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