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 #include "llvm/Transforms/Scalar/EarlyCSE.h" 16 #include "llvm/ADT/Hashing.h" 17 #include "llvm/ADT/ScopedHashTable.h" 18 #include "llvm/ADT/Statistic.h" 19 #include "llvm/Analysis/AssumptionCache.h" 20 #include "llvm/Analysis/InstructionSimplify.h" 21 #include "llvm/Analysis/TargetLibraryInfo.h" 22 #include "llvm/Analysis/TargetTransformInfo.h" 23 #include "llvm/IR/DataLayout.h" 24 #include "llvm/IR/Dominators.h" 25 #include "llvm/IR/Instructions.h" 26 #include "llvm/IR/IntrinsicInst.h" 27 #include "llvm/IR/PatternMatch.h" 28 #include "llvm/Pass.h" 29 #include "llvm/Support/Debug.h" 30 #include "llvm/Support/RecyclingAllocator.h" 31 #include "llvm/Support/raw_ostream.h" 32 #include "llvm/Transforms/Scalar.h" 33 #include "llvm/Transforms/Utils/Local.h" 34 #include <deque> 35 using namespace llvm; 36 using namespace llvm::PatternMatch; 37 38 #define DEBUG_TYPE "early-cse" 39 40 STATISTIC(NumSimplify, "Number of instructions simplified or DCE'd"); 41 STATISTIC(NumCSE, "Number of instructions CSE'd"); 42 STATISTIC(NumCSELoad, "Number of load instructions CSE'd"); 43 STATISTIC(NumCSECall, "Number of call instructions CSE'd"); 44 STATISTIC(NumDSE, "Number of trivial dead stores removed"); 45 46 //===----------------------------------------------------------------------===// 47 // SimpleValue 48 //===----------------------------------------------------------------------===// 49 50 namespace { 51 /// \brief Struct representing the available values in the scoped hash table. 52 struct SimpleValue { 53 Instruction *Inst; 54 55 SimpleValue(Instruction *I) : Inst(I) { 56 assert((isSentinel() || canHandle(I)) && "Inst can't be handled!"); 57 } 58 59 bool isSentinel() const { 60 return Inst == DenseMapInfo<Instruction *>::getEmptyKey() || 61 Inst == DenseMapInfo<Instruction *>::getTombstoneKey(); 62 } 63 64 static bool canHandle(Instruction *Inst) { 65 // This can only handle non-void readnone functions. 66 if (CallInst *CI = dyn_cast<CallInst>(Inst)) 67 return CI->doesNotAccessMemory() && !CI->getType()->isVoidTy(); 68 return isa<CastInst>(Inst) || isa<BinaryOperator>(Inst) || 69 isa<GetElementPtrInst>(Inst) || isa<CmpInst>(Inst) || 70 isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) || 71 isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) || 72 isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst); 73 } 74 }; 75 } 76 77 namespace llvm { 78 template <> struct DenseMapInfo<SimpleValue> { 79 static inline SimpleValue getEmptyKey() { 80 return DenseMapInfo<Instruction *>::getEmptyKey(); 81 } 82 static inline SimpleValue getTombstoneKey() { 83 return DenseMapInfo<Instruction *>::getTombstoneKey(); 84 } 85 static unsigned getHashValue(SimpleValue Val); 86 static bool isEqual(SimpleValue LHS, SimpleValue RHS); 87 }; 88 } 89 90 unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) { 91 Instruction *Inst = Val.Inst; 92 // Hash in all of the operands as pointers. 93 if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst)) { 94 Value *LHS = BinOp->getOperand(0); 95 Value *RHS = BinOp->getOperand(1); 96 if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1)) 97 std::swap(LHS, RHS); 98 99 if (isa<OverflowingBinaryOperator>(BinOp)) { 100 // Hash the overflow behavior 101 unsigned Overflow = 102 BinOp->hasNoSignedWrap() * OverflowingBinaryOperator::NoSignedWrap | 103 BinOp->hasNoUnsignedWrap() * 104 OverflowingBinaryOperator::NoUnsignedWrap; 105 return hash_combine(BinOp->getOpcode(), Overflow, LHS, RHS); 106 } 107 108 return hash_combine(BinOp->getOpcode(), LHS, RHS); 109 } 110 111 if (CmpInst *CI = dyn_cast<CmpInst>(Inst)) { 112 Value *LHS = CI->getOperand(0); 113 Value *RHS = CI->getOperand(1); 114 CmpInst::Predicate Pred = CI->getPredicate(); 115 if (Inst->getOperand(0) > Inst->getOperand(1)) { 116 std::swap(LHS, RHS); 117 Pred = CI->getSwappedPredicate(); 118 } 119 return hash_combine(Inst->getOpcode(), Pred, LHS, RHS); 120 } 121 122 if (CastInst *CI = dyn_cast<CastInst>(Inst)) 123 return hash_combine(CI->getOpcode(), CI->getType(), CI->getOperand(0)); 124 125 if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Inst)) 126 return hash_combine(EVI->getOpcode(), EVI->getOperand(0), 127 hash_combine_range(EVI->idx_begin(), EVI->idx_end())); 128 129 if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Inst)) 130 return hash_combine(IVI->getOpcode(), IVI->getOperand(0), 131 IVI->getOperand(1), 132 hash_combine_range(IVI->idx_begin(), IVI->idx_end())); 133 134 assert((isa<CallInst>(Inst) || isa<BinaryOperator>(Inst) || 135 isa<GetElementPtrInst>(Inst) || isa<SelectInst>(Inst) || 136 isa<ExtractElementInst>(Inst) || isa<InsertElementInst>(Inst) || 137 isa<ShuffleVectorInst>(Inst)) && 138 "Invalid/unknown instruction"); 139 140 // Mix in the opcode. 141 return hash_combine( 142 Inst->getOpcode(), 143 hash_combine_range(Inst->value_op_begin(), Inst->value_op_end())); 144 } 145 146 bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) { 147 Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst; 148 149 if (LHS.isSentinel() || RHS.isSentinel()) 150 return LHSI == RHSI; 151 152 if (LHSI->getOpcode() != RHSI->getOpcode()) 153 return false; 154 if (LHSI->isIdenticalTo(RHSI)) 155 return true; 156 157 // If we're not strictly identical, we still might be a commutable instruction 158 if (BinaryOperator *LHSBinOp = dyn_cast<BinaryOperator>(LHSI)) { 159 if (!LHSBinOp->isCommutative()) 160 return false; 161 162 assert(isa<BinaryOperator>(RHSI) && 163 "same opcode, but different instruction type?"); 164 BinaryOperator *RHSBinOp = cast<BinaryOperator>(RHSI); 165 166 // Check overflow attributes 167 if (isa<OverflowingBinaryOperator>(LHSBinOp)) { 168 assert(isa<OverflowingBinaryOperator>(RHSBinOp) && 169 "same opcode, but different operator type?"); 170 if (LHSBinOp->hasNoUnsignedWrap() != RHSBinOp->hasNoUnsignedWrap() || 171 LHSBinOp->hasNoSignedWrap() != RHSBinOp->hasNoSignedWrap()) 172 return false; 173 } 174 175 // Commuted equality 176 return LHSBinOp->getOperand(0) == RHSBinOp->getOperand(1) && 177 LHSBinOp->getOperand(1) == RHSBinOp->getOperand(0); 178 } 179 if (CmpInst *LHSCmp = dyn_cast<CmpInst>(LHSI)) { 180 assert(isa<CmpInst>(RHSI) && 181 "same opcode, but different instruction type?"); 182 CmpInst *RHSCmp = cast<CmpInst>(RHSI); 183 // Commuted equality 184 return LHSCmp->getOperand(0) == RHSCmp->getOperand(1) && 185 LHSCmp->getOperand(1) == RHSCmp->getOperand(0) && 186 LHSCmp->getSwappedPredicate() == RHSCmp->getPredicate(); 187 } 188 189 return false; 190 } 191 192 //===----------------------------------------------------------------------===// 193 // CallValue 194 //===----------------------------------------------------------------------===// 195 196 namespace { 197 /// \brief Struct representing the available call values in the scoped hash 198 /// table. 199 struct CallValue { 200 Instruction *Inst; 201 202 CallValue(Instruction *I) : Inst(I) { 203 assert((isSentinel() || canHandle(I)) && "Inst can't be handled!"); 204 } 205 206 bool isSentinel() const { 207 return Inst == DenseMapInfo<Instruction *>::getEmptyKey() || 208 Inst == DenseMapInfo<Instruction *>::getTombstoneKey(); 209 } 210 211 static bool canHandle(Instruction *Inst) { 212 // Don't value number anything that returns void. 213 if (Inst->getType()->isVoidTy()) 214 return false; 215 216 CallInst *CI = dyn_cast<CallInst>(Inst); 217 if (!CI || !CI->onlyReadsMemory()) 218 return false; 219 return true; 220 } 221 }; 222 } 223 224 namespace llvm { 225 template <> struct DenseMapInfo<CallValue> { 226 static inline CallValue getEmptyKey() { 227 return DenseMapInfo<Instruction *>::getEmptyKey(); 228 } 229 static inline CallValue getTombstoneKey() { 230 return DenseMapInfo<Instruction *>::getTombstoneKey(); 231 } 232 static unsigned getHashValue(CallValue Val); 233 static bool isEqual(CallValue LHS, CallValue RHS); 234 }; 235 } 236 237 unsigned DenseMapInfo<CallValue>::getHashValue(CallValue Val) { 238 Instruction *Inst = Val.Inst; 239 // Hash all of the operands as pointers and mix in the opcode. 240 return hash_combine( 241 Inst->getOpcode(), 242 hash_combine_range(Inst->value_op_begin(), Inst->value_op_end())); 243 } 244 245 bool DenseMapInfo<CallValue>::isEqual(CallValue LHS, CallValue RHS) { 246 Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst; 247 if (LHS.isSentinel() || RHS.isSentinel()) 248 return LHSI == RHSI; 249 return LHSI->isIdenticalTo(RHSI); 250 } 251 252 //===----------------------------------------------------------------------===// 253 // EarlyCSE implementation 254 //===----------------------------------------------------------------------===// 255 256 namespace { 257 /// \brief A simple and fast domtree-based CSE pass. 258 /// 259 /// This pass does a simple depth-first walk over the dominator tree, 260 /// eliminating trivially redundant instructions and using instsimplify to 261 /// canonicalize things as it goes. It is intended to be fast and catch obvious 262 /// cases so that instcombine and other passes are more effective. It is 263 /// expected that a later pass of GVN will catch the interesting/hard cases. 264 class EarlyCSE { 265 public: 266 Function &F; 267 const TargetLibraryInfo &TLI; 268 const TargetTransformInfo &TTI; 269 DominatorTree &DT; 270 AssumptionCache &AC; 271 typedef RecyclingAllocator< 272 BumpPtrAllocator, ScopedHashTableVal<SimpleValue, Value *>> AllocatorTy; 273 typedef ScopedHashTable<SimpleValue, Value *, DenseMapInfo<SimpleValue>, 274 AllocatorTy> ScopedHTType; 275 276 /// \brief A scoped hash table of the current values of all of our simple 277 /// scalar expressions. 278 /// 279 /// As we walk down the domtree, we look to see if instructions are in this: 280 /// if so, we replace them with what we find, otherwise we insert them so 281 /// that dominated values can succeed in their lookup. 282 ScopedHTType AvailableValues; 283 284 /// \brief A scoped hash table of the current values of loads. 285 /// 286 /// This allows us to get efficient access to dominating loads when we have 287 /// a fully redundant load. In addition to the most recent load, we keep 288 /// track of a generation count of the read, which is compared against the 289 /// current generation count. The current generation count is incremented 290 /// after every possibly writing memory operation, which ensures that we only 291 /// CSE loads with other loads that have no intervening store. 292 typedef RecyclingAllocator< 293 BumpPtrAllocator, 294 ScopedHashTableVal<Value *, std::pair<Value *, unsigned>>> 295 LoadMapAllocator; 296 typedef ScopedHashTable<Value *, std::pair<Value *, unsigned>, 297 DenseMapInfo<Value *>, LoadMapAllocator> LoadHTType; 298 LoadHTType AvailableLoads; 299 300 /// \brief A scoped hash table of the current values of read-only call 301 /// values. 302 /// 303 /// It uses the same generation count as loads. 304 typedef ScopedHashTable<CallValue, std::pair<Value *, unsigned>> CallHTType; 305 CallHTType AvailableCalls; 306 307 /// \brief This is the current generation of the memory value. 308 unsigned CurrentGeneration; 309 310 /// \brief Set up the EarlyCSE runner for a particular function. 311 EarlyCSE(Function &F, const TargetLibraryInfo &TLI, 312 const TargetTransformInfo &TTI, DominatorTree &DT, 313 AssumptionCache &AC) 314 : F(F), TLI(TLI), TTI(TTI), DT(DT), AC(AC), CurrentGeneration(0) {} 315 316 bool run(); 317 318 private: 319 // Almost a POD, but needs to call the constructors for the scoped hash 320 // tables so that a new scope gets pushed on. These are RAII so that the 321 // scope gets popped when the NodeScope is destroyed. 322 class NodeScope { 323 public: 324 NodeScope(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads, 325 CallHTType &AvailableCalls) 326 : Scope(AvailableValues), LoadScope(AvailableLoads), 327 CallScope(AvailableCalls) {} 328 329 private: 330 NodeScope(const NodeScope &) = delete; 331 void operator=(const NodeScope &) = delete; 332 333 ScopedHTType::ScopeTy Scope; 334 LoadHTType::ScopeTy LoadScope; 335 CallHTType::ScopeTy CallScope; 336 }; 337 338 // Contains all the needed information to create a stack for doing a depth 339 // first tranversal of the tree. This includes scopes for values, loads, and 340 // calls as well as the generation. There is a child iterator so that the 341 // children do not need to be store spearately. 342 class StackNode { 343 public: 344 StackNode(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads, 345 CallHTType &AvailableCalls, unsigned cg, DomTreeNode *n, 346 DomTreeNode::iterator child, DomTreeNode::iterator end) 347 : CurrentGeneration(cg), ChildGeneration(cg), Node(n), ChildIter(child), 348 EndIter(end), Scopes(AvailableValues, AvailableLoads, AvailableCalls), 349 Processed(false) {} 350 351 // Accessors. 352 unsigned currentGeneration() { return CurrentGeneration; } 353 unsigned childGeneration() { return ChildGeneration; } 354 void childGeneration(unsigned generation) { ChildGeneration = generation; } 355 DomTreeNode *node() { return Node; } 356 DomTreeNode::iterator childIter() { return ChildIter; } 357 DomTreeNode *nextChild() { 358 DomTreeNode *child = *ChildIter; 359 ++ChildIter; 360 return child; 361 } 362 DomTreeNode::iterator end() { return EndIter; } 363 bool isProcessed() { return Processed; } 364 void process() { Processed = true; } 365 366 private: 367 StackNode(const StackNode &) = delete; 368 void operator=(const StackNode &) = delete; 369 370 // Members. 371 unsigned CurrentGeneration; 372 unsigned ChildGeneration; 373 DomTreeNode *Node; 374 DomTreeNode::iterator ChildIter; 375 DomTreeNode::iterator EndIter; 376 NodeScope Scopes; 377 bool Processed; 378 }; 379 380 /// \brief Wrapper class to handle memory instructions, including loads, 381 /// stores and intrinsic loads and stores defined by the target. 382 class ParseMemoryInst { 383 public: 384 ParseMemoryInst(Instruction *Inst, const TargetTransformInfo &TTI) 385 : Load(false), Store(false), Vol(false), MayReadFromMemory(false), 386 MayWriteToMemory(false), MatchingId(-1), Ptr(nullptr) { 387 MayReadFromMemory = Inst->mayReadFromMemory(); 388 MayWriteToMemory = Inst->mayWriteToMemory(); 389 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { 390 MemIntrinsicInfo Info; 391 if (!TTI.getTgtMemIntrinsic(II, Info)) 392 return; 393 if (Info.NumMemRefs == 1) { 394 Store = Info.WriteMem; 395 Load = Info.ReadMem; 396 MatchingId = Info.MatchingId; 397 MayReadFromMemory = Info.ReadMem; 398 MayWriteToMemory = Info.WriteMem; 399 Vol = Info.Vol; 400 Ptr = Info.PtrVal; 401 } 402 } else if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 403 Load = true; 404 Vol = !LI->isSimple(); 405 Ptr = LI->getPointerOperand(); 406 } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 407 Store = true; 408 Vol = !SI->isSimple(); 409 Ptr = SI->getPointerOperand(); 410 } 411 } 412 bool isLoad() { return Load; } 413 bool isStore() { return Store; } 414 bool isVolatile() { return Vol; } 415 bool isMatchingMemLoc(const ParseMemoryInst &Inst) { 416 return Ptr == Inst.Ptr && MatchingId == Inst.MatchingId; 417 } 418 bool isValid() { return Ptr != nullptr; } 419 int getMatchingId() { return MatchingId; } 420 Value *getPtr() { return Ptr; } 421 bool mayReadFromMemory() { return MayReadFromMemory; } 422 bool mayWriteToMemory() { return MayWriteToMemory; } 423 424 private: 425 bool Load; 426 bool Store; 427 bool Vol; 428 bool MayReadFromMemory; 429 bool MayWriteToMemory; 430 // For regular (non-intrinsic) loads/stores, this is set to -1. For 431 // intrinsic loads/stores, the id is retrieved from the corresponding 432 // field in the MemIntrinsicInfo structure. That field contains 433 // non-negative values only. 434 int MatchingId; 435 Value *Ptr; 436 }; 437 438 bool processNode(DomTreeNode *Node); 439 440 Value *getOrCreateResult(Value *Inst, Type *ExpectedType) const { 441 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) 442 return LI; 443 else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) 444 return SI->getValueOperand(); 445 assert(isa<IntrinsicInst>(Inst) && "Instruction not supported"); 446 return TTI.getOrCreateResultFromMemIntrinsic(cast<IntrinsicInst>(Inst), 447 ExpectedType); 448 } 449 }; 450 } 451 452 bool EarlyCSE::processNode(DomTreeNode *Node) { 453 BasicBlock *BB = Node->getBlock(); 454 455 // If this block has a single predecessor, then the predecessor is the parent 456 // of the domtree node and all of the live out memory values are still current 457 // in this block. If this block has multiple predecessors, then they could 458 // have invalidated the live-out memory values of our parent value. For now, 459 // just be conservative and invalidate memory if this block has multiple 460 // predecessors. 461 if (!BB->getSinglePredecessor()) 462 ++CurrentGeneration; 463 464 /// LastStore - Keep track of the last non-volatile store that we saw... for 465 /// as long as there in no instruction that reads memory. If we see a store 466 /// to the same location, we delete the dead store. This zaps trivial dead 467 /// stores which can occur in bitfield code among other things. 468 Instruction *LastStore = nullptr; 469 470 bool Changed = false; 471 const DataLayout &DL = BB->getModule()->getDataLayout(); 472 473 // See if any instructions in the block can be eliminated. If so, do it. If 474 // not, add them to AvailableValues. 475 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) { 476 Instruction *Inst = I++; 477 478 // Dead instructions should just be removed. 479 if (isInstructionTriviallyDead(Inst, &TLI)) { 480 DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n'); 481 Inst->eraseFromParent(); 482 Changed = true; 483 ++NumSimplify; 484 continue; 485 } 486 487 // Skip assume intrinsics, they don't really have side effects (although 488 // they're marked as such to ensure preservation of control dependencies), 489 // and this pass will not disturb any of the assumption's control 490 // dependencies. 491 if (match(Inst, m_Intrinsic<Intrinsic::assume>())) { 492 DEBUG(dbgs() << "EarlyCSE skipping assumption: " << *Inst << '\n'); 493 continue; 494 } 495 496 // If the instruction can be simplified (e.g. X+0 = X) then replace it with 497 // its simpler value. 498 if (Value *V = SimplifyInstruction(Inst, DL, &TLI, &DT, &AC)) { 499 DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << " to: " << *V << '\n'); 500 Inst->replaceAllUsesWith(V); 501 Inst->eraseFromParent(); 502 Changed = true; 503 ++NumSimplify; 504 continue; 505 } 506 507 // If this is a simple instruction that we can value number, process it. 508 if (SimpleValue::canHandle(Inst)) { 509 // See if the instruction has an available value. If so, use it. 510 if (Value *V = AvailableValues.lookup(Inst)) { 511 DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << " to: " << *V << '\n'); 512 Inst->replaceAllUsesWith(V); 513 Inst->eraseFromParent(); 514 Changed = true; 515 ++NumCSE; 516 continue; 517 } 518 519 // Otherwise, just remember that this value is available. 520 AvailableValues.insert(Inst, Inst); 521 continue; 522 } 523 524 ParseMemoryInst MemInst(Inst, TTI); 525 // If this is a non-volatile load, process it. 526 if (MemInst.isValid() && MemInst.isLoad()) { 527 // Ignore volatile loads. 528 if (MemInst.isVolatile()) { 529 LastStore = nullptr; 530 // Don't CSE across synchronization boundaries. 531 if (Inst->mayWriteToMemory()) 532 ++CurrentGeneration; 533 continue; 534 } 535 536 // If we have an available version of this load, and if it is the right 537 // generation, replace this instruction. 538 std::pair<Value *, unsigned> InVal = 539 AvailableLoads.lookup(MemInst.getPtr()); 540 if (InVal.first != nullptr && InVal.second == CurrentGeneration) { 541 Value *Op = getOrCreateResult(InVal.first, Inst->getType()); 542 if (Op != nullptr) { 543 DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << *Inst 544 << " to: " << *InVal.first << '\n'); 545 if (!Inst->use_empty()) 546 Inst->replaceAllUsesWith(Op); 547 Inst->eraseFromParent(); 548 Changed = true; 549 ++NumCSELoad; 550 continue; 551 } 552 } 553 554 // Otherwise, remember that we have this instruction. 555 AvailableLoads.insert(MemInst.getPtr(), std::pair<Value *, unsigned>( 556 Inst, CurrentGeneration)); 557 LastStore = nullptr; 558 continue; 559 } 560 561 // If this instruction may read from memory, forget LastStore. 562 // Load/store intrinsics will indicate both a read and a write to 563 // memory. The target may override this (e.g. so that a store intrinsic 564 // does not read from memory, and thus will be treated the same as a 565 // regular store for commoning purposes). 566 if (Inst->mayReadFromMemory() && 567 !(MemInst.isValid() && !MemInst.mayReadFromMemory())) 568 LastStore = nullptr; 569 570 // If this is a read-only call, process it. 571 if (CallValue::canHandle(Inst)) { 572 // If we have an available version of this call, and if it is the right 573 // generation, replace this instruction. 574 std::pair<Value *, unsigned> InVal = AvailableCalls.lookup(Inst); 575 if (InVal.first != nullptr && InVal.second == CurrentGeneration) { 576 DEBUG(dbgs() << "EarlyCSE CSE CALL: " << *Inst 577 << " to: " << *InVal.first << '\n'); 578 if (!Inst->use_empty()) 579 Inst->replaceAllUsesWith(InVal.first); 580 Inst->eraseFromParent(); 581 Changed = true; 582 ++NumCSECall; 583 continue; 584 } 585 586 // Otherwise, remember that we have this instruction. 587 AvailableCalls.insert( 588 Inst, std::pair<Value *, unsigned>(Inst, CurrentGeneration)); 589 continue; 590 } 591 592 // Okay, this isn't something we can CSE at all. Check to see if it is 593 // something that could modify memory. If so, our available memory values 594 // cannot be used so bump the generation count. 595 if (Inst->mayWriteToMemory()) { 596 ++CurrentGeneration; 597 598 if (MemInst.isValid() && MemInst.isStore()) { 599 // We do a trivial form of DSE if there are two stores to the same 600 // location with no intervening loads. Delete the earlier store. 601 if (LastStore) { 602 ParseMemoryInst LastStoreMemInst(LastStore, TTI); 603 if (LastStoreMemInst.isMatchingMemLoc(MemInst)) { 604 DEBUG(dbgs() << "EarlyCSE DEAD STORE: " << *LastStore 605 << " due to: " << *Inst << '\n'); 606 LastStore->eraseFromParent(); 607 Changed = true; 608 ++NumDSE; 609 LastStore = nullptr; 610 } 611 // fallthrough - we can exploit information about this store 612 } 613 614 // Okay, we just invalidated anything we knew about loaded values. Try 615 // to salvage *something* by remembering that the stored value is a live 616 // version of the pointer. It is safe to forward from volatile stores 617 // to non-volatile loads, so we don't have to check for volatility of 618 // the store. 619 AvailableLoads.insert(MemInst.getPtr(), std::pair<Value *, unsigned>( 620 Inst, CurrentGeneration)); 621 622 // Remember that this was the last store we saw for DSE. 623 if (!MemInst.isVolatile()) 624 LastStore = Inst; 625 } 626 } 627 } 628 629 return Changed; 630 } 631 632 bool EarlyCSE::run() { 633 // Note, deque is being used here because there is significant performance 634 // gains over vector when the container becomes very large due to the 635 // specific access patterns. For more information see the mailing list 636 // discussion on this: 637 // http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html 638 std::deque<StackNode *> nodesToProcess; 639 640 bool Changed = false; 641 642 // Process the root node. 643 nodesToProcess.push_back(new StackNode( 644 AvailableValues, AvailableLoads, AvailableCalls, CurrentGeneration, 645 DT.getRootNode(), DT.getRootNode()->begin(), DT.getRootNode()->end())); 646 647 // Save the current generation. 648 unsigned LiveOutGeneration = CurrentGeneration; 649 650 // Process the stack. 651 while (!nodesToProcess.empty()) { 652 // Grab the first item off the stack. Set the current generation, remove 653 // the node from the stack, and process it. 654 StackNode *NodeToProcess = nodesToProcess.back(); 655 656 // Initialize class members. 657 CurrentGeneration = NodeToProcess->currentGeneration(); 658 659 // Check if the node needs to be processed. 660 if (!NodeToProcess->isProcessed()) { 661 // Process the node. 662 Changed |= processNode(NodeToProcess->node()); 663 NodeToProcess->childGeneration(CurrentGeneration); 664 NodeToProcess->process(); 665 } else if (NodeToProcess->childIter() != NodeToProcess->end()) { 666 // Push the next child onto the stack. 667 DomTreeNode *child = NodeToProcess->nextChild(); 668 nodesToProcess.push_back( 669 new StackNode(AvailableValues, AvailableLoads, AvailableCalls, 670 NodeToProcess->childGeneration(), child, child->begin(), 671 child->end())); 672 } else { 673 // It has been processed, and there are no more children to process, 674 // so delete it and pop it off the stack. 675 delete NodeToProcess; 676 nodesToProcess.pop_back(); 677 } 678 } // while (!nodes...) 679 680 // Reset the current generation. 681 CurrentGeneration = LiveOutGeneration; 682 683 return Changed; 684 } 685 686 PreservedAnalyses EarlyCSEPass::run(Function &F, 687 AnalysisManager<Function> *AM) { 688 auto &TLI = AM->getResult<TargetLibraryAnalysis>(F); 689 auto &TTI = AM->getResult<TargetIRAnalysis>(F); 690 auto &DT = AM->getResult<DominatorTreeAnalysis>(F); 691 auto &AC = AM->getResult<AssumptionAnalysis>(F); 692 693 EarlyCSE CSE(F, TLI, TTI, DT, AC); 694 695 if (!CSE.run()) 696 return PreservedAnalyses::all(); 697 698 // CSE preserves the dominator tree because it doesn't mutate the CFG. 699 // FIXME: Bundle this with other CFG-preservation. 700 PreservedAnalyses PA; 701 PA.preserve<DominatorTreeAnalysis>(); 702 return PA; 703 } 704 705 namespace { 706 /// \brief A simple and fast domtree-based CSE pass. 707 /// 708 /// This pass does a simple depth-first walk over the dominator tree, 709 /// eliminating trivially redundant instructions and using instsimplify to 710 /// canonicalize things as it goes. It is intended to be fast and catch obvious 711 /// cases so that instcombine and other passes are more effective. It is 712 /// expected that a later pass of GVN will catch the interesting/hard cases. 713 class EarlyCSELegacyPass : public FunctionPass { 714 public: 715 static char ID; 716 717 EarlyCSELegacyPass() : FunctionPass(ID) { 718 initializeEarlyCSELegacyPassPass(*PassRegistry::getPassRegistry()); 719 } 720 721 bool runOnFunction(Function &F) override { 722 if (skipOptnoneFunction(F)) 723 return false; 724 725 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); 726 auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 727 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 728 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 729 730 EarlyCSE CSE(F, TLI, TTI, DT, AC); 731 732 return CSE.run(); 733 } 734 735 void getAnalysisUsage(AnalysisUsage &AU) const override { 736 AU.addRequired<AssumptionCacheTracker>(); 737 AU.addRequired<DominatorTreeWrapperPass>(); 738 AU.addRequired<TargetLibraryInfoWrapperPass>(); 739 AU.addRequired<TargetTransformInfoWrapperPass>(); 740 AU.setPreservesCFG(); 741 } 742 }; 743 } 744 745 char EarlyCSELegacyPass::ID = 0; 746 747 FunctionPass *llvm::createEarlyCSEPass() { return new EarlyCSELegacyPass(); } 748 749 INITIALIZE_PASS_BEGIN(EarlyCSELegacyPass, "early-cse", "Early CSE", false, 750 false) 751 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 752 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 753 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 754 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 755 INITIALIZE_PASS_END(EarlyCSELegacyPass, "early-cse", "Early CSE", false, false) 756