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