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