LLVM 24.0.0git
MachineCombiner.cpp
Go to the documentation of this file.
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
14#include "CodeGenOptions.h"
15#include "llvm/ADT/DenseMap.h"
16#include "llvm/ADT/Statistic.h"
35#include "llvm/Support/Debug.h"
37
38using namespace llvm;
39
40#define DEBUG_TYPE "machine-combiner"
41
42STATISTIC(NumInstCombined, "Number of machineinst combined");
43
44namespace {
45class MachineCombinerImpl {
46 const CodeGenOptions &Opts;
47 const TargetSubtargetInfo *STI = nullptr;
48 const TargetInstrInfo *TII = nullptr;
49 const TargetRegisterInfo *TRI = nullptr;
50 MCSchedModel SchedModel;
51 MachineRegisterInfo *MRI = nullptr;
52 MachineLoopInfo *MLI = nullptr; // Current MachineLoopInfo
53 MachineTraceMetrics *Traces = nullptr;
54 MachineTraceMetrics::Ensemble *TraceEnsemble = nullptr;
55 MachineBlockFrequencyInfo *MBFI = nullptr;
56 ProfileSummaryInfo *PSI = nullptr;
57 RegisterClassInfo *RegClassInfo = nullptr;
58
59 TargetSchedModel TSchedModel;
60
61public:
62 explicit MachineCombinerImpl(const CodeGenOptions &Opts) : Opts(Opts) {}
63 bool run(MachineFunction &MF, MachineLoopInfo *MLI,
64 MachineTraceMetrics *Traces, ProfileSummaryInfo *PSI,
65 MachineBlockFrequencyInfo *MBFI, RegisterClassInfo *RegClassInfo);
66
67private:
68 bool combineInstructions(MachineBasicBlock *);
69 MachineInstr *getOperandDef(const MachineOperand &MO);
70 bool isTransientMI(const MachineInstr *MI);
71 unsigned getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
72 DenseMap<Register, unsigned> &InstrIdxForVirtReg,
74 const MachineBasicBlock &MBB);
75 unsigned getLatency(MachineInstr *Root, MachineInstr *NewRoot,
77 bool improvesCriticalPathLen(MachineBasicBlock *MBB, MachineInstr *Root,
79 SmallVectorImpl<MachineInstr *> &InsInstrs,
80 SmallVectorImpl<MachineInstr *> &DelInstrs,
81 DenseMap<Register, unsigned> &InstrIdxForVirtReg,
82 unsigned Pattern, bool SlackIsAccurate);
83 bool reduceRegisterPressure(MachineInstr &Root, MachineBasicBlock *MBB,
84 SmallVectorImpl<MachineInstr *> &InsInstrs,
85 SmallVectorImpl<MachineInstr *> &DelInstrs,
86 unsigned Pattern);
87 bool preservesResourceLen(MachineBasicBlock *MBB,
89 SmallVectorImpl<MachineInstr *> &InsInstrs,
90 SmallVectorImpl<MachineInstr *> &DelInstrs);
91 void instr2instrSC(SmallVectorImpl<MachineInstr *> &Instrs,
92 SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC);
93 std::pair<unsigned, unsigned>
94 getLatenciesForInstrSequences(MachineInstr &MI,
95 SmallVectorImpl<MachineInstr *> &InsInstrs,
96 SmallVectorImpl<MachineInstr *> &DelInstrs,
98
99 CombinerObjective getCombinerObjective(unsigned Pattern);
100};
101
102class MachineCombinerLegacy : public MachineFunctionPass {
103public:
104 static char ID;
105 MachineCombinerLegacy() : MachineFunctionPass(ID) {}
106 void getAnalysisUsage(AnalysisUsage &AU) const override;
107 bool runOnMachineFunction(MachineFunction &MF) override;
108 StringRef getPassName() const override { return "Machine InstCombiner"; }
109};
110} // namespace
111
112char MachineCombinerLegacy::ID = 0;
113char &llvm::MachineCombinerID = MachineCombinerLegacy::ID;
114
115INITIALIZE_PASS_BEGIN(MachineCombinerLegacy, DEBUG_TYPE, "Machine InstCombiner",
116 false, false)
120INITIALIZE_PASS_END(MachineCombinerLegacy, DEBUG_TYPE, "Machine InstCombiner",
122
123void MachineCombinerLegacy::getAnalysisUsage(AnalysisUsage &AU) const {
124 AU.setPreservesCFG();
125 AU.addRequired<MachineLoopInfoWrapperPass>();
126 AU.addRequired<MachineRegisterClassInfoWrapperPass>();
127 AU.addRequired<MachineTraceMetricsWrapperPass>();
128 AU.addPreserved<MachineTraceMetricsWrapperPass>();
129 AU.addRequired<LazyMachineBlockFrequencyInfoPass>();
130 AU.addRequired<ProfileSummaryInfoWrapperPass>();
132}
133
134MachineInstr *MachineCombinerImpl::getOperandDef(const MachineOperand &MO) {
135 MachineInstr *DefInstr = nullptr;
136 // We need a virtual register definition.
137 if (MO.isReg() && MO.getReg().isVirtual())
138 DefInstr = MRI->getUniqueVRegDef(MO.getReg());
139 return DefInstr;
140}
141
142/// Return true if MI is unlikely to generate an actual target instruction.
143bool MachineCombinerImpl::isTransientMI(const MachineInstr *MI) {
144 if (!MI->isCopy())
145 return MI->isTransient();
146
147 // If MI is a COPY, check if its src and dst registers can be coalesced.
148 Register Dst = MI->getOperand(0).getReg();
149 Register Src = MI->getOperand(1).getReg();
150
151 if (!MI->isFullCopy()) {
152 // If src RC contains super registers of dst RC, it can also be coalesced.
153 if (MI->getOperand(0).getSubReg() || Src.isPhysical() || Dst.isPhysical())
154 return false;
155
156 auto SrcSub = MI->getOperand(1).getSubReg();
157 auto SrcRC = MRI->getRegClass(Src);
158 auto DstRC = MRI->getRegClass(Dst);
159 return TRI->getMatchingSuperRegClass(SrcRC, DstRC, SrcSub) != nullptr;
160 }
161
162 if (Src.isPhysical() && Dst.isPhysical())
163 return Src == Dst;
164
165 if (Src.isVirtual() && Dst.isVirtual()) {
166 auto SrcRC = MRI->getRegClass(Src);
167 auto DstRC = MRI->getRegClass(Dst);
168 return SrcRC->hasSuperClassEq(DstRC) || SrcRC->hasSubClassEq(DstRC);
169 }
170
171 if (Src.isVirtual())
172 std::swap(Src, Dst);
173
174 // Now Src is physical register, Dst is virtual register.
175 auto DstRC = MRI->getRegClass(Dst);
176 return DstRC->contains(Src);
177}
178
179/// Computes depth of instructions in vector \InsInstr.
180///
181/// \param InsInstrs is a vector of machine instructions
182/// \param InstrIdxForVirtReg is a dense map of virtual register to index
183/// of defining machine instruction in \p InsInstrs
184/// \param BlockTrace is a trace of machine instructions
185///
186/// \returns Depth of last instruction in \InsInstrs ("NewRoot")
187unsigned
188MachineCombinerImpl::getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
189 DenseMap<Register, unsigned> &InstrIdxForVirtReg,
191 const MachineBasicBlock &MBB) {
192 SmallVector<unsigned, 16> InstrDepth;
193 // For each instruction in the new sequence compute the depth based on the
194 // operands. Use the trace information when possible. For new operands which
195 // are tracked in the InstrIdxForVirtReg map depth is looked up in InstrDepth
196 for (auto *InstrPtr : InsInstrs) { // for each Use
197 unsigned IDepth = 0;
198 for (const MachineOperand &MO : InstrPtr->all_uses()) {
199 // Check for virtual register operand.
200 if (!MO.getReg().isVirtual())
201 continue;
202 unsigned DepthOp = 0;
203 unsigned LatencyOp = 0;
204 auto II = InstrIdxForVirtReg.find(MO.getReg());
205 if (II != InstrIdxForVirtReg.end()) {
206 // Operand is new virtual register not in trace
207 assert(II->second < InstrDepth.size() && "Bad Index");
208 MachineInstr *DefInstr = InsInstrs[II->second];
209 assert(DefInstr &&
210 "There must be a definition for a new virtual register");
211 DepthOp = InstrDepth[II->second];
212 int DefIdx =
213 DefInstr->findRegisterDefOperandIdx(MO.getReg(), /*TRI=*/nullptr);
214 int UseIdx =
215 InstrPtr->findRegisterUseOperandIdx(MO.getReg(), /*TRI=*/nullptr);
216 LatencyOp = TSchedModel.computeOperandLatency(DefInstr, DefIdx,
217 InstrPtr, UseIdx);
218 } else {
219 MachineInstr *DefInstr = getOperandDef(MO);
220 if (DefInstr && (TII->getMachineCombinerTraceStrategy() !=
221 MachineTraceStrategy::TS_Local ||
222 DefInstr->getParent() == &MBB)) {
223 DepthOp = BlockTrace.getInstrCycles(*DefInstr).Depth;
224 if (!isTransientMI(DefInstr))
225 LatencyOp = TSchedModel.computeOperandLatency(
226 DefInstr,
227 DefInstr->findRegisterDefOperandIdx(MO.getReg(),
228 /*TRI=*/nullptr),
229 InstrPtr,
230 InstrPtr->findRegisterUseOperandIdx(MO.getReg(),
231 /*TRI=*/nullptr));
232 }
233 }
234 IDepth = std::max(IDepth, DepthOp + LatencyOp);
235 }
236 InstrDepth.push_back(IDepth);
237 }
238 unsigned NewRootIdx = InsInstrs.size() - 1;
239 return InstrDepth[NewRootIdx];
240}
241
242/// Computes instruction latency as max of latency of defined operands.
243///
244/// \param Root is a machine instruction that could be replaced by NewRoot.
245/// It is used to compute a more accurate latency information for NewRoot in
246/// case there is a dependent instruction in the same trace (\p BlockTrace)
247/// \param NewRoot is the instruction for which the latency is computed
248/// \param BlockTrace is a trace of machine instructions
249///
250/// \returns Latency of \p NewRoot
251unsigned
252MachineCombinerImpl::getLatency(MachineInstr *Root, MachineInstr *NewRoot,
253 MachineTraceMetrics::Trace BlockTrace) {
254 // Check each definition in NewRoot and compute the latency
255 unsigned NewRootLatency = 0;
256
257 for (const MachineOperand &MO : NewRoot->all_defs()) {
258 // Check for virtual register operand.
259 if (!MO.getReg().isVirtual())
260 continue;
261 // Get the first instruction that uses MO
263 RI++;
264 if (RI == MRI->reg_end())
265 continue;
266 MachineInstr *UseMO = RI->getParent();
267 unsigned LatencyOp = 0;
268 if (UseMO && BlockTrace.isDepInTrace(*Root, *UseMO)) {
269 LatencyOp = TSchedModel.computeOperandLatency(
270 NewRoot,
271 NewRoot->findRegisterDefOperandIdx(MO.getReg(), /*TRI=*/nullptr),
272 UseMO,
273 UseMO->findRegisterUseOperandIdx(MO.getReg(), /*TRI=*/nullptr));
274 } else {
275 LatencyOp = TSchedModel.computeInstrLatency(NewRoot);
276 }
277 NewRootLatency = std::max(NewRootLatency, LatencyOp);
278 }
279 return NewRootLatency;
280}
281
282CombinerObjective MachineCombinerImpl::getCombinerObjective(unsigned Pattern) {
283 // TODO: If C++ ever gets a real enum class, make this part of the
284 // MachineCombinerPattern class.
285 switch (Pattern) {
286 case MachineCombinerPattern::REASSOC_AX_BY:
287 case MachineCombinerPattern::REASSOC_AX_YB:
288 case MachineCombinerPattern::REASSOC_XA_BY:
289 case MachineCombinerPattern::REASSOC_XA_YB:
290 return CombinerObjective::MustReduceDepth;
291 default:
292 return TII->getCombinerObjective(Pattern);
293 }
294}
295
296/// Estimate the latency of the new and original instruction sequence by summing
297/// up the latencies of the inserted and deleted instructions. This assumes
298/// that the inserted and deleted instructions are dependent instruction chains,
299/// which might not hold in all cases.
300std::pair<unsigned, unsigned>
301MachineCombinerImpl::getLatenciesForInstrSequences(
302 MachineInstr &MI, SmallVectorImpl<MachineInstr *> &InsInstrs,
303 SmallVectorImpl<MachineInstr *> &DelInstrs,
304 MachineTraceMetrics::Trace BlockTrace) {
305 assert(!InsInstrs.empty() && "Only support sequences that insert instrs.");
306 unsigned NewRootLatency = 0;
307 // NewRoot is the last instruction in the \p InsInstrs vector.
308 MachineInstr *NewRoot = InsInstrs.back();
309 for (unsigned i = 0; i < InsInstrs.size() - 1; i++)
310 NewRootLatency += TSchedModel.computeInstrLatency(InsInstrs[i]);
311 NewRootLatency += getLatency(&MI, NewRoot, BlockTrace);
312
313 unsigned RootLatency = 0;
314 for (auto *I : DelInstrs)
315 RootLatency += TSchedModel.computeInstrLatency(I);
316
317 return {NewRootLatency, RootLatency};
318}
319
320bool MachineCombinerImpl::reduceRegisterPressure(
321 MachineInstr &Root, MachineBasicBlock *MBB,
322 SmallVectorImpl<MachineInstr *> &InsInstrs,
323 SmallVectorImpl<MachineInstr *> &DelInstrs, unsigned Pattern) {
324 // FIXME: for now, we don't do any check for the register pressure patterns.
325 // We treat them as always profitable. But we can do better if we make
326 // RegPressureTracker class be aware of TIE attribute. Then we can get an
327 // accurate compare of register pressure with DelInstrs or InsInstrs.
328 return true;
329}
330
331/// The DAGCombine code sequence ends in MI (Machine Instruction) Root.
332/// The new code sequence ends in MI NewRoot. A necessary condition for the new
333/// sequence to replace the old sequence is that it cannot lengthen the critical
334/// path. The definition of "improve" may be restricted by specifying that the
335/// new path improves the data dependency chain (MustReduceDepth).
336bool MachineCombinerImpl::improvesCriticalPathLen(
337 MachineBasicBlock *MBB, MachineInstr *Root,
339 SmallVectorImpl<MachineInstr *> &InsInstrs,
340 SmallVectorImpl<MachineInstr *> &DelInstrs,
341 DenseMap<Register, unsigned> &InstrIdxForVirtReg, unsigned Pattern,
342 bool SlackIsAccurate) {
343 // Get depth and latency of NewRoot and Root.
344 unsigned NewRootDepth =
345 getDepth(InsInstrs, InstrIdxForVirtReg, BlockTrace, *MBB);
346 unsigned RootDepth = BlockTrace.getInstrCycles(*Root).Depth;
347
348 LLVM_DEBUG(dbgs() << " Dependence data for " << *Root << "\tNewRootDepth: "
349 << NewRootDepth << "\tRootDepth: " << RootDepth);
350
351 // For a transform such as reassociation, the cost equation is
352 // conservatively calculated so that we must improve the depth (data
353 // dependency cycles) in the critical path to proceed with the transform.
354 // Being conservative also protects against inaccuracies in the underlying
355 // machine trace metrics and CPU models.
356 if (getCombinerObjective(Pattern) == CombinerObjective::MustReduceDepth) {
357 LLVM_DEBUG(dbgs() << "\tIt MustReduceDepth ");
358 LLVM_DEBUG(NewRootDepth < RootDepth
359 ? dbgs() << "\t and it does it\n"
360 : dbgs() << "\t but it does NOT do it\n");
361 return NewRootDepth < RootDepth;
362 }
363
364 // A more flexible cost calculation for the critical path includes the slack
365 // of the original code sequence. This may allow the transform to proceed
366 // even if the instruction depths (data dependency cycles) become worse.
367
368 // Account for the latency of the inserted and deleted instructions by
369 unsigned NewRootLatency, RootLatency;
370 if (TII->accumulateInstrSeqToRootLatency(*Root)) {
371 std::tie(NewRootLatency, RootLatency) =
372 getLatenciesForInstrSequences(*Root, InsInstrs, DelInstrs, BlockTrace);
373 } else {
374 NewRootLatency = TSchedModel.computeInstrLatency(InsInstrs.back());
375 RootLatency = TSchedModel.computeInstrLatency(Root);
376 }
377
378 unsigned RootSlack = BlockTrace.getInstrSlack(*Root);
379 unsigned NewCycleCount = NewRootDepth + NewRootLatency;
380 unsigned OldCycleCount =
381 RootDepth + RootLatency + (SlackIsAccurate ? RootSlack : 0);
382 LLVM_DEBUG(dbgs() << "\n\tNewRootLatency: " << NewRootLatency
383 << "\tRootLatency: " << RootLatency << "\n\tRootSlack: "
384 << RootSlack << " SlackIsAccurate=" << SlackIsAccurate
385 << "\n\tNewRootDepth + NewRootLatency = " << NewCycleCount
386 << "\n\tRootDepth + RootLatency + RootSlack = "
387 << OldCycleCount);
388 LLVM_DEBUG(NewCycleCount <= OldCycleCount
389 ? dbgs() << "\n\t It IMPROVES PathLen because"
390 : dbgs() << "\n\t It DOES NOT improve PathLen because");
391 LLVM_DEBUG(dbgs() << "\n\t\tNewCycleCount = " << NewCycleCount
392 << ", OldCycleCount = " << OldCycleCount << "\n");
393
394 return NewCycleCount <= OldCycleCount;
395}
396
397/// helper routine to convert instructions into SC
398void MachineCombinerImpl::instr2instrSC(
399 SmallVectorImpl<MachineInstr *> &Instrs,
400 SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC) {
401 for (auto *InstrPtr : Instrs) {
402 unsigned Opc = InstrPtr->getOpcode();
403 unsigned Idx = TII->get(Opc).getSchedClass();
404 const MCSchedClassDesc *SC = SchedModel.getSchedClassDesc(Idx);
405 InstrsSC.push_back(SC);
406 }
407}
408
409/// True when the new instructions do not increase resource length
410bool MachineCombinerImpl::preservesResourceLen(
411 MachineBasicBlock *MBB, MachineTraceMetrics::Trace BlockTrace,
412 SmallVectorImpl<MachineInstr *> &InsInstrs,
413 SmallVectorImpl<MachineInstr *> &DelInstrs) {
414 if (!TSchedModel.hasInstrSchedModel())
415 return true;
416
417 // Compute current resource length
418
419 // ArrayRef<const MachineBasicBlock *> MBBarr(MBB);
421 MBBarr.push_back(MBB);
422 unsigned ResLenBeforeCombine = BlockTrace.getResourceLength(MBBarr);
423
424 // Deal with SC rather than Instructions.
427
428 instr2instrSC(InsInstrs, InsInstrsSC);
429 instr2instrSC(DelInstrs, DelInstrsSC);
430
431 ArrayRef<const MCSchedClassDesc *> MSCInsArr{InsInstrsSC};
432 ArrayRef<const MCSchedClassDesc *> MSCDelArr{DelInstrsSC};
433
434 // Compute new resource length.
435 unsigned ResLenAfterCombine =
436 BlockTrace.getResourceLength(MBBarr, MSCInsArr, MSCDelArr);
437
438 LLVM_DEBUG(dbgs() << "\t\tResource length before replacement: "
439 << ResLenBeforeCombine
440 << " and after: " << ResLenAfterCombine << "\n");
442 ResLenAfterCombine <=
443 ResLenBeforeCombine + TII->getExtendResourceLenLimit()
444 ? dbgs() << "\t\t As result it IMPROVES/PRESERVES Resource Length\n"
445 : dbgs() << "\t\t As result it DOES NOT improve/preserve Resource "
446 "Length\n");
447
448 return ResLenAfterCombine <=
449 ResLenBeforeCombine + TII->getExtendResourceLenLimit();
450}
451
452/// Inserts InsInstrs and deletes DelInstrs. Incrementally updates instruction
453/// depths if requested.
454///
455/// \param MBB basic block to insert instructions in
456/// \param MI current machine instruction
457/// \param InsInstrs new instructions to insert in \p MBB
458/// \param DelInstrs instruction to delete from \p MBB
459/// \param TraceEnsemble is a pointer to the machine trace information
460/// \param RegUnits set of live registers, needed to compute instruction depths
461/// \param TII is target instruction info, used to call target hook
462/// \param Pattern is used to call target hook finalizeInsInstrs
463/// \param IncrementalUpdate if true, compute instruction depths incrementally,
464/// otherwise invalidate the trace
465static void
469 MachineTraceMetrics::Ensemble *TraceEnsemble,
470 LiveRegUnitSet &RegUnits, const TargetInstrInfo *TII,
471 unsigned Pattern, bool IncrementalUpdate) {
472 // If we want to fix up some placeholder for some target, do it now.
473 // We need this because in genAlternativeCodeSequence, we have not decided the
474 // better pattern InsInstrs or DelInstrs, so we don't want generate some
475 // sideeffect to the function. For example we need to delay the constant pool
476 // entry creation here after InsInstrs is selected as better pattern.
477 // Otherwise the constant pool entry created for InsInstrs will not be deleted
478 // even if InsInstrs is not the better pattern.
479 TII->finalizeInsInstrs(MI, Pattern, InsInstrs);
480
481 for (auto *InstrPtr : InsInstrs)
482 MBB->insert((MachineBasicBlock::iterator)&MI, InstrPtr);
483
484 for (auto *InstrPtr : DelInstrs) {
485 InstrPtr->eraseFromParent();
486 // Erase all LiveRegs defined by the removed instruction
487 for (auto *I = RegUnits.begin(); I != RegUnits.end();) {
488 if (I->MI == InstrPtr)
489 I = RegUnits.erase(I);
490 else
491 I++;
492 }
493 }
494
495 if (IncrementalUpdate)
496 for (auto *InstrPtr : InsInstrs)
497 TraceEnsemble->updateDepth(MBB, *InstrPtr, RegUnits);
498 else
499 TraceEnsemble->invalidate(MBB);
500
501 NumInstCombined++;
502}
503
504/// Substitute a slow code sequence with a faster one by
505/// evaluating instruction combining pattern.
506/// The prototype of such a pattern is MUl + ADD -> MADD. Performs instruction
507/// combining based on machine trace metrics. Only combine a sequence of
508/// instructions when this neither lengthens the critical path nor increases
509/// resource pressure. When optimizing for codesize always combine when the new
510/// sequence is shorter.
511bool MachineCombinerImpl::combineInstructions(MachineBasicBlock *MBB) {
512 bool Changed = false;
513 LLVM_DEBUG(dbgs() << "Combining MBB " << MBB->getName() << "\n");
514
515 bool IncrementalUpdate = false;
516 auto BlockIter = MBB->begin();
517 decltype(BlockIter) LastUpdate;
518 // Check if the block is in a loop.
519 const MachineLoop *ML = MLI->getLoopFor(MBB);
520 if (!TraceEnsemble)
521 TraceEnsemble = Traces->getEnsemble(TII->getMachineCombinerTraceStrategy());
522
523 LiveRegUnitSet RegUnits;
524 RegUnits.setUniverse(TRI->getNumRegUnits());
525
526 bool OptForSize = llvm::shouldOptimizeForSize(MBB, PSI, MBFI);
527
528 bool DoRegPressureReduce =
529 TII->shouldReduceRegisterPressure(MBB, RegClassInfo);
530
531 while (BlockIter != MBB->end()) {
532 auto &MI = *BlockIter++;
533 SmallVector<unsigned, 16> Patterns;
534 // The motivating example is:
535 //
536 // MUL Other MUL_op1 MUL_op2 Other
537 // \ / \ | /
538 // ADD/SUB => MADD/MSUB
539 // (=Root) (=NewRoot)
540
541 // The DAGCombine code always replaced MUL + ADD/SUB by MADD. While this is
542 // usually beneficial for code size it unfortunately can hurt performance
543 // when the ADD is on the critical path, but the MUL is not. With the
544 // substitution the MUL becomes part of the critical path (in form of the
545 // MADD) and can lengthen it on architectures where the MADD latency is
546 // longer than the ADD latency.
547 //
548 // For each instruction we check if it can be the root of a combiner
549 // pattern. Then for each pattern the new code sequence in form of MI is
550 // generated and evaluated. When the efficiency criteria (don't lengthen
551 // critical path, don't use more resources) is met the new sequence gets
552 // hooked up into the basic block before the old sequence is removed.
553 //
554 // The algorithm does not try to evaluate all patterns and pick the best.
555 // This is only an artificial restriction though. In practice there is
556 // mostly one pattern, and getMachineCombinerPatterns() can order patterns
557 // based on an internal cost heuristic. If
558 // machine-combiner-verify-pattern-order is enabled, all patterns are
559 // checked to ensure later patterns do not provide better latency savings.
560
561 if (!TII->getMachineCombinerPatterns(MI, Patterns, DoRegPressureReduce))
562 continue;
563
564 // Only used with -machine-combiner-verify-pattern-order.
565 [[maybe_unused]] long PrevLatencyDiff = std::numeric_limits<long>::max();
566
567 for (const auto P : Patterns) {
570 DenseMap<Register, unsigned> InstrIdxForVirtReg;
571 TII->genAlternativeCodeSequence(MI, P, InsInstrs, DelInstrs,
572 InstrIdxForVirtReg);
573 // Found pattern, but did not generate alternative sequence.
574 // This can happen e.g. when an immediate could not be materialized
575 // in a single instruction.
576 if (InsInstrs.empty())
577 continue;
578
579 LLVM_DEBUG(if (Opts.machine_combiner_dump_subst_intrs) {
580 dbgs() << "\tFor the Pattern (" << (int)P
581 << ") these instructions could be removed\n";
582 for (auto const *InstrPtr : DelInstrs)
583 InstrPtr->print(dbgs(), /*IsStandalone*/false, /*SkipOpers*/false,
584 /*SkipDebugLoc*/false, /*AddNewLine*/true, TII);
585 dbgs() << "\tThese instructions could replace the removed ones\n";
586 for (auto const *InstrPtr : InsInstrs)
587 InstrPtr->print(dbgs(), /*IsStandalone*/false, /*SkipOpers*/false,
588 /*SkipDebugLoc*/false, /*AddNewLine*/true, TII);
589 });
590
591 // Check that the difference between original and new latency is
592 // decreasing for later patterns. This helps to discover sub-optimal
593 // pattern orderings.
594 if (Opts.machine_combiner_verify_pattern_order &&
595 TSchedModel.hasInstrSchedModelOrItineraries()) {
596 auto [NewRootLatency, RootLatency] = getLatenciesForInstrSequences(
597 MI, InsInstrs, DelInstrs, TraceEnsemble->getTrace(MBB));
598 long CurrentLatencyDiff = ((long)RootLatency) - ((long)NewRootLatency);
599 assert(CurrentLatencyDiff <= PrevLatencyDiff &&
600 "Current pattern is expected to be better than the previous "
601 "pattern.");
602 PrevLatencyDiff = CurrentLatencyDiff;
603 }
604
605 if (IncrementalUpdate && LastUpdate != BlockIter) {
606 // Update depths since the last incremental update.
607 TraceEnsemble->updateDepths(LastUpdate, BlockIter, RegUnits);
608 LastUpdate = BlockIter;
609 }
610
611 if (DoRegPressureReduce &&
612 getCombinerObjective(P) ==
613 CombinerObjective::MustReduceRegisterPressure) {
615 Opts.machine_combiner_inc_threshold)) {
616 // Use incremental depth updates for basic blocks above threshold
617 IncrementalUpdate = true;
618 LastUpdate = BlockIter;
619 }
620 if (reduceRegisterPressure(MI, MBB, InsInstrs, DelInstrs, P)) {
621 // Replace DelInstrs with InsInstrs.
622 insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, TraceEnsemble,
623 RegUnits, TII, P, IncrementalUpdate);
624 Changed |= true;
625
626 // Go back to previous instruction as it may have ILP reassociation
627 // opportunity.
628 BlockIter--;
629 break;
630 }
631 }
632
633 if (ML && TII->isThroughputPattern(P)) {
634 LLVM_DEBUG(dbgs() << "\t Replacing due to throughput pattern in loop\n");
635 insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, TraceEnsemble,
636 RegUnits, TII, P, IncrementalUpdate);
637 // Eagerly stop after the first pattern fires.
638 Changed = true;
639 break;
640 } else if (OptForSize && InsInstrs.size() < DelInstrs.size()) {
641 LLVM_DEBUG(dbgs() << "\t Replacing due to OptForSize ("
642 << InsInstrs.size() << " < "
643 << DelInstrs.size() << ")\n");
644 insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, TraceEnsemble,
645 RegUnits, TII, P, IncrementalUpdate);
646 // Eagerly stop after the first pattern fires.
647 Changed = true;
648 break;
649 } else {
650 // For big basic blocks, we only compute the full trace the first time
651 // we hit this. We do not invalidate the trace, but instead update the
652 // instruction depths incrementally.
653 // NOTE: Only the instruction depths up to MI are accurate. All other
654 // trace information is not updated.
655 MachineTraceMetrics::Trace BlockTrace = TraceEnsemble->getTrace(MBB);
656 Traces->verifyAnalysis();
657 if (improvesCriticalPathLen(MBB, &MI, BlockTrace, InsInstrs, DelInstrs,
658 InstrIdxForVirtReg, P,
659 !IncrementalUpdate) &&
660 preservesResourceLen(MBB, BlockTrace, InsInstrs, DelInstrs)) {
662 Opts.machine_combiner_inc_threshold)) {
663 // Use incremental depth updates for basic blocks above treshold
664 IncrementalUpdate = true;
665 LastUpdate = BlockIter;
666 }
667
668 insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, TraceEnsemble,
669 RegUnits, TII, P, IncrementalUpdate);
670
671 // Eagerly stop after the first pattern fires.
672 Changed = true;
673 break;
674 }
675 // Cleanup instructions of the alternative code sequence. There is no
676 // use for them.
678 for (auto *InstrPtr : InsInstrs)
679 MF->deleteMachineInstr(InstrPtr);
680 }
681 InstrIdxForVirtReg.clear();
682 }
683 }
684
685 if (Changed && IncrementalUpdate)
686 Traces->invalidate(MBB);
687 return Changed;
688}
689
690bool MachineCombinerImpl::run(MachineFunction &MF, MachineLoopInfo *MLI,
691 MachineTraceMetrics *Traces,
692 ProfileSummaryInfo *PSI,
693 MachineBlockFrequencyInfo *MBFI,
694 RegisterClassInfo *RegClassInfo) {
695 STI = &MF.getSubtarget();
696 TII = STI->getInstrInfo();
697 TRI = STI->getRegisterInfo();
698 SchedModel = STI->getSchedModel();
699 TSchedModel.init(STI);
700 MRI = &MF.getRegInfo();
701 this->MLI = MLI;
702 this->Traces = Traces;
703 this->PSI = PSI;
704 this->MBFI = MBFI;
705 this->RegClassInfo = RegClassInfo;
706 TraceEnsemble = nullptr;
707
708 LLVM_DEBUG(dbgs() << "Machine InstCombiner: " << MF.getName() << '\n');
709 if (!TII->useMachineCombiner()) {
711 dbgs()
712 << " Skipping pass: Target does not support machine combiner\n");
713 return false;
714 }
715
716 bool Changed = false;
717
718 // Try to combine instructions.
719 for (auto &MBB : MF)
720 Changed |= combineInstructions(&MBB);
721
722 return Changed;
723}
724
725bool MachineCombinerLegacy::runOnMachineFunction(MachineFunction &MF) {
726 auto *MLI = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
727 auto *Traces = &getAnalysis<MachineTraceMetricsWrapperPass>().getMTM();
728 auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
729 auto *MBFI = (PSI && PSI->hasProfileSummary())
730 ? &getAnalysis<LazyMachineBlockFrequencyInfoPass>().getBFI()
731 : nullptr;
732 auto &RegClassInfo =
733 getAnalysis<MachineRegisterClassInfoWrapperPass>().getRCI();
734 return MachineCombinerImpl(getCodeGenOptions(MF))
735 .run(MF, MLI, Traces, PSI, MBFI, &RegClassInfo);
736}
737
738PreservedAnalyses
741 MFPropsModifier _(*this, MF);
742 auto &MLI = MFAM.getResult<MachineLoopAnalysis>(MF);
743 auto &Traces = MFAM.getResult<MachineTraceMetricsAnalysis>(MF);
745 .getCachedResult<ProfileSummaryAnalysis>(
746 *MF.getFunction().getParent());
747 auto *MBFI = (PSI && PSI->hasProfileSummary())
749 : nullptr;
750 auto &RegClassInfo = MFAM.getResult<MachineRegisterClassAnalysis>(MF);
751 if (!MachineCombinerImpl(getCodeGenOptions(MF))
752 .run(MF, &MLI, &Traces, PSI, MBFI, &RegClassInfo))
753 return PreservedAnalyses::all();
754
756 PA.preserveSet<CFGAnalyses>();
757 PA.preserve<MachineTraceMetricsAnalysis>();
758 return PA;
759}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
const AArch64InstrInfo & TII
MachineBasicBlock & MBB
This file defines the DenseMap class.
#define DEBUG_TYPE
#define _
IRTranslator LLVM IR MI
===- LazyMachineBlockFrequencyInfo.h - Lazy Block Frequency -*- C++ -*–===//
#define I(x, y, z)
Definition MD5.cpp:57
static void insertDeleteInstructions(MachineBasicBlock *MBB, MachineInstr &MI, SmallVectorImpl< MachineInstr * > &InsInstrs, SmallVectorImpl< MachineInstr * > &DelInstrs, MachineTraceMetrics::Ensemble *TraceEnsemble, LiveRegUnitSet &RegUnits, const TargetInstrInfo *TII, unsigned Pattern, bool IncrementalUpdate)
Inserts InsInstrs and deletes DelInstrs.
Register const TargetRegisterInfo * TRI
Promote Memory to Register
Definition Mem2Reg.cpp:110
uint64_t IntrinsicInst * II
#define P(N)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
MachineRegisterInfo & MRI
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:171
#define LLVM_DEBUG(...)
Definition Debug.h:119
bool isThroughputPattern(unsigned Pattern) const override
Return true when a code sequence can improve throughput.
CombinerObjective getCombinerObjective(unsigned Pattern) const override
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
Represents analyses that only rely on functions' control flow.
Definition Analysis.h:73
iterator find(const_arg_type_t< KeyT > Val)
Definition DenseMap.h:766
iterator end()
Definition DenseMap.h:686
Module * getParent()
Get the module that this global value is contained inside of...
This is an alternative analysis pass to MachineBlockFrequencyInfo.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
bool hasSuperClassEq(const MCRegisterClass *RC) const
Returns true if RC is a super-class of or equal to this class.
bool contains(MCRegister Reg) const
contains - Return true if the specified register is included in this register class.
const MCSchedModel & getSchedModel() const
Get the machine model for this subtarget's CPU.
An RAII based helper class to modify MachineFunctionProperties when running pass.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
MachineInstrBundleIterator< MachineInstr > iterator
LLVM_ABI StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
LLVM_ABI bool sizeWithoutDebugLargerThan(unsigned Limit) const
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
Representation of each machine instruction.
const MachineBasicBlock * getParent() const
filtered_mop_range all_defs()
Returns an iterator range over all operands that are (explicit or implicit) register defs.
LLVM_ABI int findRegisterUseOperandIdx(Register Reg, const TargetRegisterInfo *TRI, bool isKill=false) const
Returns the operand index that is a use of the specific register or -1 if it is not found.
bool isTransient() const
Return true if this is a transient instruction that is either very likely to be eliminated during reg...
LLVM_ABI int findRegisterDefOperandIdx(Register Reg, const TargetRegisterInfo *TRI, bool isDead=false, bool Overlap=false) const
Returns the operand index that is a def of the specified register or -1 if it is not found.
Analysis pass that exposes the MachineLoopInfo for a machine function.
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
Register getReg() const
getReg - Returns the register number.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
static reg_iterator reg_end()
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
reg_iterator reg_begin(Register RegNo) const
defusechain_iterator< true, true, false, true, false > reg_iterator
reg_iterator/reg_begin/reg_end - Walk all defs and uses of the specified register.
LLVM_ABI LLVM_READONLY MachineInstr * getUniqueVRegDef(Register Reg) const
getUniqueVRegDef - Return the unique machine instr that defines the specified virtual register or nul...
A trace ensemble is a collection of traces selected using the same strategy, for example 'minimum res...
void invalidate(const MachineBasicBlock *MBB)
Invalidate traces through BadMBB.
void updateDepth(TraceBlockInfo &TBI, const MachineInstr &, LiveRegUnitSet &RegUnits)
Updates the depth of an machine instruction, given RegUnits.
void updateDepths(MachineBasicBlock::iterator Start, MachineBasicBlock::iterator End, LiveRegUnitSet &RegUnits)
Updates the depth of the instructions from Start to End.
Trace getTrace(const MachineBasicBlock *MBB)
Get the trace that passes through MBB.
LLVM_ABI unsigned getResourceLength(ArrayRef< const MachineBasicBlock * > Extrablocks={}, ArrayRef< const MCSchedClassDesc * > ExtraInstrs={}, ArrayRef< const MCSchedClassDesc * > RemoveInstrs={}) const
Return the resource length of the trace.
InstrCycles getInstrCycles(const MachineInstr &MI) const
Return the depth and height of MI.
LLVM_ABI unsigned getInstrSlack(const MachineInstr &MI) const
Return the slack of MI.
LLVM_ABI bool isDepInTrace(const MachineInstr &DefMI, const MachineInstr &UseMI) const
A dependence is useful if the basic block of the defining instruction is part of the trace of the use...
LLVM_ABI Ensemble * getEnsemble(MachineTraceStrategy)
Get the trace ensemble representing the given trace selection strategy.
LLVM_ABI void verifyAnalysis() const
LLVM_ABI void invalidate(const MachineBasicBlock *MBB)
Invalidate cached information about MBB.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Analysis providing profile information.
bool hasProfileSummary() const
Returns true if profile summary is available.
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition Register.h:79
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
iterator erase(iterator I)
erase - Erases an existing element identified by a valid iterator.
Definition SparseSet.h:288
const_iterator begin() const
Definition SparseSet.h:171
const_iterator end() const
Definition SparseSet.h:172
void setUniverse(unsigned U)
setUniverse - Set the universe size which determines the largest key the set can hold.
Definition SparseSet.h:153
TargetInstrInfo - Interface to description of machine instruction set.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Provide an instruction scheduling machine model to CodeGen passes.
LLVM_ABI bool hasInstrSchedModel() const
Return true if this machine model includes an instruction-level scheduling model.
LLVM_ABI void init(const TargetSubtargetInfo *TSInfo, bool EnableSModel=true, bool EnableSItins=true)
Initialize the machine model for instruction scheduling.
LLVM_ABI unsigned computeOperandLatency(const MachineInstr *DefMI, unsigned DefOperIdx, const MachineInstr *UseMI, unsigned UseOperIdx) const
Compute operand latency based on the available machine model.
bool hasInstrSchedModelOrItineraries() const
Return true if this machine model includes an instruction-level scheduling model or cycle-to-cycle it...
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetInstrInfo * getInstrInfo() const
virtual const TargetRegisterInfo * getRegisterInfo() const =0
Return the target's register information.
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
This is an optimization pass for GlobalISel generic memory operations.
OuterAnalysisManagerProxy< ModuleAnalysisManager, MachineFunction > ModuleAnalysisManagerMachineFunctionProxy
Provide the ModuleAnalysisManager to Function proxy.
LLVM_ABI bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)
Returns true if machine function MF is suggested to be size-optimized based on the profile.
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
LLVM_ABI PreservedAnalyses getMachineFunctionPassPreservedAnalyses()
Returns the minimum set of Analyses that all machine function passes must preserve.
LLVM_ABI char & MachineCombinerID
This pass performs instruction combining using trace metrics to estimate critical-path and resource d...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
CombinerObjective
The combiner's goal may differ based on which pattern it is attempting to optimize.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
SparseSet< LiveRegUnit, MCRegUnit, MCRegUnitToIndex > LiveRegUnitSet
ArrayRef(const T &OneElt) -> ArrayRef< T >
const CodeGenOptions & getCodeGenOptions(const LLVMContext &C)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition BitVector.h:881
Machine model for scheduling, bundling, and heuristics.
Definition MCSchedule.h:268
const MCSchedClassDesc * getSchedClassDesc(unsigned SchedClassIdx) const
Definition MCSchedule.h:376
unsigned Depth
Earliest issue cycle as determined by data dependencies and instruction latencies from the beginning ...