LLVM 24.0.0git
GVN.cpp
Go to the documentation of this file.
1//===- GVN.cpp - Eliminate redundant values and loads ---------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass performs global value numbering to eliminate fully redundant
10// instructions. It also performs simple dead load elimination.
11//
12// Note that this pass does the value numbering itself; it does not use the
13// ValueNumbering analysis passes.
14//
15//===----------------------------------------------------------------------===//
16
18#include "ScalarOptions.h"
19#include "llvm/ADT/DenseMap.h"
21#include "llvm/ADT/Hashing.h"
22#include "llvm/ADT/MapVector.h"
24#include "llvm/ADT/STLExtras.h"
25#include "llvm/ADT/SetVector.h"
28#include "llvm/ADT/Statistic.h"
32#include "llvm/Analysis/CFG.h"
37#include "llvm/Analysis/Loads.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"
58#include "llvm/IR/LLVMContext.h"
59#include "llvm/IR/Metadata.h"
60#include "llvm/IR/Module.h"
61#include "llvm/IR/PassManager.h"
64#include "llvm/IR/Type.h"
65#include "llvm/IR/Use.h"
66#include "llvm/IR/Value.h"
68#include "llvm/Pass.h"
72#include "llvm/Support/Debug.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
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;
119
121
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(Ty->getContext(), Other.Attrs).has_value())
135 return false;
136 return true;
137 }
138
140 return hash_combine(Value.Opcode, Value.Ty,
141 hash_combine_range(Value.VarArgs));
142 }
143};
144
146 static unsigned getHashValue(const GVNValueTable::Expression &E) {
147 using llvm::hash_value;
148
149 return static_cast<unsigned>(hash_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.
161public:
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.
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:
183 const LeaderListNode *Current;
184
185 public:
186 using iterator_category = std::forward_iterator_tag;
188 using difference_type = std::ptrdiff_t;
191
192 leader_iterator(const LeaderListNode *C) : Current(C) {}
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
208 auto I = NumToLeaders.find(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.
243 const ScalarOptions *Opts = nullptr;
244 llvm::GVNOptions Options;
245
246public:
247 struct AvailableValue;
249
251
252 /// This removes the specified instruction from
253 /// our various maps and marks it for deletion.
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;
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.
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,
303 OptimizationRemarkEmitter *ORE, MemorySSA *MSSA = nullptr);
304
305 // List of critical edges to be split between iterations.
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;
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 {DepKind::Other, BB, Addr, Inst, -1};
332 }
333
334 static ReachingMemVal getDef(const Value *Addr, Instruction *Inst) {
335 return {DepKind::Def, Inst->getParent(), Addr, Inst, -1};
336 }
337
338 static ReachingMemVal getClobber(const Value *Addr, Instruction *Inst,
339 int32_t Offset = -1) {
340 return {DepKind::Clobber, Inst->getParent(), Addr, Inst, Offset};
341 }
342
343 static ReachingMemVal getSelect(BasicBlock *BB, SelectInst *Sel,
344 const Value *TrueAddr,
345 const Value *FalseAddr) {
346 return {DepKind::Select, BB, nullptr, nullptr, -1, Sel,
347 TrueAddr, 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.
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.
479 /// Kind of the live-out value.
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
512 AvailableValue Res;
513 Res.Val = nullptr;
514 Res.Kind = ValType::UndefVal;
515 Res.Offset = 0;
516 return Res;
517 }
518
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
536 assert(isSimpleValue() && "Wrong accessor");
537 return Val;
538 }
539
541 assert(isCoercedLoadValue() && "Wrong accessor");
542 return cast<LoadInst>(Val);
543 }
544
546 assert(isMemIntrinValue() && "Wrong accessor");
547 return cast<MemIntrinsic>(Val);
548 }
549
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.
558};
559
560/// Represents an AvailableValue which can be rematerialized at the end of
561/// the associated BasicBlock.
563 /// BB - The basic block in question.
564 BasicBlock *BB = nullptr;
565
566 /// AV - The actual available value.
568
571 Res.BB = BB;
572 Res.AV = std::move(AV);
573 return Res;
574 }
575
577 unsigned Offset = 0) {
578 return get(BB, AvailableValue::get(V, Offset));
579 }
580
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.
588 return AV.MaterializeAdjustedValue(Load, 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>(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(lookupOrAdd(GCR->getOperand(0)));
605 E.VarArgs.push_back(lookupOrAdd(GCR->getBasePtr()));
606 E.VarArgs.push_back(lookupOrAdd(GCR->getDerivedPtr()));
607 } else {
608 for (Use &Op : I->operands())
609 E.VarArgs.push_back(lookupOrAdd(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(E.VarArgs[0], E.VarArgs[1]);
619 E.Commutative = true;
620 }
621
622 if (auto *IVI = dyn_cast<InsertValueInst>(I)) {
623 E.VarArgs.append(IVI->idx_begin(), IVI->idx_end());
624 } else if (auto *SVI = dyn_cast<ShuffleVectorInst>(I)) {
625 ArrayRef<int> ShuffleMask = SVI->getShuffleMask();
626 E.VarArgs.append(ShuffleMask.begin(), ShuffleMask.end());
627 } else if (auto *CB = dyn_cast<CallBase>(I)) {
628 E.Attrs = CB->getAttributes();
629 }
630
631 return E;
632}
633
635GVNValueTable::createCmpExpr(unsigned Opcode, CmpInst::Predicate Predicate,
636 Value *LHS, Value *RHS) {
637 assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) &&
638 "Not a comparison!");
641 E.VarArgs.push_back(lookupOrAdd(LHS));
642 E.VarArgs.push_back(lookupOrAdd(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(E.VarArgs[0], E.VarArgs[1]);
648 }
649 E.Opcode = (Opcode << 8) | Predicate;
650 E.Commutative = true;
651 return E;
652}
653
655GVNValueTable::createExtractValueExpr(ExtractValueInst *EI) {
656 assert(EI && "Not an ExtractValueInst?");
658 E.Ty = EI->getType();
659 E.Opcode = 0;
660
661 WithOverflowInst *WO = dyn_cast<WithOverflowInst>(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(lookupOrAdd(WO->getLHS()));
668 E.VarArgs.push_back(lookupOrAdd(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(lookupOrAdd(Op));
677
678 append_range(E.VarArgs, EI->indices());
679
680 return E;
681}
682
683GVNValueTable::Expression GVNValueTable::createGEPExpr(GetElementPtrInst *GEP) {
685 Type *PtrTy = GEP->getType()->getScalarType();
686 const DataLayout &DL = GEP->getDataLayout();
687 unsigned BitWidth = DL.getIndexTypeSizeInBits(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(lookupOrAdd(GEP->getPointerOperand()));
697 for (const auto &[V, Scale] : VariableOffsets) {
698 E.VarArgs.push_back(lookupOrAdd(V));
699 E.VarArgs.push_back(lookupOrAdd(ConstantInt::get(Context, Scale)));
700 }
701 if (!ConstantOffset.isZero())
702 E.VarArgs.push_back(
703 lookupOrAdd(ConstantInt::get(Context, 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(lookupOrAdd(Op));
711 }
712 return E;
713}
714
715//===----------------------------------------------------------------------===//
716// ValueTable External Functions
717//===----------------------------------------------------------------------===//
718
724
725/// add - Insert a value into the table with a specified value number.
727 ValueNumbering.insert(std::make_pair(V, Num));
728 if (PHINode *PN = dyn_cast<PHINode>(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");
742 Exp.VarArgs.push_back(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(C)) {
775 Expression Exp = createExpr(C);
776 uint32_t E = assignExpNewValueNum(Exp).first;
777 ValueNumbering[C] = E;
778 return E;
779 }
780
781 if (MD && AA->onlyReadsMemory(C)) {
782 Expression Exp = createExpr(C);
783 auto [E, IsValNumNew] = assignExpNewValueNum(Exp);
784 if (IsValNumNew) {
785 ValueNumbering[C] = E;
786 return E;
787 }
788
789 MemDepResult LocalDep = MD->getDependency(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>(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(C->getArgOperand(I));
808 uint32_t LocalDepCallVN = lookupOrAdd(LocalDepCall->getArgOperand(I));
809 if (CVN != LocalDepCallVN) {
810 ValueNumbering[C] = NextValueNumber;
811 return NextValueNumber++;
812 }
813 }
814
815 uint32_t V = lookupOrAdd(LocalDepCall);
816 ValueNumbering[C] = V;
817 return V;
818 }
819
820 // Non-local case.
822 MD->getNonLocalCallDependency(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>(I.getResult().getInst());
840 // FIXME: All duplicated with non-local case.
841 if (NonLocalDepCall && DT->properlyDominates(I.getBB(), 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(C->getArgOperand(I));
861 uint32_t CDepVN = lookupOrAdd(CDep->getArgOperand(I));
862 if (CVN != CDepVN) {
863 ValueNumbering[C] = NextValueNumber;
864 return NextValueNumber++;
865 }
866 }
867
868 uint32_t V = lookupOrAdd(CDep);
869 ValueNumbering[C] = V;
870 return V;
871 }
872
873 if (MSSA && IsMSSAEnabled && AA->onlyReadsMemory(C)) {
874 Expression Exp = createExpr(C);
875 addMemoryStateToExp(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
893 Exp.Ty = I->getType();
894 Exp.Opcode = I->getOpcode();
895 for (Use &Op : I->operands())
896 Exp.VarArgs.push_back(lookupOrAdd(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.
906 return ValueNumbering.contains(V);
907}
908
910 return MSSA->isLiveOnEntryDef(MA) || isa<MemoryPhi>(MA)
911 ? lookupOrAdd(MA->getBlock())
912 : lookupOrAdd(cast<MemoryUseOrDef>(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.
918 auto VI = ValueNumbering.find(V);
919 if (VI != ValueNumbering.end())
920 return VI->second;
921
922 auto *I = dyn_cast<Instruction>(V);
923 if (!I) {
924 ValueNumbering[V] = NextValueNumber;
925 if (isa<BasicBlock>(V))
926 NumberingBB[NextValueNumber] = cast<BasicBlock>(V);
927 return NextValueNumber++;
928 }
929
930 Expression Exp;
931 switch (I->getOpcode()) {
932 case Instruction::Call:
933 return lookupOrAddCall(cast<CallInst>(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(I->getOpcode(), cast<CmpInst>(I)->getPredicate(),
980 I->getOperand(0), I->getOperand(1));
981 break;
982 case Instruction::GetElementPtr:
983 Exp = createGEPExpr(cast<GetElementPtrInst>(I));
984 break;
985 case Instruction::ExtractValue:
986 Exp = createExtractValueExpr(cast<ExtractValueInst>(I));
987 break;
988 case Instruction::PHI:
989 ValueNumbering[V] = NextValueNumber;
990 NumberingPhi[NextValueNumber] = cast<PHINode>(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.
1008 auto VI = ValueNumbering.find(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.
1021 CmpInst::Predicate Predicate, Value *LHS,
1022 Value *RHS) {
1023 Expression Exp = createCmpExpr(Opcode, Predicate, LHS, RHS);
1024 return assignExpNewValueNum(Exp).first;
1025}
1026
1028 Value *LHS, Value *RHS) {
1029 Expression Exp = createCmpExpr(Opcode, Predicate, LHS, RHS);
1030 return ExpressionNumbering.lookup(Exp);
1031}
1032
1033/// Returns the value number of ptrtoint \p Ptr to \Ty.
1035 Expression Exp(Instruction::PtrToInt);
1036 Exp.Ty = Ty;
1037 Exp.VarArgs.push_back(lookupOrAdd(Ptr));
1038 return ExpressionNumbering.lookup(Exp);
1039}
1040
1041/// Remove all entries from the ValueTable.
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.
1056 uint32_t Num = ValueNumbering.lookup(V);
1057 ValueNumbering.erase(V);
1058 // If V is PHINode, V <--> value number is an one-to-one mapping.
1059 if (isa<PHINode>(V))
1060 NumberingPhi.erase(Num);
1061 else if (isa<BasicBlock>(V))
1062 NumberingBB.erase(Num);
1063}
1064
1065/// verifyRemoved - Verify that the value is removed from all internal data
1066/// structures.
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.
1078 const auto &[It, Inserted] = NumToLeaders.try_emplace(N, V, BB, 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.
1090 auto It = NumToLeaders.find(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>(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(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>(Next);
1123 }
1124 }
1125}
1126
1127//===----------------------------------------------------------------------===//
1128// GVN Pass
1129//===----------------------------------------------------------------------===//
1130
1132 return Options.AllowScalarPRE.value_or(Opts->enable_scalar_pre);
1133}
1134
1136 return Options.AllowLoadPRE.value_or(Opts->enable_load_pre);
1137}
1138
1140 return Options.AllowLoadInLoopPRE.value_or(Opts->enable_load_in_loop_pre);
1141}
1142
1144 return Options.AllowLoadPRESplitBackedge.value_or(
1145 Opts->enable_split_backedge_in_load_pre);
1146}
1147
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(false);
1154 return Options.AllowMemDep.value_or(valueOr(Opts->enable_gvn_memdep, true));
1155}
1156
1158 return Options.AllowMemorySSA.value_or(Opts->enable_gvn_memoryssa);
1159}
1160
1163
1164GVNPass::~GVNPass() = default;
1165
1166GVNPass::GVNPass(GVNPass &&) noexcept = default;
1167
1168GVNPass &GVNPass::operator=(GVNPass &&) noexcept = default;
1169
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>(F);
1177 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
1178 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1179 auto &AA = AM.getResult<AAManager>(F);
1180 auto *MemDep = Impl->isMemDepEnabled()
1181 ? &AM.getResult<MemoryDependenceAnalysis>(F)
1182 : nullptr;
1183 auto &LI = AM.getResult<LoopAnalysis>(F);
1184 auto *MSSA = AM.getCachedResult<MemorySSAAnalysis>(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>(F);
1189 }
1190 auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
1191 bool Changed = Impl->run(F, AC, DT, TLI, AA, MemDep, LI, &ORE,
1192 MSSA ? &MSSA->getMSSA() : nullptr);
1193 if (!Changed)
1194 return PreservedAnalyses::all();
1198 if (MSSA)
1200 PA.preserve<LoopAnalysis>();
1201 return PA;
1202}
1203
1205 salvageKnowledge(I, AC);
1207 removeInstruction(I);
1208}
1209
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.
1234 /// We know the block *is* fully available. This is a fixpoint.
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.
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.
1252 const ScalarOptions &Opts, BasicBlock *BB,
1253 DenseMap<BasicBlock *, AvailabilityState> &FullyAvailableBlocks) {
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(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(
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(CurrBB)) {
1297 MaxBBSpeculationCutoffReachedTimes += (int)OutOfBudget;
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(pred_begin(CurrBB), pred_end(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(BB);
1321 if (It == FullyAvailableBlocks.end())
1322 return; // Never queried this block, leave as-is.
1323 switch (AvailabilityState &State = It->second) {
1326 return; // Don't backpropagate further, continue processing worklist.
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(succ_begin(BB), 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(succ_begin(*UnavailableBB), succ_end(*UnavailableBB));
1346 while (!Worklist.empty())
1347 MarkAsFixpointAndEnqueueSuccessors(Worklist.pop_back_val(),
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(),
1358
1359 assert(NewSpeculativelyAvailableBBs.empty() &&
1360 "Must have fixed all the new speculatively available blocks.");
1361#endif
1362
1363 return !UnavailableBB;
1364}
1365
1368
1369/// If the specified OldValue exists in ValuesPerBlock, replace its value with
1370/// NewValue.
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 *
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(ValuesPerBlock[0].BB, 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.
1404 SSAUpdater SSAUpdate(&NewPHIs);
1405 SSAUpdate.Initialize(Load->getType(), 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, AV.MaterializeAdjustedValue(Load));
1426 }
1427
1428 // Perform PHI construction.
1429 return SSAUpdate.GetValueInMiddleOfBlock(Load->getParent());
1430}
1431
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(Res, Offset, LoadTy, InsertPt, 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(CoercedLoad, Load, false);
1452 } else {
1453 Res = getValueForLoad(CoercedLoad, Offset, LoadTy, InsertPt,
1454 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(LLVMContext::MD_noundef))
1466 CoercedLoad->dropUnknownNonDebugMetadata(
1467 {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()) {
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(Sel->getCondition(), V1, V2, "",
1488 InsertPt->getIterator(),
1489 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>(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>(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(From, Between);
1513 Exclusion.insert(Between->getParent());
1514 return !isPotentiallyReachable(From, To, &Exclusion, DT);
1515}
1516
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>(U) || isa<StoreInst>(U))) {
1527 auto *I = cast<Instruction>(U);
1528 if (I->getFunction() == Load->getFunction() && DT->dominates(I, Load)) {
1529 // Use the most immediately dominating value.
1530 if (OtherAccess) {
1531 if (DT->dominates(OtherAccess, 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>(U) || isa<StoreInst>(U))) {
1548 auto *I = cast<Instruction>(U);
1549 if (I->getFunction() == Load->getFunction() &&
1550 isPotentiallyReachable(I, Load, nullptr, DT)) {
1551 if (OtherAccess) {
1552 if (liesBetween(OtherAccess, I, Load, DT)) {
1553 OtherAccess = I;
1554 } else if (!liesBetween(I, OtherAccess, 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.
1574 const DominatorTree *DT,
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(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(BatchAA.getModRefInfo(Inst, Loc))) {
1607 // A simple store to the exact location can forward its value.
1608 if (auto *SI = dyn_cast<StoreInst>(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>(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(Load);
1633 Value *V1 = findDominatingValue(*Opts, Loc.getWithNewPtr(TrueAddr),
1634 Load->getType(), From, getAliasAnalysis());
1635 if (!V1)
1636 return std::nullopt;
1637 Value *V2 = findDominatingValue(*Opts, Loc.getWithNewPtr(FalseAddr),
1638 Load->getType(), From, 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>(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(Load->getType(), Address, DepSI, DL);
1663 if (Offset != -1)
1664 return AvailableValue::get(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>(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(DepLoad, LoadType,
1684 DepLoad->getFunction())) {
1685 const auto ClobberOff = MD->getClobberOffset(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(DepLoad, LoadType,
1693 DepLoad->getFunction()) ||
1694 Offset < 0)
1695 Offset = -1;
1696 }
1697 if (Offset == -1)
1698 Offset =
1699 analyzeLoadFromClobberingLoad(LoadType, Address, DepLoad, DL);
1700 if (Offset != -1)
1701 return AvailableValue::getLoad(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>(DepInst)) {
1708 if (Address && !Load->isAtomic()) {
1710 DepMI, DL);
1711 if (Offset != -1)
1712 return AvailableValue::getMI(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>(DepInst) || isLifetimeStart(DepInst))
1731 return AvailableValue::get(UndefValue::get(Load->getType()));
1732
1733 if (Constant *InitVal =
1734 getInitialValueOfAllocation(DepInst, TLI, Load->getType()))
1735 return AvailableValue::get(InitVal);
1736
1737 if (StoreInst *S = dyn_cast<StoreInst>(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(S->getValueOperand(), Load->getType(),
1742 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(S->getValueOperand());
1750 }
1751
1752 if (LoadInst *LD = dyn_cast<LoadInst>(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(LD, Load->getType(),
1757 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(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>(DepInst)) {
1771 assert(Sel->getType() == Load->getPointerOperandType());
1772 if (auto AV = analyzeSelectAvailability(Load, Sel, Sel->getTrueValue(),
1773 Sel->getFalseValue(), 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,
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(DepBB)) {
1798 // Dead dependent mem-op disguise as a load evaluating the same value
1799 // as the load in question.
1800 ValuesPerBlock.push_back(AvailableValueInBlock::getUndef(DepBB));
1801 continue;
1802 }
1803
1804 if (Dep.Kind == DepKind::Other) {
1805 UnavailableBlocks.push_back(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, Dep.Sel, const_cast<Value *>(Dep.SelTrueAddr),
1815 const_cast<Value *>(Dep.SelFalseAddr), DepBB->getTerminator())) {
1816 ValuesPerBlock.push_back(
1817 AvailableValueInBlock::get(DepBB, std::move(*AV)));
1818 } else {
1819 UnavailableBlocks.push_back(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, 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 AvailableValueInBlock::get(DepBB, std::move(*AV)));
1834 } else {
1835 UnavailableBlocks.push_back(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(0);
1870 if (SuccBB == LoadBB)
1871 SuccBB = Term->getSuccessor(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>(Inst))
1878 continue;
1879 if (--NumInsts == 0)
1880 return nullptr;
1881
1882 if (!Inst.isIdenticalTo(Load))
1883 continue;
1884
1885 bool HasLocalDep = true;
1886 if (!isMemorySSAEnabled()) {
1887 MemDepResult Dep = MD->getDependency(&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(&Inst); MA && isa<MemoryUse>(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(&Inst))
1903 return cast<LoadInst>(&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 NewLoad, nullptr, NewLoad->getParent(), MemorySSA::BeforeTerminator);
1929 if (auto *NewDef = dyn_cast<MemoryDef>(NewAccess))
1930 MSSAU->insertDef(NewDef, /*RenameUses=*/true);
1931 else
1932 MSSAU->insertUse(cast<MemoryUse>(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(LLVMContext::MD_invariant_load))
1941 NewLoad->setMetadata(LLVMContext::MD_invariant_load, MD);
1942 if (auto *InvGroupMD = Load->getMetadata(LLVMContext::MD_invariant_group))
1943 NewLoad->setMetadata(LLVMContext::MD_invariant_group, InvGroupMD);
1944 if (auto *RangeMD = Load->getMetadata(LLVMContext::MD_range))
1945 NewLoad->setMetadata(LLVMContext::MD_range, RangeMD);
1946 if (auto *NoFPClassMD = Load->getMetadata(LLVMContext::MD_nofpclass))
1947 NewLoad->setMetadata(LLVMContext::MD_nofpclass, NoFPClassMD);
1948
1949 if (auto *AccessMD = Load->getMetadata(LLVMContext::MD_access_group))
1950 if (LI->getLoopFor(Load->getParent()) == LI->getLoopFor(UnavailableBlock))
1951 NewLoad->setMetadata(LLVMContext::MD_access_group, 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 AvailableValueInBlock::get(UnavailableBlock, NewLoad));
1962 if (MD)
1963 MD->invalidateCachedPointerInfo(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(UnavailableBlock);
1970 if (It != CriticalEdgePredAndLoad->end()) {
1971 ++NumPRELoadMoved2CEPred;
1972 ICF->insertInstructionTo(NewLoad, UnavailableBlock);
1973 LoadInst *OldLoad = It->second;
1974 combineMetadataForCSE(NewLoad, OldLoad, /*DoesKMove=*/true);
1975 OldLoad->replaceAllUsesWith(NewLoad);
1976 replaceValuesPerBlockEntry(ValuesPerBlock, OldLoad, NewLoad);
1977 if (uint32_t ValNo = VN.lookup(OldLoad, false))
1978 LeaderTable.erase(ValNo, OldLoad, OldLoad->getParent());
1979 removeInstruction(OldLoad);
1980 }
1981 }
1982 }
1983
1984 // Perform PHI construction.
1985 Value *V = constructSSAForLoadSet(Load, ValuesPerBlock, getDominatorTree());
1986 // constructSSAForLoadSet is responsible for combining metadata.
1987 ICF->removeUsersOf(Load);
1988 Load->replaceAllUsesWith(V);
1989 if (isa<PHINode>(V))
1990 V->takeName(Load);
1991 if (Instruction *I = dyn_cast<Instruction>(V))
1992 I->setDebugLoc(Load->getDebugLoc());
1993 if (MD && V->getType()->isPtrOrPtrVectorTy())
1994 MD->invalidateCachedPointerInfo(V);
1995 ORE->emit([&]() {
1996 return OptimizationRemark(DEBUG_TYPE, "LoadPRE", Load)
1997 << "load eliminated by PRE";
1998 });
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(Load);
2037
2038 while (TmpBB->getSinglePredecessor()) {
2039 TmpBB = TmpBB->getSinglePredecessor();
2040 if (TmpBB == LoadBB) // Infinite (unreachable) loop.
2041 return false;
2042 if (Blockers.count(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(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(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, Pred, FullyAvailableBlocks)) {
2087 continue;
2088 }
2089
2090 if (Pred->getTerminator()->getNumSuccessors() != 1) {
2091 if (isa<IndirectBrInst>(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.
2107 if (DT->dominates(LoadBB, 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(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())
2145 DT))
2146 return false;
2147 for (auto &PL : PredLoads)
2148 if (!isSafeToSpeculativelyExecute(Load, PL.first->getTerminator(), AC,
2149 DT))
2150 return false;
2151 for (auto &CEP : CriticalEdgePredAndLoad)
2152 if (!isSafeToSpeculativelyExecute(Load, 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(OrigPred, 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(Cur, Cur->getSinglePredecessor(),
2189 *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(LoadBB, UnavailablePred, *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(I);
2248 }
2249
2250 eliminatePartiallyRedundantLoad(Load, ValuesPerBlock, PredLoads,
2251 &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(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(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(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(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(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(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(ReloadBB, 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(Load, 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
2359 using namespace ore;
2360
2361 ORE->emit([&]() {
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(Attribute::SanitizeAddress) ||
2374 Load->getFunction()->hasFnAttribute(Attribute::SanitizeHWAddress))
2375 return false;
2376
2377 // Find the non-local dependencies of the load.
2378 LoadDepVect Deps;
2379 MD->getNonLocalPointerDependency(Load, 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
2389 MemVals.reserve(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 ReachingMemVal::getSelect(BB, Sel, Addrs.first, Addrs.second));
2400 continue;
2401 }
2402 Value *Address = SelAddr.getAddr();
2403 if (R.isClobber())
2404 MemVals.emplace_back(ReachingMemVal::getClobber(Address, Inst));
2405 else if (R.isDef())
2406 MemVals.emplace_back(ReachingMemVal::getDef(Address, Inst));
2407 else
2408 MemVals.emplace_back(ReachingMemVal::getUnknown(BB, Address, Inst));
2409 }
2410
2411 return processNonLocalLoad(Load, MemVals);
2412}
2413
2414bool GVNPassImpl::processNonLocalLoad(LoadInst *Load,
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>(Load->getOperand(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>(U.get()); I && VN.exists(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, getDominatorTree());
2459 // constructSSAForLoadSet is responsible for combining metadata.
2460 ICF->removeUsersOf(Load);
2461 Load->replaceAllUsesWith(V);
2462
2463 if (isa<PHINode>(V))
2464 V->takeName(Load);
2465 if (Instruction *I = dyn_cast<Instruction>(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(V);
2473 ++NumGVNLoad;
2474 reportLoadElim(Load, V, ORE);
2476 return true;
2477 }
2478
2479 // Step 3: Eliminate partial redundancy.
2480 if (!isLoadPREEnabled())
2481 return Changed;
2482 if (!isLoadInLoopPREEnabled() && LI->getLoopFor(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(0);
2494
2495 if (ConstantInt *Cond = dyn_cast<ConstantInt>(V)) {
2496 if (Cond->isZero()) {
2497 Type *Int8Ty = Type::getInt8Ty(V->getContext());
2498 Type *PtrTy = PointerType::get(V->getContext(), 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(Int8Ty), Constant::getNullValue(PtrTy),
2504 IntrinsicI->getIterator());
2505 if (MSSAU) {
2506 const MemoryUseOrDef *FirstNonDom = nullptr;
2507 const auto *AL =
2508 MSSAU->getMemorySSA()->getBlockAccesses(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>(&Acc))
2517 if (!Current->getMemoryInst()->comesBefore(NewS)) {
2518 FirstNonDom = Current;
2519 break;
2520 }
2521 }
2522 }
2523
2524 auto *NewDef =
2525 FirstNonDom ? MSSAU->createMemoryAccessBefore(
2526 NewS, nullptr,
2527 const_cast<MemoryUseOrDef *>(FirstNonDom))
2528 : MSSAU->createMemoryAccessInBB(
2529 NewS, nullptr,
2530 NewS->getParent(), MemorySSA::BeforeTerminator);
2531
2532 MSSAU->insertDef(cast<MemoryDef>(NewDef), /*RenameUses=*/false);
2533 }
2534 }
2535 if (isAssumeWithEmptyBundle(*IntrinsicI)) {
2536 salvageAndRemoveInstruction(IntrinsicI);
2537 return true;
2538 }
2539 return false;
2540 }
2541
2542 if (isa<Constant>(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(V->getContext());
2550 return propagateEquality(V, True, IntrinsicI);
2551}
2552
2555 I->replaceAllUsesWith(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.
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>(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(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>(U);
2585 if (!I || I == L || !DT.dominates(I, MostDominatingInstruction))
2586 continue;
2587
2588 // Add bitcasts and zero GEPs to queue.
2589 // TODO: Should drop bitcast?
2590 if (isa<BitCastInst>(I) ||
2592 cast<GetElementPtrInst>(I)->hasAllZeroIndices())) {
2593 PointerUsesQueue.push_back(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(LLVMContext::MD_invariant_group) &&
2601 Ptr == getLoadStorePointerOperand(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>
2614 const TargetLibraryInfo *TLI) {
2615 if (auto *LI = dyn_cast<LoadInst>(I))
2616 return MemoryLocation::get(LI);
2617
2618 if (auto *II = dyn_cast<IntrinsicInst>(I)) {
2619 switch (II->getIntrinsicID()) {
2620 case Intrinsic::masked_load:
2622 case Intrinsic::masked_store:
2623 if (AllowStores)
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>(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(Loc.Ptr, Candidate, AR.getOffset());
2653 else
2654 Choice = ReachingMemVal::getDef(Loc.Ptr, Candidate);
2655 return;
2656 }
2657 if (!MSSA.locallyDominates(MSSA.getMemoryAccess(Choice->Inst),
2658 MSSA.getMemoryAccess(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, Loc.Ptr);
2679
2680 auto *UseOrDef = dyn_cast<MemoryUseOrDef>(U);
2681 if (!UseOrDef || UseOrDef->getBlock() != BB)
2682 continue;
2683
2684 Instruction *MemI = UseOrDef->getMemoryInst();
2685 if (MemI == L ||
2686 (L && !MSSA.locallyDominates(UseOrDef, MSSA.getMemoryAccess(L))))
2687 continue;
2688
2689 if (auto MaybeLoc = maybeLoadStoreLocation(MemI, IsInvariantLoad, TLI)) {
2690 AliasResult AR = AA.alias(*MaybeLoc, Loc);
2691 // If the locations do not certainly alias, we cannot possibly infer the
2692 // following load loads the same value.
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(ClobberMA)) {
2726 if (Alloc->getParent() == BB)
2727 return ReachingMemVal::getDef(Loc.Ptr, const_cast<AllocaInst *>(Alloc));
2728 return ReachingMemVal::getUnknown(BB, 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>(I))
2737 return L->getOrdering();
2738 return cast<StoreInst>(I)->getOrdering();
2739 };
2740 Instruction *ClobberI = cast<MemoryDef>(ClobberMA)->getMemoryInst();
2741
2742 // Check if the clobbering access is a load or a store that we can reuse.
2743 if (auto MaybeLoc = maybeLoadStoreLocation(ClobberI, true, TLI)) {
2744 AliasResult AR = AA.alias(*MaybeLoc, Loc);
2745 if (AR == AliasResult::MustAlias)
2746 return ReachingMemVal::getDef(Loc.Ptr, 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(GetOrdering(ClobberI), AtomicOrdering::Monotonic) ||
2756 isa<StoreInst>(ClobberI))
2757 return std::nullopt;
2758 return ReachingMemVal::getClobber(Loc.Ptr, ClobberI);
2759 }
2760
2761 // Skip over volatile loads (the original load is non-volatile, non-atomic).
2762 if (auto *LI = dyn_cast<LoadInst>(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>(ClobberI))
2768 if (isStorePreservingMemoryLocation(SI, Loc, LoadAlign, AA,
2769 Opts->gvn_max_num_insns))
2770 return std::nullopt;
2771
2772 if (AR == AliasResult::MayAlias ||
2774 (!AR.hasOffset() || AR.getOffset() < 0)))
2775 return ReachingMemVal::getClobber(Loc.Ptr, ClobberI);
2776
2777 // The only option left is a store of the superset of the required bits.
2779 AR.getOffset() > 0 &&
2780 "Must be the superset/partial overlap case with positive offset");
2781 return ReachingMemVal::getClobber(Loc.Ptr, ClobberI, AR.getOffset());
2782 }
2783
2784 if (auto *II = dyn_cast<IntrinsicInst>(ClobberI)) {
2785 if (II->getIntrinsicID() == Intrinsic::lifetime_start) {
2786 MemoryLocation IIObjLoc = MemoryLocation::getForArgument(II, 0, TLI);
2787 if (AA.isMustAlias(IIObjLoc, Loc))
2788 return ReachingMemVal::getDef(Loc.Ptr, 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(ClobberI)) {
2796 const Value *Obj = getUnderlyingObject(Loc.Ptr);
2797 if (Obj == ClobberI || AA.isMustAlias(ClobberI, Loc.Ptr))
2798 return ReachingMemVal::getDef(Loc.Ptr, ClobberI);
2799 }
2800
2801 // Can reorder loads across a release fence.
2802 if (auto *FI = dyn_cast<FenceInst>(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(ClobberI, 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(Loc.Ptr, 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,
2826 if (Addr.needsPHITranslationFromBlock(BB) &&
2828 return false;
2829
2830 auto *MPhi =
2831 ClobberMA->getBlock() == BB ? dyn_cast<MemoryPhi>(ClobberMA) : nullptr;
2833 for (BasicBlock *Pred : predecessors(BB)) {
2834 // Skip unreachable predecessors.
2835 if (!DT->isReachableFromEntry(Pred))
2836 continue;
2837
2838 // Skip already visited predecessors.
2839 if (llvm::any_of(Preds, [Pred](const auto &P) { return P.first == Pred; }))
2840 continue;
2841
2842 PHITransAddr TransAddr = Addr;
2843 if (TransAddr.needsPHITranslationFromBlock(BB))
2844 TransAddr.translateValue(BB, Pred, DT, false);
2845
2846 auto It = Blocks.find(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 Pred, DependencyBlockInfo(TransAddr,
2859 MPhi ? MPhi->getIncomingValueForBlock(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(P.first, std::move(P.second)).first;
2869 Worklist.push_back(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(MA);
2891 MA = cast<MemoryUseOrDef>(MA)->getDefiningAccess();
2892 }
2893 Clobbers.push_back(MA);
2894
2895 if (MSSA.isLiveOnEntryDef(MA) ||
2896 (MA->getBlock() == BB && !isa<MemoryPhi>(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(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(
2932 AAResults &AAR) {
2933 BatchAAResults AA(AAR, EA);
2934 BasicBlock *StartBlock = L->getParent();
2935 bool IsInvariantLoad = L->hasMetadata(LLVMContext::MD_invariant_load);
2936 // TODO: Simplify later work by just getClobberingMemoryAccess().
2937 MemoryAccess *ClobberMA = MSSA.getMemoryAccess(L)->getDefiningAccess();
2938 const MemoryLocation Loc = MemoryLocation::get(L);
2939
2940 // Fast path for load tagged with !invariant.group.
2941 if (L->hasMetadata(LLVMContext::MD_invariant_group)) {
2942 if (Instruction *G = findInvariantGroupValue(L, *DT)) {
2943 Values.emplace_back(
2944 ReachingMemVal::getDef(getLoadStorePointerOperand(G), 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, StartBlock,
2956 SmallVector<MemoryAccess *, 1>{ClobberMA}, MSSA, AA, L)) {
2957 Values.emplace_back(*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>(ClobberMA))
2964 break;
2965
2966 // Check if the clobber actually aliases the load location.
2967 if (auto RMV =
2968 accessMayModifyLocation(ClobberMA, Loc, L->getAlign(),
2969 IsInvariantLoad, StartBlock, MSSA, AA)) {
2970 Values.emplace_back(*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>(ClobberMA)->getDefiningAccess();
2977 }
2978
2979 // Non-local speculations are not allowed under ASan.
2980 if (L->getFunction()->hasFnAttribute(Attribute::SanitizeAddress) ||
2981 L->getFunction()->hasFnAttribute(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(StartBlock,
2994 PHITransAddr(L->getPointerOperand(), DL, AC),
2995 ClobberMA, Blocks, 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(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>(Info.ClobberMA)) {
3016 const MemoryLocation BBLoc = Loc.getWithNewPtr(Info.Addr.getAddr());
3017 if (auto RMV =
3018 accessMayModifyLocation(Info.ClobberMA, BBLoc, 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>(Info.ClobberMA)->getDefiningAccess();
3031 Worklist.emplace_back(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, Info.Addr, 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(BB)->second;
3059 Info.Visited = true;
3060 }
3061
3063 while (!Worklist.empty()) {
3064 auto *BB = Worklist.pop_back_val();
3065 DependencyBlockInfo &Info = Blocks.find(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(ReachingMemVal::getUnknown(BB, nullptr));
3071 continue;
3072 }
3073
3074 Clobbers.clear();
3075 collectClobberList(Clobbers, BB, Info, Blocks, MSSA);
3076 if (auto RMV =
3077 scanMemoryAccessesUsers(Loc.getWithNewPtr(Info.Addr.getAddr()),
3078 IsInvariantLoad, BB, Clobbers, MSSA, AA)) {
3079 Values.push_back(*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(*Info.MemVal);
3087 continue;
3088 }
3089
3090 if (Info.ForceUnknown) {
3091 Values.push_back(ReachingMemVal::getUnknown(BB, 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(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(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()) {
3126 return true;
3127 }
3128
3129 ReachingMemVal MemVal = ReachingMemVal::getUnknown(nullptr, nullptr);
3130 if (!isMemorySSAEnabled()) {
3131 // ... to a pointer that has been loaded from before...
3132 MemDepResult Dep = MD->getDependency(L);
3133
3134 // If it is defined in another block, try harder.
3135 if (Dep.isNonLocal())
3136 return processNonLocalLoad(L);
3137
3138 // Only handle the local case below.
3139 if (Dep.isDef())
3140 MemVal = ReachingMemVal::getDef(L->getPointerOperand(), Dep.getInst());
3141 else if (Dep.isClobber())
3142 MemVal =
3143 ReachingMemVal::getClobber(L->getPointerOperand(), Dep.getInst());
3144 } else {
3146 if (!findReachingValuesForLoad(L, MemVals, *MSSAU->getMemorySSA(), *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(L, 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(L, MemVal, L->getPointerOperand());
3165 if (!AV)
3166 return false;
3167
3169
3170 // MaterializeAdjustedValue is responsible for combining metadata.
3171 ICF->removeUsersOf(L);
3172 L->replaceAllUsesWith(AvailableValue);
3173 if (MSSAU)
3174 MSSAU->removeMemoryAccess(L);
3175 ++NumGVNLoad;
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(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(I, 0, TLI);
3191
3192 if (!isMemorySSAEnabled()) {
3193 if (!MD)
3194 return false;
3195 MemDepResult Dep = MD->getDependency(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 MSSA->getWalker()->getClobberingMemoryAccess(I, 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(Def) ||
3206 Def->getBlock() != I->getParent())
3207 return false;
3208 DepInst = Def->getMemoryInst();
3209 }
3210
3211 Value *Mask = I->getOperand(1);
3212 Value *Passthrough = I->getOperand(2);
3213 Value *StoreVal;
3214 if (!match(DepInst,
3215 m_MaskedStore(m_Value(StoreVal), m_Value(), m_Specific(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 =
3223 if (!BatchAA.isMustAlias(StoreLoc, LoadLoc))
3224 return false;
3225 }
3226
3227 // Remove the load but generate a select for the passthrough
3228 Value *OpToForward = llvm::SelectInst::Create(Mask, StoreVal, Passthrough, "",
3229 I->getIterator());
3230
3231 ICF->removeUsersOf(I);
3232 I->replaceAllUsesWith(OpToForward);
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(Exp);
3245 if (ExprIdx.size() < NextValueNumber + 1)
3246 ExprIdx.resize(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 LeaderTable.getLeaders(Num),
3259 [=](const GVNLeaderMap::LeaderTableEntry &L) { return L.BB == BB; });
3260}
3261
3262/// Wrap phiTranslateImpl to provide caching functionality.
3264 const BasicBlock *PhiBlock, uint32_t Num,
3265 GVNLeaderMap &LeaderTable) {
3266 auto FindRes = PhiTranslateTable.find({Num, Pred});
3267 if (FindRes != PhiTranslateTable.end())
3268 return FindRes->second;
3269 uint32_t NewNum = phiTranslateImpl(Pred, PhiBlock, Num, LeaderTable);
3270 PhiTranslateTable.insert({{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(Num);
3282 for (const auto &Entry : Leaders) {
3283 Call = dyn_cast<CallInst>(&*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(Call);
3295 if (!LocalDep.isNonLocal())
3296 return false;
3297
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) != Pred)
3322 continue;
3323 if (uint32_t TransVal = lookup(PN->getIncomingValue(I), 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) != Pred)
3339 continue;
3340 MemoryAccess *MA = MPhi->getIncomingValue(i);
3341 if (auto *PredPhi = dyn_cast<MemoryPhi>(MA))
3342 return lookupOrAdd(PredPhi->getBlock());
3343 if (MSSA->isLiveOnEntryDef(MA))
3344 return lookupOrAdd(&BB->getParent()->getEntryBlock());
3345 return lookupOrAdd(cast<MemoryUseOrDef>(MA)->getMemoryInst());
3346 }
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, 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, 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(Exp.VarArgs[0], Exp.VarArgs[1]);
3376 uint32_t Opcode = Exp.Opcode >> 8;
3377 if (Opcode == Instruction::ICmp || Opcode == Instruction::FCmp)
3378 Exp.Opcode = (Opcode << 8) |
3380 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.
3396 const BasicBlock &CurrBlock) {
3397 for (const BasicBlock *Pred : predecessors(&CurrBlock))
3398 PhiTranslateTable.erase({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(Num);
3408 if (Leaders.empty())
3409 return nullptr;
3410
3411 Value *Val = nullptr;
3412 for (const auto &Entry : Leaders) {
3413 if (DT->dominates(Entry.BB, 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'.
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) {
3457 SmallDenseSet<std::pair<Value *, Value *>, 4> Visited;
3458 Worklist.push_back(std::make_pair(LHS, RHS));
3459 bool Changed = false;
3460 SmallVector<const BasicBlock *> DominatedBlocks;
3461 if (const BasicBlockEdge *Edge = std::get_if<BasicBlockEdge>(&Root)) {
3462 // For speed, compute a conservative fast approximation to
3463 // DT->dominates(Root, Root.getEnd());
3465 DominatedBlocks.push_back(Edge->getEnd());
3466 } else {
3467 Instruction *I = std::get<Instruction *>(Root);
3468 for (const auto *Node : DT->getNode(I->getParent())->children())
3469 DominatedBlocks.push_back(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.
3482 continue;
3483
3484 // Prefer a constant on the right-hand side, or an Argument if no constants.
3486 std::swap(LHS, RHS);
3487 assert((isa<Argument>(LHS) || isa<Instruction>(LHS)) && "Unexpected value!");
3488 const DataLayout &DL =
3490 ? cast<Argument>(LHS)->getParent()->getDataLayout()
3491 : cast<Instruction>(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(LHS);
3498 if ((isa<Argument>(LHS) && isa<Argument>(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(RHS);
3503 if (LVN < RVN) {
3504 std::swap(LHS, RHS);
3505 LVN = RVN;
3506 }
3507 }
3508
3509 if (!Visited.insert({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.
3522 for (const BasicBlock *BB : DominatedBlocks)
3523 LeaderTable.insert(LVN, 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>(&Root))
3535 NumReplacements = replaceDominatedUsesWithIf(
3536 LHS, RHS, *DT, *Edge, CanReplacePointersCallBack);
3537 else
3538 NumReplacements = replaceDominatedUsesWithIf(
3539 LHS, RHS, *DT, std::get<Instruction *>(Root),
3540 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(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(1))
3556 // Not a boolean equality - bail out.
3557 continue;
3558 ConstantInt *CI = dyn_cast<ConstantInt>(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(LHS, m_LogicalAnd(m_Value(A), m_Value(B)))) ||
3570 (IsKnownFalse && match(LHS, m_LogicalOr(m_Value(A), m_Value(B))))) {
3571 Worklist.push_back(std::make_pair(A, RHS));
3572 Worklist.push_back(std::make_pair(B, 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>(LHS)) {
3580 Value *Op0 = Cmp->getOperand(0), *Op1 = Cmp->getOperand(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(IsKnownFalse))
3586 Worklist.push_back(std::make_pair(Op0, 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(Cmp->getType(), 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(Cmp->getOpcode(), NotPred, Op0, 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(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>(&Root)) {
3605 if (!DT->dominates(Entry.BB, Edge->getStart()) &&
3606 !DT->dominates(Edge->getEnd(), Entry.BB))
3607 continue;
3608 } else {
3609 auto *InstBB = std::get<Instruction *>(Root)->getParent();
3610 if (!DT->dominates(Entry.BB, InstBB) &&
3611 !DT->dominates(InstBB, Entry.BB))
3612 continue;
3613 }
3614
3615 Value *NotCmp = Entry.Val;
3616 if (NotCmp && isa<Instruction>(NotCmp)) {
3617 unsigned NumReplacements;
3618 if (const BasicBlockEdge *Edge = std::get_if<BasicBlockEdge>(&Root))
3619 NumReplacements =
3620 replaceDominatedUsesWith(NotCmp, NotVal, *DT, *Edge);
3621 else
3622 NumReplacements = replaceDominatedUsesWith(
3623 NotCmp, NotVal, *DT, std::get<Instruction *>(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(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(Num, 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(LHS, m_NUWTrunc(m_Value(A)))) {
3646 Worklist.emplace_back(A, ConstantInt::get(A->getType(), IsKnownTrue));
3647 continue;
3648 }
3649
3650 if (match(LHS, m_Not(m_Value(A)))) {
3651 Worklist.emplace_back(A, ConstantInt::get(A->getType(), !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(Cmp->getOpcode(), Pred, Cmp->getOperand(0),
3662 Cmp->getOperand(1));
3663 if (Num != 0)
3664 return findLeader(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(Cmp, Repl);
3671 BinaryOperator *Not = BinaryOperator::CreateNot(
3672 Repl, Repl->getName() + ".not", Cmp->getIterator());
3673 Not->setDebugLoc(Cmp->getDebugLoc());
3674 Cmp->replaceAllUsesWith(Not);
3676 return true;
3677 }
3678
3679 // Substitute icmp samesign upred with icmp spred
3680 auto *ICmp = dyn_cast<ICmpInst>(Cmp);
3681 if (ICmp && ICmp->hasSameSign() && !ICmp->isEquality()) {
3682 if (Value *Repl = FindCmpLeader(
3683 ICmpInst::getFlippedSignednessPredicate(ICmp->getPredicate()))) {
3684 patchAndReplaceAllUsesWith(Cmp, Repl);
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, {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(I);
3706 I->replaceAllUsesWith(V);
3707 Changed = true;
3708 }
3709 if (isInstructionTriviallyDead(I, TLI)) {
3711 Changed = true;
3712 }
3713 if (Changed) {
3714 if (MD && V->getType()->isPtrOrPtrVectorTy())
3715 MD->invalidateCachedPointerInfo(V);
3716 ++NumGVNSimpl;
3717 return true;
3718 }
3719 }
3720
3721 if (auto *Assume = dyn_cast<AssumeInst>(I))
3722 return processAssumeIntrinsic(Assume);
3723
3724 if (LoadInst *Load = dyn_cast<LoadInst>(I)) {
3725 if (processLoad(Load))
3726 return true;
3727
3728 unsigned Num = VN.lookupOrAdd(Load);
3729 LeaderTable.insert(Num, Load, Load->getParent());
3730 return false;
3731 }
3732
3734 processMaskedLoad(cast<IntrinsicInst>(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>(I)) {
3740 if (isa<Constant>(BI->getCondition()))
3741 return processFoldableCondBr(BI);
3742
3743 Value *BranchCond = BI->getCondition();
3744 BasicBlock *TrueSucc = BI->getSuccessor(0);
3745 BasicBlock *FalseSucc = BI->getSuccessor(1);
3746 // Avoid multiple edges early.
3747 if (TrueSucc == FalseSucc)
3748 return false;
3749
3750 BasicBlock *Parent = BI->getParent();
3751 bool Changed = false;
3752
3754 BasicBlockEdge TrueE(Parent, TrueSucc);
3755 Changed |= propagateEquality(BranchCond, TrueVal, TrueE);
3756
3758 BasicBlockEdge FalseE(Parent, FalseSucc);
3759 Changed |= propagateEquality(BranchCond, FalseVal, 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>(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(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(Dst) == 1) {
3779 BasicBlockEdge E(Parent, Dst);
3780 Changed |= propagateEquality(SwitchCond, Case.getCaseValue(), 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(I);
3793
3794 // Allocations are always uniquely numbered, so we can save time and memory
3795 // by fast failing them.
3796 if (isa<AllocaInst>(I) || I->isTerminator() || isa<PHINode>(I)) {
3797 LeaderTable.insert(Num, I, 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>(I)) {
3804 const DataLayout &DL = I->getDataLayout();
3805 unsigned AS = PTA->getPointerAddressSpace();
3806 if (DL.getAddressSizeInBits(AS) == DL.getPointerSizeInBits(AS) &&
3807 !DL.hasUnstableRepresentation(AS)) {
3808 uint32_t PTINum =
3809 VN.lookupPtrToInt(PTA->getPointerOperand(), PTA->getType());
3810 if (Value *PTI = findLeader(I->getParent(), PTINum)) {
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(I->getParent(), Num) : nullptr;
3823 if (!Repl) {
3824 if (auto *Cmp = dyn_cast<CmpInst>(I); Cmp && replaceWithEquivalentCmp(Cmp))
3825 return true;
3826
3827 // Failure, just remember this instance for future use.
3828 LeaderTable.insert(Num, I, 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!
3840 if (MD && Repl->getType()->isPtrOrPtrVectorTy())
3841 MD->invalidateCachedPointerInfo(Repl);
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,
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("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(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(MSSA, 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(F)) {
3887 bool RemovedBlock = MergeBlockIntoPredecessor(&BB, &DTU, &LI, MSSAU, 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(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, PHINodesToRemove);
3946 for (PHINode *PN : PHINodesToRemove) {
3947 removeInstruction(PN);
3948 }
3949 for (Instruction &Inst : make_early_inc_range(*BB))
3950 ChangedFunction |= processInstruction(&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);
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(Op)) {
3972 Success = false;
3973 break;
3974 }
3975 uint32_t TValNo = VN.phiTranslate(Pred, Curr, VN.lookup(Op), LeaderTable);
3976 if (Value *V = findLeader(Pred, TValNo)) {
3977 Instr->setOperand(I, 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(Pred->getTerminator()->getIterator());
3991 Instr->setName(Instr->getName() + ".pre");
3992 Instr->setDebugLoc(Instr->getDebugLoc());
3993
3994 ICF->insertInstructionTo(Instr, Pred);
3995
3996 unsigned Num = VN.lookupOrAdd(Instr);
3997 VN.add(Instr, Num);
3998
3999 // Update the availability map to include the new instruction.
4000 LeaderTable.insert(Num, Instr, Pred);
4001 return true;
4002}
4003
4004bool GVNPassImpl::performScalarPRE(Instruction *CurInst) {
4005 if (isa<AllocaInst>(CurInst) || CurInst->isTerminator() ||
4006 isa<PHINode>(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>(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>(CurInst))
4026 return false;
4027
4028 if (auto *CallB = dyn_cast<CallBase>(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(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(*CurrentBlock->getParent());
4050
4052 for (BasicBlock *P : predecessors(CurrentBlock)) {
4053 // We're not interested in PRE where blocks with predecessors that are
4054 // not reachable.
4055 if (!DT->isReachableFromEntry(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(P, CurrentBlock, ValNo, LeaderTable);
4068 Value *PredV = findLeader(P, TValNo);
4069 if (!PredV) {
4070 PredMap.push_back(std::make_pair(static_cast<Value *>(nullptr), 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(std::make_pair(PredV, 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(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(CurInst))
4100 return false;
4101 }
4102
4103 // Don't do PRE across indirect branch.
4104 if (isa<IndirectBrInst>(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(PREPred, CurrentBlock);
4111 if (isCriticalEdge(PREPred->getTerminator(), SuccNum)) {
4112 ToSplit.push_back(std::make_pair(PREPred->getTerminator(), 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(PREInstr, PREPred, 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(CurInst->getType(), PredMap.size(),
4135 CurInst->getName() + ".pre-phi");
4136 Phi->insertBefore(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.
4142 Phi->addIncoming(V, BB);
4143 } else
4144 Phi->addIncoming(PREInstr, PREPred);
4145 }
4146
4147 VN.add(Phi, 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(ValNo, *CurrentBlock);
4151 LeaderTable.insert(ValNo, Phi, CurrentBlock);
4152 Phi->setDebugLoc(CurInst->getDebugLoc());
4153 CurInst->replaceAllUsesWith(Phi);
4154 if (MD && Phi->getType()->isPtrOrPtrVectorTy())
4155 MD->invalidateCachedPointerInfo(Phi);
4156 LeaderTable.erase(ValNo, CurInst, CurrentBlock);
4157
4158 LLVM_DEBUG(dbgs() << "GVN PRE removed: " << *CurInst << '\n');
4159 removeInstruction(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(&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.
4198 Pred, Succ,
4199 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(Edge.first, Edge.second,
4218 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(I);
4256 if (MD) MD->removeInstruction(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(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(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) {
4281 SmallSetVector<BasicBlock *, 4> DF;
4282
4283 NewDead.push_back(BB);
4284 while (!NewDead.empty()) {
4285 BasicBlock *D = NewDead.pop_back_val();
4286 if (DeadBlocks.count(D))
4287 continue;
4288
4289 // All blocks dominated by D are dead.
4290 SmallVector<BasicBlock *, 8> Dom;
4291 DT->getDescendants(D, Dom);
4292 DeadBlocks.insert_range(Dom);
4293
4294 // Figure out the dominance-frontier(D).
4295 for (BasicBlock *B : Dom) {
4296 for (BasicBlock *S : successors(B)) {
4297 if (DeadBlocks.count(S))
4298 continue;
4299
4300 bool AllPredDead = true;
4301 for (BasicBlock *P : predecessors(S))
4302 if (!DeadBlocks.count(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(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(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(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.
4330 for (BasicBlock *P : Preds) {
4331 if (!DeadBlocks.count(P))
4332 continue;
4333
4334 if (is_contained(successors(P), B) &&
4335 isCriticalEdge(P->getTerminator(), B)) {
4336 if (BasicBlock *S = splitCriticalEdges(P, B))
4337 DeadBlocks.insert(P = S);
4338 }
4339 }
4340
4341 // Now poison the incoming values from the dead predecessors.
4342 for (BasicBlock *P : predecessors(B)) {
4343 if (!DeadBlocks.count(P))
4344 continue;
4345 for (PHINode &Phi : B->phis()) {
4346 Phi.setIncomingValueForBlock(P, PoisonValue::get(Phi.getType()));
4347 if (MD)
4348 MD->invalidateCachedPointerInfo(&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(0) == BI->getSuccessor(1))
4370 return false;
4371
4372 ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
4373 if (!Cond)
4374 return false;
4375
4376 BasicBlock *DeadRoot =
4377 Cond->getZExtValue() ? BI->getSuccessor(1) : BI->getSuccessor(0);
4378 if (DeadBlocks.count(DeadRoot))
4379 return false;
4380
4381 if (!DeadRoot->getSinglePredecessor())
4382 DeadRoot = splitCriticalEdges(BI->getParent(), DeadRoot);
4383
4384 addDeadBlock(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(&Inst);
4396 LeaderTable.insert(ValNum, &Inst, BB);
4397 }
4398 }
4399}
4400
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)) {
4411 }
4412
4413 bool runOnFunction(Function &F) override {
4414 if (skipFunction(F))
4415 return false;
4416
4417 Impl.Opts = &getScalarOptions(F);
4419 return Impl.run(
4420 F, getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F),
4423 getAnalysis<AAResultsWrapperPass>().getAAResults(),
4425 getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
4427 MSSAWP ? &MSSAWP->getMSSA() : nullptr);
4428 }
4429
4444
4445private:
4446 GVNPassImpl Impl;
4447};
4448
4449char GVNLegacyPass::ID = 0;
4450
4451INITIALIZE_PASS_BEGIN(GVNLegacyPass, "gvn", "Global Value Numbering", false, false)
4459INITIALIZE_PASS_END(GVNLegacyPass, "gvn", "Global Value Numbering", false, false)
4460
4461// The public interface to this file...
4464 return new GVNLegacyPass(ScalarPRE);
4465}
const TargetLowering & TLI
SDValue Pred
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Function Alias Analysis false
This file contains the simple types necessary to represent the attributes associated with functions a...
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_ABI
Definition Compiler.h:211
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static RegisterPass< DebugifyFunctionPass > DF("debugify-function", "Attach debug info to a function")
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
early cse Early CSE w MemorySSA
This file provides a data structure for mapping values and expressions to congruence class IDs.
static Value * findDominatingValue(const ScalarOptions &Opts, const MemoryLocation &Loc, Type *LoadTy, Instruction *From, AAResults *AA)
Definition GVN.cpp:1594
static void reportMayClobberedLoad(LoadInst *Load, Instruction *DepInst, const DominatorTree *DT, OptimizationRemarkEmitter *ORE)
Try to locate the three instruction involved in a missed load-elimination case that is due to an inte...
Definition GVN.cpp:1573
static Instruction * findInvariantGroupValue(LoadInst *L, DominatorTree &DT)
If a load has !invariant.group, try to find the most-dominating instruction with the same metadata an...
Definition GVN.cpp:2561
static void reportLoadElim(LoadInst *Load, Value *AvailableValue, OptimizationRemarkEmitter *ORE)
Definition GVN.cpp:2357
static const Instruction * findMayClobberedPtrAccess(LoadInst *Load, const DominatorTree *DT)
Definition GVN.cpp:1517
static std::optional< MemoryLocation > maybeLoadStoreLocation(Instruction *I, bool AllowStores, const TargetLibraryInfo *TLI)
Return the memory location accessed by the (masked) load/store instruction I, if the instruction coul...
Definition GVN.cpp:2613
GVNPassImpl::AvailableValue AvailableValue
Definition GVN.cpp:1366
static bool isOnlyReachableViaThisEdge(const BasicBlockEdge &E, DominatorTree *DT)
There is an edge from 'Src' to 'Dst'.
Definition GVN.cpp:3426
static bool isValueFullyAvailableInBlock(const ScalarOptions &Opts, BasicBlock *BB, DenseMap< BasicBlock *, AvailabilityState > &FullyAvailableBlocks)
Return true if we can prove that the value we're analyzing is fully available in the specified block.
Definition GVN.cpp:1251
static bool liesBetween(const Instruction *From, Instruction *Between, const Instruction *To, const DominatorTree *DT)
Assuming To can be reached from both From and Between, does Between lie on every path from From to To...
Definition GVN.cpp:1508
static bool isLifetimeStart(const Instruction *Inst)
Definition GVN.cpp:1500
static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl)
Definition GVN.cpp:2553
static void replaceValuesPerBlockEntry(SmallVectorImpl< AvailableValueInBlock > &ValuesPerBlock, Value *OldValue, Value *NewValue)
If the specified OldValue exists in ValuesPerBlock, replace its value with NewValue.
Definition GVN.cpp:1371
GVNPassImpl::AvailableValueInBlock AvailableValueInBlock
Definition GVN.cpp:1367
AvailabilityState
Definition GVN.cpp:1231
@ Unavailable
We know the block is not fully available. This is a fixpoint.
Definition GVN.cpp:1233
@ Available
We know the block is fully available. This is a fixpoint.
Definition GVN.cpp:1235
@ SpeculativelyAvailable
We do not know whether the block is fully available or not, but we are currently speculating that it ...
Definition GVN.cpp:1240
static Value * constructSSAForLoadSet(LoadInst *Load, SmallVectorImpl< AvailableValueInBlock > &ValuesPerBlock, DominatorTree &DT)
Given a set of loads specified by ValuesPerBlock, construct SSA form, allowing us to eliminate Load.
Definition GVN.cpp:1390
This file provides the interface for LLVM's Global Value Numbering pass which eliminates fully redund...
#define DEBUG_TYPE
This is the interface for a simple mod/ref and alias analysis over globals.
Hexagon Common GEP
#define _
IRTranslator LLVM IR MI
Module.h This file contains the declarations for the Module class.
This header defines various interfaces for pass management in LLVM.
This defines the Use class.
static LVOptions Options
Definition LVOptions.cpp:25
#define F(x, y, z)
Definition MD5.cpp:54
#define I(x, y, z)
Definition MD5.cpp:57
#define G(x, y, z)
Definition MD5.cpp:55
This file implements a map that provides insertion order iteration.
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
This file contains the declarations for metadata subclasses.
uint64_t IntrinsicInst * II
#define P(N)
ppc ctr loops PowerPC CTR Loops Verify
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
This file contains the declarations for profiling metadata utility functions.
SmallVector< MachineOperand, 4 > Cond
static DominatorTree getDomTree(Function &F)
std::pair< BasicBlock *, BasicBlock * > Edge
This file contains some templates that are useful if you are working with the STL at all.
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition Statistic.h:171
#define LLVM_DEBUG(...)
Definition Debug.h:119
Value * RHS
Value * LHS
static const uint32_t IV[8]
Definition blake3_impl.h:83
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition GVN.cpp:4430
static char ID
Definition GVN.cpp:4403
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition GVN.cpp:4413
GVNLegacyPass(bool ScalarPRE=true)
Definition GVN.cpp:4406
A manager for alias analyses.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
@ MayAlias
The two locations may or may not alias.
@ NoAlias
The two locations do not alias at all.
@ PartialAlias
The two locations alias, but only due to a partial overlap.
@ MustAlias
The two locations precisely alias each other.
constexpr int32_t getOffset() const
constexpr bool hasOffset() const
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
iterator end() const
Definition ArrayRef.h:130
iterator begin() const
Definition ArrayRef.h:129
Value handle that asserts if the Value is deleted.
This represents the llvm.assume intrinsic.
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition BasicBlock.h:62
const Function * getParent() const
Return the enclosing method, or null if none.
Definition BasicBlock.h:213
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
InstListType::iterator iterator
Instruction iterators...
Definition BasicBlock.h:170
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition BasicBlock.h:683
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
Definition BasicBlock.h:237
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
LLVM_ABI Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
static LLVM_ABI BinaryOperator * CreateNot(Value *Op, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Value * getArgOperand(unsigned i) const
unsigned arg_size() const
This class represents a function call, abstracting a target machine's calling convention.
This class is the base class for the comparison instructions.
Definition InstrTypes.h:728
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition InstrTypes.h:740
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition InstrTypes.h:890
Conditional Branch instruction.
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
Definition Constants.h:231
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A parsed version of the target data layout string in and methods for querying it.
Definition DataLayout.h:64
iterator find(const_arg_type_t< KeyT > Val)
Definition DenseMap.h:766
iterator end()
Definition DenseMap.h:686
ValueT lookup(const_arg_type_t< KeyT > Val) const
Return the entry for the specified key, or a default constructed value if no such entry exists.
Definition DenseMap.h:793
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
Definition DenseMap.h:856
Analysis pass which computes a DominatorTree.
Definition Dominators.h:241
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Legacy analysis pass which computes a DominatorTree.
Definition Dominators.h:277
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition Dominators.h:122
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Context-sensitive CaptureAnalysis provider, which computes and caches the earliest common dominator c...
Class representing an expression and its matching format.
This instruction extracts a struct member or array element value from an aggregate value.
unsigned getNumIndices() const
iterator_range< idx_iterator > indices() const
idx_iterator idx_begin() const
FunctionPass class - This class is used to implement most global optimizations.
Definition Pass.h:312
FunctionPass(char &pid)
Definition Pass.h:314
bool skipFunction(const Function &F) const
Optional passes call this function to check whether the pass should be skipped.
Definition Pass.cpp:197
const BasicBlock & getEntryBlock() const
Definition Function.h:803
Represents calls to the gc.relocate intrinsic.
leader_iterator & operator++()
Definition GVN.cpp:193
bool operator!=(const leader_iterator &Other) const
Definition GVN.cpp:201
leader_iterator(const LeaderListNode *C)
Definition GVN.cpp:192
reference operator*() const
Definition GVN.cpp:204
const LeaderTableEntry value_type
Definition GVN.cpp:187
std::forward_iterator_tag iterator_category
Definition GVN.cpp:186
bool operator==(const leader_iterator &Other) const
Definition GVN.cpp:198
A mapping from value numbers to lists of Value*'s that have that value number.
Definition GVN.cpp:160
LLVM_ABI void insert(uint32_t N, Value *V, const BasicBlock *BB)
Push a new Value to the LeaderTable onto the list for its value number.
Definition GVN.cpp:1077
LLVM_ABI void erase(uint32_t N, Instruction *I, const BasicBlock *BB)
Scan the list of values corresponding to a given value number, and remove the given instruction if en...
Definition GVN.cpp:1089
iterator_range< leader_iterator > getLeaders(uint32_t N)
Definition GVN.cpp:207
The core GVN pass object.
Definition GVN.cpp:242
bool isMemDepEnabled() const
Definition GVN.cpp:1148
bool isScalarPREEnabled() const
Definition GVN.cpp:1131
friend class GVNPass
Definition GVN.cpp:268
bool isLoadPRESplitBackedgeEnabled() const
Definition GVN.cpp:1143
MemoryDependenceResults & getMemDep() const
Definition GVN.cpp:258
AAResults * getAliasAnalysis() const
Definition GVN.cpp:257
void salvageAndRemoveInstruction(Instruction *I)
This removes the specified instruction from our various maps and marks it for deletion.
Definition GVN.cpp:1204
bool isLoadInLoopPREEnabled() const
Definition GVN.cpp:1139
bool isLoadPREEnabled() const
Definition GVN.cpp:1135
bool isMemorySSAEnabled() const
Definition GVN.cpp:1157
DominatorTree & getDominatorTree() const
Definition GVN.cpp:256
GVNPassImpl(llvm::GVNOptions Options={})
Definition GVN.cpp:250
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition GVN.cpp:1170
LLVM_ABI GVNPass(GVNOptions Options={})
Definition GVN.cpp:1161
LLVM_ABI void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition GVN.cpp:1210
LLVM_ABI ~GVNPass()
This class holds the mapping between values and value numbers.
LLVM_ABI uint32_t lookupOrAddCmp(unsigned Opcode, CmpInst::Predicate Pred, Value *LHS, Value *RHS)
Returns the value number of the given comparison, assigning it a new number if it did not have one be...
Definition GVN.cpp:1020
LLVM_ABI void erase(Value *V)
Remove a value from the value numbering.
Definition GVN.cpp:1055
LLVM_ABI uint32_t lookup(Value *V, bool Verify=true) const
Returns the value number of the specified value.
Definition GVN.cpp:1007
LLVM_ABI void add(Value *V, uint32_t Num)
add - Insert a value into the table with a specified value number.
Definition GVN.cpp:726
LLVM_ABI void eraseTranslateCacheEntry(uint32_t Num, const BasicBlock &CurrBlock)
Erase stale entry from phiTranslate cache so phiTranslate can be computed again.
Definition GVN.cpp:3395
LLVM_ABI void verifyRemoved(const Value *) const
verifyRemoved - Verify that the value is removed from all internal data structures.
Definition GVN.cpp:1067
LLVM_ABI uint32_t phiTranslate(const BasicBlock *BB, const BasicBlock *PhiBlock, uint32_t Num, GVNLeaderMap &LeaderTable)
Wrap phiTranslateImpl to provide caching functionality.
Definition GVN.cpp:3263
LLVM_ABI GVNValueTable()
LLVM_ABI uint32_t lookupCmp(unsigned Opcode, CmpInst::Predicate Pred, Value *LHS, Value *RHS)
Definition GVN.cpp:1027
LLVM_ABI uint32_t lookupOrAdd(MemoryAccess *MA)
Definition GVN.cpp:909
LLVM_ABI void clear()
Remove all entries from the ValueTable.
Definition GVN.cpp:1042
LLVM_ABI bool exists(Value *V) const
Returns true if a value number exists for the specified value.
Definition GVN.cpp:905
LLVM_ABI GVNValueTable & operator=(const GVNValueTable &Arg)
LLVM_ABI uint32_t lookupPtrToInt(Value *Ptr, Type *Ty)
Returns the value number of ptrtoint Ptr to \Ty.
Definition GVN.cpp:1034
LLVM_ABI ~GVNValueTable()
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Legacy wrapper pass to provide the GlobalsAAResult object.
Predicate getFlippedSignednessPredicate() const
For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->EQ.
This class allows to keep track on instructions with implicit control flow.
LLVM_ABI Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
LLVM_ABI bool mayWriteToMemory() const LLVM_READONLY
Return true if this instruction may modify memory.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
bool hasMetadata() const
Return true if this instruction has any metadata attached to it.
LLVM_ABI bool isAtomic() const LLVM_READONLY
Return true if this instruction has an AtomicOrdering of unordered or higher.
LLVM_ABI bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
LLVM_ABI bool mayReadFromMemory() const LLVM_READONLY
Return true if this instruction may read memory.
LLVM_ABI void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs={})
Drop all unknown metadata except for debug locations.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
LLVM_ABI bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
A wrapper class for inspecting calls to intrinsic functions.
An instruction for reading from memory.
Analysis pass that exposes the LoopInfo for a function.
Definition LoopInfo.h:598
The legacy pass manager's analysis pass to compute loop information.
Definition LoopInfo.h:623
This class implements a map that also provides access to all stored values in a deterministic order.
Definition MapVector.h:39
iterator find(const KeyT &Key)
Definition MapVector.h:157
iterator end()
Definition MapVector.h:70
size_type size() const
Definition MapVector.h:59
A memory dependence query can return one of three different answers.
bool isClobber() const
Tests if this MemDepResult represents a query that is an instruction clobber dependency.
bool isNonLocal() const
Tests if this MemDepResult represents a query that is transparent to the start of the block,...
bool isDef() const
Tests if this MemDepResult represents a query that is an instruction definition dependency.
bool isLocal() const
Tests if this MemDepResult represents a valid local query (Clobber/Def).
Instruction * getInst() const
If this is a normal dependency, returns the instruction that is depended on.
This is the common base class for memset/memcpy/memmove.
BasicBlock * getBlock() const
Definition MemorySSA.h:164
An analysis that produces MemoryDependenceResults for a function.
Provides a lazy, caching interface for making common memory aliasing information queries,...
std::vector< NonLocalDepEntry > NonLocalDepInfo
LLVM_ABI MemDepResult getDependency(Instruction *QueryInst)
Returns the instruction on which a memory operation depends.
LLVM_ABI const NonLocalDepInfo & getNonLocalCallDependency(CallBase *QueryCall)
Perform a full dependency query for the specified call, returning the set of blocks that the value is...
A wrapper analysis pass for the legacy pass manager that exposes a MemoryDepnedenceResults instance.
Representation for a specific memory location.
static LLVM_ABI MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
MemoryLocation getWithNewPtr(const Value *NewPtr) const
const Value * Ptr
The address of the start of the location.
static LLVM_ABI MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition MemorySSA.h:523
BasicBlock * getIncomingBlock(unsigned I) const
Return incoming basic block number i.
Definition MemorySSA.h:536
MemoryAccess * getIncomingValue(unsigned I) const
Return incoming value number x.
Definition MemorySSA.h:526
An analysis that produces MemorySSA for a function.
Definition MemorySSA.h:936
MemoryAccess * getClobberingMemoryAccess(const Instruction *I, BatchAAResults &AA)
Given a memory Mod/Ref/ModRef'ing instruction, calling this will give you the nearest dominating Memo...
Definition MemorySSA.h:1049
Legacy analysis pass which computes MemorySSA.
Definition MemorySSA.h:989
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition MemorySSA.h:689
LLVM_ABI MemorySSAWalker * getSkipSelfWalker()
LLVM_ABI void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
LLVM_ABI MemorySSAWalker * getWalker()
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition MemorySSA.h:707
LLVM_ABI bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in the same basic block, determine whether MemoryAccess A dominates MemoryA...
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
Definition MemorySSA.h:727
MemoryAccess * getDefiningAccess() const
Get the access that produces the memory state used by this Use.
Definition MemorySSA.h:262
This is an entry in the NonLocalDepInfo cache.
OptimizationRemarkEmitter legacy analysis pass.
The optimization diagnostic interface.
LLVM_ABI void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
Diagnostic information for missed-optimization remarks.
Diagnostic information for applied optimization remarks.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
PHITransAddr - An address value which tracks and handles phi translation.
LLVM_ABI Value * translateValue(BasicBlock *CurBB, BasicBlock *PredBB, const DominatorTree *DT, bool MustDominate)
translateValue - PHI translate the current address up the CFG from CurBB to Pred, updating our state ...
LLVM_ABI bool isPotentiallyPHITranslatable() const
isPotentiallyPHITranslatable - If this needs PHI translation, return true if we have some hope of doi...
bool needsPHITranslationFromBlock(BasicBlock *BB) const
needsPHITranslationFromBlock - Return true if moving from the specified BasicBlock to its predecessor...
Value * getAddr() const
static LLVM_ABI PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
AnalysisType * getAnalysisIfAvailable() const
getAnalysisIfAvailable<AnalysisType>() - Subclasses use this function to get analysis information tha...
static LLVM_ABI PointerType * get(LLVMContext &C, unsigned AddressSpace)
This constructs an opaque pointer to an object in a numbered address space.
Definition Type.cpp:882
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
PreservedAnalyses & preserve()
Mark an analysis as preserved.
Definition Analysis.h:133
Helper class for SSA formation on a set of values defined in multiple blocks.
Definition SSAUpdater.h:39
LLVM_ABI void Initialize(Type *Ty, StringRef Name)
Reset this object to get ready for a new set of SSA updates with type 'Ty'.
LLVM_ABI Value * GetValueInMiddleOfBlock(BasicBlock *BB)
Construct SSA form, materializing a value that is live in the middle of the specified block.
LLVM_ABI bool HasValueForBlock(BasicBlock *BB) const
Return true if the SSAUpdater already has a value for the specified block.
LLVM_ABI void AddAvailableValue(BasicBlock *BB, Value *V)
Indicate that a rewritten value is available in the specified block with the specified value.
std::pair< SelectInst *, SelectAddrs > getSelectAndAddrs() const
Value * getAddr() const
This class represents the LLVM 'select' instruction.
const Value * getFalseValue() const
const Value * getCondition() const
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", InsertPosition InsertBefore=nullptr, const Instruction *MDFrom=nullptr)
const Value * getTrueValue() const
A vector that has set insertion semantics.
Definition SetVector.h:57
bool erase(PtrType Ptr)
Remove pointer from the set.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Represent a constant reference to a string, i.e.
Definition StringRef.h:56
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition Type.h:46
LLVM_ABI bool isTokenLikeTy() const
Returns true if this is 'token' or a token-like target type.s.
Definition Type.cpp:1108
static LLVM_ABI IntegerType * getInt8Ty(LLVMContext &C)
Definition Type.cpp:292
bool isPtrOrPtrVectorTy() const
Return true if this is a pointer type or a vector of pointer types.
Definition Type.h:280
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition Type.h:252
bool isVoidTy() const
Return true if this is 'void'.
Definition Type.h:141
static LLVM_ABI UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
A Use represents the edge between a Value definition and its users.
Definition Use.h:35
op_range operands()
Definition User.h:267
LLVM Value Representation.
Definition Value.h:75
Type * getType() const
All values are typed, get the type of this value.
Definition Value.h:257
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition Value.h:441
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition Value.cpp:548
iterator_range< user_iterator > users()
Definition Value.h:428
bool hasUseList() const
Check if this Value has a use-list.
Definition Value.h:346
LLVM_ABI bool canBeFreed() const
Return true if the memory object referred to by V can by freed in the scope for which the SSA value d...
Definition Value.cpp:827
LLVM_ABI void deleteValue()
Delete a pointer to a generic Value.
Definition Value.cpp:103
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
Definition Value.cpp:314
std::pair< iterator, bool > insert(const ValueT &V)
Definition DenseSet.h:210
An efficient, type-erasing, non-owning reference to a callable.
An opaque object representing a hash code.
Definition Hashing.h:77
const ParentTy * getParent() const
Definition ilist_node.h:34
self_iterator getIterator()
Definition ilist_node.h:123
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
CallInst * Call
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Abstract Attribute helper functions.
Definition Attributor.h:166
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
@ Entry
Definition COFF.h:862
@ BasicBlock
Various leaf nodes.
Definition ISDOpcodes.h:83
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
auto m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
NoWrapTrunc_match< OpTy, TruncInst::NoUnsignedWrap > m_NUWTrunc(const OpTy &Op)
Matches trunc nuw.
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
auto m_MaskedStore(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2)
Matches MaskedStore Intrinsic.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
Not(const Pred &P) -> Not< Pred >
LLVM_ABI int analyzeLoadFromClobberingStore(Type *LoadTy, Value *LoadPtr, StoreInst *DepSI, const DataLayout &DL)
This function determines whether a value for the pointer LoadPtr can be extracted from the store at D...
LLVM_ABI Value * getMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset, Type *LoadTy, Instruction *InsertPt, const DataLayout &DL)
If analyzeLoadFromClobberingMemInst returned an offset, this function can be used to actually perform...
LLVM_ABI int analyzeLoadFromClobberingLoad(Type *LoadTy, Value *LoadPtr, LoadInst *DepLI, const DataLayout &DL)
This function determines whether a value for the pointer LoadPtr can be extracted from the load at De...
LLVM_ABI Value * getValueForLoad(Value *SrcVal, unsigned Offset, Type *LoadTy, Instruction *InsertPt, Function *F)
If analyzeLoadFromClobberingStore/Load returned an offset, this function can be used to actually perf...
LLVM_ABI int analyzeLoadFromClobberingMemInst(Type *LoadTy, Value *LoadPtr, MemIntrinsic *DepMI, const DataLayout &DL)
This function determines whether a value for the pointer LoadPtr can be extracted from the memory int...
LLVM_ABI bool canCoerceMustAliasedValueToLoad(Value *StoredVal, Type *LoadTy, Function *F)
Return true if CoerceAvailableValueToLoadType would succeed if it was called.
Add a small namespace to avoid name clashes with the classes used in the streaming interface.
NodeAddr< InstrNode * > Instr
Definition RDFGraph.h:389
NodeAddr< PhiNode * > Phi
Definition RDFGraph.h:390
NodeAddr< UseNode * > Use
Definition RDFGraph.h:385
NodeAddr< NodeBase * > Node
Definition RDFGraph.h:381
friend class Instruction
Iterator for Instructions in a `BasicBlock.
Definition BasicBlock.h:73
This is an optimization pass for GlobalISel generic memory operations.
@ Offset
Definition DWP.cpp:577
LLVM_ABI cl::opt< bool > ProfcheckDisableMetadataFixes
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1755
hash_code hash_value(const FixedPointSemantics &Val)
LLVM_ABI Constant * getInitialValueOfAllocation(const Value *V, const TargetLibraryInfo *TLI, Type *Ty)
If this is a call to an allocation function that initializes memory to a fixed value,...
LLVM_ABI unsigned replaceDominatedUsesWithIf(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge, function_ref< bool(const Use &U, const Value *To)> ShouldReplace)
Replace each use of 'From' with 'To' if that use is dominated by the given edge and the callback Shou...
Definition Local.cpp:3360
RelativeUniformCounterPtr Values
Definition InstrProf.h:91
LLVM_ABI unsigned GetSuccessorNumber(const BasicBlock *BB, const BasicBlock *Succ)
Search for the specified successor of basic block BB and return its position in the terminator instru...
Definition CFG.cpp:90
auto pred_end(const MachineBasicBlock *BB)
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
LLVM_ABI FunctionPass * createGVNPass(bool ScalarPRE)
Create a legacy GVN pass.
Definition GVN.cpp:4463
LLVM_ABI void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
Definition Utils.cpp:1837
auto successors(const MachineBasicBlock *BB)
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
@ Load
The value being inserted comes from a load (InsertElement only).
constexpr from_range_t from_range
LLVM_ABI bool isStorePreservingMemoryLocation(const StoreInst *SI, const MemoryLocation &MemLoc, Align MemLocAlign, BatchAAResults &AA, unsigned ScanLimit)
Check whether SI, which may alias MemLoc, can be safely skipped.
Definition Loads.cpp:845
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition STLExtras.h:2224
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition STLExtras.h:649
LLVM_ABI bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
LLVM_ABI bool isAssumeWithEmptyBundle(const AssumeInst &Assume)
Return true iff the operand bundles of the provided llvm.assume doesn't contain any valuable informat...
const ScalarOptions & getScalarOptions(const LLVMContext &C)
LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
Definition InstrProf.h:143
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1762
LLVM_ABI bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
Definition Local.cpp:408
LLVM_ABI bool canReplacePointersInUseIfEqual(const Use &U, const Value *To, const DataLayout &DL)
Definition Loads.cpp:926
LLVM_ABI bool canReplacePointersIfEqual(const Value *From, const Value *To, const DataLayout &DL)
Returns true if a pointer value From can be replaced with another pointer value \To if they are deeme...
Definition Loads.cpp:946
bool isModSet(const ModRefInfo MRI)
Definition ModRef.h:49
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
LLVM_ABI void report_fatal_error(Error Err, bool gen_crash_diag=true)
Definition Error.cpp:163
LLVM_ABI void patchReplacementInstruction(Instruction *I, Value *Repl, bool DoesKMove=false)
Patch the replacement so that it is not more restrictive than the value being replaced.
Definition Local.cpp:3259
LLVM_ABI void initializeGVNLegacyPassPass(PassRegistry &)
LLVM_ABI bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition MemorySSA.cpp:76
LLVM_ABI unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge)
Replace each use of 'From' with 'To' if that use is dominated by the given edge.
Definition Local.cpp:3339
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth, bool MustPreserveProvenance=false)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:547
@ Success
The lock was released successfully.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
LLVM_ABI void combineMetadataForCSE(Instruction *K, const Instruction *J, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
Definition Local.cpp:3186
iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition ModRef.h:28
@ Ref
The access may reference the value stored in memory.
Definition ModRef.h:32
@ NoModRef
The access neither references nor modifies the value stored in memory.
Definition ModRef.h:30
@ Other
Any other memory.
Definition ModRef.h:68
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
LLVM_ABI bool salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
LLVM_ABI bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
LLVM_ABI FunctionPass * createGVNPass()
Definition GVN.cpp:4462
LLVM_ABI bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr, const CycleInfo *CI=nullptr)
Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...
Definition CFG.cpp:335
DWARFExpression::Operation Op
LLVM_ABI BasicBlock * SplitCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions(), const Twine &BBName="")
If this edge is a critical edge, insert a new node to split the critical edge.
LLVM_ABI bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
Definition CFG.cpp:106
LLVM_ABI bool willNotFreeBetween(const Instruction *Assume, const Instruction *CtxI, const DominatorTree *DT=nullptr)
Returns true, if no instruction between Assume and CtxI may free (including through synchronization).
constexpr unsigned BitWidth
auto pred_begin(const MachineBasicBlock *BB)
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition STLExtras.h:1963
constexpr bool valueOr(BoolOrDefault X, bool Default)
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Next
Definition InstrProf.h:147
bool pred_empty(const BasicBlock *BB)
Definition CFG.h:107
iterator_range< df_iterator< T > > depth_first(const T &G)
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition Hashing.h:307
BumpPtrAllocatorImpl<> BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition Allocator.h:391
LLVM_ABI bool EliminateDuplicatePHINodes(BasicBlock *BB)
Check for and eliminate duplicate PHI nodes in this block.
Definition Local.cpp:1550
bool isStrongerThan(AtomicOrdering AO, AtomicOrdering Other)
Returns true if ao is stronger than other as defined by the AtomicOrdering lattice,...
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition Hashing.h:287
Implement std::hash so that hash_code can be used in STL containers.
Definition BitVector.h:879
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition BitVector.h:881
#define N
Represents an AvailableValue which can be rematerialized at the end of the associated BasicBlock.
Definition GVN.cpp:562
AvailableValue AV
AV - The actual available value.
Definition GVN.cpp:567
BasicBlock * BB
BB - The basic block in question.
Definition GVN.cpp:564
static AvailableValueInBlock get(BasicBlock *BB, Value *V, unsigned Offset=0)
Definition GVN.cpp:576
Value * MaterializeAdjustedValue(LoadInst *Load) const
Emit code at the end of this block to adjust the value defined here to the specified type.
Definition GVN.cpp:587
static AvailableValueInBlock getUndef(BasicBlock *BB)
Definition GVN.cpp:581
static AvailableValueInBlock get(BasicBlock *BB, AvailableValue &&AV)
Definition GVN.cpp:569
Represents a particular available value that we know how to materialize.
Definition GVN.cpp:466
Value * getSimpleValue() const
Definition GVN.cpp:535
SelectInst * getSelectInstr() const
Definition GVN.cpp:550
static AvailableValue getUndef()
Definition GVN.cpp:511
Value * Val
Val - The value that is live out of the block.
Definition GVN.cpp:478
ValType Kind
Kind of the live-out value.
Definition GVN.cpp:480
static AvailableValue getMI(MemIntrinsic *MI, unsigned Offset=0)
Definition GVN.cpp:495
unsigned Offset
Offset - The byte offset in Val that is interesting for the load query.
Definition GVN.cpp:483
LoadInst * getCoercedLoadValue() const
Definition GVN.cpp:540
static AvailableValue get(Value *V, unsigned Offset=0)
Definition GVN.cpp:487
static AvailableValue getSelect(SelectInst *Sel, Value *V1, Value *V2)
Definition GVN.cpp:519
Value * V1
V1, V2 - The dominating non-clobbered values of SelectVal.
Definition GVN.cpp:485
static AvailableValue getLoad(LoadInst *Load, unsigned Offset=0)
Definition GVN.cpp:503
Value * MaterializeAdjustedValue(LoadInst *Load, Instruction *InsertPt) const
Emit code at the specified insertion point to adjust the value defined here to the specified type.
Definition GVN.cpp:1432
MemIntrinsic * getMemIntrinValue() const
Definition GVN.cpp:545
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition Alignment.h:39
static unsigned getHashValue(const GVNValueTable::Expression &E)
Definition GVN.cpp:146
static bool isEqual(const GVNValueTable::Expression &LHS, const GVNValueTable::Expression &RHS)
Definition GVN.cpp:152
An information struct used to provide DenseMap with the various necessary components for a given valu...
AssertingVH< Value > Val
Definition GVN.cpp:166
LeaderTableEntry(Value *V, const BasicBlock *BB)
Definition GVN.cpp:168
A set of parameters to control various transforms performed by GVN pass.
Definition GVN.h:34
Expression(uint32_t Op=~2U)
Definition GVN.cpp:122
SmallVector< uint32_t, 4 > VarArgs
Definition GVN.cpp:118
bool operator==(const Expression &Other) const
Definition GVN.cpp:124
friend hash_code hash_value(const Expression &Value)
Definition GVN.cpp:139