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