diff options
Diffstat (limited to 'contrib/llvm/lib/CodeGen/MachinePipeliner.cpp')
| -rw-r--r-- | contrib/llvm/lib/CodeGen/MachinePipeliner.cpp | 3984 |
1 files changed, 3984 insertions, 0 deletions
diff --git a/contrib/llvm/lib/CodeGen/MachinePipeliner.cpp b/contrib/llvm/lib/CodeGen/MachinePipeliner.cpp new file mode 100644 index 0000000..43a1809 --- /dev/null +++ b/contrib/llvm/lib/CodeGen/MachinePipeliner.cpp @@ -0,0 +1,3984 @@ +//===-- 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/ArrayRef.h" +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/iterator_range.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/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/MemoryLocation.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/MachineFunction.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/CodeGen/MachineInstrBundle.h" +#include "llvm/CodeGen/MachineLoopInfo.h" +#include "llvm/CodeGen/MachineMemOperand.h" +#include "llvm/CodeGen/MachineOperand.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/RegisterClassInfo.h" +#include "llvm/CodeGen/RegisterPressure.h" +#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/ScheduleDAGInstrs.h" +#include "llvm/CodeGen/ScheduleDAGMutation.h" +#include "llvm/IR/Attributes.h" +#include "llvm/IR/DebugLoc.h" +#include "llvm/MC/MCInstrItineraries.h" +#include "llvm/PassAnalysisSupport.h" +#include "llvm/PassRegistry.h" +#include "llvm/PassSupport.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/MathExtras.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" +#include <algorithm> +#include <cassert> +#include <climits> +#include <cstdint> +#include <deque> +#include <functional> +#include <iterator> +#include <map> +#include <tuple> +#include <utility> +#include <vector> + +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. +static cl::opt<bool> 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<bool> 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<int> 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<int> + 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<bool> + 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<bool> + SwpPruneLoopCarried("pipeliner-prune-loop-carried", + cl::desc("Prune loop carried order dependences."), + cl::Hidden, cl::init(true)); + +#ifndef NDEBUG +static cl::opt<int> SwpLoopLimit("pipeliner-max", cl::Hidden, cl::init(-1)); +#endif + +static cl::opt<bool> 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<MachineOperand, 4> BrCond; + MachineInstr *LoopInductionVar = nullptr; + MachineInstr *LoopCompare = nullptr; + }; + LoopInfo LI; + + static char ID; + MachinePipeliner() : MachineFunctionPass(ID) { + initializeMachinePipelinerPass(*PassRegistry::getPassRegistry()); + } + + bool runOnMachineFunction(MachineFunction &MF) override; + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired<AAResultsWrapperPass>(); + AU.addPreserved<AAResultsWrapperPass>(); + AU.addRequired<MachineLoopInfo>(); + AU.addRequired<MachineDominatorTree>(); + AU.addRequired<LiveIntervals>(); + 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<NodeInfo> ScheduleInfo; + + enum OrderKind { BottomUp = 0, TopDown = 1 }; + /// Computed node ordering for scheduling. + SetVector<SUnit *> NodeOrder; + + typedef SmallVector<NodeSet, 8> NodeSetType; + typedef DenseMap<unsigned, unsigned> ValueMapTy; + typedef SmallVectorImpl<MachineBasicBlock *> MBBVectorTy; + typedef DenseMap<MachineInstr *, MachineInstr *> InstrMapTy; + + /// Instructions to change when emitting the final schedule. + DenseMap<SUnit *, std::pair<unsigned, int64_t>> InstrChanges; + + /// We may create a new instruction, so remember it because it + /// must be deleted when the pass is finished. + SmallPtrSet<MachineInstr *, 4> NewMIs; + + /// Ordered list of DAG postprocessing steps. + std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations; + + /// Helper class to implement Johnson's circuit finding algorithm. + class Circuits { + std::vector<SUnit> &SUnits; + SetVector<SUnit *> Stack; + BitVector Blocked; + SmallVector<SmallPtrSet<SUnit *, 4>, 10> B; + SmallVector<SmallVector<int, 4>, 16> AdjK; + unsigned NumPaths; + static unsigned MaxPaths; + + public: + Circuits(std::vector<SUnit> &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<SUnit *, 4>()); + 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) { + P.MF->getSubtarget().getSMSMutations(Mutations); + } + + void schedule() override; + void finishBlock() override; + + /// 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<SUnit *, std::pair<unsigned, int64_t>>::iterator It = + InstrChanges.find(SU); + if (It != InstrChanges.end()) + return It->second.first; + return 0; + } + + void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) { + Mutations.push_back(std::move(Mutation)); + } + +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<SUnit *> &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, + unsigned LoopStage, ValueMapTy *VRMap, + MachineBasicBlock *BB); + void rewritePhiValues(MachineBasicBlock *NewBB, unsigned StageNum, + SMSchedule &Schedule, ValueMapTy *VRMap, + InstrMapTy &InstrMap); + void rewriteScheduledInstr(MachineBasicBlock *BB, SMSchedule &Schedule, + InstrMapTy &InstrMap, unsigned CurStageNum, + unsigned PhiNum, MachineInstr *Phi, + unsigned OldReg, unsigned NewReg, + unsigned PrevReg = 0); + bool canUseLastOffsetValue(MachineInstr *MI, unsigned &BasePos, + unsigned &OffsetPos, unsigned &NewBase, + int64_t &NewOffset); + void postprocessDAG(); +}; + +/// A NodeSet contains a set of SUnit DAG nodes with additional information +/// that assigns a priority to the set. +class NodeSet { + SetVector<SUnit *> Nodes; + bool HasRecurrence; + unsigned RecMII = 0; + int MaxMOV = 0; + int MaxDepth = 0; + unsigned Colocate = 0; + SUnit *ExceedPressure = nullptr; + +public: + typedef SetVector<SUnit *>::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) { Nodes.insert(S, E); } + + template <typename UnaryPredicate> 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<SUnit *> &() { 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<int, std::deque<SUnit *>> ScheduledInstrs; + + /// Map from instruction to execution cycle. + std::map<SUnit *, int> 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<unsigned, std::pair<unsigned, bool>> 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<int, std::deque<SUnit *>>::iterator sched_iterator; + typedef DenseMap<int, std::deque<SUnit *>>::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<SUnit *, int>::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<SUnit *, int>::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<unsigned, bool> 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<unsigned, bool> 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<SUnit *> &getInstructions(int cycle) { + return ScheduledInstrs[cycle]; + } + + bool isValidSchedule(SwingSchedulerDAG *SSD); + void finalizeSchedule(SwingSchedulerDAG *SSD); + bool orderDependence(SwingSchedulerDAG *SSD, SUnit *SU, + std::deque<SUnit *> &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<MachineLoopInfo>(); + MDT = &getAnalysis<MachineDominatorTree>(); + 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<LiveIntervals>(), 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<AAResultsWrapperPass>().getAAResults(); + buildSchedGraph(AA); + addLoopCarriedDependences(AA); + updatePhiDependences(); + Topo.InitDAGTopologicalSorting(); + postprocessDAG(); + 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<NodeSet>()); + + 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<SUnit *, 8> Visited; + SmallVector<SUnit *, 8> 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.isDereferenceableInvariantLoad(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<Value *> &Objs, + const DataLayout &DL) { + if (!MI->hasOneMemOperand()) + return; + MachineMemOperand *MM = *MI->memoperands_begin(); + if (!MM->getValue()) + return; + GetUnderlyingObjects(const_cast<Value *>(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<Value *, SmallVector<SUnit *, 4>> PendingLoads; + for (auto &SU : SUnits) { + MachineInstr &MI = *SU.getInstr(); + if (isDependenceBarrier(MI, AA)) + PendingLoads.clear(); + else if (MI.mayLoad()) { + SmallVector<Value *, 4> Objs; + getUnderlyingObjects(&MI, Objs, MF.getDataLayout()); + for (auto V : Objs) { + SmallVector<SUnit *, 4> &SUs = PendingLoads[V]; + SUs.push_back(&SU); + } + } else if (MI.mayStore()) { + SmallVector<Value *, 4> Objs; + getUnderlyingObjects(&MI, Objs, MF.getDataLayout()); + for (auto V : Objs) { + MapVector<Value *, SmallVector<SUnit *, 4>>::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)) { + SU.addPred(SDep(Load, SDep::Barrier)); + 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) { + SU.addPred(SDep(Load, SDep::Barrier)); + continue; + } + MachineMemOperand *MMO1 = *LdMI.memoperands_begin(); + MachineMemOperand *MMO2 = *MI.memoperands_begin(); + if (!MMO1->getValue() || !MMO2->getValue()) { + SU.addPred(SDep(Load, SDep::Barrier)); + 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<SDep, 4> RemoveDeps; + const TargetSubtargetInfo &ST = MF.getSubtarget<TargetSubtargetInfo>(); + + // 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 != nullptr && 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 == nullptr) + continue; + SUnit *SU = getSUnit(DefMI); + if (SU != nullptr && 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<SDep, 4> 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<unsigned, unsigned> 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(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; + } +}; + +} // end anonymous namespace + +/// 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<DFAPacketizer *, 8> 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<MachineInstr *, std::vector<MachineInstr *>, 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<DFAPacketizer *>::iterator RI = Resources.begin(); + SmallVectorImpl<DFAPacketizer *>::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<SUnit> &SUnits) { + SmallVector<std::pair<SUnit *, SDep>, 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<std::pair<SUnit *, SDep>, 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) { + // Do not process a boundary node and a back-edge is processed only + // if it goes to a Phi. + if (SI.getSUnit()->isBoundaryNode() || + (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<SUnit *, 4> &BU = B[U]; + while (!BU.empty()) { + SmallPtrSet<SUnit *, 4>::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<SUnit *> &NodeOrder, + SmallSetVector<SUnit *, 8> &Preds, + const NodeSet *S = nullptr) { + Preds.clear(); + for (SetVector<SUnit *>::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<SUnit *> &NodeOrder, + SmallSetVector<SUnit *, 8> &Succs, + const NodeSet *S = nullptr) { + Succs.clear(); + for (SetVector<SUnit *>::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<SUnit *> &Path, + SetVector<SUnit *> &DestNodes, + SetVector<SUnit *> &Exclude, + SmallPtrSet<SUnit *, 8> &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 <class S1Ty, class S2Ty> 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(MachineFunction &MF, RegPressureTracker &RPTracker, + NodeSet &NS) { + const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); + MachineRegisterInfo &MRI = MF.getRegInfo(); + SmallVector<RegisterMaskPair, 8> LiveOutRegs; + SmallSet<unsigned, 4> Uses; + for (SUnit *SU : NS) { + const MachineInstr *MI = SU->getInstr(); + if (MI->isPHI()) + continue; + for (const MachineOperand &MO : MI->operands()) + if (MO.isReg() && MO.isUse()) { + unsigned Reg = MO.getReg(); + if (TargetRegisterInfo::isVirtualRegister(Reg)) + Uses.insert(Reg); + else if (MRI.isAllocatable(Reg)) + for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) + Uses.insert(*Units); + } + } + for (SUnit *SU : NS) + for (const MachineOperand &MO : SU->getInstr()->operands()) + if (MO.isReg() && MO.isDef() && !MO.isDead()) { + unsigned Reg = MO.getReg(); + if (TargetRegisterInfo::isVirtualRegister(Reg)) { + if (!Uses.count(Reg)) + LiveOutRegs.push_back(RegisterMaskPair(Reg, + LaneBitmask::getNone())); + } else if (MRI.isAllocatable(Reg)) { + for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) + if (!Uses.count(*Units)) + LiveOutRegs.push_back(RegisterMaskPair(*Units, + LaneBitmask::getNone())); + } + } + 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(MF, RecRPTracker, NS); + RecRPTracker.closeBottom(); + + std::vector<SUnit *> 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<PressureChange> 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<SUnit *, 8> 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<SUnit *, 8> 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<SUnit *> NodesAdded; + SmallPtrSet<SUnit *, 8> Visited; + // Add the nodes that are on a path between the previous node sets and + // the current node set. + for (NodeSet &I : NodeSets) { + SmallSetVector<SUnit *, 8> N; + // Add the nodes from the current node set to the previous node set. + if (succ_L(I, N)) { + SetVector<SUnit *> 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<SUnit *> 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<SUnit *, 8> 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<SUnit *> &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<SUnit *, 8> &Set1, const NodeSet &Set2, + SmallSetVector<SUnit *, 8> &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<SUnit *, 8> R; + NodeOrder.clear(); + + for (auto &Nodes : NodeSets) { + DEBUG(dbgs() << "NodeSet size " << Nodes.size() << "\n"); + OrderKind Order; + SmallSetVector<SUnit *, 8> 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 == nullptr || 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<SUnit *, 8> 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 == nullptr || 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<SUnit *, 8> 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<SUnit *>::iterator NI = NodeOrder.begin(); + SetVector<SUnit *>::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); + } + // Even if we find a schedule, make sure the schedule doesn't exceed the + // allowable number of stages. We keep trying if this happens. + if (scheduleFound) + if (SwpMaxStages > -1 && + Schedule.getMaxStageCount() > (unsigned)SwpMaxStages) + scheduleFound = false; + + DEBUG({ + if (!scheduleFound) + dbgs() << "\tCan't schedule\n"; + }); + } while (++NI != NE && scheduleFound); + + // If a schedule is found, check if it is a valid schedule too. + if (scheduleFound) + scheduleFound = Schedule.isValidSchedule(this); + } + + 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<MachineBasicBlock *, 4> 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<SUnit *> &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<MachineBasicBlock *, 4> 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<MachineOperand, 0> Cond; + TII->insertBranch(*PreheaderBB, PrologBBs[0], nullptr, Cond, DebugLoc()); + } +} + +/// Generate the pipeline epilog code. The epilog code finishes the iterations +/// that were started in either the prolog or the kernel. We create a basic +/// block for each stage that needs to complete. +void SwingSchedulerDAG::generateEpilog(SMSchedule &Schedule, unsigned LastStage, + MachineBasicBlock *KernelBB, + ValueMapTy *VRMap, + MBBVectorTy &EpilogBBs, + MBBVectorTy &PrologBBs) { + // We need to change the branch from the kernel to the first epilog block, so + // this call to analyze branch uses the kernel rather than the original BB. + MachineBasicBlock *TBB = nullptr, *FBB = nullptr; + SmallVector<MachineOperand, 4> 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<MachineOperand, 4> Cond1; + TII->insertBranch(*LastEpilogBB, LoopExitBB, nullptr, Cond1, DebugLoc()); + } +} + +/// Replace all uses of FromReg that appear outside the specified +/// basic block with ToReg. +static void replaceRegUsesAfterLoop(unsigned FromReg, unsigned ToReg, + MachineBasicBlock *MBB, + MachineRegisterInfo &MRI, + LiveIntervals &LIS) { + for (MachineRegisterInfo::use_iterator I = MRI.use_begin(FromReg), + E = MRI.use_end(); + I != E;) { + MachineOperand &O = *I; + ++I; + if (O.getParent()->getParent() != MBB) + O.setReg(ToReg); + } + if (!LIS.hasInterval(ToReg)) + LIS.createEmptyInterval(ToReg); +} + +/// Return true if the register has a use that occurs outside the +/// specified loop. +static bool hasUseAfterLoop(unsigned Reg, MachineBasicBlock *BB, + MachineRegisterInfo &MRI) { + for (MachineRegisterInfo::use_iterator I = MRI.use_begin(Reg), + E = MRI.use_end(); + I != E; ++I) + if (I->getParent()->getParent() != BB) + return true; + return false; +} + +/// Generate Phis for the specific block in the generated pipelined code. +/// This function looks at the Phis from the original code to guide the +/// creation of new Phis. +void SwingSchedulerDAG::generateExistingPhis( + MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2, + MachineBasicBlock *KernelBB, SMSchedule &Schedule, ValueMapTy *VRMap, + InstrMapTy &InstrMap, unsigned LastStageNum, unsigned CurStageNum, + bool IsLast) { + // Compute the stage number for the 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]; + } + // Adjust the number of Phis needed depending on the number of prologs left, + // and the distance from where the Phi is first scheduled. + unsigned NumPhis = NumStages; + if (!InKernel && (int)PrologStage < LoopValStage) + // The NumPhis is the maximum number of new Phis needed during the steady + // state. If the Phi has not been scheduled in current prolog, then we + // need to generate less Phis. + NumPhis = std::max((int)NumPhis - (int)(LoopValStage - PrologStage), 1); + // The number of Phis cannot exceed the number of prolog stages. Each + // stage can potentially define two values. + NumPhis = std::min(NumPhis, PrologStage + 2); + + 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)); + int StageAdj = (PhiOpStage != -1 ? PhiStage - PhiOpStage : 0); + if (PhiOpStage != -1 && PrologStage - StageAdj >= Indirects + np && + VRMap[PrologStage - StageAdj - Indirects - np].count(PhiOp1)) { + PhiOp1 = VRMap[PrologStage - StageAdj - Indirects - np][PhiOp1]; + break; + } + ++Indirects; + } + } else + PhiOp1 = InitVal; + // If this references a generated Phi in the kernel, get the Phi operand + // from the incoming block. + if (MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1)) + if (InstOp1->isPHI() && InstOp1->getParent() == KernelBB) + PhiOp1 = getInitPhiReg(*InstOp1, KernelBB); + + MachineInstr *PhiInst = MRI.getVRegDef(LoopVal); + bool LoopDefIsPhi = PhiInst && PhiInst->isPHI(); + // In the epilog, a map lookup is needed to get the value from the kernel, + // or previous epilog block. How is does this depends on if the + // instruction is scheduled in the previous block. + if (!InKernel) { + int StageDiffAdj = 0; + if (LoopValStage != -1 && StageScheduled > LoopValStage) + StageDiffAdj = StageScheduled - LoopValStage; + // Use the loop value defined in the kernel, unless the kernel + // contains the last definition of the Phi. + if (np == 0 && PrevStage == LastStageNum && + (StageScheduled != 0 || LoopValStage != 0) && + VRMap[PrevStage - StageDiffAdj].count(LoopVal)) + PhiOp2 = VRMap[PrevStage - StageDiffAdj][LoopVal]; + // Use the value defined by the Phi. We add one because we switch + // from looking at the loop value to the Phi definition. + else if (np > 0 && PrevStage == LastStageNum && + VRMap[PrevStage - np + 1].count(Def)) + PhiOp2 = VRMap[PrevStage - np + 1][Def]; + // Use the loop value defined in the kernel. + else if ((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 && (int)PrologStage >= StageScheduled) { + 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 (InKernel && StageDiff > 0 && + VRMap[CurStageNum - StageDiff - np].count(LoopVal)) + PhiOp2 = VRMap[CurStageNum - StageDiff - np][LoopVal]; + } + + const TargetRegisterClass *RC = MRI.getRegClass(Def); + NewReg = MRI.createVirtualRegister(RC); + + MachineInstrBuilder NewPhi = + BuildMI(*NewBB, NewBB->getFirstNonPHI(), DebugLoc(), + TII->get(TargetOpcode::PHI), NewReg); + NewPhi.addReg(PhiOp1).addMBB(BB1); + NewPhi.addReg(PhiOp2).addMBB(BB2); + if (np == 0) + InstrMap[NewPhi] = &*BBI; + + // We define the Phis after creating the new pipelined code, so + // we need to rename the Phi values in scheduled instructions. + + unsigned PrevReg = 0; + if (InKernel && VRMap[PrevStage - np].count(LoopVal)) + PrevReg = VRMap[PrevStage - np][LoopVal]; + rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, np, &*BBI, + Def, NewReg, PrevReg); + // If the Phi has been scheduled, use the new name for rewriting. + if (VRMap[CurStageNum - np].count(Def)) { + unsigned R = VRMap[CurStageNum - np][Def]; + rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, np, &*BBI, + R, NewReg); + } + + // Check if we need to rename any uses that occurs after the loop. The + // register to replace depends on whether the Phi is scheduled in the + // epilog. + if (IsLast && np == NumPhis - 1) + replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS); + + // In the kernel, a dependent Phi uses the value from this Phi. + if (InKernel) + PhiOp2 = NewReg; + + // Update the map with the new Phi name. + VRMap[CurStageNum - np][Def] = NewReg; + } + + while (NumPhis++ < NumStages) { + rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, NumPhis, + &*BBI, Def, NewReg, 0); + } + + // Check if we need to rename a Phi that has been eliminated due to + // scheduling. + if (NumStages == 0 && IsLast && VRMap[CurStageNum].count(LoopVal)) + replaceRegUsesAfterLoop(Def, VRMap[CurStageNum][LoopVal], BB, MRI, LIS); + } +} + +/// Generate Phis for the specified block in the generated pipelined code. +/// These are new Phis needed because the definition is scheduled after the +/// use in the 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(); + 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<MachineInstr *, 4> 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<MachineOperand, 4> 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, nullptr, Cond, DebugLoc()); + removePhis(Epilog, LastEpi); + // Remove the blocks that are no longer referenced. + if (LastPro != LastEpi) { + LastEpi->clear(); + LastEpi->eraseFromParent(); + } + LastPro->clear(); + LastPro->eraseFromParent(); + } else { + numAdded = TII->insertBranch(*Prolog, LastPro, nullptr, Cond, DebugLoc()); + removePhis(Epilog, Prolog); + } + LastPro = Prolog; + LastEpi = Epilog; + for (MachineBasicBlock::reverse_instr_iterator I = Prolog->instr_rbegin(), + E = Prolog->instr_rend(); + I != E && numAdded > 0; ++I, --numAdded) + updateInstruction(&*I, false, j, 0, Schedule, VRMap); + } +} + +/// Return true if we can compute the amount the instruction changes +/// during each iteration. Set Delta to the amount of the change. +bool SwingSchedulerDAG::computeDelta(MachineInstr &MI, unsigned &Delta) { + 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 = 0; + if (!TII->getIncrementValue(*BaseDef, D) && D >= 0) + return false; + + Delta = D; + return true; +} + +/// Update the memory operand with a new offset when the pipeliner +/// generates a new copy of the instruction that refers to a +/// different memory location. +void 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 (MachineMemOperand *MMO : NewMI.memoperands()) { + if (MMO->isVolatile() || (MMO->isInvariant() && MMO->isDereferenceable()) || + (!MMO->getValue())) { + NewMemRefs[Refs++] = MMO; + continue; + } + unsigned Delta; + if (computeDelta(OldMI, Delta)) { + int64_t AdjOffset = Delta * Num; + NewMemRefs[Refs++] = + MF.getMachineMemOperand(MMO, AdjOffset, MMO->getSize()); + } else + NewMemRefs[Refs++] = MF.getMachineMemOperand(MMO, 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); + // Check for tied operands in inline asm instructions. This should be handled + // elsewhere, but I'm not sure of the best solution. + if (OldMI->isInlineAsm()) + for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) { + const auto &MO = OldMI->getOperand(i); + if (MO.isReg() && MO.isUse()) + break; + unsigned UseIdx; + if (OldMI->isRegTiedToUseOperand(i, &UseIdx)) + NewMI->tieOperands(i, UseIdx); + } + updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum); + return NewMI; +} + +/// Clone the instruction for the new pipelined loop. If needed, this +/// function updates the instruction using the values saved in the +/// InstrChanges structure. +MachineInstr *SwingSchedulerDAG::cloneAndChangeInstr(MachineInstr *OldMI, + unsigned CurStageNum, + unsigned InstStageNum, + SMSchedule &Schedule) { + MachineInstr *NewMI = MF.CloneMachineInstr(OldMI); + DenseMap<SUnit *, std::pair<unsigned, int64_t>>::iterator It = + InstrChanges.find(getSUnit(OldMI)); + if (It != InstrChanges.end()) { + std::pair<unsigned, int64_t> RegAndOffset = It->second; + unsigned BasePos, OffsetPos; + if (!TII->getBaseAndOffsetPosition(*OldMI, BasePos, OffsetPos)) + return nullptr; + int64_t NewOffset = OldMI->getOperand(OffsetPos).getImm(); + MachineInstr *LoopDef = findDefInLoop(RegAndOffset.first); + if (Schedule.stageScheduled(getSUnit(LoopDef)) > (signed)InstStageNum) + NewOffset += RegAndOffset.second * (CurStageNum - InstStageNum); + NewMI->getOperand(OffsetPos).setImm(NewOffset); + } + updateMemOperands(*NewMI, *OldMI, CurStageNum - InstStageNum); + return NewMI; +} + +/// Update the machine instruction with new virtual registers. This +/// function may change the defintions and/or uses. +void SwingSchedulerDAG::updateInstruction(MachineInstr *NewMI, bool LastDef, + unsigned CurStageNum, + unsigned InstrStageNum, + SMSchedule &Schedule, + ValueMapTy *VRMap) { + for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = NewMI->getOperand(i); + if (!MO.isReg() || !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<MachineInstr *, 8> Visited; + MachineInstr *Def = MRI.getVRegDef(Reg); + while (Def->isPHI()) { + if (!Visited.insert(Def).second) + break; + for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2) + if (Def->getOperand(i + 1).getMBB() == BB) { + Def = MRI.getVRegDef(Def->getOperand(i).getReg()); + break; + } + } + return Def; +} + +/// Return the new name for the value from the previous stage. +unsigned SwingSchedulerDAG::getPrevMapVal(unsigned StageNum, unsigned PhiStage, + unsigned LoopVal, unsigned LoopStage, + ValueMapTy *VRMap, + MachineBasicBlock *BB) { + unsigned PrevVal = 0; + if (StageNum > PhiStage) { + MachineInstr *LoopInst = MRI.getVRegDef(LoopVal); + if (PhiStage == LoopStage && VRMap[StageNum - 1].count(LoopVal)) + // The name is defined in the previous stage. + PrevVal = VRMap[StageNum - 1][LoopVal]; + else if (VRMap[StageNum].count(LoopVal)) + // The previous name is defined in the current stage when the instruction + // order is swapped. + PrevVal = VRMap[StageNum][LoopVal]; + else if (!LoopInst->isPHI() || LoopInst->getParent() != BB) + // The loop value hasn't yet been scheduled. + PrevVal = LoopVal; + else if (StageNum == PhiStage + 1) + // The loop value is another phi, which has not been scheduled. + PrevVal = getInitPhiReg(*LoopInst, BB); + else if (StageNum > PhiStage + 1 && LoopInst->getParent() == BB) + // The loop value is another phi, which has been scheduled. + PrevVal = + getPrevMapVal(StageNum - 1, PhiStage, getLoopPhiReg(*LoopInst, BB), + LoopStage, VRMap, BB); + } + return PrevVal; +} + +/// Rewrite the Phi values in the specified block to use the mappings +/// from the initial operand. Once the Phi is scheduled, we switch +/// to using the loop value instead of the Phi value, so those names +/// do not need to be rewritten. +void SwingSchedulerDAG::rewritePhiValues(MachineBasicBlock *NewBB, + unsigned StageNum, + SMSchedule &Schedule, + ValueMapTy *VRMap, + InstrMapTy &InstrMap) { + for (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 LoopStage = + (unsigned)Schedule.stageScheduled(getSUnit(MRI.getVRegDef(LoopVal))); + unsigned NumPhis = Schedule.getStagesForPhi(PhiDef); + if (NumPhis > StageNum) + NumPhis = StageNum; + for (unsigned np = 0; np <= NumPhis; ++np) { + unsigned NewVal = + getPrevMapVal(StageNum - np, PhiStage, LoopVal, LoopStage, VRMap, BB); + if (!NewVal) + NewVal = InitVal; + rewriteScheduledInstr(NewBB, Schedule, InstrMap, StageNum - np, np, &*BBI, + PhiDef, NewVal); + } + } +} + +/// Rewrite a previously scheduled instruction to use the register value +/// from the new instruction. Make sure the instruction occurs in the +/// basic block, and we don't change the uses in the new instruction. +void SwingSchedulerDAG::rewriteScheduledInstr( + MachineBasicBlock *BB, SMSchedule &Schedule, InstrMapTy &InstrMap, + unsigned CurStageNum, unsigned PhiNum, MachineInstr *Phi, unsigned OldReg, + unsigned NewReg, unsigned PrevReg) { + bool InProlog = (CurStageNum < Schedule.getMaxStageCount()); + int StagePhi = Schedule.stageScheduled(getSUnit(Phi)) + PhiNum; + // Rewrite uses that have been scheduled already to use the new + // Phi register. + for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(OldReg), + EI = MRI.use_end(); + UI != EI;) { + MachineOperand &UseOp = *UI; + MachineInstr *UseMI = UseOp.getParent(); + ++UI; + if (UseMI->getParent() != BB) + continue; + if (UseMI->isPHI()) { + if (!Phi->isPHI() && UseMI->getOperand(0).getReg() == NewReg) + continue; + if (getLoopPhiReg(*UseMI, BB) != OldReg) + continue; + } + InstrMapTy::iterator OrigInstr = InstrMap.find(UseMI); + assert(OrigInstr != InstrMap.end() && "Instruction not scheduled."); + SUnit *OrigMISU = getSUnit(OrigInstr->second); + int StageSched = Schedule.stageScheduled(OrigMISU); + int CycleSched = Schedule.cycleScheduled(OrigMISU); + unsigned ReplaceReg = 0; + // This is the stage for the scheduled instruction. + if (StagePhi == StageSched && Phi->isPHI()) { + int CyclePhi = Schedule.cycleScheduled(getSUnit(Phi)); + if (PrevReg && InProlog) + ReplaceReg = PrevReg; + else if (PrevReg && !Schedule.isLoopCarried(this, *Phi) && + (CyclePhi <= CycleSched || OrigMISU->getInstr()->isPHI())) + ReplaceReg = PrevReg; + else + ReplaceReg = NewReg; + } + // The scheduled instruction occurs before the scheduled Phi, and the + // Phi is not loop carried. + if (!InProlog && StagePhi + 1 == StageSched && + !Schedule.isLoopCarried(this, *Phi)) + ReplaceReg = NewReg; + if (StagePhi > StageSched && Phi->isPHI()) + ReplaceReg = NewReg; + if (!InProlog && !Phi->isPHI() && StagePhi < StageSched) + ReplaceReg = NewReg; + if (ReplaceReg) { + MRI.constrainRegClass(ReplaceReg, MRI.getRegClass(OldReg)); + UseOp.setReg(ReplaceReg); + } + } +} + +/// Check if we can change the instruction to use an offset value from the +/// previous iteration. If so, return true and set the base and offset values +/// so that we can rewrite the load, if necessary. +/// 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<SUnit *, std::pair<unsigned, int64_t>>::iterator It = + InstrChanges.find(SU); + if (It != InstrChanges.end()) { + std::pair<unsigned, int64_t> 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; +} + +void SwingSchedulerDAG::postprocessDAG() { + for (auto &M : Mutations) + M->apply(this); +} + +/// 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<SUnit *> &cycleInstrs = ScheduledInstrs[checkCycle]; + + for (std::deque<SUnit *>::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<SUnit *, 8> Visited; + SmallVector<SDep, 8> 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<SUnit *, int>::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<SUnit *, 8> Visited; + SmallVector<SDep, 8> 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<SUnit *, int>::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<SUnit *> &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<SUnit *>::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.isDef() && Reads && stageScheduled(*I) > StageInst1) { + // Add the instruction after the scheduled instruction. + OrderAfterDef = true; + MoveDef = 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() && Writes && stageScheduled(*I) < StageInst1) { + // Add the instruction before the scheduled instruction. + OrderBeforeUse = true; + MoveUse = Pos; + } 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) { + if (S.getSUnit() == *I && stageScheduled(*I) == StageInst1) { + OrderBeforeUse = true; + MoveUse = Pos; + } + } else if (TargetRegisterInfo::isPhysicalRegister(S.getReg())) { + if (cycleScheduled(SU) != cycleScheduled(S.getSUnit())) { + if (S.isAssignedRegDep()) { + OrderAfterDef = true; + MoveDef = Pos; + } + } else { + OrderBeforeUse = true; + MoveUse = Pos; + } + } + for (auto &P : SU->Preds) + if (P.getKind() == SDep::Order) { + if (P.getSUnit() == *I && stageScheduled(*I) == StageInst1) { + OrderAfterDef = true; + MoveDef = Pos; + } + } else if (TargetRegisterInfo::isPhysicalRegister(P.getReg())) { + if (cycleScheduled(SU) != cycleScheduled(P.getSUnit())) { + if (P.isAssignedRegDep()) { + OrderBeforeUse = true; + MoveUse = Pos; + } + } else { + OrderAfterDef = true; + MoveDef = Pos; + } + } + } + + // A circular dependence. + if (OrderAfterDef && OrderBeforeUse && MoveUse == MoveDef) + OrderBeforeUse = false; + + // OrderAfterDef takes precedences over OrderBeforeDef. The latter is due + // to a loop-carried dependence. + if (OrderBeforeDef) + OrderBeforeUse = !OrderAfterDef || (MoveUse > MoveDef); + + // The uncommon case when the instruction order needs to be updated because + // there is both a use and def. + if (OrderBeforeUse && OrderAfterDef) { + 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) || (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; +} + +// Check if the generated schedule is valid. This function checks if +// an instruction that uses a physical register is scheduled in a +// different stage than the definition. The pipeliner does not handle +// physical register values that may cross a basic block boundary. +bool SMSchedule::isValidSchedule(SwingSchedulerDAG *SSD) { + for (int i = 0, e = SSD->SUnits.size(); i < e; ++i) { + SUnit &SU = SSD->SUnits[i]; + if (!SU.hasPhysRegDefs) + continue; + int StageDef = stageScheduled(&SU); + assert(StageDef != -1 && "Instruction should have been scheduled."); + for (auto &SI : SU.Succs) + if (SI.isAssignedRegDep()) + if (ST.getRegisterInfo()->isPhysicalRegister(SI.getReg())) + if (stageScheduled(SI.getSUnit()) != StageDef) + return false; + } + return true; +} + +/// 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<SUnit *> &cycleInstrs = + ScheduledInstrs[cycle + (stage * InitiationInterval)]; + for (std::deque<SUnit *>::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<SUnit *> &cycleInstrs = ScheduledInstrs[Cycle]; + std::deque<SUnit *> 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<SUnit *> 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()); } |
