LLVM 17.0.0git
NewGVN.cpp
Go to the documentation of this file.
1//===- NewGVN.cpp - Global Value Numbering Pass ---------------------------===//
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/// \file
10/// This file implements the new LLVM's Global Value Numbering pass.
11/// GVN partitions values computed by a function into congruence classes.
12/// Values ending up in the same congruence class are guaranteed to be the same
13/// for every execution of the program. In that respect, congruency is a
14/// compile-time approximation of equivalence of values at runtime.
15/// The algorithm implemented here uses a sparse formulation and it's based
16/// on the ideas described in the paper:
17/// "A Sparse Algorithm for Predicated Global Value Numbering" from
18/// Karthik Gargi.
19///
20/// A brief overview of the algorithm: The algorithm is essentially the same as
21/// the standard RPO value numbering algorithm (a good reference is the paper
22/// "SCC based value numbering" by L. Taylor Simpson) with one major difference:
23/// The RPO algorithm proceeds, on every iteration, to process every reachable
24/// block and every instruction in that block. This is because the standard RPO
25/// algorithm does not track what things have the same value number, it only
26/// tracks what the value number of a given operation is (the mapping is
27/// operation -> value number). Thus, when a value number of an operation
28/// changes, it must reprocess everything to ensure all uses of a value number
29/// get updated properly. In constrast, the sparse algorithm we use *also*
30/// tracks what operations have a given value number (IE it also tracks the
31/// reverse mapping from value number -> operations with that value number), so
32/// that it only needs to reprocess the instructions that are affected when
33/// something's value number changes. The vast majority of complexity and code
34/// in this file is devoted to tracking what value numbers could change for what
35/// instructions when various things happen. The rest of the algorithm is
36/// devoted to performing symbolic evaluation, forward propagation, and
37/// simplification of operations based on the value numbers deduced so far
38///
39/// In order to make the GVN mostly-complete, we use a technique derived from
40/// "Detection of Redundant Expressions: A Complete and Polynomial-time
41/// Algorithm in SSA" by R.R. Pai. The source of incompleteness in most SSA
42/// based GVN algorithms is related to their inability to detect equivalence
43/// between phi of ops (IE phi(a+b, c+d)) and op of phis (phi(a,c) + phi(b, d)).
44/// We resolve this issue by generating the equivalent "phi of ops" form for
45/// each op of phis we see, in a way that only takes polynomial time to resolve.
46///
47/// We also do not perform elimination by using any published algorithm. All
48/// published algorithms are O(Instructions). Instead, we use a technique that
49/// is O(number of operations with the same value number), enabling us to skip
50/// trying to eliminate things that have unique value numbers.
51//
52//===----------------------------------------------------------------------===//
53
55#include "llvm/ADT/ArrayRef.h"
56#include "llvm/ADT/BitVector.h"
57#include "llvm/ADT/DenseMap.h"
59#include "llvm/ADT/DenseSet.h"
62#include "llvm/ADT/Hashing.h"
69#include "llvm/ADT/Statistic.h"
81#include "llvm/IR/Argument.h"
82#include "llvm/IR/BasicBlock.h"
83#include "llvm/IR/Constant.h"
84#include "llvm/IR/Constants.h"
85#include "llvm/IR/Dominators.h"
86#include "llvm/IR/Function.h"
87#include "llvm/IR/InstrTypes.h"
88#include "llvm/IR/Instruction.h"
92#include "llvm/IR/Type.h"
93#include "llvm/IR/Use.h"
94#include "llvm/IR/User.h"
95#include "llvm/IR/Value.h"
97#include "llvm/Pass.h"
100#include "llvm/Support/Casting.h"
102#include "llvm/Support/Debug.h"
113#include <algorithm>
114#include <cassert>
115#include <cstdint>
116#include <iterator>
117#include <map>
118#include <memory>
119#include <set>
120#include <string>
121#include <tuple>
122#include <utility>
123#include <vector>
124
125using namespace llvm;
126using namespace llvm::GVNExpression;
127using namespace llvm::VNCoercion;
128using namespace llvm::PatternMatch;
129
130#define DEBUG_TYPE "newgvn"
131
132STATISTIC(NumGVNInstrDeleted, "Number of instructions deleted");
133STATISTIC(NumGVNBlocksDeleted, "Number of blocks deleted");
134STATISTIC(NumGVNOpsSimplified, "Number of Expressions simplified");
135STATISTIC(NumGVNPhisAllSame, "Number of PHIs whos arguments are all the same");
136STATISTIC(NumGVNMaxIterations,
137 "Maximum Number of iterations it took to converge GVN");
138STATISTIC(NumGVNLeaderChanges, "Number of leader changes");
139STATISTIC(NumGVNSortedLeaderChanges, "Number of sorted leader changes");
140STATISTIC(NumGVNAvoidedSortedLeaderChanges,
141 "Number of avoided sorted leader changes");
142STATISTIC(NumGVNDeadStores, "Number of redundant/dead stores eliminated");
143STATISTIC(NumGVNPHIOfOpsCreated, "Number of PHI of ops created");
144STATISTIC(NumGVNPHIOfOpsEliminations,
145 "Number of things eliminated using PHI of ops");
146DEBUG_COUNTER(VNCounter, "newgvn-vn",
147 "Controls which instructions are value numbered");
148DEBUG_COUNTER(PHIOfOpsCounter, "newgvn-phi",
149 "Controls which instructions we create phi of ops for");
150// Currently store defining access refinement is too slow due to basicaa being
151// egregiously slow. This flag lets us keep it working while we work on this
152// issue.
153static cl::opt<bool> EnableStoreRefinement("enable-store-refinement",
154 cl::init(false), cl::Hidden);
155
156/// Currently, the generation "phi of ops" can result in correctness issues.
157static cl::opt<bool> EnablePhiOfOps("enable-phi-of-ops", cl::init(true),
158 cl::Hidden);
159
160//===----------------------------------------------------------------------===//
161// GVN Pass
162//===----------------------------------------------------------------------===//
163
164// Anchor methods.
165namespace llvm {
166namespace GVNExpression {
167
168Expression::~Expression() = default;
175
176} // end namespace GVNExpression
177} // end namespace llvm
178
179namespace {
180
181// Tarjan's SCC finding algorithm with Nuutila's improvements
182// SCCIterator is actually fairly complex for the simple thing we want.
183// It also wants to hand us SCC's that are unrelated to the phi node we ask
184// about, and have us process them there or risk redoing work.
185// Graph traits over a filter iterator also doesn't work that well here.
186// This SCC finder is specialized to walk use-def chains, and only follows
187// instructions,
188// not generic values (arguments, etc).
189struct TarjanSCC {
190 TarjanSCC() : Components(1) {}
191
192 void Start(const Instruction *Start) {
193 if (Root.lookup(Start) == 0)
194 FindSCC(Start);
195 }
196
197 const SmallPtrSetImpl<const Value *> &getComponentFor(const Value *V) const {
198 unsigned ComponentID = ValueToComponent.lookup(V);
199
200 assert(ComponentID > 0 &&
201 "Asking for a component for a value we never processed");
202 return Components[ComponentID];
203 }
204
205private:
206 void FindSCC(const Instruction *I) {
207 Root[I] = ++DFSNum;
208 // Store the DFS Number we had before it possibly gets incremented.
209 unsigned int OurDFS = DFSNum;
210 for (const auto &Op : I->operands()) {
211 if (auto *InstOp = dyn_cast<Instruction>(Op)) {
212 if (Root.lookup(Op) == 0)
213 FindSCC(InstOp);
214 if (!InComponent.count(Op))
215 Root[I] = std::min(Root.lookup(I), Root.lookup(Op));
216 }
217 }
218 // See if we really were the root of a component, by seeing if we still have
219 // our DFSNumber. If we do, we are the root of the component, and we have
220 // completed a component. If we do not, we are not the root of a component,
221 // and belong on the component stack.
222 if (Root.lookup(I) == OurDFS) {
223 unsigned ComponentID = Components.size();
224 Components.resize(Components.size() + 1);
225 auto &Component = Components.back();
226 Component.insert(I);
227 LLVM_DEBUG(dbgs() << "Component root is " << *I << "\n");
228 InComponent.insert(I);
229 ValueToComponent[I] = ComponentID;
230 // Pop a component off the stack and label it.
231 while (!Stack.empty() && Root.lookup(Stack.back()) >= OurDFS) {
232 auto *Member = Stack.back();
233 LLVM_DEBUG(dbgs() << "Component member is " << *Member << "\n");
234 Component.insert(Member);
235 InComponent.insert(Member);
236 ValueToComponent[Member] = ComponentID;
237 Stack.pop_back();
238 }
239 } else {
240 // Part of a component, push to stack
241 Stack.push_back(I);
242 }
243 }
244
245 unsigned int DFSNum = 1;
249
250 // Store the components as vector of ptr sets, because we need the topo order
251 // of SCC's, but not individual member order
253
254 DenseMap<const Value *, unsigned> ValueToComponent;
255};
256
257// Congruence classes represent the set of expressions/instructions
258// that are all the same *during some scope in the function*.
259// That is, because of the way we perform equality propagation, and
260// because of memory value numbering, it is not correct to assume
261// you can willy-nilly replace any member with any other at any
262// point in the function.
263//
264// For any Value in the Member set, it is valid to replace any dominated member
265// with that Value.
266//
267// Every congruence class has a leader, and the leader is used to symbolize
268// instructions in a canonical way (IE every operand of an instruction that is a
269// member of the same congruence class will always be replaced with leader
270// during symbolization). To simplify symbolization, we keep the leader as a
271// constant if class can be proved to be a constant value. Otherwise, the
272// leader is the member of the value set with the smallest DFS number. Each
273// congruence class also has a defining expression, though the expression may be
274// null. If it exists, it can be used for forward propagation and reassociation
275// of values.
276
277// For memory, we also track a representative MemoryAccess, and a set of memory
278// members for MemoryPhis (which have no real instructions). Note that for
279// memory, it seems tempting to try to split the memory members into a
280// MemoryCongruenceClass or something. Unfortunately, this does not work
281// easily. The value numbering of a given memory expression depends on the
282// leader of the memory congruence class, and the leader of memory congruence
283// class depends on the value numbering of a given memory expression. This
284// leads to wasted propagation, and in some cases, missed optimization. For
285// example: If we had value numbered two stores together before, but now do not,
286// we move them to a new value congruence class. This in turn will move at one
287// of the memorydefs to a new memory congruence class. Which in turn, affects
288// the value numbering of the stores we just value numbered (because the memory
289// congruence class is part of the value number). So while theoretically
290// possible to split them up, it turns out to be *incredibly* complicated to get
291// it to work right, because of the interdependency. While structurally
292// slightly messier, it is algorithmically much simpler and faster to do what we
293// do here, and track them both at once in the same class.
294// Note: The default iterators for this class iterate over values
295class CongruenceClass {
296public:
297 using MemberType = Value;
298 using MemberSet = SmallPtrSet<MemberType *, 4>;
299 using MemoryMemberType = MemoryPhi;
300 using MemoryMemberSet = SmallPtrSet<const MemoryMemberType *, 2>;
301
302 explicit CongruenceClass(unsigned ID) : ID(ID) {}
303 CongruenceClass(unsigned ID, Value *Leader, const Expression *E)
304 : ID(ID), RepLeader(Leader), DefiningExpr(E) {}
305
306 unsigned getID() const { return ID; }
307
308 // True if this class has no members left. This is mainly used for assertion
309 // purposes, and for skipping empty classes.
310 bool isDead() const {
311 // If it's both dead from a value perspective, and dead from a memory
312 // perspective, it's really dead.
313 return empty() && memory_empty();
314 }
315
316 // Leader functions
317 Value *getLeader() const { return RepLeader; }
318 void setLeader(Value *Leader) { RepLeader = Leader; }
319 const std::pair<Value *, unsigned int> &getNextLeader() const {
320 return NextLeader;
321 }
322 void resetNextLeader() { NextLeader = {nullptr, ~0}; }
323 void addPossibleNextLeader(std::pair<Value *, unsigned int> LeaderPair) {
324 if (LeaderPair.second < NextLeader.second)
325 NextLeader = LeaderPair;
326 }
327
328 Value *getStoredValue() const { return RepStoredValue; }
329 void setStoredValue(Value *Leader) { RepStoredValue = Leader; }
330 const MemoryAccess *getMemoryLeader() const { return RepMemoryAccess; }
331 void setMemoryLeader(const MemoryAccess *Leader) { RepMemoryAccess = Leader; }
332
333 // Forward propagation info
334 const Expression *getDefiningExpr() const { return DefiningExpr; }
335
336 // Value member set
337 bool empty() const { return Members.empty(); }
338 unsigned size() const { return Members.size(); }
339 MemberSet::const_iterator begin() const { return Members.begin(); }
340 MemberSet::const_iterator end() const { return Members.end(); }
341 void insert(MemberType *M) { Members.insert(M); }
342 void erase(MemberType *M) { Members.erase(M); }
343 void swap(MemberSet &Other) { Members.swap(Other); }
344
345 // Memory member set
346 bool memory_empty() const { return MemoryMembers.empty(); }
347 unsigned memory_size() const { return MemoryMembers.size(); }
348 MemoryMemberSet::const_iterator memory_begin() const {
349 return MemoryMembers.begin();
350 }
351 MemoryMemberSet::const_iterator memory_end() const {
352 return MemoryMembers.end();
353 }
355 return make_range(memory_begin(), memory_end());
356 }
357
358 void memory_insert(const MemoryMemberType *M) { MemoryMembers.insert(M); }
359 void memory_erase(const MemoryMemberType *M) { MemoryMembers.erase(M); }
360
361 // Store count
362 unsigned getStoreCount() const { return StoreCount; }
363 void incStoreCount() { ++StoreCount; }
364 void decStoreCount() {
365 assert(StoreCount != 0 && "Store count went negative");
366 --StoreCount;
367 }
368
369 // True if this class has no memory members.
370 bool definesNoMemory() const { return StoreCount == 0 && memory_empty(); }
371
372 // Return true if two congruence classes are equivalent to each other. This
373 // means that every field but the ID number and the dead field are equivalent.
374 bool isEquivalentTo(const CongruenceClass *Other) const {
375 if (!Other)
376 return false;
377 if (this == Other)
378 return true;
379
380 if (std::tie(StoreCount, RepLeader, RepStoredValue, RepMemoryAccess) !=
381 std::tie(Other->StoreCount, Other->RepLeader, Other->RepStoredValue,
382 Other->RepMemoryAccess))
383 return false;
384 if (DefiningExpr != Other->DefiningExpr)
385 if (!DefiningExpr || !Other->DefiningExpr ||
386 *DefiningExpr != *Other->DefiningExpr)
387 return false;
388
389 if (Members.size() != Other->Members.size())
390 return false;
391
392 return llvm::set_is_subset(Members, Other->Members);
393 }
394
395private:
396 unsigned ID;
397
398 // Representative leader.
399 Value *RepLeader = nullptr;
400
401 // The most dominating leader after our current leader, because the member set
402 // is not sorted and is expensive to keep sorted all the time.
403 std::pair<Value *, unsigned int> NextLeader = {nullptr, ~0U};
404
405 // If this is represented by a store, the value of the store.
406 Value *RepStoredValue = nullptr;
407
408 // If this class contains MemoryDefs or MemoryPhis, this is the leading memory
409 // access.
410 const MemoryAccess *RepMemoryAccess = nullptr;
411
412 // Defining Expression.
413 const Expression *DefiningExpr = nullptr;
414
415 // Actual members of this class.
416 MemberSet Members;
417
418 // This is the set of MemoryPhis that exist in the class. MemoryDefs and
419 // MemoryUses have real instructions representing them, so we only need to
420 // track MemoryPhis here.
421 MemoryMemberSet MemoryMembers;
422
423 // Number of stores in this congruence class.
424 // This is used so we can detect store equivalence changes properly.
425 int StoreCount = 0;
426};
427
428} // end anonymous namespace
429
430namespace llvm {
431
433 const Expression &E;
434
435 explicit ExactEqualsExpression(const Expression &E) : E(E) {}
436
437 hash_code getComputedHash() const { return E.getComputedHash(); }
438
439 bool operator==(const Expression &Other) const {
440 return E.exactlyEquals(Other);
441 }
442};
443
444template <> struct DenseMapInfo<const Expression *> {
445 static const Expression *getEmptyKey() {
446 auto Val = static_cast<uintptr_t>(-1);
447 Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable;
448 return reinterpret_cast<const Expression *>(Val);
449 }
450
451 static const Expression *getTombstoneKey() {
452 auto Val = static_cast<uintptr_t>(~1U);
453 Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable;
454 return reinterpret_cast<const Expression *>(Val);
455 }
456
457 static unsigned getHashValue(const Expression *E) {
458 return E->getComputedHash();
459 }
460
461 static unsigned getHashValue(const ExactEqualsExpression &E) {
462 return E.getComputedHash();
463 }
464
465 static bool isEqual(const ExactEqualsExpression &LHS, const Expression *RHS) {
466 if (RHS == getTombstoneKey() || RHS == getEmptyKey())
467 return false;
468 return LHS == *RHS;
469 }
470
471 static bool isEqual(const Expression *LHS, const Expression *RHS) {
472 if (LHS == RHS)
473 return true;
474 if (LHS == getTombstoneKey() || RHS == getTombstoneKey() ||
475 LHS == getEmptyKey() || RHS == getEmptyKey())
476 return false;
477 // Compare hashes before equality. This is *not* what the hashtable does,
478 // since it is computing it modulo the number of buckets, whereas we are
479 // using the full hash keyspace. Since the hashes are precomputed, this
480 // check is *much* faster than equality.
481 if (LHS->getComputedHash() != RHS->getComputedHash())
482 return false;
483 return *LHS == *RHS;
484 }
485};
486
487} // end namespace llvm
488
489namespace {
490
491class NewGVN {
492 Function &F;
493 DominatorTree *DT = nullptr;
494 const TargetLibraryInfo *TLI = nullptr;
495 AliasAnalysis *AA = nullptr;
496 MemorySSA *MSSA = nullptr;
497 MemorySSAWalker *MSSAWalker = nullptr;
498 AssumptionCache *AC = nullptr;
499 const DataLayout &DL;
500 std::unique_ptr<PredicateInfo> PredInfo;
501
502 // These are the only two things the create* functions should have
503 // side-effects on due to allocating memory.
504 mutable BumpPtrAllocator ExpressionAllocator;
505 mutable ArrayRecycler<Value *> ArgRecycler;
506 mutable TarjanSCC SCCFinder;
507 const SimplifyQuery SQ;
508
509 // Number of function arguments, used by ranking
510 unsigned int NumFuncArgs = 0;
511
512 // RPOOrdering of basic blocks
514
515 // Congruence class info.
516
517 // This class is called INITIAL in the paper. It is the class everything
518 // startsout in, and represents any value. Being an optimistic analysis,
519 // anything in the TOP class has the value TOP, which is indeterminate and
520 // equivalent to everything.
521 CongruenceClass *TOPClass = nullptr;
522 std::vector<CongruenceClass *> CongruenceClasses;
523 unsigned NextCongruenceNum = 0;
524
525 // Value Mappings.
528
529 // Value PHI handling, used to make equivalence between phi(op, op) and
530 // op(phi, phi).
531 // These mappings just store various data that would normally be part of the
532 // IR.
534
535 DenseMap<const Value *, bool> OpSafeForPHIOfOps;
536
537 // Map a temporary instruction we created to a parent block.
539
540 // Map between the already in-program instructions and the temporary phis we
541 // created that they are known equivalent to.
543
544 // In order to know when we should re-process instructions that have
545 // phi-of-ops, we track the set of expressions that they needed as
546 // leaders. When we discover new leaders for those expressions, we process the
547 // associated phi-of-op instructions again in case they have changed. The
548 // other way they may change is if they had leaders, and those leaders
549 // disappear. However, at the point they have leaders, there are uses of the
550 // relevant operands in the created phi node, and so they will get reprocessed
551 // through the normal user marking we perform.
554 ExpressionToPhiOfOps;
555
556 // Map from temporary operation to MemoryAccess.
558
559 // Set of all temporary instructions we created.
560 // Note: This will include instructions that were just created during value
561 // numbering. The way to test if something is using them is to check
562 // RealToTemp.
563 DenseSet<Instruction *> AllTempInstructions;
564
565 // This is the set of instructions to revisit on a reachability change. At
566 // the end of the main iteration loop it will contain at least all the phi of
567 // ops instructions that will be changed to phis, as well as regular phis.
568 // During the iteration loop, it may contain other things, such as phi of ops
569 // instructions that used edge reachability to reach a result, and so need to
570 // be revisited when the edge changes, independent of whether the phi they
571 // depended on changes.
572 DenseMap<BasicBlock *, SparseBitVector<>> RevisitOnReachabilityChange;
573
574 // Mapping from predicate info we used to the instructions we used it with.
575 // In order to correctly ensure propagation, we must keep track of what
576 // comparisons we used, so that when the values of the comparisons change, we
577 // propagate the information to the places we used the comparison.
579 PredicateToUsers;
580
581 // the same reasoning as PredicateToUsers. When we skip MemoryAccesses for
582 // stores, we no longer can rely solely on the def-use chains of MemorySSA.
584 MemoryToUsers;
585
586 // A table storing which memorydefs/phis represent a memory state provably
587 // equivalent to another memory state.
588 // We could use the congruence class machinery, but the MemoryAccess's are
589 // abstract memory states, so they can only ever be equivalent to each other,
590 // and not to constants, etc.
592
593 // We could, if we wanted, build MemoryPhiExpressions and
594 // MemoryVariableExpressions, etc, and value number them the same way we value
595 // number phi expressions. For the moment, this seems like overkill. They
596 // can only exist in one of three states: they can be TOP (equal to
597 // everything), Equivalent to something else, or unique. Because we do not
598 // create expressions for them, we need to simulate leader change not just
599 // when they change class, but when they change state. Note: We can do the
600 // same thing for phis, and avoid having phi expressions if we wanted, We
601 // should eventually unify in one direction or the other, so this is a little
602 // bit of an experiment in which turns out easier to maintain.
603 enum MemoryPhiState { MPS_Invalid, MPS_TOP, MPS_Equivalent, MPS_Unique };
605
606 enum InstCycleState { ICS_Unknown, ICS_CycleFree, ICS_Cycle };
608
609 // Expression to class mapping.
610 using ExpressionClassMap = DenseMap<const Expression *, CongruenceClass *>;
611 ExpressionClassMap ExpressionToClass;
612
613 // We have a single expression that represents currently DeadExpressions.
614 // For dead expressions we can prove will stay dead, we mark them with
615 // DFS number zero. However, it's possible in the case of phi nodes
616 // for us to assume/prove all arguments are dead during fixpointing.
617 // We use DeadExpression for that case.
618 DeadExpression *SingletonDeadExpression = nullptr;
619
620 // Which values have changed as a result of leader changes.
621 SmallPtrSet<Value *, 8> LeaderChanges;
622
623 // Reachability info.
624 using BlockEdge = BasicBlockEdge;
625 DenseSet<BlockEdge> ReachableEdges;
627
628 // This is a bitvector because, on larger functions, we may have
629 // thousands of touched instructions at once (entire blocks,
630 // instructions with hundreds of uses, etc). Even with optimization
631 // for when we mark whole blocks as touched, when this was a
632 // SmallPtrSet or DenseSet, for some functions, we spent >20% of all
633 // the time in GVN just managing this list. The bitvector, on the
634 // other hand, efficiently supports test/set/clear of both
635 // individual and ranges, as well as "find next element" This
636 // enables us to use it as a worklist with essentially 0 cost.
637 BitVector TouchedInstructions;
638
640 mutable DenseMap<const IntrinsicInst *, const Value *> IntrinsicInstPred;
641
642#ifndef NDEBUG
643 // Debugging for how many times each block and instruction got processed.
645#endif
646
647 // DFS info.
648 // This contains a mapping from Instructions to DFS numbers.
649 // The numbering starts at 1. An instruction with DFS number zero
650 // means that the instruction is dead.
652
653 // This contains the mapping DFS numbers to instructions.
654 SmallVector<Value *, 32> DFSToInstr;
655
656 // Deletion info.
657 SmallPtrSet<Instruction *, 8> InstructionsToErase;
658
659public:
660 NewGVN(Function &F, DominatorTree *DT, AssumptionCache *AC,
662 const DataLayout &DL)
663 : F(F), DT(DT), TLI(TLI), AA(AA), MSSA(MSSA), AC(AC), DL(DL),
664 PredInfo(std::make_unique<PredicateInfo>(F, *DT, *AC)),
665 SQ(DL, TLI, DT, AC, /*CtxI=*/nullptr, /*UseInstrInfo=*/false,
666 /*CanUseUndef=*/false) {}
667
668 bool runGVN();
669
670private:
671 /// Helper struct return a Expression with an optional extra dependency.
672 struct ExprResult {
673 const Expression *Expr;
674 Value *ExtraDep;
675 const PredicateBase *PredDep;
676
677 ExprResult(const Expression *Expr, Value *ExtraDep = nullptr,
678 const PredicateBase *PredDep = nullptr)
679 : Expr(Expr), ExtraDep(ExtraDep), PredDep(PredDep) {}
680 ExprResult(const ExprResult &) = delete;
681 ExprResult(ExprResult &&Other)
682 : Expr(Other.Expr), ExtraDep(Other.ExtraDep), PredDep(Other.PredDep) {
683 Other.Expr = nullptr;
684 Other.ExtraDep = nullptr;
685 Other.PredDep = nullptr;
686 }
687 ExprResult &operator=(const ExprResult &Other) = delete;
688 ExprResult &operator=(ExprResult &&Other) = delete;
689
690 ~ExprResult() { assert(!ExtraDep && "unhandled ExtraDep"); }
691
692 operator bool() const { return Expr; }
693
694 static ExprResult none() { return {nullptr, nullptr, nullptr}; }
695 static ExprResult some(const Expression *Expr, Value *ExtraDep = nullptr) {
696 return {Expr, ExtraDep, nullptr};
697 }
698 static ExprResult some(const Expression *Expr,
699 const PredicateBase *PredDep) {
700 return {Expr, nullptr, PredDep};
701 }
702 static ExprResult some(const Expression *Expr, Value *ExtraDep,
703 const PredicateBase *PredDep) {
704 return {Expr, ExtraDep, PredDep};
705 }
706 };
707
708 // Expression handling.
709 ExprResult createExpression(Instruction *) const;
710 const Expression *createBinaryExpression(unsigned, Type *, Value *, Value *,
711 Instruction *) const;
712
713 // Our canonical form for phi arguments is a pair of incoming value, incoming
714 // basic block.
715 using ValPair = std::pair<Value *, BasicBlock *>;
716
717 PHIExpression *createPHIExpression(ArrayRef<ValPair>, const Instruction *,
718 BasicBlock *, bool &HasBackEdge,
719 bool &OriginalOpsConstant) const;
720 const DeadExpression *createDeadExpression() const;
721 const VariableExpression *createVariableExpression(Value *) const;
722 const ConstantExpression *createConstantExpression(Constant *) const;
723 const Expression *createVariableOrConstant(Value *V) const;
724 const UnknownExpression *createUnknownExpression(Instruction *) const;
725 const StoreExpression *createStoreExpression(StoreInst *,
726 const MemoryAccess *) const;
727 LoadExpression *createLoadExpression(Type *, Value *, LoadInst *,
728 const MemoryAccess *) const;
729 const CallExpression *createCallExpression(CallInst *,
730 const MemoryAccess *) const;
732 createAggregateValueExpression(Instruction *) const;
733 bool setBasicExpressionInfo(Instruction *, BasicExpression *) const;
734
735 // Congruence class handling.
736 CongruenceClass *createCongruenceClass(Value *Leader, const Expression *E) {
737 auto *result = new CongruenceClass(NextCongruenceNum++, Leader, E);
738 CongruenceClasses.emplace_back(result);
739 return result;
740 }
741
742 CongruenceClass *createMemoryClass(MemoryAccess *MA) {
743 auto *CC = createCongruenceClass(nullptr, nullptr);
744 CC->setMemoryLeader(MA);
745 return CC;
746 }
747
748 CongruenceClass *ensureLeaderOfMemoryClass(MemoryAccess *MA) {
749 auto *CC = getMemoryClass(MA);
750 if (CC->getMemoryLeader() != MA)
751 CC = createMemoryClass(MA);
752 return CC;
753 }
754
755 CongruenceClass *createSingletonCongruenceClass(Value *Member) {
756 CongruenceClass *CClass = createCongruenceClass(Member, nullptr);
757 CClass->insert(Member);
758 ValueToClass[Member] = CClass;
759 return CClass;
760 }
761
762 void initializeCongruenceClasses(Function &F);
763 const Expression *makePossiblePHIOfOps(Instruction *,
765 Value *findLeaderForInst(Instruction *ValueOp,
767 MemoryAccess *MemAccess, Instruction *OrigInst,
768 BasicBlock *PredBB);
769 bool OpIsSafeForPHIOfOps(Value *Op, const BasicBlock *PHIBlock,
771 void addPhiOfOps(PHINode *Op, BasicBlock *BB, Instruction *ExistingValue);
772 void removePhiOfOps(Instruction *I, PHINode *PHITemp);
773
774 // Value number an Instruction or MemoryPhi.
775 void valueNumberMemoryPhi(MemoryPhi *);
776 void valueNumberInstruction(Instruction *);
777
778 // Symbolic evaluation.
779 ExprResult checkExprResults(Expression *, Instruction *, Value *) const;
780 ExprResult performSymbolicEvaluation(Value *,
782 const Expression *performSymbolicLoadCoercion(Type *, Value *, LoadInst *,
783 Instruction *,
784 MemoryAccess *) const;
785 const Expression *performSymbolicLoadEvaluation(Instruction *) const;
786 const Expression *performSymbolicStoreEvaluation(Instruction *) const;
787 ExprResult performSymbolicCallEvaluation(Instruction *) const;
788 void sortPHIOps(MutableArrayRef<ValPair> Ops) const;
789 const Expression *performSymbolicPHIEvaluation(ArrayRef<ValPair>,
790 Instruction *I,
791 BasicBlock *PHIBlock) const;
792 const Expression *performSymbolicAggrValueEvaluation(Instruction *) const;
793 ExprResult performSymbolicCmpEvaluation(Instruction *) const;
794 ExprResult performSymbolicPredicateInfoEvaluation(IntrinsicInst *) const;
795
796 // Congruence finding.
797 bool someEquivalentDominates(const Instruction *, const Instruction *) const;
798 Value *lookupOperandLeader(Value *) const;
799 CongruenceClass *getClassForExpression(const Expression *E) const;
800 void performCongruenceFinding(Instruction *, const Expression *);
801 void moveValueToNewCongruenceClass(Instruction *, const Expression *,
802 CongruenceClass *, CongruenceClass *);
803 void moveMemoryToNewCongruenceClass(Instruction *, MemoryAccess *,
804 CongruenceClass *, CongruenceClass *);
805 Value *getNextValueLeader(CongruenceClass *) const;
806 const MemoryAccess *getNextMemoryLeader(CongruenceClass *) const;
807 bool setMemoryClass(const MemoryAccess *From, CongruenceClass *To);
808 CongruenceClass *getMemoryClass(const MemoryAccess *MA) const;
809 const MemoryAccess *lookupMemoryLeader(const MemoryAccess *) const;
810 bool isMemoryAccessTOP(const MemoryAccess *) const;
811
812 // Ranking
813 unsigned int getRank(const Value *) const;
814 bool shouldSwapOperands(const Value *, const Value *) const;
815 bool shouldSwapOperandsForIntrinsic(const Value *, const Value *,
816 const IntrinsicInst *I) const;
817
818 // Reachability handling.
819 void updateReachableEdge(BasicBlock *, BasicBlock *);
820 void processOutgoingEdges(Instruction *, BasicBlock *);
821 Value *findConditionEquivalence(Value *) const;
822
823 // Elimination.
824 struct ValueDFS;
825 void convertClassToDFSOrdered(const CongruenceClass &,
829 void convertClassToLoadsAndStores(const CongruenceClass &,
831
832 bool eliminateInstructions(Function &);
833 void replaceInstruction(Instruction *, Value *);
834 void markInstructionForDeletion(Instruction *);
835 void deleteInstructionsInBlock(BasicBlock *);
836 Value *findPHIOfOpsLeader(const Expression *, const Instruction *,
837 const BasicBlock *) const;
838
839 // Various instruction touch utilities
840 template <typename Map, typename KeyType>
841 void touchAndErase(Map &, const KeyType &);
842 void markUsersTouched(Value *);
843 void markMemoryUsersTouched(const MemoryAccess *);
844 void markMemoryDefTouched(const MemoryAccess *);
845 void markPredicateUsersTouched(Instruction *);
846 void markValueLeaderChangeTouched(CongruenceClass *CC);
847 void markMemoryLeaderChangeTouched(CongruenceClass *CC);
848 void markPhiOfOpsChanged(const Expression *E);
849 void addMemoryUsers(const MemoryAccess *To, MemoryAccess *U) const;
850 void addAdditionalUsers(Value *To, Value *User) const;
851 void addAdditionalUsers(ExprResult &Res, Instruction *User) const;
852
853 // Main loop of value numbering
854 void iterateTouchedInstructions();
855
856 // Utilities.
857 void cleanupTables();
858 std::pair<unsigned, unsigned> assignDFSNumbers(BasicBlock *, unsigned);
859 void updateProcessedCount(const Value *V);
860 void verifyMemoryCongruency() const;
861 void verifyIterationSettled(Function &F);
862 void verifyStoreExpressions() const;
863 bool singleReachablePHIPath(SmallPtrSet<const MemoryAccess *, 8> &,
864 const MemoryAccess *, const MemoryAccess *) const;
865 BasicBlock *getBlockForValue(Value *V) const;
866 void deleteExpression(const Expression *E) const;
867 MemoryUseOrDef *getMemoryAccess(const Instruction *) const;
868 MemoryPhi *getMemoryAccess(const BasicBlock *) const;
869 template <class T, class Range> T *getMinDFSOfRange(const Range &) const;
870
871 unsigned InstrToDFSNum(const Value *V) const {
872 assert(isa<Instruction>(V) && "This should not be used for MemoryAccesses");
873 return InstrDFS.lookup(V);
874 }
875
876 unsigned InstrToDFSNum(const MemoryAccess *MA) const {
877 return MemoryToDFSNum(MA);
878 }
879
880 Value *InstrFromDFSNum(unsigned DFSNum) { return DFSToInstr[DFSNum]; }
881
882 // Given a MemoryAccess, return the relevant instruction DFS number. Note:
883 // This deliberately takes a value so it can be used with Use's, which will
884 // auto-convert to Value's but not to MemoryAccess's.
885 unsigned MemoryToDFSNum(const Value *MA) const {
886 assert(isa<MemoryAccess>(MA) &&
887 "This should not be used with instructions");
888 return isa<MemoryUseOrDef>(MA)
889 ? InstrToDFSNum(cast<MemoryUseOrDef>(MA)->getMemoryInst())
890 : InstrDFS.lookup(MA);
891 }
892
893 bool isCycleFree(const Instruction *) const;
894 bool isBackedge(BasicBlock *From, BasicBlock *To) const;
895
896 // Debug counter info. When verifying, we have to reset the value numbering
897 // debug counter to the same state it started in to get the same results.
898 int64_t StartingVNCounter = 0;
899};
900
901} // end anonymous namespace
902
903template <typename T>
904static bool equalsLoadStoreHelper(const T &LHS, const Expression &RHS) {
905 if (!isa<LoadExpression>(RHS) && !isa<StoreExpression>(RHS))
906 return false;
907 return LHS.MemoryExpression::equals(RHS);
908}
909
911 return equalsLoadStoreHelper(*this, Other);
912}
913
915 if (!equalsLoadStoreHelper(*this, Other))
916 return false;
917 // Make sure that store vs store includes the value operand.
918 if (const auto *S = dyn_cast<StoreExpression>(&Other))
919 if (getStoredValue() != S->getStoredValue())
920 return false;
921 return true;
922}
923
924// Determine if the edge From->To is a backedge
925bool NewGVN::isBackedge(BasicBlock *From, BasicBlock *To) const {
926 return From == To ||
927 RPOOrdering.lookup(DT->getNode(From)) >=
928 RPOOrdering.lookup(DT->getNode(To));
929}
930
931#ifndef NDEBUG
932static std::string getBlockName(const BasicBlock *B) {
934}
935#endif
936
937// Get a MemoryAccess for an instruction, fake or real.
938MemoryUseOrDef *NewGVN::getMemoryAccess(const Instruction *I) const {
939 auto *Result = MSSA->getMemoryAccess(I);
940 return Result ? Result : TempToMemory.lookup(I);
941}
942
943// Get a MemoryPhi for a basic block. These are all real.
944MemoryPhi *NewGVN::getMemoryAccess(const BasicBlock *BB) const {
945 return MSSA->getMemoryAccess(BB);
946}
947
948// Get the basic block from an instruction/memory value.
949BasicBlock *NewGVN::getBlockForValue(Value *V) const {
950 if (auto *I = dyn_cast<Instruction>(V)) {
951 auto *Parent = I->getParent();
952 if (Parent)
953 return Parent;
954 Parent = TempToBlock.lookup(V);
955 assert(Parent && "Every fake instruction should have a block");
956 return Parent;
957 }
958
959 auto *MP = dyn_cast<MemoryPhi>(V);
960 assert(MP && "Should have been an instruction or a MemoryPhi");
961 return MP->getBlock();
962}
963
964// Delete a definitely dead expression, so it can be reused by the expression
965// allocator. Some of these are not in creation functions, so we have to accept
966// const versions.
967void NewGVN::deleteExpression(const Expression *E) const {
968 assert(isa<BasicExpression>(E));
969 auto *BE = cast<BasicExpression>(E);
970 const_cast<BasicExpression *>(BE)->deallocateOperands(ArgRecycler);
971 ExpressionAllocator.Deallocate(E);
972}
973
974// If V is a predicateinfo copy, get the thing it is a copy of.
975static Value *getCopyOf(const Value *V) {
976 if (auto *II = dyn_cast<IntrinsicInst>(V))
977 if (II->getIntrinsicID() == Intrinsic::ssa_copy)
978 return II->getOperand(0);
979 return nullptr;
980}
981
982// Return true if V is really PN, even accounting for predicateinfo copies.
983static bool isCopyOfPHI(const Value *V, const PHINode *PN) {
984 return V == PN || getCopyOf(V) == PN;
985}
986
987static bool isCopyOfAPHI(const Value *V) {
988 auto *CO = getCopyOf(V);
989 return CO && isa<PHINode>(CO);
990}
991
992// Sort PHI Operands into a canonical order. What we use here is an RPO
993// order. The BlockInstRange numbers are generated in an RPO walk of the basic
994// blocks.
995void NewGVN::sortPHIOps(MutableArrayRef<ValPair> Ops) const {
996 llvm::sort(Ops, [&](const ValPair &P1, const ValPair &P2) {
997 return BlockInstRange.lookup(P1.second).first <
998 BlockInstRange.lookup(P2.second).first;
999 });
1000}
1001
1002// Return true if V is a value that will always be available (IE can
1003// be placed anywhere) in the function. We don't do globals here
1004// because they are often worse to put in place.
1005static bool alwaysAvailable(Value *V) {
1006 return isa<Constant>(V) || isa<Argument>(V);
1007}
1008
1009// Create a PHIExpression from an array of {incoming edge, value} pairs. I is
1010// the original instruction we are creating a PHIExpression for (but may not be
1011// a phi node). We require, as an invariant, that all the PHIOperands in the
1012// same block are sorted the same way. sortPHIOps will sort them into a
1013// canonical order.
1014PHIExpression *NewGVN::createPHIExpression(ArrayRef<ValPair> PHIOperands,
1015 const Instruction *I,
1016 BasicBlock *PHIBlock,
1017 bool &HasBackedge,
1018 bool &OriginalOpsConstant) const {
1019 unsigned NumOps = PHIOperands.size();
1020 auto *E = new (ExpressionAllocator) PHIExpression(NumOps, PHIBlock);
1021
1022 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1023 E->setType(PHIOperands.begin()->first->getType());
1024 E->setOpcode(Instruction::PHI);
1025
1026 // Filter out unreachable phi operands.
1027 auto Filtered = make_filter_range(PHIOperands, [&](const ValPair &P) {
1028 auto *BB = P.second;
1029 if (auto *PHIOp = dyn_cast<PHINode>(I))
1030 if (isCopyOfPHI(P.first, PHIOp))
1031 return false;
1032 if (!ReachableEdges.count({BB, PHIBlock}))
1033 return false;
1034 // Things in TOPClass are equivalent to everything.
1035 if (ValueToClass.lookup(P.first) == TOPClass)
1036 return false;
1037 OriginalOpsConstant = OriginalOpsConstant && isa<Constant>(P.first);
1038 HasBackedge = HasBackedge || isBackedge(BB, PHIBlock);
1039 return lookupOperandLeader(P.first) != I;
1040 });
1041 std::transform(Filtered.begin(), Filtered.end(), op_inserter(E),
1042 [&](const ValPair &P) -> Value * {
1043 return lookupOperandLeader(P.first);
1044 });
1045 return E;
1046}
1047
1048// Set basic expression info (Arguments, type, opcode) for Expression
1049// E from Instruction I in block B.
1050bool NewGVN::setBasicExpressionInfo(Instruction *I, BasicExpression *E) const {
1051 bool AllConstant = true;
1052 if (auto *GEP = dyn_cast<GetElementPtrInst>(I))
1053 E->setType(GEP->getSourceElementType());
1054 else
1055 E->setType(I->getType());
1056 E->setOpcode(I->getOpcode());
1057 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1058
1059 // Transform the operand array into an operand leader array, and keep track of
1060 // whether all members are constant.
1061 std::transform(I->op_begin(), I->op_end(), op_inserter(E), [&](Value *O) {
1062 auto Operand = lookupOperandLeader(O);
1063 AllConstant = AllConstant && isa<Constant>(Operand);
1064 return Operand;
1065 });
1066
1067 return AllConstant;
1068}
1069
1070const Expression *NewGVN::createBinaryExpression(unsigned Opcode, Type *T,
1071 Value *Arg1, Value *Arg2,
1072 Instruction *I) const {
1073 auto *E = new (ExpressionAllocator) BasicExpression(2);
1074 // TODO: we need to remove context instruction after Value Tracking
1075 // can run without context instruction
1076 const SimplifyQuery Q = SQ.getWithInstruction(I);
1077
1078 E->setType(T);
1079 E->setOpcode(Opcode);
1080 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1081 if (Instruction::isCommutative(Opcode)) {
1082 // Ensure that commutative instructions that only differ by a permutation
1083 // of their operands get the same value number by sorting the operand value
1084 // numbers. Since all commutative instructions have two operands it is more
1085 // efficient to sort by hand rather than using, say, std::sort.
1086 if (shouldSwapOperands(Arg1, Arg2))
1087 std::swap(Arg1, Arg2);
1088 }
1089 E->op_push_back(lookupOperandLeader(Arg1));
1090 E->op_push_back(lookupOperandLeader(Arg2));
1091
1092 Value *V = simplifyBinOp(Opcode, E->getOperand(0), E->getOperand(1), Q);
1093 if (auto Simplified = checkExprResults(E, I, V)) {
1094 addAdditionalUsers(Simplified, I);
1095 return Simplified.Expr;
1096 }
1097 return E;
1098}
1099
1100// Take a Value returned by simplification of Expression E/Instruction
1101// I, and see if it resulted in a simpler expression. If so, return
1102// that expression.
1103NewGVN::ExprResult NewGVN::checkExprResults(Expression *E, Instruction *I,
1104 Value *V) const {
1105 if (!V)
1106 return ExprResult::none();
1107
1108 if (auto *C = dyn_cast<Constant>(V)) {
1109 if (I)
1110 LLVM_DEBUG(dbgs() << "Simplified " << *I << " to "
1111 << " constant " << *C << "\n");
1112 NumGVNOpsSimplified++;
1113 assert(isa<BasicExpression>(E) &&
1114 "We should always have had a basic expression here");
1115 deleteExpression(E);
1116 return ExprResult::some(createConstantExpression(C));
1117 } else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
1118 if (I)
1119 LLVM_DEBUG(dbgs() << "Simplified " << *I << " to "
1120 << " variable " << *V << "\n");
1121 deleteExpression(E);
1122 return ExprResult::some(createVariableExpression(V));
1123 }
1124
1125 CongruenceClass *CC = ValueToClass.lookup(V);
1126 if (CC) {
1127 if (CC->getLeader() && CC->getLeader() != I) {
1128 return ExprResult::some(createVariableOrConstant(CC->getLeader()), V);
1129 }
1130 if (CC->getDefiningExpr()) {
1131 if (I)
1132 LLVM_DEBUG(dbgs() << "Simplified " << *I << " to "
1133 << " expression " << *CC->getDefiningExpr() << "\n");
1134 NumGVNOpsSimplified++;
1135 deleteExpression(E);
1136 return ExprResult::some(CC->getDefiningExpr(), V);
1137 }
1138 }
1139
1140 return ExprResult::none();
1141}
1142
1143// Create a value expression from the instruction I, replacing operands with
1144// their leaders.
1145
1146NewGVN::ExprResult NewGVN::createExpression(Instruction *I) const {
1147 auto *E = new (ExpressionAllocator) BasicExpression(I->getNumOperands());
1148 // TODO: we need to remove context instruction after Value Tracking
1149 // can run without context instruction
1150 const SimplifyQuery Q = SQ.getWithInstruction(I);
1151
1152 bool AllConstant = setBasicExpressionInfo(I, E);
1153
1154 if (I->isCommutative()) {
1155 // Ensure that commutative instructions that only differ by a permutation
1156 // of their operands get the same value number by sorting the operand value
1157 // numbers. Since all commutative instructions have two operands it is more
1158 // efficient to sort by hand rather than using, say, std::sort.
1159 assert(I->getNumOperands() == 2 && "Unsupported commutative instruction!");
1160 if (shouldSwapOperands(E->getOperand(0), E->getOperand(1)))
1161 E->swapOperands(0, 1);
1162 }
1163 // Perform simplification.
1164 if (auto *CI = dyn_cast<CmpInst>(I)) {
1165 // Sort the operand value numbers so x<y and y>x get the same value
1166 // number.
1167 CmpInst::Predicate Predicate = CI->getPredicate();
1168 if (shouldSwapOperands(E->getOperand(0), E->getOperand(1))) {
1169 E->swapOperands(0, 1);
1171 }
1172 E->setOpcode((CI->getOpcode() << 8) | Predicate);
1173 // TODO: 25% of our time is spent in simplifyCmpInst with pointer operands
1174 assert(I->getOperand(0)->getType() == I->getOperand(1)->getType() &&
1175 "Wrong types on cmp instruction");
1176 assert((E->getOperand(0)->getType() == I->getOperand(0)->getType() &&
1177 E->getOperand(1)->getType() == I->getOperand(1)->getType()));
1178 Value *V =
1179 simplifyCmpInst(Predicate, E->getOperand(0), E->getOperand(1), Q);
1180 if (auto Simplified = checkExprResults(E, I, V))
1181 return Simplified;
1182 } else if (isa<SelectInst>(I)) {
1183 if (isa<Constant>(E->getOperand(0)) ||
1184 E->getOperand(1) == E->getOperand(2)) {
1185 assert(E->getOperand(1)->getType() == I->getOperand(1)->getType() &&
1186 E->getOperand(2)->getType() == I->getOperand(2)->getType());
1187 Value *V = simplifySelectInst(E->getOperand(0), E->getOperand(1),
1188 E->getOperand(2), Q);
1189 if (auto Simplified = checkExprResults(E, I, V))
1190 return Simplified;
1191 }
1192 } else if (I->isBinaryOp()) {
1193 Value *V =
1194 simplifyBinOp(E->getOpcode(), E->getOperand(0), E->getOperand(1), Q);
1195 if (auto Simplified = checkExprResults(E, I, V))
1196 return Simplified;
1197 } else if (auto *CI = dyn_cast<CastInst>(I)) {
1198 Value *V =
1199 simplifyCastInst(CI->getOpcode(), E->getOperand(0), CI->getType(), Q);
1200 if (auto Simplified = checkExprResults(E, I, V))
1201 return Simplified;
1202 } else if (auto *GEPI = dyn_cast<GetElementPtrInst>(I)) {
1203 Value *V = simplifyGEPInst(GEPI->getSourceElementType(), *E->op_begin(),
1204 ArrayRef(std::next(E->op_begin()), E->op_end()),
1205 GEPI->isInBounds(), Q);
1206 if (auto Simplified = checkExprResults(E, I, V))
1207 return Simplified;
1208 } else if (AllConstant) {
1209 // We don't bother trying to simplify unless all of the operands
1210 // were constant.
1211 // TODO: There are a lot of Simplify*'s we could call here, if we
1212 // wanted to. The original motivating case for this code was a
1213 // zext i1 false to i8, which we don't have an interface to
1214 // simplify (IE there is no SimplifyZExt).
1215
1217 for (Value *Arg : E->operands())
1218 C.emplace_back(cast<Constant>(Arg));
1219
1220 if (Value *V = ConstantFoldInstOperands(I, C, DL, TLI))
1221 if (auto Simplified = checkExprResults(E, I, V))
1222 return Simplified;
1223 }
1224 return ExprResult::some(E);
1225}
1226
1228NewGVN::createAggregateValueExpression(Instruction *I) const {
1229 if (auto *II = dyn_cast<InsertValueInst>(I)) {
1230 auto *E = new (ExpressionAllocator)
1231 AggregateValueExpression(I->getNumOperands(), II->getNumIndices());
1232 setBasicExpressionInfo(I, E);
1233 E->allocateIntOperands(ExpressionAllocator);
1234 std::copy(II->idx_begin(), II->idx_end(), int_op_inserter(E));
1235 return E;
1236 } else if (auto *EI = dyn_cast<ExtractValueInst>(I)) {
1237 auto *E = new (ExpressionAllocator)
1238 AggregateValueExpression(I->getNumOperands(), EI->getNumIndices());
1239 setBasicExpressionInfo(EI, E);
1240 E->allocateIntOperands(ExpressionAllocator);
1241 std::copy(EI->idx_begin(), EI->idx_end(), int_op_inserter(E));
1242 return E;
1243 }
1244 llvm_unreachable("Unhandled type of aggregate value operation");
1245}
1246
1247const DeadExpression *NewGVN::createDeadExpression() const {
1248 // DeadExpression has no arguments and all DeadExpression's are the same,
1249 // so we only need one of them.
1250 return SingletonDeadExpression;
1251}
1252
1253const VariableExpression *NewGVN::createVariableExpression(Value *V) const {
1254 auto *E = new (ExpressionAllocator) VariableExpression(V);
1255 E->setOpcode(V->getValueID());
1256 return E;
1257}
1258
1259const Expression *NewGVN::createVariableOrConstant(Value *V) const {
1260 if (auto *C = dyn_cast<Constant>(V))
1261 return createConstantExpression(C);
1262 return createVariableExpression(V);
1263}
1264
1265const ConstantExpression *NewGVN::createConstantExpression(Constant *C) const {
1266 auto *E = new (ExpressionAllocator) ConstantExpression(C);
1267 E->setOpcode(C->getValueID());
1268 return E;
1269}
1270
1271const UnknownExpression *NewGVN::createUnknownExpression(Instruction *I) const {
1272 auto *E = new (ExpressionAllocator) UnknownExpression(I);
1273 E->setOpcode(I->getOpcode());
1274 return E;
1275}
1276
1277const CallExpression *
1278NewGVN::createCallExpression(CallInst *CI, const MemoryAccess *MA) const {
1279 // FIXME: Add operand bundles for calls.
1280 // FIXME: Allow commutative matching for intrinsics.
1281 auto *E =
1282 new (ExpressionAllocator) CallExpression(CI->getNumOperands(), CI, MA);
1283 setBasicExpressionInfo(CI, E);
1284 return E;
1285}
1286
1287// Return true if some equivalent of instruction Inst dominates instruction U.
1288bool NewGVN::someEquivalentDominates(const Instruction *Inst,
1289 const Instruction *U) const {
1290 auto *CC = ValueToClass.lookup(Inst);
1291 // This must be an instruction because we are only called from phi nodes
1292 // in the case that the value it needs to check against is an instruction.
1293
1294 // The most likely candidates for dominance are the leader and the next leader.
1295 // The leader or nextleader will dominate in all cases where there is an
1296 // equivalent that is higher up in the dom tree.
1297 // We can't *only* check them, however, because the
1298 // dominator tree could have an infinite number of non-dominating siblings
1299 // with instructions that are in the right congruence class.
1300 // A
1301 // B C D E F G
1302 // |
1303 // H
1304 // Instruction U could be in H, with equivalents in every other sibling.
1305 // Depending on the rpo order picked, the leader could be the equivalent in
1306 // any of these siblings.
1307 if (!CC)
1308 return false;
1309 if (alwaysAvailable(CC->getLeader()))
1310 return true;
1311 if (DT->dominates(cast<Instruction>(CC->getLeader()), U))
1312 return true;
1313 if (CC->getNextLeader().first &&
1314 DT->dominates(cast<Instruction>(CC->getNextLeader().first), U))
1315 return true;
1316 return llvm::any_of(*CC, [&](const Value *Member) {
1317 return Member != CC->getLeader() &&
1318 DT->dominates(cast<Instruction>(Member), U);
1319 });
1320}
1321
1322// See if we have a congruence class and leader for this operand, and if so,
1323// return it. Otherwise, return the operand itself.
1324Value *NewGVN::lookupOperandLeader(Value *V) const {
1325 CongruenceClass *CC = ValueToClass.lookup(V);
1326 if (CC) {
1327 // Everything in TOP is represented by poison, as it can be any value.
1328 // We do have to make sure we get the type right though, so we can't set the
1329 // RepLeader to poison.
1330 if (CC == TOPClass)
1331 return PoisonValue::get(V->getType());
1332 return CC->getStoredValue() ? CC->getStoredValue() : CC->getLeader();
1333 }
1334
1335 return V;
1336}
1337
1338const MemoryAccess *NewGVN::lookupMemoryLeader(const MemoryAccess *MA) const {
1339 auto *CC = getMemoryClass(MA);
1340 assert(CC->getMemoryLeader() &&
1341 "Every MemoryAccess should be mapped to a congruence class with a "
1342 "representative memory access");
1343 return CC->getMemoryLeader();
1344}
1345
1346// Return true if the MemoryAccess is really equivalent to everything. This is
1347// equivalent to the lattice value "TOP" in most lattices. This is the initial
1348// state of all MemoryAccesses.
1349bool NewGVN::isMemoryAccessTOP(const MemoryAccess *MA) const {
1350 return getMemoryClass(MA) == TOPClass;
1351}
1352
1353LoadExpression *NewGVN::createLoadExpression(Type *LoadType, Value *PointerOp,
1354 LoadInst *LI,
1355 const MemoryAccess *MA) const {
1356 auto *E =
1357 new (ExpressionAllocator) LoadExpression(1, LI, lookupMemoryLeader(MA));
1358 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1359 E->setType(LoadType);
1360
1361 // Give store and loads same opcode so they value number together.
1362 E->setOpcode(0);
1363 E->op_push_back(PointerOp);
1364
1365 // TODO: Value number heap versions. We may be able to discover
1366 // things alias analysis can't on it's own (IE that a store and a
1367 // load have the same value, and thus, it isn't clobbering the load).
1368 return E;
1369}
1370
1371const StoreExpression *
1372NewGVN::createStoreExpression(StoreInst *SI, const MemoryAccess *MA) const {
1373 auto *StoredValueLeader = lookupOperandLeader(SI->getValueOperand());
1374 auto *E = new (ExpressionAllocator)
1375 StoreExpression(SI->getNumOperands(), SI, StoredValueLeader, MA);
1376 E->allocateOperands(ArgRecycler, ExpressionAllocator);
1377 E->setType(SI->getValueOperand()->getType());
1378
1379 // Give store and loads same opcode so they value number together.
1380 E->setOpcode(0);
1381 E->op_push_back(lookupOperandLeader(SI->getPointerOperand()));
1382
1383 // TODO: Value number heap versions. We may be able to discover
1384 // things alias analysis can't on it's own (IE that a store and a
1385 // load have the same value, and thus, it isn't clobbering the load).
1386 return E;
1387}
1388
1389const Expression *NewGVN::performSymbolicStoreEvaluation(Instruction *I) const {
1390 // Unlike loads, we never try to eliminate stores, so we do not check if they
1391 // are simple and avoid value numbering them.
1392 auto *SI = cast<StoreInst>(I);
1393 auto *StoreAccess = getMemoryAccess(SI);
1394 // Get the expression, if any, for the RHS of the MemoryDef.
1395 const MemoryAccess *StoreRHS = StoreAccess->getDefiningAccess();
1397 StoreRHS = MSSAWalker->getClobberingMemoryAccess(StoreAccess);
1398 // If we bypassed the use-def chains, make sure we add a use.
1399 StoreRHS = lookupMemoryLeader(StoreRHS);
1400 if (StoreRHS != StoreAccess->getDefiningAccess())
1401 addMemoryUsers(StoreRHS, StoreAccess);
1402 // If we are defined by ourselves, use the live on entry def.
1403 if (StoreRHS == StoreAccess)
1404 StoreRHS = MSSA->getLiveOnEntryDef();
1405
1406 if (SI->isSimple()) {
1407 // See if we are defined by a previous store expression, it already has a
1408 // value, and it's the same value as our current store. FIXME: Right now, we
1409 // only do this for simple stores, we should expand to cover memcpys, etc.
1410 const auto *LastStore = createStoreExpression(SI, StoreRHS);
1411 const auto *LastCC = ExpressionToClass.lookup(LastStore);
1412 // We really want to check whether the expression we matched was a store. No
1413 // easy way to do that. However, we can check that the class we found has a
1414 // store, which, assuming the value numbering state is not corrupt, is
1415 // sufficient, because we must also be equivalent to that store's expression
1416 // for it to be in the same class as the load.
1417 if (LastCC && LastCC->getStoredValue() == LastStore->getStoredValue())
1418 return LastStore;
1419 // Also check if our value operand is defined by a load of the same memory
1420 // location, and the memory state is the same as it was then (otherwise, it
1421 // could have been overwritten later. See test32 in
1422 // transforms/DeadStoreElimination/simple.ll).
1423 if (auto *LI = dyn_cast<LoadInst>(LastStore->getStoredValue()))
1424 if ((lookupOperandLeader(LI->getPointerOperand()) ==
1425 LastStore->getOperand(0)) &&
1426 (lookupMemoryLeader(getMemoryAccess(LI)->getDefiningAccess()) ==
1427 StoreRHS))
1428 return LastStore;
1429 deleteExpression(LastStore);
1430 }
1431
1432 // If the store is not equivalent to anything, value number it as a store that
1433 // produces a unique memory state (instead of using it's MemoryUse, we use
1434 // it's MemoryDef).
1435 return createStoreExpression(SI, StoreAccess);
1436}
1437
1438// See if we can extract the value of a loaded pointer from a load, a store, or
1439// a memory instruction.
1440const Expression *
1441NewGVN::performSymbolicLoadCoercion(Type *LoadType, Value *LoadPtr,
1442 LoadInst *LI, Instruction *DepInst,
1443 MemoryAccess *DefiningAccess) const {
1444 assert((!LI || LI->isSimple()) && "Not a simple load");
1445 if (auto *DepSI = dyn_cast<StoreInst>(DepInst)) {
1446 // Can't forward from non-atomic to atomic without violating memory model.
1447 // Also don't need to coerce if they are the same type, we will just
1448 // propagate.
1449 if (LI->isAtomic() > DepSI->isAtomic() ||
1450 LoadType == DepSI->getValueOperand()->getType())
1451 return nullptr;
1452 int Offset = analyzeLoadFromClobberingStore(LoadType, LoadPtr, DepSI, DL);
1453 if (Offset >= 0) {
1454 if (auto *C = dyn_cast<Constant>(
1455 lookupOperandLeader(DepSI->getValueOperand()))) {
1456 if (Constant *Res =
1457 getConstantStoreValueForLoad(C, Offset, LoadType, DL)) {
1458 LLVM_DEBUG(dbgs() << "Coercing load from store " << *DepSI
1459 << " to constant " << *Res << "\n");
1460 return createConstantExpression(Res);
1461 }
1462 }
1463 }
1464 } else if (auto *DepLI = dyn_cast<LoadInst>(DepInst)) {
1465 // Can't forward from non-atomic to atomic without violating memory model.
1466 if (LI->isAtomic() > DepLI->isAtomic())
1467 return nullptr;
1468 int Offset = analyzeLoadFromClobberingLoad(LoadType, LoadPtr, DepLI, DL);
1469 if (Offset >= 0) {
1470 // We can coerce a constant load into a load.
1471 if (auto *C = dyn_cast<Constant>(lookupOperandLeader(DepLI)))
1472 if (auto *PossibleConstant =
1473 getConstantLoadValueForLoad(C, Offset, LoadType, DL)) {
1474 LLVM_DEBUG(dbgs() << "Coercing load from load " << *LI
1475 << " to constant " << *PossibleConstant << "\n");
1476 return createConstantExpression(PossibleConstant);
1477 }
1478 }
1479 } else if (auto *DepMI = dyn_cast<MemIntrinsic>(DepInst)) {
1480 int Offset = analyzeLoadFromClobberingMemInst(LoadType, LoadPtr, DepMI, DL);
1481 if (Offset >= 0) {
1482 if (auto *PossibleConstant =
1483 getConstantMemInstValueForLoad(DepMI, Offset, LoadType, DL)) {
1484 LLVM_DEBUG(dbgs() << "Coercing load from meminst " << *DepMI
1485 << " to constant " << *PossibleConstant << "\n");
1486 return createConstantExpression(PossibleConstant);
1487 }
1488 }
1489 }
1490
1491 // All of the below are only true if the loaded pointer is produced
1492 // by the dependent instruction.
1493 if (LoadPtr != lookupOperandLeader(DepInst) &&
1494 !AA->isMustAlias(LoadPtr, DepInst))
1495 return nullptr;
1496 // If this load really doesn't depend on anything, then we must be loading an
1497 // undef value. This can happen when loading for a fresh allocation with no
1498 // intervening stores, for example. Note that this is only true in the case
1499 // that the result of the allocation is pointer equal to the load ptr.
1500 if (isa<AllocaInst>(DepInst)) {
1501 return createConstantExpression(UndefValue::get(LoadType));
1502 }
1503 // If this load occurs either right after a lifetime begin,
1504 // then the loaded value is undefined.
1505 else if (auto *II = dyn_cast<IntrinsicInst>(DepInst)) {
1506 if (II->getIntrinsicID() == Intrinsic::lifetime_start)
1507 return createConstantExpression(UndefValue::get(LoadType));
1508 } else if (auto *InitVal =
1509 getInitialValueOfAllocation(DepInst, TLI, LoadType))
1510 return createConstantExpression(InitVal);
1511
1512 return nullptr;
1513}
1514
1515const Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I) const {
1516 auto *LI = cast<LoadInst>(I);
1517
1518 // We can eliminate in favor of non-simple loads, but we won't be able to
1519 // eliminate the loads themselves.
1520 if (!LI->isSimple())
1521 return nullptr;
1522
1523 Value *LoadAddressLeader = lookupOperandLeader(LI->getPointerOperand());
1524 // Load of undef is UB.
1525 if (isa<UndefValue>(LoadAddressLeader))
1526 return createConstantExpression(PoisonValue::get(LI->getType()));
1527 MemoryAccess *OriginalAccess = getMemoryAccess(I);
1528 MemoryAccess *DefiningAccess =
1529 MSSAWalker->getClobberingMemoryAccess(OriginalAccess);
1530
1531 if (!MSSA->isLiveOnEntryDef(DefiningAccess)) {
1532 if (auto *MD = dyn_cast<MemoryDef>(DefiningAccess)) {
1533 Instruction *DefiningInst = MD->getMemoryInst();
1534 // If the defining instruction is not reachable, replace with poison.
1535 if (!ReachableBlocks.count(DefiningInst->getParent()))
1536 return createConstantExpression(PoisonValue::get(LI->getType()));
1537 // This will handle stores and memory insts. We only do if it the
1538 // defining access has a different type, or it is a pointer produced by
1539 // certain memory operations that cause the memory to have a fixed value
1540 // (IE things like calloc).
1541 if (const auto *CoercionResult =
1542 performSymbolicLoadCoercion(LI->getType(), LoadAddressLeader, LI,
1543 DefiningInst, DefiningAccess))
1544 return CoercionResult;
1545 }
1546 }
1547
1548 const auto *LE = createLoadExpression(LI->getType(), LoadAddressLeader, LI,
1549 DefiningAccess);
1550 // If our MemoryLeader is not our defining access, add a use to the
1551 // MemoryLeader, so that we get reprocessed when it changes.
1552 if (LE->getMemoryLeader() != DefiningAccess)
1553 addMemoryUsers(LE->getMemoryLeader(), OriginalAccess);
1554 return LE;
1555}
1556
1557NewGVN::ExprResult
1558NewGVN::performSymbolicPredicateInfoEvaluation(IntrinsicInst *I) const {
1559 auto *PI = PredInfo->getPredicateInfoFor(I);
1560 if (!PI)
1561 return ExprResult::none();
1562
1563 LLVM_DEBUG(dbgs() << "Found predicate info from instruction !\n");
1564
1565 const std::optional<PredicateConstraint> &Constraint = PI->getConstraint();
1566 if (!Constraint)
1567 return ExprResult::none();
1568
1569 CmpInst::Predicate Predicate = Constraint->Predicate;
1570 Value *CmpOp0 = I->getOperand(0);
1571 Value *CmpOp1 = Constraint->OtherOp;
1572
1573 Value *FirstOp = lookupOperandLeader(CmpOp0);
1574 Value *SecondOp = lookupOperandLeader(CmpOp1);
1575 Value *AdditionallyUsedValue = CmpOp0;
1576
1577 // Sort the ops.
1578 if (shouldSwapOperandsForIntrinsic(FirstOp, SecondOp, I)) {
1579 std::swap(FirstOp, SecondOp);
1581 AdditionallyUsedValue = CmpOp1;
1582 }
1583
1584 if (Predicate == CmpInst::ICMP_EQ)
1585 return ExprResult::some(createVariableOrConstant(FirstOp),
1586 AdditionallyUsedValue, PI);
1587
1588 // Handle the special case of floating point.
1589 if (Predicate == CmpInst::FCMP_OEQ && isa<ConstantFP>(FirstOp) &&
1590 !cast<ConstantFP>(FirstOp)->isZero())
1591 return ExprResult::some(createConstantExpression(cast<Constant>(FirstOp)),
1592 AdditionallyUsedValue, PI);
1593
1594 return ExprResult::none();
1595}
1596
1597// Evaluate read only and pure calls, and create an expression result.
1598NewGVN::ExprResult NewGVN::performSymbolicCallEvaluation(Instruction *I) const {
1599 auto *CI = cast<CallInst>(I);
1600 if (auto *II = dyn_cast<IntrinsicInst>(I)) {
1601 // Intrinsics with the returned attribute are copies of arguments.
1602 if (auto *ReturnedValue = II->getReturnedArgOperand()) {
1603 if (II->getIntrinsicID() == Intrinsic::ssa_copy)
1604 if (auto Res = performSymbolicPredicateInfoEvaluation(II))
1605 return Res;
1606 return ExprResult::some(createVariableOrConstant(ReturnedValue));
1607 }
1608 }
1609
1610 // FIXME: Currently the calls which may access the thread id may
1611 // be considered as not accessing the memory. But this is
1612 // problematic for coroutines, since coroutines may resume in a
1613 // different thread. So we disable the optimization here for the
1614 // correctness. However, it may block many other correct
1615 // optimizations. Revert this one when we detect the memory
1616 // accessing kind more precisely.
1617 if (CI->getFunction()->isPresplitCoroutine())
1618 return ExprResult::none();
1619
1620 if (AA->doesNotAccessMemory(CI)) {
1621 return ExprResult::some(
1622 createCallExpression(CI, TOPClass->getMemoryLeader()));
1623 } else if (AA->onlyReadsMemory(CI)) {
1624 if (auto *MA = MSSA->getMemoryAccess(CI)) {
1625 auto *DefiningAccess = MSSAWalker->getClobberingMemoryAccess(MA);
1626 return ExprResult::some(createCallExpression(CI, DefiningAccess));
1627 } else // MSSA determined that CI does not access memory.
1628 return ExprResult::some(
1629 createCallExpression(CI, TOPClass->getMemoryLeader()));
1630 }
1631 return ExprResult::none();
1632}
1633
1634// Retrieve the memory class for a given MemoryAccess.
1635CongruenceClass *NewGVN::getMemoryClass(const MemoryAccess *MA) const {
1636 auto *Result = MemoryAccessToClass.lookup(MA);
1637 assert(Result && "Should have found memory class");
1638 return Result;
1639}
1640
1641// Update the MemoryAccess equivalence table to say that From is equal to To,
1642// and return true if this is different from what already existed in the table.
1643bool NewGVN::setMemoryClass(const MemoryAccess *From,
1644 CongruenceClass *NewClass) {
1645 assert(NewClass &&
1646 "Every MemoryAccess should be getting mapped to a non-null class");
1647 LLVM_DEBUG(dbgs() << "Setting " << *From);
1648 LLVM_DEBUG(dbgs() << " equivalent to congruence class ");
1649 LLVM_DEBUG(dbgs() << NewClass->getID()
1650 << " with current MemoryAccess leader ");
1651 LLVM_DEBUG(dbgs() << *NewClass->getMemoryLeader() << "\n");
1652
1653 auto LookupResult = MemoryAccessToClass.find(From);
1654 bool Changed = false;
1655 // If it's already in the table, see if the value changed.
1656 if (LookupResult != MemoryAccessToClass.end()) {
1657 auto *OldClass = LookupResult->second;
1658 if (OldClass != NewClass) {
1659 // If this is a phi, we have to handle memory member updates.
1660 if (auto *MP = dyn_cast<MemoryPhi>(From)) {
1661 OldClass->memory_erase(MP);
1662 NewClass->memory_insert(MP);
1663 // This may have killed the class if it had no non-memory members
1664 if (OldClass->getMemoryLeader() == From) {
1665 if (OldClass->definesNoMemory()) {
1666 OldClass->setMemoryLeader(nullptr);
1667 } else {
1668 OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
1669 LLVM_DEBUG(dbgs() << "Memory class leader change for class "
1670 << OldClass->getID() << " to "
1671 << *OldClass->getMemoryLeader()
1672 << " due to removal of a memory member " << *From
1673 << "\n");
1674 markMemoryLeaderChangeTouched(OldClass);
1675 }
1676 }
1677 }
1678 // It wasn't equivalent before, and now it is.
1679 LookupResult->second = NewClass;
1680 Changed = true;
1681 }
1682 }
1683
1684 return Changed;
1685}
1686
1687// Determine if a instruction is cycle-free. That means the values in the
1688// instruction don't depend on any expressions that can change value as a result
1689// of the instruction. For example, a non-cycle free instruction would be v =
1690// phi(0, v+1).
1691bool NewGVN::isCycleFree(const Instruction *I) const {
1692 // In order to compute cycle-freeness, we do SCC finding on the instruction,
1693 // and see what kind of SCC it ends up in. If it is a singleton, it is
1694 // cycle-free. If it is not in a singleton, it is only cycle free if the
1695 // other members are all phi nodes (as they do not compute anything, they are
1696 // copies).
1697 auto ICS = InstCycleState.lookup(I);
1698 if (ICS == ICS_Unknown) {
1699 SCCFinder.Start(I);
1700 auto &SCC = SCCFinder.getComponentFor(I);
1701 // It's cycle free if it's size 1 or the SCC is *only* phi nodes.
1702 if (SCC.size() == 1)
1703 InstCycleState.insert({I, ICS_CycleFree});
1704 else {
1705 bool AllPhis = llvm::all_of(SCC, [](const Value *V) {
1706 return isa<PHINode>(V) || isCopyOfAPHI(V);
1707 });
1708 ICS = AllPhis ? ICS_CycleFree : ICS_Cycle;
1709 for (const auto *Member : SCC)
1710 if (auto *MemberPhi = dyn_cast<PHINode>(Member))
1711 InstCycleState.insert({MemberPhi, ICS});
1712 }
1713 }
1714 if (ICS == ICS_Cycle)
1715 return false;
1716 return true;
1717}
1718
1719// Evaluate PHI nodes symbolically and create an expression result.
1720const Expression *
1721NewGVN::performSymbolicPHIEvaluation(ArrayRef<ValPair> PHIOps,
1722 Instruction *I,
1723 BasicBlock *PHIBlock) const {
1724 // True if one of the incoming phi edges is a backedge.
1725 bool HasBackedge = false;
1726 // All constant tracks the state of whether all the *original* phi operands
1727 // This is really shorthand for "this phi cannot cycle due to forward
1728 // change in value of the phi is guaranteed not to later change the value of
1729 // the phi. IE it can't be v = phi(undef, v+1)
1730 bool OriginalOpsConstant = true;
1731 auto *E = cast<PHIExpression>(createPHIExpression(
1732 PHIOps, I, PHIBlock, HasBackedge, OriginalOpsConstant));
1733 // We match the semantics of SimplifyPhiNode from InstructionSimplify here.
1734 // See if all arguments are the same.
1735 // We track if any were undef because they need special handling.
1736 bool HasUndef = false, HasPoison = false;
1737 auto Filtered = make_filter_range(E->operands(), [&](Value *Arg) {
1738 if (isa<PoisonValue>(Arg)) {
1739 HasPoison = true;
1740 return false;
1741 }
1742 if (isa<UndefValue>(Arg)) {
1743 HasUndef = true;
1744 return false;
1745 }
1746 return true;
1747 });
1748 // If we are left with no operands, it's dead.
1749 if (Filtered.empty()) {
1750 // If it has undef or poison at this point, it means there are no-non-undef
1751 // arguments, and thus, the value of the phi node must be undef.
1752 if (HasUndef) {
1753 LLVM_DEBUG(
1754 dbgs() << "PHI Node " << *I
1755 << " has no non-undef arguments, valuing it as undef\n");
1756 return createConstantExpression(UndefValue::get(I->getType()));
1757 }
1758 if (HasPoison) {
1759 LLVM_DEBUG(
1760 dbgs() << "PHI Node " << *I
1761 << " has no non-poison arguments, valuing it as poison\n");
1762 return createConstantExpression(PoisonValue::get(I->getType()));
1763 }
1764
1765 LLVM_DEBUG(dbgs() << "No arguments of PHI node " << *I << " are live\n");
1766 deleteExpression(E);
1767 return createDeadExpression();
1768 }
1769 Value *AllSameValue = *(Filtered.begin());
1770 ++Filtered.begin();
1771 // Can't use std::equal here, sadly, because filter.begin moves.
1772 if (llvm::all_of(Filtered, [&](Value *Arg) { return Arg == AllSameValue; })) {
1773 // Can't fold phi(undef, X) -> X unless X can't be poison (thus X is undef
1774 // in the worst case).
1775 if (HasUndef && !isGuaranteedNotToBePoison(AllSameValue, AC, nullptr, DT))
1776 return E;
1777
1778 // In LLVM's non-standard representation of phi nodes, it's possible to have
1779 // phi nodes with cycles (IE dependent on other phis that are .... dependent
1780 // on the original phi node), especially in weird CFG's where some arguments
1781 // are unreachable, or uninitialized along certain paths. This can cause
1782 // infinite loops during evaluation. We work around this by not trying to
1783 // really evaluate them independently, but instead using a variable
1784 // expression to say if one is equivalent to the other.
1785 // We also special case undef/poison, so that if we have an undef, we can't
1786 // use the common value unless it dominates the phi block.
1787 if (HasPoison || HasUndef) {
1788 // If we have undef and at least one other value, this is really a
1789 // multivalued phi, and we need to know if it's cycle free in order to
1790 // evaluate whether we can ignore the undef. The other parts of this are
1791 // just shortcuts. If there is no backedge, or all operands are
1792 // constants, it also must be cycle free.
1793 if (HasBackedge && !OriginalOpsConstant &&
1794 !isa<UndefValue>(AllSameValue) && !isCycleFree(I))
1795 return E;
1796
1797 // Only have to check for instructions
1798 if (auto *AllSameInst = dyn_cast<Instruction>(AllSameValue))
1799 if (!someEquivalentDominates(AllSameInst, I))
1800 return E;
1801 }
1802 // Can't simplify to something that comes later in the iteration.
1803 // Otherwise, when and if it changes congruence class, we will never catch
1804 // up. We will always be a class behind it.
1805 if (isa<Instruction>(AllSameValue) &&
1806 InstrToDFSNum(AllSameValue) > InstrToDFSNum(I))
1807 return E;
1808 NumGVNPhisAllSame++;
1809 LLVM_DEBUG(dbgs() << "Simplified PHI node " << *I << " to " << *AllSameValue
1810 << "\n");
1811 deleteExpression(E);
1812 return createVariableOrConstant(AllSameValue);
1813 }
1814 return E;
1815}
1816
1817const Expression *
1818NewGVN::performSymbolicAggrValueEvaluation(Instruction *I) const {
1819 if (auto *EI = dyn_cast<ExtractValueInst>(I)) {
1820 auto *WO = dyn_cast<WithOverflowInst>(EI->getAggregateOperand());
1821 if (WO && EI->getNumIndices() == 1 && *EI->idx_begin() == 0)
1822 // EI is an extract from one of our with.overflow intrinsics. Synthesize
1823 // a semantically equivalent expression instead of an extract value
1824 // expression.
1825 return createBinaryExpression(WO->getBinaryOp(), EI->getType(),
1826 WO->getLHS(), WO->getRHS(), I);
1827 }
1828
1829 return createAggregateValueExpression(I);
1830}
1831
1832NewGVN::ExprResult NewGVN::performSymbolicCmpEvaluation(Instruction *I) const {
1833 assert(isa<CmpInst>(I) && "Expected a cmp instruction.");
1834
1835 auto *CI = cast<CmpInst>(I);
1836 // See if our operands are equal to those of a previous predicate, and if so,
1837 // if it implies true or false.
1838 auto Op0 = lookupOperandLeader(CI->getOperand(0));
1839 auto Op1 = lookupOperandLeader(CI->getOperand(1));
1840 auto OurPredicate = CI->getPredicate();
1841 if (shouldSwapOperands(Op0, Op1)) {
1842 std::swap(Op0, Op1);
1843 OurPredicate = CI->getSwappedPredicate();
1844 }
1845
1846 // Avoid processing the same info twice.
1847 const PredicateBase *LastPredInfo = nullptr;
1848 // See if we know something about the comparison itself, like it is the target
1849 // of an assume.
1850 auto *CmpPI = PredInfo->getPredicateInfoFor(I);
1851 if (isa_and_nonnull<PredicateAssume>(CmpPI))
1852 return ExprResult::some(
1853 createConstantExpression(ConstantInt::getTrue(CI->getType())));
1854
1855 if (Op0 == Op1) {
1856 // This condition does not depend on predicates, no need to add users
1857 if (CI->isTrueWhenEqual())
1858 return ExprResult::some(
1859 createConstantExpression(ConstantInt::getTrue(CI->getType())));
1860 else if (CI->isFalseWhenEqual())
1861 return ExprResult::some(
1862 createConstantExpression(ConstantInt::getFalse(CI->getType())));
1863 }
1864
1865 // NOTE: Because we are comparing both operands here and below, and using
1866 // previous comparisons, we rely on fact that predicateinfo knows to mark
1867 // comparisons that use renamed operands as users of the earlier comparisons.
1868 // It is *not* enough to just mark predicateinfo renamed operands as users of
1869 // the earlier comparisons, because the *other* operand may have changed in a
1870 // previous iteration.
1871 // Example:
1872 // icmp slt %a, %b
1873 // %b.0 = ssa.copy(%b)
1874 // false branch:
1875 // icmp slt %c, %b.0
1876
1877 // %c and %a may start out equal, and thus, the code below will say the second
1878 // %icmp is false. c may become equal to something else, and in that case the
1879 // %second icmp *must* be reexamined, but would not if only the renamed
1880 // %operands are considered users of the icmp.
1881
1882 // *Currently* we only check one level of comparisons back, and only mark one
1883 // level back as touched when changes happen. If you modify this code to look
1884 // back farther through comparisons, you *must* mark the appropriate
1885 // comparisons as users in PredicateInfo.cpp, or you will cause bugs. See if
1886 // we know something just from the operands themselves
1887
1888 // See if our operands have predicate info, so that we may be able to derive
1889 // something from a previous comparison.
1890 for (const auto &Op : CI->operands()) {
1891 auto *PI = PredInfo->getPredicateInfoFor(Op);
1892 if (const auto *PBranch = dyn_cast_or_null<PredicateBranch>(PI)) {
1893 if (PI == LastPredInfo)
1894 continue;
1895 LastPredInfo = PI;
1896 // In phi of ops cases, we may have predicate info that we are evaluating
1897 // in a different context.
1898 if (!DT->dominates(PBranch->To, getBlockForValue(I)))
1899 continue;
1900 // TODO: Along the false edge, we may know more things too, like
1901 // icmp of
1902 // same operands is false.
1903 // TODO: We only handle actual comparison conditions below, not
1904 // and/or.
1905 auto *BranchCond = dyn_cast<CmpInst>(PBranch->Condition);
1906 if (!BranchCond)
1907 continue;
1908 auto *BranchOp0 = lookupOperandLeader(BranchCond->getOperand(0));
1909 auto *BranchOp1 = lookupOperandLeader(BranchCond->getOperand(1));
1910 auto BranchPredicate = BranchCond->getPredicate();
1911 if (shouldSwapOperands(BranchOp0, BranchOp1)) {
1912 std::swap(BranchOp0, BranchOp1);
1913 BranchPredicate = BranchCond->getSwappedPredicate();
1914 }
1915 if (BranchOp0 == Op0 && BranchOp1 == Op1) {
1916 if (PBranch->TrueEdge) {
1917 // If we know the previous predicate is true and we are in the true
1918 // edge then we may be implied true or false.
1919 if (CmpInst::isImpliedTrueByMatchingCmp(BranchPredicate,
1920 OurPredicate)) {
1921 return ExprResult::some(
1922 createConstantExpression(ConstantInt::getTrue(CI->getType())),
1923 PI);
1924 }
1925
1926 if (CmpInst::isImpliedFalseByMatchingCmp(BranchPredicate,
1927 OurPredicate)) {
1928 return ExprResult::some(
1929 createConstantExpression(ConstantInt::getFalse(CI->getType())),
1930 PI);
1931 }
1932 } else {
1933 // Just handle the ne and eq cases, where if we have the same
1934 // operands, we may know something.
1935 if (BranchPredicate == OurPredicate) {
1936 // Same predicate, same ops,we know it was false, so this is false.
1937 return ExprResult::some(
1938 createConstantExpression(ConstantInt::getFalse(CI->getType())),
1939 PI);
1940 } else if (BranchPredicate ==
1941 CmpInst::getInversePredicate(OurPredicate)) {
1942 // Inverse predicate, we know the other was false, so this is true.
1943 return ExprResult::some(
1944 createConstantExpression(ConstantInt::getTrue(CI->getType())),
1945 PI);
1946 }
1947 }
1948 }
1949 }
1950 }
1951 // Create expression will take care of simplifyCmpInst
1952 return createExpression(I);
1953}
1954
1955// Substitute and symbolize the value before value numbering.
1956NewGVN::ExprResult
1957NewGVN::performSymbolicEvaluation(Value *V,
1958 SmallPtrSetImpl<Value *> &Visited) const {
1959
1960 const Expression *E = nullptr;
1961 if (auto *C = dyn_cast<Constant>(V))
1962 E = createConstantExpression(C);
1963 else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
1964 E = createVariableExpression(V);
1965 } else {
1966 // TODO: memory intrinsics.
1967 // TODO: Some day, we should do the forward propagation and reassociation
1968 // parts of the algorithm.
1969 auto *I = cast<Instruction>(V);
1970 switch (I->getOpcode()) {
1971 case Instruction::ExtractValue:
1972 case Instruction::InsertValue:
1973 E = performSymbolicAggrValueEvaluation(I);
1974 break;
1975 case Instruction::PHI: {
1977 auto *PN = cast<PHINode>(I);
1978 for (unsigned i = 0; i < PN->getNumOperands(); ++i)
1979 Ops.push_back({PN->getIncomingValue(i), PN->getIncomingBlock(i)});
1980 // Sort to ensure the invariant createPHIExpression requires is met.
1981 sortPHIOps(Ops);
1982 E = performSymbolicPHIEvaluation(Ops, I, getBlockForValue(I));
1983 } break;
1984 case Instruction::Call:
1985 return performSymbolicCallEvaluation(I);
1986 break;
1987 case Instruction::Store:
1988 E = performSymbolicStoreEvaluation(I);
1989 break;
1990 case Instruction::Load:
1991 E = performSymbolicLoadEvaluation(I);
1992 break;
1993 case Instruction::BitCast:
1994 case Instruction::AddrSpaceCast:
1995 return createExpression(I);
1996 break;
1997 case Instruction::ICmp:
1998 case Instruction::FCmp:
1999 return performSymbolicCmpEvaluation(I);
2000 break;
2001 case Instruction::FNeg:
2002 case Instruction::Add:
2003 case Instruction::FAdd:
2004 case Instruction::Sub:
2005 case Instruction::FSub:
2006 case Instruction::Mul:
2007 case Instruction::FMul:
2008 case Instruction::UDiv:
2009 case Instruction::SDiv:
2010 case Instruction::FDiv:
2011 case Instruction::URem:
2012 case Instruction::SRem:
2013 case Instruction::FRem:
2014 case Instruction::Shl:
2015 case Instruction::LShr:
2016 case Instruction::AShr:
2017 case Instruction::And:
2018 case Instruction::Or:
2019 case Instruction::Xor:
2020 case Instruction::Trunc:
2021 case Instruction::ZExt:
2022 case Instruction::SExt:
2023 case Instruction::FPToUI:
2024 case Instruction::FPToSI:
2025 case Instruction::UIToFP:
2026 case Instruction::SIToFP:
2027 case Instruction::FPTrunc:
2028 case Instruction::FPExt:
2029 case Instruction::PtrToInt:
2030 case Instruction::IntToPtr:
2031 case Instruction::Select:
2032 case Instruction::ExtractElement:
2033 case Instruction::InsertElement:
2034 case Instruction::GetElementPtr:
2035 return createExpression(I);
2036 break;
2037 case Instruction::ShuffleVector:
2038 // FIXME: Add support for shufflevector to createExpression.
2039 return ExprResult::none();
2040 default:
2041 return ExprResult::none();
2042 }
2043 }
2044 return ExprResult::some(E);
2045}
2046
2047// Look up a container of values/instructions in a map, and touch all the
2048// instructions in the container. Then erase value from the map.
2049template <typename Map, typename KeyType>
2050void NewGVN::touchAndErase(Map &M, const KeyType &Key) {
2051 const auto Result = M.find_as(Key);
2052 if (Result != M.end()) {
2053 for (const typename Map::mapped_type::value_type Mapped : Result->second)
2054 TouchedInstructions.set(InstrToDFSNum(Mapped));
2055 M.erase(Result);
2056 }
2057}
2058
2059void NewGVN::addAdditionalUsers(Value *To, Value *User) const {
2060 assert(User && To != User);
2061 if (isa<Instruction>(To))
2062 AdditionalUsers[To].insert(User);
2063}
2064
2065void NewGVN::addAdditionalUsers(ExprResult &Res, Instruction *User) const {
2066 if (Res.ExtraDep && Res.ExtraDep != User)
2067 addAdditionalUsers(Res.ExtraDep, User);
2068 Res.ExtraDep = nullptr;
2069
2070 if (Res.PredDep) {
2071 if (const auto *PBranch = dyn_cast<PredicateBranch>(Res.PredDep))
2072 PredicateToUsers[PBranch->Condition].insert(User);
2073 else if (const auto *PAssume = dyn_cast<PredicateAssume>(Res.PredDep))
2074 PredicateToUsers[PAssume->Condition].insert(User);
2075 }
2076 Res.PredDep = nullptr;
2077}
2078
2079void NewGVN::markUsersTouched(Value *V) {
2080 // Now mark the users as touched.
2081 for (auto *User : V->users()) {
2082 assert(isa<Instruction>(User) && "Use of value not within an instruction?");
2083 TouchedInstructions.set(InstrToDFSNum(User));
2084 }
2085 touchAndErase(AdditionalUsers, V);
2086}
2087
2088void NewGVN::addMemoryUsers(const MemoryAccess *To, MemoryAccess *U) const {
2089 LLVM_DEBUG(dbgs() << "Adding memory user " << *U << " to " << *To << "\n");
2090 MemoryToUsers[To].insert(U);
2091}
2092
2093void NewGVN::markMemoryDefTouched(const MemoryAccess *MA) {
2094 TouchedInstructions.set(MemoryToDFSNum(MA));
2095}
2096
2097void NewGVN::markMemoryUsersTouched(const MemoryAccess *MA) {
2098 if (isa<MemoryUse>(MA))
2099 return;
2100 for (const auto *U : MA->users())
2101 TouchedInstructions.set(MemoryToDFSNum(U));
2102 touchAndErase(MemoryToUsers, MA);
2103}
2104
2105// Touch all the predicates that depend on this instruction.
2106void NewGVN::markPredicateUsersTouched(Instruction *I) {
2107 touchAndErase(PredicateToUsers, I);
2108}
2109
2110// Mark users affected by a memory leader change.
2111void NewGVN::markMemoryLeaderChangeTouched(CongruenceClass *CC) {
2112 for (const auto *M : CC->memory())
2113 markMemoryDefTouched(M);
2114}
2115
2116// Touch the instructions that need to be updated after a congruence class has a
2117// leader change, and mark changed values.
2118void NewGVN::markValueLeaderChangeTouched(CongruenceClass *CC) {
2119 for (auto *M : *CC) {
2120 if (auto *I = dyn_cast<Instruction>(M))
2121 TouchedInstructions.set(InstrToDFSNum(I));
2122 LeaderChanges.insert(M);
2123 }
2124}
2125
2126// Give a range of things that have instruction DFS numbers, this will return
2127// the member of the range with the smallest dfs number.
2128template <class T, class Range>
2129T *NewGVN::getMinDFSOfRange(const Range &R) const {
2130 std::pair<T *, unsigned> MinDFS = {nullptr, ~0U};
2131 for (const auto X : R) {
2132 auto DFSNum = InstrToDFSNum(X);
2133 if (DFSNum < MinDFS.second)
2134 MinDFS = {X, DFSNum};
2135 }
2136 return MinDFS.first;
2137}
2138
2139// This function returns the MemoryAccess that should be the next leader of
2140// congruence class CC, under the assumption that the current leader is going to
2141// disappear.
2142const MemoryAccess *NewGVN::getNextMemoryLeader(CongruenceClass *CC) const {
2143 // TODO: If this ends up to slow, we can maintain a next memory leader like we
2144 // do for regular leaders.
2145 // Make sure there will be a leader to find.
2146 assert(!CC->definesNoMemory() && "Can't get next leader if there is none");
2147 if (CC->getStoreCount() > 0) {
2148 if (auto *NL = dyn_cast_or_null<StoreInst>(CC->getNextLeader().first))
2149 return getMemoryAccess(NL);
2150 // Find the store with the minimum DFS number.
2151 auto *V = getMinDFSOfRange<Value>(make_filter_range(
2152 *CC, [&](const Value *V) { return isa<StoreInst>(V); }));
2153 return getMemoryAccess(cast<StoreInst>(V));
2154 }
2155 assert(CC->getStoreCount() == 0);
2156
2157 // Given our assertion, hitting this part must mean
2158 // !OldClass->memory_empty()
2159 if (CC->memory_size() == 1)
2160 return *CC->memory_begin();
2161 return getMinDFSOfRange<const MemoryPhi>(CC->memory());
2162}
2163
2164// This function returns the next value leader of a congruence class, under the
2165// assumption that the current leader is going away. This should end up being
2166// the next most dominating member.
2167Value *NewGVN::getNextValueLeader(CongruenceClass *CC) const {
2168 // We don't need to sort members if there is only 1, and we don't care about
2169 // sorting the TOP class because everything either gets out of it or is
2170 // unreachable.
2171
2172 if (CC->size() == 1 || CC == TOPClass) {
2173 return *(CC->begin());
2174 } else if (CC->getNextLeader().first) {
2175 ++NumGVNAvoidedSortedLeaderChanges;
2176 return CC->getNextLeader().first;
2177 } else {
2178 ++NumGVNSortedLeaderChanges;
2179 // NOTE: If this ends up to slow, we can maintain a dual structure for
2180 // member testing/insertion, or keep things mostly sorted, and sort only
2181 // here, or use SparseBitVector or ....
2182 return getMinDFSOfRange<Value>(*CC);
2183 }
2184}
2185
2186// Move a MemoryAccess, currently in OldClass, to NewClass, including updates to
2187// the memory members, etc for the move.
2188//
2189// The invariants of this function are:
2190//
2191// - I must be moving to NewClass from OldClass
2192// - The StoreCount of OldClass and NewClass is expected to have been updated
2193// for I already if it is a store.
2194// - The OldClass memory leader has not been updated yet if I was the leader.
2195void NewGVN::moveMemoryToNewCongruenceClass(Instruction *I,
2196 MemoryAccess *InstMA,
2197 CongruenceClass *OldClass,
2198 CongruenceClass *NewClass) {
2199 // If the leader is I, and we had a representative MemoryAccess, it should
2200 // be the MemoryAccess of OldClass.
2201 assert((!InstMA || !OldClass->getMemoryLeader() ||
2202 OldClass->getLeader() != I ||
2203 MemoryAccessToClass.lookup(OldClass->getMemoryLeader()) ==
2204 MemoryAccessToClass.lookup(InstMA)) &&
2205 "Representative MemoryAccess mismatch");
2206 // First, see what happens to the new class
2207 if (!NewClass->getMemoryLeader()) {
2208 // Should be a new class, or a store becoming a leader of a new class.
2209 assert(NewClass->size() == 1 ||
2210 (isa<StoreInst>(I) && NewClass->getStoreCount() == 1));
2211 NewClass->setMemoryLeader(InstMA);
2212 // Mark it touched if we didn't just create a singleton
2213 LLVM_DEBUG(dbgs() << "Memory class leader change for class "
2214 << NewClass->getID()
2215 << " due to new memory instruction becoming leader\n");
2216 markMemoryLeaderChangeTouched(NewClass);
2217 }
2218 setMemoryClass(InstMA, NewClass);
2219 // Now, fixup the old class if necessary
2220 if (OldClass->getMemoryLeader() == InstMA) {
2221 if (!OldClass->definesNoMemory()) {
2222 OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
2223 LLVM_DEBUG(dbgs() << "Memory class leader change for class "
2224 << OldClass->getID() << " to "
2225 << *OldClass->getMemoryLeader()
2226 << " due to removal of old leader " << *InstMA << "\n");
2227 markMemoryLeaderChangeTouched(OldClass);
2228 } else
2229 OldClass->setMemoryLeader(nullptr);
2230 }
2231}
2232
2233// Move a value, currently in OldClass, to be part of NewClass
2234// Update OldClass and NewClass for the move (including changing leaders, etc).
2235void NewGVN::moveValueToNewCongruenceClass(Instruction *I, const Expression *E,
2236 CongruenceClass *OldClass,
2237 CongruenceClass *NewClass) {
2238 if (I == OldClass->getNextLeader().first)
2239 OldClass->resetNextLeader();
2240
2241 OldClass->erase(I);
2242 NewClass->insert(I);
2243
2244 if (NewClass->getLeader() != I)
2245 NewClass->addPossibleNextLeader({I, InstrToDFSNum(I)});
2246 // Handle our special casing of stores.
2247 if (auto *SI = dyn_cast<StoreInst>(I)) {
2248 OldClass->decStoreCount();
2249 // Okay, so when do we want to make a store a leader of a class?
2250 // If we have a store defined by an earlier load, we want the earlier load
2251 // to lead the class.
2252 // If we have a store defined by something else, we want the store to lead
2253 // the class so everything else gets the "something else" as a value.
2254 // If we have a store as the single member of the class, we want the store
2255 // as the leader
2256 if (NewClass->getStoreCount() == 0 && !NewClass->getStoredValue()) {
2257 // If it's a store expression we are using, it means we are not equivalent
2258 // to something earlier.
2259 if (auto *SE = dyn_cast<StoreExpression>(E)) {
2260 NewClass->setStoredValue(SE->getStoredValue());
2261 markValueLeaderChangeTouched(NewClass);
2262 // Shift the new class leader to be the store
2263 LLVM_DEBUG(dbgs() << "Changing leader of congruence class "
2264 << NewClass->getID() << " from "
2265 << *NewClass->getLeader() << " to " << *SI
2266 << " because store joined class\n");
2267 // If we changed the leader, we have to mark it changed because we don't
2268 // know what it will do to symbolic evaluation.
2269 NewClass->setLeader(SI);
2270 }
2271 // We rely on the code below handling the MemoryAccess change.
2272 }
2273 NewClass->incStoreCount();
2274 }
2275 // True if there is no memory instructions left in a class that had memory
2276 // instructions before.
2277
2278 // If it's not a memory use, set the MemoryAccess equivalence
2279 auto *InstMA = dyn_cast_or_null<MemoryDef>(getMemoryAccess(I));
2280 if (InstMA)
2281 moveMemoryToNewCongruenceClass(I, InstMA, OldClass, NewClass);
2282 ValueToClass[I] = NewClass;
2283 // See if we destroyed the class or need to swap leaders.
2284 if (OldClass->empty() && OldClass != TOPClass) {
2285 if (OldClass->getDefiningExpr()) {
2286 LLVM_DEBUG(dbgs() << "Erasing expression " << *OldClass->getDefiningExpr()
2287 << " from table\n");
2288 // We erase it as an exact expression to make sure we don't just erase an
2289 // equivalent one.
2290 auto Iter = ExpressionToClass.find_as(
2291 ExactEqualsExpression(*OldClass->getDefiningExpr()));
2292 if (Iter != ExpressionToClass.end())
2293 ExpressionToClass.erase(Iter);
2294#ifdef EXPENSIVE_CHECKS
2295 assert(
2296 (*OldClass->getDefiningExpr() != *E || ExpressionToClass.lookup(E)) &&
2297 "We erased the expression we just inserted, which should not happen");
2298#endif
2299 }
2300 } else if (OldClass->getLeader() == I) {
2301 // When the leader changes, the value numbering of
2302 // everything may change due to symbolization changes, so we need to
2303 // reprocess.
2304 LLVM_DEBUG(dbgs() << "Value class leader change for class "
2305 << OldClass->getID() << "\n");
2306 ++NumGVNLeaderChanges;
2307 // Destroy the stored value if there are no more stores to represent it.
2308 // Note that this is basically clean up for the expression removal that
2309 // happens below. If we remove stores from a class, we may leave it as a
2310 // class of equivalent memory phis.
2311 if (OldClass->getStoreCount() == 0) {
2312 if (OldClass->getStoredValue())
2313 OldClass->setStoredValue(nullptr);
2314 }
2315 OldClass->setLeader(getNextValueLeader(OldClass));
2316 OldClass->resetNextLeader();
2317 markValueLeaderChangeTouched(OldClass);
2318 }
2319}
2320
2321// For a given expression, mark the phi of ops instructions that could have
2322// changed as a result.
2323void NewGVN::markPhiOfOpsChanged(const Expression *E) {
2324 touchAndErase(ExpressionToPhiOfOps, E);
2325}
2326
2327// Perform congruence finding on a given value numbering expression.
2328void NewGVN::performCongruenceFinding(Instruction *I, const Expression *E) {
2329 // This is guaranteed to return something, since it will at least find
2330 // TOP.
2331
2332 CongruenceClass *IClass = ValueToClass.lookup(I);
2333 assert(IClass && "Should have found a IClass");
2334 // Dead classes should have been eliminated from the mapping.
2335 assert(!IClass->isDead() && "Found a dead class");
2336
2337 CongruenceClass *EClass = nullptr;
2338 if (const auto *VE = dyn_cast<VariableExpression>(E)) {
2339 EClass = ValueToClass.lookup(VE->getVariableValue());
2340 } else if (isa<DeadExpression>(E)) {
2341 EClass = TOPClass;
2342 }
2343 if (!EClass) {
2344 auto lookupResult = ExpressionToClass.insert({E, nullptr});
2345
2346 // If it's not in the value table, create a new congruence class.
2347 if (lookupResult.second) {
2348 CongruenceClass *NewClass = createCongruenceClass(nullptr, E);
2349 auto place = lookupResult.first;
2350 place->second = NewClass;
2351
2352 // Constants and variables should always be made the leader.
2353 if (const auto *CE = dyn_cast<ConstantExpression>(E)) {
2354 NewClass->setLeader(CE->getConstantValue());
2355 } else if (const auto *SE = dyn_cast<StoreExpression>(E)) {
2356 StoreInst *SI = SE->getStoreInst();
2357 NewClass->setLeader(SI);
2358 NewClass->setStoredValue(SE->getStoredValue());
2359 // The RepMemoryAccess field will be filled in properly by the
2360 // moveValueToNewCongruenceClass call.
2361 } else {
2362 NewClass->setLeader(I);
2363 }
2364 assert(!isa<VariableExpression>(E) &&
2365 "VariableExpression should have been handled already");
2366
2367 EClass = NewClass;
2368 LLVM_DEBUG(dbgs() << "Created new congruence class for " << *I
2369 << " using expression " << *E << " at "
2370 << NewClass->getID() << " and leader "
2371 << *(NewClass->getLeader()));
2372 if (NewClass->getStoredValue())
2373 LLVM_DEBUG(dbgs() << " and stored value "
2374 << *(NewClass->getStoredValue()));
2375 LLVM_DEBUG(dbgs() << "\n");
2376 } else {
2377 EClass = lookupResult.first->second;
2378 if (isa<ConstantExpression>(E))
2379 assert((isa<Constant>(EClass->getLeader()) ||
2380 (EClass->getStoredValue() &&
2381 isa<Constant>(EClass->getStoredValue()))) &&
2382 "Any class with a constant expression should have a "
2383 "constant leader");
2384
2385 assert(EClass && "Somehow don't have an eclass");
2386
2387 assert(!EClass->isDead() && "We accidentally looked up a dead class");
2388 }
2389 }
2390 bool ClassChanged = IClass != EClass;
2391 bool LeaderChanged = LeaderChanges.erase(I);
2392 if (ClassChanged || LeaderChanged) {
2393 LLVM_DEBUG(dbgs() << "New class " << EClass->getID() << " for expression "
2394 << *E << "\n");
2395 if (ClassChanged) {
2396 moveValueToNewCongruenceClass(I, E, IClass, EClass);
2397 markPhiOfOpsChanged(E);
2398 }
2399
2400 markUsersTouched(I);
2401 if (MemoryAccess *MA = getMemoryAccess(I))
2402 markMemoryUsersTouched(MA);
2403 if (auto *CI = dyn_cast<CmpInst>(I))
2404 markPredicateUsersTouched(CI);
2405 }
2406 // If we changed the class of the store, we want to ensure nothing finds the
2407 // old store expression. In particular, loads do not compare against stored
2408 // value, so they will find old store expressions (and associated class
2409 // mappings) if we leave them in the table.
2410 if (ClassChanged && isa<StoreInst>(I)) {
2411 auto *OldE = ValueToExpression.lookup(I);
2412 // It could just be that the old class died. We don't want to erase it if we
2413 // just moved classes.
2414 if (OldE && isa<StoreExpression>(OldE) && *E != *OldE) {
2415 // Erase this as an exact expression to ensure we don't erase expressions
2416 // equivalent to it.
2417 auto Iter = ExpressionToClass.find_as(ExactEqualsExpression(*OldE));
2418 if (Iter != ExpressionToClass.end())
2419 ExpressionToClass.erase(Iter);
2420 }
2421 }
2422 ValueToExpression[I] = E;
2423}
2424
2425// Process the fact that Edge (from, to) is reachable, including marking
2426// any newly reachable blocks and instructions for processing.
2427void NewGVN::updateReachableEdge(BasicBlock *From, BasicBlock *To) {
2428 // Check if the Edge was reachable before.
2429 if (ReachableEdges.insert({From, To}).second) {
2430 // If this block wasn't reachable before, all instructions are touched.
2431 if (ReachableBlocks.insert(To).second) {
2432 LLVM_DEBUG(dbgs() << "Block " << getBlockName(To)
2433 << " marked reachable\n");
2434 const auto &InstRange = BlockInstRange.lookup(To);
2435 TouchedInstructions.set(InstRange.first, InstRange.second);
2436 } else {
2437 LLVM_DEBUG(dbgs() << "Block " << getBlockName(To)
2438 << " was reachable, but new edge {"
2439 << getBlockName(From) << "," << getBlockName(To)
2440 << "} to it found\n");
2441
2442 // We've made an edge reachable to an existing block, which may
2443 // impact predicates. Otherwise, only mark the phi nodes as touched, as
2444 // they are the only thing that depend on new edges. Anything using their
2445 // values will get propagated to if necessary.
2446 if (MemoryAccess *MemPhi = getMemoryAccess(To))
2447 TouchedInstructions.set(InstrToDFSNum(MemPhi));
2448
2449 // FIXME: We should just add a union op on a Bitvector and
2450 // SparseBitVector. We can do it word by word faster than we are doing it
2451 // here.
2452 for (auto InstNum : RevisitOnReachabilityChange[To])
2453 TouchedInstructions.set(InstNum);
2454 }
2455 }
2456}
2457
2458// Given a predicate condition (from a switch, cmp, or whatever) and a block,
2459// see if we know some constant value for it already.
2460Value *NewGVN::findConditionEquivalence(Value *Cond) const {
2461 auto Result = lookupOperandLeader(Cond);
2462 return isa<Constant>(Result) ? Result : nullptr;
2463}
2464
2465// Process the outgoing edges of a block for reachability.
2466void NewGVN::processOutgoingEdges(Instruction *TI, BasicBlock *B) {
2467 // Evaluate reachability of terminator instruction.
2468 Value *Cond;
2469 BasicBlock *TrueSucc, *FalseSucc;
2470 if (match(TI, m_Br(m_Value(Cond), TrueSucc, FalseSucc))) {
2471 Value *CondEvaluated = findConditionEquivalence(Cond);
2472 if (!CondEvaluated) {
2473 if (auto *I = dyn_cast<Instruction>(Cond)) {
2475 auto Res = performSymbolicEvaluation(I, Visited);
2476 if (const auto *CE = dyn_cast_or_null<ConstantExpression>(Res.Expr)) {
2477 CondEvaluated = CE->getConstantValue();
2478 addAdditionalUsers(Res, I);
2479 } else {
2480 // Did not use simplification result, no need to add the extra
2481 // dependency.
2482 Res.ExtraDep = nullptr;
2483 }
2484 } else if (isa<ConstantInt>(Cond)) {
2485 CondEvaluated = Cond;
2486 }
2487 }
2488 ConstantInt *CI;
2489 if (CondEvaluated && (CI = dyn_cast<ConstantInt>(CondEvaluated))) {
2490 if (CI->isOne()) {
2491 LLVM_DEBUG(dbgs() << "Condition for Terminator " << *TI
2492 << " evaluated to true\n");
2493 updateReachableEdge(B, TrueSucc);
2494 } else if (CI->isZero()) {
2495 LLVM_DEBUG(dbgs() << "Condition for Terminator " << *TI
2496 << " evaluated to false\n");
2497 updateReachableEdge(B, FalseSucc);
2498 }
2499 } else {
2500 updateReachableEdge(B, TrueSucc);
2501 updateReachableEdge(B, FalseSucc);
2502 }
2503 } else if (auto *SI = dyn_cast<SwitchInst>(TI)) {
2504 // For switches, propagate the case values into the case
2505 // destinations.
2506
2507 Value *SwitchCond = SI->getCondition();
2508 Value *CondEvaluated = findConditionEquivalence(SwitchCond);
2509 // See if we were able to turn this switch statement into a constant.
2510 if (CondEvaluated && isa<ConstantInt>(CondEvaluated)) {
2511 auto *CondVal = cast<ConstantInt>(CondEvaluated);
2512 // We should be able to get case value for this.
2513 auto Case = *SI->findCaseValue(CondVal);
2514 if (Case.getCaseSuccessor() == SI->getDefaultDest()) {
2515 // We proved the value is outside of the range of the case.
2516 // We can't do anything other than mark the default dest as reachable,
2517 // and go home.
2518 updateReachableEdge(B, SI->getDefaultDest());
2519 return;
2520 }
2521 // Now get where it goes and mark it reachable.
2522 BasicBlock *TargetBlock = Case.getCaseSuccessor();
2523 updateReachableEdge(B, TargetBlock);
2524 } else {
2525 for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
2526 BasicBlock *TargetBlock = SI->getSuccessor(i);
2527 updateReachableEdge(B, TargetBlock);
2528 }
2529 }
2530 } else {
2531 // Otherwise this is either unconditional, or a type we have no
2532 // idea about. Just mark successors as reachable.
2533 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
2534 BasicBlock *TargetBlock = TI->getSuccessor(i);
2535 updateReachableEdge(B, TargetBlock);
2536 }
2537
2538 // This also may be a memory defining terminator, in which case, set it
2539 // equivalent only to itself.
2540 //
2541 auto *MA = getMemoryAccess(TI);
2542 if (MA && !isa<MemoryUse>(MA)) {
2543 auto *CC = ensureLeaderOfMemoryClass(MA);
2544 if (setMemoryClass(MA, CC))
2545 markMemoryUsersTouched(MA);
2546 }
2547 }
2548}
2549
2550// Remove the PHI of Ops PHI for I
2551void NewGVN::removePhiOfOps(Instruction *I, PHINode *PHITemp) {
2552 InstrDFS.erase(PHITemp);
2553 // It's still a temp instruction. We keep it in the array so it gets erased.
2554 // However, it's no longer used by I, or in the block
2555 TempToBlock.erase(PHITemp);
2556 RealToTemp.erase(I);
2557 // We don't remove the users from the phi node uses. This wastes a little
2558 // time, but such is life. We could use two sets to track which were there
2559 // are the start of NewGVN, and which were added, but right nowt he cost of
2560 // tracking is more than the cost of checking for more phi of ops.
2561}
2562
2563// Add PHI Op in BB as a PHI of operations version of ExistingValue.
2564void NewGVN::addPhiOfOps(PHINode *Op, BasicBlock *BB,
2565 Instruction *ExistingValue) {
2566 InstrDFS[Op] = InstrToDFSNum(ExistingValue);
2567 AllTempInstructions.insert(Op);
2568 TempToBlock[Op] = BB;
2569 RealToTemp[ExistingValue] = Op;
2570 // Add all users to phi node use, as they are now uses of the phi of ops phis
2571 // and may themselves be phi of ops.
2572 for (auto *U : ExistingValue->users())
2573 if (auto *UI = dyn_cast<Instruction>(U))
2574 PHINodeUses.insert(UI);
2575}
2576
2577static bool okayForPHIOfOps(const Instruction *I) {
2578 if (!EnablePhiOfOps)
2579 return false;
2580 return isa<BinaryOperator>(I) || isa<SelectInst>(I) || isa<CmpInst>(I) ||
2581 isa<LoadInst>(I);
2582}
2583
2584// Return true if this operand will be safe to use for phi of ops.
2585//
2586// The reason some operands are unsafe is that we are not trying to recursively
2587// translate everything back through phi nodes. We actually expect some lookups
2588// of expressions to fail. In particular, a lookup where the expression cannot
2589// exist in the predecessor. This is true even if the expression, as shown, can
2590// be determined to be constant.
2591bool NewGVN::OpIsSafeForPHIOfOps(Value *V, const BasicBlock *PHIBlock,
2593 SmallVector<Value *, 4> Worklist;
2594 Worklist.push_back(V);
2595 while (!Worklist.empty()) {
2596 auto *I = Worklist.pop_back_val();
2597 if (!isa<Instruction>(I))
2598 continue;
2599
2600 auto OISIt = OpSafeForPHIOfOps.find(I);
2601 if (OISIt != OpSafeForPHIOfOps.end())
2602 return OISIt->second;
2603
2604 // Keep walking until we either dominate the phi block, or hit a phi, or run
2605 // out of things to check.
2606 if (DT->properlyDominates(getBlockForValue(I), PHIBlock)) {
2607 OpSafeForPHIOfOps.insert({I, true});
2608 continue;
2609 }
2610 // PHI in the same block.
2611 if (isa<PHINode>(I) && getBlockForValue(I) == PHIBlock) {
2612 OpSafeForPHIOfOps.insert({I, false});
2613 return false;
2614 }
2615
2616 auto *OrigI = cast<Instruction>(I);
2617 // When we hit an instruction that reads memory (load, call, etc), we must
2618 // consider any store that may happen in the loop. For now, we assume the
2619 // worst: there is a store in the loop that alias with this read.
2620 // The case where the load is outside the loop is already covered by the
2621 // dominator check above.
2622 // TODO: relax this condition
2623 if (OrigI->mayReadFromMemory())
2624 return false;
2625
2626 // Check the operands of the current instruction.
2627 for (auto *Op : OrigI->operand_values()) {
2628 if (!isa<Instruction>(Op))
2629 continue;
2630 // Stop now if we find an unsafe operand.
2631 auto OISIt = OpSafeForPHIOfOps.find(OrigI);
2632 if (OISIt != OpSafeForPHIOfOps.end()) {
2633 if (!OISIt->second) {
2634 OpSafeForPHIOfOps.insert({I, false});
2635 return false;
2636 }
2637 continue;
2638 }
2639 if (!Visited.insert(Op).second)
2640 continue;
2641 Worklist.push_back(cast<Instruction>(Op));
2642 }
2643 }
2644 OpSafeForPHIOfOps.insert({V, true});
2645 return true;
2646}
2647
2648// Try to find a leader for instruction TransInst, which is a phi translated
2649// version of something in our original program. Visited is used to ensure we
2650// don't infinite loop during translations of cycles. OrigInst is the
2651// instruction in the original program, and PredBB is the predecessor we
2652// translated it through.
2653Value *NewGVN::findLeaderForInst(Instruction *TransInst,
2654 SmallPtrSetImpl<Value *> &Visited,
2655 MemoryAccess *MemAccess, Instruction *OrigInst,
2656 BasicBlock *PredBB) {
2657 unsigned IDFSNum = InstrToDFSNum(OrigInst);
2658 // Make sure it's marked as a temporary instruction.
2659 AllTempInstructions.insert(TransInst);
2660 // and make sure anything that tries to add it's DFS number is
2661 // redirected to the instruction we are making a phi of ops
2662 // for.
2663 TempToBlock.insert({TransInst, PredBB});
2664 InstrDFS.insert({TransInst, IDFSNum});
2665
2666 auto Res = performSymbolicEvaluation(TransInst, Visited);
2667 const Expression *E = Res.Expr;
2668 addAdditionalUsers(Res, OrigInst);
2669 InstrDFS.erase(TransInst);
2670 AllTempInstructions.erase(TransInst);
2671 TempToBlock.erase(TransInst);
2672 if (MemAccess)
2673 TempToMemory.erase(TransInst);
2674 if (!E)
2675 return nullptr;
2676 auto *FoundVal = findPHIOfOpsLeader(E, OrigInst, PredBB);
2677 if (!FoundVal) {
2678 ExpressionToPhiOfOps[E].insert(OrigInst);
2679 LLVM_DEBUG(dbgs() << "Cannot find phi of ops operand for " << *TransInst
2680 << " in block " << getBlockName(PredBB) << "\n");
2681 return nullptr;
2682 }
2683 if (auto *SI = dyn_cast<StoreInst>(FoundVal))
2684 FoundVal = SI->getValueOperand();
2685 return FoundVal;
2686}
2687
2688// When we see an instruction that is an op of phis, generate the equivalent phi
2689// of ops form.
2690const Expression *
2691NewGVN::makePossiblePHIOfOps(Instruction *I,
2692 SmallPtrSetImpl<Value *> &Visited) {
2693 if (!okayForPHIOfOps(I))
2694 return nullptr;
2695
2696 if (!Visited.insert(I).second)
2697 return nullptr;
2698 // For now, we require the instruction be cycle free because we don't
2699 // *always* create a phi of ops for instructions that could be done as phi
2700 // of ops, we only do it if we think it is useful. If we did do it all the
2701 // time, we could remove the cycle free check.
2702 if (!isCycleFree(I))
2703 return nullptr;
2704
2705 SmallPtrSet<const Value *, 8> ProcessedPHIs;
2706 // TODO: We don't do phi translation on memory accesses because it's
2707 // complicated. For a load, we'd need to be able to simulate a new memoryuse,
2708 // which we don't have a good way of doing ATM.
2709 auto *MemAccess = getMemoryAccess(I);
2710 // If the memory operation is defined by a memory operation this block that
2711 // isn't a MemoryPhi, transforming the pointer backwards through a scalar phi
2712 // can't help, as it would still be killed by that memory operation.
2713 if (MemAccess && !isa<MemoryPhi>(MemAccess->getDefiningAccess()) &&
2714 MemAccess->getDefiningAccess()->getBlock() == I->getParent())
2715 return nullptr;
2716
2717 // Convert op of phis to phi of ops
2719 SmallVector<Value *, 4> Ops(I->operand_values());
2720 BasicBlock *SamePHIBlock = nullptr;
2721 PHINode *OpPHI = nullptr;
2722 if (!DebugCounter::shouldExecute(PHIOfOpsCounter))
2723 return nullptr;
2724 for (auto *Op : Ops) {
2725 if (!isa<PHINode>(Op)) {
2726 auto *ValuePHI = RealToTemp.lookup(Op);
2727 if (!ValuePHI)
2728 continue;
2729 LLVM_DEBUG(dbgs() << "Found possible dependent phi of ops\n");
2730 Op = ValuePHI;
2731 }
2732 OpPHI = cast<PHINode>(Op);
2733 if (!SamePHIBlock) {
2734 SamePHIBlock = getBlockForValue(OpPHI);
2735 } else if (SamePHIBlock != getBlockForValue(OpPHI)) {
2736 LLVM_DEBUG(
2737 dbgs()
2738 << "PHIs for operands are not all in the same block, aborting\n");
2739 return nullptr;
2740 }
2741 // No point in doing this for one-operand phis.
2742 if (OpPHI->getNumOperands() == 1) {
2743 OpPHI = nullptr;
2744 continue;
2745 }
2746 }
2747
2748 if (!OpPHI)
2749 return nullptr;
2750
2753 auto *PHIBlock = getBlockForValue(OpPHI);
2754 RevisitOnReachabilityChange[PHIBlock].reset(InstrToDFSNum(I));
2755 for (unsigned PredNum = 0; PredNum < OpPHI->getNumOperands(); ++PredNum) {
2756 auto *PredBB = OpPHI->getIncomingBlock(PredNum);
2757 Value *FoundVal = nullptr;
2758 SmallPtrSet<Value *, 4> CurrentDeps;
2759 // We could just skip unreachable edges entirely but it's tricky to do
2760 // with rewriting existing phi nodes.
2761 if (ReachableEdges.count({PredBB, PHIBlock})) {
2762 // Clone the instruction, create an expression from it that is
2763 // translated back into the predecessor, and see if we have a leader.
2764 Instruction *ValueOp = I->clone();
2765 if (MemAccess)
2766 TempToMemory.insert({ValueOp, MemAccess});
2767 bool SafeForPHIOfOps = true;
2768 VisitedOps.clear();
2769 for (auto &Op : ValueOp->operands()) {
2770 auto *OrigOp = &*Op;
2771 // When these operand changes, it could change whether there is a
2772 // leader for us or not, so we have to add additional users.
2773 if (isa<PHINode>(Op)) {
2774 Op = Op->DoPHITranslation(PHIBlock, PredBB);
2775 if (Op != OrigOp && Op != I)
2776 CurrentDeps.insert(Op);
2777 } else if (auto *ValuePHI = RealToTemp.lookup(Op)) {
2778 if (getBlockForValue(ValuePHI) == PHIBlock)
2779 Op = ValuePHI->getIncomingValueForBlock(PredBB);
2780 }
2781 // If we phi-translated the op, it must be safe.
2782 SafeForPHIOfOps =
2783 SafeForPHIOfOps &&
2784 (Op != OrigOp || OpIsSafeForPHIOfOps(Op, PHIBlock, VisitedOps));
2785 }
2786 // FIXME: For those things that are not safe we could generate
2787 // expressions all the way down, and see if this comes out to a
2788 // constant. For anything where that is true, and unsafe, we should
2789 // have made a phi-of-ops (or value numbered it equivalent to something)
2790 // for the pieces already.
2791 FoundVal = !SafeForPHIOfOps ? nullptr
2792 : findLeaderForInst(ValueOp, Visited,
2793 MemAccess, I, PredBB);
2794 ValueOp->deleteValue();
2795 if (!FoundVal) {
2796 // We failed to find a leader for the current ValueOp, but this might
2797 // change in case of the translated operands change.
2798 if (SafeForPHIOfOps)
2799 for (auto *Dep : CurrentDeps)
2800 addAdditionalUsers(Dep, I);
2801
2802 return nullptr;
2803 }
2804 Deps.insert(CurrentDeps.begin(), CurrentDeps.end());
2805 } else {
2806 LLVM_DEBUG(dbgs() << "Skipping phi of ops operand for incoming block "
2807 << getBlockName(PredBB)
2808 << " because the block is unreachable\n");
2809 FoundVal = PoisonValue::get(I->getType());
2810 RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(I));
2811 }
2812
2813 PHIOps.push_back({FoundVal, PredBB});
2814 LLVM_DEBUG(dbgs() << "Found phi of ops operand " << *FoundVal << " in "
2815 << getBlockName(PredBB) << "\n");
2816 }
2817 for (auto *Dep : Deps)
2818 addAdditionalUsers(Dep, I);
2819 sortPHIOps(PHIOps);
2820 auto *E = performSymbolicPHIEvaluation(PHIOps, I, PHIBlock);
2821 if (isa<ConstantExpression>(E) || isa<VariableExpression>(E)) {
2822 LLVM_DEBUG(
2823 dbgs()
2824 << "Not creating real PHI of ops because it simplified to existing "
2825 "value or constant\n");
2826 // We have leaders for all operands, but do not create a real PHI node with
2827 // those leaders as operands, so the link between the operands and the
2828 // PHI-of-ops is not materialized in the IR. If any of those leaders
2829 // changes, the PHI-of-op may change also, so we need to add the operands as
2830 // additional users.
2831 for (auto &O : PHIOps)
2832 addAdditionalUsers(O.first, I);
2833
2834 return E;
2835 }
2836 auto *ValuePHI = RealToTemp.lookup(I);
2837 bool NewPHI = false;
2838 if (!ValuePHI) {
2839 ValuePHI =
2840 PHINode::Create(I->getType(), OpPHI->getNumOperands(), "phiofops");
2841 addPhiOfOps(ValuePHI, PHIBlock, I);
2842 NewPHI = true;
2843 NumGVNPHIOfOpsCreated++;
2844 }
2845 if (NewPHI) {
2846 for (auto PHIOp : PHIOps)
2847 ValuePHI->addIncoming(PHIOp.first, PHIOp.second);
2848 } else {
2849 TempToBlock[ValuePHI] = PHIBlock;
2850 unsigned int i = 0;
2851 for (auto PHIOp : PHIOps) {
2852 ValuePHI->setIncomingValue(i, PHIOp.first);
2853 ValuePHI->setIncomingBlock(i, PHIOp.second);
2854 ++i;
2855 }
2856 }
2857 RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(I));
2858 LLVM_DEBUG(dbgs() << "Created phi of ops " << *ValuePHI << " for " << *I
2859 << "\n");
2860
2861 return E;
2862}
2863
2864// The algorithm initially places the values of the routine in the TOP
2865// congruence class. The leader of TOP is the undetermined value `poison`.
2866// When the algorithm has finished, values still in TOP are unreachable.
2867void NewGVN::initializeCongruenceClasses(Function &F) {
2868 NextCongruenceNum = 0;
2869
2870 // Note that even though we use the live on entry def as a representative
2871 // MemoryAccess, it is *not* the same as the actual live on entry def. We
2872 // have no real equivalent to poison for MemoryAccesses, and so we really
2873 // should be checking whether the MemoryAccess is top if we want to know if it
2874 // is equivalent to everything. Otherwise, what this really signifies is that
2875 // the access "it reaches all the way back to the beginning of the function"
2876
2877 // Initialize all other instructions to be in TOP class.
2878 TOPClass = createCongruenceClass(nullptr, nullptr);
2879 TOPClass->setMemoryLeader(MSSA->getLiveOnEntryDef());
2880 // The live on entry def gets put into it's own class
2881 MemoryAccessToClass[MSSA->getLiveOnEntryDef()] =
2882 createMemoryClass(MSSA->getLiveOnEntryDef());
2883
2884 for (auto *DTN : nodes(DT)) {
2885 BasicBlock *BB = DTN->getBlock();
2886 // All MemoryAccesses are equivalent to live on entry to start. They must
2887 // be initialized to something so that initial changes are noticed. For
2888 // the maximal answer, we initialize them all to be the same as
2889 // liveOnEntry.
2890 auto *MemoryBlockDefs = MSSA->getBlockDefs(BB);
2891 if (MemoryBlockDefs)
2892 for (const auto &Def : *MemoryBlockDefs) {
2893 MemoryAccessToClass[&Def] = TOPClass;
2894 auto *MD = dyn_cast<MemoryDef>(&Def);
2895 // Insert the memory phis into the member list.
2896 if (!MD) {
2897 const MemoryPhi *MP = cast<MemoryPhi>(&Def);
2898 TOPClass->memory_insert(MP);
2899 MemoryPhiState.insert({MP, MPS_TOP});
2900 }
2901
2902 if (MD && isa<StoreInst>(MD->getMemoryInst()))
2903 TOPClass->incStoreCount();
2904 }
2905
2906 // FIXME: This is trying to discover which instructions are uses of phi
2907 // nodes. We should move this into one of the myriad of places that walk
2908 // all the operands already.
2909 for (auto &I : *BB) {
2910 if (isa<PHINode>(&I))
2911 for (auto *U : I.users())
2912 if (auto *UInst = dyn_cast<Instruction>(U))
2913 if (InstrToDFSNum(UInst) != 0 && okayForPHIOfOps(UInst))
2914 PHINodeUses.insert(UInst);
2915 // Don't insert void terminators into the class. We don't value number
2916 // them, and they just end up sitting in TOP.
2917 if (I.isTerminator() && I.getType()->isVoidTy())
2918 continue;
2919 TOPClass->insert(&I);
2920 ValueToClass[&I] = TOPClass;
2921 }
2922 }
2923
2924 // Initialize arguments to be in their own unique congruence classes
2925 for (auto &FA : F.args())
2926 createSingletonCongruenceClass(&FA);
2927}
2928
2929void NewGVN::cleanupTables() {
2930 for (CongruenceClass *&CC : CongruenceClasses) {
2931 LLVM_DEBUG(dbgs() << "Congruence class " << CC->getID() << " has "
2932 << CC->size() << " members\n");
2933 // Make sure we delete the congruence class (probably worth switching to
2934 // a unique_ptr at some point.
2935 delete CC;
2936 CC = nullptr;
2937 }
2938
2939 // Destroy the value expressions
2940 SmallVector<Instruction *, 8> TempInst(AllTempInstructions.begin(),
2941 AllTempInstructions.end());
2942 AllTempInstructions.clear();
2943
2944 // We have to drop all references for everything first, so there are no uses
2945 // left as we delete them.
2946 for (auto *I : TempInst) {
2947 I->dropAllReferences();
2948 }
2949
2950 while (!TempInst.empty()) {
2951 auto *I = TempInst.pop_back_val();
2952 I->deleteValue();
2953 }
2954
2955 ValueToClass.clear();
2956 ArgRecycler.clear(ExpressionAllocator);
2957 ExpressionAllocator.Reset();
2958 CongruenceClasses.clear();
2959 ExpressionToClass.clear();
2960 ValueToExpression.clear();
2961 RealToTemp.clear();
2962 AdditionalUsers.clear();
2963 ExpressionToPhiOfOps.clear();
2964 TempToBlock.clear();
2965 TempToMemory.clear();
2966 PHINodeUses.clear();
2967 OpSafeForPHIOfOps.clear();
2968 ReachableBlocks.clear();
2969 ReachableEdges.clear();
2970#ifndef NDEBUG
2971 ProcessedCount.clear();
2972#endif
2973 InstrDFS.clear();
2974 InstructionsToErase.clear();
2975 DFSToInstr.clear();
2976 BlockInstRange.clear();
2977 TouchedInstructions.clear();
2978 MemoryAccessToClass.clear();
2979 PredicateToUsers.clear();
2980 MemoryToUsers.clear();
2981 RevisitOnReachabilityChange.clear();
2982 IntrinsicInstPred.clear();
2983}
2984
2985// Assign local DFS number mapping to instructions, and leave space for Value
2986// PHI's.
2987std::pair<unsigned, unsigned> NewGVN::assignDFSNumbers(BasicBlock *B,
2988 unsigned Start) {
2989 unsigned End = Start;
2990 if (MemoryAccess *MemPhi = getMemoryAccess(B)) {
2991 InstrDFS[MemPhi] = End++;
2992 DFSToInstr.emplace_back(MemPhi);
2993 }
2994
2995 // Then the real block goes next.
2996 for (auto &I : *B) {
2997 // There's no need to call isInstructionTriviallyDead more than once on
2998 // an instruction. Therefore, once we know that an instruction is dead
2999 // we change its DFS number so that it doesn't get value numbered.
3000 if (isInstructionTriviallyDead(&I, TLI)) {
3001 InstrDFS[&I] = 0;
3002 LLVM_DEBUG(dbgs() << "Skipping trivially dead instruction " << I << "\n");
3003 markInstructionForDeletion(&I);
3004 continue;
3005 }
3006 if (isa<PHINode>(&I))
3007 RevisitOnReachabilityChange[B].set(End);
3008 InstrDFS[&I] = End++;
3009 DFSToInstr.emplace_back(&I);
3010 }
3011
3012 // All of the range functions taken half-open ranges (open on the end side).
3013 // So we do not subtract one from count, because at this point it is one
3014 // greater than the last instruction.
3015 return std::make_pair(Start, End);
3016}
3017
3018void NewGVN::updateProcessedCount(const Value *V) {
3019#ifndef NDEBUG
3020 if (ProcessedCount.count(V) == 0) {
3021 ProcessedCount.insert({V, 1});
3022 } else {
3023 ++ProcessedCount[V];
3024 assert(ProcessedCount[V] < 100 &&
3025 "Seem to have processed the same Value a lot");
3026 }
3027#endif
3028}
3029
3030// Evaluate MemoryPhi nodes symbolically, just like PHI nodes
3031void NewGVN::valueNumberMemoryPhi(MemoryPhi *MP) {
3032 // If all the arguments are the same, the MemoryPhi has the same value as the
3033 // argument. Filter out unreachable blocks and self phis from our operands.
3034 // TODO: We could do cycle-checking on the memory phis to allow valueizing for
3035 // self-phi checking.
3036 const BasicBlock *PHIBlock = MP->getBlock();
3037 auto Filtered = make_filter_range(MP->operands(), [&](const Use &U) {
3038 return cast<MemoryAccess>(U) != MP &&
3039 !isMemoryAccessTOP(cast<MemoryAccess>(U)) &&
3040 ReachableEdges.count({MP->getIncomingBlock(U), PHIBlock});
3041 });
3042 // If all that is left is nothing, our memoryphi is poison. We keep it as
3043 // InitialClass. Note: The only case this should happen is if we have at
3044 // least one self-argument.
3045 if (Filtered.begin() == Filtered.end()) {
3046 if (setMemoryClass(MP, TOPClass))
3047 markMemoryUsersTouched(MP);
3048 return;
3049 }
3050
3051 // Transform the remaining operands into operand leaders.
3052 // FIXME: mapped_iterator should have a range version.
3053 auto LookupFunc = [&](const Use &U) {
3054 return lookupMemoryLeader(cast<MemoryAccess>(U));
3055 };
3056 auto MappedBegin = map_iterator(Filtered.begin(), LookupFunc);
3057 auto MappedEnd = map_iterator(Filtered.end(), LookupFunc);
3058
3059 // and now check if all the elements are equal.
3060 // Sadly, we can't use std::equals since these are random access iterators.
3061 const auto *AllSameValue = *MappedBegin;
3062 ++MappedBegin;
3063 bool AllEqual = std::all_of(
3064 MappedBegin, MappedEnd,
3065 [&AllSameValue](const MemoryAccess *V) { return V == AllSameValue; });
3066
3067 if (AllEqual)
3068 LLVM_DEBUG(dbgs() << "Memory Phi value numbered to " << *AllSameValue
3069 << "\n");
3070 else
3071 LLVM_DEBUG(dbgs() << "Memory Phi value numbered to itself\n");
3072 // If it's equal to something, it's in that class. Otherwise, it has to be in
3073 // a class where it is the leader (other things may be equivalent to it, but
3074 // it needs to start off in its own class, which means it must have been the
3075 // leader, and it can't have stopped being the leader because it was never
3076 // removed).
3077 CongruenceClass *CC =
3078 AllEqual ? getMemoryClass(AllSameValue) : ensureLeaderOfMemoryClass(MP);
3079 auto OldState = MemoryPhiState.lookup(MP);
3080 assert(OldState != MPS_Invalid && "Invalid memory phi state");
3081 auto NewState = AllEqual ? MPS_Equivalent : MPS_Unique;
3082 MemoryPhiState[MP] = NewState;
3083 if (setMemoryClass(MP, CC) || OldState != NewState)
3084 markMemoryUsersTouched(MP);
3085}
3086
3087// Value number a single instruction, symbolically evaluating, performing
3088// congruence finding, and updating mappings.
3089void NewGVN::valueNumberInstruction(Instruction *I) {
3090 LLVM_DEBUG(dbgs() << "Processing instruction " << *I << "\n");
3091 if (!I->isTerminator()) {
3092 const Expression *Symbolized = nullptr;
3094 if (DebugCounter::shouldExecute(VNCounter)) {
3095 auto Res = performSymbolicEvaluation(I, Visited);
3096 Symbolized = Res.Expr;
3097 addAdditionalUsers(Res, I);
3098
3099 // Make a phi of ops if necessary
3100 if (Symbolized && !isa<ConstantExpression>(Symbolized) &&
3101 !isa<VariableExpression>(Symbolized) && PHINodeUses.count(I)) {
3102 auto *PHIE = makePossiblePHIOfOps(I, Visited);
3103 // If we created a phi of ops, use it.
3104 // If we couldn't create one, make sure we don't leave one lying around
3105 if (PHIE) {
3106 Symbolized = PHIE;
3107 } else if (auto *Op = RealToTemp.lookup(I)) {
3108 removePhiOfOps(I, Op);
3109 }
3110 }
3111 } else {
3112 // Mark the instruction as unused so we don't value number it again.
3113 InstrDFS[I] = 0;
3114 }
3115 // If we couldn't come up with a symbolic expression, use the unknown
3116 // expression
3117 if (Symbolized == nullptr)
3118 Symbolized = createUnknownExpression(I);
3119 performCongruenceFinding(I, Symbolized);
3120 } else {
3121 // Handle terminators that return values. All of them produce values we
3122 // don't currently understand. We don't place non-value producing
3123 // terminators in a class.
3124 if (!I->getType()->isVoidTy()) {
3125 auto *Symbolized = createUnknownExpression(I);
3126 performCongruenceFinding(I, Symbolized);
3127 }
3128 processOutgoingEdges(I, I->getParent());
3129 }
3130}
3131
3132// Check if there is a path, using single or equal argument phi nodes, from
3133// First to Second.
3134bool NewGVN::singleReachablePHIPath(
3136 const MemoryAccess *Second) const {
3137 if (First == Second)
3138 return true;
3139 if (MSSA->isLiveOnEntryDef(First))
3140 return false;
3141
3142 // This is not perfect, but as we're just verifying here, we can live with
3143 // the loss of precision. The real solution would be that of doing strongly
3144 // connected component finding in this routine, and it's probably not worth
3145 // the complexity for the time being. So, we just keep a set of visited
3146 // MemoryAccess and return true when we hit a cycle.
3147 if (!Visited.insert(First).second)
3148 return true;
3149
3150 const auto *EndDef = First;
3151 for (const auto *ChainDef : optimized_def_chain(First)) {
3152 if (ChainDef == Second)
3153 return true;
3154 if (MSSA->isLiveOnEntryDef(ChainDef))
3155 return false;
3156 EndDef = ChainDef;
3157 }
3158 auto *MP = cast<MemoryPhi>(EndDef);
3159 auto ReachableOperandPred = [&](const Use &U) {
3160 return ReachableEdges.count({MP->getIncomingBlock(U), MP->getBlock()});
3161 };
3162 auto FilteredPhiArgs =
3163 make_filter_range(MP->operands(), ReachableOperandPred);
3165 llvm::copy(FilteredPhiArgs, std::back_inserter(OperandList));
3166 bool Okay = all_equal(OperandList);
3167 if (Okay)
3168 return singleReachablePHIPath(Visited, cast<MemoryAccess>(OperandList[0]),
3169 Second);
3170 return false;
3171}
3172
3173// Verify the that the memory equivalence table makes sense relative to the
3174// congruence classes. Note that this checking is not perfect, and is currently
3175// subject to very rare false negatives. It is only useful for
3176// testing/debugging.
3177void NewGVN::verifyMemoryCongruency() const {
3178#ifndef NDEBUG
3179 // Verify that the memory table equivalence and memory member set match
3180 for (const auto *CC : CongruenceClasses) {
3181 if (CC == TOPClass || CC->isDead())
3182 continue;
3183 if (CC->getStoreCount() != 0) {
3184 assert((CC->getStoredValue() || !isa<StoreInst>(CC->getLeader())) &&
3185 "Any class with a store as a leader should have a "
3186 "representative stored value");
3187 assert(CC->getMemoryLeader() &&
3188 "Any congruence class with a store should have a "
3189 "representative access");
3190 }
3191
3192 if (CC->getMemoryLeader())
3193 assert(MemoryAccessToClass.lookup(CC->getMemoryLeader()) == CC &&
3194 "Representative MemoryAccess does not appear to be reverse "
3195 "mapped properly");
3196 for (const auto *M : CC->memory())
3197 assert(MemoryAccessToClass.lookup(M) == CC &&
3198 "Memory member does not appear to be reverse mapped properly");
3199 }
3200
3201 // Anything equivalent in the MemoryAccess table should be in the same
3202 // congruence class.
3203
3204 // Filter out the unreachable and trivially dead entries, because they may
3205 // never have been updated if the instructions were not processed.
3206 auto ReachableAccessPred =
3207 [&](const std::pair<const MemoryAccess *, CongruenceClass *> Pair) {
3208 bool Result = ReachableBlocks.count(Pair.first->getBlock());
3209 if (!Result || MSSA->isLiveOnEntryDef(Pair.first) ||
3210 MemoryToDFSNum(Pair.first) == 0)
3211 return false;
3212 if (auto *MemDef = dyn_cast<MemoryDef>(Pair.first))
3213 return !isInstructionTriviallyDead(MemDef->getMemoryInst());
3214
3215 // We could have phi nodes which operands are all trivially dead,
3216 // so we don't process them.
3217 if (auto *MemPHI = dyn_cast<MemoryPhi>(Pair.first)) {
3218 for (const auto &U : MemPHI->incoming_values()) {
3219 if (auto *I = dyn_cast<Instruction>(&*U)) {
3221 return true;
3222 }
3223 }
3224 return false;
3225 }
3226
3227 return true;
3228 };
3229
3230 auto Filtered = make_filter_range(MemoryAccessToClass, ReachableAccessPred);
3231 for (auto KV : Filtered) {
3232 if (auto *FirstMUD = dyn_cast<MemoryUseOrDef>(KV.first)) {
3233 auto *SecondMUD = dyn_cast<MemoryUseOrDef>(KV.second->getMemoryLeader());
3234 if (FirstMUD && SecondMUD) {
3236 assert((singleReachablePHIPath(VisitedMAS, FirstMUD, SecondMUD) ||
3237 ValueToClass.lookup(FirstMUD->getMemoryInst()) ==
3238 ValueToClass.lookup(SecondMUD->getMemoryInst())) &&
3239 "The instructions for these memory operations should have "
3240 "been in the same congruence class or reachable through"
3241 "a single argument phi");
3242 }
3243 } else if (auto *FirstMP = dyn_cast<MemoryPhi>(KV.first)) {
3244 // We can only sanely verify that MemoryDefs in the operand list all have
3245 // the same class.
3246 auto ReachableOperandPred = [&](const Use &U) {
3247 return ReachableEdges.count(
3248 {FirstMP->getIncomingBlock(U), FirstMP->getBlock()}) &&
3249 isa<MemoryDef>(U);
3250
3251 };
3252 // All arguments should in the same class, ignoring unreachable arguments
3253 auto FilteredPhiArgs =
3254 make_filter_range(FirstMP->operands(), ReachableOperandPred);
3256 std::transform(FilteredPhiArgs.begin(), FilteredPhiArgs.end(),
3257 std::back_inserter(PhiOpClasses), [&](const Use &U) {
3258 const MemoryDef *MD = cast<MemoryDef>(U);
3259 return ValueToClass.lookup(MD->getMemoryInst());
3260 });
3261 assert(all_equal(PhiOpClasses) &&
3262 "All MemoryPhi arguments should be in the same class");
3263 }
3264 }
3265#endif
3266}
3267
3268// Verify that the sparse propagation we did actually found the maximal fixpoint
3269// We do this by storing the value to class mapping, touching all instructions,
3270// and redoing the iteration to see if anything changed.
3271void NewGVN::verifyIterationSettled(Function &F) {
3272#ifndef NDEBUG
3273 LLVM_DEBUG(dbgs() << "Beginning iteration verification\n");
3274 if (DebugCounter::isCounterSet(VNCounter))
3275 DebugCounter::setCounterValue(VNCounter, StartingVNCounter);
3276
3277 // Note that we have to store the actual classes, as we may change existing
3278 // classes during iteration. This is because our memory iteration propagation
3279 // is not perfect, and so may waste a little work. But it should generate
3280 // exactly the same congruence classes we have now, with different IDs.
3281 std::map<const Value *, CongruenceClass> BeforeIteration;
3282
3283 for (auto &KV : ValueToClass) {
3284 if (auto *I = dyn_cast<Instruction>(KV.first))
3285 // Skip unused/dead instructions.
3286 if (InstrToDFSNum(I) == 0)
3287 continue;
3288 BeforeIteration.insert({KV.first, *KV.second});
3289 }
3290
3291 TouchedInstructions.set();
3292 TouchedInstructions.reset(0);
3293 OpSafeForPHIOfOps.clear();
3294 iterateTouchedInstructions();
3296 EqualClasses;
3297 for (const auto &KV : ValueToClass) {
3298 if (auto *I = dyn_cast<Instruction>(KV.first))
3299 // Skip unused/dead instructions.
3300 if (InstrToDFSNum(I) == 0)
3301 continue;
3302 // We could sink these uses, but i think this adds a bit of clarity here as
3303 // to what we are comparing.
3304 auto *BeforeCC = &BeforeIteration.find(KV.first)->second;
3305 auto *AfterCC = KV.second;
3306 // Note that the classes can't change at this point, so we memoize the set
3307 // that are equal.
3308 if (!EqualClasses.count({BeforeCC, AfterCC})) {
3309 assert(BeforeCC->isEquivalentTo(AfterCC) &&
3310 "Value number changed after main loop completed!");
3311 EqualClasses.insert({BeforeCC, AfterCC});
3312 }
3313 }
3314#endif
3315}
3316
3317// Verify that for each store expression in the expression to class mapping,
3318// only the latest appears, and multiple ones do not appear.
3319// Because loads do not use the stored value when doing equality with stores,
3320// if we don't erase the old store expressions from the table, a load can find
3321// a no-longer valid StoreExpression.
3322void NewGVN::verifyStoreExpressions() const {
3323#ifndef NDEBUG
3324 // This is the only use of this, and it's not worth defining a complicated
3325 // densemapinfo hash/equality function for it.
3326 std::set<
3327 std::pair<const Value *,
3328 std::tuple<const Value *, const CongruenceClass *, Value *>>>
3329 StoreExpressionSet;
3330 for (const auto &KV : ExpressionToClass) {
3331 if (auto *SE = dyn_cast<StoreExpression>(KV.first)) {
3332 // Make sure a version that will conflict with loads is not already there
3333 auto Res = StoreExpressionSet.insert(
3334 {SE->getOperand(0), std::make_tuple(SE->getMemoryLeader(), KV.second,
3335 SE->getStoredValue())});
3336 bool Okay = Res.second;
3337 // It's okay to have the same expression already in there if it is
3338 // identical in nature.
3339 // This can happen when the leader of the stored value changes over time.
3340 if (!Okay)
3341 Okay = (std::get<1>(Res.first->second) == KV.second) &&
3342 (lookupOperandLeader(std::get<2>(Res.first->second)) ==
3343 lookupOperandLeader(SE->getStoredValue()));
3344 assert(Okay && "Stored expression conflict exists in expression table");
3345 auto *ValueExpr = ValueToExpression.lookup(SE->getStoreInst());
3346 assert(ValueExpr && ValueExpr->equals(*SE) &&
3347 "StoreExpression in ExpressionToClass is not latest "
3348 "StoreExpression for value");
3349 }
3350 }
3351#endif
3352}
3353
3354// This is the main value numbering loop, it iterates over the initial touched
3355// instruction set, propagating value numbers, marking things touched, etc,
3356// until the set of touched instructions is completely empty.
3357void NewGVN::iterateTouchedInstructions() {
3358 uint64_t Iterations = 0;
3359 // Figure out where touchedinstructions starts
3360 int FirstInstr = TouchedInstructions.find_first();
3361 // Nothing set, nothing to iterate, just return.
3362 if (FirstInstr == -1)
3363 return;
3364 const BasicBlock *LastBlock = getBlockForValue(InstrFromDFSNum(FirstInstr));
3365 while (TouchedInstructions.any()) {
3366 ++Iterations;
3367 // Walk through all the instructions in all the blocks in RPO.
3368 // TODO: As we hit a new block, we should push and pop equalities into a
3369 // table lookupOperandLeader can use, to catch things PredicateInfo
3370 // might miss, like edge-only equivalences.
3371 for (unsigned InstrNum : TouchedInstructions.set_bits()) {
3372
3373 // This instruction was found to be dead. We don't bother looking
3374 // at it again.
3375 if (InstrNum == 0) {
3376 TouchedInstructions.reset(InstrNum);
3377 continue;
3378 }
3379
3380 Value *V = InstrFromDFSNum(InstrNum);
3381 const BasicBlock *CurrBlock = getBlockForValue(V);
3382
3383 // If we hit a new block, do reachability processing.
3384 if (CurrBlock != LastBlock) {
3385 LastBlock = CurrBlock;
3386 bool BlockReachable = ReachableBlocks.count(CurrBlock);
3387 const auto &CurrInstRange = BlockInstRange.lookup(CurrBlock);
3388
3389 // If it's not reachable, erase any touched instructions and move on.
3390 if (!BlockReachable) {
3391 TouchedInstructions.reset(CurrInstRange.first, CurrInstRange.second);
3392 LLVM_DEBUG(dbgs() << "Skipping instructions in block "
3393 << getBlockName(CurrBlock)
3394 << " because it is unreachable\n");
3395 continue;
3396 }
3397 updateProcessedCount(CurrBlock);
3398 }
3399 // Reset after processing (because we may mark ourselves as touched when
3400 // we propagate equalities).
3401 TouchedInstructions.reset(InstrNum);
3402
3403 if (auto *MP = dyn_cast<MemoryPhi>(V)) {
3404 LLVM_DEBUG(dbgs() << "Processing MemoryPhi " << *MP << "\n");
3405 valueNumberMemoryPhi(MP);
3406 } else if (auto *I = dyn_cast<Instruction>(V)) {
3407 valueNumberInstruction(I);
3408 } else {
3409 llvm_unreachable("Should have been a MemoryPhi or Instruction");
3410 }
3411 updateProcessedCount(V);
3412 }
3413 }
3414 NumGVNMaxIterations = std::max(NumGVNMaxIterations.getValue(), Iterations);
3415}
3416
3417// This is the main transformation entry point.
3418bool NewGVN::runGVN() {
3419 if (DebugCounter::isCounterSet(VNCounter))
3420 StartingVNCounter = DebugCounter::getCounterValue(VNCounter);
3421 bool Changed = false;
3422 NumFuncArgs = F.arg_size();
3423 MSSAWalker = MSSA->getWalker();
3424 SingletonDeadExpression = new (ExpressionAllocator) DeadExpression();
3425
3426 // Count number of instructions for sizing of hash tables, and come
3427 // up with a global dfs numbering for instructions.
3428 unsigned ICount = 1;
3429 // Add an empty instruction to account for the fact that we start at 1
3430 DFSToInstr.emplace_back(nullptr);
3431 // Note: We want ideal RPO traversal of the blocks, which is not quite the
3432 // same as dominator tree order, particularly with regard whether backedges
3433 // get visited first or second, given a block with multiple successors.
3434 // If we visit in the wrong order, we will end up performing N times as many
3435 // iterations.
3436 // The dominator tree does guarantee that, for a given dom tree node, it's
3437 // parent must occur before it in the RPO ordering. Thus, we only need to sort
3438 // the siblings.
3440 unsigned Counter = 0;
3441 for (auto &B : RPOT) {
3442 auto *Node = DT->getNode(B);
3443 assert(Node && "RPO and Dominator tree should have same reachability");
3444 RPOOrdering[Node] = ++Counter;
3445 }
3446 // Sort dominator tree children arrays into RPO.
3447 for (auto &B : RPOT) {
3448 auto *Node = DT->getNode(B);
3449 if (Node->getNumChildren() > 1)
3450 llvm::sort(*Node, [&](const DomTreeNode *A, const DomTreeNode *B) {
3451 return RPOOrdering[A] < RPOOrdering[B];
3452 });
3453 }
3454
3455 // Now a standard depth first ordering of the domtree is equivalent to RPO.
3456 for (auto *DTN : depth_first(DT->getRootNode())) {
3457 BasicBlock *B = DTN->getBlock();
3458 const auto &BlockRange = assignDFSNumbers(B, ICount);
3459 BlockInstRange.insert({B, BlockRange});
3460 ICount += BlockRange.second - BlockRange.first;
3461 }
3462 initializeCongruenceClasses(F);
3463
3464 TouchedInstructions.resize(ICount);
3465 // Ensure we don't end up resizing the expressionToClass map, as
3466 // that can be quite expensive. At most, we have one expression per
3467 // instruction.
3468 ExpressionToClass.reserve(ICount);
3469
3470 // Initialize the touched instructions to include the entry block.
3471 const auto &InstRange = BlockInstRange.lookup(&F.getEntryBlock());
3472 TouchedInstructions.set(InstRange.first, InstRange.second);
3473 LLVM_DEBUG(dbgs() << "Block " << getBlockName(&F.getEntryBlock())
3474 << " marked reachable\n");
3475 ReachableBlocks.insert(&F.getEntryBlock());
3476
3477 iterateTouchedInstructions();
3478 verifyMemoryCongruency();
3479 verifyIterationSettled(F);
3480 verifyStoreExpressions();
3481
3482 Changed |= eliminateInstructions(F);
3483
3484 // Delete all instructions marked for deletion.
3485 for (Instruction *ToErase : InstructionsToErase) {
3486 if (!ToErase->use_empty())
3487 ToErase->replaceAllUsesWith(PoisonValue::get(ToErase->getType()));
3488
3489 assert(ToErase->getParent() &&
3490 "BB containing ToErase deleted unexpectedly!");
3491 ToErase->eraseFromParent();
3492 }
3493 Changed |= !InstructionsToErase.empty();
3494
3495 // Delete all unreachable blocks.
3496 auto UnreachableBlockPred = [&](const BasicBlock &BB) {
3497 return !ReachableBlocks.count(&BB);
3498 };
3499
3500 for (auto &BB : make_filter_range(F, UnreachableBlockPred)) {
3501 LLVM_DEBUG(dbgs() << "We believe block " << getBlockName(&BB)
3502 << " is unreachable\n");
3503 deleteInstructionsInBlock(&BB);
3504 Changed = true;
3505 }
3506
3507 cleanupTables();
3508 return Changed;
3509}
3510
3512 int DFSIn = 0;
3513 int DFSOut = 0;
3514 int LocalNum = 0;
3515
3516 // Only one of Def and U will be set.
3517 // The bool in the Def tells us whether the Def is the stored value of a
3518 // store.
3520 Use *U = nullptr;
3521
3522 bool operator<(const ValueDFS &Other) const {
3523 // It's not enough that any given field be less than - we have sets
3524 // of fields that need to be evaluated together to give a proper ordering.
3525 // For example, if you have;
3526 // DFS (1, 3)
3527 // Val 0
3528 // DFS (1, 2)
3529 // Val 50
3530 // We want the second to be less than the first, but if we just go field
3531 // by field, we will get to Val 0 < Val 50 and say the first is less than
3532 // the second. We only want it to be less than if the DFS orders are equal.
3533 //
3534 // Each LLVM instruction only produces one value, and thus the lowest-level
3535 // differentiator that really matters for the stack (and what we use as as a
3536 // replacement) is the local dfs number.
3537 // Everything else in the structure is instruction level, and only affects
3538 // the order in which we will replace operands of a given instruction.
3539 //
3540 // For a given instruction (IE things with equal dfsin, dfsout, localnum),
3541 // the order of replacement of uses does not matter.
3542 // IE given,
3543 // a = 5
3544 // b = a + a
3545 // When you hit b, you will have two valuedfs with the same dfsin, out, and
3546 // localnum.
3547 // The .val will be the same as well.
3548 // The .u's will be different.
3549 // You will replace both, and it does not matter what order you replace them
3550 // in (IE whether you replace operand 2, then operand 1, or operand 1, then
3551 // operand 2).
3552 // Similarly for the case of same dfsin, dfsout, localnum, but different
3553 // .val's
3554 // a = 5
3555 // b = 6
3556 // c = a + b
3557 // in c, we will a valuedfs for a, and one for b,with everything the same
3558 // but .val and .u.
3559 // It does not matter what order we replace these operands in.
3560 // You will always end up with the same IR, and this is guaranteed.
3561 return std::tie(DFSIn, DFSOut, LocalNum, Def, U) <
3562 std::tie(Other.DFSIn, Other.DFSOut, Other.LocalNum, Other.Def,
3563 Other.U);
3564 }
3565};
3566
3567// This function converts the set of members for a congruence class from values,
3568// to sets of defs and uses with associated DFS info. The total number of
3569// reachable uses for each value is stored in UseCount, and instructions that
3570// seem
3571// dead (have no non-dead uses) are stored in ProbablyDead.
3572void NewGVN::convertClassToDFSOrdered(
3573 const CongruenceClass &Dense, SmallVectorImpl<ValueDFS> &DFSOrderedSet,
3575 SmallPtrSetImpl<Instruction *> &ProbablyDead) const {
3576 for (auto *D : Dense) {
3577 // First add the value.
3578 BasicBlock *BB = getBlockForValue(D);
3579 // Constants are handled prior to ever calling this function, so
3580 // we should only be left with instructions as members.
3581 assert(BB && "Should have figured out a basic block for value");
3582 ValueDFS VDDef;
3583 DomTreeNode *DomNode = DT->getNode(BB);
3584 VDDef.DFSIn = DomNode->getDFSNumIn();
3585 VDDef.DFSOut = DomNode->getDFSNumOut();
3586 // If it's a store, use the leader of the value operand, if it's always
3587 // available, or the value operand. TODO: We could do dominance checks to
3588 // find a dominating leader, but not worth it ATM.
3589 if (auto *SI = dyn_cast<StoreInst>(D)) {
3590 auto Leader = lookupOperandLeader(SI->getValueOperand());
3591 if (alwaysAvailable(Leader)) {
3592 VDDef.Def.setPointer(Leader);
3593 } else {
3594 VDDef.Def.setPointer(SI->getValueOperand());
3595 VDDef.Def.setInt(true);
3596 }
3597 } else {
3598 VDDef.Def.setPointer(D);
3599 }
3600 assert(isa<Instruction>(D) &&
3601 "The dense set member should always be an instruction");
3602 Instruction *Def = cast<Instruction>(D);
3603 VDDef.LocalNum = InstrToDFSNum(D);
3604 DFSOrderedSet.push_back(VDDef);
3605 // If there is a phi node equivalent, add it
3606 if (auto *PN = RealToTemp.lookup(Def)) {
3607 auto *PHIE =
3608 dyn_cast_or_null<PHIExpression>(ValueToExpression.lookup(Def));
3609 if (PHIE) {
3610 VDDef.Def.setInt(false);
3611 VDDef.Def.setPointer(PN);
3612 VDDef.LocalNum = 0;
3613 DFSOrderedSet.push_back(VDDef);
3614 }
3615 }
3616
3617 unsigned int UseCount = 0;
3618 // Now add the uses.
3619 for (auto &U : Def->uses()) {
3620 if (auto *I = dyn_cast<Instruction>(U.getUser())) {
3621 // Don't try to replace into dead uses
3622 if (InstructionsToErase.count(I))
3623 continue;
3624 ValueDFS VDUse;
3625 // Put the phi node uses in the incoming block.
3626 BasicBlock *IBlock;
3627 if (auto *P = dyn_cast<PHINode>(I)) {
3628 IBlock = P->getIncomingBlock(U);
3629 // Make phi node users appear last in the incoming block
3630 // they are from.
3631 VDUse.LocalNum = InstrDFS.size() + 1;
3632 } else {
3633 IBlock = getBlockForValue(I);
3634 VDUse.LocalNum = InstrToDFSNum(I);
3635 }
3636
3637 // Skip uses in unreachable blocks, as we're going
3638 // to delete them.
3639 if (!ReachableBlocks.contains(IBlock))
3640 continue;
3641
3642 DomTreeNode *DomNode = DT->getNode(IBlock);
3643 VDUse.DFSIn = DomNode->getDFSNumIn();
3644 VDUse.DFSOut = DomNode->getDFSNumOut();
3645 VDUse.U = &U;
3646 ++UseCount;
3647 DFSOrderedSet.emplace_back(VDUse);
3648 }
3649 }
3650
3651 // If there are no uses, it's probably dead (but it may have side-effects,
3652 // so not definitely dead. Otherwise, store the number of uses so we can
3653 // track if it becomes dead later).
3654 if (UseCount == 0)
3655 ProbablyDead.insert(Def);
3656 else
3657 UseCounts[Def] = UseCount;
3658 }
3659}
3660
3661// This function converts the set of members for a congruence class from values,
3662// to the set of defs for loads and stores, with associated DFS info.
3663void NewGVN::convertClassToLoadsAndStores(
3664 const CongruenceClass &Dense,
3665 SmallVectorImpl<ValueDFS> &LoadsAndStores) const {
3666 for (auto *D : Dense) {
3667 if (!isa<LoadInst>(D) && !isa<StoreInst>(D))
3668 continue;
3669
3670 BasicBlock *BB = getBlockForValue(D);
3671 ValueDFS VD;
3672 DomTreeNode *DomNode = DT->getNode(BB);
3673 VD.DFSIn = DomNode->getDFSNumIn();
3674 VD.DFSOut = DomNode->getDFSNumOut();
3675 VD.Def.setPointer(D);
3676
3677 // If it's an instruction, use the real local dfs number.
3678 if (auto *I = dyn_cast<Instruction>(D))
3679 VD.LocalNum = InstrToDFSNum(I);
3680 else
3681 llvm_unreachable("Should have been an instruction");
3682
3683 LoadsAndStores.emplace_back(VD);
3684 }
3685}
3686
3689 I->replaceAllUsesWith(Repl);
3690}
3691
3692void NewGVN::deleteInstructionsInBlock(BasicBlock *BB) {
3693 LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << *BB);
3694 ++NumGVNBlocksDeleted;
3695
3696 // Delete the instructions backwards, as it has a reduced likelihood of having
3697 // to update as many def-use and use-def chains. Start after the terminator.
3698 auto StartPoint = BB->rbegin();
3699 ++StartPoint;
3700 // Note that we explicitly recalculate BB->rend() on each iteration,
3701 // as it may change when we remove the first instruction.
3702 for (BasicBlock::reverse_iterator I(StartPoint); I != BB->rend();) {
3703 Instruction &Inst = *I++;
3704 if (!Inst.use_empty())
3706 if (isa<LandingPadInst>(Inst))
3707 continue;
3708 salvageKnowledge(&Inst, AC);
3709
3710 Inst.eraseFromParent();
3711 ++NumGVNInstrDeleted;
3712 }
3713 // Now insert something that simplifycfg will turn into an unreachable.
3714 Type *Int8Ty = Type::getInt8Ty(BB->getContext());
3715 new StoreInst(PoisonValue::get(Int8Ty),
3717 BB->getTerminator());
3718}
3719
3720void NewGVN::markInstructionForDeletion(Instruction *I) {
3721 LLVM_DEBUG(dbgs() << "Marking " << *I << " for deletion\n");
3722 InstructionsToErase.insert(I);
3723}
3724
3725void NewGVN::replaceInstruction(Instruction *I, Value *V) {
3726 LLVM_DEBUG(dbgs() << "Replacing " << *I << " with " << *V << "\n");
3728 // We save the actual erasing to avoid invalidating memory
3729 // dependencies until we are done with everything.
3730 markInstructionForDeletion(I);
3731}
3732
3733namespace {
3734
3735// This is a stack that contains both the value and dfs info of where
3736// that value is valid.
3737class ValueDFSStack {
3738public:
3739 Value *back() const { return ValueStack.back(); }
3740 std::pair<int, int> dfs_back() const { return DFSStack.back(); }
3741
3742 void push_back(Value *V, int DFSIn, int DFSOut) {
3743 ValueStack.emplace_back(V);
3744 DFSStack.emplace_back(DFSIn, DFSOut);
3745 }
3746
3747 bool empty() const { return DFSStack.empty(); }
3748
3749 bool isInScope(int DFSIn, int DFSOut) const {
3750 if (empty())
3751 return false;
3752 return DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second;
3753 }
3754
3755 void popUntilDFSScope(int DFSIn, int DFSOut) {
3756
3757 // These two should always be in sync at this point.
3758 assert(ValueStack.size() == DFSStack.size() &&
3759 "Mismatch between ValueStack and DFSStack");
3760 while (
3761 !DFSStack.empty() &&
3762 !(DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second)) {
3763 DFSStack.pop_back();
3764 ValueStack.pop_back();
3765 }
3766 }
3767
3768private:
3769 SmallVector<Value *, 8> ValueStack;
3771};
3772
3773} // end anonymous namespace
3774
3775// Given an expression, get the congruence class for it.
3776CongruenceClass *NewGVN::getClassForExpression(const Expression *E) const {
3777 if (auto *VE = dyn_cast<VariableExpression>(E))
3778 return ValueToClass.lookup(VE->getVariableValue());
3779 else if (isa<DeadExpression>(E))
3780 return TOPClass;
3781 return ExpressionToClass.lookup(E);
3782}
3783
3784// Given a value and a basic block we are trying to see if it is available in,
3785// see if the value has a leader available in that block.
3786Value *NewGVN::findPHIOfOpsLeader(const Expression *E,
3787 const Instruction *OrigInst,
3788 const BasicBlock *BB) const {
3789 // It would already be constant if we could make it constant
3790 if (auto *CE = dyn_cast<ConstantExpression>(E))
3791 return CE->getConstantValue();
3792 if (auto *VE = dyn_cast<VariableExpression>(E)) {
3793 auto *V = VE->getVariableValue();
3794 if (alwaysAvailable(V) || DT->dominates(getBlockForValue(V), BB))
3795 return VE->getVariableValue();
3796 }
3797
3798 auto *CC = getClassForExpression(E);
3799 if (!CC)
3800 return nullptr;
3801 if (alwaysAvailable(CC->getLeader()))
3802 return CC->getLeader();
3803
3804 for (auto *Member : *CC) {
3805 auto *MemberInst = dyn_cast<Instruction>(Member);
3806 if (MemberInst == OrigInst)
3807 continue;
3808 // Anything that isn't an instruction is always available.
3809 if (!MemberInst)
3810 return Member;
3811 if (DT->dominates(getBlockForValue(MemberInst), BB))
3812 return Member;
3813 }
3814 return nullptr;
3815}
3816
3817bool NewGVN::eliminateInstructions(Function &F) {
3818 // This is a non-standard eliminator. The normal way to eliminate is
3819 // to walk the dominator tree in order, keeping track of available
3820 // values, and eliminating them. However, this is mildly
3821 // pointless. It requires doing lookups on every instruction,
3822 // regardless of whether we will ever eliminate it. For
3823 // instructions part of most singleton congruence classes, we know we
3824 // will never eliminate them.
3825
3826 // Instead, this eliminator looks at the congruence classes directly, sorts
3827 // them into a DFS ordering of the dominator tree, and then we just
3828 // perform elimination straight on the sets by walking the congruence
3829 // class member uses in order, and eliminate the ones dominated by the
3830 // last member. This is worst case O(E log E) where E = number of
3831 // instructions in a single congruence class. In theory, this is all
3832 // instructions. In practice, it is much faster, as most instructions are
3833 // either in singleton congruence classes or can't possibly be eliminated
3834 // anyway (if there are no overlapping DFS ranges in class).
3835 // When we find something not dominated, it becomes the new leader
3836 // for elimination purposes.
3837 // TODO: If we wanted to be faster, We could remove any members with no
3838 // overlapping ranges while sorting, as we will never eliminate anything
3839 // with those members, as they don't dominate anything else in our set.
3840
3841 bool AnythingReplaced = false;
3842
3843 // Since we are going to walk the domtree anyway, and we can't guarantee the
3844 // DFS numbers are updated, we compute some ourselves.
3845 DT->updateDFSNumbers();
3846
3847 // Go through all of our phi nodes, and kill the arguments associated with
3848 // unreachable edges.
3849 auto ReplaceUnreachablePHIArgs = [&](PHINode *PHI, BasicBlock *BB) {
3850 for (auto &Operand : PHI->incoming_values())
3851 if (!ReachableEdges.count({PHI->getIncomingBlock(Operand), BB})) {
3852 LLVM_DEBUG(dbgs() << "Replacing incoming value of " << PHI
3853 << " for block "
3854 << getBlockName(PHI->getIncomingBlock(Operand))
3855 << " with poison due to it being unreachable\n");
3856 Operand.set(PoisonValue::get(PHI->getType()));
3857 }
3858 };
3859 // Replace unreachable phi arguments.
3860 // At this point, RevisitOnReachabilityChange only contains:
3861 //
3862 // 1. PHIs
3863 // 2. Temporaries that will convert to PHIs
3864 // 3. Operations that are affected by an unreachable edge but do not fit into
3865 // 1 or 2 (rare).
3866 // So it is a slight overshoot of what we want. We could make it exact by
3867 // using two SparseBitVectors per block.
3868 DenseMap<const BasicBlock *, unsigned> ReachablePredCount;
3869 for (auto &KV : ReachableEdges)
3870 ReachablePredCount[KV.getEnd()]++;
3871 for (auto &BBPair : RevisitOnReachabilityChange) {
3872 for (auto InstNum : BBPair.second) {
3873 auto *Inst = InstrFromDFSNum(InstNum);
3874 auto *PHI = dyn_cast<PHINode>(Inst);
3875 PHI = PHI ? PHI : dyn_cast_or_null<PHINode>(RealToTemp.lookup(Inst));
3876 if (!PHI)
3877 continue;
3878 auto *BB = BBPair.first;
3879 if (ReachablePredCount.lookup(BB) != PHI->getNumIncomingValues())
3880 ReplaceUnreachablePHIArgs(PHI, BB);
3881 }
3882 }
3883
3884 // Map to store the use counts
3886 for (auto *CC : reverse(CongruenceClasses)) {
3887 LLVM_DEBUG(dbgs() << "Eliminating in congruence class " << CC->getID()
3888 << "\n");
3889 // Track the equivalent store info so we can decide whether to try
3890 // dead store elimination.
3891 SmallVector<ValueDFS, 8> PossibleDeadStores;
3892 SmallPtrSet<Instruction *, 8> ProbablyDead;
3893 if (CC->isDead() || CC->empty())
3894 continue;
3895 // Everything still in the TOP class is unreachable or dead.
3896 if (CC == TOPClass) {
3897 for (auto *M : *CC) {
3898 auto *VTE = ValueToExpression.lookup(M);
3899 if (VTE && isa<DeadExpression>(VTE))
3900 markInstructionForDeletion(cast<Instruction>(M));
3901 assert((!ReachableBlocks.count(cast<Instruction>(M)->getParent()) ||
3902 InstructionsToErase.count(cast<Instruction>(M))) &&
3903 "Everything in TOP should be unreachable or dead at this "
3904 "point");
3905 }
3906 continue;
3907 }
3908
3909 assert(CC->getLeader() && "We should have had a leader");
3910 // If this is a leader that is always available, and it's a
3911 // constant or has no equivalences, just replace everything with
3912 // it. We then update the congruence class with whatever members
3913 // are left.
3914 Value *Leader =
3915 CC->getStoredValue() ? CC->getStoredValue() : CC->getLeader();
3916 if (alwaysAvailable(Leader)) {
3917 CongruenceClass::MemberSet MembersLeft;
3918 for (auto *M : *CC) {
3919 Value *Member = M;
3920 // Void things have no uses we can replace.
3921 if (Member == Leader || !isa<Instruction>(Member) ||
3922 Member->getType()->isVoidTy()) {
3923 MembersLeft.insert(Member);
3924 continue;
3925 }
3926 LLVM_DEBUG(dbgs() << "Found replacement " << *(Leader) << " for "
3927 << *Member << "\n");
3928 auto *I = cast<Instruction>(Member);
3929 assert(Leader != I && "About to accidentally remove our leader");
3930 replaceInstruction(I, Leader);
3931 AnythingReplaced = true;
3932 }
3933 CC->swap(MembersLeft);
3934 } else {
3935 // If this is a singleton, we can skip it.
3936 if (CC->size() != 1 || RealToTemp.count(Leader)) {
3937 // This is a stack because equality replacement/etc may place
3938 // constants in the middle of the member list, and we want to use
3939 // those constant values in preference to the current leader, over
3940 // the scope of those constants.
3941 ValueDFSStack EliminationStack;
3942
3943 // Convert the members to DFS ordered sets and then merge them.
3944 SmallVector<ValueDFS, 8> DFSOrderedSet;
3945 convertClassToDFSOrdered(*CC, DFSOrderedSet, UseCounts, ProbablyDead);
3946
3947 // Sort the whole thing.
3948 llvm::sort(DFSOrderedSet);
3949 for (auto &VD : DFSOrderedSet) {
3950 int MemberDFSIn = VD.DFSIn;
3951 int MemberDFSOut = VD.DFSOut;
3952 Value *Def = VD.Def.getPointer();
3953 bool FromStore = VD.Def.getInt();
3954 Use *U = VD.U;
3955 // We ignore void things because we can't get a value from them.
3956 if (Def && Def->getType()->isVoidTy())
3957 continue;
3958 auto *DefInst = dyn_cast_or_null<Instruction>(Def);
3959 if (DefInst && AllTempInstructions.count(DefInst)) {
3960 auto *PN = cast<PHINode>(DefInst);
3961
3962 // If this is a value phi and that's the expression we used, insert
3963 // it into the program
3964 // remove from temp instruction list.
3965 AllTempInstructions.erase(PN);
3966 auto *DefBlock = getBlockForValue(Def);
3967 LLVM_DEBUG(dbgs() << "Inserting fully real phi of ops" << *Def
3968 << " into block "
3969 << getBlockName(getBlockForValue(Def)) << "\n");
3970 PN->insertBefore(&DefBlock->front());
3971 Def = PN;
3972 NumGVNPHIOfOpsEliminations++;
3973 }
3974
3975 if (EliminationStack.empty()) {
3976 LLVM_DEBUG(dbgs() << "Elimination Stack is empty\n");
3977 } else {
3978 LLVM_DEBUG(dbgs() << "Elimination Stack Top DFS numbers are ("
3979 << EliminationStack.dfs_back().first << ","
3980 << EliminationStack.dfs_back().second << ")\n");
3981 }
3982
3983 LLVM_DEBUG(dbgs() << "Current DFS numbers are (" << MemberDFSIn << ","
3984 << MemberDFSOut << ")\n");
3985 // First, we see if we are out of scope or empty. If so,
3986 // and there equivalences, we try to replace the top of
3987 // stack with equivalences (if it's on the stack, it must
3988 // not have been eliminated yet).
3989 // Then we synchronize to our current scope, by
3990 // popping until we are back within a DFS scope that
3991 // dominates the current member.
3992 // Then, what happens depends on a few factors
3993 // If the stack is now empty, we need to push
3994 // If we have a constant or a local equivalence we want to
3995 // start using, we also push.
3996 // Otherwise, we walk along, processing members who are
3997 // dominated by this scope, and eliminate them.
3998 bool ShouldPush = Def && EliminationStack.empty();
3999 bool OutOfScope =
4000 !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut);
4001
4002 if (OutOfScope || ShouldPush) {
4003 // Sync to our current scope.
4004 EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
4005 bool ShouldPush = Def && EliminationStack.empty();
4006 if (ShouldPush) {
4007 EliminationStack.push_back(Def, MemberDFSIn, MemberDFSOut);
4008 }
4009 }
4010
4011 // Skip the Def's, we only want to eliminate on their uses. But mark
4012 // dominated defs as dead.
4013 if (Def) {
4014 // For anything in this case, what and how we value number
4015 // guarantees that any side-effets that would have occurred (ie
4016 // throwing, etc) can be proven to either still occur (because it's
4017 // dominated by something that has the same side-effects), or never
4018 // occur. Otherwise, we would not have been able to prove it value
4019 // equivalent to something else. For these things, we can just mark
4020 // it all dead. Note that this is different from the "ProbablyDead"
4021 // set, which may not be dominated by anything, and thus, are only
4022 // easy to prove dead if they are also side-effect free. Note that
4023 // because stores are put in terms of the stored value, we skip
4024 // stored values here. If the stored value is really dead, it will
4025 // still be marked for deletion when we process it in its own class.
4026 if (!EliminationStack.empty() && Def != EliminationStack.back() &&
4027 isa<Instruction>(Def) && !FromStore)
4028 markInstructionForDeletion(cast<Instruction>(Def));
4029 continue;
4030 }
4031 // At this point, we know it is a Use we are trying to possibly
4032 // replace.
4033
4034 assert(isa<Instruction>(U->get()) &&
4035 "Current def should have been an instruction");
4036 assert(isa<Instruction>(U->getUser()) &&
4037 "Current user should have been an instruction");
4038
4039 // If the thing we are replacing into is already marked to be dead,
4040 // this use is dead. Note that this is true regardless of whether
4041 // we have anything dominating the use or not. We do this here
4042 // because we are already walking all the uses anyway.
4043 Instruction *InstUse = cast<Instruction>(U->getUser());
4044 if (InstructionsToErase.count(InstUse)) {
4045 auto &UseCount = UseCounts[U->get()];
4046 if (--UseCount == 0) {
4047 ProbablyDead.insert(cast<Instruction>(U->get()));
4048 }
4049 }
4050
4051 // If we get to this point, and the stack is empty we must have a use
4052 // with nothing we can use to eliminate this use, so just skip it.
4053 if (EliminationStack.empty())
4054 continue;
4055
4056 Value *DominatingLeader = EliminationStack.back();
4057
4058 auto *II = dyn_cast<IntrinsicInst>(DominatingLeader);
4059 bool isSSACopy = II && II->getIntrinsicID() == Intrinsic::ssa_copy;
4060 if (isSSACopy)
4061 DominatingLeader = II->getOperand(0);
4062
4063 // Don't replace our existing users with ourselves.
4064 if (U->get() == DominatingLeader)
4065 continue;
4067 << "Found replacement " << *DominatingLeader << " for "
4068 << *U->get() << " in " << *(U->getUser()) << "\n");
4069
4070 // If we replaced something in an instruction, handle the patching of
4071 // metadata. Skip this if we are replacing predicateinfo with its
4072 // original operand, as we already know we can just drop it.
4073 auto *ReplacedInst = cast<Instruction>(U->get());
4074 auto *PI = PredInfo->getPredicateInfoFor(ReplacedInst);
4075 if (!PI || DominatingLeader != PI->OriginalOp)
4076 patchReplacementInstruction(ReplacedInst, DominatingLeader);
4077 U->set(DominatingLeader);
4078 // This is now a use of the dominating leader, which means if the
4079 // dominating leader was dead, it's now live!
4080 auto &LeaderUseCount = UseCounts[DominatingLeader];
4081 // It's about to be alive again.
4082 if (LeaderUseCount == 0 && isa<Instruction>(DominatingLeader))
4083 ProbablyDead.erase(cast<Instruction>(DominatingLeader));
4084 // For copy instructions, we use their operand as a leader,
4085 // which means we remove a user of the copy and it may become dead.
4086 if (isSSACopy) {
4087 unsigned &IIUseCount = UseCounts[II];
4088 if (--IIUseCount == 0)
4089 ProbablyDead.insert(II);
4090 }
4091 ++LeaderUseCount;
4092 AnythingReplaced = true;
4093 }
4094 }
4095 }
4096
4097 // At this point, anything still in the ProbablyDead set is actually dead if
4098 // would be trivially dead.
4099 for (auto *I : ProbablyDead)
4101 markInstructionForDeletion(I);
4102
4103 // Cleanup the congruence class.
4104 CongruenceClass::MemberSet MembersLeft;
4105 for (auto *Member : *CC)
4106 if (!isa<Instruction>(Member) ||
4107 !InstructionsToErase.count(cast<Instruction>(Member)))
4108 MembersLeft.insert(Member);
4109 CC->swap(MembersLeft);
4110
4111 // If we have possible dead stores to look at, try to eliminate them.
4112 if (CC->getStoreCount() > 0) {
4113 convertClassToLoadsAndStores(*CC, PossibleDeadStores);
4114 llvm::sort(PossibleDeadStores);
4115 ValueDFSStack EliminationStack;
4116 for (auto &VD : PossibleDeadStores) {
4117 int MemberDFSIn = VD.DFSIn;
4118 int MemberDFSOut = VD.DFSOut;
4119 Instruction *Member = cast<Instruction>(VD.Def.getPointer());
4120 if (EliminationStack.empty() ||
4121 !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut)) {
4122 // Sync to our current scope.
4123 EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
4124 if (EliminationStack.empty()) {
4125 EliminationStack.push_back(Member, MemberDFSIn, MemberDFSOut);
4126 continue;
4127 }
4128 }
4129 // We already did load elimination, so nothing to do here.
4130 if (isa<LoadInst>(Member))
4131 continue;
4132 assert(!EliminationStack.empty());
4133 Instruction *Leader = cast<Instruction>(EliminationStack.back());
4134 (void)Leader;
4135 assert(DT->dominates(Leader->getParent(), Member->getParent()));
4136 // Member is dominater by Leader, and thus dead
4137 LLVM_DEBUG(dbgs() << "Marking dead store " << *Member
4138 << " that is dominated by " << *Leader << "\n");
4139 markInstructionForDeletion(Member);
4140 CC->erase(Member);
4141 ++NumGVNDeadStores;
4142 }
4143 }
4144 }
4145 return AnythingReplaced;
4146}
4147
4148// This function provides global ranking of operations so that we can place them
4149// in a canonical order. Note that rank alone is not necessarily enough for a
4150// complete ordering, as constants all have the same rank. However, generally,
4151// we will simplify an operation with all constants so that it doesn't matter
4152// what order they appear in.
4153unsigned int NewGVN::getRank(const Value *V) const {
4154 // Prefer constants to undef to anything else
4155 // Undef is a constant, have to check it first.
4156 // Prefer poison to undef as it's less defined.
4157 // Prefer smaller constants to constantexprs
4158 // Note that the order here matters because of class inheritance
4159 if (isa<ConstantExpr>(V))
4160 return 3;
4161 if (isa<PoisonValue>(V))
4162 return 1;
4163 if (isa<UndefValue>(V))
4164 return 2;
4165 if (isa<Constant>(V))
4166 return 0;
4167 if (auto *A = dyn_cast<Argument>(V))
4168 return 4 + A->getArgNo();
4169
4170 // Need to shift the instruction DFS by number of arguments + 5 to account for
4171 // the constant and argument ranking above.
4172 unsigned Result = InstrToDFSNum(V);
4173 if (Result > 0)
4174 return 5 + NumFuncArgs + Result;
4175 // Unreachable or something else, just return a really large number.
4176 return ~0;
4177}
4178
4179// This is a function that says whether two commutative operations should
4180// have their order swapped when canonicalizing.
4181bool NewGVN::shouldSwapOperands(const Value *A, const Value *B) const {
4182 // Because we only care about a total ordering, and don't rewrite expressions
4183 // in this order, we order by rank, which will give a strict weak ordering to
4184 // everything but constants, and then we order by pointer address.
4185 return std::make_pair(getRank(A), A) > std::make_pair(getRank(B), B);
4186}
4187
4188bool NewGVN::shouldSwapOperandsForIntrinsic(const Value *A, const Value *B,
4189 const IntrinsicInst *I) const {
4190 auto LookupResult = IntrinsicInstPred.find(I);
4191 if (shouldSwapOperands(A, B)) {
4192 if (LookupResult == IntrinsicInstPred.end())
4193 IntrinsicInstPred.insert({I, B});
4194 else
4195 LookupResult->second = B;
4196 return true;
4197 }
4198
4199 if (LookupResult != IntrinsicInstPred.end()) {
4200 auto *SeenPredicate = LookupResult->second;
4201 if (SeenPredicate) {
4202 if (SeenPredicate == B)
4203 return true;
4204 else
4205 LookupResult->second = nullptr;
4206 }
4207 }
4208 return false;
4209}
4210
4212 // Apparently the order in which we get these results matter for
4213 // the old GVN (see Chandler's comment in GVN.cpp). I'll keep
4214 // the same order here, just in case.
4215 auto &AC = AM.getResult<AssumptionAnalysis>(F);
4216 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
4217 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
4218 auto &AA = AM.getResult<AAManager>(F);
4219 auto &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
4220 bool Changed =
4221 NewGVN(F, &DT, &AC, &TLI, &AA, &MSSA, F.getParent()->getDataLayout())
4222 .runGVN();
4223 if (!Changed)
4224 return PreservedAnalyses::all();
4227 return PA;
4228}
aarch64 promote const
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Rewrite undef for PHI
Unify divergent function exit nodes
This file defines the BumpPtrAllocator interface.
SmallVector< MachineOperand, 4 > Cond
This file implements the BitVector class.
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
Definition: DebugCounter.h:182
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
#define NL
std::optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1260
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
The header file for the GVN pass that contains expression handling classes.
static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl)
Definition: GVN.cpp:2006
This is the interface for a simple mod/ref and alias analysis over globals.
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
Hexagon Common GEP
static bool lookup(const GsymReader &GR, DataExtractor &Data, uint64_t &Offset, uint64_t BaseAddr, uint64_t Addr, SourceLocations &SrcLocs, llvm::Error &Err)
A Lookup helper functions.
Definition: InlineInfo.cpp:109
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:524
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
Branch Probability Basic Block static false std::string getBlockName(const MachineBasicBlock *BB)
Helper to print the name of a MBB.
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
static bool alwaysAvailable(Value *V)
Definition: NewGVN.cpp:1005
static Value * getCopyOf(const Value *V)
Definition: NewGVN.cpp:975
static bool isCopyOfPHI(const Value *V, const PHINode *PN)
Definition: NewGVN.cpp:983
static bool isCopyOfAPHI(const Value *V)
Definition: NewGVN.cpp:987
static bool okayForPHIOfOps(const Instruction *I)
Definition: NewGVN.cpp:2577
static cl::opt< bool > EnableStoreRefinement("enable-store-refinement", cl::init(false), cl::Hidden)
static bool equalsLoadStoreHelper(const T &LHS, const Expression &RHS)
Definition: NewGVN.cpp:904
static cl::opt< bool > EnablePhiOfOps("enable-phi-of-ops", cl::init(true), cl::Hidden)
Currently, the generation "phi of ops" can result in correctness issues.
This file provides the interface for LLVM's Global Value Numbering pass.
#define P(N)
if(VerifyEach)
This file defines the PointerIntPair class.
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
This file implements the PredicateInfo analysis, which creates an Extended SSA form for operations us...
@ SI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines generic set operations that may be used on set's of different types,...
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the SparseBitVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
This defines the Use class.
Value * RHS
Value * LHS
A manager for alias analyses.
bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A trivial helper function to check to see if the specified pointers are must-alias.
bool doesNotAccessMemory(const CallBase *Call)
Checks if the specified call is known to never read or write memory.
bool onlyReadsMemory(const CallBase *Call)
Checks if the specified call is known to only read from non-volatile memory (or not access memory at ...
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
Recycle small arrays allocated from a BumpPtrAllocator.
Definition: ArrayRecycler.h:28
void clear(AllocatorType &Allocator)
Release all the tracked allocations to the allocator.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:163
iterator begin() const
Definition: ArrayRef.h:151
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
reverse_iterator rbegin()
Definition: BasicBlock.h:319
InstListType::reverse_iterator reverse_iterator
Definition: BasicBlock.h:89
reverse_iterator rend()
Definition: BasicBlock.h:321
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:35
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:127
BitVector & reset()
Definition: BitVector.h:392
int find_first() const
find_first - Returns the index of the first set bit, -1 if none of the bits are set.
Definition: BitVector.h:300
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:341
void clear()
clear - Removes all bits from the bitvector.
Definition: BitVector.h:335
BitVector & set()
Definition: BitVector.h:351
bool any() const
any - Returns true if any bit is set.
Definition: BitVector.h:170
iterator_range< const_set_bits_iterator > set_bits() const
Definition: BitVector.h:140
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:66
void Reset()
Deallocate all but the current slab and reset the current pointer to the beginning of it,...
Definition: Allocator.h:123
void Deallocate(const void *Ptr, size_t Size, size_t)
Definition: Allocator.h:218
This class represents a function call, abstracting a target machine's calling convention.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:718
@ FCMP_OEQ
0 0 0 1 True if ordered and equal
Definition: InstrTypes.h:721
@ ICMP_EQ
equal
Definition: InstrTypes.h:739
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Definition: InstrTypes.h:859
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:832
static bool isImpliedTrueByMatchingCmp(Predicate Pred1, Predicate Pred2)
Determine if Pred1 implies Pred2 is true when two compares have matching operands.
static bool isImpliedFalseByMatchingCmp(Predicate Pred1, Predicate Pred2)
Determine if Pred1 implies Pred2 is false when two compares have matching operands.
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
Definition: Constants.h:203
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:833
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:197
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:840
This is an important base class in LLVM.
Definition: Constant.h:41
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:356
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
static void setCounterValue(unsigned ID, int64_t Count)
Definition: DebugCounter.h:113
static bool isCounterSet(unsigned ID)
Definition: DebugCounter.h:100
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:72
static int64_t getCounterValue(unsigned ID)
Definition: DebugCounter.h:105
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:202
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
bool erase(const KeyT &Val)
Definition: DenseMap.h:315
unsigned size() const
Definition: DenseMap.h:99
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:151
iterator end()
Definition: DenseMap.h:84
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
unsigned getDFSNumOut() const
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
void updateDFSNumbers() const
updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
Class representing an expression and its matching format.
bool isPresplitCoroutine() const
Determine if the function is presplit coroutine.
Definition: Function.h:492
bool equals(const Expression &Other) const override
Definition: NewGVN.cpp:910
bool equals(const Expression &Other) const override
Definition: NewGVN.cpp:914
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
bool isCommutative() const LLVM_READONLY
Return true if the instruction is commutative:
bool isAtomic() const LLVM_READONLY
Return true if this instruction has an AtomicOrdering of unordered or higher.
const BasicBlock * getParent() const
Definition: Instruction.h:90
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:74
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:82
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
An instruction for reading from memory.
Definition: Instructions.h:177
Value * getPointerOperand()
Definition: Instructions.h:264
bool isSimple() const
Definition: Instructions.h:256
BasicBlock * getBlock() const
Definition: MemorySSA.h:164
Represents phi nodes for memory accesses.
Definition: MemorySSA.h:479
BasicBlock * getIncomingBlock(unsigned I) const
Return incoming basic block number i.
Definition: MemorySSA.h:540
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:936
This is the generic walker interface for walkers of MemorySSA.
Definition: MemorySSA.h:1017
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:1046
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
MemorySSAWalker * getWalker()
Definition: MemorySSA.cpp:1557
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:717
MemoryAccess * getLiveOnEntryDef() const
Definition: MemorySSA.h:741
const DefsList * getBlockDefs(const BasicBlock *BB) const
Return the list of MemoryDef's and MemoryPhi's for a given basic block.
Definition: MemorySSA.h:765
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
Definition: MemorySSA.h:737
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:252
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:305
PreservedAnalyses run(Function &F, AnalysisManager< Function > &AM)
Run the pass over the function.
Definition: NewGVN.cpp:4211
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
PointerIntPair - This class implements a pair of a pointer and small integer.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1750
Encapsulates PredicateInfo, including all data associated with memory accesses.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
SmallPtrSetIterator< PtrType > const_iterator
Definition: SmallPtrSet.h:355
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
Definition: SmallPtrSet.h:379
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
iterator end() const
Definition: SmallPtrSet.h:408
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
iterator begin() const
Definition: SmallPtrSet.h:403
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:389
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
bool empty() const
Definition: SmallVector.h:94
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
An instruction for storing to memory.
Definition: Instructions.h:301
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
PointerType * getPointerTo(unsigned AddrSpace=0) const
Return a pointer to the current type.
static IntegerType * getInt8Ty(LLVMContext &C)
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1731
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
op_range operands()
Definition: User.h:242
Value * getOperand(unsigned i) const
Definition: User.h:169
unsigned getNumOperands() const
Definition: User.h:191
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
iterator_range< user_iterator > users()
Definition: Value.h:421
void deleteValue()
Delete a pointer to a generic Value.
Definition: Value.cpp:109
bool use_empty() const
Definition: Value.h:344
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
iterator find(const_arg_type_t< ValueT > V)
Definition: DenseSet.h:179
bool erase(const ValueT &V)
Definition: DenseSet.h:101
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
An opaque object representing a hash code.
Definition: Hashing.h:74
A range adaptor for a pair of iterators.
friend const_iterator begin(StringRef path, Style style)
Get begin iterator over path.
Definition: Path.cpp:226
friend const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
Constant * getConstantLoadValueForLoad(Constant *SrcVal, unsigned Offset, Type *LoadTy, const DataLayout &DL)
Definition: VNCoercion.cpp:508
int analyzeLoadFromClobberingStore(Type *LoadTy, Value *LoadPtr, StoreInst *DepSI, const DataLayout &DL)
This function determines whether a value for the pointer LoadPtr can be extracted from the store at D...
Definition: VNCoercion.cpp:211
int analyzeLoadFromClobberingLoad(Type *LoadTy, Value *LoadPtr, LoadInst *DepLI, const DataLayout &DL)
This function determines whether a value for the pointer LoadPtr can be extracted from the load at De...
Definition: VNCoercion.cpp:317
Constant * getConstantMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset, Type *LoadTy, const DataLayout &DL)
Definition: VNCoercion.cpp:567
int analyzeLoadFromClobberingMemInst(Type *LoadTy, Value *LoadPtr, MemIntrinsic *DepMI, const DataLayout &DL)
This function determines whether a value for the pointer LoadPtr can be extracted from the memory int...
Definition: VNCoercion.cpp:352
Constant * getConstantStoreValueForLoad(Constant *SrcVal, unsigned Offset, Type *LoadTy, const DataLayout &DL)
Definition: VNCoercion.cpp:453
@ CE
Windows NT (Windows on ARM)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
std::vector< ExecutorAddr > LookupResult
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:406
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:1819
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,...
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1777
SDValue getStoredValue(SDValue Op)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
mapped_iterator< ItTy, FuncTy > map_iterator(ItTy I, FuncTy F)
Definition: STLExtras.h:456
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
Value * simplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty, const SimplifyQuery &Q)
Given operands for a CastInst, fold the result or return null.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1826
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
Definition: Local.cpp:398
bool wouldInstructionBeTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction would have no side effects if it was not used.
Definition: Local.cpp:417
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:511
Constant * ConstantFoldInstOperands(Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1744
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void patchReplacementInstruction(Instruction *I, Value *Repl)
Patch the replacement so that it is not more restrictive than the value being replaced.
Definition: Local.cpp:2796
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
Definition: STLExtras.h:664
bool salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
Value * simplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a CmpInst, fold the result or return null.
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:1921
iterator_range< df_iterator< T > > depth_first(const T &G)
bool all_equal(std::initializer_list< T > Values)
Returns true if all Values in the initializer lists are equal or the list.
Definition: STLExtras.h:2101
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Value * simplifyGEPInst(Type *SrcTy, Value *Ptr, ArrayRef< Value * > Indices, bool InBounds, const SimplifyQuery &Q)
Given operands for a GetElementPtrInst, fold the result or return null.
Value * simplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, const SimplifyQuery &Q)
Given operands for a SelectInst, fold the result or return null.
iterator_range< def_chain_iterator< T, true > > optimized_def_chain(T MA)
Definition: MemorySSA.h:1365
Definition: BitVector.h:858
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
PointerIntPair< Value *, 1, bool > Def
Definition: NewGVN.cpp:3519
bool operator<(const ValueDFS &Other) const
Definition: NewGVN.cpp:3522
DOTGraphTraits - Template class that can be specialized to customize how graphs are converted to 'dot...
static unsigned getHashValue(const ExactEqualsExpression &E)
Definition: NewGVN.cpp:461
static unsigned getHashValue(const Expression *E)
Definition: NewGVN.cpp:457
static const Expression * getTombstoneKey()
Definition: NewGVN.cpp:451
static bool isEqual(const Expression *LHS, const Expression *RHS)
Definition: NewGVN.cpp:471
static const Expression * getEmptyKey()
Definition: NewGVN.cpp:445
static bool isEqual(const ExactEqualsExpression &LHS, const Expression *RHS)
Definition: NewGVN.cpp:465
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: DenseMapInfo.h:51
ExactEqualsExpression(const Expression &E)
Definition: NewGVN.cpp:435
const Expression & E
Definition: NewGVN.cpp:433
hash_code getComputedHash() const
Definition: NewGVN.cpp:437
bool operator==(const Expression &Other) const
Definition: NewGVN.cpp:439
SimplifyQuery getWithInstruction(Instruction *I) const
unsigned int LocalNum