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