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 "llvm/ADT/SparseSet.h" 25 #include <map> 26 27 namespace llvm { 28 class MachineLoopInfo; 29 class MachineDominatorTree; 30 class LiveIntervals; 31 class RegPressureTracker; 32 33 /// LoopDependencies - This class analyzes loop-oriented register 34 /// dependencies, which are used to guide scheduling decisions. 35 /// For example, loop induction variable increments should be 36 /// scheduled as soon as possible after the variable's last use. 37 /// 38 class LoopDependencies { 39 const MachineDominatorTree &MDT; 40 41 public: 42 typedef std::map<unsigned, std::pair<const MachineOperand *, unsigned> > 43 LoopDeps; 44 LoopDeps Deps; 45 46 LoopDependencies(const MachineDominatorTree &mdt) : MDT(mdt) {} 47 48 /// VisitLoop - Clear out any previous state and analyze the given loop. 49 /// 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: 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 /// An individual mapping from virtual register number to SUnit. 100 struct VReg2SUnit { 101 unsigned VirtReg; 102 SUnit *SU; 103 104 VReg2SUnit(unsigned reg, SUnit *su): VirtReg(reg), SU(su) {} 105 106 unsigned getSparseSetIndex() const { 107 return TargetRegisterInfo::virtReg2Index(VirtReg); 108 } 109 }; 110 111 /// Record a physical register access. 112 /// For non data-dependent uses, OpIdx == -1. 113 struct PhysRegSUOper { 114 SUnit *SU; 115 int OpIdx; 116 117 PhysRegSUOper(SUnit *su, int op): SU(su), OpIdx(op) {} 118 }; 119 120 /// Combine a SparseSet with a 1x1 vector to track physical registers. 121 /// The SparseSet allows iterating over the (few) live registers for quickly 122 /// comparing against a regmask or clearing the set. 123 /// 124 /// Storage for the map is allocated once for the pass. The map can be 125 /// cleared between scheduling regions without freeing unused entries. 126 class Reg2SUnitsMap { 127 SparseSet<unsigned> PhysRegSet; 128 std::vector<std::vector<PhysRegSUOper> > SUnits; 129 public: 130 typedef SparseSet<unsigned>::const_iterator const_iterator; 131 132 // Allow iteration over register numbers (keys) in the map. If needed, we 133 // can provide an iterator over SUnits (values) as well. 134 const_iterator reg_begin() const { return PhysRegSet.begin(); } 135 const_iterator reg_end() const { return PhysRegSet.end(); } 136 137 /// Initialize the map with the number of registers. 138 /// If the map is already large enough, no allocation occurs. 139 /// For simplicity we expect the map to be empty(). 140 void setRegLimit(unsigned Limit); 141 142 /// Returns true if the map is empty. 143 bool empty() const { return PhysRegSet.empty(); } 144 145 /// Clear the map without deallocating storage. 146 void clear(); 147 148 bool contains(unsigned Reg) const { return PhysRegSet.count(Reg); } 149 150 /// If this register is mapped, return its existing SUnits vector. 151 /// Otherwise map the register and return an empty SUnits vector. 152 std::vector<PhysRegSUOper> &operator[](unsigned Reg) { 153 bool New = PhysRegSet.insert(Reg).second; 154 assert((!New || SUnits[Reg].empty()) && "stale SUnits vector"); 155 (void)New; 156 return SUnits[Reg]; 157 } 158 159 /// Erase an existing element without freeing memory. 160 void erase(unsigned Reg) { 161 PhysRegSet.erase(Reg); 162 SUnits[Reg].clear(); 163 } 164 }; 165 166 /// Use SparseSet as a SparseMap by relying on the fact that it never 167 /// compares ValueT's, only unsigned keys. This allows the set to be cleared 168 /// between scheduling regions in constant time as long as ValueT does not 169 /// require a destructor. 170 typedef SparseSet<VReg2SUnit, VirtReg2IndexFunctor> VReg2SUnitMap; 171 172 /// ScheduleDAGInstrs - A ScheduleDAG subclass for scheduling lists of 173 /// MachineInstrs. 174 class ScheduleDAGInstrs : public ScheduleDAG { 175 protected: 176 const MachineLoopInfo &MLI; 177 const MachineDominatorTree &MDT; 178 const MachineFrameInfo *MFI; 179 const InstrItineraryData *InstrItins; 180 181 /// Live Intervals provides reaching defs in preRA scheduling. 182 LiveIntervals *LIS; 183 184 /// isPostRA flag indicates vregs cannot be present. 185 bool IsPostRA; 186 187 /// UnitLatencies (misnamed) flag avoids computing def-use latencies, using 188 /// the def-side latency only. 189 bool UnitLatencies; 190 191 /// The standard DAG builder does not normally include terminators as DAG 192 /// nodes because it does not create the necessary dependencies to prevent 193 /// reordering. A specialized scheduler can overide 194 /// TargetInstrInfo::isSchedulingBoundary then enable this flag to indicate 195 /// it has taken responsibility for scheduling the terminator correctly. 196 bool CanHandleTerminators; 197 198 /// State specific to the current scheduling region. 199 /// ------------------------------------------------ 200 201 /// The block in which to insert instructions 202 MachineBasicBlock *BB; 203 204 /// The beginning of the range to be scheduled. 205 MachineBasicBlock::iterator RegionBegin; 206 207 /// The end of the range to be scheduled. 208 MachineBasicBlock::iterator RegionEnd; 209 210 /// The index in BB of RegionEnd. 211 unsigned EndIndex; 212 213 /// After calling BuildSchedGraph, each machine instruction in the current 214 /// scheduling region is mapped to an SUnit. 215 DenseMap<MachineInstr*, SUnit*> MISUnitMap; 216 217 /// State internal to DAG building. 218 /// ------------------------------- 219 220 /// Defs, Uses - Remember where defs and uses of each register are as we 221 /// iterate upward through the instructions. This is allocated here instead 222 /// of inside BuildSchedGraph to avoid the need for it to be initialized and 223 /// destructed for each block. 224 Reg2SUnitsMap Defs; 225 Reg2SUnitsMap Uses; 226 227 /// Track the last instructon in this region defining each virtual register. 228 VReg2SUnitMap VRegDefs; 229 230 /// PendingLoads - Remember where unknown loads are after the most recent 231 /// unknown store, as we iterate. As with Defs and Uses, this is here 232 /// to minimize construction/destruction. 233 std::vector<SUnit *> PendingLoads; 234 235 /// LoopRegs - Track which registers are used for loop-carried dependencies. 236 /// 237 LoopDependencies LoopRegs; 238 239 /// DbgValues - Remember instruction that precedes DBG_VALUE. 240 /// These are generated by buildSchedGraph but persist so they can be 241 /// referenced when emitting the final schedule. 242 typedef std::vector<std::pair<MachineInstr *, MachineInstr *> > 243 DbgValueVector; 244 DbgValueVector DbgValues; 245 MachineInstr *FirstDbgValue; 246 247 public: 248 explicit ScheduleDAGInstrs(MachineFunction &mf, 249 const MachineLoopInfo &mli, 250 const MachineDominatorTree &mdt, 251 bool IsPostRAFlag, 252 LiveIntervals *LIS = 0); 253 254 virtual ~ScheduleDAGInstrs() {} 255 256 /// begin - Return an iterator to the top of the current scheduling region. 257 MachineBasicBlock::iterator begin() const { return RegionBegin; } 258 259 /// end - Return an iterator to the bottom of the current scheduling region. 260 MachineBasicBlock::iterator end() const { return RegionEnd; } 261 262 /// newSUnit - Creates a new SUnit and return a ptr to it. 263 SUnit *newSUnit(MachineInstr *MI); 264 265 /// getSUnit - Return an existing SUnit for this MI, or NULL. 266 SUnit *getSUnit(MachineInstr *MI) const; 267 268 /// startBlock - Prepare to perform scheduling in the given block. 269 virtual void startBlock(MachineBasicBlock *BB); 270 271 /// finishBlock - Clean up after scheduling in the given block. 272 virtual void finishBlock(); 273 274 /// Initialize the scheduler state for the next scheduling region. 275 virtual void enterRegion(MachineBasicBlock *bb, 276 MachineBasicBlock::iterator begin, 277 MachineBasicBlock::iterator end, 278 unsigned endcount); 279 280 /// Notify that the scheduler has finished scheduling the current region. 281 virtual void exitRegion(); 282 283 /// buildSchedGraph - Build SUnits from the MachineBasicBlock that we are 284 /// input. 285 void buildSchedGraph(AliasAnalysis *AA, RegPressureTracker *RPTracker = 0); 286 287 /// addSchedBarrierDeps - Add dependencies from instructions in the current 288 /// list of instructions being scheduled to scheduling barrier. We want to 289 /// make sure instructions which define registers that are either used by 290 /// the terminator or are live-out are properly scheduled. This is 291 /// especially important when the definition latency of the return value(s) 292 /// are too high to be hidden by the branch or when the liveout registers 293 /// used by instructions in the fallthrough block. 294 void addSchedBarrierDeps(); 295 296 /// computeLatency - Compute node latency. 297 /// 298 virtual void computeLatency(SUnit *SU); 299 300 /// schedule - Order nodes according to selected style, filling 301 /// in the Sequence member. 302 /// 303 /// Typically, a scheduling algorithm will implement schedule() without 304 /// overriding enterRegion() or exitRegion(). 305 virtual void schedule() = 0; 306 307 /// finalizeSchedule - Allow targets to perform final scheduling actions at 308 /// the level of the whole MachineFunction. By default does nothing. 309 virtual void finalizeSchedule() {} 310 311 virtual void dumpNode(const SUnit *SU) const; 312 313 /// Return a label for a DAG node that points to an instruction. 314 virtual std::string getGraphNodeLabel(const SUnit *SU) const; 315 316 /// Return a label for the region of code covered by the DAG. 317 virtual std::string getDAGName() const; 318 319 protected: 320 void initSUnits(); 321 void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx); 322 void addPhysRegDeps(SUnit *SU, unsigned OperIdx); 323 void addVRegDefDeps(SUnit *SU, unsigned OperIdx); 324 void addVRegUseDeps(SUnit *SU, unsigned OperIdx); 325 }; 326 327 /// newSUnit - Creates a new SUnit and return a ptr to it. 328 inline SUnit *ScheduleDAGInstrs::newSUnit(MachineInstr *MI) { 329 #ifndef NDEBUG 330 const SUnit *Addr = SUnits.empty() ? 0 : &SUnits[0]; 331 #endif 332 SUnits.push_back(SUnit(MI, (unsigned)SUnits.size())); 333 assert((Addr == 0 || Addr == &SUnits[0]) && 334 "SUnits std::vector reallocated on the fly!"); 335 SUnits.back().OrigNode = &SUnits.back(); 336 return &SUnits.back(); 337 } 338 339 /// getSUnit - Return an existing SUnit for this MI, or NULL. 340 inline SUnit *ScheduleDAGInstrs::getSUnit(MachineInstr *MI) const { 341 DenseMap<MachineInstr*, SUnit*>::const_iterator I = MISUnitMap.find(MI); 342 if (I == MISUnitMap.end()) 343 return 0; 344 return I->second; 345 } 346 } // namespace llvm 347 348 #endif 349