1//=- CFLAndersAliasAnalysis.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 inclusion-based alias analysis
11/// implemented with CFL graph reachability.
12///
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_ANALYSIS_CFLANDERSALIASANALYSIS_H
16#define LLVM_ANALYSIS_CFLANDERSALIASANALYSIS_H
17
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/Optional.h"
20#include "llvm/Analysis/AliasAnalysis.h"
21#include "llvm/IR/Function.h"
22#include "llvm/IR/ValueHandle.h"
23#include "llvm/Pass.h"
24#include <forward_list>
25
26namespace llvm {
27
28class TargetLibraryInfo;
29
30namespace cflaa {
31struct AliasSummary;
32}
33
34class CFLAndersAAResult : public AAResultBase<CFLAndersAAResult> {
35  friend AAResultBase<CFLAndersAAResult>;
36  class FunctionInfo;
37
38public:
39  explicit CFLAndersAAResult(const TargetLibraryInfo &);
40  CFLAndersAAResult(CFLAndersAAResult &&);
41  ~CFLAndersAAResult();
42
43  /// Handle invalidation events from the new pass manager.
44  /// By definition, this result is stateless and so remains valid.
45  bool invalidate(Function &, const PreservedAnalyses &,
46                  FunctionAnalysisManager::Invalidator &) {
47    return false;
48  }
49  /// Evict the given function from cache
50  void evict(const Function &Fn);
51
52  /// \brief Get the alias summary for the given function
53  /// Return nullptr if the summary is not found or not available
54  const cflaa::AliasSummary *getAliasSummary(const Function &);
55
56  AliasResult query(const MemoryLocation &, const MemoryLocation &);
57  AliasResult alias(const MemoryLocation &, const MemoryLocation &);
58
59private:
60  struct FunctionHandle final : public CallbackVH {
61    FunctionHandle(Function *Fn, CFLAndersAAResult *Result)
62        : CallbackVH(Fn), Result(Result) {
63      assert(Fn != nullptr);
64      assert(Result != nullptr);
65    }
66
67    void deleted() override { removeSelfFromCache(); }
68    void allUsesReplacedWith(Value *) override { removeSelfFromCache(); }
69
70  private:
71    CFLAndersAAResult *Result;
72
73    void removeSelfFromCache() {
74      assert(Result != nullptr);
75      auto *Val = getValPtr();
76      Result->evict(*cast<Function>(Val));
77      setValPtr(nullptr);
78    }
79  };
80
81  /// \brief Ensures that the given function is available in the cache.
82  /// Returns the appropriate entry from the cache.
83  const Optional<FunctionInfo> &ensureCached(const Function &);
84
85  /// \brief Inserts the given Function into the cache.
86  void scan(const Function &);
87
88  /// \brief Build summary for a given function
89  FunctionInfo buildInfoFrom(const Function &);
90
91  const TargetLibraryInfo &TLI;
92
93  /// \brief Cached mapping of Functions to their StratifiedSets.
94  /// If a function's sets are currently being built, it is marked
95  /// in the cache as an Optional without a value. This way, if we
96  /// have any kind of recursion, it is discernable from a function
97  /// that simply has empty sets.
98  DenseMap<const Function *, Optional<FunctionInfo>> Cache;
99
100  std::forward_list<FunctionHandle> Handles;
101};
102
103/// Analysis pass providing a never-invalidated alias analysis result.
104///
105/// FIXME: We really should refactor CFL to use the analysis more heavily, and
106/// in particular to leverage invalidation to trigger re-computation.
107class CFLAndersAA : public AnalysisInfoMixin<CFLAndersAA> {
108  friend AnalysisInfoMixin<CFLAndersAA>;
109  static AnalysisKey Key;
110
111public:
112  typedef CFLAndersAAResult Result;
113
114  CFLAndersAAResult run(Function &F, FunctionAnalysisManager &AM);
115};
116
117/// Legacy wrapper pass to provide the CFLAndersAAResult object.
118class CFLAndersAAWrapperPass : public ImmutablePass {
119  std::unique_ptr<CFLAndersAAResult> Result;
120
121public:
122  static char ID;
123
124  CFLAndersAAWrapperPass();
125
126  CFLAndersAAResult &getResult() { return *Result; }
127  const CFLAndersAAResult &getResult() const { return *Result; }
128
129  void initializePass() override;
130  void getAnalysisUsage(AnalysisUsage &AU) const override;
131};
132
133//===--------------------------------------------------------------------===//
134//
135// createCFLAndersAAWrapperPass - This pass implements a set-based approach to
136// alias analysis.
137//
138ImmutablePass *createCFLAndersAAWrapperPass();
139}
140
141#endif
142