Index: include/llvm/CodeGen/Passes.h =================================================================== --- include/llvm/CodeGen/Passes.h +++ include/llvm/CodeGen/Passes.h @@ -370,6 +370,9 @@ /// and propagates register usage information of callee to caller /// if available with PysicalRegisterUsageInfo pass. FunctionPass *createRegUsageInfoPropPass(); + + /// This pass performs software pipelining on machine instructions. + extern char &MachinePipelinerID; } // End llvm namespace /// Target machine pass initializer for passes with dependencies. Use with Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -213,6 +213,7 @@ void initializeMachineLICMPass(PassRegistry&); void initializeMachineLoopInfoPass(PassRegistry&); void initializeMachineModuleInfoPass(PassRegistry&); +void initializeMachinePipelinerPass(PassRegistry&); void initializeMachinePostDominatorTreePass(PassRegistry&); void initializeMachineRegionInfoPassPass(PassRegistry&); void initializeMachineSchedulerPass(PassRegistry&); Index: include/llvm/Target/TargetInstrInfo.h =================================================================== --- include/llvm/Target/TargetInstrInfo.h +++ include/llvm/Target/TargetInstrInfo.h @@ -18,6 +18,7 @@ #include "llvm/ADT/SmallSet.h" #include "llvm/CodeGen/MachineCombinerPattern.h" #include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/MC/MCInstrInfo.h" #include "llvm/Support/BranchProbability.h" #include "llvm/Target/TargetRegisterInfo.h" @@ -546,6 +547,26 @@ llvm_unreachable("Target didn't implement TargetInstrInfo::InsertBranch!"); } + /// Analyze the loop code, return true if it cannot be understoo. Upon + /// success, this function returns false and returns information about the + /// induction variable and compare instruction used at the end. + virtual bool analyzeLoop(MachineLoop &L, MachineInstr *&IndVarInst, + MachineInstr *&CmpInst) const { + return true; + } + + /// Generate code to reduce the loop iteration by one and check if the loop is + /// finished. Return the value/register of the the new loop count. We need + /// this function when peeling off one or more iterations of a loop. This + /// function assumes the nth iteration is peeled first. + virtual unsigned reduceLoopCount(MachineBasicBlock &MBB, + MachineInstr *IndVar, MachineInstr *Cmp, + SmallVectorImpl &Cond, + SmallVectorImpl &PrevInsts, + unsigned Iter, unsigned MaxIter) const { + llvm_unreachable("Target didn't implement ReduceLoopCount"); + } + /// Delete the instruction OldInst and everything after it, replacing it with /// an unconditional branch to NewDest. This is used by the tail merging pass. virtual void ReplaceTailWithBranchTo(MachineBasicBlock::iterator Tail, @@ -1005,6 +1026,20 @@ return false; } + /// Return true if the instruction contains a base register and offset. If + /// true, the function also sets the operand position in the instruction + /// for the base register and offset. + virtual bool getBaseAndOffsetPosition(const MachineInstr *MI, + unsigned &BasePos, + unsigned &OffsetPos) const { + return false; + } + + /// If the instruction is an increment of a constant value, return the amount. + virtual bool getIncrementValue(const MachineInstr *MI, int &Value) const { + return false; + } + virtual bool enableClusterLoads() const { return false; } virtual bool enableClusterStores() const { return false; } @@ -1037,6 +1072,10 @@ /// Return the noop instruction to use for a noop. virtual void getNoopForMachoTarget(MCInst &NopInst) const; + /// Return true for post-incremented instructions. + virtual bool isPostIncrement(const MachineInstr* MI) const { + return false; + } /// Returns true if the instruction is already predicated. virtual bool isPredicated(const MachineInstr &MI) const { Index: lib/CodeGen/CMakeLists.txt =================================================================== --- lib/CodeGen/CMakeLists.txt +++ lib/CodeGen/CMakeLists.txt @@ -69,6 +69,7 @@ MachineModuleInfo.cpp MachineModuleInfoImpls.cpp MachinePassRegistry.cpp + MachinePipeliner.cpp MachinePostDominators.cpp MachineRegionInfo.cpp MachineRegisterInfo.cpp Index: lib/CodeGen/CodeGen.cpp =================================================================== --- lib/CodeGen/CodeGen.cpp +++ lib/CodeGen/CodeGen.cpp @@ -53,6 +53,7 @@ initializeMachineLICMPass(Registry); initializeMachineLoopInfoPass(Registry); initializeMachineModuleInfoPass(Registry); + initializeMachinePipelinerPass(Registry); initializeMachinePostDominatorTreePass(Registry); initializeMachineSchedulerPass(Registry); initializeMachineSinkingPass(Registry); Index: lib/CodeGen/MachinePipeliner.cpp =================================================================== --- /dev/null +++ lib/CodeGen/MachinePipeliner.cpp @@ -0,0 +1,3830 @@ +//===-- MachinePipeliner.cpp - Machine Software Pipeliner Pass ------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// An implementation of the Swing Modulo Scheduling (SMS) software pipeliner. +// +// Software pipelining (SWP) is an instruction scheduling technique for loops +// that overlap loop iterations and explioits ILP via a compiler transformation. +// +// Swing Modulo Scheduling is an implementation of software pipelining +// that generates schedules that are near optimal in terms of initiation +// interval, register requirements, and stage count. See the papers: +// +// "Swing Modulo Scheduling: A Lifetime-Sensitive Approach", by J. Llosa, +// A. Gonzalez, E. Ayguade, and M. Valero. In PACT '96 Processings of the 1996 +// Conference on Parallel Architectures and Compilation Techiniques. +// +// "Lifetime-Sensitive Modulo Scheduling in a Production Environment", by J. +// Llosa, E. Ayguade, A. Gonzalez, M. Valero, and J. Eckhardt. In IEEE +// Transactions on Computers, Vol. 50, No. 3, 2001. +// +// "An Implementation of Swing Modulo Scheduling With Extensions for +// Superblocks", by T. Lattner, Master's Thesis, University of Illinois at +// Urbana-Chambpain, 2005. +// +// +// The SMS algorithm consists of three main steps after computing the minimal +// initiation interval (MII). +// 1) Analyze the dependence graph and compute information about each +// instruction in the graph. +// 2) Order the nodes (instructions) by priority based upon the heuristics +// described in the algorithm. +// 3) Attempt to schedule the nodes in the specified order using the MII. +// +// This SMS implementation is a target-independent back-end pass. When enabled, +// the pass runs just prior to the register allocation pass, while the machine +// IR is in SSA form. If software pipelining is successful, then the original +// loop is replaced by the optimized loop. The optimized loop contains one or +// more prolog blocks, the pipelined kernel, and one or more epilog blocks. If +// the instructions cannot be scheduled in a given MII, we increase the MII by +// one and try again. +// +// The SMS implementation is an extension of the ScheduleDAGInstrs class. We +// represent loop carried dependences in the DAG as order edges to the Phi +// nodes. We also perform several passes over the DAG to eliminate unnecessary +// edges that inhibit the ability to pipeline. The implementation uses the +// DFAPacketizer class to compute the minimum initiation interval and the check +// where an instruction may be inserted in the pipelined schedule. +// +// In order for the SMS pass to work, several target specific hooks need to be +// implemented to get information about the loop structure and to rewrite +// instructions. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/MapVector.h" +#include "llvm/ADT/PriorityQueue.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/CodeGen/DFAPacketizer.h" +#include "llvm/CodeGen/LiveIntervalAnalysis.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/CodeGen/MachineLoopInfo.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/Passes.h" +#include "llvm/CodeGen/RegisterClassInfo.h" +#include "llvm/CodeGen/RegisterPressure.h" +#include "llvm/CodeGen/ScheduleDAGInstrs.h" +#include "llvm/MC/MCInstrItineraries.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" +#include +#include +#include + +using namespace llvm; + +#define DEBUG_TYPE "pipeliner" + +STATISTIC(NumTrytoPipeline, "Number of loops that we attempt to pipeline"); +STATISTIC(NumPipelined, "Number of loops software pipelined"); + +/// A command line option to turn software pipelining on or off. +cl::opt EnableSWP("enable-pipeliner", cl::Hidden, cl::init(true), + cl::ZeroOrMore, cl::desc("Enable Software Pipelining")); + +/// A command line option to enable SWP at -Os. +static cl::opt EnableSWPOptSize("enable-pipeliner-opt-size", + cl::desc("Enable SWP at Os."), cl::Hidden, + cl::init(false)); + +/// A command line argument to limit minimum initial interval for pipelining. +static cl::opt SwpMaxMii("pipeliner-max-mii", + cl::desc("Size limit for the the MII."), + cl::Hidden, cl::init(27)); + +/// A command line argument to limit the number of stages in the pipeline. +static cl::opt + SwpMaxStages("pipeliner-max-stages", + cl::desc("Maximum stages allowed in the generated scheduled."), + cl::Hidden, cl::init(3)); + +/// A command line option to disable the pruning of chain dependences due to +/// an unrelated Phi. +static cl::opt + SwpPruneDeps("pipeliner-prune-deps", + cl::desc("Prune dependences between unrelated Phi nodes."), + cl::Hidden, cl::init(true)); + +/// A command line option to disable the pruning of loop carried order +/// dependences. +static cl::opt + SwpPruneLoopCarried("pipeliner-prune-loop-carried", + cl::desc("Prune loop carried order dependences."), + cl::Hidden, cl::init(true)); + +#ifndef NDEBUG +static cl::opt SwpLoopLimit("pipeliner-max", cl::Hidden, cl::init(-1)); +#endif + +static cl::opt SwpIgnoreRecMII("pipeliner-ignore-recmii", + cl::ReallyHidden, cl::init(false), + cl::ZeroOrMore, cl::desc("Ignore RecMII")); + +namespace { + +class NodeSet; +class SMSchedule; +class SwingSchedulerDAG; + +/// The main class in the implementation of the target independent +/// software pipeliner pass. +class MachinePipeliner : public MachineFunctionPass { +public: + MachineFunction *MF = nullptr; + const MachineLoopInfo *MLI = nullptr; + const MachineDominatorTree *MDT = nullptr; + const InstrItineraryData *InstrItins; + const TargetInstrInfo *TII = nullptr; + RegisterClassInfo RegClassInfo; + +#ifndef NDEBUG + static int NumTries; +#endif + /// Cache the target analysis information about the loop. + struct LoopInfo { + MachineBasicBlock *TBB = nullptr; + MachineBasicBlock *FBB = nullptr; + SmallVector BrCond; + MachineInstr *LoopInductionVar = nullptr; + MachineInstr *LoopCompare = nullptr; + }; + LoopInfo LI; + + static char ID; + MachinePipeliner() : MachineFunctionPass(ID) { + initializeMachinePipelinerPass(*PassRegistry::getPassRegistry()); + } + + virtual bool runOnMachineFunction(MachineFunction &MF); + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); + AU.addPreserved(); + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + MachineFunctionPass::getAnalysisUsage(AU); + } + +private: + bool canPipelineLoop(MachineLoop &L); + bool scheduleLoop(MachineLoop &L); + bool swingModuloScheduler(MachineLoop &L); +}; + +/// This class builds the dependence graph for the instructions in a loop, +/// and attempts to schedule the instructions using the SMS algorithm. +class SwingSchedulerDAG : public ScheduleDAGInstrs { + MachinePipeliner &Pass; + /// The minimum initiation interval between iterations for this schedule. + unsigned MII; + /// Set to true if a valid pipelined schedule is found for the loop. + bool Scheduled; + MachineLoop &Loop; + LiveIntervals &LIS; + const RegisterClassInfo &RegClassInfo; + + /// A toplogical ordering of the SUnits, which is needed for changing + /// dependences and iterating over the SUnits. + ScheduleDAGTopologicalSort Topo; + + struct NodeInfo { + int ASAP; + int ALAP; + NodeInfo() : ASAP(0), ALAP(0) {} + }; + /// Computed properties for each node in the graph. + std::vector ScheduleInfo; + + enum OrderKind { BottomUp = 0, TopDown = 1 }; + /// Computed node ordering for scheduling. + SetVector NodeOrder; + + typedef SmallVector NodeSetType; + typedef DenseMap ValueMapTy; + typedef SmallVectorImpl MBBVectorTy; + typedef DenseMap InstrMapTy; + + /// Instructions to change when emitting the final schedule. + DenseMap> InstrChanges; + + /// We may create a new instruction, so remember it because it + /// must be deleted when the pass is finished. + SmallPtrSet NewMIs; + + /// Helper class to implement Johnson's circuit finding algorithm. + class Circuits { + std::vector &SUnits; + SetVector Stack; + BitVector Blocked; + SmallVector, 10> B; + SmallVector, 16> AdjK; + unsigned NumPaths; + static unsigned MaxPaths; + + public: + Circuits(std::vector &SUs) + : SUnits(SUs), Stack(), Blocked(SUs.size()), B(SUs.size()), + AdjK(SUs.size()) {} + /// Reset the data structures used in the circuit algorithm. + void reset() { + Stack.clear(); + Blocked.reset(); + B.assign(SUnits.size(), SmallPtrSet()); + NumPaths = 0; + } + void createAdjacencyStructure(SwingSchedulerDAG *DAG); + bool circuit(int V, int S, NodeSetType &NodeSets, bool HasBackedge = false); + void unblock(int U); + }; + +public: + SwingSchedulerDAG(MachinePipeliner &P, MachineLoop &L, LiveIntervals &lis, + const RegisterClassInfo &rci) + : ScheduleDAGInstrs(*P.MF, P.MLI, false), Pass(P), MII(0), + Scheduled(false), Loop(L), LIS(lis), RegClassInfo(rci), + Topo(SUnits, &ExitSU) {} + + void schedule(); + void finishBlock(); + + /// Return true if the loop kernel has been scheduled. + bool hasNewSchedule() { return Scheduled; } + + /// Return the earliest time an instruction may be scheduled. + int getASAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ASAP; } + + /// Return the latest time an instruction my be scheduled. + int getALAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ALAP; } + + /// The mobility function, which the the number of slots in which + /// an instruction may be scheduled. + int getMOV(SUnit *Node) { return getALAP(Node) - getASAP(Node); } + + /// The depth, in the dependence graph, for a node. + int getDepth(SUnit *Node) { return Node->getDepth(); } + + /// The height, in the dependence graph, for a node. + int getHeight(SUnit *Node) { return Node->getHeight(); } + + /// Return true if the dependence is a back-edge in the data dependence graph. + /// Since the DAG doesn't contain cycles, we represent a cycle in the graph + /// using an anti dependence from a Phi to an instruction. + bool isBackedge(SUnit *Source, const SDep &Dep) { + if (Dep.getKind() != SDep::Anti) + return false; + return Source->getInstr()->isPHI() || Dep.getSUnit()->getInstr()->isPHI(); + } + + /// Return true if the dependence is an order dependence between non-Phis. + static bool isOrder(SUnit *Source, const SDep &Dep) { + if (Dep.getKind() != SDep::Order) + return false; + return (!Source->getInstr()->isPHI() && + !Dep.getSUnit()->getInstr()->isPHI()); + } + + bool isLoopCarriedOrder(SUnit *Source, const SDep &Dep, bool isSucc = true); + + /// The latency of the dependence. + unsigned getLatency(SUnit *Source, const SDep &Dep) { + // Anti dependences represent recurrences, so use the latency of the + // instruction on the back-edge. + if (Dep.getKind() == SDep::Anti) { + if (Source->getInstr()->isPHI()) + return Dep.getSUnit()->Latency; + if (Dep.getSUnit()->getInstr()->isPHI()) + return Source->Latency; + return Dep.getLatency(); + } + return Dep.getLatency(); + } + + /// The distance function, which indicates that operation V of iteration I + /// depends on operations U of iteration I-distance. + unsigned getDistance(SUnit *U, SUnit *V, const SDep &Dep) { + // Instructions that feed a Phi have a distance of 1. Computing larger + // values for arrays requires data dependence information. + if (V->getInstr()->isPHI() && Dep.getKind() == SDep::Anti) + return 1; + return 0; + } + + /// Set the Minimum Initiation Interval for this schedule attempt. + void setMII(unsigned mii) { MII = mii; } + + MachineInstr *applyInstrChange(MachineInstr *MI, SMSchedule &Schedule, + bool UpdateDAG = false); + + /// Return the new base register that was stored away for the changed + /// instruction. + unsigned getInstrBaseReg(SUnit *SU) { + DenseMap>::iterator It = + InstrChanges.find(SU); + if (It != InstrChanges.end()) + return It->second.first; + return 0; + } + +private: + void addLoopCarriedDependences(AliasAnalysis *AA); + void updatePhiDependences(); + void changeDependences(); + unsigned calculateResMII(); + unsigned calculateRecMII(NodeSetType &RecNodeSets); + void findCircuits(NodeSetType &NodeSets); + void fuseRecs(NodeSetType &NodeSets); + void removeDuplicateNodes(NodeSetType &NodeSets); + void computeNodeFunctions(NodeSetType &NodeSets); + void registerPressureFilter(NodeSetType &NodeSets); + void colocateNodeSets(NodeSetType &NodeSets); + void checkNodeSets(NodeSetType &NodeSets); + void groupRemainingNodes(NodeSetType &NodeSets); + void addConnectedNodes(SUnit *SU, NodeSet &NewSet, + SetVector &NodesAdded); + void computeNodeOrder(NodeSetType &NodeSets); + 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(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 InstStageNum, + SMSchedule &Schedule, ValueMapTy *VRMap); + MachineInstr *findDefInLoop(unsigned Reg); + unsigned getPrevMapVal(unsigned StageNum, unsigned PhiStage, unsigned LoopVal, + 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); +}; + +/// A NodeSet contains a set of SUnit DAG nodes with additional information +/// that assigns a priority to the set. +class NodeSet { + SetVector Nodes; + bool HasRecurrence; + unsigned RecMII = 0; + int MaxMOV = 0; + int MaxDepth = 0; + unsigned Colocate = 0; + SUnit *ExceedPressure = nullptr; + +public: + typedef SetVector::const_iterator iterator; + + NodeSet() : Nodes(), HasRecurrence(false) {} + + NodeSet(iterator S, iterator E) : Nodes(S, E), HasRecurrence(true) {} + + bool insert(SUnit *SU) { return Nodes.insert(SU); } + + void insert(iterator S, iterator E) { return Nodes.insert(S, E); } + + template bool remove_if(UnaryPredicate P) { + return Nodes.remove_if(P); + } + + unsigned count(SUnit *SU) const { return Nodes.count(SU); } + + bool hasRecurrence() { return HasRecurrence; }; + + unsigned size() const { return Nodes.size(); } + + bool empty() const { return Nodes.empty(); } + + SUnit *getNode(unsigned i) const { return Nodes[i]; }; + + void setRecMII(unsigned mii) { RecMII = mii; }; + + void setColocate(unsigned c) { Colocate = c; }; + + void setExceedPressure(SUnit *SU) { ExceedPressure = SU; } + + bool isExceedSU(SUnit *SU) { return ExceedPressure == SU; } + + int compareRecMII(NodeSet &RHS) { return RecMII - RHS.RecMII; } + + int getRecMII() { return RecMII; } + + /// Summarize node functions for the entire node set. + void computeNodeSetInfo(SwingSchedulerDAG *SSD) { + for (SUnit *SU : *this) { + MaxMOV = std::max(MaxMOV, SSD->getMOV(SU)); + MaxDepth = std::max(MaxDepth, SSD->getDepth(SU)); + } + } + + void clear() { + Nodes.clear(); + RecMII = 0; + HasRecurrence = false; + MaxMOV = 0; + MaxDepth = 0; + Colocate = 0; + ExceedPressure = nullptr; + } + + operator SetVector &() { return Nodes; } + + /// Sort the node sets by importance. First, rank them by recurrence MII, + /// then by mobility (least mobile done first), and finally by depth. + /// Each node set may contain a colocate value which is used as the first + /// tie breaker, if it's set. + bool operator>(const NodeSet &RHS) const { + if (RecMII == RHS.RecMII) { + if (Colocate != 0 && RHS.Colocate != 0 && Colocate != RHS.Colocate) + return Colocate < RHS.Colocate; + if (MaxMOV == RHS.MaxMOV) + return MaxDepth > RHS.MaxDepth; + return MaxMOV < RHS.MaxMOV; + } + return RecMII > RHS.RecMII; + } + + bool operator==(const NodeSet &RHS) const { + return RecMII == RHS.RecMII && MaxMOV == RHS.MaxMOV && + MaxDepth == RHS.MaxDepth; + } + + bool operator!=(const NodeSet &RHS) const { return !operator==(RHS); } + + iterator begin() { return Nodes.begin(); } + iterator end() { return Nodes.end(); } + + void print(raw_ostream &os) const { + os << "Num nodes " << size() << " rec " << RecMII << " mov " << MaxMOV + << " depth " << MaxDepth << " col " << Colocate << "\n"; + for (const auto &I : Nodes) + os << " SU(" << I->NodeNum << ") " << *(I->getInstr()); + os << "\n"; + } + + void dump() const { print(dbgs()); } +}; + +/// This class repesents the scheduled code. The main data structure is a +/// map from scheduled cycle to instructions. During scheduling, the +/// data structure explicitly represents all stages/iterations. When +/// the algorithm finshes, the schedule is collapsed into a single stage, +/// which represents instructions from different loop iterations. +/// +/// The SMS algorithm allows negative values for cycles, so the first cycle +/// in the schedule is the smallest cycle value. +class SMSchedule { +private: + /// Map from execution cycle to instructions. + DenseMap> ScheduledInstrs; + + /// 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; + + /// Keep track of the last cycle value in the schedule. + int LastCycle; + + /// The initiation interval (II) for the schedule. + int InitiationInterval; + + /// Target machine information. + const TargetSubtargetInfo &ST; + + /// Virtual register information. + MachineRegisterInfo &MRI; + + DFAPacketizer *Resources; + +public: + SMSchedule(MachineFunction *mf) + : ST(mf->getSubtarget()), MRI(mf->getRegInfo()), + Resources(ST.getInstrInfo()->CreateTargetScheduleState(ST)) { + FirstCycle = 0; + LastCycle = 0; + InitiationInterval = 0; + } + + ~SMSchedule() { + ScheduledInstrs.clear(); + InstrToCycle.clear(); + RegToStageDiff.clear(); + delete Resources; + } + + void reset() { + ScheduledInstrs.clear(); + InstrToCycle.clear(); + RegToStageDiff.clear(); + FirstCycle = 0; + LastCycle = 0; + InitiationInterval = 0; + } + + /// Set the initiation interval for this schedule. + void setInitiationInterval(int ii) { InitiationInterval = ii; } + + /// Return the first cycle in the completed schedule. This + /// can be a negative value. + int getFirstCycle() const { return FirstCycle; } + + /// Return the last cycle in the finalized schedule. + int getFinalCycle() const { return FirstCycle + InitiationInterval - 1; } + + /// Return the cycle of the earliest scheduled instruction in the dependence + /// chain. + int earliestCycleInChain(const SDep &Dep); + + /// Return the cycle of the latest scheduled instruction in the dependence + /// chain. + int latestCycleInChain(const SDep &Dep); + + void computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart, + int *MinEnd, int *MaxStart, int II, SwingSchedulerDAG *DAG); + bool insert(SUnit *SU, int StartCycle, int EndCycle, int II); + + /// Iterators for the cycle to instruction map. + typedef DenseMap>::iterator sched_iterator; + typedef DenseMap>::const_iterator + const_sched_iterator; + + /// Return true if the instruction is scheduled at the specified stage. + bool isScheduledAtStage(SUnit *SU, unsigned StageNum) { + return (stageScheduled(SU) == (int)StageNum); + } + + /// Return the stage for a scheduled instruction. Return -1 if + /// the instruction has not been scheduled. + int stageScheduled(SUnit *SU) const { + std::map::const_iterator it = InstrToCycle.find(SU); + if (it == InstrToCycle.end()) + return -1; + return (it->second - FirstCycle) / InitiationInterval; + } + + /// Return the cycle for a scheduled instruction. This function normalizes + /// the first cycle to be 0. + unsigned cycleScheduled(SUnit *SU) const { + std::map::const_iterator it = InstrToCycle.find(SU); + assert(it != InstrToCycle.end() && "Instruction hasn't been scheduled."); + return (it->second - FirstCycle) % InitiationInterval; + } + + /// Return the maximum stage count needed for this schedule. + unsigned getMaxStageCount() { + 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]; + } + + void finalizeSchedule(SwingSchedulerDAG *SSD); + bool orderDependence(SwingSchedulerDAG *SSD, SUnit *SU, + std::deque &Insts); + bool isLoopCarried(SwingSchedulerDAG *SSD, MachineInstr *Phi); + bool isLoopCarriedDefOfUse(SwingSchedulerDAG *SSD, MachineInstr *Inst, + MachineOperand &MO); + void print(raw_ostream &os) const; + void dump() const; +}; + +} // end anonymous namespace + +unsigned SwingSchedulerDAG::Circuits::MaxPaths = 5; +char MachinePipeliner::ID = 0; +#ifndef NDEBUG +int MachinePipeliner::NumTries = 0; +#endif +char &llvm::MachinePipelinerID = MachinePipeliner::ID; +INITIALIZE_PASS_BEGIN(MachinePipeliner, "pipeliner", + "Modulo Software Pipelining", false, false) +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) +INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) +INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) +INITIALIZE_PASS_DEPENDENCY(LiveIntervals) +INITIALIZE_PASS_END(MachinePipeliner, "pipeliner", + "Modulo Software Pipelining", false, false) + +/// The "main" function for implementing Swing Modulo Scheduling. +bool MachinePipeliner::runOnMachineFunction(MachineFunction &mf) { + if (skipFunction(*mf.getFunction())) + return false; + + if (!EnableSWP) + return false; + + if (mf.getFunction()->getAttributes().hasAttribute( + AttributeSet::FunctionIndex, Attribute::OptimizeForSize) && + !EnableSWPOptSize.getPosition()) + return false; + + MF = &mf; + MLI = &getAnalysis(); + MDT = &getAnalysis(); + TII = MF->getSubtarget().getInstrInfo(); + RegClassInfo.runOnMachineFunction(*MF); + + for (auto &L : *MLI) + scheduleLoop(*L); + + return false; +} + +/// Attempt to perform the SMS algorithm on the specified loop. This function is +/// the main entry point for the algorithm. The function identifies candidate +/// loops, calculates the minimum initiation interval, and attempts to schedule +/// the loop. +bool MachinePipeliner::scheduleLoop(MachineLoop &L) { + bool Changed = false; + for (auto &InnerLoop : L) + Changed |= scheduleLoop(*InnerLoop); + +#ifndef NDEBUG + // Stop trying after reaching the limit (if any). + int Limit = SwpLoopLimit; + if (Limit >= 0) { + if (NumTries >= SwpLoopLimit) + return Changed; + NumTries++; + } +#endif + + if (!canPipelineLoop(L)) + return Changed; + + ++NumTrytoPipeline; + + Changed = swingModuloScheduler(L); + + return Changed; +} + +/// Return true if the loop can be software pipelined. The algorithm is +/// restricted to loops with a single basic block. Make sure that the +/// branch in the loop can be analyzed. +bool MachinePipeliner::canPipelineLoop(MachineLoop &L) { + if (L.getNumBlocks() != 1) + return false; + + // Check if the branch can't be understood because we can't do pipelining + // if that's the case. + LI.TBB = nullptr; + LI.FBB = nullptr; + LI.BrCond.clear(); + if (TII->AnalyzeBranch(*L.getHeader(), LI.TBB, LI.FBB, LI.BrCond)) + return false; + + LI.LoopInductionVar = nullptr; + LI.LoopCompare = nullptr; + if (TII->analyzeLoop(L, LI.LoopInductionVar, LI.LoopCompare)) + return false; + + if (!L.getLoopPreheader()) + return false; + + // If any of the Phis contain subregs, then we can't pipeline + // because we don't know how to maintain subreg information in the + // VMap structure. + MachineBasicBlock *MBB = L.getHeader(); + for (MachineBasicBlock::iterator BBI = MBB->instr_begin(), + BBE = MBB->getFirstNonPHI(); + BBI != BBE; ++BBI) + for (unsigned i = 1; i != BBI->getNumOperands(); i += 2) + if (BBI->getOperand(i).getSubReg() != 0) + return false; + + return true; +} + +/// The SMS algorithm consists of the following main steps: +/// 1. Computation and analysis of the dependence graph. +/// 2. Ordering of the nodes (instructions). +/// 3. Attempt to Schedule the loop. +bool MachinePipeliner::swingModuloScheduler(MachineLoop &L) { + assert(L.getBlocks().size() == 1 && "SMS works on single blocks only."); + + SwingSchedulerDAG SMS(*this, L, getAnalysis(), RegClassInfo); + + MachineBasicBlock *MBB = L.getHeader(); + // The kernel should not include any terminator instructions. These + // will be added back later. + SMS.startBlock(MBB); + + // Compute the number of 'real' instructions in the basic block by + // ignoring terminators. + unsigned size = MBB->size(); + for (MachineBasicBlock::iterator I = MBB->getFirstTerminator(), + E = MBB->instr_end(); + I != E; ++I, --size) + ; + + SMS.enterRegion(MBB, MBB->begin(), MBB->getFirstTerminator(), size); + SMS.schedule(); + SMS.exitRegion(); + + SMS.finishBlock(); + return SMS.hasNewSchedule(); +} + +/// We override the schedule function in ScheduleDAGInstrs to implement the +/// scheduling part of the Swing Modulo Scheduling algorithm. +void SwingSchedulerDAG::schedule() { + AliasAnalysis *AA = &Pass.getAnalysis().getAAResults(); + buildSchedGraph(AA); + addLoopCarriedDependences(AA); + updatePhiDependences(); + Topo.InitDAGTopologicalSorting(); + changeDependences(); + DEBUG({ + for (unsigned su = 0, e = SUnits.size(); su != e; ++su) + SUnits[su].dumpAll(this); + }); + + NodeSetType NodeSets; + findCircuits(NodeSets); + + // Calculate the MII. + unsigned ResMII = calculateResMII(); + unsigned RecMII = calculateRecMII(NodeSets); + + fuseRecs(NodeSets); + + // This flag is used for testing and can cause correctness problems. + if (SwpIgnoreRecMII) + RecMII = 0; + + MII = std::max(ResMII, RecMII); + DEBUG(dbgs() << "MII = " << MII << " (rec=" << RecMII << ", res=" << ResMII + << ")\n"); + + // Can't schedule a loop without a valid MII. + if (MII == 0) + return; + + // Don't pipeline large loops. + if (SwpMaxMii != -1 && (int)MII > SwpMaxMii) + return; + + computeNodeFunctions(NodeSets); + + registerPressureFilter(NodeSets); + + colocateNodeSets(NodeSets); + + checkNodeSets(NodeSets); + + DEBUG({ + for (auto &I : NodeSets) { + dbgs() << " Rec NodeSet "; + I.dump(); + } + }); + + std::sort(NodeSets.begin(), NodeSets.end(), std::greater()); + + groupRemainingNodes(NodeSets); + + removeDuplicateNodes(NodeSets); + + DEBUG({ + for (auto &I : NodeSets) { + dbgs() << " NodeSet "; + I.dump(); + } + }); + + computeNodeOrder(NodeSets); + + SMSchedule Schedule(Pass.MF); + Scheduled = schedulePipeline(Schedule); + + if (!Scheduled) + return; + + unsigned numStages = Schedule.getMaxStageCount(); + // No need to generate pipeline if there are no overlapped iterations. + if (numStages == 0) + return; + + // Check that the maximum stage count is less than user-defined limit. + if (SwpMaxStages > -1 && (int)numStages > SwpMaxStages) + return; + + generatePipelinedLoop(Schedule); + ++NumPipelined; +} + +/// Clean up after the software pipeliner runs. +void SwingSchedulerDAG::finishBlock() { + for (MachineInstr *I : NewMIs) + MF.DeleteMachineInstr(I); + NewMIs.clear(); + + // Call the superclass. + ScheduleDAGInstrs::finishBlock(); +} + +/// 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 if (Phi->getOperand(i + 1).getMBB() == Loop) + 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 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; +} + +/// Return true if SUb can be reached from SUa following the chain edges. +static bool isSuccOrder(SUnit *SUa, SUnit *SUb) { + SmallPtrSet Visited; + SmallVector Worklist; + Worklist.push_back(SUa); + while (!Worklist.empty()) { + const SUnit *SU = Worklist.pop_back_val(); + for (auto &SI : SU->Succs) { + SUnit *SuccSU = SI.getSUnit(); + if (SI.getKind() == SDep::Order) { + if (Visited.count(SuccSU)) + continue; + if (SuccSU == SUb) + return true; + Worklist.push_back(SuccSU); + Visited.insert(SuccSU); + } + } + } + return false; +} + +/// Return true if the instruction causes a chain between memory +/// references before and after it. +static bool isDependenceBarrier(MachineInstr *MI, AliasAnalysis *AA) { + return MI->isCall() || MI->hasUnmodeledSideEffects() || + (MI->hasOrderedMemoryRef() && + (!MI->mayLoad() || !MI->isInvariantLoad(AA))); +} + +/// Return the underlying objects for the memory references of an instruction. +/// This function calls the code in ValueTracking, but first checks that the +/// instruction has a memory operand. +static void getUnderlyingObjects(MachineInstr *MI, + SmallVectorImpl &Objs, + const DataLayout &DL) { + if (!MI->hasOneMemOperand()) + return; + MachineMemOperand *MM = *MI->memoperands_begin(); + if (!MM->getValue()) + return; + GetUnderlyingObjects(const_cast(MM->getValue()), Objs, DL); +} + +/// Add a chain edge between a load and store if the store can be an +/// alias of the load on a subsequent iteration, i.e., a loop carried +/// dependence. This code is very similar to the code in ScheduleDAGInstrs +/// but that code doesn't create loop carried dependences. +void SwingSchedulerDAG::addLoopCarriedDependences(AliasAnalysis *AA) { + MapVector> PendingLoads; + for (auto &SU : SUnits) { + MachineInstr *MI = SU.getInstr(); + if (isDependenceBarrier(MI, AA)) + PendingLoads.clear(); + else if (MI->mayLoad()) { + SmallVector Objs; + getUnderlyingObjects(MI, Objs, MF.getDataLayout()); + for (auto V : Objs) { + SmallVector &SUs = PendingLoads[V]; + SUs.push_back(&SU); + } + } else if (MI->mayStore()) { + SmallVector Objs; + getUnderlyingObjects(MI, Objs, MF.getDataLayout()); + for (auto V : Objs) { + MapVector>::iterator I = + PendingLoads.find(V); + if (I == PendingLoads.end()) + continue; + for (auto Load : I->second) { + if (isSuccOrder(Load, &SU)) + continue; + MachineInstr *LdMI = Load->getInstr(); + // First, perform the cheaper check that compares the base register. + // If they are the same and the load offset is less than the store + // offset, then mark the dependence as loop carried potentially. + unsigned BaseReg1, BaseReg2; + int64_t Offset1, Offset2; + if (!TII->getMemOpBaseRegImmOfs(LdMI, BaseReg1, Offset1, TRI) || + !TII->getMemOpBaseRegImmOfs(MI, BaseReg2, Offset2, TRI)) + continue; + if (BaseReg1 == BaseReg2 && (int)Offset1 < (int)Offset2) { + assert(TII->areMemAccessesTriviallyDisjoint(LdMI, MI, AA) && + "What happened to the chain edge?"); + SU.addPred(SDep(Load, SDep::Barrier)); + continue; + } + // Second, the more expensive check that uses alias analysis on the + // base registers. If they alias, and the load offset is less than + // the store offset, the mark the dependence as loop carried. + if (!AA) + continue; + MachineMemOperand *MMO1 = *LdMI->memoperands_begin(); + MachineMemOperand *MMO2 = *MI->memoperands_begin(); + if (!MMO1->getValue() || !MMO2->getValue()) + continue; + if (MMO1->getValue() == MMO2->getValue() && + MMO1->getOffset() <= MMO2->getOffset()) { + SU.addPred(SDep(Load, SDep::Barrier)); + continue; + } + AliasResult AAResult = AA->alias( + MemoryLocation(MMO1->getValue(), MemoryLocation::UnknownSize, + MMO1->getAAInfo()), + MemoryLocation(MMO2->getValue(), MemoryLocation::UnknownSize, + MMO2->getAAInfo())); + + if (AAResult != NoAlias) + SU.addPred(SDep(Load, SDep::Barrier)); + } + } + } + } +} + +/// Update the phi dependences to the DAG because ScheduleDAGInstrs no longer +/// processes dependences for PHIs. This function adds true dependences +/// from a PHI to a use, and a loop carried dependence from the use to the +/// PHI. The loop carried dependence is represented as an anti dependence +/// edge. This function also removes chain dependences between unrelated +/// PHIs. +void SwingSchedulerDAG::updatePhiDependences() { + SmallVector RemoveDeps; + const TargetSubtargetInfo &ST = MF.getSubtarget(); + + // Iterate over each DAG node. + for (SUnit &I : SUnits) { + RemoveDeps.clear(); + // Set to true if the instruction has an operand defined by a Phi. + unsigned HasPhiUse = 0; + unsigned HasPhiDef = 0; + MachineInstr *MI = I.getInstr(); + // Iterate over each operand, and we process the definitions. + for (MachineInstr::mop_iterator MOI = MI->operands_begin(), + MOE = MI->operands_end(); + MOI != MOE; ++MOI) { + if (!MOI->isReg()) + continue; + unsigned Reg = MOI->getReg(); + if (MOI->isDef()) { + // If the register is used by a Phi, then create an anti dependence. + for (MachineRegisterInfo::use_instr_iterator + UI = MRI.use_instr_begin(Reg), + UE = MRI.use_instr_end(); + UI != UE; ++UI) { + MachineInstr *UseMI = &*UI; + SUnit *SU = getSUnit(UseMI); + if (SU != 0 && UseMI->isPHI()) { + if (!MI->isPHI()) { + SDep Dep(SU, SDep::Anti, Reg); + I.addPred(Dep); + } else { + HasPhiDef = Reg; + // Add a chain edge to a dependent Phi that isn't an existing + // predecessor. + if (SU->NodeNum < I.NodeNum && !I.isPred(SU)) + I.addPred(SDep(SU, SDep::Barrier)); + } + } + } + } else if (MOI->isUse()) { + // If the register is defined by a Phi, then create a true dependence. + MachineInstr *DefMI = MRI.getUniqueVRegDef(Reg); + if (DefMI == 0) + continue; + SUnit *SU = getSUnit(DefMI); + if (SU != 0 && DefMI->isPHI()) { + if (!MI->isPHI()) { + SDep Dep(SU, SDep::Data, Reg); + Dep.setLatency(0); + ST.adjustSchedDependency(SU, &I, Dep); + I.addPred(Dep); + } else { + HasPhiUse = Reg; + // Add a chain edge to a dependent Phi that isn't an existing + // predecessor. + if (SU->NodeNum < I.NodeNum && !I.isPred(SU)) + I.addPred(SDep(SU, SDep::Barrier)); + } + } + } + } + // Remove order dependences from an unrelated Phi. + if (!SwpPruneDeps) + continue; + for (auto &PI : I.Preds) { + MachineInstr *PMI = PI.getSUnit()->getInstr(); + if (PMI->isPHI() && PI.getKind() == SDep::Order) { + if (I.getInstr()->isPHI()) { + if (PMI->getOperand(0).getReg() == HasPhiUse) + continue; + if (getLoopPhiReg(PMI, PMI->getParent()) == HasPhiDef) + continue; + } + RemoveDeps.push_back(PI); + } + } + for (int i = 0, e = RemoveDeps.size(); i != e; ++i) + I.removePred(RemoveDeps[i]); + } +} + +/// Iterate over each DAG node and see if we can change any dependences +/// in order to reduce the recurrence MII. +void SwingSchedulerDAG::changeDependences() { + // See if an instruction can use a value from the previous iteration. + // If so, we update the base and offset of the instruction and change + // the dependences. + for (SUnit &I : SUnits) { + unsigned BasePos = 0, OffsetPos = 0, NewBase = 0; + int64_t NewOffset = 0; + if (!canUseLastOffsetValue(I.getInstr(), BasePos, OffsetPos, NewBase, + NewOffset)) + continue; + + // Get the MI and SUnit for the instruction that defines the original base. + unsigned OrigBase = I.getInstr()->getOperand(BasePos).getReg(); + MachineInstr *DefMI = MRI.getUniqueVRegDef(OrigBase); + if (!DefMI) + continue; + SUnit *DefSU = getSUnit(DefMI); + if (!DefSU) + continue; + // Get the MI and SUnit for the instruction that defins the new base. + MachineInstr *LastMI = MRI.getUniqueVRegDef(NewBase); + if (!LastMI) + continue; + SUnit *LastSU = getSUnit(LastMI); + if (!LastSU) + continue; + + if (Topo.IsReachable(&I, LastSU)) + continue; + + // Remove the dependence. The value now depends on a prior iteration. + SmallVector Deps; + for (SUnit::pred_iterator P = I.Preds.begin(), E = I.Preds.end(); P != E; + ++P) + if (P->getSUnit() == DefSU) + Deps.push_back(*P); + for (int i = 0, e = Deps.size(); i != e; i++) { + Topo.RemovePred(&I, Deps[i].getSUnit()); + I.removePred(Deps[i]); + } + // Remove the chain dependence between the instructions. + Deps.clear(); + for (auto &P : LastSU->Preds) + if (P.getSUnit() == &I && P.getKind() == SDep::Order) + Deps.push_back(P); + for (int i = 0, e = Deps.size(); i != e; i++) { + Topo.RemovePred(LastSU, Deps[i].getSUnit()); + LastSU->removePred(Deps[i]); + } + + // Add a dependence between the new instruction and the instruction + // that defines the new base. + SDep Dep(&I, SDep::Anti, NewBase); + LastSU->addPred(Dep); + + // Remember the base and offset information so that we can update the + // instruction during code generation. + InstrChanges[&I] = std::make_pair(NewBase, NewOffset); + } +} + +namespace { +// FuncUnitSorter - Comparison operator used to sort instructions by +// the number of functional unit choices. +struct FuncUnitSorter { + const InstrItineraryData *InstrItins; + DenseMap Resources; + + // Compute the number of functional unit alternatives needed + // at each stage, and take the minimum value. We prioritize the + // instructions by the least number of choices first. + unsigned minFuncUnits(const MachineInstr *Inst, unsigned &F) const { + unsigned schedClass = Inst->getDesc().getSchedClass(); + unsigned min = UINT_MAX; + for (const InstrStage *IS = InstrItins->beginStage(schedClass), + *IE = InstrItins->endStage(schedClass); + IS != IE; ++IS) { + unsigned funcUnits = IS->getUnits(); + unsigned numAlternatives = countPopulation(funcUnits); + if (numAlternatives < min) { + min = numAlternatives; + F = funcUnits; + } + } + return min; + } + + // Compute the critical resources needed by the instruction. This + // function records the functional units needed by instructions that + // must use only one functional unit. We use this as a tie breaker + // for computing the resource MII. The instrutions that require + // the same, highly used, functional unit have high priority. + void calcCriticalResources(const MachineInstr *MI) { + unsigned SchedClass = MI->getDesc().getSchedClass(); + for (const InstrStage *IS = InstrItins->beginStage(SchedClass), + *IE = InstrItins->endStage(SchedClass); + IS != IE; ++IS) { + unsigned FuncUnits = IS->getUnits(); + if (countPopulation(FuncUnits) == 1) + Resources[FuncUnits]++; + } + } + + FuncUnitSorter(const InstrItineraryData *IID) : InstrItins(IID) {} + /// Return true if IS1 has less priority than IS2. + bool operator()(const MachineInstr *IS1, const MachineInstr *IS2) const { + unsigned F1 = 0, F2 = 0; + unsigned MFUs1 = minFuncUnits(IS1, F1); + unsigned MFUs2 = minFuncUnits(IS2, F2); + if (MFUs1 == 1 && MFUs2 == 1) + return Resources.lookup(F1) < Resources.lookup(F2); + return MFUs1 > MFUs2; + } +}; +} + +/// Calculate the resource constrained minimum initiation interval for the +/// specified loop. We use the DFA to model the resources needed for +/// each instruction, and we ignore dependences. A different DFA is created +/// for each cycle that is required. When adding a new instruction, we attempt +/// to add it to each existing DFA, until a legal space is found. If the +/// instruction cannot be reserved in an existing DFA, we create a new one. +unsigned SwingSchedulerDAG::calculateResMII() { + SmallVector Resources; + MachineBasicBlock *MBB = Loop.getHeader(); + Resources.push_back(TII->CreateTargetScheduleState(MF.getSubtarget())); + + // Sort the instructions by the number of available choices for scheduling, + // least to most. Use the number of critical resources as the tie breaker. + FuncUnitSorter FUS = + FuncUnitSorter(MF.getSubtarget().getInstrItineraryData()); + for (MachineBasicBlock::iterator I = MBB->getFirstNonPHI(), + E = MBB->getFirstTerminator(); + I != E; ++I) + FUS.calcCriticalResources(I); + PriorityQueue, FuncUnitSorter> + FuncUnitOrder(FUS); + + for (MachineBasicBlock::iterator I = MBB->getFirstNonPHI(), + E = MBB->getFirstTerminator(); + I != E; ++I) + FuncUnitOrder.push(I); + + while (!FuncUnitOrder.empty()) { + MachineInstr *MI = FuncUnitOrder.top(); + FuncUnitOrder.pop(); + if (TII->isZeroCost(MI->getOpcode())) + continue; + // Attempt to reserve the instruction in an existing DFA. At least one + // DFA is needed for each cycle. + unsigned NumCycles = getSUnit(MI)->Latency; + unsigned ReservedCycles = 0; + SmallVectorImpl::iterator RI = Resources.begin(); + SmallVectorImpl::iterator RE = Resources.end(); + for (unsigned C = 0; C < NumCycles; ++C) + while (RI != RE) { + if ((*RI++)->canReserveResources(*MI)) { + ++ReservedCycles; + break; + } + } + // Start reserving resources using existing DFAs. + for (unsigned C = 0; C < ReservedCycles; ++C) { + --RI; + (*RI)->reserveResources(*MI); + } + // Add new DFAs, if needed, to reserve resources. + for (unsigned C = ReservedCycles; C < NumCycles; ++C) { + DFAPacketizer *NewResource = + TII->CreateTargetScheduleState(MF.getSubtarget()); + assert(NewResource->canReserveResources(*MI) && "Reserve error."); + NewResource->reserveResources(*MI); + Resources.push_back(NewResource); + } + } + int Resmii = Resources.size(); + // Delete the memory for each of the DFAs that were created earlier. + for (DFAPacketizer *RI : Resources) { + DFAPacketizer *D = RI; + delete D; + } + Resources.clear(); + return Resmii; +} + +/// Calculate the recurrence-constrainted minimum initiation interval. +/// Iterate over each circuit. Compute the delay(c) and distance(c) +/// for each circuit. The II needs to satisfy the inequality +/// delay(c) - II*distance(c) <= 0. For each circuit, choose the smallest +/// II that satistifies the inequality, and the RecMII is the maximum +/// of those values. +unsigned SwingSchedulerDAG::calculateRecMII(NodeSetType &NodeSets) { + unsigned RecMII = 0; + + for (NodeSet &Nodes : NodeSets) { + if (Nodes.size() == 0) + continue; + + unsigned Delay = Nodes.size() - 1; + unsigned Distance = 1; + + // ii = ceil(delay / distance) + unsigned CurMII = (Delay + Distance - 1) / Distance; + Nodes.setRecMII(CurMII); + if (CurMII > RecMII) + RecMII = CurMII; + } + + return RecMII; +} + +/// Swap all the anti dependences in the DAG. That means it is no longer a DAG, +/// but we do this to find the circuits, and then change them back. +static void swapAntiDependences(std::vector &SUnits) { + SmallVector, 8> DepsAdded; + for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { + SUnit *SU = &SUnits[i]; + for (SUnit::pred_iterator IP = SU->Preds.begin(), EP = SU->Preds.end(); + IP != EP; ++IP) { + if (IP->getKind() != SDep::Anti) + continue; + DepsAdded.push_back(std::make_pair(SU, *IP)); + } + } + for (SmallVector, 8>::iterator I = DepsAdded.begin(), + E = DepsAdded.end(); + I != E; ++I) { + // Remove this anti dependency and add one in the reverse direction. + SUnit *SU = I->first; + SDep &D = I->second; + SUnit *TargetSU = D.getSUnit(); + unsigned Reg = D.getReg(); + unsigned Lat = D.getLatency(); + SU->removePred(D); + SDep Dep(SU, SDep::Anti, Reg); + Dep.setLatency(Lat); + TargetSU->addPred(Dep); + } +} + +/// Create the adjacency structure of the nodes in the graph. +void SwingSchedulerDAG::Circuits::createAdjacencyStructure( + SwingSchedulerDAG *DAG) { + BitVector Added(SUnits.size()); + for (int i = 0, e = SUnits.size(); i != e; ++i) { + Added.reset(); + // Add any successor to the adjacency matrix and exclude duplicates. + for (auto &SI : SUnits[i].Succs) { + // A back-edge is processed only if it goes to a Phi. + if (SI.getKind() == SDep::Anti && !SI.getSUnit()->getInstr()->isPHI()) + continue; + int N = SI.getSUnit()->NodeNum; + if (!Added.test(N)) { + AdjK[i].push_back(N); + Added.set(N); + } + } + // A chain edge between a store and a load is treated as a back-edge in the + // adjacency matrix. + for (auto &PI : SUnits[i].Preds) { + if (!SUnits[i].getInstr()->mayStore() || + !DAG->isLoopCarriedOrder(&SUnits[i], PI, false)) + continue; + if (PI.getKind() == SDep::Order && PI.getSUnit()->getInstr()->mayLoad()) { + int N = PI.getSUnit()->NodeNum; + if (!Added.test(N)) { + AdjK[i].push_back(N); + Added.set(N); + } + } + } + } +} + +/// Identify an elementary circuit in the dependence graph starting at the +/// specified node. +bool SwingSchedulerDAG::Circuits::circuit(int V, int S, NodeSetType &NodeSets, + bool HasBackedge) { + SUnit *SV = &SUnits[V]; + bool F = false; + Stack.insert(SV); + Blocked.set(V); + + for (auto W : AdjK[V]) { + if (NumPaths > MaxPaths) + break; + if (W < S) + continue; + if (W == S) { + if (!HasBackedge) + NodeSets.push_back(NodeSet(Stack.begin(), Stack.end())); + F = true; + ++NumPaths; + break; + } else if (!Blocked.test(W)) { + if (circuit(W, S, NodeSets, W < V ? true : HasBackedge)) + F = true; + } + } + + if (F) + unblock(V); + else { + for (auto W : AdjK[V]) { + if (W < S) + continue; + if (B[W].count(SV) == 0) + B[W].insert(SV); + } + } + Stack.pop_back(); + return F; +} + +/// Unblock a node in the circuit finding algorithm. +void SwingSchedulerDAG::Circuits::unblock(int U) { + Blocked.reset(U); + SmallPtrSet &BU = B[U]; + while (!BU.empty()) { + SmallPtrSet::iterator SI = BU.begin(); + assert(SI != BU.end() && "Invalid B set."); + SUnit *W = *SI; + BU.erase(W); + if (Blocked.test(W->NodeNum)) + unblock(W->NodeNum); + } +} + +/// Identify all the elementary circuits in the dependence graph using +/// Johnson's circuit algorithm. +void SwingSchedulerDAG::findCircuits(NodeSetType &NodeSets) { + // Swap all the anti dependences in the DAG. That means it is no longer a DAG, + // but we do this to find the circuits, and then change them back. + swapAntiDependences(SUnits); + + Circuits Cir(SUnits); + // Create the adjacency structure. + Cir.createAdjacencyStructure(this); + for (int i = 0, e = SUnits.size(); i != e; ++i) { + Cir.reset(); + Cir.circuit(i, i, NodeSets); + } + + // Change the dependences back so that we've created a DAG again. + swapAntiDependences(SUnits); +} + +/// Return true for DAG nodes that we ignore when computing the cost functions. +/// We ignore the back-edge recurrence in order to avoid unbounded recurison +/// in the calculation of the ASAP, ALAP, etc functions. +static bool ignoreDependence(const SDep &D, bool isPred) { + if (D.isArtificial()) + return true; + return D.getKind() == SDep::Anti && isPred; +} + +/// Compute several functions need to order the nodes for scheduling. +/// ASAP - Earliest time to schedule a node. +/// ALAP - Latest time to schedule a node. +/// MOV - Mobility function, difference between ALAP and ASAP. +/// D - Depth of each node. +/// H - Height of each node. +void SwingSchedulerDAG::computeNodeFunctions(NodeSetType &NodeSets) { + + ScheduleInfo.resize(SUnits.size()); + + DEBUG({ + for (ScheduleDAGTopologicalSort::const_iterator I = Topo.begin(), + E = Topo.end(); + I != E; ++I) { + SUnit *SU = &SUnits[*I]; + SU->dump(this); + } + }); + + int maxASAP = 0; + // Compute ASAP. + for (ScheduleDAGTopologicalSort::const_iterator I = Topo.begin(), + E = Topo.end(); + I != E; ++I) { + int asap = 0; + SUnit *SU = &SUnits[*I]; + for (SUnit::const_pred_iterator IP = SU->Preds.begin(), + EP = SU->Preds.end(); + IP != EP; ++IP) { + if (ignoreDependence(*IP, true)) + continue; + SUnit *pred = IP->getSUnit(); + asap = std::max(asap, (int)(getASAP(pred) + getLatency(SU, *IP) - + getDistance(pred, SU, *IP) * MII)); + } + maxASAP = std::max(maxASAP, asap); + ScheduleInfo[*I].ASAP = asap; + } + + // Compute ALAP and MOV. + for (ScheduleDAGTopologicalSort::const_reverse_iterator I = Topo.rbegin(), + E = Topo.rend(); + I != E; ++I) { + int alap = maxASAP; + SUnit *SU = &SUnits[*I]; + for (SUnit::const_succ_iterator IS = SU->Succs.begin(), + ES = SU->Succs.end(); + IS != ES; ++IS) { + if (ignoreDependence(*IS, true)) + continue; + SUnit *succ = IS->getSUnit(); + alap = std::min(alap, (int)(getALAP(succ) - getLatency(SU, *IS) + + getDistance(SU, succ, *IS) * MII)); + } + + ScheduleInfo[*I].ALAP = alap; + } + + // After computing the node functions, compute the summary for each node set. + for (NodeSet &I : NodeSets) + I.computeNodeSetInfo(this); + + DEBUG({ + for (unsigned i = 0; i < SUnits.size(); i++) { + dbgs() << "\tNode " << i << ":\n"; + dbgs() << "\t ASAP = " << getASAP(&SUnits[i]) << "\n"; + dbgs() << "\t ALAP = " << getALAP(&SUnits[i]) << "\n"; + dbgs() << "\t MOV = " << getMOV(&SUnits[i]) << "\n"; + dbgs() << "\t D = " << getDepth(&SUnits[i]) << "\n"; + dbgs() << "\t H = " << getHeight(&SUnits[i]) << "\n"; + } + }); +} + +/// Compute the Pred_L(O) set, as defined in the paper. The set is defined +/// as the predecessors of the elements of NodeOrder that are not also in +/// NodeOrder. +static bool pred_L(SetVector &NodeOrder, + SmallSetVector &Preds, + const NodeSet *S = nullptr) { + Preds.clear(); + for (SetVector::iterator I = NodeOrder.begin(), E = NodeOrder.end(); + I != E; ++I) { + for (SUnit::pred_iterator PI = (*I)->Preds.begin(), PE = (*I)->Preds.end(); + PI != PE; ++PI) { + if (S && S->count(PI->getSUnit()) == 0) + continue; + if (ignoreDependence(*PI, true)) + continue; + if (NodeOrder.count(PI->getSUnit()) == 0) + Preds.insert(PI->getSUnit()); + } + // Back-edges are predecessors with an anti-dependence. + for (SUnit::const_succ_iterator IS = (*I)->Succs.begin(), + ES = (*I)->Succs.end(); + IS != ES; ++IS) { + if (IS->getKind() != SDep::Anti) + continue; + if (S && S->count(IS->getSUnit()) == 0) + continue; + if (NodeOrder.count(IS->getSUnit()) == 0) + Preds.insert(IS->getSUnit()); + } + } + return Preds.size() > 0; +} + +/// Compute the Succ_L(O) set, as defined in the paper. The set is defined +/// as the successors of the elements of NodeOrder that are not also in +/// NodeOrder. +static bool succ_L(SetVector &NodeOrder, + SmallSetVector &Succs, + const NodeSet *S = nullptr) { + Succs.clear(); + for (SetVector::iterator I = NodeOrder.begin(), E = NodeOrder.end(); + I != E; ++I) { + for (SUnit::succ_iterator SI = (*I)->Succs.begin(), SE = (*I)->Succs.end(); + SI != SE; ++SI) { + if (S && S->count(SI->getSUnit()) == 0) + continue; + if (ignoreDependence(*SI, false)) + continue; + if (NodeOrder.count(SI->getSUnit()) == 0) + Succs.insert(SI->getSUnit()); + } + for (SUnit::const_pred_iterator PI = (*I)->Preds.begin(), + PE = (*I)->Preds.end(); + PI != PE; ++PI) { + if (PI->getKind() != SDep::Anti) + continue; + if (S && S->count(PI->getSUnit()) == 0) + continue; + if (NodeOrder.count(PI->getSUnit()) == 0) + Succs.insert(PI->getSUnit()); + } + } + return Succs.size() > 0; +} + +/// Return true if there is a path from the specified node to any of the nodes +/// in DestNodes. Keep track and return the nodes in any path. +static bool computePath(SUnit *Cur, SetVector &Path, + SetVector &DestNodes, + SetVector &Exclude, + SmallPtrSet &Visited) { + if (Cur->isBoundaryNode()) + return false; + if (Exclude.count(Cur) != 0) + return false; + if (DestNodes.count(Cur) != 0) + return true; + if (!Visited.insert(Cur).second) + return Path.count(Cur) != 0; + bool FoundPath = false; + for (auto &SI : Cur->Succs) + FoundPath |= computePath(SI.getSUnit(), Path, DestNodes, Exclude, Visited); + for (auto &PI : Cur->Preds) + if (PI.getKind() == SDep::Anti) + FoundPath |= + computePath(PI.getSUnit(), Path, DestNodes, Exclude, Visited); + if (FoundPath) + Path.insert(Cur); + return FoundPath; +} + +/// Return true if Set1 is a subset of Set2. +template static bool isSubset(S1Ty &Set1, S2Ty &Set2) { + for (typename S1Ty::iterator I = Set1.begin(), E = Set1.end(); I != E; ++I) + if (Set2.count(*I) == 0) + return false; + return true; +} + +/// Compute the live-out registers for the instructions in a node-set. +/// The live-out registers are those that are defined in the node-set, +/// but not used. Except for use operands of Phis. +static void computeLiveOuts(RegPressureTracker &RPTracker, NodeSet &NS) { + SmallVector LiveOutRegs; + SmallSet Uses; + for (SUnit *SU : NS) { + const MachineInstr *MI = SU->getInstr(); + if (MI->isPHI()) + continue; + for (ConstMIOperands MO(*MI); MO.isValid(); ++MO) + if (MO->isReg() && MO->isUse()) + Uses.insert(MO->getReg()); + } + for (SUnit *SU : NS) + for (ConstMIOperands MO(*SU->getInstr()); MO.isValid(); ++MO) + if (MO->isReg() && MO->isDef() && !MO->isDead() && + !Uses.count(MO->getReg())) + LiveOutRegs.push_back(RegisterMaskPair(MO->getReg(), 0)); + RPTracker.addLiveRegs(LiveOutRegs); +} + +/// A heuristic to filter nodes in recurrent node-sets if the register +/// pressure of a set is too high. +void SwingSchedulerDAG::registerPressureFilter(NodeSetType &NodeSets) { + for (auto &NS : NodeSets) { + // Skip small node-sets since they won't cause register pressure problems. + if (NS.size() <= 2) + continue; + IntervalPressure RecRegPressure; + RegPressureTracker RecRPTracker(RecRegPressure); + RecRPTracker.init(&MF, &RegClassInfo, &LIS, BB, BB->end(), false, true); + computeLiveOuts(RecRPTracker, NS); + RecRPTracker.closeBottom(); + + std::vector SUnits(NS.begin(), NS.end()); + std::sort(SUnits.begin(), SUnits.end(), [](const SUnit *A, const SUnit *B) { + return A->NodeNum > B->NodeNum; + }); + + for (auto &SU : SUnits) { + // Since we're computing the register pressure for a subset of the + // instructions in a block, we need to set the tracker for each + // instruction in the node-set. The tracker is set to the instruction + // just after the one we're interested in. + MachineBasicBlock::const_iterator CurInstI = SU->getInstr(); + RecRPTracker.setPos(std::next(CurInstI)); + + RegPressureDelta RPDelta; + ArrayRef CriticalPSets; + RecRPTracker.getMaxUpwardPressureDelta(SU->getInstr(), nullptr, RPDelta, + CriticalPSets, + RecRegPressure.MaxSetPressure); + if (RPDelta.Excess.isValid()) { + DEBUG(dbgs() << "Excess register pressure: SU(" << SU->NodeNum << ") " + << TRI->getRegPressureSetName(RPDelta.Excess.getPSet()) + << ":" << RPDelta.Excess.getUnitInc()); + NS.setExceedPressure(SU); + break; + } + RecRPTracker.recede(); + } + } +} + +/// A heuristic to colocate node sets that have the same set of +/// successors. +void SwingSchedulerDAG::colocateNodeSets(NodeSetType &NodeSets) { + unsigned Colocate = 0; + for (int i = 0, e = NodeSets.size(); i < e; ++i) { + NodeSet &N1 = NodeSets[i]; + SmallSetVector S1; + if (N1.empty() || !succ_L(N1, S1)) + continue; + for (int j = i + 1; j < e; ++j) { + NodeSet &N2 = NodeSets[j]; + if (N1.compareRecMII(N2) != 0) + continue; + SmallSetVector S2; + if (N2.empty() || !succ_L(N2, S2)) + continue; + if (isSubset(S1, S2) && S1.size() == S2.size()) { + N1.setColocate(++Colocate); + N2.setColocate(Colocate); + break; + } + } + } +} + +/// Check if the existing node-sets are profitable. If not, then ignore the +/// recurrent node-sets, and attempt to schedule all nodes together. This is +/// a heuristic. If the MII is large and there is a non-recurrent node with +/// a large depth compared to the MII, then it's best to try and schedule +/// all instruction together instead of starting with the recurrent node-sets. +void SwingSchedulerDAG::checkNodeSets(NodeSetType &NodeSets) { + // Look for loops with a large MII. + if (MII <= 20) + return; + // Check if the node-set contains only a simple add recurrence. + for (auto &NS : NodeSets) + if (NS.size() > 2) + return; + // If the depth of any instruction is significantly larger than the MII, then + // ignore the recurrent node-sets and treat all instructions equally. + for (auto &SU : SUnits) + if (SU.getDepth() > MII * 1.5) { + NodeSets.clear(); + DEBUG(dbgs() << "Clear recurrence node-sets\n"); + return; + } +} + +/// Add the nodes that do not belong to a recurrence set into groups +/// based upon connected componenets. +void SwingSchedulerDAG::groupRemainingNodes(NodeSetType &NodeSets) { + SetVector NodesAdded; + SmallPtrSet Visited; + // Add the nodes that are on a path between the previous node sets and + // the current node set. + for (NodeSet &I : NodeSets) { + SmallSetVector N; + // Add the nodes from the current node set to the previous node set. + if (succ_L(I, N)) { + SetVector Path; + for (SUnit *NI : N) { + Visited.clear(); + computePath(NI, Path, NodesAdded, I, Visited); + } + if (Path.size() > 0) + I.insert(Path.begin(), Path.end()); + } + // Add the nodes from the previous node set to the current node set. + N.clear(); + if (succ_L(NodesAdded, N)) { + SetVector Path; + for (SUnit *NI : N) { + Visited.clear(); + computePath(NI, Path, I, NodesAdded, Visited); + } + if (Path.size() > 0) + I.insert(Path.begin(), Path.end()); + } + NodesAdded.insert(I.begin(), I.end()); + } + + // Create a new node set with the connected nodes of any successor of a node + // in a recurrent set. + NodeSet NewSet; + SmallSetVector N; + if (succ_L(NodesAdded, N)) + for (SUnit *I : N) + addConnectedNodes(I, NewSet, NodesAdded); + if (NewSet.size() > 0) + NodeSets.push_back(NewSet); + + // Create a new node set with the connected nodes of any predecessor of a node + // in a recurrent set. + NewSet.clear(); + if (pred_L(NodesAdded, N)) + for (SUnit *I : N) + addConnectedNodes(I, NewSet, NodesAdded); + if (NewSet.size() > 0) + NodeSets.push_back(NewSet); + + // Create new nodes sets with the connected nodes any any remaining node that + // has no predecessor. + for (unsigned i = 0; i < SUnits.size(); ++i) { + SUnit *SU = &SUnits[i]; + if (NodesAdded.count(SU) == 0) { + NewSet.clear(); + addConnectedNodes(SU, NewSet, NodesAdded); + if (NewSet.size() > 0) + NodeSets.push_back(NewSet); + } + } +} + +/// Add the node to the set, and add all is its connected nodes to the set. +void SwingSchedulerDAG::addConnectedNodes(SUnit *SU, NodeSet &NewSet, + SetVector &NodesAdded) { + NewSet.insert(SU); + NodesAdded.insert(SU); + for (auto &SI : SU->Succs) { + SUnit *Successor = SI.getSUnit(); + if (!SI.isArtificial() && NodesAdded.count(Successor) == 0) + addConnectedNodes(Successor, NewSet, NodesAdded); + } + for (auto &PI : SU->Preds) { + SUnit *Predecessor = PI.getSUnit(); + if (!PI.isArtificial() && NodesAdded.count(Predecessor) == 0) + addConnectedNodes(Predecessor, NewSet, NodesAdded); + } +} + +/// Return true if Set1 contains elements in Set2. The elements in common +/// are returned in a different container. +static bool isIntersect(SmallSetVector &Set1, const NodeSet &Set2, + SmallSetVector &Result) { + Result.clear(); + for (unsigned i = 0, e = Set1.size(); i != e; ++i) { + SUnit *SU = Set1[i]; + if (Set2.count(SU) != 0) + Result.insert(SU); + } + return !Result.empty(); +} + +/// Merge the recurrence node sets that have the same initial node. +void SwingSchedulerDAG::fuseRecs(NodeSetType &NodeSets) { + for (NodeSetType::iterator I = NodeSets.begin(), E = NodeSets.end(); I != E; + ++I) { + NodeSet &NI = *I; + for (NodeSetType::iterator J = I + 1; J != E;) { + NodeSet &NJ = *J; + if (NI.getNode(0)->NodeNum == NJ.getNode(0)->NodeNum) { + if (NJ.compareRecMII(NI) > 0) + NI.setRecMII(NJ.getRecMII()); + for (NodeSet::iterator NII = J->begin(), ENI = J->end(); NII != ENI; + ++NII) + I->insert(*NII); + NodeSets.erase(J); + E = NodeSets.end(); + } else { + ++J; + } + } + } +} + +/// Remove nodes that have been scheduled in previous NodeSets. +void SwingSchedulerDAG::removeDuplicateNodes(NodeSetType &NodeSets) { + for (NodeSetType::iterator I = NodeSets.begin(), E = NodeSets.end(); I != E; + ++I) + for (NodeSetType::iterator J = I + 1; J != E;) { + J->remove_if([&](SUnit *SUJ) { return I->count(SUJ); }); + + if (J->size() == 0) { + NodeSets.erase(J); + E = NodeSets.end(); + } else { + ++J; + } + } +} + +/// Return true if Inst1 defines a value that is used in Inst2. +static bool hasDataDependence(SUnit *Inst1, SUnit *Inst2) { + for (auto &SI : Inst1->Succs) + if (SI.getSUnit() == Inst2 && SI.getKind() == SDep::Data) + return true; + return false; +} + +/// Compute an ordered list of the dependence graph nodes, which +/// indicates the order that the nodes will be scheduled. This is a +/// two-level algorithm. First, a partial order is created, which +/// consists of a list of sets ordered from highest to lowest priority. +void SwingSchedulerDAG::computeNodeOrder(NodeSetType &NodeSets) { + SmallSetVector R; + NodeOrder.clear(); + + for (auto &Nodes : NodeSets) { + DEBUG(dbgs() << "NodeSet size " << Nodes.size() << "\n"); + OrderKind Order; + SmallSetVector N; + if (pred_L(NodeOrder, N) && isSubset(N, Nodes)) { + R.insert(N.begin(), N.end()); + Order = BottomUp; + DEBUG(dbgs() << " Bottom up (preds) "); + } else if (succ_L(NodeOrder, N) && isSubset(N, Nodes)) { + R.insert(N.begin(), N.end()); + Order = TopDown; + DEBUG(dbgs() << " Top down (succs) "); + } else if (isIntersect(N, Nodes, R)) { + // If some of the successors are in the existing node-set, then use the + // top-down ordering. + Order = TopDown; + DEBUG(dbgs() << " Top down (intersect) "); + } else if (NodeSets.size() == 1) { + for (auto &N : Nodes) + if (N->Succs.size() == 0) + R.insert(N); + Order = BottomUp; + DEBUG(dbgs() << " Bottom up (all) "); + } else { + // Find the node with the highest ASAP. + SUnit *maxASAP = nullptr; + for (SUnit *SU : Nodes) { + if (maxASAP == nullptr || getASAP(SU) >= getASAP(maxASAP)) + maxASAP = SU; + } + R.insert(maxASAP); + Order = BottomUp; + DEBUG(dbgs() << " Bottom up (default) "); + } + + while (!R.empty()) { + if (Order == TopDown) { + // Choose the node with the maximum height. If more than one, choose + // the node with the lowest MOV. If still more than one, check if there + // is a dependence between the instructions. + while (!R.empty()) { + SUnit *maxHeight = nullptr; + for (SUnit *I : R) { + if (maxHeight == 0 || getHeight(I) > getHeight(maxHeight)) + maxHeight = I; + else if (getHeight(I) == getHeight(maxHeight) && + getMOV(I) < getMOV(maxHeight) && + !hasDataDependence(maxHeight, I)) + maxHeight = I; + else if (hasDataDependence(I, maxHeight)) + maxHeight = I; + } + NodeOrder.insert(maxHeight); + DEBUG(dbgs() << maxHeight->NodeNum << " "); + R.remove(maxHeight); + for (const auto &I : maxHeight->Succs) { + if (Nodes.count(I.getSUnit()) == 0) + continue; + if (NodeOrder.count(I.getSUnit()) != 0) + continue; + if (ignoreDependence(I, false)) + continue; + R.insert(I.getSUnit()); + } + // Back-edges are predecessors with an anti-dependence. + for (const auto &I : maxHeight->Preds) { + if (I.getKind() != SDep::Anti) + continue; + if (Nodes.count(I.getSUnit()) == 0) + continue; + if (NodeOrder.count(I.getSUnit()) != 0) + continue; + R.insert(I.getSUnit()); + } + } + Order = BottomUp; + DEBUG(dbgs() << "\n Switching order to bottom up "); + SmallSetVector N; + if (pred_L(NodeOrder, N, &Nodes)) + R.insert(N.begin(), N.end()); + } else { + // Choose the node with the maximum depth. If more than one, choose + // the node with the lowest MOV. If there is still more than one, check + // for a dependence between the instructions. + while (!R.empty()) { + SUnit *maxDepth = nullptr; + for (SUnit *I : R) { + if (maxDepth == 0 || getDepth(I) > getDepth(maxDepth)) + maxDepth = I; + else if (getDepth(I) == getDepth(maxDepth) && + getMOV(I) < getMOV(maxDepth) && + !hasDataDependence(I, maxDepth)) + maxDepth = I; + else if (hasDataDependence(maxDepth, I)) + maxDepth = I; + } + NodeOrder.insert(maxDepth); + DEBUG(dbgs() << maxDepth->NodeNum << " "); + R.remove(maxDepth); + if (Nodes.isExceedSU(maxDepth)) { + Order = TopDown; + R.clear(); + R.insert(Nodes.getNode(0)); + break; + } + for (const auto &I : maxDepth->Preds) { + if (Nodes.count(I.getSUnit()) == 0) + continue; + if (NodeOrder.count(I.getSUnit()) != 0) + continue; + if (I.getKind() == SDep::Anti) + continue; + R.insert(I.getSUnit()); + } + // Back-edges are predecessors with an anti-dependence. + for (const auto &I : maxDepth->Succs) { + if (I.getKind() != SDep::Anti) + continue; + if (Nodes.count(I.getSUnit()) == 0) + continue; + if (NodeOrder.count(I.getSUnit()) != 0) + continue; + R.insert(I.getSUnit()); + } + } + Order = TopDown; + DEBUG(dbgs() << "\n Switching order to top down "); + SmallSetVector N; + if (succ_L(NodeOrder, N, &Nodes)) + R.insert(N.begin(), N.end()); + } + } + DEBUG(dbgs() << "\nDone with Nodeset\n"); + } + + DEBUG({ + dbgs() << "Node order: "; + for (SUnit *I : NodeOrder) + dbgs() << " " << I->NodeNum << " "; + dbgs() << "\n"; + }); +} + +/// Process the nodes in the computed order and create the pipelined schedule +/// of the instructions, if possible. Return true if a schedule is found. +bool SwingSchedulerDAG::schedulePipeline(SMSchedule &Schedule) { + + if (NodeOrder.size() == 0) + return false; + + bool scheduleFound = false; + // Keep increasing II until a valid schedule is found. + for (unsigned II = MII; II < MII + 10 && !scheduleFound; ++II) { + Schedule.reset(); + Schedule.setInitiationInterval(II); + DEBUG(dbgs() << "Try to schedule with " << II << "\n"); + + SetVector::iterator NI = NodeOrder.begin(); + SetVector::iterator NE = NodeOrder.end(); + do { + SUnit *SU = *NI; + + // Compute the schedule time for the instruction, which is based + // upon the scheduled time for any predecessors/successors. + int EarlyStart = INT_MIN; + int LateStart = INT_MAX; + // These values are set when the size of the schedule window is limited + // due to chain dependences. + int SchedEnd = INT_MAX; + int SchedStart = INT_MIN; + Schedule.computeStart(SU, &EarlyStart, &LateStart, &SchedEnd, &SchedStart, + II, this); + DEBUG({ + dbgs() << "Inst (" << SU->NodeNum << ") "; + SU->getInstr()->dump(); + dbgs() << "\n"; + }); + DEBUG({ + dbgs() << "\tes: " << EarlyStart << " ls: " << LateStart + << " me: " << SchedEnd << " ms: " << SchedStart << "\n"; + }); + + if (EarlyStart > LateStart || SchedEnd < EarlyStart || + SchedStart > LateStart) + scheduleFound = false; + else if (EarlyStart != INT_MIN && LateStart == INT_MAX) { + SchedEnd = std::min(SchedEnd, EarlyStart + (int)II - 1); + scheduleFound = Schedule.insert(SU, EarlyStart, SchedEnd, II); + } else if (EarlyStart == INT_MIN && LateStart != INT_MAX) { + SchedStart = std::max(SchedStart, LateStart - (int)II + 1); + scheduleFound = Schedule.insert(SU, LateStart, SchedStart, II); + } else if (EarlyStart != INT_MIN && LateStart != INT_MAX) { + SchedEnd = + std::min(SchedEnd, std::min(LateStart, EarlyStart + (int)II - 1)); + // When scheduling a Phi it is better to start at the late cycle and go + // backwards. The default order may insert the Phi too far away from + // its first dependence. + if (SU->getInstr()->isPHI()) + scheduleFound = Schedule.insert(SU, SchedEnd, EarlyStart, II); + else + scheduleFound = Schedule.insert(SU, EarlyStart, SchedEnd, II); + } else { + int FirstCycle = Schedule.getFirstCycle(); + scheduleFound = Schedule.insert(SU, FirstCycle + getASAP(SU), + FirstCycle + getASAP(SU) + II - 1, II); + } + DEBUG({ + if (!scheduleFound) + dbgs() << "\tCan't schedule\n"; + }); + } while (++NI != NE && scheduleFound); + } + + DEBUG(dbgs() << "Schedule Found? " << scheduleFound << "\n"); + + if (scheduleFound) + Schedule.finalizeSchedule(this); + else + Schedule.reset(); + + 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 orignal 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(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); + + 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(PrologBBs, KernelBB, EpilogBBs, Schedule, VRMap); + + // Remove the original loop since it's no longer referenced. + 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 != NULL && + "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); + 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], 0, 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)) { + MachineInstr *NewMI = cloneInstr(In, EpilogStage - LastStage, 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; + + DEBUG({ + dbgs() << "epilog:\n"; + NewBB->dump(); + }); + } + + // Fix any Phi nodes in the loop exit block. + for (MachineInstr &MI : *LoopExitBB) { + if (!MI.isPHI()) + break; + for (unsigned i = 2, e = MI.getNumOperands() + 1; i != e; i += 2) { + MachineOperand &MO = MI.getOperand(i); + if (MO.getMBB() == BB) + MO.setMBB(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, 0, 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 inital 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) { + unsigned 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, + NewReg); + if (VRMap[CurStageNum].count(LoopVal)) + VRMap[CurStageNum][Def] = VRMap[CurStageNum][LoopVal]; + } + // The number of Phis can't exceed the number of prolog stages. We add 2 + // beacause prolog stage number is zero based, and there is a "stage"/Phi + // for the original Phi instruction. + unsigned NumPhis = NumStages; + if (StageScheduled <= (int)PrologStage && NumStages > PrologStage + 2) + NumPhis = PrologStage + 2; + else if (LoopValStage > (int)PrologStage && NumStages > PrologStage + 1) + NumPhis = PrologStage + 1; + 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 intruction + // 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)); + if (PhiOpStage != -1 && PrologStage + PhiOpStage >= Indirects + np && + VRMap[PrologStage + PhiOpStage - Indirects - np].count(PhiOp1)) { + PhiOp1 = VRMap[PrologStage + PhiOpStage - 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 ((unsigned)LoopValStage + StageDiffAdj > 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)) + 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 && VRMap[CurStageNum].count(LoopVal) && + LoopValStage >= (int)(CurStageNum - LastStageNum)) { + int LVNumStages = Schedule.getStagesForPhi(LoopVal); + int StageDiff = (StageScheduled - LoopValStage); + LVNumStages -= StageDiff; + if (LVNumStages > (int)np) { + 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].count(LoopVal)) { + NewReg = VRMap[ReuseStage][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; + } + } else if (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 pipelened 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() || + !TargetRegisterInfo::isVirtualRegister(MO.getReg())) + continue; + + int StageScheduled = Schedule.stageScheduled(getSUnit(BBI)); + assert(StageScheduled != -1 && "Expecting scheduled instruction."); + unsigned 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); + unsigned 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; + unsigned reg = MOI->getReg(); + 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) { + MI->eraseFromParent(); + ME = (*MBB)->instr_rend(); + 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; + unsigned reg = MI->getOperand(0).getReg(); + if (MRI.use_begin(reg) == MRI.use_end()) { + 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 (MachineBasicBlock::iterator BBI = KernelBB->instr_begin(), + BBF = KernelBB->getFirstNonPHI(); + BBI != BBF; ++BBI) { + unsigned Def = BBI->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(BBI, 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(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, 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 (TargetRegisterInfo::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, 0, 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, 0, 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) { + const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); + unsigned BaseReg; + int64_t Offset; + if (!TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI)) + return false; + + 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; + if (!TII->getIncrementValue(BaseDef, D) || D < 0) + return false; + + Delta = D; + return true; +} + +/// Update the memory operand with a new offset when the pipeliner +/// generate 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. + unsigned NumRefs = NewMI->memoperands_end() - NewMI->memoperands_begin(); + if (NumRefs == 0) + return; + MachineInstr::mmo_iterator NewMemRefs = MF.allocateMemRefsArray(NumRefs); + unsigned Refs = 0; + for (MachineInstr::mmo_iterator I = NewMI->memoperands_begin(), + E = NewMI->memoperands_end(); + I != E; ++I) { + if ((*I)->isVolatile() || (*I)->isInvariant() || (!(*I)->getValue())) { + NewMemRefs[Refs++] = *I; + continue; + } + unsigned Delta; + if (computeDelta(OldMI, Delta)) { + int64_t AdjOffset = Delta * Num; + NewMemRefs[Refs++] = + MF.getMachineMemOperand(*I, AdjOffset, (*I)->getSize()); + } else + NewMemRefs[Refs++] = MF.getMachineMemOperand(*I, 0, UINT64_MAX); + } + NewMI->setMemRefs(NewMemRefs, NewMemRefs + NumRefs); +} + +/// 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); + 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)CurStageNum) + 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() || !TargetRegisterInfo::isVirtualRegister(MO.getReg())) + continue; + unsigned reg = MO.getReg(); + if (MO.isDef()) { + // Create a new virtual register for the definition. + const TargetRegisterClass *RC = MRI.getRegClass(reg); + unsigned 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, ValueMapTy *VRMap, + MachineBasicBlock *BB) { + unsigned PrevVal = 0; + if (StageNum > PhiStage) { + MachineInstr *LoopInst = MRI.getVRegDef(LoopVal); + if (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()) + // 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), 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 (MachineBasicBlock::iterator BBI = BB->instr_begin(), + BBE = BB->getFirstNonPHI(); + BBI != BBE; ++BBI) { + unsigned InitVal = 0; + unsigned LoopVal = 0; + getPhiRegs(BBI, BB, InitVal, LoopVal); + unsigned PhiDef = BBI->getOperand(0).getReg(); + + unsigned PhiStage = + (unsigned)Schedule.stageScheduled(getSUnit(MRI.getVRegDef(PhiDef))); + unsigned NumPhis = Schedule.getStagesForReg(PhiDef, StageNum); + if (NumPhis > StageNum + 1) + NumPhis = StageNum + 1; + // Always do at least one iteration. In this case, the loop value is + // scheduled prior to the Phi in the next iteration. + if (NumPhis == 0) + NumPhis = 1; + for (unsigned np = 0; np < NumPhis; ++np) { + unsigned PrevVal = + getPrevMapVal(StageNum - np, PhiStage, LoopVal, VRMap, BB); + rewriteScheduledInstr(NewBB, Schedule, InstrMap, StageNum, np, BBI, + PhiDef, InitVal, PrevVal); + } + } +} + +/// 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 (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. +/// v1 = Phi(v0, v3) +/// v2 = load v1, 0 +/// v3 = post_store v1, 4, x +/// This function enables the load to be rewritten as v2 = load v3, 4. +bool SwingSchedulerDAG::canUseLastOffsetValue(MachineInstr *MI, + unsigned &BasePos, + unsigned &OffsetPos, + unsigned &NewBase, + int64_t &Offset) { + // Get the load instruction. + if (TII->isPostIncrement(MI)) + return false; + unsigned BasePosLd, OffsetPosLd; + if (!TII->getBaseAndOffsetPosition(MI, BasePosLd, OffsetPosLd)) + return false; + unsigned BaseReg = MI->getOperand(BasePosLd).getReg(); + + // Look for the Phi instruction. + MachineRegisterInfo &MRI = MI->getParent()->getParent()->getRegInfo(); + MachineInstr *Phi = MRI.getVRegDef(BaseReg); + if (!Phi || !Phi->isPHI()) + return false; + // Get the register defined in the loop block. + unsigned PrevReg = getLoopPhiReg(Phi, MI->getParent()); + if (!PrevReg) + return false; + + // Check for the post-increment load/store instruction. + MachineInstr *PrevDef = MRI.getVRegDef(PrevReg); + if (!PrevDef || PrevDef == MI) + return false; + + if (!TII->isPostIncrement(PrevDef)) + return false; + + unsigned BasePos1 = 0, OffsetPos1 = 0; + if (!TII->getBaseAndOffsetPosition(PrevDef, BasePos1, OffsetPos1)) + return false; + + // Make sure offset values are both positive or both negative. + int64_t LoadOffset = MI->getOperand(OffsetPosLd).getImm(); + int64_t StoreOffset = PrevDef->getOperand(OffsetPos1).getImm(); + if ((LoadOffset >= 0) != (StoreOffset >= 0)) + return false; + + // Set the return value once we determine that we return true. + BasePos = BasePosLd; + OffsetPos = OffsetPosLd; + NewBase = PrevReg; + Offset = StoreOffset; + return true; +} + +/// Apply changes to the instruction if needed. The changes are need +/// to improve the scheduling and depend up on the final schedule. +MachineInstr *SwingSchedulerDAG::applyInstrChange(MachineInstr *MI, + SMSchedule &Schedule, + bool UpdateDAG) { + SUnit *SU = getSUnit(MI); + DenseMap>::iterator It = + InstrChanges.find(SU); + if (It != InstrChanges.end()) { + std::pair RegAndOffset = It->second; + unsigned BasePos, OffsetPos; + if (!TII->getBaseAndOffsetPosition(MI, BasePos, OffsetPos)) + return nullptr; + unsigned BaseReg = MI->getOperand(BasePos).getReg(); + MachineInstr *LoopDef = findDefInLoop(BaseReg); + int DefStageNum = Schedule.stageScheduled(getSUnit(LoopDef)); + int DefCycleNum = Schedule.cycleScheduled(getSUnit(LoopDef)); + int BaseStageNum = Schedule.stageScheduled(SU); + int BaseCycleNum = Schedule.cycleScheduled(SU); + if (BaseStageNum < DefStageNum) { + MachineInstr *NewMI = MF.CloneMachineInstr(MI); + int OffsetDiff = DefStageNum - BaseStageNum; + if (DefCycleNum < BaseCycleNum) { + NewMI->getOperand(BasePos).setReg(RegAndOffset.first); + if (OffsetDiff > 0) + --OffsetDiff; + } + int64_t NewOffset = + MI->getOperand(OffsetPos).getImm() + RegAndOffset.second * OffsetDiff; + NewMI->getOperand(OffsetPos).setImm(NewOffset); + if (UpdateDAG) { + SU->setInstr(NewMI); + MISUnitMap[NewMI] = SU; + } + NewMIs.insert(NewMI); + return NewMI; + } + } + return nullptr; +} + +/// Return true for an order dependence that is loop carried potentially. +/// An order dependence is loop carried if the destination defines a value +/// that may be used by the source in a subsequent iteration. +bool SwingSchedulerDAG::isLoopCarriedOrder(SUnit *Source, const SDep &Dep, + bool isSucc) { + if (!isOrder(Source, Dep) || Dep.isArtificial()) + return false; + + if (!SwpPruneLoopCarried) + return true; + + MachineInstr *SI = Source->getInstr(); + MachineInstr *DI = Dep.getSUnit()->getInstr(); + if (!isSucc) + std::swap(SI, DI); + assert(SI != nullptr && DI != nullptr && "Expecting SUnit with an MI."); + + // Assume ordered loads and stores may have a loop carried dependence. + if (SI->hasUnmodeledSideEffects() || DI->hasUnmodeledSideEffects() || + SI->hasOrderedMemoryRef() || DI->hasOrderedMemoryRef()) + return true; + + // Only chain dependences between a load and store can be loop carried. + if (!DI->mayStore() || !SI->mayLoad()) + return false; + + unsigned DeltaS, DeltaD; + if (!computeDelta(SI, DeltaS) || !computeDelta(DI, DeltaD)) + return true; + + unsigned BaseRegS, BaseRegD; + int64_t OffsetS, OffsetD; + const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); + if (!TII->getMemOpBaseRegImmOfs(SI, BaseRegS, OffsetS, TRI) || + !TII->getMemOpBaseRegImmOfs(DI, BaseRegD, OffsetD, TRI)) + return true; + + if (BaseRegS != BaseRegD) + return true; + + uint64_t AccessSizeS = (*SI->memoperands_begin())->getSize(); + uint64_t AccessSizeD = (*DI->memoperands_begin())->getSize(); + + // This is the main test, which checks the offset values and the loop + // increment value to determine if the accesses may be loop carried. + if (OffsetS >= OffsetD) + return OffsetS + AccessSizeS > DeltaS; + else if (OffsetS < OffsetD) + return OffsetD + AccessSizeD > DeltaD; + + return true; +} + +/// Try to schedule the node at the specified StartCycle and continue +/// until the node is schedule or the EndCycle is reached. This function +/// returns true if the node is scheduled. This routine may search either +/// forward or backward for a place to insert the instruction based upon +/// the relative values of StartCycle and EndCycle. +bool SMSchedule::insert(SUnit *SU, int StartCycle, int EndCycle, int II) { + bool forward = true; + if (StartCycle > EndCycle) + forward = false; + + // The terminating condition depends on the direction. + int termCycle = forward ? EndCycle + 1 : EndCycle - 1; + for (int curCycle = StartCycle; curCycle != termCycle; + forward ? ++curCycle : --curCycle) { + + // Add the already scheduled instructions at the specified cycle to the DFA. + Resources->clearResources(); + for (int checkCycle = FirstCycle + ((curCycle - FirstCycle) % II); + checkCycle <= LastCycle; checkCycle += II) { + std::deque &cycleInstrs = ScheduledInstrs[checkCycle]; + + for (std::deque::iterator I = cycleInstrs.begin(), + E = cycleInstrs.end(); + I != E; ++I) { + if (ST.getInstrInfo()->isZeroCost((*I)->getInstr()->getOpcode())) + continue; + assert(Resources->canReserveResources(*(*I)->getInstr()) && + "These instructions have already been scheduled."); + Resources->reserveResources(*(*I)->getInstr()); + } + } + if (ST.getInstrInfo()->isZeroCost(SU->getInstr()->getOpcode()) || + Resources->canReserveResources(*SU->getInstr())) { + DEBUG({ + dbgs() << "\tinsert at cycle " << curCycle << " "; + SU->getInstr()->dump(); + }); + + ScheduledInstrs[curCycle].push_back(SU); + InstrToCycle.insert(std::make_pair(SU, curCycle)); + if (curCycle > LastCycle) + LastCycle = curCycle; + if (curCycle < FirstCycle) + FirstCycle = curCycle; + return true; + } + DEBUG({ + dbgs() << "\tfailed to insert at cycle " << curCycle << " "; + SU->getInstr()->dump(); + }); + } + return false; +} + +// Return the cycle of the earliest scheduled instruction in the chain. +int SMSchedule::earliestCycleInChain(const SDep &Dep) { + SmallPtrSet Visited; + SmallVector Worklist; + Worklist.push_back(Dep); + int EarlyCycle = INT_MAX; + while (!Worklist.empty()) { + const SDep &Cur = Worklist.pop_back_val(); + SUnit *PrevSU = Cur.getSUnit(); + if (Visited.count(PrevSU)) + continue; + std::map::const_iterator it = InstrToCycle.find(PrevSU); + if (it == InstrToCycle.end()) + continue; + EarlyCycle = std::min(EarlyCycle, it->second); + for (const auto &PI : PrevSU->Preds) + if (SwingSchedulerDAG::isOrder(PrevSU, PI)) + Worklist.push_back(PI); + Visited.insert(PrevSU); + } + return EarlyCycle; +} + +// Return the cycle of the latest scheduled instruction in the chain. +int SMSchedule::latestCycleInChain(const SDep &Dep) { + SmallPtrSet Visited; + SmallVector Worklist; + Worklist.push_back(Dep); + int LateCycle = INT_MIN; + while (!Worklist.empty()) { + const SDep &Cur = Worklist.pop_back_val(); + SUnit *SuccSU = Cur.getSUnit(); + if (Visited.count(SuccSU)) + continue; + std::map::const_iterator it = InstrToCycle.find(SuccSU); + if (it == InstrToCycle.end()) + continue; + LateCycle = std::max(LateCycle, it->second); + for (const auto &SI : SuccSU->Succs) + if (SwingSchedulerDAG::isOrder(SuccSU, SI)) + Worklist.push_back(SI); + Visited.insert(SuccSU); + } + return LateCycle; +} + +/// If an instruction has a use that spans multiple iterations, then +/// return true. These instructions are characterized by having a back-ege +/// to a Phi, which contains a reference to another Phi. +static SUnit *multipleIterations(SUnit *SU, SwingSchedulerDAG *DAG) { + for (auto &P : SU->Preds) + if (DAG->isBackedge(SU, P) && P.getSUnit()->getInstr()->isPHI()) + for (auto &S : P.getSUnit()->Succs) + if (S.getKind() == SDep::Order && S.getSUnit()->getInstr()->isPHI()) + return P.getSUnit(); + return nullptr; +} + +/// Compute the scheduling start slot for the instruction. The start slot +/// depends on any predecessor or successor nodes scheduled already. +void SMSchedule::computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart, + int *MinEnd, int *MaxStart, int II, + SwingSchedulerDAG *DAG) { + // Iterate over each instruction that has been scheduled already. The start + // slot computuation depends on whether the previously scheduled instruction + // is a predecessor or successor of the specified instruction. + for (int cycle = getFirstCycle(); cycle <= LastCycle; ++cycle) { + + // Iterate over each instruction in the current cycle. + for (SUnit *I : getInstructions(cycle)) { + // Because we're processing a DAG for the dependences, we recognize + // the back-edge in recurrences by anti dependences. + for (unsigned i = 0, e = (unsigned)SU->Preds.size(); i != e; ++i) { + const SDep &Dep = SU->Preds[i]; + if (Dep.getSUnit() == I) { + if (!DAG->isBackedge(SU, Dep)) { + int EarlyStart = cycle + DAG->getLatency(SU, Dep) - + DAG->getDistance(Dep.getSUnit(), SU, Dep) * II; + *MaxEarlyStart = std::max(*MaxEarlyStart, EarlyStart); + if (DAG->isLoopCarriedOrder(SU, Dep, false)) { + int End = earliestCycleInChain(Dep) + (II - 1); + *MinEnd = std::min(*MinEnd, End); + } + } else { + int LateStart = cycle - DAG->getLatency(SU, Dep) + + DAG->getDistance(SU, Dep.getSUnit(), Dep) * II; + *MinLateStart = std::min(*MinLateStart, LateStart); + } + } + // For instruction that requires multiple iterations, make sure that + // the dependent instruction is not scheduled past the definition. + SUnit *BE = multipleIterations(I, DAG); + if (BE && Dep.getSUnit() == BE && !SU->getInstr()->isPHI() && + !SU->isPred(I)) + *MinLateStart = std::min(*MinLateStart, cycle); + } + for (unsigned i = 0, e = (unsigned)SU->Succs.size(); i != e; ++i) + if (SU->Succs[i].getSUnit() == I) { + const SDep &Dep = SU->Succs[i]; + if (!DAG->isBackedge(SU, Dep)) { + int LateStart = cycle - DAG->getLatency(SU, Dep) + + DAG->getDistance(SU, Dep.getSUnit(), Dep) * II; + *MinLateStart = std::min(*MinLateStart, LateStart); + if (DAG->isLoopCarriedOrder(SU, Dep)) { + int Start = latestCycleInChain(Dep) + 1 - II; + *MaxStart = std::max(*MaxStart, Start); + } + } else { + int EarlyStart = cycle + DAG->getLatency(SU, Dep) - + DAG->getDistance(Dep.getSUnit(), SU, Dep) * II; + *MaxEarlyStart = std::max(*MaxEarlyStart, EarlyStart); + } + } + } + } +} + +/// Order the instructions within a cycle so that the definitions occur +/// before the uses. Returns true if the instruction is added to the start +/// of the list, or false if added to the end. +bool SMSchedule::orderDependence(SwingSchedulerDAG *SSD, SUnit *SU, + std::deque &Insts) { + MachineInstr *MI = SU->getInstr(); + bool OrderBeforeUse = false; + bool OrderAfterDef = false; + bool OrderBeforeDef = false; + unsigned MoveDef = 0; + unsigned MoveUse = 0; + int StageInst1 = stageScheduled(SU); + + unsigned Pos = 0; + for (std::deque::iterator I = Insts.begin(), E = Insts.end(); I != E; + ++I, ++Pos) { + // Relative order of Phis does not matter. + if (MI->isPHI() && (*I)->getInstr()->isPHI()) + continue; + for (unsigned i = 0, e = MI->getNumOperands(); i < e; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg())) + continue; + unsigned Reg = MO.getReg(); + unsigned BasePos, OffsetPos; + if (ST.getInstrInfo()->getBaseAndOffsetPosition(MI, BasePos, OffsetPos)) + if (MI->getOperand(BasePos).getReg() == Reg) + if (unsigned NewReg = SSD->getInstrBaseReg(SU)) + Reg = NewReg; + bool Reads, Writes; + std::tie(Reads, Writes) = + (*I)->getInstr()->readsWritesVirtualRegister(Reg); + if (MO.isDef() && Reads && stageScheduled(*I) <= StageInst1) { + OrderBeforeUse = true; + MoveUse = Pos; + } else if (MO.isUse() && Writes && stageScheduled(*I) == StageInst1) { + if (cycleScheduled(*I) == cycleScheduled(SU) && !(*I)->isSucc(SU)) { + OrderBeforeUse = true; + MoveUse = Pos; + } else { + OrderAfterDef = true; + MoveDef = Pos; + } + } else if (MO.isUse() && Writes && stageScheduled(*I) > StageInst1) { + OrderBeforeUse = true; + MoveUse = Pos; + if (MoveUse != 0) { + OrderAfterDef = true; + MoveDef = Pos - 1; + } + } else if (MO.isUse() && stageScheduled(*I) == StageInst1 && + isLoopCarriedDefOfUse(SSD, (*I)->getInstr(), MO)) { + OrderBeforeDef = true; + MoveUse = Pos; + } + } + // Check for order dependences between instructions. Make sure the source + // is ordered before the destination. + for (auto &S : SU->Succs) + if (S.getKind() == SDep::Order && S.getSUnit() == *I) { + OrderBeforeUse = true; + MoveUse = Pos; + } + for (auto &P : SU->Preds) + if (P.getKind() == SDep::Order && P.getSUnit() == *I) { + OrderAfterDef = true; + MoveDef = Pos; + } + } + + // OrderAfterDef takes precedences over OrderBeforeDef. The latter is due + // to a loop-carried dependence. + if (OrderBeforeDef) + OrderBeforeUse = !OrderAfterDef; + + // The uncommon case when the instruction order needs to be updated because + // there is both a use and def. + if (OrderBeforeUse && OrderAfterDef) { + assert(MoveUse != MoveDef && "Need to move two instructions."); + SUnit *UseSU = Insts.at(MoveUse); + SUnit *DefSU = Insts.at(MoveDef); + if (MoveUse > MoveDef) { + Insts.erase(Insts.begin() + MoveUse); + Insts.erase(Insts.begin() + MoveDef); + } else { + Insts.erase(Insts.begin() + MoveDef); + Insts.erase(Insts.begin() + MoveUse); + } + if (orderDependence(SSD, UseSU, Insts)) { + Insts.push_front(SU); + orderDependence(SSD, DefSU, Insts); + return true; + } + Insts.pop_back(); + Insts.push_back(SU); + Insts.push_back(UseSU); + orderDependence(SSD, DefSU, Insts); + return false; + } + // Put the new instruction first if there is a use in the list. Otherwise, + // put it at the end of the list. + if (OrderBeforeUse) + Insts.push_front(SU); + else + Insts.push_back(SU); + return OrderBeforeUse; +} + +/// Return true if the scheduled Phi has a loop carried operand. +bool SMSchedule::isLoopCarried(SwingSchedulerDAG *SSD, MachineInstr *Phi) { + if (!Phi->isPHI()) + return false; + assert(Phi->isPHI() && "Expecing a Phi."); + SUnit *DefSU = SSD->getSUnit(Phi); + unsigned DefCycle = cycleScheduled(DefSU); + int DefStage = stageScheduled(DefSU); + + unsigned InitVal = 0; + unsigned LoopVal = 0; + getPhiRegs(Phi, Phi->getParent(), InitVal, LoopVal); + SUnit *UseSU = SSD->getSUnit(MRI.getVRegDef(LoopVal)); + if (!UseSU) + return true; + if (UseSU->getInstr()->isPHI()) + return true; + unsigned LoopCycle = cycleScheduled(UseSU); + int LoopStage = stageScheduled(UseSU); + return LoopCycle > DefCycle || + (LoopCycle <= DefCycle && LoopStage <= DefStage); +} + +/// Return true if the instruction is a definition that is loop carried +/// and defines the use on the next iteration. +/// v1 = phi(v2, v3) +/// (Def) v3 = op v1 +/// (MO) = v1 +/// If MO appears before Def, then then v1 and v3 may get assigned to the same +/// register. +bool SMSchedule::isLoopCarriedDefOfUse(SwingSchedulerDAG *SSD, + MachineInstr *Def, MachineOperand &MO) { + if (!MO.isReg()) + return false; + if (Def->isPHI()) + return false; + MachineInstr *Phi = MRI.getVRegDef(MO.getReg()); + if (!Phi || !Phi->isPHI() || Phi->getParent() != Def->getParent()) + return false; + if (!isLoopCarried(SSD, Phi)) + return false; + unsigned LoopReg = getLoopPhiReg(Phi, Phi->getParent()); + for (unsigned i = 0, e = Def->getNumOperands(); i != e; ++i) { + MachineOperand &DMO = Def->getOperand(i); + if (!DMO.isReg() || !DMO.isDef()) + continue; + if (DMO.getReg() == LoopReg) + return true; + } + return false; +} + +/// After the schedule has been formed, call this function to combine +/// the instructions from the different stages/cycles. That is, this +/// function creates a schedule that represents a single iteration. +void SMSchedule::finalizeSchedule(SwingSchedulerDAG *SSD) { + // Move all instructions to the first stage from later stages. + for (int cycle = getFirstCycle(); cycle <= getFinalCycle(); ++cycle) { + for (int stage = 1, lastStage = getMaxStageCount(); stage <= lastStage; + ++stage) { + std::deque &cycleInstrs = + ScheduledInstrs[cycle + (stage * InitiationInterval)]; + for (std::deque::reverse_iterator I = cycleInstrs.rbegin(), + E = cycleInstrs.rend(); + I != E; ++I) + 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; + + unsigned 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. + for (int cycle = getFinalCycle() + 1; cycle <= LastCycle; ++cycle) + ScheduledInstrs.erase(cycle); + + // Change the registers in instruction as specified in the InstrChanges + // map. We need to use the new registers to create the correct order. + for (int i = 0, e = SSD->SUnits.size(); i != e; ++i) { + SUnit *SU = &SSD->SUnits[i]; + SSD->applyInstrChange(SU->getInstr(), *this, true); + } + + // Reorder the instructions in each cycle to fix and improve the + // generated code. + for (int Cycle = getFirstCycle(), E = getFinalCycle(); Cycle <= E; ++Cycle) { + std::deque &cycleInstrs = ScheduledInstrs[Cycle]; + std::deque newOrderZC; + // Put the zero-cost, pseudo instructions at the start of the cycle. + for (unsigned i = 0, e = cycleInstrs.size(); i < e; ++i) { + SUnit *SU = cycleInstrs[i]; + if (ST.getInstrInfo()->isZeroCost(SU->getInstr()->getOpcode())) + orderDependence(SSD, SU, newOrderZC); + } + std::deque newOrderI; + // Then, add the regular instructions back. + for (unsigned i = 0, e = cycleInstrs.size(); i < e; ++i) { + SUnit *SU = cycleInstrs[i]; + if (!ST.getInstrInfo()->isZeroCost(SU->getInstr()->getOpcode())) + orderDependence(SSD, SU, newOrderI); + } + // Replace the old order with the new order. + cycleInstrs.swap(newOrderZC); + cycleInstrs.insert(cycleInstrs.end(), newOrderI.begin(), newOrderI.end()); + } + + DEBUG(dump();); +} + +/// Print the schedule information to the given output. +void SMSchedule::print(raw_ostream &os) const { + // Iterate over each cycle. + for (int cycle = getFirstCycle(); cycle <= getFinalCycle(); ++cycle) { + // Iterate over each instruction in the cycle. + const_sched_iterator cycleInstrs = ScheduledInstrs.find(cycle); + for (SUnit *CI : cycleInstrs->second) { + os << "cycle " << cycle << " (" << stageScheduled(CI) << ") "; + os << "(" << CI->NodeNum << ") "; + CI->getInstr()->print(os); + os << "\n"; + } + } +} + +/// Utility function used for debugging to print the schedule. +void SMSchedule::dump() const { print(dbgs()); } Index: lib/Target/Hexagon/HexagonInstrInfo.h =================================================================== --- lib/Target/Hexagon/HexagonInstrInfo.h +++ lib/Target/Hexagon/HexagonInstrInfo.h @@ -103,6 +103,22 @@ MachineBasicBlock *FBB, ArrayRef Cond, const DebugLoc &DL) const override; + /// Analyze the loop code, return true if it cannot be understood. Upon + /// success, this function returns false and returns information about the + /// induction variable and compare instruction used at the end. + bool analyzeLoop(MachineLoop &L, MachineInstr *&IndVarInst, + MachineInstr *&CmpInst) const override; + + /// Generate code to reduce the loop iteration by one and check if the loop is + /// finished. Return the value/register of the the new loop count. We need + /// this function when peeling off one or more iterations of a loop. This + /// function assumes the nth iteration is peeled first. + unsigned reduceLoopCount(MachineBasicBlock &MBB, + MachineInstr *IndVar, MachineInstr *Cmp, + SmallVectorImpl &Cond, + SmallVectorImpl &PrevInsts, + unsigned Iter, unsigned MaxIter) const override; + /// Return true if it's profitable to predicate /// instructions with accumulated instruction latency of "NumCycles" /// of the specified basic block, where the probability of the instructions @@ -172,6 +188,11 @@ /// anything was changed. bool expandPostRAPseudo(MachineBasicBlock::iterator MI) const override; + /// \brief Get the base register and byte offset of a load/store instr. + bool getMemOpBaseRegImmOfs(MachineInstr *LdSt, unsigned &BaseReg, + int64_t &Offset, + const TargetRegisterInfo *TRI) const override; + /// Reverses the branch condition of the specified condition list, /// returning false on success and true if it cannot be reversed. bool ReverseBranchCondition(SmallVectorImpl &Cond) @@ -249,6 +270,14 @@ AliasAnalysis *AA = nullptr) const override; + /// For instructions with a base and offset, return the position of the + /// base register and offset operands. + bool getBaseAndOffsetPosition(const MachineInstr *MI, unsigned &BasePos, + unsigned &OffsetPos) const override; + + /// If the instruction is an increment of a constant value, return the amount. + bool getIncrementValue(const MachineInstr *MI, int &Value) const override; + /// HexagonInstrInfo specifics. /// @@ -299,7 +328,7 @@ bool isNewValueStore(const MachineInstr* MI) const; bool isNewValueStore(unsigned Opcode) const; bool isOperandExtended(const MachineInstr *MI, unsigned OperandNum) const; - bool isPostIncrement(const MachineInstr* MI) const; + bool isPostIncrement(const MachineInstr* MI) const override; bool isPredicatedNew(const MachineInstr &MI) const; bool isPredicatedNew(unsigned Opcode) const; bool isPredicatedTrue(const MachineInstr &MI) const; @@ -346,8 +375,6 @@ unsigned getAddrMode(const MachineInstr* MI) const; unsigned getBaseAndOffset(const MachineInstr *MI, int &Offset, unsigned &AccessSize) const; - bool getBaseAndOffsetPosition(const MachineInstr *MI, unsigned &BasePos, - unsigned &OffsetPos) const; short getBaseWithLongOffset(short Opcode) const; short getBaseWithLongOffset(const MachineInstr *MI) const; short getBaseWithRegOffset(const MachineInstr *MI) const; Index: lib/Target/Hexagon/HexagonInstrInfo.cpp =================================================================== --- lib/Target/Hexagon/HexagonInstrInfo.cpp +++ lib/Target/Hexagon/HexagonInstrInfo.cpp @@ -657,6 +657,85 @@ return 2; } +/// Analyze the loop code to find the loop induction variable and compare used +/// to compute the number of iterations. Currently, we analyze loop that are +/// controlled using hardware loops. In this case, the induction variable +/// instruction is null. For all other cases, this function returns true, which +/// means we're unable to analyze it. +bool HexagonInstrInfo::analyzeLoop(MachineLoop &L, + MachineInstr *&IndVarInst, + MachineInstr *&CmpInst) const { + + MachineBasicBlock *LoopEnd = L.getBottomBlock(); + MachineBasicBlock::iterator I = LoopEnd->getFirstTerminator(); + // We really "analyze" only hardware loops right now. + if (I != LoopEnd->end() && isEndLoopN(I->getOpcode())) { + IndVarInst = nullptr; + CmpInst = I; + return false; + } + return true; +} + +/// Generate code to reduce the loop iteration by one and check if the loop is +/// finished. Return the value/register of the new loop count. this function +/// assumes the nth iteration is peeled first. +unsigned HexagonInstrInfo::reduceLoopCount(MachineBasicBlock &MBB, + MachineInstr *IndVar, MachineInstr *Cmp, + SmallVectorImpl &Cond, + SmallVectorImpl &PrevInsts, + unsigned Iter, unsigned MaxIter) const { + // We expect a hardware loop currently. This means that IndVar is set + // to null, and the compare is the ENDLOOP instruction. + assert((!IndVar) && isEndLoopN(Cmp->getOpcode()) + && "Expecting a hardware loop"); + MachineFunction *MF = MBB.getParent(); + DebugLoc DL = Cmp->getDebugLoc(); + SmallPtrSet VisitedBBs; + MachineInstr *Loop = findLoopInstr(&MBB, Cmp->getOpcode(), VisitedBBs); + if (!Loop) + return 0; + // If the loop trip count is a compile-time value, then just change the + // value. + if (Loop->getOpcode() == Hexagon::J2_loop0i || + Loop->getOpcode() == Hexagon::J2_loop1i) { + int64_t Offset = Loop->getOperand(1).getImm(); + if (Offset <= 1) + Loop->eraseFromParent(); + else + Loop->getOperand(1).setImm(Offset - 1); + return Offset - 1; + } + // The loop trip count is a run-time value. We generate code to subtract + // one from the trip count, and update the loop instruction. + assert(Loop->getOpcode() == Hexagon::J2_loop0r && "Unexpected instruction"); + unsigned LoopCount = Loop->getOperand(1).getReg(); + // Check if we're done with the loop. + unsigned LoopEnd = createVR(MF, MVT::i1); + MachineInstr *NewCmp = BuildMI(&MBB, DL, get(Hexagon::C2_cmpgtui), LoopEnd). + addReg(LoopCount).addImm(1); + unsigned NewLoopCount = createVR(MF, MVT::i32); + MachineInstr *NewAdd = BuildMI(&MBB, DL, get(Hexagon::A2_addi), NewLoopCount). + addReg(LoopCount).addImm(-1); + // Update the previously generated instructions with the new loop counter. + for (SmallVectorImpl::iterator I = PrevInsts.begin(), + E = PrevInsts.end(); I != E; ++I) + (*I)->substituteRegister(LoopCount, NewLoopCount, 0, getRegisterInfo()); + PrevInsts.clear(); + PrevInsts.push_back(NewCmp); + PrevInsts.push_back(NewAdd); + // Insert the new loop instruction if this is the last time the loop is + // decremented. + if (Iter == MaxIter) + BuildMI(&MBB, DL, get(Hexagon::J2_loop0r)). + addMBB(Loop->getOperand(0).getMBB()).addReg(NewLoopCount); + // Delete the old loop instruction. + if (Iter == 0) + Loop->eraseFromParent(); + Cond.push_back(MachineOperand::CreateImm(Hexagon::J2_jumpf)); + Cond.push_back(NewCmp->getOperand(0)); + return NewLoopCount; +} bool HexagonInstrInfo::isProfitableToIfCvt(MachineBasicBlock &MBB, unsigned NumCycles, unsigned ExtraPredCycles, @@ -1565,6 +1644,22 @@ } +/// If the instruction is an increment of a constant value, return the amount. +bool HexagonInstrInfo::getIncrementValue(const MachineInstr *MI, + int &Value) const { + if (isPostIncrement(MI)) { + unsigned AccessSize; + return getBaseAndOffset(MI, Value, AccessSize); + } + if (MI->getOpcode() == Hexagon::A2_addi) { + Value = MI->getOperand(2).getImm(); + return true; + } + + return false; +} + + unsigned HexagonInstrInfo::createVR(MachineFunction* MF, MVT VT) const { MachineRegisterInfo &MRI = MF->getRegInfo(); const TargetRegisterClass *TRC; @@ -2804,6 +2899,18 @@ } +/// \brief Get the base register and byte offset of a load/store instr. +bool HexagonInstrInfo::getMemOpBaseRegImmOfs(MachineInstr *LdSt, + unsigned &BaseReg, int64_t &Offset, const TargetRegisterInfo *TRI) + const { + unsigned AccessSize = 0; + int OffsetVal = 0; + BaseReg = getBaseAndOffset(LdSt, OffsetVal, AccessSize); + Offset = OffsetVal; + return BaseReg != 0; +} + + /// \brief Can these instructions execute at the same time in a bundle. bool HexagonInstrInfo::canExecuteInBundle(const MachineInstr *First, const MachineInstr *Second) const { Index: lib/Target/Hexagon/HexagonTargetMachine.cpp =================================================================== --- lib/Target/Hexagon/HexagonTargetMachine.cpp +++ lib/Target/Hexagon/HexagonTargetMachine.cpp @@ -27,7 +27,6 @@ using namespace llvm; - static cl::opt EnableRDFOpt("rdf-opt", cl::Hidden, cl::ZeroOrMore, cl::init(true), cl::desc("Enable RDF-based optimizations")); @@ -277,6 +276,8 @@ if (!DisableHardwareLoops) addPass(createHexagonHardwareLoops(), false); } + if (TM->getOptLevel() >= CodeGenOpt::Default) + addPass(&MachinePipelinerID); } void HexagonPassConfig::addPostRegAlloc() { Index: test/CodeGen/Hexagon/swp-const-tc.ll =================================================================== --- /dev/null +++ test/CodeGen/Hexagon/swp-const-tc.ll @@ -0,0 +1,51 @@ +; RUN: llc -march=hexagon -mcpu=hexagonv5 -enable-pipeliner -verify-machineinstrs < %s | FileCheck %s + +; If the trip count is a compile-time constant, then decrement it instead +; of computing a new LC0 value. + +; CHECK-LABEL: @test +; CHECK: loop0(.LBB0_1, #998) + +define i32 @test(i32* %A, i32* %B, i32 %count) { +entry: + br label %for.body + +for.body: + %sum.02 = phi i32 [ 0, %entry ], [ %add, %for.body ] + %arrayidx.phi = phi i32* [ %A, %entry ], [ %arrayidx.inc, %for.body ] + %i.01 = phi i32 [ 0, %entry ], [ %inc, %for.body ] + %0 = load i32, i32* %arrayidx.phi, align 4 + %add = add nsw i32 %0, %sum.02 + %inc = add nsw i32 %i.01, 1 + %exitcond = icmp eq i32 %inc, 1000 + %arrayidx.inc = getelementptr i32, i32* %arrayidx.phi, i32 1 + br i1 %exitcond, label %for.end, label %for.body + +for.end: + ret i32 %add +} + +; The constant trip count is small enough that the kernel is not executed. + +; CHECK-LABEL: @test1 +; CHECK-NOT: loop0( + +define i32 @test1(i32* %A, i32* %B, i32 %count) { +entry: + br label %for.body + +for.body: + %sum.02 = phi i32 [ 0, %entry ], [ %add, %for.body ] + %arrayidx.phi = phi i32* [ %A, %entry ], [ %arrayidx.inc, %for.body ] + %i.01 = phi i32 [ 0, %entry ], [ %inc, %for.body ] + %0 = load i32, i32* %arrayidx.phi, align 4 + %add = add nsw i32 %0, %sum.02 + %inc = add nsw i32 %i.01, 1 + %exitcond = icmp eq i32 %inc, 1 + %arrayidx.inc = getelementptr i32, i32* %arrayidx.phi, i32 1 + br i1 %exitcond, label %for.end, label %for.body + +for.end: + ret i32 %add +} + Index: test/CodeGen/Hexagon/swp-dag-phi.ll =================================================================== --- /dev/null +++ test/CodeGen/Hexagon/swp-dag-phi.ll @@ -0,0 +1,42 @@ +; RUN: llc -march=hexagon -mcpu=hexagonv5 -enable-pipeliner -pipeliner-max-stages=2 < %s +; REQUIRES: asserts + +; This tests check that a dependence is created between a Phi and it's uses. +; An assert occurs if the Phi dependences are not correct. + +define void @test1(i32* %f2, i32 %nc) { +entry: + %i.011 = add i32 %nc, -1 + %cmp12 = icmp sgt i32 %i.011, 1 + br i1 %cmp12, label %for.body.preheader, label %for.end + +for.body.preheader: + %0 = add i32 %nc, -2 + %scevgep = getelementptr i32, i32* %f2, i32 %0 + %sri = load i32, i32* %scevgep, align 4 + %scevgep15 = getelementptr i32, i32* %f2, i32 %i.011 + %sri16 = load i32, i32* %scevgep15, align 4 + br label %for.body + +for.body: + %i.014 = phi i32 [ %i.0, %for.body ], [ %i.011, %for.body.preheader ] + %i.0.in13 = phi i32 [ %i.014, %for.body ], [ %nc, %for.body.preheader ] + %sr = phi i32 [ %1, %for.body ], [ %sri, %for.body.preheader ] + %sr17 = phi i32 [ %sr, %for.body ], [ %sri16, %for.body.preheader ] + %arrayidx = getelementptr inbounds i32, i32* %f2, i32 %i.014 + %sub1 = add nsw i32 %i.0.in13, -3 + %arrayidx2 = getelementptr inbounds i32, i32* %f2, i32 %sub1 + %1 = load i32, i32* %arrayidx2, align 4 + %sub3 = sub nsw i32 %sr17, %1 + store i32 %sub3, i32* %arrayidx, align 4 + %i.0 = add nsw i32 %i.014, -1 + %cmp = icmp sgt i32 %i.0, 1 + br i1 %cmp, label %for.body, label %for.end.loopexit + +for.end.loopexit: + br label %for.end + +for.end: + ret void +} + Index: test/CodeGen/Hexagon/swp-epilog-reuse.ll =================================================================== --- /dev/null +++ test/CodeGen/Hexagon/swp-epilog-reuse.ll @@ -0,0 +1,65 @@ +; RUN: llc -fp-contract=fast -O3 -march=hexagon -mcpu=hexagonv5 < %s +; REQUIRES: asserts + +; Test that the pipeliner doesn't ICE due because the PHI generation +; code in the epilog does not attempt to reuse an existing PHI. + +define void @test(float* noalias %srcImg, i32 %width, float* noalias %dstImg) { +entry.split: + %shr = lshr i32 %width, 1 + %incdec.ptr253 = getelementptr inbounds float, float* %dstImg, i32 2 + br i1 undef, label %for.body, label %for.end + +for.body: + %dst.21518.reg2mem.0 = phi float* [ null, %while.end712 ], [ %incdec.ptr253, %entry.split ] + %dstEnd.01519 = phi float* [ %add.ptr725, %while.end712 ], [ undef, %entry.split ] + %add.ptr367 = getelementptr inbounds float, float* %srcImg, i32 undef + %dst.31487 = getelementptr inbounds float, float* %dst.21518.reg2mem.0, i32 1 + br i1 undef, label %while.body661.preheader, label %while.end712 + +while.body661.preheader: + %scevgep1941 = getelementptr float, float* %add.ptr367, i32 1 + br label %while.body661.ur + +while.body661.ur: + %lsr.iv1942 = phi float* [ %scevgep1941, %while.body661.preheader ], [ undef, %while.body661.ur ] + %col1.31508.reg2mem.0.ur = phi float [ %col3.31506.reg2mem.0.ur, %while.body661.ur ], [ undef, %while.body661.preheader ] + %col4.31507.reg2mem.0.ur = phi float [ %add710.ur, %while.body661.ur ], [ 0.000000e+00, %while.body661.preheader ] + %col3.31506.reg2mem.0.ur = phi float [ %add689.ur, %while.body661.ur ], [ undef, %while.body661.preheader ] + %dst.41511.ur = phi float* [ %incdec.ptr674.ur, %while.body661.ur ], [ %dst.31487, %while.body661.preheader ] + %mul662.ur = fmul float %col1.31508.reg2mem.0.ur, 4.000000e+00 + %add663.ur = fadd float undef, %mul662.ur + %add665.ur = fadd float %add663.ur, undef + %add667.ur = fadd float undef, %add665.ur + %add669.ur = fadd float undef, %add667.ur + %add670.ur = fadd float %col4.31507.reg2mem.0.ur, %add669.ur + %conv673.ur = fmul float %add670.ur, 3.906250e-03 + %incdec.ptr674.ur = getelementptr inbounds float, float* %dst.41511.ur, i32 1 + store float %conv673.ur, float* %dst.41511.ur, align 4 + %scevgep1959 = getelementptr float, float* %lsr.iv1942, i32 -1 + %0 = load float, float* %scevgep1959, align 4 + %mul680.ur = fmul float %0, 4.000000e+00 + %add681.ur = fadd float undef, %mul680.ur + %add684.ur = fadd float undef, %add681.ur + %add687.ur = fadd float undef, %add684.ur + %add689.ur = fadd float undef, %add687.ur + %add699.ur = fadd float undef, undef + %add703.ur = fadd float undef, %add699.ur + %add707.ur = fadd float undef, %add703.ur + %add710.ur = fadd float undef, %add707.ur + %cmp660.ur = icmp ult float* %incdec.ptr674.ur, %dstEnd.01519 + br i1 %cmp660.ur, label %while.body661.ur, label %while.end712 + +while.end712: + %dst.4.lcssa.reg2mem.0 = phi float* [ %dst.31487, %for.body ], [ undef, %while.body661.ur ] + %conv721 = fpext float undef to double + %mul722 = fmul double %conv721, 0x3F7111112119E8FB + %conv723 = fptrunc double %mul722 to float + store float %conv723, float* %dst.4.lcssa.reg2mem.0, align 4 + %add.ptr725 = getelementptr inbounds float, float* %dstEnd.01519, i32 %shr + %cmp259 = icmp ult i32 undef, undef + br i1 %cmp259, label %for.body, label %for.end + +for.end: + ret void +} Index: test/CodeGen/Hexagon/swp-matmul-bitext.ll =================================================================== --- /dev/null +++ test/CodeGen/Hexagon/swp-matmul-bitext.ll @@ -0,0 +1,75 @@ +; RUN: llc -march=hexagon -mcpu=hexagonv60 -enable-bsb-sched=0 -enable-pipeliner < %s | FileCheck %s +; RUN: llc -march=hexagon -mcpu=hexagonv5 -enable-pipeliner < %s | FileCheck %s + +; From coremark. Test that we pipeline the matrix multiplication bitextract +; function. The pipelined code should have two packets. + +; CHECK: loop0(.LBB0_[[LOOP:.]], +; CHECK: .LBB0_[[LOOP]]: +; CHECK: = extractu([[REG2:(r[0-9]+)]], +; CHECK: = extractu([[REG2]], +; CHECK: [[REG0:(r[0-9]+)]] = memh +; CHECK: [[REG1:(r[0-9]+)]] = memh +; CHECK: += mpyi +; CHECK: [[REG2]] = mpyi([[REG0]], [[REG1]]) +; CHECK: endloop0 + +%union_h2_sem_t = type { i32 } + +@sem_i = common global [0 x %union_h2_sem_t] zeroinitializer, align 4 + +define void @matrix_mul_matrix_bitextract(i32 %N, i32* %C, i16* %A, i16* %B) { +entry: + %cmp53 = icmp eq i32 %N, 0 + br i1 %cmp53, label %for_end27, label %for_body3_lr_ph_us + +for_body3_lr_ph_us: + %i_054_us = phi i32 [ %inc26_us, %for_cond1_for_inc25_crit_edge_us ], [ 0, %entry ] + %0 = mul i32 %i_054_us, %N + %arrayidx9_us_us_gep = getelementptr i16, i16* %A, i32 %0 + br label %for_body3_us_us + +for_cond1_for_inc25_crit_edge_us: + %inc26_us = add i32 %i_054_us, 1 + %exitcond89 = icmp eq i32 %inc26_us, %N + br i1 %exitcond89, label %for_end27, label %for_body3_lr_ph_us + +for_body3_us_us: + %j_052_us_us = phi i32 [ %inc23_us_us, %for_cond4_for_inc22_crit_edge_us_us ], [ 0, %for_body3_lr_ph_us ] + %add_us_us = add i32 %j_052_us_us, %0 + %arrayidx_us_us = getelementptr inbounds i32, i32* %C, i32 %add_us_us + store i32 0, i32* %arrayidx_us_us, align 4 + br label %for_body6_us_us + +for_cond4_for_inc22_crit_edge_us_us: + store i32 %add21_us_us, i32* %arrayidx_us_us, align 4 + %inc23_us_us = add i32 %j_052_us_us, 1 + %exitcond88 = icmp eq i32 %inc23_us_us, %N + br i1 %exitcond88, label %for_cond1_for_inc25_crit_edge_us, label %for_body3_us_us + +for_body6_us_us: + %1 = phi i32 [ 0, %for_body3_us_us ], [ %add21_us_us, %for_body6_us_us ] + %arrayidx9_us_us_phi = phi i16* [ %arrayidx9_us_us_gep, %for_body3_us_us ], [ %arrayidx9_us_us_inc, %for_body6_us_us ] + %k_050_us_us = phi i32 [ 0, %for_body3_us_us ], [ %inc_us_us, %for_body6_us_us ] + %2 = load i16, i16* %arrayidx9_us_us_phi, align 2 + %conv_us_us = sext i16 %2 to i32 + %mul10_us_us = mul i32 %k_050_us_us, %N + %add11_us_us = add i32 %mul10_us_us, %j_052_us_us + %arrayidx12_us_us = getelementptr inbounds i16, i16* %B, i32 %add11_us_us + %3 = load i16, i16* %arrayidx12_us_us, align 2 + %conv13_us_us = sext i16 %3 to i32 + %mul14_us_us = mul nsw i32 %conv13_us_us, %conv_us_us + %shr47_us_us = lshr i32 %mul14_us_us, 2 + %and_us_us = and i32 %shr47_us_us, 15 + %shr1548_us_us = lshr i32 %mul14_us_us, 5 + %and16_us_us = and i32 %shr1548_us_us, 127 + %mul17_us_us = mul i32 %and_us_us, %and16_us_us + %add21_us_us = add i32 %mul17_us_us, %1 + %inc_us_us = add i32 %k_050_us_us, 1 + %exitcond87 = icmp eq i32 %inc_us_us, %N + %arrayidx9_us_us_inc = getelementptr i16, i16* %arrayidx9_us_us_phi, i32 1 + br i1 %exitcond87, label %for_cond4_for_inc22_crit_edge_us_us, label %for_body6_us_us + +for_end27: + ret void +} Index: test/CodeGen/Hexagon/swp-max.ll =================================================================== --- /dev/null +++ test/CodeGen/Hexagon/swp-max.ll @@ -0,0 +1,42 @@ +; RUN: llc -march=hexagon -mcpu=hexagonv5 -enable-pipeliner \ +; RUN: -pipeliner-max-stages=2 < %s | FileCheck %s + +@A = global [8 x i32] [i32 4, i32 -3, i32 5, i32 -2, i32 -1, i32 2, i32 6, i32 -2], align 8 + +define i32 @test(i32 %Left, i32 %Right) { +entry: + %add = add nsw i32 %Right, %Left + %div = sdiv i32 %add, 2 + %cmp9 = icmp slt i32 %div, %Left + br i1 %cmp9, label %for.end, label %for.body.preheader + +for.body.preheader: + br label %for.body + +; CHECK: loop0(.LBB0_[[LOOP:.]], +; CHECK: .LBB0_[[LOOP]]: +; CHECK: [[REG1:(r[0-9]+)]] = max(r{{[0-9]+}}, [[REG1]]) +; CHECK: [[REG0:(r[0-9]+)]] = add([[REG2:(r[0-9]+)]], [[REG0]]) +; CHECK: [[REG2]] = memw +; CHECK: endloop0 + +for.body: + %MaxLeftBorderSum.012 = phi i32 [ %MaxLeftBorderSum.1, %for.body ], [ 0, %for.body.preheader ] + %i.011 = phi i32 [ %dec, %for.body ], [ %div, %for.body.preheader ] + %LeftBorderSum.010 = phi i32 [ %add1, %for.body ], [ 0, %for.body.preheader ] + %arrayidx = getelementptr inbounds [8 x i32], [8 x i32]* @A, i32 0, i32 %i.011 + %0 = load i32, i32* %arrayidx, align 4 + %add1 = add nsw i32 %0, %LeftBorderSum.010 + %cmp2 = icmp sgt i32 %add1, %MaxLeftBorderSum.012 + %MaxLeftBorderSum.1 = select i1 %cmp2, i32 %add1, i32 %MaxLeftBorderSum.012 + %dec = add nsw i32 %i.011, -1 + %cmp = icmp slt i32 %dec, %Left + br i1 %cmp, label %for.end.loopexit, label %for.body + +for.end.loopexit: + br label %for.end + +for.end: + %MaxLeftBorderSum.0.lcssa = phi i32 [ 0, %entry ], [ %MaxLeftBorderSum.1, %for.end.loopexit ] + ret i32 %MaxLeftBorderSum.0.lcssa +} Index: test/CodeGen/Hexagon/swp-multi-loops.ll =================================================================== --- /dev/null +++ test/CodeGen/Hexagon/swp-multi-loops.ll @@ -0,0 +1,75 @@ +; RUN: llc -march=hexagon -mcpu=hexagonv5 -enable-pipeliner < %s | FileCheck %s + +; Make sure we attempt to pipeline all inner most loops. + +; Check if the first loop is pipelined. +; CHECK: loop0(.LBB0_[[LOOP:.]], +; CHECK: .LBB0_[[LOOP]]: +; CHECK: add(r{{[0-9]+}}, r{{[0-9]+}}) +; CHECK-NEXT: memw(r{{[0-9]+}}{{.*}}++{{.*}}#4) +; CHECK-NEXT: endloop0 + +; Check if the second loop is pipelined. +; CHECK: loop0(.LBB0_[[LOOP:.]], +; CHECK: .LBB0_[[LOOP]]: +; CHECK: add(r{{[0-9]+}}, r{{[0-9]+}}) +; CHECK-NEXT: memw(r{{[0-9]+}}{{.*}}++{{.*}}#4) +; CHECK-NEXT: endloop0 + +define i32 @test(i32* %a, i32 %n, i32 %l) { +entry: + %cmp23 = icmp sgt i32 %n, 0 + br i1 %cmp23, label %for.body3.lr.ph.preheader, label %for.end14 + +for.body3.lr.ph.preheader: + br label %for.body3.lr.ph + +for.body3.lr.ph: + %sum1.026 = phi i32 [ %add8, %for.inc12 ], [ 0, %for.body3.lr.ph.preheader ] + %sum.025 = phi i32 [ %add, %for.inc12 ], [ 0, %for.body3.lr.ph.preheader ] + %j.024 = phi i32 [ %inc13, %for.inc12 ], [ 0, %for.body3.lr.ph.preheader ] + br label %for.body3 + +for.body3: + %sum.118 = phi i32 [ %sum.025, %for.body3.lr.ph ], [ %add, %for.body3 ] + %arrayidx.phi = phi i32* [ %a, %for.body3.lr.ph ], [ %arrayidx.inc, %for.body3 ] + %i.017 = phi i32 [ 0, %for.body3.lr.ph ], [ %inc, %for.body3 ] + %0 = load i32, i32* %arrayidx.phi, align 4 + %add = add nsw i32 %0, %sum.118 + %inc = add nsw i32 %i.017, 1 + %exitcond = icmp eq i32 %inc, %n + %arrayidx.inc = getelementptr i32, i32* %arrayidx.phi, i32 1 + br i1 %exitcond, label %for.end, label %for.body3 + +for.end: + tail call void @bar(i32* %a) #2 + br label %for.body6 + +for.body6: + %sum1.121 = phi i32 [ %sum1.026, %for.end ], [ %add8, %for.body6 ] + %arrayidx7.phi = phi i32* [ %a, %for.end ], [ %arrayidx7.inc, %for.body6 ] + %i.120 = phi i32 [ 0, %for.end ], [ %inc10, %for.body6 ] + %1 = load i32, i32* %arrayidx7.phi, align 4 + %add8 = add nsw i32 %1, %sum1.121 + %inc10 = add nsw i32 %i.120, 1 + %exitcond29 = icmp eq i32 %inc10, %n + %arrayidx7.inc = getelementptr i32, i32* %arrayidx7.phi, i32 1 + br i1 %exitcond29, label %for.inc12, label %for.body6 + +for.inc12: + %inc13 = add nsw i32 %j.024, 1 + %exitcond30 = icmp eq i32 %inc13, %n + br i1 %exitcond30, label %for.end14.loopexit, label %for.body3.lr.ph + +for.end14.loopexit: + br label %for.end14 + +for.end14: + %sum1.0.lcssa = phi i32 [ 0, %entry ], [ %add8, %for.end14.loopexit ] + %sum.0.lcssa = phi i32 [ 0, %entry ], [ %add, %for.end14.loopexit ] + %add15 = add nsw i32 %sum1.0.lcssa, %sum.0.lcssa + ret i32 %add15 +} + +declare void @bar(i32*) + Index: test/CodeGen/Hexagon/swp-vect-dotprod.ll =================================================================== --- /dev/null +++ test/CodeGen/Hexagon/swp-vect-dotprod.ll @@ -0,0 +1,41 @@ +; RUN: llc -march=hexagon -mcpu=hexagonv5 -enable-pipeliner < %s | FileCheck %s +; RUN: llc -march=hexagon -mcpu=hexagonv5 -O2 < %s | FileCheck %s +; RUN: llc -march=hexagon -mcpu=hexagonv5 -O3 < %s | FileCheck %s +; +; Check that we pipeline a vectorized dot product in a single packet. +; +; CHECK: { +; CHECK: += mpyi +; CHECK: += mpyi +; CHECK: memd +; CHECK: memd +; CHECK: } :endloop0 + +@a = common global [5000 x i32] zeroinitializer, align 8 +@b = common global [5000 x i32] zeroinitializer, align 8 + +define i32 @vecMultGlobal() { +entry: + br label %polly.loop_body + +polly.loop_after: + %0 = extractelement <2 x i32> %addp_vec, i32 0 + %1 = extractelement <2 x i32> %addp_vec, i32 1 + %add_sum = add i32 %0, %1 + ret i32 %add_sum + +polly.loop_body: + %polly.loopiv13 = phi i32 [ 0, %entry ], [ %polly.next_loopiv, %polly.loop_body ] + %reduction.012 = phi <2 x i32> [ zeroinitializer, %entry ], [ %addp_vec, %polly.loop_body ] + %polly.next_loopiv = add nsw i32 %polly.loopiv13, 2 + %p_arrayidx1 = getelementptr [5000 x i32], [5000 x i32]* @b, i32 0, i32 %polly.loopiv13 + %p_arrayidx = getelementptr [5000 x i32], [5000 x i32]* @a, i32 0, i32 %polly.loopiv13 + %vector_ptr = bitcast i32* %p_arrayidx1 to <2 x i32>* + %_p_vec_full = load <2 x i32>, <2 x i32>* %vector_ptr, align 8 + %vector_ptr7 = bitcast i32* %p_arrayidx to <2 x i32>* + %_p_vec_full8 = load <2 x i32>, <2 x i32>* %vector_ptr7, align 8 + %mulp_vec = mul <2 x i32> %_p_vec_full8, %_p_vec_full + %addp_vec = add <2 x i32> %mulp_vec, %reduction.012 + %2 = icmp slt i32 %polly.next_loopiv, 5000 + br i1 %2, label %polly.loop_body, label %polly.loop_after +} Index: test/CodeGen/Hexagon/swp-vmult.ll =================================================================== --- /dev/null +++ test/CodeGen/Hexagon/swp-vmult.ll @@ -0,0 +1,33 @@ +; RUN: llc -march=hexagon -mcpu=hexagonv5 -enable-pipeliner < %s | FileCheck %s +; RUN: llc -march=hexagon -mcpu=hexagonv5 -O3 < %s | FileCheck %s + +; Multiply and accumulate +; CHECK: mpyi([[REG0:r([0-9]+)]], [[REG1:r([0-9]+)]]) +; CHECK-NEXT: add(r{{[0-9]+}}, #4) +; CHECK-NEXT: [[REG0]] = memw(r{{[0-9]+}} + r{{[0-9]+}}<<#0) +; CHECK-NEXT: [[REG1]] = memw(r{{[0-9]+}} + r{{[0-9]+}}<<#0) +; CHECK-NEXT: endloop0 + +define i32 @foo(i32* %a, i32* %b, i32 %n) { +entry: + br label %for.body + +for.body: + %sum.03 = phi i32 [ 0, %entry ], [ %add, %for.body ] + %arrayidx.phi = phi i32* [ %a, %entry ], [ %arrayidx.inc, %for.body ] + %arrayidx1.phi = phi i32* [ %b, %entry ], [ %arrayidx1.inc, %for.body ] + %i.02 = phi i32 [ 0, %entry ], [ %inc, %for.body ] + %0 = load i32, i32* %arrayidx.phi, align 4 + %1 = load i32, i32* %arrayidx1.phi, align 4 + %mul = mul nsw i32 %1, %0 + %add = add nsw i32 %mul, %sum.03 + %inc = add nsw i32 %i.02, 1 + %exitcond = icmp eq i32 %inc, 10000 + %arrayidx.inc = getelementptr i32, i32* %arrayidx.phi, i32 1 + %arrayidx1.inc = getelementptr i32, i32* %arrayidx1.phi, i32 1 + br i1 %exitcond, label %for.end, label %for.body + +for.end: + ret i32 %add +} + Index: test/CodeGen/Hexagon/swp-vsum.ll =================================================================== --- /dev/null +++ test/CodeGen/Hexagon/swp-vsum.ll @@ -0,0 +1,29 @@ +; RUN: llc -march=hexagon -mcpu=hexagonv5 -enable-pipeliner < %s | FileCheck %s +; RUN: llc -march=hexagon -mcpu=hexagonv5 -O3 < %s | FileCheck %s + +; Simple vector total. +; CHECK: loop0(.LBB0_[[LOOP:.]], +; CHECK: .LBB0_[[LOOP]]: +; CHECK: add([[REG:r([0-9]+)]], r{{[0-9]+}}) +; CHECK-NEXT: add(r{{[0-9]+}}, #4) +; CHECK-NEXT: [[REG]] = memw(r{{[0-9]+}} + r{{[0-9]+}}<<#0) +; CHECK-NEXT: endloop0 + +define i32 @foo(i32* %a, i32 %n) { +entry: + br label %for.body + +for.body: + %sum.02 = phi i32 [ 0, %entry ], [ %add, %for.body ] + %arrayidx.phi = phi i32* [ %a, %entry ], [ %arrayidx.inc, %for.body ] + %i.01 = phi i32 [ 0, %entry ], [ %inc, %for.body ] + %0 = load i32, i32* %arrayidx.phi, align 4 + %add = add nsw i32 %0, %sum.02 + %inc = add nsw i32 %i.01, 1 + %exitcond = icmp eq i32 %inc, 10000 + %arrayidx.inc = getelementptr i32, i32* %arrayidx.phi, i32 1 + br i1 %exitcond, label %for.end, label %for.body + +for.end: + ret i32 %add +}