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 #define DEBUG_TYPE "twoaddrinstr"
  31 #include "llvm/CodeGen/Passes.h"
  32 #include "llvm/Function.h"
  33 #include "llvm/CodeGen/LiveVariables.h"
  34 #include "llvm/CodeGen/MachineFunctionPass.h"
  35 #include "llvm/CodeGen/MachineInstr.h"
  36 #include "llvm/CodeGen/MachineRegisterInfo.h"
  37 #include "llvm/Target/TargetRegisterInfo.h"
  38 #include "llvm/Target/TargetInstrInfo.h"
  39 #include "llvm/Target/TargetMachine.h"
  40 #include "llvm/Target/TargetOptions.h"
  41 #include "llvm/Support/Compiler.h"
  42 #include "llvm/Support/Debug.h"
  43 #include "llvm/ADT/BitVector.h"
  44 #include "llvm/ADT/DenseMap.h"
  45 #include "llvm/ADT/SmallSet.h"
  46 #include "llvm/ADT/Statistic.h"
  47 #include "llvm/ADT/STLExtras.h"
  48 using namespace llvm;
  49
  50 STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions");
  51 STATISTIC(NumCommuted        , "Number of instructions commuted to coalesce");
  52 STATISTIC(NumAggrCommuted    , "Number of instructions aggressively commuted");
  53 STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address");
  54 STATISTIC(Num3AddrSunk,        "Number of 3-address instructions sunk");
  55 STATISTIC(NumReMats,           "Number of instructions re-materialized");
  56 STATISTIC(NumDeletes,          "Number of dead instructions deleted");
  57
  58 namespace {
  59   class VISIBILITY_HIDDEN TwoAddressInstructionPass
  60     : public MachineFunctionPass {
  61     const TargetInstrInfo *TII;
  62     const TargetRegisterInfo *TRI;
  63     MachineRegisterInfo *MRI;
  64     LiveVariables *LV;
  65
  66     bool Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI,
  67                               unsigned Reg,
  68                               MachineBasicBlock::iterator OldPos);
  69
  70     bool isProfitableToReMat(unsigned Reg, const TargetRegisterClass *RC,
  71                              MachineInstr *MI, MachineInstr *DefMI,
  72                              MachineBasicBlock *MBB, unsigned Loc,
  73                              DenseMap<MachineInstr*, unsigned> &DistanceMap);
  74
  75     bool NoUseAfterLastDef(unsigned Reg, MachineBasicBlock *MBB, unsigned Dist,
  76                            DenseMap<MachineInstr*, unsigned> &DistanceMap,
  77                            unsigned &LastDef);
  78
  79     bool isProfitableToCommute(unsigned regB, unsigned regC,
  80                                MachineInstr *MI, MachineBasicBlock *MBB,
  81                                unsigned Dist,
  82                                DenseMap<MachineInstr*, unsigned> &DistanceMap);
  83
  84     bool CommuteInstruction(MachineBasicBlock::iterator &mi,
  85                             MachineFunction::iterator &mbbi,
  86                             unsigned RegC, unsigned Dist,
  87                             DenseMap<MachineInstr*, unsigned> &DistanceMap);
  88   public:
  89     static char ID; // Pass identification, replacement for typeid
  90     TwoAddressInstructionPass() : MachineFunctionPass(&ID) {}
  91
  92     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  93       AU.addPreserved<LiveVariables>();
  94       AU.addPreservedID(MachineLoopInfoID);
  95       AU.addPreservedID(MachineDominatorsID);
  96       if (StrongPHIElim)
  97         AU.addPreservedID(StrongPHIEliminationID);
  98       else
  99         AU.addPreservedID(PHIEliminationID);
 100       MachineFunctionPass::getAnalysisUsage(AU);
 101     }
 102
 103     /// runOnMachineFunction - Pass entry point.
 104     bool runOnMachineFunction(MachineFunction&);
 105   };
 106 }
 107
 108 char TwoAddressInstructionPass::ID = 0;
 109 static RegisterPass<TwoAddressInstructionPass>
 110 X("twoaddressinstruction", "Two-Address instruction pass");
 111
 112 const PassInfo *const llvm::TwoAddressInstructionPassID = &X;
 113
 114 /// Sink3AddrInstruction - A two-address instruction has been converted to a
 115 /// three-address instruction to avoid clobbering a register. Try to sink it
 116 /// past the instruction that would kill the above mentioned register to reduce
 117 /// register pressure.
 118 bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB,
 119                                            MachineInstr *MI, unsigned SavedReg,
 120                                            MachineBasicBlock::iterator OldPos) {
 121   // Check if it's safe to move this instruction.
 122   bool SeenStore = true; // Be conservative.
 123   if (!MI->isSafeToMove(TII, SeenStore))
 124     return false;
 125
 126   unsigned DefReg = 0;
 127   SmallSet<unsigned, 4> UseRegs;
 128
 129   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 130     const MachineOperand &MO = MI->getOperand(i);
 131     if (!MO.isReg())
 132       continue;
 133     unsigned MOReg = MO.getReg();
 134     if (!MOReg)
 135       continue;
 136     if (MO.isUse() && MOReg != SavedReg)
 137       UseRegs.insert(MO.getReg());
 138     if (!MO.isDef())
 139       continue;
 140     if (MO.isImplicit())
 141       // Don't try to move it if it implicitly defines a register.
 142       return false;
 143     if (DefReg)
 144       // For now, don't move any instructions that define multiple registers.
 145       return false;
 146     DefReg = MO.getReg();
 147   }
 148
 149   // Find the instruction that kills SavedReg.
 150   MachineInstr *KillMI = NULL;
 151   for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(SavedReg),
 152          UE = MRI->use_end(); UI != UE; ++UI) {
 153     MachineOperand &UseMO = UI.getOperand();
 154     if (!UseMO.isKill())
 155       continue;
 156     KillMI = UseMO.getParent();
 157     break;
 158   }
 159
 160   if (!KillMI || KillMI->getParent() != MBB)
 161     return false;
 162
 163   // If any of the definitions are used by another instruction between the
 164   // position and the kill use, then it's not safe to sink it.
 165   //
 166   // FIXME: This can be sped up if there is an easy way to query whether an
 167   // instruction is before or after another instruction. Then we can use
 168   // MachineRegisterInfo def / use instead.
 169   MachineOperand *KillMO = NULL;
 170   MachineBasicBlock::iterator KillPos = KillMI;
 171   ++KillPos;
 172
 173   unsigned NumVisited = 0;
 174   for (MachineBasicBlock::iterator I = next(OldPos); I != KillPos; ++I) {
 175     MachineInstr *OtherMI = I;
 176     if (NumVisited > 30)  // FIXME: Arbitrary limit to reduce compile time cost.
 177       return false;
 178     ++NumVisited;
 179     for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) {
 180       MachineOperand &MO = OtherMI->getOperand(i);
 181       if (!MO.isReg())
 182         continue;
 183       unsigned MOReg = MO.getReg();
 184       if (!MOReg)
 185         continue;
 186       if (DefReg == MOReg)
 187         return false;
 188
 189       if (MO.isKill()) {
 190         if (OtherMI == KillMI && MOReg == SavedReg)
 191           // Save the operand that kills the register. We want to unset the kill
 192           // marker if we can sink MI past it.
 193           KillMO = &MO;
 194         else if (UseRegs.count(MOReg))
 195           // One of the uses is killed before the destination.
 196           return false;
 197       }
 198     }
 199   }
 200
 201   // Update kill and LV information.
 202   KillMO->setIsKill(false);
 203   KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI);
 204   KillMO->setIsKill(true);
 205
 206   if (LV)
 207     LV->replaceKillInstruction(SavedReg, KillMI, MI);
 208
 209   // Move instruction to its destination.
 210   MBB->remove(MI);
 211   MBB->insert(KillPos, MI);
 212
 213   ++Num3AddrSunk;
 214   return true;
 215 }
 216
 217 /// isTwoAddrUse - Return true if the specified MI is using the specified
 218 /// register as a two-address operand.
 219 static bool isTwoAddrUse(MachineInstr *UseMI, unsigned Reg) {
 220   const TargetInstrDesc &TID = UseMI->getDesc();
 221   for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) {
 222     MachineOperand &MO = UseMI->getOperand(i);
 223     if (MO.isReg() && MO.getReg() == Reg &&
 224         (MO.isDef() || TID.getOperandConstraint(i, TOI::TIED_TO) != -1))
 225       // Earlier use is a two-address one.
 226       return true;
 227   }
 228   return false;
 229 }
 230
 231 /// isProfitableToReMat - Return true if the heuristics determines it is likely
 232 /// to be profitable to re-materialize the definition of Reg rather than copy
 233 /// the register.
 234 bool
 235 TwoAddressInstructionPass::isProfitableToReMat(unsigned Reg,
 236                                 const TargetRegisterClass *RC,
 237                                 MachineInstr *MI, MachineInstr *DefMI,
 238                                 MachineBasicBlock *MBB, unsigned Loc,
 239                                 DenseMap<MachineInstr*, unsigned> &DistanceMap){
 240   bool OtherUse = false;
 241   for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
 242          UE = MRI->use_end(); UI != UE; ++UI) {
 243     MachineOperand &UseMO = UI.getOperand();
 244     MachineInstr *UseMI = UseMO.getParent();
 245     MachineBasicBlock *UseMBB = UseMI->getParent();
 246     if (UseMBB == MBB) {
 247       DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI);
 248       if (DI != DistanceMap.end() && DI->second == Loc)
 249         continue;  // Current use.
 250       OtherUse = true;
 251       // There is at least one other use in the MBB that will clobber the
 252       // register.
 253       if (isTwoAddrUse(UseMI, Reg))
 254         return true;
 255     }
 256   }
 257
 258   // If other uses in MBB are not two-address uses, then don't remat.
 259   if (OtherUse)
 260     return false;
 261
 262   // No other uses in the same block, remat if it's defined in the same
 263   // block so it does not unnecessarily extend the live range.
 264   return MBB == DefMI->getParent();
 265 }
 266
 267 /// NoUseAfterLastDef - Return true if there are no intervening uses between the
 268 /// last instruction in the MBB that defines the specified register and the
 269 /// two-address instruction which is being processed. It also returns the last
 270 /// def location by reference
 271 bool TwoAddressInstructionPass::NoUseAfterLastDef(unsigned Reg,
 272                                  MachineBasicBlock *MBB, unsigned Dist,
 273                                  DenseMap<MachineInstr*, unsigned> &DistanceMap,
 274                                  unsigned &LastDef) {
 275   LastDef = 0;
 276   unsigned LastUse = Dist;
 277   for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Reg),
 278          E = MRI->reg_end(); I != E; ++I) {
 279     MachineOperand &MO = I.getOperand();
 280     MachineInstr *MI = MO.getParent();
 281     if (MI->getParent() != MBB)
 282       continue;
 283     DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI);
 284     if (DI == DistanceMap.end())
 285       continue;
 286     if (MO.isUse() && DI->second < LastUse)
 287       LastUse = DI->second;
 288     if (MO.isDef() && DI->second > LastDef)
 289       LastDef = DI->second;
 290   }
 291
 292   return !(LastUse > LastDef && LastUse < Dist);
 293 }
 294
 295 /// isProfitableToReMat - Return true if it's potentially profitable to commute
 296 /// the two-address instruction that's being processed.
 297 bool
 298 TwoAddressInstructionPass::isProfitableToCommute(unsigned regB, unsigned regC,
 299                 MachineInstr *MI, MachineBasicBlock *MBB,
 300                 unsigned Dist, DenseMap<MachineInstr*, unsigned> &DistanceMap) {
 301   // Determine if it's profitable to commute this two address instruction. In
 302   // general, we want no uses between this instruction and the definition of
 303   // the two-address register.
 304   // e.g.
 305   // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1
 306   // %reg1029<def> = MOV8rr %reg1028
 307   // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead>
 308   // insert => %reg1030<def> = MOV8rr %reg1028
 309   // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead>
 310   // In this case, it might not be possible to coalesce the second MOV8rr
 311   // instruction if the first one is coalesced. So it would be profitable to
 312   // commute it:
 313   // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1
 314   // %reg1029<def> = MOV8rr %reg1028
 315   // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead>
 316   // insert => %reg1030<def> = MOV8rr %reg1029
 317   // %reg1030<def> = ADD8rr %reg1029<kill>, %reg1028<kill>, %EFLAGS<imp-def,dead>
 318
 319   if (!MI->killsRegister(regC))
 320     return false;
 321
 322   // Ok, we have something like:
 323   // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead>
 324   // let's see if it's worth commuting it.
 325
 326   // If there is a use of regC between its last def (could be livein) and this
 327   // instruction, then bail.
 328   unsigned LastDefC = 0;
 329   if (!NoUseAfterLastDef(regC, MBB, Dist, DistanceMap, LastDefC))
 330     return false;
 331
 332   // If there is a use of regB between its last def (could be livein) and this
 333   // instruction, then go ahead and make this transformation.
 334   unsigned LastDefB = 0;
 335   if (!NoUseAfterLastDef(regB, MBB, Dist, DistanceMap, LastDefB))
 336     return true;
 337
 338   // Since there are no intervening uses for both registers, then commute
 339   // if the def of regC is closer. Its live interval is shorter.
 340   return LastDefB && LastDefC && LastDefC > LastDefB;
 341 }
 342
 343 /// CommuteInstruction - Commute a two-address instruction and update the basic
 344 /// block, distance map, and live variables if needed. Return true if it is
 345 /// successful.
 346 bool
 347 TwoAddressInstructionPass::CommuteInstruction(MachineBasicBlock::iterator &mi,
 348                                               MachineFunction::iterator &mbbi,
 349                                               unsigned RegC, unsigned Dist,
 350                                DenseMap<MachineInstr*, unsigned> &DistanceMap) {
 351   MachineInstr *MI = mi;
 352   DOUT << "2addr: COMMUTING  : " << *MI;
 353   MachineInstr *NewMI = TII->commuteInstruction(MI);
 354
 355   if (NewMI == 0) {
 356     DOUT << "2addr: COMMUTING FAILED!\n";
 357     return false;
 358   }
 359
 360   DOUT << "2addr: COMMUTED TO: " << *NewMI;
 361   // If the instruction changed to commute it, update livevar.
 362   if (NewMI != MI) {
 363     if (LV)
 364       // Update live variables
 365       LV->replaceKillInstruction(RegC, MI, NewMI);
 366
 367     mbbi->insert(mi, NewMI);           // Insert the new inst
 368     mbbi->erase(mi);                   // Nuke the old inst.
 369     mi = NewMI;
 370     DistanceMap.insert(std::make_pair(NewMI, Dist));
 371   }
 372   return true;
 373 }
 374
 375 /// isSafeToDelete - If the specified instruction does not produce any side
 376 /// effects and all of its defs are dead, then it's safe to delete.
 377 static bool isSafeToDelete(MachineInstr *MI, const TargetInstrInfo *TII) {
 378   const TargetInstrDesc &TID = MI->getDesc();
 379   if (TID.mayStore() || TID.isCall())
 380     return false;
 381   if (TID.isTerminator() || TID.hasUnmodeledSideEffects())
 382     return false;
 383
 384   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 385     MachineOperand &MO = MI->getOperand(i);
 386     if (!MO.isReg() || !MO.isDef())
 387       continue;
 388     if (!MO.isDead())
 389       return false;
 390   }
 391
 392   return true;
 393 }
 394
 395 /// runOnMachineFunction - Reduce two-address instructions to two operands.
 396 ///
 397 bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
 398   DOUT << "Machine Function\n";
 399   const TargetMachine &TM = MF.getTarget();
 400   MRI = &MF.getRegInfo();
 401   TII = TM.getInstrInfo();
 402   TRI = TM.getRegisterInfo();
 403   LV = getAnalysisIfAvailable<LiveVariables>();
 404
 405   bool MadeChange = false;
 406
 407   DOUT << "********** REWRITING TWO-ADDR INSTRS **********\n";
 408   DOUT << "********** Function: " << MF.getFunction()->getName() << '\n';
 409
 410   // ReMatRegs - Keep track of the registers whose def's are remat'ed.
 411   BitVector ReMatRegs;
 412   ReMatRegs.resize(MRI->getLastVirtReg()+1);
 413
 414   // DistanceMap - Keep track the distance of a MI from the start of the
 415   // current basic block.
 416   DenseMap<MachineInstr*, unsigned> DistanceMap;
 417
 418   for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end();
 419        mbbi != mbbe; ++mbbi) {
 420     unsigned Dist = 0;
 421     DistanceMap.clear();
 422     for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end();
 423          mi != me; ) {
 424       MachineBasicBlock::iterator nmi = next(mi);
 425       const TargetInstrDesc &TID = mi->getDesc();
 426       bool FirstTied = true;
 427
 428       DistanceMap.insert(std::make_pair(mi, ++Dist));
 429       for (unsigned si = 1, e = TID.getNumOperands(); si < e; ++si) {
 430         int ti = TID.getOperandConstraint(si, TOI::TIED_TO);
 431         if (ti == -1)
 432           continue;
 433
 434         if (FirstTied) {
 435           ++NumTwoAddressInstrs;
 436           DOUT << '\t'; DEBUG(mi->print(*cerr.stream(), &TM));
 437         }
 438
 439         FirstTied = false;
 440
 441         assert(mi->getOperand(si).isReg() && mi->getOperand(si).getReg() &&
 442                mi->getOperand(si).isUse() && "two address instruction invalid");
 443
 444         // If the two operands are the same we just remove the use
 445         // and mark the def as def&use, otherwise we have to insert a copy.
 446         if (mi->getOperand(ti).getReg() != mi->getOperand(si).getReg()) {
 447           // Rewrite:
 448           //     a = b op c
 449           // to:
 450           //     a = b
 451           //     a = a op c
 452           unsigned regA = mi->getOperand(ti).getReg();
 453           unsigned regB = mi->getOperand(si).getReg();
 454
 455           assert(TargetRegisterInfo::isVirtualRegister(regA) &&
 456                  TargetRegisterInfo::isVirtualRegister(regB) &&
 457                  "cannot update physical register live information");
 458
 459 #ifndef NDEBUG
 460           // First, verify that we don't have a use of a in the instruction (a =
 461           // b + a for example) because our transformation will not work. This
 462           // should never occur because we are in SSA form.
 463           for (unsigned i = 0; i != mi->getNumOperands(); ++i)
 464             assert((int)i == ti ||
 465                    !mi->getOperand(i).isReg() ||
 466                    mi->getOperand(i).getReg() != regA);
 467 #endif
 468
 469           // If this instruction is not the killing user of B, see if we can
 470           // rearrange the code to make it so.  Making it the killing user will
 471           // allow us to coalesce A and B together, eliminating the copy we are
 472           // about to insert.
 473           if (!mi->killsRegister(regB)) {
 474             // If regA is dead and the instruction can be deleted, just delete
 475             // it so it doesn't clobber regB.
 476             if (mi->getOperand(ti).isDead() && isSafeToDelete(mi, TII)) {
 477               mbbi->erase(mi); // Nuke the old inst.
 478               mi = nmi;
 479               ++NumDeletes;
 480               break; // Done with this instruction.
 481             }
 482
 483             // If this instruction is commutative, check to see if C dies.  If
 484             // so, swap the B and C operands.  This makes the live ranges of A
 485             // and C joinable.
 486             // FIXME: This code also works for A := B op C instructions.
 487             if (TID.isCommutable() && mi->getNumOperands() >= 3) {
 488               assert(mi->getOperand(3-si).isReg() &&
 489                      "Not a proper commutative instruction!");
 490               unsigned regC = mi->getOperand(3-si).getReg();
 491               if (mi->killsRegister(regC)) {
 492                 if (CommuteInstruction(mi, mbbi, regC, Dist, DistanceMap)) {
 493                   ++NumCommuted;
 494                   regB = regC;
 495                   goto InstructionRearranged;
 496                 }
 497               }
 498             }
 499
 500             // If this instruction is potentially convertible to a true
 501             // three-address instruction,
 502             if (TID.isConvertibleTo3Addr()) {
 503               // FIXME: This assumes there are no more operands which are tied
 504               // to another register.
 505 #ifndef NDEBUG
 506               for (unsigned i = si + 1, e = TID.getNumOperands(); i < e; ++i)
 507                 assert(TID.getOperandConstraint(i, TOI::TIED_TO) == -1);
 508 #endif
 509
 510               MachineInstr *NewMI = TII->convertToThreeAddress(mbbi, mi, LV);
 511               if (NewMI) {
 512                 DOUT << "2addr: CONVERTING 2-ADDR: " << *mi;
 513                 DOUT << "2addr:         TO 3-ADDR: " << *NewMI;
 514                 bool Sunk = false;
 515
 516                 if (NewMI->findRegisterUseOperand(regB, false, TRI))
 517                   // FIXME: Temporary workaround. If the new instruction doesn't
 518                   // uses regB, convertToThreeAddress must have created more
 519                   // then one instruction.
 520                   Sunk = Sink3AddrInstruction(mbbi, NewMI, regB, mi);
 521
 522                 mbbi->erase(mi); // Nuke the old inst.
 523
 524                 if (!Sunk) {
 525                   DistanceMap.insert(std::make_pair(NewMI, Dist));
 526                   mi = NewMI;
 527                   nmi = next(mi);
 528                 }
 529
 530                 ++NumConvertedTo3Addr;
 531                 break; // Done with this instruction.
 532               }
 533             }
 534           }
 535
 536           // If it's profitable to commute the instruction, do so.
 537           if (TID.isCommutable() && mi->getNumOperands() >= 3) {
 538             unsigned regC = mi->getOperand(3-si).getReg();
 539             if (isProfitableToCommute(regB, regC, mi, mbbi, Dist, DistanceMap))
 540               if (CommuteInstruction(mi, mbbi, regC, Dist, DistanceMap)) {
 541                 ++NumAggrCommuted;
 542                 ++NumCommuted;
 543                 regB = regC;
 544               }
 545           }
 546
 547         InstructionRearranged:
 548           const TargetRegisterClass* rc = MRI->getRegClass(regA);
 549           MachineInstr *DefMI = MRI->getVRegDef(regB);
 550           // If it's safe and profitable, remat the definition instead of
 551           // copying it.
 552           if (DefMI &&
 553               DefMI->getDesc().isAsCheapAsAMove() &&
 554               DefMI->isSafeToReMat(TII, regB) &&
 555               isProfitableToReMat(regB, rc, mi, DefMI, mbbi, Dist,DistanceMap)){
 556             DEBUG(cerr << "2addr: REMATTING : " << *DefMI << "\n");
 557             TII->reMaterialize(*mbbi, mi, regA, DefMI);
 558             ReMatRegs.set(regB);
 559             ++NumReMats;
 560           } else {
 561             TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc);
 562           }
 563
 564           MachineBasicBlock::iterator prevMI = prior(mi);
 565           // Update DistanceMap.
 566           DistanceMap.insert(std::make_pair(prevMI, Dist));
 567           DistanceMap[mi] = ++Dist;
 568
 569           // Update live variables for regB.
 570           if (LV) {
 571             LiveVariables::VarInfo& varInfoB = LV->getVarInfo(regB);
 572
 573             // regB is used in this BB.
 574             varInfoB.UsedBlocks[mbbi->getNumber()] = true;
 575
 576             if (LV->removeVirtualRegisterKilled(regB,  mi))
 577               LV->addVirtualRegisterKilled(regB, prevMI);
 578
 579             if (LV->removeVirtualRegisterDead(regB, mi))
 580               LV->addVirtualRegisterDead(regB, prevMI);
 581           }
 582
 583           DOUT << "\t\tprepend:\t"; DEBUG(prevMI->print(*cerr.stream(), &TM));
 584
 585           // Replace all occurences of regB with regA.
 586           for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) {
 587             if (mi->getOperand(i).isReg() &&
 588                 mi->getOperand(i).getReg() == regB)
 589               mi->getOperand(i).setReg(regA);
 590           }
 591         }
 592
 593         assert(mi->getOperand(ti).isDef() && mi->getOperand(si).isUse());
 594         mi->getOperand(ti).setReg(mi->getOperand(si).getReg());
 595         MadeChange = true;
 596
 597         DOUT << "\t\trewrite to:\t"; DEBUG(mi->print(*cerr.stream(), &TM));
 598       }
 599
 600       mi = nmi;
 601     }
 602   }
 603
 604   // Some remat'ed instructions are dead.
 605   int VReg = ReMatRegs.find_first();
 606   while (VReg != -1) {
 607     if (MRI->use_empty(VReg)) {
 608       MachineInstr *DefMI = MRI->getVRegDef(VReg);
 609       DefMI->eraseFromParent();
 610     }
 611     VReg = ReMatRegs.find_next(VReg);
 612   }
 613
 614   return MadeChange;
 615 }