LLVM 22.0.0git
EarlyCSE.cpp
Go to the documentation of this file.
1//===- EarlyCSE.cpp - Simple and fast CSE pass ----------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass performs a simple dominator tree walk that eliminates trivially
10// redundant instructions.
11//
12//===----------------------------------------------------------------------===//
13
16#include "llvm/ADT/Hashing.h"
17#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/Statistic.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"
38#include "llvm/IR/LLVMContext.h"
39#include "llvm/IR/PassManager.h"
41#include "llvm/IR/Type.h"
42#include "llvm/IR/Value.h"
44#include "llvm/Pass.h"
48#include "llvm/Support/Debug.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
77 "earlycse-mssa-optimization-cap", cl::init(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
82 "earlycse-debug-hash", cl::init(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>(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>(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>(Inst) || isa<UnaryOperator>(Inst) ||
147 isa<BinaryOperator>(Inst) || isa<CmpInst>(Inst) ||
151 isa<FreezeInst>(Inst);
152 }
153};
154
155} // end anonymous namespace
156
157namespace llvm {
158
159template <> struct DenseMapInfo<SimpleValue> {
160 static inline SimpleValue getEmptyKey() {
162 }
163
164 static inline SimpleValue 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.
176 Value *&B,
177 SelectPatternFlavor &Flavor) {
178 // Return false if V is not even a select.
179 if (!match(V, m_Select(m_Value(Cond), m_Value(A), m_Value(B))))
180 return false;
181
182 // Look through a 'not' of the condition operand by swapping A/B.
183 Value *CondNot;
184 if (match(Cond, m_Not(m_Value(CondNot)))) {
185 Cond = CondNot;
186 std::swap(A, 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(Cond, m_ICmp(Pred, m_Specific(A), m_Specific(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(Cond, m_ICmp(Pred, m_Specific(B), m_Specific(A))))
202 return true;
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(CI->getOpcode(), CI->getParent(),
228 }
229 return hash_combine(CI->getOpcode(),
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>(Inst)) {
237 Value *LHS = BinOp->getOperand(0);
238 Value *RHS = BinOp->getOperand(1);
239 if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1))
240 std::swap(LHS, RHS);
241
242 return hash_combine(BinOp->getOpcode(), LHS, RHS);
243 }
244
245 if (CmpInst *CI = dyn_cast<CmpInst>(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(0);
251 Value *RHS = CI->getOperand(1);
252 CmpInst::Predicate Pred = CI->getPredicate();
253 CmpInst::Predicate SwappedPred = CI->getSwappedPredicate();
254 if (std::tie(LHS, Pred) > std::tie(RHS, SwappedPred)) {
255 std::swap(LHS, RHS);
256 Pred = SwappedPred;
257 }
258 return hash_combine(Inst->getOpcode(), Pred, LHS, RHS);
259 }
260
261 // Hash general selects to allow matching commuted true/false operands.
263 Value *Cond, *A, *B;
264 if (matchSelectWithOptionalNotCond(Inst, Cond, A, B, 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, B);
274 return hash_combine(Inst->getOpcode(), SPF, A, 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(Cond, m_Cmp(Pred, m_Value(X), m_Value(Y))))
283 return hash_combine(Inst->getOpcode(), Cond, A, 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) {
288 Pred = CmpInst::getInversePredicate(Pred);
289 std::swap(A, B);
290 }
291 return hash_combine(Inst->getOpcode(),
292 static_cast<CmpInst::Predicate>(Pred), X, Y, A, B);
293 }
294
295 if (CastInst *CI = dyn_cast<CastInst>(Inst))
296 return hash_combine(CI->getOpcode(), CI->getType(), CI->getOperand(0));
297
298 if (FreezeInst *FI = dyn_cast<FreezeInst>(Inst))
299 return hash_combine(FI->getOpcode(), FI->getOperand(0));
300
301 if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Inst))
302 return hash_combine(EVI->getOpcode(), EVI->getOperand(0),
303 hash_combine_range(EVI->indices()));
304
305 if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(Inst))
306 return hash_combine(IVI->getOpcode(), IVI->getOperand(0),
307 IVI->getOperand(1), hash_combine_range(IVI->indices()));
308
311 isa<UnaryOperator>(Inst) || isa<FreezeInst>(Inst)) &&
312 "Invalid/unknown instruction");
313
314 // Handle intrinsics with commutative operands.
315 auto *II = dyn_cast<IntrinsicInst>(Inst);
316 if (II && II->isCommutative() && II->arg_size() >= 2) {
317 Value *LHS = II->getArgOperand(0), *RHS = II->getArgOperand(1);
318 if (LHS > RHS)
319 std::swap(LHS, RHS);
320 return hash_combine(
321 II->getOpcode(), LHS, RHS,
322 hash_combine_range(drop_begin(II->operand_values(), 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>(Inst))
329 return hash_combine(GCR->getOpcode(), GCR->getOperand(0),
330 GCR->getBasePtr(), 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>(Inst))
335 return hashCallInst(CI);
336
337 // Mix in the opcode.
338 return hash_combine(Inst->getOpcode(),
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.
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(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>(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>(LHSI)) {
375 if (!LHSBinOp->isCommutative())
376 return false;
377
379 "same opcode, but different instruction type?");
380 BinaryOperator *RHSBinOp = cast<BinaryOperator>(RHSI);
381
382 // Commuted equality
383 return LHSBinOp->getOperand(0) == RHSBinOp->getOperand(1) &&
384 LHSBinOp->getOperand(1) == RHSBinOp->getOperand(0);
385 }
386 if (CmpInst *LHSCmp = dyn_cast<CmpInst>(LHSI)) {
387 assert(isa<CmpInst>(RHSI) &&
388 "same opcode, but different instruction type?");
389 CmpInst *RHSCmp = cast<CmpInst>(RHSI);
390 // Commuted equality
391 return LHSCmp->getOperand(0) == RHSCmp->getOperand(1) &&
392 LHSCmp->getOperand(1) == RHSCmp->getOperand(0) &&
393 LHSCmp->getSwappedPredicate() == RHSCmp->getPredicate();
394 }
395
396 auto *LII = dyn_cast<IntrinsicInst>(LHSI);
397 auto *RII = dyn_cast<IntrinsicInst>(RHSI);
398 if (LII && RII && LII->getIntrinsicID() == RII->getIntrinsicID() &&
399 LII->isCommutative() && LII->arg_size() >= 2) {
400 return LII->getArgOperand(0) == RII->getArgOperand(1) &&
401 LII->getArgOperand(1) == RII->getArgOperand(0) &&
402 std::equal(LII->arg_begin() + 2, LII->arg_end(),
403 RII->arg_begin() + 2, RII->arg_end()) &&
404 LII->hasSameSpecialState(RII, /*IgnoreAlignment=*/false,
405 /*IntersectAttrs=*/true);
406 }
407
408 // See comment above in `getHashValue()`.
409 if (const GCRelocateInst *GCR1 = dyn_cast<GCRelocateInst>(LHSI))
410 if (const GCRelocateInst *GCR2 = dyn_cast<GCRelocateInst>(RHSI))
411 return GCR1->getOperand(0) == GCR2->getOperand(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(LHSI, CondL, LHSA, LHSB, LSPF) &&
421 matchSelectWithOptionalNotCond(RHSI, CondR, RHSA, RHSB, 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(CondL, m_Cmp(PredL, m_Value(X), m_Value(Y))) &&
456 match(CondR, m_Cmp(PredR, m_Specific(X), m_Specific(Y))) &&
457 CmpInst::getInversePredicate(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) ||
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>(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.
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() {
517 }
518
519 static inline CallValue 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(cast<CallInst>(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>(LHS.Inst);
541 CallInst *RHSI = cast<CallInst>(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(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>(Inst);
578 }
579};
580
581} // namespace
582
583namespace llvm {
584
585template <> struct DenseMapInfo<GEPValue> {
586 static inline GEPValue getEmptyKey() {
588 }
589
590 static inline GEPValue 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.Inst);
602 if (Val.ConstantOffset.has_value())
603 return hash_combine(GEP->getOpcode(), GEP->getPointerOperand(),
604 Val.ConstantOffset.value());
605 return hash_combine(GEP->getOpcode(),
606 hash_combine_range(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>(LHS.Inst);
613 auto *RGEP = cast<GetElementPtrInst>(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(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>(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:
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,
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;
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>(Inst)) {
810 IntrID = II->getIntrinsicID();
811 if (TTI.getTgtMemIntrinsic(II, Info))
812 return;
813 if (isHandledNonTargetIntrinsic(IntrID)) {
814 switch (IntrID) {
815 case Intrinsic::masked_load:
816 Info.PtrVal = Inst->getOperand(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(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>(Inst);
847 }
848
849 bool isStore() const {
850 if (IntrID != 0)
851 return Info.WriteMem;
852 return isa<StoreInst>(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>(Inst)) {
866 return LI->isUnordered();
867 } else if (StoreInst *SI = dyn_cast<StoreInst>(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>(Inst)) {
879 return LI->isVolatile();
880 } else if (StoreInst *SI = dyn_cast<StoreInst>(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>(Inst))
889 return LI->hasMetadata(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(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>(V))
946 return isHandledNonTargetIntrinsic(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,
962 bool CanCreate) const {
963 // TODO: We could insert relevant casts on type mismatch.
964 // The load or the store's first operand.
965 Value *V;
966 if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
967 switch (II->getIntrinsicID()) {
968 case Intrinsic::masked_load:
969 V = II;
970 break;
971 case Intrinsic::masked_store:
972 V = II->getOperand(0);
973 break;
974 default:
975 return TTI.getOrCreateResultFromMemIntrinsic(II, ExpectedType,
976 CanCreate);
977 }
978 } else {
979 V = isa<LoadInst>(Inst) ? Inst : cast<StoreInst>(Inst)->getValueOperand();
980 }
981
982 return V->getType() == ExpectedType ? V : nullptr;
983 }
984
985 /// Return true if the instruction is known to only operate on memory
986 /// provably invariant in the given "generation".
987 bool isOperatingOnInvariantMemAt(Instruction *I, unsigned GenAt);
988
989 bool isSameMemGeneration(unsigned EarlierGeneration, unsigned LaterGeneration,
990 Instruction *EarlierInst, Instruction *LaterInst);
991
992 bool isNonTargetIntrinsicMatch(const IntrinsicInst *Earlier,
993 const IntrinsicInst *Later) {
994 auto IsSubmask = [](const Value *Mask0, const Value *Mask1) {
995 // Is Mask0 a submask of Mask1?
996 if (Mask0 == Mask1)
997 return true;
998 if (isa<UndefValue>(Mask0) || isa<UndefValue>(Mask1))
999 return false;
1000 auto *Vec0 = dyn_cast<ConstantVector>(Mask0);
1001 auto *Vec1 = dyn_cast<ConstantVector>(Mask1);
1002 if (!Vec0 || !Vec1)
1003 return false;
1004 if (Vec0->getType() != Vec1->getType())
1005 return false;
1006 for (int i = 0, e = Vec0->getNumOperands(); i != e; ++i) {
1007 Constant *Elem0 = Vec0->getOperand(i);
1008 Constant *Elem1 = Vec1->getOperand(i);
1009 auto *Int0 = dyn_cast<ConstantInt>(Elem0);
1010 if (Int0 && Int0->isZero())
1011 continue;
1012 auto *Int1 = dyn_cast<ConstantInt>(Elem1);
1013 if (Int1 && !Int1->isZero())
1014 continue;
1015 if (isa<UndefValue>(Elem0) || isa<UndefValue>(Elem1))
1016 return false;
1017 if (Elem0 == Elem1)
1018 continue;
1019 return false;
1020 }
1021 return true;
1022 };
1023 auto PtrOp = [](const IntrinsicInst *II) {
1024 if (II->getIntrinsicID() == Intrinsic::masked_load)
1025 return II->getOperand(0);
1026 if (II->getIntrinsicID() == Intrinsic::masked_store)
1027 return II->getOperand(1);
1028 llvm_unreachable("Unexpected IntrinsicInst");
1029 };
1030 auto MaskOp = [](const IntrinsicInst *II) {
1031 if (II->getIntrinsicID() == Intrinsic::masked_load)
1032 return II->getOperand(2);
1033 if (II->getIntrinsicID() == Intrinsic::masked_store)
1034 return II->getOperand(3);
1035 llvm_unreachable("Unexpected IntrinsicInst");
1036 };
1037 auto ThruOp = [](const IntrinsicInst *II) {
1038 if (II->getIntrinsicID() == Intrinsic::masked_load)
1039 return II->getOperand(3);
1040 llvm_unreachable("Unexpected IntrinsicInst");
1041 };
1042
1043 if (PtrOp(Earlier) != PtrOp(Later))
1044 return false;
1045
1046 Intrinsic::ID IDE = Earlier->getIntrinsicID();
1047 Intrinsic::ID IDL = Later->getIntrinsicID();
1048 // We could really use specific intrinsic classes for masked loads
1049 // and stores in IntrinsicInst.h.
1050 if (IDE == Intrinsic::masked_load && IDL == Intrinsic::masked_load) {
1051 // Trying to replace later masked load with the earlier one.
1052 // Check that the pointers are the same, and
1053 // - masks and pass-throughs are the same, or
1054 // - replacee's pass-through is "undef" and replacer's mask is a
1055 // super-set of the replacee's mask.
1056 if (MaskOp(Earlier) == MaskOp(Later) && ThruOp(Earlier) == ThruOp(Later))
1057 return true;
1058 if (!isa<UndefValue>(ThruOp(Later)))
1059 return false;
1060 return IsSubmask(MaskOp(Later), MaskOp(Earlier));
1061 }
1062 if (IDE == Intrinsic::masked_store && IDL == Intrinsic::masked_load) {
1063 // Trying to replace a load of a stored value with the store's value.
1064 // Check that the pointers are the same, and
1065 // - load's mask is a subset of store's mask, and
1066 // - load's pass-through is "undef".
1067 if (!IsSubmask(MaskOp(Later), MaskOp(Earlier)))
1068 return false;
1069 return isa<UndefValue>(ThruOp(Later));
1070 }
1071 if (IDE == Intrinsic::masked_load && IDL == Intrinsic::masked_store) {
1072 // Trying to remove a store of the loaded value.
1073 // Check that the pointers are the same, and
1074 // - store's mask is a subset of the load's mask.
1075 return IsSubmask(MaskOp(Later), MaskOp(Earlier));
1076 }
1077 if (IDE == Intrinsic::masked_store && IDL == Intrinsic::masked_store) {
1078 // Trying to remove a dead store (earlier).
1079 // Check that the pointers are the same,
1080 // - the to-be-removed store's mask is a subset of the other store's
1081 // mask.
1082 return IsSubmask(MaskOp(Earlier), MaskOp(Later));
1083 }
1084 return false;
1085 }
1086
1087 void removeMSSA(Instruction &Inst) {
1088 if (!MSSA)
1089 return;
1090 if (VerifyMemorySSA)
1091 MSSA->verifyMemorySSA();
1092 // Removing a store here can leave MemorySSA in an unoptimized state by
1093 // creating MemoryPhis that have identical arguments and by creating
1094 // MemoryUses whose defining access is not an actual clobber. The phi case
1095 // is handled by MemorySSA when passing OptimizePhis = true to
1096 // removeMemoryAccess. The non-optimized MemoryUse case is lazily updated
1097 // by MemorySSA's getClobberingMemoryAccess.
1098 MSSAUpdater->removeMemoryAccess(&Inst, true);
1099 }
1100};
1101
1102} // end anonymous namespace
1103
1104/// Determine if the memory referenced by LaterInst is from the same heap
1105/// version as EarlierInst.
1106/// This is currently called in two scenarios:
1107///
1108/// load p
1109/// ...
1110/// load p
1111///
1112/// and
1113///
1114/// x = load p
1115/// ...
1116/// store x, p
1117///
1118/// in both cases we want to verify that there are no possible writes to the
1119/// memory referenced by p between the earlier and later instruction.
1120bool EarlyCSE::isSameMemGeneration(unsigned EarlierGeneration,
1121 unsigned LaterGeneration,
1122 Instruction *EarlierInst,
1123 Instruction *LaterInst) {
1124 // Check the simple memory generation tracking first.
1125 if (EarlierGeneration == LaterGeneration)
1126 return true;
1127
1128 if (!MSSA)
1129 return false;
1130
1131 // If MemorySSA has determined that one of EarlierInst or LaterInst does not
1132 // read/write memory, then we can safely return true here.
1133 // FIXME: We could be more aggressive when checking doesNotAccessMemory(),
1134 // onlyReadsMemory(), mayReadFromMemory(), and mayWriteToMemory() in this pass
1135 // by also checking the MemorySSA MemoryAccess on the instruction. Initial
1136 // experiments suggest this isn't worthwhile, at least for C/C++ code compiled
1137 // with the default optimization pipeline.
1138 auto *EarlierMA = MSSA->getMemoryAccess(EarlierInst);
1139 if (!EarlierMA)
1140 return true;
1141 auto *LaterMA = MSSA->getMemoryAccess(LaterInst);
1142 if (!LaterMA)
1143 return true;
1144
1145 // Since we know LaterDef dominates LaterInst and EarlierInst dominates
1146 // LaterInst, if LaterDef dominates EarlierInst then it can't occur between
1147 // EarlierInst and LaterInst and neither can any other write that potentially
1148 // clobbers LaterInst.
1149 MemoryAccess *LaterDef;
1150 if (ClobberCounter < EarlyCSEMssaOptCap) {
1151 LaterDef = MSSA->getWalker()->getClobberingMemoryAccess(LaterInst);
1152 ClobberCounter++;
1153 } else
1154 LaterDef = LaterMA->getDefiningAccess();
1155
1156 return MSSA->dominates(LaterDef, EarlierMA);
1157}
1158
1159bool EarlyCSE::isOperatingOnInvariantMemAt(Instruction *I, unsigned GenAt) {
1160 // A location loaded from with an invariant_load is assumed to *never* change
1161 // within the visible scope of the compilation.
1162 if (auto *LI = dyn_cast<LoadInst>(I))
1163 if (LI->hasMetadata(LLVMContext::MD_invariant_load))
1164 return true;
1165
1166 auto MemLocOpt = MemoryLocation::getOrNone(I);
1167 if (!MemLocOpt)
1168 // "target" intrinsic forms of loads aren't currently known to
1169 // MemoryLocation::get. TODO
1170 return false;
1171 MemoryLocation MemLoc = *MemLocOpt;
1172 if (!AvailableInvariants.count(MemLoc))
1173 return false;
1174
1175 // Is the generation at which this became invariant older than the
1176 // current one?
1177 return AvailableInvariants.lookup(MemLoc) <= GenAt;
1178}
1179
1180bool EarlyCSE::handleBranchCondition(Instruction *CondInst,
1181 const BranchInst *BI, const BasicBlock *BB,
1182 const BasicBlock *Pred) {
1183 assert(BI->isConditional() && "Should be a conditional branch!");
1184 assert(BI->getCondition() == CondInst && "Wrong condition?");
1185 assert(BI->getSuccessor(0) == BB || BI->getSuccessor(1) == BB);
1186 auto *TorF = (BI->getSuccessor(0) == BB)
1188 : ConstantInt::getFalse(BB->getContext());
1189 auto MatchBinOp = [](Instruction *I, unsigned Opcode, Value *&LHS,
1190 Value *&RHS) {
1191 if (Opcode == Instruction::And &&
1193 return true;
1194 else if (Opcode == Instruction::Or &&
1196 return true;
1197 return false;
1198 };
1199 // If the condition is AND operation, we can propagate its operands into the
1200 // true branch. If it is OR operation, we can propagate them into the false
1201 // branch.
1202 unsigned PropagateOpcode =
1203 (BI->getSuccessor(0) == BB) ? Instruction::And : Instruction::Or;
1204
1205 bool MadeChanges = false;
1206 SmallVector<Instruction *, 4> WorkList;
1207 SmallPtrSet<Instruction *, 4> Visited;
1208 WorkList.push_back(CondInst);
1209 while (!WorkList.empty()) {
1210 Instruction *Curr = WorkList.pop_back_val();
1211
1212 AvailableValues.insert(Curr, TorF);
1213 LLVM_DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"
1214 << Curr->getName() << "' as " << *TorF << " in "
1215 << BB->getName() << "\n");
1216 if (!DebugCounter::shouldExecute(CSECounter)) {
1217 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1218 } else {
1219 // Replace all dominated uses with the known value.
1220 if (unsigned Count = replaceDominatedUsesWith(Curr, TorF, DT,
1221 BasicBlockEdge(Pred, BB))) {
1222 NumCSECVP += Count;
1223 MadeChanges = true;
1224 }
1225 }
1226
1227 Value *LHS, *RHS;
1228 if (MatchBinOp(Curr, PropagateOpcode, LHS, RHS))
1229 for (auto *Op : { LHS, RHS })
1230 if (Instruction *OPI = dyn_cast<Instruction>(Op))
1231 if (SimpleValue::canHandle(OPI) && Visited.insert(OPI).second)
1232 WorkList.push_back(OPI);
1233 }
1234
1235 return MadeChanges;
1236}
1237
1238Value *EarlyCSE::getMatchingValue(LoadValue &InVal, ParseMemoryInst &MemInst,
1239 unsigned CurrentGeneration) {
1240 if (InVal.DefInst == nullptr)
1241 return nullptr;
1242 if (InVal.MatchingId != MemInst.getMatchingId())
1243 return nullptr;
1244 // We don't yet handle removing loads with ordering of any kind.
1245 if (MemInst.isVolatile() || !MemInst.isUnordered())
1246 return nullptr;
1247 // We can't replace an atomic load with one which isn't also atomic.
1248 if (MemInst.isLoad() && !InVal.IsAtomic && MemInst.isAtomic())
1249 return nullptr;
1250 // The value V returned from this function is used differently depending
1251 // on whether MemInst is a load or a store. If it's a load, we will replace
1252 // MemInst with V, if it's a store, we will check if V is the same as the
1253 // available value.
1254 bool MemInstMatching = !MemInst.isLoad();
1255 Instruction *Matching = MemInstMatching ? MemInst.get() : InVal.DefInst;
1256 Instruction *Other = MemInstMatching ? InVal.DefInst : MemInst.get();
1257
1258 // For stores check the result values before checking memory generation
1259 // (otherwise isSameMemGeneration may crash).
1260 Value *Result =
1261 MemInst.isStore()
1262 ? getOrCreateResult(Matching, Other->getType(), /*CanCreate=*/false)
1263 : nullptr;
1264 if (MemInst.isStore() && InVal.DefInst != Result)
1265 return nullptr;
1266
1267 // Deal with non-target memory intrinsics.
1268 bool MatchingNTI = isHandledNonTargetIntrinsic(Matching);
1269 bool OtherNTI = isHandledNonTargetIntrinsic(Other);
1270 if (OtherNTI != MatchingNTI)
1271 return nullptr;
1272 if (OtherNTI && MatchingNTI) {
1273 if (!isNonTargetIntrinsicMatch(cast<IntrinsicInst>(InVal.DefInst),
1274 cast<IntrinsicInst>(MemInst.get())))
1275 return nullptr;
1276 }
1277
1278 if (!isOperatingOnInvariantMemAt(MemInst.get(), InVal.Generation) &&
1279 !isSameMemGeneration(InVal.Generation, CurrentGeneration, InVal.DefInst,
1280 MemInst.get()))
1281 return nullptr;
1282
1283 if (!Result)
1284 Result = getOrCreateResult(Matching, Other->getType(), /*CanCreate=*/true);
1285 return Result;
1286}
1287
1288static void combineIRFlags(Instruction &From, Value *To) {
1289 if (auto *I = dyn_cast<Instruction>(To)) {
1290 // If I being poison triggers UB, there is no need to drop those
1291 // flags. Otherwise, only retain flags present on both I and Inst.
1292 // TODO: Currently some fast-math flags are not treated as
1293 // poison-generating even though they should. Until this is fixed,
1294 // always retain flags present on both I and Inst for floating point
1295 // instructions.
1296 if (isa<FPMathOperator>(I) ||
1297 (I->hasPoisonGeneratingFlags() && !programUndefinedIfPoison(I)))
1298 I->andIRFlags(&From);
1299 }
1300 if (isa<CallBase>(&From) && isa<CallBase>(To)) {
1301 // NB: Intersection of attrs between InVal.first and Inst is overly
1302 // conservative. Since we only CSE readonly functions that have the same
1303 // memory state, we can preserve (or possibly in some cases combine)
1304 // more attributes. Likewise this implies when checking equality of
1305 // callsite for CSEing, we can probably ignore more attributes.
1306 // Generally poison generating attributes need to be handled with more
1307 // care as they can create *new* UB if preserved/combined and violated.
1308 // Attributes that imply immediate UB on the other hand would have been
1309 // violated either way.
1310 bool Success =
1311 cast<CallBase>(To)->tryIntersectAttributes(cast<CallBase>(&From));
1312 assert(Success && "Failed to intersect attributes in callsites that "
1313 "passed identical check");
1314 // For NDEBUG Compile.
1315 (void)Success;
1316 }
1317}
1318
1319bool EarlyCSE::overridingStores(const ParseMemoryInst &Earlier,
1320 const ParseMemoryInst &Later) {
1321 // Can we remove Earlier store because of Later store?
1322
1323 assert(Earlier.isUnordered() && !Earlier.isVolatile() &&
1324 "Violated invariant");
1325 if (Earlier.getPointerOperand() != Later.getPointerOperand())
1326 return false;
1327 if (!Earlier.getValueType() || !Later.getValueType() ||
1328 Earlier.getValueType() != Later.getValueType())
1329 return false;
1330 if (Earlier.getMatchingId() != Later.getMatchingId())
1331 return false;
1332 // At the moment, we don't remove ordered stores, but do remove
1333 // unordered atomic stores. There's no special requirement (for
1334 // unordered atomics) about removing atomic stores only in favor of
1335 // other atomic stores since we were going to execute the non-atomic
1336 // one anyway and the atomic one might never have become visible.
1337 if (!Earlier.isUnordered() || !Later.isUnordered())
1338 return false;
1339
1340 // Deal with non-target memory intrinsics.
1341 bool ENTI = isHandledNonTargetIntrinsic(Earlier.get());
1342 bool LNTI = isHandledNonTargetIntrinsic(Later.get());
1343 if (ENTI && LNTI)
1344 return isNonTargetIntrinsicMatch(cast<IntrinsicInst>(Earlier.get()),
1345 cast<IntrinsicInst>(Later.get()));
1346
1347 // Because of the check above, at least one of them is false.
1348 // For now disallow matching intrinsics with non-intrinsics,
1349 // so assume that the stores match if neither is an intrinsic.
1350 return ENTI == LNTI;
1351}
1352
1353bool EarlyCSE::processNode(DomTreeNode *Node) {
1354 bool Changed = false;
1355 BasicBlock *BB = Node->getBlock();
1356
1357 // If this block has a single predecessor, then the predecessor is the parent
1358 // of the domtree node and all of the live out memory values are still current
1359 // in this block. If this block has multiple predecessors, then they could
1360 // have invalidated the live-out memory values of our parent value. For now,
1361 // just be conservative and invalidate memory if this block has multiple
1362 // predecessors.
1363 if (!BB->getSinglePredecessor())
1364 ++CurrentGeneration;
1365
1366 // If this node has a single predecessor which ends in a conditional branch,
1367 // we can infer the value of the branch condition given that we took this
1368 // path. We need the single predecessor to ensure there's not another path
1369 // which reaches this block where the condition might hold a different
1370 // value. Since we're adding this to the scoped hash table (like any other
1371 // def), it will have been popped if we encounter a future merge block.
1372 if (BasicBlock *Pred = BB->getSinglePredecessor()) {
1373 auto *BI = dyn_cast<BranchInst>(Pred->getTerminator());
1374 if (BI && BI->isConditional()) {
1375 auto *CondInst = dyn_cast<Instruction>(BI->getCondition());
1376 if (CondInst && SimpleValue::canHandle(CondInst))
1377 Changed |= handleBranchCondition(CondInst, BI, BB, Pred);
1378 }
1379 }
1380
1381 /// LastStore - Keep track of the last non-volatile store that we saw... for
1382 /// as long as there in no instruction that reads memory. If we see a store
1383 /// to the same location, we delete the dead store. This zaps trivial dead
1384 /// stores which can occur in bitfield code among other things.
1385 Instruction *LastStore = nullptr;
1386
1387 // See if any instructions in the block can be eliminated. If so, do it. If
1388 // not, add them to AvailableValues.
1389 for (Instruction &Inst : make_early_inc_range(*BB)) {
1390 // Dead instructions should just be removed.
1391 if (isInstructionTriviallyDead(&Inst, &TLI)) {
1392 LLVM_DEBUG(dbgs() << "EarlyCSE DCE: " << Inst << '\n');
1393 if (!DebugCounter::shouldExecute(CSECounter)) {
1394 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1395 continue;
1396 }
1397
1398 salvageKnowledge(&Inst, &AC);
1399 salvageDebugInfo(Inst);
1400 removeMSSA(Inst);
1401 Inst.eraseFromParent();
1402 Changed = true;
1403 ++NumSimplify;
1404 continue;
1405 }
1406
1407 // Skip assume intrinsics, they don't really have side effects (although
1408 // they're marked as such to ensure preservation of control dependencies),
1409 // and this pass will not bother with its removal. However, we should mark
1410 // its condition as true for all dominated blocks.
1411 if (auto *Assume = dyn_cast<AssumeInst>(&Inst)) {
1412 auto *CondI = dyn_cast<Instruction>(Assume->getArgOperand(0));
1413 if (CondI && SimpleValue::canHandle(CondI)) {
1414 LLVM_DEBUG(dbgs() << "EarlyCSE considering assumption: " << Inst
1415 << '\n');
1416 AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
1417 } else
1418 LLVM_DEBUG(dbgs() << "EarlyCSE skipping assumption: " << Inst << '\n');
1419 continue;
1420 }
1421
1422 // Likewise, noalias intrinsics don't actually write.
1423 if (match(&Inst,
1425 LLVM_DEBUG(dbgs() << "EarlyCSE skipping noalias intrinsic: " << Inst
1426 << '\n');
1427 continue;
1428 }
1429
1430 // Skip sideeffect intrinsics, for the same reason as assume intrinsics.
1432 LLVM_DEBUG(dbgs() << "EarlyCSE skipping sideeffect: " << Inst << '\n');
1433 continue;
1434 }
1435
1436 // Skip pseudoprobe intrinsics, for the same reason as assume intrinsics.
1438 LLVM_DEBUG(dbgs() << "EarlyCSE skipping pseudoprobe: " << Inst << '\n');
1439 continue;
1440 }
1441
1442 // We can skip all invariant.start intrinsics since they only read memory,
1443 // and we can forward values across it. For invariant starts without
1444 // invariant ends, we can use the fact that the invariantness never ends to
1445 // start a scope in the current generaton which is true for all future
1446 // generations. Also, we dont need to consume the last store since the
1447 // semantics of invariant.start allow us to perform DSE of the last
1448 // store, if there was a store following invariant.start. Consider:
1449 //
1450 // store 30, i8* p
1451 // invariant.start(p)
1452 // store 40, i8* p
1453 // We can DSE the store to 30, since the store 40 to invariant location p
1454 // causes undefined behaviour.
1456 // If there are any uses, the scope might end.
1457 if (!Inst.use_empty())
1458 continue;
1459 MemoryLocation MemLoc =
1461 // Don't start a scope if we already have a better one pushed
1462 if (!AvailableInvariants.count(MemLoc))
1463 AvailableInvariants.insert(MemLoc, CurrentGeneration);
1464 continue;
1465 }
1466
1467 if (isGuard(&Inst)) {
1468 if (auto *CondI =
1469 dyn_cast<Instruction>(cast<CallInst>(Inst).getArgOperand(0))) {
1470 if (SimpleValue::canHandle(CondI)) {
1471 // Do we already know the actual value of this condition?
1472 if (auto *KnownCond = AvailableValues.lookup(CondI)) {
1473 // Is the condition known to be true?
1474 if (isa<ConstantInt>(KnownCond) &&
1475 cast<ConstantInt>(KnownCond)->isOne()) {
1477 << "EarlyCSE removing guard: " << Inst << '\n');
1478 salvageKnowledge(&Inst, &AC);
1479 removeMSSA(Inst);
1480 Inst.eraseFromParent();
1481 Changed = true;
1482 continue;
1483 } else
1484 // Use the known value if it wasn't true.
1485 cast<CallInst>(Inst).setArgOperand(0, KnownCond);
1486 }
1487 // The condition we're on guarding here is true for all dominated
1488 // locations.
1489 AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
1490 }
1491 }
1492
1493 // Guard intrinsics read all memory, but don't write any memory.
1494 // Accordingly, don't update the generation but consume the last store (to
1495 // avoid an incorrect DSE).
1496 LastStore = nullptr;
1497 continue;
1498 }
1499
1500 // If the instruction can be simplified (e.g. X+0 = X) then replace it with
1501 // its simpler value.
1502 if (Value *V = simplifyInstruction(&Inst, SQ)) {
1503 LLVM_DEBUG(dbgs() << "EarlyCSE Simplify: " << Inst << " to: " << *V
1504 << '\n');
1505 if (!DebugCounter::shouldExecute(CSECounter)) {
1506 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1507 } else {
1508 bool Killed = false;
1509 if (!Inst.use_empty()) {
1510 Inst.replaceAllUsesWith(V);
1511 Changed = true;
1512 }
1513 if (isInstructionTriviallyDead(&Inst, &TLI)) {
1514 salvageKnowledge(&Inst, &AC);
1515 removeMSSA(Inst);
1516 Inst.eraseFromParent();
1517 Changed = true;
1518 Killed = true;
1519 }
1520 if (Changed)
1521 ++NumSimplify;
1522 if (Killed)
1523 continue;
1524 }
1525 }
1526
1527 // Make sure stores prior to a potential unwind are not removed, as the
1528 // caller may read the memory.
1529 if (Inst.mayThrow())
1530 LastStore = nullptr;
1531
1532 // If this is a simple instruction that we can value number, process it.
1533 if (SimpleValue::canHandle(&Inst)) {
1534 if ([[maybe_unused]] auto *CI = dyn_cast<ConstrainedFPIntrinsic>(&Inst)) {
1535 assert(CI->getExceptionBehavior() != fp::ebStrict &&
1536 "Unexpected ebStrict from SimpleValue::canHandle()");
1537 assert((!CI->getRoundingMode() ||
1538 CI->getRoundingMode() != RoundingMode::Dynamic) &&
1539 "Unexpected dynamic rounding from SimpleValue::canHandle()");
1540 }
1541 // See if the instruction has an available value. If so, use it.
1542 if (Value *V = AvailableValues.lookup(&Inst)) {
1543 LLVM_DEBUG(dbgs() << "EarlyCSE CSE: " << Inst << " to: " << *V
1544 << '\n');
1545 if (!DebugCounter::shouldExecute(CSECounter)) {
1546 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1547 continue;
1548 }
1549 combineIRFlags(Inst, V);
1550 Inst.replaceAllUsesWith(V);
1551 salvageKnowledge(&Inst, &AC);
1552 removeMSSA(Inst);
1553 Inst.eraseFromParent();
1554 Changed = true;
1555 ++NumCSE;
1556 continue;
1557 }
1558
1559 // Otherwise, just remember that this value is available.
1560 AvailableValues.insert(&Inst, &Inst);
1561 continue;
1562 }
1563
1564 ParseMemoryInst MemInst(&Inst, TTI);
1565 // If this is a non-volatile load, process it.
1566 if (MemInst.isValid() && MemInst.isLoad()) {
1567 // (conservatively) we can't peak past the ordering implied by this
1568 // operation, but we can add this load to our set of available values
1569 if (MemInst.isVolatile() || !MemInst.isUnordered()) {
1570 LastStore = nullptr;
1571 ++CurrentGeneration;
1572 }
1573
1574 if (MemInst.isInvariantLoad()) {
1575 // If we pass an invariant load, we know that memory location is
1576 // indefinitely constant from the moment of first dereferenceability.
1577 // We conservatively treat the invariant_load as that moment. If we
1578 // pass a invariant load after already establishing a scope, don't
1579 // restart it since we want to preserve the earliest point seen.
1580 auto MemLoc = MemoryLocation::get(&Inst);
1581 if (!AvailableInvariants.count(MemLoc))
1582 AvailableInvariants.insert(MemLoc, CurrentGeneration);
1583 }
1584
1585 // If we have an available version of this load, and if it is the right
1586 // generation or the load is known to be from an invariant location,
1587 // replace this instruction.
1588 //
1589 // If either the dominating load or the current load are invariant, then
1590 // we can assume the current load loads the same value as the dominating
1591 // load.
1592 LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
1593 if (Value *Op = getMatchingValue(InVal, MemInst, CurrentGeneration)) {
1594 LLVM_DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << Inst
1595 << " to: " << *InVal.DefInst << '\n');
1596 if (!DebugCounter::shouldExecute(CSECounter)) {
1597 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1598 continue;
1599 }
1600 if (InVal.IsLoad)
1601 if (auto *I = dyn_cast<Instruction>(Op))
1602 combineMetadataForCSE(I, &Inst, false);
1603 if (!Inst.use_empty())
1604 Inst.replaceAllUsesWith(Op);
1605 salvageKnowledge(&Inst, &AC);
1606 removeMSSA(Inst);
1607 Inst.eraseFromParent();
1608 Changed = true;
1609 ++NumCSELoad;
1610 continue;
1611 }
1612
1613 // Otherwise, remember that we have this instruction.
1614 AvailableLoads.insert(MemInst.getPointerOperand(),
1615 LoadValue(&Inst, CurrentGeneration,
1616 MemInst.getMatchingId(),
1617 MemInst.isAtomic(),
1618 MemInst.isLoad()));
1619 LastStore = nullptr;
1620 continue;
1621 }
1622
1623 // If this instruction may read from memory, forget LastStore. Load/store
1624 // intrinsics will indicate both a read and a write to memory. The target
1625 // may override this (e.g. so that a store intrinsic does not read from
1626 // memory, and thus will be treated the same as a regular store for
1627 // commoning purposes).
1628 if (Inst.mayReadFromMemory() &&
1629 !(MemInst.isValid() && !MemInst.mayReadFromMemory()))
1630 LastStore = nullptr;
1631
1632 // If this is a read-only or write-only call, process it. Skip store
1633 // MemInsts, as they will be more precisely handled later on. Also skip
1634 // memsets, as DSE may be able to optimize them better by removing the
1635 // earlier rather than later store.
1636 if (CallValue::canHandle(&Inst) &&
1637 (!MemInst.isValid() || !MemInst.isStore()) && !isa<MemSetInst>(&Inst)) {
1638 // If we have an available version of this call, and if it is the right
1639 // generation, replace this instruction.
1640 std::pair<Instruction *, unsigned> InVal = AvailableCalls.lookup(&Inst);
1641 if (InVal.first != nullptr &&
1642 isSameMemGeneration(InVal.second, CurrentGeneration, InVal.first,
1643 &Inst) &&
1644 InVal.first->mayReadFromMemory() == Inst.mayReadFromMemory()) {
1645 LLVM_DEBUG(dbgs() << "EarlyCSE CSE CALL: " << Inst
1646 << " to: " << *InVal.first << '\n');
1647 if (!DebugCounter::shouldExecute(CSECounter)) {
1648 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1649 continue;
1650 }
1651 combineIRFlags(Inst, InVal.first);
1652 if (!Inst.use_empty())
1653 Inst.replaceAllUsesWith(InVal.first);
1654 salvageKnowledge(&Inst, &AC);
1655 removeMSSA(Inst);
1656 Inst.eraseFromParent();
1657 Changed = true;
1658 ++NumCSECall;
1659 continue;
1660 }
1661
1662 // Increase memory generation for writes. Do this before inserting
1663 // the call, so it has the generation after the write occurred.
1664 if (Inst.mayWriteToMemory())
1665 ++CurrentGeneration;
1666
1667 // Otherwise, remember that we have this instruction.
1668 AvailableCalls.insert(&Inst, std::make_pair(&Inst, CurrentGeneration));
1669 continue;
1670 }
1671
1672 // Compare GEP instructions based on offset.
1673 if (GEPValue::canHandle(&Inst)) {
1674 auto *GEP = cast<GetElementPtrInst>(&Inst);
1675 APInt Offset = APInt(SQ.DL.getIndexTypeSizeInBits(GEP->getType()), 0);
1676 GEPValue GEPVal(GEP, GEP->accumulateConstantOffset(SQ.DL, Offset)
1677 ? Offset.trySExtValue()
1678 : std::nullopt);
1679 if (Value *V = AvailableGEPs.lookup(GEPVal)) {
1680 LLVM_DEBUG(dbgs() << "EarlyCSE CSE GEP: " << Inst << " to: " << *V
1681 << '\n');
1682 combineIRFlags(Inst, V);
1683 Inst.replaceAllUsesWith(V);
1684 salvageKnowledge(&Inst, &AC);
1685 removeMSSA(Inst);
1686 Inst.eraseFromParent();
1687 Changed = true;
1688 ++NumCSEGEP;
1689 continue;
1690 }
1691
1692 // Otherwise, just remember that we have this GEP.
1693 AvailableGEPs.insert(GEPVal, &Inst);
1694 continue;
1695 }
1696
1697 // A release fence requires that all stores complete before it, but does
1698 // not prevent the reordering of following loads 'before' the fence. As a
1699 // result, we don't need to consider it as writing to memory and don't need
1700 // to advance the generation. We do need to prevent DSE across the fence,
1701 // but that's handled above.
1702 if (auto *FI = dyn_cast<FenceInst>(&Inst))
1703 if (FI->getOrdering() == AtomicOrdering::Release) {
1704 assert(Inst.mayReadFromMemory() && "relied on to prevent DSE above");
1705 continue;
1706 }
1707
1708 // write back DSE - If we write back the same value we just loaded from
1709 // the same location and haven't passed any intervening writes or ordering
1710 // operations, we can remove the write. The primary benefit is in allowing
1711 // the available load table to remain valid and value forward past where
1712 // the store originally was.
1713 if (MemInst.isValid() && MemInst.isStore()) {
1714 LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
1715 if (InVal.DefInst &&
1716 InVal.DefInst ==
1717 getMatchingValue(InVal, MemInst, CurrentGeneration)) {
1718 LLVM_DEBUG(dbgs() << "EarlyCSE DSE (writeback): " << Inst << '\n');
1719 if (!DebugCounter::shouldExecute(CSECounter)) {
1720 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1721 continue;
1722 }
1723 salvageKnowledge(&Inst, &AC);
1724 removeMSSA(Inst);
1725 Inst.eraseFromParent();
1726 Changed = true;
1727 ++NumDSE;
1728 // We can avoid incrementing the generation count since we were able
1729 // to eliminate this store.
1730 continue;
1731 }
1732 }
1733
1734 // Okay, this isn't something we can CSE at all. Check to see if it is
1735 // something that could modify memory. If so, our available memory values
1736 // cannot be used so bump the generation count.
1737 if (Inst.mayWriteToMemory()) {
1738 ++CurrentGeneration;
1739
1740 if (MemInst.isValid() && MemInst.isStore()) {
1741 // We do a trivial form of DSE if there are two stores to the same
1742 // location with no intervening loads. Delete the earlier store.
1743 if (LastStore) {
1744 if (overridingStores(ParseMemoryInst(LastStore, TTI), MemInst)) {
1745 LLVM_DEBUG(dbgs() << "EarlyCSE DEAD STORE: " << *LastStore
1746 << " due to: " << Inst << '\n');
1747 if (!DebugCounter::shouldExecute(CSECounter)) {
1748 LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
1749 } else {
1750 salvageKnowledge(&Inst, &AC);
1751 removeMSSA(*LastStore);
1752 LastStore->eraseFromParent();
1753 Changed = true;
1754 ++NumDSE;
1755 LastStore = nullptr;
1756 }
1757 }
1758 // fallthrough - we can exploit information about this store
1759 }
1760
1761 // Okay, we just invalidated anything we knew about loaded values. Try
1762 // to salvage *something* by remembering that the stored value is a live
1763 // version of the pointer. It is safe to forward from volatile stores
1764 // to non-volatile loads, so we don't have to check for volatility of
1765 // the store.
1766 AvailableLoads.insert(MemInst.getPointerOperand(),
1767 LoadValue(&Inst, CurrentGeneration,
1768 MemInst.getMatchingId(),
1769 MemInst.isAtomic(),
1770 MemInst.isLoad()));
1771
1772 // Remember that this was the last unordered store we saw for DSE. We
1773 // don't yet handle DSE on ordered or volatile stores since we don't
1774 // have a good way to model the ordering requirement for following
1775 // passes once the store is removed. We could insert a fence, but
1776 // since fences are slightly stronger than stores in their ordering,
1777 // it's not clear this is a profitable transform. Another option would
1778 // be to merge the ordering with that of the post dominating store.
1779 if (MemInst.isUnordered() && !MemInst.isVolatile())
1780 LastStore = &Inst;
1781 else
1782 LastStore = nullptr;
1783 }
1784 }
1785 }
1786
1787 return Changed;
1788}
1789
1790bool EarlyCSE::run() {
1791 // Note, deque is being used here because there is significant performance
1792 // gains over vector when the container becomes very large due to the
1793 // specific access patterns. For more information see the mailing list
1794 // discussion on this:
1795 // http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html
1796 std::deque<StackNode *> nodesToProcess;
1797
1798 bool Changed = false;
1799
1800 // Process the root node.
1801 nodesToProcess.push_back(new StackNode(
1802 AvailableValues, AvailableLoads, AvailableInvariants, AvailableCalls,
1803 AvailableGEPs, CurrentGeneration, DT.getRootNode(),
1804 DT.getRootNode()->begin(), DT.getRootNode()->end()));
1805
1806 assert(!CurrentGeneration && "Create a new EarlyCSE instance to rerun it.");
1807
1808 // Process the stack.
1809 while (!nodesToProcess.empty()) {
1810 // Grab the first item off the stack. Set the current generation, remove
1811 // the node from the stack, and process it.
1812 StackNode *NodeToProcess = nodesToProcess.back();
1813
1814 // Initialize class members.
1815 CurrentGeneration = NodeToProcess->currentGeneration();
1816
1817 // Check if the node needs to be processed.
1818 if (!NodeToProcess->isProcessed()) {
1819 // Process the node.
1820 Changed |= processNode(NodeToProcess->node());
1821 NodeToProcess->childGeneration(CurrentGeneration);
1822 NodeToProcess->process();
1823 } else if (NodeToProcess->childIter() != NodeToProcess->end()) {
1824 // Push the next child onto the stack.
1825 DomTreeNode *child = NodeToProcess->nextChild();
1826 nodesToProcess.push_back(new StackNode(
1827 AvailableValues, AvailableLoads, AvailableInvariants, AvailableCalls,
1828 AvailableGEPs, NodeToProcess->childGeneration(), child,
1829 child->begin(), child->end()));
1830 } else {
1831 // It has been processed, and there are no more children to process,
1832 // so delete it and pop it off the stack.
1833 delete NodeToProcess;
1834 nodesToProcess.pop_back();
1835 }
1836 } // while (!nodes...)
1837
1838 return Changed;
1839}
1840
1843 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1844 auto &TTI = AM.getResult<TargetIRAnalysis>(F);
1845 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1846 auto &AC = AM.getResult<AssumptionAnalysis>(F);
1847 auto *MSSA =
1848 UseMemorySSA ? &AM.getResult<MemorySSAAnalysis>(F).getMSSA() : nullptr;
1849
1850 EarlyCSE CSE(F.getDataLayout(), TLI, TTI, DT, AC, MSSA);
1851
1852 if (!CSE.run())
1853 return PreservedAnalyses::all();
1854
1857 if (UseMemorySSA)
1859 return PA;
1860}
1861
1863 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
1864 static_cast<PassInfoMixin<EarlyCSEPass> *>(this)->printPipeline(
1865 OS, MapClassName2PassName);
1866 OS << '<';
1867 if (UseMemorySSA)
1868 OS << "memssa";
1869 OS << '>';
1870}
1871
1872namespace {
1873
1874/// A simple and fast domtree-based CSE pass.
1875///
1876/// This pass does a simple depth-first walk over the dominator tree,
1877/// eliminating trivially redundant instructions and using instsimplify to
1878/// canonicalize things as it goes. It is intended to be fast and catch obvious
1879/// cases so that instcombine and other passes are more effective. It is
1880/// expected that a later pass of GVN will catch the interesting/hard cases.
1881template<bool UseMemorySSA>
1882class EarlyCSELegacyCommonPass : public FunctionPass {
1883public:
1884 static char ID;
1885
1886 EarlyCSELegacyCommonPass() : FunctionPass(ID) {
1887 if (UseMemorySSA)
1889 else
1891 }
1892
1893 bool runOnFunction(Function &F) override {
1894 if (skipFunction(F))
1895 return false;
1896
1897 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
1898 auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
1899 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1900 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1901 auto *MSSA =
1902 UseMemorySSA ? &getAnalysis<MemorySSAWrapperPass>().getMSSA() : nullptr;
1903
1904 EarlyCSE CSE(F.getDataLayout(), TLI, TTI, DT, AC, MSSA);
1905
1906 return CSE.run();
1907 }
1908
1909 void getAnalysisUsage(AnalysisUsage &AU) const override {
1910 AU.addRequired<AssumptionCacheTracker>();
1911 AU.addRequired<DominatorTreeWrapperPass>();
1912 AU.addRequired<TargetLibraryInfoWrapperPass>();
1913 AU.addRequired<TargetTransformInfoWrapperPass>();
1914 if (UseMemorySSA) {
1915 AU.addRequired<AAResultsWrapperPass>();
1916 AU.addRequired<MemorySSAWrapperPass>();
1917 AU.addPreserved<MemorySSAWrapperPass>();
1918 }
1919 AU.addPreserved<GlobalsAAWrapperPass>();
1920 AU.addPreserved<AAResultsWrapperPass>();
1921 AU.setPreservesCFG();
1922 }
1923};
1924
1925} // end anonymous namespace
1926
1927using EarlyCSELegacyPass = EarlyCSELegacyCommonPass</*UseMemorySSA=*/false>;
1928
1929template<>
1930char EarlyCSELegacyPass::ID = 0;
1931
1932INITIALIZE_PASS_BEGIN(EarlyCSELegacyPass, "early-cse", "Early CSE", false,
1933 false)
1938INITIALIZE_PASS_END(EarlyCSELegacyPass, "early-cse", "Early CSE", false, false)
1939
1940using EarlyCSEMemSSALegacyPass =
1941 EarlyCSELegacyCommonPass</*UseMemorySSA=*/true>;
1942
1943template<>
1944char EarlyCSEMemSSALegacyPass::ID = 0;
1945
1947 if (UseMemorySSA)
1948 return new EarlyCSEMemSSALegacyPass();
1949 else
1950 return new EarlyCSELegacyPass();
1951}
1952
1953INITIALIZE_PASS_BEGIN(EarlyCSEMemSSALegacyPass, "early-cse-memssa",
1954 "Early CSE w/ MemorySSA", false, false)
1961INITIALIZE_PASS_END(EarlyCSEMemSSALegacyPass, "early-cse-memssa",
1962 "Early CSE w/ MemorySSA", false, false)
#define Success
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static bool isLoad(int Opcode)
static bool isStore(int Opcode)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file defines the BumpPtrAllocator interface.
Atomic ordering constants.
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Optimize for code generation
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static bool isSentinel(const DWARFDebugNames::AttributeEncoding &AE)
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
This file defines DenseMapInfo traits for DenseMap.
static cl::opt< bool > EarlyCSEDebugHash("earlycse-debug-hash", cl::init(false), cl::Hidden, cl::desc("Perform extra assertion checking to verify that SimpleValue's hash " "function is well-behaved w.r.t. its isEqual predicate"))
static void combineIRFlags(Instruction &From, Value *To)
EarlyCSELegacyCommonPass< false > EarlyCSELegacyPass
early cse Early CSE w MemorySSA
static unsigned getHashValueImpl(SimpleValue Val)
Definition EarlyCSE.cpp:233
static bool isEqualImpl(SimpleValue LHS, SimpleValue RHS)
Definition EarlyCSE.cpp:354
static bool matchSelectWithOptionalNotCond(Value *V, Value *&Cond, Value *&A, Value *&B, SelectPatternFlavor &Flavor)
Match a 'select' including an optional 'not's of the condition.
Definition EarlyCSE.cpp:175
static unsigned hashCallInst(CallInst *CI)
Definition EarlyCSE.cpp:222
static cl::opt< unsigned > EarlyCSEMssaOptCap("earlycse-mssa-optimization-cap", cl::init(500), cl::Hidden, cl::desc("Enable imprecision in EarlyCSE in pathological cases, in exchange " "for faster compile. Caps the MemorySSA clobbering calls."))
This file provides the interface for a simple, fast CSE pass.
static bool runOnFunction(Function &F, bool PostInlining)
This is the interface for a simple mod/ref and alias analysis over globals.
Hexagon Common GEP
This header defines various interfaces for pass management in LLVM.
static Constant * getFalse(Type *Ty)
For a boolean type or a vector of boolean type, return false or a vector with every element false.
Value * getMatchingValue(LoadValue LV, LoadInst *LI, unsigned CurrentGeneration, BatchAAResults &BAA, function_ref< MemorySSA *()> GetMSSA)
#define F(x, y, z)
Definition MD5.cpp:55
#define I(x, y, z)
Definition MD5.cpp:58
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
static bool isInvariantLoad(const LoadInst *LI, const bool IsKernelFn)
uint64_t IntrinsicInst * II
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
const SmallVectorImpl< MachineOperand > & Cond
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
static Type * getValueType(Value *V)
Returns the type of the given value/instruction V.
This file contains some templates that are useful if you are working with the STL at all.
separate const offset from Split GEPs to a variadic base and a constant offset for better CSE
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:167
#define LLVM_DEBUG(...)
Definition Debug.h:119
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
This pass exposes codegen information to IR-level passes.
Value * RHS
Value * LHS
bool isProcessed() const
unsigned currentGeneration() const
unsigned childGeneration() const
DomTreeNode::const_iterator end() const
void process()
DomTreeNode * nextChild()
DomTreeNode::const_iterator childIter() const
DomTreeNode * node()
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
LLVM_ABI void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition Pass.cpp:270
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition BasicBlock.h:233
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
Value * getCondition() const
Represents analyses that only rely on functions' control flow.
Definition Analysis.h:73
bool onlyWritesMemory(unsigned OpNo) const
bool onlyReadsMemory(unsigned OpNo) const
bool isConvergent() const
Determine if the invoke is convergent.
This class represents a function call, abstracting a target machine's calling convention.
This is the base class for all instructions that perform data casts.
Definition InstrTypes.h:448
This class is the base class for the comparison instructions.
Definition InstrTypes.h:666
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition InstrTypes.h:678
@ ICMP_SLT
signed less than
Definition InstrTypes.h:707
@ ICMP_SLE
signed less or equal
Definition InstrTypes.h:708
@ ICMP_UGE
unsigned greater or equal
Definition InstrTypes.h:702
@ ICMP_UGT
unsigned greater than
Definition InstrTypes.h:701
@ ICMP_SGT
signed greater than
Definition InstrTypes.h:705
@ ICMP_ULT
unsigned less than
Definition InstrTypes.h:703
@ ICMP_SGE
signed greater or equal
Definition InstrTypes.h:706
@ ICMP_ULE
unsigned less or equal
Definition InstrTypes.h:704
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition InstrTypes.h:829
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition InstrTypes.h:791
Predicate getPredicate() const
Return the predicate for this instruction.
Definition InstrTypes.h:767
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
LLVM_ABI unsigned getIndexTypeSizeInBits(Type *Ty) const
The size in bits of the index used in GEP calculation for this type.
static bool shouldExecute(unsigned CounterName)
typename SmallVector< DomTreeNodeBase *, 4 >::const_iterator const_iterator
Analysis pass which computes a DominatorTree.
Definition Dominators.h:284
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
Legacy analysis pass which computes a DominatorTree.
Definition Dominators.h:322
This instruction extracts a struct member or array element value from an aggregate value.
This class represents a freeze function that returns random concrete value if an operand is either a ...
FunctionPass class - This class is used to implement most global optimizations.
Definition Pass.h:314
bool isPresplitCoroutine() const
Determine if the function is presplit coroutine.
Definition Function.h:539
Represents calls to the gc.relocate intrinsic.
This instruction inserts a struct field of array element value into an aggregate value.
LLVM_ABI bool mayThrow(bool IncludePhaseOneUnwind=false) const LLVM_READONLY
Return true if this instruction may throw an exception.
LLVM_ABI bool mayWriteToMemory() const LLVM_READONLY
Return true if this instruction may modify memory.
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
LLVM_ABI bool isIdenticalToWhenDefined(const Instruction *I, bool IntersectAttrs=false) const LLVM_READONLY
This is like isIdenticalTo, except that it ignores the SubclassOptionalData flags,...
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
LLVM_ABI bool mayReadFromMemory() const LLVM_READONLY
Return true if this instruction may read memory.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
static LLVM_ABI MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
static LLVM_ABI std::optional< MemoryLocation > getOrNone(const Instruction *Inst)
static LLVM_ABI MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
An analysis that produces MemorySSA for a function.
Definition MemorySSA.h:936
MemoryAccess * getClobberingMemoryAccess(const Instruction *I, BatchAAResults &AA)
Given a memory Mod/Ref/ModRef'ing instruction, calling this will give you the nearest dominating Memo...
Definition MemorySSA.h:1053
Legacy analysis pass which computes MemorySSA.
Definition MemorySSA.h:993
LLVM_ABI bool dominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in potentially different blocks, determine whether MemoryAccess A dominates...
LLVM_ABI MemorySSAWalker * getWalker()
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition MemorySSA.h:720
static LLVM_ABI PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
PreservedAnalyses & preserveSet()
Mark an analysis set as preserved.
Definition Analysis.h:151
PreservedAnalyses & preserve()
Mark an analysis as preserved.
Definition Analysis.h:132
ScopedHashTableScope< SimpleValue, Value *, DenseMapInfo< SimpleValue >, AllocatorTy > ScopeTy
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
void push_back(const T &Elt)
StringRef - Represent a constant reference to a string, i.e.
Definition StringRef.h:55
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
Wrapper pass for TargetTransformInfo.
LLVM_ABI bool getTgtMemIntrinsic(IntrinsicInst *Inst, MemIntrinsicInfo &Info) const
Value * getOperand(unsigned i) const
Definition User.h:232
iterator_range< value_op_iterator > operand_values()
Definition User.h:316
LLVM Value Representation.
Definition Value.h:75
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition Value.cpp:546
bool use_empty() const
Definition Value.h:346
An efficient, type-erasing, non-owning reference to a callable.
const ParentTy * getParent() const
Definition ilist_node.h:34
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
Changed
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition CallingConv.h:24
@ BasicBlock
Various leaf nodes.
Definition ISDOpcodes.h:81
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
IntrinsicID_match m_Intrinsic()
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
@ ebStrict
This corresponds to "fpexcept.strict".
Definition FPEnv.h:42
@ Assume
Do not drop type tests (default).
NodeAddr< NodeBase * > Node
Definition RDFGraph.h:381
Context & getContext() const
Definition BasicBlock.h:99
iterator end() const
Definition BasicBlock.h:89
friend class Instruction
Iterator for Instructions in a `BasicBlock.
Definition BasicBlock.h:73
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition STLExtras.h:330
@ Offset
Definition DWP.cpp:477
FunctionAddr VTableAddr Value
Definition InstrProf.h:137
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:649
LLVM_ABI void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
Definition Utils.cpp:1723
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition STLExtras.h:646
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
LLVM_ABI void initializeEarlyCSEMemSSALegacyPassPass(PassRegistry &)
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
DomTreeNodeBase< BasicBlock > DomTreeNode
Definition Dominators.h:95
LLVM_ABI bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
Definition Local.cpp:402
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
SelectPatternFlavor
Specific patterns of select instructions we can match.
@ SPF_UMIN
Signed minimum.
@ SPF_UMAX
Signed maximum.
@ SPF_SMAX
Unsigned minimum.
@ SPF_UNKNOWN
decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)
LLVM_ABI bool programUndefinedIfPoison(const Instruction *Inst)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:207
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition Allocator.h:383
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:548
LLVM_ABI void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
Definition Local.cpp:3081
@ Other
Any other memory.
Definition ModRef.h:68
TargetTransformInfo TTI
LLVM_ABI bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition MemorySSA.cpp:84
LLVM_ABI bool salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
DWARFExpression::Operation Op
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:565
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition Hashing.h:591
LLVM_ABI FunctionPass * createEarlyCSEPass(bool UseMemorySSA=false)
LLVM_ABI void initializeEarlyCSELegacyPassPass(PassRegistry &)
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition Hashing.h:465
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition BitVector.h:853
unsigned Generation
static unsigned getHashValue(CallValue Val)
static CallValue getTombstoneKey()
Definition EarlyCSE.cpp:519
static bool isEqual(CallValue LHS, CallValue RHS)
static CallValue getEmptyKey()
Definition EarlyCSE.cpp:515
static bool isEqual(const GEPValue &LHS, const GEPValue &RHS)
static unsigned getHashValue(const GEPValue &Val)
static GEPValue getTombstoneKey()
Definition EarlyCSE.cpp:590
static GEPValue getEmptyKey()
Definition EarlyCSE.cpp:586
static SimpleValue getEmptyKey()
Definition EarlyCSE.cpp:160
static unsigned getHashValue(SimpleValue Val)
static SimpleValue getTombstoneKey()
Definition EarlyCSE.cpp:164
static bool isEqual(SimpleValue LHS, SimpleValue RHS)
An information struct used to provide DenseMap with the various necessary components for a given valu...
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
LLVM_ABI void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition PassManager.h:70
const DataLayout & DL