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