Index: llvm/trunk/include/llvm/CodeGen/MachinePipeliner.h =================================================================== --- llvm/trunk/include/llvm/CodeGen/MachinePipeliner.h +++ llvm/trunk/include/llvm/CodeGen/MachinePipeliner.h @@ -148,7 +148,7 @@ /// We may create a new instruction, so remember it because it /// must be deleted when the pass is finished. - SmallPtrSet NewMIs; + DenseMap NewMIs; /// Ordered list of DAG postprocessing steps. std::vector> Mutations; @@ -297,53 +297,8 @@ void computeNodeOrder(NodeSetType &NodeSets); void checkValidNodeOrder(const NodeSetType &Circuits) const; bool schedulePipeline(SMSchedule &Schedule); - void generatePipelinedLoop(SMSchedule &Schedule); - void generateProlog(SMSchedule &Schedule, unsigned LastStage, - MachineBasicBlock *KernelBB, ValueMapTy *VRMap, - MBBVectorTy &PrologBBs); - void generateEpilog(SMSchedule &Schedule, unsigned LastStage, - MachineBasicBlock *KernelBB, ValueMapTy *VRMap, - MBBVectorTy &EpilogBBs, MBBVectorTy &PrologBBs); - void generateExistingPhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1, - MachineBasicBlock *BB2, MachineBasicBlock *KernelBB, - SMSchedule &Schedule, ValueMapTy *VRMap, - InstrMapTy &InstrMap, unsigned LastStageNum, - unsigned CurStageNum, bool IsLast); - void generatePhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1, - MachineBasicBlock *BB2, MachineBasicBlock *KernelBB, - SMSchedule &Schedule, ValueMapTy *VRMap, - InstrMapTy &InstrMap, unsigned LastStageNum, - unsigned CurStageNum, bool IsLast); - void removeDeadInstructions(MachineBasicBlock *KernelBB, - MBBVectorTy &EpilogBBs); - void splitLifetimes(MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs, - SMSchedule &Schedule); - void addBranches(MachineBasicBlock &PreheaderBB, MBBVectorTy &PrologBBs, - MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs, - SMSchedule &Schedule, ValueMapTy *VRMap); bool computeDelta(MachineInstr &MI, unsigned &Delta); - void updateMemOperands(MachineInstr &NewMI, MachineInstr &OldMI, - unsigned Num); - MachineInstr *cloneInstr(MachineInstr *OldMI, unsigned CurStageNum, - unsigned InstStageNum); - MachineInstr *cloneAndChangeInstr(MachineInstr *OldMI, unsigned CurStageNum, - unsigned InstStageNum, - SMSchedule &Schedule); - void updateInstruction(MachineInstr *NewMI, bool LastDef, - unsigned CurStageNum, unsigned InstrStageNum, - SMSchedule &Schedule, ValueMapTy *VRMap); MachineInstr *findDefInLoop(unsigned Reg); - unsigned getPrevMapVal(unsigned StageNum, unsigned PhiStage, unsigned LoopVal, - unsigned LoopStage, ValueMapTy *VRMap, - MachineBasicBlock *BB); - void rewritePhiValues(MachineBasicBlock *NewBB, unsigned StageNum, - SMSchedule &Schedule, ValueMapTy *VRMap, - InstrMapTy &InstrMap); - void rewriteScheduledInstr(MachineBasicBlock *BB, SMSchedule &Schedule, - InstrMapTy &InstrMap, unsigned CurStageNum, - unsigned PhiNum, MachineInstr *Phi, - unsigned OldReg, unsigned NewReg, - unsigned PrevReg = 0); bool canUseLastOffsetValue(MachineInstr *MI, unsigned &BasePos, unsigned &OffsetPos, unsigned &NewBase, int64_t &NewOffset); @@ -529,12 +484,6 @@ /// Map from instruction to execution cycle. std::map InstrToCycle; - /// Map for each register and the max difference between its uses and def. - /// The first element in the pair is the max difference in stages. The - /// second is true if the register defines a Phi value and loop value is - /// scheduled before the Phi. - std::map> RegToStageDiff; - /// Keep track of the first cycle value in the schedule. It starts /// as zero, but the algorithm allows negative values. int FirstCycle = 0; @@ -560,7 +509,6 @@ void reset() { ScheduledInstrs.clear(); InstrToCycle.clear(); - RegToStageDiff.clear(); FirstCycle = 0; LastCycle = 0; InitiationInterval = 0; @@ -620,28 +568,6 @@ return (LastCycle - FirstCycle) / InitiationInterval; } - /// Return the max. number of stages/iterations that can occur between a - /// register definition and its uses. - unsigned getStagesForReg(int Reg, unsigned CurStage) { - std::pair Stages = RegToStageDiff[Reg]; - if (CurStage > getMaxStageCount() && Stages.first == 0 && Stages.second) - return 1; - return Stages.first; - } - - /// The number of stages for a Phi is a little different than other - /// instructions. The minimum value computed in RegToStageDiff is 1 - /// because we assume the Phi is needed for at least 1 iteration. - /// This is not the case if the loop value is scheduled prior to the - /// Phi in the same stage. This function returns the number of stages - /// or iterations needed between the Phi definition and any uses. - unsigned getStagesForPhi(int Reg) { - std::pair Stages = RegToStageDiff[Reg]; - if (Stages.second) - return Stages.first; - return Stages.first - 1; - } - /// Return the instructions that are scheduled at the specified cycle. std::deque &getInstructions(int cycle) { return ScheduledInstrs[cycle]; Index: llvm/trunk/include/llvm/CodeGen/ModuloSchedule.h =================================================================== --- llvm/trunk/include/llvm/CodeGen/ModuloSchedule.h +++ llvm/trunk/include/llvm/CodeGen/ModuloSchedule.h @@ -0,0 +1,259 @@ +//===- ModuloSchedule.h - Software pipeline schedule expansion ------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Software pipelining (SWP) is an instruction scheduling technique for loops +// that overlaps loop iterations and exploits ILP via compiler transformations. +// +// There are multiple methods for analyzing a loop and creating a schedule. +// An example algorithm is Swing Modulo Scheduling (implemented by the +// MachinePipeliner). The details of how a schedule is arrived at are irrelevant +// for the task of actually rewriting a loop to adhere to the schedule, which +// is what this file does. +// +// A schedule is, for every instruction in a block, a Cycle and a Stage. Note +// that we only support single-block loops, so "block" and "loop" can be used +// interchangably. +// +// The Cycle of an instruction defines a partial order of the instructions in +// the remapped loop. Instructions within a cycle must not consume the output +// of any instruction in the same cycle. Cycle information is assumed to have +// been calculated such that the processor will execute instructions in +// lock-step (for example in a VLIW ISA). +// +// The Stage of an instruction defines the mapping between logical loop +// iterations and pipelined loop iterations. An example (unrolled) pipeline +// may look something like: +// +// I0[0] Execute instruction I0 of iteration 0 +// I1[0], I0[1] Execute I0 of iteration 1 and I1 of iteration 1 +// I1[1], I0[2] +// I1[2], I0[3] +// +// In the schedule for this unrolled sequence we would say that I0 was scheduled +// in stage 0 and I1 in stage 1: +// +// loop: +// [stage 0] x = I0 +// [stage 1] I1 x (from stage 0) +// +// And to actually generate valid code we must insert a phi: +// +// loop: +// x' = phi(x) +// x = I0 +// I1 x' +// +// This is a simple example; the rules for how to generate correct code given +// an arbitrary schedule containing loop-carried values are complex. +// +// Note that these examples only mention the steady-state kernel of the +// generated loop; prologs and epilogs must be generated also that prime and +// flush the pipeline. Doing so is nontrivial. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_LIB_CODEGEN_MODULOSCHEDULE_H +#define LLVM_LIB_CODEGEN_MODULOSCHEDULE_H + +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineLoopInfo.h" +#include "llvm/CodeGen/TargetSubtargetInfo.h" +#include + +namespace llvm { +class MachineBasicBlock; +class MachineInstr; +class LiveIntervals; + +/// Represents a schedule for a single-block loop. For every instruction we +/// maintain a Cycle and Stage. +class ModuloSchedule { +private: + /// The block containing the loop instructions. + MachineLoop *Loop; + + /// The instructions to be generated, in total order. Cycle provides a partial + /// order; the total order within cycles has been decided by the schedule + /// producer. + std::vector ScheduledInstrs; + + /// The cycle for each instruction. + DenseMap Cycle; + + /// The stage for each instruction. + DenseMap Stage; + + /// The number of stages in this schedule (Max(Stage) + 1). + int NumStages; + +public: + /// Create a new ModuloSchedule. + /// \arg ScheduledInstrs The new loop instructions, in total resequenced + /// order. + /// \arg Cycle Cycle index for all instructions in ScheduledInstrs. Cycle does + /// not need to start at zero. ScheduledInstrs must be partially ordered by + /// Cycle. + /// \arg Stage Stage index for all instructions in ScheduleInstrs. + ModuloSchedule(MachineFunction &MF, MachineLoop *Loop, + std::vector ScheduledInstrs, + DenseMap Cycle, + DenseMap Stage) + : Loop(Loop), ScheduledInstrs(ScheduledInstrs), Cycle(std::move(Cycle)), + Stage(std::move(Stage)) { + NumStages = 0; + for (auto &KV : this->Stage) + NumStages = std::max(NumStages, KV.second); + ++NumStages; + } + + /// Return the single-block loop being scheduled. + MachineLoop *getLoop() const { return Loop; } + + /// Return the number of stages contained in this schedule, which is the + /// largest stage index + 1. + int getNumStages() const { return NumStages; } + + /// Return the first cycle in the schedule, which is the cycle index of the + /// first instruction. + int getFirstCycle() { return Cycle[ScheduledInstrs.front()]; } + + /// Return the final cycle in the schedule, which is the cycle index of the + /// last instruction. + int getFinalCycle() { return Cycle[ScheduledInstrs.back()]; } + + /// Return the stage that MI is scheduled in, or -1. + int getStage(MachineInstr *MI) { + auto I = Stage.find(MI); + return I == Stage.end() ? -1 : I->second; + } + + /// Return the cycle that MI is scheduled at, or -1. + int getCycle(MachineInstr *MI) { + auto I = Cycle.find(MI); + return I == Cycle.end() ? -1 : I->second; + } + + /// Return the rescheduled instructions in order. + ArrayRef getInstructions() { return ScheduledInstrs; } +}; + +/// The ModuloScheduleExpander takes a ModuloSchedule and expands it in-place, +/// rewriting the old loop and inserting prologs and epilogs as required. +class ModuloScheduleExpander { +public: + using InstrChangesTy = DenseMap>; + +private: + using ValueMapTy = DenseMap; + using MBBVectorTy = SmallVectorImpl; + using InstrMapTy = DenseMap; + + ModuloSchedule &Schedule; + MachineFunction &MF; + const TargetSubtargetInfo &ST; + MachineRegisterInfo &MRI; + const TargetInstrInfo *TII; + LiveIntervals &LIS; + + MachineBasicBlock *BB; + MachineBasicBlock *Preheader; + + /// Map for each register and the max difference between its uses and def. + /// The first element in the pair is the max difference in stages. The + /// second is true if the register defines a Phi value and loop value is + /// scheduled before the Phi. + std::map> RegToStageDiff; + + /// Instructions to change when emitting the final schedule. + InstrChangesTy InstrChanges; + + void generatePipelinedLoop(); + void generateProlog(unsigned LastStage, MachineBasicBlock *KernelBB, + ValueMapTy *VRMap, MBBVectorTy &PrologBBs); + void generateEpilog(unsigned LastStage, MachineBasicBlock *KernelBB, + ValueMapTy *VRMap, MBBVectorTy &EpilogBBs, + MBBVectorTy &PrologBBs); + void generateExistingPhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1, + MachineBasicBlock *BB2, MachineBasicBlock *KernelBB, + ValueMapTy *VRMap, InstrMapTy &InstrMap, + unsigned LastStageNum, unsigned CurStageNum, + bool IsLast); + void generatePhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1, + MachineBasicBlock *BB2, MachineBasicBlock *KernelBB, + ValueMapTy *VRMap, InstrMapTy &InstrMap, + unsigned LastStageNum, unsigned CurStageNum, bool IsLast); + void removeDeadInstructions(MachineBasicBlock *KernelBB, + MBBVectorTy &EpilogBBs); + void splitLifetimes(MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs); + void addBranches(MachineBasicBlock &PreheaderBB, MBBVectorTy &PrologBBs, + MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs, + ValueMapTy *VRMap); + bool computeDelta(MachineInstr &MI, unsigned &Delta); + void updateMemOperands(MachineInstr &NewMI, MachineInstr &OldMI, + unsigned Num); + MachineInstr *cloneInstr(MachineInstr *OldMI, unsigned CurStageNum, + unsigned InstStageNum); + MachineInstr *cloneAndChangeInstr(MachineInstr *OldMI, unsigned CurStageNum, + unsigned InstStageNum); + void updateInstruction(MachineInstr *NewMI, bool LastDef, + unsigned CurStageNum, unsigned InstrStageNum, + ValueMapTy *VRMap); + MachineInstr *findDefInLoop(unsigned Reg); + unsigned getPrevMapVal(unsigned StageNum, unsigned PhiStage, unsigned LoopVal, + unsigned LoopStage, ValueMapTy *VRMap, + MachineBasicBlock *BB); + void rewritePhiValues(MachineBasicBlock *NewBB, unsigned StageNum, + ValueMapTy *VRMap, InstrMapTy &InstrMap); + void rewriteScheduledInstr(MachineBasicBlock *BB, InstrMapTy &InstrMap, + unsigned CurStageNum, unsigned PhiNum, + MachineInstr *Phi, unsigned OldReg, + unsigned NewReg, unsigned PrevReg = 0); + bool isLoopCarried(MachineInstr &Phi); + + /// Return the max. number of stages/iterations that can occur between a + /// register definition and its uses. + unsigned getStagesForReg(int Reg, unsigned CurStage) { + std::pair Stages = RegToStageDiff[Reg]; + if ((int)CurStage > Schedule.getNumStages() - 1 && Stages.first == 0 && + Stages.second) + return 1; + return Stages.first; + } + + /// The number of stages for a Phi is a little different than other + /// instructions. The minimum value computed in RegToStageDiff is 1 + /// because we assume the Phi is needed for at least 1 iteration. + /// This is not the case if the loop value is scheduled prior to the + /// Phi in the same stage. This function returns the number of stages + /// or iterations needed between the Phi definition and any uses. + unsigned getStagesForPhi(int Reg) { + std::pair Stages = RegToStageDiff[Reg]; + if (Stages.second) + return Stages.first; + return Stages.first - 1; + } + +public: + /// Create a new ModuloScheduleExpander. + /// \arg InstrChanges Modifications to make to instructions with memory + /// operands. + /// FIXME: InstrChanges is opaque and is an implementation detail of an + /// optimization in MachinePipeliner that crosses abstraction boundaries. + ModuloScheduleExpander(MachineFunction &MF, ModuloSchedule &S, + LiveIntervals &LIS, InstrChangesTy InstrChanges) + : Schedule(S), MF(MF), ST(MF.getSubtarget()), MRI(MF.getRegInfo()), + TII(ST.getInstrInfo()), LIS(LIS), + InstrChanges(std::move(InstrChanges)) {} + + /// Performs the actual expansion. + void expand(); +}; + +} // end namespace llvm + +#endif // LLVM_LIB_CODEGEN_MODULOSCHEDULE_H Index: llvm/trunk/lib/CodeGen/CMakeLists.txt =================================================================== --- llvm/trunk/lib/CodeGen/CMakeLists.txt +++ llvm/trunk/lib/CodeGen/CMakeLists.txt @@ -94,6 +94,7 @@ MachineSSAUpdater.cpp MachineTraceMetrics.cpp MachineVerifier.cpp + ModuloSchedule.cpp PatchableFunction.cpp MIRPrinter.cpp MIRPrintingPass.cpp Index: llvm/trunk/lib/CodeGen/MachinePipeliner.cpp =================================================================== --- llvm/trunk/lib/CodeGen/MachinePipeliner.cpp +++ llvm/trunk/lib/CodeGen/MachinePipeliner.cpp @@ -56,6 +56,7 @@ #include "llvm/CodeGen/MachineOperand.h" #include "llvm/CodeGen/MachinePipeliner.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/ModuloSchedule.h" #include "llvm/CodeGen/RegisterPressure.h" #include "llvm/CodeGen/ScheduleDAG.h" #include "llvm/CodeGen/ScheduleDAGMutation.h" @@ -515,14 +516,35 @@ return; } - generatePipelinedLoop(Schedule); + // Generate the schedule as a ModuloSchedule. + DenseMap Cycles, Stages; + std::vector OrderedInsts; + for (int Cycle = Schedule.getFirstCycle(); Cycle <= Schedule.getFinalCycle(); + ++Cycle) { + for (SUnit *SU : Schedule.getInstructions(Cycle)) { + OrderedInsts.push_back(SU->getInstr()); + Cycles[SU->getInstr()] = Cycle; + Stages[SU->getInstr()] = Schedule.stageScheduled(SU); + } + } + DenseMap> NewInstrChanges; + for (auto &KV : NewMIs) { + Cycles[KV.first] = Cycles[KV.second]; + Stages[KV.first] = Stages[KV.second]; + NewInstrChanges[KV.first] = InstrChanges[getSUnit(KV.first)]; + } + + ModuloSchedule MS(MF, &Loop, std::move(OrderedInsts), std::move(Cycles), + std::move(Stages)); + ModuloScheduleExpander MSE(MF, MS, LIS, std::move(NewInstrChanges)); + MSE.expand(); ++NumPipelined; } /// Clean up after the software pipeliner runs. void SwingSchedulerDAG::finishBlock() { - for (MachineInstr *I : NewMIs) - MF.DeleteMachineInstr(I); + for (auto &KV : NewMIs) + MF.DeleteMachineInstr(KV.second); NewMIs.clear(); // Call the superclass. @@ -546,14 +568,6 @@ assert(InitVal != 0 && LoopVal != 0 && "Unexpected Phi structure."); } -/// Return the Phi register value that comes from the incoming block. -static unsigned getInitPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB) { - for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2) - if (Phi.getOperand(i + 1).getMBB() != LoopBB) - return Phi.getOperand(i).getReg(); - return 0; -} - /// Return the Phi register value that comes the loop block. static unsigned getLoopPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB) { for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2) @@ -2012,828 +2026,6 @@ return scheduleFound && Schedule.getMaxStageCount() > 0; } -/// Given a schedule for the loop, generate a new version of the loop, -/// and replace the old version. This function generates a prolog -/// that contains the initial iterations in the pipeline, and kernel -/// loop, and the epilogue that contains the code for the final -/// iterations. -void SwingSchedulerDAG::generatePipelinedLoop(SMSchedule &Schedule) { - // Create a new basic block for the kernel and add it to the CFG. - MachineBasicBlock *KernelBB = MF.CreateMachineBasicBlock(BB->getBasicBlock()); - - unsigned MaxStageCount = Schedule.getMaxStageCount(); - - // Remember the registers that are used in different stages. The index is - // the iteration, or stage, that the instruction is scheduled in. This is - // a map between register names in the original block and the names created - // in each stage of the pipelined loop. - ValueMapTy *VRMap = new ValueMapTy[(MaxStageCount + 1) * 2]; - InstrMapTy InstrMap; - - SmallVector PrologBBs; - - MachineBasicBlock *PreheaderBB = MLI->getLoopFor(BB)->getLoopPreheader(); - assert(PreheaderBB != nullptr && - "Need to add code to handle loops w/o preheader"); - // Generate the prolog instructions that set up the pipeline. - generateProlog(Schedule, MaxStageCount, KernelBB, VRMap, PrologBBs); - MF.insert(BB->getIterator(), KernelBB); - - // Rearrange the instructions to generate the new, pipelined loop, - // and update register names as needed. - for (int Cycle = Schedule.getFirstCycle(), - LastCycle = Schedule.getFinalCycle(); - Cycle <= LastCycle; ++Cycle) { - std::deque &CycleInstrs = Schedule.getInstructions(Cycle); - // This inner loop schedules each instruction in the cycle. - for (SUnit *CI : CycleInstrs) { - if (CI->getInstr()->isPHI()) - continue; - unsigned StageNum = Schedule.stageScheduled(getSUnit(CI->getInstr())); - MachineInstr *NewMI = cloneInstr(CI->getInstr(), MaxStageCount, StageNum); - updateInstruction(NewMI, false, MaxStageCount, StageNum, Schedule, VRMap); - KernelBB->push_back(NewMI); - InstrMap[NewMI] = CI->getInstr(); - } - } - - // Copy any terminator instructions to the new kernel, and update - // names as needed. - for (MachineBasicBlock::iterator I = BB->getFirstTerminator(), - E = BB->instr_end(); - I != E; ++I) { - MachineInstr *NewMI = MF.CloneMachineInstr(&*I); - updateInstruction(NewMI, false, MaxStageCount, 0, Schedule, VRMap); - KernelBB->push_back(NewMI); - InstrMap[NewMI] = &*I; - } - - KernelBB->transferSuccessors(BB); - KernelBB->replaceSuccessor(BB, KernelBB); - - generateExistingPhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, Schedule, - VRMap, InstrMap, MaxStageCount, MaxStageCount, false); - generatePhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, Schedule, VRMap, - InstrMap, MaxStageCount, MaxStageCount, false); - - LLVM_DEBUG(dbgs() << "New block\n"; KernelBB->dump();); - - SmallVector EpilogBBs; - // Generate the epilog instructions to complete the pipeline. - generateEpilog(Schedule, MaxStageCount, KernelBB, VRMap, EpilogBBs, - PrologBBs); - - // We need this step because the register allocation doesn't handle some - // situations well, so we insert copies to help out. - splitLifetimes(KernelBB, EpilogBBs, Schedule); - - // Remove dead instructions due to loop induction variables. - removeDeadInstructions(KernelBB, EpilogBBs); - - // Add branches between prolog and epilog blocks. - addBranches(*PreheaderBB, PrologBBs, KernelBB, EpilogBBs, Schedule, VRMap); - - // Remove the original loop since it's no longer referenced. - for (auto &I : *BB) - LIS.RemoveMachineInstrFromMaps(I); - BB->clear(); - BB->eraseFromParent(); - - delete[] VRMap; -} - -/// Generate the pipeline prolog code. -void SwingSchedulerDAG::generateProlog(SMSchedule &Schedule, unsigned LastStage, - MachineBasicBlock *KernelBB, - ValueMapTy *VRMap, - MBBVectorTy &PrologBBs) { - MachineBasicBlock *PreheaderBB = MLI->getLoopFor(BB)->getLoopPreheader(); - assert(PreheaderBB != nullptr && - "Need to add code to handle loops w/o preheader"); - MachineBasicBlock *PredBB = PreheaderBB; - InstrMapTy InstrMap; - - // Generate a basic block for each stage, not including the last stage, - // which will be generated in the kernel. Each basic block may contain - // instructions from multiple stages/iterations. - for (unsigned i = 0; i < LastStage; ++i) { - // Create and insert the prolog basic block prior to the original loop - // basic block. The original loop is removed later. - MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(BB->getBasicBlock()); - PrologBBs.push_back(NewBB); - MF.insert(BB->getIterator(), NewBB); - NewBB->transferSuccessors(PredBB); - PredBB->addSuccessor(NewBB); - PredBB = NewBB; - - // Generate instructions for each appropriate stage. Process instructions - // in original program order. - for (int StageNum = i; StageNum >= 0; --StageNum) { - for (MachineBasicBlock::iterator BBI = BB->instr_begin(), - BBE = BB->getFirstTerminator(); - BBI != BBE; ++BBI) { - if (Schedule.isScheduledAtStage(getSUnit(&*BBI), (unsigned)StageNum)) { - if (BBI->isPHI()) - continue; - MachineInstr *NewMI = - cloneAndChangeInstr(&*BBI, i, (unsigned)StageNum, Schedule); - updateInstruction(NewMI, false, i, (unsigned)StageNum, Schedule, - VRMap); - NewBB->push_back(NewMI); - InstrMap[NewMI] = &*BBI; - } - } - } - rewritePhiValues(NewBB, i, Schedule, VRMap, InstrMap); - LLVM_DEBUG({ - dbgs() << "prolog:\n"; - NewBB->dump(); - }); - } - - PredBB->replaceSuccessor(BB, KernelBB); - - // Check if we need to remove the branch from the preheader to the original - // loop, and replace it with a branch to the new loop. - unsigned numBranches = TII->removeBranch(*PreheaderBB); - if (numBranches) { - SmallVector Cond; - TII->insertBranch(*PreheaderBB, PrologBBs[0], nullptr, Cond, DebugLoc()); - } -} - -/// Generate the pipeline epilog code. The epilog code finishes the iterations -/// that were started in either the prolog or the kernel. We create a basic -/// block for each stage that needs to complete. -void SwingSchedulerDAG::generateEpilog(SMSchedule &Schedule, unsigned LastStage, - MachineBasicBlock *KernelBB, - ValueMapTy *VRMap, - MBBVectorTy &EpilogBBs, - MBBVectorTy &PrologBBs) { - // We need to change the branch from the kernel to the first epilog block, so - // this call to analyze branch uses the kernel rather than the original BB. - MachineBasicBlock *TBB = nullptr, *FBB = nullptr; - SmallVector Cond; - bool checkBranch = TII->analyzeBranch(*KernelBB, TBB, FBB, Cond); - assert(!checkBranch && "generateEpilog must be able to analyze the branch"); - if (checkBranch) - return; - - MachineBasicBlock::succ_iterator LoopExitI = KernelBB->succ_begin(); - if (*LoopExitI == KernelBB) - ++LoopExitI; - assert(LoopExitI != KernelBB->succ_end() && "Expecting a successor"); - MachineBasicBlock *LoopExitBB = *LoopExitI; - - MachineBasicBlock *PredBB = KernelBB; - MachineBasicBlock *EpilogStart = LoopExitBB; - InstrMapTy InstrMap; - - // Generate a basic block for each stage, not including the last stage, - // which was generated for the kernel. Each basic block may contain - // instructions from multiple stages/iterations. - int EpilogStage = LastStage + 1; - for (unsigned i = LastStage; i >= 1; --i, ++EpilogStage) { - MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(); - EpilogBBs.push_back(NewBB); - MF.insert(BB->getIterator(), NewBB); - - PredBB->replaceSuccessor(LoopExitBB, NewBB); - NewBB->addSuccessor(LoopExitBB); - - if (EpilogStart == LoopExitBB) - EpilogStart = NewBB; - - // Add instructions to the epilog depending on the current block. - // Process instructions in original program order. - for (unsigned StageNum = i; StageNum <= LastStage; ++StageNum) { - for (auto &BBI : *BB) { - if (BBI.isPHI()) - continue; - MachineInstr *In = &BBI; - if (Schedule.isScheduledAtStage(getSUnit(In), StageNum)) { - // Instructions with memoperands in the epilog are updated with - // conservative values. - MachineInstr *NewMI = cloneInstr(In, UINT_MAX, 0); - updateInstruction(NewMI, i == 1, EpilogStage, 0, Schedule, VRMap); - NewBB->push_back(NewMI); - InstrMap[NewMI] = In; - } - } - } - generateExistingPhis(NewBB, PrologBBs[i - 1], PredBB, KernelBB, Schedule, - VRMap, InstrMap, LastStage, EpilogStage, i == 1); - generatePhis(NewBB, PrologBBs[i - 1], PredBB, KernelBB, Schedule, VRMap, - InstrMap, LastStage, EpilogStage, i == 1); - PredBB = NewBB; - - LLVM_DEBUG({ - dbgs() << "epilog:\n"; - NewBB->dump(); - }); - } - - // Fix any Phi nodes in the loop exit block. - LoopExitBB->replacePhiUsesWith(BB, PredBB); - - // Create a branch to the new epilog from the kernel. - // Remove the original branch and add a new branch to the epilog. - TII->removeBranch(*KernelBB); - TII->insertBranch(*KernelBB, KernelBB, EpilogStart, Cond, DebugLoc()); - // Add a branch to the loop exit. - if (EpilogBBs.size() > 0) { - MachineBasicBlock *LastEpilogBB = EpilogBBs.back(); - SmallVector Cond1; - TII->insertBranch(*LastEpilogBB, LoopExitBB, nullptr, Cond1, DebugLoc()); - } -} - -/// Replace all uses of FromReg that appear outside the specified -/// basic block with ToReg. -static void replaceRegUsesAfterLoop(unsigned FromReg, unsigned ToReg, - MachineBasicBlock *MBB, - MachineRegisterInfo &MRI, - LiveIntervals &LIS) { - for (MachineRegisterInfo::use_iterator I = MRI.use_begin(FromReg), - E = MRI.use_end(); - I != E;) { - MachineOperand &O = *I; - ++I; - if (O.getParent()->getParent() != MBB) - O.setReg(ToReg); - } - if (!LIS.hasInterval(ToReg)) - LIS.createEmptyInterval(ToReg); -} - -/// Return true if the register has a use that occurs outside the -/// specified loop. -static bool hasUseAfterLoop(unsigned Reg, MachineBasicBlock *BB, - MachineRegisterInfo &MRI) { - for (MachineRegisterInfo::use_iterator I = MRI.use_begin(Reg), - E = MRI.use_end(); - I != E; ++I) - if (I->getParent()->getParent() != BB) - return true; - return false; -} - -/// Generate Phis for the specific block in the generated pipelined code. -/// This function looks at the Phis from the original code to guide the -/// creation of new Phis. -void SwingSchedulerDAG::generateExistingPhis( - MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2, - MachineBasicBlock *KernelBB, SMSchedule &Schedule, ValueMapTy *VRMap, - InstrMapTy &InstrMap, unsigned LastStageNum, unsigned CurStageNum, - bool IsLast) { - // Compute the stage number for the initial value of the Phi, which - // comes from the prolog. The prolog to use depends on to which kernel/ - // epilog that we're adding the Phi. - unsigned PrologStage = 0; - unsigned PrevStage = 0; - bool InKernel = (LastStageNum == CurStageNum); - if (InKernel) { - PrologStage = LastStageNum - 1; - PrevStage = CurStageNum; - } else { - PrologStage = LastStageNum - (CurStageNum - LastStageNum); - PrevStage = LastStageNum + (CurStageNum - LastStageNum) - 1; - } - - for (MachineBasicBlock::iterator BBI = BB->instr_begin(), - BBE = BB->getFirstNonPHI(); - BBI != BBE; ++BBI) { - Register Def = BBI->getOperand(0).getReg(); - - unsigned InitVal = 0; - unsigned LoopVal = 0; - getPhiRegs(*BBI, BB, InitVal, LoopVal); - - unsigned PhiOp1 = 0; - // The Phi value from the loop body typically is defined in the loop, but - // not always. So, we need to check if the value is defined in the loop. - unsigned PhiOp2 = LoopVal; - if (VRMap[LastStageNum].count(LoopVal)) - PhiOp2 = VRMap[LastStageNum][LoopVal]; - - int StageScheduled = Schedule.stageScheduled(getSUnit(&*BBI)); - int LoopValStage = - Schedule.stageScheduled(getSUnit(MRI.getVRegDef(LoopVal))); - unsigned NumStages = Schedule.getStagesForReg(Def, CurStageNum); - if (NumStages == 0) { - // We don't need to generate a Phi anymore, but we need to rename any uses - // of the Phi value. - unsigned NewReg = VRMap[PrevStage][LoopVal]; - rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, 0, &*BBI, - Def, InitVal, NewReg); - if (VRMap[CurStageNum].count(LoopVal)) - VRMap[CurStageNum][Def] = VRMap[CurStageNum][LoopVal]; - } - // Adjust the number of Phis needed depending on the number of prologs left, - // and the distance from where the Phi is first scheduled. The number of - // Phis cannot exceed the number of prolog stages. Each stage can - // potentially define two values. - unsigned MaxPhis = PrologStage + 2; - if (!InKernel && (int)PrologStage <= LoopValStage) - MaxPhis = std::max((int)MaxPhis - (int)LoopValStage, 1); - unsigned NumPhis = std::min(NumStages, MaxPhis); - - unsigned NewReg = 0; - unsigned AccessStage = (LoopValStage != -1) ? LoopValStage : StageScheduled; - // In the epilog, we may need to look back one stage to get the correct - // Phi name because the epilog and prolog blocks execute the same stage. - // The correct name is from the previous block only when the Phi has - // been completely scheduled prior to the epilog, and Phi value is not - // needed in multiple stages. - int StageDiff = 0; - if (!InKernel && StageScheduled >= LoopValStage && AccessStage == 0 && - NumPhis == 1) - StageDiff = 1; - // Adjust the computations below when the phi and the loop definition - // are scheduled in different stages. - if (InKernel && LoopValStage != -1 && StageScheduled > LoopValStage) - StageDiff = StageScheduled - LoopValStage; - for (unsigned np = 0; np < NumPhis; ++np) { - // If the Phi hasn't been scheduled, then use the initial Phi operand - // value. Otherwise, use the scheduled version of the instruction. This - // is a little complicated when a Phi references another Phi. - if (np > PrologStage || StageScheduled >= (int)LastStageNum) - PhiOp1 = InitVal; - // Check if the Phi has already been scheduled in a prolog stage. - else if (PrologStage >= AccessStage + StageDiff + np && - VRMap[PrologStage - StageDiff - np].count(LoopVal) != 0) - PhiOp1 = VRMap[PrologStage - StageDiff - np][LoopVal]; - // Check if the Phi has already been scheduled, but the loop instruction - // is either another Phi, or doesn't occur in the loop. - else if (PrologStage >= AccessStage + StageDiff + np) { - // If the Phi references another Phi, we need to examine the other - // Phi to get the correct value. - PhiOp1 = LoopVal; - MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1); - int Indirects = 1; - while (InstOp1 && InstOp1->isPHI() && InstOp1->getParent() == BB) { - int PhiStage = Schedule.stageScheduled(getSUnit(InstOp1)); - if ((int)(PrologStage - StageDiff - np) < PhiStage + Indirects) - PhiOp1 = getInitPhiReg(*InstOp1, BB); - else - PhiOp1 = getLoopPhiReg(*InstOp1, BB); - InstOp1 = MRI.getVRegDef(PhiOp1); - int PhiOpStage = Schedule.stageScheduled(getSUnit(InstOp1)); - int StageAdj = (PhiOpStage != -1 ? PhiStage - PhiOpStage : 0); - if (PhiOpStage != -1 && PrologStage - StageAdj >= Indirects + np && - VRMap[PrologStage - StageAdj - Indirects - np].count(PhiOp1)) { - PhiOp1 = VRMap[PrologStage - StageAdj - Indirects - np][PhiOp1]; - break; - } - ++Indirects; - } - } else - PhiOp1 = InitVal; - // If this references a generated Phi in the kernel, get the Phi operand - // from the incoming block. - if (MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1)) - if (InstOp1->isPHI() && InstOp1->getParent() == KernelBB) - PhiOp1 = getInitPhiReg(*InstOp1, KernelBB); - - MachineInstr *PhiInst = MRI.getVRegDef(LoopVal); - bool LoopDefIsPhi = PhiInst && PhiInst->isPHI(); - // In the epilog, a map lookup is needed to get the value from the kernel, - // or previous epilog block. How is does this depends on if the - // instruction is scheduled in the previous block. - if (!InKernel) { - int StageDiffAdj = 0; - if (LoopValStage != -1 && StageScheduled > LoopValStage) - StageDiffAdj = StageScheduled - LoopValStage; - // Use the loop value defined in the kernel, unless the kernel - // contains the last definition of the Phi. - if (np == 0 && PrevStage == LastStageNum && - (StageScheduled != 0 || LoopValStage != 0) && - VRMap[PrevStage - StageDiffAdj].count(LoopVal)) - PhiOp2 = VRMap[PrevStage - StageDiffAdj][LoopVal]; - // Use the value defined by the Phi. We add one because we switch - // from looking at the loop value to the Phi definition. - else if (np > 0 && PrevStage == LastStageNum && - VRMap[PrevStage - np + 1].count(Def)) - PhiOp2 = VRMap[PrevStage - np + 1][Def]; - // Use the loop value defined in the kernel. - else if (static_cast(LoopValStage) > PrologStage + 1 && - VRMap[PrevStage - StageDiffAdj - np].count(LoopVal)) - PhiOp2 = VRMap[PrevStage - StageDiffAdj - np][LoopVal]; - // Use the value defined by the Phi, unless we're generating the first - // epilog and the Phi refers to a Phi in a different stage. - else if (VRMap[PrevStage - np].count(Def) && - (!LoopDefIsPhi || (PrevStage != LastStageNum) || (LoopValStage == StageScheduled))) - PhiOp2 = VRMap[PrevStage - np][Def]; - } - - // Check if we can reuse an existing Phi. This occurs when a Phi - // references another Phi, and the other Phi is scheduled in an - // earlier stage. We can try to reuse an existing Phi up until the last - // stage of the current Phi. - if (LoopDefIsPhi) { - if (static_cast(PrologStage - np) >= StageScheduled) { - int LVNumStages = Schedule.getStagesForPhi(LoopVal); - int StageDiff = (StageScheduled - LoopValStage); - LVNumStages -= StageDiff; - // Make sure the loop value Phi has been processed already. - if (LVNumStages > (int)np && VRMap[CurStageNum].count(LoopVal)) { - NewReg = PhiOp2; - unsigned ReuseStage = CurStageNum; - if (Schedule.isLoopCarried(this, *PhiInst)) - ReuseStage -= LVNumStages; - // Check if the Phi to reuse has been generated yet. If not, then - // there is nothing to reuse. - if (VRMap[ReuseStage - np].count(LoopVal)) { - NewReg = VRMap[ReuseStage - np][LoopVal]; - - rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, np, - &*BBI, Def, NewReg); - // Update the map with the new Phi name. - VRMap[CurStageNum - np][Def] = NewReg; - PhiOp2 = NewReg; - if (VRMap[LastStageNum - np - 1].count(LoopVal)) - PhiOp2 = VRMap[LastStageNum - np - 1][LoopVal]; - - if (IsLast && np == NumPhis - 1) - replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS); - continue; - } - } - } - if (InKernel && StageDiff > 0 && - VRMap[CurStageNum - StageDiff - np].count(LoopVal)) - PhiOp2 = VRMap[CurStageNum - StageDiff - np][LoopVal]; - } - - const TargetRegisterClass *RC = MRI.getRegClass(Def); - NewReg = MRI.createVirtualRegister(RC); - - MachineInstrBuilder NewPhi = - BuildMI(*NewBB, NewBB->getFirstNonPHI(), DebugLoc(), - TII->get(TargetOpcode::PHI), NewReg); - NewPhi.addReg(PhiOp1).addMBB(BB1); - NewPhi.addReg(PhiOp2).addMBB(BB2); - if (np == 0) - InstrMap[NewPhi] = &*BBI; - - // We define the Phis after creating the new pipelined code, so - // we need to rename the Phi values in scheduled instructions. - - unsigned PrevReg = 0; - if (InKernel && VRMap[PrevStage - np].count(LoopVal)) - PrevReg = VRMap[PrevStage - np][LoopVal]; - rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, np, &*BBI, - Def, NewReg, PrevReg); - // If the Phi has been scheduled, use the new name for rewriting. - if (VRMap[CurStageNum - np].count(Def)) { - unsigned R = VRMap[CurStageNum - np][Def]; - rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, np, &*BBI, - R, NewReg); - } - - // Check if we need to rename any uses that occurs after the loop. The - // register to replace depends on whether the Phi is scheduled in the - // epilog. - if (IsLast && np == NumPhis - 1) - replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS); - - // In the kernel, a dependent Phi uses the value from this Phi. - if (InKernel) - PhiOp2 = NewReg; - - // Update the map with the new Phi name. - VRMap[CurStageNum - np][Def] = NewReg; - } - - while (NumPhis++ < NumStages) { - rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, NumPhis, - &*BBI, Def, NewReg, 0); - } - - // Check if we need to rename a Phi that has been eliminated due to - // scheduling. - if (NumStages == 0 && IsLast && VRMap[CurStageNum].count(LoopVal)) - replaceRegUsesAfterLoop(Def, VRMap[CurStageNum][LoopVal], BB, MRI, LIS); - } -} - -/// Generate Phis for the specified block in the generated pipelined code. -/// These are new Phis needed because the definition is scheduled after the -/// use in the pipelined sequence. -void SwingSchedulerDAG::generatePhis( - MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2, - MachineBasicBlock *KernelBB, SMSchedule &Schedule, ValueMapTy *VRMap, - InstrMapTy &InstrMap, unsigned LastStageNum, unsigned CurStageNum, - bool IsLast) { - // Compute the stage number that contains the initial Phi value, and - // the Phi from the previous stage. - unsigned PrologStage = 0; - unsigned PrevStage = 0; - unsigned StageDiff = CurStageNum - LastStageNum; - bool InKernel = (StageDiff == 0); - if (InKernel) { - PrologStage = LastStageNum - 1; - PrevStage = CurStageNum; - } else { - PrologStage = LastStageNum - StageDiff; - PrevStage = LastStageNum + StageDiff - 1; - } - - for (MachineBasicBlock::iterator BBI = BB->getFirstNonPHI(), - BBE = BB->instr_end(); - BBI != BBE; ++BBI) { - for (unsigned i = 0, e = BBI->getNumOperands(); i != e; ++i) { - MachineOperand &MO = BBI->getOperand(i); - if (!MO.isReg() || !MO.isDef() || - !Register::isVirtualRegister(MO.getReg())) - continue; - - int StageScheduled = Schedule.stageScheduled(getSUnit(&*BBI)); - assert(StageScheduled != -1 && "Expecting scheduled instruction."); - Register Def = MO.getReg(); - unsigned NumPhis = Schedule.getStagesForReg(Def, CurStageNum); - // An instruction scheduled in stage 0 and is used after the loop - // requires a phi in the epilog for the last definition from either - // the kernel or prolog. - if (!InKernel && NumPhis == 0 && StageScheduled == 0 && - hasUseAfterLoop(Def, BB, MRI)) - NumPhis = 1; - if (!InKernel && (unsigned)StageScheduled > PrologStage) - continue; - - unsigned PhiOp2 = VRMap[PrevStage][Def]; - if (MachineInstr *InstOp2 = MRI.getVRegDef(PhiOp2)) - if (InstOp2->isPHI() && InstOp2->getParent() == NewBB) - PhiOp2 = getLoopPhiReg(*InstOp2, BB2); - // The number of Phis can't exceed the number of prolog stages. The - // prolog stage number is zero based. - if (NumPhis > PrologStage + 1 - StageScheduled) - NumPhis = PrologStage + 1 - StageScheduled; - for (unsigned np = 0; np < NumPhis; ++np) { - unsigned PhiOp1 = VRMap[PrologStage][Def]; - if (np <= PrologStage) - PhiOp1 = VRMap[PrologStage - np][Def]; - if (MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1)) { - if (InstOp1->isPHI() && InstOp1->getParent() == KernelBB) - PhiOp1 = getInitPhiReg(*InstOp1, KernelBB); - if (InstOp1->isPHI() && InstOp1->getParent() == NewBB) - PhiOp1 = getInitPhiReg(*InstOp1, NewBB); - } - if (!InKernel) - PhiOp2 = VRMap[PrevStage - np][Def]; - - const TargetRegisterClass *RC = MRI.getRegClass(Def); - Register NewReg = MRI.createVirtualRegister(RC); - - MachineInstrBuilder NewPhi = - BuildMI(*NewBB, NewBB->getFirstNonPHI(), DebugLoc(), - TII->get(TargetOpcode::PHI), NewReg); - NewPhi.addReg(PhiOp1).addMBB(BB1); - NewPhi.addReg(PhiOp2).addMBB(BB2); - if (np == 0) - InstrMap[NewPhi] = &*BBI; - - // Rewrite uses and update the map. The actions depend upon whether - // we generating code for the kernel or epilog blocks. - if (InKernel) { - rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, np, - &*BBI, PhiOp1, NewReg); - rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, np, - &*BBI, PhiOp2, NewReg); - - PhiOp2 = NewReg; - VRMap[PrevStage - np - 1][Def] = NewReg; - } else { - VRMap[CurStageNum - np][Def] = NewReg; - if (np == NumPhis - 1) - rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, np, - &*BBI, Def, NewReg); - } - if (IsLast && np == NumPhis - 1) - replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS); - } - } - } -} - -/// Remove instructions that generate values with no uses. -/// Typically, these are induction variable operations that generate values -/// used in the loop itself. A dead instruction has a definition with -/// no uses, or uses that occur in the original loop only. -void SwingSchedulerDAG::removeDeadInstructions(MachineBasicBlock *KernelBB, - MBBVectorTy &EpilogBBs) { - // For each epilog block, check that the value defined by each instruction - // is used. If not, delete it. - for (MBBVectorTy::reverse_iterator MBB = EpilogBBs.rbegin(), - MBE = EpilogBBs.rend(); - MBB != MBE; ++MBB) - for (MachineBasicBlock::reverse_instr_iterator MI = (*MBB)->instr_rbegin(), - ME = (*MBB)->instr_rend(); - MI != ME;) { - // From DeadMachineInstructionElem. Don't delete inline assembly. - if (MI->isInlineAsm()) { - ++MI; - continue; - } - bool SawStore = false; - // Check if it's safe to remove the instruction due to side effects. - // We can, and want to, remove Phis here. - if (!MI->isSafeToMove(nullptr, SawStore) && !MI->isPHI()) { - ++MI; - continue; - } - bool used = true; - for (MachineInstr::mop_iterator MOI = MI->operands_begin(), - MOE = MI->operands_end(); - MOI != MOE; ++MOI) { - if (!MOI->isReg() || !MOI->isDef()) - continue; - Register reg = MOI->getReg(); - // Assume physical registers are used, unless they are marked dead. - if (Register::isPhysicalRegister(reg)) { - used = !MOI->isDead(); - if (used) - break; - continue; - } - unsigned realUses = 0; - for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(reg), - EI = MRI.use_end(); - UI != EI; ++UI) { - // Check if there are any uses that occur only in the original - // loop. If so, that's not a real use. - if (UI->getParent()->getParent() != BB) { - realUses++; - used = true; - break; - } - } - if (realUses > 0) - break; - used = false; - } - if (!used) { - LIS.RemoveMachineInstrFromMaps(*MI); - MI++->eraseFromParent(); - continue; - } - ++MI; - } - // In the kernel block, check if we can remove a Phi that generates a value - // used in an instruction removed in the epilog block. - for (MachineBasicBlock::iterator BBI = KernelBB->instr_begin(), - BBE = KernelBB->getFirstNonPHI(); - BBI != BBE;) { - MachineInstr *MI = &*BBI; - ++BBI; - Register reg = MI->getOperand(0).getReg(); - if (MRI.use_begin(reg) == MRI.use_end()) { - LIS.RemoveMachineInstrFromMaps(*MI); - MI->eraseFromParent(); - } - } -} - -/// For loop carried definitions, we split the lifetime of a virtual register -/// that has uses past the definition in the next iteration. A copy with a new -/// virtual register is inserted before the definition, which helps with -/// generating a better register assignment. -/// -/// v1 = phi(a, v2) v1 = phi(a, v2) -/// v2 = phi(b, v3) v2 = phi(b, v3) -/// v3 = .. v4 = copy v1 -/// .. = V1 v3 = .. -/// .. = v4 -void SwingSchedulerDAG::splitLifetimes(MachineBasicBlock *KernelBB, - MBBVectorTy &EpilogBBs, - SMSchedule &Schedule) { - const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); - for (auto &PHI : KernelBB->phis()) { - Register Def = PHI.getOperand(0).getReg(); - // Check for any Phi definition that used as an operand of another Phi - // in the same block. - for (MachineRegisterInfo::use_instr_iterator I = MRI.use_instr_begin(Def), - E = MRI.use_instr_end(); - I != E; ++I) { - if (I->isPHI() && I->getParent() == KernelBB) { - // Get the loop carried definition. - unsigned LCDef = getLoopPhiReg(PHI, KernelBB); - if (!LCDef) - continue; - MachineInstr *MI = MRI.getVRegDef(LCDef); - if (!MI || MI->getParent() != KernelBB || MI->isPHI()) - continue; - // Search through the rest of the block looking for uses of the Phi - // definition. If one occurs, then split the lifetime. - unsigned SplitReg = 0; - for (auto &BBJ : make_range(MachineBasicBlock::instr_iterator(MI), - KernelBB->instr_end())) - if (BBJ.readsRegister(Def)) { - // We split the lifetime when we find the first use. - if (SplitReg == 0) { - SplitReg = MRI.createVirtualRegister(MRI.getRegClass(Def)); - BuildMI(*KernelBB, MI, MI->getDebugLoc(), - TII->get(TargetOpcode::COPY), SplitReg) - .addReg(Def); - } - BBJ.substituteRegister(Def, SplitReg, 0, *TRI); - } - if (!SplitReg) - continue; - // Search through each of the epilog blocks for any uses to be renamed. - for (auto &Epilog : EpilogBBs) - for (auto &I : *Epilog) - if (I.readsRegister(Def)) - I.substituteRegister(Def, SplitReg, 0, *TRI); - break; - } - } - } -} - -/// Remove the incoming block from the Phis in a basic block. -static void removePhis(MachineBasicBlock *BB, MachineBasicBlock *Incoming) { - for (MachineInstr &MI : *BB) { - if (!MI.isPHI()) - break; - for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) - if (MI.getOperand(i + 1).getMBB() == Incoming) { - MI.RemoveOperand(i + 1); - MI.RemoveOperand(i); - break; - } - } -} - -/// Create branches from each prolog basic block to the appropriate epilog -/// block. These edges are needed if the loop ends before reaching the -/// kernel. -void SwingSchedulerDAG::addBranches(MachineBasicBlock &PreheaderBB, - MBBVectorTy &PrologBBs, - MachineBasicBlock *KernelBB, - MBBVectorTy &EpilogBBs, - SMSchedule &Schedule, ValueMapTy *VRMap) { - assert(PrologBBs.size() == EpilogBBs.size() && "Prolog/Epilog mismatch"); - MachineInstr *IndVar = Pass.LI.LoopInductionVar; - MachineInstr *Cmp = Pass.LI.LoopCompare; - MachineBasicBlock *LastPro = KernelBB; - MachineBasicBlock *LastEpi = KernelBB; - - // Start from the blocks connected to the kernel and work "out" - // to the first prolog and the last epilog blocks. - SmallVector PrevInsts; - unsigned MaxIter = PrologBBs.size() - 1; - unsigned LC = UINT_MAX; - unsigned LCMin = UINT_MAX; - for (unsigned i = 0, j = MaxIter; i <= MaxIter; ++i, --j) { - // Add branches to the prolog that go to the corresponding - // epilog, and the fall-thru prolog/kernel block. - MachineBasicBlock *Prolog = PrologBBs[j]; - MachineBasicBlock *Epilog = EpilogBBs[i]; - // We've executed one iteration, so decrement the loop count and check for - // the loop end. - SmallVector Cond; - // Check if the LOOP0 has already been removed. If so, then there is no need - // to reduce the trip count. - if (LC != 0) - LC = TII->reduceLoopCount(*Prolog, PreheaderBB, IndVar, *Cmp, Cond, - PrevInsts, j, MaxIter); - - // Record the value of the first trip count, which is used to determine if - // branches and blocks can be removed for constant trip counts. - if (LCMin == UINT_MAX) - LCMin = LC; - - unsigned numAdded = 0; - if (Register::isVirtualRegister(LC)) { - Prolog->addSuccessor(Epilog); - numAdded = TII->insertBranch(*Prolog, Epilog, LastPro, Cond, DebugLoc()); - } else if (j >= LCMin) { - Prolog->addSuccessor(Epilog); - Prolog->removeSuccessor(LastPro); - LastEpi->removeSuccessor(Epilog); - numAdded = TII->insertBranch(*Prolog, Epilog, nullptr, Cond, DebugLoc()); - removePhis(Epilog, LastEpi); - // Remove the blocks that are no longer referenced. - if (LastPro != LastEpi) { - LastEpi->clear(); - LastEpi->eraseFromParent(); - } - LastPro->clear(); - LastPro->eraseFromParent(); - } else { - numAdded = TII->insertBranch(*Prolog, LastPro, nullptr, Cond, DebugLoc()); - removePhis(Epilog, Prolog); - } - LastPro = Prolog; - LastEpi = Epilog; - for (MachineBasicBlock::reverse_instr_iterator I = Prolog->instr_rbegin(), - E = Prolog->instr_rend(); - I != E && numAdded > 0; ++I, --numAdded) - updateInstruction(&*I, false, j, 0, Schedule, VRMap); - } -} - /// Return true if we can compute the amount the instruction changes /// during each iteration. Set Delta to the amount of the change. bool SwingSchedulerDAG::computeDelta(MachineInstr &MI, unsigned &Delta) { @@ -2866,261 +2058,6 @@ return true; } -/// Update the memory operand with a new offset when the pipeliner -/// generates a new copy of the instruction that refers to a -/// different memory location. -void SwingSchedulerDAG::updateMemOperands(MachineInstr &NewMI, - MachineInstr &OldMI, unsigned Num) { - if (Num == 0) - return; - // If the instruction has memory operands, then adjust the offset - // when the instruction appears in different stages. - if (NewMI.memoperands_empty()) - return; - SmallVector NewMMOs; - for (MachineMemOperand *MMO : NewMI.memoperands()) { - // TODO: Figure out whether isAtomic is really necessary (see D57601). - if (MMO->isVolatile() || MMO->isAtomic() || - (MMO->isInvariant() && MMO->isDereferenceable()) || - (!MMO->getValue())) { - NewMMOs.push_back(MMO); - continue; - } - unsigned Delta; - if (Num != UINT_MAX && computeDelta(OldMI, Delta)) { - int64_t AdjOffset = Delta * Num; - NewMMOs.push_back( - MF.getMachineMemOperand(MMO, AdjOffset, MMO->getSize())); - } else { - NewMMOs.push_back( - MF.getMachineMemOperand(MMO, 0, MemoryLocation::UnknownSize)); - } - } - NewMI.setMemRefs(MF, NewMMOs); -} - -/// Clone the instruction for the new pipelined loop and update the -/// memory operands, if needed. -MachineInstr *SwingSchedulerDAG::cloneInstr(MachineInstr *OldMI, - unsigned CurStageNum, - unsigned InstStageNum) { - MachineInstr *NewMI = MF.CloneMachineInstr(OldMI); - // Check for tied operands in inline asm instructions. This should be handled - // elsewhere, but I'm not sure of the best solution. - if (OldMI->isInlineAsm()) - for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) { - const auto &MO = OldMI->getOperand(i); - if (MO.isReg() && MO.isUse()) - break; - unsigned UseIdx; - if (OldMI->isRegTiedToUseOperand(i, &UseIdx)) - NewMI->tieOperands(i, UseIdx); - } - updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum); - return NewMI; -} - -/// Clone the instruction for the new pipelined loop. If needed, this -/// function updates the instruction using the values saved in the -/// InstrChanges structure. -MachineInstr *SwingSchedulerDAG::cloneAndChangeInstr(MachineInstr *OldMI, - unsigned CurStageNum, - unsigned InstStageNum, - SMSchedule &Schedule) { - MachineInstr *NewMI = MF.CloneMachineInstr(OldMI); - DenseMap>::iterator It = - InstrChanges.find(getSUnit(OldMI)); - if (It != InstrChanges.end()) { - std::pair RegAndOffset = It->second; - unsigned BasePos, OffsetPos; - if (!TII->getBaseAndOffsetPosition(*OldMI, BasePos, OffsetPos)) - return nullptr; - int64_t NewOffset = OldMI->getOperand(OffsetPos).getImm(); - MachineInstr *LoopDef = findDefInLoop(RegAndOffset.first); - if (Schedule.stageScheduled(getSUnit(LoopDef)) > (signed)InstStageNum) - NewOffset += RegAndOffset.second * (CurStageNum - InstStageNum); - NewMI->getOperand(OffsetPos).setImm(NewOffset); - } - updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum); - return NewMI; -} - -/// Update the machine instruction with new virtual registers. This -/// function may change the defintions and/or uses. -void SwingSchedulerDAG::updateInstruction(MachineInstr *NewMI, bool LastDef, - unsigned CurStageNum, - unsigned InstrStageNum, - SMSchedule &Schedule, - ValueMapTy *VRMap) { - for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { - MachineOperand &MO = NewMI->getOperand(i); - if (!MO.isReg() || !Register::isVirtualRegister(MO.getReg())) - continue; - Register reg = MO.getReg(); - if (MO.isDef()) { - // Create a new virtual register for the definition. - const TargetRegisterClass *RC = MRI.getRegClass(reg); - Register NewReg = MRI.createVirtualRegister(RC); - MO.setReg(NewReg); - VRMap[CurStageNum][reg] = NewReg; - if (LastDef) - replaceRegUsesAfterLoop(reg, NewReg, BB, MRI, LIS); - } else if (MO.isUse()) { - MachineInstr *Def = MRI.getVRegDef(reg); - // Compute the stage that contains the last definition for instruction. - int DefStageNum = Schedule.stageScheduled(getSUnit(Def)); - unsigned StageNum = CurStageNum; - if (DefStageNum != -1 && (int)InstrStageNum > DefStageNum) { - // Compute the difference in stages between the defintion and the use. - unsigned StageDiff = (InstrStageNum - DefStageNum); - // Make an adjustment to get the last definition. - StageNum -= StageDiff; - } - if (VRMap[StageNum].count(reg)) - MO.setReg(VRMap[StageNum][reg]); - } - } -} - -/// Return the instruction in the loop that defines the register. -/// If the definition is a Phi, then follow the Phi operand to -/// the instruction in the loop. -MachineInstr *SwingSchedulerDAG::findDefInLoop(unsigned Reg) { - SmallPtrSet Visited; - MachineInstr *Def = MRI.getVRegDef(Reg); - while (Def->isPHI()) { - if (!Visited.insert(Def).second) - break; - for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2) - if (Def->getOperand(i + 1).getMBB() == BB) { - Def = MRI.getVRegDef(Def->getOperand(i).getReg()); - break; - } - } - return Def; -} - -/// Return the new name for the value from the previous stage. -unsigned SwingSchedulerDAG::getPrevMapVal(unsigned StageNum, unsigned PhiStage, - unsigned LoopVal, unsigned LoopStage, - ValueMapTy *VRMap, - MachineBasicBlock *BB) { - unsigned PrevVal = 0; - if (StageNum > PhiStage) { - MachineInstr *LoopInst = MRI.getVRegDef(LoopVal); - if (PhiStage == LoopStage && VRMap[StageNum - 1].count(LoopVal)) - // The name is defined in the previous stage. - PrevVal = VRMap[StageNum - 1][LoopVal]; - else if (VRMap[StageNum].count(LoopVal)) - // The previous name is defined in the current stage when the instruction - // order is swapped. - PrevVal = VRMap[StageNum][LoopVal]; - else if (!LoopInst->isPHI() || LoopInst->getParent() != BB) - // The loop value hasn't yet been scheduled. - PrevVal = LoopVal; - else if (StageNum == PhiStage + 1) - // The loop value is another phi, which has not been scheduled. - PrevVal = getInitPhiReg(*LoopInst, BB); - else if (StageNum > PhiStage + 1 && LoopInst->getParent() == BB) - // The loop value is another phi, which has been scheduled. - PrevVal = - getPrevMapVal(StageNum - 1, PhiStage, getLoopPhiReg(*LoopInst, BB), - LoopStage, VRMap, BB); - } - return PrevVal; -} - -/// Rewrite the Phi values in the specified block to use the mappings -/// from the initial operand. Once the Phi is scheduled, we switch -/// to using the loop value instead of the Phi value, so those names -/// do not need to be rewritten. -void SwingSchedulerDAG::rewritePhiValues(MachineBasicBlock *NewBB, - unsigned StageNum, - SMSchedule &Schedule, - ValueMapTy *VRMap, - InstrMapTy &InstrMap) { - for (auto &PHI : BB->phis()) { - unsigned InitVal = 0; - unsigned LoopVal = 0; - getPhiRegs(PHI, BB, InitVal, LoopVal); - Register PhiDef = PHI.getOperand(0).getReg(); - - unsigned PhiStage = - (unsigned)Schedule.stageScheduled(getSUnit(MRI.getVRegDef(PhiDef))); - unsigned LoopStage = - (unsigned)Schedule.stageScheduled(getSUnit(MRI.getVRegDef(LoopVal))); - unsigned NumPhis = Schedule.getStagesForPhi(PhiDef); - if (NumPhis > StageNum) - NumPhis = StageNum; - for (unsigned np = 0; np <= NumPhis; ++np) { - unsigned NewVal = - getPrevMapVal(StageNum - np, PhiStage, LoopVal, LoopStage, VRMap, BB); - if (!NewVal) - NewVal = InitVal; - rewriteScheduledInstr(NewBB, Schedule, InstrMap, StageNum - np, np, &PHI, - PhiDef, NewVal); - } - } -} - -/// Rewrite a previously scheduled instruction to use the register value -/// from the new instruction. Make sure the instruction occurs in the -/// basic block, and we don't change the uses in the new instruction. -void SwingSchedulerDAG::rewriteScheduledInstr( - MachineBasicBlock *BB, SMSchedule &Schedule, InstrMapTy &InstrMap, - unsigned CurStageNum, unsigned PhiNum, MachineInstr *Phi, unsigned OldReg, - unsigned NewReg, unsigned PrevReg) { - bool InProlog = (CurStageNum < Schedule.getMaxStageCount()); - int StagePhi = Schedule.stageScheduled(getSUnit(Phi)) + PhiNum; - // Rewrite uses that have been scheduled already to use the new - // Phi register. - for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(OldReg), - EI = MRI.use_end(); - UI != EI;) { - MachineOperand &UseOp = *UI; - MachineInstr *UseMI = UseOp.getParent(); - ++UI; - if (UseMI->getParent() != BB) - continue; - if (UseMI->isPHI()) { - if (!Phi->isPHI() && UseMI->getOperand(0).getReg() == NewReg) - continue; - if (getLoopPhiReg(*UseMI, BB) != OldReg) - continue; - } - InstrMapTy::iterator OrigInstr = InstrMap.find(UseMI); - assert(OrigInstr != InstrMap.end() && "Instruction not scheduled."); - SUnit *OrigMISU = getSUnit(OrigInstr->second); - int StageSched = Schedule.stageScheduled(OrigMISU); - int CycleSched = Schedule.cycleScheduled(OrigMISU); - unsigned ReplaceReg = 0; - // This is the stage for the scheduled instruction. - if (StagePhi == StageSched && Phi->isPHI()) { - int CyclePhi = Schedule.cycleScheduled(getSUnit(Phi)); - if (PrevReg && InProlog) - ReplaceReg = PrevReg; - else if (PrevReg && !Schedule.isLoopCarried(this, *Phi) && - (CyclePhi <= CycleSched || OrigMISU->getInstr()->isPHI())) - ReplaceReg = PrevReg; - else - ReplaceReg = NewReg; - } - // The scheduled instruction occurs before the scheduled Phi, and the - // Phi is not loop carried. - if (!InProlog && StagePhi + 1 == StageSched && - !Schedule.isLoopCarried(this, *Phi)) - ReplaceReg = NewReg; - if (StagePhi > StageSched && Phi->isPHI()) - ReplaceReg = NewReg; - if (!InProlog && !Phi->isPHI() && StagePhi < StageSched) - ReplaceReg = NewReg; - if (ReplaceReg) { - MRI.constrainRegClass(ReplaceReg, MRI.getRegClass(OldReg)); - UseOp.setReg(ReplaceReg); - } - } -} - /// Check if we can change the instruction to use an offset value from the /// previous iteration. If so, return true and set the base and offset values /// so that we can rewrite the load, if necessary. @@ -3213,11 +2150,29 @@ NewMI->getOperand(OffsetPos).setImm(NewOffset); SU->setInstr(NewMI); MISUnitMap[NewMI] = SU; - NewMIs.insert(NewMI); + NewMIs[MI] = NewMI; } } } +/// Return the instruction in the loop that defines the register. +/// If the definition is a Phi, then follow the Phi operand to +/// the instruction in the loop. +MachineInstr *SwingSchedulerDAG::findDefInLoop(unsigned Reg) { + SmallPtrSet Visited; + MachineInstr *Def = MRI.getVRegDef(Reg); + while (Def->isPHI()) { + if (!Visited.insert(Def).second) + break; + for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2) + if (Def->getOperand(i + 1).getMBB() == BB) { + Def = MRI.getVRegDef(Def->getOperand(i).getReg()); + break; + } + } + return Def; +} + /// Return true for an order or output dependence that is loop carried /// potentially. A dependence is loop carried if the destination defines a valu /// that may be used or defined by the source in a subsequent iteration. @@ -3802,7 +2757,7 @@ NewMI->getOperand(OffsetPos).setImm(NewOffset); SU->setInstr(NewMI); MISUnitMap[NewMI] = SU; - NewMIs.insert(NewMI); + NewMIs[MI] = NewMI; } } OverlapReg = 0; @@ -3839,40 +2794,6 @@ ScheduledInstrs[cycle].push_front(*I); } } - // Iterate over the definitions in each instruction, and compute the - // stage difference for each use. Keep the maximum value. - for (auto &I : InstrToCycle) { - int DefStage = stageScheduled(I.first); - MachineInstr *MI = I.first->getInstr(); - for (unsigned i = 0, e = MI->getNumOperands(); i < e; ++i) { - MachineOperand &Op = MI->getOperand(i); - if (!Op.isReg() || !Op.isDef()) - continue; - - Register Reg = Op.getReg(); - unsigned MaxDiff = 0; - bool PhiIsSwapped = false; - for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(Reg), - EI = MRI.use_end(); - UI != EI; ++UI) { - MachineOperand &UseOp = *UI; - MachineInstr *UseMI = UseOp.getParent(); - SUnit *SUnitUse = SSD->getSUnit(UseMI); - int UseStage = stageScheduled(SUnitUse); - unsigned Diff = 0; - if (UseStage != -1 && UseStage >= DefStage) - Diff = UseStage - DefStage; - if (MI->isPHI()) { - if (isLoopCarried(SSD, *MI)) - ++Diff; - else - PhiIsSwapped = true; - } - MaxDiff = std::max(Diff, MaxDiff); - } - RegToStageDiff[Reg] = std::make_pair(MaxDiff, PhiIsSwapped); - } - } // Erase all the elements in the later stages. Only one iteration should // remain in the scheduled list, and it contains all the instructions. @@ -4077,4 +2998,3 @@ return DFAResources->clearResources(); std::fill(ProcResourceCount.begin(), ProcResourceCount.end(), 0); } - Index: llvm/trunk/lib/CodeGen/ModuloSchedule.cpp =================================================================== --- llvm/trunk/lib/CodeGen/ModuloSchedule.cpp +++ llvm/trunk/lib/CodeGen/ModuloSchedule.cpp @@ -0,0 +1,1190 @@ +//===- ModuloSchedule.cpp - Software pipeline schedule expansion ----------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/ModuloSchedule.h" +#include "llvm/CodeGen/LiveIntervals.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/CodeGen/TargetInstrInfo.h" +#include "llvm/Support/Debug.h" + +#define DEBUG_TYPE "pipeliner" +using namespace llvm; + +/// Return the register values for the operands of a Phi instruction. +/// This function assume the instruction is a Phi. +static void getPhiRegs(MachineInstr &Phi, MachineBasicBlock *Loop, + unsigned &InitVal, unsigned &LoopVal) { + assert(Phi.isPHI() && "Expecting a Phi."); + + InitVal = 0; + LoopVal = 0; + for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2) + if (Phi.getOperand(i + 1).getMBB() != Loop) + InitVal = Phi.getOperand(i).getReg(); + else + LoopVal = Phi.getOperand(i).getReg(); + + assert(InitVal != 0 && LoopVal != 0 && "Unexpected Phi structure."); +} + +/// Return the Phi register value that comes from the incoming block. +static unsigned getInitPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB) { + for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2) + if (Phi.getOperand(i + 1).getMBB() != LoopBB) + return Phi.getOperand(i).getReg(); + return 0; +} + +/// Return the Phi register value that comes the loop block. +static unsigned getLoopPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB) { + for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2) + if (Phi.getOperand(i + 1).getMBB() == LoopBB) + return Phi.getOperand(i).getReg(); + return 0; +} + +void ModuloScheduleExpander::expand() { + BB = Schedule.getLoop()->getTopBlock(); + Preheader = *BB->pred_begin(); + if (Preheader == BB) + Preheader = *std::next(BB->pred_begin()); + + // Iterate over the definitions in each instruction, and compute the + // stage difference for each use. Keep the maximum value. + for (MachineInstr *MI : Schedule.getInstructions()) { + int DefStage = Schedule.getStage(MI); + for (unsigned i = 0, e = MI->getNumOperands(); i < e; ++i) { + MachineOperand &Op = MI->getOperand(i); + if (!Op.isReg() || !Op.isDef()) + continue; + + Register Reg = Op.getReg(); + unsigned MaxDiff = 0; + bool PhiIsSwapped = false; + for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(Reg), + EI = MRI.use_end(); + UI != EI; ++UI) { + MachineOperand &UseOp = *UI; + MachineInstr *UseMI = UseOp.getParent(); + int UseStage = Schedule.getStage(UseMI); + unsigned Diff = 0; + if (UseStage != -1 && UseStage >= DefStage) + Diff = UseStage - DefStage; + if (MI->isPHI()) { + if (isLoopCarried(*MI)) + ++Diff; + else + PhiIsSwapped = true; + } + MaxDiff = std::max(Diff, MaxDiff); + } + RegToStageDiff[Reg] = std::make_pair(MaxDiff, PhiIsSwapped); + } + } + + generatePipelinedLoop(); +} + +void ModuloScheduleExpander::generatePipelinedLoop() { + // Create a new basic block for the kernel and add it to the CFG. + MachineBasicBlock *KernelBB = MF.CreateMachineBasicBlock(BB->getBasicBlock()); + + unsigned MaxStageCount = Schedule.getNumStages() - 1; + + // Remember the registers that are used in different stages. The index is + // the iteration, or stage, that the instruction is scheduled in. This is + // a map between register names in the original block and the names created + // in each stage of the pipelined loop. + ValueMapTy *VRMap = new ValueMapTy[(MaxStageCount + 1) * 2]; + InstrMapTy InstrMap; + + SmallVector PrologBBs; + + // Generate the prolog instructions that set up the pipeline. + generateProlog(MaxStageCount, KernelBB, VRMap, PrologBBs); + MF.insert(BB->getIterator(), KernelBB); + + // Rearrange the instructions to generate the new, pipelined loop, + // and update register names as needed. + for (MachineInstr *CI : Schedule.getInstructions()) { + if (CI->isPHI()) + continue; + unsigned StageNum = Schedule.getStage(CI); + MachineInstr *NewMI = cloneInstr(CI, MaxStageCount, StageNum); + updateInstruction(NewMI, false, MaxStageCount, StageNum, VRMap); + KernelBB->push_back(NewMI); + InstrMap[NewMI] = CI; + } + + // Copy any terminator instructions to the new kernel, and update + // names as needed. + for (MachineBasicBlock::iterator I = BB->getFirstTerminator(), + E = BB->instr_end(); + I != E; ++I) { + MachineInstr *NewMI = MF.CloneMachineInstr(&*I); + updateInstruction(NewMI, false, MaxStageCount, 0, VRMap); + KernelBB->push_back(NewMI); + InstrMap[NewMI] = &*I; + } + + KernelBB->transferSuccessors(BB); + KernelBB->replaceSuccessor(BB, KernelBB); + + generateExistingPhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, VRMap, + InstrMap, MaxStageCount, MaxStageCount, false); + generatePhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, VRMap, InstrMap, + MaxStageCount, MaxStageCount, false); + + LLVM_DEBUG(dbgs() << "New block\n"; KernelBB->dump();); + + SmallVector EpilogBBs; + // Generate the epilog instructions to complete the pipeline. + generateEpilog(MaxStageCount, KernelBB, VRMap, EpilogBBs, PrologBBs); + + // We need this step because the register allocation doesn't handle some + // situations well, so we insert copies to help out. + splitLifetimes(KernelBB, EpilogBBs); + + // Remove dead instructions due to loop induction variables. + removeDeadInstructions(KernelBB, EpilogBBs); + + // Add branches between prolog and epilog blocks. + addBranches(*Preheader, PrologBBs, KernelBB, EpilogBBs, VRMap); + + // Remove the original loop since it's no longer referenced. + for (auto &I : *BB) + LIS.RemoveMachineInstrFromMaps(I); + BB->clear(); + BB->eraseFromParent(); + + delete[] VRMap; +} + +/// Generate the pipeline prolog code. +void ModuloScheduleExpander::generateProlog(unsigned LastStage, + MachineBasicBlock *KernelBB, + ValueMapTy *VRMap, + MBBVectorTy &PrologBBs) { + MachineBasicBlock *PredBB = Preheader; + InstrMapTy InstrMap; + + // Generate a basic block for each stage, not including the last stage, + // which will be generated in the kernel. Each basic block may contain + // instructions from multiple stages/iterations. + for (unsigned i = 0; i < LastStage; ++i) { + // Create and insert the prolog basic block prior to the original loop + // basic block. The original loop is removed later. + MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(BB->getBasicBlock()); + PrologBBs.push_back(NewBB); + MF.insert(BB->getIterator(), NewBB); + NewBB->transferSuccessors(PredBB); + PredBB->addSuccessor(NewBB); + PredBB = NewBB; + + // Generate instructions for each appropriate stage. Process instructions + // in original program order. + for (int StageNum = i; StageNum >= 0; --StageNum) { + for (MachineBasicBlock::iterator BBI = BB->instr_begin(), + BBE = BB->getFirstTerminator(); + BBI != BBE; ++BBI) { + if (Schedule.getStage(&*BBI) == StageNum) { + if (BBI->isPHI()) + continue; + MachineInstr *NewMI = + cloneAndChangeInstr(&*BBI, i, (unsigned)StageNum); + updateInstruction(NewMI, false, i, (unsigned)StageNum, VRMap); + NewBB->push_back(NewMI); + InstrMap[NewMI] = &*BBI; + } + } + } + rewritePhiValues(NewBB, i, VRMap, InstrMap); + LLVM_DEBUG({ + dbgs() << "prolog:\n"; + NewBB->dump(); + }); + } + + PredBB->replaceSuccessor(BB, KernelBB); + + // Check if we need to remove the branch from the preheader to the original + // loop, and replace it with a branch to the new loop. + unsigned numBranches = TII->removeBranch(*Preheader); + if (numBranches) { + SmallVector Cond; + TII->insertBranch(*Preheader, PrologBBs[0], nullptr, Cond, DebugLoc()); + } +} + +/// Generate the pipeline epilog code. The epilog code finishes the iterations +/// that were started in either the prolog or the kernel. We create a basic +/// block for each stage that needs to complete. +void ModuloScheduleExpander::generateEpilog(unsigned LastStage, + MachineBasicBlock *KernelBB, + ValueMapTy *VRMap, + MBBVectorTy &EpilogBBs, + MBBVectorTy &PrologBBs) { + // We need to change the branch from the kernel to the first epilog block, so + // this call to analyze branch uses the kernel rather than the original BB. + MachineBasicBlock *TBB = nullptr, *FBB = nullptr; + SmallVector Cond; + bool checkBranch = TII->analyzeBranch(*KernelBB, TBB, FBB, Cond); + assert(!checkBranch && "generateEpilog must be able to analyze the branch"); + if (checkBranch) + return; + + MachineBasicBlock::succ_iterator LoopExitI = KernelBB->succ_begin(); + if (*LoopExitI == KernelBB) + ++LoopExitI; + assert(LoopExitI != KernelBB->succ_end() && "Expecting a successor"); + MachineBasicBlock *LoopExitBB = *LoopExitI; + + MachineBasicBlock *PredBB = KernelBB; + MachineBasicBlock *EpilogStart = LoopExitBB; + InstrMapTy InstrMap; + + // Generate a basic block for each stage, not including the last stage, + // which was generated for the kernel. Each basic block may contain + // instructions from multiple stages/iterations. + int EpilogStage = LastStage + 1; + for (unsigned i = LastStage; i >= 1; --i, ++EpilogStage) { + MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(); + EpilogBBs.push_back(NewBB); + MF.insert(BB->getIterator(), NewBB); + + PredBB->replaceSuccessor(LoopExitBB, NewBB); + NewBB->addSuccessor(LoopExitBB); + + if (EpilogStart == LoopExitBB) + EpilogStart = NewBB; + + // Add instructions to the epilog depending on the current block. + // Process instructions in original program order. + for (unsigned StageNum = i; StageNum <= LastStage; ++StageNum) { + for (auto &BBI : *BB) { + if (BBI.isPHI()) + continue; + MachineInstr *In = &BBI; + if ((unsigned)Schedule.getStage(In) == StageNum) { + // Instructions with memoperands in the epilog are updated with + // conservative values. + MachineInstr *NewMI = cloneInstr(In, UINT_MAX, 0); + updateInstruction(NewMI, i == 1, EpilogStage, 0, VRMap); + NewBB->push_back(NewMI); + InstrMap[NewMI] = In; + } + } + } + generateExistingPhis(NewBB, PrologBBs[i - 1], PredBB, KernelBB, VRMap, + InstrMap, LastStage, EpilogStage, i == 1); + generatePhis(NewBB, PrologBBs[i - 1], PredBB, KernelBB, VRMap, InstrMap, + LastStage, EpilogStage, i == 1); + PredBB = NewBB; + + LLVM_DEBUG({ + dbgs() << "epilog:\n"; + NewBB->dump(); + }); + } + + // Fix any Phi nodes in the loop exit block. + LoopExitBB->replacePhiUsesWith(BB, PredBB); + + // Create a branch to the new epilog from the kernel. + // Remove the original branch and add a new branch to the epilog. + TII->removeBranch(*KernelBB); + TII->insertBranch(*KernelBB, KernelBB, EpilogStart, Cond, DebugLoc()); + // Add a branch to the loop exit. + if (EpilogBBs.size() > 0) { + MachineBasicBlock *LastEpilogBB = EpilogBBs.back(); + SmallVector Cond1; + TII->insertBranch(*LastEpilogBB, LoopExitBB, nullptr, Cond1, DebugLoc()); + } +} + +/// Replace all uses of FromReg that appear outside the specified +/// basic block with ToReg. +static void replaceRegUsesAfterLoop(unsigned FromReg, unsigned ToReg, + MachineBasicBlock *MBB, + MachineRegisterInfo &MRI, + LiveIntervals &LIS) { + for (MachineRegisterInfo::use_iterator I = MRI.use_begin(FromReg), + E = MRI.use_end(); + I != E;) { + MachineOperand &O = *I; + ++I; + if (O.getParent()->getParent() != MBB) + O.setReg(ToReg); + } + if (!LIS.hasInterval(ToReg)) + LIS.createEmptyInterval(ToReg); +} + +/// Return true if the register has a use that occurs outside the +/// specified loop. +static bool hasUseAfterLoop(unsigned Reg, MachineBasicBlock *BB, + MachineRegisterInfo &MRI) { + for (MachineRegisterInfo::use_iterator I = MRI.use_begin(Reg), + E = MRI.use_end(); + I != E; ++I) + if (I->getParent()->getParent() != BB) + return true; + return false; +} + +/// Generate Phis for the specific block in the generated pipelined code. +/// This function looks at the Phis from the original code to guide the +/// creation of new Phis. +void ModuloScheduleExpander::generateExistingPhis( + MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2, + MachineBasicBlock *KernelBB, ValueMapTy *VRMap, InstrMapTy &InstrMap, + unsigned LastStageNum, unsigned CurStageNum, bool IsLast) { + // Compute the stage number for the initial value of the Phi, which + // comes from the prolog. The prolog to use depends on to which kernel/ + // epilog that we're adding the Phi. + unsigned PrologStage = 0; + unsigned PrevStage = 0; + bool InKernel = (LastStageNum == CurStageNum); + if (InKernel) { + PrologStage = LastStageNum - 1; + PrevStage = CurStageNum; + } else { + PrologStage = LastStageNum - (CurStageNum - LastStageNum); + PrevStage = LastStageNum + (CurStageNum - LastStageNum) - 1; + } + + for (MachineBasicBlock::iterator BBI = BB->instr_begin(), + BBE = BB->getFirstNonPHI(); + BBI != BBE; ++BBI) { + Register Def = BBI->getOperand(0).getReg(); + + unsigned InitVal = 0; + unsigned LoopVal = 0; + getPhiRegs(*BBI, BB, InitVal, LoopVal); + + unsigned PhiOp1 = 0; + // The Phi value from the loop body typically is defined in the loop, but + // not always. So, we need to check if the value is defined in the loop. + unsigned PhiOp2 = LoopVal; + if (VRMap[LastStageNum].count(LoopVal)) + PhiOp2 = VRMap[LastStageNum][LoopVal]; + + int StageScheduled = Schedule.getStage(&*BBI); + int LoopValStage = Schedule.getStage(MRI.getVRegDef(LoopVal)); + unsigned NumStages = getStagesForReg(Def, CurStageNum); + if (NumStages == 0) { + // We don't need to generate a Phi anymore, but we need to rename any uses + // of the Phi value. + unsigned NewReg = VRMap[PrevStage][LoopVal]; + rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, 0, &*BBI, Def, + InitVal, NewReg); + if (VRMap[CurStageNum].count(LoopVal)) + VRMap[CurStageNum][Def] = VRMap[CurStageNum][LoopVal]; + } + // Adjust the number of Phis needed depending on the number of prologs left, + // and the distance from where the Phi is first scheduled. The number of + // Phis cannot exceed the number of prolog stages. Each stage can + // potentially define two values. + unsigned MaxPhis = PrologStage + 2; + if (!InKernel && (int)PrologStage <= LoopValStage) + MaxPhis = std::max((int)MaxPhis - (int)LoopValStage, 1); + unsigned NumPhis = std::min(NumStages, MaxPhis); + + unsigned NewReg = 0; + unsigned AccessStage = (LoopValStage != -1) ? LoopValStage : StageScheduled; + // In the epilog, we may need to look back one stage to get the correct + // Phi name because the epilog and prolog blocks execute the same stage. + // The correct name is from the previous block only when the Phi has + // been completely scheduled prior to the epilog, and Phi value is not + // needed in multiple stages. + int StageDiff = 0; + if (!InKernel && StageScheduled >= LoopValStage && AccessStage == 0 && + NumPhis == 1) + StageDiff = 1; + // Adjust the computations below when the phi and the loop definition + // are scheduled in different stages. + if (InKernel && LoopValStage != -1 && StageScheduled > LoopValStage) + StageDiff = StageScheduled - LoopValStage; + for (unsigned np = 0; np < NumPhis; ++np) { + // If the Phi hasn't been scheduled, then use the initial Phi operand + // value. Otherwise, use the scheduled version of the instruction. This + // is a little complicated when a Phi references another Phi. + if (np > PrologStage || StageScheduled >= (int)LastStageNum) + PhiOp1 = InitVal; + // Check if the Phi has already been scheduled in a prolog stage. + else if (PrologStage >= AccessStage + StageDiff + np && + VRMap[PrologStage - StageDiff - np].count(LoopVal) != 0) + PhiOp1 = VRMap[PrologStage - StageDiff - np][LoopVal]; + // Check if the Phi has already been scheduled, but the loop instruction + // is either another Phi, or doesn't occur in the loop. + else if (PrologStage >= AccessStage + StageDiff + np) { + // If the Phi references another Phi, we need to examine the other + // Phi to get the correct value. + PhiOp1 = LoopVal; + MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1); + int Indirects = 1; + while (InstOp1 && InstOp1->isPHI() && InstOp1->getParent() == BB) { + int PhiStage = Schedule.getStage(InstOp1); + if ((int)(PrologStage - StageDiff - np) < PhiStage + Indirects) + PhiOp1 = getInitPhiReg(*InstOp1, BB); + else + PhiOp1 = getLoopPhiReg(*InstOp1, BB); + InstOp1 = MRI.getVRegDef(PhiOp1); + int PhiOpStage = Schedule.getStage(InstOp1); + int StageAdj = (PhiOpStage != -1 ? PhiStage - PhiOpStage : 0); + if (PhiOpStage != -1 && PrologStage - StageAdj >= Indirects + np && + VRMap[PrologStage - StageAdj - Indirects - np].count(PhiOp1)) { + PhiOp1 = VRMap[PrologStage - StageAdj - Indirects - np][PhiOp1]; + break; + } + ++Indirects; + } + } else + PhiOp1 = InitVal; + // If this references a generated Phi in the kernel, get the Phi operand + // from the incoming block. + if (MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1)) + if (InstOp1->isPHI() && InstOp1->getParent() == KernelBB) + PhiOp1 = getInitPhiReg(*InstOp1, KernelBB); + + MachineInstr *PhiInst = MRI.getVRegDef(LoopVal); + bool LoopDefIsPhi = PhiInst && PhiInst->isPHI(); + // In the epilog, a map lookup is needed to get the value from the kernel, + // or previous epilog block. How is does this depends on if the + // instruction is scheduled in the previous block. + if (!InKernel) { + int StageDiffAdj = 0; + if (LoopValStage != -1 && StageScheduled > LoopValStage) + StageDiffAdj = StageScheduled - LoopValStage; + // Use the loop value defined in the kernel, unless the kernel + // contains the last definition of the Phi. + if (np == 0 && PrevStage == LastStageNum && + (StageScheduled != 0 || LoopValStage != 0) && + VRMap[PrevStage - StageDiffAdj].count(LoopVal)) + PhiOp2 = VRMap[PrevStage - StageDiffAdj][LoopVal]; + // Use the value defined by the Phi. We add one because we switch + // from looking at the loop value to the Phi definition. + else if (np > 0 && PrevStage == LastStageNum && + VRMap[PrevStage - np + 1].count(Def)) + PhiOp2 = VRMap[PrevStage - np + 1][Def]; + // Use the loop value defined in the kernel. + else if (static_cast(LoopValStage) > PrologStage + 1 && + VRMap[PrevStage - StageDiffAdj - np].count(LoopVal)) + PhiOp2 = VRMap[PrevStage - StageDiffAdj - np][LoopVal]; + // Use the value defined by the Phi, unless we're generating the first + // epilog and the Phi refers to a Phi in a different stage. + else if (VRMap[PrevStage - np].count(Def) && + (!LoopDefIsPhi || (PrevStage != LastStageNum) || + (LoopValStage == StageScheduled))) + PhiOp2 = VRMap[PrevStage - np][Def]; + } + + // Check if we can reuse an existing Phi. This occurs when a Phi + // references another Phi, and the other Phi is scheduled in an + // earlier stage. We can try to reuse an existing Phi up until the last + // stage of the current Phi. + if (LoopDefIsPhi) { + if (static_cast(PrologStage - np) >= StageScheduled) { + int LVNumStages = getStagesForPhi(LoopVal); + int StageDiff = (StageScheduled - LoopValStage); + LVNumStages -= StageDiff; + // Make sure the loop value Phi has been processed already. + if (LVNumStages > (int)np && VRMap[CurStageNum].count(LoopVal)) { + NewReg = PhiOp2; + unsigned ReuseStage = CurStageNum; + if (isLoopCarried(*PhiInst)) + ReuseStage -= LVNumStages; + // Check if the Phi to reuse has been generated yet. If not, then + // there is nothing to reuse. + if (VRMap[ReuseStage - np].count(LoopVal)) { + NewReg = VRMap[ReuseStage - np][LoopVal]; + + rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, + Def, NewReg); + // Update the map with the new Phi name. + VRMap[CurStageNum - np][Def] = NewReg; + PhiOp2 = NewReg; + if (VRMap[LastStageNum - np - 1].count(LoopVal)) + PhiOp2 = VRMap[LastStageNum - np - 1][LoopVal]; + + if (IsLast && np == NumPhis - 1) + replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS); + continue; + } + } + } + if (InKernel && StageDiff > 0 && + VRMap[CurStageNum - StageDiff - np].count(LoopVal)) + PhiOp2 = VRMap[CurStageNum - StageDiff - np][LoopVal]; + } + + const TargetRegisterClass *RC = MRI.getRegClass(Def); + NewReg = MRI.createVirtualRegister(RC); + + MachineInstrBuilder NewPhi = + BuildMI(*NewBB, NewBB->getFirstNonPHI(), DebugLoc(), + TII->get(TargetOpcode::PHI), NewReg); + NewPhi.addReg(PhiOp1).addMBB(BB1); + NewPhi.addReg(PhiOp2).addMBB(BB2); + if (np == 0) + InstrMap[NewPhi] = &*BBI; + + // We define the Phis after creating the new pipelined code, so + // we need to rename the Phi values in scheduled instructions. + + unsigned PrevReg = 0; + if (InKernel && VRMap[PrevStage - np].count(LoopVal)) + PrevReg = VRMap[PrevStage - np][LoopVal]; + rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, Def, + NewReg, PrevReg); + // If the Phi has been scheduled, use the new name for rewriting. + if (VRMap[CurStageNum - np].count(Def)) { + unsigned R = VRMap[CurStageNum - np][Def]; + rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, R, + NewReg); + } + + // Check if we need to rename any uses that occurs after the loop. The + // register to replace depends on whether the Phi is scheduled in the + // epilog. + if (IsLast && np == NumPhis - 1) + replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS); + + // In the kernel, a dependent Phi uses the value from this Phi. + if (InKernel) + PhiOp2 = NewReg; + + // Update the map with the new Phi name. + VRMap[CurStageNum - np][Def] = NewReg; + } + + while (NumPhis++ < NumStages) { + rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, NumPhis, &*BBI, Def, + NewReg, 0); + } + + // Check if we need to rename a Phi that has been eliminated due to + // scheduling. + if (NumStages == 0 && IsLast && VRMap[CurStageNum].count(LoopVal)) + replaceRegUsesAfterLoop(Def, VRMap[CurStageNum][LoopVal], BB, MRI, LIS); + } +} + +/// Generate Phis for the specified block in the generated pipelined code. +/// These are new Phis needed because the definition is scheduled after the +/// use in the pipelined sequence. +void ModuloScheduleExpander::generatePhis( + MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2, + MachineBasicBlock *KernelBB, ValueMapTy *VRMap, InstrMapTy &InstrMap, + unsigned LastStageNum, unsigned CurStageNum, bool IsLast) { + // Compute the stage number that contains the initial Phi value, and + // the Phi from the previous stage. + unsigned PrologStage = 0; + unsigned PrevStage = 0; + unsigned StageDiff = CurStageNum - LastStageNum; + bool InKernel = (StageDiff == 0); + if (InKernel) { + PrologStage = LastStageNum - 1; + PrevStage = CurStageNum; + } else { + PrologStage = LastStageNum - StageDiff; + PrevStage = LastStageNum + StageDiff - 1; + } + + for (MachineBasicBlock::iterator BBI = BB->getFirstNonPHI(), + BBE = BB->instr_end(); + BBI != BBE; ++BBI) { + for (unsigned i = 0, e = BBI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = BBI->getOperand(i); + if (!MO.isReg() || !MO.isDef() || + !Register::isVirtualRegister(MO.getReg())) + continue; + + int StageScheduled = Schedule.getStage(&*BBI); + assert(StageScheduled != -1 && "Expecting scheduled instruction."); + Register Def = MO.getReg(); + unsigned NumPhis = getStagesForReg(Def, CurStageNum); + // An instruction scheduled in stage 0 and is used after the loop + // requires a phi in the epilog for the last definition from either + // the kernel or prolog. + if (!InKernel && NumPhis == 0 && StageScheduled == 0 && + hasUseAfterLoop(Def, BB, MRI)) + NumPhis = 1; + if (!InKernel && (unsigned)StageScheduled > PrologStage) + continue; + + unsigned PhiOp2 = VRMap[PrevStage][Def]; + if (MachineInstr *InstOp2 = MRI.getVRegDef(PhiOp2)) + if (InstOp2->isPHI() && InstOp2->getParent() == NewBB) + PhiOp2 = getLoopPhiReg(*InstOp2, BB2); + // The number of Phis can't exceed the number of prolog stages. The + // prolog stage number is zero based. + if (NumPhis > PrologStage + 1 - StageScheduled) + NumPhis = PrologStage + 1 - StageScheduled; + for (unsigned np = 0; np < NumPhis; ++np) { + unsigned PhiOp1 = VRMap[PrologStage][Def]; + if (np <= PrologStage) + PhiOp1 = VRMap[PrologStage - np][Def]; + if (MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1)) { + if (InstOp1->isPHI() && InstOp1->getParent() == KernelBB) + PhiOp1 = getInitPhiReg(*InstOp1, KernelBB); + if (InstOp1->isPHI() && InstOp1->getParent() == NewBB) + PhiOp1 = getInitPhiReg(*InstOp1, NewBB); + } + if (!InKernel) + PhiOp2 = VRMap[PrevStage - np][Def]; + + const TargetRegisterClass *RC = MRI.getRegClass(Def); + Register NewReg = MRI.createVirtualRegister(RC); + + MachineInstrBuilder NewPhi = + BuildMI(*NewBB, NewBB->getFirstNonPHI(), DebugLoc(), + TII->get(TargetOpcode::PHI), NewReg); + NewPhi.addReg(PhiOp1).addMBB(BB1); + NewPhi.addReg(PhiOp2).addMBB(BB2); + if (np == 0) + InstrMap[NewPhi] = &*BBI; + + // Rewrite uses and update the map. The actions depend upon whether + // we generating code for the kernel or epilog blocks. + if (InKernel) { + rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, PhiOp1, + NewReg); + rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, PhiOp2, + NewReg); + + PhiOp2 = NewReg; + VRMap[PrevStage - np - 1][Def] = NewReg; + } else { + VRMap[CurStageNum - np][Def] = NewReg; + if (np == NumPhis - 1) + rewriteScheduledInstr(NewBB, InstrMap, CurStageNum, np, &*BBI, Def, + NewReg); + } + if (IsLast && np == NumPhis - 1) + replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS); + } + } + } +} + +/// Remove instructions that generate values with no uses. +/// Typically, these are induction variable operations that generate values +/// used in the loop itself. A dead instruction has a definition with +/// no uses, or uses that occur in the original loop only. +void ModuloScheduleExpander::removeDeadInstructions(MachineBasicBlock *KernelBB, + MBBVectorTy &EpilogBBs) { + // For each epilog block, check that the value defined by each instruction + // is used. If not, delete it. + for (MBBVectorTy::reverse_iterator MBB = EpilogBBs.rbegin(), + MBE = EpilogBBs.rend(); + MBB != MBE; ++MBB) + for (MachineBasicBlock::reverse_instr_iterator MI = (*MBB)->instr_rbegin(), + ME = (*MBB)->instr_rend(); + MI != ME;) { + // From DeadMachineInstructionElem. Don't delete inline assembly. + if (MI->isInlineAsm()) { + ++MI; + continue; + } + bool SawStore = false; + // Check if it's safe to remove the instruction due to side effects. + // We can, and want to, remove Phis here. + if (!MI->isSafeToMove(nullptr, SawStore) && !MI->isPHI()) { + ++MI; + continue; + } + bool used = true; + for (MachineInstr::mop_iterator MOI = MI->operands_begin(), + MOE = MI->operands_end(); + MOI != MOE; ++MOI) { + if (!MOI->isReg() || !MOI->isDef()) + continue; + Register reg = MOI->getReg(); + // Assume physical registers are used, unless they are marked dead. + if (Register::isPhysicalRegister(reg)) { + used = !MOI->isDead(); + if (used) + break; + continue; + } + unsigned realUses = 0; + for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(reg), + EI = MRI.use_end(); + UI != EI; ++UI) { + // Check if there are any uses that occur only in the original + // loop. If so, that's not a real use. + if (UI->getParent()->getParent() != BB) { + realUses++; + used = true; + break; + } + } + if (realUses > 0) + break; + used = false; + } + if (!used) { + LIS.RemoveMachineInstrFromMaps(*MI); + MI++->eraseFromParent(); + continue; + } + ++MI; + } + // In the kernel block, check if we can remove a Phi that generates a value + // used in an instruction removed in the epilog block. + for (MachineBasicBlock::iterator BBI = KernelBB->instr_begin(), + BBE = KernelBB->getFirstNonPHI(); + BBI != BBE;) { + MachineInstr *MI = &*BBI; + ++BBI; + Register reg = MI->getOperand(0).getReg(); + if (MRI.use_begin(reg) == MRI.use_end()) { + LIS.RemoveMachineInstrFromMaps(*MI); + MI->eraseFromParent(); + } + } +} + +/// For loop carried definitions, we split the lifetime of a virtual register +/// that has uses past the definition in the next iteration. A copy with a new +/// virtual register is inserted before the definition, which helps with +/// generating a better register assignment. +/// +/// v1 = phi(a, v2) v1 = phi(a, v2) +/// v2 = phi(b, v3) v2 = phi(b, v3) +/// v3 = .. v4 = copy v1 +/// .. = V1 v3 = .. +/// .. = v4 +void ModuloScheduleExpander::splitLifetimes(MachineBasicBlock *KernelBB, + MBBVectorTy &EpilogBBs) { + const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); + for (auto &PHI : KernelBB->phis()) { + Register Def = PHI.getOperand(0).getReg(); + // Check for any Phi definition that used as an operand of another Phi + // in the same block. + for (MachineRegisterInfo::use_instr_iterator I = MRI.use_instr_begin(Def), + E = MRI.use_instr_end(); + I != E; ++I) { + if (I->isPHI() && I->getParent() == KernelBB) { + // Get the loop carried definition. + unsigned LCDef = getLoopPhiReg(PHI, KernelBB); + if (!LCDef) + continue; + MachineInstr *MI = MRI.getVRegDef(LCDef); + if (!MI || MI->getParent() != KernelBB || MI->isPHI()) + continue; + // Search through the rest of the block looking for uses of the Phi + // definition. If one occurs, then split the lifetime. + unsigned SplitReg = 0; + for (auto &BBJ : make_range(MachineBasicBlock::instr_iterator(MI), + KernelBB->instr_end())) + if (BBJ.readsRegister(Def)) { + // We split the lifetime when we find the first use. + if (SplitReg == 0) { + SplitReg = MRI.createVirtualRegister(MRI.getRegClass(Def)); + BuildMI(*KernelBB, MI, MI->getDebugLoc(), + TII->get(TargetOpcode::COPY), SplitReg) + .addReg(Def); + } + BBJ.substituteRegister(Def, SplitReg, 0, *TRI); + } + if (!SplitReg) + continue; + // Search through each of the epilog blocks for any uses to be renamed. + for (auto &Epilog : EpilogBBs) + for (auto &I : *Epilog) + if (I.readsRegister(Def)) + I.substituteRegister(Def, SplitReg, 0, *TRI); + break; + } + } + } +} + +/// Remove the incoming block from the Phis in a basic block. +static void removePhis(MachineBasicBlock *BB, MachineBasicBlock *Incoming) { + for (MachineInstr &MI : *BB) { + if (!MI.isPHI()) + break; + for (unsigned i = 1, e = MI.getNumOperands(); i != e; i += 2) + if (MI.getOperand(i + 1).getMBB() == Incoming) { + MI.RemoveOperand(i + 1); + MI.RemoveOperand(i); + break; + } + } +} + +/// Create branches from each prolog basic block to the appropriate epilog +/// block. These edges are needed if the loop ends before reaching the +/// kernel. +void ModuloScheduleExpander::addBranches(MachineBasicBlock &PreheaderBB, + MBBVectorTy &PrologBBs, + MachineBasicBlock *KernelBB, + MBBVectorTy &EpilogBBs, + ValueMapTy *VRMap) { + assert(PrologBBs.size() == EpilogBBs.size() && "Prolog/Epilog mismatch"); + MachineInstr *IndVar; + MachineInstr *Cmp; + if (TII->analyzeLoop(*Schedule.getLoop(), IndVar, Cmp)) + llvm_unreachable("Must be able to analyze loop!"); + MachineBasicBlock *LastPro = KernelBB; + MachineBasicBlock *LastEpi = KernelBB; + + // Start from the blocks connected to the kernel and work "out" + // to the first prolog and the last epilog blocks. + SmallVector PrevInsts; + unsigned MaxIter = PrologBBs.size() - 1; + unsigned LC = UINT_MAX; + unsigned LCMin = UINT_MAX; + for (unsigned i = 0, j = MaxIter; i <= MaxIter; ++i, --j) { + // Add branches to the prolog that go to the corresponding + // epilog, and the fall-thru prolog/kernel block. + MachineBasicBlock *Prolog = PrologBBs[j]; + MachineBasicBlock *Epilog = EpilogBBs[i]; + // We've executed one iteration, so decrement the loop count and check for + // the loop end. + SmallVector Cond; + // Check if the LOOP0 has already been removed. If so, then there is no need + // to reduce the trip count. + if (LC != 0) + LC = TII->reduceLoopCount(*Prolog, PreheaderBB, IndVar, *Cmp, Cond, + PrevInsts, j, MaxIter); + + // Record the value of the first trip count, which is used to determine if + // branches and blocks can be removed for constant trip counts. + if (LCMin == UINT_MAX) + LCMin = LC; + + unsigned numAdded = 0; + if (Register::isVirtualRegister(LC)) { + Prolog->addSuccessor(Epilog); + numAdded = TII->insertBranch(*Prolog, Epilog, LastPro, Cond, DebugLoc()); + } else if (j >= LCMin) { + Prolog->addSuccessor(Epilog); + Prolog->removeSuccessor(LastPro); + LastEpi->removeSuccessor(Epilog); + numAdded = TII->insertBranch(*Prolog, Epilog, nullptr, Cond, DebugLoc()); + removePhis(Epilog, LastEpi); + // Remove the blocks that are no longer referenced. + if (LastPro != LastEpi) { + LastEpi->clear(); + LastEpi->eraseFromParent(); + } + LastPro->clear(); + LastPro->eraseFromParent(); + } else { + numAdded = TII->insertBranch(*Prolog, LastPro, nullptr, Cond, DebugLoc()); + removePhis(Epilog, Prolog); + } + LastPro = Prolog; + LastEpi = Epilog; + for (MachineBasicBlock::reverse_instr_iterator I = Prolog->instr_rbegin(), + E = Prolog->instr_rend(); + I != E && numAdded > 0; ++I, --numAdded) + updateInstruction(&*I, false, j, 0, VRMap); + } +} + +/// Return true if we can compute the amount the instruction changes +/// during each iteration. Set Delta to the amount of the change. +bool ModuloScheduleExpander::computeDelta(MachineInstr &MI, unsigned &Delta) { + const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); + const MachineOperand *BaseOp; + int64_t Offset; + if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, TRI)) + return false; + + if (!BaseOp->isReg()) + return false; + + Register BaseReg = BaseOp->getReg(); + + MachineRegisterInfo &MRI = MF.getRegInfo(); + // Check if there is a Phi. If so, get the definition in the loop. + MachineInstr *BaseDef = MRI.getVRegDef(BaseReg); + if (BaseDef && BaseDef->isPHI()) { + BaseReg = getLoopPhiReg(*BaseDef, MI.getParent()); + BaseDef = MRI.getVRegDef(BaseReg); + } + if (!BaseDef) + return false; + + int D = 0; + if (!TII->getIncrementValue(*BaseDef, D) && D >= 0) + return false; + + Delta = D; + return true; +} + +/// Update the memory operand with a new offset when the pipeliner +/// generates a new copy of the instruction that refers to a +/// different memory location. +void ModuloScheduleExpander::updateMemOperands(MachineInstr &NewMI, + MachineInstr &OldMI, + unsigned Num) { + if (Num == 0) + return; + // If the instruction has memory operands, then adjust the offset + // when the instruction appears in different stages. + if (NewMI.memoperands_empty()) + return; + SmallVector NewMMOs; + for (MachineMemOperand *MMO : NewMI.memoperands()) { + // TODO: Figure out whether isAtomic is really necessary (see D57601). + if (MMO->isVolatile() || MMO->isAtomic() || + (MMO->isInvariant() && MMO->isDereferenceable()) || + (!MMO->getValue())) { + NewMMOs.push_back(MMO); + continue; + } + unsigned Delta; + if (Num != UINT_MAX && computeDelta(OldMI, Delta)) { + int64_t AdjOffset = Delta * Num; + NewMMOs.push_back( + MF.getMachineMemOperand(MMO, AdjOffset, MMO->getSize())); + } else { + NewMMOs.push_back( + MF.getMachineMemOperand(MMO, 0, MemoryLocation::UnknownSize)); + } + } + NewMI.setMemRefs(MF, NewMMOs); +} + +/// Clone the instruction for the new pipelined loop and update the +/// memory operands, if needed. +MachineInstr *ModuloScheduleExpander::cloneInstr(MachineInstr *OldMI, + unsigned CurStageNum, + unsigned InstStageNum) { + MachineInstr *NewMI = MF.CloneMachineInstr(OldMI); + // Check for tied operands in inline asm instructions. This should be handled + // elsewhere, but I'm not sure of the best solution. + if (OldMI->isInlineAsm()) + for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) { + const auto &MO = OldMI->getOperand(i); + if (MO.isReg() && MO.isUse()) + break; + unsigned UseIdx; + if (OldMI->isRegTiedToUseOperand(i, &UseIdx)) + NewMI->tieOperands(i, UseIdx); + } + updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum); + return NewMI; +} + +/// Clone the instruction for the new pipelined loop. If needed, this +/// function updates the instruction using the values saved in the +/// InstrChanges structure. +MachineInstr *ModuloScheduleExpander::cloneAndChangeInstr( + MachineInstr *OldMI, unsigned CurStageNum, unsigned InstStageNum) { + MachineInstr *NewMI = MF.CloneMachineInstr(OldMI); + auto It = InstrChanges.find(OldMI); + if (It != InstrChanges.end()) { + std::pair RegAndOffset = It->second; + unsigned BasePos, OffsetPos; + if (!TII->getBaseAndOffsetPosition(*OldMI, BasePos, OffsetPos)) + return nullptr; + int64_t NewOffset = OldMI->getOperand(OffsetPos).getImm(); + MachineInstr *LoopDef = findDefInLoop(RegAndOffset.first); + if (Schedule.getStage(LoopDef) > (signed)InstStageNum) + NewOffset += RegAndOffset.second * (CurStageNum - InstStageNum); + NewMI->getOperand(OffsetPos).setImm(NewOffset); + } + updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum); + return NewMI; +} + +/// Update the machine instruction with new virtual registers. This +/// function may change the defintions and/or uses. +void ModuloScheduleExpander::updateInstruction(MachineInstr *NewMI, + bool LastDef, + unsigned CurStageNum, + unsigned InstrStageNum, + ValueMapTy *VRMap) { + for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = NewMI->getOperand(i); + if (!MO.isReg() || !Register::isVirtualRegister(MO.getReg())) + continue; + Register reg = MO.getReg(); + if (MO.isDef()) { + // Create a new virtual register for the definition. + const TargetRegisterClass *RC = MRI.getRegClass(reg); + Register NewReg = MRI.createVirtualRegister(RC); + MO.setReg(NewReg); + VRMap[CurStageNum][reg] = NewReg; + if (LastDef) + replaceRegUsesAfterLoop(reg, NewReg, BB, MRI, LIS); + } else if (MO.isUse()) { + MachineInstr *Def = MRI.getVRegDef(reg); + // Compute the stage that contains the last definition for instruction. + int DefStageNum = Schedule.getStage(Def); + unsigned StageNum = CurStageNum; + if (DefStageNum != -1 && (int)InstrStageNum > DefStageNum) { + // Compute the difference in stages between the defintion and the use. + unsigned StageDiff = (InstrStageNum - DefStageNum); + // Make an adjustment to get the last definition. + StageNum -= StageDiff; + } + if (VRMap[StageNum].count(reg)) + MO.setReg(VRMap[StageNum][reg]); + } + } +} + +/// Return the instruction in the loop that defines the register. +/// If the definition is a Phi, then follow the Phi operand to +/// the instruction in the loop. +MachineInstr *ModuloScheduleExpander::findDefInLoop(unsigned Reg) { + SmallPtrSet Visited; + MachineInstr *Def = MRI.getVRegDef(Reg); + while (Def->isPHI()) { + if (!Visited.insert(Def).second) + break; + for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2) + if (Def->getOperand(i + 1).getMBB() == BB) { + Def = MRI.getVRegDef(Def->getOperand(i).getReg()); + break; + } + } + return Def; +} + +/// Return the new name for the value from the previous stage. +unsigned ModuloScheduleExpander::getPrevMapVal( + unsigned StageNum, unsigned PhiStage, unsigned LoopVal, unsigned LoopStage, + ValueMapTy *VRMap, MachineBasicBlock *BB) { + unsigned PrevVal = 0; + if (StageNum > PhiStage) { + MachineInstr *LoopInst = MRI.getVRegDef(LoopVal); + if (PhiStage == LoopStage && VRMap[StageNum - 1].count(LoopVal)) + // The name is defined in the previous stage. + PrevVal = VRMap[StageNum - 1][LoopVal]; + else if (VRMap[StageNum].count(LoopVal)) + // The previous name is defined in the current stage when the instruction + // order is swapped. + PrevVal = VRMap[StageNum][LoopVal]; + else if (!LoopInst->isPHI() || LoopInst->getParent() != BB) + // The loop value hasn't yet been scheduled. + PrevVal = LoopVal; + else if (StageNum == PhiStage + 1) + // The loop value is another phi, which has not been scheduled. + PrevVal = getInitPhiReg(*LoopInst, BB); + else if (StageNum > PhiStage + 1 && LoopInst->getParent() == BB) + // The loop value is another phi, which has been scheduled. + PrevVal = + getPrevMapVal(StageNum - 1, PhiStage, getLoopPhiReg(*LoopInst, BB), + LoopStage, VRMap, BB); + } + return PrevVal; +} + +/// Rewrite the Phi values in the specified block to use the mappings +/// from the initial operand. Once the Phi is scheduled, we switch +/// to using the loop value instead of the Phi value, so those names +/// do not need to be rewritten. +void ModuloScheduleExpander::rewritePhiValues(MachineBasicBlock *NewBB, + unsigned StageNum, + ValueMapTy *VRMap, + InstrMapTy &InstrMap) { + for (auto &PHI : BB->phis()) { + unsigned InitVal = 0; + unsigned LoopVal = 0; + getPhiRegs(PHI, BB, InitVal, LoopVal); + Register PhiDef = PHI.getOperand(0).getReg(); + + unsigned PhiStage = (unsigned)Schedule.getStage(MRI.getVRegDef(PhiDef)); + unsigned LoopStage = (unsigned)Schedule.getStage(MRI.getVRegDef(LoopVal)); + unsigned NumPhis = getStagesForPhi(PhiDef); + if (NumPhis > StageNum) + NumPhis = StageNum; + for (unsigned np = 0; np <= NumPhis; ++np) { + unsigned NewVal = + getPrevMapVal(StageNum - np, PhiStage, LoopVal, LoopStage, VRMap, BB); + if (!NewVal) + NewVal = InitVal; + rewriteScheduledInstr(NewBB, InstrMap, StageNum - np, np, &PHI, PhiDef, + NewVal); + } + } +} + +/// Rewrite a previously scheduled instruction to use the register value +/// from the new instruction. Make sure the instruction occurs in the +/// basic block, and we don't change the uses in the new instruction. +void ModuloScheduleExpander::rewriteScheduledInstr( + MachineBasicBlock *BB, InstrMapTy &InstrMap, unsigned CurStageNum, + unsigned PhiNum, MachineInstr *Phi, unsigned OldReg, unsigned NewReg, + unsigned PrevReg) { + bool InProlog = (CurStageNum < (unsigned)Schedule.getNumStages() - 1); + int StagePhi = Schedule.getStage(Phi) + PhiNum; + // Rewrite uses that have been scheduled already to use the new + // Phi register. + for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(OldReg), + EI = MRI.use_end(); + UI != EI;) { + MachineOperand &UseOp = *UI; + MachineInstr *UseMI = UseOp.getParent(); + ++UI; + if (UseMI->getParent() != BB) + continue; + if (UseMI->isPHI()) { + if (!Phi->isPHI() && UseMI->getOperand(0).getReg() == NewReg) + continue; + if (getLoopPhiReg(*UseMI, BB) != OldReg) + continue; + } + InstrMapTy::iterator OrigInstr = InstrMap.find(UseMI); + assert(OrigInstr != InstrMap.end() && "Instruction not scheduled."); + MachineInstr *OrigMI = OrigInstr->second; + int StageSched = Schedule.getStage(OrigMI); + int CycleSched = Schedule.getCycle(OrigMI); + unsigned ReplaceReg = 0; + // This is the stage for the scheduled instruction. + if (StagePhi == StageSched && Phi->isPHI()) { + int CyclePhi = Schedule.getCycle(Phi); + if (PrevReg && InProlog) + ReplaceReg = PrevReg; + else if (PrevReg && !isLoopCarried(*Phi) && + (CyclePhi <= CycleSched || OrigMI->isPHI())) + ReplaceReg = PrevReg; + else + ReplaceReg = NewReg; + } + // The scheduled instruction occurs before the scheduled Phi, and the + // Phi is not loop carried. + if (!InProlog && StagePhi + 1 == StageSched && !isLoopCarried(*Phi)) + ReplaceReg = NewReg; + if (StagePhi > StageSched && Phi->isPHI()) + ReplaceReg = NewReg; + if (!InProlog && !Phi->isPHI() && StagePhi < StageSched) + ReplaceReg = NewReg; + if (ReplaceReg) { + MRI.constrainRegClass(ReplaceReg, MRI.getRegClass(OldReg)); + UseOp.setReg(ReplaceReg); + } + } +} + +bool ModuloScheduleExpander::isLoopCarried(MachineInstr &Phi) { + if (!Phi.isPHI()) + return false; + unsigned DefCycle = Schedule.getCycle(&Phi); + int DefStage = Schedule.getStage(&Phi); + + unsigned InitVal = 0; + unsigned LoopVal = 0; + getPhiRegs(Phi, Phi.getParent(), InitVal, LoopVal); + MachineInstr *Use = MRI.getVRegDef(LoopVal); + if (!Use || Use->isPHI()) + return true; + unsigned LoopCycle = Schedule.getCycle(Use); + int LoopStage = Schedule.getStage(Use); + return (LoopCycle > DefCycle) || (LoopStage <= DefStage); +}