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 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/Function.h"
  32 #include "llvm/CodeGen/Passes.h"
  33 #include "llvm/CodeGen/LiveVariables.h"
  34 #include "llvm/CodeGen/MachineFunctionPass.h"
  35 #include "llvm/CodeGen/MachineInstr.h"
  36 #include "llvm/CodeGen/SSARegMap.h"
  37 #include "llvm/Target/MRegisterInfo.h"
  38 #include "llvm/Target/TargetInstrInfo.h"
  39 #include "llvm/Target/TargetMachine.h"
  40 #include "Support/Debug.h"
  41 #include "Support/Statistic.h"
  42 #include "Support/STLExtras.h"
  43 #include <iostream>
  44 using namespace llvm;
  45
  46 namespace {
  47     Statistic<> numTwoAddressInstrs("twoaddressinstruction",
  48                                     "Number of two-address instructions");
  49     Statistic<> numInstrsAdded("twoaddressinstruction",
  50                                "Number of instructions added");
  51
  52     struct TwoAddressInstructionPass : public MachineFunctionPass
  53     {
  54         virtual void getAnalysisUsage(AnalysisUsage &AU) const;
  55
  56         /// runOnMachineFunction - pass entry point
  57         bool runOnMachineFunction(MachineFunction&);
  58     };
  59
  60     RegisterPass<TwoAddressInstructionPass> X(
  61         "twoaddressinstruction", "Two-Address instruction pass");
  62 };
  63
  64 const PassInfo *llvm::TwoAddressInstructionPassID = X.getPassInfo();
  65
  66 void TwoAddressInstructionPass::getAnalysisUsage(AnalysisUsage &AU) const
  67 {
  68     AU.addPreserved<LiveVariables>();
  69     AU.addPreservedID(PHIEliminationID);
  70     MachineFunctionPass::getAnalysisUsage(AU);
  71 }
  72
  73 /// runOnMachineFunction - Reduce two-address instructions to two
  74 /// operands.
  75 ///
  76 bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
  77     DEBUG(std::cerr << "Machine Function\n");
  78     const TargetMachine &TM = MF.getTarget();
  79     const MRegisterInfo &MRI = *TM.getRegisterInfo();
  80     const TargetInstrInfo &TII = TM.getInstrInfo();
  81     LiveVariables* LV = getAnalysisToUpdate<LiveVariables>();
  82
  83     bool MadeChange = false;
  84
  85     DEBUG(std::cerr << "********** REWRITING TWO-ADDR INSTRS **********\n");
  86     DEBUG(std::cerr << "********** Function: "
  87           << MF.getFunction()->getName() << '\n');
  88
  89     for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end();
  90          mbbi != mbbe; ++mbbi) {
  91         for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end();
  92              mi != me; ++mi) {
  93             unsigned opcode = mi->getOpcode();
  94
  95             // ignore if it is not a two-address instruction
  96             if (!TII.isTwoAddrInstr(opcode))
  97                 continue;
  98
  99             ++numTwoAddressInstrs;
 100
 101             DEBUG(std::cerr << '\t'; mi->print(std::cerr, TM));
 102
 103             assert(mi->getOperand(1).isRegister() &&
 104                    mi->getOperand(1).getReg() &&
 105                    mi->getOperand(1).isUse() &&
 106                    "two address instruction invalid");
 107
 108             // if the two operands are the same we just remove the use
 109             // and mark the def as def&use
 110             if (mi->getOperand(0).getReg() ==
 111                 mi->getOperand(1).getReg()) {
 112             }
 113             else {
 114                 MadeChange = true;
 115
 116                 // rewrite:
 117                 //     a = b op c
 118                 // to:
 119                 //     a = b
 120                 //     a = a op c
 121                 unsigned regA = mi->getOperand(0).getReg();
 122                 unsigned regB = mi->getOperand(1).getReg();
 123
 124                 assert(MRegisterInfo::isVirtualRegister(regA) &&
 125                        MRegisterInfo::isVirtualRegister(regB) &&
 126                        "cannot update physical register live information");
 127
 128                 // first make sure we do not have a use of a in the
 129                 // instruction (a = b + a for example) because our
 130                 // transformation will not work. This should never occur
 131                 // because we are in SSA form.
 132                 for (unsigned i = 1; i != mi->getNumOperands(); ++i)
 133                     assert(!mi->getOperand(i).isRegister() ||
 134                            mi->getOperand(i).getReg() != regA);
 135
 136                 const TargetRegisterClass* rc =
 137                     MF.getSSARegMap()->getRegClass(regA);
 138                 unsigned Added = MRI.copyRegToReg(*mbbi, mi, regA, regB, rc);
 139                 numInstrsAdded += Added;
 140
 141                 MachineBasicBlock::iterator prevMi = prior(mi);
 142                 DEBUG(std::cerr << "\t\tprepend:\t";
 143                       prevMi->print(std::cerr, TM));
 144
 145                 if (LV) {
 146                     // update live variables for regA
 147                     assert(Added == 1 &&
 148                            "Cannot handle multi-instruction copies yet!");
 149                     LiveVariables::VarInfo& varInfo = LV->getVarInfo(regA);
 150                     varInfo.DefInst = prevMi;
 151
 152                     // update live variables for regB
 153                     if (LV->removeVirtualRegisterKilled(regB, &*mbbi, mi))
 154                         LV->addVirtualRegisterKilled(regB, &*mbbi, prevMi);
 155
 156                     if (LV->removeVirtualRegisterDead(regB, &*mbbi, mi))
 157                         LV->addVirtualRegisterDead(regB, &*mbbi, prevMi);
 158                 }
 159
 160                 // replace all occurences of regB with regA
 161                 for (unsigned i = 1, e = mi->getNumOperands(); i != e; ++i) {
 162                     if (mi->getOperand(i).isRegister() &&
 163                         mi->getOperand(i).getReg() == regB)
 164                         mi->SetMachineOperandReg(i, regA);
 165                 }
 166             }
 167
 168             assert(mi->getOperand(0).isDef());
 169             mi->getOperand(0).setUse();
 170             mi->RemoveOperand(1);
 171
 172             DEBUG(std::cerr << "\t\trewrite to:\t";
 173                   mi->print(std::cerr, TM));
 174         }
 175     }
 176
 177     return MadeChange;
 178 }