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/Support/Compiler.h"
  41 #include "llvm/Support/Debug.h"
  42 #include "llvm/ADT/BitVector.h"
  43 #include "llvm/ADT/DenseMap.h"
  44 #include "llvm/ADT/SmallPtrSet.h"
  45 #include "llvm/ADT/Statistic.h"
  46 #include "llvm/ADT/STLExtras.h"
  47 using namespace llvm;
  48
  49 STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions");
  50 STATISTIC(NumCommuted        , "Number of instructions commuted to coalesce");
  51 STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address");
  52 STATISTIC(Num3AddrSunk,        "Number of 3-address instructions sunk");
  53 STATISTIC(NumReMats,           "Number of instructions re-materialized");
  54
  55 namespace {
  56   class VISIBILITY_HIDDEN TwoAddressInstructionPass
  57     : public MachineFunctionPass {
  58     const TargetInstrInfo *TII;
  59     const TargetRegisterInfo *TRI;
  60     MachineRegisterInfo *MRI;
  61     LiveVariables *LV;
  62
  63     bool Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI,
  64                               unsigned Reg,
  65                               MachineBasicBlock::iterator OldPos);
  66
  67     bool isProfitableToReMat(unsigned Reg, const TargetRegisterClass *RC,
  68                              MachineInstr *MI, MachineInstr *DefMI,
  69                              MachineBasicBlock *MBB, unsigned Loc,
  70                              DenseMap<MachineInstr*, unsigned> &DistanceMap);
  71   public:
  72     static char ID; // Pass identification, replacement for typeid
  73     TwoAddressInstructionPass() : MachineFunctionPass(&ID) {}
  74
  75     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  76       AU.addPreserved<LiveVariables>();
  77       AU.addPreservedID(MachineLoopInfoID);
  78       AU.addPreservedID(MachineDominatorsID);
  79       AU.addPreservedID(PHIEliminationID);
  80       MachineFunctionPass::getAnalysisUsage(AU);
  81     }
  82
  83     /// runOnMachineFunction - Pass entry point.
  84     bool runOnMachineFunction(MachineFunction&);
  85   };
  86 }
  87
  88 char TwoAddressInstructionPass::ID = 0;
  89 static RegisterPass<TwoAddressInstructionPass>
  90 X("twoaddressinstruction", "Two-Address instruction pass");
  91
  92 const PassInfo *const llvm::TwoAddressInstructionPassID = &X;
  93
  94 /// Sink3AddrInstruction - A two-address instruction has been converted to a
  95 /// three-address instruction to avoid clobbering a register. Try to sink it
  96 /// past the instruction that would kill the above mentioned register to reduce
  97 /// register pressure.
  98 bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB,
  99                                            MachineInstr *MI, unsigned SavedReg,
 100                                            MachineBasicBlock::iterator OldPos) {
 101   // Check if it's safe to move this instruction.
 102   bool SeenStore = true; // Be conservative.
 103   if (!MI->isSafeToMove(TII, SeenStore))
 104     return false;
 105
 106   unsigned DefReg = 0;
 107   SmallSet<unsigned, 4> UseRegs;
 108
 109   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 110     const MachineOperand &MO = MI->getOperand(i);
 111     if (!MO.isReg())
 112       continue;
 113     unsigned MOReg = MO.getReg();
 114     if (!MOReg)
 115       continue;
 116     if (MO.isUse() && MOReg != SavedReg)
 117       UseRegs.insert(MO.getReg());
 118     if (!MO.isDef())
 119       continue;
 120     if (MO.isImplicit())
 121       // Don't try to move it if it implicitly defines a register.
 122       return false;
 123     if (DefReg)
 124       // For now, don't move any instructions that define multiple registers.
 125       return false;
 126     DefReg = MO.getReg();
 127   }
 128
 129   // Find the instruction that kills SavedReg.
 130   MachineInstr *KillMI = NULL;
 131   for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(SavedReg),
 132          UE = MRI->use_end(); UI != UE; ++UI) {
 133     MachineOperand &UseMO = UI.getOperand();
 134     if (!UseMO.isKill())
 135       continue;
 136     KillMI = UseMO.getParent();
 137     break;
 138   }
 139
 140   if (!KillMI || KillMI->getParent() != MBB)
 141     return false;
 142
 143   // If any of the definitions are used by another instruction between the
 144   // position and the kill use, then it's not safe to sink it.
 145   //
 146   // FIXME: This can be sped up if there is an easy way to query whether an
 147   // instruction is before or after another instruction. Then we can use
 148   // MachineRegisterInfo def / use instead.
 149   MachineOperand *KillMO = NULL;
 150   MachineBasicBlock::iterator KillPos = KillMI;
 151   ++KillPos;
 152
 153   unsigned NumVisited = 0;
 154   for (MachineBasicBlock::iterator I = next(OldPos); I != KillPos; ++I) {
 155     MachineInstr *OtherMI = I;
 156     if (NumVisited > 30)  // FIXME: Arbitrary limit to reduce compile time cost.
 157       return false;
 158     ++NumVisited;
 159     for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) {
 160       MachineOperand &MO = OtherMI->getOperand(i);
 161       if (!MO.isReg())
 162         continue;
 163       unsigned MOReg = MO.getReg();
 164       if (!MOReg)
 165         continue;
 166       if (DefReg == MOReg)
 167         return false;
 168
 169       if (MO.isKill()) {
 170         if (OtherMI == KillMI && MOReg == SavedReg)
 171           // Save the operand that kills the register. We want to unset the kill
 172           // marker if we can sink MI past it.
 173           KillMO = &MO;
 174         else if (UseRegs.count(MOReg))
 175           // One of the uses is killed before the destination.
 176           return false;
 177       }
 178     }
 179   }
 180
 181   // Update kill and LV information.
 182   KillMO->setIsKill(false);
 183   KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI);
 184   KillMO->setIsKill(true);
 185
 186   if (LV)
 187     LV->replaceKillInstruction(SavedReg, KillMI, MI);
 188
 189   // Move instruction to its destination.
 190   MBB->remove(MI);
 191   MBB->insert(KillPos, MI);
 192
 193   ++Num3AddrSunk;
 194   return true;
 195 }
 196
 197 /// isTwoAddrUse - Return true if the specified MI is using the specified
 198 /// register as a two-address operand.
 199 static bool isTwoAddrUse(MachineInstr *UseMI, unsigned Reg) {
 200   const TargetInstrDesc &TID = UseMI->getDesc();
 201   for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) {
 202     MachineOperand &MO = UseMI->getOperand(i);
 203     if (MO.isReg() && MO.getReg() == Reg &&
 204         (MO.isDef() || TID.getOperandConstraint(i, TOI::TIED_TO) != -1))
 205       // Earlier use is a two-address one.
 206       return true;
 207   }
 208   return false;
 209 }
 210
 211 /// isProfitableToReMat - Return true if the heuristics determines it is likely
 212 /// to be profitable to re-materialize the definition of Reg rather than copy
 213 /// the register.
 214 bool
 215 TwoAddressInstructionPass::isProfitableToReMat(unsigned Reg,
 216                                 const TargetRegisterClass *RC,
 217                                 MachineInstr *MI, MachineInstr *DefMI,
 218                                 MachineBasicBlock *MBB, unsigned Loc,
 219                                 DenseMap<MachineInstr*, unsigned> &DistanceMap){
 220   bool OtherUse = false;
 221   for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
 222          UE = MRI->use_end(); UI != UE; ++UI) {
 223     MachineOperand &UseMO = UI.getOperand();
 224     if (!UseMO.isUse())
 225       continue;
 226     MachineInstr *UseMI = UseMO.getParent();
 227     MachineBasicBlock *UseMBB = UseMI->getParent();
 228     if (UseMBB == MBB) {
 229       DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI);
 230       if (DI != DistanceMap.end() && DI->second == Loc)
 231         continue;  // Current use.
 232       OtherUse = true;
 233       // There is at least one other use in the MBB that will clobber the
 234       // register.
 235       if (isTwoAddrUse(UseMI, Reg))
 236         return true;
 237     }
 238   }
 239
 240   // If other uses in MBB are not two-address uses, then don't remat.
 241   if (OtherUse)
 242     return false;
 243
 244   // No other uses in the same block, remat if it's defined in the same
 245   // block so it does not unnecessarily extend the live range.
 246   return MBB == DefMI->getParent();
 247 }
 248
 249 /// runOnMachineFunction - Reduce two-address instructions to two operands.
 250 ///
 251 bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
 252   DOUT << "Machine Function\n";
 253   const TargetMachine &TM = MF.getTarget();
 254   MRI = &MF.getRegInfo();
 255   TII = TM.getInstrInfo();
 256   TRI = TM.getRegisterInfo();
 257   LV = getAnalysisToUpdate<LiveVariables>();
 258
 259   bool MadeChange = false;
 260
 261   DOUT << "********** REWRITING TWO-ADDR INSTRS **********\n";
 262   DOUT << "********** Function: " << MF.getFunction()->getName() << '\n';
 263
 264   // ReMatRegs - Keep track of the registers whose def's are remat'ed.
 265   BitVector ReMatRegs;
 266   ReMatRegs.resize(MRI->getLastVirtReg()+1);
 267
 268   // DistanceMap - Keep track the distance of a MI from the start of the
 269   // current basic block.
 270   DenseMap<MachineInstr*, unsigned> DistanceMap;
 271
 272   for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end();
 273        mbbi != mbbe; ++mbbi) {
 274     unsigned Dist = 0;
 275     DistanceMap.clear();
 276     for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end();
 277          mi != me; ) {
 278       MachineBasicBlock::iterator nmi = next(mi);
 279       const TargetInstrDesc &TID = mi->getDesc();
 280       bool FirstTied = true;
 281
 282       DistanceMap.insert(std::make_pair(mi, ++Dist));
 283       for (unsigned si = 1, e = TID.getNumOperands(); si < e; ++si) {
 284         int ti = TID.getOperandConstraint(si, TOI::TIED_TO);
 285         if (ti == -1)
 286           continue;
 287
 288         if (FirstTied) {
 289           ++NumTwoAddressInstrs;
 290           DOUT << '\t'; DEBUG(mi->print(*cerr.stream(), &TM));
 291         }
 292
 293         FirstTied = false;
 294
 295         assert(mi->getOperand(si).isReg() && mi->getOperand(si).getReg() &&
 296                mi->getOperand(si).isUse() && "two address instruction invalid");
 297
 298         // If the two operands are the same we just remove the use
 299         // and mark the def as def&use, otherwise we have to insert a copy.
 300         if (mi->getOperand(ti).getReg() != mi->getOperand(si).getReg()) {
 301           // Rewrite:
 302           //     a = b op c
 303           // to:
 304           //     a = b
 305           //     a = a op c
 306           unsigned regA = mi->getOperand(ti).getReg();
 307           unsigned regB = mi->getOperand(si).getReg();
 308
 309           assert(TargetRegisterInfo::isVirtualRegister(regA) &&
 310                  TargetRegisterInfo::isVirtualRegister(regB) &&
 311                  "cannot update physical register live information");
 312
 313 #ifndef NDEBUG
 314           // First, verify that we don't have a use of a in the instruction (a =
 315           // b + a for example) because our transformation will not work. This
 316           // should never occur because we are in SSA form.
 317           for (unsigned i = 0; i != mi->getNumOperands(); ++i)
 318             assert((int)i == ti ||
 319                    !mi->getOperand(i).isReg() ||
 320                    mi->getOperand(i).getReg() != regA);
 321 #endif
 322
 323           // If this instruction is not the killing user of B, see if we can
 324           // rearrange the code to make it so.  Making it the killing user will
 325           // allow us to coalesce A and B together, eliminating the copy we are
 326           // about to insert.
 327           if (!mi->killsRegister(regB)) {
 328             // If this instruction is commutative, check to see if C dies.  If
 329             // so, swap the B and C operands.  This makes the live ranges of A
 330             // and C joinable.
 331             // FIXME: This code also works for A := B op C instructions.
 332             if (TID.isCommutable() && mi->getNumOperands() >= 3) {
 333               assert(mi->getOperand(3-si).isReg() &&
 334                      "Not a proper commutative instruction!");
 335               unsigned regC = mi->getOperand(3-si).getReg();
 336
 337               if (mi->killsRegister(regC)) {
 338                 DOUT << "2addr: COMMUTING  : " << *mi;
 339                 MachineInstr *NewMI = TII->commuteInstruction(mi);
 340
 341                 if (NewMI == 0) {
 342                   DOUT << "2addr: COMMUTING FAILED!\n";
 343                 } else {
 344                   DOUT << "2addr: COMMUTED TO: " << *NewMI;
 345                   // If the instruction changed to commute it, update livevar.
 346                   if (NewMI != mi) {
 347                     if (LV)
 348                       // Update live variables
 349                       LV->replaceKillInstruction(regC, mi, NewMI);
 350
 351                     mbbi->insert(mi, NewMI);           // Insert the new inst
 352                     mbbi->erase(mi);                   // Nuke the old inst.
 353                     mi = NewMI;
 354                     DistanceMap.insert(std::make_pair(NewMI, Dist));
 355                   }
 356
 357                   ++NumCommuted;
 358                   regB = regC;
 359                   goto InstructionRearranged;
 360                 }
 361               }
 362             }
 363
 364             // If this instruction is potentially convertible to a true
 365             // three-address instruction,
 366             if (TID.isConvertibleTo3Addr()) {
 367               // FIXME: This assumes there are no more operands which are tied
 368               // to another register.
 369 #ifndef NDEBUG
 370               for (unsigned i = si + 1, e = TID.getNumOperands(); i < e; ++i)
 371                 assert(TID.getOperandConstraint(i, TOI::TIED_TO) == -1);
 372 #endif
 373
 374               MachineInstr *NewMI = TII->convertToThreeAddress(mbbi, mi, LV);
 375               if (NewMI) {
 376                 DOUT << "2addr: CONVERTING 2-ADDR: " << *mi;
 377                 DOUT << "2addr:         TO 3-ADDR: " << *NewMI;
 378                 bool Sunk = false;
 379
 380                 if (NewMI->findRegisterUseOperand(regB, false, TRI))
 381                   // FIXME: Temporary workaround. If the new instruction doesn't
 382                   // uses regB, convertToThreeAddress must have created more
 383                   // then one instruction.
 384                   Sunk = Sink3AddrInstruction(mbbi, NewMI, regB, mi);
 385
 386                 mbbi->erase(mi); // Nuke the old inst.
 387
 388                 if (!Sunk) {
 389                   DistanceMap.insert(std::make_pair(NewMI, Dist));
 390                   mi = NewMI;
 391                   nmi = next(mi);
 392                 }
 393
 394                 ++NumConvertedTo3Addr;
 395                 break; // Done with this instruction.
 396               }
 397             }
 398           }
 399
 400         InstructionRearranged:
 401           const TargetRegisterClass* rc = MRI->getRegClass(regA);
 402           MachineInstr *DefMI = MRI->getVRegDef(regB);
 403           // If it's safe and profitable, remat the definition instead of
 404           // copying it.
 405           if (DefMI &&
 406               DefMI->getDesc().isAsCheapAsAMove() &&
 407               DefMI->isSafeToReMat(TII, regB) &&
 408               isProfitableToReMat(regB, rc, mi, DefMI, mbbi, Dist,DistanceMap)){
 409             DEBUG(cerr << "2addr: REMATTING : " << *DefMI << "\n");
 410             TII->reMaterialize(*mbbi, mi, regA, DefMI);
 411             ReMatRegs.set(regB);
 412             ++NumReMats;
 413           } else {
 414             TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc);
 415           }
 416
 417           MachineBasicBlock::iterator prevMi = prior(mi);
 418           DOUT << "\t\tprepend:\t"; DEBUG(prevMi->print(*cerr.stream(), &TM));
 419
 420           // Update live variables for regB.
 421           if (LV) {
 422             LiveVariables::VarInfo& varInfoB = LV->getVarInfo(regB);
 423
 424             // regB is used in this BB.
 425             varInfoB.UsedBlocks[mbbi->getNumber()] = true;
 426
 427             if (LV->removeVirtualRegisterKilled(regB,  mi))
 428               LV->addVirtualRegisterKilled(regB, prevMi);
 429
 430             if (LV->removeVirtualRegisterDead(regB, mi))
 431               LV->addVirtualRegisterDead(regB, prevMi);
 432           }
 433
 434           // Replace all occurences of regB with regA.
 435           for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) {
 436             if (mi->getOperand(i).isReg() &&
 437                 mi->getOperand(i).getReg() == regB)
 438               mi->getOperand(i).setReg(regA);
 439           }
 440         }
 441
 442         assert(mi->getOperand(ti).isDef() && mi->getOperand(si).isUse());
 443         mi->getOperand(ti).setReg(mi->getOperand(si).getReg());
 444         MadeChange = true;
 445
 446         DOUT << "\t\trewrite to:\t"; DEBUG(mi->print(*cerr.stream(), &TM));
 447       }
 448
 449       mi = nmi;
 450     }
 451   }
 452
 453   // Some remat'ed instructions are dead.
 454   int VReg = ReMatRegs.find_first();
 455   while (VReg != -1) {
 456     if (MRI->use_empty(VReg)) {
 457       MachineInstr *DefMI = MRI->getVRegDef(VReg);
 458       DefMI->eraseFromParent();
 459     }
 460     VReg = ReMatRegs.find_next(VReg);
 461   }
 462
 463   return MadeChange;
 464 }