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/CommandLine.h"
  41 #include "llvm/Support/Compiler.h"
  42 #include "llvm/Support/Debug.h"
  43 #include "llvm/ADT/SmallPtrSet.h"
  44 #include "llvm/ADT/Statistic.h"
  45 #include "llvm/ADT/STLExtras.h"
  46 using namespace llvm;
  47
  48 STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions");
  49 STATISTIC(NumCommuted        , "Number of instructions commuted to coalesce");
  50 STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address");
  51 STATISTIC(Num3AddrSunk,        "Number of 3-address instructions sunk");
  52
  53 static cl::opt<bool>
  54 EnableReMat("2-addr-remat", cl::init(false), cl::Hidden,
  55             cl::desc("Two-addr conversion should remat when possible."));
  56
  57 namespace {
  58   class VISIBILITY_HIDDEN TwoAddressInstructionPass
  59     : public MachineFunctionPass {
  60     const TargetInstrInfo *TII;
  61     const TargetRegisterInfo *TRI;
  62     MachineRegisterInfo *MRI;
  63     LiveVariables *LV;
  64
  65     bool Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI,
  66                               unsigned Reg,
  67                               MachineBasicBlock::iterator OldPos);
  68   public:
  69     static char ID; // Pass identification, replacement for typeid
  70     TwoAddressInstructionPass() : MachineFunctionPass((intptr_t)&ID) {}
  71
  72     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  73       AU.addRequired<LiveVariables>();
  74       AU.addPreserved<LiveVariables>();
  75       AU.addPreservedID(MachineLoopInfoID);
  76       AU.addPreservedID(MachineDominatorsID);
  77       AU.addPreservedID(PHIEliminationID);
  78       MachineFunctionPass::getAnalysisUsage(AU);
  79     }
  80
  81     /// runOnMachineFunction - Pass entry point.
  82     bool runOnMachineFunction(MachineFunction&);
  83   };
  84 }
  85
  86 char TwoAddressInstructionPass::ID = 0;
  87 static RegisterPass<TwoAddressInstructionPass>
  88 X("twoaddressinstruction", "Two-Address instruction pass");
  89
  90 const PassInfo *const llvm::TwoAddressInstructionPassID = &X;
  91
  92 /// Sink3AddrInstruction - A two-address instruction has been converted to a
  93 /// three-address instruction to avoid clobbering a register. Try to sink it
  94 /// past the instruction that would kill the above mentioned register to reduce
  95 /// register pressure.
  96 ///
  97 bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB,
  98                                            MachineInstr *MI, unsigned SavedReg,
  99                                            MachineBasicBlock::iterator OldPos) {
 100   // Check if it's safe to move this instruction.
 101   bool SeenStore = true; // Be conservative.
 102   if (!MI->isSafeToMove(TII, SeenStore))
 103     return false;
 104
 105   unsigned DefReg = 0;
 106   SmallSet<unsigned, 4> UseRegs;
 107
 108   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 109     const MachineOperand &MO = MI->getOperand(i);
 110     if (!MO.isRegister())
 111       continue;
 112     unsigned MOReg = MO.getReg();
 113     if (!MOReg)
 114       continue;
 115     if (MO.isUse() && MOReg != SavedReg)
 116       UseRegs.insert(MO.getReg());
 117     if (!MO.isDef())
 118       continue;
 119     if (MO.isImplicit())
 120       // Don't try to move it if it implicitly defines a register.
 121       return false;
 122     if (DefReg)
 123       // For now, don't move any instructions that define multiple registers.
 124       return false;
 125     DefReg = MO.getReg();
 126   }
 127
 128   // Find the instruction that kills SavedReg.
 129   MachineInstr *KillMI = NULL;
 130
 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 if 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   for (MachineBasicBlock::iterator I = next(OldPos); I != KillPos; ++I) {
 154     MachineInstr *OtherMI = I;
 155
 156     for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) {
 157       MachineOperand &MO = OtherMI->getOperand(i);
 158       if (!MO.isRegister())
 159         continue;
 160       unsigned MOReg = MO.getReg();
 161       if (!MOReg)
 162         continue;
 163       if (DefReg == MOReg)
 164         return false;
 165
 166       if (MO.isKill()) {
 167         if (OtherMI == KillMI && MOReg == SavedReg)
 168           // Save the operand that kills the register. We want unset the kill
 169           // marker is we can sink MI past it.
 170           KillMO = &MO;
 171         else if (UseRegs.count(MOReg))
 172           // One of the uses is killed before the destination.
 173           return false;
 174       }
 175     }
 176   }
 177
 178   // Update kill and LV information.
 179   KillMO->setIsKill(false);
 180   KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI);
 181   KillMO->setIsKill(true);
 182   LiveVariables::VarInfo& VarInfo = LV->getVarInfo(SavedReg);
 183   VarInfo.removeKill(KillMI);
 184   VarInfo.Kills.push_back(MI);
 185
 186   // Move instruction to its destination.
 187   MBB->remove(MI);
 188   MBB->insert(KillPos, MI);
 189
 190   ++Num3AddrSunk;
 191   return true;
 192 }
 193
 194 /// runOnMachineFunction - Reduce two-address instructions to two operands.
 195 ///
 196 bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
 197   DOUT << "Machine Function\n";
 198   const TargetMachine &TM = MF.getTarget();
 199   MRI = &MF.getRegInfo();
 200   TII = TM.getInstrInfo();
 201   TRI = TM.getRegisterInfo();
 202   LV = &getAnalysis<LiveVariables>();
 203
 204   bool MadeChange = false;
 205
 206   DOUT << "********** REWRITING TWO-ADDR INSTRS **********\n";
 207   DOUT << "********** Function: " << MF.getFunction()->getName() << '\n';
 208
 209   SmallPtrSet<MachineInstr*, 8> ReMattedInstrs;
 210
 211   for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end();
 212        mbbi != mbbe; ++mbbi) {
 213     for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end();
 214          mi != me; ) {
 215       MachineBasicBlock::iterator nmi = next(mi);
 216       const TargetInstrDesc &TID = mi->getDesc();
 217       bool FirstTied = true;
 218
 219       for (unsigned si = 1, e = TID.getNumOperands(); si < e; ++si) {
 220         int ti = TID.getOperandConstraint(si, TOI::TIED_TO);
 221         if (ti == -1)
 222           continue;
 223
 224         if (FirstTied) {
 225           ++NumTwoAddressInstrs;
 226           DOUT << '\t'; DEBUG(mi->print(*cerr.stream(), &TM));
 227         }
 228
 229         FirstTied = false;
 230
 231         assert(mi->getOperand(si).isRegister() && mi->getOperand(si).getReg() &&
 232                mi->getOperand(si).isUse() && "two address instruction invalid");
 233
 234         // If the two operands are the same we just remove the use
 235         // and mark the def as def&use, otherwise we have to insert a copy.
 236         if (mi->getOperand(ti).getReg() != mi->getOperand(si).getReg()) {
 237           // Rewrite:
 238           //     a = b op c
 239           // to:
 240           //     a = b
 241           //     a = a op c
 242           unsigned regA = mi->getOperand(ti).getReg();
 243           unsigned regB = mi->getOperand(si).getReg();
 244
 245           assert(TargetRegisterInfo::isVirtualRegister(regA) &&
 246                  TargetRegisterInfo::isVirtualRegister(regB) &&
 247                  "cannot update physical register live information");
 248
 249 #ifndef NDEBUG
 250           // First, verify that we don't have a use of a in the instruction (a =
 251           // b + a for example) because our transformation will not work. This
 252           // should never occur because we are in SSA form.
 253           for (unsigned i = 0; i != mi->getNumOperands(); ++i)
 254             assert((int)i == ti ||
 255                    !mi->getOperand(i).isRegister() ||
 256                    mi->getOperand(i).getReg() != regA);
 257 #endif
 258
 259           // If this instruction is not the killing user of B, see if we can
 260           // rearrange the code to make it so.  Making it the killing user will
 261           // allow us to coalesce A and B together, eliminating the copy we are
 262           // about to insert.
 263           if (!mi->killsRegister(regB)) {
 264             // If this instruction is commutative, check to see if C dies.  If
 265             // so, swap the B and C operands.  This makes the live ranges of A
 266             // and C joinable.
 267             // FIXME: This code also works for A := B op C instructions.
 268             if (TID.isCommutable() && mi->getNumOperands() >= 3) {
 269               assert(mi->getOperand(3-si).isRegister() &&
 270                      "Not a proper commutative instruction!");
 271               unsigned regC = mi->getOperand(3-si).getReg();
 272
 273               if (mi->killsRegister(regC)) {
 274                 DOUT << "2addr: COMMUTING  : " << *mi;
 275                 MachineInstr *NewMI = TII->commuteInstruction(mi);
 276
 277                 if (NewMI == 0) {
 278                   DOUT << "2addr: COMMUTING FAILED!\n";
 279                 } else {
 280                   DOUT << "2addr: COMMUTED TO: " << *NewMI;
 281                   // If the instruction changed to commute it, update livevar.
 282                   if (NewMI != mi) {
 283                     LV->instructionChanged(mi, NewMI); // Update live variables
 284                     mbbi->insert(mi, NewMI);           // Insert the new inst
 285                     mbbi->erase(mi);                   // Nuke the old inst.
 286                     mi = NewMI;
 287                   }
 288
 289                   ++NumCommuted;
 290                   regB = regC;
 291                   goto InstructionRearranged;
 292                 }
 293               }
 294             }
 295
 296             // If this instruction is potentially convertible to a true
 297             // three-address instruction,
 298             if (TID.isConvertibleTo3Addr()) {
 299               // FIXME: This assumes there are no more operands which are tied
 300               // to another register.
 301 #ifndef NDEBUG
 302               for (unsigned i = si + 1, e = TID.getNumOperands(); i < e; ++i)
 303                 assert(TID.getOperandConstraint(i, TOI::TIED_TO) == -1);
 304 #endif
 305
 306               if (MachineInstr *New=TII->convertToThreeAddress(mbbi, mi, *LV)) {
 307                 DOUT << "2addr: CONVERTING 2-ADDR: " << *mi;
 308                 DOUT << "2addr:         TO 3-ADDR: " << *New;
 309                 bool Sunk = false;
 310
 311                 if (New->findRegisterUseOperand(regB, false, TRI))
 312                   // FIXME: Temporary workaround. If the new instruction doesn't
 313                   // uses regB, convertToThreeAddress must have created more
 314                   // then one instruction.
 315                   Sunk = Sink3AddrInstruction(mbbi, New, regB, mi);
 316
 317                 mbbi->erase(mi); // Nuke the old inst.
 318
 319                 if (!Sunk) {
 320                   mi = New;
 321                   nmi = next(mi);
 322                 }
 323
 324                 ++NumConvertedTo3Addr;
 325                 break; // Done with this instruction.
 326               }
 327             }
 328           }
 329
 330         InstructionRearranged:
 331           const TargetRegisterClass* rc = MF.getRegInfo().getRegClass(regA);
 332           MachineInstr *Orig = MRI->getVRegDef(regB);
 333
 334           if (EnableReMat && Orig && TII->isTriviallyReMaterializable(Orig)) {
 335             TII->reMaterialize(*mbbi, mi, regA, Orig);
 336             ReMattedInstrs.insert(Orig);
 337           } else {
 338             TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc);
 339           }
 340
 341           MachineBasicBlock::iterator prevMi = prior(mi);
 342           DOUT << "\t\tprepend:\t"; DEBUG(prevMi->print(*cerr.stream(), &TM));
 343
 344           // Update live variables for regB.
 345           LiveVariables::VarInfo& varInfoB = LV->getVarInfo(regB);
 346
 347           // regB is used in this BB.
 348           varInfoB.UsedBlocks[mbbi->getNumber()] = true;
 349
 350           if (LV->removeVirtualRegisterKilled(regB, mbbi, mi))
 351             LV->addVirtualRegisterKilled(regB, prevMi);
 352
 353           if (LV->removeVirtualRegisterDead(regB, mbbi, mi))
 354             LV->addVirtualRegisterDead(regB, prevMi);
 355
 356           // Replace all occurences of regB with regA.
 357           for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) {
 358             if (mi->getOperand(i).isRegister() &&
 359                 mi->getOperand(i).getReg() == regB)
 360               mi->getOperand(i).setReg(regA);
 361           }
 362         }
 363
 364         assert(mi->getOperand(ti).isDef() && mi->getOperand(si).isUse());
 365         mi->getOperand(ti).setReg(mi->getOperand(si).getReg());
 366         MadeChange = true;
 367
 368         DOUT << "\t\trewrite to:\t"; DEBUG(mi->print(*cerr.stream(), &TM));
 369       }
 370
 371       mi = nmi;
 372     }
 373   }
 374
 375   if (EnableReMat) {
 376     SmallPtrSet<MachineInstr*, 8>::iterator I = ReMattedInstrs.begin();
 377     SmallPtrSet<MachineInstr*, 8>::iterator E = ReMattedInstrs.end();
 378
 379     for (; I != E; ++I) {
 380       MachineInstr *MI = *I;
 381       bool InstrDead = true;
 382
 383       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 384         const MachineOperand &MO = MI->getOperand(i);
 385         if (!MO.isRegister())
 386           continue;
 387         unsigned MOReg = MO.getReg();
 388         if (!MOReg)
 389           continue;
 390         if (MO.isDef()) {
 391           if (MO.isImplicit())
 392             continue;
 393
 394           if (MRI->use_begin(MOReg) != MRI->use_end()) {
 395             InstrDead = false;
 396             break;
 397           }
 398         }
 399       }
 400
 401       if (InstrDead && MI->getNumOperands() > 0)
 402         MI->eraseFromParent();
 403     }
 404   }
 405
 406   return MadeChange;
 407 }