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