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