TwoAddressInstructionPass.cpp revision fdb99838a30eba6ee4e7ae8c8077b4f8d62cf560 
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/BitVector.h"
43#include "llvm/ADT/DenseMap.h"
44#include "llvm/ADT/SmallPtrSet.h"
45#include "llvm/ADT/Statistic.h"
46#include "llvm/ADT/STLExtras.h"
47using namespace llvm;
48
49STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions");
50STATISTIC(NumCommuted        , "Number of instructions commuted to coalesce");
51STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address");
52STATISTIC(Num3AddrSunk,        "Number of 3-address instructions sunk");
53STATISTIC(NumReMats,           "Number of instructions re-materialized");
54
55namespace {
56  class VISIBILITY_HIDDEN TwoAddressInstructionPass
57    : public MachineFunctionPass {
58    const TargetInstrInfo *TII;
59    const TargetRegisterInfo *TRI;
60    MachineRegisterInfo *MRI;
61    LiveVariables *LV;
62
63    bool Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI,
64                              unsigned Reg,
65                              MachineBasicBlock::iterator OldPos);
66
67    bool isSafeToReMat(unsigned DstReg, MachineInstr *MI);
68    bool isProfitableToReMat(unsigned Reg, const TargetRegisterClass *RC,
69                             MachineInstr *MI, MachineInstr *DefMI,
70                             MachineBasicBlock *MBB, unsigned Loc,
71                             DenseMap<MachineInstr*, unsigned> &DistanceMap);
72  public:
73    static char ID; // Pass identification, replacement for typeid
74    TwoAddressInstructionPass() : MachineFunctionPass((intptr_t)&ID) {}
75
76    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
77      AU.addRequired<LiveVariables>();
78      AU.addPreserved<LiveVariables>();
79      AU.addPreservedID(MachineLoopInfoID);
80      AU.addPreservedID(MachineDominatorsID);
81      AU.addPreservedID(PHIEliminationID);
82      MachineFunctionPass::getAnalysisUsage(AU);
83    }
84
85    /// runOnMachineFunction - Pass entry point.
86    bool runOnMachineFunction(MachineFunction&);
87  };
88}
89
90char TwoAddressInstructionPass::ID = 0;
91static RegisterPass<TwoAddressInstructionPass>
92X("twoaddressinstruction", "Two-Address instruction pass");
93
94const PassInfo *const llvm::TwoAddressInstructionPassID = &X;
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 reduce
99/// 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
111  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
112    const MachineOperand &MO = MI->getOperand(i);
113    if (!MO.isRegister())
114      continue;
115    unsigned MOReg = MO.getReg();
116    if (!MOReg)
117      continue;
118    if (MO.isUse() && MOReg != SavedReg)
119      UseRegs.insert(MO.getReg());
120    if (!MO.isDef())
121      continue;
122    if (MO.isImplicit())
123      // Don't try to move it if it implicitly defines a register.
124      return false;
125    if (DefReg)
126      // For now, don't move any instructions that define multiple registers.
127      return false;
128    DefReg = MO.getReg();
129  }
130
131  // Find the instruction that kills SavedReg.
132  MachineInstr *KillMI = NULL;
133  for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(SavedReg),
134         UE = MRI->use_end(); UI != UE; ++UI) {
135    MachineOperand &UseMO = UI.getOperand();
136    if (!UseMO.isKill())
137      continue;
138    KillMI = UseMO.getParent();
139    break;
140  }
141
142  if (!KillMI || KillMI->getParent() != MBB)
143    return false;
144
145  // If any of the definitions are used by another instruction between the
146  // position and the kill use, then it's not safe to sink it.
147  //
148  // FIXME: This can be sped up if there is an easy way to query whether an
149  // instruction is before or after another instruction. Then we can use
150  // MachineRegisterInfo def / use instead.
151  MachineOperand *KillMO = NULL;
152  MachineBasicBlock::iterator KillPos = KillMI;
153  ++KillPos;
154
155  unsigned NumVisited = 0;
156  for (MachineBasicBlock::iterator I = next(OldPos); I != KillPos; ++I) {
157    MachineInstr *OtherMI = I;
158    if (NumVisited > 30)  // FIXME: Arbitrary limit to reduce compile time cost.
159      return false;
160    ++NumVisited;
161    for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) {
162      MachineOperand &MO = OtherMI->getOperand(i);
163      if (!MO.isRegister())
164        continue;
165      unsigned MOReg = MO.getReg();
166      if (!MOReg)
167        continue;
168      if (DefReg == MOReg)
169        return false;
170
171      if (MO.isKill()) {
172        if (OtherMI == KillMI && MOReg == SavedReg)
173          // Save the operand that kills the register. We want to unset the kill
174          // marker if we can sink MI past it.
175          KillMO = &MO;
176        else if (UseRegs.count(MOReg))
177          // One of the uses is killed before the destination.
178          return false;
179      }
180    }
181  }
182
183  // Update kill and LV information.
184  KillMO->setIsKill(false);
185  KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI);
186  KillMO->setIsKill(true);
187  LiveVariables::VarInfo& VarInfo = LV->getVarInfo(SavedReg);
188  VarInfo.removeKill(KillMI);
189  VarInfo.Kills.push_back(MI);
190
191  // Move instruction to its destination.
192  MBB->remove(MI);
193  MBB->insert(KillPos, MI);
194
195  ++Num3AddrSunk;
196  return true;
197}
198
199/// isSafeToReMat - Return true if it's safe to rematerialize the specified
200/// instruction which defined the specified register instead of copying it.
201bool
202TwoAddressInstructionPass::isSafeToReMat(unsigned DstReg, MachineInstr *MI) {
203  const TargetInstrDesc &TID = MI->getDesc();
204  if (!TID.isAsCheapAsAMove())
205    return false;
206  bool SawStore = false;
207  if (!MI->isSafeToMove(TII, SawStore))
208    return false;
209  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
210    MachineOperand &MO = MI->getOperand(i);
211    if (!MO.isRegister())
212      continue;
213    // FIXME: For now, do not remat any instruction with register operands.
214    // Later on, we can loosen the restriction is the register operands have
215    // not been modified between the def and use. Note, this is different from
216    // MachineSink because the code in no longer in two-address form (at least
217    // partially).
218    if (MO.isUse())
219      return false;
220    else if (!MO.isDead() && MO.getReg() != DstReg)
221      return false;
222  }
223  return true;
224}
225
226/// isTwoAddrUse - Return true if the specified MI is using the specified
227/// register as a two-address operand.
228static bool isTwoAddrUse(MachineInstr *UseMI, unsigned Reg) {
229  const TargetInstrDesc &TID = UseMI->getDesc();
230  for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) {
231    MachineOperand &MO = UseMI->getOperand(i);
232    if (MO.isRegister() && MO.getReg() == Reg &&
233        (MO.isDef() || TID.getOperandConstraint(i, TOI::TIED_TO) != -1))
234      // Earlier use is a two-address one.
235      return true;
236  }
237  return false;
238}
239
240/// isProfitableToReMat - Return true if the heuristics determines it is likely
241/// to be profitable to re-materialize the definition of Reg rather than copy
242/// the register.
243bool
244TwoAddressInstructionPass::isProfitableToReMat(unsigned Reg,
245                                const TargetRegisterClass *RC,
246                                MachineInstr *MI, MachineInstr *DefMI,
247                                MachineBasicBlock *MBB, unsigned Loc,
248                                DenseMap<MachineInstr*, unsigned> &DistanceMap){
249  bool OtherUse = false;
250  for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
251         UE = MRI->use_end(); UI != UE; ++UI) {
252    MachineOperand &UseMO = UI.getOperand();
253    if (!UseMO.isUse())
254      continue;
255    MachineInstr *UseMI = UseMO.getParent();
256    MachineBasicBlock *UseMBB = UseMI->getParent();
257    if (UseMBB == MBB) {
258      DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI);
259      if (DI != DistanceMap.end() && DI->second == Loc)
260        continue;  // Current use.
261      OtherUse = true;
262      // There is at least one other use in the MBB that will clobber the
263      // register.
264      if (isTwoAddrUse(UseMI, Reg))
265        return true;
266    }
267  }
268
269  // If other uses in MBB are not two-address uses, then don't remat.
270  if (OtherUse)
271    return false;
272
273  // No other uses in the same block, remat if it's defined in the same
274  // block so it does not unnecessarily extend the live range.
275  return MBB == DefMI->getParent();
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 (DefMI &&
432              isSafeToReMat(regB, DefMI) &&
433              isProfitableToReMat(regB, rc, mi, DefMI, mbbi, Dist,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  // Some remat'ed instructions are dead.
477  int VReg = ReMatRegs.find_first();
478  while (VReg != -1) {
479    if (MRI->use_empty(VReg)) {
480      MachineInstr *DefMI = MRI->getVRegDef(VReg);
481      DefMI->eraseFromParent();
482    }
483    VReg = ReMatRegs.find_next(VReg);
484  }
485
486  return MadeChange;
487}
488