1 //===- EarlyCSE.cpp - Simple and fast CSE pass ----------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass performs a simple dominator tree walk that eliminates trivially
11 // redundant instructions.
13 //===----------------------------------------------------------------------===//
15 #include "llvm/Transforms/Scalar/EarlyCSE.h"
16 #include "llvm/ADT/Hashing.h"
17 #include "llvm/ADT/ScopedHashTable.h"
18 #include "llvm/ADT/SetVector.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/Analysis/AssumptionCache.h"
21 #include "llvm/Analysis/GlobalsModRef.h"
22 #include "llvm/Analysis/InstructionSimplify.h"
23 #include "llvm/Analysis/MemorySSA.h"
24 #include "llvm/Analysis/MemorySSAUpdater.h"
25 #include "llvm/Analysis/TargetLibraryInfo.h"
26 #include "llvm/Analysis/TargetTransformInfo.h"
27 #include "llvm/IR/DataLayout.h"
28 #include "llvm/IR/Dominators.h"
29 #include "llvm/IR/Instructions.h"
30 #include "llvm/IR/IntrinsicInst.h"
31 #include "llvm/IR/PatternMatch.h"
32 #include "llvm/Pass.h"
33 #include "llvm/Support/Debug.h"
34 #include "llvm/Support/RecyclingAllocator.h"
35 #include "llvm/Support/raw_ostream.h"
36 #include "llvm/Transforms/Scalar.h"
37 #include "llvm/Transforms/Utils/Local.h"
40 using namespace llvm::PatternMatch;
42 #define DEBUG_TYPE "early-cse"
44 STATISTIC(NumSimplify, "Number of instructions simplified or DCE'd");
45 STATISTIC(NumCSE, "Number of instructions CSE'd");
46 STATISTIC(NumCSECVP, "Number of compare instructions CVP'd");
47 STATISTIC(NumCSELoad, "Number of load instructions CSE'd");
48 STATISTIC(NumCSECall, "Number of call instructions CSE'd");
49 STATISTIC(NumDSE, "Number of trivial dead stores removed");
51 //===----------------------------------------------------------------------===//
53 //===----------------------------------------------------------------------===//
56 /// \brief Struct representing the available values in the scoped hash table.
60 SimpleValue(Instruction *I) : Inst(I) {
61 assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
64 bool isSentinel() const {
65 return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||
66 Inst == DenseMapInfo<Instruction *>::getTombstoneKey();
69 static bool canHandle(Instruction *Inst) {
70 // This can only handle non-void readnone functions.
71 if (CallInst *CI = dyn_cast<CallInst>(Inst))
72 return CI->doesNotAccessMemory() && !CI->getType()->isVoidTy();
73 return isa<CastInst>(Inst) || isa<BinaryOperator>(Inst) ||
74 isa<GetElementPtrInst>(Inst) || isa<CmpInst>(Inst) ||
75 isa<SelectInst>(Inst) || isa<ExtractElementInst>(Inst) ||
76 isa<InsertElementInst>(Inst) || isa<ShuffleVectorInst>(Inst) ||
77 isa<ExtractValueInst>(Inst) || isa<InsertValueInst>(Inst);
83 template <> struct DenseMapInfo<SimpleValue> {
84 static inline SimpleValue getEmptyKey() {
85 return DenseMapInfo<Instruction *>::getEmptyKey();
87 static inline SimpleValue getTombstoneKey() {
88 return DenseMapInfo<Instruction *>::getTombstoneKey();
90 static unsigned getHashValue(SimpleValue Val);
91 static bool isEqual(SimpleValue LHS, SimpleValue RHS);
95 unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
96 Instruction *Inst = Val.Inst;
97 // Hash in all of the operands as pointers.
98 if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst)) {
99 Value *LHS = BinOp->getOperand(0);
100 Value *RHS = BinOp->getOperand(1);
101 if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1))
104 return hash_combine(BinOp->getOpcode(), LHS, RHS);
107 if (CmpInst *CI = dyn_cast<CmpInst>(Inst)) {
108 Value *LHS = CI->getOperand(0);
109 Value *RHS = CI->getOperand(1);
110 CmpInst::Predicate Pred = CI->getPredicate();
111 if (Inst->getOperand(0) > Inst->getOperand(1)) {
113 Pred = CI->getSwappedPredicate();
115 return hash_combine(Inst->getOpcode(), Pred, LHS, RHS);
118 if (CastInst *CI = dyn_cast<CastInst>(Inst))
119 return hash_combine(CI->getOpcode(), CI->getType(), CI->getOperand(0));
121 if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Inst))
122 return hash_combine(EVI->getOpcode(), EVI->getOperand(0),
123 hash_combine_range(EVI->idx_begin(), EVI->idx_end()));
125 if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Inst))
126 return hash_combine(IVI->getOpcode(), IVI->getOperand(0),
128 hash_combine_range(IVI->idx_begin(), IVI->idx_end()));
130 assert((isa<CallInst>(Inst) || isa<BinaryOperator>(Inst) ||
131 isa<GetElementPtrInst>(Inst) || isa<SelectInst>(Inst) ||
132 isa<ExtractElementInst>(Inst) || isa<InsertElementInst>(Inst) ||
133 isa<ShuffleVectorInst>(Inst)) &&
134 "Invalid/unknown instruction");
136 // Mix in the opcode.
139 hash_combine_range(Inst->value_op_begin(), Inst->value_op_end()));
142 bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
143 Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
145 if (LHS.isSentinel() || RHS.isSentinel())
148 if (LHSI->getOpcode() != RHSI->getOpcode())
150 if (LHSI->isIdenticalToWhenDefined(RHSI))
153 // If we're not strictly identical, we still might be a commutable instruction
154 if (BinaryOperator *LHSBinOp = dyn_cast<BinaryOperator>(LHSI)) {
155 if (!LHSBinOp->isCommutative())
158 assert(isa<BinaryOperator>(RHSI) &&
159 "same opcode, but different instruction type?");
160 BinaryOperator *RHSBinOp = cast<BinaryOperator>(RHSI);
163 return LHSBinOp->getOperand(0) == RHSBinOp->getOperand(1) &&
164 LHSBinOp->getOperand(1) == RHSBinOp->getOperand(0);
166 if (CmpInst *LHSCmp = dyn_cast<CmpInst>(LHSI)) {
167 assert(isa<CmpInst>(RHSI) &&
168 "same opcode, but different instruction type?");
169 CmpInst *RHSCmp = cast<CmpInst>(RHSI);
171 return LHSCmp->getOperand(0) == RHSCmp->getOperand(1) &&
172 LHSCmp->getOperand(1) == RHSCmp->getOperand(0) &&
173 LHSCmp->getSwappedPredicate() == RHSCmp->getPredicate();
179 //===----------------------------------------------------------------------===//
181 //===----------------------------------------------------------------------===//
184 /// \brief Struct representing the available call values in the scoped hash
189 CallValue(Instruction *I) : Inst(I) {
190 assert((isSentinel() || canHandle(I)) && "Inst can't be handled!");
193 bool isSentinel() const {
194 return Inst == DenseMapInfo<Instruction *>::getEmptyKey() ||
195 Inst == DenseMapInfo<Instruction *>::getTombstoneKey();
198 static bool canHandle(Instruction *Inst) {
199 // Don't value number anything that returns void.
200 if (Inst->getType()->isVoidTy())
203 CallInst *CI = dyn_cast<CallInst>(Inst);
204 if (!CI || !CI->onlyReadsMemory())
212 template <> struct DenseMapInfo<CallValue> {
213 static inline CallValue getEmptyKey() {
214 return DenseMapInfo<Instruction *>::getEmptyKey();
216 static inline CallValue getTombstoneKey() {
217 return DenseMapInfo<Instruction *>::getTombstoneKey();
219 static unsigned getHashValue(CallValue Val);
220 static bool isEqual(CallValue LHS, CallValue RHS);
224 unsigned DenseMapInfo<CallValue>::getHashValue(CallValue Val) {
225 Instruction *Inst = Val.Inst;
226 // Hash all of the operands as pointers and mix in the opcode.
229 hash_combine_range(Inst->value_op_begin(), Inst->value_op_end()));
232 bool DenseMapInfo<CallValue>::isEqual(CallValue LHS, CallValue RHS) {
233 Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
234 if (LHS.isSentinel() || RHS.isSentinel())
236 return LHSI->isIdenticalTo(RHSI);
239 //===----------------------------------------------------------------------===//
240 // EarlyCSE implementation
241 //===----------------------------------------------------------------------===//
244 /// \brief A simple and fast domtree-based CSE pass.
246 /// This pass does a simple depth-first walk over the dominator tree,
247 /// eliminating trivially redundant instructions and using instsimplify to
248 /// canonicalize things as it goes. It is intended to be fast and catch obvious
249 /// cases so that instcombine and other passes are more effective. It is
250 /// expected that a later pass of GVN will catch the interesting/hard cases.
253 const TargetLibraryInfo &TLI;
254 const TargetTransformInfo &TTI;
257 const SimplifyQuery SQ;
259 std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
260 typedef RecyclingAllocator<
261 BumpPtrAllocator, ScopedHashTableVal<SimpleValue, Value *>> AllocatorTy;
262 typedef ScopedHashTable<SimpleValue, Value *, DenseMapInfo<SimpleValue>,
263 AllocatorTy> ScopedHTType;
265 /// \brief A scoped hash table of the current values of all of our simple
266 /// scalar expressions.
268 /// As we walk down the domtree, we look to see if instructions are in this:
269 /// if so, we replace them with what we find, otherwise we insert them so
270 /// that dominated values can succeed in their lookup.
271 ScopedHTType AvailableValues;
273 /// A scoped hash table of the current values of previously encounted memory
276 /// This allows us to get efficient access to dominating loads or stores when
277 /// we have a fully redundant load. In addition to the most recent load, we
278 /// keep track of a generation count of the read, which is compared against
279 /// the current generation count. The current generation count is incremented
280 /// after every possibly writing memory operation, which ensures that we only
281 /// CSE loads with other loads that have no intervening store. Ordering
282 /// events (such as fences or atomic instructions) increment the generation
283 /// count as well; essentially, we model these as writes to all possible
284 /// locations. Note that atomic and/or volatile loads and stores can be
285 /// present the table; it is the responsibility of the consumer to inspect
286 /// the atomicity/volatility if needed.
288 Instruction *DefInst;
294 : DefInst(nullptr), Generation(0), MatchingId(-1), IsAtomic(false),
295 IsInvariant(false) {}
296 LoadValue(Instruction *Inst, unsigned Generation, unsigned MatchingId,
297 bool IsAtomic, bool IsInvariant)
298 : DefInst(Inst), Generation(Generation), MatchingId(MatchingId),
299 IsAtomic(IsAtomic), IsInvariant(IsInvariant) {}
301 typedef RecyclingAllocator<BumpPtrAllocator,
302 ScopedHashTableVal<Value *, LoadValue>>
304 typedef ScopedHashTable<Value *, LoadValue, DenseMapInfo<Value *>,
305 LoadMapAllocator> LoadHTType;
306 LoadHTType AvailableLoads;
308 /// \brief A scoped hash table of the current values of read-only call
311 /// It uses the same generation count as loads.
312 typedef ScopedHashTable<CallValue, std::pair<Instruction *, unsigned>>
314 CallHTType AvailableCalls;
316 /// \brief This is the current generation of the memory value.
317 unsigned CurrentGeneration;
319 /// \brief Set up the EarlyCSE runner for a particular function.
320 EarlyCSE(const DataLayout &DL, const TargetLibraryInfo &TLI,
321 const TargetTransformInfo &TTI, DominatorTree &DT,
322 AssumptionCache &AC, MemorySSA *MSSA)
323 : TLI(TLI), TTI(TTI), DT(DT), AC(AC), SQ(DL, &TLI, &DT, &AC), MSSA(MSSA),
324 MSSAUpdater(make_unique<MemorySSAUpdater>(MSSA)), CurrentGeneration(0) {
330 // Almost a POD, but needs to call the constructors for the scoped hash
331 // tables so that a new scope gets pushed on. These are RAII so that the
332 // scope gets popped when the NodeScope is destroyed.
335 NodeScope(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
336 CallHTType &AvailableCalls)
337 : Scope(AvailableValues), LoadScope(AvailableLoads),
338 CallScope(AvailableCalls) {}
341 NodeScope(const NodeScope &) = delete;
342 void operator=(const NodeScope &) = delete;
344 ScopedHTType::ScopeTy Scope;
345 LoadHTType::ScopeTy LoadScope;
346 CallHTType::ScopeTy CallScope;
349 // Contains all the needed information to create a stack for doing a depth
350 // first traversal of the tree. This includes scopes for values, loads, and
351 // calls as well as the generation. There is a child iterator so that the
352 // children do not need to be store separately.
355 StackNode(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
356 CallHTType &AvailableCalls, unsigned cg, DomTreeNode *n,
357 DomTreeNode::iterator child, DomTreeNode::iterator end)
358 : CurrentGeneration(cg), ChildGeneration(cg), Node(n), ChildIter(child),
359 EndIter(end), Scopes(AvailableValues, AvailableLoads, AvailableCalls),
363 unsigned currentGeneration() { return CurrentGeneration; }
364 unsigned childGeneration() { return ChildGeneration; }
365 void childGeneration(unsigned generation) { ChildGeneration = generation; }
366 DomTreeNode *node() { return Node; }
367 DomTreeNode::iterator childIter() { return ChildIter; }
368 DomTreeNode *nextChild() {
369 DomTreeNode *child = *ChildIter;
373 DomTreeNode::iterator end() { return EndIter; }
374 bool isProcessed() { return Processed; }
375 void process() { Processed = true; }
378 StackNode(const StackNode &) = delete;
379 void operator=(const StackNode &) = delete;
382 unsigned CurrentGeneration;
383 unsigned ChildGeneration;
385 DomTreeNode::iterator ChildIter;
386 DomTreeNode::iterator EndIter;
391 /// \brief Wrapper class to handle memory instructions, including loads,
392 /// stores and intrinsic loads and stores defined by the target.
393 class ParseMemoryInst {
395 ParseMemoryInst(Instruction *Inst, const TargetTransformInfo &TTI)
396 : IsTargetMemInst(false), Inst(Inst) {
397 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
398 if (TTI.getTgtMemIntrinsic(II, Info))
399 IsTargetMemInst = true;
401 bool isLoad() const {
402 if (IsTargetMemInst) return Info.ReadMem;
403 return isa<LoadInst>(Inst);
405 bool isStore() const {
406 if (IsTargetMemInst) return Info.WriteMem;
407 return isa<StoreInst>(Inst);
409 bool isAtomic() const {
411 return Info.Ordering != AtomicOrdering::NotAtomic;
412 return Inst->isAtomic();
414 bool isUnordered() const {
416 return Info.isUnordered();
418 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
419 return LI->isUnordered();
420 } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
421 return SI->isUnordered();
423 // Conservative answer
424 return !Inst->isAtomic();
427 bool isVolatile() const {
429 return Info.IsVolatile;
431 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
432 return LI->isVolatile();
433 } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
434 return SI->isVolatile();
436 // Conservative answer
440 bool isInvariantLoad() const {
441 if (auto *LI = dyn_cast<LoadInst>(Inst))
442 return LI->getMetadata(LLVMContext::MD_invariant_load) != nullptr;
446 bool isMatchingMemLoc(const ParseMemoryInst &Inst) const {
447 return (getPointerOperand() == Inst.getPointerOperand() &&
448 getMatchingId() == Inst.getMatchingId());
450 bool isValid() const { return getPointerOperand() != nullptr; }
452 // For regular (non-intrinsic) loads/stores, this is set to -1. For
453 // intrinsic loads/stores, the id is retrieved from the corresponding
454 // field in the MemIntrinsicInfo structure. That field contains
455 // non-negative values only.
456 int getMatchingId() const {
457 if (IsTargetMemInst) return Info.MatchingId;
460 Value *getPointerOperand() const {
461 if (IsTargetMemInst) return Info.PtrVal;
462 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
463 return LI->getPointerOperand();
464 } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
465 return SI->getPointerOperand();
469 bool mayReadFromMemory() const {
470 if (IsTargetMemInst) return Info.ReadMem;
471 return Inst->mayReadFromMemory();
473 bool mayWriteToMemory() const {
474 if (IsTargetMemInst) return Info.WriteMem;
475 return Inst->mayWriteToMemory();
479 bool IsTargetMemInst;
480 MemIntrinsicInfo Info;
484 bool processNode(DomTreeNode *Node);
486 Value *getOrCreateResult(Value *Inst, Type *ExpectedType) const {
487 if (auto *LI = dyn_cast<LoadInst>(Inst))
489 if (auto *SI = dyn_cast<StoreInst>(Inst))
490 return SI->getValueOperand();
491 assert(isa<IntrinsicInst>(Inst) && "Instruction not supported");
492 return TTI.getOrCreateResultFromMemIntrinsic(cast<IntrinsicInst>(Inst),
496 bool isSameMemGeneration(unsigned EarlierGeneration, unsigned LaterGeneration,
497 Instruction *EarlierInst, Instruction *LaterInst);
499 void removeMSSA(Instruction *Inst) {
502 // Removing a store here can leave MemorySSA in an unoptimized state by
503 // creating MemoryPhis that have identical arguments and by creating
504 // MemoryUses whose defining access is not an actual clobber. We handle the
505 // phi case eagerly here. The non-optimized MemoryUse case is lazily
506 // updated by MemorySSA getClobberingMemoryAccess.
507 if (MemoryAccess *MA = MSSA->getMemoryAccess(Inst)) {
508 // Optimize MemoryPhi nodes that may become redundant by having all the
509 // same input values once MA is removed.
510 SmallSetVector<MemoryPhi *, 4> PhisToCheck;
511 SmallVector<MemoryAccess *, 8> WorkQueue;
512 WorkQueue.push_back(MA);
513 // Process MemoryPhi nodes in FIFO order using a ever-growing vector since
514 // we shouldn't be processing that many phis and this will avoid an
515 // allocation in almost all cases.
516 for (unsigned I = 0; I < WorkQueue.size(); ++I) {
517 MemoryAccess *WI = WorkQueue[I];
519 for (auto *U : WI->users())
520 if (MemoryPhi *MP = dyn_cast<MemoryPhi>(U))
521 PhisToCheck.insert(MP);
523 MSSAUpdater->removeMemoryAccess(WI);
525 for (MemoryPhi *MP : PhisToCheck) {
526 MemoryAccess *FirstIn = MP->getIncomingValue(0);
527 if (all_of(MP->incoming_values(),
528 [=](Use &In) { return In == FirstIn; }))
529 WorkQueue.push_back(MP);
538 /// Determine if the memory referenced by LaterInst is from the same heap
539 /// version as EarlierInst.
540 /// This is currently called in two scenarios:
552 /// in both cases we want to verify that there are no possible writes to the
553 /// memory referenced by p between the earlier and later instruction.
554 bool EarlyCSE::isSameMemGeneration(unsigned EarlierGeneration,
555 unsigned LaterGeneration,
556 Instruction *EarlierInst,
557 Instruction *LaterInst) {
558 // Check the simple memory generation tracking first.
559 if (EarlierGeneration == LaterGeneration)
565 // Since we know LaterDef dominates LaterInst and EarlierInst dominates
566 // LaterInst, if LaterDef dominates EarlierInst then it can't occur between
567 // EarlierInst and LaterInst and neither can any other write that potentially
568 // clobbers LaterInst.
569 MemoryAccess *LaterDef =
570 MSSA->getWalker()->getClobberingMemoryAccess(LaterInst);
571 return MSSA->dominates(LaterDef, MSSA->getMemoryAccess(EarlierInst));
574 bool EarlyCSE::processNode(DomTreeNode *Node) {
575 bool Changed = false;
576 BasicBlock *BB = Node->getBlock();
578 // If this block has a single predecessor, then the predecessor is the parent
579 // of the domtree node and all of the live out memory values are still current
580 // in this block. If this block has multiple predecessors, then they could
581 // have invalidated the live-out memory values of our parent value. For now,
582 // just be conservative and invalidate memory if this block has multiple
584 if (!BB->getSinglePredecessor())
587 // If this node has a single predecessor which ends in a conditional branch,
588 // we can infer the value of the branch condition given that we took this
589 // path. We need the single predecessor to ensure there's not another path
590 // which reaches this block where the condition might hold a different
591 // value. Since we're adding this to the scoped hash table (like any other
592 // def), it will have been popped if we encounter a future merge block.
593 if (BasicBlock *Pred = BB->getSinglePredecessor()) {
594 auto *BI = dyn_cast<BranchInst>(Pred->getTerminator());
595 if (BI && BI->isConditional()) {
596 auto *CondInst = dyn_cast<Instruction>(BI->getCondition());
597 if (CondInst && SimpleValue::canHandle(CondInst)) {
598 assert(BI->getSuccessor(0) == BB || BI->getSuccessor(1) == BB);
599 auto *TorF = (BI->getSuccessor(0) == BB)
600 ? ConstantInt::getTrue(BB->getContext())
601 : ConstantInt::getFalse(BB->getContext());
602 AvailableValues.insert(CondInst, TorF);
603 DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"
604 << CondInst->getName() << "' as " << *TorF << " in "
605 << BB->getName() << "\n");
606 // Replace all dominated uses with the known value.
607 if (unsigned Count = replaceDominatedUsesWith(
608 CondInst, TorF, DT, BasicBlockEdge(Pred, BB))) {
616 /// LastStore - Keep track of the last non-volatile store that we saw... for
617 /// as long as there in no instruction that reads memory. If we see a store
618 /// to the same location, we delete the dead store. This zaps trivial dead
619 /// stores which can occur in bitfield code among other things.
620 Instruction *LastStore = nullptr;
622 // See if any instructions in the block can be eliminated. If so, do it. If
623 // not, add them to AvailableValues.
624 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
625 Instruction *Inst = &*I++;
627 // Dead instructions should just be removed.
628 if (isInstructionTriviallyDead(Inst, &TLI)) {
629 DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n');
631 Inst->eraseFromParent();
637 // Skip assume intrinsics, they don't really have side effects (although
638 // they're marked as such to ensure preservation of control dependencies),
639 // and this pass will not bother with its removal. However, we should mark
640 // its condition as true for all dominated blocks.
641 if (match(Inst, m_Intrinsic<Intrinsic::assume>())) {
643 dyn_cast<Instruction>(cast<CallInst>(Inst)->getArgOperand(0));
644 if (CondI && SimpleValue::canHandle(CondI)) {
645 DEBUG(dbgs() << "EarlyCSE considering assumption: " << *Inst << '\n');
646 AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
648 DEBUG(dbgs() << "EarlyCSE skipping assumption: " << *Inst << '\n');
652 // Skip invariant.start intrinsics since they only read memory, and we can
653 // forward values across it. Also, we dont need to consume the last store
654 // since the semantics of invariant.start allow us to perform DSE of the
655 // last store, if there was a store following invariant.start. Consider:
658 // invariant.start(p)
660 // We can DSE the store to 30, since the store 40 to invariant location p
661 // causes undefined behaviour.
662 if (match(Inst, m_Intrinsic<Intrinsic::invariant_start>()))
665 if (match(Inst, m_Intrinsic<Intrinsic::experimental_guard>())) {
667 dyn_cast<Instruction>(cast<CallInst>(Inst)->getArgOperand(0))) {
668 if (SimpleValue::canHandle(CondI)) {
669 // Do we already know the actual value of this condition?
670 if (auto *KnownCond = AvailableValues.lookup(CondI)) {
671 // Is the condition known to be true?
672 if (isa<ConstantInt>(KnownCond) &&
673 cast<ConstantInt>(KnownCond)->isOne()) {
674 DEBUG(dbgs() << "EarlyCSE removing guard: " << *Inst << '\n');
676 Inst->eraseFromParent();
680 // Use the known value if it wasn't true.
681 cast<CallInst>(Inst)->setArgOperand(0, KnownCond);
683 // The condition we're on guarding here is true for all dominated
685 AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
689 // Guard intrinsics read all memory, but don't write any memory.
690 // Accordingly, don't update the generation but consume the last store (to
691 // avoid an incorrect DSE).
696 // If the instruction can be simplified (e.g. X+0 = X) then replace it with
697 // its simpler value.
698 if (Value *V = SimplifyInstruction(Inst, SQ)) {
699 DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << " to: " << *V << '\n');
701 if (!Inst->use_empty()) {
702 Inst->replaceAllUsesWith(V);
705 if (isInstructionTriviallyDead(Inst, &TLI)) {
707 Inst->eraseFromParent();
717 // If this is a simple instruction that we can value number, process it.
718 if (SimpleValue::canHandle(Inst)) {
719 // See if the instruction has an available value. If so, use it.
720 if (Value *V = AvailableValues.lookup(Inst)) {
721 DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << " to: " << *V << '\n');
722 if (auto *I = dyn_cast<Instruction>(V))
724 Inst->replaceAllUsesWith(V);
726 Inst->eraseFromParent();
732 // Otherwise, just remember that this value is available.
733 AvailableValues.insert(Inst, Inst);
737 ParseMemoryInst MemInst(Inst, TTI);
738 // If this is a non-volatile load, process it.
739 if (MemInst.isValid() && MemInst.isLoad()) {
740 // (conservatively) we can't peak past the ordering implied by this
741 // operation, but we can add this load to our set of available values
742 if (MemInst.isVolatile() || !MemInst.isUnordered()) {
747 // If we have an available version of this load, and if it is the right
748 // generation or the load is known to be from an invariant location,
749 // replace this instruction.
751 // If either the dominating load or the current load are invariant, then
752 // we can assume the current load loads the same value as the dominating
754 LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
755 if (InVal.DefInst != nullptr &&
756 InVal.MatchingId == MemInst.getMatchingId() &&
757 // We don't yet handle removing loads with ordering of any kind.
758 !MemInst.isVolatile() && MemInst.isUnordered() &&
759 // We can't replace an atomic load with one which isn't also atomic.
760 InVal.IsAtomic >= MemInst.isAtomic() &&
761 (InVal.IsInvariant || MemInst.isInvariantLoad() ||
762 isSameMemGeneration(InVal.Generation, CurrentGeneration,
763 InVal.DefInst, Inst))) {
764 Value *Op = getOrCreateResult(InVal.DefInst, Inst->getType());
766 DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << *Inst
767 << " to: " << *InVal.DefInst << '\n');
768 if (!Inst->use_empty())
769 Inst->replaceAllUsesWith(Op);
771 Inst->eraseFromParent();
778 // Otherwise, remember that we have this instruction.
779 AvailableLoads.insert(
780 MemInst.getPointerOperand(),
781 LoadValue(Inst, CurrentGeneration, MemInst.getMatchingId(),
782 MemInst.isAtomic(), MemInst.isInvariantLoad()));
787 // If this instruction may read from memory or throw (and potentially read
788 // from memory in the exception handler), forget LastStore. Load/store
789 // intrinsics will indicate both a read and a write to memory. The target
790 // may override this (e.g. so that a store intrinsic does not read from
791 // memory, and thus will be treated the same as a regular store for
792 // commoning purposes).
793 if ((Inst->mayReadFromMemory() || Inst->mayThrow()) &&
794 !(MemInst.isValid() && !MemInst.mayReadFromMemory()))
797 // If this is a read-only call, process it.
798 if (CallValue::canHandle(Inst)) {
799 // If we have an available version of this call, and if it is the right
800 // generation, replace this instruction.
801 std::pair<Instruction *, unsigned> InVal = AvailableCalls.lookup(Inst);
802 if (InVal.first != nullptr &&
803 isSameMemGeneration(InVal.second, CurrentGeneration, InVal.first,
805 DEBUG(dbgs() << "EarlyCSE CSE CALL: " << *Inst
806 << " to: " << *InVal.first << '\n');
807 if (!Inst->use_empty())
808 Inst->replaceAllUsesWith(InVal.first);
810 Inst->eraseFromParent();
816 // Otherwise, remember that we have this instruction.
817 AvailableCalls.insert(
818 Inst, std::pair<Instruction *, unsigned>(Inst, CurrentGeneration));
822 // A release fence requires that all stores complete before it, but does
823 // not prevent the reordering of following loads 'before' the fence. As a
824 // result, we don't need to consider it as writing to memory and don't need
825 // to advance the generation. We do need to prevent DSE across the fence,
826 // but that's handled above.
827 if (FenceInst *FI = dyn_cast<FenceInst>(Inst))
828 if (FI->getOrdering() == AtomicOrdering::Release) {
829 assert(Inst->mayReadFromMemory() && "relied on to prevent DSE above");
833 // write back DSE - If we write back the same value we just loaded from
834 // the same location and haven't passed any intervening writes or ordering
835 // operations, we can remove the write. The primary benefit is in allowing
836 // the available load table to remain valid and value forward past where
837 // the store originally was.
838 if (MemInst.isValid() && MemInst.isStore()) {
839 LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
841 InVal.DefInst == getOrCreateResult(Inst, InVal.DefInst->getType()) &&
842 InVal.MatchingId == MemInst.getMatchingId() &&
843 // We don't yet handle removing stores with ordering of any kind.
844 !MemInst.isVolatile() && MemInst.isUnordered() &&
845 isSameMemGeneration(InVal.Generation, CurrentGeneration,
846 InVal.DefInst, Inst)) {
847 // It is okay to have a LastStore to a different pointer here if MemorySSA
848 // tells us that the load and store are from the same memory generation.
849 // In that case, LastStore should keep its present value since we're
850 // removing the current store.
851 assert((!LastStore ||
852 ParseMemoryInst(LastStore, TTI).getPointerOperand() ==
853 MemInst.getPointerOperand() ||
855 "can't have an intervening store if not using MemorySSA!");
856 DEBUG(dbgs() << "EarlyCSE DSE (writeback): " << *Inst << '\n');
858 Inst->eraseFromParent();
861 // We can avoid incrementing the generation count since we were able
862 // to eliminate this store.
867 // Okay, this isn't something we can CSE at all. Check to see if it is
868 // something that could modify memory. If so, our available memory values
869 // cannot be used so bump the generation count.
870 if (Inst->mayWriteToMemory()) {
873 if (MemInst.isValid() && MemInst.isStore()) {
874 // We do a trivial form of DSE if there are two stores to the same
875 // location with no intervening loads. Delete the earlier store.
876 // At the moment, we don't remove ordered stores, but do remove
877 // unordered atomic stores. There's no special requirement (for
878 // unordered atomics) about removing atomic stores only in favor of
879 // other atomic stores since we we're going to execute the non-atomic
880 // one anyway and the atomic one might never have become visible.
882 ParseMemoryInst LastStoreMemInst(LastStore, TTI);
883 assert(LastStoreMemInst.isUnordered() &&
884 !LastStoreMemInst.isVolatile() &&
885 "Violated invariant");
886 if (LastStoreMemInst.isMatchingMemLoc(MemInst)) {
887 DEBUG(dbgs() << "EarlyCSE DEAD STORE: " << *LastStore
888 << " due to: " << *Inst << '\n');
889 removeMSSA(LastStore);
890 LastStore->eraseFromParent();
895 // fallthrough - we can exploit information about this store
898 // Okay, we just invalidated anything we knew about loaded values. Try
899 // to salvage *something* by remembering that the stored value is a live
900 // version of the pointer. It is safe to forward from volatile stores
901 // to non-volatile loads, so we don't have to check for volatility of
903 AvailableLoads.insert(
904 MemInst.getPointerOperand(),
905 LoadValue(Inst, CurrentGeneration, MemInst.getMatchingId(),
906 MemInst.isAtomic(), /*IsInvariant=*/false));
908 // Remember that this was the last unordered store we saw for DSE. We
909 // don't yet handle DSE on ordered or volatile stores since we don't
910 // have a good way to model the ordering requirement for following
911 // passes once the store is removed. We could insert a fence, but
912 // since fences are slightly stronger than stores in their ordering,
913 // it's not clear this is a profitable transform. Another option would
914 // be to merge the ordering with that of the post dominating store.
915 if (MemInst.isUnordered() && !MemInst.isVolatile())
926 bool EarlyCSE::run() {
927 // Note, deque is being used here because there is significant performance
928 // gains over vector when the container becomes very large due to the
929 // specific access patterns. For more information see the mailing list
930 // discussion on this:
931 // http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html
932 std::deque<StackNode *> nodesToProcess;
934 bool Changed = false;
936 // Process the root node.
937 nodesToProcess.push_back(new StackNode(
938 AvailableValues, AvailableLoads, AvailableCalls, CurrentGeneration,
939 DT.getRootNode(), DT.getRootNode()->begin(), DT.getRootNode()->end()));
941 // Save the current generation.
942 unsigned LiveOutGeneration = CurrentGeneration;
944 // Process the stack.
945 while (!nodesToProcess.empty()) {
946 // Grab the first item off the stack. Set the current generation, remove
947 // the node from the stack, and process it.
948 StackNode *NodeToProcess = nodesToProcess.back();
950 // Initialize class members.
951 CurrentGeneration = NodeToProcess->currentGeneration();
953 // Check if the node needs to be processed.
954 if (!NodeToProcess->isProcessed()) {
956 Changed |= processNode(NodeToProcess->node());
957 NodeToProcess->childGeneration(CurrentGeneration);
958 NodeToProcess->process();
959 } else if (NodeToProcess->childIter() != NodeToProcess->end()) {
960 // Push the next child onto the stack.
961 DomTreeNode *child = NodeToProcess->nextChild();
962 nodesToProcess.push_back(
963 new StackNode(AvailableValues, AvailableLoads, AvailableCalls,
964 NodeToProcess->childGeneration(), child, child->begin(),
967 // It has been processed, and there are no more children to process,
968 // so delete it and pop it off the stack.
969 delete NodeToProcess;
970 nodesToProcess.pop_back();
972 } // while (!nodes...)
974 // Reset the current generation.
975 CurrentGeneration = LiveOutGeneration;
980 PreservedAnalyses EarlyCSEPass::run(Function &F,
981 FunctionAnalysisManager &AM) {
982 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
983 auto &TTI = AM.getResult<TargetIRAnalysis>(F);
984 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
985 auto &AC = AM.getResult<AssumptionAnalysis>(F);
987 UseMemorySSA ? &AM.getResult<MemorySSAAnalysis>(F).getMSSA() : nullptr;
989 EarlyCSE CSE(F.getParent()->getDataLayout(), TLI, TTI, DT, AC, MSSA);
992 return PreservedAnalyses::all();
994 PreservedAnalyses PA;
995 PA.preserveSet<CFGAnalyses>();
996 PA.preserve<GlobalsAA>();
998 PA.preserve<MemorySSAAnalysis>();
1003 /// \brief A simple and fast domtree-based CSE pass.
1005 /// This pass does a simple depth-first walk over the dominator tree,
1006 /// eliminating trivially redundant instructions and using instsimplify to
1007 /// canonicalize things as it goes. It is intended to be fast and catch obvious
1008 /// cases so that instcombine and other passes are more effective. It is
1009 /// expected that a later pass of GVN will catch the interesting/hard cases.
1010 template<bool UseMemorySSA>
1011 class EarlyCSELegacyCommonPass : public FunctionPass {
1015 EarlyCSELegacyCommonPass() : FunctionPass(ID) {
1017 initializeEarlyCSEMemSSALegacyPassPass(*PassRegistry::getPassRegistry());
1019 initializeEarlyCSELegacyPassPass(*PassRegistry::getPassRegistry());
1022 bool runOnFunction(Function &F) override {
1023 if (skipFunction(F))
1026 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1027 auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1028 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1029 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1031 UseMemorySSA ? &getAnalysis<MemorySSAWrapperPass>().getMSSA() : nullptr;
1033 EarlyCSE CSE(F.getParent()->getDataLayout(), TLI, TTI, DT, AC, MSSA);
1038 void getAnalysisUsage(AnalysisUsage &AU) const override {
1039 AU.addRequired<AssumptionCacheTracker>();
1040 AU.addRequired<DominatorTreeWrapperPass>();
1041 AU.addRequired<TargetLibraryInfoWrapperPass>();
1042 AU.addRequired<TargetTransformInfoWrapperPass>();
1044 AU.addRequired<MemorySSAWrapperPass>();
1045 AU.addPreserved<MemorySSAWrapperPass>();
1047 AU.addPreserved<GlobalsAAWrapperPass>();
1048 AU.setPreservesCFG();
1053 using EarlyCSELegacyPass = EarlyCSELegacyCommonPass</*UseMemorySSA=*/false>;
1056 char EarlyCSELegacyPass::ID = 0;
1058 INITIALIZE_PASS_BEGIN(EarlyCSELegacyPass, "early-cse", "Early CSE", false,
1060 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
1061 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
1062 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1063 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
1064 INITIALIZE_PASS_END(EarlyCSELegacyPass, "early-cse", "Early CSE", false, false)
1066 using EarlyCSEMemSSALegacyPass =
1067 EarlyCSELegacyCommonPass</*UseMemorySSA=*/true>;
1070 char EarlyCSEMemSSALegacyPass::ID = 0;
1072 FunctionPass *llvm::createEarlyCSEPass(bool UseMemorySSA) {
1074 return new EarlyCSEMemSSALegacyPass();
1076 return new EarlyCSELegacyPass();
1079 INITIALIZE_PASS_BEGIN(EarlyCSEMemSSALegacyPass, "early-cse-memssa",
1080 "Early CSE w/ MemorySSA", false, false)
1081 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
1082 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
1083 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1084 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
1085 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
1086 INITIALIZE_PASS_END(EarlyCSEMemSSALegacyPass, "early-cse-memssa",
1087 "Early CSE w/ MemorySSA", false, false)