TwoAddressInstructionPass.cpp revision eea81bafd624c36d396a08bea87bafd996e6bf43 
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"
38using namespace llvm;
39
40namespace {
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
58const PassInfo *llvm::TwoAddressInstructionPassID = X.getPassInfo();
59
60void 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///
72bool 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}
169