X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FMachineScheduler.h;h=2003297ff0acda797d6858faa592e142fa351f2c;hb=2c46deb1d07f4588ee70059cdd4c7145f81bc8e8;hp=93990e164d1411e04db1cdd0c9f2df43ce929af9;hpb=412cd2f81374865dfa708bef6d5b896ca10dece0;p=oota-llvm.git diff --git a/include/llvm/CodeGen/MachineScheduler.h b/include/llvm/CodeGen/MachineScheduler.h index 93990e164d1..2003297ff0a 100644 --- a/include/llvm/CodeGen/MachineScheduler.h +++ b/include/llvm/CodeGen/MachineScheduler.h @@ -24,13 +24,12 @@ // //===----------------------------------------------------------------------===// -#ifndef MACHINESCHEDULER_H -#define MACHINESCHEDULER_H +#ifndef LLVM_CODEGEN_MACHINESCHEDULER_H +#define LLVM_CODEGEN_MACHINESCHEDULER_H #include "llvm/CodeGen/MachinePassRegistry.h" #include "llvm/CodeGen/RegisterPressure.h" #include "llvm/CodeGen/ScheduleDAGInstrs.h" -#include "llvm/Target/TargetInstrInfo.h" namespace llvm { @@ -43,6 +42,7 @@ class MachineDominatorTree; class MachineLoopInfo; class RegisterClassInfo; class ScheduleDAGInstrs; +class SchedDFSResult; /// MachineSchedContext provides enough context from the MachineScheduler pass /// for the target to instantiate a scheduler. @@ -101,20 +101,55 @@ public: class ScheduleDAGMI; +/// Define a generic scheduling policy for targets that don't provide their own +/// MachineSchedStrategy. This can be overriden for each scheduling region +/// before building the DAG. +struct MachineSchedPolicy { + // Allow the scheduler to disable register pressure tracking. + bool ShouldTrackPressure; + + // Allow the scheduler to force top-down or bottom-up scheduling. If neither + // is true, the scheduler runs in both directions and converges. + bool OnlyTopDown; + bool OnlyBottomUp; + + MachineSchedPolicy(): + ShouldTrackPressure(false), OnlyTopDown(false), OnlyBottomUp(false) {} +}; + /// MachineSchedStrategy - Interface to the scheduling algorithm used by /// ScheduleDAGMI. +/// +/// Initialization sequence: +/// initPolicy -> shouldTrackPressure -> initialize(DAG) -> registerRoots class MachineSchedStrategy { public: virtual ~MachineSchedStrategy() {} + /// Optionally override the per-region scheduling policy. + virtual void initPolicy(MachineBasicBlock::iterator Begin, + MachineBasicBlock::iterator End, + unsigned NumRegionInstrs) {} + + /// Check if pressure tracking is needed before building the DAG and + /// initializing this strategy. Called after initPolicy. + virtual bool shouldTrackPressure() const { return true; } + /// Initialize the strategy after building the DAG for a new region. virtual void initialize(ScheduleDAGMI *DAG) = 0; + /// Notify this strategy that all roots have been released (including those + /// that depend on EntrySU or ExitSU). + virtual void registerRoots() {} + /// Pick the next node to schedule, or return NULL. Set IsTopNode to true to /// schedule the node at the top of the unscheduled region. Otherwise it will /// be scheduled at the bottom. virtual SUnit *pickNode(bool &IsTopNode) = 0; + /// \brief Scheduler callback to notify that a new subtree is scheduled. + virtual void scheduleTree(unsigned SubtreeID) {} + /// Notify MachineSchedStrategy that ScheduleDAGMI has scheduled an /// instruction and updated scheduled/remaining flags in the DAG nodes. virtual void schedNode(SUnit *SU, bool IsTopNode) = 0; @@ -150,6 +185,8 @@ public: bool empty() const { return Queue.empty(); } + void clear() { Queue.clear(); } + unsigned size() const { return Queue.size(); } typedef std::vector::iterator iterator; @@ -158,6 +195,8 @@ public: iterator end() { return Queue.end(); } + ArrayRef elements() { return Queue; } + iterator find(SUnit *SU) { return std::find(Queue.begin(), Queue.end(), SU); } @@ -167,13 +206,15 @@ public: SU->NodeQueueId |= ID; } - void remove(iterator I) { + iterator remove(iterator I) { (*I)->NodeQueueId &= ~ID; *I = Queue.back(); + unsigned idx = I - Queue.begin(); Queue.pop_back(); + return Queue.begin() + idx; } -#ifndef NDEBUG +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) void dump(); #endif }; @@ -194,19 +235,34 @@ protected: RegisterClassInfo *RegClassInfo; MachineSchedStrategy *SchedImpl; + /// Information about DAG subtrees. If DFSResult is NULL, then SchedulerTrees + /// will be empty. + SchedDFSResult *DFSResult; + BitVector ScheduledTrees; + + /// Topo - A topological ordering for SUnits which permits fast IsReachable + /// and similar queries. + ScheduleDAGTopologicalSort Topo; + /// Ordered list of DAG postprocessing steps. std::vector Mutations; MachineBasicBlock::iterator LiveRegionEnd; - /// Register pressure in this region computed by buildSchedGraph. + // Map each SU to its summary of pressure changes. This array is updated for + // liveness during bottom-up scheduling. Top-down scheduling may proceed but + // has no affect on the pressure diffs. + PressureDiffs SUPressureDiffs; + + /// Register pressure in this region computed by initRegPressure. + bool ShouldTrackPressure; IntervalPressure RegPressure; RegPressureTracker RPTracker; /// List of pressure sets that exceed the target's pressure limit before /// scheduling, listed in increasing set ID order. Each pressure set is paired /// with its max pressure in the currently scheduled regions. - std::vector RegionCriticalPSets; + std::vector RegionCriticalPSets; /// The top of the unscheduled zone. MachineBasicBlock::iterator CurrentTop; @@ -218,6 +274,10 @@ protected: IntervalPressure BotPressure; RegPressureTracker BotRPTracker; + /// Record the next node in a scheduled cluster. + const SUnit *NextClusterPred; + const SUnit *NextClusterSucc; + #ifndef NDEBUG /// The number of instructions scheduled so far. Used to cut off the /// scheduler at the point determined by misched-cutoff. @@ -227,25 +287,41 @@ protected: public: ScheduleDAGMI(MachineSchedContext *C, MachineSchedStrategy *S): ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), - AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), + AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), DFSResult(0), + Topo(SUnits, &ExitSU), ShouldTrackPressure(false), RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure), - CurrentBottom(), BotRPTracker(BotPressure) { + CurrentBottom(), BotRPTracker(BotPressure), + NextClusterPred(NULL), NextClusterSucc(NULL) { #ifndef NDEBUG NumInstrsScheduled = 0; #endif } - virtual ~ScheduleDAGMI() { - delete SchedImpl; - } + virtual ~ScheduleDAGMI(); + + /// \brief Return true if register pressure tracking is enabled. + bool isTrackingPressure() const { return ShouldTrackPressure; } /// Add a postprocessing step to the DAG builder. /// Mutations are applied in the order that they are added after normal DAG /// building and before MachineSchedStrategy initialization. + /// + /// ScheduleDAGMI takes ownership of the Mutation object. void addMutation(ScheduleDAGMutation *Mutation) { Mutations.push_back(Mutation); } + /// \brief True if an edge can be added from PredSU to SuccSU without creating + /// a cycle. + bool canAddEdge(SUnit *SuccSU, SUnit *PredSU); + + /// \brief Add a DAG edge to the given SU with the given predecessor + /// dependence data. + /// + /// \returns true if the edge may be added without creating a cycle OR if an + /// equivalent edge already existed (false indicates failure). + bool addEdge(SUnit *SuccSU, const SDep &PredDep); + MachineBasicBlock::iterator top() const { return CurrentTop; } MachineBasicBlock::iterator bottom() const { return CurrentBottom; } @@ -255,13 +331,16 @@ public: void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, - unsigned endcount); - + unsigned regioninstrs) LLVM_OVERRIDE; /// Implement ScheduleDAGInstrs interface for scheduling a sequence of /// reorderable instructions. virtual void schedule(); + /// Change the position of an instruction within the basic block and update + /// live ranges and region boundary iterators. + void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos); + /// Get current register pressure for the top scheduled instructions. const IntervalPressure &getTopPressure() const { return TopPressure; } const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; } @@ -273,10 +352,33 @@ public: /// Get register pressure for the entire scheduling region before scheduling. const IntervalPressure &getRegPressure() const { return RegPressure; } - const std::vector &getRegionCriticalPSets() const { + const std::vector &getRegionCriticalPSets() const { return RegionCriticalPSets; } + PressureDiff &getPressureDiff(const SUnit *SU) { + return SUPressureDiffs[SU->NodeNum]; + } + + const SUnit *getNextClusterPred() const { return NextClusterPred; } + + const SUnit *getNextClusterSucc() const { return NextClusterSucc; } + + /// Compute a DFSResult after DAG building is complete, and before any + /// queue comparisons. + void computeDFSResult(); + + /// Return a non-null DFS result if the scheduling strategy initialized it. + const SchedDFSResult *getDFSResult() const { return DFSResult; } + + BitVector &getScheduledTrees() { return ScheduledTrees; } + + /// Compute the cyclic critical path through the DAG. + unsigned computeCyclicCriticalPath(); + + void viewGraph(const Twine &Name, const Twine &Title) LLVM_OVERRIDE; + void viewGraph() LLVM_OVERRIDE; + protected: // Top-Level entry points for the schedule() driver... @@ -290,8 +392,8 @@ protected: /// instances of ScheduleDAGMI to perform custom DAG postprocessing. void postprocessDAG(); - /// Identify DAG roots and setup scheduler queues. - void initQueues(); + /// Release ExitSU predecessors and setup scheduler queues. + void initQueues(ArrayRef TopRoots, ArrayRef BotRoots); /// Move an instruction and update register pressure. void scheduleMI(SUnit *SU, bool IsTopNode); @@ -302,16 +404,22 @@ protected: /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues. void placeDebugValues(); + /// \brief dump the scheduled Sequence. + void dumpSchedule() const; + // Lesser helpers... void initRegPressure(); - void updateScheduledPressure(std::vector NewMaxPressure); + void updatePressureDiffs(ArrayRef LiveUses); + + void updateScheduledPressure(const SUnit *SU, + const std::vector &NewMaxPressure); - void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos); bool checkSchedLimit(); - void releaseRoots(); + void findRootsAndBiasEdges(SmallVectorImpl &TopRoots, + SmallVectorImpl &BotRoots); void releaseSucc(SUnit *SU, SDep *SuccEdge); void releaseSuccessors(SUnit *SU);