1 //===- TwoAddressInstructionPass.cpp - Two-Address instruction pass -------===// 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 // This file implements the TwoAddress instruction pass which is used 10 // by most register allocators. Two-Address instructions are rewritten 11 // from: 12 // 13 // A = B op C 14 // 15 // to: 16 // 17 // A = B 18 // A op= C 19 // 20 // Note that if a register allocator chooses to use this pass, that it 21 // has to be capable of handling the non-SSA nature of these rewritten 22 // virtual registers. 23 // 24 // It is also worth noting that the duplicate operand of the two 25 // address instruction is removed. 26 // 27 //===----------------------------------------------------------------------===// 28 29 #include "llvm/CodeGen/TwoAddressInstructionPass.h" 30 #include "llvm/ADT/DenseMap.h" 31 #include "llvm/ADT/SmallPtrSet.h" 32 #include "llvm/ADT/SmallVector.h" 33 #include "llvm/ADT/Statistic.h" 34 #include "llvm/ADT/iterator_range.h" 35 #include "llvm/Analysis/AliasAnalysis.h" 36 #include "llvm/CodeGen/LiveInterval.h" 37 #include "llvm/CodeGen/LiveIntervals.h" 38 #include "llvm/CodeGen/LiveVariables.h" 39 #include "llvm/CodeGen/MachineBasicBlock.h" 40 #include "llvm/CodeGen/MachineDominators.h" 41 #include "llvm/CodeGen/MachineFunction.h" 42 #include "llvm/CodeGen/MachineFunctionPass.h" 43 #include "llvm/CodeGen/MachineInstr.h" 44 #include "llvm/CodeGen/MachineInstrBuilder.h" 45 #include "llvm/CodeGen/MachineLoopInfo.h" 46 #include "llvm/CodeGen/MachineOperand.h" 47 #include "llvm/CodeGen/MachineRegisterInfo.h" 48 #include "llvm/CodeGen/Passes.h" 49 #include "llvm/CodeGen/SlotIndexes.h" 50 #include "llvm/CodeGen/TargetInstrInfo.h" 51 #include "llvm/CodeGen/TargetOpcodes.h" 52 #include "llvm/CodeGen/TargetRegisterInfo.h" 53 #include "llvm/CodeGen/TargetSubtargetInfo.h" 54 #include "llvm/MC/MCInstrDesc.h" 55 #include "llvm/Pass.h" 56 #include "llvm/Support/CodeGen.h" 57 #include "llvm/Support/CommandLine.h" 58 #include "llvm/Support/Debug.h" 59 #include "llvm/Support/ErrorHandling.h" 60 #include "llvm/Support/raw_ostream.h" 61 #include "llvm/Target/TargetMachine.h" 62 #include <cassert> 63 #include <iterator> 64 #include <utility> 65 66 using namespace llvm; 67 68 #define DEBUG_TYPE "twoaddressinstruction" 69 70 STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions"); 71 STATISTIC(NumCommuted , "Number of instructions commuted to coalesce"); 72 STATISTIC(NumAggrCommuted , "Number of instructions aggressively commuted"); 73 STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address"); 74 STATISTIC(NumReSchedUps, "Number of instructions re-scheduled up"); 75 STATISTIC(NumReSchedDowns, "Number of instructions re-scheduled down"); 76 77 // Temporary flag to disable rescheduling. 78 static cl::opt<bool> 79 EnableRescheduling("twoaddr-reschedule", 80 cl::desc("Coalesce copies by rescheduling (default=true)"), 81 cl::init(true), cl::Hidden); 82 83 // Limit the number of dataflow edges to traverse when evaluating the benefit 84 // of commuting operands. 85 static cl::opt<unsigned> MaxDataFlowEdge( 86 "dataflow-edge-limit", cl::Hidden, cl::init(3), 87 cl::desc("Maximum number of dataflow edges to traverse when evaluating " 88 "the benefit of commuting operands")); 89 90 namespace { 91 92 class TwoAddressInstructionImpl { 93 MachineFunction *MF = nullptr; 94 const TargetInstrInfo *TII = nullptr; 95 const TargetRegisterInfo *TRI = nullptr; 96 const InstrItineraryData *InstrItins = nullptr; 97 MachineRegisterInfo *MRI = nullptr; 98 LiveVariables *LV = nullptr; 99 LiveIntervals *LIS = nullptr; 100 AliasAnalysis *AA = nullptr; 101 CodeGenOptLevel OptLevel = CodeGenOptLevel::None; 102 103 // The current basic block being processed. 104 MachineBasicBlock *MBB = nullptr; 105 106 // Keep track the distance of a MI from the start of the current basic block. 107 DenseMap<MachineInstr*, unsigned> DistanceMap; 108 109 // Set of already processed instructions in the current block. 110 SmallPtrSet<MachineInstr*, 8> Processed; 111 112 // A map from virtual registers to physical registers which are likely targets 113 // to be coalesced to due to copies from physical registers to virtual 114 // registers. e.g. v1024 = move r0. 115 DenseMap<Register, Register> SrcRegMap; 116 117 // A map from virtual registers to physical registers which are likely targets 118 // to be coalesced to due to copies to physical registers from virtual 119 // registers. e.g. r1 = move v1024. 120 DenseMap<Register, Register> DstRegMap; 121 122 MachineInstr *getSingleDef(Register Reg, MachineBasicBlock *BB) const; 123 124 bool isRevCopyChain(Register FromReg, Register ToReg, int Maxlen); 125 126 bool noUseAfterLastDef(Register Reg, unsigned Dist, unsigned &LastDef); 127 128 bool isCopyToReg(MachineInstr &MI, Register &SrcReg, Register &DstReg, 129 bool &IsSrcPhys, bool &IsDstPhys) const; 130 131 bool isPlainlyKilled(const MachineInstr *MI, LiveRange &LR) const; 132 bool isPlainlyKilled(const MachineInstr *MI, Register Reg) const; 133 bool isPlainlyKilled(const MachineOperand &MO) const; 134 135 bool isKilled(MachineInstr &MI, Register Reg, bool allowFalsePositives) const; 136 137 MachineInstr *findOnlyInterestingUse(Register Reg, MachineBasicBlock *MBB, 138 bool &IsCopy, Register &DstReg, 139 bool &IsDstPhys) const; 140 141 bool regsAreCompatible(Register RegA, Register RegB) const; 142 143 void removeMapRegEntry(const MachineOperand &MO, 144 DenseMap<Register, Register> &RegMap) const; 145 146 void removeClobberedSrcRegMap(MachineInstr *MI); 147 148 bool regOverlapsSet(const SmallVectorImpl<Register> &Set, Register Reg) const; 149 150 bool isProfitableToCommute(Register RegA, Register RegB, Register RegC, 151 MachineInstr *MI, unsigned Dist); 152 153 bool commuteInstruction(MachineInstr *MI, unsigned DstIdx, 154 unsigned RegBIdx, unsigned RegCIdx, unsigned Dist); 155 156 bool isProfitableToConv3Addr(Register RegA, Register RegB); 157 158 bool convertInstTo3Addr(MachineBasicBlock::iterator &mi, 159 MachineBasicBlock::iterator &nmi, Register RegA, 160 Register RegB, unsigned &Dist); 161 162 bool isDefTooClose(Register Reg, unsigned Dist, MachineInstr *MI); 163 164 bool rescheduleMIBelowKill(MachineBasicBlock::iterator &mi, 165 MachineBasicBlock::iterator &nmi, Register Reg); 166 bool rescheduleKillAboveMI(MachineBasicBlock::iterator &mi, 167 MachineBasicBlock::iterator &nmi, Register Reg); 168 169 bool tryInstructionTransform(MachineBasicBlock::iterator &mi, 170 MachineBasicBlock::iterator &nmi, 171 unsigned SrcIdx, unsigned DstIdx, 172 unsigned &Dist, bool shouldOnlyCommute); 173 174 bool tryInstructionCommute(MachineInstr *MI, 175 unsigned DstOpIdx, 176 unsigned BaseOpIdx, 177 bool BaseOpKilled, 178 unsigned Dist); 179 void scanUses(Register DstReg); 180 181 void processCopy(MachineInstr *MI); 182 183 using TiedPairList = SmallVector<std::pair<unsigned, unsigned>, 4>; 184 using TiedOperandMap = SmallDenseMap<unsigned, TiedPairList>; 185 186 bool collectTiedOperands(MachineInstr *MI, TiedOperandMap&); 187 void processTiedPairs(MachineInstr *MI, TiedPairList&, unsigned &Dist); 188 void eliminateRegSequence(MachineBasicBlock::iterator&); 189 bool processStatepoint(MachineInstr *MI, TiedOperandMap &TiedOperands); 190 191 public: 192 TwoAddressInstructionImpl(MachineFunction &MF, MachineFunctionPass *P); 193 TwoAddressInstructionImpl(MachineFunction &MF, 194 MachineFunctionAnalysisManager &MFAM); 195 void setOptLevel(CodeGenOptLevel Level) { OptLevel = Level; } 196 bool run(); 197 }; 198 199 class TwoAddressInstructionLegacyPass : public MachineFunctionPass { 200 public: 201 static char ID; // Pass identification, replacement for typeid 202 203 TwoAddressInstructionLegacyPass() : MachineFunctionPass(ID) { 204 initializeTwoAddressInstructionLegacyPassPass( 205 *PassRegistry::getPassRegistry()); 206 } 207 208 /// Pass entry point. 209 bool runOnMachineFunction(MachineFunction &MF) override { 210 TwoAddressInstructionImpl Impl(MF, this); 211 // Disable optimizations if requested. We cannot skip the whole pass as some 212 // fixups are necessary for correctness. 213 if (skipFunction(MF.getFunction())) 214 Impl.setOptLevel(CodeGenOptLevel::None); 215 return Impl.run(); 216 } 217 218 void getAnalysisUsage(AnalysisUsage &AU) const override { 219 AU.setPreservesCFG(); 220 AU.addUsedIfAvailable<AAResultsWrapperPass>(); 221 AU.addUsedIfAvailable<LiveVariablesWrapperPass>(); 222 AU.addPreserved<LiveVariablesWrapperPass>(); 223 AU.addPreserved<SlotIndexesWrapperPass>(); 224 AU.addPreserved<LiveIntervalsWrapperPass>(); 225 AU.addPreservedID(MachineLoopInfoID); 226 AU.addPreservedID(MachineDominatorsID); 227 MachineFunctionPass::getAnalysisUsage(AU); 228 } 229 }; 230 231 } // end anonymous namespace 232 233 PreservedAnalyses 234 TwoAddressInstructionPass::run(MachineFunction &MF, 235 MachineFunctionAnalysisManager &MFAM) { 236 // Disable optimizations if requested. We cannot skip the whole pass as some 237 // fixups are necessary for correctness. 238 TwoAddressInstructionImpl Impl(MF, MFAM); 239 if (MF.getFunction().hasOptNone()) 240 Impl.setOptLevel(CodeGenOptLevel::None); 241 242 MFPropsModifier _(*this, MF); 243 bool Changed = Impl.run(); 244 if (!Changed) 245 return PreservedAnalyses::all(); 246 auto PA = getMachineFunctionPassPreservedAnalyses(); 247 PA.preserve<LiveIntervalsAnalysis>(); 248 PA.preserve<LiveVariablesAnalysis>(); 249 PA.preserve<MachineDominatorTreeAnalysis>(); 250 PA.preserve<MachineLoopAnalysis>(); 251 PA.preserve<SlotIndexesAnalysis>(); 252 PA.preserveSet<CFGAnalyses>(); 253 return PA; 254 } 255 256 char TwoAddressInstructionLegacyPass::ID = 0; 257 258 char &llvm::TwoAddressInstructionPassID = TwoAddressInstructionLegacyPass::ID; 259 260 INITIALIZE_PASS_BEGIN(TwoAddressInstructionLegacyPass, DEBUG_TYPE, 261 "Two-Address instruction pass", false, false) 262 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 263 INITIALIZE_PASS_END(TwoAddressInstructionLegacyPass, DEBUG_TYPE, 264 "Two-Address instruction pass", false, false) 265 266 TwoAddressInstructionImpl::TwoAddressInstructionImpl( 267 MachineFunction &Func, MachineFunctionAnalysisManager &MFAM) 268 : MF(&Func), TII(Func.getSubtarget().getInstrInfo()), 269 TRI(Func.getSubtarget().getRegisterInfo()), 270 InstrItins(Func.getSubtarget().getInstrItineraryData()), 271 MRI(&Func.getRegInfo()), 272 LV(MFAM.getCachedResult<LiveVariablesAnalysis>(Func)), 273 LIS(MFAM.getCachedResult<LiveIntervalsAnalysis>(Func)), 274 OptLevel(Func.getTarget().getOptLevel()) { 275 auto &FAM = MFAM.getResult<FunctionAnalysisManagerMachineFunctionProxy>(Func) 276 .getManager(); 277 AA = FAM.getCachedResult<AAManager>(Func.getFunction()); 278 } 279 280 TwoAddressInstructionImpl::TwoAddressInstructionImpl(MachineFunction &Func, 281 MachineFunctionPass *P) 282 : MF(&Func), TII(Func.getSubtarget().getInstrInfo()), 283 TRI(Func.getSubtarget().getRegisterInfo()), 284 InstrItins(Func.getSubtarget().getInstrItineraryData()), 285 MRI(&Func.getRegInfo()), OptLevel(Func.getTarget().getOptLevel()) { 286 auto *LVWrapper = P->getAnalysisIfAvailable<LiveVariablesWrapperPass>(); 287 LV = LVWrapper ? &LVWrapper->getLV() : nullptr; 288 auto *LISWrapper = P->getAnalysisIfAvailable<LiveIntervalsWrapperPass>(); 289 LIS = LISWrapper ? &LISWrapper->getLIS() : nullptr; 290 if (auto *AAPass = P->getAnalysisIfAvailable<AAResultsWrapperPass>()) 291 AA = &AAPass->getAAResults(); 292 else 293 AA = nullptr; 294 } 295 296 /// Return the MachineInstr* if it is the single def of the Reg in current BB. 297 MachineInstr * 298 TwoAddressInstructionImpl::getSingleDef(Register Reg, 299 MachineBasicBlock *BB) const { 300 MachineInstr *Ret = nullptr; 301 for (MachineInstr &DefMI : MRI->def_instructions(Reg)) { 302 if (DefMI.getParent() != BB || DefMI.isDebugValue()) 303 continue; 304 if (!Ret) 305 Ret = &DefMI; 306 else if (Ret != &DefMI) 307 return nullptr; 308 } 309 return Ret; 310 } 311 312 /// Check if there is a reversed copy chain from FromReg to ToReg: 313 /// %Tmp1 = copy %Tmp2; 314 /// %FromReg = copy %Tmp1; 315 /// %ToReg = add %FromReg ... 316 /// %Tmp2 = copy %ToReg; 317 /// MaxLen specifies the maximum length of the copy chain the func 318 /// can walk through. 319 bool TwoAddressInstructionImpl::isRevCopyChain(Register FromReg, Register ToReg, 320 int Maxlen) { 321 Register TmpReg = FromReg; 322 for (int i = 0; i < Maxlen; i++) { 323 MachineInstr *Def = getSingleDef(TmpReg, MBB); 324 if (!Def || !Def->isCopy()) 325 return false; 326 327 TmpReg = Def->getOperand(1).getReg(); 328 329 if (TmpReg == ToReg) 330 return true; 331 } 332 return false; 333 } 334 335 /// Return true if there are no intervening uses between the last instruction 336 /// in the MBB that defines the specified register and the two-address 337 /// instruction which is being processed. It also returns the last def location 338 /// by reference. 339 bool TwoAddressInstructionImpl::noUseAfterLastDef(Register Reg, unsigned Dist, 340 unsigned &LastDef) { 341 LastDef = 0; 342 unsigned LastUse = Dist; 343 for (MachineOperand &MO : MRI->reg_operands(Reg)) { 344 MachineInstr *MI = MO.getParent(); 345 if (MI->getParent() != MBB || MI->isDebugValue()) 346 continue; 347 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); 348 if (DI == DistanceMap.end()) 349 continue; 350 if (MO.isUse() && DI->second < LastUse) 351 LastUse = DI->second; 352 if (MO.isDef() && DI->second > LastDef) 353 LastDef = DI->second; 354 } 355 356 return !(LastUse > LastDef && LastUse < Dist); 357 } 358 359 /// Return true if the specified MI is a copy instruction or an extract_subreg 360 /// instruction. It also returns the source and destination registers and 361 /// whether they are physical registers by reference. 362 bool TwoAddressInstructionImpl::isCopyToReg(MachineInstr &MI, Register &SrcReg, 363 Register &DstReg, bool &IsSrcPhys, 364 bool &IsDstPhys) const { 365 SrcReg = 0; 366 DstReg = 0; 367 if (MI.isCopy()) { 368 DstReg = MI.getOperand(0).getReg(); 369 SrcReg = MI.getOperand(1).getReg(); 370 } else if (MI.isInsertSubreg() || MI.isSubregToReg()) { 371 DstReg = MI.getOperand(0).getReg(); 372 SrcReg = MI.getOperand(2).getReg(); 373 } else { 374 return false; 375 } 376 377 IsSrcPhys = SrcReg.isPhysical(); 378 IsDstPhys = DstReg.isPhysical(); 379 return true; 380 } 381 382 bool TwoAddressInstructionImpl::isPlainlyKilled(const MachineInstr *MI, 383 LiveRange &LR) const { 384 // This is to match the kill flag version where undefs don't have kill flags. 385 if (!LR.hasAtLeastOneValue()) 386 return false; 387 388 SlotIndex useIdx = LIS->getInstructionIndex(*MI); 389 LiveInterval::const_iterator I = LR.find(useIdx); 390 assert(I != LR.end() && "Reg must be live-in to use."); 391 return !I->end.isBlock() && SlotIndex::isSameInstr(I->end, useIdx); 392 } 393 394 /// Test if the given register value, which is used by the 395 /// given instruction, is killed by the given instruction. 396 bool TwoAddressInstructionImpl::isPlainlyKilled(const MachineInstr *MI, 397 Register Reg) const { 398 // FIXME: Sometimes tryInstructionTransform() will add instructions and 399 // test whether they can be folded before keeping them. In this case it 400 // sets a kill before recursively calling tryInstructionTransform() again. 401 // If there is no interval available, we assume that this instruction is 402 // one of those. A kill flag is manually inserted on the operand so the 403 // check below will handle it. 404 if (LIS && !LIS->isNotInMIMap(*MI)) { 405 if (Reg.isVirtual()) 406 return isPlainlyKilled(MI, LIS->getInterval(Reg)); 407 // Reserved registers are considered always live. 408 if (MRI->isReserved(Reg)) 409 return false; 410 return all_of(TRI->regunits(Reg), [&](MCRegUnit U) { 411 return isPlainlyKilled(MI, LIS->getRegUnit(U)); 412 }); 413 } 414 415 return MI->killsRegister(Reg, /*TRI=*/nullptr); 416 } 417 418 /// Test if the register used by the given operand is killed by the operand's 419 /// instruction. 420 bool TwoAddressInstructionImpl::isPlainlyKilled( 421 const MachineOperand &MO) const { 422 return MO.isKill() || isPlainlyKilled(MO.getParent(), MO.getReg()); 423 } 424 425 /// Test if the given register value, which is used by the given 426 /// instruction, is killed by the given instruction. This looks through 427 /// coalescable copies to see if the original value is potentially not killed. 428 /// 429 /// For example, in this code: 430 /// 431 /// %reg1034 = copy %reg1024 432 /// %reg1035 = copy killed %reg1025 433 /// %reg1036 = add killed %reg1034, killed %reg1035 434 /// 435 /// %reg1034 is not considered to be killed, since it is copied from a 436 /// register which is not killed. Treating it as not killed lets the 437 /// normal heuristics commute the (two-address) add, which lets 438 /// coalescing eliminate the extra copy. 439 /// 440 /// If allowFalsePositives is true then likely kills are treated as kills even 441 /// if it can't be proven that they are kills. 442 bool TwoAddressInstructionImpl::isKilled(MachineInstr &MI, Register Reg, 443 bool allowFalsePositives) const { 444 MachineInstr *DefMI = &MI; 445 while (true) { 446 // All uses of physical registers are likely to be kills. 447 if (Reg.isPhysical() && (allowFalsePositives || MRI->hasOneUse(Reg))) 448 return true; 449 if (!isPlainlyKilled(DefMI, Reg)) 450 return false; 451 if (Reg.isPhysical()) 452 return true; 453 MachineRegisterInfo::def_iterator Begin = MRI->def_begin(Reg); 454 // If there are multiple defs, we can't do a simple analysis, so just 455 // go with what the kill flag says. 456 if (std::next(Begin) != MRI->def_end()) 457 return true; 458 DefMI = Begin->getParent(); 459 bool IsSrcPhys, IsDstPhys; 460 Register SrcReg, DstReg; 461 // If the def is something other than a copy, then it isn't going to 462 // be coalesced, so follow the kill flag. 463 if (!isCopyToReg(*DefMI, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) 464 return true; 465 Reg = SrcReg; 466 } 467 } 468 469 /// Return true if the specified MI uses the specified register as a two-address 470 /// use. If so, return the destination register by reference. 471 static bool isTwoAddrUse(MachineInstr &MI, Register Reg, Register &DstReg) { 472 for (unsigned i = 0, NumOps = MI.getNumOperands(); i != NumOps; ++i) { 473 const MachineOperand &MO = MI.getOperand(i); 474 if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg) 475 continue; 476 unsigned ti; 477 if (MI.isRegTiedToDefOperand(i, &ti)) { 478 DstReg = MI.getOperand(ti).getReg(); 479 return true; 480 } 481 } 482 return false; 483 } 484 485 /// Given a register, if all its uses are in the same basic block, return the 486 /// last use instruction if it's a copy or a two-address use. 487 MachineInstr *TwoAddressInstructionImpl::findOnlyInterestingUse( 488 Register Reg, MachineBasicBlock *MBB, bool &IsCopy, Register &DstReg, 489 bool &IsDstPhys) const { 490 MachineOperand *UseOp = nullptr; 491 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) { 492 MachineInstr *MI = MO.getParent(); 493 if (MI->getParent() != MBB) 494 return nullptr; 495 if (isPlainlyKilled(MI, Reg)) 496 UseOp = &MO; 497 } 498 if (!UseOp) 499 return nullptr; 500 MachineInstr &UseMI = *UseOp->getParent(); 501 502 Register SrcReg; 503 bool IsSrcPhys; 504 if (isCopyToReg(UseMI, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) { 505 IsCopy = true; 506 return &UseMI; 507 } 508 IsDstPhys = false; 509 if (isTwoAddrUse(UseMI, Reg, DstReg)) { 510 IsDstPhys = DstReg.isPhysical(); 511 return &UseMI; 512 } 513 if (UseMI.isCommutable()) { 514 unsigned Src1 = TargetInstrInfo::CommuteAnyOperandIndex; 515 unsigned Src2 = UseOp->getOperandNo(); 516 if (TII->findCommutedOpIndices(UseMI, Src1, Src2)) { 517 MachineOperand &MO = UseMI.getOperand(Src1); 518 if (MO.isReg() && MO.isUse() && 519 isTwoAddrUse(UseMI, MO.getReg(), DstReg)) { 520 IsDstPhys = DstReg.isPhysical(); 521 return &UseMI; 522 } 523 } 524 } 525 return nullptr; 526 } 527 528 /// Return the physical register the specified virtual register might be mapped 529 /// to. 530 static MCRegister getMappedReg(Register Reg, 531 DenseMap<Register, Register> &RegMap) { 532 while (Reg.isVirtual()) { 533 DenseMap<Register, Register>::iterator SI = RegMap.find(Reg); 534 if (SI == RegMap.end()) 535 return 0; 536 Reg = SI->second; 537 } 538 if (Reg.isPhysical()) 539 return Reg; 540 return 0; 541 } 542 543 /// Return true if the two registers are equal or aliased. 544 bool TwoAddressInstructionImpl::regsAreCompatible(Register RegA, 545 Register RegB) const { 546 if (RegA == RegB) 547 return true; 548 if (!RegA || !RegB) 549 return false; 550 return TRI->regsOverlap(RegA, RegB); 551 } 552 553 /// From RegMap remove entries mapped to a physical register which overlaps MO. 554 void TwoAddressInstructionImpl::removeMapRegEntry( 555 const MachineOperand &MO, DenseMap<Register, Register> &RegMap) const { 556 assert( 557 (MO.isReg() || MO.isRegMask()) && 558 "removeMapRegEntry must be called with a register or regmask operand."); 559 560 SmallVector<Register, 2> Srcs; 561 for (auto SI : RegMap) { 562 Register ToReg = SI.second; 563 if (ToReg.isVirtual()) 564 continue; 565 566 if (MO.isReg()) { 567 Register Reg = MO.getReg(); 568 if (TRI->regsOverlap(ToReg, Reg)) 569 Srcs.push_back(SI.first); 570 } else if (MO.clobbersPhysReg(ToReg)) 571 Srcs.push_back(SI.first); 572 } 573 574 for (auto SrcReg : Srcs) 575 RegMap.erase(SrcReg); 576 } 577 578 /// If a physical register is clobbered, old entries mapped to it should be 579 /// deleted. For example 580 /// 581 /// %2:gr64 = COPY killed $rdx 582 /// MUL64r %3:gr64, implicit-def $rax, implicit-def $rdx 583 /// 584 /// After the MUL instruction, $rdx contains different value than in the COPY 585 /// instruction. So %2 should not map to $rdx after MUL. 586 void TwoAddressInstructionImpl::removeClobberedSrcRegMap(MachineInstr *MI) { 587 if (MI->isCopy()) { 588 // If a virtual register is copied to its mapped physical register, it 589 // doesn't change the potential coalescing between them, so we don't remove 590 // entries mapped to the physical register. For example 591 // 592 // %100 = COPY $r8 593 // ... 594 // $r8 = COPY %100 595 // 596 // The first copy constructs SrcRegMap[%100] = $r8, the second copy doesn't 597 // destroy the content of $r8, and should not impact SrcRegMap. 598 Register Dst = MI->getOperand(0).getReg(); 599 if (!Dst || Dst.isVirtual()) 600 return; 601 602 Register Src = MI->getOperand(1).getReg(); 603 if (regsAreCompatible(Dst, getMappedReg(Src, SrcRegMap))) 604 return; 605 } 606 607 for (const MachineOperand &MO : MI->operands()) { 608 if (MO.isRegMask()) { 609 removeMapRegEntry(MO, SrcRegMap); 610 continue; 611 } 612 if (!MO.isReg() || !MO.isDef()) 613 continue; 614 Register Reg = MO.getReg(); 615 if (!Reg || Reg.isVirtual()) 616 continue; 617 removeMapRegEntry(MO, SrcRegMap); 618 } 619 } 620 621 // Returns true if Reg is equal or aliased to at least one register in Set. 622 bool TwoAddressInstructionImpl::regOverlapsSet( 623 const SmallVectorImpl<Register> &Set, Register Reg) const { 624 for (unsigned R : Set) 625 if (TRI->regsOverlap(R, Reg)) 626 return true; 627 628 return false; 629 } 630 631 /// Return true if it's potentially profitable to commute the two-address 632 /// instruction that's being processed. 633 bool TwoAddressInstructionImpl::isProfitableToCommute(Register RegA, 634 Register RegB, 635 Register RegC, 636 MachineInstr *MI, 637 unsigned Dist) { 638 if (OptLevel == CodeGenOptLevel::None) 639 return false; 640 641 // Determine if it's profitable to commute this two address instruction. In 642 // general, we want no uses between this instruction and the definition of 643 // the two-address register. 644 // e.g. 645 // %reg1028 = EXTRACT_SUBREG killed %reg1027, 1 646 // %reg1029 = COPY %reg1028 647 // %reg1029 = SHR8ri %reg1029, 7, implicit dead %eflags 648 // insert => %reg1030 = COPY %reg1028 649 // %reg1030 = ADD8rr killed %reg1028, killed %reg1029, implicit dead %eflags 650 // In this case, it might not be possible to coalesce the second COPY 651 // instruction if the first one is coalesced. So it would be profitable to 652 // commute it: 653 // %reg1028 = EXTRACT_SUBREG killed %reg1027, 1 654 // %reg1029 = COPY %reg1028 655 // %reg1029 = SHR8ri %reg1029, 7, implicit dead %eflags 656 // insert => %reg1030 = COPY %reg1029 657 // %reg1030 = ADD8rr killed %reg1029, killed %reg1028, implicit dead %eflags 658 659 if (!isPlainlyKilled(MI, RegC)) 660 return false; 661 662 // Ok, we have something like: 663 // %reg1030 = ADD8rr killed %reg1028, killed %reg1029, implicit dead %eflags 664 // let's see if it's worth commuting it. 665 666 // Look for situations like this: 667 // %reg1024 = MOV r1 668 // %reg1025 = MOV r0 669 // %reg1026 = ADD %reg1024, %reg1025 670 // r0 = MOV %reg1026 671 // Commute the ADD to hopefully eliminate an otherwise unavoidable copy. 672 MCRegister ToRegA = getMappedReg(RegA, DstRegMap); 673 if (ToRegA) { 674 MCRegister FromRegB = getMappedReg(RegB, SrcRegMap); 675 MCRegister FromRegC = getMappedReg(RegC, SrcRegMap); 676 bool CompB = FromRegB && regsAreCompatible(FromRegB, ToRegA); 677 bool CompC = FromRegC && regsAreCompatible(FromRegC, ToRegA); 678 679 // Compute if any of the following are true: 680 // -RegB is not tied to a register and RegC is compatible with RegA. 681 // -RegB is tied to the wrong physical register, but RegC is. 682 // -RegB is tied to the wrong physical register, and RegC isn't tied. 683 if ((!FromRegB && CompC) || (FromRegB && !CompB && (!FromRegC || CompC))) 684 return true; 685 // Don't compute if any of the following are true: 686 // -RegC is not tied to a register and RegB is compatible with RegA. 687 // -RegC is tied to the wrong physical register, but RegB is. 688 // -RegC is tied to the wrong physical register, and RegB isn't tied. 689 if ((!FromRegC && CompB) || (FromRegC && !CompC && (!FromRegB || CompB))) 690 return false; 691 } 692 693 // If there is a use of RegC between its last def (could be livein) and this 694 // instruction, then bail. 695 unsigned LastDefC = 0; 696 if (!noUseAfterLastDef(RegC, Dist, LastDefC)) 697 return false; 698 699 // If there is a use of RegB between its last def (could be livein) and this 700 // instruction, then go ahead and make this transformation. 701 unsigned LastDefB = 0; 702 if (!noUseAfterLastDef(RegB, Dist, LastDefB)) 703 return true; 704 705 // Look for situation like this: 706 // %reg101 = MOV %reg100 707 // %reg102 = ... 708 // %reg103 = ADD %reg102, %reg101 709 // ... = %reg103 ... 710 // %reg100 = MOV %reg103 711 // If there is a reversed copy chain from reg101 to reg103, commute the ADD 712 // to eliminate an otherwise unavoidable copy. 713 // FIXME: 714 // We can extend the logic further: If an pair of operands in an insn has 715 // been merged, the insn could be regarded as a virtual copy, and the virtual 716 // copy could also be used to construct a copy chain. 717 // To more generally minimize register copies, ideally the logic of two addr 718 // instruction pass should be integrated with register allocation pass where 719 // interference graph is available. 720 if (isRevCopyChain(RegC, RegA, MaxDataFlowEdge)) 721 return true; 722 723 if (isRevCopyChain(RegB, RegA, MaxDataFlowEdge)) 724 return false; 725 726 // Look for other target specific commute preference. 727 bool Commute; 728 if (TII->hasCommutePreference(*MI, Commute)) 729 return Commute; 730 731 // Since there are no intervening uses for both registers, then commute 732 // if the def of RegC is closer. Its live interval is shorter. 733 return LastDefB && LastDefC && LastDefC > LastDefB; 734 } 735 736 /// Commute a two-address instruction and update the basic block, distance map, 737 /// and live variables if needed. Return true if it is successful. 738 bool TwoAddressInstructionImpl::commuteInstruction(MachineInstr *MI, 739 unsigned DstIdx, 740 unsigned RegBIdx, 741 unsigned RegCIdx, 742 unsigned Dist) { 743 Register RegC = MI->getOperand(RegCIdx).getReg(); 744 LLVM_DEBUG(dbgs() << "2addr: COMMUTING : " << *MI); 745 MachineInstr *NewMI = TII->commuteInstruction(*MI, false, RegBIdx, RegCIdx); 746 747 if (NewMI == nullptr) { 748 LLVM_DEBUG(dbgs() << "2addr: COMMUTING FAILED!\n"); 749 return false; 750 } 751 752 LLVM_DEBUG(dbgs() << "2addr: COMMUTED TO: " << *NewMI); 753 assert(NewMI == MI && 754 "TargetInstrInfo::commuteInstruction() should not return a new " 755 "instruction unless it was requested."); 756 757 // Update source register map. 758 MCRegister FromRegC = getMappedReg(RegC, SrcRegMap); 759 if (FromRegC) { 760 Register RegA = MI->getOperand(DstIdx).getReg(); 761 SrcRegMap[RegA] = FromRegC; 762 } 763 764 return true; 765 } 766 767 /// Return true if it is profitable to convert the given 2-address instruction 768 /// to a 3-address one. 769 bool TwoAddressInstructionImpl::isProfitableToConv3Addr(Register RegA, 770 Register RegB) { 771 // Look for situations like this: 772 // %reg1024 = MOV r1 773 // %reg1025 = MOV r0 774 // %reg1026 = ADD %reg1024, %reg1025 775 // r2 = MOV %reg1026 776 // Turn ADD into a 3-address instruction to avoid a copy. 777 MCRegister FromRegB = getMappedReg(RegB, SrcRegMap); 778 if (!FromRegB) 779 return false; 780 MCRegister ToRegA = getMappedReg(RegA, DstRegMap); 781 return (ToRegA && !regsAreCompatible(FromRegB, ToRegA)); 782 } 783 784 /// Convert the specified two-address instruction into a three address one. 785 /// Return true if this transformation was successful. 786 bool TwoAddressInstructionImpl::convertInstTo3Addr( 787 MachineBasicBlock::iterator &mi, MachineBasicBlock::iterator &nmi, 788 Register RegA, Register RegB, unsigned &Dist) { 789 MachineInstrSpan MIS(mi, MBB); 790 MachineInstr *NewMI = TII->convertToThreeAddress(*mi, LV, LIS); 791 if (!NewMI) 792 return false; 793 794 LLVM_DEBUG(dbgs() << "2addr: CONVERTING 2-ADDR: " << *mi); 795 LLVM_DEBUG(dbgs() << "2addr: TO 3-ADDR: " << *NewMI); 796 797 // If the old instruction is debug value tracked, an update is required. 798 if (auto OldInstrNum = mi->peekDebugInstrNum()) { 799 assert(mi->getNumExplicitDefs() == 1); 800 assert(NewMI->getNumExplicitDefs() == 1); 801 802 // Find the old and new def location. 803 unsigned OldIdx = mi->defs().begin()->getOperandNo(); 804 unsigned NewIdx = NewMI->defs().begin()->getOperandNo(); 805 806 // Record that one def has been replaced by the other. 807 unsigned NewInstrNum = NewMI->getDebugInstrNum(); 808 MF->makeDebugValueSubstitution(std::make_pair(OldInstrNum, OldIdx), 809 std::make_pair(NewInstrNum, NewIdx)); 810 } 811 812 MBB->erase(mi); // Nuke the old inst. 813 814 for (MachineInstr &MI : MIS) 815 DistanceMap.insert(std::make_pair(&MI, Dist++)); 816 Dist--; 817 mi = NewMI; 818 nmi = std::next(mi); 819 820 // Update source and destination register maps. 821 SrcRegMap.erase(RegA); 822 DstRegMap.erase(RegB); 823 return true; 824 } 825 826 /// Scan forward recursively for only uses, update maps if the use is a copy or 827 /// a two-address instruction. 828 void TwoAddressInstructionImpl::scanUses(Register DstReg) { 829 SmallVector<Register, 4> VirtRegPairs; 830 bool IsDstPhys; 831 bool IsCopy = false; 832 Register NewReg; 833 Register Reg = DstReg; 834 while (MachineInstr *UseMI = 835 findOnlyInterestingUse(Reg, MBB, IsCopy, NewReg, IsDstPhys)) { 836 if (IsCopy && !Processed.insert(UseMI).second) 837 break; 838 839 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI); 840 if (DI != DistanceMap.end()) 841 // Earlier in the same MBB.Reached via a back edge. 842 break; 843 844 if (IsDstPhys) { 845 VirtRegPairs.push_back(NewReg); 846 break; 847 } 848 SrcRegMap[NewReg] = Reg; 849 VirtRegPairs.push_back(NewReg); 850 Reg = NewReg; 851 } 852 853 if (!VirtRegPairs.empty()) { 854 unsigned ToReg = VirtRegPairs.back(); 855 VirtRegPairs.pop_back(); 856 while (!VirtRegPairs.empty()) { 857 unsigned FromReg = VirtRegPairs.pop_back_val(); 858 bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second; 859 if (!isNew) 860 assert(DstRegMap[FromReg] == ToReg &&"Can't map to two dst registers!"); 861 ToReg = FromReg; 862 } 863 bool isNew = DstRegMap.insert(std::make_pair(DstReg, ToReg)).second; 864 if (!isNew) 865 assert(DstRegMap[DstReg] == ToReg && "Can't map to two dst registers!"); 866 } 867 } 868 869 /// If the specified instruction is not yet processed, process it if it's a 870 /// copy. For a copy instruction, we find the physical registers the 871 /// source and destination registers might be mapped to. These are kept in 872 /// point-to maps used to determine future optimizations. e.g. 873 /// v1024 = mov r0 874 /// v1025 = mov r1 875 /// v1026 = add v1024, v1025 876 /// r1 = mov r1026 877 /// If 'add' is a two-address instruction, v1024, v1026 are both potentially 878 /// coalesced to r0 (from the input side). v1025 is mapped to r1. v1026 is 879 /// potentially joined with r1 on the output side. It's worthwhile to commute 880 /// 'add' to eliminate a copy. 881 void TwoAddressInstructionImpl::processCopy(MachineInstr *MI) { 882 if (Processed.count(MI)) 883 return; 884 885 bool IsSrcPhys, IsDstPhys; 886 Register SrcReg, DstReg; 887 if (!isCopyToReg(*MI, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) 888 return; 889 890 if (IsDstPhys && !IsSrcPhys) { 891 DstRegMap.insert(std::make_pair(SrcReg, DstReg)); 892 } else if (!IsDstPhys && IsSrcPhys) { 893 bool isNew = SrcRegMap.insert(std::make_pair(DstReg, SrcReg)).second; 894 if (!isNew) 895 assert(SrcRegMap[DstReg] == SrcReg && 896 "Can't map to two src physical registers!"); 897 898 scanUses(DstReg); 899 } 900 901 Processed.insert(MI); 902 } 903 904 /// If there is one more local instruction that reads 'Reg' and it kills 'Reg, 905 /// consider moving the instruction below the kill instruction in order to 906 /// eliminate the need for the copy. 907 bool TwoAddressInstructionImpl::rescheduleMIBelowKill( 908 MachineBasicBlock::iterator &mi, MachineBasicBlock::iterator &nmi, 909 Register Reg) { 910 // Bail immediately if we don't have LV or LIS available. We use them to find 911 // kills efficiently. 912 if (!LV && !LIS) 913 return false; 914 915 MachineInstr *MI = &*mi; 916 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); 917 if (DI == DistanceMap.end()) 918 // Must be created from unfolded load. Don't waste time trying this. 919 return false; 920 921 MachineInstr *KillMI = nullptr; 922 if (LIS) { 923 LiveInterval &LI = LIS->getInterval(Reg); 924 assert(LI.end() != LI.begin() && 925 "Reg should not have empty live interval."); 926 927 SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot(); 928 LiveInterval::const_iterator I = LI.find(MBBEndIdx); 929 if (I != LI.end() && I->start < MBBEndIdx) 930 return false; 931 932 --I; 933 KillMI = LIS->getInstructionFromIndex(I->end); 934 } else { 935 KillMI = LV->getVarInfo(Reg).findKill(MBB); 936 } 937 if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike()) 938 // Don't mess with copies, they may be coalesced later. 939 return false; 940 941 if (KillMI->hasUnmodeledSideEffects() || KillMI->isCall() || 942 KillMI->isBranch() || KillMI->isTerminator()) 943 // Don't move pass calls, etc. 944 return false; 945 946 Register DstReg; 947 if (isTwoAddrUse(*KillMI, Reg, DstReg)) 948 return false; 949 950 bool SeenStore = true; 951 if (!MI->isSafeToMove(AA, SeenStore)) 952 return false; 953 954 if (TII->getInstrLatency(InstrItins, *MI) > 1) 955 // FIXME: Needs more sophisticated heuristics. 956 return false; 957 958 SmallVector<Register, 2> Uses; 959 SmallVector<Register, 2> Kills; 960 SmallVector<Register, 2> Defs; 961 for (const MachineOperand &MO : MI->operands()) { 962 if (!MO.isReg()) 963 continue; 964 Register MOReg = MO.getReg(); 965 if (!MOReg) 966 continue; 967 if (MO.isDef()) 968 Defs.push_back(MOReg); 969 else { 970 Uses.push_back(MOReg); 971 if (MOReg != Reg && isPlainlyKilled(MO)) 972 Kills.push_back(MOReg); 973 } 974 } 975 976 // Move the copies connected to MI down as well. 977 MachineBasicBlock::iterator Begin = MI; 978 MachineBasicBlock::iterator AfterMI = std::next(Begin); 979 MachineBasicBlock::iterator End = AfterMI; 980 while (End != MBB->end()) { 981 End = skipDebugInstructionsForward(End, MBB->end()); 982 if (End->isCopy() && regOverlapsSet(Defs, End->getOperand(1).getReg())) 983 Defs.push_back(End->getOperand(0).getReg()); 984 else 985 break; 986 ++End; 987 } 988 989 // Check if the reschedule will not break dependencies. 990 unsigned NumVisited = 0; 991 MachineBasicBlock::iterator KillPos = KillMI; 992 ++KillPos; 993 for (MachineInstr &OtherMI : make_range(End, KillPos)) { 994 // Debug or pseudo instructions cannot be counted against the limit. 995 if (OtherMI.isDebugOrPseudoInstr()) 996 continue; 997 if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost. 998 return false; 999 ++NumVisited; 1000 if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() || 1001 OtherMI.isBranch() || OtherMI.isTerminator()) 1002 // Don't move pass calls, etc. 1003 return false; 1004 for (const MachineOperand &MO : OtherMI.operands()) { 1005 if (!MO.isReg()) 1006 continue; 1007 Register MOReg = MO.getReg(); 1008 if (!MOReg) 1009 continue; 1010 if (MO.isDef()) { 1011 if (regOverlapsSet(Uses, MOReg)) 1012 // Physical register use would be clobbered. 1013 return false; 1014 if (!MO.isDead() && regOverlapsSet(Defs, MOReg)) 1015 // May clobber a physical register def. 1016 // FIXME: This may be too conservative. It's ok if the instruction 1017 // is sunken completely below the use. 1018 return false; 1019 } else { 1020 if (regOverlapsSet(Defs, MOReg)) 1021 return false; 1022 bool isKill = isPlainlyKilled(MO); 1023 if (MOReg != Reg && ((isKill && regOverlapsSet(Uses, MOReg)) || 1024 regOverlapsSet(Kills, MOReg))) 1025 // Don't want to extend other live ranges and update kills. 1026 return false; 1027 if (MOReg == Reg && !isKill) 1028 // We can't schedule across a use of the register in question. 1029 return false; 1030 // Ensure that if this is register in question, its the kill we expect. 1031 assert((MOReg != Reg || &OtherMI == KillMI) && 1032 "Found multiple kills of a register in a basic block"); 1033 } 1034 } 1035 } 1036 1037 // Move debug info as well. 1038 while (Begin != MBB->begin() && std::prev(Begin)->isDebugInstr()) 1039 --Begin; 1040 1041 nmi = End; 1042 MachineBasicBlock::iterator InsertPos = KillPos; 1043 if (LIS) { 1044 // We have to move the copies (and any interleaved debug instructions) 1045 // first so that the MBB is still well-formed when calling handleMove(). 1046 for (MachineBasicBlock::iterator MBBI = AfterMI; MBBI != End;) { 1047 auto CopyMI = MBBI++; 1048 MBB->splice(InsertPos, MBB, CopyMI); 1049 if (!CopyMI->isDebugOrPseudoInstr()) 1050 LIS->handleMove(*CopyMI); 1051 InsertPos = CopyMI; 1052 } 1053 End = std::next(MachineBasicBlock::iterator(MI)); 1054 } 1055 1056 // Copies following MI may have been moved as well. 1057 MBB->splice(InsertPos, MBB, Begin, End); 1058 DistanceMap.erase(DI); 1059 1060 // Update live variables 1061 if (LIS) { 1062 LIS->handleMove(*MI); 1063 } else { 1064 LV->removeVirtualRegisterKilled(Reg, *KillMI); 1065 LV->addVirtualRegisterKilled(Reg, *MI); 1066 } 1067 1068 LLVM_DEBUG(dbgs() << "\trescheduled below kill: " << *KillMI); 1069 return true; 1070 } 1071 1072 /// Return true if the re-scheduling will put the given instruction too close 1073 /// to the defs of its register dependencies. 1074 bool TwoAddressInstructionImpl::isDefTooClose(Register Reg, unsigned Dist, 1075 MachineInstr *MI) { 1076 for (MachineInstr &DefMI : MRI->def_instructions(Reg)) { 1077 if (DefMI.getParent() != MBB || DefMI.isCopy() || DefMI.isCopyLike()) 1078 continue; 1079 if (&DefMI == MI) 1080 return true; // MI is defining something KillMI uses 1081 DenseMap<MachineInstr*, unsigned>::iterator DDI = DistanceMap.find(&DefMI); 1082 if (DDI == DistanceMap.end()) 1083 return true; // Below MI 1084 unsigned DefDist = DDI->second; 1085 assert(Dist > DefDist && "Visited def already?"); 1086 if (TII->getInstrLatency(InstrItins, DefMI) > (Dist - DefDist)) 1087 return true; 1088 } 1089 return false; 1090 } 1091 1092 /// If there is one more local instruction that reads 'Reg' and it kills 'Reg, 1093 /// consider moving the kill instruction above the current two-address 1094 /// instruction in order to eliminate the need for the copy. 1095 bool TwoAddressInstructionImpl::rescheduleKillAboveMI( 1096 MachineBasicBlock::iterator &mi, MachineBasicBlock::iterator &nmi, 1097 Register Reg) { 1098 // Bail immediately if we don't have LV or LIS available. We use them to find 1099 // kills efficiently. 1100 if (!LV && !LIS) 1101 return false; 1102 1103 MachineInstr *MI = &*mi; 1104 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); 1105 if (DI == DistanceMap.end()) 1106 // Must be created from unfolded load. Don't waste time trying this. 1107 return false; 1108 1109 MachineInstr *KillMI = nullptr; 1110 if (LIS) { 1111 LiveInterval &LI = LIS->getInterval(Reg); 1112 assert(LI.end() != LI.begin() && 1113 "Reg should not have empty live interval."); 1114 1115 SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot(); 1116 LiveInterval::const_iterator I = LI.find(MBBEndIdx); 1117 if (I != LI.end() && I->start < MBBEndIdx) 1118 return false; 1119 1120 --I; 1121 KillMI = LIS->getInstructionFromIndex(I->end); 1122 } else { 1123 KillMI = LV->getVarInfo(Reg).findKill(MBB); 1124 } 1125 if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike()) 1126 // Don't mess with copies, they may be coalesced later. 1127 return false; 1128 1129 Register DstReg; 1130 if (isTwoAddrUse(*KillMI, Reg, DstReg)) 1131 return false; 1132 1133 bool SeenStore = true; 1134 if (!KillMI->isSafeToMove(AA, SeenStore)) 1135 return false; 1136 1137 SmallVector<Register, 2> Uses; 1138 SmallVector<Register, 2> Kills; 1139 SmallVector<Register, 2> Defs; 1140 SmallVector<Register, 2> LiveDefs; 1141 for (const MachineOperand &MO : KillMI->operands()) { 1142 if (!MO.isReg()) 1143 continue; 1144 Register MOReg = MO.getReg(); 1145 if (MO.isUse()) { 1146 if (!MOReg) 1147 continue; 1148 if (isDefTooClose(MOReg, DI->second, MI)) 1149 return false; 1150 bool isKill = isPlainlyKilled(MO); 1151 if (MOReg == Reg && !isKill) 1152 return false; 1153 Uses.push_back(MOReg); 1154 if (isKill && MOReg != Reg) 1155 Kills.push_back(MOReg); 1156 } else if (MOReg.isPhysical()) { 1157 Defs.push_back(MOReg); 1158 if (!MO.isDead()) 1159 LiveDefs.push_back(MOReg); 1160 } 1161 } 1162 1163 // Check if the reschedule will not break depedencies. 1164 unsigned NumVisited = 0; 1165 for (MachineInstr &OtherMI : 1166 make_range(mi, MachineBasicBlock::iterator(KillMI))) { 1167 // Debug or pseudo instructions cannot be counted against the limit. 1168 if (OtherMI.isDebugOrPseudoInstr()) 1169 continue; 1170 if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost. 1171 return false; 1172 ++NumVisited; 1173 if (OtherMI.hasUnmodeledSideEffects() || OtherMI.isCall() || 1174 OtherMI.isBranch() || OtherMI.isTerminator()) 1175 // Don't move pass calls, etc. 1176 return false; 1177 SmallVector<Register, 2> OtherDefs; 1178 for (const MachineOperand &MO : OtherMI.operands()) { 1179 if (!MO.isReg()) 1180 continue; 1181 Register MOReg = MO.getReg(); 1182 if (!MOReg) 1183 continue; 1184 if (MO.isUse()) { 1185 if (regOverlapsSet(Defs, MOReg)) 1186 // Moving KillMI can clobber the physical register if the def has 1187 // not been seen. 1188 return false; 1189 if (regOverlapsSet(Kills, MOReg)) 1190 // Don't want to extend other live ranges and update kills. 1191 return false; 1192 if (&OtherMI != MI && MOReg == Reg && !isPlainlyKilled(MO)) 1193 // We can't schedule across a use of the register in question. 1194 return false; 1195 } else { 1196 OtherDefs.push_back(MOReg); 1197 } 1198 } 1199 1200 for (Register MOReg : OtherDefs) { 1201 if (regOverlapsSet(Uses, MOReg)) 1202 return false; 1203 if (MOReg.isPhysical() && regOverlapsSet(LiveDefs, MOReg)) 1204 return false; 1205 // Physical register def is seen. 1206 llvm::erase(Defs, MOReg); 1207 } 1208 } 1209 1210 // Move the old kill above MI, don't forget to move debug info as well. 1211 MachineBasicBlock::iterator InsertPos = mi; 1212 while (InsertPos != MBB->begin() && std::prev(InsertPos)->isDebugInstr()) 1213 --InsertPos; 1214 MachineBasicBlock::iterator From = KillMI; 1215 MachineBasicBlock::iterator To = std::next(From); 1216 while (std::prev(From)->isDebugInstr()) 1217 --From; 1218 MBB->splice(InsertPos, MBB, From, To); 1219 1220 nmi = std::prev(InsertPos); // Backtrack so we process the moved instr. 1221 DistanceMap.erase(DI); 1222 1223 // Update live variables 1224 if (LIS) { 1225 LIS->handleMove(*KillMI); 1226 } else { 1227 LV->removeVirtualRegisterKilled(Reg, *KillMI); 1228 LV->addVirtualRegisterKilled(Reg, *MI); 1229 } 1230 1231 LLVM_DEBUG(dbgs() << "\trescheduled kill: " << *KillMI); 1232 return true; 1233 } 1234 1235 /// Tries to commute the operand 'BaseOpIdx' and some other operand in the 1236 /// given machine instruction to improve opportunities for coalescing and 1237 /// elimination of a register to register copy. 1238 /// 1239 /// 'DstOpIdx' specifies the index of MI def operand. 1240 /// 'BaseOpKilled' specifies if the register associated with 'BaseOpIdx' 1241 /// operand is killed by the given instruction. 1242 /// The 'Dist' arguments provides the distance of MI from the start of the 1243 /// current basic block and it is used to determine if it is profitable 1244 /// to commute operands in the instruction. 1245 /// 1246 /// Returns true if the transformation happened. Otherwise, returns false. 1247 bool TwoAddressInstructionImpl::tryInstructionCommute(MachineInstr *MI, 1248 unsigned DstOpIdx, 1249 unsigned BaseOpIdx, 1250 bool BaseOpKilled, 1251 unsigned Dist) { 1252 if (!MI->isCommutable()) 1253 return false; 1254 1255 bool MadeChange = false; 1256 Register DstOpReg = MI->getOperand(DstOpIdx).getReg(); 1257 Register BaseOpReg = MI->getOperand(BaseOpIdx).getReg(); 1258 unsigned OpsNum = MI->getDesc().getNumOperands(); 1259 unsigned OtherOpIdx = MI->getDesc().getNumDefs(); 1260 for (; OtherOpIdx < OpsNum; OtherOpIdx++) { 1261 // The call of findCommutedOpIndices below only checks if BaseOpIdx 1262 // and OtherOpIdx are commutable, it does not really search for 1263 // other commutable operands and does not change the values of passed 1264 // variables. 1265 if (OtherOpIdx == BaseOpIdx || !MI->getOperand(OtherOpIdx).isReg() || 1266 !TII->findCommutedOpIndices(*MI, BaseOpIdx, OtherOpIdx)) 1267 continue; 1268 1269 Register OtherOpReg = MI->getOperand(OtherOpIdx).getReg(); 1270 bool AggressiveCommute = false; 1271 1272 // If OtherOp dies but BaseOp does not, swap the OtherOp and BaseOp 1273 // operands. This makes the live ranges of DstOp and OtherOp joinable. 1274 bool OtherOpKilled = isKilled(*MI, OtherOpReg, false); 1275 bool DoCommute = !BaseOpKilled && OtherOpKilled; 1276 1277 if (!DoCommute && 1278 isProfitableToCommute(DstOpReg, BaseOpReg, OtherOpReg, MI, Dist)) { 1279 DoCommute = true; 1280 AggressiveCommute = true; 1281 } 1282 1283 // If it's profitable to commute, try to do so. 1284 if (DoCommute && commuteInstruction(MI, DstOpIdx, BaseOpIdx, OtherOpIdx, 1285 Dist)) { 1286 MadeChange = true; 1287 ++NumCommuted; 1288 if (AggressiveCommute) 1289 ++NumAggrCommuted; 1290 1291 // There might be more than two commutable operands, update BaseOp and 1292 // continue scanning. 1293 // FIXME: This assumes that the new instruction's operands are in the 1294 // same positions and were simply swapped. 1295 BaseOpReg = OtherOpReg; 1296 BaseOpKilled = OtherOpKilled; 1297 // Resamples OpsNum in case the number of operands was reduced. This 1298 // happens with X86. 1299 OpsNum = MI->getDesc().getNumOperands(); 1300 } 1301 } 1302 return MadeChange; 1303 } 1304 1305 /// For the case where an instruction has a single pair of tied register 1306 /// operands, attempt some transformations that may either eliminate the tied 1307 /// operands or improve the opportunities for coalescing away the register copy. 1308 /// Returns true if no copy needs to be inserted to untie mi's operands 1309 /// (either because they were untied, or because mi was rescheduled, and will 1310 /// be visited again later). If the shouldOnlyCommute flag is true, only 1311 /// instruction commutation is attempted. 1312 bool TwoAddressInstructionImpl::tryInstructionTransform( 1313 MachineBasicBlock::iterator &mi, MachineBasicBlock::iterator &nmi, 1314 unsigned SrcIdx, unsigned DstIdx, unsigned &Dist, bool shouldOnlyCommute) { 1315 if (OptLevel == CodeGenOptLevel::None) 1316 return false; 1317 1318 MachineInstr &MI = *mi; 1319 Register regA = MI.getOperand(DstIdx).getReg(); 1320 Register regB = MI.getOperand(SrcIdx).getReg(); 1321 1322 assert(regB.isVirtual() && "cannot make instruction into two-address form"); 1323 bool regBKilled = isKilled(MI, regB, true); 1324 1325 if (regA.isVirtual()) 1326 scanUses(regA); 1327 1328 bool Commuted = tryInstructionCommute(&MI, DstIdx, SrcIdx, regBKilled, Dist); 1329 1330 // If the instruction is convertible to 3 Addr, instead 1331 // of returning try 3 Addr transformation aggressively and 1332 // use this variable to check later. Because it might be better. 1333 // For example, we can just use `leal (%rsi,%rdi), %eax` and `ret` 1334 // instead of the following code. 1335 // addl %esi, %edi 1336 // movl %edi, %eax 1337 // ret 1338 if (Commuted && !MI.isConvertibleTo3Addr()) 1339 return false; 1340 1341 if (shouldOnlyCommute) 1342 return false; 1343 1344 // If there is one more use of regB later in the same MBB, consider 1345 // re-schedule this MI below it. 1346 if (!Commuted && EnableRescheduling && rescheduleMIBelowKill(mi, nmi, regB)) { 1347 ++NumReSchedDowns; 1348 return true; 1349 } 1350 1351 // If we commuted, regB may have changed so we should re-sample it to avoid 1352 // confusing the three address conversion below. 1353 if (Commuted) { 1354 regB = MI.getOperand(SrcIdx).getReg(); 1355 regBKilled = isKilled(MI, regB, true); 1356 } 1357 1358 if (MI.isConvertibleTo3Addr()) { 1359 // This instruction is potentially convertible to a true 1360 // three-address instruction. Check if it is profitable. 1361 if (!regBKilled || isProfitableToConv3Addr(regA, regB)) { 1362 // Try to convert it. 1363 if (convertInstTo3Addr(mi, nmi, regA, regB, Dist)) { 1364 ++NumConvertedTo3Addr; 1365 return true; // Done with this instruction. 1366 } 1367 } 1368 } 1369 1370 // Return if it is commuted but 3 addr conversion is failed. 1371 if (Commuted) 1372 return false; 1373 1374 // If there is one more use of regB later in the same MBB, consider 1375 // re-schedule it before this MI if it's legal. 1376 if (EnableRescheduling && rescheduleKillAboveMI(mi, nmi, regB)) { 1377 ++NumReSchedUps; 1378 return true; 1379 } 1380 1381 // If this is an instruction with a load folded into it, try unfolding 1382 // the load, e.g. avoid this: 1383 // movq %rdx, %rcx 1384 // addq (%rax), %rcx 1385 // in favor of this: 1386 // movq (%rax), %rcx 1387 // addq %rdx, %rcx 1388 // because it's preferable to schedule a load than a register copy. 1389 if (MI.mayLoad() && !regBKilled) { 1390 // Determine if a load can be unfolded. 1391 unsigned LoadRegIndex; 1392 unsigned NewOpc = 1393 TII->getOpcodeAfterMemoryUnfold(MI.getOpcode(), 1394 /*UnfoldLoad=*/true, 1395 /*UnfoldStore=*/false, 1396 &LoadRegIndex); 1397 if (NewOpc != 0) { 1398 const MCInstrDesc &UnfoldMCID = TII->get(NewOpc); 1399 if (UnfoldMCID.getNumDefs() == 1) { 1400 // Unfold the load. 1401 LLVM_DEBUG(dbgs() << "2addr: UNFOLDING: " << MI); 1402 const TargetRegisterClass *RC = 1403 TRI->getAllocatableClass( 1404 TII->getRegClass(UnfoldMCID, LoadRegIndex, TRI, *MF)); 1405 Register Reg = MRI->createVirtualRegister(RC); 1406 SmallVector<MachineInstr *, 2> NewMIs; 1407 if (!TII->unfoldMemoryOperand(*MF, MI, Reg, 1408 /*UnfoldLoad=*/true, 1409 /*UnfoldStore=*/false, NewMIs)) { 1410 LLVM_DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n"); 1411 return false; 1412 } 1413 assert(NewMIs.size() == 2 && 1414 "Unfolded a load into multiple instructions!"); 1415 // The load was previously folded, so this is the only use. 1416 NewMIs[1]->addRegisterKilled(Reg, TRI); 1417 1418 // Tentatively insert the instructions into the block so that they 1419 // look "normal" to the transformation logic. 1420 MBB->insert(mi, NewMIs[0]); 1421 MBB->insert(mi, NewMIs[1]); 1422 DistanceMap.insert(std::make_pair(NewMIs[0], Dist++)); 1423 DistanceMap.insert(std::make_pair(NewMIs[1], Dist)); 1424 1425 LLVM_DEBUG(dbgs() << "2addr: NEW LOAD: " << *NewMIs[0] 1426 << "2addr: NEW INST: " << *NewMIs[1]); 1427 1428 // Transform the instruction, now that it no longer has a load. 1429 unsigned NewDstIdx = 1430 NewMIs[1]->findRegisterDefOperandIdx(regA, /*TRI=*/nullptr); 1431 unsigned NewSrcIdx = 1432 NewMIs[1]->findRegisterUseOperandIdx(regB, /*TRI=*/nullptr); 1433 MachineBasicBlock::iterator NewMI = NewMIs[1]; 1434 bool TransformResult = 1435 tryInstructionTransform(NewMI, mi, NewSrcIdx, NewDstIdx, Dist, true); 1436 (void)TransformResult; 1437 assert(!TransformResult && 1438 "tryInstructionTransform() should return false."); 1439 if (NewMIs[1]->getOperand(NewSrcIdx).isKill()) { 1440 // Success, or at least we made an improvement. Keep the unfolded 1441 // instructions and discard the original. 1442 if (LV) { 1443 for (const MachineOperand &MO : MI.operands()) { 1444 if (MO.isReg() && MO.getReg().isVirtual()) { 1445 if (MO.isUse()) { 1446 if (MO.isKill()) { 1447 if (NewMIs[0]->killsRegister(MO.getReg(), /*TRI=*/nullptr)) 1448 LV->replaceKillInstruction(MO.getReg(), MI, *NewMIs[0]); 1449 else { 1450 assert(NewMIs[1]->killsRegister(MO.getReg(), 1451 /*TRI=*/nullptr) && 1452 "Kill missing after load unfold!"); 1453 LV->replaceKillInstruction(MO.getReg(), MI, *NewMIs[1]); 1454 } 1455 } 1456 } else if (LV->removeVirtualRegisterDead(MO.getReg(), MI)) { 1457 if (NewMIs[1]->registerDefIsDead(MO.getReg(), 1458 /*TRI=*/nullptr)) 1459 LV->addVirtualRegisterDead(MO.getReg(), *NewMIs[1]); 1460 else { 1461 assert(NewMIs[0]->registerDefIsDead(MO.getReg(), 1462 /*TRI=*/nullptr) && 1463 "Dead flag missing after load unfold!"); 1464 LV->addVirtualRegisterDead(MO.getReg(), *NewMIs[0]); 1465 } 1466 } 1467 } 1468 } 1469 LV->addVirtualRegisterKilled(Reg, *NewMIs[1]); 1470 } 1471 1472 SmallVector<Register, 4> OrigRegs; 1473 if (LIS) { 1474 for (const MachineOperand &MO : MI.operands()) { 1475 if (MO.isReg()) 1476 OrigRegs.push_back(MO.getReg()); 1477 } 1478 1479 LIS->RemoveMachineInstrFromMaps(MI); 1480 } 1481 1482 MI.eraseFromParent(); 1483 DistanceMap.erase(&MI); 1484 1485 // Update LiveIntervals. 1486 if (LIS) { 1487 MachineBasicBlock::iterator Begin(NewMIs[0]); 1488 MachineBasicBlock::iterator End(NewMIs[1]); 1489 LIS->repairIntervalsInRange(MBB, Begin, End, OrigRegs); 1490 } 1491 1492 mi = NewMIs[1]; 1493 } else { 1494 // Transforming didn't eliminate the tie and didn't lead to an 1495 // improvement. Clean up the unfolded instructions and keep the 1496 // original. 1497 LLVM_DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n"); 1498 NewMIs[0]->eraseFromParent(); 1499 NewMIs[1]->eraseFromParent(); 1500 DistanceMap.erase(NewMIs[0]); 1501 DistanceMap.erase(NewMIs[1]); 1502 Dist--; 1503 } 1504 } 1505 } 1506 } 1507 1508 return false; 1509 } 1510 1511 // Collect tied operands of MI that need to be handled. 1512 // Rewrite trivial cases immediately. 1513 // Return true if any tied operands where found, including the trivial ones. 1514 bool TwoAddressInstructionImpl::collectTiedOperands( 1515 MachineInstr *MI, TiedOperandMap &TiedOperands) { 1516 bool AnyOps = false; 1517 unsigned NumOps = MI->getNumOperands(); 1518 1519 for (unsigned SrcIdx = 0; SrcIdx < NumOps; ++SrcIdx) { 1520 unsigned DstIdx = 0; 1521 if (!MI->isRegTiedToDefOperand(SrcIdx, &DstIdx)) 1522 continue; 1523 AnyOps = true; 1524 MachineOperand &SrcMO = MI->getOperand(SrcIdx); 1525 MachineOperand &DstMO = MI->getOperand(DstIdx); 1526 Register SrcReg = SrcMO.getReg(); 1527 Register DstReg = DstMO.getReg(); 1528 // Tied constraint already satisfied? 1529 if (SrcReg == DstReg) 1530 continue; 1531 1532 assert(SrcReg && SrcMO.isUse() && "two address instruction invalid"); 1533 1534 // Deal with undef uses immediately - simply rewrite the src operand. 1535 if (SrcMO.isUndef() && !DstMO.getSubReg()) { 1536 // Constrain the DstReg register class if required. 1537 if (DstReg.isVirtual()) { 1538 const TargetRegisterClass *RC = MRI->getRegClass(SrcReg); 1539 MRI->constrainRegClass(DstReg, RC); 1540 } 1541 SrcMO.setReg(DstReg); 1542 SrcMO.setSubReg(0); 1543 LLVM_DEBUG(dbgs() << "\t\trewrite undef:\t" << *MI); 1544 continue; 1545 } 1546 TiedOperands[SrcReg].push_back(std::make_pair(SrcIdx, DstIdx)); 1547 } 1548 return AnyOps; 1549 } 1550 1551 // Process a list of tied MI operands that all use the same source register. 1552 // The tied pairs are of the form (SrcIdx, DstIdx). 1553 void TwoAddressInstructionImpl::processTiedPairs(MachineInstr *MI, 1554 TiedPairList &TiedPairs, 1555 unsigned &Dist) { 1556 bool IsEarlyClobber = llvm::any_of(TiedPairs, [MI](auto const &TP) { 1557 return MI->getOperand(TP.second).isEarlyClobber(); 1558 }); 1559 1560 bool RemovedKillFlag = false; 1561 bool AllUsesCopied = true; 1562 unsigned LastCopiedReg = 0; 1563 SlotIndex LastCopyIdx; 1564 Register RegB = 0; 1565 unsigned SubRegB = 0; 1566 for (auto &TP : TiedPairs) { 1567 unsigned SrcIdx = TP.first; 1568 unsigned DstIdx = TP.second; 1569 1570 const MachineOperand &DstMO = MI->getOperand(DstIdx); 1571 Register RegA = DstMO.getReg(); 1572 1573 // Grab RegB from the instruction because it may have changed if the 1574 // instruction was commuted. 1575 RegB = MI->getOperand(SrcIdx).getReg(); 1576 SubRegB = MI->getOperand(SrcIdx).getSubReg(); 1577 1578 if (RegA == RegB) { 1579 // The register is tied to multiple destinations (or else we would 1580 // not have continued this far), but this use of the register 1581 // already matches the tied destination. Leave it. 1582 AllUsesCopied = false; 1583 continue; 1584 } 1585 LastCopiedReg = RegA; 1586 1587 assert(RegB.isVirtual() && "cannot make instruction into two-address form"); 1588 1589 #ifndef NDEBUG 1590 // First, verify that we don't have a use of "a" in the instruction 1591 // (a = b + a for example) because our transformation will not 1592 // work. This should never occur because we are in SSA form. 1593 for (unsigned i = 0; i != MI->getNumOperands(); ++i) 1594 assert(i == DstIdx || 1595 !MI->getOperand(i).isReg() || 1596 MI->getOperand(i).getReg() != RegA); 1597 #endif 1598 1599 // Emit a copy. 1600 MachineInstrBuilder MIB = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), 1601 TII->get(TargetOpcode::COPY), RegA); 1602 // If this operand is folding a truncation, the truncation now moves to the 1603 // copy so that the register classes remain valid for the operands. 1604 MIB.addReg(RegB, 0, SubRegB); 1605 const TargetRegisterClass *RC = MRI->getRegClass(RegB); 1606 if (SubRegB) { 1607 if (RegA.isVirtual()) { 1608 assert(TRI->getMatchingSuperRegClass(RC, MRI->getRegClass(RegA), 1609 SubRegB) && 1610 "tied subregister must be a truncation"); 1611 // The superreg class will not be used to constrain the subreg class. 1612 RC = nullptr; 1613 } else { 1614 assert(TRI->getMatchingSuperReg(RegA, SubRegB, MRI->getRegClass(RegB)) 1615 && "tied subregister must be a truncation"); 1616 } 1617 } 1618 1619 // Update DistanceMap. 1620 MachineBasicBlock::iterator PrevMI = MI; 1621 --PrevMI; 1622 DistanceMap.insert(std::make_pair(&*PrevMI, Dist)); 1623 DistanceMap[MI] = ++Dist; 1624 1625 if (LIS) { 1626 LastCopyIdx = LIS->InsertMachineInstrInMaps(*PrevMI).getRegSlot(); 1627 1628 SlotIndex endIdx = 1629 LIS->getInstructionIndex(*MI).getRegSlot(IsEarlyClobber); 1630 if (RegA.isVirtual()) { 1631 LiveInterval &LI = LIS->getInterval(RegA); 1632 VNInfo *VNI = LI.getNextValue(LastCopyIdx, LIS->getVNInfoAllocator()); 1633 LI.addSegment(LiveRange::Segment(LastCopyIdx, endIdx, VNI)); 1634 for (auto &S : LI.subranges()) { 1635 VNI = S.getNextValue(LastCopyIdx, LIS->getVNInfoAllocator()); 1636 S.addSegment(LiveRange::Segment(LastCopyIdx, endIdx, VNI)); 1637 } 1638 } else { 1639 for (MCRegUnit Unit : TRI->regunits(RegA)) { 1640 if (LiveRange *LR = LIS->getCachedRegUnit(Unit)) { 1641 VNInfo *VNI = 1642 LR->getNextValue(LastCopyIdx, LIS->getVNInfoAllocator()); 1643 LR->addSegment(LiveRange::Segment(LastCopyIdx, endIdx, VNI)); 1644 } 1645 } 1646 } 1647 } 1648 1649 LLVM_DEBUG(dbgs() << "\t\tprepend:\t" << *MIB); 1650 1651 MachineOperand &MO = MI->getOperand(SrcIdx); 1652 assert(MO.isReg() && MO.getReg() == RegB && MO.isUse() && 1653 "inconsistent operand info for 2-reg pass"); 1654 if (isPlainlyKilled(MO)) { 1655 MO.setIsKill(false); 1656 RemovedKillFlag = true; 1657 } 1658 1659 // Make sure regA is a legal regclass for the SrcIdx operand. 1660 if (RegA.isVirtual() && RegB.isVirtual()) 1661 MRI->constrainRegClass(RegA, RC); 1662 MO.setReg(RegA); 1663 // The getMatchingSuper asserts guarantee that the register class projected 1664 // by SubRegB is compatible with RegA with no subregister. So regardless of 1665 // whether the dest oper writes a subreg, the source oper should not. 1666 MO.setSubReg(0); 1667 } 1668 1669 if (AllUsesCopied) { 1670 LaneBitmask RemainingUses = LaneBitmask::getNone(); 1671 // Replace other (un-tied) uses of regB with LastCopiedReg. 1672 for (MachineOperand &MO : MI->all_uses()) { 1673 if (MO.getReg() == RegB) { 1674 if (MO.getSubReg() == SubRegB && !IsEarlyClobber) { 1675 if (isPlainlyKilled(MO)) { 1676 MO.setIsKill(false); 1677 RemovedKillFlag = true; 1678 } 1679 MO.setReg(LastCopiedReg); 1680 MO.setSubReg(0); 1681 } else { 1682 RemainingUses |= TRI->getSubRegIndexLaneMask(MO.getSubReg()); 1683 } 1684 } 1685 } 1686 1687 // Update live variables for regB. 1688 if (RemovedKillFlag && RemainingUses.none() && LV && 1689 LV->getVarInfo(RegB).removeKill(*MI)) { 1690 MachineBasicBlock::iterator PrevMI = MI; 1691 --PrevMI; 1692 LV->addVirtualRegisterKilled(RegB, *PrevMI); 1693 } 1694 1695 if (RemovedKillFlag && RemainingUses.none()) 1696 SrcRegMap[LastCopiedReg] = RegB; 1697 1698 // Update LiveIntervals. 1699 if (LIS) { 1700 SlotIndex UseIdx = LIS->getInstructionIndex(*MI); 1701 auto Shrink = [=](LiveRange &LR, LaneBitmask LaneMask) { 1702 LiveRange::Segment *S = LR.getSegmentContaining(LastCopyIdx); 1703 if (!S) 1704 return true; 1705 if ((LaneMask & RemainingUses).any()) 1706 return false; 1707 if (S->end.getBaseIndex() != UseIdx) 1708 return false; 1709 S->end = LastCopyIdx; 1710 return true; 1711 }; 1712 1713 LiveInterval &LI = LIS->getInterval(RegB); 1714 bool ShrinkLI = true; 1715 for (auto &S : LI.subranges()) 1716 ShrinkLI &= Shrink(S, S.LaneMask); 1717 if (ShrinkLI) 1718 Shrink(LI, LaneBitmask::getAll()); 1719 } 1720 } else if (RemovedKillFlag) { 1721 // Some tied uses of regB matched their destination registers, so 1722 // regB is still used in this instruction, but a kill flag was 1723 // removed from a different tied use of regB, so now we need to add 1724 // a kill flag to one of the remaining uses of regB. 1725 for (MachineOperand &MO : MI->all_uses()) { 1726 if (MO.getReg() == RegB) { 1727 MO.setIsKill(true); 1728 break; 1729 } 1730 } 1731 } 1732 } 1733 1734 // For every tied operand pair this function transforms statepoint from 1735 // RegA = STATEPOINT ... RegB(tied-def N) 1736 // to 1737 // RegB = STATEPOINT ... RegB(tied-def N) 1738 // and replaces all uses of RegA with RegB. 1739 // No extra COPY instruction is necessary because tied use is killed at 1740 // STATEPOINT. 1741 bool TwoAddressInstructionImpl::processStatepoint( 1742 MachineInstr *MI, TiedOperandMap &TiedOperands) { 1743 1744 bool NeedCopy = false; 1745 for (auto &TO : TiedOperands) { 1746 Register RegB = TO.first; 1747 if (TO.second.size() != 1) { 1748 NeedCopy = true; 1749 continue; 1750 } 1751 1752 unsigned SrcIdx = TO.second[0].first; 1753 unsigned DstIdx = TO.second[0].second; 1754 1755 MachineOperand &DstMO = MI->getOperand(DstIdx); 1756 Register RegA = DstMO.getReg(); 1757 1758 assert(RegB == MI->getOperand(SrcIdx).getReg()); 1759 1760 if (RegA == RegB) 1761 continue; 1762 1763 // CodeGenPrepare can sink pointer compare past statepoint, which 1764 // breaks assumption that statepoint kills tied-use register when 1765 // in SSA form (see note in IR/SafepointIRVerifier.cpp). Fall back 1766 // to generic tied register handling to avoid assertion failures. 1767 // TODO: Recompute LIS/LV information for new range here. 1768 if (LIS) { 1769 const auto &UseLI = LIS->getInterval(RegB); 1770 const auto &DefLI = LIS->getInterval(RegA); 1771 if (DefLI.overlaps(UseLI)) { 1772 LLVM_DEBUG(dbgs() << "LIS: " << printReg(RegB, TRI, 0) 1773 << " UseLI overlaps with DefLI\n"); 1774 NeedCopy = true; 1775 continue; 1776 } 1777 } else if (LV && LV->getVarInfo(RegB).findKill(MI->getParent()) != MI) { 1778 // Note that MachineOperand::isKill does not work here, because it 1779 // is set only on first register use in instruction and for statepoint 1780 // tied-use register will usually be found in preceeding deopt bundle. 1781 LLVM_DEBUG(dbgs() << "LV: " << printReg(RegB, TRI, 0) 1782 << " not killed by statepoint\n"); 1783 NeedCopy = true; 1784 continue; 1785 } 1786 1787 if (!MRI->constrainRegClass(RegB, MRI->getRegClass(RegA))) { 1788 LLVM_DEBUG(dbgs() << "MRI: couldn't constrain" << printReg(RegB, TRI, 0) 1789 << " to register class of " << printReg(RegA, TRI, 0) 1790 << '\n'); 1791 NeedCopy = true; 1792 continue; 1793 } 1794 MRI->replaceRegWith(RegA, RegB); 1795 1796 if (LIS) { 1797 VNInfo::Allocator &A = LIS->getVNInfoAllocator(); 1798 LiveInterval &LI = LIS->getInterval(RegB); 1799 LiveInterval &Other = LIS->getInterval(RegA); 1800 SmallVector<VNInfo *> NewVNIs; 1801 for (const VNInfo *VNI : Other.valnos) { 1802 assert(VNI->id == NewVNIs.size() && "assumed"); 1803 NewVNIs.push_back(LI.createValueCopy(VNI, A)); 1804 } 1805 for (auto &S : Other) { 1806 VNInfo *VNI = NewVNIs[S.valno->id]; 1807 LiveRange::Segment NewSeg(S.start, S.end, VNI); 1808 LI.addSegment(NewSeg); 1809 } 1810 LIS->removeInterval(RegA); 1811 } 1812 1813 if (LV) { 1814 if (MI->getOperand(SrcIdx).isKill()) 1815 LV->removeVirtualRegisterKilled(RegB, *MI); 1816 LiveVariables::VarInfo &SrcInfo = LV->getVarInfo(RegB); 1817 LiveVariables::VarInfo &DstInfo = LV->getVarInfo(RegA); 1818 SrcInfo.AliveBlocks |= DstInfo.AliveBlocks; 1819 DstInfo.AliveBlocks.clear(); 1820 for (auto *KillMI : DstInfo.Kills) 1821 LV->addVirtualRegisterKilled(RegB, *KillMI, false); 1822 } 1823 } 1824 return !NeedCopy; 1825 } 1826 1827 /// Reduce two-address instructions to two operands. 1828 bool TwoAddressInstructionImpl::run() { 1829 bool MadeChange = false; 1830 1831 LLVM_DEBUG(dbgs() << "********** REWRITING TWO-ADDR INSTRS **********\n"); 1832 LLVM_DEBUG(dbgs() << "********** Function: " << MF->getName() << '\n'); 1833 1834 // This pass takes the function out of SSA form. 1835 MRI->leaveSSA(); 1836 1837 // This pass will rewrite the tied-def to meet the RegConstraint. 1838 MF->getProperties() 1839 .set(MachineFunctionProperties::Property::TiedOpsRewritten); 1840 1841 TiedOperandMap TiedOperands; 1842 for (MachineBasicBlock &MBBI : *MF) { 1843 MBB = &MBBI; 1844 unsigned Dist = 0; 1845 DistanceMap.clear(); 1846 SrcRegMap.clear(); 1847 DstRegMap.clear(); 1848 Processed.clear(); 1849 for (MachineBasicBlock::iterator mi = MBB->begin(), me = MBB->end(); 1850 mi != me; ) { 1851 MachineBasicBlock::iterator nmi = std::next(mi); 1852 // Skip debug instructions. 1853 if (mi->isDebugInstr()) { 1854 mi = nmi; 1855 continue; 1856 } 1857 1858 // Expand REG_SEQUENCE instructions. This will position mi at the first 1859 // expanded instruction. 1860 if (mi->isRegSequence()) 1861 eliminateRegSequence(mi); 1862 1863 DistanceMap.insert(std::make_pair(&*mi, ++Dist)); 1864 1865 processCopy(&*mi); 1866 1867 // First scan through all the tied register uses in this instruction 1868 // and record a list of pairs of tied operands for each register. 1869 if (!collectTiedOperands(&*mi, TiedOperands)) { 1870 removeClobberedSrcRegMap(&*mi); 1871 mi = nmi; 1872 continue; 1873 } 1874 1875 ++NumTwoAddressInstrs; 1876 MadeChange = true; 1877 LLVM_DEBUG(dbgs() << '\t' << *mi); 1878 1879 // If the instruction has a single pair of tied operands, try some 1880 // transformations that may either eliminate the tied operands or 1881 // improve the opportunities for coalescing away the register copy. 1882 if (TiedOperands.size() == 1) { 1883 SmallVectorImpl<std::pair<unsigned, unsigned>> &TiedPairs 1884 = TiedOperands.begin()->second; 1885 if (TiedPairs.size() == 1) { 1886 unsigned SrcIdx = TiedPairs[0].first; 1887 unsigned DstIdx = TiedPairs[0].second; 1888 Register SrcReg = mi->getOperand(SrcIdx).getReg(); 1889 Register DstReg = mi->getOperand(DstIdx).getReg(); 1890 if (SrcReg != DstReg && 1891 tryInstructionTransform(mi, nmi, SrcIdx, DstIdx, Dist, false)) { 1892 // The tied operands have been eliminated or shifted further down 1893 // the block to ease elimination. Continue processing with 'nmi'. 1894 TiedOperands.clear(); 1895 removeClobberedSrcRegMap(&*mi); 1896 mi = nmi; 1897 continue; 1898 } 1899 } 1900 } 1901 1902 if (mi->getOpcode() == TargetOpcode::STATEPOINT && 1903 processStatepoint(&*mi, TiedOperands)) { 1904 TiedOperands.clear(); 1905 LLVM_DEBUG(dbgs() << "\t\trewrite to:\t" << *mi); 1906 mi = nmi; 1907 continue; 1908 } 1909 1910 // Now iterate over the information collected above. 1911 for (auto &TO : TiedOperands) { 1912 processTiedPairs(&*mi, TO.second, Dist); 1913 LLVM_DEBUG(dbgs() << "\t\trewrite to:\t" << *mi); 1914 } 1915 1916 // Rewrite INSERT_SUBREG as COPY now that we no longer need SSA form. 1917 if (mi->isInsertSubreg()) { 1918 // From %reg = INSERT_SUBREG %reg, %subreg, subidx 1919 // To %reg:subidx = COPY %subreg 1920 unsigned SubIdx = mi->getOperand(3).getImm(); 1921 mi->removeOperand(3); 1922 assert(mi->getOperand(0).getSubReg() == 0 && "Unexpected subreg idx"); 1923 mi->getOperand(0).setSubReg(SubIdx); 1924 mi->getOperand(0).setIsUndef(mi->getOperand(1).isUndef()); 1925 mi->removeOperand(1); 1926 mi->setDesc(TII->get(TargetOpcode::COPY)); 1927 LLVM_DEBUG(dbgs() << "\t\tconvert to:\t" << *mi); 1928 1929 // Update LiveIntervals. 1930 if (LIS) { 1931 Register Reg = mi->getOperand(0).getReg(); 1932 LiveInterval &LI = LIS->getInterval(Reg); 1933 if (LI.hasSubRanges()) { 1934 // The COPY no longer defines subregs of %reg except for 1935 // %reg.subidx. 1936 LaneBitmask LaneMask = 1937 TRI->getSubRegIndexLaneMask(mi->getOperand(0).getSubReg()); 1938 SlotIndex Idx = LIS->getInstructionIndex(*mi).getRegSlot(); 1939 for (auto &S : LI.subranges()) { 1940 if ((S.LaneMask & LaneMask).none()) { 1941 LiveRange::iterator DefSeg = S.FindSegmentContaining(Idx); 1942 if (mi->getOperand(0).isUndef()) { 1943 S.removeValNo(DefSeg->valno); 1944 } else { 1945 LiveRange::iterator UseSeg = std::prev(DefSeg); 1946 S.MergeValueNumberInto(DefSeg->valno, UseSeg->valno); 1947 } 1948 } 1949 } 1950 1951 // The COPY no longer has a use of %reg. 1952 LIS->shrinkToUses(&LI); 1953 } else { 1954 // The live interval for Reg did not have subranges but now it needs 1955 // them because we have introduced a subreg def. Recompute it. 1956 LIS->removeInterval(Reg); 1957 LIS->createAndComputeVirtRegInterval(Reg); 1958 } 1959 } 1960 } 1961 1962 // Clear TiedOperands here instead of at the top of the loop 1963 // since most instructions do not have tied operands. 1964 TiedOperands.clear(); 1965 removeClobberedSrcRegMap(&*mi); 1966 mi = nmi; 1967 } 1968 } 1969 1970 return MadeChange; 1971 } 1972 1973 /// Eliminate a REG_SEQUENCE instruction as part of the de-ssa process. 1974 /// 1975 /// The instruction is turned into a sequence of sub-register copies: 1976 /// 1977 /// %dst = REG_SEQUENCE %v1, ssub0, %v2, ssub1 1978 /// 1979 /// Becomes: 1980 /// 1981 /// undef %dst:ssub0 = COPY %v1 1982 /// %dst:ssub1 = COPY %v2 1983 void TwoAddressInstructionImpl::eliminateRegSequence( 1984 MachineBasicBlock::iterator &MBBI) { 1985 MachineInstr &MI = *MBBI; 1986 Register DstReg = MI.getOperand(0).getReg(); 1987 1988 SmallVector<Register, 4> OrigRegs; 1989 VNInfo *DefVN = nullptr; 1990 if (LIS) { 1991 OrigRegs.push_back(MI.getOperand(0).getReg()); 1992 for (unsigned i = 1, e = MI.getNumOperands(); i < e; i += 2) 1993 OrigRegs.push_back(MI.getOperand(i).getReg()); 1994 if (LIS->hasInterval(DstReg)) { 1995 DefVN = LIS->getInterval(DstReg) 1996 .Query(LIS->getInstructionIndex(MI)) 1997 .valueOut(); 1998 } 1999 } 2000 2001 LaneBitmask UndefLanes = LaneBitmask::getNone(); 2002 bool DefEmitted = false; 2003 for (unsigned i = 1, e = MI.getNumOperands(); i < e; i += 2) { 2004 MachineOperand &UseMO = MI.getOperand(i); 2005 Register SrcReg = UseMO.getReg(); 2006 unsigned SubIdx = MI.getOperand(i+1).getImm(); 2007 // Nothing needs to be inserted for undef operands. 2008 if (UseMO.isUndef()) { 2009 UndefLanes |= TRI->getSubRegIndexLaneMask(SubIdx); 2010 continue; 2011 } 2012 2013 // Defer any kill flag to the last operand using SrcReg. Otherwise, we 2014 // might insert a COPY that uses SrcReg after is was killed. 2015 bool isKill = UseMO.isKill(); 2016 if (isKill) 2017 for (unsigned j = i + 2; j < e; j += 2) 2018 if (MI.getOperand(j).getReg() == SrcReg) { 2019 MI.getOperand(j).setIsKill(); 2020 UseMO.setIsKill(false); 2021 isKill = false; 2022 break; 2023 } 2024 2025 // Insert the sub-register copy. 2026 MachineInstr *CopyMI = BuildMI(*MI.getParent(), MI, MI.getDebugLoc(), 2027 TII->get(TargetOpcode::COPY)) 2028 .addReg(DstReg, RegState::Define, SubIdx) 2029 .add(UseMO); 2030 2031 // The first def needs an undef flag because there is no live register 2032 // before it. 2033 if (!DefEmitted) { 2034 CopyMI->getOperand(0).setIsUndef(true); 2035 // Return an iterator pointing to the first inserted instr. 2036 MBBI = CopyMI; 2037 } 2038 DefEmitted = true; 2039 2040 // Update LiveVariables' kill info. 2041 if (LV && isKill && !SrcReg.isPhysical()) 2042 LV->replaceKillInstruction(SrcReg, MI, *CopyMI); 2043 2044 LLVM_DEBUG(dbgs() << "Inserted: " << *CopyMI); 2045 } 2046 2047 MachineBasicBlock::iterator EndMBBI = 2048 std::next(MachineBasicBlock::iterator(MI)); 2049 2050 if (!DefEmitted) { 2051 LLVM_DEBUG(dbgs() << "Turned: " << MI << " into an IMPLICIT_DEF"); 2052 MI.setDesc(TII->get(TargetOpcode::IMPLICIT_DEF)); 2053 for (int j = MI.getNumOperands() - 1, ee = 0; j > ee; --j) 2054 MI.removeOperand(j); 2055 } else { 2056 if (LIS) { 2057 // Force live interval recomputation if we moved to a partial definition 2058 // of the register. Undef flags must be propagate to uses of undefined 2059 // subregister for accurate interval computation. 2060 if (UndefLanes.any() && DefVN && MRI->shouldTrackSubRegLiveness(DstReg)) { 2061 auto &LI = LIS->getInterval(DstReg); 2062 for (MachineOperand &UseOp : MRI->use_operands(DstReg)) { 2063 unsigned SubReg = UseOp.getSubReg(); 2064 if (UseOp.isUndef() || !SubReg) 2065 continue; 2066 auto *VN = 2067 LI.getVNInfoAt(LIS->getInstructionIndex(*UseOp.getParent())); 2068 if (DefVN != VN) 2069 continue; 2070 LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg); 2071 if ((UndefLanes & LaneMask).any()) 2072 UseOp.setIsUndef(true); 2073 } 2074 LIS->removeInterval(DstReg); 2075 } 2076 LIS->RemoveMachineInstrFromMaps(MI); 2077 } 2078 2079 LLVM_DEBUG(dbgs() << "Eliminated: " << MI); 2080 MI.eraseFromParent(); 2081 } 2082 2083 // Udpate LiveIntervals. 2084 if (LIS) 2085 LIS->repairIntervalsInRange(MBB, MBBI, EndMBBI, OrigRegs); 2086 } 2087