1 //===---- MachineCombiner.cpp - Instcombining on SSA form machine code ----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // The machine combiner pass uses machine trace metrics to ensure the combined
11 // instructions do not lengthen the critical path or the resource depth.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/ADT/DenseMap.h"
15 #include "llvm/ADT/Statistic.h"
16 #include "llvm/CodeGen/MachineDominators.h"
17 #include "llvm/CodeGen/MachineFunction.h"
18 #include "llvm/CodeGen/MachineFunctionPass.h"
19 #include "llvm/CodeGen/MachineLoopInfo.h"
20 #include "llvm/CodeGen/MachineRegisterInfo.h"
21 #include "llvm/CodeGen/MachineTraceMetrics.h"
22 #include "llvm/CodeGen/Passes.h"
23 #include "llvm/CodeGen/TargetInstrInfo.h"
24 #include "llvm/CodeGen/TargetRegisterInfo.h"
25 #include "llvm/CodeGen/TargetSchedule.h"
26 #include "llvm/CodeGen/TargetSubtargetInfo.h"
27 #include "llvm/Support/CommandLine.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/raw_ostream.h"
33 #define DEBUG_TYPE "machine-combiner"
35 STATISTIC(NumInstCombined, "Number of machineinst combined");
37 static cl::opt<unsigned>
38 inc_threshold("machine-combiner-inc-threshold", cl::Hidden,
39 cl::desc("Incremental depth computation will be used for basic "
40 "blocks with more instructions."), cl::init(500));
43 class MachineCombiner : public MachineFunctionPass {
44 const TargetInstrInfo *TII;
45 const TargetRegisterInfo *TRI;
46 MCSchedModel SchedModel;
47 MachineRegisterInfo *MRI;
48 MachineLoopInfo *MLI; // Current MachineLoopInfo
49 MachineTraceMetrics *Traces;
50 MachineTraceMetrics::Ensemble *MinInstr;
52 TargetSchedModel TSchedModel;
54 /// True if optimizing for code size.
59 MachineCombiner() : MachineFunctionPass(ID) {
60 initializeMachineCombinerPass(*PassRegistry::getPassRegistry());
62 void getAnalysisUsage(AnalysisUsage &AU) const override;
63 bool runOnMachineFunction(MachineFunction &MF) override;
64 StringRef getPassName() const override { return "Machine InstCombiner"; }
67 bool doSubstitute(unsigned NewSize, unsigned OldSize);
68 bool combineInstructions(MachineBasicBlock *);
69 MachineInstr *getOperandDef(const MachineOperand &MO);
70 unsigned getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
71 DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
72 MachineTraceMetrics::Trace BlockTrace);
73 unsigned getLatency(MachineInstr *Root, MachineInstr *NewRoot,
74 MachineTraceMetrics::Trace BlockTrace);
76 improvesCriticalPathLen(MachineBasicBlock *MBB, MachineInstr *Root,
77 MachineTraceMetrics::Trace BlockTrace,
78 SmallVectorImpl<MachineInstr *> &InsInstrs,
79 SmallVectorImpl<MachineInstr *> &DelInstrs,
80 DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
81 MachineCombinerPattern Pattern, bool SlackIsAccurate);
82 bool preservesResourceLen(MachineBasicBlock *MBB,
83 MachineTraceMetrics::Trace BlockTrace,
84 SmallVectorImpl<MachineInstr *> &InsInstrs,
85 SmallVectorImpl<MachineInstr *> &DelInstrs);
86 void instr2instrSC(SmallVectorImpl<MachineInstr *> &Instrs,
87 SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC);
91 char MachineCombiner::ID = 0;
92 char &llvm::MachineCombinerID = MachineCombiner::ID;
94 INITIALIZE_PASS_BEGIN(MachineCombiner, DEBUG_TYPE,
95 "Machine InstCombiner", false, false)
96 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
97 INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics)
98 INITIALIZE_PASS_END(MachineCombiner, DEBUG_TYPE, "Machine InstCombiner",
101 void MachineCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
102 AU.setPreservesCFG();
103 AU.addPreserved<MachineDominatorTree>();
104 AU.addRequired<MachineLoopInfo>();
105 AU.addPreserved<MachineLoopInfo>();
106 AU.addRequired<MachineTraceMetrics>();
107 AU.addPreserved<MachineTraceMetrics>();
108 MachineFunctionPass::getAnalysisUsage(AU);
111 MachineInstr *MachineCombiner::getOperandDef(const MachineOperand &MO) {
112 MachineInstr *DefInstr = nullptr;
113 // We need a virtual register definition.
114 if (MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg()))
115 DefInstr = MRI->getUniqueVRegDef(MO.getReg());
116 // PHI's have no depth etc.
117 if (DefInstr && DefInstr->isPHI())
122 /// Computes depth of instructions in vector \InsInstr.
124 /// \param InsInstrs is a vector of machine instructions
125 /// \param InstrIdxForVirtReg is a dense map of virtual register to index
126 /// of defining machine instruction in \p InsInstrs
127 /// \param BlockTrace is a trace of machine instructions
129 /// \returns Depth of last instruction in \InsInstrs ("NewRoot")
131 MachineCombiner::getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
132 DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
133 MachineTraceMetrics::Trace BlockTrace) {
134 SmallVector<unsigned, 16> InstrDepth;
135 assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
136 "Missing machine model\n");
138 // For each instruction in the new sequence compute the depth based on the
139 // operands. Use the trace information when possible. For new operands which
140 // are tracked in the InstrIdxForVirtReg map depth is looked up in InstrDepth
141 for (auto *InstrPtr : InsInstrs) { // for each Use
143 DEBUG(dbgs() << "NEW INSTR ";
144 InstrPtr->print(dbgs(), TII);
146 for (const MachineOperand &MO : InstrPtr->operands()) {
147 // Check for virtual register operand.
148 if (!(MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg())))
152 unsigned DepthOp = 0;
153 unsigned LatencyOp = 0;
154 DenseMap<unsigned, unsigned>::iterator II =
155 InstrIdxForVirtReg.find(MO.getReg());
156 if (II != InstrIdxForVirtReg.end()) {
157 // Operand is new virtual register not in trace
158 assert(II->second < InstrDepth.size() && "Bad Index");
159 MachineInstr *DefInstr = InsInstrs[II->second];
161 "There must be a definition for a new virtual register");
162 DepthOp = InstrDepth[II->second];
163 int DefIdx = DefInstr->findRegisterDefOperandIdx(MO.getReg());
164 int UseIdx = InstrPtr->findRegisterUseOperandIdx(MO.getReg());
165 LatencyOp = TSchedModel.computeOperandLatency(DefInstr, DefIdx,
168 MachineInstr *DefInstr = getOperandDef(MO);
170 DepthOp = BlockTrace.getInstrCycles(*DefInstr).Depth;
171 LatencyOp = TSchedModel.computeOperandLatency(
172 DefInstr, DefInstr->findRegisterDefOperandIdx(MO.getReg()),
173 InstrPtr, InstrPtr->findRegisterUseOperandIdx(MO.getReg()));
176 IDepth = std::max(IDepth, DepthOp + LatencyOp);
178 InstrDepth.push_back(IDepth);
180 unsigned NewRootIdx = InsInstrs.size() - 1;
181 return InstrDepth[NewRootIdx];
184 /// Computes instruction latency as max of latency of defined operands.
186 /// \param Root is a machine instruction that could be replaced by NewRoot.
187 /// It is used to compute a more accurate latency information for NewRoot in
188 /// case there is a dependent instruction in the same trace (\p BlockTrace)
189 /// \param NewRoot is the instruction for which the latency is computed
190 /// \param BlockTrace is a trace of machine instructions
192 /// \returns Latency of \p NewRoot
193 unsigned MachineCombiner::getLatency(MachineInstr *Root, MachineInstr *NewRoot,
194 MachineTraceMetrics::Trace BlockTrace) {
195 assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
196 "Missing machine model\n");
198 // Check each definition in NewRoot and compute the latency
199 unsigned NewRootLatency = 0;
201 for (const MachineOperand &MO : NewRoot->operands()) {
202 // Check for virtual register operand.
203 if (!(MO.isReg() && TargetRegisterInfo::isVirtualRegister(MO.getReg())))
207 // Get the first instruction that uses MO
208 MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(MO.getReg());
210 MachineInstr *UseMO = RI->getParent();
211 unsigned LatencyOp = 0;
212 if (UseMO && BlockTrace.isDepInTrace(*Root, *UseMO)) {
213 LatencyOp = TSchedModel.computeOperandLatency(
214 NewRoot, NewRoot->findRegisterDefOperandIdx(MO.getReg()), UseMO,
215 UseMO->findRegisterUseOperandIdx(MO.getReg()));
217 LatencyOp = TSchedModel.computeInstrLatency(NewRoot);
219 NewRootLatency = std::max(NewRootLatency, LatencyOp);
221 return NewRootLatency;
224 /// The combiner's goal may differ based on which pattern it is attempting
226 enum class CombinerObjective {
227 MustReduceDepth, // The data dependency chain must be improved.
228 Default // The critical path must not be lengthened.
231 static CombinerObjective getCombinerObjective(MachineCombinerPattern P) {
232 // TODO: If C++ ever gets a real enum class, make this part of the
233 // MachineCombinerPattern class.
235 case MachineCombinerPattern::REASSOC_AX_BY:
236 case MachineCombinerPattern::REASSOC_AX_YB:
237 case MachineCombinerPattern::REASSOC_XA_BY:
238 case MachineCombinerPattern::REASSOC_XA_YB:
239 return CombinerObjective::MustReduceDepth;
241 return CombinerObjective::Default;
245 /// The DAGCombine code sequence ends in MI (Machine Instruction) Root.
246 /// The new code sequence ends in MI NewRoot. A necessary condition for the new
247 /// sequence to replace the old sequence is that it cannot lengthen the critical
248 /// path. The definition of "improve" may be restricted by specifying that the
249 /// new path improves the data dependency chain (MustReduceDepth).
250 bool MachineCombiner::improvesCriticalPathLen(
251 MachineBasicBlock *MBB, MachineInstr *Root,
252 MachineTraceMetrics::Trace BlockTrace,
253 SmallVectorImpl<MachineInstr *> &InsInstrs,
254 SmallVectorImpl<MachineInstr *> &DelInstrs,
255 DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
256 MachineCombinerPattern Pattern,
257 bool SlackIsAccurate) {
258 assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
259 "Missing machine model\n");
260 // NewRoot is the last instruction in the \p InsInstrs vector.
261 unsigned NewRootIdx = InsInstrs.size() - 1;
262 MachineInstr *NewRoot = InsInstrs[NewRootIdx];
264 // Get depth and latency of NewRoot and Root.
265 unsigned NewRootDepth = getDepth(InsInstrs, InstrIdxForVirtReg, BlockTrace);
266 unsigned RootDepth = BlockTrace.getInstrCycles(*Root).Depth;
268 DEBUG(dbgs() << "DEPENDENCE DATA FOR " << *Root << "\n";
269 dbgs() << " NewRootDepth: " << NewRootDepth << "\n";
270 dbgs() << " RootDepth: " << RootDepth << "\n");
272 // For a transform such as reassociation, the cost equation is
273 // conservatively calculated so that we must improve the depth (data
274 // dependency cycles) in the critical path to proceed with the transform.
275 // Being conservative also protects against inaccuracies in the underlying
276 // machine trace metrics and CPU models.
277 if (getCombinerObjective(Pattern) == CombinerObjective::MustReduceDepth)
278 return NewRootDepth < RootDepth;
280 // A more flexible cost calculation for the critical path includes the slack
281 // of the original code sequence. This may allow the transform to proceed
282 // even if the instruction depths (data dependency cycles) become worse.
284 // Account for the latency of the inserted and deleted instructions by
285 // adding up their latencies. This assumes that the inserted and deleted
286 // instructions are dependent instruction chains, which might not hold
288 unsigned NewRootLatency = 0;
289 for (unsigned i = 0; i < InsInstrs.size() - 1; i++)
290 NewRootLatency += TSchedModel.computeInstrLatency(InsInstrs[i]);
291 NewRootLatency += getLatency(Root, NewRoot, BlockTrace);
293 unsigned RootLatency = 0;
294 for (auto I : DelInstrs)
295 RootLatency += TSchedModel.computeInstrLatency(I);
297 unsigned RootSlack = BlockTrace.getInstrSlack(*Root);
298 unsigned NewCycleCount = NewRootDepth + NewRootLatency;
299 unsigned OldCycleCount = RootDepth + RootLatency +
300 (SlackIsAccurate ? RootSlack : 0);
301 DEBUG(dbgs() << " NewRootLatency: " << NewRootLatency << "\n";
302 dbgs() << " RootLatency: " << RootLatency << "\n";
303 dbgs() << " RootSlack: " << RootSlack << " SlackIsAccurate="
304 << SlackIsAccurate << "\n";
305 dbgs() << " NewRootDepth + NewRootLatency = "
306 << NewCycleCount << "\n";
307 dbgs() << " RootDepth + RootLatency + RootSlack = "
308 << OldCycleCount << "\n";
311 return NewCycleCount <= OldCycleCount;
314 /// helper routine to convert instructions into SC
315 void MachineCombiner::instr2instrSC(
316 SmallVectorImpl<MachineInstr *> &Instrs,
317 SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC) {
318 for (auto *InstrPtr : Instrs) {
319 unsigned Opc = InstrPtr->getOpcode();
320 unsigned Idx = TII->get(Opc).getSchedClass();
321 const MCSchedClassDesc *SC = SchedModel.getSchedClassDesc(Idx);
322 InstrsSC.push_back(SC);
326 /// True when the new instructions do not increase resource length
327 bool MachineCombiner::preservesResourceLen(
328 MachineBasicBlock *MBB, MachineTraceMetrics::Trace BlockTrace,
329 SmallVectorImpl<MachineInstr *> &InsInstrs,
330 SmallVectorImpl<MachineInstr *> &DelInstrs) {
331 if (!TSchedModel.hasInstrSchedModel())
334 // Compute current resource length
336 //ArrayRef<const MachineBasicBlock *> MBBarr(MBB);
337 SmallVector <const MachineBasicBlock *, 1> MBBarr;
338 MBBarr.push_back(MBB);
339 unsigned ResLenBeforeCombine = BlockTrace.getResourceLength(MBBarr);
341 // Deal with SC rather than Instructions.
342 SmallVector<const MCSchedClassDesc *, 16> InsInstrsSC;
343 SmallVector<const MCSchedClassDesc *, 16> DelInstrsSC;
345 instr2instrSC(InsInstrs, InsInstrsSC);
346 instr2instrSC(DelInstrs, DelInstrsSC);
348 ArrayRef<const MCSchedClassDesc *> MSCInsArr = makeArrayRef(InsInstrsSC);
349 ArrayRef<const MCSchedClassDesc *> MSCDelArr = makeArrayRef(DelInstrsSC);
351 // Compute new resource length.
352 unsigned ResLenAfterCombine =
353 BlockTrace.getResourceLength(MBBarr, MSCInsArr, MSCDelArr);
355 DEBUG(dbgs() << "RESOURCE DATA: \n";
356 dbgs() << " resource len before: " << ResLenBeforeCombine
357 << " after: " << ResLenAfterCombine << "\n";);
359 return ResLenAfterCombine <= ResLenBeforeCombine;
362 /// \returns true when new instruction sequence should be generated
363 /// independent if it lengthens critical path or not
364 bool MachineCombiner::doSubstitute(unsigned NewSize, unsigned OldSize) {
365 if (OptSize && (NewSize < OldSize))
367 if (!TSchedModel.hasInstrSchedModelOrItineraries())
372 /// Inserts InsInstrs and deletes DelInstrs. Incrementally updates instruction
373 /// depths if requested.
375 /// \param MBB basic block to insert instructions in
376 /// \param MI current machine instruction
377 /// \param InsInstrs new instructions to insert in \p MBB
378 /// \param DelInstrs instruction to delete from \p MBB
379 /// \param MinInstr is a pointer to the machine trace information
380 /// \param RegUnits set of live registers, needed to compute instruction depths
381 /// \param IncrementalUpdate if true, compute instruction depths incrementally,
382 /// otherwise invalidate the trace
383 static void insertDeleteInstructions(MachineBasicBlock *MBB, MachineInstr &MI,
384 SmallVector<MachineInstr *, 16> InsInstrs,
385 SmallVector<MachineInstr *, 16> DelInstrs,
386 MachineTraceMetrics::Ensemble *MinInstr,
387 SparseSet<LiveRegUnit> &RegUnits,
388 bool IncrementalUpdate) {
389 for (auto *InstrPtr : InsInstrs)
390 MBB->insert((MachineBasicBlock::iterator)&MI, InstrPtr);
392 for (auto *InstrPtr : DelInstrs) {
393 InstrPtr->eraseFromParentAndMarkDBGValuesForRemoval();
394 // Erase all LiveRegs defined by the removed instruction
395 for (auto I = RegUnits.begin(); I != RegUnits.end(); ) {
396 if (I->MI == InstrPtr)
397 I = RegUnits.erase(I);
403 if (IncrementalUpdate)
404 for (auto *InstrPtr : InsInstrs)
405 MinInstr->updateDepth(MBB, *InstrPtr, RegUnits);
407 MinInstr->invalidate(MBB);
412 /// Substitute a slow code sequence with a faster one by
413 /// evaluating instruction combining pattern.
414 /// The prototype of such a pattern is MUl + ADD -> MADD. Performs instruction
415 /// combining based on machine trace metrics. Only combine a sequence of
416 /// instructions when this neither lengthens the critical path nor increases
417 /// resource pressure. When optimizing for codesize always combine when the new
418 /// sequence is shorter.
419 bool MachineCombiner::combineInstructions(MachineBasicBlock *MBB) {
420 bool Changed = false;
421 DEBUG(dbgs() << "Combining MBB " << MBB->getName() << "\n");
423 bool IncrementalUpdate = false;
424 auto BlockIter = MBB->begin();
425 decltype(BlockIter) LastUpdate;
426 // Check if the block is in a loop.
427 const MachineLoop *ML = MLI->getLoopFor(MBB);
429 MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
431 SparseSet<LiveRegUnit> RegUnits;
432 RegUnits.setUniverse(TRI->getNumRegUnits());
434 while (BlockIter != MBB->end()) {
435 auto &MI = *BlockIter++;
437 DEBUG(dbgs() << "INSTR "; MI.dump(); dbgs() << "\n";);
438 SmallVector<MachineCombinerPattern, 16> Patterns;
439 // The motivating example is:
441 // MUL Other MUL_op1 MUL_op2 Other
443 // ADD/SUB => MADD/MSUB
444 // (=Root) (=NewRoot)
446 // The DAGCombine code always replaced MUL + ADD/SUB by MADD. While this is
447 // usually beneficial for code size it unfortunately can hurt performance
448 // when the ADD is on the critical path, but the MUL is not. With the
449 // substitution the MUL becomes part of the critical path (in form of the
450 // MADD) and can lengthen it on architectures where the MADD latency is
451 // longer than the ADD latency.
453 // For each instruction we check if it can be the root of a combiner
454 // pattern. Then for each pattern the new code sequence in form of MI is
455 // generated and evaluated. When the efficiency criteria (don't lengthen
456 // critical path, don't use more resources) is met the new sequence gets
457 // hooked up into the basic block before the old sequence is removed.
459 // The algorithm does not try to evaluate all patterns and pick the best.
460 // This is only an artificial restriction though. In practice there is
461 // mostly one pattern, and getMachineCombinerPatterns() can order patterns
462 // based on an internal cost heuristic.
464 if (!TII->getMachineCombinerPatterns(MI, Patterns))
467 for (auto P : Patterns) {
468 SmallVector<MachineInstr *, 16> InsInstrs;
469 SmallVector<MachineInstr *, 16> DelInstrs;
470 DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
471 TII->genAlternativeCodeSequence(MI, P, InsInstrs, DelInstrs,
473 unsigned NewInstCount = InsInstrs.size();
474 unsigned OldInstCount = DelInstrs.size();
475 // Found pattern, but did not generate alternative sequence.
476 // This can happen e.g. when an immediate could not be materialized
477 // in a single instruction.
481 bool SubstituteAlways = false;
482 if (ML && TII->isThroughputPattern(P))
483 SubstituteAlways = true;
485 if (IncrementalUpdate) {
486 // Update depths since the last incremental update.
487 MinInstr->updateDepths(LastUpdate, BlockIter, RegUnits);
488 LastUpdate = BlockIter;
491 // Substitute when we optimize for codesize and the new sequence has
492 // fewer instructions OR
493 // the new sequence neither lengthens the critical path nor increases
494 // resource pressure.
495 if (SubstituteAlways || doSubstitute(NewInstCount, OldInstCount)) {
496 insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
497 RegUnits, IncrementalUpdate);
498 // Eagerly stop after the first pattern fires.
502 // For big basic blocks, we only compute the full trace the first time
503 // we hit this. We do not invalidate the trace, but instead update the
504 // instruction depths incrementally.
505 // NOTE: Only the instruction depths up to MI are accurate. All other
506 // trace information is not updated.
507 MachineTraceMetrics::Trace BlockTrace = MinInstr->getTrace(MBB);
508 Traces->verifyAnalysis();
509 if (improvesCriticalPathLen(MBB, &MI, BlockTrace, InsInstrs, DelInstrs,
510 InstrIdxForVirtReg, P,
511 !IncrementalUpdate) &&
512 preservesResourceLen(MBB, BlockTrace, InsInstrs, DelInstrs)) {
513 if (MBB->size() > inc_threshold) {
514 // Use incremental depth updates for basic blocks above treshold
515 IncrementalUpdate = true;
516 LastUpdate = BlockIter;
519 insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
520 RegUnits, IncrementalUpdate);
522 // Eagerly stop after the first pattern fires.
526 // Cleanup instructions of the alternative code sequence. There is no
528 MachineFunction *MF = MBB->getParent();
529 for (auto *InstrPtr : InsInstrs)
530 MF->DeleteMachineInstr(InstrPtr);
532 InstrIdxForVirtReg.clear();
536 if (Changed && IncrementalUpdate)
537 Traces->invalidate(MBB);
541 bool MachineCombiner::runOnMachineFunction(MachineFunction &MF) {
542 const TargetSubtargetInfo &STI = MF.getSubtarget();
543 TII = STI.getInstrInfo();
544 TRI = STI.getRegisterInfo();
545 SchedModel = STI.getSchedModel();
546 TSchedModel.init(SchedModel, &STI, TII);
547 MRI = &MF.getRegInfo();
548 MLI = &getAnalysis<MachineLoopInfo>();
549 Traces = &getAnalysis<MachineTraceMetrics>();
551 OptSize = MF.getFunction().optForSize();
553 DEBUG(dbgs() << getPassName() << ": " << MF.getName() << '\n');
554 if (!TII->useMachineCombiner()) {
555 DEBUG(dbgs() << " Skipping pass: Target does not support machine combiner\n");
559 bool Changed = false;
561 // Try to combine instructions.
563 Changed |= combineInstructions(&MBB);