Evan Cheng | c6fe333 | 2010-03-02 02:38:24 +0000 | [diff] [blame] | 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 |
Evan Cheng | c5bbba1 | 2010-03-02 19:02:27 +0000 | [diff] [blame] | 11 | // instructions using a scoped hash table based value numbering scheme. It |
Evan Cheng | c6fe333 | 2010-03-02 02:38:24 +0000 | [diff] [blame] | 12 | // must be run while the machine function is still in SSA form. |
| 13 | // |
| 14 | //===----------------------------------------------------------------------===// |
| 15 | |
Evan Cheng | c6fe333 | 2010-03-02 02:38:24 +0000 | [diff] [blame] | 16 | #include "llvm/CodeGen/Passes.h" |
Evan Cheng | 3115698 | 2010-04-21 00:21:07 +0000 | [diff] [blame] | 17 | #include "llvm/ADT/DenseMap.h" |
Evan Cheng | c6fe333 | 2010-03-02 02:38:24 +0000 | [diff] [blame] | 18 | #include "llvm/ADT/ScopedHashTable.h" |
Evan Cheng | 189c1ec | 2010-10-29 23:36:03 +0000 | [diff] [blame] | 19 | #include "llvm/ADT/SmallSet.h" |
Evan Cheng | c6fe333 | 2010-03-02 02:38:24 +0000 | [diff] [blame] | 20 | #include "llvm/ADT/Statistic.h" |
Chandler Carruth | d04a8d4 | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 21 | #include "llvm/Analysis/AliasAnalysis.h" |
| 22 | #include "llvm/CodeGen/MachineDominators.h" |
| 23 | #include "llvm/CodeGen/MachineInstr.h" |
| 24 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
Evan Cheng | c6fe333 | 2010-03-02 02:38:24 +0000 | [diff] [blame] | 25 | #include "llvm/Support/Debug.h" |
Cameron Zwarich | 53eeba5 | 2011-01-03 04:07:46 +0000 | [diff] [blame] | 26 | #include "llvm/Support/RecyclingAllocator.h" |
Chandler Carruth | d04a8d4 | 2012-12-03 16:50:05 +0000 | [diff] [blame] | 27 | #include "llvm/Target/TargetInstrInfo.h" |
Stephen Hines | 37ed9c1 | 2014-12-01 14:51:49 -0800 | [diff] [blame^] | 28 | #include "llvm/Target/TargetSubtargetInfo.h" |
Evan Cheng | c6fe333 | 2010-03-02 02:38:24 +0000 | [diff] [blame] | 29 | using namespace llvm; |
| 30 | |
Stephen Hines | dce4a40 | 2014-05-29 02:49:00 -0700 | [diff] [blame] | 31 | #define DEBUG_TYPE "machine-cse" |
| 32 | |
Evan Cheng | 16b48b8 | 2010-03-03 21:20:05 +0000 | [diff] [blame] | 33 | STATISTIC(NumCoalesces, "Number of copies coalesced"); |
| 34 | STATISTIC(NumCSEs, "Number of common subexpression eliminated"); |
Evan Cheng | 189c1ec | 2010-10-29 23:36:03 +0000 | [diff] [blame] | 35 | STATISTIC(NumPhysCSEs, |
| 36 | "Number of physreg referencing common subexpr eliminated"); |
Evan Cheng | 97b5beb | 2012-01-10 02:02:58 +0000 | [diff] [blame] | 37 | STATISTIC(NumCrossBBCSEs, |
| 38 | "Number of cross-MBB physreg referencing CS eliminated"); |
Evan Cheng | a63cde2 | 2010-12-15 22:16:21 +0000 | [diff] [blame] | 39 | STATISTIC(NumCommutes, "Number of copies coalesced after commuting"); |
Bob Wilson | 3844173 | 2010-06-03 18:28:31 +0000 | [diff] [blame] | 40 | |
Evan Cheng | c6fe333 | 2010-03-02 02:38:24 +0000 | [diff] [blame] | 41 | namespace { |
| 42 | class MachineCSE : public MachineFunctionPass { |
Evan Cheng | 6ba9554 | 2010-03-03 02:48:20 +0000 | [diff] [blame] | 43 | const TargetInstrInfo *TII; |
Evan Cheng | b3958e8 | 2010-03-04 01:33:55 +0000 | [diff] [blame] | 44 | const TargetRegisterInfo *TRI; |
Evan Cheng | a5f32cb | 2010-03-04 21:18:08 +0000 | [diff] [blame] | 45 | AliasAnalysis *AA; |
Evan Cheng | 31f94c7 | 2010-03-09 03:21:12 +0000 | [diff] [blame] | 46 | MachineDominatorTree *DT; |
| 47 | MachineRegisterInfo *MRI; |
Evan Cheng | c6fe333 | 2010-03-02 02:38:24 +0000 | [diff] [blame] | 48 | public: |
| 49 | static char ID; // Pass identification |
Owen Anderson | 081c34b | 2010-10-19 17:21:58 +0000 | [diff] [blame] | 50 | MachineCSE() : MachineFunctionPass(ID), LookAheadLimit(5), CurrVN(0) { |
| 51 | initializeMachineCSEPass(*PassRegistry::getPassRegistry()); |
| 52 | } |
Evan Cheng | c6fe333 | 2010-03-02 02:38:24 +0000 | [diff] [blame] | 53 | |
Stephen Hines | 36b5688 | 2014-04-23 16:57:46 -0700 | [diff] [blame] | 54 | bool runOnMachineFunction(MachineFunction &MF) override; |
Andrew Trick | 1df91b0 | 2012-02-08 21:22:43 +0000 | [diff] [blame] | 55 | |
Stephen Hines | 36b5688 | 2014-04-23 16:57:46 -0700 | [diff] [blame] | 56 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
Evan Cheng | c6fe333 | 2010-03-02 02:38:24 +0000 | [diff] [blame] | 57 | AU.setPreservesCFG(); |
| 58 | MachineFunctionPass::getAnalysisUsage(AU); |
Evan Cheng | a5f32cb | 2010-03-04 21:18:08 +0000 | [diff] [blame] | 59 | AU.addRequired<AliasAnalysis>(); |
Evan Cheng | 6542416 | 2010-08-17 20:57:42 +0000 | [diff] [blame] | 60 | AU.addPreservedID(MachineLoopInfoID); |
Evan Cheng | c6fe333 | 2010-03-02 02:38:24 +0000 | [diff] [blame] | 61 | AU.addRequired<MachineDominatorTree>(); |
| 62 | AU.addPreserved<MachineDominatorTree>(); |
| 63 | } |
| 64 | |
Stephen Hines | 36b5688 | 2014-04-23 16:57:46 -0700 | [diff] [blame] | 65 | void releaseMemory() override { |
Evan Cheng | c2b768f | 2010-09-17 21:59:42 +0000 | [diff] [blame] | 66 | ScopeMap.clear(); |
| 67 | Exps.clear(); |
| 68 | } |
| 69 | |
Evan Cheng | c6fe333 | 2010-03-02 02:38:24 +0000 | [diff] [blame] | 70 | private: |
Evan Cheng | 835810b | 2010-05-21 21:22:19 +0000 | [diff] [blame] | 71 | const unsigned LookAheadLimit; |
Cameron Zwarich | 53eeba5 | 2011-01-03 04:07:46 +0000 | [diff] [blame] | 72 | typedef RecyclingAllocator<BumpPtrAllocator, |
| 73 | ScopedHashTableVal<MachineInstr*, unsigned> > AllocatorTy; |
| 74 | typedef ScopedHashTable<MachineInstr*, unsigned, |
| 75 | MachineInstrExpressionTrait, AllocatorTy> ScopedHTType; |
| 76 | typedef ScopedHTType::ScopeTy ScopeType; |
Evan Cheng | 3115698 | 2010-04-21 00:21:07 +0000 | [diff] [blame] | 77 | DenseMap<MachineBasicBlock*, ScopeType*> ScopeMap; |
Cameron Zwarich | 53eeba5 | 2011-01-03 04:07:46 +0000 | [diff] [blame] | 78 | ScopedHTType VNT; |
Evan Cheng | 16b48b8 | 2010-03-03 21:20:05 +0000 | [diff] [blame] | 79 | SmallVector<MachineInstr*, 64> Exps; |
Evan Cheng | 3115698 | 2010-04-21 00:21:07 +0000 | [diff] [blame] | 80 | unsigned CurrVN; |
Evan Cheng | 16b48b8 | 2010-03-03 21:20:05 +0000 | [diff] [blame] | 81 | |
Stephen Hines | 37ed9c1 | 2014-12-01 14:51:49 -0800 | [diff] [blame^] | 82 | bool PerformTrivialCopyPropagation(MachineInstr *MI, |
| 83 | MachineBasicBlock *MBB); |
Evan Cheng | b3958e8 | 2010-03-04 01:33:55 +0000 | [diff] [blame] | 84 | bool isPhysDefTriviallyDead(unsigned Reg, |
| 85 | MachineBasicBlock::const_iterator I, |
Nick Lewycky | 7a7a6db | 2012-07-05 06:19:21 +0000 | [diff] [blame] | 86 | MachineBasicBlock::const_iterator E) const; |
Evan Cheng | 189c1ec | 2010-10-29 23:36:03 +0000 | [diff] [blame] | 87 | bool hasLivePhysRegDefUses(const MachineInstr *MI, |
| 88 | const MachineBasicBlock *MBB, |
Evan Cheng | 97b5beb | 2012-01-10 02:02:58 +0000 | [diff] [blame] | 89 | SmallSet<unsigned,8> &PhysRefs, |
Craig Topper | a0ec3f9 | 2013-07-14 04:42:23 +0000 | [diff] [blame] | 90 | SmallVectorImpl<unsigned> &PhysDefs, |
Ulrich Weigand | b64e211 | 2012-11-13 18:40:58 +0000 | [diff] [blame] | 91 | bool &PhysUseDef) const; |
Evan Cheng | 189c1ec | 2010-10-29 23:36:03 +0000 | [diff] [blame] | 92 | bool PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI, |
Evan Cheng | 97b5beb | 2012-01-10 02:02:58 +0000 | [diff] [blame] | 93 | SmallSet<unsigned,8> &PhysRefs, |
Craig Topper | a0ec3f9 | 2013-07-14 04:42:23 +0000 | [diff] [blame] | 94 | SmallVectorImpl<unsigned> &PhysDefs, |
Evan Cheng | 97b5beb | 2012-01-10 02:02:58 +0000 | [diff] [blame] | 95 | bool &NonLocal) const; |
Evan Cheng | a5f32cb | 2010-03-04 21:18:08 +0000 | [diff] [blame] | 96 | bool isCSECandidate(MachineInstr *MI); |
Evan Cheng | 2938a00 | 2010-03-10 02:12:03 +0000 | [diff] [blame] | 97 | bool isProfitableToCSE(unsigned CSReg, unsigned Reg, |
| 98 | MachineInstr *CSMI, MachineInstr *MI); |
Evan Cheng | 3115698 | 2010-04-21 00:21:07 +0000 | [diff] [blame] | 99 | void EnterScope(MachineBasicBlock *MBB); |
| 100 | void ExitScope(MachineBasicBlock *MBB); |
| 101 | bool ProcessBlock(MachineBasicBlock *MBB); |
| 102 | void ExitScopeIfDone(MachineDomTreeNode *Node, |
Bill Wendling | 96cb112 | 2012-07-19 00:04:14 +0000 | [diff] [blame] | 103 | DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren); |
Evan Cheng | 3115698 | 2010-04-21 00:21:07 +0000 | [diff] [blame] | 104 | bool PerformCSE(MachineDomTreeNode *Node); |
Evan Cheng | c6fe333 | 2010-03-02 02:38:24 +0000 | [diff] [blame] | 105 | }; |
| 106 | } // end anonymous namespace |
| 107 | |
| 108 | char MachineCSE::ID = 0; |
Andrew Trick | 1dd8c85 | 2012-02-08 21:23:13 +0000 | [diff] [blame] | 109 | char &llvm::MachineCSEID = MachineCSE::ID; |
Owen Anderson | 2ab36d3 | 2010-10-12 19:48:12 +0000 | [diff] [blame] | 110 | INITIALIZE_PASS_BEGIN(MachineCSE, "machine-cse", |
| 111 | "Machine Common Subexpression Elimination", false, false) |
| 112 | INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) |
| 113 | INITIALIZE_AG_DEPENDENCY(AliasAnalysis) |
| 114 | INITIALIZE_PASS_END(MachineCSE, "machine-cse", |
Owen Anderson | ce665bd | 2010-10-07 22:25:06 +0000 | [diff] [blame] | 115 | "Machine Common Subexpression Elimination", false, false) |
Evan Cheng | c6fe333 | 2010-03-02 02:38:24 +0000 | [diff] [blame] | 116 | |
Stephen Hines | 37ed9c1 | 2014-12-01 14:51:49 -0800 | [diff] [blame^] | 117 | /// The source register of a COPY machine instruction can be propagated to all |
| 118 | /// its users, and this propagation could increase the probability of finding |
| 119 | /// common subexpressions. If the COPY has only one user, the COPY itself can |
| 120 | /// be removed. |
| 121 | bool MachineCSE::PerformTrivialCopyPropagation(MachineInstr *MI, |
| 122 | MachineBasicBlock *MBB) { |
Evan Cheng | 6ba9554 | 2010-03-03 02:48:20 +0000 | [diff] [blame] | 123 | bool Changed = false; |
| 124 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 125 | MachineOperand &MO = MI->getOperand(i); |
Evan Cheng | 16b48b8 | 2010-03-03 21:20:05 +0000 | [diff] [blame] | 126 | if (!MO.isReg() || !MO.isUse()) |
| 127 | continue; |
| 128 | unsigned Reg = MO.getReg(); |
Jakob Stoklund Olesen | c9df025 | 2011-01-10 02:58:51 +0000 | [diff] [blame] | 129 | if (!TargetRegisterInfo::isVirtualRegister(Reg)) |
Evan Cheng | 16b48b8 | 2010-03-03 21:20:05 +0000 | [diff] [blame] | 130 | continue; |
Stephen Hines | 37ed9c1 | 2014-12-01 14:51:49 -0800 | [diff] [blame^] | 131 | bool OnlyOneUse = MRI->hasOneNonDBGUse(Reg); |
Evan Cheng | 16b48b8 | 2010-03-03 21:20:05 +0000 | [diff] [blame] | 132 | MachineInstr *DefMI = MRI->getVRegDef(Reg); |
Jakob Stoklund Olesen | 0bc25f4 | 2010-07-08 16:40:22 +0000 | [diff] [blame] | 133 | if (!DefMI->isCopy()) |
| 134 | continue; |
Jakob Stoklund Olesen | 04c528a | 2010-07-16 04:45:42 +0000 | [diff] [blame] | 135 | unsigned SrcReg = DefMI->getOperand(1).getReg(); |
Jakob Stoklund Olesen | 0bc25f4 | 2010-07-08 16:40:22 +0000 | [diff] [blame] | 136 | if (!TargetRegisterInfo::isVirtualRegister(SrcReg)) |
| 137 | continue; |
Stephen Hines | 36b5688 | 2014-04-23 16:57:46 -0700 | [diff] [blame] | 138 | if (DefMI->getOperand(0).getSubReg()) |
Jakob Stoklund Olesen | 0bc25f4 | 2010-07-08 16:40:22 +0000 | [diff] [blame] | 139 | continue; |
Stephen Hines | 36b5688 | 2014-04-23 16:57:46 -0700 | [diff] [blame] | 140 | // FIXME: We should trivially coalesce subregister copies to expose CSE |
| 141 | // opportunities on instructions with truncated operands (see |
| 142 | // cse-add-with-overflow.ll). This can be done here as follows: |
| 143 | // if (SrcSubReg) |
| 144 | // RC = TRI->getMatchingSuperRegClass(MRI->getRegClass(SrcReg), RC, |
| 145 | // SrcSubReg); |
| 146 | // MO.substVirtReg(SrcReg, SrcSubReg, *TRI); |
| 147 | // |
| 148 | // The 2-addr pass has been updated to handle coalesced subregs. However, |
| 149 | // some machine-specific code still can't handle it. |
| 150 | // To handle it properly we also need a way find a constrained subregister |
| 151 | // class given a super-reg class and subreg index. |
| 152 | if (DefMI->getOperand(1).getSubReg()) |
| 153 | continue; |
| 154 | const TargetRegisterClass *RC = MRI->getRegClass(Reg); |
| 155 | if (!MRI->constrainRegClass(SrcReg, RC)) |
Jakob Stoklund Olesen | 0bc25f4 | 2010-07-08 16:40:22 +0000 | [diff] [blame] | 156 | continue; |
| 157 | DEBUG(dbgs() << "Coalescing: " << *DefMI); |
Jakob Stoklund Olesen | bf4699c | 2010-10-06 23:54:39 +0000 | [diff] [blame] | 158 | DEBUG(dbgs() << "*** to: " << *MI); |
Stephen Hines | 37ed9c1 | 2014-12-01 14:51:49 -0800 | [diff] [blame^] | 159 | // Propagate SrcReg of copies to MI. |
Jakob Stoklund Olesen | 0bc25f4 | 2010-07-08 16:40:22 +0000 | [diff] [blame] | 160 | MO.setReg(SrcReg); |
| 161 | MRI->clearKillFlags(SrcReg); |
Stephen Hines | 37ed9c1 | 2014-12-01 14:51:49 -0800 | [diff] [blame^] | 162 | // Coalesce single use copies. |
| 163 | if (OnlyOneUse) { |
| 164 | DefMI->eraseFromParent(); |
| 165 | ++NumCoalesces; |
| 166 | } |
Jakob Stoklund Olesen | 0bc25f4 | 2010-07-08 16:40:22 +0000 | [diff] [blame] | 167 | Changed = true; |
Evan Cheng | 6ba9554 | 2010-03-03 02:48:20 +0000 | [diff] [blame] | 168 | } |
| 169 | |
| 170 | return Changed; |
| 171 | } |
| 172 | |
Evan Cheng | 835810b | 2010-05-21 21:22:19 +0000 | [diff] [blame] | 173 | bool |
| 174 | MachineCSE::isPhysDefTriviallyDead(unsigned Reg, |
| 175 | MachineBasicBlock::const_iterator I, |
| 176 | MachineBasicBlock::const_iterator E) const { |
Eric Christopher | e81d010 | 2010-05-21 23:40:03 +0000 | [diff] [blame] | 177 | unsigned LookAheadLeft = LookAheadLimit; |
Evan Cheng | 112e5e7 | 2010-03-23 20:33:48 +0000 | [diff] [blame] | 178 | while (LookAheadLeft) { |
Evan Cheng | 2250425 | 2010-03-24 01:50:28 +0000 | [diff] [blame] | 179 | // Skip over dbg_value's. |
| 180 | while (I != E && I->isDebugValue()) |
| 181 | ++I; |
| 182 | |
Evan Cheng | b3958e8 | 2010-03-04 01:33:55 +0000 | [diff] [blame] | 183 | if (I == E) |
| 184 | // Reached end of block, register is obviously dead. |
| 185 | return true; |
| 186 | |
Evan Cheng | b3958e8 | 2010-03-04 01:33:55 +0000 | [diff] [blame] | 187 | bool SeenDef = false; |
| 188 | for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { |
| 189 | const MachineOperand &MO = I->getOperand(i); |
Jakob Stoklund Olesen | 2129a0f | 2012-02-28 02:08:50 +0000 | [diff] [blame] | 190 | if (MO.isRegMask() && MO.clobbersPhysReg(Reg)) |
| 191 | SeenDef = true; |
Evan Cheng | b3958e8 | 2010-03-04 01:33:55 +0000 | [diff] [blame] | 192 | if (!MO.isReg() || !MO.getReg()) |
| 193 | continue; |
| 194 | if (!TRI->regsOverlap(MO.getReg(), Reg)) |
| 195 | continue; |
| 196 | if (MO.isUse()) |
Evan Cheng | 835810b | 2010-05-21 21:22:19 +0000 | [diff] [blame] | 197 | // Found a use! |
Evan Cheng | b3958e8 | 2010-03-04 01:33:55 +0000 | [diff] [blame] | 198 | return false; |
| 199 | SeenDef = true; |
| 200 | } |
| 201 | if (SeenDef) |
Andrew Trick | 1df91b0 | 2012-02-08 21:22:43 +0000 | [diff] [blame] | 202 | // See a def of Reg (or an alias) before encountering any use, it's |
Evan Cheng | b3958e8 | 2010-03-04 01:33:55 +0000 | [diff] [blame] | 203 | // trivially dead. |
| 204 | return true; |
Evan Cheng | 112e5e7 | 2010-03-23 20:33:48 +0000 | [diff] [blame] | 205 | |
| 206 | --LookAheadLeft; |
Evan Cheng | b3958e8 | 2010-03-04 01:33:55 +0000 | [diff] [blame] | 207 | ++I; |
| 208 | } |
| 209 | return false; |
| 210 | } |
| 211 | |
Evan Cheng | 189c1ec | 2010-10-29 23:36:03 +0000 | [diff] [blame] | 212 | /// hasLivePhysRegDefUses - Return true if the specified instruction read/write |
Evan Cheng | 835810b | 2010-05-21 21:22:19 +0000 | [diff] [blame] | 213 | /// physical registers (except for dead defs of physical registers). It also |
Evan Cheng | 2b4e727 | 2010-06-04 23:28:13 +0000 | [diff] [blame] | 214 | /// returns the physical register def by reference if it's the only one and the |
| 215 | /// instruction does not uses a physical register. |
Evan Cheng | 189c1ec | 2010-10-29 23:36:03 +0000 | [diff] [blame] | 216 | bool MachineCSE::hasLivePhysRegDefUses(const MachineInstr *MI, |
| 217 | const MachineBasicBlock *MBB, |
Evan Cheng | 97b5beb | 2012-01-10 02:02:58 +0000 | [diff] [blame] | 218 | SmallSet<unsigned,8> &PhysRefs, |
Craig Topper | a0ec3f9 | 2013-07-14 04:42:23 +0000 | [diff] [blame] | 219 | SmallVectorImpl<unsigned> &PhysDefs, |
Ulrich Weigand | b64e211 | 2012-11-13 18:40:58 +0000 | [diff] [blame] | 220 | bool &PhysUseDef) const{ |
| 221 | // First, add all uses to PhysRefs. |
Evan Cheng | 6ba9554 | 2010-03-03 02:48:20 +0000 | [diff] [blame] | 222 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
Evan Cheng | 835810b | 2010-05-21 21:22:19 +0000 | [diff] [blame] | 223 | const MachineOperand &MO = MI->getOperand(i); |
Ulrich Weigand | b64e211 | 2012-11-13 18:40:58 +0000 | [diff] [blame] | 224 | if (!MO.isReg() || MO.isDef()) |
Evan Cheng | 6ba9554 | 2010-03-03 02:48:20 +0000 | [diff] [blame] | 225 | continue; |
| 226 | unsigned Reg = MO.getReg(); |
| 227 | if (!Reg) |
| 228 | continue; |
Evan Cheng | 835810b | 2010-05-21 21:22:19 +0000 | [diff] [blame] | 229 | if (TargetRegisterInfo::isVirtualRegister(Reg)) |
| 230 | continue; |
Benjamin Kramer | 5fa2d45 | 2012-08-11 20:42:59 +0000 | [diff] [blame] | 231 | // Reading constant physregs is ok. |
| 232 | if (!MRI->isConstantPhysReg(Reg, *MBB->getParent())) |
| 233 | for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) |
Benjamin Kramer | cfc0ad6 | 2012-08-11 19:05:13 +0000 | [diff] [blame] | 234 | PhysRefs.insert(*AI); |
Ulrich Weigand | b64e211 | 2012-11-13 18:40:58 +0000 | [diff] [blame] | 235 | } |
| 236 | |
| 237 | // Next, collect all defs into PhysDefs. If any is already in PhysRefs |
| 238 | // (which currently contains only uses), set the PhysUseDef flag. |
| 239 | PhysUseDef = false; |
Stephen Hines | 36b5688 | 2014-04-23 16:57:46 -0700 | [diff] [blame] | 240 | MachineBasicBlock::const_iterator I = MI; I = std::next(I); |
Ulrich Weigand | b64e211 | 2012-11-13 18:40:58 +0000 | [diff] [blame] | 241 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 242 | const MachineOperand &MO = MI->getOperand(i); |
| 243 | if (!MO.isReg() || !MO.isDef()) |
| 244 | continue; |
| 245 | unsigned Reg = MO.getReg(); |
| 246 | if (!Reg) |
| 247 | continue; |
| 248 | if (TargetRegisterInfo::isVirtualRegister(Reg)) |
| 249 | continue; |
| 250 | // Check against PhysRefs even if the def is "dead". |
| 251 | if (PhysRefs.count(Reg)) |
| 252 | PhysUseDef = true; |
| 253 | // If the def is dead, it's ok. But the def may not marked "dead". That's |
| 254 | // common since this pass is run before livevariables. We can scan |
| 255 | // forward a few instructions and check if it is obviously dead. |
| 256 | if (!MO.isDead() && !isPhysDefTriviallyDead(Reg, I, MBB->end())) |
Evan Cheng | 97b5beb | 2012-01-10 02:02:58 +0000 | [diff] [blame] | 257 | PhysDefs.push_back(Reg); |
Evan Cheng | b3958e8 | 2010-03-04 01:33:55 +0000 | [diff] [blame] | 258 | } |
| 259 | |
Ulrich Weigand | b64e211 | 2012-11-13 18:40:58 +0000 | [diff] [blame] | 260 | // Finally, add all defs to PhysRefs as well. |
| 261 | for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) |
| 262 | for (MCRegAliasIterator AI(PhysDefs[i], TRI, true); AI.isValid(); ++AI) |
| 263 | PhysRefs.insert(*AI); |
| 264 | |
Evan Cheng | 189c1ec | 2010-10-29 23:36:03 +0000 | [diff] [blame] | 265 | return !PhysRefs.empty(); |
Evan Cheng | c6fe333 | 2010-03-02 02:38:24 +0000 | [diff] [blame] | 266 | } |
| 267 | |
Evan Cheng | 189c1ec | 2010-10-29 23:36:03 +0000 | [diff] [blame] | 268 | bool MachineCSE::PhysRegDefsReach(MachineInstr *CSMI, MachineInstr *MI, |
Evan Cheng | 97b5beb | 2012-01-10 02:02:58 +0000 | [diff] [blame] | 269 | SmallSet<unsigned,8> &PhysRefs, |
Craig Topper | a0ec3f9 | 2013-07-14 04:42:23 +0000 | [diff] [blame] | 270 | SmallVectorImpl<unsigned> &PhysDefs, |
Evan Cheng | 97b5beb | 2012-01-10 02:02:58 +0000 | [diff] [blame] | 271 | bool &NonLocal) const { |
Eli Friedman | 5e926ac | 2011-05-06 05:23:07 +0000 | [diff] [blame] | 272 | // For now conservatively returns false if the common subexpression is |
Evan Cheng | 97b5beb | 2012-01-10 02:02:58 +0000 | [diff] [blame] | 273 | // not in the same basic block as the given instruction. The only exception |
| 274 | // is if the common subexpression is in the sole predecessor block. |
| 275 | const MachineBasicBlock *MBB = MI->getParent(); |
| 276 | const MachineBasicBlock *CSMBB = CSMI->getParent(); |
| 277 | |
| 278 | bool CrossMBB = false; |
| 279 | if (CSMBB != MBB) { |
Evan Cheng | f96703e | 2012-01-11 00:38:11 +0000 | [diff] [blame] | 280 | if (MBB->pred_size() != 1 || *MBB->pred_begin() != CSMBB) |
Evan Cheng | 97b5beb | 2012-01-10 02:02:58 +0000 | [diff] [blame] | 281 | return false; |
Evan Cheng | f96703e | 2012-01-11 00:38:11 +0000 | [diff] [blame] | 282 | |
| 283 | for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) { |
Jakob Stoklund Olesen | fb9ebbf | 2012-10-15 21:57:41 +0000 | [diff] [blame] | 284 | if (MRI->isAllocatable(PhysDefs[i]) || MRI->isReserved(PhysDefs[i])) |
Lang Hames | c2e08db | 2012-02-17 00:27:16 +0000 | [diff] [blame] | 285 | // Avoid extending live range of physical registers if they are |
| 286 | //allocatable or reserved. |
Evan Cheng | f96703e | 2012-01-11 00:38:11 +0000 | [diff] [blame] | 287 | return false; |
| 288 | } |
| 289 | CrossMBB = true; |
Evan Cheng | 97b5beb | 2012-01-10 02:02:58 +0000 | [diff] [blame] | 290 | } |
Stephen Hines | 36b5688 | 2014-04-23 16:57:46 -0700 | [diff] [blame] | 291 | MachineBasicBlock::const_iterator I = CSMI; I = std::next(I); |
Eli Friedman | 5e926ac | 2011-05-06 05:23:07 +0000 | [diff] [blame] | 292 | MachineBasicBlock::const_iterator E = MI; |
Evan Cheng | 97b5beb | 2012-01-10 02:02:58 +0000 | [diff] [blame] | 293 | MachineBasicBlock::const_iterator EE = CSMBB->end(); |
Evan Cheng | 835810b | 2010-05-21 21:22:19 +0000 | [diff] [blame] | 294 | unsigned LookAheadLeft = LookAheadLimit; |
| 295 | while (LookAheadLeft) { |
Eli Friedman | 5e926ac | 2011-05-06 05:23:07 +0000 | [diff] [blame] | 296 | // Skip over dbg_value's. |
Evan Cheng | 97b5beb | 2012-01-10 02:02:58 +0000 | [diff] [blame] | 297 | while (I != E && I != EE && I->isDebugValue()) |
Evan Cheng | 835810b | 2010-05-21 21:22:19 +0000 | [diff] [blame] | 298 | ++I; |
Eli Friedman | 5e926ac | 2011-05-06 05:23:07 +0000 | [diff] [blame] | 299 | |
Evan Cheng | 97b5beb | 2012-01-10 02:02:58 +0000 | [diff] [blame] | 300 | if (I == EE) { |
| 301 | assert(CrossMBB && "Reaching end-of-MBB without finding MI?"); |
Duncan Sands | 5b8a1db | 2012-02-05 14:20:11 +0000 | [diff] [blame] | 302 | (void)CrossMBB; |
Evan Cheng | 97b5beb | 2012-01-10 02:02:58 +0000 | [diff] [blame] | 303 | CrossMBB = false; |
| 304 | NonLocal = true; |
| 305 | I = MBB->begin(); |
| 306 | EE = MBB->end(); |
| 307 | continue; |
| 308 | } |
| 309 | |
Eli Friedman | 5e926ac | 2011-05-06 05:23:07 +0000 | [diff] [blame] | 310 | if (I == E) |
| 311 | return true; |
| 312 | |
| 313 | for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { |
| 314 | const MachineOperand &MO = I->getOperand(i); |
Jakob Stoklund Olesen | 2129a0f | 2012-02-28 02:08:50 +0000 | [diff] [blame] | 315 | // RegMasks go on instructions like calls that clobber lots of physregs. |
| 316 | // Don't attempt to CSE across such an instruction. |
| 317 | if (MO.isRegMask()) |
| 318 | return false; |
Eli Friedman | 5e926ac | 2011-05-06 05:23:07 +0000 | [diff] [blame] | 319 | if (!MO.isReg() || !MO.isDef()) |
| 320 | continue; |
| 321 | unsigned MOReg = MO.getReg(); |
| 322 | if (TargetRegisterInfo::isVirtualRegister(MOReg)) |
| 323 | continue; |
| 324 | if (PhysRefs.count(MOReg)) |
| 325 | return false; |
Evan Cheng | 189c1ec | 2010-10-29 23:36:03 +0000 | [diff] [blame] | 326 | } |
Eli Friedman | 5e926ac | 2011-05-06 05:23:07 +0000 | [diff] [blame] | 327 | |
| 328 | --LookAheadLeft; |
| 329 | ++I; |
Evan Cheng | 835810b | 2010-05-21 21:22:19 +0000 | [diff] [blame] | 330 | } |
| 331 | |
| 332 | return false; |
| 333 | } |
| 334 | |
Evan Cheng | a5f32cb | 2010-03-04 21:18:08 +0000 | [diff] [blame] | 335 | bool MachineCSE::isCSECandidate(MachineInstr *MI) { |
Stephen Hines | 36b5688 | 2014-04-23 16:57:46 -0700 | [diff] [blame] | 336 | if (MI->isPosition() || MI->isPHI() || MI->isImplicitDef() || MI->isKill() || |
| 337 | MI->isInlineAsm() || MI->isDebugValue()) |
Evan Cheng | 5196018 | 2010-03-08 23:49:12 +0000 | [diff] [blame] | 338 | return false; |
| 339 | |
Evan Cheng | 2938a00 | 2010-03-10 02:12:03 +0000 | [diff] [blame] | 340 | // Ignore copies. |
Jakob Stoklund Olesen | 04c528a | 2010-07-16 04:45:42 +0000 | [diff] [blame] | 341 | if (MI->isCopyLike()) |
Evan Cheng | a5f32cb | 2010-03-04 21:18:08 +0000 | [diff] [blame] | 342 | return false; |
| 343 | |
| 344 | // Ignore stuff that we obviously can't move. |
Evan Cheng | 5a96b3d | 2011-12-07 07:15:52 +0000 | [diff] [blame] | 345 | if (MI->mayStore() || MI->isCall() || MI->isTerminator() || |
Evan Cheng | c36b706 | 2011-01-07 23:50:32 +0000 | [diff] [blame] | 346 | MI->hasUnmodeledSideEffects()) |
Evan Cheng | a5f32cb | 2010-03-04 21:18:08 +0000 | [diff] [blame] | 347 | return false; |
| 348 | |
Evan Cheng | 5a96b3d | 2011-12-07 07:15:52 +0000 | [diff] [blame] | 349 | if (MI->mayLoad()) { |
Evan Cheng | a5f32cb | 2010-03-04 21:18:08 +0000 | [diff] [blame] | 350 | // Okay, this instruction does a load. As a refinement, we allow the target |
| 351 | // to decide whether the loaded value is actually a constant. If so, we can |
| 352 | // actually use it as a load. |
| 353 | if (!MI->isInvariantLoad(AA)) |
| 354 | // FIXME: we should be able to hoist loads with no other side effects if |
| 355 | // there are no other instructions which can change memory in this loop. |
| 356 | // This is a trivial form of alias analysis. |
| 357 | return false; |
| 358 | } |
| 359 | return true; |
| 360 | } |
| 361 | |
Evan Cheng | 31f94c7 | 2010-03-09 03:21:12 +0000 | [diff] [blame] | 362 | /// isProfitableToCSE - Return true if it's profitable to eliminate MI with a |
| 363 | /// common expression that defines Reg. |
Evan Cheng | 2938a00 | 2010-03-10 02:12:03 +0000 | [diff] [blame] | 364 | bool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg, |
| 365 | MachineInstr *CSMI, MachineInstr *MI) { |
| 366 | // FIXME: Heuristics that works around the lack the live range splitting. |
| 367 | |
Manman Ren | ba86b13 | 2012-08-07 06:16:46 +0000 | [diff] [blame] | 368 | // If CSReg is used at all uses of Reg, CSE should not increase register |
| 369 | // pressure of CSReg. |
| 370 | bool MayIncreasePressure = true; |
| 371 | if (TargetRegisterInfo::isVirtualRegister(CSReg) && |
| 372 | TargetRegisterInfo::isVirtualRegister(Reg)) { |
| 373 | MayIncreasePressure = false; |
| 374 | SmallPtrSet<MachineInstr*, 8> CSUses; |
Stephen Hines | 36b5688 | 2014-04-23 16:57:46 -0700 | [diff] [blame] | 375 | for (MachineInstr &MI : MRI->use_nodbg_instructions(CSReg)) { |
| 376 | CSUses.insert(&MI); |
Manman Ren | ba86b13 | 2012-08-07 06:16:46 +0000 | [diff] [blame] | 377 | } |
Stephen Hines | 36b5688 | 2014-04-23 16:57:46 -0700 | [diff] [blame] | 378 | for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) { |
| 379 | if (!CSUses.count(&MI)) { |
Manman Ren | ba86b13 | 2012-08-07 06:16:46 +0000 | [diff] [blame] | 380 | MayIncreasePressure = true; |
| 381 | break; |
| 382 | } |
| 383 | } |
| 384 | } |
| 385 | if (!MayIncreasePressure) return true; |
| 386 | |
Chris Lattner | 622a11b | 2011-01-10 07:51:31 +0000 | [diff] [blame] | 387 | // Heuristics #1: Don't CSE "cheap" computation if the def is not local or in |
| 388 | // an immediate predecessor. We don't want to increase register pressure and |
| 389 | // end up causing other computation to be spilled. |
Stephen Hines | bfc2d68 | 2014-10-17 08:47:43 -0700 | [diff] [blame] | 390 | if (TII->isAsCheapAsAMove(MI)) { |
Evan Cheng | 2938a00 | 2010-03-10 02:12:03 +0000 | [diff] [blame] | 391 | MachineBasicBlock *CSBB = CSMI->getParent(); |
| 392 | MachineBasicBlock *BB = MI->getParent(); |
Chris Lattner | 622a11b | 2011-01-10 07:51:31 +0000 | [diff] [blame] | 393 | if (CSBB != BB && !CSBB->isSuccessor(BB)) |
Evan Cheng | 2938a00 | 2010-03-10 02:12:03 +0000 | [diff] [blame] | 394 | return false; |
| 395 | } |
| 396 | |
| 397 | // Heuristics #2: If the expression doesn't not use a vr and the only use |
| 398 | // of the redundant computation are copies, do not cse. |
| 399 | bool HasVRegUse = false; |
| 400 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 401 | const MachineOperand &MO = MI->getOperand(i); |
Jakob Stoklund Olesen | c9df025 | 2011-01-10 02:58:51 +0000 | [diff] [blame] | 402 | if (MO.isReg() && MO.isUse() && |
Evan Cheng | 2938a00 | 2010-03-10 02:12:03 +0000 | [diff] [blame] | 403 | TargetRegisterInfo::isVirtualRegister(MO.getReg())) { |
| 404 | HasVRegUse = true; |
| 405 | break; |
| 406 | } |
| 407 | } |
| 408 | if (!HasVRegUse) { |
| 409 | bool HasNonCopyUse = false; |
Stephen Hines | 36b5688 | 2014-04-23 16:57:46 -0700 | [diff] [blame] | 410 | for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) { |
Evan Cheng | 2938a00 | 2010-03-10 02:12:03 +0000 | [diff] [blame] | 411 | // Ignore copies. |
Stephen Hines | 36b5688 | 2014-04-23 16:57:46 -0700 | [diff] [blame] | 412 | if (!MI.isCopyLike()) { |
Evan Cheng | 2938a00 | 2010-03-10 02:12:03 +0000 | [diff] [blame] | 413 | HasNonCopyUse = true; |
| 414 | break; |
| 415 | } |
| 416 | } |
| 417 | if (!HasNonCopyUse) |
| 418 | return false; |
| 419 | } |
| 420 | |
| 421 | // Heuristics #3: If the common subexpression is used by PHIs, do not reuse |
| 422 | // it unless the defined value is already used in the BB of the new use. |
Evan Cheng | 31f94c7 | 2010-03-09 03:21:12 +0000 | [diff] [blame] | 423 | bool HasPHI = false; |
| 424 | SmallPtrSet<MachineBasicBlock*, 4> CSBBs; |
Stephen Hines | 36b5688 | 2014-04-23 16:57:46 -0700 | [diff] [blame] | 425 | for (MachineInstr &MI : MRI->use_nodbg_instructions(CSReg)) { |
| 426 | HasPHI |= MI.isPHI(); |
| 427 | CSBBs.insert(MI.getParent()); |
Evan Cheng | 31f94c7 | 2010-03-09 03:21:12 +0000 | [diff] [blame] | 428 | } |
| 429 | |
| 430 | if (!HasPHI) |
| 431 | return true; |
| 432 | return CSBBs.count(MI->getParent()); |
| 433 | } |
| 434 | |
Evan Cheng | 3115698 | 2010-04-21 00:21:07 +0000 | [diff] [blame] | 435 | void MachineCSE::EnterScope(MachineBasicBlock *MBB) { |
| 436 | DEBUG(dbgs() << "Entering: " << MBB->getName() << '\n'); |
| 437 | ScopeType *Scope = new ScopeType(VNT); |
| 438 | ScopeMap[MBB] = Scope; |
| 439 | } |
| 440 | |
| 441 | void MachineCSE::ExitScope(MachineBasicBlock *MBB) { |
| 442 | DEBUG(dbgs() << "Exiting: " << MBB->getName() << '\n'); |
| 443 | DenseMap<MachineBasicBlock*, ScopeType*>::iterator SI = ScopeMap.find(MBB); |
| 444 | assert(SI != ScopeMap.end()); |
Evan Cheng | 3115698 | 2010-04-21 00:21:07 +0000 | [diff] [blame] | 445 | delete SI->second; |
Jakub Staszak | bb8ddc7 | 2012-11-26 22:14:19 +0000 | [diff] [blame] | 446 | ScopeMap.erase(SI); |
Evan Cheng | 3115698 | 2010-04-21 00:21:07 +0000 | [diff] [blame] | 447 | } |
| 448 | |
| 449 | bool MachineCSE::ProcessBlock(MachineBasicBlock *MBB) { |
Evan Cheng | 6ba9554 | 2010-03-03 02:48:20 +0000 | [diff] [blame] | 450 | bool Changed = false; |
| 451 | |
Evan Cheng | 31f94c7 | 2010-03-09 03:21:12 +0000 | [diff] [blame] | 452 | SmallVector<std::pair<unsigned, unsigned>, 8> CSEPairs; |
Manman Ren | 39ad568 | 2012-08-08 00:51:41 +0000 | [diff] [blame] | 453 | SmallVector<unsigned, 2> ImplicitDefsToUpdate; |
Evan Cheng | 16b48b8 | 2010-03-03 21:20:05 +0000 | [diff] [blame] | 454 | for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ) { |
Evan Cheng | 6ba9554 | 2010-03-03 02:48:20 +0000 | [diff] [blame] | 455 | MachineInstr *MI = &*I; |
Evan Cheng | 16b48b8 | 2010-03-03 21:20:05 +0000 | [diff] [blame] | 456 | ++I; |
Evan Cheng | a5f32cb | 2010-03-04 21:18:08 +0000 | [diff] [blame] | 457 | |
| 458 | if (!isCSECandidate(MI)) |
Evan Cheng | 6ba9554 | 2010-03-03 02:48:20 +0000 | [diff] [blame] | 459 | continue; |
Evan Cheng | 6ba9554 | 2010-03-03 02:48:20 +0000 | [diff] [blame] | 460 | |
| 461 | bool FoundCSE = VNT.count(MI); |
| 462 | if (!FoundCSE) { |
Stephen Hines | 37ed9c1 | 2014-12-01 14:51:49 -0800 | [diff] [blame^] | 463 | // Using trivial copy propagation to find more CSE opportunities. |
| 464 | if (PerformTrivialCopyPropagation(MI, MBB)) { |
Evan Cheng | cfea985 | 2011-04-11 18:47:20 +0000 | [diff] [blame] | 465 | Changed = true; |
| 466 | |
Evan Cheng | db8771a | 2010-04-02 02:21:24 +0000 | [diff] [blame] | 467 | // After coalescing MI itself may become a copy. |
Jakob Stoklund Olesen | 04c528a | 2010-07-16 04:45:42 +0000 | [diff] [blame] | 468 | if (MI->isCopyLike()) |
Evan Cheng | db8771a | 2010-04-02 02:21:24 +0000 | [diff] [blame] | 469 | continue; |
Stephen Hines | 37ed9c1 | 2014-12-01 14:51:49 -0800 | [diff] [blame^] | 470 | |
| 471 | // Try again to see if CSE is possible. |
Evan Cheng | 6ba9554 | 2010-03-03 02:48:20 +0000 | [diff] [blame] | 472 | FoundCSE = VNT.count(MI); |
Evan Cheng | db8771a | 2010-04-02 02:21:24 +0000 | [diff] [blame] | 473 | } |
Evan Cheng | 6ba9554 | 2010-03-03 02:48:20 +0000 | [diff] [blame] | 474 | } |
Evan Cheng | a63cde2 | 2010-12-15 22:16:21 +0000 | [diff] [blame] | 475 | |
| 476 | // Commute commutable instructions. |
| 477 | bool Commuted = false; |
Evan Cheng | 5a96b3d | 2011-12-07 07:15:52 +0000 | [diff] [blame] | 478 | if (!FoundCSE && MI->isCommutable()) { |
Evan Cheng | a63cde2 | 2010-12-15 22:16:21 +0000 | [diff] [blame] | 479 | MachineInstr *NewMI = TII->commuteInstruction(MI); |
| 480 | if (NewMI) { |
| 481 | Commuted = true; |
| 482 | FoundCSE = VNT.count(NewMI); |
Evan Cheng | cfea985 | 2011-04-11 18:47:20 +0000 | [diff] [blame] | 483 | if (NewMI != MI) { |
Evan Cheng | a63cde2 | 2010-12-15 22:16:21 +0000 | [diff] [blame] | 484 | // New instruction. It doesn't need to be kept. |
| 485 | NewMI->eraseFromParent(); |
Evan Cheng | cfea985 | 2011-04-11 18:47:20 +0000 | [diff] [blame] | 486 | Changed = true; |
| 487 | } else if (!FoundCSE) |
Evan Cheng | a63cde2 | 2010-12-15 22:16:21 +0000 | [diff] [blame] | 488 | // MI was changed but it didn't help, commute it back! |
| 489 | (void)TII->commuteInstruction(MI); |
| 490 | } |
| 491 | } |
Evan Cheng | 6ba9554 | 2010-03-03 02:48:20 +0000 | [diff] [blame] | 492 | |
Evan Cheng | 189c1ec | 2010-10-29 23:36:03 +0000 | [diff] [blame] | 493 | // If the instruction defines physical registers and the values *may* be |
Evan Cheng | 67bda72 | 2010-03-03 23:59:08 +0000 | [diff] [blame] | 494 | // used, then it's not safe to replace it with a common subexpression. |
Evan Cheng | 189c1ec | 2010-10-29 23:36:03 +0000 | [diff] [blame] | 495 | // It's also not safe if the instruction uses physical registers. |
Evan Cheng | 97b5beb | 2012-01-10 02:02:58 +0000 | [diff] [blame] | 496 | bool CrossMBBPhysDef = false; |
Nick Lewycky | 7a7a6db | 2012-07-05 06:19:21 +0000 | [diff] [blame] | 497 | SmallSet<unsigned, 8> PhysRefs; |
Evan Cheng | 97b5beb | 2012-01-10 02:02:58 +0000 | [diff] [blame] | 498 | SmallVector<unsigned, 2> PhysDefs; |
Ulrich Weigand | b64e211 | 2012-11-13 18:40:58 +0000 | [diff] [blame] | 499 | bool PhysUseDef = false; |
| 500 | if (FoundCSE && hasLivePhysRegDefUses(MI, MBB, PhysRefs, |
| 501 | PhysDefs, PhysUseDef)) { |
Evan Cheng | 67bda72 | 2010-03-03 23:59:08 +0000 | [diff] [blame] | 502 | FoundCSE = false; |
| 503 | |
Evan Cheng | 97b5beb | 2012-01-10 02:02:58 +0000 | [diff] [blame] | 504 | // ... Unless the CS is local or is in the sole predecessor block |
| 505 | // and it also defines the physical register which is not clobbered |
| 506 | // in between and the physical register uses were not clobbered. |
Ulrich Weigand | b64e211 | 2012-11-13 18:40:58 +0000 | [diff] [blame] | 507 | // This can never be the case if the instruction both uses and |
| 508 | // defines the same physical register, which was detected above. |
| 509 | if (!PhysUseDef) { |
| 510 | unsigned CSVN = VNT.lookup(MI); |
| 511 | MachineInstr *CSMI = Exps[CSVN]; |
| 512 | if (PhysRegDefsReach(CSMI, MI, PhysRefs, PhysDefs, CrossMBBPhysDef)) |
| 513 | FoundCSE = true; |
| 514 | } |
Evan Cheng | 835810b | 2010-05-21 21:22:19 +0000 | [diff] [blame] | 515 | } |
| 516 | |
Evan Cheng | 16b48b8 | 2010-03-03 21:20:05 +0000 | [diff] [blame] | 517 | if (!FoundCSE) { |
| 518 | VNT.insert(MI, CurrVN++); |
| 519 | Exps.push_back(MI); |
| 520 | continue; |
| 521 | } |
| 522 | |
| 523 | // Found a common subexpression, eliminate it. |
| 524 | unsigned CSVN = VNT.lookup(MI); |
| 525 | MachineInstr *CSMI = Exps[CSVN]; |
| 526 | DEBUG(dbgs() << "Examining: " << *MI); |
| 527 | DEBUG(dbgs() << "*** Found a common subexpression: " << *CSMI); |
Evan Cheng | 31f94c7 | 2010-03-09 03:21:12 +0000 | [diff] [blame] | 528 | |
| 529 | // Check if it's profitable to perform this CSE. |
| 530 | bool DoCSE = true; |
Manman Ren | 39ad568 | 2012-08-08 00:51:41 +0000 | [diff] [blame] | 531 | unsigned NumDefs = MI->getDesc().getNumDefs() + |
| 532 | MI->getDesc().getNumImplicitDefs(); |
Stephen Hines | 36b5688 | 2014-04-23 16:57:46 -0700 | [diff] [blame] | 533 | |
Evan Cheng | 16b48b8 | 2010-03-03 21:20:05 +0000 | [diff] [blame] | 534 | for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) { |
| 535 | MachineOperand &MO = MI->getOperand(i); |
| 536 | if (!MO.isReg() || !MO.isDef()) |
| 537 | continue; |
| 538 | unsigned OldReg = MO.getReg(); |
| 539 | unsigned NewReg = CSMI->getOperand(i).getReg(); |
Manman Ren | 39ad568 | 2012-08-08 00:51:41 +0000 | [diff] [blame] | 540 | |
| 541 | // Go through implicit defs of CSMI and MI, if a def is not dead at MI, |
| 542 | // we should make sure it is not dead at CSMI. |
| 543 | if (MO.isImplicit() && !MO.isDead() && CSMI->getOperand(i).isDead()) |
| 544 | ImplicitDefsToUpdate.push_back(i); |
| 545 | if (OldReg == NewReg) { |
| 546 | --NumDefs; |
Evan Cheng | 6cc1aea | 2010-03-06 01:14:19 +0000 | [diff] [blame] | 547 | continue; |
Manman Ren | 39ad568 | 2012-08-08 00:51:41 +0000 | [diff] [blame] | 548 | } |
Bill Wendling | f6fb7ed | 2011-10-12 23:03:40 +0000 | [diff] [blame] | 549 | |
Evan Cheng | 6cc1aea | 2010-03-06 01:14:19 +0000 | [diff] [blame] | 550 | assert(TargetRegisterInfo::isVirtualRegister(OldReg) && |
Evan Cheng | 16b48b8 | 2010-03-03 21:20:05 +0000 | [diff] [blame] | 551 | TargetRegisterInfo::isVirtualRegister(NewReg) && |
| 552 | "Do not CSE physical register defs!"); |
Bill Wendling | f6fb7ed | 2011-10-12 23:03:40 +0000 | [diff] [blame] | 553 | |
Evan Cheng | 2938a00 | 2010-03-10 02:12:03 +0000 | [diff] [blame] | 554 | if (!isProfitableToCSE(NewReg, OldReg, CSMI, MI)) { |
Nick Lewycky | 7a7a6db | 2012-07-05 06:19:21 +0000 | [diff] [blame] | 555 | DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n"); |
Evan Cheng | 31f94c7 | 2010-03-09 03:21:12 +0000 | [diff] [blame] | 556 | DoCSE = false; |
| 557 | break; |
| 558 | } |
Bill Wendling | f6fb7ed | 2011-10-12 23:03:40 +0000 | [diff] [blame] | 559 | |
| 560 | // Don't perform CSE if the result of the old instruction cannot exist |
| 561 | // within the register class of the new instruction. |
| 562 | const TargetRegisterClass *OldRC = MRI->getRegClass(OldReg); |
| 563 | if (!MRI->constrainRegClass(NewReg, OldRC)) { |
Nick Lewycky | 7a7a6db | 2012-07-05 06:19:21 +0000 | [diff] [blame] | 564 | DEBUG(dbgs() << "*** Not the same register class, avoid CSE!\n"); |
Bill Wendling | f6fb7ed | 2011-10-12 23:03:40 +0000 | [diff] [blame] | 565 | DoCSE = false; |
| 566 | break; |
| 567 | } |
| 568 | |
Evan Cheng | 31f94c7 | 2010-03-09 03:21:12 +0000 | [diff] [blame] | 569 | CSEPairs.push_back(std::make_pair(OldReg, NewReg)); |
Evan Cheng | 16b48b8 | 2010-03-03 21:20:05 +0000 | [diff] [blame] | 570 | --NumDefs; |
| 571 | } |
Evan Cheng | 31f94c7 | 2010-03-09 03:21:12 +0000 | [diff] [blame] | 572 | |
| 573 | // Actually perform the elimination. |
| 574 | if (DoCSE) { |
Dan Gohman | 49b4589 | 2010-05-13 19:24:00 +0000 | [diff] [blame] | 575 | for (unsigned i = 0, e = CSEPairs.size(); i != e; ++i) { |
Evan Cheng | 31f94c7 | 2010-03-09 03:21:12 +0000 | [diff] [blame] | 576 | MRI->replaceRegWith(CSEPairs[i].first, CSEPairs[i].second); |
Dan Gohman | 49b4589 | 2010-05-13 19:24:00 +0000 | [diff] [blame] | 577 | MRI->clearKillFlags(CSEPairs[i].second); |
| 578 | } |
Evan Cheng | 97b5beb | 2012-01-10 02:02:58 +0000 | [diff] [blame] | 579 | |
Manman Ren | 39ad568 | 2012-08-08 00:51:41 +0000 | [diff] [blame] | 580 | // Go through implicit defs of CSMI and MI, if a def is not dead at MI, |
| 581 | // we should make sure it is not dead at CSMI. |
| 582 | for (unsigned i = 0, e = ImplicitDefsToUpdate.size(); i != e; ++i) |
| 583 | CSMI->getOperand(ImplicitDefsToUpdate[i]).setIsDead(false); |
| 584 | |
Evan Cheng | 97b5beb | 2012-01-10 02:02:58 +0000 | [diff] [blame] | 585 | if (CrossMBBPhysDef) { |
| 586 | // Add physical register defs now coming in from a predecessor to MBB |
| 587 | // livein list. |
| 588 | while (!PhysDefs.empty()) { |
| 589 | unsigned LiveIn = PhysDefs.pop_back_val(); |
| 590 | if (!MBB->isLiveIn(LiveIn)) |
| 591 | MBB->addLiveIn(LiveIn); |
| 592 | } |
| 593 | ++NumCrossBBCSEs; |
| 594 | } |
| 595 | |
Evan Cheng | 31f94c7 | 2010-03-09 03:21:12 +0000 | [diff] [blame] | 596 | MI->eraseFromParent(); |
| 597 | ++NumCSEs; |
Evan Cheng | 189c1ec | 2010-10-29 23:36:03 +0000 | [diff] [blame] | 598 | if (!PhysRefs.empty()) |
Evan Cheng | 2b4e727 | 2010-06-04 23:28:13 +0000 | [diff] [blame] | 599 | ++NumPhysCSEs; |
Evan Cheng | a63cde2 | 2010-12-15 22:16:21 +0000 | [diff] [blame] | 600 | if (Commuted) |
| 601 | ++NumCommutes; |
Evan Cheng | cfea985 | 2011-04-11 18:47:20 +0000 | [diff] [blame] | 602 | Changed = true; |
Evan Cheng | 31f94c7 | 2010-03-09 03:21:12 +0000 | [diff] [blame] | 603 | } else { |
Evan Cheng | 31f94c7 | 2010-03-09 03:21:12 +0000 | [diff] [blame] | 604 | VNT.insert(MI, CurrVN++); |
| 605 | Exps.push_back(MI); |
| 606 | } |
| 607 | CSEPairs.clear(); |
Manman Ren | 39ad568 | 2012-08-08 00:51:41 +0000 | [diff] [blame] | 608 | ImplicitDefsToUpdate.clear(); |
Evan Cheng | 6ba9554 | 2010-03-03 02:48:20 +0000 | [diff] [blame] | 609 | } |
| 610 | |
Evan Cheng | 3115698 | 2010-04-21 00:21:07 +0000 | [diff] [blame] | 611 | return Changed; |
| 612 | } |
| 613 | |
| 614 | /// ExitScopeIfDone - Destroy scope for the MBB that corresponds to the given |
| 615 | /// dominator tree node if its a leaf or all of its children are done. Walk |
| 616 | /// up the dominator tree to destroy ancestors which are now done. |
| 617 | void |
| 618 | MachineCSE::ExitScopeIfDone(MachineDomTreeNode *Node, |
Nick Lewycky | 7a7a6db | 2012-07-05 06:19:21 +0000 | [diff] [blame] | 619 | DenseMap<MachineDomTreeNode*, unsigned> &OpenChildren) { |
Evan Cheng | 3115698 | 2010-04-21 00:21:07 +0000 | [diff] [blame] | 620 | if (OpenChildren[Node]) |
| 621 | return; |
| 622 | |
| 623 | // Pop scope. |
| 624 | ExitScope(Node->getBlock()); |
| 625 | |
| 626 | // Now traverse upwards to pop ancestors whose offsprings are all done. |
Nick Lewycky | 7a7a6db | 2012-07-05 06:19:21 +0000 | [diff] [blame] | 627 | while (MachineDomTreeNode *Parent = Node->getIDom()) { |
Evan Cheng | 3115698 | 2010-04-21 00:21:07 +0000 | [diff] [blame] | 628 | unsigned Left = --OpenChildren[Parent]; |
| 629 | if (Left != 0) |
| 630 | break; |
| 631 | ExitScope(Parent->getBlock()); |
| 632 | Node = Parent; |
| 633 | } |
| 634 | } |
| 635 | |
| 636 | bool MachineCSE::PerformCSE(MachineDomTreeNode *Node) { |
| 637 | SmallVector<MachineDomTreeNode*, 32> Scopes; |
| 638 | SmallVector<MachineDomTreeNode*, 8> WorkList; |
Evan Cheng | 3115698 | 2010-04-21 00:21:07 +0000 | [diff] [blame] | 639 | DenseMap<MachineDomTreeNode*, unsigned> OpenChildren; |
| 640 | |
Evan Cheng | c2b768f | 2010-09-17 21:59:42 +0000 | [diff] [blame] | 641 | CurrVN = 0; |
| 642 | |
Evan Cheng | 3115698 | 2010-04-21 00:21:07 +0000 | [diff] [blame] | 643 | // Perform a DFS walk to determine the order of visit. |
| 644 | WorkList.push_back(Node); |
| 645 | do { |
| 646 | Node = WorkList.pop_back_val(); |
| 647 | Scopes.push_back(Node); |
| 648 | const std::vector<MachineDomTreeNode*> &Children = Node->getChildren(); |
| 649 | unsigned NumChildren = Children.size(); |
| 650 | OpenChildren[Node] = NumChildren; |
| 651 | for (unsigned i = 0; i != NumChildren; ++i) { |
| 652 | MachineDomTreeNode *Child = Children[i]; |
Evan Cheng | 3115698 | 2010-04-21 00:21:07 +0000 | [diff] [blame] | 653 | WorkList.push_back(Child); |
| 654 | } |
| 655 | } while (!WorkList.empty()); |
| 656 | |
| 657 | // Now perform CSE. |
| 658 | bool Changed = false; |
| 659 | for (unsigned i = 0, e = Scopes.size(); i != e; ++i) { |
| 660 | MachineDomTreeNode *Node = Scopes[i]; |
| 661 | MachineBasicBlock *MBB = Node->getBlock(); |
| 662 | EnterScope(MBB); |
| 663 | Changed |= ProcessBlock(MBB); |
| 664 | // If it's a leaf node, it's done. Traverse upwards to pop ancestors. |
Nick Lewycky | 7a7a6db | 2012-07-05 06:19:21 +0000 | [diff] [blame] | 665 | ExitScopeIfDone(Node, OpenChildren); |
Evan Cheng | 3115698 | 2010-04-21 00:21:07 +0000 | [diff] [blame] | 666 | } |
Evan Cheng | 6ba9554 | 2010-03-03 02:48:20 +0000 | [diff] [blame] | 667 | |
| 668 | return Changed; |
| 669 | } |
| 670 | |
Evan Cheng | c6fe333 | 2010-03-02 02:38:24 +0000 | [diff] [blame] | 671 | bool MachineCSE::runOnMachineFunction(MachineFunction &MF) { |
Stephen Hines | 36b5688 | 2014-04-23 16:57:46 -0700 | [diff] [blame] | 672 | if (skipOptnoneFunction(*MF.getFunction())) |
| 673 | return false; |
| 674 | |
Stephen Hines | 37ed9c1 | 2014-12-01 14:51:49 -0800 | [diff] [blame^] | 675 | TII = MF.getSubtarget().getInstrInfo(); |
| 676 | TRI = MF.getSubtarget().getRegisterInfo(); |
Evan Cheng | 6ba9554 | 2010-03-03 02:48:20 +0000 | [diff] [blame] | 677 | MRI = &MF.getRegInfo(); |
Evan Cheng | a5f32cb | 2010-03-04 21:18:08 +0000 | [diff] [blame] | 678 | AA = &getAnalysis<AliasAnalysis>(); |
Evan Cheng | 31f94c7 | 2010-03-09 03:21:12 +0000 | [diff] [blame] | 679 | DT = &getAnalysis<MachineDominatorTree>(); |
Evan Cheng | 3115698 | 2010-04-21 00:21:07 +0000 | [diff] [blame] | 680 | return PerformCSE(DT->getRootNode()); |
Evan Cheng | c6fe333 | 2010-03-02 02:38:24 +0000 | [diff] [blame] | 681 | } |