LCOV - code coverage report
Current view: top level - lib/Analysis - CFLAndersAliasAnalysis.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 311 323 96.3 %
Date: 2017-09-14 15:23:50 Functions: 37 41 90.2 %
Legend: Lines: hit not hit

          Line data    Source code
       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         183 : CFLAndersAAResult::CFLAndersAAResult(const TargetLibraryInfo &TLI) : TLI(TLI) {}
      93          82 : CFLAndersAAResult::CFLAndersAAResult(CFLAndersAAResult &&RHS)
      94         328 :     : 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         191 :   return std::less<const Value *>()(LHS.Val, RHS.Val) ||
     144           0 :          (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         380 : 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        1013 :   bool insert(InstantiatedValue From, InstantiatedValue To, MatchState State) {
     171             :     assert(From != To);
     172        3039 :     auto &States = ReachMap[To][From];
     173        1013 :     auto Idx = static_cast<size_t>(State);
     174        1013 :     if (!States.test(Idx)) {
     175         948 :       States.set(Idx);
     176         948 :       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         529 :   reachableValueAliases(InstantiatedValue V) const {
     184         529 :     auto Itr = ReachMap.find(V);
     185        1058 :     if (Itr == ReachMap.end())
     186             :       return make_range<const_valuestate_iterator>(const_valuestate_iterator(),
     187         520 :                                                    const_valuestate_iterator());
     188         269 :     return make_range<const_valuestate_iterator>(Itr->second.begin(),
     189         807 :                                                  Itr->second.end());
     190             :   }
     191             : 
     192             :   iterator_range<const_value_iterator> value_mappings() const {
     193         570 :     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         380 : 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          40 :   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         120 :     return MemMap[LHS].insert(RHS).second;
     213             :   }
     214             : 
     215             :   const MemSet *getMemoryAliases(InstantiatedValue V) const {
     216         808 :     auto Itr = MemMap.find(V);
     217        1616 :     if (Itr == MemMap.end())
     218             :       return nullptr;
     219          66 :     return &Itr->second;
     220             :   }
     221             : };
     222             : 
     223             : // We use AliasAttrMap to keep track of the AliasAttr of each node.
     224         380 : 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        2068 :     auto &OldAttr = AttrMap[V];
     234        1034 :     auto NewAttr = OldAttr | Attr;
     235        1034 :     if (OldAttr == NewAttr)
     236             :       return false;
     237         461 :     OldAttr = NewAttr;
     238             :     return true;
     239             :   }
     240             : 
     241         775 :   AliasAttrs getAttrs(InstantiatedValue V) const {
     242         775 :     AliasAttrs Attr;
     243         775 :     auto Itr = AttrMap.find(V);
     244        1550 :     if (Itr != AttrMap.end())
     245         775 :       Attr = Itr->second;
     246         775 :     return Attr;
     247             :   }
     248             : 
     249             :   iterator_range<const_iterator> mappings() const {
     250         570 :     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         336 : 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         855 : 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          64 :   const AliasSummary &getAliasSummary() const { return Summary; }
     342             : };
     343             : 
     344             : static bool hasReadOnlyState(StateSet Set) {
     345         249 :   return (Set & StateSet(ReadOnlyStateMask)).any();
     346             : }
     347             : 
     348             : static bool hasWriteOnlyState(StateSet Set) {
     349         195 :   return (Set & StateSet(WriteOnlyStateMask)).any();
     350             : }
     351             : 
     352             : static Optional<InterfaceValue>
     353         959 : getInterfaceValue(InstantiatedValue IValue,
     354             :                   const SmallVectorImpl<Value *> &RetVals) {
     355         959 :   auto Val = IValue.Val;
     356             : 
     357        1918 :   Optional<unsigned> Index;
     358        1181 :   if (auto Arg = dyn_cast<Argument>(Val))
     359         444 :     Index = Arg->getArgNo() + 1;
     360         737 :   else if (is_contained(RetVals, Val))
     361             :     Index = 0;
     362             : 
     363         959 :   if (Index)
     364         566 :     return InterfaceValue{*Index, IValue.DerefLevel};
     365             :   return None;
     366             : }
     367             : 
     368          95 : static void populateAttrMap(DenseMap<const Value *, AliasAttrs> &AttrMap,
     369             :                             const AliasAttrMap &AMap) {
     370         657 :   for (const auto &Mapping : AMap.mappings()) {
     371         562 :     auto IVal = Mapping.first;
     372             : 
     373             :     // Insert IVal into the map
     374        1124 :     auto &Attr = AttrMap[IVal.Val];
     375             :     // AttrMap only cares about top-level values
     376         562 :     if (IVal.DerefLevel == 0)
     377         369 :       Attr |= Mapping.second;
     378             :   }
     379          95 : }
     380             : 
     381             : static void
     382          95 : populateAliasMap(DenseMap<const Value *, std::vector<OffsetValue>> &AliasMap,
     383             :                  const ReachabilitySet &ReachSet) {
     384         409 :   for (const auto &OuterMapping : ReachSet.value_mappings()) {
     385             :     // AliasMap only cares about top-level values
     386         314 :     if (OuterMapping.first.DerefLevel > 0)
     387         113 :       continue;
     388             : 
     389         201 :     auto Val = OuterMapping.first.Val;
     390         402 :     auto &AliasList = AliasMap[Val];
     391         897 :     for (const auto &InnerMapping : OuterMapping.second) {
     392             :       // Again, AliasMap only cares about top-level values
     393         495 :       if (InnerMapping.first.DerefLevel == 0)
     394         524 :         AliasList.push_back(OffsetValue{InnerMapping.first.Val, UnknownOffset});
     395             :     }
     396             : 
     397             :     // Sort AliasList for faster lookup
     398         402 :     std::sort(AliasList.begin(), AliasList.end());
     399             :   }
     400          95 : }
     401             : 
     402          95 : 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         183 :   for (const auto &Arg : Fn.args()) {
     409         176 :     if (is_contained(RetVals, &Arg)) {
     410           3 :       auto ArgVal = InterfaceValue{Arg.getArgNo() + 1, 0};
     411           3 :       auto RetVal = InterfaceValue{0, 0};
     412           3 :       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         190 :   DenseMap<Value *, ValueSummary> ValueMap;
     430         409 :   for (const auto &OuterMapping : ReachSet.value_mappings()) {
     431         628 :     if (auto Dst = getInterfaceValue(OuterMapping.first, RetVals)) {
     432         217 :       for (const auto &InnerMapping : OuterMapping.second) {
     433             :         // If Src is a param/return value, we get a same-level assignment.
     434         166 :         if (auto Src = getInterfaceValue(InnerMapping.first, RetVals)) {
     435             :           // This may happen if both Dst and Src are return values
     436          36 :           if (*Dst == *Src)
     437           0 :             continue;
     438             : 
     439          18 :           if (hasReadOnlyState(InnerMapping.second))
     440          27 :             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          65 :           auto SrcIVal = InnerMapping.first;
     445          65 :           if (hasReadOnlyState(InnerMapping.second))
     446          76 :             ValueMap[SrcIVal.Val].FromRecords.push_back(
     447          76 :                 ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
     448          65 :           if (hasWriteOnlyState(InnerMapping.second))
     449          54 :             ValueMap[SrcIVal.Val].ToRecords.push_back(
     450          54 :                 ValueSummary::Record{*Dst, SrcIVal.DerefLevel});
     451             :         }
     452             :       }
     453             :     }
     454             :   }
     455             : 
     456         341 :   for (const auto &Mapping : ValueMap) {
     457         206 :     for (const auto &FromRecord : Mapping.second.FromRecords) {
     458         123 :       for (const auto &ToRecord : Mapping.second.ToRecords) {
     459           9 :         auto ToLevel = ToRecord.DerefLevel;
     460           9 :         auto FromLevel = FromRecord.DerefLevel;
     461             :         // Same-level assignments should have already been processed by now
     462           9 :         if (ToLevel == FromLevel)
     463           0 :           continue;
     464             : 
     465           9 :         auto SrcIndex = FromRecord.IValue.Index;
     466           9 :         auto SrcLevel = FromRecord.IValue.DerefLevel;
     467           9 :         auto DstIndex = ToRecord.IValue.Index;
     468           9 :         auto DstLevel = ToRecord.IValue.DerefLevel;
     469           9 :         if (ToLevel > FromLevel)
     470           3 :           SrcLevel += ToLevel - FromLevel;
     471             :         else
     472           6 :           DstLevel += FromLevel - ToLevel;
     473             : 
     474           9 :         ExtRelations.push_back(ExternalRelation{
     475             :             InterfaceValue{SrcIndex, SrcLevel},
     476             :             InterfaceValue{DstIndex, DstLevel}, UnknownOffset});
     477             :       }
     478             :     }
     479             :   }
     480             : 
     481             :   // Remove duplicates in ExtRelations
     482         380 :   std::sort(ExtRelations.begin(), ExtRelations.end());
     483         380 :   ExtRelations.erase(std::unique(ExtRelations.begin(), ExtRelations.end()),
     484         190 :                      ExtRelations.end());
     485          95 : }
     486             : 
     487          95 : static void populateExternalAttributes(
     488             :     SmallVectorImpl<ExternalAttribute> &ExtAttributes, const Function &Fn,
     489             :     const SmallVectorImpl<Value *> &RetVals, const AliasAttrMap &AMap) {
     490         657 :   for (const auto &Mapping : AMap.mappings()) {
     491        1124 :     if (auto IVal = getInterfaceValue(Mapping.first, RetVals)) {
     492         198 :       auto Attr = getExternallyVisibleAttrs(Mapping.second);
     493         198 :       if (Attr.any())
     494          52 :         ExtAttributes.push_back(ExternalAttribute{*IVal, Attr});
     495             :     }
     496             :   }
     497          95 : }
     498             : 
     499          95 : CFLAndersAAResult::FunctionInfo::FunctionInfo(
     500             :     const Function &Fn, const SmallVectorImpl<Value *> &RetVals,
     501         380 :     const ReachabilitySet &ReachSet, const AliasAttrMap &AMap) {
     502          95 :   populateAttrMap(AttrMap, AMap);
     503          95 :   populateExternalAttributes(Summary.RetParamAttributes, Fn, RetVals, AMap);
     504          95 :   populateAliasMap(AliasMap, ReachSet);
     505          95 :   populateExternalRelations(Summary.RetParamRelations, Fn, RetVals, ReachSet);
     506          95 : }
     507             : 
     508             : Optional<AliasAttrs>
     509        1330 : CFLAndersAAResult::FunctionInfo::getAttrs(const Value *V) const {
     510             :   assert(V != nullptr);
     511             : 
     512        1330 :   auto Itr = AttrMap.find(V);
     513        2660 :   if (Itr != AttrMap.end())
     514        1329 :     return Itr->second;
     515             :   return None;
     516             : }
     517             : 
     518         665 : 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        1330 :   auto MaybeAttrsA = getAttrs(LHS);
     528        1330 :   auto MaybeAttrsB = getAttrs(RHS);
     529         665 :   if (!MaybeAttrsA || !MaybeAttrsB)
     530             :     return true;
     531             : 
     532             :   // Check AliasAttrs before AliasMap lookup since it's cheaper
     533         664 :   auto AttrsA = *MaybeAttrsA;
     534         664 :   auto AttrsB = *MaybeAttrsB;
     535         664 :   if (hasUnknownOrCallerAttr(AttrsA))
     536         148 :     return AttrsB.any();
     537         516 :   if (hasUnknownOrCallerAttr(AttrsB))
     538          10 :     return AttrsA.any();
     539         506 :   if (isGlobalOrArgAttr(AttrsA))
     540          48 :     return isGlobalOrArgAttr(AttrsB);
     541         458 :   if (isGlobalOrArgAttr(AttrsB))
     542          74 :     return isGlobalOrArgAttr(AttrsA);
     543             : 
     544             :   // At this point both LHS and RHS should point to locally allocated objects
     545             : 
     546         384 :   auto Itr = AliasMap.find(LHS);
     547         768 :   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         592 :     auto RangePair = std::equal_range(Itr->second.begin(), Itr->second.end(),
     557        1480 :                                       OffsetValue{RHS, 0}, Comparator);
     558             : 
     559         296 :     if (RangePair.first != RangePair.second) {
     560             :       // Be conservative about UnknownSize
     561         216 :       if (LHSSize == MemoryLocation::UnknownSize ||
     562         108 :           RHSSize == MemoryLocation::UnknownSize)
     563             :         return true;
     564             : 
     565         108 :       for (const auto &OVal : make_range(RangePair)) {
     566             :         // Be conservative about UnknownOffset
     567         108 :         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           0 :         if (LLVM_UNLIKELY(LHSSize > INT64_MAX || RHSSize > INT64_MAX))
     577             :           return true;
     578             : 
     579           0 :         auto LHSStart = OVal.Offset;
     580             :         // FIXME: Do we need to guard against integer overflow?
     581           0 :         auto LHSEnd = OVal.Offset + static_cast<int64_t>(LHSSize);
     582           0 :         auto RHSStart = 0;
     583           0 :         auto RHSEnd = static_cast<int64_t>(RHSSize);
     584           0 :         if (LHSEnd > RHSStart && LHSStart < RHSEnd)
     585             :           return true;
     586             :       }
     587             :     }
     588             :   }
     589             : 
     590             :   return false;
     591             : }
     592             : 
     593        1289 : static void propagate(InstantiatedValue From, InstantiatedValue To,
     594             :                       MatchState State, ReachabilitySet &ReachSet,
     595             :                       std::vector<WorkListItem> &WorkList) {
     596        1289 :   if (From == To)
     597             :     return;
     598        1013 :   if (ReachSet.insert(From, To, State))
     599        1896 :     WorkList.push_back(WorkListItem{From, To, State});
     600             : }
     601             : 
     602          95 : static void initializeWorkList(std::vector<WorkListItem> &WorkList,
     603             :                                ReachabilitySet &ReachSet,
     604             :                                const CFLGraph &Graph) {
     605          95 :   for (const auto &Mapping : Graph.value_mappings()) {
     606         369 :     auto Val = Mapping.first;
     607         369 :     auto &ValueInfo = Mapping.second;
     608             :     assert(ValueInfo.getNumLevels() > 0);
     609             : 
     610             :     // Insert all immediate assignment neighbors to the worklist
     611        1300 :     for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
     612         562 :       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        2440 :       for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges) {
     616         192 :         propagate(Edge.Other, Src, MatchState::FlowFromReadOnly, ReachSet,
     617             :                   WorkList);
     618         192 :         propagate(Src, Edge.Other, MatchState::FlowToWriteOnly, ReachSet,
     619             :                   WorkList);
     620             :       }
     621             :     }
     622             :   }
     623          95 : }
     624             : 
     625             : static Optional<InstantiatedValue> getNodeBelow(const CFLGraph &Graph,
     626             :                                                 InstantiatedValue V) {
     627        2408 :   auto NodeBelow = InstantiatedValue{V.Val, V.DerefLevel + 1};
     628        2408 :   if (Graph.getNode(NodeBelow))
     629             :     return NodeBelow;
     630             :   return None;
     631             : }
     632             : 
     633         948 : static void processWorkListItem(const WorkListItem &Item, const CFLGraph &Graph,
     634             :                                 ReachabilitySet &ReachSet, AliasMemSet &MemSet,
     635             :                                 std::vector<WorkListItem> &WorkList) {
     636         948 :   auto FromNode = Item.From;
     637         948 :   auto ToNode = Item.To;
     638             : 
     639         948 :   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        2844 :   auto FromNodeBelow = getNodeBelow(Graph, FromNode);
     651        2844 :   auto ToNodeBelow = getNodeBelow(Graph, ToNode);
     652         988 :   if (FromNodeBelow && ToNodeBelow &&
     653          80 :       MemSet.insert(*FromNodeBelow, *ToNodeBelow)) {
     654          72 :     propagate(*FromNodeBelow, *ToNodeBelow,
     655             :               MatchState::FlowFromMemAliasNoReadWrite, ReachSet, WorkList);
     656         153 :     for (const auto &Mapping : ReachSet.reachableValueAliases(*FromNodeBelow)) {
     657         117 :       auto Src = Mapping.first;
     658         351 :       auto MemAliasPropagate = [&](MatchState FromState, MatchState ToState) {
     659         351 :         if (Mapping.second.test(static_cast<size_t>(FromState)))
     660          98 :           propagate(Src, *ToNodeBelow, ToState, ReachSet, WorkList);
     661         468 :       };
     662             : 
     663         117 :       MemAliasPropagate(MatchState::FlowFromReadOnly,
     664             :                         MatchState::FlowFromMemAliasReadOnly);
     665         117 :       MemAliasPropagate(MatchState::FlowToWriteOnly,
     666             :                         MatchState::FlowToMemAliasWriteOnly);
     667         117 :       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         948 :   auto NextAssignState = [&](MatchState State) {
     681        4416 :     for (const auto &AssignEdge : NodeInfo->Edges)
     682         624 :       propagate(FromNode, AssignEdge.Other, State, ReachSet, WorkList);
     683        1896 :   };
     684         358 :   auto NextRevAssignState = [&](MatchState State) {
     685        1534 :     for (const auto &RevAssignEdge : NodeInfo->ReverseEdges)
     686         102 :       propagate(FromNode, RevAssignEdge.Other, State, ReachSet, WorkList);
     687        1306 :   };
     688         808 :   auto NextMemState = [&](MatchState State) {
     689        1616 :     if (auto AliasSet = MemSet.getMemoryAliases(ToNode)) {
     690         452 :       for (const auto &MemAlias : *AliasSet)
     691          94 :         propagate(FromNode, MemAlias, State, ReachSet, WorkList);
     692             :     }
     693        1756 :   };
     694             : 
     695         948 :   switch (Item.State) {
     696         294 :   case MatchState::FlowFromReadOnly:
     697         294 :     NextRevAssignState(MatchState::FlowFromReadOnly);
     698         294 :     NextAssignState(MatchState::FlowToReadWrite);
     699         294 :     NextMemState(MatchState::FlowFromMemAliasReadOnly);
     700         294 :     break;
     701             : 
     702          36 :   case MatchState::FlowFromMemAliasNoReadWrite:
     703          36 :     NextRevAssignState(MatchState::FlowFromReadOnly);
     704          36 :     NextAssignState(MatchState::FlowToWriteOnly);
     705          36 :     break;
     706             : 
     707          28 :   case MatchState::FlowFromMemAliasReadOnly:
     708          28 :     NextRevAssignState(MatchState::FlowFromReadOnly);
     709          28 :     NextAssignState(MatchState::FlowToReadWrite);
     710          28 :     break;
     711             : 
     712         304 :   case MatchState::FlowToWriteOnly:
     713         304 :     NextAssignState(MatchState::FlowToWriteOnly);
     714         304 :     NextMemState(MatchState::FlowToMemAliasWriteOnly);
     715         304 :     break;
     716             : 
     717         210 :   case MatchState::FlowToReadWrite:
     718         210 :     NextAssignState(MatchState::FlowToReadWrite);
     719         210 :     NextMemState(MatchState::FlowToMemAliasReadWrite);
     720         210 :     break;
     721             : 
     722          18 :   case MatchState::FlowToMemAliasWriteOnly:
     723          18 :     NextAssignState(MatchState::FlowToWriteOnly);
     724          18 :     break;
     725             : 
     726          58 :   case MatchState::FlowToMemAliasReadWrite:
     727          58 :     NextAssignState(MatchState::FlowToReadWrite);
     728          58 :     break;
     729             :   }
     730         948 : }
     731             : 
     732          95 : static AliasAttrMap buildAttrMap(const CFLGraph &Graph,
     733             :                                  const ReachabilitySet &ReachSet) {
     734          95 :   AliasAttrMap AttrMap;
     735         380 :   std::vector<InstantiatedValue> WorkList, NextList;
     736             : 
     737             :   // Initialize each node with its original AliasAttrs in CFLGraph
     738          95 :   for (const auto &Mapping : Graph.value_mappings()) {
     739         369 :     auto Val = Mapping.first;
     740         369 :     auto &ValueInfo = Mapping.second;
     741        1300 :     for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
     742         562 :       auto Node = InstantiatedValue{Val, I};
     743        1124 :       AttrMap.add(Node, ValueInfo.getNodeInfoAtLevel(I).Attr);
     744         562 :       WorkList.push_back(Node);
     745             :     }
     746             :   }
     747             : 
     748         281 :   while (!WorkList.empty()) {
     749         961 :     for (const auto &Dst : WorkList) {
     750         775 :       auto DstAttr = AttrMap.getAttrs(Dst);
     751         775 :       if (DstAttr.none())
     752         282 :         continue;
     753             : 
     754             :       // Propagate attr on the same level
     755         825 :       for (const auto &Mapping : ReachSet.reachableValueAliases(Dst)) {
     756         332 :         auto Src = Mapping.first;
     757          92 :         if (AttrMap.add(Src, DstAttr))
     758          92 :           NextList.push_back(Src);
     759             :       }
     760             : 
     761             :       // Propagate attr to the levels below
     762         986 :       auto DstBelow = getNodeBelow(Graph, Dst);
     763         531 :       while (DstBelow) {
     764         280 :         if (AttrMap.add(*DstBelow, DstAttr)) {
     765         121 :           NextList.push_back(*DstBelow);
     766         121 :           break;
     767             :         }
     768          76 :         DstBelow = getNodeBelow(Graph, *DstBelow);
     769             :       }
     770             :     }
     771         186 :     WorkList.swap(NextList);
     772             :     NextList.clear();
     773             :   }
     774             : 
     775          95 :   return AttrMap;
     776             : }
     777             : 
     778             : CFLAndersAAResult::FunctionInfo
     779          95 : 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         285 :       const_cast<Function &>(Fn));
     784          95 :   auto &Graph = GraphBuilder.getCFLGraph();
     785             : 
     786         190 :   ReachabilitySet ReachSet;
     787         190 :   AliasMemSet MemSet;
     788             : 
     789         380 :   std::vector<WorkListItem> WorkList, NextList;
     790          95 :   initializeWorkList(WorkList, ReachSet, Graph);
     791             :   // TODO: make sure we don't stop before the fix point is reached
     792         270 :   while (!WorkList.empty()) {
     793        1123 :     for (const auto &Item : WorkList)
     794         948 :       processWorkListItem(Item, Graph, ReachSet, MemSet, NextList);
     795             : 
     796         175 :     NextList.swap(WorkList);
     797             :     NextList.clear();
     798             :   }
     799             : 
     800             :   // Now that we have all the reachability info, propagate AliasAttrs according
     801             :   // to it
     802         190 :   auto IValueAttrMap = buildAttrMap(Graph, ReachSet);
     803             : 
     804          95 :   return FunctionInfo(Fn, GraphBuilder.getReturnValues(), ReachSet,
     805         285 :                       std::move(IValueAttrMap));
     806             : }
     807             : 
     808          95 : void CFLAndersAAResult::scan(const Function &Fn) {
     809         570 :   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         190 :   auto FunInfo = buildInfoFrom(Fn);
     818         190 :   Cache[&Fn] = std::move(FunInfo);
     819         190 :   Handles.emplace_front(const_cast<Function *>(&Fn), this);
     820          95 : }
     821             : 
     822           0 : void CFLAndersAAResult::evict(const Function *Fn) { Cache.erase(Fn); }
     823             : 
     824             : const Optional<CFLAndersAAResult::FunctionInfo> &
     825         729 : CFLAndersAAResult::ensureCached(const Function &Fn) {
     826         729 :   auto Iter = Cache.find(&Fn);
     827        2187 :   if (Iter == Cache.end()) {
     828          95 :     scan(Fn);
     829          95 :     Iter = Cache.find(&Fn);
     830             :     assert(Iter != Cache.end());
     831             :     assert(Iter->second.hasValue());
     832             :   }
     833         729 :   return Iter->second;
     834             : }
     835             : 
     836          64 : const AliasSummary *CFLAndersAAResult::getAliasSummary(const Function &Fn) {
     837          64 :   auto &FunInfo = ensureCached(Fn);
     838          64 :   if (FunInfo.hasValue())
     839         128 :     return &FunInfo->getAliasSummary();
     840             :   else
     841             :     return nullptr;
     842             : }
     843             : 
     844         665 : AliasResult CFLAndersAAResult::query(const MemoryLocation &LocA,
     845             :                                      const MemoryLocation &LocB) {
     846         665 :   auto *ValA = LocA.Ptr;
     847         665 :   auto *ValB = LocB.Ptr;
     848             : 
     849        1995 :   if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
     850             :     return NoAlias;
     851             : 
     852         651 :   auto *Fn = parentFunctionOfValue(ValA);
     853         651 :   if (!Fn) {
     854          14 :     Fn = parentFunctionOfValue(ValB);
     855          14 :     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         665 :   auto &FunInfo = ensureCached(*Fn);
     868             : 
     869             :   // AliasMap lookup
     870         665 :   if (FunInfo->mayAlias(ValA, LocA.Size, ValB, LocB.Size))
     871             :     return MayAlias;
     872         392 :   return NoAlias;
     873             : }
     874             : 
     875         665 : AliasResult CFLAndersAAResult::alias(const MemoryLocation &LocA,
     876             :                                      const MemoryLocation &LocB) {
     877         665 :   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         679 :   if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr))
     886             :     return AAResultBase::alias(LocA, LocB);
     887             : 
     888         665 :   AliasResult QueryResult = query(LocA, LocB);
     889         665 :   if (QueryResult == MayAlias)
     890         273 :     return AAResultBase::alias(LocA, LocB);
     891             : 
     892             :   return QueryResult;
     893             : }
     894             : 
     895             : AnalysisKey CFLAndersAA::Key;
     896             : 
     897          41 : CFLAndersAAResult CFLAndersAA::run(Function &F, FunctionAnalysisManager &AM) {
     898          41 :   return CFLAndersAAResult(AM.getResult<TargetLibraryAnalysis>(F));
     899             : }
     900             : 
     901             : char CFLAndersAAWrapperPass::ID = 0;
     902      293859 : INITIALIZE_PASS(CFLAndersAAWrapperPass, "cfl-anders-aa",
     903             :                 "Inclusion-Based CFL Alias Analysis", false, true)
     904             : 
     905           0 : ImmutablePass *llvm::createCFLAndersAAWrapperPass() {
     906           0 :   return new CFLAndersAAWrapperPass();
     907             : }
     908             : 
     909          60 : CFLAndersAAWrapperPass::CFLAndersAAWrapperPass() : ImmutablePass(ID) {
     910          20 :   initializeCFLAndersAAWrapperPassPass(*PassRegistry::getPassRegistry());
     911          20 : }
     912             : 
     913          20 : void CFLAndersAAWrapperPass::initializePass() {
     914          20 :   auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
     915          60 :   Result.reset(new CFLAndersAAResult(TLIWP.getTLI()));
     916          20 : }
     917             : 
     918          20 : void CFLAndersAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
     919          40 :   AU.setPreservesAll();
     920          20 :   AU.addRequired<TargetLibraryInfoWrapperPass>();
     921          20 : }

Generated by: LCOV version 1.13