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