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
17#include "llvm/Transforms/Scalar/GVN.h"
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/DepthFirstIterator.h"
20#include "llvm/ADT/Hashing.h"
21#include "llvm/ADT/MapVector.h"
22#include "llvm/ADT/PostOrderIterator.h"
23#include "llvm/ADT/STLExtras.h"
24#include "llvm/ADT/SetVector.h"
25#include "llvm/ADT/SmallPtrSet.h"
26#include "llvm/ADT/SmallVector.h"
27#include "llvm/ADT/Statistic.h"
28#include "llvm/Analysis/AliasAnalysis.h"
29#include "llvm/Analysis/AssumeBundleQueries.h"
30#include "llvm/Analysis/AssumptionCache.h"
31#include "llvm/Analysis/CFG.h"
32#include "llvm/Analysis/DomTreeUpdater.h"
33#include "llvm/Analysis/GlobalsModRef.h"
34#include "llvm/Analysis/InstructionPrecedenceTracking.h"
35#include "llvm/Analysis/InstructionSimplify.h"
36#include "llvm/Analysis/Loads.h"
37#include "llvm/Analysis/LoopInfo.h"
38#include "llvm/Analysis/MemoryBuiltins.h"
39#include "llvm/Analysis/MemoryDependenceAnalysis.h"
40#include "llvm/Analysis/MemorySSA.h"
41#include "llvm/Analysis/MemorySSAUpdater.h"
42#include "llvm/Analysis/OptimizationRemarkEmitter.h"
43#include "llvm/Analysis/PHITransAddr.h"
44#include "llvm/Analysis/TargetLibraryInfo.h"
45#include "llvm/Analysis/ValueTracking.h"
46#include "llvm/IR/Attributes.h"
47#include "llvm/IR/BasicBlock.h"
48#include "llvm/IR/Constant.h"
49#include "llvm/IR/Constants.h"
50#include "llvm/IR/DebugLoc.h"
51#include "llvm/IR/Dominators.h"
52#include "llvm/IR/Function.h"
53#include "llvm/IR/InstrTypes.h"
54#include "llvm/IR/Instruction.h"
55#include "llvm/IR/Instructions.h"
56#include "llvm/IR/IntrinsicInst.h"
57#include "llvm/IR/LLVMContext.h"
58#include "llvm/IR/Metadata.h"
59#include "llvm/IR/Module.h"
60#include "llvm/IR/PassManager.h"
61#include "llvm/IR/PatternMatch.h"
62#include "llvm/IR/Type.h"
63#include "llvm/IR/Use.h"
64#include "llvm/IR/Value.h"
65#include "llvm/InitializePasses.h"
66#include "llvm/Pass.h"
67#include "llvm/Support/Casting.h"
68#include "llvm/Support/CommandLine.h"
69#include "llvm/Support/Compiler.h"
70#include "llvm/Support/Debug.h"
71#include "llvm/Support/raw_ostream.h"
72#include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
73#include "llvm/Transforms/Utils/BasicBlockUtils.h"
74#include "llvm/Transforms/Utils/Local.h"
75#include "llvm/Transforms/Utils/SSAUpdater.h"
76#include "llvm/Transforms/Utils/VNCoercion.h"
77#include <algorithm>
78#include <cassert>
79#include <cstdint>
80#include <optional>
81#include <utility>
82
83using namespace llvm;
84using namespace llvm::VNCoercion;
85using namespace PatternMatch;
86
87using AvailableValue = GVNPass::AvailableValue;
88using AvailableValueInBlock = GVNPass::AvailableValueInBlock;
89
90#define DEBUG_TYPE "gvn"
91
92STATISTIC(NumGVNInstr, "Number of instructions deleted");
93STATISTIC(NumGVNLoad, "Number of loads deleted");
94STATISTIC(NumGVNPRE, "Number of instructions PRE'd");
95STATISTIC(NumGVNBlocks, "Number of blocks merged");
96STATISTIC(NumGVNSimpl, "Number of instructions simplified");
97STATISTIC(NumGVNEqProp, "Number of equalities propagated");
98STATISTIC(NumPRELoad, "Number of loads PRE'd");
99STATISTIC(NumPRELoopLoad, "Number of loop loads PRE'd");
100STATISTIC(NumPRELoadMoved2CEPred,
101 "Number of loads moved to predecessor of a critical edge in PRE");
102
103STATISTIC(IsValueFullyAvailableInBlockNumSpeculationsMax,
104 "Number of blocks speculated as available in "
105 "IsValueFullyAvailableInBlock(), max");
106STATISTIC(MaxBBSpeculationCutoffReachedTimes,
107 "Number of times we we reached gvn-max-block-speculations cut-off "
108 "preventing further exploration");
109
110static cl::opt<bool> GVNEnableScalarPRE("enable-scalar-pre", cl::init(Val: true),
111 cl::Hidden);
112static cl::opt<bool> GVNEnableLoadPRE("enable-load-pre", cl::init(Val: true));
113static cl::opt<bool> GVNEnableLoadInLoopPRE("enable-load-in-loop-pre",
114 cl::init(Val: true));
115static cl::opt<bool>
116GVNEnableSplitBackedgeInLoadPRE("enable-split-backedge-in-load-pre",
117 cl::init(Val: false));
118static cl::opt<bool> GVNEnableMemDep("enable-gvn-memdep", cl::init(Val: true));
119static cl::opt<bool> GVNEnableMemorySSA("enable-gvn-memoryssa",
120 cl::init(Val: false));
121
122static cl::opt<unsigned> ScanUsersLimit(
123 "gvn-scan-users-limit", cl::Hidden, cl::init(Val: 100),
124 cl::desc("The number of memory accesses to scan in a block in reaching "
125 "memory values analysis (default = 100)"));
126
127static cl::opt<uint32_t> MaxNumDeps(
128 "gvn-max-num-deps", cl::Hidden, cl::init(Val: 100),
129 cl::desc("Max number of dependences to attempt Load PRE (default = 100)"));
130
131// This is based on IsValueFullyAvailableInBlockNumSpeculationsMax stat.
132static cl::opt<uint32_t> MaxBBSpeculations(
133 "gvn-max-block-speculations", cl::Hidden, cl::init(Val: 600),
134 cl::desc("Max number of blocks we're willing to speculate on (and recurse "
135 "into) when deducing if a value is fully available or not in GVN "
136 "(default = 600)"));
137
138static cl::opt<uint32_t> MaxNumVisitedInsts(
139 "gvn-max-num-visited-insts", cl::Hidden, cl::init(Val: 100),
140 cl::desc("Max number of visited instructions when trying to find "
141 "dominating value of select dependency (default = 100)"));
142
143static cl::opt<uint32_t> MaxNumInsnsPerBlock(
144 "gvn-max-num-insns", cl::Hidden, cl::init(Val: 100),
145 cl::desc("Max number of instructions to scan in each basic block in GVN "
146 "(default = 100)"));
147
148struct llvm::GVNPass::Expression {
149 uint32_t Opcode;
150 bool Commutative = false;
151 // The type is not necessarily the result type of the expression, it may be
152 // any additional type needed to disambiguate the expression.
153 Type *Ty = nullptr;
154 SmallVector<uint32_t, 4> VarArgs;
155
156 AttributeList Attrs;
157
158 Expression(uint32_t Op = ~2U) : Opcode(Op) {}
159
160 bool operator==(const Expression &Other) const {
161 if (Opcode != Other.Opcode)
162 return false;
163 if (Opcode == ~0U || Opcode == ~1U)
164 return true;
165 if (Ty != Other.Ty)
166 return false;
167 if (VarArgs != Other.VarArgs)
168 return false;
169 if ((!Attrs.isEmpty() || !Other.Attrs.isEmpty()) &&
170 !Attrs.intersectWith(C&: Ty->getContext(), Other: Other.Attrs).has_value())
171 return false;
172 return true;
173 }
174
175 friend hash_code hash_value(const Expression &Value) {
176 return hash_combine(args: Value.Opcode, args: Value.Ty,
177 args: hash_combine_range(R: Value.VarArgs));
178 }
179};
180
181template <> struct llvm::DenseMapInfo<GVNPass::Expression> {
182 static unsigned getHashValue(const GVNPass::Expression &E) {
183 using llvm::hash_value;
184
185 return static_cast<unsigned>(hash_value(Value: E));
186 }
187
188 static bool isEqual(const GVNPass::Expression &LHS,
189 const GVNPass::Expression &RHS) {
190 return LHS == RHS;
191 }
192};
193
194/// Represents a particular available value that we know how to materialize.
195/// Materialization of an AvailableValue never fails. An AvailableValue is
196/// implicitly associated with a rematerialization point which is the
197/// location of the instruction from which it was formed.
198struct llvm::GVNPass::AvailableValue {
199 enum class ValType {
200 SimpleVal, // A simple offsetted value that is accessed.
201 LoadVal, // A value produced by a load.
202 MemIntrin, // A memory intrinsic which is loaded from.
203 UndefVal, // A UndefValue representing a value from dead block (which
204 // is not yet physically removed from the CFG).
205 SelectVal, // A pointer select which is loaded from and for which the load
206 // can be replace by a value select.
207 };
208
209 /// Val - The value that is live out of the block.
210 Value *Val;
211 /// Kind of the live-out value.
212 ValType Kind;
213
214 /// Offset - The byte offset in Val that is interesting for the load query.
215 unsigned Offset = 0;
216 /// V1, V2 - The dominating non-clobbered values of SelectVal.
217 Value *V1 = nullptr, *V2 = nullptr;
218
219 static AvailableValue get(Value *V, unsigned Offset = 0) {
220 AvailableValue Res;
221 Res.Val = V;
222 Res.Kind = ValType::SimpleVal;
223 Res.Offset = Offset;
224 return Res;
225 }
226
227 static AvailableValue getMI(MemIntrinsic *MI, unsigned Offset = 0) {
228 AvailableValue Res;
229 Res.Val = MI;
230 Res.Kind = ValType::MemIntrin;
231 Res.Offset = Offset;
232 return Res;
233 }
234
235 static AvailableValue getLoad(LoadInst *Load, unsigned Offset = 0) {
236 AvailableValue Res;
237 Res.Val = Load;
238 Res.Kind = ValType::LoadVal;
239 Res.Offset = Offset;
240 return Res;
241 }
242
243 static AvailableValue getUndef() {
244 AvailableValue Res;
245 Res.Val = nullptr;
246 Res.Kind = ValType::UndefVal;
247 Res.Offset = 0;
248 return Res;
249 }
250
251 static AvailableValue getSelect(Value *Cond, Value *V1, Value *V2) {
252 AvailableValue Res;
253 Res.Val = Cond;
254 Res.Kind = ValType::SelectVal;
255 Res.Offset = 0;
256 Res.V1 = V1;
257 Res.V2 = V2;
258 return Res;
259 }
260
261 bool isSimpleValue() const { return Kind == ValType::SimpleVal; }
262 bool isCoercedLoadValue() const { return Kind == ValType::LoadVal; }
263 bool isMemIntrinValue() const { return Kind == ValType::MemIntrin; }
264 bool isUndefValue() const { return Kind == ValType::UndefVal; }
265 bool isSelectValue() const { return Kind == ValType::SelectVal; }
266
267 Value *getSimpleValue() const {
268 assert(isSimpleValue() && "Wrong accessor");
269 return Val;
270 }
271
272 LoadInst *getCoercedLoadValue() const {
273 assert(isCoercedLoadValue() && "Wrong accessor");
274 return cast<LoadInst>(Val);
275 }
276
277 MemIntrinsic *getMemIntrinValue() const {
278 assert(isMemIntrinValue() && "Wrong accessor");
279 return cast<MemIntrinsic>(Val);
280 }
281
282 Value *getSelectCondition() const {
283 assert(isSelectValue() && "Wrong accessor");
284 return Val;
285 }
286
287 /// Emit code at the specified insertion point to adjust the value defined
288 /// here to the specified type. This handles various coercion cases.
289 Value *MaterializeAdjustedValue(LoadInst *Load, Instruction *InsertPt) const;
290};
291
292/// Represents an AvailableValue which can be rematerialized at the end of
293/// the associated BasicBlock.
294struct llvm::GVNPass::AvailableValueInBlock {
295 /// BB - The basic block in question.
296 BasicBlock *BB = nullptr;
297
298 /// AV - The actual available value.
299 AvailableValue AV;
300
301 static AvailableValueInBlock get(BasicBlock *BB, AvailableValue &&AV) {
302 AvailableValueInBlock Res;
303 Res.BB = BB;
304 Res.AV = std::move(AV);
305 return Res;
306 }
307
308 static AvailableValueInBlock get(BasicBlock *BB, Value *V,
309 unsigned Offset = 0) {
310 return get(BB, AV: AvailableValue::get(V, Offset));
311 }
312
313 static AvailableValueInBlock getUndef(BasicBlock *BB) {
314 return get(BB, AV: AvailableValue::getUndef());
315 }
316
317 /// Emit code at the end of this block to adjust the value defined here to
318 /// the specified type. This handles various coercion cases.
319 Value *MaterializeAdjustedValue(LoadInst *Load) const {
320 return AV.MaterializeAdjustedValue(Load, InsertPt: BB->getTerminator());
321 }
322};
323
324//===----------------------------------------------------------------------===//
325// ValueTable Internal Functions
326//===----------------------------------------------------------------------===//
327
328GVNPass::Expression GVNPass::ValueTable::createExpr(Instruction *I) {
329 Expression E;
330 E.Ty = I->getType();
331 E.Opcode = I->getOpcode();
332 if (const GCRelocateInst *GCR = dyn_cast<GCRelocateInst>(Val: I)) {
333 // gc.relocate is 'special' call: its second and third operands are
334 // not real values, but indices into statepoint's argument list.
335 // Use the refered to values for purposes of identity.
336 E.VarArgs.push_back(Elt: lookupOrAdd(V: GCR->getOperand(i_nocapture: 0)));
337 E.VarArgs.push_back(Elt: lookupOrAdd(V: GCR->getBasePtr()));
338 E.VarArgs.push_back(Elt: lookupOrAdd(V: GCR->getDerivedPtr()));
339 } else {
340 for (Use &Op : I->operands())
341 E.VarArgs.push_back(Elt: lookupOrAdd(V: Op));
342 }
343 if (I->isCommutative()) {
344 // Ensure that commutative instructions that only differ by a permutation
345 // of their operands get the same value number by sorting the operand value
346 // numbers. Since commutative operands are the 1st two operands it is more
347 // efficient to sort by hand rather than using, say, std::sort.
348 assert(I->getNumOperands() >= 2 && "Unsupported commutative instruction!");
349 if (E.VarArgs[0] > E.VarArgs[1])
350 std::swap(a&: E.VarArgs[0], b&: E.VarArgs[1]);
351 E.Commutative = true;
352 }
353
354 if (auto *C = dyn_cast<CmpInst>(Val: I)) {
355 // Sort the operand value numbers so x<y and y>x get the same value number.
356 CmpInst::Predicate Predicate = C->getPredicate();
357 if (E.VarArgs[0] > E.VarArgs[1]) {
358 std::swap(a&: E.VarArgs[0], b&: E.VarArgs[1]);
359 Predicate = CmpInst::getSwappedPredicate(pred: Predicate);
360 }
361 E.Opcode = (C->getOpcode() << 8) | Predicate;
362 E.Commutative = true;
363 } else if (auto *IVI = dyn_cast<InsertValueInst>(Val: I)) {
364 E.VarArgs.append(in_start: IVI->idx_begin(), in_end: IVI->idx_end());
365 } else if (auto *SVI = dyn_cast<ShuffleVectorInst>(Val: I)) {
366 ArrayRef<int> ShuffleMask = SVI->getShuffleMask();
367 E.VarArgs.append(in_start: ShuffleMask.begin(), in_end: ShuffleMask.end());
368 } else if (auto *CB = dyn_cast<CallBase>(Val: I)) {
369 E.Attrs = CB->getAttributes();
370 }
371
372 return E;
373}
374
375GVNPass::Expression GVNPass::ValueTable::createCmpExpr(
376 unsigned Opcode, CmpInst::Predicate Predicate, Value *LHS, Value *RHS) {
377 assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) &&
378 "Not a comparison!");
379 Expression E;
380 E.Ty = CmpInst::makeCmpResultType(opnd_type: LHS->getType());
381 E.VarArgs.push_back(Elt: lookupOrAdd(V: LHS));
382 E.VarArgs.push_back(Elt: lookupOrAdd(V: RHS));
383
384 // Sort the operand value numbers so x<y and y>x get the same value number.
385 if (E.VarArgs[0] > E.VarArgs[1]) {
386 std::swap(a&: E.VarArgs[0], b&: E.VarArgs[1]);
387 Predicate = CmpInst::getSwappedPredicate(pred: Predicate);
388 }
389 E.Opcode = (Opcode << 8) | Predicate;
390 E.Commutative = true;
391 return E;
392}
393
394GVNPass::Expression
395GVNPass::ValueTable::createExtractvalueExpr(ExtractValueInst *EI) {
396 assert(EI && "Not an ExtractValueInst?");
397 Expression E;
398 E.Ty = EI->getType();
399 E.Opcode = 0;
400
401 WithOverflowInst *WO = dyn_cast<WithOverflowInst>(Val: EI->getAggregateOperand());
402 if (WO != nullptr && EI->getNumIndices() == 1 && *EI->idx_begin() == 0) {
403 // EI is an extract from one of our with.overflow intrinsics. Synthesize
404 // a semantically equivalent expression instead of an extract value
405 // expression.
406 E.Opcode = WO->getBinaryOp();
407 E.VarArgs.push_back(Elt: lookupOrAdd(V: WO->getLHS()));
408 E.VarArgs.push_back(Elt: lookupOrAdd(V: WO->getRHS()));
409 return E;
410 }
411
412 // Not a recognised intrinsic. Fall back to producing an extract value
413 // expression.
414 E.Opcode = EI->getOpcode();
415 for (Use &Op : EI->operands())
416 E.VarArgs.push_back(Elt: lookupOrAdd(V: Op));
417
418 append_range(C&: E.VarArgs, R: EI->indices());
419
420 return E;
421}
422
423GVNPass::Expression GVNPass::ValueTable::createGEPExpr(GetElementPtrInst *GEP) {
424 Expression E;
425 Type *PtrTy = GEP->getType()->getScalarType();
426 const DataLayout &DL = GEP->getDataLayout();
427 unsigned BitWidth = DL.getIndexTypeSizeInBits(Ty: PtrTy);
428 SmallMapVector<Value *, APInt, 4> VariableOffsets;
429 APInt ConstantOffset(BitWidth, 0);
430 if (GEP->collectOffset(DL, BitWidth, VariableOffsets, ConstantOffset)) {
431 // Convert into offset representation, to recognize equivalent address
432 // calculations that use different type encoding.
433 LLVMContext &Context = GEP->getContext();
434 E.Opcode = GEP->getOpcode();
435 E.Ty = nullptr;
436 E.VarArgs.push_back(Elt: lookupOrAdd(V: GEP->getPointerOperand()));
437 for (const auto &[V, Scale] : VariableOffsets) {
438 E.VarArgs.push_back(Elt: lookupOrAdd(V));
439 E.VarArgs.push_back(Elt: lookupOrAdd(V: ConstantInt::get(Context, V: Scale)));
440 }
441 if (!ConstantOffset.isZero())
442 E.VarArgs.push_back(
443 Elt: lookupOrAdd(V: ConstantInt::get(Context, V: ConstantOffset)));
444 } else {
445 // If converting to offset representation fails (for scalable vectors),
446 // fall back to type-based implementation.
447 E.Opcode = GEP->getOpcode();
448 E.Ty = GEP->getSourceElementType();
449 for (Use &Op : GEP->operands())
450 E.VarArgs.push_back(Elt: lookupOrAdd(V: Op));
451 }
452 return E;
453}
454
455//===----------------------------------------------------------------------===//
456// ValueTable External Functions
457//===----------------------------------------------------------------------===//
458
459GVNPass::ValueTable::ValueTable() = default;
460GVNPass::ValueTable::ValueTable(const ValueTable &) = default;
461GVNPass::ValueTable::ValueTable(ValueTable &&) = default;
462GVNPass::ValueTable::~ValueTable() = default;
463GVNPass::ValueTable &
464GVNPass::ValueTable::operator=(const GVNPass::ValueTable &Arg) = default;
465
466/// add - Insert a value into the table with a specified value number.
467void GVNPass::ValueTable::add(Value *V, uint32_t Num) {
468 ValueNumbering.insert(KV: std::make_pair(x&: V, y&: Num));
469 if (PHINode *PN = dyn_cast<PHINode>(Val: V))
470 NumberingPhi[Num] = PN;
471}
472
473/// Include the incoming memory state into the hash of the expression for the
474/// given instruction. If the incoming memory state is:
475/// * LiveOnEntry, add the value number of the entry block,
476/// * a MemoryPhi, add the value number of the basic block corresponding to that
477/// MemoryPhi,
478/// * a MemoryDef, add the value number of the memory setting instruction.
479void GVNPass::ValueTable::addMemoryStateToExp(Instruction *I, Expression &Exp) {
480 assert(MSSA && "addMemoryStateToExp should not be called without MemorySSA");
481 assert(MSSA->getMemoryAccess(I) && "Instruction does not access memory");
482 MemoryAccess *MA = MSSA->getSkipSelfWalker()->getClobberingMemoryAccess(I);
483 Exp.VarArgs.push_back(Elt: lookupOrAdd(MA));
484}
485
486uint32_t GVNPass::ValueTable::lookupOrAddCall(CallInst *C) {
487 // FIXME: Currently the calls which may access the thread id may
488 // be considered as not accessing the memory. But this is
489 // problematic for coroutines, since coroutines may resume in a
490 // different thread. So we disable the optimization here for the
491 // correctness. However, it may block many other correct
492 // optimizations. Revert this one when we detect the memory
493 // accessing kind more precisely.
494 if (C->getFunction()->isPresplitCoroutine()) {
495 ValueNumbering[C] = NextValueNumber;
496 return NextValueNumber++;
497 }
498
499 // Do not combine convergent calls since they implicitly depend on the set of
500 // threads that is currently executing, and they might be in different basic
501 // blocks.
502 if (C->isConvergent()) {
503 ValueNumbering[C] = NextValueNumber;
504 return NextValueNumber++;
505 }
506
507 if (AA->doesNotAccessMemory(Call: C)) {
508 Expression Exp = createExpr(I: C);
509 uint32_t E = assignExpNewValueNum(Exp).first;
510 ValueNumbering[C] = E;
511 return E;
512 }
513
514 if (MD && AA->onlyReadsMemory(Call: C)) {
515 Expression Exp = createExpr(I: C);
516 auto [E, IsValNumNew] = assignExpNewValueNum(Exp);
517 if (IsValNumNew) {
518 ValueNumbering[C] = E;
519 return E;
520 }
521
522 MemDepResult LocalDep = MD->getDependency(QueryInst: C);
523
524 if (!LocalDep.isDef() && !LocalDep.isNonLocal()) {
525 ValueNumbering[C] = NextValueNumber;
526 return NextValueNumber++;
527 }
528
529 if (LocalDep.isDef()) {
530 // For masked load/store intrinsics, the local_dep may actually be
531 // a normal load or store instruction.
532 CallInst *LocalDepCall = dyn_cast<CallInst>(Val: LocalDep.getInst());
533
534 if (!LocalDepCall || LocalDepCall->arg_size() != C->arg_size()) {
535 ValueNumbering[C] = NextValueNumber;
536 return NextValueNumber++;
537 }
538
539 for (unsigned I = 0, E = C->arg_size(); I < E; ++I) {
540 uint32_t CVN = lookupOrAdd(V: C->getArgOperand(i: I));
541 uint32_t LocalDepCallVN = lookupOrAdd(V: LocalDepCall->getArgOperand(i: I));
542 if (CVN != LocalDepCallVN) {
543 ValueNumbering[C] = NextValueNumber;
544 return NextValueNumber++;
545 }
546 }
547
548 uint32_t V = lookupOrAdd(V: LocalDepCall);
549 ValueNumbering[C] = V;
550 return V;
551 }
552
553 // Non-local case.
554 const MemoryDependenceResults::NonLocalDepInfo &Deps =
555 MD->getNonLocalCallDependency(QueryCall: C);
556 // FIXME: Move the checking logic to MemDep!
557 CallInst *CDep = nullptr;
558
559 // Check to see if we have a single dominating call instruction that is
560 // identical to C.
561 for (const NonLocalDepEntry &I : Deps) {
562 if (I.getResult().isNonLocal())
563 continue;
564
565 // We don't handle non-definitions. If we already have a call, reject
566 // instruction dependencies.
567 if (!I.getResult().isDef() || CDep != nullptr) {
568 CDep = nullptr;
569 break;
570 }
571
572 CallInst *NonLocalDepCall = dyn_cast<CallInst>(Val: I.getResult().getInst());
573 // FIXME: All duplicated with non-local case.
574 if (NonLocalDepCall && DT->properlyDominates(A: I.getBB(), B: C->getParent())) {
575 CDep = NonLocalDepCall;
576 continue;
577 }
578
579 CDep = nullptr;
580 break;
581 }
582
583 if (!CDep) {
584 ValueNumbering[C] = NextValueNumber;
585 return NextValueNumber++;
586 }
587
588 if (CDep->arg_size() != C->arg_size()) {
589 ValueNumbering[C] = NextValueNumber;
590 return NextValueNumber++;
591 }
592 for (unsigned I = 0, E = C->arg_size(); I < E; ++I) {
593 uint32_t CVN = lookupOrAdd(V: C->getArgOperand(i: I));
594 uint32_t CDepVN = lookupOrAdd(V: CDep->getArgOperand(i: I));
595 if (CVN != CDepVN) {
596 ValueNumbering[C] = NextValueNumber;
597 return NextValueNumber++;
598 }
599 }
600
601 uint32_t V = lookupOrAdd(V: CDep);
602 ValueNumbering[C] = V;
603 return V;
604 }
605
606 if (MSSA && IsMSSAEnabled && AA->onlyReadsMemory(Call: C)) {
607 Expression Exp = createExpr(I: C);
608 addMemoryStateToExp(I: C, Exp);
609 auto [V, _] = assignExpNewValueNum(Exp);
610 ValueNumbering[C] = V;
611 return V;
612 }
613
614 ValueNumbering[C] = NextValueNumber;
615 return NextValueNumber++;
616}
617
618/// Returns the value number for the specified load or store instruction.
619uint32_t GVNPass::ValueTable::computeLoadStoreVN(Instruction *I) {
620 if (!MSSA || !IsMSSAEnabled) {
621 ValueNumbering[I] = NextValueNumber;
622 return NextValueNumber++;
623 }
624
625 Expression Exp;
626 Exp.Ty = I->getType();
627 Exp.Opcode = I->getOpcode();
628 for (Use &Op : I->operands())
629 Exp.VarArgs.push_back(Elt: lookupOrAdd(V: Op));
630 addMemoryStateToExp(I, Exp);
631
632 auto [V, _] = assignExpNewValueNum(Exp);
633 ValueNumbering[I] = V;
634 return V;
635}
636
637/// Returns true if a value number exists for the specified value.
638bool GVNPass::ValueTable::exists(Value *V) const {
639 return ValueNumbering.contains(Val: V);
640}
641
642uint32_t GVNPass::ValueTable::lookupOrAdd(MemoryAccess *MA) {
643 return MSSA->isLiveOnEntryDef(MA) || isa<MemoryPhi>(Val: MA)
644 ? lookupOrAdd(V: MA->getBlock())
645 : lookupOrAdd(V: cast<MemoryUseOrDef>(Val: MA)->getMemoryInst());
646}
647
648/// lookupOrAdd - Returns the value number for the specified value, assigning
649/// it a new number if it did not have one before.
650uint32_t GVNPass::ValueTable::lookupOrAdd(Value *V) {
651 auto VI = ValueNumbering.find(Val: V);
652 if (VI != ValueNumbering.end())
653 return VI->second;
654
655 auto *I = dyn_cast<Instruction>(Val: V);
656 if (!I) {
657 ValueNumbering[V] = NextValueNumber;
658 if (isa<BasicBlock>(Val: V))
659 NumberingBB[NextValueNumber] = cast<BasicBlock>(Val: V);
660 return NextValueNumber++;
661 }
662
663 Expression Exp;
664 switch (I->getOpcode()) {
665 case Instruction::Call:
666 return lookupOrAddCall(C: cast<CallInst>(Val: I));
667 case Instruction::FNeg:
668 case Instruction::Add:
669 case Instruction::FAdd:
670 case Instruction::Sub:
671 case Instruction::FSub:
672 case Instruction::Mul:
673 case Instruction::FMul:
674 case Instruction::UDiv:
675 case Instruction::SDiv:
676 case Instruction::FDiv:
677 case Instruction::URem:
678 case Instruction::SRem:
679 case Instruction::FRem:
680 case Instruction::Shl:
681 case Instruction::LShr:
682 case Instruction::AShr:
683 case Instruction::And:
684 case Instruction::Or:
685 case Instruction::Xor:
686 case Instruction::ICmp:
687 case Instruction::FCmp:
688 case Instruction::Trunc:
689 case Instruction::ZExt:
690 case Instruction::SExt:
691 case Instruction::FPToUI:
692 case Instruction::FPToSI:
693 case Instruction::UIToFP:
694 case Instruction::SIToFP:
695 case Instruction::FPTrunc:
696 case Instruction::FPExt:
697 case Instruction::PtrToInt:
698 case Instruction::PtrToAddr:
699 case Instruction::IntToPtr:
700 case Instruction::AddrSpaceCast:
701 case Instruction::BitCast:
702 case Instruction::Select:
703 case Instruction::Freeze:
704 case Instruction::ExtractElement:
705 case Instruction::InsertElement:
706 case Instruction::ShuffleVector:
707 case Instruction::InsertValue:
708 Exp = createExpr(I);
709 break;
710 case Instruction::GetElementPtr:
711 Exp = createGEPExpr(GEP: cast<GetElementPtrInst>(Val: I));
712 break;
713 case Instruction::ExtractValue:
714 Exp = createExtractvalueExpr(EI: cast<ExtractValueInst>(Val: I));
715 break;
716 case Instruction::PHI:
717 ValueNumbering[V] = NextValueNumber;
718 NumberingPhi[NextValueNumber] = cast<PHINode>(Val: V);
719 return NextValueNumber++;
720 case Instruction::Load:
721 case Instruction::Store:
722 return computeLoadStoreVN(I);
723 default:
724 ValueNumbering[V] = NextValueNumber;
725 return NextValueNumber++;
726 }
727
728 uint32_t E = assignExpNewValueNum(Exp).first;
729 ValueNumbering[V] = E;
730 return E;
731}
732
733/// Returns the value number of the specified value. Fails if
734/// the value has not yet been numbered.
735uint32_t GVNPass::ValueTable::lookup(Value *V, bool Verify) const {
736 auto VI = ValueNumbering.find(Val: V);
737 if (Verify) {
738 assert(VI != ValueNumbering.end() && "Value not numbered?");
739 return VI->second;
740 }
741 return (VI != ValueNumbering.end()) ? VI->second : 0;
742}
743
744/// Returns the value number of the given comparison,
745/// assigning it a new number if it did not have one before. Useful when
746/// we deduced the result of a comparison, but don't immediately have an
747/// instruction realizing that comparison to hand.
748uint32_t GVNPass::ValueTable::lookupOrAddCmp(unsigned Opcode,
749 CmpInst::Predicate Predicate,
750 Value *LHS, Value *RHS) {
751 Expression Exp = createCmpExpr(Opcode, Predicate, LHS, RHS);
752 return assignExpNewValueNum(Exp).first;
753}
754
755/// Returns the value number of ptrtoint \p Ptr to \Ty.
756uint32_t GVNPass::ValueTable::lookupPtrToInt(Value *Ptr, Type *Ty) {
757 Expression Exp(Instruction::PtrToInt);
758 Exp.Ty = Ty;
759 Exp.VarArgs.push_back(Elt: lookupOrAdd(V: Ptr));
760 return ExpressionNumbering.lookup(Val: Exp);
761}
762
763/// Remove all entries from the ValueTable.
764void GVNPass::ValueTable::clear() {
765 ValueNumbering.clear();
766 ExpressionNumbering.clear();
767 NumberingPhi.clear();
768 NumberingBB.clear();
769 PhiTranslateTable.clear();
770 NextValueNumber = 1;
771 Expressions.clear();
772 ExprIdx.clear();
773 NextExprNumber = 0;
774}
775
776/// Remove a value from the value numbering.
777void GVNPass::ValueTable::erase(Value *V) {
778 uint32_t Num = ValueNumbering.lookup(Val: V);
779 ValueNumbering.erase(Val: V);
780 // If V is PHINode, V <--> value number is an one-to-one mapping.
781 if (isa<PHINode>(Val: V))
782 NumberingPhi.erase(Val: Num);
783 else if (isa<BasicBlock>(Val: V))
784 NumberingBB.erase(Val: Num);
785}
786
787/// verifyRemoved - Verify that the value is removed from all internal data
788/// structures.
789void GVNPass::ValueTable::verifyRemoved(const Value *V) const {
790 assert(!ValueNumbering.contains(V) &&
791 "Inst still occurs in value numbering map!");
792}
793
794//===----------------------------------------------------------------------===//
795// LeaderMap External Functions
796//===----------------------------------------------------------------------===//
797
798/// Push a new Value to the LeaderTable onto the list for its value number.
799void GVNPass::LeaderMap::insert(uint32_t N, Value *V, const BasicBlock *BB) {
800 const auto &[It, Inserted] = NumToLeaders.try_emplace(Key: N, Args&: V, Args&: BB, Args: nullptr);
801 if (!Inserted) {
802 // Key already exists: insert new node after the head.
803 auto *NewSlot = TableAllocator.Allocate<LeaderListNode>();
804 new (NewSlot) LeaderListNode(V, BB, It->second.Next);
805 It->second.Next = NewSlot;
806 }
807}
808
809/// Scan the list of values corresponding to a given
810/// value number, and remove the given instruction if encountered.
811void GVNPass::LeaderMap::erase(uint32_t N, Instruction *I,
812 const BasicBlock *BB) {
813 auto It = NumToLeaders.find(Val: N);
814 if (It == NumToLeaders.end())
815 return;
816
817 LeaderListNode *Prev = nullptr;
818 LeaderListNode *Curr = &It->second;
819
820 while (Curr && (Curr->Entry.Val != I || Curr->Entry.BB != BB)) {
821 Prev = Curr;
822 Curr = Curr->Next;
823 }
824
825 if (!Curr)
826 return;
827
828 if (Prev) {
829 // Non-head node: unlink and destroy.
830 Prev->Next = Curr->Next;
831 Curr->~LeaderListNode();
832 TableAllocator.Deallocate<LeaderListNode>(Ptr: Curr);
833 } else {
834 // Head node (stored by value in DenseMap).
835 if (!Curr->Next) {
836 // Only node; erase from map (DenseMap calls the destructor).
837 NumToLeaders.erase(I: It);
838 } else {
839 // Move second node's data into head, then destroy second node.
840 LeaderListNode *Next = Curr->Next;
841 Curr->Entry.Val = std::move(Next->Entry.Val);
842 Curr->Entry.BB = Next->Entry.BB;
843 Curr->Next = Next->Next;
844 Next->~LeaderListNode();
845 TableAllocator.Deallocate<LeaderListNode>(Ptr: Next);
846 }
847 }
848}
849
850//===----------------------------------------------------------------------===//
851// GVN Pass
852//===----------------------------------------------------------------------===//
853
854bool GVNPass::isScalarPREEnabled() const {
855 return Options.AllowScalarPRE.value_or(u&: GVNEnableScalarPRE);
856}
857
858bool GVNPass::isLoadPREEnabled() const {
859 return Options.AllowLoadPRE.value_or(u&: GVNEnableLoadPRE);
860}
861
862bool GVNPass::isLoadInLoopPREEnabled() const {
863 return Options.AllowLoadInLoopPRE.value_or(u&: GVNEnableLoadInLoopPRE);
864}
865
866bool GVNPass::isLoadPRESplitBackedgeEnabled() const {
867 return Options.AllowLoadPRESplitBackedge.value_or(
868 u&: GVNEnableSplitBackedgeInLoadPRE);
869}
870
871bool GVNPass::isMemDepEnabled() const {
872 return Options.AllowMemDep.value_or(u&: GVNEnableMemDep);
873}
874
875bool GVNPass::isMemorySSAEnabled() const {
876 return Options.AllowMemorySSA.value_or(u&: GVNEnableMemorySSA);
877}
878
879PreservedAnalyses GVNPass::run(Function &F, FunctionAnalysisManager &AM) {
880 // FIXME: The order of evaluation of these 'getResult' calls is very
881 // significant! Re-ordering these variables will cause GVN when run alone to
882 // be less effective! We should fix memdep and basic-aa to not exhibit this
883 // behavior, but until then don't change the order here.
884 auto &AC = AM.getResult<AssumptionAnalysis>(IR&: F);
885 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
886 auto &TLI = AM.getResult<TargetLibraryAnalysis>(IR&: F);
887 auto &AA = AM.getResult<AAManager>(IR&: F);
888 auto *MemDep =
889 isMemDepEnabled() ? &AM.getResult<MemoryDependenceAnalysis>(IR&: F) : nullptr;
890 auto &LI = AM.getResult<LoopAnalysis>(IR&: F);
891 auto *MSSA = AM.getCachedResult<MemorySSAAnalysis>(IR&: F);
892 if (isMemorySSAEnabled() && !MSSA) {
893 assert(!MemDep &&
894 "On-demand computation of MemSSA implies that MemDep is disabled!");
895 MSSA = &AM.getResult<MemorySSAAnalysis>(IR&: F);
896 }
897 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F);
898 bool Changed = runImpl(F, RunAC&: AC, RunDT&: DT, RunTLI: TLI, RunAA&: AA, RunMD: MemDep, LI, ORE: &ORE,
899 MSSA: MSSA ? &MSSA->getMSSA() : nullptr);
900 if (!Changed)
901 return PreservedAnalyses::all();
902 PreservedAnalyses PA;
903 PA.preserve<DominatorTreeAnalysis>();
904 PA.preserve<TargetLibraryAnalysis>();
905 if (MSSA)
906 PA.preserve<MemorySSAAnalysis>();
907 PA.preserve<LoopAnalysis>();
908 return PA;
909}
910
911void GVNPass::printPipeline(
912 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
913 static_cast<PassInfoMixin<GVNPass> *>(this)->printPipeline(
914 OS, MapClassName2PassName);
915
916 OS << '<';
917 if (Options.AllowScalarPRE != std::nullopt)
918 OS << (*Options.AllowScalarPRE ? "" : "no-") << "scalar-pre;";
919 if (Options.AllowLoadPRE != std::nullopt)
920 OS << (*Options.AllowLoadPRE ? "" : "no-") << "load-pre;";
921 if (Options.AllowLoadPRESplitBackedge != std::nullopt)
922 OS << (*Options.AllowLoadPRESplitBackedge ? "" : "no-")
923 << "split-backedge-load-pre;";
924 if (Options.AllowMemDep != std::nullopt)
925 OS << (*Options.AllowMemDep ? "" : "no-") << "memdep;";
926 if (Options.AllowMemorySSA != std::nullopt)
927 OS << (*Options.AllowMemorySSA ? "" : "no-") << "memoryssa";
928 OS << '>';
929}
930
931void GVNPass::salvageAndRemoveInstruction(Instruction *I) {
932 salvageKnowledge(I, AC);
933 salvageDebugInfo(I&: *I);
934 removeInstruction(I);
935}
936
937#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
938LLVM_DUMP_METHOD void GVNPass::dump(DenseMap<uint32_t, Value *> &Map) const {
939 errs() << "{\n";
940 for (const auto &[Num, Exp] : Map) {
941 errs() << Num << "\n";
942 Exp->dump();
943 }
944 errs() << "}\n";
945}
946#endif
947
948enum class AvailabilityState : char {
949 /// We know the block *is not* fully available. This is a fixpoint.
950 Unavailable = 0,
951 /// We know the block *is* fully available. This is a fixpoint.
952 Available = 1,
953 /// We do not know whether the block is fully available or not,
954 /// but we are currently speculating that it will be.
955 /// If it would have turned out that the block was, in fact, not fully
956 /// available, this would have been cleaned up into an Unavailable.
957 SpeculativelyAvailable = 2,
958};
959
960/// Return true if we can prove that the value
961/// we're analyzing is fully available in the specified block. As we go, keep
962/// track of which blocks we know are fully alive in FullyAvailableBlocks. This
963/// map is actually a tri-state map with the following values:
964/// 0) we know the block *is not* fully available.
965/// 1) we know the block *is* fully available.
966/// 2) we do not know whether the block is fully available or not, but we are
967/// currently speculating that it will be.
968static bool IsValueFullyAvailableInBlock(
969 BasicBlock *BB,
970 DenseMap<BasicBlock *, AvailabilityState> &FullyAvailableBlocks) {
971 SmallVector<BasicBlock *, 32> Worklist;
972 std::optional<BasicBlock *> UnavailableBB;
973
974 // The number of times we didn't find an entry for a block in a map and
975 // optimistically inserted an entry marking block as speculatively available.
976 unsigned NumNewNewSpeculativelyAvailableBBs = 0;
977
978#ifndef NDEBUG
979 SmallPtrSet<BasicBlock *, 32> NewSpeculativelyAvailableBBs;
980 SmallVector<BasicBlock *, 32> AvailableBBs;
981#endif
982
983 Worklist.emplace_back(Args&: BB);
984 while (!Worklist.empty()) {
985 BasicBlock *CurrBB = Worklist.pop_back_val(); // LoadFO - depth-first!
986 // Optimistically assume that the block is Speculatively Available and check
987 // to see if we already know about this block in one lookup.
988 std::pair<DenseMap<BasicBlock *, AvailabilityState>::iterator, bool> IV =
989 FullyAvailableBlocks.try_emplace(
990 Key: CurrBB, Args: AvailabilityState::SpeculativelyAvailable);
991 AvailabilityState &State = IV.first->second;
992
993 // Did the entry already exist for this block?
994 if (!IV.second) {
995 if (State == AvailabilityState::Unavailable) {
996 UnavailableBB = CurrBB;
997 break; // Backpropagate unavailability info.
998 }
999
1000#ifndef NDEBUG
1001 AvailableBBs.emplace_back(CurrBB);
1002#endif
1003 continue; // Don't recurse further, but continue processing worklist.
1004 }
1005
1006 // No entry found for block.
1007 ++NumNewNewSpeculativelyAvailableBBs;
1008 bool OutOfBudget = NumNewNewSpeculativelyAvailableBBs > MaxBBSpeculations;
1009
1010 // If we have exhausted our budget, mark this block as unavailable.
1011 // Also, if this block has no predecessors, the value isn't live-in here.
1012 if (OutOfBudget || pred_empty(BB: CurrBB)) {
1013 MaxBBSpeculationCutoffReachedTimes += (int)OutOfBudget;
1014 State = AvailabilityState::Unavailable;
1015 UnavailableBB = CurrBB;
1016 break; // Backpropagate unavailability info.
1017 }
1018
1019 // Tentatively consider this block as speculatively available.
1020#ifndef NDEBUG
1021 NewSpeculativelyAvailableBBs.insert(CurrBB);
1022#endif
1023 // And further recurse into block's predecessors, in depth-first order!
1024 Worklist.append(in_start: pred_begin(BB: CurrBB), in_end: pred_end(BB: CurrBB));
1025 }
1026
1027#if LLVM_ENABLE_STATS
1028 IsValueFullyAvailableInBlockNumSpeculationsMax.updateMax(
1029 NumNewNewSpeculativelyAvailableBBs);
1030#endif
1031
1032 // If the block isn't marked as fixpoint yet
1033 // (the Unavailable and Available states are fixpoints).
1034 auto MarkAsFixpointAndEnqueueSuccessors =
1035 [&](BasicBlock *BB, AvailabilityState FixpointState) {
1036 auto It = FullyAvailableBlocks.find(Val: BB);
1037 if (It == FullyAvailableBlocks.end())
1038 return; // Never queried this block, leave as-is.
1039 switch (AvailabilityState &State = It->second) {
1040 case AvailabilityState::Unavailable:
1041 case AvailabilityState::Available:
1042 return; // Don't backpropagate further, continue processing worklist.
1043 case AvailabilityState::SpeculativelyAvailable: // Fix it!
1044 State = FixpointState;
1045#ifndef NDEBUG
1046 assert(NewSpeculativelyAvailableBBs.erase(BB) &&
1047 "Found a speculatively available successor leftover?");
1048#endif
1049 // Queue successors for further processing.
1050 Worklist.append(in_start: succ_begin(BB), in_end: succ_end(BB));
1051 return;
1052 }
1053 };
1054
1055 if (UnavailableBB) {
1056 // Okay, we have encountered an unavailable block.
1057 // Mark speculatively available blocks reachable from UnavailableBB as
1058 // unavailable as well. Paths are terminated when they reach blocks not in
1059 // FullyAvailableBlocks or they are not marked as speculatively available.
1060 Worklist.clear();
1061 Worklist.append(in_start: succ_begin(BB: *UnavailableBB), in_end: succ_end(BB: *UnavailableBB));
1062 while (!Worklist.empty())
1063 MarkAsFixpointAndEnqueueSuccessors(Worklist.pop_back_val(),
1064 AvailabilityState::Unavailable);
1065 }
1066
1067#ifndef NDEBUG
1068 Worklist.clear();
1069 for (BasicBlock *AvailableBB : AvailableBBs)
1070 Worklist.append(succ_begin(AvailableBB), succ_end(AvailableBB));
1071 while (!Worklist.empty())
1072 MarkAsFixpointAndEnqueueSuccessors(Worklist.pop_back_val(),
1073 AvailabilityState::Available);
1074
1075 assert(NewSpeculativelyAvailableBBs.empty() &&
1076 "Must have fixed all the new speculatively available blocks.");
1077#endif
1078
1079 return !UnavailableBB;
1080}
1081
1082/// If the specified OldValue exists in ValuesPerBlock, replace its value with
1083/// NewValue.
1084static void replaceValuesPerBlockEntry(
1085 SmallVectorImpl<AvailableValueInBlock> &ValuesPerBlock, Value *OldValue,
1086 Value *NewValue) {
1087 for (AvailableValueInBlock &V : ValuesPerBlock) {
1088 if (V.AV.Val == OldValue)
1089 V.AV.Val = NewValue;
1090 if (V.AV.isSelectValue()) {
1091 if (V.AV.V1 == OldValue)
1092 V.AV.V1 = NewValue;
1093 if (V.AV.V2 == OldValue)
1094 V.AV.V2 = NewValue;
1095 }
1096 }
1097}
1098
1099/// Given a set of loads specified by ValuesPerBlock,
1100/// construct SSA form, allowing us to eliminate Load. This returns the value
1101/// that should be used at Load's definition site.
1102static Value *
1103ConstructSSAForLoadSet(LoadInst *Load,
1104 SmallVectorImpl<AvailableValueInBlock> &ValuesPerBlock,
1105 GVNPass &GVN) {
1106 // Check for the fully redundant, dominating load case. In this case, we can
1107 // just use the dominating value directly.
1108 if (ValuesPerBlock.size() == 1 &&
1109 GVN.getDominatorTree().properlyDominates(A: ValuesPerBlock[0].BB,
1110 B: Load->getParent())) {
1111 assert(!ValuesPerBlock[0].AV.isUndefValue() &&
1112 "Dead BB dominate this block");
1113 return ValuesPerBlock[0].MaterializeAdjustedValue(Load);
1114 }
1115
1116 // Otherwise, we have to construct SSA form.
1117 SmallVector<PHINode*, 8> NewPHIs;
1118 SSAUpdater SSAUpdate(&NewPHIs);
1119 SSAUpdate.Initialize(Ty: Load->getType(), Name: Load->getName());
1120
1121 for (const AvailableValueInBlock &AV : ValuesPerBlock) {
1122 BasicBlock *BB = AV.BB;
1123
1124 if (AV.AV.isUndefValue())
1125 continue;
1126
1127 if (SSAUpdate.HasValueForBlock(BB))
1128 continue;
1129
1130 // If the value is the load that we will be eliminating, and the block it's
1131 // available in is the block that the load is in, then don't add it as
1132 // SSAUpdater will resolve the value to the relevant phi which may let it
1133 // avoid phi construction entirely if there's actually only one value.
1134 if (BB == Load->getParent() &&
1135 ((AV.AV.isSimpleValue() && AV.AV.getSimpleValue() == Load) ||
1136 (AV.AV.isCoercedLoadValue() && AV.AV.getCoercedLoadValue() == Load)))
1137 continue;
1138
1139 SSAUpdate.AddAvailableValue(BB, V: AV.MaterializeAdjustedValue(Load));
1140 }
1141
1142 // Perform PHI construction.
1143 return SSAUpdate.GetValueInMiddleOfBlock(BB: Load->getParent());
1144}
1145
1146Value *AvailableValue::MaterializeAdjustedValue(LoadInst *Load,
1147 Instruction *InsertPt) const {
1148 Value *Res;
1149 Type *LoadTy = Load->getType();
1150 const DataLayout &DL = Load->getDataLayout();
1151 if (isSimpleValue()) {
1152 Res = getSimpleValue();
1153 if (Res->getType() != LoadTy) {
1154 Res = getValueForLoad(SrcVal: Res, Offset, LoadTy, InsertPt, F: Load->getFunction());
1155
1156 LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL VAL:\nOffset: " << Offset
1157 << " " << *getSimpleValue() << '\n'
1158 << *Res << '\n'
1159 << "\n\n\n");
1160 }
1161 } else if (isCoercedLoadValue()) {
1162 LoadInst *CoercedLoad = getCoercedLoadValue();
1163 if (CoercedLoad->getType() == LoadTy && Offset == 0) {
1164 Res = CoercedLoad;
1165 combineMetadataForCSE(K: CoercedLoad, J: Load, DoesKMove: false);
1166 } else {
1167 Res = getValueForLoad(SrcVal: CoercedLoad, Offset, LoadTy, InsertPt,
1168 F: Load->getFunction());
1169 // We are adding a new user for this load, for which the original
1170 // metadata may not hold. Additionally, the new load may have a different
1171 // size and type, so their metadata cannot be combined in any
1172 // straightforward way.
1173 // Drop all metadata that is not known to cause immediate UB on violation,
1174 // unless the load has !noundef, in which case all metadata violations
1175 // will be promoted to UB.
1176 // !noalias and !alias.scope are kept: the load is not moved and still
1177 // accesses the same memory, and these are independent of the load type
1178 // and offset, so they remain valid for the coerced result.
1179 if (!CoercedLoad->hasMetadata(KindID: LLVMContext::MD_noundef))
1180 CoercedLoad->dropUnknownNonDebugMetadata(
1181 KnownIDs: {LLVMContext::MD_dereferenceable,
1182 LLVMContext::MD_dereferenceable_or_null,
1183 LLVMContext::MD_invariant_load, LLVMContext::MD_invariant_group,
1184 LLVMContext::MD_alias_scope, LLVMContext::MD_noalias});
1185 LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL LOAD:\nOffset: " << Offset
1186 << " " << *getCoercedLoadValue() << '\n'
1187 << *Res << '\n'
1188 << "\n\n\n");
1189 }
1190 } else if (isMemIntrinValue()) {
1191 Res = getMemInstValueForLoad(SrcInst: getMemIntrinValue(), Offset, LoadTy,
1192 InsertPt, DL);
1193 LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL MEM INTRIN:\nOffset: " << Offset
1194 << " " << *getMemIntrinValue() << '\n'
1195 << *Res << '\n'
1196 << "\n\n\n");
1197 } else if (isSelectValue()) {
1198 // Introduce a new value select for a load from an eligible pointer select.
1199 Value *Cond = getSelectCondition();
1200 assert(V1 && V2 && "both value operands of the select must be present");
1201 Res = SelectInst::Create(C: Cond, S1: V1, S2: V2, NameStr: "", InsertBefore: InsertPt->getIterator());
1202 // We use the DebugLoc from the original load here, as this instruction
1203 // materializes the value that would previously have been loaded.
1204 cast<SelectInst>(Val: Res)->setDebugLoc(Load->getDebugLoc());
1205 } else {
1206 llvm_unreachable("Should not materialize value from dead block");
1207 }
1208 assert(Res && "failed to materialize?");
1209 return Res;
1210}
1211
1212static bool isLifetimeStart(const Instruction *Inst) {
1213 if (const IntrinsicInst* II = dyn_cast<IntrinsicInst>(Val: Inst))
1214 return II->getIntrinsicID() == Intrinsic::lifetime_start;
1215 return false;
1216}
1217
1218/// Assuming To can be reached from both From and Between, does Between lie on
1219/// every path from From to To?
1220static bool liesBetween(const Instruction *From, Instruction *Between,
1221 const Instruction *To, const DominatorTree *DT) {
1222 if (From->getParent() == Between->getParent())
1223 return DT->dominates(Def: From, User: Between);
1224 SmallPtrSet<BasicBlock *, 1> Exclusion;
1225 Exclusion.insert(Ptr: Between->getParent());
1226 return !isPotentiallyReachable(From, To, ExclusionSet: &Exclusion, DT);
1227}
1228
1229static const Instruction *findMayClobberedPtrAccess(LoadInst *Load,
1230 const DominatorTree *DT) {
1231 Value *PtrOp = Load->getPointerOperand();
1232 if (!PtrOp->hasUseList())
1233 return nullptr;
1234
1235 Instruction *OtherAccess = nullptr;
1236
1237 for (auto *U : PtrOp->users()) {
1238 if (U != Load && (isa<LoadInst>(Val: U) || isa<StoreInst>(Val: U))) {
1239 auto *I = cast<Instruction>(Val: U);
1240 if (I->getFunction() == Load->getFunction() && DT->dominates(Def: I, User: Load)) {
1241 // Use the most immediately dominating value.
1242 if (OtherAccess) {
1243 if (DT->dominates(Def: OtherAccess, User: I))
1244 OtherAccess = I;
1245 else
1246 assert(U == OtherAccess || DT->dominates(I, OtherAccess));
1247 } else
1248 OtherAccess = I;
1249 }
1250 }
1251 }
1252
1253 if (OtherAccess)
1254 return OtherAccess;
1255
1256 // There is no dominating use, check if we can find a closest non-dominating
1257 // use that lies between any other potentially available use and Load.
1258 for (auto *U : PtrOp->users()) {
1259 if (U != Load && (isa<LoadInst>(Val: U) || isa<StoreInst>(Val: U))) {
1260 auto *I = cast<Instruction>(Val: U);
1261 if (I->getFunction() == Load->getFunction() &&
1262 isPotentiallyReachable(From: I, To: Load, ExclusionSet: nullptr, DT)) {
1263 if (OtherAccess) {
1264 if (liesBetween(From: OtherAccess, Between: I, To: Load, DT)) {
1265 OtherAccess = I;
1266 } else if (!liesBetween(From: I, Between: OtherAccess, To: Load, DT)) {
1267 // These uses are both partially available at Load were it not for
1268 // the clobber, but neither lies strictly after the other.
1269 OtherAccess = nullptr;
1270 break;
1271 } // else: keep current OtherAccess since it lies between U and
1272 // Load.
1273 } else {
1274 OtherAccess = I;
1275 }
1276 }
1277 }
1278 }
1279
1280 return OtherAccess;
1281}
1282
1283/// Try to locate the three instruction involved in a missed
1284/// load-elimination case that is due to an intervening store.
1285static void reportMayClobberedLoad(LoadInst *Load, Instruction *DepInst,
1286 const DominatorTree *DT,
1287 OptimizationRemarkEmitter *ORE) {
1288 using namespace ore;
1289
1290 OptimizationRemarkMissed R(DEBUG_TYPE, "LoadClobbered", Load);
1291 R << "load of type " << NV("Type", Load->getType()) << " not eliminated"
1292 << setExtraArgs();
1293
1294 const Instruction *OtherAccess = findMayClobberedPtrAccess(Load, DT);
1295 if (OtherAccess)
1296 R << " in favor of " << NV("OtherAccess", OtherAccess);
1297
1298 R << " because it is clobbered by " << NV("ClobberedBy", DepInst);
1299
1300 ORE->emit(OptDiag&: R);
1301}
1302
1303// Find a dominating value for Loc memory location in the extended basic block
1304// (chain of basic blocks with single predecessors) starting From instruction.
1305// Returns the value from a matching load or a simple store to the same pointer.
1306static Value *findDominatingValue(const MemoryLocation &Loc, Type *LoadTy,
1307 Instruction *From, AAResults *AA) {
1308 uint32_t NumVisitedInsts = 0;
1309 BasicBlock *FromBB = From->getParent();
1310 BatchAAResults BatchAA(*AA);
1311 for (BasicBlock *BB = FromBB; BB; BB = BB->getSinglePredecessor())
1312 for (auto *Inst = BB == FromBB ? From : BB->getTerminator();
1313 Inst != nullptr; Inst = Inst->getPrevNode()) {
1314 // Stop the search if limit is reached.
1315 if (++NumVisitedInsts > MaxNumVisitedInsts)
1316 return nullptr;
1317 if (isModSet(MRI: BatchAA.getModRefInfo(I: Inst, OptLoc: Loc))) {
1318 // A simple store to the exact location can forward its value.
1319 if (auto *SI = dyn_cast<StoreInst>(Val: Inst))
1320 if (SI->isSimple() && SI->getPointerOperand() == Loc.Ptr &&
1321 SI->getValueOperand()->getType() == LoadTy)
1322 return SI->getValueOperand();
1323 return nullptr;
1324 }
1325 if (auto *LI = dyn_cast<LoadInst>(Val: Inst))
1326 if (LI->getPointerOperand() == Loc.Ptr && LI->getType() == LoadTy)
1327 return LI;
1328 }
1329 return nullptr;
1330}
1331
1332std::optional<AvailableValue>
1333GVNPass::AnalyzeSelectAvailability(LoadInst *Load, Value *Cond, Value *TrueAddr,
1334 Value *FalseAddr, Instruction *From) {
1335 assert(TrueAddr->getType() == Load->getPointerOperandType() &&
1336 "Invalid address type of true side of select dependency");
1337 assert(FalseAddr->getType() == Load->getPointerOperandType() &&
1338 "Invalid address type of false side of select dependency");
1339 // We can convert a load through a select address into a select of the two
1340 // loaded values only if both sides have a dominating, non-clobbered value of
1341 // the right type in the extended basic block ending at From.
1342 auto Loc = MemoryLocation::get(LI: Load);
1343 Value *V1 = findDominatingValue(Loc: Loc.getWithNewPtr(NewPtr: TrueAddr), LoadTy: Load->getType(),
1344 From, AA: getAliasAnalysis());
1345 if (!V1)
1346 return std::nullopt;
1347 Value *V2 = findDominatingValue(Loc: Loc.getWithNewPtr(NewPtr: FalseAddr), LoadTy: Load->getType(),
1348 From, AA: getAliasAnalysis());
1349 if (!V2)
1350 return std::nullopt;
1351 return AvailableValue::getSelect(Cond, V1, V2);
1352}
1353
1354std::optional<AvailableValue>
1355GVNPass::AnalyzeLoadAvailability(LoadInst *Load, const ReachingMemVal &Dep,
1356 Value *Address) {
1357 assert(Load->isUnordered() && "rules below are incorrect for ordered access");
1358 assert((Dep.Kind == DepKind::Def || Dep.Kind == DepKind::Clobber) &&
1359 "expected a local dependence");
1360
1361 Instruction *DepInst = Dep.Inst;
1362
1363 const DataLayout &DL = Load->getDataLayout();
1364 if (Dep.Kind == DepKind::Clobber) {
1365 // If the dependence is to a store that writes to a superset of the bits
1366 // read by the load, we can extract the bits we need for the load from the
1367 // stored value.
1368 if (StoreInst *DepSI = dyn_cast<StoreInst>(Val: DepInst)) {
1369 // Can't forward from non-atomic to atomic without violating memory model.
1370 if (Address && Load->isAtomic() <= DepSI->isAtomic()) {
1371 int Offset =
1372 analyzeLoadFromClobberingStore(LoadTy: Load->getType(), LoadPtr: Address, DepSI, DL);
1373 if (Offset != -1)
1374 return AvailableValue::get(V: DepSI->getValueOperand(), Offset);
1375 }
1376 }
1377
1378 // Check to see if we have something like this:
1379 // load i32* P
1380 // load i8* (P+1)
1381 // if we have this, replace the later with an extraction from the former.
1382 if (LoadInst *DepLoad = dyn_cast<LoadInst>(Val: DepInst)) {
1383 // If this is a clobber and L is the first instruction in its block, then
1384 // we have the first instruction in the entry block.
1385 // Can't forward from non-atomic to atomic without violating memory model.
1386 if (DepLoad != Load && Address &&
1387 Load->isAtomic() <= DepLoad->isAtomic()) {
1388 Type *LoadType = Load->getType();
1389 int Offset = Dep.Offset;
1390
1391 if (!isMemorySSAEnabled()) {
1392 // If MD reported clobber, check it was nested.
1393 if (canCoerceMustAliasedValueToLoad(StoredVal: DepLoad, LoadTy: LoadType,
1394 F: DepLoad->getFunction())) {
1395 const auto ClobberOff = MD->getClobberOffset(DepInst: DepLoad);
1396 // GVN has no deal with a negative offset.
1397 Offset = (ClobberOff == std::nullopt || *ClobberOff < 0)
1398 ? -1
1399 : *ClobberOff;
1400 }
1401 } else {
1402 if (!canCoerceMustAliasedValueToLoad(StoredVal: DepLoad, LoadTy: LoadType,
1403 F: DepLoad->getFunction()) ||
1404 Offset < 0)
1405 Offset = -1;
1406 }
1407 if (Offset == -1)
1408 Offset =
1409 analyzeLoadFromClobberingLoad(LoadTy: LoadType, LoadPtr: Address, DepLI: DepLoad, DL);
1410 if (Offset != -1)
1411 return AvailableValue::getLoad(Load: DepLoad, Offset);
1412 }
1413 }
1414
1415 // If the clobbering value is a memset/memcpy/memmove, see if we can
1416 // forward a value on from it.
1417 if (MemIntrinsic *DepMI = dyn_cast<MemIntrinsic>(Val: DepInst)) {
1418 if (Address && !Load->isAtomic()) {
1419 int Offset = analyzeLoadFromClobberingMemInst(LoadTy: Load->getType(), LoadPtr: Address,
1420 DepMI, DL);
1421 if (Offset != -1)
1422 return AvailableValue::getMI(MI: DepMI, Offset);
1423 }
1424 }
1425
1426 // Nothing known about this clobber, have to be conservative.
1427 LLVM_DEBUG(
1428 // fast print dep, using operator<< on instruction is too slow.
1429 dbgs() << "GVN: load "; Load->printAsOperand(dbgs());
1430 dbgs() << " is clobbered by " << *DepInst << '\n';);
1431 if (ORE->allowExtraAnalysis(DEBUG_TYPE))
1432 reportMayClobberedLoad(Load, DepInst, DT, ORE);
1433
1434 return std::nullopt;
1435 }
1436 assert(Dep.Kind == DepKind::Def && "follows from above");
1437
1438 // Loading the alloca -> undef.
1439 // Loading immediately after lifetime begin -> undef.
1440 if (isa<AllocaInst>(Val: DepInst) || isLifetimeStart(Inst: DepInst))
1441 return AvailableValue::get(V: UndefValue::get(T: Load->getType()));
1442
1443 if (Constant *InitVal =
1444 getInitialValueOfAllocation(V: DepInst, TLI, Ty: Load->getType()))
1445 return AvailableValue::get(V: InitVal);
1446
1447 if (StoreInst *S = dyn_cast<StoreInst>(Val: DepInst)) {
1448 // Reject loads and stores that are to the same address but are of
1449 // different types if we have to. If the stored value is convertable to
1450 // the loaded value, we can reuse it.
1451 if (!canCoerceMustAliasedValueToLoad(StoredVal: S->getValueOperand(), LoadTy: Load->getType(),
1452 F: S->getFunction()))
1453 return std::nullopt;
1454
1455 // Can't forward from non-atomic to atomic without violating memory model.
1456 if (S->isAtomic() < Load->isAtomic())
1457 return std::nullopt;
1458
1459 return AvailableValue::get(V: S->getValueOperand());
1460 }
1461
1462 if (LoadInst *LD = dyn_cast<LoadInst>(Val: DepInst)) {
1463 // If the types mismatch and we can't handle it, reject reuse of the load.
1464 // If the stored value is larger or equal to the loaded value, we can reuse
1465 // it.
1466 if (!canCoerceMustAliasedValueToLoad(StoredVal: LD, LoadTy: Load->getType(),
1467 F: LD->getFunction()))
1468 return std::nullopt;
1469
1470 // Can't forward from non-atomic to atomic without violating memory model.
1471 if (LD->isAtomic() < Load->isAtomic())
1472 return std::nullopt;
1473
1474 return AvailableValue::getLoad(Load: LD);
1475 }
1476
1477 // Check if load with Addr dependent from select can be converted to select
1478 // between load values. There must be no instructions between the found
1479 // loads and DepInst that may clobber the loads.
1480 if (auto *Sel = dyn_cast<SelectInst>(Val: DepInst)) {
1481 assert(Sel->getType() == Load->getPointerOperandType());
1482 if (auto AV = AnalyzeSelectAvailability(Load, Cond: Sel->getCondition(),
1483 TrueAddr: Sel->getTrueValue(),
1484 FalseAddr: Sel->getFalseValue(), From: DepInst))
1485 return AV;
1486 return std::nullopt;
1487 }
1488
1489 // Unknown def - must be conservative.
1490 LLVM_DEBUG(
1491 // fast print dep, using operator<< on instruction is too slow.
1492 dbgs() << "GVN: load "; Load->printAsOperand(dbgs());
1493 dbgs() << " has unknown def " << *DepInst << '\n';);
1494 return std::nullopt;
1495}
1496
1497void GVNPass::AnalyzeLoadAvailability(LoadInst *Load,
1498 SmallVectorImpl<ReachingMemVal> &Deps,
1499 AvailValInBlkVect &ValuesPerBlock,
1500 UnavailBlkVect &UnavailableBlocks) {
1501 // Filter out useless results (non-locals, etc). Keep track of the blocks
1502 // where we have a value available in repl, also keep track of whether we see
1503 // dependencies that produce an unknown value for the load (such as a call
1504 // that could potentially clobber the load).
1505 for (const auto &Dep : Deps) {
1506 BasicBlock *DepBB = Dep.Block;
1507
1508 if (DeadBlocks.count(key: DepBB)) {
1509 // Dead dependent mem-op disguise as a load evaluating the same value
1510 // as the load in question.
1511 ValuesPerBlock.push_back(Elt: AvailableValueInBlock::getUndef(BB: DepBB));
1512 continue;
1513 }
1514
1515 if (Dep.Kind == DepKind::Other) {
1516 UnavailableBlocks.push_back(Elt: DepBB);
1517 continue;
1518 }
1519
1520 // The load address is a select in this block: try to rematerialize the
1521 // load as a select of the two reaching values (one per side). The values
1522 // are searched for at the end of DepBB.
1523 if (Dep.Kind == DepKind::Select) {
1524 if (auto AV = AnalyzeSelectAvailability(
1525 Load, Cond: const_cast<Value *>(Dep.SelCond),
1526 TrueAddr: const_cast<Value *>(Dep.SelTrueAddr),
1527 FalseAddr: const_cast<Value *>(Dep.SelFalseAddr), From: DepBB->getTerminator())) {
1528 ValuesPerBlock.push_back(
1529 Elt: AvailableValueInBlock::get(BB: DepBB, AV: std::move(*AV)));
1530 } else {
1531 UnavailableBlocks.push_back(Elt: DepBB);
1532 }
1533 continue;
1534 }
1535
1536 // The address being loaded in this non-local block may not be the same as
1537 // the pointer operand of the load if PHI translation occurs. Make sure
1538 // to consider the right address.
1539 if (auto AV =
1540 AnalyzeLoadAvailability(Load, Dep, Address: const_cast<Value *>(Dep.Addr))) {
1541 // subtlety: because we know this was a non-local dependency, we know
1542 // it's safe to materialize anywhere between the instruction within
1543 // DepInfo and the end of it's block.
1544 ValuesPerBlock.push_back(
1545 Elt: AvailableValueInBlock::get(BB: DepBB, AV: std::move(*AV)));
1546 } else {
1547 UnavailableBlocks.push_back(Elt: DepBB);
1548 }
1549 }
1550
1551 assert(Deps.size() == ValuesPerBlock.size() + UnavailableBlocks.size() &&
1552 "post condition violation");
1553}
1554
1555/// Given the following code, v1 is partially available on some edges, but not
1556/// available on the edge from PredBB. This function tries to find if there is
1557/// another identical load in the other successor of PredBB.
1558///
1559/// v0 = load %addr
1560/// br %LoadBB
1561///
1562/// LoadBB:
1563/// v1 = load %addr
1564/// ...
1565///
1566/// PredBB:
1567/// ...
1568/// br %cond, label %LoadBB, label %SuccBB
1569///
1570/// SuccBB:
1571/// v2 = load %addr
1572/// ...
1573///
1574LoadInst *GVNPass::findLoadToHoistIntoPred(BasicBlock *Pred, BasicBlock *LoadBB,
1575 LoadInst *Load) {
1576 // For simplicity we handle a Pred has 2 successors only.
1577 auto *Term = Pred->getTerminator();
1578 if (Term->getNumSuccessors() != 2 || Term->isSpecialTerminator())
1579 return nullptr;
1580 auto *SuccBB = Term->getSuccessor(Idx: 0);
1581 if (SuccBB == LoadBB)
1582 SuccBB = Term->getSuccessor(Idx: 1);
1583 if (!SuccBB->getSinglePredecessor())
1584 return nullptr;
1585
1586 unsigned int NumInsts = MaxNumInsnsPerBlock;
1587 for (Instruction &Inst : *SuccBB) {
1588 if (Inst.isDebugOrPseudoInst())
1589 continue;
1590 if (--NumInsts == 0)
1591 return nullptr;
1592
1593 if (!Inst.isIdenticalTo(I: Load))
1594 continue;
1595
1596 bool HasLocalDep = true;
1597 if (!isMemorySSAEnabled()) {
1598 MemDepResult Dep = MD->getDependency(QueryInst: &Inst);
1599 HasLocalDep = !Dep.isNonLocal();
1600 } else {
1601 auto *MSSA = MSSAU->getMemorySSA();
1602 // Do not hoist if the identical load has ordering constraint.
1603 if (auto *MA = MSSA->getMemoryAccess(I: &Inst); MA && isa<MemoryUse>(Val: MA)) {
1604 auto *Clobber = MSSA->getWalker()->getClobberingMemoryAccess(MA);
1605 HasLocalDep = Clobber->getBlock() == SuccBB;
1606 }
1607 }
1608
1609 // If an identical load doesn't depends on any local instructions, it can
1610 // be safely moved to PredBB.
1611 // Also check for the implicit control flow instructions. See the comments
1612 // in PerformLoadPRE for details.
1613 if (!HasLocalDep && !ICF->isDominatedByICFIFromSameBlock(Insn: &Inst))
1614 return cast<LoadInst>(Val: &Inst);
1615
1616 // Otherwise there is something in the same BB clobbers the memory, we can't
1617 // move this and later load to PredBB.
1618 return nullptr;
1619 }
1620
1621 return nullptr;
1622}
1623
1624void GVNPass::eliminatePartiallyRedundantLoad(
1625 LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
1626 MapVector<BasicBlock *, Value *> &AvailableLoads,
1627 MapVector<BasicBlock *, LoadInst *> *CriticalEdgePredAndLoad) {
1628 for (const auto &AvailableLoad : AvailableLoads) {
1629 BasicBlock *UnavailableBlock = AvailableLoad.first;
1630 Value *LoadPtr = AvailableLoad.second;
1631
1632 auto *NewLoad =
1633 new LoadInst(Load->getType(), LoadPtr, Load->getName() + ".pre",
1634 Load->getProperties(),
1635 UnavailableBlock->getTerminator()->getIterator());
1636 NewLoad->setDebugLoc(Load->getDebugLoc());
1637 if (MSSAU) {
1638 auto *NewAccess = MSSAU->createMemoryAccessInBB(
1639 I: NewLoad, Definition: nullptr, BB: NewLoad->getParent(), Point: MemorySSA::BeforeTerminator);
1640 if (auto *NewDef = dyn_cast<MemoryDef>(Val: NewAccess))
1641 MSSAU->insertDef(Def: NewDef, /*RenameUses=*/true);
1642 else
1643 MSSAU->insertUse(Use: cast<MemoryUse>(Val: NewAccess), /*RenameUses=*/true);
1644 }
1645
1646 // Transfer the old load's AA tags to the new load.
1647 AAMDNodes Tags = Load->getAAMetadata();
1648 if (Tags)
1649 NewLoad->setAAMetadata(Tags);
1650
1651 if (auto *MD = Load->getMetadata(KindID: LLVMContext::MD_invariant_load))
1652 NewLoad->setMetadata(KindID: LLVMContext::MD_invariant_load, Node: MD);
1653 if (auto *InvGroupMD = Load->getMetadata(KindID: LLVMContext::MD_invariant_group))
1654 NewLoad->setMetadata(KindID: LLVMContext::MD_invariant_group, Node: InvGroupMD);
1655 if (auto *RangeMD = Load->getMetadata(KindID: LLVMContext::MD_range))
1656 NewLoad->setMetadata(KindID: LLVMContext::MD_range, Node: RangeMD);
1657 if (auto *NoFPClassMD = Load->getMetadata(KindID: LLVMContext::MD_nofpclass))
1658 NewLoad->setMetadata(KindID: LLVMContext::MD_nofpclass, Node: NoFPClassMD);
1659
1660 if (auto *AccessMD = Load->getMetadata(KindID: LLVMContext::MD_access_group))
1661 if (LI->getLoopFor(BB: Load->getParent()) == LI->getLoopFor(BB: UnavailableBlock))
1662 NewLoad->setMetadata(KindID: LLVMContext::MD_access_group, Node: AccessMD);
1663
1664 // We do not propagate the old load's debug location, because the new
1665 // load now lives in a different BB, and we want to avoid a jumpy line
1666 // table.
1667 // FIXME: How do we retain source locations without causing poor debugging
1668 // behavior?
1669
1670 // Add the newly created load.
1671 ValuesPerBlock.push_back(
1672 Elt: AvailableValueInBlock::get(BB: UnavailableBlock, V: NewLoad));
1673 if (MD)
1674 MD->invalidateCachedPointerInfo(Ptr: LoadPtr);
1675 LLVM_DEBUG(dbgs() << "GVN INSERTED " << *NewLoad << '\n');
1676
1677 // For PredBB in CriticalEdgePredAndLoad we need to replace the uses of old
1678 // load instruction with the new created load instruction.
1679 if (CriticalEdgePredAndLoad) {
1680 auto It = CriticalEdgePredAndLoad->find(Key: UnavailableBlock);
1681 if (It != CriticalEdgePredAndLoad->end()) {
1682 ++NumPRELoadMoved2CEPred;
1683 ICF->insertInstructionTo(Inst: NewLoad, BB: UnavailableBlock);
1684 LoadInst *OldLoad = It->second;
1685 combineMetadataForCSE(K: NewLoad, J: OldLoad, /*DoesKMove=*/true);
1686 OldLoad->replaceAllUsesWith(V: NewLoad);
1687 replaceValuesPerBlockEntry(ValuesPerBlock, OldValue: OldLoad, NewValue: NewLoad);
1688 if (uint32_t ValNo = VN.lookup(V: OldLoad, Verify: false))
1689 LeaderTable.erase(N: ValNo, I: OldLoad, BB: OldLoad->getParent());
1690 removeInstruction(I: OldLoad);
1691 }
1692 }
1693 }
1694
1695 // Perform PHI construction.
1696 Value *V = ConstructSSAForLoadSet(Load, ValuesPerBlock, GVN&: *this);
1697 // ConstructSSAForLoadSet is responsible for combining metadata.
1698 ICF->removeUsersOf(Inst: Load);
1699 Load->replaceAllUsesWith(V);
1700 if (isa<PHINode>(Val: V))
1701 V->takeName(V: Load);
1702 if (Instruction *I = dyn_cast<Instruction>(Val: V))
1703 I->setDebugLoc(Load->getDebugLoc());
1704 if (MD && V->getType()->isPtrOrPtrVectorTy())
1705 MD->invalidateCachedPointerInfo(Ptr: V);
1706 ORE->emit(RemarkBuilder: [&]() {
1707 return OptimizationRemark(DEBUG_TYPE, "LoadPRE", Load)
1708 << "load eliminated by PRE";
1709 });
1710 salvageAndRemoveInstruction(I: Load);
1711}
1712
1713bool GVNPass::PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
1714 UnavailBlkVect &UnavailableBlocks) {
1715 // Okay, we have *some* definitions of the value. This means that the value
1716 // is available in some of our (transitive) predecessors. Lets think about
1717 // doing PRE of this load. This will involve inserting a new load into the
1718 // predecessor when it's not available. We could do this in general, but
1719 // prefer to not increase code size. As such, we only do this when we know
1720 // that we only have to insert *one* load (which means we're basically moving
1721 // the load, not inserting a new one).
1722
1723 SmallPtrSet<BasicBlock *, 4> Blockers(llvm::from_range, UnavailableBlocks);
1724
1725 // Let's find the first basic block with more than one predecessor. Walk
1726 // backwards through predecessors if needed.
1727 BasicBlock *LoadBB = Load->getParent();
1728 BasicBlock *TmpBB = LoadBB;
1729
1730 // Check that there is no implicit control flow instructions above our load in
1731 // its block. If there is an instruction that doesn't always pass the
1732 // execution to the following instruction, then moving through it may become
1733 // invalid. For example:
1734 //
1735 // int arr[LEN];
1736 // int index = ???;
1737 // ...
1738 // guard(0 <= index && index < LEN);
1739 // use(arr[index]);
1740 //
1741 // It is illegal to move the array access to any point above the guard,
1742 // because if the index is out of bounds we should deoptimize rather than
1743 // access the array.
1744 // Check that there is no guard in this block above our instruction.
1745 bool MustEnsureSafetyOfSpeculativeExecution =
1746 ICF->isDominatedByICFIFromSameBlock(Insn: Load);
1747
1748 while (TmpBB->getSinglePredecessor()) {
1749 TmpBB = TmpBB->getSinglePredecessor();
1750 if (TmpBB == LoadBB) // Infinite (unreachable) loop.
1751 return false;
1752 if (Blockers.count(Ptr: TmpBB))
1753 return false;
1754
1755 // If any of these blocks has more than one successor (i.e. if the edge we
1756 // just traversed was critical), then there are other paths through this
1757 // block along which the load may not be anticipated. Hoisting the load
1758 // above this block would be adding the load to execution paths along
1759 // which it was not previously executed.
1760 if (TmpBB->getTerminator()->getNumSuccessors() != 1)
1761 return false;
1762
1763 // Check that there is no implicit control flow in a block above.
1764 MustEnsureSafetyOfSpeculativeExecution =
1765 MustEnsureSafetyOfSpeculativeExecution || ICF->hasICF(BB: TmpBB);
1766 }
1767
1768 assert(TmpBB);
1769 LoadBB = TmpBB;
1770
1771 // Check to see how many predecessors have the loaded value fully
1772 // available.
1773 MapVector<BasicBlock *, Value *> PredLoads;
1774 DenseMap<BasicBlock *, AvailabilityState> FullyAvailableBlocks;
1775 for (const AvailableValueInBlock &AV : ValuesPerBlock)
1776 FullyAvailableBlocks[AV.BB] = AvailabilityState::Available;
1777 for (BasicBlock *UnavailableBB : UnavailableBlocks)
1778 FullyAvailableBlocks[UnavailableBB] = AvailabilityState::Unavailable;
1779
1780 // The edge from Pred to LoadBB is a critical edge will be splitted.
1781 SmallVector<BasicBlock *, 4> CriticalEdgePredSplit;
1782 // The edge from Pred to LoadBB is a critical edge, another successor of Pred
1783 // contains a load can be moved to Pred. This data structure maps the Pred to
1784 // the movable load.
1785 MapVector<BasicBlock *, LoadInst *> CriticalEdgePredAndLoad;
1786 for (BasicBlock *Pred : predecessors(BB: LoadBB)) {
1787 // If any predecessor block is an EH pad that does not allow non-PHI
1788 // instructions before the terminator, we can't PRE the load.
1789 if (Pred->getTerminator()->isEHPad()) {
1790 LLVM_DEBUG(
1791 dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD PREDECESSOR '"
1792 << Pred->getName() << "': " << *Load << '\n');
1793 return false;
1794 }
1795
1796 if (IsValueFullyAvailableInBlock(BB: Pred, FullyAvailableBlocks)) {
1797 continue;
1798 }
1799
1800 if (Pred->getTerminator()->getNumSuccessors() != 1) {
1801 if (isa<IndirectBrInst>(Val: Pred->getTerminator())) {
1802 LLVM_DEBUG(
1803 dbgs() << "COULD NOT PRE LOAD BECAUSE OF INDBR CRITICAL EDGE '"
1804 << Pred->getName() << "': " << *Load << '\n');
1805 return false;
1806 }
1807
1808 if (LoadBB->isEHPad()) {
1809 LLVM_DEBUG(
1810 dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD CRITICAL EDGE '"
1811 << Pred->getName() << "': " << *Load << '\n');
1812 return false;
1813 }
1814
1815 // Do not split backedge as it will break the canonical loop form.
1816 if (!isLoadPRESplitBackedgeEnabled())
1817 if (DT->dominates(A: LoadBB, B: Pred)) {
1818 LLVM_DEBUG(
1819 dbgs()
1820 << "COULD NOT PRE LOAD BECAUSE OF A BACKEDGE CRITICAL EDGE '"
1821 << Pred->getName() << "': " << *Load << '\n');
1822 return false;
1823 }
1824
1825 if (LoadInst *LI = findLoadToHoistIntoPred(Pred, LoadBB, Load))
1826 CriticalEdgePredAndLoad[Pred] = LI;
1827 else
1828 CriticalEdgePredSplit.push_back(Elt: Pred);
1829 } else {
1830 // Only add the predecessors that will not be split for now.
1831 PredLoads[Pred] = nullptr;
1832 }
1833 }
1834
1835 // Decide whether PRE is profitable for this load.
1836 unsigned NumInsertPreds = PredLoads.size() + CriticalEdgePredSplit.size();
1837 unsigned NumUnavailablePreds = NumInsertPreds +
1838 CriticalEdgePredAndLoad.size();
1839 assert(NumUnavailablePreds != 0 &&
1840 "Fully available value should already be eliminated!");
1841 (void)NumUnavailablePreds;
1842
1843 // If we need to insert new load in multiple predecessors, reject it.
1844 // FIXME: If we could restructure the CFG, we could make a common pred with
1845 // all the preds that don't have an available Load and insert a new load into
1846 // that one block.
1847 if (NumInsertPreds > 1)
1848 return false;
1849
1850 // Now we know where we will insert load. We must ensure that it is safe
1851 // to speculatively execute the load at that points.
1852 if (MustEnsureSafetyOfSpeculativeExecution) {
1853 if (CriticalEdgePredSplit.size())
1854 if (!isSafeToSpeculativelyExecute(I: Load, CtxI: &*LoadBB->getFirstNonPHIIt(), AC,
1855 DT))
1856 return false;
1857 for (auto &PL : PredLoads)
1858 if (!isSafeToSpeculativelyExecute(I: Load, CtxI: PL.first->getTerminator(), AC,
1859 DT))
1860 return false;
1861 for (auto &CEP : CriticalEdgePredAndLoad)
1862 if (!isSafeToSpeculativelyExecute(I: Load, CtxI: CEP.first->getTerminator(), AC,
1863 DT))
1864 return false;
1865 }
1866
1867 // Split critical edges, and update the unavailable predecessors accordingly.
1868 for (BasicBlock *OrigPred : CriticalEdgePredSplit) {
1869 BasicBlock *NewPred = splitCriticalEdges(Pred: OrigPred, Succ: LoadBB);
1870 assert(!PredLoads.count(OrigPred) && "Split edges shouldn't be in map!");
1871 PredLoads[NewPred] = nullptr;
1872 LLVM_DEBUG(dbgs() << "Split critical edge " << OrigPred->getName() << "->"
1873 << LoadBB->getName() << '\n');
1874 }
1875
1876 for (auto &CEP : CriticalEdgePredAndLoad)
1877 PredLoads[CEP.first] = nullptr;
1878
1879 // Check if the load can safely be moved to all the unavailable predecessors.
1880 bool CanDoPRE = true;
1881 const DataLayout &DL = Load->getDataLayout();
1882 SmallVector<Instruction*, 8> NewInsts;
1883 for (auto &PredLoad : PredLoads) {
1884 BasicBlock *UnavailablePred = PredLoad.first;
1885
1886 // Do PHI translation to get its value in the predecessor if necessary. The
1887 // returned pointer (if non-null) is guaranteed to dominate UnavailablePred.
1888 // We do the translation for each edge we skipped by going from Load's block
1889 // to LoadBB, otherwise we might miss pieces needing translation.
1890
1891 // If all preds have a single successor, then we know it is safe to insert
1892 // the load on the pred (?!?), so we can insert code to materialize the
1893 // pointer if it is not available.
1894 Value *LoadPtr = Load->getPointerOperand();
1895 BasicBlock *Cur = Load->getParent();
1896 while (Cur != LoadBB) {
1897 PHITransAddr Address(LoadPtr, DL, AC);
1898 LoadPtr = Address.translateWithInsertion(CurBB: Cur, PredBB: Cur->getSinglePredecessor(),
1899 DT: *DT, NewInsts);
1900 if (!LoadPtr) {
1901 CanDoPRE = false;
1902 break;
1903 }
1904 Cur = Cur->getSinglePredecessor();
1905 }
1906
1907 if (LoadPtr) {
1908 PHITransAddr Address(LoadPtr, DL, AC);
1909 LoadPtr = Address.translateWithInsertion(CurBB: LoadBB, PredBB: UnavailablePred, DT: *DT,
1910 NewInsts);
1911 }
1912 // If we couldn't find or insert a computation of this phi translated value,
1913 // we fail PRE.
1914 if (!LoadPtr) {
1915 LLVM_DEBUG(dbgs() << "COULDN'T INSERT PHI TRANSLATED VALUE OF: "
1916 << *Load->getPointerOperand() << "\n");
1917 CanDoPRE = false;
1918 break;
1919 }
1920
1921 PredLoad.second = LoadPtr;
1922 }
1923
1924 if (!CanDoPRE) {
1925 while (!NewInsts.empty()) {
1926 // Erase instructions generated by the failed PHI translation before
1927 // trying to number them. PHI translation might insert instructions
1928 // in basic blocks other than the current one, and we delete them
1929 // directly, as salvageAndRemoveInstruction only allows removing from the
1930 // current basic block.
1931 NewInsts.pop_back_val()->eraseFromParent();
1932 }
1933 // HINT: Don't revert the edge-splitting as following transformation may
1934 // also need to split these critical edges.
1935 return !CriticalEdgePredSplit.empty();
1936 }
1937
1938 // Okay, we can eliminate this load by inserting a reload in the predecessor
1939 // and using PHI construction to get the value in the other predecessors, do
1940 // it.
1941 LLVM_DEBUG(dbgs() << "GVN REMOVING PRE LOAD: " << *Load << '\n');
1942 LLVM_DEBUG(if (!NewInsts.empty()) dbgs() << "INSERTED " << NewInsts.size()
1943 << " INSTS: " << *NewInsts.back()
1944 << '\n');
1945
1946 // Assign value numbers to the new instructions.
1947 for (Instruction *I : NewInsts) {
1948 // Instructions that have been inserted in predecessor(s) to materialize
1949 // the load address do not retain their original debug locations. Doing
1950 // so could lead to confusing (but correct) source attributions.
1951 I->updateLocationAfterHoist();
1952
1953 // FIXME: We really _ought_ to insert these value numbers into their
1954 // parent's availability map. However, in doing so, we risk getting into
1955 // ordering issues. If a block hasn't been processed yet, we would be
1956 // marking a value as AVAIL-IN, which isn't what we intend.
1957 VN.lookupOrAdd(V: I);
1958 }
1959
1960 eliminatePartiallyRedundantLoad(Load, ValuesPerBlock, AvailableLoads&: PredLoads,
1961 CriticalEdgePredAndLoad: &CriticalEdgePredAndLoad);
1962 ++NumPRELoad;
1963 return true;
1964}
1965
1966bool GVNPass::performLoopLoadPRE(LoadInst *Load,
1967 AvailValInBlkVect &ValuesPerBlock,
1968 UnavailBlkVect &UnavailableBlocks) {
1969 const Loop *L = LI->getLoopFor(BB: Load->getParent());
1970 // TODO: Generalize to other loop blocks that dominate the latch.
1971 if (!L || L->getHeader() != Load->getParent())
1972 return false;
1973
1974 BasicBlock *Preheader = L->getLoopPreheader();
1975 BasicBlock *Latch = L->getLoopLatch();
1976 if (!Preheader || !Latch)
1977 return false;
1978
1979 Value *LoadPtr = Load->getPointerOperand();
1980 // Must be available in preheader.
1981 if (!L->isLoopInvariant(V: LoadPtr))
1982 return false;
1983
1984 // We plan to hoist the load to preheader without introducing a new fault.
1985 // In order to do it, we need to prove that we cannot side-exit the loop
1986 // once loop header is first entered before execution of the load.
1987 if (ICF->isDominatedByICFIFromSameBlock(Insn: Load))
1988 return false;
1989
1990 BasicBlock *LoopBlock = nullptr;
1991 for (auto *Blocker : UnavailableBlocks) {
1992 // Blockers from outside the loop are handled in preheader.
1993 if (!L->contains(BB: Blocker))
1994 continue;
1995
1996 // Only allow one loop block. Loop header is not less frequently executed
1997 // than each loop block, and likely it is much more frequently executed. But
1998 // in case of multiple loop blocks, we need extra information (such as block
1999 // frequency info) to understand whether it is profitable to PRE into
2000 // multiple loop blocks.
2001 if (LoopBlock)
2002 return false;
2003
2004 // Do not sink into inner loops. This may be non-profitable.
2005 if (L != LI->getLoopFor(BB: Blocker))
2006 return false;
2007
2008 // Blocks that dominate the latch execute on every single iteration, maybe
2009 // except the last one. So PREing into these blocks doesn't make much sense
2010 // in most cases. But the blocks that do not necessarily execute on each
2011 // iteration are sometimes much colder than the header, and this is when
2012 // PRE is potentially profitable.
2013 if (DT->dominates(A: Blocker, B: Latch))
2014 return false;
2015
2016 // Make sure that the terminator itself doesn't clobber.
2017 if (Blocker->getTerminator()->mayWriteToMemory())
2018 return false;
2019
2020 LoopBlock = Blocker;
2021 }
2022
2023 if (!LoopBlock)
2024 return false;
2025
2026 // Make sure the memory at this pointer cannot be freed, therefore we can
2027 // safely reload from it after clobber.
2028 if (LoadPtr->canBeFreed())
2029 return false;
2030
2031 // TODO: Support critical edge splitting if blocker has more than 1 successor.
2032 MapVector<BasicBlock *, Value *> AvailableLoads;
2033 AvailableLoads[LoopBlock] = LoadPtr;
2034 AvailableLoads[Preheader] = LoadPtr;
2035
2036 LLVM_DEBUG(dbgs() << "GVN REMOVING PRE LOOP LOAD: " << *Load << '\n');
2037 eliminatePartiallyRedundantLoad(Load, ValuesPerBlock, AvailableLoads,
2038 /*CriticalEdgePredAndLoad*/ nullptr);
2039 ++NumPRELoopLoad;
2040 return true;
2041}
2042
2043static void reportLoadElim(LoadInst *Load, Value *AvailableValue,
2044 OptimizationRemarkEmitter *ORE) {
2045 using namespace ore;
2046
2047 ORE->emit(RemarkBuilder: [&]() {
2048 return OptimizationRemark(DEBUG_TYPE, "LoadElim", Load)
2049 << "load of type " << NV("Type", Load->getType()) << " eliminated"
2050 << setExtraArgs() << " in favor of "
2051 << NV("InfavorOfValue", AvailableValue);
2052 });
2053}
2054
2055/// Attempt to eliminate a load whose dependencies are
2056/// non-local by performing PHI construction.
2057bool GVNPass::processNonLocalLoad(LoadInst *Load) {
2058 // Non-local speculations are not allowed under asan.
2059 if (Load->getFunction()->hasFnAttribute(Kind: Attribute::SanitizeAddress) ||
2060 Load->getFunction()->hasFnAttribute(Kind: Attribute::SanitizeHWAddress))
2061 return false;
2062
2063 // Find the non-local dependencies of the load.
2064 LoadDepVect Deps;
2065 MD->getNonLocalPointerDependency(QueryInst: Load, Result&: Deps);
2066
2067 // If we had to process more than one hundred blocks to find the
2068 // dependencies, this load isn't worth worrying about. Optimizing
2069 // it will be too expensive.
2070 unsigned NumDeps = Deps.size();
2071 if (NumDeps > MaxNumDeps)
2072 return false;
2073
2074 SmallVector<ReachingMemVal, 64> MemVals;
2075 MemVals.reserve(N: Deps.size());
2076
2077 for (const NonLocalDepResult &Dep : Deps) {
2078 const auto &R = Dep.getResult();
2079 SelectAddr SelAddr = Dep.getAddress();
2080 BasicBlock *BB = Dep.getBB();
2081 Instruction *Inst = R.getInst();
2082 if (R.isSelect()) {
2083 auto [Cond, Addrs] = SelAddr.getSelectCondAndAddrs();
2084 MemVals.emplace_back(
2085 Args: ReachingMemVal::getSelect(BB, Cond, TrueAddr: Addrs.first, FalseAddr: Addrs.second));
2086 continue;
2087 }
2088 Value *Address = SelAddr.getAddr();
2089 if (R.isClobber())
2090 MemVals.emplace_back(Args: ReachingMemVal::getClobber(Addr: Address, Inst));
2091 else if (R.isDef())
2092 MemVals.emplace_back(Args: ReachingMemVal::getDef(Addr: Address, Inst));
2093 else
2094 MemVals.emplace_back(Args: ReachingMemVal::getUnknown(BB, Addr: Address, Inst));
2095 }
2096
2097 return processNonLocalLoad(L: Load, Deps&: MemVals);
2098}
2099
2100bool GVNPass::processNonLocalLoad(LoadInst *Load,
2101 SmallVectorImpl<ReachingMemVal> &Deps) {
2102 // If we had a phi translation failure, we'll have a single entry which is a
2103 // clobber in the current block. Reject this early.
2104 if (Deps.size() == 1 && Deps[0].Kind == DepKind::Other) {
2105 LLVM_DEBUG(dbgs() << "GVN: non-local load "; Load->printAsOperand(dbgs());
2106 dbgs() << " has unknown dependencies\n";);
2107 return false;
2108 }
2109
2110 bool Changed = false;
2111 // This is a limited form of scalar PRE for load indices. If this load follows
2112 // a GEP, see if we can PRE the indices before analyzing.
2113 if (isScalarPREEnabled()) {
2114 if (GetElementPtrInst *GEP =
2115 dyn_cast<GetElementPtrInst>(Val: Load->getOperand(i_nocapture: 0))) {
2116 for (Use &U : GEP->indices())
2117 if (Instruction *I = dyn_cast<Instruction>(Val: U.get()))
2118 Changed |= performScalarPRE(I);
2119 }
2120 }
2121
2122 // Step 1: Analyze the availability of the load.
2123 AvailValInBlkVect ValuesPerBlock;
2124 UnavailBlkVect UnavailableBlocks;
2125 AnalyzeLoadAvailability(Load, Deps, ValuesPerBlock, UnavailableBlocks);
2126
2127 // If we have no predecessors that produce a known value for this load, exit
2128 // early.
2129 if (ValuesPerBlock.empty())
2130 return Changed;
2131
2132 // Step 2: Eliminate fully redundancy.
2133 //
2134 // If all of the instructions we depend on produce a known value for this
2135 // load, then it is fully redundant and we can use PHI insertion to compute
2136 // its value. Insert PHIs and remove the fully redundant value now.
2137 if (UnavailableBlocks.empty()) {
2138 LLVM_DEBUG(dbgs() << "GVN REMOVING NONLOCAL LOAD: " << *Load << '\n');
2139
2140 // Perform PHI construction.
2141 Value *V = ConstructSSAForLoadSet(Load, ValuesPerBlock, GVN&: *this);
2142 // ConstructSSAForLoadSet is responsible for combining metadata.
2143 ICF->removeUsersOf(Inst: Load);
2144 Load->replaceAllUsesWith(V);
2145
2146 if (isa<PHINode>(Val: V))
2147 V->takeName(V: Load);
2148 if (Instruction *I = dyn_cast<Instruction>(Val: V))
2149 // If instruction I has debug info, then we should not update it.
2150 // Also, if I has a null DebugLoc, then it is still potentially incorrect
2151 // to propagate Load's DebugLoc because Load may not post-dominate I.
2152 if (Load->getDebugLoc() && Load->getParent() == I->getParent())
2153 I->setDebugLoc(Load->getDebugLoc());
2154 if (MD && V->getType()->isPtrOrPtrVectorTy())
2155 MD->invalidateCachedPointerInfo(Ptr: V);
2156 ++NumGVNLoad;
2157 reportLoadElim(Load, AvailableValue: V, ORE);
2158 salvageAndRemoveInstruction(I: Load);
2159 return true;
2160 }
2161
2162 // Step 3: Eliminate partial redundancy.
2163 if (!isLoadPREEnabled())
2164 return Changed;
2165 if (!isLoadInLoopPREEnabled() && LI->getLoopFor(BB: Load->getParent()))
2166 return Changed;
2167
2168 if (performLoopLoadPRE(Load, ValuesPerBlock, UnavailableBlocks) ||
2169 PerformLoadPRE(Load, ValuesPerBlock, UnavailableBlocks))
2170 return true;
2171
2172 return Changed;
2173}
2174
2175bool GVNPass::processAssumeIntrinsic(AssumeInst *IntrinsicI) {
2176 Value *V = IntrinsicI->getArgOperand(i: 0);
2177
2178 if (ConstantInt *Cond = dyn_cast<ConstantInt>(Val: V)) {
2179 if (Cond->isZero()) {
2180 Type *Int8Ty = Type::getInt8Ty(C&: V->getContext());
2181 Type *PtrTy = PointerType::get(C&: V->getContext(), AddressSpace: 0);
2182 // Insert a new store to null instruction before the load to indicate that
2183 // this code is not reachable. FIXME: We could insert unreachable
2184 // instruction directly because we can modify the CFG.
2185 auto *NewS =
2186 new StoreInst(PoisonValue::get(T: Int8Ty), Constant::getNullValue(Ty: PtrTy),
2187 IntrinsicI->getIterator());
2188 if (MSSAU) {
2189 const MemoryUseOrDef *FirstNonDom = nullptr;
2190 const auto *AL =
2191 MSSAU->getMemorySSA()->getBlockAccesses(BB: IntrinsicI->getParent());
2192
2193 // If there are accesses in the current basic block, find the first one
2194 // that does not come before NewS. The new memory access is inserted
2195 // after the found access or before the terminator if no such access is
2196 // found.
2197 if (AL) {
2198 for (const auto &Acc : *AL) {
2199 if (auto *Current = dyn_cast<MemoryUseOrDef>(Val: &Acc))
2200 if (!Current->getMemoryInst()->comesBefore(Other: NewS)) {
2201 FirstNonDom = Current;
2202 break;
2203 }
2204 }
2205 }
2206
2207 auto *NewDef =
2208 FirstNonDom ? MSSAU->createMemoryAccessBefore(
2209 I: NewS, Definition: nullptr,
2210 InsertPt: const_cast<MemoryUseOrDef *>(FirstNonDom))
2211 : MSSAU->createMemoryAccessInBB(
2212 I: NewS, Definition: nullptr,
2213 BB: NewS->getParent(), Point: MemorySSA::BeforeTerminator);
2214
2215 MSSAU->insertDef(Def: cast<MemoryDef>(Val: NewDef), /*RenameUses=*/false);
2216 }
2217 }
2218 if (isAssumeWithEmptyBundle(Assume: *IntrinsicI)) {
2219 salvageAndRemoveInstruction(I: IntrinsicI);
2220 return true;
2221 }
2222 return false;
2223 }
2224
2225 if (isa<Constant>(Val: V)) {
2226 // If it's not false, and constant, it must evaluate to true. This means our
2227 // assume is assume(true), and thus, pointless, and we don't want to do
2228 // anything more here.
2229 return false;
2230 }
2231
2232 Constant *True = ConstantInt::getTrue(Context&: V->getContext());
2233 return propagateEquality(LHS: V, RHS: True, Root: IntrinsicI);
2234}
2235
2236static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl) {
2237 patchReplacementInstruction(I, Repl);
2238 I->replaceAllUsesWith(V: Repl);
2239}
2240
2241/// If a load has !invariant.group, try to find the most-dominating instruction
2242/// with the same metadata and equivalent pointer (modulo bitcasts and zero
2243/// GEPs). If one is found that dominates the load, its value can be reused.
2244static Instruction *findInvariantGroupValue(LoadInst *L, DominatorTree &DT) {
2245 Value *PointerOperand = L->getPointerOperand()->stripPointerCasts();
2246
2247 // It's not safe to walk the use list of a global value because function
2248 // passes aren't allowed to look outside their functions.
2249 // FIXME: this could be fixed by filtering instructions from outside of
2250 // current function.
2251 if (isa<Constant>(Val: PointerOperand))
2252 return nullptr;
2253
2254 // Queue to process all pointers that are equivalent to load operand.
2255 SmallVector<Value *, 8> PointerUsesQueue;
2256 PointerUsesQueue.push_back(Elt: PointerOperand);
2257
2258 Instruction *MostDominatingInstruction = L;
2259
2260 // FIXME: This loop is potentially O(n^2) due to repeated dominates checks.
2261 while (!PointerUsesQueue.empty()) {
2262 Value *Ptr = PointerUsesQueue.pop_back_val();
2263 assert(Ptr && !isa<GlobalValue>(Ptr) &&
2264 "Null or GlobalValue should not be inserted");
2265
2266 for (User *U : Ptr->users()) {
2267 auto *I = dyn_cast<Instruction>(Val: U);
2268 if (!I || I == L || !DT.dominates(Def: I, User: MostDominatingInstruction))
2269 continue;
2270
2271 // Add bitcasts and zero GEPs to queue.
2272 // TODO: Should drop bitcast?
2273 if (isa<BitCastInst>(Val: I) ||
2274 (isa<GetElementPtrInst>(Val: I) &&
2275 cast<GetElementPtrInst>(Val: I)->hasAllZeroIndices())) {
2276 PointerUsesQueue.push_back(Elt: I);
2277 continue;
2278 }
2279
2280 // If we hit a load/store with an invariant.group metadata and the same
2281 // pointer operand, we can assume that value pointed to by the pointer
2282 // operand didn't change.
2283 if (I->hasMetadata(KindID: LLVMContext::MD_invariant_group) &&
2284 Ptr == getLoadStorePointerOperand(V: I) && !I->isVolatile())
2285 MostDominatingInstruction = I;
2286 }
2287 }
2288
2289 return MostDominatingInstruction != L ? MostDominatingInstruction : nullptr;
2290}
2291
2292/// Return the memory location accessed by the (masked) load/store instruction
2293/// `I`, if the instruction could potentially provide a useful value for
2294/// eliminating the load.
2295static std::optional<MemoryLocation>
2296maybeLoadStoreLocation(Instruction *I, bool AllowStores,
2297 const TargetLibraryInfo *TLI) {
2298 if (auto *LI = dyn_cast<LoadInst>(Val: I))
2299 return MemoryLocation::get(LI);
2300
2301 if (auto *II = dyn_cast<IntrinsicInst>(Val: I)) {
2302 switch (II->getIntrinsicID()) {
2303 case Intrinsic::masked_load:
2304 return MemoryLocation::getForArgument(Call: II, ArgIdx: 0, TLI);
2305 case Intrinsic::masked_store:
2306 if (AllowStores)
2307 return MemoryLocation::getForArgument(Call: II, ArgIdx: 1, TLI);
2308 return std::nullopt;
2309 default:
2310 break;
2311 }
2312 }
2313
2314 if (!AllowStores)
2315 return std::nullopt;
2316
2317 if (auto *SI = dyn_cast<StoreInst>(Val: I))
2318 return MemoryLocation::get(SI);
2319 return std::nullopt;
2320}
2321
2322/// Scan the users of each MemoryAccess in `ClobbersList` that belong to `BB`,
2323/// looking for memory reads whose location aliases `Loc` and dominates our
2324/// load.
2325std::optional<GVNPass::ReachingMemVal> GVNPass::scanMemoryAccessesUsers(
2326 const MemoryLocation &Loc, bool IsInvariantLoad, BasicBlock *BB,
2327 const SmallVectorImpl<MemoryAccess *> &ClobbersList, MemorySSA &MSSA,
2328 BatchAAResults &AA, LoadInst *L) {
2329
2330 // Prefer a candidate that is closer to the load within the same block.
2331 auto UpdateChoice = [&](std::optional<ReachingMemVal> &Choice,
2332 AliasResult &AR, Instruction *Candidate) {
2333 if (!Choice) {
2334 if (AR == AliasResult::PartialAlias)
2335 Choice = ReachingMemVal::getClobber(Addr: Loc.Ptr, Inst: Candidate, Offset: AR.getOffset());
2336 else
2337 Choice = ReachingMemVal::getDef(Addr: Loc.Ptr, Inst: Candidate);
2338 return;
2339 }
2340 if (!MSSA.locallyDominates(A: MSSA.getMemoryAccess(I: Choice->Inst),
2341 B: MSSA.getMemoryAccess(I: Candidate)))
2342 return;
2343
2344 if (AR == AliasResult::PartialAlias) {
2345 Choice->Kind = DepKind::Clobber;
2346 Choice->Offset = AR.getOffset();
2347 } else {
2348 Choice->Kind = DepKind::Def;
2349 Choice->Offset = -1;
2350 }
2351
2352 Choice->Inst = Candidate;
2353 Choice->Block = Candidate->getParent();
2354 };
2355
2356 std::optional<ReachingMemVal> ReachingVal;
2357 for (MemoryAccess *MA : ClobbersList) {
2358 unsigned Scanned = 0;
2359 for (User *U : MA->users()) {
2360 if (++Scanned >= ScanUsersLimit)
2361 return ReachingMemVal::getUnknown(BB, Addr: Loc.Ptr);
2362
2363 auto *UseOrDef = dyn_cast<MemoryUseOrDef>(Val: U);
2364 if (!UseOrDef || UseOrDef->getBlock() != BB)
2365 continue;
2366
2367 Instruction *MemI = UseOrDef->getMemoryInst();
2368 if (MemI == L ||
2369 (L && !MSSA.locallyDominates(A: UseOrDef, B: MSSA.getMemoryAccess(I: L))))
2370 continue;
2371
2372 if (auto MaybeLoc = maybeLoadStoreLocation(I: MemI, AllowStores: IsInvariantLoad, TLI)) {
2373 AliasResult AR = AA.alias(LocA: *MaybeLoc, LocB: Loc);
2374 // If the locations do not certainly alias, we cannot possibly infer the
2375 // following load loads the same value.
2376 if (AR == AliasResult::NoAlias || AR == AliasResult::MayAlias)
2377 continue;
2378
2379 // Locations partially overlap, but neither is a subset of the other, or
2380 // the second location is before the first.
2381 if (AR == AliasResult::PartialAlias &&
2382 (!AR.hasOffset() || AR.getOffset() < 0))
2383 continue;
2384
2385 // Found candidate, the new load memory location and the given location
2386 // must alias: precise overlap, or subset with non-negative offset.
2387 UpdateChoice(ReachingVal, AR, MemI);
2388 }
2389 }
2390 if (ReachingVal)
2391 break;
2392 }
2393
2394 return ReachingVal;
2395}
2396
2397/// Check if a given MemoryAccess (usually a MemoryDef) actually modifies a
2398/// given location. Returns a ReachingMemVal describing the dependency.
2399std::optional<GVNPass::ReachingMemVal> GVNPass::accessMayModifyLocation(
2400 MemoryAccess *ClobberMA, const MemoryLocation &Loc, bool IsInvariantLoad,
2401 BasicBlock *BB, MemorySSA &MSSA, BatchAAResults &AA) {
2402 assert(ClobberMA->getBlock() == BB);
2403
2404 // If the clobbering access is the entry memory state, we cannot say anything
2405 // about the content of the memory, except when we are accessing a local
2406 // object, which can be turned later into producing `undef`.
2407 if (MSSA.isLiveOnEntryDef(MA: ClobberMA)) {
2408 if (auto *Alloc = dyn_cast<AllocaInst>(Val: getUnderlyingObject(V: Loc.Ptr)))
2409 if (Alloc->getParent() == BB)
2410 return ReachingMemVal::getDef(Addr: Loc.Ptr, Inst: const_cast<AllocaInst *>(Alloc));
2411 return ReachingMemVal::getUnknown(BB, Addr: Loc.Ptr);
2412 }
2413
2414 // Loads from "constant" memory can't be clobbered.
2415 if (IsInvariantLoad || AA.pointsToConstantMemory(Loc))
2416 return std::nullopt;
2417
2418 auto GetOrdering = [](const Instruction *I) {
2419 if (auto *L = dyn_cast<LoadInst>(Val: I))
2420 return L->getOrdering();
2421 return cast<StoreInst>(Val: I)->getOrdering();
2422 };
2423 Instruction *ClobberI = cast<MemoryDef>(Val: ClobberMA)->getMemoryInst();
2424
2425 // Check if the clobbering access is a load or a store that we can reuse.
2426 if (auto MaybeLoc = maybeLoadStoreLocation(I: ClobberI, AllowStores: true, TLI)) {
2427 AliasResult AR = AA.alias(LocA: *MaybeLoc, LocB: Loc);
2428 if (AR == AliasResult::MustAlias)
2429 return ReachingMemVal::getDef(Addr: Loc.Ptr, Inst: ClobberI);
2430
2431 if (AR == AliasResult::NoAlias) {
2432 // If the locations do not alias we may still be able to skip over the
2433 // clobbering instruction, even if it is atomic.
2434 // The original load is either non-atomic or unordered. We can reorder
2435 // these across non-atomic, unordered or monotonic loads or across any
2436 // store.
2437 if (!ClobberI->isAtomic() ||
2438 !isStrongerThan(AO: GetOrdering(ClobberI), Other: AtomicOrdering::Monotonic) ||
2439 isa<StoreInst>(Val: ClobberI))
2440 return std::nullopt;
2441 return ReachingMemVal::getClobber(Addr: Loc.Ptr, Inst: ClobberI);
2442 }
2443
2444 // Skip over volatile loads (the original load is non-volatile, non-atomic).
2445 if (!ClobberI->isAtomic() && isa<LoadInst>(Val: ClobberI))
2446 return std::nullopt;
2447
2448 if (AR == AliasResult::MayAlias ||
2449 (AR == AliasResult::PartialAlias &&
2450 (!AR.hasOffset() || AR.getOffset() < 0)))
2451 return ReachingMemVal::getClobber(Addr: Loc.Ptr, Inst: ClobberI);
2452
2453 // The only option left is a store of the superset of the required bits.
2454 assert(AR == AliasResult::PartialAlias && AR.hasOffset() &&
2455 AR.getOffset() > 0 &&
2456 "Must be the superset/partial overlap case with positive offset");
2457 return ReachingMemVal::getClobber(Addr: Loc.Ptr, Inst: ClobberI, Offset: AR.getOffset());
2458 }
2459
2460 if (auto *II = dyn_cast<IntrinsicInst>(Val: ClobberI)) {
2461 if (isa<DbgInfoIntrinsic>(Val: II))
2462 return std::nullopt;
2463 if (II->getIntrinsicID() == Intrinsic::lifetime_start) {
2464 MemoryLocation IIObjLoc = MemoryLocation::getForArgument(Call: II, ArgIdx: 0, TLI);
2465 if (AA.isMustAlias(LocA: IIObjLoc, LocB: Loc))
2466 return ReachingMemVal::getDef(Addr: Loc.Ptr, Inst: ClobberI);
2467 return std::nullopt;
2468 }
2469 }
2470
2471 // If we are at a malloc-like function call, we can turn the load into `undef`
2472 // or zero.
2473 if (isNoAliasCall(V: ClobberI)) {
2474 const Value *Obj = getUnderlyingObject(V: Loc.Ptr);
2475 if (Obj == ClobberI || AA.isMustAlias(V1: ClobberI, V2: Loc.Ptr))
2476 return ReachingMemVal::getDef(Addr: Loc.Ptr, Inst: ClobberI);
2477 }
2478
2479 // Can reorder loads across a release fence.
2480 if (auto *FI = dyn_cast<FenceInst>(Val: ClobberI))
2481 if (FI->getOrdering() == AtomicOrdering::Release)
2482 return std::nullopt;
2483
2484 // See if the clobber instruction (e.g., a generic call) may modify the
2485 // location.
2486 ModRefInfo MR = AA.getModRefInfo(I: ClobberI, OptLoc: Loc);
2487 // If may modify the location, analyze deeper, to exclude accesses to
2488 // non-escaping local allocations.
2489 if (MR == ModRefInfo::NoModRef || MR == ModRefInfo::Ref)
2490 return std::nullopt;
2491
2492 // Conservatively assume the clobbering memory access may overwrite the
2493 // location.
2494 return ReachingMemVal::getClobber(Addr: Loc.Ptr, Inst: ClobberI);
2495}
2496
2497/// Collect the predecessors of block, while doing phi-translation of the memory
2498/// address and the memory clobber. Return false if the block should be marked
2499/// as clobbering the memory location in an unknown way.
2500bool GVNPass::collectPredecessors(BasicBlock *BB, const PHITransAddr &Addr,
2501 MemoryAccess *ClobberMA,
2502 DependencyBlockSet &Blocks,
2503 SmallVectorImpl<BasicBlock *> &Worklist) {
2504 if (Addr.needsPHITranslationFromBlock(BB) &&
2505 !Addr.isPotentiallyPHITranslatable())
2506 return false;
2507
2508 auto *MPhi =
2509 ClobberMA->getBlock() == BB ? dyn_cast<MemoryPhi>(Val: ClobberMA) : nullptr;
2510 SmallVector<std::pair<BasicBlock *, DependencyBlockInfo>, 8> Preds;
2511 for (BasicBlock *Pred : predecessors(BB)) {
2512 // Skip unreachable predecessors.
2513 if (!DT->isReachableFromEntry(A: Pred))
2514 continue;
2515
2516 // Skip already visited predecessors.
2517 if (llvm::any_of(Range&: Preds, P: [Pred](const auto &P) { return P.first == Pred; }))
2518 continue;
2519
2520 PHITransAddr TransAddr = Addr;
2521 if (TransAddr.needsPHITranslationFromBlock(BB))
2522 TransAddr.translateValue(CurBB: BB, PredBB: Pred, DT, MustDominate: false);
2523
2524 auto It = Blocks.find(Val: Pred);
2525 if (It != Blocks.end()) {
2526 // If we reach a visited block with a different address, set the
2527 // current block as clobbering the memory location in an unknown way
2528 // (by returning false).
2529 if (It->second.Addr.getAddr() != TransAddr.getAddr())
2530 return false;
2531 // Otherwise, just stop the traversal.
2532 continue;
2533 }
2534
2535 Preds.emplace_back(
2536 Args&: Pred, Args: DependencyBlockInfo(TransAddr,
2537 MPhi ? MPhi->getIncomingValueForBlock(BB: Pred)
2538 : ClobberMA));
2539 }
2540
2541 // We collected the predecessors and stored them in Preds. Now, populate the
2542 // worklist with the predecessors found, and cache the eventual translated
2543 // address for each block.
2544 for (auto &P : Preds) {
2545 [[maybe_unused]] auto It =
2546 Blocks.try_emplace(Key: P.first, Args: std::move(P.second)).first;
2547 Worklist.push_back(Elt: P.first);
2548 }
2549
2550 return true;
2551}
2552
2553/// Build a list of MemoryAccesses whose users could potentially alias the
2554/// memory location being queried. Starts from StartInfo's initial clobber,
2555/// walk the use-def chain to the final clobber. If the chain extends beyond
2556/// `BB`, continue into that block but only if it is in the previously collected
2557/// set.
2558void GVNPass::collectClobberList(SmallVectorImpl<MemoryAccess *> &Clobbers,
2559 BasicBlock *BB,
2560 const DependencyBlockInfo &StartInfo,
2561 const DependencyBlockSet &Blocks,
2562 MemorySSA &MSSA) {
2563 MemoryAccess *MA = StartInfo.InitialClobberMA;
2564 MemoryAccess *LastMA = StartInfo.ClobberMA;
2565
2566 for (;;) {
2567 while (MA != LastMA) {
2568 Clobbers.push_back(Elt: MA);
2569 MA = cast<MemoryUseOrDef>(Val: MA)->getDefiningAccess();
2570 }
2571 Clobbers.push_back(Elt: MA);
2572
2573 if (MSSA.isLiveOnEntryDef(MA) ||
2574 (MA->getBlock() == BB && !isa<MemoryPhi>(Val: MA)))
2575 break;
2576
2577 // If the final clobber in the current block is a MemoryPhi, go to the
2578 // immediate dominator; otherwise, just get to the block containing the
2579 // final clobber.
2580 if (MA->getBlock() == BB)
2581 BB = DT->getNode(BB)->getIDom()->getBlock();
2582 else
2583 BB = MA->getBlock();
2584
2585 auto It = Blocks.find(Val: BB);
2586 if (It == Blocks.end())
2587 break;
2588
2589 MA = It->second.InitialClobberMA;
2590 LastMA = It->second.ClobberMA;
2591 if (MA == Clobbers.back())
2592 Clobbers.pop_back();
2593 }
2594}
2595
2596/// Entrypoint for the MemorySSA-based redundant load elimination algorithm.
2597/// Given as input a load instruction, the function computes the set of reaching
2598/// memory values, one per predecessor path, that AnalyzeLoadAvailability can
2599/// later use to establish whether the load may be eliminated. A reaching value
2600/// may be of the following descriptor kind:
2601/// * Def: a precise instruction that produces the exact bits the load would
2602/// read (e.g., an equivalent load or a MustAlias store);
2603/// * Clobber: a write that clobbers a superset of the bits the load would read
2604/// (e.g., a memset over a larger region);
2605/// * Other: we know which block defines the memory location in some way, but
2606/// could not identify a precise instruction (e.g., memory already live at
2607/// function entry).
2608bool GVNPass::findReachingValuesForLoad(LoadInst *L,
2609 SmallVectorImpl<ReachingMemVal> &Values,
2610 MemorySSA &MSSA, AAResults &AAR) {
2611 EarliestEscapeAnalysis EA(*DT, LI);
2612 BatchAAResults AA(AAR, &EA);
2613 BasicBlock *StartBlock = L->getParent();
2614 bool IsInvariantLoad = L->hasMetadata(KindID: LLVMContext::MD_invariant_load);
2615 // TODO: Simplify later work by just getClobberingMemoryAccess().
2616 MemoryAccess *ClobberMA = MSSA.getMemoryAccess(I: L)->getDefiningAccess();
2617 const MemoryLocation Loc = MemoryLocation::get(LI: L);
2618
2619 // Fast path for load tagged with !invariant.group.
2620 if (L->hasMetadata(KindID: LLVMContext::MD_invariant_group)) {
2621 if (Instruction *G = findInvariantGroupValue(L, DT&: *DT)) {
2622 Values.emplace_back(
2623 Args: ReachingMemVal::getDef(Addr: getLoadStorePointerOperand(V: G), Inst: G));
2624 return true;
2625 }
2626 }
2627
2628 // Phase 1. First off, look for a local dependency to avoid having to
2629 // disambiguate between before the load and after the load of the starting
2630 // block (as the load may be visited from a backedge).
2631 do {
2632 // Scan users of the clobbering memory access.
2633 if (auto RMV = scanMemoryAccessesUsers(
2634 Loc, IsInvariantLoad, BB: StartBlock,
2635 ClobbersList: SmallVector<MemoryAccess *, 1>{ClobberMA}, MSSA, AA, L)) {
2636 Values.emplace_back(Args&: *RMV);
2637 return true;
2638 }
2639
2640 // Exit from here, and proceed visiting predecessors if the clobbering
2641 // access is non-local or is a MemoryPhi.
2642 if (ClobberMA->getBlock() != StartBlock || isa<MemoryPhi>(Val: ClobberMA))
2643 break;
2644
2645 // Check if the clobber actually aliases the load location.
2646 if (auto RMV = accessMayModifyLocation(ClobberMA, Loc, IsInvariantLoad,
2647 BB: StartBlock, MSSA, AA)) {
2648 Values.emplace_back(Args&: *RMV);
2649 return true;
2650 }
2651
2652 // It may happen that the clobbering memory access does not actually
2653 // clobber our load location, transition to its defining memory access.
2654 ClobberMA = cast<MemoryUseOrDef>(Val: ClobberMA)->getDefiningAccess();
2655 } while (ClobberMA->getBlock() == StartBlock);
2656
2657 // Non-local speculations are not allowed under ASan.
2658 if (L->getFunction()->hasFnAttribute(Kind: Attribute::SanitizeAddress) ||
2659 L->getFunction()->hasFnAttribute(Kind: Attribute::SanitizeHWAddress))
2660 return false;
2661
2662 // Phase 2. Walk backwards through the CFG, collecting all the blocks that
2663 // contain an instruction that modifies the load memory location, or that lie
2664 // on a path between a clobbering block and our load. Start off by collecting
2665 // the predecessors of `StartBlock`. All the visited blocks are stored in a
2666 // the set `Blocks`. If possible, the memory address maintained for the block
2667 // visited does get phi-translated.
2668 DependencyBlockSet Blocks;
2669 SmallVector<BasicBlock *, 16> InitialWorklist;
2670 const DataLayout &DL = L->getModule()->getDataLayout();
2671 if (!collectPredecessors(BB: StartBlock,
2672 Addr: PHITransAddr(L->getPointerOperand(), DL, AC),
2673 ClobberMA, Blocks, Worklist&: InitialWorklist))
2674 return false;
2675
2676 // Do a bottom-up DFS.
2677 auto Worklist = InitialWorklist;
2678 while (!Worklist.empty()) {
2679 auto *BB = Worklist.pop_back_val();
2680 DependencyBlockInfo &Info = Blocks.find(Val: BB)->second;
2681
2682 // Phi-translation may have failed.
2683 if (!Info.Addr.getAddr())
2684 continue;
2685
2686 // If the clobbering memory access is in the current block and it indeed
2687 // clobbers our load location, record the dependency and do not visit the
2688 // predecessors of this block further, continue with the blocks in the
2689 // worklist.
2690 if (Info.ClobberMA->getBlock() == BB && !isa<MemoryPhi>(Val: Info.ClobberMA)) {
2691 if (auto RMV = accessMayModifyLocation(
2692 ClobberMA: Info.ClobberMA, Loc: Loc.getWithNewPtr(NewPtr: Info.Addr.getAddr()),
2693 IsInvariantLoad, BB, MSSA, AA)) {
2694 Info.MemVal = RMV;
2695 continue;
2696 }
2697 assert(!MSSA.isLiveOnEntryDef(Info.ClobberMA) &&
2698 "LiveOnEntry aliases everything");
2699
2700 // If, however, the clobbering memory access does not actually clobber
2701 // our load location, transition to its defining memory access, but
2702 // keep examining the same basic block.
2703 Info.ClobberMA =
2704 cast<MemoryUseOrDef>(Val: Info.ClobberMA)->getDefiningAccess();
2705 Worklist.emplace_back(Args&: BB);
2706 continue;
2707 }
2708
2709 // At this point we know the current block is "transparent", i.e. the memory
2710 // location is not modified when execution goes through this block.
2711 // Continue to its predecessors, unless a predecessor has already been
2712 // visited with a different address. We currently cannot represent such a
2713 // dependency.
2714 if (BB == StartBlock && Info.Addr.getAddr() != L->getPointerOperand()) {
2715 Info.ForceUnknown = true;
2716 continue;
2717 }
2718 if (BB != StartBlock &&
2719 !collectPredecessors(BB, Addr: Info.Addr, ClobberMA: Info.ClobberMA, Blocks, Worklist))
2720 Info.ForceUnknown = true;
2721 }
2722
2723 // Phase 3. We have collected all the blocks that either write a value to the
2724 // memory location of the load, or there exists a path to the load, along
2725 // which the memory location is not modified. Perform a second DFS to find
2726 // load-to-load dependencies; namely, look at the dominating memory reads,
2727 // that alias our load. These are the MemoryUses that are users of the
2728 // MemoryDefs we previously identified. If no memory read is encountered,
2729 // either confirm the clobbering write found before or set to unknown.
2730 Worklist = InitialWorklist;
2731 for (BasicBlock *BB : Worklist) {
2732 DependencyBlockInfo &Info = Blocks.find(Val: BB)->second;
2733 Info.Visited = true;
2734 }
2735
2736 SmallVector<MemoryAccess *> Clobbers;
2737 while (!Worklist.empty()) {
2738 auto *BB = Worklist.pop_back_val();
2739 DependencyBlockInfo &Info = Blocks.find(Val: BB)->second;
2740
2741 // If phi-translation failed, assume the memory location is modified in
2742 // unknown way.
2743 if (!Info.Addr.getAddr()) {
2744 Values.push_back(Elt: ReachingMemVal::getUnknown(BB, Addr: nullptr));
2745 continue;
2746 }
2747
2748 Clobbers.clear();
2749 collectClobberList(Clobbers, BB, StartInfo: Info, Blocks, MSSA);
2750 if (auto RMV =
2751 scanMemoryAccessesUsers(Loc: Loc.getWithNewPtr(NewPtr: Info.Addr.getAddr()),
2752 IsInvariantLoad, BB, ClobbersList: Clobbers, MSSA, AA)) {
2753 Values.push_back(Elt: *RMV);
2754 continue;
2755 }
2756
2757 // If no reusable memory use was found, and the current block is not
2758 // transparent, use the already established memory def.
2759 if (Info.MemVal) {
2760 Values.push_back(Elt: *Info.MemVal);
2761 continue;
2762 }
2763
2764 if (Info.ForceUnknown) {
2765 Values.push_back(Elt: ReachingMemVal::getUnknown(BB, Addr: Info.Addr.getAddr()));
2766 continue;
2767 }
2768
2769 // If the current block is transparent, continue to its predecessors.
2770 for (BasicBlock *Pred : predecessors(BB)) {
2771 auto It = Blocks.find(Val: Pred);
2772 if (It == Blocks.end())
2773 continue;
2774 DependencyBlockInfo &PredInfo = It->second;
2775 if (PredInfo.Visited)
2776 continue;
2777 PredInfo.Visited = true;
2778 Worklist.push_back(Elt: Pred);
2779 }
2780 }
2781
2782 return true;
2783}
2784
2785/// Attempt to eliminate a load, first by eliminating it
2786/// locally, and then attempting non-local elimination if that fails.
2787bool GVNPass::processLoad(LoadInst *L) {
2788 if (!MD && !isMemorySSAEnabled())
2789 return false;
2790
2791 // This code hasn't been audited for ordered or volatile memory access.
2792 if (!L->isUnordered())
2793 return false;
2794
2795 if (L->getType()->isTokenLikeTy())
2796 return false;
2797
2798 if (L->use_empty()) {
2799 salvageAndRemoveInstruction(I: L);
2800 return true;
2801 }
2802
2803 ReachingMemVal MemVal = ReachingMemVal::getUnknown(BB: nullptr, Addr: nullptr);
2804 if (!isMemorySSAEnabled()) {
2805 // ... to a pointer that has been loaded from before...
2806 MemDepResult Dep = MD->getDependency(QueryInst: L);
2807
2808 // If it is defined in another block, try harder.
2809 if (Dep.isNonLocal())
2810 return processNonLocalLoad(Load: L);
2811
2812 // Only handle the local case below.
2813 if (Dep.isDef())
2814 MemVal = ReachingMemVal::getDef(Addr: L->getPointerOperand(), Inst: Dep.getInst());
2815 else if (Dep.isClobber())
2816 MemVal =
2817 ReachingMemVal::getClobber(Addr: L->getPointerOperand(), Inst: Dep.getInst());
2818 } else {
2819 SmallVector<ReachingMemVal, 8> MemVals;
2820 if (!findReachingValuesForLoad(L, Values&: MemVals, MSSA&: *MSSAU->getMemorySSA(), AAR&: *AA))
2821 return false; // Too many dependencies.
2822 assert(MemVals.size() && "Expected at least an unknown value");
2823 if (MemVals.size() > 1 || MemVals[0].Block != L->getParent())
2824 return processNonLocalLoad(Load: L, Deps&: MemVals);
2825
2826 MemVal = MemVals[0];
2827 }
2828
2829 if (MemVal.Kind == DepKind::Other) {
2830 // This might be a NonFuncLocal or an Unknown.
2831 LLVM_DEBUG(
2832 // fast print dep, using operator<< on instruction is too slow.
2833 dbgs() << "GVN: load "; L->printAsOperand(dbgs());
2834 dbgs() << " has unknown dependence\n";);
2835 return false;
2836 }
2837
2838 auto AV = AnalyzeLoadAvailability(Load: L, Dep: MemVal, Address: L->getPointerOperand());
2839 if (!AV)
2840 return false;
2841
2842 Value *AvailableValue = AV->MaterializeAdjustedValue(Load: L, InsertPt: L);
2843
2844 // MaterializeAdjustedValue is responsible for combining metadata.
2845 ICF->removeUsersOf(Inst: L);
2846 L->replaceAllUsesWith(V: AvailableValue);
2847 if (MSSAU)
2848 MSSAU->removeMemoryAccess(I: L);
2849 ++NumGVNLoad;
2850 reportLoadElim(Load: L, AvailableValue, ORE);
2851 salvageAndRemoveInstruction(I: L);
2852 // Tell MDA to reexamine the reused pointer since we might have more
2853 // information after forwarding it.
2854 if (MD && AvailableValue->getType()->isPtrOrPtrVectorTy())
2855 MD->invalidateCachedPointerInfo(Ptr: AvailableValue);
2856 return true;
2857}
2858
2859// Attempt to process masked loads which have loaded from
2860// masked stores with the same mask
2861bool GVNPass::processMaskedLoad(IntrinsicInst *I) {
2862 if (!MD)
2863 return false;
2864 MemDepResult Dep = MD->getDependency(QueryInst: I);
2865 Instruction *DepInst = Dep.getInst();
2866 if (!DepInst || !Dep.isLocal() || !Dep.isDef())
2867 return false;
2868
2869 Value *Mask = I->getOperand(i_nocapture: 1);
2870 Value *Passthrough = I->getOperand(i_nocapture: 2);
2871 Value *StoreVal;
2872 if (!match(V: DepInst,
2873 P: m_MaskedStore(Op0: m_Value(V&: StoreVal), Op1: m_Value(), Op2: m_Specific(V: Mask))) ||
2874 StoreVal->getType() != I->getType())
2875 return false;
2876
2877 // Remove the load but generate a select for the passthrough
2878 Value *OpToForward = llvm::SelectInst::Create(C: Mask, S1: StoreVal, S2: Passthrough, NameStr: "",
2879 InsertBefore: I->getIterator());
2880
2881 ICF->removeUsersOf(Inst: I);
2882 I->replaceAllUsesWith(V: OpToForward);
2883 salvageAndRemoveInstruction(I);
2884 ++NumGVNLoad;
2885 return true;
2886}
2887
2888/// Return a pair the first field showing the value number of \p Exp and the
2889/// second field showing whether it is a value number newly created.
2890std::pair<uint32_t, bool>
2891GVNPass::ValueTable::assignExpNewValueNum(Expression &Exp) {
2892 uint32_t &E = ExpressionNumbering[Exp];
2893 bool CreateNewValNum = !E;
2894 if (CreateNewValNum) {
2895 Expressions.push_back(x: Exp);
2896 if (ExprIdx.size() < NextValueNumber + 1)
2897 ExprIdx.resize(new_size: NextValueNumber * 2);
2898 E = NextValueNumber;
2899 ExprIdx[NextValueNumber++] = NextExprNumber++;
2900 }
2901 return {E, CreateNewValNum};
2902}
2903
2904/// Return whether all the values related with the same \p num are
2905/// defined in \p BB.
2906bool GVNPass::ValueTable::areAllValsInBB(uint32_t Num, const BasicBlock *BB,
2907 GVNPass &GVN) {
2908 return all_of(
2909 Range: GVN.LeaderTable.getLeaders(N: Num),
2910 P: [=](const LeaderMap::LeaderTableEntry &L) { return L.BB == BB; });
2911}
2912
2913/// Wrap phiTranslateImpl to provide caching functionality.
2914uint32_t GVNPass::ValueTable::phiTranslate(const BasicBlock *Pred,
2915 const BasicBlock *PhiBlock,
2916 uint32_t Num, GVNPass &GVN) {
2917 auto FindRes = PhiTranslateTable.find(Val: {Num, Pred});
2918 if (FindRes != PhiTranslateTable.end())
2919 return FindRes->second;
2920 uint32_t NewNum = phiTranslateImpl(BB: Pred, PhiBlock, Num, GVN);
2921 PhiTranslateTable.insert(KV: {{Num, Pred}, NewNum});
2922 return NewNum;
2923}
2924
2925// Return true if the value number \p Num and NewNum have equal value.
2926// Return false if the result is unknown.
2927bool GVNPass::ValueTable::areCallValsEqual(uint32_t Num, uint32_t NewNum,
2928 const BasicBlock *Pred,
2929 const BasicBlock *PhiBlock,
2930 GVNPass &GVN) {
2931 CallInst *Call = nullptr;
2932 auto Leaders = GVN.LeaderTable.getLeaders(N: Num);
2933 for (const auto &Entry : Leaders) {
2934 Call = dyn_cast<CallInst>(Val: &*Entry.Val);
2935 if (Call && Call->getParent() == PhiBlock)
2936 break;
2937 }
2938
2939 if (AA->doesNotAccessMemory(Call))
2940 return true;
2941
2942 if (!MD || !AA->onlyReadsMemory(Call))
2943 return false;
2944
2945 MemDepResult LocalDep = MD->getDependency(QueryInst: Call);
2946 if (!LocalDep.isNonLocal())
2947 return false;
2948
2949 const MemoryDependenceResults::NonLocalDepInfo &Deps =
2950 MD->getNonLocalCallDependency(QueryCall: Call);
2951
2952 // Check to see if the Call has no function local clobber.
2953 for (const NonLocalDepEntry &D : Deps) {
2954 if (D.getResult().isNonFuncLocal())
2955 return true;
2956 }
2957 return false;
2958}
2959
2960/// Translate value number \p Num using phis, so that it has the values of
2961/// the phis in BB.
2962uint32_t GVNPass::ValueTable::phiTranslateImpl(const BasicBlock *Pred,
2963 const BasicBlock *PhiBlock,
2964 uint32_t Num, GVNPass &GVN) {
2965 // See if we can refine the value number by looking at the PN incoming value
2966 // for the given predecessor.
2967 if (PHINode *PN = NumberingPhi[Num]) {
2968 if (PN->getParent() != PhiBlock)
2969 return Num;
2970 for (unsigned I = 0; I != PN->getNumIncomingValues(); ++I) {
2971 if (PN->getIncomingBlock(i: I) != Pred)
2972 continue;
2973 if (uint32_t TransVal = lookup(V: PN->getIncomingValue(i: I), Verify: false))
2974 return TransVal;
2975 }
2976 return Num;
2977 }
2978
2979 if (BasicBlock *BB = NumberingBB[Num]) {
2980 assert(MSSA && "NumberingBB is non-empty only when using MemorySSA");
2981 // Value numbers of basic blocks are used to represent memory state in
2982 // load/store instructions and read-only function calls when said state is
2983 // set by a MemoryPhi.
2984 if (BB != PhiBlock)
2985 return Num;
2986 MemoryPhi *MPhi = MSSA->getMemoryAccess(BB);
2987 for (unsigned i = 0, N = MPhi->getNumIncomingValues(); i != N; ++i) {
2988 if (MPhi->getIncomingBlock(I: i) != Pred)
2989 continue;
2990 MemoryAccess *MA = MPhi->getIncomingValue(I: i);
2991 if (auto *PredPhi = dyn_cast<MemoryPhi>(Val: MA))
2992 return lookupOrAdd(V: PredPhi->getBlock());
2993 if (MSSA->isLiveOnEntryDef(MA))
2994 return lookupOrAdd(V: &BB->getParent()->getEntryBlock());
2995 return lookupOrAdd(V: cast<MemoryUseOrDef>(Val: MA)->getMemoryInst());
2996 }
2997 llvm_unreachable(
2998 "CFG/MemorySSA mismatch: predecessor not found among incoming blocks");
2999 }
3000
3001 // If there is any value related with Num is defined in a BB other than
3002 // PhiBlock, it cannot depend on a phi in PhiBlock without going through
3003 // a backedge. We can do an early exit in that case to save compile time.
3004 if (!areAllValsInBB(Num, BB: PhiBlock, GVN))
3005 return Num;
3006
3007 if (Num >= ExprIdx.size() || ExprIdx[Num] == 0)
3008 return Num;
3009 Expression Exp = Expressions[ExprIdx[Num]];
3010
3011 for (unsigned I = 0; I < Exp.VarArgs.size(); I++) {
3012 // For InsertValue and ExtractValue, some varargs are index numbers
3013 // instead of value numbers. Those index numbers should not be
3014 // translated.
3015 if ((I > 1 && Exp.Opcode == Instruction::InsertValue) ||
3016 (I > 0 && Exp.Opcode == Instruction::ExtractValue) ||
3017 (I > 1 && Exp.Opcode == Instruction::ShuffleVector))
3018 continue;
3019 Exp.VarArgs[I] = phiTranslate(Pred, PhiBlock, Num: Exp.VarArgs[I], GVN);
3020 }
3021
3022 if (Exp.Commutative) {
3023 assert(Exp.VarArgs.size() >= 2 && "Unsupported commutative instruction!");
3024 if (Exp.VarArgs[0] > Exp.VarArgs[1]) {
3025 std::swap(a&: Exp.VarArgs[0], b&: Exp.VarArgs[1]);
3026 uint32_t Opcode = Exp.Opcode >> 8;
3027 if (Opcode == Instruction::ICmp || Opcode == Instruction::FCmp)
3028 Exp.Opcode = (Opcode << 8) |
3029 CmpInst::getSwappedPredicate(
3030 pred: static_cast<CmpInst::Predicate>(Exp.Opcode & 255));
3031 }
3032 }
3033
3034 if (uint32_t NewNum = ExpressionNumbering[Exp]) {
3035 if (Exp.Opcode == Instruction::Call && NewNum != Num)
3036 return areCallValsEqual(Num, NewNum, Pred, PhiBlock, GVN) ? NewNum : Num;
3037 return NewNum;
3038 }
3039 return Num;
3040}
3041
3042/// Erase stale entry from phiTranslate cache so phiTranslate can be computed
3043/// again.
3044void GVNPass::ValueTable::eraseTranslateCacheEntry(
3045 uint32_t Num, const BasicBlock &CurrBlock) {
3046 for (const BasicBlock *Pred : predecessors(BB: &CurrBlock))
3047 PhiTranslateTable.erase(Val: {Num, Pred});
3048}
3049
3050// In order to find a leader for a given value number at a
3051// specific basic block, we first obtain the list of all Values for that number,
3052// and then scan the list to find one whose block dominates the block in
3053// question. This is fast because dominator tree queries consist of only
3054// a few comparisons of DFS numbers.
3055Value *GVNPass::findLeader(const BasicBlock *BB, uint32_t Num) {
3056 auto Leaders = LeaderTable.getLeaders(N: Num);
3057 if (Leaders.empty())
3058 return nullptr;
3059
3060 Value *Val = nullptr;
3061 for (const auto &Entry : Leaders) {
3062 if (DT->dominates(A: Entry.BB, B: BB)) {
3063 Val = Entry.Val;
3064 if (isa<Constant>(Val))
3065 return Val;
3066 }
3067 }
3068
3069 return Val;
3070}
3071
3072/// There is an edge from 'Src' to 'Dst'. Return
3073/// true if every path from the entry block to 'Dst' passes via this edge. In
3074/// particular 'Dst' must not be reachable via another edge from 'Src'.
3075static bool isOnlyReachableViaThisEdge(const BasicBlockEdge &E,
3076 DominatorTree *DT) {
3077 // While in theory it is interesting to consider the case in which Dst has
3078 // more than one predecessor, because Dst might be part of a loop which is
3079 // only reachable from Src, in practice it is pointless since at the time
3080 // GVN runs all such loops have preheaders, which means that Dst will have
3081 // been changed to have only one predecessor, namely Src.
3082 const BasicBlock *Pred = E.getEnd()->getSinglePredecessor();
3083 assert((!Pred || Pred == E.getStart()) &&
3084 "No edge between these basic blocks!");
3085 return Pred != nullptr;
3086}
3087
3088void GVNPass::assignBlockRPONumber(Function &F) {
3089 BlockRPONumber.clear();
3090 uint32_t NextBlockNumber = 1;
3091 ReversePostOrderTraversal<Function *> RPOT(&F);
3092 for (BasicBlock *BB : RPOT)
3093 BlockRPONumber[BB] = NextBlockNumber++;
3094 InvalidBlockRPONumbers = false;
3095}
3096
3097/// The given values are known to be equal in every use
3098/// dominated by 'Root'. Exploit this, for example by replacing 'LHS' with
3099/// 'RHS' everywhere in the scope. Returns whether a change was made.
3100/// The Root may either be a basic block edge (for conditions) or an
3101/// instruction (for assumes).
3102bool GVNPass::propagateEquality(
3103 Value *LHS, Value *RHS,
3104 const std::variant<BasicBlockEdge, Instruction *> &Root) {
3105 SmallVector<std::pair<Value*, Value*>, 4> Worklist;
3106 Worklist.push_back(Elt: std::make_pair(x&: LHS, y&: RHS));
3107 bool Changed = false;
3108 SmallVector<const BasicBlock *> DominatedBlocks;
3109 if (const BasicBlockEdge *Edge = std::get_if<BasicBlockEdge>(ptr: &Root)) {
3110 // For speed, compute a conservative fast approximation to
3111 // DT->dominates(Root, Root.getEnd());
3112 if (isOnlyReachableViaThisEdge(E: *Edge, DT))
3113 DominatedBlocks.push_back(Elt: Edge->getEnd());
3114 } else {
3115 Instruction *I = std::get<Instruction *>(v: Root);
3116 for (const auto *Node : DT->getNode(BB: I->getParent())->children())
3117 DominatedBlocks.push_back(Elt: Node->getBlock());
3118 }
3119
3120 while (!Worklist.empty()) {
3121 std::pair<Value*, Value*> Item = Worklist.pop_back_val();
3122 LHS = Item.first; RHS = Item.second;
3123
3124 if (LHS == RHS)
3125 continue;
3126 assert(LHS->getType() == RHS->getType() && "Equality but unequal types!");
3127
3128 // Don't try to propagate equalities between constants.
3129 if (isa<Constant>(Val: LHS) && isa<Constant>(Val: RHS))
3130 continue;
3131
3132 // Prefer a constant on the right-hand side, or an Argument if no constants.
3133 if (isa<Constant>(Val: LHS) || (isa<Argument>(Val: LHS) && !isa<Constant>(Val: RHS)))
3134 std::swap(a&: LHS, b&: RHS);
3135 assert((isa<Argument>(LHS) || isa<Instruction>(LHS)) && "Unexpected value!");
3136 const DataLayout &DL =
3137 isa<Argument>(Val: LHS)
3138 ? cast<Argument>(Val: LHS)->getParent()->getDataLayout()
3139 : cast<Instruction>(Val: LHS)->getDataLayout();
3140
3141 // If there is no obvious reason to prefer the left-hand side over the
3142 // right-hand side, ensure the longest lived term is on the right-hand side,
3143 // so the shortest lived term will be replaced by the longest lived.
3144 // This tends to expose more simplifications.
3145 uint32_t LVN = VN.lookupOrAdd(V: LHS);
3146 if ((isa<Argument>(Val: LHS) && isa<Argument>(Val: RHS)) ||
3147 (isa<Instruction>(Val: LHS) && isa<Instruction>(Val: RHS))) {
3148 // Move the 'oldest' value to the right-hand side, using the value number
3149 // as a proxy for age.
3150 uint32_t RVN = VN.lookupOrAdd(V: RHS);
3151 if (LVN < RVN) {
3152 std::swap(a&: LHS, b&: RHS);
3153 LVN = RVN;
3154 }
3155 }
3156
3157 // If value numbering later sees that an instruction in the scope is equal
3158 // to 'LHS' then ensure it will be turned into 'RHS'. In order to preserve
3159 // the invariant that instructions only occur in the leader table for their
3160 // own value number (this is used by removeFromLeaderTable), do not do this
3161 // if RHS is an instruction (if an instruction in the scope is morphed into
3162 // LHS then it will be turned into RHS by the next GVN iteration anyway, so
3163 // using the leader table is about compiling faster, not optimizing better).
3164 // The leader table only tracks basic blocks, not edges. Only add to if we
3165 // have the simple case where the edge dominates the end.
3166 if (!isa<Instruction>(Val: RHS) && canReplacePointersIfEqual(From: LHS, To: RHS, DL))
3167 for (const BasicBlock *BB : DominatedBlocks)
3168 LeaderTable.insert(N: LVN, V: RHS, BB);
3169
3170 // Replace all occurrences of 'LHS' with 'RHS' everywhere in the scope. As
3171 // LHS always has at least one use that is not dominated by Root, this will
3172 // never do anything if LHS has only one use.
3173 if (!LHS->hasOneUse()) {
3174 // Create a callback that captures the DL.
3175 auto CanReplacePointersCallBack = [&DL](const Use &U, const Value *To) {
3176 return canReplacePointersInUseIfEqual(U, To, DL);
3177 };
3178 unsigned NumReplacements;
3179 if (const BasicBlockEdge *Edge = std::get_if<BasicBlockEdge>(ptr: &Root))
3180 NumReplacements = replaceDominatedUsesWithIf(
3181 From: LHS, To: RHS, DT&: *DT, Edge: *Edge, ShouldReplace: CanReplacePointersCallBack);
3182 else
3183 NumReplacements = replaceDominatedUsesWithIf(
3184 From: LHS, To: RHS, DT&: *DT, I: std::get<Instruction *>(v: Root),
3185 ShouldReplace: CanReplacePointersCallBack);
3186
3187 if (NumReplacements > 0) {
3188 Changed = true;
3189 NumGVNEqProp += NumReplacements;
3190 // Cached information for anything that uses LHS will be invalid.
3191 if (MD)
3192 MD->invalidateCachedPointerInfo(Ptr: LHS);
3193 }
3194 }
3195
3196 // Now try to deduce additional equalities from this one. For example, if
3197 // the known equality was "(A != B)" == "false" then it follows that A and B
3198 // are equal in the scope. Only boolean equalities with an explicit true or
3199 // false RHS are currently supported.
3200 if (!RHS->getType()->isIntegerTy(BitWidth: 1))
3201 // Not a boolean equality - bail out.
3202 continue;
3203 ConstantInt *CI = dyn_cast<ConstantInt>(Val: RHS);
3204 if (!CI)
3205 // RHS neither 'true' nor 'false' - bail out.
3206 continue;
3207 // Whether RHS equals 'true'. Otherwise it equals 'false'.
3208 bool IsKnownTrue = CI->isMinusOne();
3209 bool IsKnownFalse = !IsKnownTrue;
3210
3211 // If "A && B" is known true then both A and B are known true. If "A || B"
3212 // is known false then both A and B are known false.
3213 Value *A, *B;
3214 if ((IsKnownTrue && match(V: LHS, P: m_LogicalAnd(L: m_Value(V&: A), R: m_Value(V&: B)))) ||
3215 (IsKnownFalse && match(V: LHS, P: m_LogicalOr(L: m_Value(V&: A), R: m_Value(V&: B))))) {
3216 Worklist.push_back(Elt: std::make_pair(x&: A, y&: RHS));
3217 Worklist.push_back(Elt: std::make_pair(x&: B, y&: RHS));
3218 continue;
3219 }
3220
3221 // If we are propagating an equality like "(A == B)" == "true" then also
3222 // propagate the equality A == B. When propagating a comparison such as
3223 // "(A >= B)" == "true", replace all instances of "A < B" with "false".
3224 if (CmpInst *Cmp = dyn_cast<CmpInst>(Val: LHS)) {
3225 Value *Op0 = Cmp->getOperand(i_nocapture: 0), *Op1 = Cmp->getOperand(i_nocapture: 1);
3226
3227 // If "A == B" is known true, or "A != B" is known false, then replace
3228 // A with B everywhere in the scope. For floating point operations, we
3229 // have to be careful since equality does not always imply equivalance.
3230 if (Cmp->isEquivalence(Invert: IsKnownFalse))
3231 Worklist.push_back(Elt: std::make_pair(x&: Op0, y&: Op1));
3232
3233 // If "A >= B" is known true, replace "A < B" with false everywhere.
3234 CmpInst::Predicate NotPred = Cmp->getInversePredicate();
3235 Constant *NotVal = ConstantInt::get(Ty: Cmp->getType(), V: IsKnownFalse);
3236 // Since we don't have the instruction "A < B" immediately to hand, work
3237 // out the value number that it would have and use that to find an
3238 // appropriate instruction (if any).
3239 uint32_t NextNum = VN.getNextUnusedValueNumber();
3240 uint32_t Num = VN.lookupOrAddCmp(Opcode: Cmp->getOpcode(), Predicate: NotPred, LHS: Op0, RHS: Op1);
3241 // If the number we were assigned was brand new then there is no point in
3242 // looking for an instruction realizing it: there cannot be one!
3243 if (Num < NextNum) {
3244 for (const auto &Entry : LeaderTable.getLeaders(N: Num)) {
3245 // Only look at leaders that either dominate the start of the edge,
3246 // or are dominated by the end. This check is not necessary for
3247 // correctness, it only discards cases for which the following
3248 // use replacement will not work anyway.
3249 if (const BasicBlockEdge *Edge = std::get_if<BasicBlockEdge>(ptr: &Root)) {
3250 if (!DT->dominates(A: Entry.BB, B: Edge->getStart()) &&
3251 !DT->dominates(A: Edge->getEnd(), B: Entry.BB))
3252 continue;
3253 } else {
3254 auto *InstBB = std::get<Instruction *>(v: Root)->getParent();
3255 if (!DT->dominates(A: Entry.BB, B: InstBB) &&
3256 !DT->dominates(A: InstBB, B: Entry.BB))
3257 continue;
3258 }
3259
3260 Value *NotCmp = Entry.Val;
3261 if (NotCmp && isa<Instruction>(Val: NotCmp)) {
3262 unsigned NumReplacements;
3263 if (const BasicBlockEdge *Edge = std::get_if<BasicBlockEdge>(ptr: &Root))
3264 NumReplacements =
3265 replaceDominatedUsesWith(From: NotCmp, To: NotVal, DT&: *DT, Edge: *Edge);
3266 else
3267 NumReplacements = replaceDominatedUsesWith(
3268 From: NotCmp, To: NotVal, DT&: *DT, I: std::get<Instruction *>(v: Root));
3269 Changed |= NumReplacements > 0;
3270 NumGVNEqProp += NumReplacements;
3271 // Cached information for anything that uses NotCmp will be invalid.
3272 if (MD)
3273 MD->invalidateCachedPointerInfo(Ptr: NotCmp);
3274 }
3275 }
3276 }
3277 // Ensure that any instruction in scope that gets the "A < B" value number
3278 // is replaced with false.
3279 // The leader table only tracks basic blocks, not edges. Only add to if we
3280 // have the simple case where the edge dominates the end.
3281 for (const BasicBlock *BB : DominatedBlocks)
3282 LeaderTable.insert(N: Num, V: NotVal, BB);
3283
3284 continue;
3285 }
3286
3287 // Propagate equalities that results from truncation with no unsigned wrap
3288 // like (trunc nuw i64 %v to i1) == "true" or (trunc nuw i64 %v to i1) ==
3289 // "false"
3290 if (match(V: LHS, P: m_NUWTrunc(Op: m_Value(V&: A)))) {
3291 Worklist.emplace_back(Args&: A, Args: ConstantInt::get(Ty: A->getType(), V: IsKnownTrue));
3292 continue;
3293 }
3294
3295 if (match(V: LHS, P: m_Not(V: m_Value(V&: A)))) {
3296 Worklist.emplace_back(Args&: A, Args: ConstantInt::get(Ty: A->getType(), V: !IsKnownTrue));
3297 continue;
3298 }
3299 }
3300
3301 return Changed;
3302}
3303
3304/// When calculating availability, handle an instruction
3305/// by inserting it into the appropriate sets.
3306bool GVNPass::processInstruction(Instruction *I) {
3307 // If the instruction can be easily simplified then do so now in preference
3308 // to value numbering it. Value numbering often exposes redundancies, for
3309 // example if it determines that %y is equal to %x then the instruction
3310 // "%z = and i32 %x, %y" becomes "%z = and i32 %x, %x" which we now simplify.
3311 const DataLayout &DL = I->getDataLayout();
3312 if (Value *V = simplifyInstruction(I, Q: {DL, TLI, DT, AC})) {
3313 bool Changed = false;
3314 if (!I->use_empty()) {
3315 // Simplification can cause a special instruction to become not special.
3316 // For example, devirtualization to a willreturn function.
3317 ICF->removeUsersOf(Inst: I);
3318 I->replaceAllUsesWith(V);
3319 Changed = true;
3320 }
3321 if (isInstructionTriviallyDead(I, TLI)) {
3322 salvageAndRemoveInstruction(I);
3323 Changed = true;
3324 }
3325 if (Changed) {
3326 if (MD && V->getType()->isPtrOrPtrVectorTy())
3327 MD->invalidateCachedPointerInfo(Ptr: V);
3328 ++NumGVNSimpl;
3329 return true;
3330 }
3331 }
3332
3333 if (auto *Assume = dyn_cast<AssumeInst>(Val: I))
3334 return processAssumeIntrinsic(IntrinsicI: Assume);
3335
3336 if (LoadInst *Load = dyn_cast<LoadInst>(Val: I)) {
3337 if (processLoad(L: Load))
3338 return true;
3339
3340 unsigned Num = VN.lookupOrAdd(V: Load);
3341 LeaderTable.insert(N: Num, V: Load, BB: Load->getParent());
3342 return false;
3343 }
3344
3345 if (match(V: I, P: m_Intrinsic<Intrinsic::masked_load>()) &&
3346 processMaskedLoad(I: cast<IntrinsicInst>(Val: I)))
3347 return true;
3348
3349 // For conditional branches, we can perform simple conditional propagation on
3350 // the condition value itself.
3351 if (CondBrInst *BI = dyn_cast<CondBrInst>(Val: I)) {
3352 if (isa<Constant>(Val: BI->getCondition()))
3353 return processFoldableCondBr(BI);
3354
3355 Value *BranchCond = BI->getCondition();
3356 BasicBlock *TrueSucc = BI->getSuccessor(i: 0);
3357 BasicBlock *FalseSucc = BI->getSuccessor(i: 1);
3358 // Avoid multiple edges early.
3359 if (TrueSucc == FalseSucc)
3360 return false;
3361
3362 BasicBlock *Parent = BI->getParent();
3363 bool Changed = false;
3364
3365 Value *TrueVal = ConstantInt::getTrue(Context&: TrueSucc->getContext());
3366 BasicBlockEdge TrueE(Parent, TrueSucc);
3367 Changed |= propagateEquality(LHS: BranchCond, RHS: TrueVal, Root: TrueE);
3368
3369 Value *FalseVal = ConstantInt::getFalse(Context&: FalseSucc->getContext());
3370 BasicBlockEdge FalseE(Parent, FalseSucc);
3371 Changed |= propagateEquality(LHS: BranchCond, RHS: FalseVal, Root: FalseE);
3372
3373 return Changed;
3374 }
3375
3376 // For switches, propagate the case values into the case destinations.
3377 if (SwitchInst *SI = dyn_cast<SwitchInst>(Val: I)) {
3378 Value *SwitchCond = SI->getCondition();
3379 BasicBlock *Parent = SI->getParent();
3380 bool Changed = false;
3381
3382 // Remember how many outgoing edges there are to every successor.
3383 SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges;
3384 for (BasicBlock *Succ : successors(BB: Parent))
3385 ++SwitchEdges[Succ];
3386
3387 for (const auto &Case : SI->cases()) {
3388 BasicBlock *Dst = Case.getCaseSuccessor();
3389 // If there is only a single edge, propagate the case value into it.
3390 if (SwitchEdges.lookup(Val: Dst) == 1) {
3391 BasicBlockEdge E(Parent, Dst);
3392 Changed |= propagateEquality(LHS: SwitchCond, RHS: Case.getCaseValue(), Root: E);
3393 }
3394 }
3395 return Changed;
3396 }
3397
3398 // Instructions with void type don't return a value, so there's
3399 // no point in trying to find redundancies in them.
3400 if (I->getType()->isVoidTy())
3401 return false;
3402
3403 uint32_t NextNum = VN.getNextUnusedValueNumber();
3404 unsigned Num = VN.lookupOrAdd(V: I);
3405
3406 // Allocations are always uniquely numbered, so we can save time and memory
3407 // by fast failing them.
3408 if (isa<AllocaInst>(Val: I) || I->isTerminator() || isa<PHINode>(Val: I)) {
3409 LeaderTable.insert(N: Num, V: I, BB: I->getParent());
3410 return false;
3411 }
3412
3413 // A ptrtoaddr and a ptrtoint of the same pointer compute the same value when
3414 // the address width equals the pointer representation width.
3415 if (auto *PTA = dyn_cast<PtrToAddrInst>(Val: I)) {
3416 const DataLayout &DL = I->getDataLayout();
3417 unsigned AS = PTA->getPointerAddressSpace();
3418 if (DL.getAddressSizeInBits(AS) == DL.getPointerSizeInBits(AS) &&
3419 !DL.hasUnstableRepresentation(AddrSpace: AS)) {
3420 uint32_t PTINum =
3421 VN.lookupPtrToInt(Ptr: PTA->getPointerOperand(), Ty: PTA->getType());
3422 if (Value *PTI = findLeader(BB: I->getParent(), Num: PTINum)) {
3423 patchAndReplaceAllUsesWith(I, Repl: PTI);
3424 salvageAndRemoveInstruction(I);
3425 return true;
3426 }
3427 }
3428 }
3429
3430 // If the number we were assigned was a brand new VN, then we don't
3431 // need to do a lookup to see if the number already exists
3432 // somewhere in the domtree: it can't!
3433 if (Num >= NextNum) {
3434 LeaderTable.insert(N: Num, V: I, BB: I->getParent());
3435 return false;
3436 }
3437
3438 // Perform fast-path value-number based elimination of values inherited from
3439 // dominators.
3440 Value *Repl = findLeader(BB: I->getParent(), Num);
3441 if (!Repl) {
3442 // Failure, just remember this instance for future use.
3443 LeaderTable.insert(N: Num, V: I, BB: I->getParent());
3444 return false;
3445 }
3446
3447 if (Repl == I) {
3448 // If I was the result of a shortcut PRE, it might already be in the table
3449 // and the best replacement for itself. Nothing to do.
3450 return false;
3451 }
3452
3453 // Remove it!
3454 patchAndReplaceAllUsesWith(I, Repl);
3455 if (MD && Repl->getType()->isPtrOrPtrVectorTy())
3456 MD->invalidateCachedPointerInfo(Ptr: Repl);
3457 salvageAndRemoveInstruction(I);
3458 return true;
3459}
3460
3461/// runOnFunction - This is the main transformation entry point for a function.
3462bool GVNPass::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
3463 const TargetLibraryInfo &RunTLI, AAResults &RunAA,
3464 MemoryDependenceResults *RunMD, LoopInfo &LI,
3465 OptimizationRemarkEmitter *RunORE, MemorySSA *MSSA) {
3466 AC = &RunAC;
3467 DT = &RunDT;
3468 VN.setDomTree(DT);
3469 TLI = &RunTLI;
3470 AA = &RunAA;
3471 VN.setAliasAnalysis(&RunAA);
3472 MD = RunMD;
3473 ImplicitControlFlowTracking ImplicitCFT;
3474 ICF = &ImplicitCFT;
3475 this->LI = &LI;
3476 VN.setMemDep(M: MD);
3477 // Propagate the MSSA-enabled flag so the value-numbering paths in
3478 // lookupOrAddCall() and computeLoadStoreVN(), which depends on whether
3479 // IsMSSAEnabled is turned on.
3480 VN.setMemorySSA(M: MSSA, MSSAEnabled: isMemorySSAEnabled());
3481 ORE = RunORE;
3482 InvalidBlockRPONumbers = true;
3483 MemorySSAUpdater Updater(MSSA);
3484 MSSAU = MSSA ? &Updater : nullptr;
3485
3486 bool Changed = false;
3487 bool ShouldContinue = true;
3488
3489 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
3490 // Merge unconditional branches, allowing PRE to catch more
3491 // optimization opportunities.
3492 for (BasicBlock &BB : make_early_inc_range(Range&: F)) {
3493 bool RemovedBlock = MergeBlockIntoPredecessor(BB: &BB, DTU: &DTU, LI: &LI, MSSAU, MemDep: MD);
3494 if (RemovedBlock)
3495 ++NumGVNBlocks;
3496
3497 Changed |= RemovedBlock;
3498 }
3499 DTU.flush();
3500
3501 unsigned Iteration = 0;
3502 while (ShouldContinue) {
3503 LLVM_DEBUG(dbgs() << "GVN iteration: " << Iteration << "\n");
3504 (void) Iteration;
3505 ShouldContinue = iterateOnFunction(F);
3506 Changed |= ShouldContinue;
3507 ++Iteration;
3508 }
3509
3510 if (isScalarPREEnabled()) {
3511 // Fabricate val-num for dead-code in order to suppress assertion in
3512 // performPRE().
3513 assignValNumForDeadCode();
3514 bool PREChanged = true;
3515 while (PREChanged) {
3516 PREChanged = performPRE(F);
3517 Changed |= PREChanged;
3518 }
3519 }
3520
3521 // FIXME: Should perform GVN again after PRE does something. PRE can move
3522 // computations into blocks where they become fully redundant. Note that
3523 // we can't do this until PRE's critical edge splitting updates memdep.
3524 // Actually, when this happens, we should just fully integrate PRE into GVN.
3525
3526 cleanupGlobalSets();
3527 // Do not cleanup DeadBlocks in cleanupGlobalSets() as it's called for each
3528 // iteration.
3529 DeadBlocks.clear();
3530
3531 if (MSSA && VerifyMemorySSA)
3532 MSSA->verifyMemorySSA();
3533
3534 return Changed;
3535}
3536
3537bool GVNPass::processBlock(BasicBlock *BB) {
3538 if (DeadBlocks.count(key: BB))
3539 return false;
3540
3541 bool ChangedFunction = false;
3542
3543 // Since we may not have visited the input blocks of the phis, we can't
3544 // use our normal hash approach for phis. Instead, simply look for
3545 // obvious duplicates. The first pass of GVN will tend to create
3546 // identical phis, and the second or later passes can eliminate them.
3547 SmallPtrSet<PHINode *, 8> PHINodesToRemove;
3548 ChangedFunction |= EliminateDuplicatePHINodes(BB, ToRemove&: PHINodesToRemove);
3549 for (PHINode *PN : PHINodesToRemove) {
3550 removeInstruction(I: PN);
3551 }
3552 for (Instruction &Inst : make_early_inc_range(Range&: *BB))
3553 ChangedFunction |= processInstruction(I: &Inst);
3554 return ChangedFunction;
3555}
3556
3557// Instantiate an expression in a predecessor that lacked it.
3558bool GVNPass::performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
3559 BasicBlock *Curr, unsigned int ValNo) {
3560 // Because we are going top-down through the block, all value numbers
3561 // will be available in the predecessor by the time we need them. Any
3562 // that weren't originally present will have been instantiated earlier
3563 // in this loop.
3564 bool Success = true;
3565 for (unsigned I = 0, E = Instr->getNumOperands(); I != E; ++I) {
3566 Value *Op = Instr->getOperand(i: I);
3567 if (isa<Argument>(Val: Op) || isa<Constant>(Val: Op) || isa<GlobalValue>(Val: Op))
3568 continue;
3569 // This could be a newly inserted instruction, in which case, we won't
3570 // find a value number, and should give up before we hurt ourselves.
3571 // FIXME: Rewrite the infrastructure to let it easier to value number
3572 // and process newly inserted instructions.
3573 if (!VN.exists(V: Op)) {
3574 Success = false;
3575 break;
3576 }
3577 uint32_t TValNo =
3578 VN.phiTranslate(Pred, PhiBlock: Curr, Num: VN.lookup(V: Op), GVN&: *this);
3579 if (Value *V = findLeader(BB: Pred, Num: TValNo)) {
3580 Instr->setOperand(i: I, Val: V);
3581 } else {
3582 Success = false;
3583 break;
3584 }
3585 }
3586
3587 // Fail out if we encounter an operand that is not available in
3588 // the PRE predecessor. This is typically because of loads which
3589 // are not value numbered precisely.
3590 if (!Success)
3591 return false;
3592
3593 Instr->insertBefore(InsertPos: Pred->getTerminator()->getIterator());
3594 Instr->setName(Instr->getName() + ".pre");
3595 Instr->setDebugLoc(Instr->getDebugLoc());
3596
3597 ICF->insertInstructionTo(Inst: Instr, BB: Pred);
3598
3599 unsigned Num = VN.lookupOrAdd(V: Instr);
3600 VN.add(V: Instr, Num);
3601
3602 // Update the availability map to include the new instruction.
3603 LeaderTable.insert(N: Num, V: Instr, BB: Pred);
3604 return true;
3605}
3606
3607bool GVNPass::performScalarPRE(Instruction *CurInst) {
3608 if (isa<AllocaInst>(Val: CurInst) || CurInst->isTerminator() ||
3609 isa<PHINode>(Val: CurInst) || CurInst->getType()->isVoidTy() ||
3610 CurInst->mayReadFromMemory() || CurInst->mayHaveSideEffects() ||
3611 CurInst->getType()->isTokenLikeTy())
3612 return false;
3613
3614 // Don't do PRE on compares. The PHI would prevent CodeGenPrepare from
3615 // sinking the compare again, and it would force the code generator to
3616 // move the i1 from processor flags or predicate registers into a general
3617 // purpose register.
3618 if (isa<CmpInst>(Val: CurInst))
3619 return false;
3620
3621 // Don't do PRE on GEPs. The inserted PHI would prevent CodeGenPrepare from
3622 // sinking the addressing mode computation back to its uses. Extending the
3623 // GEP's live range increases the register pressure, and therefore it can
3624 // introduce unnecessary spills.
3625 //
3626 // This doesn't prevent Load PRE. PHI translation will make the GEP available
3627 // to the load by moving it to the predecessor block if necessary.
3628 if (isa<GetElementPtrInst>(Val: CurInst))
3629 return false;
3630
3631 if (auto *CallB = dyn_cast<CallBase>(Val: CurInst)) {
3632 // We don't currently value number ANY inline asm calls.
3633 if (CallB->isInlineAsm())
3634 return false;
3635 }
3636
3637 uint32_t ValNo = VN.lookup(V: CurInst);
3638
3639 // Look for the predecessors for PRE opportunities. We're
3640 // only trying to solve the basic diamond case, where
3641 // a value is computed in the successor and one predecessor,
3642 // but not the other. We also explicitly disallow cases
3643 // where the successor is its own predecessor, because they're
3644 // more complicated to get right.
3645 unsigned NumWith = 0;
3646 unsigned NumWithout = 0;
3647 BasicBlock *PREPred = nullptr;
3648 BasicBlock *CurrentBlock = CurInst->getParent();
3649
3650 // Update the RPO numbers for this function.
3651 if (InvalidBlockRPONumbers)
3652 assignBlockRPONumber(F&: *CurrentBlock->getParent());
3653
3654 SmallVector<std::pair<Value *, BasicBlock *>, 8> PredMap;
3655 for (BasicBlock *P : predecessors(BB: CurrentBlock)) {
3656 // We're not interested in PRE where blocks with predecessors that are
3657 // not reachable.
3658 if (!DT->isReachableFromEntry(A: P)) {
3659 NumWithout = 2;
3660 break;
3661 }
3662 // It is not safe to do PRE when P->CurrentBlock is a loop backedge.
3663 assert(BlockRPONumber.count(P) && BlockRPONumber.count(CurrentBlock) &&
3664 "Invalid BlockRPONumber map.");
3665 if (BlockRPONumber[P] >= BlockRPONumber[CurrentBlock]) {
3666 NumWithout = 2;
3667 break;
3668 }
3669
3670 uint32_t TValNo = VN.phiTranslate(Pred: P, PhiBlock: CurrentBlock, Num: ValNo, GVN&: *this);
3671 Value *PredV = findLeader(BB: P, Num: TValNo);
3672 if (!PredV) {
3673 PredMap.push_back(Elt: std::make_pair(x: static_cast<Value *>(nullptr), y&: P));
3674 PREPred = P;
3675 ++NumWithout;
3676 } else if (PredV == CurInst) {
3677 // CurInst dominates this predecessor.
3678 NumWithout = 2;
3679 break;
3680 } else {
3681 PredMap.push_back(Elt: std::make_pair(x&: PredV, y&: P));
3682 ++NumWith;
3683 }
3684 }
3685
3686 // Don't do PRE when it might increase code size, i.e. when
3687 // we would need to insert instructions in more than one pred.
3688 if (NumWithout > 1 || NumWith == 0)
3689 return false;
3690
3691 // We may have a case where all predecessors have the instruction,
3692 // and we just need to insert a phi node. Otherwise, perform
3693 // insertion.
3694 Instruction *PREInstr = nullptr;
3695
3696 if (NumWithout != 0) {
3697 if (!isSafeToSpeculativelyExecute(I: CurInst)) {
3698 // It is only valid to insert a new instruction if the current instruction
3699 // is always executed. An instruction with implicit control flow could
3700 // prevent us from doing it. If we cannot speculate the execution, then
3701 // PRE should be prohibited.
3702 if (ICF->isDominatedByICFIFromSameBlock(Insn: CurInst))
3703 return false;
3704 }
3705
3706 // Don't do PRE across indirect branch.
3707 if (isa<IndirectBrInst>(Val: PREPred->getTerminator()))
3708 return false;
3709
3710 // We can't do PRE safely on a critical edge, so instead we schedule
3711 // the edge to be split and perform the PRE the next time we iterate
3712 // on the function.
3713 unsigned SuccNum = GetSuccessorNumber(BB: PREPred, Succ: CurrentBlock);
3714 if (isCriticalEdge(TI: PREPred->getTerminator(), SuccNum)) {
3715 ToSplit.push_back(Elt: std::make_pair(x: PREPred->getTerminator(), y&: SuccNum));
3716 return false;
3717 }
3718 // We need to insert somewhere, so let's give it a shot.
3719 PREInstr = CurInst->clone();
3720 if (!performScalarPREInsertion(Instr: PREInstr, Pred: PREPred, Curr: CurrentBlock, ValNo)) {
3721 // If we failed insertion, make sure we remove the instruction.
3722#ifndef NDEBUG
3723 verifyRemoved(PREInstr);
3724#endif
3725 PREInstr->deleteValue();
3726 return false;
3727 }
3728 }
3729
3730 // Either we should have filled in the PRE instruction, or we should
3731 // not have needed insertions.
3732 assert(PREInstr != nullptr || NumWithout == 0);
3733
3734 ++NumGVNPRE;
3735
3736 // Create a PHI to make the value available in this block.
3737 PHINode *Phi = PHINode::Create(Ty: CurInst->getType(), NumReservedValues: PredMap.size(),
3738 NameStr: CurInst->getName() + ".pre-phi");
3739 Phi->insertBefore(InsertPos: CurrentBlock->begin());
3740 for (auto &[V, BB] : PredMap) {
3741 if (V) {
3742 // If we use an existing value in this phi, we have to patch the original
3743 // value because the phi will be used to replace a later value.
3744 patchReplacementInstruction(I: CurInst, Repl: V);
3745 Phi->addIncoming(V, BB);
3746 } else
3747 Phi->addIncoming(V: PREInstr, BB: PREPred);
3748 }
3749
3750 VN.add(V: Phi, Num: ValNo);
3751 // After creating a new PHI for ValNo, the phi translate result for ValNo will
3752 // be changed, so erase the related stale entries in phi translate cache.
3753 VN.eraseTranslateCacheEntry(Num: ValNo, CurrBlock: *CurrentBlock);
3754 LeaderTable.insert(N: ValNo, V: Phi, BB: CurrentBlock);
3755 Phi->setDebugLoc(CurInst->getDebugLoc());
3756 CurInst->replaceAllUsesWith(V: Phi);
3757 if (MD && Phi->getType()->isPtrOrPtrVectorTy())
3758 MD->invalidateCachedPointerInfo(Ptr: Phi);
3759 LeaderTable.erase(N: ValNo, I: CurInst, BB: CurrentBlock);
3760
3761 LLVM_DEBUG(dbgs() << "GVN PRE removed: " << *CurInst << '\n');
3762 removeInstruction(I: CurInst);
3763
3764 return true;
3765}
3766
3767/// Perform a purely local form of PRE that looks for diamond
3768/// control flow patterns and attempts to perform simple PRE at the join point.
3769bool GVNPass::performPRE(Function &F) {
3770 bool Changed = false;
3771 for (BasicBlock *CurrentBlock : depth_first(G: &F.getEntryBlock())) {
3772 // Nothing to PRE in the entry block.
3773 if (CurrentBlock == &F.getEntryBlock())
3774 continue;
3775
3776 // Don't perform PRE on an EH pad.
3777 if (CurrentBlock->isEHPad())
3778 continue;
3779
3780 for (BasicBlock::iterator BI = CurrentBlock->begin(),
3781 BE = CurrentBlock->end();
3782 BI != BE;) {
3783 Instruction *CurInst = &*BI++;
3784 Changed |= performScalarPRE(CurInst);
3785 }
3786 }
3787
3788 if (splitCriticalEdges())
3789 Changed = true;
3790
3791 return Changed;
3792}
3793
3794/// Split the critical edge connecting the given two blocks, and return
3795/// the block inserted to the critical edge.
3796BasicBlock *GVNPass::splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ) {
3797 // GVN does not require loop-simplify, do not try to preserve it if it is not
3798 // possible.
3799 BasicBlock *BB = SplitCriticalEdge(
3800 Src: Pred, Dst: Succ,
3801 Options: CriticalEdgeSplittingOptions(DT, LI, MSSAU).unsetPreserveLoopSimplify());
3802 if (BB) {
3803 if (MD)
3804 MD->invalidateCachedPredecessors();
3805 InvalidBlockRPONumbers = true;
3806 }
3807 return BB;
3808}
3809
3810/// Split critical edges found during the previous
3811/// iteration that may enable further optimization.
3812bool GVNPass::splitCriticalEdges() {
3813 if (ToSplit.empty())
3814 return false;
3815
3816 bool Changed = false;
3817 do {
3818 std::pair<Instruction *, unsigned> Edge = ToSplit.pop_back_val();
3819 Changed |= SplitCriticalEdge(TI: Edge.first, SuccNum: Edge.second,
3820 Options: CriticalEdgeSplittingOptions(DT, LI, MSSAU)) !=
3821 nullptr;
3822 } while (!ToSplit.empty());
3823 if (Changed) {
3824 if (MD)
3825 MD->invalidateCachedPredecessors();
3826 InvalidBlockRPONumbers = true;
3827 }
3828 return Changed;
3829}
3830
3831/// Executes one iteration of GVN.
3832bool GVNPass::iterateOnFunction(Function &F) {
3833 cleanupGlobalSets();
3834
3835 // Top-down walk of the dominator tree.
3836 bool Changed = false;
3837 // Needed for value numbering with phi construction to work.
3838 // RPOT walks the graph in its constructor and will not be invalidated during
3839 // processBlock.
3840 ReversePostOrderTraversal<Function *> RPOT(&F);
3841
3842 for (BasicBlock *BB : RPOT)
3843 Changed |= processBlock(BB);
3844
3845 return Changed;
3846}
3847
3848void GVNPass::cleanupGlobalSets() {
3849 VN.clear();
3850 LeaderTable.clear();
3851 BlockRPONumber.clear();
3852 ICF->clear();
3853 InvalidBlockRPONumbers = true;
3854}
3855
3856void GVNPass::removeInstruction(Instruction *I) {
3857 VN.erase(V: I);
3858 if (MD) MD->removeInstruction(InstToRemove: I);
3859 if (MSSAU)
3860 MSSAU->removeMemoryAccess(I);
3861#ifndef NDEBUG
3862 verifyRemoved(I);
3863#endif
3864 ICF->removeInstruction(Inst: I);
3865 I->eraseFromParent();
3866 ++NumGVNInstr;
3867}
3868
3869/// Verify that the specified instruction does not occur in our
3870/// internal data structures.
3871void GVNPass::verifyRemoved(const Instruction *Inst) const {
3872 VN.verifyRemoved(V: Inst);
3873}
3874
3875/// BB is declared dead, which implied other blocks become dead as well. This
3876/// function is to add all these blocks to "DeadBlocks". For the dead blocks'
3877/// live successors, update their phi nodes by replacing the operands
3878/// corresponding to dead blocks with UndefVal.
3879void GVNPass::addDeadBlock(BasicBlock *BB) {
3880 SmallVector<BasicBlock *, 4> NewDead;
3881 SmallSetVector<BasicBlock *, 4> DF;
3882
3883 NewDead.push_back(Elt: BB);
3884 while (!NewDead.empty()) {
3885 BasicBlock *D = NewDead.pop_back_val();
3886 if (DeadBlocks.count(key: D))
3887 continue;
3888
3889 // All blocks dominated by D are dead.
3890 SmallVector<BasicBlock *, 8> Dom;
3891 DT->getDescendants(R: D, Result&: Dom);
3892 DeadBlocks.insert_range(R&: Dom);
3893
3894 // Figure out the dominance-frontier(D).
3895 for (BasicBlock *B : Dom) {
3896 for (BasicBlock *S : successors(BB: B)) {
3897 if (DeadBlocks.count(key: S))
3898 continue;
3899
3900 bool AllPredDead = true;
3901 for (BasicBlock *P : predecessors(BB: S))
3902 if (!DeadBlocks.count(key: P)) {
3903 AllPredDead = false;
3904 break;
3905 }
3906
3907 if (!AllPredDead) {
3908 // S could be proved dead later on. That is why we don't update phi
3909 // operands at this moment.
3910 DF.insert(X: S);
3911 } else {
3912 // While S is not dominated by D, it is dead by now. This could take
3913 // place if S already have a dead predecessor before D is declared
3914 // dead.
3915 NewDead.push_back(Elt: S);
3916 }
3917 }
3918 }
3919 }
3920
3921 // For the dead blocks' live successors, update their phi nodes by replacing
3922 // the operands corresponding to dead blocks with UndefVal.
3923 for (BasicBlock *B : DF) {
3924 if (DeadBlocks.count(key: B))
3925 continue;
3926
3927 // First, split the critical edges. This might also create additional blocks
3928 // to preserve LoopSimplify form and adjust edges accordingly.
3929 SmallVector<BasicBlock *, 4> Preds(predecessors(BB: B));
3930 for (BasicBlock *P : Preds) {
3931 if (!DeadBlocks.count(key: P))
3932 continue;
3933
3934 if (is_contained(Range: successors(BB: P), Element: B) &&
3935 isCriticalEdge(TI: P->getTerminator(), Succ: B)) {
3936 if (BasicBlock *S = splitCriticalEdges(Pred: P, Succ: B))
3937 DeadBlocks.insert(X: P = S);
3938 }
3939 }
3940
3941 // Now poison the incoming values from the dead predecessors.
3942 for (BasicBlock *P : predecessors(BB: B)) {
3943 if (!DeadBlocks.count(key: P))
3944 continue;
3945 for (PHINode &Phi : B->phis()) {
3946 Phi.setIncomingValueForBlock(BB: P, V: PoisonValue::get(T: Phi.getType()));
3947 if (MD)
3948 MD->invalidateCachedPointerInfo(Ptr: &Phi);
3949 }
3950 }
3951 }
3952}
3953
3954// If the given branch is recognized as a foldable branch (i.e. conditional
3955// branch with constant condition), it will perform following analyses and
3956// transformation.
3957// 1) If the dead out-coming edge is a critical-edge, split it. Let
3958// R be the target of the dead out-coming edge.
3959// 1) Identify the set of dead blocks implied by the branch's dead outcoming
3960// edge. The result of this step will be {X| X is dominated by R}
3961// 2) Identify those blocks which haves at least one dead predecessor. The
3962// result of this step will be dominance-frontier(R).
3963// 3) Update the PHIs in DF(R) by replacing the operands corresponding to
3964// dead blocks with "UndefVal" in an hope these PHIs will optimized away.
3965//
3966// Return true iff *NEW* dead code are found.
3967bool GVNPass::processFoldableCondBr(CondBrInst *BI) {
3968 // If a branch has two identical successors, we cannot declare either dead.
3969 if (BI->getSuccessor(i: 0) == BI->getSuccessor(i: 1))
3970 return false;
3971
3972 ConstantInt *Cond = dyn_cast<ConstantInt>(Val: BI->getCondition());
3973 if (!Cond)
3974 return false;
3975
3976 BasicBlock *DeadRoot =
3977 Cond->getZExtValue() ? BI->getSuccessor(i: 1) : BI->getSuccessor(i: 0);
3978 if (DeadBlocks.count(key: DeadRoot))
3979 return false;
3980
3981 if (!DeadRoot->getSinglePredecessor())
3982 DeadRoot = splitCriticalEdges(Pred: BI->getParent(), Succ: DeadRoot);
3983
3984 addDeadBlock(BB: DeadRoot);
3985 return true;
3986}
3987
3988// performPRE() will trigger assert if it comes across an instruction without
3989// associated val-num. As it normally has far more live instructions than dead
3990// instructions, it makes more sense just to "fabricate" a val-number for the
3991// dead code than checking if instruction involved is dead or not.
3992void GVNPass::assignValNumForDeadCode() {
3993 for (BasicBlock *BB : DeadBlocks) {
3994 for (Instruction &Inst : *BB) {
3995 unsigned ValNum = VN.lookupOrAdd(V: &Inst);
3996 LeaderTable.insert(N: ValNum, V: &Inst, BB);
3997 }
3998 }
3999}
4000
4001class llvm::GVNLegacyPass : public FunctionPass {
4002public:
4003 static char ID; // Pass identification, replacement for typeid.
4004
4005 explicit GVNLegacyPass(bool MemDepAnalysis = GVNEnableMemDep,
4006 bool MemSSAAnalysis = GVNEnableMemorySSA,
4007 bool ScalarPRE = true)
4008 : FunctionPass(ID), Impl(GVNOptions()
4009 .setMemDep(MemDepAnalysis)
4010 .setMemorySSA(MemSSAAnalysis)
4011 .setScalarPRE(ScalarPRE)) {
4012 initializeGVNLegacyPassPass(*PassRegistry::getPassRegistry());
4013 }
4014
4015 bool runOnFunction(Function &F) override {
4016 if (skipFunction(F))
4017 return false;
4018
4019 auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
4020 if (Impl.isMemorySSAEnabled() && !MSSAWP)
4021 MSSAWP = &getAnalysis<MemorySSAWrapperPass>();
4022
4023 return Impl.runImpl(
4024 F, RunAC&: getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F),
4025 RunDT&: getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
4026 RunTLI: getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F),
4027 RunAA&: getAnalysis<AAResultsWrapperPass>().getAAResults(),
4028 RunMD: Impl.isMemDepEnabled()
4029 ? &getAnalysis<MemoryDependenceWrapperPass>().getMemDep()
4030 : nullptr,
4031 LI&: getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
4032 RunORE: &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(),
4033 MSSA: MSSAWP ? &MSSAWP->getMSSA() : nullptr);
4034 }
4035
4036 void getAnalysisUsage(AnalysisUsage &AU) const override {
4037 AU.addRequired<AssumptionCacheTracker>();
4038 AU.addRequired<DominatorTreeWrapperPass>();
4039 AU.addRequired<TargetLibraryInfoWrapperPass>();
4040 AU.addRequired<LoopInfoWrapperPass>();
4041 if (Impl.isMemDepEnabled())
4042 AU.addRequired<MemoryDependenceWrapperPass>();
4043 AU.addRequired<AAResultsWrapperPass>();
4044 AU.addPreserved<DominatorTreeWrapperPass>();
4045 AU.addPreserved<GlobalsAAWrapperPass>();
4046 AU.addPreserved<TargetLibraryInfoWrapperPass>();
4047 AU.addPreserved<LoopInfoWrapperPass>();
4048 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
4049 AU.addPreserved<MemorySSAWrapperPass>();
4050 if (Impl.isMemorySSAEnabled())
4051 AU.addRequired<MemorySSAWrapperPass>();
4052 }
4053
4054private:
4055 GVNPass Impl;
4056};
4057
4058char GVNLegacyPass::ID = 0;
4059
4060INITIALIZE_PASS_BEGIN(GVNLegacyPass, "gvn", "Global Value Numbering", false, false)
4061INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
4062INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)
4063INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
4064INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
4065INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
4066INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
4067INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
4068INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
4069INITIALIZE_PASS_END(GVNLegacyPass, "gvn", "Global Value Numbering", false, false)
4070
4071// The public interface to this file...
4072FunctionPass *llvm::createGVNPass() { return new GVNLegacyPass(); }
4073FunctionPass *llvm::createGVNPass(bool ScalarPRE) {
4074 return new GVNLegacyPass(GVNEnableMemDep, GVNEnableMemorySSA, ScalarPRE);
4075}
4076