X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FMachineScheduler.h;h=77828953347c6315d7bf911e936a8005b537b40e;hb=1cbca515b6804a24d778fc0cab04ea0c53900141;hp=08f91828050829777eac84c28fde963a1be9bb56;hpb=9b5caaa9c452f262a52dd5ac7ebbc722da5a63de;p=oota-llvm.git diff --git a/include/llvm/CodeGen/MachineScheduler.h b/include/llvm/CodeGen/MachineScheduler.h index 08f91828050..77828953347 100644 --- a/include/llvm/CodeGen/MachineScheduler.h +++ b/include/llvm/CodeGen/MachineScheduler.h @@ -7,8 +7,48 @@ // //===----------------------------------------------------------------------===// // -// This file provides a MachineSchedRegistry for registering alternative machine -// schedulers. A Target may provide an alternative scheduler implementation by +// This file provides an interface for customizing the standard MachineScheduler +// pass. Note that the entire pass may be replaced as follows: +// +// TargetMachine::createPassConfig(PassManagerBase &PM) { +// PM.substitutePass(&MachineSchedulerID, &CustomSchedulerPassID); +// ...} +// +// The MachineScheduler pass is only responsible for choosing the regions to be +// scheduled. Targets can override the DAG builder and scheduler without +// replacing the pass as follows: +// +// ScheduleDAGInstrs *PassConfig:: +// createMachineScheduler(MachineSchedContext *C) { +// return new CustomMachineScheduler(C); +// } +// +// The default scheduler, ScheduleDAGMI, builds the DAG and drives list +// scheduling while updating the instruction stream, register pressure, and live +// intervals. Most targets don't need to override the DAG builder and list +// schedulier, but subtargets that require custom scheduling heuristics may +// plugin an alternate MachineSchedStrategy. The strategy is responsible for +// selecting the highest priority node from the list: +// +// ScheduleDAGInstrs *PassConfig:: +// createMachineScheduler(MachineSchedContext *C) { +// return new ScheduleDAGMI(C, CustomStrategy(C)); +// } +// +// The DAG builder can also be customized in a sense by adding DAG mutations +// that will run after DAG building and before list scheduling. DAG mutations +// can adjust dependencies based on target-specific knowledge or add weak edges +// to aid heuristics: +// +// ScheduleDAGInstrs *PassConfig:: +// createMachineScheduler(MachineSchedContext *C) { +// ScheduleDAGMI *DAG = new ScheduleDAGMI(C, CustomStrategy(C)); +// DAG->addMutation(new CustomDependencies(DAG->TII, DAG->TRI)); +// return DAG; +// } +// +// A target that supports alternative schedulers can use the +// MachineSchedRegistry to allow command line selection. This can be done by // implementing the following boilerplate: // // static ScheduleDAGInstrs *createCustomMachineSched(MachineSchedContext *C) { @@ -18,19 +58,28 @@ // SchedCustomRegistry("custom", "Run my target's custom scheduler", // createCustomMachineSched); // -// Inside PassConfig: -// enablePass(&MachineSchedulerID); -// MachineSchedRegistry::setDefault(createCustomMachineSched); +// +// Finally, subtargets that don't need to implement custom heuristics but would +// like to configure the GenericScheduler's policy for a given scheduler region, +// including scheduling direction and register pressure tracking policy, can do +// this: +// +// void Subtarget:: +// overrideSchedPolicy(MachineSchedPolicy &Policy, +// MachineInstr *begin, +// MachineInstr *end, +// unsigned NumRegionInstrs) const { +// Policy. = true; +// } // //===----------------------------------------------------------------------===// -#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 +92,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. @@ -85,15 +135,6 @@ public: static MachineSchedRegistry *getList() { return (MachineSchedRegistry *)Registry.getList(); } - static ScheduleDAGCtor getDefault() { - return (ScheduleDAGCtor)Registry.getDefault(); - } - static void setDefault(ScheduleDAGCtor C) { - Registry.setDefault((MachinePassCtor)C); - } - static void setDefault(StringRef Name) { - Registry.setDefault(Name); - } static void setListener(MachinePassRegistryListener *L) { Registry.setListener(L); } @@ -101,12 +142,41 @@ 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 { + virtual void anchor(); 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; @@ -119,6 +189,9 @@ public: /// 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; @@ -164,6 +237,8 @@ public: iterator end() { return Queue.end(); } + ArrayRef elements() { return Queue; } + iterator find(SUnit *SU) { return std::find(Queue.begin(), Queue.end(), SU); } @@ -181,13 +256,14 @@ public: return Queue.begin() + idx; } -#ifndef NDEBUG +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) void dump(); #endif }; /// Mutate the DAG as a postpass after normal DAG building. class ScheduleDAGMutation { + virtual void anchor(); public: virtual ~ScheduleDAGMutation() {} @@ -202,6 +278,11 @@ 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; @@ -211,14 +292,20 @@ protected: 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; @@ -243,19 +330,20 @@ 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), - Topo(SUnits, &ExitSU), RPTracker(RegPressure), CurrentTop(), - TopRPTracker(TopPressure), CurrentBottom(), BotRPTracker(BotPressure), + AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), DFSResult(0), + Topo(SUnits, &ExitSU), ShouldTrackPressure(false), + RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure), + CurrentBottom(), BotRPTracker(BotPressure), NextClusterPred(NULL), NextClusterSucc(NULL) { #ifndef NDEBUG NumInstrsScheduled = 0; #endif } - virtual ~ScheduleDAGMI() { - DeleteContainerPointers(Mutations); - 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 @@ -266,6 +354,10 @@ public: 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. /// @@ -282,13 +374,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; } @@ -300,14 +395,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... @@ -321,8 +435,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); @@ -340,12 +454,15 @@ protected: 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);