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 "CodeGenOptions.h"
15#include "llvm/ADT/DenseMap.h"
16#include "llvm/ADT/Statistic.h"
17#include "llvm/Analysis/ProfileSummaryInfo.h"
18#include "llvm/CodeGen/LazyMachineBlockFrequencyInfo.h"
19#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
20#include "llvm/CodeGen/MachineCombinerPattern.h"
21#include "llvm/CodeGen/MachineDominators.h"
22#include "llvm/CodeGen/MachineFunction.h"
23#include "llvm/CodeGen/MachineFunctionAnalysis.h"
24#include "llvm/CodeGen/MachineFunctionPass.h"
25#include "llvm/CodeGen/MachineLoopInfo.h"
26#include "llvm/CodeGen/MachineRegisterInfo.h"
27#include "llvm/CodeGen/MachineSizeOpts.h"
28#include "llvm/CodeGen/MachineTraceMetrics.h"
29#include "llvm/CodeGen/RegisterClassInfo.h"
30#include "llvm/CodeGen/TargetInstrInfo.h"
31#include "llvm/CodeGen/TargetRegisterInfo.h"
32#include "llvm/CodeGen/TargetSchedule.h"
33#include "llvm/CodeGen/TargetSubtargetInfo.h"
34#include "llvm/InitializePasses.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
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,
73 MachineTraceMetrics::Trace BlockTrace,
74 const MachineBasicBlock &MBB);
75 unsigned getLatency(MachineInstr *Root, MachineInstr *NewRoot,
76 MachineTraceMetrics::Trace BlockTrace);
77 bool improvesCriticalPathLen(MachineBasicBlock *MBB, MachineInstr *Root,
78 MachineTraceMetrics::Trace BlockTrace,
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,
88 MachineTraceMetrics::Trace BlockTrace,
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,
97 MachineTraceMetrics::Trace BlockTrace);
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)
117INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
118INITIALIZE_PASS_DEPENDENCY(MachineRegisterClassInfoWrapperPass)
119INITIALIZE_PASS_DEPENDENCY(MachineTraceMetricsWrapperPass)
120INITIALIZE_PASS_END(MachineCombinerLegacy, DEBUG_TYPE, "Machine InstCombiner",
121 false, false)
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>();
131 MachineFunctionPass::getAnalysisUsage(AU);
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(Reg: 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(i: 0).getReg();
149 Register Src = MI->getOperand(i: 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(i: 0).getSubReg() || Src.isPhysical() || Dst.isPhysical())
154 return false;
155
156 auto SrcSub = MI->getOperand(i: 1).getSubReg();
157 auto SrcRC = MRI->getRegClass(Reg: Src);
158 auto DstRC = MRI->getRegClass(Reg: Dst);
159 return TRI->getMatchingSuperRegClass(A: SrcRC, B: DstRC, Idx: 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(Reg: Src);
167 auto DstRC = MRI->getRegClass(Reg: Dst);
168 return SrcRC->hasSuperClassEq(RC: DstRC) || SrcRC->hasSubClassEq(RC: DstRC);
169 }
170
171 if (Src.isVirtual())
172 std::swap(a&: Src, b&: Dst);
173
174 // Now Src is physical register, Dst is virtual register.
175 auto DstRC = MRI->getRegClass(Reg: Dst);
176 return DstRC->contains(Reg: 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,
190 MachineTraceMetrics::Trace BlockTrace,
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(Val: 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(Reg: MO.getReg(), /*TRI=*/nullptr);
214 int UseIdx =
215 InstrPtr->findRegisterUseOperandIdx(Reg: MO.getReg(), /*TRI=*/nullptr);
216 LatencyOp = TSchedModel.computeOperandLatency(DefMI: DefInstr, DefOperIdx: DefIdx,
217 UseMI: InstrPtr, UseOperIdx: 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(MI: *DefInstr).Depth;
224 if (!isTransientMI(MI: DefInstr))
225 LatencyOp = TSchedModel.computeOperandLatency(
226 DefMI: DefInstr,
227 DefOperIdx: DefInstr->findRegisterDefOperandIdx(Reg: MO.getReg(),
228 /*TRI=*/nullptr),
229 UseMI: InstrPtr,
230 UseOperIdx: InstrPtr->findRegisterUseOperandIdx(Reg: MO.getReg(),
231 /*TRI=*/nullptr));
232 }
233 }
234 IDepth = std::max(a: IDepth, b: DepthOp + LatencyOp);
235 }
236 InstrDepth.push_back(Elt: 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
262 MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(RegNo: MO.getReg());
263 RI++;
264 if (RI == MRI->reg_end())
265 continue;
266 MachineInstr *UseMO = RI->getParent();
267 unsigned LatencyOp = 0;
268 if (UseMO && BlockTrace.isDepInTrace(DefMI: *Root, UseMI: *UseMO)) {
269 LatencyOp = TSchedModel.computeOperandLatency(
270 DefMI: NewRoot,
271 DefOperIdx: NewRoot->findRegisterDefOperandIdx(Reg: MO.getReg(), /*TRI=*/nullptr),
272 UseMI: UseMO,
273 UseOperIdx: UseMO->findRegisterUseOperandIdx(Reg: MO.getReg(), /*TRI=*/nullptr));
274 } else {
275 LatencyOp = TSchedModel.computeInstrLatency(MI: NewRoot);
276 }
277 NewRootLatency = std::max(a: NewRootLatency, b: 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(MI: InsInstrs[i]);
311 NewRootLatency += getLatency(Root: &MI, NewRoot, BlockTrace);
312
313 unsigned RootLatency = 0;
314 for (auto *I : DelInstrs)
315 RootLatency += TSchedModel.computeInstrLatency(MI: 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,
338 MachineTraceMetrics::Trace BlockTrace,
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: *MBB);
346 unsigned RootDepth = BlockTrace.getInstrCycles(MI: *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&: *Root)) {
371 std::tie(args&: NewRootLatency, args&: RootLatency) =
372 getLatenciesForInstrSequences(MI&: *Root, InsInstrs, DelInstrs, BlockTrace);
373 } else {
374 NewRootLatency = TSchedModel.computeInstrLatency(MI: InsInstrs.back());
375 RootLatency = TSchedModel.computeInstrLatency(MI: Root);
376 }
377
378 unsigned RootSlack = BlockTrace.getInstrSlack(MI: *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(Opcode: Opc).getSchedClass();
404 const MCSchedClassDesc *SC = SchedModel.getSchedClassDesc(SchedClassIdx: Idx);
405 InstrsSC.push_back(Elt: 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);
420 SmallVector<const MachineBasicBlock *, 1> MBBarr;
421 MBBarr.push_back(Elt: MBB);
422 unsigned ResLenBeforeCombine = BlockTrace.getResourceLength(Extrablocks: MBBarr);
423
424 // Deal with SC rather than Instructions.
425 SmallVector<const MCSchedClassDesc *, 16> InsInstrsSC;
426 SmallVector<const MCSchedClassDesc *, 16> DelInstrsSC;
427
428 instr2instrSC(Instrs&: InsInstrs, InstrsSC&: InsInstrsSC);
429 instr2instrSC(Instrs&: DelInstrs, InstrsSC&: 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(Extrablocks: MBBarr, ExtraInstrs: MSCInsArr, RemoveInstrs: MSCDelArr);
437
438 LLVM_DEBUG(dbgs() << "\t\tResource length before replacement: "
439 << ResLenBeforeCombine
440 << " and after: " << ResLenAfterCombine << "\n");
441 LLVM_DEBUG(
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
466insertDeleteInstructions(MachineBasicBlock *MBB, MachineInstr &MI,
467 SmallVectorImpl<MachineInstr *> &InsInstrs,
468 SmallVectorImpl<MachineInstr *> &DelInstrs,
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(Root&: MI, Pattern, InsInstrs);
480
481 for (auto *InstrPtr : InsInstrs)
482 MBB->insert(I: (MachineBasicBlock::iterator)&MI, 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(BB: 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(Root&: 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) {
568 SmallVector<MachineInstr *, 16> InsInstrs;
569 SmallVector<MachineInstr *, 16> DelInstrs;
570 DenseMap<Register, unsigned> InstrIdxForVirtReg;
571 TII->genAlternativeCodeSequence(Root&: MI, Pattern: P, InsInstrs, DelInstrs,
572 InstIdxForVirtReg&: 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, BlockTrace: 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(Start: LastUpdate, End: BlockIter, RegUnits);
608 LastUpdate = BlockIter;
609 }
610
611 if (DoRegPressureReduce &&
612 getCombinerObjective(Pattern: P) ==
613 CombinerObjective::MustReduceRegisterPressure) {
614 if (MBB->sizeWithoutDebugLargerThan(
615 Limit: 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(Root&: MI, MBB, InsInstrs, DelInstrs, Pattern: P)) {
621 // Replace DelInstrs with InsInstrs.
622 insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, TraceEnsemble,
623 RegUnits, TII, Pattern: 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(Pattern: P)) {
634 LLVM_DEBUG(dbgs() << "\t Replacing due to throughput pattern in loop\n");
635 insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, TraceEnsemble,
636 RegUnits, TII, Pattern: 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, Pattern: 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, Root: &MI, BlockTrace, InsInstrs, DelInstrs,
658 InstrIdxForVirtReg, Pattern: P,
659 SlackIsAccurate: !IncrementalUpdate) &&
660 preservesResourceLen(MBB, BlockTrace, InsInstrs, DelInstrs)) {
661 if (MBB->sizeWithoutDebugLargerThan(
662 Limit: 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, Pattern: 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.
677 MachineFunction *MF = MBB->getParent();
678 for (auto *InstrPtr : InsInstrs)
679 MF->deleteMachineInstr(MI: 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(TSInfo: 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()) {
710 LLVM_DEBUG(
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: &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: &RegClassInfo);
736}
737
738PreservedAnalyses
739MachineCombinerPass::run(MachineFunction &MF,
740 MachineFunctionAnalysisManager &MFAM) {
741 MFPropsModifier _(*this, MF);
742 auto &MLI = MFAM.getResult<MachineLoopAnalysis>(IR&: MF);
743 auto &Traces = MFAM.getResult<MachineTraceMetricsAnalysis>(IR&: MF);
744 auto *PSI = MFAM.getResult<ModuleAnalysisManagerMachineFunctionProxy>(IR&: MF)
745 .getCachedResult<ProfileSummaryAnalysis>(
746 IR&: *MF.getFunction().getParent());
747 auto *MBFI = (PSI && PSI->hasProfileSummary())
748 ? &MFAM.getResult<MachineBlockFrequencyAnalysis>(IR&: MF)
749 : nullptr;
750 auto &RegClassInfo = MFAM.getResult<MachineRegisterClassAnalysis>(IR&: MF);
751 if (!MachineCombinerImpl(getCodeGenOptions(MF))
752 .run(MF, MLI: &MLI, Traces: &Traces, PSI, MBFI, RegClassInfo: &RegClassInfo))
753 return PreservedAnalyses::all();
754
755 auto PA = getMachineFunctionPassPreservedAnalyses();
756 PA.preserveSet<CFGAnalyses>();
757 PA.preserve<MachineTraceMetricsAnalysis>();
758 return PA;
759}
760