LLVM 19.0.0git
GVN.cpp
Go to the documentation of this file.
1//===- GVN.cpp - Eliminate redundant values and loads ---------------------===//
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 global value numbering to eliminate fully redundant
10// instructions. It also performs simple dead load elimination.
11//
12// Note that this pass does the value numbering itself; it does not use the
13// ValueNumbering analysis passes.
14//
15//===----------------------------------------------------------------------===//
16
18#include "llvm/ADT/DenseMap.h"
20#include "llvm/ADT/Hashing.h"
21#include "llvm/ADT/MapVector.h"
23#include "llvm/ADT/STLExtras.h"
24#include "llvm/ADT/SetVector.h"
27#include "llvm/ADT/Statistic.h"
31#include "llvm/Analysis/CFG.h"
45#include "llvm/IR/Attributes.h"
46#include "llvm/IR/BasicBlock.h"
47#include "llvm/IR/Constant.h"
48#include "llvm/IR/Constants.h"
49#include "llvm/IR/DebugLoc.h"
50#include "llvm/IR/Dominators.h"
51#include "llvm/IR/Function.h"
52#include "llvm/IR/InstrTypes.h"
53#include "llvm/IR/Instruction.h"
56#include "llvm/IR/LLVMContext.h"
57#include "llvm/IR/Metadata.h"
58#include "llvm/IR/Module.h"
59#include "llvm/IR/PassManager.h"
61#include "llvm/IR/Type.h"
62#include "llvm/IR/Use.h"
63#include "llvm/IR/Value.h"
65#include "llvm/Pass.h"
69#include "llvm/Support/Debug.h"
76#include <algorithm>
77#include <cassert>
78#include <cstdint>
79#include <optional>
80#include <utility>
81
82using namespace llvm;
83using namespace llvm::gvn;
84using namespace llvm::VNCoercion;
85using namespace PatternMatch;
86
87#define DEBUG_TYPE "gvn"
88
89STATISTIC(NumGVNInstr, "Number of instructions deleted");
90STATISTIC(NumGVNLoad, "Number of loads deleted");
91STATISTIC(NumGVNPRE, "Number of instructions PRE'd");
92STATISTIC(NumGVNBlocks, "Number of blocks merged");
93STATISTIC(NumGVNSimpl, "Number of instructions simplified");
94STATISTIC(NumGVNEqProp, "Number of equalities propagated");
95STATISTIC(NumPRELoad, "Number of loads PRE'd");
96STATISTIC(NumPRELoopLoad, "Number of loop loads PRE'd");
97STATISTIC(NumPRELoadMoved2CEPred,
98 "Number of loads moved to predecessor of a critical edge in PRE");
99
100STATISTIC(IsValueFullyAvailableInBlockNumSpeculationsMax,
101 "Number of blocks speculated as available in "
102 "IsValueFullyAvailableInBlock(), max");
103STATISTIC(MaxBBSpeculationCutoffReachedTimes,
104 "Number of times we we reached gvn-max-block-speculations cut-off "
105 "preventing further exploration");
106
107static cl::opt<bool> GVNEnablePRE("enable-pre", cl::init(true), cl::Hidden);
108static cl::opt<bool> GVNEnableLoadPRE("enable-load-pre", cl::init(true));
109static cl::opt<bool> GVNEnableLoadInLoopPRE("enable-load-in-loop-pre",
110 cl::init(true));
111static cl::opt<bool>
112GVNEnableSplitBackedgeInLoadPRE("enable-split-backedge-in-load-pre",
113 cl::init(false));
114static cl::opt<bool> GVNEnableMemDep("enable-gvn-memdep", cl::init(true));
115
117 "gvn-max-num-deps", cl::Hidden, cl::init(100),
118 cl::desc("Max number of dependences to attempt Load PRE (default = 100)"));
119
120// This is based on IsValueFullyAvailableInBlockNumSpeculationsMax stat.
122 "gvn-max-block-speculations", cl::Hidden, cl::init(600),
123 cl::desc("Max number of blocks we're willing to speculate on (and recurse "
124 "into) when deducing if a value is fully available or not in GVN "
125 "(default = 600)"));
126
128 "gvn-max-num-visited-insts", cl::Hidden, cl::init(100),
129 cl::desc("Max number of visited instructions when trying to find "
130 "dominating value of select dependency (default = 100)"));
131
133 "gvn-max-num-insns", cl::Hidden, cl::init(100),
134 cl::desc("Max number of instructions to scan in each basic block in GVN "
135 "(default = 100)"));
136
139 bool commutative = false;
140 // The type is not necessarily the result type of the expression, it may be
141 // any additional type needed to disambiguate the expression.
142 Type *type = nullptr;
144
145 Expression(uint32_t o = ~2U) : opcode(o) {}
146
147 bool operator==(const Expression &other) const {
148 if (opcode != other.opcode)
149 return false;
150 if (opcode == ~0U || opcode == ~1U)
151 return true;
152 if (type != other.type)
153 return false;
154 if (varargs != other.varargs)
155 return false;
156 return true;
157 }
158
160 return hash_combine(
161 Value.opcode, Value.type,
162 hash_combine_range(Value.varargs.begin(), Value.varargs.end()));
163 }
164};
165
166namespace llvm {
167
168template <> struct DenseMapInfo<GVNPass::Expression> {
169 static inline GVNPass::Expression getEmptyKey() { return ~0U; }
170 static inline GVNPass::Expression getTombstoneKey() { return ~1U; }
171
172 static unsigned getHashValue(const GVNPass::Expression &e) {
173 using llvm::hash_value;
174
175 return static_cast<unsigned>(hash_value(e));
176 }
177
178 static bool isEqual(const GVNPass::Expression &LHS,
179 const GVNPass::Expression &RHS) {
180 return LHS == RHS;
181 }
182};
183
184} // end namespace llvm
185
186/// Represents a particular available value that we know how to materialize.
187/// Materialization of an AvailableValue never fails. An AvailableValue is
188/// implicitly associated with a rematerialization point which is the
189/// location of the instruction from which it was formed.
191 enum class ValType {
192 SimpleVal, // A simple offsetted value that is accessed.
193 LoadVal, // A value produced by a load.
194 MemIntrin, // A memory intrinsic which is loaded from.
195 UndefVal, // A UndefValue representing a value from dead block (which
196 // is not yet physically removed from the CFG).
197 SelectVal, // A pointer select which is loaded from and for which the load
198 // can be replace by a value select.
199 };
200
201 /// Val - The value that is live out of the block.
203 /// Kind of the live-out value.
205
206 /// Offset - The byte offset in Val that is interesting for the load query.
207 unsigned Offset = 0;
208 /// V1, V2 - The dominating non-clobbered values of SelectVal.
209 Value *V1 = nullptr, *V2 = nullptr;
210
211 static AvailableValue get(Value *V, unsigned Offset = 0) {
212 AvailableValue Res;
213 Res.Val = V;
215 Res.Offset = Offset;
216 return Res;
217 }
218
219 static AvailableValue getMI(MemIntrinsic *MI, unsigned Offset = 0) {
220 AvailableValue Res;
221 Res.Val = MI;
223 Res.Offset = Offset;
224 return Res;
225 }
226
227 static AvailableValue getLoad(LoadInst *Load, unsigned Offset = 0) {
228 AvailableValue Res;
229 Res.Val = Load;
231 Res.Offset = Offset;
232 return Res;
233 }
234
236 AvailableValue Res;
237 Res.Val = nullptr;
239 Res.Offset = 0;
240 return Res;
241 }
242
244 AvailableValue Res;
245 Res.Val = Sel;
247 Res.Offset = 0;
248 Res.V1 = V1;
249 Res.V2 = V2;
250 return Res;
251 }
252
253 bool isSimpleValue() const { return Kind == ValType::SimpleVal; }
254 bool isCoercedLoadValue() const { return Kind == ValType::LoadVal; }
255 bool isMemIntrinValue() const { return Kind == ValType::MemIntrin; }
256 bool isUndefValue() const { return Kind == ValType::UndefVal; }
257 bool isSelectValue() const { return Kind == ValType::SelectVal; }
258
260 assert(isSimpleValue() && "Wrong accessor");
261 return Val;
262 }
263
265 assert(isCoercedLoadValue() && "Wrong accessor");
266 return cast<LoadInst>(Val);
267 }
268
270 assert(isMemIntrinValue() && "Wrong accessor");
271 return cast<MemIntrinsic>(Val);
272 }
273
275 assert(isSelectValue() && "Wrong accessor");
276 return cast<SelectInst>(Val);
277 }
278
279 /// Emit code at the specified insertion point to adjust the value defined
280 /// here to the specified type. This handles various coercion cases.
282 GVNPass &gvn) const;
283};
284
285/// Represents an AvailableValue which can be rematerialized at the end of
286/// the associated BasicBlock.
288 /// BB - The basic block in question.
289 BasicBlock *BB = nullptr;
290
291 /// AV - The actual available value
293
296 Res.BB = BB;
297 Res.AV = std::move(AV);
298 return Res;
299 }
300
302 unsigned Offset = 0) {
303 return get(BB, AvailableValue::get(V, Offset));
304 }
305
308 }
309
311 Value *V1, Value *V2) {
312 return get(BB, AvailableValue::getSelect(Sel, V1, V2));
313 }
314
315 /// Emit code at the end of this block to adjust the value defined here to
316 /// the specified type. This handles various coercion cases.
318 return AV.MaterializeAdjustedValue(Load, BB->getTerminator(), gvn);
319 }
320};
321
322//===----------------------------------------------------------------------===//
323// ValueTable Internal Functions
324//===----------------------------------------------------------------------===//
325
326GVNPass::Expression GVNPass::ValueTable::createExpr(Instruction *I) {
327 Expression e;
328 e.type = I->getType();
329 e.opcode = I->getOpcode();
330 if (const GCRelocateInst *GCR = dyn_cast<GCRelocateInst>(I)) {
331 // gc.relocate is 'special' call: its second and third operands are
332 // not real values, but indices into statepoint's argument list.
333 // Use the refered to values for purposes of identity.
334 e.varargs.push_back(lookupOrAdd(GCR->getOperand(0)));
335 e.varargs.push_back(lookupOrAdd(GCR->getBasePtr()));
336 e.varargs.push_back(lookupOrAdd(GCR->getDerivedPtr()));
337 } else {
338 for (Use &Op : I->operands())
339 e.varargs.push_back(lookupOrAdd(Op));
340 }
341 if (I->isCommutative()) {
342 // Ensure that commutative instructions that only differ by a permutation
343 // of their operands get the same value number by sorting the operand value
344 // numbers. Since commutative operands are the 1st two operands it is more
345 // efficient to sort by hand rather than using, say, std::sort.
346 assert(I->getNumOperands() >= 2 && "Unsupported commutative instruction!");
347 if (e.varargs[0] > e.varargs[1])
348 std::swap(e.varargs[0], e.varargs[1]);
349 e.commutative = true;
350 }
351
352 if (auto *C = dyn_cast<CmpInst>(I)) {
353 // Sort the operand value numbers so x<y and y>x get the same value number.
354 CmpInst::Predicate Predicate = C->getPredicate();
355 if (e.varargs[0] > e.varargs[1]) {
356 std::swap(e.varargs[0], e.varargs[1]);
358 }
359 e.opcode = (C->getOpcode() << 8) | Predicate;
360 e.commutative = true;
361 } else if (auto *E = dyn_cast<InsertValueInst>(I)) {
362 e.varargs.append(E->idx_begin(), E->idx_end());
363 } else if (auto *SVI = dyn_cast<ShuffleVectorInst>(I)) {
364 ArrayRef<int> ShuffleMask = SVI->getShuffleMask();
365 e.varargs.append(ShuffleMask.begin(), ShuffleMask.end());
366 }
367
368 return e;
369}
370
371GVNPass::Expression GVNPass::ValueTable::createCmpExpr(
372 unsigned Opcode, CmpInst::Predicate Predicate, Value *LHS, Value *RHS) {
373 assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) &&
374 "Not a comparison!");
377 e.varargs.push_back(lookupOrAdd(LHS));
378 e.varargs.push_back(lookupOrAdd(RHS));
379
380 // Sort the operand value numbers so x<y and y>x get the same value number.
381 if (e.varargs[0] > e.varargs[1]) {
382 std::swap(e.varargs[0], e.varargs[1]);
384 }
385 e.opcode = (Opcode << 8) | Predicate;
386 e.commutative = true;
387 return e;
388}
389
391GVNPass::ValueTable::createExtractvalueExpr(ExtractValueInst *EI) {
392 assert(EI && "Not an ExtractValueInst?");
394 e.type = EI->getType();
395 e.opcode = 0;
396
397 WithOverflowInst *WO = dyn_cast<WithOverflowInst>(EI->getAggregateOperand());
398 if (WO != nullptr && EI->getNumIndices() == 1 && *EI->idx_begin() == 0) {
399 // EI is an extract from one of our with.overflow intrinsics. Synthesize
400 // a semantically equivalent expression instead of an extract value
401 // expression.
402 e.opcode = WO->getBinaryOp();
403 e.varargs.push_back(lookupOrAdd(WO->getLHS()));
404 e.varargs.push_back(lookupOrAdd(WO->getRHS()));
405 return e;
406 }
407
408 // Not a recognised intrinsic. Fall back to producing an extract value
409 // expression.
410 e.opcode = EI->getOpcode();
411 for (Use &Op : EI->operands())
412 e.varargs.push_back(lookupOrAdd(Op));
413
414 append_range(e.varargs, EI->indices());
415
416 return e;
417}
418
419GVNPass::Expression GVNPass::ValueTable::createGEPExpr(GetElementPtrInst *GEP) {
420 Expression E;
421 Type *PtrTy = GEP->getType()->getScalarType();
422 const DataLayout &DL = GEP->getModule()->getDataLayout();
423 unsigned BitWidth = DL.getIndexTypeSizeInBits(PtrTy);
424 MapVector<Value *, APInt> VariableOffsets;
425 APInt ConstantOffset(BitWidth, 0);
426 if (GEP->collectOffset(DL, BitWidth, VariableOffsets, ConstantOffset)) {
427 // Convert into offset representation, to recognize equivalent address
428 // calculations that use different type encoding.
429 LLVMContext &Context = GEP->getContext();
430 E.opcode = GEP->getOpcode();
431 E.type = nullptr;
432 E.varargs.push_back(lookupOrAdd(GEP->getPointerOperand()));
433 for (const auto &Pair : VariableOffsets) {
434 E.varargs.push_back(lookupOrAdd(Pair.first));
435 E.varargs.push_back(lookupOrAdd(ConstantInt::get(Context, Pair.second)));
436 }
437 if (!ConstantOffset.isZero())
438 E.varargs.push_back(
439 lookupOrAdd(ConstantInt::get(Context, ConstantOffset)));
440 } else {
441 // If converting to offset representation fails (for scalable vectors),
442 // fall back to type-based implementation:
443 E.opcode = GEP->getOpcode();
444 E.type = GEP->getSourceElementType();
445 for (Use &Op : GEP->operands())
446 E.varargs.push_back(lookupOrAdd(Op));
447 }
448 return E;
449}
450
451//===----------------------------------------------------------------------===//
452// ValueTable External Functions
453//===----------------------------------------------------------------------===//
454
455GVNPass::ValueTable::ValueTable() = default;
456GVNPass::ValueTable::ValueTable(const ValueTable &) = default;
457GVNPass::ValueTable::ValueTable(ValueTable &&) = default;
458GVNPass::ValueTable::~ValueTable() = default;
461
462/// add - Insert a value into the table with a specified value number.
463void GVNPass::ValueTable::add(Value *V, uint32_t num) {
464 valueNumbering.insert(std::make_pair(V, num));
465 if (PHINode *PN = dyn_cast<PHINode>(V))
466 NumberingPhi[num] = PN;
467}
468
469uint32_t GVNPass::ValueTable::lookupOrAddCall(CallInst *C) {
470 // FIXME: Currently the calls which may access the thread id may
471 // be considered as not accessing the memory. But this is
472 // problematic for coroutines, since coroutines may resume in a
473 // different thread. So we disable the optimization here for the
474 // correctness. However, it may block many other correct
475 // optimizations. Revert this one when we detect the memory
476 // accessing kind more precisely.
477 if (C->getFunction()->isPresplitCoroutine()) {
478 valueNumbering[C] = nextValueNumber;
479 return nextValueNumber++;
480 }
481
482 // Do not combine convergent calls since they implicitly depend on the set of
483 // threads that is currently executing, and they might be in different basic
484 // blocks.
485 if (C->isConvergent()) {
486 valueNumbering[C] = nextValueNumber;
487 return nextValueNumber++;
488 }
489
490 if (AA->doesNotAccessMemory(C)) {
491 Expression exp = createExpr(C);
492 uint32_t e = assignExpNewValueNum(exp).first;
493 valueNumbering[C] = e;
494 return e;
495 }
496
497 if (MD && AA->onlyReadsMemory(C)) {
498 Expression exp = createExpr(C);
499 auto ValNum = assignExpNewValueNum(exp);
500 if (ValNum.second) {
501 valueNumbering[C] = ValNum.first;
502 return ValNum.first;
503 }
504
505 MemDepResult local_dep = MD->getDependency(C);
506
507 if (!local_dep.isDef() && !local_dep.isNonLocal()) {
508 valueNumbering[C] = nextValueNumber;
509 return nextValueNumber++;
510 }
511
512 if (local_dep.isDef()) {
513 // For masked load/store intrinsics, the local_dep may actually be
514 // a normal load or store instruction.
515 CallInst *local_cdep = dyn_cast<CallInst>(local_dep.getInst());
516
517 if (!local_cdep || local_cdep->arg_size() != C->arg_size()) {
518 valueNumbering[C] = nextValueNumber;
519 return nextValueNumber++;
520 }
521
522 for (unsigned i = 0, e = C->arg_size(); i < e; ++i) {
523 uint32_t c_vn = lookupOrAdd(C->getArgOperand(i));
524 uint32_t cd_vn = lookupOrAdd(local_cdep->getArgOperand(i));
525 if (c_vn != cd_vn) {
526 valueNumbering[C] = nextValueNumber;
527 return nextValueNumber++;
528 }
529 }
530
531 uint32_t v = lookupOrAdd(local_cdep);
532 valueNumbering[C] = v;
533 return v;
534 }
535
536 // Non-local case.
539 // FIXME: Move the checking logic to MemDep!
540 CallInst* cdep = nullptr;
541
542 // Check to see if we have a single dominating call instruction that is
543 // identical to C.
544 for (const NonLocalDepEntry &I : deps) {
545 if (I.getResult().isNonLocal())
546 continue;
547
548 // We don't handle non-definitions. If we already have a call, reject
549 // instruction dependencies.
550 if (!I.getResult().isDef() || cdep != nullptr) {
551 cdep = nullptr;
552 break;
553 }
554
555 CallInst *NonLocalDepCall = dyn_cast<CallInst>(I.getResult().getInst());
556 // FIXME: All duplicated with non-local case.
557 if (NonLocalDepCall && DT->properlyDominates(I.getBB(), C->getParent())) {
558 cdep = NonLocalDepCall;
559 continue;
560 }
561
562 cdep = nullptr;
563 break;
564 }
565
566 if (!cdep) {
567 valueNumbering[C] = nextValueNumber;
568 return nextValueNumber++;
569 }
570
571 if (cdep->arg_size() != C->arg_size()) {
572 valueNumbering[C] = nextValueNumber;
573 return nextValueNumber++;
574 }
575 for (unsigned i = 0, e = C->arg_size(); i < e; ++i) {
576 uint32_t c_vn = lookupOrAdd(C->getArgOperand(i));
577 uint32_t cd_vn = lookupOrAdd(cdep->getArgOperand(i));
578 if (c_vn != cd_vn) {
579 valueNumbering[C] = nextValueNumber;
580 return nextValueNumber++;
581 }
582 }
583
584 uint32_t v = lookupOrAdd(cdep);
585 valueNumbering[C] = v;
586 return v;
587 }
588
589 valueNumbering[C] = nextValueNumber;
590 return nextValueNumber++;
591}
592
593/// Returns true if a value number exists for the specified value.
594bool GVNPass::ValueTable::exists(Value *V) const {
595 return valueNumbering.contains(V);
596}
597
598/// lookup_or_add - Returns the value number for the specified value, assigning
599/// it a new number if it did not have one before.
600uint32_t GVNPass::ValueTable::lookupOrAdd(Value *V) {
601 DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
602 if (VI != valueNumbering.end())
603 return VI->second;
604
605 auto *I = dyn_cast<Instruction>(V);
606 if (!I) {
607 valueNumbering[V] = nextValueNumber;
608 return nextValueNumber++;
609 }
610
611 Expression exp;
612 switch (I->getOpcode()) {
613 case Instruction::Call:
614 return lookupOrAddCall(cast<CallInst>(I));
615 case Instruction::FNeg:
616 case Instruction::Add:
617 case Instruction::FAdd:
618 case Instruction::Sub:
619 case Instruction::FSub:
620 case Instruction::Mul:
621 case Instruction::FMul:
622 case Instruction::UDiv:
623 case Instruction::SDiv:
624 case Instruction::FDiv:
625 case Instruction::URem:
626 case Instruction::SRem:
627 case Instruction::FRem:
628 case Instruction::Shl:
629 case Instruction::LShr:
630 case Instruction::AShr:
631 case Instruction::And:
632 case Instruction::Or:
633 case Instruction::Xor:
634 case Instruction::ICmp:
635 case Instruction::FCmp:
636 case Instruction::Trunc:
637 case Instruction::ZExt:
638 case Instruction::SExt:
639 case Instruction::FPToUI:
640 case Instruction::FPToSI:
641 case Instruction::UIToFP:
642 case Instruction::SIToFP:
643 case Instruction::FPTrunc:
644 case Instruction::FPExt:
645 case Instruction::PtrToInt:
646 case Instruction::IntToPtr:
647 case Instruction::AddrSpaceCast:
648 case Instruction::BitCast:
649 case Instruction::Select:
650 case Instruction::Freeze:
651 case Instruction::ExtractElement:
652 case Instruction::InsertElement:
653 case Instruction::ShuffleVector:
654 case Instruction::InsertValue:
655 exp = createExpr(I);
656 break;
657 case Instruction::GetElementPtr:
658 exp = createGEPExpr(cast<GetElementPtrInst>(I));
659 break;
660 case Instruction::ExtractValue:
661 exp = createExtractvalueExpr(cast<ExtractValueInst>(I));
662 break;
663 case Instruction::PHI:
664 valueNumbering[V] = nextValueNumber;
665 NumberingPhi[nextValueNumber] = cast<PHINode>(V);
666 return nextValueNumber++;
667 default:
668 valueNumbering[V] = nextValueNumber;
669 return nextValueNumber++;
670 }
671
672 uint32_t e = assignExpNewValueNum(exp).first;
673 valueNumbering[V] = e;
674 return e;
675}
676
677/// Returns the value number of the specified value. Fails if
678/// the value has not yet been numbered.
679uint32_t GVNPass::ValueTable::lookup(Value *V, bool Verify) const {
680 DenseMap<Value*, uint32_t>::const_iterator VI = valueNumbering.find(V);
681 if (Verify) {
682 assert(VI != valueNumbering.end() && "Value not numbered?");
683 return VI->second;
684 }
685 return (VI != valueNumbering.end()) ? VI->second : 0;
686}
687
688/// Returns the value number of the given comparison,
689/// assigning it a new number if it did not have one before. Useful when
690/// we deduced the result of a comparison, but don't immediately have an
691/// instruction realizing that comparison to hand.
692uint32_t GVNPass::ValueTable::lookupOrAddCmp(unsigned Opcode,
693 CmpInst::Predicate Predicate,
694 Value *LHS, Value *RHS) {
695 Expression exp = createCmpExpr(Opcode, Predicate, LHS, RHS);
696 return assignExpNewValueNum(exp).first;
697}
698
699/// Remove all entries from the ValueTable.
701 valueNumbering.clear();
702 expressionNumbering.clear();
703 NumberingPhi.clear();
704 PhiTranslateTable.clear();
705 nextValueNumber = 1;
706 Expressions.clear();
707 ExprIdx.clear();
708 nextExprNumber = 0;
709}
710
711/// Remove a value from the value numbering.
713 uint32_t Num = valueNumbering.lookup(V);
714 valueNumbering.erase(V);
715 // If V is PHINode, V <--> value number is an one-to-one mapping.
716 if (isa<PHINode>(V))
717 NumberingPhi.erase(Num);
718}
719
720/// verifyRemoved - Verify that the value is removed from all internal data
721/// structures.
722void GVNPass::ValueTable::verifyRemoved(const Value *V) const {
723 assert(!valueNumbering.contains(V) &&
724 "Inst still occurs in value numbering map!");
725}
726
727//===----------------------------------------------------------------------===//
728// GVN Pass
729//===----------------------------------------------------------------------===//
730
732 return Options.AllowPRE.value_or(GVNEnablePRE);
733}
734
736 return Options.AllowLoadPRE.value_or(GVNEnableLoadPRE);
737}
738
740 return Options.AllowLoadInLoopPRE.value_or(GVNEnableLoadInLoopPRE);
741}
742
744 return Options.AllowLoadPRESplitBackedge.value_or(
746}
747
749 return Options.AllowMemDep.value_or(GVNEnableMemDep);
750}
751
753 // FIXME: The order of evaluation of these 'getResult' calls is very
754 // significant! Re-ordering these variables will cause GVN when run alone to
755 // be less effective! We should fix memdep and basic-aa to not exhibit this
756 // behavior, but until then don't change the order here.
757 auto &AC = AM.getResult<AssumptionAnalysis>(F);
758 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
759 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
760 auto &AA = AM.getResult<AAManager>(F);
761 auto *MemDep =
763 auto &LI = AM.getResult<LoopAnalysis>(F);
764 auto *MSSA = AM.getCachedResult<MemorySSAAnalysis>(F);
766 bool Changed = runImpl(F, AC, DT, TLI, AA, MemDep, LI, &ORE,
767 MSSA ? &MSSA->getMSSA() : nullptr);
768 if (!Changed)
769 return PreservedAnalyses::all();
773 if (MSSA)
776 return PA;
777}
778
780 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
781 static_cast<PassInfoMixin<GVNPass> *>(this)->printPipeline(
782 OS, MapClassName2PassName);
783
784 OS << '<';
785 if (Options.AllowPRE != std::nullopt)
786 OS << (*Options.AllowPRE ? "" : "no-") << "pre;";
787 if (Options.AllowLoadPRE != std::nullopt)
788 OS << (*Options.AllowLoadPRE ? "" : "no-") << "load-pre;";
789 if (Options.AllowLoadPRESplitBackedge != std::nullopt)
790 OS << (*Options.AllowLoadPRESplitBackedge ? "" : "no-")
791 << "split-backedge-load-pre;";
792 if (Options.AllowMemDep != std::nullopt)
793 OS << (*Options.AllowMemDep ? "" : "no-") << "memdep";
794 OS << '>';
795}
796
797#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
798LLVM_DUMP_METHOD void GVNPass::dump(DenseMap<uint32_t, Value *> &d) const {
799 errs() << "{\n";
800 for (auto &I : d) {
801 errs() << I.first << "\n";
802 I.second->dump();
803 }
804 errs() << "}\n";
805}
806#endif
807
808enum class AvailabilityState : char {
809 /// We know the block *is not* fully available. This is a fixpoint.
810 Unavailable = 0,
811 /// We know the block *is* fully available. This is a fixpoint.
812 Available = 1,
813 /// We do not know whether the block is fully available or not,
814 /// but we are currently speculating that it will be.
815 /// If it would have turned out that the block was, in fact, not fully
816 /// available, this would have been cleaned up into an Unavailable.
818};
819
820/// Return true if we can prove that the value
821/// we're analyzing is fully available in the specified block. As we go, keep
822/// track of which blocks we know are fully alive in FullyAvailableBlocks. This
823/// map is actually a tri-state map with the following values:
824/// 0) we know the block *is not* fully available.
825/// 1) we know the block *is* fully available.
826/// 2) we do not know whether the block is fully available or not, but we are
827/// currently speculating that it will be.
829 BasicBlock *BB,
830 DenseMap<BasicBlock *, AvailabilityState> &FullyAvailableBlocks) {
832 std::optional<BasicBlock *> UnavailableBB;
833
834 // The number of times we didn't find an entry for a block in a map and
835 // optimistically inserted an entry marking block as speculatively available.
836 unsigned NumNewNewSpeculativelyAvailableBBs = 0;
837
838#ifndef NDEBUG
839 SmallSet<BasicBlock *, 32> NewSpeculativelyAvailableBBs;
841#endif
842
843 Worklist.emplace_back(BB);
844 while (!Worklist.empty()) {
845 BasicBlock *CurrBB = Worklist.pop_back_val(); // LoadFO - depth-first!
846 // Optimistically assume that the block is Speculatively Available and check
847 // to see if we already know about this block in one lookup.
848 std::pair<DenseMap<BasicBlock *, AvailabilityState>::iterator, bool> IV =
849 FullyAvailableBlocks.try_emplace(
850 CurrBB, AvailabilityState::SpeculativelyAvailable);
851 AvailabilityState &State = IV.first->second;
852
853 // Did the entry already exist for this block?
854 if (!IV.second) {
855 if (State == AvailabilityState::Unavailable) {
856 UnavailableBB = CurrBB;
857 break; // Backpropagate unavailability info.
858 }
859
860#ifndef NDEBUG
861 AvailableBBs.emplace_back(CurrBB);
862#endif
863 continue; // Don't recurse further, but continue processing worklist.
864 }
865
866 // No entry found for block.
867 ++NumNewNewSpeculativelyAvailableBBs;
868 bool OutOfBudget = NumNewNewSpeculativelyAvailableBBs > MaxBBSpeculations;
869
870 // If we have exhausted our budget, mark this block as unavailable.
871 // Also, if this block has no predecessors, the value isn't live-in here.
872 if (OutOfBudget || pred_empty(CurrBB)) {
873 MaxBBSpeculationCutoffReachedTimes += (int)OutOfBudget;
874 State = AvailabilityState::Unavailable;
875 UnavailableBB = CurrBB;
876 break; // Backpropagate unavailability info.
877 }
878
879 // Tentatively consider this block as speculatively available.
880#ifndef NDEBUG
881 NewSpeculativelyAvailableBBs.insert(CurrBB);
882#endif
883 // And further recurse into block's predecessors, in depth-first order!
884 Worklist.append(pred_begin(CurrBB), pred_end(CurrBB));
885 }
886
887#if LLVM_ENABLE_STATS
888 IsValueFullyAvailableInBlockNumSpeculationsMax.updateMax(
889 NumNewNewSpeculativelyAvailableBBs);
890#endif
891
892 // If the block isn't marked as fixpoint yet
893 // (the Unavailable and Available states are fixpoints)
894 auto MarkAsFixpointAndEnqueueSuccessors =
895 [&](BasicBlock *BB, AvailabilityState FixpointState) {
896 auto It = FullyAvailableBlocks.find(BB);
897 if (It == FullyAvailableBlocks.end())
898 return; // Never queried this block, leave as-is.
899 switch (AvailabilityState &State = It->second) {
900 case AvailabilityState::Unavailable:
901 case AvailabilityState::Available:
902 return; // Don't backpropagate further, continue processing worklist.
903 case AvailabilityState::SpeculativelyAvailable: // Fix it!
904 State = FixpointState;
905#ifndef NDEBUG
906 assert(NewSpeculativelyAvailableBBs.erase(BB) &&
907 "Found a speculatively available successor leftover?");
908#endif
909 // Queue successors for further processing.
910 Worklist.append(succ_begin(BB), succ_end(BB));
911 return;
912 }
913 };
914
915 if (UnavailableBB) {
916 // Okay, we have encountered an unavailable block.
917 // Mark speculatively available blocks reachable from UnavailableBB as
918 // unavailable as well. Paths are terminated when they reach blocks not in
919 // FullyAvailableBlocks or they are not marked as speculatively available.
920 Worklist.clear();
921 Worklist.append(succ_begin(*UnavailableBB), succ_end(*UnavailableBB));
922 while (!Worklist.empty())
923 MarkAsFixpointAndEnqueueSuccessors(Worklist.pop_back_val(),
924 AvailabilityState::Unavailable);
925 }
926
927#ifndef NDEBUG
928 Worklist.clear();
929 for (BasicBlock *AvailableBB : AvailableBBs)
930 Worklist.append(succ_begin(AvailableBB), succ_end(AvailableBB));
931 while (!Worklist.empty())
932 MarkAsFixpointAndEnqueueSuccessors(Worklist.pop_back_val(),
933 AvailabilityState::Available);
934
935 assert(NewSpeculativelyAvailableBBs.empty() &&
936 "Must have fixed all the new speculatively available blocks.");
937#endif
938
939 return !UnavailableBB;
940}
941
942/// If the specified OldValue exists in ValuesPerBlock, replace its value with
943/// NewValue.
945 SmallVectorImpl<AvailableValueInBlock> &ValuesPerBlock, Value *OldValue,
946 Value *NewValue) {
947 for (AvailableValueInBlock &V : ValuesPerBlock) {
948 if (V.AV.Val == OldValue)
949 V.AV.Val = NewValue;
950 if (V.AV.isSelectValue()) {
951 if (V.AV.V1 == OldValue)
952 V.AV.V1 = NewValue;
953 if (V.AV.V2 == OldValue)
954 V.AV.V2 = NewValue;
955 }
956 }
957}
958
959/// Given a set of loads specified by ValuesPerBlock,
960/// construct SSA form, allowing us to eliminate Load. This returns the value
961/// that should be used at Load's definition site.
962static Value *
965 GVNPass &gvn) {
966 // Check for the fully redundant, dominating load case. In this case, we can
967 // just use the dominating value directly.
968 if (ValuesPerBlock.size() == 1 &&
969 gvn.getDominatorTree().properlyDominates(ValuesPerBlock[0].BB,
970 Load->getParent())) {
971 assert(!ValuesPerBlock[0].AV.isUndefValue() &&
972 "Dead BB dominate this block");
973 return ValuesPerBlock[0].MaterializeAdjustedValue(Load, gvn);
974 }
975
976 // Otherwise, we have to construct SSA form.
978 SSAUpdater SSAUpdate(&NewPHIs);
979 SSAUpdate.Initialize(Load->getType(), Load->getName());
980
981 for (const AvailableValueInBlock &AV : ValuesPerBlock) {
982 BasicBlock *BB = AV.BB;
983
984 if (AV.AV.isUndefValue())
985 continue;
986
987 if (SSAUpdate.HasValueForBlock(BB))
988 continue;
989
990 // If the value is the load that we will be eliminating, and the block it's
991 // available in is the block that the load is in, then don't add it as
992 // SSAUpdater will resolve the value to the relevant phi which may let it
993 // avoid phi construction entirely if there's actually only one value.
994 if (BB == Load->getParent() &&
995 ((AV.AV.isSimpleValue() && AV.AV.getSimpleValue() == Load) ||
996 (AV.AV.isCoercedLoadValue() && AV.AV.getCoercedLoadValue() == Load)))
997 continue;
998
999 SSAUpdate.AddAvailableValue(BB, AV.MaterializeAdjustedValue(Load, gvn));
1000 }
1001
1002 // Perform PHI construction.
1003 return SSAUpdate.GetValueInMiddleOfBlock(Load->getParent());
1004}
1005
1007 Instruction *InsertPt,
1008 GVNPass &gvn) const {
1009 Value *Res;
1010 Type *LoadTy = Load->getType();
1011 const DataLayout &DL = Load->getModule()->getDataLayout();
1012 if (isSimpleValue()) {
1013 Res = getSimpleValue();
1014 if (Res->getType() != LoadTy) {
1015 Res = getValueForLoad(Res, Offset, LoadTy, InsertPt, DL);
1016
1017 LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL VAL:\nOffset: " << Offset
1018 << " " << *getSimpleValue() << '\n'
1019 << *Res << '\n'
1020 << "\n\n\n");
1021 }
1022 } else if (isCoercedLoadValue()) {
1023 LoadInst *CoercedLoad = getCoercedLoadValue();
1024 if (CoercedLoad->getType() == LoadTy && Offset == 0) {
1025 Res = CoercedLoad;
1026 combineMetadataForCSE(CoercedLoad, Load, false);
1027 } else {
1028 Res = getValueForLoad(CoercedLoad, Offset, LoadTy, InsertPt, DL);
1029 // We are adding a new user for this load, for which the original
1030 // metadata may not hold. Additionally, the new load may have a different
1031 // size and type, so their metadata cannot be combined in any
1032 // straightforward way.
1033 // Drop all metadata that is not known to cause immediate UB on violation,
1034 // unless the load has !noundef, in which case all metadata violations
1035 // will be promoted to UB.
1036 // TODO: We can combine noalias/alias.scope metadata here, because it is
1037 // independent of the load type.
1038 if (!CoercedLoad->hasMetadata(LLVMContext::MD_noundef))
1039 CoercedLoad->dropUnknownNonDebugMetadata(
1040 {LLVMContext::MD_dereferenceable,
1041 LLVMContext::MD_dereferenceable_or_null,
1042 LLVMContext::MD_invariant_load, LLVMContext::MD_invariant_group});
1043 LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL LOAD:\nOffset: " << Offset
1044 << " " << *getCoercedLoadValue() << '\n'
1045 << *Res << '\n'
1046 << "\n\n\n");
1047 }
1048 } else if (isMemIntrinValue()) {
1049 Res = getMemInstValueForLoad(getMemIntrinValue(), Offset, LoadTy,
1050 InsertPt, DL);
1051 LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL MEM INTRIN:\nOffset: " << Offset
1052 << " " << *getMemIntrinValue() << '\n'
1053 << *Res << '\n'
1054 << "\n\n\n");
1055 } else if (isSelectValue()) {
1056 // Introduce a new value select for a load from an eligible pointer select.
1057 SelectInst *Sel = getSelectValue();
1058 assert(V1 && V2 && "both value operands of the select must be present");
1059 Res =
1060 SelectInst::Create(Sel->getCondition(), V1, V2, "", Sel->getIterator());
1061 } else {
1062 llvm_unreachable("Should not materialize value from dead block");
1063 }
1064 assert(Res && "failed to materialize?");
1065 return Res;
1066}
1067
1068static bool isLifetimeStart(const Instruction *Inst) {
1069 if (const IntrinsicInst* II = dyn_cast<IntrinsicInst>(Inst))
1070 return II->getIntrinsicID() == Intrinsic::lifetime_start;
1071 return false;
1072}
1073
1074/// Assuming To can be reached from both From and Between, does Between lie on
1075/// every path from From to To?
1076static bool liesBetween(const Instruction *From, Instruction *Between,
1077 const Instruction *To, DominatorTree *DT) {
1078 if (From->getParent() == Between->getParent())
1079 return DT->dominates(From, Between);
1080 SmallSet<BasicBlock *, 1> Exclusion;
1081 Exclusion.insert(Between->getParent());
1082 return !isPotentiallyReachable(From, To, &Exclusion, DT);
1083}
1084
1085/// Try to locate the three instruction involved in a missed
1086/// load-elimination case that is due to an intervening store.
1088 DominatorTree *DT,
1090 using namespace ore;
1091
1092 Instruction *OtherAccess = nullptr;
1093
1094 OptimizationRemarkMissed R(DEBUG_TYPE, "LoadClobbered", Load);
1095 R << "load of type " << NV("Type", Load->getType()) << " not eliminated"
1096 << setExtraArgs();
1097
1098 for (auto *U : Load->getPointerOperand()->users()) {
1099 if (U != Load && (isa<LoadInst>(U) || isa<StoreInst>(U))) {
1100 auto *I = cast<Instruction>(U);
1101 if (I->getFunction() == Load->getFunction() && DT->dominates(I, Load)) {
1102 // Use the most immediately dominating value
1103 if (OtherAccess) {
1104 if (DT->dominates(OtherAccess, I))
1105 OtherAccess = I;
1106 else
1107 assert(U == OtherAccess || DT->dominates(I, OtherAccess));
1108 } else
1109 OtherAccess = I;
1110 }
1111 }
1112 }
1113
1114 if (!OtherAccess) {
1115 // There is no dominating use, check if we can find a closest non-dominating
1116 // use that lies between any other potentially available use and Load.
1117 for (auto *U : Load->getPointerOperand()->users()) {
1118 if (U != Load && (isa<LoadInst>(U) || isa<StoreInst>(U))) {
1119 auto *I = cast<Instruction>(U);
1120 if (I->getFunction() == Load->getFunction() &&
1121 isPotentiallyReachable(I, Load, nullptr, DT)) {
1122 if (OtherAccess) {
1123 if (liesBetween(OtherAccess, I, Load, DT)) {
1124 OtherAccess = I;
1125 } else if (!liesBetween(I, OtherAccess, Load, DT)) {
1126 // These uses are both partially available at Load were it not for
1127 // the clobber, but neither lies strictly after the other.
1128 OtherAccess = nullptr;
1129 break;
1130 } // else: keep current OtherAccess since it lies between U and Load
1131 } else {
1132 OtherAccess = I;
1133 }
1134 }
1135 }
1136 }
1137 }
1138
1139 if (OtherAccess)
1140 R << " in favor of " << NV("OtherAccess", OtherAccess);
1141
1142 R << " because it is clobbered by " << NV("ClobberedBy", DepInfo.getInst());
1143
1144 ORE->emit(R);
1145}
1146
1147// Find non-clobbered value for Loc memory location in extended basic block
1148// (chain of basic blocks with single predecessors) starting From instruction.
1149static Value *findDominatingValue(const MemoryLocation &Loc, Type *LoadTy,
1150 Instruction *From, AAResults *AA) {
1151 uint32_t NumVisitedInsts = 0;
1152 BasicBlock *FromBB = From->getParent();
1153 BatchAAResults BatchAA(*AA);
1154 for (BasicBlock *BB = FromBB; BB; BB = BB->getSinglePredecessor())
1155 for (auto *Inst = BB == FromBB ? From : BB->getTerminator();
1156 Inst != nullptr; Inst = Inst->getPrevNonDebugInstruction()) {
1157 // Stop the search if limit is reached.
1158 if (++NumVisitedInsts > MaxNumVisitedInsts)
1159 return nullptr;
1160 if (isModSet(BatchAA.getModRefInfo(Inst, Loc)))
1161 return nullptr;
1162 if (auto *LI = dyn_cast<LoadInst>(Inst))
1163 if (LI->getPointerOperand() == Loc.Ptr && LI->getType() == LoadTy)
1164 return LI;
1165 }
1166 return nullptr;
1167}
1168
1169std::optional<AvailableValue>
1170GVNPass::AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo,
1171 Value *Address) {
1172 assert(Load->isUnordered() && "rules below are incorrect for ordered access");
1173 assert(DepInfo.isLocal() && "expected a local dependence");
1174
1175 Instruction *DepInst = DepInfo.getInst();
1176
1177 const DataLayout &DL = Load->getModule()->getDataLayout();
1178 if (DepInfo.isClobber()) {
1179 // If the dependence is to a store that writes to a superset of the bits
1180 // read by the load, we can extract the bits we need for the load from the
1181 // stored value.
1182 if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInst)) {
1183 // Can't forward from non-atomic to atomic without violating memory model.
1184 if (Address && Load->isAtomic() <= DepSI->isAtomic()) {
1185 int Offset =
1186 analyzeLoadFromClobberingStore(Load->getType(), Address, DepSI, DL);
1187 if (Offset != -1)
1188 return AvailableValue::get(DepSI->getValueOperand(), Offset);
1189 }
1190 }
1191
1192 // Check to see if we have something like this:
1193 // load i32* P
1194 // load i8* (P+1)
1195 // if we have this, replace the later with an extraction from the former.
1196 if (LoadInst *DepLoad = dyn_cast<LoadInst>(DepInst)) {
1197 // If this is a clobber and L is the first instruction in its block, then
1198 // we have the first instruction in the entry block.
1199 // Can't forward from non-atomic to atomic without violating memory model.
1200 if (DepLoad != Load && Address &&
1201 Load->isAtomic() <= DepLoad->isAtomic()) {
1202 Type *LoadType = Load->getType();
1203 int Offset = -1;
1204
1205 // If MD reported clobber, check it was nested.
1206 if (DepInfo.isClobber() &&
1207 canCoerceMustAliasedValueToLoad(DepLoad, LoadType, DL)) {
1208 const auto ClobberOff = MD->getClobberOffset(DepLoad);
1209 // GVN has no deal with a negative offset.
1210 Offset = (ClobberOff == std::nullopt || *ClobberOff < 0)
1211 ? -1
1212 : *ClobberOff;
1213 }
1214 if (Offset == -1)
1215 Offset =
1216 analyzeLoadFromClobberingLoad(LoadType, Address, DepLoad, DL);
1217 if (Offset != -1)
1218 return AvailableValue::getLoad(DepLoad, Offset);
1219 }
1220 }
1221
1222 // If the clobbering value is a memset/memcpy/memmove, see if we can
1223 // forward a value on from it.
1224 if (MemIntrinsic *DepMI = dyn_cast<MemIntrinsic>(DepInst)) {
1225 if (Address && !Load->isAtomic()) {
1227 DepMI, DL);
1228 if (Offset != -1)
1229 return AvailableValue::getMI(DepMI, Offset);
1230 }
1231 }
1232
1233 // Nothing known about this clobber, have to be conservative
1234 LLVM_DEBUG(
1235 // fast print dep, using operator<< on instruction is too slow.
1236 dbgs() << "GVN: load "; Load->printAsOperand(dbgs());
1237 dbgs() << " is clobbered by " << *DepInst << '\n';);
1239 reportMayClobberedLoad(Load, DepInfo, DT, ORE);
1240
1241 return std::nullopt;
1242 }
1243 assert(DepInfo.isDef() && "follows from above");
1244
1245 // Loading the alloca -> undef.
1246 // Loading immediately after lifetime begin -> undef.
1247 if (isa<AllocaInst>(DepInst) || isLifetimeStart(DepInst))
1248 return AvailableValue::get(UndefValue::get(Load->getType()));
1249
1250 if (Constant *InitVal =
1251 getInitialValueOfAllocation(DepInst, TLI, Load->getType()))
1252 return AvailableValue::get(InitVal);
1253
1254 if (StoreInst *S = dyn_cast<StoreInst>(DepInst)) {
1255 // Reject loads and stores that are to the same address but are of
1256 // different types if we have to. If the stored value is convertable to
1257 // the loaded value, we can reuse it.
1258 if (!canCoerceMustAliasedValueToLoad(S->getValueOperand(), Load->getType(),
1259 DL))
1260 return std::nullopt;
1261
1262 // Can't forward from non-atomic to atomic without violating memory model.
1263 if (S->isAtomic() < Load->isAtomic())
1264 return std::nullopt;
1265
1266 return AvailableValue::get(S->getValueOperand());
1267 }
1268
1269 if (LoadInst *LD = dyn_cast<LoadInst>(DepInst)) {
1270 // If the types mismatch and we can't handle it, reject reuse of the load.
1271 // If the stored value is larger or equal to the loaded value, we can reuse
1272 // it.
1273 if (!canCoerceMustAliasedValueToLoad(LD, Load->getType(), DL))
1274 return std::nullopt;
1275
1276 // Can't forward from non-atomic to atomic without violating memory model.
1277 if (LD->isAtomic() < Load->isAtomic())
1278 return std::nullopt;
1279
1280 return AvailableValue::getLoad(LD);
1281 }
1282
1283 // Check if load with Addr dependent from select can be converted to select
1284 // between load values. There must be no instructions between the found
1285 // loads and DepInst that may clobber the loads.
1286 if (auto *Sel = dyn_cast<SelectInst>(DepInst)) {
1287 assert(Sel->getType() == Load->getPointerOperandType());
1288 auto Loc = MemoryLocation::get(Load);
1289 Value *V1 =
1290 findDominatingValue(Loc.getWithNewPtr(Sel->getTrueValue()),
1291 Load->getType(), DepInst, getAliasAnalysis());
1292 if (!V1)
1293 return std::nullopt;
1294 Value *V2 =
1295 findDominatingValue(Loc.getWithNewPtr(Sel->getFalseValue()),
1296 Load->getType(), DepInst, getAliasAnalysis());
1297 if (!V2)
1298 return std::nullopt;
1299 return AvailableValue::getSelect(Sel, V1, V2);
1300 }
1301
1302 // Unknown def - must be conservative
1303 LLVM_DEBUG(
1304 // fast print dep, using operator<< on instruction is too slow.
1305 dbgs() << "GVN: load "; Load->printAsOperand(dbgs());
1306 dbgs() << " has unknown def " << *DepInst << '\n';);
1307 return std::nullopt;
1308}
1309
1310void GVNPass::AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps,
1311 AvailValInBlkVect &ValuesPerBlock,
1312 UnavailBlkVect &UnavailableBlocks) {
1313 // Filter out useless results (non-locals, etc). Keep track of the blocks
1314 // where we have a value available in repl, also keep track of whether we see
1315 // dependencies that produce an unknown value for the load (such as a call
1316 // that could potentially clobber the load).
1317 for (const auto &Dep : Deps) {
1318 BasicBlock *DepBB = Dep.getBB();
1319 MemDepResult DepInfo = Dep.getResult();
1320
1321 if (DeadBlocks.count(DepBB)) {
1322 // Dead dependent mem-op disguise as a load evaluating the same value
1323 // as the load in question.
1324 ValuesPerBlock.push_back(AvailableValueInBlock::getUndef(DepBB));
1325 continue;
1326 }
1327
1328 if (!DepInfo.isLocal()) {
1329 UnavailableBlocks.push_back(DepBB);
1330 continue;
1331 }
1332
1333 // The address being loaded in this non-local block may not be the same as
1334 // the pointer operand of the load if PHI translation occurs. Make sure
1335 // to consider the right address.
1336 if (auto AV = AnalyzeLoadAvailability(Load, DepInfo, Dep.getAddress())) {
1337 // subtlety: because we know this was a non-local dependency, we know
1338 // it's safe to materialize anywhere between the instruction within
1339 // DepInfo and the end of it's block.
1340 ValuesPerBlock.push_back(
1341 AvailableValueInBlock::get(DepBB, std::move(*AV)));
1342 } else {
1343 UnavailableBlocks.push_back(DepBB);
1344 }
1345 }
1346
1347 assert(Deps.size() == ValuesPerBlock.size() + UnavailableBlocks.size() &&
1348 "post condition violation");
1349}
1350
1351/// Given the following code, v1 is partially available on some edges, but not
1352/// available on the edge from PredBB. This function tries to find if there is
1353/// another identical load in the other successor of PredBB.
1354///
1355/// v0 = load %addr
1356/// br %LoadBB
1357///
1358/// LoadBB:
1359/// v1 = load %addr
1360/// ...
1361///
1362/// PredBB:
1363/// ...
1364/// br %cond, label %LoadBB, label %SuccBB
1365///
1366/// SuccBB:
1367/// v2 = load %addr
1368/// ...
1369///
1370LoadInst *GVNPass::findLoadToHoistIntoPred(BasicBlock *Pred, BasicBlock *LoadBB,
1371 LoadInst *Load) {
1372 // For simplicity we handle a Pred has 2 successors only.
1373 auto *Term = Pred->getTerminator();
1374 if (Term->getNumSuccessors() != 2 || Term->isSpecialTerminator())
1375 return nullptr;
1376 auto *SuccBB = Term->getSuccessor(0);
1377 if (SuccBB == LoadBB)
1378 SuccBB = Term->getSuccessor(1);
1379 if (!SuccBB->getSinglePredecessor())
1380 return nullptr;
1381
1382 unsigned int NumInsts = MaxNumInsnsPerBlock;
1383 for (Instruction &Inst : *SuccBB) {
1384 if (Inst.isDebugOrPseudoInst())
1385 continue;
1386 if (--NumInsts == 0)
1387 return nullptr;
1388
1389 if (!Inst.isIdenticalTo(Load))
1390 continue;
1391
1392 MemDepResult Dep = MD->getDependency(&Inst);
1393 // If an identical load doesn't depends on any local instructions, it can
1394 // be safely moved to PredBB.
1395 // Also check for the implicit control flow instructions. See the comments
1396 // in PerformLoadPRE for details.
1397 if (Dep.isNonLocal() && !ICF->isDominatedByICFIFromSameBlock(&Inst))
1398 return cast<LoadInst>(&Inst);
1399
1400 // Otherwise there is something in the same BB clobbers the memory, we can't
1401 // move this and later load to PredBB.
1402 return nullptr;
1403 }
1404
1405 return nullptr;
1406}
1407
1408void GVNPass::eliminatePartiallyRedundantLoad(
1409 LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
1410 MapVector<BasicBlock *, Value *> &AvailableLoads,
1411 MapVector<BasicBlock *, LoadInst *> *CriticalEdgePredAndLoad) {
1412 for (const auto &AvailableLoad : AvailableLoads) {
1413 BasicBlock *UnavailableBlock = AvailableLoad.first;
1414 Value *LoadPtr = AvailableLoad.second;
1415
1416 auto *NewLoad = new LoadInst(
1417 Load->getType(), LoadPtr, Load->getName() + ".pre", Load->isVolatile(),
1418 Load->getAlign(), Load->getOrdering(), Load->getSyncScopeID(),
1419 UnavailableBlock->getTerminator()->getIterator());
1420 NewLoad->setDebugLoc(Load->getDebugLoc());
1421 if (MSSAU) {
1422 auto *NewAccess = MSSAU->createMemoryAccessInBB(
1423 NewLoad, nullptr, NewLoad->getParent(), MemorySSA::BeforeTerminator);
1424 if (auto *NewDef = dyn_cast<MemoryDef>(NewAccess))
1425 MSSAU->insertDef(NewDef, /*RenameUses=*/true);
1426 else
1427 MSSAU->insertUse(cast<MemoryUse>(NewAccess), /*RenameUses=*/true);
1428 }
1429
1430 // Transfer the old load's AA tags to the new load.
1431 AAMDNodes Tags = Load->getAAMetadata();
1432 if (Tags)
1433 NewLoad->setAAMetadata(Tags);
1434
1435 if (auto *MD = Load->getMetadata(LLVMContext::MD_invariant_load))
1436 NewLoad->setMetadata(LLVMContext::MD_invariant_load, MD);
1437 if (auto *InvGroupMD = Load->getMetadata(LLVMContext::MD_invariant_group))
1438 NewLoad->setMetadata(LLVMContext::MD_invariant_group, InvGroupMD);
1439 if (auto *RangeMD = Load->getMetadata(LLVMContext::MD_range))
1440 NewLoad->setMetadata(LLVMContext::MD_range, RangeMD);
1441 if (auto *AccessMD = Load->getMetadata(LLVMContext::MD_access_group))
1442 if (LI->getLoopFor(Load->getParent()) == LI->getLoopFor(UnavailableBlock))
1443 NewLoad->setMetadata(LLVMContext::MD_access_group, AccessMD);
1444
1445 // We do not propagate the old load's debug location, because the new
1446 // load now lives in a different BB, and we want to avoid a jumpy line
1447 // table.
1448 // FIXME: How do we retain source locations without causing poor debugging
1449 // behavior?
1450
1451 // Add the newly created load.
1452 ValuesPerBlock.push_back(
1453 AvailableValueInBlock::get(UnavailableBlock, NewLoad));
1454 MD->invalidateCachedPointerInfo(LoadPtr);
1455 LLVM_DEBUG(dbgs() << "GVN INSERTED " << *NewLoad << '\n');
1456
1457 // For PredBB in CriticalEdgePredAndLoad we need to replace the uses of old
1458 // load instruction with the new created load instruction.
1459 if (CriticalEdgePredAndLoad) {
1460 auto I = CriticalEdgePredAndLoad->find(UnavailableBlock);
1461 if (I != CriticalEdgePredAndLoad->end()) {
1462 ++NumPRELoadMoved2CEPred;
1463 ICF->insertInstructionTo(NewLoad, UnavailableBlock);
1464 LoadInst *OldLoad = I->second;
1465 combineMetadataForCSE(NewLoad, OldLoad, false);
1466 OldLoad->replaceAllUsesWith(NewLoad);
1467 replaceValuesPerBlockEntry(ValuesPerBlock, OldLoad, NewLoad);
1468 if (uint32_t ValNo = VN.lookup(OldLoad, false))
1469 removeFromLeaderTable(ValNo, OldLoad, OldLoad->getParent());
1470 VN.erase(OldLoad);
1471 removeInstruction(OldLoad);
1472 }
1473 }
1474 }
1475
1476 // Perform PHI construction.
1477 Value *V = ConstructSSAForLoadSet(Load, ValuesPerBlock, *this);
1478 // ConstructSSAForLoadSet is responsible for combining metadata.
1479 ICF->removeUsersOf(Load);
1480 Load->replaceAllUsesWith(V);
1481 if (isa<PHINode>(V))
1482 V->takeName(Load);
1483 if (Instruction *I = dyn_cast<Instruction>(V))
1484 I->setDebugLoc(Load->getDebugLoc());
1485 if (V->getType()->isPtrOrPtrVectorTy())
1488 ORE->emit([&]() {
1489 return OptimizationRemark(DEBUG_TYPE, "LoadPRE", Load)
1490 << "load eliminated by PRE";
1491 });
1492}
1493
1494bool GVNPass::PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
1495 UnavailBlkVect &UnavailableBlocks) {
1496 // Okay, we have *some* definitions of the value. This means that the value
1497 // is available in some of our (transitive) predecessors. Lets think about
1498 // doing PRE of this load. This will involve inserting a new load into the
1499 // predecessor when it's not available. We could do this in general, but
1500 // prefer to not increase code size. As such, we only do this when we know
1501 // that we only have to insert *one* load (which means we're basically moving
1502 // the load, not inserting a new one).
1503
1504 SmallPtrSet<BasicBlock *, 4> Blockers(UnavailableBlocks.begin(),
1505 UnavailableBlocks.end());
1506
1507 // Let's find the first basic block with more than one predecessor. Walk
1508 // backwards through predecessors if needed.
1509 BasicBlock *LoadBB = Load->getParent();
1510 BasicBlock *TmpBB = LoadBB;
1511
1512 // Check that there is no implicit control flow instructions above our load in
1513 // its block. If there is an instruction that doesn't always pass the
1514 // execution to the following instruction, then moving through it may become
1515 // invalid. For example:
1516 //
1517 // int arr[LEN];
1518 // int index = ???;
1519 // ...
1520 // guard(0 <= index && index < LEN);
1521 // use(arr[index]);
1522 //
1523 // It is illegal to move the array access to any point above the guard,
1524 // because if the index is out of bounds we should deoptimize rather than
1525 // access the array.
1526 // Check that there is no guard in this block above our instruction.
1527 bool MustEnsureSafetyOfSpeculativeExecution =
1529
1530 while (TmpBB->getSinglePredecessor()) {
1531 TmpBB = TmpBB->getSinglePredecessor();
1532 if (TmpBB == LoadBB) // Infinite (unreachable) loop.
1533 return false;
1534 if (Blockers.count(TmpBB))
1535 return false;
1536
1537 // If any of these blocks has more than one successor (i.e. if the edge we
1538 // just traversed was critical), then there are other paths through this
1539 // block along which the load may not be anticipated. Hoisting the load
1540 // above this block would be adding the load to execution paths along
1541 // which it was not previously executed.
1542 if (TmpBB->getTerminator()->getNumSuccessors() != 1)
1543 return false;
1544
1545 // Check that there is no implicit control flow in a block above.
1546 MustEnsureSafetyOfSpeculativeExecution =
1547 MustEnsureSafetyOfSpeculativeExecution || ICF->hasICF(TmpBB);
1548 }
1549
1550 assert(TmpBB);
1551 LoadBB = TmpBB;
1552
1553 // Check to see how many predecessors have the loaded value fully
1554 // available.
1556 DenseMap<BasicBlock *, AvailabilityState> FullyAvailableBlocks;
1557 for (const AvailableValueInBlock &AV : ValuesPerBlock)
1558 FullyAvailableBlocks[AV.BB] = AvailabilityState::Available;
1559 for (BasicBlock *UnavailableBB : UnavailableBlocks)
1560 FullyAvailableBlocks[UnavailableBB] = AvailabilityState::Unavailable;
1561
1562 // The edge from Pred to LoadBB is a critical edge will be splitted.
1563 SmallVector<BasicBlock *, 4> CriticalEdgePredSplit;
1564 // The edge from Pred to LoadBB is a critical edge, another successor of Pred
1565 // contains a load can be moved to Pred. This data structure maps the Pred to
1566 // the movable load.
1567 MapVector<BasicBlock *, LoadInst *> CriticalEdgePredAndLoad;
1568 for (BasicBlock *Pred : predecessors(LoadBB)) {
1569 // If any predecessor block is an EH pad that does not allow non-PHI
1570 // instructions before the terminator, we can't PRE the load.
1571 if (Pred->getTerminator()->isEHPad()) {
1572 LLVM_DEBUG(
1573 dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD PREDECESSOR '"
1574 << Pred->getName() << "': " << *Load << '\n');
1575 return false;
1576 }
1577
1578 if (IsValueFullyAvailableInBlock(Pred, FullyAvailableBlocks)) {
1579 continue;
1580 }
1581
1582 if (Pred->getTerminator()->getNumSuccessors() != 1) {
1583 if (isa<IndirectBrInst>(Pred->getTerminator())) {
1584 LLVM_DEBUG(
1585 dbgs() << "COULD NOT PRE LOAD BECAUSE OF INDBR CRITICAL EDGE '"
1586 << Pred->getName() << "': " << *Load << '\n');
1587 return false;
1588 }
1589
1590 if (LoadBB->isEHPad()) {
1591 LLVM_DEBUG(
1592 dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD CRITICAL EDGE '"
1593 << Pred->getName() << "': " << *Load << '\n');
1594 return false;
1595 }
1596
1597 // Do not split backedge as it will break the canonical loop form.
1599 if (DT->dominates(LoadBB, Pred)) {
1600 LLVM_DEBUG(
1601 dbgs()
1602 << "COULD NOT PRE LOAD BECAUSE OF A BACKEDGE CRITICAL EDGE '"
1603 << Pred->getName() << "': " << *Load << '\n');
1604 return false;
1605 }
1606
1607 if (LoadInst *LI = findLoadToHoistIntoPred(Pred, LoadBB, Load))
1608 CriticalEdgePredAndLoad[Pred] = LI;
1609 else
1610 CriticalEdgePredSplit.push_back(Pred);
1611 } else {
1612 // Only add the predecessors that will not be split for now.
1613 PredLoads[Pred] = nullptr;
1614 }
1615 }
1616
1617 // Decide whether PRE is profitable for this load.
1618 unsigned NumInsertPreds = PredLoads.size() + CriticalEdgePredSplit.size();
1619 unsigned NumUnavailablePreds = NumInsertPreds +
1620 CriticalEdgePredAndLoad.size();
1621 assert(NumUnavailablePreds != 0 &&
1622 "Fully available value should already be eliminated!");
1623 (void)NumUnavailablePreds;
1624
1625 // If we need to insert new load in multiple predecessors, reject it.
1626 // FIXME: If we could restructure the CFG, we could make a common pred with
1627 // all the preds that don't have an available Load and insert a new load into
1628 // that one block.
1629 if (NumInsertPreds > 1)
1630 return false;
1631
1632 // Now we know where we will insert load. We must ensure that it is safe
1633 // to speculatively execute the load at that points.
1634 if (MustEnsureSafetyOfSpeculativeExecution) {
1635 if (CriticalEdgePredSplit.size())
1636 if (!isSafeToSpeculativelyExecute(Load, LoadBB->getFirstNonPHI(), AC, DT))
1637 return false;
1638 for (auto &PL : PredLoads)
1639 if (!isSafeToSpeculativelyExecute(Load, PL.first->getTerminator(), AC,
1640 DT))
1641 return false;
1642 for (auto &CEP : CriticalEdgePredAndLoad)
1643 if (!isSafeToSpeculativelyExecute(Load, CEP.first->getTerminator(), AC,
1644 DT))
1645 return false;
1646 }
1647
1648 // Split critical edges, and update the unavailable predecessors accordingly.
1649 for (BasicBlock *OrigPred : CriticalEdgePredSplit) {
1650 BasicBlock *NewPred = splitCriticalEdges(OrigPred, LoadBB);
1651 assert(!PredLoads.count(OrigPred) && "Split edges shouldn't be in map!");
1652 PredLoads[NewPred] = nullptr;
1653 LLVM_DEBUG(dbgs() << "Split critical edge " << OrigPred->getName() << "->"
1654 << LoadBB->getName() << '\n');
1655 }
1656
1657 for (auto &CEP : CriticalEdgePredAndLoad)
1658 PredLoads[CEP.first] = nullptr;
1659
1660 // Check if the load can safely be moved to all the unavailable predecessors.
1661 bool CanDoPRE = true;
1662 const DataLayout &DL = Load->getModule()->getDataLayout();
1664 for (auto &PredLoad : PredLoads) {
1665 BasicBlock *UnavailablePred = PredLoad.first;
1666
1667 // Do PHI translation to get its value in the predecessor if necessary. The
1668 // returned pointer (if non-null) is guaranteed to dominate UnavailablePred.
1669 // We do the translation for each edge we skipped by going from Load's block
1670 // to LoadBB, otherwise we might miss pieces needing translation.
1671
1672 // If all preds have a single successor, then we know it is safe to insert
1673 // the load on the pred (?!?), so we can insert code to materialize the
1674 // pointer if it is not available.
1675 Value *LoadPtr = Load->getPointerOperand();
1676 BasicBlock *Cur = Load->getParent();
1677 while (Cur != LoadBB) {
1678 PHITransAddr Address(LoadPtr, DL, AC);
1679 LoadPtr = Address.translateWithInsertion(Cur, Cur->getSinglePredecessor(),
1680 *DT, NewInsts);
1681 if (!LoadPtr) {
1682 CanDoPRE = false;
1683 break;
1684 }
1685 Cur = Cur->getSinglePredecessor();
1686 }
1687
1688 if (LoadPtr) {
1689 PHITransAddr Address(LoadPtr, DL, AC);
1690 LoadPtr = Address.translateWithInsertion(LoadBB, UnavailablePred, *DT,
1691 NewInsts);
1692 }
1693 // If we couldn't find or insert a computation of this phi translated value,
1694 // we fail PRE.
1695 if (!LoadPtr) {
1696 LLVM_DEBUG(dbgs() << "COULDN'T INSERT PHI TRANSLATED VALUE OF: "
1697 << *Load->getPointerOperand() << "\n");
1698 CanDoPRE = false;
1699 break;
1700 }
1701
1702 PredLoad.second = LoadPtr;
1703 }
1704
1705 if (!CanDoPRE) {
1706 while (!NewInsts.empty()) {
1707 // Erase instructions generated by the failed PHI translation before
1708 // trying to number them. PHI translation might insert instructions
1709 // in basic blocks other than the current one, and we delete them
1710 // directly, as markInstructionForDeletion only allows removing from the
1711 // current basic block.
1712 NewInsts.pop_back_val()->eraseFromParent();
1713 }
1714 // HINT: Don't revert the edge-splitting as following transformation may
1715 // also need to split these critical edges.
1716 return !CriticalEdgePredSplit.empty();
1717 }
1718
1719 // Okay, we can eliminate this load by inserting a reload in the predecessor
1720 // and using PHI construction to get the value in the other predecessors, do
1721 // it.
1722 LLVM_DEBUG(dbgs() << "GVN REMOVING PRE LOAD: " << *Load << '\n');
1723 LLVM_DEBUG(if (!NewInsts.empty()) dbgs() << "INSERTED " << NewInsts.size()
1724 << " INSTS: " << *NewInsts.back()
1725 << '\n');
1726
1727 // Assign value numbers to the new instructions.
1728 for (Instruction *I : NewInsts) {
1729 // Instructions that have been inserted in predecessor(s) to materialize
1730 // the load address do not retain their original debug locations. Doing
1731 // so could lead to confusing (but correct) source attributions.
1732 I->updateLocationAfterHoist();
1733
1734 // FIXME: We really _ought_ to insert these value numbers into their
1735 // parent's availability map. However, in doing so, we risk getting into
1736 // ordering issues. If a block hasn't been processed yet, we would be
1737 // marking a value as AVAIL-IN, which isn't what we intend.
1738 VN.lookupOrAdd(I);
1739 }
1740
1741 eliminatePartiallyRedundantLoad(Load, ValuesPerBlock, PredLoads,
1742 &CriticalEdgePredAndLoad);
1743 ++NumPRELoad;
1744 return true;
1745}
1746
1747bool GVNPass::performLoopLoadPRE(LoadInst *Load,
1748 AvailValInBlkVect &ValuesPerBlock,
1749 UnavailBlkVect &UnavailableBlocks) {
1750 const Loop *L = LI->getLoopFor(Load->getParent());
1751 // TODO: Generalize to other loop blocks that dominate the latch.
1752 if (!L || L->getHeader() != Load->getParent())
1753 return false;
1754
1755 BasicBlock *Preheader = L->getLoopPreheader();
1756 BasicBlock *Latch = L->getLoopLatch();
1757 if (!Preheader || !Latch)
1758 return false;
1759
1760 Value *LoadPtr = Load->getPointerOperand();
1761 // Must be available in preheader.
1762 if (!L->isLoopInvariant(LoadPtr))
1763 return false;
1764
1765 // We plan to hoist the load to preheader without introducing a new fault.
1766 // In order to do it, we need to prove that we cannot side-exit the loop
1767 // once loop header is first entered before execution of the load.
1768 if (ICF->isDominatedByICFIFromSameBlock(Load))
1769 return false;
1770
1771 BasicBlock *LoopBlock = nullptr;
1772 for (auto *Blocker : UnavailableBlocks) {
1773 // Blockers from outside the loop are handled in preheader.
1774 if (!L->contains(Blocker))
1775 continue;
1776
1777 // Only allow one loop block. Loop header is not less frequently executed
1778 // than each loop block, and likely it is much more frequently executed. But
1779 // in case of multiple loop blocks, we need extra information (such as block
1780 // frequency info) to understand whether it is profitable to PRE into
1781 // multiple loop blocks.
1782 if (LoopBlock)
1783 return false;
1784
1785 // Do not sink into inner loops. This may be non-profitable.
1786 if (L != LI->getLoopFor(Blocker))
1787 return false;
1788
1789 // Blocks that dominate the latch execute on every single iteration, maybe
1790 // except the last one. So PREing into these blocks doesn't make much sense
1791 // in most cases. But the blocks that do not necessarily execute on each
1792 // iteration are sometimes much colder than the header, and this is when
1793 // PRE is potentially profitable.
1794 if (DT->dominates(Blocker, Latch))
1795 return false;
1796
1797 // Make sure that the terminator itself doesn't clobber.
1798 if (Blocker->getTerminator()->mayWriteToMemory())
1799 return false;
1800
1801 LoopBlock = Blocker;
1802 }
1803
1804 if (!LoopBlock)
1805 return false;
1806
1807 // Make sure the memory at this pointer cannot be freed, therefore we can
1808 // safely reload from it after clobber.
1809 if (LoadPtr->canBeFreed())
1810 return false;
1811
1812 // TODO: Support critical edge splitting if blocker has more than 1 successor.
1813 MapVector<BasicBlock *, Value *> AvailableLoads;
1814 AvailableLoads[LoopBlock] = LoadPtr;
1815 AvailableLoads[Preheader] = LoadPtr;
1816
1817 LLVM_DEBUG(dbgs() << "GVN REMOVING PRE LOOP LOAD: " << *Load << '\n');
1818 eliminatePartiallyRedundantLoad(Load, ValuesPerBlock, AvailableLoads,
1819 /*CriticalEdgePredAndLoad*/ nullptr);
1820 ++NumPRELoopLoad;
1821 return true;
1822}
1823
1826 using namespace ore;
1827
1828 ORE->emit([&]() {
1829 return OptimizationRemark(DEBUG_TYPE, "LoadElim", Load)
1830 << "load of type " << NV("Type", Load->getType()) << " eliminated"
1831 << setExtraArgs() << " in favor of "
1832 << NV("InfavorOfValue", AvailableValue);
1833 });
1834}
1835
1836/// Attempt to eliminate a load whose dependencies are
1837/// non-local by performing PHI construction.
1838bool GVNPass::processNonLocalLoad(LoadInst *Load) {
1839 // non-local speculations are not allowed under asan.
1840 if (Load->getParent()->getParent()->hasFnAttribute(
1841 Attribute::SanitizeAddress) ||
1842 Load->getParent()->getParent()->hasFnAttribute(
1843 Attribute::SanitizeHWAddress))
1844 return false;
1845
1846 // Step 1: Find the non-local dependencies of the load.
1847 LoadDepVect Deps;
1848 MD->getNonLocalPointerDependency(Load, Deps);
1849
1850 // If we had to process more than one hundred blocks to find the
1851 // dependencies, this load isn't worth worrying about. Optimizing
1852 // it will be too expensive.
1853 unsigned NumDeps = Deps.size();
1854 if (NumDeps > MaxNumDeps)
1855 return false;
1856
1857 // If we had a phi translation failure, we'll have a single entry which is a
1858 // clobber in the current block. Reject this early.
1859 if (NumDeps == 1 &&
1860 !Deps[0].getResult().isDef() && !Deps[0].getResult().isClobber()) {
1861 LLVM_DEBUG(dbgs() << "GVN: non-local load "; Load->printAsOperand(dbgs());
1862 dbgs() << " has unknown dependencies\n";);
1863 return false;
1864 }
1865
1866 bool Changed = false;
1867 // If this load follows a GEP, see if we can PRE the indices before analyzing.
1868 if (GetElementPtrInst *GEP =
1869 dyn_cast<GetElementPtrInst>(Load->getOperand(0))) {
1870 for (Use &U : GEP->indices())
1871 if (Instruction *I = dyn_cast<Instruction>(U.get()))
1872 Changed |= performScalarPRE(I);
1873 }
1874
1875 // Step 2: Analyze the availability of the load
1876 AvailValInBlkVect ValuesPerBlock;
1877 UnavailBlkVect UnavailableBlocks;
1878 AnalyzeLoadAvailability(Load, Deps, ValuesPerBlock, UnavailableBlocks);
1879
1880 // If we have no predecessors that produce a known value for this load, exit
1881 // early.
1882 if (ValuesPerBlock.empty())
1883 return Changed;
1884
1885 // Step 3: Eliminate fully redundancy.
1886 //
1887 // If all of the instructions we depend on produce a known value for this
1888 // load, then it is fully redundant and we can use PHI insertion to compute
1889 // its value. Insert PHIs and remove the fully redundant value now.
1890 if (UnavailableBlocks.empty()) {
1891 LLVM_DEBUG(dbgs() << "GVN REMOVING NONLOCAL LOAD: " << *Load << '\n');
1892
1893 // Perform PHI construction.
1894 Value *V = ConstructSSAForLoadSet(Load, ValuesPerBlock, *this);
1895 // ConstructSSAForLoadSet is responsible for combining metadata.
1896 ICF->removeUsersOf(Load);
1897 Load->replaceAllUsesWith(V);
1898
1899 if (isa<PHINode>(V))
1900 V->takeName(Load);
1901 if (Instruction *I = dyn_cast<Instruction>(V))
1902 // If instruction I has debug info, then we should not update it.
1903 // Also, if I has a null DebugLoc, then it is still potentially incorrect
1904 // to propagate Load's DebugLoc because Load may not post-dominate I.
1905 if (Load->getDebugLoc() && Load->getParent() == I->getParent())
1906 I->setDebugLoc(Load->getDebugLoc());
1907 if (V->getType()->isPtrOrPtrVectorTy())
1910 ++NumGVNLoad;
1911 reportLoadElim(Load, V, ORE);
1912 return true;
1913 }
1914
1915 // Step 4: Eliminate partial redundancy.
1916 if (!isPREEnabled() || !isLoadPREEnabled())
1917 return Changed;
1918 if (!isLoadInLoopPREEnabled() && LI->getLoopFor(Load->getParent()))
1919 return Changed;
1920
1921 if (performLoopLoadPRE(Load, ValuesPerBlock, UnavailableBlocks) ||
1922 PerformLoadPRE(Load, ValuesPerBlock, UnavailableBlocks))
1923 return true;
1924
1925 return Changed;
1926}
1927
1929 if (Cmp->getPredicate() == CmpInst::Predicate::ICMP_EQ)
1930 return true;
1931
1932 // Floating point comparisons can be equal, but not equivalent. Cases:
1933 // NaNs for unordered operators
1934 // +0.0 vs 0.0 for all operators
1935 if (Cmp->getPredicate() == CmpInst::Predicate::FCMP_OEQ ||
1936 (Cmp->getPredicate() == CmpInst::Predicate::FCMP_UEQ &&
1937 Cmp->getFastMathFlags().noNaNs())) {
1938 Value *LHS = Cmp->getOperand(0);
1939 Value *RHS = Cmp->getOperand(1);
1940 // If we can prove either side non-zero, then equality must imply
1941 // equivalence.
1942 // FIXME: We should do this optimization if 'no signed zeros' is
1943 // applicable via an instruction-level fast-math-flag or some other
1944 // indicator that relaxed FP semantics are being used.
1945 if (isa<ConstantFP>(LHS) && !cast<ConstantFP>(LHS)->isZero())
1946 return true;
1947 if (isa<ConstantFP>(RHS) && !cast<ConstantFP>(RHS)->isZero())
1948 return true;
1949 // TODO: Handle vector floating point constants
1950 }
1951 return false;
1952}
1953
1955 if (Cmp->getPredicate() == CmpInst::Predicate::ICMP_NE)
1956 return true;
1957
1958 // Floating point comparisons can be equal, but not equivelent. Cases:
1959 // NaNs for unordered operators
1960 // +0.0 vs 0.0 for all operators
1961 if ((Cmp->getPredicate() == CmpInst::Predicate::FCMP_ONE &&
1962 Cmp->getFastMathFlags().noNaNs()) ||
1963 Cmp->getPredicate() == CmpInst::Predicate::FCMP_UNE) {
1964 Value *LHS = Cmp->getOperand(0);
1965 Value *RHS = Cmp->getOperand(1);
1966 // If we can prove either side non-zero, then equality must imply
1967 // equivalence.
1968 // FIXME: We should do this optimization if 'no signed zeros' is
1969 // applicable via an instruction-level fast-math-flag or some other
1970 // indicator that relaxed FP semantics are being used.
1971 if (isa<ConstantFP>(LHS) && !cast<ConstantFP>(LHS)->isZero())
1972 return true;
1973 if (isa<ConstantFP>(RHS) && !cast<ConstantFP>(RHS)->isZero())
1974 return true;
1975 // TODO: Handle vector floating point constants
1976 }
1977 return false;
1978}
1979
1980
1981static bool hasUsersIn(Value *V, BasicBlock *BB) {
1982 return llvm::any_of(V->users(), [BB](User *U) {
1983 auto *I = dyn_cast<Instruction>(U);
1984 return I && I->getParent() == BB;
1985 });
1986}
1987
1988bool GVNPass::processAssumeIntrinsic(AssumeInst *IntrinsicI) {
1989 Value *V = IntrinsicI->getArgOperand(0);
1990
1991 if (ConstantInt *Cond = dyn_cast<ConstantInt>(V)) {
1992 if (Cond->isZero()) {
1993 Type *Int8Ty = Type::getInt8Ty(V->getContext());
1994 Type *PtrTy = PointerType::get(V->getContext(), 0);
1995 // Insert a new store to null instruction before the load to indicate that
1996 // this code is not reachable. FIXME: We could insert unreachable
1997 // instruction directly because we can modify the CFG.
1998 auto *NewS =
2000 IntrinsicI->getIterator());
2001 if (MSSAU) {
2002 const MemoryUseOrDef *FirstNonDom = nullptr;
2003 const auto *AL =
2004 MSSAU->getMemorySSA()->getBlockAccesses(IntrinsicI->getParent());
2005
2006 // If there are accesses in the current basic block, find the first one
2007 // that does not come before NewS. The new memory access is inserted
2008 // after the found access or before the terminator if no such access is
2009 // found.
2010 if (AL) {
2011 for (const auto &Acc : *AL) {
2012 if (auto *Current = dyn_cast<MemoryUseOrDef>(&Acc))
2013 if (!Current->getMemoryInst()->comesBefore(NewS)) {
2014 FirstNonDom = Current;
2015 break;
2016 }
2017 }
2018 }
2019
2020 auto *NewDef =
2021 FirstNonDom ? MSSAU->createMemoryAccessBefore(
2022 NewS, nullptr,
2023 const_cast<MemoryUseOrDef *>(FirstNonDom))
2024 : MSSAU->createMemoryAccessInBB(
2025 NewS, nullptr,
2026 NewS->getParent(), MemorySSA::BeforeTerminator);
2027
2028 MSSAU->insertDef(cast<MemoryDef>(NewDef), /*RenameUses=*/false);
2029 }
2030 }
2031 if (isAssumeWithEmptyBundle(*IntrinsicI)) {
2032 markInstructionForDeletion(IntrinsicI);
2033 return true;
2034 }
2035 return false;
2036 }
2037
2038 if (isa<Constant>(V)) {
2039 // If it's not false, and constant, it must evaluate to true. This means our
2040 // assume is assume(true), and thus, pointless, and we don't want to do
2041 // anything more here.
2042 return false;
2043 }
2044
2045 Constant *True = ConstantInt::getTrue(V->getContext());
2046 bool Changed = false;
2047
2048 for (BasicBlock *Successor : successors(IntrinsicI->getParent())) {
2049 BasicBlockEdge Edge(IntrinsicI->getParent(), Successor);
2050
2051 // This property is only true in dominated successors, propagateEquality
2052 // will check dominance for us.
2053 Changed |= propagateEquality(V, True, Edge, false);
2054 }
2055
2056 // We can replace assume value with true, which covers cases like this:
2057 // call void @llvm.assume(i1 %cmp)
2058 // br i1 %cmp, label %bb1, label %bb2 ; will change %cmp to true
2059 ReplaceOperandsWithMap[V] = True;
2060
2061 // Similarly, after assume(!NotV) we know that NotV == false.
2062 Value *NotV;
2063 if (match(V, m_Not(m_Value(NotV))))
2064 ReplaceOperandsWithMap[NotV] = ConstantInt::getFalse(V->getContext());
2065
2066 // If we find an equality fact, canonicalize all dominated uses in this block
2067 // to one of the two values. We heuristically choice the "oldest" of the
2068 // two where age is determined by value number. (Note that propagateEquality
2069 // above handles the cross block case.)
2070 //
2071 // Key case to cover are:
2072 // 1)
2073 // %cmp = fcmp oeq float 3.000000e+00, %0 ; const on lhs could happen
2074 // call void @llvm.assume(i1 %cmp)
2075 // ret float %0 ; will change it to ret float 3.000000e+00
2076 // 2)
2077 // %load = load float, float* %addr
2078 // %cmp = fcmp oeq float %load, %0
2079 // call void @llvm.assume(i1 %cmp)
2080 // ret float %load ; will change it to ret float %0
2081 if (auto *CmpI = dyn_cast<CmpInst>(V)) {
2082 if (impliesEquivalanceIfTrue(CmpI)) {
2083 Value *CmpLHS = CmpI->getOperand(0);
2084 Value *CmpRHS = CmpI->getOperand(1);
2085 // Heuristically pick the better replacement -- the choice of heuristic
2086 // isn't terribly important here, but the fact we canonicalize on some
2087 // replacement is for exposing other simplifications.
2088 // TODO: pull this out as a helper function and reuse w/existing
2089 // (slightly different) logic.
2090 if (isa<Constant>(CmpLHS) && !isa<Constant>(CmpRHS))
2091 std::swap(CmpLHS, CmpRHS);
2092 if (!isa<Instruction>(CmpLHS) && isa<Instruction>(CmpRHS))
2093 std::swap(CmpLHS, CmpRHS);
2094 if ((isa<Argument>(CmpLHS) && isa<Argument>(CmpRHS)) ||
2095 (isa<Instruction>(CmpLHS) && isa<Instruction>(CmpRHS))) {
2096 // Move the 'oldest' value to the right-hand side, using the value
2097 // number as a proxy for age.
2098 uint32_t LVN = VN.lookupOrAdd(CmpLHS);
2099 uint32_t RVN = VN.lookupOrAdd(CmpRHS);
2100 if (LVN < RVN)
2101 std::swap(CmpLHS, CmpRHS);
2102 }
2103
2104 // Handle degenerate case where we either haven't pruned a dead path or a
2105 // removed a trivial assume yet.
2106 if (isa<Constant>(CmpLHS) && isa<Constant>(CmpRHS))
2107 return Changed;
2108
2109 LLVM_DEBUG(dbgs() << "Replacing dominated uses of "
2110 << *CmpLHS << " with "
2111 << *CmpRHS << " in block "
2112 << IntrinsicI->getParent()->getName() << "\n");
2113
2114
2115 // Setup the replacement map - this handles uses within the same block
2116 if (hasUsersIn(CmpLHS, IntrinsicI->getParent()))
2117 ReplaceOperandsWithMap[CmpLHS] = CmpRHS;
2118
2119 // NOTE: The non-block local cases are handled by the call to
2120 // propagateEquality above; this block is just about handling the block
2121 // local cases. TODO: There's a bunch of logic in propagateEqualiy which
2122 // isn't duplicated for the block local case, can we share it somehow?
2123 }
2124 }
2125 return Changed;
2126}
2127
2130 I->replaceAllUsesWith(Repl);
2131}
2132
2133/// Attempt to eliminate a load, first by eliminating it
2134/// locally, and then attempting non-local elimination if that fails.
2135bool GVNPass::processLoad(LoadInst *L) {
2136 if (!MD)
2137 return false;
2138
2139 // This code hasn't been audited for ordered or volatile memory access
2140 if (!L->isUnordered())
2141 return false;
2142
2143 if (L->use_empty()) {
2145 return true;
2146 }
2147
2148 // ... to a pointer that has been loaded from before...
2149 MemDepResult Dep = MD->getDependency(L);
2150
2151 // If it is defined in another block, try harder.
2152 if (Dep.isNonLocal())
2153 return processNonLocalLoad(L);
2154
2155 // Only handle the local case below
2156 if (!Dep.isLocal()) {
2157 // This might be a NonFuncLocal or an Unknown
2158 LLVM_DEBUG(
2159 // fast print dep, using operator<< on instruction is too slow.
2160 dbgs() << "GVN: load "; L->printAsOperand(dbgs());
2161 dbgs() << " has unknown dependence\n";);
2162 return false;
2163 }
2164
2165 auto AV = AnalyzeLoadAvailability(L, Dep, L->getPointerOperand());
2166 if (!AV)
2167 return false;
2168
2169 Value *AvailableValue = AV->MaterializeAdjustedValue(L, L, *this);
2170
2171 // MaterializeAdjustedValue is responsible for combining metadata.
2172 ICF->removeUsersOf(L);
2173 L->replaceAllUsesWith(AvailableValue);
2175 if (MSSAU)
2176 MSSAU->removeMemoryAccess(L);
2177 ++NumGVNLoad;
2179 // Tell MDA to reexamine the reused pointer since we might have more
2180 // information after forwarding it.
2181 if (MD && AvailableValue->getType()->isPtrOrPtrVectorTy())
2183 return true;
2184}
2185
2186/// Return a pair the first field showing the value number of \p Exp and the
2187/// second field showing whether it is a value number newly created.
2188std::pair<uint32_t, bool>
2189GVNPass::ValueTable::assignExpNewValueNum(Expression &Exp) {
2190 uint32_t &e = expressionNumbering[Exp];
2191 bool CreateNewValNum = !e;
2192 if (CreateNewValNum) {
2193 Expressions.push_back(Exp);
2194 if (ExprIdx.size() < nextValueNumber + 1)
2195 ExprIdx.resize(nextValueNumber * 2);
2196 e = nextValueNumber;
2197 ExprIdx[nextValueNumber++] = nextExprNumber++;
2198 }
2199 return {e, CreateNewValNum};
2200}
2201
2202/// Return whether all the values related with the same \p num are
2203/// defined in \p BB.
2204bool GVNPass::ValueTable::areAllValsInBB(uint32_t Num, const BasicBlock *BB,
2205 GVNPass &Gvn) {
2206 LeaderTableEntry *Vals = &Gvn.LeaderTable[Num];
2207 while (Vals && Vals->BB == BB)
2208 Vals = Vals->Next;
2209 return !Vals;
2210}
2211
2212/// Wrap phiTranslateImpl to provide caching functionality.
2213uint32_t GVNPass::ValueTable::phiTranslate(const BasicBlock *Pred,
2214 const BasicBlock *PhiBlock,
2215 uint32_t Num, GVNPass &Gvn) {
2216 auto FindRes = PhiTranslateTable.find({Num, Pred});
2217 if (FindRes != PhiTranslateTable.end())
2218 return FindRes->second;
2219 uint32_t NewNum = phiTranslateImpl(Pred, PhiBlock, Num, Gvn);
2220 PhiTranslateTable.insert({{Num, Pred}, NewNum});
2221 return NewNum;
2222}
2223
2224// Return true if the value number \p Num and NewNum have equal value.
2225// Return false if the result is unknown.
2226bool GVNPass::ValueTable::areCallValsEqual(uint32_t Num, uint32_t NewNum,
2227 const BasicBlock *Pred,
2228 const BasicBlock *PhiBlock,
2229 GVNPass &Gvn) {
2230 CallInst *Call = nullptr;
2231 LeaderTableEntry *Vals = &Gvn.LeaderTable[Num];
2232 while (Vals) {
2233 Call = dyn_cast<CallInst>(Vals->Val);
2234 if (Call && Call->getParent() == PhiBlock)
2235 break;
2236 Vals = Vals->Next;
2237 }
2238
2239 if (AA->doesNotAccessMemory(Call))
2240 return true;
2241
2242 if (!MD || !AA->onlyReadsMemory(Call))
2243 return false;
2244
2245 MemDepResult local_dep = MD->getDependency(Call);
2246 if (!local_dep.isNonLocal())
2247 return false;
2248
2250 MD->getNonLocalCallDependency(Call);
2251
2252 // Check to see if the Call has no function local clobber.
2253 for (const NonLocalDepEntry &D : deps) {
2254 if (D.getResult().isNonFuncLocal())
2255 return true;
2256 }
2257 return false;
2258}
2259
2260/// Translate value number \p Num using phis, so that it has the values of
2261/// the phis in BB.
2262uint32_t GVNPass::ValueTable::phiTranslateImpl(const BasicBlock *Pred,
2263 const BasicBlock *PhiBlock,
2264 uint32_t Num, GVNPass &Gvn) {
2265 if (PHINode *PN = NumberingPhi[Num]) {
2266 for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) {
2267 if (PN->getParent() == PhiBlock && PN->getIncomingBlock(i) == Pred)
2268 if (uint32_t TransVal = lookup(PN->getIncomingValue(i), false))
2269 return TransVal;
2270 }
2271 return Num;
2272 }
2273
2274 // If there is any value related with Num is defined in a BB other than
2275 // PhiBlock, it cannot depend on a phi in PhiBlock without going through
2276 // a backedge. We can do an early exit in that case to save compile time.
2277 if (!areAllValsInBB(Num, PhiBlock, Gvn))
2278 return Num;
2279
2280 if (Num >= ExprIdx.size() || ExprIdx[Num] == 0)
2281 return Num;
2282 Expression Exp = Expressions[ExprIdx[Num]];
2283
2284 for (unsigned i = 0; i < Exp.varargs.size(); i++) {
2285 // For InsertValue and ExtractValue, some varargs are index numbers
2286 // instead of value numbers. Those index numbers should not be
2287 // translated.
2288 if ((i > 1 && Exp.opcode == Instruction::InsertValue) ||
2289 (i > 0 && Exp.opcode == Instruction::ExtractValue) ||
2290 (i > 1 && Exp.opcode == Instruction::ShuffleVector))
2291 continue;
2292 Exp.varargs[i] = phiTranslate(Pred, PhiBlock, Exp.varargs[i], Gvn);
2293 }
2294
2295 if (Exp.commutative) {
2296 assert(Exp.varargs.size() >= 2 && "Unsupported commutative instruction!");
2297 if (Exp.varargs[0] > Exp.varargs[1]) {
2298 std::swap(Exp.varargs[0], Exp.varargs[1]);
2299 uint32_t Opcode = Exp.opcode >> 8;
2300 if (Opcode == Instruction::ICmp || Opcode == Instruction::FCmp)
2301 Exp.opcode = (Opcode << 8) |
2303 static_cast<CmpInst::Predicate>(Exp.opcode & 255));
2304 }
2305 }
2306
2307 if (uint32_t NewNum = expressionNumbering[Exp]) {
2308 if (Exp.opcode == Instruction::Call && NewNum != Num)
2309 return areCallValsEqual(Num, NewNum, Pred, PhiBlock, Gvn) ? NewNum : Num;
2310 return NewNum;
2311 }
2312 return Num;
2313}
2314
2315/// Erase stale entry from phiTranslate cache so phiTranslate can be computed
2316/// again.
2317void GVNPass::ValueTable::eraseTranslateCacheEntry(
2318 uint32_t Num, const BasicBlock &CurrBlock) {
2319 for (const BasicBlock *Pred : predecessors(&CurrBlock))
2320 PhiTranslateTable.erase({Num, Pred});
2321}
2322
2323// In order to find a leader for a given value number at a
2324// specific basic block, we first obtain the list of all Values for that number,
2325// and then scan the list to find one whose block dominates the block in
2326// question. This is fast because dominator tree queries consist of only
2327// a few comparisons of DFS numbers.
2328Value *GVNPass::findLeader(const BasicBlock *BB, uint32_t num) {
2329 LeaderTableEntry Vals = LeaderTable[num];
2330 if (!Vals.Val) return nullptr;
2331
2332 Value *Val = nullptr;
2333 if (DT->dominates(Vals.BB, BB)) {
2334 Val = Vals.Val;
2335 if (isa<Constant>(Val)) return Val;
2336 }
2337
2338 LeaderTableEntry* Next = Vals.Next;
2339 while (Next) {
2340 if (DT->dominates(Next->BB, BB)) {
2341 if (isa<Constant>(Next->Val)) return Next->Val;
2342 if (!Val) Val = Next->Val;
2343 }
2344
2345 Next = Next->Next;
2346 }
2347
2348 return Val;
2349}
2350
2351/// There is an edge from 'Src' to 'Dst'. Return
2352/// true if every path from the entry block to 'Dst' passes via this edge. In
2353/// particular 'Dst' must not be reachable via another edge from 'Src'.
2355 DominatorTree *DT) {
2356 // While in theory it is interesting to consider the case in which Dst has
2357 // more than one predecessor, because Dst might be part of a loop which is
2358 // only reachable from Src, in practice it is pointless since at the time
2359 // GVN runs all such loops have preheaders, which means that Dst will have
2360 // been changed to have only one predecessor, namely Src.
2361 const BasicBlock *Pred = E.getEnd()->getSinglePredecessor();
2362 assert((!Pred || Pred == E.getStart()) &&
2363 "No edge between these basic blocks!");
2364 return Pred != nullptr;
2365}
2366
2367void GVNPass::assignBlockRPONumber(Function &F) {
2368 BlockRPONumber.clear();
2369 uint32_t NextBlockNumber = 1;
2371 for (BasicBlock *BB : RPOT)
2372 BlockRPONumber[BB] = NextBlockNumber++;
2373 InvalidBlockRPONumbers = false;
2374}
2375
2376bool GVNPass::replaceOperandsForInBlockEquality(Instruction *Instr) const {
2377 bool Changed = false;
2378 for (unsigned OpNum = 0; OpNum < Instr->getNumOperands(); ++OpNum) {
2379 Value *Operand = Instr->getOperand(OpNum);
2380 auto it = ReplaceOperandsWithMap.find(Operand);
2381 if (it != ReplaceOperandsWithMap.end()) {
2382 LLVM_DEBUG(dbgs() << "GVN replacing: " << *Operand << " with "
2383 << *it->second << " in instruction " << *Instr << '\n');
2384 Instr->setOperand(OpNum, it->second);
2385 Changed = true;
2386 }
2387 }
2388 return Changed;
2389}
2390
2391/// The given values are known to be equal in every block
2392/// dominated by 'Root'. Exploit this, for example by replacing 'LHS' with
2393/// 'RHS' everywhere in the scope. Returns whether a change was made.
2394/// If DominatesByEdge is false, then it means that we will propagate the RHS
2395/// value starting from the end of Root.Start.
2396bool GVNPass::propagateEquality(Value *LHS, Value *RHS,
2397 const BasicBlockEdge &Root,
2398 bool DominatesByEdge) {
2400 Worklist.push_back(std::make_pair(LHS, RHS));
2401 bool Changed = false;
2402 // For speed, compute a conservative fast approximation to
2403 // DT->dominates(Root, Root.getEnd());
2404 const bool RootDominatesEnd = isOnlyReachableViaThisEdge(Root, DT);
2405
2406 while (!Worklist.empty()) {
2407 std::pair<Value*, Value*> Item = Worklist.pop_back_val();
2408 LHS = Item.first; RHS = Item.second;
2409
2410 if (LHS == RHS)
2411 continue;
2412 assert(LHS->getType() == RHS->getType() && "Equality but unequal types!");
2413
2414 // Don't try to propagate equalities between constants.
2415 if (isa<Constant>(LHS) && isa<Constant>(RHS))
2416 continue;
2417
2418 // Prefer a constant on the right-hand side, or an Argument if no constants.
2419 if (isa<Constant>(LHS) || (isa<Argument>(LHS) && !isa<Constant>(RHS)))
2420 std::swap(LHS, RHS);
2421 assert((isa<Argument>(LHS) || isa<Instruction>(LHS)) && "Unexpected value!");
2422
2423 // If there is no obvious reason to prefer the left-hand side over the
2424 // right-hand side, ensure the longest lived term is on the right-hand side,
2425 // so the shortest lived term will be replaced by the longest lived.
2426 // This tends to expose more simplifications.
2427 uint32_t LVN = VN.lookupOrAdd(LHS);
2428 if ((isa<Argument>(LHS) && isa<Argument>(RHS)) ||
2429 (isa<Instruction>(LHS) && isa<Instruction>(RHS))) {
2430 // Move the 'oldest' value to the right-hand side, using the value number
2431 // as a proxy for age.
2432 uint32_t RVN = VN.lookupOrAdd(RHS);
2433 if (LVN < RVN) {
2434 std::swap(LHS, RHS);
2435 LVN = RVN;
2436 }
2437 }
2438
2439 // If value numbering later sees that an instruction in the scope is equal
2440 // to 'LHS' then ensure it will be turned into 'RHS'. In order to preserve
2441 // the invariant that instructions only occur in the leader table for their
2442 // own value number (this is used by removeFromLeaderTable), do not do this
2443 // if RHS is an instruction (if an instruction in the scope is morphed into
2444 // LHS then it will be turned into RHS by the next GVN iteration anyway, so
2445 // using the leader table is about compiling faster, not optimizing better).
2446 // The leader table only tracks basic blocks, not edges. Only add to if we
2447 // have the simple case where the edge dominates the end.
2448 if (RootDominatesEnd && !isa<Instruction>(RHS))
2449 addToLeaderTable(LVN, RHS, Root.getEnd());
2450
2451 // Replace all occurrences of 'LHS' with 'RHS' everywhere in the scope. As
2452 // LHS always has at least one use that is not dominated by Root, this will
2453 // never do anything if LHS has only one use.
2454 if (!LHS->hasOneUse()) {
2455 unsigned NumReplacements =
2456 DominatesByEdge
2457 ? replaceDominatedUsesWith(LHS, RHS, *DT, Root)
2458 : replaceDominatedUsesWith(LHS, RHS, *DT, Root.getStart());
2459
2460 Changed |= NumReplacements > 0;
2461 NumGVNEqProp += NumReplacements;
2462 // Cached information for anything that uses LHS will be invalid.
2463 if (MD)
2465 }
2466
2467 // Now try to deduce additional equalities from this one. For example, if
2468 // the known equality was "(A != B)" == "false" then it follows that A and B
2469 // are equal in the scope. Only boolean equalities with an explicit true or
2470 // false RHS are currently supported.
2471 if (!RHS->getType()->isIntegerTy(1))
2472 // Not a boolean equality - bail out.
2473 continue;
2474 ConstantInt *CI = dyn_cast<ConstantInt>(RHS);
2475 if (!CI)
2476 // RHS neither 'true' nor 'false' - bail out.
2477 continue;
2478 // Whether RHS equals 'true'. Otherwise it equals 'false'.
2479 bool isKnownTrue = CI->isMinusOne();
2480 bool isKnownFalse = !isKnownTrue;
2481
2482 // If "A && B" is known true then both A and B are known true. If "A || B"
2483 // is known false then both A and B are known false.
2484 Value *A, *B;
2485 if ((isKnownTrue && match(LHS, m_LogicalAnd(m_Value(A), m_Value(B)))) ||
2486 (isKnownFalse && match(LHS, m_LogicalOr(m_Value(A), m_Value(B))))) {
2487 Worklist.push_back(std::make_pair(A, RHS));
2488 Worklist.push_back(std::make_pair(B, RHS));
2489 continue;
2490 }
2491
2492 // If we are propagating an equality like "(A == B)" == "true" then also
2493 // propagate the equality A == B. When propagating a comparison such as
2494 // "(A >= B)" == "true", replace all instances of "A < B" with "false".
2495 if (CmpInst *Cmp = dyn_cast<CmpInst>(LHS)) {
2496 Value *Op0 = Cmp->getOperand(0), *Op1 = Cmp->getOperand(1);
2497
2498 // If "A == B" is known true, or "A != B" is known false, then replace
2499 // A with B everywhere in the scope. For floating point operations, we
2500 // have to be careful since equality does not always imply equivalance.
2501 if ((isKnownTrue && impliesEquivalanceIfTrue(Cmp)) ||
2502 (isKnownFalse && impliesEquivalanceIfFalse(Cmp)))
2503 Worklist.push_back(std::make_pair(Op0, Op1));
2504
2505 // If "A >= B" is known true, replace "A < B" with false everywhere.
2506 CmpInst::Predicate NotPred = Cmp->getInversePredicate();
2507 Constant *NotVal = ConstantInt::get(Cmp->getType(), isKnownFalse);
2508 // Since we don't have the instruction "A < B" immediately to hand, work
2509 // out the value number that it would have and use that to find an
2510 // appropriate instruction (if any).
2511 uint32_t NextNum = VN.getNextUnusedValueNumber();
2512 uint32_t Num = VN.lookupOrAddCmp(Cmp->getOpcode(), NotPred, Op0, Op1);
2513 // If the number we were assigned was brand new then there is no point in
2514 // looking for an instruction realizing it: there cannot be one!
2515 if (Num < NextNum) {
2516 Value *NotCmp = findLeader(Root.getEnd(), Num);
2517 if (NotCmp && isa<Instruction>(NotCmp)) {
2518 unsigned NumReplacements =
2519 DominatesByEdge
2520 ? replaceDominatedUsesWith(NotCmp, NotVal, *DT, Root)
2521 : replaceDominatedUsesWith(NotCmp, NotVal, *DT,
2522 Root.getStart());
2523 Changed |= NumReplacements > 0;
2524 NumGVNEqProp += NumReplacements;
2525 // Cached information for anything that uses NotCmp will be invalid.
2526 if (MD)
2527 MD->invalidateCachedPointerInfo(NotCmp);
2528 }
2529 }
2530 // Ensure that any instruction in scope that gets the "A < B" value number
2531 // is replaced with false.
2532 // The leader table only tracks basic blocks, not edges. Only add to if we
2533 // have the simple case where the edge dominates the end.
2534 if (RootDominatesEnd)
2535 addToLeaderTable(Num, NotVal, Root.getEnd());
2536
2537 continue;
2538 }
2539 }
2540
2541 return Changed;
2542}
2543
2544/// When calculating availability, handle an instruction
2545/// by inserting it into the appropriate sets
2546bool GVNPass::processInstruction(Instruction *I) {
2547 // Ignore dbg info intrinsics.
2548 if (isa<DbgInfoIntrinsic>(I))
2549 return false;
2550
2551 // If the instruction can be easily simplified then do so now in preference
2552 // to value numbering it. Value numbering often exposes redundancies, for
2553 // example if it determines that %y is equal to %x then the instruction
2554 // "%z = and i32 %x, %y" becomes "%z = and i32 %x, %x" which we now simplify.
2555 const DataLayout &DL = I->getModule()->getDataLayout();
2556 if (Value *V = simplifyInstruction(I, {DL, TLI, DT, AC})) {
2557 bool Changed = false;
2558 if (!I->use_empty()) {
2559 // Simplification can cause a special instruction to become not special.
2560 // For example, devirtualization to a willreturn function.
2561 ICF->removeUsersOf(I);
2562 I->replaceAllUsesWith(V);
2563 Changed = true;
2564 }
2565 if (isInstructionTriviallyDead(I, TLI)) {
2567 Changed = true;
2568 }
2569 if (Changed) {
2570 if (MD && V->getType()->isPtrOrPtrVectorTy())
2572 ++NumGVNSimpl;
2573 return true;
2574 }
2575 }
2576
2577 if (auto *Assume = dyn_cast<AssumeInst>(I))
2578 return processAssumeIntrinsic(Assume);
2579
2580 if (LoadInst *Load = dyn_cast<LoadInst>(I)) {
2581 if (processLoad(Load))
2582 return true;
2583
2584 unsigned Num = VN.lookupOrAdd(Load);
2585 addToLeaderTable(Num, Load, Load->getParent());
2586 return false;
2587 }
2588
2589 // For conditional branches, we can perform simple conditional propagation on
2590 // the condition value itself.
2591 if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
2592 if (!BI->isConditional())
2593 return false;
2594
2595 if (isa<Constant>(BI->getCondition()))
2596 return processFoldableCondBr(BI);
2597
2598 Value *BranchCond = BI->getCondition();
2599 BasicBlock *TrueSucc = BI->getSuccessor(0);
2600 BasicBlock *FalseSucc = BI->getSuccessor(1);
2601 // Avoid multiple edges early.
2602 if (TrueSucc == FalseSucc)
2603 return false;
2604
2605 BasicBlock *Parent = BI->getParent();
2606 bool Changed = false;
2607
2609 BasicBlockEdge TrueE(Parent, TrueSucc);
2610 Changed |= propagateEquality(BranchCond, TrueVal, TrueE, true);
2611
2613 BasicBlockEdge FalseE(Parent, FalseSucc);
2614 Changed |= propagateEquality(BranchCond, FalseVal, FalseE, true);
2615
2616 return Changed;
2617 }
2618
2619 // For switches, propagate the case values into the case destinations.
2620 if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
2621 Value *SwitchCond = SI->getCondition();
2622 BasicBlock *Parent = SI->getParent();
2623 bool Changed = false;
2624
2625 // Remember how many outgoing edges there are to every successor.
2627 for (BasicBlock *Succ : successors(Parent))
2628 ++SwitchEdges[Succ];
2629
2630 for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
2631 i != e; ++i) {
2632 BasicBlock *Dst = i->getCaseSuccessor();
2633 // If there is only a single edge, propagate the case value into it.
2634 if (SwitchEdges.lookup(Dst) == 1) {
2635 BasicBlockEdge E(Parent, Dst);
2636 Changed |= propagateEquality(SwitchCond, i->getCaseValue(), E, true);
2637 }
2638 }
2639 return Changed;
2640 }
2641
2642 // Instructions with void type don't return a value, so there's
2643 // no point in trying to find redundancies in them.
2644 if (I->getType()->isVoidTy())
2645 return false;
2646
2647 uint32_t NextNum = VN.getNextUnusedValueNumber();
2648 unsigned Num = VN.lookupOrAdd(I);
2649
2650 // Allocations are always uniquely numbered, so we can save time and memory
2651 // by fast failing them.
2652 if (isa<AllocaInst>(I) || I->isTerminator() || isa<PHINode>(I)) {
2653 addToLeaderTable(Num, I, I->getParent());
2654 return false;
2655 }
2656
2657 // If the number we were assigned was a brand new VN, then we don't
2658 // need to do a lookup to see if the number already exists
2659 // somewhere in the domtree: it can't!
2660 if (Num >= NextNum) {
2661 addToLeaderTable(Num, I, I->getParent());
2662 return false;
2663 }
2664
2665 // Perform fast-path value-number based elimination of values inherited from
2666 // dominators.
2667 Value *Repl = findLeader(I->getParent(), Num);
2668 if (!Repl) {
2669 // Failure, just remember this instance for future use.
2670 addToLeaderTable(Num, I, I->getParent());
2671 return false;
2672 }
2673
2674 if (Repl == I) {
2675 // If I was the result of a shortcut PRE, it might already be in the table
2676 // and the best replacement for itself. Nothing to do.
2677 return false;
2678 }
2679
2680 // Remove it!
2682 if (MD && Repl->getType()->isPtrOrPtrVectorTy())
2685 return true;
2686}
2687
2688/// runOnFunction - This is the main transformation entry point for a function.
2689bool GVNPass::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
2690 const TargetLibraryInfo &RunTLI, AAResults &RunAA,
2692 OptimizationRemarkEmitter *RunORE, MemorySSA *MSSA) {
2693 AC = &RunAC;
2694 DT = &RunDT;
2695 VN.setDomTree(DT);
2696 TLI = &RunTLI;
2697 VN.setAliasAnalysis(&RunAA);
2698 MD = RunMD;
2699 ImplicitControlFlowTracking ImplicitCFT;
2700 ICF = &ImplicitCFT;
2701 this->LI = &LI;
2702 VN.setMemDep(MD);
2703 ORE = RunORE;
2704 InvalidBlockRPONumbers = true;
2705 MemorySSAUpdater Updater(MSSA);
2706 MSSAU = MSSA ? &Updater : nullptr;
2707
2708 bool Changed = false;
2709 bool ShouldContinue = true;
2710
2712 // Merge unconditional branches, allowing PRE to catch more
2713 // optimization opportunities.
2715 bool removedBlock = MergeBlockIntoPredecessor(&BB, &DTU, &LI, MSSAU, MD);
2716 if (removedBlock)
2717 ++NumGVNBlocks;
2718
2719 Changed |= removedBlock;
2720 }
2721 DTU.flush();
2722
2723 unsigned Iteration = 0;
2724 while (ShouldContinue) {
2725 LLVM_DEBUG(dbgs() << "GVN iteration: " << Iteration << "\n");
2726 (void) Iteration;
2727 ShouldContinue = iterateOnFunction(F);
2728 Changed |= ShouldContinue;
2729 ++Iteration;
2730 }
2731
2732 if (isPREEnabled()) {
2733 // Fabricate val-num for dead-code in order to suppress assertion in
2734 // performPRE().
2735 assignValNumForDeadCode();
2736 bool PREChanged = true;
2737 while (PREChanged) {
2738 PREChanged = performPRE(F);
2739 Changed |= PREChanged;
2740 }
2741 }
2742
2743 // FIXME: Should perform GVN again after PRE does something. PRE can move
2744 // computations into blocks where they become fully redundant. Note that
2745 // we can't do this until PRE's critical edge splitting updates memdep.
2746 // Actually, when this happens, we should just fully integrate PRE into GVN.
2747
2748 cleanupGlobalSets();
2749 // Do not cleanup DeadBlocks in cleanupGlobalSets() as it's called for each
2750 // iteration.
2751 DeadBlocks.clear();
2752
2753 if (MSSA && VerifyMemorySSA)
2754 MSSA->verifyMemorySSA();
2755
2756 return Changed;
2757}
2758
2759bool GVNPass::processBlock(BasicBlock *BB) {
2760 // FIXME: Kill off InstrsToErase by doing erasing eagerly in a helper function
2761 // (and incrementing BI before processing an instruction).
2762 assert(InstrsToErase.empty() &&
2763 "We expect InstrsToErase to be empty across iterations");
2764 if (DeadBlocks.count(BB))
2765 return false;
2766
2767 // Clearing map before every BB because it can be used only for single BB.
2768 ReplaceOperandsWithMap.clear();
2769 bool ChangedFunction = false;
2770
2771 // Since we may not have visited the input blocks of the phis, we can't
2772 // use our normal hash approach for phis. Instead, simply look for
2773 // obvious duplicates. The first pass of GVN will tend to create
2774 // identical phis, and the second or later passes can eliminate them.
2775 SmallPtrSet<PHINode *, 8> PHINodesToRemove;
2776 ChangedFunction |= EliminateDuplicatePHINodes(BB, PHINodesToRemove);
2777 for (PHINode *PN : PHINodesToRemove) {
2778 VN.erase(PN);
2779 removeInstruction(PN);
2780 }
2781
2782 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
2783 BI != BE;) {
2784 if (!ReplaceOperandsWithMap.empty())
2785 ChangedFunction |= replaceOperandsForInBlockEquality(&*BI);
2786 ChangedFunction |= processInstruction(&*BI);
2787
2788 if (InstrsToErase.empty()) {
2789 ++BI;
2790 continue;
2791 }
2792
2793 // If we need some instructions deleted, do it now.
2794 NumGVNInstr += InstrsToErase.size();
2795
2796 // Avoid iterator invalidation.
2797 bool AtStart = BI == BB->begin();
2798 if (!AtStart)
2799 --BI;
2800
2801 for (auto *I : InstrsToErase) {
2802 assert(I->getParent() == BB && "Removing instruction from wrong block?");
2803 LLVM_DEBUG(dbgs() << "GVN removed: " << *I << '\n');
2804 salvageKnowledge(I, AC);
2806 removeInstruction(I);
2807 }
2808 InstrsToErase.clear();
2809
2810 if (AtStart)
2811 BI = BB->begin();
2812 else
2813 ++BI;
2814 }
2815
2816 return ChangedFunction;
2817}
2818
2819// Instantiate an expression in a predecessor that lacked it.
2820bool GVNPass::performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
2821 BasicBlock *Curr, unsigned int ValNo) {
2822 // Because we are going top-down through the block, all value numbers
2823 // will be available in the predecessor by the time we need them. Any
2824 // that weren't originally present will have been instantiated earlier
2825 // in this loop.
2826 bool success = true;
2827 for (unsigned i = 0, e = Instr->getNumOperands(); i != e; ++i) {
2828 Value *Op = Instr->getOperand(i);
2829 if (isa<Argument>(Op) || isa<Constant>(Op) || isa<GlobalValue>(Op))
2830 continue;
2831 // This could be a newly inserted instruction, in which case, we won't
2832 // find a value number, and should give up before we hurt ourselves.
2833 // FIXME: Rewrite the infrastructure to let it easier to value number
2834 // and process newly inserted instructions.
2835 if (!VN.exists(Op)) {
2836 success = false;
2837 break;
2838 }
2839 uint32_t TValNo =
2840 VN.phiTranslate(Pred, Curr, VN.lookup(Op), *this);
2841 if (Value *V = findLeader(Pred, TValNo)) {
2842 Instr->setOperand(i, V);
2843 } else {
2844 success = false;
2845 break;
2846 }
2847 }
2848
2849 // Fail out if we encounter an operand that is not available in
2850 // the PRE predecessor. This is typically because of loads which
2851 // are not value numbered precisely.
2852 if (!success)
2853 return false;
2854
2855 Instr->insertBefore(Pred->getTerminator());
2856 Instr->setName(Instr->getName() + ".pre");
2857 Instr->setDebugLoc(Instr->getDebugLoc());
2858
2859 ICF->insertInstructionTo(Instr, Pred);
2860
2861 unsigned Num = VN.lookupOrAdd(Instr);
2862 VN.add(Instr, Num);
2863
2864 // Update the availability map to include the new instruction.
2865 addToLeaderTable(Num, Instr, Pred);
2866 return true;
2867}
2868
2869bool GVNPass::performScalarPRE(Instruction *CurInst) {
2870 if (isa<AllocaInst>(CurInst) || CurInst->isTerminator() ||
2871 isa<PHINode>(CurInst) || CurInst->getType()->isVoidTy() ||
2872 CurInst->mayReadFromMemory() || CurInst->mayHaveSideEffects() ||
2873 isa<DbgInfoIntrinsic>(CurInst))
2874 return false;
2875
2876 // Don't do PRE on compares. The PHI would prevent CodeGenPrepare from
2877 // sinking the compare again, and it would force the code generator to
2878 // move the i1 from processor flags or predicate registers into a general
2879 // purpose register.
2880 if (isa<CmpInst>(CurInst))
2881 return false;
2882
2883 // Don't do PRE on GEPs. The inserted PHI would prevent CodeGenPrepare from
2884 // sinking the addressing mode computation back to its uses. Extending the
2885 // GEP's live range increases the register pressure, and therefore it can
2886 // introduce unnecessary spills.
2887 //
2888 // This doesn't prevent Load PRE. PHI translation will make the GEP available
2889 // to the load by moving it to the predecessor block if necessary.
2890 if (isa<GetElementPtrInst>(CurInst))
2891 return false;
2892
2893 if (auto *CallB = dyn_cast<CallBase>(CurInst)) {
2894 // We don't currently value number ANY inline asm calls.
2895 if (CallB->isInlineAsm())
2896 return false;
2897 }
2898
2899 uint32_t ValNo = VN.lookup(CurInst);
2900
2901 // Look for the predecessors for PRE opportunities. We're
2902 // only trying to solve the basic diamond case, where
2903 // a value is computed in the successor and one predecessor,
2904 // but not the other. We also explicitly disallow cases
2905 // where the successor is its own predecessor, because they're
2906 // more complicated to get right.
2907 unsigned NumWith = 0;
2908 unsigned NumWithout = 0;
2909 BasicBlock *PREPred = nullptr;
2910 BasicBlock *CurrentBlock = CurInst->getParent();
2911
2912 // Update the RPO numbers for this function.
2913 if (InvalidBlockRPONumbers)
2914 assignBlockRPONumber(*CurrentBlock->getParent());
2915
2917 for (BasicBlock *P : predecessors(CurrentBlock)) {
2918 // We're not interested in PRE where blocks with predecessors that are
2919 // not reachable.
2920 if (!DT->isReachableFromEntry(P)) {
2921 NumWithout = 2;
2922 break;
2923 }
2924 // It is not safe to do PRE when P->CurrentBlock is a loop backedge.
2925 assert(BlockRPONumber.count(P) && BlockRPONumber.count(CurrentBlock) &&
2926 "Invalid BlockRPONumber map.");
2927 if (BlockRPONumber[P] >= BlockRPONumber[CurrentBlock]) {
2928 NumWithout = 2;
2929 break;
2930 }
2931
2932 uint32_t TValNo = VN.phiTranslate(P, CurrentBlock, ValNo, *this);
2933 Value *predV = findLeader(P, TValNo);
2934 if (!predV) {
2935 predMap.push_back(std::make_pair(static_cast<Value *>(nullptr), P));
2936 PREPred = P;
2937 ++NumWithout;
2938 } else if (predV == CurInst) {
2939 /* CurInst dominates this predecessor. */
2940 NumWithout = 2;
2941 break;
2942 } else {
2943 predMap.push_back(std::make_pair(predV, P));
2944 ++NumWith;
2945 }
2946 }
2947
2948 // Don't do PRE when it might increase code size, i.e. when
2949 // we would need to insert instructions in more than one pred.
2950 if (NumWithout > 1 || NumWith == 0)
2951 return false;
2952
2953 // We may have a case where all predecessors have the instruction,
2954 // and we just need to insert a phi node. Otherwise, perform
2955 // insertion.
2956 Instruction *PREInstr = nullptr;
2957
2958 if (NumWithout != 0) {
2959 if (!isSafeToSpeculativelyExecute(CurInst)) {
2960 // It is only valid to insert a new instruction if the current instruction
2961 // is always executed. An instruction with implicit control flow could
2962 // prevent us from doing it. If we cannot speculate the execution, then
2963 // PRE should be prohibited.
2964 if (ICF->isDominatedByICFIFromSameBlock(CurInst))
2965 return false;
2966 }
2967
2968 // Don't do PRE across indirect branch.
2969 if (isa<IndirectBrInst>(PREPred->getTerminator()))
2970 return false;
2971
2972 // We can't do PRE safely on a critical edge, so instead we schedule
2973 // the edge to be split and perform the PRE the next time we iterate
2974 // on the function.
2975 unsigned SuccNum = GetSuccessorNumber(PREPred, CurrentBlock);
2976 if (isCriticalEdge(PREPred->getTerminator(), SuccNum)) {
2977 toSplit.push_back(std::make_pair(PREPred->getTerminator(), SuccNum));
2978 return false;
2979 }
2980 // We need to insert somewhere, so let's give it a shot
2981 PREInstr = CurInst->clone();
2982 if (!performScalarPREInsertion(PREInstr, PREPred, CurrentBlock, ValNo)) {
2983 // If we failed insertion, make sure we remove the instruction.
2984#ifndef NDEBUG
2985 verifyRemoved(PREInstr);
2986#endif
2987 PREInstr->deleteValue();
2988 return false;
2989 }
2990 }
2991
2992 // Either we should have filled in the PRE instruction, or we should
2993 // not have needed insertions.
2994 assert(PREInstr != nullptr || NumWithout == 0);
2995
2996 ++NumGVNPRE;
2997
2998 // Create a PHI to make the value available in this block.
2999 PHINode *Phi = PHINode::Create(CurInst->getType(), predMap.size(),
3000 CurInst->getName() + ".pre-phi");
3001 Phi->insertBefore(CurrentBlock->begin());
3002 for (unsigned i = 0, e = predMap.size(); i != e; ++i) {
3003 if (Value *V = predMap[i].first) {
3004 // If we use an existing value in this phi, we have to patch the original
3005 // value because the phi will be used to replace a later value.
3006 patchReplacementInstruction(CurInst, V);
3007 Phi->addIncoming(V, predMap[i].second);
3008 } else
3009 Phi->addIncoming(PREInstr, PREPred);
3010 }
3011
3012 VN.add(Phi, ValNo);
3013 // After creating a new PHI for ValNo, the phi translate result for ValNo will
3014 // be changed, so erase the related stale entries in phi translate cache.
3015 VN.eraseTranslateCacheEntry(ValNo, *CurrentBlock);
3016 addToLeaderTable(ValNo, Phi, CurrentBlock);
3017 Phi->setDebugLoc(CurInst->getDebugLoc());
3018 CurInst->replaceAllUsesWith(Phi);
3019 if (MD && Phi->getType()->isPtrOrPtrVectorTy())
3021 VN.erase(CurInst);
3022 removeFromLeaderTable(ValNo, CurInst, CurrentBlock);
3023
3024 LLVM_DEBUG(dbgs() << "GVN PRE removed: " << *CurInst << '\n');
3025 removeInstruction(CurInst);
3026 ++NumGVNInstr;
3027
3028 return true;
3029}
3030
3031/// Perform a purely local form of PRE that looks for diamond
3032/// control flow patterns and attempts to perform simple PRE at the join point.
3033bool GVNPass::performPRE(Function &F) {
3034 bool Changed = false;
3035 for (BasicBlock *CurrentBlock : depth_first(&F.getEntryBlock())) {
3036 // Nothing to PRE in the entry block.
3037 if (CurrentBlock == &F.getEntryBlock())
3038 continue;
3039
3040 // Don't perform PRE on an EH pad.
3041 if (CurrentBlock->isEHPad())
3042 continue;
3043
3044 for (BasicBlock::iterator BI = CurrentBlock->begin(),
3045 BE = CurrentBlock->end();
3046 BI != BE;) {
3047 Instruction *CurInst = &*BI++;
3048 Changed |= performScalarPRE(CurInst);
3049 }
3050 }
3051
3052 if (splitCriticalEdges())
3053 Changed = true;
3054
3055 return Changed;
3056}
3057
3058/// Split the critical edge connecting the given two blocks, and return
3059/// the block inserted to the critical edge.
3060BasicBlock *GVNPass::splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ) {
3061 // GVN does not require loop-simplify, do not try to preserve it if it is not
3062 // possible.
3064 Pred, Succ,
3065 CriticalEdgeSplittingOptions(DT, LI, MSSAU).unsetPreserveLoopSimplify());
3066 if (BB) {
3067 if (MD)
3069 InvalidBlockRPONumbers = true;
3070 }
3071 return BB;
3072}
3073
3074/// Split critical edges found during the previous
3075/// iteration that may enable further optimization.
3076bool GVNPass::splitCriticalEdges() {
3077 if (toSplit.empty())
3078 return false;
3079
3080 bool Changed = false;
3081 do {
3082 std::pair<Instruction *, unsigned> Edge = toSplit.pop_back_val();
3083 Changed |= SplitCriticalEdge(Edge.first, Edge.second,
3084 CriticalEdgeSplittingOptions(DT, LI, MSSAU)) !=
3085 nullptr;
3086 } while (!toSplit.empty());
3087 if (Changed) {
3088 if (MD)
3090 InvalidBlockRPONumbers = true;
3091 }
3092 return Changed;
3093}
3094
3095/// Executes one iteration of GVN
3096bool GVNPass::iterateOnFunction(Function &F) {
3097 cleanupGlobalSets();
3098
3099 // Top-down walk of the dominator tree
3100 bool Changed = false;
3101 // Needed for value numbering with phi construction to work.
3102 // RPOT walks the graph in its constructor and will not be invalidated during
3103 // processBlock.
3105
3106 for (BasicBlock *BB : RPOT)
3107 Changed |= processBlock(BB);
3108
3109 return Changed;
3110}
3111
3112void GVNPass::cleanupGlobalSets() {
3113 VN.clear();
3114 LeaderTable.clear();
3115 BlockRPONumber.clear();
3116 TableAllocator.Reset();
3117 ICF->clear();
3118 InvalidBlockRPONumbers = true;
3119}
3120
3121void GVNPass::removeInstruction(Instruction *I) {
3122 if (MD) MD->removeInstruction(I);
3123 if (MSSAU)
3124 MSSAU->removeMemoryAccess(I);
3125#ifndef NDEBUG
3126 verifyRemoved(I);
3127#endif
3128 ICF->removeInstruction(I);
3129 I->eraseFromParent();
3130}
3131
3132/// Verify that the specified instruction does not occur in our
3133/// internal data structures.
3134void GVNPass::verifyRemoved(const Instruction *Inst) const {
3135 VN.verifyRemoved(Inst);
3136
3137 // Walk through the value number scope to make sure the instruction isn't
3138 // ferreted away in it.
3139 for (const auto &I : LeaderTable) {
3140 const LeaderTableEntry *Node = &I.second;
3141 assert(Node->Val != Inst && "Inst still in value numbering scope!");
3142
3143 while (Node->Next) {
3144 Node = Node->Next;
3145 assert(Node->Val != Inst && "Inst still in value numbering scope!");
3146 }
3147 }
3148}
3149
3150/// BB is declared dead, which implied other blocks become dead as well. This
3151/// function is to add all these blocks to "DeadBlocks". For the dead blocks'
3152/// live successors, update their phi nodes by replacing the operands
3153/// corresponding to dead blocks with UndefVal.
3154void GVNPass::addDeadBlock(BasicBlock *BB) {
3157
3158 NewDead.push_back(BB);
3159 while (!NewDead.empty()) {
3160 BasicBlock *D = NewDead.pop_back_val();
3161 if (DeadBlocks.count(D))
3162 continue;
3163
3164 // All blocks dominated by D are dead.
3166 DT->getDescendants(D, Dom);
3167 DeadBlocks.insert(Dom.begin(), Dom.end());
3168
3169 // Figure out the dominance-frontier(D).
3170 for (BasicBlock *B : Dom) {
3171 for (BasicBlock *S : successors(B)) {
3172 if (DeadBlocks.count(S))
3173 continue;
3174
3175 bool AllPredDead = true;
3176 for (BasicBlock *P : predecessors(S))
3177 if (!DeadBlocks.count(P)) {
3178 AllPredDead = false;
3179 break;
3180 }
3181
3182 if (!AllPredDead) {
3183 // S could be proved dead later on. That is why we don't update phi
3184 // operands at this moment.
3185 DF.insert(S);
3186 } else {
3187 // While S is not dominated by D, it is dead by now. This could take
3188 // place if S already have a dead predecessor before D is declared
3189 // dead.
3190 NewDead.push_back(S);
3191 }
3192 }
3193 }
3194 }
3195
3196 // For the dead blocks' live successors, update their phi nodes by replacing
3197 // the operands corresponding to dead blocks with UndefVal.
3198 for (BasicBlock *B : DF) {
3199 if (DeadBlocks.count(B))
3200 continue;
3201
3202 // First, split the critical edges. This might also create additional blocks
3203 // to preserve LoopSimplify form and adjust edges accordingly.
3205 for (BasicBlock *P : Preds) {
3206 if (!DeadBlocks.count(P))
3207 continue;
3208
3210 isCriticalEdge(P->getTerminator(), B)) {
3211 if (BasicBlock *S = splitCriticalEdges(P, B))
3212 DeadBlocks.insert(P = S);
3213 }
3214 }
3215
3216 // Now poison the incoming values from the dead predecessors.
3217 for (BasicBlock *P : predecessors(B)) {
3218 if (!DeadBlocks.count(P))
3219 continue;
3220 for (PHINode &Phi : B->phis()) {
3221 Phi.setIncomingValueForBlock(P, PoisonValue::get(Phi.getType()));
3222 if (MD)
3224 }
3225 }
3226 }
3227}
3228
3229// If the given branch is recognized as a foldable branch (i.e. conditional
3230// branch with constant condition), it will perform following analyses and
3231// transformation.
3232// 1) If the dead out-coming edge is a critical-edge, split it. Let
3233// R be the target of the dead out-coming edge.
3234// 1) Identify the set of dead blocks implied by the branch's dead outcoming
3235// edge. The result of this step will be {X| X is dominated by R}
3236// 2) Identify those blocks which haves at least one dead predecessor. The
3237// result of this step will be dominance-frontier(R).
3238// 3) Update the PHIs in DF(R) by replacing the operands corresponding to
3239// dead blocks with "UndefVal" in an hope these PHIs will optimized away.
3240//
3241// Return true iff *NEW* dead code are found.
3242bool GVNPass::processFoldableCondBr(BranchInst *BI) {
3243 if (!BI || BI->isUnconditional())
3244 return false;
3245
3246 // If a branch has two identical successors, we cannot declare either dead.
3247 if (BI->getSuccessor(0) == BI->getSuccessor(1))
3248 return false;
3249
3250 ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
3251 if (!Cond)
3252 return false;
3253
3254 BasicBlock *DeadRoot =
3255 Cond->getZExtValue() ? BI->getSuccessor(1) : BI->getSuccessor(0);
3256 if (DeadBlocks.count(DeadRoot))
3257 return false;
3258
3259 if (!DeadRoot->getSinglePredecessor())
3260 DeadRoot = splitCriticalEdges(BI->getParent(), DeadRoot);
3261
3262 addDeadBlock(DeadRoot);
3263 return true;
3264}
3265
3266// performPRE() will trigger assert if it comes across an instruction without
3267// associated val-num. As it normally has far more live instructions than dead
3268// instructions, it makes more sense just to "fabricate" a val-number for the
3269// dead code than checking if instruction involved is dead or not.
3270void GVNPass::assignValNumForDeadCode() {
3271 for (BasicBlock *BB : DeadBlocks) {
3272 for (Instruction &Inst : *BB) {
3273 unsigned ValNum = VN.lookupOrAdd(&Inst);
3274 addToLeaderTable(ValNum, &Inst, BB);
3275 }
3276 }
3277}
3278
3280public:
3281 static char ID; // Pass identification, replacement for typeid
3282
3283 explicit GVNLegacyPass(bool NoMemDepAnalysis = !GVNEnableMemDep)
3284 : FunctionPass(ID), Impl(GVNOptions().setMemDep(!NoMemDepAnalysis)) {
3286 }
3287
3288 bool runOnFunction(Function &F) override {
3289 if (skipFunction(F))
3290 return false;
3291
3292 auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
3293 return Impl.runImpl(
3294 F, getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F),
3295 getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
3296 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F),
3297 getAnalysis<AAResultsWrapperPass>().getAAResults(),
3298 Impl.isMemDepEnabled()
3299 ? &getAnalysis<MemoryDependenceWrapperPass>().getMemDep()
3300 : nullptr,
3301 getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
3302 &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(),
3303 MSSAWP ? &MSSAWP->getMSSA() : nullptr);
3304 }
3305
3306 void getAnalysisUsage(AnalysisUsage &AU) const override {
3311 if (Impl.isMemDepEnabled())
3320 }
3321
3322private:
3323 GVNPass Impl;
3324};
3325
3326char GVNLegacyPass::ID = 0;
3327
3328INITIALIZE_PASS_BEGIN(GVNLegacyPass, "gvn", "Global Value Numbering", false, false)
3337
3338// The public interface to this file...
3339FunctionPass *llvm::createGVNPass(bool NoMemDepAnalysis) {
3340 return new GVNLegacyPass(NoMemDepAnalysis);
3341}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file contains the simple types necessary to represent the attributes associated with functions a...
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:529
This file contains the declarations for the subclasses of Constant, which represent the different fla...
#define LLVM_DEBUG(X)
Definition: Debug.h:101
static RegisterPass< DebugifyFunctionPass > DF("debugify-function", "Attach debug info to a function")
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
static bool hasUsersIn(Value *V, BasicBlock *BB)
Definition: GVN.cpp:1981
static void reportMayClobberedLoad(LoadInst *Load, MemDepResult DepInfo, DominatorTree *DT, OptimizationRemarkEmitter *ORE)
Try to locate the three instruction involved in a missed load-elimination case that is due to an inte...
Definition: GVN.cpp:1087
static void reportLoadElim(LoadInst *Load, Value *AvailableValue, OptimizationRemarkEmitter *ORE)
Definition: GVN.cpp:1824
static cl::opt< uint32_t > MaxNumInsnsPerBlock("gvn-max-num-insns", cl::Hidden, cl::init(100), cl::desc("Max number of instructions to scan in each basic block in GVN " "(default = 100)"))
static cl::opt< bool > GVNEnableMemDep("enable-gvn-memdep", cl::init(true))
static cl::opt< bool > GVNEnableLoadInLoopPRE("enable-load-in-loop-pre", cl::init(true))
static cl::opt< uint32_t > MaxNumDeps("gvn-max-num-deps", cl::Hidden, cl::init(100), cl::desc("Max number of dependences to attempt Load PRE (default = 100)"))
static Value * ConstructSSAForLoadSet(LoadInst *Load, SmallVectorImpl< AvailableValueInBlock > &ValuesPerBlock, GVNPass &gvn)
Given a set of loads specified by ValuesPerBlock, construct SSA form, allowing us to eliminate Load.
Definition: GVN.cpp:963
static bool isOnlyReachableViaThisEdge(const BasicBlockEdge &E, DominatorTree *DT)
There is an edge from 'Src' to 'Dst'.
Definition: GVN.cpp:2354
static bool impliesEquivalanceIfFalse(CmpInst *Cmp)
Definition: GVN.cpp:1954
static bool IsValueFullyAvailableInBlock(BasicBlock *BB, DenseMap< BasicBlock *, AvailabilityState > &FullyAvailableBlocks)
Return true if we can prove that the value we're analyzing is fully available in the specified block.
Definition: GVN.cpp:828
static Value * findDominatingValue(const MemoryLocation &Loc, Type *LoadTy, Instruction *From, AAResults *AA)
Definition: GVN.cpp:1149
static bool isLifetimeStart(const Instruction *Inst)
Definition: GVN.cpp:1068
static cl::opt< bool > GVNEnableSplitBackedgeInLoadPRE("enable-split-backedge-in-load-pre", cl::init(false))
static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl)
Definition: GVN.cpp:2128
static void replaceValuesPerBlockEntry(SmallVectorImpl< AvailableValueInBlock > &ValuesPerBlock, Value *OldValue, Value *NewValue)
If the specified OldValue exists in ValuesPerBlock, replace its value with NewValue.
Definition: GVN.cpp:944
static bool impliesEquivalanceIfTrue(CmpInst *Cmp)
Definition: GVN.cpp:1928
AvailabilityState
Definition: GVN.cpp:808
@ Unavailable
We know the block is not fully available. This is a fixpoint.
@ Available
We know the block is fully available. This is a fixpoint.
@ SpeculativelyAvailable
We do not know whether the block is fully available or not, but we are currently speculating that it ...
static cl::opt< bool > GVNEnablePRE("enable-pre", cl::init(true), cl::Hidden)
static cl::opt< uint32_t > MaxNumVisitedInsts("gvn-max-num-visited-insts", cl::Hidden, cl::init(100), cl::desc("Max number of visited instructions when trying to find " "dominating value of select dependency (default = 100)"))
static cl::opt< uint32_t > MaxBBSpeculations("gvn-max-block-speculations", cl::Hidden, cl::init(600), cl::desc("Max number of blocks we're willing to speculate on (and recurse " "into) when deducing if a value is fully available or not in GVN " "(default = 600)"))
static bool liesBetween(const Instruction *From, Instruction *Between, const Instruction *To, DominatorTree *DT)
Assuming To can be reached from both From and Between, does Between lie on every path from From to To...
Definition: GVN.cpp:1076
static cl::opt< bool > GVNEnableLoadPRE("enable-load-pre", cl::init(true))
This file provides the interface for LLVM's Global Value Numbering pass which eliminates fully redund...
#define DEBUG_TYPE
This is the interface for a simple mod/ref and alias analysis over globals.
Hexagon Common GEP
IRTranslator LLVM IR MI
static bool lookup(const GsymReader &GR, DataExtractor &Data, uint64_t &Offset, uint64_t BaseAddr, uint64_t Addr, SourceLocations &SrcLocs, llvm::Error &Err)
A Lookup helper functions.
Definition: InlineInfo.cpp:109
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:531
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file implements a map that provides insertion order iteration.
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
This file contains the declarations for metadata subclasses.
Module.h This file contains the declarations for the Module class.
LLVMContext & Context
#define P(N)
ppc ctr loops PowerPC CTR Loops Verify
This header defines various interfaces for pass management in LLVM.
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
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
This defines the Use class.
Value * RHS
Value * LHS
static const uint32_t IV[8]
Definition: blake3_impl.h:78
A manager for alias analyses.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Class for arbitrary precision integers.
Definition: APInt.h:76
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:321
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:492
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:473
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
iterator end() const
Definition: ArrayRef.h:154
iterator begin() const
Definition: ArrayRef.h:153
This represents the llvm.assume intrinsic.
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
const BasicBlock * getEnd() const
Definition: Dominators.h:112
const BasicBlock * getStart() const
Definition: Dominators.h:108
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
iterator end()
Definition: BasicBlock.h:443
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:430
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:360
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:452
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:206
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:165
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:168
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:657
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:221
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
Value * getRHS() const
Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
Value * getLHS() const
Conditional or Unconditional Branch instruction.
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
Value * getCondition() const
void Reset()
Deallocate all but the current slab and reset the current pointer to the beginning of it,...
Definition: Allocator.h:123
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1660
unsigned arg_size() const
Definition: InstrTypes.h:1658
This class represents a function call, abstracting a target machine's calling convention.
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:956
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1335
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:966
@ FCMP_OEQ
0 0 0 1 True if ordered and equal
Definition: InstrTypes.h:969
@ FCMP_ONE
0 1 1 0 True if ordered and operands are unequal
Definition: InstrTypes.h:974
@ FCMP_UEQ
1 0 0 1 True if unordered or equal
Definition: InstrTypes.h:977
@ ICMP_EQ
equal
Definition: InstrTypes.h:987
@ ICMP_NE
not equal
Definition: InstrTypes.h:988
@ FCMP_UNE
1 1 1 0 True if unordered or not equal
Definition: InstrTypes.h:982
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:1140
This is the shared class of boolean and integer constants.
Definition: Constants.h:80
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
Definition: Constants.h:217
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:849
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:856
This is an important base class in LLVM.
Definition: Constant.h:41
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:370
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:202
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
Definition: DenseMap.h:235
iterator end()
Definition: DenseMap.h:84
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
void getDescendants(NodeT *R, SmallVectorImpl< NodeT * > &Result) const
Get all nodes dominated by R, including R itself.
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:317
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:321
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
Class representing an expression and its matching format.
This instruction extracts a struct member or array element value from an aggregate value.
unsigned getNumIndices() const
iterator_range< idx_iterator > indices() const
idx_iterator idx_begin() const
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
Represents calls to the gc.relocate intrinsic.
This class holds the mapping between values and value numbers.
Definition: GVN.h:151
uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred, Value *LHS, Value *RHS)
Returns the value number of the given comparison, assigning it a new number if it did not have one be...
Definition: GVN.cpp:692
uint32_t getNextUnusedValueNumber()
Definition: GVN.h:213
uint32_t lookupOrAdd(Value *V)
lookup_or_add - Returns the value number for the specified value, assigning it a new number if it did...
Definition: GVN.cpp:600
uint32_t lookup(Value *V, bool Verify=true) const
Returns the value number of the specified value.
Definition: GVN.cpp:679
void setAliasAnalysis(AAResults *A)
Definition: GVN.h:209
void clear()
Remove all entries from the ValueTable.
Definition: GVN.cpp:700
bool exists(Value *V) const
Returns true if a value number exists for the specified value.
Definition: GVN.cpp:594
uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock, uint32_t Num, GVNPass &Gvn)
Wrap phiTranslateImpl to provide caching functionality.
Definition: GVN.cpp:2213
void setMemDep(MemoryDependenceResults *M)
Definition: GVN.h:211
void erase(Value *v)
Remove a value from the value numbering.
Definition: GVN.cpp:712
void add(Value *V, uint32_t num)
add - Insert a value into the table with a specified value number.
Definition: GVN.cpp:463
void setDomTree(DominatorTree *D)
Definition: GVN.h:212
void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock)
Erase stale entry from phiTranslate cache so phiTranslate can be computed again.
Definition: GVN.cpp:2317
void verifyRemoved(const Value *) const
verifyRemoved - Verify that the value is removed from all internal data structures.
Definition: GVN.cpp:722
The core GVN pass object.
Definition: GVN.h:117
friend class gvn::GVNLegacyPass
Definition: GVN.h:218
bool isPREEnabled() const
Definition: GVN.cpp:731
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: GVN.cpp:752
AAResults * getAliasAnalysis() const
Definition: GVN.h:139
bool isLoadPREEnabled() const
Definition: GVN.cpp:735
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: GVN.cpp:779
DominatorTree & getDominatorTree() const
Definition: GVN.h:138
bool isLoadInLoopPREEnabled() const
Definition: GVN.cpp:739
bool isLoadPRESplitBackedgeEnabled() const
Definition: GVN.cpp:743
void markInstructionForDeletion(Instruction *I)
This removes the specified instruction from our various maps and marks it for deletion.
Definition: GVN.h:133
bool isMemDepEnabled() const
Definition: GVN.cpp:748
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:973
Legacy wrapper pass to provide the GlobalsAAResult object.
This class allows to keep track on instructions with implicit control flow.
bool isDominatedByICFIFromSameBlock(const Instruction *Insn)
Returns true if the first ICFI of Insn's block exists and dominates Insn.
bool hasICF(const BasicBlock *BB)
Returns true if at least one instruction from the given basic block has implicit control flow.
void clear()
Invalidates all information from this tracking.
void removeUsersOf(const Instruction *Inst)
Notifies this tracking that we are going to replace all uses of Inst.
void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB)
Notifies this tracking that we are going to insert a new instruction Inst to the basic block BB.
void removeInstruction(const Instruction *Inst)
Notifies this tracking that we are going to remove the instruction Inst It makes all necessary update...
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:454
bool hasMetadata() const
Return true if this instruction has any metadata attached to it.
Definition: Instruction.h:341
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:802
const BasicBlock * getParent() const
Definition: Instruction.h:152
bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
Definition: Instruction.h:255
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.
Definition: Instruction.h:252
void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs)
Drop all unknown metadata except for debug locations.
Definition: Metadata.cpp:1590
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
An instruction for reading from memory.
Definition: Instructions.h:184
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:566
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:593
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:36
iterator end()
Definition: MapVector.h:71
iterator find(const KeyT &Key)
Definition: MapVector.h:167
size_type size() const
Definition: MapVector.h:60
A memory dependence query can return one of three different answers.
bool isClobber() const
Tests if this MemDepResult represents a query that is an instruction clobber dependency.
bool isNonLocal() const
Tests if this MemDepResult represents a query that is transparent to the start of the block,...
bool isDef() const
Tests if this MemDepResult represents a query that is an instruction definition dependency.
bool isLocal() const
Tests if this MemDepResult represents a valid local query (Clobber/Def).
Instruction * getInst() const
If this is a normal dependency, returns the instruction that is depended on.
This is the common base class for memset/memcpy/memmove.
An analysis that produces MemoryDependenceResults for a function.
Provides a lazy, caching interface for making common memory aliasing information queries,...
std::vector< NonLocalDepEntry > NonLocalDepInfo
void invalidateCachedPredecessors()
Clears the PredIteratorCache info.
void invalidateCachedPointerInfo(Value *Ptr)
Invalidates cached information about the specified pointer, because it may be too conservative in mem...
std::optional< int32_t > getClobberOffset(LoadInst *DepInst) const
Return the clobber offset to dependent instruction.
void removeInstruction(Instruction *InstToRemove)
Removes an instruction from the dependence analysis, updating the dependence of instructions that pre...
MemDepResult getDependency(Instruction *QueryInst)
Returns the instruction on which a memory operation depends.
const NonLocalDepInfo & getNonLocalCallDependency(CallBase *QueryCall)
Perform a full dependency query for the specified call, returning the set of blocks that the value is...
void getNonLocalPointerDependency(Instruction *QueryInst, SmallVectorImpl< NonLocalDepResult > &Result)
Perform a full dependency query for an access to the QueryInst's specified memory location,...
A wrapper analysis pass for the legacy pass manager that exposes a MemoryDepnedenceResults instance.
Representation for a specific memory location.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
const Value * Ptr
The address of the start of the location.
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:923
MemorySSA * getMemorySSA() const
Get handle on MemorySSA.
MemoryUseOrDef * createMemoryAccessBefore(Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt)
Create a MemoryAccess in MemorySSA before an existing MemoryAccess.
void insertDef(MemoryDef *Def, bool RenameUses=false)
Insert a definition into the MemorySSA IR.
MemoryAccess * createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, const BasicBlock *BB, MemorySSA::InsertionPlace Point)
Create a MemoryAccess in MemorySSA at a specified point in a block.
void insertUse(MemoryUse *Use, bool RenameUses=false)
void removeMemoryAccess(MemoryAccess *, bool OptimizePhis=false)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:980
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
const AccessList * getBlockAccesses(const BasicBlock *BB) const
Return the list of MemoryAccess's for a given basic block.
Definition: MemorySSA.h:757
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1861
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:252
This is an entry in the NonLocalDepInfo cache.
OptimizationRemarkEmitter legacy analysis pass.
The optimization diagnostic interface.
bool allowExtraAnalysis(StringRef PassName) const
Whether we allow for extra compile-time budget to perform more analysis to produce fewer false positi...
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
Diagnostic information for missed-optimization remarks.
Diagnostic information for applied optimization remarks.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr, BasicBlock::iterator InsertBefore)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
PHITransAddr - An address value which tracks and handles phi translation.
Definition: PHITransAddr.h:35
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
static PointerType * get(Type *ElementType, unsigned AddressSpace)
This constructs a pointer to an object of the specified type in a numbered address space.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1827
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
void preserve()
Mark an analysis as preserved.
Definition: Analysis.h:129
Helper class for SSA formation on a set of values defined in multiple blocks.
Definition: SSAUpdater.h:40
void Initialize(Type *Ty, StringRef Name)
Reset this object to get ready for a new set of SSA updates with type 'Ty'.
Definition: SSAUpdater.cpp:53
Value * GetValueInMiddleOfBlock(BasicBlock *BB)
Construct SSA form, materializing a value that is live in the middle of the specified block.
Definition: SSAUpdater.cpp:98
bool HasValueForBlock(BasicBlock *BB) const
Return true if the SSAUpdater already has a value for the specified block.
Definition: SSAUpdater.cpp:62
void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
Definition: SSAUpdater.cpp:70
This class represents the LLVM 'select' instruction.
const Value * getCondition() const
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr, BasicBlock::iterator InsertBefore, Instruction *MDFrom=nullptr)
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
bool empty() const
Definition: SmallSet.h:159
bool erase(const T &V)
Definition: SmallSet.h:207
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:179
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:950
iterator erase(const_iterator CI)
Definition: SmallVector.h:750
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:696
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:818
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
SmallVector & operator=(const SmallVector &RHS)
Definition: SmallVector.h:1254
An instruction for storing to memory.
Definition: Instructions.h:317
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
Multiway switch.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
static IntegerType * getInt8Ty(LLVMContext &C)
bool isPtrOrPtrVectorTy() const
Return true if this is a pointer type or a vector of pointer types.
Definition: Type.h:262
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:228
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:140
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1808
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
op_range operands()
Definition: User.h:242
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:534
bool canBeFreed() const
Return true if the memory object referred to by V can by freed in the scope for which the SSA value d...
Definition: Value.cpp:789
void deleteValue()
Delete a pointer to a generic Value.
Definition: Value.cpp:110
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
Represents an op.with.overflow intrinsic.
An efficient, type-erasing, non-owning reference to a callable.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: GVN.cpp:3306
GVNLegacyPass(bool NoMemDepAnalysis=!GVNEnableMemDep)
Definition: GVN.cpp:3283
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: GVN.cpp:3288
An opaque object representing a hash code.
Definition: Hashing.h:74
self_iterator getIterator()
Definition: ilist_node.h:109
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:92
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
Value * getValueForLoad(Value *SrcVal, unsigned Offset, Type *LoadTy, Instruction *InsertPt, const DataLayout &DL)
If analyzeLoadFromClobberingStore/Load returned an offset, this function can be used to actually perf...
Definition: VNCoercion.cpp:335
int analyzeLoadFromClobberingStore(Type *LoadTy, Value *LoadPtr, StoreInst *DepSI, const DataLayout &DL)
This function determines whether a value for the pointer LoadPtr can be extracted from the store at D...
Definition: VNCoercion.cpp:211
Value * getMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset, Type *LoadTy, Instruction *InsertPt, const DataLayout &DL)
If analyzeLoadFromClobberingMemInst returned an offset, this function can be used to actually perform...
Definition: VNCoercion.cpp:360
int analyzeLoadFromClobberingLoad(Type *LoadTy, Value *LoadPtr, LoadInst *DepLI, const DataLayout &DL)
This function determines whether a value for the pointer LoadPtr can be extracted from the load at De...
Definition: VNCoercion.cpp:232
int analyzeLoadFromClobberingMemInst(Type *LoadTy, Value *LoadPtr, MemIntrinsic *DepMI, const DataLayout &DL)
This function determines whether a value for the pointer LoadPtr can be extracted from the memory int...
Definition: VNCoercion.cpp:246
bool canCoerceMustAliasedValueToLoad(Value *StoredVal, Type *LoadTy, const DataLayout &DL)
Return true if CoerceAvailableValueToLoadType would succeed if it was called.
Definition: VNCoercion.cpp:18
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
A private "module" namespace for types and utilities used by GVN.
Definition: GVN.h:59
constexpr double e
Definition: MathExtras.h:31
NodeAddr< InstrNode * > Instr
Definition: RDFGraph.h:389
NodeAddr< PhiNode * > Phi
Definition: RDFGraph.h:390
@ FalseVal
Definition: TGLexer.h:59
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
pred_iterator pred_end(BasicBlock *BB)
Definition: CFG.h:114
@ Offset
Definition: DWP.cpp:456
hash_code hash_value(const FixedPointSemantics &Val)
Definition: APFixedPoint.h:128
Constant * getInitialValueOfAllocation(const Value *V, const TargetLibraryInfo *TLI, Type *Ty)
If this is a call to an allocation function that initializes memory to a fixed value,...
unsigned GetSuccessorNumber(const BasicBlock *BB, const BasicBlock *Succ)
Search for the specified successor of basic block BB and return its position in the terminator instru...
Definition: CFG.cpp:79
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:1650
auto successors(const MachineBasicBlock *BB)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition: STLExtras.h:2073
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:656
bool isAssumeWithEmptyBundle(const AssumeInst &Assume)
Return true iff the operand bundles of the provided llvm.assume doesn't contain any valuable informat...
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
void initializeGVNLegacyPassPass(PassRegistry &)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1729
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:399
pred_iterator pred_begin(BasicBlock *BB)
Definition: CFG.h:110
bool isModSet(const ModRefInfo MRI)
Definition: ModRef.h:48
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void patchReplacementInstruction(Instruction *I, Value *Repl)
Patch the replacement so that it is not more restrictive than the value being replaced.
Definition: Local.cpp:3400
unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge)
Replace each use of 'From' with 'To' if that use is dominated by the given edge.
Definition: Local.cpp:3466
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
@ Global
Append to llvm.global_dtors.
void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
Definition: Local.cpp:3327
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:83
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
bool salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
BasicBlock * SplitCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
If this edge is a critical edge, insert a new node to split the critical edge.
FunctionPass * createGVNPass(bool NoMemDepAnalysis=false)
Create a legacy GVN pass.
Definition: GVN.cpp:3339
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
Definition: CFG.cpp:95
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:191
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1879
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:118
iterator_range< df_iterator< T > > depth_first(const T &G)
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:613
bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
Definition: Local.cpp:1486
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:491
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...
Definition: CFG.cpp:231
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:760
Option class for critical edge splitting.
static GVNPass::Expression getTombstoneKey()
Definition: GVN.cpp:170
static bool isEqual(const GVNPass::Expression &LHS, const GVNPass::Expression &RHS)
Definition: GVN.cpp:178
static unsigned getHashValue(const GVNPass::Expression &e)
Definition: GVN.cpp:172
static GVNPass::Expression getEmptyKey()
Definition: GVN.cpp:169
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: DenseMapInfo.h:50
A set of parameters to control various transforms performed by GVN pass.
Definition: GVN.h:74
std::optional< bool > AllowLoadPRESplitBackedge
Definition: GVN.h:78
std::optional< bool > AllowPRE
Definition: GVN.h:75
std::optional< bool > AllowLoadInLoopPRE
Definition: GVN.h:77
std::optional< bool > AllowMemDep
Definition: GVN.h:79
std::optional< bool > AllowLoadPRE
Definition: GVN.h:76
SmallVector< uint32_t, 4 > varargs
Definition: GVN.cpp:143
bool operator==(const Expression &other) const
Definition: GVN.cpp:147
friend hash_code hash_value(const Expression &Value)
Definition: GVN.cpp:159
Expression(uint32_t o=~2U)
Definition: GVN.cpp:145
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:74
Represents an AvailableValue which can be rematerialized at the end of the associated BasicBlock.
Definition: GVN.cpp:287
static AvailableValueInBlock get(BasicBlock *BB, Value *V, unsigned Offset=0)
Definition: GVN.cpp:301
static AvailableValueInBlock getUndef(BasicBlock *BB)
Definition: GVN.cpp:306
static AvailableValueInBlock get(BasicBlock *BB, AvailableValue &&AV)
Definition: GVN.cpp:294
Value * MaterializeAdjustedValue(LoadInst *Load, GVNPass &gvn) const
Emit code at the end of this block to adjust the value defined here to the specified type.
Definition: GVN.cpp:317
AvailableValue AV
AV - The actual available value.
Definition: GVN.cpp:292
static AvailableValueInBlock getSelect(BasicBlock *BB, SelectInst *Sel, Value *V1, Value *V2)
Definition: GVN.cpp:310
BasicBlock * BB
BB - The basic block in question.
Definition: GVN.cpp:289
Represents a particular available value that we know how to materialize.
Definition: GVN.cpp:190
unsigned Offset
Offset - The byte offset in Val that is interesting for the load query.
Definition: GVN.cpp:207
bool isSimpleValue() const
Definition: GVN.cpp:253
static AvailableValue getSelect(SelectInst *Sel, Value *V1, Value *V2)
Definition: GVN.cpp:243
bool isCoercedLoadValue() const
Definition: GVN.cpp:254
static AvailableValue get(Value *V, unsigned Offset=0)
Definition: GVN.cpp:211
ValType Kind
Kind of the live-out value.
Definition: GVN.cpp:204
LoadInst * getCoercedLoadValue() const
Definition: GVN.cpp:264
static AvailableValue getLoad(LoadInst *Load, unsigned Offset=0)
Definition: GVN.cpp:227
static AvailableValue getMI(MemIntrinsic *MI, unsigned Offset=0)
Definition: GVN.cpp:219
bool isUndefValue() const
Definition: GVN.cpp:256
bool isSelectValue() const
Definition: GVN.cpp:257
Value * Val
Val - The value that is live out of the block.
Definition: GVN.cpp:202
Value * V1
V1, V2 - The dominating non-clobbered values of SelectVal.
Definition: GVN.cpp:209
Value * MaterializeAdjustedValue(LoadInst *Load, Instruction *InsertPt, GVNPass &gvn) const
Emit code at the specified insertion point to adjust the value defined here to the specified type.
Definition: GVN.cpp:1006
static AvailableValue getUndef()
Definition: GVN.cpp:235
SelectInst * getSelectValue() const
Definition: GVN.cpp:274
Value * getSimpleValue() const
Definition: GVN.cpp:259
bool isMemIntrinValue() const
Definition: GVN.cpp:255
MemIntrinsic * getMemIntrinValue() const
Definition: GVN.cpp:269