MachineCSE.cpp revision 86a144c9543b17fb15eeaf17e16686a5c863461c 
1//===-- MachineCSE.cpp - Machine Common Subexpression Elimination 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 pass performs global common subexpression elimination on machine
11// instructions using a scoped hash table based value numbering scheme. It
12// must be run while the machine function is still in SSA form.
13//
14//===----------------------------------------------------------------------===//
15
16#define DEBUG_TYPE "machine-cse"
17#include "llvm/CodeGen/Passes.h"
18#include "llvm/CodeGen/MachineDominators.h"
19#include "llvm/CodeGen/MachineInstr.h"
20#include "llvm/CodeGen/MachineRegisterInfo.h"
21#include "llvm/Target/TargetInstrInfo.h"
22#include "llvm/ADT/ScopedHashTable.h"
23#include "llvm/ADT/Statistic.h"
24#include "llvm/Support/Debug.h"
25
26using namespace llvm;
27
28STATISTIC(NumCoalesces, "Number of copies coalesced");
29STATISTIC(NumCSEs,      "Number of common subexpression eliminated");
30
31namespace llvm {
32  template<> struct DenseMapInfo<MachineInstr*> {
33    static inline MachineInstr *getEmptyKey() {
34      return 0;
35    }
36
37    static inline MachineInstr *getTombstoneKey() {
38      return reinterpret_cast<MachineInstr*>(-1);
39    }
40
41    static unsigned getHashValue(const MachineInstr* const &MI) {
42      unsigned Hash = MI->getOpcode() * 37;
43      for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
44        const MachineOperand &MO = MI->getOperand(i);
45        uint64_t Key = (uint64_t)MO.getType() << 32;
46        switch (MO.getType()) {
47        default: break;
48        case MachineOperand::MO_Register:
49          if (MO.isDef() && TargetRegisterInfo::isVirtualRegister(MO.getReg()))
50            continue;  // Skip virtual register defs.
51          Key |= MO.getReg();
52          break;
53        case MachineOperand::MO_Immediate:
54          Key |= MO.getImm();
55          break;
56        case MachineOperand::MO_FrameIndex:
57        case MachineOperand::MO_ConstantPoolIndex:
58        case MachineOperand::MO_JumpTableIndex:
59          Key |= MO.getIndex();
60          break;
61        case MachineOperand::MO_MachineBasicBlock:
62          Key |= DenseMapInfo<void*>::getHashValue(MO.getMBB());
63          break;
64        case MachineOperand::MO_GlobalAddress:
65          Key |= DenseMapInfo<void*>::getHashValue(MO.getGlobal());
66          break;
67        case MachineOperand::MO_BlockAddress:
68          Key |= DenseMapInfo<void*>::getHashValue(MO.getBlockAddress());
69          break;
70        }
71        Key += ~(Key << 32);
72        Key ^= (Key >> 22);
73        Key += ~(Key << 13);
74        Key ^= (Key >> 8);
75        Key += (Key << 3);
76        Key ^= (Key >> 15);
77        Key += ~(Key << 27);
78        Key ^= (Key >> 31);
79        Hash = (unsigned)Key + Hash * 37;
80      }
81      return Hash;
82    }
83
84    static bool isEqual(const MachineInstr* const &LHS,
85                        const MachineInstr* const &RHS) {
86      if (RHS == getEmptyKey() || RHS == getTombstoneKey() ||
87          LHS == getEmptyKey() || LHS == getTombstoneKey())
88        return LHS == RHS;
89      return LHS->isIdenticalTo(RHS, MachineInstr::IgnoreVRegDefs);
90    }
91  };
92} // end llvm namespace
93
94namespace {
95  class MachineCSE : public MachineFunctionPass {
96    const TargetInstrInfo *TII;
97    MachineRegisterInfo  *MRI;
98    MachineDominatorTree *DT;
99  public:
100    static char ID; // Pass identification
101    MachineCSE() : MachineFunctionPass(&ID), CurrVN(0) {}
102
103    virtual bool runOnMachineFunction(MachineFunction &MF);
104
105    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
106      AU.setPreservesCFG();
107      MachineFunctionPass::getAnalysisUsage(AU);
108      AU.addRequired<MachineDominatorTree>();
109      AU.addPreserved<MachineDominatorTree>();
110    }
111
112  private:
113    unsigned CurrVN;
114    ScopedHashTable<MachineInstr*, unsigned> VNT;
115    SmallVector<MachineInstr*, 64> Exps;
116
117    bool PerformTrivialCoalescing(MachineInstr *MI, MachineBasicBlock *MBB);
118    bool ProcessBlock(MachineDomTreeNode *Node);
119  };
120} // end anonymous namespace
121
122char MachineCSE::ID = 0;
123static RegisterPass<MachineCSE>
124X("machine-cse", "Machine Common Subexpression Elimination");
125
126FunctionPass *llvm::createMachineCSEPass() { return new MachineCSE(); }
127
128bool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI,
129                                          MachineBasicBlock *MBB) {
130  bool Changed = false;
131  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
132    MachineOperand &MO = MI->getOperand(i);
133    if (!MO.isReg() || !MO.isUse())
134      continue;
135    unsigned Reg = MO.getReg();
136    if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg))
137      continue;
138    if (!MRI->hasOneUse(Reg))
139      // Only coalesce single use copies. This ensure the copy will be
140      // deleted.
141      continue;
142    MachineInstr *DefMI = MRI->getVRegDef(Reg);
143    if (DefMI->getParent() != MBB)
144      continue;
145    unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
146    if (TII->isMoveInstr(*DefMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
147        TargetRegisterInfo::isVirtualRegister(SrcReg) &&
148        !SrcSubIdx && !DstSubIdx) {
149      MO.setReg(SrcReg);
150      DefMI->eraseFromParent();
151      ++NumCoalesces;
152      Changed = true;
153    }
154  }
155
156  return Changed;
157}
158
159static bool hasLivePhysRegDefUse(MachineInstr *MI) {
160  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
161    MachineOperand &MO = MI->getOperand(i);
162    if (!MO.isReg())
163      continue;
164    unsigned Reg = MO.getReg();
165    if (!Reg)
166      continue;
167    // FIXME: This is obviously overly conservative. On x86 lots of instructions
168    // will def EFLAGS and they are not marked dead at this point.
169    if (TargetRegisterInfo::isPhysicalRegister(Reg) &&
170        !(MO.isDef() && MO.isDead()))
171      return true;
172  }
173  return false;
174}
175
176bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) {
177  bool Changed = false;
178
179  ScopedHashTableScope<MachineInstr*, unsigned> VNTS(VNT);
180  MachineBasicBlock *MBB = Node->getBlock();
181  for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) {
182    MachineInstr *MI = &*I;
183    ++I;
184    bool SawStore = false;
185    if (!MI->isSafeToMove(TII, 0, SawStore))
186      continue;
187    // Ignore copies or instructions that read / write physical registers
188    // (except for dead defs of physical registers).
189    unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
190    if (TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) ||
191        MI->isExtractSubreg() || MI->isInsertSubreg() || MI->isSubregToReg())
192      continue;
193    if (hasLivePhysRegDefUse(MI))
194      continue;
195
196    bool FoundCSE = VNT.count(MI);
197    if (!FoundCSE) {
198      // Look for trivial copy coalescing opportunities.
199      if (PerformTrivialCoalescing(MI, MBB))
200        FoundCSE = VNT.count(MI);
201    }
202
203    if (!FoundCSE) {
204      VNT.insert(MI, CurrVN++);
205      Exps.push_back(MI);
206      continue;
207    }
208
209    // Found a common subexpression, eliminate it.
210    unsigned CSVN = VNT.lookup(MI);
211    MachineInstr *CSMI = Exps[CSVN];
212    DEBUG(dbgs() << "Examining: " << *MI);
213    DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI);
214    unsigned NumDefs = MI->getDesc().getNumDefs();
215    for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) {
216      MachineOperand &MO = MI->getOperand(i);
217      if (!MO.isReg() || !MO.isDef())
218        continue;
219      unsigned OldReg = MO.getReg();
220      unsigned NewReg = CSMI->getOperand(i).getReg();
221      assert(OldReg != NewReg &&
222             TargetRegisterInfo::isVirtualRegister(OldReg) &&
223             TargetRegisterInfo::isVirtualRegister(NewReg) &&
224             "Do not CSE physical register defs!");
225      MRI->replaceRegWith(OldReg, NewReg);
226      --NumDefs;
227    }
228    MI->eraseFromParent();
229    ++NumCSEs;
230  }
231
232  // Recursively call ProcessBlock with childred.
233  const std::vector<MachineDomTreeNode*> &Children = Node->getChildren();
234  for (unsigned i = 0, e = Children.size(); i != e; ++i)
235    Changed |= ProcessBlock(Children[i]);
236
237  return Changed;
238}
239
240bool MachineCSE::runOnMachineFunction(MachineFunction &MF) {
241  TII = MF.getTarget().getInstrInfo();
242  MRI = &MF.getRegInfo();
243  DT = &getAnalysis<MachineDominatorTree>();
244  return ProcessBlock(DT->getRootNode());
245}
246