lib/CodeGen/TwoAddressInstructionPass.cpp

   1 //===-- TwoAddressInstructionPass.cpp - Two-Address instruction pass ------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source 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 = A op C
  20 //
  21 // Note that if a register allocator chooses to use this pass, that it has to
  22 // be capable of handling the non-SSA nature of these rewritten virtual
  23 // registers.
  24 //
  25 //===----------------------------------------------------------------------===//
  26
  27 #define DEBUG_TYPE "twoaddrinstr"
  28 #include "llvm/CodeGen/Passes.h"
  29 #include "llvm/CodeGen/LiveVariables.h"
  30 #include "llvm/CodeGen/MachineFunctionPass.h"
  31 #include "llvm/CodeGen/MachineInstr.h"
  32 #include "llvm/CodeGen/SSARegMap.h"
  33 #include "llvm/Target/MRegisterInfo.h"
  34 #include "llvm/Target/TargetInstrInfo.h"
  35 #include "llvm/Target/TargetMachine.h"
  36 #include "Support/Debug.h"
  37 #include "Support/Statistic.h"
  38 using namespace llvm;
  39
  40 namespace {
  41     Statistic<> numTwoAddressInstrs("twoaddressinstruction",
  42                                     "Number of two-address instructions");
  43     Statistic<> numInstrsAdded("twoaddressinstruction",
  44                                "Number of instructions added");
  45
  46     struct TwoAddressInstructionPass : public MachineFunctionPass
  47     {
  48         virtual void getAnalysisUsage(AnalysisUsage &AU) const;
  49
  50         /// runOnMachineFunction - pass entry point
  51         bool runOnMachineFunction(MachineFunction&);
  52     };
  53
  54     RegisterPass<TwoAddressInstructionPass> X(
  55         "twoaddressinstruction", "Two-Address instruction pass");
  56 };
  57
  58 const PassInfo *llvm::TwoAddressInstructionPassID = X.getPassInfo();
  59
  60 void TwoAddressInstructionPass::getAnalysisUsage(AnalysisUsage &AU) const
  61 {
  62     AU.addPreserved<LiveVariables>();
  63     AU.addRequired<LiveVariables>();
  64     AU.addPreservedID(PHIEliminationID);
  65     AU.addRequiredID(PHIEliminationID);
  66     MachineFunctionPass::getAnalysisUsage(AU);
  67 }
  68
  69 /// runOnMachineFunction - Reduce two-address instructions to two
  70 /// operands.
  71 ///
  72 bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
  73     DEBUG(std::cerr << "Machine Function\n");
  74     const TargetMachine &TM = MF.getTarget();
  75     const MRegisterInfo &MRI = *TM.getRegisterInfo();
  76     const TargetInstrInfo &TII = TM.getInstrInfo();
  77     LiveVariables &LV = getAnalysis<LiveVariables>();
  78
  79     bool MadeChange = false;
  80
  81     for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end();
  82          mbbi != mbbe; ++mbbi) {
  83         for (MachineBasicBlock::iterator mii = mbbi->begin();
  84              mii != mbbi->end(); ++mii) {
  85             MachineInstr* mi = *mii;
  86             unsigned opcode = mi->getOpcode();
  87
  88             // ignore if it is not a two-address instruction
  89             if (!TII.isTwoAddrInstr(opcode))
  90                 continue;
  91
  92             ++numTwoAddressInstrs;
  93
  94             DEBUG(std::cerr << "\tinstruction: "; mi->print(std::cerr, TM));
  95
  96             assert(mi->getOperand(1).isRegister() &&
  97                    mi->getOperand(1).getAllocatedRegNum() &&
  98                    mi->getOperand(1).isUse() &&
  99                    "two address instruction invalid");
 100
 101             // we have nothing to do if the two operands are the same
 102             if (mi->getOperand(0).getAllocatedRegNum() ==
 103                 mi->getOperand(1).getAllocatedRegNum())
 104                 continue;
 105
 106             MadeChange = true;
 107
 108             // rewrite:
 109             //     a = b op c
 110             // to:
 111             //     a = b
 112             //     a = a op c
 113             unsigned regA = mi->getOperand(0).getAllocatedRegNum();
 114             unsigned regB = mi->getOperand(1).getAllocatedRegNum();
 115
 116             assert(MRegisterInfo::isVirtualRegister(regA) &&
 117                    MRegisterInfo::isVirtualRegister(regB) &&
 118                    "cannot update physical register live information");
 119
 120             // first make sure we do not have a use of a in the
 121             // instruction (a = b + a for example) because our
 122             // transformation will not work. This should never occur
 123             // because we are in SSA form.
 124             for (unsigned i = 1; i != mi->getNumOperands(); ++i)
 125                 assert(!mi->getOperand(i).isRegister() ||
 126                        mi->getOperand(i).getAllocatedRegNum() != (int)regA);
 127
 128             const TargetRegisterClass* rc =MF.getSSARegMap()->getRegClass(regA);
 129             unsigned Added = MRI.copyRegToReg(*mbbi, mii, regA, regB, rc);
 130             numInstrsAdded += Added;
 131
 132             MachineInstr* prevMi = *(mii - 1);
 133             DEBUG(std::cerr << "\t\tadded instruction: ";
 134                   prevMi->print(std::cerr, TM));
 135
 136             // update live variables for regA
 137             assert(Added == 1 && "Cannot handle multi-instruction copies yet!");
 138             LiveVariables::VarInfo& varInfo = LV.getVarInfo(regA);
 139             varInfo.DefInst = prevMi;
 140
 141             // update live variables for regB
 142             if (LV.removeVirtualRegisterKilled(regB, &*mbbi, mi))
 143                 LV.addVirtualRegisterKilled(regB, &*mbbi, prevMi);
 144
 145             if (LV.removeVirtualRegisterDead(regB, &*mbbi, mi))
 146                 LV.addVirtualRegisterDead(regB, &*mbbi, prevMi);
 147
 148             // replace all occurences of regB with regA
 149             // and mark all uses and defs of regA as def&use
 150             for (unsigned i = 1; i < mi->getNumOperands(); ++i) {
 151                 MachineOperand& op = mi->getOperand(i);
 152                 if (op.isRegister()) {
 153                     if (op.getReg() == regB)
 154                         mi->SetMachineOperandReg(i, regA);
 155                     if (op.getReg() == regA)
 156                         op.setDef().setUse();
 157                 }
 158             }
 159
 160             DEBUG(std::cerr << "\t\tmodified original to: ";
 161                   mi->print(std::cerr, TM));
 162             assert(mi->getOperand(0).getAllocatedRegNum() ==
 163                    mi->getOperand(1).getAllocatedRegNum());
 164         }
 165     }
 166
 167     return MadeChange;
 168 }