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