blob: 5dd51a7944c80e377f7d2211c4a146d4a3d8979e [file] [log] [blame]
Evan Chengc6fe3332010-03-02 02:38:24 +00001//===-- 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
Evan Chengc5bbba12010-03-02 19:02:27 +000011// instructions using a scoped hash table based value numbering scheme. It
Evan Chengc6fe3332010-03-02 02:38:24 +000012// 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"
Evan Cheng6ba95542010-03-03 02:48:20 +000020#include "llvm/CodeGen/MachineRegisterInfo.h"
Evan Chenga5f32cb2010-03-04 21:18:08 +000021#include "llvm/Analysis/AliasAnalysis.h"
Evan Cheng6ba95542010-03-03 02:48:20 +000022#include "llvm/Target/TargetInstrInfo.h"
Evan Cheng31156982010-04-21 00:21:07 +000023#include "llvm/ADT/DenseMap.h"
Evan Chengc6fe3332010-03-02 02:38:24 +000024#include "llvm/ADT/ScopedHashTable.h"
Evan Cheng189c1ec2010-10-29 23:36:03 +000025#include "llvm/ADT/SmallSet.h"
Evan Chengc6fe3332010-03-02 02:38:24 +000026#include "llvm/ADT/Statistic.h"
27#include "llvm/Support/Debug.h"
Cameron Zwarich53eeba52011-01-03 04:07:46 +000028#include "llvm/Support/RecyclingAllocator.h"
Evan Chengc6fe3332010-03-02 02:38:24 +000029using namespace llvm;
30
Evan Cheng16b48b82010-03-03 21:20:05 +000031STATISTIC(NumCoalesces, "Number of copies coalesced");
32STATISTIC(NumCSEs, "Number of common subexpression eliminated");
Evan Cheng189c1ec2010-10-29 23:36:03 +000033STATISTIC(NumPhysCSEs,
34 "Number of physreg referencing common subexpr eliminated");
Evan Cheng97b5beb2012-01-10 02:02:58 +000035STATISTIC(NumCrossBBCSEs,
36 "Number of cross-MBB physreg referencing CS eliminated");
Evan Chenga63cde22010-12-15 22:16:21 +000037STATISTIC(NumCommutes, "Number of copies coalesced after commuting");
Bob Wilson38441732010-06-03 18:28:31 +000038
Evan Chengc6fe3332010-03-02 02:38:24 +000039namespace {
40 class MachineCSE : public MachineFunctionPass {
Evan Cheng6ba95542010-03-03 02:48:20 +000041 const TargetInstrInfo *TII;
Evan Chengb3958e82010-03-04 01:33:55 +000042 const TargetRegisterInfo *TRI;
Evan Chenga5f32cb2010-03-04 21:18:08 +000043 AliasAnalysis *AA;
Evan Cheng31f94c72010-03-09 03:21:12 +000044 MachineDominatorTree *DT;
45 MachineRegisterInfo *MRI;
Evan Chengc6fe3332010-03-02 02:38:24 +000046 public:
47 static char ID; // Pass identification
Owen Anderson081c34b2010-10-19 17:21:58 +000048 MachineCSE() : MachineFunctionPass(ID), LookAheadLimit(5), CurrVN(0) {
49 initializeMachineCSEPass(*PassRegistry::getPassRegistry());
50 }
Evan Chengc6fe3332010-03-02 02:38:24 +000051
52 virtual bool runOnMachineFunction(MachineFunction &MF);
53
54 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
55 AU.setPreservesCFG();
56 MachineFunctionPass::getAnalysisUsage(AU);
Evan Chenga5f32cb2010-03-04 21:18:08 +000057 AU.addRequired<AliasAnalysis>();
Evan Cheng65424162010-08-17 20:57:42 +000058 AU.addPreservedID(MachineLoopInfoID);
Evan Chengc6fe3332010-03-02 02:38:24 +000059 AU.addRequired<MachineDominatorTree>();
60 AU.addPreserved<MachineDominatorTree>();
61 }
62
Evan Chengc2b768f2010-09-17 21:59:42 +000063 virtual void releaseMemory() {
64 ScopeMap.clear();
65 Exps.clear();
66 }
67
Evan Chengc6fe3332010-03-02 02:38:24 +000068 private:
Evan Cheng835810b2010-05-21 21:22:19 +000069 const unsigned LookAheadLimit;
Cameron Zwarich53eeba52011-01-03 04:07:46 +000070 typedef RecyclingAllocator<BumpPtrAllocator,
71 ScopedHashTableVal<MachineInstr*, unsigned> > AllocatorTy;
72 typedef ScopedHashTable<MachineInstr*, unsigned,
73 MachineInstrExpressionTrait, AllocatorTy> ScopedHTType;
74 typedef ScopedHTType::ScopeTy ScopeType;
Evan Cheng31156982010-04-21 00:21:07 +000075 DenseMap<MachineBasicBlock*, ScopeType*> ScopeMap;
Cameron Zwarich53eeba52011-01-03 04:07:46 +000076 ScopedHTType VNT;
Evan Cheng16b48b82010-03-03 21:20:05 +000077 SmallVector<MachineInstr*, 64> Exps;
Evan Cheng31156982010-04-21 00:21:07 +000078 unsigned CurrVN;
Evan Cheng16b48b82010-03-03 21:20:05 +000079
Evan Chenga5f32cb2010-03-04 21:18:08 +000080 bool PerformTrivialCoalescing(MachineInstr *MI, MachineBasicBlock *MBB);
Evan Chengb3958e82010-03-04 01:33:55 +000081 bool isPhysDefTriviallyDead(unsigned Reg,
82 MachineBasicBlock::const_iterator I,
Evan Cheng835810b2010-05-21 21:22:19 +000083 MachineBasicBlock::const_iterator E) const ;
Evan Cheng189c1ec2010-10-29 23:36:03 +000084 bool hasLivePhysRegDefUses(const MachineInstr *MI,
85 const MachineBasicBlock *MBB,
Evan Cheng97b5beb2012-01-10 02:02:58 +000086 SmallSet<unsigned,8> &PhysRefs,
87 SmallVector<unsigned,2> &PhysDefs) const;
Evan Cheng189c1ec2010-10-29 23:36:03 +000088 bool PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI,
Evan Cheng97b5beb2012-01-10 02:02:58 +000089 SmallSet<unsigned,8> &PhysRefs,
90 bool &NonLocal) const;
Evan Chenga5f32cb2010-03-04 21:18:08 +000091 bool isCSECandidate(MachineInstr *MI);
Evan Cheng2938a002010-03-10 02:12:03 +000092 bool isProfitableToCSE(unsigned CSReg, unsigned Reg,
93 MachineInstr *CSMI, MachineInstr *MI);
Evan Cheng31156982010-04-21 00:21:07 +000094 void EnterScope(MachineBasicBlock *MBB);
95 void ExitScope(MachineBasicBlock *MBB);
96 bool ProcessBlock(MachineBasicBlock *MBB);
97 void ExitScopeIfDone(MachineDomTreeNode *Node,
98 DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren,
99 DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> &ParentMap);
100 bool PerformCSE(MachineDomTreeNode *Node);
Evan Chengc6fe3332010-03-02 02:38:24 +0000101 };
102} // end anonymous namespace
103
104char MachineCSE::ID = 0;
Owen Anderson2ab36d32010-10-12 19:48:12 +0000105INITIALIZE_PASS_BEGIN(MachineCSE, "machine-cse",
106 "Machine Common Subexpression Elimination", false, false)
107INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
108INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
109INITIALIZE_PASS_END(MachineCSE, "machine-cse",
Owen Andersonce665bd2010-10-07 22:25:06 +0000110 "Machine Common Subexpression Elimination", false, false)
Evan Chengc6fe3332010-03-02 02:38:24 +0000111
112FunctionPass *llvm::createMachineCSEPass() { return new MachineCSE(); }
113
Evan Cheng6ba95542010-03-03 02:48:20 +0000114bool MachineCSE::PerformTrivialCoalescing(MachineInstr *MI,
115 MachineBasicBlock *MBB) {
116 bool Changed = false;
117 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
118 MachineOperand &MO = MI->getOperand(i);
Evan Cheng16b48b82010-03-03 21:20:05 +0000119 if (!MO.isReg() || !MO.isUse())
120 continue;
121 unsigned Reg = MO.getReg();
Jakob Stoklund Olesenc9df0252011-01-10 02:58:51 +0000122 if (!TargetRegisterInfo::isVirtualRegister(Reg))
Evan Cheng16b48b82010-03-03 21:20:05 +0000123 continue;
Evan Chengf437f732010-09-17 21:56:26 +0000124 if (!MRI->hasOneNonDBGUse(Reg))
Evan Cheng16b48b82010-03-03 21:20:05 +0000125 // Only coalesce single use copies. This ensure the copy will be
126 // deleted.
127 continue;
128 MachineInstr *DefMI = MRI->getVRegDef(Reg);
129 if (DefMI->getParent() != MBB)
130 continue;
Jakob Stoklund Olesen0bc25f42010-07-08 16:40:22 +0000131 if (!DefMI->isCopy())
132 continue;
Jakob Stoklund Olesen04c528a2010-07-16 04:45:42 +0000133 unsigned SrcReg = DefMI->getOperand(1).getReg();
Jakob Stoklund Olesen0bc25f42010-07-08 16:40:22 +0000134 if (!TargetRegisterInfo::isVirtualRegister(SrcReg))
135 continue;
136 if (DefMI->getOperand(0).getSubReg() || DefMI->getOperand(1).getSubReg())
137 continue;
Jakob Stoklund Olesenbf4699c2010-10-06 23:54:39 +0000138 if (!MRI->constrainRegClass(SrcReg, MRI->getRegClass(Reg)))
Jakob Stoklund Olesen0bc25f42010-07-08 16:40:22 +0000139 continue;
140 DEBUG(dbgs() << "Coalescing: " << *DefMI);
Jakob Stoklund Olesenbf4699c2010-10-06 23:54:39 +0000141 DEBUG(dbgs() << "*** to: " << *MI);
Jakob Stoklund Olesen0bc25f42010-07-08 16:40:22 +0000142 MO.setReg(SrcReg);
143 MRI->clearKillFlags(SrcReg);
Jakob Stoklund Olesen0bc25f42010-07-08 16:40:22 +0000144 DefMI->eraseFromParent();
145 ++NumCoalesces;
146 Changed = true;
Evan Cheng6ba95542010-03-03 02:48:20 +0000147 }
148
149 return Changed;
150}
151
Evan Cheng835810b2010-05-21 21:22:19 +0000152bool
153MachineCSE::isPhysDefTriviallyDead(unsigned Reg,
154 MachineBasicBlock::const_iterator I,
155 MachineBasicBlock::const_iterator E) const {
Eric Christophere81d0102010-05-21 23:40:03 +0000156 unsigned LookAheadLeft = LookAheadLimit;
Evan Cheng112e5e72010-03-23 20:33:48 +0000157 while (LookAheadLeft) {
Evan Cheng22504252010-03-24 01:50:28 +0000158 // Skip over dbg_value's.
159 while (I != E && I->isDebugValue())
160 ++I;
161
Evan Chengb3958e82010-03-04 01:33:55 +0000162 if (I == E)
163 // Reached end of block, register is obviously dead.
164 return true;
165
Evan Chengb3958e82010-03-04 01:33:55 +0000166 bool SeenDef = false;
167 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
168 const MachineOperand &MO = I->getOperand(i);
169 if (!MO.isReg() || !MO.getReg())
170 continue;
171 if (!TRI->regsOverlap(MO.getReg(), Reg))
172 continue;
173 if (MO.isUse())
Evan Cheng835810b2010-05-21 21:22:19 +0000174 // Found a use!
Evan Chengb3958e82010-03-04 01:33:55 +0000175 return false;
176 SeenDef = true;
177 }
178 if (SeenDef)
179 // See a def of Reg (or an alias) before encountering any use, it's
180 // trivially dead.
181 return true;
Evan Cheng112e5e72010-03-23 20:33:48 +0000182
183 --LookAheadLeft;
Evan Chengb3958e82010-03-04 01:33:55 +0000184 ++I;
185 }
186 return false;
187}
188
Evan Cheng189c1ec2010-10-29 23:36:03 +0000189/// hasLivePhysRegDefUses - Return true if the specified instruction read/write
Evan Cheng835810b2010-05-21 21:22:19 +0000190/// physical registers (except for dead defs of physical registers). It also
Evan Cheng2b4e7272010-06-04 23:28:13 +0000191/// returns the physical register def by reference if it's the only one and the
192/// instruction does not uses a physical register.
Evan Cheng189c1ec2010-10-29 23:36:03 +0000193bool MachineCSE::hasLivePhysRegDefUses(const MachineInstr *MI,
194 const MachineBasicBlock *MBB,
Evan Cheng97b5beb2012-01-10 02:02:58 +0000195 SmallSet<unsigned,8> &PhysRefs,
196 SmallVector<unsigned,2> &PhysDefs) const{
Evan Cheng189c1ec2010-10-29 23:36:03 +0000197 MachineBasicBlock::const_iterator I = MI; I = llvm::next(I);
Evan Cheng6ba95542010-03-03 02:48:20 +0000198 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
Evan Cheng835810b2010-05-21 21:22:19 +0000199 const MachineOperand &MO = MI->getOperand(i);
Evan Cheng6ba95542010-03-03 02:48:20 +0000200 if (!MO.isReg())
201 continue;
202 unsigned Reg = MO.getReg();
203 if (!Reg)
204 continue;
Evan Cheng835810b2010-05-21 21:22:19 +0000205 if (TargetRegisterInfo::isVirtualRegister(Reg))
206 continue;
Evan Cheng189c1ec2010-10-29 23:36:03 +0000207 // If the def is dead, it's ok. But the def may not marked "dead". That's
Evan Cheng835810b2010-05-21 21:22:19 +0000208 // common since this pass is run before livevariables. We can scan
209 // forward a few instructions and check if it is obviously dead.
Evan Cheng189c1ec2010-10-29 23:36:03 +0000210 if (MO.isDef() &&
211 (MO.isDead() || isPhysDefTriviallyDead(Reg, I, MBB->end())))
212 continue;
213 PhysRefs.insert(Reg);
Evan Cheng97b5beb2012-01-10 02:02:58 +0000214 if (MO.isDef())
215 PhysDefs.push_back(Reg);
Evan Cheng189c1ec2010-10-29 23:36:03 +0000216 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias)
217 PhysRefs.insert(*Alias);
Evan Chengb3958e82010-03-04 01:33:55 +0000218 }
219
Evan Cheng189c1ec2010-10-29 23:36:03 +0000220 return !PhysRefs.empty();
Evan Chengc6fe3332010-03-02 02:38:24 +0000221}
222
Evan Cheng189c1ec2010-10-29 23:36:03 +0000223bool MachineCSE::PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI,
Evan Cheng97b5beb2012-01-10 02:02:58 +0000224 SmallSet<unsigned,8> &PhysRefs,
225 bool &NonLocal) const {
Eli Friedman5e926ac2011-05-06 05:23:07 +0000226 // For now conservatively returns false if the common subexpression is
Evan Cheng97b5beb2012-01-10 02:02:58 +0000227 // not in the same basic block as the given instruction. The only exception
228 // is if the common subexpression is in the sole predecessor block.
229 const MachineBasicBlock *MBB = MI->getParent();
230 const MachineBasicBlock *CSMBB = CSMI->getParent();
231
232 bool CrossMBB = false;
233 if (CSMBB != MBB) {
234 if (MBB->pred_size() == 1 && *MBB->pred_begin() == CSMBB)
235 CrossMBB = true;
236 else
237 return false;
238 }
Eli Friedman5e926ac2011-05-06 05:23:07 +0000239 MachineBasicBlock::const_iterator I = CSMI; I = llvm::next(I);
240 MachineBasicBlock::const_iterator E = MI;
Evan Cheng97b5beb2012-01-10 02:02:58 +0000241 MachineBasicBlock::const_iterator EE = CSMBB->end();
Evan Cheng835810b2010-05-21 21:22:19 +0000242 unsigned LookAheadLeft = LookAheadLimit;
243 while (LookAheadLeft) {
Eli Friedman5e926ac2011-05-06 05:23:07 +0000244 // Skip over dbg_value's.
Evan Cheng97b5beb2012-01-10 02:02:58 +0000245 while (I != E && I != EE && I->isDebugValue())
Evan Cheng835810b2010-05-21 21:22:19 +0000246 ++I;
Eli Friedman5e926ac2011-05-06 05:23:07 +0000247
Evan Cheng97b5beb2012-01-10 02:02:58 +0000248 if (I == EE) {
249 assert(CrossMBB && "Reaching end-of-MBB without finding MI?");
250 CrossMBB = false;
251 NonLocal = true;
252 I = MBB->begin();
253 EE = MBB->end();
254 continue;
255 }
256
Eli Friedman5e926ac2011-05-06 05:23:07 +0000257 if (I == E)
258 return true;
259
260 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
261 const MachineOperand &MO = I->getOperand(i);
262 if (!MO.isReg() || !MO.isDef())
263 continue;
264 unsigned MOReg = MO.getReg();
265 if (TargetRegisterInfo::isVirtualRegister(MOReg))
266 continue;
267 if (PhysRefs.count(MOReg))
268 return false;
Evan Cheng189c1ec2010-10-29 23:36:03 +0000269 }
Eli Friedman5e926ac2011-05-06 05:23:07 +0000270
271 --LookAheadLeft;
272 ++I;
Evan Cheng835810b2010-05-21 21:22:19 +0000273 }
274
275 return false;
276}
277
Evan Chenga5f32cb2010-03-04 21:18:08 +0000278bool MachineCSE::isCSECandidate(MachineInstr *MI) {
Evan Cheng51960182010-03-08 23:49:12 +0000279 if (MI->isLabel() || MI->isPHI() || MI->isImplicitDef() ||
Dale Johannesene68ea062010-03-11 02:10:24 +0000280 MI->isKill() || MI->isInlineAsm() || MI->isDebugValue())
Evan Cheng51960182010-03-08 23:49:12 +0000281 return false;
282
Evan Cheng2938a002010-03-10 02:12:03 +0000283 // Ignore copies.
Jakob Stoklund Olesen04c528a2010-07-16 04:45:42 +0000284 if (MI->isCopyLike())
Evan Chenga5f32cb2010-03-04 21:18:08 +0000285 return false;
286
287 // Ignore stuff that we obviously can't move.
Evan Cheng5a96b3d2011-12-07 07:15:52 +0000288 if (MI->mayStore() || MI->isCall() || MI->isTerminator() ||
Evan Chengc36b7062011-01-07 23:50:32 +0000289 MI->hasUnmodeledSideEffects())
Evan Chenga5f32cb2010-03-04 21:18:08 +0000290 return false;
291
Evan Cheng5a96b3d2011-12-07 07:15:52 +0000292 if (MI->mayLoad()) {
Evan Chenga5f32cb2010-03-04 21:18:08 +0000293 // Okay, this instruction does a load. As a refinement, we allow the target
294 // to decide whether the loaded value is actually a constant. If so, we can
295 // actually use it as a load.
296 if (!MI->isInvariantLoad(AA))
297 // FIXME: we should be able to hoist loads with no other side effects if
298 // there are no other instructions which can change memory in this loop.
299 // This is a trivial form of alias analysis.
300 return false;
301 }
302 return true;
303}
304
Evan Cheng31f94c72010-03-09 03:21:12 +0000305/// isProfitableToCSE - Return true if it's profitable to eliminate MI with a
306/// common expression that defines Reg.
Evan Cheng2938a002010-03-10 02:12:03 +0000307bool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg,
308 MachineInstr *CSMI, MachineInstr *MI) {
309 // FIXME: Heuristics that works around the lack the live range splitting.
310
Chris Lattner622a11b2011-01-10 07:51:31 +0000311 // Heuristics #1: Don't CSE "cheap" computation if the def is not local or in
312 // an immediate predecessor. We don't want to increase register pressure and
313 // end up causing other computation to be spilled.
Evan Cheng5a96b3d2011-12-07 07:15:52 +0000314 if (MI->isAsCheapAsAMove()) {
Evan Cheng2938a002010-03-10 02:12:03 +0000315 MachineBasicBlock *CSBB = CSMI->getParent();
316 MachineBasicBlock *BB = MI->getParent();
Chris Lattner622a11b2011-01-10 07:51:31 +0000317 if (CSBB != BB && !CSBB->isSuccessor(BB))
Evan Cheng2938a002010-03-10 02:12:03 +0000318 return false;
319 }
320
321 // Heuristics #2: If the expression doesn't not use a vr and the only use
322 // of the redundant computation are copies, do not cse.
323 bool HasVRegUse = false;
324 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
325 const MachineOperand &MO = MI->getOperand(i);
Jakob Stoklund Olesenc9df0252011-01-10 02:58:51 +0000326 if (MO.isReg() && MO.isUse() &&
Evan Cheng2938a002010-03-10 02:12:03 +0000327 TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
328 HasVRegUse = true;
329 break;
330 }
331 }
332 if (!HasVRegUse) {
333 bool HasNonCopyUse = false;
334 for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(Reg),
335 E = MRI->use_nodbg_end(); I != E; ++I) {
336 MachineInstr *Use = &*I;
337 // Ignore copies.
Jakob Stoklund Olesen04c528a2010-07-16 04:45:42 +0000338 if (!Use->isCopyLike()) {
Evan Cheng2938a002010-03-10 02:12:03 +0000339 HasNonCopyUse = true;
340 break;
341 }
342 }
343 if (!HasNonCopyUse)
344 return false;
345 }
346
347 // Heuristics #3: If the common subexpression is used by PHIs, do not reuse
348 // it unless the defined value is already used in the BB of the new use.
Evan Cheng31f94c72010-03-09 03:21:12 +0000349 bool HasPHI = false;
350 SmallPtrSet<MachineBasicBlock*, 4> CSBBs;
Evan Cheng2938a002010-03-10 02:12:03 +0000351 for (MachineRegisterInfo::use_nodbg_iterator I = MRI->use_nodbg_begin(CSReg),
Evan Cheng31f94c72010-03-09 03:21:12 +0000352 E = MRI->use_nodbg_end(); I != E; ++I) {
353 MachineInstr *Use = &*I;
354 HasPHI |= Use->isPHI();
355 CSBBs.insert(Use->getParent());
356 }
357
358 if (!HasPHI)
359 return true;
360 return CSBBs.count(MI->getParent());
361}
362
Evan Cheng31156982010-04-21 00:21:07 +0000363void MachineCSE::EnterScope(MachineBasicBlock *MBB) {
364 DEBUG(dbgs() << "Entering: " << MBB->getName() << '\n');
365 ScopeType *Scope = new ScopeType(VNT);
366 ScopeMap[MBB] = Scope;
367}
368
369void MachineCSE::ExitScope(MachineBasicBlock *MBB) {
370 DEBUG(dbgs() << "Exiting: " << MBB->getName() << '\n');
371 DenseMap<MachineBasicBlock*, ScopeType*>::iterator SI = ScopeMap.find(MBB);
372 assert(SI != ScopeMap.end());
373 ScopeMap.erase(SI);
374 delete SI->second;
375}
376
377bool MachineCSE::ProcessBlock(MachineBasicBlock *MBB) {
Evan Cheng6ba95542010-03-03 02:48:20 +0000378 bool Changed = false;
379
Evan Cheng31f94c72010-03-09 03:21:12 +0000380 SmallVector<std::pair<unsigned, unsigned>, 8> CSEPairs;
Evan Cheng16b48b82010-03-03 21:20:05 +0000381 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) {
Evan Cheng6ba95542010-03-03 02:48:20 +0000382 MachineInstr *MI = &*I;
Evan Cheng16b48b82010-03-03 21:20:05 +0000383 ++I;
Evan Chenga5f32cb2010-03-04 21:18:08 +0000384
385 if (!isCSECandidate(MI))
Evan Cheng6ba95542010-03-03 02:48:20 +0000386 continue;
Evan Cheng6ba95542010-03-03 02:48:20 +0000387
388 bool FoundCSE = VNT.count(MI);
389 if (!FoundCSE) {
390 // Look for trivial copy coalescing opportunities.
Evan Chengdb8771a2010-04-02 02:21:24 +0000391 if (PerformTrivialCoalescing(MI, MBB)) {
Evan Chengcfea9852011-04-11 18:47:20 +0000392 Changed = true;
393
Evan Chengdb8771a2010-04-02 02:21:24 +0000394 // After coalescing MI itself may become a copy.
Jakob Stoklund Olesen04c528a2010-07-16 04:45:42 +0000395 if (MI->isCopyLike())
Evan Chengdb8771a2010-04-02 02:21:24 +0000396 continue;
Evan Cheng6ba95542010-03-03 02:48:20 +0000397 FoundCSE = VNT.count(MI);
Evan Chengdb8771a2010-04-02 02:21:24 +0000398 }
Evan Cheng6ba95542010-03-03 02:48:20 +0000399 }
Evan Chenga63cde22010-12-15 22:16:21 +0000400
401 // Commute commutable instructions.
402 bool Commuted = false;
Evan Cheng5a96b3d2011-12-07 07:15:52 +0000403 if (!FoundCSE && MI->isCommutable()) {
Evan Chenga63cde22010-12-15 22:16:21 +0000404 MachineInstr *NewMI = TII->commuteInstruction(MI);
405 if (NewMI) {
406 Commuted = true;
407 FoundCSE = VNT.count(NewMI);
Evan Chengcfea9852011-04-11 18:47:20 +0000408 if (NewMI != MI) {
Evan Chenga63cde22010-12-15 22:16:21 +0000409 // New instruction. It doesn't need to be kept.
410 NewMI->eraseFromParent();
Evan Chengcfea9852011-04-11 18:47:20 +0000411 Changed = true;
412 } else if (!FoundCSE)
Evan Chenga63cde22010-12-15 22:16:21 +0000413 // MI was changed but it didn't help, commute it back!
414 (void)TII->commuteInstruction(MI);
415 }
416 }
Evan Cheng6ba95542010-03-03 02:48:20 +0000417
Evan Cheng189c1ec2010-10-29 23:36:03 +0000418 // If the instruction defines physical registers and the values *may* be
Evan Cheng67bda722010-03-03 23:59:08 +0000419 // used, then it's not safe to replace it with a common subexpression.
Evan Cheng189c1ec2010-10-29 23:36:03 +0000420 // It's also not safe if the instruction uses physical registers.
Evan Cheng97b5beb2012-01-10 02:02:58 +0000421 bool CrossMBBPhysDef = false;
Evan Cheng189c1ec2010-10-29 23:36:03 +0000422 SmallSet<unsigned,8> PhysRefs;
Evan Cheng97b5beb2012-01-10 02:02:58 +0000423 SmallVector<unsigned, 2> PhysDefs;
424 if (FoundCSE && hasLivePhysRegDefUses(MI, MBB, PhysRefs, PhysDefs)) {
Evan Cheng67bda722010-03-03 23:59:08 +0000425 FoundCSE = false;
426
Evan Cheng97b5beb2012-01-10 02:02:58 +0000427 // ... Unless the CS is local or is in the sole predecessor block
428 // and it also defines the physical register which is not clobbered
429 // in between and the physical register uses were not clobbered.
Evan Cheng189c1ec2010-10-29 23:36:03 +0000430 unsigned CSVN = VNT.lookup(MI);
431 MachineInstr *CSMI = Exps[CSVN];
Evan Cheng97b5beb2012-01-10 02:02:58 +0000432 if (PhysRegDefsReach(CSMI, MI, PhysRefs, CrossMBBPhysDef))
Evan Cheng189c1ec2010-10-29 23:36:03 +0000433 FoundCSE = true;
Evan Cheng835810b2010-05-21 21:22:19 +0000434 }
435
Evan Cheng16b48b82010-03-03 21:20:05 +0000436 if (!FoundCSE) {
437 VNT.insert(MI, CurrVN++);
438 Exps.push_back(MI);
439 continue;
440 }
441
442 // Found a common subexpression, eliminate it.
443 unsigned CSVN = VNT.lookup(MI);
444 MachineInstr *CSMI = Exps[CSVN];
445 DEBUG(dbgs() << "Examining: " << *MI);
446 DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI);
Evan Cheng31f94c72010-03-09 03:21:12 +0000447
448 // Check if it's profitable to perform this CSE.
449 bool DoCSE = true;
Evan Cheng16b48b82010-03-03 21:20:05 +0000450 unsigned NumDefs = MI->getDesc().getNumDefs();
451 for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) {
452 MachineOperand &MO = MI->getOperand(i);
453 if (!MO.isReg() || !MO.isDef())
454 continue;
455 unsigned OldReg = MO.getReg();
456 unsigned NewReg = CSMI->getOperand(i).getReg();
Evan Cheng6cc1aea2010-03-06 01:14:19 +0000457 if (OldReg == NewReg)
458 continue;
Bill Wendlingf6fb7ed2011-10-12 23:03:40 +0000459
Evan Cheng6cc1aea2010-03-06 01:14:19 +0000460 assert(TargetRegisterInfo::isVirtualRegister(OldReg) &&
Evan Cheng16b48b82010-03-03 21:20:05 +0000461 TargetRegisterInfo::isVirtualRegister(NewReg) &&
462 "Do not CSE physical register defs!");
Bill Wendlingf6fb7ed2011-10-12 23:03:40 +0000463
Evan Cheng2938a002010-03-10 02:12:03 +0000464 if (!isProfitableToCSE(NewReg, OldReg, CSMI, MI)) {
Evan Cheng31f94c72010-03-09 03:21:12 +0000465 DoCSE = false;
466 break;
467 }
Bill Wendlingf6fb7ed2011-10-12 23:03:40 +0000468
469 // Don't perform CSE if the result of the old instruction cannot exist
470 // within the register class of the new instruction.
471 const TargetRegisterClass *OldRC = MRI->getRegClass(OldReg);
472 if (!MRI->constrainRegClass(NewReg, OldRC)) {
473 DoCSE = false;
474 break;
475 }
476
Evan Cheng31f94c72010-03-09 03:21:12 +0000477 CSEPairs.push_back(std::make_pair(OldReg, NewReg));
Evan Cheng16b48b82010-03-03 21:20:05 +0000478 --NumDefs;
479 }
Evan Cheng31f94c72010-03-09 03:21:12 +0000480
481 // Actually perform the elimination.
482 if (DoCSE) {
Dan Gohman49b45892010-05-13 19:24:00 +0000483 for (unsigned i = 0, e = CSEPairs.size(); i != e; ++i) {
Evan Cheng31f94c72010-03-09 03:21:12 +0000484 MRI->replaceRegWith(CSEPairs[i].first, CSEPairs[i].second);
Dan Gohman49b45892010-05-13 19:24:00 +0000485 MRI->clearKillFlags(CSEPairs[i].second);
486 }
Evan Cheng97b5beb2012-01-10 02:02:58 +0000487
488 if (CrossMBBPhysDef) {
489 // Add physical register defs now coming in from a predecessor to MBB
490 // livein list.
491 while (!PhysDefs.empty()) {
492 unsigned LiveIn = PhysDefs.pop_back_val();
493 if (!MBB->isLiveIn(LiveIn))
494 MBB->addLiveIn(LiveIn);
495 }
496 ++NumCrossBBCSEs;
497 }
498
Evan Cheng31f94c72010-03-09 03:21:12 +0000499 MI->eraseFromParent();
500 ++NumCSEs;
Evan Cheng189c1ec2010-10-29 23:36:03 +0000501 if (!PhysRefs.empty())
Evan Cheng2b4e7272010-06-04 23:28:13 +0000502 ++NumPhysCSEs;
Evan Chenga63cde22010-12-15 22:16:21 +0000503 if (Commuted)
504 ++NumCommutes;
Evan Chengcfea9852011-04-11 18:47:20 +0000505 Changed = true;
Evan Cheng31f94c72010-03-09 03:21:12 +0000506 } else {
507 DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n");
508 VNT.insert(MI, CurrVN++);
509 Exps.push_back(MI);
510 }
511 CSEPairs.clear();
Evan Cheng6ba95542010-03-03 02:48:20 +0000512 }
513
Evan Cheng31156982010-04-21 00:21:07 +0000514 return Changed;
515}
516
517/// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given
518/// dominator tree node if its a leaf or all of its children are done. Walk
519/// up the dominator tree to destroy ancestors which are now done.
520void
521MachineCSE::ExitScopeIfDone(MachineDomTreeNode *Node,
522 DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren,
523 DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> &ParentMap) {
524 if (OpenChildren[Node])
525 return;
526
527 // Pop scope.
528 ExitScope(Node->getBlock());
529
530 // Now traverse upwards to pop ancestors whose offsprings are all done.
531 while (MachineDomTreeNode *Parent = ParentMap[Node]) {
532 unsigned Left = --OpenChildren[Parent];
533 if (Left != 0)
534 break;
535 ExitScope(Parent->getBlock());
536 Node = Parent;
537 }
538}
539
540bool MachineCSE::PerformCSE(MachineDomTreeNode *Node) {
541 SmallVector<MachineDomTreeNode*, 32> Scopes;
542 SmallVector<MachineDomTreeNode*, 8> WorkList;
543 DenseMap<MachineDomTreeNode*, MachineDomTreeNode*> ParentMap;
544 DenseMap<MachineDomTreeNode*, unsigned> OpenChildren;
545
Evan Chengc2b768f2010-09-17 21:59:42 +0000546 CurrVN = 0;
547
Evan Cheng31156982010-04-21 00:21:07 +0000548 // Perform a DFS walk to determine the order of visit.
549 WorkList.push_back(Node);
550 do {
551 Node = WorkList.pop_back_val();
552 Scopes.push_back(Node);
553 const std::vector<MachineDomTreeNode*> &Children = Node->getChildren();
554 unsigned NumChildren = Children.size();
555 OpenChildren[Node] = NumChildren;
556 for (unsigned i = 0; i != NumChildren; ++i) {
557 MachineDomTreeNode *Child = Children[i];
558 ParentMap[Child] = Node;
559 WorkList.push_back(Child);
560 }
561 } while (!WorkList.empty());
562
563 // Now perform CSE.
564 bool Changed = false;
565 for (unsigned i = 0, e = Scopes.size(); i != e; ++i) {
566 MachineDomTreeNode *Node = Scopes[i];
567 MachineBasicBlock *MBB = Node->getBlock();
568 EnterScope(MBB);
569 Changed |= ProcessBlock(MBB);
570 // If it's a leaf node, it's done. Traverse upwards to pop ancestors.
571 ExitScopeIfDone(Node, OpenChildren, ParentMap);
572 }
Evan Cheng6ba95542010-03-03 02:48:20 +0000573
574 return Changed;
575}
576
Evan Chengc6fe3332010-03-02 02:38:24 +0000577bool MachineCSE::runOnMachineFunction(MachineFunction &MF) {
Evan Cheng6ba95542010-03-03 02:48:20 +0000578 TII = MF.getTarget().getInstrInfo();
Evan Chengb3958e82010-03-04 01:33:55 +0000579 TRI = MF.getTarget().getRegisterInfo();
Evan Cheng6ba95542010-03-03 02:48:20 +0000580 MRI = &MF.getRegInfo();
Evan Chenga5f32cb2010-03-04 21:18:08 +0000581 AA = &getAnalysis<AliasAnalysis>();
Evan Cheng31f94c72010-03-09 03:21:12 +0000582 DT = &getAnalysis<MachineDominatorTree>();
Evan Cheng31156982010-04-21 00:21:07 +0000583 return PerformCSE(DT->getRootNode());
Evan Chengc6fe3332010-03-02 02:38:24 +0000584}