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