LLVM 18.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) {
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;
460GVNPass::ValueTable::operator=(const GVNPass::ValueTable &Arg) = 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.count(V) != 0;
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.
700void GVNPass::ValueTable::clear() {
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.
712void GVNPass::ValueTable::erase(Value *V) {
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.getCachedResult<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)
775 if (LI)
777 return PA;
778}
779
781 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
782 static_cast<PassInfoMixin<GVNPass> *>(this)->printPipeline(
783 OS, MapClassName2PassName);
784
785 OS << '<';
786 if (Options.AllowPRE != std::nullopt)
787 OS << (*Options.AllowPRE ? "" : "no-") << "pre;";
788 if (Options.AllowLoadPRE != std::nullopt)
789 OS << (*Options.AllowLoadPRE ? "" : "no-") << "load-pre;";
790 if (Options.AllowLoadPRESplitBackedge != std::nullopt)
791 OS << (*Options.AllowLoadPRESplitBackedge ? "" : "no-")
792 << "split-backedge-load-pre;";
793 if (Options.AllowMemDep != std::nullopt)
794 OS << (*Options.AllowMemDep ? "" : "no-") << "memdep";
795 OS << '>';
796}
797
798#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
799LLVM_DUMP_METHOD void GVNPass::dump(DenseMap<uint32_t, Value *> &d) const {
800 errs() << "{\n";
801 for (auto &I : d) {
802 errs() << I.first << "\n";
803 I.second->dump();
804 }
805 errs() << "}\n";
806}
807#endif
808
809enum class AvailabilityState : char {
810 /// We know the block *is not* fully available. This is a fixpoint.
811 Unavailable = 0,
812 /// We know the block *is* fully available. This is a fixpoint.
813 Available = 1,
814 /// We do not know whether the block is fully available or not,
815 /// but we are currently speculating that it will be.
816 /// If it would have turned out that the block was, in fact, not fully
817 /// available, this would have been cleaned up into an Unavailable.
819};
820
821/// Return true if we can prove that the value
822/// we're analyzing is fully available in the specified block. As we go, keep
823/// track of which blocks we know are fully alive in FullyAvailableBlocks. This
824/// map is actually a tri-state map with the following values:
825/// 0) we know the block *is not* fully available.
826/// 1) we know the block *is* fully available.
827/// 2) we do not know whether the block is fully available or not, but we are
828/// currently speculating that it will be.
830 BasicBlock *BB,
831 DenseMap<BasicBlock *, AvailabilityState> &FullyAvailableBlocks) {
833 std::optional<BasicBlock *> UnavailableBB;
834
835 // The number of times we didn't find an entry for a block in a map and
836 // optimistically inserted an entry marking block as speculatively available.
837 unsigned NumNewNewSpeculativelyAvailableBBs = 0;
838
839#ifndef NDEBUG
840 SmallSet<BasicBlock *, 32> NewSpeculativelyAvailableBBs;
842#endif
843
844 Worklist.emplace_back(BB);
845 while (!Worklist.empty()) {
846 BasicBlock *CurrBB = Worklist.pop_back_val(); // LoadFO - depth-first!
847 // Optimistically assume that the block is Speculatively Available and check
848 // to see if we already know about this block in one lookup.
849 std::pair<DenseMap<BasicBlock *, AvailabilityState>::iterator, bool> IV =
850 FullyAvailableBlocks.try_emplace(
851 CurrBB, AvailabilityState::SpeculativelyAvailable);
852 AvailabilityState &State = IV.first->second;
853
854 // Did the entry already exist for this block?
855 if (!IV.second) {
856 if (State == AvailabilityState::Unavailable) {
857 UnavailableBB = CurrBB;
858 break; // Backpropagate unavailability info.
859 }
860
861#ifndef NDEBUG
862 AvailableBBs.emplace_back(CurrBB);
863#endif
864 continue; // Don't recurse further, but continue processing worklist.
865 }
866
867 // No entry found for block.
868 ++NumNewNewSpeculativelyAvailableBBs;
869 bool OutOfBudget = NumNewNewSpeculativelyAvailableBBs > MaxBBSpeculations;
870
871 // If we have exhausted our budget, mark this block as unavailable.
872 // Also, if this block has no predecessors, the value isn't live-in here.
873 if (OutOfBudget || pred_empty(CurrBB)) {
874 MaxBBSpeculationCutoffReachedTimes += (int)OutOfBudget;
875 State = AvailabilityState::Unavailable;
876 UnavailableBB = CurrBB;
877 break; // Backpropagate unavailability info.
878 }
879
880 // Tentatively consider this block as speculatively available.
881#ifndef NDEBUG
882 NewSpeculativelyAvailableBBs.insert(CurrBB);
883#endif
884 // And further recurse into block's predecessors, in depth-first order!
885 Worklist.append(pred_begin(CurrBB), pred_end(CurrBB));
886 }
887
888#if LLVM_ENABLE_STATS
889 IsValueFullyAvailableInBlockNumSpeculationsMax.updateMax(
890 NumNewNewSpeculativelyAvailableBBs);
891#endif
892
893 // If the block isn't marked as fixpoint yet
894 // (the Unavailable and Available states are fixpoints)
895 auto MarkAsFixpointAndEnqueueSuccessors =
896 [&](BasicBlock *BB, AvailabilityState FixpointState) {
897 auto It = FullyAvailableBlocks.find(BB);
898 if (It == FullyAvailableBlocks.end())
899 return; // Never queried this block, leave as-is.
900 switch (AvailabilityState &State = It->second) {
901 case AvailabilityState::Unavailable:
902 case AvailabilityState::Available:
903 return; // Don't backpropagate further, continue processing worklist.
904 case AvailabilityState::SpeculativelyAvailable: // Fix it!
905 State = FixpointState;
906#ifndef NDEBUG
907 assert(NewSpeculativelyAvailableBBs.erase(BB) &&
908 "Found a speculatively available successor leftover?");
909#endif
910 // Queue successors for further processing.
911 Worklist.append(succ_begin(BB), succ_end(BB));
912 return;
913 }
914 };
915
916 if (UnavailableBB) {
917 // Okay, we have encountered an unavailable block.
918 // Mark speculatively available blocks reachable from UnavailableBB as
919 // unavailable as well. Paths are terminated when they reach blocks not in
920 // FullyAvailableBlocks or they are not marked as speculatively available.
921 Worklist.clear();
922 Worklist.append(succ_begin(*UnavailableBB), succ_end(*UnavailableBB));
923 while (!Worklist.empty())
924 MarkAsFixpointAndEnqueueSuccessors(Worklist.pop_back_val(),
925 AvailabilityState::Unavailable);
926 }
927
928#ifndef NDEBUG
929 Worklist.clear();
930 for (BasicBlock *AvailableBB : AvailableBBs)
931 Worklist.append(succ_begin(AvailableBB), succ_end(AvailableBB));
932 while (!Worklist.empty())
933 MarkAsFixpointAndEnqueueSuccessors(Worklist.pop_back_val(),
934 AvailabilityState::Available);
935
936 assert(NewSpeculativelyAvailableBBs.empty() &&
937 "Must have fixed all the new speculatively available blocks.");
938#endif
939
940 return !UnavailableBB;
941}
942
943/// If the specified OldValue exists in ValuesPerBlock, replace its value with
944/// NewValue.
946 SmallVectorImpl<AvailableValueInBlock> &ValuesPerBlock, Value *OldValue,
947 Value *NewValue) {
948 for (AvailableValueInBlock &V : ValuesPerBlock) {
949 if ((V.AV.isSimpleValue() && V.AV.getSimpleValue() == OldValue) ||
950 (V.AV.isCoercedLoadValue() && V.AV.getCoercedLoadValue() == OldValue))
951 V = AvailableValueInBlock::get(V.BB, NewValue);
952 }
953}
954
955/// Given a set of loads specified by ValuesPerBlock,
956/// construct SSA form, allowing us to eliminate Load. This returns the value
957/// that should be used at Load's definition site.
958static Value *
961 GVNPass &gvn) {
962 // Check for the fully redundant, dominating load case. In this case, we can
963 // just use the dominating value directly.
964 if (ValuesPerBlock.size() == 1 &&
965 gvn.getDominatorTree().properlyDominates(ValuesPerBlock[0].BB,
966 Load->getParent())) {
967 assert(!ValuesPerBlock[0].AV.isUndefValue() &&
968 "Dead BB dominate this block");
969 return ValuesPerBlock[0].MaterializeAdjustedValue(Load, gvn);
970 }
971
972 // Otherwise, we have to construct SSA form.
974 SSAUpdater SSAUpdate(&NewPHIs);
975 SSAUpdate.Initialize(Load->getType(), Load->getName());
976
977 for (const AvailableValueInBlock &AV : ValuesPerBlock) {
978 BasicBlock *BB = AV.BB;
979
980 if (AV.AV.isUndefValue())
981 continue;
982
983 if (SSAUpdate.HasValueForBlock(BB))
984 continue;
985
986 // If the value is the load that we will be eliminating, and the block it's
987 // available in is the block that the load is in, then don't add it as
988 // SSAUpdater will resolve the value to the relevant phi which may let it
989 // avoid phi construction entirely if there's actually only one value.
990 if (BB == Load->getParent() &&
991 ((AV.AV.isSimpleValue() && AV.AV.getSimpleValue() == Load) ||
992 (AV.AV.isCoercedLoadValue() && AV.AV.getCoercedLoadValue() == Load)))
993 continue;
994
995 SSAUpdate.AddAvailableValue(BB, AV.MaterializeAdjustedValue(Load, gvn));
996 }
997
998 // Perform PHI construction.
999 return SSAUpdate.GetValueInMiddleOfBlock(Load->getParent());
1000}
1001
1003 Instruction *InsertPt,
1004 GVNPass &gvn) const {
1005 Value *Res;
1006 Type *LoadTy = Load->getType();
1007 const DataLayout &DL = Load->getModule()->getDataLayout();
1008 if (isSimpleValue()) {
1009 Res = getSimpleValue();
1010 if (Res->getType() != LoadTy) {
1011 Res = getValueForLoad(Res, Offset, LoadTy, InsertPt, DL);
1012
1013 LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL VAL:\nOffset: " << Offset
1014 << " " << *getSimpleValue() << '\n'
1015 << *Res << '\n'
1016 << "\n\n\n");
1017 }
1018 } else if (isCoercedLoadValue()) {
1019 LoadInst *CoercedLoad = getCoercedLoadValue();
1020 if (CoercedLoad->getType() == LoadTy && Offset == 0) {
1021 Res = CoercedLoad;
1022 combineMetadataForCSE(CoercedLoad, Load, false);
1023 } else {
1024 Res = getValueForLoad(CoercedLoad, Offset, LoadTy, InsertPt, DL);
1025 // We are adding a new user for this load, for which the original
1026 // metadata may not hold. Additionally, the new load may have a different
1027 // size and type, so their metadata cannot be combined in any
1028 // straightforward way.
1029 // Drop all metadata that is not known to cause immediate UB on violation,
1030 // unless the load has !noundef, in which case all metadata violations
1031 // will be promoted to UB.
1032 // TODO: We can combine noalias/alias.scope metadata here, because it is
1033 // independent of the load type.
1034 if (!CoercedLoad->hasMetadata(LLVMContext::MD_noundef))
1035 CoercedLoad->dropUnknownNonDebugMetadata(
1036 {LLVMContext::MD_dereferenceable,
1037 LLVMContext::MD_dereferenceable_or_null,
1038 LLVMContext::MD_invariant_load, LLVMContext::MD_invariant_group});
1039 LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL LOAD:\nOffset: " << Offset
1040 << " " << *getCoercedLoadValue() << '\n'
1041 << *Res << '\n'
1042 << "\n\n\n");
1043 }
1044 } else if (isMemIntrinValue()) {
1045 Res = getMemInstValueForLoad(getMemIntrinValue(), Offset, LoadTy,
1046 InsertPt, DL);
1047 LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL MEM INTRIN:\nOffset: " << Offset
1048 << " " << *getMemIntrinValue() << '\n'
1049 << *Res << '\n'
1050 << "\n\n\n");
1051 } else if (isSelectValue()) {
1052 // Introduce a new value select for a load from an eligible pointer select.
1053 SelectInst *Sel = getSelectValue();
1054 assert(V1 && V2 && "both value operands of the select must be present");
1055 Res = SelectInst::Create(Sel->getCondition(), V1, V2, "", Sel);
1056 } else {
1057 llvm_unreachable("Should not materialize value from dead block");
1058 }
1059 assert(Res && "failed to materialize?");
1060 return Res;
1061}
1062
1063static bool isLifetimeStart(const Instruction *Inst) {
1064 if (const IntrinsicInst* II = dyn_cast<IntrinsicInst>(Inst))
1065 return II->getIntrinsicID() == Intrinsic::lifetime_start;
1066 return false;
1067}
1068
1069/// Assuming To can be reached from both From and Between, does Between lie on
1070/// every path from From to To?
1071static bool liesBetween(const Instruction *From, Instruction *Between,
1072 const Instruction *To, DominatorTree *DT) {
1073 if (From->getParent() == Between->getParent())
1074 return DT->dominates(From, Between);
1075 SmallSet<BasicBlock *, 1> Exclusion;
1076 Exclusion.insert(Between->getParent());
1077 return !isPotentiallyReachable(From, To, &Exclusion, DT);
1078}
1079
1080/// Try to locate the three instruction involved in a missed
1081/// load-elimination case that is due to an intervening store.
1083 DominatorTree *DT,
1085 using namespace ore;
1086
1087 Instruction *OtherAccess = nullptr;
1088
1089 OptimizationRemarkMissed R(DEBUG_TYPE, "LoadClobbered", Load);
1090 R << "load of type " << NV("Type", Load->getType()) << " not eliminated"
1091 << setExtraArgs();
1092
1093 for (auto *U : Load->getPointerOperand()->users()) {
1094 if (U != Load && (isa<LoadInst>(U) || isa<StoreInst>(U))) {
1095 auto *I = cast<Instruction>(U);
1096 if (I->getFunction() == Load->getFunction() && DT->dominates(I, Load)) {
1097 // Use the most immediately dominating value
1098 if (OtherAccess) {
1099 if (DT->dominates(OtherAccess, I))
1100 OtherAccess = I;
1101 else
1102 assert(U == OtherAccess || DT->dominates(I, OtherAccess));
1103 } else
1104 OtherAccess = I;
1105 }
1106 }
1107 }
1108
1109 if (!OtherAccess) {
1110 // There is no dominating use, check if we can find a closest non-dominating
1111 // use that lies between any other potentially available use and Load.
1112 for (auto *U : Load->getPointerOperand()->users()) {
1113 if (U != Load && (isa<LoadInst>(U) || isa<StoreInst>(U))) {
1114 auto *I = cast<Instruction>(U);
1115 if (I->getFunction() == Load->getFunction() &&
1116 isPotentiallyReachable(I, Load, nullptr, DT)) {
1117 if (OtherAccess) {
1118 if (liesBetween(OtherAccess, I, Load, DT)) {
1119 OtherAccess = I;
1120 } else if (!liesBetween(I, OtherAccess, Load, DT)) {
1121 // These uses are both partially available at Load were it not for
1122 // the clobber, but neither lies strictly after the other.
1123 OtherAccess = nullptr;
1124 break;
1125 } // else: keep current OtherAccess since it lies between U and Load
1126 } else {
1127 OtherAccess = I;
1128 }
1129 }
1130 }
1131 }
1132 }
1133
1134 if (OtherAccess)
1135 R << " in favor of " << NV("OtherAccess", OtherAccess);
1136
1137 R << " because it is clobbered by " << NV("ClobberedBy", DepInfo.getInst());
1138
1139 ORE->emit(R);
1140}
1141
1142// Find non-clobbered value for Loc memory location in extended basic block
1143// (chain of basic blocks with single predecessors) starting From instruction.
1144static Value *findDominatingValue(const MemoryLocation &Loc, Type *LoadTy,
1145 Instruction *From, AAResults *AA) {
1146 uint32_t NumVisitedInsts = 0;
1147 BasicBlock *FromBB = From->getParent();
1148 BatchAAResults BatchAA(*AA);
1149 for (BasicBlock *BB = FromBB; BB; BB = BB->getSinglePredecessor())
1150 for (auto *Inst = BB == FromBB ? From : BB->getTerminator();
1151 Inst != nullptr; Inst = Inst->getPrevNonDebugInstruction()) {
1152 // Stop the search if limit is reached.
1153 if (++NumVisitedInsts > MaxNumVisitedInsts)
1154 return nullptr;
1155 if (isModSet(BatchAA.getModRefInfo(Inst, Loc)))
1156 return nullptr;
1157 if (auto *LI = dyn_cast<LoadInst>(Inst))
1158 if (LI->getPointerOperand() == Loc.Ptr && LI->getType() == LoadTy)
1159 return LI;
1160 }
1161 return nullptr;
1162}
1163
1164std::optional<AvailableValue>
1165GVNPass::AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo,
1166 Value *Address) {
1167 assert(Load->isUnordered() && "rules below are incorrect for ordered access");
1168 assert(DepInfo.isLocal() && "expected a local dependence");
1169
1170 Instruction *DepInst = DepInfo.getInst();
1171
1172 const DataLayout &DL = Load->getModule()->getDataLayout();
1173 if (DepInfo.isClobber()) {
1174 // If the dependence is to a store that writes to a superset of the bits
1175 // read by the load, we can extract the bits we need for the load from the
1176 // stored value.
1177 if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInst)) {
1178 // Can't forward from non-atomic to atomic without violating memory model.
1179 if (Address && Load->isAtomic() <= DepSI->isAtomic()) {
1180 int Offset =
1181 analyzeLoadFromClobberingStore(Load->getType(), Address, DepSI, DL);
1182 if (Offset != -1)
1183 return AvailableValue::get(DepSI->getValueOperand(), Offset);
1184 }
1185 }
1186
1187 // Check to see if we have something like this:
1188 // load i32* P
1189 // load i8* (P+1)
1190 // if we have this, replace the later with an extraction from the former.
1191 if (LoadInst *DepLoad = dyn_cast<LoadInst>(DepInst)) {
1192 // If this is a clobber and L is the first instruction in its block, then
1193 // we have the first instruction in the entry block.
1194 // Can't forward from non-atomic to atomic without violating memory model.
1195 if (DepLoad != Load && Address &&
1196 Load->isAtomic() <= DepLoad->isAtomic()) {
1197 Type *LoadType = Load->getType();
1198 int Offset = -1;
1199
1200 // If MD reported clobber, check it was nested.
1201 if (DepInfo.isClobber() &&
1202 canCoerceMustAliasedValueToLoad(DepLoad, LoadType, DL)) {
1203 const auto ClobberOff = MD->getClobberOffset(DepLoad);
1204 // GVN has no deal with a negative offset.
1205 Offset = (ClobberOff == std::nullopt || *ClobberOff < 0)
1206 ? -1
1207 : *ClobberOff;
1208 }
1209 if (Offset == -1)
1210 Offset =
1211 analyzeLoadFromClobberingLoad(LoadType, Address, DepLoad, DL);
1212 if (Offset != -1)
1213 return AvailableValue::getLoad(DepLoad, Offset);
1214 }
1215 }
1216
1217 // If the clobbering value is a memset/memcpy/memmove, see if we can
1218 // forward a value on from it.
1219 if (MemIntrinsic *DepMI = dyn_cast<MemIntrinsic>(DepInst)) {
1220 if (Address && !Load->isAtomic()) {
1222 DepMI, DL);
1223 if (Offset != -1)
1224 return AvailableValue::getMI(DepMI, Offset);
1225 }
1226 }
1227
1228 // Nothing known about this clobber, have to be conservative
1229 LLVM_DEBUG(
1230 // fast print dep, using operator<< on instruction is too slow.
1231 dbgs() << "GVN: load "; Load->printAsOperand(dbgs());
1232 dbgs() << " is clobbered by " << *DepInst << '\n';);
1234 reportMayClobberedLoad(Load, DepInfo, DT, ORE);
1235
1236 return std::nullopt;
1237 }
1238 assert(DepInfo.isDef() && "follows from above");
1239
1240 // Loading the alloca -> undef.
1241 // Loading immediately after lifetime begin -> undef.
1242 if (isa<AllocaInst>(DepInst) || isLifetimeStart(DepInst))
1243 return AvailableValue::get(UndefValue::get(Load->getType()));
1244
1245 if (Constant *InitVal =
1246 getInitialValueOfAllocation(DepInst, TLI, Load->getType()))
1247 return AvailableValue::get(InitVal);
1248
1249 if (StoreInst *S = dyn_cast<StoreInst>(DepInst)) {
1250 // Reject loads and stores that are to the same address but are of
1251 // different types if we have to. If the stored value is convertable to
1252 // the loaded value, we can reuse it.
1253 if (!canCoerceMustAliasedValueToLoad(S->getValueOperand(), Load->getType(),
1254 DL))
1255 return std::nullopt;
1256
1257 // Can't forward from non-atomic to atomic without violating memory model.
1258 if (S->isAtomic() < Load->isAtomic())
1259 return std::nullopt;
1260
1261 return AvailableValue::get(S->getValueOperand());
1262 }
1263
1264 if (LoadInst *LD = dyn_cast<LoadInst>(DepInst)) {
1265 // If the types mismatch and we can't handle it, reject reuse of the load.
1266 // If the stored value is larger or equal to the loaded value, we can reuse
1267 // it.
1268 if (!canCoerceMustAliasedValueToLoad(LD, Load->getType(), DL))
1269 return std::nullopt;
1270
1271 // Can't forward from non-atomic to atomic without violating memory model.
1272 if (LD->isAtomic() < Load->isAtomic())
1273 return std::nullopt;
1274
1275 return AvailableValue::getLoad(LD);
1276 }
1277
1278 // Check if load with Addr dependent from select can be converted to select
1279 // between load values. There must be no instructions between the found
1280 // loads and DepInst that may clobber the loads.
1281 if (auto *Sel = dyn_cast<SelectInst>(DepInst)) {
1282 assert(Sel->getType() == Load->getPointerOperandType());
1283 auto Loc = MemoryLocation::get(Load);
1284 Value *V1 =
1285 findDominatingValue(Loc.getWithNewPtr(Sel->getTrueValue()),
1286 Load->getType(), DepInst, getAliasAnalysis());
1287 if (!V1)
1288 return std::nullopt;
1289 Value *V2 =
1290 findDominatingValue(Loc.getWithNewPtr(Sel->getFalseValue()),
1291 Load->getType(), DepInst, getAliasAnalysis());
1292 if (!V2)
1293 return std::nullopt;
1294 return AvailableValue::getSelect(Sel, V1, V2);
1295 }
1296
1297 // Unknown def - must be conservative
1298 LLVM_DEBUG(
1299 // fast print dep, using operator<< on instruction is too slow.
1300 dbgs() << "GVN: load "; Load->printAsOperand(dbgs());
1301 dbgs() << " has unknown def " << *DepInst << '\n';);
1302 return std::nullopt;
1303}
1304
1305void GVNPass::AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps,
1306 AvailValInBlkVect &ValuesPerBlock,
1307 UnavailBlkVect &UnavailableBlocks) {
1308 // Filter out useless results (non-locals, etc). Keep track of the blocks
1309 // where we have a value available in repl, also keep track of whether we see
1310 // dependencies that produce an unknown value for the load (such as a call
1311 // that could potentially clobber the load).
1312 for (const auto &Dep : Deps) {
1313 BasicBlock *DepBB = Dep.getBB();
1314 MemDepResult DepInfo = Dep.getResult();
1315
1316 if (DeadBlocks.count(DepBB)) {
1317 // Dead dependent mem-op disguise as a load evaluating the same value
1318 // as the load in question.
1319 ValuesPerBlock.push_back(AvailableValueInBlock::getUndef(DepBB));
1320 continue;
1321 }
1322
1323 if (!DepInfo.isLocal()) {
1324 UnavailableBlocks.push_back(DepBB);
1325 continue;
1326 }
1327
1328 // The address being loaded in this non-local block may not be the same as
1329 // the pointer operand of the load if PHI translation occurs. Make sure
1330 // to consider the right address.
1331 if (auto AV = AnalyzeLoadAvailability(Load, DepInfo, Dep.getAddress())) {
1332 // subtlety: because we know this was a non-local dependency, we know
1333 // it's safe to materialize anywhere between the instruction within
1334 // DepInfo and the end of it's block.
1335 ValuesPerBlock.push_back(
1336 AvailableValueInBlock::get(DepBB, std::move(*AV)));
1337 } else {
1338 UnavailableBlocks.push_back(DepBB);
1339 }
1340 }
1341
1342 assert(Deps.size() == ValuesPerBlock.size() + UnavailableBlocks.size() &&
1343 "post condition violation");
1344}
1345
1346/// Given the following code, v1 is partially available on some edges, but not
1347/// available on the edge from PredBB. This function tries to find if there is
1348/// another identical load in the other successor of PredBB.
1349///
1350/// v0 = load %addr
1351/// br %LoadBB
1352///
1353/// LoadBB:
1354/// v1 = load %addr
1355/// ...
1356///
1357/// PredBB:
1358/// ...
1359/// br %cond, label %LoadBB, label %SuccBB
1360///
1361/// SuccBB:
1362/// v2 = load %addr
1363/// ...
1364///
1365LoadInst *GVNPass::findLoadToHoistIntoPred(BasicBlock *Pred, BasicBlock *LoadBB,
1366 LoadInst *Load) {
1367 // For simplicity we handle a Pred has 2 successors only.
1368 auto *Term = Pred->getTerminator();
1369 if (Term->getNumSuccessors() != 2 || Term->isSpecialTerminator())
1370 return nullptr;
1371 auto *SuccBB = Term->getSuccessor(0);
1372 if (SuccBB == LoadBB)
1373 SuccBB = Term->getSuccessor(1);
1374 if (!SuccBB->getSinglePredecessor())
1375 return nullptr;
1376
1377 unsigned int NumInsts = MaxNumInsnsPerBlock;
1378 for (Instruction &Inst : *SuccBB) {
1379 if (Inst.isDebugOrPseudoInst())
1380 continue;
1381 if (--NumInsts == 0)
1382 return nullptr;
1383
1384 if (!Inst.isIdenticalTo(Load))
1385 continue;
1386
1387 MemDepResult Dep = MD->getDependency(&Inst);
1388 // If an identical load doesn't depends on any local instructions, it can
1389 // be safely moved to PredBB.
1390 // Also check for the implicit control flow instructions. See the comments
1391 // in PerformLoadPRE for details.
1392 if (Dep.isNonLocal() && !ICF->isDominatedByICFIFromSameBlock(&Inst))
1393 return cast<LoadInst>(&Inst);
1394
1395 // Otherwise there is something in the same BB clobbers the memory, we can't
1396 // move this and later load to PredBB.
1397 return nullptr;
1398 }
1399
1400 return nullptr;
1401}
1402
1403void GVNPass::eliminatePartiallyRedundantLoad(
1404 LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
1405 MapVector<BasicBlock *, Value *> &AvailableLoads,
1406 MapVector<BasicBlock *, LoadInst *> *CriticalEdgePredAndLoad) {
1407 for (const auto &AvailableLoad : AvailableLoads) {
1408 BasicBlock *UnavailableBlock = AvailableLoad.first;
1409 Value *LoadPtr = AvailableLoad.second;
1410
1411 auto *NewLoad =
1412 new LoadInst(Load->getType(), LoadPtr, Load->getName() + ".pre",
1413 Load->isVolatile(), Load->getAlign(), Load->getOrdering(),
1414 Load->getSyncScopeID(), UnavailableBlock->getTerminator());
1415 NewLoad->setDebugLoc(Load->getDebugLoc());
1416 if (MSSAU) {
1417 auto *NewAccess = MSSAU->createMemoryAccessInBB(
1418 NewLoad, nullptr, NewLoad->getParent(), MemorySSA::BeforeTerminator);
1419 if (auto *NewDef = dyn_cast<MemoryDef>(NewAccess))
1420 MSSAU->insertDef(NewDef, /*RenameUses=*/true);
1421 else
1422 MSSAU->insertUse(cast<MemoryUse>(NewAccess), /*RenameUses=*/true);
1423 }
1424
1425 // Transfer the old load's AA tags to the new load.
1426 AAMDNodes Tags = Load->getAAMetadata();
1427 if (Tags)
1428 NewLoad->setAAMetadata(Tags);
1429
1430 if (auto *MD = Load->getMetadata(LLVMContext::MD_invariant_load))
1431 NewLoad->setMetadata(LLVMContext::MD_invariant_load, MD);
1432 if (auto *InvGroupMD = Load->getMetadata(LLVMContext::MD_invariant_group))
1433 NewLoad->setMetadata(LLVMContext::MD_invariant_group, InvGroupMD);
1434 if (auto *RangeMD = Load->getMetadata(LLVMContext::MD_range))
1435 NewLoad->setMetadata(LLVMContext::MD_range, RangeMD);
1436 if (auto *AccessMD = Load->getMetadata(LLVMContext::MD_access_group))
1437 if (LI &&
1438 LI->getLoopFor(Load->getParent()) == LI->getLoopFor(UnavailableBlock))
1439 NewLoad->setMetadata(LLVMContext::MD_access_group, AccessMD);
1440
1441 // We do not propagate the old load's debug location, because the new
1442 // load now lives in a different BB, and we want to avoid a jumpy line
1443 // table.
1444 // FIXME: How do we retain source locations without causing poor debugging
1445 // behavior?
1446
1447 // Add the newly created load.
1448 ValuesPerBlock.push_back(
1449 AvailableValueInBlock::get(UnavailableBlock, NewLoad));
1450 MD->invalidateCachedPointerInfo(LoadPtr);
1451 LLVM_DEBUG(dbgs() << "GVN INSERTED " << *NewLoad << '\n');
1452
1453 // For PredBB in CriticalEdgePredAndLoad we need to replace the uses of old
1454 // load instruction with the new created load instruction.
1455 if (CriticalEdgePredAndLoad) {
1456 auto I = CriticalEdgePredAndLoad->find(UnavailableBlock);
1457 if (I != CriticalEdgePredAndLoad->end()) {
1458 ++NumPRELoadMoved2CEPred;
1459 ICF->insertInstructionTo(NewLoad, UnavailableBlock);
1460 LoadInst *OldLoad = I->second;
1461 combineMetadataForCSE(NewLoad, OldLoad, false);
1462 OldLoad->replaceAllUsesWith(NewLoad);
1463 replaceValuesPerBlockEntry(ValuesPerBlock, OldLoad, NewLoad);
1464 if (uint32_t ValNo = VN.lookup(OldLoad, false))
1465 removeFromLeaderTable(ValNo, OldLoad, OldLoad->getParent());
1466 VN.erase(OldLoad);
1467 removeInstruction(OldLoad);
1468 }
1469 }
1470 }
1471
1472 // Perform PHI construction.
1473 Value *V = ConstructSSAForLoadSet(Load, ValuesPerBlock, *this);
1474 // ConstructSSAForLoadSet is responsible for combining metadata.
1475 Load->replaceAllUsesWith(V);
1476 if (isa<PHINode>(V))
1477 V->takeName(Load);
1478 if (Instruction *I = dyn_cast<Instruction>(V))
1479 I->setDebugLoc(Load->getDebugLoc());
1480 if (V->getType()->isPtrOrPtrVectorTy())
1483 ORE->emit([&]() {
1484 return OptimizationRemark(DEBUG_TYPE, "LoadPRE", Load)
1485 << "load eliminated by PRE";
1486 });
1487}
1488
1489bool GVNPass::PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
1490 UnavailBlkVect &UnavailableBlocks) {
1491 // Okay, we have *some* definitions of the value. This means that the value
1492 // is available in some of our (transitive) predecessors. Lets think about
1493 // doing PRE of this load. This will involve inserting a new load into the
1494 // predecessor when it's not available. We could do this in general, but
1495 // prefer to not increase code size. As such, we only do this when we know
1496 // that we only have to insert *one* load (which means we're basically moving
1497 // the load, not inserting a new one).
1498
1499 SmallPtrSet<BasicBlock *, 4> Blockers(UnavailableBlocks.begin(),
1500 UnavailableBlocks.end());
1501
1502 // Let's find the first basic block with more than one predecessor. Walk
1503 // backwards through predecessors if needed.
1504 BasicBlock *LoadBB = Load->getParent();
1505 BasicBlock *TmpBB = LoadBB;
1506
1507 // Check that there is no implicit control flow instructions above our load in
1508 // its block. If there is an instruction that doesn't always pass the
1509 // execution to the following instruction, then moving through it may become
1510 // invalid. For example:
1511 //
1512 // int arr[LEN];
1513 // int index = ???;
1514 // ...
1515 // guard(0 <= index && index < LEN);
1516 // use(arr[index]);
1517 //
1518 // It is illegal to move the array access to any point above the guard,
1519 // because if the index is out of bounds we should deoptimize rather than
1520 // access the array.
1521 // Check that there is no guard in this block above our instruction.
1522 bool MustEnsureSafetyOfSpeculativeExecution =
1524
1525 while (TmpBB->getSinglePredecessor()) {
1526 TmpBB = TmpBB->getSinglePredecessor();
1527 if (TmpBB == LoadBB) // Infinite (unreachable) loop.
1528 return false;
1529 if (Blockers.count(TmpBB))
1530 return false;
1531
1532 // If any of these blocks has more than one successor (i.e. if the edge we
1533 // just traversed was critical), then there are other paths through this
1534 // block along which the load may not be anticipated. Hoisting the load
1535 // above this block would be adding the load to execution paths along
1536 // which it was not previously executed.
1537 if (TmpBB->getTerminator()->getNumSuccessors() != 1)
1538 return false;
1539
1540 // Check that there is no implicit control flow in a block above.
1541 MustEnsureSafetyOfSpeculativeExecution =
1542 MustEnsureSafetyOfSpeculativeExecution || ICF->hasICF(TmpBB);
1543 }
1544
1545 assert(TmpBB);
1546 LoadBB = TmpBB;
1547
1548 // Check to see how many predecessors have the loaded value fully
1549 // available.
1551 DenseMap<BasicBlock *, AvailabilityState> FullyAvailableBlocks;
1552 for (const AvailableValueInBlock &AV : ValuesPerBlock)
1553 FullyAvailableBlocks[AV.BB] = AvailabilityState::Available;
1554 for (BasicBlock *UnavailableBB : UnavailableBlocks)
1555 FullyAvailableBlocks[UnavailableBB] = AvailabilityState::Unavailable;
1556
1557 // The edge from Pred to LoadBB is a critical edge will be splitted.
1558 SmallVector<BasicBlock *, 4> CriticalEdgePredSplit;
1559 // The edge from Pred to LoadBB is a critical edge, another successor of Pred
1560 // contains a load can be moved to Pred. This data structure maps the Pred to
1561 // the movable load.
1562 MapVector<BasicBlock *, LoadInst *> CriticalEdgePredAndLoad;
1563 for (BasicBlock *Pred : predecessors(LoadBB)) {
1564 // If any predecessor block is an EH pad that does not allow non-PHI
1565 // instructions before the terminator, we can't PRE the load.
1566 if (Pred->getTerminator()->isEHPad()) {
1567 LLVM_DEBUG(
1568 dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD PREDECESSOR '"
1569 << Pred->getName() << "': " << *Load << '\n');
1570 return false;
1571 }
1572
1573 if (IsValueFullyAvailableInBlock(Pred, FullyAvailableBlocks)) {
1574 continue;
1575 }
1576
1577 if (Pred->getTerminator()->getNumSuccessors() != 1) {
1578 if (isa<IndirectBrInst>(Pred->getTerminator())) {
1579 LLVM_DEBUG(
1580 dbgs() << "COULD NOT PRE LOAD BECAUSE OF INDBR CRITICAL EDGE '"
1581 << Pred->getName() << "': " << *Load << '\n');
1582 return false;
1583 }
1584
1585 if (LoadBB->isEHPad()) {
1586 LLVM_DEBUG(
1587 dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD CRITICAL EDGE '"
1588 << Pred->getName() << "': " << *Load << '\n');
1589 return false;
1590 }
1591
1592 // Do not split backedge as it will break the canonical loop form.
1594 if (DT->dominates(LoadBB, Pred)) {
1595 LLVM_DEBUG(
1596 dbgs()
1597 << "COULD NOT PRE LOAD BECAUSE OF A BACKEDGE CRITICAL EDGE '"
1598 << Pred->getName() << "': " << *Load << '\n');
1599 return false;
1600 }
1601
1602 if (LoadInst *LI = findLoadToHoistIntoPred(Pred, LoadBB, Load))
1603 CriticalEdgePredAndLoad[Pred] = LI;
1604 else
1605 CriticalEdgePredSplit.push_back(Pred);
1606 } else {
1607 // Only add the predecessors that will not be split for now.
1608 PredLoads[Pred] = nullptr;
1609 }
1610 }
1611
1612 // Decide whether PRE is profitable for this load.
1613 unsigned NumInsertPreds = PredLoads.size() + CriticalEdgePredSplit.size();
1614 unsigned NumUnavailablePreds = NumInsertPreds +
1615 CriticalEdgePredAndLoad.size();
1616 assert(NumUnavailablePreds != 0 &&
1617 "Fully available value should already be eliminated!");
1618 (void)NumUnavailablePreds;
1619
1620 // If we need to insert new load in multiple predecessors, reject it.
1621 // FIXME: If we could restructure the CFG, we could make a common pred with
1622 // all the preds that don't have an available Load and insert a new load into
1623 // that one block.
1624 if (NumInsertPreds > 1)
1625 return false;
1626
1627 // Now we know where we will insert load. We must ensure that it is safe
1628 // to speculatively execute the load at that points.
1629 if (MustEnsureSafetyOfSpeculativeExecution) {
1630 if (CriticalEdgePredSplit.size())
1631 if (!isSafeToSpeculativelyExecute(Load, LoadBB->getFirstNonPHI(), AC, DT))
1632 return false;
1633 for (auto &PL : PredLoads)
1634 if (!isSafeToSpeculativelyExecute(Load, PL.first->getTerminator(), AC,
1635 DT))
1636 return false;
1637 for (auto &CEP : CriticalEdgePredAndLoad)
1638 if (!isSafeToSpeculativelyExecute(Load, CEP.first->getTerminator(), AC,
1639 DT))
1640 return false;
1641 }
1642
1643 // Split critical edges, and update the unavailable predecessors accordingly.
1644 for (BasicBlock *OrigPred : CriticalEdgePredSplit) {
1645 BasicBlock *NewPred = splitCriticalEdges(OrigPred, LoadBB);
1646 assert(!PredLoads.count(OrigPred) && "Split edges shouldn't be in map!");
1647 PredLoads[NewPred] = nullptr;
1648 LLVM_DEBUG(dbgs() << "Split critical edge " << OrigPred->getName() << "->"
1649 << LoadBB->getName() << '\n');
1650 }
1651
1652 for (auto &CEP : CriticalEdgePredAndLoad)
1653 PredLoads[CEP.first] = nullptr;
1654
1655 // Check if the load can safely be moved to all the unavailable predecessors.
1656 bool CanDoPRE = true;
1657 const DataLayout &DL = Load->getModule()->getDataLayout();
1659 for (auto &PredLoad : PredLoads) {
1660 BasicBlock *UnavailablePred = PredLoad.first;
1661
1662 // Do PHI translation to get its value in the predecessor if necessary. The
1663 // returned pointer (if non-null) is guaranteed to dominate UnavailablePred.
1664 // We do the translation for each edge we skipped by going from Load's block
1665 // to LoadBB, otherwise we might miss pieces needing translation.
1666
1667 // If all preds have a single successor, then we know it is safe to insert
1668 // the load on the pred (?!?), so we can insert code to materialize the
1669 // pointer if it is not available.
1670 Value *LoadPtr = Load->getPointerOperand();
1671 BasicBlock *Cur = Load->getParent();
1672 while (Cur != LoadBB) {
1673 PHITransAddr Address(LoadPtr, DL, AC);
1674 LoadPtr = Address.translateWithInsertion(Cur, Cur->getSinglePredecessor(),
1675 *DT, NewInsts);
1676 if (!LoadPtr) {
1677 CanDoPRE = false;
1678 break;
1679 }
1680 Cur = Cur->getSinglePredecessor();
1681 }
1682
1683 if (LoadPtr) {
1684 PHITransAddr Address(LoadPtr, DL, AC);
1685 LoadPtr = Address.translateWithInsertion(LoadBB, UnavailablePred, *DT,
1686 NewInsts);
1687 }
1688 // If we couldn't find or insert a computation of this phi translated value,
1689 // we fail PRE.
1690 if (!LoadPtr) {
1691 LLVM_DEBUG(dbgs() << "COULDN'T INSERT PHI TRANSLATED VALUE OF: "
1692 << *Load->getPointerOperand() << "\n");
1693 CanDoPRE = false;
1694 break;
1695 }
1696
1697 PredLoad.second = LoadPtr;
1698 }
1699
1700 if (!CanDoPRE) {
1701 while (!NewInsts.empty()) {
1702 // Erase instructions generated by the failed PHI translation before
1703 // trying to number them. PHI translation might insert instructions
1704 // in basic blocks other than the current one, and we delete them
1705 // directly, as markInstructionForDeletion only allows removing from the
1706 // current basic block.
1707 NewInsts.pop_back_val()->eraseFromParent();
1708 }
1709 // HINT: Don't revert the edge-splitting as following transformation may
1710 // also need to split these critical edges.
1711 return !CriticalEdgePredSplit.empty();
1712 }
1713
1714 // Okay, we can eliminate this load by inserting a reload in the predecessor
1715 // and using PHI construction to get the value in the other predecessors, do
1716 // it.
1717 LLVM_DEBUG(dbgs() << "GVN REMOVING PRE LOAD: " << *Load << '\n');
1718 LLVM_DEBUG(if (!NewInsts.empty()) dbgs() << "INSERTED " << NewInsts.size()
1719 << " INSTS: " << *NewInsts.back()
1720 << '\n');
1721
1722 // Assign value numbers to the new instructions.
1723 for (Instruction *I : NewInsts) {
1724 // Instructions that have been inserted in predecessor(s) to materialize
1725 // the load address do not retain their original debug locations. Doing
1726 // so could lead to confusing (but correct) source attributions.
1727 I->updateLocationAfterHoist();
1728
1729 // FIXME: We really _ought_ to insert these value numbers into their
1730 // parent's availability map. However, in doing so, we risk getting into
1731 // ordering issues. If a block hasn't been processed yet, we would be
1732 // marking a value as AVAIL-IN, which isn't what we intend.
1733 VN.lookupOrAdd(I);
1734 }
1735
1736 eliminatePartiallyRedundantLoad(Load, ValuesPerBlock, PredLoads,
1737 &CriticalEdgePredAndLoad);
1738 ++NumPRELoad;
1739 return true;
1740}
1741
1742bool GVNPass::performLoopLoadPRE(LoadInst *Load,
1743 AvailValInBlkVect &ValuesPerBlock,
1744 UnavailBlkVect &UnavailableBlocks) {
1745 if (!LI)
1746 return false;
1747
1748 const Loop *L = LI->getLoopFor(Load->getParent());
1749 // TODO: Generalize to other loop blocks that dominate the latch.
1750 if (!L || L->getHeader() != Load->getParent())
1751 return false;
1752
1753 BasicBlock *Preheader = L->getLoopPreheader();
1754 BasicBlock *Latch = L->getLoopLatch();
1755 if (!Preheader || !Latch)
1756 return false;
1757
1758 Value *LoadPtr = Load->getPointerOperand();
1759 // Must be available in preheader.
1760 if (!L->isLoopInvariant(LoadPtr))
1761 return false;
1762
1763 // We plan to hoist the load to preheader without introducing a new fault.
1764 // In order to do it, we need to prove that we cannot side-exit the loop
1765 // once loop header is first entered before execution of the load.
1766 if (ICF->isDominatedByICFIFromSameBlock(Load))
1767 return false;
1768
1769 BasicBlock *LoopBlock = nullptr;
1770 for (auto *Blocker : UnavailableBlocks) {
1771 // Blockers from outside the loop are handled in preheader.
1772 if (!L->contains(Blocker))
1773 continue;
1774
1775 // Only allow one loop block. Loop header is not less frequently executed
1776 // than each loop block, and likely it is much more frequently executed. But
1777 // in case of multiple loop blocks, we need extra information (such as block
1778 // frequency info) to understand whether it is profitable to PRE into
1779 // multiple loop blocks.
1780 if (LoopBlock)
1781 return false;
1782
1783 // Do not sink into inner loops. This may be non-profitable.
1784 if (L != LI->getLoopFor(Blocker))
1785 return false;
1786
1787 // Blocks that dominate the latch execute on every single iteration, maybe
1788 // except the last one. So PREing into these blocks doesn't make much sense
1789 // in most cases. But the blocks that do not necessarily execute on each
1790 // iteration are sometimes much colder than the header, and this is when
1791 // PRE is potentially profitable.
1792 if (DT->dominates(Blocker, Latch))
1793 return false;
1794
1795 // Make sure that the terminator itself doesn't clobber.
1796 if (Blocker->getTerminator()->mayWriteToMemory())
1797 return false;
1798
1799 LoopBlock = Blocker;
1800 }
1801
1802 if (!LoopBlock)
1803 return false;
1804
1805 // Make sure the memory at this pointer cannot be freed, therefore we can
1806 // safely reload from it after clobber.
1807 if (LoadPtr->canBeFreed())
1808 return false;
1809
1810 // TODO: Support critical edge splitting if blocker has more than 1 successor.
1811 MapVector<BasicBlock *, Value *> AvailableLoads;
1812 AvailableLoads[LoopBlock] = LoadPtr;
1813 AvailableLoads[Preheader] = LoadPtr;
1814
1815 LLVM_DEBUG(dbgs() << "GVN REMOVING PRE LOOP LOAD: " << *Load << '\n');
1816 eliminatePartiallyRedundantLoad(Load, ValuesPerBlock, AvailableLoads,
1817 /*CriticalEdgePredAndLoad*/ nullptr);
1818 ++NumPRELoopLoad;
1819 return true;
1820}
1821
1824 using namespace ore;
1825
1826 ORE->emit([&]() {
1827 return OptimizationRemark(DEBUG_TYPE, "LoadElim", Load)
1828 << "load of type " << NV("Type", Load->getType()) << " eliminated"
1829 << setExtraArgs() << " in favor of "
1830 << NV("InfavorOfValue", AvailableValue);
1831 });
1832}
1833
1834/// Attempt to eliminate a load whose dependencies are
1835/// non-local by performing PHI construction.
1836bool GVNPass::processNonLocalLoad(LoadInst *Load) {
1837 // non-local speculations are not allowed under asan.
1838 if (Load->getParent()->getParent()->hasFnAttribute(
1839 Attribute::SanitizeAddress) ||
1840 Load->getParent()->getParent()->hasFnAttribute(
1841 Attribute::SanitizeHWAddress))
1842 return false;
1843
1844 // Step 1: Find the non-local dependencies of the load.
1845 LoadDepVect Deps;
1846 MD->getNonLocalPointerDependency(Load, Deps);
1847
1848 // If we had to process more than one hundred blocks to find the
1849 // dependencies, this load isn't worth worrying about. Optimizing
1850 // it will be too expensive.
1851 unsigned NumDeps = Deps.size();
1852 if (NumDeps > MaxNumDeps)
1853 return false;
1854
1855 // If we had a phi translation failure, we'll have a single entry which is a
1856 // clobber in the current block. Reject this early.
1857 if (NumDeps == 1 &&
1858 !Deps[0].getResult().isDef() && !Deps[0].getResult().isClobber()) {
1859 LLVM_DEBUG(dbgs() << "GVN: non-local load "; Load->printAsOperand(dbgs());
1860 dbgs() << " has unknown dependencies\n";);
1861 return false;
1862 }
1863
1864 bool Changed = false;
1865 // If this load follows a GEP, see if we can PRE the indices before analyzing.
1866 if (GetElementPtrInst *GEP =
1867 dyn_cast<GetElementPtrInst>(Load->getOperand(0))) {
1868 for (Use &U : GEP->indices())
1869 if (Instruction *I = dyn_cast<Instruction>(U.get()))
1870 Changed |= performScalarPRE(I);
1871 }
1872
1873 // Step 2: Analyze the availability of the load
1874 AvailValInBlkVect ValuesPerBlock;
1875 UnavailBlkVect UnavailableBlocks;
1876 AnalyzeLoadAvailability(Load, Deps, ValuesPerBlock, UnavailableBlocks);
1877
1878 // If we have no predecessors that produce a known value for this load, exit
1879 // early.
1880 if (ValuesPerBlock.empty())
1881 return Changed;
1882
1883 // Step 3: Eliminate fully redundancy.
1884 //
1885 // If all of the instructions we depend on produce a known value for this
1886 // load, then it is fully redundant and we can use PHI insertion to compute
1887 // its value. Insert PHIs and remove the fully redundant value now.
1888 if (UnavailableBlocks.empty()) {
1889 LLVM_DEBUG(dbgs() << "GVN REMOVING NONLOCAL LOAD: " << *Load << '\n');
1890
1891 // Perform PHI construction.
1892 Value *V = ConstructSSAForLoadSet(Load, ValuesPerBlock, *this);
1893 // ConstructSSAForLoadSet is responsible for combining metadata.
1894 Load->replaceAllUsesWith(V);
1895
1896 if (isa<PHINode>(V))
1897 V->takeName(Load);
1898 if (Instruction *I = dyn_cast<Instruction>(V))
1899 // If instruction I has debug info, then we should not update it.
1900 // Also, if I has a null DebugLoc, then it is still potentially incorrect
1901 // to propagate Load's DebugLoc because Load may not post-dominate I.
1902 if (Load->getDebugLoc() && Load->getParent() == I->getParent())
1903 I->setDebugLoc(Load->getDebugLoc());
1904 if (V->getType()->isPtrOrPtrVectorTy())
1907 ++NumGVNLoad;
1908 reportLoadElim(Load, V, ORE);
1909 return true;
1910 }
1911
1912 // Step 4: Eliminate partial redundancy.
1913 if (!isPREEnabled() || !isLoadPREEnabled())
1914 return Changed;
1915 if (!isLoadInLoopPREEnabled() && LI && LI->getLoopFor(Load->getParent()))
1916 return Changed;
1917
1918 if (performLoopLoadPRE(Load, ValuesPerBlock, UnavailableBlocks) ||
1919 PerformLoadPRE(Load, ValuesPerBlock, UnavailableBlocks))
1920 return true;
1921
1922 return Changed;
1923}
1924
1926 if (Cmp->getPredicate() == CmpInst::Predicate::ICMP_EQ)
1927 return true;
1928
1929 // Floating point comparisons can be equal, but not equivalent. Cases:
1930 // NaNs for unordered operators
1931 // +0.0 vs 0.0 for all operators
1932 if (Cmp->getPredicate() == CmpInst::Predicate::FCMP_OEQ ||
1933 (Cmp->getPredicate() == CmpInst::Predicate::FCMP_UEQ &&
1934 Cmp->getFastMathFlags().noNaNs())) {
1935 Value *LHS = Cmp->getOperand(0);
1936 Value *RHS = Cmp->getOperand(1);
1937 // If we can prove either side non-zero, then equality must imply
1938 // equivalence.
1939 // FIXME: We should do this optimization if 'no signed zeros' is
1940 // applicable via an instruction-level fast-math-flag or some other
1941 // indicator that relaxed FP semantics are being used.
1942 if (isa<ConstantFP>(LHS) && !cast<ConstantFP>(LHS)->isZero())
1943 return true;
1944 if (isa<ConstantFP>(RHS) && !cast<ConstantFP>(RHS)->isZero())
1945 return true;
1946 // TODO: Handle vector floating point constants
1947 }
1948 return false;
1949}
1950
1952 if (Cmp->getPredicate() == CmpInst::Predicate::ICMP_NE)
1953 return true;
1954
1955 // Floating point comparisons can be equal, but not equivelent. Cases:
1956 // NaNs for unordered operators
1957 // +0.0 vs 0.0 for all operators
1958 if ((Cmp->getPredicate() == CmpInst::Predicate::FCMP_ONE &&
1959 Cmp->getFastMathFlags().noNaNs()) ||
1960 Cmp->getPredicate() == CmpInst::Predicate::FCMP_UNE) {
1961 Value *LHS = Cmp->getOperand(0);
1962 Value *RHS = Cmp->getOperand(1);
1963 // If we can prove either side non-zero, then equality must imply
1964 // equivalence.
1965 // FIXME: We should do this optimization if 'no signed zeros' is
1966 // applicable via an instruction-level fast-math-flag or some other
1967 // indicator that relaxed FP semantics are being used.
1968 if (isa<ConstantFP>(LHS) && !cast<ConstantFP>(LHS)->isZero())
1969 return true;
1970 if (isa<ConstantFP>(RHS) && !cast<ConstantFP>(RHS)->isZero())
1971 return true;
1972 // TODO: Handle vector floating point constants
1973 }
1974 return false;
1975}
1976
1977
1978static bool hasUsersIn(Value *V, BasicBlock *BB) {
1979 return llvm::any_of(V->users(), [BB](User *U) {
1980 auto *I = dyn_cast<Instruction>(U);
1981 return I && I->getParent() == BB;
1982 });
1983}
1984
1985bool GVNPass::processAssumeIntrinsic(AssumeInst *IntrinsicI) {
1986 Value *V = IntrinsicI->getArgOperand(0);
1987
1988 if (ConstantInt *Cond = dyn_cast<ConstantInt>(V)) {
1989 if (Cond->isZero()) {
1990 Type *Int8Ty = Type::getInt8Ty(V->getContext());
1991 Type *PtrTy = PointerType::get(V->getContext(), 0);
1992 // Insert a new store to null instruction before the load to indicate that
1993 // this code is not reachable. FIXME: We could insert unreachable
1994 // instruction directly because we can modify the CFG.
1995 auto *NewS = new StoreInst(PoisonValue::get(Int8Ty),
1996 Constant::getNullValue(PtrTy), IntrinsicI);
1997 if (MSSAU) {
1998 const MemoryUseOrDef *FirstNonDom = nullptr;
1999 const auto *AL =
2000 MSSAU->getMemorySSA()->getBlockAccesses(IntrinsicI->getParent());
2001
2002 // If there are accesses in the current basic block, find the first one
2003 // that does not come before NewS. The new memory access is inserted
2004 // after the found access or before the terminator if no such access is
2005 // found.
2006 if (AL) {
2007 for (const auto &Acc : *AL) {
2008 if (auto *Current = dyn_cast<MemoryUseOrDef>(&Acc))
2009 if (!Current->getMemoryInst()->comesBefore(NewS)) {
2010 FirstNonDom = Current;
2011 break;
2012 }
2013 }
2014 }
2015
2016 auto *NewDef =
2017 FirstNonDom ? MSSAU->createMemoryAccessBefore(
2018 NewS, nullptr,
2019 const_cast<MemoryUseOrDef *>(FirstNonDom))
2020 : MSSAU->createMemoryAccessInBB(
2021 NewS, nullptr,
2022 NewS->getParent(), MemorySSA::BeforeTerminator);
2023
2024 MSSAU->insertDef(cast<MemoryDef>(NewDef), /*RenameUses=*/false);
2025 }
2026 }
2027 if (isAssumeWithEmptyBundle(*IntrinsicI)) {
2028 markInstructionForDeletion(IntrinsicI);
2029 return true;
2030 }
2031 return false;
2032 }
2033
2034 if (isa<Constant>(V)) {
2035 // If it's not false, and constant, it must evaluate to true. This means our
2036 // assume is assume(true), and thus, pointless, and we don't want to do
2037 // anything more here.
2038 return false;
2039 }
2040
2041 Constant *True = ConstantInt::getTrue(V->getContext());
2042 bool Changed = false;
2043
2044 for (BasicBlock *Successor : successors(IntrinsicI->getParent())) {
2045 BasicBlockEdge Edge(IntrinsicI->getParent(), Successor);
2046
2047 // This property is only true in dominated successors, propagateEquality
2048 // will check dominance for us.
2049 Changed |= propagateEquality(V, True, Edge, false);
2050 }
2051
2052 // We can replace assume value with true, which covers cases like this:
2053 // call void @llvm.assume(i1 %cmp)
2054 // br i1 %cmp, label %bb1, label %bb2 ; will change %cmp to true
2055 ReplaceOperandsWithMap[V] = True;
2056
2057 // Similarly, after assume(!NotV) we know that NotV == false.
2058 Value *NotV;
2059 if (match(V, m_Not(m_Value(NotV))))
2060 ReplaceOperandsWithMap[NotV] = ConstantInt::getFalse(V->getContext());
2061
2062 // If we find an equality fact, canonicalize all dominated uses in this block
2063 // to one of the two values. We heuristically choice the "oldest" of the
2064 // two where age is determined by value number. (Note that propagateEquality
2065 // above handles the cross block case.)
2066 //
2067 // Key case to cover are:
2068 // 1)
2069 // %cmp = fcmp oeq float 3.000000e+00, %0 ; const on lhs could happen
2070 // call void @llvm.assume(i1 %cmp)
2071 // ret float %0 ; will change it to ret float 3.000000e+00
2072 // 2)
2073 // %load = load float, float* %addr
2074 // %cmp = fcmp oeq float %load, %0
2075 // call void @llvm.assume(i1 %cmp)
2076 // ret float %load ; will change it to ret float %0
2077 if (auto *CmpI = dyn_cast<CmpInst>(V)) {
2078 if (impliesEquivalanceIfTrue(CmpI)) {
2079 Value *CmpLHS = CmpI->getOperand(0);
2080 Value *CmpRHS = CmpI->getOperand(1);
2081 // Heuristically pick the better replacement -- the choice of heuristic
2082 // isn't terribly important here, but the fact we canonicalize on some
2083 // replacement is for exposing other simplifications.
2084 // TODO: pull this out as a helper function and reuse w/existing
2085 // (slightly different) logic.
2086 if (isa<Constant>(CmpLHS) && !isa<Constant>(CmpRHS))
2087 std::swap(CmpLHS, CmpRHS);
2088 if (!isa<Instruction>(CmpLHS) && isa<Instruction>(CmpRHS))
2089 std::swap(CmpLHS, CmpRHS);
2090 if ((isa<Argument>(CmpLHS) && isa<Argument>(CmpRHS)) ||
2091 (isa<Instruction>(CmpLHS) && isa<Instruction>(CmpRHS))) {
2092 // Move the 'oldest' value to the right-hand side, using the value
2093 // number as a proxy for age.
2094 uint32_t LVN = VN.lookupOrAdd(CmpLHS);
2095 uint32_t RVN = VN.lookupOrAdd(CmpRHS);
2096 if (LVN < RVN)
2097 std::swap(CmpLHS, CmpRHS);
2098 }
2099
2100 // Handle degenerate case where we either haven't pruned a dead path or a
2101 // removed a trivial assume yet.
2102 if (isa<Constant>(CmpLHS) && isa<Constant>(CmpRHS))
2103 return Changed;
2104
2105 LLVM_DEBUG(dbgs() << "Replacing dominated uses of "
2106 << *CmpLHS << " with "
2107 << *CmpRHS << " in block "
2108 << IntrinsicI->getParent()->getName() << "\n");
2109
2110
2111 // Setup the replacement map - this handles uses within the same block
2112 if (hasUsersIn(CmpLHS, IntrinsicI->getParent()))
2113 ReplaceOperandsWithMap[CmpLHS] = CmpRHS;
2114
2115 // NOTE: The non-block local cases are handled by the call to
2116 // propagateEquality above; this block is just about handling the block
2117 // local cases. TODO: There's a bunch of logic in propagateEqualiy which
2118 // isn't duplicated for the block local case, can we share it somehow?
2119 }
2120 }
2121 return Changed;
2122}
2123
2126 I->replaceAllUsesWith(Repl);
2127}
2128
2129/// Attempt to eliminate a load, first by eliminating it
2130/// locally, and then attempting non-local elimination if that fails.
2131bool GVNPass::processLoad(LoadInst *L) {
2132 if (!MD)
2133 return false;
2134
2135 // This code hasn't been audited for ordered or volatile memory access
2136 if (!L->isUnordered())
2137 return false;
2138
2139 if (L->use_empty()) {
2141 return true;
2142 }
2143
2144 // ... to a pointer that has been loaded from before...
2145 MemDepResult Dep = MD->getDependency(L);
2146
2147 // If it is defined in another block, try harder.
2148 if (Dep.isNonLocal())
2149 return processNonLocalLoad(L);
2150
2151 // Only handle the local case below
2152 if (!Dep.isLocal()) {
2153 // This might be a NonFuncLocal or an Unknown
2154 LLVM_DEBUG(
2155 // fast print dep, using operator<< on instruction is too slow.
2156 dbgs() << "GVN: load "; L->printAsOperand(dbgs());
2157 dbgs() << " has unknown dependence\n";);
2158 return false;
2159 }
2160
2161 auto AV = AnalyzeLoadAvailability(L, Dep, L->getPointerOperand());
2162 if (!AV)
2163 return false;
2164
2165 Value *AvailableValue = AV->MaterializeAdjustedValue(L, L, *this);
2166
2167 // MaterializeAdjustedValue is responsible for combining metadata.
2168 L->replaceAllUsesWith(AvailableValue);
2170 if (MSSAU)
2171 MSSAU->removeMemoryAccess(L);
2172 ++NumGVNLoad;
2174 // Tell MDA to reexamine the reused pointer since we might have more
2175 // information after forwarding it.
2176 if (MD && AvailableValue->getType()->isPtrOrPtrVectorTy())
2178 return true;
2179}
2180
2181/// Return a pair the first field showing the value number of \p Exp and the
2182/// second field showing whether it is a value number newly created.
2183std::pair<uint32_t, bool>
2184GVNPass::ValueTable::assignExpNewValueNum(Expression &Exp) {
2185 uint32_t &e = expressionNumbering[Exp];
2186 bool CreateNewValNum = !e;
2187 if (CreateNewValNum) {
2188 Expressions.push_back(Exp);
2189 if (ExprIdx.size() < nextValueNumber + 1)
2190 ExprIdx.resize(nextValueNumber * 2);
2191 e = nextValueNumber;
2192 ExprIdx[nextValueNumber++] = nextExprNumber++;
2193 }
2194 return {e, CreateNewValNum};
2195}
2196
2197/// Return whether all the values related with the same \p num are
2198/// defined in \p BB.
2199bool GVNPass::ValueTable::areAllValsInBB(uint32_t Num, const BasicBlock *BB,
2200 GVNPass &Gvn) {
2201 LeaderTableEntry *Vals = &Gvn.LeaderTable[Num];
2202 while (Vals && Vals->BB == BB)
2203 Vals = Vals->Next;
2204 return !Vals;
2205}
2206
2207/// Wrap phiTranslateImpl to provide caching functionality.
2208uint32_t GVNPass::ValueTable::phiTranslate(const BasicBlock *Pred,
2209 const BasicBlock *PhiBlock,
2210 uint32_t Num, GVNPass &Gvn) {
2211 auto FindRes = PhiTranslateTable.find({Num, Pred});
2212 if (FindRes != PhiTranslateTable.end())
2213 return FindRes->second;
2214 uint32_t NewNum = phiTranslateImpl(Pred, PhiBlock, Num, Gvn);
2215 PhiTranslateTable.insert({{Num, Pred}, NewNum});
2216 return NewNum;
2217}
2218
2219// Return true if the value number \p Num and NewNum have equal value.
2220// Return false if the result is unknown.
2221bool GVNPass::ValueTable::areCallValsEqual(uint32_t Num, uint32_t NewNum,
2222 const BasicBlock *Pred,
2223 const BasicBlock *PhiBlock,
2224 GVNPass &Gvn) {
2225 CallInst *Call = nullptr;
2226 LeaderTableEntry *Vals = &Gvn.LeaderTable[Num];
2227 while (Vals) {
2228 Call = dyn_cast<CallInst>(Vals->Val);
2229 if (Call && Call->getParent() == PhiBlock)
2230 break;
2231 Vals = Vals->Next;
2232 }
2233
2234 if (AA->doesNotAccessMemory(Call))
2235 return true;
2236
2237 if (!MD || !AA->onlyReadsMemory(Call))
2238 return false;
2239
2240 MemDepResult local_dep = MD->getDependency(Call);
2241 if (!local_dep.isNonLocal())
2242 return false;
2243
2245 MD->getNonLocalCallDependency(Call);
2246
2247 // Check to see if the Call has no function local clobber.
2248 for (const NonLocalDepEntry &D : deps) {
2249 if (D.getResult().isNonFuncLocal())
2250 return true;
2251 }
2252 return false;
2253}
2254
2255/// Translate value number \p Num using phis, so that it has the values of
2256/// the phis in BB.
2257uint32_t GVNPass::ValueTable::phiTranslateImpl(const BasicBlock *Pred,
2258 const BasicBlock *PhiBlock,
2259 uint32_t Num, GVNPass &Gvn) {
2260 if (PHINode *PN = NumberingPhi[Num]) {
2261 for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) {
2262 if (PN->getParent() == PhiBlock && PN->getIncomingBlock(i) == Pred)
2263 if (uint32_t TransVal = lookup(PN->getIncomingValue(i), false))
2264 return TransVal;
2265 }
2266 return Num;
2267 }
2268
2269 // If there is any value related with Num is defined in a BB other than
2270 // PhiBlock, it cannot depend on a phi in PhiBlock without going through
2271 // a backedge. We can do an early exit in that case to save compile time.
2272 if (!areAllValsInBB(Num, PhiBlock, Gvn))
2273 return Num;
2274
2275 if (Num >= ExprIdx.size() || ExprIdx[Num] == 0)
2276 return Num;
2277 Expression Exp = Expressions[ExprIdx[Num]];
2278
2279 for (unsigned i = 0; i < Exp.varargs.size(); i++) {
2280 // For InsertValue and ExtractValue, some varargs are index numbers
2281 // instead of value numbers. Those index numbers should not be
2282 // translated.
2283 if ((i > 1 && Exp.opcode == Instruction::InsertValue) ||
2284 (i > 0 && Exp.opcode == Instruction::ExtractValue) ||
2285 (i > 1 && Exp.opcode == Instruction::ShuffleVector))
2286 continue;
2287 Exp.varargs[i] = phiTranslate(Pred, PhiBlock, Exp.varargs[i], Gvn);
2288 }
2289
2290 if (Exp.commutative) {
2291 assert(Exp.varargs.size() >= 2 && "Unsupported commutative instruction!");
2292 if (Exp.varargs[0] > Exp.varargs[1]) {
2293 std::swap(Exp.varargs[0], Exp.varargs[1]);
2294 uint32_t Opcode = Exp.opcode >> 8;
2295 if (Opcode == Instruction::ICmp || Opcode == Instruction::FCmp)
2296 Exp.opcode = (Opcode << 8) |
2298 static_cast<CmpInst::Predicate>(Exp.opcode & 255));
2299 }
2300 }
2301
2302 if (uint32_t NewNum = expressionNumbering[Exp]) {
2303 if (Exp.opcode == Instruction::Call && NewNum != Num)
2304 return areCallValsEqual(Num, NewNum, Pred, PhiBlock, Gvn) ? NewNum : Num;
2305 return NewNum;
2306 }
2307 return Num;
2308}
2309
2310/// Erase stale entry from phiTranslate cache so phiTranslate can be computed
2311/// again.
2312void GVNPass::ValueTable::eraseTranslateCacheEntry(
2313 uint32_t Num, const BasicBlock &CurrBlock) {
2314 for (const BasicBlock *Pred : predecessors(&CurrBlock))
2315 PhiTranslateTable.erase({Num, Pred});
2316}
2317
2318// In order to find a leader for a given value number at a
2319// specific basic block, we first obtain the list of all Values for that number,
2320// and then scan the list to find one whose block dominates the block in
2321// question. This is fast because dominator tree queries consist of only
2322// a few comparisons of DFS numbers.
2323Value *GVNPass::findLeader(const BasicBlock *BB, uint32_t num) {
2324 LeaderTableEntry Vals = LeaderTable[num];
2325 if (!Vals.Val) return nullptr;
2326
2327 Value *Val = nullptr;
2328 if (DT->dominates(Vals.BB, BB)) {
2329 Val = Vals.Val;
2330 if (isa<Constant>(Val)) return Val;
2331 }
2332
2333 LeaderTableEntry* Next = Vals.Next;
2334 while (Next) {
2335 if (DT->dominates(Next->BB, BB)) {
2336 if (isa<Constant>(Next->Val)) return Next->Val;
2337 if (!Val) Val = Next->Val;
2338 }
2339
2340 Next = Next->Next;
2341 }
2342
2343 return Val;
2344}
2345
2346/// There is an edge from 'Src' to 'Dst'. Return
2347/// true if every path from the entry block to 'Dst' passes via this edge. In
2348/// particular 'Dst' must not be reachable via another edge from 'Src'.
2350 DominatorTree *DT) {
2351 // While in theory it is interesting to consider the case in which Dst has
2352 // more than one predecessor, because Dst might be part of a loop which is
2353 // only reachable from Src, in practice it is pointless since at the time
2354 // GVN runs all such loops have preheaders, which means that Dst will have
2355 // been changed to have only one predecessor, namely Src.
2356 const BasicBlock *Pred = E.getEnd()->getSinglePredecessor();
2357 assert((!Pred || Pred == E.getStart()) &&
2358 "No edge between these basic blocks!");
2359 return Pred != nullptr;
2360}
2361
2362void GVNPass::assignBlockRPONumber(Function &F) {
2363 BlockRPONumber.clear();
2364 uint32_t NextBlockNumber = 1;
2366 for (BasicBlock *BB : RPOT)
2367 BlockRPONumber[BB] = NextBlockNumber++;
2368 InvalidBlockRPONumbers = false;
2369}
2370
2371bool GVNPass::replaceOperandsForInBlockEquality(Instruction *Instr) const {
2372 bool Changed = false;
2373 for (unsigned OpNum = 0; OpNum < Instr->getNumOperands(); ++OpNum) {
2374 Value *Operand = Instr->getOperand(OpNum);
2375 auto it = ReplaceOperandsWithMap.find(Operand);
2376 if (it != ReplaceOperandsWithMap.end()) {
2377 LLVM_DEBUG(dbgs() << "GVN replacing: " << *Operand << " with "
2378 << *it->second << " in instruction " << *Instr << '\n');
2379 Instr->setOperand(OpNum, it->second);
2380 Changed = true;
2381 }
2382 }
2383 return Changed;
2384}
2385
2386/// The given values are known to be equal in every block
2387/// dominated by 'Root'. Exploit this, for example by replacing 'LHS' with
2388/// 'RHS' everywhere in the scope. Returns whether a change was made.
2389/// If DominatesByEdge is false, then it means that we will propagate the RHS
2390/// value starting from the end of Root.Start.
2391bool GVNPass::propagateEquality(Value *LHS, Value *RHS,
2392 const BasicBlockEdge &Root,
2393 bool DominatesByEdge) {
2395 Worklist.push_back(std::make_pair(LHS, RHS));
2396 bool Changed = false;
2397 // For speed, compute a conservative fast approximation to
2398 // DT->dominates(Root, Root.getEnd());
2399 const bool RootDominatesEnd = isOnlyReachableViaThisEdge(Root, DT);
2400
2401 while (!Worklist.empty()) {
2402 std::pair<Value*, Value*> Item = Worklist.pop_back_val();
2403 LHS = Item.first; RHS = Item.second;
2404
2405 if (LHS == RHS)
2406 continue;
2407 assert(LHS->getType() == RHS->getType() && "Equality but unequal types!");
2408
2409 // Don't try to propagate equalities between constants.
2410 if (isa<Constant>(LHS) && isa<Constant>(RHS))
2411 continue;
2412
2413 // Prefer a constant on the right-hand side, or an Argument if no constants.
2414 if (isa<Constant>(LHS) || (isa<Argument>(LHS) && !isa<Constant>(RHS)))
2415 std::swap(LHS, RHS);
2416 assert((isa<Argument>(LHS) || isa<Instruction>(LHS)) && "Unexpected value!");
2417
2418 // If there is no obvious reason to prefer the left-hand side over the
2419 // right-hand side, ensure the longest lived term is on the right-hand side,
2420 // so the shortest lived term will be replaced by the longest lived.
2421 // This tends to expose more simplifications.
2422 uint32_t LVN = VN.lookupOrAdd(LHS);
2423 if ((isa<Argument>(LHS) && isa<Argument>(RHS)) ||
2424 (isa<Instruction>(LHS) && isa<Instruction>(RHS))) {
2425 // Move the 'oldest' value to the right-hand side, using the value number
2426 // as a proxy for age.
2427 uint32_t RVN = VN.lookupOrAdd(RHS);
2428 if (LVN < RVN) {
2429 std::swap(LHS, RHS);
2430 LVN = RVN;
2431 }
2432 }
2433
2434 // If value numbering later sees that an instruction in the scope is equal
2435 // to 'LHS' then ensure it will be turned into 'RHS'. In order to preserve
2436 // the invariant that instructions only occur in the leader table for their
2437 // own value number (this is used by removeFromLeaderTable), do not do this
2438 // if RHS is an instruction (if an instruction in the scope is morphed into
2439 // LHS then it will be turned into RHS by the next GVN iteration anyway, so
2440 // using the leader table is about compiling faster, not optimizing better).
2441 // The leader table only tracks basic blocks, not edges. Only add to if we
2442 // have the simple case where the edge dominates the end.
2443 if (RootDominatesEnd && !isa<Instruction>(RHS))
2444 addToLeaderTable(LVN, RHS, Root.getEnd());
2445
2446 // Replace all occurrences of 'LHS' with 'RHS' everywhere in the scope. As
2447 // LHS always has at least one use that is not dominated by Root, this will
2448 // never do anything if LHS has only one use.
2449 if (!LHS->hasOneUse()) {
2450 unsigned NumReplacements =
2451 DominatesByEdge
2452 ? replaceDominatedUsesWith(LHS, RHS, *DT, Root)
2453 : replaceDominatedUsesWith(LHS, RHS, *DT, Root.getStart());
2454
2455 Changed |= NumReplacements > 0;
2456 NumGVNEqProp += NumReplacements;
2457 // Cached information for anything that uses LHS will be invalid.
2458 if (MD)
2460 }
2461
2462 // Now try to deduce additional equalities from this one. For example, if
2463 // the known equality was "(A != B)" == "false" then it follows that A and B
2464 // are equal in the scope. Only boolean equalities with an explicit true or
2465 // false RHS are currently supported.
2466 if (!RHS->getType()->isIntegerTy(1))
2467 // Not a boolean equality - bail out.
2468 continue;
2469 ConstantInt *CI = dyn_cast<ConstantInt>(RHS);
2470 if (!CI)
2471 // RHS neither 'true' nor 'false' - bail out.
2472 continue;
2473 // Whether RHS equals 'true'. Otherwise it equals 'false'.
2474 bool isKnownTrue = CI->isMinusOne();
2475 bool isKnownFalse = !isKnownTrue;
2476
2477 // If "A && B" is known true then both A and B are known true. If "A || B"
2478 // is known false then both A and B are known false.
2479 Value *A, *B;
2480 if ((isKnownTrue && match(LHS, m_LogicalAnd(m_Value(A), m_Value(B)))) ||
2481 (isKnownFalse && match(LHS, m_LogicalOr(m_Value(A), m_Value(B))))) {
2482 Worklist.push_back(std::make_pair(A, RHS));
2483 Worklist.push_back(std::make_pair(B, RHS));
2484 continue;
2485 }
2486
2487 // If we are propagating an equality like "(A == B)" == "true" then also
2488 // propagate the equality A == B. When propagating a comparison such as
2489 // "(A >= B)" == "true", replace all instances of "A < B" with "false".
2490 if (CmpInst *Cmp = dyn_cast<CmpInst>(LHS)) {
2491 Value *Op0 = Cmp->getOperand(0), *Op1 = Cmp->getOperand(1);
2492
2493 // If "A == B" is known true, or "A != B" is known false, then replace
2494 // A with B everywhere in the scope. For floating point operations, we
2495 // have to be careful since equality does not always imply equivalance.
2496 if ((isKnownTrue && impliesEquivalanceIfTrue(Cmp)) ||
2497 (isKnownFalse && impliesEquivalanceIfFalse(Cmp)))
2498 Worklist.push_back(std::make_pair(Op0, Op1));
2499
2500 // If "A >= B" is known true, replace "A < B" with false everywhere.
2501 CmpInst::Predicate NotPred = Cmp->getInversePredicate();
2502 Constant *NotVal = ConstantInt::get(Cmp->getType(), isKnownFalse);
2503 // Since we don't have the instruction "A < B" immediately to hand, work
2504 // out the value number that it would have and use that to find an
2505 // appropriate instruction (if any).
2506 uint32_t NextNum = VN.getNextUnusedValueNumber();
2507 uint32_t Num = VN.lookupOrAddCmp(Cmp->getOpcode(), NotPred, Op0, Op1);
2508 // If the number we were assigned was brand new then there is no point in
2509 // looking for an instruction realizing it: there cannot be one!
2510 if (Num < NextNum) {
2511 Value *NotCmp = findLeader(Root.getEnd(), Num);
2512 if (NotCmp && isa<Instruction>(NotCmp)) {
2513 unsigned NumReplacements =
2514 DominatesByEdge
2515 ? replaceDominatedUsesWith(NotCmp, NotVal, *DT, Root)
2516 : replaceDominatedUsesWith(NotCmp, NotVal, *DT,
2517 Root.getStart());
2518 Changed |= NumReplacements > 0;
2519 NumGVNEqProp += NumReplacements;
2520 // Cached information for anything that uses NotCmp will be invalid.
2521 if (MD)
2522 MD->invalidateCachedPointerInfo(NotCmp);
2523 }
2524 }
2525 // Ensure that any instruction in scope that gets the "A < B" value number
2526 // is replaced with false.
2527 // The leader table only tracks basic blocks, not edges. Only add to if we
2528 // have the simple case where the edge dominates the end.
2529 if (RootDominatesEnd)
2530 addToLeaderTable(Num, NotVal, Root.getEnd());
2531
2532 continue;
2533 }
2534 }
2535
2536 return Changed;
2537}
2538
2539/// When calculating availability, handle an instruction
2540/// by inserting it into the appropriate sets
2541bool GVNPass::processInstruction(Instruction *I) {
2542 // Ignore dbg info intrinsics.
2543 if (isa<DbgInfoIntrinsic>(I))
2544 return false;
2545
2546 // If the instruction can be easily simplified then do so now in preference
2547 // to value numbering it. Value numbering often exposes redundancies, for
2548 // example if it determines that %y is equal to %x then the instruction
2549 // "%z = and i32 %x, %y" becomes "%z = and i32 %x, %x" which we now simplify.
2550 const DataLayout &DL = I->getModule()->getDataLayout();
2551 if (Value *V = simplifyInstruction(I, {DL, TLI, DT, AC})) {
2552 bool Changed = false;
2553 if (!I->use_empty()) {
2554 // Simplification can cause a special instruction to become not special.
2555 // For example, devirtualization to a willreturn function.
2556 ICF->removeUsersOf(I);
2557 I->replaceAllUsesWith(V);
2558 Changed = true;
2559 }
2560 if (isInstructionTriviallyDead(I, TLI)) {
2562 Changed = true;
2563 }
2564 if (Changed) {
2565 if (MD && V->getType()->isPtrOrPtrVectorTy())
2567 ++NumGVNSimpl;
2568 return true;
2569 }
2570 }
2571
2572 if (auto *Assume = dyn_cast<AssumeInst>(I))
2573 return processAssumeIntrinsic(Assume);
2574
2575 if (LoadInst *Load = dyn_cast<LoadInst>(I)) {
2576 if (processLoad(Load))
2577 return true;
2578
2579 unsigned Num = VN.lookupOrAdd(Load);
2580 addToLeaderTable(Num, Load, Load->getParent());
2581 return false;
2582 }
2583
2584 // For conditional branches, we can perform simple conditional propagation on
2585 // the condition value itself.
2586 if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
2587 if (!BI->isConditional())
2588 return false;
2589
2590 if (isa<Constant>(BI->getCondition()))
2591 return processFoldableCondBr(BI);
2592
2593 Value *BranchCond = BI->getCondition();
2594 BasicBlock *TrueSucc = BI->getSuccessor(0);
2595 BasicBlock *FalseSucc = BI->getSuccessor(1);
2596 // Avoid multiple edges early.
2597 if (TrueSucc == FalseSucc)
2598 return false;
2599
2600 BasicBlock *Parent = BI->getParent();
2601 bool Changed = false;
2602
2604 BasicBlockEdge TrueE(Parent, TrueSucc);
2605 Changed |= propagateEquality(BranchCond, TrueVal, TrueE, true);
2606
2608 BasicBlockEdge FalseE(Parent, FalseSucc);
2609 Changed |= propagateEquality(BranchCond, FalseVal, FalseE, true);
2610
2611 return Changed;
2612 }
2613
2614 // For switches, propagate the case values into the case destinations.
2615 if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
2616 Value *SwitchCond = SI->getCondition();
2617 BasicBlock *Parent = SI->getParent();
2618 bool Changed = false;
2619
2620 // Remember how many outgoing edges there are to every successor.
2622 for (unsigned i = 0, n = SI->getNumSuccessors(); i != n; ++i)
2623 ++SwitchEdges[SI->getSuccessor(i)];
2624
2625 for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
2626 i != e; ++i) {
2627 BasicBlock *Dst = i->getCaseSuccessor();
2628 // If there is only a single edge, propagate the case value into it.
2629 if (SwitchEdges.lookup(Dst) == 1) {
2630 BasicBlockEdge E(Parent, Dst);
2631 Changed |= propagateEquality(SwitchCond, i->getCaseValue(), E, true);
2632 }
2633 }
2634 return Changed;
2635 }
2636
2637 // Instructions with void type don't return a value, so there's
2638 // no point in trying to find redundancies in them.
2639 if (I->getType()->isVoidTy())
2640 return false;
2641
2642 uint32_t NextNum = VN.getNextUnusedValueNumber();
2643 unsigned Num = VN.lookupOrAdd(I);
2644
2645 // Allocations are always uniquely numbered, so we can save time and memory
2646 // by fast failing them.
2647 if (isa<AllocaInst>(I) || I->isTerminator() || isa<PHINode>(I)) {
2648 addToLeaderTable(Num, I, I->getParent());
2649 return false;
2650 }
2651
2652 // If the number we were assigned was a brand new VN, then we don't
2653 // need to do a lookup to see if the number already exists
2654 // somewhere in the domtree: it can't!
2655 if (Num >= NextNum) {
2656 addToLeaderTable(Num, I, I->getParent());
2657 return false;
2658 }
2659
2660 // Perform fast-path value-number based elimination of values inherited from
2661 // dominators.
2662 Value *Repl = findLeader(I->getParent(), Num);
2663 if (!Repl) {
2664 // Failure, just remember this instance for future use.
2665 addToLeaderTable(Num, I, I->getParent());
2666 return false;
2667 }
2668
2669 if (Repl == I) {
2670 // If I was the result of a shortcut PRE, it might already be in the table
2671 // and the best replacement for itself. Nothing to do.
2672 return false;
2673 }
2674
2675 // Remove it!
2677 if (MD && Repl->getType()->isPtrOrPtrVectorTy())
2680 return true;
2681}
2682
2683/// runOnFunction - This is the main transformation entry point for a function.
2684bool GVNPass::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
2685 const TargetLibraryInfo &RunTLI, AAResults &RunAA,
2687 OptimizationRemarkEmitter *RunORE, MemorySSA *MSSA) {
2688 AC = &RunAC;
2689 DT = &RunDT;
2690 VN.setDomTree(DT);
2691 TLI = &RunTLI;
2692 VN.setAliasAnalysis(&RunAA);
2693 MD = RunMD;
2694 ImplicitControlFlowTracking ImplicitCFT;
2695 ICF = &ImplicitCFT;
2696 this->LI = LI;
2697 VN.setMemDep(MD);
2698 ORE = RunORE;
2699 InvalidBlockRPONumbers = true;
2700 MemorySSAUpdater Updater(MSSA);
2701 MSSAU = MSSA ? &Updater : nullptr;
2702
2703 bool Changed = false;
2704 bool ShouldContinue = true;
2705
2707 // Merge unconditional branches, allowing PRE to catch more
2708 // optimization opportunities.
2710 bool removedBlock = MergeBlockIntoPredecessor(&BB, &DTU, LI, MSSAU, MD);
2711 if (removedBlock)
2712 ++NumGVNBlocks;
2713
2714 Changed |= removedBlock;
2715 }
2716
2717 unsigned Iteration = 0;
2718 while (ShouldContinue) {
2719 LLVM_DEBUG(dbgs() << "GVN iteration: " << Iteration << "\n");
2720 (void) Iteration;
2721 ShouldContinue = iterateOnFunction(F);
2722 Changed |= ShouldContinue;
2723 ++Iteration;
2724 }
2725
2726 if (isPREEnabled()) {
2727 // Fabricate val-num for dead-code in order to suppress assertion in
2728 // performPRE().
2729 assignValNumForDeadCode();
2730 bool PREChanged = true;
2731 while (PREChanged) {
2732 PREChanged = performPRE(F);
2733 Changed |= PREChanged;
2734 }
2735 }
2736
2737 // FIXME: Should perform GVN again after PRE does something. PRE can move
2738 // computations into blocks where they become fully redundant. Note that
2739 // we can't do this until PRE's critical edge splitting updates memdep.
2740 // Actually, when this happens, we should just fully integrate PRE into GVN.
2741
2742 cleanupGlobalSets();
2743 // Do not cleanup DeadBlocks in cleanupGlobalSets() as it's called for each
2744 // iteration.
2745 DeadBlocks.clear();
2746
2747 if (MSSA && VerifyMemorySSA)
2748 MSSA->verifyMemorySSA();
2749
2750 return Changed;
2751}
2752
2753bool GVNPass::processBlock(BasicBlock *BB) {
2754 // FIXME: Kill off InstrsToErase by doing erasing eagerly in a helper function
2755 // (and incrementing BI before processing an instruction).
2756 assert(InstrsToErase.empty() &&
2757 "We expect InstrsToErase to be empty across iterations");
2758 if (DeadBlocks.count(BB))
2759 return false;
2760
2761 // Clearing map before every BB because it can be used only for single BB.
2762 ReplaceOperandsWithMap.clear();
2763 bool ChangedFunction = false;
2764
2765 // Since we may not have visited the input blocks of the phis, we can't
2766 // use our normal hash approach for phis. Instead, simply look for
2767 // obvious duplicates. The first pass of GVN will tend to create
2768 // identical phis, and the second or later passes can eliminate them.
2769 SmallPtrSet<PHINode *, 8> PHINodesToRemove;
2770 ChangedFunction |= EliminateDuplicatePHINodes(BB, PHINodesToRemove);
2771 for (PHINode *PN : PHINodesToRemove) {
2772 VN.erase(PN);
2773 removeInstruction(PN);
2774 }
2775
2776 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
2777 BI != BE;) {
2778 if (!ReplaceOperandsWithMap.empty())
2779 ChangedFunction |= replaceOperandsForInBlockEquality(&*BI);
2780 ChangedFunction |= processInstruction(&*BI);
2781
2782 if (InstrsToErase.empty()) {
2783 ++BI;
2784 continue;
2785 }
2786
2787 // If we need some instructions deleted, do it now.
2788 NumGVNInstr += InstrsToErase.size();
2789
2790 // Avoid iterator invalidation.
2791 bool AtStart = BI == BB->begin();
2792 if (!AtStart)
2793 --BI;
2794
2795 for (auto *I : InstrsToErase) {
2796 assert(I->getParent() == BB && "Removing instruction from wrong block?");
2797 LLVM_DEBUG(dbgs() << "GVN removed: " << *I << '\n');
2798 salvageKnowledge(I, AC);
2800 removeInstruction(I);
2801 }
2802 InstrsToErase.clear();
2803
2804 if (AtStart)
2805 BI = BB->begin();
2806 else
2807 ++BI;
2808 }
2809
2810 return ChangedFunction;
2811}
2812
2813// Instantiate an expression in a predecessor that lacked it.
2814bool GVNPass::performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
2815 BasicBlock *Curr, unsigned int ValNo) {
2816 // Because we are going top-down through the block, all value numbers
2817 // will be available in the predecessor by the time we need them. Any
2818 // that weren't originally present will have been instantiated earlier
2819 // in this loop.
2820 bool success = true;
2821 for (unsigned i = 0, e = Instr->getNumOperands(); i != e; ++i) {
2822 Value *Op = Instr->getOperand(i);
2823 if (isa<Argument>(Op) || isa<Constant>(Op) || isa<GlobalValue>(Op))
2824 continue;
2825 // This could be a newly inserted instruction, in which case, we won't
2826 // find a value number, and should give up before we hurt ourselves.
2827 // FIXME: Rewrite the infrastructure to let it easier to value number
2828 // and process newly inserted instructions.
2829 if (!VN.exists(Op)) {
2830 success = false;
2831 break;
2832 }
2833 uint32_t TValNo =
2834 VN.phiTranslate(Pred, Curr, VN.lookup(Op), *this);
2835 if (Value *V = findLeader(Pred, TValNo)) {
2836 Instr->setOperand(i, V);
2837 } else {
2838 success = false;
2839 break;
2840 }
2841 }
2842
2843 // Fail out if we encounter an operand that is not available in
2844 // the PRE predecessor. This is typically because of loads which
2845 // are not value numbered precisely.
2846 if (!success)
2847 return false;
2848
2849 Instr->insertBefore(Pred->getTerminator());
2850 Instr->setName(Instr->getName() + ".pre");
2851 Instr->setDebugLoc(Instr->getDebugLoc());
2852
2853 ICF->insertInstructionTo(Instr, Pred);
2854
2855 unsigned Num = VN.lookupOrAdd(Instr);
2856 VN.add(Instr, Num);
2857
2858 // Update the availability map to include the new instruction.
2859 addToLeaderTable(Num, Instr, Pred);
2860 return true;
2861}
2862
2863bool GVNPass::performScalarPRE(Instruction *CurInst) {
2864 if (isa<AllocaInst>(CurInst) || CurInst->isTerminator() ||
2865 isa<PHINode>(CurInst) || CurInst->getType()->isVoidTy() ||
2866 CurInst->mayReadFromMemory() || CurInst->mayHaveSideEffects() ||
2867 isa<DbgInfoIntrinsic>(CurInst))
2868 return false;
2869
2870 // Don't do PRE on compares. The PHI would prevent CodeGenPrepare from
2871 // sinking the compare again, and it would force the code generator to
2872 // move the i1 from processor flags or predicate registers into a general
2873 // purpose register.
2874 if (isa<CmpInst>(CurInst))
2875 return false;
2876
2877 // Don't do PRE on GEPs. The inserted PHI would prevent CodeGenPrepare from
2878 // sinking the addressing mode computation back to its uses. Extending the
2879 // GEP's live range increases the register pressure, and therefore it can
2880 // introduce unnecessary spills.
2881 //
2882 // This doesn't prevent Load PRE. PHI translation will make the GEP available
2883 // to the load by moving it to the predecessor block if necessary.
2884 if (isa<GetElementPtrInst>(CurInst))
2885 return false;
2886
2887 if (auto *CallB = dyn_cast<CallBase>(CurInst)) {
2888 // We don't currently value number ANY inline asm calls.
2889 if (CallB->isInlineAsm())
2890 return false;
2891 }
2892
2893 uint32_t ValNo = VN.lookup(CurInst);
2894
2895 // Look for the predecessors for PRE opportunities. We're
2896 // only trying to solve the basic diamond case, where
2897 // a value is computed in the successor and one predecessor,
2898 // but not the other. We also explicitly disallow cases
2899 // where the successor is its own predecessor, because they're
2900 // more complicated to get right.
2901 unsigned NumWith = 0;
2902 unsigned NumWithout = 0;
2903 BasicBlock *PREPred = nullptr;
2904 BasicBlock *CurrentBlock = CurInst->getParent();
2905
2906 // Update the RPO numbers for this function.
2907 if (InvalidBlockRPONumbers)
2908 assignBlockRPONumber(*CurrentBlock->getParent());
2909
2911 for (BasicBlock *P : predecessors(CurrentBlock)) {
2912 // We're not interested in PRE where blocks with predecessors that are
2913 // not reachable.
2914 if (!DT->isReachableFromEntry(P)) {
2915 NumWithout = 2;
2916 break;
2917 }
2918 // It is not safe to do PRE when P->CurrentBlock is a loop backedge.
2919 assert(BlockRPONumber.count(P) && BlockRPONumber.count(CurrentBlock) &&
2920 "Invalid BlockRPONumber map.");
2921 if (BlockRPONumber[P] >= BlockRPONumber[CurrentBlock]) {
2922 NumWithout = 2;
2923 break;
2924 }
2925
2926 uint32_t TValNo = VN.phiTranslate(P, CurrentBlock, ValNo, *this);
2927 Value *predV = findLeader(P, TValNo);
2928 if (!predV) {
2929 predMap.push_back(std::make_pair(static_cast<Value *>(nullptr), P));
2930 PREPred = P;
2931 ++NumWithout;
2932 } else if (predV == CurInst) {
2933 /* CurInst dominates this predecessor. */
2934 NumWithout = 2;
2935 break;
2936 } else {
2937 predMap.push_back(std::make_pair(predV, P));
2938 ++NumWith;
2939 }
2940 }
2941
2942 // Don't do PRE when it might increase code size, i.e. when
2943 // we would need to insert instructions in more than one pred.
2944 if (NumWithout > 1 || NumWith == 0)
2945 return false;
2946
2947 // We may have a case where all predecessors have the instruction,
2948 // and we just need to insert a phi node. Otherwise, perform
2949 // insertion.
2950 Instruction *PREInstr = nullptr;
2951
2952 if (NumWithout != 0) {
2953 if (!isSafeToSpeculativelyExecute(CurInst)) {
2954 // It is only valid to insert a new instruction if the current instruction
2955 // is always executed. An instruction with implicit control flow could
2956 // prevent us from doing it. If we cannot speculate the execution, then
2957 // PRE should be prohibited.
2958 if (ICF->isDominatedByICFIFromSameBlock(CurInst))
2959 return false;
2960 }
2961
2962 // Don't do PRE across indirect branch.
2963 if (isa<IndirectBrInst>(PREPred->getTerminator()))
2964 return false;
2965
2966 // We can't do PRE safely on a critical edge, so instead we schedule
2967 // the edge to be split and perform the PRE the next time we iterate
2968 // on the function.
2969 unsigned SuccNum = GetSuccessorNumber(PREPred, CurrentBlock);
2970 if (isCriticalEdge(PREPred->getTerminator(), SuccNum)) {
2971 toSplit.push_back(std::make_pair(PREPred->getTerminator(), SuccNum));
2972 return false;
2973 }
2974 // We need to insert somewhere, so let's give it a shot
2975 PREInstr = CurInst->clone();
2976 if (!performScalarPREInsertion(PREInstr, PREPred, CurrentBlock, ValNo)) {
2977 // If we failed insertion, make sure we remove the instruction.
2978#ifndef NDEBUG
2979 verifyRemoved(PREInstr);
2980#endif
2981 PREInstr->deleteValue();
2982 return false;
2983 }
2984 }
2985
2986 // Either we should have filled in the PRE instruction, or we should
2987 // not have needed insertions.
2988 assert(PREInstr != nullptr || NumWithout == 0);
2989
2990 ++NumGVNPRE;
2991
2992 // Create a PHI to make the value available in this block.
2993 PHINode *Phi = PHINode::Create(CurInst->getType(), predMap.size(),
2994 CurInst->getName() + ".pre-phi");
2995 Phi->insertBefore(CurrentBlock->begin());
2996 for (unsigned i = 0, e = predMap.size(); i != e; ++i) {
2997 if (Value *V = predMap[i].first) {
2998 // If we use an existing value in this phi, we have to patch the original
2999 // value because the phi will be used to replace a later value.
3000 patchReplacementInstruction(CurInst, V);
3001 Phi->addIncoming(V, predMap[i].second);
3002 } else
3003 Phi->addIncoming(PREInstr, PREPred);
3004 }
3005
3006 VN.add(Phi, ValNo);
3007 // After creating a new PHI for ValNo, the phi translate result for ValNo will
3008 // be changed, so erase the related stale entries in phi translate cache.
3009 VN.eraseTranslateCacheEntry(ValNo, *CurrentBlock);
3010 addToLeaderTable(ValNo, Phi, CurrentBlock);
3011 Phi->setDebugLoc(CurInst->getDebugLoc());
3012 CurInst->replaceAllUsesWith(Phi);
3013 if (MD && Phi->getType()->isPtrOrPtrVectorTy())
3015 VN.erase(CurInst);
3016 removeFromLeaderTable(ValNo, CurInst, CurrentBlock);
3017
3018 LLVM_DEBUG(dbgs() << "GVN PRE removed: " << *CurInst << '\n');
3019 removeInstruction(CurInst);
3020 ++NumGVNInstr;
3021
3022 return true;
3023}
3024
3025/// Perform a purely local form of PRE that looks for diamond
3026/// control flow patterns and attempts to perform simple PRE at the join point.
3027bool GVNPass::performPRE(Function &F) {
3028 bool Changed = false;
3029 for (BasicBlock *CurrentBlock : depth_first(&F.getEntryBlock())) {
3030 // Nothing to PRE in the entry block.
3031 if (CurrentBlock == &F.getEntryBlock())
3032 continue;
3033
3034 // Don't perform PRE on an EH pad.
3035 if (CurrentBlock->isEHPad())
3036 continue;
3037
3038 for (BasicBlock::iterator BI = CurrentBlock->begin(),
3039 BE = CurrentBlock->end();
3040 BI != BE;) {
3041 Instruction *CurInst = &*BI++;
3042 Changed |= performScalarPRE(CurInst);
3043 }
3044 }
3045
3046 if (splitCriticalEdges())
3047 Changed = true;
3048
3049 return Changed;
3050}
3051
3052/// Split the critical edge connecting the given two blocks, and return
3053/// the block inserted to the critical edge.
3054BasicBlock *GVNPass::splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ) {
3055 // GVN does not require loop-simplify, do not try to preserve it if it is not
3056 // possible.
3058 Pred, Succ,
3059 CriticalEdgeSplittingOptions(DT, LI, MSSAU).unsetPreserveLoopSimplify());
3060 if (BB) {
3061 if (MD)
3063 InvalidBlockRPONumbers = true;
3064 }
3065 return BB;
3066}
3067
3068/// Split critical edges found during the previous
3069/// iteration that may enable further optimization.
3070bool GVNPass::splitCriticalEdges() {
3071 if (toSplit.empty())
3072 return false;
3073
3074 bool Changed = false;
3075 do {
3076 std::pair<Instruction *, unsigned> Edge = toSplit.pop_back_val();
3077 Changed |= SplitCriticalEdge(Edge.first, Edge.second,
3078 CriticalEdgeSplittingOptions(DT, LI, MSSAU)) !=
3079 nullptr;
3080 } while (!toSplit.empty());
3081 if (Changed) {
3082 if (MD)
3084 InvalidBlockRPONumbers = true;
3085 }
3086 return Changed;
3087}
3088
3089/// Executes one iteration of GVN
3090bool GVNPass::iterateOnFunction(Function &F) {
3091 cleanupGlobalSets();
3092
3093 // Top-down walk of the dominator tree
3094 bool Changed = false;
3095 // Needed for value numbering with phi construction to work.
3096 // RPOT walks the graph in its constructor and will not be invalidated during
3097 // processBlock.
3099
3100 for (BasicBlock *BB : RPOT)
3101 Changed |= processBlock(BB);
3102
3103 return Changed;
3104}
3105
3106void GVNPass::cleanupGlobalSets() {
3107 VN.clear();
3108 LeaderTable.clear();
3109 BlockRPONumber.clear();
3110 TableAllocator.Reset();
3111 ICF->clear();
3112 InvalidBlockRPONumbers = true;
3113}
3114
3115void GVNPass::removeInstruction(Instruction *I) {
3116 if (MD) MD->removeInstruction(I);
3117 if (MSSAU)
3118 MSSAU->removeMemoryAccess(I);
3119#ifndef NDEBUG
3120 verifyRemoved(I);
3121#endif
3122 ICF->removeInstruction(I);
3123 I->eraseFromParent();
3124}
3125
3126/// Verify that the specified instruction does not occur in our
3127/// internal data structures.
3128void GVNPass::verifyRemoved(const Instruction *Inst) const {
3129 VN.verifyRemoved(Inst);
3130
3131 // Walk through the value number scope to make sure the instruction isn't
3132 // ferreted away in it.
3133 for (const auto &I : LeaderTable) {
3134 const LeaderTableEntry *Node = &I.second;
3135 assert(Node->Val != Inst && "Inst still in value numbering scope!");
3136
3137 while (Node->Next) {
3138 Node = Node->Next;
3139 assert(Node->Val != Inst && "Inst still in value numbering scope!");
3140 }
3141 }
3142}
3143
3144/// BB is declared dead, which implied other blocks become dead as well. This
3145/// function is to add all these blocks to "DeadBlocks". For the dead blocks'
3146/// live successors, update their phi nodes by replacing the operands
3147/// corresponding to dead blocks with UndefVal.
3148void GVNPass::addDeadBlock(BasicBlock *BB) {
3151
3152 NewDead.push_back(BB);
3153 while (!NewDead.empty()) {
3154 BasicBlock *D = NewDead.pop_back_val();
3155 if (DeadBlocks.count(D))
3156 continue;
3157
3158 // All blocks dominated by D are dead.
3160 DT->getDescendants(D, Dom);
3161 DeadBlocks.insert(Dom.begin(), Dom.end());
3162
3163 // Figure out the dominance-frontier(D).
3164 for (BasicBlock *B : Dom) {
3165 for (BasicBlock *S : successors(B)) {
3166 if (DeadBlocks.count(S))
3167 continue;
3168
3169 bool AllPredDead = true;
3170 for (BasicBlock *P : predecessors(S))
3171 if (!DeadBlocks.count(P)) {
3172 AllPredDead = false;
3173 break;
3174 }
3175
3176 if (!AllPredDead) {
3177 // S could be proved dead later on. That is why we don't update phi
3178 // operands at this moment.
3179 DF.insert(S);
3180 } else {
3181 // While S is not dominated by D, it is dead by now. This could take
3182 // place if S already have a dead predecessor before D is declared
3183 // dead.
3184 NewDead.push_back(S);
3185 }
3186 }
3187 }
3188 }
3189
3190 // For the dead blocks' live successors, update their phi nodes by replacing
3191 // the operands corresponding to dead blocks with UndefVal.
3192 for (BasicBlock *B : DF) {
3193 if (DeadBlocks.count(B))
3194 continue;
3195
3196 // First, split the critical edges. This might also create additional blocks
3197 // to preserve LoopSimplify form and adjust edges accordingly.
3199 for (BasicBlock *P : Preds) {
3200 if (!DeadBlocks.count(P))
3201 continue;
3202
3204 isCriticalEdge(P->getTerminator(), B)) {
3205 if (BasicBlock *S = splitCriticalEdges(P, B))
3206 DeadBlocks.insert(P = S);
3207 }
3208 }
3209
3210 // Now poison the incoming values from the dead predecessors.
3211 for (BasicBlock *P : predecessors(B)) {
3212 if (!DeadBlocks.count(P))
3213 continue;
3214 for (PHINode &Phi : B->phis()) {
3215 Phi.setIncomingValueForBlock(P, PoisonValue::get(Phi.getType()));
3216 if (MD)
3218 }
3219 }
3220 }
3221}
3222
3223// If the given branch is recognized as a foldable branch (i.e. conditional
3224// branch with constant condition), it will perform following analyses and
3225// transformation.
3226// 1) If the dead out-coming edge is a critical-edge, split it. Let
3227// R be the target of the dead out-coming edge.
3228// 1) Identify the set of dead blocks implied by the branch's dead outcoming
3229// edge. The result of this step will be {X| X is dominated by R}
3230// 2) Identify those blocks which haves at least one dead predecessor. The
3231// result of this step will be dominance-frontier(R).
3232// 3) Update the PHIs in DF(R) by replacing the operands corresponding to
3233// dead blocks with "UndefVal" in an hope these PHIs will optimized away.
3234//
3235// Return true iff *NEW* dead code are found.
3236bool GVNPass::processFoldableCondBr(BranchInst *BI) {
3237 if (!BI || BI->isUnconditional())
3238 return false;
3239
3240 // If a branch has two identical successors, we cannot declare either dead.
3241 if (BI->getSuccessor(0) == BI->getSuccessor(1))
3242 return false;
3243
3244 ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
3245 if (!Cond)
3246 return false;
3247
3248 BasicBlock *DeadRoot =
3249 Cond->getZExtValue() ? BI->getSuccessor(1) : BI->getSuccessor(0);
3250 if (DeadBlocks.count(DeadRoot))
3251 return false;
3252
3253 if (!DeadRoot->getSinglePredecessor())
3254 DeadRoot = splitCriticalEdges(BI->getParent(), DeadRoot);
3255
3256 addDeadBlock(DeadRoot);
3257 return true;
3258}
3259
3260// performPRE() will trigger assert if it comes across an instruction without
3261// associated val-num. As it normally has far more live instructions than dead
3262// instructions, it makes more sense just to "fabricate" a val-number for the
3263// dead code than checking if instruction involved is dead or not.
3264void GVNPass::assignValNumForDeadCode() {
3265 for (BasicBlock *BB : DeadBlocks) {
3266 for (Instruction &Inst : *BB) {
3267 unsigned ValNum = VN.lookupOrAdd(&Inst);
3268 addToLeaderTable(ValNum, &Inst, BB);
3269 }
3270 }
3271}
3272
3274public:
3275 static char ID; // Pass identification, replacement for typeid
3276
3277 explicit GVNLegacyPass(bool NoMemDepAnalysis = !GVNEnableMemDep)
3278 : FunctionPass(ID), Impl(GVNOptions().setMemDep(!NoMemDepAnalysis)) {
3280 }
3281
3282 bool runOnFunction(Function &F) override {
3283 if (skipFunction(F))
3284 return false;
3285
3286 auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
3287
3288 auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
3289 return Impl.runImpl(
3290 F, getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F),
3291 getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
3292 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F),
3293 getAnalysis<AAResultsWrapperPass>().getAAResults(),
3294 Impl.isMemDepEnabled()
3295 ? &getAnalysis<MemoryDependenceWrapperPass>().getMemDep()
3296 : nullptr,
3297 LIWP ? &LIWP->getLoopInfo() : nullptr,
3298 &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(),
3299 MSSAWP ? &MSSAWP->getMSSA() : nullptr);
3300 }
3301
3302 void getAnalysisUsage(AnalysisUsage &AU) const override {
3307 if (Impl.isMemDepEnabled())
3316 }
3317
3318private:
3319 GVNPass Impl;
3320};
3321
3322char GVNLegacyPass::ID = 0;
3323
3324INITIALIZE_PASS_BEGIN(GVNLegacyPass, "gvn", "Global Value Numbering", false, false)
3333
3334// The public interface to this file...
3335FunctionPass *llvm::createGVNPass(bool NoMemDepAnalysis) {
3336 return new GVNLegacyPass(NoMemDepAnalysis);
3337}
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")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:510
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:1978
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:1082
static void reportLoadElim(LoadInst *Load, Value *AvailableValue, OptimizationRemarkEmitter *ORE)
Definition: GVN.cpp:1822
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:959
static bool isOnlyReachableViaThisEdge(const BasicBlockEdge &E, DominatorTree *DT)
There is an edge from 'Src' to 'Dst'.
Definition: GVN.cpp:2349
static bool impliesEquivalanceIfFalse(CmpInst *Cmp)
Definition: GVN.cpp:1951
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:829
static Value * findDominatingValue(const MemoryLocation &Loc, Type *LoadTy, Instruction *From, AAResults *AA)
Definition: GVN.cpp:1144
static bool isLifetimeStart(const Instruction *Inst)
Definition: GVN.cpp:1063
static cl::opt< bool > GVNEnableSplitBackedgeInLoadPRE("enable-split-backedge-in-load-pre", cl::init(false))
static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl)
Definition: GVN.cpp:2124
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:945
static bool impliesEquivalanceIfTrue(CmpInst *Cmp)
Definition: GVN.cpp:1925
AvailabilityState
Definition: GVN.cpp:809
@ 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:1071
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:526
#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:620
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:793
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
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:116
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator end()
Definition: BasicBlock.h:337
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:335
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:216
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:296
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:112
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:35
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:533
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:127
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:1357
unsigned arg_size() const
Definition: InstrTypes.h:1355
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:701
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1058
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:711
@ FCMP_OEQ
0 0 0 1 True if ordered and equal
Definition: InstrTypes.h:714
@ FCMP_ONE
0 1 1 0 True if ordered and operands are unequal
Definition: InstrTypes.h:719
@ FCMP_UEQ
1 0 0 1 True if unordered or equal
Definition: InstrTypes.h:722
@ ICMP_EQ
equal
Definition: InstrTypes.h:732
@ ICMP_NE
not equal
Definition: InstrTypes.h:733
@ FCMP_UNE
1 1 1 0 True if unordered or not equal
Definition: InstrTypes.h:727
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:863
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
Definition: Constants.h:209
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:833
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:888
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:840
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:356
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:314
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
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:2208
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:2312
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:780
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:940
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:392
bool hasMetadata() const
Return true if this instruction has any metadata attached to it.
Definition: Instruction.h:284
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:734
const BasicBlock * getParent() const
Definition: Instruction.h:90
bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
Definition: Instruction.h:198
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:195
void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs)
Drop all unknown metadata except for debug locations.
Definition: Metadata.cpp:1467
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:177
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:569
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:594
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:47
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:146
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:975
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:1857
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="", Instruction *InsertBefore=nullptr)
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:1743
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
Helper class for SSA formation on a set of values defined in multiple blocks.
Definition: SSAUpdater.h:39
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="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
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:577
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:687
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
An instruction for storing to memory.
Definition: Instructions.h:301
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:1724
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:535
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:784
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:3302
GVNLegacyPass(bool NoMemDepAnalysis=!GVNEnableMemDep)
Definition: GVN.cpp:3277
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: GVN.cpp:3282
An opaque object representing a hash code.
Definition: Hashing.h:74
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.
std::unique_ptr< ValueIDNum[]> ValueTable
Type for a table of values in a block.
@ 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:76
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:445
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
@ Offset
Definition: DWP.cpp:440
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
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:1394
auto successors(const MachineBasicBlock *BB)
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2037
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:666
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 &)
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
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:1734
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:398
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
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:109
void patchReplacementInstruction(Instruction *I, Value *Repl)
Patch the replacement so that it is not more restrictive than the value being replaced.
Definition: Local.cpp:2873
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:2933
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
@ 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:2800
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:83
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:3335
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:184
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1884
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:1383
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:651
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:371
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:1002
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