TwoAddressInstructionPass.cpp revision 32a3ac79116ce93471cd18ede24452c6af5b290b 
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/BitVector.h"
44#include "llvm/ADT/DenseMap.h"
45#include "llvm/ADT/SmallPtrSet.h"
46#include "llvm/ADT/Statistic.h"
47#include "llvm/ADT/STLExtras.h"
48using namespace llvm;
49
50STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions");
51STATISTIC(NumCommuted        , "Number of instructions commuted to coalesce");
52STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address");
53STATISTIC(Num3AddrSunk,        "Number of 3-address instructions sunk");
54STATISTIC(NumReMats,           "Number of instructions re-materialized");
55
56static cl::opt<bool>
57EnableReMat("two-addr-remat", cl::init(false), cl::Hidden,
58            cl::desc("Two-addr conversion should remat when possible."));
59
60namespace {
61  class VISIBILITY_HIDDEN TwoAddressInstructionPass
62    : public MachineFunctionPass {
63    const TargetInstrInfo *TII;
64    const TargetRegisterInfo *TRI;
65    MachineRegisterInfo *MRI;
66    LiveVariables *LV;
67
68    bool Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI,
69                              unsigned Reg,
70                              MachineBasicBlock::iterator OldPos);
71
72    bool isSafeToReMat(unsigned DstReg, MachineInstr *MI);
73    bool isProfitableToReMat(unsigned Reg, const TargetRegisterClass *RC,
74                             MachineInstr *MI, unsigned Loc,
75                             MachineInstr *DefMI, MachineBasicBlock *MBB,
76                             DenseMap<MachineInstr*, unsigned> &DistanceMap);
77  public:
78    static char ID; // Pass identification, replacement for typeid
79    TwoAddressInstructionPass() : MachineFunctionPass((intptr_t)&ID) {}
80
81    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
82      AU.addRequired<LiveVariables>();
83      AU.addPreserved<LiveVariables>();
84      AU.addPreservedID(MachineLoopInfoID);
85      AU.addPreservedID(MachineDominatorsID);
86      AU.addPreservedID(PHIEliminationID);
87      MachineFunctionPass::getAnalysisUsage(AU);
88    }
89
90    /// runOnMachineFunction - Pass entry point.
91    bool runOnMachineFunction(MachineFunction&);
92  };
93}
94
95char TwoAddressInstructionPass::ID = 0;
96static RegisterPass<TwoAddressInstructionPass>
97X("twoaddressinstruction", "Two-Address instruction pass");
98
99const PassInfo *const llvm::TwoAddressInstructionPassID = &X;
100
101/// Sink3AddrInstruction - A two-address instruction has been converted to a
102/// three-address instruction to avoid clobbering a register. Try to sink it
103/// past the instruction that would kill the above mentioned register to reduce
104/// register pressure.
105bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB,
106                                           MachineInstr *MI, unsigned SavedReg,
107                                           MachineBasicBlock::iterator OldPos) {
108  // Check if it's safe to move this instruction.
109  bool SeenStore = true; // Be conservative.
110  if (!MI->isSafeToMove(TII, SeenStore))
111    return false;
112
113  unsigned DefReg = 0;
114  SmallSet<unsigned, 4> UseRegs;
115
116  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
117    const MachineOperand &MO = MI->getOperand(i);
118    if (!MO.isRegister())
119      continue;
120    unsigned MOReg = MO.getReg();
121    if (!MOReg)
122      continue;
123    if (MO.isUse() && MOReg != SavedReg)
124      UseRegs.insert(MO.getReg());
125    if (!MO.isDef())
126      continue;
127    if (MO.isImplicit())
128      // Don't try to move it if it implicitly defines a register.
129      return false;
130    if (DefReg)
131      // For now, don't move any instructions that define multiple registers.
132      return false;
133    DefReg = MO.getReg();
134  }
135
136  // Find the instruction that kills SavedReg.
137  MachineInstr *KillMI = NULL;
138  for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(SavedReg),
139         UE = MRI->use_end(); UI != UE; ++UI) {
140    MachineOperand &UseMO = UI.getOperand();
141    if (!UseMO.isKill())
142      continue;
143    KillMI = UseMO.getParent();
144    break;
145  }
146
147  if (!KillMI || KillMI->getParent() != MBB)
148    return false;
149
150  // If any of the definitions are used by another instruction between the
151  // position and the kill use, then it's not safe to sink it.
152  //
153  // FIXME: This can be sped up if there is an easy way to query whether an
154  // instruction is before or after another instruction. Then we can use
155  // MachineRegisterInfo def / use instead.
156  MachineOperand *KillMO = NULL;
157  MachineBasicBlock::iterator KillPos = KillMI;
158  ++KillPos;
159
160  unsigned NumVisited = 0;
161  for (MachineBasicBlock::iterator I = next(OldPos); I != KillPos; ++I) {
162    MachineInstr *OtherMI = I;
163    if (NumVisited > 30)  // FIXME: Arbitrary limit to reduce compile time cost.
164      return false;
165    ++NumVisited;
166    for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) {
167      MachineOperand &MO = OtherMI->getOperand(i);
168      if (!MO.isRegister())
169        continue;
170      unsigned MOReg = MO.getReg();
171      if (!MOReg)
172        continue;
173      if (DefReg == MOReg)
174        return false;
175
176      if (MO.isKill()) {
177        if (OtherMI == KillMI && MOReg == SavedReg)
178          // Save the operand that kills the register. We want to unset the kill
179          // marker if we can sink MI past it.
180          KillMO = &MO;
181        else if (UseRegs.count(MOReg))
182          // One of the uses is killed before the destination.
183          return false;
184      }
185    }
186  }
187
188  // Update kill and LV information.
189  KillMO->setIsKill(false);
190  KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI);
191  KillMO->setIsKill(true);
192  LiveVariables::VarInfo& VarInfo = LV->getVarInfo(SavedReg);
193  VarInfo.removeKill(KillMI);
194  VarInfo.Kills.push_back(MI);
195
196  // Move instruction to its destination.
197  MBB->remove(MI);
198  MBB->insert(KillPos, MI);
199
200  ++Num3AddrSunk;
201  return true;
202}
203
204/// isSafeToReMat - Return true if it's safe to rematerialize the specified
205/// instruction which defined the specified register instead of copying it.
206bool
207TwoAddressInstructionPass::isSafeToReMat(unsigned DstReg, MachineInstr *MI) {
208  const TargetInstrDesc &TID = MI->getDesc();
209  if (!TID.isAsCheapAsAMove())
210    return false;
211  bool SawStore = false;
212  if (!MI->isSafeToMove(TII, SawStore))
213    return false;
214  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
215    MachineOperand &MO = MI->getOperand(i);
216    if (!MO.isRegister())
217      continue;
218    // FIXME: For now, do not remat any instruction with register operands.
219    // Later on, we can loosen the restriction is the register operands have
220    // not been modified between the def and use. Note, this is different from
221    // MachineSink because the code in no longer in two-address form (at least
222    // partially).
223    if (MO.isUse())
224      return false;
225    else if (!MO.isDead() && MO.getReg() != DstReg)
226      return false;
227  }
228  return true;
229}
230
231/// isTwoAddrUse - Return true if the specified MI is using the specified
232/// register as a two-address operand.
233static bool isTwoAddrUse(MachineInstr *UseMI, unsigned Reg) {
234  const TargetInstrDesc &TID = UseMI->getDesc();
235  for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) {
236    MachineOperand &MO = UseMI->getOperand(i);
237    if (MO.isRegister() && MO.getReg() == Reg &&
238        (MO.isDef() || TID.getOperandConstraint(i, TOI::TIED_TO) != -1))
239      // Earlier use is a two-address one.
240      return true;
241  }
242  return false;
243}
244
245/// isProfitableToReMat - Return true if the heuristics determines it is likely
246/// to be profitable to re-materialize the definition of Reg rather than copy
247/// the register.
248bool
249TwoAddressInstructionPass::isProfitableToReMat(unsigned Reg,
250                                const TargetRegisterClass *RC,
251                                MachineInstr *MI, unsigned Loc,
252                                MachineInstr *DefMI, MachineBasicBlock *MBB,
253                                DenseMap<MachineInstr*, unsigned> &DistanceMap) {
254  if (DefMI->getParent() != MBB)
255    return true;
256  // If earlier uses in MBB are not two-address uses, then don't remat.
257  bool OtherUse = false;
258  for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
259         UE = MRI->use_end(); UI != UE; ++UI) {
260    MachineOperand &UseMO = UI.getOperand();
261    if (!UseMO.isUse())
262      continue;
263    MachineInstr *UseMI = UseMO.getParent();
264    if (UseMI->getParent() != MBB)
265      continue;
266    DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI);
267    if (DI != DistanceMap.end() && DI->second == Loc)
268      continue;  // Current use.
269    OtherUse = true;
270    // There is at least one other use in the MBB that will clobber the
271    // register.
272    if (isTwoAddrUse(UseMI, Reg))
273      return true;
274  }
275  return !OtherUse;
276}
277
278/// runOnMachineFunction - Reduce two-address instructions to two operands.
279///
280bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
281  DOUT << "Machine Function\n";
282  const TargetMachine &TM = MF.getTarget();
283  MRI = &MF.getRegInfo();
284  TII = TM.getInstrInfo();
285  TRI = TM.getRegisterInfo();
286  LV = &getAnalysis<LiveVariables>();
287
288  bool MadeChange = false;
289
290  DOUT << "********** REWRITING TWO-ADDR INSTRS **********\n";
291  DOUT << "********** Function: " << MF.getFunction()->getName() << '\n';
292
293  // ReMatRegs - Keep track of the registers whose def's are remat'ed.
294  BitVector ReMatRegs;
295  ReMatRegs.resize(MRI->getLastVirtReg()+1);
296
297  // DistanceMap - Keep track the distance of a MI from the start of the
298  // current basic block.
299  DenseMap<MachineInstr*, unsigned> DistanceMap;
300
301  for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end();
302       mbbi != mbbe; ++mbbi) {
303    unsigned Dist = 0;
304    DistanceMap.clear();
305    for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end();
306         mi != me; ) {
307      MachineBasicBlock::iterator nmi = next(mi);
308      const TargetInstrDesc &TID = mi->getDesc();
309      bool FirstTied = true;
310
311      DistanceMap.insert(std::make_pair(mi, ++Dist));
312      for (unsigned si = 1, e = TID.getNumOperands(); si < e; ++si) {
313        int ti = TID.getOperandConstraint(si, TOI::TIED_TO);
314        if (ti == -1)
315          continue;
316
317        if (FirstTied) {
318          ++NumTwoAddressInstrs;
319          DOUT << '\t'; DEBUG(mi->print(*cerr.stream(), &TM));
320        }
321
322        FirstTied = false;
323
324        assert(mi->getOperand(si).isRegister() && mi->getOperand(si).getReg() &&
325               mi->getOperand(si).isUse() && "two address instruction invalid");
326
327        // If the two operands are the same we just remove the use
328        // and mark the def as def&use, otherwise we have to insert a copy.
329        if (mi->getOperand(ti).getReg() != mi->getOperand(si).getReg()) {
330          // Rewrite:
331          //     a = b op c
332          // to:
333          //     a = b
334          //     a = a op c
335          unsigned regA = mi->getOperand(ti).getReg();
336          unsigned regB = mi->getOperand(si).getReg();
337
338          assert(TargetRegisterInfo::isVirtualRegister(regA) &&
339                 TargetRegisterInfo::isVirtualRegister(regB) &&
340                 "cannot update physical register live information");
341
342#ifndef NDEBUG
343          // First, verify that we don't have a use of a in the instruction (a =
344          // b + a for example) because our transformation will not work. This
345          // should never occur because we are in SSA form.
346          for (unsigned i = 0; i != mi->getNumOperands(); ++i)
347            assert((int)i == ti ||
348                   !mi->getOperand(i).isRegister() ||
349                   mi->getOperand(i).getReg() != regA);
350#endif
351
352          // If this instruction is not the killing user of B, see if we can
353          // rearrange the code to make it so.  Making it the killing user will
354          // allow us to coalesce A and B together, eliminating the copy we are
355          // about to insert.
356          if (!mi->killsRegister(regB)) {
357            // If this instruction is commutative, check to see if C dies.  If
358            // so, swap the B and C operands.  This makes the live ranges of A
359            // and C joinable.
360            // FIXME: This code also works for A := B op C instructions.
361            if (TID.isCommutable() && mi->getNumOperands() >= 3) {
362              assert(mi->getOperand(3-si).isRegister() &&
363                     "Not a proper commutative instruction!");
364              unsigned regC = mi->getOperand(3-si).getReg();
365
366              if (mi->killsRegister(regC)) {
367                DOUT << "2addr: COMMUTING  : " << *mi;
368                MachineInstr *NewMI = TII->commuteInstruction(mi);
369
370                if (NewMI == 0) {
371                  DOUT << "2addr: COMMUTING FAILED!\n";
372                } else {
373                  DOUT << "2addr: COMMUTED TO: " << *NewMI;
374                  // If the instruction changed to commute it, update livevar.
375                  if (NewMI != mi) {
376                    LV->instructionChanged(mi, NewMI); // Update live variables
377                    mbbi->insert(mi, NewMI);           // Insert the new inst
378                    mbbi->erase(mi);                   // Nuke the old inst.
379                    mi = NewMI;
380                    DistanceMap.insert(std::make_pair(NewMI, Dist));
381                  }
382
383                  ++NumCommuted;
384                  regB = regC;
385                  goto InstructionRearranged;
386                }
387              }
388            }
389
390            // If this instruction is potentially convertible to a true
391            // three-address instruction,
392            if (TID.isConvertibleTo3Addr()) {
393              // FIXME: This assumes there are no more operands which are tied
394              // to another register.
395#ifndef NDEBUG
396              for (unsigned i = si + 1, e = TID.getNumOperands(); i < e; ++i)
397                assert(TID.getOperandConstraint(i, TOI::TIED_TO) == -1);
398#endif
399
400              MachineInstr *NewMI = TII->convertToThreeAddress(mbbi, mi, *LV);
401              if (NewMI) {
402                DOUT << "2addr: CONVERTING 2-ADDR: " << *mi;
403                DOUT << "2addr:         TO 3-ADDR: " << *NewMI;
404                bool Sunk = false;
405
406                if (NewMI->findRegisterUseOperand(regB, false, TRI))
407                  // FIXME: Temporary workaround. If the new instruction doesn't
408                  // uses regB, convertToThreeAddress must have created more
409                  // then one instruction.
410                  Sunk = Sink3AddrInstruction(mbbi, NewMI, regB, mi);
411
412                mbbi->erase(mi); // Nuke the old inst.
413
414                if (!Sunk) {
415                  DistanceMap.insert(std::make_pair(NewMI, Dist));
416                  mi = NewMI;
417                  nmi = next(mi);
418                }
419
420                ++NumConvertedTo3Addr;
421                break; // Done with this instruction.
422              }
423            }
424          }
425
426        InstructionRearranged:
427          const TargetRegisterClass* rc = MRI->getRegClass(regA);
428          MachineInstr *DefMI = MRI->getVRegDef(regB);
429          // If it's safe and profitable, remat the definition instead of
430          // copying it.
431          if (EnableReMat && DefMI &&
432              isSafeToReMat(regB, DefMI) &&
433              isProfitableToReMat(regB, rc, mi, Dist, DefMI, mbbi,DistanceMap)){
434            DEBUG(cerr << "2addr: REMATTING : " << *DefMI << "\n");
435            TII->reMaterialize(*mbbi, mi, regA, DefMI);
436            ReMatRegs.set(regB);
437            ++NumReMats;
438          } else {
439            TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc);
440          }
441
442          MachineBasicBlock::iterator prevMi = prior(mi);
443          DOUT << "\t\tprepend:\t"; DEBUG(prevMi->print(*cerr.stream(), &TM));
444
445          // Update live variables for regB.
446          LiveVariables::VarInfo& varInfoB = LV->getVarInfo(regB);
447
448          // regB is used in this BB.
449          varInfoB.UsedBlocks[mbbi->getNumber()] = true;
450
451          if (LV->removeVirtualRegisterKilled(regB, mbbi, mi))
452            LV->addVirtualRegisterKilled(regB, prevMi);
453
454          if (LV->removeVirtualRegisterDead(regB, mbbi, mi))
455            LV->addVirtualRegisterDead(regB, prevMi);
456
457          // Replace all occurences of regB with regA.
458          for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) {
459            if (mi->getOperand(i).isRegister() &&
460                mi->getOperand(i).getReg() == regB)
461              mi->getOperand(i).setReg(regA);
462          }
463        }
464
465        assert(mi->getOperand(ti).isDef() && mi->getOperand(si).isUse());
466        mi->getOperand(ti).setReg(mi->getOperand(si).getReg());
467        MadeChange = true;
468
469        DOUT << "\t\trewrite to:\t"; DEBUG(mi->print(*cerr.stream(), &TM));
470      }
471
472      mi = nmi;
473    }
474  }
475
476  if (EnableReMat) {
477    // Some remat'ed instructions are dead.
478    int VReg = ReMatRegs.find_first();
479    while (VReg != -1) {
480      if (MRI->use_empty(VReg)) {
481        MachineInstr *DefMI = MRI->getVRegDef(VReg);
482        DefMI->eraseFromParent();
483      }
484      VReg = ReMatRegs.find_next(VReg);
485    }
486
487  }
488
489  return MadeChange;
490}
491