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