Home | History | Annotate | Download | only in Analysis 
      1 //=- CFLAndersAliasAnalysis.h - 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 /// \file
     10 /// This is the interface for LLVM's inclusion-based alias analysis
     11 /// implemented with CFL graph reachability.
     12 ///
     13 //===----------------------------------------------------------------------===//
     14 
     15 #ifndef LLVM_ANALYSIS_CFLANDERSALIASANALYSIS_H
     16 #define LLVM_ANALYSIS_CFLANDERSALIASANALYSIS_H
     17 
     18 #include "llvm/ADT/DenseMap.h"
     19 #include "llvm/ADT/Optional.h"
     20 #include "llvm/Analysis/AliasAnalysis.h"
     21 #include "llvm/IR/Function.h"
     22 #include "llvm/IR/ValueHandle.h"
     23 #include "llvm/Pass.h"
     24 #include <forward_list>
     25 
     26 namespace llvm {
     27 
     28 class TargetLibraryInfo;
     29 
     30 namespace cflaa {
     31 struct AliasSummary;
     32 }
     33 
     34 class CFLAndersAAResult : public AAResultBase<CFLAndersAAResult> {
     35   friend AAResultBase<CFLAndersAAResult>;
     36   class FunctionInfo;
     37 
     38 public:
     39   explicit CFLAndersAAResult(const TargetLibraryInfo &);
     40   CFLAndersAAResult(CFLAndersAAResult &&);
     41   ~CFLAndersAAResult();
     42 
     43   /// Handle invalidation events from the new pass manager.
     44   /// By definition, this result is stateless and so remains valid.
     45   bool invalidate(Function &, const PreservedAnalyses &,
     46                   FunctionAnalysisManager::Invalidator &) {
     47     return false;
     48   }
     49   /// Evict the given function from cache
     50   void evict(const Function &Fn);
     51 
     52   /// \brief Get the alias summary for the given function
     53   /// Return nullptr if the summary is not found or not available
     54   const cflaa::AliasSummary *getAliasSummary(const Function &);
     55 
     56   AliasResult query(const MemoryLocation &, const MemoryLocation &);
     57   AliasResult alias(const MemoryLocation &, const MemoryLocation &);
     58 
     59 private:
     60   struct FunctionHandle final : public CallbackVH {
     61     FunctionHandle(Function *Fn, CFLAndersAAResult *Result)
     62         : CallbackVH(Fn), Result(Result) {
     63       assert(Fn != nullptr);
     64       assert(Result != nullptr);
     65     }
     66 
     67     void deleted() override { removeSelfFromCache(); }
     68     void allUsesReplacedWith(Value *) override { removeSelfFromCache(); }
     69 
     70   private:
     71     CFLAndersAAResult *Result;
     72 
     73     void removeSelfFromCache() {
     74       assert(Result != nullptr);
     75       auto *Val = getValPtr();
     76       Result->evict(*cast<Function>(Val));
     77       setValPtr(nullptr);
     78     }
     79   };
     80 
     81   /// \brief Ensures that the given function is available in the cache.
     82   /// Returns the appropriate entry from the cache.
     83   const Optional<FunctionInfo> &ensureCached(const Function &);
     84 
     85   /// \brief Inserts the given Function into the cache.
     86   void scan(const Function &);
     87 
     88   /// \brief Build summary for a given function
     89   FunctionInfo buildInfoFrom(const Function &);
     90 
     91   const TargetLibraryInfo &TLI;
     92 
     93   /// \brief Cached mapping of Functions to their StratifiedSets.
     94   /// If a function's sets are currently being built, it is marked
     95   /// in the cache as an Optional without a value. This way, if we
     96   /// have any kind of recursion, it is discernable from a function
     97   /// that simply has empty sets.
     98   DenseMap<const Function *, Optional<FunctionInfo>> Cache;
     99 
    100   std::forward_list<FunctionHandle> Handles;
    101 };
    102 
    103 /// Analysis pass providing a never-invalidated alias analysis result.
    104 ///
    105 /// FIXME: We really should refactor CFL to use the analysis more heavily, and
    106 /// in particular to leverage invalidation to trigger re-computation.
    107 class CFLAndersAA : public AnalysisInfoMixin<CFLAndersAA> {
    108   friend AnalysisInfoMixin<CFLAndersAA>;
    109   static AnalysisKey Key;
    110 
    111 public:
    112   typedef CFLAndersAAResult Result;
    113 
    114   CFLAndersAAResult run(Function &F, FunctionAnalysisManager &AM);
    115 };
    116 
    117 /// Legacy wrapper pass to provide the CFLAndersAAResult object.
    118 class CFLAndersAAWrapperPass : public ImmutablePass {
    119   std::unique_ptr<CFLAndersAAResult> Result;
    120 
    121 public:
    122   static char ID;
    123 
    124   CFLAndersAAWrapperPass();
    125 
    126   CFLAndersAAResult &getResult() { return *Result; }
    127   const CFLAndersAAResult &getResult() const { return *Result; }
    128 
    129   void initializePass() override;
    130   void getAnalysisUsage(AnalysisUsage &AU) const override;
    131 };
    132 
    133 //===--------------------------------------------------------------------===//
    134 //
    135 // createCFLAndersAAWrapperPass - This pass implements a set-based approach to
    136 // alias analysis.
    137 //
    138 ImmutablePass *createCFLAndersAAWrapperPass();
    139 }
    140 
    141 #endif
    142