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 CFLAliasAnalysis : public ImmutablePass, public AliasAnalysis {
  30   struct FunctionInfo;
  31
  32   struct FunctionHandle final : public CallbackVH {
  33     FunctionHandle(Function *Fn, CFLAliasAnalysis *CFLAA)
  34         : CallbackVH(Fn), CFLAA(CFLAA) {
  35       assert(Fn != nullptr);
  36       assert(CFLAA != nullptr);
  37     }
  38
  39     void deleted() override { removeSelfFromCache(); }
  40     void allUsesReplacedWith(Value *) override { removeSelfFromCache(); }
  41
  42   private:
  43     CFLAliasAnalysis *CFLAA;
  44
  45     void removeSelfFromCache() {
  46       assert(CFLAA != nullptr);
  47       auto *Val = getValPtr();
  48       CFLAA->evict(cast<Function>(Val));
  49       setValPtr(nullptr);
  50     }
  51   };
  52
  53   /// \brief Cached mapping of Functions to their StratifiedSets.
  54   /// If a function's sets are currently being built, it is marked
  55   /// in the cache as an Optional without a value. This way, if we
  56   /// have any kind of recursion, it is discernable from a function
  57   /// that simply has empty sets.
  58   DenseMap<Function *, Optional<FunctionInfo>> Cache;
  59   std::forward_list<FunctionHandle> Handles;
  60
  61 public:
  62   static char ID;
  63
  64   CFLAliasAnalysis();
  65   ~CFLAliasAnalysis() override;
  66
  67   void getAnalysisUsage(AnalysisUsage &AU) const override;
  68
  69   void *getAdjustedAnalysisPointer(const void *ID) override;
  70
  71   /// \brief Inserts the given Function into the cache.
  72   void scan(Function *Fn);
  73
  74   void evict(Function *Fn);
  75
  76   /// \brief Ensures that the given function is available in the cache.
  77   /// Returns the appropriate entry from the cache.
  78   const Optional<FunctionInfo> &ensureCached(Function *Fn);
  79
  80   AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB);
  81
  82   AliasResult alias(const MemoryLocation &LocA,
  83                     const MemoryLocation &LocB) override {
  84     if (LocA.Ptr == LocB.Ptr) {
  85       if (LocA.Size == LocB.Size) {
  86         return MustAlias;
  87       } else {
  88         return PartialAlias;
  89       }
  90     }
  91
  92     // Comparisons between global variables and other constants should be
  93     // handled by BasicAA.
  94     // TODO: ConstantExpr handling -- CFLAA may report NoAlias when comparing
  95     // a GlobalValue and ConstantExpr, but every query needs to have at least
  96     // one Value tied to a Function, and neither GlobalValues nor ConstantExprs
  97     // are.
  98     if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr)) {
  99       return AliasAnalysis::alias(LocA, LocB);
 100     }
 101
 102     AliasResult QueryResult = query(LocA, LocB);
 103     if (QueryResult == MayAlias)
 104       return AliasAnalysis::alias(LocA, LocB);
 105
 106     return QueryResult;
 107   }
 108
 109   bool doInitialization(Module &M) override;
 110
 111 private:
 112   FunctionInfo buildSetsFrom(Function *F);
 113 };
 114
 115 //===--------------------------------------------------------------------===//
 116 //
 117 // createCFLAliasAnalysisPass - This pass implements a set-based approach to
 118 // alias analysis.
 119 //
 120 ImmutablePass *createCFLAliasAnalysisPass();
 121
 122 }
 123
 124 #endif