EarlyCSE.cpp revision 75637154c38da0243c51f4338137a78849808e50
110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project//===- EarlyCSE.cpp - Simple and fast CSE pass ----------------------------===// 210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project// 310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project// The LLVM Compiler Infrastructure 410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project// 510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project// This file is distributed under the University of Illinois Open Source 610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project// License. See LICENSE.TXT for details. 710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project// 810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project//===----------------------------------------------------------------------===// 910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project// 1010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project// This pass performs a simple dominator tree walk that eliminates trivially 1110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project// redundant instructions. 1210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project// 1310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project//===----------------------------------------------------------------------===// 1410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 1510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project#define DEBUG_TYPE "early-cse" 1610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project#include "llvm/Transforms/Scalar.h" 1710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project#include "llvm/Instructions.h" 1810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project#include "llvm/Pass.h" 1910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project#include "llvm/Analysis/Dominators.h" 2010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project#include "llvm/Analysis/InstructionSimplify.h" 2110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project#include "llvm/Target/TargetData.h" 2210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project#include "llvm/Transforms/Utils/Local.h" 2310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project#include "llvm/Support/Debug.h" 2410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project#include "llvm/Support/RecyclingAllocator.h" 2510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project#include "llvm/ADT/ScopedHashTable.h" 2610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project#include "llvm/ADT/Statistic.h" 2710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Projectusing namespace llvm; 2810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 2910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source ProjectSTATISTIC(NumSimplify, "Number of instructions simplified or DCE'd"); 3010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source ProjectSTATISTIC(NumCSE, "Number of instructions CSE'd"); 3110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source ProjectSTATISTIC(NumCSELoad, "Number of load instructions CSE'd"); 3210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source ProjectSTATISTIC(NumCSECall, "Number of call instructions CSE'd"); 3310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source ProjectSTATISTIC(NumDSE, "Number of trivial dead stores removed"); 3410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 3510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Projectstatic unsigned getHash(const void *V) { 3610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project return DenseMapInfo<const void*>::getHashValue(V); 3710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project} 3810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 3910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project//===----------------------------------------------------------------------===// 4010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project// SimpleValue 4110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project//===----------------------------------------------------------------------===// 4210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 4310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Projectnamespace { 4410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project /// SimpleValue - Instances of this struct represent available values in the 4510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project /// scoped hash table. 4610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project struct SimpleValue { 4710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project Instruction *Inst; 4810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 4910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project SimpleValue(Instruction *I) : Inst(I) { 5010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project assert((isSentinel() || canHandle(I)) && "Inst can't be handled!"); 5110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project } 5210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 53b415faba7482dd7ee3335f0f1518333554e3da0dJeff Brown bool isSentinel() const { 5410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project return Inst == DenseMapInfo<Instruction*>::getEmptyKey() || 5510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project Inst == DenseMapInfo<Instruction*>::getTombstoneKey(); 56b415faba7482dd7ee3335f0f1518333554e3da0dJeff Brown } 5710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 5810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project static bool canHandle(Instruction *Inst) { 5910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project return isa<CastInst>(Inst) || isa<BinaryOperator>(Inst) || 6010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project isa<GetElementPtrInst>(Inst) || isa<CmpInst>(Inst) || 6110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) || 6210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) || 6310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst); 6410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project } 6510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project }; 6610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project} 6710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 6810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Projectnamespace llvm { 6910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project// SimpleValue is POD. 7010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Projecttemplate<> struct isPodLike<SimpleValue> { 7110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project static const bool value = true; 7210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project}; 7310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 7410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Projecttemplate<> struct DenseMapInfo<SimpleValue> { 7510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project static inline SimpleValue getEmptyKey() { 7610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project return DenseMapInfo<Instruction*>::getEmptyKey(); 7710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project } 7810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project static inline SimpleValue getTombstoneKey() { 7910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project return DenseMapInfo<Instruction*>::getTombstoneKey(); 8010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project } 8110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project static unsigned getHashValue(SimpleValue Val); 8210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project static bool isEqual(SimpleValue LHS, SimpleValue RHS); 8310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project}; 8410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project} 8510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 8610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Projectunsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) { 8710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project Instruction *Inst = Val.Inst; 8810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 8910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project // Hash in all of the operands as pointers. 9010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project unsigned Res = 0; 9110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i) 9210e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project Res ^= getHash(Inst->getOperand(i)) << i; 9310e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project 9410e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project if (CastInst *CI = dyn_cast<CastInst>(Inst)) 9510e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project Res ^= getHash(CI->getType()); 9610e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project else if (CmpInst *CI = dyn_cast<CmpInst>(Inst)) 9710e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project Res ^= CI->getPredicate(); 9810e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project else if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Inst)) { 9910e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project for (ExtractValueInst::idx_iterator I = EVI->idx_begin(), 10010e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project E = EVI->idx_end(); I != E; ++I) 10110e23eebca4175a8dfe3a788b2bebacb1fcfce54The Android Open Source Project Res ^= *I; 102 } else if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Inst)) { 103 for (InsertValueInst::idx_iterator I = IVI->idx_begin(), 104 E = IVI->idx_end(); I != E; ++I) 105 Res ^= *I; 106 } else { 107 // nothing extra to hash in. 108 assert((isa<BinaryOperator>(Inst) || isa<GetElementPtrInst>(Inst) || 109 isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) || 110 isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst)) && 111 "Invalid/unknown instruction"); 112 } 113 114 // Mix in the opcode. 115 return (Res << 1) ^ Inst->getOpcode(); 116} 117 118bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) { 119 Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst; 120 121 if (LHS.isSentinel() || RHS.isSentinel()) 122 return LHSI == RHSI; 123 124 if (LHSI->getOpcode() != RHSI->getOpcode()) return false; 125 return LHSI->isIdenticalTo(RHSI); 126} 127 128//===----------------------------------------------------------------------===// 129// CallValue 130//===----------------------------------------------------------------------===// 131 132namespace { 133 /// CallValue - Instances of this struct represent available call values in 134 /// the scoped hash table. 135 struct CallValue { 136 Instruction *Inst; 137 138 CallValue(Instruction *I) : Inst(I) { 139 assert((isSentinel() || canHandle(I)) && "Inst can't be handled!"); 140 } 141 142 bool isSentinel() const { 143 return Inst == DenseMapInfo<Instruction*>::getEmptyKey() || 144 Inst == DenseMapInfo<Instruction*>::getTombstoneKey(); 145 } 146 147 static bool canHandle(Instruction *Inst) { 148 if (CallInst *CI = dyn_cast<CallInst>(Inst)) 149 return CI->onlyReadsMemory(); 150 return false; 151 } 152 }; 153} 154 155namespace llvm { 156 // CallValue is POD. 157 template<> struct isPodLike<CallValue> { 158 static const bool value = true; 159 }; 160 161 template<> struct DenseMapInfo<CallValue> { 162 static inline CallValue getEmptyKey() { 163 return DenseMapInfo<Instruction*>::getEmptyKey(); 164 } 165 static inline CallValue getTombstoneKey() { 166 return DenseMapInfo<Instruction*>::getTombstoneKey(); 167 } 168 static unsigned getHashValue(CallValue Val); 169 static bool isEqual(CallValue LHS, CallValue RHS); 170 }; 171} 172unsigned DenseMapInfo<CallValue>::getHashValue(CallValue 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<CallValue>::isEqual(CallValue LHS, CallValue RHS) { 183 Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst; 184 if (LHS.isSentinel() || RHS.isSentinel()) 185 return LHSI == RHSI; 186 return LHSI->isIdenticalTo(RHSI); 187} 188 189 190//===----------------------------------------------------------------------===// 191// EarlyCSE pass. 192//===----------------------------------------------------------------------===// 193 194namespace { 195 196/// EarlyCSE - This pass does a simple depth-first walk over the dominator 197/// tree, eliminating trivially redundant instructions and using instsimplify 198/// to canonicalize things as it goes. It is intended to be fast and catch 199/// obvious cases so that instcombine and other passes are more effective. It 200/// is expected that a later pass of GVN will catch the interesting/hard 201/// cases. 202class EarlyCSE : public FunctionPass { 203public: 204 const TargetData *TD; 205 DominatorTree *DT; 206 typedef RecyclingAllocator<BumpPtrAllocator, 207 ScopedHashTableVal<SimpleValue, Value*> > AllocatorTy; 208 typedef ScopedHashTable<SimpleValue, Value*, DenseMapInfo<SimpleValue>, 209 AllocatorTy> ScopedHTType; 210 211 /// AvailableValues - This scoped hash table contains the current values of 212 /// all of our simple scalar expressions. As we walk down the domtree, we 213 /// look to see if instructions are in this: if so, we replace them with what 214 /// we find, otherwise we insert them so that dominated values can succeed in 215 /// their lookup. 216 ScopedHTType *AvailableValues; 217 218 /// AvailableLoads - This scoped hash table contains the current values 219 /// of loads. This allows us to get efficient access to dominating loads when 220 /// we have a fully redundant load. In addition to the most recent load, we 221 /// keep track of a generation count of the read, which is compared against 222 /// the current generation count. The current generation count is 223 /// incremented after every possibly writing memory operation, which ensures 224 /// that we only CSE loads with other loads that have no intervening store. 225 typedef RecyclingAllocator<BumpPtrAllocator, 226 ScopedHashTableVal<Value*, std::pair<Value*, unsigned> > > LoadMapAllocator; 227 typedef ScopedHashTable<Value*, std::pair<Value*, unsigned>, 228 DenseMapInfo<Value*>, LoadMapAllocator> LoadHTType; 229 LoadHTType *AvailableLoads; 230 231 /// AvailableCalls - This scoped hash table contains the current values 232 /// of read-only call values. It uses the same generation count as loads. 233 typedef ScopedHashTable<CallValue, std::pair<Value*, unsigned> > CallHTType; 234 CallHTType *AvailableCalls; 235 236 /// CurrentGeneration - This is the current generation of the memory value. 237 unsigned CurrentGeneration; 238 239 static char ID; 240 explicit EarlyCSE() : FunctionPass(ID) { 241 initializeEarlyCSEPass(*PassRegistry::getPassRegistry()); 242 } 243 244 bool runOnFunction(Function &F); 245 246private: 247 248 bool processNode(DomTreeNode *Node); 249 250 // This transformation requires dominator postdominator info 251 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 252 AU.addRequired<DominatorTree>(); 253 AU.setPreservesCFG(); 254 } 255}; 256} 257 258char EarlyCSE::ID = 0; 259 260// createEarlyCSEPass - The public interface to this file. 261FunctionPass *llvm::createEarlyCSEPass() { 262 return new EarlyCSE(); 263} 264 265INITIALIZE_PASS_BEGIN(EarlyCSE, "early-cse", "Early CSE", false, false) 266INITIALIZE_PASS_DEPENDENCY(DominatorTree) 267INITIALIZE_PASS_END(EarlyCSE, "early-cse", "Early CSE", false, false) 268 269bool EarlyCSE::processNode(DomTreeNode *Node) { 270 // Define a scope in the scoped hash table. When we are done processing this 271 // domtree node and recurse back up to our parent domtree node, this will pop 272 // off all the values we install. 273 ScopedHTType::ScopeTy Scope(*AvailableValues); 274 275 // Define a scope for the load values so that anything we add will get 276 // popped when we recurse back up to our parent domtree node. 277 LoadHTType::ScopeTy LoadScope(*AvailableLoads); 278 279 // Define a scope for the call values so that anything we add will get 280 // popped when we recurse back up to our parent domtree node. 281 CallHTType::ScopeTy CallScope(*AvailableCalls); 282 283 BasicBlock *BB = Node->getBlock(); 284 285 // If this block has a single predecessor, then the predecessor is the parent 286 // of the domtree node and all of the live out memory values are still current 287 // in this block. If this block has multiple predecessors, then they could 288 // have invalidated the live-out memory values of our parent value. For now, 289 // just be conservative and invalidate memory if this block has multiple 290 // predecessors. 291 if (BB->getSinglePredecessor() == 0) 292 ++CurrentGeneration; 293 294 /// LastStore - Keep track of the last non-volatile store that we saw... for 295 /// as long as there in no instruction that reads memory. If we see a store 296 /// to the same location, we delete the dead store. This zaps trivial dead 297 /// stores which can occur in bitfield code among other things. 298 StoreInst *LastStore = 0; 299 300 bool Changed = false; 301 302 // See if any instructions in the block can be eliminated. If so, do it. If 303 // not, add them to AvailableValues. 304 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { 305 Instruction *Inst = I++; 306 307 // Dead instructions should just be removed. 308 if (isInstructionTriviallyDead(Inst)) { 309 DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n'); 310 Inst->eraseFromParent(); 311 Changed = true; 312 ++NumSimplify; 313 continue; 314 } 315 316 // If the instruction can be simplified (e.g. X+0 = X) then replace it with 317 // its simpler value. 318 if (Value *V = SimplifyInstruction(Inst, TD, DT)) { 319 DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << " to: " << *V << '\n'); 320 Inst->replaceAllUsesWith(V); 321 Inst->eraseFromParent(); 322 Changed = true; 323 ++NumSimplify; 324 continue; 325 } 326 327 // If this is a simple instruction that we can value number, process it. 328 if (SimpleValue::canHandle(Inst)) { 329 // See if the instruction has an available value. If so, use it. 330 if (Value *V = AvailableValues->lookup(Inst)) { 331 DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << " to: " << *V << '\n'); 332 Inst->replaceAllUsesWith(V); 333 Inst->eraseFromParent(); 334 Changed = true; 335 ++NumCSE; 336 continue; 337 } 338 339 // Otherwise, just remember that this value is available. 340 AvailableValues->insert(Inst, Inst); 341 continue; 342 } 343 344 // If this is a non-volatile load, process it. 345 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 346 // Ignore volatile loads. 347 if (LI->isVolatile()) { 348 LastStore = 0; 349 continue; 350 } 351 352 // If we have an available version of this load, and if it is the right 353 // generation, replace this instruction. 354 std::pair<Value*, unsigned> InVal = 355 AvailableLoads->lookup(Inst->getOperand(0)); 356 if (InVal.first != 0 && InVal.second == CurrentGeneration) { 357 DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << *Inst << " to: " 358 << *InVal.first << '\n'); 359 if (!Inst->use_empty()) Inst->replaceAllUsesWith(InVal.first); 360 Inst->eraseFromParent(); 361 Changed = true; 362 ++NumCSELoad; 363 continue; 364 } 365 366 // Otherwise, remember that we have this instruction. 367 AvailableLoads->insert(Inst->getOperand(0), 368 std::pair<Value*, unsigned>(Inst, CurrentGeneration)); 369 LastStore = 0; 370 continue; 371 } 372 373 // If this instruction may read from memory, forget LastStore. 374 if (Inst->mayReadFromMemory()) 375 LastStore = 0; 376 377 // If this is a read-only call, process it. 378 if (CallValue::canHandle(Inst)) { 379 // If we have an available version of this call, and if it is the right 380 // generation, replace this instruction. 381 std::pair<Value*, unsigned> InVal = AvailableCalls->lookup(Inst); 382 if (InVal.first != 0 && InVal.second == CurrentGeneration) { 383 DEBUG(dbgs() << "EarlyCSE CSE CALL: " << *Inst << " to: " 384 << *InVal.first << '\n'); 385 if (!Inst->use_empty()) Inst->replaceAllUsesWith(InVal.first); 386 Inst->eraseFromParent(); 387 Changed = true; 388 ++NumCSECall; 389 continue; 390 } 391 392 // Otherwise, remember that we have this instruction. 393 AvailableCalls->insert(Inst, 394 std::pair<Value*, unsigned>(Inst, CurrentGeneration)); 395 continue; 396 } 397 398 // Okay, this isn't something we can CSE at all. Check to see if it is 399 // something that could modify memory. If so, our available memory values 400 // cannot be used so bump the generation count. 401 if (Inst->mayWriteToMemory()) { 402 ++CurrentGeneration; 403 404 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 405 // We do a trivial form of DSE if there are two stores to the same 406 // location with no intervening loads. Delete the earlier store. 407 if (LastStore && 408 LastStore->getPointerOperand() == SI->getPointerOperand()) { 409 DEBUG(dbgs() << "EarlyCSE DEAD STORE: " << *LastStore << " due to: " 410 << *Inst << '\n'); 411 LastStore->eraseFromParent(); 412 Changed = true; 413 ++NumDSE; 414 LastStore = 0; 415 continue; 416 } 417 418 // Okay, we just invalidated anything we knew about loaded values. Try 419 // to salvage *something* by remembering that the stored value is a live 420 // version of the pointer. It is safe to forward from volatile stores 421 // to non-volatile loads, so we don't have to check for volatility of 422 // the store. 423 AvailableLoads->insert(SI->getPointerOperand(), 424 std::pair<Value*, unsigned>(SI->getValueOperand(), CurrentGeneration)); 425 426 // Remember that this was the last store we saw for DSE. 427 if (!SI->isVolatile()) 428 LastStore = SI; 429 } 430 } 431 } 432 433 unsigned LiveOutGeneration = CurrentGeneration; 434 for (DomTreeNode::iterator I = Node->begin(), E = Node->end(); I != E; ++I) { 435 Changed |= processNode(*I); 436 // Pop any generation changes off the stack from the recursive walk. 437 CurrentGeneration = LiveOutGeneration; 438 } 439 return Changed; 440} 441 442 443bool EarlyCSE::runOnFunction(Function &F) { 444 TD = getAnalysisIfAvailable<TargetData>(); 445 DT = &getAnalysis<DominatorTree>(); 446 447 // Tables that the pass uses when walking the domtree. 448 ScopedHTType AVTable; 449 AvailableValues = &AVTable; 450 LoadHTType LoadTable; 451 AvailableLoads = &LoadTable; 452 CallHTType CallTable; 453 AvailableCalls = &CallTable; 454 455 CurrentGeneration = 0; 456 return processNode(DT->getRootNode()); 457} 458