Dale Johannesen | 4dc35db | 2007-07-13 17:31:29 +0000 | [diff] [blame] | 1 | //===----- SchedulePostRAList.cpp - list scheduler ------------------------===// |
Dale Johannesen | 2182f06 | 2007-07-13 17:13:54 +0000 | [diff] [blame] | 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | f3ebc3f | 2007-12-29 20:36:04 +0000 | [diff] [blame] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Dale Johannesen | 2182f06 | 2007-07-13 17:13:54 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This implements a top-down list scheduler, using standard algorithms. |
| 11 | // The basic approach uses a priority queue of available nodes to schedule. |
| 12 | // One at a time, nodes are taken from the priority queue (thus in priority |
| 13 | // order), checked for legality to schedule, and emitted if legal. |
| 14 | // |
| 15 | // Nodes may not be legal to schedule either due to structural hazards (e.g. |
| 16 | // pipeline or resource constraints) or because an input to the instruction has |
| 17 | // not completed execution. |
| 18 | // |
| 19 | //===----------------------------------------------------------------------===// |
| 20 | |
Dale Johannesen | 2182f06 | 2007-07-13 17:13:54 +0000 | [diff] [blame] | 21 | #include "llvm/CodeGen/Passes.h" |
Chandler Carruth | ed0881b | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 22 | #include "AggressiveAntiDepBreaker.h" |
| 23 | #include "AntiDepBreaker.h" |
| 24 | #include "CriticalAntiDepBreaker.h" |
| 25 | #include "llvm/ADT/BitVector.h" |
| 26 | #include "llvm/ADT/Statistic.h" |
| 27 | #include "llvm/Analysis/AliasAnalysis.h" |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 28 | #include "llvm/CodeGen/LatencyPriorityQueue.h" |
Dan Gohman | dddc1ac | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 29 | #include "llvm/CodeGen/MachineDominators.h" |
David Goodwin | be3039e | 2009-10-01 19:45:32 +0000 | [diff] [blame] | 30 | #include "llvm/CodeGen/MachineFrameInfo.h" |
Dale Johannesen | 2182f06 | 2007-07-13 17:13:54 +0000 | [diff] [blame] | 31 | #include "llvm/CodeGen/MachineFunctionPass.h" |
Dan Gohman | dddc1ac | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 32 | #include "llvm/CodeGen/MachineLoopInfo.h" |
Dan Gohman | ad2134d | 2008-11-25 00:52:40 +0000 | [diff] [blame] | 33 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
Andrew Trick | 05ff466 | 2012-06-06 20:29:31 +0000 | [diff] [blame] | 34 | #include "llvm/CodeGen/RegisterClassInfo.h" |
Andrew Trick | 9a0c583 | 2012-03-07 23:01:06 +0000 | [diff] [blame] | 35 | #include "llvm/CodeGen/ScheduleDAGInstrs.h" |
Dan Gohman | ceac7c3 | 2009-01-16 01:33:36 +0000 | [diff] [blame] | 36 | #include "llvm/CodeGen/ScheduleHazardRecognizer.h" |
Chandler Carruth | ed0881b | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 37 | #include "llvm/CodeGen/SchedulerRegistry.h" |
David Goodwin | e056d10 | 2009-10-26 22:31:16 +0000 | [diff] [blame] | 38 | #include "llvm/Support/CommandLine.h" |
Dale Johannesen | 2182f06 | 2007-07-13 17:13:54 +0000 | [diff] [blame] | 39 | #include "llvm/Support/Debug.h" |
Torok Edwin | 56d0659 | 2009-07-11 20:10:48 +0000 | [diff] [blame] | 40 | #include "llvm/Support/ErrorHandling.h" |
David Goodwin | f20236a | 2009-08-11 01:44:26 +0000 | [diff] [blame] | 41 | #include "llvm/Support/raw_ostream.h" |
Chandler Carruth | ed0881b | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 42 | #include "llvm/Target/TargetInstrInfo.h" |
| 43 | #include "llvm/Target/TargetLowering.h" |
Chandler Carruth | ed0881b | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 44 | #include "llvm/Target/TargetRegisterInfo.h" |
| 45 | #include "llvm/Target/TargetSubtargetInfo.h" |
Dale Johannesen | 2182f06 | 2007-07-13 17:13:54 +0000 | [diff] [blame] | 46 | using namespace llvm; |
| 47 | |
Chandler Carruth | 1b9dde0 | 2014-04-22 02:02:50 +0000 | [diff] [blame] | 48 | #define DEBUG_TYPE "post-RA-sched" |
| 49 | |
Dan Gohman | ceac7c3 | 2009-01-16 01:33:36 +0000 | [diff] [blame] | 50 | STATISTIC(NumNoops, "Number of noops inserted"); |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 51 | STATISTIC(NumStalls, "Number of pipeline stalls"); |
David Goodwin | 8370485 | 2009-10-26 16:59:04 +0000 | [diff] [blame] | 52 | STATISTIC(NumFixedAnti, "Number of fixed anti-dependencies"); |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 53 | |
David Goodwin | 9a051a5 | 2009-10-01 21:46:35 +0000 | [diff] [blame] | 54 | // Post-RA scheduling is enabled with |
Evan Cheng | 0d639a2 | 2011-07-01 21:01:15 +0000 | [diff] [blame] | 55 | // TargetSubtargetInfo.enablePostRAScheduler(). This flag can be used to |
David Goodwin | 9a051a5 | 2009-10-01 21:46:35 +0000 | [diff] [blame] | 56 | // override the target. |
| 57 | static cl::opt<bool> |
| 58 | EnablePostRAScheduler("post-RA-scheduler", |
| 59 | cl::desc("Enable scheduling after register allocation"), |
David Goodwin | 1cc6dd9 | 2009-10-01 22:19:57 +0000 | [diff] [blame] | 60 | cl::init(false), cl::Hidden); |
David Goodwin | 8370485 | 2009-10-26 16:59:04 +0000 | [diff] [blame] | 61 | static cl::opt<std::string> |
Dan Gohman | ad2134d | 2008-11-25 00:52:40 +0000 | [diff] [blame] | 62 | EnableAntiDepBreaking("break-anti-dependencies", |
David Goodwin | 8370485 | 2009-10-26 16:59:04 +0000 | [diff] [blame] | 63 | cl::desc("Break post-RA scheduling anti-dependencies: " |
| 64 | "\"critical\", \"all\", or \"none\""), |
| 65 | cl::init("none"), cl::Hidden); |
Dan Gohman | ceac7c3 | 2009-01-16 01:33:36 +0000 | [diff] [blame] | 66 | |
David Goodwin | 7f65169 | 2009-09-01 18:34:03 +0000 | [diff] [blame] | 67 | // If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod |
| 68 | static cl::opt<int> |
| 69 | DebugDiv("postra-sched-debugdiv", |
| 70 | cl::desc("Debug control MBBs that are scheduled"), |
| 71 | cl::init(0), cl::Hidden); |
| 72 | static cl::opt<int> |
| 73 | DebugMod("postra-sched-debugmod", |
| 74 | cl::desc("Debug control MBBs that are scheduled"), |
| 75 | cl::init(0), cl::Hidden); |
| 76 | |
David Goodwin | 661ea98 | 2009-10-26 19:41:00 +0000 | [diff] [blame] | 77 | AntiDepBreaker::~AntiDepBreaker() { } |
| 78 | |
Dale Johannesen | 2182f06 | 2007-07-13 17:13:54 +0000 | [diff] [blame] | 79 | namespace { |
Nick Lewycky | 02d5f77 | 2009-10-25 06:33:48 +0000 | [diff] [blame] | 80 | class PostRAScheduler : public MachineFunctionPass { |
Evan Cheng | 2d51c7c | 2010-06-18 23:09:54 +0000 | [diff] [blame] | 81 | const TargetInstrInfo *TII; |
Jakob Stoklund Olesen | 4f5f84c | 2011-06-16 21:56:21 +0000 | [diff] [blame] | 82 | RegisterClassInfo RegClassInfo; |
Dan Gohman | 87b02d5 | 2009-10-09 23:27:56 +0000 | [diff] [blame] | 83 | |
Dale Johannesen | 2182f06 | 2007-07-13 17:13:54 +0000 | [diff] [blame] | 84 | public: |
| 85 | static char ID; |
Andrew Trick | df7e376 | 2012-02-08 21:22:53 +0000 | [diff] [blame] | 86 | PostRAScheduler() : MachineFunctionPass(ID) {} |
Dan Gohman | ad2134d | 2008-11-25 00:52:40 +0000 | [diff] [blame] | 87 | |
Craig Topper | 4584cd5 | 2014-03-07 09:26:03 +0000 | [diff] [blame] | 88 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
Dan Gohman | 0402315 | 2009-07-31 23:37:33 +0000 | [diff] [blame] | 89 | AU.setPreservesCFG(); |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 90 | AU.addRequired<AAResultsWrapperPass>(); |
Andrew Trick | df7e376 | 2012-02-08 21:22:53 +0000 | [diff] [blame] | 91 | AU.addRequired<TargetPassConfig>(); |
Dan Gohman | dddc1ac | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 92 | AU.addRequired<MachineDominatorTree>(); |
| 93 | AU.addPreserved<MachineDominatorTree>(); |
| 94 | AU.addRequired<MachineLoopInfo>(); |
| 95 | AU.addPreserved<MachineLoopInfo>(); |
| 96 | MachineFunctionPass::getAnalysisUsage(AU); |
| 97 | } |
| 98 | |
Craig Topper | 4584cd5 | 2014-03-07 09:26:03 +0000 | [diff] [blame] | 99 | bool runOnMachineFunction(MachineFunction &Fn) override; |
NAKAMURA Takumi | f51a34e | 2014-10-29 15:23:11 +0000 | [diff] [blame] | 100 | |
Sanjay Patel | a2f658d | 2014-07-15 22:39:58 +0000 | [diff] [blame] | 101 | bool enablePostRAScheduler( |
| 102 | const TargetSubtargetInfo &ST, CodeGenOpt::Level OptLevel, |
| 103 | TargetSubtargetInfo::AntiDepBreakMode &Mode, |
| 104 | TargetSubtargetInfo::RegClassVector &CriticalPathRCs) const; |
Dale Johannesen | 2182f06 | 2007-07-13 17:13:54 +0000 | [diff] [blame] | 105 | }; |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 106 | char PostRAScheduler::ID = 0; |
| 107 | |
Nick Lewycky | 02d5f77 | 2009-10-25 06:33:48 +0000 | [diff] [blame] | 108 | class SchedulePostRATDList : public ScheduleDAGInstrs { |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 109 | /// AvailableQueue - The priority queue to use for the available SUnits. |
Dan Gohman | 682a2d1 | 2009-10-21 01:44:44 +0000 | [diff] [blame] | 110 | /// |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 111 | LatencyPriorityQueue AvailableQueue; |
Jim Grosbach | d772bde | 2010-05-14 21:19:48 +0000 | [diff] [blame] | 112 | |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 113 | /// PendingQueue - This contains all of the instructions whose operands have |
| 114 | /// been issued, but their results are not ready yet (due to the latency of |
| 115 | /// the operation). Once the operands becomes available, the instruction is |
| 116 | /// added to the AvailableQueue. |
| 117 | std::vector<SUnit*> PendingQueue; |
| 118 | |
Dan Gohman | ceac7c3 | 2009-01-16 01:33:36 +0000 | [diff] [blame] | 119 | /// HazardRec - The hazard recognizer to use. |
| 120 | ScheduleHazardRecognizer *HazardRec; |
| 121 | |
David Goodwin | 8370485 | 2009-10-26 16:59:04 +0000 | [diff] [blame] | 122 | /// AntiDepBreak - Anti-dependence breaking object, or NULL if none |
| 123 | AntiDepBreaker *AntiDepBreak; |
| 124 | |
Dan Gohman | 87b02d5 | 2009-10-09 23:27:56 +0000 | [diff] [blame] | 125 | /// AA - AliasAnalysis for making memory reference queries. |
| 126 | AliasAnalysis *AA; |
| 127 | |
Andrew Trick | 60cf03e | 2012-03-07 05:21:52 +0000 | [diff] [blame] | 128 | /// The schedule. Null SUnit*'s represent noop instructions. |
| 129 | std::vector<SUnit*> Sequence; |
| 130 | |
Krzysztof Parzyszek | 5c61d11 | 2016-03-05 15:45:23 +0000 | [diff] [blame] | 131 | /// Ordered list of DAG postprocessing steps. |
| 132 | std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations; |
| 133 | |
Andrew Trick | a53e101 | 2013-08-23 17:48:33 +0000 | [diff] [blame] | 134 | /// The index in BB of RegionEnd. |
| 135 | /// |
| 136 | /// This is the instruction number from the top of the current block, not |
| 137 | /// the SlotIndex. It is only used by the AntiDepBreaker. |
| 138 | unsigned EndIndex; |
| 139 | |
Dan Gohman | ad2134d | 2008-11-25 00:52:40 +0000 | [diff] [blame] | 140 | public: |
Andrew Trick | 10ffc2b | 2010-12-24 05:03:26 +0000 | [diff] [blame] | 141 | SchedulePostRATDList( |
Alexey Samsonov | ea0aee6 | 2014-08-20 20:57:26 +0000 | [diff] [blame] | 142 | MachineFunction &MF, MachineLoopInfo &MLI, AliasAnalysis *AA, |
| 143 | const RegisterClassInfo &, |
| 144 | TargetSubtargetInfo::AntiDepBreakMode AntiDepMode, |
| 145 | SmallVectorImpl<const TargetRegisterClass *> &CriticalPathRCs); |
Dan Gohman | ceac7c3 | 2009-01-16 01:33:36 +0000 | [diff] [blame] | 146 | |
Alexander Kornienko | f817c1c | 2015-04-11 02:11:45 +0000 | [diff] [blame] | 147 | ~SchedulePostRATDList() override; |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 148 | |
Andrew Trick | 52226d4 | 2012-03-07 23:00:49 +0000 | [diff] [blame] | 149 | /// startBlock - Initialize register live-range state for scheduling in |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 150 | /// this block. |
| 151 | /// |
Craig Topper | 4584cd5 | 2014-03-07 09:26:03 +0000 | [diff] [blame] | 152 | void startBlock(MachineBasicBlock *BB) override; |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 153 | |
Andrew Trick | a53e101 | 2013-08-23 17:48:33 +0000 | [diff] [blame] | 154 | // Set the index of RegionEnd within the current BB. |
| 155 | void setEndIndex(unsigned EndIdx) { EndIndex = EndIdx; } |
| 156 | |
Andrew Trick | 60cf03e | 2012-03-07 05:21:52 +0000 | [diff] [blame] | 157 | /// Initialize the scheduler state for the next scheduling region. |
Craig Topper | 4584cd5 | 2014-03-07 09:26:03 +0000 | [diff] [blame] | 158 | void enterRegion(MachineBasicBlock *bb, |
| 159 | MachineBasicBlock::iterator begin, |
| 160 | MachineBasicBlock::iterator end, |
| 161 | unsigned regioninstrs) override; |
Andrew Trick | 60cf03e | 2012-03-07 05:21:52 +0000 | [diff] [blame] | 162 | |
| 163 | /// Notify that the scheduler has finished scheduling the current region. |
Craig Topper | 4584cd5 | 2014-03-07 09:26:03 +0000 | [diff] [blame] | 164 | void exitRegion() override; |
Andrew Trick | 60cf03e | 2012-03-07 05:21:52 +0000 | [diff] [blame] | 165 | |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 166 | /// Schedule - Schedule the instruction range using list scheduling. |
| 167 | /// |
Craig Topper | 4584cd5 | 2014-03-07 09:26:03 +0000 | [diff] [blame] | 168 | void schedule() override; |
Jim Grosbach | d772bde | 2010-05-14 21:19:48 +0000 | [diff] [blame] | 169 | |
Andrew Trick | e932bb7 | 2012-03-07 05:21:44 +0000 | [diff] [blame] | 170 | void EmitSchedule(); |
| 171 | |
Dan Gohman | 682a2d1 | 2009-10-21 01:44:44 +0000 | [diff] [blame] | 172 | /// Observe - Update liveness information to account for the current |
| 173 | /// instruction, which will not be scheduled. |
| 174 | /// |
Duncan P. N. Exon Smith | 5e6e8c7 | 2016-02-27 19:33:37 +0000 | [diff] [blame] | 175 | void Observe(MachineInstr &MI, unsigned Count); |
Dan Gohman | 682a2d1 | 2009-10-21 01:44:44 +0000 | [diff] [blame] | 176 | |
Andrew Trick | 52226d4 | 2012-03-07 23:00:49 +0000 | [diff] [blame] | 177 | /// finishBlock - Clean up register live-range state. |
Dan Gohman | 682a2d1 | 2009-10-21 01:44:44 +0000 | [diff] [blame] | 178 | /// |
Craig Topper | 4584cd5 | 2014-03-07 09:26:03 +0000 | [diff] [blame] | 179 | void finishBlock() override; |
Dan Gohman | 682a2d1 | 2009-10-21 01:44:44 +0000 | [diff] [blame] | 180 | |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 181 | private: |
Krzysztof Parzyszek | 5c61d11 | 2016-03-05 15:45:23 +0000 | [diff] [blame] | 182 | /// Apply each ScheduleDAGMutation step in order. |
| 183 | void postprocessDAG(); |
| 184 | |
David Goodwin | 80a03cc | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 185 | void ReleaseSucc(SUnit *SU, SDep *SuccEdge); |
| 186 | void ReleaseSuccessors(SUnit *SU); |
| 187 | void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle); |
| 188 | void ListScheduleTopDown(); |
Jim Grosbach | d772bde | 2010-05-14 21:19:48 +0000 | [diff] [blame] | 189 | |
Andrew Trick | edee68c | 2012-03-07 05:21:40 +0000 | [diff] [blame] | 190 | void dumpSchedule() const; |
Hal Finkel | 4fd3b1d | 2013-12-11 22:33:43 +0000 | [diff] [blame] | 191 | void emitNoop(unsigned CurCycle); |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 192 | }; |
Alexander Kornienko | f00654e | 2015-06-23 09:49:53 +0000 | [diff] [blame] | 193 | } |
Dale Johannesen | 2182f06 | 2007-07-13 17:13:54 +0000 | [diff] [blame] | 194 | |
Andrew Trick | 1fa5bcb | 2012-02-08 21:23:13 +0000 | [diff] [blame] | 195 | char &llvm::PostRASchedulerID = PostRAScheduler::ID; |
| 196 | |
| 197 | INITIALIZE_PASS(PostRAScheduler, "post-RA-sched", |
| 198 | "Post RA top-down list latency scheduler", false, false) |
| 199 | |
Andrew Trick | 10ffc2b | 2010-12-24 05:03:26 +0000 | [diff] [blame] | 200 | SchedulePostRATDList::SchedulePostRATDList( |
Alexey Samsonov | ea0aee6 | 2014-08-20 20:57:26 +0000 | [diff] [blame] | 201 | MachineFunction &MF, MachineLoopInfo &MLI, AliasAnalysis *AA, |
| 202 | const RegisterClassInfo &RCI, |
| 203 | TargetSubtargetInfo::AntiDepBreakMode AntiDepMode, |
| 204 | SmallVectorImpl<const TargetRegisterClass *> &CriticalPathRCs) |
Matthias Braun | 93563e7 | 2015-11-03 01:53:29 +0000 | [diff] [blame] | 205 | : ScheduleDAGInstrs(MF, &MLI), AA(AA), EndIndex(0) { |
Andrew Trick | 6b104f8 | 2013-12-28 21:56:55 +0000 | [diff] [blame] | 206 | |
Eric Christopher | d913448 | 2014-08-04 21:25:23 +0000 | [diff] [blame] | 207 | const InstrItineraryData *InstrItins = |
Eric Christopher | b66367a | 2014-10-14 07:17:23 +0000 | [diff] [blame] | 208 | MF.getSubtarget().getInstrItineraryData(); |
Andrew Trick | 10ffc2b | 2010-12-24 05:03:26 +0000 | [diff] [blame] | 209 | HazardRec = |
Eric Christopher | b66367a | 2014-10-14 07:17:23 +0000 | [diff] [blame] | 210 | MF.getSubtarget().getInstrInfo()->CreateTargetPostRAHazardRecognizer( |
Eric Christopher | d913448 | 2014-08-04 21:25:23 +0000 | [diff] [blame] | 211 | InstrItins, this); |
Krzysztof Parzyszek | 5c61d11 | 2016-03-05 15:45:23 +0000 | [diff] [blame] | 212 | MF.getSubtarget().getPostRAMutations(Mutations); |
Preston Gurd | 9a09147 | 2012-04-23 21:39:35 +0000 | [diff] [blame] | 213 | |
| 214 | assert((AntiDepMode == TargetSubtargetInfo::ANTIDEP_NONE || |
| 215 | MRI.tracksLiveness()) && |
| 216 | "Live-ins must be accurate for anti-dependency breaking"); |
Andrew Trick | 10ffc2b | 2010-12-24 05:03:26 +0000 | [diff] [blame] | 217 | AntiDepBreak = |
Evan Cheng | 0d639a2 | 2011-07-01 21:01:15 +0000 | [diff] [blame] | 218 | ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_ALL) ? |
Jakob Stoklund Olesen | 4f5f84c | 2011-06-16 21:56:21 +0000 | [diff] [blame] | 219 | (AntiDepBreaker *)new AggressiveAntiDepBreaker(MF, RCI, CriticalPathRCs) : |
Evan Cheng | 0d639a2 | 2011-07-01 21:01:15 +0000 | [diff] [blame] | 220 | ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_CRITICAL) ? |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 221 | (AntiDepBreaker *)new CriticalAntiDepBreaker(MF, RCI) : nullptr)); |
Andrew Trick | 10ffc2b | 2010-12-24 05:03:26 +0000 | [diff] [blame] | 222 | } |
| 223 | |
| 224 | SchedulePostRATDList::~SchedulePostRATDList() { |
| 225 | delete HazardRec; |
| 226 | delete AntiDepBreak; |
| 227 | } |
| 228 | |
Andrew Trick | 60cf03e | 2012-03-07 05:21:52 +0000 | [diff] [blame] | 229 | /// Initialize state associated with the next scheduling region. |
| 230 | void SchedulePostRATDList::enterRegion(MachineBasicBlock *bb, |
| 231 | MachineBasicBlock::iterator begin, |
| 232 | MachineBasicBlock::iterator end, |
Andrew Trick | a53e101 | 2013-08-23 17:48:33 +0000 | [diff] [blame] | 233 | unsigned regioninstrs) { |
| 234 | ScheduleDAGInstrs::enterRegion(bb, begin, end, regioninstrs); |
Andrew Trick | 60cf03e | 2012-03-07 05:21:52 +0000 | [diff] [blame] | 235 | Sequence.clear(); |
| 236 | } |
| 237 | |
| 238 | /// Print the schedule before exiting the region. |
| 239 | void SchedulePostRATDList::exitRegion() { |
| 240 | DEBUG({ |
| 241 | dbgs() << "*** Final schedule ***\n"; |
| 242 | dumpSchedule(); |
| 243 | dbgs() << '\n'; |
| 244 | }); |
| 245 | ScheduleDAGInstrs::exitRegion(); |
| 246 | } |
| 247 | |
Manman Ren | 19f49ac | 2012-09-11 22:23:19 +0000 | [diff] [blame] | 248 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
Andrew Trick | edee68c | 2012-03-07 05:21:40 +0000 | [diff] [blame] | 249 | /// dumpSchedule - dump the scheduled Sequence. |
| 250 | void SchedulePostRATDList::dumpSchedule() const { |
| 251 | for (unsigned i = 0, e = Sequence.size(); i != e; i++) { |
| 252 | if (SUnit *SU = Sequence[i]) |
| 253 | SU->dump(this); |
| 254 | else |
| 255 | dbgs() << "**** NOOP ****\n"; |
| 256 | } |
| 257 | } |
Manman Ren | 742534c | 2012-09-06 19:06:06 +0000 | [diff] [blame] | 258 | #endif |
Andrew Trick | edee68c | 2012-03-07 05:21:40 +0000 | [diff] [blame] | 259 | |
Sanjay Patel | a2f658d | 2014-07-15 22:39:58 +0000 | [diff] [blame] | 260 | bool PostRAScheduler::enablePostRAScheduler( |
| 261 | const TargetSubtargetInfo &ST, |
| 262 | CodeGenOpt::Level OptLevel, |
| 263 | TargetSubtargetInfo::AntiDepBreakMode &Mode, |
| 264 | TargetSubtargetInfo::RegClassVector &CriticalPathRCs) const { |
| 265 | Mode = ST.getAntiDepBreakMode(); |
| 266 | ST.getCriticalPathRCs(CriticalPathRCs); |
Matthias Braun | 39a2afc | 2015-06-13 03:42:16 +0000 | [diff] [blame] | 267 | return ST.enablePostRAScheduler() && |
Sanjay Patel | a2f658d | 2014-07-15 22:39:58 +0000 | [diff] [blame] | 268 | OptLevel >= ST.getOptLevelToEnablePostRAScheduler(); |
| 269 | } |
| 270 | |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 271 | bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { |
Paul Robinson | 7c99ec5 | 2014-03-31 17:43:35 +0000 | [diff] [blame] | 272 | if (skipOptnoneFunction(*Fn.getFunction())) |
| 273 | return false; |
| 274 | |
Eric Christopher | fc6de42 | 2014-08-05 02:39:49 +0000 | [diff] [blame] | 275 | TII = Fn.getSubtarget().getInstrInfo(); |
Andrew Trick | 10ffc2b | 2010-12-24 05:03:26 +0000 | [diff] [blame] | 276 | MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>(); |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 277 | AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); |
Andrew Trick | df7e376 | 2012-02-08 21:22:53 +0000 | [diff] [blame] | 278 | TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>(); |
| 279 | |
Jakob Stoklund Olesen | 4f5f84c | 2011-06-16 21:56:21 +0000 | [diff] [blame] | 280 | RegClassInfo.runOnMachineFunction(Fn); |
Dan Gohman | 26e9b89 | 2009-10-10 00:15:38 +0000 | [diff] [blame] | 281 | |
David Goodwin | 9a051a5 | 2009-10-01 21:46:35 +0000 | [diff] [blame] | 282 | // Check for explicit enable/disable of post-ra scheduling. |
Evan Cheng | 7fae11b | 2011-12-14 02:11:42 +0000 | [diff] [blame] | 283 | TargetSubtargetInfo::AntiDepBreakMode AntiDepMode = |
| 284 | TargetSubtargetInfo::ANTIDEP_NONE; |
Craig Topper | 760b134 | 2012-02-22 05:59:10 +0000 | [diff] [blame] | 285 | SmallVector<const TargetRegisterClass*, 4> CriticalPathRCs; |
David Goodwin | 9a051a5 | 2009-10-01 21:46:35 +0000 | [diff] [blame] | 286 | if (EnablePostRAScheduler.getPosition() > 0) { |
| 287 | if (!EnablePostRAScheduler) |
Evan Cheng | 8b61476 | 2009-10-16 06:10:34 +0000 | [diff] [blame] | 288 | return false; |
David Goodwin | 9a051a5 | 2009-10-01 21:46:35 +0000 | [diff] [blame] | 289 | } else { |
Evan Cheng | 8b61476 | 2009-10-16 06:10:34 +0000 | [diff] [blame] | 290 | // Check that post-RA scheduling is enabled for this target. |
Andrew Trick | 10ffc2b | 2010-12-24 05:03:26 +0000 | [diff] [blame] | 291 | // This may upgrade the AntiDepMode. |
Eric Christopher | 3d4276f | 2015-01-27 07:31:29 +0000 | [diff] [blame] | 292 | if (!enablePostRAScheduler(Fn.getSubtarget(), PassConfig->getOptLevel(), |
Sanjay Patel | a2f658d | 2014-07-15 22:39:58 +0000 | [diff] [blame] | 293 | AntiDepMode, CriticalPathRCs)) |
Evan Cheng | 8b61476 | 2009-10-16 06:10:34 +0000 | [diff] [blame] | 294 | return false; |
David Goodwin | 9a051a5 | 2009-10-01 21:46:35 +0000 | [diff] [blame] | 295 | } |
David Goodwin | 17199b5 | 2009-09-30 00:10:16 +0000 | [diff] [blame] | 296 | |
David Goodwin | 02ad4cb | 2009-10-22 23:19:17 +0000 | [diff] [blame] | 297 | // Check for antidep breaking override... |
| 298 | if (EnableAntiDepBreaking.getPosition() > 0) { |
Evan Cheng | 0d639a2 | 2011-07-01 21:01:15 +0000 | [diff] [blame] | 299 | AntiDepMode = (EnableAntiDepBreaking == "all") |
| 300 | ? TargetSubtargetInfo::ANTIDEP_ALL |
| 301 | : ((EnableAntiDepBreaking == "critical") |
| 302 | ? TargetSubtargetInfo::ANTIDEP_CRITICAL |
| 303 | : TargetSubtargetInfo::ANTIDEP_NONE); |
David Goodwin | 02ad4cb | 2009-10-22 23:19:17 +0000 | [diff] [blame] | 304 | } |
| 305 | |
David Greene | aa8ce38 | 2010-01-05 01:26:01 +0000 | [diff] [blame] | 306 | DEBUG(dbgs() << "PostRAScheduler\n"); |
Dale Johannesen | 2182f06 | 2007-07-13 17:13:54 +0000 | [diff] [blame] | 307 | |
Alexey Samsonov | ea0aee6 | 2014-08-20 20:57:26 +0000 | [diff] [blame] | 308 | SchedulePostRATDList Scheduler(Fn, MLI, AA, RegClassInfo, AntiDepMode, |
Andrew Trick | 10ffc2b | 2010-12-24 05:03:26 +0000 | [diff] [blame] | 309 | CriticalPathRCs); |
Dan Gohman | 619ef48 | 2009-01-15 19:20:50 +0000 | [diff] [blame] | 310 | |
Dale Johannesen | 2182f06 | 2007-07-13 17:13:54 +0000 | [diff] [blame] | 311 | // Loop over all of the basic blocks |
Duncan P. N. Exon Smith | 1ff4098 | 2015-10-09 21:05:00 +0000 | [diff] [blame] | 312 | for (auto &MBB : Fn) { |
David Goodwin | 7f65169 | 2009-09-01 18:34:03 +0000 | [diff] [blame] | 313 | #ifndef NDEBUG |
| 314 | // If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod |
| 315 | if (DebugDiv > 0) { |
| 316 | static int bbcnt = 0; |
| 317 | if (bbcnt++ % DebugDiv != DebugMod) |
| 318 | continue; |
Craig Topper | a538d83 | 2012-08-22 06:07:19 +0000 | [diff] [blame] | 319 | dbgs() << "*** DEBUG scheduling " << Fn.getName() |
Duncan P. N. Exon Smith | 1ff4098 | 2015-10-09 21:05:00 +0000 | [diff] [blame] | 320 | << ":BB#" << MBB.getNumber() << " ***\n"; |
David Goodwin | 7f65169 | 2009-09-01 18:34:03 +0000 | [diff] [blame] | 321 | } |
| 322 | #endif |
| 323 | |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 324 | // Initialize register live-range state for scheduling in this block. |
Duncan P. N. Exon Smith | 1ff4098 | 2015-10-09 21:05:00 +0000 | [diff] [blame] | 325 | Scheduler.startBlock(&MBB); |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 326 | |
Dan Gohman | 5f8a259 | 2009-01-16 22:10:20 +0000 | [diff] [blame] | 327 | // Schedule each sequence of instructions not interrupted by a label |
| 328 | // or anything else that effectively needs to shut down scheduling. |
Duncan P. N. Exon Smith | 1ff4098 | 2015-10-09 21:05:00 +0000 | [diff] [blame] | 329 | MachineBasicBlock::iterator Current = MBB.end(); |
| 330 | unsigned Count = MBB.size(), CurrentCount = Count; |
| 331 | for (MachineBasicBlock::iterator I = Current; I != MBB.begin();) { |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 332 | MachineInstr *MI = std::prev(I); |
Andrew Trick | a53e101 | 2013-08-23 17:48:33 +0000 | [diff] [blame] | 333 | --Count; |
Jakob Stoklund Olesen | a793a59 | 2012-02-23 17:54:21 +0000 | [diff] [blame] | 334 | // Calls are not scheduling boundaries before register allocation, but |
| 335 | // post-ra we don't gain anything by scheduling across calls since we |
| 336 | // don't need to worry about register pressure. |
Duncan P. N. Exon Smith | 1ff4098 | 2015-10-09 21:05:00 +0000 | [diff] [blame] | 337 | if (MI->isCall() || TII->isSchedulingBoundary(MI, &MBB, Fn)) { |
| 338 | Scheduler.enterRegion(&MBB, I, Current, CurrentCount - Count); |
Andrew Trick | a53e101 | 2013-08-23 17:48:33 +0000 | [diff] [blame] | 339 | Scheduler.setEndIndex(CurrentCount); |
Andrew Trick | 52226d4 | 2012-03-07 23:00:49 +0000 | [diff] [blame] | 340 | Scheduler.schedule(); |
Andrew Trick | 60cf03e | 2012-03-07 05:21:52 +0000 | [diff] [blame] | 341 | Scheduler.exitRegion(); |
Dan Gohman | 25c1653 | 2010-05-01 00:01:06 +0000 | [diff] [blame] | 342 | Scheduler.EmitSchedule(); |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 343 | Current = MI; |
Andrew Trick | a53e101 | 2013-08-23 17:48:33 +0000 | [diff] [blame] | 344 | CurrentCount = Count; |
Duncan P. N. Exon Smith | 5e6e8c7 | 2016-02-27 19:33:37 +0000 | [diff] [blame] | 345 | Scheduler.Observe(*MI, CurrentCount); |
Dan Gohman | 5f8a259 | 2009-01-16 22:10:20 +0000 | [diff] [blame] | 346 | } |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 347 | I = MI; |
Evan Cheng | 7fae11b | 2011-12-14 02:11:42 +0000 | [diff] [blame] | 348 | if (MI->isBundle()) |
| 349 | Count -= MI->getBundleSize(); |
Dan Gohman | d564353 | 2009-02-03 18:57:45 +0000 | [diff] [blame] | 350 | } |
Dan Gohman | dfaf646 | 2009-02-11 04:27:20 +0000 | [diff] [blame] | 351 | assert(Count == 0 && "Instruction count mismatch!"); |
Duncan P. N. Exon Smith | 1ff4098 | 2015-10-09 21:05:00 +0000 | [diff] [blame] | 352 | assert((MBB.begin() == Current || CurrentCount != 0) && |
Dan Gohman | 64613ac | 2009-03-10 18:10:43 +0000 | [diff] [blame] | 353 | "Instruction count mismatch!"); |
Duncan P. N. Exon Smith | 1ff4098 | 2015-10-09 21:05:00 +0000 | [diff] [blame] | 354 | Scheduler.enterRegion(&MBB, MBB.begin(), Current, CurrentCount); |
Andrew Trick | a53e101 | 2013-08-23 17:48:33 +0000 | [diff] [blame] | 355 | Scheduler.setEndIndex(CurrentCount); |
Andrew Trick | 52226d4 | 2012-03-07 23:00:49 +0000 | [diff] [blame] | 356 | Scheduler.schedule(); |
Andrew Trick | 60cf03e | 2012-03-07 05:21:52 +0000 | [diff] [blame] | 357 | Scheduler.exitRegion(); |
Dan Gohman | 25c1653 | 2010-05-01 00:01:06 +0000 | [diff] [blame] | 358 | Scheduler.EmitSchedule(); |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 359 | |
| 360 | // Clean up register live-range state. |
Andrew Trick | 52226d4 | 2012-03-07 23:00:49 +0000 | [diff] [blame] | 361 | Scheduler.finishBlock(); |
David Goodwin | ae6bc82 | 2009-08-25 17:03:05 +0000 | [diff] [blame] | 362 | |
David Goodwin | 6c08cfc | 2009-09-03 22:15:25 +0000 | [diff] [blame] | 363 | // Update register kills |
Duncan P. N. Exon Smith | 1ff4098 | 2015-10-09 21:05:00 +0000 | [diff] [blame] | 364 | Scheduler.fixupKills(&MBB); |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 365 | } |
Dale Johannesen | 2182f06 | 2007-07-13 17:13:54 +0000 | [diff] [blame] | 366 | |
| 367 | return true; |
| 368 | } |
Jim Grosbach | d772bde | 2010-05-14 21:19:48 +0000 | [diff] [blame] | 369 | |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 370 | /// StartBlock - Initialize register live-range state for scheduling in |
| 371 | /// this block. |
Dan Gohman | ad2134d | 2008-11-25 00:52:40 +0000 | [diff] [blame] | 372 | /// |
Andrew Trick | 52226d4 | 2012-03-07 23:00:49 +0000 | [diff] [blame] | 373 | void SchedulePostRATDList::startBlock(MachineBasicBlock *BB) { |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 374 | // Call the superclass. |
Andrew Trick | 52226d4 | 2012-03-07 23:00:49 +0000 | [diff] [blame] | 375 | ScheduleDAGInstrs::startBlock(BB); |
Dan Gohman | ad2134d | 2008-11-25 00:52:40 +0000 | [diff] [blame] | 376 | |
David Goodwin | 8370485 | 2009-10-26 16:59:04 +0000 | [diff] [blame] | 377 | // Reset the hazard recognizer and anti-dep breaker. |
David Goodwin | 6021b4d | 2009-08-10 15:55:25 +0000 | [diff] [blame] | 378 | HazardRec->Reset(); |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 379 | if (AntiDepBreak) |
David Goodwin | 8370485 | 2009-10-26 16:59:04 +0000 | [diff] [blame] | 380 | AntiDepBreak->StartBlock(BB); |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 381 | } |
| 382 | |
| 383 | /// Schedule - Schedule the instruction range using list scheduling. |
| 384 | /// |
Andrew Trick | 52226d4 | 2012-03-07 23:00:49 +0000 | [diff] [blame] | 385 | void SchedulePostRATDList::schedule() { |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 386 | // Build the scheduling graph. |
Andrew Trick | 52226d4 | 2012-03-07 23:00:49 +0000 | [diff] [blame] | 387 | buildSchedGraph(AA); |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 388 | |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 389 | if (AntiDepBreak) { |
Jim Grosbach | d772bde | 2010-05-14 21:19:48 +0000 | [diff] [blame] | 390 | unsigned Broken = |
Andrew Trick | 8c207e4 | 2012-03-09 04:29:02 +0000 | [diff] [blame] | 391 | AntiDepBreak->BreakAntiDependencies(SUnits, RegionBegin, RegionEnd, |
| 392 | EndIndex, DbgValues); |
Jim Grosbach | d772bde | 2010-05-14 21:19:48 +0000 | [diff] [blame] | 393 | |
David Goodwin | 80a03cc | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 394 | if (Broken != 0) { |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 395 | // We made changes. Update the dependency graph. |
| 396 | // Theoretically we could update the graph in place: |
| 397 | // When a live range is changed to use a different register, remove |
| 398 | // the def's anti-dependence *and* output-dependence edges due to |
| 399 | // that register, and add new anti-dependence and output-dependence |
| 400 | // edges based on the next live range of the register. |
Andrew Trick | 60cf03e | 2012-03-07 05:21:52 +0000 | [diff] [blame] | 401 | ScheduleDAG::clearDAG(); |
Andrew Trick | 52226d4 | 2012-03-07 23:00:49 +0000 | [diff] [blame] | 402 | buildSchedGraph(AA); |
Jim Grosbach | d772bde | 2010-05-14 21:19:48 +0000 | [diff] [blame] | 403 | |
David Goodwin | 8370485 | 2009-10-26 16:59:04 +0000 | [diff] [blame] | 404 | NumFixedAnti += Broken; |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 405 | } |
| 406 | } |
| 407 | |
Krzysztof Parzyszek | cd99e36 | 2016-03-08 16:54:20 +0000 | [diff] [blame^] | 408 | postprocessDAG(); |
| 409 | |
David Greene | aa8ce38 | 2010-01-05 01:26:01 +0000 | [diff] [blame] | 410 | DEBUG(dbgs() << "********** List Scheduling **********\n"); |
Matthias Braun | 9198c67 | 2015-11-06 20:59:02 +0000 | [diff] [blame] | 411 | DEBUG( |
| 412 | for (const SUnit &SU : SUnits) { |
| 413 | SU.dumpAll(this); |
| 414 | dbgs() << '\n'; |
| 415 | } |
| 416 | ); |
David Goodwin | 6021b4d | 2009-08-10 15:55:25 +0000 | [diff] [blame] | 417 | |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 418 | AvailableQueue.initNodes(SUnits); |
David Goodwin | 80a03cc | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 419 | ListScheduleTopDown(); |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 420 | AvailableQueue.releaseState(); |
| 421 | } |
| 422 | |
| 423 | /// Observe - Update liveness information to account for the current |
| 424 | /// instruction, which will not be scheduled. |
| 425 | /// |
Duncan P. N. Exon Smith | 5e6e8c7 | 2016-02-27 19:33:37 +0000 | [diff] [blame] | 426 | void SchedulePostRATDList::Observe(MachineInstr &MI, unsigned Count) { |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 427 | if (AntiDepBreak) |
Andrew Trick | a316faa | 2012-03-07 23:00:52 +0000 | [diff] [blame] | 428 | AntiDepBreak->Observe(MI, Count, EndIndex); |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 429 | } |
| 430 | |
| 431 | /// FinishBlock - Clean up register live-range state. |
| 432 | /// |
Andrew Trick | 52226d4 | 2012-03-07 23:00:49 +0000 | [diff] [blame] | 433 | void SchedulePostRATDList::finishBlock() { |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 434 | if (AntiDepBreak) |
David Goodwin | 8370485 | 2009-10-26 16:59:04 +0000 | [diff] [blame] | 435 | AntiDepBreak->FinishBlock(); |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 436 | |
| 437 | // Call the superclass. |
Andrew Trick | 52226d4 | 2012-03-07 23:00:49 +0000 | [diff] [blame] | 438 | ScheduleDAGInstrs::finishBlock(); |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 439 | } |
| 440 | |
Krzysztof Parzyszek | 5c61d11 | 2016-03-05 15:45:23 +0000 | [diff] [blame] | 441 | /// Apply each ScheduleDAGMutation step in order. |
| 442 | void SchedulePostRATDList::postprocessDAG() { |
| 443 | for (auto &M : Mutations) |
| 444 | M->apply(this); |
| 445 | } |
| 446 | |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 447 | //===----------------------------------------------------------------------===// |
| 448 | // Top-Down Scheduling |
| 449 | //===----------------------------------------------------------------------===// |
| 450 | |
| 451 | /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to |
Andrew Trick | f1ff84c | 2012-11-12 19:28:57 +0000 | [diff] [blame] | 452 | /// the PendingQueue if the count reaches zero. |
David Goodwin | 80a03cc | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 453 | void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) { |
Dan Gohman | 2d17089 | 2008-12-09 22:54:47 +0000 | [diff] [blame] | 454 | SUnit *SuccSU = SuccEdge->getSUnit(); |
Reid Kleckner | 8ff5c19 | 2009-09-30 20:15:38 +0000 | [diff] [blame] | 455 | |
Andrew Trick | 4b1f9e3 | 2012-11-13 02:35:06 +0000 | [diff] [blame] | 456 | if (SuccEdge->isWeak()) { |
Andrew Trick | f1ff84c | 2012-11-12 19:28:57 +0000 | [diff] [blame] | 457 | --SuccSU->WeakPredsLeft; |
| 458 | return; |
| 459 | } |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 460 | #ifndef NDEBUG |
Reid Kleckner | 8ff5c19 | 2009-09-30 20:15:38 +0000 | [diff] [blame] | 461 | if (SuccSU->NumPredsLeft == 0) { |
David Greene | aa8ce38 | 2010-01-05 01:26:01 +0000 | [diff] [blame] | 462 | dbgs() << "*** Scheduling failed! ***\n"; |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 463 | SuccSU->dump(this); |
David Greene | aa8ce38 | 2010-01-05 01:26:01 +0000 | [diff] [blame] | 464 | dbgs() << " has been released too many times!\n"; |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 465 | llvm_unreachable(nullptr); |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 466 | } |
| 467 | #endif |
Reid Kleckner | 8ff5c19 | 2009-09-30 20:15:38 +0000 | [diff] [blame] | 468 | --SuccSU->NumPredsLeft; |
| 469 | |
Andrew Trick | 84f9ad9 | 2011-05-06 18:14:32 +0000 | [diff] [blame] | 470 | // Standard scheduler algorithms will recompute the depth of the successor |
Andrew Trick | aab77fe | 2011-05-06 17:09:08 +0000 | [diff] [blame] | 471 | // here as such: |
| 472 | // SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency()); |
| 473 | // |
| 474 | // However, we lazily compute node depth instead. Note that |
| 475 | // ScheduleNodeTopDown has already updated the depth of this node which causes |
| 476 | // all descendents to be marked dirty. Setting the successor depth explicitly |
| 477 | // here would cause depth to be recomputed for all its ancestors. If the |
| 478 | // successor is not yet ready (because of a transitively redundant edge) then |
| 479 | // this causes depth computation to be quadratic in the size of the DAG. |
Jim Grosbach | d772bde | 2010-05-14 21:19:48 +0000 | [diff] [blame] | 480 | |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 481 | // If all the node's predecessors are scheduled, this node is ready |
| 482 | // to be scheduled. Ignore the special ExitSU node. |
| 483 | if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 484 | PendingQueue.push_back(SuccSU); |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 485 | } |
| 486 | |
| 487 | /// ReleaseSuccessors - Call ReleaseSucc on each of SU's successors. |
David Goodwin | 80a03cc | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 488 | void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) { |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 489 | for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); |
David Goodwin | 8501dbbe | 2009-11-03 20:57:50 +0000 | [diff] [blame] | 490 | I != E; ++I) { |
David Goodwin | 80a03cc | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 491 | ReleaseSucc(SU, &*I); |
David Goodwin | 8501dbbe | 2009-11-03 20:57:50 +0000 | [diff] [blame] | 492 | } |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 493 | } |
| 494 | |
| 495 | /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending |
| 496 | /// count of its successors. If a successor pending count is zero, add it to |
| 497 | /// the Available queue. |
David Goodwin | 80a03cc | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 498 | void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { |
David Greene | aa8ce38 | 2010-01-05 01:26:01 +0000 | [diff] [blame] | 499 | DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 500 | DEBUG(SU->dump(this)); |
Jim Grosbach | d772bde | 2010-05-14 21:19:48 +0000 | [diff] [blame] | 501 | |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 502 | Sequence.push_back(SU); |
Jim Grosbach | d772bde | 2010-05-14 21:19:48 +0000 | [diff] [blame] | 503 | assert(CurCycle >= SU->getDepth() && |
David Goodwin | 8501dbbe | 2009-11-03 20:57:50 +0000 | [diff] [blame] | 504 | "Node scheduled above its depth!"); |
David Goodwin | 80a03cc | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 505 | SU->setDepthToAtLeast(CurCycle); |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 506 | |
David Goodwin | 80a03cc | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 507 | ReleaseSuccessors(SU); |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 508 | SU->isScheduled = true; |
Andrew Trick | 52226d4 | 2012-03-07 23:00:49 +0000 | [diff] [blame] | 509 | AvailableQueue.scheduledNode(SU); |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 510 | } |
| 511 | |
Hal Finkel | 4fd3b1d | 2013-12-11 22:33:43 +0000 | [diff] [blame] | 512 | /// emitNoop - Add a noop to the current instruction sequence. |
| 513 | void SchedulePostRATDList::emitNoop(unsigned CurCycle) { |
| 514 | DEBUG(dbgs() << "*** Emitting noop in cycle " << CurCycle << '\n'); |
| 515 | HazardRec->EmitNoop(); |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 516 | Sequence.push_back(nullptr); // NULL here means noop |
Hal Finkel | 4fd3b1d | 2013-12-11 22:33:43 +0000 | [diff] [blame] | 517 | ++NumNoops; |
| 518 | } |
| 519 | |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 520 | /// ListScheduleTopDown - The main loop of list scheduling for top-down |
| 521 | /// schedulers. |
David Goodwin | 80a03cc | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 522 | void SchedulePostRATDList::ListScheduleTopDown() { |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 523 | unsigned CurCycle = 0; |
Jim Grosbach | d772bde | 2010-05-14 21:19:48 +0000 | [diff] [blame] | 524 | |
David Goodwin | 8501dbbe | 2009-11-03 20:57:50 +0000 | [diff] [blame] | 525 | // We're scheduling top-down but we're visiting the regions in |
| 526 | // bottom-up order, so we don't know the hazards at the start of a |
| 527 | // region. So assume no hazards (this should usually be ok as most |
| 528 | // blocks are a single region). |
| 529 | HazardRec->Reset(); |
| 530 | |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 531 | // Release any successors of the special Entry node. |
David Goodwin | 80a03cc | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 532 | ReleaseSuccessors(&EntrySU); |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 533 | |
David Goodwin | 80a03cc | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 534 | // Add all leaves to Available queue. |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 535 | for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { |
| 536 | // It is available if it has no predecessors. |
Andrew Trick | f1ff84c | 2012-11-12 19:28:57 +0000 | [diff] [blame] | 537 | if (!SUnits[i].NumPredsLeft && !SUnits[i].isAvailable) { |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 538 | AvailableQueue.push(&SUnits[i]); |
| 539 | SUnits[i].isAvailable = true; |
| 540 | } |
| 541 | } |
Dan Gohman | b954343 | 2009-02-10 23:27:53 +0000 | [diff] [blame] | 542 | |
David Goodwin | 1f8c7a7 | 2009-08-12 21:47:46 +0000 | [diff] [blame] | 543 | // In any cycle where we can't schedule any instructions, we must |
| 544 | // stall or emit a noop, depending on the target. |
Benjamin Kramer | e3c9d23 | 2009-09-06 12:10:17 +0000 | [diff] [blame] | 545 | bool CycleHasInsts = false; |
David Goodwin | 1f8c7a7 | 2009-08-12 21:47:46 +0000 | [diff] [blame] | 546 | |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 547 | // While Available queue is not empty, grab the node with the highest |
| 548 | // priority. If it is not ready put it back. Schedule the node. |
Dan Gohman | ceac7c3 | 2009-01-16 01:33:36 +0000 | [diff] [blame] | 549 | std::vector<SUnit*> NotReady; |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 550 | Sequence.reserve(SUnits.size()); |
| 551 | while (!AvailableQueue.empty() || !PendingQueue.empty()) { |
| 552 | // Check to see if any of the pending instructions are ready to issue. If |
| 553 | // so, add them to the available queue. |
Dan Gohman | dddc1ac | 2008-12-16 03:25:46 +0000 | [diff] [blame] | 554 | unsigned MinDepth = ~0u; |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 555 | for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) { |
David Goodwin | 80a03cc | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 556 | if (PendingQueue[i]->getDepth() <= CurCycle) { |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 557 | AvailableQueue.push(PendingQueue[i]); |
| 558 | PendingQueue[i]->isAvailable = true; |
| 559 | PendingQueue[i] = PendingQueue.back(); |
| 560 | PendingQueue.pop_back(); |
| 561 | --i; --e; |
David Goodwin | 80a03cc | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 562 | } else if (PendingQueue[i]->getDepth() < MinDepth) |
| 563 | MinDepth = PendingQueue[i]->getDepth(); |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 564 | } |
David Goodwin | ebd694b | 2009-08-11 17:35:23 +0000 | [diff] [blame] | 565 | |
Andrew Trick | 10ffc2b | 2010-12-24 05:03:26 +0000 | [diff] [blame] | 566 | DEBUG(dbgs() << "\n*** Examining Available\n"; AvailableQueue.dump(this)); |
David Goodwin | ebd694b | 2009-08-11 17:35:23 +0000 | [diff] [blame] | 567 | |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 568 | SUnit *FoundSUnit = nullptr, *NotPreferredSUnit = nullptr; |
Dan Gohman | ceac7c3 | 2009-01-16 01:33:36 +0000 | [diff] [blame] | 569 | bool HasNoopHazards = false; |
| 570 | while (!AvailableQueue.empty()) { |
| 571 | SUnit *CurSUnit = AvailableQueue.pop(); |
| 572 | |
| 573 | ScheduleHazardRecognizer::HazardType HT = |
Andrew Trick | 10ffc2b | 2010-12-24 05:03:26 +0000 | [diff] [blame] | 574 | HazardRec->getHazardType(CurSUnit, 0/*no stalls*/); |
Dan Gohman | ceac7c3 | 2009-01-16 01:33:36 +0000 | [diff] [blame] | 575 | if (HT == ScheduleHazardRecognizer::NoHazard) { |
Hal Finkel | 4fd3b1d | 2013-12-11 22:33:43 +0000 | [diff] [blame] | 576 | if (HazardRec->ShouldPreferAnother(CurSUnit)) { |
| 577 | if (!NotPreferredSUnit) { |
NAKAMURA Takumi | f51a34e | 2014-10-29 15:23:11 +0000 | [diff] [blame] | 578 | // If this is the first non-preferred node for this cycle, then |
| 579 | // record it and continue searching for a preferred node. If this |
| 580 | // is not the first non-preferred node, then treat it as though |
| 581 | // there had been a hazard. |
Hal Finkel | 4fd3b1d | 2013-12-11 22:33:43 +0000 | [diff] [blame] | 582 | NotPreferredSUnit = CurSUnit; |
| 583 | continue; |
| 584 | } |
| 585 | } else { |
| 586 | FoundSUnit = CurSUnit; |
| 587 | break; |
| 588 | } |
Dan Gohman | ceac7c3 | 2009-01-16 01:33:36 +0000 | [diff] [blame] | 589 | } |
| 590 | |
| 591 | // Remember if this is a noop hazard. |
| 592 | HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard; |
| 593 | |
| 594 | NotReady.push_back(CurSUnit); |
| 595 | } |
| 596 | |
Hal Finkel | 4fd3b1d | 2013-12-11 22:33:43 +0000 | [diff] [blame] | 597 | // If we have a non-preferred node, push it back onto the available list. |
| 598 | // If we did not find a preferred node, then schedule this first |
| 599 | // non-preferred node. |
| 600 | if (NotPreferredSUnit) { |
| 601 | if (!FoundSUnit) { |
| 602 | DEBUG(dbgs() << "*** Will schedule a non-preferred instruction...\n"); |
| 603 | FoundSUnit = NotPreferredSUnit; |
| 604 | } else { |
| 605 | AvailableQueue.push(NotPreferredSUnit); |
| 606 | } |
| 607 | |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 608 | NotPreferredSUnit = nullptr; |
Hal Finkel | 4fd3b1d | 2013-12-11 22:33:43 +0000 | [diff] [blame] | 609 | } |
| 610 | |
Dan Gohman | ceac7c3 | 2009-01-16 01:33:36 +0000 | [diff] [blame] | 611 | // Add the nodes that aren't ready back onto the available list. |
| 612 | if (!NotReady.empty()) { |
| 613 | AvailableQueue.push_all(NotReady); |
| 614 | NotReady.clear(); |
| 615 | } |
| 616 | |
David Goodwin | 8501dbbe | 2009-11-03 20:57:50 +0000 | [diff] [blame] | 617 | // If we found a node to schedule... |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 618 | if (FoundSUnit) { |
Hal Finkel | 4fd3b1d | 2013-12-11 22:33:43 +0000 | [diff] [blame] | 619 | // If we need to emit noops prior to this instruction, then do so. |
| 620 | unsigned NumPreNoops = HazardRec->PreEmitNoops(FoundSUnit); |
| 621 | for (unsigned i = 0; i != NumPreNoops; ++i) |
| 622 | emitNoop(CurCycle); |
| 623 | |
David Goodwin | 8501dbbe | 2009-11-03 20:57:50 +0000 | [diff] [blame] | 624 | // ... schedule the node... |
David Goodwin | 80a03cc | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 625 | ScheduleNodeTopDown(FoundSUnit, CurCycle); |
Dan Gohman | ceac7c3 | 2009-01-16 01:33:36 +0000 | [diff] [blame] | 626 | HazardRec->EmitInstruction(FoundSUnit); |
Benjamin Kramer | e3c9d23 | 2009-09-06 12:10:17 +0000 | [diff] [blame] | 627 | CycleHasInsts = true; |
Andrew Trick | 18c9b37 | 2011-06-01 03:27:56 +0000 | [diff] [blame] | 628 | if (HazardRec->atIssueLimit()) { |
| 629 | DEBUG(dbgs() << "*** Max instructions per cycle " << CurCycle << '\n'); |
| 630 | HazardRec->AdvanceCycle(); |
| 631 | ++CurCycle; |
| 632 | CycleHasInsts = false; |
| 633 | } |
Dan Gohman | ceac7c3 | 2009-01-16 01:33:36 +0000 | [diff] [blame] | 634 | } else { |
Benjamin Kramer | e3c9d23 | 2009-09-06 12:10:17 +0000 | [diff] [blame] | 635 | if (CycleHasInsts) { |
David Greene | aa8ce38 | 2010-01-05 01:26:01 +0000 | [diff] [blame] | 636 | DEBUG(dbgs() << "*** Finished cycle " << CurCycle << '\n'); |
David Goodwin | 1f8c7a7 | 2009-08-12 21:47:46 +0000 | [diff] [blame] | 637 | HazardRec->AdvanceCycle(); |
| 638 | } else if (!HasNoopHazards) { |
| 639 | // Otherwise, we have a pipeline stall, but no other problem, |
| 640 | // just advance the current cycle and try again. |
David Greene | aa8ce38 | 2010-01-05 01:26:01 +0000 | [diff] [blame] | 641 | DEBUG(dbgs() << "*** Stall in cycle " << CurCycle << '\n'); |
David Goodwin | 1f8c7a7 | 2009-08-12 21:47:46 +0000 | [diff] [blame] | 642 | HazardRec->AdvanceCycle(); |
David Goodwin | 80a03cc | 2009-11-20 19:32:48 +0000 | [diff] [blame] | 643 | ++NumStalls; |
David Goodwin | 1f8c7a7 | 2009-08-12 21:47:46 +0000 | [diff] [blame] | 644 | } else { |
| 645 | // Otherwise, we have no instructions to issue and we have instructions |
| 646 | // that will fault if we don't do this right. This is the case for |
| 647 | // processors without pipeline interlocks and other cases. |
Hal Finkel | 4fd3b1d | 2013-12-11 22:33:43 +0000 | [diff] [blame] | 648 | emitNoop(CurCycle); |
David Goodwin | 1f8c7a7 | 2009-08-12 21:47:46 +0000 | [diff] [blame] | 649 | } |
| 650 | |
Dan Gohman | ceac7c3 | 2009-01-16 01:33:36 +0000 | [diff] [blame] | 651 | ++CurCycle; |
Benjamin Kramer | e3c9d23 | 2009-09-06 12:10:17 +0000 | [diff] [blame] | 652 | CycleHasInsts = false; |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 653 | } |
| 654 | } |
| 655 | |
| 656 | #ifndef NDEBUG |
Andrew Trick | 46a5866 | 2012-03-07 05:21:36 +0000 | [diff] [blame] | 657 | unsigned ScheduledNodes = VerifyScheduledDAG(/*isBottomUp=*/false); |
| 658 | unsigned Noops = 0; |
| 659 | for (unsigned i = 0, e = Sequence.size(); i != e; ++i) |
| 660 | if (!Sequence[i]) |
| 661 | ++Noops; |
| 662 | assert(Sequence.size() - Noops == ScheduledNodes && |
| 663 | "The number of nodes scheduled doesn't match the expected number!"); |
| 664 | #endif // NDEBUG |
Dan Gohman | 60cb69e | 2008-11-19 23:18:57 +0000 | [diff] [blame] | 665 | } |
Andrew Trick | e932bb7 | 2012-03-07 05:21:44 +0000 | [diff] [blame] | 666 | |
| 667 | // EmitSchedule - Emit the machine code in scheduled order. |
| 668 | void SchedulePostRATDList::EmitSchedule() { |
Andrew Trick | 8c207e4 | 2012-03-09 04:29:02 +0000 | [diff] [blame] | 669 | RegionBegin = RegionEnd; |
Andrew Trick | e932bb7 | 2012-03-07 05:21:44 +0000 | [diff] [blame] | 670 | |
| 671 | // If first instruction was a DBG_VALUE then put it back. |
| 672 | if (FirstDbgValue) |
Andrew Trick | 8c207e4 | 2012-03-09 04:29:02 +0000 | [diff] [blame] | 673 | BB->splice(RegionEnd, BB, FirstDbgValue); |
Andrew Trick | e932bb7 | 2012-03-07 05:21:44 +0000 | [diff] [blame] | 674 | |
| 675 | // Then re-insert them according to the given schedule. |
| 676 | for (unsigned i = 0, e = Sequence.size(); i != e; i++) { |
| 677 | if (SUnit *SU = Sequence[i]) |
Andrew Trick | 8c207e4 | 2012-03-09 04:29:02 +0000 | [diff] [blame] | 678 | BB->splice(RegionEnd, BB, SU->getInstr()); |
Andrew Trick | e932bb7 | 2012-03-07 05:21:44 +0000 | [diff] [blame] | 679 | else |
| 680 | // Null SUnit* is a noop. |
Andrew Trick | 8c207e4 | 2012-03-09 04:29:02 +0000 | [diff] [blame] | 681 | TII->insertNoop(*BB, RegionEnd); |
Andrew Trick | e932bb7 | 2012-03-07 05:21:44 +0000 | [diff] [blame] | 682 | |
| 683 | // Update the Begin iterator, as the first instruction in the block |
| 684 | // may have been scheduled later. |
| 685 | if (i == 0) |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 686 | RegionBegin = std::prev(RegionEnd); |
Andrew Trick | e932bb7 | 2012-03-07 05:21:44 +0000 | [diff] [blame] | 687 | } |
| 688 | |
| 689 | // Reinsert any remaining debug_values. |
| 690 | for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator |
| 691 | DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) { |
Benjamin Kramer | b6d0bd4 | 2014-03-02 12:27:27 +0000 | [diff] [blame] | 692 | std::pair<MachineInstr *, MachineInstr *> P = *std::prev(DI); |
Andrew Trick | e932bb7 | 2012-03-07 05:21:44 +0000 | [diff] [blame] | 693 | MachineInstr *DbgValue = P.first; |
| 694 | MachineBasicBlock::iterator OrigPrivMI = P.second; |
| 695 | BB->splice(++OrigPrivMI, BB, DbgValue); |
| 696 | } |
| 697 | DbgValues.clear(); |
Craig Topper | c0196b1 | 2014-04-14 00:51:57 +0000 | [diff] [blame] | 698 | FirstDbgValue = nullptr; |
Andrew Trick | e932bb7 | 2012-03-07 05:21:44 +0000 | [diff] [blame] | 699 | } |