contrib/llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp

   1 //===- CFLAndersAliasAnalysis.cpp - Unification-based Alias Analysis ------===//
   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, summary-based alias analysis algorithm. It
  11 // differs from CFLSteensAliasAnalysis in its inclusion-based nature while
  12 // CFLSteensAliasAnalysis is unification-based. This pass has worse performance
  13 // than CFLSteensAliasAnalysis (the worst case complexity of
  14 // CFLAndersAliasAnalysis is cubic, while the worst case complexity of
  15 // CFLSteensAliasAnalysis is almost linear), but it is able to yield more
  16 // precise analysis result. The precision of this analysis is roughly the same
  17 // as that of an one level context-sensitive Andersen's algorithm.
  18 //
  19 // The algorithm used here is based on recursive state machine matching scheme
  20 // proposed in "Demand-driven alias analysis for C" by Xin Zheng and Radu
  21 // Rugina. The general idea is to extend the tranditional transitive closure
  22 // algorithm to perform CFL matching along the way: instead of recording
  23 // "whether X is reachable from Y", we keep track of "whether X is reachable
  24 // from Y at state Z", where the "state" field indicates where we are in the CFL
  25 // matching process. To understand the matching better, it is advisable to have
  26 // the state machine shown in Figure 3 of the paper available when reading the
  27 // codes: all we do here is to selectively expand the transitive closure by
  28 // discarding edges that are not recognized by the state machine.
  29 //
  30 // There are two differences between our current implementation and the one
  31 // described in the paper:
  32 // - Our algorithm eagerly computes all alias pairs after the CFLGraph is built,
  33 // while in the paper the authors did the computation in a demand-driven
  34 // fashion. We did not implement the demand-driven algorithm due to the
  35 // additional coding complexity and higher memory profile, but if we found it
  36 // necessary we may switch to it eventually.
  37 // - In the paper the authors use a state machine that does not distinguish
  38 // value reads from value writes. For example, if Y is reachable from X at state
  39 // S3, it may be the case that X is written into Y, or it may be the case that
  40 // there's a third value Z that writes into both X and Y. To make that
  41 // distinction (which is crucial in building function summary as well as
  42 // retrieving mod-ref info), we choose to duplicate some of the states in the
  43 // paper's proposed state machine. The duplication does not change the set the
  44 // machine accepts. Given a pair of reachable values, it only provides more
  45 // detailed information on which value is being written into and which is being
  46 // read from.
  47 //
  48 //===----------------------------------------------------------------------===//
  49
  50 // N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and
  51 // CFLAndersAA is interprocedural. This is *technically* A Bad Thing, because
  52 // FunctionPasses are only allowed to inspect the Function that they're being
  53 // run on. Realistically, this likely isn't a problem until we allow
  54 // FunctionPasses to run concurrently.
  55
  56 #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
  57 #include "AliasAnalysisSummary.h"
  58 #include "CFLGraph.h"
  59 #include "llvm/ADT/DenseMap.h"
  60 #include "llvm/ADT/DenseMapInfo.h"
  61 #include "llvm/ADT/DenseSet.h"
  62 #include "llvm/ADT/None.h"
  63 #include "llvm/ADT/Optional.h"
  64 #include "llvm/ADT/STLExtras.h"
  65 #include "llvm/ADT/SmallVector.h"
  66 #include "llvm/ADT/iterator_range.h"
  67 #include "llvm/Analysis/AliasAnalysis.h"
  68 #include "llvm/Analysis/MemoryLocation.h"
  69 #include "llvm/IR/Argument.h"
  70 #include "llvm/IR/Function.h"
  71 #include "llvm/IR/PassManager.h"
  72 #include "llvm/IR/Type.h"
  73 #include "llvm/Pass.h"
  74 #include "llvm/Support/Casting.h"
  75 #include "llvm/Support/Compiler.h"
  76 #include "llvm/Support/Debug.h"
  77 #include "llvm/Support/raw_ostream.h"
  78 #include <algorithm>
  79 #include <bitset>
  80 #include <cassert>
  81 #include <cstddef>
  82 #include <cstdint>
  83 #include <functional>
  84 #include <utility>
  85 #include <vector>
  86
  87 using namespace llvm;
  88 using namespace llvm::cflaa;
  89
  90 #define DEBUG_TYPE "cfl-anders-aa"
  91
  92 CFLAndersAAResult::CFLAndersAAResult(const TargetLibraryInfo &TLI) : TLI(TLI) {}
  93 CFLAndersAAResult::CFLAndersAAResult(CFLAndersAAResult &&RHS)
  94     : AAResultBase(std::move(RHS)), TLI(RHS.TLI) {}
  95 CFLAndersAAResult::~CFLAndersAAResult() = default;
  96
  97 namespace {
  98
  99 enum class MatchState : uint8_t {
 100   // The following state represents S1 in the paper.
 101   FlowFromReadOnly = 0,
 102   // The following two states together represent S2 in the paper.
 103   // The 'NoReadWrite' suffix indicates that there exists an alias path that
 104   // does not contain assignment and reverse assignment edges.
 105   // The 'ReadOnly' suffix indicates that there exists an alias path that
 106   // contains reverse assignment edges only.
 107   FlowFromMemAliasNoReadWrite,
 108   FlowFromMemAliasReadOnly,
 109   // The following two states together represent S3 in the paper.
 110   // The 'WriteOnly' suffix indicates that there exists an alias path that
 111   // contains assignment edges only.
 112   // The 'ReadWrite' suffix indicates that there exists an alias path that
 113   // contains both assignment and reverse assignment edges. Note that if X and Y
 114   // are reachable at 'ReadWrite' state, it does NOT mean X is both read from
 115   // and written to Y. Instead, it means that a third value Z is written to both
 116   // X and Y.
 117   FlowToWriteOnly,
 118   FlowToReadWrite,
 119   // The following two states together represent S4 in the paper.
 120   FlowToMemAliasWriteOnly,
 121   FlowToMemAliasReadWrite,
 122 };
 123
 124 using StateSet = std::bitset<7>;
 125
 126 const unsigned ReadOnlyStateMask =
 127     (1U << static_cast<uint8_t>(MatchState::FlowFromReadOnly)) |
 128     (1U << static_cast<uint8_t>(MatchState::FlowFromMemAliasReadOnly));
 129 const unsigned WriteOnlyStateMask =
 130     (1U << static_cast<uint8_t>(MatchState::FlowToWriteOnly)) |
 131     (1U << static_cast<uint8_t>(MatchState::FlowToMemAliasWriteOnly));
 132
 133 // A pair that consists of a value and an offset
 134 struct OffsetValue {
 135   const Value *Val;
 136   int64_t Offset;
 137 };
 138
 139 bool operator==(OffsetValue LHS, OffsetValue RHS) {
 140   return LHS.Val == RHS.Val && LHS.Offset == RHS.Offset;
 141 }
 142 bool operator<(OffsetValue LHS, OffsetValue RHS) {
 143   return std::less<const Value *>()(LHS.Val, RHS.Val) ||
 144          (LHS.Val == RHS.Val && LHS.Offset < RHS.Offset);
 145 }
 146
 147 // A pair that consists of an InstantiatedValue and an offset
 148 struct OffsetInstantiatedValue {
 149   InstantiatedValue IVal;
 150   int64_t Offset;
 151 };
 152
 153 bool operator==(OffsetInstantiatedValue LHS, OffsetInstantiatedValue RHS) {
 154   return LHS.IVal == RHS.IVal && LHS.Offset == RHS.Offset;
 155 }
 156
 157 // We use ReachabilitySet to keep track of value aliases (The nonterminal "V" in
 158 // the paper) during the analysis.
 159 class ReachabilitySet {
 160   using ValueStateMap = DenseMap<InstantiatedValue, StateSet>;
 161   using ValueReachMap = DenseMap<InstantiatedValue, ValueStateMap>;
 162
 163   ValueReachMap ReachMap;
 164
 165 public:
 166   using const_valuestate_iterator = ValueStateMap::const_iterator;
 167   using const_value_iterator = ValueReachMap::const_iterator;
 168
 169   // Insert edge 'From->To' at state 'State'
 170   bool insert(InstantiatedValue From, InstantiatedValue To, MatchState State) {
 171     assert(From != To);
 172     auto &States = ReachMap[To][From];
 173     auto Idx = static_cast<size_t>(State);
 174     if (!States.test(Idx)) {
 175       States.set(Idx);
 176       return true;
 177     }
 178     return false;
 179   }
 180
 181   // Return the set of all ('From', 'State') pair for a given node 'To'
 182   iterator_range<const_valuestate_iterator>
 183   reachableValueAliases(InstantiatedValue V) const {
 184     auto Itr = ReachMap.find(V);
 185     if (Itr == ReachMap.end())
 186       return make_range<const_valuestate_iterator>(const_valuestate_iterator(),
 187                                                    const_valuestate_iterator());
 188     return make_range<const_valuestate_iterator>(Itr->second.begin(),
 189                                                  Itr->second.end());
 190   }
 191
 192   iterator_range<const_value_iterator> value_mappings() const {
 193     return make_range<const_value_iterator>(ReachMap.begin(), ReachMap.end());
 194   }
 195 };
 196
 197 // We use AliasMemSet to keep track of all memory aliases (the nonterminal "M"
 198 // in the paper) during the analysis.
 199 class AliasMemSet {
 200   using MemSet = DenseSet<InstantiatedValue>;
 201   using MemMapType = DenseMap<InstantiatedValue, MemSet>;
 202
 203   MemMapType MemMap;
 204
 205 public:
 206   using const_mem_iterator = MemSet::const_iterator;
 207
 208   bool insert(InstantiatedValue LHS, InstantiatedValue RHS) {
 209     // Top-level values can never be memory aliases because one cannot take the
 210     // addresses of them
 211     assert(LHS.DerefLevel > 0 && RHS.DerefLevel > 0);
 212     return MemMap[LHS].insert(RHS).second;
 213   }
 214
 215   const MemSet *getMemoryAliases(InstantiatedValue V) const {
 216     auto Itr = MemMap.find(V);
 217     if (Itr == MemMap.end())
 218       return nullptr;
 219     return &Itr->second;
 220   }
 221 };
 222
 223 // We use AliasAttrMap to keep track of the AliasAttr of each node.
 224 class AliasAttrMap {
 225   using MapType = DenseMap<InstantiatedValue, AliasAttrs>;
 226
 227   MapType AttrMap;
 228
 229 public:
 230   using const_iterator = MapType::const_iterator;
 231
 232   bool add(InstantiatedValue V, AliasAttrs Attr) {
 233     auto &OldAttr = AttrMap[V];
 234     auto NewAttr = OldAttr | Attr;
 235     if (OldAttr == NewAttr)
 236       return false;
 237     OldAttr = NewAttr;
 238     return true;
 239   }
 240
 241   AliasAttrs getAttrs(InstantiatedValue V) const {
 242     AliasAttrs Attr;
 243     auto Itr = AttrMap.find(V);
 244     if (Itr != AttrMap.end())
 245       Attr = Itr->second;
 246     return Attr;
 247   }
 248
 249   iterator_range<const_iterator> mappings() const {
 250     return make_range<const_iterator>(AttrMap.begin(), AttrMap.end());
 251   }
 252 };
 253
 254 struct WorkListItem {
 255   InstantiatedValue From;
 256   InstantiatedValue To;
 257   MatchState State;
 258 };
 259
 260 struct ValueSummary {
 261   struct Record {
 262     InterfaceValue IValue;
 263     unsigned DerefLevel;
 264   };
 265   SmallVector<Record, 4> FromRecords, ToRecords;
 266 };
 267
 268 } // end anonymous namespace
 269
 270 namespace llvm {
 271
 272 // Specialize DenseMapInfo for OffsetValue.
 273 template <> struct DenseMapInfo<OffsetValue> {
 274   static OffsetValue getEmptyKey() {
 275     return OffsetValue{DenseMapInfo<const Value *>::getEmptyKey(),
 276                        DenseMapInfo<int64_t>::getEmptyKey()};
 277   }
 278
 279   static OffsetValue getTombstoneKey() {
 280     return OffsetValue{DenseMapInfo<const Value *>::getTombstoneKey(),
 281                        DenseMapInfo<int64_t>::getEmptyKey()};
 282   }
 283
 284   static unsigned getHashValue(const OffsetValue &OVal) {
 285     return DenseMapInfo<std::pair<const Value *, int64_t>>::getHashValue(
 286         std::make_pair(OVal.Val, OVal.Offset));
 287   }
 288
 289   static bool isEqual(const OffsetValue &LHS, const OffsetValue &RHS) {
 290     return LHS == RHS;
 291   }
 292 };
 293
 294 // Specialize DenseMapInfo for OffsetInstantiatedValue.
 295 template <> struct DenseMapInfo<OffsetInstantiatedValue> {
 296   static OffsetInstantiatedValue getEmptyKey() {
 297     return OffsetInstantiatedValue{
 298         DenseMapInfo<InstantiatedValue>::getEmptyKey(),
 299         DenseMapInfo<int64_t>::getEmptyKey()};
 300   }
 301
 302   static OffsetInstantiatedValue getTombstoneKey() {
 303     return OffsetInstantiatedValue{
 304         DenseMapInfo<InstantiatedValue>::getTombstoneKey(),
 305         DenseMapInfo<int64_t>::getEmptyKey()};
 306   }
 307
 308   static unsigned getHashValue(const OffsetInstantiatedValue &OVal) {
 309     return DenseMapInfo<std::pair<InstantiatedValue, int64_t>>::getHashValue(
 310         std::make_pair(OVal.IVal, OVal.Offset));
 311   }
 312
 313   static bool isEqual(const OffsetInstantiatedValue &LHS,
 314                       const OffsetInstantiatedValue &RHS) {
 315     return LHS == RHS;
 316   }
 317 };
 318
 319 } // end namespace llvm
 320
 321 class CFLAndersAAResult::FunctionInfo {
 322   /// Map a value to other values that may alias it
 323   /// Since the alias relation is symmetric, to save some space we assume values
 324   /// are properly ordered: if a and b alias each other, and a < b, then b is in
 325   /// AliasMap[a] but not vice versa.
 326   DenseMap<const Value *, std::vector<OffsetValue>> AliasMap;
 327
 328   /// Map a value to its corresponding AliasAttrs
 329   DenseMap<const Value *, AliasAttrs> AttrMap;
 330
 331   /// Summary of externally visible effects.
 332   AliasSummary Summary;
 333
 334   Optional<AliasAttrs> getAttrs(const Value *) const;
 335
 336 public:
 337   FunctionInfo(const Function &, const SmallVectorImpl<Value *> &,
 338                const ReachabilitySet &, const AliasAttrMap &);
 339
 340   bool mayAlias(const Value *, uint64_t, const Value *, uint64_t) const;
 341   const AliasSummary &getAliasSummary() const { return Summary; }
 342 };
 343
 344 static bool hasReadOnlyState(StateSet Set) {
 345   return (Set & StateSet(ReadOnlyStateMask)).any();
 346 }
 347
 348 static bool hasWriteOnlyState(StateSet Set) {
 349   return (Set & StateSet(WriteOnlyStateMask)).any();
 350 }
 351
 352 static Optional<InterfaceValue>
 353 getInterfaceValue(InstantiatedValue IValue,
 354                   const SmallVectorImpl<Value *> &RetVals) {
 355   auto Val = IValue.Val;
 356
 357   Optional<unsigned> Index;
 358   if (auto Arg = dyn_cast<Argument>(Val))
 359     Index = Arg->getArgNo() + 1;
 360   else if (is_contained(RetVals, Val))
 361     Index = 0;
 362
 363   if (Index)
 364     return InterfaceValue{*Index, IValue.DerefLevel};
 365   return None;
 366 }
 367
 368 static void populateAttrMap(DenseMap<const Value *, AliasAttrs> &AttrMap,
 369                             const AliasAttrMap &AMap) {
 370   for (const auto &Mapping : AMap.mappings()) {
 371     auto IVal = Mapping.first;
 372
 373     // Insert IVal into the map
 374     auto &Attr = AttrMap[IVal.Val];
 375     // AttrMap only cares about top-level values
 376     if (IVal.DerefLevel == 0)
 377       Attr |= Mapping.second;
 378   }
 379 }
 380
 381 static void
 382 populateAliasMap(DenseMap<const Value *, std::vector<OffsetValue>> &AliasMap,
 383                  const ReachabilitySet &ReachSet) {
 384   for (const auto &OuterMapping : ReachSet.value_mappings()) {
 385     // AliasMap only cares about top-level values
 386     if (OuterMapping.first.DerefLevel > 0)
 387       continue;
 388
 389     auto Val = OuterMapping.first.Val;
 390     auto &AliasList = AliasMap[Val];
 391     for (const auto &InnerMapping : OuterMapping.second) {
 392       // Again, AliasMap only cares about top-level values
 393       if (InnerMapping.first.DerefLevel == 0)
 394         AliasList.push_back(OffsetValue{InnerMapping.first.Val, UnknownOffset});
 395     }
 396
 397     // Sort AliasList for faster lookup
 398     std::sort(AliasList.begin(), AliasList.end());
 399   }
 400 }
 401
 402 static void populateExternalRelations(
 403     SmallVectorImpl<ExternalRelation> &ExtRelations, const Function &Fn,
 404     const SmallVectorImpl<Value *> &RetVals, const ReachabilitySet &ReachSet) {
 405   // If a function only returns one of its argument X, then X will be both an
 406   // argument and a return value at the same time. This is an edge case that
 407   // needs special handling here.
 408   for (const auto &Arg : Fn.args()) {
 409     if (is_contained(RetVals, &Arg)) {
 410       auto ArgVal = InterfaceValue{Arg.getArgNo() + 1, 0};
 411       auto RetVal = InterfaceValue{0, 0};
 412       ExtRelations.push_back(ExternalRelation{ArgVal, RetVal, 0});
 413     }
 414   }
 415
 416   // Below is the core summary construction logic.
 417   // A naive solution of adding only the value aliases that are parameters or
 418   // return values in ReachSet to the summary won't work: It is possible that a
 419   // parameter P is written into an intermediate value I, and the function
 420   // subsequently returns *I. In that case, *I is does not value alias anything
 421   // in ReachSet, and the naive solution will miss a summary edge from (P, 1) to
 422   // (I, 1).
 423   // To account for the aforementioned case, we need to check each non-parameter
 424   // and non-return value for the possibility of acting as an intermediate.
 425   // 'ValueMap' here records, for each value, which InterfaceValues read from or
 426   // write into it. If both the read list and the write list of a given value
 427   // are non-empty, we know that a particular value is an intermidate and we
 428   // need to add summary edges from the writes to the reads.
 429   DenseMap<Value *, ValueSummary> ValueMap;
 430   for (const auto &OuterMapping : ReachSet.value_mappings()) {
 431     if (auto Dst = getInterfaceValue(OuterMapping.first, RetVals)) {
 432       for (const auto &InnerMapping : OuterMapping.second) {
 433         // If Src is a param/return value, we get a same-level assignment.
 434         if (auto Src = getInterfaceValue(InnerMapping.first, RetVals)) {
 435           // This may happen if both Dst and Src are return values
 436           if (*Dst == *Src)
 437             continue;
 438
 439           if (hasReadOnlyState(InnerMapping.second))
 440             ExtRelations.push_back(ExternalRelation{*Dst, *Src, UnknownOffset});
 441           // No need to check for WriteOnly state, since ReachSet is symmetric
 442         } else {
 443           // If Src is not a param/return, add it to ValueMap
 444           auto SrcIVal = InnerMapping.first;
 445           if (hasReadOnlyState(InnerMapping.second))
 446             ValueMap[SrcIVal.Val].FromRecords.push_back(
 447                 ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
 448           if (hasWriteOnlyState(InnerMapping.second))
 449             ValueMap[SrcIVal.Val].ToRecords.push_back(
 450                 ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
 451         }
 452       }
 453     }
 454   }
 455
 456   for (const auto &Mapping : ValueMap) {
 457     for (const auto &FromRecord : Mapping.second.FromRecords) {
 458       for (const auto &ToRecord : Mapping.second.ToRecords) {
 459         auto ToLevel = ToRecord.DerefLevel;
 460         auto FromLevel = FromRecord.DerefLevel;
 461         // Same-level assignments should have already been processed by now
 462         if (ToLevel == FromLevel)
 463           continue;
 464
 465         auto SrcIndex = FromRecord.IValue.Index;
 466         auto SrcLevel = FromRecord.IValue.DerefLevel;
 467         auto DstIndex = ToRecord.IValue.Index;
 468         auto DstLevel = ToRecord.IValue.DerefLevel;
 469         if (ToLevel > FromLevel)
 470           SrcLevel += ToLevel - FromLevel;
 471         else
 472           DstLevel += FromLevel - ToLevel;
 473
 474         ExtRelations.push_back(ExternalRelation{
 475             InterfaceValue{SrcIndex, SrcLevel},
 476             InterfaceValue{DstIndex, DstLevel}, UnknownOffset});
 477       }
 478     }
 479   }
 480
 481   // Remove duplicates in ExtRelations
 482   std::sort(ExtRelations.begin(), ExtRelations.end());
 483   ExtRelations.erase(std::unique(ExtRelations.begin(), ExtRelations.end()),
 484                      ExtRelations.end());
 485 }
 486
 487 static void populateExternalAttributes(
 488     SmallVectorImpl<ExternalAttribute> &ExtAttributes, const Function &Fn,
 489     const SmallVectorImpl<Value *> &RetVals, const AliasAttrMap &AMap) {
 490   for (const auto &Mapping : AMap.mappings()) {
 491     if (auto IVal = getInterfaceValue(Mapping.first, RetVals)) {
 492       auto Attr = getExternallyVisibleAttrs(Mapping.second);
 493       if (Attr.any())
 494         ExtAttributes.push_back(ExternalAttribute{*IVal, Attr});
 495     }
 496   }
 497 }
 498
 499 CFLAndersAAResult::FunctionInfo::FunctionInfo(
 500     const Function &Fn, const SmallVectorImpl<Value *> &RetVals,
 501     const ReachabilitySet &ReachSet, const AliasAttrMap &AMap) {
 502   populateAttrMap(AttrMap, AMap);
 503   populateExternalAttributes(Summary.RetParamAttributes, Fn, RetVals, AMap);
 504   populateAliasMap(AliasMap, ReachSet);
 505   populateExternalRelations(Summary.RetParamRelations, Fn, RetVals, ReachSet);
 506 }
 507
 508 Optional<AliasAttrs>
 509 CFLAndersAAResult::FunctionInfo::getAttrs(const Value *V) const {
 510   assert(V != nullptr);
 511
 512   auto Itr = AttrMap.find(V);
 513   if (Itr != AttrMap.end())
 514     return Itr->second;
 515   return None;
 516 }
 517
 518 bool CFLAndersAAResult::FunctionInfo::mayAlias(const Value *LHS,
 519                                                uint64_t LHSSize,
 520                                                const Value *RHS,
 521                                                uint64_t RHSSize) const {
 522   assert(LHS && RHS);
 523
 524   // Check if we've seen LHS and RHS before. Sometimes LHS or RHS can be created
 525   // after the analysis gets executed, and we want to be conservative in those
 526   // cases.
 527   auto MaybeAttrsA = getAttrs(LHS);
 528   auto MaybeAttrsB = getAttrs(RHS);
 529   if (!MaybeAttrsA || !MaybeAttrsB)
 530     return true;
 531
 532   // Check AliasAttrs before AliasMap lookup since it's cheaper
 533   auto AttrsA = *MaybeAttrsA;
 534   auto AttrsB = *MaybeAttrsB;
 535   if (hasUnknownOrCallerAttr(AttrsA))
 536     return AttrsB.any();
 537   if (hasUnknownOrCallerAttr(AttrsB))
 538     return AttrsA.any();
 539   if (isGlobalOrArgAttr(AttrsA))
 540     return isGlobalOrArgAttr(AttrsB);
 541   if (isGlobalOrArgAttr(AttrsB))
 542     return isGlobalOrArgAttr(AttrsA);
 543
 544   // At this point both LHS and RHS should point to locally allocated objects
 545
 546   auto Itr = AliasMap.find(LHS);
 547   if (Itr != AliasMap.end()) {
 548
 549     // Find out all (X, Offset) where X == RHS
 550     auto Comparator = [](OffsetValue LHS, OffsetValue RHS) {
 551       return std::less<const Value *>()(LHS.Val, RHS.Val);
 552     };
 553 #ifdef EXPENSIVE_CHECKS
 554     assert(std::is_sorted(Itr->second.begin(), Itr->second.end(), Comparator));
 555 #endif
 556     auto RangePair = std::equal_range(Itr->second.begin(), Itr->second.end(),
 557                                       OffsetValue{RHS, 0}, Comparator);
 558
 559     if (RangePair.first != RangePair.second) {
 560       // Be conservative about UnknownSize
 561       if (LHSSize == MemoryLocation::UnknownSize ||
 562           RHSSize == MemoryLocation::UnknownSize)
 563         return true;
 564
 565       for (const auto &OVal : make_range(RangePair)) {
 566         // Be conservative about UnknownOffset
 567         if (OVal.Offset == UnknownOffset)
 568           return true;
 569
 570         // We know that LHS aliases (RHS + OVal.Offset) if the control flow
 571         // reaches here. The may-alias query essentially becomes integer
 572         // range-overlap queries over two ranges [OVal.Offset, OVal.Offset +
 573         // LHSSize) and [0, RHSSize).
 574
 575         // Try to be conservative on super large offsets
 576         if (LLVM_UNLIKELY(LHSSize > INT64_MAX || RHSSize > INT64_MAX))
 577           return true;
 578
 579         auto LHSStart = OVal.Offset;
 580         // FIXME: Do we need to guard against integer overflow?
 581         auto LHSEnd = OVal.Offset + static_cast<int64_t>(LHSSize);
 582         auto RHSStart = 0;
 583         auto RHSEnd = static_cast<int64_t>(RHSSize);
 584         if (LHSEnd > RHSStart && LHSStart < RHSEnd)
 585           return true;
 586       }
 587     }
 588   }
 589
 590   return false;
 591 }
 592
 593 static void propagate(InstantiatedValue From, InstantiatedValue To,
 594                       MatchState State, ReachabilitySet &ReachSet,
 595                       std::vector<WorkListItem> &WorkList) {
 596   if (From == To)
 597     return;
 598   if (ReachSet.insert(From, To, State))
 599     WorkList.push_back(WorkListItem{From, To, State});
 600 }
 601
 602 static void initializeWorkList(std::vector<WorkListItem> &WorkList,
 603                                ReachabilitySet &ReachSet,
 604                                const CFLGraph &Graph) {
 605   for (const auto &Mapping : Graph.value_mappings()) {
 606     auto Val = Mapping.first;
 607     auto &ValueInfo = Mapping.second;
 608     assert(ValueInfo.getNumLevels() > 0);
 609
 610     // Insert all immediate assignment neighbors to the worklist
 611     for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
 612       auto Src = InstantiatedValue{Val, I};
 613       // If there's an assignment edge from X to Y, it means Y is reachable from
 614       // X at S2 and X is reachable from Y at S1
 615       for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges) {
 616         propagate(Edge.Other, Src, MatchState::FlowFromReadOnly, ReachSet,
 617                   WorkList);
 618         propagate(Src, Edge.Other, MatchState::FlowToWriteOnly, ReachSet,
 619                   WorkList);
 620       }
 621     }
 622   }
 623 }
 624
 625 static Optional<InstantiatedValue> getNodeBelow(const CFLGraph &Graph,
 626                                                 InstantiatedValue V) {
 627   auto NodeBelow = InstantiatedValue{V.Val, V.DerefLevel + 1};
 628   if (Graph.getNode(NodeBelow))
 629     return NodeBelow;
 630   return None;
 631 }
 632
 633 static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph,
 634                                 ReachabilitySet &ReachSet, AliasMemSet &MemSet,
 635                                 std::vector<WorkListItem> &WorkList) {
 636   auto FromNode = Item.From;
 637   auto ToNode = Item.To;
 638
 639   auto NodeInfo = Graph.getNode(ToNode);
 640   assert(NodeInfo != nullptr);
 641
 642   // TODO: propagate field offsets
 643
 644   // FIXME: Here is a neat trick we can do: since both ReachSet and MemSet holds
 645   // relations that are symmetric, we could actually cut the storage by half by
 646   // sorting FromNode and ToNode before insertion happens.
 647
 648   // The newly added value alias pair may pontentially generate more memory
 649   // alias pairs. Check for them here.
 650   auto FromNodeBelow = getNodeBelow(Graph, FromNode);
 651   auto ToNodeBelow = getNodeBelow(Graph, ToNode);
 652   if (FromNodeBelow && ToNodeBelow &&
 653       MemSet.insert(*FromNodeBelow, *ToNodeBelow)) {
 654     propagate(*FromNodeBelow, *ToNodeBelow,
 655               MatchState::FlowFromMemAliasNoReadWrite, ReachSet, WorkList);
 656     for (const auto &Mapping : ReachSet.reachableValueAliases(*FromNodeBelow)) {
 657       auto Src = Mapping.first;
 658       auto MemAliasPropagate = [&](MatchState FromState, MatchState ToState) {
 659         if (Mapping.second.test(static_cast<size_t>(FromState)))
 660           propagate(Src, *ToNodeBelow, ToState, ReachSet, WorkList);
 661       };
 662
 663       MemAliasPropagate(MatchState::FlowFromReadOnly,
 664                         MatchState::FlowFromMemAliasReadOnly);
 665       MemAliasPropagate(MatchState::FlowToWriteOnly,
 666                         MatchState::FlowToMemAliasWriteOnly);
 667       MemAliasPropagate(MatchState::FlowToReadWrite,
 668                         MatchState::FlowToMemAliasReadWrite);
 669     }
 670   }
 671
 672   // This is the core of the state machine walking algorithm. We expand ReachSet
 673   // based on which state we are at (which in turn dictates what edges we
 674   // should examine)
 675   // From a high-level point of view, the state machine here guarantees two
 676   // properties:
 677   // - If *X and *Y are memory aliases, then X and Y are value aliases
 678   // - If Y is an alias of X, then reverse assignment edges (if there is any)
 679   // should precede any assignment edges on the path from X to Y.
 680   auto NextAssignState = [&](MatchState State) {
 681     for (const auto &AssignEdge : NodeInfo->Edges)
 682       propagate(FromNode, AssignEdge.Other, State, ReachSet, WorkList);
 683   };
 684   auto NextRevAssignState = [&](MatchState State) {
 685     for (const auto &RevAssignEdge : NodeInfo->ReverseEdges)
 686       propagate(FromNode, RevAssignEdge.Other, State, ReachSet, WorkList);
 687   };
 688   auto NextMemState = [&](MatchState State) {
 689     if (auto AliasSet = MemSet.getMemoryAliases(ToNode)) {
 690       for (const auto &MemAlias : *AliasSet)
 691         propagate(FromNode, MemAlias, State, ReachSet, WorkList);
 692     }
 693   };
 694
 695   switch (Item.State) {
 696   case MatchState::FlowFromReadOnly:
 697     NextRevAssignState(MatchState::FlowFromReadOnly);
 698     NextAssignState(MatchState::FlowToReadWrite);
 699     NextMemState(MatchState::FlowFromMemAliasReadOnly);
 700     break;
 701
 702   case MatchState::FlowFromMemAliasNoReadWrite:
 703     NextRevAssignState(MatchState::FlowFromReadOnly);
 704     NextAssignState(MatchState::FlowToWriteOnly);
 705     break;
 706
 707   case MatchState::FlowFromMemAliasReadOnly:
 708     NextRevAssignState(MatchState::FlowFromReadOnly);
 709     NextAssignState(MatchState::FlowToReadWrite);
 710     break;
 711
 712   case MatchState::FlowToWriteOnly:
 713     NextAssignState(MatchState::FlowToWriteOnly);
 714     NextMemState(MatchState::FlowToMemAliasWriteOnly);
 715     break;
 716
 717   case MatchState::FlowToReadWrite:
 718     NextAssignState(MatchState::FlowToReadWrite);
 719     NextMemState(MatchState::FlowToMemAliasReadWrite);
 720     break;
 721
 722   case MatchState::FlowToMemAliasWriteOnly:
 723     NextAssignState(MatchState::FlowToWriteOnly);
 724     break;
 725
 726   case MatchState::FlowToMemAliasReadWrite:
 727     NextAssignState(MatchState::FlowToReadWrite);
 728     break;
 729   }
 730 }
 731
 732 static AliasAttrMap buildAttrMap(const CFLGraph &Graph,
 733                                  const ReachabilitySet &ReachSet) {
 734   AliasAttrMap AttrMap;
 735   std::vector<InstantiatedValue> WorkList, NextList;
 736
 737   // Initialize each node with its original AliasAttrs in CFLGraph
 738   for (const auto &Mapping : Graph.value_mappings()) {
 739     auto Val = Mapping.first;
 740     auto &ValueInfo = Mapping.second;
 741     for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
 742       auto Node = InstantiatedValue{Val, I};
 743       AttrMap.add(Node, ValueInfo.getNodeInfoAtLevel(I).Attr);
 744       WorkList.push_back(Node);
 745     }
 746   }
 747
 748   while (!WorkList.empty()) {
 749     for (const auto &Dst : WorkList) {
 750       auto DstAttr = AttrMap.getAttrs(Dst);
 751       if (DstAttr.none())
 752         continue;
 753
 754       // Propagate attr on the same level
 755       for (const auto &Mapping : ReachSet.reachableValueAliases(Dst)) {
 756         auto Src = Mapping.first;
 757         if (AttrMap.add(Src, DstAttr))
 758           NextList.push_back(Src);
 759       }
 760
 761       // Propagate attr to the levels below
 762       auto DstBelow = getNodeBelow(Graph, Dst);
 763       while (DstBelow) {
 764         if (AttrMap.add(*DstBelow, DstAttr)) {
 765           NextList.push_back(*DstBelow);
 766           break;
 767         }
 768         DstBelow = getNodeBelow(Graph, *DstBelow);
 769       }
 770     }
 771     WorkList.swap(NextList);
 772     NextList.clear();
 773   }
 774
 775   return AttrMap;
 776 }
 777
 778 CFLAndersAAResult::FunctionInfo
 779 CFLAndersAAResult::buildInfoFrom(const Function &Fn) {
 780   CFLGraphBuilder<CFLAndersAAResult> GraphBuilder(
 781       *this, TLI,
 782       // Cast away the constness here due to GraphBuilder's API requirement
 783       const_cast<Function &>(Fn));
 784   auto &Graph = GraphBuilder.getCFLGraph();
 785
 786   ReachabilitySet ReachSet;
 787   AliasMemSet MemSet;
 788
 789   std::vector<WorkListItem> WorkList, NextList;
 790   initializeWorkList(WorkList, ReachSet, Graph);
 791   // TODO: make sure we don't stop before the fix point is reached
 792   while (!WorkList.empty()) {
 793     for (const auto &Item : WorkList)
 794       processWorkListItem(Item, Graph, ReachSet, MemSet, NextList);
 795
 796     NextList.swap(WorkList);
 797     NextList.clear();
 798   }
 799
 800   // Now that we have all the reachability info, propagate AliasAttrs according
 801   // to it
 802   auto IValueAttrMap = buildAttrMap(Graph, ReachSet);
 803
 804   return FunctionInfo(Fn, GraphBuilder.getReturnValues(), ReachSet,
 805                       std::move(IValueAttrMap));
 806 }
 807
 808 void CFLAndersAAResult::scan(const Function &Fn) {
 809   auto InsertPair = Cache.insert(std::make_pair(&Fn, Optional<FunctionInfo>()));
 810   (void)InsertPair;
 811   assert(InsertPair.second &&
 812          "Trying to scan a function that has already been cached");
 813
 814   // Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call
 815   // may get evaluated after operator[], potentially triggering a DenseMap
 816   // resize and invalidating the reference returned by operator[]
 817   auto FunInfo = buildInfoFrom(Fn);
 818   Cache[&Fn] = std::move(FunInfo);
 819   Handles.emplace_front(const_cast<Function *>(&Fn), this);
 820 }
 821
 822 void CFLAndersAAResult::evict(const Function *Fn) { Cache.erase(Fn); }
 823
 824 const Optional<CFLAndersAAResult::FunctionInfo> &
 825 CFLAndersAAResult::ensureCached(const Function &Fn) {
 826   auto Iter = Cache.find(&Fn);
 827   if (Iter == Cache.end()) {
 828     scan(Fn);
 829     Iter = Cache.find(&Fn);
 830     assert(Iter != Cache.end());
 831     assert(Iter->second.hasValue());
 832   }
 833   return Iter->second;
 834 }
 835
 836 const AliasSummary *CFLAndersAAResult::getAliasSummary(const Function &Fn) {
 837   auto &FunInfo = ensureCached(Fn);
 838   if (FunInfo.hasValue())
 839     return &FunInfo->getAliasSummary();
 840   else
 841     return nullptr;
 842 }
 843
 844 AliasResult CFLAndersAAResult::query(const MemoryLocation &LocA,
 845                                      const MemoryLocation &LocB) {
 846   auto *ValA = LocA.Ptr;
 847   auto *ValB = LocB.Ptr;
 848
 849   if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
 850     return NoAlias;
 851
 852   auto *Fn = parentFunctionOfValue(ValA);
 853   if (!Fn) {
 854     Fn = parentFunctionOfValue(ValB);
 855     if (!Fn) {
 856       // The only times this is known to happen are when globals + InlineAsm are
 857       // involved
 858       DEBUG(dbgs()
 859             << "CFLAndersAA: could not extract parent function information.\n");
 860       return MayAlias;
 861     }
 862   } else {
 863     assert(!parentFunctionOfValue(ValB) || parentFunctionOfValue(ValB) == Fn);
 864   }
 865
 866   assert(Fn != nullptr);
 867   auto &FunInfo = ensureCached(*Fn);
 868
 869   // AliasMap lookup
 870   if (FunInfo->mayAlias(ValA, LocA.Size, ValB, LocB.Size))
 871     return MayAlias;
 872   return NoAlias;
 873 }
 874
 875 AliasResult CFLAndersAAResult::alias(const MemoryLocation &LocA,
 876                                      const MemoryLocation &LocB) {
 877   if (LocA.Ptr == LocB.Ptr)
 878     return MustAlias;
 879
 880   // Comparisons between global variables and other constants should be
 881   // handled by BasicAA.
 882   // CFLAndersAA may report NoAlias when comparing a GlobalValue and
 883   // ConstantExpr, but every query needs to have at least one Value tied to a
 884   // Function, and neither GlobalValues nor ConstantExprs are.
 885   if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr))
 886     return AAResultBase::alias(LocA, LocB);
 887
 888   AliasResult QueryResult = query(LocA, LocB);
 889   if (QueryResult == MayAlias)
 890     return AAResultBase::alias(LocA, LocB);
 891
 892   return QueryResult;
 893 }
 894
 895 AnalysisKey CFLAndersAA::Key;
 896
 897 CFLAndersAAResult CFLAndersAA::run(Function &F, FunctionAnalysisManager &AM) {
 898   return CFLAndersAAResult(AM.getResult<TargetLibraryAnalysis>(F));
 899 }
 900
 901 char CFLAndersAAWrapperPass::ID = 0;
 902 INITIALIZE_PASS(CFLAndersAAWrapperPass, "cfl-anders-aa",
 903                 "Inclusion-Based CFL Alias Analysis", false, true)
 904
 905 ImmutablePass *llvm::createCFLAndersAAWrapperPass() {
 906   return new CFLAndersAAWrapperPass();
 907 }
 908
 909 CFLAndersAAWrapperPass::CFLAndersAAWrapperPass() : ImmutablePass(ID) {
 910   initializeCFLAndersAAWrapperPassPass(*PassRegistry::getPassRegistry());
 911 }
 912
 913 void CFLAndersAAWrapperPass::initializePass() {
 914   auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
 915   Result.reset(new CFLAndersAAResult(TLIWP.getTLI()));
 916 }
 917
 918 void CFLAndersAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
 919   AU.setPreservesAll();
 920   AU.addRequired<TargetLibraryInfoWrapperPass>();
 921 }