109467b48Spatrick //===- NewGVN.cpp - Global Value Numbering Pass ---------------------------===//
209467b48Spatrick //
309467b48Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
409467b48Spatrick // See https://llvm.org/LICENSE.txt for license information.
509467b48Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
609467b48Spatrick //
709467b48Spatrick //===----------------------------------------------------------------------===//
809467b48Spatrick //
909467b48Spatrick /// \file
1009467b48Spatrick /// This file implements the new LLVM's Global Value Numbering pass.
1109467b48Spatrick /// GVN partitions values computed by a function into congruence classes.
1209467b48Spatrick /// Values ending up in the same congruence class are guaranteed to be the same
1309467b48Spatrick /// for every execution of the program. In that respect, congruency is a
1409467b48Spatrick /// compile-time approximation of equivalence of values at runtime.
1509467b48Spatrick /// The algorithm implemented here uses a sparse formulation and it's based
1609467b48Spatrick /// on the ideas described in the paper:
1709467b48Spatrick /// "A Sparse Algorithm for Predicated Global Value Numbering" from
1809467b48Spatrick /// Karthik Gargi.
1909467b48Spatrick ///
2009467b48Spatrick /// A brief overview of the algorithm: The algorithm is essentially the same as
2109467b48Spatrick /// the standard RPO value numbering algorithm (a good reference is the paper
2209467b48Spatrick /// "SCC based value numbering" by L. Taylor Simpson) with one major difference:
2309467b48Spatrick /// The RPO algorithm proceeds, on every iteration, to process every reachable
2409467b48Spatrick /// block and every instruction in that block. This is because the standard RPO
2509467b48Spatrick /// algorithm does not track what things have the same value number, it only
2609467b48Spatrick /// tracks what the value number of a given operation is (the mapping is
2709467b48Spatrick /// operation -> value number). Thus, when a value number of an operation
2809467b48Spatrick /// changes, it must reprocess everything to ensure all uses of a value number
2909467b48Spatrick /// get updated properly. In constrast, the sparse algorithm we use *also*
3009467b48Spatrick /// tracks what operations have a given value number (IE it also tracks the
3109467b48Spatrick /// reverse mapping from value number -> operations with that value number), so
3209467b48Spatrick /// that it only needs to reprocess the instructions that are affected when
3309467b48Spatrick /// something's value number changes. The vast majority of complexity and code
3409467b48Spatrick /// in this file is devoted to tracking what value numbers could change for what
3509467b48Spatrick /// instructions when various things happen. The rest of the algorithm is
3609467b48Spatrick /// devoted to performing symbolic evaluation, forward propagation, and
3709467b48Spatrick /// simplification of operations based on the value numbers deduced so far
3809467b48Spatrick ///
3909467b48Spatrick /// In order to make the GVN mostly-complete, we use a technique derived from
4009467b48Spatrick /// "Detection of Redundant Expressions: A Complete and Polynomial-time
4109467b48Spatrick /// Algorithm in SSA" by R.R. Pai. The source of incompleteness in most SSA
4209467b48Spatrick /// based GVN algorithms is related to their inability to detect equivalence
4309467b48Spatrick /// between phi of ops (IE phi(a+b, c+d)) and op of phis (phi(a,c) + phi(b, d)).
4409467b48Spatrick /// We resolve this issue by generating the equivalent "phi of ops" form for
4509467b48Spatrick /// each op of phis we see, in a way that only takes polynomial time to resolve.
4609467b48Spatrick ///
4709467b48Spatrick /// We also do not perform elimination by using any published algorithm. All
4809467b48Spatrick /// published algorithms are O(Instructions). Instead, we use a technique that
4909467b48Spatrick /// is O(number of operations with the same value number), enabling us to skip
5009467b48Spatrick /// trying to eliminate things that have unique value numbers.
5109467b48Spatrick //
5209467b48Spatrick //===----------------------------------------------------------------------===//
5309467b48Spatrick
5409467b48Spatrick #include "llvm/Transforms/Scalar/NewGVN.h"
5509467b48Spatrick #include "llvm/ADT/ArrayRef.h"
5609467b48Spatrick #include "llvm/ADT/BitVector.h"
5709467b48Spatrick #include "llvm/ADT/DenseMap.h"
5809467b48Spatrick #include "llvm/ADT/DenseMapInfo.h"
5909467b48Spatrick #include "llvm/ADT/DenseSet.h"
6009467b48Spatrick #include "llvm/ADT/DepthFirstIterator.h"
6109467b48Spatrick #include "llvm/ADT/GraphTraits.h"
6209467b48Spatrick #include "llvm/ADT/Hashing.h"
6309467b48Spatrick #include "llvm/ADT/PointerIntPair.h"
6409467b48Spatrick #include "llvm/ADT/PostOrderIterator.h"
6573471bf0Spatrick #include "llvm/ADT/SetOperations.h"
6609467b48Spatrick #include "llvm/ADT/SmallPtrSet.h"
6709467b48Spatrick #include "llvm/ADT/SmallVector.h"
6809467b48Spatrick #include "llvm/ADT/SparseBitVector.h"
6909467b48Spatrick #include "llvm/ADT/Statistic.h"
7009467b48Spatrick #include "llvm/ADT/iterator_range.h"
7109467b48Spatrick #include "llvm/Analysis/AliasAnalysis.h"
7209467b48Spatrick #include "llvm/Analysis/AssumptionCache.h"
7309467b48Spatrick #include "llvm/Analysis/CFGPrinter.h"
7409467b48Spatrick #include "llvm/Analysis/ConstantFolding.h"
7509467b48Spatrick #include "llvm/Analysis/GlobalsModRef.h"
7609467b48Spatrick #include "llvm/Analysis/InstructionSimplify.h"
7709467b48Spatrick #include "llvm/Analysis/MemoryBuiltins.h"
7809467b48Spatrick #include "llvm/Analysis/MemorySSA.h"
7909467b48Spatrick #include "llvm/Analysis/TargetLibraryInfo.h"
80*d415bd75Srobert #include "llvm/Analysis/ValueTracking.h"
8109467b48Spatrick #include "llvm/IR/Argument.h"
8209467b48Spatrick #include "llvm/IR/BasicBlock.h"
8309467b48Spatrick #include "llvm/IR/Constant.h"
8409467b48Spatrick #include "llvm/IR/Constants.h"
8509467b48Spatrick #include "llvm/IR/Dominators.h"
8609467b48Spatrick #include "llvm/IR/Function.h"
8709467b48Spatrick #include "llvm/IR/InstrTypes.h"
8809467b48Spatrick #include "llvm/IR/Instruction.h"
8909467b48Spatrick #include "llvm/IR/Instructions.h"
9009467b48Spatrick #include "llvm/IR/IntrinsicInst.h"
9109467b48Spatrick #include "llvm/IR/PatternMatch.h"
9209467b48Spatrick #include "llvm/IR/Type.h"
9309467b48Spatrick #include "llvm/IR/Use.h"
9409467b48Spatrick #include "llvm/IR/User.h"
9509467b48Spatrick #include "llvm/IR/Value.h"
9609467b48Spatrick #include "llvm/InitializePasses.h"
9709467b48Spatrick #include "llvm/Pass.h"
9809467b48Spatrick #include "llvm/Support/Allocator.h"
9909467b48Spatrick #include "llvm/Support/ArrayRecycler.h"
10009467b48Spatrick #include "llvm/Support/Casting.h"
10109467b48Spatrick #include "llvm/Support/CommandLine.h"
10209467b48Spatrick #include "llvm/Support/Debug.h"
10309467b48Spatrick #include "llvm/Support/DebugCounter.h"
10409467b48Spatrick #include "llvm/Support/ErrorHandling.h"
10509467b48Spatrick #include "llvm/Support/PointerLikeTypeTraits.h"
10609467b48Spatrick #include "llvm/Support/raw_ostream.h"
10709467b48Spatrick #include "llvm/Transforms/Scalar.h"
10809467b48Spatrick #include "llvm/Transforms/Scalar/GVNExpression.h"
109097a140dSpatrick #include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
11009467b48Spatrick #include "llvm/Transforms/Utils/Local.h"
11109467b48Spatrick #include "llvm/Transforms/Utils/PredicateInfo.h"
11209467b48Spatrick #include "llvm/Transforms/Utils/VNCoercion.h"
11309467b48Spatrick #include <algorithm>
11409467b48Spatrick #include <cassert>
11509467b48Spatrick #include <cstdint>
11609467b48Spatrick #include <iterator>
11709467b48Spatrick #include <map>
11809467b48Spatrick #include <memory>
11909467b48Spatrick #include <set>
12009467b48Spatrick #include <string>
12109467b48Spatrick #include <tuple>
12209467b48Spatrick #include <utility>
12309467b48Spatrick #include <vector>
12409467b48Spatrick
12509467b48Spatrick using namespace llvm;
12609467b48Spatrick using namespace llvm::GVNExpression;
12709467b48Spatrick using namespace llvm::VNCoercion;
12809467b48Spatrick using namespace llvm::PatternMatch;
12909467b48Spatrick
13009467b48Spatrick #define DEBUG_TYPE "newgvn"
13109467b48Spatrick
13209467b48Spatrick STATISTIC(NumGVNInstrDeleted, "Number of instructions deleted");
13309467b48Spatrick STATISTIC(NumGVNBlocksDeleted, "Number of blocks deleted");
13409467b48Spatrick STATISTIC(NumGVNOpsSimplified, "Number of Expressions simplified");
13509467b48Spatrick STATISTIC(NumGVNPhisAllSame, "Number of PHIs whos arguments are all the same");
13609467b48Spatrick STATISTIC(NumGVNMaxIterations,
13709467b48Spatrick "Maximum Number of iterations it took to converge GVN");
13809467b48Spatrick STATISTIC(NumGVNLeaderChanges, "Number of leader changes");
13909467b48Spatrick STATISTIC(NumGVNSortedLeaderChanges, "Number of sorted leader changes");
14009467b48Spatrick STATISTIC(NumGVNAvoidedSortedLeaderChanges,
14109467b48Spatrick "Number of avoided sorted leader changes");
14209467b48Spatrick STATISTIC(NumGVNDeadStores, "Number of redundant/dead stores eliminated");
14309467b48Spatrick STATISTIC(NumGVNPHIOfOpsCreated, "Number of PHI of ops created");
14409467b48Spatrick STATISTIC(NumGVNPHIOfOpsEliminations,
14509467b48Spatrick "Number of things eliminated using PHI of ops");
14609467b48Spatrick DEBUG_COUNTER(VNCounter, "newgvn-vn",
14709467b48Spatrick "Controls which instructions are value numbered");
14809467b48Spatrick DEBUG_COUNTER(PHIOfOpsCounter, "newgvn-phi",
14909467b48Spatrick "Controls which instructions we create phi of ops for");
15009467b48Spatrick // Currently store defining access refinement is too slow due to basicaa being
15109467b48Spatrick // egregiously slow. This flag lets us keep it working while we work on this
15209467b48Spatrick // issue.
15309467b48Spatrick static cl::opt<bool> EnableStoreRefinement("enable-store-refinement",
15409467b48Spatrick cl::init(false), cl::Hidden);
15509467b48Spatrick
15609467b48Spatrick /// Currently, the generation "phi of ops" can result in correctness issues.
15709467b48Spatrick static cl::opt<bool> EnablePhiOfOps("enable-phi-of-ops", cl::init(true),
15809467b48Spatrick cl::Hidden);
15909467b48Spatrick
16009467b48Spatrick //===----------------------------------------------------------------------===//
16109467b48Spatrick // GVN Pass
16209467b48Spatrick //===----------------------------------------------------------------------===//
16309467b48Spatrick
16409467b48Spatrick // Anchor methods.
16509467b48Spatrick namespace llvm {
16609467b48Spatrick namespace GVNExpression {
16709467b48Spatrick
16809467b48Spatrick Expression::~Expression() = default;
16909467b48Spatrick BasicExpression::~BasicExpression() = default;
17009467b48Spatrick CallExpression::~CallExpression() = default;
17109467b48Spatrick LoadExpression::~LoadExpression() = default;
17209467b48Spatrick StoreExpression::~StoreExpression() = default;
17309467b48Spatrick AggregateValueExpression::~AggregateValueExpression() = default;
17409467b48Spatrick PHIExpression::~PHIExpression() = default;
17509467b48Spatrick
17609467b48Spatrick } // end namespace GVNExpression
17709467b48Spatrick } // end namespace llvm
17809467b48Spatrick
17909467b48Spatrick namespace {
18009467b48Spatrick
18109467b48Spatrick // Tarjan's SCC finding algorithm with Nuutila's improvements
18209467b48Spatrick // SCCIterator is actually fairly complex for the simple thing we want.
18309467b48Spatrick // It also wants to hand us SCC's that are unrelated to the phi node we ask
18409467b48Spatrick // about, and have us process them there or risk redoing work.
18509467b48Spatrick // Graph traits over a filter iterator also doesn't work that well here.
18609467b48Spatrick // This SCC finder is specialized to walk use-def chains, and only follows
18709467b48Spatrick // instructions,
18809467b48Spatrick // not generic values (arguments, etc).
18909467b48Spatrick struct TarjanSCC {
TarjanSCC__anon9b3904d50111::TarjanSCC19009467b48Spatrick TarjanSCC() : Components(1) {}
19109467b48Spatrick
Start__anon9b3904d50111::TarjanSCC19209467b48Spatrick void Start(const Instruction *Start) {
19309467b48Spatrick if (Root.lookup(Start) == 0)
19409467b48Spatrick FindSCC(Start);
19509467b48Spatrick }
19609467b48Spatrick
getComponentFor__anon9b3904d50111::TarjanSCC19709467b48Spatrick const SmallPtrSetImpl<const Value *> &getComponentFor(const Value *V) const {
19809467b48Spatrick unsigned ComponentID = ValueToComponent.lookup(V);
19909467b48Spatrick
20009467b48Spatrick assert(ComponentID > 0 &&
20109467b48Spatrick "Asking for a component for a value we never processed");
20209467b48Spatrick return Components[ComponentID];
20309467b48Spatrick }
20409467b48Spatrick
20509467b48Spatrick private:
FindSCC__anon9b3904d50111::TarjanSCC20609467b48Spatrick void FindSCC(const Instruction *I) {
20709467b48Spatrick Root[I] = ++DFSNum;
20809467b48Spatrick // Store the DFS Number we had before it possibly gets incremented.
20909467b48Spatrick unsigned int OurDFS = DFSNum;
210*d415bd75Srobert for (const auto &Op : I->operands()) {
21109467b48Spatrick if (auto *InstOp = dyn_cast<Instruction>(Op)) {
21209467b48Spatrick if (Root.lookup(Op) == 0)
21309467b48Spatrick FindSCC(InstOp);
21409467b48Spatrick if (!InComponent.count(Op))
21509467b48Spatrick Root[I] = std::min(Root.lookup(I), Root.lookup(Op));
21609467b48Spatrick }
21709467b48Spatrick }
21809467b48Spatrick // See if we really were the root of a component, by seeing if we still have
21909467b48Spatrick // our DFSNumber. If we do, we are the root of the component, and we have
22009467b48Spatrick // completed a component. If we do not, we are not the root of a component,
22109467b48Spatrick // and belong on the component stack.
22209467b48Spatrick if (Root.lookup(I) == OurDFS) {
22309467b48Spatrick unsigned ComponentID = Components.size();
22409467b48Spatrick Components.resize(Components.size() + 1);
22509467b48Spatrick auto &Component = Components.back();
22609467b48Spatrick Component.insert(I);
22709467b48Spatrick LLVM_DEBUG(dbgs() << "Component root is " << *I << "\n");
22809467b48Spatrick InComponent.insert(I);
22909467b48Spatrick ValueToComponent[I] = ComponentID;
23009467b48Spatrick // Pop a component off the stack and label it.
23109467b48Spatrick while (!Stack.empty() && Root.lookup(Stack.back()) >= OurDFS) {
23209467b48Spatrick auto *Member = Stack.back();
23309467b48Spatrick LLVM_DEBUG(dbgs() << "Component member is " << *Member << "\n");
23409467b48Spatrick Component.insert(Member);
23509467b48Spatrick InComponent.insert(Member);
23609467b48Spatrick ValueToComponent[Member] = ComponentID;
23709467b48Spatrick Stack.pop_back();
23809467b48Spatrick }
23909467b48Spatrick } else {
24009467b48Spatrick // Part of a component, push to stack
24109467b48Spatrick Stack.push_back(I);
24209467b48Spatrick }
24309467b48Spatrick }
24409467b48Spatrick
24509467b48Spatrick unsigned int DFSNum = 1;
24609467b48Spatrick SmallPtrSet<const Value *, 8> InComponent;
24709467b48Spatrick DenseMap<const Value *, unsigned int> Root;
24809467b48Spatrick SmallVector<const Value *, 8> Stack;
24909467b48Spatrick
25009467b48Spatrick // Store the components as vector of ptr sets, because we need the topo order
25109467b48Spatrick // of SCC's, but not individual member order
25209467b48Spatrick SmallVector<SmallPtrSet<const Value *, 8>, 8> Components;
25309467b48Spatrick
25409467b48Spatrick DenseMap<const Value *, unsigned> ValueToComponent;
25509467b48Spatrick };
25609467b48Spatrick
25709467b48Spatrick // Congruence classes represent the set of expressions/instructions
25809467b48Spatrick // that are all the same *during some scope in the function*.
25909467b48Spatrick // That is, because of the way we perform equality propagation, and
26009467b48Spatrick // because of memory value numbering, it is not correct to assume
26109467b48Spatrick // you can willy-nilly replace any member with any other at any
26209467b48Spatrick // point in the function.
26309467b48Spatrick //
26409467b48Spatrick // For any Value in the Member set, it is valid to replace any dominated member
26509467b48Spatrick // with that Value.
26609467b48Spatrick //
26709467b48Spatrick // Every congruence class has a leader, and the leader is used to symbolize
26809467b48Spatrick // instructions in a canonical way (IE every operand of an instruction that is a
26909467b48Spatrick // member of the same congruence class will always be replaced with leader
27009467b48Spatrick // during symbolization). To simplify symbolization, we keep the leader as a
27109467b48Spatrick // constant if class can be proved to be a constant value. Otherwise, the
27209467b48Spatrick // leader is the member of the value set with the smallest DFS number. Each
27309467b48Spatrick // congruence class also has a defining expression, though the expression may be
27409467b48Spatrick // null. If it exists, it can be used for forward propagation and reassociation
27509467b48Spatrick // of values.
27609467b48Spatrick
27709467b48Spatrick // For memory, we also track a representative MemoryAccess, and a set of memory
27809467b48Spatrick // members for MemoryPhis (which have no real instructions). Note that for
27909467b48Spatrick // memory, it seems tempting to try to split the memory members into a
28009467b48Spatrick // MemoryCongruenceClass or something. Unfortunately, this does not work
28109467b48Spatrick // easily. The value numbering of a given memory expression depends on the
28209467b48Spatrick // leader of the memory congruence class, and the leader of memory congruence
28309467b48Spatrick // class depends on the value numbering of a given memory expression. This
28409467b48Spatrick // leads to wasted propagation, and in some cases, missed optimization. For
28509467b48Spatrick // example: If we had value numbered two stores together before, but now do not,
28609467b48Spatrick // we move them to a new value congruence class. This in turn will move at one
28709467b48Spatrick // of the memorydefs to a new memory congruence class. Which in turn, affects
28809467b48Spatrick // the value numbering of the stores we just value numbered (because the memory
28909467b48Spatrick // congruence class is part of the value number). So while theoretically
29009467b48Spatrick // possible to split them up, it turns out to be *incredibly* complicated to get
29109467b48Spatrick // it to work right, because of the interdependency. While structurally
29209467b48Spatrick // slightly messier, it is algorithmically much simpler and faster to do what we
29309467b48Spatrick // do here, and track them both at once in the same class.
29409467b48Spatrick // Note: The default iterators for this class iterate over values
29509467b48Spatrick class CongruenceClass {
29609467b48Spatrick public:
29709467b48Spatrick using MemberType = Value;
29809467b48Spatrick using MemberSet = SmallPtrSet<MemberType *, 4>;
29909467b48Spatrick using MemoryMemberType = MemoryPhi;
30009467b48Spatrick using MemoryMemberSet = SmallPtrSet<const MemoryMemberType *, 2>;
30109467b48Spatrick
CongruenceClass(unsigned ID)30209467b48Spatrick explicit CongruenceClass(unsigned ID) : ID(ID) {}
CongruenceClass(unsigned ID,Value * Leader,const Expression * E)30309467b48Spatrick CongruenceClass(unsigned ID, Value *Leader, const Expression *E)
30409467b48Spatrick : ID(ID), RepLeader(Leader), DefiningExpr(E) {}
30509467b48Spatrick
getID() const30609467b48Spatrick unsigned getID() const { return ID; }
30709467b48Spatrick
30809467b48Spatrick // True if this class has no members left. This is mainly used for assertion
30909467b48Spatrick // purposes, and for skipping empty classes.
isDead() const31009467b48Spatrick bool isDead() const {
31109467b48Spatrick // If it's both dead from a value perspective, and dead from a memory
31209467b48Spatrick // perspective, it's really dead.
31309467b48Spatrick return empty() && memory_empty();
31409467b48Spatrick }
31509467b48Spatrick
31609467b48Spatrick // Leader functions
getLeader() const31709467b48Spatrick Value *getLeader() const { return RepLeader; }
setLeader(Value * Leader)31809467b48Spatrick void setLeader(Value *Leader) { RepLeader = Leader; }
getNextLeader() const31909467b48Spatrick const std::pair<Value *, unsigned int> &getNextLeader() const {
32009467b48Spatrick return NextLeader;
32109467b48Spatrick }
resetNextLeader()32209467b48Spatrick void resetNextLeader() { NextLeader = {nullptr, ~0}; }
addPossibleNextLeader(std::pair<Value *,unsigned int> LeaderPair)32309467b48Spatrick void addPossibleNextLeader(std::pair<Value *, unsigned int> LeaderPair) {
32409467b48Spatrick if (LeaderPair.second < NextLeader.second)
32509467b48Spatrick NextLeader = LeaderPair;
32609467b48Spatrick }
32709467b48Spatrick
getStoredValue() const32809467b48Spatrick Value *getStoredValue() const { return RepStoredValue; }
setStoredValue(Value * Leader)32909467b48Spatrick void setStoredValue(Value *Leader) { RepStoredValue = Leader; }
getMemoryLeader() const33009467b48Spatrick const MemoryAccess *getMemoryLeader() const { return RepMemoryAccess; }
setMemoryLeader(const MemoryAccess * Leader)33109467b48Spatrick void setMemoryLeader(const MemoryAccess *Leader) { RepMemoryAccess = Leader; }
33209467b48Spatrick
33309467b48Spatrick // Forward propagation info
getDefiningExpr() const33409467b48Spatrick const Expression *getDefiningExpr() const { return DefiningExpr; }
33509467b48Spatrick
33609467b48Spatrick // Value member set
empty() const33709467b48Spatrick bool empty() const { return Members.empty(); }
size() const33809467b48Spatrick unsigned size() const { return Members.size(); }
begin() const33909467b48Spatrick MemberSet::const_iterator begin() const { return Members.begin(); }
end() const34009467b48Spatrick MemberSet::const_iterator end() const { return Members.end(); }
insert(MemberType * M)34109467b48Spatrick void insert(MemberType *M) { Members.insert(M); }
erase(MemberType * M)34209467b48Spatrick void erase(MemberType *M) { Members.erase(M); }
swap(MemberSet & Other)34309467b48Spatrick void swap(MemberSet &Other) { Members.swap(Other); }
34409467b48Spatrick
34509467b48Spatrick // Memory member set
memory_empty() const34609467b48Spatrick bool memory_empty() const { return MemoryMembers.empty(); }
memory_size() const34709467b48Spatrick unsigned memory_size() const { return MemoryMembers.size(); }
memory_begin() const34809467b48Spatrick MemoryMemberSet::const_iterator memory_begin() const {
34909467b48Spatrick return MemoryMembers.begin();
35009467b48Spatrick }
memory_end() const35109467b48Spatrick MemoryMemberSet::const_iterator memory_end() const {
35209467b48Spatrick return MemoryMembers.end();
35309467b48Spatrick }
memory() const35409467b48Spatrick iterator_range<MemoryMemberSet::const_iterator> memory() const {
35509467b48Spatrick return make_range(memory_begin(), memory_end());
35609467b48Spatrick }
35709467b48Spatrick
memory_insert(const MemoryMemberType * M)35809467b48Spatrick void memory_insert(const MemoryMemberType *M) { MemoryMembers.insert(M); }
memory_erase(const MemoryMemberType * M)35909467b48Spatrick void memory_erase(const MemoryMemberType *M) { MemoryMembers.erase(M); }
36009467b48Spatrick
36109467b48Spatrick // Store count
getStoreCount() const36209467b48Spatrick unsigned getStoreCount() const { return StoreCount; }
incStoreCount()36309467b48Spatrick void incStoreCount() { ++StoreCount; }
decStoreCount()36409467b48Spatrick void decStoreCount() {
36509467b48Spatrick assert(StoreCount != 0 && "Store count went negative");
36609467b48Spatrick --StoreCount;
36709467b48Spatrick }
36809467b48Spatrick
36909467b48Spatrick // True if this class has no memory members.
definesNoMemory() const37009467b48Spatrick bool definesNoMemory() const { return StoreCount == 0 && memory_empty(); }
37109467b48Spatrick
37209467b48Spatrick // Return true if two congruence classes are equivalent to each other. This
37309467b48Spatrick // means that every field but the ID number and the dead field are equivalent.
isEquivalentTo(const CongruenceClass * Other) const37409467b48Spatrick bool isEquivalentTo(const CongruenceClass *Other) const {
37509467b48Spatrick if (!Other)
37609467b48Spatrick return false;
37709467b48Spatrick if (this == Other)
37809467b48Spatrick return true;
37909467b48Spatrick
38009467b48Spatrick if (std::tie(StoreCount, RepLeader, RepStoredValue, RepMemoryAccess) !=
38109467b48Spatrick std::tie(Other->StoreCount, Other->RepLeader, Other->RepStoredValue,
38209467b48Spatrick Other->RepMemoryAccess))
38309467b48Spatrick return false;
38409467b48Spatrick if (DefiningExpr != Other->DefiningExpr)
38509467b48Spatrick if (!DefiningExpr || !Other->DefiningExpr ||
38609467b48Spatrick *DefiningExpr != *Other->DefiningExpr)
38709467b48Spatrick return false;
38809467b48Spatrick
38909467b48Spatrick if (Members.size() != Other->Members.size())
39009467b48Spatrick return false;
39109467b48Spatrick
39273471bf0Spatrick return llvm::set_is_subset(Members, Other->Members);
39309467b48Spatrick }
39409467b48Spatrick
39509467b48Spatrick private:
39609467b48Spatrick unsigned ID;
39709467b48Spatrick
39809467b48Spatrick // Representative leader.
39909467b48Spatrick Value *RepLeader = nullptr;
40009467b48Spatrick
40109467b48Spatrick // The most dominating leader after our current leader, because the member set
40209467b48Spatrick // is not sorted and is expensive to keep sorted all the time.
40309467b48Spatrick std::pair<Value *, unsigned int> NextLeader = {nullptr, ~0U};
40409467b48Spatrick
40509467b48Spatrick // If this is represented by a store, the value of the store.
40609467b48Spatrick Value *RepStoredValue = nullptr;
40709467b48Spatrick
40809467b48Spatrick // If this class contains MemoryDefs or MemoryPhis, this is the leading memory
40909467b48Spatrick // access.
41009467b48Spatrick const MemoryAccess *RepMemoryAccess = nullptr;
41109467b48Spatrick
41209467b48Spatrick // Defining Expression.
41309467b48Spatrick const Expression *DefiningExpr = nullptr;
41409467b48Spatrick
41509467b48Spatrick // Actual members of this class.
41609467b48Spatrick MemberSet Members;
41709467b48Spatrick
41809467b48Spatrick // This is the set of MemoryPhis that exist in the class. MemoryDefs and
41909467b48Spatrick // MemoryUses have real instructions representing them, so we only need to
42009467b48Spatrick // track MemoryPhis here.
42109467b48Spatrick MemoryMemberSet MemoryMembers;
42209467b48Spatrick
42309467b48Spatrick // Number of stores in this congruence class.
42409467b48Spatrick // This is used so we can detect store equivalence changes properly.
42509467b48Spatrick int StoreCount = 0;
42609467b48Spatrick };
42709467b48Spatrick
42809467b48Spatrick } // end anonymous namespace
42909467b48Spatrick
43009467b48Spatrick namespace llvm {
43109467b48Spatrick
43209467b48Spatrick struct ExactEqualsExpression {
43309467b48Spatrick const Expression &E;
43409467b48Spatrick
ExactEqualsExpressionllvm::ExactEqualsExpression43509467b48Spatrick explicit ExactEqualsExpression(const Expression &E) : E(E) {}
43609467b48Spatrick
getComputedHashllvm::ExactEqualsExpression43709467b48Spatrick hash_code getComputedHash() const { return E.getComputedHash(); }
43809467b48Spatrick
operator ==llvm::ExactEqualsExpression43909467b48Spatrick bool operator==(const Expression &Other) const {
44009467b48Spatrick return E.exactlyEquals(Other);
44109467b48Spatrick }
44209467b48Spatrick };
44309467b48Spatrick
44409467b48Spatrick template <> struct DenseMapInfo<const Expression *> {
getEmptyKeyllvm::DenseMapInfo44509467b48Spatrick static const Expression *getEmptyKey() {
44609467b48Spatrick auto Val = static_cast<uintptr_t>(-1);
44709467b48Spatrick Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable;
44809467b48Spatrick return reinterpret_cast<const Expression *>(Val);
44909467b48Spatrick }
45009467b48Spatrick
getTombstoneKeyllvm::DenseMapInfo45109467b48Spatrick static const Expression *getTombstoneKey() {
45209467b48Spatrick auto Val = static_cast<uintptr_t>(~1U);
45309467b48Spatrick Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable;
45409467b48Spatrick return reinterpret_cast<const Expression *>(Val);
45509467b48Spatrick }
45609467b48Spatrick
getHashValuellvm::DenseMapInfo45709467b48Spatrick static unsigned getHashValue(const Expression *E) {
45809467b48Spatrick return E->getComputedHash();
45909467b48Spatrick }
46009467b48Spatrick
getHashValuellvm::DenseMapInfo46109467b48Spatrick static unsigned getHashValue(const ExactEqualsExpression &E) {
46209467b48Spatrick return E.getComputedHash();
46309467b48Spatrick }
46409467b48Spatrick
isEqualllvm::DenseMapInfo46509467b48Spatrick static bool isEqual(const ExactEqualsExpression &LHS, const Expression *RHS) {
46609467b48Spatrick if (RHS == getTombstoneKey() || RHS == getEmptyKey())
46709467b48Spatrick return false;
46809467b48Spatrick return LHS == *RHS;
46909467b48Spatrick }
47009467b48Spatrick
isEqualllvm::DenseMapInfo47109467b48Spatrick static bool isEqual(const Expression *LHS, const Expression *RHS) {
47209467b48Spatrick if (LHS == RHS)
47309467b48Spatrick return true;
47409467b48Spatrick if (LHS == getTombstoneKey() || RHS == getTombstoneKey() ||
47509467b48Spatrick LHS == getEmptyKey() || RHS == getEmptyKey())
47609467b48Spatrick return false;
47709467b48Spatrick // Compare hashes before equality. This is *not* what the hashtable does,
47809467b48Spatrick // since it is computing it modulo the number of buckets, whereas we are
47909467b48Spatrick // using the full hash keyspace. Since the hashes are precomputed, this
48009467b48Spatrick // check is *much* faster than equality.
48109467b48Spatrick if (LHS->getComputedHash() != RHS->getComputedHash())
48209467b48Spatrick return false;
48309467b48Spatrick return *LHS == *RHS;
48409467b48Spatrick }
48509467b48Spatrick };
48609467b48Spatrick
48709467b48Spatrick } // end namespace llvm
48809467b48Spatrick
48909467b48Spatrick namespace {
49009467b48Spatrick
49109467b48Spatrick class NewGVN {
49209467b48Spatrick Function &F;
49309467b48Spatrick DominatorTree *DT = nullptr;
49409467b48Spatrick const TargetLibraryInfo *TLI = nullptr;
49509467b48Spatrick AliasAnalysis *AA = nullptr;
49609467b48Spatrick MemorySSA *MSSA = nullptr;
49709467b48Spatrick MemorySSAWalker *MSSAWalker = nullptr;
498097a140dSpatrick AssumptionCache *AC = nullptr;
49909467b48Spatrick const DataLayout &DL;
50009467b48Spatrick std::unique_ptr<PredicateInfo> PredInfo;
50109467b48Spatrick
50209467b48Spatrick // These are the only two things the create* functions should have
50309467b48Spatrick // side-effects on due to allocating memory.
50409467b48Spatrick mutable BumpPtrAllocator ExpressionAllocator;
50509467b48Spatrick mutable ArrayRecycler<Value *> ArgRecycler;
50609467b48Spatrick mutable TarjanSCC SCCFinder;
50709467b48Spatrick const SimplifyQuery SQ;
50809467b48Spatrick
50909467b48Spatrick // Number of function arguments, used by ranking
51009467b48Spatrick unsigned int NumFuncArgs = 0;
51109467b48Spatrick
51209467b48Spatrick // RPOOrdering of basic blocks
51309467b48Spatrick DenseMap<const DomTreeNode *, unsigned> RPOOrdering;
51409467b48Spatrick
51509467b48Spatrick // Congruence class info.
51609467b48Spatrick
51709467b48Spatrick // This class is called INITIAL in the paper. It is the class everything
51809467b48Spatrick // startsout in, and represents any value. Being an optimistic analysis,
51909467b48Spatrick // anything in the TOP class has the value TOP, which is indeterminate and
52009467b48Spatrick // equivalent to everything.
52109467b48Spatrick CongruenceClass *TOPClass = nullptr;
52209467b48Spatrick std::vector<CongruenceClass *> CongruenceClasses;
52309467b48Spatrick unsigned NextCongruenceNum = 0;
52409467b48Spatrick
52509467b48Spatrick // Value Mappings.
52609467b48Spatrick DenseMap<Value *, CongruenceClass *> ValueToClass;
52709467b48Spatrick DenseMap<Value *, const Expression *> ValueToExpression;
52809467b48Spatrick
52909467b48Spatrick // Value PHI handling, used to make equivalence between phi(op, op) and
53009467b48Spatrick // op(phi, phi).
53109467b48Spatrick // These mappings just store various data that would normally be part of the
53209467b48Spatrick // IR.
53309467b48Spatrick SmallPtrSet<const Instruction *, 8> PHINodeUses;
53409467b48Spatrick
53509467b48Spatrick DenseMap<const Value *, bool> OpSafeForPHIOfOps;
53609467b48Spatrick
53709467b48Spatrick // Map a temporary instruction we created to a parent block.
53809467b48Spatrick DenseMap<const Value *, BasicBlock *> TempToBlock;
53909467b48Spatrick
54009467b48Spatrick // Map between the already in-program instructions and the temporary phis we
54109467b48Spatrick // created that they are known equivalent to.
54209467b48Spatrick DenseMap<const Value *, PHINode *> RealToTemp;
54309467b48Spatrick
54409467b48Spatrick // In order to know when we should re-process instructions that have
54509467b48Spatrick // phi-of-ops, we track the set of expressions that they needed as
54609467b48Spatrick // leaders. When we discover new leaders for those expressions, we process the
54709467b48Spatrick // associated phi-of-op instructions again in case they have changed. The
54809467b48Spatrick // other way they may change is if they had leaders, and those leaders
54909467b48Spatrick // disappear. However, at the point they have leaders, there are uses of the
55009467b48Spatrick // relevant operands in the created phi node, and so they will get reprocessed
55109467b48Spatrick // through the normal user marking we perform.
55209467b48Spatrick mutable DenseMap<const Value *, SmallPtrSet<Value *, 2>> AdditionalUsers;
55309467b48Spatrick DenseMap<const Expression *, SmallPtrSet<Instruction *, 2>>
55409467b48Spatrick ExpressionToPhiOfOps;
55509467b48Spatrick
55609467b48Spatrick // Map from temporary operation to MemoryAccess.
55709467b48Spatrick DenseMap<const Instruction *, MemoryUseOrDef *> TempToMemory;
55809467b48Spatrick
55909467b48Spatrick // Set of all temporary instructions we created.
56009467b48Spatrick // Note: This will include instructions that were just created during value
56109467b48Spatrick // numbering. The way to test if something is using them is to check
56209467b48Spatrick // RealToTemp.
56309467b48Spatrick DenseSet<Instruction *> AllTempInstructions;
56409467b48Spatrick
56509467b48Spatrick // This is the set of instructions to revisit on a reachability change. At
56609467b48Spatrick // the end of the main iteration loop it will contain at least all the phi of
56709467b48Spatrick // ops instructions that will be changed to phis, as well as regular phis.
56809467b48Spatrick // During the iteration loop, it may contain other things, such as phi of ops
56909467b48Spatrick // instructions that used edge reachability to reach a result, and so need to
57009467b48Spatrick // be revisited when the edge changes, independent of whether the phi they
57109467b48Spatrick // depended on changes.
57209467b48Spatrick DenseMap<BasicBlock *, SparseBitVector<>> RevisitOnReachabilityChange;
57309467b48Spatrick
57409467b48Spatrick // Mapping from predicate info we used to the instructions we used it with.
57509467b48Spatrick // In order to correctly ensure propagation, we must keep track of what
57609467b48Spatrick // comparisons we used, so that when the values of the comparisons change, we
57709467b48Spatrick // propagate the information to the places we used the comparison.
57809467b48Spatrick mutable DenseMap<const Value *, SmallPtrSet<Instruction *, 2>>
57909467b48Spatrick PredicateToUsers;
58009467b48Spatrick
58109467b48Spatrick // the same reasoning as PredicateToUsers. When we skip MemoryAccesses for
58209467b48Spatrick // stores, we no longer can rely solely on the def-use chains of MemorySSA.
58309467b48Spatrick mutable DenseMap<const MemoryAccess *, SmallPtrSet<MemoryAccess *, 2>>
58409467b48Spatrick MemoryToUsers;
58509467b48Spatrick
58609467b48Spatrick // A table storing which memorydefs/phis represent a memory state provably
58709467b48Spatrick // equivalent to another memory state.
58809467b48Spatrick // We could use the congruence class machinery, but the MemoryAccess's are
58909467b48Spatrick // abstract memory states, so they can only ever be equivalent to each other,
59009467b48Spatrick // and not to constants, etc.
59109467b48Spatrick DenseMap<const MemoryAccess *, CongruenceClass *> MemoryAccessToClass;
59209467b48Spatrick
59309467b48Spatrick // We could, if we wanted, build MemoryPhiExpressions and
59409467b48Spatrick // MemoryVariableExpressions, etc, and value number them the same way we value
59509467b48Spatrick // number phi expressions. For the moment, this seems like overkill. They
59609467b48Spatrick // can only exist in one of three states: they can be TOP (equal to
59709467b48Spatrick // everything), Equivalent to something else, or unique. Because we do not
59809467b48Spatrick // create expressions for them, we need to simulate leader change not just
59909467b48Spatrick // when they change class, but when they change state. Note: We can do the
60009467b48Spatrick // same thing for phis, and avoid having phi expressions if we wanted, We
60109467b48Spatrick // should eventually unify in one direction or the other, so this is a little
60209467b48Spatrick // bit of an experiment in which turns out easier to maintain.
60309467b48Spatrick enum MemoryPhiState { MPS_Invalid, MPS_TOP, MPS_Equivalent, MPS_Unique };
60409467b48Spatrick DenseMap<const MemoryPhi *, MemoryPhiState> MemoryPhiState;
60509467b48Spatrick
60609467b48Spatrick enum InstCycleState { ICS_Unknown, ICS_CycleFree, ICS_Cycle };
60709467b48Spatrick mutable DenseMap<const Instruction *, InstCycleState> InstCycleState;
60809467b48Spatrick
60909467b48Spatrick // Expression to class mapping.
61009467b48Spatrick using ExpressionClassMap = DenseMap<const Expression *, CongruenceClass *>;
61109467b48Spatrick ExpressionClassMap ExpressionToClass;
61209467b48Spatrick
61309467b48Spatrick // We have a single expression that represents currently DeadExpressions.
61409467b48Spatrick // For dead expressions we can prove will stay dead, we mark them with
61509467b48Spatrick // DFS number zero. However, it's possible in the case of phi nodes
61609467b48Spatrick // for us to assume/prove all arguments are dead during fixpointing.
61709467b48Spatrick // We use DeadExpression for that case.
61809467b48Spatrick DeadExpression *SingletonDeadExpression = nullptr;
61909467b48Spatrick
62009467b48Spatrick // Which values have changed as a result of leader changes.
62109467b48Spatrick SmallPtrSet<Value *, 8> LeaderChanges;
62209467b48Spatrick
62309467b48Spatrick // Reachability info.
62409467b48Spatrick using BlockEdge = BasicBlockEdge;
62509467b48Spatrick DenseSet<BlockEdge> ReachableEdges;
62609467b48Spatrick SmallPtrSet<const BasicBlock *, 8> ReachableBlocks;
62709467b48Spatrick
62809467b48Spatrick // This is a bitvector because, on larger functions, we may have
62909467b48Spatrick // thousands of touched instructions at once (entire blocks,
63009467b48Spatrick // instructions with hundreds of uses, etc). Even with optimization
63109467b48Spatrick // for when we mark whole blocks as touched, when this was a
63209467b48Spatrick // SmallPtrSet or DenseSet, for some functions, we spent >20% of all
63309467b48Spatrick // the time in GVN just managing this list. The bitvector, on the
63409467b48Spatrick // other hand, efficiently supports test/set/clear of both
63509467b48Spatrick // individual and ranges, as well as "find next element" This
63609467b48Spatrick // enables us to use it as a worklist with essentially 0 cost.
63709467b48Spatrick BitVector TouchedInstructions;
63809467b48Spatrick
63909467b48Spatrick DenseMap<const BasicBlock *, std::pair<unsigned, unsigned>> BlockInstRange;
640*d415bd75Srobert mutable DenseMap<const IntrinsicInst *, const Value *> IntrinsicInstPred;
64109467b48Spatrick
64209467b48Spatrick #ifndef NDEBUG
64309467b48Spatrick // Debugging for how many times each block and instruction got processed.
64409467b48Spatrick DenseMap<const Value *, unsigned> ProcessedCount;
64509467b48Spatrick #endif
64609467b48Spatrick
64709467b48Spatrick // DFS info.
64809467b48Spatrick // This contains a mapping from Instructions to DFS numbers.
64909467b48Spatrick // The numbering starts at 1. An instruction with DFS number zero
65009467b48Spatrick // means that the instruction is dead.
65109467b48Spatrick DenseMap<const Value *, unsigned> InstrDFS;
65209467b48Spatrick
65309467b48Spatrick // This contains the mapping DFS numbers to instructions.
65409467b48Spatrick SmallVector<Value *, 32> DFSToInstr;
65509467b48Spatrick
65609467b48Spatrick // Deletion info.
65709467b48Spatrick SmallPtrSet<Instruction *, 8> InstructionsToErase;
65809467b48Spatrick
65909467b48Spatrick public:
NewGVN(Function & F,DominatorTree * DT,AssumptionCache * AC,TargetLibraryInfo * TLI,AliasAnalysis * AA,MemorySSA * MSSA,const DataLayout & DL)66009467b48Spatrick NewGVN(Function &F, DominatorTree *DT, AssumptionCache *AC,
66109467b48Spatrick TargetLibraryInfo *TLI, AliasAnalysis *AA, MemorySSA *MSSA,
66209467b48Spatrick const DataLayout &DL)
663097a140dSpatrick : F(F), DT(DT), TLI(TLI), AA(AA), MSSA(MSSA), AC(AC), DL(DL),
66409467b48Spatrick PredInfo(std::make_unique<PredicateInfo>(F, *DT, *AC)),
66573471bf0Spatrick SQ(DL, TLI, DT, AC, /*CtxI=*/nullptr, /*UseInstrInfo=*/false,
66673471bf0Spatrick /*CanUseUndef=*/false) {}
66709467b48Spatrick
66809467b48Spatrick bool runGVN();
66909467b48Spatrick
67009467b48Spatrick private:
67173471bf0Spatrick /// Helper struct return a Expression with an optional extra dependency.
67273471bf0Spatrick struct ExprResult {
67373471bf0Spatrick const Expression *Expr;
67473471bf0Spatrick Value *ExtraDep;
67573471bf0Spatrick const PredicateBase *PredDep;
67673471bf0Spatrick
ExprResult__anon9b3904d50211::NewGVN::ExprResult67773471bf0Spatrick ExprResult(const Expression *Expr, Value *ExtraDep = nullptr,
67873471bf0Spatrick const PredicateBase *PredDep = nullptr)
67973471bf0Spatrick : Expr(Expr), ExtraDep(ExtraDep), PredDep(PredDep) {}
68073471bf0Spatrick ExprResult(const ExprResult &) = delete;
ExprResult__anon9b3904d50211::NewGVN::ExprResult68173471bf0Spatrick ExprResult(ExprResult &&Other)
68273471bf0Spatrick : Expr(Other.Expr), ExtraDep(Other.ExtraDep), PredDep(Other.PredDep) {
68373471bf0Spatrick Other.Expr = nullptr;
68473471bf0Spatrick Other.ExtraDep = nullptr;
68573471bf0Spatrick Other.PredDep = nullptr;
68673471bf0Spatrick }
68773471bf0Spatrick ExprResult &operator=(const ExprResult &Other) = delete;
68873471bf0Spatrick ExprResult &operator=(ExprResult &&Other) = delete;
68973471bf0Spatrick
~ExprResult__anon9b3904d50211::NewGVN::ExprResult69073471bf0Spatrick ~ExprResult() { assert(!ExtraDep && "unhandled ExtraDep"); }
69173471bf0Spatrick
operator bool__anon9b3904d50211::NewGVN::ExprResult69273471bf0Spatrick operator bool() const { return Expr; }
69373471bf0Spatrick
none__anon9b3904d50211::NewGVN::ExprResult69473471bf0Spatrick static ExprResult none() { return {nullptr, nullptr, nullptr}; }
some__anon9b3904d50211::NewGVN::ExprResult69573471bf0Spatrick static ExprResult some(const Expression *Expr, Value *ExtraDep = nullptr) {
69673471bf0Spatrick return {Expr, ExtraDep, nullptr};
69773471bf0Spatrick }
some__anon9b3904d50211::NewGVN::ExprResult69873471bf0Spatrick static ExprResult some(const Expression *Expr,
69973471bf0Spatrick const PredicateBase *PredDep) {
70073471bf0Spatrick return {Expr, nullptr, PredDep};
70173471bf0Spatrick }
some__anon9b3904d50211::NewGVN::ExprResult70273471bf0Spatrick static ExprResult some(const Expression *Expr, Value *ExtraDep,
70373471bf0Spatrick const PredicateBase *PredDep) {
70473471bf0Spatrick return {Expr, ExtraDep, PredDep};
70573471bf0Spatrick }
70673471bf0Spatrick };
70773471bf0Spatrick
70809467b48Spatrick // Expression handling.
70973471bf0Spatrick ExprResult createExpression(Instruction *) const;
71009467b48Spatrick const Expression *createBinaryExpression(unsigned, Type *, Value *, Value *,
71109467b48Spatrick Instruction *) const;
71209467b48Spatrick
71309467b48Spatrick // Our canonical form for phi arguments is a pair of incoming value, incoming
71409467b48Spatrick // basic block.
71509467b48Spatrick using ValPair = std::pair<Value *, BasicBlock *>;
71609467b48Spatrick
71709467b48Spatrick PHIExpression *createPHIExpression(ArrayRef<ValPair>, const Instruction *,
71809467b48Spatrick BasicBlock *, bool &HasBackEdge,
71909467b48Spatrick bool &OriginalOpsConstant) const;
72009467b48Spatrick const DeadExpression *createDeadExpression() const;
72109467b48Spatrick const VariableExpression *createVariableExpression(Value *) const;
72209467b48Spatrick const ConstantExpression *createConstantExpression(Constant *) const;
72309467b48Spatrick const Expression *createVariableOrConstant(Value *V) const;
72409467b48Spatrick const UnknownExpression *createUnknownExpression(Instruction *) const;
72509467b48Spatrick const StoreExpression *createStoreExpression(StoreInst *,
72609467b48Spatrick const MemoryAccess *) const;
72709467b48Spatrick LoadExpression *createLoadExpression(Type *, Value *, LoadInst *,
72809467b48Spatrick const MemoryAccess *) const;
72909467b48Spatrick const CallExpression *createCallExpression(CallInst *,
73009467b48Spatrick const MemoryAccess *) const;
73109467b48Spatrick const AggregateValueExpression *
73209467b48Spatrick createAggregateValueExpression(Instruction *) const;
73309467b48Spatrick bool setBasicExpressionInfo(Instruction *, BasicExpression *) const;
73409467b48Spatrick
73509467b48Spatrick // Congruence class handling.
createCongruenceClass(Value * Leader,const Expression * E)73609467b48Spatrick CongruenceClass *createCongruenceClass(Value *Leader, const Expression *E) {
73709467b48Spatrick auto *result = new CongruenceClass(NextCongruenceNum++, Leader, E);
73809467b48Spatrick CongruenceClasses.emplace_back(result);
73909467b48Spatrick return result;
74009467b48Spatrick }
74109467b48Spatrick
createMemoryClass(MemoryAccess * MA)74209467b48Spatrick CongruenceClass *createMemoryClass(MemoryAccess *MA) {
74309467b48Spatrick auto *CC = createCongruenceClass(nullptr, nullptr);
74409467b48Spatrick CC->setMemoryLeader(MA);
74509467b48Spatrick return CC;
74609467b48Spatrick }
74709467b48Spatrick
ensureLeaderOfMemoryClass(MemoryAccess * MA)74809467b48Spatrick CongruenceClass *ensureLeaderOfMemoryClass(MemoryAccess *MA) {
74909467b48Spatrick auto *CC = getMemoryClass(MA);
75009467b48Spatrick if (CC->getMemoryLeader() != MA)
75109467b48Spatrick CC = createMemoryClass(MA);
75209467b48Spatrick return CC;
75309467b48Spatrick }
75409467b48Spatrick
createSingletonCongruenceClass(Value * Member)75509467b48Spatrick CongruenceClass *createSingletonCongruenceClass(Value *Member) {
75609467b48Spatrick CongruenceClass *CClass = createCongruenceClass(Member, nullptr);
75709467b48Spatrick CClass->insert(Member);
75809467b48Spatrick ValueToClass[Member] = CClass;
75909467b48Spatrick return CClass;
76009467b48Spatrick }
76109467b48Spatrick
76209467b48Spatrick void initializeCongruenceClasses(Function &F);
76309467b48Spatrick const Expression *makePossiblePHIOfOps(Instruction *,
76409467b48Spatrick SmallPtrSetImpl<Value *> &);
76509467b48Spatrick Value *findLeaderForInst(Instruction *ValueOp,
76609467b48Spatrick SmallPtrSetImpl<Value *> &Visited,
76709467b48Spatrick MemoryAccess *MemAccess, Instruction *OrigInst,
76809467b48Spatrick BasicBlock *PredBB);
76909467b48Spatrick bool OpIsSafeForPHIOfOps(Value *Op, const BasicBlock *PHIBlock,
77009467b48Spatrick SmallPtrSetImpl<const Value *> &);
77109467b48Spatrick void addPhiOfOps(PHINode *Op, BasicBlock *BB, Instruction *ExistingValue);
77209467b48Spatrick void removePhiOfOps(Instruction *I, PHINode *PHITemp);
77309467b48Spatrick
77409467b48Spatrick // Value number an Instruction or MemoryPhi.
77509467b48Spatrick void valueNumberMemoryPhi(MemoryPhi *);
77609467b48Spatrick void valueNumberInstruction(Instruction *);
77709467b48Spatrick
77809467b48Spatrick // Symbolic evaluation.
77973471bf0Spatrick ExprResult checkExprResults(Expression *, Instruction *, Value *) const;
78073471bf0Spatrick ExprResult performSymbolicEvaluation(Value *,
78109467b48Spatrick SmallPtrSetImpl<Value *> &) const;
78209467b48Spatrick const Expression *performSymbolicLoadCoercion(Type *, Value *, LoadInst *,
78309467b48Spatrick Instruction *,
78409467b48Spatrick MemoryAccess *) const;
78509467b48Spatrick const Expression *performSymbolicLoadEvaluation(Instruction *) const;
78609467b48Spatrick const Expression *performSymbolicStoreEvaluation(Instruction *) const;
78773471bf0Spatrick ExprResult performSymbolicCallEvaluation(Instruction *) const;
78809467b48Spatrick void sortPHIOps(MutableArrayRef<ValPair> Ops) const;
78909467b48Spatrick const Expression *performSymbolicPHIEvaluation(ArrayRef<ValPair>,
79009467b48Spatrick Instruction *I,
79109467b48Spatrick BasicBlock *PHIBlock) const;
79209467b48Spatrick const Expression *performSymbolicAggrValueEvaluation(Instruction *) const;
79373471bf0Spatrick ExprResult performSymbolicCmpEvaluation(Instruction *) const;
794*d415bd75Srobert ExprResult performSymbolicPredicateInfoEvaluation(IntrinsicInst *) const;
79509467b48Spatrick
79609467b48Spatrick // Congruence finding.
79709467b48Spatrick bool someEquivalentDominates(const Instruction *, const Instruction *) const;
79809467b48Spatrick Value *lookupOperandLeader(Value *) const;
79909467b48Spatrick CongruenceClass *getClassForExpression(const Expression *E) const;
80009467b48Spatrick void performCongruenceFinding(Instruction *, const Expression *);
80109467b48Spatrick void moveValueToNewCongruenceClass(Instruction *, const Expression *,
80209467b48Spatrick CongruenceClass *, CongruenceClass *);
80309467b48Spatrick void moveMemoryToNewCongruenceClass(Instruction *, MemoryAccess *,
80409467b48Spatrick CongruenceClass *, CongruenceClass *);
80509467b48Spatrick Value *getNextValueLeader(CongruenceClass *) const;
80609467b48Spatrick const MemoryAccess *getNextMemoryLeader(CongruenceClass *) const;
80709467b48Spatrick bool setMemoryClass(const MemoryAccess *From, CongruenceClass *To);
80809467b48Spatrick CongruenceClass *getMemoryClass(const MemoryAccess *MA) const;
80909467b48Spatrick const MemoryAccess *lookupMemoryLeader(const MemoryAccess *) const;
81009467b48Spatrick bool isMemoryAccessTOP(const MemoryAccess *) const;
81109467b48Spatrick
81209467b48Spatrick // Ranking
81309467b48Spatrick unsigned int getRank(const Value *) const;
81409467b48Spatrick bool shouldSwapOperands(const Value *, const Value *) const;
815*d415bd75Srobert bool shouldSwapOperandsForIntrinsic(const Value *, const Value *,
816*d415bd75Srobert const IntrinsicInst *I) const;
81709467b48Spatrick
81809467b48Spatrick // Reachability handling.
81909467b48Spatrick void updateReachableEdge(BasicBlock *, BasicBlock *);
82009467b48Spatrick void processOutgoingEdges(Instruction *, BasicBlock *);
82109467b48Spatrick Value *findConditionEquivalence(Value *) const;
82209467b48Spatrick
82309467b48Spatrick // Elimination.
82409467b48Spatrick struct ValueDFS;
82509467b48Spatrick void convertClassToDFSOrdered(const CongruenceClass &,
82609467b48Spatrick SmallVectorImpl<ValueDFS> &,
82709467b48Spatrick DenseMap<const Value *, unsigned int> &,
82809467b48Spatrick SmallPtrSetImpl<Instruction *> &) const;
82909467b48Spatrick void convertClassToLoadsAndStores(const CongruenceClass &,
83009467b48Spatrick SmallVectorImpl<ValueDFS> &) const;
83109467b48Spatrick
83209467b48Spatrick bool eliminateInstructions(Function &);
83309467b48Spatrick void replaceInstruction(Instruction *, Value *);
83409467b48Spatrick void markInstructionForDeletion(Instruction *);
83509467b48Spatrick void deleteInstructionsInBlock(BasicBlock *);
83609467b48Spatrick Value *findPHIOfOpsLeader(const Expression *, const Instruction *,
83709467b48Spatrick const BasicBlock *) const;
83809467b48Spatrick
83909467b48Spatrick // Various instruction touch utilities
84009467b48Spatrick template <typename Map, typename KeyType>
84109467b48Spatrick void touchAndErase(Map &, const KeyType &);
84209467b48Spatrick void markUsersTouched(Value *);
84309467b48Spatrick void markMemoryUsersTouched(const MemoryAccess *);
84409467b48Spatrick void markMemoryDefTouched(const MemoryAccess *);
84509467b48Spatrick void markPredicateUsersTouched(Instruction *);
84609467b48Spatrick void markValueLeaderChangeTouched(CongruenceClass *CC);
84709467b48Spatrick void markMemoryLeaderChangeTouched(CongruenceClass *CC);
84809467b48Spatrick void markPhiOfOpsChanged(const Expression *E);
84909467b48Spatrick void addMemoryUsers(const MemoryAccess *To, MemoryAccess *U) const;
85009467b48Spatrick void addAdditionalUsers(Value *To, Value *User) const;
85173471bf0Spatrick void addAdditionalUsers(ExprResult &Res, Instruction *User) const;
85209467b48Spatrick
85309467b48Spatrick // Main loop of value numbering
85409467b48Spatrick void iterateTouchedInstructions();
85509467b48Spatrick
85609467b48Spatrick // Utilities.
85709467b48Spatrick void cleanupTables();
85809467b48Spatrick std::pair<unsigned, unsigned> assignDFSNumbers(BasicBlock *, unsigned);
85909467b48Spatrick void updateProcessedCount(const Value *V);
86009467b48Spatrick void verifyMemoryCongruency() const;
86109467b48Spatrick void verifyIterationSettled(Function &F);
86209467b48Spatrick void verifyStoreExpressions() const;
86309467b48Spatrick bool singleReachablePHIPath(SmallPtrSet<const MemoryAccess *, 8> &,
86409467b48Spatrick const MemoryAccess *, const MemoryAccess *) const;
86509467b48Spatrick BasicBlock *getBlockForValue(Value *V) const;
86609467b48Spatrick void deleteExpression(const Expression *E) const;
86709467b48Spatrick MemoryUseOrDef *getMemoryAccess(const Instruction *) const;
86809467b48Spatrick MemoryPhi *getMemoryAccess(const BasicBlock *) const;
86909467b48Spatrick template <class T, class Range> T *getMinDFSOfRange(const Range &) const;
87009467b48Spatrick
InstrToDFSNum(const Value * V) const87109467b48Spatrick unsigned InstrToDFSNum(const Value *V) const {
87209467b48Spatrick assert(isa<Instruction>(V) && "This should not be used for MemoryAccesses");
87309467b48Spatrick return InstrDFS.lookup(V);
87409467b48Spatrick }
87509467b48Spatrick
InstrToDFSNum(const MemoryAccess * MA) const87609467b48Spatrick unsigned InstrToDFSNum(const MemoryAccess *MA) const {
87709467b48Spatrick return MemoryToDFSNum(MA);
87809467b48Spatrick }
87909467b48Spatrick
InstrFromDFSNum(unsigned DFSNum)88009467b48Spatrick Value *InstrFromDFSNum(unsigned DFSNum) { return DFSToInstr[DFSNum]; }
88109467b48Spatrick
88209467b48Spatrick // Given a MemoryAccess, return the relevant instruction DFS number. Note:
88309467b48Spatrick // This deliberately takes a value so it can be used with Use's, which will
88409467b48Spatrick // auto-convert to Value's but not to MemoryAccess's.
MemoryToDFSNum(const Value * MA) const88509467b48Spatrick unsigned MemoryToDFSNum(const Value *MA) const {
88609467b48Spatrick assert(isa<MemoryAccess>(MA) &&
88709467b48Spatrick "This should not be used with instructions");
88809467b48Spatrick return isa<MemoryUseOrDef>(MA)
88909467b48Spatrick ? InstrToDFSNum(cast<MemoryUseOrDef>(MA)->getMemoryInst())
89009467b48Spatrick : InstrDFS.lookup(MA);
89109467b48Spatrick }
89209467b48Spatrick
89309467b48Spatrick bool isCycleFree(const Instruction *) const;
89409467b48Spatrick bool isBackedge(BasicBlock *From, BasicBlock *To) const;
89509467b48Spatrick
89609467b48Spatrick // Debug counter info. When verifying, we have to reset the value numbering
89709467b48Spatrick // debug counter to the same state it started in to get the same results.
89809467b48Spatrick int64_t StartingVNCounter = 0;
89909467b48Spatrick };
90009467b48Spatrick
90109467b48Spatrick } // end anonymous namespace
90209467b48Spatrick
90309467b48Spatrick template <typename T>
equalsLoadStoreHelper(const T & LHS,const Expression & RHS)90409467b48Spatrick static bool equalsLoadStoreHelper(const T &LHS, const Expression &RHS) {
90509467b48Spatrick if (!isa<LoadExpression>(RHS) && !isa<StoreExpression>(RHS))
90609467b48Spatrick return false;
90709467b48Spatrick return LHS.MemoryExpression::equals(RHS);
90809467b48Spatrick }
90909467b48Spatrick
equals(const Expression & Other) const91009467b48Spatrick bool LoadExpression::equals(const Expression &Other) const {
91109467b48Spatrick return equalsLoadStoreHelper(*this, Other);
91209467b48Spatrick }
91309467b48Spatrick
equals(const Expression & Other) const91409467b48Spatrick bool StoreExpression::equals(const Expression &Other) const {
91509467b48Spatrick if (!equalsLoadStoreHelper(*this, Other))
91609467b48Spatrick return false;
91709467b48Spatrick // Make sure that store vs store includes the value operand.
91809467b48Spatrick if (const auto *S = dyn_cast<StoreExpression>(&Other))
91909467b48Spatrick if (getStoredValue() != S->getStoredValue())
92009467b48Spatrick return false;
92109467b48Spatrick return true;
92209467b48Spatrick }
92309467b48Spatrick
92409467b48Spatrick // Determine if the edge From->To is a backedge
isBackedge(BasicBlock * From,BasicBlock * To) const92509467b48Spatrick bool NewGVN::isBackedge(BasicBlock *From, BasicBlock *To) const {
92609467b48Spatrick return From == To ||
92709467b48Spatrick RPOOrdering.lookup(DT->getNode(From)) >=
92809467b48Spatrick RPOOrdering.lookup(DT->getNode(To));
92909467b48Spatrick }
93009467b48Spatrick
93109467b48Spatrick #ifndef NDEBUG
getBlockName(const BasicBlock * B)93209467b48Spatrick static std::string getBlockName(const BasicBlock *B) {
933097a140dSpatrick return DOTGraphTraits<DOTFuncInfo *>::getSimpleNodeLabel(B, nullptr);
93409467b48Spatrick }
93509467b48Spatrick #endif
93609467b48Spatrick
93709467b48Spatrick // Get a MemoryAccess for an instruction, fake or real.
getMemoryAccess(const Instruction * I) const93809467b48Spatrick MemoryUseOrDef *NewGVN::getMemoryAccess(const Instruction *I) const {
93909467b48Spatrick auto *Result = MSSA->getMemoryAccess(I);
94009467b48Spatrick return Result ? Result : TempToMemory.lookup(I);
94109467b48Spatrick }
94209467b48Spatrick
94309467b48Spatrick // Get a MemoryPhi for a basic block. These are all real.
getMemoryAccess(const BasicBlock * BB) const94409467b48Spatrick MemoryPhi *NewGVN::getMemoryAccess(const BasicBlock *BB) const {
94509467b48Spatrick return MSSA->getMemoryAccess(BB);
94609467b48Spatrick }
94709467b48Spatrick
94809467b48Spatrick // Get the basic block from an instruction/memory value.
getBlockForValue(Value * V) const94909467b48Spatrick BasicBlock *NewGVN::getBlockForValue(Value *V) const {
95009467b48Spatrick if (auto *I = dyn_cast<Instruction>(V)) {
95109467b48Spatrick auto *Parent = I->getParent();
95209467b48Spatrick if (Parent)
95309467b48Spatrick return Parent;
95409467b48Spatrick Parent = TempToBlock.lookup(V);
95509467b48Spatrick assert(Parent && "Every fake instruction should have a block");
95609467b48Spatrick return Parent;
95709467b48Spatrick }
95809467b48Spatrick
95909467b48Spatrick auto *MP = dyn_cast<MemoryPhi>(V);
96009467b48Spatrick assert(MP && "Should have been an instruction or a MemoryPhi");
96109467b48Spatrick return MP->getBlock();
96209467b48Spatrick }
96309467b48Spatrick
96409467b48Spatrick // Delete a definitely dead expression, so it can be reused by the expression
96509467b48Spatrick // allocator. Some of these are not in creation functions, so we have to accept
96609467b48Spatrick // const versions.
deleteExpression(const Expression * E) const96709467b48Spatrick void NewGVN::deleteExpression(const Expression *E) const {
96809467b48Spatrick assert(isa<BasicExpression>(E));
96909467b48Spatrick auto *BE = cast<BasicExpression>(E);
97009467b48Spatrick const_cast<BasicExpression *>(BE)->deallocateOperands(ArgRecycler);
97109467b48Spatrick ExpressionAllocator.Deallocate(E);
97209467b48Spatrick }
97309467b48Spatrick
97409467b48Spatrick // If V is a predicateinfo copy, get the thing it is a copy of.
getCopyOf(const Value * V)97509467b48Spatrick static Value *getCopyOf(const Value *V) {
97609467b48Spatrick if (auto *II = dyn_cast<IntrinsicInst>(V))
97709467b48Spatrick if (II->getIntrinsicID() == Intrinsic::ssa_copy)
97809467b48Spatrick return II->getOperand(0);
97909467b48Spatrick return nullptr;
98009467b48Spatrick }
98109467b48Spatrick
98209467b48Spatrick // Return true if V is really PN, even accounting for predicateinfo copies.
isCopyOfPHI(const Value * V,const PHINode * PN)98309467b48Spatrick static bool isCopyOfPHI(const Value *V, const PHINode *PN) {
98409467b48Spatrick return V == PN || getCopyOf(V) == PN;
98509467b48Spatrick }
98609467b48Spatrick
isCopyOfAPHI(const Value * V)98709467b48Spatrick static bool isCopyOfAPHI(const Value *V) {
98809467b48Spatrick auto *CO = getCopyOf(V);
98909467b48Spatrick return CO && isa<PHINode>(CO);
99009467b48Spatrick }
99109467b48Spatrick
99209467b48Spatrick // Sort PHI Operands into a canonical order. What we use here is an RPO
99309467b48Spatrick // order. The BlockInstRange numbers are generated in an RPO walk of the basic
99409467b48Spatrick // blocks.
sortPHIOps(MutableArrayRef<ValPair> Ops) const99509467b48Spatrick void NewGVN::sortPHIOps(MutableArrayRef<ValPair> Ops) const {
99609467b48Spatrick llvm::sort(Ops, [&](const ValPair &P1, const ValPair &P2) {
99709467b48Spatrick return BlockInstRange.lookup(P1.second).first <
99809467b48Spatrick BlockInstRange.lookup(P2.second).first;
99909467b48Spatrick });
100009467b48Spatrick }
100109467b48Spatrick
100209467b48Spatrick // Return true if V is a value that will always be available (IE can
100309467b48Spatrick // be placed anywhere) in the function. We don't do globals here
100409467b48Spatrick // because they are often worse to put in place.
alwaysAvailable(Value * V)100509467b48Spatrick static bool alwaysAvailable(Value *V) {
100609467b48Spatrick return isa<Constant>(V) || isa<Argument>(V);
100709467b48Spatrick }
100809467b48Spatrick
100909467b48Spatrick // Create a PHIExpression from an array of {incoming edge, value} pairs. I is
101009467b48Spatrick // the original instruction we are creating a PHIExpression for (but may not be
101109467b48Spatrick // a phi node). We require, as an invariant, that all the PHIOperands in the
101209467b48Spatrick // same block are sorted the same way. sortPHIOps will sort them into a
101309467b48Spatrick // canonical order.
createPHIExpression(ArrayRef<ValPair> PHIOperands,const Instruction * I,BasicBlock * PHIBlock,bool & HasBackedge,bool & OriginalOpsConstant) const101409467b48Spatrick PHIExpression *NewGVN::createPHIExpression(ArrayRef<ValPair> PHIOperands,
101509467b48Spatrick const Instruction *I,
101609467b48Spatrick BasicBlock *PHIBlock,
101709467b48Spatrick bool &HasBackedge,
101809467b48Spatrick bool &OriginalOpsConstant) const {
101909467b48Spatrick unsigned NumOps = PHIOperands.size();
102009467b48Spatrick auto *E = new (ExpressionAllocator) PHIExpression(NumOps, PHIBlock);
102109467b48Spatrick
102209467b48Spatrick E->allocateOperands(ArgRecycler, ExpressionAllocator);
102309467b48Spatrick E->setType(PHIOperands.begin()->first->getType());
102409467b48Spatrick E->setOpcode(Instruction::PHI);
102509467b48Spatrick
102609467b48Spatrick // Filter out unreachable phi operands.
102709467b48Spatrick auto Filtered = make_filter_range(PHIOperands, [&](const ValPair &P) {
102809467b48Spatrick auto *BB = P.second;
102909467b48Spatrick if (auto *PHIOp = dyn_cast<PHINode>(I))
103009467b48Spatrick if (isCopyOfPHI(P.first, PHIOp))
103109467b48Spatrick return false;
103209467b48Spatrick if (!ReachableEdges.count({BB, PHIBlock}))
103309467b48Spatrick return false;
103409467b48Spatrick // Things in TOPClass are equivalent to everything.
103509467b48Spatrick if (ValueToClass.lookup(P.first) == TOPClass)
103609467b48Spatrick return false;
103709467b48Spatrick OriginalOpsConstant = OriginalOpsConstant && isa<Constant>(P.first);
103809467b48Spatrick HasBackedge = HasBackedge || isBackedge(BB, PHIBlock);
103909467b48Spatrick return lookupOperandLeader(P.first) != I;
104009467b48Spatrick });
104109467b48Spatrick std::transform(Filtered.begin(), Filtered.end(), op_inserter(E),
104209467b48Spatrick [&](const ValPair &P) -> Value * {
104309467b48Spatrick return lookupOperandLeader(P.first);
104409467b48Spatrick });
104509467b48Spatrick return E;
104609467b48Spatrick }
104709467b48Spatrick
104809467b48Spatrick // Set basic expression info (Arguments, type, opcode) for Expression
104909467b48Spatrick // E from Instruction I in block B.
setBasicExpressionInfo(Instruction * I,BasicExpression * E) const105009467b48Spatrick bool NewGVN::setBasicExpressionInfo(Instruction *I, BasicExpression *E) const {
105109467b48Spatrick bool AllConstant = true;
105209467b48Spatrick if (auto *GEP = dyn_cast<GetElementPtrInst>(I))
105309467b48Spatrick E->setType(GEP->getSourceElementType());
105409467b48Spatrick else
105509467b48Spatrick E->setType(I->getType());
105609467b48Spatrick E->setOpcode(I->getOpcode());
105709467b48Spatrick E->allocateOperands(ArgRecycler, ExpressionAllocator);
105809467b48Spatrick
105909467b48Spatrick // Transform the operand array into an operand leader array, and keep track of
106009467b48Spatrick // whether all members are constant.
106109467b48Spatrick std::transform(I->op_begin(), I->op_end(), op_inserter(E), [&](Value *O) {
106209467b48Spatrick auto Operand = lookupOperandLeader(O);
106309467b48Spatrick AllConstant = AllConstant && isa<Constant>(Operand);
106409467b48Spatrick return Operand;
106509467b48Spatrick });
106609467b48Spatrick
106709467b48Spatrick return AllConstant;
106809467b48Spatrick }
106909467b48Spatrick
createBinaryExpression(unsigned Opcode,Type * T,Value * Arg1,Value * Arg2,Instruction * I) const107009467b48Spatrick const Expression *NewGVN::createBinaryExpression(unsigned Opcode, Type *T,
107109467b48Spatrick Value *Arg1, Value *Arg2,
107209467b48Spatrick Instruction *I) const {
107309467b48Spatrick auto *E = new (ExpressionAllocator) BasicExpression(2);
1074*d415bd75Srobert // TODO: we need to remove context instruction after Value Tracking
1075*d415bd75Srobert // can run without context instruction
1076*d415bd75Srobert const SimplifyQuery Q = SQ.getWithInstruction(I);
107709467b48Spatrick
107809467b48Spatrick E->setType(T);
107909467b48Spatrick E->setOpcode(Opcode);
108009467b48Spatrick E->allocateOperands(ArgRecycler, ExpressionAllocator);
108109467b48Spatrick if (Instruction::isCommutative(Opcode)) {
108209467b48Spatrick // Ensure that commutative instructions that only differ by a permutation
108309467b48Spatrick // of their operands get the same value number by sorting the operand value
108409467b48Spatrick // numbers. Since all commutative instructions have two operands it is more
108509467b48Spatrick // efficient to sort by hand rather than using, say, std::sort.
108609467b48Spatrick if (shouldSwapOperands(Arg1, Arg2))
108709467b48Spatrick std::swap(Arg1, Arg2);
108809467b48Spatrick }
108909467b48Spatrick E->op_push_back(lookupOperandLeader(Arg1));
109009467b48Spatrick E->op_push_back(lookupOperandLeader(Arg2));
109109467b48Spatrick
1092*d415bd75Srobert Value *V = simplifyBinOp(Opcode, E->getOperand(0), E->getOperand(1), Q);
109373471bf0Spatrick if (auto Simplified = checkExprResults(E, I, V)) {
109473471bf0Spatrick addAdditionalUsers(Simplified, I);
109573471bf0Spatrick return Simplified.Expr;
109673471bf0Spatrick }
109709467b48Spatrick return E;
109809467b48Spatrick }
109909467b48Spatrick
110009467b48Spatrick // Take a Value returned by simplification of Expression E/Instruction
110109467b48Spatrick // I, and see if it resulted in a simpler expression. If so, return
110209467b48Spatrick // that expression.
checkExprResults(Expression * E,Instruction * I,Value * V) const110373471bf0Spatrick NewGVN::ExprResult NewGVN::checkExprResults(Expression *E, Instruction *I,
110409467b48Spatrick Value *V) const {
110509467b48Spatrick if (!V)
110673471bf0Spatrick return ExprResult::none();
110773471bf0Spatrick
110809467b48Spatrick if (auto *C = dyn_cast<Constant>(V)) {
110909467b48Spatrick if (I)
111009467b48Spatrick LLVM_DEBUG(dbgs() << "Simplified " << *I << " to "
111109467b48Spatrick << " constant " << *C << "\n");
111209467b48Spatrick NumGVNOpsSimplified++;
111309467b48Spatrick assert(isa<BasicExpression>(E) &&
111409467b48Spatrick "We should always have had a basic expression here");
111509467b48Spatrick deleteExpression(E);
111673471bf0Spatrick return ExprResult::some(createConstantExpression(C));
111709467b48Spatrick } else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
111809467b48Spatrick if (I)
111909467b48Spatrick LLVM_DEBUG(dbgs() << "Simplified " << *I << " to "
112009467b48Spatrick << " variable " << *V << "\n");
112109467b48Spatrick deleteExpression(E);
112273471bf0Spatrick return ExprResult::some(createVariableExpression(V));
112309467b48Spatrick }
112409467b48Spatrick
112509467b48Spatrick CongruenceClass *CC = ValueToClass.lookup(V);
112609467b48Spatrick if (CC) {
112709467b48Spatrick if (CC->getLeader() && CC->getLeader() != I) {
112873471bf0Spatrick return ExprResult::some(createVariableOrConstant(CC->getLeader()), V);
112909467b48Spatrick }
113009467b48Spatrick if (CC->getDefiningExpr()) {
113109467b48Spatrick if (I)
113209467b48Spatrick LLVM_DEBUG(dbgs() << "Simplified " << *I << " to "
113309467b48Spatrick << " expression " << *CC->getDefiningExpr() << "\n");
113409467b48Spatrick NumGVNOpsSimplified++;
113509467b48Spatrick deleteExpression(E);
113673471bf0Spatrick return ExprResult::some(CC->getDefiningExpr(), V);
113709467b48Spatrick }
113809467b48Spatrick }
113909467b48Spatrick
114073471bf0Spatrick return ExprResult::none();
114109467b48Spatrick }
114209467b48Spatrick
114309467b48Spatrick // Create a value expression from the instruction I, replacing operands with
114409467b48Spatrick // their leaders.
114509467b48Spatrick
createExpression(Instruction * I) const114673471bf0Spatrick NewGVN::ExprResult NewGVN::createExpression(Instruction *I) const {
114709467b48Spatrick auto *E = new (ExpressionAllocator) BasicExpression(I->getNumOperands());
1148*d415bd75Srobert // TODO: we need to remove context instruction after Value Tracking
1149*d415bd75Srobert // can run without context instruction
1150*d415bd75Srobert const SimplifyQuery Q = SQ.getWithInstruction(I);
115109467b48Spatrick
115209467b48Spatrick bool AllConstant = setBasicExpressionInfo(I, E);
115309467b48Spatrick
115409467b48Spatrick if (I->isCommutative()) {
115509467b48Spatrick // Ensure that commutative instructions that only differ by a permutation
115609467b48Spatrick // of their operands get the same value number by sorting the operand value
115709467b48Spatrick // numbers. Since all commutative instructions have two operands it is more
115809467b48Spatrick // efficient to sort by hand rather than using, say, std::sort.
115909467b48Spatrick assert(I->getNumOperands() == 2 && "Unsupported commutative instruction!");
116009467b48Spatrick if (shouldSwapOperands(E->getOperand(0), E->getOperand(1)))
116109467b48Spatrick E->swapOperands(0, 1);
116209467b48Spatrick }
116309467b48Spatrick // Perform simplification.
116409467b48Spatrick if (auto *CI = dyn_cast<CmpInst>(I)) {
116509467b48Spatrick // Sort the operand value numbers so x<y and y>x get the same value
116609467b48Spatrick // number.
116709467b48Spatrick CmpInst::Predicate Predicate = CI->getPredicate();
116809467b48Spatrick if (shouldSwapOperands(E->getOperand(0), E->getOperand(1))) {
116909467b48Spatrick E->swapOperands(0, 1);
117009467b48Spatrick Predicate = CmpInst::getSwappedPredicate(Predicate);
117109467b48Spatrick }
117209467b48Spatrick E->setOpcode((CI->getOpcode() << 8) | Predicate);
1173*d415bd75Srobert // TODO: 25% of our time is spent in simplifyCmpInst with pointer operands
117409467b48Spatrick assert(I->getOperand(0)->getType() == I->getOperand(1)->getType() &&
117509467b48Spatrick "Wrong types on cmp instruction");
117609467b48Spatrick assert((E->getOperand(0)->getType() == I->getOperand(0)->getType() &&
117709467b48Spatrick E->getOperand(1)->getType() == I->getOperand(1)->getType()));
117809467b48Spatrick Value *V =
1179*d415bd75Srobert simplifyCmpInst(Predicate, E->getOperand(0), E->getOperand(1), Q);
118073471bf0Spatrick if (auto Simplified = checkExprResults(E, I, V))
118173471bf0Spatrick return Simplified;
118209467b48Spatrick } else if (isa<SelectInst>(I)) {
118309467b48Spatrick if (isa<Constant>(E->getOperand(0)) ||
118409467b48Spatrick E->getOperand(1) == E->getOperand(2)) {
118509467b48Spatrick assert(E->getOperand(1)->getType() == I->getOperand(1)->getType() &&
118609467b48Spatrick E->getOperand(2)->getType() == I->getOperand(2)->getType());
1187*d415bd75Srobert Value *V = simplifySelectInst(E->getOperand(0), E->getOperand(1),
1188*d415bd75Srobert E->getOperand(2), Q);
118973471bf0Spatrick if (auto Simplified = checkExprResults(E, I, V))
119073471bf0Spatrick return Simplified;
119109467b48Spatrick }
119209467b48Spatrick } else if (I->isBinaryOp()) {
119309467b48Spatrick Value *V =
1194*d415bd75Srobert simplifyBinOp(E->getOpcode(), E->getOperand(0), E->getOperand(1), Q);
119573471bf0Spatrick if (auto Simplified = checkExprResults(E, I, V))
119673471bf0Spatrick return Simplified;
119709467b48Spatrick } else if (auto *CI = dyn_cast<CastInst>(I)) {
119809467b48Spatrick Value *V =
1199*d415bd75Srobert simplifyCastInst(CI->getOpcode(), E->getOperand(0), CI->getType(), Q);
120073471bf0Spatrick if (auto Simplified = checkExprResults(E, I, V))
120173471bf0Spatrick return Simplified;
1202*d415bd75Srobert } else if (auto *GEPI = dyn_cast<GetElementPtrInst>(I)) {
1203*d415bd75Srobert Value *V = simplifyGEPInst(GEPI->getSourceElementType(), *E->op_begin(),
1204*d415bd75Srobert ArrayRef(std::next(E->op_begin()), E->op_end()),
1205*d415bd75Srobert GEPI->isInBounds(), Q);
120673471bf0Spatrick if (auto Simplified = checkExprResults(E, I, V))
120773471bf0Spatrick return Simplified;
120809467b48Spatrick } else if (AllConstant) {
120909467b48Spatrick // We don't bother trying to simplify unless all of the operands
121009467b48Spatrick // were constant.
121109467b48Spatrick // TODO: There are a lot of Simplify*'s we could call here, if we
121209467b48Spatrick // wanted to. The original motivating case for this code was a
121309467b48Spatrick // zext i1 false to i8, which we don't have an interface to
121409467b48Spatrick // simplify (IE there is no SimplifyZExt).
121509467b48Spatrick
121609467b48Spatrick SmallVector<Constant *, 8> C;
121709467b48Spatrick for (Value *Arg : E->operands())
121809467b48Spatrick C.emplace_back(cast<Constant>(Arg));
121909467b48Spatrick
122009467b48Spatrick if (Value *V = ConstantFoldInstOperands(I, C, DL, TLI))
122173471bf0Spatrick if (auto Simplified = checkExprResults(E, I, V))
122273471bf0Spatrick return Simplified;
122309467b48Spatrick }
122473471bf0Spatrick return ExprResult::some(E);
122509467b48Spatrick }
122609467b48Spatrick
122709467b48Spatrick const AggregateValueExpression *
createAggregateValueExpression(Instruction * I) const122809467b48Spatrick NewGVN::createAggregateValueExpression(Instruction *I) const {
122909467b48Spatrick if (auto *II = dyn_cast<InsertValueInst>(I)) {
123009467b48Spatrick auto *E = new (ExpressionAllocator)
123109467b48Spatrick AggregateValueExpression(I->getNumOperands(), II->getNumIndices());
123209467b48Spatrick setBasicExpressionInfo(I, E);
123309467b48Spatrick E->allocateIntOperands(ExpressionAllocator);
123409467b48Spatrick std::copy(II->idx_begin(), II->idx_end(), int_op_inserter(E));
123509467b48Spatrick return E;
123609467b48Spatrick } else if (auto *EI = dyn_cast<ExtractValueInst>(I)) {
123709467b48Spatrick auto *E = new (ExpressionAllocator)
123809467b48Spatrick AggregateValueExpression(I->getNumOperands(), EI->getNumIndices());
123909467b48Spatrick setBasicExpressionInfo(EI, E);
124009467b48Spatrick E->allocateIntOperands(ExpressionAllocator);
124109467b48Spatrick std::copy(EI->idx_begin(), EI->idx_end(), int_op_inserter(E));
124209467b48Spatrick return E;
124309467b48Spatrick }
124409467b48Spatrick llvm_unreachable("Unhandled type of aggregate value operation");
124509467b48Spatrick }
124609467b48Spatrick
createDeadExpression() const124709467b48Spatrick const DeadExpression *NewGVN::createDeadExpression() const {
124809467b48Spatrick // DeadExpression has no arguments and all DeadExpression's are the same,
124909467b48Spatrick // so we only need one of them.
125009467b48Spatrick return SingletonDeadExpression;
125109467b48Spatrick }
125209467b48Spatrick
createVariableExpression(Value * V) const125309467b48Spatrick const VariableExpression *NewGVN::createVariableExpression(Value *V) const {
125409467b48Spatrick auto *E = new (ExpressionAllocator) VariableExpression(V);
125509467b48Spatrick E->setOpcode(V->getValueID());
125609467b48Spatrick return E;
125709467b48Spatrick }
125809467b48Spatrick
createVariableOrConstant(Value * V) const125909467b48Spatrick const Expression *NewGVN::createVariableOrConstant(Value *V) const {
126009467b48Spatrick if (auto *C = dyn_cast<Constant>(V))
126109467b48Spatrick return createConstantExpression(C);
126209467b48Spatrick return createVariableExpression(V);
126309467b48Spatrick }
126409467b48Spatrick
createConstantExpression(Constant * C) const126509467b48Spatrick const ConstantExpression *NewGVN::createConstantExpression(Constant *C) const {
126609467b48Spatrick auto *E = new (ExpressionAllocator) ConstantExpression(C);
126709467b48Spatrick E->setOpcode(C->getValueID());
126809467b48Spatrick return E;
126909467b48Spatrick }
127009467b48Spatrick
createUnknownExpression(Instruction * I) const127109467b48Spatrick const UnknownExpression *NewGVN::createUnknownExpression(Instruction *I) const {
127209467b48Spatrick auto *E = new (ExpressionAllocator) UnknownExpression(I);
127309467b48Spatrick E->setOpcode(I->getOpcode());
127409467b48Spatrick return E;
127509467b48Spatrick }
127609467b48Spatrick
127709467b48Spatrick const CallExpression *
createCallExpression(CallInst * CI,const MemoryAccess * MA) const127809467b48Spatrick NewGVN::createCallExpression(CallInst *CI, const MemoryAccess *MA) const {
127909467b48Spatrick // FIXME: Add operand bundles for calls.
128073471bf0Spatrick // FIXME: Allow commutative matching for intrinsics.
128109467b48Spatrick auto *E =
128209467b48Spatrick new (ExpressionAllocator) CallExpression(CI->getNumOperands(), CI, MA);
128309467b48Spatrick setBasicExpressionInfo(CI, E);
128409467b48Spatrick return E;
128509467b48Spatrick }
128609467b48Spatrick
128709467b48Spatrick // Return true if some equivalent of instruction Inst dominates instruction U.
someEquivalentDominates(const Instruction * Inst,const Instruction * U) const128809467b48Spatrick bool NewGVN::someEquivalentDominates(const Instruction *Inst,
128909467b48Spatrick const Instruction *U) const {
129009467b48Spatrick auto *CC = ValueToClass.lookup(Inst);
129109467b48Spatrick // This must be an instruction because we are only called from phi nodes
129209467b48Spatrick // in the case that the value it needs to check against is an instruction.
129309467b48Spatrick
129409467b48Spatrick // The most likely candidates for dominance are the leader and the next leader.
129509467b48Spatrick // The leader or nextleader will dominate in all cases where there is an
129609467b48Spatrick // equivalent that is higher up in the dom tree.
129709467b48Spatrick // We can't *only* check them, however, because the
129809467b48Spatrick // dominator tree could have an infinite number of non-dominating siblings
129909467b48Spatrick // with instructions that are in the right congruence class.
130009467b48Spatrick // A
130109467b48Spatrick // B C D E F G
130209467b48Spatrick // |
130309467b48Spatrick // H
130409467b48Spatrick // Instruction U could be in H, with equivalents in every other sibling.
130509467b48Spatrick // Depending on the rpo order picked, the leader could be the equivalent in
130609467b48Spatrick // any of these siblings.
130709467b48Spatrick if (!CC)
130809467b48Spatrick return false;
130909467b48Spatrick if (alwaysAvailable(CC->getLeader()))
131009467b48Spatrick return true;
131109467b48Spatrick if (DT->dominates(cast<Instruction>(CC->getLeader()), U))
131209467b48Spatrick return true;
131309467b48Spatrick if (CC->getNextLeader().first &&
131409467b48Spatrick DT->dominates(cast<Instruction>(CC->getNextLeader().first), U))
131509467b48Spatrick return true;
131609467b48Spatrick return llvm::any_of(*CC, [&](const Value *Member) {
131709467b48Spatrick return Member != CC->getLeader() &&
131809467b48Spatrick DT->dominates(cast<Instruction>(Member), U);
131909467b48Spatrick });
132009467b48Spatrick }
132109467b48Spatrick
132209467b48Spatrick // See if we have a congruence class and leader for this operand, and if so,
132309467b48Spatrick // return it. Otherwise, return the operand itself.
lookupOperandLeader(Value * V) const132409467b48Spatrick Value *NewGVN::lookupOperandLeader(Value *V) const {
132509467b48Spatrick CongruenceClass *CC = ValueToClass.lookup(V);
132609467b48Spatrick if (CC) {
1327*d415bd75Srobert // Everything in TOP is represented by poison, as it can be any value.
132809467b48Spatrick // We do have to make sure we get the type right though, so we can't set the
1329*d415bd75Srobert // RepLeader to poison.
133009467b48Spatrick if (CC == TOPClass)
1331*d415bd75Srobert return PoisonValue::get(V->getType());
133209467b48Spatrick return CC->getStoredValue() ? CC->getStoredValue() : CC->getLeader();
133309467b48Spatrick }
133409467b48Spatrick
133509467b48Spatrick return V;
133609467b48Spatrick }
133709467b48Spatrick
lookupMemoryLeader(const MemoryAccess * MA) const133809467b48Spatrick const MemoryAccess *NewGVN::lookupMemoryLeader(const MemoryAccess *MA) const {
133909467b48Spatrick auto *CC = getMemoryClass(MA);
134009467b48Spatrick assert(CC->getMemoryLeader() &&
134109467b48Spatrick "Every MemoryAccess should be mapped to a congruence class with a "
134209467b48Spatrick "representative memory access");
134309467b48Spatrick return CC->getMemoryLeader();
134409467b48Spatrick }
134509467b48Spatrick
134609467b48Spatrick // Return true if the MemoryAccess is really equivalent to everything. This is
134709467b48Spatrick // equivalent to the lattice value "TOP" in most lattices. This is the initial
134809467b48Spatrick // state of all MemoryAccesses.
isMemoryAccessTOP(const MemoryAccess * MA) const134909467b48Spatrick bool NewGVN::isMemoryAccessTOP(const MemoryAccess *MA) const {
135009467b48Spatrick return getMemoryClass(MA) == TOPClass;
135109467b48Spatrick }
135209467b48Spatrick
createLoadExpression(Type * LoadType,Value * PointerOp,LoadInst * LI,const MemoryAccess * MA) const135309467b48Spatrick LoadExpression *NewGVN::createLoadExpression(Type *LoadType, Value *PointerOp,
135409467b48Spatrick LoadInst *LI,
135509467b48Spatrick const MemoryAccess *MA) const {
135609467b48Spatrick auto *E =
135709467b48Spatrick new (ExpressionAllocator) LoadExpression(1, LI, lookupMemoryLeader(MA));
135809467b48Spatrick E->allocateOperands(ArgRecycler, ExpressionAllocator);
135909467b48Spatrick E->setType(LoadType);
136009467b48Spatrick
136109467b48Spatrick // Give store and loads same opcode so they value number together.
136209467b48Spatrick E->setOpcode(0);
136309467b48Spatrick E->op_push_back(PointerOp);
136409467b48Spatrick
136509467b48Spatrick // TODO: Value number heap versions. We may be able to discover
136609467b48Spatrick // things alias analysis can't on it's own (IE that a store and a
136709467b48Spatrick // load have the same value, and thus, it isn't clobbering the load).
136809467b48Spatrick return E;
136909467b48Spatrick }
137009467b48Spatrick
137109467b48Spatrick const StoreExpression *
createStoreExpression(StoreInst * SI,const MemoryAccess * MA) const137209467b48Spatrick NewGVN::createStoreExpression(StoreInst *SI, const MemoryAccess *MA) const {
137309467b48Spatrick auto *StoredValueLeader = lookupOperandLeader(SI->getValueOperand());
137409467b48Spatrick auto *E = new (ExpressionAllocator)
137509467b48Spatrick StoreExpression(SI->getNumOperands(), SI, StoredValueLeader, MA);
137609467b48Spatrick E->allocateOperands(ArgRecycler, ExpressionAllocator);
137709467b48Spatrick E->setType(SI->getValueOperand()->getType());
137809467b48Spatrick
137909467b48Spatrick // Give store and loads same opcode so they value number together.
138009467b48Spatrick E->setOpcode(0);
138109467b48Spatrick E->op_push_back(lookupOperandLeader(SI->getPointerOperand()));
138209467b48Spatrick
138309467b48Spatrick // TODO: Value number heap versions. We may be able to discover
138409467b48Spatrick // things alias analysis can't on it's own (IE that a store and a
138509467b48Spatrick // load have the same value, and thus, it isn't clobbering the load).
138609467b48Spatrick return E;
138709467b48Spatrick }
138809467b48Spatrick
performSymbolicStoreEvaluation(Instruction * I) const138909467b48Spatrick const Expression *NewGVN::performSymbolicStoreEvaluation(Instruction *I) const {
139009467b48Spatrick // Unlike loads, we never try to eliminate stores, so we do not check if they
139109467b48Spatrick // are simple and avoid value numbering them.
139209467b48Spatrick auto *SI = cast<StoreInst>(I);
139309467b48Spatrick auto *StoreAccess = getMemoryAccess(SI);
139409467b48Spatrick // Get the expression, if any, for the RHS of the MemoryDef.
139509467b48Spatrick const MemoryAccess *StoreRHS = StoreAccess->getDefiningAccess();
139609467b48Spatrick if (EnableStoreRefinement)
139709467b48Spatrick StoreRHS = MSSAWalker->getClobberingMemoryAccess(StoreAccess);
139809467b48Spatrick // If we bypassed the use-def chains, make sure we add a use.
139909467b48Spatrick StoreRHS = lookupMemoryLeader(StoreRHS);
140009467b48Spatrick if (StoreRHS != StoreAccess->getDefiningAccess())
140109467b48Spatrick addMemoryUsers(StoreRHS, StoreAccess);
140209467b48Spatrick // If we are defined by ourselves, use the live on entry def.
140309467b48Spatrick if (StoreRHS == StoreAccess)
140409467b48Spatrick StoreRHS = MSSA->getLiveOnEntryDef();
140509467b48Spatrick
140609467b48Spatrick if (SI->isSimple()) {
140709467b48Spatrick // See if we are defined by a previous store expression, it already has a
140809467b48Spatrick // value, and it's the same value as our current store. FIXME: Right now, we
140909467b48Spatrick // only do this for simple stores, we should expand to cover memcpys, etc.
141009467b48Spatrick const auto *LastStore = createStoreExpression(SI, StoreRHS);
141109467b48Spatrick const auto *LastCC = ExpressionToClass.lookup(LastStore);
141209467b48Spatrick // We really want to check whether the expression we matched was a store. No
141309467b48Spatrick // easy way to do that. However, we can check that the class we found has a
141409467b48Spatrick // store, which, assuming the value numbering state is not corrupt, is
141509467b48Spatrick // sufficient, because we must also be equivalent to that store's expression
141609467b48Spatrick // for it to be in the same class as the load.
141709467b48Spatrick if (LastCC && LastCC->getStoredValue() == LastStore->getStoredValue())
141809467b48Spatrick return LastStore;
141909467b48Spatrick // Also check if our value operand is defined by a load of the same memory
142009467b48Spatrick // location, and the memory state is the same as it was then (otherwise, it
142109467b48Spatrick // could have been overwritten later. See test32 in
142209467b48Spatrick // transforms/DeadStoreElimination/simple.ll).
142309467b48Spatrick if (auto *LI = dyn_cast<LoadInst>(LastStore->getStoredValue()))
142409467b48Spatrick if ((lookupOperandLeader(LI->getPointerOperand()) ==
142509467b48Spatrick LastStore->getOperand(0)) &&
142609467b48Spatrick (lookupMemoryLeader(getMemoryAccess(LI)->getDefiningAccess()) ==
142709467b48Spatrick StoreRHS))
142809467b48Spatrick return LastStore;
142909467b48Spatrick deleteExpression(LastStore);
143009467b48Spatrick }
143109467b48Spatrick
143209467b48Spatrick // If the store is not equivalent to anything, value number it as a store that
143309467b48Spatrick // produces a unique memory state (instead of using it's MemoryUse, we use
143409467b48Spatrick // it's MemoryDef).
143509467b48Spatrick return createStoreExpression(SI, StoreAccess);
143609467b48Spatrick }
143709467b48Spatrick
143809467b48Spatrick // See if we can extract the value of a loaded pointer from a load, a store, or
143909467b48Spatrick // a memory instruction.
144009467b48Spatrick const Expression *
performSymbolicLoadCoercion(Type * LoadType,Value * LoadPtr,LoadInst * LI,Instruction * DepInst,MemoryAccess * DefiningAccess) const144109467b48Spatrick NewGVN::performSymbolicLoadCoercion(Type *LoadType, Value *LoadPtr,
144209467b48Spatrick LoadInst *LI, Instruction *DepInst,
144309467b48Spatrick MemoryAccess *DefiningAccess) const {
144409467b48Spatrick assert((!LI || LI->isSimple()) && "Not a simple load");
144509467b48Spatrick if (auto *DepSI = dyn_cast<StoreInst>(DepInst)) {
144609467b48Spatrick // Can't forward from non-atomic to atomic without violating memory model.
144709467b48Spatrick // Also don't need to coerce if they are the same type, we will just
144809467b48Spatrick // propagate.
144909467b48Spatrick if (LI->isAtomic() > DepSI->isAtomic() ||
145009467b48Spatrick LoadType == DepSI->getValueOperand()->getType())
145109467b48Spatrick return nullptr;
145209467b48Spatrick int Offset = analyzeLoadFromClobberingStore(LoadType, LoadPtr, DepSI, DL);
145309467b48Spatrick if (Offset >= 0) {
145409467b48Spatrick if (auto *C = dyn_cast<Constant>(
145509467b48Spatrick lookupOperandLeader(DepSI->getValueOperand()))) {
1456*d415bd75Srobert if (Constant *Res =
1457*d415bd75Srobert getConstantStoreValueForLoad(C, Offset, LoadType, DL)) {
145809467b48Spatrick LLVM_DEBUG(dbgs() << "Coercing load from store " << *DepSI
1459*d415bd75Srobert << " to constant " << *Res << "\n");
1460*d415bd75Srobert return createConstantExpression(Res);
1461*d415bd75Srobert }
146209467b48Spatrick }
146309467b48Spatrick }
146409467b48Spatrick } else if (auto *DepLI = dyn_cast<LoadInst>(DepInst)) {
146509467b48Spatrick // Can't forward from non-atomic to atomic without violating memory model.
146609467b48Spatrick if (LI->isAtomic() > DepLI->isAtomic())
146709467b48Spatrick return nullptr;
146809467b48Spatrick int Offset = analyzeLoadFromClobberingLoad(LoadType, LoadPtr, DepLI, DL);
146909467b48Spatrick if (Offset >= 0) {
147009467b48Spatrick // We can coerce a constant load into a load.
147109467b48Spatrick if (auto *C = dyn_cast<Constant>(lookupOperandLeader(DepLI)))
147209467b48Spatrick if (auto *PossibleConstant =
147309467b48Spatrick getConstantLoadValueForLoad(C, Offset, LoadType, DL)) {
147409467b48Spatrick LLVM_DEBUG(dbgs() << "Coercing load from load " << *LI
147509467b48Spatrick << " to constant " << *PossibleConstant << "\n");
147609467b48Spatrick return createConstantExpression(PossibleConstant);
147709467b48Spatrick }
147809467b48Spatrick }
147909467b48Spatrick } else if (auto *DepMI = dyn_cast<MemIntrinsic>(DepInst)) {
148009467b48Spatrick int Offset = analyzeLoadFromClobberingMemInst(LoadType, LoadPtr, DepMI, DL);
148109467b48Spatrick if (Offset >= 0) {
148209467b48Spatrick if (auto *PossibleConstant =
148309467b48Spatrick getConstantMemInstValueForLoad(DepMI, Offset, LoadType, DL)) {
148409467b48Spatrick LLVM_DEBUG(dbgs() << "Coercing load from meminst " << *DepMI
148509467b48Spatrick << " to constant " << *PossibleConstant << "\n");
148609467b48Spatrick return createConstantExpression(PossibleConstant);
148709467b48Spatrick }
148809467b48Spatrick }
148909467b48Spatrick }
149009467b48Spatrick
149109467b48Spatrick // All of the below are only true if the loaded pointer is produced
149209467b48Spatrick // by the dependent instruction.
149309467b48Spatrick if (LoadPtr != lookupOperandLeader(DepInst) &&
149409467b48Spatrick !AA->isMustAlias(LoadPtr, DepInst))
149509467b48Spatrick return nullptr;
149609467b48Spatrick // If this load really doesn't depend on anything, then we must be loading an
149709467b48Spatrick // undef value. This can happen when loading for a fresh allocation with no
149809467b48Spatrick // intervening stores, for example. Note that this is only true in the case
149909467b48Spatrick // that the result of the allocation is pointer equal to the load ptr.
1500*d415bd75Srobert if (isa<AllocaInst>(DepInst)) {
150109467b48Spatrick return createConstantExpression(UndefValue::get(LoadType));
150209467b48Spatrick }
150309467b48Spatrick // If this load occurs either right after a lifetime begin,
150409467b48Spatrick // then the loaded value is undefined.
150509467b48Spatrick else if (auto *II = dyn_cast<IntrinsicInst>(DepInst)) {
150609467b48Spatrick if (II->getIntrinsicID() == Intrinsic::lifetime_start)
150709467b48Spatrick return createConstantExpression(UndefValue::get(LoadType));
1508*d415bd75Srobert } else if (auto *InitVal =
1509*d415bd75Srobert getInitialValueOfAllocation(DepInst, TLI, LoadType))
1510*d415bd75Srobert return createConstantExpression(InitVal);
151109467b48Spatrick
151209467b48Spatrick return nullptr;
151309467b48Spatrick }
151409467b48Spatrick
performSymbolicLoadEvaluation(Instruction * I) const151509467b48Spatrick const Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I) const {
151609467b48Spatrick auto *LI = cast<LoadInst>(I);
151709467b48Spatrick
151809467b48Spatrick // We can eliminate in favor of non-simple loads, but we won't be able to
151909467b48Spatrick // eliminate the loads themselves.
152009467b48Spatrick if (!LI->isSimple())
152109467b48Spatrick return nullptr;
152209467b48Spatrick
152309467b48Spatrick Value *LoadAddressLeader = lookupOperandLeader(LI->getPointerOperand());
1524*d415bd75Srobert // Load of undef is UB.
152509467b48Spatrick if (isa<UndefValue>(LoadAddressLeader))
1526*d415bd75Srobert return createConstantExpression(PoisonValue::get(LI->getType()));
152709467b48Spatrick MemoryAccess *OriginalAccess = getMemoryAccess(I);
152809467b48Spatrick MemoryAccess *DefiningAccess =
152909467b48Spatrick MSSAWalker->getClobberingMemoryAccess(OriginalAccess);
153009467b48Spatrick
153109467b48Spatrick if (!MSSA->isLiveOnEntryDef(DefiningAccess)) {
153209467b48Spatrick if (auto *MD = dyn_cast<MemoryDef>(DefiningAccess)) {
153309467b48Spatrick Instruction *DefiningInst = MD->getMemoryInst();
1534*d415bd75Srobert // If the defining instruction is not reachable, replace with poison.
153509467b48Spatrick if (!ReachableBlocks.count(DefiningInst->getParent()))
1536*d415bd75Srobert return createConstantExpression(PoisonValue::get(LI->getType()));
153709467b48Spatrick // This will handle stores and memory insts. We only do if it the
153809467b48Spatrick // defining access has a different type, or it is a pointer produced by
153909467b48Spatrick // certain memory operations that cause the memory to have a fixed value
154009467b48Spatrick // (IE things like calloc).
154109467b48Spatrick if (const auto *CoercionResult =
154209467b48Spatrick performSymbolicLoadCoercion(LI->getType(), LoadAddressLeader, LI,
154309467b48Spatrick DefiningInst, DefiningAccess))
154409467b48Spatrick return CoercionResult;
154509467b48Spatrick }
154609467b48Spatrick }
154709467b48Spatrick
154809467b48Spatrick const auto *LE = createLoadExpression(LI->getType(), LoadAddressLeader, LI,
154909467b48Spatrick DefiningAccess);
155009467b48Spatrick // If our MemoryLeader is not our defining access, add a use to the
155109467b48Spatrick // MemoryLeader, so that we get reprocessed when it changes.
155209467b48Spatrick if (LE->getMemoryLeader() != DefiningAccess)
155309467b48Spatrick addMemoryUsers(LE->getMemoryLeader(), OriginalAccess);
155409467b48Spatrick return LE;
155509467b48Spatrick }
155609467b48Spatrick
155773471bf0Spatrick NewGVN::ExprResult
performSymbolicPredicateInfoEvaluation(IntrinsicInst * I) const1558*d415bd75Srobert NewGVN::performSymbolicPredicateInfoEvaluation(IntrinsicInst *I) const {
155909467b48Spatrick auto *PI = PredInfo->getPredicateInfoFor(I);
156009467b48Spatrick if (!PI)
156173471bf0Spatrick return ExprResult::none();
156209467b48Spatrick
156309467b48Spatrick LLVM_DEBUG(dbgs() << "Found predicate info from instruction !\n");
156409467b48Spatrick
1565*d415bd75Srobert const std::optional<PredicateConstraint> &Constraint = PI->getConstraint();
156673471bf0Spatrick if (!Constraint)
156773471bf0Spatrick return ExprResult::none();
156809467b48Spatrick
156973471bf0Spatrick CmpInst::Predicate Predicate = Constraint->Predicate;
157073471bf0Spatrick Value *CmpOp0 = I->getOperand(0);
157173471bf0Spatrick Value *CmpOp1 = Constraint->OtherOp;
157209467b48Spatrick
157373471bf0Spatrick Value *FirstOp = lookupOperandLeader(CmpOp0);
157473471bf0Spatrick Value *SecondOp = lookupOperandLeader(CmpOp1);
157573471bf0Spatrick Value *AdditionallyUsedValue = CmpOp0;
157609467b48Spatrick
157709467b48Spatrick // Sort the ops.
1578*d415bd75Srobert if (shouldSwapOperandsForIntrinsic(FirstOp, SecondOp, I)) {
157909467b48Spatrick std::swap(FirstOp, SecondOp);
158073471bf0Spatrick Predicate = CmpInst::getSwappedPredicate(Predicate);
158173471bf0Spatrick AdditionallyUsedValue = CmpOp1;
158209467b48Spatrick }
158309467b48Spatrick
158473471bf0Spatrick if (Predicate == CmpInst::ICMP_EQ)
158573471bf0Spatrick return ExprResult::some(createVariableOrConstant(FirstOp),
158673471bf0Spatrick AdditionallyUsedValue, PI);
158773471bf0Spatrick
158809467b48Spatrick // Handle the special case of floating point.
158973471bf0Spatrick if (Predicate == CmpInst::FCMP_OEQ && isa<ConstantFP>(FirstOp) &&
159073471bf0Spatrick !cast<ConstantFP>(FirstOp)->isZero())
159173471bf0Spatrick return ExprResult::some(createConstantExpression(cast<Constant>(FirstOp)),
159273471bf0Spatrick AdditionallyUsedValue, PI);
159373471bf0Spatrick
159473471bf0Spatrick return ExprResult::none();
159509467b48Spatrick }
159609467b48Spatrick
159709467b48Spatrick // Evaluate read only and pure calls, and create an expression result.
performSymbolicCallEvaluation(Instruction * I) const159873471bf0Spatrick NewGVN::ExprResult NewGVN::performSymbolicCallEvaluation(Instruction *I) const {
159909467b48Spatrick auto *CI = cast<CallInst>(I);
160009467b48Spatrick if (auto *II = dyn_cast<IntrinsicInst>(I)) {
160109467b48Spatrick // Intrinsics with the returned attribute are copies of arguments.
160209467b48Spatrick if (auto *ReturnedValue = II->getReturnedArgOperand()) {
160309467b48Spatrick if (II->getIntrinsicID() == Intrinsic::ssa_copy)
1604*d415bd75Srobert if (auto Res = performSymbolicPredicateInfoEvaluation(II))
160573471bf0Spatrick return Res;
160673471bf0Spatrick return ExprResult::some(createVariableOrConstant(ReturnedValue));
160709467b48Spatrick }
160809467b48Spatrick }
1609*d415bd75Srobert
1610*d415bd75Srobert // FIXME: Currently the calls which may access the thread id may
1611*d415bd75Srobert // be considered as not accessing the memory. But this is
1612*d415bd75Srobert // problematic for coroutines, since coroutines may resume in a
1613*d415bd75Srobert // different thread. So we disable the optimization here for the
1614*d415bd75Srobert // correctness. However, it may block many other correct
1615*d415bd75Srobert // optimizations. Revert this one when we detect the memory
1616*d415bd75Srobert // accessing kind more precisely.
1617*d415bd75Srobert if (CI->getFunction()->isPresplitCoroutine())
1618*d415bd75Srobert return ExprResult::none();
1619*d415bd75Srobert
162009467b48Spatrick if (AA->doesNotAccessMemory(CI)) {
162173471bf0Spatrick return ExprResult::some(
162273471bf0Spatrick createCallExpression(CI, TOPClass->getMemoryLeader()));
162309467b48Spatrick } else if (AA->onlyReadsMemory(CI)) {
162409467b48Spatrick if (auto *MA = MSSA->getMemoryAccess(CI)) {
162509467b48Spatrick auto *DefiningAccess = MSSAWalker->getClobberingMemoryAccess(MA);
162673471bf0Spatrick return ExprResult::some(createCallExpression(CI, DefiningAccess));
162709467b48Spatrick } else // MSSA determined that CI does not access memory.
162873471bf0Spatrick return ExprResult::some(
162973471bf0Spatrick createCallExpression(CI, TOPClass->getMemoryLeader()));
163009467b48Spatrick }
163173471bf0Spatrick return ExprResult::none();
163209467b48Spatrick }
163309467b48Spatrick
163409467b48Spatrick // Retrieve the memory class for a given MemoryAccess.
getMemoryClass(const MemoryAccess * MA) const163509467b48Spatrick CongruenceClass *NewGVN::getMemoryClass(const MemoryAccess *MA) const {
163609467b48Spatrick auto *Result = MemoryAccessToClass.lookup(MA);
163709467b48Spatrick assert(Result && "Should have found memory class");
163809467b48Spatrick return Result;
163909467b48Spatrick }
164009467b48Spatrick
164109467b48Spatrick // Update the MemoryAccess equivalence table to say that From is equal to To,
164209467b48Spatrick // and return true if this is different from what already existed in the table.
setMemoryClass(const MemoryAccess * From,CongruenceClass * NewClass)164309467b48Spatrick bool NewGVN::setMemoryClass(const MemoryAccess *From,
164409467b48Spatrick CongruenceClass *NewClass) {
164509467b48Spatrick assert(NewClass &&
164609467b48Spatrick "Every MemoryAccess should be getting mapped to a non-null class");
164709467b48Spatrick LLVM_DEBUG(dbgs() << "Setting " << *From);
164809467b48Spatrick LLVM_DEBUG(dbgs() << " equivalent to congruence class ");
164909467b48Spatrick LLVM_DEBUG(dbgs() << NewClass->getID()
165009467b48Spatrick << " with current MemoryAccess leader ");
165109467b48Spatrick LLVM_DEBUG(dbgs() << *NewClass->getMemoryLeader() << "\n");
165209467b48Spatrick
165309467b48Spatrick auto LookupResult = MemoryAccessToClass.find(From);
165409467b48Spatrick bool Changed = false;
165509467b48Spatrick // If it's already in the table, see if the value changed.
165609467b48Spatrick if (LookupResult != MemoryAccessToClass.end()) {
165709467b48Spatrick auto *OldClass = LookupResult->second;
165809467b48Spatrick if (OldClass != NewClass) {
165909467b48Spatrick // If this is a phi, we have to handle memory member updates.
166009467b48Spatrick if (auto *MP = dyn_cast<MemoryPhi>(From)) {
166109467b48Spatrick OldClass->memory_erase(MP);
166209467b48Spatrick NewClass->memory_insert(MP);
166309467b48Spatrick // This may have killed the class if it had no non-memory members
166409467b48Spatrick if (OldClass->getMemoryLeader() == From) {
166509467b48Spatrick if (OldClass->definesNoMemory()) {
166609467b48Spatrick OldClass->setMemoryLeader(nullptr);
166709467b48Spatrick } else {
166809467b48Spatrick OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
166909467b48Spatrick LLVM_DEBUG(dbgs() << "Memory class leader change for class "
167009467b48Spatrick << OldClass->getID() << " to "
167109467b48Spatrick << *OldClass->getMemoryLeader()
167209467b48Spatrick << " due to removal of a memory member " << *From
167309467b48Spatrick << "\n");
167409467b48Spatrick markMemoryLeaderChangeTouched(OldClass);
167509467b48Spatrick }
167609467b48Spatrick }
167709467b48Spatrick }
167809467b48Spatrick // It wasn't equivalent before, and now it is.
167909467b48Spatrick LookupResult->second = NewClass;
168009467b48Spatrick Changed = true;
168109467b48Spatrick }
168209467b48Spatrick }
168309467b48Spatrick
168409467b48Spatrick return Changed;
168509467b48Spatrick }
168609467b48Spatrick
168709467b48Spatrick // Determine if a instruction is cycle-free. That means the values in the
168809467b48Spatrick // instruction don't depend on any expressions that can change value as a result
168909467b48Spatrick // of the instruction. For example, a non-cycle free instruction would be v =
169009467b48Spatrick // phi(0, v+1).
isCycleFree(const Instruction * I) const169109467b48Spatrick bool NewGVN::isCycleFree(const Instruction *I) const {
169209467b48Spatrick // In order to compute cycle-freeness, we do SCC finding on the instruction,
169309467b48Spatrick // and see what kind of SCC it ends up in. If it is a singleton, it is
169409467b48Spatrick // cycle-free. If it is not in a singleton, it is only cycle free if the
169509467b48Spatrick // other members are all phi nodes (as they do not compute anything, they are
169609467b48Spatrick // copies).
169709467b48Spatrick auto ICS = InstCycleState.lookup(I);
169809467b48Spatrick if (ICS == ICS_Unknown) {
169909467b48Spatrick SCCFinder.Start(I);
170009467b48Spatrick auto &SCC = SCCFinder.getComponentFor(I);
170109467b48Spatrick // It's cycle free if it's size 1 or the SCC is *only* phi nodes.
170209467b48Spatrick if (SCC.size() == 1)
170309467b48Spatrick InstCycleState.insert({I, ICS_CycleFree});
170409467b48Spatrick else {
170509467b48Spatrick bool AllPhis = llvm::all_of(SCC, [](const Value *V) {
170609467b48Spatrick return isa<PHINode>(V) || isCopyOfAPHI(V);
170709467b48Spatrick });
170809467b48Spatrick ICS = AllPhis ? ICS_CycleFree : ICS_Cycle;
1709*d415bd75Srobert for (const auto *Member : SCC)
171009467b48Spatrick if (auto *MemberPhi = dyn_cast<PHINode>(Member))
171109467b48Spatrick InstCycleState.insert({MemberPhi, ICS});
171209467b48Spatrick }
171309467b48Spatrick }
171409467b48Spatrick if (ICS == ICS_Cycle)
171509467b48Spatrick return false;
171609467b48Spatrick return true;
171709467b48Spatrick }
171809467b48Spatrick
171909467b48Spatrick // Evaluate PHI nodes symbolically and create an expression result.
172009467b48Spatrick const Expression *
performSymbolicPHIEvaluation(ArrayRef<ValPair> PHIOps,Instruction * I,BasicBlock * PHIBlock) const172109467b48Spatrick NewGVN::performSymbolicPHIEvaluation(ArrayRef<ValPair> PHIOps,
172209467b48Spatrick Instruction *I,
172309467b48Spatrick BasicBlock *PHIBlock) const {
172409467b48Spatrick // True if one of the incoming phi edges is a backedge.
172509467b48Spatrick bool HasBackedge = false;
172609467b48Spatrick // All constant tracks the state of whether all the *original* phi operands
172709467b48Spatrick // This is really shorthand for "this phi cannot cycle due to forward
172809467b48Spatrick // change in value of the phi is guaranteed not to later change the value of
172909467b48Spatrick // the phi. IE it can't be v = phi(undef, v+1)
173009467b48Spatrick bool OriginalOpsConstant = true;
173109467b48Spatrick auto *E = cast<PHIExpression>(createPHIExpression(
173209467b48Spatrick PHIOps, I, PHIBlock, HasBackedge, OriginalOpsConstant));
173309467b48Spatrick // We match the semantics of SimplifyPhiNode from InstructionSimplify here.
173409467b48Spatrick // See if all arguments are the same.
173509467b48Spatrick // We track if any were undef because they need special handling.
1736*d415bd75Srobert bool HasUndef = false, HasPoison = false;
173709467b48Spatrick auto Filtered = make_filter_range(E->operands(), [&](Value *Arg) {
1738*d415bd75Srobert if (isa<PoisonValue>(Arg)) {
1739*d415bd75Srobert HasPoison = true;
1740*d415bd75Srobert return false;
1741*d415bd75Srobert }
174209467b48Spatrick if (isa<UndefValue>(Arg)) {
174309467b48Spatrick HasUndef = true;
174409467b48Spatrick return false;
174509467b48Spatrick }
174609467b48Spatrick return true;
174709467b48Spatrick });
174809467b48Spatrick // If we are left with no operands, it's dead.
174909467b48Spatrick if (Filtered.empty()) {
1750*d415bd75Srobert // If it has undef or poison at this point, it means there are no-non-undef
1751*d415bd75Srobert // arguments, and thus, the value of the phi node must be undef.
175209467b48Spatrick if (HasUndef) {
175309467b48Spatrick LLVM_DEBUG(
175409467b48Spatrick dbgs() << "PHI Node " << *I
175509467b48Spatrick << " has no non-undef arguments, valuing it as undef\n");
175609467b48Spatrick return createConstantExpression(UndefValue::get(I->getType()));
175709467b48Spatrick }
1758*d415bd75Srobert if (HasPoison) {
1759*d415bd75Srobert LLVM_DEBUG(
1760*d415bd75Srobert dbgs() << "PHI Node " << *I
1761*d415bd75Srobert << " has no non-poison arguments, valuing it as poison\n");
1762*d415bd75Srobert return createConstantExpression(PoisonValue::get(I->getType()));
1763*d415bd75Srobert }
176409467b48Spatrick
176509467b48Spatrick LLVM_DEBUG(dbgs() << "No arguments of PHI node " << *I << " are live\n");
176609467b48Spatrick deleteExpression(E);
176709467b48Spatrick return createDeadExpression();
176809467b48Spatrick }
176909467b48Spatrick Value *AllSameValue = *(Filtered.begin());
177009467b48Spatrick ++Filtered.begin();
177109467b48Spatrick // Can't use std::equal here, sadly, because filter.begin moves.
177209467b48Spatrick if (llvm::all_of(Filtered, [&](Value *Arg) { return Arg == AllSameValue; })) {
1773*d415bd75Srobert // Can't fold phi(undef, X) -> X unless X can't be poison (thus X is undef
1774*d415bd75Srobert // in the worst case).
1775*d415bd75Srobert if (HasUndef && !isGuaranteedNotToBePoison(AllSameValue, AC, nullptr, DT))
1776*d415bd75Srobert return E;
1777*d415bd75Srobert
177809467b48Spatrick // In LLVM's non-standard representation of phi nodes, it's possible to have
177909467b48Spatrick // phi nodes with cycles (IE dependent on other phis that are .... dependent
178009467b48Spatrick // on the original phi node), especially in weird CFG's where some arguments
178109467b48Spatrick // are unreachable, or uninitialized along certain paths. This can cause
178209467b48Spatrick // infinite loops during evaluation. We work around this by not trying to
178309467b48Spatrick // really evaluate them independently, but instead using a variable
178409467b48Spatrick // expression to say if one is equivalent to the other.
1785*d415bd75Srobert // We also special case undef/poison, so that if we have an undef, we can't
1786*d415bd75Srobert // use the common value unless it dominates the phi block.
1787*d415bd75Srobert if (HasPoison || HasUndef) {
178809467b48Spatrick // If we have undef and at least one other value, this is really a
178909467b48Spatrick // multivalued phi, and we need to know if it's cycle free in order to
179009467b48Spatrick // evaluate whether we can ignore the undef. The other parts of this are
179109467b48Spatrick // just shortcuts. If there is no backedge, or all operands are
179209467b48Spatrick // constants, it also must be cycle free.
179309467b48Spatrick if (HasBackedge && !OriginalOpsConstant &&
179409467b48Spatrick !isa<UndefValue>(AllSameValue) && !isCycleFree(I))
179509467b48Spatrick return E;
179609467b48Spatrick
179709467b48Spatrick // Only have to check for instructions
179809467b48Spatrick if (auto *AllSameInst = dyn_cast<Instruction>(AllSameValue))
179909467b48Spatrick if (!someEquivalentDominates(AllSameInst, I))
180009467b48Spatrick return E;
180109467b48Spatrick }
180209467b48Spatrick // Can't simplify to something that comes later in the iteration.
180309467b48Spatrick // Otherwise, when and if it changes congruence class, we will never catch
180409467b48Spatrick // up. We will always be a class behind it.
180509467b48Spatrick if (isa<Instruction>(AllSameValue) &&
180609467b48Spatrick InstrToDFSNum(AllSameValue) > InstrToDFSNum(I))
180709467b48Spatrick return E;
180809467b48Spatrick NumGVNPhisAllSame++;
180909467b48Spatrick LLVM_DEBUG(dbgs() << "Simplified PHI node " << *I << " to " << *AllSameValue
181009467b48Spatrick << "\n");
181109467b48Spatrick deleteExpression(E);
181209467b48Spatrick return createVariableOrConstant(AllSameValue);
181309467b48Spatrick }
181409467b48Spatrick return E;
181509467b48Spatrick }
181609467b48Spatrick
181709467b48Spatrick const Expression *
performSymbolicAggrValueEvaluation(Instruction * I) const181809467b48Spatrick NewGVN::performSymbolicAggrValueEvaluation(Instruction *I) const {
181909467b48Spatrick if (auto *EI = dyn_cast<ExtractValueInst>(I)) {
182009467b48Spatrick auto *WO = dyn_cast<WithOverflowInst>(EI->getAggregateOperand());
182109467b48Spatrick if (WO && EI->getNumIndices() == 1 && *EI->idx_begin() == 0)
182209467b48Spatrick // EI is an extract from one of our with.overflow intrinsics. Synthesize
182309467b48Spatrick // a semantically equivalent expression instead of an extract value
182409467b48Spatrick // expression.
182509467b48Spatrick return createBinaryExpression(WO->getBinaryOp(), EI->getType(),
182609467b48Spatrick WO->getLHS(), WO->getRHS(), I);
182709467b48Spatrick }
182809467b48Spatrick
182909467b48Spatrick return createAggregateValueExpression(I);
183009467b48Spatrick }
183109467b48Spatrick
performSymbolicCmpEvaluation(Instruction * I) const183273471bf0Spatrick NewGVN::ExprResult NewGVN::performSymbolicCmpEvaluation(Instruction *I) const {
183309467b48Spatrick assert(isa<CmpInst>(I) && "Expected a cmp instruction.");
183409467b48Spatrick
183509467b48Spatrick auto *CI = cast<CmpInst>(I);
183609467b48Spatrick // See if our operands are equal to those of a previous predicate, and if so,
183709467b48Spatrick // if it implies true or false.
183809467b48Spatrick auto Op0 = lookupOperandLeader(CI->getOperand(0));
183909467b48Spatrick auto Op1 = lookupOperandLeader(CI->getOperand(1));
184009467b48Spatrick auto OurPredicate = CI->getPredicate();
184109467b48Spatrick if (shouldSwapOperands(Op0, Op1)) {
184209467b48Spatrick std::swap(Op0, Op1);
184309467b48Spatrick OurPredicate = CI->getSwappedPredicate();
184409467b48Spatrick }
184509467b48Spatrick
184609467b48Spatrick // Avoid processing the same info twice.
184709467b48Spatrick const PredicateBase *LastPredInfo = nullptr;
184809467b48Spatrick // See if we know something about the comparison itself, like it is the target
184909467b48Spatrick // of an assume.
185009467b48Spatrick auto *CmpPI = PredInfo->getPredicateInfoFor(I);
1851*d415bd75Srobert if (isa_and_nonnull<PredicateAssume>(CmpPI))
185273471bf0Spatrick return ExprResult::some(
185373471bf0Spatrick createConstantExpression(ConstantInt::getTrue(CI->getType())));
185409467b48Spatrick
185509467b48Spatrick if (Op0 == Op1) {
185609467b48Spatrick // This condition does not depend on predicates, no need to add users
185709467b48Spatrick if (CI->isTrueWhenEqual())
185873471bf0Spatrick return ExprResult::some(
185973471bf0Spatrick createConstantExpression(ConstantInt::getTrue(CI->getType())));
186009467b48Spatrick else if (CI->isFalseWhenEqual())
186173471bf0Spatrick return ExprResult::some(
186273471bf0Spatrick createConstantExpression(ConstantInt::getFalse(CI->getType())));
186309467b48Spatrick }
186409467b48Spatrick
186509467b48Spatrick // NOTE: Because we are comparing both operands here and below, and using
186609467b48Spatrick // previous comparisons, we rely on fact that predicateinfo knows to mark
186709467b48Spatrick // comparisons that use renamed operands as users of the earlier comparisons.
186809467b48Spatrick // It is *not* enough to just mark predicateinfo renamed operands as users of
186909467b48Spatrick // the earlier comparisons, because the *other* operand may have changed in a
187009467b48Spatrick // previous iteration.
187109467b48Spatrick // Example:
187209467b48Spatrick // icmp slt %a, %b
187309467b48Spatrick // %b.0 = ssa.copy(%b)
187409467b48Spatrick // false branch:
187509467b48Spatrick // icmp slt %c, %b.0
187609467b48Spatrick
187709467b48Spatrick // %c and %a may start out equal, and thus, the code below will say the second
187809467b48Spatrick // %icmp is false. c may become equal to something else, and in that case the
187909467b48Spatrick // %second icmp *must* be reexamined, but would not if only the renamed
188009467b48Spatrick // %operands are considered users of the icmp.
188109467b48Spatrick
188209467b48Spatrick // *Currently* we only check one level of comparisons back, and only mark one
188309467b48Spatrick // level back as touched when changes happen. If you modify this code to look
188409467b48Spatrick // back farther through comparisons, you *must* mark the appropriate
188509467b48Spatrick // comparisons as users in PredicateInfo.cpp, or you will cause bugs. See if
188609467b48Spatrick // we know something just from the operands themselves
188709467b48Spatrick
188809467b48Spatrick // See if our operands have predicate info, so that we may be able to derive
188909467b48Spatrick // something from a previous comparison.
189009467b48Spatrick for (const auto &Op : CI->operands()) {
189109467b48Spatrick auto *PI = PredInfo->getPredicateInfoFor(Op);
189209467b48Spatrick if (const auto *PBranch = dyn_cast_or_null<PredicateBranch>(PI)) {
189309467b48Spatrick if (PI == LastPredInfo)
189409467b48Spatrick continue;
189509467b48Spatrick LastPredInfo = PI;
189609467b48Spatrick // In phi of ops cases, we may have predicate info that we are evaluating
189709467b48Spatrick // in a different context.
189809467b48Spatrick if (!DT->dominates(PBranch->To, getBlockForValue(I)))
189909467b48Spatrick continue;
190009467b48Spatrick // TODO: Along the false edge, we may know more things too, like
190109467b48Spatrick // icmp of
190209467b48Spatrick // same operands is false.
190309467b48Spatrick // TODO: We only handle actual comparison conditions below, not
190409467b48Spatrick // and/or.
190509467b48Spatrick auto *BranchCond = dyn_cast<CmpInst>(PBranch->Condition);
190609467b48Spatrick if (!BranchCond)
190709467b48Spatrick continue;
190809467b48Spatrick auto *BranchOp0 = lookupOperandLeader(BranchCond->getOperand(0));
190909467b48Spatrick auto *BranchOp1 = lookupOperandLeader(BranchCond->getOperand(1));
191009467b48Spatrick auto BranchPredicate = BranchCond->getPredicate();
191109467b48Spatrick if (shouldSwapOperands(BranchOp0, BranchOp1)) {
191209467b48Spatrick std::swap(BranchOp0, BranchOp1);
191309467b48Spatrick BranchPredicate = BranchCond->getSwappedPredicate();
191409467b48Spatrick }
191509467b48Spatrick if (BranchOp0 == Op0 && BranchOp1 == Op1) {
191609467b48Spatrick if (PBranch->TrueEdge) {
191709467b48Spatrick // If we know the previous predicate is true and we are in the true
191809467b48Spatrick // edge then we may be implied true or false.
191909467b48Spatrick if (CmpInst::isImpliedTrueByMatchingCmp(BranchPredicate,
192009467b48Spatrick OurPredicate)) {
192173471bf0Spatrick return ExprResult::some(
192273471bf0Spatrick createConstantExpression(ConstantInt::getTrue(CI->getType())),
192373471bf0Spatrick PI);
192409467b48Spatrick }
192509467b48Spatrick
192609467b48Spatrick if (CmpInst::isImpliedFalseByMatchingCmp(BranchPredicate,
192709467b48Spatrick OurPredicate)) {
192873471bf0Spatrick return ExprResult::some(
192973471bf0Spatrick createConstantExpression(ConstantInt::getFalse(CI->getType())),
193073471bf0Spatrick PI);
193109467b48Spatrick }
193209467b48Spatrick } else {
193309467b48Spatrick // Just handle the ne and eq cases, where if we have the same
193409467b48Spatrick // operands, we may know something.
193509467b48Spatrick if (BranchPredicate == OurPredicate) {
193609467b48Spatrick // Same predicate, same ops,we know it was false, so this is false.
193773471bf0Spatrick return ExprResult::some(
193873471bf0Spatrick createConstantExpression(ConstantInt::getFalse(CI->getType())),
193973471bf0Spatrick PI);
194009467b48Spatrick } else if (BranchPredicate ==
194109467b48Spatrick CmpInst::getInversePredicate(OurPredicate)) {
194209467b48Spatrick // Inverse predicate, we know the other was false, so this is true.
194373471bf0Spatrick return ExprResult::some(
194473471bf0Spatrick createConstantExpression(ConstantInt::getTrue(CI->getType())),
194573471bf0Spatrick PI);
194609467b48Spatrick }
194709467b48Spatrick }
194809467b48Spatrick }
194909467b48Spatrick }
195009467b48Spatrick }
195109467b48Spatrick // Create expression will take care of simplifyCmpInst
195209467b48Spatrick return createExpression(I);
195309467b48Spatrick }
195409467b48Spatrick
195509467b48Spatrick // Substitute and symbolize the value before value numbering.
195673471bf0Spatrick NewGVN::ExprResult
performSymbolicEvaluation(Value * V,SmallPtrSetImpl<Value * > & Visited) const195709467b48Spatrick NewGVN::performSymbolicEvaluation(Value *V,
195809467b48Spatrick SmallPtrSetImpl<Value *> &Visited) const {
195973471bf0Spatrick
196009467b48Spatrick const Expression *E = nullptr;
196109467b48Spatrick if (auto *C = dyn_cast<Constant>(V))
196209467b48Spatrick E = createConstantExpression(C);
196309467b48Spatrick else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
196409467b48Spatrick E = createVariableExpression(V);
196509467b48Spatrick } else {
196609467b48Spatrick // TODO: memory intrinsics.
196709467b48Spatrick // TODO: Some day, we should do the forward propagation and reassociation
196809467b48Spatrick // parts of the algorithm.
196909467b48Spatrick auto *I = cast<Instruction>(V);
197009467b48Spatrick switch (I->getOpcode()) {
197109467b48Spatrick case Instruction::ExtractValue:
197209467b48Spatrick case Instruction::InsertValue:
197309467b48Spatrick E = performSymbolicAggrValueEvaluation(I);
197409467b48Spatrick break;
197509467b48Spatrick case Instruction::PHI: {
197609467b48Spatrick SmallVector<ValPair, 3> Ops;
197709467b48Spatrick auto *PN = cast<PHINode>(I);
197809467b48Spatrick for (unsigned i = 0; i < PN->getNumOperands(); ++i)
197909467b48Spatrick Ops.push_back({PN->getIncomingValue(i), PN->getIncomingBlock(i)});
198009467b48Spatrick // Sort to ensure the invariant createPHIExpression requires is met.
198109467b48Spatrick sortPHIOps(Ops);
198209467b48Spatrick E = performSymbolicPHIEvaluation(Ops, I, getBlockForValue(I));
198309467b48Spatrick } break;
198409467b48Spatrick case Instruction::Call:
198573471bf0Spatrick return performSymbolicCallEvaluation(I);
198609467b48Spatrick break;
198709467b48Spatrick case Instruction::Store:
198809467b48Spatrick E = performSymbolicStoreEvaluation(I);
198909467b48Spatrick break;
199009467b48Spatrick case Instruction::Load:
199109467b48Spatrick E = performSymbolicLoadEvaluation(I);
199209467b48Spatrick break;
199309467b48Spatrick case Instruction::BitCast:
199409467b48Spatrick case Instruction::AddrSpaceCast:
199573471bf0Spatrick return createExpression(I);
199609467b48Spatrick break;
199709467b48Spatrick case Instruction::ICmp:
199809467b48Spatrick case Instruction::FCmp:
199973471bf0Spatrick return performSymbolicCmpEvaluation(I);
200009467b48Spatrick break;
200109467b48Spatrick case Instruction::FNeg:
200209467b48Spatrick case Instruction::Add:
200309467b48Spatrick case Instruction::FAdd:
200409467b48Spatrick case Instruction::Sub:
200509467b48Spatrick case Instruction::FSub:
200609467b48Spatrick case Instruction::Mul:
200709467b48Spatrick case Instruction::FMul:
200809467b48Spatrick case Instruction::UDiv:
200909467b48Spatrick case Instruction::SDiv:
201009467b48Spatrick case Instruction::FDiv:
201109467b48Spatrick case Instruction::URem:
201209467b48Spatrick case Instruction::SRem:
201309467b48Spatrick case Instruction::FRem:
201409467b48Spatrick case Instruction::Shl:
201509467b48Spatrick case Instruction::LShr:
201609467b48Spatrick case Instruction::AShr:
201709467b48Spatrick case Instruction::And:
201809467b48Spatrick case Instruction::Or:
201909467b48Spatrick case Instruction::Xor:
202009467b48Spatrick case Instruction::Trunc:
202109467b48Spatrick case Instruction::ZExt:
202209467b48Spatrick case Instruction::SExt:
202309467b48Spatrick case Instruction::FPToUI:
202409467b48Spatrick case Instruction::FPToSI:
202509467b48Spatrick case Instruction::UIToFP:
202609467b48Spatrick case Instruction::SIToFP:
202709467b48Spatrick case Instruction::FPTrunc:
202809467b48Spatrick case Instruction::FPExt:
202909467b48Spatrick case Instruction::PtrToInt:
203009467b48Spatrick case Instruction::IntToPtr:
203109467b48Spatrick case Instruction::Select:
203209467b48Spatrick case Instruction::ExtractElement:
203309467b48Spatrick case Instruction::InsertElement:
203409467b48Spatrick case Instruction::GetElementPtr:
203573471bf0Spatrick return createExpression(I);
203609467b48Spatrick break;
2037097a140dSpatrick case Instruction::ShuffleVector:
2038097a140dSpatrick // FIXME: Add support for shufflevector to createExpression.
203973471bf0Spatrick return ExprResult::none();
204009467b48Spatrick default:
204173471bf0Spatrick return ExprResult::none();
204209467b48Spatrick }
204309467b48Spatrick }
204473471bf0Spatrick return ExprResult::some(E);
204509467b48Spatrick }
204609467b48Spatrick
204709467b48Spatrick // Look up a container of values/instructions in a map, and touch all the
204809467b48Spatrick // instructions in the container. Then erase value from the map.
204909467b48Spatrick template <typename Map, typename KeyType>
touchAndErase(Map & M,const KeyType & Key)205009467b48Spatrick void NewGVN::touchAndErase(Map &M, const KeyType &Key) {
205109467b48Spatrick const auto Result = M.find_as(Key);
205209467b48Spatrick if (Result != M.end()) {
205309467b48Spatrick for (const typename Map::mapped_type::value_type Mapped : Result->second)
205409467b48Spatrick TouchedInstructions.set(InstrToDFSNum(Mapped));
205509467b48Spatrick M.erase(Result);
205609467b48Spatrick }
205709467b48Spatrick }
205809467b48Spatrick
addAdditionalUsers(Value * To,Value * User) const205909467b48Spatrick void NewGVN::addAdditionalUsers(Value *To, Value *User) const {
206009467b48Spatrick assert(User && To != User);
206109467b48Spatrick if (isa<Instruction>(To))
206209467b48Spatrick AdditionalUsers[To].insert(User);
206309467b48Spatrick }
206409467b48Spatrick
addAdditionalUsers(ExprResult & Res,Instruction * User) const206573471bf0Spatrick void NewGVN::addAdditionalUsers(ExprResult &Res, Instruction *User) const {
206673471bf0Spatrick if (Res.ExtraDep && Res.ExtraDep != User)
206773471bf0Spatrick addAdditionalUsers(Res.ExtraDep, User);
206873471bf0Spatrick Res.ExtraDep = nullptr;
206973471bf0Spatrick
207073471bf0Spatrick if (Res.PredDep) {
207173471bf0Spatrick if (const auto *PBranch = dyn_cast<PredicateBranch>(Res.PredDep))
207273471bf0Spatrick PredicateToUsers[PBranch->Condition].insert(User);
207373471bf0Spatrick else if (const auto *PAssume = dyn_cast<PredicateAssume>(Res.PredDep))
207473471bf0Spatrick PredicateToUsers[PAssume->Condition].insert(User);
207573471bf0Spatrick }
207673471bf0Spatrick Res.PredDep = nullptr;
207773471bf0Spatrick }
207873471bf0Spatrick
markUsersTouched(Value * V)207909467b48Spatrick void NewGVN::markUsersTouched(Value *V) {
208009467b48Spatrick // Now mark the users as touched.
208109467b48Spatrick for (auto *User : V->users()) {
208209467b48Spatrick assert(isa<Instruction>(User) && "Use of value not within an instruction?");
208309467b48Spatrick TouchedInstructions.set(InstrToDFSNum(User));
208409467b48Spatrick }
208509467b48Spatrick touchAndErase(AdditionalUsers, V);
208609467b48Spatrick }
208709467b48Spatrick
addMemoryUsers(const MemoryAccess * To,MemoryAccess * U) const208809467b48Spatrick void NewGVN::addMemoryUsers(const MemoryAccess *To, MemoryAccess *U) const {
208909467b48Spatrick LLVM_DEBUG(dbgs() << "Adding memory user " << *U << " to " << *To << "\n");
209009467b48Spatrick MemoryToUsers[To].insert(U);
209109467b48Spatrick }
209209467b48Spatrick
markMemoryDefTouched(const MemoryAccess * MA)209309467b48Spatrick void NewGVN::markMemoryDefTouched(const MemoryAccess *MA) {
209409467b48Spatrick TouchedInstructions.set(MemoryToDFSNum(MA));
209509467b48Spatrick }
209609467b48Spatrick
markMemoryUsersTouched(const MemoryAccess * MA)209709467b48Spatrick void NewGVN::markMemoryUsersTouched(const MemoryAccess *MA) {
209809467b48Spatrick if (isa<MemoryUse>(MA))
209909467b48Spatrick return;
2100*d415bd75Srobert for (const auto *U : MA->users())
210109467b48Spatrick TouchedInstructions.set(MemoryToDFSNum(U));
210209467b48Spatrick touchAndErase(MemoryToUsers, MA);
210309467b48Spatrick }
210409467b48Spatrick
210509467b48Spatrick // Touch all the predicates that depend on this instruction.
markPredicateUsersTouched(Instruction * I)210609467b48Spatrick void NewGVN::markPredicateUsersTouched(Instruction *I) {
210709467b48Spatrick touchAndErase(PredicateToUsers, I);
210809467b48Spatrick }
210909467b48Spatrick
211009467b48Spatrick // Mark users affected by a memory leader change.
markMemoryLeaderChangeTouched(CongruenceClass * CC)211109467b48Spatrick void NewGVN::markMemoryLeaderChangeTouched(CongruenceClass *CC) {
2112*d415bd75Srobert for (const auto *M : CC->memory())
211309467b48Spatrick markMemoryDefTouched(M);
211409467b48Spatrick }
211509467b48Spatrick
211609467b48Spatrick // Touch the instructions that need to be updated after a congruence class has a
211709467b48Spatrick // leader change, and mark changed values.
markValueLeaderChangeTouched(CongruenceClass * CC)211809467b48Spatrick void NewGVN::markValueLeaderChangeTouched(CongruenceClass *CC) {
2119*d415bd75Srobert for (auto *M : *CC) {
212009467b48Spatrick if (auto *I = dyn_cast<Instruction>(M))
212109467b48Spatrick TouchedInstructions.set(InstrToDFSNum(I));
212209467b48Spatrick LeaderChanges.insert(M);
212309467b48Spatrick }
212409467b48Spatrick }
212509467b48Spatrick
212609467b48Spatrick // Give a range of things that have instruction DFS numbers, this will return
212709467b48Spatrick // the member of the range with the smallest dfs number.
212809467b48Spatrick template <class T, class Range>
212909467b48Spatrick T *NewGVN::getMinDFSOfRange(const Range &R) const {
213009467b48Spatrick std::pair<T *, unsigned> MinDFS = {nullptr, ~0U};
213109467b48Spatrick for (const auto X : R) {
213209467b48Spatrick auto DFSNum = InstrToDFSNum(X);
213309467b48Spatrick if (DFSNum < MinDFS.second)
213409467b48Spatrick MinDFS = {X, DFSNum};
213509467b48Spatrick }
213609467b48Spatrick return MinDFS.first;
213709467b48Spatrick }
213809467b48Spatrick
213909467b48Spatrick // This function returns the MemoryAccess that should be the next leader of
214009467b48Spatrick // congruence class CC, under the assumption that the current leader is going to
214109467b48Spatrick // disappear.
getNextMemoryLeader(CongruenceClass * CC) const214209467b48Spatrick const MemoryAccess *NewGVN::getNextMemoryLeader(CongruenceClass *CC) const {
214309467b48Spatrick // TODO: If this ends up to slow, we can maintain a next memory leader like we
214409467b48Spatrick // do for regular leaders.
214509467b48Spatrick // Make sure there will be a leader to find.
214609467b48Spatrick assert(!CC->definesNoMemory() && "Can't get next leader if there is none");
214709467b48Spatrick if (CC->getStoreCount() > 0) {
214809467b48Spatrick if (auto *NL = dyn_cast_or_null<StoreInst>(CC->getNextLeader().first))
214909467b48Spatrick return getMemoryAccess(NL);
215009467b48Spatrick // Find the store with the minimum DFS number.
215109467b48Spatrick auto *V = getMinDFSOfRange<Value>(make_filter_range(
215209467b48Spatrick *CC, [&](const Value *V) { return isa<StoreInst>(V); }));
215309467b48Spatrick return getMemoryAccess(cast<StoreInst>(V));
215409467b48Spatrick }
215509467b48Spatrick assert(CC->getStoreCount() == 0);
215609467b48Spatrick
215709467b48Spatrick // Given our assertion, hitting this part must mean
215809467b48Spatrick // !OldClass->memory_empty()
215909467b48Spatrick if (CC->memory_size() == 1)
216009467b48Spatrick return *CC->memory_begin();
216109467b48Spatrick return getMinDFSOfRange<const MemoryPhi>(CC->memory());
216209467b48Spatrick }
216309467b48Spatrick
216409467b48Spatrick // This function returns the next value leader of a congruence class, under the
216509467b48Spatrick // assumption that the current leader is going away. This should end up being
216609467b48Spatrick // the next most dominating member.
getNextValueLeader(CongruenceClass * CC) const216709467b48Spatrick Value *NewGVN::getNextValueLeader(CongruenceClass *CC) const {
216809467b48Spatrick // We don't need to sort members if there is only 1, and we don't care about
216909467b48Spatrick // sorting the TOP class because everything either gets out of it or is
217009467b48Spatrick // unreachable.
217109467b48Spatrick
217209467b48Spatrick if (CC->size() == 1 || CC == TOPClass) {
217309467b48Spatrick return *(CC->begin());
217409467b48Spatrick } else if (CC->getNextLeader().first) {
217509467b48Spatrick ++NumGVNAvoidedSortedLeaderChanges;
217609467b48Spatrick return CC->getNextLeader().first;
217709467b48Spatrick } else {
217809467b48Spatrick ++NumGVNSortedLeaderChanges;
217909467b48Spatrick // NOTE: If this ends up to slow, we can maintain a dual structure for
218009467b48Spatrick // member testing/insertion, or keep things mostly sorted, and sort only
218109467b48Spatrick // here, or use SparseBitVector or ....
218209467b48Spatrick return getMinDFSOfRange<Value>(*CC);
218309467b48Spatrick }
218409467b48Spatrick }
218509467b48Spatrick
218609467b48Spatrick // Move a MemoryAccess, currently in OldClass, to NewClass, including updates to
218709467b48Spatrick // the memory members, etc for the move.
218809467b48Spatrick //
218909467b48Spatrick // The invariants of this function are:
219009467b48Spatrick //
219109467b48Spatrick // - I must be moving to NewClass from OldClass
219209467b48Spatrick // - The StoreCount of OldClass and NewClass is expected to have been updated
219309467b48Spatrick // for I already if it is a store.
219409467b48Spatrick // - The OldClass memory leader has not been updated yet if I was the leader.
moveMemoryToNewCongruenceClass(Instruction * I,MemoryAccess * InstMA,CongruenceClass * OldClass,CongruenceClass * NewClass)219509467b48Spatrick void NewGVN::moveMemoryToNewCongruenceClass(Instruction *I,
219609467b48Spatrick MemoryAccess *InstMA,
219709467b48Spatrick CongruenceClass *OldClass,
219809467b48Spatrick CongruenceClass *NewClass) {
219909467b48Spatrick // If the leader is I, and we had a representative MemoryAccess, it should
220009467b48Spatrick // be the MemoryAccess of OldClass.
220109467b48Spatrick assert((!InstMA || !OldClass->getMemoryLeader() ||
220209467b48Spatrick OldClass->getLeader() != I ||
220309467b48Spatrick MemoryAccessToClass.lookup(OldClass->getMemoryLeader()) ==
220409467b48Spatrick MemoryAccessToClass.lookup(InstMA)) &&
220509467b48Spatrick "Representative MemoryAccess mismatch");
220609467b48Spatrick // First, see what happens to the new class
220709467b48Spatrick if (!NewClass->getMemoryLeader()) {
220809467b48Spatrick // Should be a new class, or a store becoming a leader of a new class.
220909467b48Spatrick assert(NewClass->size() == 1 ||
221009467b48Spatrick (isa<StoreInst>(I) && NewClass->getStoreCount() == 1));
221109467b48Spatrick NewClass->setMemoryLeader(InstMA);
221209467b48Spatrick // Mark it touched if we didn't just create a singleton
221309467b48Spatrick LLVM_DEBUG(dbgs() << "Memory class leader change for class "
221409467b48Spatrick << NewClass->getID()
221509467b48Spatrick << " due to new memory instruction becoming leader\n");
221609467b48Spatrick markMemoryLeaderChangeTouched(NewClass);
221709467b48Spatrick }
221809467b48Spatrick setMemoryClass(InstMA, NewClass);
221909467b48Spatrick // Now, fixup the old class if necessary
222009467b48Spatrick if (OldClass->getMemoryLeader() == InstMA) {
222109467b48Spatrick if (!OldClass->definesNoMemory()) {
222209467b48Spatrick OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
222309467b48Spatrick LLVM_DEBUG(dbgs() << "Memory class leader change for class "
222409467b48Spatrick << OldClass->getID() << " to "
222509467b48Spatrick << *OldClass->getMemoryLeader()
222609467b48Spatrick << " due to removal of old leader " << *InstMA << "\n");
222709467b48Spatrick markMemoryLeaderChangeTouched(OldClass);
222809467b48Spatrick } else
222909467b48Spatrick OldClass->setMemoryLeader(nullptr);
223009467b48Spatrick }
223109467b48Spatrick }
223209467b48Spatrick
223309467b48Spatrick // Move a value, currently in OldClass, to be part of NewClass
223409467b48Spatrick // Update OldClass and NewClass for the move (including changing leaders, etc).
moveValueToNewCongruenceClass(Instruction * I,const Expression * E,CongruenceClass * OldClass,CongruenceClass * NewClass)223509467b48Spatrick void NewGVN::moveValueToNewCongruenceClass(Instruction *I, const Expression *E,
223609467b48Spatrick CongruenceClass *OldClass,
223709467b48Spatrick CongruenceClass *NewClass) {
223809467b48Spatrick if (I == OldClass->getNextLeader().first)
223909467b48Spatrick OldClass->resetNextLeader();
224009467b48Spatrick
224109467b48Spatrick OldClass->erase(I);
224209467b48Spatrick NewClass->insert(I);
224309467b48Spatrick
224409467b48Spatrick if (NewClass->getLeader() != I)
224509467b48Spatrick NewClass->addPossibleNextLeader({I, InstrToDFSNum(I)});
224609467b48Spatrick // Handle our special casing of stores.
224709467b48Spatrick if (auto *SI = dyn_cast<StoreInst>(I)) {
224809467b48Spatrick OldClass->decStoreCount();
224909467b48Spatrick // Okay, so when do we want to make a store a leader of a class?
225009467b48Spatrick // If we have a store defined by an earlier load, we want the earlier load
225109467b48Spatrick // to lead the class.
225209467b48Spatrick // If we have a store defined by something else, we want the store to lead
225309467b48Spatrick // the class so everything else gets the "something else" as a value.
225409467b48Spatrick // If we have a store as the single member of the class, we want the store
225509467b48Spatrick // as the leader
225609467b48Spatrick if (NewClass->getStoreCount() == 0 && !NewClass->getStoredValue()) {
225709467b48Spatrick // If it's a store expression we are using, it means we are not equivalent
225809467b48Spatrick // to something earlier.
225909467b48Spatrick if (auto *SE = dyn_cast<StoreExpression>(E)) {
226009467b48Spatrick NewClass->setStoredValue(SE->getStoredValue());
226109467b48Spatrick markValueLeaderChangeTouched(NewClass);
226209467b48Spatrick // Shift the new class leader to be the store
226309467b48Spatrick LLVM_DEBUG(dbgs() << "Changing leader of congruence class "
226409467b48Spatrick << NewClass->getID() << " from "
226509467b48Spatrick << *NewClass->getLeader() << " to " << *SI
226609467b48Spatrick << " because store joined class\n");
226709467b48Spatrick // If we changed the leader, we have to mark it changed because we don't
226809467b48Spatrick // know what it will do to symbolic evaluation.
226909467b48Spatrick NewClass->setLeader(SI);
227009467b48Spatrick }
227109467b48Spatrick // We rely on the code below handling the MemoryAccess change.
227209467b48Spatrick }
227309467b48Spatrick NewClass->incStoreCount();
227409467b48Spatrick }
227509467b48Spatrick // True if there is no memory instructions left in a class that had memory
227609467b48Spatrick // instructions before.
227709467b48Spatrick
227809467b48Spatrick // If it's not a memory use, set the MemoryAccess equivalence
227909467b48Spatrick auto *InstMA = dyn_cast_or_null<MemoryDef>(getMemoryAccess(I));
228009467b48Spatrick if (InstMA)
228109467b48Spatrick moveMemoryToNewCongruenceClass(I, InstMA, OldClass, NewClass);
228209467b48Spatrick ValueToClass[I] = NewClass;
228309467b48Spatrick // See if we destroyed the class or need to swap leaders.
228409467b48Spatrick if (OldClass->empty() && OldClass != TOPClass) {
228509467b48Spatrick if (OldClass->getDefiningExpr()) {
228609467b48Spatrick LLVM_DEBUG(dbgs() << "Erasing expression " << *OldClass->getDefiningExpr()
228709467b48Spatrick << " from table\n");
228809467b48Spatrick // We erase it as an exact expression to make sure we don't just erase an
228909467b48Spatrick // equivalent one.
229009467b48Spatrick auto Iter = ExpressionToClass.find_as(
229109467b48Spatrick ExactEqualsExpression(*OldClass->getDefiningExpr()));
229209467b48Spatrick if (Iter != ExpressionToClass.end())
229309467b48Spatrick ExpressionToClass.erase(Iter);
229409467b48Spatrick #ifdef EXPENSIVE_CHECKS
229509467b48Spatrick assert(
229609467b48Spatrick (*OldClass->getDefiningExpr() != *E || ExpressionToClass.lookup(E)) &&
229709467b48Spatrick "We erased the expression we just inserted, which should not happen");
229809467b48Spatrick #endif
229909467b48Spatrick }
230009467b48Spatrick } else if (OldClass->getLeader() == I) {
230109467b48Spatrick // When the leader changes, the value numbering of
230209467b48Spatrick // everything may change due to symbolization changes, so we need to
230309467b48Spatrick // reprocess.
230409467b48Spatrick LLVM_DEBUG(dbgs() << "Value class leader change for class "
230509467b48Spatrick << OldClass->getID() << "\n");
230609467b48Spatrick ++NumGVNLeaderChanges;
230709467b48Spatrick // Destroy the stored value if there are no more stores to represent it.
230809467b48Spatrick // Note that this is basically clean up for the expression removal that
230909467b48Spatrick // happens below. If we remove stores from a class, we may leave it as a
231009467b48Spatrick // class of equivalent memory phis.
231109467b48Spatrick if (OldClass->getStoreCount() == 0) {
231209467b48Spatrick if (OldClass->getStoredValue())
231309467b48Spatrick OldClass->setStoredValue(nullptr);
231409467b48Spatrick }
231509467b48Spatrick OldClass->setLeader(getNextValueLeader(OldClass));
231609467b48Spatrick OldClass->resetNextLeader();
231709467b48Spatrick markValueLeaderChangeTouched(OldClass);
231809467b48Spatrick }
231909467b48Spatrick }
232009467b48Spatrick
232109467b48Spatrick // For a given expression, mark the phi of ops instructions that could have
232209467b48Spatrick // changed as a result.
markPhiOfOpsChanged(const Expression * E)232309467b48Spatrick void NewGVN::markPhiOfOpsChanged(const Expression *E) {
232409467b48Spatrick touchAndErase(ExpressionToPhiOfOps, E);
232509467b48Spatrick }
232609467b48Spatrick
232709467b48Spatrick // Perform congruence finding on a given value numbering expression.
performCongruenceFinding(Instruction * I,const Expression * E)232809467b48Spatrick void NewGVN::performCongruenceFinding(Instruction *I, const Expression *E) {
232909467b48Spatrick // This is guaranteed to return something, since it will at least find
233009467b48Spatrick // TOP.
233109467b48Spatrick
233209467b48Spatrick CongruenceClass *IClass = ValueToClass.lookup(I);
233309467b48Spatrick assert(IClass && "Should have found a IClass");
233409467b48Spatrick // Dead classes should have been eliminated from the mapping.
233509467b48Spatrick assert(!IClass->isDead() && "Found a dead class");
233609467b48Spatrick
233709467b48Spatrick CongruenceClass *EClass = nullptr;
233809467b48Spatrick if (const auto *VE = dyn_cast<VariableExpression>(E)) {
233909467b48Spatrick EClass = ValueToClass.lookup(VE->getVariableValue());
234009467b48Spatrick } else if (isa<DeadExpression>(E)) {
234109467b48Spatrick EClass = TOPClass;
234209467b48Spatrick }
234309467b48Spatrick if (!EClass) {
234409467b48Spatrick auto lookupResult = ExpressionToClass.insert({E, nullptr});
234509467b48Spatrick
234609467b48Spatrick // If it's not in the value table, create a new congruence class.
234709467b48Spatrick if (lookupResult.second) {
234809467b48Spatrick CongruenceClass *NewClass = createCongruenceClass(nullptr, E);
234909467b48Spatrick auto place = lookupResult.first;
235009467b48Spatrick place->second = NewClass;
235109467b48Spatrick
235209467b48Spatrick // Constants and variables should always be made the leader.
235309467b48Spatrick if (const auto *CE = dyn_cast<ConstantExpression>(E)) {
235409467b48Spatrick NewClass->setLeader(CE->getConstantValue());
235509467b48Spatrick } else if (const auto *SE = dyn_cast<StoreExpression>(E)) {
235609467b48Spatrick StoreInst *SI = SE->getStoreInst();
235709467b48Spatrick NewClass->setLeader(SI);
235809467b48Spatrick NewClass->setStoredValue(SE->getStoredValue());
235909467b48Spatrick // The RepMemoryAccess field will be filled in properly by the
236009467b48Spatrick // moveValueToNewCongruenceClass call.
236109467b48Spatrick } else {
236209467b48Spatrick NewClass->setLeader(I);
236309467b48Spatrick }
236409467b48Spatrick assert(!isa<VariableExpression>(E) &&
236509467b48Spatrick "VariableExpression should have been handled already");
236609467b48Spatrick
236709467b48Spatrick EClass = NewClass;
236809467b48Spatrick LLVM_DEBUG(dbgs() << "Created new congruence class for " << *I
236909467b48Spatrick << " using expression " << *E << " at "
237009467b48Spatrick << NewClass->getID() << " and leader "
237109467b48Spatrick << *(NewClass->getLeader()));
237209467b48Spatrick if (NewClass->getStoredValue())
237309467b48Spatrick LLVM_DEBUG(dbgs() << " and stored value "
237409467b48Spatrick << *(NewClass->getStoredValue()));
237509467b48Spatrick LLVM_DEBUG(dbgs() << "\n");
237609467b48Spatrick } else {
237709467b48Spatrick EClass = lookupResult.first->second;
237809467b48Spatrick if (isa<ConstantExpression>(E))
237909467b48Spatrick assert((isa<Constant>(EClass->getLeader()) ||
238009467b48Spatrick (EClass->getStoredValue() &&
238109467b48Spatrick isa<Constant>(EClass->getStoredValue()))) &&
238209467b48Spatrick "Any class with a constant expression should have a "
238309467b48Spatrick "constant leader");
238409467b48Spatrick
238509467b48Spatrick assert(EClass && "Somehow don't have an eclass");
238609467b48Spatrick
238709467b48Spatrick assert(!EClass->isDead() && "We accidentally looked up a dead class");
238809467b48Spatrick }
238909467b48Spatrick }
239009467b48Spatrick bool ClassChanged = IClass != EClass;
239109467b48Spatrick bool LeaderChanged = LeaderChanges.erase(I);
239209467b48Spatrick if (ClassChanged || LeaderChanged) {
239309467b48Spatrick LLVM_DEBUG(dbgs() << "New class " << EClass->getID() << " for expression "
239409467b48Spatrick << *E << "\n");
239509467b48Spatrick if (ClassChanged) {
239609467b48Spatrick moveValueToNewCongruenceClass(I, E, IClass, EClass);
239709467b48Spatrick markPhiOfOpsChanged(E);
239809467b48Spatrick }
239909467b48Spatrick
240009467b48Spatrick markUsersTouched(I);
240109467b48Spatrick if (MemoryAccess *MA = getMemoryAccess(I))
240209467b48Spatrick markMemoryUsersTouched(MA);
240309467b48Spatrick if (auto *CI = dyn_cast<CmpInst>(I))
240409467b48Spatrick markPredicateUsersTouched(CI);
240509467b48Spatrick }
240609467b48Spatrick // If we changed the class of the store, we want to ensure nothing finds the
240709467b48Spatrick // old store expression. In particular, loads do not compare against stored
240809467b48Spatrick // value, so they will find old store expressions (and associated class
240909467b48Spatrick // mappings) if we leave them in the table.
241009467b48Spatrick if (ClassChanged && isa<StoreInst>(I)) {
241109467b48Spatrick auto *OldE = ValueToExpression.lookup(I);
241209467b48Spatrick // It could just be that the old class died. We don't want to erase it if we
241309467b48Spatrick // just moved classes.
241409467b48Spatrick if (OldE && isa<StoreExpression>(OldE) && *E != *OldE) {
241509467b48Spatrick // Erase this as an exact expression to ensure we don't erase expressions
241609467b48Spatrick // equivalent to it.
241709467b48Spatrick auto Iter = ExpressionToClass.find_as(ExactEqualsExpression(*OldE));
241809467b48Spatrick if (Iter != ExpressionToClass.end())
241909467b48Spatrick ExpressionToClass.erase(Iter);
242009467b48Spatrick }
242109467b48Spatrick }
242209467b48Spatrick ValueToExpression[I] = E;
242309467b48Spatrick }
242409467b48Spatrick
242509467b48Spatrick // Process the fact that Edge (from, to) is reachable, including marking
242609467b48Spatrick // any newly reachable blocks and instructions for processing.
updateReachableEdge(BasicBlock * From,BasicBlock * To)242709467b48Spatrick void NewGVN::updateReachableEdge(BasicBlock *From, BasicBlock *To) {
242809467b48Spatrick // Check if the Edge was reachable before.
242909467b48Spatrick if (ReachableEdges.insert({From, To}).second) {
243009467b48Spatrick // If this block wasn't reachable before, all instructions are touched.
243109467b48Spatrick if (ReachableBlocks.insert(To).second) {
243209467b48Spatrick LLVM_DEBUG(dbgs() << "Block " << getBlockName(To)
243309467b48Spatrick << " marked reachable\n");
243409467b48Spatrick const auto &InstRange = BlockInstRange.lookup(To);
243509467b48Spatrick TouchedInstructions.set(InstRange.first, InstRange.second);
243609467b48Spatrick } else {
243709467b48Spatrick LLVM_DEBUG(dbgs() << "Block " << getBlockName(To)
243809467b48Spatrick << " was reachable, but new edge {"
243909467b48Spatrick << getBlockName(From) << "," << getBlockName(To)
244009467b48Spatrick << "} to it found\n");
244109467b48Spatrick
244209467b48Spatrick // We've made an edge reachable to an existing block, which may
244309467b48Spatrick // impact predicates. Otherwise, only mark the phi nodes as touched, as
244409467b48Spatrick // they are the only thing that depend on new edges. Anything using their
244509467b48Spatrick // values will get propagated to if necessary.
244609467b48Spatrick if (MemoryAccess *MemPhi = getMemoryAccess(To))
244709467b48Spatrick TouchedInstructions.set(InstrToDFSNum(MemPhi));
244809467b48Spatrick
244909467b48Spatrick // FIXME: We should just add a union op on a Bitvector and
245009467b48Spatrick // SparseBitVector. We can do it word by word faster than we are doing it
245109467b48Spatrick // here.
245209467b48Spatrick for (auto InstNum : RevisitOnReachabilityChange[To])
245309467b48Spatrick TouchedInstructions.set(InstNum);
245409467b48Spatrick }
245509467b48Spatrick }
245609467b48Spatrick }
245709467b48Spatrick
245809467b48Spatrick // Given a predicate condition (from a switch, cmp, or whatever) and a block,
245909467b48Spatrick // see if we know some constant value for it already.
findConditionEquivalence(Value * Cond) const246009467b48Spatrick Value *NewGVN::findConditionEquivalence(Value *Cond) const {
246109467b48Spatrick auto Result = lookupOperandLeader(Cond);
246209467b48Spatrick return isa<Constant>(Result) ? Result : nullptr;
246309467b48Spatrick }
246409467b48Spatrick
246509467b48Spatrick // Process the outgoing edges of a block for reachability.
processOutgoingEdges(Instruction * TI,BasicBlock * B)246609467b48Spatrick void NewGVN::processOutgoingEdges(Instruction *TI, BasicBlock *B) {
246709467b48Spatrick // Evaluate reachability of terminator instruction.
246809467b48Spatrick Value *Cond;
246909467b48Spatrick BasicBlock *TrueSucc, *FalseSucc;
247009467b48Spatrick if (match(TI, m_Br(m_Value(Cond), TrueSucc, FalseSucc))) {
247109467b48Spatrick Value *CondEvaluated = findConditionEquivalence(Cond);
247209467b48Spatrick if (!CondEvaluated) {
247309467b48Spatrick if (auto *I = dyn_cast<Instruction>(Cond)) {
247473471bf0Spatrick SmallPtrSet<Value *, 4> Visited;
247573471bf0Spatrick auto Res = performSymbolicEvaluation(I, Visited);
247673471bf0Spatrick if (const auto *CE = dyn_cast_or_null<ConstantExpression>(Res.Expr)) {
247709467b48Spatrick CondEvaluated = CE->getConstantValue();
247873471bf0Spatrick addAdditionalUsers(Res, I);
247973471bf0Spatrick } else {
248073471bf0Spatrick // Did not use simplification result, no need to add the extra
248173471bf0Spatrick // dependency.
248273471bf0Spatrick Res.ExtraDep = nullptr;
248309467b48Spatrick }
248409467b48Spatrick } else if (isa<ConstantInt>(Cond)) {
248509467b48Spatrick CondEvaluated = Cond;
248609467b48Spatrick }
248709467b48Spatrick }
248809467b48Spatrick ConstantInt *CI;
248909467b48Spatrick if (CondEvaluated && (CI = dyn_cast<ConstantInt>(CondEvaluated))) {
249009467b48Spatrick if (CI->isOne()) {
249109467b48Spatrick LLVM_DEBUG(dbgs() << "Condition for Terminator " << *TI
249209467b48Spatrick << " evaluated to true\n");
249309467b48Spatrick updateReachableEdge(B, TrueSucc);
249409467b48Spatrick } else if (CI->isZero()) {
249509467b48Spatrick LLVM_DEBUG(dbgs() << "Condition for Terminator " << *TI
249609467b48Spatrick << " evaluated to false\n");
249709467b48Spatrick updateReachableEdge(B, FalseSucc);
249809467b48Spatrick }
249909467b48Spatrick } else {
250009467b48Spatrick updateReachableEdge(B, TrueSucc);
250109467b48Spatrick updateReachableEdge(B, FalseSucc);
250209467b48Spatrick }
250309467b48Spatrick } else if (auto *SI = dyn_cast<SwitchInst>(TI)) {
250409467b48Spatrick // For switches, propagate the case values into the case
250509467b48Spatrick // destinations.
250609467b48Spatrick
250709467b48Spatrick Value *SwitchCond = SI->getCondition();
250809467b48Spatrick Value *CondEvaluated = findConditionEquivalence(SwitchCond);
250909467b48Spatrick // See if we were able to turn this switch statement into a constant.
251009467b48Spatrick if (CondEvaluated && isa<ConstantInt>(CondEvaluated)) {
251109467b48Spatrick auto *CondVal = cast<ConstantInt>(CondEvaluated);
251209467b48Spatrick // We should be able to get case value for this.
251309467b48Spatrick auto Case = *SI->findCaseValue(CondVal);
251409467b48Spatrick if (Case.getCaseSuccessor() == SI->getDefaultDest()) {
251509467b48Spatrick // We proved the value is outside of the range of the case.
251609467b48Spatrick // We can't do anything other than mark the default dest as reachable,
251709467b48Spatrick // and go home.
251809467b48Spatrick updateReachableEdge(B, SI->getDefaultDest());
251909467b48Spatrick return;
252009467b48Spatrick }
252109467b48Spatrick // Now get where it goes and mark it reachable.
252209467b48Spatrick BasicBlock *TargetBlock = Case.getCaseSuccessor();
252309467b48Spatrick updateReachableEdge(B, TargetBlock);
252409467b48Spatrick } else {
252509467b48Spatrick for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
252609467b48Spatrick BasicBlock *TargetBlock = SI->getSuccessor(i);
252709467b48Spatrick updateReachableEdge(B, TargetBlock);
252809467b48Spatrick }
252909467b48Spatrick }
253009467b48Spatrick } else {
253109467b48Spatrick // Otherwise this is either unconditional, or a type we have no
253209467b48Spatrick // idea about. Just mark successors as reachable.
253309467b48Spatrick for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
253409467b48Spatrick BasicBlock *TargetBlock = TI->getSuccessor(i);
253509467b48Spatrick updateReachableEdge(B, TargetBlock);
253609467b48Spatrick }
253709467b48Spatrick
253809467b48Spatrick // This also may be a memory defining terminator, in which case, set it
253909467b48Spatrick // equivalent only to itself.
254009467b48Spatrick //
254109467b48Spatrick auto *MA = getMemoryAccess(TI);
254209467b48Spatrick if (MA && !isa<MemoryUse>(MA)) {
254309467b48Spatrick auto *CC = ensureLeaderOfMemoryClass(MA);
254409467b48Spatrick if (setMemoryClass(MA, CC))
254509467b48Spatrick markMemoryUsersTouched(MA);
254609467b48Spatrick }
254709467b48Spatrick }
254809467b48Spatrick }
254909467b48Spatrick
255009467b48Spatrick // Remove the PHI of Ops PHI for I
removePhiOfOps(Instruction * I,PHINode * PHITemp)255109467b48Spatrick void NewGVN::removePhiOfOps(Instruction *I, PHINode *PHITemp) {
255209467b48Spatrick InstrDFS.erase(PHITemp);
255309467b48Spatrick // It's still a temp instruction. We keep it in the array so it gets erased.
255409467b48Spatrick // However, it's no longer used by I, or in the block
255509467b48Spatrick TempToBlock.erase(PHITemp);
255609467b48Spatrick RealToTemp.erase(I);
255709467b48Spatrick // We don't remove the users from the phi node uses. This wastes a little
255809467b48Spatrick // time, but such is life. We could use two sets to track which were there
255909467b48Spatrick // are the start of NewGVN, and which were added, but right nowt he cost of
256009467b48Spatrick // tracking is more than the cost of checking for more phi of ops.
256109467b48Spatrick }
256209467b48Spatrick
256309467b48Spatrick // Add PHI Op in BB as a PHI of operations version of ExistingValue.
addPhiOfOps(PHINode * Op,BasicBlock * BB,Instruction * ExistingValue)256409467b48Spatrick void NewGVN::addPhiOfOps(PHINode *Op, BasicBlock *BB,
256509467b48Spatrick Instruction *ExistingValue) {
256609467b48Spatrick InstrDFS[Op] = InstrToDFSNum(ExistingValue);
256709467b48Spatrick AllTempInstructions.insert(Op);
256809467b48Spatrick TempToBlock[Op] = BB;
256909467b48Spatrick RealToTemp[ExistingValue] = Op;
257009467b48Spatrick // Add all users to phi node use, as they are now uses of the phi of ops phis
257109467b48Spatrick // and may themselves be phi of ops.
257209467b48Spatrick for (auto *U : ExistingValue->users())
257309467b48Spatrick if (auto *UI = dyn_cast<Instruction>(U))
257409467b48Spatrick PHINodeUses.insert(UI);
257509467b48Spatrick }
257609467b48Spatrick
okayForPHIOfOps(const Instruction * I)257709467b48Spatrick static bool okayForPHIOfOps(const Instruction *I) {
257809467b48Spatrick if (!EnablePhiOfOps)
257909467b48Spatrick return false;
258009467b48Spatrick return isa<BinaryOperator>(I) || isa<SelectInst>(I) || isa<CmpInst>(I) ||
258109467b48Spatrick isa<LoadInst>(I);
258209467b48Spatrick }
258309467b48Spatrick
258409467b48Spatrick // Return true if this operand will be safe to use for phi of ops.
258509467b48Spatrick //
258609467b48Spatrick // The reason some operands are unsafe is that we are not trying to recursively
258709467b48Spatrick // translate everything back through phi nodes. We actually expect some lookups
258809467b48Spatrick // of expressions to fail. In particular, a lookup where the expression cannot
258909467b48Spatrick // exist in the predecessor. This is true even if the expression, as shown, can
259009467b48Spatrick // be determined to be constant.
OpIsSafeForPHIOfOps(Value * V,const BasicBlock * PHIBlock,SmallPtrSetImpl<const Value * > & Visited)259109467b48Spatrick bool NewGVN::OpIsSafeForPHIOfOps(Value *V, const BasicBlock *PHIBlock,
259209467b48Spatrick SmallPtrSetImpl<const Value *> &Visited) {
2593*d415bd75Srobert SmallVector<Value *, 4> Worklist;
2594*d415bd75Srobert Worklist.push_back(V);
259509467b48Spatrick while (!Worklist.empty()) {
259609467b48Spatrick auto *I = Worklist.pop_back_val();
2597*d415bd75Srobert if (!isa<Instruction>(I))
2598*d415bd75Srobert continue;
2599*d415bd75Srobert
2600*d415bd75Srobert auto OISIt = OpSafeForPHIOfOps.find(I);
2601*d415bd75Srobert if (OISIt != OpSafeForPHIOfOps.end())
2602*d415bd75Srobert return OISIt->second;
2603*d415bd75Srobert
2604*d415bd75Srobert // Keep walking until we either dominate the phi block, or hit a phi, or run
2605*d415bd75Srobert // out of things to check.
2606*d415bd75Srobert if (DT->properlyDominates(getBlockForValue(I), PHIBlock)) {
2607*d415bd75Srobert OpSafeForPHIOfOps.insert({I, true});
2608*d415bd75Srobert continue;
2609*d415bd75Srobert }
2610*d415bd75Srobert // PHI in the same block.
2611*d415bd75Srobert if (isa<PHINode>(I) && getBlockForValue(I) == PHIBlock) {
2612*d415bd75Srobert OpSafeForPHIOfOps.insert({I, false});
261309467b48Spatrick return false;
261409467b48Spatrick }
2615*d415bd75Srobert
2616*d415bd75Srobert auto *OrigI = cast<Instruction>(I);
2617*d415bd75Srobert // When we hit an instruction that reads memory (load, call, etc), we must
2618*d415bd75Srobert // consider any store that may happen in the loop. For now, we assume the
2619*d415bd75Srobert // worst: there is a store in the loop that alias with this read.
2620*d415bd75Srobert // The case where the load is outside the loop is already covered by the
2621*d415bd75Srobert // dominator check above.
2622*d415bd75Srobert // TODO: relax this condition
2623*d415bd75Srobert if (OrigI->mayReadFromMemory())
2624*d415bd75Srobert return false;
2625*d415bd75Srobert
2626*d415bd75Srobert // Check the operands of the current instruction.
2627*d415bd75Srobert for (auto *Op : OrigI->operand_values()) {
2628*d415bd75Srobert if (!isa<Instruction>(Op))
2629*d415bd75Srobert continue;
2630*d415bd75Srobert // Stop now if we find an unsafe operand.
2631*d415bd75Srobert auto OISIt = OpSafeForPHIOfOps.find(OrigI);
2632*d415bd75Srobert if (OISIt != OpSafeForPHIOfOps.end()) {
2633*d415bd75Srobert if (!OISIt->second) {
2634*d415bd75Srobert OpSafeForPHIOfOps.insert({I, false});
2635*d415bd75Srobert return false;
2636*d415bd75Srobert }
2637*d415bd75Srobert continue;
2638*d415bd75Srobert }
2639*d415bd75Srobert if (!Visited.insert(Op).second)
2640*d415bd75Srobert continue;
2641*d415bd75Srobert Worklist.push_back(cast<Instruction>(Op));
2642*d415bd75Srobert }
2643*d415bd75Srobert }
264409467b48Spatrick OpSafeForPHIOfOps.insert({V, true});
264509467b48Spatrick return true;
264609467b48Spatrick }
264709467b48Spatrick
264809467b48Spatrick // Try to find a leader for instruction TransInst, which is a phi translated
264909467b48Spatrick // version of something in our original program. Visited is used to ensure we
265009467b48Spatrick // don't infinite loop during translations of cycles. OrigInst is the
265109467b48Spatrick // instruction in the original program, and PredBB is the predecessor we
265209467b48Spatrick // translated it through.
findLeaderForInst(Instruction * TransInst,SmallPtrSetImpl<Value * > & Visited,MemoryAccess * MemAccess,Instruction * OrigInst,BasicBlock * PredBB)265309467b48Spatrick Value *NewGVN::findLeaderForInst(Instruction *TransInst,
265409467b48Spatrick SmallPtrSetImpl<Value *> &Visited,
265509467b48Spatrick MemoryAccess *MemAccess, Instruction *OrigInst,
265609467b48Spatrick BasicBlock *PredBB) {
265709467b48Spatrick unsigned IDFSNum = InstrToDFSNum(OrigInst);
265809467b48Spatrick // Make sure it's marked as a temporary instruction.
265909467b48Spatrick AllTempInstructions.insert(TransInst);
266009467b48Spatrick // and make sure anything that tries to add it's DFS number is
266109467b48Spatrick // redirected to the instruction we are making a phi of ops
266209467b48Spatrick // for.
266309467b48Spatrick TempToBlock.insert({TransInst, PredBB});
266409467b48Spatrick InstrDFS.insert({TransInst, IDFSNum});
266509467b48Spatrick
266673471bf0Spatrick auto Res = performSymbolicEvaluation(TransInst, Visited);
266773471bf0Spatrick const Expression *E = Res.Expr;
266873471bf0Spatrick addAdditionalUsers(Res, OrigInst);
266909467b48Spatrick InstrDFS.erase(TransInst);
267009467b48Spatrick AllTempInstructions.erase(TransInst);
267109467b48Spatrick TempToBlock.erase(TransInst);
267209467b48Spatrick if (MemAccess)
267309467b48Spatrick TempToMemory.erase(TransInst);
267409467b48Spatrick if (!E)
267509467b48Spatrick return nullptr;
267609467b48Spatrick auto *FoundVal = findPHIOfOpsLeader(E, OrigInst, PredBB);
267709467b48Spatrick if (!FoundVal) {
267809467b48Spatrick ExpressionToPhiOfOps[E].insert(OrigInst);
267909467b48Spatrick LLVM_DEBUG(dbgs() << "Cannot find phi of ops operand for " << *TransInst
268009467b48Spatrick << " in block " << getBlockName(PredBB) << "\n");
268109467b48Spatrick return nullptr;
268209467b48Spatrick }
268309467b48Spatrick if (auto *SI = dyn_cast<StoreInst>(FoundVal))
268409467b48Spatrick FoundVal = SI->getValueOperand();
268509467b48Spatrick return FoundVal;
268609467b48Spatrick }
268709467b48Spatrick
268809467b48Spatrick // When we see an instruction that is an op of phis, generate the equivalent phi
268909467b48Spatrick // of ops form.
269009467b48Spatrick const Expression *
makePossiblePHIOfOps(Instruction * I,SmallPtrSetImpl<Value * > & Visited)269109467b48Spatrick NewGVN::makePossiblePHIOfOps(Instruction *I,
269209467b48Spatrick SmallPtrSetImpl<Value *> &Visited) {
269309467b48Spatrick if (!okayForPHIOfOps(I))
269409467b48Spatrick return nullptr;
269509467b48Spatrick
269609467b48Spatrick if (!Visited.insert(I).second)
269709467b48Spatrick return nullptr;
269809467b48Spatrick // For now, we require the instruction be cycle free because we don't
269909467b48Spatrick // *always* create a phi of ops for instructions that could be done as phi
270009467b48Spatrick // of ops, we only do it if we think it is useful. If we did do it all the
270109467b48Spatrick // time, we could remove the cycle free check.
270209467b48Spatrick if (!isCycleFree(I))
270309467b48Spatrick return nullptr;
270409467b48Spatrick
270509467b48Spatrick SmallPtrSet<const Value *, 8> ProcessedPHIs;
270609467b48Spatrick // TODO: We don't do phi translation on memory accesses because it's
270709467b48Spatrick // complicated. For a load, we'd need to be able to simulate a new memoryuse,
270809467b48Spatrick // which we don't have a good way of doing ATM.
270909467b48Spatrick auto *MemAccess = getMemoryAccess(I);
271009467b48Spatrick // If the memory operation is defined by a memory operation this block that
271109467b48Spatrick // isn't a MemoryPhi, transforming the pointer backwards through a scalar phi
271209467b48Spatrick // can't help, as it would still be killed by that memory operation.
271309467b48Spatrick if (MemAccess && !isa<MemoryPhi>(MemAccess->getDefiningAccess()) &&
271409467b48Spatrick MemAccess->getDefiningAccess()->getBlock() == I->getParent())
271509467b48Spatrick return nullptr;
271609467b48Spatrick
271709467b48Spatrick // Convert op of phis to phi of ops
271809467b48Spatrick SmallPtrSet<const Value *, 10> VisitedOps;
271909467b48Spatrick SmallVector<Value *, 4> Ops(I->operand_values());
272009467b48Spatrick BasicBlock *SamePHIBlock = nullptr;
272109467b48Spatrick PHINode *OpPHI = nullptr;
272209467b48Spatrick if (!DebugCounter::shouldExecute(PHIOfOpsCounter))
272309467b48Spatrick return nullptr;
272409467b48Spatrick for (auto *Op : Ops) {
272509467b48Spatrick if (!isa<PHINode>(Op)) {
272609467b48Spatrick auto *ValuePHI = RealToTemp.lookup(Op);
272709467b48Spatrick if (!ValuePHI)
272809467b48Spatrick continue;
272909467b48Spatrick LLVM_DEBUG(dbgs() << "Found possible dependent phi of ops\n");
273009467b48Spatrick Op = ValuePHI;
273109467b48Spatrick }
273209467b48Spatrick OpPHI = cast<PHINode>(Op);
273309467b48Spatrick if (!SamePHIBlock) {
273409467b48Spatrick SamePHIBlock = getBlockForValue(OpPHI);
273509467b48Spatrick } else if (SamePHIBlock != getBlockForValue(OpPHI)) {
273609467b48Spatrick LLVM_DEBUG(
273709467b48Spatrick dbgs()
273809467b48Spatrick << "PHIs for operands are not all in the same block, aborting\n");
273909467b48Spatrick return nullptr;
274009467b48Spatrick }
274109467b48Spatrick // No point in doing this for one-operand phis.
274209467b48Spatrick if (OpPHI->getNumOperands() == 1) {
274309467b48Spatrick OpPHI = nullptr;
274409467b48Spatrick continue;
274509467b48Spatrick }
274609467b48Spatrick }
274709467b48Spatrick
274809467b48Spatrick if (!OpPHI)
274909467b48Spatrick return nullptr;
275009467b48Spatrick
275109467b48Spatrick SmallVector<ValPair, 4> PHIOps;
275209467b48Spatrick SmallPtrSet<Value *, 4> Deps;
275309467b48Spatrick auto *PHIBlock = getBlockForValue(OpPHI);
275409467b48Spatrick RevisitOnReachabilityChange[PHIBlock].reset(InstrToDFSNum(I));
275509467b48Spatrick for (unsigned PredNum = 0; PredNum < OpPHI->getNumOperands(); ++PredNum) {
275609467b48Spatrick auto *PredBB = OpPHI->getIncomingBlock(PredNum);
275709467b48Spatrick Value *FoundVal = nullptr;
275809467b48Spatrick SmallPtrSet<Value *, 4> CurrentDeps;
275909467b48Spatrick // We could just skip unreachable edges entirely but it's tricky to do
276009467b48Spatrick // with rewriting existing phi nodes.
276109467b48Spatrick if (ReachableEdges.count({PredBB, PHIBlock})) {
276209467b48Spatrick // Clone the instruction, create an expression from it that is
276309467b48Spatrick // translated back into the predecessor, and see if we have a leader.
276409467b48Spatrick Instruction *ValueOp = I->clone();
276509467b48Spatrick if (MemAccess)
276609467b48Spatrick TempToMemory.insert({ValueOp, MemAccess});
276709467b48Spatrick bool SafeForPHIOfOps = true;
276809467b48Spatrick VisitedOps.clear();
276909467b48Spatrick for (auto &Op : ValueOp->operands()) {
277009467b48Spatrick auto *OrigOp = &*Op;
277109467b48Spatrick // When these operand changes, it could change whether there is a
277209467b48Spatrick // leader for us or not, so we have to add additional users.
277309467b48Spatrick if (isa<PHINode>(Op)) {
277409467b48Spatrick Op = Op->DoPHITranslation(PHIBlock, PredBB);
277509467b48Spatrick if (Op != OrigOp && Op != I)
277609467b48Spatrick CurrentDeps.insert(Op);
277709467b48Spatrick } else if (auto *ValuePHI = RealToTemp.lookup(Op)) {
277809467b48Spatrick if (getBlockForValue(ValuePHI) == PHIBlock)
277909467b48Spatrick Op = ValuePHI->getIncomingValueForBlock(PredBB);
278009467b48Spatrick }
278109467b48Spatrick // If we phi-translated the op, it must be safe.
278209467b48Spatrick SafeForPHIOfOps =
278309467b48Spatrick SafeForPHIOfOps &&
278409467b48Spatrick (Op != OrigOp || OpIsSafeForPHIOfOps(Op, PHIBlock, VisitedOps));
278509467b48Spatrick }
278609467b48Spatrick // FIXME: For those things that are not safe we could generate
278709467b48Spatrick // expressions all the way down, and see if this comes out to a
278809467b48Spatrick // constant. For anything where that is true, and unsafe, we should
278909467b48Spatrick // have made a phi-of-ops (or value numbered it equivalent to something)
279009467b48Spatrick // for the pieces already.
279109467b48Spatrick FoundVal = !SafeForPHIOfOps ? nullptr
279209467b48Spatrick : findLeaderForInst(ValueOp, Visited,
279309467b48Spatrick MemAccess, I, PredBB);
279409467b48Spatrick ValueOp->deleteValue();
279509467b48Spatrick if (!FoundVal) {
279609467b48Spatrick // We failed to find a leader for the current ValueOp, but this might
279709467b48Spatrick // change in case of the translated operands change.
279809467b48Spatrick if (SafeForPHIOfOps)
2799*d415bd75Srobert for (auto *Dep : CurrentDeps)
280009467b48Spatrick addAdditionalUsers(Dep, I);
280109467b48Spatrick
280209467b48Spatrick return nullptr;
280309467b48Spatrick }
280409467b48Spatrick Deps.insert(CurrentDeps.begin(), CurrentDeps.end());
280509467b48Spatrick } else {
280609467b48Spatrick LLVM_DEBUG(dbgs() << "Skipping phi of ops operand for incoming block "
280709467b48Spatrick << getBlockName(PredBB)
280809467b48Spatrick << " because the block is unreachable\n");
2809*d415bd75Srobert FoundVal = PoisonValue::get(I->getType());
281009467b48Spatrick RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(I));
281109467b48Spatrick }
281209467b48Spatrick
281309467b48Spatrick PHIOps.push_back({FoundVal, PredBB});
281409467b48Spatrick LLVM_DEBUG(dbgs() << "Found phi of ops operand " << *FoundVal << " in "
281509467b48Spatrick << getBlockName(PredBB) << "\n");
281609467b48Spatrick }
2817*d415bd75Srobert for (auto *Dep : Deps)
281809467b48Spatrick addAdditionalUsers(Dep, I);
281909467b48Spatrick sortPHIOps(PHIOps);
282009467b48Spatrick auto *E = performSymbolicPHIEvaluation(PHIOps, I, PHIBlock);
282109467b48Spatrick if (isa<ConstantExpression>(E) || isa<VariableExpression>(E)) {
282209467b48Spatrick LLVM_DEBUG(
282309467b48Spatrick dbgs()
282409467b48Spatrick << "Not creating real PHI of ops because it simplified to existing "
282509467b48Spatrick "value or constant\n");
282673471bf0Spatrick // We have leaders for all operands, but do not create a real PHI node with
282773471bf0Spatrick // those leaders as operands, so the link between the operands and the
282873471bf0Spatrick // PHI-of-ops is not materialized in the IR. If any of those leaders
282973471bf0Spatrick // changes, the PHI-of-op may change also, so we need to add the operands as
283073471bf0Spatrick // additional users.
283173471bf0Spatrick for (auto &O : PHIOps)
283273471bf0Spatrick addAdditionalUsers(O.first, I);
283373471bf0Spatrick
283409467b48Spatrick return E;
283509467b48Spatrick }
283609467b48Spatrick auto *ValuePHI = RealToTemp.lookup(I);
283709467b48Spatrick bool NewPHI = false;
283809467b48Spatrick if (!ValuePHI) {
283909467b48Spatrick ValuePHI =
284009467b48Spatrick PHINode::Create(I->getType(), OpPHI->getNumOperands(), "phiofops");
284109467b48Spatrick addPhiOfOps(ValuePHI, PHIBlock, I);
284209467b48Spatrick NewPHI = true;
284309467b48Spatrick NumGVNPHIOfOpsCreated++;
284409467b48Spatrick }
284509467b48Spatrick if (NewPHI) {
284609467b48Spatrick for (auto PHIOp : PHIOps)
284709467b48Spatrick ValuePHI->addIncoming(PHIOp.first, PHIOp.second);
284809467b48Spatrick } else {
284909467b48Spatrick TempToBlock[ValuePHI] = PHIBlock;
285009467b48Spatrick unsigned int i = 0;
285109467b48Spatrick for (auto PHIOp : PHIOps) {
285209467b48Spatrick ValuePHI->setIncomingValue(i, PHIOp.first);
285309467b48Spatrick ValuePHI->setIncomingBlock(i, PHIOp.second);
285409467b48Spatrick ++i;
285509467b48Spatrick }
285609467b48Spatrick }
285709467b48Spatrick RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(I));
285809467b48Spatrick LLVM_DEBUG(dbgs() << "Created phi of ops " << *ValuePHI << " for " << *I
285909467b48Spatrick << "\n");
286009467b48Spatrick
286109467b48Spatrick return E;
286209467b48Spatrick }
286309467b48Spatrick
286409467b48Spatrick // The algorithm initially places the values of the routine in the TOP
2865*d415bd75Srobert // congruence class. The leader of TOP is the undetermined value `poison`.
286609467b48Spatrick // When the algorithm has finished, values still in TOP are unreachable.
initializeCongruenceClasses(Function & F)286709467b48Spatrick void NewGVN::initializeCongruenceClasses(Function &F) {
286809467b48Spatrick NextCongruenceNum = 0;
286909467b48Spatrick
287009467b48Spatrick // Note that even though we use the live on entry def as a representative
287109467b48Spatrick // MemoryAccess, it is *not* the same as the actual live on entry def. We
2872*d415bd75Srobert // have no real equivalent to poison for MemoryAccesses, and so we really
287309467b48Spatrick // should be checking whether the MemoryAccess is top if we want to know if it
287409467b48Spatrick // is equivalent to everything. Otherwise, what this really signifies is that
287509467b48Spatrick // the access "it reaches all the way back to the beginning of the function"
287609467b48Spatrick
287709467b48Spatrick // Initialize all other instructions to be in TOP class.
287809467b48Spatrick TOPClass = createCongruenceClass(nullptr, nullptr);
287909467b48Spatrick TOPClass->setMemoryLeader(MSSA->getLiveOnEntryDef());
288009467b48Spatrick // The live on entry def gets put into it's own class
288109467b48Spatrick MemoryAccessToClass[MSSA->getLiveOnEntryDef()] =
288209467b48Spatrick createMemoryClass(MSSA->getLiveOnEntryDef());
288309467b48Spatrick
2884*d415bd75Srobert for (auto *DTN : nodes(DT)) {
288509467b48Spatrick BasicBlock *BB = DTN->getBlock();
288609467b48Spatrick // All MemoryAccesses are equivalent to live on entry to start. They must
288709467b48Spatrick // be initialized to something so that initial changes are noticed. For
288809467b48Spatrick // the maximal answer, we initialize them all to be the same as
288909467b48Spatrick // liveOnEntry.
289009467b48Spatrick auto *MemoryBlockDefs = MSSA->getBlockDefs(BB);
289109467b48Spatrick if (MemoryBlockDefs)
289209467b48Spatrick for (const auto &Def : *MemoryBlockDefs) {
289309467b48Spatrick MemoryAccessToClass[&Def] = TOPClass;
289409467b48Spatrick auto *MD = dyn_cast<MemoryDef>(&Def);
289509467b48Spatrick // Insert the memory phis into the member list.
289609467b48Spatrick if (!MD) {
289709467b48Spatrick const MemoryPhi *MP = cast<MemoryPhi>(&Def);
289809467b48Spatrick TOPClass->memory_insert(MP);
289909467b48Spatrick MemoryPhiState.insert({MP, MPS_TOP});
290009467b48Spatrick }
290109467b48Spatrick
290209467b48Spatrick if (MD && isa<StoreInst>(MD->getMemoryInst()))
290309467b48Spatrick TOPClass->incStoreCount();
290409467b48Spatrick }
290509467b48Spatrick
290609467b48Spatrick // FIXME: This is trying to discover which instructions are uses of phi
290709467b48Spatrick // nodes. We should move this into one of the myriad of places that walk
290809467b48Spatrick // all the operands already.
290909467b48Spatrick for (auto &I : *BB) {
291009467b48Spatrick if (isa<PHINode>(&I))
291109467b48Spatrick for (auto *U : I.users())
291209467b48Spatrick if (auto *UInst = dyn_cast<Instruction>(U))
291309467b48Spatrick if (InstrToDFSNum(UInst) != 0 && okayForPHIOfOps(UInst))
291409467b48Spatrick PHINodeUses.insert(UInst);
291509467b48Spatrick // Don't insert void terminators into the class. We don't value number
291609467b48Spatrick // them, and they just end up sitting in TOP.
291709467b48Spatrick if (I.isTerminator() && I.getType()->isVoidTy())
291809467b48Spatrick continue;
291909467b48Spatrick TOPClass->insert(&I);
292009467b48Spatrick ValueToClass[&I] = TOPClass;
292109467b48Spatrick }
292209467b48Spatrick }
292309467b48Spatrick
292409467b48Spatrick // Initialize arguments to be in their own unique congruence classes
292509467b48Spatrick for (auto &FA : F.args())
292609467b48Spatrick createSingletonCongruenceClass(&FA);
292709467b48Spatrick }
292809467b48Spatrick
cleanupTables()292909467b48Spatrick void NewGVN::cleanupTables() {
2930*d415bd75Srobert for (CongruenceClass *&CC : CongruenceClasses) {
2931*d415bd75Srobert LLVM_DEBUG(dbgs() << "Congruence class " << CC->getID() << " has "
2932*d415bd75Srobert << CC->size() << " members\n");
293309467b48Spatrick // Make sure we delete the congruence class (probably worth switching to
293409467b48Spatrick // a unique_ptr at some point.
2935*d415bd75Srobert delete CC;
2936*d415bd75Srobert CC = nullptr;
293709467b48Spatrick }
293809467b48Spatrick
293909467b48Spatrick // Destroy the value expressions
294009467b48Spatrick SmallVector<Instruction *, 8> TempInst(AllTempInstructions.begin(),
294109467b48Spatrick AllTempInstructions.end());
294209467b48Spatrick AllTempInstructions.clear();
294309467b48Spatrick
294409467b48Spatrick // We have to drop all references for everything first, so there are no uses
294509467b48Spatrick // left as we delete them.
294609467b48Spatrick for (auto *I : TempInst) {
294709467b48Spatrick I->dropAllReferences();
294809467b48Spatrick }
294909467b48Spatrick
295009467b48Spatrick while (!TempInst.empty()) {
295173471bf0Spatrick auto *I = TempInst.pop_back_val();
295209467b48Spatrick I->deleteValue();
295309467b48Spatrick }
295409467b48Spatrick
295509467b48Spatrick ValueToClass.clear();
295609467b48Spatrick ArgRecycler.clear(ExpressionAllocator);
295709467b48Spatrick ExpressionAllocator.Reset();
295809467b48Spatrick CongruenceClasses.clear();
295909467b48Spatrick ExpressionToClass.clear();
296009467b48Spatrick ValueToExpression.clear();
296109467b48Spatrick RealToTemp.clear();
296209467b48Spatrick AdditionalUsers.clear();
296309467b48Spatrick ExpressionToPhiOfOps.clear();
296409467b48Spatrick TempToBlock.clear();
296509467b48Spatrick TempToMemory.clear();
296609467b48Spatrick PHINodeUses.clear();
296709467b48Spatrick OpSafeForPHIOfOps.clear();
296809467b48Spatrick ReachableBlocks.clear();
296909467b48Spatrick ReachableEdges.clear();
297009467b48Spatrick #ifndef NDEBUG
297109467b48Spatrick ProcessedCount.clear();
297209467b48Spatrick #endif
297309467b48Spatrick InstrDFS.clear();
297409467b48Spatrick InstructionsToErase.clear();
297509467b48Spatrick DFSToInstr.clear();
297609467b48Spatrick BlockInstRange.clear();
297709467b48Spatrick TouchedInstructions.clear();
297809467b48Spatrick MemoryAccessToClass.clear();
297909467b48Spatrick PredicateToUsers.clear();
298009467b48Spatrick MemoryToUsers.clear();
298109467b48Spatrick RevisitOnReachabilityChange.clear();
2982*d415bd75Srobert IntrinsicInstPred.clear();
298309467b48Spatrick }
298409467b48Spatrick
298509467b48Spatrick // Assign local DFS number mapping to instructions, and leave space for Value
298609467b48Spatrick // PHI's.
assignDFSNumbers(BasicBlock * B,unsigned Start)298709467b48Spatrick std::pair<unsigned, unsigned> NewGVN::assignDFSNumbers(BasicBlock *B,
298809467b48Spatrick unsigned Start) {
298909467b48Spatrick unsigned End = Start;
299009467b48Spatrick if (MemoryAccess *MemPhi = getMemoryAccess(B)) {
299109467b48Spatrick InstrDFS[MemPhi] = End++;
299209467b48Spatrick DFSToInstr.emplace_back(MemPhi);
299309467b48Spatrick }
299409467b48Spatrick
299509467b48Spatrick // Then the real block goes next.
299609467b48Spatrick for (auto &I : *B) {
299709467b48Spatrick // There's no need to call isInstructionTriviallyDead more than once on
299809467b48Spatrick // an instruction. Therefore, once we know that an instruction is dead
299909467b48Spatrick // we change its DFS number so that it doesn't get value numbered.
300009467b48Spatrick if (isInstructionTriviallyDead(&I, TLI)) {
300109467b48Spatrick InstrDFS[&I] = 0;
300209467b48Spatrick LLVM_DEBUG(dbgs() << "Skipping trivially dead instruction " << I << "\n");
300309467b48Spatrick markInstructionForDeletion(&I);
300409467b48Spatrick continue;
300509467b48Spatrick }
300609467b48Spatrick if (isa<PHINode>(&I))
300709467b48Spatrick RevisitOnReachabilityChange[B].set(End);
300809467b48Spatrick InstrDFS[&I] = End++;
300909467b48Spatrick DFSToInstr.emplace_back(&I);
301009467b48Spatrick }
301109467b48Spatrick
301209467b48Spatrick // All of the range functions taken half-open ranges (open on the end side).
301309467b48Spatrick // So we do not subtract one from count, because at this point it is one
301409467b48Spatrick // greater than the last instruction.
301509467b48Spatrick return std::make_pair(Start, End);
301609467b48Spatrick }
301709467b48Spatrick
updateProcessedCount(const Value * V)301809467b48Spatrick void NewGVN::updateProcessedCount(const Value *V) {
301909467b48Spatrick #ifndef NDEBUG
302009467b48Spatrick if (ProcessedCount.count(V) == 0) {
302109467b48Spatrick ProcessedCount.insert({V, 1});
302209467b48Spatrick } else {
302309467b48Spatrick ++ProcessedCount[V];
302409467b48Spatrick assert(ProcessedCount[V] < 100 &&
302509467b48Spatrick "Seem to have processed the same Value a lot");
302609467b48Spatrick }
302709467b48Spatrick #endif
302809467b48Spatrick }
302909467b48Spatrick
303009467b48Spatrick // Evaluate MemoryPhi nodes symbolically, just like PHI nodes
valueNumberMemoryPhi(MemoryPhi * MP)303109467b48Spatrick void NewGVN::valueNumberMemoryPhi(MemoryPhi *MP) {
303209467b48Spatrick // If all the arguments are the same, the MemoryPhi has the same value as the
303309467b48Spatrick // argument. Filter out unreachable blocks and self phis from our operands.
303409467b48Spatrick // TODO: We could do cycle-checking on the memory phis to allow valueizing for
303509467b48Spatrick // self-phi checking.
303609467b48Spatrick const BasicBlock *PHIBlock = MP->getBlock();
303709467b48Spatrick auto Filtered = make_filter_range(MP->operands(), [&](const Use &U) {
303809467b48Spatrick return cast<MemoryAccess>(U) != MP &&
303909467b48Spatrick !isMemoryAccessTOP(cast<MemoryAccess>(U)) &&
304009467b48Spatrick ReachableEdges.count({MP->getIncomingBlock(U), PHIBlock});
304109467b48Spatrick });
3042*d415bd75Srobert // If all that is left is nothing, our memoryphi is poison. We keep it as
304309467b48Spatrick // InitialClass. Note: The only case this should happen is if we have at
304409467b48Spatrick // least one self-argument.
304509467b48Spatrick if (Filtered.begin() == Filtered.end()) {
304609467b48Spatrick if (setMemoryClass(MP, TOPClass))
304709467b48Spatrick markMemoryUsersTouched(MP);
304809467b48Spatrick return;
304909467b48Spatrick }
305009467b48Spatrick
305109467b48Spatrick // Transform the remaining operands into operand leaders.
305209467b48Spatrick // FIXME: mapped_iterator should have a range version.
305309467b48Spatrick auto LookupFunc = [&](const Use &U) {
305409467b48Spatrick return lookupMemoryLeader(cast<MemoryAccess>(U));
305509467b48Spatrick };
305609467b48Spatrick auto MappedBegin = map_iterator(Filtered.begin(), LookupFunc);
305709467b48Spatrick auto MappedEnd = map_iterator(Filtered.end(), LookupFunc);
305809467b48Spatrick
305909467b48Spatrick // and now check if all the elements are equal.
306009467b48Spatrick // Sadly, we can't use std::equals since these are random access iterators.
306109467b48Spatrick const auto *AllSameValue = *MappedBegin;
306209467b48Spatrick ++MappedBegin;
306309467b48Spatrick bool AllEqual = std::all_of(
306409467b48Spatrick MappedBegin, MappedEnd,
306509467b48Spatrick [&AllSameValue](const MemoryAccess *V) { return V == AllSameValue; });
306609467b48Spatrick
306709467b48Spatrick if (AllEqual)
306809467b48Spatrick LLVM_DEBUG(dbgs() << "Memory Phi value numbered to " << *AllSameValue
306909467b48Spatrick << "\n");
307009467b48Spatrick else
307109467b48Spatrick LLVM_DEBUG(dbgs() << "Memory Phi value numbered to itself\n");
307209467b48Spatrick // If it's equal to something, it's in that class. Otherwise, it has to be in
307309467b48Spatrick // a class where it is the leader (other things may be equivalent to it, but
307409467b48Spatrick // it needs to start off in its own class, which means it must have been the
307509467b48Spatrick // leader, and it can't have stopped being the leader because it was never
307609467b48Spatrick // removed).
307709467b48Spatrick CongruenceClass *CC =
307809467b48Spatrick AllEqual ? getMemoryClass(AllSameValue) : ensureLeaderOfMemoryClass(MP);
307909467b48Spatrick auto OldState = MemoryPhiState.lookup(MP);
308009467b48Spatrick assert(OldState != MPS_Invalid && "Invalid memory phi state");
308109467b48Spatrick auto NewState = AllEqual ? MPS_Equivalent : MPS_Unique;
308209467b48Spatrick MemoryPhiState[MP] = NewState;
308309467b48Spatrick if (setMemoryClass(MP, CC) || OldState != NewState)
308409467b48Spatrick markMemoryUsersTouched(MP);
308509467b48Spatrick }
308609467b48Spatrick
308709467b48Spatrick // Value number a single instruction, symbolically evaluating, performing
308809467b48Spatrick // congruence finding, and updating mappings.
valueNumberInstruction(Instruction * I)308909467b48Spatrick void NewGVN::valueNumberInstruction(Instruction *I) {
309009467b48Spatrick LLVM_DEBUG(dbgs() << "Processing instruction " << *I << "\n");
309109467b48Spatrick if (!I->isTerminator()) {
309209467b48Spatrick const Expression *Symbolized = nullptr;
309309467b48Spatrick SmallPtrSet<Value *, 2> Visited;
309409467b48Spatrick if (DebugCounter::shouldExecute(VNCounter)) {
309573471bf0Spatrick auto Res = performSymbolicEvaluation(I, Visited);
309673471bf0Spatrick Symbolized = Res.Expr;
309773471bf0Spatrick addAdditionalUsers(Res, I);
309873471bf0Spatrick
309909467b48Spatrick // Make a phi of ops if necessary
310009467b48Spatrick if (Symbolized && !isa<ConstantExpression>(Symbolized) &&
310109467b48Spatrick !isa<VariableExpression>(Symbolized) && PHINodeUses.count(I)) {
310209467b48Spatrick auto *PHIE = makePossiblePHIOfOps(I, Visited);
310309467b48Spatrick // If we created a phi of ops, use it.
310409467b48Spatrick // If we couldn't create one, make sure we don't leave one lying around
310509467b48Spatrick if (PHIE) {
310609467b48Spatrick Symbolized = PHIE;
310709467b48Spatrick } else if (auto *Op = RealToTemp.lookup(I)) {
310809467b48Spatrick removePhiOfOps(I, Op);
310909467b48Spatrick }
311009467b48Spatrick }
311109467b48Spatrick } else {
311209467b48Spatrick // Mark the instruction as unused so we don't value number it again.
311309467b48Spatrick InstrDFS[I] = 0;
311409467b48Spatrick }
311509467b48Spatrick // If we couldn't come up with a symbolic expression, use the unknown
311609467b48Spatrick // expression
311709467b48Spatrick if (Symbolized == nullptr)
311809467b48Spatrick Symbolized = createUnknownExpression(I);
311909467b48Spatrick performCongruenceFinding(I, Symbolized);
312009467b48Spatrick } else {
312109467b48Spatrick // Handle terminators that return values. All of them produce values we
312209467b48Spatrick // don't currently understand. We don't place non-value producing
312309467b48Spatrick // terminators in a class.
312409467b48Spatrick if (!I->getType()->isVoidTy()) {
312509467b48Spatrick auto *Symbolized = createUnknownExpression(I);
312609467b48Spatrick performCongruenceFinding(I, Symbolized);
312709467b48Spatrick }
312809467b48Spatrick processOutgoingEdges(I, I->getParent());
312909467b48Spatrick }
313009467b48Spatrick }
313109467b48Spatrick
313209467b48Spatrick // Check if there is a path, using single or equal argument phi nodes, from
313309467b48Spatrick // First to Second.
singleReachablePHIPath(SmallPtrSet<const MemoryAccess *,8> & Visited,const MemoryAccess * First,const MemoryAccess * Second) const313409467b48Spatrick bool NewGVN::singleReachablePHIPath(
313509467b48Spatrick SmallPtrSet<const MemoryAccess *, 8> &Visited, const MemoryAccess *First,
313609467b48Spatrick const MemoryAccess *Second) const {
313709467b48Spatrick if (First == Second)
313809467b48Spatrick return true;
313909467b48Spatrick if (MSSA->isLiveOnEntryDef(First))
314009467b48Spatrick return false;
314109467b48Spatrick
314209467b48Spatrick // This is not perfect, but as we're just verifying here, we can live with
314309467b48Spatrick // the loss of precision. The real solution would be that of doing strongly
314409467b48Spatrick // connected component finding in this routine, and it's probably not worth
314509467b48Spatrick // the complexity for the time being. So, we just keep a set of visited
314609467b48Spatrick // MemoryAccess and return true when we hit a cycle.
3147*d415bd75Srobert if (!Visited.insert(First).second)
314809467b48Spatrick return true;
314909467b48Spatrick
315009467b48Spatrick const auto *EndDef = First;
3151*d415bd75Srobert for (const auto *ChainDef : optimized_def_chain(First)) {
315209467b48Spatrick if (ChainDef == Second)
315309467b48Spatrick return true;
315409467b48Spatrick if (MSSA->isLiveOnEntryDef(ChainDef))
315509467b48Spatrick return false;
315609467b48Spatrick EndDef = ChainDef;
315709467b48Spatrick }
315809467b48Spatrick auto *MP = cast<MemoryPhi>(EndDef);
315909467b48Spatrick auto ReachableOperandPred = [&](const Use &U) {
316009467b48Spatrick return ReachableEdges.count({MP->getIncomingBlock(U), MP->getBlock()});
316109467b48Spatrick };
316209467b48Spatrick auto FilteredPhiArgs =
316309467b48Spatrick make_filter_range(MP->operands(), ReachableOperandPred);
316409467b48Spatrick SmallVector<const Value *, 32> OperandList;
316509467b48Spatrick llvm::copy(FilteredPhiArgs, std::back_inserter(OperandList));
3166*d415bd75Srobert bool Okay = all_equal(OperandList);
316709467b48Spatrick if (Okay)
316809467b48Spatrick return singleReachablePHIPath(Visited, cast<MemoryAccess>(OperandList[0]),
316909467b48Spatrick Second);
317009467b48Spatrick return false;
317109467b48Spatrick }
317209467b48Spatrick
317309467b48Spatrick // Verify the that the memory equivalence table makes sense relative to the
317409467b48Spatrick // congruence classes. Note that this checking is not perfect, and is currently
317509467b48Spatrick // subject to very rare false negatives. It is only useful for
317609467b48Spatrick // testing/debugging.
verifyMemoryCongruency() const317709467b48Spatrick void NewGVN::verifyMemoryCongruency() const {
317809467b48Spatrick #ifndef NDEBUG
317909467b48Spatrick // Verify that the memory table equivalence and memory member set match
318009467b48Spatrick for (const auto *CC : CongruenceClasses) {
318109467b48Spatrick if (CC == TOPClass || CC->isDead())
318209467b48Spatrick continue;
318309467b48Spatrick if (CC->getStoreCount() != 0) {
318409467b48Spatrick assert((CC->getStoredValue() || !isa<StoreInst>(CC->getLeader())) &&
318509467b48Spatrick "Any class with a store as a leader should have a "
318609467b48Spatrick "representative stored value");
318709467b48Spatrick assert(CC->getMemoryLeader() &&
318809467b48Spatrick "Any congruence class with a store should have a "
318909467b48Spatrick "representative access");
319009467b48Spatrick }
319109467b48Spatrick
319209467b48Spatrick if (CC->getMemoryLeader())
319309467b48Spatrick assert(MemoryAccessToClass.lookup(CC->getMemoryLeader()) == CC &&
319409467b48Spatrick "Representative MemoryAccess does not appear to be reverse "
319509467b48Spatrick "mapped properly");
3196*d415bd75Srobert for (const auto *M : CC->memory())
319709467b48Spatrick assert(MemoryAccessToClass.lookup(M) == CC &&
319809467b48Spatrick "Memory member does not appear to be reverse mapped properly");
319909467b48Spatrick }
320009467b48Spatrick
320109467b48Spatrick // Anything equivalent in the MemoryAccess table should be in the same
320209467b48Spatrick // congruence class.
320309467b48Spatrick
320409467b48Spatrick // Filter out the unreachable and trivially dead entries, because they may
320509467b48Spatrick // never have been updated if the instructions were not processed.
320609467b48Spatrick auto ReachableAccessPred =
320709467b48Spatrick [&](const std::pair<const MemoryAccess *, CongruenceClass *> Pair) {
320809467b48Spatrick bool Result = ReachableBlocks.count(Pair.first->getBlock());
320909467b48Spatrick if (!Result || MSSA->isLiveOnEntryDef(Pair.first) ||
321009467b48Spatrick MemoryToDFSNum(Pair.first) == 0)
321109467b48Spatrick return false;
321209467b48Spatrick if (auto *MemDef = dyn_cast<MemoryDef>(Pair.first))
321309467b48Spatrick return !isInstructionTriviallyDead(MemDef->getMemoryInst());
321409467b48Spatrick
321509467b48Spatrick // We could have phi nodes which operands are all trivially dead,
321609467b48Spatrick // so we don't process them.
321709467b48Spatrick if (auto *MemPHI = dyn_cast<MemoryPhi>(Pair.first)) {
3218*d415bd75Srobert for (const auto &U : MemPHI->incoming_values()) {
321909467b48Spatrick if (auto *I = dyn_cast<Instruction>(&*U)) {
322009467b48Spatrick if (!isInstructionTriviallyDead(I))
322109467b48Spatrick return true;
322209467b48Spatrick }
322309467b48Spatrick }
322409467b48Spatrick return false;
322509467b48Spatrick }
322609467b48Spatrick
322709467b48Spatrick return true;
322809467b48Spatrick };
322909467b48Spatrick
323009467b48Spatrick auto Filtered = make_filter_range(MemoryAccessToClass, ReachableAccessPred);
323109467b48Spatrick for (auto KV : Filtered) {
323209467b48Spatrick if (auto *FirstMUD = dyn_cast<MemoryUseOrDef>(KV.first)) {
323309467b48Spatrick auto *SecondMUD = dyn_cast<MemoryUseOrDef>(KV.second->getMemoryLeader());
323409467b48Spatrick if (FirstMUD && SecondMUD) {
323509467b48Spatrick SmallPtrSet<const MemoryAccess *, 8> VisitedMAS;
323609467b48Spatrick assert((singleReachablePHIPath(VisitedMAS, FirstMUD, SecondMUD) ||
323709467b48Spatrick ValueToClass.lookup(FirstMUD->getMemoryInst()) ==
323809467b48Spatrick ValueToClass.lookup(SecondMUD->getMemoryInst())) &&
323909467b48Spatrick "The instructions for these memory operations should have "
324009467b48Spatrick "been in the same congruence class or reachable through"
324109467b48Spatrick "a single argument phi");
324209467b48Spatrick }
324309467b48Spatrick } else if (auto *FirstMP = dyn_cast<MemoryPhi>(KV.first)) {
324409467b48Spatrick // We can only sanely verify that MemoryDefs in the operand list all have
324509467b48Spatrick // the same class.
324609467b48Spatrick auto ReachableOperandPred = [&](const Use &U) {
324709467b48Spatrick return ReachableEdges.count(
324809467b48Spatrick {FirstMP->getIncomingBlock(U), FirstMP->getBlock()}) &&
324909467b48Spatrick isa<MemoryDef>(U);
325009467b48Spatrick
325109467b48Spatrick };
325209467b48Spatrick // All arguments should in the same class, ignoring unreachable arguments
325309467b48Spatrick auto FilteredPhiArgs =
325409467b48Spatrick make_filter_range(FirstMP->operands(), ReachableOperandPred);
325509467b48Spatrick SmallVector<const CongruenceClass *, 16> PhiOpClasses;
325609467b48Spatrick std::transform(FilteredPhiArgs.begin(), FilteredPhiArgs.end(),
325709467b48Spatrick std::back_inserter(PhiOpClasses), [&](const Use &U) {
325809467b48Spatrick const MemoryDef *MD = cast<MemoryDef>(U);
325909467b48Spatrick return ValueToClass.lookup(MD->getMemoryInst());
326009467b48Spatrick });
3261*d415bd75Srobert assert(all_equal(PhiOpClasses) &&
326209467b48Spatrick "All MemoryPhi arguments should be in the same class");
326309467b48Spatrick }
326409467b48Spatrick }
326509467b48Spatrick #endif
326609467b48Spatrick }
326709467b48Spatrick
326809467b48Spatrick // Verify that the sparse propagation we did actually found the maximal fixpoint
326909467b48Spatrick // We do this by storing the value to class mapping, touching all instructions,
327009467b48Spatrick // and redoing the iteration to see if anything changed.
verifyIterationSettled(Function & F)327109467b48Spatrick void NewGVN::verifyIterationSettled(Function &F) {
327209467b48Spatrick #ifndef NDEBUG
327309467b48Spatrick LLVM_DEBUG(dbgs() << "Beginning iteration verification\n");
327409467b48Spatrick if (DebugCounter::isCounterSet(VNCounter))
327509467b48Spatrick DebugCounter::setCounterValue(VNCounter, StartingVNCounter);
327609467b48Spatrick
327709467b48Spatrick // Note that we have to store the actual classes, as we may change existing
327809467b48Spatrick // classes during iteration. This is because our memory iteration propagation
327909467b48Spatrick // is not perfect, and so may waste a little work. But it should generate
328009467b48Spatrick // exactly the same congruence classes we have now, with different IDs.
328109467b48Spatrick std::map<const Value *, CongruenceClass> BeforeIteration;
328209467b48Spatrick
328309467b48Spatrick for (auto &KV : ValueToClass) {
328409467b48Spatrick if (auto *I = dyn_cast<Instruction>(KV.first))
328509467b48Spatrick // Skip unused/dead instructions.
328609467b48Spatrick if (InstrToDFSNum(I) == 0)
328709467b48Spatrick continue;
328809467b48Spatrick BeforeIteration.insert({KV.first, *KV.second});
328909467b48Spatrick }
329009467b48Spatrick
329109467b48Spatrick TouchedInstructions.set();
329209467b48Spatrick TouchedInstructions.reset(0);
3293*d415bd75Srobert OpSafeForPHIOfOps.clear();
329409467b48Spatrick iterateTouchedInstructions();
329509467b48Spatrick DenseSet<std::pair<const CongruenceClass *, const CongruenceClass *>>
329609467b48Spatrick EqualClasses;
329709467b48Spatrick for (const auto &KV : ValueToClass) {
329809467b48Spatrick if (auto *I = dyn_cast<Instruction>(KV.first))
329909467b48Spatrick // Skip unused/dead instructions.
330009467b48Spatrick if (InstrToDFSNum(I) == 0)
330109467b48Spatrick continue;
330209467b48Spatrick // We could sink these uses, but i think this adds a bit of clarity here as
330309467b48Spatrick // to what we are comparing.
330409467b48Spatrick auto *BeforeCC = &BeforeIteration.find(KV.first)->second;
330509467b48Spatrick auto *AfterCC = KV.second;
330609467b48Spatrick // Note that the classes can't change at this point, so we memoize the set
330709467b48Spatrick // that are equal.
330809467b48Spatrick if (!EqualClasses.count({BeforeCC, AfterCC})) {
330909467b48Spatrick assert(BeforeCC->isEquivalentTo(AfterCC) &&
331009467b48Spatrick "Value number changed after main loop completed!");
331109467b48Spatrick EqualClasses.insert({BeforeCC, AfterCC});
331209467b48Spatrick }
331309467b48Spatrick }
331409467b48Spatrick #endif
331509467b48Spatrick }
331609467b48Spatrick
331709467b48Spatrick // Verify that for each store expression in the expression to class mapping,
331809467b48Spatrick // only the latest appears, and multiple ones do not appear.
331909467b48Spatrick // Because loads do not use the stored value when doing equality with stores,
332009467b48Spatrick // if we don't erase the old store expressions from the table, a load can find
332109467b48Spatrick // a no-longer valid StoreExpression.
verifyStoreExpressions() const332209467b48Spatrick void NewGVN::verifyStoreExpressions() const {
332309467b48Spatrick #ifndef NDEBUG
332409467b48Spatrick // This is the only use of this, and it's not worth defining a complicated
332509467b48Spatrick // densemapinfo hash/equality function for it.
332609467b48Spatrick std::set<
332709467b48Spatrick std::pair<const Value *,
332809467b48Spatrick std::tuple<const Value *, const CongruenceClass *, Value *>>>
332909467b48Spatrick StoreExpressionSet;
333009467b48Spatrick for (const auto &KV : ExpressionToClass) {
333109467b48Spatrick if (auto *SE = dyn_cast<StoreExpression>(KV.first)) {
333209467b48Spatrick // Make sure a version that will conflict with loads is not already there
333309467b48Spatrick auto Res = StoreExpressionSet.insert(
333409467b48Spatrick {SE->getOperand(0), std::make_tuple(SE->getMemoryLeader(), KV.second,
333509467b48Spatrick SE->getStoredValue())});
333609467b48Spatrick bool Okay = Res.second;
333709467b48Spatrick // It's okay to have the same expression already in there if it is
333809467b48Spatrick // identical in nature.
333909467b48Spatrick // This can happen when the leader of the stored value changes over time.
334009467b48Spatrick if (!Okay)
334109467b48Spatrick Okay = (std::get<1>(Res.first->second) == KV.second) &&
334209467b48Spatrick (lookupOperandLeader(std::get<2>(Res.first->second)) ==
334309467b48Spatrick lookupOperandLeader(SE->getStoredValue()));
334409467b48Spatrick assert(Okay && "Stored expression conflict exists in expression table");
334509467b48Spatrick auto *ValueExpr = ValueToExpression.lookup(SE->getStoreInst());
334609467b48Spatrick assert(ValueExpr && ValueExpr->equals(*SE) &&
334709467b48Spatrick "StoreExpression in ExpressionToClass is not latest "
334809467b48Spatrick "StoreExpression for value");
334909467b48Spatrick }
335009467b48Spatrick }
335109467b48Spatrick #endif
335209467b48Spatrick }
335309467b48Spatrick
335409467b48Spatrick // This is the main value numbering loop, it iterates over the initial touched
335509467b48Spatrick // instruction set, propagating value numbers, marking things touched, etc,
335609467b48Spatrick // until the set of touched instructions is completely empty.
iterateTouchedInstructions()335709467b48Spatrick void NewGVN::iterateTouchedInstructions() {
3358*d415bd75Srobert uint64_t Iterations = 0;
335909467b48Spatrick // Figure out where touchedinstructions starts
336009467b48Spatrick int FirstInstr = TouchedInstructions.find_first();
336109467b48Spatrick // Nothing set, nothing to iterate, just return.
336209467b48Spatrick if (FirstInstr == -1)
336309467b48Spatrick return;
336409467b48Spatrick const BasicBlock *LastBlock = getBlockForValue(InstrFromDFSNum(FirstInstr));
336509467b48Spatrick while (TouchedInstructions.any()) {
336609467b48Spatrick ++Iterations;
336709467b48Spatrick // Walk through all the instructions in all the blocks in RPO.
336809467b48Spatrick // TODO: As we hit a new block, we should push and pop equalities into a
336909467b48Spatrick // table lookupOperandLeader can use, to catch things PredicateInfo
337009467b48Spatrick // might miss, like edge-only equivalences.
337109467b48Spatrick for (unsigned InstrNum : TouchedInstructions.set_bits()) {
337209467b48Spatrick
337309467b48Spatrick // This instruction was found to be dead. We don't bother looking
337409467b48Spatrick // at it again.
337509467b48Spatrick if (InstrNum == 0) {
337609467b48Spatrick TouchedInstructions.reset(InstrNum);
337709467b48Spatrick continue;
337809467b48Spatrick }
337909467b48Spatrick
338009467b48Spatrick Value *V = InstrFromDFSNum(InstrNum);
338109467b48Spatrick const BasicBlock *CurrBlock = getBlockForValue(V);
338209467b48Spatrick
338309467b48Spatrick // If we hit a new block, do reachability processing.
338409467b48Spatrick if (CurrBlock != LastBlock) {
338509467b48Spatrick LastBlock = CurrBlock;
338609467b48Spatrick bool BlockReachable = ReachableBlocks.count(CurrBlock);
338709467b48Spatrick const auto &CurrInstRange = BlockInstRange.lookup(CurrBlock);
338809467b48Spatrick
338909467b48Spatrick // If it's not reachable, erase any touched instructions and move on.
339009467b48Spatrick if (!BlockReachable) {
339109467b48Spatrick TouchedInstructions.reset(CurrInstRange.first, CurrInstRange.second);
339209467b48Spatrick LLVM_DEBUG(dbgs() << "Skipping instructions in block "
339309467b48Spatrick << getBlockName(CurrBlock)
339409467b48Spatrick << " because it is unreachable\n");
339509467b48Spatrick continue;
339609467b48Spatrick }
339709467b48Spatrick updateProcessedCount(CurrBlock);
339809467b48Spatrick }
339909467b48Spatrick // Reset after processing (because we may mark ourselves as touched when
340009467b48Spatrick // we propagate equalities).
340109467b48Spatrick TouchedInstructions.reset(InstrNum);
340209467b48Spatrick
340309467b48Spatrick if (auto *MP = dyn_cast<MemoryPhi>(V)) {
340409467b48Spatrick LLVM_DEBUG(dbgs() << "Processing MemoryPhi " << *MP << "\n");
340509467b48Spatrick valueNumberMemoryPhi(MP);
340609467b48Spatrick } else if (auto *I = dyn_cast<Instruction>(V)) {
340709467b48Spatrick valueNumberInstruction(I);
340809467b48Spatrick } else {
340909467b48Spatrick llvm_unreachable("Should have been a MemoryPhi or Instruction");
341009467b48Spatrick }
341109467b48Spatrick updateProcessedCount(V);
341209467b48Spatrick }
341309467b48Spatrick }
341409467b48Spatrick NumGVNMaxIterations = std::max(NumGVNMaxIterations.getValue(), Iterations);
341509467b48Spatrick }
341609467b48Spatrick
341709467b48Spatrick // This is the main transformation entry point.
runGVN()341809467b48Spatrick bool NewGVN::runGVN() {
341909467b48Spatrick if (DebugCounter::isCounterSet(VNCounter))
342009467b48Spatrick StartingVNCounter = DebugCounter::getCounterValue(VNCounter);
342109467b48Spatrick bool Changed = false;
342209467b48Spatrick NumFuncArgs = F.arg_size();
342309467b48Spatrick MSSAWalker = MSSA->getWalker();
342409467b48Spatrick SingletonDeadExpression = new (ExpressionAllocator) DeadExpression();
342509467b48Spatrick
342609467b48Spatrick // Count number of instructions for sizing of hash tables, and come
342709467b48Spatrick // up with a global dfs numbering for instructions.
342809467b48Spatrick unsigned ICount = 1;
342909467b48Spatrick // Add an empty instruction to account for the fact that we start at 1
343009467b48Spatrick DFSToInstr.emplace_back(nullptr);
343109467b48Spatrick // Note: We want ideal RPO traversal of the blocks, which is not quite the
343209467b48Spatrick // same as dominator tree order, particularly with regard whether backedges
343309467b48Spatrick // get visited first or second, given a block with multiple successors.
343409467b48Spatrick // If we visit in the wrong order, we will end up performing N times as many
343509467b48Spatrick // iterations.
343609467b48Spatrick // The dominator tree does guarantee that, for a given dom tree node, it's
343709467b48Spatrick // parent must occur before it in the RPO ordering. Thus, we only need to sort
343809467b48Spatrick // the siblings.
343909467b48Spatrick ReversePostOrderTraversal<Function *> RPOT(&F);
344009467b48Spatrick unsigned Counter = 0;
344109467b48Spatrick for (auto &B : RPOT) {
344209467b48Spatrick auto *Node = DT->getNode(B);
344309467b48Spatrick assert(Node && "RPO and Dominator tree should have same reachability");
344409467b48Spatrick RPOOrdering[Node] = ++Counter;
344509467b48Spatrick }
344609467b48Spatrick // Sort dominator tree children arrays into RPO.
344709467b48Spatrick for (auto &B : RPOT) {
344809467b48Spatrick auto *Node = DT->getNode(B);
3449097a140dSpatrick if (Node->getNumChildren() > 1)
345073471bf0Spatrick llvm::sort(*Node, [&](const DomTreeNode *A, const DomTreeNode *B) {
345109467b48Spatrick return RPOOrdering[A] < RPOOrdering[B];
345209467b48Spatrick });
345309467b48Spatrick }
345409467b48Spatrick
345509467b48Spatrick // Now a standard depth first ordering of the domtree is equivalent to RPO.
3456*d415bd75Srobert for (auto *DTN : depth_first(DT->getRootNode())) {
345709467b48Spatrick BasicBlock *B = DTN->getBlock();
345809467b48Spatrick const auto &BlockRange = assignDFSNumbers(B, ICount);
345909467b48Spatrick BlockInstRange.insert({B, BlockRange});
346009467b48Spatrick ICount += BlockRange.second - BlockRange.first;
346109467b48Spatrick }
346209467b48Spatrick initializeCongruenceClasses(F);
346309467b48Spatrick
346409467b48Spatrick TouchedInstructions.resize(ICount);
346509467b48Spatrick // Ensure we don't end up resizing the expressionToClass map, as
346609467b48Spatrick // that can be quite expensive. At most, we have one expression per
346709467b48Spatrick // instruction.
346809467b48Spatrick ExpressionToClass.reserve(ICount);
346909467b48Spatrick
347009467b48Spatrick // Initialize the touched instructions to include the entry block.
347109467b48Spatrick const auto &InstRange = BlockInstRange.lookup(&F.getEntryBlock());
347209467b48Spatrick TouchedInstructions.set(InstRange.first, InstRange.second);
347309467b48Spatrick LLVM_DEBUG(dbgs() << "Block " << getBlockName(&F.getEntryBlock())
347409467b48Spatrick << " marked reachable\n");
347509467b48Spatrick ReachableBlocks.insert(&F.getEntryBlock());
347609467b48Spatrick
347709467b48Spatrick iterateTouchedInstructions();
347809467b48Spatrick verifyMemoryCongruency();
347909467b48Spatrick verifyIterationSettled(F);
348009467b48Spatrick verifyStoreExpressions();
348109467b48Spatrick
348209467b48Spatrick Changed |= eliminateInstructions(F);
348309467b48Spatrick
348409467b48Spatrick // Delete all instructions marked for deletion.
348509467b48Spatrick for (Instruction *ToErase : InstructionsToErase) {
348609467b48Spatrick if (!ToErase->use_empty())
3487*d415bd75Srobert ToErase->replaceAllUsesWith(PoisonValue::get(ToErase->getType()));
348809467b48Spatrick
348909467b48Spatrick assert(ToErase->getParent() &&
349009467b48Spatrick "BB containing ToErase deleted unexpectedly!");
349109467b48Spatrick ToErase->eraseFromParent();
349209467b48Spatrick }
349309467b48Spatrick Changed |= !InstructionsToErase.empty();
349409467b48Spatrick
349509467b48Spatrick // Delete all unreachable blocks.
349609467b48Spatrick auto UnreachableBlockPred = [&](const BasicBlock &BB) {
349709467b48Spatrick return !ReachableBlocks.count(&BB);
349809467b48Spatrick };
349909467b48Spatrick
350009467b48Spatrick for (auto &BB : make_filter_range(F, UnreachableBlockPred)) {
350109467b48Spatrick LLVM_DEBUG(dbgs() << "We believe block " << getBlockName(&BB)
350209467b48Spatrick << " is unreachable\n");
350309467b48Spatrick deleteInstructionsInBlock(&BB);
350409467b48Spatrick Changed = true;
350509467b48Spatrick }
350609467b48Spatrick
350709467b48Spatrick cleanupTables();
350809467b48Spatrick return Changed;
350909467b48Spatrick }
351009467b48Spatrick
351109467b48Spatrick struct NewGVN::ValueDFS {
351209467b48Spatrick int DFSIn = 0;
351309467b48Spatrick int DFSOut = 0;
351409467b48Spatrick int LocalNum = 0;
351509467b48Spatrick
351609467b48Spatrick // Only one of Def and U will be set.
351709467b48Spatrick // The bool in the Def tells us whether the Def is the stored value of a
351809467b48Spatrick // store.
351909467b48Spatrick PointerIntPair<Value *, 1, bool> Def;
352009467b48Spatrick Use *U = nullptr;
352109467b48Spatrick
operator <NewGVN::ValueDFS352209467b48Spatrick bool operator<(const ValueDFS &Other) const {
352309467b48Spatrick // It's not enough that any given field be less than - we have sets
352409467b48Spatrick // of fields that need to be evaluated together to give a proper ordering.
352509467b48Spatrick // For example, if you have;
352609467b48Spatrick // DFS (1, 3)
352709467b48Spatrick // Val 0
352809467b48Spatrick // DFS (1, 2)
352909467b48Spatrick // Val 50
353009467b48Spatrick // We want the second to be less than the first, but if we just go field
353109467b48Spatrick // by field, we will get to Val 0 < Val 50 and say the first is less than
353209467b48Spatrick // the second. We only want it to be less than if the DFS orders are equal.
353309467b48Spatrick //
353409467b48Spatrick // Each LLVM instruction only produces one value, and thus the lowest-level
353509467b48Spatrick // differentiator that really matters for the stack (and what we use as as a
353609467b48Spatrick // replacement) is the local dfs number.
353709467b48Spatrick // Everything else in the structure is instruction level, and only affects
353809467b48Spatrick // the order in which we will replace operands of a given instruction.
353909467b48Spatrick //
354009467b48Spatrick // For a given instruction (IE things with equal dfsin, dfsout, localnum),
354109467b48Spatrick // the order of replacement of uses does not matter.
354209467b48Spatrick // IE given,
354309467b48Spatrick // a = 5
354409467b48Spatrick // b = a + a
354509467b48Spatrick // When you hit b, you will have two valuedfs with the same dfsin, out, and
354609467b48Spatrick // localnum.
354709467b48Spatrick // The .val will be the same as well.
354809467b48Spatrick // The .u's will be different.
354909467b48Spatrick // You will replace both, and it does not matter what order you replace them
355009467b48Spatrick // in (IE whether you replace operand 2, then operand 1, or operand 1, then
355109467b48Spatrick // operand 2).
355209467b48Spatrick // Similarly for the case of same dfsin, dfsout, localnum, but different
355309467b48Spatrick // .val's
355409467b48Spatrick // a = 5
355509467b48Spatrick // b = 6
355609467b48Spatrick // c = a + b
355709467b48Spatrick // in c, we will a valuedfs for a, and one for b,with everything the same
355809467b48Spatrick // but .val and .u.
355909467b48Spatrick // It does not matter what order we replace these operands in.
356009467b48Spatrick // You will always end up with the same IR, and this is guaranteed.
356109467b48Spatrick return std::tie(DFSIn, DFSOut, LocalNum, Def, U) <
356209467b48Spatrick std::tie(Other.DFSIn, Other.DFSOut, Other.LocalNum, Other.Def,
356309467b48Spatrick Other.U);
356409467b48Spatrick }
356509467b48Spatrick };
356609467b48Spatrick
356709467b48Spatrick // This function converts the set of members for a congruence class from values,
356809467b48Spatrick // to sets of defs and uses with associated DFS info. The total number of
356909467b48Spatrick // reachable uses for each value is stored in UseCount, and instructions that
357009467b48Spatrick // seem
357109467b48Spatrick // dead (have no non-dead uses) are stored in ProbablyDead.
convertClassToDFSOrdered(const CongruenceClass & Dense,SmallVectorImpl<ValueDFS> & DFSOrderedSet,DenseMap<const Value *,unsigned int> & UseCounts,SmallPtrSetImpl<Instruction * > & ProbablyDead) const357209467b48Spatrick void NewGVN::convertClassToDFSOrdered(
357309467b48Spatrick const CongruenceClass &Dense, SmallVectorImpl<ValueDFS> &DFSOrderedSet,
357409467b48Spatrick DenseMap<const Value *, unsigned int> &UseCounts,
357509467b48Spatrick SmallPtrSetImpl<Instruction *> &ProbablyDead) const {
3576*d415bd75Srobert for (auto *D : Dense) {
357709467b48Spatrick // First add the value.
357809467b48Spatrick BasicBlock *BB = getBlockForValue(D);
357909467b48Spatrick // Constants are handled prior to ever calling this function, so
358009467b48Spatrick // we should only be left with instructions as members.
358109467b48Spatrick assert(BB && "Should have figured out a basic block for value");
358209467b48Spatrick ValueDFS VDDef;
358309467b48Spatrick DomTreeNode *DomNode = DT->getNode(BB);
358409467b48Spatrick VDDef.DFSIn = DomNode->getDFSNumIn();
358509467b48Spatrick VDDef.DFSOut = DomNode->getDFSNumOut();
358609467b48Spatrick // If it's a store, use the leader of the value operand, if it's always
358709467b48Spatrick // available, or the value operand. TODO: We could do dominance checks to
358809467b48Spatrick // find a dominating leader, but not worth it ATM.
358909467b48Spatrick if (auto *SI = dyn_cast<StoreInst>(D)) {
359009467b48Spatrick auto Leader = lookupOperandLeader(SI->getValueOperand());
359109467b48Spatrick if (alwaysAvailable(Leader)) {
359209467b48Spatrick VDDef.Def.setPointer(Leader);
359309467b48Spatrick } else {
359409467b48Spatrick VDDef.Def.setPointer(SI->getValueOperand());
359509467b48Spatrick VDDef.Def.setInt(true);
359609467b48Spatrick }
359709467b48Spatrick } else {
359809467b48Spatrick VDDef.Def.setPointer(D);
359909467b48Spatrick }
360009467b48Spatrick assert(isa<Instruction>(D) &&
360109467b48Spatrick "The dense set member should always be an instruction");
360209467b48Spatrick Instruction *Def = cast<Instruction>(D);
360309467b48Spatrick VDDef.LocalNum = InstrToDFSNum(D);
360409467b48Spatrick DFSOrderedSet.push_back(VDDef);
360509467b48Spatrick // If there is a phi node equivalent, add it
360609467b48Spatrick if (auto *PN = RealToTemp.lookup(Def)) {
360709467b48Spatrick auto *PHIE =
360809467b48Spatrick dyn_cast_or_null<PHIExpression>(ValueToExpression.lookup(Def));
360909467b48Spatrick if (PHIE) {
361009467b48Spatrick VDDef.Def.setInt(false);
361109467b48Spatrick VDDef.Def.setPointer(PN);
361209467b48Spatrick VDDef.LocalNum = 0;
361309467b48Spatrick DFSOrderedSet.push_back(VDDef);
361409467b48Spatrick }
361509467b48Spatrick }
361609467b48Spatrick
361709467b48Spatrick unsigned int UseCount = 0;
361809467b48Spatrick // Now add the uses.
361909467b48Spatrick for (auto &U : Def->uses()) {
362009467b48Spatrick if (auto *I = dyn_cast<Instruction>(U.getUser())) {
362109467b48Spatrick // Don't try to replace into dead uses
362209467b48Spatrick if (InstructionsToErase.count(I))
362309467b48Spatrick continue;
362409467b48Spatrick ValueDFS VDUse;
362509467b48Spatrick // Put the phi node uses in the incoming block.
362609467b48Spatrick BasicBlock *IBlock;
362709467b48Spatrick if (auto *P = dyn_cast<PHINode>(I)) {
362809467b48Spatrick IBlock = P->getIncomingBlock(U);
362909467b48Spatrick // Make phi node users appear last in the incoming block
363009467b48Spatrick // they are from.
363109467b48Spatrick VDUse.LocalNum = InstrDFS.size() + 1;
363209467b48Spatrick } else {
363309467b48Spatrick IBlock = getBlockForValue(I);
363409467b48Spatrick VDUse.LocalNum = InstrToDFSNum(I);
363509467b48Spatrick }
363609467b48Spatrick
363709467b48Spatrick // Skip uses in unreachable blocks, as we're going
363809467b48Spatrick // to delete them.
3639*d415bd75Srobert if (!ReachableBlocks.contains(IBlock))
364009467b48Spatrick continue;
364109467b48Spatrick
364209467b48Spatrick DomTreeNode *DomNode = DT->getNode(IBlock);
364309467b48Spatrick VDUse.DFSIn = DomNode->getDFSNumIn();
364409467b48Spatrick VDUse.DFSOut = DomNode->getDFSNumOut();
364509467b48Spatrick VDUse.U = &U;
364609467b48Spatrick ++UseCount;
364709467b48Spatrick DFSOrderedSet.emplace_back(VDUse);
364809467b48Spatrick }
364909467b48Spatrick }
365009467b48Spatrick
365109467b48Spatrick // If there are no uses, it's probably dead (but it may have side-effects,
365209467b48Spatrick // so not definitely dead. Otherwise, store the number of uses so we can
365309467b48Spatrick // track if it becomes dead later).
365409467b48Spatrick if (UseCount == 0)
365509467b48Spatrick ProbablyDead.insert(Def);
365609467b48Spatrick else
365709467b48Spatrick UseCounts[Def] = UseCount;
365809467b48Spatrick }
365909467b48Spatrick }
366009467b48Spatrick
366109467b48Spatrick // This function converts the set of members for a congruence class from values,
366209467b48Spatrick // to the set of defs for loads and stores, with associated DFS info.
convertClassToLoadsAndStores(const CongruenceClass & Dense,SmallVectorImpl<ValueDFS> & LoadsAndStores) const366309467b48Spatrick void NewGVN::convertClassToLoadsAndStores(
366409467b48Spatrick const CongruenceClass &Dense,
366509467b48Spatrick SmallVectorImpl<ValueDFS> &LoadsAndStores) const {
3666*d415bd75Srobert for (auto *D : Dense) {
366709467b48Spatrick if (!isa<LoadInst>(D) && !isa<StoreInst>(D))
366809467b48Spatrick continue;
366909467b48Spatrick
367009467b48Spatrick BasicBlock *BB = getBlockForValue(D);
367109467b48Spatrick ValueDFS VD;
367209467b48Spatrick DomTreeNode *DomNode = DT->getNode(BB);
367309467b48Spatrick VD.DFSIn = DomNode->getDFSNumIn();
367409467b48Spatrick VD.DFSOut = DomNode->getDFSNumOut();
367509467b48Spatrick VD.Def.setPointer(D);
367609467b48Spatrick
367709467b48Spatrick // If it's an instruction, use the real local dfs number.
367809467b48Spatrick if (auto *I = dyn_cast<Instruction>(D))
367909467b48Spatrick VD.LocalNum = InstrToDFSNum(I);
368009467b48Spatrick else
368109467b48Spatrick llvm_unreachable("Should have been an instruction");
368209467b48Spatrick
368309467b48Spatrick LoadsAndStores.emplace_back(VD);
368409467b48Spatrick }
368509467b48Spatrick }
368609467b48Spatrick
patchAndReplaceAllUsesWith(Instruction * I,Value * Repl)368709467b48Spatrick static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl) {
368809467b48Spatrick patchReplacementInstruction(I, Repl);
368909467b48Spatrick I->replaceAllUsesWith(Repl);
369009467b48Spatrick }
369109467b48Spatrick
deleteInstructionsInBlock(BasicBlock * BB)369209467b48Spatrick void NewGVN::deleteInstructionsInBlock(BasicBlock *BB) {
369309467b48Spatrick LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << *BB);
369409467b48Spatrick ++NumGVNBlocksDeleted;
369509467b48Spatrick
369609467b48Spatrick // Delete the instructions backwards, as it has a reduced likelihood of having
369709467b48Spatrick // to update as many def-use and use-def chains. Start after the terminator.
369809467b48Spatrick auto StartPoint = BB->rbegin();
369909467b48Spatrick ++StartPoint;
370009467b48Spatrick // Note that we explicitly recalculate BB->rend() on each iteration,
370109467b48Spatrick // as it may change when we remove the first instruction.
370209467b48Spatrick for (BasicBlock::reverse_iterator I(StartPoint); I != BB->rend();) {
370309467b48Spatrick Instruction &Inst = *I++;
370409467b48Spatrick if (!Inst.use_empty())
3705*d415bd75Srobert Inst.replaceAllUsesWith(PoisonValue::get(Inst.getType()));
370609467b48Spatrick if (isa<LandingPadInst>(Inst))
370709467b48Spatrick continue;
3708097a140dSpatrick salvageKnowledge(&Inst, AC);
370909467b48Spatrick
371009467b48Spatrick Inst.eraseFromParent();
371109467b48Spatrick ++NumGVNInstrDeleted;
371209467b48Spatrick }
371309467b48Spatrick // Now insert something that simplifycfg will turn into an unreachable.
371409467b48Spatrick Type *Int8Ty = Type::getInt8Ty(BB->getContext());
3715*d415bd75Srobert new StoreInst(PoisonValue::get(Int8Ty),
371609467b48Spatrick Constant::getNullValue(Int8Ty->getPointerTo()),
371709467b48Spatrick BB->getTerminator());
371809467b48Spatrick }
371909467b48Spatrick
markInstructionForDeletion(Instruction * I)372009467b48Spatrick void NewGVN::markInstructionForDeletion(Instruction *I) {
372109467b48Spatrick LLVM_DEBUG(dbgs() << "Marking " << *I << " for deletion\n");
372209467b48Spatrick InstructionsToErase.insert(I);
372309467b48Spatrick }
372409467b48Spatrick
replaceInstruction(Instruction * I,Value * V)372509467b48Spatrick void NewGVN::replaceInstruction(Instruction *I, Value *V) {
372609467b48Spatrick LLVM_DEBUG(dbgs() << "Replacing " << *I << " with " << *V << "\n");
372709467b48Spatrick patchAndReplaceAllUsesWith(I, V);
372809467b48Spatrick // We save the actual erasing to avoid invalidating memory
372909467b48Spatrick // dependencies until we are done with everything.
373009467b48Spatrick markInstructionForDeletion(I);
373109467b48Spatrick }
373209467b48Spatrick
373309467b48Spatrick namespace {
373409467b48Spatrick
373509467b48Spatrick // This is a stack that contains both the value and dfs info of where
373609467b48Spatrick // that value is valid.
373709467b48Spatrick class ValueDFSStack {
373809467b48Spatrick public:
back() const373909467b48Spatrick Value *back() const { return ValueStack.back(); }
dfs_back() const374009467b48Spatrick std::pair<int, int> dfs_back() const { return DFSStack.back(); }
374109467b48Spatrick
push_back(Value * V,int DFSIn,int DFSOut)374209467b48Spatrick void push_back(Value *V, int DFSIn, int DFSOut) {
374309467b48Spatrick ValueStack.emplace_back(V);
374409467b48Spatrick DFSStack.emplace_back(DFSIn, DFSOut);
374509467b48Spatrick }
374609467b48Spatrick
empty() const374709467b48Spatrick bool empty() const { return DFSStack.empty(); }
374809467b48Spatrick
isInScope(int DFSIn,int DFSOut) const374909467b48Spatrick bool isInScope(int DFSIn, int DFSOut) const {
375009467b48Spatrick if (empty())
375109467b48Spatrick return false;
375209467b48Spatrick return DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second;
375309467b48Spatrick }
375409467b48Spatrick
popUntilDFSScope(int DFSIn,int DFSOut)375509467b48Spatrick void popUntilDFSScope(int DFSIn, int DFSOut) {
375609467b48Spatrick
375709467b48Spatrick // These two should always be in sync at this point.
375809467b48Spatrick assert(ValueStack.size() == DFSStack.size() &&
375909467b48Spatrick "Mismatch between ValueStack and DFSStack");
376009467b48Spatrick while (
376109467b48Spatrick !DFSStack.empty() &&
376209467b48Spatrick !(DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second)) {
376309467b48Spatrick DFSStack.pop_back();
376409467b48Spatrick ValueStack.pop_back();
376509467b48Spatrick }
376609467b48Spatrick }
376709467b48Spatrick
376809467b48Spatrick private:
376909467b48Spatrick SmallVector<Value *, 8> ValueStack;
377009467b48Spatrick SmallVector<std::pair<int, int>, 8> DFSStack;
377109467b48Spatrick };
377209467b48Spatrick
377309467b48Spatrick } // end anonymous namespace
377409467b48Spatrick
377509467b48Spatrick // Given an expression, get the congruence class for it.
getClassForExpression(const Expression * E) const377609467b48Spatrick CongruenceClass *NewGVN::getClassForExpression(const Expression *E) const {
377709467b48Spatrick if (auto *VE = dyn_cast<VariableExpression>(E))
377809467b48Spatrick return ValueToClass.lookup(VE->getVariableValue());
377909467b48Spatrick else if (isa<DeadExpression>(E))
378009467b48Spatrick return TOPClass;
378109467b48Spatrick return ExpressionToClass.lookup(E);
378209467b48Spatrick }
378309467b48Spatrick
378409467b48Spatrick // Given a value and a basic block we are trying to see if it is available in,
378509467b48Spatrick // see if the value has a leader available in that block.
findPHIOfOpsLeader(const Expression * E,const Instruction * OrigInst,const BasicBlock * BB) const378609467b48Spatrick Value *NewGVN::findPHIOfOpsLeader(const Expression *E,
378709467b48Spatrick const Instruction *OrigInst,
378809467b48Spatrick const BasicBlock *BB) const {
378909467b48Spatrick // It would already be constant if we could make it constant
379009467b48Spatrick if (auto *CE = dyn_cast<ConstantExpression>(E))
379109467b48Spatrick return CE->getConstantValue();
379209467b48Spatrick if (auto *VE = dyn_cast<VariableExpression>(E)) {
379309467b48Spatrick auto *V = VE->getVariableValue();
379409467b48Spatrick if (alwaysAvailable(V) || DT->dominates(getBlockForValue(V), BB))
379509467b48Spatrick return VE->getVariableValue();
379609467b48Spatrick }
379709467b48Spatrick
379809467b48Spatrick auto *CC = getClassForExpression(E);
379909467b48Spatrick if (!CC)
380009467b48Spatrick return nullptr;
380109467b48Spatrick if (alwaysAvailable(CC->getLeader()))
380209467b48Spatrick return CC->getLeader();
380309467b48Spatrick
3804*d415bd75Srobert for (auto *Member : *CC) {
380509467b48Spatrick auto *MemberInst = dyn_cast<Instruction>(Member);
380609467b48Spatrick if (MemberInst == OrigInst)
380709467b48Spatrick continue;
380809467b48Spatrick // Anything that isn't an instruction is always available.
380909467b48Spatrick if (!MemberInst)
381009467b48Spatrick return Member;
381109467b48Spatrick if (DT->dominates(getBlockForValue(MemberInst), BB))
381209467b48Spatrick return Member;
381309467b48Spatrick }
381409467b48Spatrick return nullptr;
381509467b48Spatrick }
381609467b48Spatrick
eliminateInstructions(Function & F)381709467b48Spatrick bool NewGVN::eliminateInstructions(Function &F) {
381809467b48Spatrick // This is a non-standard eliminator. The normal way to eliminate is
381909467b48Spatrick // to walk the dominator tree in order, keeping track of available
382009467b48Spatrick // values, and eliminating them. However, this is mildly
382109467b48Spatrick // pointless. It requires doing lookups on every instruction,
382209467b48Spatrick // regardless of whether we will ever eliminate it. For
382309467b48Spatrick // instructions part of most singleton congruence classes, we know we
382409467b48Spatrick // will never eliminate them.
382509467b48Spatrick
382609467b48Spatrick // Instead, this eliminator looks at the congruence classes directly, sorts
382709467b48Spatrick // them into a DFS ordering of the dominator tree, and then we just
382809467b48Spatrick // perform elimination straight on the sets by walking the congruence
382909467b48Spatrick // class member uses in order, and eliminate the ones dominated by the
383009467b48Spatrick // last member. This is worst case O(E log E) where E = number of
383109467b48Spatrick // instructions in a single congruence class. In theory, this is all
383209467b48Spatrick // instructions. In practice, it is much faster, as most instructions are
383309467b48Spatrick // either in singleton congruence classes or can't possibly be eliminated
383409467b48Spatrick // anyway (if there are no overlapping DFS ranges in class).
383509467b48Spatrick // When we find something not dominated, it becomes the new leader
383609467b48Spatrick // for elimination purposes.
383709467b48Spatrick // TODO: If we wanted to be faster, We could remove any members with no
383809467b48Spatrick // overlapping ranges while sorting, as we will never eliminate anything
383909467b48Spatrick // with those members, as they don't dominate anything else in our set.
384009467b48Spatrick
384109467b48Spatrick bool AnythingReplaced = false;
384209467b48Spatrick
384309467b48Spatrick // Since we are going to walk the domtree anyway, and we can't guarantee the
384409467b48Spatrick // DFS numbers are updated, we compute some ourselves.
384509467b48Spatrick DT->updateDFSNumbers();
384609467b48Spatrick
384709467b48Spatrick // Go through all of our phi nodes, and kill the arguments associated with
384809467b48Spatrick // unreachable edges.
384909467b48Spatrick auto ReplaceUnreachablePHIArgs = [&](PHINode *PHI, BasicBlock *BB) {
385009467b48Spatrick for (auto &Operand : PHI->incoming_values())
385109467b48Spatrick if (!ReachableEdges.count({PHI->getIncomingBlock(Operand), BB})) {
385209467b48Spatrick LLVM_DEBUG(dbgs() << "Replacing incoming value of " << PHI
385309467b48Spatrick << " for block "
385409467b48Spatrick << getBlockName(PHI->getIncomingBlock(Operand))
3855*d415bd75Srobert << " with poison due to it being unreachable\n");
3856*d415bd75Srobert Operand.set(PoisonValue::get(PHI->getType()));
385709467b48Spatrick }
385809467b48Spatrick };
385909467b48Spatrick // Replace unreachable phi arguments.
386009467b48Spatrick // At this point, RevisitOnReachabilityChange only contains:
386109467b48Spatrick //
386209467b48Spatrick // 1. PHIs
386309467b48Spatrick // 2. Temporaries that will convert to PHIs
386409467b48Spatrick // 3. Operations that are affected by an unreachable edge but do not fit into
386509467b48Spatrick // 1 or 2 (rare).
386609467b48Spatrick // So it is a slight overshoot of what we want. We could make it exact by
386709467b48Spatrick // using two SparseBitVectors per block.
386809467b48Spatrick DenseMap<const BasicBlock *, unsigned> ReachablePredCount;
386909467b48Spatrick for (auto &KV : ReachableEdges)
387009467b48Spatrick ReachablePredCount[KV.getEnd()]++;
387109467b48Spatrick for (auto &BBPair : RevisitOnReachabilityChange) {
387209467b48Spatrick for (auto InstNum : BBPair.second) {
387309467b48Spatrick auto *Inst = InstrFromDFSNum(InstNum);
387409467b48Spatrick auto *PHI = dyn_cast<PHINode>(Inst);
387509467b48Spatrick PHI = PHI ? PHI : dyn_cast_or_null<PHINode>(RealToTemp.lookup(Inst));
387609467b48Spatrick if (!PHI)
387709467b48Spatrick continue;
387809467b48Spatrick auto *BB = BBPair.first;
387909467b48Spatrick if (ReachablePredCount.lookup(BB) != PHI->getNumIncomingValues())
388009467b48Spatrick ReplaceUnreachablePHIArgs(PHI, BB);
388109467b48Spatrick }
388209467b48Spatrick }
388309467b48Spatrick
388409467b48Spatrick // Map to store the use counts
388509467b48Spatrick DenseMap<const Value *, unsigned int> UseCounts;
388609467b48Spatrick for (auto *CC : reverse(CongruenceClasses)) {
388709467b48Spatrick LLVM_DEBUG(dbgs() << "Eliminating in congruence class " << CC->getID()
388809467b48Spatrick << "\n");
388909467b48Spatrick // Track the equivalent store info so we can decide whether to try
389009467b48Spatrick // dead store elimination.
389109467b48Spatrick SmallVector<ValueDFS, 8> PossibleDeadStores;
389209467b48Spatrick SmallPtrSet<Instruction *, 8> ProbablyDead;
389309467b48Spatrick if (CC->isDead() || CC->empty())
389409467b48Spatrick continue;
389509467b48Spatrick // Everything still in the TOP class is unreachable or dead.
389609467b48Spatrick if (CC == TOPClass) {
3897*d415bd75Srobert for (auto *M : *CC) {
389809467b48Spatrick auto *VTE = ValueToExpression.lookup(M);
389909467b48Spatrick if (VTE && isa<DeadExpression>(VTE))
390009467b48Spatrick markInstructionForDeletion(cast<Instruction>(M));
390109467b48Spatrick assert((!ReachableBlocks.count(cast<Instruction>(M)->getParent()) ||
390209467b48Spatrick InstructionsToErase.count(cast<Instruction>(M))) &&
390309467b48Spatrick "Everything in TOP should be unreachable or dead at this "
390409467b48Spatrick "point");
390509467b48Spatrick }
390609467b48Spatrick continue;
390709467b48Spatrick }
390809467b48Spatrick
390909467b48Spatrick assert(CC->getLeader() && "We should have had a leader");
391009467b48Spatrick // If this is a leader that is always available, and it's a
391109467b48Spatrick // constant or has no equivalences, just replace everything with
391209467b48Spatrick // it. We then update the congruence class with whatever members
391309467b48Spatrick // are left.
391409467b48Spatrick Value *Leader =
391509467b48Spatrick CC->getStoredValue() ? CC->getStoredValue() : CC->getLeader();
391609467b48Spatrick if (alwaysAvailable(Leader)) {
391709467b48Spatrick CongruenceClass::MemberSet MembersLeft;
3918*d415bd75Srobert for (auto *M : *CC) {
391909467b48Spatrick Value *Member = M;
392009467b48Spatrick // Void things have no uses we can replace.
392109467b48Spatrick if (Member == Leader || !isa<Instruction>(Member) ||
392209467b48Spatrick Member->getType()->isVoidTy()) {
392309467b48Spatrick MembersLeft.insert(Member);
392409467b48Spatrick continue;
392509467b48Spatrick }
392609467b48Spatrick LLVM_DEBUG(dbgs() << "Found replacement " << *(Leader) << " for "
392709467b48Spatrick << *Member << "\n");
392809467b48Spatrick auto *I = cast<Instruction>(Member);
392909467b48Spatrick assert(Leader != I && "About to accidentally remove our leader");
393009467b48Spatrick replaceInstruction(I, Leader);
393109467b48Spatrick AnythingReplaced = true;
393209467b48Spatrick }
393309467b48Spatrick CC->swap(MembersLeft);
393409467b48Spatrick } else {
393509467b48Spatrick // If this is a singleton, we can skip it.
393609467b48Spatrick if (CC->size() != 1 || RealToTemp.count(Leader)) {
393709467b48Spatrick // This is a stack because equality replacement/etc may place
393809467b48Spatrick // constants in the middle of the member list, and we want to use
393909467b48Spatrick // those constant values in preference to the current leader, over
394009467b48Spatrick // the scope of those constants.
394109467b48Spatrick ValueDFSStack EliminationStack;
394209467b48Spatrick
394309467b48Spatrick // Convert the members to DFS ordered sets and then merge them.
394409467b48Spatrick SmallVector<ValueDFS, 8> DFSOrderedSet;
394509467b48Spatrick convertClassToDFSOrdered(*CC, DFSOrderedSet, UseCounts, ProbablyDead);
394609467b48Spatrick
394709467b48Spatrick // Sort the whole thing.
394809467b48Spatrick llvm::sort(DFSOrderedSet);
394909467b48Spatrick for (auto &VD : DFSOrderedSet) {
395009467b48Spatrick int MemberDFSIn = VD.DFSIn;
395109467b48Spatrick int MemberDFSOut = VD.DFSOut;
395209467b48Spatrick Value *Def = VD.Def.getPointer();
395309467b48Spatrick bool FromStore = VD.Def.getInt();
395409467b48Spatrick Use *U = VD.U;
395509467b48Spatrick // We ignore void things because we can't get a value from them.
395609467b48Spatrick if (Def && Def->getType()->isVoidTy())
395709467b48Spatrick continue;
395809467b48Spatrick auto *DefInst = dyn_cast_or_null<Instruction>(Def);
395909467b48Spatrick if (DefInst && AllTempInstructions.count(DefInst)) {
396009467b48Spatrick auto *PN = cast<PHINode>(DefInst);
396109467b48Spatrick
396209467b48Spatrick // If this is a value phi and that's the expression we used, insert
396309467b48Spatrick // it into the program
396409467b48Spatrick // remove from temp instruction list.
396509467b48Spatrick AllTempInstructions.erase(PN);
396609467b48Spatrick auto *DefBlock = getBlockForValue(Def);
396709467b48Spatrick LLVM_DEBUG(dbgs() << "Inserting fully real phi of ops" << *Def
396809467b48Spatrick << " into block "
396909467b48Spatrick << getBlockName(getBlockForValue(Def)) << "\n");
397009467b48Spatrick PN->insertBefore(&DefBlock->front());
397109467b48Spatrick Def = PN;
397209467b48Spatrick NumGVNPHIOfOpsEliminations++;
397309467b48Spatrick }
397409467b48Spatrick
397509467b48Spatrick if (EliminationStack.empty()) {
397609467b48Spatrick LLVM_DEBUG(dbgs() << "Elimination Stack is empty\n");
397709467b48Spatrick } else {
397809467b48Spatrick LLVM_DEBUG(dbgs() << "Elimination Stack Top DFS numbers are ("
397909467b48Spatrick << EliminationStack.dfs_back().first << ","
398009467b48Spatrick << EliminationStack.dfs_back().second << ")\n");
398109467b48Spatrick }
398209467b48Spatrick
398309467b48Spatrick LLVM_DEBUG(dbgs() << "Current DFS numbers are (" << MemberDFSIn << ","
398409467b48Spatrick << MemberDFSOut << ")\n");
398509467b48Spatrick // First, we see if we are out of scope or empty. If so,
398609467b48Spatrick // and there equivalences, we try to replace the top of
398709467b48Spatrick // stack with equivalences (if it's on the stack, it must
398809467b48Spatrick // not have been eliminated yet).
398909467b48Spatrick // Then we synchronize to our current scope, by
399009467b48Spatrick // popping until we are back within a DFS scope that
399109467b48Spatrick // dominates the current member.
399209467b48Spatrick // Then, what happens depends on a few factors
399309467b48Spatrick // If the stack is now empty, we need to push
399409467b48Spatrick // If we have a constant or a local equivalence we want to
399509467b48Spatrick // start using, we also push.
399609467b48Spatrick // Otherwise, we walk along, processing members who are
399709467b48Spatrick // dominated by this scope, and eliminate them.
399809467b48Spatrick bool ShouldPush = Def && EliminationStack.empty();
399909467b48Spatrick bool OutOfScope =
400009467b48Spatrick !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut);
400109467b48Spatrick
400209467b48Spatrick if (OutOfScope || ShouldPush) {
400309467b48Spatrick // Sync to our current scope.
400409467b48Spatrick EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
400509467b48Spatrick bool ShouldPush = Def && EliminationStack.empty();
400609467b48Spatrick if (ShouldPush) {
400709467b48Spatrick EliminationStack.push_back(Def, MemberDFSIn, MemberDFSOut);
400809467b48Spatrick }
400909467b48Spatrick }
401009467b48Spatrick
401109467b48Spatrick // Skip the Def's, we only want to eliminate on their uses. But mark
401209467b48Spatrick // dominated defs as dead.
401309467b48Spatrick if (Def) {
401409467b48Spatrick // For anything in this case, what and how we value number
401509467b48Spatrick // guarantees that any side-effets that would have occurred (ie
401609467b48Spatrick // throwing, etc) can be proven to either still occur (because it's
401709467b48Spatrick // dominated by something that has the same side-effects), or never
401809467b48Spatrick // occur. Otherwise, we would not have been able to prove it value
401909467b48Spatrick // equivalent to something else. For these things, we can just mark
402009467b48Spatrick // it all dead. Note that this is different from the "ProbablyDead"
402109467b48Spatrick // set, which may not be dominated by anything, and thus, are only
402209467b48Spatrick // easy to prove dead if they are also side-effect free. Note that
402309467b48Spatrick // because stores are put in terms of the stored value, we skip
402409467b48Spatrick // stored values here. If the stored value is really dead, it will
402509467b48Spatrick // still be marked for deletion when we process it in its own class.
402609467b48Spatrick if (!EliminationStack.empty() && Def != EliminationStack.back() &&
402709467b48Spatrick isa<Instruction>(Def) && !FromStore)
402809467b48Spatrick markInstructionForDeletion(cast<Instruction>(Def));
402909467b48Spatrick continue;
403009467b48Spatrick }
403109467b48Spatrick // At this point, we know it is a Use we are trying to possibly
403209467b48Spatrick // replace.
403309467b48Spatrick
403409467b48Spatrick assert(isa<Instruction>(U->get()) &&
403509467b48Spatrick "Current def should have been an instruction");
403609467b48Spatrick assert(isa<Instruction>(U->getUser()) &&
403709467b48Spatrick "Current user should have been an instruction");
403809467b48Spatrick
403909467b48Spatrick // If the thing we are replacing into is already marked to be dead,
404009467b48Spatrick // this use is dead. Note that this is true regardless of whether
404109467b48Spatrick // we have anything dominating the use or not. We do this here
404209467b48Spatrick // because we are already walking all the uses anyway.
404309467b48Spatrick Instruction *InstUse = cast<Instruction>(U->getUser());
404409467b48Spatrick if (InstructionsToErase.count(InstUse)) {
404509467b48Spatrick auto &UseCount = UseCounts[U->get()];
404609467b48Spatrick if (--UseCount == 0) {
404709467b48Spatrick ProbablyDead.insert(cast<Instruction>(U->get()));
404809467b48Spatrick }
404909467b48Spatrick }
405009467b48Spatrick
405109467b48Spatrick // If we get to this point, and the stack is empty we must have a use
405209467b48Spatrick // with nothing we can use to eliminate this use, so just skip it.
405309467b48Spatrick if (EliminationStack.empty())
405409467b48Spatrick continue;
405509467b48Spatrick
405609467b48Spatrick Value *DominatingLeader = EliminationStack.back();
405709467b48Spatrick
405809467b48Spatrick auto *II = dyn_cast<IntrinsicInst>(DominatingLeader);
405909467b48Spatrick bool isSSACopy = II && II->getIntrinsicID() == Intrinsic::ssa_copy;
406009467b48Spatrick if (isSSACopy)
406109467b48Spatrick DominatingLeader = II->getOperand(0);
406209467b48Spatrick
406309467b48Spatrick // Don't replace our existing users with ourselves.
406409467b48Spatrick if (U->get() == DominatingLeader)
406509467b48Spatrick continue;
406609467b48Spatrick LLVM_DEBUG(dbgs()
406709467b48Spatrick << "Found replacement " << *DominatingLeader << " for "
406809467b48Spatrick << *U->get() << " in " << *(U->getUser()) << "\n");
406909467b48Spatrick
407009467b48Spatrick // If we replaced something in an instruction, handle the patching of
407109467b48Spatrick // metadata. Skip this if we are replacing predicateinfo with its
407209467b48Spatrick // original operand, as we already know we can just drop it.
407309467b48Spatrick auto *ReplacedInst = cast<Instruction>(U->get());
407409467b48Spatrick auto *PI = PredInfo->getPredicateInfoFor(ReplacedInst);
407509467b48Spatrick if (!PI || DominatingLeader != PI->OriginalOp)
407609467b48Spatrick patchReplacementInstruction(ReplacedInst, DominatingLeader);
407709467b48Spatrick U->set(DominatingLeader);
407809467b48Spatrick // This is now a use of the dominating leader, which means if the
407909467b48Spatrick // dominating leader was dead, it's now live!
408009467b48Spatrick auto &LeaderUseCount = UseCounts[DominatingLeader];
408109467b48Spatrick // It's about to be alive again.
408209467b48Spatrick if (LeaderUseCount == 0 && isa<Instruction>(DominatingLeader))
408309467b48Spatrick ProbablyDead.erase(cast<Instruction>(DominatingLeader));
408409467b48Spatrick // For copy instructions, we use their operand as a leader,
408509467b48Spatrick // which means we remove a user of the copy and it may become dead.
408609467b48Spatrick if (isSSACopy) {
408709467b48Spatrick unsigned &IIUseCount = UseCounts[II];
408809467b48Spatrick if (--IIUseCount == 0)
408909467b48Spatrick ProbablyDead.insert(II);
409009467b48Spatrick }
409109467b48Spatrick ++LeaderUseCount;
409209467b48Spatrick AnythingReplaced = true;
409309467b48Spatrick }
409409467b48Spatrick }
409509467b48Spatrick }
409609467b48Spatrick
409709467b48Spatrick // At this point, anything still in the ProbablyDead set is actually dead if
409809467b48Spatrick // would be trivially dead.
409909467b48Spatrick for (auto *I : ProbablyDead)
410009467b48Spatrick if (wouldInstructionBeTriviallyDead(I))
410109467b48Spatrick markInstructionForDeletion(I);
410209467b48Spatrick
410309467b48Spatrick // Cleanup the congruence class.
410409467b48Spatrick CongruenceClass::MemberSet MembersLeft;
410509467b48Spatrick for (auto *Member : *CC)
410609467b48Spatrick if (!isa<Instruction>(Member) ||
410709467b48Spatrick !InstructionsToErase.count(cast<Instruction>(Member)))
410809467b48Spatrick MembersLeft.insert(Member);
410909467b48Spatrick CC->swap(MembersLeft);
411009467b48Spatrick
411109467b48Spatrick // If we have possible dead stores to look at, try to eliminate them.
411209467b48Spatrick if (CC->getStoreCount() > 0) {
411309467b48Spatrick convertClassToLoadsAndStores(*CC, PossibleDeadStores);
411409467b48Spatrick llvm::sort(PossibleDeadStores);
411509467b48Spatrick ValueDFSStack EliminationStack;
411609467b48Spatrick for (auto &VD : PossibleDeadStores) {
411709467b48Spatrick int MemberDFSIn = VD.DFSIn;
411809467b48Spatrick int MemberDFSOut = VD.DFSOut;
411909467b48Spatrick Instruction *Member = cast<Instruction>(VD.Def.getPointer());
412009467b48Spatrick if (EliminationStack.empty() ||
412109467b48Spatrick !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut)) {
412209467b48Spatrick // Sync to our current scope.
412309467b48Spatrick EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
412409467b48Spatrick if (EliminationStack.empty()) {
412509467b48Spatrick EliminationStack.push_back(Member, MemberDFSIn, MemberDFSOut);
412609467b48Spatrick continue;
412709467b48Spatrick }
412809467b48Spatrick }
412909467b48Spatrick // We already did load elimination, so nothing to do here.
413009467b48Spatrick if (isa<LoadInst>(Member))
413109467b48Spatrick continue;
413209467b48Spatrick assert(!EliminationStack.empty());
413309467b48Spatrick Instruction *Leader = cast<Instruction>(EliminationStack.back());
413409467b48Spatrick (void)Leader;
413509467b48Spatrick assert(DT->dominates(Leader->getParent(), Member->getParent()));
413609467b48Spatrick // Member is dominater by Leader, and thus dead
413709467b48Spatrick LLVM_DEBUG(dbgs() << "Marking dead store " << *Member
413809467b48Spatrick << " that is dominated by " << *Leader << "\n");
413909467b48Spatrick markInstructionForDeletion(Member);
414009467b48Spatrick CC->erase(Member);
414109467b48Spatrick ++NumGVNDeadStores;
414209467b48Spatrick }
414309467b48Spatrick }
414409467b48Spatrick }
414509467b48Spatrick return AnythingReplaced;
414609467b48Spatrick }
414709467b48Spatrick
414809467b48Spatrick // This function provides global ranking of operations so that we can place them
414909467b48Spatrick // in a canonical order. Note that rank alone is not necessarily enough for a
415009467b48Spatrick // complete ordering, as constants all have the same rank. However, generally,
415109467b48Spatrick // we will simplify an operation with all constants so that it doesn't matter
415209467b48Spatrick // what order they appear in.
getRank(const Value * V) const415309467b48Spatrick unsigned int NewGVN::getRank(const Value *V) const {
415409467b48Spatrick // Prefer constants to undef to anything else
415509467b48Spatrick // Undef is a constant, have to check it first.
4156*d415bd75Srobert // Prefer poison to undef as it's less defined.
415709467b48Spatrick // Prefer smaller constants to constantexprs
4158*d415bd75Srobert // Note that the order here matters because of class inheritance
415909467b48Spatrick if (isa<ConstantExpr>(V))
4160*d415bd75Srobert return 3;
4161*d415bd75Srobert if (isa<PoisonValue>(V))
416209467b48Spatrick return 1;
4163*d415bd75Srobert if (isa<UndefValue>(V))
4164*d415bd75Srobert return 2;
416509467b48Spatrick if (isa<Constant>(V))
416609467b48Spatrick return 0;
4167*d415bd75Srobert if (auto *A = dyn_cast<Argument>(V))
4168*d415bd75Srobert return 4 + A->getArgNo();
416909467b48Spatrick
4170*d415bd75Srobert // Need to shift the instruction DFS by number of arguments + 5 to account for
417109467b48Spatrick // the constant and argument ranking above.
417209467b48Spatrick unsigned Result = InstrToDFSNum(V);
417309467b48Spatrick if (Result > 0)
4174*d415bd75Srobert return 5 + NumFuncArgs + Result;
417509467b48Spatrick // Unreachable or something else, just return a really large number.
417609467b48Spatrick return ~0;
417709467b48Spatrick }
417809467b48Spatrick
417909467b48Spatrick // This is a function that says whether two commutative operations should
418009467b48Spatrick // have their order swapped when canonicalizing.
shouldSwapOperands(const Value * A,const Value * B) const418109467b48Spatrick bool NewGVN::shouldSwapOperands(const Value *A, const Value *B) const {
418209467b48Spatrick // Because we only care about a total ordering, and don't rewrite expressions
418309467b48Spatrick // in this order, we order by rank, which will give a strict weak ordering to
418409467b48Spatrick // everything but constants, and then we order by pointer address.
418509467b48Spatrick return std::make_pair(getRank(A), A) > std::make_pair(getRank(B), B);
418609467b48Spatrick }
418709467b48Spatrick
shouldSwapOperandsForIntrinsic(const Value * A,const Value * B,const IntrinsicInst * I) const4188*d415bd75Srobert bool NewGVN::shouldSwapOperandsForIntrinsic(const Value *A, const Value *B,
4189*d415bd75Srobert const IntrinsicInst *I) const {
4190*d415bd75Srobert auto LookupResult = IntrinsicInstPred.find(I);
4191*d415bd75Srobert if (shouldSwapOperands(A, B)) {
4192*d415bd75Srobert if (LookupResult == IntrinsicInstPred.end())
4193*d415bd75Srobert IntrinsicInstPred.insert({I, B});
4194*d415bd75Srobert else
4195*d415bd75Srobert LookupResult->second = B;
4196*d415bd75Srobert return true;
4197*d415bd75Srobert }
4198*d415bd75Srobert
4199*d415bd75Srobert if (LookupResult != IntrinsicInstPred.end()) {
4200*d415bd75Srobert auto *SeenPredicate = LookupResult->second;
4201*d415bd75Srobert if (SeenPredicate) {
4202*d415bd75Srobert if (SeenPredicate == B)
4203*d415bd75Srobert return true;
4204*d415bd75Srobert else
4205*d415bd75Srobert LookupResult->second = nullptr;
4206*d415bd75Srobert }
4207*d415bd75Srobert }
4208*d415bd75Srobert return false;
4209*d415bd75Srobert }
4210*d415bd75Srobert
421109467b48Spatrick namespace {
421209467b48Spatrick
421309467b48Spatrick class NewGVNLegacyPass : public FunctionPass {
421409467b48Spatrick public:
421509467b48Spatrick // Pass identification, replacement for typeid.
421609467b48Spatrick static char ID;
421709467b48Spatrick
NewGVNLegacyPass()421809467b48Spatrick NewGVNLegacyPass() : FunctionPass(ID) {
421909467b48Spatrick initializeNewGVNLegacyPassPass(*PassRegistry::getPassRegistry());
422009467b48Spatrick }
422109467b48Spatrick
422209467b48Spatrick bool runOnFunction(Function &F) override;
422309467b48Spatrick
422409467b48Spatrick private:
getAnalysisUsage(AnalysisUsage & AU) const422509467b48Spatrick void getAnalysisUsage(AnalysisUsage &AU) const override {
422609467b48Spatrick AU.addRequired<AssumptionCacheTracker>();
422709467b48Spatrick AU.addRequired<DominatorTreeWrapperPass>();
422809467b48Spatrick AU.addRequired<TargetLibraryInfoWrapperPass>();
422909467b48Spatrick AU.addRequired<MemorySSAWrapperPass>();
423009467b48Spatrick AU.addRequired<AAResultsWrapperPass>();
423109467b48Spatrick AU.addPreserved<DominatorTreeWrapperPass>();
423209467b48Spatrick AU.addPreserved<GlobalsAAWrapperPass>();
423309467b48Spatrick }
423409467b48Spatrick };
423509467b48Spatrick
423609467b48Spatrick } // end anonymous namespace
423709467b48Spatrick
runOnFunction(Function & F)423809467b48Spatrick bool NewGVNLegacyPass::runOnFunction(Function &F) {
423909467b48Spatrick if (skipFunction(F))
424009467b48Spatrick return false;
424109467b48Spatrick return NewGVN(F, &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
424209467b48Spatrick &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F),
424309467b48Spatrick &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F),
424409467b48Spatrick &getAnalysis<AAResultsWrapperPass>().getAAResults(),
424509467b48Spatrick &getAnalysis<MemorySSAWrapperPass>().getMSSA(),
424609467b48Spatrick F.getParent()->getDataLayout())
424709467b48Spatrick .runGVN();
424809467b48Spatrick }
424909467b48Spatrick
425009467b48Spatrick char NewGVNLegacyPass::ID = 0;
425109467b48Spatrick
425209467b48Spatrick INITIALIZE_PASS_BEGIN(NewGVNLegacyPass, "newgvn", "Global Value Numbering",
425309467b48Spatrick false, false)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)425409467b48Spatrick INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
425509467b48Spatrick INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
425609467b48Spatrick INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
425709467b48Spatrick INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
425809467b48Spatrick INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
425909467b48Spatrick INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
426009467b48Spatrick INITIALIZE_PASS_END(NewGVNLegacyPass, "newgvn", "Global Value Numbering", false,
426109467b48Spatrick false)
426209467b48Spatrick
426309467b48Spatrick // createGVNPass - The public interface to this file.
426409467b48Spatrick FunctionPass *llvm::createNewGVNPass() { return new NewGVNLegacyPass(); }
426509467b48Spatrick
run(Function & F,AnalysisManager<Function> & AM)426609467b48Spatrick PreservedAnalyses NewGVNPass::run(Function &F, AnalysisManager<Function> &AM) {
426709467b48Spatrick // Apparently the order in which we get these results matter for
426809467b48Spatrick // the old GVN (see Chandler's comment in GVN.cpp). I'll keep
426909467b48Spatrick // the same order here, just in case.
427009467b48Spatrick auto &AC = AM.getResult<AssumptionAnalysis>(F);
427109467b48Spatrick auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
427209467b48Spatrick auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
427309467b48Spatrick auto &AA = AM.getResult<AAManager>(F);
427409467b48Spatrick auto &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
427509467b48Spatrick bool Changed =
427609467b48Spatrick NewGVN(F, &DT, &AC, &TLI, &AA, &MSSA, F.getParent()->getDataLayout())
427709467b48Spatrick .runGVN();
427809467b48Spatrick if (!Changed)
427909467b48Spatrick return PreservedAnalyses::all();
428009467b48Spatrick PreservedAnalyses PA;
428109467b48Spatrick PA.preserve<DominatorTreeAnalysis>();
428209467b48Spatrick return PA;
428309467b48Spatrick }
4284