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