lib/Analysis/CFLAliasAnalysis.cpp

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