LLVM API Documentation
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