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