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