MachineCopyPropagation.cpp revision 1df91b0e54bc62f8fc7a06a4f75220e40aa2dfe0 
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;
53
54INITIALIZE_PASS(MachineCopyPropagation, "machine-cp",
55                "Machine Copy Propagation Pass", false, false)
56
57FunctionPass *llvm::createMachineCopyPropagationPass() {
58  return new MachineCopyPropagation();
59}
60
61void
62MachineCopyPropagation::SourceNoLongerAvailable(unsigned Reg,
63                              DenseMap<unsigned, unsigned> &SrcMap,
64                              DenseMap<unsigned, MachineInstr*> &AvailCopyMap) {
65  DenseMap<unsigned, unsigned>::iterator SI = SrcMap.find(Reg);
66  if (SI != SrcMap.end()) {
67    unsigned MappedDef = SI->second;
68    // Source of copy is no longer available for propagation.
69    if (AvailCopyMap.erase(MappedDef)) {
70      for (const unsigned *SR = TRI->getSubRegisters(MappedDef); *SR; ++SR)
71        AvailCopyMap.erase(*SR);
72    }
73  }
74  for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
75    SI = SrcMap.find(*AS);
76    if (SI != SrcMap.end()) {
77      unsigned MappedDef = SI->second;
78      if (AvailCopyMap.erase(MappedDef)) {
79        for (const unsigned *SR = TRI->getSubRegisters(MappedDef); *SR; ++SR)
80          AvailCopyMap.erase(*SR);
81      }
82    }
83  }
84}
85
86static bool NoInterveningSideEffect(const MachineInstr *CopyMI,
87                                    const MachineInstr *MI) {
88  const MachineBasicBlock *MBB = CopyMI->getParent();
89  if (MI->getParent() != MBB)
90    return false;
91  MachineBasicBlock::const_iterator I = CopyMI;
92  MachineBasicBlock::const_iterator E = MBB->end();
93  MachineBasicBlock::const_iterator E2 = MI;
94
95  ++I;
96  while (I != E && I != E2) {
97    if (I->hasUnmodeledSideEffects() || I->isCall() ||
98        I->isTerminator())
99      return false;
100    ++I;
101  }
102  return true;
103}
104
105bool MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
106  SmallSetVector<MachineInstr*, 8> MaybeDeadCopies; // Candidates for deletion
107  DenseMap<unsigned, MachineInstr*> AvailCopyMap;   // Def -> available copies map
108  DenseMap<unsigned, MachineInstr*> CopyMap;        // Def -> copies map
109  DenseMap<unsigned, unsigned> SrcMap;              // Src -> Def map
110
111  bool Changed = false;
112  for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E; ) {
113    MachineInstr *MI = &*I;
114    ++I;
115
116    if (MI->isCopy()) {
117      unsigned Def = MI->getOperand(0).getReg();
118      unsigned Src = MI->getOperand(1).getReg();
119
120      if (TargetRegisterInfo::isVirtualRegister(Def) ||
121          TargetRegisterInfo::isVirtualRegister(Src))
122        report_fatal_error("MachineCopyPropagation should be run after"
123                           " register allocation!");
124
125      DenseMap<unsigned, MachineInstr*>::iterator CI = AvailCopyMap.find(Src);
126      if (CI != AvailCopyMap.end()) {
127        MachineInstr *CopyMI = CI->second;
128        unsigned SrcSrc = CopyMI->getOperand(1).getReg();
129        if (!ReservedRegs.test(Def) &&
130            (!ReservedRegs.test(Src) || NoInterveningSideEffect(CopyMI, MI)) &&
131            (SrcSrc == Def || TRI->isSubRegister(SrcSrc, Def))) {
132          // The two copies cancel out and the source of the first copy
133          // hasn't been overridden, eliminate the second one. e.g.
134          //  %ECX<def> = COPY %EAX<kill>
135          //  ... nothing clobbered EAX.
136          //  %EAX<def> = COPY %ECX
137          // =>
138          //  %ECX<def> = COPY %EAX
139          //
140          // Also avoid eliminating a copy from reserved registers unless the
141          // definition is proven not clobbered. e.g.
142          // %RSP<def> = COPY %RAX
143          // CALL
144          // %RAX<def> = COPY %RSP
145
146          // Clear any kills of Def between CopyMI and MI. This extends the
147          // live range.
148          for (MachineBasicBlock::iterator I = CopyMI, E = MI; I != E; ++I)
149            I->clearRegisterKills(Def, TRI);
150
151          MI->eraseFromParent();
152          Changed = true;
153          ++NumDeletes;
154          continue;
155        }
156      }
157
158      // If Src is defined by a previous copy, it cannot be eliminated.
159      CI = CopyMap.find(Src);
160      if (CI != CopyMap.end())
161        MaybeDeadCopies.remove(CI->second);
162      for (const unsigned *AS = TRI->getAliasSet(Src); *AS; ++AS) {
163        CI = CopyMap.find(*AS);
164        if (CI != CopyMap.end())
165          MaybeDeadCopies.remove(CI->second);
166      }
167
168      // Copy is now a candidate for deletion.
169      MaybeDeadCopies.insert(MI);
170
171      // If 'Src' is previously source of another copy, then this earlier copy's
172      // source is no longer available. e.g.
173      // %xmm9<def> = copy %xmm2
174      // ...
175      // %xmm2<def> = copy %xmm0
176      // ...
177      // %xmm2<def> = copy %xmm9
178      SourceNoLongerAvailable(Def, SrcMap, AvailCopyMap);
179
180      // Remember Def is defined by the copy.
181      CopyMap[Def] = MI;
182      AvailCopyMap[Def] = MI;
183      for (const unsigned *SR = TRI->getSubRegisters(Def); *SR; ++SR) {
184        CopyMap[*SR] = MI;
185        AvailCopyMap[*SR] = MI;
186      }
187
188      // Remember source that's copied to Def. Once it's clobbered, then
189      // it's no longer available for copy propagation.
190      SrcMap[Src] = Def;
191
192      continue;
193    }
194
195    // Not a copy.
196    SmallVector<unsigned, 2> Defs;
197    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
198      MachineOperand &MO = MI->getOperand(i);
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    for (unsigned i = 0, e = Defs.size(); i != e; ++i) {
227      unsigned Reg = Defs[i];
228
229      // No longer defined by a copy.
230      CopyMap.erase(Reg);
231      AvailCopyMap.erase(Reg);
232      for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
233        CopyMap.erase(*AS);
234        AvailCopyMap.erase(*AS);
235      }
236
237      // If 'Reg' is previously source of a copy, it is no longer available for
238      // copy propagation.
239      SourceNoLongerAvailable(Reg, SrcMap, AvailCopyMap);
240    }
241  }
242
243  // If MBB doesn't have successors, delete the copies whose defs are not used.
244  // If MBB does have successors, then conservative assume the defs are live-out
245  // since we don't want to trust live-in lists.
246  if (MBB.succ_empty()) {
247    for (SmallSetVector<MachineInstr*, 8>::iterator
248           DI = MaybeDeadCopies.begin(), DE = MaybeDeadCopies.end();
249         DI != DE; ++DI) {
250      if (!ReservedRegs.test((*DI)->getOperand(0).getReg())) {
251        (*DI)->eraseFromParent();
252        Changed = true;
253        ++NumDeletes;
254      }
255    }
256  }
257
258  return Changed;
259}
260
261bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {
262  bool Changed = false;
263
264  TRI = MF.getTarget().getRegisterInfo();
265  ReservedRegs = TRI->getReservedRegs(MF);
266
267  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
268    Changed |= CopyPropagateBlock(*I);
269
270  return Changed;
271}
272