X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FScheduleDAGInstrs.h;h=00dd8f9a633e2c23df17f003fabcfafc2bedd114;hb=0bea7854271564707d59a10339e9f302155d0b73;hp=4fee108cd2be0d5991821f4e6b3b1c914d3f159f;hpb=007079201276368736fc893d4d5ec7aeeca00823;p=oota-llvm.git diff --git a/include/llvm/CodeGen/ScheduleDAGInstrs.h b/include/llvm/CodeGen/ScheduleDAGInstrs.h index 4fee108cd2b..00dd8f9a633 100644 --- a/include/llvm/CodeGen/ScheduleDAGInstrs.h +++ b/include/llvm/CodeGen/ScheduleDAGInstrs.h @@ -12,91 +12,23 @@ // //===----------------------------------------------------------------------===// -#ifndef SCHEDULEDAGINSTRS_H -#define SCHEDULEDAGINSTRS_H +#ifndef LLVM_CODEGEN_SCHEDULEDAGINSTRS_H +#define LLVM_CODEGEN_SCHEDULEDAGINSTRS_H -#include "llvm/CodeGen/MachineDominators.h" -#include "llvm/CodeGen/MachineLoopInfo.h" +#include "llvm/ADT/SparseMultiSet.h" +#include "llvm/ADT/SparseSet.h" #include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/CodeGen/TargetSchedule.h" #include "llvm/Support/Compiler.h" #include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/ADT/SmallSet.h" -#include "llvm/ADT/SparseSet.h" -#include namespace llvm { + class MachineFrameInfo; class MachineLoopInfo; class MachineDominatorTree; class LiveIntervals; - - /// LoopDependencies - This class analyzes loop-oriented register - /// dependencies, which are used to guide scheduling decisions. - /// For example, loop induction variable increments should be - /// scheduled as soon as possible after the variable's last use. - /// - class LoopDependencies { - const MachineLoopInfo &MLI; - const MachineDominatorTree &MDT; - - public: - typedef std::map > - LoopDeps; - LoopDeps Deps; - - LoopDependencies(const MachineLoopInfo &mli, - const MachineDominatorTree &mdt) : - MLI(mli), MDT(mdt) {} - - /// VisitLoop - Clear out any previous state and analyze the given loop. - /// - void VisitLoop(const MachineLoop *Loop) { - assert(Deps.empty() && "stale loop dependencies"); - - MachineBasicBlock *Header = Loop->getHeader(); - SmallSet LoopLiveIns; - for (MachineBasicBlock::livein_iterator LI = Header->livein_begin(), - LE = Header->livein_end(); LI != LE; ++LI) - LoopLiveIns.insert(*LI); - - const MachineDomTreeNode *Node = MDT.getNode(Header); - const MachineBasicBlock *MBB = Node->getBlock(); - assert(Loop->contains(MBB) && - "Loop does not contain header!"); - VisitRegion(Node, MBB, Loop, LoopLiveIns); - } - - private: - void VisitRegion(const MachineDomTreeNode *Node, - const MachineBasicBlock *MBB, - const MachineLoop *Loop, - const SmallSet &LoopLiveIns) { - unsigned Count = 0; - for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end(); - I != E; ++I) { - const MachineInstr *MI = I; - if (MI->isDebugValue()) - continue; - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - const MachineOperand &MO = MI->getOperand(i); - if (!MO.isReg() || !MO.isUse()) - continue; - unsigned MOReg = MO.getReg(); - if (LoopLiveIns.count(MOReg)) - Deps.insert(std::make_pair(MOReg, std::make_pair(&MO, Count))); - } - ++Count; // Not every iteration due to dbg_value above. - } - - const std::vector &Children = Node->getChildren(); - for (std::vector::const_iterator I = - Children.begin(), E = Children.end(); I != E; ++I) { - const MachineDomTreeNode *ChildNode = *I; - MachineBasicBlock *ChildBlock = ChildNode->getBlock(); - if (Loop->contains(ChildBlock)) - VisitRegion(ChildNode, ChildBlock, Loop, LoopLiveIns); - } - } - }; + class RegPressureTracker; + class PressureDiffs; /// An individual mapping from virtual register number to SUnit. struct VReg2SUnit { @@ -105,85 +37,63 @@ namespace llvm { VReg2SUnit(unsigned reg, SUnit *su): VirtReg(reg), SU(su) {} - unsigned getSparseSetKey() const { + unsigned getSparseSetIndex() const { return TargetRegisterInfo::virtReg2Index(VirtReg); } }; - /// Combine a SparseSet with a 1x1 vector to track physical registers. - /// The SparseSet allows iterating over the (few) live registers for quickly - /// comparing against a regmask or clearing the set. - /// - /// Storage for the map is allocated once for the pass. The map can be - /// cleared between scheduling regions without freeing unused entries. - class Reg2SUnitsMap { - SparseSet PhysRegSet; - std::vector > SUnits; - public: - typedef SparseSet::const_iterator const_iterator; - - // Allow iteration over register numbers (keys) in the map. If needed, we - // can provide an iterator over SUnits (values) as well. - const_iterator reg_begin() const { return PhysRegSet.begin(); } - const_iterator reg_end() const { return PhysRegSet.end(); } - - /// Initialize the map with the number of registers. - /// If the map is already large enough, no allocation occurs. - /// For simplicity we expect the map to be empty(). - void setRegLimit(unsigned Limit); - - /// Returns true if the map is empty. - bool empty() const { return PhysRegSet.empty(); } - - /// Clear the map without deallocating storage. - void clear(); - - bool contains(unsigned Reg) const { return PhysRegSet.count(Reg); } + /// Record a physical register access. + /// For non-data-dependent uses, OpIdx == -1. + struct PhysRegSUOper { + SUnit *SU; + int OpIdx; + unsigned Reg; - /// If this register is mapped, return its existing SUnits vector. - /// Otherwise map the register and return an empty SUnits vector. - std::vector &operator[](unsigned Reg) { - bool New = PhysRegSet.insert(Reg).second; - assert((!New || SUnits[Reg].empty()) && "stale SUnits vector"); - (void)New; - return SUnits[Reg]; - } + PhysRegSUOper(SUnit *su, int op, unsigned R): SU(su), OpIdx(op), Reg(R) {} - /// Erase an existing element without freeing memory. - void erase(unsigned Reg) { - PhysRegSet.erase(Reg); - SUnits[Reg].clear(); - } + unsigned getSparseSetIndex() const { return Reg; } }; + /// Use a SparseMultiSet to track physical registers. Storage is only + /// allocated once for the pass. It can be cleared in constant time and reused + /// without any frees. + typedef SparseMultiSet, uint16_t> + Reg2SUnitsMap; + /// Use SparseSet as a SparseMap by relying on the fact that it never /// compares ValueT's, only unsigned keys. This allows the set to be cleared /// between scheduling regions in constant time as long as ValueT does not /// require a destructor. - typedef SparseSet VReg2SUnitMap; + typedef SparseSet VReg2SUnitMap; + + /// Track local uses of virtual registers. These uses are gathered by the DAG + /// builder and may be consulted by the scheduler to avoid iterating an entire + /// vreg use list. + typedef SparseMultiSet VReg2UseMap; /// ScheduleDAGInstrs - A ScheduleDAG subclass for scheduling lists of /// MachineInstrs. class ScheduleDAGInstrs : public ScheduleDAG { protected: - const MachineLoopInfo &MLI; - const MachineDominatorTree &MDT; + const MachineLoopInfo *MLI; const MachineFrameInfo *MFI; - const InstrItineraryData *InstrItins; /// Live Intervals provides reaching defs in preRA scheduling. LiveIntervals *LIS; + /// TargetSchedModel provides an interface to the machine model. + TargetSchedModel SchedModel; + /// isPostRA flag indicates vregs cannot be present. bool IsPostRA; - /// UnitLatencies (misnamed) flag avoids computing def-use latencies, using - /// the def-side latency only. - bool UnitLatencies; + /// True if the DAG builder should remove kill flags (in preparation for + /// rescheduling). + bool RemoveKillFlags; /// The standard DAG builder does not normally include terminators as DAG /// nodes because it does not create the necessary dependencies to prevent - /// reordering. A specialized scheduler can overide + /// reordering. A specialized scheduler can override /// TargetInstrInfo::isSchedulingBoundary then enable this flag to indicate /// it has taken responsibility for scheduling the terminator correctly. bool CanHandleTerminators; @@ -200,13 +110,18 @@ namespace llvm { /// The end of the range to be scheduled. MachineBasicBlock::iterator RegionEnd; - /// The index in BB of RegionEnd. - unsigned EndIndex; + /// Instructions in this region (distance(RegionBegin, RegionEnd)). + unsigned NumRegionInstrs; /// After calling BuildSchedGraph, each machine instruction in the current /// scheduling region is mapped to an SUnit. DenseMap MISUnitMap; + /// After calling BuildSchedGraph, each vreg used in the scheduling region + /// is mapped to a set of SUnits. These include all local vreg uses, not + /// just the uses for a singly defined vreg. + VReg2UseMap VRegUses; + /// State internal to DAG building. /// ------------------------------- @@ -217,7 +132,7 @@ namespace llvm { Reg2SUnitsMap Defs; Reg2SUnitsMap Uses; - /// Track the last instructon in this region defining each virtual register. + /// Track the last instruction in this region defining each virtual register. VReg2SUnitMap VRegDefs; /// PendingLoads - Remember where unknown loads are after the most recent @@ -225,11 +140,7 @@ namespace llvm { /// to minimize construction/destruction. std::vector PendingLoads; - /// LoopRegs - Track which registers are used for loop-carried dependencies. - /// - LoopDependencies LoopRegs; - - /// DbgValues - Remember instruction that preceeds DBG_VALUE. + /// DbgValues - Remember instruction that precedes DBG_VALUE. /// These are generated by buildSchedGraph but persist so they can be /// referenced when emitting the final schedule. typedef std::vector > @@ -237,15 +148,33 @@ namespace llvm { DbgValueVector DbgValues; MachineInstr *FirstDbgValue; + /// Set of live physical registers for updating kill flags. + BitVector LiveRegs; + public: explicit ScheduleDAGInstrs(MachineFunction &mf, - const MachineLoopInfo &mli, - const MachineDominatorTree &mdt, + const MachineLoopInfo *mli, bool IsPostRAFlag, - LiveIntervals *LIS = 0); + bool RemoveKillFlags = false, + LiveIntervals *LIS = nullptr); virtual ~ScheduleDAGInstrs() {} + bool isPostRA() const { return IsPostRA; } + + /// \brief Expose LiveIntervals for use in DAG mutators and such. + LiveIntervals *getLIS() const { return LIS; } + + /// \brief Get the machine model for instruction scheduling. + const TargetSchedModel *getSchedModel() const { return &SchedModel; } + + /// \brief Resolve and cache a resolved scheduling class for an SUnit. + const MCSchedClassDesc *getSchedClass(SUnit *SU) const { + if (!SU->SchedClass && SchedModel.hasInstrSchedModel()) + SU->SchedClass = SchedModel.resolveSchedClass(SU->getInstr()); + return SU->SchedClass; + } + /// begin - Return an iterator to the top of the current scheduling region. MachineBasicBlock::iterator begin() const { return RegionBegin; } @@ -268,14 +197,16 @@ namespace llvm { virtual void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, - unsigned endcount); + unsigned regioninstrs); /// Notify that the scheduler has finished scheduling the current region. virtual void exitRegion(); /// buildSchedGraph - Build SUnits from the MachineBasicBlock that we are /// input. - void buildSchedGraph(AliasAnalysis *AA); + void buildSchedGraph(AliasAnalysis *AA, + RegPressureTracker *RPTracker = nullptr, + PressureDiffs *PDiffs = nullptr); /// addSchedBarrierDeps - Add dependencies from instructions in the current /// list of instructions being scheduled to scheduling barrier. We want to @@ -286,16 +217,6 @@ namespace llvm { /// used by instructions in the fallthrough block. void addSchedBarrierDeps(); - /// computeLatency - Compute node latency. - /// - virtual void computeLatency(SUnit *SU); - - /// computeOperandLatency - Override dependence edge latency using - /// operand use/def information - /// - virtual void computeOperandLatency(SUnit *Def, SUnit *Use, - SDep& dep) const; - /// schedule - Order nodes according to selected style, filling /// in the Sequence member. /// @@ -307,33 +228,40 @@ namespace llvm { /// the level of the whole MachineFunction. By default does nothing. virtual void finalizeSchedule() {} - virtual void dumpNode(const SUnit *SU) const; + void dumpNode(const SUnit *SU) const override; /// Return a label for a DAG node that points to an instruction. - virtual std::string getGraphNodeLabel(const SUnit *SU) const; + std::string getGraphNodeLabel(const SUnit *SU) const override; /// Return a label for the region of code covered by the DAG. - virtual std::string getDAGName() const; + std::string getDAGName() const override; + /// \brief Fix register kill flags that scheduling has made invalid. + void fixupKills(MachineBasicBlock *MBB); protected: void initSUnits(); - void addPhysRegDataDeps(SUnit *SU, const MachineOperand &MO); + void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx); void addPhysRegDeps(SUnit *SU, unsigned OperIdx); void addVRegDefDeps(SUnit *SU, unsigned OperIdx); void addVRegUseDeps(SUnit *SU, unsigned OperIdx); - VReg2SUnitMap::iterator findVRegDef(unsigned VirtReg) { - return VRegDefs.find(TargetRegisterInfo::virtReg2Index(VirtReg)); - } + /// \brief PostRA helper for rewriting kill flags. + void startBlockForKills(MachineBasicBlock *BB); + + /// \brief Toggle a register operand kill flag. + /// + /// Other adjustments may be made to the instruction if necessary. Return + /// true if the operand has been deleted, false if not. + bool toggleKillFlag(MachineInstr *MI, MachineOperand &MO); }; /// newSUnit - Creates a new SUnit and return a ptr to it. inline SUnit *ScheduleDAGInstrs::newSUnit(MachineInstr *MI) { #ifndef NDEBUG - const SUnit *Addr = SUnits.empty() ? 0 : &SUnits[0]; + const SUnit *Addr = SUnits.empty() ? nullptr : &SUnits[0]; #endif SUnits.push_back(SUnit(MI, (unsigned)SUnits.size())); - assert((Addr == 0 || Addr == &SUnits[0]) && + assert((Addr == nullptr || Addr == &SUnits[0]) && "SUnits std::vector reallocated on the fly!"); SUnits.back().OrigNode = &SUnits.back(); return &SUnits.back(); @@ -343,7 +271,7 @@ namespace llvm { inline SUnit *ScheduleDAGInstrs::getSUnit(MachineInstr *MI) const { DenseMap::const_iterator I = MISUnitMap.find(MI); if (I == MISUnitMap.end()) - return 0; + return nullptr; return I->second; } } // namespace llvm