LLVM 24.0.0git
EarlyCSE.cpp
Go to the documentation of this file.
1//===- EarlyCSE.cpp - Simple and fast CSE pass ----------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass performs a simple dominator tree walk that eliminates trivially
10// redundant instructions.
11//
12//===----------------------------------------------------------------------===//
13
15#include "ScalarOptions.h"
17#include "llvm/ADT/Hashing.h"
18#include "llvm/ADT/STLExtras.h"
21#include "llvm/ADT/Statistic.h"
31#include "llvm/IR/BasicBlock.h"
32#include "llvm/IR/Constants.h"
33#include "llvm/IR/Dominators.h"
34#include "llvm/IR/Function.h"
35#include "llvm/IR/InstrTypes.h"
36#include "llvm/IR/Instruction.h"
39#include "llvm/IR/LLVMContext.h"
40#include "llvm/IR/PassManager.h"
42#include "llvm/IR/Type.h"
43#include "llvm/IR/Value.h"
45#include "llvm/Pass.h"
49#include "llvm/Support/Debug.h"
56#include <cassert>
57#include <deque>
58#include <memory>
59#include <utility>
60
61using namespace llvm;
62using namespace llvm::PatternMatch;
63
64#define DEBUG_TYPE "early-cse"
65
66STATISTIC(NumSimplify, "Number of instructions simplified or DCE'd");
67STATISTIC(NumCSE, "Number of instructions CSE'd");
68STATISTIC(NumCSECVP, "Number of compare instructions CVP'd");
69STATISTIC(NumCSELoad, "Number of load instructions CSE'd");
70STATISTIC(NumCSECall, "Number of call instructions CSE'd");
71STATISTIC(NumCSEGEP, "Number of GEP instructions CSE'd");
72STATISTIC(NumDSE, "Number of trivial dead stores removed");
73
74DEBUG_COUNTER(CSECounter, "early-cse",
75 "Controls which instructions are removed");
76
77//===----------------------------------------------------------------------===//
78// SimpleValue
79//===----------------------------------------------------------------------===//
80
81namespace {
82
83/// Struct representing the available values in the scoped hash table.
84struct SimpleValue {
85 Instruction *Inst;
86
87 SimpleValue(Instruction *I) : Inst(I) {
88 assert(canHandle(I) && "Inst can't be handled!");
89 }
90
91 static bool canHandle(Instruction *Inst) {
92 // This can only handle non-void readnone functions.
93 // Also handled are constrained intrinsic that look like the types
94 // of instruction handled below (UnaryOperator, etc.).
95 if (CallInst *CI = dyn_cast<CallInst>(Inst)) {
96 if (Function *F = CI->getCalledFunction()) {
97 switch (F->getIntrinsicID()) {
98 case Intrinsic::experimental_constrained_fadd:
99 case Intrinsic::experimental_constrained_fsub:
100 case Intrinsic::experimental_constrained_fmul:
101 case Intrinsic::experimental_constrained_fdiv:
102 case Intrinsic::experimental_constrained_frem:
103 case Intrinsic::experimental_constrained_fptosi:
104 case Intrinsic::experimental_constrained_sitofp:
105 case Intrinsic::experimental_constrained_fptoui:
106 case Intrinsic::experimental_constrained_uitofp:
107 case Intrinsic::experimental_constrained_fcmp:
108 case Intrinsic::experimental_constrained_fcmps: {
109 auto *CFP = cast<ConstrainedFPIntrinsic>(CI);
110 if (CFP->getExceptionBehavior() &&
111 CFP->getExceptionBehavior() == fp::ebStrict)
112 return false;
113 // Since we CSE across function calls we must not allow
114 // the rounding mode to change.
115 if (CFP->getRoundingMode() &&
116 CFP->getRoundingMode() == RoundingMode::Dynamic)
117 return false;
118 return true;
119 }
120 }
121 }
122 return CI->doesNotAccessMemory() &&
123 // FIXME: Currently the calls which may access the thread id may
124 // be considered as not accessing the memory. But this is
125 // problematic for coroutines, since coroutines may resume in a
126 // different thread. So we disable the optimization here for the
127 // correctness. However, it may block many other correct
128 // optimizations. Revert this one when we detect the memory
129 // accessing kind more precisely.
130 !CI->getFunction()->isPresplitCoroutine();
131 }
132 return isa<CastInst>(Inst) || isa<UnaryOperator>(Inst) ||
133 isa<BinaryOperator>(Inst) || isa<CmpInst>(Inst) ||
137 isa<FreezeInst>(Inst) || isa<BitExtractInst>(Inst) ||
138 isa<BitInsertInst>(Inst);
139 }
140};
141
142} // end anonymous namespace
143
144template <> struct llvm::DenseMapInfo<SimpleValue> {
145 static unsigned getHashValue(SimpleValue Val);
146 static bool isEqual(SimpleValue LHS, SimpleValue RHS);
147};
148
149/// Match a 'select' including an optional 'not's of the condition.
151 Value *&B) {
152 // Return false if V is not even a select.
154 return false;
155
156 // Look through a 'not' of the condition operand by swapping A/B.
157 Value *CondNot;
158 if (match(Cond, m_Not(m_Value(CondNot)))) {
159 Cond = CondNot;
160 std::swap(A, B);
161 }
162
163 return true;
164}
165
166static unsigned hashCallInst(CallInst *CI) {
167 // Don't CSE convergent calls in different basic blocks, because they
168 // implicitly depend on the set of threads that is currently executing.
169 if (CI->isConvergent()) {
170 return hash_combine(CI->getOpcode(), CI->getParent(),
172 }
173 return hash_combine(CI->getOpcode(),
175}
176
177static unsigned getHashValueImpl(SimpleValue Val) {
178 Instruction *Inst = Val.Inst;
179 // Hash in all of the operands as pointers.
180 if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst)) {
181 Value *LHS = BinOp->getOperand(0);
182 Value *RHS = BinOp->getOperand(1);
183 if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1))
184 std::swap(LHS, RHS);
185
186 return hash_combine(BinOp->getOpcode(), LHS, RHS);
187 }
188
189 if (CmpInst *CI = dyn_cast<CmpInst>(Inst)) {
190 // Compares can be commuted by swapping the comparands and
191 // updating the predicate. Choose the form that has the
192 // comparands in sorted order, or in the case of a tie, the
193 // one with the lower predicate.
194 Value *LHS = CI->getOperand(0);
195 Value *RHS = CI->getOperand(1);
196 CmpInst::Predicate Pred = CI->getPredicate();
197 CmpInst::Predicate SwappedPred = CI->getSwappedPredicate();
198 if (std::tie(LHS, Pred) > std::tie(RHS, SwappedPred)) {
199 std::swap(LHS, RHS);
200 Pred = SwappedPred;
201 }
202 return hash_combine(Inst->getOpcode(), Pred, LHS, RHS);
203 }
204
205 // Hash general selects to allow matching commuted true/false operands.
206 Value *Cond, *A, *B;
207 if (matchSelectWithOptionalNotCond(Inst, Cond, A, B)) {
208 // Hash general selects to allow matching commuted true/false operands.
209
210 // If we do not have a compare as the condition, just hash in the condition.
212 Value *X, *Y;
213 if (!match(Cond, m_Cmp(Pred, m_Value(X), m_Value(Y))))
214 return hash_combine(Inst->getOpcode(), Cond, A, B);
215
216 // Similar to cmp normalization (above) - canonicalize the predicate value:
217 // select (icmp Pred, X, Y), A, B --> select (icmp InvPred, X, Y), B, A
220 std::swap(A, B);
221 }
222 return hash_combine(Inst->getOpcode(),
223 static_cast<CmpInst::Predicate>(Pred), X, Y, A, B);
224 }
225
226 if (CastInst *CI = dyn_cast<CastInst>(Inst))
227 return hash_combine(CI->getOpcode(), CI->getType(), CI->getOperand(0));
228
229 if (FreezeInst *FI = dyn_cast<FreezeInst>(Inst))
230 return hash_combine(FI->getOpcode(), FI->getOperand(0));
231
232 if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Inst))
233 return hash_combine(EVI->getOpcode(), EVI->getOperand(0),
234 hash_combine_range(EVI->indices()));
235
236 if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Inst))
237 return hash_combine(IVI->getOpcode(), IVI->getOperand(0),
238 IVI->getOperand(1), hash_combine_range(IVI->indices()));
239
242 isa<UnaryOperator>(Inst) || isa<FreezeInst>(Inst) ||
243 isa<BitExtractInst>(Inst) || isa<BitInsertInst>(Inst)) &&
244 "Invalid/unknown instruction");
245
246 // Handle intrinsics with commutative operands.
247 auto *II = dyn_cast<IntrinsicInst>(Inst);
248 if (II && II->isCommutative() && II->arg_size() >= 2) {
249 Value *LHS = II->getArgOperand(0), *RHS = II->getArgOperand(1);
250 if (LHS > RHS)
251 std::swap(LHS, RHS);
252 return hash_combine(
253 II->getOpcode(), LHS, RHS,
254 hash_combine_range(drop_begin(II->operand_values(), 2)));
255 }
256
257 // gc.relocate is 'special' call: its second and third operands are
258 // not real values, but indices into statepoint's argument list.
259 // Get values they point to.
260 if (const GCRelocateInst *GCR = dyn_cast<GCRelocateInst>(Inst))
261 return hash_combine(GCR->getOpcode(), GCR->getOperand(0),
262 GCR->getBasePtr(), GCR->getDerivedPtr());
263
264 // Don't CSE convergent calls in different basic blocks, because they
265 // implicitly depend on the set of threads that is currently executing.
266 if (CallInst *CI = dyn_cast<CallInst>(Inst))
267 return hashCallInst(CI);
268
269 // Mix in the opcode.
270 return hash_combine(Inst->getOpcode(),
272}
273
274unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
275#ifndef NDEBUG
276 // If -earlycse-debug-hash was specified, return a constant -- this
277 // will force all hashing to collide, so we'll exhaustively search
278 // the table for a match, and the assertion in isEqual will fire if
279 // there's a bug causing equal keys to hash differently.
280 if (getScalarOptions(*Val.Inst->getFunction()).earlycse_debug_hash)
281 return 0;
282#endif
283 return getHashValueImpl(Val);
284}
285
286static bool isEqualImpl(SimpleValue LHS, SimpleValue RHS) {
287 Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
288
289 if (LHSI->getOpcode() != RHSI->getOpcode())
290 return false;
291 if (LHSI->isIdenticalToWhenDefined(RHSI, /*IntersectAttrs=*/true)) {
292 // Convergent calls implicitly depend on the set of threads that is
293 // currently executing, so conservatively return false if they are in
294 // different basic blocks.
295 if (CallInst *CI = dyn_cast<CallInst>(LHSI);
296 CI && CI->isConvergent() && LHSI->getParent() != RHSI->getParent())
297 return false;
298
299 return true;
300 }
301
302 // If we're not strictly identical, we still might be a commutable instruction
303 if (BinaryOperator *LHSBinOp = dyn_cast<BinaryOperator>(LHSI)) {
304 if (!LHSBinOp->isCommutative())
305 return false;
306
308 "same opcode, but different instruction type?");
309 BinaryOperator *RHSBinOp = cast<BinaryOperator>(RHSI);
310
311 // Commuted equality
312 return LHSBinOp->getOperand(0) == RHSBinOp->getOperand(1) &&
313 LHSBinOp->getOperand(1) == RHSBinOp->getOperand(0);
314 }
315 if (CmpInst *LHSCmp = dyn_cast<CmpInst>(LHSI)) {
316 assert(isa<CmpInst>(RHSI) &&
317 "same opcode, but different instruction type?");
318 CmpInst *RHSCmp = cast<CmpInst>(RHSI);
319 // Commuted equality
320 return LHSCmp->getOperand(0) == RHSCmp->getOperand(1) &&
321 LHSCmp->getOperand(1) == RHSCmp->getOperand(0) &&
322 LHSCmp->getSwappedPredicate() == RHSCmp->getPredicate();
323 }
324
325 auto *LII = dyn_cast<IntrinsicInst>(LHSI);
326 auto *RII = dyn_cast<IntrinsicInst>(RHSI);
327 if (LII && RII && LII->getIntrinsicID() == RII->getIntrinsicID() &&
328 LII->isCommutative() && LII->arg_size() >= 2) {
329 return LII->getArgOperand(0) == RII->getArgOperand(1) &&
330 LII->getArgOperand(1) == RII->getArgOperand(0) &&
331 std::equal(LII->arg_begin() + 2, LII->arg_end(),
332 RII->arg_begin() + 2, RII->arg_end()) &&
333 LII->hasSameSpecialState(RII, /*IgnoreAlignment=*/false,
334 /*IntersectAttrs=*/true);
335 }
336
337 // See comment above in `getHashValue()`.
338 if (const GCRelocateInst *GCR1 = dyn_cast<GCRelocateInst>(LHSI))
339 if (const GCRelocateInst *GCR2 = dyn_cast<GCRelocateInst>(RHSI))
340 return GCR1->getOperand(0) == GCR2->getOperand(0) &&
341 GCR1->getBasePtr() == GCR2->getBasePtr() &&
342 GCR1->getDerivedPtr() == GCR2->getDerivedPtr();
343
344 // Selects can be non-trivially equivalent via inverted conditions and swaps.
345 Value *CondL, *CondR, *LHSA, *RHSA, *LHSB, *RHSB;
346 if (matchSelectWithOptionalNotCond(LHSI, CondL, LHSA, LHSB) &&
347 matchSelectWithOptionalNotCond(RHSI, CondR, RHSA, RHSB)) {
348 // select Cond, A, B <--> select not(Cond), B, A
349 if (CondL == CondR && LHSA == RHSA && LHSB == RHSB)
350 return true;
351
352 // If the true/false operands are swapped and the conditions are compares
353 // with inverted predicates, the selects are equal:
354 // select (icmp Pred, X, Y), A, B <--> select (icmp InvPred, X, Y), B, A
355 //
356 // This also handles patterns with a double-negation in the sense of not +
357 // inverse, because we looked through a 'not' in the matching function and
358 // swapped A/B:
359 // select (cmp Pred, X, Y), A, B <--> select (not (cmp InvPred, X, Y)), B, A
360 if (LHSA == RHSB && LHSB == RHSA) {
361 CmpPredicate PredL, PredR;
362 Value *X, *Y;
363 if (match(CondL, m_Cmp(PredL, m_Value(X), m_Value(Y))) &&
364 match(CondR, m_Cmp(PredR, m_Specific(X), m_Specific(Y))) &&
365 CmpInst::getInversePredicate(PredL) == PredR)
366 return true;
367 }
368 }
369
370 return false;
371}
372
373bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
374 // These comparisons are nontrivial, so assert that equality implies
375 // hash equality (DenseMap demands this as an invariant).
376 bool Result = isEqualImpl(LHS, RHS);
378 return Result;
379}
380
381//===----------------------------------------------------------------------===//
382// CallValue
383//===----------------------------------------------------------------------===//
384
385namespace {
386
387/// Struct representing the available call values in the scoped hash
388/// table.
389struct CallValue {
390 Instruction *Inst;
391
392 CallValue(Instruction *I) : Inst(I) {
393 assert(canHandle(I) && "Inst can't be handled!");
394 }
395
396 static bool canHandle(Instruction *Inst) {
397 CallInst *CI = dyn_cast<CallInst>(Inst);
398 if (!CI || (!CI->onlyReadsMemory() && !CI->onlyWritesMemory()) ||
399 // FIXME: Currently the calls which may access the thread id may
400 // be considered as not accessing the memory. But this is
401 // problematic for coroutines, since coroutines may resume in a
402 // different thread. So we disable the optimization here for the
403 // correctness. However, it may block many other correct
404 // optimizations. Revert this one when we detect the memory
405 // accessing kind more precisely.
407 return false;
408 return true;
409 }
410};
411
412} // end anonymous namespace
413
414template <> struct llvm::DenseMapInfo<CallValue> {
415 static unsigned getHashValue(CallValue Val);
416 static bool isEqual(CallValue LHS, CallValue RHS);
417};
418
419unsigned DenseMapInfo<CallValue>::getHashValue(CallValue Val) {
420 Instruction *Inst = Val.Inst;
421
422 // Hash all of the operands as pointers and mix in the opcode.
423 return hashCallInst(cast<CallInst>(Inst));
424}
425
426bool DenseMapInfo<CallValue>::isEqual(CallValue LHS, CallValue RHS) {
427 CallInst *LHSI = cast<CallInst>(LHS.Inst);
428 CallInst *RHSI = cast<CallInst>(RHS.Inst);
429
430 // Convergent calls implicitly depend on the set of threads that is
431 // currently executing, so conservatively return false if they are in
432 // different basic blocks.
433 if (LHSI->isConvergent() && LHSI->getParent() != RHSI->getParent())
434 return false;
435
436 return LHSI->isIdenticalToWhenDefined(RHSI, /*IntersectAttrs=*/true);
437}
438
439//===----------------------------------------------------------------------===//
440// GEPValue
441//===----------------------------------------------------------------------===//
442
443namespace {
444
445struct GEPValue {
446 Instruction *Inst;
447 std::optional<int64_t> ConstantOffset;
448
449 GEPValue(Instruction *I) : Inst(I) {
450 assert(canHandle(I) && "Inst can't be handled!");
451 }
452
453 GEPValue(Instruction *I, std::optional<int64_t> ConstantOffset)
454 : Inst(I), ConstantOffset(ConstantOffset) {
455 assert(canHandle(I) && "Inst can't be handled!");
456 }
457
458 static bool canHandle(Instruction *Inst) {
459 return isa<GetElementPtrInst>(Inst);
460 }
461};
462
463} // namespace
464
465template <> struct llvm::DenseMapInfo<GEPValue> {
466 static unsigned getHashValue(const GEPValue &Val);
467 static bool isEqual(const GEPValue &LHS, const GEPValue &RHS);
468};
469
470unsigned DenseMapInfo<GEPValue>::getHashValue(const GEPValue &Val) {
471 auto *GEP = cast<GetElementPtrInst>(Val.Inst);
472 if (Val.ConstantOffset.has_value())
473 return hash_combine(GEP->getOpcode(), GEP->getPointerOperand(),
474 Val.ConstantOffset.value());
475 return hash_combine(GEP->getOpcode(),
476 hash_combine_range(GEP->operand_values()));
477}
478
479bool DenseMapInfo<GEPValue>::isEqual(const GEPValue &LHS, const GEPValue &RHS) {
480 auto *LGEP = cast<GetElementPtrInst>(LHS.Inst);
481 auto *RGEP = cast<GetElementPtrInst>(RHS.Inst);
482 if (LGEP->getPointerOperand() != RGEP->getPointerOperand())
483 return false;
484 if (LHS.ConstantOffset.has_value() && RHS.ConstantOffset.has_value())
485 return LHS.ConstantOffset.value() == RHS.ConstantOffset.value();
486 return LGEP->isIdenticalToWhenDefined(RGEP);
487}
488
489//===----------------------------------------------------------------------===//
490// EarlyCSE implementation
491//===----------------------------------------------------------------------===//
492
493namespace {
494
495/// A simple and fast domtree-based CSE pass.
496///
497/// This pass does a simple depth-first walk over the dominator tree,
498/// eliminating trivially redundant instructions and using instsimplify to
499/// canonicalize things as it goes. It is intended to be fast and catch obvious
500/// cases so that instcombine and other passes are more effective. It is
501/// expected that a later pass of GVN will catch the interesting/hard cases.
502class EarlyCSE {
503public:
504 const ScalarOptions &Opts;
505 const TargetLibraryInfo &TLI;
506 const TargetTransformInfo &TTI;
507 DominatorTree &DT;
508 AssumptionCache &AC;
509 const SimplifyQuery SQ;
510 MemorySSA *MSSA;
511 std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
512
513 using AllocatorTy =
514 RecyclingAllocator<BumpPtrAllocator,
515 ScopedHashTableVal<SimpleValue, Value *>>;
516 using ScopedHTType =
517 ScopedHashTable<SimpleValue, Value *, DenseMapInfo<SimpleValue>,
518 AllocatorTy>;
519
520 /// A scoped hash table of the current values of all of our simple
521 /// scalar expressions.
522 ///
523 /// As we walk down the domtree, we look to see if instructions are in this:
524 /// if so, we replace them with what we find, otherwise we insert them so
525 /// that dominated values can succeed in their lookup.
526 ScopedHTType AvailableValues;
527
528 /// A scoped hash table of the current values of previously encountered
529 /// memory locations.
530 ///
531 /// This allows us to get efficient access to dominating loads or stores when
532 /// we have a fully redundant load. In addition to the most recent load, we
533 /// keep track of a generation count of the read, which is compared against
534 /// the current generation count. The current generation count is incremented
535 /// after every possibly writing memory operation, which ensures that we only
536 /// CSE loads with other loads that have no intervening store. Ordering
537 /// events (such as fences or atomic instructions) increment the generation
538 /// count as well; essentially, we model these as writes to all possible
539 /// locations. Note that atomic and/or volatile loads and stores can be
540 /// present the table; it is the responsibility of the consumer to inspect
541 /// the atomicity/volatility if needed.
542 struct LoadValue {
543 Instruction *DefInst = nullptr;
544 unsigned Generation = 0;
545 int MatchingId = -1;
546 bool IsAtomic = false;
547 bool IsLoad = false;
548
549 LoadValue() = default;
550 LoadValue(Instruction *Inst, unsigned Generation, unsigned MatchingId,
551 bool IsAtomic, bool IsLoad)
552 : DefInst(Inst), Generation(Generation), MatchingId(MatchingId),
553 IsAtomic(IsAtomic), IsLoad(IsLoad) {}
554 };
555
556 using LoadMapAllocator =
557 RecyclingAllocator<BumpPtrAllocator,
558 ScopedHashTableVal<Value *, LoadValue>>;
559 using LoadHTType =
560 ScopedHashTable<Value *, LoadValue, DenseMapInfo<Value *>,
561 LoadMapAllocator>;
562
563 LoadHTType AvailableLoads;
564
565 // A scoped hash table mapping memory locations (represented as typed
566 // addresses) to generation numbers at which that memory location became
567 // (henceforth indefinitely) invariant.
568 using InvariantMapAllocator =
569 RecyclingAllocator<BumpPtrAllocator,
570 ScopedHashTableVal<MemoryLocation, unsigned>>;
571 using InvariantHTType =
572 ScopedHashTable<MemoryLocation, unsigned, DenseMapInfo<MemoryLocation>,
573 InvariantMapAllocator>;
574 InvariantHTType AvailableInvariants;
575
576 /// A scoped hash table of the current values of read-only call
577 /// values.
578 ///
579 /// It uses the same generation count as loads.
580 using CallHTType =
581 ScopedHashTable<CallValue, std::pair<Instruction *, unsigned>>;
582 CallHTType AvailableCalls;
583
584 using GEPMapAllocatorTy =
585 RecyclingAllocator<BumpPtrAllocator,
586 ScopedHashTableVal<GEPValue, Value *>>;
587 using GEPHTType = ScopedHashTable<GEPValue, Value *, DenseMapInfo<GEPValue>,
588 GEPMapAllocatorTy>;
589 GEPHTType AvailableGEPs;
590
591 /// This is the current generation of the memory value.
592 unsigned CurrentGeneration = 0;
593
594 /// Set up the EarlyCSE runner for a particular function.
595 EarlyCSE(const ScalarOptions &Opts, const DataLayout &DL,
596 const TargetLibraryInfo &TLI, const TargetTransformInfo &TTI,
597 DominatorTree &DT, AssumptionCache &AC, MemorySSA *MSSA)
598 : Opts(Opts), TLI(TLI), TTI(TTI), DT(DT), AC(AC), SQ(DL, &TLI, &DT, &AC),
599 MSSA(MSSA), MSSAUpdater(std::make_unique<MemorySSAUpdater>(MSSA)) {}
600
601 bool run();
602
603private:
604 unsigned ClobberCounter = 0;
605 // Almost a POD, but needs to call the constructors for the scoped hash
606 // tables so that a new scope gets pushed on. These are RAII so that the
607 // scope gets popped when the NodeScope is destroyed.
608 class NodeScope {
609 public:
610 NodeScope(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
611 InvariantHTType &AvailableInvariants, CallHTType &AvailableCalls,
612 GEPHTType &AvailableGEPs)
613 : Scope(AvailableValues), LoadScope(AvailableLoads),
614 InvariantScope(AvailableInvariants), CallScope(AvailableCalls),
615 GEPScope(AvailableGEPs) {}
616 NodeScope(const NodeScope &) = delete;
617 NodeScope &operator=(const NodeScope &) = delete;
618
619 private:
621 LoadHTType::ScopeTy LoadScope;
622 InvariantHTType::ScopeTy InvariantScope;
623 CallHTType::ScopeTy CallScope;
624 GEPHTType::ScopeTy GEPScope;
625 };
626
627 // Contains all the needed information to create a stack for doing a depth
628 // first traversal of the tree. This includes scopes for values, loads, and
629 // calls as well as the generation. There is a child iterator so that the
630 // children do not need to be store separately.
631 class StackNode {
632 public:
633 StackNode(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
634 InvariantHTType &AvailableInvariants, CallHTType &AvailableCalls,
635 GEPHTType &AvailableGEPs, unsigned cg, DomTreeNode *n,
636 DomTreeNode::const_iterator child,
637 DomTreeNode::const_iterator end)
638 : CurrentGeneration(cg), ChildGeneration(cg), Node(n), ChildIter(child),
639 EndIter(end),
640 Scopes(AvailableValues, AvailableLoads, AvailableInvariants,
641 AvailableCalls, AvailableGEPs) {}
642 StackNode(const StackNode &) = delete;
643 StackNode &operator=(const StackNode &) = delete;
644
645 // Accessors.
646 unsigned currentGeneration() const { return CurrentGeneration; }
647 unsigned childGeneration() const { return ChildGeneration; }
648 void childGeneration(unsigned generation) { ChildGeneration = generation; }
649 DomTreeNode *node() { return Node; }
650 DomTreeNode::const_iterator childIter() const { return ChildIter; }
651
652 DomTreeNode *nextChild() {
653 DomTreeNode *child = *ChildIter;
654 ++ChildIter;
655 return child;
656 }
657
658 DomTreeNode::const_iterator end() const { return EndIter; }
659 bool isProcessed() const { return Processed; }
660 void process() { Processed = true; }
661
662 private:
663 unsigned CurrentGeneration;
664 unsigned ChildGeneration;
665 DomTreeNode *Node;
666 DomTreeNode::const_iterator ChildIter;
667 DomTreeNode::const_iterator EndIter;
668 NodeScope Scopes;
669 bool Processed = false;
670 };
671
672 /// Wrapper class to handle memory instructions, including loads,
673 /// stores and intrinsic loads and stores defined by the target.
674 class ParseMemoryInst {
675 public:
676 ParseMemoryInst(Instruction *Inst, const TargetTransformInfo &TTI)
677 : Inst(Inst) {
678 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
679 IntrID = II->getIntrinsicID();
680 if (TTI.getTgtMemIntrinsic(II, Info))
681 return;
682 if (isHandledNonTargetIntrinsic(IntrID)) {
683 switch (IntrID) {
684 case Intrinsic::masked_load:
685 Info.PtrVal = Inst->getOperand(0);
686 Info.MatchingId = Intrinsic::masked_load;
687 Info.ReadMem = true;
688 Info.WriteMem = false;
689 Info.IsVolatile = false;
690 break;
691 case Intrinsic::masked_store:
692 Info.PtrVal = Inst->getOperand(1);
693 // Use the ID of masked load as the "matching id". This will
694 // prevent matching non-masked loads/stores with masked ones
695 // (which could be done), but at the moment, the code here
696 // does not support matching intrinsics with non-intrinsics,
697 // so keep the MatchingIds specific to masked instructions
698 // for now (TODO).
699 Info.MatchingId = Intrinsic::masked_load;
700 Info.ReadMem = false;
701 Info.WriteMem = true;
702 Info.IsVolatile = false;
703 break;
704 }
705 } else if (auto *MI = dyn_cast<MemSetInst>(Inst)) {
706 Info.PtrVal = MI->getDest();
707 Info.MatchingId = 0;
708 Info.ReadMem = false;
709 Info.WriteMem = true;
710 Info.IsVolatile = MI->isVolatile();
711 }
712 }
713 }
714
715 Instruction *get() { return Inst; }
716 const Instruction *get() const { return Inst; }
717
718 bool isLoad() const {
719 if (IntrID != 0)
720 return Info.ReadMem;
721 return isa<LoadInst>(Inst);
722 }
723
724 bool isStore() const {
725 if (IntrID != 0)
726 return Info.WriteMem;
727 return isa<StoreInst>(Inst);
728 }
729
730 bool isAtomic() const {
731 if (IntrID != 0)
732 return Info.Ordering != AtomicOrdering::NotAtomic;
733 return Inst->isAtomic();
734 }
735
736 bool isUnordered() const {
737 if (IntrID != 0)
738 return Info.isUnordered();
739
740 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
741 return LI->isUnordered();
742 } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
743 return SI->isUnordered();
744 }
745 // Conservative answer
746 return !Inst->isAtomic();
747 }
748
749 bool isVolatile() const {
750 if (IntrID != 0)
751 return Info.IsVolatile;
752
753 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
754 return LI->isVolatile();
755 } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
756 return SI->isVolatile();
757 }
758 // Conservative answer
759 return true;
760 }
761
762 bool isInvariantLoad() const {
763 if (auto *LI = dyn_cast<LoadInst>(Inst))
764 return LI->hasMetadata(LLVMContext::MD_invariant_load);
765 return false;
766 }
767
768 bool isValid() const { return getPointerOperand() != nullptr; }
769
770 // For regular (non-intrinsic) loads/stores, this is set to -1. For
771 // intrinsic loads/stores, the id is retrieved from the corresponding
772 // field in the MemIntrinsicInfo structure. That field contains
773 // non-negative values only.
774 int getMatchingId() const {
775 if (IntrID != 0)
776 return Info.MatchingId;
777 return -1;
778 }
779
780 Value *getPointerOperand() const {
781 if (IntrID != 0)
782 return Info.PtrVal;
783 return getLoadStorePointerOperand(Inst);
784 }
785
786 Type *getValueType() const {
787 // TODO: handle target-specific intrinsics.
788 return Inst->getAccessType();
789 }
790
791 bool mayReadFromMemory() const {
792 if (IntrID != 0)
793 return Info.ReadMem;
794 return Inst->mayReadFromMemory();
795 }
796
797 bool mayWriteToMemory() const {
798 if (IntrID != 0)
799 return Info.WriteMem;
800 return Inst->mayWriteToMemory();
801 }
802
803 private:
804 Intrinsic::ID IntrID = 0;
805 MemIntrinsicInfo Info;
806 Instruction *Inst;
807 };
808
809 // This function is to prevent accidentally passing a non-target
810 // intrinsic ID to TargetTransformInfo.
811 static bool isHandledNonTargetIntrinsic(Intrinsic::ID ID) {
812 switch (ID) {
813 case Intrinsic::masked_load:
814 case Intrinsic::masked_store:
815 return true;
816 }
817 return false;
818 }
819 static bool isHandledNonTargetIntrinsic(const Value *V) {
820 if (auto *II = dyn_cast<IntrinsicInst>(V))
821 return isHandledNonTargetIntrinsic(II->getIntrinsicID());
822 return false;
823 }
824
825 bool processNode(DomTreeNode *Node);
826
827 bool handleBranchCondition(Instruction *CondInst, const CondBrInst *BI,
828 const BasicBlock *BB, const BasicBlock *Pred);
829
830 Value *getMatchingValue(LoadValue &InVal, ParseMemoryInst &MemInst,
831 unsigned CurrentGeneration);
832
833 bool overridingStores(const ParseMemoryInst &Earlier,
834 const ParseMemoryInst &Later);
835
836 Value *getOrCreateResult(Instruction *Inst, Type *ExpectedType,
837 bool CanCreate) const {
838 // TODO: We could insert relevant casts on type mismatch.
839 // The load or the store's first operand.
840 Value *V;
841 if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
842 switch (II->getIntrinsicID()) {
843 case Intrinsic::masked_load:
844 V = II;
845 break;
846 case Intrinsic::masked_store:
847 V = II->getOperand(0);
848 break;
849 default:
850 return TTI.getOrCreateResultFromMemIntrinsic(II, ExpectedType,
851 CanCreate);
852 }
853 } else {
854 V = isa<LoadInst>(Inst) ? Inst : cast<StoreInst>(Inst)->getValueOperand();
855 }
856
857 return V->getType() == ExpectedType ? V : nullptr;
858 }
859
860 /// Return true if the instruction is known to only operate on memory
861 /// provably invariant in the given "generation".
862 bool isOperatingOnInvariantMemAt(Instruction *I, unsigned GenAt);
863
864 bool isSameMemGeneration(unsigned EarlierGeneration, unsigned LaterGeneration,
865 Instruction *EarlierInst, Instruction *LaterInst);
866
867 bool isNonTargetIntrinsicMatch(const IntrinsicInst *Earlier,
868 const IntrinsicInst *Later) {
869 auto IsSubmask = [](const Value *Mask0, const Value *Mask1) {
870 // Is Mask0 a submask of Mask1?
871 if (Mask0 == Mask1)
872 return true;
873 if (isa<UndefValue>(Mask0) || isa<UndefValue>(Mask1))
874 return false;
875 auto *Vec0 = dyn_cast<ConstantVector>(Mask0);
876 auto *Vec1 = dyn_cast<ConstantVector>(Mask1);
877 if (!Vec0 || !Vec1)
878 return false;
879 if (Vec0->getType() != Vec1->getType())
880 return false;
881 for (int i = 0, e = Vec0->getNumOperands(); i != e; ++i) {
882 Constant *Elem0 = Vec0->getOperand(i);
883 Constant *Elem1 = Vec1->getOperand(i);
884 auto *Int0 = dyn_cast<ConstantInt>(Elem0);
885 if (Int0 && Int0->isZero())
886 continue;
887 auto *Int1 = dyn_cast<ConstantInt>(Elem1);
888 if (Int1 && !Int1->isZero())
889 continue;
890 if (isa<UndefValue>(Elem0) || isa<UndefValue>(Elem1))
891 return false;
892 if (Elem0 == Elem1)
893 continue;
894 return false;
895 }
896 return true;
897 };
898 auto PtrOp = [](const IntrinsicInst *II) {
899 if (II->getIntrinsicID() == Intrinsic::masked_load)
900 return II->getOperand(0);
901 if (II->getIntrinsicID() == Intrinsic::masked_store)
902 return II->getOperand(1);
903 llvm_unreachable("Unexpected IntrinsicInst");
904 };
905 auto MaskOp = [](const IntrinsicInst *II) {
906 if (II->getIntrinsicID() == Intrinsic::masked_load)
907 return II->getOperand(1);
908 if (II->getIntrinsicID() == Intrinsic::masked_store)
909 return II->getOperand(2);
910 llvm_unreachable("Unexpected IntrinsicInst");
911 };
912 auto ThruOp = [](const IntrinsicInst *II) {
913 if (II->getIntrinsicID() == Intrinsic::masked_load)
914 return II->getOperand(2);
915 llvm_unreachable("Unexpected IntrinsicInst");
916 };
917
918 if (PtrOp(Earlier) != PtrOp(Later))
919 return false;
920
921 Intrinsic::ID IDE = Earlier->getIntrinsicID();
922 Intrinsic::ID IDL = Later->getIntrinsicID();
923 // We could really use specific intrinsic classes for masked loads
924 // and stores in IntrinsicInst.h.
925 if (IDE == Intrinsic::masked_load && IDL == Intrinsic::masked_load) {
926 // Trying to replace later masked load with the earlier one.
927 // Check that the pointers are the same, and
928 // - masks and pass-throughs are the same, or
929 // - replacee's pass-through is "undef" and replacer's mask is a
930 // super-set of the replacee's mask.
931 if (MaskOp(Earlier) == MaskOp(Later) && ThruOp(Earlier) == ThruOp(Later))
932 return true;
933 if (!isa<UndefValue>(ThruOp(Later)))
934 return false;
935 return IsSubmask(MaskOp(Later), MaskOp(Earlier));
936 }
937 if (IDE == Intrinsic::masked_store && IDL == Intrinsic::masked_load) {
938 // Trying to replace a load of a stored value with the store's value.
939 // Check that the pointers are the same, and
940 // - load's mask is a subset of store's mask, and
941 // - load's pass-through is "undef".
942 if (!IsSubmask(MaskOp(Later), MaskOp(Earlier)))
943 return false;
944 return isa<UndefValue>(ThruOp(Later));
945 }
946 if (IDE == Intrinsic::masked_load && IDL == Intrinsic::masked_store) {
947 // Trying to remove a store of the loaded value.
948 // Check that the pointers are the same, and
949 // - store's mask is a subset of the load's mask.
950 return IsSubmask(MaskOp(Later), MaskOp(Earlier));
951 }
952 if (IDE == Intrinsic::masked_store && IDL == Intrinsic::masked_store) {
953 // Trying to remove a dead store (earlier).
954 // Check that the pointers are the same,
955 // - the to-be-removed store's mask is a subset of the other store's
956 // mask.
957 return IsSubmask(MaskOp(Earlier), MaskOp(Later));
958 }
959 return false;
960 }
961
962 void removeMSSA(Instruction &Inst) {
963 if (!MSSA)
964 return;
965 if (VerifyMemorySSA)
966 MSSA->verifyMemorySSA();
967 // Removing a store here can leave MemorySSA in an unoptimized state by
968 // creating MemoryPhis that have identical arguments and by creating
969 // MemoryUses whose defining access is not an actual clobber. The phi case
970 // is handled by MemorySSA when passing OptimizePhis = true to
971 // removeMemoryAccess. The non-optimized MemoryUse case is lazily updated
972 // by MemorySSA's getClobberingMemoryAccess.
973 MSSAUpdater->removeMemoryAccess(&Inst, true);
974 }
975};
976
977} // end anonymous namespace
978
979/// Determine if the memory referenced by LaterInst is from the same heap
980/// version as EarlierInst.
981/// This is currently called in two scenarios:
982///
983/// load p
984/// ...
985/// load p
986///
987/// and
988///
989/// x = load p
990/// ...
991/// store x, p
992///
993/// in both cases we want to verify that there are no possible writes to the
994/// memory referenced by p between the earlier and later instruction.
995bool EarlyCSE::isSameMemGeneration(unsigned EarlierGeneration,
996 unsigned LaterGeneration,
997 Instruction *EarlierInst,
998 Instruction *LaterInst) {
999 // Check the simple memory generation tracking first.
1000 if (EarlierGeneration == LaterGeneration)
1001 return true;
1002
1003 if (!MSSA)
1004 return false;
1005
1006 // If MemorySSA has determined that one of EarlierInst or LaterInst does not
1007 // read/write memory, then we can safely return true here.
1008 // FIXME: We could be more aggressive when checking doesNotAccessMemory(),
1009 // onlyReadsMemory(), mayReadFromMemory(), and mayWriteToMemory() in this pass
1010 // by also checking the MemorySSA MemoryAccess on the instruction. Initial
1011 // experiments suggest this isn't worthwhile, at least for C/C++ code compiled
1012 // with the default optimization pipeline.
1013 auto *EarlierMA = MSSA->getMemoryAccess(EarlierInst);
1014 if (!EarlierMA)
1015 return true;
1016 auto *LaterMA = MSSA->getMemoryAccess(LaterInst);
1017 if (!LaterMA)
1018 return true;
1019
1020 // Since we know LaterDef dominates LaterInst and EarlierInst dominates
1021 // LaterInst, if LaterDef dominates EarlierInst then it can't occur between
1022 // EarlierInst and LaterInst and neither can any other write that potentially
1023 // clobbers LaterInst.
1024 MemoryAccess *LaterDef;
1025 if (ClobberCounter < Opts.earlycse_mssa_optimization_cap) {
1026 LaterDef = MSSA->getWalker()->getClobberingMemoryAccess(LaterInst);
1027 ClobberCounter++;
1028 } else
1029 LaterDef = LaterMA->getDefiningAccess();
1030
1031 return MSSA->dominates(LaterDef, EarlierMA);
1032}
1033
1034bool EarlyCSE::isOperatingOnInvariantMemAt(Instruction *I, unsigned GenAt) {
1035 // A location loaded from with an invariant_load is assumed to *never* change
1036 // within the visible scope of the compilation.
1037 if (auto *LI = dyn_cast<LoadInst>(I))
1038 if (LI->hasMetadata(LLVMContext::MD_invariant_load))
1039 return true;
1040
1041 auto MemLocOpt = MemoryLocation::getOrNone(I);
1042 if (!MemLocOpt)
1043 // "target" intrinsic forms of loads aren't currently known to
1044 // MemoryLocation::get. TODO
1045 return false;
1046 MemoryLocation MemLoc = *MemLocOpt;
1047 if (!AvailableInvariants.count(MemLoc))
1048 return false;
1049
1050 // Is the generation at which this became invariant older than the
1051 // current one?
1052 return AvailableInvariants.lookup(MemLoc) <= GenAt;
1053}
1054
1055bool EarlyCSE::handleBranchCondition(Instruction *CondInst,
1056 const CondBrInst *BI, const BasicBlock *BB,
1057 const BasicBlock *Pred) {
1058 assert(BI->getCondition() == CondInst && "Wrong condition?");
1059 assert(BI->getSuccessor(0) == BB || BI->getSuccessor(1) == BB);
1060 auto *TorF = (BI->getSuccessor(0) == BB)
1062 : ConstantInt::getFalse(BB->getContext());
1063 auto MatchBinOp = [](Instruction *I, unsigned Opcode, Value *&LHS,
1064 Value *&RHS) {
1065 if (Opcode == Instruction::And &&
1067 return true;
1068 else if (Opcode == Instruction::Or &&
1070 return true;
1071 return false;
1072 };
1073 // If the condition is AND operation, we can propagate its operands into the
1074 // true branch. If it is OR operation, we can propagate them into the false
1075 // branch.
1076 unsigned PropagateOpcode =
1077 (BI->getSuccessor(0) == BB) ? Instruction::And : Instruction::Or;
1078
1079 bool MadeChanges = false;
1080 SmallVector<Instruction *, 4> WorkList;
1081 SmallPtrSet<Instruction *, 4> Visited;
1082 WorkList.push_back(CondInst);
1083 while (!WorkList.empty()) {
1084 Instruction *Curr = WorkList.pop_back_val();
1085
1086 AvailableValues.insert(Curr, TorF);
1087 LLVM_DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"
1088 << Curr->getName() << "' as " << *TorF << " in "
1089 << BB->getName() << "\n");
1090 if (!DebugCounter::shouldExecute(CSECounter)) {
1091 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1092 } else {
1093 // Replace all dominated uses with the known value.
1094 if (unsigned Count = replaceDominatedUsesWith(Curr, TorF, DT,
1095 BasicBlockEdge(Pred, BB))) {
1096 NumCSECVP += Count;
1097 MadeChanges = true;
1098 }
1099 }
1100
1101 Value *LHS, *RHS;
1102 if (MatchBinOp(Curr, PropagateOpcode, LHS, RHS))
1103 for (auto *Op : { LHS, RHS })
1104 if (Instruction *OPI = dyn_cast<Instruction>(Op))
1105 if (SimpleValue::canHandle(OPI) && Visited.insert(OPI).second)
1106 WorkList.push_back(OPI);
1107 }
1108
1109 return MadeChanges;
1110}
1111
1112Value *EarlyCSE::getMatchingValue(LoadValue &InVal, ParseMemoryInst &MemInst,
1113 unsigned CurrentGeneration) {
1114 if (InVal.DefInst == nullptr)
1115 return nullptr;
1116 if (auto *MSI = dyn_cast<MemSetInst>(InVal.DefInst)) {
1117 if (!MemInst.isLoad() || MemInst.isVolatile() || !MemInst.isUnordered() ||
1118 MemInst.getMatchingId() != -1)
1119 return nullptr;
1120 if (MSI->isVolatile())
1121 return nullptr;
1122 auto *Val = dyn_cast<ConstantInt>(MSI->getValue());
1123 if (!Val || !Val->isZero())
1124 return nullptr;
1125 auto Len = MSI->getLengthInBytes();
1126 if (!Len)
1127 return nullptr;
1128 Type *InstType = MemInst.getValueType();
1129 if (!InstType)
1130 return nullptr;
1131 TypeSize LoadSize = SQ.DL.getTypeStoreSize(InstType);
1132 if (LoadSize.isScalable() || Len->ult(LoadSize.getFixedValue()))
1133 return nullptr;
1134 if (!isOperatingOnInvariantMemAt(MemInst.get(), InVal.Generation) &&
1135 !isSameMemGeneration(InVal.Generation, CurrentGeneration, InVal.DefInst,
1136 MemInst.get()))
1137 return nullptr;
1138 return Constant::getNullValue(MemInst.getValueType());
1139 }
1140 if (InVal.MatchingId != MemInst.getMatchingId())
1141 return nullptr;
1142 // We don't yet handle removing loads with ordering of any kind.
1143 if (MemInst.isVolatile() || !MemInst.isUnordered())
1144 return nullptr;
1145 // We can't replace an atomic load with one which isn't also atomic.
1146 if (MemInst.isLoad() && !InVal.IsAtomic && MemInst.isAtomic())
1147 return nullptr;
1148 // The value V returned from this function is used differently depending
1149 // on whether MemInst is a load or a store. If it's a load, we will replace
1150 // MemInst with V, if it's a store, we will check if V is the same as the
1151 // available value.
1152 bool MemInstMatching = !MemInst.isLoad();
1153 Instruction *Matching = MemInstMatching ? MemInst.get() : InVal.DefInst;
1154 Instruction *Other = MemInstMatching ? InVal.DefInst : MemInst.get();
1155
1156 // For stores check the result values before checking memory generation
1157 // (otherwise isSameMemGeneration may crash).
1158 Value *Result =
1159 MemInst.isStore()
1160 ? getOrCreateResult(Matching, Other->getType(), /*CanCreate=*/false)
1161 : nullptr;
1162 if (MemInst.isStore() && InVal.DefInst != Result)
1163 return nullptr;
1164
1165 // Deal with non-target memory intrinsics.
1166 bool MatchingNTI = isHandledNonTargetIntrinsic(Matching);
1167 bool OtherNTI = isHandledNonTargetIntrinsic(Other);
1168 if (OtherNTI != MatchingNTI)
1169 return nullptr;
1170 if (OtherNTI && MatchingNTI) {
1171 if (!isNonTargetIntrinsicMatch(cast<IntrinsicInst>(InVal.DefInst),
1172 cast<IntrinsicInst>(MemInst.get())))
1173 return nullptr;
1174 }
1175
1176 if (!isOperatingOnInvariantMemAt(MemInst.get(), InVal.Generation) &&
1177 !isSameMemGeneration(InVal.Generation, CurrentGeneration, InVal.DefInst,
1178 MemInst.get()))
1179 return nullptr;
1180
1181 if (!Result)
1182 Result = getOrCreateResult(Matching, Other->getType(), /*CanCreate=*/true);
1183 return Result;
1184}
1185
1186static void combineIRFlags(Instruction &From, Value *To) {
1187 if (auto *I = dyn_cast<Instruction>(To)) {
1188 // If I being poison triggers UB, there is no need to drop those
1189 // flags. Otherwise, only retain flags present on both I and Inst.
1190 // TODO: Currently some fast-math flags are not treated as
1191 // poison-generating even though they should. Until this is fixed,
1192 // always retain flags present on both I and Inst for floating point
1193 // instructions.
1194 if (isa<FPMathOperator>(I) ||
1195 (I->hasPoisonGeneratingFlags() && !programUndefinedIfPoison(I)))
1196 I->andIRFlags(&From);
1197 }
1198 if (isa<CallBase>(&From) && isa<CallBase>(To)) {
1199 // NB: Intersection of attrs between InVal.first and Inst is overly
1200 // conservative. Since we only CSE readonly functions that have the same
1201 // memory state, we can preserve (or possibly in some cases combine)
1202 // more attributes. Likewise this implies when checking equality of
1203 // callsite for CSEing, we can probably ignore more attributes.
1204 // Generally poison generating attributes need to be handled with more
1205 // care as they can create *new* UB if preserved/combined and violated.
1206 // Attributes that imply immediate UB on the other hand would have been
1207 // violated either way.
1208 bool Success =
1209 cast<CallBase>(To)->tryIntersectAttributes(cast<CallBase>(&From));
1210 assert(Success && "Failed to intersect attributes in callsites that "
1211 "passed identical check");
1212 // For NDEBUG Compile.
1213 (void)Success;
1214 }
1215}
1216
1217bool EarlyCSE::overridingStores(const ParseMemoryInst &Earlier,
1218 const ParseMemoryInst &Later) {
1219 // Can we remove Earlier store because of Later store?
1220
1221 assert(Earlier.isUnordered() && !Earlier.isVolatile() &&
1222 "Violated invariant");
1223 if (Earlier.getPointerOperand() != Later.getPointerOperand())
1224 return false;
1225 if (!Earlier.getValueType() || !Later.getValueType() ||
1226 Earlier.getValueType() != Later.getValueType())
1227 return false;
1228 if (Earlier.getMatchingId() != Later.getMatchingId())
1229 return false;
1230 // At the moment, we don't remove ordered stores, but do remove
1231 // unordered atomic stores. There's no special requirement (for
1232 // unordered atomics) about removing atomic stores only in favor of
1233 // other atomic stores since we were going to execute the non-atomic
1234 // one anyway and the atomic one might never have become visible.
1235 if (!Earlier.isUnordered() || !Later.isUnordered())
1236 return false;
1237
1238 // Deal with non-target memory intrinsics.
1239 bool ENTI = isHandledNonTargetIntrinsic(Earlier.get());
1240 bool LNTI = isHandledNonTargetIntrinsic(Later.get());
1241 if (ENTI && LNTI)
1242 return isNonTargetIntrinsicMatch(cast<IntrinsicInst>(Earlier.get()),
1243 cast<IntrinsicInst>(Later.get()));
1244
1245 // Because of the check above, at least one of them is false.
1246 // For now disallow matching intrinsics with non-intrinsics,
1247 // so assume that the stores match if neither is an intrinsic.
1248 return ENTI == LNTI;
1249}
1250
1251bool EarlyCSE::processNode(DomTreeNode *Node) {
1252 bool Changed = false;
1253 BasicBlock *BB = Node->getBlock();
1254
1255 // If this block has a single predecessor, then the predecessor is the parent
1256 // of the domtree node and all of the live out memory values are still current
1257 // in this block. If this block has multiple predecessors, then they could
1258 // have invalidated the live-out memory values of our parent value. For now,
1259 // just be conservative and invalidate memory if this block has multiple
1260 // predecessors.
1261 if (!BB->getSinglePredecessor())
1262 ++CurrentGeneration;
1263
1264 // If this node has a single predecessor which ends in a conditional branch,
1265 // we can infer the value of the branch condition given that we took this
1266 // path. We need the single predecessor to ensure there's not another path
1267 // which reaches this block where the condition might hold a different
1268 // value. Since we're adding this to the scoped hash table (like any other
1269 // def), it will have been popped if we encounter a future merge block.
1270 if (BasicBlock *Pred = BB->getSinglePredecessor()) {
1271 if (auto *BI = dyn_cast<CondBrInst>(Pred->getTerminator())) {
1272 auto *CondInst = dyn_cast<Instruction>(BI->getCondition());
1273 if (CondInst && SimpleValue::canHandle(CondInst))
1274 Changed |= handleBranchCondition(CondInst, BI, BB, Pred);
1275 }
1276 }
1277
1278 /// LastStore - Keep track of the last non-volatile store that we saw... for
1279 /// as long as there in no instruction that reads memory. If we see a store
1280 /// to the same location, we delete the dead store. This zaps trivial dead
1281 /// stores which can occur in bitfield code among other things.
1282 Instruction *LastStore = nullptr;
1283
1284 // See if any instructions in the block can be eliminated. If so, do it. If
1285 // not, add them to AvailableValues.
1286 for (Instruction &Inst : make_early_inc_range(*BB)) {
1287 // Dead instructions should just be removed.
1288 if (isInstructionTriviallyDead(&Inst, &TLI)) {
1289 LLVM_DEBUG(dbgs() << "EarlyCSE DCE: " << Inst << '\n');
1290 if (!DebugCounter::shouldExecute(CSECounter)) {
1291 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1292 continue;
1293 }
1294
1295 salvageKnowledge(&Inst, &AC);
1296 salvageDebugInfo(Inst);
1297 removeMSSA(Inst);
1298 Inst.eraseFromParent();
1299 Changed = true;
1300 ++NumSimplify;
1301 continue;
1302 }
1303
1304 // Skip assume intrinsics, they don't really have side effects (although
1305 // they're marked as such to ensure preservation of control dependencies),
1306 // and this pass will not bother with its removal. However, we should mark
1307 // its condition as true for all dominated blocks.
1308 if (auto *Assume = dyn_cast<AssumeInst>(&Inst)) {
1309 auto *CondI = dyn_cast<Instruction>(Assume->getArgOperand(0));
1310 if (CondI && SimpleValue::canHandle(CondI)) {
1311 LLVM_DEBUG(dbgs() << "EarlyCSE considering assumption: " << Inst
1312 << '\n');
1313 AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
1314 } else
1315 LLVM_DEBUG(dbgs() << "EarlyCSE skipping assumption: " << Inst << '\n');
1316 continue;
1317 }
1318
1319 // Likewise, noalias intrinsics don't actually write.
1320 if (match(&Inst,
1322 LLVM_DEBUG(dbgs() << "EarlyCSE skipping noalias intrinsic: " << Inst
1323 << '\n');
1324 continue;
1325 }
1326
1327 // Skip sideeffect intrinsics, for the same reason as assume intrinsics.
1329 LLVM_DEBUG(dbgs() << "EarlyCSE skipping sideeffect: " << Inst << '\n');
1330 continue;
1331 }
1332
1333 // Skip pseudoprobe intrinsics, for the same reason as assume intrinsics.
1335 LLVM_DEBUG(dbgs() << "EarlyCSE skipping pseudoprobe: " << Inst << '\n');
1336 continue;
1337 }
1338
1339 // We can skip all invariant.start intrinsics since they only read memory,
1340 // and we can forward values across it. For invariant starts without
1341 // invariant ends, we can use the fact that the invariantness never ends to
1342 // start a scope in the current generaton which is true for all future
1343 // generations. Also, we dont need to consume the last store since the
1344 // semantics of invariant.start allow us to perform DSE of the last
1345 // store, if there was a store following invariant.start. Consider:
1346 //
1347 // store 30, i8* p
1348 // invariant.start(p)
1349 // store 40, i8* p
1350 // We can DSE the store to 30, since the store 40 to invariant location p
1351 // causes undefined behaviour.
1353 // If there are any uses, the scope might end.
1354 if (!Inst.use_empty())
1355 continue;
1356 MemoryLocation MemLoc =
1358 // Don't start a scope if we already have a better one pushed
1359 if (!AvailableInvariants.count(MemLoc))
1360 AvailableInvariants.insert(MemLoc, CurrentGeneration);
1361 continue;
1362 }
1363
1364 if (isGuard(&Inst)) {
1365 if (auto *CondI =
1366 dyn_cast<Instruction>(cast<CallInst>(Inst).getArgOperand(0))) {
1367 if (SimpleValue::canHandle(CondI)) {
1368 // Do we already know the actual value of this condition?
1369 if (auto *KnownCond = AvailableValues.lookup(CondI)) {
1370 // Is the condition known to be true?
1371 if (isa<ConstantInt>(KnownCond) &&
1372 cast<ConstantInt>(KnownCond)->isOne()) {
1374 << "EarlyCSE removing guard: " << Inst << '\n');
1375 salvageKnowledge(&Inst, &AC);
1376 removeMSSA(Inst);
1377 Inst.eraseFromParent();
1378 Changed = true;
1379 continue;
1380 } else
1381 // Use the known value if it wasn't true.
1382 cast<CallInst>(Inst).setArgOperand(0, KnownCond);
1383 }
1384 // The condition we're on guarding here is true for all dominated
1385 // locations.
1386 AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
1387 }
1388 }
1389
1390 // Guard intrinsics read all memory, but don't write any memory.
1391 // Accordingly, don't update the generation but consume the last store (to
1392 // avoid an incorrect DSE).
1393 LastStore = nullptr;
1394 continue;
1395 }
1396
1397 // If the instruction can be simplified (e.g. X+0 = X) then replace it with
1398 // its simpler value.
1399 if (Value *V = simplifyInstruction(&Inst, SQ)) {
1400 LLVM_DEBUG(dbgs() << "EarlyCSE Simplify: " << Inst << " to: " << *V
1401 << '\n');
1402 if (!DebugCounter::shouldExecute(CSECounter)) {
1403 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1404 } else {
1405 bool Killed = false;
1406 if (!Inst.use_empty()) {
1407 Inst.replaceAllUsesWith(V);
1408 Changed = true;
1409 }
1410 if (isInstructionTriviallyDead(&Inst, &TLI)) {
1411 salvageKnowledge(&Inst, &AC);
1412 removeMSSA(Inst);
1413 Inst.eraseFromParent();
1414 Changed = true;
1415 Killed = true;
1416 }
1417 if (Changed)
1418 ++NumSimplify;
1419 if (Killed)
1420 continue;
1421 }
1422 }
1423
1424 // Make sure stores prior to a potential unwind are not removed, as the
1425 // caller may read the memory.
1426 if (Inst.mayThrow())
1427 LastStore = nullptr;
1428
1429 // If this is a simple instruction that we can value number, process it.
1430 if (SimpleValue::canHandle(&Inst)) {
1431 if ([[maybe_unused]] auto *CI = dyn_cast<ConstrainedFPIntrinsic>(&Inst)) {
1432 assert(CI->getExceptionBehavior() != fp::ebStrict &&
1433 "Unexpected ebStrict from SimpleValue::canHandle()");
1434 assert((!CI->getRoundingMode() ||
1435 CI->getRoundingMode() != RoundingMode::Dynamic) &&
1436 "Unexpected dynamic rounding from SimpleValue::canHandle()");
1437 }
1438 // See if the instruction has an available value. If so, use it.
1439 if (Value *V = AvailableValues.lookup(&Inst)) {
1440 LLVM_DEBUG(dbgs() << "EarlyCSE CSE: " << Inst << " to: " << *V
1441 << '\n');
1442 if (!DebugCounter::shouldExecute(CSECounter)) {
1443 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1444 continue;
1445 }
1446 combineIRFlags(Inst, V);
1447 Inst.replaceAllUsesWith(V);
1448 salvageKnowledge(&Inst, &AC);
1449 removeMSSA(Inst);
1450 Inst.eraseFromParent();
1451 Changed = true;
1452 ++NumCSE;
1453 continue;
1454 }
1455
1456 // Otherwise, just remember that this value is available.
1457 AvailableValues.insert(&Inst, &Inst);
1458 continue;
1459 }
1460
1461 ParseMemoryInst MemInst(&Inst, TTI);
1462 // If this is a non-volatile load, process it.
1463 if (MemInst.isValid() && MemInst.isLoad()) {
1464 // (conservatively) we can't peak past the ordering implied by this
1465 // operation, but we can add this load to our set of available values
1466 if (MemInst.isVolatile() || !MemInst.isUnordered()) {
1467 LastStore = nullptr;
1468 ++CurrentGeneration;
1469 }
1470
1471 if (MemInst.isInvariantLoad()) {
1472 // If we pass an invariant load, we know that memory location is
1473 // indefinitely constant from the moment of first dereferenceability.
1474 // We conservatively treat the invariant_load as that moment. If we
1475 // pass a invariant load after already establishing a scope, don't
1476 // restart it since we want to preserve the earliest point seen.
1477 auto MemLoc = MemoryLocation::get(&Inst);
1478 if (!AvailableInvariants.count(MemLoc))
1479 AvailableInvariants.insert(MemLoc, CurrentGeneration);
1480 }
1481
1482 // If we have an available version of this load, and if it is the right
1483 // generation or the load is known to be from an invariant location,
1484 // replace this instruction.
1485 //
1486 // If either the dominating load or the current load are invariant, then
1487 // we can assume the current load loads the same value as the dominating
1488 // load.
1489 LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
1490 if (Value *Op = getMatchingValue(InVal, MemInst, CurrentGeneration)) {
1491 LLVM_DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << Inst
1492 << " to: " << *InVal.DefInst << '\n');
1493 if (!DebugCounter::shouldExecute(CSECounter)) {
1494 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1495 continue;
1496 }
1497 if (InVal.IsLoad)
1498 if (auto *I = dyn_cast<Instruction>(Op))
1499 combineMetadataForCSE(I, &Inst, false);
1500 if (!Inst.use_empty())
1501 Inst.replaceAllUsesWith(Op);
1502 salvageKnowledge(&Inst, &AC);
1503 removeMSSA(Inst);
1504 Inst.eraseFromParent();
1505 Changed = true;
1506 ++NumCSELoad;
1507 continue;
1508 }
1509
1510 // Otherwise, remember that we have this instruction.
1511 AvailableLoads.insert(MemInst.getPointerOperand(),
1512 LoadValue(&Inst, CurrentGeneration,
1513 MemInst.getMatchingId(),
1514 MemInst.isAtomic(),
1515 MemInst.isLoad()));
1516 LastStore = nullptr;
1517 continue;
1518 }
1519
1520 // If this instruction may read from memory, forget LastStore. Load/store
1521 // intrinsics will indicate both a read and a write to memory. The target
1522 // may override this (e.g. so that a store intrinsic does not read from
1523 // memory, and thus will be treated the same as a regular store for
1524 // commoning purposes).
1525 if (Inst.mayReadFromMemory() &&
1526 !(MemInst.isValid() && !MemInst.mayReadFromMemory()))
1527 LastStore = nullptr;
1528
1529 // If this is a read-only or write-only call, process it. Skip store
1530 // MemInsts, as they will be more precisely handled later on. Also skip
1531 // memsets, as DSE may be able to optimize them better by removing the
1532 // earlier rather than later store.
1533 if (CallValue::canHandle(&Inst) &&
1534 (!MemInst.isValid() || !MemInst.isStore()) && !isa<MemSetInst>(&Inst)) {
1535 // If we have an available version of this call, and if it is the right
1536 // generation, replace this instruction.
1537 std::pair<Instruction *, unsigned> InVal = AvailableCalls.lookup(&Inst);
1538 if (InVal.first != nullptr &&
1539 isSameMemGeneration(InVal.second, CurrentGeneration, InVal.first,
1540 &Inst) &&
1541 InVal.first->mayReadFromMemory() == Inst.mayReadFromMemory()) {
1542 LLVM_DEBUG(dbgs() << "EarlyCSE CSE CALL: " << Inst
1543 << " to: " << *InVal.first << '\n');
1544 if (!DebugCounter::shouldExecute(CSECounter)) {
1545 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1546 continue;
1547 }
1548 combineIRFlags(Inst, InVal.first);
1549 if (!Inst.use_empty())
1550 Inst.replaceAllUsesWith(InVal.first);
1551 salvageKnowledge(&Inst, &AC);
1552 removeMSSA(Inst);
1553 Inst.eraseFromParent();
1554 Changed = true;
1555 ++NumCSECall;
1556 continue;
1557 }
1558
1559 // Increase memory generation for writes. Do this before inserting
1560 // the call, so it has the generation after the write occurred.
1561 if (Inst.mayWriteToMemory())
1562 ++CurrentGeneration;
1563
1564 // Otherwise, remember that we have this instruction.
1565 AvailableCalls.insert(&Inst, std::make_pair(&Inst, CurrentGeneration));
1566 continue;
1567 }
1568
1569 // Compare GEP instructions based on offset.
1570 if (GEPValue::canHandle(&Inst)) {
1571 auto *GEP = cast<GetElementPtrInst>(&Inst);
1572 APInt Offset = APInt(SQ.DL.getIndexTypeSizeInBits(GEP->getType()), 0);
1573 GEPValue GEPVal(GEP, GEP->accumulateConstantOffset(SQ.DL, Offset)
1574 ? Offset.trySExtValue()
1575 : std::nullopt);
1576 if (Value *V = AvailableGEPs.lookup(GEPVal)) {
1577 LLVM_DEBUG(dbgs() << "EarlyCSE CSE GEP: " << Inst << " to: " << *V
1578 << '\n');
1579 combineIRFlags(Inst, V);
1580 Inst.replaceAllUsesWith(V);
1581 salvageKnowledge(&Inst, &AC);
1582 removeMSSA(Inst);
1583 Inst.eraseFromParent();
1584 Changed = true;
1585 ++NumCSEGEP;
1586 continue;
1587 }
1588
1589 // Otherwise, just remember that we have this GEP.
1590 AvailableGEPs.insert(GEPVal, &Inst);
1591 continue;
1592 }
1593
1594 // A release fence requires that all stores complete before it, but does
1595 // not prevent the reordering of following loads 'before' the fence. As a
1596 // result, we don't need to consider it as writing to memory and don't need
1597 // to advance the generation. We do need to prevent DSE across the fence,
1598 // but that's handled above.
1599 if (auto *FI = dyn_cast<FenceInst>(&Inst))
1600 if (FI->getOrdering() == AtomicOrdering::Release) {
1601 assert(Inst.mayReadFromMemory() && "relied on to prevent DSE above");
1602 continue;
1603 }
1604
1605 // write back DSE - If we write back the same value we just loaded from
1606 // the same location and haven't passed any intervening writes or ordering
1607 // operations, we can remove the write. The primary benefit is in allowing
1608 // the available load table to remain valid and value forward past where
1609 // the store originally was.
1610 if (MemInst.isValid() && MemInst.isStore()) {
1611 LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
1612 if (InVal.DefInst &&
1613 InVal.DefInst ==
1614 getMatchingValue(InVal, MemInst, CurrentGeneration)) {
1615 LLVM_DEBUG(dbgs() << "EarlyCSE DSE (writeback): " << Inst << '\n');
1616 if (!DebugCounter::shouldExecute(CSECounter)) {
1617 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1618 continue;
1619 }
1620 salvageKnowledge(&Inst, &AC);
1621 removeMSSA(Inst);
1622 Inst.eraseFromParent();
1623 Changed = true;
1624 ++NumDSE;
1625 // We can avoid incrementing the generation count since we were able
1626 // to eliminate this store.
1627 continue;
1628 }
1629 }
1630
1631 // Okay, this isn't something we can CSE at all. Check to see if it is
1632 // something that could modify memory. If so, our available memory values
1633 // cannot be used so bump the generation count.
1634 if (Inst.mayWriteToMemory()) {
1635 ++CurrentGeneration;
1636
1637 if (MemInst.isValid() && MemInst.isStore()) {
1638 // We do a trivial form of DSE if there are two stores to the same
1639 // location with no intervening loads. Delete the earlier store.
1640 if (LastStore) {
1641 if (overridingStores(ParseMemoryInst(LastStore, TTI), MemInst)) {
1642 LLVM_DEBUG(dbgs() << "EarlyCSE DEAD STORE: " << *LastStore
1643 << " due to: " << Inst << '\n');
1644 if (!DebugCounter::shouldExecute(CSECounter)) {
1645 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1646 } else {
1647 salvageKnowledge(&Inst, &AC);
1648 removeMSSA(*LastStore);
1649 LastStore->eraseFromParent();
1650 Changed = true;
1651 ++NumDSE;
1652 LastStore = nullptr;
1653 }
1654 }
1655 // fallthrough - we can exploit information about this store
1656 }
1657
1658 // Okay, we just invalidated anything we knew about loaded values. Try
1659 // to salvage *something* by remembering that the stored value is a live
1660 // version of the pointer. It is safe to forward from volatile stores
1661 // to non-volatile loads, so we don't have to check for volatility of
1662 // the store.
1663 AvailableLoads.insert(MemInst.getPointerOperand(),
1664 LoadValue(&Inst, CurrentGeneration,
1665 MemInst.getMatchingId(),
1666 MemInst.isAtomic(),
1667 MemInst.isLoad()));
1668
1669 // Remember that this was the last unordered store we saw for DSE. We
1670 // don't yet handle DSE on ordered or volatile stores since we don't
1671 // have a good way to model the ordering requirement for following
1672 // passes once the store is removed. We could insert a fence, but
1673 // since fences are slightly stronger than stores in their ordering,
1674 // it's not clear this is a profitable transform. Another option would
1675 // be to merge the ordering with that of the post dominating store.
1676 if (MemInst.isUnordered() && !MemInst.isVolatile())
1677 LastStore = &Inst;
1678 else
1679 LastStore = nullptr;
1680 }
1681 }
1682 }
1683
1684 return Changed;
1685}
1686
1687bool EarlyCSE::run() {
1688 // Note, deque is being used here because there is significant performance
1689 // gains over vector when the container becomes very large due to the
1690 // specific access patterns. For more information see the mailing list
1691 // discussion on this:
1692 // http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html
1693 std::deque<StackNode *> nodesToProcess;
1694
1695 bool Changed = false;
1696
1697 // Process the root node.
1698 nodesToProcess.push_back(new StackNode(
1699 AvailableValues, AvailableLoads, AvailableInvariants, AvailableCalls,
1700 AvailableGEPs, CurrentGeneration, DT.getRootNode(),
1701 DT.getRootNode()->begin(), DT.getRootNode()->end()));
1702
1703 assert(!CurrentGeneration && "Create a new EarlyCSE instance to rerun it.");
1704
1705 // Process the stack.
1706 while (!nodesToProcess.empty()) {
1707 // Grab the first item off the stack. Set the current generation, remove
1708 // the node from the stack, and process it.
1709 StackNode *NodeToProcess = nodesToProcess.back();
1710
1711 // Initialize class members.
1712 CurrentGeneration = NodeToProcess->currentGeneration();
1713
1714 // Check if the node needs to be processed.
1715 if (!NodeToProcess->isProcessed()) {
1716 // Process the node.
1717 Changed |= processNode(NodeToProcess->node());
1718 NodeToProcess->childGeneration(CurrentGeneration);
1719 NodeToProcess->process();
1720 } else if (NodeToProcess->childIter() != NodeToProcess->end()) {
1721 // Push the next child onto the stack.
1722 DomTreeNode *child = NodeToProcess->nextChild();
1723 nodesToProcess.push_back(new StackNode(
1724 AvailableValues, AvailableLoads, AvailableInvariants, AvailableCalls,
1725 AvailableGEPs, NodeToProcess->childGeneration(), child,
1726 child->begin(), child->end()));
1727 } else {
1728 // It has been processed, and there are no more children to process,
1729 // so delete it and pop it off the stack.
1730 delete NodeToProcess;
1731 nodesToProcess.pop_back();
1732 }
1733 } // while (!nodes...)
1734
1735 return Changed;
1736}
1737
1740 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1741 auto &TTI = AM.getResult<TargetIRAnalysis>(F);
1742 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1743 auto &AC = AM.getResult<AssumptionAnalysis>(F);
1744 auto *MSSA =
1745 UseMemorySSA ? &AM.getResult<MemorySSAAnalysis>(F).getMSSA() : nullptr;
1746
1747 EarlyCSE CSE(getScalarOptions(F), F.getDataLayout(), TLI, TTI, DT, AC, MSSA);
1748
1749 if (!CSE.run())
1750 return PreservedAnalyses::all();
1751
1754 if (UseMemorySSA)
1756 return PA;
1757}
1758
1760 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
1761 static_cast<PassInfoMixin<EarlyCSEPass> *>(this)->printPipeline(
1762 OS, MapClassName2PassName);
1763 OS << '<';
1764 if (UseMemorySSA)
1765 OS << "memssa";
1766 OS << '>';
1767}
1768
1769namespace {
1770
1771/// A simple and fast domtree-based CSE pass.
1772///
1773/// This pass does a simple depth-first walk over the dominator tree,
1774/// eliminating trivially redundant instructions and using instsimplify to
1775/// canonicalize things as it goes. It is intended to be fast and catch obvious
1776/// cases so that instcombine and other passes are more effective. It is
1777/// expected that a later pass of GVN will catch the interesting/hard cases.
1778template<bool UseMemorySSA>
1779class EarlyCSELegacyCommonPass : public FunctionPass {
1780public:
1781 static char ID;
1782
1783 EarlyCSELegacyCommonPass() : FunctionPass(ID) {
1784 if (UseMemorySSA)
1786 else
1788 }
1789
1790 bool runOnFunction(Function &F) override {
1791 if (skipFunction(F))
1792 return false;
1793
1794 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
1795 auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1796 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1797 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1798 auto *MSSA =
1799 UseMemorySSA ? &getAnalysis<MemorySSAWrapperPass>().getMSSA() : nullptr;
1800
1801 EarlyCSE CSE(getScalarOptions(F), F.getDataLayout(), TLI, TTI, DT, AC,
1802 MSSA);
1803
1804 return CSE.run();
1805 }
1806
1807 void getAnalysisUsage(AnalysisUsage &AU) const override {
1808 AU.addRequired<AssumptionCacheTracker>();
1809 AU.addRequired<DominatorTreeWrapperPass>();
1810 AU.addRequired<TargetLibraryInfoWrapperPass>();
1811 AU.addRequired<TargetTransformInfoWrapperPass>();
1812 if (UseMemorySSA) {
1813 AU.addRequired<AAResultsWrapperPass>();
1814 AU.addRequired<MemorySSAWrapperPass>();
1815 AU.addPreserved<MemorySSAWrapperPass>();
1816 }
1817 AU.addPreserved<GlobalsAAWrapperPass>();
1818 AU.addPreserved<AAResultsWrapperPass>();
1819 AU.setPreservesCFG();
1820 }
1821};
1822
1823} // end anonymous namespace
1824
1825using EarlyCSELegacyPass = EarlyCSELegacyCommonPass</*UseMemorySSA=*/false>;
1826
1827template<>
1828char EarlyCSELegacyPass::ID = 0;
1829
1830INITIALIZE_PASS_BEGIN(EarlyCSELegacyPass, "early-cse", "Early CSE", false,
1831 false)
1836INITIALIZE_PASS_END(EarlyCSELegacyPass, "early-cse", "Early CSE", false, false)
1837
1838using EarlyCSEMemSSALegacyPass =
1839 EarlyCSELegacyCommonPass</*UseMemorySSA=*/true>;
1840
1841template<>
1842char EarlyCSEMemSSALegacyPass::ID = 0;
1843
1845 if (UseMemorySSA)
1846 return new EarlyCSEMemSSALegacyPass();
1847 else
1848 return new EarlyCSELegacyPass();
1849}
1850
1851INITIALIZE_PASS_BEGIN(EarlyCSEMemSSALegacyPass, "early-cse-memssa",
1852 "Early CSE w/ MemorySSA", false, false)
1859INITIALIZE_PASS_END(EarlyCSEMemSSALegacyPass, "early-cse-memssa",
1860 "Early CSE w/ MemorySSA", false, false)
#define Success
const TargetLowering & TLI
SDValue Pred
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static bool isLoad(int Opcode)
static bool isStore(int Opcode)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file defines the BumpPtrAllocator interface.
Atomic ordering constants.
#define X(NUM, ENUM, NAME)
Definition ELF.h:665
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Optimize for code generation
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
This file defines DenseMapInfo traits for DenseMap.
static void combineIRFlags(Instruction &From, Value *To)
EarlyCSELegacyCommonPass< false > EarlyCSELegacyPass
static bool matchSelectWithOptionalNotCond(Value *V, Value *&Cond, Value *&A, Value *&B)
Match a 'select' including an optional 'not's of the condition.
Definition EarlyCSE.cpp:150
early cse Early CSE w MemorySSA
static unsigned getHashValueImpl(SimpleValue Val)
Definition EarlyCSE.cpp:177
static bool isEqualImpl(SimpleValue LHS, SimpleValue RHS)
Definition EarlyCSE.cpp:286
static unsigned hashCallInst(CallInst *CI)
Definition EarlyCSE.cpp:166
This file provides the interface for a simple, fast CSE pass.
static bool runOnFunction(Function &F, bool PostInlining)
This is the interface for a simple mod/ref and alias analysis over globals.
Hexagon Common GEP
IRTranslator LLVM IR MI
This header defines various interfaces for pass management in LLVM.
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
static bool isAtomic(MachineBasicBlock::iterator I)
Value * getMatchingValue(LoadValue LV, LoadInst *LI, unsigned CurrentGeneration, BatchAAResults &BAA, function_ref< MemorySSA *()> GetMSSA)
#define F(x, y, z)
Definition MD5.cpp:54
#define I(x, y, z)
Definition MD5.cpp:57
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
static bool isInvariantLoad(const Instruction *I, const Value *Ptr, const bool IsKernelFn)
uint64_t IntrinsicInst * II
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
SmallVector< MachineOperand, 4 > Cond
const RISCVInstrInfo * RII
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
Func getContext().diagnose(DiagnosticInfoUnsupported(Func
This file contains some templates that are useful if you are working with the STL at all.
separate const offset from Split GEPs to a variadic base and a constant offset for better CSE
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:171
#define LLVM_DEBUG(...)
Definition Debug.h:119
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
This pass exposes codegen information to IR-level passes.
Value * RHS
Value * LHS
bool isProcessed() const
unsigned currentGeneration() const
unsigned childGeneration() const
DomTreeNode::const_iterator end() const
void process()
DomTreeNode * nextChild()
DomTreeNode::const_iterator childIter() const
DomTreeNode * node()
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
LLVM_ABI void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition Pass.cpp:280
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
Represents analyses that only rely on functions' control flow.
Definition Analysis.h:73
bool onlyWritesMemory(unsigned OpNo) const
bool onlyReadsMemory(unsigned OpNo) const
bool isConvergent() const
Determine if the invoke is convergent.
This class represents a function call, abstracting a target machine's calling convention.
This is the base class for all instructions that perform data casts.
Definition InstrTypes.h:512
This class is the base class for the comparison instructions.
Definition InstrTypes.h:728
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition InstrTypes.h:740
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition InstrTypes.h:852
Predicate getPredicate() const
Return the predicate for this instruction.
Definition InstrTypes.h:828
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
LLVM_ABI unsigned getIndexTypeSizeInBits(Type *Ty) const
The size in bits of the index used in GEP calculation for this type.
TypeSize getTypeStoreSize(Type *Ty) const
Returns the maximum number of bytes that may be overwritten by storing the specified type.
Definition DataLayout.h:582
static bool shouldExecute(CounterInfo &Counter)
iterator begin() const
iterator end() const
Analysis pass which computes a DominatorTree.
Definition Dominators.h:241
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
Legacy analysis pass which computes a DominatorTree.
Definition Dominators.h:277
This instruction extracts a struct member or array element value from an aggregate value.
This class represents a freeze function that returns random concrete value if an operand is either a ...
FunctionPass class - This class is used to implement most global optimizations.
Definition Pass.h:312
bool isPresplitCoroutine() const
Determine if the function is presplit coroutine.
Definition Function.h:522
Represents calls to the gc.relocate intrinsic.
This instruction inserts a struct field of array element value into an aggregate value.
LLVM_ABI bool mayThrow(bool IncludePhaseOneUnwind=false) const LLVM_READONLY
Return true if this instruction may throw an exception.
LLVM_ABI bool mayWriteToMemory() const LLVM_READONLY
Return true if this instruction may modify memory.
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
LLVM_ABI bool isIdenticalToWhenDefined(const Instruction *I, bool IntersectAttrs=false) const LLVM_READONLY
This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags,...
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
LLVM_ABI bool mayReadFromMemory() const LLVM_READONLY
Return true if this instruction may read memory.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
static LLVM_ABI MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
static LLVM_ABI std::optional< MemoryLocation > getOrNone(const Instruction *Inst)
static LLVM_ABI MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
An analysis that produces MemorySSA for a function.
Definition MemorySSA.h:936
MemoryAccess * getClobberingMemoryAccess(const Instruction *I, BatchAAResults &AA)
Given a memory Mod/Ref/ModRef'ing instruction, calling this will give you the nearest dominating Memo...
Definition MemorySSA.h:1049
Legacy analysis pass which computes MemorySSA.
Definition MemorySSA.h:989
LLVM_ABI bool dominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in potentially different blocks, determine whether MemoryAccess A dominates...
LLVM_ABI MemorySSAWalker * getWalker()
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition MemorySSA.h:707
static LLVM_ABI PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
PreservedAnalyses & preserveSet()
Mark an analysis set as preserved.
Definition Analysis.h:152
PreservedAnalyses & preserve()
Mark an analysis as preserved.
Definition Analysis.h:133
ScopedHashTableScope< SimpleValue, Value *, DenseMapInfo< SimpleValue >, AllocatorTy > ScopeTy
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
void push_back(const T &Elt)
Represent a constant reference to a string, i.e.
Definition StringRef.h:56
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
Wrapper pass for TargetTransformInfo.
LLVM_ABI bool getTgtMemIntrinsic(IntrinsicInst *Inst, MemIntrinsicInfo &Info) const
Value * getOperand(unsigned i) const
Definition User.h:207
iterator_range< value_op_iterator > operand_values()
Definition User.h:291
LLVM Value Representation.
Definition Value.h:75
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition Value.cpp:548
bool use_empty() const
Definition Value.h:348
constexpr ScalarTy getFixedValue() const
Definition TypeSize.h:201
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
Definition TypeSize.h:169
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
Definition ilist_node.h:34
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ BasicBlock
Various leaf nodes.
Definition ISDOpcodes.h:83
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
auto m_Cmp()
Matches any compare instruction and ignore it.
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
auto m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
@ ebStrict
This corresponds to "fpexcept.strict".
Definition FPEnv.h:42
NodeAddr< NodeBase * > Node
Definition RDFGraph.h:381
iterator end() const
Definition BasicBlock.h:89
friend class Instruction
Iterator for Instructions in a `BasicBlock.
Definition BasicBlock.h:73
Type * getValueType(Value *V, bool ReVec, bool LookThroughCmp)
Returns the "element type" of the given value/instruction V.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition STLExtras.h:316
@ Offset
Definition DWP.cpp:577
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
LLVM_ABI void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
Definition Utils.cpp:1837
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition STLExtras.h:649
const ScalarOptions & getScalarOptions(const LLVMContext &C)
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
Definition InstrProf.h:143
LLVM_ABI void initializeEarlyCSEMemSSALegacyPassPass(PassRegistry &)
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
DomTreeNodeBase< BasicBlock > DomTreeNode
Definition Dominators.h:65
LLVM_ABI bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
Definition Local.cpp:408
LLVM_ABI bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)
LLVM_ABI bool programUndefinedIfPoison(const Instruction *Inst)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
LLVM_ABI bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition MemorySSA.cpp:76
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
LLVM_ABI void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
Definition Local.cpp:3186
@ Other
Any other memory.
Definition ModRef.h:68
TargetTransformInfo TTI
LLVM_ABI bool salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
DWARFExpression::Operation Op
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition Hashing.h:307
BumpPtrAllocatorImpl<> BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition Allocator.h:391
LLVM_ABI FunctionPass * createEarlyCSEPass(bool UseMemorySSA=false)
LLVM_ABI void initializeEarlyCSELegacyPassPass(PassRegistry &)
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition Hashing.h:287
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition BitVector.h:881
unsigned Generation
static unsigned getHashValue(CallValue Val)
static bool isEqual(CallValue LHS, CallValue RHS)
static bool isEqual(const GEPValue &LHS, const GEPValue &RHS)
static unsigned getHashValue(const GEPValue &Val)
static unsigned getHashValue(SimpleValue Val)
static bool isEqual(SimpleValue LHS, SimpleValue RHS)
An information struct used to provide DenseMap with the various necessary components for a given valu...
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
LLVM_ABI void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
const DataLayout & DL