1327952Sdim//===- NewGVN.cpp - Global Value Numbering Pass ---------------------------===// 2311116Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6311116Sdim// 7311116Sdim//===----------------------------------------------------------------------===// 8327952Sdim// 9311116Sdim/// \file 10311116Sdim/// This file implements the new LLVM's Global Value Numbering pass. 11311116Sdim/// GVN partitions values computed by a function into congruence classes. 12311116Sdim/// Values ending up in the same congruence class are guaranteed to be the same 13311116Sdim/// for every execution of the program. In that respect, congruency is a 14311116Sdim/// compile-time approximation of equivalence of values at runtime. 15311116Sdim/// The algorithm implemented here uses a sparse formulation and it's based 16311116Sdim/// on the ideas described in the paper: 17311116Sdim/// "A Sparse Algorithm for Predicated Global Value Numbering" from 18311116Sdim/// Karthik Gargi. 19311116Sdim/// 20321369Sdim/// A brief overview of the algorithm: The algorithm is essentially the same as 21321369Sdim/// the standard RPO value numbering algorithm (a good reference is the paper 22321369Sdim/// "SCC based value numbering" by L. Taylor Simpson) with one major difference: 23321369Sdim/// The RPO algorithm proceeds, on every iteration, to process every reachable 24321369Sdim/// block and every instruction in that block. This is because the standard RPO 25321369Sdim/// algorithm does not track what things have the same value number, it only 26321369Sdim/// tracks what the value number of a given operation is (the mapping is 27321369Sdim/// operation -> value number). Thus, when a value number of an operation 28321369Sdim/// changes, it must reprocess everything to ensure all uses of a value number 29321369Sdim/// get updated properly. In constrast, the sparse algorithm we use *also* 30321369Sdim/// tracks what operations have a given value number (IE it also tracks the 31321369Sdim/// reverse mapping from value number -> operations with that value number), so 32321369Sdim/// that it only needs to reprocess the instructions that are affected when 33321369Sdim/// something's value number changes. The vast majority of complexity and code 34321369Sdim/// in this file is devoted to tracking what value numbers could change for what 35321369Sdim/// instructions when various things happen. The rest of the algorithm is 36321369Sdim/// devoted to performing symbolic evaluation, forward propagation, and 37321369Sdim/// simplification of operations based on the value numbers deduced so far 38321369Sdim/// 39321369Sdim/// In order to make the GVN mostly-complete, we use a technique derived from 40321369Sdim/// "Detection of Redundant Expressions: A Complete and Polynomial-time 41321369Sdim/// Algorithm in SSA" by R.R. Pai. The source of incompleteness in most SSA 42321369Sdim/// based GVN algorithms is related to their inability to detect equivalence 43321369Sdim/// between phi of ops (IE phi(a+b, c+d)) and op of phis (phi(a,c) + phi(b, d)). 44321369Sdim/// We resolve this issue by generating the equivalent "phi of ops" form for 45321369Sdim/// each op of phis we see, in a way that only takes polynomial time to resolve. 46321369Sdim/// 47321369Sdim/// We also do not perform elimination by using any published algorithm. All 48321369Sdim/// published algorithms are O(Instructions). Instead, we use a technique that 49321369Sdim/// is O(number of operations with the same value number), enabling us to skip 50321369Sdim/// trying to eliminate things that have unique value numbers. 51327952Sdim// 52311116Sdim//===----------------------------------------------------------------------===// 53311116Sdim 54311116Sdim#include "llvm/Transforms/Scalar/NewGVN.h" 55327952Sdim#include "llvm/ADT/ArrayRef.h" 56311116Sdim#include "llvm/ADT/BitVector.h" 57311116Sdim#include "llvm/ADT/DenseMap.h" 58327952Sdim#include "llvm/ADT/DenseMapInfo.h" 59311116Sdim#include "llvm/ADT/DenseSet.h" 60311116Sdim#include "llvm/ADT/DepthFirstIterator.h" 61327952Sdim#include "llvm/ADT/GraphTraits.h" 62311116Sdim#include "llvm/ADT/Hashing.h" 63327952Sdim#include "llvm/ADT/PointerIntPair.h" 64311116Sdim#include "llvm/ADT/PostOrderIterator.h" 65311116Sdim#include "llvm/ADT/SmallPtrSet.h" 66327952Sdim#include "llvm/ADT/SmallVector.h" 67327952Sdim#include "llvm/ADT/SparseBitVector.h" 68311116Sdim#include "llvm/ADT/Statistic.h" 69327952Sdim#include "llvm/ADT/iterator_range.h" 70311116Sdim#include "llvm/Analysis/AliasAnalysis.h" 71311116Sdim#include "llvm/Analysis/AssumptionCache.h" 72311116Sdim#include "llvm/Analysis/CFGPrinter.h" 73311116Sdim#include "llvm/Analysis/ConstantFolding.h" 74311116Sdim#include "llvm/Analysis/GlobalsModRef.h" 75311116Sdim#include "llvm/Analysis/InstructionSimplify.h" 76311116Sdim#include "llvm/Analysis/MemoryBuiltins.h" 77321369Sdim#include "llvm/Analysis/MemorySSA.h" 78311116Sdim#include "llvm/Analysis/TargetLibraryInfo.h" 79327952Sdim#include "llvm/IR/Argument.h" 80327952Sdim#include "llvm/IR/BasicBlock.h" 81327952Sdim#include "llvm/IR/Constant.h" 82327952Sdim#include "llvm/IR/Constants.h" 83311116Sdim#include "llvm/IR/Dominators.h" 84327952Sdim#include "llvm/IR/Function.h" 85327952Sdim#include "llvm/IR/InstrTypes.h" 86327952Sdim#include "llvm/IR/Instruction.h" 87327952Sdim#include "llvm/IR/Instructions.h" 88311116Sdim#include "llvm/IR/IntrinsicInst.h" 89327952Sdim#include "llvm/IR/Intrinsics.h" 90311116Sdim#include "llvm/IR/LLVMContext.h" 91360784Sdim#include "llvm/IR/PatternMatch.h" 92311116Sdim#include "llvm/IR/Type.h" 93327952Sdim#include "llvm/IR/Use.h" 94327952Sdim#include "llvm/IR/User.h" 95327952Sdim#include "llvm/IR/Value.h" 96360784Sdim#include "llvm/InitializePasses.h" 97327952Sdim#include "llvm/Pass.h" 98311116Sdim#include "llvm/Support/Allocator.h" 99327952Sdim#include "llvm/Support/ArrayRecycler.h" 100327952Sdim#include "llvm/Support/Casting.h" 101311116Sdim#include "llvm/Support/CommandLine.h" 102311116Sdim#include "llvm/Support/Debug.h" 103321369Sdim#include "llvm/Support/DebugCounter.h" 104327952Sdim#include "llvm/Support/ErrorHandling.h" 105327952Sdim#include "llvm/Support/PointerLikeTypeTraits.h" 106327952Sdim#include "llvm/Support/raw_ostream.h" 107311116Sdim#include "llvm/Transforms/Scalar.h" 108311116Sdim#include "llvm/Transforms/Scalar/GVNExpression.h" 109360784Sdim#include "llvm/Transforms/Utils/Local.h" 110321369Sdim#include "llvm/Transforms/Utils/PredicateInfo.h" 111321369Sdim#include "llvm/Transforms/Utils/VNCoercion.h" 112327952Sdim#include <algorithm> 113327952Sdim#include <cassert> 114327952Sdim#include <cstdint> 115327952Sdim#include <iterator> 116327952Sdim#include <map> 117327952Sdim#include <memory> 118327952Sdim#include <set> 119327952Sdim#include <string> 120327952Sdim#include <tuple> 121311116Sdim#include <utility> 122311116Sdim#include <vector> 123327952Sdim 124311116Sdimusing namespace llvm; 125311116Sdimusing namespace llvm::GVNExpression; 126321369Sdimusing namespace llvm::VNCoercion; 127360784Sdimusing namespace llvm::PatternMatch; 128327952Sdim 129311116Sdim#define DEBUG_TYPE "newgvn" 130311116Sdim 131311116SdimSTATISTIC(NumGVNInstrDeleted, "Number of instructions deleted"); 132311116SdimSTATISTIC(NumGVNBlocksDeleted, "Number of blocks deleted"); 133311116SdimSTATISTIC(NumGVNOpsSimplified, "Number of Expressions simplified"); 134311116SdimSTATISTIC(NumGVNPhisAllSame, "Number of PHIs whos arguments are all the same"); 135311833SdimSTATISTIC(NumGVNMaxIterations, 136311833Sdim "Maximum Number of iterations it took to converge GVN"); 137312639SdimSTATISTIC(NumGVNLeaderChanges, "Number of leader changes"); 138312639SdimSTATISTIC(NumGVNSortedLeaderChanges, "Number of sorted leader changes"); 139312639SdimSTATISTIC(NumGVNAvoidedSortedLeaderChanges, 140312639Sdim "Number of avoided sorted leader changes"); 141321369SdimSTATISTIC(NumGVNDeadStores, "Number of redundant/dead stores eliminated"); 142321369SdimSTATISTIC(NumGVNPHIOfOpsCreated, "Number of PHI of ops created"); 143321369SdimSTATISTIC(NumGVNPHIOfOpsEliminations, 144321369Sdim "Number of things eliminated using PHI of ops"); 145321369SdimDEBUG_COUNTER(VNCounter, "newgvn-vn", 146327952Sdim "Controls which instructions are value numbered"); 147321369SdimDEBUG_COUNTER(PHIOfOpsCounter, "newgvn-phi", 148327952Sdim "Controls which instructions we create phi of ops for"); 149321369Sdim// Currently store defining access refinement is too slow due to basicaa being 150321369Sdim// egregiously slow. This flag lets us keep it working while we work on this 151321369Sdim// issue. 152321369Sdimstatic cl::opt<bool> EnableStoreRefinement("enable-store-refinement", 153321369Sdim cl::init(false), cl::Hidden); 154311116Sdim 155327952Sdim/// Currently, the generation "phi of ops" can result in correctness issues. 156327952Sdimstatic cl::opt<bool> EnablePhiOfOps("enable-phi-of-ops", cl::init(true), 157327952Sdim cl::Hidden); 158327952Sdim 159311116Sdim//===----------------------------------------------------------------------===// 160311116Sdim// GVN Pass 161311116Sdim//===----------------------------------------------------------------------===// 162311116Sdim 163311116Sdim// Anchor methods. 164311116Sdimnamespace llvm { 165311116Sdimnamespace GVNExpression { 166327952Sdim 167311116SdimExpression::~Expression() = default; 168311116SdimBasicExpression::~BasicExpression() = default; 169311116SdimCallExpression::~CallExpression() = default; 170311116SdimLoadExpression::~LoadExpression() = default; 171311116SdimStoreExpression::~StoreExpression() = default; 172311116SdimAggregateValueExpression::~AggregateValueExpression() = default; 173311116SdimPHIExpression::~PHIExpression() = default; 174311116Sdim 175327952Sdim} // end namespace GVNExpression 176327952Sdim} // end namespace llvm 177327952Sdim 178327952Sdimnamespace { 179327952Sdim 180321369Sdim// Tarjan's SCC finding algorithm with Nuutila's improvements 181321369Sdim// SCCIterator is actually fairly complex for the simple thing we want. 182321369Sdim// It also wants to hand us SCC's that are unrelated to the phi node we ask 183321369Sdim// about, and have us process them there or risk redoing work. 184321369Sdim// Graph traits over a filter iterator also doesn't work that well here. 185321369Sdim// This SCC finder is specialized to walk use-def chains, and only follows 186321369Sdim// instructions, 187321369Sdim// not generic values (arguments, etc). 188321369Sdimstruct TarjanSCC { 189321369Sdim TarjanSCC() : Components(1) {} 190321369Sdim 191321369Sdim void Start(const Instruction *Start) { 192321369Sdim if (Root.lookup(Start) == 0) 193321369Sdim FindSCC(Start); 194321369Sdim } 195321369Sdim 196321369Sdim const SmallPtrSetImpl<const Value *> &getComponentFor(const Value *V) const { 197321369Sdim unsigned ComponentID = ValueToComponent.lookup(V); 198321369Sdim 199321369Sdim assert(ComponentID > 0 && 200321369Sdim "Asking for a component for a value we never processed"); 201321369Sdim return Components[ComponentID]; 202321369Sdim } 203321369Sdim 204321369Sdimprivate: 205321369Sdim void FindSCC(const Instruction *I) { 206321369Sdim Root[I] = ++DFSNum; 207321369Sdim // Store the DFS Number we had before it possibly gets incremented. 208321369Sdim unsigned int OurDFS = DFSNum; 209321369Sdim for (auto &Op : I->operands()) { 210321369Sdim if (auto *InstOp = dyn_cast<Instruction>(Op)) { 211321369Sdim if (Root.lookup(Op) == 0) 212321369Sdim FindSCC(InstOp); 213321369Sdim if (!InComponent.count(Op)) 214321369Sdim Root[I] = std::min(Root.lookup(I), Root.lookup(Op)); 215321369Sdim } 216321369Sdim } 217321369Sdim // See if we really were the root of a component, by seeing if we still have 218321369Sdim // our DFSNumber. If we do, we are the root of the component, and we have 219321369Sdim // completed a component. If we do not, we are not the root of a component, 220321369Sdim // and belong on the component stack. 221321369Sdim if (Root.lookup(I) == OurDFS) { 222321369Sdim unsigned ComponentID = Components.size(); 223321369Sdim Components.resize(Components.size() + 1); 224321369Sdim auto &Component = Components.back(); 225321369Sdim Component.insert(I); 226341825Sdim LLVM_DEBUG(dbgs() << "Component root is " << *I << "\n"); 227321369Sdim InComponent.insert(I); 228321369Sdim ValueToComponent[I] = ComponentID; 229321369Sdim // Pop a component off the stack and label it. 230321369Sdim while (!Stack.empty() && Root.lookup(Stack.back()) >= OurDFS) { 231321369Sdim auto *Member = Stack.back(); 232341825Sdim LLVM_DEBUG(dbgs() << "Component member is " << *Member << "\n"); 233321369Sdim Component.insert(Member); 234321369Sdim InComponent.insert(Member); 235321369Sdim ValueToComponent[Member] = ComponentID; 236321369Sdim Stack.pop_back(); 237321369Sdim } 238321369Sdim } else { 239321369Sdim // Part of a component, push to stack 240321369Sdim Stack.push_back(I); 241321369Sdim } 242321369Sdim } 243327952Sdim 244321369Sdim unsigned int DFSNum = 1; 245321369Sdim SmallPtrSet<const Value *, 8> InComponent; 246321369Sdim DenseMap<const Value *, unsigned int> Root; 247321369Sdim SmallVector<const Value *, 8> Stack; 248327952Sdim 249321369Sdim // Store the components as vector of ptr sets, because we need the topo order 250321369Sdim // of SCC's, but not individual member order 251321369Sdim SmallVector<SmallPtrSet<const Value *, 8>, 8> Components; 252327952Sdim 253321369Sdim DenseMap<const Value *, unsigned> ValueToComponent; 254321369Sdim}; 255327952Sdim 256311116Sdim// Congruence classes represent the set of expressions/instructions 257311116Sdim// that are all the same *during some scope in the function*. 258311116Sdim// That is, because of the way we perform equality propagation, and 259311116Sdim// because of memory value numbering, it is not correct to assume 260311116Sdim// you can willy-nilly replace any member with any other at any 261311116Sdim// point in the function. 262311116Sdim// 263311116Sdim// For any Value in the Member set, it is valid to replace any dominated member 264311116Sdim// with that Value. 265311116Sdim// 266321369Sdim// Every congruence class has a leader, and the leader is used to symbolize 267321369Sdim// instructions in a canonical way (IE every operand of an instruction that is a 268321369Sdim// member of the same congruence class will always be replaced with leader 269321369Sdim// during symbolization). To simplify symbolization, we keep the leader as a 270321369Sdim// constant if class can be proved to be a constant value. Otherwise, the 271321369Sdim// leader is the member of the value set with the smallest DFS number. Each 272321369Sdim// congruence class also has a defining expression, though the expression may be 273321369Sdim// null. If it exists, it can be used for forward propagation and reassociation 274321369Sdim// of values. 275321369Sdim 276321369Sdim// For memory, we also track a representative MemoryAccess, and a set of memory 277321369Sdim// members for MemoryPhis (which have no real instructions). Note that for 278321369Sdim// memory, it seems tempting to try to split the memory members into a 279321369Sdim// MemoryCongruenceClass or something. Unfortunately, this does not work 280321369Sdim// easily. The value numbering of a given memory expression depends on the 281321369Sdim// leader of the memory congruence class, and the leader of memory congruence 282321369Sdim// class depends on the value numbering of a given memory expression. This 283321369Sdim// leads to wasted propagation, and in some cases, missed optimization. For 284321369Sdim// example: If we had value numbered two stores together before, but now do not, 285321369Sdim// we move them to a new value congruence class. This in turn will move at one 286321369Sdim// of the memorydefs to a new memory congruence class. Which in turn, affects 287321369Sdim// the value numbering of the stores we just value numbered (because the memory 288321369Sdim// congruence class is part of the value number). So while theoretically 289321369Sdim// possible to split them up, it turns out to be *incredibly* complicated to get 290321369Sdim// it to work right, because of the interdependency. While structurally 291321369Sdim// slightly messier, it is algorithmically much simpler and faster to do what we 292321369Sdim// do here, and track them both at once in the same class. 293321369Sdim// Note: The default iterators for this class iterate over values 294321369Sdimclass CongruenceClass { 295321369Sdimpublic: 296321369Sdim using MemberType = Value; 297321369Sdim using MemberSet = SmallPtrSet<MemberType *, 4>; 298321369Sdim using MemoryMemberType = MemoryPhi; 299321369Sdim using MemoryMemberSet = SmallPtrSet<const MemoryMemberType *, 2>; 300321369Sdim 301321369Sdim explicit CongruenceClass(unsigned ID) : ID(ID) {} 302321369Sdim CongruenceClass(unsigned ID, Value *Leader, const Expression *E) 303321369Sdim : ID(ID), RepLeader(Leader), DefiningExpr(E) {} 304327952Sdim 305321369Sdim unsigned getID() const { return ID; } 306327952Sdim 307321369Sdim // True if this class has no members left. This is mainly used for assertion 308321369Sdim // purposes, and for skipping empty classes. 309321369Sdim bool isDead() const { 310321369Sdim // If it's both dead from a value perspective, and dead from a memory 311321369Sdim // perspective, it's really dead. 312321369Sdim return empty() && memory_empty(); 313321369Sdim } 314327952Sdim 315321369Sdim // Leader functions 316321369Sdim Value *getLeader() const { return RepLeader; } 317321369Sdim void setLeader(Value *Leader) { RepLeader = Leader; } 318321369Sdim const std::pair<Value *, unsigned int> &getNextLeader() const { 319321369Sdim return NextLeader; 320321369Sdim } 321321369Sdim void resetNextLeader() { NextLeader = {nullptr, ~0}; } 322321369Sdim void addPossibleNextLeader(std::pair<Value *, unsigned int> LeaderPair) { 323321369Sdim if (LeaderPair.second < NextLeader.second) 324321369Sdim NextLeader = LeaderPair; 325321369Sdim } 326321369Sdim 327321369Sdim Value *getStoredValue() const { return RepStoredValue; } 328321369Sdim void setStoredValue(Value *Leader) { RepStoredValue = Leader; } 329321369Sdim const MemoryAccess *getMemoryLeader() const { return RepMemoryAccess; } 330321369Sdim void setMemoryLeader(const MemoryAccess *Leader) { RepMemoryAccess = Leader; } 331321369Sdim 332321369Sdim // Forward propagation info 333321369Sdim const Expression *getDefiningExpr() const { return DefiningExpr; } 334321369Sdim 335321369Sdim // Value member set 336321369Sdim bool empty() const { return Members.empty(); } 337321369Sdim unsigned size() const { return Members.size(); } 338321369Sdim MemberSet::const_iterator begin() const { return Members.begin(); } 339321369Sdim MemberSet::const_iterator end() const { return Members.end(); } 340321369Sdim void insert(MemberType *M) { Members.insert(M); } 341321369Sdim void erase(MemberType *M) { Members.erase(M); } 342321369Sdim void swap(MemberSet &Other) { Members.swap(Other); } 343321369Sdim 344321369Sdim // Memory member set 345321369Sdim bool memory_empty() const { return MemoryMembers.empty(); } 346321369Sdim unsigned memory_size() const { return MemoryMembers.size(); } 347321369Sdim MemoryMemberSet::const_iterator memory_begin() const { 348321369Sdim return MemoryMembers.begin(); 349321369Sdim } 350321369Sdim MemoryMemberSet::const_iterator memory_end() const { 351321369Sdim return MemoryMembers.end(); 352321369Sdim } 353321369Sdim iterator_range<MemoryMemberSet::const_iterator> memory() const { 354321369Sdim return make_range(memory_begin(), memory_end()); 355321369Sdim } 356327952Sdim 357321369Sdim void memory_insert(const MemoryMemberType *M) { MemoryMembers.insert(M); } 358321369Sdim void memory_erase(const MemoryMemberType *M) { MemoryMembers.erase(M); } 359321369Sdim 360321369Sdim // Store count 361321369Sdim unsigned getStoreCount() const { return StoreCount; } 362321369Sdim void incStoreCount() { ++StoreCount; } 363321369Sdim void decStoreCount() { 364321369Sdim assert(StoreCount != 0 && "Store count went negative"); 365321369Sdim --StoreCount; 366321369Sdim } 367321369Sdim 368321369Sdim // True if this class has no memory members. 369321369Sdim bool definesNoMemory() const { return StoreCount == 0 && memory_empty(); } 370321369Sdim 371341825Sdim // Return true if two congruence classes are equivalent to each other. This 372341825Sdim // means that every field but the ID number and the dead field are equivalent. 373321369Sdim bool isEquivalentTo(const CongruenceClass *Other) const { 374321369Sdim if (!Other) 375321369Sdim return false; 376321369Sdim if (this == Other) 377321369Sdim return true; 378321369Sdim 379321369Sdim if (std::tie(StoreCount, RepLeader, RepStoredValue, RepMemoryAccess) != 380321369Sdim std::tie(Other->StoreCount, Other->RepLeader, Other->RepStoredValue, 381321369Sdim Other->RepMemoryAccess)) 382321369Sdim return false; 383321369Sdim if (DefiningExpr != Other->DefiningExpr) 384321369Sdim if (!DefiningExpr || !Other->DefiningExpr || 385321369Sdim *DefiningExpr != *Other->DefiningExpr) 386321369Sdim return false; 387341825Sdim 388341825Sdim if (Members.size() != Other->Members.size()) 389341825Sdim return false; 390341825Sdim 391341825Sdim return all_of(Members, 392341825Sdim [&](const Value *V) { return Other->Members.count(V); }); 393321369Sdim } 394321369Sdim 395321369Sdimprivate: 396311116Sdim unsigned ID; 397327952Sdim 398311116Sdim // Representative leader. 399311116Sdim Value *RepLeader = nullptr; 400327952Sdim 401321369Sdim // The most dominating leader after our current leader, because the member set 402321369Sdim // is not sorted and is expensive to keep sorted all the time. 403321369Sdim std::pair<Value *, unsigned int> NextLeader = {nullptr, ~0U}; 404327952Sdim 405321369Sdim // If this is represented by a store, the value of the store. 406321369Sdim Value *RepStoredValue = nullptr; 407327952Sdim 408321369Sdim // If this class contains MemoryDefs or MemoryPhis, this is the leading memory 409321369Sdim // access. 410321369Sdim const MemoryAccess *RepMemoryAccess = nullptr; 411327952Sdim 412311116Sdim // Defining Expression. 413311116Sdim const Expression *DefiningExpr = nullptr; 414327952Sdim 415311116Sdim // Actual members of this class. 416311116Sdim MemberSet Members; 417327952Sdim 418321369Sdim // This is the set of MemoryPhis that exist in the class. MemoryDefs and 419321369Sdim // MemoryUses have real instructions representing them, so we only need to 420321369Sdim // track MemoryPhis here. 421321369Sdim MemoryMemberSet MemoryMembers; 422327952Sdim 423312197Sdim // Number of stores in this congruence class. 424312197Sdim // This is used so we can detect store equivalence changes properly. 425312197Sdim int StoreCount = 0; 426321369Sdim}; 427312197Sdim 428327952Sdim} // end anonymous namespace 429327952Sdim 430321369Sdimnamespace llvm { 431327952Sdim 432321369Sdimstruct ExactEqualsExpression { 433321369Sdim const Expression &E; 434327952Sdim 435321369Sdim explicit ExactEqualsExpression(const Expression &E) : E(E) {} 436327952Sdim 437321369Sdim hash_code getComputedHash() const { return E.getComputedHash(); } 438327952Sdim 439321369Sdim bool operator==(const Expression &Other) const { 440321369Sdim return E.exactlyEquals(Other); 441321369Sdim } 442311116Sdim}; 443311116Sdim 444311116Sdimtemplate <> struct DenseMapInfo<const Expression *> { 445311116Sdim static const Expression *getEmptyKey() { 446311116Sdim auto Val = static_cast<uintptr_t>(-1); 447311116Sdim Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable; 448311116Sdim return reinterpret_cast<const Expression *>(Val); 449311116Sdim } 450327952Sdim 451311116Sdim static const Expression *getTombstoneKey() { 452311116Sdim auto Val = static_cast<uintptr_t>(~1U); 453311116Sdim Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable; 454311116Sdim return reinterpret_cast<const Expression *>(Val); 455311116Sdim } 456327952Sdim 457321369Sdim static unsigned getHashValue(const Expression *E) { 458321369Sdim return E->getComputedHash(); 459311116Sdim } 460327952Sdim 461321369Sdim static unsigned getHashValue(const ExactEqualsExpression &E) { 462321369Sdim return E.getComputedHash(); 463321369Sdim } 464327952Sdim 465321369Sdim static bool isEqual(const ExactEqualsExpression &LHS, const Expression *RHS) { 466321369Sdim if (RHS == getTombstoneKey() || RHS == getEmptyKey()) 467321369Sdim return false; 468321369Sdim return LHS == *RHS; 469321369Sdim } 470321369Sdim 471311116Sdim static bool isEqual(const Expression *LHS, const Expression *RHS) { 472311116Sdim if (LHS == RHS) 473311116Sdim return true; 474311116Sdim if (LHS == getTombstoneKey() || RHS == getTombstoneKey() || 475311116Sdim LHS == getEmptyKey() || RHS == getEmptyKey()) 476311116Sdim return false; 477321369Sdim // Compare hashes before equality. This is *not* what the hashtable does, 478321369Sdim // since it is computing it modulo the number of buckets, whereas we are 479321369Sdim // using the full hash keyspace. Since the hashes are precomputed, this 480321369Sdim // check is *much* faster than equality. 481321369Sdim if (LHS->getComputedHash() != RHS->getComputedHash()) 482321369Sdim return false; 483311116Sdim return *LHS == *RHS; 484311116Sdim } 485311116Sdim}; 486327952Sdim 487311116Sdim} // end namespace llvm 488311116Sdim 489321369Sdimnamespace { 490327952Sdim 491321369Sdimclass NewGVN { 492321369Sdim Function &F; 493360784Sdim DominatorTree *DT = nullptr; 494360784Sdim const TargetLibraryInfo *TLI = nullptr; 495360784Sdim AliasAnalysis *AA = nullptr; 496360784Sdim MemorySSA *MSSA = nullptr; 497360784Sdim MemorySSAWalker *MSSAWalker = nullptr; 498321369Sdim const DataLayout &DL; 499321369Sdim std::unique_ptr<PredicateInfo> PredInfo; 500311116Sdim 501321369Sdim // These are the only two things the create* functions should have 502321369Sdim // side-effects on due to allocating memory. 503321369Sdim mutable BumpPtrAllocator ExpressionAllocator; 504321369Sdim mutable ArrayRecycler<Value *> ArgRecycler; 505321369Sdim mutable TarjanSCC SCCFinder; 506321369Sdim const SimplifyQuery SQ; 507321369Sdim 508321369Sdim // Number of function arguments, used by ranking 509360784Sdim unsigned int NumFuncArgs = 0; 510321369Sdim 511321369Sdim // RPOOrdering of basic blocks 512321369Sdim DenseMap<const DomTreeNode *, unsigned> RPOOrdering; 513321369Sdim 514311116Sdim // Congruence class info. 515321369Sdim 516321369Sdim // This class is called INITIAL in the paper. It is the class everything 517321369Sdim // startsout in, and represents any value. Being an optimistic analysis, 518321369Sdim // anything in the TOP class has the value TOP, which is indeterminate and 519321369Sdim // equivalent to everything. 520360784Sdim CongruenceClass *TOPClass = nullptr; 521311116Sdim std::vector<CongruenceClass *> CongruenceClasses; 522360784Sdim unsigned NextCongruenceNum = 0; 523311116Sdim 524311116Sdim // Value Mappings. 525311116Sdim DenseMap<Value *, CongruenceClass *> ValueToClass; 526311116Sdim DenseMap<Value *, const Expression *> ValueToExpression; 527327952Sdim 528321369Sdim // Value PHI handling, used to make equivalence between phi(op, op) and 529321369Sdim // op(phi, phi). 530321369Sdim // These mappings just store various data that would normally be part of the 531321369Sdim // IR. 532327952Sdim SmallPtrSet<const Instruction *, 8> PHINodeUses; 533327952Sdim 534327952Sdim DenseMap<const Value *, bool> OpSafeForPHIOfOps; 535327952Sdim 536321369Sdim // Map a temporary instruction we created to a parent block. 537321369Sdim DenseMap<const Value *, BasicBlock *> TempToBlock; 538327952Sdim 539327952Sdim // Map between the already in-program instructions and the temporary phis we 540327952Sdim // created that they are known equivalent to. 541321369Sdim DenseMap<const Value *, PHINode *> RealToTemp; 542327952Sdim 543321369Sdim // In order to know when we should re-process instructions that have 544321369Sdim // phi-of-ops, we track the set of expressions that they needed as 545321369Sdim // leaders. When we discover new leaders for those expressions, we process the 546321369Sdim // associated phi-of-op instructions again in case they have changed. The 547321369Sdim // other way they may change is if they had leaders, and those leaders 548321369Sdim // disappear. However, at the point they have leaders, there are uses of the 549321369Sdim // relevant operands in the created phi node, and so they will get reprocessed 550321369Sdim // through the normal user marking we perform. 551321369Sdim mutable DenseMap<const Value *, SmallPtrSet<Value *, 2>> AdditionalUsers; 552321369Sdim DenseMap<const Expression *, SmallPtrSet<Instruction *, 2>> 553321369Sdim ExpressionToPhiOfOps; 554327952Sdim 555321369Sdim // Map from temporary operation to MemoryAccess. 556321369Sdim DenseMap<const Instruction *, MemoryUseOrDef *> TempToMemory; 557327952Sdim 558321369Sdim // Set of all temporary instructions we created. 559327952Sdim // Note: This will include instructions that were just created during value 560327952Sdim // numbering. The way to test if something is using them is to check 561327952Sdim // RealToTemp. 562321369Sdim DenseSet<Instruction *> AllTempInstructions; 563311116Sdim 564327952Sdim // This is the set of instructions to revisit on a reachability change. At 565327952Sdim // the end of the main iteration loop it will contain at least all the phi of 566327952Sdim // ops instructions that will be changed to phis, as well as regular phis. 567327952Sdim // During the iteration loop, it may contain other things, such as phi of ops 568327952Sdim // instructions that used edge reachability to reach a result, and so need to 569327952Sdim // be revisited when the edge changes, independent of whether the phi they 570327952Sdim // depended on changes. 571327952Sdim DenseMap<BasicBlock *, SparseBitVector<>> RevisitOnReachabilityChange; 572327952Sdim 573321369Sdim // Mapping from predicate info we used to the instructions we used it with. 574321369Sdim // In order to correctly ensure propagation, we must keep track of what 575321369Sdim // comparisons we used, so that when the values of the comparisons change, we 576321369Sdim // propagate the information to the places we used the comparison. 577321369Sdim mutable DenseMap<const Value *, SmallPtrSet<Instruction *, 2>> 578321369Sdim PredicateToUsers; 579327952Sdim 580321369Sdim // the same reasoning as PredicateToUsers. When we skip MemoryAccesses for 581321369Sdim // stores, we no longer can rely solely on the def-use chains of MemorySSA. 582321369Sdim mutable DenseMap<const MemoryAccess *, SmallPtrSet<MemoryAccess *, 2>> 583321369Sdim MemoryToUsers; 584321369Sdim 585311116Sdim // A table storing which memorydefs/phis represent a memory state provably 586311116Sdim // equivalent to another memory state. 587311116Sdim // We could use the congruence class machinery, but the MemoryAccess's are 588311116Sdim // abstract memory states, so they can only ever be equivalent to each other, 589311116Sdim // and not to constants, etc. 590321369Sdim DenseMap<const MemoryAccess *, CongruenceClass *> MemoryAccessToClass; 591311116Sdim 592321369Sdim // We could, if we wanted, build MemoryPhiExpressions and 593321369Sdim // MemoryVariableExpressions, etc, and value number them the same way we value 594321369Sdim // number phi expressions. For the moment, this seems like overkill. They 595321369Sdim // can only exist in one of three states: they can be TOP (equal to 596321369Sdim // everything), Equivalent to something else, or unique. Because we do not 597321369Sdim // create expressions for them, we need to simulate leader change not just 598321369Sdim // when they change class, but when they change state. Note: We can do the 599321369Sdim // same thing for phis, and avoid having phi expressions if we wanted, We 600321369Sdim // should eventually unify in one direction or the other, so this is a little 601321369Sdim // bit of an experiment in which turns out easier to maintain. 602321369Sdim enum MemoryPhiState { MPS_Invalid, MPS_TOP, MPS_Equivalent, MPS_Unique }; 603321369Sdim DenseMap<const MemoryPhi *, MemoryPhiState> MemoryPhiState; 604321369Sdim 605321369Sdim enum InstCycleState { ICS_Unknown, ICS_CycleFree, ICS_Cycle }; 606321369Sdim mutable DenseMap<const Instruction *, InstCycleState> InstCycleState; 607327952Sdim 608311116Sdim // Expression to class mapping. 609311116Sdim using ExpressionClassMap = DenseMap<const Expression *, CongruenceClass *>; 610311116Sdim ExpressionClassMap ExpressionToClass; 611311116Sdim 612321369Sdim // We have a single expression that represents currently DeadExpressions. 613321369Sdim // For dead expressions we can prove will stay dead, we mark them with 614321369Sdim // DFS number zero. However, it's possible in the case of phi nodes 615321369Sdim // for us to assume/prove all arguments are dead during fixpointing. 616321369Sdim // We use DeadExpression for that case. 617321369Sdim DeadExpression *SingletonDeadExpression = nullptr; 618321369Sdim 619311116Sdim // Which values have changed as a result of leader changes. 620312197Sdim SmallPtrSet<Value *, 8> LeaderChanges; 621311116Sdim 622311116Sdim // Reachability info. 623311116Sdim using BlockEdge = BasicBlockEdge; 624311116Sdim DenseSet<BlockEdge> ReachableEdges; 625311116Sdim SmallPtrSet<const BasicBlock *, 8> ReachableBlocks; 626311116Sdim 627311116Sdim // This is a bitvector because, on larger functions, we may have 628311116Sdim // thousands of touched instructions at once (entire blocks, 629311116Sdim // instructions with hundreds of uses, etc). Even with optimization 630311116Sdim // for when we mark whole blocks as touched, when this was a 631311116Sdim // SmallPtrSet or DenseSet, for some functions, we spent >20% of all 632311116Sdim // the time in GVN just managing this list. The bitvector, on the 633311116Sdim // other hand, efficiently supports test/set/clear of both 634311116Sdim // individual and ranges, as well as "find next element" This 635311116Sdim // enables us to use it as a worklist with essentially 0 cost. 636311116Sdim BitVector TouchedInstructions; 637311116Sdim 638311116Sdim DenseMap<const BasicBlock *, std::pair<unsigned, unsigned>> BlockInstRange; 639311116Sdim 640311116Sdim#ifndef NDEBUG 641311116Sdim // Debugging for how many times each block and instruction got processed. 642311116Sdim DenseMap<const Value *, unsigned> ProcessedCount; 643311116Sdim#endif 644311116Sdim 645311116Sdim // DFS info. 646321369Sdim // This contains a mapping from Instructions to DFS numbers. 647321369Sdim // The numbering starts at 1. An instruction with DFS number zero 648321369Sdim // means that the instruction is dead. 649311116Sdim DenseMap<const Value *, unsigned> InstrDFS; 650321369Sdim 651321369Sdim // This contains the mapping DFS numbers to instructions. 652311116Sdim SmallVector<Value *, 32> DFSToInstr; 653311116Sdim 654311116Sdim // Deletion info. 655311116Sdim SmallPtrSet<Instruction *, 8> InstructionsToErase; 656311116Sdim 657311116Sdimpublic: 658321369Sdim NewGVN(Function &F, DominatorTree *DT, AssumptionCache *AC, 659321369Sdim TargetLibraryInfo *TLI, AliasAnalysis *AA, MemorySSA *MSSA, 660321369Sdim const DataLayout &DL) 661321369Sdim : F(F), DT(DT), TLI(TLI), AA(AA), MSSA(MSSA), DL(DL), 662360784Sdim PredInfo(std::make_unique<PredicateInfo>(F, *DT, *AC)), 663344779Sdim SQ(DL, TLI, DT, AC, /*CtxI=*/nullptr, /*UseInstrInfo=*/false) {} 664327952Sdim 665321369Sdim bool runGVN(); 666311116Sdim 667311116Sdimprivate: 668311116Sdim // Expression handling. 669321369Sdim const Expression *createExpression(Instruction *) const; 670326909Sdim const Expression *createBinaryExpression(unsigned, Type *, Value *, Value *, 671326909Sdim Instruction *) const; 672327952Sdim 673327952Sdim // Our canonical form for phi arguments is a pair of incoming value, incoming 674327952Sdim // basic block. 675327952Sdim using ValPair = std::pair<Value *, BasicBlock *>; 676327952Sdim 677327952Sdim PHIExpression *createPHIExpression(ArrayRef<ValPair>, const Instruction *, 678327952Sdim BasicBlock *, bool &HasBackEdge, 679321369Sdim bool &OriginalOpsConstant) const; 680321369Sdim const DeadExpression *createDeadExpression() const; 681321369Sdim const VariableExpression *createVariableExpression(Value *) const; 682321369Sdim const ConstantExpression *createConstantExpression(Constant *) const; 683321369Sdim const Expression *createVariableOrConstant(Value *V) const; 684321369Sdim const UnknownExpression *createUnknownExpression(Instruction *) const; 685321369Sdim const StoreExpression *createStoreExpression(StoreInst *, 686321369Sdim const MemoryAccess *) const; 687311116Sdim LoadExpression *createLoadExpression(Type *, Value *, LoadInst *, 688321369Sdim const MemoryAccess *) const; 689321369Sdim const CallExpression *createCallExpression(CallInst *, 690321369Sdim const MemoryAccess *) const; 691311116Sdim const AggregateValueExpression * 692321369Sdim createAggregateValueExpression(Instruction *) const; 693321369Sdim bool setBasicExpressionInfo(Instruction *, BasicExpression *) const; 694311116Sdim 695311116Sdim // Congruence class handling. 696311116Sdim CongruenceClass *createCongruenceClass(Value *Leader, const Expression *E) { 697311116Sdim auto *result = new CongruenceClass(NextCongruenceNum++, Leader, E); 698311116Sdim CongruenceClasses.emplace_back(result); 699311116Sdim return result; 700311116Sdim } 701311116Sdim 702321369Sdim CongruenceClass *createMemoryClass(MemoryAccess *MA) { 703321369Sdim auto *CC = createCongruenceClass(nullptr, nullptr); 704321369Sdim CC->setMemoryLeader(MA); 705321369Sdim return CC; 706321369Sdim } 707327952Sdim 708321369Sdim CongruenceClass *ensureLeaderOfMemoryClass(MemoryAccess *MA) { 709321369Sdim auto *CC = getMemoryClass(MA); 710321369Sdim if (CC->getMemoryLeader() != MA) 711321369Sdim CC = createMemoryClass(MA); 712321369Sdim return CC; 713321369Sdim } 714321369Sdim 715311116Sdim CongruenceClass *createSingletonCongruenceClass(Value *Member) { 716311116Sdim CongruenceClass *CClass = createCongruenceClass(Member, nullptr); 717321369Sdim CClass->insert(Member); 718311116Sdim ValueToClass[Member] = CClass; 719311116Sdim return CClass; 720311116Sdim } 721327952Sdim 722311116Sdim void initializeCongruenceClasses(Function &F); 723327952Sdim const Expression *makePossiblePHIOfOps(Instruction *, 724321369Sdim SmallPtrSetImpl<Value *> &); 725327952Sdim Value *findLeaderForInst(Instruction *ValueOp, 726327952Sdim SmallPtrSetImpl<Value *> &Visited, 727327952Sdim MemoryAccess *MemAccess, Instruction *OrigInst, 728327952Sdim BasicBlock *PredBB); 729327952Sdim bool OpIsSafeForPHIOfOpsHelper(Value *V, const BasicBlock *PHIBlock, 730327952Sdim SmallPtrSetImpl<const Value *> &Visited, 731327952Sdim SmallVectorImpl<Instruction *> &Worklist); 732327952Sdim bool OpIsSafeForPHIOfOps(Value *Op, const BasicBlock *PHIBlock, 733327952Sdim SmallPtrSetImpl<const Value *> &); 734321369Sdim void addPhiOfOps(PHINode *Op, BasicBlock *BB, Instruction *ExistingValue); 735327952Sdim void removePhiOfOps(Instruction *I, PHINode *PHITemp); 736311116Sdim 737311116Sdim // Value number an Instruction or MemoryPhi. 738311116Sdim void valueNumberMemoryPhi(MemoryPhi *); 739311116Sdim void valueNumberInstruction(Instruction *); 740311116Sdim 741311116Sdim // Symbolic evaluation. 742311116Sdim const Expression *checkSimplificationResults(Expression *, Instruction *, 743321369Sdim Value *) const; 744321369Sdim const Expression *performSymbolicEvaluation(Value *, 745321369Sdim SmallPtrSetImpl<Value *> &) const; 746321369Sdim const Expression *performSymbolicLoadCoercion(Type *, Value *, LoadInst *, 747321369Sdim Instruction *, 748321369Sdim MemoryAccess *) const; 749321369Sdim const Expression *performSymbolicLoadEvaluation(Instruction *) const; 750321369Sdim const Expression *performSymbolicStoreEvaluation(Instruction *) const; 751321369Sdim const Expression *performSymbolicCallEvaluation(Instruction *) const; 752327952Sdim void sortPHIOps(MutableArrayRef<ValPair> Ops) const; 753327952Sdim const Expression *performSymbolicPHIEvaluation(ArrayRef<ValPair>, 754327952Sdim Instruction *I, 755327952Sdim BasicBlock *PHIBlock) const; 756321369Sdim const Expression *performSymbolicAggrValueEvaluation(Instruction *) const; 757321369Sdim const Expression *performSymbolicCmpEvaluation(Instruction *) const; 758321369Sdim const Expression *performSymbolicPredicateInfoEvaluation(Instruction *) const; 759311116Sdim 760311116Sdim // Congruence finding. 761321369Sdim bool someEquivalentDominates(const Instruction *, const Instruction *) const; 762321369Sdim Value *lookupOperandLeader(Value *) const; 763327952Sdim CongruenceClass *getClassForExpression(const Expression *E) const; 764312639Sdim void performCongruenceFinding(Instruction *, const Expression *); 765321369Sdim void moveValueToNewCongruenceClass(Instruction *, const Expression *, 766321369Sdim CongruenceClass *, CongruenceClass *); 767321369Sdim void moveMemoryToNewCongruenceClass(Instruction *, MemoryAccess *, 768321369Sdim CongruenceClass *, CongruenceClass *); 769321369Sdim Value *getNextValueLeader(CongruenceClass *) const; 770321369Sdim const MemoryAccess *getNextMemoryLeader(CongruenceClass *) const; 771321369Sdim bool setMemoryClass(const MemoryAccess *From, CongruenceClass *To); 772321369Sdim CongruenceClass *getMemoryClass(const MemoryAccess *MA) const; 773321369Sdim const MemoryAccess *lookupMemoryLeader(const MemoryAccess *) const; 774321369Sdim bool isMemoryAccessTOP(const MemoryAccess *) const; 775321369Sdim 776321369Sdim // Ranking 777321369Sdim unsigned int getRank(const Value *) const; 778321369Sdim bool shouldSwapOperands(const Value *, const Value *) const; 779321369Sdim 780311116Sdim // Reachability handling. 781311116Sdim void updateReachableEdge(BasicBlock *, BasicBlock *); 782344779Sdim void processOutgoingEdges(Instruction *, BasicBlock *); 783321369Sdim Value *findConditionEquivalence(Value *) const; 784311116Sdim 785311116Sdim // Elimination. 786311116Sdim struct ValueDFS; 787321369Sdim void convertClassToDFSOrdered(const CongruenceClass &, 788321369Sdim SmallVectorImpl<ValueDFS> &, 789321369Sdim DenseMap<const Value *, unsigned int> &, 790321369Sdim SmallPtrSetImpl<Instruction *> &) const; 791321369Sdim void convertClassToLoadsAndStores(const CongruenceClass &, 792321369Sdim SmallVectorImpl<ValueDFS> &) const; 793311116Sdim 794311116Sdim bool eliminateInstructions(Function &); 795311116Sdim void replaceInstruction(Instruction *, Value *); 796311116Sdim void markInstructionForDeletion(Instruction *); 797311116Sdim void deleteInstructionsInBlock(BasicBlock *); 798327952Sdim Value *findPHIOfOpsLeader(const Expression *, const Instruction *, 799327952Sdim const BasicBlock *) const; 800311116Sdim 801311116Sdim // New instruction creation. 802327952Sdim void handleNewInstruction(Instruction *) {} 803311833Sdim 804311833Sdim // Various instruction touch utilities 805321369Sdim template <typename Map, typename KeyType, typename Func> 806321369Sdim void for_each_found(Map &, const KeyType &, Func); 807321369Sdim template <typename Map, typename KeyType> 808321369Sdim void touchAndErase(Map &, const KeyType &); 809311116Sdim void markUsersTouched(Value *); 810321369Sdim void markMemoryUsersTouched(const MemoryAccess *); 811321369Sdim void markMemoryDefTouched(const MemoryAccess *); 812321369Sdim void markPredicateUsersTouched(Instruction *); 813321369Sdim void markValueLeaderChangeTouched(CongruenceClass *CC); 814321369Sdim void markMemoryLeaderChangeTouched(CongruenceClass *CC); 815321369Sdim void markPhiOfOpsChanged(const Expression *E); 816321369Sdim void addPredicateUsers(const PredicateBase *, Instruction *) const; 817321369Sdim void addMemoryUsers(const MemoryAccess *To, MemoryAccess *U) const; 818321369Sdim void addAdditionalUsers(Value *To, Value *User) const; 819311116Sdim 820321369Sdim // Main loop of value numbering 821321369Sdim void iterateTouchedInstructions(); 822321369Sdim 823311116Sdim // Utilities. 824311116Sdim void cleanupTables(); 825311116Sdim std::pair<unsigned, unsigned> assignDFSNumbers(BasicBlock *, unsigned); 826321369Sdim void updateProcessedCount(const Value *V); 827312197Sdim void verifyMemoryCongruency() const; 828321369Sdim void verifyIterationSettled(Function &F); 829321369Sdim void verifyStoreExpressions() const; 830321369Sdim bool singleReachablePHIPath(SmallPtrSet<const MemoryAccess *, 8> &, 831321369Sdim const MemoryAccess *, const MemoryAccess *) const; 832321369Sdim BasicBlock *getBlockForValue(Value *V) const; 833321369Sdim void deleteExpression(const Expression *E) const; 834321369Sdim MemoryUseOrDef *getMemoryAccess(const Instruction *) const; 835321369Sdim MemoryAccess *getDefiningAccess(const MemoryAccess *) const; 836321369Sdim MemoryPhi *getMemoryAccess(const BasicBlock *) const; 837321369Sdim template <class T, class Range> T *getMinDFSOfRange(const Range &) const; 838327952Sdim 839321369Sdim unsigned InstrToDFSNum(const Value *V) const { 840321369Sdim assert(isa<Instruction>(V) && "This should not be used for MemoryAccesses"); 841321369Sdim return InstrDFS.lookup(V); 842321369Sdim } 843321369Sdim 844321369Sdim unsigned InstrToDFSNum(const MemoryAccess *MA) const { 845321369Sdim return MemoryToDFSNum(MA); 846321369Sdim } 847327952Sdim 848321369Sdim Value *InstrFromDFSNum(unsigned DFSNum) { return DFSToInstr[DFSNum]; } 849327952Sdim 850321369Sdim // Given a MemoryAccess, return the relevant instruction DFS number. Note: 851321369Sdim // This deliberately takes a value so it can be used with Use's, which will 852321369Sdim // auto-convert to Value's but not to MemoryAccess's. 853321369Sdim unsigned MemoryToDFSNum(const Value *MA) const { 854321369Sdim assert(isa<MemoryAccess>(MA) && 855321369Sdim "This should not be used with instructions"); 856321369Sdim return isa<MemoryUseOrDef>(MA) 857321369Sdim ? InstrToDFSNum(cast<MemoryUseOrDef>(MA)->getMemoryInst()) 858321369Sdim : InstrDFS.lookup(MA); 859321369Sdim } 860327952Sdim 861321369Sdim bool isCycleFree(const Instruction *) const; 862321369Sdim bool isBackedge(BasicBlock *From, BasicBlock *To) const; 863327952Sdim 864321369Sdim // Debug counter info. When verifying, we have to reset the value numbering 865321369Sdim // debug counter to the same state it started in to get the same results. 866360784Sdim int64_t StartingVNCounter = 0; 867311116Sdim}; 868327952Sdim 869321369Sdim} // end anonymous namespace 870311116Sdim 871311116Sdimtemplate <typename T> 872311116Sdimstatic bool equalsLoadStoreHelper(const T &LHS, const Expression &RHS) { 873321369Sdim if (!isa<LoadExpression>(RHS) && !isa<StoreExpression>(RHS)) 874311116Sdim return false; 875321369Sdim return LHS.MemoryExpression::equals(RHS); 876311116Sdim} 877311116Sdim 878311116Sdimbool LoadExpression::equals(const Expression &Other) const { 879311116Sdim return equalsLoadStoreHelper(*this, Other); 880311116Sdim} 881311116Sdim 882311116Sdimbool StoreExpression::equals(const Expression &Other) const { 883321369Sdim if (!equalsLoadStoreHelper(*this, Other)) 884321369Sdim return false; 885321369Sdim // Make sure that store vs store includes the value operand. 886321369Sdim if (const auto *S = dyn_cast<StoreExpression>(&Other)) 887321369Sdim if (getStoredValue() != S->getStoredValue()) 888321369Sdim return false; 889321369Sdim return true; 890311116Sdim} 891311116Sdim 892321369Sdim// Determine if the edge From->To is a backedge 893321369Sdimbool NewGVN::isBackedge(BasicBlock *From, BasicBlock *To) const { 894327952Sdim return From == To || 895327952Sdim RPOOrdering.lookup(DT->getNode(From)) >= 896327952Sdim RPOOrdering.lookup(DT->getNode(To)); 897321369Sdim} 898321369Sdim 899311116Sdim#ifndef NDEBUG 900311116Sdimstatic std::string getBlockName(const BasicBlock *B) { 901311116Sdim return DOTGraphTraits<const Function *>::getSimpleNodeLabel(B, nullptr); 902311116Sdim} 903311116Sdim#endif 904311116Sdim 905321369Sdim// Get a MemoryAccess for an instruction, fake or real. 906321369SdimMemoryUseOrDef *NewGVN::getMemoryAccess(const Instruction *I) const { 907321369Sdim auto *Result = MSSA->getMemoryAccess(I); 908321369Sdim return Result ? Result : TempToMemory.lookup(I); 909321369Sdim} 910311116Sdim 911321369Sdim// Get a MemoryPhi for a basic block. These are all real. 912321369SdimMemoryPhi *NewGVN::getMemoryAccess(const BasicBlock *BB) const { 913321369Sdim return MSSA->getMemoryAccess(BB); 914321369Sdim} 915321369Sdim 916321369Sdim// Get the basic block from an instruction/memory value. 917321369SdimBasicBlock *NewGVN::getBlockForValue(Value *V) const { 918321369Sdim if (auto *I = dyn_cast<Instruction>(V)) { 919321369Sdim auto *Parent = I->getParent(); 920321369Sdim if (Parent) 921321369Sdim return Parent; 922321369Sdim Parent = TempToBlock.lookup(V); 923321369Sdim assert(Parent && "Every fake instruction should have a block"); 924321369Sdim return Parent; 925321369Sdim } 926321369Sdim 927321369Sdim auto *MP = dyn_cast<MemoryPhi>(V); 928321369Sdim assert(MP && "Should have been an instruction or a MemoryPhi"); 929321369Sdim return MP->getBlock(); 930321369Sdim} 931321369Sdim 932321369Sdim// Delete a definitely dead expression, so it can be reused by the expression 933321369Sdim// allocator. Some of these are not in creation functions, so we have to accept 934321369Sdim// const versions. 935321369Sdimvoid NewGVN::deleteExpression(const Expression *E) const { 936321369Sdim assert(isa<BasicExpression>(E)); 937321369Sdim auto *BE = cast<BasicExpression>(E); 938321369Sdim const_cast<BasicExpression *>(BE)->deallocateOperands(ArgRecycler); 939321369Sdim ExpressionAllocator.Deallocate(E); 940321369Sdim} 941327952Sdim 942327952Sdim// If V is a predicateinfo copy, get the thing it is a copy of. 943327952Sdimstatic Value *getCopyOf(const Value *V) { 944327952Sdim if (auto *II = dyn_cast<IntrinsicInst>(V)) 945327952Sdim if (II->getIntrinsicID() == Intrinsic::ssa_copy) 946327952Sdim return II->getOperand(0); 947327952Sdim return nullptr; 948327952Sdim} 949327952Sdim 950327952Sdim// Return true if V is really PN, even accounting for predicateinfo copies. 951327952Sdimstatic bool isCopyOfPHI(const Value *V, const PHINode *PN) { 952327952Sdim return V == PN || getCopyOf(V) == PN; 953327952Sdim} 954327952Sdim 955327952Sdimstatic bool isCopyOfAPHI(const Value *V) { 956327952Sdim auto *CO = getCopyOf(V); 957327952Sdim return CO && isa<PHINode>(CO); 958327952Sdim} 959327952Sdim 960327952Sdim// Sort PHI Operands into a canonical order. What we use here is an RPO 961327952Sdim// order. The BlockInstRange numbers are generated in an RPO walk of the basic 962327952Sdim// blocks. 963327952Sdimvoid NewGVN::sortPHIOps(MutableArrayRef<ValPair> Ops) const { 964344779Sdim llvm::sort(Ops, [&](const ValPair &P1, const ValPair &P2) { 965327952Sdim return BlockInstRange.lookup(P1.second).first < 966327952Sdim BlockInstRange.lookup(P2.second).first; 967327952Sdim }); 968327952Sdim} 969327952Sdim 970327952Sdim// Return true if V is a value that will always be available (IE can 971327952Sdim// be placed anywhere) in the function. We don't do globals here 972327952Sdim// because they are often worse to put in place. 973327952Sdimstatic bool alwaysAvailable(Value *V) { 974327952Sdim return isa<Constant>(V) || isa<Argument>(V); 975327952Sdim} 976327952Sdim 977327952Sdim// Create a PHIExpression from an array of {incoming edge, value} pairs. I is 978327952Sdim// the original instruction we are creating a PHIExpression for (but may not be 979327952Sdim// a phi node). We require, as an invariant, that all the PHIOperands in the 980327952Sdim// same block are sorted the same way. sortPHIOps will sort them into a 981327952Sdim// canonical order. 982327952SdimPHIExpression *NewGVN::createPHIExpression(ArrayRef<ValPair> PHIOperands, 983327952Sdim const Instruction *I, 984327952Sdim BasicBlock *PHIBlock, 985327952Sdim bool &HasBackedge, 986321369Sdim bool &OriginalOpsConstant) const { 987327952Sdim unsigned NumOps = PHIOperands.size(); 988327952Sdim auto *E = new (ExpressionAllocator) PHIExpression(NumOps, PHIBlock); 989311116Sdim 990311116Sdim E->allocateOperands(ArgRecycler, ExpressionAllocator); 991327952Sdim E->setType(PHIOperands.begin()->first->getType()); 992327952Sdim E->setOpcode(Instruction::PHI); 993311116Sdim 994321369Sdim // Filter out unreachable phi operands. 995327952Sdim auto Filtered = make_filter_range(PHIOperands, [&](const ValPair &P) { 996327952Sdim auto *BB = P.second; 997327952Sdim if (auto *PHIOp = dyn_cast<PHINode>(I)) 998327952Sdim if (isCopyOfPHI(P.first, PHIOp)) 999327952Sdim return false; 1000327952Sdim if (!ReachableEdges.count({BB, PHIBlock})) 1001321369Sdim return false; 1002321369Sdim // Things in TOPClass are equivalent to everything. 1003327952Sdim if (ValueToClass.lookup(P.first) == TOPClass) 1004321369Sdim return false; 1005327952Sdim OriginalOpsConstant = OriginalOpsConstant && isa<Constant>(P.first); 1006327952Sdim HasBackedge = HasBackedge || isBackedge(BB, PHIBlock); 1007327952Sdim return lookupOperandLeader(P.first) != I; 1008321369Sdim }); 1009311116Sdim std::transform(Filtered.begin(), Filtered.end(), op_inserter(E), 1010327952Sdim [&](const ValPair &P) -> Value * { 1011327952Sdim return lookupOperandLeader(P.first); 1012311116Sdim }); 1013311116Sdim return E; 1014311116Sdim} 1015311116Sdim 1016311116Sdim// Set basic expression info (Arguments, type, opcode) for Expression 1017311116Sdim// E from Instruction I in block B. 1018321369Sdimbool NewGVN::setBasicExpressionInfo(Instruction *I, BasicExpression *E) const { 1019311116Sdim bool AllConstant = true; 1020311116Sdim if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) 1021311116Sdim E->setType(GEP->getSourceElementType()); 1022311116Sdim else 1023311116Sdim E->setType(I->getType()); 1024311116Sdim E->setOpcode(I->getOpcode()); 1025311116Sdim E->allocateOperands(ArgRecycler, ExpressionAllocator); 1026311116Sdim 1027311116Sdim // Transform the operand array into an operand leader array, and keep track of 1028311116Sdim // whether all members are constant. 1029311116Sdim std::transform(I->op_begin(), I->op_end(), op_inserter(E), [&](Value *O) { 1030321369Sdim auto Operand = lookupOperandLeader(O); 1031321369Sdim AllConstant = AllConstant && isa<Constant>(Operand); 1032311116Sdim return Operand; 1033311116Sdim }); 1034311116Sdim 1035311116Sdim return AllConstant; 1036311116Sdim} 1037311116Sdim 1038311116Sdimconst Expression *NewGVN::createBinaryExpression(unsigned Opcode, Type *T, 1039326909Sdim Value *Arg1, Value *Arg2, 1040326909Sdim Instruction *I) const { 1041311116Sdim auto *E = new (ExpressionAllocator) BasicExpression(2); 1042311116Sdim 1043311116Sdim E->setType(T); 1044311116Sdim E->setOpcode(Opcode); 1045311116Sdim E->allocateOperands(ArgRecycler, ExpressionAllocator); 1046311116Sdim if (Instruction::isCommutative(Opcode)) { 1047311116Sdim // Ensure that commutative instructions that only differ by a permutation 1048311116Sdim // of their operands get the same value number by sorting the operand value 1049311116Sdim // numbers. Since all commutative instructions have two operands it is more 1050311116Sdim // efficient to sort by hand rather than using, say, std::sort. 1051321369Sdim if (shouldSwapOperands(Arg1, Arg2)) 1052311116Sdim std::swap(Arg1, Arg2); 1053311116Sdim } 1054321369Sdim E->op_push_back(lookupOperandLeader(Arg1)); 1055321369Sdim E->op_push_back(lookupOperandLeader(Arg2)); 1056311116Sdim 1057321369Sdim Value *V = SimplifyBinOp(Opcode, E->getOperand(0), E->getOperand(1), SQ); 1058326909Sdim if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V)) 1059311116Sdim return SimplifiedE; 1060311116Sdim return E; 1061311116Sdim} 1062311116Sdim 1063311116Sdim// Take a Value returned by simplification of Expression E/Instruction 1064311116Sdim// I, and see if it resulted in a simpler expression. If so, return 1065311116Sdim// that expression. 1066311116Sdimconst Expression *NewGVN::checkSimplificationResults(Expression *E, 1067321369Sdim Instruction *I, 1068321369Sdim Value *V) const { 1069311116Sdim if (!V) 1070311116Sdim return nullptr; 1071311116Sdim if (auto *C = dyn_cast<Constant>(V)) { 1072311116Sdim if (I) 1073341825Sdim LLVM_DEBUG(dbgs() << "Simplified " << *I << " to " 1074341825Sdim << " constant " << *C << "\n"); 1075311116Sdim NumGVNOpsSimplified++; 1076311116Sdim assert(isa<BasicExpression>(E) && 1077311116Sdim "We should always have had a basic expression here"); 1078321369Sdim deleteExpression(E); 1079311116Sdim return createConstantExpression(C); 1080311116Sdim } else if (isa<Argument>(V) || isa<GlobalVariable>(V)) { 1081311116Sdim if (I) 1082341825Sdim LLVM_DEBUG(dbgs() << "Simplified " << *I << " to " 1083341825Sdim << " variable " << *V << "\n"); 1084321369Sdim deleteExpression(E); 1085311116Sdim return createVariableExpression(V); 1086311116Sdim } 1087311116Sdim 1088311116Sdim CongruenceClass *CC = ValueToClass.lookup(V); 1089327952Sdim if (CC) { 1090327952Sdim if (CC->getLeader() && CC->getLeader() != I) { 1091344779Sdim // If we simplified to something else, we need to communicate 1092344779Sdim // that we're users of the value we simplified to. 1093344779Sdim if (I != V) { 1094344779Sdim // Don't add temporary instructions to the user lists. 1095344779Sdim if (!AllTempInstructions.count(I)) 1096344779Sdim addAdditionalUsers(V, I); 1097344779Sdim } 1098327952Sdim return createVariableOrConstant(CC->getLeader()); 1099321369Sdim } 1100327952Sdim if (CC->getDefiningExpr()) { 1101327952Sdim // If we simplified to something else, we need to communicate 1102327952Sdim // that we're users of the value we simplified to. 1103327952Sdim if (I != V) { 1104327952Sdim // Don't add temporary instructions to the user lists. 1105327952Sdim if (!AllTempInstructions.count(I)) 1106327952Sdim addAdditionalUsers(V, I); 1107327952Sdim } 1108321369Sdim 1109327952Sdim if (I) 1110341825Sdim LLVM_DEBUG(dbgs() << "Simplified " << *I << " to " 1111341825Sdim << " expression " << *CC->getDefiningExpr() << "\n"); 1112327952Sdim NumGVNOpsSimplified++; 1113327952Sdim deleteExpression(E); 1114327952Sdim return CC->getDefiningExpr(); 1115327952Sdim } 1116311116Sdim } 1117327952Sdim 1118311116Sdim return nullptr; 1119311116Sdim} 1120311116Sdim 1121327952Sdim// Create a value expression from the instruction I, replacing operands with 1122327952Sdim// their leaders. 1123327952Sdim 1124321369Sdimconst Expression *NewGVN::createExpression(Instruction *I) const { 1125311116Sdim auto *E = new (ExpressionAllocator) BasicExpression(I->getNumOperands()); 1126311116Sdim 1127321369Sdim bool AllConstant = setBasicExpressionInfo(I, E); 1128311116Sdim 1129311116Sdim if (I->isCommutative()) { 1130311116Sdim // Ensure that commutative instructions that only differ by a permutation 1131311116Sdim // of their operands get the same value number by sorting the operand value 1132311116Sdim // numbers. Since all commutative instructions have two operands it is more 1133311116Sdim // efficient to sort by hand rather than using, say, std::sort. 1134311116Sdim assert(I->getNumOperands() == 2 && "Unsupported commutative instruction!"); 1135321369Sdim if (shouldSwapOperands(E->getOperand(0), E->getOperand(1))) 1136311116Sdim E->swapOperands(0, 1); 1137311116Sdim } 1138327952Sdim // Perform simplification. 1139311116Sdim if (auto *CI = dyn_cast<CmpInst>(I)) { 1140311116Sdim // Sort the operand value numbers so x<y and y>x get the same value 1141311116Sdim // number. 1142311116Sdim CmpInst::Predicate Predicate = CI->getPredicate(); 1143321369Sdim if (shouldSwapOperands(E->getOperand(0), E->getOperand(1))) { 1144311116Sdim E->swapOperands(0, 1); 1145311116Sdim Predicate = CmpInst::getSwappedPredicate(Predicate); 1146311116Sdim } 1147311116Sdim E->setOpcode((CI->getOpcode() << 8) | Predicate); 1148311116Sdim // TODO: 25% of our time is spent in SimplifyCmpInst with pointer operands 1149311116Sdim assert(I->getOperand(0)->getType() == I->getOperand(1)->getType() && 1150311116Sdim "Wrong types on cmp instruction"); 1151321369Sdim assert((E->getOperand(0)->getType() == I->getOperand(0)->getType() && 1152321369Sdim E->getOperand(1)->getType() == I->getOperand(1)->getType())); 1153321369Sdim Value *V = 1154321369Sdim SimplifyCmpInst(Predicate, E->getOperand(0), E->getOperand(1), SQ); 1155321369Sdim if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V)) 1156321369Sdim return SimplifiedE; 1157311116Sdim } else if (isa<SelectInst>(I)) { 1158311116Sdim if (isa<Constant>(E->getOperand(0)) || 1159327952Sdim E->getOperand(1) == E->getOperand(2)) { 1160321369Sdim assert(E->getOperand(1)->getType() == I->getOperand(1)->getType() && 1161321369Sdim E->getOperand(2)->getType() == I->getOperand(2)->getType()); 1162311116Sdim Value *V = SimplifySelectInst(E->getOperand(0), E->getOperand(1), 1163321369Sdim E->getOperand(2), SQ); 1164311116Sdim if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V)) 1165311116Sdim return SimplifiedE; 1166311116Sdim } 1167311116Sdim } else if (I->isBinaryOp()) { 1168321369Sdim Value *V = 1169321369Sdim SimplifyBinOp(E->getOpcode(), E->getOperand(0), E->getOperand(1), SQ); 1170311116Sdim if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V)) 1171311116Sdim return SimplifiedE; 1172353358Sdim } else if (auto *CI = dyn_cast<CastInst>(I)) { 1173321369Sdim Value *V = 1174353358Sdim SimplifyCastInst(CI->getOpcode(), E->getOperand(0), CI->getType(), SQ); 1175311116Sdim if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V)) 1176311116Sdim return SimplifiedE; 1177311116Sdim } else if (isa<GetElementPtrInst>(I)) { 1178321369Sdim Value *V = SimplifyGEPInst( 1179321369Sdim E->getType(), ArrayRef<Value *>(E->op_begin(), E->op_end()), SQ); 1180311116Sdim if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V)) 1181311116Sdim return SimplifiedE; 1182311116Sdim } else if (AllConstant) { 1183311116Sdim // We don't bother trying to simplify unless all of the operands 1184311116Sdim // were constant. 1185311116Sdim // TODO: There are a lot of Simplify*'s we could call here, if we 1186311116Sdim // wanted to. The original motivating case for this code was a 1187311116Sdim // zext i1 false to i8, which we don't have an interface to 1188311116Sdim // simplify (IE there is no SimplifyZExt). 1189311116Sdim 1190311116Sdim SmallVector<Constant *, 8> C; 1191311116Sdim for (Value *Arg : E->operands()) 1192311116Sdim C.emplace_back(cast<Constant>(Arg)); 1193311116Sdim 1194321369Sdim if (Value *V = ConstantFoldInstOperands(I, C, DL, TLI)) 1195311116Sdim if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V)) 1196311116Sdim return SimplifiedE; 1197311116Sdim } 1198311116Sdim return E; 1199311116Sdim} 1200311116Sdim 1201311116Sdimconst AggregateValueExpression * 1202321369SdimNewGVN::createAggregateValueExpression(Instruction *I) const { 1203311116Sdim if (auto *II = dyn_cast<InsertValueInst>(I)) { 1204311116Sdim auto *E = new (ExpressionAllocator) 1205311116Sdim AggregateValueExpression(I->getNumOperands(), II->getNumIndices()); 1206321369Sdim setBasicExpressionInfo(I, E); 1207311116Sdim E->allocateIntOperands(ExpressionAllocator); 1208311116Sdim std::copy(II->idx_begin(), II->idx_end(), int_op_inserter(E)); 1209311116Sdim return E; 1210311116Sdim } else if (auto *EI = dyn_cast<ExtractValueInst>(I)) { 1211311116Sdim auto *E = new (ExpressionAllocator) 1212311116Sdim AggregateValueExpression(I->getNumOperands(), EI->getNumIndices()); 1213321369Sdim setBasicExpressionInfo(EI, E); 1214311116Sdim E->allocateIntOperands(ExpressionAllocator); 1215311116Sdim std::copy(EI->idx_begin(), EI->idx_end(), int_op_inserter(E)); 1216311116Sdim return E; 1217311116Sdim } 1218311116Sdim llvm_unreachable("Unhandled type of aggregate value operation"); 1219311116Sdim} 1220311116Sdim 1221321369Sdimconst DeadExpression *NewGVN::createDeadExpression() const { 1222321369Sdim // DeadExpression has no arguments and all DeadExpression's are the same, 1223321369Sdim // so we only need one of them. 1224321369Sdim return SingletonDeadExpression; 1225321369Sdim} 1226321369Sdim 1227321369Sdimconst VariableExpression *NewGVN::createVariableExpression(Value *V) const { 1228311116Sdim auto *E = new (ExpressionAllocator) VariableExpression(V); 1229311116Sdim E->setOpcode(V->getValueID()); 1230311116Sdim return E; 1231311116Sdim} 1232311116Sdim 1233321369Sdimconst Expression *NewGVN::createVariableOrConstant(Value *V) const { 1234321369Sdim if (auto *C = dyn_cast<Constant>(V)) 1235311116Sdim return createConstantExpression(C); 1236321369Sdim return createVariableExpression(V); 1237311116Sdim} 1238311116Sdim 1239321369Sdimconst ConstantExpression *NewGVN::createConstantExpression(Constant *C) const { 1240311116Sdim auto *E = new (ExpressionAllocator) ConstantExpression(C); 1241311116Sdim E->setOpcode(C->getValueID()); 1242311116Sdim return E; 1243311116Sdim} 1244311116Sdim 1245321369Sdimconst UnknownExpression *NewGVN::createUnknownExpression(Instruction *I) const { 1246311116Sdim auto *E = new (ExpressionAllocator) UnknownExpression(I); 1247311116Sdim E->setOpcode(I->getOpcode()); 1248311116Sdim return E; 1249311116Sdim} 1250311116Sdim 1251321369Sdimconst CallExpression * 1252321369SdimNewGVN::createCallExpression(CallInst *CI, const MemoryAccess *MA) const { 1253311116Sdim // FIXME: Add operand bundles for calls. 1254311116Sdim auto *E = 1255321369Sdim new (ExpressionAllocator) CallExpression(CI->getNumOperands(), CI, MA); 1256321369Sdim setBasicExpressionInfo(CI, E); 1257311116Sdim return E; 1258311116Sdim} 1259311116Sdim 1260321369Sdim// Return true if some equivalent of instruction Inst dominates instruction U. 1261321369Sdimbool NewGVN::someEquivalentDominates(const Instruction *Inst, 1262321369Sdim const Instruction *U) const { 1263321369Sdim auto *CC = ValueToClass.lookup(Inst); 1264327952Sdim // This must be an instruction because we are only called from phi nodes 1265321369Sdim // in the case that the value it needs to check against is an instruction. 1266321369Sdim 1267341825Sdim // The most likely candidates for dominance are the leader and the next leader. 1268321369Sdim // The leader or nextleader will dominate in all cases where there is an 1269321369Sdim // equivalent that is higher up in the dom tree. 1270321369Sdim // We can't *only* check them, however, because the 1271321369Sdim // dominator tree could have an infinite number of non-dominating siblings 1272321369Sdim // with instructions that are in the right congruence class. 1273321369Sdim // A 1274321369Sdim // B C D E F G 1275321369Sdim // | 1276321369Sdim // H 1277321369Sdim // Instruction U could be in H, with equivalents in every other sibling. 1278321369Sdim // Depending on the rpo order picked, the leader could be the equivalent in 1279321369Sdim // any of these siblings. 1280321369Sdim if (!CC) 1281321369Sdim return false; 1282327952Sdim if (alwaysAvailable(CC->getLeader())) 1283327952Sdim return true; 1284321369Sdim if (DT->dominates(cast<Instruction>(CC->getLeader()), U)) 1285321369Sdim return true; 1286321369Sdim if (CC->getNextLeader().first && 1287321369Sdim DT->dominates(cast<Instruction>(CC->getNextLeader().first), U)) 1288321369Sdim return true; 1289321369Sdim return llvm::any_of(*CC, [&](const Value *Member) { 1290321369Sdim return Member != CC->getLeader() && 1291321369Sdim DT->dominates(cast<Instruction>(Member), U); 1292321369Sdim }); 1293321369Sdim} 1294321369Sdim 1295311116Sdim// See if we have a congruence class and leader for this operand, and if so, 1296311116Sdim// return it. Otherwise, return the operand itself. 1297321369SdimValue *NewGVN::lookupOperandLeader(Value *V) const { 1298311116Sdim CongruenceClass *CC = ValueToClass.lookup(V); 1299321369Sdim if (CC) { 1300321369Sdim // Everything in TOP is represented by undef, as it can be any value. 1301321369Sdim // We do have to make sure we get the type right though, so we can't set the 1302321369Sdim // RepLeader to undef. 1303321369Sdim if (CC == TOPClass) 1304321369Sdim return UndefValue::get(V->getType()); 1305321369Sdim return CC->getStoredValue() ? CC->getStoredValue() : CC->getLeader(); 1306321369Sdim } 1307321369Sdim 1308311116Sdim return V; 1309311116Sdim} 1310311116Sdim 1311321369Sdimconst MemoryAccess *NewGVN::lookupMemoryLeader(const MemoryAccess *MA) const { 1312321369Sdim auto *CC = getMemoryClass(MA); 1313321369Sdim assert(CC->getMemoryLeader() && 1314321369Sdim "Every MemoryAccess should be mapped to a congruence class with a " 1315321369Sdim "representative memory access"); 1316321369Sdim return CC->getMemoryLeader(); 1317311116Sdim} 1318311116Sdim 1319321369Sdim// Return true if the MemoryAccess is really equivalent to everything. This is 1320321369Sdim// equivalent to the lattice value "TOP" in most lattices. This is the initial 1321321369Sdim// state of all MemoryAccesses. 1322321369Sdimbool NewGVN::isMemoryAccessTOP(const MemoryAccess *MA) const { 1323321369Sdim return getMemoryClass(MA) == TOPClass; 1324321369Sdim} 1325321369Sdim 1326311116SdimLoadExpression *NewGVN::createLoadExpression(Type *LoadType, Value *PointerOp, 1327321369Sdim LoadInst *LI, 1328321369Sdim const MemoryAccess *MA) const { 1329321369Sdim auto *E = 1330321369Sdim new (ExpressionAllocator) LoadExpression(1, LI, lookupMemoryLeader(MA)); 1331311116Sdim E->allocateOperands(ArgRecycler, ExpressionAllocator); 1332311116Sdim E->setType(LoadType); 1333311116Sdim 1334311116Sdim // Give store and loads same opcode so they value number together. 1335311116Sdim E->setOpcode(0); 1336321369Sdim E->op_push_back(PointerOp); 1337311116Sdim if (LI) 1338360784Sdim E->setAlignment(MaybeAlign(LI->getAlignment())); 1339311116Sdim 1340311116Sdim // TODO: Value number heap versions. We may be able to discover 1341311116Sdim // things alias analysis can't on it's own (IE that a store and a 1342311116Sdim // load have the same value, and thus, it isn't clobbering the load). 1343311116Sdim return E; 1344311116Sdim} 1345311116Sdim 1346321369Sdimconst StoreExpression * 1347321369SdimNewGVN::createStoreExpression(StoreInst *SI, const MemoryAccess *MA) const { 1348321369Sdim auto *StoredValueLeader = lookupOperandLeader(SI->getValueOperand()); 1349321369Sdim auto *E = new (ExpressionAllocator) 1350321369Sdim StoreExpression(SI->getNumOperands(), SI, StoredValueLeader, MA); 1351311116Sdim E->allocateOperands(ArgRecycler, ExpressionAllocator); 1352311116Sdim E->setType(SI->getValueOperand()->getType()); 1353311116Sdim 1354311116Sdim // Give store and loads same opcode so they value number together. 1355311116Sdim E->setOpcode(0); 1356321369Sdim E->op_push_back(lookupOperandLeader(SI->getPointerOperand())); 1357311116Sdim 1358311116Sdim // TODO: Value number heap versions. We may be able to discover 1359311116Sdim // things alias analysis can't on it's own (IE that a store and a 1360311116Sdim // load have the same value, and thus, it isn't clobbering the load). 1361311116Sdim return E; 1362311116Sdim} 1363311116Sdim 1364321369Sdimconst Expression *NewGVN::performSymbolicStoreEvaluation(Instruction *I) const { 1365311116Sdim // Unlike loads, we never try to eliminate stores, so we do not check if they 1366311116Sdim // are simple and avoid value numbering them. 1367311116Sdim auto *SI = cast<StoreInst>(I); 1368321369Sdim auto *StoreAccess = getMemoryAccess(SI); 1369321369Sdim // Get the expression, if any, for the RHS of the MemoryDef. 1370321369Sdim const MemoryAccess *StoreRHS = StoreAccess->getDefiningAccess(); 1371321369Sdim if (EnableStoreRefinement) 1372321369Sdim StoreRHS = MSSAWalker->getClobberingMemoryAccess(StoreAccess); 1373321369Sdim // If we bypassed the use-def chains, make sure we add a use. 1374327952Sdim StoreRHS = lookupMemoryLeader(StoreRHS); 1375321369Sdim if (StoreRHS != StoreAccess->getDefiningAccess()) 1376321369Sdim addMemoryUsers(StoreRHS, StoreAccess); 1377321369Sdim // If we are defined by ourselves, use the live on entry def. 1378321369Sdim if (StoreRHS == StoreAccess) 1379321369Sdim StoreRHS = MSSA->getLiveOnEntryDef(); 1380321369Sdim 1381311116Sdim if (SI->isSimple()) { 1382321369Sdim // See if we are defined by a previous store expression, it already has a 1383321369Sdim // value, and it's the same value as our current store. FIXME: Right now, we 1384321369Sdim // only do this for simple stores, we should expand to cover memcpys, etc. 1385321369Sdim const auto *LastStore = createStoreExpression(SI, StoreRHS); 1386321369Sdim const auto *LastCC = ExpressionToClass.lookup(LastStore); 1387321369Sdim // We really want to check whether the expression we matched was a store. No 1388321369Sdim // easy way to do that. However, we can check that the class we found has a 1389321369Sdim // store, which, assuming the value numbering state is not corrupt, is 1390321369Sdim // sufficient, because we must also be equivalent to that store's expression 1391321369Sdim // for it to be in the same class as the load. 1392321369Sdim if (LastCC && LastCC->getStoredValue() == LastStore->getStoredValue()) 1393321369Sdim return LastStore; 1394321369Sdim // Also check if our value operand is defined by a load of the same memory 1395321369Sdim // location, and the memory state is the same as it was then (otherwise, it 1396321369Sdim // could have been overwritten later. See test32 in 1397321369Sdim // transforms/DeadStoreElimination/simple.ll). 1398321369Sdim if (auto *LI = dyn_cast<LoadInst>(LastStore->getStoredValue())) 1399321369Sdim if ((lookupOperandLeader(LI->getPointerOperand()) == 1400321369Sdim LastStore->getOperand(0)) && 1401321369Sdim (lookupMemoryLeader(getMemoryAccess(LI)->getDefiningAccess()) == 1402321369Sdim StoreRHS)) 1403321369Sdim return LastStore; 1404321369Sdim deleteExpression(LastStore); 1405311116Sdim } 1406311116Sdim 1407321369Sdim // If the store is not equivalent to anything, value number it as a store that 1408321369Sdim // produces a unique memory state (instead of using it's MemoryUse, we use 1409321369Sdim // it's MemoryDef). 1410321369Sdim return createStoreExpression(SI, StoreAccess); 1411311116Sdim} 1412311116Sdim 1413321369Sdim// See if we can extract the value of a loaded pointer from a load, a store, or 1414321369Sdim// a memory instruction. 1415321369Sdimconst Expression * 1416321369SdimNewGVN::performSymbolicLoadCoercion(Type *LoadType, Value *LoadPtr, 1417321369Sdim LoadInst *LI, Instruction *DepInst, 1418321369Sdim MemoryAccess *DefiningAccess) const { 1419321369Sdim assert((!LI || LI->isSimple()) && "Not a simple load"); 1420321369Sdim if (auto *DepSI = dyn_cast<StoreInst>(DepInst)) { 1421321369Sdim // Can't forward from non-atomic to atomic without violating memory model. 1422321369Sdim // Also don't need to coerce if they are the same type, we will just 1423327952Sdim // propagate. 1424321369Sdim if (LI->isAtomic() > DepSI->isAtomic() || 1425321369Sdim LoadType == DepSI->getValueOperand()->getType()) 1426321369Sdim return nullptr; 1427321369Sdim int Offset = analyzeLoadFromClobberingStore(LoadType, LoadPtr, DepSI, DL); 1428321369Sdim if (Offset >= 0) { 1429321369Sdim if (auto *C = dyn_cast<Constant>( 1430321369Sdim lookupOperandLeader(DepSI->getValueOperand()))) { 1431341825Sdim LLVM_DEBUG(dbgs() << "Coercing load from store " << *DepSI 1432341825Sdim << " to constant " << *C << "\n"); 1433321369Sdim return createConstantExpression( 1434321369Sdim getConstantStoreValueForLoad(C, Offset, LoadType, DL)); 1435321369Sdim } 1436321369Sdim } 1437327952Sdim } else if (auto *DepLI = dyn_cast<LoadInst>(DepInst)) { 1438321369Sdim // Can't forward from non-atomic to atomic without violating memory model. 1439321369Sdim if (LI->isAtomic() > DepLI->isAtomic()) 1440321369Sdim return nullptr; 1441321369Sdim int Offset = analyzeLoadFromClobberingLoad(LoadType, LoadPtr, DepLI, DL); 1442321369Sdim if (Offset >= 0) { 1443327952Sdim // We can coerce a constant load into a load. 1444321369Sdim if (auto *C = dyn_cast<Constant>(lookupOperandLeader(DepLI))) 1445321369Sdim if (auto *PossibleConstant = 1446321369Sdim getConstantLoadValueForLoad(C, Offset, LoadType, DL)) { 1447341825Sdim LLVM_DEBUG(dbgs() << "Coercing load from load " << *LI 1448341825Sdim << " to constant " << *PossibleConstant << "\n"); 1449321369Sdim return createConstantExpression(PossibleConstant); 1450321369Sdim } 1451321369Sdim } 1452327952Sdim } else if (auto *DepMI = dyn_cast<MemIntrinsic>(DepInst)) { 1453321369Sdim int Offset = analyzeLoadFromClobberingMemInst(LoadType, LoadPtr, DepMI, DL); 1454321369Sdim if (Offset >= 0) { 1455321369Sdim if (auto *PossibleConstant = 1456321369Sdim getConstantMemInstValueForLoad(DepMI, Offset, LoadType, DL)) { 1457341825Sdim LLVM_DEBUG(dbgs() << "Coercing load from meminst " << *DepMI 1458341825Sdim << " to constant " << *PossibleConstant << "\n"); 1459321369Sdim return createConstantExpression(PossibleConstant); 1460321369Sdim } 1461321369Sdim } 1462321369Sdim } 1463321369Sdim 1464321369Sdim // All of the below are only true if the loaded pointer is produced 1465321369Sdim // by the dependent instruction. 1466321369Sdim if (LoadPtr != lookupOperandLeader(DepInst) && 1467321369Sdim !AA->isMustAlias(LoadPtr, DepInst)) 1468321369Sdim return nullptr; 1469321369Sdim // If this load really doesn't depend on anything, then we must be loading an 1470321369Sdim // undef value. This can happen when loading for a fresh allocation with no 1471321369Sdim // intervening stores, for example. Note that this is only true in the case 1472321369Sdim // that the result of the allocation is pointer equal to the load ptr. 1473321369Sdim if (isa<AllocaInst>(DepInst) || isMallocLikeFn(DepInst, TLI)) { 1474321369Sdim return createConstantExpression(UndefValue::get(LoadType)); 1475321369Sdim } 1476321369Sdim // If this load occurs either right after a lifetime begin, 1477321369Sdim // then the loaded value is undefined. 1478321369Sdim else if (auto *II = dyn_cast<IntrinsicInst>(DepInst)) { 1479321369Sdim if (II->getIntrinsicID() == Intrinsic::lifetime_start) 1480321369Sdim return createConstantExpression(UndefValue::get(LoadType)); 1481321369Sdim } 1482321369Sdim // If this load follows a calloc (which zero initializes memory), 1483321369Sdim // then the loaded value is zero 1484321369Sdim else if (isCallocLikeFn(DepInst, TLI)) { 1485321369Sdim return createConstantExpression(Constant::getNullValue(LoadType)); 1486321369Sdim } 1487321369Sdim 1488321369Sdim return nullptr; 1489321369Sdim} 1490321369Sdim 1491321369Sdimconst Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I) const { 1492311116Sdim auto *LI = cast<LoadInst>(I); 1493311116Sdim 1494311116Sdim // We can eliminate in favor of non-simple loads, but we won't be able to 1495311116Sdim // eliminate the loads themselves. 1496311116Sdim if (!LI->isSimple()) 1497311116Sdim return nullptr; 1498311116Sdim 1499321369Sdim Value *LoadAddressLeader = lookupOperandLeader(LI->getPointerOperand()); 1500311116Sdim // Load of undef is undef. 1501311116Sdim if (isa<UndefValue>(LoadAddressLeader)) 1502311116Sdim return createConstantExpression(UndefValue::get(LI->getType())); 1503321369Sdim MemoryAccess *OriginalAccess = getMemoryAccess(I); 1504321369Sdim MemoryAccess *DefiningAccess = 1505321369Sdim MSSAWalker->getClobberingMemoryAccess(OriginalAccess); 1506311116Sdim 1507311116Sdim if (!MSSA->isLiveOnEntryDef(DefiningAccess)) { 1508311116Sdim if (auto *MD = dyn_cast<MemoryDef>(DefiningAccess)) { 1509311116Sdim Instruction *DefiningInst = MD->getMemoryInst(); 1510311116Sdim // If the defining instruction is not reachable, replace with undef. 1511311116Sdim if (!ReachableBlocks.count(DefiningInst->getParent())) 1512311116Sdim return createConstantExpression(UndefValue::get(LI->getType())); 1513321369Sdim // This will handle stores and memory insts. We only do if it the 1514321369Sdim // defining access has a different type, or it is a pointer produced by 1515321369Sdim // certain memory operations that cause the memory to have a fixed value 1516321369Sdim // (IE things like calloc). 1517321369Sdim if (const auto *CoercionResult = 1518321369Sdim performSymbolicLoadCoercion(LI->getType(), LoadAddressLeader, LI, 1519321369Sdim DefiningInst, DefiningAccess)) 1520321369Sdim return CoercionResult; 1521311116Sdim } 1522311116Sdim } 1523311116Sdim 1524327952Sdim const auto *LE = createLoadExpression(LI->getType(), LoadAddressLeader, LI, 1525327952Sdim DefiningAccess); 1526327952Sdim // If our MemoryLeader is not our defining access, add a use to the 1527327952Sdim // MemoryLeader, so that we get reprocessed when it changes. 1528327952Sdim if (LE->getMemoryLeader() != DefiningAccess) 1529327952Sdim addMemoryUsers(LE->getMemoryLeader(), OriginalAccess); 1530327952Sdim return LE; 1531311116Sdim} 1532311116Sdim 1533321369Sdimconst Expression * 1534321369SdimNewGVN::performSymbolicPredicateInfoEvaluation(Instruction *I) const { 1535321369Sdim auto *PI = PredInfo->getPredicateInfoFor(I); 1536321369Sdim if (!PI) 1537321369Sdim return nullptr; 1538321369Sdim 1539341825Sdim LLVM_DEBUG(dbgs() << "Found predicate info from instruction !\n"); 1540321369Sdim 1541321369Sdim auto *PWC = dyn_cast<PredicateWithCondition>(PI); 1542321369Sdim if (!PWC) 1543321369Sdim return nullptr; 1544321369Sdim 1545321369Sdim auto *CopyOf = I->getOperand(0); 1546321369Sdim auto *Cond = PWC->Condition; 1547321369Sdim 1548321369Sdim // If this a copy of the condition, it must be either true or false depending 1549327952Sdim // on the predicate info type and edge. 1550321369Sdim if (CopyOf == Cond) { 1551321369Sdim // We should not need to add predicate users because the predicate info is 1552321369Sdim // already a use of this operand. 1553321369Sdim if (isa<PredicateAssume>(PI)) 1554321369Sdim return createConstantExpression(ConstantInt::getTrue(Cond->getType())); 1555321369Sdim if (auto *PBranch = dyn_cast<PredicateBranch>(PI)) { 1556321369Sdim if (PBranch->TrueEdge) 1557321369Sdim return createConstantExpression(ConstantInt::getTrue(Cond->getType())); 1558321369Sdim return createConstantExpression(ConstantInt::getFalse(Cond->getType())); 1559321369Sdim } 1560321369Sdim if (auto *PSwitch = dyn_cast<PredicateSwitch>(PI)) 1561321369Sdim return createConstantExpression(cast<Constant>(PSwitch->CaseValue)); 1562321369Sdim } 1563321369Sdim 1564321369Sdim // Not a copy of the condition, so see what the predicates tell us about this 1565321369Sdim // value. First, though, we check to make sure the value is actually a copy 1566321369Sdim // of one of the condition operands. It's possible, in certain cases, for it 1567321369Sdim // to be a copy of a predicateinfo copy. In particular, if two branch 1568321369Sdim // operations use the same condition, and one branch dominates the other, we 1569321369Sdim // will end up with a copy of a copy. This is currently a small deficiency in 1570321369Sdim // predicateinfo. What will end up happening here is that we will value 1571321369Sdim // number both copies the same anyway. 1572321369Sdim 1573321369Sdim // Everything below relies on the condition being a comparison. 1574321369Sdim auto *Cmp = dyn_cast<CmpInst>(Cond); 1575321369Sdim if (!Cmp) 1576321369Sdim return nullptr; 1577321369Sdim 1578321369Sdim if (CopyOf != Cmp->getOperand(0) && CopyOf != Cmp->getOperand(1)) { 1579341825Sdim LLVM_DEBUG(dbgs() << "Copy is not of any condition operands!\n"); 1580321369Sdim return nullptr; 1581321369Sdim } 1582321369Sdim Value *FirstOp = lookupOperandLeader(Cmp->getOperand(0)); 1583321369Sdim Value *SecondOp = lookupOperandLeader(Cmp->getOperand(1)); 1584321369Sdim bool SwappedOps = false; 1585327952Sdim // Sort the ops. 1586321369Sdim if (shouldSwapOperands(FirstOp, SecondOp)) { 1587321369Sdim std::swap(FirstOp, SecondOp); 1588321369Sdim SwappedOps = true; 1589321369Sdim } 1590321369Sdim CmpInst::Predicate Predicate = 1591321369Sdim SwappedOps ? Cmp->getSwappedPredicate() : Cmp->getPredicate(); 1592321369Sdim 1593321369Sdim if (isa<PredicateAssume>(PI)) { 1594341825Sdim // If we assume the operands are equal, then they are equal. 1595341825Sdim if (Predicate == CmpInst::ICMP_EQ) { 1596321369Sdim addPredicateUsers(PI, I); 1597341825Sdim addAdditionalUsers(SwappedOps ? Cmp->getOperand(1) : Cmp->getOperand(0), 1598341825Sdim I); 1599321369Sdim return createVariableOrConstant(FirstOp); 1600321369Sdim } 1601321369Sdim } 1602321369Sdim if (const auto *PBranch = dyn_cast<PredicateBranch>(PI)) { 1603321369Sdim // If we are *not* a copy of the comparison, we may equal to the other 1604321369Sdim // operand when the predicate implies something about equality of 1605321369Sdim // operations. In particular, if the comparison is true/false when the 1606321369Sdim // operands are equal, and we are on the right edge, we know this operation 1607321369Sdim // is equal to something. 1608321369Sdim if ((PBranch->TrueEdge && Predicate == CmpInst::ICMP_EQ) || 1609321369Sdim (!PBranch->TrueEdge && Predicate == CmpInst::ICMP_NE)) { 1610321369Sdim addPredicateUsers(PI, I); 1611327952Sdim addAdditionalUsers(SwappedOps ? Cmp->getOperand(1) : Cmp->getOperand(0), 1612327952Sdim I); 1613321369Sdim return createVariableOrConstant(FirstOp); 1614321369Sdim } 1615321369Sdim // Handle the special case of floating point. 1616321369Sdim if (((PBranch->TrueEdge && Predicate == CmpInst::FCMP_OEQ) || 1617321369Sdim (!PBranch->TrueEdge && Predicate == CmpInst::FCMP_UNE)) && 1618321369Sdim isa<ConstantFP>(FirstOp) && !cast<ConstantFP>(FirstOp)->isZero()) { 1619321369Sdim addPredicateUsers(PI, I); 1620327952Sdim addAdditionalUsers(SwappedOps ? Cmp->getOperand(1) : Cmp->getOperand(0), 1621327952Sdim I); 1622321369Sdim return createConstantExpression(cast<Constant>(FirstOp)); 1623321369Sdim } 1624321369Sdim } 1625321369Sdim return nullptr; 1626321369Sdim} 1627321369Sdim 1628311116Sdim// Evaluate read only and pure calls, and create an expression result. 1629321369Sdimconst Expression *NewGVN::performSymbolicCallEvaluation(Instruction *I) const { 1630311116Sdim auto *CI = cast<CallInst>(I); 1631321369Sdim if (auto *II = dyn_cast<IntrinsicInst>(I)) { 1632341825Sdim // Intrinsics with the returned attribute are copies of arguments. 1633321369Sdim if (auto *ReturnedValue = II->getReturnedArgOperand()) { 1634321369Sdim if (II->getIntrinsicID() == Intrinsic::ssa_copy) 1635321369Sdim if (const auto *Result = performSymbolicPredicateInfoEvaluation(I)) 1636321369Sdim return Result; 1637321369Sdim return createVariableOrConstant(ReturnedValue); 1638321369Sdim } 1639321369Sdim } 1640321369Sdim if (AA->doesNotAccessMemory(CI)) { 1641321369Sdim return createCallExpression(CI, TOPClass->getMemoryLeader()); 1642321369Sdim } else if (AA->onlyReadsMemory(CI)) { 1643360784Sdim if (auto *MA = MSSA->getMemoryAccess(CI)) { 1644360784Sdim auto *DefiningAccess = MSSAWalker->getClobberingMemoryAccess(MA); 1645360784Sdim return createCallExpression(CI, DefiningAccess); 1646360784Sdim } else // MSSA determined that CI does not access memory. 1647360784Sdim return createCallExpression(CI, TOPClass->getMemoryLeader()); 1648311116Sdim } 1649311116Sdim return nullptr; 1650311116Sdim} 1651311116Sdim 1652321369Sdim// Retrieve the memory class for a given MemoryAccess. 1653321369SdimCongruenceClass *NewGVN::getMemoryClass(const MemoryAccess *MA) const { 1654321369Sdim auto *Result = MemoryAccessToClass.lookup(MA); 1655321369Sdim assert(Result && "Should have found memory class"); 1656321369Sdim return Result; 1657321369Sdim} 1658321369Sdim 1659321369Sdim// Update the MemoryAccess equivalence table to say that From is equal to To, 1660311116Sdim// and return true if this is different from what already existed in the table. 1661321369Sdimbool NewGVN::setMemoryClass(const MemoryAccess *From, 1662321369Sdim CongruenceClass *NewClass) { 1663321369Sdim assert(NewClass && 1664321369Sdim "Every MemoryAccess should be getting mapped to a non-null class"); 1665341825Sdim LLVM_DEBUG(dbgs() << "Setting " << *From); 1666341825Sdim LLVM_DEBUG(dbgs() << " equivalent to congruence class "); 1667341825Sdim LLVM_DEBUG(dbgs() << NewClass->getID() 1668341825Sdim << " with current MemoryAccess leader "); 1669341825Sdim LLVM_DEBUG(dbgs() << *NewClass->getMemoryLeader() << "\n"); 1670321369Sdim 1671321369Sdim auto LookupResult = MemoryAccessToClass.find(From); 1672311116Sdim bool Changed = false; 1673311116Sdim // If it's already in the table, see if the value changed. 1674321369Sdim if (LookupResult != MemoryAccessToClass.end()) { 1675321369Sdim auto *OldClass = LookupResult->second; 1676321369Sdim if (OldClass != NewClass) { 1677321369Sdim // If this is a phi, we have to handle memory member updates. 1678321369Sdim if (auto *MP = dyn_cast<MemoryPhi>(From)) { 1679321369Sdim OldClass->memory_erase(MP); 1680321369Sdim NewClass->memory_insert(MP); 1681321369Sdim // This may have killed the class if it had no non-memory members 1682321369Sdim if (OldClass->getMemoryLeader() == From) { 1683321369Sdim if (OldClass->definesNoMemory()) { 1684321369Sdim OldClass->setMemoryLeader(nullptr); 1685321369Sdim } else { 1686321369Sdim OldClass->setMemoryLeader(getNextMemoryLeader(OldClass)); 1687341825Sdim LLVM_DEBUG(dbgs() << "Memory class leader change for class " 1688341825Sdim << OldClass->getID() << " to " 1689341825Sdim << *OldClass->getMemoryLeader() 1690341825Sdim << " due to removal of a memory member " << *From 1691341825Sdim << "\n"); 1692321369Sdim markMemoryLeaderChangeTouched(OldClass); 1693321369Sdim } 1694321369Sdim } 1695321369Sdim } 1696311116Sdim // It wasn't equivalent before, and now it is. 1697321369Sdim LookupResult->second = NewClass; 1698311116Sdim Changed = true; 1699311116Sdim } 1700311116Sdim } 1701311116Sdim 1702311116Sdim return Changed; 1703311116Sdim} 1704321369Sdim 1705321369Sdim// Determine if a instruction is cycle-free. That means the values in the 1706321369Sdim// instruction don't depend on any expressions that can change value as a result 1707321369Sdim// of the instruction. For example, a non-cycle free instruction would be v = 1708321369Sdim// phi(0, v+1). 1709321369Sdimbool NewGVN::isCycleFree(const Instruction *I) const { 1710321369Sdim // In order to compute cycle-freeness, we do SCC finding on the instruction, 1711321369Sdim // and see what kind of SCC it ends up in. If it is a singleton, it is 1712321369Sdim // cycle-free. If it is not in a singleton, it is only cycle free if the 1713321369Sdim // other members are all phi nodes (as they do not compute anything, they are 1714321369Sdim // copies). 1715321369Sdim auto ICS = InstCycleState.lookup(I); 1716321369Sdim if (ICS == ICS_Unknown) { 1717321369Sdim SCCFinder.Start(I); 1718321369Sdim auto &SCC = SCCFinder.getComponentFor(I); 1719341825Sdim // It's cycle free if it's size 1 or the SCC is *only* phi nodes. 1720321369Sdim if (SCC.size() == 1) 1721321369Sdim InstCycleState.insert({I, ICS_CycleFree}); 1722321369Sdim else { 1723327952Sdim bool AllPhis = llvm::all_of(SCC, [](const Value *V) { 1724327952Sdim return isa<PHINode>(V) || isCopyOfAPHI(V); 1725327952Sdim }); 1726321369Sdim ICS = AllPhis ? ICS_CycleFree : ICS_Cycle; 1727321369Sdim for (auto *Member : SCC) 1728321369Sdim if (auto *MemberPhi = dyn_cast<PHINode>(Member)) 1729321369Sdim InstCycleState.insert({MemberPhi, ICS}); 1730321369Sdim } 1731321369Sdim } 1732321369Sdim if (ICS == ICS_Cycle) 1733321369Sdim return false; 1734321369Sdim return true; 1735321369Sdim} 1736321369Sdim 1737327952Sdim// Evaluate PHI nodes symbolically and create an expression result. 1738327952Sdimconst Expression * 1739327952SdimNewGVN::performSymbolicPHIEvaluation(ArrayRef<ValPair> PHIOps, 1740327952Sdim Instruction *I, 1741327952Sdim BasicBlock *PHIBlock) const { 1742321369Sdim // True if one of the incoming phi edges is a backedge. 1743321369Sdim bool HasBackedge = false; 1744321369Sdim // All constant tracks the state of whether all the *original* phi operands 1745321369Sdim // This is really shorthand for "this phi cannot cycle due to forward 1746321369Sdim // change in value of the phi is guaranteed not to later change the value of 1747321369Sdim // the phi. IE it can't be v = phi(undef, v+1) 1748327952Sdim bool OriginalOpsConstant = true; 1749327952Sdim auto *E = cast<PHIExpression>(createPHIExpression( 1750327952Sdim PHIOps, I, PHIBlock, HasBackedge, OriginalOpsConstant)); 1751311833Sdim // We match the semantics of SimplifyPhiNode from InstructionSimplify here. 1752321369Sdim // See if all arguments are the same. 1753311833Sdim // We track if any were undef because they need special handling. 1754311833Sdim bool HasUndef = false; 1755321369Sdim auto Filtered = make_filter_range(E->operands(), [&](Value *Arg) { 1756311833Sdim if (isa<UndefValue>(Arg)) { 1757311833Sdim HasUndef = true; 1758311833Sdim return false; 1759311833Sdim } 1760311833Sdim return true; 1761311833Sdim }); 1762321369Sdim // If we are left with no operands, it's dead. 1763360784Sdim if (Filtered.empty()) { 1764321369Sdim // If it has undef at this point, it means there are no-non-undef arguments, 1765321369Sdim // and thus, the value of the phi node must be undef. 1766321369Sdim if (HasUndef) { 1767341825Sdim LLVM_DEBUG( 1768341825Sdim dbgs() << "PHI Node " << *I 1769341825Sdim << " has no non-undef arguments, valuing it as undef\n"); 1770321369Sdim return createConstantExpression(UndefValue::get(I->getType())); 1771321369Sdim } 1772321369Sdim 1773341825Sdim LLVM_DEBUG(dbgs() << "No arguments of PHI node " << *I << " are live\n"); 1774321369Sdim deleteExpression(E); 1775321369Sdim return createDeadExpression(); 1776311116Sdim } 1777311833Sdim Value *AllSameValue = *(Filtered.begin()); 1778311833Sdim ++Filtered.begin(); 1779311833Sdim // Can't use std::equal here, sadly, because filter.begin moves. 1780327952Sdim if (llvm::all_of(Filtered, [&](Value *Arg) { return Arg == AllSameValue; })) { 1781311833Sdim // In LLVM's non-standard representation of phi nodes, it's possible to have 1782311833Sdim // phi nodes with cycles (IE dependent on other phis that are .... dependent 1783311833Sdim // on the original phi node), especially in weird CFG's where some arguments 1784311833Sdim // are unreachable, or uninitialized along certain paths. This can cause 1785311833Sdim // infinite loops during evaluation. We work around this by not trying to 1786311833Sdim // really evaluate them independently, but instead using a variable 1787311833Sdim // expression to say if one is equivalent to the other. 1788311833Sdim // We also special case undef, so that if we have an undef, we can't use the 1789311833Sdim // common value unless it dominates the phi block. 1790311833Sdim if (HasUndef) { 1791321369Sdim // If we have undef and at least one other value, this is really a 1792321369Sdim // multivalued phi, and we need to know if it's cycle free in order to 1793321369Sdim // evaluate whether we can ignore the undef. The other parts of this are 1794321369Sdim // just shortcuts. If there is no backedge, or all operands are 1795327952Sdim // constants, it also must be cycle free. 1796327952Sdim if (HasBackedge && !OriginalOpsConstant && 1797321369Sdim !isa<UndefValue>(AllSameValue) && !isCycleFree(I)) 1798321369Sdim return E; 1799321369Sdim 1800311833Sdim // Only have to check for instructions 1801311833Sdim if (auto *AllSameInst = dyn_cast<Instruction>(AllSameValue)) 1802321369Sdim if (!someEquivalentDominates(AllSameInst, I)) 1803311833Sdim return E; 1804311116Sdim } 1805321369Sdim // Can't simplify to something that comes later in the iteration. 1806321369Sdim // Otherwise, when and if it changes congruence class, we will never catch 1807321369Sdim // up. We will always be a class behind it. 1808321369Sdim if (isa<Instruction>(AllSameValue) && 1809321369Sdim InstrToDFSNum(AllSameValue) > InstrToDFSNum(I)) 1810321369Sdim return E; 1811311116Sdim NumGVNPhisAllSame++; 1812341825Sdim LLVM_DEBUG(dbgs() << "Simplified PHI node " << *I << " to " << *AllSameValue 1813341825Sdim << "\n"); 1814321369Sdim deleteExpression(E); 1815321369Sdim return createVariableOrConstant(AllSameValue); 1816311116Sdim } 1817311116Sdim return E; 1818311116Sdim} 1819311116Sdim 1820311116Sdimconst Expression * 1821321369SdimNewGVN::performSymbolicAggrValueEvaluation(Instruction *I) const { 1822311116Sdim if (auto *EI = dyn_cast<ExtractValueInst>(I)) { 1823353358Sdim auto *WO = dyn_cast<WithOverflowInst>(EI->getAggregateOperand()); 1824353358Sdim if (WO && EI->getNumIndices() == 1 && *EI->idx_begin() == 0) 1825353358Sdim // EI is an extract from one of our with.overflow intrinsics. Synthesize 1826353358Sdim // a semantically equivalent expression instead of an extract value 1827353358Sdim // expression. 1828353358Sdim return createBinaryExpression(WO->getBinaryOp(), EI->getType(), 1829353358Sdim WO->getLHS(), WO->getRHS(), I); 1830311116Sdim } 1831311116Sdim 1832321369Sdim return createAggregateValueExpression(I); 1833311116Sdim} 1834327952Sdim 1835321369Sdimconst Expression *NewGVN::performSymbolicCmpEvaluation(Instruction *I) const { 1836327952Sdim assert(isa<CmpInst>(I) && "Expected a cmp instruction."); 1837327952Sdim 1838327952Sdim auto *CI = cast<CmpInst>(I); 1839321369Sdim // See if our operands are equal to those of a previous predicate, and if so, 1840321369Sdim // if it implies true or false. 1841321369Sdim auto Op0 = lookupOperandLeader(CI->getOperand(0)); 1842321369Sdim auto Op1 = lookupOperandLeader(CI->getOperand(1)); 1843321369Sdim auto OurPredicate = CI->getPredicate(); 1844321369Sdim if (shouldSwapOperands(Op0, Op1)) { 1845321369Sdim std::swap(Op0, Op1); 1846321369Sdim OurPredicate = CI->getSwappedPredicate(); 1847321369Sdim } 1848311116Sdim 1849327952Sdim // Avoid processing the same info twice. 1850321369Sdim const PredicateBase *LastPredInfo = nullptr; 1851321369Sdim // See if we know something about the comparison itself, like it is the target 1852321369Sdim // of an assume. 1853321369Sdim auto *CmpPI = PredInfo->getPredicateInfoFor(I); 1854321369Sdim if (dyn_cast_or_null<PredicateAssume>(CmpPI)) 1855321369Sdim return createConstantExpression(ConstantInt::getTrue(CI->getType())); 1856321369Sdim 1857321369Sdim if (Op0 == Op1) { 1858321369Sdim // This condition does not depend on predicates, no need to add users 1859321369Sdim if (CI->isTrueWhenEqual()) 1860321369Sdim return createConstantExpression(ConstantInt::getTrue(CI->getType())); 1861321369Sdim else if (CI->isFalseWhenEqual()) 1862321369Sdim return createConstantExpression(ConstantInt::getFalse(CI->getType())); 1863321369Sdim } 1864321369Sdim 1865321369Sdim // NOTE: Because we are comparing both operands here and below, and using 1866321369Sdim // previous comparisons, we rely on fact that predicateinfo knows to mark 1867321369Sdim // comparisons that use renamed operands as users of the earlier comparisons. 1868321369Sdim // It is *not* enough to just mark predicateinfo renamed operands as users of 1869321369Sdim // the earlier comparisons, because the *other* operand may have changed in a 1870321369Sdim // previous iteration. 1871321369Sdim // Example: 1872321369Sdim // icmp slt %a, %b 1873321369Sdim // %b.0 = ssa.copy(%b) 1874321369Sdim // false branch: 1875321369Sdim // icmp slt %c, %b.0 1876321369Sdim 1877321369Sdim // %c and %a may start out equal, and thus, the code below will say the second 1878321369Sdim // %icmp is false. c may become equal to something else, and in that case the 1879321369Sdim // %second icmp *must* be reexamined, but would not if only the renamed 1880321369Sdim // %operands are considered users of the icmp. 1881321369Sdim 1882321369Sdim // *Currently* we only check one level of comparisons back, and only mark one 1883327952Sdim // level back as touched when changes happen. If you modify this code to look 1884321369Sdim // back farther through comparisons, you *must* mark the appropriate 1885321369Sdim // comparisons as users in PredicateInfo.cpp, or you will cause bugs. See if 1886321369Sdim // we know something just from the operands themselves 1887321369Sdim 1888321369Sdim // See if our operands have predicate info, so that we may be able to derive 1889321369Sdim // something from a previous comparison. 1890321369Sdim for (const auto &Op : CI->operands()) { 1891321369Sdim auto *PI = PredInfo->getPredicateInfoFor(Op); 1892321369Sdim if (const auto *PBranch = dyn_cast_or_null<PredicateBranch>(PI)) { 1893321369Sdim if (PI == LastPredInfo) 1894321369Sdim continue; 1895321369Sdim LastPredInfo = PI; 1896327952Sdim // In phi of ops cases, we may have predicate info that we are evaluating 1897327952Sdim // in a different context. 1898327952Sdim if (!DT->dominates(PBranch->To, getBlockForValue(I))) 1899327952Sdim continue; 1900327952Sdim // TODO: Along the false edge, we may know more things too, like 1901327952Sdim // icmp of 1902321369Sdim // same operands is false. 1903327952Sdim // TODO: We only handle actual comparison conditions below, not 1904327952Sdim // and/or. 1905321369Sdim auto *BranchCond = dyn_cast<CmpInst>(PBranch->Condition); 1906321369Sdim if (!BranchCond) 1907321369Sdim continue; 1908321369Sdim auto *BranchOp0 = lookupOperandLeader(BranchCond->getOperand(0)); 1909321369Sdim auto *BranchOp1 = lookupOperandLeader(BranchCond->getOperand(1)); 1910321369Sdim auto BranchPredicate = BranchCond->getPredicate(); 1911321369Sdim if (shouldSwapOperands(BranchOp0, BranchOp1)) { 1912321369Sdim std::swap(BranchOp0, BranchOp1); 1913321369Sdim BranchPredicate = BranchCond->getSwappedPredicate(); 1914321369Sdim } 1915321369Sdim if (BranchOp0 == Op0 && BranchOp1 == Op1) { 1916321369Sdim if (PBranch->TrueEdge) { 1917321369Sdim // If we know the previous predicate is true and we are in the true 1918321369Sdim // edge then we may be implied true or false. 1919321369Sdim if (CmpInst::isImpliedTrueByMatchingCmp(BranchPredicate, 1920321369Sdim OurPredicate)) { 1921321369Sdim addPredicateUsers(PI, I); 1922321369Sdim return createConstantExpression( 1923321369Sdim ConstantInt::getTrue(CI->getType())); 1924321369Sdim } 1925321369Sdim 1926321369Sdim if (CmpInst::isImpliedFalseByMatchingCmp(BranchPredicate, 1927321369Sdim OurPredicate)) { 1928321369Sdim addPredicateUsers(PI, I); 1929321369Sdim return createConstantExpression( 1930321369Sdim ConstantInt::getFalse(CI->getType())); 1931321369Sdim } 1932321369Sdim } else { 1933321369Sdim // Just handle the ne and eq cases, where if we have the same 1934321369Sdim // operands, we may know something. 1935321369Sdim if (BranchPredicate == OurPredicate) { 1936321369Sdim addPredicateUsers(PI, I); 1937321369Sdim // Same predicate, same ops,we know it was false, so this is false. 1938321369Sdim return createConstantExpression( 1939321369Sdim ConstantInt::getFalse(CI->getType())); 1940321369Sdim } else if (BranchPredicate == 1941321369Sdim CmpInst::getInversePredicate(OurPredicate)) { 1942321369Sdim addPredicateUsers(PI, I); 1943321369Sdim // Inverse predicate, we know the other was false, so this is true. 1944321369Sdim return createConstantExpression( 1945321369Sdim ConstantInt::getTrue(CI->getType())); 1946321369Sdim } 1947321369Sdim } 1948321369Sdim } 1949321369Sdim } 1950321369Sdim } 1951321369Sdim // Create expression will take care of simplifyCmpInst 1952321369Sdim return createExpression(I); 1953321369Sdim} 1954321369Sdim 1955311116Sdim// Substitute and symbolize the value before value numbering. 1956321369Sdimconst Expression * 1957321369SdimNewGVN::performSymbolicEvaluation(Value *V, 1958321369Sdim SmallPtrSetImpl<Value *> &Visited) const { 1959311116Sdim const Expression *E = nullptr; 1960311116Sdim if (auto *C = dyn_cast<Constant>(V)) 1961311116Sdim E = createConstantExpression(C); 1962311116Sdim else if (isa<Argument>(V) || isa<GlobalVariable>(V)) { 1963311116Sdim E = createVariableExpression(V); 1964311116Sdim } else { 1965311116Sdim // TODO: memory intrinsics. 1966311116Sdim // TODO: Some day, we should do the forward propagation and reassociation 1967311116Sdim // parts of the algorithm. 1968311116Sdim auto *I = cast<Instruction>(V); 1969311116Sdim switch (I->getOpcode()) { 1970311116Sdim case Instruction::ExtractValue: 1971311116Sdim case Instruction::InsertValue: 1972321369Sdim E = performSymbolicAggrValueEvaluation(I); 1973311116Sdim break; 1974327952Sdim case Instruction::PHI: { 1975327952Sdim SmallVector<ValPair, 3> Ops; 1976327952Sdim auto *PN = cast<PHINode>(I); 1977327952Sdim for (unsigned i = 0; i < PN->getNumOperands(); ++i) 1978327952Sdim Ops.push_back({PN->getIncomingValue(i), PN->getIncomingBlock(i)}); 1979327952Sdim // Sort to ensure the invariant createPHIExpression requires is met. 1980327952Sdim sortPHIOps(Ops); 1981327952Sdim E = performSymbolicPHIEvaluation(Ops, I, getBlockForValue(I)); 1982327952Sdim } break; 1983311116Sdim case Instruction::Call: 1984321369Sdim E = performSymbolicCallEvaluation(I); 1985311116Sdim break; 1986311116Sdim case Instruction::Store: 1987321369Sdim E = performSymbolicStoreEvaluation(I); 1988311116Sdim break; 1989311116Sdim case Instruction::Load: 1990321369Sdim E = performSymbolicLoadEvaluation(I); 1991311116Sdim break; 1992341825Sdim case Instruction::BitCast: 1993353358Sdim case Instruction::AddrSpaceCast: 1994321369Sdim E = createExpression(I); 1995327952Sdim break; 1996321369Sdim case Instruction::ICmp: 1997327952Sdim case Instruction::FCmp: 1998321369Sdim E = performSymbolicCmpEvaluation(I); 1999327952Sdim break; 2000353358Sdim case Instruction::FNeg: 2001311116Sdim case Instruction::Add: 2002311116Sdim case Instruction::FAdd: 2003311116Sdim case Instruction::Sub: 2004311116Sdim case Instruction::FSub: 2005311116Sdim case Instruction::Mul: 2006311116Sdim case Instruction::FMul: 2007311116Sdim case Instruction::UDiv: 2008311116Sdim case Instruction::SDiv: 2009311116Sdim case Instruction::FDiv: 2010311116Sdim case Instruction::URem: 2011311116Sdim case Instruction::SRem: 2012311116Sdim case Instruction::FRem: 2013311116Sdim case Instruction::Shl: 2014311116Sdim case Instruction::LShr: 2015311116Sdim case Instruction::AShr: 2016311116Sdim case Instruction::And: 2017311116Sdim case Instruction::Or: 2018311116Sdim case Instruction::Xor: 2019311116Sdim case Instruction::Trunc: 2020311116Sdim case Instruction::ZExt: 2021311116Sdim case Instruction::SExt: 2022311116Sdim case Instruction::FPToUI: 2023311116Sdim case Instruction::FPToSI: 2024311116Sdim case Instruction::UIToFP: 2025311116Sdim case Instruction::SIToFP: 2026311116Sdim case Instruction::FPTrunc: 2027311116Sdim case Instruction::FPExt: 2028311116Sdim case Instruction::PtrToInt: 2029311116Sdim case Instruction::IntToPtr: 2030311116Sdim case Instruction::Select: 2031311116Sdim case Instruction::ExtractElement: 2032311116Sdim case Instruction::InsertElement: 2033311116Sdim case Instruction::ShuffleVector: 2034311116Sdim case Instruction::GetElementPtr: 2035321369Sdim E = createExpression(I); 2036311116Sdim break; 2037311116Sdim default: 2038311116Sdim return nullptr; 2039311116Sdim } 2040311116Sdim } 2041311116Sdim return E; 2042311116Sdim} 2043311116Sdim 2044321369Sdim// Look up a container in a map, and then call a function for each thing in the 2045321369Sdim// found container. 2046321369Sdimtemplate <typename Map, typename KeyType, typename Func> 2047321369Sdimvoid NewGVN::for_each_found(Map &M, const KeyType &Key, Func F) { 2048321369Sdim const auto Result = M.find_as(Key); 2049321369Sdim if (Result != M.end()) 2050321369Sdim for (typename Map::mapped_type::value_type Mapped : Result->second) 2051321369Sdim F(Mapped); 2052321369Sdim} 2053311116Sdim 2054321369Sdim// Look up a container of values/instructions in a map, and touch all the 2055321369Sdim// instructions in the container. Then erase value from the map. 2056321369Sdimtemplate <typename Map, typename KeyType> 2057321369Sdimvoid NewGVN::touchAndErase(Map &M, const KeyType &Key) { 2058321369Sdim const auto Result = M.find_as(Key); 2059321369Sdim if (Result != M.end()) { 2060321369Sdim for (const typename Map::mapped_type::value_type Mapped : Result->second) 2061321369Sdim TouchedInstructions.set(InstrToDFSNum(Mapped)); 2062321369Sdim M.erase(Result); 2063321369Sdim } 2064311116Sdim} 2065311116Sdim 2066321369Sdimvoid NewGVN::addAdditionalUsers(Value *To, Value *User) const { 2067326909Sdim assert(User && To != User); 2068321369Sdim if (isa<Instruction>(To)) 2069321369Sdim AdditionalUsers[To].insert(User); 2070321369Sdim} 2071321369Sdim 2072311116Sdimvoid NewGVN::markUsersTouched(Value *V) { 2073311116Sdim // Now mark the users as touched. 2074311116Sdim for (auto *User : V->users()) { 2075311116Sdim assert(isa<Instruction>(User) && "Use of value not within an instruction?"); 2076321369Sdim TouchedInstructions.set(InstrToDFSNum(User)); 2077311116Sdim } 2078321369Sdim touchAndErase(AdditionalUsers, V); 2079311116Sdim} 2080311116Sdim 2081321369Sdimvoid NewGVN::addMemoryUsers(const MemoryAccess *To, MemoryAccess *U) const { 2082341825Sdim LLVM_DEBUG(dbgs() << "Adding memory user " << *U << " to " << *To << "\n"); 2083321369Sdim MemoryToUsers[To].insert(U); 2084311116Sdim} 2085311116Sdim 2086321369Sdimvoid NewGVN::markMemoryDefTouched(const MemoryAccess *MA) { 2087321369Sdim TouchedInstructions.set(MemoryToDFSNum(MA)); 2088321369Sdim} 2089321369Sdim 2090321369Sdimvoid NewGVN::markMemoryUsersTouched(const MemoryAccess *MA) { 2091321369Sdim if (isa<MemoryUse>(MA)) 2092321369Sdim return; 2093321369Sdim for (auto U : MA->users()) 2094321369Sdim TouchedInstructions.set(MemoryToDFSNum(U)); 2095321369Sdim touchAndErase(MemoryToUsers, MA); 2096321369Sdim} 2097321369Sdim 2098321369Sdim// Add I to the set of users of a given predicate. 2099321369Sdimvoid NewGVN::addPredicateUsers(const PredicateBase *PB, Instruction *I) const { 2100321369Sdim // Don't add temporary instructions to the user lists. 2101321369Sdim if (AllTempInstructions.count(I)) 2102321369Sdim return; 2103321369Sdim 2104321369Sdim if (auto *PBranch = dyn_cast<PredicateBranch>(PB)) 2105321369Sdim PredicateToUsers[PBranch->Condition].insert(I); 2106353358Sdim else if (auto *PAssume = dyn_cast<PredicateAssume>(PB)) 2107321369Sdim PredicateToUsers[PAssume->Condition].insert(I); 2108321369Sdim} 2109321369Sdim 2110321369Sdim// Touch all the predicates that depend on this instruction. 2111321369Sdimvoid NewGVN::markPredicateUsersTouched(Instruction *I) { 2112321369Sdim touchAndErase(PredicateToUsers, I); 2113321369Sdim} 2114321369Sdim 2115321369Sdim// Mark users affected by a memory leader change. 2116321369Sdimvoid NewGVN::markMemoryLeaderChangeTouched(CongruenceClass *CC) { 2117321369Sdim for (auto M : CC->memory()) 2118321369Sdim markMemoryDefTouched(M); 2119321369Sdim} 2120321369Sdim 2121311833Sdim// Touch the instructions that need to be updated after a congruence class has a 2122311833Sdim// leader change, and mark changed values. 2123321369Sdimvoid NewGVN::markValueLeaderChangeTouched(CongruenceClass *CC) { 2124321369Sdim for (auto M : *CC) { 2125311833Sdim if (auto *I = dyn_cast<Instruction>(M)) 2126321369Sdim TouchedInstructions.set(InstrToDFSNum(I)); 2127312197Sdim LeaderChanges.insert(M); 2128311833Sdim } 2129311833Sdim} 2130311833Sdim 2131321369Sdim// Give a range of things that have instruction DFS numbers, this will return 2132321369Sdim// the member of the range with the smallest dfs number. 2133321369Sdimtemplate <class T, class Range> 2134321369SdimT *NewGVN::getMinDFSOfRange(const Range &R) const { 2135321369Sdim std::pair<T *, unsigned> MinDFS = {nullptr, ~0U}; 2136321369Sdim for (const auto X : R) { 2137321369Sdim auto DFSNum = InstrToDFSNum(X); 2138321369Sdim if (DFSNum < MinDFS.second) 2139321369Sdim MinDFS = {X, DFSNum}; 2140321369Sdim } 2141321369Sdim return MinDFS.first; 2142321369Sdim} 2143312639Sdim 2144321369Sdim// This function returns the MemoryAccess that should be the next leader of 2145321369Sdim// congruence class CC, under the assumption that the current leader is going to 2146321369Sdim// disappear. 2147321369Sdimconst MemoryAccess *NewGVN::getNextMemoryLeader(CongruenceClass *CC) const { 2148321369Sdim // TODO: If this ends up to slow, we can maintain a next memory leader like we 2149321369Sdim // do for regular leaders. 2150327952Sdim // Make sure there will be a leader to find. 2151321369Sdim assert(!CC->definesNoMemory() && "Can't get next leader if there is none"); 2152321369Sdim if (CC->getStoreCount() > 0) { 2153321369Sdim if (auto *NL = dyn_cast_or_null<StoreInst>(CC->getNextLeader().first)) 2154321369Sdim return getMemoryAccess(NL); 2155321369Sdim // Find the store with the minimum DFS number. 2156321369Sdim auto *V = getMinDFSOfRange<Value>(make_filter_range( 2157321369Sdim *CC, [&](const Value *V) { return isa<StoreInst>(V); })); 2158321369Sdim return getMemoryAccess(cast<StoreInst>(V)); 2159321369Sdim } 2160321369Sdim assert(CC->getStoreCount() == 0); 2161312639Sdim 2162321369Sdim // Given our assertion, hitting this part must mean 2163321369Sdim // !OldClass->memory_empty() 2164321369Sdim if (CC->memory_size() == 1) 2165321369Sdim return *CC->memory_begin(); 2166321369Sdim return getMinDFSOfRange<const MemoryPhi>(CC->memory()); 2167321369Sdim} 2168321369Sdim 2169321369Sdim// This function returns the next value leader of a congruence class, under the 2170321369Sdim// assumption that the current leader is going away. This should end up being 2171321369Sdim// the next most dominating member. 2172321369SdimValue *NewGVN::getNextValueLeader(CongruenceClass *CC) const { 2173321369Sdim // We don't need to sort members if there is only 1, and we don't care about 2174321369Sdim // sorting the TOP class because everything either gets out of it or is 2175321369Sdim // unreachable. 2176321369Sdim 2177321369Sdim if (CC->size() == 1 || CC == TOPClass) { 2178321369Sdim return *(CC->begin()); 2179321369Sdim } else if (CC->getNextLeader().first) { 2180321369Sdim ++NumGVNAvoidedSortedLeaderChanges; 2181321369Sdim return CC->getNextLeader().first; 2182321369Sdim } else { 2183321369Sdim ++NumGVNSortedLeaderChanges; 2184321369Sdim // NOTE: If this ends up to slow, we can maintain a dual structure for 2185321369Sdim // member testing/insertion, or keep things mostly sorted, and sort only 2186321369Sdim // here, or use SparseBitVector or .... 2187321369Sdim return getMinDFSOfRange<Value>(*CC); 2188312719Sdim } 2189321369Sdim} 2190312639Sdim 2191321369Sdim// Move a MemoryAccess, currently in OldClass, to NewClass, including updates to 2192321369Sdim// the memory members, etc for the move. 2193321369Sdim// 2194321369Sdim// The invariants of this function are: 2195321369Sdim// 2196321369Sdim// - I must be moving to NewClass from OldClass 2197321369Sdim// - The StoreCount of OldClass and NewClass is expected to have been updated 2198341825Sdim// for I already if it is a store. 2199321369Sdim// - The OldClass memory leader has not been updated yet if I was the leader. 2200321369Sdimvoid NewGVN::moveMemoryToNewCongruenceClass(Instruction *I, 2201321369Sdim MemoryAccess *InstMA, 2202321369Sdim CongruenceClass *OldClass, 2203321369Sdim CongruenceClass *NewClass) { 2204341825Sdim // If the leader is I, and we had a representative MemoryAccess, it should 2205321369Sdim // be the MemoryAccess of OldClass. 2206321369Sdim assert((!InstMA || !OldClass->getMemoryLeader() || 2207321369Sdim OldClass->getLeader() != I || 2208321369Sdim MemoryAccessToClass.lookup(OldClass->getMemoryLeader()) == 2209321369Sdim MemoryAccessToClass.lookup(InstMA)) && 2210321369Sdim "Representative MemoryAccess mismatch"); 2211321369Sdim // First, see what happens to the new class 2212321369Sdim if (!NewClass->getMemoryLeader()) { 2213321369Sdim // Should be a new class, or a store becoming a leader of a new class. 2214321369Sdim assert(NewClass->size() == 1 || 2215321369Sdim (isa<StoreInst>(I) && NewClass->getStoreCount() == 1)); 2216321369Sdim NewClass->setMemoryLeader(InstMA); 2217321369Sdim // Mark it touched if we didn't just create a singleton 2218341825Sdim LLVM_DEBUG(dbgs() << "Memory class leader change for class " 2219341825Sdim << NewClass->getID() 2220341825Sdim << " due to new memory instruction becoming leader\n"); 2221321369Sdim markMemoryLeaderChangeTouched(NewClass); 2222312639Sdim } 2223321369Sdim setMemoryClass(InstMA, NewClass); 2224321369Sdim // Now, fixup the old class if necessary 2225321369Sdim if (OldClass->getMemoryLeader() == InstMA) { 2226321369Sdim if (!OldClass->definesNoMemory()) { 2227321369Sdim OldClass->setMemoryLeader(getNextMemoryLeader(OldClass)); 2228341825Sdim LLVM_DEBUG(dbgs() << "Memory class leader change for class " 2229341825Sdim << OldClass->getID() << " to " 2230341825Sdim << *OldClass->getMemoryLeader() 2231341825Sdim << " due to removal of old leader " << *InstMA << "\n"); 2232321369Sdim markMemoryLeaderChangeTouched(OldClass); 2233321369Sdim } else 2234321369Sdim OldClass->setMemoryLeader(nullptr); 2235321369Sdim } 2236321369Sdim} 2237312639Sdim 2238321369Sdim// Move a value, currently in OldClass, to be part of NewClass 2239321369Sdim// Update OldClass and NewClass for the move (including changing leaders, etc). 2240321369Sdimvoid NewGVN::moveValueToNewCongruenceClass(Instruction *I, const Expression *E, 2241321369Sdim CongruenceClass *OldClass, 2242321369Sdim CongruenceClass *NewClass) { 2243321369Sdim if (I == OldClass->getNextLeader().first) 2244321369Sdim OldClass->resetNextLeader(); 2245321369Sdim 2246321369Sdim OldClass->erase(I); 2247321369Sdim NewClass->insert(I); 2248321369Sdim 2249321369Sdim if (NewClass->getLeader() != I) 2250321369Sdim NewClass->addPossibleNextLeader({I, InstrToDFSNum(I)}); 2251321369Sdim // Handle our special casing of stores. 2252321369Sdim if (auto *SI = dyn_cast<StoreInst>(I)) { 2253321369Sdim OldClass->decStoreCount(); 2254321369Sdim // Okay, so when do we want to make a store a leader of a class? 2255321369Sdim // If we have a store defined by an earlier load, we want the earlier load 2256321369Sdim // to lead the class. 2257321369Sdim // If we have a store defined by something else, we want the store to lead 2258321369Sdim // the class so everything else gets the "something else" as a value. 2259321369Sdim // If we have a store as the single member of the class, we want the store 2260321369Sdim // as the leader 2261321369Sdim if (NewClass->getStoreCount() == 0 && !NewClass->getStoredValue()) { 2262321369Sdim // If it's a store expression we are using, it means we are not equivalent 2263321369Sdim // to something earlier. 2264321369Sdim if (auto *SE = dyn_cast<StoreExpression>(E)) { 2265321369Sdim NewClass->setStoredValue(SE->getStoredValue()); 2266321369Sdim markValueLeaderChangeTouched(NewClass); 2267321369Sdim // Shift the new class leader to be the store 2268341825Sdim LLVM_DEBUG(dbgs() << "Changing leader of congruence class " 2269341825Sdim << NewClass->getID() << " from " 2270341825Sdim << *NewClass->getLeader() << " to " << *SI 2271341825Sdim << " because store joined class\n"); 2272321369Sdim // If we changed the leader, we have to mark it changed because we don't 2273321369Sdim // know what it will do to symbolic evaluation. 2274321369Sdim NewClass->setLeader(SI); 2275321369Sdim } 2276321369Sdim // We rely on the code below handling the MemoryAccess change. 2277321369Sdim } 2278321369Sdim NewClass->incStoreCount(); 2279312197Sdim } 2280321369Sdim // True if there is no memory instructions left in a class that had memory 2281321369Sdim // instructions before. 2282312197Sdim 2283321369Sdim // If it's not a memory use, set the MemoryAccess equivalence 2284321369Sdim auto *InstMA = dyn_cast_or_null<MemoryDef>(getMemoryAccess(I)); 2285321369Sdim if (InstMA) 2286321369Sdim moveMemoryToNewCongruenceClass(I, InstMA, OldClass, NewClass); 2287312639Sdim ValueToClass[I] = NewClass; 2288312197Sdim // See if we destroyed the class or need to swap leaders. 2289321369Sdim if (OldClass->empty() && OldClass != TOPClass) { 2290321369Sdim if (OldClass->getDefiningExpr()) { 2291341825Sdim LLVM_DEBUG(dbgs() << "Erasing expression " << *OldClass->getDefiningExpr() 2292341825Sdim << " from table\n"); 2293321369Sdim // We erase it as an exact expression to make sure we don't just erase an 2294321369Sdim // equivalent one. 2295321369Sdim auto Iter = ExpressionToClass.find_as( 2296321369Sdim ExactEqualsExpression(*OldClass->getDefiningExpr())); 2297321369Sdim if (Iter != ExpressionToClass.end()) 2298321369Sdim ExpressionToClass.erase(Iter); 2299321369Sdim#ifdef EXPENSIVE_CHECKS 2300321369Sdim assert( 2301321369Sdim (*OldClass->getDefiningExpr() != *E || ExpressionToClass.lookup(E)) && 2302321369Sdim "We erased the expression we just inserted, which should not happen"); 2303321369Sdim#endif 2304312197Sdim } 2305321369Sdim } else if (OldClass->getLeader() == I) { 2306312197Sdim // When the leader changes, the value numbering of 2307312197Sdim // everything may change due to symbolization changes, so we need to 2308312197Sdim // reprocess. 2309341825Sdim LLVM_DEBUG(dbgs() << "Value class leader change for class " 2310341825Sdim << OldClass->getID() << "\n"); 2311312639Sdim ++NumGVNLeaderChanges; 2312321369Sdim // Destroy the stored value if there are no more stores to represent it. 2313321369Sdim // Note that this is basically clean up for the expression removal that 2314321369Sdim // happens below. If we remove stores from a class, we may leave it as a 2315321369Sdim // class of equivalent memory phis. 2316321369Sdim if (OldClass->getStoreCount() == 0) { 2317321369Sdim if (OldClass->getStoredValue()) 2318321369Sdim OldClass->setStoredValue(nullptr); 2319312639Sdim } 2320321369Sdim OldClass->setLeader(getNextValueLeader(OldClass)); 2321321369Sdim OldClass->resetNextLeader(); 2322321369Sdim markValueLeaderChangeTouched(OldClass); 2323312197Sdim } 2324312197Sdim} 2325312197Sdim 2326321369Sdim// For a given expression, mark the phi of ops instructions that could have 2327321369Sdim// changed as a result. 2328321369Sdimvoid NewGVN::markPhiOfOpsChanged(const Expression *E) { 2329327952Sdim touchAndErase(ExpressionToPhiOfOps, E); 2330321369Sdim} 2331321369Sdim 2332311116Sdim// Perform congruence finding on a given value numbering expression. 2333312639Sdimvoid NewGVN::performCongruenceFinding(Instruction *I, const Expression *E) { 2334311116Sdim // This is guaranteed to return something, since it will at least find 2335321369Sdim // TOP. 2336311833Sdim 2337321369Sdim CongruenceClass *IClass = ValueToClass.lookup(I); 2338312639Sdim assert(IClass && "Should have found a IClass"); 2339311116Sdim // Dead classes should have been eliminated from the mapping. 2340321369Sdim assert(!IClass->isDead() && "Found a dead class"); 2341311116Sdim 2342321369Sdim CongruenceClass *EClass = nullptr; 2343311116Sdim if (const auto *VE = dyn_cast<VariableExpression>(E)) { 2344321369Sdim EClass = ValueToClass.lookup(VE->getVariableValue()); 2345321369Sdim } else if (isa<DeadExpression>(E)) { 2346321369Sdim EClass = TOPClass; 2347321369Sdim } 2348321369Sdim if (!EClass) { 2349311116Sdim auto lookupResult = ExpressionToClass.insert({E, nullptr}); 2350311116Sdim 2351311116Sdim // If it's not in the value table, create a new congruence class. 2352311116Sdim if (lookupResult.second) { 2353311116Sdim CongruenceClass *NewClass = createCongruenceClass(nullptr, E); 2354311116Sdim auto place = lookupResult.first; 2355311116Sdim place->second = NewClass; 2356311116Sdim 2357311116Sdim // Constants and variables should always be made the leader. 2358311833Sdim if (const auto *CE = dyn_cast<ConstantExpression>(E)) { 2359321369Sdim NewClass->setLeader(CE->getConstantValue()); 2360311833Sdim } else if (const auto *SE = dyn_cast<StoreExpression>(E)) { 2361311833Sdim StoreInst *SI = SE->getStoreInst(); 2362321369Sdim NewClass->setLeader(SI); 2363321369Sdim NewClass->setStoredValue(SE->getStoredValue()); 2364321369Sdim // The RepMemoryAccess field will be filled in properly by the 2365321369Sdim // moveValueToNewCongruenceClass call. 2366311833Sdim } else { 2367321369Sdim NewClass->setLeader(I); 2368311833Sdim } 2369311833Sdim assert(!isa<VariableExpression>(E) && 2370311833Sdim "VariableExpression should have been handled already"); 2371311116Sdim 2372311116Sdim EClass = NewClass; 2373341825Sdim LLVM_DEBUG(dbgs() << "Created new congruence class for " << *I 2374341825Sdim << " using expression " << *E << " at " 2375341825Sdim << NewClass->getID() << " and leader " 2376341825Sdim << *(NewClass->getLeader())); 2377321369Sdim if (NewClass->getStoredValue()) 2378341825Sdim LLVM_DEBUG(dbgs() << " and stored value " 2379341825Sdim << *(NewClass->getStoredValue())); 2380341825Sdim LLVM_DEBUG(dbgs() << "\n"); 2381311116Sdim } else { 2382311116Sdim EClass = lookupResult.first->second; 2383311116Sdim if (isa<ConstantExpression>(E)) 2384321369Sdim assert((isa<Constant>(EClass->getLeader()) || 2385321369Sdim (EClass->getStoredValue() && 2386321369Sdim isa<Constant>(EClass->getStoredValue()))) && 2387311116Sdim "Any class with a constant expression should have a " 2388311116Sdim "constant leader"); 2389311116Sdim 2390311116Sdim assert(EClass && "Somehow don't have an eclass"); 2391311116Sdim 2392321369Sdim assert(!EClass->isDead() && "We accidentally looked up a dead class"); 2393311116Sdim } 2394311116Sdim } 2395312639Sdim bool ClassChanged = IClass != EClass; 2396312639Sdim bool LeaderChanged = LeaderChanges.erase(I); 2397312197Sdim if (ClassChanged || LeaderChanged) { 2398341825Sdim LLVM_DEBUG(dbgs() << "New class " << EClass->getID() << " for expression " 2399341825Sdim << *E << "\n"); 2400321369Sdim if (ClassChanged) { 2401321369Sdim moveValueToNewCongruenceClass(I, E, IClass, EClass); 2402321369Sdim markPhiOfOpsChanged(E); 2403321369Sdim } 2404311116Sdim 2405312639Sdim markUsersTouched(I); 2406321369Sdim if (MemoryAccess *MA = getMemoryAccess(I)) 2407312639Sdim markMemoryUsersTouched(MA); 2408321369Sdim if (auto *CI = dyn_cast<CmpInst>(I)) 2409321369Sdim markPredicateUsersTouched(CI); 2410321369Sdim } 2411321369Sdim // If we changed the class of the store, we want to ensure nothing finds the 2412321369Sdim // old store expression. In particular, loads do not compare against stored 2413321369Sdim // value, so they will find old store expressions (and associated class 2414321369Sdim // mappings) if we leave them in the table. 2415321369Sdim if (ClassChanged && isa<StoreInst>(I)) { 2416321369Sdim auto *OldE = ValueToExpression.lookup(I); 2417321369Sdim // It could just be that the old class died. We don't want to erase it if we 2418321369Sdim // just moved classes. 2419321369Sdim if (OldE && isa<StoreExpression>(OldE) && *E != *OldE) { 2420321369Sdim // Erase this as an exact expression to ensure we don't erase expressions 2421321369Sdim // equivalent to it. 2422321369Sdim auto Iter = ExpressionToClass.find_as(ExactEqualsExpression(*OldE)); 2423321369Sdim if (Iter != ExpressionToClass.end()) 2424321369Sdim ExpressionToClass.erase(Iter); 2425311116Sdim } 2426311116Sdim } 2427321369Sdim ValueToExpression[I] = E; 2428311116Sdim} 2429311116Sdim 2430311116Sdim// Process the fact that Edge (from, to) is reachable, including marking 2431311116Sdim// any newly reachable blocks and instructions for processing. 2432311116Sdimvoid NewGVN::updateReachableEdge(BasicBlock *From, BasicBlock *To) { 2433311116Sdim // Check if the Edge was reachable before. 2434311116Sdim if (ReachableEdges.insert({From, To}).second) { 2435311116Sdim // If this block wasn't reachable before, all instructions are touched. 2436311116Sdim if (ReachableBlocks.insert(To).second) { 2437341825Sdim LLVM_DEBUG(dbgs() << "Block " << getBlockName(To) 2438341825Sdim << " marked reachable\n"); 2439311116Sdim const auto &InstRange = BlockInstRange.lookup(To); 2440311116Sdim TouchedInstructions.set(InstRange.first, InstRange.second); 2441311116Sdim } else { 2442341825Sdim LLVM_DEBUG(dbgs() << "Block " << getBlockName(To) 2443341825Sdim << " was reachable, but new edge {" 2444341825Sdim << getBlockName(From) << "," << getBlockName(To) 2445341825Sdim << "} to it found\n"); 2446311116Sdim 2447311116Sdim // We've made an edge reachable to an existing block, which may 2448311116Sdim // impact predicates. Otherwise, only mark the phi nodes as touched, as 2449311116Sdim // they are the only thing that depend on new edges. Anything using their 2450311116Sdim // values will get propagated to if necessary. 2451321369Sdim if (MemoryAccess *MemPhi = getMemoryAccess(To)) 2452321369Sdim TouchedInstructions.set(InstrToDFSNum(MemPhi)); 2453311116Sdim 2454327952Sdim // FIXME: We should just add a union op on a Bitvector and 2455327952Sdim // SparseBitVector. We can do it word by word faster than we are doing it 2456327952Sdim // here. 2457327952Sdim for (auto InstNum : RevisitOnReachabilityChange[To]) 2458327952Sdim TouchedInstructions.set(InstNum); 2459311116Sdim } 2460311116Sdim } 2461311116Sdim} 2462311116Sdim 2463311116Sdim// Given a predicate condition (from a switch, cmp, or whatever) and a block, 2464311116Sdim// see if we know some constant value for it already. 2465321369SdimValue *NewGVN::findConditionEquivalence(Value *Cond) const { 2466321369Sdim auto Result = lookupOperandLeader(Cond); 2467321369Sdim return isa<Constant>(Result) ? Result : nullptr; 2468311116Sdim} 2469311116Sdim 2470311116Sdim// Process the outgoing edges of a block for reachability. 2471344779Sdimvoid NewGVN::processOutgoingEdges(Instruction *TI, BasicBlock *B) { 2472311116Sdim // Evaluate reachability of terminator instruction. 2473360784Sdim Value *Cond; 2474360784Sdim BasicBlock *TrueSucc, *FalseSucc; 2475360784Sdim if (match(TI, m_Br(m_Value(Cond), TrueSucc, FalseSucc))) { 2476321369Sdim Value *CondEvaluated = findConditionEquivalence(Cond); 2477311116Sdim if (!CondEvaluated) { 2478311116Sdim if (auto *I = dyn_cast<Instruction>(Cond)) { 2479321369Sdim const Expression *E = createExpression(I); 2480311116Sdim if (const auto *CE = dyn_cast<ConstantExpression>(E)) { 2481311116Sdim CondEvaluated = CE->getConstantValue(); 2482311116Sdim } 2483311116Sdim } else if (isa<ConstantInt>(Cond)) { 2484311116Sdim CondEvaluated = Cond; 2485311116Sdim } 2486311116Sdim } 2487311116Sdim ConstantInt *CI; 2488311116Sdim if (CondEvaluated && (CI = dyn_cast<ConstantInt>(CondEvaluated))) { 2489311116Sdim if (CI->isOne()) { 2490341825Sdim LLVM_DEBUG(dbgs() << "Condition for Terminator " << *TI 2491341825Sdim << " evaluated to true\n"); 2492311116Sdim updateReachableEdge(B, TrueSucc); 2493311116Sdim } else if (CI->isZero()) { 2494341825Sdim LLVM_DEBUG(dbgs() << "Condition for Terminator " << *TI 2495341825Sdim << " evaluated to false\n"); 2496311116Sdim updateReachableEdge(B, FalseSucc); 2497311116Sdim } 2498311116Sdim } else { 2499311116Sdim updateReachableEdge(B, TrueSucc); 2500311116Sdim updateReachableEdge(B, FalseSucc); 2501311116Sdim } 2502311116Sdim } else if (auto *SI = dyn_cast<SwitchInst>(TI)) { 2503311116Sdim // For switches, propagate the case values into the case 2504311116Sdim // destinations. 2505311116Sdim 2506311116Sdim Value *SwitchCond = SI->getCondition(); 2507321369Sdim Value *CondEvaluated = findConditionEquivalence(SwitchCond); 2508311116Sdim // See if we were able to turn this switch statement into a constant. 2509311116Sdim if (CondEvaluated && isa<ConstantInt>(CondEvaluated)) { 2510311116Sdim auto *CondVal = cast<ConstantInt>(CondEvaluated); 2511311116Sdim // We should be able to get case value for this. 2512321369Sdim auto Case = *SI->findCaseValue(CondVal); 2513321369Sdim if (Case.getCaseSuccessor() == SI->getDefaultDest()) { 2514311116Sdim // We proved the value is outside of the range of the case. 2515311116Sdim // We can't do anything other than mark the default dest as reachable, 2516311116Sdim // and go home. 2517311116Sdim updateReachableEdge(B, SI->getDefaultDest()); 2518311116Sdim return; 2519311116Sdim } 2520311116Sdim // Now get where it goes and mark it reachable. 2521321369Sdim BasicBlock *TargetBlock = Case.getCaseSuccessor(); 2522311116Sdim updateReachableEdge(B, TargetBlock); 2523311116Sdim } else { 2524311116Sdim for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) { 2525311116Sdim BasicBlock *TargetBlock = SI->getSuccessor(i); 2526311116Sdim updateReachableEdge(B, TargetBlock); 2527311116Sdim } 2528311116Sdim } 2529311116Sdim } else { 2530311116Sdim // Otherwise this is either unconditional, or a type we have no 2531311116Sdim // idea about. Just mark successors as reachable. 2532311116Sdim for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { 2533311116Sdim BasicBlock *TargetBlock = TI->getSuccessor(i); 2534311116Sdim updateReachableEdge(B, TargetBlock); 2535311116Sdim } 2536311116Sdim 2537311116Sdim // This also may be a memory defining terminator, in which case, set it 2538321369Sdim // equivalent only to itself. 2539321369Sdim // 2540321369Sdim auto *MA = getMemoryAccess(TI); 2541321369Sdim if (MA && !isa<MemoryUse>(MA)) { 2542321369Sdim auto *CC = ensureLeaderOfMemoryClass(MA); 2543321369Sdim if (setMemoryClass(MA, CC)) 2544321369Sdim markMemoryUsersTouched(MA); 2545321369Sdim } 2546311116Sdim } 2547311116Sdim} 2548311116Sdim 2549327952Sdim// Remove the PHI of Ops PHI for I 2550327952Sdimvoid NewGVN::removePhiOfOps(Instruction *I, PHINode *PHITemp) { 2551327952Sdim InstrDFS.erase(PHITemp); 2552327952Sdim // It's still a temp instruction. We keep it in the array so it gets erased. 2553327952Sdim // However, it's no longer used by I, or in the block 2554327952Sdim TempToBlock.erase(PHITemp); 2555327952Sdim RealToTemp.erase(I); 2556327952Sdim // We don't remove the users from the phi node uses. This wastes a little 2557327952Sdim // time, but such is life. We could use two sets to track which were there 2558327952Sdim // are the start of NewGVN, and which were added, but right nowt he cost of 2559327952Sdim // tracking is more than the cost of checking for more phi of ops. 2560327952Sdim} 2561327952Sdim 2562327952Sdim// Add PHI Op in BB as a PHI of operations version of ExistingValue. 2563321369Sdimvoid NewGVN::addPhiOfOps(PHINode *Op, BasicBlock *BB, 2564321369Sdim Instruction *ExistingValue) { 2565321369Sdim InstrDFS[Op] = InstrToDFSNum(ExistingValue); 2566321369Sdim AllTempInstructions.insert(Op); 2567321369Sdim TempToBlock[Op] = BB; 2568321369Sdim RealToTemp[ExistingValue] = Op; 2569327952Sdim // Add all users to phi node use, as they are now uses of the phi of ops phis 2570327952Sdim // and may themselves be phi of ops. 2571327952Sdim for (auto *U : ExistingValue->users()) 2572327952Sdim if (auto *UI = dyn_cast<Instruction>(U)) 2573327952Sdim PHINodeUses.insert(UI); 2574321369Sdim} 2575321369Sdim 2576321369Sdimstatic bool okayForPHIOfOps(const Instruction *I) { 2577327952Sdim if (!EnablePhiOfOps) 2578327952Sdim return false; 2579321369Sdim return isa<BinaryOperator>(I) || isa<SelectInst>(I) || isa<CmpInst>(I) || 2580321369Sdim isa<LoadInst>(I); 2581321369Sdim} 2582321369Sdim 2583327952Sdimbool NewGVN::OpIsSafeForPHIOfOpsHelper( 2584327952Sdim Value *V, const BasicBlock *PHIBlock, 2585327952Sdim SmallPtrSetImpl<const Value *> &Visited, 2586327952Sdim SmallVectorImpl<Instruction *> &Worklist) { 2587327952Sdim 2588327952Sdim if (!isa<Instruction>(V)) 2589327952Sdim return true; 2590327952Sdim auto OISIt = OpSafeForPHIOfOps.find(V); 2591327952Sdim if (OISIt != OpSafeForPHIOfOps.end()) 2592327952Sdim return OISIt->second; 2593327952Sdim 2594327952Sdim // Keep walking until we either dominate the phi block, or hit a phi, or run 2595327952Sdim // out of things to check. 2596327952Sdim if (DT->properlyDominates(getBlockForValue(V), PHIBlock)) { 2597327952Sdim OpSafeForPHIOfOps.insert({V, true}); 2598327952Sdim return true; 2599327952Sdim } 2600327952Sdim // PHI in the same block. 2601327952Sdim if (isa<PHINode>(V) && getBlockForValue(V) == PHIBlock) { 2602327952Sdim OpSafeForPHIOfOps.insert({V, false}); 2603327952Sdim return false; 2604327952Sdim } 2605327952Sdim 2606327952Sdim auto *OrigI = cast<Instruction>(V); 2607327952Sdim for (auto *Op : OrigI->operand_values()) { 2608327952Sdim if (!isa<Instruction>(Op)) 2609327952Sdim continue; 2610327952Sdim // Stop now if we find an unsafe operand. 2611327952Sdim auto OISIt = OpSafeForPHIOfOps.find(OrigI); 2612327952Sdim if (OISIt != OpSafeForPHIOfOps.end()) { 2613327952Sdim if (!OISIt->second) { 2614327952Sdim OpSafeForPHIOfOps.insert({V, false}); 2615327952Sdim return false; 2616327952Sdim } 2617327952Sdim continue; 2618327952Sdim } 2619327952Sdim if (!Visited.insert(Op).second) 2620327952Sdim continue; 2621327952Sdim Worklist.push_back(cast<Instruction>(Op)); 2622327952Sdim } 2623327952Sdim return true; 2624327952Sdim} 2625327952Sdim 2626327952Sdim// Return true if this operand will be safe to use for phi of ops. 2627327952Sdim// 2628327952Sdim// The reason some operands are unsafe is that we are not trying to recursively 2629327952Sdim// translate everything back through phi nodes. We actually expect some lookups 2630327952Sdim// of expressions to fail. In particular, a lookup where the expression cannot 2631327952Sdim// exist in the predecessor. This is true even if the expression, as shown, can 2632327952Sdim// be determined to be constant. 2633327952Sdimbool NewGVN::OpIsSafeForPHIOfOps(Value *V, const BasicBlock *PHIBlock, 2634327952Sdim SmallPtrSetImpl<const Value *> &Visited) { 2635327952Sdim SmallVector<Instruction *, 4> Worklist; 2636327952Sdim if (!OpIsSafeForPHIOfOpsHelper(V, PHIBlock, Visited, Worklist)) 2637327952Sdim return false; 2638327952Sdim while (!Worklist.empty()) { 2639327952Sdim auto *I = Worklist.pop_back_val(); 2640327952Sdim if (!OpIsSafeForPHIOfOpsHelper(I, PHIBlock, Visited, Worklist)) 2641327952Sdim return false; 2642327952Sdim } 2643327952Sdim OpSafeForPHIOfOps.insert({V, true}); 2644327952Sdim return true; 2645327952Sdim} 2646327952Sdim 2647327952Sdim// Try to find a leader for instruction TransInst, which is a phi translated 2648327952Sdim// version of something in our original program. Visited is used to ensure we 2649327952Sdim// don't infinite loop during translations of cycles. OrigInst is the 2650327952Sdim// instruction in the original program, and PredBB is the predecessor we 2651327952Sdim// translated it through. 2652327952SdimValue *NewGVN::findLeaderForInst(Instruction *TransInst, 2653327952Sdim SmallPtrSetImpl<Value *> &Visited, 2654327952Sdim MemoryAccess *MemAccess, Instruction *OrigInst, 2655327952Sdim BasicBlock *PredBB) { 2656327952Sdim unsigned IDFSNum = InstrToDFSNum(OrigInst); 2657327952Sdim // Make sure it's marked as a temporary instruction. 2658327952Sdim AllTempInstructions.insert(TransInst); 2659327952Sdim // and make sure anything that tries to add it's DFS number is 2660327952Sdim // redirected to the instruction we are making a phi of ops 2661327952Sdim // for. 2662327952Sdim TempToBlock.insert({TransInst, PredBB}); 2663327952Sdim InstrDFS.insert({TransInst, IDFSNum}); 2664327952Sdim 2665327952Sdim const Expression *E = performSymbolicEvaluation(TransInst, Visited); 2666327952Sdim InstrDFS.erase(TransInst); 2667327952Sdim AllTempInstructions.erase(TransInst); 2668327952Sdim TempToBlock.erase(TransInst); 2669327952Sdim if (MemAccess) 2670327952Sdim TempToMemory.erase(TransInst); 2671327952Sdim if (!E) 2672327952Sdim return nullptr; 2673327952Sdim auto *FoundVal = findPHIOfOpsLeader(E, OrigInst, PredBB); 2674327952Sdim if (!FoundVal) { 2675327952Sdim ExpressionToPhiOfOps[E].insert(OrigInst); 2676341825Sdim LLVM_DEBUG(dbgs() << "Cannot find phi of ops operand for " << *TransInst 2677341825Sdim << " in block " << getBlockName(PredBB) << "\n"); 2678327952Sdim return nullptr; 2679327952Sdim } 2680327952Sdim if (auto *SI = dyn_cast<StoreInst>(FoundVal)) 2681327952Sdim FoundVal = SI->getValueOperand(); 2682327952Sdim return FoundVal; 2683327952Sdim} 2684327952Sdim 2685321369Sdim// When we see an instruction that is an op of phis, generate the equivalent phi 2686321369Sdim// of ops form. 2687321369Sdimconst Expression * 2688327952SdimNewGVN::makePossiblePHIOfOps(Instruction *I, 2689321369Sdim SmallPtrSetImpl<Value *> &Visited) { 2690321369Sdim if (!okayForPHIOfOps(I)) 2691321369Sdim return nullptr; 2692321369Sdim 2693321369Sdim if (!Visited.insert(I).second) 2694321369Sdim return nullptr; 2695321369Sdim // For now, we require the instruction be cycle free because we don't 2696321369Sdim // *always* create a phi of ops for instructions that could be done as phi 2697321369Sdim // of ops, we only do it if we think it is useful. If we did do it all the 2698321369Sdim // time, we could remove the cycle free check. 2699321369Sdim if (!isCycleFree(I)) 2700321369Sdim return nullptr; 2701321369Sdim 2702321369Sdim SmallPtrSet<const Value *, 8> ProcessedPHIs; 2703321369Sdim // TODO: We don't do phi translation on memory accesses because it's 2704321369Sdim // complicated. For a load, we'd need to be able to simulate a new memoryuse, 2705321369Sdim // which we don't have a good way of doing ATM. 2706321369Sdim auto *MemAccess = getMemoryAccess(I); 2707321369Sdim // If the memory operation is defined by a memory operation this block that 2708321369Sdim // isn't a MemoryPhi, transforming the pointer backwards through a scalar phi 2709321369Sdim // can't help, as it would still be killed by that memory operation. 2710321369Sdim if (MemAccess && !isa<MemoryPhi>(MemAccess->getDefiningAccess()) && 2711321369Sdim MemAccess->getDefiningAccess()->getBlock() == I->getParent()) 2712321369Sdim return nullptr; 2713321369Sdim 2714341825Sdim // Convert op of phis to phi of ops 2715327952Sdim SmallPtrSet<const Value *, 10> VisitedOps; 2716341825Sdim SmallVector<Value *, 4> Ops(I->operand_values()); 2717341825Sdim BasicBlock *SamePHIBlock = nullptr; 2718341825Sdim PHINode *OpPHI = nullptr; 2719341825Sdim if (!DebugCounter::shouldExecute(PHIOfOpsCounter)) 2720341825Sdim return nullptr; 2721341825Sdim for (auto *Op : Ops) { 2722327952Sdim if (!isa<PHINode>(Op)) { 2723327952Sdim auto *ValuePHI = RealToTemp.lookup(Op); 2724327952Sdim if (!ValuePHI) 2725327952Sdim continue; 2726341825Sdim LLVM_DEBUG(dbgs() << "Found possible dependent phi of ops\n"); 2727327952Sdim Op = ValuePHI; 2728327952Sdim } 2729341825Sdim OpPHI = cast<PHINode>(Op); 2730341825Sdim if (!SamePHIBlock) { 2731341825Sdim SamePHIBlock = getBlockForValue(OpPHI); 2732341825Sdim } else if (SamePHIBlock != getBlockForValue(OpPHI)) { 2733341825Sdim LLVM_DEBUG( 2734341825Sdim dbgs() 2735341825Sdim << "PHIs for operands are not all in the same block, aborting\n"); 2736341825Sdim return nullptr; 2737341825Sdim } 2738321369Sdim // No point in doing this for one-operand phis. 2739341825Sdim if (OpPHI->getNumOperands() == 1) { 2740341825Sdim OpPHI = nullptr; 2741321369Sdim continue; 2742341825Sdim } 2743341825Sdim } 2744341825Sdim 2745341825Sdim if (!OpPHI) 2746341825Sdim return nullptr; 2747341825Sdim 2748341825Sdim SmallVector<ValPair, 4> PHIOps; 2749341825Sdim SmallPtrSet<Value *, 4> Deps; 2750341825Sdim auto *PHIBlock = getBlockForValue(OpPHI); 2751341825Sdim RevisitOnReachabilityChange[PHIBlock].reset(InstrToDFSNum(I)); 2752341825Sdim for (unsigned PredNum = 0; PredNum < OpPHI->getNumOperands(); ++PredNum) { 2753341825Sdim auto *PredBB = OpPHI->getIncomingBlock(PredNum); 2754341825Sdim Value *FoundVal = nullptr; 2755341825Sdim SmallPtrSet<Value *, 4> CurrentDeps; 2756341825Sdim // We could just skip unreachable edges entirely but it's tricky to do 2757341825Sdim // with rewriting existing phi nodes. 2758341825Sdim if (ReachableEdges.count({PredBB, PHIBlock})) { 2759341825Sdim // Clone the instruction, create an expression from it that is 2760341825Sdim // translated back into the predecessor, and see if we have a leader. 2761341825Sdim Instruction *ValueOp = I->clone(); 2762341825Sdim if (MemAccess) 2763341825Sdim TempToMemory.insert({ValueOp, MemAccess}); 2764341825Sdim bool SafeForPHIOfOps = true; 2765341825Sdim VisitedOps.clear(); 2766341825Sdim for (auto &Op : ValueOp->operands()) { 2767341825Sdim auto *OrigOp = &*Op; 2768341825Sdim // When these operand changes, it could change whether there is a 2769341825Sdim // leader for us or not, so we have to add additional users. 2770341825Sdim if (isa<PHINode>(Op)) { 2771341825Sdim Op = Op->DoPHITranslation(PHIBlock, PredBB); 2772341825Sdim if (Op != OrigOp && Op != I) 2773341825Sdim CurrentDeps.insert(Op); 2774341825Sdim } else if (auto *ValuePHI = RealToTemp.lookup(Op)) { 2775341825Sdim if (getBlockForValue(ValuePHI) == PHIBlock) 2776341825Sdim Op = ValuePHI->getIncomingValueForBlock(PredBB); 2777321369Sdim } 2778341825Sdim // If we phi-translated the op, it must be safe. 2779341825Sdim SafeForPHIOfOps = 2780341825Sdim SafeForPHIOfOps && 2781341825Sdim (Op != OrigOp || OpIsSafeForPHIOfOps(Op, PHIBlock, VisitedOps)); 2782321369Sdim } 2783341825Sdim // FIXME: For those things that are not safe we could generate 2784341825Sdim // expressions all the way down, and see if this comes out to a 2785341825Sdim // constant. For anything where that is true, and unsafe, we should 2786341825Sdim // have made a phi-of-ops (or value numbered it equivalent to something) 2787341825Sdim // for the pieces already. 2788341825Sdim FoundVal = !SafeForPHIOfOps ? nullptr 2789341825Sdim : findLeaderForInst(ValueOp, Visited, 2790341825Sdim MemAccess, I, PredBB); 2791341825Sdim ValueOp->deleteValue(); 2792341825Sdim if (!FoundVal) { 2793341825Sdim // We failed to find a leader for the current ValueOp, but this might 2794341825Sdim // change in case of the translated operands change. 2795341825Sdim if (SafeForPHIOfOps) 2796341825Sdim for (auto Dep : CurrentDeps) 2797341825Sdim addAdditionalUsers(Dep, I); 2798321369Sdim 2799341825Sdim return nullptr; 2800341825Sdim } 2801341825Sdim Deps.insert(CurrentDeps.begin(), CurrentDeps.end()); 2802321369Sdim } else { 2803341825Sdim LLVM_DEBUG(dbgs() << "Skipping phi of ops operand for incoming block " 2804341825Sdim << getBlockName(PredBB) 2805341825Sdim << " because the block is unreachable\n"); 2806341825Sdim FoundVal = UndefValue::get(I->getType()); 2807341825Sdim RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(I)); 2808321369Sdim } 2809327952Sdim 2810341825Sdim PHIOps.push_back({FoundVal, PredBB}); 2811341825Sdim LLVM_DEBUG(dbgs() << "Found phi of ops operand " << *FoundVal << " in " 2812341825Sdim << getBlockName(PredBB) << "\n"); 2813341825Sdim } 2814341825Sdim for (auto Dep : Deps) 2815341825Sdim addAdditionalUsers(Dep, I); 2816341825Sdim sortPHIOps(PHIOps); 2817341825Sdim auto *E = performSymbolicPHIEvaluation(PHIOps, I, PHIBlock); 2818341825Sdim if (isa<ConstantExpression>(E) || isa<VariableExpression>(E)) { 2819341825Sdim LLVM_DEBUG( 2820341825Sdim dbgs() 2821341825Sdim << "Not creating real PHI of ops because it simplified to existing " 2822341825Sdim "value or constant\n"); 2823327952Sdim return E; 2824321369Sdim } 2825341825Sdim auto *ValuePHI = RealToTemp.lookup(I); 2826341825Sdim bool NewPHI = false; 2827341825Sdim if (!ValuePHI) { 2828341825Sdim ValuePHI = 2829341825Sdim PHINode::Create(I->getType(), OpPHI->getNumOperands(), "phiofops"); 2830341825Sdim addPhiOfOps(ValuePHI, PHIBlock, I); 2831341825Sdim NewPHI = true; 2832341825Sdim NumGVNPHIOfOpsCreated++; 2833341825Sdim } 2834341825Sdim if (NewPHI) { 2835341825Sdim for (auto PHIOp : PHIOps) 2836341825Sdim ValuePHI->addIncoming(PHIOp.first, PHIOp.second); 2837341825Sdim } else { 2838341825Sdim TempToBlock[ValuePHI] = PHIBlock; 2839341825Sdim unsigned int i = 0; 2840341825Sdim for (auto PHIOp : PHIOps) { 2841341825Sdim ValuePHI->setIncomingValue(i, PHIOp.first); 2842341825Sdim ValuePHI->setIncomingBlock(i, PHIOp.second); 2843341825Sdim ++i; 2844341825Sdim } 2845341825Sdim } 2846341825Sdim RevisitOnReachabilityChange[PHIBlock].set(InstrToDFSNum(I)); 2847341825Sdim LLVM_DEBUG(dbgs() << "Created phi of ops " << *ValuePHI << " for " << *I 2848341825Sdim << "\n"); 2849341825Sdim 2850341825Sdim return E; 2851321369Sdim} 2852321369Sdim 2853321369Sdim// The algorithm initially places the values of the routine in the TOP 2854321369Sdim// congruence class. The leader of TOP is the undetermined value `undef`. 2855321369Sdim// When the algorithm has finished, values still in TOP are unreachable. 2856311116Sdimvoid NewGVN::initializeCongruenceClasses(Function &F) { 2857321369Sdim NextCongruenceNum = 0; 2858311116Sdim 2859321369Sdim // Note that even though we use the live on entry def as a representative 2860321369Sdim // MemoryAccess, it is *not* the same as the actual live on entry def. We 2861321369Sdim // have no real equivalemnt to undef for MemoryAccesses, and so we really 2862321369Sdim // should be checking whether the MemoryAccess is top if we want to know if it 2863321369Sdim // is equivalent to everything. Otherwise, what this really signifies is that 2864321369Sdim // the access "it reaches all the way back to the beginning of the function" 2865321369Sdim 2866321369Sdim // Initialize all other instructions to be in TOP class. 2867321369Sdim TOPClass = createCongruenceClass(nullptr, nullptr); 2868321369Sdim TOPClass->setMemoryLeader(MSSA->getLiveOnEntryDef()); 2869321369Sdim // The live on entry def gets put into it's own class 2870321369Sdim MemoryAccessToClass[MSSA->getLiveOnEntryDef()] = 2871321369Sdim createMemoryClass(MSSA->getLiveOnEntryDef()); 2872321369Sdim 2873321369Sdim for (auto DTN : nodes(DT)) { 2874321369Sdim BasicBlock *BB = DTN->getBlock(); 2875321369Sdim // All MemoryAccesses are equivalent to live on entry to start. They must 2876321369Sdim // be initialized to something so that initial changes are noticed. For 2877321369Sdim // the maximal answer, we initialize them all to be the same as 2878321369Sdim // liveOnEntry. 2879321369Sdim auto *MemoryBlockDefs = MSSA->getBlockDefs(BB); 2880321369Sdim if (MemoryBlockDefs) 2881321369Sdim for (const auto &Def : *MemoryBlockDefs) { 2882321369Sdim MemoryAccessToClass[&Def] = TOPClass; 2883321369Sdim auto *MD = dyn_cast<MemoryDef>(&Def); 2884321369Sdim // Insert the memory phis into the member list. 2885321369Sdim if (!MD) { 2886321369Sdim const MemoryPhi *MP = cast<MemoryPhi>(&Def); 2887321369Sdim TOPClass->memory_insert(MP); 2888321369Sdim MemoryPhiState.insert({MP, MPS_TOP}); 2889321369Sdim } 2890321369Sdim 2891321369Sdim if (MD && isa<StoreInst>(MD->getMemoryInst())) 2892321369Sdim TOPClass->incStoreCount(); 2893312197Sdim } 2894327952Sdim 2895327952Sdim // FIXME: This is trying to discover which instructions are uses of phi 2896327952Sdim // nodes. We should move this into one of the myriad of places that walk 2897327952Sdim // all the operands already. 2898321369Sdim for (auto &I : *BB) { 2899321369Sdim if (isa<PHINode>(&I)) 2900321369Sdim for (auto *U : I.users()) 2901321369Sdim if (auto *UInst = dyn_cast<Instruction>(U)) 2902321369Sdim if (InstrToDFSNum(UInst) != 0 && okayForPHIOfOps(UInst)) 2903321369Sdim PHINodeUses.insert(UInst); 2904321369Sdim // Don't insert void terminators into the class. We don't value number 2905321369Sdim // them, and they just end up sitting in TOP. 2906344779Sdim if (I.isTerminator() && I.getType()->isVoidTy()) 2907321369Sdim continue; 2908321369Sdim TOPClass->insert(&I); 2909321369Sdim ValueToClass[&I] = TOPClass; 2910311116Sdim } 2911311116Sdim } 2912311116Sdim 2913311116Sdim // Initialize arguments to be in their own unique congruence classes 2914311116Sdim for (auto &FA : F.args()) 2915311116Sdim createSingletonCongruenceClass(&FA); 2916311116Sdim} 2917311116Sdim 2918311116Sdimvoid NewGVN::cleanupTables() { 2919311116Sdim for (unsigned i = 0, e = CongruenceClasses.size(); i != e; ++i) { 2920341825Sdim LLVM_DEBUG(dbgs() << "Congruence class " << CongruenceClasses[i]->getID() 2921341825Sdim << " has " << CongruenceClasses[i]->size() 2922341825Sdim << " members\n"); 2923311116Sdim // Make sure we delete the congruence class (probably worth switching to 2924311116Sdim // a unique_ptr at some point. 2925311116Sdim delete CongruenceClasses[i]; 2926311116Sdim CongruenceClasses[i] = nullptr; 2927311116Sdim } 2928311116Sdim 2929321369Sdim // Destroy the value expressions 2930321369Sdim SmallVector<Instruction *, 8> TempInst(AllTempInstructions.begin(), 2931321369Sdim AllTempInstructions.end()); 2932321369Sdim AllTempInstructions.clear(); 2933321369Sdim 2934321369Sdim // We have to drop all references for everything first, so there are no uses 2935321369Sdim // left as we delete them. 2936321369Sdim for (auto *I : TempInst) { 2937321369Sdim I->dropAllReferences(); 2938321369Sdim } 2939321369Sdim 2940321369Sdim while (!TempInst.empty()) { 2941321369Sdim auto *I = TempInst.back(); 2942321369Sdim TempInst.pop_back(); 2943321369Sdim I->deleteValue(); 2944321369Sdim } 2945321369Sdim 2946311116Sdim ValueToClass.clear(); 2947311116Sdim ArgRecycler.clear(ExpressionAllocator); 2948311116Sdim ExpressionAllocator.Reset(); 2949311116Sdim CongruenceClasses.clear(); 2950311116Sdim ExpressionToClass.clear(); 2951311116Sdim ValueToExpression.clear(); 2952321369Sdim RealToTemp.clear(); 2953321369Sdim AdditionalUsers.clear(); 2954321369Sdim ExpressionToPhiOfOps.clear(); 2955321369Sdim TempToBlock.clear(); 2956321369Sdim TempToMemory.clear(); 2957327952Sdim PHINodeUses.clear(); 2958327952Sdim OpSafeForPHIOfOps.clear(); 2959311116Sdim ReachableBlocks.clear(); 2960311116Sdim ReachableEdges.clear(); 2961311116Sdim#ifndef NDEBUG 2962311116Sdim ProcessedCount.clear(); 2963311116Sdim#endif 2964311116Sdim InstrDFS.clear(); 2965311116Sdim InstructionsToErase.clear(); 2966311116Sdim DFSToInstr.clear(); 2967311116Sdim BlockInstRange.clear(); 2968311116Sdim TouchedInstructions.clear(); 2969321369Sdim MemoryAccessToClass.clear(); 2970321369Sdim PredicateToUsers.clear(); 2971321369Sdim MemoryToUsers.clear(); 2972327952Sdim RevisitOnReachabilityChange.clear(); 2973311116Sdim} 2974311116Sdim 2975321369Sdim// Assign local DFS number mapping to instructions, and leave space for Value 2976321369Sdim// PHI's. 2977311116Sdimstd::pair<unsigned, unsigned> NewGVN::assignDFSNumbers(BasicBlock *B, 2978311116Sdim unsigned Start) { 2979311116Sdim unsigned End = Start; 2980321369Sdim if (MemoryAccess *MemPhi = getMemoryAccess(B)) { 2981311116Sdim InstrDFS[MemPhi] = End++; 2982311116Sdim DFSToInstr.emplace_back(MemPhi); 2983311116Sdim } 2984311116Sdim 2985321369Sdim // Then the real block goes next. 2986311116Sdim for (auto &I : *B) { 2987321369Sdim // There's no need to call isInstructionTriviallyDead more than once on 2988321369Sdim // an instruction. Therefore, once we know that an instruction is dead 2989321369Sdim // we change its DFS number so that it doesn't get value numbered. 2990321369Sdim if (isInstructionTriviallyDead(&I, TLI)) { 2991321369Sdim InstrDFS[&I] = 0; 2992341825Sdim LLVM_DEBUG(dbgs() << "Skipping trivially dead instruction " << I << "\n"); 2993321369Sdim markInstructionForDeletion(&I); 2994321369Sdim continue; 2995321369Sdim } 2996327952Sdim if (isa<PHINode>(&I)) 2997327952Sdim RevisitOnReachabilityChange[B].set(End); 2998311116Sdim InstrDFS[&I] = End++; 2999311116Sdim DFSToInstr.emplace_back(&I); 3000311116Sdim } 3001311116Sdim 3002311116Sdim // All of the range functions taken half-open ranges (open on the end side). 3003311116Sdim // So we do not subtract one from count, because at this point it is one 3004311116Sdim // greater than the last instruction. 3005311116Sdim return std::make_pair(Start, End); 3006311116Sdim} 3007311116Sdim 3008321369Sdimvoid NewGVN::updateProcessedCount(const Value *V) { 3009311116Sdim#ifndef NDEBUG 3010311116Sdim if (ProcessedCount.count(V) == 0) { 3011311116Sdim ProcessedCount.insert({V, 1}); 3012311116Sdim } else { 3013321369Sdim ++ProcessedCount[V]; 3014311116Sdim assert(ProcessedCount[V] < 100 && 3015311116Sdim "Seem to have processed the same Value a lot"); 3016311116Sdim } 3017311116Sdim#endif 3018311116Sdim} 3019327952Sdim 3020311116Sdim// Evaluate MemoryPhi nodes symbolically, just like PHI nodes 3021311116Sdimvoid NewGVN::valueNumberMemoryPhi(MemoryPhi *MP) { 3022311116Sdim // If all the arguments are the same, the MemoryPhi has the same value as the 3023321369Sdim // argument. Filter out unreachable blocks and self phis from our operands. 3024321369Sdim // TODO: We could do cycle-checking on the memory phis to allow valueizing for 3025321369Sdim // self-phi checking. 3026321369Sdim const BasicBlock *PHIBlock = MP->getBlock(); 3027311116Sdim auto Filtered = make_filter_range(MP->operands(), [&](const Use &U) { 3028321369Sdim return cast<MemoryAccess>(U) != MP && 3029321369Sdim !isMemoryAccessTOP(cast<MemoryAccess>(U)) && 3030321369Sdim ReachableEdges.count({MP->getIncomingBlock(U), PHIBlock}); 3031311116Sdim }); 3032321369Sdim // If all that is left is nothing, our memoryphi is undef. We keep it as 3033321369Sdim // InitialClass. Note: The only case this should happen is if we have at 3034321369Sdim // least one self-argument. 3035321369Sdim if (Filtered.begin() == Filtered.end()) { 3036321369Sdim if (setMemoryClass(MP, TOPClass)) 3037321369Sdim markMemoryUsersTouched(MP); 3038321369Sdim return; 3039321369Sdim } 3040311116Sdim 3041311116Sdim // Transform the remaining operands into operand leaders. 3042311116Sdim // FIXME: mapped_iterator should have a range version. 3043311116Sdim auto LookupFunc = [&](const Use &U) { 3044321369Sdim return lookupMemoryLeader(cast<MemoryAccess>(U)); 3045311116Sdim }; 3046311116Sdim auto MappedBegin = map_iterator(Filtered.begin(), LookupFunc); 3047311116Sdim auto MappedEnd = map_iterator(Filtered.end(), LookupFunc); 3048311116Sdim 3049311116Sdim // and now check if all the elements are equal. 3050311116Sdim // Sadly, we can't use std::equals since these are random access iterators. 3051321369Sdim const auto *AllSameValue = *MappedBegin; 3052311116Sdim ++MappedBegin; 3053311116Sdim bool AllEqual = std::all_of( 3054311116Sdim MappedBegin, MappedEnd, 3055311116Sdim [&AllSameValue](const MemoryAccess *V) { return V == AllSameValue; }); 3056311116Sdim 3057311116Sdim if (AllEqual) 3058341825Sdim LLVM_DEBUG(dbgs() << "Memory Phi value numbered to " << *AllSameValue 3059341825Sdim << "\n"); 3060311116Sdim else 3061341825Sdim LLVM_DEBUG(dbgs() << "Memory Phi value numbered to itself\n"); 3062321369Sdim // If it's equal to something, it's in that class. Otherwise, it has to be in 3063321369Sdim // a class where it is the leader (other things may be equivalent to it, but 3064321369Sdim // it needs to start off in its own class, which means it must have been the 3065321369Sdim // leader, and it can't have stopped being the leader because it was never 3066321369Sdim // removed). 3067321369Sdim CongruenceClass *CC = 3068321369Sdim AllEqual ? getMemoryClass(AllSameValue) : ensureLeaderOfMemoryClass(MP); 3069321369Sdim auto OldState = MemoryPhiState.lookup(MP); 3070321369Sdim assert(OldState != MPS_Invalid && "Invalid memory phi state"); 3071321369Sdim auto NewState = AllEqual ? MPS_Equivalent : MPS_Unique; 3072321369Sdim MemoryPhiState[MP] = NewState; 3073321369Sdim if (setMemoryClass(MP, CC) || OldState != NewState) 3074311116Sdim markMemoryUsersTouched(MP); 3075311116Sdim} 3076311116Sdim 3077311116Sdim// Value number a single instruction, symbolically evaluating, performing 3078311116Sdim// congruence finding, and updating mappings. 3079311116Sdimvoid NewGVN::valueNumberInstruction(Instruction *I) { 3080341825Sdim LLVM_DEBUG(dbgs() << "Processing instruction " << *I << "\n"); 3081311116Sdim if (!I->isTerminator()) { 3082321369Sdim const Expression *Symbolized = nullptr; 3083321369Sdim SmallPtrSet<Value *, 2> Visited; 3084321369Sdim if (DebugCounter::shouldExecute(VNCounter)) { 3085321369Sdim Symbolized = performSymbolicEvaluation(I, Visited); 3086321369Sdim // Make a phi of ops if necessary 3087321369Sdim if (Symbolized && !isa<ConstantExpression>(Symbolized) && 3088321369Sdim !isa<VariableExpression>(Symbolized) && PHINodeUses.count(I)) { 3089327952Sdim auto *PHIE = makePossiblePHIOfOps(I, Visited); 3090327952Sdim // If we created a phi of ops, use it. 3091327952Sdim // If we couldn't create one, make sure we don't leave one lying around 3092327952Sdim if (PHIE) { 3093321369Sdim Symbolized = PHIE; 3094327952Sdim } else if (auto *Op = RealToTemp.lookup(I)) { 3095327952Sdim removePhiOfOps(I, Op); 3096327952Sdim } 3097321369Sdim } 3098321369Sdim } else { 3099321369Sdim // Mark the instruction as unused so we don't value number it again. 3100321369Sdim InstrDFS[I] = 0; 3101321369Sdim } 3102311116Sdim // If we couldn't come up with a symbolic expression, use the unknown 3103311116Sdim // expression 3104311116Sdim if (Symbolized == nullptr) 3105311116Sdim Symbolized = createUnknownExpression(I); 3106311116Sdim performCongruenceFinding(I, Symbolized); 3107311116Sdim } else { 3108311116Sdim // Handle terminators that return values. All of them produce values we 3109321369Sdim // don't currently understand. We don't place non-value producing 3110321369Sdim // terminators in a class. 3111311327Sdim if (!I->getType()->isVoidTy()) { 3112311116Sdim auto *Symbolized = createUnknownExpression(I); 3113311116Sdim performCongruenceFinding(I, Symbolized); 3114311116Sdim } 3115344779Sdim processOutgoingEdges(I, I->getParent()); 3116311116Sdim } 3117311116Sdim} 3118311116Sdim 3119312197Sdim// Check if there is a path, using single or equal argument phi nodes, from 3120312197Sdim// First to Second. 3121321369Sdimbool NewGVN::singleReachablePHIPath( 3122321369Sdim SmallPtrSet<const MemoryAccess *, 8> &Visited, const MemoryAccess *First, 3123321369Sdim const MemoryAccess *Second) const { 3124312197Sdim if (First == Second) 3125312197Sdim return true; 3126321369Sdim if (MSSA->isLiveOnEntryDef(First)) 3127321369Sdim return false; 3128312197Sdim 3129321369Sdim // This is not perfect, but as we're just verifying here, we can live with 3130321369Sdim // the loss of precision. The real solution would be that of doing strongly 3131321369Sdim // connected component finding in this routine, and it's probably not worth 3132321369Sdim // the complexity for the time being. So, we just keep a set of visited 3133321369Sdim // MemoryAccess and return true when we hit a cycle. 3134321369Sdim if (Visited.count(First)) 3135321369Sdim return true; 3136321369Sdim Visited.insert(First); 3137321369Sdim 3138321369Sdim const auto *EndDef = First; 3139321369Sdim for (auto *ChainDef : optimized_def_chain(First)) { 3140321369Sdim if (ChainDef == Second) 3141321369Sdim return true; 3142321369Sdim if (MSSA->isLiveOnEntryDef(ChainDef)) 3143321369Sdim return false; 3144321369Sdim EndDef = ChainDef; 3145312197Sdim } 3146321369Sdim auto *MP = cast<MemoryPhi>(EndDef); 3147321369Sdim auto ReachableOperandPred = [&](const Use &U) { 3148321369Sdim return ReachableEdges.count({MP->getIncomingBlock(U), MP->getBlock()}); 3149321369Sdim }; 3150321369Sdim auto FilteredPhiArgs = 3151321369Sdim make_filter_range(MP->operands(), ReachableOperandPred); 3152321369Sdim SmallVector<const Value *, 32> OperandList; 3153344779Sdim llvm::copy(FilteredPhiArgs, std::back_inserter(OperandList)); 3154344779Sdim bool Okay = is_splat(OperandList); 3155321369Sdim if (Okay) 3156321369Sdim return singleReachablePHIPath(Visited, cast<MemoryAccess>(OperandList[0]), 3157321369Sdim Second); 3158321369Sdim return false; 3159312197Sdim} 3160312197Sdim 3161311116Sdim// Verify the that the memory equivalence table makes sense relative to the 3162312197Sdim// congruence classes. Note that this checking is not perfect, and is currently 3163321369Sdim// subject to very rare false negatives. It is only useful for 3164321369Sdim// testing/debugging. 3165312197Sdimvoid NewGVN::verifyMemoryCongruency() const { 3166321369Sdim#ifndef NDEBUG 3167321369Sdim // Verify that the memory table equivalence and memory member set match 3168321369Sdim for (const auto *CC : CongruenceClasses) { 3169321369Sdim if (CC == TOPClass || CC->isDead()) 3170321369Sdim continue; 3171321369Sdim if (CC->getStoreCount() != 0) { 3172321369Sdim assert((CC->getStoredValue() || !isa<StoreInst>(CC->getLeader())) && 3173321369Sdim "Any class with a store as a leader should have a " 3174321369Sdim "representative stored value"); 3175321369Sdim assert(CC->getMemoryLeader() && 3176321369Sdim "Any congruence class with a store should have a " 3177321369Sdim "representative access"); 3178321369Sdim } 3179321369Sdim 3180321369Sdim if (CC->getMemoryLeader()) 3181321369Sdim assert(MemoryAccessToClass.lookup(CC->getMemoryLeader()) == CC && 3182321369Sdim "Representative MemoryAccess does not appear to be reverse " 3183321369Sdim "mapped properly"); 3184321369Sdim for (auto M : CC->memory()) 3185321369Sdim assert(MemoryAccessToClass.lookup(M) == CC && 3186321369Sdim "Memory member does not appear to be reverse mapped properly"); 3187321369Sdim } 3188321369Sdim 3189321369Sdim // Anything equivalent in the MemoryAccess table should be in the same 3190311116Sdim // congruence class. 3191311116Sdim 3192311116Sdim // Filter out the unreachable and trivially dead entries, because they may 3193311116Sdim // never have been updated if the instructions were not processed. 3194311116Sdim auto ReachableAccessPred = 3195321369Sdim [&](const std::pair<const MemoryAccess *, CongruenceClass *> Pair) { 3196311116Sdim bool Result = ReachableBlocks.count(Pair.first->getBlock()); 3197321369Sdim if (!Result || MSSA->isLiveOnEntryDef(Pair.first) || 3198321369Sdim MemoryToDFSNum(Pair.first) == 0) 3199311116Sdim return false; 3200311116Sdim if (auto *MemDef = dyn_cast<MemoryDef>(Pair.first)) 3201311116Sdim return !isInstructionTriviallyDead(MemDef->getMemoryInst()); 3202321369Sdim 3203321369Sdim // We could have phi nodes which operands are all trivially dead, 3204321369Sdim // so we don't process them. 3205321369Sdim if (auto *MemPHI = dyn_cast<MemoryPhi>(Pair.first)) { 3206321369Sdim for (auto &U : MemPHI->incoming_values()) { 3207327952Sdim if (auto *I = dyn_cast<Instruction>(&*U)) { 3208321369Sdim if (!isInstructionTriviallyDead(I)) 3209321369Sdim return true; 3210321369Sdim } 3211321369Sdim } 3212321369Sdim return false; 3213321369Sdim } 3214321369Sdim 3215311116Sdim return true; 3216311116Sdim }; 3217311116Sdim 3218321369Sdim auto Filtered = make_filter_range(MemoryAccessToClass, ReachableAccessPred); 3219311116Sdim for (auto KV : Filtered) { 3220311116Sdim if (auto *FirstMUD = dyn_cast<MemoryUseOrDef>(KV.first)) { 3221321369Sdim auto *SecondMUD = dyn_cast<MemoryUseOrDef>(KV.second->getMemoryLeader()); 3222321369Sdim if (FirstMUD && SecondMUD) { 3223321369Sdim SmallPtrSet<const MemoryAccess *, 8> VisitedMAS; 3224321369Sdim assert((singleReachablePHIPath(VisitedMAS, FirstMUD, SecondMUD) || 3225321369Sdim ValueToClass.lookup(FirstMUD->getMemoryInst()) == 3226321369Sdim ValueToClass.lookup(SecondMUD->getMemoryInst())) && 3227321369Sdim "The instructions for these memory operations should have " 3228321369Sdim "been in the same congruence class or reachable through" 3229321369Sdim "a single argument phi"); 3230321369Sdim } 3231311116Sdim } else if (auto *FirstMP = dyn_cast<MemoryPhi>(KV.first)) { 3232311116Sdim // We can only sanely verify that MemoryDefs in the operand list all have 3233311116Sdim // the same class. 3234311116Sdim auto ReachableOperandPred = [&](const Use &U) { 3235321369Sdim return ReachableEdges.count( 3236321369Sdim {FirstMP->getIncomingBlock(U), FirstMP->getBlock()}) && 3237311116Sdim isa<MemoryDef>(U); 3238311116Sdim 3239311116Sdim }; 3240311116Sdim // All arguments should in the same class, ignoring unreachable arguments 3241311116Sdim auto FilteredPhiArgs = 3242311116Sdim make_filter_range(FirstMP->operands(), ReachableOperandPred); 3243311116Sdim SmallVector<const CongruenceClass *, 16> PhiOpClasses; 3244311116Sdim std::transform(FilteredPhiArgs.begin(), FilteredPhiArgs.end(), 3245311116Sdim std::back_inserter(PhiOpClasses), [&](const Use &U) { 3246311116Sdim const MemoryDef *MD = cast<MemoryDef>(U); 3247311116Sdim return ValueToClass.lookup(MD->getMemoryInst()); 3248311116Sdim }); 3249344779Sdim assert(is_splat(PhiOpClasses) && 3250311116Sdim "All MemoryPhi arguments should be in the same class"); 3251311116Sdim } 3252311116Sdim } 3253321369Sdim#endif 3254311116Sdim} 3255311116Sdim 3256321369Sdim// Verify that the sparse propagation we did actually found the maximal fixpoint 3257321369Sdim// We do this by storing the value to class mapping, touching all instructions, 3258321369Sdim// and redoing the iteration to see if anything changed. 3259321369Sdimvoid NewGVN::verifyIterationSettled(Function &F) { 3260321369Sdim#ifndef NDEBUG 3261341825Sdim LLVM_DEBUG(dbgs() << "Beginning iteration verification\n"); 3262321369Sdim if (DebugCounter::isCounterSet(VNCounter)) 3263321369Sdim DebugCounter::setCounterValue(VNCounter, StartingVNCounter); 3264321369Sdim 3265321369Sdim // Note that we have to store the actual classes, as we may change existing 3266321369Sdim // classes during iteration. This is because our memory iteration propagation 3267321369Sdim // is not perfect, and so may waste a little work. But it should generate 3268321369Sdim // exactly the same congruence classes we have now, with different IDs. 3269321369Sdim std::map<const Value *, CongruenceClass> BeforeIteration; 3270321369Sdim 3271321369Sdim for (auto &KV : ValueToClass) { 3272321369Sdim if (auto *I = dyn_cast<Instruction>(KV.first)) 3273321369Sdim // Skip unused/dead instructions. 3274321369Sdim if (InstrToDFSNum(I) == 0) 3275321369Sdim continue; 3276321369Sdim BeforeIteration.insert({KV.first, *KV.second}); 3277321369Sdim } 3278321369Sdim 3279321369Sdim TouchedInstructions.set(); 3280321369Sdim TouchedInstructions.reset(0); 3281321369Sdim iterateTouchedInstructions(); 3282321369Sdim DenseSet<std::pair<const CongruenceClass *, const CongruenceClass *>> 3283321369Sdim EqualClasses; 3284321369Sdim for (const auto &KV : ValueToClass) { 3285321369Sdim if (auto *I = dyn_cast<Instruction>(KV.first)) 3286321369Sdim // Skip unused/dead instructions. 3287321369Sdim if (InstrToDFSNum(I) == 0) 3288321369Sdim continue; 3289321369Sdim // We could sink these uses, but i think this adds a bit of clarity here as 3290321369Sdim // to what we are comparing. 3291321369Sdim auto *BeforeCC = &BeforeIteration.find(KV.first)->second; 3292321369Sdim auto *AfterCC = KV.second; 3293321369Sdim // Note that the classes can't change at this point, so we memoize the set 3294321369Sdim // that are equal. 3295321369Sdim if (!EqualClasses.count({BeforeCC, AfterCC})) { 3296321369Sdim assert(BeforeCC->isEquivalentTo(AfterCC) && 3297321369Sdim "Value number changed after main loop completed!"); 3298321369Sdim EqualClasses.insert({BeforeCC, AfterCC}); 3299321369Sdim } 3300321369Sdim } 3301321369Sdim#endif 3302321369Sdim} 3303321369Sdim 3304321369Sdim// Verify that for each store expression in the expression to class mapping, 3305321369Sdim// only the latest appears, and multiple ones do not appear. 3306321369Sdim// Because loads do not use the stored value when doing equality with stores, 3307321369Sdim// if we don't erase the old store expressions from the table, a load can find 3308321369Sdim// a no-longer valid StoreExpression. 3309321369Sdimvoid NewGVN::verifyStoreExpressions() const { 3310321369Sdim#ifndef NDEBUG 3311321369Sdim // This is the only use of this, and it's not worth defining a complicated 3312321369Sdim // densemapinfo hash/equality function for it. 3313321369Sdim std::set< 3314321369Sdim std::pair<const Value *, 3315321369Sdim std::tuple<const Value *, const CongruenceClass *, Value *>>> 3316321369Sdim StoreExpressionSet; 3317321369Sdim for (const auto &KV : ExpressionToClass) { 3318321369Sdim if (auto *SE = dyn_cast<StoreExpression>(KV.first)) { 3319321369Sdim // Make sure a version that will conflict with loads is not already there 3320321369Sdim auto Res = StoreExpressionSet.insert( 3321321369Sdim {SE->getOperand(0), std::make_tuple(SE->getMemoryLeader(), KV.second, 3322321369Sdim SE->getStoredValue())}); 3323321369Sdim bool Okay = Res.second; 3324321369Sdim // It's okay to have the same expression already in there if it is 3325321369Sdim // identical in nature. 3326321369Sdim // This can happen when the leader of the stored value changes over time. 3327321369Sdim if (!Okay) 3328321369Sdim Okay = (std::get<1>(Res.first->second) == KV.second) && 3329321369Sdim (lookupOperandLeader(std::get<2>(Res.first->second)) == 3330321369Sdim lookupOperandLeader(SE->getStoredValue())); 3331321369Sdim assert(Okay && "Stored expression conflict exists in expression table"); 3332321369Sdim auto *ValueExpr = ValueToExpression.lookup(SE->getStoreInst()); 3333321369Sdim assert(ValueExpr && ValueExpr->equals(*SE) && 3334321369Sdim "StoreExpression in ExpressionToClass is not latest " 3335321369Sdim "StoreExpression for value"); 3336321369Sdim } 3337321369Sdim } 3338321369Sdim#endif 3339321369Sdim} 3340321369Sdim 3341321369Sdim// This is the main value numbering loop, it iterates over the initial touched 3342321369Sdim// instruction set, propagating value numbers, marking things touched, etc, 3343321369Sdim// until the set of touched instructions is completely empty. 3344321369Sdimvoid NewGVN::iterateTouchedInstructions() { 3345321369Sdim unsigned int Iterations = 0; 3346321369Sdim // Figure out where touchedinstructions starts 3347321369Sdim int FirstInstr = TouchedInstructions.find_first(); 3348321369Sdim // Nothing set, nothing to iterate, just return. 3349321369Sdim if (FirstInstr == -1) 3350321369Sdim return; 3351321369Sdim const BasicBlock *LastBlock = getBlockForValue(InstrFromDFSNum(FirstInstr)); 3352321369Sdim while (TouchedInstructions.any()) { 3353321369Sdim ++Iterations; 3354321369Sdim // Walk through all the instructions in all the blocks in RPO. 3355321369Sdim // TODO: As we hit a new block, we should push and pop equalities into a 3356321369Sdim // table lookupOperandLeader can use, to catch things PredicateInfo 3357321369Sdim // might miss, like edge-only equivalences. 3358321369Sdim for (unsigned InstrNum : TouchedInstructions.set_bits()) { 3359321369Sdim 3360321369Sdim // This instruction was found to be dead. We don't bother looking 3361321369Sdim // at it again. 3362321369Sdim if (InstrNum == 0) { 3363321369Sdim TouchedInstructions.reset(InstrNum); 3364321369Sdim continue; 3365321369Sdim } 3366321369Sdim 3367321369Sdim Value *V = InstrFromDFSNum(InstrNum); 3368321369Sdim const BasicBlock *CurrBlock = getBlockForValue(V); 3369321369Sdim 3370321369Sdim // If we hit a new block, do reachability processing. 3371321369Sdim if (CurrBlock != LastBlock) { 3372321369Sdim LastBlock = CurrBlock; 3373321369Sdim bool BlockReachable = ReachableBlocks.count(CurrBlock); 3374321369Sdim const auto &CurrInstRange = BlockInstRange.lookup(CurrBlock); 3375321369Sdim 3376321369Sdim // If it's not reachable, erase any touched instructions and move on. 3377321369Sdim if (!BlockReachable) { 3378321369Sdim TouchedInstructions.reset(CurrInstRange.first, CurrInstRange.second); 3379341825Sdim LLVM_DEBUG(dbgs() << "Skipping instructions in block " 3380341825Sdim << getBlockName(CurrBlock) 3381341825Sdim << " because it is unreachable\n"); 3382321369Sdim continue; 3383321369Sdim } 3384321369Sdim updateProcessedCount(CurrBlock); 3385321369Sdim } 3386321369Sdim // Reset after processing (because we may mark ourselves as touched when 3387321369Sdim // we propagate equalities). 3388321369Sdim TouchedInstructions.reset(InstrNum); 3389321369Sdim 3390321369Sdim if (auto *MP = dyn_cast<MemoryPhi>(V)) { 3391341825Sdim LLVM_DEBUG(dbgs() << "Processing MemoryPhi " << *MP << "\n"); 3392321369Sdim valueNumberMemoryPhi(MP); 3393321369Sdim } else if (auto *I = dyn_cast<Instruction>(V)) { 3394321369Sdim valueNumberInstruction(I); 3395321369Sdim } else { 3396321369Sdim llvm_unreachable("Should have been a MemoryPhi or Instruction"); 3397321369Sdim } 3398321369Sdim updateProcessedCount(V); 3399321369Sdim } 3400321369Sdim } 3401321369Sdim NumGVNMaxIterations = std::max(NumGVNMaxIterations.getValue(), Iterations); 3402321369Sdim} 3403321369Sdim 3404311116Sdim// This is the main transformation entry point. 3405321369Sdimbool NewGVN::runGVN() { 3406321369Sdim if (DebugCounter::isCounterSet(VNCounter)) 3407321369Sdim StartingVNCounter = DebugCounter::getCounterValue(VNCounter); 3408311116Sdim bool Changed = false; 3409321369Sdim NumFuncArgs = F.arg_size(); 3410311116Sdim MSSAWalker = MSSA->getWalker(); 3411321369Sdim SingletonDeadExpression = new (ExpressionAllocator) DeadExpression(); 3412311116Sdim 3413311116Sdim // Count number of instructions for sizing of hash tables, and come 3414311116Sdim // up with a global dfs numbering for instructions. 3415311116Sdim unsigned ICount = 1; 3416311116Sdim // Add an empty instruction to account for the fact that we start at 1 3417311116Sdim DFSToInstr.emplace_back(nullptr); 3418321369Sdim // Note: We want ideal RPO traversal of the blocks, which is not quite the 3419321369Sdim // same as dominator tree order, particularly with regard whether backedges 3420321369Sdim // get visited first or second, given a block with multiple successors. 3421311116Sdim // If we visit in the wrong order, we will end up performing N times as many 3422311116Sdim // iterations. 3423311116Sdim // The dominator tree does guarantee that, for a given dom tree node, it's 3424311116Sdim // parent must occur before it in the RPO ordering. Thus, we only need to sort 3425311116Sdim // the siblings. 3426311116Sdim ReversePostOrderTraversal<Function *> RPOT(&F); 3427311116Sdim unsigned Counter = 0; 3428311116Sdim for (auto &B : RPOT) { 3429311116Sdim auto *Node = DT->getNode(B); 3430311116Sdim assert(Node && "RPO and Dominator tree should have same reachability"); 3431311116Sdim RPOOrdering[Node] = ++Counter; 3432311116Sdim } 3433311116Sdim // Sort dominator tree children arrays into RPO. 3434311116Sdim for (auto &B : RPOT) { 3435311116Sdim auto *Node = DT->getNode(B); 3436311116Sdim if (Node->getChildren().size() > 1) 3437341825Sdim llvm::sort(Node->begin(), Node->end(), 3438341825Sdim [&](const DomTreeNode *A, const DomTreeNode *B) { 3439341825Sdim return RPOOrdering[A] < RPOOrdering[B]; 3440341825Sdim }); 3441311116Sdim } 3442311116Sdim 3443311116Sdim // Now a standard depth first ordering of the domtree is equivalent to RPO. 3444321369Sdim for (auto DTN : depth_first(DT->getRootNode())) { 3445321369Sdim BasicBlock *B = DTN->getBlock(); 3446311116Sdim const auto &BlockRange = assignDFSNumbers(B, ICount); 3447311116Sdim BlockInstRange.insert({B, BlockRange}); 3448311116Sdim ICount += BlockRange.second - BlockRange.first; 3449311116Sdim } 3450321369Sdim initializeCongruenceClasses(F); 3451311116Sdim 3452311116Sdim TouchedInstructions.resize(ICount); 3453311116Sdim // Ensure we don't end up resizing the expressionToClass map, as 3454311116Sdim // that can be quite expensive. At most, we have one expression per 3455311116Sdim // instruction. 3456311116Sdim ExpressionToClass.reserve(ICount); 3457311116Sdim 3458311116Sdim // Initialize the touched instructions to include the entry block. 3459311116Sdim const auto &InstRange = BlockInstRange.lookup(&F.getEntryBlock()); 3460311116Sdim TouchedInstructions.set(InstRange.first, InstRange.second); 3461341825Sdim LLVM_DEBUG(dbgs() << "Block " << getBlockName(&F.getEntryBlock()) 3462341825Sdim << " marked reachable\n"); 3463311116Sdim ReachableBlocks.insert(&F.getEntryBlock()); 3464311116Sdim 3465321369Sdim iterateTouchedInstructions(); 3466321369Sdim verifyMemoryCongruency(); 3467321369Sdim verifyIterationSettled(F); 3468321369Sdim verifyStoreExpressions(); 3469311116Sdim 3470311116Sdim Changed |= eliminateInstructions(F); 3471311116Sdim 3472311116Sdim // Delete all instructions marked for deletion. 3473311116Sdim for (Instruction *ToErase : InstructionsToErase) { 3474311116Sdim if (!ToErase->use_empty()) 3475311116Sdim ToErase->replaceAllUsesWith(UndefValue::get(ToErase->getType())); 3476311116Sdim 3477344779Sdim assert(ToErase->getParent() && 3478344779Sdim "BB containing ToErase deleted unexpectedly!"); 3479344779Sdim ToErase->eraseFromParent(); 3480311116Sdim } 3481353358Sdim Changed |= !InstructionsToErase.empty(); 3482311116Sdim 3483311116Sdim // Delete all unreachable blocks. 3484311116Sdim auto UnreachableBlockPred = [&](const BasicBlock &BB) { 3485311116Sdim return !ReachableBlocks.count(&BB); 3486311116Sdim }; 3487311116Sdim 3488311116Sdim for (auto &BB : make_filter_range(F, UnreachableBlockPred)) { 3489341825Sdim LLVM_DEBUG(dbgs() << "We believe block " << getBlockName(&BB) 3490341825Sdim << " is unreachable\n"); 3491311116Sdim deleteInstructionsInBlock(&BB); 3492311116Sdim Changed = true; 3493311116Sdim } 3494311116Sdim 3495311116Sdim cleanupTables(); 3496311116Sdim return Changed; 3497311116Sdim} 3498311116Sdim 3499311116Sdimstruct NewGVN::ValueDFS { 3500311116Sdim int DFSIn = 0; 3501311116Sdim int DFSOut = 0; 3502311116Sdim int LocalNum = 0; 3503327952Sdim 3504321369Sdim // Only one of Def and U will be set. 3505321369Sdim // The bool in the Def tells us whether the Def is the stored value of a 3506321369Sdim // store. 3507321369Sdim PointerIntPair<Value *, 1, bool> Def; 3508311116Sdim Use *U = nullptr; 3509327952Sdim 3510311116Sdim bool operator<(const ValueDFS &Other) const { 3511311116Sdim // It's not enough that any given field be less than - we have sets 3512311116Sdim // of fields that need to be evaluated together to give a proper ordering. 3513311116Sdim // For example, if you have; 3514311116Sdim // DFS (1, 3) 3515311116Sdim // Val 0 3516311116Sdim // DFS (1, 2) 3517311116Sdim // Val 50 3518311116Sdim // We want the second to be less than the first, but if we just go field 3519311116Sdim // by field, we will get to Val 0 < Val 50 and say the first is less than 3520311116Sdim // the second. We only want it to be less than if the DFS orders are equal. 3521311116Sdim // 3522311116Sdim // Each LLVM instruction only produces one value, and thus the lowest-level 3523311116Sdim // differentiator that really matters for the stack (and what we use as as a 3524311116Sdim // replacement) is the local dfs number. 3525311116Sdim // Everything else in the structure is instruction level, and only affects 3526311116Sdim // the order in which we will replace operands of a given instruction. 3527311116Sdim // 3528311116Sdim // For a given instruction (IE things with equal dfsin, dfsout, localnum), 3529311116Sdim // the order of replacement of uses does not matter. 3530311116Sdim // IE given, 3531311116Sdim // a = 5 3532311116Sdim // b = a + a 3533311116Sdim // When you hit b, you will have two valuedfs with the same dfsin, out, and 3534311116Sdim // localnum. 3535311116Sdim // The .val will be the same as well. 3536311116Sdim // The .u's will be different. 3537311116Sdim // You will replace both, and it does not matter what order you replace them 3538311116Sdim // in (IE whether you replace operand 2, then operand 1, or operand 1, then 3539311116Sdim // operand 2). 3540311116Sdim // Similarly for the case of same dfsin, dfsout, localnum, but different 3541311116Sdim // .val's 3542311116Sdim // a = 5 3543311116Sdim // b = 6 3544311116Sdim // c = a + b 3545311116Sdim // in c, we will a valuedfs for a, and one for b,with everything the same 3546311116Sdim // but .val and .u. 3547311116Sdim // It does not matter what order we replace these operands in. 3548311116Sdim // You will always end up with the same IR, and this is guaranteed. 3549321369Sdim return std::tie(DFSIn, DFSOut, LocalNum, Def, U) < 3550321369Sdim std::tie(Other.DFSIn, Other.DFSOut, Other.LocalNum, Other.Def, 3551311116Sdim Other.U); 3552311116Sdim } 3553311116Sdim}; 3554311116Sdim 3555321369Sdim// This function converts the set of members for a congruence class from values, 3556321369Sdim// to sets of defs and uses with associated DFS info. The total number of 3557321369Sdim// reachable uses for each value is stored in UseCount, and instructions that 3558321369Sdim// seem 3559321369Sdim// dead (have no non-dead uses) are stored in ProbablyDead. 3560321369Sdimvoid NewGVN::convertClassToDFSOrdered( 3561321369Sdim const CongruenceClass &Dense, SmallVectorImpl<ValueDFS> &DFSOrderedSet, 3562321369Sdim DenseMap<const Value *, unsigned int> &UseCounts, 3563321369Sdim SmallPtrSetImpl<Instruction *> &ProbablyDead) const { 3564311116Sdim for (auto D : Dense) { 3565311116Sdim // First add the value. 3566311116Sdim BasicBlock *BB = getBlockForValue(D); 3567311116Sdim // Constants are handled prior to ever calling this function, so 3568311116Sdim // we should only be left with instructions as members. 3569311116Sdim assert(BB && "Should have figured out a basic block for value"); 3570321369Sdim ValueDFS VDDef; 3571321369Sdim DomTreeNode *DomNode = DT->getNode(BB); 3572321369Sdim VDDef.DFSIn = DomNode->getDFSNumIn(); 3573321369Sdim VDDef.DFSOut = DomNode->getDFSNumOut(); 3574321369Sdim // If it's a store, use the leader of the value operand, if it's always 3575321369Sdim // available, or the value operand. TODO: We could do dominance checks to 3576321369Sdim // find a dominating leader, but not worth it ATM. 3577321369Sdim if (auto *SI = dyn_cast<StoreInst>(D)) { 3578321369Sdim auto Leader = lookupOperandLeader(SI->getValueOperand()); 3579321369Sdim if (alwaysAvailable(Leader)) { 3580321369Sdim VDDef.Def.setPointer(Leader); 3581321369Sdim } else { 3582321369Sdim VDDef.Def.setPointer(SI->getValueOperand()); 3583321369Sdim VDDef.Def.setInt(true); 3584321369Sdim } 3585321369Sdim } else { 3586321369Sdim VDDef.Def.setPointer(D); 3587321369Sdim } 3588321369Sdim assert(isa<Instruction>(D) && 3589321369Sdim "The dense set member should always be an instruction"); 3590321369Sdim Instruction *Def = cast<Instruction>(D); 3591321369Sdim VDDef.LocalNum = InstrToDFSNum(D); 3592321369Sdim DFSOrderedSet.push_back(VDDef); 3593321369Sdim // If there is a phi node equivalent, add it 3594321369Sdim if (auto *PN = RealToTemp.lookup(Def)) { 3595321369Sdim auto *PHIE = 3596321369Sdim dyn_cast_or_null<PHIExpression>(ValueToExpression.lookup(Def)); 3597321369Sdim if (PHIE) { 3598321369Sdim VDDef.Def.setInt(false); 3599321369Sdim VDDef.Def.setPointer(PN); 3600321369Sdim VDDef.LocalNum = 0; 3601321369Sdim DFSOrderedSet.push_back(VDDef); 3602321369Sdim } 3603321369Sdim } 3604311116Sdim 3605321369Sdim unsigned int UseCount = 0; 3606321369Sdim // Now add the uses. 3607321369Sdim for (auto &U : Def->uses()) { 3608311116Sdim if (auto *I = dyn_cast<Instruction>(U.getUser())) { 3609321369Sdim // Don't try to replace into dead uses 3610321369Sdim if (InstructionsToErase.count(I)) 3611321369Sdim continue; 3612321369Sdim ValueDFS VDUse; 3613311116Sdim // Put the phi node uses in the incoming block. 3614311116Sdim BasicBlock *IBlock; 3615311116Sdim if (auto *P = dyn_cast<PHINode>(I)) { 3616311116Sdim IBlock = P->getIncomingBlock(U); 3617311116Sdim // Make phi node users appear last in the incoming block 3618311116Sdim // they are from. 3619321369Sdim VDUse.LocalNum = InstrDFS.size() + 1; 3620311116Sdim } else { 3621321369Sdim IBlock = getBlockForValue(I); 3622321369Sdim VDUse.LocalNum = InstrToDFSNum(I); 3623311116Sdim } 3624321369Sdim 3625321369Sdim // Skip uses in unreachable blocks, as we're going 3626321369Sdim // to delete them. 3627321369Sdim if (ReachableBlocks.count(IBlock) == 0) 3628321369Sdim continue; 3629321369Sdim 3630321369Sdim DomTreeNode *DomNode = DT->getNode(IBlock); 3631321369Sdim VDUse.DFSIn = DomNode->getDFSNumIn(); 3632321369Sdim VDUse.DFSOut = DomNode->getDFSNumOut(); 3633321369Sdim VDUse.U = &U; 3634321369Sdim ++UseCount; 3635321369Sdim DFSOrderedSet.emplace_back(VDUse); 3636311116Sdim } 3637311116Sdim } 3638321369Sdim 3639321369Sdim // If there are no uses, it's probably dead (but it may have side-effects, 3640321369Sdim // so not definitely dead. Otherwise, store the number of uses so we can 3641321369Sdim // track if it becomes dead later). 3642321369Sdim if (UseCount == 0) 3643321369Sdim ProbablyDead.insert(Def); 3644321369Sdim else 3645321369Sdim UseCounts[Def] = UseCount; 3646311116Sdim } 3647311116Sdim} 3648311116Sdim 3649321369Sdim// This function converts the set of members for a congruence class from values, 3650321369Sdim// to the set of defs for loads and stores, with associated DFS info. 3651321369Sdimvoid NewGVN::convertClassToLoadsAndStores( 3652321369Sdim const CongruenceClass &Dense, 3653321369Sdim SmallVectorImpl<ValueDFS> &LoadsAndStores) const { 3654321369Sdim for (auto D : Dense) { 3655321369Sdim if (!isa<LoadInst>(D) && !isa<StoreInst>(D)) 3656321369Sdim continue; 3657321369Sdim 3658321369Sdim BasicBlock *BB = getBlockForValue(D); 3659321369Sdim ValueDFS VD; 3660321369Sdim DomTreeNode *DomNode = DT->getNode(BB); 3661321369Sdim VD.DFSIn = DomNode->getDFSNumIn(); 3662321369Sdim VD.DFSOut = DomNode->getDFSNumOut(); 3663321369Sdim VD.Def.setPointer(D); 3664321369Sdim 3665321369Sdim // If it's an instruction, use the real local dfs number. 3666321369Sdim if (auto *I = dyn_cast<Instruction>(D)) 3667321369Sdim VD.LocalNum = InstrToDFSNum(I); 3668321369Sdim else 3669321369Sdim llvm_unreachable("Should have been an instruction"); 3670321369Sdim 3671321369Sdim LoadsAndStores.emplace_back(VD); 3672321369Sdim } 3673321369Sdim} 3674321369Sdim 3675311116Sdimstatic void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl) { 3676311116Sdim patchReplacementInstruction(I, Repl); 3677311116Sdim I->replaceAllUsesWith(Repl); 3678311116Sdim} 3679311116Sdim 3680311116Sdimvoid NewGVN::deleteInstructionsInBlock(BasicBlock *BB) { 3681341825Sdim LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << *BB); 3682311116Sdim ++NumGVNBlocksDeleted; 3683311116Sdim 3684311116Sdim // Delete the instructions backwards, as it has a reduced likelihood of having 3685311116Sdim // to update as many def-use and use-def chains. Start after the terminator. 3686311116Sdim auto StartPoint = BB->rbegin(); 3687311116Sdim ++StartPoint; 3688311116Sdim // Note that we explicitly recalculate BB->rend() on each iteration, 3689311116Sdim // as it may change when we remove the first instruction. 3690311116Sdim for (BasicBlock::reverse_iterator I(StartPoint); I != BB->rend();) { 3691311116Sdim Instruction &Inst = *I++; 3692311116Sdim if (!Inst.use_empty()) 3693311116Sdim Inst.replaceAllUsesWith(UndefValue::get(Inst.getType())); 3694311116Sdim if (isa<LandingPadInst>(Inst)) 3695311116Sdim continue; 3696311116Sdim 3697311116Sdim Inst.eraseFromParent(); 3698311116Sdim ++NumGVNInstrDeleted; 3699311116Sdim } 3700321369Sdim // Now insert something that simplifycfg will turn into an unreachable. 3701321369Sdim Type *Int8Ty = Type::getInt8Ty(BB->getContext()); 3702321369Sdim new StoreInst(UndefValue::get(Int8Ty), 3703321369Sdim Constant::getNullValue(Int8Ty->getPointerTo()), 3704321369Sdim BB->getTerminator()); 3705311116Sdim} 3706311116Sdim 3707311116Sdimvoid NewGVN::markInstructionForDeletion(Instruction *I) { 3708341825Sdim LLVM_DEBUG(dbgs() << "Marking " << *I << " for deletion\n"); 3709311116Sdim InstructionsToErase.insert(I); 3710311116Sdim} 3711311116Sdim 3712311116Sdimvoid NewGVN::replaceInstruction(Instruction *I, Value *V) { 3713341825Sdim LLVM_DEBUG(dbgs() << "Replacing " << *I << " with " << *V << "\n"); 3714311116Sdim patchAndReplaceAllUsesWith(I, V); 3715311116Sdim // We save the actual erasing to avoid invalidating memory 3716311116Sdim // dependencies until we are done with everything. 3717311116Sdim markInstructionForDeletion(I); 3718311116Sdim} 3719311116Sdim 3720311116Sdimnamespace { 3721311116Sdim 3722311116Sdim// This is a stack that contains both the value and dfs info of where 3723311116Sdim// that value is valid. 3724311116Sdimclass ValueDFSStack { 3725311116Sdimpublic: 3726311116Sdim Value *back() const { return ValueStack.back(); } 3727311116Sdim std::pair<int, int> dfs_back() const { return DFSStack.back(); } 3728311116Sdim 3729311116Sdim void push_back(Value *V, int DFSIn, int DFSOut) { 3730311116Sdim ValueStack.emplace_back(V); 3731311116Sdim DFSStack.emplace_back(DFSIn, DFSOut); 3732311116Sdim } 3733327952Sdim 3734311116Sdim bool empty() const { return DFSStack.empty(); } 3735327952Sdim 3736311116Sdim bool isInScope(int DFSIn, int DFSOut) const { 3737311116Sdim if (empty()) 3738311116Sdim return false; 3739311116Sdim return DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second; 3740311116Sdim } 3741311116Sdim 3742311116Sdim void popUntilDFSScope(int DFSIn, int DFSOut) { 3743311116Sdim 3744311116Sdim // These two should always be in sync at this point. 3745311116Sdim assert(ValueStack.size() == DFSStack.size() && 3746311116Sdim "Mismatch between ValueStack and DFSStack"); 3747311116Sdim while ( 3748311116Sdim !DFSStack.empty() && 3749311116Sdim !(DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second)) { 3750311116Sdim DFSStack.pop_back(); 3751311116Sdim ValueStack.pop_back(); 3752311116Sdim } 3753311116Sdim } 3754311116Sdim 3755311116Sdimprivate: 3756311116Sdim SmallVector<Value *, 8> ValueStack; 3757311116Sdim SmallVector<std::pair<int, int>, 8> DFSStack; 3758311116Sdim}; 3759327952Sdim 3760327952Sdim} // end anonymous namespace 3761327952Sdim 3762327952Sdim// Given an expression, get the congruence class for it. 3763327952SdimCongruenceClass *NewGVN::getClassForExpression(const Expression *E) const { 3764327952Sdim if (auto *VE = dyn_cast<VariableExpression>(E)) 3765327952Sdim return ValueToClass.lookup(VE->getVariableValue()); 3766327952Sdim else if (isa<DeadExpression>(E)) 3767327952Sdim return TOPClass; 3768327952Sdim return ExpressionToClass.lookup(E); 3769311116Sdim} 3770311116Sdim 3771321369Sdim// Given a value and a basic block we are trying to see if it is available in, 3772321369Sdim// see if the value has a leader available in that block. 3773327952SdimValue *NewGVN::findPHIOfOpsLeader(const Expression *E, 3774327952Sdim const Instruction *OrigInst, 3775321369Sdim const BasicBlock *BB) const { 3776321369Sdim // It would already be constant if we could make it constant 3777321369Sdim if (auto *CE = dyn_cast<ConstantExpression>(E)) 3778321369Sdim return CE->getConstantValue(); 3779327952Sdim if (auto *VE = dyn_cast<VariableExpression>(E)) { 3780327952Sdim auto *V = VE->getVariableValue(); 3781327952Sdim if (alwaysAvailable(V) || DT->dominates(getBlockForValue(V), BB)) 3782327952Sdim return VE->getVariableValue(); 3783327952Sdim } 3784321369Sdim 3785327952Sdim auto *CC = getClassForExpression(E); 3786321369Sdim if (!CC) 3787321369Sdim return nullptr; 3788321369Sdim if (alwaysAvailable(CC->getLeader())) 3789321369Sdim return CC->getLeader(); 3790321369Sdim 3791321369Sdim for (auto Member : *CC) { 3792321369Sdim auto *MemberInst = dyn_cast<Instruction>(Member); 3793327952Sdim if (MemberInst == OrigInst) 3794327952Sdim continue; 3795321369Sdim // Anything that isn't an instruction is always available. 3796321369Sdim if (!MemberInst) 3797321369Sdim return Member; 3798327952Sdim if (DT->dominates(getBlockForValue(MemberInst), BB)) 3799321369Sdim return Member; 3800321369Sdim } 3801321369Sdim return nullptr; 3802321369Sdim} 3803321369Sdim 3804311116Sdimbool NewGVN::eliminateInstructions(Function &F) { 3805311116Sdim // This is a non-standard eliminator. The normal way to eliminate is 3806311116Sdim // to walk the dominator tree in order, keeping track of available 3807311116Sdim // values, and eliminating them. However, this is mildly 3808311116Sdim // pointless. It requires doing lookups on every instruction, 3809311116Sdim // regardless of whether we will ever eliminate it. For 3810311116Sdim // instructions part of most singleton congruence classes, we know we 3811311116Sdim // will never eliminate them. 3812311116Sdim 3813311116Sdim // Instead, this eliminator looks at the congruence classes directly, sorts 3814311116Sdim // them into a DFS ordering of the dominator tree, and then we just 3815311116Sdim // perform elimination straight on the sets by walking the congruence 3816311116Sdim // class member uses in order, and eliminate the ones dominated by the 3817311116Sdim // last member. This is worst case O(E log E) where E = number of 3818311116Sdim // instructions in a single congruence class. In theory, this is all 3819311116Sdim // instructions. In practice, it is much faster, as most instructions are 3820311116Sdim // either in singleton congruence classes or can't possibly be eliminated 3821311116Sdim // anyway (if there are no overlapping DFS ranges in class). 3822311116Sdim // When we find something not dominated, it becomes the new leader 3823311116Sdim // for elimination purposes. 3824311116Sdim // TODO: If we wanted to be faster, We could remove any members with no 3825311116Sdim // overlapping ranges while sorting, as we will never eliminate anything 3826311116Sdim // with those members, as they don't dominate anything else in our set. 3827311116Sdim 3828311116Sdim bool AnythingReplaced = false; 3829311116Sdim 3830311116Sdim // Since we are going to walk the domtree anyway, and we can't guarantee the 3831311116Sdim // DFS numbers are updated, we compute some ourselves. 3832311116Sdim DT->updateDFSNumbers(); 3833311116Sdim 3834321369Sdim // Go through all of our phi nodes, and kill the arguments associated with 3835321369Sdim // unreachable edges. 3836327952Sdim auto ReplaceUnreachablePHIArgs = [&](PHINode *PHI, BasicBlock *BB) { 3837327952Sdim for (auto &Operand : PHI->incoming_values()) 3838327952Sdim if (!ReachableEdges.count({PHI->getIncomingBlock(Operand), BB})) { 3839341825Sdim LLVM_DEBUG(dbgs() << "Replacing incoming value of " << PHI 3840341825Sdim << " for block " 3841341825Sdim << getBlockName(PHI->getIncomingBlock(Operand)) 3842341825Sdim << " with undef due to it being unreachable\n"); 3843327952Sdim Operand.set(UndefValue::get(PHI->getType())); 3844311116Sdim } 3845321369Sdim }; 3846327952Sdim // Replace unreachable phi arguments. 3847327952Sdim // At this point, RevisitOnReachabilityChange only contains: 3848327952Sdim // 3849327952Sdim // 1. PHIs 3850327952Sdim // 2. Temporaries that will convert to PHIs 3851327952Sdim // 3. Operations that are affected by an unreachable edge but do not fit into 3852327952Sdim // 1 or 2 (rare). 3853327952Sdim // So it is a slight overshoot of what we want. We could make it exact by 3854327952Sdim // using two SparseBitVectors per block. 3855321369Sdim DenseMap<const BasicBlock *, unsigned> ReachablePredCount; 3856327952Sdim for (auto &KV : ReachableEdges) 3857321369Sdim ReachablePredCount[KV.getEnd()]++; 3858327952Sdim for (auto &BBPair : RevisitOnReachabilityChange) { 3859327952Sdim for (auto InstNum : BBPair.second) { 3860327952Sdim auto *Inst = InstrFromDFSNum(InstNum); 3861327952Sdim auto *PHI = dyn_cast<PHINode>(Inst); 3862327952Sdim PHI = PHI ? PHI : dyn_cast_or_null<PHINode>(RealToTemp.lookup(Inst)); 3863327952Sdim if (!PHI) 3864327952Sdim continue; 3865327952Sdim auto *BB = BBPair.first; 3866327952Sdim if (ReachablePredCount.lookup(BB) != PHI->getNumIncomingValues()) 3867321369Sdim ReplaceUnreachablePHIArgs(PHI, BB); 3868311116Sdim } 3869327952Sdim } 3870311116Sdim 3871321369Sdim // Map to store the use counts 3872321369Sdim DenseMap<const Value *, unsigned int> UseCounts; 3873321369Sdim for (auto *CC : reverse(CongruenceClasses)) { 3874341825Sdim LLVM_DEBUG(dbgs() << "Eliminating in congruence class " << CC->getID() 3875341825Sdim << "\n"); 3876321369Sdim // Track the equivalent store info so we can decide whether to try 3877321369Sdim // dead store elimination. 3878321369Sdim SmallVector<ValueDFS, 8> PossibleDeadStores; 3879321369Sdim SmallPtrSet<Instruction *, 8> ProbablyDead; 3880321369Sdim if (CC->isDead() || CC->empty()) 3881311116Sdim continue; 3882321369Sdim // Everything still in the TOP class is unreachable or dead. 3883321369Sdim if (CC == TOPClass) { 3884321369Sdim for (auto M : *CC) { 3885321369Sdim auto *VTE = ValueToExpression.lookup(M); 3886321369Sdim if (VTE && isa<DeadExpression>(VTE)) 3887321369Sdim markInstructionForDeletion(cast<Instruction>(M)); 3888321369Sdim assert((!ReachableBlocks.count(cast<Instruction>(M)->getParent()) || 3889321369Sdim InstructionsToErase.count(cast<Instruction>(M))) && 3890321369Sdim "Everything in TOP should be unreachable or dead at this " 3891321369Sdim "point"); 3892321369Sdim } 3893321369Sdim continue; 3894321369Sdim } 3895311116Sdim 3896321369Sdim assert(CC->getLeader() && "We should have had a leader"); 3897311116Sdim // If this is a leader that is always available, and it's a 3898311116Sdim // constant or has no equivalences, just replace everything with 3899311116Sdim // it. We then update the congruence class with whatever members 3900311116Sdim // are left. 3901321369Sdim Value *Leader = 3902321369Sdim CC->getStoredValue() ? CC->getStoredValue() : CC->getLeader(); 3903321369Sdim if (alwaysAvailable(Leader)) { 3904321369Sdim CongruenceClass::MemberSet MembersLeft; 3905321369Sdim for (auto M : *CC) { 3906311116Sdim Value *Member = M; 3907311116Sdim // Void things have no uses we can replace. 3908321369Sdim if (Member == Leader || !isa<Instruction>(Member) || 3909321369Sdim Member->getType()->isVoidTy()) { 3910311116Sdim MembersLeft.insert(Member); 3911311116Sdim continue; 3912311116Sdim } 3913341825Sdim LLVM_DEBUG(dbgs() << "Found replacement " << *(Leader) << " for " 3914341825Sdim << *Member << "\n"); 3915321369Sdim auto *I = cast<Instruction>(Member); 3916321369Sdim assert(Leader != I && "About to accidentally remove our leader"); 3917321369Sdim replaceInstruction(I, Leader); 3918321369Sdim AnythingReplaced = true; 3919311116Sdim } 3920321369Sdim CC->swap(MembersLeft); 3921311116Sdim } else { 3922311116Sdim // If this is a singleton, we can skip it. 3923327952Sdim if (CC->size() != 1 || RealToTemp.count(Leader)) { 3924311116Sdim // This is a stack because equality replacement/etc may place 3925311116Sdim // constants in the middle of the member list, and we want to use 3926311116Sdim // those constant values in preference to the current leader, over 3927311116Sdim // the scope of those constants. 3928311116Sdim ValueDFSStack EliminationStack; 3929311116Sdim 3930311116Sdim // Convert the members to DFS ordered sets and then merge them. 3931311833Sdim SmallVector<ValueDFS, 8> DFSOrderedSet; 3932321369Sdim convertClassToDFSOrdered(*CC, DFSOrderedSet, UseCounts, ProbablyDead); 3933311116Sdim 3934311116Sdim // Sort the whole thing. 3935344779Sdim llvm::sort(DFSOrderedSet); 3936311833Sdim for (auto &VD : DFSOrderedSet) { 3937311833Sdim int MemberDFSIn = VD.DFSIn; 3938311833Sdim int MemberDFSOut = VD.DFSOut; 3939321369Sdim Value *Def = VD.Def.getPointer(); 3940321369Sdim bool FromStore = VD.Def.getInt(); 3941321369Sdim Use *U = VD.U; 3942321369Sdim // We ignore void things because we can't get a value from them. 3943321369Sdim if (Def && Def->getType()->isVoidTy()) 3944321369Sdim continue; 3945321369Sdim auto *DefInst = dyn_cast_or_null<Instruction>(Def); 3946321369Sdim if (DefInst && AllTempInstructions.count(DefInst)) { 3947321369Sdim auto *PN = cast<PHINode>(DefInst); 3948311116Sdim 3949321369Sdim // If this is a value phi and that's the expression we used, insert 3950321369Sdim // it into the program 3951321369Sdim // remove from temp instruction list. 3952321369Sdim AllTempInstructions.erase(PN); 3953321369Sdim auto *DefBlock = getBlockForValue(Def); 3954341825Sdim LLVM_DEBUG(dbgs() << "Inserting fully real phi of ops" << *Def 3955341825Sdim << " into block " 3956341825Sdim << getBlockName(getBlockForValue(Def)) << "\n"); 3957321369Sdim PN->insertBefore(&DefBlock->front()); 3958321369Sdim Def = PN; 3959321369Sdim NumGVNPHIOfOpsEliminations++; 3960311833Sdim } 3961311116Sdim 3962311116Sdim if (EliminationStack.empty()) { 3963341825Sdim LLVM_DEBUG(dbgs() << "Elimination Stack is empty\n"); 3964311116Sdim } else { 3965341825Sdim LLVM_DEBUG(dbgs() << "Elimination Stack Top DFS numbers are (" 3966341825Sdim << EliminationStack.dfs_back().first << "," 3967341825Sdim << EliminationStack.dfs_back().second << ")\n"); 3968311116Sdim } 3969311116Sdim 3970341825Sdim LLVM_DEBUG(dbgs() << "Current DFS numbers are (" << MemberDFSIn << "," 3971341825Sdim << MemberDFSOut << ")\n"); 3972311116Sdim // First, we see if we are out of scope or empty. If so, 3973311116Sdim // and there equivalences, we try to replace the top of 3974311116Sdim // stack with equivalences (if it's on the stack, it must 3975311116Sdim // not have been eliminated yet). 3976311116Sdim // Then we synchronize to our current scope, by 3977311116Sdim // popping until we are back within a DFS scope that 3978311116Sdim // dominates the current member. 3979311116Sdim // Then, what happens depends on a few factors 3980311116Sdim // If the stack is now empty, we need to push 3981311116Sdim // If we have a constant or a local equivalence we want to 3982311116Sdim // start using, we also push. 3983311116Sdim // Otherwise, we walk along, processing members who are 3984311116Sdim // dominated by this scope, and eliminate them. 3985321369Sdim bool ShouldPush = Def && EliminationStack.empty(); 3986311116Sdim bool OutOfScope = 3987311116Sdim !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut); 3988311116Sdim 3989311116Sdim if (OutOfScope || ShouldPush) { 3990311116Sdim // Sync to our current scope. 3991311116Sdim EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut); 3992321369Sdim bool ShouldPush = Def && EliminationStack.empty(); 3993311116Sdim if (ShouldPush) { 3994321369Sdim EliminationStack.push_back(Def, MemberDFSIn, MemberDFSOut); 3995311116Sdim } 3996311116Sdim } 3997311116Sdim 3998321369Sdim // Skip the Def's, we only want to eliminate on their uses. But mark 3999321369Sdim // dominated defs as dead. 4000321369Sdim if (Def) { 4001321369Sdim // For anything in this case, what and how we value number 4002321369Sdim // guarantees that any side-effets that would have occurred (ie 4003321369Sdim // throwing, etc) can be proven to either still occur (because it's 4004321369Sdim // dominated by something that has the same side-effects), or never 4005321369Sdim // occur. Otherwise, we would not have been able to prove it value 4006321369Sdim // equivalent to something else. For these things, we can just mark 4007321369Sdim // it all dead. Note that this is different from the "ProbablyDead" 4008321369Sdim // set, which may not be dominated by anything, and thus, are only 4009321369Sdim // easy to prove dead if they are also side-effect free. Note that 4010321369Sdim // because stores are put in terms of the stored value, we skip 4011321369Sdim // stored values here. If the stored value is really dead, it will 4012321369Sdim // still be marked for deletion when we process it in its own class. 4013321369Sdim if (!EliminationStack.empty() && Def != EliminationStack.back() && 4014321369Sdim isa<Instruction>(Def) && !FromStore) 4015321369Sdim markInstructionForDeletion(cast<Instruction>(Def)); 4016321369Sdim continue; 4017321369Sdim } 4018321369Sdim // At this point, we know it is a Use we are trying to possibly 4019321369Sdim // replace. 4020321369Sdim 4021321369Sdim assert(isa<Instruction>(U->get()) && 4022321369Sdim "Current def should have been an instruction"); 4023321369Sdim assert(isa<Instruction>(U->getUser()) && 4024321369Sdim "Current user should have been an instruction"); 4025321369Sdim 4026321369Sdim // If the thing we are replacing into is already marked to be dead, 4027321369Sdim // this use is dead. Note that this is true regardless of whether 4028321369Sdim // we have anything dominating the use or not. We do this here 4029321369Sdim // because we are already walking all the uses anyway. 4030321369Sdim Instruction *InstUse = cast<Instruction>(U->getUser()); 4031321369Sdim if (InstructionsToErase.count(InstUse)) { 4032321369Sdim auto &UseCount = UseCounts[U->get()]; 4033321369Sdim if (--UseCount == 0) { 4034321369Sdim ProbablyDead.insert(cast<Instruction>(U->get())); 4035321369Sdim } 4036321369Sdim } 4037321369Sdim 4038311116Sdim // If we get to this point, and the stack is empty we must have a use 4039321369Sdim // with nothing we can use to eliminate this use, so just skip it. 4040311116Sdim if (EliminationStack.empty()) 4041311116Sdim continue; 4042311116Sdim 4043321369Sdim Value *DominatingLeader = EliminationStack.back(); 4044311116Sdim 4045321369Sdim auto *II = dyn_cast<IntrinsicInst>(DominatingLeader); 4046341825Sdim bool isSSACopy = II && II->getIntrinsicID() == Intrinsic::ssa_copy; 4047341825Sdim if (isSSACopy) 4048321369Sdim DominatingLeader = II->getOperand(0); 4049321369Sdim 4050311833Sdim // Don't replace our existing users with ourselves. 4051321369Sdim if (U->get() == DominatingLeader) 4052311116Sdim continue; 4053341825Sdim LLVM_DEBUG(dbgs() 4054341825Sdim << "Found replacement " << *DominatingLeader << " for " 4055341825Sdim << *U->get() << " in " << *(U->getUser()) << "\n"); 4056311116Sdim 4057311116Sdim // If we replaced something in an instruction, handle the patching of 4058321369Sdim // metadata. Skip this if we are replacing predicateinfo with its 4059321369Sdim // original operand, as we already know we can just drop it. 4060321369Sdim auto *ReplacedInst = cast<Instruction>(U->get()); 4061321369Sdim auto *PI = PredInfo->getPredicateInfoFor(ReplacedInst); 4062321369Sdim if (!PI || DominatingLeader != PI->OriginalOp) 4063321369Sdim patchReplacementInstruction(ReplacedInst, DominatingLeader); 4064321369Sdim U->set(DominatingLeader); 4065321369Sdim // This is now a use of the dominating leader, which means if the 4066321369Sdim // dominating leader was dead, it's now live! 4067321369Sdim auto &LeaderUseCount = UseCounts[DominatingLeader]; 4068321369Sdim // It's about to be alive again. 4069321369Sdim if (LeaderUseCount == 0 && isa<Instruction>(DominatingLeader)) 4070321369Sdim ProbablyDead.erase(cast<Instruction>(DominatingLeader)); 4071344779Sdim // For copy instructions, we use their operand as a leader, 4072344779Sdim // which means we remove a user of the copy and it may become dead. 4073344779Sdim if (isSSACopy) { 4074344779Sdim unsigned &IIUseCount = UseCounts[II]; 4075344779Sdim if (--IIUseCount == 0) 4076344779Sdim ProbablyDead.insert(II); 4077344779Sdim } 4078321369Sdim ++LeaderUseCount; 4079311116Sdim AnythingReplaced = true; 4080311116Sdim } 4081311116Sdim } 4082311116Sdim } 4083311116Sdim 4084321369Sdim // At this point, anything still in the ProbablyDead set is actually dead if 4085321369Sdim // would be trivially dead. 4086321369Sdim for (auto *I : ProbablyDead) 4087321369Sdim if (wouldInstructionBeTriviallyDead(I)) 4088321369Sdim markInstructionForDeletion(I); 4089321369Sdim 4090311116Sdim // Cleanup the congruence class. 4091321369Sdim CongruenceClass::MemberSet MembersLeft; 4092321369Sdim for (auto *Member : *CC) 4093321369Sdim if (!isa<Instruction>(Member) || 4094321369Sdim !InstructionsToErase.count(cast<Instruction>(Member))) 4095311116Sdim MembersLeft.insert(Member); 4096321369Sdim CC->swap(MembersLeft); 4097311116Sdim 4098321369Sdim // If we have possible dead stores to look at, try to eliminate them. 4099321369Sdim if (CC->getStoreCount() > 0) { 4100321369Sdim convertClassToLoadsAndStores(*CC, PossibleDeadStores); 4101344779Sdim llvm::sort(PossibleDeadStores); 4102321369Sdim ValueDFSStack EliminationStack; 4103321369Sdim for (auto &VD : PossibleDeadStores) { 4104321369Sdim int MemberDFSIn = VD.DFSIn; 4105321369Sdim int MemberDFSOut = VD.DFSOut; 4106321369Sdim Instruction *Member = cast<Instruction>(VD.Def.getPointer()); 4107321369Sdim if (EliminationStack.empty() || 4108321369Sdim !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut)) { 4109321369Sdim // Sync to our current scope. 4110321369Sdim EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut); 4111321369Sdim if (EliminationStack.empty()) { 4112321369Sdim EliminationStack.push_back(Member, MemberDFSIn, MemberDFSOut); 4113321369Sdim continue; 4114321369Sdim } 4115321369Sdim } 4116321369Sdim // We already did load elimination, so nothing to do here. 4117321369Sdim if (isa<LoadInst>(Member)) 4118311116Sdim continue; 4119321369Sdim assert(!EliminationStack.empty()); 4120321369Sdim Instruction *Leader = cast<Instruction>(EliminationStack.back()); 4121321369Sdim (void)Leader; 4122321369Sdim assert(DT->dominates(Leader->getParent(), Member->getParent())); 4123321369Sdim // Member is dominater by Leader, and thus dead 4124341825Sdim LLVM_DEBUG(dbgs() << "Marking dead store " << *Member 4125341825Sdim << " that is dominated by " << *Leader << "\n"); 4126321369Sdim markInstructionForDeletion(Member); 4127321369Sdim CC->erase(Member); 4128321369Sdim ++NumGVNDeadStores; 4129311116Sdim } 4130311116Sdim } 4131311116Sdim } 4132311116Sdim return AnythingReplaced; 4133311116Sdim} 4134321369Sdim 4135321369Sdim// This function provides global ranking of operations so that we can place them 4136321369Sdim// in a canonical order. Note that rank alone is not necessarily enough for a 4137321369Sdim// complete ordering, as constants all have the same rank. However, generally, 4138321369Sdim// we will simplify an operation with all constants so that it doesn't matter 4139321369Sdim// what order they appear in. 4140321369Sdimunsigned int NewGVN::getRank(const Value *V) const { 4141321369Sdim // Prefer constants to undef to anything else 4142321369Sdim // Undef is a constant, have to check it first. 4143321369Sdim // Prefer smaller constants to constantexprs 4144321369Sdim if (isa<ConstantExpr>(V)) 4145321369Sdim return 2; 4146321369Sdim if (isa<UndefValue>(V)) 4147321369Sdim return 1; 4148321369Sdim if (isa<Constant>(V)) 4149321369Sdim return 0; 4150321369Sdim else if (auto *A = dyn_cast<Argument>(V)) 4151321369Sdim return 3 + A->getArgNo(); 4152321369Sdim 4153321369Sdim // Need to shift the instruction DFS by number of arguments + 3 to account for 4154321369Sdim // the constant and argument ranking above. 4155321369Sdim unsigned Result = InstrToDFSNum(V); 4156321369Sdim if (Result > 0) 4157321369Sdim return 4 + NumFuncArgs + Result; 4158321369Sdim // Unreachable or something else, just return a really large number. 4159321369Sdim return ~0; 4160321369Sdim} 4161321369Sdim 4162321369Sdim// This is a function that says whether two commutative operations should 4163321369Sdim// have their order swapped when canonicalizing. 4164321369Sdimbool NewGVN::shouldSwapOperands(const Value *A, const Value *B) const { 4165321369Sdim // Because we only care about a total ordering, and don't rewrite expressions 4166321369Sdim // in this order, we order by rank, which will give a strict weak ordering to 4167321369Sdim // everything but constants, and then we order by pointer address. 4168321369Sdim return std::make_pair(getRank(A), A) > std::make_pair(getRank(B), B); 4169321369Sdim} 4170321369Sdim 4171321369Sdimnamespace { 4172327952Sdim 4173321369Sdimclass NewGVNLegacyPass : public FunctionPass { 4174321369Sdimpublic: 4175327952Sdim // Pass identification, replacement for typeid. 4176327952Sdim static char ID; 4177327952Sdim 4178321369Sdim NewGVNLegacyPass() : FunctionPass(ID) { 4179321369Sdim initializeNewGVNLegacyPassPass(*PassRegistry::getPassRegistry()); 4180321369Sdim } 4181327952Sdim 4182321369Sdim bool runOnFunction(Function &F) override; 4183321369Sdim 4184321369Sdimprivate: 4185321369Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 4186321369Sdim AU.addRequired<AssumptionCacheTracker>(); 4187321369Sdim AU.addRequired<DominatorTreeWrapperPass>(); 4188321369Sdim AU.addRequired<TargetLibraryInfoWrapperPass>(); 4189321369Sdim AU.addRequired<MemorySSAWrapperPass>(); 4190321369Sdim AU.addRequired<AAResultsWrapperPass>(); 4191321369Sdim AU.addPreserved<DominatorTreeWrapperPass>(); 4192321369Sdim AU.addPreserved<GlobalsAAWrapperPass>(); 4193321369Sdim } 4194321369Sdim}; 4195321369Sdim 4196327952Sdim} // end anonymous namespace 4197327952Sdim 4198321369Sdimbool NewGVNLegacyPass::runOnFunction(Function &F) { 4199321369Sdim if (skipFunction(F)) 4200321369Sdim return false; 4201321369Sdim return NewGVN(F, &getAnalysis<DominatorTreeWrapperPass>().getDomTree(), 4202321369Sdim &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F), 4203360784Sdim &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F), 4204321369Sdim &getAnalysis<AAResultsWrapperPass>().getAAResults(), 4205321369Sdim &getAnalysis<MemorySSAWrapperPass>().getMSSA(), 4206321369Sdim F.getParent()->getDataLayout()) 4207321369Sdim .runGVN(); 4208321369Sdim} 4209321369Sdim 4210327952Sdimchar NewGVNLegacyPass::ID = 0; 4211327952Sdim 4212321369SdimINITIALIZE_PASS_BEGIN(NewGVNLegacyPass, "newgvn", "Global Value Numbering", 4213321369Sdim false, false) 4214321369SdimINITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 4215321369SdimINITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass) 4216321369SdimINITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 4217321369SdimINITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 4218321369SdimINITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 4219321369SdimINITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) 4220321369SdimINITIALIZE_PASS_END(NewGVNLegacyPass, "newgvn", "Global Value Numbering", false, 4221321369Sdim false) 4222321369Sdim 4223321369Sdim// createGVNPass - The public interface to this file. 4224321369SdimFunctionPass *llvm::createNewGVNPass() { return new NewGVNLegacyPass(); } 4225321369Sdim 4226321369SdimPreservedAnalyses NewGVNPass::run(Function &F, AnalysisManager<Function> &AM) { 4227321369Sdim // Apparently the order in which we get these results matter for 4228321369Sdim // the old GVN (see Chandler's comment in GVN.cpp). I'll keep 4229321369Sdim // the same order here, just in case. 4230321369Sdim auto &AC = AM.getResult<AssumptionAnalysis>(F); 4231321369Sdim auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 4232321369Sdim auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); 4233321369Sdim auto &AA = AM.getResult<AAManager>(F); 4234321369Sdim auto &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA(); 4235321369Sdim bool Changed = 4236321369Sdim NewGVN(F, &DT, &AC, &TLI, &AA, &MSSA, F.getParent()->getDataLayout()) 4237321369Sdim .runGVN(); 4238321369Sdim if (!Changed) 4239321369Sdim return PreservedAnalyses::all(); 4240321369Sdim PreservedAnalyses PA; 4241321369Sdim PA.preserve<DominatorTreeAnalysis>(); 4242321369Sdim PA.preserve<GlobalsAA>(); 4243321369Sdim return PA; 4244321369Sdim} 4245