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