Andrew Walbran | 16937d0 | 2019-10-22 13:54:20 +0100 | [diff] [blame] | 1 | //===- MachinePipeliner.h - Machine Software Pipeliner Pass -------------===// |
| 2 | // |
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | // |
| 9 | // An implementation of the Swing Modulo Scheduling (SMS) software pipeliner. |
| 10 | // |
| 11 | // Software pipelining (SWP) is an instruction scheduling technique for loops |
| 12 | // that overlap loop iterations and exploits ILP via a compiler transformation. |
| 13 | // |
| 14 | // Swing Modulo Scheduling is an implementation of software pipelining |
| 15 | // that generates schedules that are near optimal in terms of initiation |
| 16 | // interval, register requirements, and stage count. See the papers: |
| 17 | // |
| 18 | // "Swing Modulo Scheduling: A Lifetime-Sensitive Approach", by J. Llosa, |
| 19 | // A. Gonzalez, E. Ayguade, and M. Valero. In PACT '96 Proceedings of the 1996 |
| 20 | // Conference on Parallel Architectures and Compilation Techiniques. |
| 21 | // |
| 22 | // "Lifetime-Sensitive Modulo Scheduling in a Production Environment", by J. |
| 23 | // Llosa, E. Ayguade, A. Gonzalez, M. Valero, and J. Eckhardt. In IEEE |
| 24 | // Transactions on Computers, Vol. 50, No. 3, 2001. |
| 25 | // |
| 26 | // "An Implementation of Swing Modulo Scheduling With Extensions for |
| 27 | // Superblocks", by T. Lattner, Master's Thesis, University of Illinois at |
| 28 | // Urbana-Champaign, 2005. |
| 29 | // |
| 30 | // |
| 31 | // The SMS algorithm consists of three main steps after computing the minimal |
| 32 | // initiation interval (MII). |
| 33 | // 1) Analyze the dependence graph and compute information about each |
| 34 | // instruction in the graph. |
| 35 | // 2) Order the nodes (instructions) by priority based upon the heuristics |
| 36 | // described in the algorithm. |
| 37 | // 3) Attempt to schedule the nodes in the specified order using the MII. |
| 38 | // |
| 39 | //===----------------------------------------------------------------------===// |
| 40 | #ifndef LLVM_LIB_CODEGEN_MACHINEPIPELINER_H |
| 41 | #define LLVM_LIB_CODEGEN_MACHINEPIPELINER_H |
| 42 | |
| 43 | #include "llvm/CodeGen/MachineDominators.h" |
| 44 | #include "llvm/CodeGen/RegisterClassInfo.h" |
| 45 | #include "llvm/CodeGen/ScheduleDAGInstrs.h" |
| 46 | #include "llvm/CodeGen/TargetInstrInfo.h" |
| 47 | |
| 48 | namespace llvm { |
| 49 | |
| 50 | class NodeSet; |
| 51 | class SMSchedule; |
| 52 | |
| 53 | extern cl::opt<bool> SwpEnableCopyToPhi; |
| 54 | |
| 55 | /// The main class in the implementation of the target independent |
| 56 | /// software pipeliner pass. |
| 57 | class MachinePipeliner : public MachineFunctionPass { |
| 58 | public: |
| 59 | MachineFunction *MF = nullptr; |
| 60 | const MachineLoopInfo *MLI = nullptr; |
| 61 | const MachineDominatorTree *MDT = nullptr; |
| 62 | const InstrItineraryData *InstrItins; |
| 63 | const TargetInstrInfo *TII = nullptr; |
| 64 | RegisterClassInfo RegClassInfo; |
| 65 | bool disabledByPragma = false; |
| 66 | unsigned II_setByPragma = 0; |
| 67 | |
| 68 | #ifndef NDEBUG |
| 69 | static int NumTries; |
| 70 | #endif |
| 71 | |
| 72 | /// Cache the target analysis information about the loop. |
| 73 | struct LoopInfo { |
| 74 | MachineBasicBlock *TBB = nullptr; |
| 75 | MachineBasicBlock *FBB = nullptr; |
| 76 | SmallVector<MachineOperand, 4> BrCond; |
| 77 | MachineInstr *LoopInductionVar = nullptr; |
| 78 | MachineInstr *LoopCompare = nullptr; |
| 79 | }; |
| 80 | LoopInfo LI; |
| 81 | |
| 82 | static char ID; |
| 83 | |
| 84 | MachinePipeliner() : MachineFunctionPass(ID) { |
| 85 | initializeMachinePipelinerPass(*PassRegistry::getPassRegistry()); |
| 86 | } |
| 87 | |
| 88 | bool runOnMachineFunction(MachineFunction &MF) override; |
| 89 | |
| 90 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
| 91 | AU.addRequired<AAResultsWrapperPass>(); |
| 92 | AU.addPreserved<AAResultsWrapperPass>(); |
| 93 | AU.addRequired<MachineLoopInfo>(); |
| 94 | AU.addRequired<MachineDominatorTree>(); |
| 95 | AU.addRequired<LiveIntervals>(); |
| 96 | MachineFunctionPass::getAnalysisUsage(AU); |
| 97 | } |
| 98 | |
| 99 | private: |
| 100 | void preprocessPhiNodes(MachineBasicBlock &B); |
| 101 | bool canPipelineLoop(MachineLoop &L); |
| 102 | bool scheduleLoop(MachineLoop &L); |
| 103 | bool swingModuloScheduler(MachineLoop &L); |
| 104 | void setPragmaPipelineOptions(MachineLoop &L); |
| 105 | }; |
| 106 | |
| 107 | /// This class builds the dependence graph for the instructions in a loop, |
| 108 | /// and attempts to schedule the instructions using the SMS algorithm. |
| 109 | class SwingSchedulerDAG : public ScheduleDAGInstrs { |
| 110 | MachinePipeliner &Pass; |
| 111 | /// The minimum initiation interval between iterations for this schedule. |
| 112 | unsigned MII = 0; |
| 113 | /// The maximum initiation interval between iterations for this schedule. |
| 114 | unsigned MAX_II = 0; |
| 115 | /// Set to true if a valid pipelined schedule is found for the loop. |
| 116 | bool Scheduled = false; |
| 117 | MachineLoop &Loop; |
| 118 | LiveIntervals &LIS; |
| 119 | const RegisterClassInfo &RegClassInfo; |
| 120 | unsigned II_setByPragma = 0; |
| 121 | |
| 122 | /// A toplogical ordering of the SUnits, which is needed for changing |
| 123 | /// dependences and iterating over the SUnits. |
| 124 | ScheduleDAGTopologicalSort Topo; |
| 125 | |
| 126 | struct NodeInfo { |
| 127 | int ASAP = 0; |
| 128 | int ALAP = 0; |
| 129 | int ZeroLatencyDepth = 0; |
| 130 | int ZeroLatencyHeight = 0; |
| 131 | |
| 132 | NodeInfo() = default; |
| 133 | }; |
| 134 | /// Computed properties for each node in the graph. |
| 135 | std::vector<NodeInfo> ScheduleInfo; |
| 136 | |
| 137 | enum OrderKind { BottomUp = 0, TopDown = 1 }; |
| 138 | /// Computed node ordering for scheduling. |
| 139 | SetVector<SUnit *> NodeOrder; |
| 140 | |
| 141 | using NodeSetType = SmallVector<NodeSet, 8>; |
| 142 | using ValueMapTy = DenseMap<unsigned, unsigned>; |
| 143 | using MBBVectorTy = SmallVectorImpl<MachineBasicBlock *>; |
| 144 | using InstrMapTy = DenseMap<MachineInstr *, MachineInstr *>; |
| 145 | |
| 146 | /// Instructions to change when emitting the final schedule. |
| 147 | DenseMap<SUnit *, std::pair<unsigned, int64_t>> InstrChanges; |
| 148 | |
| 149 | /// We may create a new instruction, so remember it because it |
| 150 | /// must be deleted when the pass is finished. |
| 151 | SmallPtrSet<MachineInstr *, 4> NewMIs; |
| 152 | |
| 153 | /// Ordered list of DAG postprocessing steps. |
| 154 | std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations; |
| 155 | |
| 156 | /// Helper class to implement Johnson's circuit finding algorithm. |
| 157 | class Circuits { |
| 158 | std::vector<SUnit> &SUnits; |
| 159 | SetVector<SUnit *> Stack; |
| 160 | BitVector Blocked; |
| 161 | SmallVector<SmallPtrSet<SUnit *, 4>, 10> B; |
| 162 | SmallVector<SmallVector<int, 4>, 16> AdjK; |
| 163 | // Node to Index from ScheduleDAGTopologicalSort |
| 164 | std::vector<int> *Node2Idx; |
| 165 | unsigned NumPaths; |
| 166 | static unsigned MaxPaths; |
| 167 | |
| 168 | public: |
| 169 | Circuits(std::vector<SUnit> &SUs, ScheduleDAGTopologicalSort &Topo) |
| 170 | : SUnits(SUs), Blocked(SUs.size()), B(SUs.size()), AdjK(SUs.size()) { |
| 171 | Node2Idx = new std::vector<int>(SUs.size()); |
| 172 | unsigned Idx = 0; |
| 173 | for (const auto &NodeNum : Topo) |
| 174 | Node2Idx->at(NodeNum) = Idx++; |
| 175 | } |
| 176 | |
| 177 | ~Circuits() { delete Node2Idx; } |
| 178 | |
| 179 | /// Reset the data structures used in the circuit algorithm. |
| 180 | void reset() { |
| 181 | Stack.clear(); |
| 182 | Blocked.reset(); |
| 183 | B.assign(SUnits.size(), SmallPtrSet<SUnit *, 4>()); |
| 184 | NumPaths = 0; |
| 185 | } |
| 186 | |
| 187 | void createAdjacencyStructure(SwingSchedulerDAG *DAG); |
| 188 | bool circuit(int V, int S, NodeSetType &NodeSets, bool HasBackedge = false); |
| 189 | void unblock(int U); |
| 190 | }; |
| 191 | |
| 192 | struct CopyToPhiMutation : public ScheduleDAGMutation { |
| 193 | void apply(ScheduleDAGInstrs *DAG) override; |
| 194 | }; |
| 195 | |
| 196 | public: |
| 197 | SwingSchedulerDAG(MachinePipeliner &P, MachineLoop &L, LiveIntervals &lis, |
| 198 | const RegisterClassInfo &rci, unsigned II) |
| 199 | : ScheduleDAGInstrs(*P.MF, P.MLI, false), Pass(P), Loop(L), LIS(lis), |
| 200 | RegClassInfo(rci), II_setByPragma(II), Topo(SUnits, &ExitSU) { |
| 201 | P.MF->getSubtarget().getSMSMutations(Mutations); |
| 202 | if (SwpEnableCopyToPhi) |
| 203 | Mutations.push_back(llvm::make_unique<CopyToPhiMutation>()); |
| 204 | } |
| 205 | |
| 206 | void schedule() override; |
| 207 | void finishBlock() override; |
| 208 | |
| 209 | /// Return true if the loop kernel has been scheduled. |
| 210 | bool hasNewSchedule() { return Scheduled; } |
| 211 | |
| 212 | /// Return the earliest time an instruction may be scheduled. |
| 213 | int getASAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ASAP; } |
| 214 | |
| 215 | /// Return the latest time an instruction my be scheduled. |
| 216 | int getALAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ALAP; } |
| 217 | |
| 218 | /// The mobility function, which the number of slots in which |
| 219 | /// an instruction may be scheduled. |
| 220 | int getMOV(SUnit *Node) { return getALAP(Node) - getASAP(Node); } |
| 221 | |
| 222 | /// The depth, in the dependence graph, for a node. |
| 223 | unsigned getDepth(SUnit *Node) { return Node->getDepth(); } |
| 224 | |
| 225 | /// The maximum unweighted length of a path from an arbitrary node to the |
| 226 | /// given node in which each edge has latency 0 |
| 227 | int getZeroLatencyDepth(SUnit *Node) { |
| 228 | return ScheduleInfo[Node->NodeNum].ZeroLatencyDepth; |
| 229 | } |
| 230 | |
| 231 | /// The height, in the dependence graph, for a node. |
| 232 | unsigned getHeight(SUnit *Node) { return Node->getHeight(); } |
| 233 | |
| 234 | /// The maximum unweighted length of a path from the given node to an |
| 235 | /// arbitrary node in which each edge has latency 0 |
| 236 | int getZeroLatencyHeight(SUnit *Node) { |
| 237 | return ScheduleInfo[Node->NodeNum].ZeroLatencyHeight; |
| 238 | } |
| 239 | |
| 240 | /// Return true if the dependence is a back-edge in the data dependence graph. |
| 241 | /// Since the DAG doesn't contain cycles, we represent a cycle in the graph |
| 242 | /// using an anti dependence from a Phi to an instruction. |
| 243 | bool isBackedge(SUnit *Source, const SDep &Dep) { |
| 244 | if (Dep.getKind() != SDep::Anti) |
| 245 | return false; |
| 246 | return Source->getInstr()->isPHI() || Dep.getSUnit()->getInstr()->isPHI(); |
| 247 | } |
| 248 | |
| 249 | bool isLoopCarriedDep(SUnit *Source, const SDep &Dep, bool isSucc = true); |
| 250 | |
| 251 | /// The distance function, which indicates that operation V of iteration I |
| 252 | /// depends on operations U of iteration I-distance. |
| 253 | unsigned getDistance(SUnit *U, SUnit *V, const SDep &Dep) { |
| 254 | // Instructions that feed a Phi have a distance of 1. Computing larger |
| 255 | // values for arrays requires data dependence information. |
| 256 | if (V->getInstr()->isPHI() && Dep.getKind() == SDep::Anti) |
| 257 | return 1; |
| 258 | return 0; |
| 259 | } |
| 260 | |
| 261 | void applyInstrChange(MachineInstr *MI, SMSchedule &Schedule); |
| 262 | |
| 263 | void fixupRegisterOverlaps(std::deque<SUnit *> &Instrs); |
| 264 | |
| 265 | /// Return the new base register that was stored away for the changed |
| 266 | /// instruction. |
| 267 | unsigned getInstrBaseReg(SUnit *SU) { |
| 268 | DenseMap<SUnit *, std::pair<unsigned, int64_t>>::iterator It = |
| 269 | InstrChanges.find(SU); |
| 270 | if (It != InstrChanges.end()) |
| 271 | return It->second.first; |
| 272 | return 0; |
| 273 | } |
| 274 | |
| 275 | void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) { |
| 276 | Mutations.push_back(std::move(Mutation)); |
| 277 | } |
| 278 | |
| 279 | static bool classof(const ScheduleDAGInstrs *DAG) { return true; } |
| 280 | |
| 281 | private: |
| 282 | void addLoopCarriedDependences(AliasAnalysis *AA); |
| 283 | void updatePhiDependences(); |
| 284 | void changeDependences(); |
| 285 | unsigned calculateResMII(); |
| 286 | unsigned calculateRecMII(NodeSetType &RecNodeSets); |
| 287 | void findCircuits(NodeSetType &NodeSets); |
| 288 | void fuseRecs(NodeSetType &NodeSets); |
| 289 | void removeDuplicateNodes(NodeSetType &NodeSets); |
| 290 | void computeNodeFunctions(NodeSetType &NodeSets); |
| 291 | void registerPressureFilter(NodeSetType &NodeSets); |
| 292 | void colocateNodeSets(NodeSetType &NodeSets); |
| 293 | void checkNodeSets(NodeSetType &NodeSets); |
| 294 | void groupRemainingNodes(NodeSetType &NodeSets); |
| 295 | void addConnectedNodes(SUnit *SU, NodeSet &NewSet, |
| 296 | SetVector<SUnit *> &NodesAdded); |
| 297 | void computeNodeOrder(NodeSetType &NodeSets); |
| 298 | void checkValidNodeOrder(const NodeSetType &Circuits) const; |
| 299 | bool schedulePipeline(SMSchedule &Schedule); |
| 300 | void generatePipelinedLoop(SMSchedule &Schedule); |
| 301 | void generateProlog(SMSchedule &Schedule, unsigned LastStage, |
| 302 | MachineBasicBlock *KernelBB, ValueMapTy *VRMap, |
| 303 | MBBVectorTy &PrologBBs); |
| 304 | void generateEpilog(SMSchedule &Schedule, unsigned LastStage, |
| 305 | MachineBasicBlock *KernelBB, ValueMapTy *VRMap, |
| 306 | MBBVectorTy &EpilogBBs, MBBVectorTy &PrologBBs); |
| 307 | void generateExistingPhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1, |
| 308 | MachineBasicBlock *BB2, MachineBasicBlock *KernelBB, |
| 309 | SMSchedule &Schedule, ValueMapTy *VRMap, |
| 310 | InstrMapTy &InstrMap, unsigned LastStageNum, |
| 311 | unsigned CurStageNum, bool IsLast); |
| 312 | void generatePhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1, |
| 313 | MachineBasicBlock *BB2, MachineBasicBlock *KernelBB, |
| 314 | SMSchedule &Schedule, ValueMapTy *VRMap, |
| 315 | InstrMapTy &InstrMap, unsigned LastStageNum, |
| 316 | unsigned CurStageNum, bool IsLast); |
| 317 | void removeDeadInstructions(MachineBasicBlock *KernelBB, |
| 318 | MBBVectorTy &EpilogBBs); |
| 319 | void splitLifetimes(MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs, |
| 320 | SMSchedule &Schedule); |
| 321 | void addBranches(MBBVectorTy &PrologBBs, MachineBasicBlock *KernelBB, |
| 322 | MBBVectorTy &EpilogBBs, SMSchedule &Schedule, |
| 323 | ValueMapTy *VRMap); |
| 324 | bool computeDelta(MachineInstr &MI, unsigned &Delta); |
| 325 | void updateMemOperands(MachineInstr &NewMI, MachineInstr &OldMI, |
| 326 | unsigned Num); |
| 327 | MachineInstr *cloneInstr(MachineInstr *OldMI, unsigned CurStageNum, |
| 328 | unsigned InstStageNum); |
| 329 | MachineInstr *cloneAndChangeInstr(MachineInstr *OldMI, unsigned CurStageNum, |
| 330 | unsigned InstStageNum, |
| 331 | SMSchedule &Schedule); |
| 332 | void updateInstruction(MachineInstr *NewMI, bool LastDef, |
| 333 | unsigned CurStageNum, unsigned InstrStageNum, |
| 334 | SMSchedule &Schedule, ValueMapTy *VRMap); |
| 335 | MachineInstr *findDefInLoop(unsigned Reg); |
| 336 | unsigned getPrevMapVal(unsigned StageNum, unsigned PhiStage, unsigned LoopVal, |
| 337 | unsigned LoopStage, ValueMapTy *VRMap, |
| 338 | MachineBasicBlock *BB); |
| 339 | void rewritePhiValues(MachineBasicBlock *NewBB, unsigned StageNum, |
| 340 | SMSchedule &Schedule, ValueMapTy *VRMap, |
| 341 | InstrMapTy &InstrMap); |
| 342 | void rewriteScheduledInstr(MachineBasicBlock *BB, SMSchedule &Schedule, |
| 343 | InstrMapTy &InstrMap, unsigned CurStageNum, |
| 344 | unsigned PhiNum, MachineInstr *Phi, |
| 345 | unsigned OldReg, unsigned NewReg, |
| 346 | unsigned PrevReg = 0); |
| 347 | bool canUseLastOffsetValue(MachineInstr *MI, unsigned &BasePos, |
| 348 | unsigned &OffsetPos, unsigned &NewBase, |
| 349 | int64_t &NewOffset); |
| 350 | void postprocessDAG(); |
| 351 | /// Set the Minimum Initiation Interval for this schedule attempt. |
| 352 | void setMII(unsigned ResMII, unsigned RecMII); |
| 353 | /// Set the Maximum Initiation Interval for this schedule attempt. |
| 354 | void setMAX_II(); |
| 355 | }; |
| 356 | |
| 357 | /// A NodeSet contains a set of SUnit DAG nodes with additional information |
| 358 | /// that assigns a priority to the set. |
| 359 | class NodeSet { |
| 360 | SetVector<SUnit *> Nodes; |
| 361 | bool HasRecurrence = false; |
| 362 | unsigned RecMII = 0; |
| 363 | int MaxMOV = 0; |
| 364 | unsigned MaxDepth = 0; |
| 365 | unsigned Colocate = 0; |
| 366 | SUnit *ExceedPressure = nullptr; |
| 367 | unsigned Latency = 0; |
| 368 | |
| 369 | public: |
| 370 | using iterator = SetVector<SUnit *>::const_iterator; |
| 371 | |
| 372 | NodeSet() = default; |
| 373 | NodeSet(iterator S, iterator E) : Nodes(S, E), HasRecurrence(true) { |
| 374 | Latency = 0; |
| 375 | for (unsigned i = 0, e = Nodes.size(); i < e; ++i) |
| 376 | for (const SDep &Succ : Nodes[i]->Succs) |
| 377 | if (Nodes.count(Succ.getSUnit())) |
| 378 | Latency += Succ.getLatency(); |
| 379 | } |
| 380 | |
| 381 | bool insert(SUnit *SU) { return Nodes.insert(SU); } |
| 382 | |
| 383 | void insert(iterator S, iterator E) { Nodes.insert(S, E); } |
| 384 | |
| 385 | template <typename UnaryPredicate> bool remove_if(UnaryPredicate P) { |
| 386 | return Nodes.remove_if(P); |
| 387 | } |
| 388 | |
| 389 | unsigned count(SUnit *SU) const { return Nodes.count(SU); } |
| 390 | |
| 391 | bool hasRecurrence() { return HasRecurrence; }; |
| 392 | |
| 393 | unsigned size() const { return Nodes.size(); } |
| 394 | |
| 395 | bool empty() const { return Nodes.empty(); } |
| 396 | |
| 397 | SUnit *getNode(unsigned i) const { return Nodes[i]; }; |
| 398 | |
| 399 | void setRecMII(unsigned mii) { RecMII = mii; }; |
| 400 | |
| 401 | void setColocate(unsigned c) { Colocate = c; }; |
| 402 | |
| 403 | void setExceedPressure(SUnit *SU) { ExceedPressure = SU; } |
| 404 | |
| 405 | bool isExceedSU(SUnit *SU) { return ExceedPressure == SU; } |
| 406 | |
| 407 | int compareRecMII(NodeSet &RHS) { return RecMII - RHS.RecMII; } |
| 408 | |
| 409 | int getRecMII() { return RecMII; } |
| 410 | |
| 411 | /// Summarize node functions for the entire node set. |
| 412 | void computeNodeSetInfo(SwingSchedulerDAG *SSD) { |
| 413 | for (SUnit *SU : *this) { |
| 414 | MaxMOV = std::max(MaxMOV, SSD->getMOV(SU)); |
| 415 | MaxDepth = std::max(MaxDepth, SSD->getDepth(SU)); |
| 416 | } |
| 417 | } |
| 418 | |
| 419 | unsigned getLatency() { return Latency; } |
| 420 | |
| 421 | unsigned getMaxDepth() { return MaxDepth; } |
| 422 | |
| 423 | void clear() { |
| 424 | Nodes.clear(); |
| 425 | RecMII = 0; |
| 426 | HasRecurrence = false; |
| 427 | MaxMOV = 0; |
| 428 | MaxDepth = 0; |
| 429 | Colocate = 0; |
| 430 | ExceedPressure = nullptr; |
| 431 | } |
| 432 | |
| 433 | operator SetVector<SUnit *> &() { return Nodes; } |
| 434 | |
| 435 | /// Sort the node sets by importance. First, rank them by recurrence MII, |
| 436 | /// then by mobility (least mobile done first), and finally by depth. |
| 437 | /// Each node set may contain a colocate value which is used as the first |
| 438 | /// tie breaker, if it's set. |
| 439 | bool operator>(const NodeSet &RHS) const { |
| 440 | if (RecMII == RHS.RecMII) { |
| 441 | if (Colocate != 0 && RHS.Colocate != 0 && Colocate != RHS.Colocate) |
| 442 | return Colocate < RHS.Colocate; |
| 443 | if (MaxMOV == RHS.MaxMOV) |
| 444 | return MaxDepth > RHS.MaxDepth; |
| 445 | return MaxMOV < RHS.MaxMOV; |
| 446 | } |
| 447 | return RecMII > RHS.RecMII; |
| 448 | } |
| 449 | |
| 450 | bool operator==(const NodeSet &RHS) const { |
| 451 | return RecMII == RHS.RecMII && MaxMOV == RHS.MaxMOV && |
| 452 | MaxDepth == RHS.MaxDepth; |
| 453 | } |
| 454 | |
| 455 | bool operator!=(const NodeSet &RHS) const { return !operator==(RHS); } |
| 456 | |
| 457 | iterator begin() { return Nodes.begin(); } |
| 458 | iterator end() { return Nodes.end(); } |
| 459 | void print(raw_ostream &os) const; |
| 460 | |
| 461 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| 462 | LLVM_DUMP_METHOD void dump() const; |
| 463 | #endif |
| 464 | }; |
| 465 | |
| 466 | /// This class represents the scheduled code. The main data structure is a |
| 467 | /// map from scheduled cycle to instructions. During scheduling, the |
| 468 | /// data structure explicitly represents all stages/iterations. When |
| 469 | /// the algorithm finshes, the schedule is collapsed into a single stage, |
| 470 | /// which represents instructions from different loop iterations. |
| 471 | /// |
| 472 | /// The SMS algorithm allows negative values for cycles, so the first cycle |
| 473 | /// in the schedule is the smallest cycle value. |
| 474 | class SMSchedule { |
| 475 | private: |
| 476 | /// Map from execution cycle to instructions. |
| 477 | DenseMap<int, std::deque<SUnit *>> ScheduledInstrs; |
| 478 | |
| 479 | /// Map from instruction to execution cycle. |
| 480 | std::map<SUnit *, int> InstrToCycle; |
| 481 | |
| 482 | /// Map for each register and the max difference between its uses and def. |
| 483 | /// The first element in the pair is the max difference in stages. The |
| 484 | /// second is true if the register defines a Phi value and loop value is |
| 485 | /// scheduled before the Phi. |
| 486 | std::map<unsigned, std::pair<unsigned, bool>> RegToStageDiff; |
| 487 | |
| 488 | /// Keep track of the first cycle value in the schedule. It starts |
| 489 | /// as zero, but the algorithm allows negative values. |
| 490 | int FirstCycle = 0; |
| 491 | |
| 492 | /// Keep track of the last cycle value in the schedule. |
| 493 | int LastCycle = 0; |
| 494 | |
| 495 | /// The initiation interval (II) for the schedule. |
| 496 | int InitiationInterval = 0; |
| 497 | |
| 498 | /// Target machine information. |
| 499 | const TargetSubtargetInfo &ST; |
| 500 | |
| 501 | /// Virtual register information. |
| 502 | MachineRegisterInfo &MRI; |
| 503 | |
| 504 | std::unique_ptr<DFAPacketizer> Resources; |
| 505 | |
| 506 | public: |
| 507 | SMSchedule(MachineFunction *mf) |
| 508 | : ST(mf->getSubtarget()), MRI(mf->getRegInfo()), |
| 509 | Resources(ST.getInstrInfo()->CreateTargetScheduleState(ST)) {} |
| 510 | |
| 511 | void reset() { |
| 512 | ScheduledInstrs.clear(); |
| 513 | InstrToCycle.clear(); |
| 514 | RegToStageDiff.clear(); |
| 515 | FirstCycle = 0; |
| 516 | LastCycle = 0; |
| 517 | InitiationInterval = 0; |
| 518 | } |
| 519 | |
| 520 | /// Set the initiation interval for this schedule. |
| 521 | void setInitiationInterval(int ii) { InitiationInterval = ii; } |
| 522 | |
| 523 | /// Return the first cycle in the completed schedule. This |
| 524 | /// can be a negative value. |
| 525 | int getFirstCycle() const { return FirstCycle; } |
| 526 | |
| 527 | /// Return the last cycle in the finalized schedule. |
| 528 | int getFinalCycle() const { return FirstCycle + InitiationInterval - 1; } |
| 529 | |
| 530 | /// Return the cycle of the earliest scheduled instruction in the dependence |
| 531 | /// chain. |
| 532 | int earliestCycleInChain(const SDep &Dep); |
| 533 | |
| 534 | /// Return the cycle of the latest scheduled instruction in the dependence |
| 535 | /// chain. |
| 536 | int latestCycleInChain(const SDep &Dep); |
| 537 | |
| 538 | void computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart, |
| 539 | int *MinEnd, int *MaxStart, int II, SwingSchedulerDAG *DAG); |
| 540 | bool insert(SUnit *SU, int StartCycle, int EndCycle, int II); |
| 541 | |
| 542 | /// Iterators for the cycle to instruction map. |
| 543 | using sched_iterator = DenseMap<int, std::deque<SUnit *>>::iterator; |
| 544 | using const_sched_iterator = |
| 545 | DenseMap<int, std::deque<SUnit *>>::const_iterator; |
| 546 | |
| 547 | /// Return true if the instruction is scheduled at the specified stage. |
| 548 | bool isScheduledAtStage(SUnit *SU, unsigned StageNum) { |
| 549 | return (stageScheduled(SU) == (int)StageNum); |
| 550 | } |
| 551 | |
| 552 | /// Return the stage for a scheduled instruction. Return -1 if |
| 553 | /// the instruction has not been scheduled. |
| 554 | int stageScheduled(SUnit *SU) const { |
| 555 | std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU); |
| 556 | if (it == InstrToCycle.end()) |
| 557 | return -1; |
| 558 | return (it->second - FirstCycle) / InitiationInterval; |
| 559 | } |
| 560 | |
| 561 | /// Return the cycle for a scheduled instruction. This function normalizes |
| 562 | /// the first cycle to be 0. |
| 563 | unsigned cycleScheduled(SUnit *SU) const { |
| 564 | std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU); |
| 565 | assert(it != InstrToCycle.end() && "Instruction hasn't been scheduled."); |
| 566 | return (it->second - FirstCycle) % InitiationInterval; |
| 567 | } |
| 568 | |
| 569 | /// Return the maximum stage count needed for this schedule. |
| 570 | unsigned getMaxStageCount() { |
| 571 | return (LastCycle - FirstCycle) / InitiationInterval; |
| 572 | } |
| 573 | |
| 574 | /// Return the max. number of stages/iterations that can occur between a |
| 575 | /// register definition and its uses. |
| 576 | unsigned getStagesForReg(int Reg, unsigned CurStage) { |
| 577 | std::pair<unsigned, bool> Stages = RegToStageDiff[Reg]; |
| 578 | if (CurStage > getMaxStageCount() && Stages.first == 0 && Stages.second) |
| 579 | return 1; |
| 580 | return Stages.first; |
| 581 | } |
| 582 | |
| 583 | /// The number of stages for a Phi is a little different than other |
| 584 | /// instructions. The minimum value computed in RegToStageDiff is 1 |
| 585 | /// because we assume the Phi is needed for at least 1 iteration. |
| 586 | /// This is not the case if the loop value is scheduled prior to the |
| 587 | /// Phi in the same stage. This function returns the number of stages |
| 588 | /// or iterations needed between the Phi definition and any uses. |
| 589 | unsigned getStagesForPhi(int Reg) { |
| 590 | std::pair<unsigned, bool> Stages = RegToStageDiff[Reg]; |
| 591 | if (Stages.second) |
| 592 | return Stages.first; |
| 593 | return Stages.first - 1; |
| 594 | } |
| 595 | |
| 596 | /// Return the instructions that are scheduled at the specified cycle. |
| 597 | std::deque<SUnit *> &getInstructions(int cycle) { |
| 598 | return ScheduledInstrs[cycle]; |
| 599 | } |
| 600 | |
| 601 | bool isValidSchedule(SwingSchedulerDAG *SSD); |
| 602 | void finalizeSchedule(SwingSchedulerDAG *SSD); |
| 603 | void orderDependence(SwingSchedulerDAG *SSD, SUnit *SU, |
| 604 | std::deque<SUnit *> &Insts); |
| 605 | bool isLoopCarried(SwingSchedulerDAG *SSD, MachineInstr &Phi); |
| 606 | bool isLoopCarriedDefOfUse(SwingSchedulerDAG *SSD, MachineInstr *Def, |
| 607 | MachineOperand &MO); |
| 608 | void print(raw_ostream &os) const; |
| 609 | void dump() const; |
| 610 | }; |
| 611 | |
| 612 | } // end namespace llvm |
| 613 | |
| 614 | #endif // LLVM_LIB_CODEGEN_MACHINEPIPELINER_H |