Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 1 | //===- CFLAliasAnalysis.cpp - CFL-Based Alias Analysis Implementation ------==// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file implements a CFL-based context-insensitive alias analysis |
| 11 | // algorithm. It does not depend on types. The algorithm is a mixture of the one |
| 12 | // described in "Demand-driven alias analysis for C" by Xin Zheng and Radu |
| 13 | // Rugina, and "Fast algorithms for Dyck-CFL-reachability with applications to |
| 14 | // Alias Analysis" by Zhang Q, Lyu M R, Yuan H, and Su Z. -- to summarize the |
| 15 | // papers, we build a graph of the uses of a variable, where each node is a |
| 16 | // memory location, and each edge is an action that happened on that memory |
Chad Rosier | 38c6ad2 | 2015-06-19 17:32:57 +0000 | [diff] [blame] | 17 | // location. The "actions" can be one of Dereference, Reference, or Assign. |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 18 | // |
| 19 | // Two variables are considered as aliasing iff you can reach one value's node |
| 20 | // from the other value's node and the language formed by concatenating all of |
| 21 | // the edge labels (actions) conforms to a context-free grammar. |
| 22 | // |
| 23 | // Because this algorithm requires a graph search on each query, we execute the |
| 24 | // algorithm outlined in "Fast algorithms..." (mentioned above) |
| 25 | // in order to transform the graph into sets of variables that may alias in |
George Burgess IV | 77351ba3 | 2016-01-28 00:54:01 +0000 | [diff] [blame] | 26 | // ~nlogn time (n = number of variables), which makes queries take constant |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 27 | // time. |
| 28 | //===----------------------------------------------------------------------===// |
| 29 | |
George Burgess IV | 77351ba3 | 2016-01-28 00:54:01 +0000 | [diff] [blame] | 30 | // N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and |
| 31 | // CFLAA is interprocedural. This is *technically* A Bad Thing, because |
| 32 | // FunctionPasses are only allowed to inspect the Function that they're being |
| 33 | // run on. Realistically, this likely isn't a problem until we allow |
| 34 | // FunctionPasses to run concurrently. |
| 35 | |
Chandler Carruth | 8b046a4 | 2015-08-14 02:42:20 +0000 | [diff] [blame] | 36 | #include "llvm/Analysis/CFLAliasAnalysis.h" |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 37 | #include "StratifiedSets.h" |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 38 | #include "llvm/ADT/BitVector.h" |
| 39 | #include "llvm/ADT/DenseMap.h" |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 40 | #include "llvm/ADT/None.h" |
Chandler Carruth | d990388 | 2015-01-14 11:23:27 +0000 | [diff] [blame] | 41 | #include "llvm/ADT/Optional.h" |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 42 | #include "llvm/IR/Constants.h" |
| 43 | #include "llvm/IR/Function.h" |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 44 | #include "llvm/IR/InstVisitor.h" |
Chandler Carruth | d990388 | 2015-01-14 11:23:27 +0000 | [diff] [blame] | 45 | #include "llvm/IR/Instructions.h" |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 46 | #include "llvm/Pass.h" |
| 47 | #include "llvm/Support/Allocator.h" |
Hal Finkel | 7d7087c | 2014-09-02 22:13:00 +0000 | [diff] [blame] | 48 | #include "llvm/Support/Compiler.h" |
George Burgess IV | 33305e7 | 2015-02-12 03:07:07 +0000 | [diff] [blame] | 49 | #include "llvm/Support/Debug.h" |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 50 | #include "llvm/Support/ErrorHandling.h" |
Benjamin Kramer | 799003b | 2015-03-23 19:32:43 +0000 | [diff] [blame] | 51 | #include "llvm/Support/raw_ostream.h" |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 52 | #include <algorithm> |
| 53 | #include <cassert> |
Benjamin Kramer | 799003b | 2015-03-23 19:32:43 +0000 | [diff] [blame] | 54 | #include <memory> |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 55 | #include <tuple> |
| 56 | |
| 57 | using namespace llvm; |
| 58 | |
George Burgess IV | 33305e7 | 2015-02-12 03:07:07 +0000 | [diff] [blame] | 59 | #define DEBUG_TYPE "cfl-aa" |
| 60 | |
Chandler Carruth | 12884f7 | 2016-03-02 15:56:53 +0000 | [diff] [blame] | 61 | CFLAAResult::CFLAAResult() : AAResultBase() {} |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 62 | CFLAAResult::CFLAAResult(CFLAAResult &&Arg) : AAResultBase(std::move(Arg)) {} |
Chandler Carruth | 342c671 | 2016-02-20 03:52:02 +0000 | [diff] [blame] | 63 | CFLAAResult::~CFLAAResult() {} |
Chandler Carruth | 8b046a4 | 2015-08-14 02:42:20 +0000 | [diff] [blame] | 64 | |
| 65 | // \brief Information we have about a function and would like to keep around |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 66 | struct CFLAAResult::FunctionInfo { |
Chandler Carruth | 8b046a4 | 2015-08-14 02:42:20 +0000 | [diff] [blame] | 67 | StratifiedSets<Value *> Sets; |
| 68 | // Lots of functions have < 4 returns. Adjust as necessary. |
| 69 | SmallVector<Value *, 4> ReturnedValues; |
| 70 | |
| 71 | FunctionInfo(StratifiedSets<Value *> &&S, SmallVector<Value *, 4> &&RV) |
| 72 | : Sets(std::move(S)), ReturnedValues(std::move(RV)) {} |
| 73 | }; |
| 74 | |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 75 | // Try to go from a Value* to a Function*. Never returns nullptr. |
| 76 | static Optional<Function *> parentFunctionOfValue(Value *); |
| 77 | |
| 78 | // Returns possible functions called by the Inst* into the given |
| 79 | // SmallVectorImpl. Returns true if targets found, false otherwise. |
| 80 | // This is templated because InvokeInst/CallInst give us the same |
| 81 | // set of functions that we care about, and I don't like repeating |
| 82 | // myself. |
| 83 | template <typename Inst> |
| 84 | static bool getPossibleTargets(Inst *, SmallVectorImpl<Function *> &); |
| 85 | |
| 86 | // Some instructions need to have their users tracked. Instructions like |
| 87 | // `add` require you to get the users of the Instruction* itself, other |
| 88 | // instructions like `store` require you to get the users of the first |
| 89 | // operand. This function gets the "proper" value to track for each |
| 90 | // type of instruction we support. |
| 91 | static Optional<Value *> getTargetValue(Instruction *); |
| 92 | |
| 93 | // There are certain instructions (i.e. FenceInst, etc.) that we ignore. |
| 94 | // This notes that we should ignore those. |
| 95 | static bool hasUsefulEdges(Instruction *); |
| 96 | |
Hal Finkel | 1ae325f | 2014-09-02 23:50:01 +0000 | [diff] [blame] | 97 | const StratifiedIndex StratifiedLink::SetSentinel = |
George Burgess IV | 11d509d | 2015-03-15 00:52:21 +0000 | [diff] [blame] | 98 | std::numeric_limits<StratifiedIndex>::max(); |
Hal Finkel | 1ae325f | 2014-09-02 23:50:01 +0000 | [diff] [blame] | 99 | |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 100 | namespace { |
| 101 | // StratifiedInfo Attribute things. |
| 102 | typedef unsigned StratifiedAttr; |
Hal Finkel | 7d7087c | 2014-09-02 22:13:00 +0000 | [diff] [blame] | 103 | LLVM_CONSTEXPR unsigned MaxStratifiedAttrIndex = NumStratifiedAttrs; |
| 104 | LLVM_CONSTEXPR unsigned AttrAllIndex = 0; |
| 105 | LLVM_CONSTEXPR unsigned AttrGlobalIndex = 1; |
George Burgess IV | b54a8d62 | 2015-03-10 02:40:06 +0000 | [diff] [blame] | 106 | LLVM_CONSTEXPR unsigned AttrUnknownIndex = 2; |
| 107 | LLVM_CONSTEXPR unsigned AttrFirstArgIndex = 3; |
Hal Finkel | 7d7087c | 2014-09-02 22:13:00 +0000 | [diff] [blame] | 108 | LLVM_CONSTEXPR unsigned AttrLastArgIndex = MaxStratifiedAttrIndex; |
| 109 | LLVM_CONSTEXPR unsigned AttrMaxNumArgs = AttrLastArgIndex - AttrFirstArgIndex; |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 110 | |
Hal Finkel | 7d7087c | 2014-09-02 22:13:00 +0000 | [diff] [blame] | 111 | LLVM_CONSTEXPR StratifiedAttr AttrNone = 0; |
George Burgess IV | b54a8d62 | 2015-03-10 02:40:06 +0000 | [diff] [blame] | 112 | LLVM_CONSTEXPR StratifiedAttr AttrUnknown = 1 << AttrUnknownIndex; |
Hal Finkel | 7d7087c | 2014-09-02 22:13:00 +0000 | [diff] [blame] | 113 | LLVM_CONSTEXPR StratifiedAttr AttrAll = ~AttrNone; |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 114 | |
| 115 | // \brief StratifiedSets call for knowledge of "direction", so this is how we |
| 116 | // represent that locally. |
| 117 | enum class Level { Same, Above, Below }; |
| 118 | |
| 119 | // \brief Edges can be one of four "weights" -- each weight must have an inverse |
| 120 | // weight (Assign has Assign; Reference has Dereference). |
| 121 | enum class EdgeType { |
| 122 | // The weight assigned when assigning from or to a value. For example, in: |
| 123 | // %b = getelementptr %a, 0 |
| 124 | // ...The relationships are %b assign %a, and %a assign %b. This used to be |
| 125 | // two edges, but having a distinction bought us nothing. |
| 126 | Assign, |
| 127 | |
| 128 | // The edge used when we have an edge going from some handle to a Value. |
| 129 | // Examples of this include: |
| 130 | // %b = load %a (%b Dereference %a) |
| 131 | // %b = extractelement %a, 0 (%a Dereference %b) |
| 132 | Dereference, |
| 133 | |
| 134 | // The edge used when our edge goes from a value to a handle that may have |
| 135 | // contained it at some point. Examples: |
| 136 | // %b = load %a (%a Reference %b) |
| 137 | // %b = extractelement %a, 0 (%b Reference %a) |
| 138 | Reference |
| 139 | }; |
| 140 | |
| 141 | // \brief Encodes the notion of a "use" |
| 142 | struct Edge { |
| 143 | // \brief Which value the edge is coming from |
| 144 | Value *From; |
| 145 | |
| 146 | // \brief Which value the edge is pointing to |
| 147 | Value *To; |
| 148 | |
| 149 | // \brief Edge weight |
| 150 | EdgeType Weight; |
| 151 | |
| 152 | // \brief Whether we aliased any external values along the way that may be |
| 153 | // invisible to the analysis (i.e. landingpad for exceptions, calls for |
| 154 | // interprocedural analysis, etc.) |
| 155 | StratifiedAttrs AdditionalAttrs; |
| 156 | |
| 157 | Edge(Value *From, Value *To, EdgeType W, StratifiedAttrs A) |
| 158 | : From(From), To(To), Weight(W), AdditionalAttrs(A) {} |
| 159 | }; |
| 160 | |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 161 | // \brief Gets the edges our graph should have, based on an Instruction* |
| 162 | class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> { |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 163 | CFLAAResult &AA; |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 164 | SmallVectorImpl<Edge> &Output; |
| 165 | |
| 166 | public: |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 167 | GetEdgesVisitor(CFLAAResult &AA, SmallVectorImpl<Edge> &Output) |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 168 | : AA(AA), Output(Output) {} |
| 169 | |
| 170 | void visitInstruction(Instruction &) { |
| 171 | llvm_unreachable("Unsupported instruction encountered"); |
| 172 | } |
| 173 | |
George Burgess IV | b54a8d62 | 2015-03-10 02:40:06 +0000 | [diff] [blame] | 174 | void visitPtrToIntInst(PtrToIntInst &Inst) { |
| 175 | auto *Ptr = Inst.getOperand(0); |
| 176 | Output.push_back(Edge(Ptr, Ptr, EdgeType::Assign, AttrUnknown)); |
| 177 | } |
| 178 | |
| 179 | void visitIntToPtrInst(IntToPtrInst &Inst) { |
| 180 | auto *Ptr = &Inst; |
| 181 | Output.push_back(Edge(Ptr, Ptr, EdgeType::Assign, AttrUnknown)); |
| 182 | } |
| 183 | |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 184 | void visitCastInst(CastInst &Inst) { |
George Burgess IV | 11d509d | 2015-03-15 00:52:21 +0000 | [diff] [blame] | 185 | Output.push_back( |
| 186 | Edge(&Inst, Inst.getOperand(0), EdgeType::Assign, AttrNone)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 187 | } |
| 188 | |
| 189 | void visitBinaryOperator(BinaryOperator &Inst) { |
| 190 | auto *Op1 = Inst.getOperand(0); |
| 191 | auto *Op2 = Inst.getOperand(1); |
Hal Finkel | 8d1590d | 2014-09-02 22:52:30 +0000 | [diff] [blame] | 192 | Output.push_back(Edge(&Inst, Op1, EdgeType::Assign, AttrNone)); |
| 193 | Output.push_back(Edge(&Inst, Op2, EdgeType::Assign, AttrNone)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 194 | } |
| 195 | |
| 196 | void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) { |
| 197 | auto *Ptr = Inst.getPointerOperand(); |
| 198 | auto *Val = Inst.getNewValOperand(); |
Hal Finkel | 8d1590d | 2014-09-02 22:52:30 +0000 | [diff] [blame] | 199 | Output.push_back(Edge(Ptr, Val, EdgeType::Dereference, AttrNone)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 200 | } |
| 201 | |
| 202 | void visitAtomicRMWInst(AtomicRMWInst &Inst) { |
| 203 | auto *Ptr = Inst.getPointerOperand(); |
| 204 | auto *Val = Inst.getValOperand(); |
Hal Finkel | 8d1590d | 2014-09-02 22:52:30 +0000 | [diff] [blame] | 205 | Output.push_back(Edge(Ptr, Val, EdgeType::Dereference, AttrNone)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 206 | } |
| 207 | |
| 208 | void visitPHINode(PHINode &Inst) { |
George Burgess IV | 77351ba3 | 2016-01-28 00:54:01 +0000 | [diff] [blame] | 209 | for (Value *Val : Inst.incoming_values()) |
Hal Finkel | 8d1590d | 2014-09-02 22:52:30 +0000 | [diff] [blame] | 210 | Output.push_back(Edge(&Inst, Val, EdgeType::Assign, AttrNone)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 211 | } |
| 212 | |
| 213 | void visitGetElementPtrInst(GetElementPtrInst &Inst) { |
| 214 | auto *Op = Inst.getPointerOperand(); |
Hal Finkel | 8d1590d | 2014-09-02 22:52:30 +0000 | [diff] [blame] | 215 | Output.push_back(Edge(&Inst, Op, EdgeType::Assign, AttrNone)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 216 | for (auto I = Inst.idx_begin(), E = Inst.idx_end(); I != E; ++I) |
Hal Finkel | 8d1590d | 2014-09-02 22:52:30 +0000 | [diff] [blame] | 217 | Output.push_back(Edge(&Inst, *I, EdgeType::Assign, AttrNone)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 218 | } |
| 219 | |
| 220 | void visitSelectInst(SelectInst &Inst) { |
Daniel Berlin | 16f7a52 | 2015-01-26 17:31:17 +0000 | [diff] [blame] | 221 | // Condition is not processed here (The actual statement producing |
| 222 | // the condition result is processed elsewhere). For select, the |
| 223 | // condition is evaluated, but not loaded, stored, or assigned |
| 224 | // simply as a result of being the condition of a select. |
| 225 | |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 226 | auto *TrueVal = Inst.getTrueValue(); |
Hal Finkel | 8d1590d | 2014-09-02 22:52:30 +0000 | [diff] [blame] | 227 | Output.push_back(Edge(&Inst, TrueVal, EdgeType::Assign, AttrNone)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 228 | auto *FalseVal = Inst.getFalseValue(); |
Hal Finkel | 8d1590d | 2014-09-02 22:52:30 +0000 | [diff] [blame] | 229 | Output.push_back(Edge(&Inst, FalseVal, EdgeType::Assign, AttrNone)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 230 | } |
| 231 | |
| 232 | void visitAllocaInst(AllocaInst &) {} |
| 233 | |
| 234 | void visitLoadInst(LoadInst &Inst) { |
| 235 | auto *Ptr = Inst.getPointerOperand(); |
| 236 | auto *Val = &Inst; |
Hal Finkel | 8d1590d | 2014-09-02 22:52:30 +0000 | [diff] [blame] | 237 | Output.push_back(Edge(Val, Ptr, EdgeType::Reference, AttrNone)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 238 | } |
| 239 | |
| 240 | void visitStoreInst(StoreInst &Inst) { |
| 241 | auto *Ptr = Inst.getPointerOperand(); |
| 242 | auto *Val = Inst.getValueOperand(); |
Hal Finkel | 8d1590d | 2014-09-02 22:52:30 +0000 | [diff] [blame] | 243 | Output.push_back(Edge(Ptr, Val, EdgeType::Dereference, AttrNone)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 244 | } |
| 245 | |
Hal Finkel | db5f86a | 2014-10-14 20:51:26 +0000 | [diff] [blame] | 246 | void visitVAArgInst(VAArgInst &Inst) { |
| 247 | // We can't fully model va_arg here. For *Ptr = Inst.getOperand(0), it does |
| 248 | // two things: |
| 249 | // 1. Loads a value from *((T*)*Ptr). |
| 250 | // 2. Increments (stores to) *Ptr by some target-specific amount. |
| 251 | // For now, we'll handle this like a landingpad instruction (by placing the |
| 252 | // result in its own group, and having that group alias externals). |
| 253 | auto *Val = &Inst; |
| 254 | Output.push_back(Edge(Val, Val, EdgeType::Assign, AttrAll)); |
| 255 | } |
| 256 | |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 257 | static bool isFunctionExternal(Function *Fn) { |
| 258 | return Fn->isDeclaration() || !Fn->hasLocalLinkage(); |
| 259 | } |
| 260 | |
| 261 | // Gets whether the sets at Index1 above, below, or equal to the sets at |
| 262 | // Index2. Returns None if they are not in the same set chain. |
| 263 | static Optional<Level> getIndexRelation(const StratifiedSets<Value *> &Sets, |
| 264 | StratifiedIndex Index1, |
| 265 | StratifiedIndex Index2) { |
| 266 | if (Index1 == Index2) |
| 267 | return Level::Same; |
| 268 | |
| 269 | const auto *Current = &Sets.getLink(Index1); |
| 270 | while (Current->hasBelow()) { |
| 271 | if (Current->Below == Index2) |
| 272 | return Level::Below; |
| 273 | Current = &Sets.getLink(Current->Below); |
| 274 | } |
| 275 | |
| 276 | Current = &Sets.getLink(Index1); |
| 277 | while (Current->hasAbove()) { |
| 278 | if (Current->Above == Index2) |
| 279 | return Level::Above; |
| 280 | Current = &Sets.getLink(Current->Above); |
| 281 | } |
| 282 | |
George Burgess IV | 77351ba3 | 2016-01-28 00:54:01 +0000 | [diff] [blame] | 283 | return None; |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 284 | } |
| 285 | |
| 286 | bool |
| 287 | tryInterproceduralAnalysis(const SmallVectorImpl<Function *> &Fns, |
| 288 | Value *FuncValue, |
| 289 | const iterator_range<User::op_iterator> &Args) { |
Hal Finkel | ca616ac | 2014-09-02 23:29:48 +0000 | [diff] [blame] | 290 | const unsigned ExpectedMaxArgs = 8; |
| 291 | const unsigned MaxSupportedArgs = 50; |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 292 | assert(Fns.size() > 0); |
| 293 | |
| 294 | // I put this here to give us an upper bound on time taken by IPA. Is it |
| 295 | // really (realistically) needed? Keep in mind that we do have an n^2 algo. |
George Burgess IV | ab03af2 | 2015-03-10 02:58:15 +0000 | [diff] [blame] | 296 | if (std::distance(Args.begin(), Args.end()) > (int)MaxSupportedArgs) |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 297 | return false; |
| 298 | |
| 299 | // Exit early if we'll fail anyway |
| 300 | for (auto *Fn : Fns) { |
| 301 | if (isFunctionExternal(Fn) || Fn->isVarArg()) |
| 302 | return false; |
| 303 | auto &MaybeInfo = AA.ensureCached(Fn); |
| 304 | if (!MaybeInfo.hasValue()) |
| 305 | return false; |
| 306 | } |
| 307 | |
| 308 | SmallVector<Value *, ExpectedMaxArgs> Arguments(Args.begin(), Args.end()); |
| 309 | SmallVector<StratifiedInfo, ExpectedMaxArgs> Parameters; |
| 310 | for (auto *Fn : Fns) { |
| 311 | auto &Info = *AA.ensureCached(Fn); |
| 312 | auto &Sets = Info.Sets; |
| 313 | auto &RetVals = Info.ReturnedValues; |
| 314 | |
| 315 | Parameters.clear(); |
| 316 | for (auto &Param : Fn->args()) { |
| 317 | auto MaybeInfo = Sets.find(&Param); |
| 318 | // Did a new parameter somehow get added to the function/slip by? |
| 319 | if (!MaybeInfo.hasValue()) |
| 320 | return false; |
| 321 | Parameters.push_back(*MaybeInfo); |
| 322 | } |
| 323 | |
| 324 | // Adding an edge from argument -> return value for each parameter that |
| 325 | // may alias the return value |
| 326 | for (unsigned I = 0, E = Parameters.size(); I != E; ++I) { |
| 327 | auto &ParamInfo = Parameters[I]; |
| 328 | auto &ArgVal = Arguments[I]; |
| 329 | bool AddEdge = false; |
| 330 | StratifiedAttrs Externals; |
| 331 | for (unsigned X = 0, XE = RetVals.size(); X != XE; ++X) { |
| 332 | auto MaybeInfo = Sets.find(RetVals[X]); |
| 333 | if (!MaybeInfo.hasValue()) |
| 334 | return false; |
| 335 | |
| 336 | auto &RetInfo = *MaybeInfo; |
| 337 | auto RetAttrs = Sets.getLink(RetInfo.Index).Attrs; |
| 338 | auto ParamAttrs = Sets.getLink(ParamInfo.Index).Attrs; |
| 339 | auto MaybeRelation = |
| 340 | getIndexRelation(Sets, ParamInfo.Index, RetInfo.Index); |
| 341 | if (MaybeRelation.hasValue()) { |
| 342 | AddEdge = true; |
| 343 | Externals |= RetAttrs | ParamAttrs; |
| 344 | } |
| 345 | } |
| 346 | if (AddEdge) |
Hal Finkel | ca616ac | 2014-09-02 23:29:48 +0000 | [diff] [blame] | 347 | Output.push_back(Edge(FuncValue, ArgVal, EdgeType::Assign, |
George Burgess IV | 11d509d | 2015-03-15 00:52:21 +0000 | [diff] [blame] | 348 | StratifiedAttrs().flip())); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 349 | } |
| 350 | |
| 351 | if (Parameters.size() != Arguments.size()) |
| 352 | return false; |
| 353 | |
| 354 | // Adding edges between arguments for arguments that may end up aliasing |
| 355 | // each other. This is necessary for functions such as |
| 356 | // void foo(int** a, int** b) { *a = *b; } |
| 357 | // (Technically, the proper sets for this would be those below |
| 358 | // Arguments[I] and Arguments[X], but our algorithm will produce |
| 359 | // extremely similar, and equally correct, results either way) |
| 360 | for (unsigned I = 0, E = Arguments.size(); I != E; ++I) { |
| 361 | auto &MainVal = Arguments[I]; |
| 362 | auto &MainInfo = Parameters[I]; |
| 363 | auto &MainAttrs = Sets.getLink(MainInfo.Index).Attrs; |
| 364 | for (unsigned X = I + 1; X != E; ++X) { |
| 365 | auto &SubInfo = Parameters[X]; |
| 366 | auto &SubVal = Arguments[X]; |
| 367 | auto &SubAttrs = Sets.getLink(SubInfo.Index).Attrs; |
| 368 | auto MaybeRelation = |
| 369 | getIndexRelation(Sets, MainInfo.Index, SubInfo.Index); |
| 370 | |
| 371 | if (!MaybeRelation.hasValue()) |
| 372 | continue; |
| 373 | |
| 374 | auto NewAttrs = SubAttrs | MainAttrs; |
Hal Finkel | 8d1590d | 2014-09-02 22:52:30 +0000 | [diff] [blame] | 375 | Output.push_back(Edge(MainVal, SubVal, EdgeType::Assign, NewAttrs)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 376 | } |
| 377 | } |
| 378 | } |
| 379 | return true; |
| 380 | } |
| 381 | |
| 382 | template <typename InstT> void visitCallLikeInst(InstT &Inst) { |
George Burgess IV | 68b36e0 | 2015-08-28 00:16:18 +0000 | [diff] [blame] | 383 | // TODO: Add support for noalias args/all the other fun function attributes |
| 384 | // that we can tack on. |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 385 | SmallVector<Function *, 4> Targets; |
| 386 | if (getPossibleTargets(&Inst, Targets)) { |
| 387 | if (tryInterproceduralAnalysis(Targets, &Inst, Inst.arg_operands())) |
| 388 | return; |
| 389 | // Cleanup from interprocedural analysis |
| 390 | Output.clear(); |
| 391 | } |
| 392 | |
George Burgess IV | 68b36e0 | 2015-08-28 00:16:18 +0000 | [diff] [blame] | 393 | // Because the function is opaque, we need to note that anything |
| 394 | // could have happened to the arguments, and that the result could alias |
| 395 | // just about anything, too. |
| 396 | // The goal of the loop is in part to unify many Values into one set, so we |
| 397 | // don't care if the function is void there. |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 398 | for (Value *V : Inst.arg_operands()) |
Hal Finkel | 8d1590d | 2014-09-02 22:52:30 +0000 | [diff] [blame] | 399 | Output.push_back(Edge(&Inst, V, EdgeType::Assign, AttrAll)); |
George Burgess IV | 68b36e0 | 2015-08-28 00:16:18 +0000 | [diff] [blame] | 400 | if (Inst.getNumArgOperands() == 0 && |
| 401 | Inst.getType() != Type::getVoidTy(Inst.getContext())) |
| 402 | Output.push_back(Edge(&Inst, &Inst, EdgeType::Assign, AttrAll)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 403 | } |
| 404 | |
| 405 | void visitCallInst(CallInst &Inst) { visitCallLikeInst(Inst); } |
| 406 | |
| 407 | void visitInvokeInst(InvokeInst &Inst) { visitCallLikeInst(Inst); } |
| 408 | |
| 409 | // Because vectors/aggregates are immutable and unaddressable, |
| 410 | // there's nothing we can do to coax a value out of them, other |
| 411 | // than calling Extract{Element,Value}. We can effectively treat |
| 412 | // them as pointers to arbitrary memory locations we can store in |
| 413 | // and load from. |
| 414 | void visitExtractElementInst(ExtractElementInst &Inst) { |
| 415 | auto *Ptr = Inst.getVectorOperand(); |
| 416 | auto *Val = &Inst; |
Hal Finkel | 8d1590d | 2014-09-02 22:52:30 +0000 | [diff] [blame] | 417 | Output.push_back(Edge(Val, Ptr, EdgeType::Reference, AttrNone)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 418 | } |
| 419 | |
| 420 | void visitInsertElementInst(InsertElementInst &Inst) { |
| 421 | auto *Vec = Inst.getOperand(0); |
| 422 | auto *Val = Inst.getOperand(1); |
Hal Finkel | 8d1590d | 2014-09-02 22:52:30 +0000 | [diff] [blame] | 423 | Output.push_back(Edge(&Inst, Vec, EdgeType::Assign, AttrNone)); |
| 424 | Output.push_back(Edge(&Inst, Val, EdgeType::Dereference, AttrNone)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 425 | } |
| 426 | |
| 427 | void visitLandingPadInst(LandingPadInst &Inst) { |
| 428 | // Exceptions come from "nowhere", from our analysis' perspective. |
| 429 | // So we place the instruction its own group, noting that said group may |
| 430 | // alias externals |
Hal Finkel | 8d1590d | 2014-09-02 22:52:30 +0000 | [diff] [blame] | 431 | Output.push_back(Edge(&Inst, &Inst, EdgeType::Assign, AttrAll)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 432 | } |
| 433 | |
| 434 | void visitInsertValueInst(InsertValueInst &Inst) { |
| 435 | auto *Agg = Inst.getOperand(0); |
| 436 | auto *Val = Inst.getOperand(1); |
Hal Finkel | 8d1590d | 2014-09-02 22:52:30 +0000 | [diff] [blame] | 437 | Output.push_back(Edge(&Inst, Agg, EdgeType::Assign, AttrNone)); |
| 438 | Output.push_back(Edge(&Inst, Val, EdgeType::Dereference, AttrNone)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 439 | } |
| 440 | |
| 441 | void visitExtractValueInst(ExtractValueInst &Inst) { |
| 442 | auto *Ptr = Inst.getAggregateOperand(); |
Hal Finkel | 8d1590d | 2014-09-02 22:52:30 +0000 | [diff] [blame] | 443 | Output.push_back(Edge(&Inst, Ptr, EdgeType::Reference, AttrNone)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 444 | } |
| 445 | |
| 446 | void visitShuffleVectorInst(ShuffleVectorInst &Inst) { |
| 447 | auto *From1 = Inst.getOperand(0); |
| 448 | auto *From2 = Inst.getOperand(1); |
Hal Finkel | 8d1590d | 2014-09-02 22:52:30 +0000 | [diff] [blame] | 449 | Output.push_back(Edge(&Inst, From1, EdgeType::Assign, AttrNone)); |
| 450 | Output.push_back(Edge(&Inst, From2, EdgeType::Assign, AttrNone)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 451 | } |
Pete Cooper | 3664253 | 2015-06-12 16:13:54 +0000 | [diff] [blame] | 452 | |
| 453 | void visitConstantExpr(ConstantExpr *CE) { |
| 454 | switch (CE->getOpcode()) { |
| 455 | default: |
| 456 | llvm_unreachable("Unknown instruction type encountered!"); |
| 457 | // Build the switch statement using the Instruction.def file. |
| 458 | #define HANDLE_INST(NUM, OPCODE, CLASS) \ |
| 459 | case Instruction::OPCODE: \ |
| 460 | visit##OPCODE(*(CLASS *)CE); \ |
| 461 | break; |
| 462 | #include "llvm/IR/Instruction.def" |
| 463 | } |
| 464 | } |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 465 | }; |
| 466 | |
| 467 | // For a given instruction, we need to know which Value* to get the |
| 468 | // users of in order to build our graph. In some cases (i.e. add), |
| 469 | // we simply need the Instruction*. In other cases (i.e. store), |
| 470 | // finding the users of the Instruction* is useless; we need to find |
| 471 | // the users of the first operand. This handles determining which |
| 472 | // value to follow for us. |
| 473 | // |
| 474 | // Note: we *need* to keep this in sync with GetEdgesVisitor. Add |
| 475 | // something to GetEdgesVisitor, add it here -- remove something from |
| 476 | // GetEdgesVisitor, remove it here. |
| 477 | class GetTargetValueVisitor |
| 478 | : public InstVisitor<GetTargetValueVisitor, Value *> { |
| 479 | public: |
| 480 | Value *visitInstruction(Instruction &Inst) { return &Inst; } |
| 481 | |
| 482 | Value *visitStoreInst(StoreInst &Inst) { return Inst.getPointerOperand(); } |
| 483 | |
| 484 | Value *visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) { |
| 485 | return Inst.getPointerOperand(); |
| 486 | } |
| 487 | |
| 488 | Value *visitAtomicRMWInst(AtomicRMWInst &Inst) { |
| 489 | return Inst.getPointerOperand(); |
| 490 | } |
| 491 | |
| 492 | Value *visitInsertElementInst(InsertElementInst &Inst) { |
| 493 | return Inst.getOperand(0); |
| 494 | } |
| 495 | |
| 496 | Value *visitInsertValueInst(InsertValueInst &Inst) { |
| 497 | return Inst.getAggregateOperand(); |
| 498 | } |
| 499 | }; |
| 500 | |
| 501 | // Set building requires a weighted bidirectional graph. |
| 502 | template <typename EdgeTypeT> class WeightedBidirectionalGraph { |
| 503 | public: |
| 504 | typedef std::size_t Node; |
| 505 | |
| 506 | private: |
Hal Finkel | ca616ac | 2014-09-02 23:29:48 +0000 | [diff] [blame] | 507 | const static Node StartNode = Node(0); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 508 | |
| 509 | struct Edge { |
| 510 | EdgeTypeT Weight; |
| 511 | Node Other; |
| 512 | |
George Burgess IV | 11d509d | 2015-03-15 00:52:21 +0000 | [diff] [blame] | 513 | Edge(const EdgeTypeT &W, const Node &N) : Weight(W), Other(N) {} |
Hal Finkel | ca616ac | 2014-09-02 23:29:48 +0000 | [diff] [blame] | 514 | |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 515 | bool operator==(const Edge &E) const { |
| 516 | return Weight == E.Weight && Other == E.Other; |
| 517 | } |
| 518 | |
| 519 | bool operator!=(const Edge &E) const { return !operator==(E); } |
| 520 | }; |
| 521 | |
| 522 | struct NodeImpl { |
| 523 | std::vector<Edge> Edges; |
| 524 | }; |
| 525 | |
| 526 | std::vector<NodeImpl> NodeImpls; |
| 527 | |
| 528 | bool inbounds(Node NodeIndex) const { return NodeIndex < NodeImpls.size(); } |
| 529 | |
| 530 | const NodeImpl &getNode(Node N) const { return NodeImpls[N]; } |
| 531 | NodeImpl &getNode(Node N) { return NodeImpls[N]; } |
| 532 | |
| 533 | public: |
| 534 | // ----- Various Edge iterators for the graph ----- // |
| 535 | |
| 536 | // \brief Iterator for edges. Because this graph is bidirected, we don't |
Benjamin Kramer | df005cb | 2015-08-08 18:27:36 +0000 | [diff] [blame] | 537 | // allow modification of the edges using this iterator. Additionally, the |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 538 | // iterator becomes invalid if you add edges to or from the node you're |
| 539 | // getting the edges of. |
| 540 | struct EdgeIterator : public std::iterator<std::forward_iterator_tag, |
| 541 | std::tuple<EdgeTypeT, Node *>> { |
| 542 | EdgeIterator(const typename std::vector<Edge>::const_iterator &Iter) |
| 543 | : Current(Iter) {} |
| 544 | |
| 545 | EdgeIterator(NodeImpl &Impl) : Current(Impl.begin()) {} |
| 546 | |
| 547 | EdgeIterator &operator++() { |
| 548 | ++Current; |
| 549 | return *this; |
| 550 | } |
| 551 | |
| 552 | EdgeIterator operator++(int) { |
| 553 | EdgeIterator Copy(Current); |
| 554 | operator++(); |
| 555 | return Copy; |
| 556 | } |
| 557 | |
| 558 | std::tuple<EdgeTypeT, Node> &operator*() { |
| 559 | Store = std::make_tuple(Current->Weight, Current->Other); |
| 560 | return Store; |
| 561 | } |
| 562 | |
| 563 | bool operator==(const EdgeIterator &Other) const { |
| 564 | return Current == Other.Current; |
| 565 | } |
| 566 | |
| 567 | bool operator!=(const EdgeIterator &Other) const { |
| 568 | return !operator==(Other); |
| 569 | } |
| 570 | |
| 571 | private: |
| 572 | typename std::vector<Edge>::const_iterator Current; |
| 573 | std::tuple<EdgeTypeT, Node> Store; |
| 574 | }; |
| 575 | |
| 576 | // Wrapper for EdgeIterator with begin()/end() calls. |
| 577 | struct EdgeIterable { |
| 578 | EdgeIterable(const std::vector<Edge> &Edges) |
| 579 | : BeginIter(Edges.begin()), EndIter(Edges.end()) {} |
| 580 | |
| 581 | EdgeIterator begin() { return EdgeIterator(BeginIter); } |
| 582 | |
| 583 | EdgeIterator end() { return EdgeIterator(EndIter); } |
| 584 | |
| 585 | private: |
| 586 | typename std::vector<Edge>::const_iterator BeginIter; |
| 587 | typename std::vector<Edge>::const_iterator EndIter; |
| 588 | }; |
| 589 | |
| 590 | // ----- Actual graph-related things ----- // |
| 591 | |
Hal Finkel | ca616ac | 2014-09-02 23:29:48 +0000 | [diff] [blame] | 592 | WeightedBidirectionalGraph() {} |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 593 | |
| 594 | WeightedBidirectionalGraph(WeightedBidirectionalGraph<EdgeTypeT> &&Other) |
| 595 | : NodeImpls(std::move(Other.NodeImpls)) {} |
| 596 | |
| 597 | WeightedBidirectionalGraph<EdgeTypeT> & |
| 598 | operator=(WeightedBidirectionalGraph<EdgeTypeT> &&Other) { |
| 599 | NodeImpls = std::move(Other.NodeImpls); |
| 600 | return *this; |
| 601 | } |
| 602 | |
| 603 | Node addNode() { |
| 604 | auto Index = NodeImpls.size(); |
| 605 | auto NewNode = Node(Index); |
| 606 | NodeImpls.push_back(NodeImpl()); |
| 607 | return NewNode; |
| 608 | } |
| 609 | |
| 610 | void addEdge(Node From, Node To, const EdgeTypeT &Weight, |
| 611 | const EdgeTypeT &ReverseWeight) { |
| 612 | assert(inbounds(From)); |
| 613 | assert(inbounds(To)); |
| 614 | auto &FromNode = getNode(From); |
| 615 | auto &ToNode = getNode(To); |
Hal Finkel | ca616ac | 2014-09-02 23:29:48 +0000 | [diff] [blame] | 616 | FromNode.Edges.push_back(Edge(Weight, To)); |
| 617 | ToNode.Edges.push_back(Edge(ReverseWeight, From)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 618 | } |
| 619 | |
| 620 | EdgeIterable edgesFor(const Node &N) const { |
| 621 | const auto &Node = getNode(N); |
| 622 | return EdgeIterable(Node.Edges); |
| 623 | } |
| 624 | |
| 625 | bool empty() const { return NodeImpls.empty(); } |
| 626 | std::size_t size() const { return NodeImpls.size(); } |
| 627 | |
| 628 | // \brief Gets an arbitrary node in the graph as a starting point for |
| 629 | // traversal. |
| 630 | Node getEntryNode() { |
| 631 | assert(inbounds(StartNode)); |
| 632 | return StartNode; |
| 633 | } |
| 634 | }; |
| 635 | |
| 636 | typedef WeightedBidirectionalGraph<std::pair<EdgeType, StratifiedAttrs>> GraphT; |
| 637 | typedef DenseMap<Value *, GraphT::Node> NodeMapT; |
Alexander Kornienko | f00654e | 2015-06-23 09:49:53 +0000 | [diff] [blame] | 638 | } |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 639 | |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 640 | //===----------------------------------------------------------------------===// |
| 641 | // Function declarations that require types defined in the namespace above |
| 642 | //===----------------------------------------------------------------------===// |
| 643 | |
| 644 | // Given an argument number, returns the appropriate Attr index to set. |
| 645 | static StratifiedAttr argNumberToAttrIndex(StratifiedAttr); |
| 646 | |
| 647 | // Given a Value, potentially return which AttrIndex it maps to. |
| 648 | static Optional<StratifiedAttr> valueToAttrIndex(Value *Val); |
| 649 | |
| 650 | // Gets the inverse of a given EdgeType. |
| 651 | static EdgeType flipWeight(EdgeType); |
| 652 | |
| 653 | // Gets edges of the given Instruction*, writing them to the SmallVector*. |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 654 | static void argsToEdges(CFLAAResult &, Instruction *, SmallVectorImpl<Edge> &); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 655 | |
Pete Cooper | 3664253 | 2015-06-12 16:13:54 +0000 | [diff] [blame] | 656 | // Gets edges of the given ConstantExpr*, writing them to the SmallVector*. |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 657 | static void argsToEdges(CFLAAResult &, ConstantExpr *, SmallVectorImpl<Edge> &); |
Pete Cooper | 3664253 | 2015-06-12 16:13:54 +0000 | [diff] [blame] | 658 | |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 659 | // Gets the "Level" that one should travel in StratifiedSets |
| 660 | // given an EdgeType. |
| 661 | static Level directionOfEdgeType(EdgeType); |
| 662 | |
| 663 | // Builds the graph needed for constructing the StratifiedSets for the |
| 664 | // given function |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 665 | static void buildGraphFrom(CFLAAResult &, Function *, |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 666 | SmallVectorImpl<Value *> &, NodeMapT &, GraphT &); |
| 667 | |
George Burgess IV | ab03af2 | 2015-03-10 02:58:15 +0000 | [diff] [blame] | 668 | // Gets the edges of a ConstantExpr as if it was an Instruction. This |
| 669 | // function also acts on any nested ConstantExprs, adding the edges |
| 670 | // of those to the given SmallVector as well. |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 671 | static void constexprToEdges(CFLAAResult &, ConstantExpr &, |
George Burgess IV | ab03af2 | 2015-03-10 02:58:15 +0000 | [diff] [blame] | 672 | SmallVectorImpl<Edge> &); |
| 673 | |
| 674 | // Given an Instruction, this will add it to the graph, along with any |
| 675 | // Instructions that are potentially only available from said Instruction |
| 676 | // For example, given the following line: |
| 677 | // %0 = load i16* getelementptr ([1 x i16]* @a, 0, 0), align 2 |
| 678 | // addInstructionToGraph would add both the `load` and `getelementptr` |
| 679 | // instructions to the graph appropriately. |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 680 | static void addInstructionToGraph(CFLAAResult &, Instruction &, |
George Burgess IV | ab03af2 | 2015-03-10 02:58:15 +0000 | [diff] [blame] | 681 | SmallVectorImpl<Value *> &, NodeMapT &, |
| 682 | GraphT &); |
| 683 | |
| 684 | // Notes whether it would be pointless to add the given Value to our sets. |
| 685 | static bool canSkipAddingToSets(Value *Val); |
| 686 | |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 687 | static Optional<Function *> parentFunctionOfValue(Value *Val) { |
| 688 | if (auto *Inst = dyn_cast<Instruction>(Val)) { |
| 689 | auto *Bb = Inst->getParent(); |
| 690 | return Bb->getParent(); |
| 691 | } |
| 692 | |
| 693 | if (auto *Arg = dyn_cast<Argument>(Val)) |
| 694 | return Arg->getParent(); |
George Burgess IV | 77351ba3 | 2016-01-28 00:54:01 +0000 | [diff] [blame] | 695 | return None; |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 696 | } |
| 697 | |
| 698 | template <typename Inst> |
| 699 | static bool getPossibleTargets(Inst *Call, |
| 700 | SmallVectorImpl<Function *> &Output) { |
| 701 | if (auto *Fn = Call->getCalledFunction()) { |
| 702 | Output.push_back(Fn); |
| 703 | return true; |
| 704 | } |
| 705 | |
| 706 | // TODO: If the call is indirect, we might be able to enumerate all potential |
| 707 | // targets of the call and return them, rather than just failing. |
| 708 | return false; |
| 709 | } |
| 710 | |
| 711 | static Optional<Value *> getTargetValue(Instruction *Inst) { |
| 712 | GetTargetValueVisitor V; |
| 713 | return V.visit(Inst); |
| 714 | } |
| 715 | |
| 716 | static bool hasUsefulEdges(Instruction *Inst) { |
| 717 | bool IsNonInvokeTerminator = |
| 718 | isa<TerminatorInst>(Inst) && !isa<InvokeInst>(Inst); |
| 719 | return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) && !IsNonInvokeTerminator; |
| 720 | } |
| 721 | |
Pete Cooper | 3664253 | 2015-06-12 16:13:54 +0000 | [diff] [blame] | 722 | static bool hasUsefulEdges(ConstantExpr *CE) { |
Benjamin Kramer | df005cb | 2015-08-08 18:27:36 +0000 | [diff] [blame] | 723 | // ConstantExpr doesn't have terminators, invokes, or fences, so only needs |
Pete Cooper | 3664253 | 2015-06-12 16:13:54 +0000 | [diff] [blame] | 724 | // to check for compares. |
| 725 | return CE->getOpcode() != Instruction::ICmp && |
| 726 | CE->getOpcode() != Instruction::FCmp; |
| 727 | } |
| 728 | |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 729 | static Optional<StratifiedAttr> valueToAttrIndex(Value *Val) { |
| 730 | if (isa<GlobalValue>(Val)) |
| 731 | return AttrGlobalIndex; |
| 732 | |
| 733 | if (auto *Arg = dyn_cast<Argument>(Val)) |
Daniel Berlin | 16f7a52 | 2015-01-26 17:31:17 +0000 | [diff] [blame] | 734 | // Only pointer arguments should have the argument attribute, |
| 735 | // because things can't escape through scalars without us seeing a |
| 736 | // cast, and thus, interaction with them doesn't matter. |
| 737 | if (!Arg->hasNoAliasAttr() && Arg->getType()->isPointerTy()) |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 738 | return argNumberToAttrIndex(Arg->getArgNo()); |
George Burgess IV | 77351ba3 | 2016-01-28 00:54:01 +0000 | [diff] [blame] | 739 | return None; |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 740 | } |
| 741 | |
| 742 | static StratifiedAttr argNumberToAttrIndex(unsigned ArgNum) { |
George Burgess IV | 3c898c2 | 2015-01-21 16:37:21 +0000 | [diff] [blame] | 743 | if (ArgNum >= AttrMaxNumArgs) |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 744 | return AttrAllIndex; |
| 745 | return ArgNum + AttrFirstArgIndex; |
| 746 | } |
| 747 | |
| 748 | static EdgeType flipWeight(EdgeType Initial) { |
| 749 | switch (Initial) { |
| 750 | case EdgeType::Assign: |
| 751 | return EdgeType::Assign; |
| 752 | case EdgeType::Dereference: |
| 753 | return EdgeType::Reference; |
| 754 | case EdgeType::Reference: |
| 755 | return EdgeType::Dereference; |
| 756 | } |
| 757 | llvm_unreachable("Incomplete coverage of EdgeType enum"); |
| 758 | } |
| 759 | |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 760 | static void argsToEdges(CFLAAResult &Analysis, Instruction *Inst, |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 761 | SmallVectorImpl<Edge> &Output) { |
George Burgess IV | ab03af2 | 2015-03-10 02:58:15 +0000 | [diff] [blame] | 762 | assert(hasUsefulEdges(Inst) && |
| 763 | "Expected instructions to have 'useful' edges"); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 764 | GetEdgesVisitor v(Analysis, Output); |
| 765 | v.visit(Inst); |
| 766 | } |
| 767 | |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 768 | static void argsToEdges(CFLAAResult &Analysis, ConstantExpr *CE, |
Pete Cooper | 3664253 | 2015-06-12 16:13:54 +0000 | [diff] [blame] | 769 | SmallVectorImpl<Edge> &Output) { |
| 770 | assert(hasUsefulEdges(CE) && "Expected constant expr to have 'useful' edges"); |
| 771 | GetEdgesVisitor v(Analysis, Output); |
| 772 | v.visitConstantExpr(CE); |
| 773 | } |
| 774 | |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 775 | static Level directionOfEdgeType(EdgeType Weight) { |
| 776 | switch (Weight) { |
| 777 | case EdgeType::Reference: |
| 778 | return Level::Above; |
| 779 | case EdgeType::Dereference: |
| 780 | return Level::Below; |
| 781 | case EdgeType::Assign: |
| 782 | return Level::Same; |
| 783 | } |
| 784 | llvm_unreachable("Incomplete switch coverage"); |
| 785 | } |
| 786 | |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 787 | static void constexprToEdges(CFLAAResult &Analysis, |
George Burgess IV | ab03af2 | 2015-03-10 02:58:15 +0000 | [diff] [blame] | 788 | ConstantExpr &CExprToCollapse, |
| 789 | SmallVectorImpl<Edge> &Results) { |
| 790 | SmallVector<ConstantExpr *, 4> Worklist; |
| 791 | Worklist.push_back(&CExprToCollapse); |
| 792 | |
| 793 | SmallVector<Edge, 8> ConstexprEdges; |
Pete Cooper | 3664253 | 2015-06-12 16:13:54 +0000 | [diff] [blame] | 794 | SmallPtrSet<ConstantExpr *, 4> Visited; |
George Burgess IV | ab03af2 | 2015-03-10 02:58:15 +0000 | [diff] [blame] | 795 | while (!Worklist.empty()) { |
| 796 | auto *CExpr = Worklist.pop_back_val(); |
George Burgess IV | ab03af2 | 2015-03-10 02:58:15 +0000 | [diff] [blame] | 797 | |
Pete Cooper | 3664253 | 2015-06-12 16:13:54 +0000 | [diff] [blame] | 798 | if (!hasUsefulEdges(CExpr)) |
George Burgess IV | ab03af2 | 2015-03-10 02:58:15 +0000 | [diff] [blame] | 799 | continue; |
| 800 | |
| 801 | ConstexprEdges.clear(); |
Pete Cooper | 3664253 | 2015-06-12 16:13:54 +0000 | [diff] [blame] | 802 | argsToEdges(Analysis, CExpr, ConstexprEdges); |
George Burgess IV | ab03af2 | 2015-03-10 02:58:15 +0000 | [diff] [blame] | 803 | for (auto &Edge : ConstexprEdges) { |
Pete Cooper | 3664253 | 2015-06-12 16:13:54 +0000 | [diff] [blame] | 804 | if (auto *Nested = dyn_cast<ConstantExpr>(Edge.From)) |
| 805 | if (Visited.insert(Nested).second) |
| 806 | Worklist.push_back(Nested); |
George Burgess IV | ab03af2 | 2015-03-10 02:58:15 +0000 | [diff] [blame] | 807 | |
Pete Cooper | 3664253 | 2015-06-12 16:13:54 +0000 | [diff] [blame] | 808 | if (auto *Nested = dyn_cast<ConstantExpr>(Edge.To)) |
| 809 | if (Visited.insert(Nested).second) |
| 810 | Worklist.push_back(Nested); |
George Burgess IV | ab03af2 | 2015-03-10 02:58:15 +0000 | [diff] [blame] | 811 | } |
| 812 | |
| 813 | Results.append(ConstexprEdges.begin(), ConstexprEdges.end()); |
| 814 | } |
| 815 | } |
| 816 | |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 817 | static void addInstructionToGraph(CFLAAResult &Analysis, Instruction &Inst, |
George Burgess IV | ab03af2 | 2015-03-10 02:58:15 +0000 | [diff] [blame] | 818 | SmallVectorImpl<Value *> &ReturnedValues, |
| 819 | NodeMapT &Map, GraphT &Graph) { |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 820 | const auto findOrInsertNode = [&Map, &Graph](Value *Val) { |
| 821 | auto Pair = Map.insert(std::make_pair(Val, GraphT::Node())); |
| 822 | auto &Iter = Pair.first; |
| 823 | if (Pair.second) { |
| 824 | auto NewNode = Graph.addNode(); |
| 825 | Iter->second = NewNode; |
| 826 | } |
| 827 | return Iter->second; |
| 828 | }; |
| 829 | |
George Burgess IV | ab03af2 | 2015-03-10 02:58:15 +0000 | [diff] [blame] | 830 | // We don't want the edges of most "return" instructions, but we *do* want |
| 831 | // to know what can be returned. |
| 832 | if (isa<ReturnInst>(&Inst)) |
| 833 | ReturnedValues.push_back(&Inst); |
| 834 | |
| 835 | if (!hasUsefulEdges(&Inst)) |
| 836 | return; |
| 837 | |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 838 | SmallVector<Edge, 8> Edges; |
George Burgess IV | ab03af2 | 2015-03-10 02:58:15 +0000 | [diff] [blame] | 839 | argsToEdges(Analysis, &Inst, Edges); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 840 | |
George Burgess IV | ab03af2 | 2015-03-10 02:58:15 +0000 | [diff] [blame] | 841 | // In the case of an unused alloca (or similar), edges may be empty. Note |
| 842 | // that it exists so we can potentially answer NoAlias. |
| 843 | if (Edges.empty()) { |
| 844 | auto MaybeVal = getTargetValue(&Inst); |
| 845 | assert(MaybeVal.hasValue()); |
| 846 | auto *Target = *MaybeVal; |
| 847 | findOrInsertNode(Target); |
| 848 | return; |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 849 | } |
George Burgess IV | ab03af2 | 2015-03-10 02:58:15 +0000 | [diff] [blame] | 850 | |
| 851 | const auto addEdgeToGraph = [&Graph, &findOrInsertNode](const Edge &E) { |
| 852 | auto To = findOrInsertNode(E.To); |
| 853 | auto From = findOrInsertNode(E.From); |
| 854 | auto FlippedWeight = flipWeight(E.Weight); |
| 855 | auto Attrs = E.AdditionalAttrs; |
| 856 | Graph.addEdge(From, To, std::make_pair(E.Weight, Attrs), |
| 857 | std::make_pair(FlippedWeight, Attrs)); |
| 858 | }; |
| 859 | |
| 860 | SmallVector<ConstantExpr *, 4> ConstantExprs; |
| 861 | for (const Edge &E : Edges) { |
| 862 | addEdgeToGraph(E); |
| 863 | if (auto *Constexpr = dyn_cast<ConstantExpr>(E.To)) |
| 864 | ConstantExprs.push_back(Constexpr); |
| 865 | if (auto *Constexpr = dyn_cast<ConstantExpr>(E.From)) |
| 866 | ConstantExprs.push_back(Constexpr); |
| 867 | } |
| 868 | |
| 869 | for (ConstantExpr *CE : ConstantExprs) { |
| 870 | Edges.clear(); |
| 871 | constexprToEdges(Analysis, *CE, Edges); |
| 872 | std::for_each(Edges.begin(), Edges.end(), addEdgeToGraph); |
| 873 | } |
| 874 | } |
| 875 | |
| 876 | // Aside: We may remove graph construction entirely, because it doesn't really |
| 877 | // buy us much that we don't already have. I'd like to add interprocedural |
| 878 | // analysis prior to this however, in case that somehow requires the graph |
| 879 | // produced by this for efficient execution |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 880 | static void buildGraphFrom(CFLAAResult &Analysis, Function *Fn, |
George Burgess IV | ab03af2 | 2015-03-10 02:58:15 +0000 | [diff] [blame] | 881 | SmallVectorImpl<Value *> &ReturnedValues, |
| 882 | NodeMapT &Map, GraphT &Graph) { |
| 883 | for (auto &Bb : Fn->getBasicBlockList()) |
| 884 | for (auto &Inst : Bb.getInstList()) |
| 885 | addInstructionToGraph(Analysis, Inst, ReturnedValues, Map, Graph); |
| 886 | } |
| 887 | |
| 888 | static bool canSkipAddingToSets(Value *Val) { |
| 889 | // Constants can share instances, which may falsely unify multiple |
| 890 | // sets, e.g. in |
| 891 | // store i32* null, i32** %ptr1 |
| 892 | // store i32* null, i32** %ptr2 |
| 893 | // clearly ptr1 and ptr2 should not be unified into the same set, so |
| 894 | // we should filter out the (potentially shared) instance to |
| 895 | // i32* null. |
| 896 | if (isa<Constant>(Val)) { |
| 897 | bool Container = isa<ConstantVector>(Val) || isa<ConstantArray>(Val) || |
| 898 | isa<ConstantStruct>(Val); |
| 899 | // TODO: Because all of these things are constant, we can determine whether |
| 900 | // the data is *actually* mutable at graph building time. This will probably |
| 901 | // come for free/cheap with offset awareness. |
| 902 | bool CanStoreMutableData = |
| 903 | isa<GlobalValue>(Val) || isa<ConstantExpr>(Val) || Container; |
| 904 | return !CanStoreMutableData; |
| 905 | } |
| 906 | |
| 907 | return false; |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 908 | } |
| 909 | |
Chandler Carruth | 8b046a4 | 2015-08-14 02:42:20 +0000 | [diff] [blame] | 910 | // Builds the graph + StratifiedSets for a function. |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 911 | CFLAAResult::FunctionInfo CFLAAResult::buildSetsFrom(Function *Fn) { |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 912 | NodeMapT Map; |
| 913 | GraphT Graph; |
| 914 | SmallVector<Value *, 4> ReturnedValues; |
| 915 | |
Chandler Carruth | 8b046a4 | 2015-08-14 02:42:20 +0000 | [diff] [blame] | 916 | buildGraphFrom(*this, Fn, ReturnedValues, Map, Graph); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 917 | |
| 918 | DenseMap<GraphT::Node, Value *> NodeValueMap; |
Mehdi Amini | c04fc7a | 2016-03-22 07:20:00 +0000 | [diff] [blame] | 919 | NodeValueMap.reserve(Map.size()); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 920 | for (const auto &Pair : Map) |
Hal Finkel | 8d1590d | 2014-09-02 22:52:30 +0000 | [diff] [blame] | 921 | NodeValueMap.insert(std::make_pair(Pair.second, Pair.first)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 922 | |
| 923 | const auto findValueOrDie = [&NodeValueMap](GraphT::Node Node) { |
| 924 | auto ValIter = NodeValueMap.find(Node); |
| 925 | assert(ValIter != NodeValueMap.end()); |
| 926 | return ValIter->second; |
| 927 | }; |
| 928 | |
| 929 | StratifiedSetsBuilder<Value *> Builder; |
| 930 | |
| 931 | SmallVector<GraphT::Node, 16> Worklist; |
| 932 | for (auto &Pair : Map) { |
| 933 | Worklist.clear(); |
| 934 | |
| 935 | auto *Value = Pair.first; |
| 936 | Builder.add(Value); |
| 937 | auto InitialNode = Pair.second; |
| 938 | Worklist.push_back(InitialNode); |
| 939 | while (!Worklist.empty()) { |
| 940 | auto Node = Worklist.pop_back_val(); |
| 941 | auto *CurValue = findValueOrDie(Node); |
George Burgess IV | ab03af2 | 2015-03-10 02:58:15 +0000 | [diff] [blame] | 942 | if (canSkipAddingToSets(CurValue)) |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 943 | continue; |
| 944 | |
| 945 | for (const auto &EdgeTuple : Graph.edgesFor(Node)) { |
| 946 | auto Weight = std::get<0>(EdgeTuple); |
| 947 | auto Label = Weight.first; |
| 948 | auto &OtherNode = std::get<1>(EdgeTuple); |
| 949 | auto *OtherValue = findValueOrDie(OtherNode); |
| 950 | |
George Burgess IV | ab03af2 | 2015-03-10 02:58:15 +0000 | [diff] [blame] | 951 | if (canSkipAddingToSets(OtherValue)) |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 952 | continue; |
| 953 | |
| 954 | bool Added; |
| 955 | switch (directionOfEdgeType(Label)) { |
| 956 | case Level::Above: |
| 957 | Added = Builder.addAbove(CurValue, OtherValue); |
| 958 | break; |
| 959 | case Level::Below: |
| 960 | Added = Builder.addBelow(CurValue, OtherValue); |
| 961 | break; |
| 962 | case Level::Same: |
| 963 | Added = Builder.addWith(CurValue, OtherValue); |
| 964 | break; |
| 965 | } |
| 966 | |
George Burgess IV | b54a8d62 | 2015-03-10 02:40:06 +0000 | [diff] [blame] | 967 | auto Aliasing = Weight.second; |
| 968 | if (auto MaybeCurIndex = valueToAttrIndex(CurValue)) |
| 969 | Aliasing.set(*MaybeCurIndex); |
| 970 | if (auto MaybeOtherIndex = valueToAttrIndex(OtherValue)) |
| 971 | Aliasing.set(*MaybeOtherIndex); |
| 972 | Builder.noteAttributes(CurValue, Aliasing); |
| 973 | Builder.noteAttributes(OtherValue, Aliasing); |
| 974 | |
| 975 | if (Added) |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 976 | Worklist.push_back(OtherNode); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 977 | } |
| 978 | } |
| 979 | } |
| 980 | |
| 981 | // There are times when we end up with parameters not in our graph (i.e. if |
| 982 | // it's only used as the condition of a branch). Other bits of code depend on |
| 983 | // things that were present during construction being present in the graph. |
| 984 | // So, we add all present arguments here. |
| 985 | for (auto &Arg : Fn->args()) { |
George Burgess IV | ab03af2 | 2015-03-10 02:58:15 +0000 | [diff] [blame] | 986 | if (!Builder.add(&Arg)) |
| 987 | continue; |
| 988 | |
| 989 | auto Attrs = valueToAttrIndex(&Arg); |
| 990 | if (Attrs.hasValue()) |
| 991 | Builder.noteAttributes(&Arg, *Attrs); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 992 | } |
| 993 | |
Hal Finkel | 85f2692 | 2014-09-03 00:06:47 +0000 | [diff] [blame] | 994 | return FunctionInfo(Builder.build(), std::move(ReturnedValues)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 995 | } |
| 996 | |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 997 | void CFLAAResult::scan(Function *Fn) { |
Hal Finkel | 8d1590d | 2014-09-02 22:52:30 +0000 | [diff] [blame] | 998 | auto InsertPair = Cache.insert(std::make_pair(Fn, Optional<FunctionInfo>())); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 999 | (void)InsertPair; |
| 1000 | assert(InsertPair.second && |
| 1001 | "Trying to scan a function that has already been cached"); |
| 1002 | |
Chandler Carruth | 8b046a4 | 2015-08-14 02:42:20 +0000 | [diff] [blame] | 1003 | FunctionInfo Info(buildSetsFrom(Fn)); |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 1004 | Cache[Fn] = std::move(Info); |
| 1005 | Handles.push_front(FunctionHandle(Fn, this)); |
| 1006 | } |
| 1007 | |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 1008 | void CFLAAResult::evict(Function *Fn) { Cache.erase(Fn); } |
Chandler Carruth | 8b046a4 | 2015-08-14 02:42:20 +0000 | [diff] [blame] | 1009 | |
| 1010 | /// \brief Ensures that the given function is available in the cache. |
| 1011 | /// Returns the appropriate entry from the cache. |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 1012 | const Optional<CFLAAResult::FunctionInfo> & |
| 1013 | CFLAAResult::ensureCached(Function *Fn) { |
Chandler Carruth | 8b046a4 | 2015-08-14 02:42:20 +0000 | [diff] [blame] | 1014 | auto Iter = Cache.find(Fn); |
| 1015 | if (Iter == Cache.end()) { |
| 1016 | scan(Fn); |
| 1017 | Iter = Cache.find(Fn); |
| 1018 | assert(Iter != Cache.end()); |
| 1019 | assert(Iter->second.hasValue()); |
| 1020 | } |
| 1021 | return Iter->second; |
| 1022 | } |
| 1023 | |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 1024 | AliasResult CFLAAResult::query(const MemoryLocation &LocA, |
| 1025 | const MemoryLocation &LocB) { |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 1026 | auto *ValA = const_cast<Value *>(LocA.Ptr); |
| 1027 | auto *ValB = const_cast<Value *>(LocB.Ptr); |
| 1028 | |
| 1029 | Function *Fn = nullptr; |
| 1030 | auto MaybeFnA = parentFunctionOfValue(ValA); |
| 1031 | auto MaybeFnB = parentFunctionOfValue(ValB); |
| 1032 | if (!MaybeFnA.hasValue() && !MaybeFnB.hasValue()) { |
George Burgess IV | 33305e7 | 2015-02-12 03:07:07 +0000 | [diff] [blame] | 1033 | // The only times this is known to happen are when globals + InlineAsm |
| 1034 | // are involved |
| 1035 | DEBUG(dbgs() << "CFLAA: could not extract parent function information.\n"); |
Chandler Carruth | c3f49eb | 2015-06-22 02:16:51 +0000 | [diff] [blame] | 1036 | return MayAlias; |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 1037 | } |
| 1038 | |
| 1039 | if (MaybeFnA.hasValue()) { |
| 1040 | Fn = *MaybeFnA; |
| 1041 | assert((!MaybeFnB.hasValue() || *MaybeFnB == *MaybeFnA) && |
| 1042 | "Interprocedural queries not supported"); |
| 1043 | } else { |
| 1044 | Fn = *MaybeFnB; |
| 1045 | } |
| 1046 | |
| 1047 | assert(Fn != nullptr); |
| 1048 | auto &MaybeInfo = ensureCached(Fn); |
| 1049 | assert(MaybeInfo.hasValue()); |
| 1050 | |
| 1051 | auto &Sets = MaybeInfo->Sets; |
| 1052 | auto MaybeA = Sets.find(ValA); |
| 1053 | if (!MaybeA.hasValue()) |
Chandler Carruth | c3f49eb | 2015-06-22 02:16:51 +0000 | [diff] [blame] | 1054 | return MayAlias; |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 1055 | |
| 1056 | auto MaybeB = Sets.find(ValB); |
| 1057 | if (!MaybeB.hasValue()) |
Chandler Carruth | c3f49eb | 2015-06-22 02:16:51 +0000 | [diff] [blame] | 1058 | return MayAlias; |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 1059 | |
| 1060 | auto SetA = *MaybeA; |
| 1061 | auto SetB = *MaybeB; |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 1062 | auto AttrsA = Sets.getLink(SetA.Index).Attrs; |
| 1063 | auto AttrsB = Sets.getLink(SetB.Index).Attrs; |
George Burgess IV | 33305e7 | 2015-02-12 03:07:07 +0000 | [diff] [blame] | 1064 | |
Hal Finkel | 8eae3ad | 2014-10-06 14:42:56 +0000 | [diff] [blame] | 1065 | // Stratified set attributes are used as markets to signify whether a member |
George Burgess IV | 33305e7 | 2015-02-12 03:07:07 +0000 | [diff] [blame] | 1066 | // of a StratifiedSet (or a member of a set above the current set) has |
Hal Finkel | 8eae3ad | 2014-10-06 14:42:56 +0000 | [diff] [blame] | 1067 | // interacted with either arguments or globals. "Interacted with" meaning |
George Burgess IV | 33305e7 | 2015-02-12 03:07:07 +0000 | [diff] [blame] | 1068 | // its value may be different depending on the value of an argument or |
Hal Finkel | 8eae3ad | 2014-10-06 14:42:56 +0000 | [diff] [blame] | 1069 | // global. The thought behind this is that, because arguments and globals |
| 1070 | // may alias each other, if AttrsA and AttrsB have touched args/globals, |
George Burgess IV | 33305e7 | 2015-02-12 03:07:07 +0000 | [diff] [blame] | 1071 | // we must conservatively say that they alias. However, if at least one of |
| 1072 | // the sets has no values that could legally be altered by changing the value |
Hal Finkel | 8eae3ad | 2014-10-06 14:42:56 +0000 | [diff] [blame] | 1073 | // of an argument or global, then we don't have to be as conservative. |
| 1074 | if (AttrsA.any() && AttrsB.any()) |
Chandler Carruth | c3f49eb | 2015-06-22 02:16:51 +0000 | [diff] [blame] | 1075 | return MayAlias; |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 1076 | |
Daniel Berlin | 16f7a52 | 2015-01-26 17:31:17 +0000 | [diff] [blame] | 1077 | // We currently unify things even if the accesses to them may not be in |
| 1078 | // bounds, so we can't return partial alias here because we don't |
| 1079 | // know whether the pointer is really within the object or not. |
| 1080 | // IE Given an out of bounds GEP and an alloca'd pointer, we may |
| 1081 | // unify the two. We can't return partial alias for this case. |
| 1082 | // Since we do not currently track enough information to |
| 1083 | // differentiate |
| 1084 | |
| 1085 | if (SetA.Index == SetB.Index) |
Chandler Carruth | c3f49eb | 2015-06-22 02:16:51 +0000 | [diff] [blame] | 1086 | return MayAlias; |
Daniel Berlin | 16f7a52 | 2015-01-26 17:31:17 +0000 | [diff] [blame] | 1087 | |
Chandler Carruth | c3f49eb | 2015-06-22 02:16:51 +0000 | [diff] [blame] | 1088 | return NoAlias; |
Hal Finkel | 7529c55 | 2014-09-02 21:43:13 +0000 | [diff] [blame] | 1089 | } |
Mehdi Amini | 46a4355 | 2015-03-04 18:43:29 +0000 | [diff] [blame] | 1090 | |
Chandler Carruth | b4faf13 | 2016-03-11 10:22:49 +0000 | [diff] [blame] | 1091 | char CFLAA::PassID; |
| 1092 | |
Chandler Carruth | b47f801 | 2016-03-11 11:05:24 +0000 | [diff] [blame] | 1093 | CFLAAResult CFLAA::run(Function &F, AnalysisManager<Function> &AM) { |
Chandler Carruth | 12884f7 | 2016-03-02 15:56:53 +0000 | [diff] [blame] | 1094 | return CFLAAResult(); |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 1095 | } |
| 1096 | |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 1097 | char CFLAAWrapperPass::ID = 0; |
Chandler Carruth | 12884f7 | 2016-03-02 15:56:53 +0000 | [diff] [blame] | 1098 | INITIALIZE_PASS(CFLAAWrapperPass, "cfl-aa", "CFL-Based Alias Analysis", false, |
| 1099 | true) |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 1100 | |
| 1101 | ImmutablePass *llvm::createCFLAAWrapperPass() { return new CFLAAWrapperPass(); } |
| 1102 | |
| 1103 | CFLAAWrapperPass::CFLAAWrapperPass() : ImmutablePass(ID) { |
| 1104 | initializeCFLAAWrapperPassPass(*PassRegistry::getPassRegistry()); |
| 1105 | } |
| 1106 | |
| 1107 | bool CFLAAWrapperPass::doInitialization(Module &M) { |
Chandler Carruth | 12884f7 | 2016-03-02 15:56:53 +0000 | [diff] [blame] | 1108 | Result.reset(new CFLAAResult()); |
Chandler Carruth | 7b560d4 | 2015-09-09 17:55:00 +0000 | [diff] [blame] | 1109 | return false; |
| 1110 | } |
| 1111 | |
| 1112 | bool CFLAAWrapperPass::doFinalization(Module &M) { |
| 1113 | Result.reset(); |
| 1114 | return false; |
| 1115 | } |
| 1116 | |
| 1117 | void CFLAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { |
| 1118 | AU.setPreservesAll(); |
Mehdi Amini | 46a4355 | 2015-03-04 18:43:29 +0000 | [diff] [blame] | 1119 | } |