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