CFLSteensAliasAnalysis.h revision 360784 
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
28namespace llvm {
29
30class Function;
31class TargetLibraryInfo;
32
33namespace cflaa {
34
35struct AliasSummary;
36
37} // end namespace cflaa
38
39class CFLSteensAAResult : public AAResultBase<CFLSteensAAResult> {
40  friend AAResultBase<CFLSteensAAResult>;
41
42  class FunctionInfo;
43
44public:
45  explicit CFLSteensAAResult(
46      std::function<const TargetLibraryInfo &(Function &)> GetTLI);
47  CFLSteensAAResult(CFLSteensAAResult &&Arg);
48  ~CFLSteensAAResult();
49
50  /// Handle invalidation events from the new pass manager.
51  ///
52  /// By definition, this result is stateless and so remains valid.
53  bool invalidate(Function &, const PreservedAnalyses &,
54                  FunctionAnalysisManager::Invalidator &) {
55    return false;
56  }
57
58  /// Inserts the given Function into the cache.
59  void scan(Function *Fn);
60
61  void evict(Function *Fn);
62
63  /// Ensures that the given function is available in the cache.
64  /// Returns the appropriate entry from the cache.
65  const Optional<FunctionInfo> &ensureCached(Function *Fn);
66
67  /// Get the alias summary for the given function
68  /// Return nullptr if the summary is not found or not available
69  const cflaa::AliasSummary *getAliasSummary(Function &Fn);
70
71  AliasResult query(const MemoryLocation &LocA, const MemoryLocation &LocB);
72
73  AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
74                    AAQueryInfo &AAQI) {
75    if (LocA.Ptr == LocB.Ptr)
76      return MustAlias;
77
78    // Comparisons between global variables and other constants should be
79    // handled by BasicAA.
80    // CFLSteensAA may report NoAlias when comparing a GlobalValue and
81    // ConstantExpr, but every query needs to have at least one Value tied to a
82    // Function, and neither GlobalValues nor ConstantExprs are.
83    if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr))
84      return AAResultBase::alias(LocA, LocB, AAQI);
85
86    AliasResult QueryResult = query(LocA, LocB);
87    if (QueryResult == MayAlias)
88      return AAResultBase::alias(LocA, LocB, AAQI);
89
90    return QueryResult;
91  }
92
93private:
94  std::function<const TargetLibraryInfo &(Function &)> GetTLI;
95
96  /// Cached mapping of Functions to their StratifiedSets.
97  /// If a function's sets are currently being built, it is marked
98  /// in the cache as an Optional without a value. This way, if we
99  /// have any kind of recursion, it is discernable from a function
100  /// that simply has empty sets.
101  DenseMap<Function *, Optional<FunctionInfo>> Cache;
102  std::forward_list<cflaa::FunctionHandle<CFLSteensAAResult>> Handles;
103
104  FunctionInfo buildSetsFrom(Function *F);
105};
106
107/// Analysis pass providing a never-invalidated alias analysis result.
108///
109/// FIXME: We really should refactor CFL to use the analysis more heavily, and
110/// in particular to leverage invalidation to trigger re-computation of sets.
111class CFLSteensAA : public AnalysisInfoMixin<CFLSteensAA> {
112  friend AnalysisInfoMixin<CFLSteensAA>;
113
114  static AnalysisKey Key;
115
116public:
117  using Result = CFLSteensAAResult;
118
119  CFLSteensAAResult run(Function &F, FunctionAnalysisManager &AM);
120};
121
122/// Legacy wrapper pass to provide the CFLSteensAAResult object.
123class CFLSteensAAWrapperPass : public ImmutablePass {
124  std::unique_ptr<CFLSteensAAResult> Result;
125
126public:
127  static char ID;
128
129  CFLSteensAAWrapperPass();
130
131  CFLSteensAAResult &getResult() { return *Result; }
132  const CFLSteensAAResult &getResult() const { return *Result; }
133
134  void initializePass() override;
135  void getAnalysisUsage(AnalysisUsage &AU) const override;
136};
137
138// createCFLSteensAAWrapperPass - This pass implements a set-based approach to
139// alias analysis.
140ImmutablePass *createCFLSteensAAWrapperPass();
141
142} // end namespace llvm
143
144#endif // LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H
145