diff options
author | Stephen Hines <srhines@google.com> | 2014-07-21 00:45:20 -0700 |
---|---|---|
committer | Stephen Hines <srhines@google.com> | 2014-07-21 00:45:20 -0700 |
commit | c6a4f5e819217e1e12c458aed8e7b122e23a3a58 (patch) | |
tree | 81b7dd2bb4370a392f31d332a566c903b5744764 /include/llvm/CodeGen/MachineScheduler.h | |
parent | 19c6fbb3e8aaf74093afa08013134b61fa08f245 (diff) | |
download | external_llvm-c6a4f5e819217e1e12c458aed8e7b122e23a3a58.zip external_llvm-c6a4f5e819217e1e12c458aed8e7b122e23a3a58.tar.gz external_llvm-c6a4f5e819217e1e12c458aed8e7b122e23a3a58.tar.bz2 |
Update LLVM for rebase to r212749.
Includes a cherry-pick of:
r212948 - fixes a small issue with atomic calls
Change-Id: Ib97bd980b59f18142a69506400911a6009d9df18
Diffstat (limited to 'include/llvm/CodeGen/MachineScheduler.h')
-rw-r--r-- | include/llvm/CodeGen/MachineScheduler.h | 217 |
1 files changed, 213 insertions, 4 deletions
diff --git a/include/llvm/CodeGen/MachineScheduler.h b/include/llvm/CodeGen/MachineScheduler.h index acd37e1..7d85432 100644 --- a/include/llvm/CodeGen/MachineScheduler.h +++ b/include/llvm/CodeGen/MachineScheduler.h @@ -518,9 +518,7 @@ public: return Queue.begin() + idx; } -#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) void dump(); -#endif }; /// Summarize the unscheduled region. @@ -624,9 +622,9 @@ private: 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: @@ -739,6 +737,217 @@ public: #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 |