lib/CodeGen/ScheduleDAGInstrs.h

   1 //==- ScheduleDAGInstrs.h - MachineInstr Scheduling --------------*- C++ -*-==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the ScheduleDAGInstrs class, which implements
  11 // scheduling for a MachineInstr-based dependency graph.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef SCHEDULEDAGINSTRS_H
  16 #define SCHEDULEDAGINSTRS_H
  17
  18 #include "llvm/CodeGen/MachineDominators.h"
  19 #include "llvm/CodeGen/MachineLoopInfo.h"
  20 #include "llvm/CodeGen/ScheduleDAG.h"
  21 #include "llvm/Support/Compiler.h"
  22 #include "llvm/Target/TargetRegisterInfo.h"
  23 #include "llvm/ADT/IndexedMap.h"
  24 #include "llvm/ADT/SmallSet.h"
  25 #include <map>
  26
  27 namespace llvm {
  28   class MachineLoopInfo;
  29   class MachineDominatorTree;
  30
  31   /// LoopDependencies - This class analyzes loop-oriented register
  32   /// dependencies, which are used to guide scheduling decisions.
  33   /// For example, loop induction variable increments should be
  34   /// scheduled as soon as possible after the variable's last use.
  35   ///
  36   class LLVM_LIBRARY_VISIBILITY LoopDependencies {
  37     const MachineLoopInfo &MLI;
  38     const MachineDominatorTree &MDT;
  39
  40   public:
  41     typedef std::map<unsigned, std::pair<const MachineOperand *, unsigned> >
  42       LoopDeps;
  43     LoopDeps Deps;
  44
  45     LoopDependencies(const MachineLoopInfo &mli,
  46                      const MachineDominatorTree &mdt) :
  47       MLI(mli), MDT(mdt) {}
  48
  49     /// VisitLoop - Clear out any previous state and analyze the given loop.
  50     ///
  51     void VisitLoop(const MachineLoop *Loop) {
  52       assert(Deps.empty() && "stale loop dependencies");
  53
  54       MachineBasicBlock *Header = Loop->getHeader();
  55       SmallSet<unsigned, 8> LoopLiveIns;
  56       for (MachineBasicBlock::livein_iterator LI = Header->livein_begin(),
  57            LE = Header->livein_end(); LI != LE; ++LI)
  58         LoopLiveIns.insert(*LI);
  59
  60       const MachineDomTreeNode *Node = MDT.getNode(Header);
  61       const MachineBasicBlock *MBB = Node->getBlock();
  62       assert(Loop->contains(MBB) &&
  63              "Loop does not contain header!");
  64       VisitRegion(Node, MBB, Loop, LoopLiveIns);
  65     }
  66
  67   private:
  68     void VisitRegion(const MachineDomTreeNode *Node,
  69                      const MachineBasicBlock *MBB,
  70                      const MachineLoop *Loop,
  71                      const SmallSet<unsigned, 8> &LoopLiveIns) {
  72       unsigned Count = 0;
  73       for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end();
  74            I != E; ++I) {
  75         const MachineInstr *MI = I;
  76         if (MI->isDebugValue())
  77           continue;
  78         for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
  79           const MachineOperand &MO = MI->getOperand(i);
  80           if (!MO.isReg() || !MO.isUse())
  81             continue;
  82           unsigned MOReg = MO.getReg();
  83           if (LoopLiveIns.count(MOReg))
  84             Deps.insert(std::make_pair(MOReg, std::make_pair(&MO, Count)));
  85         }
  86         ++Count; // Not every iteration due to dbg_value above.
  87       }
  88
  89       const std::vector<MachineDomTreeNode*> &Children = Node->getChildren();
  90       for (std::vector<MachineDomTreeNode*>::const_iterator I =
  91            Children.begin(), E = Children.end(); I != E; ++I) {
  92         const MachineDomTreeNode *ChildNode = *I;
  93         MachineBasicBlock *ChildBlock = ChildNode->getBlock();
  94         if (Loop->contains(ChildBlock))
  95           VisitRegion(ChildNode, ChildBlock, Loop, LoopLiveIns);
  96       }
  97     }
  98   };
  99
 100   /// ScheduleDAGInstrs - A ScheduleDAG subclass for scheduling lists of
 101   /// MachineInstrs.
 102   class LLVM_LIBRARY_VISIBILITY ScheduleDAGInstrs : public ScheduleDAG {
 103     const MachineLoopInfo &MLI;
 104     const MachineDominatorTree &MDT;
 105     const MachineFrameInfo *MFI;
 106     const InstrItineraryData *InstrItins;
 107
 108     /// isPostRA flag indicates vregs cannot be present.
 109     bool IsPostRA;
 110
 111     /// UnitLatencies (misnamed) flag avoids computing def-use latencies, using
 112     /// the def-side latency only.
 113     bool UnitLatencies;
 114
 115     /// Defs, Uses - Remember where defs and uses of each register are as we
 116     /// iterate upward through the instructions. This is allocated here instead
 117     /// of inside BuildSchedGraph to avoid the need for it to be initialized and
 118     /// destructed for each block.
 119     std::vector<std::vector<SUnit *> > Defs;
 120     std::vector<std::vector<SUnit *> > Uses;
 121
 122     // Virtual register Defs and Uses.
 123     //
 124     // TODO: Eliminate VRegUses by creating SUnits in a prepass and looking up
 125     // the live range's reaching def.
 126     IndexedMap<SUnit*, VirtReg2IndexFunctor> VRegDefs;
 127     IndexedMap<std::vector<SUnit*>, VirtReg2IndexFunctor> VRegUses;
 128
 129     /// PendingLoads - Remember where unknown loads are after the most recent
 130     /// unknown store, as we iterate. As with Defs and Uses, this is here
 131     /// to minimize construction/destruction.
 132     std::vector<SUnit *> PendingLoads;
 133
 134     /// LoopRegs - Track which registers are used for loop-carried dependencies.
 135     ///
 136     LoopDependencies LoopRegs;
 137
 138   protected:
 139
 140     /// DbgValues - Remember instruction that preceeds DBG_VALUE.
 141     typedef std::vector<std::pair<MachineInstr *, MachineInstr *> >
 142       DbgValueVector;
 143     DbgValueVector DbgValues;
 144     MachineInstr *FirstDbgValue;
 145
 146   public:
 147     MachineBasicBlock::iterator Begin;    // The beginning of the range to
 148                                           // be scheduled. The range extends
 149                                           // to InsertPos.
 150     unsigned InsertPosIndex;              // The index in BB of InsertPos.
 151
 152     explicit ScheduleDAGInstrs(MachineFunction &mf,
 153                                const MachineLoopInfo &mli,
 154                                const MachineDominatorTree &mdt,
 155                                bool IsPostRAFlag);
 156
 157     virtual ~ScheduleDAGInstrs() {}
 158
 159     /// NewSUnit - Creates a new SUnit and return a ptr to it.
 160     ///
 161     SUnit *NewSUnit(MachineInstr *MI) {
 162 #ifndef NDEBUG
 163       const SUnit *Addr = SUnits.empty() ? 0 : &SUnits[0];
 164 #endif
 165       SUnits.push_back(SUnit(MI, (unsigned)SUnits.size()));
 166       assert((Addr == 0 || Addr == &SUnits[0]) &&
 167              "SUnits std::vector reallocated on the fly!");
 168       SUnits.back().OrigNode = &SUnits.back();
 169       return &SUnits.back();
 170     }
 171
 172     /// Run - perform scheduling.
 173     ///
 174     void Run(MachineBasicBlock *bb,
 175              MachineBasicBlock::iterator begin,
 176              MachineBasicBlock::iterator end,
 177              unsigned endindex);
 178
 179     /// BuildSchedGraph - Build SUnits from the MachineBasicBlock that we are
 180     /// input.
 181     virtual void BuildSchedGraph(AliasAnalysis *AA);
 182
 183     /// AddSchedBarrierDeps - Add dependencies from instructions in the current
 184     /// list of instructions being scheduled to scheduling barrier. We want to
 185     /// make sure instructions which define registers that are either used by
 186     /// the terminator or are live-out are properly scheduled. This is
 187     /// especially important when the definition latency of the return value(s)
 188     /// are too high to be hidden by the branch or when the liveout registers
 189     /// used by instructions in the fallthrough block.
 190     void AddSchedBarrierDeps();
 191
 192     /// ComputeLatency - Compute node latency.
 193     ///
 194     virtual void ComputeLatency(SUnit *SU);
 195
 196     /// ComputeOperandLatency - Override dependence edge latency using
 197     /// operand use/def information
 198     ///
 199     virtual void ComputeOperandLatency(SUnit *Def, SUnit *Use,
 200                                        SDep& dep) const;
 201
 202     virtual MachineBasicBlock *EmitSchedule();
 203
 204     /// StartBlock - Prepare to perform scheduling in the given block.
 205     ///
 206     virtual void StartBlock(MachineBasicBlock *BB);
 207
 208     /// Schedule - Order nodes according to selected style, filling
 209     /// in the Sequence member.
 210     ///
 211     virtual void Schedule() = 0;
 212
 213     /// FinishBlock - Clean up after scheduling in the given block.
 214     ///
 215     virtual void FinishBlock();
 216
 217     virtual void dumpNode(const SUnit *SU) const;
 218
 219     virtual std::string getGraphNodeLabel(const SUnit *SU) const;
 220
 221   protected:
 222     void addPhysRegDeps(SUnit *SU, unsigned OperIdx);
 223     void addVRegDefDeps(SUnit *SU, unsigned OperIdx);
 224     void addVRegUseDeps(SUnit *SU, unsigned OperIdx);
 225   };
 226 }
 227
 228 #endif