16dc75fe5279e2c12bda13dcc4a1a13908de8596fDan Gohman//==- ScheduleDAGInstrs.h - MachineInstr Scheduling --------------*- C++ -*-==// 2343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 3343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// The LLVM Compiler Infrastructure 4343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 5343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// This file is distributed under the University of Illinois Open Source 6343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// License. See LICENSE.TXT for details. 7343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 8343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman//===----------------------------------------------------------------------===// 9343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 10343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// This file implements the ScheduleDAGInstrs class, which implements 11343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// scheduling for a MachineInstr-based dependency graph. 12343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 13343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman//===----------------------------------------------------------------------===// 14343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 156dc75fe5279e2c12bda13dcc4a1a13908de8596fDan Gohman#ifndef SCHEDULEDAGINSTRS_H 166dc75fe5279e2c12bda13dcc4a1a13908de8596fDan Gohman#define SCHEDULEDAGINSTRS_H 17343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 189e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman#include "llvm/CodeGen/MachineDominators.h" 199e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman#include "llvm/CodeGen/MachineLoopInfo.h" 20343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/CodeGen/ScheduleDAG.h" 219e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman#include "llvm/Support/Compiler.h" 2279ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman#include "llvm/Target/TargetRegisterInfo.h" 23fb2e752e4175920d0531f2afc93a23d0cdf4db14Evan Cheng#include "llvm/ADT/SmallSet.h" 248ae3ac7a8c2112ab739b4a0dc24f28b2bbb84117Andrew Trick#include "llvm/ADT/SparseSet.h" 259e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman#include <map> 26343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 27343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmannamespace llvm { 283f23744df4809eba94284e601e81489212c974d4Dan Gohman class MachineLoopInfo; 293f23744df4809eba94284e601e81489212c974d4Dan Gohman class MachineDominatorTree; 30b4566a999970b514d7c6973d99e293a6625d3f70Andrew Trick class LiveIntervals; 31006e1abf76148626fb38de1b643c2d31de7f08a7Andrew Trick class RegPressureTracker; 323f23744df4809eba94284e601e81489212c974d4Dan Gohman 339e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman /// LoopDependencies - This class analyzes loop-oriented register 349e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman /// dependencies, which are used to guide scheduling decisions. 359e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman /// For example, loop induction variable increments should be 369e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman /// scheduled as soon as possible after the variable's last use. 379e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman /// 38ed8a0ecaa82726c88d1962a7df060390eb6e9c22Andrew Trick class LoopDependencies { 399e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman const MachineDominatorTree &MDT; 409e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman 419e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman public: 429e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman typedef std::map<unsigned, std::pair<const MachineOperand *, unsigned> > 439e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman LoopDeps; 449e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman LoopDeps Deps; 459e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman 46a7542d5f870c5d98960d1676e23ac1d1d975d7e5Benjamin Kramer LoopDependencies(const MachineDominatorTree &mdt) : MDT(mdt) {} 479e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman 489e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman /// VisitLoop - Clear out any previous state and analyze the given loop. 499e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman /// 509e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman void VisitLoop(const MachineLoop *Loop) { 51e8deca83c157999062b4894163fd6b5023c5cf91Andrew Trick assert(Deps.empty() && "stale loop dependencies"); 52e8deca83c157999062b4894163fd6b5023c5cf91Andrew Trick 539e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman MachineBasicBlock *Header = Loop->getHeader(); 549e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman SmallSet<unsigned, 8> LoopLiveIns; 559e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman for (MachineBasicBlock::livein_iterator LI = Header->livein_begin(), 569e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman LE = Header->livein_end(); LI != LE; ++LI) 579e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman LoopLiveIns.insert(*LI); 589e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman 599e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman const MachineDomTreeNode *Node = MDT.getNode(Header); 609e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman const MachineBasicBlock *MBB = Node->getBlock(); 619e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman assert(Loop->contains(MBB) && 629e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman "Loop does not contain header!"); 639e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman VisitRegion(Node, MBB, Loop, LoopLiveIns); 649e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman } 659e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman 669e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman private: 679e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman void VisitRegion(const MachineDomTreeNode *Node, 689e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman const MachineBasicBlock *MBB, 699e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman const MachineLoop *Loop, 709e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman const SmallSet<unsigned, 8> &LoopLiveIns) { 719e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman unsigned Count = 0; 729e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end(); 732f2b25451b8fd6ab0625e78df9e5c710eba2d87fJim Grosbach I != E; ++I) { 749e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman const MachineInstr *MI = I; 752f2b25451b8fd6ab0625e78df9e5c710eba2d87fJim Grosbach if (MI->isDebugValue()) 762f2b25451b8fd6ab0625e78df9e5c710eba2d87fJim Grosbach continue; 779e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 789e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman const MachineOperand &MO = MI->getOperand(i); 799e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman if (!MO.isReg() || !MO.isUse()) 809e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman continue; 819e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman unsigned MOReg = MO.getReg(); 829e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman if (LoopLiveIns.count(MOReg)) 839e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman Deps.insert(std::make_pair(MOReg, std::make_pair(&MO, Count))); 849e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman } 852f2b25451b8fd6ab0625e78df9e5c710eba2d87fJim Grosbach ++Count; // Not every iteration due to dbg_value above. 869e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman } 879e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman 889e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman const std::vector<MachineDomTreeNode*> &Children = Node->getChildren(); 899e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman for (std::vector<MachineDomTreeNode*>::const_iterator I = 909e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman Children.begin(), E = Children.end(); I != E; ++I) { 919e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman const MachineDomTreeNode *ChildNode = *I; 929e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman MachineBasicBlock *ChildBlock = ChildNode->getBlock(); 939e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman if (Loop->contains(ChildBlock)) 949e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman VisitRegion(ChildNode, ChildBlock, Loop, LoopLiveIns); 959e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman } 969e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman } 979e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman }; 989e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman 99035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// An individual mapping from virtual register number to SUnit. 100035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick struct VReg2SUnit { 101035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick unsigned VirtReg; 102035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick SUnit *SU; 103035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick 104035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick VReg2SUnit(unsigned reg, SUnit *su): VirtReg(reg), SU(su) {} 105035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick 106c0ccb8bb17028fe0dda139c0972c0125d10e6053Andrew Trick unsigned getSparseSetIndex() const { 107035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick return TargetRegisterInfo::virtReg2Index(VirtReg); 108035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick } 109035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick }; 110035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick 111ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick /// Record a physical register access. 112ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick /// For non data-dependent uses, OpIdx == -1. 113ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick struct PhysRegSUOper { 114ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick SUnit *SU; 115ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick int OpIdx; 116ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick 117ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick PhysRegSUOper(SUnit *su, int op): SU(su), OpIdx(op) {} 118ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick }; 119ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick 120035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// Combine a SparseSet with a 1x1 vector to track physical registers. 121035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// The SparseSet allows iterating over the (few) live registers for quickly 122035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// comparing against a regmask or clearing the set. 123035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// 124035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// Storage for the map is allocated once for the pass. The map can be 125035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// cleared between scheduling regions without freeing unused entries. 126035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick class Reg2SUnitsMap { 127035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick SparseSet<unsigned> PhysRegSet; 128ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick std::vector<std::vector<PhysRegSUOper> > SUnits; 129035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick public: 130035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick typedef SparseSet<unsigned>::const_iterator const_iterator; 131035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick 132035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick // Allow iteration over register numbers (keys) in the map. If needed, we 133035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick // can provide an iterator over SUnits (values) as well. 134035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick const_iterator reg_begin() const { return PhysRegSet.begin(); } 135035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick const_iterator reg_end() const { return PhysRegSet.end(); } 136035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick 137035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// Initialize the map with the number of registers. 138035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// If the map is already large enough, no allocation occurs. 139035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// For simplicity we expect the map to be empty(). 140035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick void setRegLimit(unsigned Limit); 141035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick 142035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// Returns true if the map is empty. 143035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick bool empty() const { return PhysRegSet.empty(); } 144035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick 145035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// Clear the map without deallocating storage. 146035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick void clear(); 147035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick 148035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick bool contains(unsigned Reg) const { return PhysRegSet.count(Reg); } 149035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick 150035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// If this register is mapped, return its existing SUnits vector. 151035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// Otherwise map the register and return an empty SUnits vector. 152ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick std::vector<PhysRegSUOper> &operator[](unsigned Reg) { 153035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick bool New = PhysRegSet.insert(Reg).second; 154035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick assert((!New || SUnits[Reg].empty()) && "stale SUnits vector"); 155035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick (void)New; 156035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick return SUnits[Reg]; 157035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick } 158035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick 159035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// Erase an existing element without freeing memory. 160035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick void erase(unsigned Reg) { 161035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick PhysRegSet.erase(Reg); 162035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick SUnits[Reg].clear(); 163035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick } 164035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick }; 165035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick 166035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// Use SparseSet as a SparseMap by relying on the fact that it never 167035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// compares ValueT's, only unsigned keys. This allows the set to be cleared 168035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// between scheduling regions in constant time as long as ValueT does not 169035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick /// require a destructor. 170c0ccb8bb17028fe0dda139c0972c0125d10e6053Andrew Trick typedef SparseSet<VReg2SUnit, VirtReg2IndexFunctor> VReg2SUnitMap; 171035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick 1729e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman /// ScheduleDAGInstrs - A ScheduleDAG subclass for scheduling lists of 1739e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman /// MachineInstrs. 174ed8a0ecaa82726c88d1962a7df060390eb6e9c22Andrew Trick class ScheduleDAGInstrs : public ScheduleDAG { 17547c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick protected: 1763f23744df4809eba94284e601e81489212c974d4Dan Gohman const MachineLoopInfo &MLI; 1773f23744df4809eba94284e601e81489212c974d4Dan Gohman const MachineDominatorTree &MDT; 17838bdfc69cbe370ce5f623df4449afa32cda97422Evan Cheng const MachineFrameInfo *MFI; 1793ef1c8759a20167457eb7fd82ebcaffe7ccaa1d1Evan Cheng const InstrItineraryData *InstrItins; 1803f23744df4809eba94284e601e81489212c974d4Dan Gohman 181d790cada339d7af81650084b9bb6b2ad65566fbbAndrew Trick /// Live Intervals provides reaching defs in preRA scheduling. 182d790cada339d7af81650084b9bb6b2ad65566fbbAndrew Trick LiveIntervals *LIS; 183d790cada339d7af81650084b9bb6b2ad65566fbbAndrew Trick 1845e920d7c83c20474fc3470209869978628ccf8daAndrew Trick /// isPostRA flag indicates vregs cannot be present. 1855e920d7c83c20474fc3470209869978628ccf8daAndrew Trick bool IsPostRA; 1865e920d7c83c20474fc3470209869978628ccf8daAndrew Trick 187d790cada339d7af81650084b9bb6b2ad65566fbbAndrew Trick /// UnitLatencies (misnamed) flag avoids computing def-use latencies, using 188d790cada339d7af81650084b9bb6b2ad65566fbbAndrew Trick /// the def-side latency only. 189d790cada339d7af81650084b9bb6b2ad65566fbbAndrew Trick bool UnitLatencies; 190b4566a999970b514d7c6973d99e293a6625d3f70Andrew Trick 191007079201276368736fc893d4d5ec7aeeca00823Andrew Trick /// The standard DAG builder does not normally include terminators as DAG 192007079201276368736fc893d4d5ec7aeeca00823Andrew Trick /// nodes because it does not create the necessary dependencies to prevent 193007079201276368736fc893d4d5ec7aeeca00823Andrew Trick /// reordering. A specialized scheduler can overide 194007079201276368736fc893d4d5ec7aeeca00823Andrew Trick /// TargetInstrInfo::isSchedulingBoundary then enable this flag to indicate 195007079201276368736fc893d4d5ec7aeeca00823Andrew Trick /// it has taken responsibility for scheduling the terminator correctly. 196007079201276368736fc893d4d5ec7aeeca00823Andrew Trick bool CanHandleTerminators; 197007079201276368736fc893d4d5ec7aeeca00823Andrew Trick 19847c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick /// State specific to the current scheduling region. 199d790cada339d7af81650084b9bb6b2ad65566fbbAndrew Trick /// ------------------------------------------------ 20047c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 201d790cada339d7af81650084b9bb6b2ad65566fbbAndrew Trick /// The block in which to insert instructions 20247c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick MachineBasicBlock *BB; 20347c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 204cf46b5acfd6e0ab5d21ec3160cec195d0eb77b0bAndrew Trick /// The beginning of the range to be scheduled. 20568675c6c5b173021807e4e12cd250eeba63f6d0dAndrew Trick MachineBasicBlock::iterator RegionBegin; 20647c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 207cf46b5acfd6e0ab5d21ec3160cec195d0eb77b0bAndrew Trick /// The end of the range to be scheduled. 20868675c6c5b173021807e4e12cd250eeba63f6d0dAndrew Trick MachineBasicBlock::iterator RegionEnd; 20947c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 21068675c6c5b173021807e4e12cd250eeba63f6d0dAndrew Trick /// The index in BB of RegionEnd. 211cf46b5acfd6e0ab5d21ec3160cec195d0eb77b0bAndrew Trick unsigned EndIndex; 21247c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 213e75537a243858d8293832109e61bafc8484bb52aAndrew Trick /// After calling BuildSchedGraph, each machine instruction in the current 214e75537a243858d8293832109e61bafc8484bb52aAndrew Trick /// scheduling region is mapped to an SUnit. 215b4566a999970b514d7c6973d99e293a6625d3f70Andrew Trick DenseMap<MachineInstr*, SUnit*> MISUnitMap; 216b4566a999970b514d7c6973d99e293a6625d3f70Andrew Trick 217d790cada339d7af81650084b9bb6b2ad65566fbbAndrew Trick /// State internal to DAG building. 218d790cada339d7af81650084b9bb6b2ad65566fbbAndrew Trick /// ------------------------------- 2197ebcaf4cf929ef041ae6c9c07b897e4d0aa8ad06Andrew Trick 220702d489a959b202ab06ce4bafa0bcb1fbfd2c3e4Andrew Trick /// Defs, Uses - Remember where defs and uses of each register are as we 221702d489a959b202ab06ce4bafa0bcb1fbfd2c3e4Andrew Trick /// iterate upward through the instructions. This is allocated here instead 222702d489a959b202ab06ce4bafa0bcb1fbfd2c3e4Andrew Trick /// of inside BuildSchedGraph to avoid the need for it to be initialized and 223702d489a959b202ab06ce4bafa0bcb1fbfd2c3e4Andrew Trick /// destructed for each block. 224702d489a959b202ab06ce4bafa0bcb1fbfd2c3e4Andrew Trick Reg2SUnitsMap Defs; 225702d489a959b202ab06ce4bafa0bcb1fbfd2c3e4Andrew Trick Reg2SUnitsMap Uses; 2264563bbaba7fad4403acf0236cbd75805c68f2a90Andrew Trick 227702d489a959b202ab06ce4bafa0bcb1fbfd2c3e4Andrew Trick /// Track the last instructon in this region defining each virtual register. 2288ae3ac7a8c2112ab739b4a0dc24f28b2bbb84117Andrew Trick VReg2SUnitMap VRegDefs; 2293c58ba8ea7ec097d69d7f7be5930a4a4d7405a18Andrew Trick 23079ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman /// PendingLoads - Remember where unknown loads are after the most recent 23179ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman /// unknown store, as we iterate. As with Defs and Uses, this is here 23279ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman /// to minimize construction/destruction. 23379ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman std::vector<SUnit *> PendingLoads; 23479ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman 2359e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman /// LoopRegs - Track which registers are used for loop-carried dependencies. 2369e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman /// 2379e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman LoopDependencies LoopRegs; 2389e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman 239d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer /// DbgValues - Remember instruction that precedes DBG_VALUE. 240d790cada339d7af81650084b9bb6b2ad65566fbbAndrew Trick /// These are generated by buildSchedGraph but persist so they can be 241d790cada339d7af81650084b9bb6b2ad65566fbbAndrew Trick /// referenced when emitting the final schedule. 2424563bbaba7fad4403acf0236cbd75805c68f2a90Andrew Trick typedef std::vector<std::pair<MachineInstr *, MachineInstr *> > 243e29e8e100ea38be1771e5f010a5511cbb990d515Devang Patel DbgValueVector; 244e29e8e100ea38be1771e5f010a5511cbb990d515Devang Patel DbgValueVector DbgValues; 245e29e8e100ea38be1771e5f010a5511cbb990d515Devang Patel MachineInstr *FirstDbgValue; 246e29e8e100ea38be1771e5f010a5511cbb990d515Devang Patel 247343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman public: 24879ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman explicit ScheduleDAGInstrs(MachineFunction &mf, 24979ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman const MachineLoopInfo &mli, 2505e920d7c83c20474fc3470209869978628ccf8daAndrew Trick const MachineDominatorTree &mdt, 251b4566a999970b514d7c6973d99e293a6625d3f70Andrew Trick bool IsPostRAFlag, 252b4566a999970b514d7c6973d99e293a6625d3f70Andrew Trick LiveIntervals *LIS = 0); 253343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 254343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual ~ScheduleDAGInstrs() {} 255343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 25647c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick /// begin - Return an iterator to the top of the current scheduling region. 25768675c6c5b173021807e4e12cd250eeba63f6d0dAndrew Trick MachineBasicBlock::iterator begin() const { return RegionBegin; } 25847c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 25947c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick /// end - Return an iterator to the bottom of the current scheduling region. 26068675c6c5b173021807e4e12cd250eeba63f6d0dAndrew Trick MachineBasicBlock::iterator end() const { return RegionEnd; } 26147c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 2627afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick /// newSUnit - Creates a new SUnit and return a ptr to it. 263035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick SUnit *newSUnit(MachineInstr *MI); 264343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 2657afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick /// getSUnit - Return an existing SUnit for this MI, or NULL. 2667afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick SUnit *getSUnit(MachineInstr *MI) const; 2677afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick 268953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick /// startBlock - Prepare to perform scheduling in the given block. 269953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick virtual void startBlock(MachineBasicBlock *BB); 270b4566a999970b514d7c6973d99e293a6625d3f70Andrew Trick 271953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick /// finishBlock - Clean up after scheduling in the given block. 272953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick virtual void finishBlock(); 27347c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 27447c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick /// Initialize the scheduler state for the next scheduling region. 27547c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick virtual void enterRegion(MachineBasicBlock *bb, 27647c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick MachineBasicBlock::iterator begin, 27747c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick MachineBasicBlock::iterator end, 27847c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick unsigned endcount); 27947c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 28047c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick /// Notify that the scheduler has finished scheduling the current region. 28147c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick virtual void exitRegion(); 28247ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman 283953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick /// buildSchedGraph - Build SUnits from the MachineBasicBlock that we are 284343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// input. 285006e1abf76148626fb38de1b643c2d31de7f08a7Andrew Trick void buildSchedGraph(AliasAnalysis *AA, RegPressureTracker *RPTracker = 0); 286343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 287953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick /// addSchedBarrierDeps - Add dependencies from instructions in the current 288ec6906ba47d6d32cc817e85eddb87b320d6ae18cEvan Cheng /// list of instructions being scheduled to scheduling barrier. We want to 289ec6906ba47d6d32cc817e85eddb87b320d6ae18cEvan Cheng /// make sure instructions which define registers that are either used by 290ec6906ba47d6d32cc817e85eddb87b320d6ae18cEvan Cheng /// the terminator or are live-out are properly scheduled. This is 291ec6906ba47d6d32cc817e85eddb87b320d6ae18cEvan Cheng /// especially important when the definition latency of the return value(s) 292ec6906ba47d6d32cc817e85eddb87b320d6ae18cEvan Cheng /// are too high to be hidden by the branch or when the liveout registers 293ec6906ba47d6d32cc817e85eddb87b320d6ae18cEvan Cheng /// used by instructions in the fallthrough block. 294953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick void addSchedBarrierDeps(); 295ec6906ba47d6d32cc817e85eddb87b320d6ae18cEvan Cheng 296953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick /// computeLatency - Compute node latency. 297c8c2827993204207ca70a93f62f233fbe81b97efDan Gohman /// 298953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick virtual void computeLatency(SUnit *SU); 299c8c2827993204207ca70a93f62f233fbe81b97efDan Gohman 300953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick /// schedule - Order nodes according to selected style, filling 301343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// in the Sequence member. 302343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 303953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick /// Typically, a scheduling algorithm will implement schedule() without 3046fd7dd6ba57c1b5ba1f12e7e9da574b9dbd8ae09Andrew Trick /// overriding enterRegion() or exitRegion(). 305953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick virtual void schedule() = 0; 306343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 307830da405fa32ab4f2a8378a658e1429a9ffd4d65Andrew Trick /// finalizeSchedule - Allow targets to perform final scheduling actions at 308830da405fa32ab4f2a8378a658e1429a9ffd4d65Andrew Trick /// the level of the whole MachineFunction. By default does nothing. 309830da405fa32ab4f2a8378a658e1429a9ffd4d65Andrew Trick virtual void finalizeSchedule() {} 310830da405fa32ab4f2a8378a658e1429a9ffd4d65Andrew Trick 311343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual void dumpNode(const SUnit *SU) const; 312343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 3137b58ae77acb63db29116e548393ddd2127909425Andrew Trick /// Return a label for a DAG node that points to an instruction. 314343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual std::string getGraphNodeLabel(const SUnit *SU) const; 3157ebcaf4cf929ef041ae6c9c07b897e4d0aa8ad06Andrew Trick 3167b58ae77acb63db29116e548393ddd2127909425Andrew Trick /// Return a label for the region of code covered by the DAG. 31756b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick virtual std::string getDAGName() const; 31856b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick 3197ebcaf4cf929ef041ae6c9c07b897e4d0aa8ad06Andrew Trick protected: 320b4566a999970b514d7c6973d99e293a6625d3f70Andrew Trick void initSUnits(); 321ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx); 3227ebcaf4cf929ef041ae6c9c07b897e4d0aa8ad06Andrew Trick void addPhysRegDeps(SUnit *SU, unsigned OperIdx); 3233c58ba8ea7ec097d69d7f7be5930a4a4d7405a18Andrew Trick void addVRegDefDeps(SUnit *SU, unsigned OperIdx); 3243c58ba8ea7ec097d69d7f7be5930a4a4d7405a18Andrew Trick void addVRegUseDeps(SUnit *SU, unsigned OperIdx); 325343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman }; 326035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick 3277afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick /// newSUnit - Creates a new SUnit and return a ptr to it. 328035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick inline SUnit *ScheduleDAGInstrs::newSUnit(MachineInstr *MI) { 329035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick#ifndef NDEBUG 330035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick const SUnit *Addr = SUnits.empty() ? 0 : &SUnits[0]; 331035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick#endif 332035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick SUnits.push_back(SUnit(MI, (unsigned)SUnits.size())); 333035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick assert((Addr == 0 || Addr == &SUnits[0]) && 334035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick "SUnits std::vector reallocated on the fly!"); 335035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick SUnits.back().OrigNode = &SUnits.back(); 336035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick return &SUnits.back(); 337035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick } 3387afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick 3397afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick /// getSUnit - Return an existing SUnit for this MI, or NULL. 3407afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick inline SUnit *ScheduleDAGInstrs::getSUnit(MachineInstr *MI) const { 3417afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick DenseMap<MachineInstr*, SUnit*>::const_iterator I = MISUnitMap.find(MI); 3427afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick if (I == MISUnitMap.end()) 3437afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick return 0; 3447afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick return I->second; 3457afcda0c582f57a46de32e88ad6c6d5b25d513ceAndrew Trick } 346035ec40eaf1dcd8f4809fb183098259f2dec75b9Andrew Trick} // namespace llvm 347343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 348343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#endif 349