Home | History | Annotate | Download | only in Analysis 
      1 //===- CFLAliasAnalysis.h - CFL-Based Alias Analysis Interface ---*- 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 /// \file
     10 /// This is the interface for LLVM's primary stateless and local alias analysis.
     11 ///
     12 //===----------------------------------------------------------------------===//
     13 
     14 #ifndef LLVM_ANALYSIS_CFLALIASANALYSIS_H
     15 #define LLVM_ANALYSIS_CFLALIASANALYSIS_H
     16 
     17 #include "llvm/Analysis/AliasAnalysis.h"
     18 #include "llvm/ADT/DenseMap.h"
     19 #include "llvm/ADT/None.h"
     20 #include "llvm/ADT/Optional.h"
     21 #include "llvm/IR/Function.h"
     22 #include "llvm/IR/Module.h"
     23 #include "llvm/IR/ValueHandle.h"
     24 #include "llvm/Pass.h"
     25 #include <forward_list>
     26 
     27 namespace llvm {
     28 
     29 class CFLAAResult : public AAResultBase<CFLAAResult> {
     30   friend AAResultBase<CFLAAResult>;
     31 
     32   struct FunctionInfo;
     33 
     34 public:
     35   explicit CFLAAResult(const TargetLibraryInfo &TLI);
     36   CFLAAResult(CFLAAResult &&Arg);
     37 
     38   /// Handle invalidation events from the new pass manager.
     39   ///
     40   /// By definition, this result is stateless and so remains valid.
     41   bool invalidate(Function &, const PreservedAnalyses &) { return false; }
     42 
     43   /// \brief Inserts the given Function into the cache.
     44   void scan(Function *Fn);
     45 
     46   void evict(Function *Fn);
     47 
     48   /// \brief Ensures that the given function is available in the cache.
     49   /// Returns the appropriate entry from the cache.
     50   const Optional<FunctionInfo> &ensureCached(Function *Fn);
     51 
     52   AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB);
     53 
     54   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
     55     if (LocA.Ptr == LocB.Ptr) {
     56       if (LocA.Size == LocB.Size) {
     57         return MustAlias;
     58       } else {
     59         return PartialAlias;
     60       }
     61     }
     62 
     63     // Comparisons between global variables and other constants should be
     64     // handled by BasicAA.
     65     // TODO: ConstantExpr handling -- CFLAA may report NoAlias when comparing
     66     // a GlobalValue and ConstantExpr, but every query needs to have at least
     67     // one Value tied to a Function, and neither GlobalValues nor ConstantExprs
     68     // are.
     69     if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr)) {
     70       return AAResultBase::alias(LocA, LocB);
     71     }
     72 
     73     AliasResult QueryResult = query(LocA, LocB);
     74     if (QueryResult == MayAlias)
     75       return AAResultBase::alias(LocA, LocB);
     76 
     77     return QueryResult;
     78   }
     79 
     80 private:
     81   struct FunctionHandle final : public CallbackVH {
     82     FunctionHandle(Function *Fn, CFLAAResult *Result)
     83         : CallbackVH(Fn), Result(Result) {
     84       assert(Fn != nullptr);
     85       assert(Result != nullptr);
     86     }
     87 
     88     void deleted() override { removeSelfFromCache(); }
     89     void allUsesReplacedWith(Value *) override { removeSelfFromCache(); }
     90 
     91   private:
     92     CFLAAResult *Result;
     93 
     94     void removeSelfFromCache() {
     95       assert(Result != nullptr);
     96       auto *Val = getValPtr();
     97       Result->evict(cast<Function>(Val));
     98       setValPtr(nullptr);
     99     }
    100   };
    101 
    102   /// \brief Cached mapping of Functions to their StratifiedSets.
    103   /// If a function's sets are currently being built, it is marked
    104   /// in the cache as an Optional without a value. This way, if we
    105   /// have any kind of recursion, it is discernable from a function
    106   /// that simply has empty sets.
    107   DenseMap<Function *, Optional<FunctionInfo>> Cache;
    108   std::forward_list<FunctionHandle> Handles;
    109 
    110   FunctionInfo buildSetsFrom(Function *F);
    111 };
    112 
    113 /// Analysis pass providing a never-invalidated alias analysis result.
    114 ///
    115 /// FIXME: We really should refactor CFL to use the analysis more heavily, and
    116 /// in particular to leverage invalidation to trigger re-computation of sets.
    117 class CFLAA {
    118 public:
    119   typedef CFLAAResult Result;
    120 
    121   /// \brief Opaque, unique identifier for this analysis pass.
    122   static void *ID() { return (void *)&PassID; }
    123 
    124   CFLAAResult run(Function &F, AnalysisManager<Function> *AM);
    125 
    126   /// \brief Provide access to a name for this pass for debugging purposes.
    127   static StringRef name() { return "CFLAA"; }
    128 
    129 private:
    130   static char PassID;
    131 };
    132 
    133 /// Legacy wrapper pass to provide the CFLAAResult object.
    134 class CFLAAWrapperPass : public ImmutablePass {
    135   std::unique_ptr<CFLAAResult> Result;
    136 
    137 public:
    138   static char ID;
    139 
    140   CFLAAWrapperPass();
    141 
    142   CFLAAResult &getResult() { return *Result; }
    143   const CFLAAResult &getResult() const { return *Result; }
    144 
    145   bool doInitialization(Module &M) override;
    146   bool doFinalization(Module &M) override;
    147   void getAnalysisUsage(AnalysisUsage &AU) const override;
    148 };
    149 
    150 //===--------------------------------------------------------------------===//
    151 //
    152 // createCFLAAWrapperPass - This pass implements a set-based approach to
    153 // alias analysis.
    154 //
    155 ImmutablePass *createCFLAAWrapperPass();
    156 }
    157 
    158 #endif
    159