lib/CodeGen/TwoAddressInstructionPass.cpp

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