Index: include/llvm/CodeGen/MachineLoopInfo.h =================================================================== --- include/llvm/CodeGen/MachineLoopInfo.h +++ include/llvm/CodeGen/MachineLoopInfo.h @@ -56,6 +56,14 @@ void dump() const; + // + DebugLoc getDebugLoc(); + MachineFunction* getFunction(); + void emitOptimizationRemark(const char* PassName, const char* Msg); + void emitOptimizationRemarkMissed(const char* PassName, const char* Msg); + void emitOptimizationRemarkAnalysis(const char* PassName, const char* Msg); + // + private: friend class LoopInfoBase; explicit MachineLoop(MachineBasicBlock *MBB) @@ -151,6 +159,7 @@ void removeBlock(MachineBasicBlock *BB) { LI.removeBlock(BB); } + }; Index: lib/CodeGen/CGLoopInfo.cpp =================================================================== --- lib/CodeGen/CGLoopInfo.cpp +++ lib/CodeGen/CGLoopInfo.cpp @@ -24,6 +24,7 @@ if (!Attrs.IsParallel && Attrs.VectorizeWidth == 0 && Attrs.InterleaveCount == 0 && Attrs.UnrollCount == 0 && Attrs.VectorizeEnable == LoopAttributes::Unspecified && + Attrs.PipelineEnable == LoopAttributes::Unspecified && //SYNOPSYS Attrs.UnrollEnable == LoopAttributes::Unspecified) return nullptr; @@ -65,6 +66,17 @@ Args.push_back(MDNode::get(Ctx, Vals)); } + // + // Setting pipelineenable + if (Attrs.PipelineEnable != LoopAttributes::Unspecified) { + Metadata *Vals[] = {MDString::get(Ctx, "llvm.loop.pipeline"), + ConstantAsMetadata::get(ConstantInt::get( + Type::getInt1Ty(Ctx), (Attrs.PipelineEnable == + LoopAttributes::Enable)))}; + Args.push_back(MDNode::get(Ctx, Vals)); + } + // + // Setting unroll.full or unroll.disable if (Attrs.UnrollEnable != LoopAttributes::Unspecified) { std::string Name; @@ -143,6 +155,11 @@ case LoopHintAttr::Unroll: setUnrollState(LoopAttributes::Disable); break; + // + case LoopHintAttr::Pipeline://SYNOPSYS + setPipelineEnable(false); + break; + // case LoopHintAttr::UnrollCount: case LoopHintAttr::VectorizeWidth: case LoopHintAttr::InterleaveCount: @@ -159,6 +176,11 @@ case LoopHintAttr::Unroll: setUnrollState(LoopAttributes::Enable); break; + // + case LoopHintAttr::Pipeline://SYNOPSYS + setPipelineEnable(true); + break; + // case LoopHintAttr::UnrollCount: case LoopHintAttr::VectorizeWidth: case LoopHintAttr::InterleaveCount: @@ -178,6 +200,7 @@ case LoopHintAttr::UnrollCount: case LoopHintAttr::VectorizeWidth: case LoopHintAttr::InterleaveCount: + case LoopHintAttr::Pipeline://SYNOPSYS llvm_unreachable("Options cannot be used to assume mem safety."); break; } @@ -187,6 +210,7 @@ case LoopHintAttr::Unroll: setUnrollState(LoopAttributes::Full); break; + case LoopHintAttr::Pipeline://SYNOPSYS case LoopHintAttr::Vectorize: case LoopHintAttr::Interleave: case LoopHintAttr::UnrollCount: @@ -208,6 +232,7 @@ setUnrollCount(ValueInt); break; case LoopHintAttr::Unroll: + case LoopHintAttr::Pipeline://SYNOPSYS case LoopHintAttr::Vectorize: case LoopHintAttr::Interleave: llvm_unreachable("Options cannot be assigned a value."); Index: lib/CodeGen/MachineLoopInfo.cpp =================================================================== --- lib/CodeGen/MachineLoopInfo.cpp +++ lib/CodeGen/MachineLoopInfo.cpp @@ -18,6 +18,7 @@ #include "llvm/Analysis/LoopInfoImpl.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/Passes.h" +#include "llvm/IR/DiagnosticInfo.h" //SYNOPSYS #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; @@ -81,3 +82,36 @@ print(dbgs()); } #endif + +// +DebugLoc MachineLoop::getDebugLoc() { + if (MachineBasicBlock* MBB = getTopBlock()) + for (auto& MI : *MBB) + if (!MI.isDebugValue() && MI.getDebugLoc()) + return MI.getDebugLoc(); + return DebugLoc(); +} +MachineFunction* MachineLoop::getFunction() { + if (MachineBasicBlock* MBB = getTopBlock()) + return MBB->getParent(); + return nullptr; +} +void MachineLoop::emitOptimizationRemark(const char* PassName, const char* Msg) { + if (MachineFunction* MF = getFunction()) + if (const Function* F = MF->getFunction()) + if (const DebugLoc& DL = getDebugLoc()) + llvm::emitOptimizationRemark(F->getContext(), PassName, *F, DL, Msg); +} +void MachineLoop::emitOptimizationRemarkMissed(const char* PassName, const char* Msg) { + if (MachineFunction* MF = getFunction()) + if (const Function* F = MF->getFunction()) + if (const DebugLoc& DL = getDebugLoc()) + llvm::emitOptimizationRemarkMissed(F->getContext(), PassName, *F, DL, Msg); +} +void MachineLoop::emitOptimizationRemarkAnalysis(const char* PassName, const char* Msg) { + if (MachineFunction* MF = getFunction()) + if (const Function* F = MF->getFunction()) + if (const DebugLoc& DL = getDebugLoc()) + llvm::emitOptimizationRemarkAnalysis(F->getContext(), PassName, *F, DL, Msg); +} +// Index: lib/CodeGen/MachinePipeliner.cpp =================================================================== --- lib/CodeGen/MachinePipeliner.cpp +++ lib/CodeGen/MachinePipeliner.cpp @@ -0,0 +1,4248 @@ +//===-- 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 is an instruction scheduling technique for loops that +// overlap loop iterations and explioits ILP via a compiler transformation. +// +// Swing Modulo Scheduling (SMS) is an implementation of software pipelining +// that generates schedules that are near optimal in terms of initiation +// interval, register requirements, and stage count. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/MapVector.h" +#include "llvm/ADT/PriorityQueue.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/CodeGen/DFAPacketizer.h" +#include "llvm/CodeGen/LiveIntervalAnalysis.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/CodeGen/MachineLoopInfo.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/Passes.h" +#include "llvm/CodeGen/RegisterClassInfo.h" +#include "llvm/CodeGen/RegisterPressure.h" +#include "llvm/CodeGen/ScheduleDAGInstrs.h" +#include "llvm/IR/Metadata.h" //SYNOPSYS +#include "llvm/MC/MCInstrItineraries.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" +#include "ArcReservationTable.h" //SYNOPSYS +#include +#include +#include + +using namespace llvm; + +#define DEBUG_TYPE "modulo-sched" + +STATISTIC(NumTrytoPipeline, "Number of loops that we attempt to pipeline"); +STATISTIC(NumPipelined, "Number of loops software pipelined"); + +// A command line option to enable SWP at -Os. +static cl::opt EnableSWPOptSize("enable-swp-opt-size", + cl::desc("Enable SWP at Os."), cl::Hidden, + cl::init(false)); + +// A command line argument to limit minimum initial interval for pipelining. +static cl::opt SwpMaxMii("swp-max-mii", + cl::desc("Size limit for the the MII."), + cl::Hidden, cl::init(64)); //SYNOPSYS was 27 + +static cl::opt + SwpMaxStages("swp-max-stages", + cl::desc("Maximum stages allowed in the generated scheduled."), + cl::Hidden, cl::init(3)); + +// A command line option to disable the pruning of chain dependences due to +// an unrelated Phi. +static cl::opt + SwpPruneDeps("swp-prune-deps", + cl::desc("Prune dependences between unrelated Phi nodes."), + cl::Hidden, cl::init(true)); + +// A command line option to disable the pruning of loop carried order +// dependences. +static cl::opt + SwpPruneLoopCarried("swp-prune-loop-carried", + cl::desc("Prune loop carried order dependences."), + cl::Hidden, cl::init(true)); + +#ifndef NDEBUG +static cl::opt SwpLoopLimit("swp-max", cl::Hidden, cl::init(-1)); +#endif + +static cl::opt SwpIgnoreRecMII("swp-ignore-recmii", cl::ReallyHidden, + cl::init(false), cl::ZeroOrMore, + cl::desc("Ignore RecMII")); + +static cl::opt ArcSwpMaxIter("arc-swp-max-iter", cl::Hidden, cl::init(20)); + +static cl::opt ArcKillSMS("arc-kill-sms", cl::Hidden, cl::init(0)); +#define DUMP_BEFORE() ((ArcKillSMS & 0x00000001) != 0) +#define DUMP_AFTER() ((ArcKillSMS & 0x00000002) != 0) +#define VIEW_BEFORE() ((ArcKillSMS & 0x00000004) != 0) +#define VIEW_AFTER() ((ArcKillSMS & 0x00000008) != 0) +#define DUMP_LOOP_ATTEMPT() ((ArcKillSMS & 0x00000010) != 0) + +namespace { + +class SMSchedule; +class SwingSchedulerDAG; + +// The main class in the implementation of the target independent +// software pipeliner pass. +class MachineSMS : public MachineFunctionPass { +public: + MachineFunction *MF; + const MachineLoopInfo *MLI; + const MachineDominatorTree *MDT; + const InstrItineraryData *InstrItins; + const TargetInstrInfo *TII; + RegisterClassInfo RegClassInfo; + +#ifndef NDEBUG + static int NumTries; +#endif + // Cache the target analysis information about the loop. + struct LoopInfo { + MachineBasicBlock *TBB; + MachineBasicBlock *FBB; + SmallVector BrCond; + MachineInstr *LoopInductionVar; + MachineInstr *LoopCompare; + LoopInfo() + : TBB(nullptr), FBB(nullptr), LoopInductionVar(nullptr), + LoopCompare(nullptr) {} + }; + LoopInfo LI; + + static char ID; + MachineSMS() + : MachineFunctionPass(ID), MF(nullptr), MLI(nullptr), MDT(nullptr), + TII(nullptr) { + initializeMachineSMSPass(*PassRegistry::getPassRegistry()); + } + + virtual bool runOnMachineFunction(MachineFunction &MF); + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequiredTransitive(); + AU.addPreserved(); + AU.addRequiredTransitive(); + AU.addRequiredTransitive(); + AU.addRequired(); + MachineFunctionPass::getAnalysisUsage(AU); + } + +private: + // Return true if the loop can be software pipelined. The algorithm is + // restricted to loops with a single basic block that the target is + // able to analyze. + bool canPipelineLoop(MachineLoop *L); + + // 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 scheduleLoop(MachineLoop *L); + + // The SMS algorithm consists of the following main steps: + // 1. Computation and analysis of the dependence graph. + // 2. Ordering of the nodes (instruction). + // 3. Attempt to Schedule the loop. + 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 { + MachineSMS *Pass; + unsigned MII; + bool Scheduled; + MachineLoop *Loop; + LiveIntervals *LIS; + + /// A toplogical ordering of the SUnits, which is needed for changing + /// dependences and iterating over the SUnits. + ScheduleDAGTopologicalSort Topo; + + struct NodeInfo { + int ASAP; + int ALAP; + NodeInfo() : ASAP(0), ALAP(0) {} + }; + /// Computed properties for each node in the graph. + std::vector ScheduleInfo; + + enum OrderKind { BottomUp = 0, TopDown = 1, AnyOrder = 2 }; //SYNOPSYS added AnyOrder + +#if 0 //SYNOPSYS don't define NodeOrder + + /// Computed node ordering for scheduling. + SetVector NodeOrder; + +#endif //SYNOPSYS + + // A NodeSet contains a set of SUnit DAG nodes with additional information + // that assigns a priority to the set. +public: + class NodeSet { + SetVector Nodes; + bool HasRecurrence; + unsigned RecMII; + int MaxMOV; + int MaxDepth; + unsigned Colocate; + SUnit *ExceedPressure; + + public: + typedef SetVector::iterator iterator; + typedef SetVector::const_iterator const_iterator; + + NodeSet() + : Nodes(), HasRecurrence(false), RecMII(0), MaxMOV(0), MaxDepth(0), + Colocate(0), ExceedPressure(nullptr) {} + + template + NodeSet(It S, It E) + : Nodes(S, E), HasRecurrence(true), RecMII(0), MaxMOV(0), MaxDepth(0), + Colocate(0), ExceedPressure(nullptr) {} + + bool insert(SUnit *SU) { return Nodes.insert(SU); } + + template void insert(It B, It E) { Nodes.insert(B, E); } + + template bool remove_if(UnaryPredicate P) { + return Nodes.remove_if(P); + } + + unsigned count(SUnit *SU) const { return Nodes.count(SU); } + + bool hasRecurrence() { return HasRecurrence; }; + + unsigned size() const { return Nodes.size(); } + + bool empty() const { return Nodes.empty(); } + + SUnit *getNode(unsigned i) const { return Nodes[i]; }; + + void setRecMII(unsigned mii) { RecMII = mii; }; + + void setColocate(unsigned c) { Colocate = c; }; + + void setExceedPressure(SUnit *SU) { ExceedPressure = SU; } + + bool isExceedSU(SUnit *SU) { return ExceedPressure == SU; } + + int compareRecMII(NodeSet &RHS) { return RecMII - RHS.RecMII; } + + int getRecMII() { return RecMII; } + + /// Summarize node functions for the entire node set. + void computeNodeSetInfo(SwingSchedulerDAG *SSD) { + for (NodeSet::iterator I = begin(), E = end(); I != E; ++I) { + MaxMOV = std::max(MaxMOV, SSD->getMOV(*I)); + MaxDepth = std::max(MaxDepth, SSD->getDepth(*I)); + } + } + + void clear() { + Nodes.clear(); + RecMII = 0; + HasRecurrence = false; + MaxMOV = 0; + MaxDepth = 0; + Colocate = 0; + ExceedPressure = nullptr; + } + + operator SetVector &() { return Nodes; } + + /// Sort the node sets by importance. First, rank them by recurrence MII, + /// then by mobility (least mobile done first), and finally by depth. + /// Each node set may contain a colocate value which is used as the first + /// tie breaker, if it's set. + bool operator>(const NodeSet &RHS) const { + if (RecMII == RHS.RecMII) { + if (Colocate != 0 && RHS.Colocate != 0 && Colocate != RHS.Colocate) + return Colocate < RHS.Colocate; + if (MaxMOV == RHS.MaxMOV) + return MaxDepth > RHS.MaxDepth; + return MaxMOV < RHS.MaxMOV; + } + return RecMII > RHS.RecMII; + } + bool operator==(const NodeSet &RHS) const { + return RecMII == RHS.RecMII && MaxMOV == RHS.MaxMOV && + MaxDepth == RHS.MaxDepth; + } + bool operator!=(const NodeSet &RHS) const { return !operator==(RHS); } + + iterator begin() { return Nodes.begin(); } + const_iterator begin() const { return Nodes.begin(); } + iterator end() { return Nodes.end(); } + const_iterator end() const { return Nodes.end(); } + + void print(raw_ostream &os) const { + os << "Num nodes " << size() << " rec " << RecMII << " mov " << MaxMOV + << " depth " << MaxDepth << " col " << Colocate << "\n"; + for (iterator I = begin(), E = end(); I != E; ++I) + os << " SU(" << (*I)->NodeNum << ")=" << (*I)->Latency << " " << *((*I)->getInstr()); //SYNOPSYS added Latency + os << "\n"; + } + + void dump() const { print(dbgs()); } + }; + +private: + typedef SmallVector NodeSetType; + typedef DenseMap ValueMapTy; + typedef SmallVectorImpl MBBVectorTy; + typedef DenseMap InstrMapTy; + + /// Instructions to change when emitting the final schedule. + DenseMap> InstrChanges; + + /// We may create a new instruction, so remember it because it + /// must be deleted when the pass is finished. + SmallPtrSet NewMIs; + + const RegisterClassInfo &RegClassInfo; + + /// Helper class to implement Johnson's circuit finding algorithm. + class Circuits { + std::vector &SUnits; + SmallVector Stack; + BitVector Blocked; + SmallVector, 10> B; + SmallVector, 16> AdjK; + unsigned NumPaths; + static unsigned MaxPaths; + + public: + Circuits(std::vector &SUs) + : SUnits(SUs), Stack(), Blocked(SUs.size()), B(SUs.size()), + AdjK(SUs.size()) {} + /// Reset the data structures used in the circuit algorithm. + void reset() { + Stack.clear(); + Blocked.reset(); + B.assign(SUnits.size(), SmallPtrSet()); + NumPaths = 0; + } + /// Create the Adjacency structure of the nodes in the graph. + void createAdjacencyStructure(SwingSchedulerDAG *DAG); + + /// The circuit function from Johnson's algorithm finds a circuit starting + /// at the specified node. + bool circuit(int V, int S, NodeSetType &NodeSets, bool HasBackedge = false); + + /// Unblock a node in the circuit finding algorithm. + void unblock(int U); + }; + +public: + SwingSchedulerDAG(MachineSMS *P, MachineLoop *L, LiveIntervals *lis, + const RegisterClassInfo &rci) + : ScheduleDAGInstrs(*P->MF, P->MLI, true), Pass(P), MII(0), + Scheduled(false), Loop(L), LIS(lis), Topo(SUnits, &ExitSU), + RegClassInfo(rci) {} + + // We need to implement this pure virtual function to do the scheduling. + void schedule(); + + /// Clean up after the software pipeliner runs. + void finishBlock(); + + // Return true if the loop kernel has been scheduled. + bool hasNewSchedule() { return Scheduled; } + + // Return the earliest time an instruction may be scheduled. + int getASAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ASAP; } + + // Return the latest time an instruction my be scheduled. + int getALAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ALAP; } + + // The mobility function, which the the number of slots in which + // an instruction may be scheduled. + int getMOV(SUnit *Node) { return getALAP(Node) - getASAP(Node); } + + // The depth, in the dependence graph, for a node. + int getDepth(SUnit *Node) { return Node->getDepth(); } + + // The height, in the dependence graph, for a node. + int getHeight(SUnit *Node) { return Node->getHeight(); } + + /// Return true if the dependence is a back-edge in the data dependence graph. + /// Since the DAG doesn't contain cycles, we represent a cycle in the graph + /// using an anti dependence from a Phi to an instruction. + bool isBackedge(SUnit *Source, const SDep &Dep) { + if (Dep.getKind() != SDep::Anti) + return false; + return Source->getInstr()->isPHI() || Dep.getSUnit()->getInstr()->isPHI(); + } + + /// Return true if the dependence is an order dependence between non-Phis. + static bool isOrder(SUnit *Source, const SDep &Dep) { + if (Dep.getKind() != SDep::Order) + return false; + return (!Source->getInstr()->isPHI() && + !Dep.getSUnit()->getInstr()->isPHI()); + } + + /// 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 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; } + + /// Apply changes to the instruction, which are needed to improve the + /// final schedule. + MachineInstr *applyInstrChange(MachineInstr *MI, SMSchedule &Schedule, + bool UpdateDAG = false); + + /// Return the new base register that was stored away for the changed + /// instruction. + unsigned getInstrBaseReg(SUnit *SU) { + DenseMap>::iterator It = + InstrChanges.find(SU); + if (It != InstrChanges.end()) + return It->second.first; + return 0; + } + +private: + /// Add a chain edge between a load and store if the store can be an + /// alias of the load on a subsequent iteration. + void addLoopCarriedDependences(AliasAnalysis *AA); + + /// Update the phi dependences to the DAG because ScheduleDAGInstrs no longer + /// processes dependences for PHIs. We also remove unneeded chain + /// dependences between Phis. + void updatePhiDependences(); + + /// Try to transform the instructions to improve the generated schedule. + void changeDependences(); + + /// Calculate the resource constrained minimum initiation interval. + unsigned calculateResMII(); + + /// Calculate the recurrence-constrainted minimum initiation interval. + /// A recurrence occurs if an operation in one iteration of the loop + /// has a dependence upon the same opration from a prior iteration. + unsigned calculateRecMII(NodeSetType &RecNodeSets); + + /// Find all the elementary circuits in the dependence graph using Johnson's + /// circuit algorithm. + void findCircuits(NodeSetType &NodeSets); + + /// Merge the recurrence node sets that have the same initial node. + void fuseRecs(NodeSetType &NodeSets); + + /// Remove nodes that have been scheduled in previous NodeSets. + void removeDuplicateNodes(NodeSetType &NodeSets); + + /// Merge all nodes + void mergeAllNodes(NodeSetType &NodeSets); + + // Several functions are needed by the algorithm for each node in the graph. + // This function computes the necessary information. + void computeNodeFunctions(NodeSetType &NodeSets); + + /// A heuristic to filter nodes in recurrent node-sets if the register + /// pressure of a set is too high. + void registerPressureFilter(NodeSetType &NodeSets); + + /// A heuristic to colocate node sets that have the same set of + /// successors. + void colocateNodeSets(NodeSetType &NodeSets); + + /// Check if the existing node-sets are profitable. If not, then ignore the + /// recurrent node-sets, and attempt to schedule all nodes together. + void checkNodeSets(NodeSetType &NodeSets); + + // Group the remaining nodes into sets based upon connected components. + void groupRemainingNodes(NodeSetType &NodeSets); + + // Add the node to the set, and add all is its connected nodes to the set. + void addConnectedNodes(SUnit *SU, NodeSet &NewSet, + SetVector &NodesAdded); + + // Generate an ordered list containing each node in the graph, + // which is used as the order for schduling the instructions. + void computeNodeOrder(NodeSetType &NodeSets, + SetVector&, OrderKind); //SYNOPSYS + + // Generate the pipelined schedule for the instructions, if possible. + // Return true if a schedule has been found. + bool schedulePipeline(SMSchedule &Schedule, + SetVector NodeOrder); //SYNOPSYS + + // Rearrange the instructions in the loop according to the schedule. + void generatePipelinedLoop(SMSchedule &Schedule); + + // Generate the prolog code for the pipeline. + void generateProlog(SMSchedule &Schedule, unsigned LastStage, + MachineBasicBlock *KernelBB, ValueMapTy *VRMap, + MBBVectorTy &PrologBBs); + + // Generate the epilog code for the software pipelined loop. + void generateEpilog(SMSchedule &Schedule, unsigned LastStage, + MachineBasicBlock *KernelBB, ValueMapTy *VRMap, + MBBVectorTy &EpilogBBs, MBBVectorTy &PrologBBs); + + /// Generate Phis in the pipelined loop for Phis that existed in the + /// original loop. + void generateExistingPhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1, + MachineBasicBlock *BB2, MachineBasicBlock *KernelBB, + SMSchedule &Schedule, ValueMapTy *VRMap, + InstrMapTy &InstrMap, unsigned LastStageNum, + unsigned CurStageNum, bool IsLast); + + /// Generate Phis for the specific block in the generated pipelined code. + void generatePhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1, + MachineBasicBlock *BB2, MachineBasicBlock *KernelBB, + SMSchedule &Schedule, ValueMapTy *VRMap, + InstrMapTy &InstrMap, unsigned LastStageNum, + unsigned CurStageNum, bool IsLast); + + // Remove instructions, in the epilog, that generate values with no uses. + // Typically, these are induction variable operations that generate values + // used in the loop itself. + void removeDeadInstructions(MachineBasicBlock *KernelBB, + MBBVectorTy &EpilogBBs); + + /// For loop carried definitions, we split the lifetime of a virtual register + /// that has uses past the defiition in the next iteration. A copy with a new + /// virtual register is inserted before the definition, which helps with + /// generating a better register assignment. + void splitLifetimes(MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs, + SMSchedule &Schedule); + + // Add branches and Phis between the prolog and epilog blocks. + void addBranches(MBBVectorTy &PrologBBs, MachineBasicBlock *KernelBB, + MBBVectorTy &EpilogBBs, SMSchedule &Schedule, + ValueMapTy *VRMap); + + /// Return true if we can compute the amount the instruction changes + /// during each iteration. Set Delta to the amount of the change. + bool computeDelta(MachineInstr *MI, unsigned &Delta); + + /// Update the memory operand with a new offset when the pipeliner + /// generate a new copy of the instruction that refers to a + /// different memory location. + void updateMemOperands(MachineInstr *NewMI, MachineInstr *OldMI, + unsigned Num); + + /// Clone the instruction for the new pipelined loop and update the + /// memory operands, if needed. + MachineInstr *cloneInstr(MachineInstr *OldMI, unsigned CurStageNum, + unsigned InstStageNum); + + /// Clone the instruction for the new pipelined loop. If needed, this + /// function updates the instruction using the values saved in the + /// InstrChanges structure. + MachineInstr *cloneAndChangeInstr(MachineInstr *OldMI, unsigned CurStageNum, + unsigned InstStageNum, + SMSchedule &Schedule); + + // Update the machine instruction with new virtual registers. This + // function may change both the defintions and/or uses. + void updateInstruction(MachineInstr *NewMI, bool LastDef, + unsigned CurStageNum, unsigned InstStageNum, + SMSchedule &Schedule, ValueMapTy *VRMap); + + // 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 *findDefInLoop(unsigned Reg); + + /// Return the new name for the value from the previous stage. + unsigned getPrevMapVal(unsigned StageNum, unsigned PhiStage, unsigned LoopVal, + ValueMapTy *VRMap, MachineBasicBlock *BB); + + /// Rewrite the Phi values in the specified block to use the mappings + /// from the initial operand. + void rewritePhiValues(MachineBasicBlock *NewBB, unsigned StageNum, + SMSchedule &Schedule, ValueMapTy *VRMap, + InstrMapTy &InstrMap); + + /// Rewrite a previously scheduled instruction to use a new register value, + /// which is created by a Phi typically. This version rewrites references + /// that occur at a specific stage only. + void rewriteScheduledInstr(MachineBasicBlock *BB, SMSchedule &Schedule, + InstrMapTy &InstrMap, unsigned CurStageNum, + unsigned PhiNum, MachineInstr *Phi, + unsigned OldReg, unsigned NewReg, + unsigned PrevReg = 0); + + /// 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. + bool canUseLastOffsetValue(MachineInstr *MI, unsigned &BasePos, + unsigned &OffsetPos, unsigned &NewBase, + int64_t &NewOffset); +}; + +// This class repesents the scheduled code. The main data structure is a +// map from scheduled cycle to instructions. During scheduling, the +// data structure explicitly represents all stages/iterations. When +// the algorithm finshes, the schedule is collapsed into a single stage, +// which represents instructions from different loop iterations. +// +// The SMS algorithm allows negative values for cycles, so the first cycle +// in the schedule is the smallest cycle value. +class SMSchedule { +private: + // Map from execution cycle to instructions. + DenseMap> ScheduledInstrs; + + // Map from instruction to execution cycle. + std::map InstrToCycle; + + // Map for each register and the max difference between its uses and def. + // The first element in the pair is the max difference in stages. The + // second is true if the register defines a Phi value and loop value is + // scheduled before the Phi. + std::map> RegToStageDiff; + + // Keep track of the first cycle value in the schedule. It starts + // as zero, but the algorithm allows negative values. + int FirstCycle; + + // Keep track of the last cycle value in the schedule. + int LastCycle; + + // The initiation interval (II) for the schedule. + int InitiationInterval; + + // Target machine information. + const TargetSubtargetInfo &ST; + + // Virtual register information. + MachineRegisterInfo &MRI; + + //DFAPacketizer *Resources; //SYNOPSYS commented out + ArcReservationTable Resources; //SYNOPSYS using a reservation table instead of a DFA + +public: + SMSchedule(MachineFunction *mf) + : ST(mf->getSubtarget()), MRI(mf->getRegInfo()), + Resources(mf->getSubtarget().getInstrItineraryData()) //SYNOPSYS using a reservation table instead of a DFA + //Resources(ST.getInstrInfo()->CreateTargetScheduleState(ST)) //SYNOPSYS commented out + { + FirstCycle = 0; + LastCycle = 0; + InitiationInterval = 0; + } + + ~SMSchedule() { + ScheduledInstrs.clear(); + InstrToCycle.clear(); + RegToStageDiff.clear(); + //delete Resources; //SYNOPSYS commented out + } + + void reset() { + ScheduledInstrs.clear(); + InstrToCycle.clear(); + RegToStageDiff.clear(); + Resources.clear(); //SYNOPSYS + 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); + + // Compute the scheduling start slot for the instruction. The start slot + // depends on any predecessor or successor nodes scheduled already. + void computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart, + int *MinEnd, int *MaxStart, int II, SwingSchedulerDAG *DAG); + + // 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 insert(SUnit *SU, int StartCycle, int EndCycle, int II); + + // Iterators for the cycle to instruction map. + typedef DenseMap>::iterator sched_iterator; + typedef DenseMap>::const_iterator + const_sched_iterator; + + // Return true if the instruction is scheduled at the specified stage. + bool isScheduledAtStage(SUnit *SU, unsigned StageNum) { + return (stageScheduled(SU) == (int)StageNum); + } + + // Return the stage for a scheduled instruction. Return -1 if + // the instruction has not been scheduled. + int stageScheduled(SUnit *SU) const { + std::map::const_iterator it = InstrToCycle.find(SU); + if (it == InstrToCycle.end()) + return -1; + return (it->second - FirstCycle) / InitiationInterval; + } + + /// Return the cycle for a scheduled instruction. This function normalizes + /// the first cycle to be 0. + unsigned cycleScheduled(SUnit *SU) const { + std::map::const_iterator it = InstrToCycle.find(SU); + assert(it != InstrToCycle.end() && "Instruction hasn't been scheduled."); + return (it->second - FirstCycle) % InitiationInterval; + } + + // Return the maximum stage count needed for this schedule. + unsigned getMaxStageCount() { + return (LastCycle - FirstCycle) / InitiationInterval; + } + + /// Return the max. number of stages/iterations that can occur between a + /// register definition and its uses. + unsigned getStagesForReg(int Reg, unsigned CurStage) { + std::pair Stages = RegToStageDiff[Reg]; + if (CurStage > getMaxStageCount() && Stages.first == 0 && Stages.second) + return 1; + return Stages.first; + } + + /// The number of stages for a Phi is a little different than other + /// instructions. The minimum value computed in RegToStageDiff is 1 + /// because we assume the Phi is needed for at least 1 iteration. + /// This is not the case if the loop value is scheduled prior to the + /// Phi in the same stage. This function returns the number of stages + /// or iterations needed between the Phi definition and any uses. + unsigned getStagesForPhi(int Reg) { + std::pair Stages = RegToStageDiff[Reg]; + if (Stages.second) + return Stages.first; + return Stages.first - 1; + } + + /// Return the instructions that are scheduled at the specified cycle. + std::deque &getInstructions(int cycle) { + return ScheduledInstrs[cycle]; + } + + // 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 finalizeSchedule(SwingSchedulerDAG *SSD); + + /// Order the instructions within a cycle so that the definitions occur + /// before the uses. + bool orderDependence(SwingSchedulerDAG *SSD, SUnit *SU, + std::deque &Insts); + + /// Return true if the scheduled Phi has a loop carried operand. + bool isLoopCarried(SwingSchedulerDAG *SSD, MachineInstr *Phi); + + /// Return true if the instruction is a definition that is loop carried + /// and defines the use on the next iteration. + bool isLoopCarriedDefOfUse(SwingSchedulerDAG *SSD, MachineInstr *Inst, + MachineOperand &MO); + + /// Print the schedule information to the given output. + void print(raw_ostream &os) const; + + /// Dump the schedule information to stderr. + void dump() const; +}; + +} // end anonymous namespace + +unsigned SwingSchedulerDAG::Circuits::MaxPaths = 5; +char MachineSMS::ID = 0; +#ifndef NDEBUG +int MachineSMS::NumTries = 0; +#endif +char &llvm::MachineSMSID = MachineSMS::ID; +INITIALIZE_PASS_BEGIN(MachineSMS, DEBUG_TYPE, "Modulo Software Pipelining", + false, false) +INITIALIZE_PASS_DEPENDENCY(LiveIntervals) +INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) +INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) +INITIALIZE_PASS_END(MachineSMS, DEBUG_TYPE, "Modulo Software Pipelining", + false, false) + +// The "main" function for implementing Swing Modulo Scheduling. +bool MachineSMS::runOnMachineFunction(MachineFunction &mf) { + + // + if (DUMP_BEFORE()) mf.dump(); + if (VIEW_BEFORE()) mf.viewCFG(); + // + + if (mf.getFunction()->getAttributes().hasAttribute( + AttributeSet::FunctionIndex, Attribute::OptimizeForSize) && + !EnableSWPOptSize.getPosition()) + return false; + + MF = &mf; + MLI = &getAnalysis(); + MDT = &getAnalysis(); + TII = MF->getSubtarget().getInstrInfo(); + RegClassInfo.runOnMachineFunction(*MF); + + bool changed = false; + for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E; + ++I) { + MachineLoop *L = *I; + // record result for -Rpass reporting + bool result = scheduleLoop(L); + if (!result) + L->emitOptimizationRemarkMissed(DEBUG_TYPE, "Failed to pipeline loop"); + changed |= result; + // + } + + // + if (DUMP_AFTER()) mf.dump(); + if (VIEW_AFTER()) mf.viewCFG(); + // + + return changed; +} + +// 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 MachineSMS::scheduleLoop(MachineLoop *L) { + bool Changed = false; + for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I) { + Changed = scheduleLoop(*I); + } + +#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; +} + +// +static bool pragmaPipelineDisabled(MachineBasicBlock* MBB) { + const BasicBlock* BB = MBB->getBasicBlock(); + if (BB == nullptr) return false; + const TerminatorInst* TI = BB->getTerminator(); + if (TI == nullptr) return false; + if (!TI->hasMetadataOtherThanDebugLoc()) return false; + SmallVector< std::pair< unsigned, MDNode*>, 4> md; + TI->getAllMetadata(md); + for (auto& P : md) { + MDTuple* MD = dyn_cast(P.second); + if (MD == nullptr) continue; + for (unsigned i = 0, ie = MD->getNumOperands(); i < ie; ++i) { + MDTuple* MD2 = dyn_cast(MD->getOperand(i).get()); + if (MD2 == nullptr) continue; + if (MD2->getNumOperands() != 2) continue; + MDString* MDS = dyn_cast(MD2->getOperand(0).get()); + if (MDS == nullptr) continue; + ValueAsMetadata* MDV = dyn_cast(MD2->getOperand(1).get()); + if (MDV == nullptr) continue; + ConstantInt* CI = dyn_cast(MDV->getValue()); + if (CI == nullptr) continue; + if (MDS->getString() == "llvm.loop.pipeline" && CI->isZero()) + return true; + } + } + return false; +} +// + + +// 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 MachineSMS::canPipelineLoop(MachineLoop *L) { + if (L->getNumBlocks() != 1) { + L->emitOptimizationRemarkAnalysis(DEBUG_TYPE, "Not a single basic block loop"); //SYNOPSYS + return false; + } + +// + if (pragmaPipelineDisabled(L->getHeader())) { + L->emitOptimizationRemarkAnalysis(DEBUG_TYPE, "Disabled by pragma"); + 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)) { + L->emitOptimizationRemarkAnalysis(DEBUG_TYPE, "Loop did not end in simple conditional branch"); //SYNOPSYS + return false; + } + + LI.LoopInductionVar = nullptr; + LI.LoopCompare = nullptr; + if (TII->AnalyzeLoop(L, LI.LoopInductionVar, LI.LoopCompare)) { + L->emitOptimizationRemarkAnalysis(DEBUG_TYPE, "Failed loop analysis"); //SYNOPSYS + return false; + } + + if (!L->getLoopPreheader()) { + L->emitOptimizationRemarkAnalysis(DEBUG_TYPE, "Loop does not have a valid preheader"); //SYNOPSYS + 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) { + L->emitOptimizationRemarkAnalysis(DEBUG_TYPE, "Loop contains references subregisters"); //SYNOPSYS + 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 MachineSMS::swingModuloScheduler(MachineLoop *L) { + assert(L->getBlocks().size() == 1 && "SMS works on single blocks only."); + + SwingSchedulerDAG SMS(this, L, &getAnalysis(), RegClassInfo); + + MachineBasicBlock *MBB = L->getHeader(); + // The kernel should not include any terminator instructions. These + // will be added back later. + SMS.startBlock(MBB); + + // Compute the number of 'real' instructions in the basic block by + // ignoring terminators. + unsigned size = MBB->size(); + for (MachineBasicBlock::iterator I = MBB->getFirstTerminator(), + E = MBB->instr_end(); + I != E; ++I, --size) + ; + + // + if (DUMP_LOOP_ATTEMPT()) { + dbgs() << "[MachineSMS::swingModuloScheduler] Attempting loop\n"; + MBB->dump(); + } + // + + SMS.enterRegion(MBB, MBB->begin(), MBB->getFirstTerminator(), size); + SMS.schedule(); + SMS.exitRegion(); + + SMS.finishBlock(); + return SMS.hasNewSchedule(); +} + +// We override the schedule function in ScheduleDAGInstrs to implement the +// scheduling part of the Swing Modulo Scheduling algorithm. +void SwingSchedulerDAG::schedule() { + AliasAnalysis *AA = &Pass->getAnalysis().getAAResults(); + buildSchedGraph(AA); + + addLoopCarriedDependences(AA); + updatePhiDependences(); + Topo.InitDAGTopologicalSorting(); + changeDependences(); + DEBUG({ + for (unsigned su = 0, e = SUnits.size(); su != e; ++su) + SUnits[su].dumpAll(this); + }); + + NodeSetType NodeSets; + findCircuits(NodeSets); + + // Calculate the MII. + unsigned ResMII = calculateResMII(); + unsigned RecMII = calculateRecMII(NodeSets); + + fuseRecs(NodeSets); + + // This flag is used for testing and can cause correctness problems. + if (SwpIgnoreRecMII) + RecMII = 0; + + MII = std::max(ResMII, RecMII); + DEBUG(dbgs() << "MII = " << MII << " (rec=" << RecMII << ", res=" << ResMII + << ")\n"); + + // Can't schedule a loop without a valid MII. + if (MII == 0) + return; + + // Don't pipeline large loops. + if (SwpMaxMii != -1 && (int)MII > SwpMaxMii) + return; + + computeNodeFunctions(NodeSets); + + registerPressureFilter(NodeSets); + + colocateNodeSets(NodeSets); + + checkNodeSets(NodeSets); + + DEBUG({ + for (auto &I : NodeSets) { + dbgs() << " Rec NodeSet "; + I.dump(); + } + }); + + std::sort(NodeSets.begin(), NodeSets.end(), std::greater()); + + groupRemainingNodes(NodeSets); + + removeDuplicateNodes(NodeSets); + + DEBUG({ + for (auto &I : NodeSets) { + dbgs() << " NodeSet "; + I.dump(); + } + }); + +// Try bi-directional, then BottomUp and then TopDown + + SetVector NodeOrderAny; + SMSchedule Schedule(Pass->MF); + + // Case 1 + computeNodeOrder(NodeSets, NodeOrderAny, AnyOrder); + if (NodeOrderAny.size() == 0) + return; + Scheduled = schedulePipeline(Schedule, NodeOrderAny); + DEBUG(dbgs() << ">>>>[Case 1] ScheduleFound = " << Scheduled << "\n"); + + // Case 2 + if (!Scheduled) { + SetVector NodeOrderBottomUp; + computeNodeOrder(NodeSets, NodeOrderBottomUp, BottomUp); + assert(NodeOrderBottomUp.size() != 0); + Scheduled = schedulePipeline(Schedule, NodeOrderBottomUp); + DEBUG(dbgs() << ">>>>[Case 2] ScheduleFound = " << Scheduled << "\n"); + } + + // Case 3 + if (!Scheduled) { + SetVector NodeOrderTopDown; + computeNodeOrder(NodeSets, NodeOrderTopDown, TopDown); + assert(NodeOrderTopDown.size() != 0); + Scheduled = schedulePipeline(Schedule, NodeOrderTopDown); + DEBUG(dbgs() << ">>>>[Case 3] ScheduleFound = " << Scheduled << "\n"); + } + +/**** Backup option for larger loop bodies ***/ + // Case 4 + if (!Scheduled) { + NodeSets.clear(); + NodeSet singleTopologicalNodeSet; + for (auto I = Topo.begin(),E = Topo.end(); I != E; ++I) + singleTopologicalNodeSet.insert(&SUnits[*I]); + NodeSets.push_back(singleTopologicalNodeSet); + SetVector NodeOrderBottomUpMerged; + computeNodeOrder(NodeSets, NodeOrderBottomUpMerged, BottomUp); + assert(NodeOrderBottomUpMerged.size() != 0); + Scheduled = schedulePipeline(Schedule, NodeOrderBottomUpMerged); + if (Scheduled) + dbgs() << ">>>>[Case 4] ScheduleFound!\n"; + } + + // Case 5 + if (!Scheduled) { + SetVector NodeOrderTopDownMerged; + computeNodeOrder(NodeSets, NodeOrderTopDownMerged, TopDown); + assert(NodeOrderTopDownMerged.size() != 0); + Scheduled = schedulePipeline(Schedule, NodeOrderTopDownMerged); + if (Scheduled) + dbgs() << ">>>>[Case 5] ScheduleFound!\n"; + } + + if (!Scheduled) + return; +// + +#if 0 //SYNOPSYS + + computeNodeOrder(NodeSets); + + SMSchedule Schedule(Pass->MF); + Scheduled = schedulePipeline(Schedule); + + if (!Scheduled) + return; + +#endif //SYNOPSYS + + 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 (SmallPtrSet::iterator I = NewMIs.begin(), + E = NewMIs.end(); + I != E; ++I) + MF.DeleteMachineInstr(*I); + NewMIs.clear(); + + // Call the superclass. + ScheduleDAGInstrs::finishBlock(); +} + +/// Return the register values for the operands of a Phi instruction. +/// This function assume the instruction is a Phi. +static void getPhiRegs(MachineInstr *Phi, MachineBasicBlock *Loop, + unsigned &InitVal, unsigned &LoopVal) { + assert(Phi->isPHI() && "Expecting a Phi."); + + InitVal = 0; + LoopVal = 0; + for (unsigned i = 1, e = Phi->getNumOperands(); i != e; i += 2) + if (Phi->getOperand(i + 1).getMBB() != Loop) + InitVal = Phi->getOperand(i).getReg(); + else if (Phi->getOperand(i + 1).getMBB() == Loop) + LoopVal = Phi->getOperand(i).getReg(); + + assert(InitVal != 0 && LoopVal != 0 && "Unexpected Phi structure."); +} + +/// Return the Phi register value that comes from the incoming block. +static unsigned getInitPhiReg(MachineInstr *Phi, MachineBasicBlock *LoopBB) { + for (unsigned i = 1, e = Phi->getNumOperands(); i != e; i += 2) + if (Phi->getOperand(i + 1).getMBB() != LoopBB) + return Phi->getOperand(i).getReg(); + return 0; +} + +/// Return the Phi register value that comes the the loop block. +static unsigned getLoopPhiReg(MachineInstr *Phi, MachineBasicBlock *LoopBB) { + for (unsigned i = 1, e = Phi->getNumOperands(); i != e; i += 2) + if (Phi->getOperand(i + 1).getMBB() == LoopBB) + return Phi->getOperand(i).getReg(); + return 0; +} + +/// Return true if SUb can be reached from SUa following the chain edges. +static bool isSuccOrder(SUnit *SUa, SUnit *SUb) { + SmallPtrSet Visited; + SmallVector Worklist; + Worklist.push_back(SUa); + while (!Worklist.empty()) { + const SUnit *SU = Worklist.pop_back_val(); + for (auto &SI : SU->Succs) { + SUnit *SuccSU = SI.getSUnit(); + if (SI.getKind() == SDep::Order) { + if (Visited.count(SuccSU)) + continue; + if (SuccSU == SUb) + return true; + Worklist.push_back(SuccSU); + Visited.insert(SuccSU); + } + } + } + return false; +} + +/// Return true if the instruction causes a chain between memory +/// references before and after it. +static bool isDependenceBarrier(MachineInstr *MI, AliasAnalysis *AA) { + return MI->isCall() || MI->hasUnmodeledSideEffects() || + (MI->hasOrderedMemoryRef() && + (!MI->mayLoad() || !MI->isInvariantLoad(AA))); +} + +/// Return the underlying objects for the memory references of an instruction. +/// This function calls the code in ValueTracking, but first checks that the +/// instruction has a memory operand. +static void getUnderlyingObjects(MachineInstr *MI, + SmallVectorImpl &Objs, + const DataLayout &DL) { + if (!MI->hasOneMemOperand()) + return; + MachineMemOperand *MM = *MI->memoperands_begin(); + if (!MM->getValue()) + return; + GetUnderlyingObjects(const_cast(MM->getValue()), Objs, DL); +} + +/// Add a chain edge between a load and store if the store can be an +/// alias of the load on a subsequent iteration, i.e., a loop carried +/// dependence. This code is very similar to the code in ScheduleDAGInstrs +/// but that code doesn't create loop carried dependences. +void SwingSchedulerDAG::addLoopCarriedDependences(AliasAnalysis *AA) { + MapVector> PendingLoads; + for (auto &SU : SUnits) { + MachineInstr *MI = SU.getInstr(); + + if (isDependenceBarrier(MI, AA)) + PendingLoads.clear(); + else if (MI->mayLoad()) { + SmallVector Objs; + getUnderlyingObjects(MI, Objs, MF.getDataLayout()); + for (auto V : Objs) { + SmallVector &SUs = PendingLoads[V]; + SUs.push_back(&SU); + } + } else if (MI->mayStore()) { + SmallVector Objs; + getUnderlyingObjects(MI, Objs, MF.getDataLayout()); + for (auto V : Objs) { + MapVector>::iterator I = + PendingLoads.find(V); + if (I == PendingLoads.end()) + continue; + for (auto Load : I->second) { + if (isSuccOrder(Load, &SU)) + continue; + MachineInstr *LdMI = Load->getInstr(); + // First, perform the cheaper check that compares the base register. + // If they are the same and the load offset is less than the store + // offset, then mark the dependence as loop carried potentially. + unsigned BaseReg1, Offset1, BaseReg2, Offset2; + if (!TII->getMemOpBaseRegImmOfs(LdMI, BaseReg1, Offset1, TRI) || + !TII->getMemOpBaseRegImmOfs(MI, BaseReg2, Offset2, TRI)) + continue; + if (BaseReg1 == BaseReg2 && (int)Offset1 < (int)Offset2) { + assert(TII->areMemAccessesTriviallyDisjoint(LdMI, MI, AA) && + "What happened to the chain edge?"); + SU.addPred(SDep(Load, SDep::Barrier)); + continue; + } + // Second, the more expensive check that uses alias analysis on the + // base registers. If they alias, and the load offset is less than + // the store offset, the mark the dependence as loop carried. + if (!AA) + continue; + MachineMemOperand *MMO1 = *LdMI->memoperands_begin(); + MachineMemOperand *MMO2 = *MI->memoperands_begin(); + if (!MMO1->getValue() || !MMO2->getValue()) + continue; + if (MMO1->getValue() == MMO2->getValue() && + MMO1->getOffset() <= MMO2->getOffset()) { + SU.addPred(SDep(Load, SDep::Barrier)); + continue; + } + AliasResult AAResult = AA->alias( + MemoryLocation(MMO1->getValue(), MemoryLocation::UnknownSize, + MMO1->getAAInfo()), + MemoryLocation(MMO2->getValue(), MemoryLocation::UnknownSize, + MMO2->getAAInfo())); + + if (AAResult != NoAlias) + SU.addPred(SDep(Load, SDep::Barrier)); + } + } + } + } +} + +/// Update the phi dependences to the DAG because ScheduleDAGInstrs no longer +/// processes dependences for PHIs. This function adds true dependences +/// from a PHI to a use, and a loop carried dependence from the use to the +/// PHI. The loop carried dependence is represented as an anti dependence +/// edge. This function also removes chain dependences between unrelated +/// PHIs. +void SwingSchedulerDAG::updatePhiDependences() { + SmallVector RemoveDeps; + const TargetSubtargetInfo &ST = MF.getSubtarget(); + + // Iterate over each DAG node. + for (std::vector::iterator I = SUnits.begin(), E = SUnits.end(); + I != E; ++I) { + RemoveDeps.clear(); + // Set to true if the instruction has an operand defined by a Phi. + unsigned HasPhiUse = 0; + unsigned HasPhiDef = 0; + MachineInstr *MI = I->getInstr(); + // Iterate over each operand, and we process the definitions. + for (MachineInstr::mop_iterator MOI = MI->operands_begin(), + MOE = MI->operands_end(); + MOI != MOE; ++MOI) { + if (!MOI->isReg()) + continue; + unsigned Reg = MOI->getReg(); + if (MOI->isDef()) { + // If the register is used by a Phi, then create an anti dependence. + for (MachineRegisterInfo::use_instr_iterator + UI = MRI.use_instr_begin(Reg), + UE = MRI.use_instr_end(); + UI != UE; ++UI) { + MachineInstr *UseMI = &*UI; + SUnit *SU = getSUnit(UseMI); + if (SU != 0 && UseMI->isPHI()) { + if (!MI->isPHI()) { + SDep Dep(SU, SDep::Anti, Reg); + I->addPred(Dep); + } else { + HasPhiDef = Reg; + // Add a chain edge to a dependent Phi that isn't an existing + // predecessor. + if (SU->NodeNum < I->NodeNum && !I->isPred(SU)) + I->addPred(SDep(SU, SDep::Barrier)); + } + } + } + } else if (MOI->isUse()) { + // If the register is defined by a Phi, then create a true dependence. + MachineInstr *DefMI = MRI.getUniqueVRegDef(Reg); + if (DefMI == 0) + continue; + SUnit *SU = getSUnit(DefMI); + if (SU != 0 && DefMI->isPHI()) { + if (!MI->isPHI()) { + SDep Dep(SU, SDep::Data, Reg); + Dep.setLatency(0); + ST.adjustSchedDependency(SU, &*I, Dep); + I->addPred(Dep); + } else { + HasPhiUse = Reg; + // Add a chain edge to a dependent Phi that isn't an existing + // predecessor. + if (SU->NodeNum < I->NodeNum && !I->isPred(SU)) + I->addPred(SDep(SU, SDep::Barrier)); + } + } + } + } + // Remove order dependences from an unrelated Phi. + if (!SwpPruneDeps) + continue; + for (SUnit::pred_iterator PI = I->Preds.begin(), PE = I->Preds.end(); + PI != PE; ++PI) { + 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 (std::vector::iterator I = SUnits.begin(), E = SUnits.end(); + I != E; ++I) { + unsigned BasePos = 0, OffsetPos = 0, NewBase = 0; + int64_t NewOffset = 0; + if (!canUseLastOffsetValue(I->getInstr(), BasePos, OffsetPos, NewBase, + NewOffset)) + continue; + + // Get the MI and SUnit for the instruction that defines the original base. + unsigned OrigBase = I->getInstr()->getOperand(BasePos).getReg(); + MachineInstr *DefMI = MRI.getUniqueVRegDef(OrigBase); + if (!DefMI) + continue; + SUnit *DefSU = getSUnit(DefMI); + if (!DefSU) + continue; + // Get the MI and SUnit for the instruction that defins the new base. + MachineInstr *LastMI = MRI.getUniqueVRegDef(NewBase); + if (!LastMI) + continue; + SUnit *LastSU = getSUnit(LastMI); + if (!LastSU) + continue; + + if (Topo.IsReachable(&*I, LastSU)) + continue; + + // Remove the dependence. The value now depends on a prior iteration. + SmallVector Deps; + for (SUnit::pred_iterator P = I->Preds.begin(), E = I->Preds.end(); P != E; + ++P) + if (P->getSUnit() == DefSU) + Deps.push_back(*P); + for (int i = 0, e = Deps.size(); i != e; i++) { + Topo.RemovePred(&*I, Deps[i].getSUnit()); + I->removePred(Deps[i]); + } + // Remove the chain dependence between the instructions. + Deps.clear(); + for (SUnit::pred_iterator P = LastSU->Preds.begin(), + E = LastSU->Preds.end(); + P != E; ++P) + if (P->getSUnit() == &*I && P->getKind() == SDep::Order) + Deps.push_back(*P); + for (int i = 0, e = Deps.size(); i != e; i++) { + Topo.RemovePred(LastSU, Deps[i].getSUnit()); + LastSU->removePred(Deps[i]); + } + + // Add a dependence between the new instruction and the instruction + // that defines the new base. + SDep Dep(&*I, SDep::Anti, NewBase); + LastSU->addPred(Dep); + + // Remember the base and offset information so that we can update the + // instruction during code generation. + InstrChanges[&*I] = std::make_pair(NewBase, NewOffset); + } +} + +namespace { +// FuncUnitSorter - Comparison operator used to sort instructions by +// the number of functional unit choices. +struct FuncUnitSorter { + const InstrItineraryData *InstrItins; + DenseMap Resources; + + // Compute the number of functional unit alternatives needed + // at each stage, and take the minimum value. We prioritize the + // instructions by the least number of choices first. + unsigned minFuncUnits(const MachineInstr *Inst, unsigned &F) const { + unsigned schedClass = Inst->getDesc().getSchedClass(); + unsigned min = UINT_MAX; + for (const InstrStage *IS = InstrItins->beginStage(schedClass), + *IE = InstrItins->endStage(schedClass); + IS != IE; ++IS) { + unsigned funcUnits = IS->getUnits(); + unsigned numAlternatives = countPopulation(funcUnits); + if (numAlternatives < min) { + min = numAlternatives; + F = funcUnits; + } + } + return min; + } + + // Compute the critical resources needed by the instruction. This + // function records the functional units needed by instructions that + // must use only one functional unit. We use this as a tie breaker + // for computing the resource MII. The instrutions that require + // the same, highly used, functional unit have high priority. + void calcCriticalResources(const MachineInstr *MI) { + unsigned SchedClass = MI->getDesc().getSchedClass(); + for (const InstrStage *IS = InstrItins->beginStage(SchedClass), + *IE = InstrItins->endStage(SchedClass); + IS != IE; ++IS) { + unsigned FuncUnits = IS->getUnits(); + if (countPopulation(FuncUnits) == 1) + Resources[FuncUnits]++; + } + } + + FuncUnitSorter(const InstrItineraryData *IID) : InstrItins(IID) {} + /// Return true if IS1 has less priority than IS2. + bool operator()(const MachineInstr *IS1, const MachineInstr *IS2) const { + unsigned F1 = 0, F2 = 0; + unsigned MFUs1 = minFuncUnits(IS1, F1); + unsigned MFUs2 = minFuncUnits(IS2, F2); + if (MFUs1 == 1 && MFUs2 == 1) + return Resources.lookup(F1) < Resources.lookup(F2); + return MFUs1 > MFUs2; + } +}; +} + +/// Calculate the resource constrained minimum initiation interval for the +/// specified loop. We use the DFA to model the resources needed for +/// each instruction, and we ignore dependences. A different DFA is created +/// for each cycle that is required. When adding a new instruction, we attempt +/// to add it to each existing DFA, until a legal space is found. If the +/// instruction cannot be reserved in an existing DFA, we create a new one. +unsigned SwingSchedulerDAG::calculateResMII() { + //SmallVector Resources; //SYNOPSYS commented out + ArcReservationTable Resources(MF.getSubtarget().getInstrItineraryData()); //SYNOPSYS using ArcReservationTable instead of DFAPacketizer + MachineBasicBlock *MBB = Loop->getHeader(); + //Resources.push_back(TII->CreateTargetScheduleState(MF.getSubtarget())); //SYNOPSYS commented out + + // Sort the instructions by the number of available choices for scheduling, + // least to most. Use the number of critical resources as the tie breaker. + FuncUnitSorter FUS = + FuncUnitSorter(MF.getSubtarget().getInstrItineraryData()); + for (MachineBasicBlock::iterator I = MBB->getFirstNonPHI(), + E = MBB->getFirstTerminator(); + I != E; ++I) + FUS.calcCriticalResources(I); + PriorityQueue, FuncUnitSorter> + FuncUnitOrder(FUS); + + for (MachineBasicBlock::iterator I = MBB->getFirstNonPHI(), + E = MBB->getFirstTerminator(); + I != E; ++I) + FuncUnitOrder.push(I); + + while (!FuncUnitOrder.empty()) { + MachineInstr *MI = FuncUnitOrder.top(); + FuncUnitOrder.pop(); + if (TII->isZeroCost(MI->getOpcode())) + continue; + + // +#if 1 + for (unsigned C = Resources.firstPotentialIssueCycle(); Resources.isCycleValid(C); ++C) + if (Resources.canReserveAtCycle(MI, C)) { + Resources.reserveAtCycle(MI, C); + break; + } +#else + // This appears to be all wrong. It appears to repeatedly ask if + // it can return the 1st functional unit in the itineraries over + // and over again for NumCycles. It seems to me it should check + // and then reserve each FU in the itinerary for each cycle the + // itinerary specifies. + // + + // Attempt to reserve the instruction in an existing DFA. At least one + // DFA is needed for each cycle. + unsigned NumCycles = getSUnit(MI)->Latency; + unsigned ReservedCycles = 0; + + SmallVectorImpl::iterator RI = Resources.begin(); + SmallVectorImpl::iterator RE = Resources.end(); + for (unsigned C = 0; C < NumCycles; ++C) + while (RI != RE) { + if ((*RI++)->canReserveResources(MI)) { + ++ReservedCycles; + break; + } + } + // Start reserving resources using existing DFAs. + for (unsigned C = 0; C < ReservedCycles; ++C) { + --RI; + (*RI)->reserveResources(MI); + } + // Add new DFAs, if needed, to reserve resources. + for (unsigned C = ReservedCycles; C < NumCycles; ++C) { + DFAPacketizer *NewResource = + TII->CreateTargetScheduleState(MF.getSubtarget()); + assert(NewResource->canReserveResources(MI) && "Reserve error."); + NewResource->reserveResources(MI); + Resources.push_back(NewResource); + } +#endif //SYNOPSYS + } +#// +#if 1 + int Resmii = Resources.getMaxIssueCycles(); +#else // + int Resmii = Resources.size(); + // Delete the memory for each of the DFAs that were created earlier. + for (SmallVectorImpl::iterator RI = Resources.begin(), + RE = Resources.end(); + RI != RE; ++RI) { + DFAPacketizer *D = *RI; + delete D; + } + Resources.clear(); +#endif //SYNOPSYS + 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 (NodeSetType::iterator NS = NodeSets.begin(), ENS = NodeSets.end(); + NS != ENS; ++NS) { + NodeSet &Nodes = *NS; + if (Nodes.size() == 0) + continue; + + unsigned Delay = Nodes.size() - 1; + unsigned Distance = 1; + + // ii = ceil(delay / distance) + unsigned CurMII = (Delay + Distance - 1) / Distance; + Nodes.setRecMII(CurMII); + if (CurMII > RecMII) + RecMII = CurMII; + } + + return RecMII; +} + +/// Swap all the anti dependences in the DAG. That means it is no longer a DAG, +/// but we do this to find the circuits, and then change them back. +static void swapAntiDependences(std::vector &SUnits) { + SmallVector, 8> DepsAdded; + for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { + SUnit *SU = &SUnits[i]; + for (SUnit::pred_iterator IP = SU->Preds.begin(), EP = SU->Preds.end(); + IP != EP; ++IP) { + if (IP->getKind() != SDep::Anti) + continue; + DepsAdded.push_back(std::make_pair(SU, *IP)); + } + } + for (SmallVector, 8>::iterator I = DepsAdded.begin(), + E = DepsAdded.end(); + I != E; ++I) { + // Remove this anti dependency and add one in the reverse direction. + SUnit *SU = I->first; + SDep &D = I->second; + SUnit *TargetSU = D.getSUnit(); + unsigned Reg = D.getReg(); + unsigned Lat = D.getLatency(); + SU->removePred(D); + SDep Dep(SU, SDep::Anti, Reg); + Dep.setLatency(Lat); + TargetSU->addPred(Dep); + } +} + +/// Create the adjacency structure of the nodes in the graph. +void SwingSchedulerDAG::Circuits::createAdjacencyStructure( + SwingSchedulerDAG *DAG) { + BitVector Added(SUnits.size()); + for (int i = 0, e = SUnits.size(); i != e; ++i) { + Added.reset(); + // Add any successor to the adjacency matrix and exclude duplicates. + for (auto &SI : SUnits[i].Succs) { + // A back-edge is processed only if it goes to a Phi. + if (SI.getKind() == SDep::Anti && !SI.getSUnit()->getInstr()->isPHI()) + continue; + int N = SI.getSUnit()->NodeNum; + if (N == -1) continue; + 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. +bool SwingSchedulerDAG::Circuits::circuit(int V, int S, NodeSetType &NodeSets, + bool HasBackedge) { + SUnit *SV = &SUnits[V]; + bool F = false; + Stack.push_back(SV); + Blocked.set(V); + + for (auto W : AdjK[V]) { + if (NumPaths > MaxPaths) + break; + if (W < S) + continue; + if (W == S) { + if (!HasBackedge) + NodeSets.push_back(NodeSet(Stack.begin(), Stack.end())); + F = true; + ++NumPaths; + break; + } else if (!Blocked.test(W)) { + if (circuit(W, S, NodeSets, W < V ? true : HasBackedge)) + F = true; + } + } + + if (F) + unblock(V); + else { + for (auto W : AdjK[V]) { + if (W < S) + continue; + if (B[W].count(SV) == 0) + B[W].insert(SV); + } + } + Stack.pop_back(); + return F; +} + +/// Unblock a node in the circuit finding algorithm. +void SwingSchedulerDAG::Circuits::unblock(int U) { + Blocked.reset(U); + SmallPtrSet &BU = B[U]; + while (!BU.empty()) { + SmallPtrSet::iterator SI = BU.begin(); + assert(SI != BU.end() && "Invalid B set."); + SUnit *W = *SI; + BU.erase(W); + if (Blocked.test(W->NodeNum)) + unblock(W->NodeNum); + } +} + +/// Identify all the elementary circuits in the dependence graph using +/// Johnson's circuit algorithm. +void SwingSchedulerDAG::findCircuits(NodeSetType &NodeSets) { + // Swap all the anti dependences in the DAG. That means it is no longer a DAG, + // but we do this to find the circuits, and then change them back. + swapAntiDependences(SUnits); + + Circuits Cir(SUnits); + // Create the adjacency structure. + Cir.createAdjacencyStructure(this); + for (int i = 0, e = SUnits.size(); i != e; ++i) { + Cir.reset(); + Cir.circuit(i, i, NodeSets); + } + + // Change the dependences back so that we've created a DAG again. + swapAntiDependences(SUnits); +} + +// Return true for DAG nodes that we ignore when computing the cost functions. +// We ignore the back-edge recurrence in order to avoid unbounded recurison +// in the calculation of the ASAP, ALAP, etc functions. +static bool ignoreDependence(const SDep &D, bool isPred) { + if (D.isArtificial()) + return true; + return D.getKind() == SDep::Anti && isPred; +} + +// Compute several functions need to order the nodes for scheduling. +// ASAP - Earliest time to schedule a node. +// ALAP - Latest time to schedule a node. +// MOV - Mobility function, difference between ALAP and ASAP. +// D - Depth of each node. +// H - Height of each node. +// +void SwingSchedulerDAG::computeNodeFunctions(NodeSetType &NodeSets) { + + ScheduleInfo.resize(SUnits.size()); + + DEBUG({ + for (ScheduleDAGTopologicalSort::const_iterator I = Topo.begin(), + E = Topo.end(); + I != E; ++I) { + SUnit *SU = &SUnits[*I]; + SU->dump(this); + } + }); + + int maxASAP = 0; + // Compute ASAP. + for (ScheduleDAGTopologicalSort::const_iterator I = Topo.begin(), + E = Topo.end(); + I != E; ++I) { + int asap = 0; + SUnit *SU = &SUnits[*I]; + for (SUnit::const_pred_iterator IP = SU->Preds.begin(), + EP = SU->Preds.end(); + IP != EP; ++IP) { + if (ignoreDependence(*IP, true)) + continue; + SUnit *pred = IP->getSUnit(); + asap = std::max(asap, (int)(getASAP(pred) + getLatency(SU, *IP) - + getDistance(pred, SU, *IP) * MII)); + } + + maxASAP = std::max(maxASAP, asap); + ScheduleInfo[*I].ASAP = asap; + } + + // Compute ALAP and MOV. + for (ScheduleDAGTopologicalSort::const_reverse_iterator I = Topo.rbegin(), + E = Topo.rend(); + I != E; ++I) { + int alap = maxASAP; + SUnit *SU = &SUnits[*I]; + for (SUnit::const_succ_iterator IS = SU->Succs.begin(), + ES = SU->Succs.end(); + IS != ES; ++IS) { + if (ignoreDependence(*IS, true)) + continue; + SUnit *succ = IS->getSUnit(); + alap = std::min(alap, (int)(getALAP(succ) - getLatency(SU, *IS) + + getDistance(SU, succ, *IS) * MII)); + } + + ScheduleInfo[*I].ALAP = alap; + } + + // After computing the node functions, compute the summary for each node set. + for (NodeSetType::iterator I = NodeSets.begin(), E = NodeSets.end(); I != E; + ++I) + I->computeNodeSetInfo(this); + + DEBUG({ + for (unsigned i = 0; i < SUnits.size(); i++) { + dbgs() << "\tNode " << i << ":\n"; + dbgs() << "\t ASAP = " << getASAP(&SUnits[i]) << "\n"; + dbgs() << "\t ALAP = " << getALAP(&SUnits[i]) << "\n"; + dbgs() << "\t MOV = " << getMOV(&SUnits[i]) << "\n"; + dbgs() << "\t D = " << getDepth(&SUnits[i]) << "\n"; + dbgs() << "\t H = " << getHeight(&SUnits[i]) << "\n"; + } + }); +} + +/// Compute the Pred_L(O) set, as defined in the paper. The set is defined +/// as the predecessors of the elements of NodeOrder that are not also in +/// NodeOrder. +static bool pred_L(SetVector &NodeOrder, + SmallSetVector &Preds, + const SwingSchedulerDAG::NodeSet *S = nullptr) { + Preds.clear(); + for (SetVector::iterator I = NodeOrder.begin(), E = NodeOrder.end(); + I != E; ++I) { + for (SUnit::pred_iterator PI = (*I)->Preds.begin(), PE = (*I)->Preds.end(); + PI != PE; ++PI) { + if (S && S->count(PI->getSUnit()) == 0) + continue; + if (ignoreDependence(*PI, true)) + continue; + if (NodeOrder.count(PI->getSUnit()) == 0) + Preds.insert(PI->getSUnit()); + } + // Back-edges are predecessors with an anti-dependence. + for (SUnit::const_succ_iterator IS = (*I)->Succs.begin(), + ES = (*I)->Succs.end(); + IS != ES; ++IS) { + if (IS->getKind() != SDep::Anti) + continue; + if (S && S->count(IS->getSUnit()) == 0) + continue; + if (NodeOrder.count(IS->getSUnit()) == 0) + Preds.insert(IS->getSUnit()); + } + } + return Preds.size() > 0; +} + +/// Compute the Succ_L(O) set, as defined in the paper. The set is defined +/// as the successors of the elements of NodeOrder that are not also in +/// NodeOrder. +static bool succ_L(SetVector &NodeOrder, + SmallSetVector &Succs, + const SwingSchedulerDAG::NodeSet *S = nullptr) { + Succs.clear(); + for (SetVector::iterator I = NodeOrder.begin(), E = NodeOrder.end(); + I != E; ++I) { + for (SUnit::succ_iterator SI = (*I)->Succs.begin(), SE = (*I)->Succs.end(); + SI != SE; ++SI) { + if (S && S->count(SI->getSUnit()) == 0) + continue; + if (ignoreDependence(*SI, false)) + continue; + if (NodeOrder.count(SI->getSUnit()) == 0) + Succs.insert(SI->getSUnit()); + } + for (SUnit::const_pred_iterator PI = (*I)->Preds.begin(), + PE = (*I)->Preds.end(); + PI != PE; ++PI) { + if (PI->getKind() != SDep::Anti) + continue; + if (S && S->count(PI->getSUnit()) == 0) + continue; + if (NodeOrder.count(PI->getSUnit()) == 0) + Succs.insert(PI->getSUnit()); + } + } + return Succs.size() > 0; +} + +/// Return true if there is a path from the specified node to any of the nodes +/// in DestNodes. Keep track and return the nodes in any path. +static bool computePath(SUnit *Cur, SetVector &Path, + SetVector &DestNodes, + SetVector &Exclude, + SmallPtrSet &Visited) { + if (Cur->isBoundaryNode()) + return false; + if (Exclude.count(Cur) != 0) + return false; + if (DestNodes.count(Cur) != 0) + return true; + if (!Visited.insert(Cur).second) + return Path.count(Cur) != 0; + bool FoundPath = false; + for (SUnit::succ_iterator SI = Cur->Succs.begin(), SE = Cur->Succs.end(); + SI != SE; ++SI) + FoundPath |= computePath(SI->getSUnit(), Path, DestNodes, Exclude, Visited); + for (SUnit::pred_iterator PI = Cur->Preds.begin(), PE = Cur->Preds.end(); + PI != PE; ++PI) + if (PI->getKind() == SDep::Anti) + FoundPath |= + computePath(PI->getSUnit(), Path, DestNodes, Exclude, Visited); + if (FoundPath) + Path.insert(Cur); + return FoundPath; +} + +/// Return true if Set1 is a subset of Set2. +template static bool isSubset(S1Ty &Set1, S2Ty &Set2) { + for (typename S1Ty::iterator I = Set1.begin(), E = Set1.end(); I != E; ++I) + if (Set2.count(*I) == 0) + return false; + return true; +} + + +/// Compute the live-out registers for the instructions in a node-set. +/// The live-out registers are those that are defined in the node-set, +/// but not used. Except for use operands of Phis. +static void computeLiveOuts(RegPressureTracker &RPTracker, + SwingSchedulerDAG::NodeSet &NS) { + SmallVector LiveOutRegs; + SmallSet Uses; + for (auto &I : NS) { + const MachineInstr *MI = I->getInstr(); + if (MI->isPHI()) + continue; + for (ConstMIOperands MO(MI); MO.isValid(); ++MO) + if (MO->isReg() && MO->isUse()) + Uses.insert(MO->getReg()); + } + for (auto &I : NS) + for (ConstMIOperands MO(I->getInstr()); MO.isValid(); ++MO) + if (MO->isReg() && MO->isDef() && !MO->isDead() && + !Uses.count(MO->getReg())) + LiveOutRegs.push_back(MO->getReg()); + RPTracker.addLiveRegs(LiveOutRegs); +} + +/// A heuristic to filter nodes in recurrent node-sets if the register +/// pressure of a set is too high. +void SwingSchedulerDAG::registerPressureFilter(NodeSetType &NodeSets) { + for (auto &NS : NodeSets) { + // Skip small node-sets since they won't cause register pressure problems. + if (NS.size() <= 2) + continue; + IntervalPressure RecRegPressure; + RegPressureTracker RecRPTracker(RecRegPressure); + RecRPTracker.init(&MF, &RegClassInfo, LIS, BB, BB->end(), false/*, true*/); + computeLiveOuts(RecRPTracker, NS); + RecRPTracker.closeBottom(); + + std::vector SUnits(NS.begin(), NS.end()); + std::sort(SUnits.begin(), SUnits.end(), [](const SUnit *A, const SUnit *B) { + return A->NodeNum > B->NodeNum; + }); + + for (auto &SU : SUnits) { + // Since we're computing the register pressure for a subset of the + // instructions in a block, we need to set the tracker for each + // instruction in the node-set. The tracker is set to the instruction + // just after the one we're interested in. + MachineBasicBlock::const_iterator CurInstI = SU->getInstr(); + RecRPTracker.setPos(std::next(CurInstI)); + + RegPressureDelta RPDelta; + ArrayRef CriticalPSets; + RecRPTracker.getMaxUpwardPressureDelta(SU->getInstr(), nullptr, RPDelta, + CriticalPSets, + RecRegPressure.MaxSetPressure); + if (RPDelta.Excess.isValid()) { + DEBUG(dbgs() << "Excess register pressure: SU(" << SU->NodeNum << ") " + << TRI->getRegPressureSetName(RPDelta.Excess.getPSet()) + << ":" << RPDelta.Excess.getUnitInc()); + NS.setExceedPressure(SU); + break; + } + RecRPTracker.recede(); + } + } +} + +/// A heuristic to colocate node sets that have the same set of +/// successors. +void SwingSchedulerDAG::colocateNodeSets(NodeSetType &NodeSets) { + unsigned Colocate = 0; + for (int i = 0, e = NodeSets.size(); i < e; ++i) { + NodeSet &N1 = NodeSets[i]; + SmallSetVector S1; + if (N1.empty() || !succ_L(N1, S1)) + continue; + for (int j = i + 1; j < e; ++j) { + NodeSet &N2 = NodeSets[j]; + if (N1.compareRecMII(N2) != 0) + continue; + SmallSetVector S2; + if (N2.empty() || !succ_L(N2, S2)) + continue; + if (isSubset(S1, S2) && S1.size() == S2.size()) { + N1.setColocate(++Colocate); + N2.setColocate(Colocate); + break; + } + } + } +} + +/// Check if the existing node-sets are profitable. If not, then ignore the +/// recurrent node-sets, and attempt to schedule all nodes together. This is +/// a heuristic. If the MII is large and there is a non-recurrent node with +/// a large depth compared to the MII, then it's best to try and schedule +/// all instruction together instead of starting with the recurrent node-sets. +void SwingSchedulerDAG::checkNodeSets(NodeSetType &NodeSets) { + // Look for loops with a large MII. + if (MII <= 20) + return; + // Check if the node-set contains only a simple add recurrence. + for (auto &NS : NodeSets) + if (NS.size() > 2) + return; + // If the depth of any instruction is significantly larger than the MII, then + // ignore the recurrent node-sets and treat all instructions equally. + for (auto &SU : SUnits) + if (SU.getDepth() > MII * 1.5) { + NodeSets.clear(); + DEBUG(dbgs() << "Clear recurrence node-sets\n"); + return; + } +} + +// Add the nodes that do not belong to a recurrence set into groups +// based upon connected componenets. +void SwingSchedulerDAG::groupRemainingNodes(NodeSetType &NodeSets) { + SetVector NodesAdded; + SmallPtrSet Visited; + // Add the nodes that are on a path between the previous node sets and + // the current node set. + for (NodeSetType::iterator I = NodeSets.begin(), E = NodeSets.end(); I != E; + ++I) { + SmallSetVector N; + // Add the nodes from the current node set to the previous node set. + if (succ_L(*I, N)) { + SetVector Path; + for (SmallSetVector::iterator NI = N.begin(), NE = N.end(); + NI != NE; ++NI) { + Visited.clear(); + computePath(*NI, Path, NodesAdded, *I, Visited); + } + if (Path.size() > 0) + (*I).insert(Path.begin(), Path.end()); + } + // Add the nodes from the previous node set to the current node set. + N.clear(); + if (succ_L(NodesAdded, N)) { + SetVector Path; + for (SmallSetVector::iterator NI = N.begin(), NE = N.end(); + NI != NE; ++NI) { + Visited.clear(); + computePath(*NI, Path, *I, NodesAdded, Visited); + } + if (Path.size() > 0) + (*I).insert(Path.begin(), Path.end()); + } + NodesAdded.insert((*I).begin(), (*I).end()); + } + + // Create a new node set with the connected nodes of any successor of a node + // in a recurrent set. + NodeSet NewSet; + SmallSetVector N; + if (succ_L(NodesAdded, N)) + for (SmallSetVector::iterator I = N.begin(), E = N.end(); + I != E; ++I) + 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 (SmallSetVector::iterator I = N.begin(), E = N.end(); + I != E; ++I) + addConnectedNodes(*I, NewSet, NodesAdded); + if (NewSet.size() > 0) + NodeSets.push_back(NewSet); + + // Create new nodes sets with the connected nodes any any remaining node that + // has no predecessor. + for (unsigned i = 0; i < SUnits.size(); ++i) { + SUnit *SU = &SUnits[i]; + if (NodesAdded.count(SU) == 0) { + NewSet.clear(); + addConnectedNodes(SU, NewSet, NodesAdded); + if (NewSet.size() > 0) + NodeSets.push_back(NewSet); + } + } +} + +// Add the node to the set, and add all is its connected nodes to the set. +void SwingSchedulerDAG::addConnectedNodes(SUnit *SU, NodeSet &NewSet, + SetVector &NodesAdded) { + + // Our blocks used to end in "ADD+CMP+Bcc". We had to make the Bcc + // dependent on the CMP or the dependencies were not correct. That caused + // the Bcc to be passed into this function which erroneously added it to + // the NodeSet. Now asserting instead of conditionally adding the Bcc. + assert(!SU->isBoundaryNode()); + // + + NewSet.insert(SU); + NodesAdded.insert(SU); + for (SUnit::const_succ_iterator SI = SU->Succs.begin(), SE = SU->Succs.end(); + SI != SE; ++SI) { + SUnit *Successor = SI->getSUnit(); + if (!SI->isArtificial() && NodesAdded.count(Successor) == 0) + addConnectedNodes(Successor, NewSet, NodesAdded); + } + for (SUnit::const_pred_iterator PI = SU->Preds.begin(), PE = SU->Preds.end(); + PI != PE; ++PI) { + SUnit *Predecessor = PI->getSUnit(); + if (!PI->isArtificial() && NodesAdded.count(Predecessor) == 0) + addConnectedNodes(Predecessor, NewSet, NodesAdded); + } +} + +/// Return true if Set1 contains elements in Set2. The elements in common +/// are returned in a different container. +static bool isIntersect(SmallSetVector &Set1, + const SwingSchedulerDAG::NodeSet &Set2, + SmallSetVector &Result) { + Result.clear(); + for (unsigned i = 0, e = Set1.size(); i != e; ++i) { + SUnit *SU = Set1[i]; + if (Set2.count(SU) != 0) + Result.insert(SU); + } + return !Result.empty(); +} + +/// Merge the recurrence node sets that have the same initial node. +void SwingSchedulerDAG::fuseRecs(NodeSetType &NodeSets) { + for (NodeSetType::iterator I = NodeSets.begin(), E = NodeSets.end(); I != E; + ++I) { + NodeSet &NI = *I; + for (NodeSetType::iterator J = I + 1; J != E;) { + NodeSet &NJ = *J; + if (NI.getNode(0)->NodeNum == NJ.getNode(0)->NodeNum) { + if (NJ.compareRecMII(NI) > 0) + NI.setRecMII(NJ.getRecMII()); + for (NodeSet::iterator NII = J->begin(), ENI = J->end(); NII != ENI; + ++NII) + I->insert(*NII); + NodeSets.erase(J); + E = NodeSets.end(); + } else { + ++J; + } + } + } +} + +// Merge all nodes +void SwingSchedulerDAG::mergeAllNodes(NodeSetType &NodeSets) { + NodeSets.clear(); + DEBUG(dbgs() << "Clear recurrence node-sets\n"); + groupRemainingNodes(NodeSets); + return; +} +// + +/// 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 (SUnit::succ_iterator SI = Inst1->Succs.begin(), SE = Inst1->Succs.end(); + SI != SE; ++SI) + 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, + SetVector& NodeOrder, OrderKind order) { //SYNOPSYS + + SmallSetVector R; + NodeOrder.clear(); + + for (auto &Nodes : NodeSets) { + DEBUG(dbgs() << "NodeSet size " << Nodes.size() << "\n"); + OrderKind Order; + SmallSetVector N; + // + if (order != AnyOrder) { + R.insert(Nodes.begin(), Nodes.end()); + Order = order; + DEBUG(dbgs() << " FORCED order "); + } else + // + + 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 (NodeSet::iterator NI = Nodes.begin(), ENI = Nodes.end(); NI != ENI; + ++NI) { + SUnit *SU = *NI; + 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 (SmallSetVector::iterator I = R.begin(), E = R.end(); + I != E; ++I) { + if (maxHeight == 0 || getHeight(*I) > getHeight(maxHeight)) + maxHeight = *I; + else if (getHeight(*I) == getHeight(maxHeight) && + getMOV(*I) < getMOV(maxHeight) && + !hasDataDependence(maxHeight, *I)) + maxHeight = *I; + else if (hasDataDependence(*I, maxHeight)) + maxHeight = *I; + } + NodeOrder.insert(maxHeight); + DEBUG(dbgs() << maxHeight->NodeNum << " "); + R.remove(maxHeight); + for (SUnit::const_succ_iterator I = maxHeight->Succs.begin(), + E = maxHeight->Succs.end(); + I != E; ++I) { + 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 (SUnit::const_pred_iterator I = maxHeight->Preds.begin(), + E = maxHeight->Preds.end(); + I != E; ++I) { + if (I->getKind() != SDep::Anti) + continue; + if (Nodes.count(I->getSUnit()) == 0) + continue; + if (NodeOrder.count(I->getSUnit()) != 0) + continue; + R.insert(I->getSUnit()); + } + } + Order = BottomUp; + DEBUG(dbgs() << "\n Switching order to bottom up "); + SmallSetVector N; + if (pred_L(NodeOrder, N, &Nodes)) + R.insert(N.begin(), N.end()); + } else { + // Choose the node with the maximum depth. If more than one, choose + // the node with the lowest MOV. If there is still more than one, check + // for a dependence between the instructions. + while (!R.empty()) { + SUnit *maxDepth = nullptr; + for (SmallSetVector::iterator I = R.begin(), E = R.end(); + I != E; ++I) { + if (maxDepth == 0 || getDepth(*I) > getDepth(maxDepth)) + maxDepth = *I; + else if (getDepth(*I) == getDepth(maxDepth) && + getMOV(*I) < getMOV(maxDepth) && + !hasDataDependence(*I, maxDepth)) + maxDepth = *I; + else if (hasDataDependence(maxDepth, *I)) + maxDepth = *I; + } + NodeOrder.insert(maxDepth); + DEBUG(dbgs() << maxDepth->NodeNum << " "); + R.remove(maxDepth); + if (Nodes.isExceedSU(maxDepth)) { + Order = TopDown; + R.clear(); + R.insert(Nodes.getNode(0)); + break; + } + for (SUnit::const_pred_iterator I = maxDepth->Preds.begin(), + E = maxDepth->Preds.end(); + I != E; ++I) { + 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 (SUnit::const_succ_iterator I = maxDepth->Succs.begin(), + E = maxDepth->Succs.end(); + I != E; ++I) { + if (I->getKind() != SDep::Anti) + continue; + if (Nodes.count(I->getSUnit()) == 0) + continue; + if (NodeOrder.count(I->getSUnit()) != 0) + continue; + R.insert(I->getSUnit()); + } + } + Order = TopDown; + DEBUG(dbgs() << "\n Switching order to top down "); + SmallSetVector N; + if (succ_L(NodeOrder, N, &Nodes)) + R.insert(N.begin(), N.end()); + } + } + DEBUG(dbgs() << "\nDone with Nodeset\n"); + } + + DEBUG({ + dbgs() << "Node order: "; + for (SetVector::iterator I = NodeOrder.begin(), + E = NodeOrder.end(); + I != E; ++I) { + dbgs() << " " << (*I)->NodeNum << " "; + } + dbgs() << "\n"; + }); +} + +// Process the nodes in the computed order and create the pipelined +// schedule of the instructions. +bool SwingSchedulerDAG::schedulePipeline(SMSchedule &Schedule, + SetVector NodeOrder) { //SYNOPSYS added NodeOrder + + if (NodeOrder.size() == 0) + return false; + + unsigned maxiter = ArcSwpMaxIter; //SYNOPSYS + bool scheduleFound = false; + //unsigned rMII = std::max(1u,(MII * 8) / 10); //SYNOPSYS scaled to 80% + // Keep increasing II until a valid schedule is found. + for (unsigned II = MII; II < MII + maxiter && !scheduleFound; ++II) { //SYNOPSYS was < MII + 10 + Schedule.reset(); + Schedule.setInitiationInterval(II); + + DEBUG(dbgs() << "Try to schedule with " << II << "\n"); + + unsigned CountSU = 0; //SYNOPSYS + + SetVector::iterator NI = NodeOrder.begin(); + SetVector::iterator NE = NodeOrder.end(); + do { + SUnit *SU = *NI; + + // Compute the schedule time for the instruction, which is based + // upon the scheduled time for any predecessors/successors. + int EarlyStart = INT_MIN; + int LateStart = INT_MAX; + // These values are set when the size of the schedule window is limited + // due to chain dependences. + int SchedEnd = INT_MAX; + int SchedStart = INT_MIN; + Schedule.computeStart(SU, &EarlyStart, &LateStart, &SchedEnd, &SchedStart, + II, this); + DEBUG({ + dbgs() << "Inst (" << SU->NodeNum << ") "; + SU->getInstr()->dump(); + dbgs() << "\n"; + }); + DEBUG({ + dbgs() << "\tes: " << EarlyStart << " ls: " << LateStart + << " me: " << SchedEnd << " ms: " << SchedStart << "\n"; + }); + + if (EarlyStart > LateStart || SchedEnd < EarlyStart || + SchedStart > LateStart) + scheduleFound = false; + else if (EarlyStart != INT_MIN && LateStart == INT_MAX) { + SchedEnd = std::min(SchedEnd, EarlyStart + (int)II - 1); + scheduleFound = Schedule.insert(SU, EarlyStart, SchedEnd, II); + } else if (EarlyStart == INT_MIN && LateStart != INT_MAX) { + SchedStart = std::max(SchedStart, LateStart - (int)II + 1); + scheduleFound = Schedule.insert(SU, LateStart, SchedStart, II); + } else if (EarlyStart != INT_MIN && LateStart != INT_MAX) { + SchedEnd = + std::min(SchedEnd, std::min(LateStart, EarlyStart + (int)II - 1)); + // When scheduling a Phi it is better to start at the late cycle and go + // backwards. The default order may insert the Phi too far away from + // its first dependence. + if (SU->getInstr()->isPHI()) + scheduleFound = Schedule.insert(SU, SchedEnd, EarlyStart, II); + else + scheduleFound = Schedule.insert(SU, EarlyStart, SchedEnd, II); + } else { + int FirstCycle = Schedule.getFirstCycle(); + +#if 0 + // + scheduleFound = false; + unsigned iter = II - MII; + if (SU->NumPreds > SU->NumSuccs) { + unsigned early = FirstCycle + getASAP(SU) + SU->NumPreds - SU->NumSuccs + iter; + unsigned late = FirstCycle + getASAP(SU) + II - 1; + if (early <= late) + scheduleFound = Schedule.insert(SU, early, late, II); + } + if (!scheduleFound) +#endif + + // + scheduleFound = Schedule.insert(SU, FirstCycle + getASAP(SU), + FirstCycle + getASAP(SU) + II - 1, II); + } + CountSU += scheduleFound; //SYNOPSYS + DEBUG({ + if (!scheduleFound) + dbgs() << "\tCan't schedule (Inserted=" << CountSU << ")\n"; //SYNOPSYS added Inserted=CountSU + }); + } while (++NI != NE && scheduleFound); + } + + DEBUG(dbgs() << "Schedule Found? " << scheduleFound << "\n"); + + if (scheduleFound && Schedule.getMaxStageCount() > 0) //SYNOPSYS + Loop->emitOptimizationRemark(DEBUG_TYPE, "Pipelined loop"); //SYNOPSYS + + if (scheduleFound) + Schedule.finalizeSchedule(this); + else + Schedule.reset(); + + if (scheduleFound) DEBUG(dbgs() << "maxStageCount=" << Schedule.getMaxStageCount() << " (scheule complete only when non-zero)\n"); //SYNOPSYS + + return scheduleFound && Schedule.getMaxStageCount() > 0; +} + +// Given a schedule for the loop, generate a new version of the loop, +// and replace the old version. This function generates a prolog +// that contains the initial iterations in the pipeline, and kernel +// loop, and the epilogue that contains the code for the final +// iterations. +void SwingSchedulerDAG::generatePipelinedLoop(SMSchedule &Schedule) { + // Create a new basic block for the kernel and add it to the CFG. + MachineBasicBlock *KernelBB = MF.CreateMachineBasicBlock(BB->getBasicBlock()); + + unsigned MaxStageCount = Schedule.getMaxStageCount(); + + // Remember the registers that are used in different stages. The index is + // the iteration, or stage, that the instruction is scheduled in. This is + // a map between register names in the orignal block and the names created + // in each stage of the pipelined loop. + ValueMapTy *VRMap = new ValueMapTy[(MaxStageCount + 1) * 2]; + InstrMapTy InstrMap; + SmallVector PrologBBs; + // Generate the prolog instructions that set up the pipeline. + generateProlog(Schedule, MaxStageCount, KernelBB, VRMap, PrologBBs); + + MF.insert(MachineFunction::iterator(BB), KernelBB); + + // Rearrange the instructions to generate the new, pipelined loop, + // and update register names as needed. + for (int Cycle = Schedule.getFirstCycle(), + LastCycle = Schedule.getFinalCycle(); + Cycle <= LastCycle; ++Cycle) { + std::deque &CycleInstrs = Schedule.getInstructions(Cycle); + // This inner loop schedules each instruction in the cycle. + for (std::deque::iterator CI = CycleInstrs.begin(), + ECI = CycleInstrs.end(); + CI != ECI; ++CI) { + if ((*CI)->getInstr()->isPHI()) + continue; + unsigned StageNum = Schedule.stageScheduled(getSUnit((*CI)->getInstr())); + MachineInstr *NewMI = + cloneInstr((*CI)->getInstr(), MaxStageCount, StageNum); + updateInstruction(NewMI, false, MaxStageCount, StageNum, Schedule, VRMap); + KernelBB->push_back(NewMI); + InstrMap[NewMI] = (*CI)->getInstr(); + } + } + + // Copy any terminator instructions to the new kernel, and update + // names as needed. + for (MachineBasicBlock::iterator I = BB->getFirstTerminator(), + E = BB->instr_end(); + I != E; ++I) { + MachineInstr *NewMI = MF.CloneMachineInstr(I); + updateInstruction(NewMI, false, MaxStageCount, 0, Schedule, VRMap); + KernelBB->push_back(NewMI); + InstrMap[NewMI] = I; + } + + KernelBB->transferSuccessors(BB); + KernelBB->replaceSuccessor(BB, KernelBB); + + generateExistingPhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, Schedule, + VRMap, InstrMap, MaxStageCount, MaxStageCount, false); + generatePhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, Schedule, VRMap, + InstrMap, MaxStageCount, MaxStageCount, false); + + DEBUG(dbgs() << "New block\n"; KernelBB->dump();); + + SmallVector EpilogBBs; + // Generate the epilog instructions to complete the pipeline. + generateEpilog(Schedule, MaxStageCount, KernelBB, VRMap, EpilogBBs, + PrologBBs); + + // We need this step because the register allocation doesn't handle some + // situations well, so we insert copies to help out. + splitLifetimes(KernelBB, EpilogBBs, Schedule); + + // Remove dead instructions due to loop induction variables. + removeDeadInstructions(KernelBB, EpilogBBs); + + // Add branches between prolog and epilog blocks. + addBranches(PrologBBs, KernelBB, EpilogBBs, Schedule, VRMap); + + TII->finalizeSWP(KernelBB);//SYNOPSYS + + // 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(MachineFunction::iterator(BB), NewBB); + NewBB->transferSuccessors(PredBB); + PredBB->addSuccessor(NewBB); + PredBB = NewBB; + + // Generate instructions for each appropriate stage. Process instructions + // in original program order. + for (int StageNum = i; StageNum >= 0; --StageNum) { + for (MachineBasicBlock::iterator BBI = BB->instr_begin(), + BBE = BB->getFirstTerminator(); + BBI != BBE; ++BBI) { + if (Schedule.isScheduledAtStage(getSUnit(BBI), (unsigned)StageNum)) { + if (BBI->isPHI()) + continue; + MachineInstr *NewMI = + cloneAndChangeInstr(BBI, i, (unsigned)StageNum, Schedule); + updateInstruction(NewMI, false, i, (unsigned)StageNum, Schedule, + VRMap); + NewBB->push_back(NewMI); + InstrMap[NewMI] = BBI; + } + } + } + rewritePhiValues(NewBB, i, Schedule, VRMap, InstrMap); + DEBUG({ + dbgs() << "prolog:\n"; + NewBB->dump(); + }); + } + + PredBB->replaceSuccessor(BB, KernelBB); + + // Check if we need to remove the branch from the preheader to the original + // loop, and replace it with a branch to the new loop. + unsigned numBranches = TII->RemoveBranch(*PreheaderBB); + if (numBranches) { + SmallVector Cond; + TII->InsertBranch(*PreheaderBB, PrologBBs[0], 0, Cond, DebugLoc()); + } +} + +// Generate the pipeline epilog code. The epilog code finishes the iterations +// that were started in either the prolog or the kernel. We create a basic +// block for each stage that needs to complete. +void SwingSchedulerDAG::generateEpilog(SMSchedule &Schedule, unsigned LastStage, + MachineBasicBlock *KernelBB, + ValueMapTy *VRMap, + MBBVectorTy &EpilogBBs, + MBBVectorTy &PrologBBs) { + // We need to change the branch from the kernel to the first epilog block, so + // this call to analyze branch uses the kernel rather than the original BB. + MachineBasicBlock *TBB = nullptr, *FBB = nullptr; + SmallVector Cond; + bool checkBranch = TII->AnalyzeBranch(*KernelBB, TBB, FBB, Cond); + assert(!checkBranch && "generateEpilog must be able to analyze the branch"); + if (checkBranch) + return; + + MachineBasicBlock::succ_iterator LoopExitI = KernelBB->succ_begin(); + if (*LoopExitI == KernelBB) + ++LoopExitI; + assert(LoopExitI != KernelBB->succ_end() && "Expecting a successor"); + MachineBasicBlock *LoopExitBB = *LoopExitI; + + MachineBasicBlock *PredBB = KernelBB; + MachineBasicBlock *EpilogStart = LoopExitBB; + InstrMapTy InstrMap; + + // Generate a basic block for each stage, not including the last stage, + // which was generated for the kernel. Each basic block may contain + // instructions from multiple stages/iterations. + int EpilogStage = LastStage + 1; + for (unsigned i = LastStage; i >= 1; --i, ++EpilogStage) { + MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(); + EpilogBBs.push_back(NewBB); + MF.insert(MachineFunction::iterator(BB), 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 (MachineBasicBlock::instr_iterator MI = LoopExitBB->instr_begin(), + ME = LoopExitBB->instr_end(); + MI != ME && MI->isPHI(); ++MI) + for (unsigned i = 2, e = MI->getNumOperands() + 1; i != e; i += 2) { + MachineOperand &MO = MI->getOperand(i); + if (MO.getMBB() == BB) + MO.setMBB(PredBB); + } + + // Create a branch to the new epilog from the kernel. + // Remove the original branch and add a new branch to the epilog. + TII->RemoveBranch(*KernelBB); + TII->InsertBranch(*KernelBB, KernelBB, EpilogStart, Cond, DebugLoc()); + // Add a branch to the loop exit. + if (EpilogBBs.size() > 0) { + MachineBasicBlock *LastEpilogBB = EpilogBBs.back(); + SmallVector Cond1; + TII->InsertBranch(*LastEpilogBB, LoopExitBB, 0, Cond1, DebugLoc()); + } +} + +/// Replace all uses of FromReg that appear outside the specified +/// basic block with ToReg. +static void replaceRegUsesAfterLoop(unsigned FromReg, unsigned ToReg, + MachineBasicBlock *MBB, + MachineRegisterInfo &MRI, + LiveIntervals *LIS) { + for (MachineRegisterInfo::use_iterator I = MRI.use_begin(FromReg), + E = MRI.use_end(); + I != E;) { + MachineOperand &O = *I; + ++I; + if (O.getParent()->getParent() != MBB) + O.setReg(ToReg); + } + if (!LIS->hasInterval(ToReg)) + LIS->createEmptyInterval(ToReg); +} + +/// Return true if the register has a use that occurs outside the +/// specified loop. +static bool hasUseAfterLoop(unsigned Reg, MachineBasicBlock *BB, + MachineRegisterInfo &MRI) { + for (MachineRegisterInfo::use_iterator I = MRI.use_begin(Reg), + E = MRI.use_end(); + I != E; ++I) + if (I->getParent()->getParent() != BB) + return true; + return false; +} + +/// Generate Phis for the specific block in the generated pipelined code. +/// This function looks at the Phis from the original code to guide the +/// creation of new Phis. +void SwingSchedulerDAG::generateExistingPhis( + MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2, + MachineBasicBlock *KernelBB, SMSchedule &Schedule, ValueMapTy *VRMap, + InstrMapTy &InstrMap, unsigned LastStageNum, unsigned CurStageNum, + bool IsLast) { + // Compute the stage number for the inital value of the Phi, which + // comes from the prolog. The prolog to use depends on to which kernel/ + // epilog that we're adding the Phi. + unsigned PrologStage = 0; + unsigned PrevStage = 0; + bool InKernel = (LastStageNum == CurStageNum); + if (InKernel) { + PrologStage = LastStageNum - 1; + PrevStage = CurStageNum; + } else { + PrologStage = LastStageNum - (CurStageNum - LastStageNum); + PrevStage = LastStageNum + (CurStageNum - LastStageNum) - 1; + } + + for (MachineBasicBlock::iterator BBI = BB->instr_begin(), + BBE = BB->getFirstNonPHI(); + BBI != BBE; ++BBI) { + unsigned Def = BBI->getOperand(0).getReg(); + + unsigned InitVal = 0; + unsigned LoopVal = 0; + getPhiRegs(BBI, BB, InitVal, LoopVal); + + unsigned PhiOp1 = 0; + // The Phi value from the loop body typically is defined in the loop, but + // not always. So, we need to check if the value is defined in the loop. + unsigned PhiOp2 = LoopVal; + if (VRMap[LastStageNum].count(LoopVal)) + PhiOp2 = VRMap[LastStageNum][LoopVal]; + + int StageScheduled = Schedule.stageScheduled(getSUnit(BBI)); + int LoopValStage = + Schedule.stageScheduled(getSUnit(MRI.getVRegDef(LoopVal))); + unsigned NumStages = Schedule.getStagesForReg(Def, CurStageNum); + if (NumStages == 0) { + // We don't need to generate a Phi anymore, but we need to rename any uses + // of the Phi value. + unsigned NewReg = VRMap[PrevStage][LoopVal]; + rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, 0, BBI, + Def, NewReg); + if (VRMap[CurStageNum].count(LoopVal)) + VRMap[CurStageNum][Def] = VRMap[CurStageNum][LoopVal]; + } + // The number of Phis can't exceed the number of prolog stages. We add 2 + // beacause prolog stage number is zero based, and there is a "stage"/Phi + // for the original Phi instruction. + unsigned NumPhis = NumStages; + if (StageScheduled <= (int)PrologStage && NumStages > PrologStage + 2) + NumPhis = PrologStage + 2; + else if (LoopValStage > (int)PrologStage && NumStages > PrologStage + 1) + NumPhis = PrologStage + 1; + unsigned NewReg = 0; + + unsigned AccessStage = (LoopValStage != -1) ? LoopValStage : StageScheduled; + // In the epilog, we may need to look back one stage to get the correct + // Phi name because the epilog and prolog blocks execute the same stage. + // The correct name is from the previous block only when the Phi has + // been completely scheduled prior to the epilog, and Phi value is not + // needed in multiple stages. + int StageDiff = 0; + if (!InKernel && StageScheduled >= LoopValStage && AccessStage == 0 && + NumPhis == 1) + StageDiff = 1; + // Adjust the computations below when the phi and the loop definition + // are scheduled in different stages. + if (InKernel && LoopValStage != -1 && StageScheduled > LoopValStage) + StageDiff = StageScheduled - LoopValStage; + for (unsigned np = 0; np < NumPhis; ++np) { + // If the Phi hasn't been scheduled, then use the initial Phi operand + // value. Otherwise, use the scheduled version of the instruction. This + // is a little complicated when a Phi references another Phi. + if (np > PrologStage || StageScheduled >= (int)LastStageNum) + PhiOp1 = InitVal; + // Check if the Phi has already been scheduled in a prolog stage. + else if (PrologStage >= AccessStage + StageDiff + np && + VRMap[PrologStage - StageDiff - np].count(LoopVal) != 0) + PhiOp1 = VRMap[PrologStage - StageDiff - np][LoopVal]; + // Check if the Phi has already been scheduled, but the loop intruction + // is either another Phi, or doesn't occur in the loop. + else if (PrologStage >= AccessStage + StageDiff + np) { + // If the Phi references another Phi, we need to examine the other + // Phi to get the correct value. + PhiOp1 = LoopVal; + MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1); + int Indirects = 1; + while (InstOp1 && InstOp1->isPHI() && InstOp1->getParent() == BB) { + int PhiStage = Schedule.stageScheduled(getSUnit(InstOp1)); + if ((int)(PrologStage - StageDiff - np) < PhiStage + Indirects) + PhiOp1 = getInitPhiReg(InstOp1, BB); + else + PhiOp1 = getLoopPhiReg(InstOp1, BB); + InstOp1 = MRI.getVRegDef(PhiOp1); + int PhiOpStage = Schedule.stageScheduled(getSUnit(InstOp1)); + if (PhiOpStage != -1 && PrologStage + PhiOpStage >= Indirects + np && + VRMap[PrologStage + PhiOpStage - Indirects - np].count(PhiOp1)) { + PhiOp1 = VRMap[PrologStage + PhiOpStage - Indirects - np][PhiOp1]; + break; + } + ++Indirects; + } + } else + PhiOp1 = InitVal; + // If this references a generated Phi in the kernel, get the Phi operand + // from the incoming block. + if (MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1)) + if (InstOp1->isPHI() && InstOp1->getParent() == KernelBB) + PhiOp1 = getInitPhiReg(InstOp1, KernelBB); + + MachineInstr *PhiInst = MRI.getVRegDef(LoopVal); + bool LoopDefIsPhi = PhiInst && PhiInst->isPHI(); + // In the epilog, a map lookup is needed to get the value from the kernel, + // or previous epilog block. How is does this depends on if the + // instruction is scheduled in the previous block. + if (!InKernel) { + int StageDiffAdj = 0; + if (LoopValStage != -1 && StageScheduled > LoopValStage) + StageDiffAdj = StageScheduled - LoopValStage; + // Use the loop value defined in the kernel, unless the kernel + // contains the last definition of the Phi. + if (np == 0 && PrevStage == LastStageNum && + (StageScheduled != 0 || LoopValStage != 0) && + VRMap[PrevStage - StageDiffAdj].count(LoopVal)) + PhiOp2 = VRMap[PrevStage - StageDiffAdj][LoopVal]; + // Use the value defined by the Phi. We add one because we switch + // from looking at the loop value to the Phi definition. + else if (np > 0 && PrevStage == LastStageNum && + VRMap[PrevStage - np + 1].count(Def)) + PhiOp2 = VRMap[PrevStage - np + 1][Def]; + // Use the loop value defined in the kernel. + else if ((unsigned)LoopValStage + StageDiffAdj > PrologStage + 1 && + VRMap[PrevStage - StageDiffAdj - np].count(LoopVal)) + PhiOp2 = VRMap[PrevStage - StageDiffAdj - np][LoopVal]; + // Use the value defined by the Phi, unless we're generating the first + // epilog and the Phi refers to a Phi in a different stage. + else if (VRMap[PrevStage - np].count(Def) && + (!LoopDefIsPhi || PrevStage != LastStageNum)) + PhiOp2 = VRMap[PrevStage - np][Def]; + } + + // Check if we can reuse an existing Phi. This occurs when a Phi + // references another Phi, and the other Phi is scheduled in an + // earlier stage. We can try to reuse an existing Phi up until the last + // stage of the current Phi. + if (LoopDefIsPhi && VRMap[CurStageNum].count(LoopVal) && + LoopValStage >= (int)(CurStageNum - LastStageNum)) { + int LVNumStages = Schedule.getStagesForPhi(LoopVal); + int StageDiff = (StageScheduled - LoopValStage); + LVNumStages -= StageDiff; + if (LVNumStages > (int)np) { + NewReg = PhiOp2; + unsigned ReuseStage = CurStageNum; + if (Schedule.isLoopCarried(this, PhiInst)) + ReuseStage -= LVNumStages; + // Check if the Phi to reuse has been generated yet. If not, then + // there is nothing to reuse. + if (VRMap[ReuseStage].count(LoopVal)) { + NewReg = VRMap[ReuseStage][LoopVal]; + + rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, np, + BBI, Def, NewReg); + // Update the map with the new Phi name. + VRMap[CurStageNum - np][Def] = NewReg; + PhiOp2 = NewReg; + if (VRMap[LastStageNum - np - 1].count(LoopVal)) + PhiOp2 = VRMap[LastStageNum - np - 1][LoopVal]; + + if (IsLast && np == NumPhis - 1) + replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS); + continue; + } + } else if (StageDiff > 0 && + VRMap[CurStageNum - StageDiff - np].count(LoopVal)) + PhiOp2 = VRMap[CurStageNum - StageDiff - np][LoopVal]; + } + + const TargetRegisterClass *RC = MRI.getRegClass(Def); + NewReg = MRI.createVirtualRegister(RC); + + MachineInstrBuilder NewPhi = + BuildMI(*NewBB, NewBB->getFirstNonPHI(), DebugLoc(), + TII->get(TargetOpcode::PHI), NewReg); + NewPhi.addReg(PhiOp1).addMBB(BB1); + NewPhi.addReg(PhiOp2).addMBB(BB2); + if (np == 0) + InstrMap[NewPhi] = BBI; + + // We define the Phis after creating the new pipelined code, so + // we need to rename the Phi values in scheduled instructions. + + unsigned PrevReg = 0; + if (InKernel && VRMap[PrevStage - np].count(LoopVal)) + PrevReg = VRMap[PrevStage - np][LoopVal]; + rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, np, BBI, + Def, NewReg, PrevReg); + // If the Phi has been scheduled, use the new name for rewriting. + if (VRMap[CurStageNum - np].count(Def)) { + unsigned R = VRMap[CurStageNum - np][Def]; + rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, np, BBI, + R, NewReg); + } + + // Check if we need to rename any uses that occurs after the loop. The + // register to replace depends on whether the Phi is scheduled in the + // epilog. + if (IsLast && np == NumPhis - 1) + replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS); + + // In the kernel, a dependent Phi uses the value from this Phi. + if (InKernel) + PhiOp2 = NewReg; + + // Update the map with the new Phi name. + VRMap[CurStageNum - np][Def] = NewReg; + } + + while (NumPhis++ < NumStages) { + rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, NumPhis, + BBI, Def, NewReg, 0); + } + + // Check if we need to rename a Phi that has been eliminated due to + // scheduling. + if (NumStages == 0 && IsLast && VRMap[CurStageNum].count(LoopVal)) + replaceRegUsesAfterLoop(Def, VRMap[CurStageNum][LoopVal], BB, MRI, LIS); + } +} + +/// Generate Phis for the specified block in the generated pipelined code. +/// These are new Phis needed because the definition is scheduled after the +/// use in the pipelened sequence. +void SwingSchedulerDAG::generatePhis( + MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2, + MachineBasicBlock *KernelBB, SMSchedule &Schedule, ValueMapTy *VRMap, + InstrMapTy &InstrMap, unsigned LastStageNum, unsigned CurStageNum, + bool IsLast) { + // Compute the stage number that contains the initial Phi value, and + // the Phi from the previous stage. + unsigned PrologStage = 0; + unsigned PrevStage = 0; + unsigned StageDiff = CurStageNum - LastStageNum; + bool InKernel = (StageDiff == 0); + if (InKernel) { + PrologStage = LastStageNum - 1; + PrevStage = CurStageNum; + } else { + PrologStage = LastStageNum - StageDiff; + PrevStage = LastStageNum + StageDiff - 1; + } + + for (MachineBasicBlock::iterator BBI = BB->getFirstNonPHI(), + BBE = BB->instr_end(); + BBI != BBE; ++BBI) { + for (unsigned i = 0, e = BBI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = BBI->getOperand(i); + if (!MO.isReg() || !MO.isDef() || + !TargetRegisterInfo::isVirtualRegister(MO.getReg())) + continue; + + int StageScheduled = Schedule.stageScheduled(getSUnit(BBI)); + assert(StageScheduled != -1 && "Expecting scheduled instruction."); + unsigned Def = MO.getReg(); + unsigned NumPhis = Schedule.getStagesForReg(Def, CurStageNum); + // An instruction scheduled in stage 0 and is used after the loop + // requires a phi in the epilog for the last definition from either + // the kernel or prolog. + if (!InKernel && NumPhis == 0 && StageScheduled == 0 && + hasUseAfterLoop(Def, BB, MRI)) + NumPhis = 1; + if (!InKernel && (unsigned)StageScheduled > PrologStage) + continue; + + unsigned PhiOp2 = VRMap[PrevStage][Def]; + if (MachineInstr *InstOp2 = MRI.getVRegDef(PhiOp2)) + if (InstOp2->isPHI() && InstOp2->getParent() == NewBB) + PhiOp2 = getLoopPhiReg(InstOp2, BB2); + // The number of Phis can't exceed the number of prolog stages. The + // prolog stage number is zero based. + if (NumPhis > PrologStage + 1 - StageScheduled) + NumPhis = PrologStage + 1 - StageScheduled; + for (unsigned np = 0; np < NumPhis; ++np) { + unsigned PhiOp1 = VRMap[PrologStage][Def]; + if (np <= PrologStage) + PhiOp1 = VRMap[PrologStage - np][Def]; + if (MachineInstr *InstOp1 = MRI.getVRegDef(PhiOp1)) { + if (InstOp1->isPHI() && InstOp1->getParent() == KernelBB) + PhiOp1 = getInitPhiReg(InstOp1, KernelBB); + if (InstOp1->isPHI() && InstOp1->getParent() == NewBB) + PhiOp1 = getInitPhiReg(InstOp1, NewBB); + } + if (!InKernel) + PhiOp2 = VRMap[PrevStage - np][Def]; + + const TargetRegisterClass *RC = MRI.getRegClass(Def); + unsigned NewReg = MRI.createVirtualRegister(RC); + + MachineInstrBuilder NewPhi = + BuildMI(*NewBB, NewBB->getFirstNonPHI(), DebugLoc(), + TII->get(TargetOpcode::PHI), NewReg); + NewPhi.addReg(PhiOp1).addMBB(BB1); + NewPhi.addReg(PhiOp2).addMBB(BB2); + if (np == 0) + InstrMap[NewPhi] = BBI; + + // Rewrite uses and update the map. The actions depend upon whether + // we generating code for the kernel or epilog blocks. + if (InKernel) { + rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, np, + BBI, PhiOp1, NewReg); + rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, np, + BBI, PhiOp2, NewReg); + + PhiOp2 = NewReg; + VRMap[PrevStage - np - 1][Def] = NewReg; + } else { + VRMap[CurStageNum - np][Def] = NewReg; + if (np == NumPhis - 1) + rewriteScheduledInstr(NewBB, Schedule, InstrMap, CurStageNum, np, + BBI, Def, NewReg); + } + if (IsLast && np == NumPhis - 1) + replaceRegUsesAfterLoop(Def, NewReg, BB, MRI, LIS); + } + } + } +} + +// Remove instructions that generate values with no uses. +// Typically, these are induction variable operations that generate values +// used in the loop itself. A dead instruction has a definition with +// no uses, or uses that occur in the original loop only. +void SwingSchedulerDAG::removeDeadInstructions(MachineBasicBlock *KernelBB, + MBBVectorTy &EpilogBBs) { + // For each epilog block, check that the value defined by each instruction + // is used. If not, delete it. + for (MBBVectorTy::reverse_iterator MBB = EpilogBBs.rbegin(), + MBE = EpilogBBs.rend(); + MBB != MBE; ++MBB) + for (MachineBasicBlock::reverse_instr_iterator MI = (*MBB)->instr_rbegin(), + ME = (*MBB)->instr_rend(); + MI != ME;) { + // From DeadMachineInstructionElem. Don't delete inline assembly. + if (MI->isInlineAsm()) { + ++MI; + continue; + } + bool SawStore = false; + // Check if it's safe to remove the instruction due to side effects. + // We can, and want to, remove Phis here. + if (!MI->isSafeToMove(nullptr, SawStore) && !MI->isPHI()) { + ++MI; + continue; + } + bool used = true; + for (MachineInstr::mop_iterator MOI = MI->operands_begin(), + MOE = MI->operands_end(); + MOI != MOE; ++MOI) { + if (!MOI->isReg() || !MOI->isDef()) + continue; + unsigned reg = MOI->getReg(); + unsigned realUses = 0; + for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(reg), + EI = MRI.use_end(); + UI != EI; ++UI) { + // Check if there are any uses that occur only in the original + // loop. If so, that's not a real use. + if (UI->getParent()->getParent() != BB) { + realUses++; + used = true; + break; + } + } + if (realUses > 0) + break; + used = false; + } + if (!used) { + MI->eraseFromParent(); + ME = (*MBB)->instr_rend(); + continue; + } + ++MI; + } + // In the kernel block, check if we can remove a Phi that generates a value + // used in an instruction removed in the epilog block. + for (MachineBasicBlock::iterator BBI = KernelBB->instr_begin(), + BBE = KernelBB->getFirstNonPHI(); + BBI != BBE;) { + MachineInstr *MI = &*BBI; + ++BBI; + unsigned reg = MI->getOperand(0).getReg(); + if (MRI.use_begin(reg) == MRI.use_end()) { + MI->eraseFromParent(); + } + } +} + +/// For loop carried definitions, we split the lifetime of a virtual register +/// that has uses past the definition in the next iteration. A copy with a new +/// virtual register is inserted before the definition, which helps with +/// generating a better register assignment. +/// +/// v1 = phi(a, v2) v1 = phi(a, v2) +/// v2 = phi(b, v3) v2 = phi(b, v3) +/// v3 = .. v4 = copy v1 +/// .. = V1 v3 = .. +/// .. = v4 +void SwingSchedulerDAG::splitLifetimes(MachineBasicBlock *KernelBB, + MBBVectorTy &EpilogBBs, + SMSchedule &Schedule) { + const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); + for (MachineBasicBlock::iterator BBI = KernelBB->instr_begin(), + BBF = KernelBB->getFirstNonPHI(); + BBI != BBF; ++BBI) { + unsigned Def = BBI->getOperand(0).getReg(); + // Check for any Phi definition that used as an operand of another Phi + // in the same block. + for (MachineRegisterInfo::use_instr_iterator I = MRI.use_instr_begin(Def), + E = MRI.use_instr_end(); + I != E; ++I) { + if (I->isPHI() && I->getParent() == KernelBB) { + // Get the loop carried definition. + unsigned LCDef = getLoopPhiReg(BBI, KernelBB); + if (!LCDef) + continue; + MachineInstr *MI = MRI.getVRegDef(LCDef); + if (!MI || MI->getParent() != KernelBB || MI->isPHI()) + continue; + // Search through the rest of the block looking for uses of the Phi + // definition. If one occurs, then split the lifetime. + unsigned SplitReg = 0; + for (auto &BBJ : make_range(MachineBasicBlock::instr_iterator(MI), + KernelBB->instr_end())) + if (BBJ.readsRegister(Def)) { + // We split the lifetime when we find the first use. + if (SplitReg == 0) { + SplitReg = MRI.createVirtualRegister(MRI.getRegClass(Def)); + BuildMI(*KernelBB, MI, MI->getDebugLoc(), + TII->get(TargetOpcode::COPY), SplitReg) + .addReg(Def); + } + BBJ.substituteRegister(Def, SplitReg, 0, *TRI); + } + if (!SplitReg) + continue; + // Search through each of the epilog blocks for any uses to be renamed. + for (auto &Epilog : EpilogBBs) + for (auto &I : *Epilog) + if (I.readsRegister(Def)) + I.substituteRegister(Def, SplitReg, 0, *TRI); + break; + } + } + } +} + +/// Remove the incoming block from the Phis in a basic block. +static void removePhis(MachineBasicBlock *BB, MachineBasicBlock *Incoming) { + for (MachineBasicBlock::instr_iterator MII = BB->instr_begin(), + MIE = BB->instr_end(); + MII != MIE && MII->isPHI(); ++MII) + for (unsigned i = 1, e = MII->getNumOperands(); i != e; i += 2) + if (MII->getOperand(i + 1).getMBB() == Incoming) { + MII->RemoveOperand(i + 1); + MII->RemoveOperand(i); + break; + } +} + +// Create branches from each prolog basic block to the appropriate epilog +// block. These edges are needed if the loop ends before reaching the +// kernel. +void SwingSchedulerDAG::addBranches(MBBVectorTy &PrologBBs, + MachineBasicBlock *KernelBB, + MBBVectorTy &EpilogBBs, + SMSchedule &Schedule, ValueMapTy *VRMap) { + assert(PrologBBs.size() == EpilogBBs.size() && "Prolog/Epilog mismatch"); + MachineInstr *IndVar = Pass->LI.LoopInductionVar; + MachineInstr *Cmp = Pass->LI.LoopCompare; + MachineBasicBlock *LastPro = KernelBB; + MachineBasicBlock *LastEpi = KernelBB; + + // Start from the blocks connected to the kernel and work "out" + // to the first prolog and the last epilog blocks. + SmallVector PrevInsts; + unsigned MaxIter = PrologBBs.size() - 1; + unsigned LC = UINT_MAX; + unsigned LCMin = UINT_MAX; + for (unsigned i = 0, j = MaxIter; i <= MaxIter; ++i, --j) { + // Add branches to the prolog that go to the corresponding + // epilog, and the fall-thru prolog/kernel block. + MachineBasicBlock *Prolog = PrologBBs[j]; + MachineBasicBlock *Epilog = EpilogBBs[i]; + // We've executed one iteration, so decrement the loop count and check for + // the loop end. + SmallVector Cond; + // Check if the LOOP0 has already been removed. If so, then there is no need + // to reduce the trip count. + if (LC != 0) + LC = TII->ReduceLoopCount(*Prolog, IndVar, Cmp, Cond, PrevInsts, j, + MaxIter); + + // Record the value of the first trip count, which is used to determine if + // branches and blocks can be removed for constant trip counts. + if (LCMin == UINT_MAX) + LCMin = LC; + + unsigned numAdded = 0; + if (TargetRegisterInfo::isVirtualRegister(LC)) { + Prolog->addSuccessor(Epilog); + numAdded = TII->InsertBranch(*Prolog, Epilog, LastPro, Cond, DebugLoc()); + } else if (j >= LCMin) { + Prolog->addSuccessor(Epilog); + Prolog->removeSuccessor(LastPro); + LastEpi->removeSuccessor(Epilog); + numAdded = TII->InsertBranch(*Prolog, Epilog, 0, Cond, DebugLoc()); + removePhis(Epilog, LastEpi); + // Remove the blocks that are no longer referenced. + if (LastPro != LastEpi) { + LastEpi->clear(); + LastEpi->eraseFromParent(); + } + LastPro->clear(); + LastPro->eraseFromParent(); + } else { + numAdded = TII->InsertBranch(*Prolog, LastPro, 0, Cond, DebugLoc()); + removePhis(Epilog, Prolog); + } + LastPro = Prolog; + LastEpi = Epilog; + for (MachineBasicBlock::reverse_instr_iterator I = Prolog->instr_rbegin(), + E = Prolog->instr_rend(); + I != E && numAdded > 0; ++I, --numAdded) + updateInstruction(&*I, false, j, 0, Schedule, VRMap); + } +} + +/// Return true if we can compute the amount the instruction changes +/// during each iteration. Set Delta to the amount of the change. +bool SwingSchedulerDAG::computeDelta(MachineInstr *MI, unsigned &Delta) { + const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); + unsigned BaseReg, Offset; + if (!TII->getMemOpBaseRegImmOfs(MI, BaseReg, Offset, TRI)) + return false; + + MachineRegisterInfo &MRI = MF.getRegInfo(); + // Check if there is a Phi. If so, get the definition in the loop. + MachineInstr *BaseDef = MRI.getVRegDef(BaseReg); + if (BaseDef && BaseDef->isPHI()) { + BaseReg = getLoopPhiReg(BaseDef, MI->getParent()); + BaseDef = MRI.getVRegDef(BaseReg); + } + if (!BaseDef) + return false; + + int D; + if (!TII->getIncrementValue(BaseDef, D) || D < 0) + return false; + + Delta = D; + return true; +} + +/// Update the memory operand with a new offset when the pipeliner +/// generate a new copy of the instruction that refers to a +/// different memory location. +void SwingSchedulerDAG::updateMemOperands(MachineInstr *NewMI, + MachineInstr *OldMI, unsigned Num) { + if (Num == 0) + return; + // If the instruction has memory operands, then adjust the offset + // when the instruction appears in different stages. + unsigned NumRefs = NewMI->memoperands_end() - NewMI->memoperands_begin(); + if (NumRefs == 0) + return; + MachineInstr::mmo_iterator NewMemRefs = MF.allocateMemRefsArray(NumRefs); + unsigned Refs = 0; + for (MachineInstr::mmo_iterator I = NewMI->memoperands_begin(), + E = NewMI->memoperands_end(); + I != E; ++I) { + if ((*I)->isVolatile() || (*I)->isInvariant() || (!(*I)->getValue())) { + NewMemRefs[Refs++] = *I; + continue; + } + unsigned Delta; + if (computeDelta(OldMI, Delta)) { + int64_t AdjOffset = Delta * Num; + NewMemRefs[Refs++] = + MF.getMachineMemOperand(*I, AdjOffset, (*I)->getSize()); + } else + NewMemRefs[Refs++] = MF.getMachineMemOperand(*I, 0, UINT64_MAX); + } + NewMI->setMemRefs(NewMemRefs, NewMemRefs + NumRefs); +} + +/// Clone the instruction for the new pipelined loop and update the +/// memory operands, if needed. +MachineInstr *SwingSchedulerDAG::cloneInstr(MachineInstr *OldMI, + unsigned CurStageNum, + unsigned InstStageNum) { + MachineInstr *NewMI = MF.CloneMachineInstr(OldMI); + updateMemOperands(NewMI, OldMI, CurStageNum - InstStageNum); + return NewMI; +} + +/// Clone the instruction for the new pipelined loop. If needed, this +/// function updates the instruction using the values saved in the +/// InstrChanges structure. +MachineInstr *SwingSchedulerDAG::cloneAndChangeInstr(MachineInstr *OldMI, + unsigned CurStageNum, + unsigned InstStageNum, + SMSchedule &Schedule) { + MachineInstr *NewMI = MF.CloneMachineInstr(OldMI); + DenseMap>::iterator It = + InstrChanges.find(getSUnit(OldMI)); + if (It != InstrChanges.end()) { + std::pair RegAndOffset = It->second; + unsigned BasePos, OffsetPos; + if (!TII->getBaseAndOffsetPosition(OldMI, BasePos, OffsetPos)) + return 0; + int64_t NewOffset = OldMI->getOperand(OffsetPos).getImm(); + MachineInstr *LoopDef = findDefInLoop(RegAndOffset.first); + if (Schedule.stageScheduled(getSUnit(LoopDef)) >= (signed)CurStageNum) + NewOffset += RegAndOffset.second * (CurStageNum - InstStageNum); + NewMI->getOperand(OffsetPos).setImm(NewOffset); + } + updateMemOperands(NewMI, OldMI, CurStageNum - InstStageNum); + return NewMI; +} + +// Update the machine instruction with new virtual registers. This +// function may change the defintions and/or uses. +void SwingSchedulerDAG::updateInstruction(MachineInstr *NewMI, bool LastDef, + unsigned CurStageNum, + unsigned InstrStageNum, + SMSchedule &Schedule, + ValueMapTy *VRMap) { + for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = NewMI->getOperand(i); + if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg())) + continue; + unsigned reg = MO.getReg(); + if (MO.isDef()) { + // Create a new virtual register for the definition. + const TargetRegisterClass *RC = MRI.getRegClass(reg); + unsigned NewReg = MRI.createVirtualRegister(RC); + MO.setReg(NewReg); + VRMap[CurStageNum][reg] = NewReg; + if (LastDef) + replaceRegUsesAfterLoop(reg, NewReg, BB, MRI, LIS); + } else if (MO.isUse()) { + MachineInstr *Def = MRI.getVRegDef(reg); + // Compute the stage that contains the last definition for instruction. + int DefStageNum = Schedule.stageScheduled(getSUnit(Def)); + unsigned StageNum = CurStageNum; + if (DefStageNum != -1 && (int)InstrStageNum > DefStageNum) { + // Compute the difference in stages between the defintion and the use. + unsigned StageDiff = (InstrStageNum - DefStageNum); + // Make an adjustment to get the last definition. + StageNum -= StageDiff; + } + if (VRMap[StageNum].count(reg)) + MO.setReg(VRMap[StageNum][reg]); + } + } +} + +// Return the instruction in the loop that defines the register. +// If the definition is a Phi, then follow the Phi operand to +// the instruction in the loop. +MachineInstr *SwingSchedulerDAG::findDefInLoop(unsigned Reg) { + SmallPtrSet Visited; + MachineInstr *Def = MRI.getVRegDef(Reg); + while (Def->isPHI()) { + if (!Visited.insert(Def).second) + break; + for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2) + if (Def->getOperand(i + 1).getMBB() == BB) { + Def = MRI.getVRegDef(Def->getOperand(i).getReg()); + break; + } + } + return Def; +} + +/// Return the new name for the value from the previous stage. +unsigned SwingSchedulerDAG::getPrevMapVal(unsigned StageNum, unsigned PhiStage, + unsigned LoopVal, ValueMapTy *VRMap, + MachineBasicBlock *BB) { + unsigned PrevVal = 0; + if (StageNum > PhiStage) { + MachineInstr *LoopInst = MRI.getVRegDef(LoopVal); + if (VRMap[StageNum - 1].count(LoopVal)) + // The name is defined in the previous stage. + PrevVal = VRMap[StageNum - 1][LoopVal]; + else if (VRMap[StageNum].count(LoopVal)) + // The previous name is defined in the current stage when the instruction + // order is swapped. + PrevVal = VRMap[StageNum][LoopVal]; + else if (!LoopInst->isPHI()) + // The loop value hasn't yet been scheduled. + PrevVal = LoopVal; + else if (StageNum == PhiStage + 1) + // The loop value is another phi, which has not been scheduled. + PrevVal = getInitPhiReg(LoopInst, BB); + else if (StageNum > PhiStage + 1 && LoopInst->getParent() == BB) + // The loop value is another phi, which has been scheduled. + PrevVal = getPrevMapVal(StageNum - 1, PhiStage, + getLoopPhiReg(LoopInst, BB), VRMap, BB); + } + return PrevVal; +} + +/// Rewrite the Phi values in the specified block to use the mappings +/// from the initial operand. Once the Phi is scheduled, we switch +/// to using the loop value instead of the Phi value, so those names +/// do not need to be rewritten. +void SwingSchedulerDAG::rewritePhiValues(MachineBasicBlock *NewBB, + unsigned StageNum, + SMSchedule &Schedule, + ValueMapTy *VRMap, + InstrMapTy &InstrMap) { + for (MachineBasicBlock::iterator BBI = BB->instr_begin(), + BBE = BB->getFirstNonPHI(); + BBI != BBE; ++BBI) { + unsigned InitVal = 0; + unsigned LoopVal = 0; + getPhiRegs(BBI, BB, InitVal, LoopVal); + unsigned PhiDef = BBI->getOperand(0).getReg(); + + unsigned PhiStage = + (unsigned)Schedule.stageScheduled(getSUnit(MRI.getVRegDef(PhiDef))); + unsigned NumPhis = Schedule.getStagesForReg(PhiDef, StageNum); + if (NumPhis > StageNum + 1) + NumPhis = StageNum + 1; + // Always do at least one iteration. In this case, the loop value is + // scheduled prior to the Phi in the next iteration. + if (NumPhis == 0) + NumPhis = 1; + for (unsigned np = 0; np < NumPhis; ++np) { + unsigned PrevVal = + getPrevMapVal(StageNum - np, PhiStage, LoopVal, VRMap, BB); + rewriteScheduledInstr(NewBB, Schedule, InstrMap, StageNum, np, BBI, + PhiDef, InitVal, PrevVal); + } + } +} + +/// Rewrite a previously scheduled instruction to use the register value +/// from the new instruction. Make sure the instruction occurs in the +/// basic block, and we don't change the uses in the new instruction. +void SwingSchedulerDAG::rewriteScheduledInstr( + MachineBasicBlock *BB, SMSchedule &Schedule, InstrMapTy &InstrMap, + unsigned CurStageNum, unsigned PhiNum, MachineInstr *Phi, unsigned OldReg, + unsigned NewReg, unsigned PrevReg) { + bool InProlog = (CurStageNum < Schedule.getMaxStageCount()); + int StagePhi = Schedule.stageScheduled(getSUnit(Phi)) + PhiNum; + // Rewrite uses that have been scheduled already to use the new + // Phi register. + for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(OldReg), + EI = MRI.use_end(); + UI != EI;) { + MachineOperand &UseOp = *UI; + MachineInstr *UseMI = UseOp.getParent(); + ++UI; + if (UseMI->getParent() != BB) + continue; + if (UseMI->isPHI()) { + if (!Phi->isPHI() && UseMI->getOperand(0).getReg() == NewReg) + continue; + if (getLoopPhiReg(UseMI, BB) != OldReg) + continue; + } + InstrMapTy::iterator OrigInstr = InstrMap.find(UseMI); + assert(OrigInstr != InstrMap.end() && "Instruction not scheduled."); + SUnit *OrigMISU = getSUnit(OrigInstr->second); + int StageSched = Schedule.stageScheduled(OrigMISU); + int CycleSched = Schedule.cycleScheduled(OrigMISU); + unsigned ReplaceReg = 0; + // This is the stage for the scheduled instruction. + if (StagePhi == StageSched && Phi->isPHI()) { + int CyclePhi = Schedule.cycleScheduled(getSUnit(Phi)); + if (PrevReg && InProlog) + ReplaceReg = PrevReg; + else if (PrevReg && !Schedule.isLoopCarried(this, Phi) && + (CyclePhi <= CycleSched || OrigMISU->getInstr()->isPHI())) + ReplaceReg = PrevReg; + else + ReplaceReg = NewReg; + } + // The scheduled instruction occurs before the scheduled Phi, and the + // Phi is not loop carried. + if (StagePhi + 1 == StageSched && !Schedule.isLoopCarried(this, Phi)) + ReplaceReg = NewReg; + if (StagePhi > StageSched && Phi->isPHI()) + ReplaceReg = NewReg; + if (!InProlog && !Phi->isPHI() && StagePhi < StageSched) + ReplaceReg = NewReg; + if (ReplaceReg) { + MRI.constrainRegClass(ReplaceReg, MRI.getRegClass(OldReg)); + UseOp.setReg(ReplaceReg); + } + } +} + +/// Check if we can change the instruction to use an offset value from the +/// previous iteration. If so, return true and set the base and offset values +/// so that we can rewrite the load, if necessary. +/// v1 = Phi(v0, v3) +/// v2 = load v1, 0 +/// v3 = post_store v1, 4, x +/// This function enables the load to be rewritten as v2 = load v3, 4. +bool SwingSchedulerDAG::canUseLastOffsetValue(MachineInstr *MI, + unsigned &BasePos, + unsigned &OffsetPos, + unsigned &NewBase, + int64_t &Offset) { + // Get the load instruction. + if (TII->isPostIncrement(MI)) + return false; + unsigned BasePosLd, OffsetPosLd; + if (!TII->getBaseAndOffsetPosition(MI, BasePosLd, OffsetPosLd)) + return false; + unsigned BaseReg = MI->getOperand(BasePosLd).getReg(); + + // Look for the Phi instruction. + MachineRegisterInfo &MRI = MI->getParent()->getParent()->getRegInfo(); + MachineInstr *Phi = MRI.getVRegDef(BaseReg); + if (!Phi || !Phi->isPHI()) + return false; + // Get the register defined in the loop block. + unsigned PrevReg = getLoopPhiReg(Phi, MI->getParent()); + if (!PrevReg) + return false; + + // Check for the post-increment load/store instruction. + MachineInstr *PrevDef = MRI.getVRegDef(PrevReg); + if (!PrevDef || PrevDef == MI) + return false; + + if (!TII->isPostIncrement(PrevDef)) + return false; + + unsigned BasePos1 = 0, OffsetPos1 = 0; + if (!TII->getBaseAndOffsetPosition(PrevDef, BasePos1, OffsetPos1)) + return false; + + // Make sure offset values are both positive or both negative. + int64_t LoadOffset = MI->getOperand(OffsetPosLd).getImm(); + int64_t StoreOffset = PrevDef->getOperand(OffsetPos1).getImm(); + if ((LoadOffset >= 0) != (StoreOffset >= 0)) + return false; + + // Set the return value once we determine that we return true. + BasePos = BasePosLd; + OffsetPos = OffsetPosLd; + NewBase = PrevReg; + Offset = StoreOffset; + return true; +} + +/// Apply changes to the instruction if needed. The changes are need +/// to improve the scheduling and depend up on the final schedule. +MachineInstr *SwingSchedulerDAG::applyInstrChange(MachineInstr *MI, + SMSchedule &Schedule, + bool UpdateDAG) { + SUnit *SU = getSUnit(MI); + DenseMap>::iterator It = + InstrChanges.find(SU); + if (It != InstrChanges.end()) { + std::pair RegAndOffset = It->second; + unsigned BasePos, OffsetPos; + if (!TII->getBaseAndOffsetPosition(MI, BasePos, OffsetPos)) + return 0; + 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 0; +} + +/// 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, OffsetS, BaseRegD, OffsetD; + const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); + if (!TII->getMemOpBaseRegImmOfs(SI, BaseRegS, OffsetS, TRI) || + !TII->getMemOpBaseRegImmOfs(DI, BaseRegD, OffsetD, TRI)) + return true; + + if (BaseRegS != BaseRegD) + return true; + + uint64_t AccessSizeS = (*SI->memoperands_begin())->getSize(); + uint64_t AccessSizeD = (*DI->memoperands_begin())->getSize(); + + // This is the main test, which checks the offset values and the loop + // increment value to determine if the accesses may be loop carried. + if (OffsetS >= OffsetD) + return OffsetS + AccessSizeS > DeltaS; + else if (OffsetS < OffsetD) + return OffsetD + AccessSizeD > DeltaD; + + return true; +} + +// Try to schedule the node at the specified StartCycle and continue +// until the node is schedule or the EndCycle is reached. This function +// returns true if the node is scheduled. This routine may search either +// forward or backward for a place to insert the instruction based upon +// the relative values of StartCycle and EndCycle. +// +bool SMSchedule::insert(SUnit *SU, int StartCycle, int EndCycle, int II) { + bool forward = true; + if (StartCycle > EndCycle) + forward = false; + + // The terminating condition depends on the direction. + int termCycle = forward ? EndCycle + 1 : EndCycle - 1; + for (int curCycle = StartCycle; curCycle != termCycle; + forward ? ++curCycle : --curCycle) { + + +#if 0 //SYNOPSYS The following VLIWPacketizer implementation is wrong for ARC + + // Add the already scheduled instructions at the specified cycle to the DFA. + Resources->clearResources(); + for (int checkCycle = FirstCycle + ((curCycle - FirstCycle) % II); + checkCycle <= LastCycle; checkCycle += II) { + std::deque &cycleInstrs = ScheduledInstrs[checkCycle]; + + for (std::deque::iterator I = cycleInstrs.begin(), + E = cycleInstrs.end(); + I != E; ++I) { + if (ST.getInstrInfo()->isZeroCost((*I)->getInstr()->getOpcode())) + continue; + assert(Resources->canReserveResources((*I)->getInstr()) && + "These instructions have already been scheduled."); + Resources->reserveResources((*I)->getInstr()); + } + } +#endif //SYNOPSYS + + bool ZC = ST.getInstrInfo()->isZeroCost(SU->getInstr()->getOpcode()); + if (ZC || Resources.canReserveAtCycle(SU->getInstr(), curCycle) %II) { //SYNOPSYS + + //SYNOPSYS commented out + //if (ST.getInstrInfo()->isZeroCost(SU->getInstr()->getOpcode()) || + // Resources->canReserveResources(SU->getInstr())) { + + if (!ZC) Resources.reserveAtCycle(SU->getInstr(), curCycle % II); //SYNOPSYS + + DEBUG({ + dbgs() << "\tinsert at cycle " << curCycle << " "; + SU->getInstr()->dump(); + }); + + ScheduledInstrs[curCycle].push_back(SU); + InstrToCycle.insert(std::make_pair(SU, curCycle)); + if (curCycle > LastCycle) + LastCycle = curCycle; + if (curCycle < FirstCycle) + FirstCycle = curCycle; + return true; + } + DEBUG({ + dbgs() << "\tfailed to insert at cycle " << curCycle << " "; + SU->getInstr()->dump(); + }); + } + return false; +} + +// Return the cycle of the earliest scheduled instruction in the chain. +int SMSchedule::earliestCycleInChain(const SDep &Dep) { + SmallPtrSet Visited; + SmallVector Worklist; + Worklist.push_back(Dep); + int EarlyCycle = INT_MAX; + while (!Worklist.empty()) { + const SDep &Cur = Worklist.pop_back_val(); + SUnit *PrevSU = Cur.getSUnit(); + if (Visited.count(PrevSU)) + continue; + std::map::const_iterator it = InstrToCycle.find(PrevSU); + if (it == InstrToCycle.end()) + continue; + EarlyCycle = std::min(EarlyCycle, it->second); + for (const auto &PI : PrevSU->Preds) + if (SwingSchedulerDAG::isOrder(PrevSU, PI)) + Worklist.push_back(PI); + Visited.insert(PrevSU); + } + return EarlyCycle; +} + +// Return the cycle of the latest scheduled instruction in the chain. +int SMSchedule::latestCycleInChain(const SDep &Dep) { + SmallPtrSet Visited; + SmallVector Worklist; + Worklist.push_back(Dep); + int LateCycle = INT_MIN; + while (!Worklist.empty()) { + const SDep &Cur = Worklist.pop_back_val(); + SUnit *SuccSU = Cur.getSUnit(); + if (Visited.count(SuccSU)) + continue; + std::map::const_iterator it = InstrToCycle.find(SuccSU); + if (it == InstrToCycle.end()) + continue; + LateCycle = std::max(LateCycle, it->second); + for (const auto &SI : SuccSU->Succs) + if (SwingSchedulerDAG::isOrder(SuccSU, SI)) + Worklist.push_back(SI); + Visited.insert(SuccSU); + } + return LateCycle; +} + +/// If an instruction has a use that spans multiple iterations, then +/// return true. These instructions are characterized by having a back-ege +/// to a Phi, which contains a reference to another Phi. +static SUnit *multipleIterations(SUnit *SU, SwingSchedulerDAG *DAG) { + for (auto &P : SU->Preds) + if (DAG->isBackedge(SU, P) && P.getSUnit()->getInstr()->isPHI()) + for (auto &S : P.getSUnit()->Succs) + if (S.getKind() == SDep::Order && S.getSUnit()->getInstr()->isPHI()) + return P.getSUnit(); + return nullptr; +} + +// Compute the scheduling start slot for the instruction. The start slot +// depends on any predecessor or successor nodes scheduled already. +void SMSchedule::computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart, + int *MinEnd, int *MaxStart, int II, + SwingSchedulerDAG *DAG) { + // Iterate over each instruction that has been scheduled already. The start + // slot computuation depends on whether the previously scheduled instruction + // is a predecessor or successor of the specified instruction. + for (int cycle = getFirstCycle(); cycle <= LastCycle; ++cycle) { + + // Iterate over each instruction in the current cycle. + for (std::deque::iterator I = getInstructions(cycle).begin(), + E = getInstructions(cycle).end(); + I != E; ++I) { + + // Because we're processing a DAG for the dependences, we recognize + // the back-edge in recurrences by anti dependences. + for (unsigned i = 0, e = (unsigned)SU->Preds.size(); i != e; ++i) { + const SDep &Dep = SU->Preds[i]; + if (Dep.getSUnit() == *I) { + if (!DAG->isBackedge(SU, Dep)) { + int EarlyStart = cycle + DAG->getLatency(SU, Dep) - + DAG->getDistance(Dep.getSUnit(), SU, Dep) * II; + *MaxEarlyStart = std::max(*MaxEarlyStart, EarlyStart); + if (DAG->isLoopCarriedOrder(SU, Dep, false)) { + int End = earliestCycleInChain(Dep) + (II - 1); + *MinEnd = std::min(*MinEnd, End); + } + } else { + int LateStart = cycle - DAG->getLatency(SU, Dep) + + DAG->getDistance(SU, Dep.getSUnit(), Dep) * II; + *MinLateStart = std::min(*MinLateStart, LateStart); + } + } + // For instruction that requires multiple iterations, make sure that + // the dependent instruction is not scheduled past the definition. + SUnit *BE = multipleIterations(*I, DAG); + if (BE && Dep.getSUnit() == BE && !SU->getInstr()->isPHI() && + !SU->isPred(*I)) + *MinLateStart = std::min(*MinLateStart, cycle); + } + for (unsigned i = 0, e = (unsigned)SU->Succs.size(); i != e; ++i) + if (SU->Succs[i].getSUnit() == *I) { + const SDep &Dep = SU->Succs[i]; + if (!DAG->isBackedge(SU, Dep)) { + int LateStart = cycle - DAG->getLatency(SU, Dep) + + DAG->getDistance(SU, Dep.getSUnit(), Dep) * II; + *MinLateStart = std::min(*MinLateStart, LateStart); + if (DAG->isLoopCarriedOrder(SU, Dep)) { + int Start = latestCycleInChain(Dep) + 1 - II; + *MaxStart = std::max(*MaxStart, Start); + } + } else { + int EarlyStart = cycle + DAG->getLatency(SU, Dep) - + DAG->getDistance(Dep.getSUnit(), SU, Dep) * II; + *MaxEarlyStart = std::max(*MaxEarlyStart, EarlyStart); + } + } + } + } +} + +/// Order the instructions within a cycle so that the definitions occur +/// before the uses. Returns true if the instruction is added to the start +/// of the list, or false if added to the end. +bool SMSchedule::orderDependence(SwingSchedulerDAG *SSD, SUnit *SU, + std::deque &Insts) { + MachineInstr *MI = SU->getInstr(); + bool OrderBeforeUse = false; + bool OrderAfterDef = false; + bool OrderBeforeDef = false; + unsigned MoveDef = 0; + unsigned MoveUse = 0; + int StageInst1 = stageScheduled(SU); + + unsigned Pos = 0; + for (std::deque::iterator I = Insts.begin(), E = Insts.end(); I != E; + ++I, ++Pos) { + // Relative order of Phis does not matter. + if (MI->isPHI() && (*I)->getInstr()->isPHI()) + continue; + for (unsigned i = 0, e = MI->getNumOperands(); i < e; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg())) + continue; + unsigned Reg = MO.getReg(); + unsigned BasePos, OffsetPos; + if (ST.getInstrInfo()->getBaseAndOffsetPosition(MI, BasePos, OffsetPos)) + if (MI->getOperand(BasePos).getReg() == Reg) + if (unsigned NewReg = SSD->getInstrBaseReg(SU)) + Reg = NewReg; + bool Reads, Writes; + std::tie(Reads, Writes) = + (*I)->getInstr()->readsWritesVirtualRegister(Reg); + if (MO.isDef() && Reads && stageScheduled(*I) <= StageInst1) { + OrderBeforeUse = true; + MoveUse = Pos; + } else if (MO.isUse() && Writes && stageScheduled(*I) == StageInst1) { + if (cycleScheduled(*I) == cycleScheduled(SU) && !(*I)->isSucc(SU)) { + OrderBeforeUse = true; + MoveUse = Pos; + } else { + OrderAfterDef = true; + MoveDef = Pos; + } + } else if (MO.isUse() && Writes && stageScheduled(*I) > StageInst1) { + OrderBeforeUse = true; + MoveUse = Pos; + if (MoveUse != 0) { + OrderAfterDef = true; + MoveDef = Pos - 1; + } + } else if (MO.isUse() && stageScheduled(*I) == StageInst1 && + isLoopCarriedDefOfUse(SSD, (*I)->getInstr(), MO)) { + OrderBeforeDef = true; + MoveUse = Pos; + } + } + // Check for order dependences between instructions. Make sure the source + // is ordered before the destination. + for (auto &S : SU->Succs) + if (S.getKind() == SDep::Order && S.getSUnit() == *I) { + OrderBeforeUse = true; + MoveUse = Pos; + } + for (auto &P : SU->Preds) + if (P.getKind() == SDep::Order && P.getSUnit() == *I) { + OrderAfterDef = true; + MoveDef = Pos; + } + } + + // OrderAfterDef takes precedences over OrderBeforeDef. The latter is due + // to a loop-carried dependence. + if (OrderBeforeDef) + OrderBeforeUse = !OrderAfterDef; + + // The uncommon case when the instruction order needs to be updated because + // there is both a use and def. + if (OrderBeforeUse && OrderAfterDef) { + assert(MoveUse != MoveDef && "Need to move two instructions."); + SUnit *UseSU = Insts.at(MoveUse); + SUnit *DefSU = Insts.at(MoveDef); + if (MoveUse > MoveDef) { + Insts.erase(Insts.begin() + MoveUse); + Insts.erase(Insts.begin() + MoveDef); + } else { + Insts.erase(Insts.begin() + MoveDef); + Insts.erase(Insts.begin() + MoveUse); + } + if (orderDependence(SSD, UseSU, Insts)) { + Insts.push_front(SU); + orderDependence(SSD, DefSU, Insts); + return true; + } + Insts.pop_back(); + Insts.push_back(SU); + Insts.push_back(UseSU); + orderDependence(SSD, DefSU, Insts); + return false; + } + // Put the new instruction first if there is a use in the list. Otherwise, + // put it at the end of the list. + if (OrderBeforeUse) + Insts.push_front(SU); + else + Insts.push_back(SU); + return OrderBeforeUse; +} + +/// Return true if the scheduled Phi has a loop carried operand. +bool SMSchedule::isLoopCarried(SwingSchedulerDAG *SSD, MachineInstr *Phi) { + if (!Phi->isPHI()) + return false; + assert(Phi->isPHI() && "Expecing a Phi."); + SUnit *DefSU = SSD->getSUnit(Phi); + unsigned DefCycle = cycleScheduled(DefSU); + int DefStage = stageScheduled(DefSU); + + unsigned InitVal = 0; + unsigned LoopVal = 0; + getPhiRegs(Phi, Phi->getParent(), InitVal, LoopVal); + SUnit *UseSU = SSD->getSUnit(MRI.getVRegDef(LoopVal)); + if (!UseSU) + return true; + if (UseSU->getInstr()->isPHI()) + return true; + unsigned LoopCycle = cycleScheduled(UseSU); + int LoopStage = stageScheduled(UseSU); + return LoopCycle > DefCycle || + (LoopCycle <= DefCycle && LoopStage <= DefStage); +} + +/// Return true if the instruction is a definition that is loop carried +/// and defines the use on the next iteration. +/// v1 = phi(v2, v3) +/// (Def) v3 = op v1 +/// (MO) = v1 +/// If MO appears before Def, then then v1 and v3 may get assigned to the same +/// register. +bool SMSchedule::isLoopCarriedDefOfUse(SwingSchedulerDAG *SSD, + MachineInstr *Def, MachineOperand &MO) { + if (!MO.isReg()) + return false; + if (Def->isPHI()) + return false; + MachineInstr *Phi = MRI.getVRegDef(MO.getReg()); + if (!Phi || !Phi->isPHI() || Phi->getParent() != Def->getParent()) + return false; + if (!isLoopCarried(SSD, Phi)) + return false; + unsigned LoopReg = getLoopPhiReg(Phi, Phi->getParent()); + for (unsigned i = 0, e = Def->getNumOperands(); i != e; ++i) { + MachineOperand &DMO = Def->getOperand(i); + if (!DMO.isReg() || !DMO.isDef()) + continue; + if (DMO.getReg() == LoopReg) + return true; + } + return false; +} + +// After the schedule has been formed, call this function to combine +// the instructions from the different stages/cycles. That is, this +// function creates a schedule that represents a single iteration. +void SMSchedule::finalizeSchedule(SwingSchedulerDAG *SSD) { + // Move all instructions to the first stage from later stages. + for (int cycle = getFirstCycle(); cycle <= getFinalCycle(); ++cycle) { + for (int stage = 1, lastStage = getMaxStageCount(); stage <= lastStage; + ++stage) { + std::deque &cycleInstrs = + ScheduledInstrs[cycle + (stage * InitiationInterval)]; + for (std::deque::reverse_iterator I = cycleInstrs.rbegin(), + E = cycleInstrs.rend(); + I != E; ++I) + ScheduledInstrs[cycle].push_front(*I); + } + } + // Iterate over the definitions in each instruction, and compute the + // stage difference for each use. Keep the maximum value. + for (std::map::iterator I = InstrToCycle.begin(), + E = InstrToCycle.end(); + I != E; ++I) { + int DefStage = stageScheduled(I->first); + MachineInstr *MI = I->first->getInstr(); + for (unsigned i = 0, e = MI->getNumOperands(); i < e; ++i) { + MachineOperand &Op = MI->getOperand(i); + if (!Op.isReg() || !Op.isDef()) + continue; + + unsigned Reg = Op.getReg(); + unsigned MaxDiff = 0; + bool PhiIsSwapped = false; + for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(Reg), + EI = MRI.use_end(); + UI != EI; ++UI) { + MachineOperand &UseOp = *UI; + MachineInstr *UseMI = UseOp.getParent(); + SUnit *SUnitUse = SSD->getSUnit(UseMI); + int UseStage = stageScheduled(SUnitUse); + unsigned Diff = 0; + if (UseStage != -1 && UseStage >= DefStage) + Diff = UseStage - DefStage; + if (MI->isPHI()) { + if (isLoopCarried(SSD, MI)) + ++Diff; + else + PhiIsSwapped = true; + } + MaxDiff = std::max(Diff, MaxDiff); + } + RegToStageDiff[Reg] = std::make_pair(MaxDiff, PhiIsSwapped); + } + } + + // Erase all the elements in the later stages. Only one iteration should + // remain in the scheduled list, and it contains all the instructions. + for (int cycle = getFinalCycle() + 1; cycle <= LastCycle; ++cycle) + ScheduledInstrs.erase(cycle); + + // Change the registers in instruction as specified in the InstrChanges + // map. We need to use the new registers to create the correct order. + for (int i = 0, e = SSD->SUnits.size(); i != e; ++i) { + SUnit *SU = &SSD->SUnits[i]; + SSD->applyInstrChange(SU->getInstr(), *this, true); + } + + // Reorder the instructions in each cycle to fix and improve the + // generated code. + for (int Cycle = getFirstCycle(), E = getFinalCycle(); Cycle <= E; ++Cycle) { + std::deque &cycleInstrs = ScheduledInstrs[Cycle]; + std::deque newOrderZC; + // Put the zero-cost, pseudo instructions at the start of the cycle. + for (unsigned i = 0, e = cycleInstrs.size(); i < e; ++i) { + SUnit *SU = cycleInstrs[i]; + if (ST.getInstrInfo()->isZeroCost(SU->getInstr()->getOpcode())) + orderDependence(SSD, SU, newOrderZC); + } + std::deque newOrderI; + // Then, add the regular instructions back. + for (unsigned i = 0, e = cycleInstrs.size(); i < e; ++i) { + SUnit *SU = cycleInstrs[i]; + if (!ST.getInstrInfo()->isZeroCost(SU->getInstr()->getOpcode())) + orderDependence(SSD, SU, newOrderI); + } + // Replace the old order with the new order. + cycleInstrs.swap(newOrderZC); + cycleInstrs.insert(cycleInstrs.end(), newOrderI.begin(), newOrderI.end()); + } + + DEBUG(dump();); +} + +// Print the schedule information to the given output. +void SMSchedule::print(raw_ostream &os) const { + // Iterate over each cycle. + for (int cycle = getFirstCycle(); cycle <= getFinalCycle(); ++cycle) { + // Iterate over each instruction in the cycle. + const_sched_iterator cycleInstrs = ScheduledInstrs.find(cycle); + for (std::deque::const_iterator CI = cycleInstrs->second.begin(), + ECI = cycleInstrs->second.end(); + CI != ECI; ++CI) { + os << "cycle " << cycle << " (" << stageScheduled(*CI) << ") "; + os << "(" << (*CI)->NodeNum << ") "; + (*CI)->getInstr()->print(os); + os << "\n"; + } + } +} + +// Utility function used for debugging to print the schedule. +void SMSchedule::dump() const { print(dbgs()); } Index: lib/Parse/ParsePragma.cpp =================================================================== --- lib/Parse/ParsePragma.cpp +++ lib/Parse/ParsePragma.cpp @@ -822,6 +822,7 @@ if (OptionInfo) { // Pragma Unroll does not specify an option. OptionUnroll = OptionInfo->isStr("unroll"); StateOption = llvm::StringSwitch(OptionInfo->getName()) + .Case("pipeline", true) //SYNOPSYS .Case("vectorize", true) .Case("interleave", true) .Case("unroll", true) @@ -2017,6 +2018,7 @@ IdentifierInfo *OptionInfo = Tok.getIdentifierInfo(); bool OptionValid = llvm::StringSwitch(OptionInfo->getName()) + .Case("pipeline", true) //SYNOPSYS .Case("vectorize", true) .Case("interleave", true) .Case("unroll", true) Index: lib/Sema/SemaStmtAttr.cpp =================================================================== --- lib/Sema/SemaStmtAttr.cpp +++ lib/Sema/SemaStmtAttr.cpp @@ -91,6 +91,7 @@ "Attribute must have valid option info."); Option = llvm::StringSwitch( OptionLoc->Ident->getName()) + .Case("pipeline", LoopHintAttr::Pipeline) //SYNOPSYS .Case("vectorize", LoopHintAttr::Vectorize) .Case("vectorize_width", LoopHintAttr::VectorizeWidth) .Case("interleave", LoopHintAttr::Interleave) @@ -106,6 +107,7 @@ return nullptr; State = LoopHintAttr::Numeric; } else if (Option == LoopHintAttr::Vectorize || + Option == LoopHintAttr::Pipeline || //SYNOPSYS Option == LoopHintAttr::Interleave || Option == LoopHintAttr::Unroll) { assert(StateLoc && StateLoc->Ident && "Loop hint must have an argument"); @@ -141,7 +143,8 @@ struct { const LoopHintAttr *StateAttr; const LoopHintAttr *NumericAttr; - } HintAttrs[] = {{nullptr, nullptr}, {nullptr, nullptr}, {nullptr, nullptr}}; + } HintAttrs[] = {{nullptr, nullptr}, {nullptr, nullptr}, {nullptr, nullptr}, + {nullptr, nullptr}};//SYNOPSYS added 4th initializer for "Pipeline" for (const auto *I : Attrs) { const LoopHintAttr *LH = dyn_cast(I); @@ -151,8 +154,13 @@ continue; LoopHintAttr::OptionType Option = LH->getOption(); - enum { Vectorize, Interleave, Unroll } Category; + enum { Vectorize, Interleave, Unroll, Pipeline/*SYNOPSYS*/ } Category; switch (Option) { +// + case LoopHintAttr::Pipeline: + Category = Pipeline; + break; +// case LoopHintAttr::Vectorize: case LoopHintAttr::VectorizeWidth: Category = Vectorize; @@ -170,6 +178,7 @@ auto &CategoryState = HintAttrs[Category]; const LoopHintAttr *PrevAttr; if (Option == LoopHintAttr::Vectorize || + Option == LoopHintAttr::Pipeline || //SYNOPSYS Option == LoopHintAttr::Interleave || Option == LoopHintAttr::Unroll) { // Enable|Disable|AssumeSafety hint. For example, vectorize(enable). PrevAttr = CategoryState.StateAttr;