Home | History | Annotate | Download | only in Analysis 
      1 //==- CFLSteensAliasAnalysis.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 unification-based alias analysis
     11 /// implemented with CFL graph reachability.
     12 ///
     13 //===----------------------------------------------------------------------===//
     14 
     15 #ifndef LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H
     16 #define LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_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/Analysis/MemoryLocation.h"
     23 #include "llvm/IR/PassManager.h"
     24 #include "llvm/Pass.h"
     25 #include "llvm/Support/Casting.h"
     26 #include <forward_list>
     27 #include <memory>
     28 
     29 namespace llvm {
     30 
     31 class Function;
     32 class TargetLibraryInfo;
     33 
     34 namespace cflaa {
     35 
     36 struct AliasSummary;
     37 
     38 } // end namespace cflaa
     39 
     40 class CFLSteensAAResult : public AAResultBase<CFLSteensAAResult> {
     41   friend AAResultBase<CFLSteensAAResult>;
     42 
     43   class FunctionInfo;
     44 
     45 public:
     46   explicit CFLSteensAAResult(const TargetLibraryInfo &TLI);
     47   CFLSteensAAResult(CFLSteensAAResult &&Arg);
     48   ~CFLSteensAAResult();
     49 
     50   /// Handle invalidation events from the new pass manager.
     51   ///
     52   /// By definition, this result is stateless and so remains valid.
     53   bool invalidate(Function &, const PreservedAnalyses &,
     54                   FunctionAnalysisManager::Invalidator &) {
     55     return false;
     56   }
     57 
     58   /// \brief Inserts the given Function into the cache.
     59   void scan(Function *Fn);
     60 
     61   void evict(Function *Fn);
     62 
     63   /// \brief Ensures that the given function is available in the cache.
     64   /// Returns the appropriate entry from the cache.
     65   const Optional<FunctionInfo> &ensureCached(Function *Fn);
     66 
     67   /// \brief Get the alias summary for the given function
     68   /// Return nullptr if the summary is not found or not available
     69   const cflaa::AliasSummary *getAliasSummary(Function &Fn);
     70 
     71   AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB);
     72 
     73   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
     74     if (LocA.Ptr == LocB.Ptr)
     75       return MustAlias;
     76 
     77     // Comparisons between global variables and other constants should be
     78     // handled by BasicAA.
     79     // CFLSteensAA may report NoAlias when comparing a GlobalValue and
     80     // ConstantExpr, but every query needs to have at least one Value tied to a
     81     // Function, and neither GlobalValues nor ConstantExprs are.
     82     if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr))
     83       return AAResultBase::alias(LocA, LocB);
     84 
     85     AliasResult QueryResult = query(LocA, LocB);
     86     if (QueryResult == MayAlias)
     87       return AAResultBase::alias(LocA, LocB);
     88 
     89     return QueryResult;
     90   }
     91 
     92 private:
     93   const TargetLibraryInfo &TLI;
     94 
     95   /// \brief Cached mapping of Functions to their StratifiedSets.
     96   /// If a function's sets are currently being built, it is marked
     97   /// in the cache as an Optional without a value. This way, if we
     98   /// have any kind of recursion, it is discernable from a function
     99   /// that simply has empty sets.
    100   DenseMap<Function *, Optional<FunctionInfo>> Cache;
    101   std::forward_list<cflaa::FunctionHandle<CFLSteensAAResult>> Handles;
    102 
    103   FunctionInfo buildSetsFrom(Function *F);
    104 };
    105 
    106 /// Analysis pass providing a never-invalidated alias analysis result.
    107 ///
    108 /// FIXME: We really should refactor CFL to use the analysis more heavily, and
    109 /// in particular to leverage invalidation to trigger re-computation of sets.
    110 class CFLSteensAA : public AnalysisInfoMixin<CFLSteensAA> {
    111   friend AnalysisInfoMixin<CFLSteensAA>;
    112 
    113   static AnalysisKey Key;
    114 
    115 public:
    116   using Result = CFLSteensAAResult;
    117 
    118   CFLSteensAAResult run(Function &F, FunctionAnalysisManager &AM);
    119 };
    120 
    121 /// Legacy wrapper pass to provide the CFLSteensAAResult object.
    122 class CFLSteensAAWrapperPass : public ImmutablePass {
    123   std::unique_ptr<CFLSteensAAResult> Result;
    124 
    125 public:
    126   static char ID;
    127 
    128   CFLSteensAAWrapperPass();
    129 
    130   CFLSteensAAResult &getResult() { return *Result; }
    131   const CFLSteensAAResult &getResult() const { return *Result; }
    132 
    133   void initializePass() override;
    134   void getAnalysisUsage(AnalysisUsage &AU) const override;
    135 };
    136 
    137 // createCFLSteensAAWrapperPass - This pass implements a set-based approach to
    138 // alias analysis.
    139 ImmutablePass *createCFLSteensAAWrapperPass();
    140 
    141 } // end namespace llvm
    142 
    143 #endif // LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H
    144