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     // DistanceMap - Keep track the distance of a MI from the start of the
  67     // current basic block.
  68     DenseMap<MachineInstr*, unsigned> DistanceMap;
  69
  70     // SrcRegMap - A map from virtual registers to physical registers which
  71     // are likely targets to be coalesced to due to copies from physical
  72     // registers to virtual registers. e.g. v1024 = move r0.
  73     DenseMap<unsigned, unsigned> SrcRegMap;
  74
  75     // DstRegMap - A map from virtual registers to physical registers which
  76     // are likely targets to be coalesced to due to copies to physical
  77     // registers from virtual registers. e.g. r1 = move v1024.
  78     DenseMap<unsigned, unsigned> DstRegMap;
  79
  80     bool Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI,
  81                               unsigned Reg,
  82                               MachineBasicBlock::iterator OldPos);
  83
  84     bool isProfitableToReMat(unsigned Reg, const TargetRegisterClass *RC,
  85                              MachineInstr *MI, MachineInstr *DefMI,
  86                              MachineBasicBlock *MBB, unsigned Loc);
  87
  88     bool NoUseAfterLastDef(unsigned Reg, MachineBasicBlock *MBB, unsigned Dist,
  89                            unsigned &LastDef);
  90
  91     MachineInstr *FindLastUseInMBB(unsigned Reg, MachineBasicBlock *MBB,
  92                                    unsigned Dist);
  93
  94     bool isProfitableToCommute(unsigned regB, unsigned regC,
  95                                MachineInstr *MI, MachineBasicBlock *MBB,
  96                                unsigned Dist);
  97
  98     bool CommuteInstruction(MachineBasicBlock::iterator &mi,
  99                             MachineFunction::iterator &mbbi,
 100                             unsigned RegB, unsigned RegC, unsigned Dist);
 101
 102     bool isProfitableToConv3Addr(unsigned RegA);
 103
 104     bool ConvertInstTo3Addr(MachineBasicBlock::iterator &mi,
 105                             MachineBasicBlock::iterator &nmi,
 106                             MachineFunction::iterator &mbbi,
 107                             unsigned RegB, unsigned Dist);
 108
 109     void ProcessCopy(MachineInstr *MI, MachineBasicBlock *MBB,
 110                      SmallPtrSet<MachineInstr*, 8> &Processed);
 111
 112   public:
 113     static char ID; // Pass identification, replacement for typeid
 114     TwoAddressInstructionPass() : MachineFunctionPass(&ID) {}
 115
 116     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 117       AU.setPreservesCFG();
 118       AU.addPreserved<LiveVariables>();
 119       AU.addPreservedID(MachineLoopInfoID);
 120       AU.addPreservedID(MachineDominatorsID);
 121       if (StrongPHIElim)
 122         AU.addPreservedID(StrongPHIEliminationID);
 123       else
 124         AU.addPreservedID(PHIEliminationID);
 125       MachineFunctionPass::getAnalysisUsage(AU);
 126     }
 127
 128     /// runOnMachineFunction - Pass entry point.
 129     bool runOnMachineFunction(MachineFunction&);
 130   };
 131 }
 132
 133 char TwoAddressInstructionPass::ID = 0;
 134 static RegisterPass<TwoAddressInstructionPass>
 135 X("twoaddressinstruction", "Two-Address instruction pass");
 136
 137 const PassInfo *const llvm::TwoAddressInstructionPassID = &X;
 138
 139 /// Sink3AddrInstruction - A two-address instruction has been converted to a
 140 /// three-address instruction to avoid clobbering a register. Try to sink it
 141 /// past the instruction that would kill the above mentioned register to reduce
 142 /// register pressure.
 143 bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB,
 144                                            MachineInstr *MI, unsigned SavedReg,
 145                                            MachineBasicBlock::iterator OldPos) {
 146   // Check if it's safe to move this instruction.
 147   bool SeenStore = true; // Be conservative.
 148   if (!MI->isSafeToMove(TII, SeenStore))
 149     return false;
 150
 151   unsigned DefReg = 0;
 152   SmallSet<unsigned, 4> UseRegs;
 153
 154   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 155     const MachineOperand &MO = MI->getOperand(i);
 156     if (!MO.isReg())
 157       continue;
 158     unsigned MOReg = MO.getReg();
 159     if (!MOReg)
 160       continue;
 161     if (MO.isUse() && MOReg != SavedReg)
 162       UseRegs.insert(MO.getReg());
 163     if (!MO.isDef())
 164       continue;
 165     if (MO.isImplicit())
 166       // Don't try to move it if it implicitly defines a register.
 167       return false;
 168     if (DefReg)
 169       // For now, don't move any instructions that define multiple registers.
 170       return false;
 171     DefReg = MO.getReg();
 172   }
 173
 174   // Find the instruction that kills SavedReg.
 175   MachineInstr *KillMI = NULL;
 176   for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(SavedReg),
 177          UE = MRI->use_end(); UI != UE; ++UI) {
 178     MachineOperand &UseMO = UI.getOperand();
 179     if (!UseMO.isKill())
 180       continue;
 181     KillMI = UseMO.getParent();
 182     break;
 183   }
 184
 185   if (!KillMI || KillMI->getParent() != MBB || KillMI == MI)
 186     return false;
 187
 188   // If any of the definitions are used by another instruction between the
 189   // position and the kill use, then it's not safe to sink it.
 190   //
 191   // FIXME: This can be sped up if there is an easy way to query whether an
 192   // instruction is before or after another instruction. Then we can use
 193   // MachineRegisterInfo def / use instead.
 194   MachineOperand *KillMO = NULL;
 195   MachineBasicBlock::iterator KillPos = KillMI;
 196   ++KillPos;
 197
 198   unsigned NumVisited = 0;
 199   for (MachineBasicBlock::iterator I = next(OldPos); I != KillPos; ++I) {
 200     MachineInstr *OtherMI = I;
 201     if (NumVisited > 30)  // FIXME: Arbitrary limit to reduce compile time cost.
 202       return false;
 203     ++NumVisited;
 204     for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) {
 205       MachineOperand &MO = OtherMI->getOperand(i);
 206       if (!MO.isReg())
 207         continue;
 208       unsigned MOReg = MO.getReg();
 209       if (!MOReg)
 210         continue;
 211       if (DefReg == MOReg)
 212         return false;
 213
 214       if (MO.isKill()) {
 215         if (OtherMI == KillMI && MOReg == SavedReg)
 216           // Save the operand that kills the register. We want to unset the kill
 217           // marker if we can sink MI past it.
 218           KillMO = &MO;
 219         else if (UseRegs.count(MOReg))
 220           // One of the uses is killed before the destination.
 221           return false;
 222       }
 223     }
 224   }
 225
 226   // Update kill and LV information.
 227   KillMO->setIsKill(false);
 228   KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI);
 229   KillMO->setIsKill(true);
 230
 231   if (LV)
 232     LV->replaceKillInstruction(SavedReg, KillMI, MI);
 233
 234   // Move instruction to its destination.
 235   MBB->remove(MI);
 236   MBB->insert(KillPos, MI);
 237
 238   ++Num3AddrSunk;
 239   return true;
 240 }
 241
 242 /// isTwoAddrUse - Return true if the specified MI is using the specified
 243 /// register as a two-address operand.
 244 static bool isTwoAddrUse(MachineInstr *UseMI, unsigned Reg) {
 245   const TargetInstrDesc &TID = UseMI->getDesc();
 246   for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) {
 247     MachineOperand &MO = UseMI->getOperand(i);
 248     if (MO.isReg() && MO.getReg() == Reg &&
 249         (MO.isDef() || UseMI->isRegTiedToDefOperand(i)))
 250       // Earlier use is a two-address one.
 251       return true;
 252   }
 253   return false;
 254 }
 255
 256 /// isProfitableToReMat - Return true if the heuristics determines it is likely
 257 /// to be profitable to re-materialize the definition of Reg rather than copy
 258 /// the register.
 259 bool
 260 TwoAddressInstructionPass::isProfitableToReMat(unsigned Reg,
 261                                          const TargetRegisterClass *RC,
 262                                          MachineInstr *MI, MachineInstr *DefMI,
 263                                          MachineBasicBlock *MBB, unsigned Loc) {
 264   bool OtherUse = false;
 265   for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
 266          UE = MRI->use_end(); UI != UE; ++UI) {
 267     MachineOperand &UseMO = UI.getOperand();
 268     MachineInstr *UseMI = UseMO.getParent();
 269     MachineBasicBlock *UseMBB = UseMI->getParent();
 270     if (UseMBB == MBB) {
 271       DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI);
 272       if (DI != DistanceMap.end() && DI->second == Loc)
 273         continue;  // Current use.
 274       OtherUse = true;
 275       // There is at least one other use in the MBB that will clobber the
 276       // register.
 277       if (isTwoAddrUse(UseMI, Reg))
 278         return true;
 279     }
 280   }
 281
 282   // If other uses in MBB are not two-address uses, then don't remat.
 283   if (OtherUse)
 284     return false;
 285
 286   // No other uses in the same block, remat if it's defined in the same
 287   // block so it does not unnecessarily extend the live range.
 288   return MBB == DefMI->getParent();
 289 }
 290
 291 /// NoUseAfterLastDef - Return true if there are no intervening uses between the
 292 /// last instruction in the MBB that defines the specified register and the
 293 /// two-address instruction which is being processed. It also returns the last
 294 /// def location by reference
 295 bool TwoAddressInstructionPass::NoUseAfterLastDef(unsigned Reg,
 296                                            MachineBasicBlock *MBB, unsigned Dist,
 297                                            unsigned &LastDef) {
 298   LastDef = 0;
 299   unsigned LastUse = Dist;
 300   for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Reg),
 301          E = MRI->reg_end(); I != E; ++I) {
 302     MachineOperand &MO = I.getOperand();
 303     MachineInstr *MI = MO.getParent();
 304     if (MI->getParent() != MBB)
 305       continue;
 306     DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI);
 307     if (DI == DistanceMap.end())
 308       continue;
 309     if (MO.isUse() && DI->second < LastUse)
 310       LastUse = DI->second;
 311     if (MO.isDef() && DI->second > LastDef)
 312       LastDef = DI->second;
 313   }
 314
 315   return !(LastUse > LastDef && LastUse < Dist);
 316 }
 317
 318 MachineInstr *TwoAddressInstructionPass::FindLastUseInMBB(unsigned Reg,
 319                                                          MachineBasicBlock *MBB,
 320                                                          unsigned Dist) {
 321   unsigned LastUseDist = 0;
 322   MachineInstr *LastUse = 0;
 323   for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Reg),
 324          E = MRI->reg_end(); I != E; ++I) {
 325     MachineOperand &MO = I.getOperand();
 326     MachineInstr *MI = MO.getParent();
 327     if (MI->getParent() != MBB)
 328       continue;
 329     DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI);
 330     if (DI == DistanceMap.end())
 331       continue;
 332     if (DI->second >= Dist)
 333       continue;
 334
 335     if (MO.isUse() && DI->second > LastUseDist) {
 336       LastUse = DI->first;
 337       LastUseDist = DI->second;
 338     }
 339   }
 340   return LastUse;
 341 }
 342
 343 /// isCopyToReg - Return true if the specified MI is a copy instruction or
 344 /// a extract_subreg instruction. It also returns the source and destination
 345 /// registers and whether they are physical registers by reference.
 346 static bool isCopyToReg(MachineInstr &MI, const TargetInstrInfo *TII,
 347                         unsigned &SrcReg, unsigned &DstReg,
 348                         bool &IsSrcPhys, bool &IsDstPhys) {
 349   SrcReg = 0;
 350   DstReg = 0;
 351   unsigned SrcSubIdx, DstSubIdx;
 352   if (!TII->isMoveInstr(MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) {
 353     if (MI.getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) {
 354       DstReg = MI.getOperand(0).getReg();
 355       SrcReg = MI.getOperand(1).getReg();
 356     } else if (MI.getOpcode() == TargetInstrInfo::INSERT_SUBREG) {
 357       DstReg = MI.getOperand(0).getReg();
 358       SrcReg = MI.getOperand(2).getReg();
 359     } else if (MI.getOpcode() == TargetInstrInfo::SUBREG_TO_REG) {
 360       DstReg = MI.getOperand(0).getReg();
 361       SrcReg = MI.getOperand(2).getReg();
 362     }
 363   }
 364
 365   if (DstReg) {
 366     IsSrcPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg);
 367     IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
 368     return true;
 369   }
 370   return false;
 371 }
 372
 373 /// isKilled - Test if the given register value, which is used by the given
 374 /// instruction, is killed by the given instruction. This looks through
 375 /// coalescable copies to see if the original value is potentially not killed.
 376 ///
 377 /// For example, in this code:
 378 ///
 379 ///   %reg1034 = copy %reg1024
 380 ///   %reg1035 = copy %reg1025<kill>
 381 ///   %reg1036 = add %reg1034<kill>, %reg1035<kill>
 382 ///
 383 /// %reg1034 is not considered to be killed, since it is copied from a
 384 /// register which is not killed. Treating it as not killed lets the
 385 /// normal heuristics commute the (two-address) add, which lets
 386 /// coalescing eliminate the extra copy.
 387 ///
 388 static bool isKilled(MachineInstr &MI, unsigned Reg,
 389                      const MachineRegisterInfo *MRI,
 390                      const TargetInstrInfo *TII) {
 391   MachineInstr *DefMI = &MI;
 392   for (;;) {
 393     if (!DefMI->killsRegister(Reg))
 394       return false;
 395     if (TargetRegisterInfo::isPhysicalRegister(Reg))
 396       return true;
 397     MachineRegisterInfo::def_iterator Begin = MRI->def_begin(Reg);
 398     // If there are multiple defs, we can't do a simple analysis, so just
 399     // go with what the kill flag says.
 400     if (next(Begin) != MRI->def_end())
 401       return true;
 402     DefMI = &*Begin;
 403     bool IsSrcPhys, IsDstPhys;
 404     unsigned SrcReg,  DstReg;
 405     // If the def is something other than a copy, then it isn't going to
 406     // be coalesced, so follow the kill flag.
 407     if (!isCopyToReg(*DefMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
 408       return true;
 409     Reg = SrcReg;
 410   }
 411 }
 412
 413 /// isTwoAddrUse - Return true if the specified MI uses the specified register
 414 /// as a two-address use. If so, return the destination register by reference.
 415 static bool isTwoAddrUse(MachineInstr &MI, unsigned Reg, unsigned &DstReg) {
 416   const TargetInstrDesc &TID = MI.getDesc();
 417   unsigned NumOps = (MI.getOpcode() == TargetInstrInfo::INLINEASM)
 418     ? MI.getNumOperands() : TID.getNumOperands();
 419   for (unsigned i = 0; i != NumOps; ++i) {
 420     const MachineOperand &MO = MI.getOperand(i);
 421     if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg)
 422       continue;
 423     unsigned ti;
 424     if (MI.isRegTiedToDefOperand(i, &ti)) {
 425       DstReg = MI.getOperand(ti).getReg();
 426       return true;
 427     }
 428   }
 429   return false;
 430 }
 431
 432 /// findOnlyInterestingUse - Given a register, if has a single in-basic block
 433 /// use, return the use instruction if it's a copy or a two-address use.
 434 static
 435 MachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB,
 436                                      MachineRegisterInfo *MRI,
 437                                      const TargetInstrInfo *TII,
 438                                      bool &IsCopy,
 439                                      unsigned &DstReg, bool &IsDstPhys) {
 440   MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg);
 441   if (UI == MRI->use_end())
 442     return 0;
 443   MachineInstr &UseMI = *UI;
 444   if (++UI != MRI->use_end())
 445     // More than one use.
 446     return 0;
 447   if (UseMI.getParent() != MBB)
 448     return 0;
 449   unsigned SrcReg;
 450   bool IsSrcPhys;
 451   if (isCopyToReg(UseMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) {
 452     IsCopy = true;
 453     return &UseMI;
 454   }
 455   IsDstPhys = false;
 456   if (isTwoAddrUse(UseMI, Reg, DstReg)) {
 457     IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
 458     return &UseMI;
 459   }
 460   return 0;
 461 }
 462
 463 /// getMappedReg - Return the physical register the specified virtual register
 464 /// might be mapped to.
 465 static unsigned
 466 getMappedReg(unsigned Reg, DenseMap<unsigned, unsigned> &RegMap) {
 467   while (TargetRegisterInfo::isVirtualRegister(Reg))  {
 468     DenseMap<unsigned, unsigned>::iterator SI = RegMap.find(Reg);
 469     if (SI == RegMap.end())
 470       return 0;
 471     Reg = SI->second;
 472   }
 473   if (TargetRegisterInfo::isPhysicalRegister(Reg))
 474     return Reg;
 475   return 0;
 476 }
 477
 478 /// regsAreCompatible - Return true if the two registers are equal or aliased.
 479 ///
 480 static bool
 481 regsAreCompatible(unsigned RegA, unsigned RegB, const TargetRegisterInfo *TRI) {
 482   if (RegA == RegB)
 483     return true;
 484   if (!RegA || !RegB)
 485     return false;
 486   return TRI->regsOverlap(RegA, RegB);
 487 }
 488
 489
 490 /// isProfitableToReMat - Return true if it's potentially profitable to commute
 491 /// the two-address instruction that's being processed.
 492 bool
 493 TwoAddressInstructionPass::isProfitableToCommute(unsigned regB, unsigned regC,
 494                                        MachineInstr *MI, MachineBasicBlock *MBB,
 495                                        unsigned Dist) {
 496   // Determine if it's profitable to commute this two address instruction. In
 497   // general, we want no uses between this instruction and the definition of
 498   // the two-address register.
 499   // e.g.
 500   // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1
 501   // %reg1029<def> = MOV8rr %reg1028
 502   // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead>
 503   // insert => %reg1030<def> = MOV8rr %reg1028
 504   // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead>
 505   // In this case, it might not be possible to coalesce the second MOV8rr
 506   // instruction if the first one is coalesced. So it would be profitable to
 507   // commute it:
 508   // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1
 509   // %reg1029<def> = MOV8rr %reg1028
 510   // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead>
 511   // insert => %reg1030<def> = MOV8rr %reg1029
 512   // %reg1030<def> = ADD8rr %reg1029<kill>, %reg1028<kill>, %EFLAGS<imp-def,dead>
 513
 514   if (!MI->killsRegister(regC))
 515     return false;
 516
 517   // Ok, we have something like:
 518   // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead>
 519   // let's see if it's worth commuting it.
 520
 521   // Look for situations like this:
 522   // %reg1024<def> = MOV r1
 523   // %reg1025<def> = MOV r0
 524   // %reg1026<def> = ADD %reg1024, %reg1025
 525   // r0            = MOV %reg1026
 526   // Commute the ADD to hopefully eliminate an otherwise unavoidable copy.
 527   unsigned FromRegB = getMappedReg(regB, SrcRegMap);
 528   unsigned FromRegC = getMappedReg(regC, SrcRegMap);
 529   unsigned ToRegB = getMappedReg(regB, DstRegMap);
 530   unsigned ToRegC = getMappedReg(regC, DstRegMap);
 531   if (!regsAreCompatible(FromRegB, ToRegB, TRI) &&
 532       (regsAreCompatible(FromRegB, ToRegC, TRI) ||
 533        regsAreCompatible(FromRegC, ToRegB, TRI)))
 534     return true;
 535
 536   // If there is a use of regC between its last def (could be livein) and this
 537   // instruction, then bail.
 538   unsigned LastDefC = 0;
 539   if (!NoUseAfterLastDef(regC, MBB, Dist, LastDefC))
 540     return false;
 541
 542   // If there is a use of regB between its last def (could be livein) and this
 543   // instruction, then go ahead and make this transformation.
 544   unsigned LastDefB = 0;
 545   if (!NoUseAfterLastDef(regB, MBB, Dist, LastDefB))
 546     return true;
 547
 548   // Since there are no intervening uses for both registers, then commute
 549   // if the def of regC is closer. Its live interval is shorter.
 550   return LastDefB && LastDefC && LastDefC > LastDefB;
 551 }
 552
 553 /// CommuteInstruction - Commute a two-address instruction and update the basic
 554 /// block, distance map, and live variables if needed. Return true if it is
 555 /// successful.
 556 bool
 557 TwoAddressInstructionPass::CommuteInstruction(MachineBasicBlock::iterator &mi,
 558                                MachineFunction::iterator &mbbi,
 559                                unsigned RegB, unsigned RegC, unsigned Dist) {
 560   MachineInstr *MI = mi;
 561   DOUT << "2addr: COMMUTING  : " << *MI;
 562   MachineInstr *NewMI = TII->commuteInstruction(MI);
 563
 564   if (NewMI == 0) {
 565     DOUT << "2addr: COMMUTING FAILED!\n";
 566     return false;
 567   }
 568
 569   DOUT << "2addr: COMMUTED TO: " << *NewMI;
 570   // If the instruction changed to commute it, update livevar.
 571   if (NewMI != MI) {
 572     if (LV)
 573       // Update live variables
 574       LV->replaceKillInstruction(RegC, MI, NewMI);
 575
 576     mbbi->insert(mi, NewMI);           // Insert the new inst
 577     mbbi->erase(mi);                   // Nuke the old inst.
 578     mi = NewMI;
 579     DistanceMap.insert(std::make_pair(NewMI, Dist));
 580   }
 581
 582   // Update source register map.
 583   unsigned FromRegC = getMappedReg(RegC, SrcRegMap);
 584   if (FromRegC) {
 585     unsigned RegA = MI->getOperand(0).getReg();
 586     SrcRegMap[RegA] = FromRegC;
 587   }
 588
 589   return true;
 590 }
 591
 592 /// isProfitableToConv3Addr - Return true if it is profitable to convert the
 593 /// given 2-address instruction to a 3-address one.
 594 bool
 595 TwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA) {
 596   // Look for situations like this:
 597   // %reg1024<def> = MOV r1
 598   // %reg1025<def> = MOV r0
 599   // %reg1026<def> = ADD %reg1024, %reg1025
 600   // r2            = MOV %reg1026
 601   // Turn ADD into a 3-address instruction to avoid a copy.
 602   unsigned FromRegA = getMappedReg(RegA, SrcRegMap);
 603   unsigned ToRegA = getMappedReg(RegA, DstRegMap);
 604   return (FromRegA && ToRegA && !regsAreCompatible(FromRegA, ToRegA, TRI));
 605 }
 606
 607 /// ConvertInstTo3Addr - Convert the specified two-address instruction into a
 608 /// three address one. Return true if this transformation was successful.
 609 bool
 610 TwoAddressInstructionPass::ConvertInstTo3Addr(MachineBasicBlock::iterator &mi,
 611                                               MachineBasicBlock::iterator &nmi,
 612                                               MachineFunction::iterator &mbbi,
 613                                               unsigned RegB, unsigned Dist) {
 614   MachineInstr *NewMI = TII->convertToThreeAddress(mbbi, mi, LV);
 615   if (NewMI) {
 616     DOUT << "2addr: CONVERTING 2-ADDR: " << *mi;
 617     DOUT << "2addr:         TO 3-ADDR: " << *NewMI;
 618     bool Sunk = false;
 619
 620     if (NewMI->findRegisterUseOperand(RegB, false, TRI))
 621       // FIXME: Temporary workaround. If the new instruction doesn't
 622       // uses RegB, convertToThreeAddress must have created more
 623       // then one instruction.
 624       Sunk = Sink3AddrInstruction(mbbi, NewMI, RegB, mi);
 625
 626     mbbi->erase(mi); // Nuke the old inst.
 627
 628     if (!Sunk) {
 629       DistanceMap.insert(std::make_pair(NewMI, Dist));
 630       mi = NewMI;
 631       nmi = next(mi);
 632     }
 633     return true;
 634   }
 635
 636   return false;
 637 }
 638
 639 /// ProcessCopy - If the specified instruction is not yet processed, process it
 640 /// if it's a copy. For a copy instruction, we find the physical registers the
 641 /// source and destination registers might be mapped to. These are kept in
 642 /// point-to maps used to determine future optimizations. e.g.
 643 /// v1024 = mov r0
 644 /// v1025 = mov r1
 645 /// v1026 = add v1024, v1025
 646 /// r1    = mov r1026
 647 /// If 'add' is a two-address instruction, v1024, v1026 are both potentially
 648 /// coalesced to r0 (from the input side). v1025 is mapped to r1. v1026 is
 649 /// potentially joined with r1 on the output side. It's worthwhile to commute
 650 /// 'add' to eliminate a copy.
 651 void TwoAddressInstructionPass::ProcessCopy(MachineInstr *MI,
 652                                      MachineBasicBlock *MBB,
 653                                      SmallPtrSet<MachineInstr*, 8> &Processed) {
 654   if (Processed.count(MI))
 655     return;
 656
 657   bool IsSrcPhys, IsDstPhys;
 658   unsigned SrcReg, DstReg;
 659   if (!isCopyToReg(*MI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys))
 660     return;
 661
 662   if (IsDstPhys && !IsSrcPhys)
 663     DstRegMap.insert(std::make_pair(SrcReg, DstReg));
 664   else if (!IsDstPhys && IsSrcPhys) {
 665     bool isNew = SrcRegMap.insert(std::make_pair(DstReg, SrcReg)).second;
 666     if (!isNew)
 667       assert(SrcRegMap[DstReg] == SrcReg &&
 668              "Can't map to two src physical registers!");
 669
 670     SmallVector<unsigned, 4> VirtRegPairs;
 671     bool IsCopy = false;
 672     unsigned NewReg = 0;
 673     while (MachineInstr *UseMI = findOnlyInterestingUse(DstReg, MBB, MRI,TII,
 674                                                    IsCopy, NewReg, IsDstPhys)) {
 675       if (IsCopy) {
 676         if (!Processed.insert(UseMI))
 677           break;
 678       }
 679
 680       DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI);
 681       if (DI != DistanceMap.end())
 682         // Earlier in the same MBB.Reached via a back edge.
 683         break;
 684
 685       if (IsDstPhys) {
 686         VirtRegPairs.push_back(NewReg);
 687         break;
 688       }
 689       bool isNew = SrcRegMap.insert(std::make_pair(NewReg, DstReg)).second;
 690       if (!isNew)
 691         assert(SrcRegMap[NewReg] == DstReg &&
 692                "Can't map to two src physical registers!");
 693       VirtRegPairs.push_back(NewReg);
 694       DstReg = NewReg;
 695     }
 696
 697     if (!VirtRegPairs.empty()) {
 698       unsigned ToReg = VirtRegPairs.back();
 699       VirtRegPairs.pop_back();
 700       while (!VirtRegPairs.empty()) {
 701         unsigned FromReg = VirtRegPairs.back();
 702         VirtRegPairs.pop_back();
 703         bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second;
 704         if (!isNew)
 705           assert(DstRegMap[FromReg] == ToReg &&
 706                  "Can't map to two dst physical registers!");
 707         ToReg = FromReg;
 708       }
 709     }
 710   }
 711
 712   Processed.insert(MI);
 713 }
 714
 715 /// isSafeToDelete - If the specified instruction does not produce any side
 716 /// effects and all of its defs are dead, then it's safe to delete.
 717 static bool isSafeToDelete(MachineInstr *MI, unsigned Reg,
 718                            const TargetInstrInfo *TII,
 719                            SmallVector<unsigned, 4> &Kills) {
 720   const TargetInstrDesc &TID = MI->getDesc();
 721   if (TID.mayStore() || TID.isCall())
 722     return false;
 723   if (TID.isTerminator() || TID.hasUnmodeledSideEffects())
 724     return false;
 725
 726   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 727     MachineOperand &MO = MI->getOperand(i);
 728     if (!MO.isReg())
 729       continue;
 730     if (MO.isDef() && !MO.isDead())
 731       return false;
 732     if (MO.isUse() && MO.getReg() != Reg && MO.isKill())
 733       Kills.push_back(MO.getReg());
 734   }
 735
 736   return true;
 737 }
 738
 739 /// runOnMachineFunction - Reduce two-address instructions to two operands.
 740 ///
 741 bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
 742   DOUT << "Machine Function\n";
 743   const TargetMachine &TM = MF.getTarget();
 744   MRI = &MF.getRegInfo();
 745   TII = TM.getInstrInfo();
 746   TRI = TM.getRegisterInfo();
 747   LV = getAnalysisIfAvailable<LiveVariables>();
 748
 749   bool MadeChange = false;
 750
 751   DOUT << "********** REWRITING TWO-ADDR INSTRS **********\n";
 752   DEBUG(errs() << "********** Function: "
 753         << MF.getFunction()->getName() << '\n');
 754
 755   // ReMatRegs - Keep track of the registers whose def's are remat'ed.
 756   BitVector ReMatRegs;
 757   ReMatRegs.resize(MRI->getLastVirtReg()+1);
 758
 759   SmallPtrSet<MachineInstr*, 8> Processed;
 760   for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end();
 761        mbbi != mbbe; ++mbbi) {
 762     unsigned Dist = 0;
 763     DistanceMap.clear();
 764     SrcRegMap.clear();
 765     DstRegMap.clear();
 766     Processed.clear();
 767     for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end();
 768          mi != me; ) {
 769       MachineBasicBlock::iterator nmi = next(mi);
 770       const TargetInstrDesc &TID = mi->getDesc();
 771       bool FirstTied = true;
 772
 773       DistanceMap.insert(std::make_pair(mi, ++Dist));
 774
 775       ProcessCopy(&*mi, &*mbbi, Processed);
 776
 777       unsigned NumOps = (mi->getOpcode() == TargetInstrInfo::INLINEASM)
 778         ? mi->getNumOperands() : TID.getNumOperands();
 779       for (unsigned si = 0; si < NumOps; ++si) {
 780         unsigned ti = 0;
 781         if (!mi->isRegTiedToDefOperand(si, &ti))
 782           continue;
 783
 784         if (FirstTied) {
 785           ++NumTwoAddressInstrs;
 786           DOUT << '\t' << *mi;
 787         }
 788
 789         FirstTied = false;
 790
 791         assert(mi->getOperand(si).isReg() && mi->getOperand(si).getReg() &&
 792                mi->getOperand(si).isUse() && "two address instruction invalid");
 793
 794         // If the two operands are the same we just remove the use
 795         // and mark the def as def&use, otherwise we have to insert a copy.
 796         if (mi->getOperand(ti).getReg() != mi->getOperand(si).getReg()) {
 797           // Rewrite:
 798           //     a = b op c
 799           // to:
 800           //     a = b
 801           //     a = a op c
 802           unsigned regA = mi->getOperand(ti).getReg();
 803           unsigned regB = mi->getOperand(si).getReg();
 804           unsigned regASubIdx = mi->getOperand(ti).getSubReg();
 805
 806           assert(TargetRegisterInfo::isVirtualRegister(regB) &&
 807                  "cannot make instruction into two-address form");
 808
 809 #ifndef NDEBUG
 810           // First, verify that we don't have a use of a in the instruction (a =
 811           // b + a for example) because our transformation will not work. This
 812           // should never occur because we are in SSA form.
 813           for (unsigned i = 0; i != mi->getNumOperands(); ++i)
 814             assert(i == ti ||
 815                    !mi->getOperand(i).isReg() ||
 816                    mi->getOperand(i).getReg() != regA);
 817 #endif
 818
 819           // If this instruction is not the killing user of B, see if we can
 820           // rearrange the code to make it so.  Making it the killing user will
 821           // allow us to coalesce A and B together, eliminating the copy we are
 822           // about to insert.
 823           if (!isKilled(*mi, regB, MRI, TII)) {
 824             // If regA is dead and the instruction can be deleted, just delete
 825             // it so it doesn't clobber regB.
 826             SmallVector<unsigned, 4> Kills;
 827             if (mi->getOperand(ti).isDead() &&
 828                 isSafeToDelete(mi, regB, TII, Kills)) {
 829               SmallVector<std::pair<std::pair<unsigned, bool>
 830                 ,MachineInstr*>, 4> NewKills;
 831               bool ReallySafe = true;
 832               // If this instruction kills some virtual registers, we need
 833               // update the kill information. If it's not possible to do so,
 834               // then bail out.
 835               while (!Kills.empty()) {
 836                 unsigned Kill = Kills.back();
 837                 Kills.pop_back();
 838                 if (TargetRegisterInfo::isPhysicalRegister(Kill)) {
 839                   ReallySafe = false;
 840                   break;
 841                 }
 842                 MachineInstr *LastKill = FindLastUseInMBB(Kill, &*mbbi, Dist);
 843                 if (LastKill) {
 844                   bool isModRef = LastKill->modifiesRegister(Kill);
 845                   NewKills.push_back(std::make_pair(std::make_pair(Kill,isModRef),
 846                                                     LastKill));
 847                 } else {
 848                   ReallySafe = false;
 849                   break;
 850                 }
 851               }
 852
 853               if (ReallySafe) {
 854                 if (LV) {
 855                   while (!NewKills.empty()) {
 856                     MachineInstr *NewKill = NewKills.back().second;
 857                     unsigned Kill = NewKills.back().first.first;
 858                     bool isDead = NewKills.back().first.second;
 859                     NewKills.pop_back();
 860                     if (LV->removeVirtualRegisterKilled(Kill,  mi)) {
 861                       if (isDead)
 862                         LV->addVirtualRegisterDead(Kill, NewKill);
 863                       else
 864                         LV->addVirtualRegisterKilled(Kill, NewKill);
 865                     }
 866                   }
 867                 }
 868
 869                 // We're really going to nuke the old inst. If regB was marked
 870                 // as a kill we need to update its Kills list.
 871                 if (mi->getOperand(si).isKill())
 872                   LV->removeVirtualRegisterKilled(regB, mi);
 873
 874                 mbbi->erase(mi); // Nuke the old inst.
 875                 mi = nmi;
 876                 ++NumDeletes;
 877                 break; // Done with this instruction.
 878               }
 879             }
 880
 881             // If this instruction is commutative, check to see if C dies.  If
 882             // so, swap the B and C operands.  This makes the live ranges of A
 883             // and C joinable.
 884             // FIXME: This code also works for A := B op C instructions.
 885             unsigned SrcOp1, SrcOp2;
 886             if (TID.isCommutable() && mi->getNumOperands() >= 3 &&
 887                 TII->findCommutedOpIndices(mi, SrcOp1, SrcOp2)) {
 888               unsigned regC = 0;
 889               if (si == SrcOp1)
 890                 regC = mi->getOperand(SrcOp2).getReg();
 891               else if (si == SrcOp2)
 892                 regC = mi->getOperand(SrcOp1).getReg();
 893               if (isKilled(*mi, regC, MRI, TII)) {
 894                 if (CommuteInstruction(mi, mbbi, regB, regC, Dist)) {
 895                   ++NumCommuted;
 896                   regB = regC;
 897                   goto InstructionRearranged;
 898                 }
 899               }
 900             }
 901
 902             // If this instruction is potentially convertible to a true
 903             // three-address instruction,
 904             if (TID.isConvertibleTo3Addr()) {
 905               // FIXME: This assumes there are no more operands which are tied
 906               // to another register.
 907 #ifndef NDEBUG
 908               for (unsigned i = si + 1, e = TID.getNumOperands(); i < e; ++i)
 909                 assert(TID.getOperandConstraint(i, TOI::TIED_TO) == -1);
 910 #endif
 911
 912               if (ConvertInstTo3Addr(mi, nmi, mbbi, regB, Dist)) {
 913                 ++NumConvertedTo3Addr;
 914                 break; // Done with this instruction.
 915               }
 916             }
 917           }
 918
 919           // If it's profitable to commute the instruction, do so.
 920           unsigned SrcOp1, SrcOp2;
 921           if (TID.isCommutable() && mi->getNumOperands() >= 3 &&
 922               TII->findCommutedOpIndices(mi, SrcOp1, SrcOp2)) {
 923             unsigned regC = 0;
 924             if (si == SrcOp1)
 925               regC = mi->getOperand(SrcOp2).getReg();
 926             else if (si == SrcOp2)
 927               regC = mi->getOperand(SrcOp1).getReg();
 928
 929             if (regC && isProfitableToCommute(regB, regC, mi, mbbi, Dist))
 930               if (CommuteInstruction(mi, mbbi, regB, regC, Dist)) {
 931                 ++NumAggrCommuted;
 932                 ++NumCommuted;
 933                 regB = regC;
 934                 goto InstructionRearranged;
 935               }
 936           }
 937
 938           // If it's profitable to convert the 2-address instruction to a
 939           // 3-address one, do so.
 940           if (TID.isConvertibleTo3Addr() && isProfitableToConv3Addr(regA)) {
 941             if (ConvertInstTo3Addr(mi, nmi, mbbi, regB, Dist)) {
 942               ++NumConvertedTo3Addr;
 943               break; // Done with this instruction.
 944             }
 945           }
 946
 947         InstructionRearranged:
 948           const TargetRegisterClass* rc = MRI->getRegClass(regB);
 949           MachineInstr *DefMI = MRI->getVRegDef(regB);
 950           // If it's safe and profitable, remat the definition instead of
 951           // copying it.
 952           if (DefMI &&
 953               DefMI->getDesc().isAsCheapAsAMove() &&
 954               DefMI->isSafeToReMat(TII, regB) &&
 955               isProfitableToReMat(regB, rc, mi, DefMI, mbbi, Dist)){
 956             DEBUG(cerr << "2addr: REMATTING : " << *DefMI << "\n");
 957             TII->reMaterialize(*mbbi, mi, regA, regASubIdx, DefMI);
 958             ReMatRegs.set(regB);
 959             ++NumReMats;
 960           } else {
 961             bool Emitted = TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc);
 962             (void)Emitted;
 963             assert(Emitted && "Unable to issue a copy instruction!\n");
 964           }
 965
 966           MachineBasicBlock::iterator prevMI = prior(mi);
 967           // Update DistanceMap.
 968           DistanceMap.insert(std::make_pair(prevMI, Dist));
 969           DistanceMap[mi] = ++Dist;
 970
 971           // Update live variables for regB.
 972           if (LV) {
 973             if (LV->removeVirtualRegisterKilled(regB,  mi))
 974               LV->addVirtualRegisterKilled(regB, prevMI);
 975
 976             if (LV->removeVirtualRegisterDead(regB, mi))
 977               LV->addVirtualRegisterDead(regB, prevMI);
 978           }
 979
 980           DOUT << "\t\tprepend:\t" << *prevMI;
 981
 982           // Replace all occurences of regB with regA.
 983           for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) {
 984             if (mi->getOperand(i).isReg() &&
 985                 mi->getOperand(i).getReg() == regB)
 986               mi->getOperand(i).setReg(regA);
 987           }
 988         }
 989
 990         assert(mi->getOperand(ti).isDef() && mi->getOperand(si).isUse());
 991         mi->getOperand(ti).setReg(mi->getOperand(si).getReg());
 992         MadeChange = true;
 993
 994         DOUT << "\t\trewrite to:\t" << *mi;
 995       }
 996
 997       mi = nmi;
 998     }
 999   }
1000
1001   // Some remat'ed instructions are dead.
1002   int VReg = ReMatRegs.find_first();
1003   while (VReg != -1) {
1004     if (MRI->use_empty(VReg)) {
1005       MachineInstr *DefMI = MRI->getVRegDef(VReg);
1006       DefMI->eraseFromParent();
1007     }
1008     VReg = ReMatRegs.find_next(VReg);
1009   }
1010
1011   return MadeChange;
1012 }