TwoAddressInstructionPass.cpp revision 8c2403631b9c83b6bb80ef61a7f6d5a34975e6a9 
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//===----------------------------------------------------------------------===//
22
23#define DEBUG_TYPE "twoaddrinstr"
24#include "llvm/Function.h"
25#include "llvm/CodeGen/LiveVariables.h"
26#include "llvm/CodeGen/MachineFrameInfo.h"
27#include "llvm/CodeGen/MachineFunctionPass.h"
28#include "llvm/CodeGen/MachineInstr.h"
29#include "llvm/CodeGen/Passes.h"
30#include "llvm/CodeGen/SSARegMap.h"
31#include "llvm/Target/MRegisterInfo.h"
32#include "llvm/Target/TargetInstrInfo.h"
33#include "llvm/Target/TargetMachine.h"
34#include "llvm/Target/TargetRegInfo.h"
35#include "Support/Debug.h"
36#include "Support/Statistic.h"
37#include "Support/STLExtras.h"
38#include <iostream>
39
40using namespace llvm;
41
42namespace {
43    class TwoAddressInstructionPass : public MachineFunctionPass
44    {
45    private:
46        MachineFunction* mf_;
47        const TargetMachine* tm_;
48        const MRegisterInfo* mri_;
49        LiveVariables* lv_;
50
51    public:
52        virtual void getAnalysisUsage(AnalysisUsage &AU) const;
53
54    private:
55        /// runOnMachineFunction - pass entry point
56        bool runOnMachineFunction(MachineFunction&);
57    };
58
59    RegisterPass<TwoAddressInstructionPass> X(
60        "twoaddressinstruction", "Two-Address instruction pass");
61
62    Statistic<> numTwoAddressInstrs("twoaddressinstruction",
63                                    "Number of two-address instructions");
64    Statistic<> numInstrsAdded("twoaddressinstruction",
65                               "Number of instructions added");
66};
67
68const PassInfo *llvm::TwoAddressInstructionPassID = X.getPassInfo();
69
70void TwoAddressInstructionPass::getAnalysisUsage(AnalysisUsage &AU) const
71{
72    AU.addPreserved<LiveVariables>();
73    AU.addRequired<LiveVariables>();
74    AU.addPreservedID(PHIEliminationID);
75    AU.addRequiredID(PHIEliminationID);
76    MachineFunctionPass::getAnalysisUsage(AU);
77}
78
79/// runOnMachineFunction - Reduce two-address instructions to two
80/// operands
81///
82bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &fn) {
83    DEBUG(std::cerr << "Machine Function\n");
84    mf_ = &fn;
85    tm_ = &fn.getTarget();
86    mri_ = tm_->getRegisterInfo();
87    lv_ = &getAnalysis<LiveVariables>();
88
89    const TargetInstrInfo& tii = tm_->getInstrInfo();
90
91    for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
92         mbbi != mbbe; ++mbbi) {
93        for (MachineBasicBlock::iterator mii = mbbi->begin();
94             mii != mbbi->end(); ++mii) {
95            MachineInstr* mi = *mii;
96
97            unsigned opcode = mi->getOpcode();
98            // ignore if it is not a two-address instruction
99            if (!tii.isTwoAddrInstr(opcode))
100                continue;
101
102            ++numTwoAddressInstrs;
103
104            DEBUG(std::cerr << "\tinstruction: "; mi->print(std::cerr, *tm_));
105
106            // we have nothing to do if the two operands are the same
107            if (mi->getOperand(0).getAllocatedRegNum() ==
108                mi->getOperand(1).getAllocatedRegNum())
109                continue;
110
111            assert(mi->getOperand(1).isRegister() &&
112                   mi->getOperand(1).getAllocatedRegNum() &&
113                   mi->getOperand(1).isUse() &&
114                   "two address instruction invalid");
115
116            // rewrite:
117            //     a = b op c
118            // to:
119            //     a = b
120            //     a = a op c
121            unsigned regA = mi->getOperand(0).getAllocatedRegNum();
122            unsigned regB = mi->getOperand(1).getAllocatedRegNum();
123            bool regAisPhysical = regA < MRegisterInfo::FirstVirtualRegister;
124            bool regBisPhysical = regB < MRegisterInfo::FirstVirtualRegister;
125
126            // first make sure we do not have a use of a in the
127            // instruction (a = b + a for example) because our
128            // transofrmation will not work. This should never occur
129            // because of SSA.
130            for (unsigned i = 1; i < mi->getNumOperands(); ++i) {
131                assert(!mi->getOperand(i).isRegister() ||
132                       mi->getOperand(i).getAllocatedRegNum() != (int)regA);
133            }
134
135            const TargetRegisterClass* rc = regAisPhysical ?
136                mri_->getRegClass(regA) :
137                mf_->getSSARegMap()->getRegClass(regA);
138
139            numInstrsAdded += mri_->copyRegToReg(*mbbi, mii, regA, regB, rc);
140
141            MachineInstr* prevMi = *(mii - 1);
142            DEBUG(std::cerr << "\t\tadded instruction: ";
143                  prevMi->print(std::cerr, *tm_));
144
145            // update live variables for regA
146            if (regAisPhysical) {
147                lv_->HandlePhysRegDef(regA, prevMi);
148            }
149            else {
150                LiveVariables::VarInfo& varInfo = lv_->getVarInfo(regA);
151                varInfo.DefInst = prevMi;
152            }
153
154            // update live variables for regB
155            if (regBisPhysical) {
156                lv_->HandlePhysRegUse(regB, prevMi);
157            }
158            else {
159                if (lv_->removeVirtualRegisterKilled(regB, &*mbbi, mi))
160                    lv_->addVirtualRegisterKilled(regB, &*mbbi, prevMi);
161
162                if (lv_->removeVirtualRegisterDead(regB, &*mbbi, mi))
163                    lv_->addVirtualRegisterDead(regB, &*mbbi, prevMi);
164            }
165
166            // replace all occurences of regB with regA
167            for (unsigned i = 1; i < mi->getNumOperands(); ++i) {
168                if (mi->getOperand(i).isRegister() &&
169                    mi->getOperand(i).getReg() == regB)
170                    mi->SetMachineOperandReg(i, regA);
171            }
172            DEBUG(std::cerr << "\t\tmodified original to: ";
173                  mi->print(std::cerr, *tm_));
174            assert(mi->getOperand(0).getAllocatedRegNum() ==
175                   mi->getOperand(1).getAllocatedRegNum());
176        }
177    }
178
179    return numInstrsAdded != 0;
180}
181