Bug Summary

File:llvm/lib/CodeGen/MachinePipeliner.cpp
Warning:line 1923, column 13
Value stored to 'Order' is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name MachinePipeliner.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -mframe-pointer=none -fmath-errno -fno-rounding-math -masm-verbose -mconstructor-aliases -munwind-tables -target-cpu x86-64 -dwarf-column-info -fno-split-dwarf-inlining -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-11/lib/clang/11.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/include -I /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-11/lib/clang/11.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/build-llvm/lib/CodeGen -fdebug-prefix-map=/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2020-03-09-184146-41876-1 -x c++ /build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp
1//===- MachinePipeliner.cpp - Machine Software Pipeliner Pass -------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// An implementation of the Swing Modulo Scheduling (SMS) software pipeliner.
10//
11// This SMS implementation is a target-independent back-end pass. When enabled,
12// the pass runs just prior to the register allocation pass, while the machine
13// IR is in SSA form. If software pipelining is successful, then the original
14// loop is replaced by the optimized loop. The optimized loop contains one or
15// more prolog blocks, the pipelined kernel, and one or more epilog blocks. If
16// the instructions cannot be scheduled in a given MII, we increase the MII by
17// one and try again.
18//
19// The SMS implementation is an extension of the ScheduleDAGInstrs class. We
20// represent loop carried dependences in the DAG as order edges to the Phi
21// nodes. We also perform several passes over the DAG to eliminate unnecessary
22// edges that inhibit the ability to pipeline. The implementation uses the
23// DFAPacketizer class to compute the minimum initiation interval and the check
24// where an instruction may be inserted in the pipelined schedule.
25//
26// In order for the SMS pass to work, several target specific hooks need to be
27// implemented to get information about the loop structure and to rewrite
28// instructions.
29//
30//===----------------------------------------------------------------------===//
31
32#include "llvm/ADT/ArrayRef.h"
33#include "llvm/ADT/BitVector.h"
34#include "llvm/ADT/DenseMap.h"
35#include "llvm/ADT/MapVector.h"
36#include "llvm/ADT/PriorityQueue.h"
37#include "llvm/ADT/SetVector.h"
38#include "llvm/ADT/SmallPtrSet.h"
39#include "llvm/ADT/SmallSet.h"
40#include "llvm/ADT/SmallVector.h"
41#include "llvm/ADT/Statistic.h"
42#include "llvm/ADT/iterator_range.h"
43#include "llvm/Analysis/AliasAnalysis.h"
44#include "llvm/Analysis/MemoryLocation.h"
45#include "llvm/Analysis/ValueTracking.h"
46#include "llvm/CodeGen/DFAPacketizer.h"
47#include "llvm/CodeGen/LiveIntervals.h"
48#include "llvm/CodeGen/MachineBasicBlock.h"
49#include "llvm/CodeGen/MachineDominators.h"
50#include "llvm/CodeGen/MachineFunction.h"
51#include "llvm/CodeGen/MachineFunctionPass.h"
52#include "llvm/CodeGen/MachineInstr.h"
53#include "llvm/CodeGen/MachineInstrBuilder.h"
54#include "llvm/CodeGen/MachineLoopInfo.h"
55#include "llvm/CodeGen/MachineMemOperand.h"
56#include "llvm/CodeGen/MachineOperand.h"
57#include "llvm/CodeGen/MachinePipeliner.h"
58#include "llvm/CodeGen/MachineRegisterInfo.h"
59#include "llvm/CodeGen/ModuloSchedule.h"
60#include "llvm/CodeGen/RegisterPressure.h"
61#include "llvm/CodeGen/ScheduleDAG.h"
62#include "llvm/CodeGen/ScheduleDAGMutation.h"
63#include "llvm/CodeGen/TargetOpcodes.h"
64#include "llvm/CodeGen/TargetRegisterInfo.h"
65#include "llvm/CodeGen/TargetSubtargetInfo.h"
66#include "llvm/Config/llvm-config.h"
67#include "llvm/IR/Attributes.h"
68#include "llvm/IR/DebugLoc.h"
69#include "llvm/IR/Function.h"
70#include "llvm/MC/LaneBitmask.h"
71#include "llvm/MC/MCInstrDesc.h"
72#include "llvm/MC/MCInstrItineraries.h"
73#include "llvm/MC/MCRegisterInfo.h"
74#include "llvm/Pass.h"
75#include "llvm/Support/CommandLine.h"
76#include "llvm/Support/Compiler.h"
77#include "llvm/Support/Debug.h"
78#include "llvm/Support/MathExtras.h"
79#include "llvm/Support/raw_ostream.h"
80#include <algorithm>
81#include <cassert>
82#include <climits>
83#include <cstdint>
84#include <deque>
85#include <functional>
86#include <iterator>
87#include <map>
88#include <memory>
89#include <tuple>
90#include <utility>
91#include <vector>
92
93using namespace llvm;
94
95#define DEBUG_TYPE"pipeliner" "pipeliner"
96
97STATISTIC(NumTrytoPipeline, "Number of loops that we attempt to pipeline")static llvm::Statistic NumTrytoPipeline = {"pipeliner", "NumTrytoPipeline"
, "Number of loops that we attempt to pipeline"}
;
98STATISTIC(NumPipelined, "Number of loops software pipelined")static llvm::Statistic NumPipelined = {"pipeliner", "NumPipelined"
, "Number of loops software pipelined"}
;
99STATISTIC(NumNodeOrderIssues, "Number of node order issues found")static llvm::Statistic NumNodeOrderIssues = {"pipeliner", "NumNodeOrderIssues"
, "Number of node order issues found"}
;
100STATISTIC(NumFailBranch, "Pipeliner abort due to unknown branch")static llvm::Statistic NumFailBranch = {"pipeliner", "NumFailBranch"
, "Pipeliner abort due to unknown branch"}
;
101STATISTIC(NumFailLoop, "Pipeliner abort due to unsupported loop")static llvm::Statistic NumFailLoop = {"pipeliner", "NumFailLoop"
, "Pipeliner abort due to unsupported loop"}
;
102STATISTIC(NumFailPreheader, "Pipeliner abort due to missing preheader")static llvm::Statistic NumFailPreheader = {"pipeliner", "NumFailPreheader"
, "Pipeliner abort due to missing preheader"}
;
103STATISTIC(NumFailLargeMaxMII, "Pipeliner abort due to MaxMII too large")static llvm::Statistic NumFailLargeMaxMII = {"pipeliner", "NumFailLargeMaxMII"
, "Pipeliner abort due to MaxMII too large"}
;
104STATISTIC(NumFailZeroMII, "Pipeliner abort due to zero MII")static llvm::Statistic NumFailZeroMII = {"pipeliner", "NumFailZeroMII"
, "Pipeliner abort due to zero MII"}
;
105STATISTIC(NumFailNoSchedule, "Pipeliner abort due to no schedule found")static llvm::Statistic NumFailNoSchedule = {"pipeliner", "NumFailNoSchedule"
, "Pipeliner abort due to no schedule found"}
;
106STATISTIC(NumFailZeroStage, "Pipeliner abort due to zero stage")static llvm::Statistic NumFailZeroStage = {"pipeliner", "NumFailZeroStage"
, "Pipeliner abort due to zero stage"}
;
107STATISTIC(NumFailLargeMaxStage, "Pipeliner abort due to too many stages")static llvm::Statistic NumFailLargeMaxStage = {"pipeliner", "NumFailLargeMaxStage"
, "Pipeliner abort due to too many stages"}
;
108
109/// A command line option to turn software pipelining on or off.
110static cl::opt<bool> EnableSWP("enable-pipeliner", cl::Hidden, cl::init(true),
111 cl::ZeroOrMore,
112 cl::desc("Enable Software Pipelining"));
113
114/// A command line option to enable SWP at -Os.
115static cl::opt<bool> EnableSWPOptSize("enable-pipeliner-opt-size",
116 cl::desc("Enable SWP at Os."), cl::Hidden,
117 cl::init(false));
118
119/// A command line argument to limit minimum initial interval for pipelining.
120static cl::opt<int> SwpMaxMii("pipeliner-max-mii",
121 cl::desc("Size limit for the MII."),
122 cl::Hidden, cl::init(27));
123
124/// A command line argument to limit the number of stages in the pipeline.
125static cl::opt<int>
126 SwpMaxStages("pipeliner-max-stages",
127 cl::desc("Maximum stages allowed in the generated scheduled."),
128 cl::Hidden, cl::init(3));
129
130/// A command line option to disable the pruning of chain dependences due to
131/// an unrelated Phi.
132static cl::opt<bool>
133 SwpPruneDeps("pipeliner-prune-deps",
134 cl::desc("Prune dependences between unrelated Phi nodes."),
135 cl::Hidden, cl::init(true));
136
137/// A command line option to disable the pruning of loop carried order
138/// dependences.
139static cl::opt<bool>
140 SwpPruneLoopCarried("pipeliner-prune-loop-carried",
141 cl::desc("Prune loop carried order dependences."),
142 cl::Hidden, cl::init(true));
143
144#ifndef NDEBUG
145static cl::opt<int> SwpLoopLimit("pipeliner-max", cl::Hidden, cl::init(-1));
146#endif
147
148static cl::opt<bool> SwpIgnoreRecMII("pipeliner-ignore-recmii",
149 cl::ReallyHidden, cl::init(false),
150 cl::ZeroOrMore, cl::desc("Ignore RecMII"));
151
152static cl::opt<bool> SwpShowResMask("pipeliner-show-mask", cl::Hidden,
153 cl::init(false));
154static cl::opt<bool> SwpDebugResource("pipeliner-dbg-res", cl::Hidden,
155 cl::init(false));
156
157static cl::opt<bool> EmitTestAnnotations(
158 "pipeliner-annotate-for-testing", cl::Hidden, cl::init(false),
159 cl::desc("Instead of emitting the pipelined code, annotate instructions "
160 "with the generated schedule for feeding into the "
161 "-modulo-schedule-test pass"));
162
163static cl::opt<bool> ExperimentalCodeGen(
164 "pipeliner-experimental-cg", cl::Hidden, cl::init(false),
165 cl::desc(
166 "Use the experimental peeling code generator for software pipelining"));
167
168namespace llvm {
169
170// A command line option to enable the CopyToPhi DAG mutation.
171cl::opt<bool>
172 SwpEnableCopyToPhi("pipeliner-enable-copytophi", cl::ReallyHidden,
173 cl::init(true), cl::ZeroOrMore,
174 cl::desc("Enable CopyToPhi DAG Mutation"));
175
176} // end namespace llvm
177
178unsigned SwingSchedulerDAG::Circuits::MaxPaths = 5;
179char MachinePipeliner::ID = 0;
180#ifndef NDEBUG
181int MachinePipeliner::NumTries = 0;
182#endif
183char &llvm::MachinePipelinerID = MachinePipeliner::ID;
184
185INITIALIZE_PASS_BEGIN(MachinePipeliner, DEBUG_TYPE,static void *initializeMachinePipelinerPassOnce(PassRegistry &
Registry) {
186 "Modulo Software Pipelining", false, false)static void *initializeMachinePipelinerPassOnce(PassRegistry &
Registry) {
187INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);
188INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)initializeMachineLoopInfoPass(Registry);
189INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)initializeMachineDominatorTreePass(Registry);
190INITIALIZE_PASS_DEPENDENCY(LiveIntervals)initializeLiveIntervalsPass(Registry);
191INITIALIZE_PASS_END(MachinePipeliner, DEBUG_TYPE,PassInfo *PI = new PassInfo( "Modulo Software Pipelining", "pipeliner"
, &MachinePipeliner::ID, PassInfo::NormalCtor_t(callDefaultCtor
<MachinePipeliner>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeMachinePipelinerPassFlag
; void llvm::initializeMachinePipelinerPass(PassRegistry &
Registry) { llvm::call_once(InitializeMachinePipelinerPassFlag
, initializeMachinePipelinerPassOnce, std::ref(Registry)); }
192 "Modulo Software Pipelining", false, false)PassInfo *PI = new PassInfo( "Modulo Software Pipelining", "pipeliner"
, &MachinePipeliner::ID, PassInfo::NormalCtor_t(callDefaultCtor
<MachinePipeliner>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeMachinePipelinerPassFlag
; void llvm::initializeMachinePipelinerPass(PassRegistry &
Registry) { llvm::call_once(InitializeMachinePipelinerPassFlag
, initializeMachinePipelinerPassOnce, std::ref(Registry)); }
193
194/// The "main" function for implementing Swing Modulo Scheduling.
195bool MachinePipeliner::runOnMachineFunction(MachineFunction &mf) {
196 if (skipFunction(mf.getFunction()))
197 return false;
198
199 if (!EnableSWP)
200 return false;
201
202 if (mf.getFunction().getAttributes().hasAttribute(
203 AttributeList::FunctionIndex, Attribute::OptimizeForSize) &&
204 !EnableSWPOptSize.getPosition())
205 return false;
206
207 if (!mf.getSubtarget().enableMachinePipeliner())
208 return false;
209
210 // Cannot pipeline loops without instruction itineraries if we are using
211 // DFA for the pipeliner.
212 if (mf.getSubtarget().useDFAforSMS() &&
213 (!mf.getSubtarget().getInstrItineraryData() ||
214 mf.getSubtarget().getInstrItineraryData()->isEmpty()))
215 return false;
216
217 MF = &mf;
218 MLI = &getAnalysis<MachineLoopInfo>();
219 MDT = &getAnalysis<MachineDominatorTree>();
220 TII = MF->getSubtarget().getInstrInfo();
221 RegClassInfo.runOnMachineFunction(*MF);
222
223 for (auto &L : *MLI)
224 scheduleLoop(*L);
225
226 return false;
227}
228
229/// Attempt to perform the SMS algorithm on the specified loop. This function is
230/// the main entry point for the algorithm. The function identifies candidate
231/// loops, calculates the minimum initiation interval, and attempts to schedule
232/// the loop.
233bool MachinePipeliner::scheduleLoop(MachineLoop &L) {
234 bool Changed = false;
235 for (auto &InnerLoop : L)
236 Changed |= scheduleLoop(*InnerLoop);
237
238#ifndef NDEBUG
239 // Stop trying after reaching the limit (if any).
240 int Limit = SwpLoopLimit;
241 if (Limit >= 0) {
242 if (NumTries >= SwpLoopLimit)
243 return Changed;
244 NumTries++;
245 }
246#endif
247
248 setPragmaPipelineOptions(L);
249 if (!canPipelineLoop(L)) {
250 LLVM_DEBUG(dbgs() << "\n!!! Can not pipeline loop.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "\n!!! Can not pipeline loop.\n"
; } } while (false)
;
251 return Changed;
252 }
253
254 ++NumTrytoPipeline;
255
256 Changed = swingModuloScheduler(L);
257
258 return Changed;
259}
260
261void MachinePipeliner::setPragmaPipelineOptions(MachineLoop &L) {
262 MachineBasicBlock *LBLK = L.getTopBlock();
263
264 if (LBLK == nullptr)
265 return;
266
267 const BasicBlock *BBLK = LBLK->getBasicBlock();
268 if (BBLK == nullptr)
269 return;
270
271 const Instruction *TI = BBLK->getTerminator();
272 if (TI == nullptr)
273 return;
274
275 MDNode *LoopID = TI->getMetadata(LLVMContext::MD_loop);
276 if (LoopID == nullptr)
277 return;
278
279 assert(LoopID->getNumOperands() > 0 && "requires atleast one operand")((LoopID->getNumOperands() > 0 && "requires atleast one operand"
) ? static_cast<void> (0) : __assert_fail ("LoopID->getNumOperands() > 0 && \"requires atleast one operand\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 279, __PRETTY_FUNCTION__))
;
280 assert(LoopID->getOperand(0) == LoopID && "invalid loop")((LoopID->getOperand(0) == LoopID && "invalid loop"
) ? static_cast<void> (0) : __assert_fail ("LoopID->getOperand(0) == LoopID && \"invalid loop\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 280, __PRETTY_FUNCTION__))
;
281
282 for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
283 MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
284
285 if (MD == nullptr)
286 continue;
287
288 MDString *S = dyn_cast<MDString>(MD->getOperand(0));
289
290 if (S == nullptr)
291 continue;
292
293 if (S->getString() == "llvm.loop.pipeline.initiationinterval") {
294 assert(MD->getNumOperands() == 2 &&((MD->getNumOperands() == 2 && "Pipeline initiation interval hint metadata should have two operands."
) ? static_cast<void> (0) : __assert_fail ("MD->getNumOperands() == 2 && \"Pipeline initiation interval hint metadata should have two operands.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 295, __PRETTY_FUNCTION__))
295 "Pipeline initiation interval hint metadata should have two operands.")((MD->getNumOperands() == 2 && "Pipeline initiation interval hint metadata should have two operands."
) ? static_cast<void> (0) : __assert_fail ("MD->getNumOperands() == 2 && \"Pipeline initiation interval hint metadata should have two operands.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 295, __PRETTY_FUNCTION__))
;
296 II_setByPragma =
297 mdconst::extract<ConstantInt>(MD->getOperand(1))->getZExtValue();
298 assert(II_setByPragma >= 1 && "Pipeline initiation interval must be positive.")((II_setByPragma >= 1 && "Pipeline initiation interval must be positive."
) ? static_cast<void> (0) : __assert_fail ("II_setByPragma >= 1 && \"Pipeline initiation interval must be positive.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 298, __PRETTY_FUNCTION__))
;
299 } else if (S->getString() == "llvm.loop.pipeline.disable") {
300 disabledByPragma = true;
301 }
302 }
303}
304
305/// Return true if the loop can be software pipelined. The algorithm is
306/// restricted to loops with a single basic block. Make sure that the
307/// branch in the loop can be analyzed.
308bool MachinePipeliner::canPipelineLoop(MachineLoop &L) {
309 if (L.getNumBlocks() != 1)
310 return false;
311
312 if (disabledByPragma)
313 return false;
314
315 // Check if the branch can't be understood because we can't do pipelining
316 // if that's the case.
317 LI.TBB = nullptr;
318 LI.FBB = nullptr;
319 LI.BrCond.clear();
320 if (TII->analyzeBranch(*L.getHeader(), LI.TBB, LI.FBB, LI.BrCond)) {
321 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "Unable to analyzeBranch, can NOT pipeline current Loop\n"
; } } while (false)
322 dbgs() << "Unable to analyzeBranch, can NOT pipeline current Loop\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "Unable to analyzeBranch, can NOT pipeline current Loop\n"
; } } while (false)
;
323 NumFailBranch++;
324 return false;
325 }
326
327 LI.LoopInductionVar = nullptr;
328 LI.LoopCompare = nullptr;
329 if (!TII->analyzeLoopForPipelining(L.getTopBlock())) {
330 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "Unable to analyzeLoop, can NOT pipeline current Loop\n"
; } } while (false)
331 dbgs() << "Unable to analyzeLoop, can NOT pipeline current Loop\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "Unable to analyzeLoop, can NOT pipeline current Loop\n"
; } } while (false)
;
332 NumFailLoop++;
333 return false;
334 }
335
336 if (!L.getLoopPreheader()) {
337 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "Preheader not found, can NOT pipeline current Loop\n"
; } } while (false)
338 dbgs() << "Preheader not found, can NOT pipeline current Loop\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "Preheader not found, can NOT pipeline current Loop\n"
; } } while (false)
;
339 NumFailPreheader++;
340 return false;
341 }
342
343 // Remove any subregisters from inputs to phi nodes.
344 preprocessPhiNodes(*L.getHeader());
345 return true;
346}
347
348void MachinePipeliner::preprocessPhiNodes(MachineBasicBlock &B) {
349 MachineRegisterInfo &MRI = MF->getRegInfo();
350 SlotIndexes &Slots = *getAnalysis<LiveIntervals>().getSlotIndexes();
351
352 for (MachineInstr &PI : make_range(B.begin(), B.getFirstNonPHI())) {
353 MachineOperand &DefOp = PI.getOperand(0);
354 assert(DefOp.getSubReg() == 0)((DefOp.getSubReg() == 0) ? static_cast<void> (0) : __assert_fail
("DefOp.getSubReg() == 0", "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 354, __PRETTY_FUNCTION__))
;
355 auto *RC = MRI.getRegClass(DefOp.getReg());
356
357 for (unsigned i = 1, n = PI.getNumOperands(); i != n; i += 2) {
358 MachineOperand &RegOp = PI.getOperand(i);
359 if (RegOp.getSubReg() == 0)
360 continue;
361
362 // If the operand uses a subregister, replace it with a new register
363 // without subregisters, and generate a copy to the new register.
364 Register NewReg = MRI.createVirtualRegister(RC);
365 MachineBasicBlock &PredB = *PI.getOperand(i+1).getMBB();
366 MachineBasicBlock::iterator At = PredB.getFirstTerminator();
367 const DebugLoc &DL = PredB.findDebugLoc(At);
368 auto Copy = BuildMI(PredB, At, DL, TII->get(TargetOpcode::COPY), NewReg)
369 .addReg(RegOp.getReg(), getRegState(RegOp),
370 RegOp.getSubReg());
371 Slots.insertMachineInstrInMaps(*Copy);
372 RegOp.setReg(NewReg);
373 RegOp.setSubReg(0);
374 }
375 }
376}
377
378/// The SMS algorithm consists of the following main steps:
379/// 1. Computation and analysis of the dependence graph.
380/// 2. Ordering of the nodes (instructions).
381/// 3. Attempt to Schedule the loop.
382bool MachinePipeliner::swingModuloScheduler(MachineLoop &L) {
383 assert(L.getBlocks().size() == 1 && "SMS works on single blocks only.")((L.getBlocks().size() == 1 && "SMS works on single blocks only."
) ? static_cast<void> (0) : __assert_fail ("L.getBlocks().size() == 1 && \"SMS works on single blocks only.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 383, __PRETTY_FUNCTION__))
;
384
385 SwingSchedulerDAG SMS(*this, L, getAnalysis<LiveIntervals>(), RegClassInfo,
386 II_setByPragma);
387
388 MachineBasicBlock *MBB = L.getHeader();
389 // The kernel should not include any terminator instructions. These
390 // will be added back later.
391 SMS.startBlock(MBB);
392
393 // Compute the number of 'real' instructions in the basic block by
394 // ignoring terminators.
395 unsigned size = MBB->size();
396 for (MachineBasicBlock::iterator I = MBB->getFirstTerminator(),
397 E = MBB->instr_end();
398 I != E; ++I, --size)
399 ;
400
401 SMS.enterRegion(MBB, MBB->begin(), MBB->getFirstTerminator(), size);
402 SMS.schedule();
403 SMS.exitRegion();
404
405 SMS.finishBlock();
406 return SMS.hasNewSchedule();
407}
408
409void SwingSchedulerDAG::setMII(unsigned ResMII, unsigned RecMII) {
410 if (II_setByPragma > 0)
411 MII = II_setByPragma;
412 else
413 MII = std::max(ResMII, RecMII);
414}
415
416void SwingSchedulerDAG::setMAX_II() {
417 if (II_setByPragma > 0)
418 MAX_II = II_setByPragma;
419 else
420 MAX_II = MII + 10;
421}
422
423/// We override the schedule function in ScheduleDAGInstrs to implement the
424/// scheduling part of the Swing Modulo Scheduling algorithm.
425void SwingSchedulerDAG::schedule() {
426 AliasAnalysis *AA = &Pass.getAnalysis<AAResultsWrapperPass>().getAAResults();
427 buildSchedGraph(AA);
428 addLoopCarriedDependences(AA);
429 updatePhiDependences();
430 Topo.InitDAGTopologicalSorting();
431 changeDependences();
432 postprocessDAG();
433 LLVM_DEBUG(dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dump(); } } while (false)
;
434
435 NodeSetType NodeSets;
436 findCircuits(NodeSets);
437 NodeSetType Circuits = NodeSets;
438
439 // Calculate the MII.
440 unsigned ResMII = calculateResMII();
441 unsigned RecMII = calculateRecMII(NodeSets);
442
443 fuseRecs(NodeSets);
444
445 // This flag is used for testing and can cause correctness problems.
446 if (SwpIgnoreRecMII)
447 RecMII = 0;
448
449 setMII(ResMII, RecMII);
450 setMAX_II();
451
452 LLVM_DEBUG(dbgs() << "MII = " << MII << " MAX_II = " << MAX_IIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "MII = " << MII <<
" MAX_II = " << MAX_II << " (rec=" << RecMII
<< ", res=" << ResMII << ")\n"; } } while (
false)
453 << " (rec=" << RecMII << ", res=" << ResMII << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "MII = " << MII <<
" MAX_II = " << MAX_II << " (rec=" << RecMII
<< ", res=" << ResMII << ")\n"; } } while (
false)
;
454
455 // Can't schedule a loop without a valid MII.
456 if (MII == 0) {
457 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "0 is not a valid Minimal Initiation Interval, can NOT schedule\n"
; } } while (false)
458 dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "0 is not a valid Minimal Initiation Interval, can NOT schedule\n"
; } } while (false)
459 << "0 is not a valid Minimal Initiation Interval, can NOT schedule\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "0 is not a valid Minimal Initiation Interval, can NOT schedule\n"
; } } while (false)
;
460 NumFailZeroMII++;
461 return;
462 }
463
464 // Don't pipeline large loops.
465 if (SwpMaxMii != -1 && (int)MII > SwpMaxMii) {
466 LLVM_DEBUG(dbgs() << "MII > " << SwpMaxMiido { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "MII > " << SwpMaxMii
<< ", we don't pipleline large loops\n"; } } while (false
)
467 << ", we don't pipleline large loops\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "MII > " << SwpMaxMii
<< ", we don't pipleline large loops\n"; } } while (false
)
;
468 NumFailLargeMaxMII++;
469 return;
470 }
471
472 computeNodeFunctions(NodeSets);
473
474 registerPressureFilter(NodeSets);
475
476 colocateNodeSets(NodeSets);
477
478 checkNodeSets(NodeSets);
479
480 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (auto &I : NodeSets) { dbgs() <<
" Rec NodeSet "; I.dump(); } }; } } while (false)
481 for (auto &I : NodeSets) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (auto &I : NodeSets) { dbgs() <<
" Rec NodeSet "; I.dump(); } }; } } while (false)
482 dbgs() << " Rec NodeSet ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (auto &I : NodeSets) { dbgs() <<
" Rec NodeSet "; I.dump(); } }; } } while (false)
483 I.dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (auto &I : NodeSets) { dbgs() <<
" Rec NodeSet "; I.dump(); } }; } } while (false)
484 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (auto &I : NodeSets) { dbgs() <<
" Rec NodeSet "; I.dump(); } }; } } while (false)
485 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (auto &I : NodeSets) { dbgs() <<
" Rec NodeSet "; I.dump(); } }; } } while (false)
;
486
487 llvm::stable_sort(NodeSets, std::greater<NodeSet>());
488
489 groupRemainingNodes(NodeSets);
490
491 removeDuplicateNodes(NodeSets);
492
493 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (auto &I : NodeSets) { dbgs() <<
" NodeSet "; I.dump(); } }; } } while (false)
494 for (auto &I : NodeSets) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (auto &I : NodeSets) { dbgs() <<
" NodeSet "; I.dump(); } }; } } while (false)
495 dbgs() << " NodeSet ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (auto &I : NodeSets) { dbgs() <<
" NodeSet "; I.dump(); } }; } } while (false)
496 I.dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (auto &I : NodeSets) { dbgs() <<
" NodeSet "; I.dump(); } }; } } while (false)
497 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (auto &I : NodeSets) { dbgs() <<
" NodeSet "; I.dump(); } }; } } while (false)
498 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (auto &I : NodeSets) { dbgs() <<
" NodeSet "; I.dump(); } }; } } while (false)
;
499
500 computeNodeOrder(NodeSets);
501
502 // check for node order issues
503 checkValidNodeOrder(Circuits);
504
505 SMSchedule Schedule(Pass.MF);
506 Scheduled = schedulePipeline(Schedule);
507
508 if (!Scheduled){
509 LLVM_DEBUG(dbgs() << "No schedule found, return\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "No schedule found, return\n"
; } } while (false)
;
510 NumFailNoSchedule++;
511 return;
512 }
513
514 unsigned numStages = Schedule.getMaxStageCount();
515 // No need to generate pipeline if there are no overlapped iterations.
516 if (numStages == 0) {
517 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "No overlapped iterations, no need to generate pipeline\n"
; } } while (false)
518 dbgs() << "No overlapped iterations, no need to generate pipeline\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "No overlapped iterations, no need to generate pipeline\n"
; } } while (false)
;
519 NumFailZeroStage++;
520 return;
521 }
522 // Check that the maximum stage count is less than user-defined limit.
523 if (SwpMaxStages > -1 && (int)numStages > SwpMaxStages) {
524 LLVM_DEBUG(dbgs() << "numStages:" << numStages << ">" << SwpMaxStagesdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "numStages:" << numStages
<< ">" << SwpMaxStages << " : too many stages, abort\n"
; } } while (false)
525 << " : too many stages, abort\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "numStages:" << numStages
<< ">" << SwpMaxStages << " : too many stages, abort\n"
; } } while (false)
;
526 NumFailLargeMaxStage++;
527 return;
528 }
529
530 // Generate the schedule as a ModuloSchedule.
531 DenseMap<MachineInstr *, int> Cycles, Stages;
532 std::vector<MachineInstr *> OrderedInsts;
533 for (int Cycle = Schedule.getFirstCycle(); Cycle <= Schedule.getFinalCycle();
534 ++Cycle) {
535 for (SUnit *SU : Schedule.getInstructions(Cycle)) {
536 OrderedInsts.push_back(SU->getInstr());
537 Cycles[SU->getInstr()] = Cycle;
538 Stages[SU->getInstr()] = Schedule.stageScheduled(SU);
539 }
540 }
541 DenseMap<MachineInstr *, std::pair<unsigned, int64_t>> NewInstrChanges;
542 for (auto &KV : NewMIs) {
543 Cycles[KV.first] = Cycles[KV.second];
544 Stages[KV.first] = Stages[KV.second];
545 NewInstrChanges[KV.first] = InstrChanges[getSUnit(KV.first)];
546 }
547
548 ModuloSchedule MS(MF, &Loop, std::move(OrderedInsts), std::move(Cycles),
549 std::move(Stages));
550 if (EmitTestAnnotations) {
551 assert(NewInstrChanges.empty() &&((NewInstrChanges.empty() && "Cannot serialize a schedule with InstrChanges!"
) ? static_cast<void> (0) : __assert_fail ("NewInstrChanges.empty() && \"Cannot serialize a schedule with InstrChanges!\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 552, __PRETTY_FUNCTION__))
552 "Cannot serialize a schedule with InstrChanges!")((NewInstrChanges.empty() && "Cannot serialize a schedule with InstrChanges!"
) ? static_cast<void> (0) : __assert_fail ("NewInstrChanges.empty() && \"Cannot serialize a schedule with InstrChanges!\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 552, __PRETTY_FUNCTION__))
;
553 ModuloScheduleTestAnnotater MSTI(MF, MS);
554 MSTI.annotate();
555 return;
556 }
557 // The experimental code generator can't work if there are InstChanges.
558 if (ExperimentalCodeGen && NewInstrChanges.empty()) {
559 PeelingModuloScheduleExpander MSE(MF, MS, &LIS);
560 MSE.expand();
561 } else {
562 ModuloScheduleExpander MSE(MF, MS, LIS, std::move(NewInstrChanges));
563 MSE.expand();
564 MSE.cleanup();
565 }
566 ++NumPipelined;
567}
568
569/// Clean up after the software pipeliner runs.
570void SwingSchedulerDAG::finishBlock() {
571 for (auto &KV : NewMIs)
572 MF.DeleteMachineInstr(KV.second);
573 NewMIs.clear();
574
575 // Call the superclass.
576 ScheduleDAGInstrs::finishBlock();
577}
578
579/// Return the register values for the operands of a Phi instruction.
580/// This function assume the instruction is a Phi.
581static void getPhiRegs(MachineInstr &Phi, MachineBasicBlock *Loop,
582 unsigned &InitVal, unsigned &LoopVal) {
583 assert(Phi.isPHI() && "Expecting a Phi.")((Phi.isPHI() && "Expecting a Phi.") ? static_cast<
void> (0) : __assert_fail ("Phi.isPHI() && \"Expecting a Phi.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 583, __PRETTY_FUNCTION__))
;
584
585 InitVal = 0;
586 LoopVal = 0;
587 for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
588 if (Phi.getOperand(i + 1).getMBB() != Loop)
589 InitVal = Phi.getOperand(i).getReg();
590 else
591 LoopVal = Phi.getOperand(i).getReg();
592
593 assert(InitVal != 0 && LoopVal != 0 && "Unexpected Phi structure.")((InitVal != 0 && LoopVal != 0 && "Unexpected Phi structure."
) ? static_cast<void> (0) : __assert_fail ("InitVal != 0 && LoopVal != 0 && \"Unexpected Phi structure.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 593, __PRETTY_FUNCTION__))
;
594}
595
596/// Return the Phi register value that comes the loop block.
597static unsigned getLoopPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB) {
598 for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
599 if (Phi.getOperand(i + 1).getMBB() == LoopBB)
600 return Phi.getOperand(i).getReg();
601 return 0;
602}
603
604/// Return true if SUb can be reached from SUa following the chain edges.
605static bool isSuccOrder(SUnit *SUa, SUnit *SUb) {
606 SmallPtrSet<SUnit *, 8> Visited;
607 SmallVector<SUnit *, 8> Worklist;
608 Worklist.push_back(SUa);
609 while (!Worklist.empty()) {
610 const SUnit *SU = Worklist.pop_back_val();
611 for (auto &SI : SU->Succs) {
612 SUnit *SuccSU = SI.getSUnit();
613 if (SI.getKind() == SDep::Order) {
614 if (Visited.count(SuccSU))
615 continue;
616 if (SuccSU == SUb)
617 return true;
618 Worklist.push_back(SuccSU);
619 Visited.insert(SuccSU);
620 }
621 }
622 }
623 return false;
624}
625
626/// Return true if the instruction causes a chain between memory
627/// references before and after it.
628static bool isDependenceBarrier(MachineInstr &MI, AliasAnalysis *AA) {
629 return MI.isCall() || MI.mayRaiseFPException() ||
630 MI.hasUnmodeledSideEffects() ||
631 (MI.hasOrderedMemoryRef() &&
632 (!MI.mayLoad() || !MI.isDereferenceableInvariantLoad(AA)));
633}
634
635/// Return the underlying objects for the memory references of an instruction.
636/// This function calls the code in ValueTracking, but first checks that the
637/// instruction has a memory operand.
638static void getUnderlyingObjects(const MachineInstr *MI,
639 SmallVectorImpl<const Value *> &Objs,
640 const DataLayout &DL) {
641 if (!MI->hasOneMemOperand())
642 return;
643 MachineMemOperand *MM = *MI->memoperands_begin();
644 if (!MM->getValue())
645 return;
646 GetUnderlyingObjects(MM->getValue(), Objs, DL);
647 for (const Value *V : Objs) {
648 if (!isIdentifiedObject(V)) {
649 Objs.clear();
650 return;
651 }
652 Objs.push_back(V);
653 }
654}
655
656/// Add a chain edge between a load and store if the store can be an
657/// alias of the load on a subsequent iteration, i.e., a loop carried
658/// dependence. This code is very similar to the code in ScheduleDAGInstrs
659/// but that code doesn't create loop carried dependences.
660void SwingSchedulerDAG::addLoopCarriedDependences(AliasAnalysis *AA) {
661 MapVector<const Value *, SmallVector<SUnit *, 4>> PendingLoads;
662 Value *UnknownValue =
663 UndefValue::get(Type::getVoidTy(MF.getFunction().getContext()));
664 for (auto &SU : SUnits) {
665 MachineInstr &MI = *SU.getInstr();
666 if (isDependenceBarrier(MI, AA))
667 PendingLoads.clear();
668 else if (MI.mayLoad()) {
669 SmallVector<const Value *, 4> Objs;
670 getUnderlyingObjects(&MI, Objs, MF.getDataLayout());
671 if (Objs.empty())
672 Objs.push_back(UnknownValue);
673 for (auto V : Objs) {
674 SmallVector<SUnit *, 4> &SUs = PendingLoads[V];
675 SUs.push_back(&SU);
676 }
677 } else if (MI.mayStore()) {
678 SmallVector<const Value *, 4> Objs;
679 getUnderlyingObjects(&MI, Objs, MF.getDataLayout());
680 if (Objs.empty())
681 Objs.push_back(UnknownValue);
682 for (auto V : Objs) {
683 MapVector<const Value *, SmallVector<SUnit *, 4>>::iterator I =
684 PendingLoads.find(V);
685 if (I == PendingLoads.end())
686 continue;
687 for (auto Load : I->second) {
688 if (isSuccOrder(Load, &SU))
689 continue;
690 MachineInstr &LdMI = *Load->getInstr();
691 // First, perform the cheaper check that compares the base register.
692 // If they are the same and the load offset is less than the store
693 // offset, then mark the dependence as loop carried potentially.
694 const MachineOperand *BaseOp1, *BaseOp2;
695 int64_t Offset1, Offset2;
696 bool Offset1IsScalable, Offset2IsScalable;
697 if (TII->getMemOperandWithOffset(LdMI, BaseOp1, Offset1,
698 Offset1IsScalable, TRI) &&
699 TII->getMemOperandWithOffset(MI, BaseOp2, Offset2,
700 Offset2IsScalable, TRI)) {
701 if (BaseOp1->isIdenticalTo(*BaseOp2) &&
702 Offset1IsScalable == Offset2IsScalable &&
703 (int)Offset1 < (int)Offset2) {
704 assert(TII->areMemAccessesTriviallyDisjoint(LdMI, MI) &&((TII->areMemAccessesTriviallyDisjoint(LdMI, MI) &&
"What happened to the chain edge?") ? static_cast<void>
(0) : __assert_fail ("TII->areMemAccessesTriviallyDisjoint(LdMI, MI) && \"What happened to the chain edge?\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 705, __PRETTY_FUNCTION__))
705 "What happened to the chain edge?")((TII->areMemAccessesTriviallyDisjoint(LdMI, MI) &&
"What happened to the chain edge?") ? static_cast<void>
(0) : __assert_fail ("TII->areMemAccessesTriviallyDisjoint(LdMI, MI) && \"What happened to the chain edge?\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 705, __PRETTY_FUNCTION__))
;
706 SDep Dep(Load, SDep::Barrier);
707 Dep.setLatency(1);
708 SU.addPred(Dep);
709 continue;
710 }
711 }
712 // Second, the more expensive check that uses alias analysis on the
713 // base registers. If they alias, and the load offset is less than
714 // the store offset, the mark the dependence as loop carried.
715 if (!AA) {
716 SDep Dep(Load, SDep::Barrier);
717 Dep.setLatency(1);
718 SU.addPred(Dep);
719 continue;
720 }
721 MachineMemOperand *MMO1 = *LdMI.memoperands_begin();
722 MachineMemOperand *MMO2 = *MI.memoperands_begin();
723 if (!MMO1->getValue() || !MMO2->getValue()) {
724 SDep Dep(Load, SDep::Barrier);
725 Dep.setLatency(1);
726 SU.addPred(Dep);
727 continue;
728 }
729 if (MMO1->getValue() == MMO2->getValue() &&
730 MMO1->getOffset() <= MMO2->getOffset()) {
731 SDep Dep(Load, SDep::Barrier);
732 Dep.setLatency(1);
733 SU.addPred(Dep);
734 continue;
735 }
736 AliasResult AAResult = AA->alias(
737 MemoryLocation(MMO1->getValue(), LocationSize::unknown(),
738 MMO1->getAAInfo()),
739 MemoryLocation(MMO2->getValue(), LocationSize::unknown(),
740 MMO2->getAAInfo()));
741
742 if (AAResult != NoAlias) {
743 SDep Dep(Load, SDep::Barrier);
744 Dep.setLatency(1);
745 SU.addPred(Dep);
746 }
747 }
748 }
749 }
750 }
751}
752
753/// Update the phi dependences to the DAG because ScheduleDAGInstrs no longer
754/// processes dependences for PHIs. This function adds true dependences
755/// from a PHI to a use, and a loop carried dependence from the use to the
756/// PHI. The loop carried dependence is represented as an anti dependence
757/// edge. This function also removes chain dependences between unrelated
758/// PHIs.
759void SwingSchedulerDAG::updatePhiDependences() {
760 SmallVector<SDep, 4> RemoveDeps;
761 const TargetSubtargetInfo &ST = MF.getSubtarget<TargetSubtargetInfo>();
762
763 // Iterate over each DAG node.
764 for (SUnit &I : SUnits) {
765 RemoveDeps.clear();
766 // Set to true if the instruction has an operand defined by a Phi.
767 unsigned HasPhiUse = 0;
768 unsigned HasPhiDef = 0;
769 MachineInstr *MI = I.getInstr();
770 // Iterate over each operand, and we process the definitions.
771 for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
772 MOE = MI->operands_end();
773 MOI != MOE; ++MOI) {
774 if (!MOI->isReg())
775 continue;
776 Register Reg = MOI->getReg();
777 if (MOI->isDef()) {
778 // If the register is used by a Phi, then create an anti dependence.
779 for (MachineRegisterInfo::use_instr_iterator
780 UI = MRI.use_instr_begin(Reg),
781 UE = MRI.use_instr_end();
782 UI != UE; ++UI) {
783 MachineInstr *UseMI = &*UI;
784 SUnit *SU = getSUnit(UseMI);
785 if (SU != nullptr && UseMI->isPHI()) {
786 if (!MI->isPHI()) {
787 SDep Dep(SU, SDep::Anti, Reg);
788 Dep.setLatency(1);
789 I.addPred(Dep);
790 } else {
791 HasPhiDef = Reg;
792 // Add a chain edge to a dependent Phi that isn't an existing
793 // predecessor.
794 if (SU->NodeNum < I.NodeNum && !I.isPred(SU))
795 I.addPred(SDep(SU, SDep::Barrier));
796 }
797 }
798 }
799 } else if (MOI->isUse()) {
800 // If the register is defined by a Phi, then create a true dependence.
801 MachineInstr *DefMI = MRI.getUniqueVRegDef(Reg);
802 if (DefMI == nullptr)
803 continue;
804 SUnit *SU = getSUnit(DefMI);
805 if (SU != nullptr && DefMI->isPHI()) {
806 if (!MI->isPHI()) {
807 SDep Dep(SU, SDep::Data, Reg);
808 Dep.setLatency(0);
809 ST.adjustSchedDependency(SU, &I, Dep);
810 I.addPred(Dep);
811 } else {
812 HasPhiUse = Reg;
813 // Add a chain edge to a dependent Phi that isn't an existing
814 // predecessor.
815 if (SU->NodeNum < I.NodeNum && !I.isPred(SU))
816 I.addPred(SDep(SU, SDep::Barrier));
817 }
818 }
819 }
820 }
821 // Remove order dependences from an unrelated Phi.
822 if (!SwpPruneDeps)
823 continue;
824 for (auto &PI : I.Preds) {
825 MachineInstr *PMI = PI.getSUnit()->getInstr();
826 if (PMI->isPHI() && PI.getKind() == SDep::Order) {
827 if (I.getInstr()->isPHI()) {
828 if (PMI->getOperand(0).getReg() == HasPhiUse)
829 continue;
830 if (getLoopPhiReg(*PMI, PMI->getParent()) == HasPhiDef)
831 continue;
832 }
833 RemoveDeps.push_back(PI);
834 }
835 }
836 for (int i = 0, e = RemoveDeps.size(); i != e; ++i)
837 I.removePred(RemoveDeps[i]);
838 }
839}
840
841/// Iterate over each DAG node and see if we can change any dependences
842/// in order to reduce the recurrence MII.
843void SwingSchedulerDAG::changeDependences() {
844 // See if an instruction can use a value from the previous iteration.
845 // If so, we update the base and offset of the instruction and change
846 // the dependences.
847 for (SUnit &I : SUnits) {
848 unsigned BasePos = 0, OffsetPos = 0, NewBase = 0;
849 int64_t NewOffset = 0;
850 if (!canUseLastOffsetValue(I.getInstr(), BasePos, OffsetPos, NewBase,
851 NewOffset))
852 continue;
853
854 // Get the MI and SUnit for the instruction that defines the original base.
855 Register OrigBase = I.getInstr()->getOperand(BasePos).getReg();
856 MachineInstr *DefMI = MRI.getUniqueVRegDef(OrigBase);
857 if (!DefMI)
858 continue;
859 SUnit *DefSU = getSUnit(DefMI);
860 if (!DefSU)
861 continue;
862 // Get the MI and SUnit for the instruction that defins the new base.
863 MachineInstr *LastMI = MRI.getUniqueVRegDef(NewBase);
864 if (!LastMI)
865 continue;
866 SUnit *LastSU = getSUnit(LastMI);
867 if (!LastSU)
868 continue;
869
870 if (Topo.IsReachable(&I, LastSU))
871 continue;
872
873 // Remove the dependence. The value now depends on a prior iteration.
874 SmallVector<SDep, 4> Deps;
875 for (SUnit::pred_iterator P = I.Preds.begin(), E = I.Preds.end(); P != E;
876 ++P)
877 if (P->getSUnit() == DefSU)
878 Deps.push_back(*P);
879 for (int i = 0, e = Deps.size(); i != e; i++) {
880 Topo.RemovePred(&I, Deps[i].getSUnit());
881 I.removePred(Deps[i]);
882 }
883 // Remove the chain dependence between the instructions.
884 Deps.clear();
885 for (auto &P : LastSU->Preds)
886 if (P.getSUnit() == &I && P.getKind() == SDep::Order)
887 Deps.push_back(P);
888 for (int i = 0, e = Deps.size(); i != e; i++) {
889 Topo.RemovePred(LastSU, Deps[i].getSUnit());
890 LastSU->removePred(Deps[i]);
891 }
892
893 // Add a dependence between the new instruction and the instruction
894 // that defines the new base.
895 SDep Dep(&I, SDep::Anti, NewBase);
896 Topo.AddPred(LastSU, &I);
897 LastSU->addPred(Dep);
898
899 // Remember the base and offset information so that we can update the
900 // instruction during code generation.
901 InstrChanges[&I] = std::make_pair(NewBase, NewOffset);
902 }
903}
904
905namespace {
906
907// FuncUnitSorter - Comparison operator used to sort instructions by
908// the number of functional unit choices.
909struct FuncUnitSorter {
910 const InstrItineraryData *InstrItins;
911 const MCSubtargetInfo *STI;
912 DenseMap<InstrStage::FuncUnits, unsigned> Resources;
913
914 FuncUnitSorter(const TargetSubtargetInfo &TSI)
915 : InstrItins(TSI.getInstrItineraryData()), STI(&TSI) {}
916
917 // Compute the number of functional unit alternatives needed
918 // at each stage, and take the minimum value. We prioritize the
919 // instructions by the least number of choices first.
920 unsigned minFuncUnits(const MachineInstr *Inst,
921 InstrStage::FuncUnits &F) const {
922 unsigned SchedClass = Inst->getDesc().getSchedClass();
923 unsigned min = UINT_MAX(2147483647 *2U +1U);
924 if (InstrItins && !InstrItins->isEmpty()) {
925 for (const InstrStage &IS :
926 make_range(InstrItins->beginStage(SchedClass),
927 InstrItins->endStage(SchedClass))) {
928 InstrStage::FuncUnits funcUnits = IS.getUnits();
929 unsigned numAlternatives = countPopulation(funcUnits);
930 if (numAlternatives < min) {
931 min = numAlternatives;
932 F = funcUnits;
933 }
934 }
935 return min;
936 }
937 if (STI && STI->getSchedModel().hasInstrSchedModel()) {
938 const MCSchedClassDesc *SCDesc =
939 STI->getSchedModel().getSchedClassDesc(SchedClass);
940 if (!SCDesc->isValid())
941 // No valid Schedule Class Desc for schedClass, should be
942 // Pseudo/PostRAPseudo
943 return min;
944
945 for (const MCWriteProcResEntry &PRE :
946 make_range(STI->getWriteProcResBegin(SCDesc),
947 STI->getWriteProcResEnd(SCDesc))) {
948 if (!PRE.Cycles)
949 continue;
950 const MCProcResourceDesc *ProcResource =
951 STI->getSchedModel().getProcResource(PRE.ProcResourceIdx);
952 unsigned NumUnits = ProcResource->NumUnits;
953 if (NumUnits < min) {
954 min = NumUnits;
955 F = PRE.ProcResourceIdx;
956 }
957 }
958 return min;
959 }
960 llvm_unreachable("Should have non-empty InstrItins or hasInstrSchedModel!")::llvm::llvm_unreachable_internal("Should have non-empty InstrItins or hasInstrSchedModel!"
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 960)
;
961 }
962
963 // Compute the critical resources needed by the instruction. This
964 // function records the functional units needed by instructions that
965 // must use only one functional unit. We use this as a tie breaker
966 // for computing the resource MII. The instrutions that require
967 // the same, highly used, functional unit have high priority.
968 void calcCriticalResources(MachineInstr &MI) {
969 unsigned SchedClass = MI.getDesc().getSchedClass();
970 if (InstrItins && !InstrItins->isEmpty()) {
971 for (const InstrStage &IS :
972 make_range(InstrItins->beginStage(SchedClass),
973 InstrItins->endStage(SchedClass))) {
974 InstrStage::FuncUnits FuncUnits = IS.getUnits();
975 if (countPopulation(FuncUnits) == 1)
976 Resources[FuncUnits]++;
977 }
978 return;
979 }
980 if (STI && STI->getSchedModel().hasInstrSchedModel()) {
981 const MCSchedClassDesc *SCDesc =
982 STI->getSchedModel().getSchedClassDesc(SchedClass);
983 if (!SCDesc->isValid())
984 // No valid Schedule Class Desc for schedClass, should be
985 // Pseudo/PostRAPseudo
986 return;
987
988 for (const MCWriteProcResEntry &PRE :
989 make_range(STI->getWriteProcResBegin(SCDesc),
990 STI->getWriteProcResEnd(SCDesc))) {
991 if (!PRE.Cycles)
992 continue;
993 Resources[PRE.ProcResourceIdx]++;
994 }
995 return;
996 }
997 llvm_unreachable("Should have non-empty InstrItins or hasInstrSchedModel!")::llvm::llvm_unreachable_internal("Should have non-empty InstrItins or hasInstrSchedModel!"
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 997)
;
998 }
999
1000 /// Return true if IS1 has less priority than IS2.
1001 bool operator()(const MachineInstr *IS1, const MachineInstr *IS2) const {
1002 InstrStage::FuncUnits F1 = 0, F2 = 0;
1003 unsigned MFUs1 = minFuncUnits(IS1, F1);
1004 unsigned MFUs2 = minFuncUnits(IS2, F2);
1005 if (MFUs1 == MFUs2)
1006 return Resources.lookup(F1) < Resources.lookup(F2);
1007 return MFUs1 > MFUs2;
1008 }
1009};
1010
1011} // end anonymous namespace
1012
1013/// Calculate the resource constrained minimum initiation interval for the
1014/// specified loop. We use the DFA to model the resources needed for
1015/// each instruction, and we ignore dependences. A different DFA is created
1016/// for each cycle that is required. When adding a new instruction, we attempt
1017/// to add it to each existing DFA, until a legal space is found. If the
1018/// instruction cannot be reserved in an existing DFA, we create a new one.
1019unsigned SwingSchedulerDAG::calculateResMII() {
1020
1021 LLVM_DEBUG(dbgs() << "calculateResMII:\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "calculateResMII:\n"; } } while
(false)
;
1022 SmallVector<ResourceManager*, 8> Resources;
1023 MachineBasicBlock *MBB = Loop.getHeader();
1024 Resources.push_back(new ResourceManager(&MF.getSubtarget()));
1025
1026 // Sort the instructions by the number of available choices for scheduling,
1027 // least to most. Use the number of critical resources as the tie breaker.
1028 FuncUnitSorter FUS = FuncUnitSorter(MF.getSubtarget());
1029 for (MachineBasicBlock::iterator I = MBB->getFirstNonPHI(),
1030 E = MBB->getFirstTerminator();
1031 I != E; ++I)
1032 FUS.calcCriticalResources(*I);
1033 PriorityQueue<MachineInstr *, std::vector<MachineInstr *>, FuncUnitSorter>
1034 FuncUnitOrder(FUS);
1035
1036 for (MachineBasicBlock::iterator I = MBB->getFirstNonPHI(),
1037 E = MBB->getFirstTerminator();
1038 I != E; ++I)
1039 FuncUnitOrder.push(&*I);
1040
1041 while (!FuncUnitOrder.empty()) {
1042 MachineInstr *MI = FuncUnitOrder.top();
1043 FuncUnitOrder.pop();
1044 if (TII->isZeroCost(MI->getOpcode()))
1045 continue;
1046 // Attempt to reserve the instruction in an existing DFA. At least one
1047 // DFA is needed for each cycle.
1048 unsigned NumCycles = getSUnit(MI)->Latency;
1049 unsigned ReservedCycles = 0;
1050 SmallVectorImpl<ResourceManager *>::iterator RI = Resources.begin();
1051 SmallVectorImpl<ResourceManager *>::iterator RE = Resources.end();
1052 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "Trying to reserve resource for "
<< NumCycles << " cycles for \n"; MI->dump();
}; } } while (false)
1053 dbgs() << "Trying to reserve resource for " << NumCyclesdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "Trying to reserve resource for "
<< NumCycles << " cycles for \n"; MI->dump();
}; } } while (false)
1054 << " cycles for \n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "Trying to reserve resource for "
<< NumCycles << " cycles for \n"; MI->dump();
}; } } while (false)
1055 MI->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "Trying to reserve resource for "
<< NumCycles << " cycles for \n"; MI->dump();
}; } } while (false)
1056 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "Trying to reserve resource for "
<< NumCycles << " cycles for \n"; MI->dump();
}; } } while (false)
;
1057 for (unsigned C = 0; C < NumCycles; ++C)
1058 while (RI != RE) {
1059 if ((*RI)->canReserveResources(*MI)) {
1060 (*RI)->reserveResources(*MI);
1061 ++ReservedCycles;
1062 break;
1063 }
1064 RI++;
1065 }
1066 LLVM_DEBUG(dbgs() << "ReservedCycles:" << ReservedCyclesdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "ReservedCycles:" << ReservedCycles
<< ", NumCycles:" << NumCycles << "\n"; } }
while (false)
1067 << ", NumCycles:" << NumCycles << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "ReservedCycles:" << ReservedCycles
<< ", NumCycles:" << NumCycles << "\n"; } }
while (false)
;
1068 // Add new DFAs, if needed, to reserve resources.
1069 for (unsigned C = ReservedCycles; C < NumCycles; ++C) {
1070 LLVM_DEBUG(if (SwpDebugResource) dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { if (SwpDebugResource) dbgs() << "NewResource created to reserve resources"
<< "\n"; } } while (false)
1071 << "NewResource created to reserve resources"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { if (SwpDebugResource) dbgs() << "NewResource created to reserve resources"
<< "\n"; } } while (false)
1072 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { if (SwpDebugResource) dbgs() << "NewResource created to reserve resources"
<< "\n"; } } while (false)
;
1073 ResourceManager *NewResource = new ResourceManager(&MF.getSubtarget());
1074 assert(NewResource->canReserveResources(*MI) && "Reserve error.")((NewResource->canReserveResources(*MI) && "Reserve error."
) ? static_cast<void> (0) : __assert_fail ("NewResource->canReserveResources(*MI) && \"Reserve error.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 1074, __PRETTY_FUNCTION__))
;
1075 NewResource->reserveResources(*MI);
1076 Resources.push_back(NewResource);
1077 }
1078 }
1079 int Resmii = Resources.size();
1080 LLVM_DEBUG(dbgs() << "Retrun Res MII:" << Resmii << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "Retrun Res MII:" << Resmii
<< "\n"; } } while (false)
;
1081 // Delete the memory for each of the DFAs that were created earlier.
1082 for (ResourceManager *RI : Resources) {
1083 ResourceManager *D = RI;
1084 delete D;
1085 }
1086 Resources.clear();
1087 return Resmii;
1088}
1089
1090/// Calculate the recurrence-constrainted minimum initiation interval.
1091/// Iterate over each circuit. Compute the delay(c) and distance(c)
1092/// for each circuit. The II needs to satisfy the inequality
1093/// delay(c) - II*distance(c) <= 0. For each circuit, choose the smallest
1094/// II that satisfies the inequality, and the RecMII is the maximum
1095/// of those values.
1096unsigned SwingSchedulerDAG::calculateRecMII(NodeSetType &NodeSets) {
1097 unsigned RecMII = 0;
1098
1099 for (NodeSet &Nodes : NodeSets) {
1100 if (Nodes.empty())
1101 continue;
1102
1103 unsigned Delay = Nodes.getLatency();
1104 unsigned Distance = 1;
1105
1106 // ii = ceil(delay / distance)
1107 unsigned CurMII = (Delay + Distance - 1) / Distance;
1108 Nodes.setRecMII(CurMII);
1109 if (CurMII > RecMII)
1110 RecMII = CurMII;
1111 }
1112
1113 return RecMII;
1114}
1115
1116/// Swap all the anti dependences in the DAG. That means it is no longer a DAG,
1117/// but we do this to find the circuits, and then change them back.
1118static void swapAntiDependences(std::vector<SUnit> &SUnits) {
1119 SmallVector<std::pair<SUnit *, SDep>, 8> DepsAdded;
1120 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
1121 SUnit *SU = &SUnits[i];
1122 for (SUnit::pred_iterator IP = SU->Preds.begin(), EP = SU->Preds.end();
1123 IP != EP; ++IP) {
1124 if (IP->getKind() != SDep::Anti)
1125 continue;
1126 DepsAdded.push_back(std::make_pair(SU, *IP));
1127 }
1128 }
1129 for (SmallVector<std::pair<SUnit *, SDep>, 8>::iterator I = DepsAdded.begin(),
1130 E = DepsAdded.end();
1131 I != E; ++I) {
1132 // Remove this anti dependency and add one in the reverse direction.
1133 SUnit *SU = I->first;
1134 SDep &D = I->second;
1135 SUnit *TargetSU = D.getSUnit();
1136 unsigned Reg = D.getReg();
1137 unsigned Lat = D.getLatency();
1138 SU->removePred(D);
1139 SDep Dep(SU, SDep::Anti, Reg);
1140 Dep.setLatency(Lat);
1141 TargetSU->addPred(Dep);
1142 }
1143}
1144
1145/// Create the adjacency structure of the nodes in the graph.
1146void SwingSchedulerDAG::Circuits::createAdjacencyStructure(
1147 SwingSchedulerDAG *DAG) {
1148 BitVector Added(SUnits.size());
1149 DenseMap<int, int> OutputDeps;
1150 for (int i = 0, e = SUnits.size(); i != e; ++i) {
1151 Added.reset();
1152 // Add any successor to the adjacency matrix and exclude duplicates.
1153 for (auto &SI : SUnits[i].Succs) {
1154 // Only create a back-edge on the first and last nodes of a dependence
1155 // chain. This records any chains and adds them later.
1156 if (SI.getKind() == SDep::Output) {
1157 int N = SI.getSUnit()->NodeNum;
1158 int BackEdge = i;
1159 auto Dep = OutputDeps.find(BackEdge);
1160 if (Dep != OutputDeps.end()) {
1161 BackEdge = Dep->second;
1162 OutputDeps.erase(Dep);
1163 }
1164 OutputDeps[N] = BackEdge;
1165 }
1166 // Do not process a boundary node, an artificial node.
1167 // A back-edge is processed only if it goes to a Phi.
1168 if (SI.getSUnit()->isBoundaryNode() || SI.isArtificial() ||
1169 (SI.getKind() == SDep::Anti && !SI.getSUnit()->getInstr()->isPHI()))
1170 continue;
1171 int N = SI.getSUnit()->NodeNum;
1172 if (!Added.test(N)) {
1173 AdjK[i].push_back(N);
1174 Added.set(N);
1175 }
1176 }
1177 // A chain edge between a store and a load is treated as a back-edge in the
1178 // adjacency matrix.
1179 for (auto &PI : SUnits[i].Preds) {
1180 if (!SUnits[i].getInstr()->mayStore() ||
1181 !DAG->isLoopCarriedDep(&SUnits[i], PI, false))
1182 continue;
1183 if (PI.getKind() == SDep::Order && PI.getSUnit()->getInstr()->mayLoad()) {
1184 int N = PI.getSUnit()->NodeNum;
1185 if (!Added.test(N)) {
1186 AdjK[i].push_back(N);
1187 Added.set(N);
1188 }
1189 }
1190 }
1191 }
1192 // Add back-edges in the adjacency matrix for the output dependences.
1193 for (auto &OD : OutputDeps)
1194 if (!Added.test(OD.second)) {
1195 AdjK[OD.first].push_back(OD.second);
1196 Added.set(OD.second);
1197 }
1198}
1199
1200/// Identify an elementary circuit in the dependence graph starting at the
1201/// specified node.
1202bool SwingSchedulerDAG::Circuits::circuit(int V, int S, NodeSetType &NodeSets,
1203 bool HasBackedge) {
1204 SUnit *SV = &SUnits[V];
1205 bool F = false;
1206 Stack.insert(SV);
1207 Blocked.set(V);
1208
1209 for (auto W : AdjK[V]) {
1210 if (NumPaths > MaxPaths)
1211 break;
1212 if (W < S)
1213 continue;
1214 if (W == S) {
1215 if (!HasBackedge)
1216 NodeSets.push_back(NodeSet(Stack.begin(), Stack.end()));
1217 F = true;
1218 ++NumPaths;
1219 break;
1220 } else if (!Blocked.test(W)) {
1221 if (circuit(W, S, NodeSets,
1222 Node2Idx->at(W) < Node2Idx->at(V) ? true : HasBackedge))
1223 F = true;
1224 }
1225 }
1226
1227 if (F)
1228 unblock(V);
1229 else {
1230 for (auto W : AdjK[V]) {
1231 if (W < S)
1232 continue;
1233 if (B[W].count(SV) == 0)
1234 B[W].insert(SV);
1235 }
1236 }
1237 Stack.pop_back();
1238 return F;
1239}
1240
1241/// Unblock a node in the circuit finding algorithm.
1242void SwingSchedulerDAG::Circuits::unblock(int U) {
1243 Blocked.reset(U);
1244 SmallPtrSet<SUnit *, 4> &BU = B[U];
1245 while (!BU.empty()) {
1246 SmallPtrSet<SUnit *, 4>::iterator SI = BU.begin();
1247 assert(SI != BU.end() && "Invalid B set.")((SI != BU.end() && "Invalid B set.") ? static_cast<
void> (0) : __assert_fail ("SI != BU.end() && \"Invalid B set.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 1247, __PRETTY_FUNCTION__))
;
1248 SUnit *W = *SI;
1249 BU.erase(W);
1250 if (Blocked.test(W->NodeNum))
1251 unblock(W->NodeNum);
1252 }
1253}
1254
1255/// Identify all the elementary circuits in the dependence graph using
1256/// Johnson's circuit algorithm.
1257void SwingSchedulerDAG::findCircuits(NodeSetType &NodeSets) {
1258 // Swap all the anti dependences in the DAG. That means it is no longer a DAG,
1259 // but we do this to find the circuits, and then change them back.
1260 swapAntiDependences(SUnits);
1261
1262 Circuits Cir(SUnits, Topo);
1263 // Create the adjacency structure.
1264 Cir.createAdjacencyStructure(this);
1265 for (int i = 0, e = SUnits.size(); i != e; ++i) {
1266 Cir.reset();
1267 Cir.circuit(i, i, NodeSets);
1268 }
1269
1270 // Change the dependences back so that we've created a DAG again.
1271 swapAntiDependences(SUnits);
1272}
1273
1274// Create artificial dependencies between the source of COPY/REG_SEQUENCE that
1275// is loop-carried to the USE in next iteration. This will help pipeliner avoid
1276// additional copies that are needed across iterations. An artificial dependence
1277// edge is added from USE to SOURCE of COPY/REG_SEQUENCE.
1278
1279// PHI-------Anti-Dep-----> COPY/REG_SEQUENCE (loop-carried)
1280// SRCOfCopY------True-Dep---> COPY/REG_SEQUENCE
1281// PHI-------True-Dep------> USEOfPhi
1282
1283// The mutation creates
1284// USEOfPHI -------Artificial-Dep---> SRCOfCopy
1285
1286// This overall will ensure, the USEOfPHI is scheduled before SRCOfCopy
1287// (since USE is a predecessor), implies, the COPY/ REG_SEQUENCE is scheduled
1288// late to avoid additional copies across iterations. The possible scheduling
1289// order would be
1290// USEOfPHI --- SRCOfCopy--- COPY/REG_SEQUENCE.
1291
1292void SwingSchedulerDAG::CopyToPhiMutation::apply(ScheduleDAGInstrs *DAG) {
1293 for (SUnit &SU : DAG->SUnits) {
1294 // Find the COPY/REG_SEQUENCE instruction.
1295 if (!SU.getInstr()->isCopy() && !SU.getInstr()->isRegSequence())
1296 continue;
1297
1298 // Record the loop carried PHIs.
1299 SmallVector<SUnit *, 4> PHISUs;
1300 // Record the SrcSUs that feed the COPY/REG_SEQUENCE instructions.
1301 SmallVector<SUnit *, 4> SrcSUs;
1302
1303 for (auto &Dep : SU.Preds) {
1304 SUnit *TmpSU = Dep.getSUnit();
1305 MachineInstr *TmpMI = TmpSU->getInstr();
1306 SDep::Kind DepKind = Dep.getKind();
1307 // Save the loop carried PHI.
1308 if (DepKind == SDep::Anti && TmpMI->isPHI())
1309 PHISUs.push_back(TmpSU);
1310 // Save the source of COPY/REG_SEQUENCE.
1311 // If the source has no pre-decessors, we will end up creating cycles.
1312 else if (DepKind == SDep::Data && !TmpMI->isPHI() && TmpSU->NumPreds > 0)
1313 SrcSUs.push_back(TmpSU);
1314 }
1315
1316 if (PHISUs.size() == 0 || SrcSUs.size() == 0)
1317 continue;
1318
1319 // Find the USEs of PHI. If the use is a PHI or REG_SEQUENCE, push back this
1320 // SUnit to the container.
1321 SmallVector<SUnit *, 8> UseSUs;
1322 // Do not use iterator based loop here as we are updating the container.
1323 for (size_t Index = 0; Index < PHISUs.size(); ++Index) {
1324 for (auto &Dep : PHISUs[Index]->Succs) {
1325 if (Dep.getKind() != SDep::Data)
1326 continue;
1327
1328 SUnit *TmpSU = Dep.getSUnit();
1329 MachineInstr *TmpMI = TmpSU->getInstr();
1330 if (TmpMI->isPHI() || TmpMI->isRegSequence()) {
1331 PHISUs.push_back(TmpSU);
1332 continue;
1333 }
1334 UseSUs.push_back(TmpSU);
1335 }
1336 }
1337
1338 if (UseSUs.size() == 0)
1339 continue;
1340
1341 SwingSchedulerDAG *SDAG = cast<SwingSchedulerDAG>(DAG);
1342 // Add the artificial dependencies if it does not form a cycle.
1343 for (auto I : UseSUs) {
1344 for (auto Src : SrcSUs) {
1345 if (!SDAG->Topo.IsReachable(I, Src) && Src != I) {
1346 Src->addPred(SDep(I, SDep::Artificial));
1347 SDAG->Topo.AddPred(Src, I);
1348 }
1349 }
1350 }
1351 }
1352}
1353
1354/// Return true for DAG nodes that we ignore when computing the cost functions.
1355/// We ignore the back-edge recurrence in order to avoid unbounded recursion
1356/// in the calculation of the ASAP, ALAP, etc functions.
1357static bool ignoreDependence(const SDep &D, bool isPred) {
1358 if (D.isArtificial())
1359 return true;
1360 return D.getKind() == SDep::Anti && isPred;
1361}
1362
1363/// Compute several functions need to order the nodes for scheduling.
1364/// ASAP - Earliest time to schedule a node.
1365/// ALAP - Latest time to schedule a node.
1366/// MOV - Mobility function, difference between ALAP and ASAP.
1367/// D - Depth of each node.
1368/// H - Height of each node.
1369void SwingSchedulerDAG::computeNodeFunctions(NodeSetType &NodeSets) {
1370 ScheduleInfo.resize(SUnits.size());
1371
1372 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (ScheduleDAGTopologicalSort::const_iterator
I = Topo.begin(), E = Topo.end(); I != E; ++I) { const SUnit
&SU = SUnits[*I]; dumpNode(SU); } }; } } while (false)
1373 for (ScheduleDAGTopologicalSort::const_iterator I = Topo.begin(),do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (ScheduleDAGTopologicalSort::const_iterator
I = Topo.begin(), E = Topo.end(); I != E; ++I) { const SUnit
&SU = SUnits[*I]; dumpNode(SU); } }; } } while (false)
1374 E = Topo.end();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (ScheduleDAGTopologicalSort::const_iterator
I = Topo.begin(), E = Topo.end(); I != E; ++I) { const SUnit
&SU = SUnits[*I]; dumpNode(SU); } }; } } while (false)
1375 I != E; ++I) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (ScheduleDAGTopologicalSort::const_iterator
I = Topo.begin(), E = Topo.end(); I != E; ++I) { const SUnit
&SU = SUnits[*I]; dumpNode(SU); } }; } } while (false)
1376 const SUnit &SU = SUnits[*I];do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (ScheduleDAGTopologicalSort::const_iterator
I = Topo.begin(), E = Topo.end(); I != E; ++I) { const SUnit
&SU = SUnits[*I]; dumpNode(SU); } }; } } while (false)
1377 dumpNode(SU);do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (ScheduleDAGTopologicalSort::const_iterator
I = Topo.begin(), E = Topo.end(); I != E; ++I) { const SUnit
&SU = SUnits[*I]; dumpNode(SU); } }; } } while (false)
1378 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (ScheduleDAGTopologicalSort::const_iterator
I = Topo.begin(), E = Topo.end(); I != E; ++I) { const SUnit
&SU = SUnits[*I]; dumpNode(SU); } }; } } while (false)
1379 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (ScheduleDAGTopologicalSort::const_iterator
I = Topo.begin(), E = Topo.end(); I != E; ++I) { const SUnit
&SU = SUnits[*I]; dumpNode(SU); } }; } } while (false)
;
1380
1381 int maxASAP = 0;
1382 // Compute ASAP and ZeroLatencyDepth.
1383 for (ScheduleDAGTopologicalSort::const_iterator I = Topo.begin(),
1384 E = Topo.end();
1385 I != E; ++I) {
1386 int asap = 0;
1387 int zeroLatencyDepth = 0;
1388 SUnit *SU = &SUnits[*I];
1389 for (SUnit::const_pred_iterator IP = SU->Preds.begin(),
1390 EP = SU->Preds.end();
1391 IP != EP; ++IP) {
1392 SUnit *pred = IP->getSUnit();
1393 if (IP->getLatency() == 0)
1394 zeroLatencyDepth =
1395 std::max(zeroLatencyDepth, getZeroLatencyDepth(pred) + 1);
1396 if (ignoreDependence(*IP, true))
1397 continue;
1398 asap = std::max(asap, (int)(getASAP(pred) + IP->getLatency() -
1399 getDistance(pred, SU, *IP) * MII));
1400 }
1401 maxASAP = std::max(maxASAP, asap);
1402 ScheduleInfo[*I].ASAP = asap;
1403 ScheduleInfo[*I].ZeroLatencyDepth = zeroLatencyDepth;
1404 }
1405
1406 // Compute ALAP, ZeroLatencyHeight, and MOV.
1407 for (ScheduleDAGTopologicalSort::const_reverse_iterator I = Topo.rbegin(),
1408 E = Topo.rend();
1409 I != E; ++I) {
1410 int alap = maxASAP;
1411 int zeroLatencyHeight = 0;
1412 SUnit *SU = &SUnits[*I];
1413 for (SUnit::const_succ_iterator IS = SU->Succs.begin(),
1414 ES = SU->Succs.end();
1415 IS != ES; ++IS) {
1416 SUnit *succ = IS->getSUnit();
1417 if (IS->getLatency() == 0)
1418 zeroLatencyHeight =
1419 std::max(zeroLatencyHeight, getZeroLatencyHeight(succ) + 1);
1420 if (ignoreDependence(*IS, true))
1421 continue;
1422 alap = std::min(alap, (int)(getALAP(succ) - IS->getLatency() +
1423 getDistance(SU, succ, *IS) * MII));
1424 }
1425
1426 ScheduleInfo[*I].ALAP = alap;
1427 ScheduleInfo[*I].ZeroLatencyHeight = zeroLatencyHeight;
1428 }
1429
1430 // After computing the node functions, compute the summary for each node set.
1431 for (NodeSet &I : NodeSets)
1432 I.computeNodeSetInfo(this);
1433
1434 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (unsigned i = 0; i < SUnits.size();
i++) { dbgs() << "\tNode " << i << ":\n"; dbgs
() << "\t ASAP = " << getASAP(&SUnits[i]) <<
"\n"; dbgs() << "\t ALAP = " << getALAP(&SUnits
[i]) << "\n"; dbgs() << "\t MOV = " << getMOV
(&SUnits[i]) << "\n"; dbgs() << "\t D = "
<< getDepth(&SUnits[i]) << "\n"; dbgs() <<
"\t H = " << getHeight(&SUnits[i]) << "\n"
; dbgs() << "\t ZLD = " << getZeroLatencyDepth
(&SUnits[i]) << "\n"; dbgs() << "\t ZLH = "
<< getZeroLatencyHeight(&SUnits[i]) << "\n";
} }; } } while (false)
1435 for (unsigned i = 0; i < SUnits.size(); i++) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (unsigned i = 0; i < SUnits.size();
i++) { dbgs() << "\tNode " << i << ":\n"; dbgs
() << "\t ASAP = " << getASAP(&SUnits[i]) <<
"\n"; dbgs() << "\t ALAP = " << getALAP(&SUnits
[i]) << "\n"; dbgs() << "\t MOV = " << getMOV
(&SUnits[i]) << "\n"; dbgs() << "\t D = "
<< getDepth(&SUnits[i]) << "\n"; dbgs() <<
"\t H = " << getHeight(&SUnits[i]) << "\n"
; dbgs() << "\t ZLD = " << getZeroLatencyDepth
(&SUnits[i]) << "\n"; dbgs() << "\t ZLH = "
<< getZeroLatencyHeight(&SUnits[i]) << "\n";
} }; } } while (false)
1436 dbgs() << "\tNode " << i << ":\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (unsigned i = 0; i < SUnits.size();
i++) { dbgs() << "\tNode " << i << ":\n"; dbgs
() << "\t ASAP = " << getASAP(&SUnits[i]) <<
"\n"; dbgs() << "\t ALAP = " << getALAP(&SUnits
[i]) << "\n"; dbgs() << "\t MOV = " << getMOV
(&SUnits[i]) << "\n"; dbgs() << "\t D = "
<< getDepth(&SUnits[i]) << "\n"; dbgs() <<
"\t H = " << getHeight(&SUnits[i]) << "\n"
; dbgs() << "\t ZLD = " << getZeroLatencyDepth
(&SUnits[i]) << "\n"; dbgs() << "\t ZLH = "
<< getZeroLatencyHeight(&SUnits[i]) << "\n";
} }; } } while (false)
1437 dbgs() << "\t ASAP = " << getASAP(&SUnits[i]) << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (unsigned i = 0; i < SUnits.size();
i++) { dbgs() << "\tNode " << i << ":\n"; dbgs
() << "\t ASAP = " << getASAP(&SUnits[i]) <<
"\n"; dbgs() << "\t ALAP = " << getALAP(&SUnits
[i]) << "\n"; dbgs() << "\t MOV = " << getMOV
(&SUnits[i]) << "\n"; dbgs() << "\t D = "
<< getDepth(&SUnits[i]) << "\n"; dbgs() <<
"\t H = " << getHeight(&SUnits[i]) << "\n"
; dbgs() << "\t ZLD = " << getZeroLatencyDepth
(&SUnits[i]) << "\n"; dbgs() << "\t ZLH = "
<< getZeroLatencyHeight(&SUnits[i]) << "\n";
} }; } } while (false)
1438 dbgs() << "\t ALAP = " << getALAP(&SUnits[i]) << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (unsigned i = 0; i < SUnits.size();
i++) { dbgs() << "\tNode " << i << ":\n"; dbgs
() << "\t ASAP = " << getASAP(&SUnits[i]) <<
"\n"; dbgs() << "\t ALAP = " << getALAP(&SUnits
[i]) << "\n"; dbgs() << "\t MOV = " << getMOV
(&SUnits[i]) << "\n"; dbgs() << "\t D = "
<< getDepth(&SUnits[i]) << "\n"; dbgs() <<
"\t H = " << getHeight(&SUnits[i]) << "\n"
; dbgs() << "\t ZLD = " << getZeroLatencyDepth
(&SUnits[i]) << "\n"; dbgs() << "\t ZLH = "
<< getZeroLatencyHeight(&SUnits[i]) << "\n";
} }; } } while (false)
1439 dbgs() << "\t MOV = " << getMOV(&SUnits[i]) << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (unsigned i = 0; i < SUnits.size();
i++) { dbgs() << "\tNode " << i << ":\n"; dbgs
() << "\t ASAP = " << getASAP(&SUnits[i]) <<
"\n"; dbgs() << "\t ALAP = " << getALAP(&SUnits
[i]) << "\n"; dbgs() << "\t MOV = " << getMOV
(&SUnits[i]) << "\n"; dbgs() << "\t D = "
<< getDepth(&SUnits[i]) << "\n"; dbgs() <<
"\t H = " << getHeight(&SUnits[i]) << "\n"
; dbgs() << "\t ZLD = " << getZeroLatencyDepth
(&SUnits[i]) << "\n"; dbgs() << "\t ZLH = "
<< getZeroLatencyHeight(&SUnits[i]) << "\n";
} }; } } while (false)
1440 dbgs() << "\t D = " << getDepth(&SUnits[i]) << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (unsigned i = 0; i < SUnits.size();
i++) { dbgs() << "\tNode " << i << ":\n"; dbgs
() << "\t ASAP = " << getASAP(&SUnits[i]) <<
"\n"; dbgs() << "\t ALAP = " << getALAP(&SUnits
[i]) << "\n"; dbgs() << "\t MOV = " << getMOV
(&SUnits[i]) << "\n"; dbgs() << "\t D = "
<< getDepth(&SUnits[i]) << "\n"; dbgs() <<
"\t H = " << getHeight(&SUnits[i]) << "\n"
; dbgs() << "\t ZLD = " << getZeroLatencyDepth
(&SUnits[i]) << "\n"; dbgs() << "\t ZLH = "
<< getZeroLatencyHeight(&SUnits[i]) << "\n";
} }; } } while (false)
1441 dbgs() << "\t H = " << getHeight(&SUnits[i]) << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (unsigned i = 0; i < SUnits.size();
i++) { dbgs() << "\tNode " << i << ":\n"; dbgs
() << "\t ASAP = " << getASAP(&SUnits[i]) <<
"\n"; dbgs() << "\t ALAP = " << getALAP(&SUnits
[i]) << "\n"; dbgs() << "\t MOV = " << getMOV
(&SUnits[i]) << "\n"; dbgs() << "\t D = "
<< getDepth(&SUnits[i]) << "\n"; dbgs() <<
"\t H = " << getHeight(&SUnits[i]) << "\n"
; dbgs() << "\t ZLD = " << getZeroLatencyDepth
(&SUnits[i]) << "\n"; dbgs() << "\t ZLH = "
<< getZeroLatencyHeight(&SUnits[i]) << "\n";
} }; } } while (false)
1442 dbgs() << "\t ZLD = " << getZeroLatencyDepth(&SUnits[i]) << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (unsigned i = 0; i < SUnits.size();
i++) { dbgs() << "\tNode " << i << ":\n"; dbgs
() << "\t ASAP = " << getASAP(&SUnits[i]) <<
"\n"; dbgs() << "\t ALAP = " << getALAP(&SUnits
[i]) << "\n"; dbgs() << "\t MOV = " << getMOV
(&SUnits[i]) << "\n"; dbgs() << "\t D = "
<< getDepth(&SUnits[i]) << "\n"; dbgs() <<
"\t H = " << getHeight(&SUnits[i]) << "\n"
; dbgs() << "\t ZLD = " << getZeroLatencyDepth
(&SUnits[i]) << "\n"; dbgs() << "\t ZLH = "
<< getZeroLatencyHeight(&SUnits[i]) << "\n";
} }; } } while (false)
1443 dbgs() << "\t ZLH = " << getZeroLatencyHeight(&SUnits[i]) << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (unsigned i = 0; i < SUnits.size();
i++) { dbgs() << "\tNode " << i << ":\n"; dbgs
() << "\t ASAP = " << getASAP(&SUnits[i]) <<
"\n"; dbgs() << "\t ALAP = " << getALAP(&SUnits
[i]) << "\n"; dbgs() << "\t MOV = " << getMOV
(&SUnits[i]) << "\n"; dbgs() << "\t D = "
<< getDepth(&SUnits[i]) << "\n"; dbgs() <<
"\t H = " << getHeight(&SUnits[i]) << "\n"
; dbgs() << "\t ZLD = " << getZeroLatencyDepth
(&SUnits[i]) << "\n"; dbgs() << "\t ZLH = "
<< getZeroLatencyHeight(&SUnits[i]) << "\n";
} }; } } while (false)
1444 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (unsigned i = 0; i < SUnits.size();
i++) { dbgs() << "\tNode " << i << ":\n"; dbgs
() << "\t ASAP = " << getASAP(&SUnits[i]) <<
"\n"; dbgs() << "\t ALAP = " << getALAP(&SUnits
[i]) << "\n"; dbgs() << "\t MOV = " << getMOV
(&SUnits[i]) << "\n"; dbgs() << "\t D = "
<< getDepth(&SUnits[i]) << "\n"; dbgs() <<
"\t H = " << getHeight(&SUnits[i]) << "\n"
; dbgs() << "\t ZLD = " << getZeroLatencyDepth
(&SUnits[i]) << "\n"; dbgs() << "\t ZLH = "
<< getZeroLatencyHeight(&SUnits[i]) << "\n";
} }; } } while (false)
1445 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { for (unsigned i = 0; i < SUnits.size();
i++) { dbgs() << "\tNode " << i << ":\n"; dbgs
() << "\t ASAP = " << getASAP(&SUnits[i]) <<
"\n"; dbgs() << "\t ALAP = " << getALAP(&SUnits
[i]) << "\n"; dbgs() << "\t MOV = " << getMOV
(&SUnits[i]) << "\n"; dbgs() << "\t D = "
<< getDepth(&SUnits[i]) << "\n"; dbgs() <<
"\t H = " << getHeight(&SUnits[i]) << "\n"
; dbgs() << "\t ZLD = " << getZeroLatencyDepth
(&SUnits[i]) << "\n"; dbgs() << "\t ZLH = "
<< getZeroLatencyHeight(&SUnits[i]) << "\n";
} }; } } while (false)
;
1446}
1447
1448/// Compute the Pred_L(O) set, as defined in the paper. The set is defined
1449/// as the predecessors of the elements of NodeOrder that are not also in
1450/// NodeOrder.
1451static bool pred_L(SetVector<SUnit *> &NodeOrder,
1452 SmallSetVector<SUnit *, 8> &Preds,
1453 const NodeSet *S = nullptr) {
1454 Preds.clear();
1455 for (SetVector<SUnit *>::iterator I = NodeOrder.begin(), E = NodeOrder.end();
1456 I != E; ++I) {
1457 for (SUnit::pred_iterator PI = (*I)->Preds.begin(), PE = (*I)->Preds.end();
1458 PI != PE; ++PI) {
1459 if (S && S->count(PI->getSUnit()) == 0)
1460 continue;
1461 if (ignoreDependence(*PI, true))
1462 continue;
1463 if (NodeOrder.count(PI->getSUnit()) == 0)
1464 Preds.insert(PI->getSUnit());
1465 }
1466 // Back-edges are predecessors with an anti-dependence.
1467 for (SUnit::const_succ_iterator IS = (*I)->Succs.begin(),
1468 ES = (*I)->Succs.end();
1469 IS != ES; ++IS) {
1470 if (IS->getKind() != SDep::Anti)
1471 continue;
1472 if (S && S->count(IS->getSUnit()) == 0)
1473 continue;
1474 if (NodeOrder.count(IS->getSUnit()) == 0)
1475 Preds.insert(IS->getSUnit());
1476 }
1477 }
1478 return !Preds.empty();
1479}
1480
1481/// Compute the Succ_L(O) set, as defined in the paper. The set is defined
1482/// as the successors of the elements of NodeOrder that are not also in
1483/// NodeOrder.
1484static bool succ_L(SetVector<SUnit *> &NodeOrder,
1485 SmallSetVector<SUnit *, 8> &Succs,
1486 const NodeSet *S = nullptr) {
1487 Succs.clear();
1488 for (SetVector<SUnit *>::iterator I = NodeOrder.begin(), E = NodeOrder.end();
1489 I != E; ++I) {
1490 for (SUnit::succ_iterator SI = (*I)->Succs.begin(), SE = (*I)->Succs.end();
1491 SI != SE; ++SI) {
1492 if (S && S->count(SI->getSUnit()) == 0)
1493 continue;
1494 if (ignoreDependence(*SI, false))
1495 continue;
1496 if (NodeOrder.count(SI->getSUnit()) == 0)
1497 Succs.insert(SI->getSUnit());
1498 }
1499 for (SUnit::const_pred_iterator PI = (*I)->Preds.begin(),
1500 PE = (*I)->Preds.end();
1501 PI != PE; ++PI) {
1502 if (PI->getKind() != SDep::Anti)
1503 continue;
1504 if (S && S->count(PI->getSUnit()) == 0)
1505 continue;
1506 if (NodeOrder.count(PI->getSUnit()) == 0)
1507 Succs.insert(PI->getSUnit());
1508 }
1509 }
1510 return !Succs.empty();
1511}
1512
1513/// Return true if there is a path from the specified node to any of the nodes
1514/// in DestNodes. Keep track and return the nodes in any path.
1515static bool computePath(SUnit *Cur, SetVector<SUnit *> &Path,
1516 SetVector<SUnit *> &DestNodes,
1517 SetVector<SUnit *> &Exclude,
1518 SmallPtrSet<SUnit *, 8> &Visited) {
1519 if (Cur->isBoundaryNode())
1520 return false;
1521 if (Exclude.count(Cur) != 0)
1522 return false;
1523 if (DestNodes.count(Cur) != 0)
1524 return true;
1525 if (!Visited.insert(Cur).second)
1526 return Path.count(Cur) != 0;
1527 bool FoundPath = false;
1528 for (auto &SI : Cur->Succs)
1529 FoundPath |= computePath(SI.getSUnit(), Path, DestNodes, Exclude, Visited);
1530 for (auto &PI : Cur->Preds)
1531 if (PI.getKind() == SDep::Anti)
1532 FoundPath |=
1533 computePath(PI.getSUnit(), Path, DestNodes, Exclude, Visited);
1534 if (FoundPath)
1535 Path.insert(Cur);
1536 return FoundPath;
1537}
1538
1539/// Return true if Set1 is a subset of Set2.
1540template <class S1Ty, class S2Ty> static bool isSubset(S1Ty &Set1, S2Ty &Set2) {
1541 for (typename S1Ty::iterator I = Set1.begin(), E = Set1.end(); I != E; ++I)
1542 if (Set2.count(*I) == 0)
1543 return false;
1544 return true;
1545}
1546
1547/// Compute the live-out registers for the instructions in a node-set.
1548/// The live-out registers are those that are defined in the node-set,
1549/// but not used. Except for use operands of Phis.
1550static void computeLiveOuts(MachineFunction &MF, RegPressureTracker &RPTracker,
1551 NodeSet &NS) {
1552 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
1553 MachineRegisterInfo &MRI = MF.getRegInfo();
1554 SmallVector<RegisterMaskPair, 8> LiveOutRegs;
1555 SmallSet<unsigned, 4> Uses;
1556 for (SUnit *SU : NS) {
1557 const MachineInstr *MI = SU->getInstr();
1558 if (MI->isPHI())
1559 continue;
1560 for (const MachineOperand &MO : MI->operands())
1561 if (MO.isReg() && MO.isUse()) {
1562 Register Reg = MO.getReg();
1563 if (Register::isVirtualRegister(Reg))
1564 Uses.insert(Reg);
1565 else if (MRI.isAllocatable(Reg))
1566 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units)
1567 Uses.insert(*Units);
1568 }
1569 }
1570 for (SUnit *SU : NS)
1571 for (const MachineOperand &MO : SU->getInstr()->operands())
1572 if (MO.isReg() && MO.isDef() && !MO.isDead()) {
1573 Register Reg = MO.getReg();
1574 if (Register::isVirtualRegister(Reg)) {
1575 if (!Uses.count(Reg))
1576 LiveOutRegs.push_back(RegisterMaskPair(Reg,
1577 LaneBitmask::getNone()));
1578 } else if (MRI.isAllocatable(Reg)) {
1579 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units)
1580 if (!Uses.count(*Units))
1581 LiveOutRegs.push_back(RegisterMaskPair(*Units,
1582 LaneBitmask::getNone()));
1583 }
1584 }
1585 RPTracker.addLiveRegs(LiveOutRegs);
1586}
1587
1588/// A heuristic to filter nodes in recurrent node-sets if the register
1589/// pressure of a set is too high.
1590void SwingSchedulerDAG::registerPressureFilter(NodeSetType &NodeSets) {
1591 for (auto &NS : NodeSets) {
1592 // Skip small node-sets since they won't cause register pressure problems.
1593 if (NS.size() <= 2)
1594 continue;
1595 IntervalPressure RecRegPressure;
1596 RegPressureTracker RecRPTracker(RecRegPressure);
1597 RecRPTracker.init(&MF, &RegClassInfo, &LIS, BB, BB->end(), false, true);
1598 computeLiveOuts(MF, RecRPTracker, NS);
1599 RecRPTracker.closeBottom();
1600
1601 std::vector<SUnit *> SUnits(NS.begin(), NS.end());
1602 llvm::sort(SUnits, [](const SUnit *A, const SUnit *B) {
1603 return A->NodeNum > B->NodeNum;
1604 });
1605
1606 for (auto &SU : SUnits) {
1607 // Since we're computing the register pressure for a subset of the
1608 // instructions in a block, we need to set the tracker for each
1609 // instruction in the node-set. The tracker is set to the instruction
1610 // just after the one we're interested in.
1611 MachineBasicBlock::const_iterator CurInstI = SU->getInstr();
1612 RecRPTracker.setPos(std::next(CurInstI));
1613
1614 RegPressureDelta RPDelta;
1615 ArrayRef<PressureChange> CriticalPSets;
1616 RecRPTracker.getMaxUpwardPressureDelta(SU->getInstr(), nullptr, RPDelta,
1617 CriticalPSets,
1618 RecRegPressure.MaxSetPressure);
1619 if (RPDelta.Excess.isValid()) {
1620 LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "Excess register pressure: SU("
<< SU->NodeNum << ") " << TRI->getRegPressureSetName
(RPDelta.Excess.getPSet()) << ":" << RPDelta.Excess
.getUnitInc(); } } while (false)
1621 dbgs() << "Excess register pressure: SU(" << SU->NodeNum << ") "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "Excess register pressure: SU("
<< SU->NodeNum << ") " << TRI->getRegPressureSetName
(RPDelta.Excess.getPSet()) << ":" << RPDelta.Excess
.getUnitInc(); } } while (false)
1622 << TRI->getRegPressureSetName(RPDelta.Excess.getPSet())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "Excess register pressure: SU("
<< SU->NodeNum << ") " << TRI->getRegPressureSetName
(RPDelta.Excess.getPSet()) << ":" << RPDelta.Excess
.getUnitInc(); } } while (false)
1623 << ":" << RPDelta.Excess.getUnitInc())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "Excess register pressure: SU("
<< SU->NodeNum << ") " << TRI->getRegPressureSetName
(RPDelta.Excess.getPSet()) << ":" << RPDelta.Excess
.getUnitInc(); } } while (false)
;
1624 NS.setExceedPressure(SU);
1625 break;
1626 }
1627 RecRPTracker.recede();
1628 }
1629 }
1630}
1631
1632/// A heuristic to colocate node sets that have the same set of
1633/// successors.
1634void SwingSchedulerDAG::colocateNodeSets(NodeSetType &NodeSets) {
1635 unsigned Colocate = 0;
1636 for (int i = 0, e = NodeSets.size(); i < e; ++i) {
1637 NodeSet &N1 = NodeSets[i];
1638 SmallSetVector<SUnit *, 8> S1;
1639 if (N1.empty() || !succ_L(N1, S1))
1640 continue;
1641 for (int j = i + 1; j < e; ++j) {
1642 NodeSet &N2 = NodeSets[j];
1643 if (N1.compareRecMII(N2) != 0)
1644 continue;
1645 SmallSetVector<SUnit *, 8> S2;
1646 if (N2.empty() || !succ_L(N2, S2))
1647 continue;
1648 if (isSubset(S1, S2) && S1.size() == S2.size()) {
1649 N1.setColocate(++Colocate);
1650 N2.setColocate(Colocate);
1651 break;
1652 }
1653 }
1654 }
1655}
1656
1657/// Check if the existing node-sets are profitable. If not, then ignore the
1658/// recurrent node-sets, and attempt to schedule all nodes together. This is
1659/// a heuristic. If the MII is large and all the recurrent node-sets are small,
1660/// then it's best to try to schedule all instructions together instead of
1661/// starting with the recurrent node-sets.
1662void SwingSchedulerDAG::checkNodeSets(NodeSetType &NodeSets) {
1663 // Look for loops with a large MII.
1664 if (MII < 17)
1665 return;
1666 // Check if the node-set contains only a simple add recurrence.
1667 for (auto &NS : NodeSets) {
1668 if (NS.getRecMII() > 2)
1669 return;
1670 if (NS.getMaxDepth() > MII)
1671 return;
1672 }
1673 NodeSets.clear();
1674 LLVM_DEBUG(dbgs() << "Clear recurrence node-sets\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "Clear recurrence node-sets\n"
; } } while (false)
;
1675 return;
1676}
1677
1678/// Add the nodes that do not belong to a recurrence set into groups
1679/// based upon connected componenets.
1680void SwingSchedulerDAG::groupRemainingNodes(NodeSetType &NodeSets) {
1681 SetVector<SUnit *> NodesAdded;
1682 SmallPtrSet<SUnit *, 8> Visited;
1683 // Add the nodes that are on a path between the previous node sets and
1684 // the current node set.
1685 for (NodeSet &I : NodeSets) {
1686 SmallSetVector<SUnit *, 8> N;
1687 // Add the nodes from the current node set to the previous node set.
1688 if (succ_L(I, N)) {
1689 SetVector<SUnit *> Path;
1690 for (SUnit *NI : N) {
1691 Visited.clear();
1692 computePath(NI, Path, NodesAdded, I, Visited);
1693 }
1694 if (!Path.empty())
1695 I.insert(Path.begin(), Path.end());
1696 }
1697 // Add the nodes from the previous node set to the current node set.
1698 N.clear();
1699 if (succ_L(NodesAdded, N)) {
1700 SetVector<SUnit *> Path;
1701 for (SUnit *NI : N) {
1702 Visited.clear();
1703 computePath(NI, Path, I, NodesAdded, Visited);
1704 }
1705 if (!Path.empty())
1706 I.insert(Path.begin(), Path.end());
1707 }
1708 NodesAdded.insert(I.begin(), I.end());
1709 }
1710
1711 // Create a new node set with the connected nodes of any successor of a node
1712 // in a recurrent set.
1713 NodeSet NewSet;
1714 SmallSetVector<SUnit *, 8> N;
1715 if (succ_L(NodesAdded, N))
1716 for (SUnit *I : N)
1717 addConnectedNodes(I, NewSet, NodesAdded);
1718 if (!NewSet.empty())
1719 NodeSets.push_back(NewSet);
1720
1721 // Create a new node set with the connected nodes of any predecessor of a node
1722 // in a recurrent set.
1723 NewSet.clear();
1724 if (pred_L(NodesAdded, N))
1725 for (SUnit *I : N)
1726 addConnectedNodes(I, NewSet, NodesAdded);
1727 if (!NewSet.empty())
1728 NodeSets.push_back(NewSet);
1729
1730 // Create new nodes sets with the connected nodes any remaining node that
1731 // has no predecessor.
1732 for (unsigned i = 0; i < SUnits.size(); ++i) {
1733 SUnit *SU = &SUnits[i];
1734 if (NodesAdded.count(SU) == 0) {
1735 NewSet.clear();
1736 addConnectedNodes(SU, NewSet, NodesAdded);
1737 if (!NewSet.empty())
1738 NodeSets.push_back(NewSet);
1739 }
1740 }
1741}
1742
1743/// Add the node to the set, and add all of its connected nodes to the set.
1744void SwingSchedulerDAG::addConnectedNodes(SUnit *SU, NodeSet &NewSet,
1745 SetVector<SUnit *> &NodesAdded) {
1746 NewSet.insert(SU);
1747 NodesAdded.insert(SU);
1748 for (auto &SI : SU->Succs) {
1749 SUnit *Successor = SI.getSUnit();
1750 if (!SI.isArtificial() && NodesAdded.count(Successor) == 0)
1751 addConnectedNodes(Successor, NewSet, NodesAdded);
1752 }
1753 for (auto &PI : SU->Preds) {
1754 SUnit *Predecessor = PI.getSUnit();
1755 if (!PI.isArtificial() && NodesAdded.count(Predecessor) == 0)
1756 addConnectedNodes(Predecessor, NewSet, NodesAdded);
1757 }
1758}
1759
1760/// Return true if Set1 contains elements in Set2. The elements in common
1761/// are returned in a different container.
1762static bool isIntersect(SmallSetVector<SUnit *, 8> &Set1, const NodeSet &Set2,
1763 SmallSetVector<SUnit *, 8> &Result) {
1764 Result.clear();
1765 for (unsigned i = 0, e = Set1.size(); i != e; ++i) {
1766 SUnit *SU = Set1[i];
1767 if (Set2.count(SU) != 0)
1768 Result.insert(SU);
1769 }
1770 return !Result.empty();
1771}
1772
1773/// Merge the recurrence node sets that have the same initial node.
1774void SwingSchedulerDAG::fuseRecs(NodeSetType &NodeSets) {
1775 for (NodeSetType::iterator I = NodeSets.begin(), E = NodeSets.end(); I != E;
1776 ++I) {
1777 NodeSet &NI = *I;
1778 for (NodeSetType::iterator J = I + 1; J != E;) {
1779 NodeSet &NJ = *J;
1780 if (NI.getNode(0)->NodeNum == NJ.getNode(0)->NodeNum) {
1781 if (NJ.compareRecMII(NI) > 0)
1782 NI.setRecMII(NJ.getRecMII());
1783 for (NodeSet::iterator NII = J->begin(), ENI = J->end(); NII != ENI;
1784 ++NII)
1785 I->insert(*NII);
1786 NodeSets.erase(J);
1787 E = NodeSets.end();
1788 } else {
1789 ++J;
1790 }
1791 }
1792 }
1793}
1794
1795/// Remove nodes that have been scheduled in previous NodeSets.
1796void SwingSchedulerDAG::removeDuplicateNodes(NodeSetType &NodeSets) {
1797 for (NodeSetType::iterator I = NodeSets.begin(), E = NodeSets.end(); I != E;
1798 ++I)
1799 for (NodeSetType::iterator J = I + 1; J != E;) {
1800 J->remove_if([&](SUnit *SUJ) { return I->count(SUJ); });
1801
1802 if (J->empty()) {
1803 NodeSets.erase(J);
1804 E = NodeSets.end();
1805 } else {
1806 ++J;
1807 }
1808 }
1809}
1810
1811/// Compute an ordered list of the dependence graph nodes, which
1812/// indicates the order that the nodes will be scheduled. This is a
1813/// two-level algorithm. First, a partial order is created, which
1814/// consists of a list of sets ordered from highest to lowest priority.
1815void SwingSchedulerDAG::computeNodeOrder(NodeSetType &NodeSets) {
1816 SmallSetVector<SUnit *, 8> R;
1817 NodeOrder.clear();
1818
1819 for (auto &Nodes : NodeSets) {
1820 LLVM_DEBUG(dbgs() << "NodeSet size " << Nodes.size() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "NodeSet size " << Nodes
.size() << "\n"; } } while (false)
;
1821 OrderKind Order;
1822 SmallSetVector<SUnit *, 8> N;
1823 if (pred_L(NodeOrder, N) && isSubset(N, Nodes)) {
1824 R.insert(N.begin(), N.end());
1825 Order = BottomUp;
1826 LLVM_DEBUG(dbgs() << " Bottom up (preds) ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << " Bottom up (preds) "; } } while
(false)
;
1827 } else if (succ_L(NodeOrder, N) && isSubset(N, Nodes)) {
1828 R.insert(N.begin(), N.end());
1829 Order = TopDown;
1830 LLVM_DEBUG(dbgs() << " Top down (succs) ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << " Top down (succs) "; } } while
(false)
;
1831 } else if (isIntersect(N, Nodes, R)) {
1832 // If some of the successors are in the existing node-set, then use the
1833 // top-down ordering.
1834 Order = TopDown;
1835 LLVM_DEBUG(dbgs() << " Top down (intersect) ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << " Top down (intersect) "; }
} while (false)
;
1836 } else if (NodeSets.size() == 1) {
1837 for (auto &N : Nodes)
1838 if (N->Succs.size() == 0)
1839 R.insert(N);
1840 Order = BottomUp;
1841 LLVM_DEBUG(dbgs() << " Bottom up (all) ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << " Bottom up (all) "; } } while
(false)
;
1842 } else {
1843 // Find the node with the highest ASAP.
1844 SUnit *maxASAP = nullptr;
1845 for (SUnit *SU : Nodes) {
1846 if (maxASAP == nullptr || getASAP(SU) > getASAP(maxASAP) ||
1847 (getASAP(SU) == getASAP(maxASAP) && SU->NodeNum > maxASAP->NodeNum))
1848 maxASAP = SU;
1849 }
1850 R.insert(maxASAP);
1851 Order = BottomUp;
1852 LLVM_DEBUG(dbgs() << " Bottom up (default) ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << " Bottom up (default) "; } }
while (false)
;
1853 }
1854
1855 while (!R.empty()) {
1856 if (Order == TopDown) {
1857 // Choose the node with the maximum height. If more than one, choose
1858 // the node wiTH the maximum ZeroLatencyHeight. If still more than one,
1859 // choose the node with the lowest MOV.
1860 while (!R.empty()) {
1861 SUnit *maxHeight = nullptr;
1862 for (SUnit *I : R) {
1863 if (maxHeight == nullptr || getHeight(I) > getHeight(maxHeight))
1864 maxHeight = I;
1865 else if (getHeight(I) == getHeight(maxHeight) &&
1866 getZeroLatencyHeight(I) > getZeroLatencyHeight(maxHeight))
1867 maxHeight = I;
1868 else if (getHeight(I) == getHeight(maxHeight) &&
1869 getZeroLatencyHeight(I) ==
1870 getZeroLatencyHeight(maxHeight) &&
1871 getMOV(I) < getMOV(maxHeight))
1872 maxHeight = I;
1873 }
1874 NodeOrder.insert(maxHeight);
1875 LLVM_DEBUG(dbgs() << maxHeight->NodeNum << " ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << maxHeight->NodeNum <<
" "; } } while (false)
;
1876 R.remove(maxHeight);
1877 for (const auto &I : maxHeight->Succs) {
1878 if (Nodes.count(I.getSUnit()) == 0)
1879 continue;
1880 if (NodeOrder.count(I.getSUnit()) != 0)
1881 continue;
1882 if (ignoreDependence(I, false))
1883 continue;
1884 R.insert(I.getSUnit());
1885 }
1886 // Back-edges are predecessors with an anti-dependence.
1887 for (const auto &I : maxHeight->Preds) {
1888 if (I.getKind() != SDep::Anti)
1889 continue;
1890 if (Nodes.count(I.getSUnit()) == 0)
1891 continue;
1892 if (NodeOrder.count(I.getSUnit()) != 0)
1893 continue;
1894 R.insert(I.getSUnit());
1895 }
1896 }
1897 Order = BottomUp;
1898 LLVM_DEBUG(dbgs() << "\n Switching order to bottom up ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "\n Switching order to bottom up "
; } } while (false)
;
1899 SmallSetVector<SUnit *, 8> N;
1900 if (pred_L(NodeOrder, N, &Nodes))
1901 R.insert(N.begin(), N.end());
1902 } else {
1903 // Choose the node with the maximum depth. If more than one, choose
1904 // the node with the maximum ZeroLatencyDepth. If still more than one,
1905 // choose the node with the lowest MOV.
1906 while (!R.empty()) {
1907 SUnit *maxDepth = nullptr;
1908 for (SUnit *I : R) {
1909 if (maxDepth == nullptr || getDepth(I) > getDepth(maxDepth))
1910 maxDepth = I;
1911 else if (getDepth(I) == getDepth(maxDepth) &&
1912 getZeroLatencyDepth(I) > getZeroLatencyDepth(maxDepth))
1913 maxDepth = I;
1914 else if (getDepth(I) == getDepth(maxDepth) &&
1915 getZeroLatencyDepth(I) == getZeroLatencyDepth(maxDepth) &&
1916 getMOV(I) < getMOV(maxDepth))
1917 maxDepth = I;
1918 }
1919 NodeOrder.insert(maxDepth);
1920 LLVM_DEBUG(dbgs() << maxDepth->NodeNum << " ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << maxDepth->NodeNum <<
" "; } } while (false)
;
1921 R.remove(maxDepth);
1922 if (Nodes.isExceedSU(maxDepth)) {
1923 Order = TopDown;
Value stored to 'Order' is never read
1924 R.clear();
1925 R.insert(Nodes.getNode(0));
1926 break;
1927 }
1928 for (const auto &I : maxDepth->Preds) {
1929 if (Nodes.count(I.getSUnit()) == 0)
1930 continue;
1931 if (NodeOrder.count(I.getSUnit()) != 0)
1932 continue;
1933 R.insert(I.getSUnit());
1934 }
1935 // Back-edges are predecessors with an anti-dependence.
1936 for (const auto &I : maxDepth->Succs) {
1937 if (I.getKind() != SDep::Anti)
1938 continue;
1939 if (Nodes.count(I.getSUnit()) == 0)
1940 continue;
1941 if (NodeOrder.count(I.getSUnit()) != 0)
1942 continue;
1943 R.insert(I.getSUnit());
1944 }
1945 }
1946 Order = TopDown;
1947 LLVM_DEBUG(dbgs() << "\n Switching order to top down ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "\n Switching order to top down "
; } } while (false)
;
1948 SmallSetVector<SUnit *, 8> N;
1949 if (succ_L(NodeOrder, N, &Nodes))
1950 R.insert(N.begin(), N.end());
1951 }
1952 }
1953 LLVM_DEBUG(dbgs() << "\nDone with Nodeset\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "\nDone with Nodeset\n"; } }
while (false)
;
1954 }
1955
1956 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "Node order: "; for (SUnit
*I : NodeOrder) dbgs() << " " << I->NodeNum <<
" "; dbgs() << "\n"; }; } } while (false)
1957 dbgs() << "Node order: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "Node order: "; for (SUnit
*I : NodeOrder) dbgs() << " " << I->NodeNum <<
" "; dbgs() << "\n"; }; } } while (false)
1958 for (SUnit *I : NodeOrder)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "Node order: "; for (SUnit
*I : NodeOrder) dbgs() << " " << I->NodeNum <<
" "; dbgs() << "\n"; }; } } while (false)
1959 dbgs() << " " << I->NodeNum << " ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "Node order: "; for (SUnit
*I : NodeOrder) dbgs() << " " << I->NodeNum <<
" "; dbgs() << "\n"; }; } } while (false)
1960 dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "Node order: "; for (SUnit
*I : NodeOrder) dbgs() << " " << I->NodeNum <<
" "; dbgs() << "\n"; }; } } while (false)
1961 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "Node order: "; for (SUnit
*I : NodeOrder) dbgs() << " " << I->NodeNum <<
" "; dbgs() << "\n"; }; } } while (false)
;
1962}
1963
1964/// Process the nodes in the computed order and create the pipelined schedule
1965/// of the instructions, if possible. Return true if a schedule is found.
1966bool SwingSchedulerDAG::schedulePipeline(SMSchedule &Schedule) {
1967
1968 if (NodeOrder.empty()){
1969 LLVM_DEBUG(dbgs() << "NodeOrder is empty! abort scheduling\n" )do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "NodeOrder is empty! abort scheduling\n"
; } } while (false)
;
1970 return false;
1971 }
1972
1973 bool scheduleFound = false;
1974 unsigned II = 0;
1975 // Keep increasing II until a valid schedule is found.
1976 for (II = MII; II <= MAX_II && !scheduleFound; ++II) {
1977 Schedule.reset();
1978 Schedule.setInitiationInterval(II);
1979 LLVM_DEBUG(dbgs() << "Try to schedule with " << II << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "Try to schedule with " <<
II << "\n"; } } while (false)
;
1980
1981 SetVector<SUnit *>::iterator NI = NodeOrder.begin();
1982 SetVector<SUnit *>::iterator NE = NodeOrder.end();
1983 do {
1984 SUnit *SU = *NI;
1985
1986 // Compute the schedule time for the instruction, which is based
1987 // upon the scheduled time for any predecessors/successors.
1988 int EarlyStart = INT_MIN(-2147483647 -1);
1989 int LateStart = INT_MAX2147483647;
1990 // These values are set when the size of the schedule window is limited
1991 // due to chain dependences.
1992 int SchedEnd = INT_MAX2147483647;
1993 int SchedStart = INT_MIN(-2147483647 -1);
1994 Schedule.computeStart(SU, &EarlyStart, &LateStart, &SchedEnd, &SchedStart,
1995 II, this);
1996 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "\n"; dbgs() << "Inst ("
<< SU->NodeNum << ") "; SU->getInstr()->
dump(); dbgs() << "\n"; }; } } while (false)
1997 dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "\n"; dbgs() << "Inst ("
<< SU->NodeNum << ") "; SU->getInstr()->
dump(); dbgs() << "\n"; }; } } while (false)
1998 dbgs() << "Inst (" << SU->NodeNum << ") ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "\n"; dbgs() << "Inst ("
<< SU->NodeNum << ") "; SU->getInstr()->
dump(); dbgs() << "\n"; }; } } while (false)
1999 SU->getInstr()->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "\n"; dbgs() << "Inst ("
<< SU->NodeNum << ") "; SU->getInstr()->
dump(); dbgs() << "\n"; }; } } while (false)
2000 dbgs() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "\n"; dbgs() << "Inst ("
<< SU->NodeNum << ") "; SU->getInstr()->
dump(); dbgs() << "\n"; }; } } while (false)
2001 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "\n"; dbgs() << "Inst ("
<< SU->NodeNum << ") "; SU->getInstr()->
dump(); dbgs() << "\n"; }; } } while (false)
;
2002 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << format("\tes: %8x ls: %8x me: %8x ms: %8x\n"
, EarlyStart, LateStart, SchedEnd, SchedStart); }; } } while (
false)
2003 dbgs() << format("\tes: %8x ls: %8x me: %8x ms: %8x\n", EarlyStart,do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << format("\tes: %8x ls: %8x me: %8x ms: %8x\n"
, EarlyStart, LateStart, SchedEnd, SchedStart); }; } } while (
false)
2004 LateStart, SchedEnd, SchedStart);do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << format("\tes: %8x ls: %8x me: %8x ms: %8x\n"
, EarlyStart, LateStart, SchedEnd, SchedStart); }; } } while (
false)
2005 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << format("\tes: %8x ls: %8x me: %8x ms: %8x\n"
, EarlyStart, LateStart, SchedEnd, SchedStart); }; } } while (
false)
;
2006
2007 if (EarlyStart > LateStart || SchedEnd < EarlyStart ||
2008 SchedStart > LateStart)
2009 scheduleFound = false;
2010 else if (EarlyStart != INT_MIN(-2147483647 -1) && LateStart == INT_MAX2147483647) {
2011 SchedEnd = std::min(SchedEnd, EarlyStart + (int)II - 1);
2012 scheduleFound = Schedule.insert(SU, EarlyStart, SchedEnd, II);
2013 } else if (EarlyStart == INT_MIN(-2147483647 -1) && LateStart != INT_MAX2147483647) {
2014 SchedStart = std::max(SchedStart, LateStart - (int)II + 1);
2015 scheduleFound = Schedule.insert(SU, LateStart, SchedStart, II);
2016 } else if (EarlyStart != INT_MIN(-2147483647 -1) && LateStart != INT_MAX2147483647) {
2017 SchedEnd =
2018 std::min(SchedEnd, std::min(LateStart, EarlyStart + (int)II - 1));
2019 // When scheduling a Phi it is better to start at the late cycle and go
2020 // backwards. The default order may insert the Phi too far away from
2021 // its first dependence.
2022 if (SU->getInstr()->isPHI())
2023 scheduleFound = Schedule.insert(SU, SchedEnd, EarlyStart, II);
2024 else
2025 scheduleFound = Schedule.insert(SU, EarlyStart, SchedEnd, II);
2026 } else {
2027 int FirstCycle = Schedule.getFirstCycle();
2028 scheduleFound = Schedule.insert(SU, FirstCycle + getASAP(SU),
2029 FirstCycle + getASAP(SU) + II - 1, II);
2030 }
2031 // Even if we find a schedule, make sure the schedule doesn't exceed the
2032 // allowable number of stages. We keep trying if this happens.
2033 if (scheduleFound)
2034 if (SwpMaxStages > -1 &&
2035 Schedule.getMaxStageCount() > (unsigned)SwpMaxStages)
2036 scheduleFound = false;
2037
2038 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (!scheduleFound) dbgs() << "\tCan't schedule\n"
; }; } } while (false)
2039 if (!scheduleFound)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (!scheduleFound) dbgs() << "\tCan't schedule\n"
; }; } } while (false)
2040 dbgs() << "\tCan't schedule\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (!scheduleFound) dbgs() << "\tCan't schedule\n"
; }; } } while (false)
2041 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (!scheduleFound) dbgs() << "\tCan't schedule\n"
; }; } } while (false)
;
2042 } while (++NI != NE && scheduleFound);
2043
2044 // If a schedule is found, check if it is a valid schedule too.
2045 if (scheduleFound)
2046 scheduleFound = Schedule.isValidSchedule(this);
2047 }
2048
2049 LLVM_DEBUG(dbgs() << "Schedule Found? " << scheduleFound << " (II=" << IIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "Schedule Found? " << scheduleFound
<< " (II=" << II << ")\n"; } } while (false
)
2050 << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "Schedule Found? " << scheduleFound
<< " (II=" << II << ")\n"; } } while (false
)
;
2051
2052 if (scheduleFound)
2053 Schedule.finalizeSchedule(this);
2054 else
2055 Schedule.reset();
2056
2057 return scheduleFound && Schedule.getMaxStageCount() > 0;
2058}
2059
2060/// Return true if we can compute the amount the instruction changes
2061/// during each iteration. Set Delta to the amount of the change.
2062bool SwingSchedulerDAG::computeDelta(MachineInstr &MI, unsigned &Delta) {
2063 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
2064 const MachineOperand *BaseOp;
2065 int64_t Offset;
2066 bool OffsetIsScalable;
2067 if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, OffsetIsScalable, TRI))
2068 return false;
2069
2070 // FIXME: This algorithm assumes instructions have fixed-size offsets.
2071 if (OffsetIsScalable)
2072 return false;
2073
2074 if (!BaseOp->isReg())
2075 return false;
2076
2077 Register BaseReg = BaseOp->getReg();
2078
2079 MachineRegisterInfo &MRI = MF.getRegInfo();
2080 // Check if there is a Phi. If so, get the definition in the loop.
2081 MachineInstr *BaseDef = MRI.getVRegDef(BaseReg);
2082 if (BaseDef && BaseDef->isPHI()) {
2083 BaseReg = getLoopPhiReg(*BaseDef, MI.getParent());
2084 BaseDef = MRI.getVRegDef(BaseReg);
2085 }
2086 if (!BaseDef)
2087 return false;
2088
2089 int D = 0;
2090 if (!TII->getIncrementValue(*BaseDef, D) && D >= 0)
2091 return false;
2092
2093 Delta = D;
2094 return true;
2095}
2096
2097/// Check if we can change the instruction to use an offset value from the
2098/// previous iteration. If so, return true and set the base and offset values
2099/// so that we can rewrite the load, if necessary.
2100/// v1 = Phi(v0, v3)
2101/// v2 = load v1, 0
2102/// v3 = post_store v1, 4, x
2103/// This function enables the load to be rewritten as v2 = load v3, 4.
2104bool SwingSchedulerDAG::canUseLastOffsetValue(MachineInstr *MI,
2105 unsigned &BasePos,
2106 unsigned &OffsetPos,
2107 unsigned &NewBase,
2108 int64_t &Offset) {
2109 // Get the load instruction.
2110 if (TII->isPostIncrement(*MI))
2111 return false;
2112 unsigned BasePosLd, OffsetPosLd;
2113 if (!TII->getBaseAndOffsetPosition(*MI, BasePosLd, OffsetPosLd))
2114 return false;
2115 Register BaseReg = MI->getOperand(BasePosLd).getReg();
2116
2117 // Look for the Phi instruction.
2118 MachineRegisterInfo &MRI = MI->getMF()->getRegInfo();
2119 MachineInstr *Phi = MRI.getVRegDef(BaseReg);
2120 if (!Phi || !Phi->isPHI())
2121 return false;
2122 // Get the register defined in the loop block.
2123 unsigned PrevReg = getLoopPhiReg(*Phi, MI->getParent());
2124 if (!PrevReg)
2125 return false;
2126
2127 // Check for the post-increment load/store instruction.
2128 MachineInstr *PrevDef = MRI.getVRegDef(PrevReg);
2129 if (!PrevDef || PrevDef == MI)
2130 return false;
2131
2132 if (!TII->isPostIncrement(*PrevDef))
2133 return false;
2134
2135 unsigned BasePos1 = 0, OffsetPos1 = 0;
2136 if (!TII->getBaseAndOffsetPosition(*PrevDef, BasePos1, OffsetPos1))
2137 return false;
2138
2139 // Make sure that the instructions do not access the same memory location in
2140 // the next iteration.
2141 int64_t LoadOffset = MI->getOperand(OffsetPosLd).getImm();
2142 int64_t StoreOffset = PrevDef->getOperand(OffsetPos1).getImm();
2143 MachineInstr *NewMI = MF.CloneMachineInstr(MI);
2144 NewMI->getOperand(OffsetPosLd).setImm(LoadOffset + StoreOffset);
2145 bool Disjoint = TII->areMemAccessesTriviallyDisjoint(*NewMI, *PrevDef);
2146 MF.DeleteMachineInstr(NewMI);
2147 if (!Disjoint)
2148 return false;
2149
2150 // Set the return value once we determine that we return true.
2151 BasePos = BasePosLd;
2152 OffsetPos = OffsetPosLd;
2153 NewBase = PrevReg;
2154 Offset = StoreOffset;
2155 return true;
2156}
2157
2158/// Apply changes to the instruction if needed. The changes are need
2159/// to improve the scheduling and depend up on the final schedule.
2160void SwingSchedulerDAG::applyInstrChange(MachineInstr *MI,
2161 SMSchedule &Schedule) {
2162 SUnit *SU = getSUnit(MI);
2163 DenseMap<SUnit *, std::pair<unsigned, int64_t>>::iterator It =
2164 InstrChanges.find(SU);
2165 if (It != InstrChanges.end()) {
2166 std::pair<unsigned, int64_t> RegAndOffset = It->second;
2167 unsigned BasePos, OffsetPos;
2168 if (!TII->getBaseAndOffsetPosition(*MI, BasePos, OffsetPos))
2169 return;
2170 Register BaseReg = MI->getOperand(BasePos).getReg();
2171 MachineInstr *LoopDef = findDefInLoop(BaseReg);
2172 int DefStageNum = Schedule.stageScheduled(getSUnit(LoopDef));
2173 int DefCycleNum = Schedule.cycleScheduled(getSUnit(LoopDef));
2174 int BaseStageNum = Schedule.stageScheduled(SU);
2175 int BaseCycleNum = Schedule.cycleScheduled(SU);
2176 if (BaseStageNum < DefStageNum) {
2177 MachineInstr *NewMI = MF.CloneMachineInstr(MI);
2178 int OffsetDiff = DefStageNum - BaseStageNum;
2179 if (DefCycleNum < BaseCycleNum) {
2180 NewMI->getOperand(BasePos).setReg(RegAndOffset.first);
2181 if (OffsetDiff > 0)
2182 --OffsetDiff;
2183 }
2184 int64_t NewOffset =
2185 MI->getOperand(OffsetPos).getImm() + RegAndOffset.second * OffsetDiff;
2186 NewMI->getOperand(OffsetPos).setImm(NewOffset);
2187 SU->setInstr(NewMI);
2188 MISUnitMap[NewMI] = SU;
2189 NewMIs[MI] = NewMI;
2190 }
2191 }
2192}
2193
2194/// Return the instruction in the loop that defines the register.
2195/// If the definition is a Phi, then follow the Phi operand to
2196/// the instruction in the loop.
2197MachineInstr *SwingSchedulerDAG::findDefInLoop(unsigned Reg) {
2198 SmallPtrSet<MachineInstr *, 8> Visited;
2199 MachineInstr *Def = MRI.getVRegDef(Reg);
2200 while (Def->isPHI()) {
2201 if (!Visited.insert(Def).second)
2202 break;
2203 for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2)
2204 if (Def->getOperand(i + 1).getMBB() == BB) {
2205 Def = MRI.getVRegDef(Def->getOperand(i).getReg());
2206 break;
2207 }
2208 }
2209 return Def;
2210}
2211
2212/// Return true for an order or output dependence that is loop carried
2213/// potentially. A dependence is loop carried if the destination defines a valu
2214/// that may be used or defined by the source in a subsequent iteration.
2215bool SwingSchedulerDAG::isLoopCarriedDep(SUnit *Source, const SDep &Dep,
2216 bool isSucc) {
2217 if ((Dep.getKind() != SDep::Order && Dep.getKind() != SDep::Output) ||
2218 Dep.isArtificial())
2219 return false;
2220
2221 if (!SwpPruneLoopCarried)
2222 return true;
2223
2224 if (Dep.getKind() == SDep::Output)
2225 return true;
2226
2227 MachineInstr *SI = Source->getInstr();
2228 MachineInstr *DI = Dep.getSUnit()->getInstr();
2229 if (!isSucc)
2230 std::swap(SI, DI);
2231 assert(SI != nullptr && DI != nullptr && "Expecting SUnit with an MI.")((SI != nullptr && DI != nullptr && "Expecting SUnit with an MI."
) ? static_cast<void> (0) : __assert_fail ("SI != nullptr && DI != nullptr && \"Expecting SUnit with an MI.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 2231, __PRETTY_FUNCTION__))
;
2232
2233 // Assume ordered loads and stores may have a loop carried dependence.
2234 if (SI->hasUnmodeledSideEffects() || DI->hasUnmodeledSideEffects() ||
2235 SI->mayRaiseFPException() || DI->mayRaiseFPException() ||
2236 SI->hasOrderedMemoryRef() || DI->hasOrderedMemoryRef())
2237 return true;
2238
2239 // Only chain dependences between a load and store can be loop carried.
2240 if (!DI->mayStore() || !SI->mayLoad())
2241 return false;
2242
2243 unsigned DeltaS, DeltaD;
2244 if (!computeDelta(*SI, DeltaS) || !computeDelta(*DI, DeltaD))
2245 return true;
2246
2247 const MachineOperand *BaseOpS, *BaseOpD;
2248 int64_t OffsetS, OffsetD;
2249 bool OffsetSIsScalable, OffsetDIsScalable;
2250 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
2251 if (!TII->getMemOperandWithOffset(*SI, BaseOpS, OffsetS, OffsetSIsScalable,
2252 TRI) ||
2253 !TII->getMemOperandWithOffset(*DI, BaseOpD, OffsetD, OffsetDIsScalable,
2254 TRI))
2255 return true;
2256
2257 assert(!OffsetSIsScalable && !OffsetDIsScalable &&((!OffsetSIsScalable && !OffsetDIsScalable &&
"Expected offsets to be byte offsets") ? static_cast<void
> (0) : __assert_fail ("!OffsetSIsScalable && !OffsetDIsScalable && \"Expected offsets to be byte offsets\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 2258, __PRETTY_FUNCTION__))
2258 "Expected offsets to be byte offsets")((!OffsetSIsScalable && !OffsetDIsScalable &&
"Expected offsets to be byte offsets") ? static_cast<void
> (0) : __assert_fail ("!OffsetSIsScalable && !OffsetDIsScalable && \"Expected offsets to be byte offsets\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 2258, __PRETTY_FUNCTION__))
;
2259
2260 if (!BaseOpS->isIdenticalTo(*BaseOpD))
2261 return true;
2262
2263 // Check that the base register is incremented by a constant value for each
2264 // iteration.
2265 MachineInstr *Def = MRI.getVRegDef(BaseOpS->getReg());
2266 if (!Def || !Def->isPHI())
2267 return true;
2268 unsigned InitVal = 0;
2269 unsigned LoopVal = 0;
2270 getPhiRegs(*Def, BB, InitVal, LoopVal);
2271 MachineInstr *LoopDef = MRI.getVRegDef(LoopVal);
2272 int D = 0;
2273 if (!LoopDef || !TII->getIncrementValue(*LoopDef, D))
2274 return true;
2275
2276 uint64_t AccessSizeS = (*SI->memoperands_begin())->getSize();
2277 uint64_t AccessSizeD = (*DI->memoperands_begin())->getSize();
2278
2279 // This is the main test, which checks the offset values and the loop
2280 // increment value to determine if the accesses may be loop carried.
2281 if (AccessSizeS == MemoryLocation::UnknownSize ||
2282 AccessSizeD == MemoryLocation::UnknownSize)
2283 return true;
2284
2285 if (DeltaS != DeltaD || DeltaS < AccessSizeS || DeltaD < AccessSizeD)
2286 return true;
2287
2288 return (OffsetS + (int64_t)AccessSizeS < OffsetD + (int64_t)AccessSizeD);
2289}
2290
2291void SwingSchedulerDAG::postprocessDAG() {
2292 for (auto &M : Mutations)
2293 M->apply(this);
2294}
2295
2296/// Try to schedule the node at the specified StartCycle and continue
2297/// until the node is schedule or the EndCycle is reached. This function
2298/// returns true if the node is scheduled. This routine may search either
2299/// forward or backward for a place to insert the instruction based upon
2300/// the relative values of StartCycle and EndCycle.
2301bool SMSchedule::insert(SUnit *SU, int StartCycle, int EndCycle, int II) {
2302 bool forward = true;
2303 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "Trying to insert node between "
<< StartCycle << " and " << EndCycle <<
" II: " << II << "\n"; }; } } while (false)
2304 dbgs() << "Trying to insert node between " << StartCycle << " and "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "Trying to insert node between "
<< StartCycle << " and " << EndCycle <<
" II: " << II << "\n"; }; } } while (false)
2305 << EndCycle << " II: " << II << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "Trying to insert node between "
<< StartCycle << " and " << EndCycle <<
" II: " << II << "\n"; }; } } while (false)
2306 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "Trying to insert node between "
<< StartCycle << " and " << EndCycle <<
" II: " << II << "\n"; }; } } while (false)
;
2307 if (StartCycle > EndCycle)
2308 forward = false;
2309
2310 // The terminating condition depends on the direction.
2311 int termCycle = forward ? EndCycle + 1 : EndCycle - 1;
2312 for (int curCycle = StartCycle; curCycle != termCycle;
2313 forward ? ++curCycle : --curCycle) {
2314
2315 // Add the already scheduled instructions at the specified cycle to the
2316 // DFA.
2317 ProcItinResources.clearResources();
2318 for (int checkCycle = FirstCycle + ((curCycle - FirstCycle) % II);
2319 checkCycle <= LastCycle; checkCycle += II) {
2320 std::deque<SUnit *> &cycleInstrs = ScheduledInstrs[checkCycle];
2321
2322 for (std::deque<SUnit *>::iterator I = cycleInstrs.begin(),
2323 E = cycleInstrs.end();
2324 I != E; ++I) {
2325 if (ST.getInstrInfo()->isZeroCost((*I)->getInstr()->getOpcode()))
2326 continue;
2327 assert(ProcItinResources.canReserveResources(*(*I)->getInstr()) &&((ProcItinResources.canReserveResources(*(*I)->getInstr())
&& "These instructions have already been scheduled."
) ? static_cast<void> (0) : __assert_fail ("ProcItinResources.canReserveResources(*(*I)->getInstr()) && \"These instructions have already been scheduled.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 2328, __PRETTY_FUNCTION__))
2328 "These instructions have already been scheduled.")((ProcItinResources.canReserveResources(*(*I)->getInstr())
&& "These instructions have already been scheduled."
) ? static_cast<void> (0) : __assert_fail ("ProcItinResources.canReserveResources(*(*I)->getInstr()) && \"These instructions have already been scheduled.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 2328, __PRETTY_FUNCTION__))
;
2329 ProcItinResources.reserveResources(*(*I)->getInstr());
2330 }
2331 }
2332 if (ST.getInstrInfo()->isZeroCost(SU->getInstr()->getOpcode()) ||
2333 ProcItinResources.canReserveResources(*SU->getInstr())) {
2334 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "\tinsert at cycle " <<
curCycle << " "; SU->getInstr()->dump(); }; } } while
(false)
2335 dbgs() << "\tinsert at cycle " << curCycle << " ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "\tinsert at cycle " <<
curCycle << " "; SU->getInstr()->dump(); }; } } while
(false)
2336 SU->getInstr()->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "\tinsert at cycle " <<
curCycle << " "; SU->getInstr()->dump(); }; } } while
(false)
2337 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "\tinsert at cycle " <<
curCycle << " "; SU->getInstr()->dump(); }; } } while
(false)
;
2338
2339 ScheduledInstrs[curCycle].push_back(SU);
2340 InstrToCycle.insert(std::make_pair(SU, curCycle));
2341 if (curCycle > LastCycle)
2342 LastCycle = curCycle;
2343 if (curCycle < FirstCycle)
2344 FirstCycle = curCycle;
2345 return true;
2346 }
2347 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "\tfailed to insert at cycle "
<< curCycle << " "; SU->getInstr()->dump()
; }; } } while (false)
2348 dbgs() << "\tfailed to insert at cycle " << curCycle << " ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "\tfailed to insert at cycle "
<< curCycle << " "; SU->getInstr()->dump()
; }; } } while (false)
2349 SU->getInstr()->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "\tfailed to insert at cycle "
<< curCycle << " "; SU->getInstr()->dump()
; }; } } while (false)
2350 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "\tfailed to insert at cycle "
<< curCycle << " "; SU->getInstr()->dump()
; }; } } while (false)
;
2351 }
2352 return false;
2353}
2354
2355// Return the cycle of the earliest scheduled instruction in the chain.
2356int SMSchedule::earliestCycleInChain(const SDep &Dep) {
2357 SmallPtrSet<SUnit *, 8> Visited;
2358 SmallVector<SDep, 8> Worklist;
2359 Worklist.push_back(Dep);
2360 int EarlyCycle = INT_MAX2147483647;
2361 while (!Worklist.empty()) {
2362 const SDep &Cur = Worklist.pop_back_val();
2363 SUnit *PrevSU = Cur.getSUnit();
2364 if (Visited.count(PrevSU))
2365 continue;
2366 std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(PrevSU);
2367 if (it == InstrToCycle.end())
2368 continue;
2369 EarlyCycle = std::min(EarlyCycle, it->second);
2370 for (const auto &PI : PrevSU->Preds)
2371 if (PI.getKind() == SDep::Order || Dep.getKind() == SDep::Output)
2372 Worklist.push_back(PI);
2373 Visited.insert(PrevSU);
2374 }
2375 return EarlyCycle;
2376}
2377
2378// Return the cycle of the latest scheduled instruction in the chain.
2379int SMSchedule::latestCycleInChain(const SDep &Dep) {
2380 SmallPtrSet<SUnit *, 8> Visited;
2381 SmallVector<SDep, 8> Worklist;
2382 Worklist.push_back(Dep);
2383 int LateCycle = INT_MIN(-2147483647 -1);
2384 while (!Worklist.empty()) {
2385 const SDep &Cur = Worklist.pop_back_val();
2386 SUnit *SuccSU = Cur.getSUnit();
2387 if (Visited.count(SuccSU))
2388 continue;
2389 std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SuccSU);
2390 if (it == InstrToCycle.end())
2391 continue;
2392 LateCycle = std::max(LateCycle, it->second);
2393 for (const auto &SI : SuccSU->Succs)
2394 if (SI.getKind() == SDep::Order || Dep.getKind() == SDep::Output)
2395 Worklist.push_back(SI);
2396 Visited.insert(SuccSU);
2397 }
2398 return LateCycle;
2399}
2400
2401/// If an instruction has a use that spans multiple iterations, then
2402/// return true. These instructions are characterized by having a back-ege
2403/// to a Phi, which contains a reference to another Phi.
2404static SUnit *multipleIterations(SUnit *SU, SwingSchedulerDAG *DAG) {
2405 for (auto &P : SU->Preds)
2406 if (DAG->isBackedge(SU, P) && P.getSUnit()->getInstr()->isPHI())
2407 for (auto &S : P.getSUnit()->Succs)
2408 if (S.getKind() == SDep::Data && S.getSUnit()->getInstr()->isPHI())
2409 return P.getSUnit();
2410 return nullptr;
2411}
2412
2413/// Compute the scheduling start slot for the instruction. The start slot
2414/// depends on any predecessor or successor nodes scheduled already.
2415void SMSchedule::computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart,
2416 int *MinEnd, int *MaxStart, int II,
2417 SwingSchedulerDAG *DAG) {
2418 // Iterate over each instruction that has been scheduled already. The start
2419 // slot computation depends on whether the previously scheduled instruction
2420 // is a predecessor or successor of the specified instruction.
2421 for (int cycle = getFirstCycle(); cycle <= LastCycle; ++cycle) {
2422
2423 // Iterate over each instruction in the current cycle.
2424 for (SUnit *I : getInstructions(cycle)) {
2425 // Because we're processing a DAG for the dependences, we recognize
2426 // the back-edge in recurrences by anti dependences.
2427 for (unsigned i = 0, e = (unsigned)SU->Preds.size(); i != e; ++i) {
2428 const SDep &Dep = SU->Preds[i];
2429 if (Dep.getSUnit() == I) {
2430 if (!DAG->isBackedge(SU, Dep)) {
2431 int EarlyStart = cycle + Dep.getLatency() -
2432 DAG->getDistance(Dep.getSUnit(), SU, Dep) * II;
2433 *MaxEarlyStart = std::max(*MaxEarlyStart, EarlyStart);
2434 if (DAG->isLoopCarriedDep(SU, Dep, false)) {
2435 int End = earliestCycleInChain(Dep) + (II - 1);
2436 *MinEnd = std::min(*MinEnd, End);
2437 }
2438 } else {
2439 int LateStart = cycle - Dep.getLatency() +
2440 DAG->getDistance(SU, Dep.getSUnit(), Dep) * II;
2441 *MinLateStart = std::min(*MinLateStart, LateStart);
2442 }
2443 }
2444 // For instruction that requires multiple iterations, make sure that
2445 // the dependent instruction is not scheduled past the definition.
2446 SUnit *BE = multipleIterations(I, DAG);
2447 if (BE && Dep.getSUnit() == BE && !SU->getInstr()->isPHI() &&
2448 !SU->isPred(I))
2449 *MinLateStart = std::min(*MinLateStart, cycle);
2450 }
2451 for (unsigned i = 0, e = (unsigned)SU->Succs.size(); i != e; ++i) {
2452 if (SU->Succs[i].getSUnit() == I) {
2453 const SDep &Dep = SU->Succs[i];
2454 if (!DAG->isBackedge(SU, Dep)) {
2455 int LateStart = cycle - Dep.getLatency() +
2456 DAG->getDistance(SU, Dep.getSUnit(), Dep) * II;
2457 *MinLateStart = std::min(*MinLateStart, LateStart);
2458 if (DAG->isLoopCarriedDep(SU, Dep)) {
2459 int Start = latestCycleInChain(Dep) + 1 - II;
2460 *MaxStart = std::max(*MaxStart, Start);
2461 }
2462 } else {
2463 int EarlyStart = cycle + Dep.getLatency() -
2464 DAG->getDistance(Dep.getSUnit(), SU, Dep) * II;
2465 *MaxEarlyStart = std::max(*MaxEarlyStart, EarlyStart);
2466 }
2467 }
2468 }
2469 }
2470 }
2471}
2472
2473/// Order the instructions within a cycle so that the definitions occur
2474/// before the uses. Returns true if the instruction is added to the start
2475/// of the list, or false if added to the end.
2476void SMSchedule::orderDependence(SwingSchedulerDAG *SSD, SUnit *SU,
2477 std::deque<SUnit *> &Insts) {
2478 MachineInstr *MI = SU->getInstr();
2479 bool OrderBeforeUse = false;
2480 bool OrderAfterDef = false;
2481 bool OrderBeforeDef = false;
2482 unsigned MoveDef = 0;
2483 unsigned MoveUse = 0;
2484 int StageInst1 = stageScheduled(SU);
2485
2486 unsigned Pos = 0;
2487 for (std::deque<SUnit *>::iterator I = Insts.begin(), E = Insts.end(); I != E;
2488 ++I, ++Pos) {
2489 for (unsigned i = 0, e = MI->getNumOperands(); i < e; ++i) {
2490 MachineOperand &MO = MI->getOperand(i);
2491 if (!MO.isReg() || !Register::isVirtualRegister(MO.getReg()))
2492 continue;
2493
2494 Register Reg = MO.getReg();
2495 unsigned BasePos, OffsetPos;
2496 if (ST.getInstrInfo()->getBaseAndOffsetPosition(*MI, BasePos, OffsetPos))
2497 if (MI->getOperand(BasePos).getReg() == Reg)
2498 if (unsigned NewReg = SSD->getInstrBaseReg(SU))
2499 Reg = NewReg;
2500 bool Reads, Writes;
2501 std::tie(Reads, Writes) =
2502 (*I)->getInstr()->readsWritesVirtualRegister(Reg);
2503 if (MO.isDef() && Reads && stageScheduled(*I) <= StageInst1) {
2504 OrderBeforeUse = true;
2505 if (MoveUse == 0)
2506 MoveUse = Pos;
2507 } else if (MO.isDef() && Reads && stageScheduled(*I) > StageInst1) {
2508 // Add the instruction after the scheduled instruction.
2509 OrderAfterDef = true;
2510 MoveDef = Pos;
2511 } else if (MO.isUse() && Writes && stageScheduled(*I) == StageInst1) {
2512 if (cycleScheduled(*I) == cycleScheduled(SU) && !(*I)->isSucc(SU)) {
2513 OrderBeforeUse = true;
2514 if (MoveUse == 0)
2515 MoveUse = Pos;
2516 } else {
2517 OrderAfterDef = true;
2518 MoveDef = Pos;
2519 }
2520 } else if (MO.isUse() && Writes && stageScheduled(*I) > StageInst1) {
2521 OrderBeforeUse = true;
2522 if (MoveUse == 0)
2523 MoveUse = Pos;
2524 if (MoveUse != 0) {
2525 OrderAfterDef = true;
2526 MoveDef = Pos - 1;
2527 }
2528 } else if (MO.isUse() && Writes && stageScheduled(*I) < StageInst1) {
2529 // Add the instruction before the scheduled instruction.
2530 OrderBeforeUse = true;
2531 if (MoveUse == 0)
2532 MoveUse = Pos;
2533 } else if (MO.isUse() && stageScheduled(*I) == StageInst1 &&
2534 isLoopCarriedDefOfUse(SSD, (*I)->getInstr(), MO)) {
2535 if (MoveUse == 0) {
2536 OrderBeforeDef = true;
2537 MoveUse = Pos;
2538 }
2539 }
2540 }
2541 // Check for order dependences between instructions. Make sure the source
2542 // is ordered before the destination.
2543 for (auto &S : SU->Succs) {
2544 if (S.getSUnit() != *I)
2545 continue;
2546 if (S.getKind() == SDep::Order && stageScheduled(*I) == StageInst1) {
2547 OrderBeforeUse = true;
2548 if (Pos < MoveUse)
2549 MoveUse = Pos;
2550 }
2551 // We did not handle HW dependences in previous for loop,
2552 // and we normally set Latency = 0 for Anti deps,
2553 // so may have nodes in same cycle with Anti denpendent on HW regs.
2554 else if (S.getKind() == SDep::Anti && stageScheduled(*I) == StageInst1) {
2555 OrderBeforeUse = true;
2556 if ((MoveUse == 0) || (Pos < MoveUse))
2557 MoveUse = Pos;
2558 }
2559 }
2560 for (auto &P : SU->Preds) {
2561 if (P.getSUnit() != *I)
2562 continue;
2563 if (P.getKind() == SDep::Order && stageScheduled(*I) == StageInst1) {
2564 OrderAfterDef = true;
2565 MoveDef = Pos;
2566 }
2567 }
2568 }
2569
2570 // A circular dependence.
2571 if (OrderAfterDef && OrderBeforeUse && MoveUse == MoveDef)
2572 OrderBeforeUse = false;
2573
2574 // OrderAfterDef takes precedences over OrderBeforeDef. The latter is due
2575 // to a loop-carried dependence.
2576 if (OrderBeforeDef)
2577 OrderBeforeUse = !OrderAfterDef || (MoveUse > MoveDef);
2578
2579 // The uncommon case when the instruction order needs to be updated because
2580 // there is both a use and def.
2581 if (OrderBeforeUse && OrderAfterDef) {
2582 SUnit *UseSU = Insts.at(MoveUse);
2583 SUnit *DefSU = Insts.at(MoveDef);
2584 if (MoveUse > MoveDef) {
2585 Insts.erase(Insts.begin() + MoveUse);
2586 Insts.erase(Insts.begin() + MoveDef);
2587 } else {
2588 Insts.erase(Insts.begin() + MoveDef);
2589 Insts.erase(Insts.begin() + MoveUse);
2590 }
2591 orderDependence(SSD, UseSU, Insts);
2592 orderDependence(SSD, SU, Insts);
2593 orderDependence(SSD, DefSU, Insts);
2594 return;
2595 }
2596 // Put the new instruction first if there is a use in the list. Otherwise,
2597 // put it at the end of the list.
2598 if (OrderBeforeUse)
2599 Insts.push_front(SU);
2600 else
2601 Insts.push_back(SU);
2602}
2603
2604/// Return true if the scheduled Phi has a loop carried operand.
2605bool SMSchedule::isLoopCarried(SwingSchedulerDAG *SSD, MachineInstr &Phi) {
2606 if (!Phi.isPHI())
2607 return false;
2608 assert(Phi.isPHI() && "Expecting a Phi.")((Phi.isPHI() && "Expecting a Phi.") ? static_cast<
void> (0) : __assert_fail ("Phi.isPHI() && \"Expecting a Phi.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 2608, __PRETTY_FUNCTION__))
;
2609 SUnit *DefSU = SSD->getSUnit(&Phi);
2610 unsigned DefCycle = cycleScheduled(DefSU);
2611 int DefStage = stageScheduled(DefSU);
2612
2613 unsigned InitVal = 0;
2614 unsigned LoopVal = 0;
2615 getPhiRegs(Phi, Phi.getParent(), InitVal, LoopVal);
2616 SUnit *UseSU = SSD->getSUnit(MRI.getVRegDef(LoopVal));
2617 if (!UseSU)
2618 return true;
2619 if (UseSU->getInstr()->isPHI())
2620 return true;
2621 unsigned LoopCycle = cycleScheduled(UseSU);
2622 int LoopStage = stageScheduled(UseSU);
2623 return (LoopCycle > DefCycle) || (LoopStage <= DefStage);
2624}
2625
2626/// Return true if the instruction is a definition that is loop carried
2627/// and defines the use on the next iteration.
2628/// v1 = phi(v2, v3)
2629/// (Def) v3 = op v1
2630/// (MO) = v1
2631/// If MO appears before Def, then then v1 and v3 may get assigned to the same
2632/// register.
2633bool SMSchedule::isLoopCarriedDefOfUse(SwingSchedulerDAG *SSD,
2634 MachineInstr *Def, MachineOperand &MO) {
2635 if (!MO.isReg())
2636 return false;
2637 if (Def->isPHI())
2638 return false;
2639 MachineInstr *Phi = MRI.getVRegDef(MO.getReg());
2640 if (!Phi || !Phi->isPHI() || Phi->getParent() != Def->getParent())
2641 return false;
2642 if (!isLoopCarried(SSD, *Phi))
2643 return false;
2644 unsigned LoopReg = getLoopPhiReg(*Phi, Phi->getParent());
2645 for (unsigned i = 0, e = Def->getNumOperands(); i != e; ++i) {
2646 MachineOperand &DMO = Def->getOperand(i);
2647 if (!DMO.isReg() || !DMO.isDef())
2648 continue;
2649 if (DMO.getReg() == LoopReg)
2650 return true;
2651 }
2652 return false;
2653}
2654
2655// Check if the generated schedule is valid. This function checks if
2656// an instruction that uses a physical register is scheduled in a
2657// different stage than the definition. The pipeliner does not handle
2658// physical register values that may cross a basic block boundary.
2659bool SMSchedule::isValidSchedule(SwingSchedulerDAG *SSD) {
2660 for (int i = 0, e = SSD->SUnits.size(); i < e; ++i) {
2661 SUnit &SU = SSD->SUnits[i];
2662 if (!SU.hasPhysRegDefs)
2663 continue;
2664 int StageDef = stageScheduled(&SU);
2665 assert(StageDef != -1 && "Instruction should have been scheduled.")((StageDef != -1 && "Instruction should have been scheduled."
) ? static_cast<void> (0) : __assert_fail ("StageDef != -1 && \"Instruction should have been scheduled.\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 2665, __PRETTY_FUNCTION__))
;
2666 for (auto &SI : SU.Succs)
2667 if (SI.isAssignedRegDep())
2668 if (Register::isPhysicalRegister(SI.getReg()))
2669 if (stageScheduled(SI.getSUnit()) != StageDef)
2670 return false;
2671 }
2672 return true;
2673}
2674
2675/// A property of the node order in swing-modulo-scheduling is
2676/// that for nodes outside circuits the following holds:
2677/// none of them is scheduled after both a successor and a
2678/// predecessor.
2679/// The method below checks whether the property is met.
2680/// If not, debug information is printed and statistics information updated.
2681/// Note that we do not use an assert statement.
2682/// The reason is that although an invalid node oder may prevent
2683/// the pipeliner from finding a pipelined schedule for arbitrary II,
2684/// it does not lead to the generation of incorrect code.
2685void SwingSchedulerDAG::checkValidNodeOrder(const NodeSetType &Circuits) const {
2686
2687 // a sorted vector that maps each SUnit to its index in the NodeOrder
2688 typedef std::pair<SUnit *, unsigned> UnitIndex;
2689 std::vector<UnitIndex> Indices(NodeOrder.size(), std::make_pair(nullptr, 0));
2690
2691 for (unsigned i = 0, s = NodeOrder.size(); i < s; ++i)
2692 Indices.push_back(std::make_pair(NodeOrder[i], i));
2693
2694 auto CompareKey = [](UnitIndex i1, UnitIndex i2) {
2695 return std::get<0>(i1) < std::get<0>(i2);
2696 };
2697
2698 // sort, so that we can perform a binary search
2699 llvm::sort(Indices, CompareKey);
2700
2701 bool Valid = true;
2702 (void)Valid;
2703 // for each SUnit in the NodeOrder, check whether
2704 // it appears after both a successor and a predecessor
2705 // of the SUnit. If this is the case, and the SUnit
2706 // is not part of circuit, then the NodeOrder is not
2707 // valid.
2708 for (unsigned i = 0, s = NodeOrder.size(); i < s; ++i) {
2709 SUnit *SU = NodeOrder[i];
2710 unsigned Index = i;
2711
2712 bool PredBefore = false;
2713 bool SuccBefore = false;
2714
2715 SUnit *Succ;
2716 SUnit *Pred;
2717 (void)Succ;
2718 (void)Pred;
2719
2720 for (SDep &PredEdge : SU->Preds) {
2721 SUnit *PredSU = PredEdge.getSUnit();
2722 unsigned PredIndex = std::get<1>(
2723 *llvm::lower_bound(Indices, std::make_pair(PredSU, 0), CompareKey));
2724 if (!PredSU->getInstr()->isPHI() && PredIndex < Index) {
2725 PredBefore = true;
2726 Pred = PredSU;
2727 break;
2728 }
2729 }
2730
2731 for (SDep &SuccEdge : SU->Succs) {
2732 SUnit *SuccSU = SuccEdge.getSUnit();
2733 // Do not process a boundary node, it was not included in NodeOrder,
2734 // hence not in Indices either, call to std::lower_bound() below will
2735 // return Indices.end().
2736 if (SuccSU->isBoundaryNode())
2737 continue;
2738 unsigned SuccIndex = std::get<1>(
2739 *llvm::lower_bound(Indices, std::make_pair(SuccSU, 0), CompareKey));
2740 if (!SuccSU->getInstr()->isPHI() && SuccIndex < Index) {
2741 SuccBefore = true;
2742 Succ = SuccSU;
2743 break;
2744 }
2745 }
2746
2747 if (PredBefore && SuccBefore && !SU->getInstr()->isPHI()) {
2748 // instructions in circuits are allowed to be scheduled
2749 // after both a successor and predecessor.
2750 bool InCircuit = llvm::any_of(
2751 Circuits, [SU](const NodeSet &Circuit) { return Circuit.count(SU); });
2752 if (InCircuit)
2753 LLVM_DEBUG(dbgs() << "In a circuit, predecessor ";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "In a circuit, predecessor "
;; } } while (false)
;
2754 else {
2755 Valid = false;
2756 NumNodeOrderIssues++;
2757 LLVM_DEBUG(dbgs() << "Predecessor ";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << "Predecessor ";; } } while (
false)
;
2758 }
2759 LLVM_DEBUG(dbgs() << Pred->NodeNum << " and successor " << Succ->NodeNumdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << Pred->NodeNum << " and successor "
<< Succ->NodeNum << " are scheduled before node "
<< SU->NodeNum << "\n";; } } while (false)
2760 << " are scheduled before node " << SU->NodeNumdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << Pred->NodeNum << " and successor "
<< Succ->NodeNum << " are scheduled before node "
<< SU->NodeNum << "\n";; } } while (false)
2761 << "\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dbgs() << Pred->NodeNum << " and successor "
<< Succ->NodeNum << " are scheduled before node "
<< SU->NodeNum << "\n";; } } while (false)
;
2762 }
2763 }
2764
2765 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (!Valid) dbgs() << "Invalid node order found!\n"
; }; } } while (false)
2766 if (!Valid)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (!Valid) dbgs() << "Invalid node order found!\n"
; }; } } while (false)
2767 dbgs() << "Invalid node order found!\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (!Valid) dbgs() << "Invalid node order found!\n"
; }; } } while (false)
2768 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (!Valid) dbgs() << "Invalid node order found!\n"
; }; } } while (false)
;
2769}
2770
2771/// Attempt to fix the degenerate cases when the instruction serialization
2772/// causes the register lifetimes to overlap. For example,
2773/// p' = store_pi(p, b)
2774/// = load p, offset
2775/// In this case p and p' overlap, which means that two registers are needed.
2776/// Instead, this function changes the load to use p' and updates the offset.
2777void SwingSchedulerDAG::fixupRegisterOverlaps(std::deque<SUnit *> &Instrs) {
2778 unsigned OverlapReg = 0;
2779 unsigned NewBaseReg = 0;
2780 for (SUnit *SU : Instrs) {
2781 MachineInstr *MI = SU->getInstr();
2782 for (unsigned i = 0, e = MI->getNumOperands(); i < e; ++i) {
2783 const MachineOperand &MO = MI->getOperand(i);
2784 // Look for an instruction that uses p. The instruction occurs in the
2785 // same cycle but occurs later in the serialized order.
2786 if (MO.isReg() && MO.isUse() && MO.getReg() == OverlapReg) {
2787 // Check that the instruction appears in the InstrChanges structure,
2788 // which contains instructions that can have the offset updated.
2789 DenseMap<SUnit *, std::pair<unsigned, int64_t>>::iterator It =
2790 InstrChanges.find(SU);
2791 if (It != InstrChanges.end()) {
2792 unsigned BasePos, OffsetPos;
2793 // Update the base register and adjust the offset.
2794 if (TII->getBaseAndOffsetPosition(*MI, BasePos, OffsetPos)) {
2795 MachineInstr *NewMI = MF.CloneMachineInstr(MI);
2796 NewMI->getOperand(BasePos).setReg(NewBaseReg);
2797 int64_t NewOffset =
2798 MI->getOperand(OffsetPos).getImm() - It->second.second;
2799 NewMI->getOperand(OffsetPos).setImm(NewOffset);
2800 SU->setInstr(NewMI);
2801 MISUnitMap[NewMI] = SU;
2802 NewMIs[MI] = NewMI;
2803 }
2804 }
2805 OverlapReg = 0;
2806 NewBaseReg = 0;
2807 break;
2808 }
2809 // Look for an instruction of the form p' = op(p), which uses and defines
2810 // two virtual registers that get allocated to the same physical register.
2811 unsigned TiedUseIdx = 0;
2812 if (MI->isRegTiedToUseOperand(i, &TiedUseIdx)) {
2813 // OverlapReg is p in the example above.
2814 OverlapReg = MI->getOperand(TiedUseIdx).getReg();
2815 // NewBaseReg is p' in the example above.
2816 NewBaseReg = MI->getOperand(i).getReg();
2817 break;
2818 }
2819 }
2820 }
2821}
2822
2823/// After the schedule has been formed, call this function to combine
2824/// the instructions from the different stages/cycles. That is, this
2825/// function creates a schedule that represents a single iteration.
2826void SMSchedule::finalizeSchedule(SwingSchedulerDAG *SSD) {
2827 // Move all instructions to the first stage from later stages.
2828 for (int cycle = getFirstCycle(); cycle <= getFinalCycle(); ++cycle) {
2829 for (int stage = 1, lastStage = getMaxStageCount(); stage <= lastStage;
2830 ++stage) {
2831 std::deque<SUnit *> &cycleInstrs =
2832 ScheduledInstrs[cycle + (stage * InitiationInterval)];
2833 for (std::deque<SUnit *>::reverse_iterator I = cycleInstrs.rbegin(),
2834 E = cycleInstrs.rend();
2835 I != E; ++I)
2836 ScheduledInstrs[cycle].push_front(*I);
2837 }
2838 }
2839
2840 // Erase all the elements in the later stages. Only one iteration should
2841 // remain in the scheduled list, and it contains all the instructions.
2842 for (int cycle = getFinalCycle() + 1; cycle <= LastCycle; ++cycle)
2843 ScheduledInstrs.erase(cycle);
2844
2845 // Change the registers in instruction as specified in the InstrChanges
2846 // map. We need to use the new registers to create the correct order.
2847 for (int i = 0, e = SSD->SUnits.size(); i != e; ++i) {
2848 SUnit *SU = &SSD->SUnits[i];
2849 SSD->applyInstrChange(SU->getInstr(), *this);
2850 }
2851
2852 // Reorder the instructions in each cycle to fix and improve the
2853 // generated code.
2854 for (int Cycle = getFirstCycle(), E = getFinalCycle(); Cycle <= E; ++Cycle) {
2855 std::deque<SUnit *> &cycleInstrs = ScheduledInstrs[Cycle];
2856 std::deque<SUnit *> newOrderPhi;
2857 for (unsigned i = 0, e = cycleInstrs.size(); i < e; ++i) {
2858 SUnit *SU = cycleInstrs[i];
2859 if (SU->getInstr()->isPHI())
2860 newOrderPhi.push_back(SU);
2861 }
2862 std::deque<SUnit *> newOrderI;
2863 for (unsigned i = 0, e = cycleInstrs.size(); i < e; ++i) {
2864 SUnit *SU = cycleInstrs[i];
2865 if (!SU->getInstr()->isPHI())
2866 orderDependence(SSD, SU, newOrderI);
2867 }
2868 // Replace the old order with the new order.
2869 cycleInstrs.swap(newOrderPhi);
2870 cycleInstrs.insert(cycleInstrs.end(), newOrderI.begin(), newOrderI.end());
2871 SSD->fixupRegisterOverlaps(cycleInstrs);
2872 }
2873
2874 LLVM_DEBUG(dump();)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { dump();; } } while (false)
;
2875}
2876
2877void NodeSet::print(raw_ostream &os) const {
2878 os << "Num nodes " << size() << " rec " << RecMII << " mov " << MaxMOV
2879 << " depth " << MaxDepth << " col " << Colocate << "\n";
2880 for (const auto &I : Nodes)
2881 os << " SU(" << I->NodeNum << ") " << *(I->getInstr());
2882 os << "\n";
2883}
2884
2885#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2886/// Print the schedule information to the given output.
2887void SMSchedule::print(raw_ostream &os) const {
2888 // Iterate over each cycle.
2889 for (int cycle = getFirstCycle(); cycle <= getFinalCycle(); ++cycle) {
2890 // Iterate over each instruction in the cycle.
2891 const_sched_iterator cycleInstrs = ScheduledInstrs.find(cycle);
2892 for (SUnit *CI : cycleInstrs->second) {
2893 os << "cycle " << cycle << " (" << stageScheduled(CI) << ") ";
2894 os << "(" << CI->NodeNum << ") ";
2895 CI->getInstr()->print(os);
2896 os << "\n";
2897 }
2898 }
2899}
2900
2901/// Utility function used for debugging to print the schedule.
2902LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void SMSchedule::dump() const { print(dbgs()); }
2903LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void NodeSet::dump() const { print(dbgs()); }
2904
2905#endif
2906
2907void ResourceManager::initProcResourceVectors(
2908 const MCSchedModel &SM, SmallVectorImpl<uint64_t> &Masks) {
2909 unsigned ProcResourceID = 0;
2910
2911 // We currently limit the resource kinds to 64 and below so that we can use
2912 // uint64_t for Masks
2913 assert(SM.getNumProcResourceKinds() < 64 &&((SM.getNumProcResourceKinds() < 64 && "Too many kinds of resources, unsupported"
) ? static_cast<void> (0) : __assert_fail ("SM.getNumProcResourceKinds() < 64 && \"Too many kinds of resources, unsupported\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 2914, __PRETTY_FUNCTION__))
2914 "Too many kinds of resources, unsupported")((SM.getNumProcResourceKinds() < 64 && "Too many kinds of resources, unsupported"
) ? static_cast<void> (0) : __assert_fail ("SM.getNumProcResourceKinds() < 64 && \"Too many kinds of resources, unsupported\""
, "/build/llvm-toolchain-snapshot-11~++20200309111110+2c36c23f347/llvm/lib/CodeGen/MachinePipeliner.cpp"
, 2914, __PRETTY_FUNCTION__))
;
2915 // Create a unique bitmask for every processor resource unit.
2916 // Skip resource at index 0, since it always references 'InvalidUnit'.
2917 Masks.resize(SM.getNumProcResourceKinds());
2918 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
2919 const MCProcResourceDesc &Desc = *SM.getProcResource(I);
2920 if (Desc.SubUnitsIdxBegin)
2921 continue;
2922 Masks[I] = 1ULL << ProcResourceID;
2923 ProcResourceID++;
2924 }
2925 // Create a unique bitmask for every processor resource group.
2926 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
2927 const MCProcResourceDesc &Desc = *SM.getProcResource(I);
2928 if (!Desc.SubUnitsIdxBegin)
2929 continue;
2930 Masks[I] = 1ULL << ProcResourceID;
2931 for (unsigned U = 0; U < Desc.NumUnits; ++U)
2932 Masks[I] |= Masks[Desc.SubUnitsIdxBegin[U]];
2933 ProcResourceID++;
2934 }
2935 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpShowResMask) { dbgs() << "ProcResourceDesc:\n"
; for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I <
E; ++I) { const MCProcResourceDesc *ProcResource = SM.getProcResource
(I); dbgs() << format(" %16s(%2d): Mask: 0x%08x, NumUnits:%2d\n"
, ProcResource->Name, I, Masks[I], ProcResource->NumUnits
); } dbgs() << " -----------------\n"; } }; } } while (
false)
2936 if (SwpShowResMask) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpShowResMask) { dbgs() << "ProcResourceDesc:\n"
; for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I <
E; ++I) { const MCProcResourceDesc *ProcResource = SM.getProcResource
(I); dbgs() << format(" %16s(%2d): Mask: 0x%08x, NumUnits:%2d\n"
, ProcResource->Name, I, Masks[I], ProcResource->NumUnits
); } dbgs() << " -----------------\n"; } }; } } while (
false)
2937 dbgs() << "ProcResourceDesc:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpShowResMask) { dbgs() << "ProcResourceDesc:\n"
; for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I <
E; ++I) { const MCProcResourceDesc *ProcResource = SM.getProcResource
(I); dbgs() << format(" %16s(%2d): Mask: 0x%08x, NumUnits:%2d\n"
, ProcResource->Name, I, Masks[I], ProcResource->NumUnits
); } dbgs() << " -----------------\n"; } }; } } while (
false)
2938 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpShowResMask) { dbgs() << "ProcResourceDesc:\n"
; for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I <
E; ++I) { const MCProcResourceDesc *ProcResource = SM.getProcResource
(I); dbgs() << format(" %16s(%2d): Mask: 0x%08x, NumUnits:%2d\n"
, ProcResource->Name, I, Masks[I], ProcResource->NumUnits
); } dbgs() << " -----------------\n"; } }; } } while (
false)
2939 const MCProcResourceDesc *ProcResource = SM.getProcResource(I);do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpShowResMask) { dbgs() << "ProcResourceDesc:\n"
; for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I <
E; ++I) { const MCProcResourceDesc *ProcResource = SM.getProcResource
(I); dbgs() << format(" %16s(%2d): Mask: 0x%08x, NumUnits:%2d\n"
, ProcResource->Name, I, Masks[I], ProcResource->NumUnits
); } dbgs() << " -----------------\n"; } }; } } while (
false)
2940 dbgs() << format(" %16s(%2d): Mask: 0x%08x, NumUnits:%2d\n",do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpShowResMask) { dbgs() << "ProcResourceDesc:\n"
; for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I <
E; ++I) { const MCProcResourceDesc *ProcResource = SM.getProcResource
(I); dbgs() << format(" %16s(%2d): Mask: 0x%08x, NumUnits:%2d\n"
, ProcResource->Name, I, Masks[I], ProcResource->NumUnits
); } dbgs() << " -----------------\n"; } }; } } while (
false)
2941 ProcResource->Name, I, Masks[I],do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpShowResMask) { dbgs() << "ProcResourceDesc:\n"
; for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I <
E; ++I) { const MCProcResourceDesc *ProcResource = SM.getProcResource
(I); dbgs() << format(" %16s(%2d): Mask: 0x%08x, NumUnits:%2d\n"
, ProcResource->Name, I, Masks[I], ProcResource->NumUnits
); } dbgs() << " -----------------\n"; } }; } } while (
false)
2942 ProcResource->NumUnits);do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpShowResMask) { dbgs() << "ProcResourceDesc:\n"
; for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I <
E; ++I) { const MCProcResourceDesc *ProcResource = SM.getProcResource
(I); dbgs() << format(" %16s(%2d): Mask: 0x%08x, NumUnits:%2d\n"
, ProcResource->Name, I, Masks[I], ProcResource->NumUnits
); } dbgs() << " -----------------\n"; } }; } } while (
false)
2943 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpShowResMask) { dbgs() << "ProcResourceDesc:\n"
; for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I <
E; ++I) { const MCProcResourceDesc *ProcResource = SM.getProcResource
(I); dbgs() << format(" %16s(%2d): Mask: 0x%08x, NumUnits:%2d\n"
, ProcResource->Name, I, Masks[I], ProcResource->NumUnits
); } dbgs() << " -----------------\n"; } }; } } while (
false)
2944 dbgs() << " -----------------\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpShowResMask) { dbgs() << "ProcResourceDesc:\n"
; for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I <
E; ++I) { const MCProcResourceDesc *ProcResource = SM.getProcResource
(I); dbgs() << format(" %16s(%2d): Mask: 0x%08x, NumUnits:%2d\n"
, ProcResource->Name, I, Masks[I], ProcResource->NumUnits
); } dbgs() << " -----------------\n"; } }; } } while (
false)
2945 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpShowResMask) { dbgs() << "ProcResourceDesc:\n"
; for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I <
E; ++I) { const MCProcResourceDesc *ProcResource = SM.getProcResource
(I); dbgs() << format(" %16s(%2d): Mask: 0x%08x, NumUnits:%2d\n"
, ProcResource->Name, I, Masks[I], ProcResource->NumUnits
); } dbgs() << " -----------------\n"; } }; } } while (
false)
2946 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpShowResMask) { dbgs() << "ProcResourceDesc:\n"
; for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I <
E; ++I) { const MCProcResourceDesc *ProcResource = SM.getProcResource
(I); dbgs() << format(" %16s(%2d): Mask: 0x%08x, NumUnits:%2d\n"
, ProcResource->Name, I, Masks[I], ProcResource->NumUnits
); } dbgs() << " -----------------\n"; } }; } } while (
false)
;
2947}
2948
2949bool ResourceManager::canReserveResources(const MCInstrDesc *MID) const {
2950
2951 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) dbgs() << "canReserveResources:\n"
; }; } } while (false)
2952 if (SwpDebugResource)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) dbgs() << "canReserveResources:\n"
; }; } } while (false)
2953 dbgs() << "canReserveResources:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) dbgs() << "canReserveResources:\n"
; }; } } while (false)
2954 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) dbgs() << "canReserveResources:\n"
; }; } } while (false)
;
2955 if (UseDFA)
2956 return DFAResources->canReserveResources(MID);
2957
2958 unsigned InsnClass = MID->getSchedClass();
2959 const MCSchedClassDesc *SCDesc = SM.getSchedClassDesc(InsnClass);
2960 if (!SCDesc->isValid()) {
2961 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "No valid Schedule Class Desc for schedClass!\n"
; dbgs() << "isPseduo:" << MID->isPseudo() <<
"\n"; }; } } while (false)
2962 dbgs() << "No valid Schedule Class Desc for schedClass!\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "No valid Schedule Class Desc for schedClass!\n"
; dbgs() << "isPseduo:" << MID->isPseudo() <<
"\n"; }; } } while (false)
2963 dbgs() << "isPseduo:" << MID->isPseudo() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "No valid Schedule Class Desc for schedClass!\n"
; dbgs() << "isPseduo:" << MID->isPseudo() <<
"\n"; }; } } while (false)
2964 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "No valid Schedule Class Desc for schedClass!\n"
; dbgs() << "isPseduo:" << MID->isPseudo() <<
"\n"; }; } } while (false)
;
2965 return true;
2966 }
2967
2968 const MCWriteProcResEntry *I = STI->getWriteProcResBegin(SCDesc);
2969 const MCWriteProcResEntry *E = STI->getWriteProcResEnd(SCDesc);
2970 for (; I != E; ++I) {
2971 if (!I->Cycles)
2972 continue;
2973 const MCProcResourceDesc *ProcResource =
2974 SM.getProcResource(I->ProcResourceIdx);
2975 unsigned NumUnits = ProcResource->NumUnits;
2976 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) dbgs() << format
(" %16s(%2d): Count: %2d, NumUnits:%2d, Cycles:%2d\n", ProcResource
->Name, I->ProcResourceIdx, ProcResourceCount[I->ProcResourceIdx
], NumUnits, I->Cycles); }; } } while (false)
2977 if (SwpDebugResource)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) dbgs() << format
(" %16s(%2d): Count: %2d, NumUnits:%2d, Cycles:%2d\n", ProcResource
->Name, I->ProcResourceIdx, ProcResourceCount[I->ProcResourceIdx
], NumUnits, I->Cycles); }; } } while (false)
2978 dbgs() << format(" %16s(%2d): Count: %2d, NumUnits:%2d, Cycles:%2d\n",do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) dbgs() << format
(" %16s(%2d): Count: %2d, NumUnits:%2d, Cycles:%2d\n", ProcResource
->Name, I->ProcResourceIdx, ProcResourceCount[I->ProcResourceIdx
], NumUnits, I->Cycles); }; } } while (false)
2979 ProcResource->Name, I->ProcResourceIdx,do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) dbgs() << format
(" %16s(%2d): Count: %2d, NumUnits:%2d, Cycles:%2d\n", ProcResource
->Name, I->ProcResourceIdx, ProcResourceCount[I->ProcResourceIdx
], NumUnits, I->Cycles); }; } } while (false)
2980 ProcResourceCount[I->ProcResourceIdx], NumUnits,do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) dbgs() << format
(" %16s(%2d): Count: %2d, NumUnits:%2d, Cycles:%2d\n", ProcResource
->Name, I->ProcResourceIdx, ProcResourceCount[I->ProcResourceIdx
], NumUnits, I->Cycles); }; } } while (false)
2981 I->Cycles);do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) dbgs() << format
(" %16s(%2d): Count: %2d, NumUnits:%2d, Cycles:%2d\n", ProcResource
->Name, I->ProcResourceIdx, ProcResourceCount[I->ProcResourceIdx
], NumUnits, I->Cycles); }; } } while (false)
2982 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) dbgs() << format
(" %16s(%2d): Count: %2d, NumUnits:%2d, Cycles:%2d\n", ProcResource
->Name, I->ProcResourceIdx, ProcResourceCount[I->ProcResourceIdx
], NumUnits, I->Cycles); }; } } while (false)
;
2983 if (ProcResourceCount[I->ProcResourceIdx] >= NumUnits)
2984 return false;
2985 }
2986 LLVM_DEBUG(if (SwpDebugResource) dbgs() << "return true\n\n";)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { if (SwpDebugResource) dbgs() << "return true\n\n"
;; } } while (false)
;
2987 return true;
2988}
2989
2990void ResourceManager::reserveResources(const MCInstrDesc *MID) {
2991 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) dbgs() << "reserveResources:\n"
; }; } } while (false)
2992 if (SwpDebugResource)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) dbgs() << "reserveResources:\n"
; }; } } while (false)
2993 dbgs() << "reserveResources:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) dbgs() << "reserveResources:\n"
; }; } } while (false)
2994 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) dbgs() << "reserveResources:\n"
; }; } } while (false)
;
2995 if (UseDFA)
2996 return DFAResources->reserveResources(MID);
2997
2998 unsigned InsnClass = MID->getSchedClass();
2999 const MCSchedClassDesc *SCDesc = SM.getSchedClassDesc(InsnClass);
3000 if (!SCDesc->isValid()) {
3001 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "No valid Schedule Class Desc for schedClass!\n"
; dbgs() << "isPseduo:" << MID->isPseudo() <<
"\n"; }; } } while (false)
3002 dbgs() << "No valid Schedule Class Desc for schedClass!\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "No valid Schedule Class Desc for schedClass!\n"
; dbgs() << "isPseduo:" << MID->isPseudo() <<
"\n"; }; } } while (false)
3003 dbgs() << "isPseduo:" << MID->isPseudo() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "No valid Schedule Class Desc for schedClass!\n"
; dbgs() << "isPseduo:" << MID->isPseudo() <<
"\n"; }; } } while (false)
3004 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { dbgs() << "No valid Schedule Class Desc for schedClass!\n"
; dbgs() << "isPseduo:" << MID->isPseudo() <<
"\n"; }; } } while (false)
;
3005 return;
3006 }
3007 for (const MCWriteProcResEntry &PRE :
3008 make_range(STI->getWriteProcResBegin(SCDesc),
3009 STI->getWriteProcResEnd(SCDesc))) {
3010 if (!PRE.Cycles)
3011 continue;
3012 ++ProcResourceCount[PRE.ProcResourceIdx];
3013 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) { const MCProcResourceDesc
*ProcResource = SM.getProcResource(PRE.ProcResourceIdx); dbgs
() << format(" %16s(%2d): Count: %2d, NumUnits:%2d, Cycles:%2d\n"
, ProcResource->Name, PRE.ProcResourceIdx, ProcResourceCount
[PRE.ProcResourceIdx], ProcResource->NumUnits, PRE.Cycles)
; } }; } } while (false)
3014 if (SwpDebugResource) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) { const MCProcResourceDesc
*ProcResource = SM.getProcResource(PRE.ProcResourceIdx); dbgs
() << format(" %16s(%2d): Count: %2d, NumUnits:%2d, Cycles:%2d\n"
, ProcResource->Name, PRE.ProcResourceIdx, ProcResourceCount
[PRE.ProcResourceIdx], ProcResource->NumUnits, PRE.Cycles)
; } }; } } while (false)
3015 const MCProcResourceDesc *ProcResource =do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) { const MCProcResourceDesc
*ProcResource = SM.getProcResource(PRE.ProcResourceIdx); dbgs
() << format(" %16s(%2d): Count: %2d, NumUnits:%2d, Cycles:%2d\n"
, ProcResource->Name, PRE.ProcResourceIdx, ProcResourceCount
[PRE.ProcResourceIdx], ProcResource->NumUnits, PRE.Cycles)
; } }; } } while (false)
3016 SM.getProcResource(PRE.ProcResourceIdx);do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) { const MCProcResourceDesc
*ProcResource = SM.getProcResource(PRE.ProcResourceIdx); dbgs
() << format(" %16s(%2d): Count: %2d, NumUnits:%2d, Cycles:%2d\n"
, ProcResource->Name, PRE.ProcResourceIdx, ProcResourceCount
[PRE.ProcResourceIdx], ProcResource->NumUnits, PRE.Cycles)
; } }; } } while (false)
3017 dbgs() << format(" %16s(%2d): Count: %2d, NumUnits:%2d, Cycles:%2d\n",do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) { const MCProcResourceDesc
*ProcResource = SM.getProcResource(PRE.ProcResourceIdx); dbgs
() << format(" %16s(%2d): Count: %2d, NumUnits:%2d, Cycles:%2d\n"
, ProcResource->Name, PRE.ProcResourceIdx, ProcResourceCount
[PRE.ProcResourceIdx], ProcResource->NumUnits, PRE.Cycles)
; } }; } } while (false)
3018 ProcResource->Name, PRE.ProcResourceIdx,do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) { const MCProcResourceDesc
*ProcResource = SM.getProcResource(PRE.ProcResourceIdx); dbgs
() << format(" %16s(%2d): Count: %2d, NumUnits:%2d, Cycles:%2d\n"
, ProcResource->Name, PRE.ProcResourceIdx, ProcResourceCount
[PRE.ProcResourceIdx], ProcResource->NumUnits, PRE.Cycles)
; } }; } } while (false)
3019 ProcResourceCount[PRE.ProcResourceIdx],do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) { const MCProcResourceDesc
*ProcResource = SM.getProcResource(PRE.ProcResourceIdx); dbgs
() << format(" %16s(%2d): Count: %2d, NumUnits:%2d, Cycles:%2d\n"
, ProcResource->Name, PRE.ProcResourceIdx, ProcResourceCount
[PRE.ProcResourceIdx], ProcResource->NumUnits, PRE.Cycles)
; } }; } } while (false)
3020 ProcResource->NumUnits, PRE.Cycles);do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) { const MCProcResourceDesc
*ProcResource = SM.getProcResource(PRE.ProcResourceIdx); dbgs
() << format(" %16s(%2d): Count: %2d, NumUnits:%2d, Cycles:%2d\n"
, ProcResource->Name, PRE.ProcResourceIdx, ProcResourceCount
[PRE.ProcResourceIdx], ProcResource->NumUnits, PRE.Cycles)
; } }; } } while (false)
3021 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) { const MCProcResourceDesc
*ProcResource = SM.getProcResource(PRE.ProcResourceIdx); dbgs
() << format(" %16s(%2d): Count: %2d, NumUnits:%2d, Cycles:%2d\n"
, ProcResource->Name, PRE.ProcResourceIdx, ProcResourceCount
[PRE.ProcResourceIdx], ProcResource->NumUnits, PRE.Cycles)
; } }; } } while (false)
3022 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) { const MCProcResourceDesc
*ProcResource = SM.getProcResource(PRE.ProcResourceIdx); dbgs
() << format(" %16s(%2d): Count: %2d, NumUnits:%2d, Cycles:%2d\n"
, ProcResource->Name, PRE.ProcResourceIdx, ProcResourceCount
[PRE.ProcResourceIdx], ProcResource->NumUnits, PRE.Cycles)
; } }; } } while (false)
;
3023 }
3024 LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) dbgs() << "reserveResources: done!\n\n"
; }; } } while (false)
3025 if (SwpDebugResource)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) dbgs() << "reserveResources: done!\n\n"
; }; } } while (false)
3026 dbgs() << "reserveResources: done!\n\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) dbgs() << "reserveResources: done!\n\n"
; }; } } while (false)
3027 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pipeliner")) { { if (SwpDebugResource) dbgs() << "reserveResources: done!\n\n"
; }; } } while (false)
;
3028}
3029
3030bool ResourceManager::canReserveResources(const MachineInstr &MI) const {
3031 return canReserveResources(&MI.getDesc());
3032}
3033
3034void ResourceManager::reserveResources(const MachineInstr &MI) {
3035 return reserveResources(&MI.getDesc());
3036}
3037
3038void ResourceManager::clearResources() {
3039 if (UseDFA)
3040 return DFAResources->clearResources();
3041 std::fill(ProcResourceCount.begin(), ProcResourceCount.end(), 0);
3042}