1 //===- ModuloSchedule.h - Software pipeline schedule expansion ------------===// 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 // Software pipelining (SWP) is an instruction scheduling technique for loops 10 // that overlaps loop iterations and exploits ILP via compiler transformations. 11 // 12 // There are multiple methods for analyzing a loop and creating a schedule. 13 // An example algorithm is Swing Modulo Scheduling (implemented by the 14 // MachinePipeliner). The details of how a schedule is arrived at are irrelevant 15 // for the task of actually rewriting a loop to adhere to the schedule, which 16 // is what this file does. 17 // 18 // A schedule is, for every instruction in a block, a Cycle and a Stage. Note 19 // that we only support single-block loops, so "block" and "loop" can be used 20 // interchangably. 21 // 22 // The Cycle of an instruction defines a partial order of the instructions in 23 // the remapped loop. Instructions within a cycle must not consume the output 24 // of any instruction in the same cycle. Cycle information is assumed to have 25 // been calculated such that the processor will execute instructions in 26 // lock-step (for example in a VLIW ISA). 27 // 28 // The Stage of an instruction defines the mapping between logical loop 29 // iterations and pipelined loop iterations. An example (unrolled) pipeline 30 // may look something like: 31 // 32 // I0[0] Execute instruction I0 of iteration 0 33 // I1[0], I0[1] Execute I0 of iteration 1 and I1 of iteration 1 34 // I1[1], I0[2] 35 // I1[2], I0[3] 36 // 37 // In the schedule for this unrolled sequence we would say that I0 was scheduled 38 // in stage 0 and I1 in stage 1: 39 // 40 // loop: 41 // [stage 0] x = I0 42 // [stage 1] I1 x (from stage 0) 43 // 44 // And to actually generate valid code we must insert a phi: 45 // 46 // loop: 47 // x' = phi(x) 48 // x = I0 49 // I1 x' 50 // 51 // This is a simple example; the rules for how to generate correct code given 52 // an arbitrary schedule containing loop-carried values are complex. 53 // 54 // Note that these examples only mention the steady-state kernel of the 55 // generated loop; prologs and epilogs must be generated also that prime and 56 // flush the pipeline. Doing so is nontrivial. 57 // 58 //===----------------------------------------------------------------------===// 59 60 #ifndef LLVM_CODEGEN_MODULOSCHEDULE_H 61 #define LLVM_CODEGEN_MODULOSCHEDULE_H 62 63 #include "llvm/CodeGen/MachineFunction.h" 64 #include "llvm/CodeGen/MachineLoopUtils.h" 65 #include "llvm/CodeGen/TargetInstrInfo.h" 66 #include "llvm/CodeGen/TargetSubtargetInfo.h" 67 #include <deque> 68 #include <vector> 69 70 namespace llvm { 71 class MachineBasicBlock; 72 class MachineLoop; 73 class MachineRegisterInfo; 74 class MachineInstr; 75 class LiveIntervals; 76 77 /// Represents a schedule for a single-block loop. For every instruction we 78 /// maintain a Cycle and Stage. 79 class ModuloSchedule { 80 private: 81 /// The block containing the loop instructions. 82 MachineLoop *Loop; 83 84 /// The instructions to be generated, in total order. Cycle provides a partial 85 /// order; the total order within cycles has been decided by the schedule 86 /// producer. 87 std::vector<MachineInstr *> ScheduledInstrs; 88 89 /// The cycle for each instruction. 90 DenseMap<MachineInstr *, int> Cycle; 91 92 /// The stage for each instruction. 93 DenseMap<MachineInstr *, int> Stage; 94 95 /// The number of stages in this schedule (Max(Stage) + 1). 96 int NumStages; 97 98 public: 99 /// Create a new ModuloSchedule. 100 /// \arg ScheduledInstrs The new loop instructions, in total resequenced 101 /// order. 102 /// \arg Cycle Cycle index for all instructions in ScheduledInstrs. Cycle does 103 /// not need to start at zero. ScheduledInstrs must be partially ordered by 104 /// Cycle. 105 /// \arg Stage Stage index for all instructions in ScheduleInstrs. 106 ModuloSchedule(MachineFunction &MF, MachineLoop *Loop, 107 std::vector<MachineInstr *> ScheduledInstrs, 108 DenseMap<MachineInstr *, int> Cycle, 109 DenseMap<MachineInstr *, int> Stage) 110 : Loop(Loop), ScheduledInstrs(ScheduledInstrs), Cycle(std::move(Cycle)), 111 Stage(std::move(Stage)) { 112 NumStages = 0; 113 for (auto &KV : this->Stage) 114 NumStages = std::max(NumStages, KV.second); 115 ++NumStages; 116 } 117 118 /// Return the single-block loop being scheduled. 119 MachineLoop *getLoop() const { return Loop; } 120 121 /// Return the number of stages contained in this schedule, which is the 122 /// largest stage index + 1. 123 int getNumStages() const { return NumStages; } 124 125 /// Return the first cycle in the schedule, which is the cycle index of the 126 /// first instruction. 127 int getFirstCycle() { return Cycle[ScheduledInstrs.front()]; } 128 129 /// Return the final cycle in the schedule, which is the cycle index of the 130 /// last instruction. 131 int getFinalCycle() { return Cycle[ScheduledInstrs.back()]; } 132 133 /// Return the stage that MI is scheduled in, or -1. 134 int getStage(MachineInstr *MI) { 135 auto I = Stage.find(MI); 136 return I == Stage.end() ? -1 : I->second; 137 } 138 139 /// Return the cycle that MI is scheduled at, or -1. 140 int getCycle(MachineInstr *MI) { 141 auto I = Cycle.find(MI); 142 return I == Cycle.end() ? -1 : I->second; 143 } 144 145 /// Set the stage of a newly created instruction. 146 void setStage(MachineInstr *MI, int MIStage) { 147 assert(Stage.count(MI) == 0); 148 Stage[MI] = MIStage; 149 } 150 151 /// Return the rescheduled instructions in order. 152 ArrayRef<MachineInstr *> getInstructions() { return ScheduledInstrs; } 153 154 void dump() { print(dbgs()); } 155 void print(raw_ostream &OS); 156 }; 157 158 /// The ModuloScheduleExpander takes a ModuloSchedule and expands it in-place, 159 /// rewriting the old loop and inserting prologs and epilogs as required. 160 class ModuloScheduleExpander { 161 public: 162 using InstrChangesTy = DenseMap<MachineInstr *, std::pair<unsigned, int64_t>>; 163 164 private: 165 using ValueMapTy = DenseMap<unsigned, unsigned>; 166 using MBBVectorTy = SmallVectorImpl<MachineBasicBlock *>; 167 using InstrMapTy = DenseMap<MachineInstr *, MachineInstr *>; 168 169 ModuloSchedule &Schedule; 170 MachineFunction &MF; 171 const TargetSubtargetInfo &ST; 172 MachineRegisterInfo &MRI; 173 const TargetInstrInfo *TII; 174 LiveIntervals &LIS; 175 176 MachineBasicBlock *BB; 177 MachineBasicBlock *Preheader; 178 MachineBasicBlock *NewKernel = nullptr; 179 std::unique_ptr<TargetInstrInfo::PipelinerLoopInfo> LoopInfo; 180 181 /// Map for each register and the max difference between its uses and def. 182 /// The first element in the pair is the max difference in stages. The 183 /// second is true if the register defines a Phi value and loop value is 184 /// scheduled before the Phi. 185 std::map<unsigned, std::pair<unsigned, bool>> RegToStageDiff; 186 187 /// Instructions to change when emitting the final schedule. 188 InstrChangesTy InstrChanges; 189 190 void generatePipelinedLoop(); 191 void generateProlog(unsigned LastStage, MachineBasicBlock *KernelBB, 192 ValueMapTy *VRMap, MBBVectorTy &PrologBBs); 193 void generateEpilog(unsigned LastStage, MachineBasicBlock *KernelBB, 194 MachineBasicBlock *OrigBB, ValueMapTy *VRMap, 195 MBBVectorTy &EpilogBBs, MBBVectorTy &PrologBBs); 196 void generateExistingPhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1, 197 MachineBasicBlock *BB2, MachineBasicBlock *KernelBB, 198 ValueMapTy *VRMap, InstrMapTy &InstrMap, 199 unsigned LastStageNum, unsigned CurStageNum, 200 bool IsLast); 201 void generatePhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1, 202 MachineBasicBlock *BB2, MachineBasicBlock *KernelBB, 203 ValueMapTy *VRMap, InstrMapTy &InstrMap, 204 unsigned LastStageNum, unsigned CurStageNum, bool IsLast); 205 void removeDeadInstructions(MachineBasicBlock *KernelBB, 206 MBBVectorTy &EpilogBBs); 207 void splitLifetimes(MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs); 208 void addBranches(MachineBasicBlock &PreheaderBB, MBBVectorTy &PrologBBs, 209 MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs, 210 ValueMapTy *VRMap); 211 bool computeDelta(MachineInstr &MI, unsigned &Delta); 212 void updateMemOperands(MachineInstr &NewMI, MachineInstr &OldMI, 213 unsigned Num); 214 MachineInstr *cloneInstr(MachineInstr *OldMI, unsigned CurStageNum, 215 unsigned InstStageNum); 216 MachineInstr *cloneAndChangeInstr(MachineInstr *OldMI, unsigned CurStageNum, 217 unsigned InstStageNum); 218 void updateInstruction(MachineInstr *NewMI, bool LastDef, 219 unsigned CurStageNum, unsigned InstrStageNum, 220 ValueMapTy *VRMap); 221 MachineInstr *findDefInLoop(unsigned Reg); 222 unsigned getPrevMapVal(unsigned StageNum, unsigned PhiStage, unsigned LoopVal, 223 unsigned LoopStage, ValueMapTy *VRMap, 224 MachineBasicBlock *BB); 225 void rewritePhiValues(MachineBasicBlock *NewBB, unsigned StageNum, 226 ValueMapTy *VRMap, InstrMapTy &InstrMap); 227 void rewriteScheduledInstr(MachineBasicBlock *BB, InstrMapTy &InstrMap, 228 unsigned CurStageNum, unsigned PhiNum, 229 MachineInstr *Phi, unsigned OldReg, 230 unsigned NewReg, unsigned PrevReg = 0); 231 bool isLoopCarried(MachineInstr &Phi); 232 233 /// Return the max. number of stages/iterations that can occur between a 234 /// register definition and its uses. 235 unsigned getStagesForReg(int Reg, unsigned CurStage) { 236 std::pair<unsigned, bool> Stages = RegToStageDiff[Reg]; 237 if ((int)CurStage > Schedule.getNumStages() - 1 && Stages.first == 0 && 238 Stages.second) 239 return 1; 240 return Stages.first; 241 } 242 243 /// The number of stages for a Phi is a little different than other 244 /// instructions. The minimum value computed in RegToStageDiff is 1 245 /// because we assume the Phi is needed for at least 1 iteration. 246 /// This is not the case if the loop value is scheduled prior to the 247 /// Phi in the same stage. This function returns the number of stages 248 /// or iterations needed between the Phi definition and any uses. 249 unsigned getStagesForPhi(int Reg) { 250 std::pair<unsigned, bool> Stages = RegToStageDiff[Reg]; 251 if (Stages.second) 252 return Stages.first; 253 return Stages.first - 1; 254 } 255 256 public: 257 /// Create a new ModuloScheduleExpander. 258 /// \arg InstrChanges Modifications to make to instructions with memory 259 /// operands. 260 /// FIXME: InstrChanges is opaque and is an implementation detail of an 261 /// optimization in MachinePipeliner that crosses abstraction boundaries. 262 ModuloScheduleExpander(MachineFunction &MF, ModuloSchedule &S, 263 LiveIntervals &LIS, InstrChangesTy InstrChanges) 264 : Schedule(S), MF(MF), ST(MF.getSubtarget()), MRI(MF.getRegInfo()), 265 TII(ST.getInstrInfo()), LIS(LIS), 266 InstrChanges(std::move(InstrChanges)) {} 267 268 /// Performs the actual expansion. 269 void expand(); 270 /// Performs final cleanup after expansion. 271 void cleanup(); 272 273 /// Returns the newly rewritten kernel block, or nullptr if this was 274 /// optimized away. 275 MachineBasicBlock *getRewrittenKernel() { return NewKernel; } 276 }; 277 278 /// A reimplementation of ModuloScheduleExpander. It works by generating a 279 /// standalone kernel loop and peeling out the prologs and epilogs. 280 class PeelingModuloScheduleExpander { 281 public: 282 PeelingModuloScheduleExpander(MachineFunction &MF, ModuloSchedule &S, 283 LiveIntervals *LIS) 284 : Schedule(S), MF(MF), ST(MF.getSubtarget()), MRI(MF.getRegInfo()), 285 TII(ST.getInstrInfo()), LIS(LIS) {} 286 287 void expand(); 288 289 /// Runs ModuloScheduleExpander and treats it as a golden input to validate 290 /// aspects of the code generated by PeelingModuloScheduleExpander. 291 void validateAgainstModuloScheduleExpander(); 292 293 protected: 294 ModuloSchedule &Schedule; 295 MachineFunction &MF; 296 const TargetSubtargetInfo &ST; 297 MachineRegisterInfo &MRI; 298 const TargetInstrInfo *TII; 299 LiveIntervals *LIS; 300 301 /// The original loop block that gets rewritten in-place. 302 MachineBasicBlock *BB; 303 /// The original loop preheader. 304 MachineBasicBlock *Preheader; 305 /// All prolog and epilog blocks. 306 SmallVector<MachineBasicBlock *, 4> Prologs, Epilogs; 307 /// For every block, the stages that are produced. 308 DenseMap<MachineBasicBlock *, BitVector> LiveStages; 309 /// For every block, the stages that are available. A stage can be available 310 /// but not produced (in the epilog) or produced but not available (in the 311 /// prolog). 312 DenseMap<MachineBasicBlock *, BitVector> AvailableStages; 313 /// When peeling the epilogue keep track of the distance between the phi 314 /// nodes and the kernel. 315 DenseMap<MachineInstr *, unsigned> PhiNodeLoopIteration; 316 317 /// CanonicalMIs and BlockMIs form a bidirectional map between any of the 318 /// loop kernel clones. 319 DenseMap<MachineInstr *, MachineInstr *> CanonicalMIs; 320 DenseMap<std::pair<MachineBasicBlock *, MachineInstr *>, MachineInstr *> 321 BlockMIs; 322 323 /// State passed from peelKernel to peelPrologAndEpilogs(). 324 std::deque<MachineBasicBlock *> PeeledFront, PeeledBack; 325 /// Illegal phis that need to be deleted once we re-link stages. 326 SmallVector<MachineInstr *, 4> IllegalPhisToDelete; 327 328 /// Converts BB from the original loop body to the rewritten, pipelined 329 /// steady-state. 330 void rewriteKernel(); 331 332 /// Peels one iteration of the rewritten kernel (BB) in the specified 333 /// direction. 334 MachineBasicBlock *peelKernel(LoopPeelDirection LPD); 335 // Delete instructions whose stage is less than MinStage in the given basic 336 // block. 337 void filterInstructions(MachineBasicBlock *MB, int MinStage); 338 // Move instructions of the given stage from sourceBB to DestBB. Remap the phi 339 // instructions to keep a valid IR. 340 void moveStageBetweenBlocks(MachineBasicBlock *DestBB, 341 MachineBasicBlock *SourceBB, unsigned Stage); 342 /// Peel the kernel forwards and backwards to produce prologs and epilogs, 343 /// and stitch them together. 344 void peelPrologAndEpilogs(); 345 /// All prolog and epilog blocks are clones of the kernel, so any produced 346 /// register in one block has an corollary in all other blocks. 347 Register getEquivalentRegisterIn(Register Reg, MachineBasicBlock *BB); 348 /// Change all users of MI, if MI is predicated out 349 /// (LiveStages[MI->getParent()] == false). 350 void rewriteUsesOf(MachineInstr *MI); 351 /// Insert branches between prologs, kernel and epilogs. 352 void fixupBranches(); 353 /// Create a poor-man's LCSSA by cloning only the PHIs from the kernel block 354 /// to a block dominated by all prologs and epilogs. This allows us to treat 355 /// the loop exiting block as any other kernel clone. 356 MachineBasicBlock *CreateLCSSAExitingBlock(); 357 /// Helper to get the stage of an instruction in the schedule. 358 unsigned getStage(MachineInstr *MI) { 359 if (CanonicalMIs.count(MI)) 360 MI = CanonicalMIs[MI]; 361 return Schedule.getStage(MI); 362 } 363 /// Helper function to find the right canonical register for a phi instruction 364 /// coming from a peeled out prologue. 365 Register getPhiCanonicalReg(MachineInstr* CanonicalPhi, MachineInstr* Phi); 366 /// Target loop info before kernel peeling. 367 std::unique_ptr<TargetInstrInfo::PipelinerLoopInfo> LoopInfo; 368 }; 369 370 /// Expander that simply annotates each scheduled instruction with a post-instr 371 /// symbol that can be consumed by the ModuloScheduleTest pass. 372 /// 373 /// The post-instr symbol is a way of annotating an instruction that can be 374 /// roundtripped in MIR. The syntax is: 375 /// MYINST %0, post-instr-symbol <mcsymbol Stage-1_Cycle-5> 376 class ModuloScheduleTestAnnotater { 377 MachineFunction &MF; 378 ModuloSchedule &S; 379 380 public: 381 ModuloScheduleTestAnnotater(MachineFunction &MF, ModuloSchedule &S) 382 : MF(MF), S(S) {} 383 384 /// Performs the annotation. 385 void annotate(); 386 }; 387 388 } // end namespace llvm 389 390 #endif // LLVM_CODEGEN_MODULOSCHEDULE_H 391