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