MachineCSE.cpp revision a054ae02fda1886f36b4b51cba8ac8000ed8be8a 
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 {
32  class MachineCSE : public MachineFunctionPass {
33    const TargetInstrInfo *TII;
34    MachineRegisterInfo  *MRI;
35    MachineDominatorTree *DT;
36  public:
37    static char ID; // Pass identification
38    MachineCSE() : MachineFunctionPass(&ID), CurrVN(0) {}
39
40    virtual bool runOnMachineFunction(MachineFunction &MF);
41
42    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
43      AU.setPreservesCFG();
44      MachineFunctionPass::getAnalysisUsage(AU);
45      AU.addRequired<MachineDominatorTree>();
46      AU.addPreserved<MachineDominatorTree>();
47    }
48
49  private:
50    unsigned CurrVN;
51    ScopedHashTable<MachineInstr*, unsigned> VNT;
52    SmallVector<MachineInstr*, 64> Exps;
53
54    bool PerformTrivialCoalescing(MachineInstr *MI, MachineBasicBlock *MBB);
55    bool ProcessBlock(MachineDomTreeNode *Node);
56  };
57} // end anonymous namespace
58
59char MachineCSE::ID = 0;
60static RegisterPass<MachineCSE>
61X("machine-cse", "Machine Common Subexpression Elimination");
62
63FunctionPass *llvm::createMachineCSEPass() { return new MachineCSE(); }
64
65bool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI,
66                                          MachineBasicBlock *MBB) {
67  bool Changed = false;
68  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
69    MachineOperand &MO = MI->getOperand(i);
70    if (!MO.isReg() || !MO.isUse())
71      continue;
72    unsigned Reg = MO.getReg();
73    if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg))
74      continue;
75    if (!MRI->hasOneUse(Reg))
76      // Only coalesce single use copies. This ensure the copy will be
77      // deleted.
78      continue;
79    MachineInstr *DefMI = MRI->getVRegDef(Reg);
80    if (DefMI->getParent() != MBB)
81      continue;
82    unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
83    if (TII->isMoveInstr(*DefMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
84        TargetRegisterInfo::isVirtualRegister(SrcReg) &&
85        !SrcSubIdx && !DstSubIdx) {
86      MO.setReg(SrcReg);
87      DefMI->eraseFromParent();
88      ++NumCoalesces;
89      Changed = true;
90    }
91  }
92
93  return Changed;
94}
95
96static bool hasLivePhysRegDefUse(MachineInstr *MI) {
97  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
98    MachineOperand &MO = MI->getOperand(i);
99    if (!MO.isReg())
100      continue;
101    unsigned Reg = MO.getReg();
102    if (!Reg)
103      continue;
104    // FIXME: This is obviously overly conservative. On x86 lots of instructions
105    // will def EFLAGS and they are not marked dead at this point.
106    if (TargetRegisterInfo::isPhysicalRegister(Reg) &&
107        !(MO.isDef() && MO.isDead()))
108      return true;
109  }
110  return false;
111}
112
113bool MachineCSE::ProcessBlock(MachineDomTreeNode *Node) {
114  bool Changed = false;
115
116  ScopedHashTableScope<MachineInstr*, unsigned> VNTS(VNT);
117  MachineBasicBlock *MBB = Node->getBlock();
118  for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) {
119    MachineInstr *MI = &*I;
120    ++I;
121    bool SawStore = false;
122    if (!MI->isSafeToMove(TII, 0, SawStore))
123      continue;
124    // Ignore copies or instructions that read / write physical registers
125    // (except for dead defs of physical registers).
126    unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
127    if (TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) ||
128        MI->isExtractSubreg() || MI->isInsertSubreg() || MI->isSubregToReg())
129      continue;
130    if (hasLivePhysRegDefUse(MI))
131      continue;
132
133    bool FoundCSE = VNT.count(MI);
134    if (!FoundCSE) {
135      // Look for trivial copy coalescing opportunities.
136      if (PerformTrivialCoalescing(MI, MBB))
137        FoundCSE = VNT.count(MI);
138    }
139
140    if (!FoundCSE) {
141      VNT.insert(MI, CurrVN++);
142      Exps.push_back(MI);
143      continue;
144    }
145
146    // Found a common subexpression, eliminate it.
147    unsigned CSVN = VNT.lookup(MI);
148    MachineInstr *CSMI = Exps[CSVN];
149    DEBUG(dbgs() << "Examining: " << *MI);
150    DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI);
151    unsigned NumDefs = MI->getDesc().getNumDefs();
152    for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) {
153      MachineOperand &MO = MI->getOperand(i);
154      if (!MO.isReg() || !MO.isDef())
155        continue;
156      unsigned OldReg = MO.getReg();
157      unsigned NewReg = CSMI->getOperand(i).getReg();
158      assert(OldReg != NewReg &&
159             TargetRegisterInfo::isVirtualRegister(OldReg) &&
160             TargetRegisterInfo::isVirtualRegister(NewReg) &&
161             "Do not CSE physical register defs!");
162      MRI->replaceRegWith(OldReg, NewReg);
163      --NumDefs;
164    }
165    MI->eraseFromParent();
166    ++NumCSEs;
167  }
168
169  // Recursively call ProcessBlock with childred.
170  const std::vector<MachineDomTreeNode*> &Children = Node->getChildren();
171  for (unsigned i = 0, e = Children.size(); i != e; ++i)
172    Changed |= ProcessBlock(Children[i]);
173
174  return Changed;
175}
176
177bool MachineCSE::runOnMachineFunction(MachineFunction &MF) {
178  TII = MF.getTarget().getInstrInfo();
179  MRI = &MF.getRegInfo();
180  DT = &getAnalysis<MachineDominatorTree>();
181  return ProcessBlock(DT->getRootNode());
182}
183