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