MachineCopyPropagation.cpp revision a8fc171b3f703ad8bda50a22e9227eee0822eeec 
1//===- MachineCopyPropagation.cpp - Machine Copy Propagation 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 is an extremely simple MachineInstr-level copy propagation pass.
11//
12//===----------------------------------------------------------------------===//
13
14#define DEBUG_TYPE "codegen-cp"
15#include "llvm/CodeGen/Passes.h"
16#include "llvm/Pass.h"
17#include "llvm/CodeGen/MachineFunction.h"
18#include "llvm/CodeGen/MachineFunctionPass.h"
19#include "llvm/Target/TargetRegisterInfo.h"
20#include "llvm/Support/Debug.h"
21#include "llvm/Support/ErrorHandling.h"
22#include "llvm/Support/raw_ostream.h"
23#include "llvm/ADT/BitVector.h"
24#include "llvm/ADT/DenseMap.h"
25#include "llvm/ADT/SetVector.h"
26#include "llvm/ADT/SmallVector.h"
27#include "llvm/ADT/Statistic.h"
28using namespace llvm;
29
30STATISTIC(NumDeletes, "Number of dead copies deleted");
31
32namespace {
33  class MachineCopyPropagation : public MachineFunctionPass {
34    const TargetRegisterInfo *TRI;
35    BitVector ReservedRegs;
36
37  public:
38    static char ID; // Pass identification, replacement for typeid
39    MachineCopyPropagation() : MachineFunctionPass(ID) {
40     initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry());
41    }
42
43    virtual bool runOnMachineFunction(MachineFunction &MF);
44
45  private:
46    void SourceNoLongerAvailable(unsigned Reg,
47                               DenseMap<unsigned, unsigned> &SrcMap,
48                               DenseMap<unsigned, MachineInstr*> &AvailCopyMap);
49    bool CopyPropagateBlock(MachineBasicBlock &MBB);
50  };
51}
52char MachineCopyPropagation::ID = 0;
53char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID;
54
55INITIALIZE_PASS(MachineCopyPropagation, "machine-cp",
56                "Machine Copy Propagation Pass", false, false)
57
58void
59MachineCopyPropagation::SourceNoLongerAvailable(unsigned Reg,
60                              DenseMap<unsigned, unsigned> &SrcMap,
61                              DenseMap<unsigned, MachineInstr*> &AvailCopyMap) {
62  DenseMap<unsigned, unsigned>::iterator SI = SrcMap.find(Reg);
63  if (SI != SrcMap.end()) {
64    unsigned MappedDef = SI->second;
65    // Source of copy is no longer available for propagation.
66    if (AvailCopyMap.erase(MappedDef)) {
67      for (const unsigned *SR = TRI->getSubRegisters(MappedDef); *SR; ++SR)
68        AvailCopyMap.erase(*SR);
69    }
70  }
71  for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
72    SI = SrcMap.find(*AS);
73    if (SI != SrcMap.end()) {
74      unsigned MappedDef = SI->second;
75      if (AvailCopyMap.erase(MappedDef)) {
76        for (const unsigned *SR = TRI->getSubRegisters(MappedDef); *SR; ++SR)
77          AvailCopyMap.erase(*SR);
78      }
79    }
80  }
81}
82
83static bool NoInterveningSideEffect(const MachineInstr *CopyMI,
84                                    const MachineInstr *MI) {
85  const MachineBasicBlock *MBB = CopyMI->getParent();
86  if (MI->getParent() != MBB)
87    return false;
88  MachineBasicBlock::const_iterator I = CopyMI;
89  MachineBasicBlock::const_iterator E = MBB->end();
90  MachineBasicBlock::const_iterator E2 = MI;
91
92  ++I;
93  while (I != E && I != E2) {
94    if (I->hasUnmodeledSideEffects() || I->isCall() ||
95        I->isTerminator())
96      return false;
97    ++I;
98  }
99  return true;
100}
101
102bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
103  SmallSetVector<MachineInstr*, 8> MaybeDeadCopies; // Candidates for deletion
104  DenseMap<unsigned, MachineInstr*> AvailCopyMap;   // Def -> available copies map
105  DenseMap<unsigned, MachineInstr*> CopyMap;        // Def -> copies map
106  DenseMap<unsigned, unsigned> SrcMap;              // Src -> Def map
107
108  bool Changed = false;
109  for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) {
110    MachineInstr *MI = &*I;
111    ++I;
112
113    if (MI->isCopy()) {
114      unsigned Def = MI->getOperand(0).getReg();
115      unsigned Src = MI->getOperand(1).getReg();
116
117      if (TargetRegisterInfo::isVirtualRegister(Def) ||
118          TargetRegisterInfo::isVirtualRegister(Src))
119        report_fatal_error("MachineCopyPropagation should be run after"
120                           " register allocation!");
121
122      DenseMap<unsigned, MachineInstr*>::iterator CI = AvailCopyMap.find(Src);
123      if (CI != AvailCopyMap.end()) {
124        MachineInstr *CopyMI = CI->second;
125        unsigned SrcSrc = CopyMI->getOperand(1).getReg();
126        if (!ReservedRegs.test(Def) &&
127            (!ReservedRegs.test(Src) || NoInterveningSideEffect(CopyMI, MI)) &&
128            (SrcSrc == Def || TRI->isSubRegister(SrcSrc, Def))) {
129          // The two copies cancel out and the source of the first copy
130          // hasn't been overridden, eliminate the second one. e.g.
131          //  %ECX<def> = COPY %EAX<kill>
132          //  ... nothing clobbered EAX.
133          //  %EAX<def> = COPY %ECX
134          // =>
135          //  %ECX<def> = COPY %EAX
136          //
137          // Also avoid eliminating a copy from reserved registers unless the
138          // definition is proven not clobbered. e.g.
139          // %RSP<def> = COPY %RAX
140          // CALL
141          // %RAX<def> = COPY %RSP
142
143          // Clear any kills of Def between CopyMI and MI. This extends the
144          // live range.
145          for (MachineBasicBlock::iterator I = CopyMI, E = MI; I != E; ++I)
146            I->clearRegisterKills(Def, TRI);
147
148          MI->eraseFromParent();
149          Changed = true;
150          ++NumDeletes;
151          continue;
152        }
153      }
154
155      // If Src is defined by a previous copy, it cannot be eliminated.
156      CI = CopyMap.find(Src);
157      if (CI != CopyMap.end())
158        MaybeDeadCopies.remove(CI->second);
159      for (const unsigned *AS = TRI->getAliasSet(Src); *AS; ++AS) {
160        CI = CopyMap.find(*AS);
161        if (CI != CopyMap.end())
162          MaybeDeadCopies.remove(CI->second);
163      }
164
165      // Copy is now a candidate for deletion.
166      MaybeDeadCopies.insert(MI);
167
168      // If 'Src' is previously source of another copy, then this earlier copy's
169      // source is no longer available. e.g.
170      // %xmm9<def> = copy %xmm2
171      // ...
172      // %xmm2<def> = copy %xmm0
173      // ...
174      // %xmm2<def> = copy %xmm9
175      SourceNoLongerAvailable(Def, SrcMap, AvailCopyMap);
176
177      // Remember Def is defined by the copy.
178      CopyMap[Def] = MI;
179      AvailCopyMap[Def] = MI;
180      for (const unsigned *SR = TRI->getSubRegisters(Def); *SR; ++SR) {
181        CopyMap[*SR] = MI;
182        AvailCopyMap[*SR] = MI;
183      }
184
185      // Remember source that's copied to Def. Once it's clobbered, then
186      // it's no longer available for copy propagation.
187      SrcMap[Src] = Def;
188
189      continue;
190    }
191
192    // Not a copy.
193    SmallVector<unsigned, 2> Defs;
194    bool HasRegMask = false;
195    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
196      MachineOperand &MO = MI->getOperand(i);
197      if (MO.isRegMask())
198        HasRegMask = true;
199      if (!MO.isReg())
200        continue;
201      unsigned Reg = MO.getReg();
202      if (!Reg)
203        continue;
204
205      if (TargetRegisterInfo::isVirtualRegister(Reg))
206        report_fatal_error("MachineCopyPropagation should be run after"
207                           " register allocation!");
208
209      if (MO.isDef()) {
210        Defs.push_back(Reg);
211        continue;
212      }
213
214      // If 'Reg' is defined by a copy, the copy is no longer a candidate
215      // for elimination.
216      DenseMap<unsigned, MachineInstr*>::iterator CI = CopyMap.find(Reg);
217      if (CI != CopyMap.end())
218        MaybeDeadCopies.remove(CI->second);
219      for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
220        CI = CopyMap.find(*AS);
221        if (CI != CopyMap.end())
222          MaybeDeadCopies.remove(CI->second);
223      }
224    }
225
226    // The instruction has a register mask operand which means that it clobbers
227    // a large set of registers.  It is possible to use the register mask to
228    // prune the available copies, but treat it like a basic block boundary for
229    // now.
230    if (HasRegMask) {
231      // FIXME: We could possibly erase some MaybeDeadCopies if their registers
232      // are clobbered by the mask.
233      MaybeDeadCopies.clear();
234      AvailCopyMap.clear();
235      CopyMap.clear();
236      SrcMap.clear();
237      continue;
238    }
239
240    for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
241      unsigned Reg = Defs[i];
242
243      // No longer defined by a copy.
244      CopyMap.erase(Reg);
245      AvailCopyMap.erase(Reg);
246      for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
247        CopyMap.erase(*AS);
248        AvailCopyMap.erase(*AS);
249      }
250
251      // If 'Reg' is previously source of a copy, it is no longer available for
252      // copy propagation.
253      SourceNoLongerAvailable(Reg, SrcMap, AvailCopyMap);
254    }
255  }
256
257  // If MBB doesn't have successors, delete the copies whose defs are not used.
258  // If MBB does have successors, then conservative assume the defs are live-out
259  // since we don't want to trust live-in lists.
260  if (MBB.succ_empty()) {
261    for (SmallSetVector<MachineInstr*, 8>::iterator
262           DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end();
263         DI != DE; ++DI) {
264      if (!ReservedRegs.test((*DI)->getOperand(0).getReg())) {
265        (*DI)->eraseFromParent();
266        Changed = true;
267        ++NumDeletes;
268      }
269    }
270  }
271
272  return Changed;
273}
274
275bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {
276  bool Changed = false;
277
278  TRI = MF.getTarget().getRegisterInfo();
279  ReservedRegs = TRI->getReservedRegs(MF);
280
281  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
282    Changed |= CopyPropagateBlock(*I);
283
284  return Changed;
285}
286