contrib/llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp

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