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