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