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