LCOV - code coverage report
Current view: top level - lib/Analysis - CFLSteensAliasAnalysis.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 129 135 95.6 %
Date: 2017-09-14 15:23:50 Functions: 17 20 85.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- CFLSteensAliasAnalysis.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-base, summary-based alias analysis algorithm. It
      11             : // does not depend on types. The algorithm is a mixture of the one described in
      12             : // "Demand-driven alias analysis for C" by Xin Zheng and Radu Rugina, and "Fast
      13             : // algorithms for Dyck-CFL-reachability with applications to Alias Analysis" by
      14             : // Zhang Q, Lyu M R, Yuan H, and Su Z. -- to summarize the papers, we build a
      15             : // graph of the uses of a variable, where each node is a memory location, and
      16             : // each edge is an action that happened on that memory location.  The "actions"
      17             : // can be one of Dereference, Reference, or Assign. The precision of this
      18             : // analysis is roughly the same as that of an one level context-sensitive
      19             : // Steensgaard's algorithm.
      20             : //
      21             : // Two variables are considered as aliasing iff you can reach one value's node
      22             : // from the other value's node and the language formed by concatenating all of
      23             : // the edge labels (actions) conforms to a context-free grammar.
      24             : //
      25             : // Because this algorithm requires a graph search on each query, we execute the
      26             : // algorithm outlined in "Fast algorithms..." (mentioned above)
      27             : // in order to transform the graph into sets of variables that may alias in
      28             : // ~nlogn time (n = number of variables), which makes queries take constant
      29             : // time.
      30             : //===----------------------------------------------------------------------===//
      31             : 
      32             : // N.B. AliasAnalysis as a whole is phrased as a FunctionPass at the moment, and
      33             : // CFLSteensAA is interprocedural. This is *technically* A Bad Thing, because
      34             : // FunctionPasses are only allowed to inspect the Function that they're being
      35             : // run on. Realistically, this likely isn't a problem until we allow
      36             : // FunctionPasses to run concurrently.
      37             : 
      38             : #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
      39             : #include "AliasAnalysisSummary.h"
      40             : #include "CFLGraph.h"
      41             : #include "StratifiedSets.h"
      42             : #include "llvm/ADT/DenseMap.h"
      43             : #include "llvm/ADT/Optional.h"
      44             : #include "llvm/ADT/SmallVector.h"
      45             : #include "llvm/Analysis/TargetLibraryInfo.h"
      46             : #include "llvm/IR/Constants.h"
      47             : #include "llvm/IR/Function.h"
      48             : #include "llvm/IR/Type.h"
      49             : #include "llvm/IR/Value.h"
      50             : #include "llvm/Pass.h"
      51             : #include "llvm/Support/Debug.h"
      52             : #include "llvm/Support/raw_ostream.h"
      53             : #include <algorithm>
      54             : #include <cassert>
      55             : #include <limits>
      56             : #include <memory>
      57             : #include <utility>
      58             : 
      59             : using namespace llvm;
      60             : using namespace llvm::cflaa;
      61             : 
      62             : #define DEBUG_TYPE "cfl-steens-aa"
      63             : 
      64          76 : CFLSteensAAResult::CFLSteensAAResult(const TargetLibraryInfo &TLI)
      65         228 :     : AAResultBase(), TLI(TLI) {}
      66          84 : CFLSteensAAResult::CFLSteensAAResult(CFLSteensAAResult &&Arg)
      67         336 :     : AAResultBase(std::move(Arg)), TLI(Arg.TLI) {}
      68             : CFLSteensAAResult::~CFLSteensAAResult() = default;
      69             : 
      70             : /// Information we have about a function and would like to keep around.
      71         460 : class CFLSteensAAResult::FunctionInfo {
      72             :   StratifiedSets<InstantiatedValue> Sets;
      73             :   AliasSummary Summary;
      74             : 
      75             : public:
      76             :   FunctionInfo(Function &Fn, const SmallVectorImpl<Value *> &RetVals,
      77             :                StratifiedSets<InstantiatedValue> S);
      78             : 
      79             :   const StratifiedSets<InstantiatedValue> &getStratifiedSets() const {
      80        2788 :     return Sets;
      81             :   }
      82             : 
      83          64 :   const AliasSummary &getAliasSummary() const { return Summary; }
      84             : };
      85             : 
      86             : const StratifiedIndex StratifiedLink::SetSentinel =
      87             :     std::numeric_limits<StratifiedIndex>::max();
      88             : 
      89             : //===----------------------------------------------------------------------===//
      90             : // Function declarations that require types defined in the namespace above
      91             : //===----------------------------------------------------------------------===//
      92             : 
      93             : /// Determines whether it would be pointless to add the given Value to our sets.
      94         922 : static bool canSkipAddingToSets(Value *Val) {
      95             :   // Constants can share instances, which may falsely unify multiple
      96             :   // sets, e.g. in
      97             :   // store i32* null, i32** %ptr1
      98             :   // store i32* null, i32** %ptr2
      99             :   // clearly ptr1 and ptr2 should not be unified into the same set, so
     100             :   // we should filter out the (potentially shared) instance to
     101             :   // i32* null.
     102         922 :   if (isa<Constant>(Val)) {
     103             :     // TODO: Because all of these things are constant, we can determine whether
     104             :     // the data is *actually* mutable at graph building time. This will probably
     105             :     // come for free/cheap with offset awareness.
     106          52 :     bool CanStoreMutableData = isa<GlobalValue>(Val) ||
     107          10 :                                isa<ConstantExpr>(Val) ||
     108          42 :                                isa<ConstantAggregate>(Val);
     109          42 :     return !CanStoreMutableData;
     110             :   }
     111             : 
     112             :   return false;
     113             : }
     114             : 
     115         115 : CFLSteensAAResult::FunctionInfo::FunctionInfo(
     116             :     Function &Fn, const SmallVectorImpl<Value *> &RetVals,
     117         115 :     StratifiedSets<InstantiatedValue> S)
     118         345 :     : Sets(std::move(S)) {
     119             :   // Historically, an arbitrary upper-bound of 50 args was selected. We may want
     120             :   // to remove this if it doesn't really matter in practice.
     121         115 :   if (Fn.arg_size() > MaxSupportedArgsInSummary)
     122           0 :     return;
     123             : 
     124         230 :   DenseMap<StratifiedIndex, InterfaceValue> InterfaceMap;
     125             : 
     126             :   // Our intention here is to record all InterfaceValues that share the same
     127             :   // StratifiedIndex in RetParamRelations. For each valid InterfaceValue, we
     128             :   // have its StratifiedIndex scanned here and check if the index is presented
     129             :   // in InterfaceMap: if it is not, we add the correspondence to the map;
     130             :   // otherwise, an aliasing relation is found and we add it to
     131             :   // RetParamRelations.
     132             : 
     133             :   auto AddToRetParamRelations = [&](unsigned InterfaceIndex,
     134         164 :                                     StratifiedIndex SetIndex) {
     135         164 :     unsigned Level = 0;
     136             :     while (true) {
     137         321 :       InterfaceValue CurrValue{InterfaceIndex, Level};
     138             : 
     139         321 :       auto Itr = InterfaceMap.find(SetIndex);
     140         642 :       if (Itr != InterfaceMap.end()) {
     141          66 :         if (CurrValue != Itr->second)
     142         389 :           Summary.RetParamRelations.push_back(
     143          66 :               ExternalRelation{CurrValue, Itr->second, UnknownOffset});
     144         164 :         break;
     145             :       }
     146             : 
     147         576 :       auto &Link = Sets.getLink(SetIndex);
     148         864 :       InterfaceMap.insert(std::make_pair(SetIndex, CurrValue));
     149         288 :       auto ExternalAttrs = getExternallyVisibleAttrs(Link.Attrs);
     150         288 :       if (ExternalAttrs.any())
     151          70 :         Summary.RetParamAttributes.push_back(
     152          70 :             ExternalAttribute{CurrValue, ExternalAttrs});
     153             : 
     154         288 :       if (!Link.hasBelow())
     155             :         break;
     156             : 
     157         157 :       ++Level;
     158         157 :       SetIndex = Link.Below;
     159         157 :     }
     160         279 :   };
     161             : 
     162             :   // Populate RetParamRelations for return values
     163         369 :   for (auto *RetVal : RetVals) {
     164             :     assert(RetVal != nullptr);
     165             :     assert(RetVal->getType()->isPointerTy());
     166          48 :     auto RetInfo = Sets.find(InstantiatedValue{RetVal, 0});
     167          24 :     if (RetInfo.hasValue())
     168          24 :       AddToRetParamRelations(0, RetInfo->Index);
     169             :   }
     170             : 
     171             :   // Populate RetParamRelations for parameters
     172         115 :   unsigned I = 0;
     173         267 :   for (auto &Param : Fn.args()) {
     174         304 :     if (Param.getType()->isPointerTy()) {
     175         280 :       auto ParamInfo = Sets.find(InstantiatedValue{&Param, 0});
     176         140 :       if (ParamInfo.hasValue())
     177         140 :         AddToRetParamRelations(I + 1, ParamInfo->Index);
     178             :     }
     179         152 :     ++I;
     180             :   }
     181             : }
     182             : 
     183             : // Builds the graph + StratifiedSets for a function.
     184         115 : CFLSteensAAResult::FunctionInfo CFLSteensAAResult::buildSetsFrom(Function *Fn) {
     185         230 :   CFLGraphBuilder<CFLSteensAAResult> GraphBuilder(*this, TLI, *Fn);
     186         230 :   StratifiedSetsBuilder<InstantiatedValue> SetBuilder;
     187             : 
     188             :   // Add all CFLGraph nodes and all Dereference edges to StratifiedSets
     189         115 :   auto &Graph = GraphBuilder.getCFLGraph();
     190         115 :   for (const auto &Mapping : Graph.value_mappings()) {
     191         461 :     auto Val = Mapping.first;
     192         461 :     if (canSkipAddingToSets(Val))
     193           0 :       continue;
     194         461 :     auto &ValueInfo = Mapping.second;
     195             : 
     196             :     assert(ValueInfo.getNumLevels() > 0);
     197         461 :     SetBuilder.add(InstantiatedValue{Val, 0});
     198         461 :     SetBuilder.noteAttributes(InstantiatedValue{Val, 0},
     199         461 :                               ValueInfo.getNodeInfoAtLevel(0).Attr);
     200        1177 :     for (unsigned I = 0, E = ValueInfo.getNumLevels() - 1; I < E; ++I) {
     201         255 :       SetBuilder.add(InstantiatedValue{Val, I + 1});
     202         255 :       SetBuilder.noteAttributes(InstantiatedValue{Val, I + 1},
     203         510 :                                 ValueInfo.getNodeInfoAtLevel(I + 1).Attr);
     204         255 :       SetBuilder.addBelow(InstantiatedValue{Val, I},
     205         510 :                           InstantiatedValue{Val, I + 1});
     206             :     }
     207             :   }
     208             : 
     209             :   // Add all assign edges to StratifiedSets
     210         115 :   for (const auto &Mapping : Graph.value_mappings()) {
     211         461 :     auto Val = Mapping.first;
     212         461 :     if (canSkipAddingToSets(Val))
     213           0 :       continue;
     214         461 :     auto &ValueInfo = Mapping.second;
     215             : 
     216        1638 :     for (unsigned I = 0, E = ValueInfo.getNumLevels(); I < E; ++I) {
     217         716 :       auto Src = InstantiatedValue{Val, I};
     218        3079 :       for (auto &Edge : ValueInfo.getNodeInfoAtLevel(I).Edges)
     219         215 :         SetBuilder.addWith(Src, Edge.Other);
     220             :     }
     221             :   }
     222             : 
     223         230 :   return FunctionInfo(*Fn, GraphBuilder.getReturnValues(), SetBuilder.build());
     224             : }
     225             : 
     226         115 : void CFLSteensAAResult::scan(Function *Fn) {
     227         690 :   auto InsertPair = Cache.insert(std::make_pair(Fn, Optional<FunctionInfo>()));
     228             :   (void)InsertPair;
     229             :   assert(InsertPair.second &&
     230             :          "Trying to scan a function that has already been cached");
     231             : 
     232             :   // Note that we can't do Cache[Fn] = buildSetsFrom(Fn) here: the function call
     233             :   // may get evaluated after operator[], potentially triggering a DenseMap
     234             :   // resize and invalidating the reference returned by operator[]
     235         230 :   auto FunInfo = buildSetsFrom(Fn);
     236         230 :   Cache[Fn] = std::move(FunInfo);
     237             : 
     238         230 :   Handles.emplace_front(Fn, this);
     239         115 : }
     240             : 
     241           0 : void CFLSteensAAResult::evict(Function *Fn) { Cache.erase(Fn); }
     242             : 
     243             : /// Ensures that the given function is available in the cache, and returns the
     244             : /// entry.
     245             : const Optional<CFLSteensAAResult::FunctionInfo> &
     246        2852 : CFLSteensAAResult::ensureCached(Function *Fn) {
     247        2852 :   auto Iter = Cache.find(Fn);
     248        8556 :   if (Iter == Cache.end()) {
     249         115 :     scan(Fn);
     250         115 :     Iter = Cache.find(Fn);
     251             :     assert(Iter != Cache.end());
     252             :     assert(Iter->second.hasValue());
     253             :   }
     254        2852 :   return Iter->second;
     255             : }
     256             : 
     257          64 : const AliasSummary *CFLSteensAAResult::getAliasSummary(Function &Fn) {
     258          64 :   auto &FunInfo = ensureCached(&Fn);
     259          64 :   if (FunInfo.hasValue())
     260         128 :     return &FunInfo->getAliasSummary();
     261             :   else
     262             :     return nullptr;
     263             : }
     264             : 
     265        2790 : AliasResult CFLSteensAAResult::query(const MemoryLocation &LocA,
     266             :                                      const MemoryLocation &LocB) {
     267        2790 :   auto *ValA = const_cast<Value *>(LocA.Ptr);
     268        2790 :   auto *ValB = const_cast<Value *>(LocB.Ptr);
     269             : 
     270        8370 :   if (!ValA->getType()->isPointerTy() || !ValB->getType()->isPointerTy())
     271             :     return NoAlias;
     272             : 
     273        2790 :   Function *Fn = nullptr;
     274        2790 :   Function *MaybeFnA = const_cast<Function *>(parentFunctionOfValue(ValA));
     275        2790 :   Function *MaybeFnB = const_cast<Function *>(parentFunctionOfValue(ValB));
     276        2790 :   if (!MaybeFnA && !MaybeFnB) {
     277             :     // The only times this is known to happen are when globals + InlineAsm are
     278             :     // involved
     279             :     DEBUG(dbgs()
     280             :           << "CFLSteensAA: could not extract parent function information.\n");
     281             :     return MayAlias;
     282             :   }
     283             : 
     284        2788 :   if (MaybeFnA) {
     285             :     Fn = MaybeFnA;
     286             :     assert((!MaybeFnB || MaybeFnB == MaybeFnA) &&
     287             :            "Interprocedural queries not supported");
     288             :   } else {
     289          39 :     Fn = MaybeFnB;
     290             :   }
     291             : 
     292             :   assert(Fn != nullptr);
     293        2788 :   auto &MaybeInfo = ensureCached(Fn);
     294             :   assert(MaybeInfo.hasValue());
     295             : 
     296        5576 :   auto &Sets = MaybeInfo->getStratifiedSets();
     297        2788 :   auto MaybeA = Sets.find(InstantiatedValue{ValA, 0});
     298        2788 :   if (!MaybeA.hasValue())
     299             :     return MayAlias;
     300             : 
     301        2783 :   auto MaybeB = Sets.find(InstantiatedValue{ValB, 0});
     302        2783 :   if (!MaybeB.hasValue())
     303             :     return MayAlias;
     304             : 
     305        2782 :   auto SetA = *MaybeA;
     306        2782 :   auto SetB = *MaybeB;
     307        5564 :   auto AttrsA = Sets.getLink(SetA.Index).Attrs;
     308        5564 :   auto AttrsB = Sets.getLink(SetB.Index).Attrs;
     309             : 
     310             :   // If both values are local (meaning the corresponding set has attribute
     311             :   // AttrNone or AttrEscaped), then we know that CFLSteensAA fully models them:
     312             :   // they may-alias each other if and only if they are in the same set.
     313             :   // If at least one value is non-local (meaning it either is global/argument or
     314             :   // it comes from unknown sources like integer cast), the situation becomes a
     315             :   // bit more interesting. We follow three general rules described below:
     316             :   // - Non-local values may alias each other
     317             :   // - AttrNone values do not alias any non-local values
     318             :   // - AttrEscaped do not alias globals/arguments, but they may alias
     319             :   // AttrUnknown values
     320        2782 :   if (SetA.Index == SetB.Index)
     321             :     return MayAlias;
     322        4194 :   if (AttrsA.none() || AttrsB.none())
     323             :     return NoAlias;
     324        1907 :   if (hasUnknownOrCallerAttr(AttrsA) || hasUnknownOrCallerAttr(AttrsB))
     325             :     return MayAlias;
     326         731 :   if (isGlobalOrArgAttr(AttrsA) && isGlobalOrArgAttr(AttrsB))
     327             :     return MayAlias;
     328             :   return NoAlias;
     329             : }
     330             : 
     331             : AnalysisKey CFLSteensAA::Key;
     332             : 
     333          42 : CFLSteensAAResult CFLSteensAA::run(Function &F, FunctionAnalysisManager &AM) {
     334          42 :   return CFLSteensAAResult(AM.getResult<TargetLibraryAnalysis>(F));
     335             : }
     336             : 
     337             : char CFLSteensAAWrapperPass::ID = 0;
     338      293901 : INITIALIZE_PASS(CFLSteensAAWrapperPass, "cfl-steens-aa",
     339             :                 "Unification-Based CFL Alias Analysis", false, true)
     340             : 
     341           0 : ImmutablePass *llvm::createCFLSteensAAWrapperPass() {
     342           0 :   return new CFLSteensAAWrapperPass();
     343             : }
     344             : 
     345         102 : CFLSteensAAWrapperPass::CFLSteensAAWrapperPass() : ImmutablePass(ID) {
     346          34 :   initializeCFLSteensAAWrapperPassPass(*PassRegistry::getPassRegistry());
     347          34 : }
     348             : 
     349          34 : void CFLSteensAAWrapperPass::initializePass() {
     350          34 :   auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
     351         102 :   Result.reset(new CFLSteensAAResult(TLIWP.getTLI()));
     352          34 : }
     353             : 
     354          34 : void CFLSteensAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
     355          68 :   AU.setPreservesAll();
     356          34 :   AU.addRequired<TargetLibraryInfoWrapperPass>();
     357          34 : }

Generated by: LCOV version 1.13