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