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