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