1 //===-- MachineCSE.cpp - Machine Common Subexpression Elimination Pass ----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
14 //===----------------------------------------------------------------------===//
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/Analysis/AliasAnalysis.h"
22 #include "llvm/Target/TargetInstrInfo.h"
23 #include "llvm/ADT/DenseMap.h"
24 #include "llvm/ADT/ScopedHashTable.h"
25 #include "llvm/ADT/Statistic.h"
26 #include "llvm/Support/CommandLine.h"
27 #include "llvm/Support/Debug.h"
31 STATISTIC(NumCoalesces, "Number of copies coalesced");
32 STATISTIC(NumCSEs, "Number of common subexpression eliminated");
35 class MachineCSE : public MachineFunctionPass {
36 const TargetInstrInfo *TII;
37 const TargetRegisterInfo *TRI;
39 MachineDominatorTree *DT;
40 MachineRegisterInfo *MRI;
42 static char ID; // Pass identification
43 MachineCSE() : MachineFunctionPass(&ID), LookAheadLimit(5), CurrVN(0) {}
45 virtual bool runOnMachineFunction(MachineFunction &MF);
47 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
49 MachineFunctionPass::getAnalysisUsage(AU);
50 AU.addRequired<AliasAnalysis>();
51 AU.addRequired<MachineDominatorTree>();
52 AU.addPreserved<MachineDominatorTree>();
56 const unsigned LookAheadLimit;
57 typedef ScopedHashTableScope<MachineInstr*, unsigned,
58 MachineInstrExpressionTrait> ScopeType;
59 DenseMap<MachineBasicBlock*, ScopeType*> ScopeMap;
60 ScopedHashTable<MachineInstr*, unsigned, MachineInstrExpressionTrait> VNT;
61 SmallVector<MachineInstr*, 64> Exps;
64 bool PerformTrivialCoalescing(MachineInstr *MI, MachineBasicBlock *MBB);
65 bool isPhysDefTriviallyDead(unsigned Reg,
66 MachineBasicBlock::const_iterator I,
67 MachineBasicBlock::const_iterator E) const ;
68 bool hasLivePhysRegDefUse(const MachineInstr *MI,
69 const MachineBasicBlock *MBB,
70 unsigned &PhysDef) const;
71 bool PhysRegDefReaches(MachineInstr *CSMI, MachineInstr *MI,
72 unsigned PhysDef) const;
73 bool isCSECandidate(MachineInstr *MI);
74 bool isProfitableToCSE(unsigned CSReg, unsigned Reg,
75 MachineInstr *CSMI, MachineInstr *MI);
76 void EnterScope(MachineBasicBlock *MBB);
77 void ExitScope(MachineBasicBlock *MBB);
78 bool ProcessBlock(MachineBasicBlock *MBB);
79 void ExitScopeIfDone(MachineDomTreeNode *Node,
80 DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren,
81 DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> &ParentMap);
82 bool PerformCSE(MachineDomTreeNode *Node);
84 } // end anonymous namespace
86 char MachineCSE::ID = 0;
87 static RegisterPass<MachineCSE>
88 X("machine-cse", "Machine Common Subexpression Elimination");
90 FunctionPass *llvm::createMachineCSEPass() { return new MachineCSE(); }
92 bool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI,
93 MachineBasicBlock *MBB) {
95 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
96 MachineOperand &MO = MI->getOperand(i);
97 if (!MO.isReg() || !MO.isUse())
99 unsigned Reg = MO.getReg();
100 if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg))
102 if (!MRI->hasOneUse(Reg))
103 // Only coalesce single use copies. This ensure the copy will be
106 MachineInstr *DefMI = MRI->getVRegDef(Reg);
107 if (DefMI->getParent() != MBB)
109 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
110 if (TII->isMoveInstr(*DefMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
111 TargetRegisterInfo::isVirtualRegister(SrcReg) &&
112 !SrcSubIdx && !DstSubIdx) {
113 const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg);
114 const TargetRegisterClass *RC = MRI->getRegClass(Reg);
115 const TargetRegisterClass *NewRC = getCommonSubClass(RC, SRC);
118 DEBUG(dbgs() << "Coalescing: " << *DefMI);
119 DEBUG(dbgs() << "*** to: " << *MI);
121 MRI->clearKillFlags(SrcReg);
123 MRI->setRegClass(SrcReg, NewRC);
124 DefMI->eraseFromParent();
134 MachineCSE::isPhysDefTriviallyDead(unsigned Reg,
135 MachineBasicBlock::const_iterator I,
136 MachineBasicBlock::const_iterator E) const {
137 unsigned LookAheadLeft = LookAheadLimit;
138 while (LookAheadLeft) {
139 // Skip over dbg_value's.
140 while (I != E && I->isDebugValue())
144 // Reached end of block, register is obviously dead.
147 bool SeenDef = false;
148 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
149 const MachineOperand &MO = I->getOperand(i);
150 if (!MO.isReg() || !MO.getReg())
152 if (!TRI->regsOverlap(MO.getReg(), Reg))
160 // See a def of Reg (or an alias) before encountering any use, it's
170 /// hasLivePhysRegDefUse - Return true if the specified instruction read / write
171 /// physical registers (except for dead defs of physical registers). It also
172 /// returns the physical register def by reference if it's the only one.
173 bool MachineCSE::hasLivePhysRegDefUse(const MachineInstr *MI,
174 const MachineBasicBlock *MBB,
175 unsigned &PhysDef) const {
177 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
178 const MachineOperand &MO = MI->getOperand(i);
181 unsigned Reg = MO.getReg();
184 if (TargetRegisterInfo::isVirtualRegister(Reg))
187 // Can't touch anything to read a physical register.
190 // If the def is dead, it's ok.
192 // Ok, this is a physical register def that's not marked "dead". That's
193 // common since this pass is run before livevariables. We can scan
194 // forward a few instructions and check if it is obviously dead.
196 // Multiple physical register defs. These are rare, forget about it.
204 MachineBasicBlock::const_iterator I = MI; I = llvm::next(I);
205 if (!isPhysDefTriviallyDead(PhysDef, I, MBB->end()))
211 bool MachineCSE::PhysRegDefReaches(MachineInstr *CSMI, MachineInstr *MI,
212 unsigned PhysDef) const {
213 // For now conservatively returns false if the common subexpression is
214 // not in the same basic block as the given instruction.
215 MachineBasicBlock *MBB = MI->getParent();
216 if (CSMI->getParent() != MBB)
218 MachineBasicBlock::const_iterator I = CSMI; I = llvm::next(I);
219 MachineBasicBlock::const_iterator E = MI;
220 unsigned LookAheadLeft = LookAheadLimit;
221 while (LookAheadLeft) {
222 // Skip over dbg_value's.
223 while (I != E && I->isDebugValue())
228 if (I->modifiesRegister(PhysDef, TRI))
238 static bool isCopy(const MachineInstr *MI, const TargetInstrInfo *TII) {
239 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
240 return TII->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) ||
241 MI->isExtractSubreg() || MI->isInsertSubreg() || MI->isSubregToReg();
244 bool MachineCSE::isCSECandidate(MachineInstr *MI) {
245 if (MI->isLabel() || MI->isPHI() || MI->isImplicitDef() ||
246 MI->isKill() || MI->isInlineAsm() || MI->isDebugValue())
253 // Ignore stuff that we obviously can't move.
254 const TargetInstrDesc &TID = MI->getDesc();
255 if (TID.mayStore() || TID.isCall() || TID.isTerminator() ||
256 TID.hasUnmodeledSideEffects())
260 // Okay, this instruction does a load. As a refinement, we allow the target
261 // to decide whether the loaded value is actually a constant. If so, we can
262 // actually use it as a load.
263 if (!MI->isInvariantLoad(AA))
264 // FIXME: we should be able to hoist loads with no other side effects if
265 // there are no other instructions which can change memory in this loop.
266 // This is a trivial form of alias analysis.
272 /// isProfitableToCSE - Return true if it's profitable to eliminate MI with a
273 /// common expression that defines Reg.
274 bool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg,
275 MachineInstr *CSMI, MachineInstr *MI) {
276 // FIXME: Heuristics that works around the lack the live range splitting.
278 // Heuristics #1: Don't cse "cheap" computating if the def is not local or in an
279 // immediate predecessor. We don't want to increase register pressure and end up
280 // causing other computation to be spilled.
281 if (MI->getDesc().isAsCheapAsAMove()) {
282 MachineBasicBlock *CSBB = CSMI->getParent();
283 MachineBasicBlock *BB = MI->getParent();
285 find(CSBB->succ_begin(), CSBB->succ_end(), BB) == CSBB->succ_end())
289 // Heuristics #2: If the expression doesn't not use a vr and the only use
290 // of the redundant computation are copies, do not cse.
291 bool HasVRegUse = false;
292 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
293 const MachineOperand &MO = MI->getOperand(i);
294 if (MO.isReg() && MO.isUse() && MO.getReg() &&
295 TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
301 bool HasNonCopyUse = false;
302 for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(Reg),
303 E = MRI->use_nodbg_end(); I != E; ++I) {
304 MachineInstr *Use = &*I;
306 if (!isCopy(Use, TII)) {
307 HasNonCopyUse = true;
315 // Heuristics #3: If the common subexpression is used by PHIs, do not reuse
316 // it unless the defined value is already used in the BB of the new use.
318 SmallPtrSet<MachineBasicBlock*, 4> CSBBs;
319 for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(CSReg),
320 E = MRI->use_nodbg_end(); I != E; ++I) {
321 MachineInstr *Use = &*I;
322 HasPHI |= Use->isPHI();
323 CSBBs.insert(Use->getParent());
328 return CSBBs.count(MI->getParent());
331 void MachineCSE::EnterScope(MachineBasicBlock *MBB) {
332 DEBUG(dbgs() << "Entering: " << MBB->getName() << '\n');
333 ScopeType *Scope = new ScopeType(VNT);
334 ScopeMap[MBB] = Scope;
337 void MachineCSE::ExitScope(MachineBasicBlock *MBB) {
338 DEBUG(dbgs() << "Exiting: " << MBB->getName() << '\n');
339 DenseMap<MachineBasicBlock*, ScopeType*>::iterator SI = ScopeMap.find(MBB);
340 assert(SI != ScopeMap.end());
345 bool MachineCSE::ProcessBlock(MachineBasicBlock *MBB) {
346 bool Changed = false;
348 SmallVector<std::pair<unsigned, unsigned>, 8> CSEPairs;
349 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) {
350 MachineInstr *MI = &*I;
353 if (!isCSECandidate(MI))
356 bool FoundCSE = VNT.count(MI);
358 // Look for trivial copy coalescing opportunities.
359 if (PerformTrivialCoalescing(MI, MBB)) {
360 // After coalescing MI itself may become a copy.
363 FoundCSE = VNT.count(MI);
366 // FIXME: commute commutable instructions?
368 // If the instruction defines a physical register and the value *may* be
369 // used, then it's not safe to replace it with a common subexpression.
370 unsigned PhysDef = 0;
371 if (FoundCSE && hasLivePhysRegDefUse(MI, MBB, PhysDef)) {
374 // ... Unless the CS is local and it also defines the physical register
375 // which is not clobbered in between.
377 unsigned CSVN = VNT.lookup(MI);
378 MachineInstr *CSMI = Exps[CSVN];
379 if (PhysRegDefReaches(CSMI, MI, PhysDef))
385 VNT.insert(MI, CurrVN++);
390 // Found a common subexpression, eliminate it.
391 unsigned CSVN = VNT.lookup(MI);
392 MachineInstr *CSMI = Exps[CSVN];
393 DEBUG(dbgs() << "Examining: " << *MI);
394 DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI);
396 // Check if it's profitable to perform this CSE.
398 unsigned NumDefs = MI->getDesc().getNumDefs();
399 for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) {
400 MachineOperand &MO = MI->getOperand(i);
401 if (!MO.isReg() || !MO.isDef())
403 unsigned OldReg = MO.getReg();
404 unsigned NewReg = CSMI->getOperand(i).getReg();
405 if (OldReg == NewReg)
407 assert(TargetRegisterInfo::isVirtualRegister(OldReg) &&
408 TargetRegisterInfo::isVirtualRegister(NewReg) &&
409 "Do not CSE physical register defs!");
410 if (!isProfitableToCSE(NewReg, OldReg, CSMI, MI)) {
414 CSEPairs.push_back(std::make_pair(OldReg, NewReg));
418 // Actually perform the elimination.
420 for (unsigned i = 0, e = CSEPairs.size(); i != e; ++i) {
421 MRI->replaceRegWith(CSEPairs[i].first, CSEPairs[i].second);
422 MRI->clearKillFlags(CSEPairs[i].second);
424 MI->eraseFromParent();
427 DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n");
428 VNT.insert(MI, CurrVN++);
437 /// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given
438 /// dominator tree node if its a leaf or all of its children are done. Walk
439 /// up the dominator tree to destroy ancestors which are now done.
441 MachineCSE::ExitScopeIfDone(MachineDomTreeNode *Node,
442 DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren,
443 DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> &ParentMap) {
444 if (OpenChildren[Node])
448 ExitScope(Node->getBlock());
450 // Now traverse upwards to pop ancestors whose offsprings are all done.
451 while (MachineDomTreeNode *Parent = ParentMap[Node]) {
452 unsigned Left = --OpenChildren[Parent];
455 ExitScope(Parent->getBlock());
460 bool MachineCSE::PerformCSE(MachineDomTreeNode *Node) {
461 SmallVector<MachineDomTreeNode*, 32> Scopes;
462 SmallVector<MachineDomTreeNode*, 8> WorkList;
463 DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> ParentMap;
464 DenseMap<MachineDomTreeNode*, unsigned> OpenChildren;
466 // Perform a DFS walk to determine the order of visit.
467 WorkList.push_back(Node);
469 Node = WorkList.pop_back_val();
470 Scopes.push_back(Node);
471 const std::vector<MachineDomTreeNode*> &Children = Node->getChildren();
472 unsigned NumChildren = Children.size();
473 OpenChildren[Node] = NumChildren;
474 for (unsigned i = 0; i != NumChildren; ++i) {
475 MachineDomTreeNode *Child = Children[i];
476 ParentMap[Child] = Node;
477 WorkList.push_back(Child);
479 } while (!WorkList.empty());
482 bool Changed = false;
483 for (unsigned i = 0, e = Scopes.size(); i != e; ++i) {
484 MachineDomTreeNode *Node = Scopes[i];
485 MachineBasicBlock *MBB = Node->getBlock();
487 Changed |= ProcessBlock(MBB);
488 // If it's a leaf node, it's done. Traverse upwards to pop ancestors.
489 ExitScopeIfDone(Node, OpenChildren, ParentMap);
495 bool MachineCSE::runOnMachineFunction(MachineFunction &MF) {
496 TII = MF.getTarget().getInstrInfo();
497 TRI = MF.getTarget().getRegisterInfo();
498 MRI = &MF.getRegInfo();
499 AA = &getAnalysis<AliasAnalysis>();
500 DT = &getAnalysis<MachineDominatorTree>();
501 return PerformCSE(DT->getRootNode());