Modified MachinePipeliner http://reviews.llvm.org/D16829

[marksl]

Summary

I added support for:

#pragma clang loop pipeline(enable)
-Rpass options

We modified MachinePipeliner:

• To use a class similar to ScoreboardHazardRecognizer (we need to redo and use ScoreboardHazardRecognizer directly)
• To try other orders besides the original bidirectional top down / bottom up order

[marksl]

This version of MachinePipeliner.cpp contains several fixes. Please search for SYNOPSYS for my changes to Brendon's original source.

include/llvm/CodeGen/MachineLoopInfo.h

public:
 
   /// getBottomBlock - Return the "bottom" block in the loop, which is the last
   /// block in the linear layout, ignoring any parts of the loop not
   /// contiguous with the part the contains the header.
   MachineBasicBlock *getBottomBlock();
 
   void dump() const;
 
+  //<SYNOPSYS>
+  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);
+  //</SYNOPSYS>
+
 private:
   friend class LoopInfoBase<MachineBasicBlock, MachineLoop>;
   explicit MachineLoop(MachineBasicBlock *MBB)
     : LoopBase<MachineBasicBlock, MachineLoop>(MBB) {}
 };
 
 // Implementation in LoopInfoImpl.h
 extern template class LoopInfoBase<MachineBasicBlock, MachineLoop>;
public:
   }
 
   /// removeBlock - This method completely removes BB from all data structures,
   /// including all of the Loop objects it is nested in and our mapping from
   /// MachineBasicBlocks to loops.
   void removeBlock(MachineBasicBlock *BB) {
     LI.removeBlock(BB);
   }
+
 };
 
 
 // Allow clients to walk the list of nested loops...
 template <> struct GraphTraits<const MachineLoop*> {
   typedef const MachineLoop NodeType;
   typedef MachineLoopInfo::iterator ChildIteratorType;
 

lib/CodeGen/CGLoopInfo.cpp

 using namespace clang::CodeGen;
 using namespace llvm;
 
 static MDNode *createMetadata(LLVMContext &Ctx, const LoopAttributes &Attrs) {
 
   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;
 
   SmallVector<Metadata *, 4> Args;
   // Reserve operand 0 for loop id self reference.
   auto TempNode = MDNode::getTemporary(Ctx, None);
   Args.push_back(TempNode.get());
 
static MDNode *createMetadata(LLVMContext &Ctx, const LoopAttributes &Attrs) {
   if (Attrs.VectorizeEnable != LoopAttributes::Unspecified) {
     Metadata *Vals[] = {MDString::get(Ctx, "llvm.loop.vectorize.enable"),
                         ConstantAsMetadata::get(ConstantInt::get(
                             Type::getInt1Ty(Ctx), (Attrs.VectorizeEnable ==
                                                    LoopAttributes::Enable)))};
     Args.push_back(MDNode::get(Ctx, Vals));
   }
 
+  //<SYNOPSYS>
+  // 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));
+  }
+  // </SYNOPSYS>
+
   // Setting unroll.full or unroll.disable
   if (Attrs.UnrollEnable != LoopAttributes::Unspecified) {
     std::string Name;
     if (Attrs.UnrollEnable == LoopAttributes::Enable)
       Name = "llvm.loop.unroll.enable";
     else if (Attrs.UnrollEnable == LoopAttributes::Full)
       Name = "llvm.loop.unroll.full";
     else
case LoopHintAttr::Disable:
         break;
       case LoopHintAttr::Interleave:
         // Disable interleaving by speciyfing a count of 1.
         setInterleaveCount(1);
         break;
       case LoopHintAttr::Unroll:
         setUnrollState(LoopAttributes::Disable);
         break;
+        //<SYNOPSYS>
+      case LoopHintAttr::Pipeline://SYNOPSYS
+        setPipelineEnable(false);
+        break;
+      //</SYNPSYS>
       case LoopHintAttr::UnrollCount:
       case LoopHintAttr::VectorizeWidth:
       case LoopHintAttr::InterleaveCount:
         llvm_unreachable("Options cannot be disabled.");
         break;
       }
       break;
     case LoopHintAttr::Enable:
       switch (Option) {
       case LoopHintAttr::Vectorize:
       case LoopHintAttr::Interleave:
         setVectorizeEnable(true);
         break;
       case LoopHintAttr::Unroll:
         setUnrollState(LoopAttributes::Enable);
         break;
+        //<SYNOPSYS>
+      case LoopHintAttr::Pipeline://SYNOPSYS
+        setPipelineEnable(true);
+        break;
+      //</SYNPSYS>
       case LoopHintAttr::UnrollCount:
       case LoopHintAttr::VectorizeWidth:
       case LoopHintAttr::InterleaveCount:
         llvm_unreachable("Options cannot enabled.");
         break;
       }
       break;
     case LoopHintAttr::AssumeSafety:
       switch (Option) {
       case LoopHintAttr::Vectorize:
       case LoopHintAttr::Interleave:
         // Apply "llvm.mem.parallel_loop_access" metadata to load/stores.
         setParallel(true);
         setVectorizeEnable(true);
         break;
       case LoopHintAttr::Unroll:
       case LoopHintAttr::UnrollCount:
       case LoopHintAttr::VectorizeWidth:
       case LoopHintAttr::InterleaveCount:
+      case LoopHintAttr::Pipeline://SYNOPSYS
         llvm_unreachable("Options cannot be used to assume mem safety.");
         break;
       }
       break;
     case LoopHintAttr::Full:
       switch (Option) {
       case LoopHintAttr::Unroll:
         setUnrollState(LoopAttributes::Full);
         break;
+      case LoopHintAttr::Pipeline://SYNOPSYS
       case LoopHintAttr::Vectorize:
       case LoopHintAttr::Interleave:
       case LoopHintAttr::UnrollCount:
       case LoopHintAttr::VectorizeWidth:
       case LoopHintAttr::InterleaveCount:
         llvm_unreachable("Options cannot be used with 'full' hint.");
         break;
       }
       break;
     case LoopHintAttr::Numeric:
       switch (Option) {
       case LoopHintAttr::VectorizeWidth:
         setVectorizeWidth(ValueInt);
         break;
       case LoopHintAttr::InterleaveCount:
         setInterleaveCount(ValueInt);
         break;
       case LoopHintAttr::UnrollCount:
         setUnrollCount(ValueInt);
         break;
       case LoopHintAttr::Unroll:
+      case LoopHintAttr::Pipeline://SYNOPSYS
       case LoopHintAttr::Vectorize:
       case LoopHintAttr::Interleave:
         llvm_unreachable("Options cannot be assigned a value.");
         break;
       }
       break;
     }
   }

lib/CodeGen/MachineLoopInfo.cpp

 // same header node... not just a single natural loop.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #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;
 
 // Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops.
 template class llvm::LoopBase<MachineBasicBlock, MachineLoop>;
 template class llvm::LoopInfoBase<MachineBasicBlock, MachineLoop>;
 
MachineBasicBlock *MachineLoop::getBottomBlock() {
   return BotMBB;
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 void MachineLoop::dump() const {
   print(dbgs());
 }
 #endif
+
+//<SYNOPSYS>
+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);
+}
+//</SYNOPSYS>

lib/CodeGen/MachinePipeliner.cpp

+//===-- 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 <climits>
+#include <deque>
+#include <map>
+
+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<bool> 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<int> SwpMaxMii("swp-max-mii",
+                              cl::desc("Size limit for the the MII."),
+                              cl::Hidden, cl::init(64));        //SYNOPSYS was 27
+
+static cl::opt<int>
+    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<bool>
+    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<bool>
+    SwpPruneLoopCarried("swp-prune-loop-carried",
+                        cl::desc("Prune loop carried order dependences."),
+                        cl::Hidden, cl::init(true));
+
+#ifndef NDEBUG
+static cl::opt<int> SwpLoopLimit("swp-max", cl::Hidden, cl::init(-1));
+#endif
+
+static cl::opt<bool> SwpIgnoreRecMII("swp-ignore-recmii", cl::ReallyHidden,
+                                     cl::init(false), cl::ZeroOrMore,
+                                     cl::desc("Ignore RecMII"));
+
+static cl::opt<unsigned> ArcSwpMaxIter("arc-swp-max-iter", cl::Hidden, cl::init(20));
+
+static cl::opt<unsigned> 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<MachineOperand, 4> 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<AAResultsWrapperPass>();
+    AU.addPreserved<AAResultsWrapperPass>();
+    AU.addRequiredTransitive<LiveIntervals>();
+    AU.addRequiredTransitive<MachineLoopInfo>();
+    AU.addRequired<MachineDominatorTree>();
+    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<NodeInfo> 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<SUnit *> 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<SUnit *> Nodes;
+    bool HasRecurrence;
+    unsigned RecMII;
+    int MaxMOV;
+    int MaxDepth;
+    unsigned Colocate;
+    SUnit *ExceedPressure;
+
+  public:
+    typedef SetVector<SUnit *>::iterator iterator;
+    typedef SetVector<SUnit *>::const_iterator const_iterator;
+
+    NodeSet()
+        : Nodes(), HasRecurrence(false), RecMII(0), MaxMOV(0), MaxDepth(0),
+          Colocate(0), ExceedPressure(nullptr) {}
+
+    template <typename It>
+    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 <typename It> void insert(It B, It E) { Nodes.insert(B, E); }
+
+    template <typename UnaryPredicate> bool remove_if(UnaryPredicate P) {
+      return Nodes.remove_if(P);
+    }
+
+    unsigned count(SUnit *SU) const { return Nodes.count(SU); }
+
+    bool hasRecurrence() { return HasRecurrence; };
+
+    unsigned size() const { return Nodes.size(); }
+
+    bool empty() const { return Nodes.empty(); }
+
+    SUnit *getNode(unsigned i) const { return Nodes[i]; };
+
+    void setRecMII(unsigned mii) { RecMII = mii; };
+
+    void setColocate(unsigned c) { Colocate = c; };
+
+    void setExceedPressure(SUnit *SU) { ExceedPressure = SU; }
+
+    bool isExceedSU(SUnit *SU) { return ExceedPressure == SU; }
+
+    int compareRecMII(NodeSet &RHS) { return RecMII - RHS.RecMII; }
+
+    int getRecMII() { return RecMII; }
+
+    /// Summarize node functions for the entire node set.
+    void computeNodeSetInfo(SwingSchedulerDAG *SSD) {
+      for (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<SUnit *> &() { return Nodes; }
+
+    /// Sort the node sets by importance. First, rank them by recurrence MII,
+    /// then by mobility (least mobile done first), and finally by depth.
+    /// Each node set may contain a colocate value which is used as the first
+    /// tie breaker, if it's set.
+    bool operator>(const NodeSet &RHS) const {
+      if (RecMII == RHS.RecMII) {
+        if (Colocate != 0 && RHS.Colocate != 0 && Colocate != RHS.Colocate)
+          return Colocate < RHS.Colocate;
+        if (MaxMOV == RHS.MaxMOV)
+          return MaxDepth > RHS.MaxDepth;
+        return MaxMOV < RHS.MaxMOV;
+      }
+      return RecMII > RHS.RecMII;
+    }
+    bool operator==(const NodeSet &RHS) const {
+      return RecMII == RHS.RecMII && MaxMOV == RHS.MaxMOV &&
+             MaxDepth == RHS.MaxDepth;
+    }
+    bool operator!=(const NodeSet &RHS) const { return !operator==(RHS); }
+
+    iterator begin() { return Nodes.begin(); }
+    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<NodeSet, 8> NodeSetType;
+  typedef DenseMap<unsigned, unsigned> ValueMapTy;
+  typedef SmallVectorImpl<MachineBasicBlock *> MBBVectorTy;
+  typedef DenseMap<MachineInstr *, MachineInstr *> InstrMapTy;
+
+  /// Instructions to change when emitting the final schedule.
+  DenseMap<SUnit *, std::pair<unsigned, int64_t>> InstrChanges;
+
+  /// We may create a new instruction, so remember it because it
+  /// must be deleted when the pass is finished.
+  SmallPtrSet<MachineInstr *, 4> NewMIs;
+
+  const RegisterClassInfo &RegClassInfo;
+
+  /// Helper class to implement Johnson's circuit finding algorithm.
+  class Circuits {
+    std::vector<SUnit> &SUnits;
+    SmallVector<SUnit *, 10> Stack;
+    BitVector Blocked;
+    SmallVector<SmallPtrSet<SUnit *, 4>, 10> B;
+    SmallVector<SmallVector<int, 4>, 16> AdjK;
+    unsigned NumPaths;
+    static unsigned MaxPaths;
+
+  public:
+    Circuits(std::vector<SUnit> &SUs)
+        : SUnits(SUs), Stack(), Blocked(SUs.size()), B(SUs.size()),
+          AdjK(SUs.size()) {}
+    /// Reset the data structures used in the circuit algorithm.
+    void reset() {
+      Stack.clear();
+      Blocked.reset();
+      B.assign(SUnits.size(), SmallPtrSet<SUnit *, 4>());
+      NumPaths = 0;
+    }
+    /// 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<SUnit *, std::pair<unsigned, int64_t>>::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<SUnit *> &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<SUnit *>&, OrderKind); //SYNOPSYS
+
+  // Generate the pipelined schedule for the instructions, if possible.
+  // Return true if a schedule has been found.
+  bool schedulePipeline(SMSchedule &Schedule,
+                        SetVector<SUnit *> 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<int, std::deque<SUnit *>> ScheduledInstrs;
+
+  // Map from instruction to execution cycle.
+  std::map<SUnit *, int> InstrToCycle;
+
+  // Map for each register and the max difference between its uses and def.
+  // The first element in the pair is the max difference in stages. The
+  // second is true if the register defines a Phi value and loop value is
+  // scheduled before the Phi.
+  std::map<unsigned, std::pair<unsigned, bool>> RegToStageDiff;
+
+  // Keep track of the first cycle value in the schedule.  It starts
+  // as zero, but the algorithm allows negative values.
+  int FirstCycle;
+
+  // Keep track of the last cycle value in the schedule.
+  int LastCycle;
+
+  // The initiation interval (II) for the schedule.
+  int InitiationInterval;
+
+  // Target machine information.
+  const TargetSubtargetInfo &ST;
+
+  // Virtual register information.
+  MachineRegisterInfo &MRI;
+
+  //DFAPacketizer *Resources;           //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<int, std::deque<SUnit *>>::iterator sched_iterator;
+  typedef DenseMap<int, std::deque<SUnit *>>::const_iterator
+      const_sched_iterator;
+
+  // Return true if the instruction is scheduled at the specified stage.
+  bool isScheduledAtStage(SUnit *SU, unsigned StageNum) {
+    return (stageScheduled(SU) == (int)StageNum);
+  }
+
+  // Return the stage for a scheduled instruction.  Return -1 if
+  // the instruction has not been scheduled.
+  int stageScheduled(SUnit *SU) const {
+    std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU);
+    if (it == InstrToCycle.end())
+      return -1;
+    return (it->second - FirstCycle) / InitiationInterval;
+  }
+
+  /// Return the cycle for a scheduled instruction. This function normalizes
+  /// the first cycle to be 0.
+  unsigned cycleScheduled(SUnit *SU) const {
+    std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU);
+    assert(it != InstrToCycle.end() && "Instruction hasn't been scheduled.");
+    return (it->second - FirstCycle) % InitiationInterval;
+  }
+
+  // Return the maximum stage count needed for this schedule.
+  unsigned getMaxStageCount() {
+    return (LastCycle - FirstCycle) / InitiationInterval;
+  }
+
+  /// Return the max. number of stages/iterations that can occur between a
+  /// register definition and its uses.
+  unsigned getStagesForReg(int Reg, unsigned CurStage) {
+    std::pair<unsigned, bool> Stages = RegToStageDiff[Reg];
+    if (CurStage > getMaxStageCount() && Stages.first == 0 && Stages.second)
+      return 1;
+    return Stages.first;
+  }
+
+  /// The number of stages for a Phi is a little different than other
+  /// instructions. The minimum value computed in RegToStageDiff is 1
+  /// because we assume the Phi is needed for at least 1 iteration.
+  /// This is not the case if the loop value is scheduled prior to the
+  /// Phi in the same stage.  This function returns the number of stages
+  /// or iterations needed between the Phi definition and any uses.
+  unsigned getStagesForPhi(int Reg) {
+    std::pair<unsigned, bool> Stages = RegToStageDiff[Reg];
+    if (Stages.second)
+      return Stages.first;
+    return Stages.first - 1;
+  }
+
+  /// Return the instructions that are scheduled at the specified cycle.
+  std::deque<SUnit *> &getInstructions(int cycle) {
+    return ScheduledInstrs[cycle];
+  }
+
+  // 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<SUnit *> &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) {
+
+  //<SYNOPSYS>
+  if (DUMP_BEFORE()) mf.dump();
+  if (VIEW_BEFORE()) mf.viewCFG();
+  //</SYNOPSYS>
+
+  if (mf.getFunction()->getAttributes().hasAttribute(
+          AttributeSet::FunctionIndex, Attribute::OptimizeForSize) &&
+      !EnableSWPOptSize.getPosition())
+    return false;
+
+  MF = &mf;
+  MLI = &getAnalysis<MachineLoopInfo>();
+  MDT = &getAnalysis<MachineDominatorTree>();
+  TII = MF->getSubtarget().getInstrInfo();
+  RegClassInfo.runOnMachineFunction(*MF);
+
+  bool changed = false;
+  for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end(); I != E;
+       ++I) {
+    MachineLoop *L = *I;
+    //<SYNOPSYS> record result for -Rpass reporting
+    bool result = scheduleLoop(L);
+    if (!result)
+      L->emitOptimizationRemarkMissed(DEBUG_TYPE, "Failed to pipeline loop");
+    changed |= result;
+    //</SYNOPSYS>
+  }
+
+  //<SYNOPSYS>
+  if (DUMP_AFTER()) mf.dump();
+  if (VIEW_AFTER()) mf.viewCFG();
+  //</SYNOPSYS>
+
+  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;
+}
+
+//<SYNOPSYS>
+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<MDTuple>(P.second);
+    if (MD == nullptr) continue;
+    for (unsigned i = 0, ie = MD->getNumOperands(); i < ie; ++i) {
+      MDTuple* MD2 = dyn_cast<MDTuple>(MD->getOperand(i).get());
+      if (MD2 == nullptr) continue;
+      if (MD2->getNumOperands() != 2) continue;
+      MDString* MDS = dyn_cast<MDString>(MD2->getOperand(0).get());
+      if (MDS == nullptr) continue;
+      ValueAsMetadata* MDV = dyn_cast<ValueAsMetadata>(MD2->getOperand(1).get());
+      if (MDV == nullptr) continue;
+      ConstantInt* CI = dyn_cast<ConstantInt>(MDV->getValue());
+      if (CI == nullptr) continue;
+      if (MDS->getString() == "llvm.loop.pipeline" && CI->isZero())
+        return true;
+    }
+  }
+  return false;
+}
+//</SYNOPSYS>
+
+
+// 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;
+  }
+
+//<SYNOPSYS>
+  if (pragmaPipelineDisabled(L->getHeader())) {
+    L->emitOptimizationRemarkAnalysis(DEBUG_TYPE, "Disabled by pragma");
+    return false;
+  }
+//</SYNOPSYS>
+
+  // 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<LiveIntervals>(), RegClassInfo);
+
+  MachineBasicBlock *MBB = L->getHeader();
+  // The kernel should not include any terminator instructions.  These
+  // will be added back later.
+  SMS.startBlock(MBB);
+
+  // Compute the number of 'real' instructions in the basic block by
+  // ignoring terminators.
+  unsigned size = MBB->size();
+  for (MachineBasicBlock::iterator I = MBB->getFirstTerminator(),
+                                   E = MBB->instr_end();
+       I != E; ++I, --size)
+    ;
+
+  //<SYNOPSYS>
+  if (DUMP_LOOP_ATTEMPT()) {
+    dbgs() << "[MachineSMS::swingModuloScheduler] Attempting loop\n";
+    MBB->dump();
+  }
+  //</SYNOPSYS>
+
+  SMS.enterRegion(MBB, MBB->begin(), MBB->getFirstTerminator(), size);
+  SMS.schedule();
+  SMS.exitRegion();
+
+  SMS.finishBlock();
+  return SMS.hasNewSchedule();
+}
+
+// We override the schedule function in ScheduleDAGInstrs to implement the
+// scheduling part of the Swing Modulo Scheduling algorithm.
+void SwingSchedulerDAG::schedule() {
+  AliasAnalysis *AA = &Pass->getAnalysis<AAResultsWrapperPass>().getAAResults();
+  buildSchedGraph(AA);
+
+  addLoopCarriedDependences(AA);
+  updatePhiDependences();
+  Topo.InitDAGTopologicalSorting();
+  changeDependences();
+  DEBUG({
+    for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
+      SUnits[su].dumpAll(this);
+  });
+
+  NodeSetType NodeSets;
+  findCircuits(NodeSets);
+
+  // Calculate the MII.
+  unsigned ResMII = calculateResMII();
+  unsigned RecMII = calculateRecMII(NodeSets);
+
+  fuseRecs(NodeSets);
+
+  // This flag is used for testing and can cause correctness problems.
+  if (SwpIgnoreRecMII)
+    RecMII = 0;
+
+  MII = std::max(ResMII, RecMII);
+  DEBUG(dbgs() << "MII = " << MII << " (rec=" << RecMII << ", res=" << ResMII
+               << ")\n");
+
+  // Can't schedule a loop without a valid MII.
+  if (MII == 0)
+    return;
+
+  // Don't pipeline large loops.
+  if (SwpMaxMii != -1 && (int)MII > SwpMaxMii)
+    return;
+
+  computeNodeFunctions(NodeSets);
+
+  registerPressureFilter(NodeSets);
+
+  colocateNodeSets(NodeSets);
+
+  checkNodeSets(NodeSets);
+
+  DEBUG({
+    for (auto &I : NodeSets) {
+      dbgs() << "  Rec NodeSet ";
+      I.dump();
+    }
+  });
+
+  std::sort(NodeSets.begin(), NodeSets.end(), std::greater<NodeSet>());
+
+  groupRemainingNodes(NodeSets);
+
+  removeDuplicateNodes(NodeSets);
+
+  DEBUG({
+    for (auto &I : NodeSets) {
+      dbgs() << "  NodeSet ";
+      I.dump();
+    }
+  });
+
+//<SYNOPSYS> Try bi-directional, then BottomUp and then TopDown
+
+  SetVector<SUnit *> 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<SUnit *> 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<SUnit *> 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<SUnit *> 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<SUnit *> NodeOrderTopDownMerged;
+    computeNodeOrder(NodeSets, NodeOrderTopDownMerged, TopDown);
+    assert(NodeOrderTopDownMerged.size() != 0);
+    Scheduled = schedulePipeline(Schedule, NodeOrderTopDownMerged);
+    if (Scheduled)
+      dbgs() << ">>>>[Case 5] ScheduleFound!\n";
+  }
+
+  if (!Scheduled)
+    return;
+//</SYNOPSYS>
+
+#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<MachineInstr *, 4>::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<SUnit *, 8> Visited;
+  SmallVector<SUnit *, 8> Worklist;
+  Worklist.push_back(SUa);
+  while (!Worklist.empty()) {
+    const SUnit *SU = Worklist.pop_back_val();
+    for (auto &SI : SU->Succs) {
+      SUnit *SuccSU = SI.getSUnit();
+      if (SI.getKind() == SDep::Order) {
+        if (Visited.count(SuccSU))
+          continue;
+        if (SuccSU == SUb)
+          return true;
+        Worklist.push_back(SuccSU);
+        Visited.insert(SuccSU);
+      }
+    }
+  }
+  return false;
+}
+
+/// Return true if the instruction causes a chain between memory
+/// references before and after it.
+static bool isDependenceBarrier(MachineInstr *MI, AliasAnalysis *AA) {
+  return MI->isCall() || MI->hasUnmodeledSideEffects() ||
+         (MI->hasOrderedMemoryRef() &&
+          (!MI->mayLoad() || !MI->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<Value *> &Objs,
+                                 const DataLayout &DL) {
+  if (!MI->hasOneMemOperand())
+    return;
+  MachineMemOperand *MM = *MI->memoperands_begin();
+  if (!MM->getValue())
+    return;
+  GetUnderlyingObjects(const_cast<Value *>(MM->getValue()), Objs, DL);
+}
+
+/// Add a chain edge between a load and store if the store can be an
+/// alias of the load on a subsequent iteration, i.e., a loop carried
+/// dependence. This code is very similar to the code in ScheduleDAGInstrs
+/// but that code doesn't create loop carried dependences.
+void SwingSchedulerDAG::addLoopCarriedDependences(AliasAnalysis *AA) {
+  MapVector<Value *, SmallVector<SUnit *, 4>> PendingLoads;
+  for (auto &SU : SUnits) {
+    MachineInstr *MI = SU.getInstr();
+
+    if (isDependenceBarrier(MI, AA))
+      PendingLoads.clear();
+    else if (MI->mayLoad()) {
+      SmallVector<Value *, 4> Objs;
+      getUnderlyingObjects(MI, Objs, MF.getDataLayout());
+      for (auto V : Objs) {
+        SmallVector<SUnit *, 4> &SUs = PendingLoads[V];
+        SUs.push_back(&SU);
+      }
+    } else if (MI->mayStore()) {
+      SmallVector<Value *, 4> Objs;
+      getUnderlyingObjects(MI, Objs, MF.getDataLayout());
+      for (auto V : Objs) {
+        MapVector<Value *, SmallVector<SUnit *, 4>>::iterator I =
+            PendingLoads.find(V);
+        if (I == PendingLoads.end())
+          continue;
+        for (auto Load : I->second) {
+          if (isSuccOrder(Load, &SU))
+            continue;
+          MachineInstr *LdMI = Load->getInstr();
+          // First, perform the cheaper check that compares the base register.
+          // If they are the same and the load offset is less than the store
+          // offset, then mark the dependence as loop carried potentially.
+          unsigned BaseReg1, 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<SDep, 4> RemoveDeps;
+  const TargetSubtargetInfo &ST = MF.getSubtarget<TargetSubtargetInfo>();
+
+  // Iterate over each DAG node.
+  for (std::vector<SUnit>::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<SUnit>::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<SDep, 4> Deps;
+    for (SUnit::pred_iterator P = I->Preds.begin(), E = I->Preds.end(); P != E;
+         ++P)
+      if (P->getSUnit() == DefSU)
+        Deps.push_back(*P);
+    for (int i = 0, e = Deps.size(); i != e; i++) {
+      Topo.RemovePred(&*I, Deps[i].getSUnit());
+      I->removePred(Deps[i]);
+    }
+    // Remove the chain dependence between the instructions.
+    Deps.clear();
+    for (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<unsigned, unsigned> Resources;
+
+  // Compute the number of functional unit alternatives needed
+  // at each stage, and take the minimum value. We prioritize the
+  // instructions by the least number of choices first.
+  unsigned minFuncUnits(const MachineInstr *Inst, unsigned &F) const {
+    unsigned schedClass = Inst->getDesc().getSchedClass();
+    unsigned min = UINT_MAX;
+    for (const InstrStage *IS = InstrItins->beginStage(schedClass),
+                          *IE = InstrItins->endStage(schedClass);
+         IS != IE; ++IS) {
+      unsigned funcUnits = IS->getUnits();
+      unsigned numAlternatives = countPopulation(funcUnits);
+      if (numAlternatives < min) {
+        min = numAlternatives;
+        F = funcUnits;
+      }
+    }
+    return min;
+  }
+
+  // Compute the critical resources needed by the instruction. This
+  // function records the functional units needed by instructions that
+  // must use only one functional unit. We use this as a tie breaker
+  // for computing the resource MII. The instrutions that require
+  // the same, highly used, functional unit have high priority.
+  void calcCriticalResources(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<DFAPacketizer *, 8> 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<MachineInstr *, std::vector<MachineInstr *>, FuncUnitSorter>
+      FuncUnitOrder(FUS);
+
+  for (MachineBasicBlock::iterator I = MBB->getFirstNonPHI(),
+                                   E = MBB->getFirstTerminator();
+       I != E; ++I)
+    FuncUnitOrder.push(I);
+
+  while (!FuncUnitOrder.empty()) {
+    MachineInstr *MI = FuncUnitOrder.top();
+    FuncUnitOrder.pop();
+    if (TII->isZeroCost(MI->getOpcode()))
+      continue;
+
+    //<SYNOPSYS>
+#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.
+    //</SYNOPSYS>
+
+    // Attempt to reserve the instruction in an existing DFA. At least one
+    // DFA is needed for each cycle.
+    unsigned NumCycles = getSUnit(MI)->Latency;
+    unsigned ReservedCycles = 0;
+
+    SmallVectorImpl<DFAPacketizer *>::iterator RI = Resources.begin();
+    SmallVectorImpl<DFAPacketizer *>::iterator RE = Resources.end();
+    for (unsigned C = 0; C < NumCycles; ++C)
+      while (RI != RE) {
+        if ((*RI++)->canReserveResources(MI)) {
+          ++ReservedCycles;
+          break;
+        }
+      }
+    // Start reserving resources using existing DFAs.
+    for (unsigned C = 0; C < ReservedCycles; ++C) {
+      --RI;
+      (*RI)->reserveResources(MI);
+    }
+    // Add new DFAs, if needed, to reserve resources.
+    for (unsigned C = ReservedCycles; C < NumCycles; ++C) {
+      DFAPacketizer *NewResource =
+          TII->CreateTargetScheduleState(MF.getSubtarget());
+      assert(NewResource->canReserveResources(MI) && "Reserve error.");
+      NewResource->reserveResources(MI);
+      Resources.push_back(NewResource);
+    }
+#endif //SYNOPSYS
+  }
+#//<SYNOPSYS>
+#if 1
+  int Resmii = Resources.getMaxIssueCycles();
+#else //</SYNOPSYS>
+  int Resmii = Resources.size();
+  // Delete the memory for each of the DFAs that were created earlier.
+  for (SmallVectorImpl<DFAPacketizer *>::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<SUnit> &SUnits) {
+  SmallVector<std::pair<SUnit *, SDep>, 8> DepsAdded;
+  for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
+    SUnit *SU = &SUnits[i];
+    for (SUnit::pred_iterator IP = SU->Preds.begin(), EP = SU->Preds.end();
+         IP != EP; ++IP) {
+      if (IP->getKind() != SDep::Anti)
+        continue;
+      DepsAdded.push_back(std::make_pair(SU, *IP));
+    }
+  }
+  for (SmallVector<std::pair<SUnit *, SDep>, 8>::iterator I = DepsAdded.begin(),
+                                                          E = DepsAdded.end();
+       I != E; ++I) {
+    // Remove this anti dependency and add one in the reverse direction.
+    SUnit *SU = I->first;
+    SDep &D = I->second;
+    SUnit *TargetSU = D.getSUnit();
+    unsigned Reg = D.getReg();
+    unsigned Lat = D.getLatency();
+    SU->removePred(D);
+    SDep Dep(SU, SDep::Anti, Reg);
+    Dep.setLatency(Lat);
+    TargetSU->addPred(Dep);
+  }
+}
+
+/// Create the adjacency structure of the nodes in the graph.
+void SwingSchedulerDAG::Circuits::createAdjacencyStructure(
+    SwingSchedulerDAG *DAG) {
+  BitVector Added(SUnits.size());
+  for (int i = 0, e = SUnits.size(); i != e; ++i) {
+    Added.reset();
+    // Add any successor to the adjacency matrix and exclude duplicates.
+    for (auto &SI : SUnits[i].Succs) {
+      // 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<SUnit *, 4> &BU = B[U];
+  while (!BU.empty()) {
+    SmallPtrSet<SUnit *, 4>::iterator SI = BU.begin();
+    assert(SI != BU.end() && "Invalid B set.");
+    SUnit *W = *SI;
+    BU.erase(W);
+    if (Blocked.test(W->NodeNum))
+      unblock(W->NodeNum);
+  }
+}
+
+/// Identify all the elementary circuits in the dependence graph using
+/// Johnson's circuit algorithm.
+void SwingSchedulerDAG::findCircuits(NodeSetType &NodeSets) {
+  // Swap all the anti dependences in the DAG. That means it is no longer a DAG,
+  // but we do this to find the circuits, and then change them back.
+  swapAntiDependences(SUnits);
+
+  Circuits Cir(SUnits);
+  // Create the adjacency structure.
+  Cir.createAdjacencyStructure(this);
+  for (int i = 0, e = SUnits.size(); i != e; ++i) {
+    Cir.reset();
+    Cir.circuit(i, i, NodeSets);
+  }
+
+  // Change the dependences back so that we've created a DAG again.
+  swapAntiDependences(SUnits);
+}
+
+// Return true for DAG nodes that we ignore when computing the cost functions.
+// We ignore the back-edge recurrence in order to avoid unbounded recurison
+// in the calculation of the ASAP, ALAP, etc functions.
+static bool ignoreDependence(const SDep &D, bool isPred) {
+  if (D.isArtificial())
+    return true;
+  return D.getKind() == SDep::Anti && isPred;
+}
+
+// Compute several functions need to order the nodes for scheduling.
+//  ASAP - Earliest time to schedule a node.
+//  ALAP - Latest time to schedule a node.
+//  MOV - Mobility function, difference between ALAP and ASAP.
+//  D - Depth of each node.
+//  H - Height of each node.
+//
+void SwingSchedulerDAG::computeNodeFunctions(NodeSetType &NodeSets) {
+
+  ScheduleInfo.resize(SUnits.size());
+
+  DEBUG({
+    for (ScheduleDAGTopologicalSort::const_iterator I = Topo.begin(),
+                                                    E = Topo.end();
+         I != E; ++I) {
+      SUnit *SU = &SUnits[*I];
+      SU->dump(this);
+    }
+  });
+
+  int maxASAP = 0;
+  // Compute ASAP.
+  for (ScheduleDAGTopologicalSort::const_iterator I = Topo.begin(),
+                                                  E = Topo.end();
+       I != E; ++I) {
+    int asap = 0;
+    SUnit *SU = &SUnits[*I];
+    for (SUnit::const_pred_iterator IP = SU->Preds.begin(),
+                                    EP = SU->Preds.end();
+         IP != EP; ++IP) {
+      if (ignoreDependence(*IP, true))
+        continue;
+      SUnit *pred = IP->getSUnit();
+      asap = std::max(asap, (int)(getASAP(pred) + getLatency(SU, *IP) -
+                                  getDistance(pred, SU, *IP) * MII));
+    }
+
+    maxASAP = std::max(maxASAP, asap);
+    ScheduleInfo[*I].ASAP = asap;
+  }
+
+  // Compute ALAP and MOV.
+  for (ScheduleDAGTopologicalSort::const_reverse_iterator I = Topo.rbegin(),
+                                                          E = Topo.rend();
+       I != E; ++I) {
+    int alap = maxASAP;
+    SUnit *SU = &SUnits[*I];
+    for (SUnit::const_succ_iterator IS = SU->Succs.begin(),
+                                    ES = SU->Succs.end();
+         IS != ES; ++IS) {
+      if (ignoreDependence(*IS, true))
+        continue;
+      SUnit *succ = IS->getSUnit();
+      alap = std::min(alap, (int)(getALAP(succ) - getLatency(SU, *IS) +
+                                  getDistance(SU, succ, *IS) * MII));
+    }
+
+    ScheduleInfo[*I].ALAP = alap;
+  }
+
+  // After computing the node functions, compute the summary for each node set.
+  for (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<SUnit *> &NodeOrder,
+                   SmallSetVector<SUnit *, 8> &Preds,
+                   const SwingSchedulerDAG::NodeSet *S = nullptr) {
+  Preds.clear();
+  for (SetVector<SUnit *>::iterator I = NodeOrder.begin(), E = NodeOrder.end();
+       I != E; ++I) {
+    for (SUnit::pred_iterator PI = (*I)->Preds.begin(), PE = (*I)->Preds.end();
+         PI != PE; ++PI) {
+      if (S && S->count(PI->getSUnit()) == 0)
+        continue;
+      if (ignoreDependence(*PI, true))
+        continue;
+      if (NodeOrder.count(PI->getSUnit()) == 0)
+        Preds.insert(PI->getSUnit());
+    }
+    // Back-edges are predecessors with an anti-dependence.
+    for (SUnit::const_succ_iterator IS = (*I)->Succs.begin(),
+                                    ES = (*I)->Succs.end();
+         IS != ES; ++IS) {
+      if (IS->getKind() != SDep::Anti)
+        continue;
+      if (S && S->count(IS->getSUnit()) == 0)
+        continue;
+      if (NodeOrder.count(IS->getSUnit()) == 0)
+        Preds.insert(IS->getSUnit());
+    }
+  }
+  return Preds.size() > 0;
+}
+
+/// Compute the Succ_L(O) set, as defined in the paper. The set is defined
+/// as the successors of the elements of NodeOrder that are not also in
+/// NodeOrder.
+static bool succ_L(SetVector<SUnit *> &NodeOrder,
+                   SmallSetVector<SUnit *, 8> &Succs,
+                   const SwingSchedulerDAG::NodeSet *S = nullptr) {
+  Succs.clear();
+  for (SetVector<SUnit *>::iterator I = NodeOrder.begin(), E = NodeOrder.end();
+       I != E; ++I) {
+    for (SUnit::succ_iterator SI = (*I)->Succs.begin(), SE = (*I)->Succs.end();
+         SI != SE; ++SI) {
+      if (S && S->count(SI->getSUnit()) == 0)
+        continue;
+      if (ignoreDependence(*SI, false))
+        continue;
+      if (NodeOrder.count(SI->getSUnit()) == 0)
+        Succs.insert(SI->getSUnit());
+    }
+    for (SUnit::const_pred_iterator PI = (*I)->Preds.begin(),
+                                    PE = (*I)->Preds.end();
+         PI != PE; ++PI) {
+      if (PI->getKind() != SDep::Anti)
+        continue;
+      if (S && S->count(PI->getSUnit()) == 0)
+        continue;
+      if (NodeOrder.count(PI->getSUnit()) == 0)
+        Succs.insert(PI->getSUnit());
+    }
+  }
+  return Succs.size() > 0;
+}
+
+/// Return true if there is a path from the specified node to any of the nodes
+/// in DestNodes. Keep track and return the nodes in any path.
+static bool computePath(SUnit *Cur, SetVector<SUnit *> &Path,
+                        SetVector<SUnit *> &DestNodes,
+                        SetVector<SUnit *> &Exclude,
+                        SmallPtrSet<SUnit *, 8> &Visited) {
+  if (Cur->isBoundaryNode())
+    return false;
+  if (Exclude.count(Cur) != 0)
+    return false;
+  if (DestNodes.count(Cur) != 0)
+    return true;
+  if (!Visited.insert(Cur).second)
+    return Path.count(Cur) != 0;
+  bool FoundPath = false;
+  for (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 <class S1Ty, class S2Ty> static bool isSubset(S1Ty &Set1, S2Ty &Set2) {
+  for (typename S1Ty::iterator I = Set1.begin(), E = Set1.end(); I != E; ++I)
+    if (Set2.count(*I) == 0)
+      return false;
+  return true;
+}
+
+
+/// Compute the live-out registers for the instructions in a node-set.
+/// The live-out registers are those that are defined in the node-set,
+/// but not used. Except for use operands of Phis.
+static void computeLiveOuts(RegPressureTracker &RPTracker,
+                            SwingSchedulerDAG::NodeSet &NS) {
+  SmallVector<unsigned, 8> LiveOutRegs;
+  SmallSet<unsigned, 4> 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<SUnit *> SUnits(NS.begin(), NS.end());
+    std::sort(SUnits.begin(), SUnits.end(), [](const SUnit *A, const SUnit *B) {
+      return A->NodeNum > B->NodeNum;
+    });
+
+    for (auto &SU : SUnits) {
+      // Since we're computing the register pressure for a subset of the
+      // instructions in a block, we need to set the tracker for each
+      // instruction in the node-set. The tracker is set to the instruction
+      // just after the one we're interested in.
+      MachineBasicBlock::const_iterator CurInstI = SU->getInstr();
+      RecRPTracker.setPos(std::next(CurInstI));
+
+      RegPressureDelta RPDelta;
+      ArrayRef<PressureChange> CriticalPSets;
+      RecRPTracker.getMaxUpwardPressureDelta(SU->getInstr(), nullptr, RPDelta,
+                                             CriticalPSets,
+                                             RecRegPressure.MaxSetPressure);
+      if (RPDelta.Excess.isValid()) {
+        DEBUG(dbgs() << "Excess register pressure: SU(" << SU->NodeNum << ") "
+                     << TRI->getRegPressureSetName(RPDelta.Excess.getPSet())
+                     << ":" << RPDelta.Excess.getUnitInc());
+        NS.setExceedPressure(SU);
+        break;
+      }
+      RecRPTracker.recede();
+    }
+  }
+}
+
+/// A heuristic to colocate node sets that have the same set of
+/// successors.
+void SwingSchedulerDAG::colocateNodeSets(NodeSetType &NodeSets) {
+  unsigned Colocate = 0;
+  for (int i = 0, e = NodeSets.size(); i < e; ++i) {
+    NodeSet &N1 = NodeSets[i];
+    SmallSetVector<SUnit *, 8> S1;
+    if (N1.empty() || !succ_L(N1, S1))
+      continue;
+    for (int j = i + 1; j < e; ++j) {
+      NodeSet &N2 = NodeSets[j];
+      if (N1.compareRecMII(N2) != 0)
+        continue;
+      SmallSetVector<SUnit *, 8> S2;
+      if (N2.empty() || !succ_L(N2, S2))
+        continue;
+      if (isSubset(S1, S2) && S1.size() == S2.size()) {
+        N1.setColocate(++Colocate);
+        N2.setColocate(Colocate);
+        break;
+      }
+    }
+  }
+}
+
+/// Check if the existing node-sets are profitable. If not, then ignore the
+/// recurrent node-sets, and attempt to schedule all nodes together. This is
+/// a heuristic. If the MII is large and there is a non-recurrent node with
+/// a large depth compared to the MII, then it's best to try and schedule
+/// all instruction together instead of starting with the recurrent node-sets.
+void SwingSchedulerDAG::checkNodeSets(NodeSetType &NodeSets) {
+  // Look for loops with a large MII.
+  if (MII <= 20)
+    return;
+  // Check if the node-set contains only a simple add recurrence.
+  for (auto &NS : NodeSets)
+    if (NS.size() > 2)
+      return;
+  // If the depth of any instruction is significantly larger than the MII, then
+  // ignore the recurrent node-sets and treat all instructions equally.
+  for (auto &SU : SUnits)
+    if (SU.getDepth() > MII * 1.5) {
+      NodeSets.clear();
+      DEBUG(dbgs() << "Clear recurrence node-sets\n");
+      return;
+    }
+}
+
+// Add the nodes that do not belong to a recurrence set into groups
+// based upon connected componenets.
+void SwingSchedulerDAG::groupRemainingNodes(NodeSetType &NodeSets) {
+  SetVector<SUnit *> NodesAdded;
+  SmallPtrSet<SUnit *, 8> Visited;
+  // Add the nodes that are on a path between the previous node sets and
+  // the current node set.
+  for (NodeSetType::iterator I = NodeSets.begin(), E = NodeSets.end(); I != E;
+       ++I) {
+    SmallSetVector<SUnit *, 8> N;
+    // Add the nodes from the current node set to the previous node set.
+    if (succ_L(*I, N)) {
+      SetVector<SUnit *> Path;
+      for (SmallSetVector<SUnit *, 8>::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<SUnit *> Path;
+      for (SmallSetVector<SUnit *, 8>::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<SUnit *, 8> N;
+  if (succ_L(NodesAdded, N))
+    for (SmallSetVector<SUnit *, 8>::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<SUnit *, 8>::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<SUnit *> &NodesAdded) {
+
+  //<SYNOPSYS> 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());
+  //</SYNOPSYS>
+
+  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<SUnit *, 8> &Set1,
+                        const SwingSchedulerDAG::NodeSet &Set2,
+                        SmallSetVector<SUnit *, 8> &Result) {
+  Result.clear();
+  for (unsigned i = 0, e = Set1.size(); i != e; ++i) {
+    SUnit *SU = Set1[i];
+    if (Set2.count(SU) != 0)
+      Result.insert(SU);
+  }
+  return !Result.empty();
+}
+
+/// Merge the recurrence node sets that have the same initial node.
+void SwingSchedulerDAG::fuseRecs(NodeSetType &NodeSets) {
+  for (NodeSetType::iterator I = NodeSets.begin(), E = NodeSets.end(); I != E;
+       ++I) {
+    NodeSet &NI = *I;
+    for (NodeSetType::iterator J = I + 1; J != E;) {
+      NodeSet &NJ = *J;
+      if (NI.getNode(0)->NodeNum == NJ.getNode(0)->NodeNum) {
+        if (NJ.compareRecMII(NI) > 0)
+          NI.setRecMII(NJ.getRecMII());
+        for (NodeSet::iterator NII = J->begin(), ENI = J->end(); NII != ENI;
+             ++NII)
+          I->insert(*NII);
+        NodeSets.erase(J);
+        E = NodeSets.end();
+      } else {
+        ++J;
+      }
+    }
+  }
+}
+
+//<SYNOPSYS> Merge all nodes
+void SwingSchedulerDAG::mergeAllNodes(NodeSetType &NodeSets) {
+    NodeSets.clear();
+    DEBUG(dbgs() << "Clear recurrence node-sets\n");
+  groupRemainingNodes(NodeSets);
+  return;
+}
+//</SYNOPSYS>
+
+/// 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<SUnit *>& NodeOrder, OrderKind order) { //SYNOPSYS
+
+  SmallSetVector<SUnit *, 8> R;
+  NodeOrder.clear();
+
+  for (auto &Nodes : NodeSets) {
+    DEBUG(dbgs() << "NodeSet size " << Nodes.size() << "\n");
+    OrderKind Order;
+    SmallSetVector<SUnit *, 8> N;
+    //<SYNOPSYS>
+    if (order != AnyOrder) {
+      R.insert(Nodes.begin(), Nodes.end());
+      Order = order;
+      DEBUG(dbgs() << "  FORCED order ");
+    } else
+    //</SYNOPSYS>
+
+    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<SUnit *, 8>::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<SUnit *, 8> N;
+        if (pred_L(NodeOrder, N, &Nodes))
+          R.insert(N.begin(), N.end());
+      } else {
+        // Choose the node with the maximum depth.  If more than one, choose
+        // the node with the lowest MOV. If there is still more than one, check
+        // for a dependence between the instructions.
+        while (!R.empty()) {
+          SUnit *maxDepth = nullptr;
+          for (SmallSetVector<SUnit *, 8>::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<SUnit *, 8> N;
+        if (succ_L(NodeOrder, N, &Nodes))
+          R.insert(N.begin(), N.end());
+      }
+    }
+    DEBUG(dbgs() << "\nDone with Nodeset\n");
+  }
+
+  DEBUG({
+    dbgs() << "Node order: ";
+    for (SetVector<SUnit *>::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<SUnit *> 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<SUnit *>::iterator NI = NodeOrder.begin();
+    SetVector<SUnit *>::iterator NE = NodeOrder.end();
+    do {
+      SUnit *SU = *NI;
+
+      // Compute the schedule time for the instruction, which is based
+      // upon the scheduled time for any predecessors/successors.
+      int EarlyStart = INT_MIN;
+      int LateStart = INT_MAX;
+      // These values are set when the size of the schedule window is limited
+      // due to chain dependences.
+      int SchedEnd = INT_MAX;
+      int SchedStart = INT_MIN;
+      Schedule.computeStart(SU, &EarlyStart, &LateStart, &SchedEnd, &SchedStart,
+                            II, this);
+      DEBUG({
+        dbgs() << "Inst (" << SU->NodeNum << ") ";
+        SU->getInstr()->dump();
+        dbgs() << "\n";
+      });
+      DEBUG({
+        dbgs() << "\tes: " << EarlyStart << " ls: " << LateStart
+               << " me: " << SchedEnd << " ms: " << SchedStart << "\n";
+      });
+
+      if (EarlyStart > LateStart || SchedEnd < EarlyStart ||
+          SchedStart > LateStart)
+        scheduleFound = false;
+      else if (EarlyStart != INT_MIN && LateStart == INT_MAX) {
+        SchedEnd = std::min(SchedEnd, EarlyStart + (int)II - 1);
+        scheduleFound = Schedule.insert(SU, EarlyStart, SchedEnd, II);
+      } else if (EarlyStart == INT_MIN && LateStart != INT_MAX) {
+        SchedStart = std::max(SchedStart, LateStart - (int)II + 1);
+        scheduleFound = Schedule.insert(SU, LateStart, SchedStart, II);
+      } else if (EarlyStart != INT_MIN && LateStart != INT_MAX) {
+        SchedEnd =
+            std::min(SchedEnd, std::min(LateStart, EarlyStart + (int)II - 1));
+        // When scheduling a Phi it is better to start at the late cycle and go
+        // backwards. The default order may insert the Phi too far away from
+        // its first dependence.
+        if (SU->getInstr()->isPHI())
+          scheduleFound = Schedule.insert(SU, SchedEnd, EarlyStart, II);
+        else
+          scheduleFound = Schedule.insert(SU, EarlyStart, SchedEnd, II);
+      } else {
+        int FirstCycle = Schedule.getFirstCycle();
+
+#if 0
+        //<SYNOPSYS>
+        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
+
+        //</SYNOPSYS>
+        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<MachineBasicBlock *, 4> 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<SUnit *> &CycleInstrs = Schedule.getInstructions(Cycle);
+    // This inner loop schedules each instruction in the cycle.
+    for (std::deque<SUnit *>::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<MachineBasicBlock *, 4> EpilogBBs;
+  // Generate the epilog instructions to complete the pipeline.
+  generateEpilog(Schedule, MaxStageCount, KernelBB, VRMap, EpilogBBs,
+                 PrologBBs);
+
+  // We need this step because the register allocation doesn't handle some
+  // situations well, so we insert copies to help out.
+  splitLifetimes(KernelBB, EpilogBBs, Schedule);
+
+  // Remove dead instructions due to loop induction variables.
+  removeDeadInstructions(KernelBB, EpilogBBs);
+
+  // Add branches between prolog and epilog blocks.
+  addBranches(PrologBBs, KernelBB, EpilogBBs, Schedule, VRMap);
+
+  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<MachineOperand, 0> 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<MachineOperand, 4> Cond;
+  bool checkBranch = TII->AnalyzeBranch(*KernelBB, TBB, FBB, Cond);
+  assert(!checkBranch && "generateEpilog must be able to analyze the branch");
+  if (checkBranch)
+    return;
+
+  MachineBasicBlock::succ_iterator LoopExitI = KernelBB->succ_begin();
+  if (*LoopExitI == KernelBB)
+    ++LoopExitI;
+  assert(LoopExitI != KernelBB->succ_end() && "Expecting a successor");
+  MachineBasicBlock *LoopExitBB = *LoopExitI;
+
+  MachineBasicBlock *PredBB = KernelBB;
+  MachineBasicBlock *EpilogStart = LoopExitBB;
+  InstrMapTy InstrMap;
+
+  // Generate a basic block for each stage, not including the last stage,
+  // which was generated for the kernel.  Each basic block may contain
+  // instructions from multiple stages/iterations.
+  int EpilogStage = LastStage + 1;
+  for (unsigned i = LastStage; i >= 1; --i, ++EpilogStage) {
+    MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock();
+    EpilogBBs.push_back(NewBB);
+    MF.insert(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<MachineOperand, 4> 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<MachineInstr *, 4> PrevInsts;
+  unsigned MaxIter = PrologBBs.size() - 1;
+  unsigned LC = UINT_MAX;
+  unsigned LCMin = UINT_MAX;
+  for (unsigned i = 0, j = MaxIter; i <= MaxIter; ++i, --j) {
+    // Add branches to the prolog that go to the corresponding
+    // epilog, and the fall-thru prolog/kernel block.
+    MachineBasicBlock *Prolog = PrologBBs[j];
+    MachineBasicBlock *Epilog = EpilogBBs[i];
+    // We've executed one iteration, so decrement the loop count and check for
+    // the loop end.
+    SmallVector<MachineOperand, 4> Cond;
+    // Check if the LOOP0 has already been removed. If so, then there is no need
+    // to reduce the trip count.
+    if (LC != 0)
+      LC = TII->ReduceLoopCount(*Prolog, IndVar, Cmp, Cond, PrevInsts, j,
+                                MaxIter);
+
+    // Record the value of the first trip count, which is used to determine if
+    // branches and blocks can be removed for constant trip counts.
+    if (LCMin == UINT_MAX)
+      LCMin = LC;
+
+    unsigned numAdded = 0;
+    if (TargetRegisterInfo::isVirtualRegister(LC)) {
+      Prolog->addSuccessor(Epilog);
+      numAdded = TII->InsertBranch(*Prolog, Epilog, LastPro, Cond, DebugLoc());
+    } else if (j >= LCMin) {
+      Prolog->addSuccessor(Epilog);
+      Prolog->removeSuccessor(LastPro);
+      LastEpi->removeSuccessor(Epilog);
+      numAdded = TII->InsertBranch(*Prolog, Epilog, 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<SUnit *, std::pair<unsigned, int64_t>>::iterator It =
+      InstrChanges.find(getSUnit(OldMI));
+  if (It != InstrChanges.end()) {
+    std::pair<unsigned, int64_t> RegAndOffset = It->second;
+    unsigned BasePos, OffsetPos;
+    if (!TII->getBaseAndOffsetPosition(OldMI, BasePos, OffsetPos))
+      return 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<MachineInstr *, 8> Visited;
+  MachineInstr *Def = MRI.getVRegDef(Reg);
+  while (Def->isPHI()) {
+    if (!Visited.insert(Def).second)
+      break;
+    for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2)
+      if (Def->getOperand(i + 1).getMBB() == BB) {
+        Def = MRI.getVRegDef(Def->getOperand(i).getReg());
+        break;
+      }
+  }
+  return Def;
+}
+
+/// Return the new name for the value from the previous stage.
+unsigned SwingSchedulerDAG::getPrevMapVal(unsigned StageNum, unsigned PhiStage,
+                                          unsigned LoopVal, 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<SUnit *, std::pair<unsigned, int64_t>>::iterator It =
+      InstrChanges.find(SU);
+  if (It != InstrChanges.end()) {
+    std::pair<unsigned, int64_t> RegAndOffset = It->second;
+    unsigned BasePos, OffsetPos;
+    if (!TII->getBaseAndOffsetPosition(MI, BasePos, OffsetPos))
+      return 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<SUnit *> &cycleInstrs = ScheduledInstrs[checkCycle];
+
+      for (std::deque<SUnit *>::iterator I = cycleInstrs.begin(),
+                                         E = cycleInstrs.end();
+           I != E; ++I) {
+        if (ST.getInstrInfo()->isZeroCost((*I)->getInstr()->getOpcode()))
+          continue;
+        assert(Resources->canReserveResources((*I)->getInstr()) &&
+               "These instructions have already been scheduled.");
+        Resources->reserveResources((*I)->getInstr());
+      }
+    }
+#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<SUnit *, 8> Visited;
+  SmallVector<SDep, 8> Worklist;
+  Worklist.push_back(Dep);
+  int EarlyCycle = INT_MAX;
+  while (!Worklist.empty()) {
+    const SDep &Cur = Worklist.pop_back_val();
+    SUnit *PrevSU = Cur.getSUnit();
+    if (Visited.count(PrevSU))
+      continue;
+    std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(PrevSU);
+    if (it == InstrToCycle.end())
+      continue;
+    EarlyCycle = std::min(EarlyCycle, it->second);
+    for (const auto &PI : PrevSU->Preds)
+      if (SwingSchedulerDAG::isOrder(PrevSU, PI))
+        Worklist.push_back(PI);
+    Visited.insert(PrevSU);
+  }
+  return EarlyCycle;
+}
+
+// Return the cycle of the latest scheduled instruction in the chain.
+int SMSchedule::latestCycleInChain(const SDep &Dep) {
+  SmallPtrSet<SUnit *, 8> Visited;
+  SmallVector<SDep, 8> Worklist;
+  Worklist.push_back(Dep);
+  int LateCycle = INT_MIN;
+  while (!Worklist.empty()) {
+    const SDep &Cur = Worklist.pop_back_val();
+    SUnit *SuccSU = Cur.getSUnit();
+    if (Visited.count(SuccSU))
+      continue;
+    std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SuccSU);
+    if (it == InstrToCycle.end())
+      continue;
+    LateCycle = std::max(LateCycle, it->second);
+    for (const auto &SI : SuccSU->Succs)
+      if (SwingSchedulerDAG::isOrder(SuccSU, SI))
+        Worklist.push_back(SI);
+    Visited.insert(SuccSU);
+  }
+  return LateCycle;
+}
+
+/// If an instruction has a use that spans multiple iterations, then
+/// return true. These instructions are characterized by having a back-ege
+/// to a Phi, which contains a reference to another Phi.
+static SUnit *multipleIterations(SUnit *SU, SwingSchedulerDAG *DAG) {
+  for (auto &P : SU->Preds)
+    if (DAG->isBackedge(SU, P) && P.getSUnit()->getInstr()->isPHI())
+      for (auto &S : P.getSUnit()->Succs)
+        if (S.getKind() == SDep::Order && S.getSUnit()->getInstr()->isPHI())
+          return P.getSUnit();
+  return nullptr;
+}
+
+// Compute the scheduling start slot for the instruction.  The start slot
+// depends on any predecessor or successor nodes scheduled already.
+void SMSchedule::computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart,
+                              int *MinEnd, int *MaxStart, int II,
+                              SwingSchedulerDAG *DAG) {
+  // Iterate over each instruction that has been scheduled already.  The start
+  // slot computuation depends on whether the previously scheduled instruction
+  // is a predecessor or successor of the specified instruction.
+  for (int cycle = getFirstCycle(); cycle <= LastCycle; ++cycle) {
+
+    // Iterate over each instruction in the current cycle.
+    for (std::deque<SUnit *>::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<SUnit *> &Insts) {
+  MachineInstr *MI = SU->getInstr();
+  bool OrderBeforeUse = false;
+  bool OrderAfterDef = false;
+  bool OrderBeforeDef = false;
+  unsigned MoveDef = 0;
+  unsigned MoveUse = 0;
+  int StageInst1 = stageScheduled(SU);
+
+  unsigned Pos = 0;
+  for (std::deque<SUnit *>::iterator I = Insts.begin(), E = Insts.end(); I != E;
+       ++I, ++Pos) {
+    // Relative order of Phis does not matter.
+    if (MI->isPHI() && (*I)->getInstr()->isPHI())
+      continue;
+    for (unsigned i = 0, e = MI->getNumOperands(); i < e; ++i) {
+      MachineOperand &MO = MI->getOperand(i);
+      if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
+        continue;
+      unsigned Reg = MO.getReg();
+      unsigned BasePos, OffsetPos;
+      if (ST.getInstrInfo()->getBaseAndOffsetPosition(MI, BasePos, OffsetPos))
+        if (MI->getOperand(BasePos).getReg() == Reg)
+          if (unsigned NewReg = SSD->getInstrBaseReg(SU))
+            Reg = NewReg;
+      bool Reads, Writes;
+      std::tie(Reads, Writes) =
+          (*I)->getInstr()->readsWritesVirtualRegister(Reg);
+      if (MO.isDef() && Reads && stageScheduled(*I) <= StageInst1) {
+        OrderBeforeUse = true;
+        MoveUse = Pos;
+      } else if (MO.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<SUnit *> &cycleInstrs =
+          ScheduledInstrs[cycle + (stage * InitiationInterval)];
+      for (std::deque<SUnit *>::reverse_iterator I = cycleInstrs.rbegin(),
+                                                 E = cycleInstrs.rend();
+           I != E; ++I)
+        ScheduledInstrs[cycle].push_front(*I);
+    }
+  }
+  // Iterate over the definitions in each instruction, and compute the
+  // stage difference for each use.  Keep the maximum value.
+  for (std::map<SUnit *, int>::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<SUnit *> &cycleInstrs = ScheduledInstrs[Cycle];
+    std::deque<SUnit *> newOrderZC;
+    // Put the zero-cost, pseudo instructions at the start of the cycle.
+    for (unsigned i = 0, e = cycleInstrs.size(); i < e; ++i) {
+      SUnit *SU = cycleInstrs[i];
+      if (ST.getInstrInfo()->isZeroCost(SU->getInstr()->getOpcode()))
+        orderDependence(SSD, SU, newOrderZC);
+    }
+    std::deque<SUnit *> newOrderI;
+    // Then, add the regular instructions back.
+    for (unsigned i = 0, e = cycleInstrs.size(); i < e; ++i) {
+      SUnit *SU = cycleInstrs[i];
+      if (!ST.getInstrInfo()->isZeroCost(SU->getInstr()->getOpcode()))
+        orderDependence(SSD, SU, newOrderI);
+    }
+    // Replace the old order with the new order.
+    cycleInstrs.swap(newOrderZC);
+    cycleInstrs.insert(cycleInstrs.end(), newOrderI.begin(), newOrderI.end());
+  }
+
+  DEBUG(dump(););
+}
+
+// Print the schedule information to the given output.
+void SMSchedule::print(raw_ostream &os) const {
+  // Iterate over each cycle.
+  for (int cycle = getFirstCycle(); cycle <= getFinalCycle(); ++cycle) {
+    // Iterate over each instruction in the cycle.
+    const_sched_iterator cycleInstrs = ScheduledInstrs.find(cycle);
+    for (std::deque<SUnit *>::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()); }

lib/Parse/ParsePragma.cpp

assert(TokSize > 0 &&
          "PragmaLoopHintInfo::Toks must contain at least one token.");
 
   // If no option is specified the argument is assumed to be a constant expr.
   bool OptionUnroll = false;
   bool StateOption = false;
   if (OptionInfo) { // Pragma Unroll does not specify an option.
     OptionUnroll = OptionInfo->isStr("unroll");
     StateOption = llvm::StringSwitch<bool>(OptionInfo->getName())
+                      .Case("pipeline", true) //SYNOPSYS
                       .Case("vectorize", true)
                       .Case("interleave", true)
                       .Case("unroll", true)
                       .Default(false);
   }
 
   // Verify loop hint has an argument.
   if (Toks[0].is(tok::eof)) {
if (Tok.isNot(tok::identifier)) {
     return;
   }
 
   while (Tok.is(tok::identifier)) {
     Token Option = Tok;
     IdentifierInfo *OptionInfo = Tok.getIdentifierInfo();
 
     bool OptionValid = llvm::StringSwitch<bool>(OptionInfo->getName())
+                           .Case("pipeline", true) //SYNOPSYS
                            .Case("vectorize", true)
                            .Case("interleave", true)
                            .Case("unroll", true)
                            .Case("vectorize_width", true)
                            .Case("interleave_count", true)
                            .Case("unroll_count", true)
                            .Default(false);
     if (!OptionValid) {

lib/Sema/SemaStmtAttr.cpp

if (PragmaNoUnroll) {
     }
   } else {
     // #pragma clang loop ...
     Spelling = LoopHintAttr::Pragma_clang_loop;
     assert(OptionLoc && OptionLoc->Ident &&
            "Attribute must have valid option info.");
     Option = llvm::StringSwitch<LoopHintAttr::OptionType>(
                  OptionLoc->Ident->getName())
+                 .Case("pipeline", LoopHintAttr::Pipeline) //SYNOPSYS
                  .Case("vectorize", LoopHintAttr::Vectorize)
                  .Case("vectorize_width", LoopHintAttr::VectorizeWidth)
                  .Case("interleave", LoopHintAttr::Interleave)
                  .Case("interleave_count", LoopHintAttr::InterleaveCount)
                  .Case("unroll", LoopHintAttr::Unroll)
                  .Case("unroll_count", LoopHintAttr::UnrollCount)
                  .Default(LoopHintAttr::Vectorize);
     if (Option == LoopHintAttr::VectorizeWidth ||
         Option == LoopHintAttr::InterleaveCount ||
         Option == LoopHintAttr::UnrollCount) {
       assert(ValueExpr && "Attribute must have a valid value expression.");
       if (S.CheckLoopHintExpr(ValueExpr, St->getLocStart()))
         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");
       if (StateLoc->Ident->isStr("disable"))
         State = LoopHintAttr::Disable;
       else if (StateLoc->Ident->isStr("assume_safety"))
         State = LoopHintAttr::AssumeSafety;
       else if (StateLoc->Ident->isStr("full"))
CheckForIncompatibleAttributes(Sema &S,
   // for the loop (for unroll, default indicates full unrolling rather than
   // enabling the transformation).  The numeric form form provides an integer
   // hint (for example, unroll count) to the transformer. The following array
   // accumulates the hints encountered while iterating through the attributes
   // to check for compatibility.
   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<LoopHintAttr>(I);
 
     // Skip non loop hint attributes
     if (!LH)
       continue;
 
     LoopHintAttr::OptionType Option = LH->getOption();
-    enum { Vectorize, Interleave, Unroll } Category;
+    enum { Vectorize, Interleave, Unroll, Pipeline/*SYNOPSYS*/ } Category;
     switch (Option) {
+//<SYNOPSYS>
+    case LoopHintAttr::Pipeline:
+      Category = Pipeline;
+      break;
+//</SYNOPSYS>
     case LoopHintAttr::Vectorize:
     case LoopHintAttr::VectorizeWidth:
       Category = Vectorize;
       break;
     case LoopHintAttr::Interleave:
     case LoopHintAttr::InterleaveCount:
       Category = Interleave;
       break;
     case LoopHintAttr::Unroll:
     case LoopHintAttr::UnrollCount:
       Category = Unroll;
       break;
     };
 
     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;
       CategoryState.StateAttr = LH;
     } else {
       // Numeric hint.  For example, vectorize_width(8).
       PrevAttr = CategoryState.NumericAttr;
       CategoryState.NumericAttr = LH;