// return new CustomMachineScheduler(C);
// }
//
-// The default scheduler, ScheduleDAGMI, builds the DAG and drives list
+// The default scheduler, ScheduleDAGMILive, 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
#include "llvm/CodeGen/RegisterPressure.h"
#include "llvm/CodeGen/ScheduleDAGInstrs.h"
+#include <memory>
+
namespace llvm {
extern cl::opt<bool> ForceTopDown;
bool OnlyTopDown;
bool OnlyBottomUp;
- MachineSchedPolicy():
- ShouldTrackPressure(false), OnlyTopDown(false), OnlyBottomUp(false) {}
+ MachineSchedPolicy(): ShouldTrackPressure(false), OnlyTopDown(false),
+ OnlyBottomUp(false) {}
};
/// MachineSchedStrategy - Interface to the scheduling algorithm used by
virtual void apply(ScheduleDAGMI *DAG) = 0;
};
-/// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that schedules
-/// machine instructions while updating LiveIntervals and tracking regpressure.
+/// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply
+/// schedules machine instructions according to the given MachineSchedStrategy
+/// without much extra book-keeping. This is the common functionality between
+/// PreRA and PostRA MachineScheduler.
class ScheduleDAGMI : public ScheduleDAGInstrs {
protected:
AliasAnalysis *AA;
- RegisterClassInfo *RegClassInfo;
- MachineSchedStrategy *SchedImpl;
-
- /// Information about DAG subtrees. If DFSResult is NULL, then SchedulerTrees
- /// will be empty.
- SchedDFSResult *DFSResult;
- BitVector ScheduledTrees;
+ std::unique_ptr<MachineSchedStrategy> SchedImpl;
/// Topo - A topological ordering for SUnits which permits fast IsReachable
/// and similar queries.
ScheduleDAGTopologicalSort Topo;
/// Ordered list of DAG postprocessing steps.
- std::vector<ScheduleDAGMutation*> Mutations;
-
- MachineBasicBlock::iterator LiveRegionEnd;
-
- // 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<PressureChange> RegionCriticalPSets;
+ std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
/// The top of the unscheduled zone.
MachineBasicBlock::iterator CurrentTop;
- IntervalPressure TopPressure;
- RegPressureTracker TopRPTracker;
/// The bottom of the unscheduled zone.
MachineBasicBlock::iterator CurrentBottom;
- IntervalPressure BotPressure;
- RegPressureTracker BotRPTracker;
/// Record the next node in a scheduled cluster.
const SUnit *NextClusterPred;
/// scheduler at the point determined by misched-cutoff.
unsigned NumInstrsScheduled;
#endif
-
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), DFSResult(0),
- Topo(SUnits, &ExitSU), ShouldTrackPressure(false),
- RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure),
- CurrentBottom(), BotRPTracker(BotPressure),
- NextClusterPred(NULL), NextClusterSucc(NULL) {
+ ScheduleDAGMI(MachineSchedContext *C, std::unique_ptr<MachineSchedStrategy> S,
+ bool IsPostRA)
+ : ScheduleDAGInstrs(*C->MF, C->MLI, IsPostRA,
+ /*RemoveKillFlags=*/IsPostRA, C->LIS),
+ AA(C->AA), SchedImpl(std::move(S)), Topo(SUnits, &ExitSU), CurrentTop(),
+ CurrentBottom(), NextClusterPred(nullptr), NextClusterSucc(nullptr) {
#ifndef NDEBUG
NumInstrsScheduled = 0;
#endif
}
- virtual ~ScheduleDAGMI();
+ // Provide a vtable anchor
+ ~ScheduleDAGMI() override;
- /// \brief Return true if register pressure tracking is enabled.
- bool isTrackingPressure() const { return ShouldTrackPressure; }
+ /// Return true if this DAG supports VReg liveness and RegPressure.
+ virtual bool hasVRegLiveness() const { return false; }
/// 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);
+ void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
+ Mutations.push_back(std::move(Mutation));
}
/// \brief True if an edge can be added from PredSU to SuccSU without creating
void enterRegion(MachineBasicBlock *bb,
MachineBasicBlock::iterator begin,
MachineBasicBlock::iterator end,
- unsigned regioninstrs) LLVM_OVERRIDE;
+ unsigned regioninstrs) override;
/// Implement ScheduleDAGInstrs interface for scheduling a sequence of
/// reorderable instructions.
- virtual void schedule();
+ void schedule() override;
/// 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);
+ const SUnit *getNextClusterPred() const { return NextClusterPred; }
+
+ const SUnit *getNextClusterSucc() const { return NextClusterSucc; }
+
+ void viewGraph(const Twine &Name, const Twine &Title) override;
+ void viewGraph() override;
+
+protected:
+ // Top-Level entry points for the schedule() driver...
+
+ /// Apply each ScheduleDAGMutation step in order. This allows different
+ /// instances of ScheduleDAGMI to perform custom DAG postprocessing.
+ void postprocessDAG();
+
+ /// Release ExitSU predecessors and setup scheduler queues.
+ void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots);
+
+ /// Update scheduler DAG and queues after scheduling an instruction.
+ void updateQueues(SUnit *SU, bool IsTopNode);
+
+ /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
+ void placeDebugValues();
+
+ /// \brief dump the scheduled Sequence.
+ void dumpSchedule() const;
+
+ // Lesser helpers...
+ bool checkSchedLimit();
+
+ void findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots,
+ SmallVectorImpl<SUnit*> &BotRoots);
+
+ void releaseSucc(SUnit *SU, SDep *SuccEdge);
+ void releaseSuccessors(SUnit *SU);
+ void releasePred(SUnit *SU, SDep *PredEdge);
+ void releasePredecessors(SUnit *SU);
+};
+
+/// ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules
+/// machine instructions while updating LiveIntervals and tracking regpressure.
+class ScheduleDAGMILive : public ScheduleDAGMI {
+protected:
+ RegisterClassInfo *RegClassInfo;
+
+ /// Information about DAG subtrees. If DFSResult is NULL, then SchedulerTrees
+ /// will be empty.
+ SchedDFSResult *DFSResult;
+ BitVector ScheduledTrees;
+
+ MachineBasicBlock::iterator LiveRegionEnd;
+
+ // 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<PressureChange> RegionCriticalPSets;
+
+ /// The top of the unscheduled zone.
+ IntervalPressure TopPressure;
+ RegPressureTracker TopRPTracker;
+
+ /// The bottom of the unscheduled zone.
+ IntervalPressure BotPressure;
+ RegPressureTracker BotRPTracker;
+
+public:
+ ScheduleDAGMILive(MachineSchedContext *C,
+ std::unique_ptr<MachineSchedStrategy> S)
+ : ScheduleDAGMI(C, std::move(S), /*IsPostRA=*/false),
+ RegClassInfo(C->RegClassInfo), DFSResult(nullptr),
+ ShouldTrackPressure(false), RPTracker(RegPressure),
+ TopRPTracker(TopPressure), BotRPTracker(BotPressure) {}
+
+ virtual ~ScheduleDAGMILive();
+
+ /// Return true if this DAG supports VReg liveness and RegPressure.
+ bool hasVRegLiveness() const override { return true; }
+
+ /// \brief Return true if register pressure tracking is enabled.
+ bool isTrackingPressure() const { return ShouldTrackPressure; }
+
/// Get current register pressure for the top scheduled instructions.
const IntervalPressure &getTopPressure() const { return TopPressure; }
const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; }
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();
BitVector &getScheduledTrees() { return ScheduledTrees; }
+ /// Implement the ScheduleDAGInstrs interface for handling the next scheduling
+ /// region. This covers all instructions in a block, while schedule() may only
+ /// cover a subset.
+ void enterRegion(MachineBasicBlock *bb,
+ MachineBasicBlock::iterator begin,
+ MachineBasicBlock::iterator end,
+ unsigned regioninstrs) override;
+
+ /// Implement ScheduleDAGInstrs interface for scheduling a sequence of
+ /// reorderable instructions.
+ void schedule() override;
+
/// 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...
/// bottom of the DAG region without covereing any unscheduled instruction.
void buildDAGWithRegPressure();
- /// Apply each ScheduleDAGMutation step in order. This allows different
- /// instances of ScheduleDAGMI to perform custom DAG postprocessing.
- void postprocessDAG();
-
- /// Release ExitSU predecessors and setup scheduler queues.
- void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots);
-
/// Move an instruction and update register pressure.
void scheduleMI(SUnit *SU, bool IsTopNode);
- /// Update scheduler DAG and queues after scheduling an instruction.
- void updateQueues(SUnit *SU, bool IsTopNode);
-
- /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
- void placeDebugValues();
-
- /// \brief dump the scheduled Sequence.
- void dumpSchedule() const;
-
// Lesser helpers...
void initRegPressure();
void updateScheduledPressure(const SUnit *SU,
const std::vector<unsigned> &NewMaxPressure);
-
- bool checkSchedLimit();
-
- void findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots,
- SmallVectorImpl<SUnit*> &BotRoots);
-
- void releaseSucc(SUnit *SU, SDep *SuccEdge);
- void releaseSuccessors(SUnit *SU);
- void releasePred(SUnit *SU, SDep *PredEdge);
- void releasePredecessors(SUnit *SU);
};
//===----------------------------------------------------------------------===//
return Queue.begin() + idx;
}
-#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void dump();
-#endif
};
/// Summarize the unscheduled region.
SmallVector<unsigned, 16> ReservedCycles;
#ifndef NDEBUG
- // Remember the greatest operand latency as an upper bound on the number of
+ // Remember the greatest possible stall as an upper bound on the number of
// times we should retry the pending queue because of a hazard.
- unsigned MaxObservedLatency;
+ unsigned MaxObservedStall;
#endif
public:
/// Pending queues extend the ready queues with the same ID and the
/// PendingFlag set.
SchedBoundary(unsigned ID, const Twine &Name):
- DAG(0), SchedModel(0), Rem(0), Available(ID, Name+".A"),
+ DAG(nullptr), SchedModel(nullptr), Rem(nullptr), Available(ID, Name+".A"),
Pending(ID << LogMaxQID, Name+".P"),
- HazardRec(0) {
+ HazardRec(nullptr) {
reset();
}
#endif
};
+/// Base class for GenericScheduler. This class maintains information about
+/// scheduling candidates based on TargetSchedModel making it easy to implement
+/// heuristics for either preRA or postRA scheduling.
+class GenericSchedulerBase : public MachineSchedStrategy {
+public:
+ /// Represent the type of SchedCandidate found within a single queue.
+ /// pickNodeBidirectional depends on these listed by decreasing priority.
+ enum CandReason {
+ NoCand, PhysRegCopy, RegExcess, RegCritical, Stall, Cluster, Weak, RegMax,
+ ResourceReduce, ResourceDemand, BotHeightReduce, BotPathReduce,
+ TopDepthReduce, TopPathReduce, NextDefUse, NodeOrder};
+
+#ifndef NDEBUG
+ static const char *getReasonStr(GenericSchedulerBase::CandReason Reason);
+#endif
+
+ /// Policy for scheduling the next instruction in the candidate's zone.
+ struct CandPolicy {
+ bool ReduceLatency;
+ unsigned ReduceResIdx;
+ unsigned DemandResIdx;
+
+ CandPolicy(): ReduceLatency(false), ReduceResIdx(0), DemandResIdx(0) {}
+ };
+
+ /// Status of an instruction's critical resource consumption.
+ struct SchedResourceDelta {
+ // Count critical resources in the scheduled region required by SU.
+ unsigned CritResources;
+
+ // Count critical resources from another region consumed by SU.
+ unsigned DemandedResources;
+
+ SchedResourceDelta(): CritResources(0), DemandedResources(0) {}
+
+ bool operator==(const SchedResourceDelta &RHS) const {
+ return CritResources == RHS.CritResources
+ && DemandedResources == RHS.DemandedResources;
+ }
+ bool operator!=(const SchedResourceDelta &RHS) const {
+ return !operator==(RHS);
+ }
+ };
+
+ /// Store the state used by GenericScheduler heuristics, required for the
+ /// lifetime of one invocation of pickNode().
+ struct SchedCandidate {
+ CandPolicy Policy;
+
+ // The best SUnit candidate.
+ SUnit *SU;
+
+ // The reason for this candidate.
+ CandReason Reason;
+
+ // Set of reasons that apply to multiple candidates.
+ uint32_t RepeatReasonSet;
+
+ // Register pressure values for the best candidate.
+ RegPressureDelta RPDelta;
+
+ // Critical resource consumption of the best candidate.
+ SchedResourceDelta ResDelta;
+
+ SchedCandidate(const CandPolicy &policy)
+ : Policy(policy), SU(nullptr), Reason(NoCand), RepeatReasonSet(0) {}
+
+ bool isValid() const { return SU; }
+
+ // Copy the status of another candidate without changing policy.
+ void setBest(SchedCandidate &Best) {
+ assert(Best.Reason != NoCand && "uninitialized Sched candidate");
+ SU = Best.SU;
+ Reason = Best.Reason;
+ RPDelta = Best.RPDelta;
+ ResDelta = Best.ResDelta;
+ }
+
+ bool isRepeat(CandReason R) { return RepeatReasonSet & (1 << R); }
+ void setRepeat(CandReason R) { RepeatReasonSet |= (1 << R); }
+
+ void initResourceDelta(const ScheduleDAGMI *DAG,
+ const TargetSchedModel *SchedModel);
+ };
+
+protected:
+ const MachineSchedContext *Context;
+ const TargetSchedModel *SchedModel;
+ const TargetRegisterInfo *TRI;
+
+ SchedRemainder Rem;
+protected:
+ GenericSchedulerBase(const MachineSchedContext *C):
+ Context(C), SchedModel(nullptr), TRI(nullptr) {}
+
+ void setPolicy(CandPolicy &Policy, bool IsPostRA, SchedBoundary &CurrZone,
+ SchedBoundary *OtherZone);
+
+#ifndef NDEBUG
+ void traceCandidate(const SchedCandidate &Cand);
+#endif
+};
+
+/// GenericScheduler shrinks the unscheduled zone using heuristics to balance
+/// the schedule.
+class GenericScheduler : public GenericSchedulerBase {
+ ScheduleDAGMILive *DAG;
+
+ // State of the top and bottom scheduled instruction boundaries.
+ SchedBoundary Top;
+ SchedBoundary Bot;
+
+ MachineSchedPolicy RegionPolicy;
+public:
+ GenericScheduler(const MachineSchedContext *C):
+ GenericSchedulerBase(C), DAG(nullptr), Top(SchedBoundary::TopQID, "TopQ"),
+ Bot(SchedBoundary::BotQID, "BotQ") {}
+
+ void initPolicy(MachineBasicBlock::iterator Begin,
+ MachineBasicBlock::iterator End,
+ unsigned NumRegionInstrs) override;
+
+ bool shouldTrackPressure() const override {
+ return RegionPolicy.ShouldTrackPressure;
+ }
+
+ void initialize(ScheduleDAGMI *dag) override;
+
+ SUnit *pickNode(bool &IsTopNode) override;
+
+ void schedNode(SUnit *SU, bool IsTopNode) override;
+
+ void releaseTopNode(SUnit *SU) override {
+ Top.releaseTopNode(SU);
+ }
+
+ void releaseBottomNode(SUnit *SU) override {
+ Bot.releaseBottomNode(SU);
+ }
+
+ void registerRoots() override;
+
+protected:
+ void checkAcyclicLatency();
+
+ void tryCandidate(SchedCandidate &Cand,
+ SchedCandidate &TryCand,
+ SchedBoundary &Zone,
+ const RegPressureTracker &RPTracker,
+ RegPressureTracker &TempTracker);
+
+ SUnit *pickNodeBidirectional(bool &IsTopNode);
+
+ void pickNodeFromQueue(SchedBoundary &Zone,
+ const RegPressureTracker &RPTracker,
+ SchedCandidate &Candidate);
+
+ void reschedulePhysRegCopies(SUnit *SU, bool isTop);
+};
+
+/// PostGenericScheduler - Interface to the scheduling algorithm used by
+/// ScheduleDAGMI.
+///
+/// Callbacks from ScheduleDAGMI:
+/// initPolicy -> initialize(DAG) -> registerRoots -> pickNode ...
+class PostGenericScheduler : public GenericSchedulerBase {
+ ScheduleDAGMI *DAG;
+ SchedBoundary Top;
+ SmallVector<SUnit*, 8> BotRoots;
+public:
+ PostGenericScheduler(const MachineSchedContext *C):
+ GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ") {}
+
+ virtual ~PostGenericScheduler() {}
+
+ void initPolicy(MachineBasicBlock::iterator Begin,
+ MachineBasicBlock::iterator End,
+ unsigned NumRegionInstrs) override {
+ /* no configurable policy */
+ };
+
+ /// PostRA scheduling does not track pressure.
+ bool shouldTrackPressure() const override { return false; }
+
+ void initialize(ScheduleDAGMI *Dag) override;
+
+ void registerRoots() override;
+
+ SUnit *pickNode(bool &IsTopNode) override;
+
+ void scheduleTree(unsigned SubtreeID) override {
+ llvm_unreachable("PostRA scheduler does not support subtree analysis.");
+ }
+
+ void schedNode(SUnit *SU, bool IsTopNode) override;
+
+ void releaseTopNode(SUnit *SU) override {
+ Top.releaseTopNode(SU);
+ }
+
+ // Only called for roots.
+ void releaseBottomNode(SUnit *SU) override {
+ BotRoots.push_back(SU);
+ }
+
+protected:
+ void tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand);
+
+ void pickNodeFromQueue(SchedCandidate &Cand);
+};
+
} // namespace llvm
#endif
projects / oota-llvm.git / blobdiff