1//=- CFLSteensAliasAnalysis.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 unification-based alias analysis
11/// implemented with CFL graph reachability.
12///
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H
16#define LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H
17
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/None.h"
20#include "llvm/ADT/Optional.h"
21#include "llvm/Analysis/AliasAnalysis.h"
22#include "llvm/IR/Function.h"
23#include "llvm/IR/Module.h"
24#include "llvm/IR/ValueHandle.h"
25#include "llvm/Pass.h"
26#include <forward_list>
27
28namespace llvm {
29
30class TargetLibraryInfo;
31
32namespace cflaa {
33struct AliasSummary;
34}
35
36class CFLSteensAAResult : public AAResultBase<CFLSteensAAResult> {
37  friend AAResultBase<CFLSteensAAResult>;
38  class FunctionInfo;
39
40public:
41  explicit CFLSteensAAResult(const TargetLibraryInfo &);
42  CFLSteensAAResult(CFLSteensAAResult &&Arg);
43  ~CFLSteensAAResult();
44
45  /// Handle invalidation events from the new pass manager.
46  ///
47  /// By definition, this result is stateless and so remains valid.
48  bool invalidate(Function &, const PreservedAnalyses &) { return false; }
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  /// \brief Get the alias summary for the given function
60  /// Return nullptr if the summary is not found or not available
61  const cflaa::AliasSummary *getAliasSummary(Function &Fn);
62
63  AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB);
64
65  AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
66    if (LocA.Ptr == LocB.Ptr)
67      return LocA.Size == LocB.Size ? MustAlias : PartialAlias;
68
69    // Comparisons between global variables and other constants should be
70    // handled by BasicAA.
71    // CFLSteensAA may report NoAlias when comparing a GlobalValue and
72    // ConstantExpr, but every query needs to have at least one Value tied to a
73    // Function, and neither GlobalValues nor ConstantExprs are.
74    if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr))
75      return AAResultBase::alias(LocA, LocB);
76
77    AliasResult QueryResult = query(LocA, LocB);
78    if (QueryResult == MayAlias)
79      return AAResultBase::alias(LocA, LocB);
80
81    return QueryResult;
82  }
83
84  /// Get the location associated with a pointer argument of a callsite.
85  ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx);
86
87  /// Returns the behavior when calling the given call site.
88  FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS);
89
90  /// Returns the behavior when calling the given function. For use when the
91  /// call site is not known.
92  FunctionModRefBehavior getModRefBehavior(const Function *F);
93
94private:
95  struct FunctionHandle final : public CallbackVH {
96    FunctionHandle(Function *Fn, CFLSteensAAResult *Result)
97        : CallbackVH(Fn), Result(Result) {
98      assert(Fn != nullptr);
99      assert(Result != nullptr);
100    }
101
102    void deleted() override { removeSelfFromCache(); }
103    void allUsesReplacedWith(Value *) override { removeSelfFromCache(); }
104
105  private:
106    CFLSteensAAResult *Result;
107
108    void removeSelfFromCache() {
109      assert(Result != nullptr);
110      auto *Val = getValPtr();
111      Result->evict(cast<Function>(Val));
112      setValPtr(nullptr);
113    }
114  };
115
116  const TargetLibraryInfo &TLI;
117
118  /// \brief Cached mapping of Functions to their StratifiedSets.
119  /// If a function's sets are currently being built, it is marked
120  /// in the cache as an Optional without a value. This way, if we
121  /// have any kind of recursion, it is discernable from a function
122  /// that simply has empty sets.
123  DenseMap<Function *, Optional<FunctionInfo>> Cache;
124  std::forward_list<FunctionHandle> Handles;
125
126  FunctionInfo buildSetsFrom(Function *F);
127};
128
129/// Analysis pass providing a never-invalidated alias analysis result.
130///
131/// FIXME: We really should refactor CFL to use the analysis more heavily, and
132/// in particular to leverage invalidation to trigger re-computation of sets.
133class CFLSteensAA : public AnalysisInfoMixin<CFLSteensAA> {
134  friend AnalysisInfoMixin<CFLSteensAA>;
135  static char PassID;
136
137public:
138  typedef CFLSteensAAResult Result;
139
140  CFLSteensAAResult run(Function &F, AnalysisManager<Function> &AM);
141};
142
143/// Legacy wrapper pass to provide the CFLSteensAAResult object.
144class CFLSteensAAWrapperPass : public ImmutablePass {
145  std::unique_ptr<CFLSteensAAResult> Result;
146
147public:
148  static char ID;
149
150  CFLSteensAAWrapperPass();
151
152  CFLSteensAAResult &getResult() { return *Result; }
153  const CFLSteensAAResult &getResult() const { return *Result; }
154
155  void initializePass() override;
156  void getAnalysisUsage(AnalysisUsage &AU) const override;
157};
158
159//===--------------------------------------------------------------------===//
160//
161// createCFLSteensAAWrapperPass - This pass implements a set-based approach to
162// alias analysis.
163//
164ImmutablePass *createCFLSteensAAWrapperPass();
165}
166
167#endif
168