include/llvm/Analysis/CFLSteensAliasAnalysis.h

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