Line data Source code
1 : //===---- MachineCombiner.cpp - Instcombining on SSA form machine code ----===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // The machine combiner pass uses machine trace metrics to ensure the combined
11 : // instructions do not lengthen the critical path or the resource depth.
12 : //===----------------------------------------------------------------------===//
13 :
14 : #include "llvm/ADT/DenseMap.h"
15 : #include "llvm/ADT/Statistic.h"
16 : #include "llvm/CodeGen/MachineDominators.h"
17 : #include "llvm/CodeGen/MachineFunction.h"
18 : #include "llvm/CodeGen/MachineFunctionPass.h"
19 : #include "llvm/CodeGen/MachineLoopInfo.h"
20 : #include "llvm/CodeGen/MachineRegisterInfo.h"
21 : #include "llvm/CodeGen/MachineTraceMetrics.h"
22 : #include "llvm/CodeGen/Passes.h"
23 : #include "llvm/CodeGen/TargetInstrInfo.h"
24 : #include "llvm/CodeGen/TargetRegisterInfo.h"
25 : #include "llvm/CodeGen/TargetSchedule.h"
26 : #include "llvm/CodeGen/TargetSubtargetInfo.h"
27 : #include "llvm/Support/CommandLine.h"
28 : #include "llvm/Support/Debug.h"
29 : #include "llvm/Support/raw_ostream.h"
30 :
31 : using namespace llvm;
32 :
33 : #define DEBUG_TYPE "machine-combiner"
34 :
35 : STATISTIC(NumInstCombined, "Number of machineinst combined");
36 :
37 : static cl::opt<unsigned>
38 : inc_threshold("machine-combiner-inc-threshold", cl::Hidden,
39 : cl::desc("Incremental depth computation will be used for basic "
40 : "blocks with more instructions."), cl::init(500));
41 :
42 : static cl::opt<bool> dump_intrs("machine-combiner-dump-subst-intrs", cl::Hidden,
43 : cl::desc("Dump all substituted intrs"),
44 : cl::init(false));
45 :
46 : #ifdef EXPENSIVE_CHECKS
47 : static cl::opt<bool> VerifyPatternOrder(
48 : "machine-combiner-verify-pattern-order", cl::Hidden,
49 : cl::desc(
50 : "Verify that the generated patterns are ordered by increasing latency"),
51 : cl::init(true));
52 : #else
53 : static cl::opt<bool> VerifyPatternOrder(
54 : "machine-combiner-verify-pattern-order", cl::Hidden,
55 : cl::desc(
56 : "Verify that the generated patterns are ordered by increasing latency"),
57 : cl::init(false));
58 : #endif
59 :
60 : namespace {
61 : class MachineCombiner : public MachineFunctionPass {
62 : const TargetSubtargetInfo *STI;
63 : const TargetInstrInfo *TII;
64 : const TargetRegisterInfo *TRI;
65 : MCSchedModel SchedModel;
66 : MachineRegisterInfo *MRI;
67 : MachineLoopInfo *MLI; // Current MachineLoopInfo
68 : MachineTraceMetrics *Traces;
69 : MachineTraceMetrics::Ensemble *MinInstr;
70 :
71 : TargetSchedModel TSchedModel;
72 :
73 : /// True if optimizing for code size.
74 : bool OptSize;
75 :
76 : public:
77 : static char ID;
78 10960 : MachineCombiner() : MachineFunctionPass(ID) {
79 10960 : initializeMachineCombinerPass(*PassRegistry::getPassRegistry());
80 10960 : }
81 : void getAnalysisUsage(AnalysisUsage &AU) const override;
82 : bool runOnMachineFunction(MachineFunction &MF) override;
83 10915 : StringRef getPassName() const override { return "Machine InstCombiner"; }
84 :
85 : private:
86 : bool doSubstitute(unsigned NewSize, unsigned OldSize);
87 : bool combineInstructions(MachineBasicBlock *);
88 : MachineInstr *getOperandDef(const MachineOperand &MO);
89 : unsigned getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
90 : DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
91 : MachineTraceMetrics::Trace BlockTrace);
92 : unsigned getLatency(MachineInstr *Root, MachineInstr *NewRoot,
93 : MachineTraceMetrics::Trace BlockTrace);
94 : bool
95 : improvesCriticalPathLen(MachineBasicBlock *MBB, MachineInstr *Root,
96 : MachineTraceMetrics::Trace BlockTrace,
97 : SmallVectorImpl<MachineInstr *> &InsInstrs,
98 : SmallVectorImpl<MachineInstr *> &DelInstrs,
99 : DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
100 : MachineCombinerPattern Pattern, bool SlackIsAccurate);
101 : bool preservesResourceLen(MachineBasicBlock *MBB,
102 : MachineTraceMetrics::Trace BlockTrace,
103 : SmallVectorImpl<MachineInstr *> &InsInstrs,
104 : SmallVectorImpl<MachineInstr *> &DelInstrs);
105 : void instr2instrSC(SmallVectorImpl<MachineInstr *> &Instrs,
106 : SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC);
107 : std::pair<unsigned, unsigned>
108 : getLatenciesForInstrSequences(MachineInstr &MI,
109 : SmallVectorImpl<MachineInstr *> &InsInstrs,
110 : SmallVectorImpl<MachineInstr *> &DelInstrs,
111 : MachineTraceMetrics::Trace BlockTrace);
112 :
113 : void verifyPatternOrder(MachineBasicBlock *MBB, MachineInstr &Root,
114 : SmallVector<MachineCombinerPattern, 16> &Patterns);
115 : };
116 : }
117 :
118 : char MachineCombiner::ID = 0;
119 : char &llvm::MachineCombinerID = MachineCombiner::ID;
120 :
121 31780 : INITIALIZE_PASS_BEGIN(MachineCombiner, DEBUG_TYPE,
122 : "Machine InstCombiner", false, false)
123 31780 : INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
124 31780 : INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics)
125 96107 : INITIALIZE_PASS_END(MachineCombiner, DEBUG_TYPE, "Machine InstCombiner",
126 : false, false)
127 :
128 10899 : void MachineCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
129 10899 : AU.setPreservesCFG();
130 : AU.addPreserved<MachineDominatorTree>();
131 : AU.addRequired<MachineLoopInfo>();
132 : AU.addPreserved<MachineLoopInfo>();
133 : AU.addRequired<MachineTraceMetrics>();
134 : AU.addPreserved<MachineTraceMetrics>();
135 10899 : MachineFunctionPass::getAnalysisUsage(AU);
136 10899 : }
137 :
138 0 : MachineInstr *MachineCombiner::getOperandDef(const MachineOperand &MO) {
139 : MachineInstr *DefInstr = nullptr;
140 : // We need a virtual register definition.
141 0 : if (MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg()))
142 0 : DefInstr = MRI->getUniqueVRegDef(MO.getReg());
143 : // PHI's have no depth etc.
144 0 : if (DefInstr && DefInstr->isPHI())
145 : DefInstr = nullptr;
146 0 : return DefInstr;
147 : }
148 :
149 : /// Computes depth of instructions in vector \InsInstr.
150 : ///
151 : /// \param InsInstrs is a vector of machine instructions
152 : /// \param InstrIdxForVirtReg is a dense map of virtual register to index
153 : /// of defining machine instruction in \p InsInstrs
154 : /// \param BlockTrace is a trace of machine instructions
155 : ///
156 : /// \returns Depth of last instruction in \InsInstrs ("NewRoot")
157 : unsigned
158 0 : MachineCombiner::getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
159 : DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
160 : MachineTraceMetrics::Trace BlockTrace) {
161 : SmallVector<unsigned, 16> InstrDepth;
162 : assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
163 : "Missing machine model\n");
164 :
165 : // For each instruction in the new sequence compute the depth based on the
166 : // operands. Use the trace information when possible. For new operands which
167 : // are tracked in the InstrIdxForVirtReg map depth is looked up in InstrDepth
168 0 : for (auto *InstrPtr : InsInstrs) { // for each Use
169 0 : unsigned IDepth = 0;
170 0 : for (const MachineOperand &MO : InstrPtr->operands()) {
171 : // Check for virtual register operand.
172 0 : if (!(MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg())))
173 0 : continue;
174 0 : if (!MO.isUse())
175 0 : continue;
176 : unsigned DepthOp = 0;
177 : unsigned LatencyOp = 0;
178 : DenseMap<unsigned, unsigned>::iterator II =
179 0 : InstrIdxForVirtReg.find(MO.getReg());
180 0 : if (II != InstrIdxForVirtReg.end()) {
181 : // Operand is new virtual register not in trace
182 : assert(II->second < InstrDepth.size() && "Bad Index");
183 0 : MachineInstr *DefInstr = InsInstrs[II->second];
184 : assert(DefInstr &&
185 : "There must be a definition for a new virtual register");
186 0 : DepthOp = InstrDepth[II->second];
187 0 : int DefIdx = DefInstr->findRegisterDefOperandIdx(MO.getReg());
188 0 : int UseIdx = InstrPtr->findRegisterUseOperandIdx(MO.getReg());
189 0 : LatencyOp = TSchedModel.computeOperandLatency(DefInstr, DefIdx,
190 : InstrPtr, UseIdx);
191 : } else {
192 0 : MachineInstr *DefInstr = getOperandDef(MO);
193 0 : if (DefInstr) {
194 0 : DepthOp = BlockTrace.getInstrCycles(*DefInstr).Depth;
195 0 : LatencyOp = TSchedModel.computeOperandLatency(
196 0 : DefInstr, DefInstr->findRegisterDefOperandIdx(MO.getReg()),
197 0 : InstrPtr, InstrPtr->findRegisterUseOperandIdx(MO.getReg()));
198 : }
199 : }
200 0 : IDepth = std::max(IDepth, DepthOp + LatencyOp);
201 : }
202 0 : InstrDepth.push_back(IDepth);
203 : }
204 0 : unsigned NewRootIdx = InsInstrs.size() - 1;
205 0 : return InstrDepth[NewRootIdx];
206 : }
207 :
208 : /// Computes instruction latency as max of latency of defined operands.
209 : ///
210 : /// \param Root is a machine instruction that could be replaced by NewRoot.
211 : /// It is used to compute a more accurate latency information for NewRoot in
212 : /// case there is a dependent instruction in the same trace (\p BlockTrace)
213 : /// \param NewRoot is the instruction for which the latency is computed
214 : /// \param BlockTrace is a trace of machine instructions
215 : ///
216 : /// \returns Latency of \p NewRoot
217 400 : unsigned MachineCombiner::getLatency(MachineInstr *Root, MachineInstr *NewRoot,
218 : MachineTraceMetrics::Trace BlockTrace) {
219 : assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
220 : "Missing machine model\n");
221 :
222 : // Check each definition in NewRoot and compute the latency
223 400 : unsigned NewRootLatency = 0;
224 :
225 1728 : for (const MachineOperand &MO : NewRoot->operands()) {
226 : // Check for virtual register operand.
227 1328 : if (!(MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg())))
228 928 : continue;
229 1280 : if (!MO.isDef())
230 : continue;
231 : // Get the first instruction that uses MO
232 400 : MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(MO.getReg());
233 : RI++;
234 400 : MachineInstr *UseMO = RI->getParent();
235 400 : unsigned LatencyOp = 0;
236 400 : if (UseMO && BlockTrace.isDepInTrace(*Root, *UseMO)) {
237 399 : LatencyOp = TSchedModel.computeOperandLatency(
238 399 : NewRoot, NewRoot->findRegisterDefOperandIdx(MO.getReg()), UseMO,
239 399 : UseMO->findRegisterUseOperandIdx(MO.getReg()));
240 : } else {
241 1 : LatencyOp = TSchedModel.computeInstrLatency(NewRoot);
242 : }
243 400 : NewRootLatency = std::max(NewRootLatency, LatencyOp);
244 : }
245 400 : return NewRootLatency;
246 : }
247 :
248 : /// The combiner's goal may differ based on which pattern it is attempting
249 : /// to optimize.
250 : enum class CombinerObjective {
251 : MustReduceDepth, // The data dependency chain must be improved.
252 : Default // The critical path must not be lengthened.
253 : };
254 :
255 : static CombinerObjective getCombinerObjective(MachineCombinerPattern P) {
256 : // TODO: If C++ ever gets a real enum class, make this part of the
257 : // MachineCombinerPattern class.
258 883 : switch (P) {
259 : case MachineCombinerPattern::REASSOC_AX_BY:
260 : case MachineCombinerPattern::REASSOC_AX_YB:
261 : case MachineCombinerPattern::REASSOC_XA_BY:
262 : case MachineCombinerPattern::REASSOC_XA_YB:
263 : return CombinerObjective::MustReduceDepth;
264 : default:
265 : return CombinerObjective::Default;
266 : }
267 : }
268 :
269 : /// Estimate the latency of the new and original instruction sequence by summing
270 : /// up the latencies of the inserted and deleted instructions. This assumes
271 : /// that the inserted and deleted instructions are dependent instruction chains,
272 : /// which might not hold in all cases.
273 400 : std::pair<unsigned, unsigned> MachineCombiner::getLatenciesForInstrSequences(
274 : MachineInstr &MI, SmallVectorImpl<MachineInstr *> &InsInstrs,
275 : SmallVectorImpl<MachineInstr *> &DelInstrs,
276 : MachineTraceMetrics::Trace BlockTrace) {
277 : assert(!InsInstrs.empty() && "Only support sequences that insert instrs.");
278 : unsigned NewRootLatency = 0;
279 : // NewRoot is the last instruction in the \p InsInstrs vector.
280 400 : MachineInstr *NewRoot = InsInstrs.back();
281 1512 : for (unsigned i = 0; i < InsInstrs.size() - 1; i++)
282 712 : NewRootLatency += TSchedModel.computeInstrLatency(InsInstrs[i]);
283 400 : NewRootLatency += getLatency(&MI, NewRoot, BlockTrace);
284 :
285 : unsigned RootLatency = 0;
286 1200 : for (auto I : DelInstrs)
287 800 : RootLatency += TSchedModel.computeInstrLatency(I);
288 :
289 400 : return {NewRootLatency, RootLatency};
290 : }
291 :
292 : /// The DAGCombine code sequence ends in MI (Machine Instruction) Root.
293 : /// The new code sequence ends in MI NewRoot. A necessary condition for the new
294 : /// sequence to replace the old sequence is that it cannot lengthen the critical
295 : /// path. The definition of "improve" may be restricted by specifying that the
296 : /// new path improves the data dependency chain (MustReduceDepth).
297 883 : bool MachineCombiner::improvesCriticalPathLen(
298 : MachineBasicBlock *MBB, MachineInstr *Root,
299 : MachineTraceMetrics::Trace BlockTrace,
300 : SmallVectorImpl<MachineInstr *> &InsInstrs,
301 : SmallVectorImpl<MachineInstr *> &DelInstrs,
302 : DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
303 : MachineCombinerPattern Pattern,
304 : bool SlackIsAccurate) {
305 : assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
306 : "Missing machine model\n");
307 : // Get depth and latency of NewRoot and Root.
308 883 : unsigned NewRootDepth = getDepth(InsInstrs, InstrIdxForVirtReg, BlockTrace);
309 883 : unsigned RootDepth = BlockTrace.getInstrCycles(*Root).Depth;
310 :
311 : LLVM_DEBUG(dbgs() << " Dependence data for " << *Root << "\tNewRootDepth: "
312 : << NewRootDepth << "\tRootDepth: " << RootDepth);
313 :
314 : // For a transform such as reassociation, the cost equation is
315 : // conservatively calculated so that we must improve the depth (data
316 : // dependency cycles) in the critical path to proceed with the transform.
317 : // Being conservative also protects against inaccuracies in the underlying
318 : // machine trace metrics and CPU models.
319 : if (getCombinerObjective(Pattern) == CombinerObjective::MustReduceDepth) {
320 : LLVM_DEBUG(dbgs() << "\tIt MustReduceDepth ");
321 : LLVM_DEBUG(NewRootDepth < RootDepth
322 : ? dbgs() << "\t and it does it\n"
323 : : dbgs() << "\t but it does NOT do it\n");
324 841 : return NewRootDepth < RootDepth;
325 : }
326 :
327 : // A more flexible cost calculation for the critical path includes the slack
328 : // of the original code sequence. This may allow the transform to proceed
329 : // even if the instruction depths (data dependency cycles) become worse.
330 :
331 : // Account for the latency of the inserted and deleted instructions by
332 : unsigned NewRootLatency, RootLatency;
333 : std::tie(NewRootLatency, RootLatency) =
334 42 : getLatenciesForInstrSequences(*Root, InsInstrs, DelInstrs, BlockTrace);
335 :
336 42 : unsigned RootSlack = BlockTrace.getInstrSlack(*Root);
337 42 : unsigned NewCycleCount = NewRootDepth + NewRootLatency;
338 42 : unsigned OldCycleCount =
339 42 : RootDepth + RootLatency + (SlackIsAccurate ? RootSlack : 0);
340 : LLVM_DEBUG(dbgs() << "\n\tNewRootLatency: " << NewRootLatency
341 : << "\tRootLatency: " << RootLatency << "\n\tRootSlack: "
342 : << RootSlack << " SlackIsAccurate=" << SlackIsAccurate
343 : << "\n\tNewRootDepth + NewRootLatency = " << NewCycleCount
344 : << "\n\tRootDepth + RootLatency + RootSlack = "
345 : << OldCycleCount;);
346 : LLVM_DEBUG(NewCycleCount <= OldCycleCount
347 : ? dbgs() << "\n\t It IMPROVES PathLen because"
348 : : dbgs() << "\n\t It DOES NOT improve PathLen because");
349 : LLVM_DEBUG(dbgs() << "\n\t\tNewCycleCount = " << NewCycleCount
350 : << ", OldCycleCount = " << OldCycleCount << "\n");
351 :
352 42 : return NewCycleCount <= OldCycleCount;
353 : }
354 :
355 : /// helper routine to convert instructions into SC
356 584 : void MachineCombiner::instr2instrSC(
357 : SmallVectorImpl<MachineInstr *> &Instrs,
358 : SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC) {
359 1722 : for (auto *InstrPtr : Instrs) {
360 1138 : unsigned Opc = InstrPtr->getOpcode();
361 1138 : unsigned Idx = TII->get(Opc).getSchedClass();
362 1138 : const MCSchedClassDesc *SC = SchedModel.getSchedClassDesc(Idx);
363 1138 : InstrsSC.push_back(SC);
364 : }
365 584 : }
366 :
367 : /// True when the new instructions do not increase resource length
368 322 : bool MachineCombiner::preservesResourceLen(
369 : MachineBasicBlock *MBB, MachineTraceMetrics::Trace BlockTrace,
370 : SmallVectorImpl<MachineInstr *> &InsInstrs,
371 : SmallVectorImpl<MachineInstr *> &DelInstrs) {
372 322 : if (!TSchedModel.hasInstrSchedModel())
373 : return true;
374 :
375 : // Compute current resource length
376 :
377 : //ArrayRef<const MachineBasicBlock *> MBBarr(MBB);
378 : SmallVector <const MachineBasicBlock *, 1> MBBarr;
379 292 : MBBarr.push_back(MBB);
380 292 : unsigned ResLenBeforeCombine = BlockTrace.getResourceLength(MBBarr);
381 :
382 : // Deal with SC rather than Instructions.
383 : SmallVector<const MCSchedClassDesc *, 16> InsInstrsSC;
384 : SmallVector<const MCSchedClassDesc *, 16> DelInstrsSC;
385 :
386 292 : instr2instrSC(InsInstrs, InsInstrsSC);
387 292 : instr2instrSC(DelInstrs, DelInstrsSC);
388 :
389 292 : ArrayRef<const MCSchedClassDesc *> MSCInsArr = makeArrayRef(InsInstrsSC);
390 292 : ArrayRef<const MCSchedClassDesc *> MSCDelArr = makeArrayRef(DelInstrsSC);
391 :
392 : // Compute new resource length.
393 : unsigned ResLenAfterCombine =
394 292 : BlockTrace.getResourceLength(MBBarr, MSCInsArr, MSCDelArr);
395 :
396 : LLVM_DEBUG(dbgs() << "\t\tResource length before replacement: "
397 : << ResLenBeforeCombine
398 : << " and after: " << ResLenAfterCombine << "\n";);
399 : LLVM_DEBUG(
400 : ResLenAfterCombine <= ResLenBeforeCombine
401 : ? dbgs() << "\t\t As result it IMPROVES/PRESERVES Resource Length\n"
402 : : dbgs() << "\t\t As result it DOES NOT improve/preserve Resource "
403 : "Length\n");
404 :
405 292 : return ResLenAfterCombine <= ResLenBeforeCombine;
406 : }
407 :
408 : /// \returns true when new instruction sequence should be generated
409 : /// independent if it lengthens critical path or not
410 : bool MachineCombiner::doSubstitute(unsigned NewSize, unsigned OldSize) {
411 3277 : if (OptSize && (NewSize < OldSize))
412 : return true;
413 3237 : if (!TSchedModel.hasInstrSchedModelOrItineraries())
414 : return true;
415 : return false;
416 : }
417 :
418 : /// Inserts InsInstrs and deletes DelInstrs. Incrementally updates instruction
419 : /// depths if requested.
420 : ///
421 : /// \param MBB basic block to insert instructions in
422 : /// \param MI current machine instruction
423 : /// \param InsInstrs new instructions to insert in \p MBB
424 : /// \param DelInstrs instruction to delete from \p MBB
425 : /// \param MinInstr is a pointer to the machine trace information
426 : /// \param RegUnits set of live registers, needed to compute instruction depths
427 : /// \param IncrementalUpdate if true, compute instruction depths incrementally,
428 : /// otherwise invalidate the trace
429 2740 : static void insertDeleteInstructions(MachineBasicBlock *MBB, MachineInstr &MI,
430 : SmallVector<MachineInstr *, 16> InsInstrs,
431 : SmallVector<MachineInstr *, 16> DelInstrs,
432 : MachineTraceMetrics::Ensemble *MinInstr,
433 : SparseSet<LiveRegUnit> &RegUnits,
434 : bool IncrementalUpdate) {
435 7980 : for (auto *InstrPtr : InsInstrs)
436 : MBB->insert((MachineBasicBlock::iterator)&MI, InstrPtr);
437 :
438 8220 : for (auto *InstrPtr : DelInstrs) {
439 5480 : InstrPtr->eraseFromParentAndMarkDBGValuesForRemoval();
440 : // Erase all LiveRegs defined by the removed instruction
441 5858 : for (auto I = RegUnits.begin(); I != RegUnits.end(); ) {
442 378 : if (I->MI == InstrPtr)
443 0 : I = RegUnits.erase(I);
444 : else
445 378 : I++;
446 : }
447 : }
448 :
449 2740 : if (IncrementalUpdate)
450 340 : for (auto *InstrPtr : InsInstrs)
451 226 : MinInstr->updateDepth(MBB, *InstrPtr, RegUnits);
452 : else
453 2626 : MinInstr->invalidate(MBB);
454 :
455 : NumInstCombined++;
456 2740 : }
457 :
458 : // Check that the difference between original and new latency is decreasing for
459 : // later patterns. This helps to discover sub-optimal pattern orderings.
460 186 : void MachineCombiner::verifyPatternOrder(
461 : MachineBasicBlock *MBB, MachineInstr &Root,
462 : SmallVector<MachineCombinerPattern, 16> &Patterns) {
463 : long PrevLatencyDiff = std::numeric_limits<long>::max();
464 : (void)PrevLatencyDiff; // Variable is used in assert only.
465 544 : for (auto P : Patterns) {
466 : SmallVector<MachineInstr *, 16> InsInstrs;
467 : SmallVector<MachineInstr *, 16> DelInstrs;
468 : DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
469 716 : TII->genAlternativeCodeSequence(Root, P, InsInstrs, DelInstrs,
470 358 : InstrIdxForVirtReg);
471 : // Found pattern, but did not generate alternative sequence.
472 : // This can happen e.g. when an immediate could not be materialized
473 : // in a single instruction.
474 358 : if (InsInstrs.empty() || !TSchedModel.hasInstrSchedModelOrItineraries())
475 : continue;
476 :
477 : unsigned NewRootLatency, RootLatency;
478 358 : std::tie(NewRootLatency, RootLatency) = getLatenciesForInstrSequences(
479 358 : Root, InsInstrs, DelInstrs, MinInstr->getTrace(MBB));
480 : long CurrentLatencyDiff = ((long)RootLatency) - ((long)NewRootLatency);
481 : assert(CurrentLatencyDiff <= PrevLatencyDiff &&
482 : "Current pattern is better than previous pattern.");
483 : PrevLatencyDiff = CurrentLatencyDiff;
484 : }
485 186 : }
486 :
487 : /// Substitute a slow code sequence with a faster one by
488 : /// evaluating instruction combining pattern.
489 : /// The prototype of such a pattern is MUl + ADD -> MADD. Performs instruction
490 : /// combining based on machine trace metrics. Only combine a sequence of
491 : /// instructions when this neither lengthens the critical path nor increases
492 : /// resource pressure. When optimizing for codesize always combine when the new
493 : /// sequence is shorter.
494 347344 : bool MachineCombiner::combineInstructions(MachineBasicBlock *MBB) {
495 : bool Changed = false;
496 : LLVM_DEBUG(dbgs() << "Combining MBB " << MBB->getName() << "\n");
497 :
498 : bool IncrementalUpdate = false;
499 : auto BlockIter = MBB->begin();
500 : decltype(BlockIter) LastUpdate;
501 : // Check if the block is in a loop.
502 347344 : const MachineLoop *ML = MLI->getLoopFor(MBB);
503 347344 : if (!MinInstr)
504 134441 : MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
505 :
506 347344 : SparseSet<LiveRegUnit> RegUnits;
507 347344 : RegUnits.setUniverse(TRI->getNumRegUnits());
508 :
509 3931561 : while (BlockIter != MBB->end()) {
510 : auto &MI = *BlockIter++;
511 : SmallVector<MachineCombinerPattern, 16> Patterns;
512 : // The motivating example is:
513 : //
514 : // MUL Other MUL_op1 MUL_op2 Other
515 : // \ / \ | /
516 : // ADD/SUB => MADD/MSUB
517 : // (=Root) (=NewRoot)
518 :
519 : // The DAGCombine code always replaced MUL + ADD/SUB by MADD. While this is
520 : // usually beneficial for code size it unfortunately can hurt performance
521 : // when the ADD is on the critical path, but the MUL is not. With the
522 : // substitution the MUL becomes part of the critical path (in form of the
523 : // MADD) and can lengthen it on architectures where the MADD latency is
524 : // longer than the ADD latency.
525 : //
526 : // For each instruction we check if it can be the root of a combiner
527 : // pattern. Then for each pattern the new code sequence in form of MI is
528 : // generated and evaluated. When the efficiency criteria (don't lengthen
529 : // critical path, don't use more resources) is met the new sequence gets
530 : // hooked up into the basic block before the old sequence is removed.
531 : //
532 : // The algorithm does not try to evaluate all patterns and pick the best.
533 : // This is only an artificial restriction though. In practice there is
534 : // mostly one pattern, and getMachineCombinerPatterns() can order patterns
535 : // based on an internal cost heuristic. If
536 : // machine-combiner-verify-pattern-order is enabled, all patterns are
537 : // checked to ensure later patterns do not provide better latency savings.
538 :
539 3584217 : if (!TII->getMachineCombinerPatterns(MI, Patterns))
540 : continue;
541 :
542 2927 : if (VerifyPatternOrder)
543 186 : verifyPatternOrder(MBB, MI, Patterns);
544 :
545 3489 : for (auto P : Patterns) {
546 : SmallVector<MachineInstr *, 16> InsInstrs;
547 : SmallVector<MachineInstr *, 16> DelInstrs;
548 : DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
549 6604 : TII->genAlternativeCodeSequence(MI, P, InsInstrs, DelInstrs,
550 3302 : InstrIdxForVirtReg);
551 3302 : unsigned NewInstCount = InsInstrs.size();
552 3302 : unsigned OldInstCount = DelInstrs.size();
553 : // Found pattern, but did not generate alternative sequence.
554 : // This can happen e.g. when an immediate could not be materialized
555 : // in a single instruction.
556 3302 : if (!NewInstCount)
557 : continue;
558 :
559 : LLVM_DEBUG(if (dump_intrs) {
560 : dbgs() << "\tFor the Pattern (" << (int)P << ") these instructions could be removed\n";
561 : for (auto const *InstrPtr : DelInstrs) {
562 : dbgs() << "\t\t" << STI->getSchedInfoStr(*InstrPtr) << ": ";
563 : InstrPtr->print(dbgs(), false, false, false, TII);
564 : }
565 : dbgs() << "\tThese instructions could replace the removed ones\n";
566 : for (auto const *InstrPtr : InsInstrs) {
567 : dbgs() << "\t\t" << STI->getSchedInfoStr(*InstrPtr) << ": ";
568 : InstrPtr->print(dbgs(), false, false, false, TII);
569 : }
570 : });
571 :
572 : bool SubstituteAlways = false;
573 3301 : if (ML && TII->isThroughputPattern(P))
574 : SubstituteAlways = true;
575 :
576 3301 : if (IncrementalUpdate) {
577 : // Update depths since the last incremental update.
578 68 : MinInstr->updateDepths(LastUpdate, BlockIter, RegUnits);
579 68 : LastUpdate = BlockIter;
580 : }
581 :
582 : // Substitute when we optimize for codesize and the new sequence has
583 : // fewer instructions OR
584 : // the new sequence neither lengthens the critical path nor increases
585 : // resource pressure.
586 3301 : if (SubstituteAlways || doSubstitute(NewInstCount, OldInstCount)) {
587 7254 : insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
588 : RegUnits, IncrementalUpdate);
589 : // Eagerly stop after the first pattern fires.
590 : Changed = true;
591 2418 : break;
592 : } else {
593 : // For big basic blocks, we only compute the full trace the first time
594 : // we hit this. We do not invalidate the trace, but instead update the
595 : // instruction depths incrementally.
596 : // NOTE: Only the instruction depths up to MI are accurate. All other
597 : // trace information is not updated.
598 883 : MachineTraceMetrics::Trace BlockTrace = MinInstr->getTrace(MBB);
599 883 : Traces->verifyAnalysis();
600 883 : if (improvesCriticalPathLen(MBB, &MI, BlockTrace, InsInstrs, DelInstrs,
601 : InstrIdxForVirtReg, P,
602 1205 : !IncrementalUpdate) &&
603 322 : preservesResourceLen(MBB, BlockTrace, InsInstrs, DelInstrs)) {
604 322 : if (MBB->size() > inc_threshold) {
605 : // Use incremental depth updates for basic blocks above treshold
606 : IncrementalUpdate = true;
607 114 : LastUpdate = BlockIter;
608 : }
609 :
610 966 : insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
611 : RegUnits, IncrementalUpdate);
612 :
613 : // Eagerly stop after the first pattern fires.
614 : Changed = true;
615 322 : break;
616 : }
617 : // Cleanup instructions of the alternative code sequence. There is no
618 : // use for them.
619 561 : MachineFunction *MF = MBB->getParent();
620 1683 : for (auto *InstrPtr : InsInstrs)
621 1122 : MF->DeleteMachineInstr(InstrPtr);
622 : }
623 561 : InstrIdxForVirtReg.clear();
624 : }
625 : }
626 :
627 347344 : if (Changed && IncrementalUpdate)
628 78 : Traces->invalidate(MBB);
629 347344 : return Changed;
630 : }
631 :
632 134441 : bool MachineCombiner::runOnMachineFunction(MachineFunction &MF) {
633 134441 : STI = &MF.getSubtarget();
634 134441 : TII = STI->getInstrInfo();
635 134441 : TRI = STI->getRegisterInfo();
636 134441 : SchedModel = STI->getSchedModel();
637 134441 : TSchedModel.init(STI);
638 134441 : MRI = &MF.getRegInfo();
639 134441 : MLI = &getAnalysis<MachineLoopInfo>();
640 134441 : Traces = &getAnalysis<MachineTraceMetrics>();
641 134441 : MinInstr = nullptr;
642 134441 : OptSize = MF.getFunction().optForSize();
643 :
644 : LLVM_DEBUG(dbgs() << getPassName() << ": " << MF.getName() << '\n');
645 134441 : if (!TII->useMachineCombiner()) {
646 : LLVM_DEBUG(
647 : dbgs()
648 : << " Skipping pass: Target does not support machine combiner\n");
649 : return false;
650 : }
651 :
652 : bool Changed = false;
653 :
654 : // Try to combine instructions.
655 481785 : for (auto &MBB : MF)
656 347344 : Changed |= combineInstructions(&MBB);
657 :
658 : return Changed;
659 : }
|
