EarlyCSE.cpp revision a60a8b0eb773eabb3ad83e610e737efda525a0da
1//===- EarlyCSE.cpp - Simple and fast CSE 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 a simple dominator tree walk that eliminates trivially 11// redundant instructions. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "early-cse" 16#include "llvm/Transforms/Scalar.h" 17#include "llvm/Instructions.h" 18#include "llvm/Pass.h" 19#include "llvm/Analysis/Dominators.h" 20#include "llvm/Analysis/InstructionSimplify.h" 21#include "llvm/Target/TargetData.h" 22#include "llvm/Transforms/Utils/Local.h" 23#include "llvm/Support/Debug.h" 24#include "llvm/Support/RecyclingAllocator.h" 25#include "llvm/ADT/ScopedHashTable.h" 26#include "llvm/ADT/Statistic.h" 27using namespace llvm; 28 29STATISTIC(NumSimplify, "Number of instructions simplified or DCE'd"); 30STATISTIC(NumCSE, "Number of instructions CSE'd"); 31STATISTIC(NumCSEMem, "Number of load and call instructions CSE'd"); 32 33static unsigned getHash(const void *V) { 34 return DenseMapInfo<const void*>::getHashValue(V); 35} 36 37//===----------------------------------------------------------------------===// 38// SimpleValue 39//===----------------------------------------------------------------------===// 40 41namespace { 42 /// SimpleValue - Instances of this struct represent available values in the 43 /// scoped hash table. 44 struct SimpleValue { 45 Instruction *Inst; 46 47 SimpleValue(Instruction *I) : Inst(I) { 48 assert((isSentinel() || canHandle(I)) && "Inst can't be handled!"); 49 } 50 51 bool isSentinel() const { 52 return Inst == DenseMapInfo<Instruction*>::getEmptyKey() || 53 Inst == DenseMapInfo<Instruction*>::getTombstoneKey(); 54 } 55 56 static bool canHandle(Instruction *Inst) { 57 return isa<CastInst>(Inst) || isa<BinaryOperator>(Inst) || 58 isa<GetElementPtrInst>(Inst) || isa<CmpInst>(Inst) || 59 isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) || 60 isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) || 61 isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst); 62 } 63 }; 64} 65 66namespace llvm { 67// SimpleValue is POD. 68template<> struct isPodLike<SimpleValue> { 69 static const bool value = true; 70}; 71 72template<> struct DenseMapInfo<SimpleValue> { 73 static inline SimpleValue getEmptyKey() { 74 return DenseMapInfo<Instruction*>::getEmptyKey(); 75 } 76 static inline SimpleValue getTombstoneKey() { 77 return DenseMapInfo<Instruction*>::getTombstoneKey(); 78 } 79 static unsigned getHashValue(SimpleValue Val); 80 static bool isEqual(SimpleValue LHS, SimpleValue RHS); 81}; 82} 83 84unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) { 85 Instruction *Inst = Val.Inst; 86 87 // Hash in all of the operands as pointers. 88 unsigned Res = 0; 89 for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i) 90 Res ^= getHash(Inst->getOperand(i)) << i; 91 92 if (CastInst *CI = dyn_cast<CastInst>(Inst)) 93 Res ^= getHash(CI->getType()); 94 else if (CmpInst *CI = dyn_cast<CmpInst>(Inst)) 95 Res ^= CI->getPredicate(); 96 else if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Inst)) { 97 for (ExtractValueInst::idx_iterator I = EVI->idx_begin(), 98 E = EVI->idx_end(); I != E; ++I) 99 Res ^= *I; 100 } else if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Inst)) { 101 for (InsertValueInst::idx_iterator I = IVI->idx_begin(), 102 E = IVI->idx_end(); I != E; ++I) 103 Res ^= *I; 104 } else { 105 // nothing extra to hash in. 106 assert((isa<BinaryOperator>(Inst) || isa<GetElementPtrInst>(Inst) || 107 isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) || 108 isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst)) && 109 "Invalid/unknown instruction"); 110 } 111 112 // Mix in the opcode. 113 return (Res << 1) ^ Inst->getOpcode(); 114} 115 116bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) { 117 Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst; 118 119 if (LHS.isSentinel() || RHS.isSentinel()) 120 return LHSI == RHSI; 121 122 if (LHSI->getOpcode() != RHSI->getOpcode()) return false; 123 return LHSI->isIdenticalTo(RHSI); 124} 125 126//===----------------------------------------------------------------------===// 127// MemoryValue 128//===----------------------------------------------------------------------===// 129 130namespace { 131 /// MemoryValue - Instances of this struct represent available load and call 132 /// values in the scoped hash table. 133 struct MemoryValue { 134 Instruction *Inst; 135 136 MemoryValue(Instruction *I) : Inst(I) { 137 assert((isSentinel() || canHandle(I)) && "Inst can't be handled!"); 138 } 139 140 bool isSentinel() const { 141 return Inst == DenseMapInfo<Instruction*>::getEmptyKey() || 142 Inst == DenseMapInfo<Instruction*>::getTombstoneKey(); 143 } 144 145 static bool canHandle(Instruction *Inst) { 146 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) 147 return !LI->isVolatile(); 148 if (CallInst *CI = dyn_cast<CallInst>(Inst)) 149 return CI->onlyReadsMemory(); 150 return false; 151 } 152 }; 153} 154 155namespace llvm { 156 // MemoryValue is POD. 157 template<> struct isPodLike<MemoryValue> { 158 static const bool value = true; 159 }; 160 161 template<> struct DenseMapInfo<MemoryValue> { 162 static inline MemoryValue getEmptyKey() { 163 return DenseMapInfo<Instruction*>::getEmptyKey(); 164 } 165 static inline MemoryValue getTombstoneKey() { 166 return DenseMapInfo<Instruction*>::getTombstoneKey(); 167 } 168 static unsigned getHashValue(MemoryValue Val); 169 static bool isEqual(MemoryValue LHS, MemoryValue RHS); 170 }; 171} 172unsigned DenseMapInfo<MemoryValue>::getHashValue(MemoryValue Val) { 173 Instruction *Inst = Val.Inst; 174 // Hash in all of the operands as pointers. 175 unsigned Res = 0; 176 for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i) 177 Res ^= getHash(Inst->getOperand(i)) << i; 178 // Mix in the opcode. 179 return (Res << 1) ^ Inst->getOpcode(); 180} 181 182bool DenseMapInfo<MemoryValue>::isEqual(MemoryValue LHS, MemoryValue RHS) { 183 Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst; 184 185 if (LHS.isSentinel() || RHS.isSentinel()) 186 return LHSI == RHSI; 187 188 if (LHSI->getOpcode() != RHSI->getOpcode()) return false; 189 return LHSI->isIdenticalTo(RHSI); 190} 191 192 193//===----------------------------------------------------------------------===// 194// EarlyCSE pass. 195//===----------------------------------------------------------------------===// 196 197namespace { 198 199/// EarlyCSE - This pass does a simple depth-first walk over the dominator 200/// tree, eliminating trivially redundant instructions and using instsimplify 201/// to canonicalize things as it goes. It is intended to be fast and catch 202/// obvious cases so that instcombine and other passes are more effective. It 203/// is expected that a later pass of GVN will catch the interesting/hard 204/// cases. 205class EarlyCSE : public FunctionPass { 206public: 207 const TargetData *TD; 208 DominatorTree *DT; 209 typedef RecyclingAllocator<BumpPtrAllocator, 210 ScopedHashTableVal<SimpleValue, Value*> > AllocatorTy; 211 typedef ScopedHashTable<SimpleValue, Value*, DenseMapInfo<SimpleValue>, 212 AllocatorTy> ScopedHTType; 213 214 /// AvailableValues - This scoped hash table contains the current values of 215 /// all of our simple scalar expressions. As we walk down the domtree, we 216 /// look to see if instructions are in this: if so, we replace them with what 217 /// we find, otherwise we insert them so that dominated values can succeed in 218 /// their lookup. 219 ScopedHTType *AvailableValues; 220 221 typedef ScopedHashTable<MemoryValue, std::pair<Value*, unsigned> > MemHTType; 222 /// AvailableMemValues - This scoped hash table contains the current values of 223 /// loads and other read-only memory values. This allows us to get efficient 224 /// access to dominating loads we we find a fully redundant load. In addition 225 /// to the most recent load, we keep track of a generation count of the read, 226 /// which is compared against the current generation count. The current 227 /// generation count is incremented after every possibly writing memory 228 /// operation, which ensures that we only CSE loads with other loads that have 229 /// no intervening store. 230 MemHTType *AvailableMemValues; 231 232 /// CurrentGeneration - This is the current generation of the memory value. 233 unsigned CurrentGeneration; 234 235 static char ID; 236 explicit EarlyCSE() : FunctionPass(ID) { 237 initializeEarlyCSEPass(*PassRegistry::getPassRegistry()); 238 } 239 240 bool runOnFunction(Function &F); 241 242private: 243 244 bool processNode(DomTreeNode *Node); 245 246 // This transformation requires dominator postdominator info 247 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 248 AU.addRequired<DominatorTree>(); 249 AU.setPreservesCFG(); 250 } 251}; 252} 253 254char EarlyCSE::ID = 0; 255 256// createEarlyCSEPass - The public interface to this file. 257FunctionPass *llvm::createEarlyCSEPass() { 258 return new EarlyCSE(); 259} 260 261INITIALIZE_PASS_BEGIN(EarlyCSE, "early-cse", "Early CSE", false, false) 262INITIALIZE_PASS_DEPENDENCY(DominatorTree) 263INITIALIZE_PASS_END(EarlyCSE, "early-cse", "Early CSE", false, false) 264 265bool EarlyCSE::processNode(DomTreeNode *Node) { 266 // Define a scope in the scoped hash table. When we are done processing this 267 // domtree node and recurse back up to our parent domtree node, this will pop 268 // off all the values we install. 269 ScopedHTType::ScopeTy Scope(*AvailableValues); 270 271 // Define a scope for the memory values so that anything we add will get 272 // popped when we recurse back up to our parent domtree node. 273 MemHTType::ScopeTy MemScope(*AvailableMemValues); 274 275 BasicBlock *BB = Node->getBlock(); 276 277 // If this block has a single predecessor, then the predecessor is the parent 278 // of the domtree node and all of the live out memory values are still current 279 // in this block. If this block has multiple predecessors, then they could 280 // have invalidated the live-out memory values of our parent value. For now, 281 // just be conservative and invalidate memory if this block has multiple 282 // predecessors. 283 if (BB->getSinglePredecessor() == 0) 284 ++CurrentGeneration; 285 286 bool Changed = false; 287 288 // See if any instructions in the block can be eliminated. If so, do it. If 289 // not, add them to AvailableValues. 290 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { 291 Instruction *Inst = I++; 292 293 // Dead instructions should just be removed. 294 if (isInstructionTriviallyDead(Inst)) { 295 DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n'); 296 Inst->eraseFromParent(); 297 Changed = true; 298 ++NumSimplify; 299 continue; 300 } 301 302 // If the instruction can be simplified (e.g. X+0 = X) then replace it with 303 // its simpler value. 304 if (Value *V = SimplifyInstruction(Inst, TD, DT)) { 305 DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << " to: " << *V << '\n'); 306 Inst->replaceAllUsesWith(V); 307 Inst->eraseFromParent(); 308 Changed = true; 309 ++NumSimplify; 310 continue; 311 } 312 313 // If this is a simple instruction that we can value number, process it. 314 if (SimpleValue::canHandle(Inst)) { 315 // See if the instruction has an available value. If so, use it. 316 if (Value *V = AvailableValues->lookup(Inst)) { 317 DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << " to: " << *V << '\n'); 318 Inst->replaceAllUsesWith(V); 319 Inst->eraseFromParent(); 320 Changed = true; 321 ++NumCSE; 322 continue; 323 } 324 325 // Otherwise, just remember that this value is available. 326 AvailableValues->insert(Inst, Inst); 327 continue; 328 } 329 330 // If this is a read-only memory value, process it. 331 if (MemoryValue::canHandle(Inst)) { 332 // If we have an available version of this value, and if it is the right 333 // generation, replace this instruction. 334 std::pair<Value*, unsigned> InVal = AvailableMemValues->lookup(Inst); 335 if (InVal.first != 0 && InVal.second == CurrentGeneration) { 336 DEBUG(dbgs() << "EarlyCSE CSE MEM: " << *Inst << " to: " 337 << *InVal.first << '\n'); 338 if (!Inst->use_empty()) Inst->replaceAllUsesWith(InVal.first); 339 Inst->eraseFromParent(); 340 Changed = true; 341 ++NumCSEMem; 342 continue; 343 } 344 345 // Otherwise, remember that we have this instruction. 346 AvailableMemValues->insert(Inst, 347 std::pair<Value*, unsigned>(Inst, CurrentGeneration)); 348 continue; 349 } 350 351 // Okay, this isn't something we can CSE at all. Check to see if it is 352 // something that could modify memory. If so, our available memory values 353 // cannot be used so bump the generation count. 354 if (Inst->mayWriteToMemory()) 355 ++CurrentGeneration; 356 } 357 358 unsigned LiveOutGeneration = CurrentGeneration; 359 for (DomTreeNode::iterator I = Node->begin(), E = Node->end(); I != E; ++I) { 360 Changed |= processNode(*I); 361 // Pop any generation changes off the stack from the recursive walk. 362 CurrentGeneration = LiveOutGeneration; 363 } 364 return Changed; 365} 366 367 368bool EarlyCSE::runOnFunction(Function &F) { 369 TD = getAnalysisIfAvailable<TargetData>(); 370 DT = &getAnalysis<DominatorTree>(); 371 ScopedHTType AVTable; 372 AvailableValues = &AVTable; 373 374 MemHTType MemTable; 375 AvailableMemValues = &MemTable; 376 377 CurrentGeneration = 0; 378 return processNode(DT->getRootNode()); 379} 380