LLVM API Documentation

ScheduleDAGInstrs.h

Go to the documentation of this file.
00001 //==- ScheduleDAGInstrs.h - MachineInstr Scheduling --------------*- C++ -*-==//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the ScheduleDAGInstrs class, which implements
00011 // scheduling for a MachineInstr-based dependency graph.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #ifndef SCHEDULEDAGINSTRS_H
00016 #define SCHEDULEDAGINSTRS_H
00017 
00018 #include "llvm/ADT/SmallSet.h"
00019 #include "llvm/CodeGen/MachineDominators.h"
00020 #include "llvm/CodeGen/MachineLoopInfo.h"
00021 #include "llvm/CodeGen/ScheduleDAG.h"
00022 #include "llvm/Support/Compiler.h"
00023 #include "llvm/Target/TargetRegisterInfo.h"
00024 #include <map>
00025 
00026 namespace llvm {
00027   class MachineLoopInfo;
00028   class MachineDominatorTree;
00029 
00030   /// LoopDependencies - This class analyzes loop-oriented register
00031   /// dependencies, which are used to guide scheduling decisions.
00032   /// For example, loop induction variable increments should be
00033   /// scheduled as soon as possible after the variable's last use.
00034   ///
00035   class VISIBILITY_HIDDEN LoopDependencies {
00036     const MachineLoopInfo &MLI;
00037     const MachineDominatorTree &MDT;
00038 
00039   public:
00040     typedef std::map<unsigned, std::pair<const MachineOperand *, unsigned> >
00041       LoopDeps;
00042     LoopDeps Deps;
00043 
00044     LoopDependencies(const MachineLoopInfo &mli,
00045                      const MachineDominatorTree &mdt) :
00046       MLI(mli), MDT(mdt) {}
00047 
00048     /// VisitLoop - Clear out any previous state and analyze the given loop.
00049     ///
00050     void VisitLoop(const MachineLoop *Loop) {
00051       Deps.clear();
00052       MachineBasicBlock *Header = Loop->getHeader();
00053       SmallSet<unsigned, 8> LoopLiveIns;
00054       for (MachineBasicBlock::livein_iterator LI = Header->livein_begin(),
00055            LE = Header->livein_end(); LI != LE; ++LI)
00056         LoopLiveIns.insert(*LI);
00057 
00058       const MachineDomTreeNode *Node = MDT.getNode(Header);
00059       const MachineBasicBlock *MBB = Node->getBlock();
00060       assert(Loop->contains(MBB) &&
00061              "Loop does not contain header!");
00062       VisitRegion(Node, MBB, Loop, LoopLiveIns);
00063     }
00064 
00065   private:
00066     void VisitRegion(const MachineDomTreeNode *Node,
00067                      const MachineBasicBlock *MBB,
00068                      const MachineLoop *Loop,
00069                      const SmallSet<unsigned, 8> &LoopLiveIns) {
00070       unsigned Count = 0;
00071       for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end();
00072            I != E; ++I, ++Count) {
00073         const MachineInstr *MI = I;
00074         for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
00075           const MachineOperand &MO = MI->getOperand(i);
00076           if (!MO.isReg() || !MO.isUse())
00077             continue;
00078           unsigned MOReg = MO.getReg();
00079           if (LoopLiveIns.count(MOReg))
00080             Deps.insert(std::make_pair(MOReg, std::make_pair(&MO, Count)));
00081         }
00082       }
00083 
00084       const std::vector<MachineDomTreeNode*> &Children = Node->getChildren();
00085       for (std::vector<MachineDomTreeNode*>::const_iterator I =
00086            Children.begin(), E = Children.end(); I != E; ++I) {
00087         const MachineDomTreeNode *ChildNode = *I;
00088         MachineBasicBlock *ChildBlock = ChildNode->getBlock();
00089         if (Loop->contains(ChildBlock))
00090           VisitRegion(ChildNode, ChildBlock, Loop, LoopLiveIns);
00091       }
00092     }
00093   };
00094 
00095   /// ScheduleDAGInstrs - A ScheduleDAG subclass for scheduling lists of
00096   /// MachineInstrs.
00097   class VISIBILITY_HIDDEN ScheduleDAGInstrs : public ScheduleDAG {
00098     const MachineLoopInfo &MLI;
00099     const MachineDominatorTree &MDT;
00100 
00101     /// Defs, Uses - Remember where defs and uses of each physical register
00102     /// are as we iterate upward through the instructions. This is allocated
00103     /// here instead of inside BuildSchedGraph to avoid the need for it to be
00104     /// initialized and destructed for each block.
00105     std::vector<SUnit *> Defs[TargetRegisterInfo::FirstVirtualRegister];
00106     std::vector<SUnit *> Uses[TargetRegisterInfo::FirstVirtualRegister];
00107 
00108     /// PendingLoads - Remember where unknown loads are after the most recent
00109     /// unknown store, as we iterate. As with Defs and Uses, this is here
00110     /// to minimize construction/destruction.
00111     std::vector<SUnit *> PendingLoads;
00112 
00113     /// LoopRegs - Track which registers are used for loop-carried dependencies.
00114     ///
00115     LoopDependencies LoopRegs;
00116 
00117     /// LoopLiveInRegs - Track which regs are live into a loop, to help guide
00118     /// back-edge-aware scheduling.
00119     ///
00120     SmallSet<unsigned, 8> LoopLiveInRegs;
00121 
00122   public:
00123     MachineBasicBlock *BB;                // Current basic block
00124     MachineBasicBlock::iterator Begin;    // The beginning of the range to
00125                                           // be scheduled. The range extends
00126                                           // to InsertPos.
00127     unsigned InsertPosIndex;              // The index in BB of InsertPos.
00128 
00129     explicit ScheduleDAGInstrs(MachineFunction &mf,
00130                                const MachineLoopInfo &mli,
00131                                const MachineDominatorTree &mdt);
00132 
00133     virtual ~ScheduleDAGInstrs() {}
00134 
00135     /// NewSUnit - Creates a new SUnit and return a ptr to it.
00136     ///
00137     SUnit *NewSUnit(MachineInstr *MI) {
00138 #ifndef NDEBUG
00139       const SUnit *Addr = SUnits.empty() ? 0 : &SUnits[0];
00140 #endif
00141       SUnits.push_back(SUnit(MI, (unsigned)SUnits.size()));
00142       assert((Addr == 0 || Addr == &SUnits[0]) &&
00143              "SUnits std::vector reallocated on the fly!");
00144       SUnits.back().OrigNode = &SUnits.back();
00145       return &SUnits.back();
00146     }
00147 
00148     /// Run - perform scheduling.
00149     ///
00150     void Run(MachineBasicBlock *bb,
00151              MachineBasicBlock::iterator begin,
00152              MachineBasicBlock::iterator end,
00153              unsigned endindex);
00154 
00155     /// BuildSchedGraph - Build SUnits from the MachineBasicBlock that we are
00156     /// input.
00157     virtual void BuildSchedGraph();
00158 
00159     /// ComputeLatency - Compute node latency.
00160     ///
00161     virtual void ComputeLatency(SUnit *SU);
00162 
00163     /// ComputeOperandLatency - Override dependence edge latency using
00164     /// operand use/def information
00165     ///
00166     virtual void ComputeOperandLatency(SUnit *Def, SUnit *Use,
00167                                        SDep& dep) const;
00168 
00169     virtual MachineBasicBlock *EmitSchedule();
00170 
00171     /// StartBlock - Prepare to perform scheduling in the given block.
00172     ///
00173     virtual void StartBlock(MachineBasicBlock *BB);
00174 
00175     /// Schedule - Order nodes according to selected style, filling
00176     /// in the Sequence member.
00177     ///
00178     virtual void Schedule() = 0;
00179 
00180     /// FinishBlock - Clean up after scheduling in the given block.
00181     ///
00182     virtual void FinishBlock();
00183 
00184     virtual void dumpNode(const SUnit *SU) const;
00185 
00186     virtual std::string getGraphNodeLabel(const SUnit *SU) const;
00187   };
00188 }
00189 
00190 #endif