Line data    Source code

       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/Optional.h"
      20             : #include "llvm/Analysis/AliasAnalysis.h"
      21             : #include "llvm/Analysis/CFLAliasAnalysisUtils.h"
      22             : #include "llvm/Analysis/MemoryLocation.h"
      23             : #include "llvm/IR/PassManager.h"
      24             : #include "llvm/Pass.h"
      25             : #include "llvm/Support/Casting.h"
      26             : #include <forward_list>
      27             : #include <memory>
      28             : 
      29             : namespace llvm {
      30             : 
      31             : class Function;
      32             : class TargetLibraryInfo;
      33             : 
      34             : namespace cflaa {
      35             : 
      36             : struct AliasSummary;
      37             : 
      38             : } // end namespace cflaa
      39             : 
      40         161 : class CFLSteensAAResult : public AAResultBase<CFLSteensAAResult> {
      41             :   friend AAResultBase<CFLSteensAAResult>;
      42             : 
      43             :   class FunctionInfo;
      44             : 
      45             : public:
      46             :   explicit CFLSteensAAResult(const TargetLibraryInfo &TLI);
      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           0 :   bool invalidate(Function &, const PreservedAnalyses &,
      54             :                   FunctionAnalysisManager::Invalidator &) {
      55           0 :     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        2804 :   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
      74        2804 :     if (LocA.Ptr == LocB.Ptr)
      75             :       return MustAlias;
      76             : 
      77             :     // Comparisons between global variables and other constants should be
      78             :     // handled by BasicAA.
      79             :     // CFLSteensAA may report NoAlias when comparing a GlobalValue and
      80             :     // ConstantExpr, but every query needs to have at least one Value tied to a
      81             :     // Function, and neither GlobalValues nor ConstantExprs are.
      82        2804 :     if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr))
      83             :       return AAResultBase::alias(LocA, LocB);
      84             : 
      85        2797 :     AliasResult QueryResult = query(LocA, LocB);
      86        2797 :     if (QueryResult == MayAlias)
      87        2428 :       return AAResultBase::alias(LocA, LocB);
      88             : 
      89             :     return QueryResult;
      90             :   }
      91             : 
      92             : private:
      93             :   const TargetLibraryInfo &TLI;
      94             : 
      95             :   /// Cached mapping of Functions to their StratifiedSets.
      96             :   /// If a function's sets are currently being built, it is marked
      97             :   /// in the cache as an Optional without a value. This way, if we
      98             :   /// have any kind of recursion, it is discernable from a function
      99             :   /// that simply has empty sets.
     100             :   DenseMap<Function *, Optional<FunctionInfo>> Cache;
     101             :   std::forward_list<cflaa::FunctionHandle<CFLSteensAAResult>> Handles;
     102             : 
     103             :   FunctionInfo buildSetsFrom(Function *F);
     104             : };
     105             : 
     106             : /// Analysis pass providing a never-invalidated alias analysis result.
     107             : ///
     108             : /// FIXME: We really should refactor CFL to use the analysis more heavily, and
     109             : /// in particular to leverage invalidation to trigger re-computation of sets.
     110             : class CFLSteensAA : public AnalysisInfoMixin<CFLSteensAA> {
     111             :   friend AnalysisInfoMixin<CFLSteensAA>;
     112             : 
     113             :   static AnalysisKey Key;
     114             : 
     115             : public:
     116             :   using Result = CFLSteensAAResult;
     117             : 
     118             :   CFLSteensAAResult run(Function &F, FunctionAnalysisManager &AM);
     119             : };
     120             : 
     121             : /// Legacy wrapper pass to provide the CFLSteensAAResult object.
     122             : class CFLSteensAAWrapperPass : public ImmutablePass {
     123             :   std::unique_ptr<CFLSteensAAResult> Result;
     124             : 
     125             : public:
     126             :   static char ID;
     127             : 
     128             :   CFLSteensAAWrapperPass();
     129             : 
     130             :   CFLSteensAAResult &getResult() { return *Result; }
     131             :   const CFLSteensAAResult &getResult() const { return *Result; }
     132             : 
     133             :   void initializePass() override;
     134             :   void getAnalysisUsage(AnalysisUsage &AU) const override;
     135             : };
     136             : 
     137             : // createCFLSteensAAWrapperPass - This pass implements a set-based approach to
     138             : // alias analysis.
     139             : ImmutablePass *createCFLSteensAAWrapperPass();
     140             : 
     141             : } // end namespace llvm
     142             : 
     143             : #endif // LLVM_ANALYSIS_CFLSTEENSALIASANALYSIS_H