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