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