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