Bug Summary

File:llvm/lib/CodeGen/MachineCombiner.cpp
Warning:line 532, column 5
Value stored to 'PrevLatencyDiff' is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name MachineCombiner.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 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/CodeGen -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include -D NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/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-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/CodeGen -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-09-04-040900-46481-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/CodeGen/MachineCombiner.cpp
1//===---- MachineCombiner.cpp - Instcombining on SSA form machine code ----===//
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// The machine combiner pass uses machine trace metrics to ensure the combined
10// instructions do not lengthen the critical path or the resource depth.
11//===----------------------------------------------------------------------===//
12
13#include "llvm/ADT/DenseMap.h"
14#include "llvm/ADT/Statistic.h"
15#include "llvm/Analysis/ProfileSummaryInfo.h"
16#include "llvm/CodeGen/LazyMachineBlockFrequencyInfo.h"
17#include "llvm/CodeGen/MachineDominators.h"
18#include "llvm/CodeGen/MachineFunction.h"
19#include "llvm/CodeGen/MachineFunctionPass.h"
20#include "llvm/CodeGen/MachineLoopInfo.h"
21#include "llvm/CodeGen/MachineRegisterInfo.h"
22#include "llvm/CodeGen/MachineSizeOpts.h"
23#include "llvm/CodeGen/MachineTraceMetrics.h"
24#include "llvm/CodeGen/Passes.h"
25#include "llvm/CodeGen/RegisterClassInfo.h"
26#include "llvm/CodeGen/TargetInstrInfo.h"
27#include "llvm/CodeGen/TargetRegisterInfo.h"
28#include "llvm/CodeGen/TargetSchedule.h"
29#include "llvm/CodeGen/TargetSubtargetInfo.h"
30#include "llvm/InitializePasses.h"
31#include "llvm/Support/CommandLine.h"
32#include "llvm/Support/Debug.h"
33#include "llvm/Support/raw_ostream.h"
34
35using namespace llvm;
36
37#define DEBUG_TYPE"machine-combiner" "machine-combiner"
38
39STATISTIC(NumInstCombined, "Number of machineinst combined")static llvm::Statistic NumInstCombined = {"machine-combiner",
"NumInstCombined", "Number of machineinst combined"};
40
41static cl::opt<unsigned>
42inc_threshold("machine-combiner-inc-threshold", cl::Hidden,
43 cl::desc("Incremental depth computation will be used for basic "
44 "blocks with more instructions."), cl::init(500));
45
46static cl::opt<bool> dump_intrs("machine-combiner-dump-subst-intrs", cl::Hidden,
47 cl::desc("Dump all substituted intrs"),
48 cl::init(false));
49
50#ifdef EXPENSIVE_CHECKS
51static cl::opt<bool> VerifyPatternOrder(
52 "machine-combiner-verify-pattern-order", cl::Hidden,
53 cl::desc(
54 "Verify that the generated patterns are ordered by increasing latency"),
55 cl::init(true));
56#else
57static cl::opt<bool> VerifyPatternOrder(
58 "machine-combiner-verify-pattern-order", cl::Hidden,
59 cl::desc(
60 "Verify that the generated patterns are ordered by increasing latency"),
61 cl::init(false));
62#endif
63
64namespace {
65class MachineCombiner : public MachineFunctionPass {
66 const TargetSubtargetInfo *STI;
67 const TargetInstrInfo *TII;
68 const TargetRegisterInfo *TRI;
69 MCSchedModel SchedModel;
70 MachineRegisterInfo *MRI;
71 MachineLoopInfo *MLI; // Current MachineLoopInfo
72 MachineTraceMetrics *Traces;
73 MachineTraceMetrics::Ensemble *MinInstr;
74 MachineBlockFrequencyInfo *MBFI;
75 ProfileSummaryInfo *PSI;
76 RegisterClassInfo RegClassInfo;
77
78 TargetSchedModel TSchedModel;
79
80 /// True if optimizing for code size.
81 bool OptSize;
82
83public:
84 static char ID;
85 MachineCombiner() : MachineFunctionPass(ID) {
86 initializeMachineCombinerPass(*PassRegistry::getPassRegistry());
87 }
88 void getAnalysisUsage(AnalysisUsage &AU) const override;
89 bool runOnMachineFunction(MachineFunction &MF) override;
90 StringRef getPassName() const override { return "Machine InstCombiner"; }
91
92private:
93 bool doSubstitute(unsigned NewSize, unsigned OldSize, bool OptForSize);
94 bool combineInstructions(MachineBasicBlock *);
95 MachineInstr *getOperandDef(const MachineOperand &MO);
96 unsigned getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
97 DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
98 MachineTraceMetrics::Trace BlockTrace);
99 unsigned getLatency(MachineInstr *Root, MachineInstr *NewRoot,
100 MachineTraceMetrics::Trace BlockTrace);
101 bool
102 improvesCriticalPathLen(MachineBasicBlock *MBB, MachineInstr *Root,
103 MachineTraceMetrics::Trace BlockTrace,
104 SmallVectorImpl<MachineInstr *> &InsInstrs,
105 SmallVectorImpl<MachineInstr *> &DelInstrs,
106 DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
107 MachineCombinerPattern Pattern, bool SlackIsAccurate);
108 bool reduceRegisterPressure(MachineInstr &Root, MachineBasicBlock *MBB,
109 SmallVectorImpl<MachineInstr *> &InsInstrs,
110 SmallVectorImpl<MachineInstr *> &DelInstrs,
111 MachineCombinerPattern Pattern);
112 bool preservesResourceLen(MachineBasicBlock *MBB,
113 MachineTraceMetrics::Trace BlockTrace,
114 SmallVectorImpl<MachineInstr *> &InsInstrs,
115 SmallVectorImpl<MachineInstr *> &DelInstrs);
116 void instr2instrSC(SmallVectorImpl<MachineInstr *> &Instrs,
117 SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC);
118 std::pair<unsigned, unsigned>
119 getLatenciesForInstrSequences(MachineInstr &MI,
120 SmallVectorImpl<MachineInstr *> &InsInstrs,
121 SmallVectorImpl<MachineInstr *> &DelInstrs,
122 MachineTraceMetrics::Trace BlockTrace);
123
124 void verifyPatternOrder(MachineBasicBlock *MBB, MachineInstr &Root,
125 SmallVector<MachineCombinerPattern, 16> &Patterns);
126};
127}
128
129char MachineCombiner::ID = 0;
130char &llvm::MachineCombinerID = MachineCombiner::ID;
131
132INITIALIZE_PASS_BEGIN(MachineCombiner, DEBUG_TYPE,static void *initializeMachineCombinerPassOnce(PassRegistry &
Registry) {
133 "Machine InstCombiner", false, false)static void *initializeMachineCombinerPassOnce(PassRegistry &
Registry) {
134INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)initializeMachineLoopInfoPass(Registry);
135INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics)initializeMachineTraceMetricsPass(Registry);
136INITIALIZE_PASS_END(MachineCombiner, DEBUG_TYPE, "Machine InstCombiner",PassInfo *PI = new PassInfo( "Machine InstCombiner", "machine-combiner"
, &MachineCombiner::ID, PassInfo::NormalCtor_t(callDefaultCtor
<MachineCombiner>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeMachineCombinerPassFlag
; void llvm::initializeMachineCombinerPass(PassRegistry &
Registry) { llvm::call_once(InitializeMachineCombinerPassFlag
, initializeMachineCombinerPassOnce, std::ref(Registry)); }
137 false, false)PassInfo *PI = new PassInfo( "Machine InstCombiner", "machine-combiner"
, &MachineCombiner::ID, PassInfo::NormalCtor_t(callDefaultCtor
<MachineCombiner>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeMachineCombinerPassFlag
; void llvm::initializeMachineCombinerPass(PassRegistry &
Registry) { llvm::call_once(InitializeMachineCombinerPassFlag
, initializeMachineCombinerPassOnce, std::ref(Registry)); }
138
139void MachineCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
140 AU.setPreservesCFG();
141 AU.addPreserved<MachineDominatorTree>();
142 AU.addRequired<MachineLoopInfo>();
143 AU.addPreserved<MachineLoopInfo>();
144 AU.addRequired<MachineTraceMetrics>();
145 AU.addPreserved<MachineTraceMetrics>();
146 AU.addRequired<LazyMachineBlockFrequencyInfoPass>();
147 AU.addRequired<ProfileSummaryInfoWrapperPass>();
148 MachineFunctionPass::getAnalysisUsage(AU);
149}
150
151MachineInstr *MachineCombiner::getOperandDef(const MachineOperand &MO) {
152 MachineInstr *DefInstr = nullptr;
153 // We need a virtual register definition.
154 if (MO.isReg() && Register::isVirtualRegister(MO.getReg()))
155 DefInstr = MRI->getUniqueVRegDef(MO.getReg());
156 // PHI's have no depth etc.
157 if (DefInstr && DefInstr->isPHI())
158 DefInstr = nullptr;
159 return DefInstr;
160}
161
162/// Computes depth of instructions in vector \InsInstr.
163///
164/// \param InsInstrs is a vector of machine instructions
165/// \param InstrIdxForVirtReg is a dense map of virtual register to index
166/// of defining machine instruction in \p InsInstrs
167/// \param BlockTrace is a trace of machine instructions
168///
169/// \returns Depth of last instruction in \InsInstrs ("NewRoot")
170unsigned
171MachineCombiner::getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
172 DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
173 MachineTraceMetrics::Trace BlockTrace) {
174 SmallVector<unsigned, 16> InstrDepth;
175 assert(TSchedModel.hasInstrSchedModelOrItineraries() &&(static_cast<void> (0))
176 "Missing machine model\n")(static_cast<void> (0));
177
178 // For each instruction in the new sequence compute the depth based on the
179 // operands. Use the trace information when possible. For new operands which
180 // are tracked in the InstrIdxForVirtReg map depth is looked up in InstrDepth
181 for (auto *InstrPtr : InsInstrs) { // for each Use
182 unsigned IDepth = 0;
183 for (const MachineOperand &MO : InstrPtr->operands()) {
184 // Check for virtual register operand.
185 if (!(MO.isReg() && Register::isVirtualRegister(MO.getReg())))
186 continue;
187 if (!MO.isUse())
188 continue;
189 unsigned DepthOp = 0;
190 unsigned LatencyOp = 0;
191 DenseMap<unsigned, unsigned>::iterator II =
192 InstrIdxForVirtReg.find(MO.getReg());
193 if (II != InstrIdxForVirtReg.end()) {
194 // Operand is new virtual register not in trace
195 assert(II->second < InstrDepth.size() && "Bad Index")(static_cast<void> (0));
196 MachineInstr *DefInstr = InsInstrs[II->second];
197 assert(DefInstr &&(static_cast<void> (0))
198 "There must be a definition for a new virtual register")(static_cast<void> (0));
199 DepthOp = InstrDepth[II->second];
200 int DefIdx = DefInstr->findRegisterDefOperandIdx(MO.getReg());
201 int UseIdx = InstrPtr->findRegisterUseOperandIdx(MO.getReg());
202 LatencyOp = TSchedModel.computeOperandLatency(DefInstr, DefIdx,
203 InstrPtr, UseIdx);
204 } else {
205 MachineInstr *DefInstr = getOperandDef(MO);
206 if (DefInstr) {
207 DepthOp = BlockTrace.getInstrCycles(*DefInstr).Depth;
208 LatencyOp = TSchedModel.computeOperandLatency(
209 DefInstr, DefInstr->findRegisterDefOperandIdx(MO.getReg()),
210 InstrPtr, InstrPtr->findRegisterUseOperandIdx(MO.getReg()));
211 }
212 }
213 IDepth = std::max(IDepth, DepthOp + LatencyOp);
214 }
215 InstrDepth.push_back(IDepth);
216 }
217 unsigned NewRootIdx = InsInstrs.size() - 1;
218 return InstrDepth[NewRootIdx];
219}
220
221/// Computes instruction latency as max of latency of defined operands.
222///
223/// \param Root is a machine instruction that could be replaced by NewRoot.
224/// It is used to compute a more accurate latency information for NewRoot in
225/// case there is a dependent instruction in the same trace (\p BlockTrace)
226/// \param NewRoot is the instruction for which the latency is computed
227/// \param BlockTrace is a trace of machine instructions
228///
229/// \returns Latency of \p NewRoot
230unsigned MachineCombiner::getLatency(MachineInstr *Root, MachineInstr *NewRoot,
231 MachineTraceMetrics::Trace BlockTrace) {
232 assert(TSchedModel.hasInstrSchedModelOrItineraries() &&(static_cast<void> (0))
233 "Missing machine model\n")(static_cast<void> (0));
234
235 // Check each definition in NewRoot and compute the latency
236 unsigned NewRootLatency = 0;
237
238 for (const MachineOperand &MO : NewRoot->operands()) {
239 // Check for virtual register operand.
240 if (!(MO.isReg() && Register::isVirtualRegister(MO.getReg())))
241 continue;
242 if (!MO.isDef())
243 continue;
244 // Get the first instruction that uses MO
245 MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(MO.getReg());
246 RI++;
247 if (RI == MRI->reg_end())
248 continue;
249 MachineInstr *UseMO = RI->getParent();
250 unsigned LatencyOp = 0;
251 if (UseMO && BlockTrace.isDepInTrace(*Root, *UseMO)) {
252 LatencyOp = TSchedModel.computeOperandLatency(
253 NewRoot, NewRoot->findRegisterDefOperandIdx(MO.getReg()), UseMO,
254 UseMO->findRegisterUseOperandIdx(MO.getReg()));
255 } else {
256 LatencyOp = TSchedModel.computeInstrLatency(NewRoot);
257 }
258 NewRootLatency = std::max(NewRootLatency, LatencyOp);
259 }
260 return NewRootLatency;
261}
262
263/// The combiner's goal may differ based on which pattern it is attempting
264/// to optimize.
265enum class CombinerObjective {
266 MustReduceDepth, // The data dependency chain must be improved.
267 MustReduceRegisterPressure, // The register pressure must be reduced.
268 Default // The critical path must not be lengthened.
269};
270
271static CombinerObjective getCombinerObjective(MachineCombinerPattern P) {
272 // TODO: If C++ ever gets a real enum class, make this part of the
273 // MachineCombinerPattern class.
274 switch (P) {
275 case MachineCombinerPattern::REASSOC_AX_BY:
276 case MachineCombinerPattern::REASSOC_AX_YB:
277 case MachineCombinerPattern::REASSOC_XA_BY:
278 case MachineCombinerPattern::REASSOC_XA_YB:
279 case MachineCombinerPattern::REASSOC_XY_AMM_BMM:
280 case MachineCombinerPattern::REASSOC_XMM_AMM_BMM:
281 return CombinerObjective::MustReduceDepth;
282 case MachineCombinerPattern::REASSOC_XY_BCA:
283 case MachineCombinerPattern::REASSOC_XY_BAC:
284 return CombinerObjective::MustReduceRegisterPressure;
285 default:
286 return CombinerObjective::Default;
287 }
288}
289
290/// Estimate the latency of the new and original instruction sequence by summing
291/// up the latencies of the inserted and deleted instructions. This assumes
292/// that the inserted and deleted instructions are dependent instruction chains,
293/// which might not hold in all cases.
294std::pair<unsigned, unsigned> MachineCombiner::getLatenciesForInstrSequences(
295 MachineInstr &MI, SmallVectorImpl<MachineInstr *> &InsInstrs,
296 SmallVectorImpl<MachineInstr *> &DelInstrs,
297 MachineTraceMetrics::Trace BlockTrace) {
298 assert(!InsInstrs.empty() && "Only support sequences that insert instrs.")(static_cast<void> (0));
299 unsigned NewRootLatency = 0;
300 // NewRoot is the last instruction in the \p InsInstrs vector.
301 MachineInstr *NewRoot = InsInstrs.back();
302 for (unsigned i = 0; i < InsInstrs.size() - 1; i++)
303 NewRootLatency += TSchedModel.computeInstrLatency(InsInstrs[i]);
304 NewRootLatency += getLatency(&MI, NewRoot, BlockTrace);
305
306 unsigned RootLatency = 0;
307 for (auto I : DelInstrs)
308 RootLatency += TSchedModel.computeInstrLatency(I);
309
310 return {NewRootLatency, RootLatency};
311}
312
313bool MachineCombiner::reduceRegisterPressure(
314 MachineInstr &Root, MachineBasicBlock *MBB,
315 SmallVectorImpl<MachineInstr *> &InsInstrs,
316 SmallVectorImpl<MachineInstr *> &DelInstrs,
317 MachineCombinerPattern Pattern) {
318 // FIXME: for now, we don't do any check for the register pressure patterns.
319 // We treat them as always profitable. But we can do better if we make
320 // RegPressureTracker class be aware of TIE attribute. Then we can get an
321 // accurate compare of register pressure with DelInstrs or InsInstrs.
322 return true;
323}
324
325/// The DAGCombine code sequence ends in MI (Machine Instruction) Root.
326/// The new code sequence ends in MI NewRoot. A necessary condition for the new
327/// sequence to replace the old sequence is that it cannot lengthen the critical
328/// path. The definition of "improve" may be restricted by specifying that the
329/// new path improves the data dependency chain (MustReduceDepth).
330bool MachineCombiner::improvesCriticalPathLen(
331 MachineBasicBlock *MBB, MachineInstr *Root,
332 MachineTraceMetrics::Trace BlockTrace,
333 SmallVectorImpl<MachineInstr *> &InsInstrs,
334 SmallVectorImpl<MachineInstr *> &DelInstrs,
335 DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
336 MachineCombinerPattern Pattern,
337 bool SlackIsAccurate) {
338 assert(TSchedModel.hasInstrSchedModelOrItineraries() &&(static_cast<void> (0))
339 "Missing machine model\n")(static_cast<void> (0));
340 // Get depth and latency of NewRoot and Root.
341 unsigned NewRootDepth = getDepth(InsInstrs, InstrIdxForVirtReg, BlockTrace);
342 unsigned RootDepth = BlockTrace.getInstrCycles(*Root).Depth;
343
344 LLVM_DEBUG(dbgs() << " Dependence data for " << *Root << "\tNewRootDepth: "do { } while (false)
345 << NewRootDepth << "\tRootDepth: " << RootDepth)do { } while (false);
346
347 // For a transform such as reassociation, the cost equation is
348 // conservatively calculated so that we must improve the depth (data
349 // dependency cycles) in the critical path to proceed with the transform.
350 // Being conservative also protects against inaccuracies in the underlying
351 // machine trace metrics and CPU models.
352 if (getCombinerObjective(Pattern) == CombinerObjective::MustReduceDepth) {
353 LLVM_DEBUG(dbgs() << "\tIt MustReduceDepth ")do { } while (false);
354 LLVM_DEBUG(NewRootDepth < RootDepthdo { } while (false)
355 ? dbgs() << "\t and it does it\n"do { } while (false)
356 : dbgs() << "\t but it does NOT do it\n")do { } while (false);
357 return NewRootDepth < RootDepth;
358 }
359
360 // A more flexible cost calculation for the critical path includes the slack
361 // of the original code sequence. This may allow the transform to proceed
362 // even if the instruction depths (data dependency cycles) become worse.
363
364 // Account for the latency of the inserted and deleted instructions by
365 unsigned NewRootLatency, RootLatency;
366 std::tie(NewRootLatency, RootLatency) =
367 getLatenciesForInstrSequences(*Root, InsInstrs, DelInstrs, BlockTrace);
368
369 unsigned RootSlack = BlockTrace.getInstrSlack(*Root);
370 unsigned NewCycleCount = NewRootDepth + NewRootLatency;
371 unsigned OldCycleCount =
372 RootDepth + RootLatency + (SlackIsAccurate ? RootSlack : 0);
373 LLVM_DEBUG(dbgs() << "\n\tNewRootLatency: " << NewRootLatencydo { } while (false)
374 << "\tRootLatency: " << RootLatency << "\n\tRootSlack: "do { } while (false)
375 << RootSlack << " SlackIsAccurate=" << SlackIsAccuratedo { } while (false)
376 << "\n\tNewRootDepth + NewRootLatency = " << NewCycleCountdo { } while (false)
377 << "\n\tRootDepth + RootLatency + RootSlack = "do { } while (false)
378 << OldCycleCount;)do { } while (false);
379 LLVM_DEBUG(NewCycleCount <= OldCycleCountdo { } while (false)
380 ? dbgs() << "\n\t It IMPROVES PathLen because"do { } while (false)
381 : dbgs() << "\n\t It DOES NOT improve PathLen because")do { } while (false);
382 LLVM_DEBUG(dbgs() << "\n\t\tNewCycleCount = " << NewCycleCountdo { } while (false)
383 << ", OldCycleCount = " << OldCycleCount << "\n")do { } while (false);
384
385 return NewCycleCount <= OldCycleCount;
386}
387
388/// helper routine to convert instructions into SC
389void MachineCombiner::instr2instrSC(
390 SmallVectorImpl<MachineInstr *> &Instrs,
391 SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC) {
392 for (auto *InstrPtr : Instrs) {
393 unsigned Opc = InstrPtr->getOpcode();
394 unsigned Idx = TII->get(Opc).getSchedClass();
395 const MCSchedClassDesc *SC = SchedModel.getSchedClassDesc(Idx);
396 InstrsSC.push_back(SC);
397 }
398}
399
400/// True when the new instructions do not increase resource length
401bool MachineCombiner::preservesResourceLen(
402 MachineBasicBlock *MBB, MachineTraceMetrics::Trace BlockTrace,
403 SmallVectorImpl<MachineInstr *> &InsInstrs,
404 SmallVectorImpl<MachineInstr *> &DelInstrs) {
405 if (!TSchedModel.hasInstrSchedModel())
406 return true;
407
408 // Compute current resource length
409
410 //ArrayRef<const MachineBasicBlock *> MBBarr(MBB);
411 SmallVector <const MachineBasicBlock *, 1> MBBarr;
412 MBBarr.push_back(MBB);
413 unsigned ResLenBeforeCombine = BlockTrace.getResourceLength(MBBarr);
414
415 // Deal with SC rather than Instructions.
416 SmallVector<const MCSchedClassDesc *, 16> InsInstrsSC;
417 SmallVector<const MCSchedClassDesc *, 16> DelInstrsSC;
418
419 instr2instrSC(InsInstrs, InsInstrsSC);
420 instr2instrSC(DelInstrs, DelInstrsSC);
421
422 ArrayRef<const MCSchedClassDesc *> MSCInsArr = makeArrayRef(InsInstrsSC);
423 ArrayRef<const MCSchedClassDesc *> MSCDelArr = makeArrayRef(DelInstrsSC);
424
425 // Compute new resource length.
426 unsigned ResLenAfterCombine =
427 BlockTrace.getResourceLength(MBBarr, MSCInsArr, MSCDelArr);
428
429 LLVM_DEBUG(dbgs() << "\t\tResource length before replacement: "do { } while (false)
430 << ResLenBeforeCombinedo { } while (false)
431 << " and after: " << ResLenAfterCombine << "\n";)do { } while (false);
432 LLVM_DEBUG(do { } while (false)
433 ResLenAfterCombine <=do { } while (false)
434 ResLenBeforeCombine + TII->getExtendResourceLenLimit()do { } while (false)
435 ? dbgs() << "\t\t As result it IMPROVES/PRESERVES Resource Length\n"do { } while (false)
436 : dbgs() << "\t\t As result it DOES NOT improve/preserve Resource "do { } while (false)
437 "Length\n")do { } while (false);
438
439 return ResLenAfterCombine <=
440 ResLenBeforeCombine + TII->getExtendResourceLenLimit();
441}
442
443/// \returns true when new instruction sequence should be generated
444/// independent if it lengthens critical path or not
445bool MachineCombiner::doSubstitute(unsigned NewSize, unsigned OldSize,
446 bool OptForSize) {
447 if (OptForSize && (NewSize < OldSize))
448 return true;
449 if (!TSchedModel.hasInstrSchedModelOrItineraries())
450 return true;
451 return false;
452}
453
454/// Inserts InsInstrs and deletes DelInstrs. Incrementally updates instruction
455/// depths if requested.
456///
457/// \param MBB basic block to insert instructions in
458/// \param MI current machine instruction
459/// \param InsInstrs new instructions to insert in \p MBB
460/// \param DelInstrs instruction to delete from \p MBB
461/// \param MinInstr is a pointer to the machine trace information
462/// \param RegUnits set of live registers, needed to compute instruction depths
463/// \param TII is target instruction info, used to call target hook
464/// \param Pattern is used to call target hook finalizeInsInstrs
465/// \param IncrementalUpdate if true, compute instruction depths incrementally,
466/// otherwise invalidate the trace
467static void insertDeleteInstructions(MachineBasicBlock *MBB, MachineInstr &MI,
468 SmallVector<MachineInstr *, 16> InsInstrs,
469 SmallVector<MachineInstr *, 16> DelInstrs,
470 MachineTraceMetrics::Ensemble *MinInstr,
471 SparseSet<LiveRegUnit> &RegUnits,
472 const TargetInstrInfo *TII,
473 MachineCombinerPattern Pattern,
474 bool IncrementalUpdate) {
475 // If we want to fix up some placeholder for some target, do it now.
476 // We need this because in genAlternativeCodeSequence, we have not decided the
477 // better pattern InsInstrs or DelInstrs, so we don't want generate some
478 // sideeffect to the function. For example we need to delay the constant pool
479 // entry creation here after InsInstrs is selected as better pattern.
480 // Otherwise the constant pool entry created for InsInstrs will not be deleted
481 // even if InsInstrs is not the better pattern.
482 TII->finalizeInsInstrs(MI, Pattern, InsInstrs);
483
484 for (auto *InstrPtr : InsInstrs)
485 MBB->insert((MachineBasicBlock::iterator)&MI, InstrPtr);
486
487 for (auto *InstrPtr : DelInstrs) {
488 InstrPtr->eraseFromParentAndMarkDBGValuesForRemoval();
489 // Erase all LiveRegs defined by the removed instruction
490 for (auto I = RegUnits.begin(); I != RegUnits.end(); ) {
491 if (I->MI == InstrPtr)
492 I = RegUnits.erase(I);
493 else
494 I++;
495 }
496 }
497
498 if (IncrementalUpdate)
499 for (auto *InstrPtr : InsInstrs)
500 MinInstr->updateDepth(MBB, *InstrPtr, RegUnits);
501 else
502 MinInstr->invalidate(MBB);
503
504 NumInstCombined++;
505}
506
507// Check that the difference between original and new latency is decreasing for
508// later patterns. This helps to discover sub-optimal pattern orderings.
509void MachineCombiner::verifyPatternOrder(
510 MachineBasicBlock *MBB, MachineInstr &Root,
511 SmallVector<MachineCombinerPattern, 16> &Patterns) {
512 long PrevLatencyDiff = std::numeric_limits<long>::max();
513 (void)PrevLatencyDiff; // Variable is used in assert only.
514 for (auto P : Patterns) {
515 SmallVector<MachineInstr *, 16> InsInstrs;
516 SmallVector<MachineInstr *, 16> DelInstrs;
517 DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
518 TII->genAlternativeCodeSequence(Root, P, InsInstrs, DelInstrs,
519 InstrIdxForVirtReg);
520 // Found pattern, but did not generate alternative sequence.
521 // This can happen e.g. when an immediate could not be materialized
522 // in a single instruction.
523 if (InsInstrs.empty() || !TSchedModel.hasInstrSchedModelOrItineraries())
524 continue;
525
526 unsigned NewRootLatency, RootLatency;
527 std::tie(NewRootLatency, RootLatency) = getLatenciesForInstrSequences(
528 Root, InsInstrs, DelInstrs, MinInstr->getTrace(MBB));
529 long CurrentLatencyDiff = ((long)RootLatency) - ((long)NewRootLatency);
530 assert(CurrentLatencyDiff <= PrevLatencyDiff &&(static_cast<void> (0))
531 "Current pattern is better than previous pattern.")(static_cast<void> (0));
532 PrevLatencyDiff = CurrentLatencyDiff;
Value stored to 'PrevLatencyDiff' is never read
533 }
534}
535
536/// Substitute a slow code sequence with a faster one by
537/// evaluating instruction combining pattern.
538/// The prototype of such a pattern is MUl + ADD -> MADD. Performs instruction
539/// combining based on machine trace metrics. Only combine a sequence of
540/// instructions when this neither lengthens the critical path nor increases
541/// resource pressure. When optimizing for codesize always combine when the new
542/// sequence is shorter.
543bool MachineCombiner::combineInstructions(MachineBasicBlock *MBB) {
544 bool Changed = false;
545 LLVM_DEBUG(dbgs() << "Combining MBB " << MBB->getName() << "\n")do { } while (false);
546
547 bool IncrementalUpdate = false;
548 auto BlockIter = MBB->begin();
549 decltype(BlockIter) LastUpdate;
550 // Check if the block is in a loop.
551 const MachineLoop *ML = MLI->getLoopFor(MBB);
552 if (!MinInstr)
553 MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
554
555 SparseSet<LiveRegUnit> RegUnits;
556 RegUnits.setUniverse(TRI->getNumRegUnits());
557
558 bool OptForSize = OptSize || llvm::shouldOptimizeForSize(MBB, PSI, MBFI);
559
560 bool DoRegPressureReduce =
561 TII->shouldReduceRegisterPressure(MBB, &RegClassInfo);
562
563 while (BlockIter != MBB->end()) {
564 auto &MI = *BlockIter++;
565 SmallVector<MachineCombinerPattern, 16> Patterns;
566 // The motivating example is:
567 //
568 // MUL Other MUL_op1 MUL_op2 Other
569 // \ / \ | /
570 // ADD/SUB => MADD/MSUB
571 // (=Root) (=NewRoot)
572
573 // The DAGCombine code always replaced MUL + ADD/SUB by MADD. While this is
574 // usually beneficial for code size it unfortunately can hurt performance
575 // when the ADD is on the critical path, but the MUL is not. With the
576 // substitution the MUL becomes part of the critical path (in form of the
577 // MADD) and can lengthen it on architectures where the MADD latency is
578 // longer than the ADD latency.
579 //
580 // For each instruction we check if it can be the root of a combiner
581 // pattern. Then for each pattern the new code sequence in form of MI is
582 // generated and evaluated. When the efficiency criteria (don't lengthen
583 // critical path, don't use more resources) is met the new sequence gets
584 // hooked up into the basic block before the old sequence is removed.
585 //
586 // The algorithm does not try to evaluate all patterns and pick the best.
587 // This is only an artificial restriction though. In practice there is
588 // mostly one pattern, and getMachineCombinerPatterns() can order patterns
589 // based on an internal cost heuristic. If
590 // machine-combiner-verify-pattern-order is enabled, all patterns are
591 // checked to ensure later patterns do not provide better latency savings.
592
593 if (!TII->getMachineCombinerPatterns(MI, Patterns, DoRegPressureReduce))
594 continue;
595
596 if (VerifyPatternOrder)
597 verifyPatternOrder(MBB, MI, Patterns);
598
599 for (auto P : Patterns) {
600 SmallVector<MachineInstr *, 16> InsInstrs;
601 SmallVector<MachineInstr *, 16> DelInstrs;
602 DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
603 TII->genAlternativeCodeSequence(MI, P, InsInstrs, DelInstrs,
604 InstrIdxForVirtReg);
605 unsigned NewInstCount = InsInstrs.size();
606 unsigned OldInstCount = DelInstrs.size();
607 // Found pattern, but did not generate alternative sequence.
608 // This can happen e.g. when an immediate could not be materialized
609 // in a single instruction.
610 if (!NewInstCount)
611 continue;
612
613 LLVM_DEBUG(if (dump_intrs) {do { } while (false)
614 dbgs() << "\tFor the Pattern (" << (int)Pdo { } while (false)
615 << ") these instructions could be removed\n";do { } while (false)
616 for (auto const *InstrPtr : DelInstrs)do { } while (false)
617 InstrPtr->print(dbgs(), /*IsStandalone*/false, /*SkipOpers*/false,do { } while (false)
618 /*SkipDebugLoc*/false, /*AddNewLine*/true, TII);do { } while (false)
619 dbgs() << "\tThese instructions could replace the removed ones\n";do { } while (false)
620 for (auto const *InstrPtr : InsInstrs)do { } while (false)
621 InstrPtr->print(dbgs(), /*IsStandalone*/false, /*SkipOpers*/false,do { } while (false)
622 /*SkipDebugLoc*/false, /*AddNewLine*/true, TII);do { } while (false)
623 })do { } while (false);
624
625 bool SubstituteAlways = false;
626 if (ML && TII->isThroughputPattern(P))
627 SubstituteAlways = true;
628
629 if (IncrementalUpdate && LastUpdate != BlockIter) {
630 // Update depths since the last incremental update.
631 MinInstr->updateDepths(LastUpdate, BlockIter, RegUnits);
632 LastUpdate = BlockIter;
633 }
634
635 if (DoRegPressureReduce &&
636 getCombinerObjective(P) ==
637 CombinerObjective::MustReduceRegisterPressure) {
638 if (MBB->size() > inc_threshold) {
639 // Use incremental depth updates for basic blocks above threshold
640 IncrementalUpdate = true;
641 LastUpdate = BlockIter;
642 }
643 if (reduceRegisterPressure(MI, MBB, InsInstrs, DelInstrs, P)) {
644 // Replace DelInstrs with InsInstrs.
645 insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
646 RegUnits, TII, P, IncrementalUpdate);
647 Changed |= true;
648
649 // Go back to previous instruction as it may have ILP reassociation
650 // opportunity.
651 BlockIter--;
652 break;
653 }
654 }
655
656 // Substitute when we optimize for codesize and the new sequence has
657 // fewer instructions OR
658 // the new sequence neither lengthens the critical path nor increases
659 // resource pressure.
660 if (SubstituteAlways ||
661 doSubstitute(NewInstCount, OldInstCount, OptForSize)) {
662 insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
663 RegUnits, TII, P, IncrementalUpdate);
664 // Eagerly stop after the first pattern fires.
665 Changed = true;
666 break;
667 } else {
668 // For big basic blocks, we only compute the full trace the first time
669 // we hit this. We do not invalidate the trace, but instead update the
670 // instruction depths incrementally.
671 // NOTE: Only the instruction depths up to MI are accurate. All other
672 // trace information is not updated.
673 MachineTraceMetrics::Trace BlockTrace = MinInstr->getTrace(MBB);
674 Traces->verifyAnalysis();
675 if (improvesCriticalPathLen(MBB, &MI, BlockTrace, InsInstrs, DelInstrs,
676 InstrIdxForVirtReg, P,
677 !IncrementalUpdate) &&
678 preservesResourceLen(MBB, BlockTrace, InsInstrs, DelInstrs)) {
679 if (MBB->size() > inc_threshold) {
680 // Use incremental depth updates for basic blocks above treshold
681 IncrementalUpdate = true;
682 LastUpdate = BlockIter;
683 }
684
685 insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
686 RegUnits, TII, P, IncrementalUpdate);
687
688 // Eagerly stop after the first pattern fires.
689 Changed = true;
690 break;
691 }
692 // Cleanup instructions of the alternative code sequence. There is no
693 // use for them.
694 MachineFunction *MF = MBB->getParent();
695 for (auto *InstrPtr : InsInstrs)
696 MF->DeleteMachineInstr(InstrPtr);
697 }
698 InstrIdxForVirtReg.clear();
699 }
700 }
701
702 if (Changed && IncrementalUpdate)
703 Traces->invalidate(MBB);
704 return Changed;
705}
706
707bool MachineCombiner::runOnMachineFunction(MachineFunction &MF) {
708 STI = &MF.getSubtarget();
709 TII = STI->getInstrInfo();
710 TRI = STI->getRegisterInfo();
711 SchedModel = STI->getSchedModel();
712 TSchedModel.init(STI);
713 MRI = &MF.getRegInfo();
714 MLI = &getAnalysis<MachineLoopInfo>();
715 Traces = &getAnalysis<MachineTraceMetrics>();
716 PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
717 MBFI = (PSI && PSI->hasProfileSummary()) ?
718 &getAnalysis<LazyMachineBlockFrequencyInfoPass>().getBFI() :
719 nullptr;
720 MinInstr = nullptr;
721 OptSize = MF.getFunction().hasOptSize();
722 RegClassInfo.runOnMachineFunction(MF);
723
724 LLVM_DEBUG(dbgs() << getPassName() << ": " << MF.getName() << '\n')do { } while (false);
725 if (!TII->useMachineCombiner()) {
726 LLVM_DEBUG(do { } while (false)
727 dbgs()do { } while (false)
728 << " Skipping pass: Target does not support machine combiner\n")do { } while (false);
729 return false;
730 }
731
732 bool Changed = false;
733
734 // Try to combine instructions.
735 for (auto &MBB : MF)
736 Changed |= combineInstructions(&MBB);
737
738 return Changed;
739}