include/llvm/Analysis/CFLAliasAnalysis.h

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