contrib/llvm/include/llvm/Analysis/CFLSteensAliasAnalysis.h

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