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