llvm/Analysis/BasicAliasAnalysis.h

0001 //===- BasicAliasAnalysis.h - Stateless, local Alias Analysis ---*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 /// \file
0009 /// This is the interface for LLVM's primary stateless and local alias analysis.
0010 ///
0011 //===----------------------------------------------------------------------===//
0012
0013 #ifndef LLVM_ANALYSIS_BASICALIASANALYSIS_H
0014 #define LLVM_ANALYSIS_BASICALIASANALYSIS_H
0015
0016 #include "llvm/ADT/SmallPtrSet.h"
0017 #include "llvm/Analysis/AliasAnalysis.h"
0018 #include "llvm/IR/PassManager.h"
0019 #include "llvm/Pass.h"
0020 #include <memory>
0021 #include <utility>
0022
0023 namespace llvm {
0024
0025 class AssumptionCache;
0026 class DataLayout;
0027 class DominatorTree;
0028 class Function;
0029 class GEPOperator;
0030 class PHINode;
0031 class SelectInst;
0032 class TargetLibraryInfo;
0033 class Value;
0034
0035 /// This is the AA result object for the basic, local, and stateless alias
0036 /// analysis. It implements the AA query interface in an entirely stateless
0037 /// manner. As one consequence, it is never invalidated due to IR changes.
0038 /// While it does retain some storage, that is used as an optimization and not
0039 /// to preserve information from query to query. However it does retain handles
0040 /// to various other analyses and must be recomputed when those analyses are.
0041 class BasicAAResult : public AAResultBase {
0042   const DataLayout &DL;
0043   const Function &F;
0044   const TargetLibraryInfo &TLI;
0045   AssumptionCache &AC;
0046   /// Use getDT() instead of accessing this member directly, in order to
0047   /// respect the AAQI.UseDominatorTree option.
0048   DominatorTree *DT_;
0049
0050   DominatorTree *getDT(const AAQueryInfo &AAQI) const {
0051     return AAQI.UseDominatorTree ? DT_ : nullptr;
0052   }
0053
0054 public:
0055   BasicAAResult(const DataLayout &DL, const Function &F,
0056                 const TargetLibraryInfo &TLI, AssumptionCache &AC,
0057                 DominatorTree *DT = nullptr)
0058       : DL(DL), F(F), TLI(TLI), AC(AC), DT_(DT) {}
0059
0060   BasicAAResult(const BasicAAResult &Arg)
0061       : AAResultBase(Arg), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI), AC(Arg.AC),
0062         DT_(Arg.DT_) {}
0063   BasicAAResult(BasicAAResult &&Arg)
0064       : AAResultBase(std::move(Arg)), DL(Arg.DL), F(Arg.F), TLI(Arg.TLI),
0065         AC(Arg.AC), DT_(Arg.DT_) {}
0066
0067   /// Handle invalidation events in the new pass manager.
0068   bool invalidate(Function &Fn, const PreservedAnalyses &PA,
0069                   FunctionAnalysisManager::Invalidator &Inv);
0070
0071   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
0072                     AAQueryInfo &AAQI, const Instruction *CtxI);
0073
0074   ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
0075                            AAQueryInfo &AAQI);
0076
0077   ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
0078                            AAQueryInfo &AAQI);
0079
0080   /// Returns a bitmask that should be unconditionally applied to the ModRef
0081   /// info of a memory location. This allows us to eliminate Mod and/or Ref
0082   /// from the ModRef info based on the knowledge that the memory location
0083   /// points to constant and/or locally-invariant memory.
0084   ///
0085   /// If IgnoreLocals is true, then this method returns NoModRef for memory
0086   /// that points to a local alloca.
0087   ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI,
0088                                bool IgnoreLocals = false);
0089
0090   /// Get the location associated with a pointer argument of a callsite.
0091   ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx);
0092
0093   /// Returns the behavior when calling the given call site.
0094   MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI);
0095
0096   /// Returns the behavior when calling the given function. For use when the
0097   /// call site is not known.
0098   MemoryEffects getMemoryEffects(const Function *Fn);
0099
0100 private:
0101   struct DecomposedGEP;
0102
0103   /// Tracks instructions visited by pointsToConstantMemory.
0104   SmallPtrSet<const Value *, 16> Visited;
0105
0106   static DecomposedGEP
0107   DecomposeGEPExpression(const Value *V, const DataLayout &DL,
0108                          AssumptionCache *AC, DominatorTree *DT);
0109
0110   /// A Heuristic for aliasGEP that searches for a constant offset
0111   /// between the variables.
0112   ///
0113   /// GetLinearExpression has some limitations, as generally zext(%x + 1)
0114   /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
0115   /// will therefore conservatively refuse to decompose these expressions.
0116   /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
0117   /// the addition overflows.
0118   bool constantOffsetHeuristic(const DecomposedGEP &GEP, LocationSize V1Size,
0119                                LocationSize V2Size, AssumptionCache *AC,
0120                                DominatorTree *DT, const AAQueryInfo &AAQI);
0121
0122   bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2,
0123                                      const AAQueryInfo &AAQI);
0124
0125   void subtractDecomposedGEPs(DecomposedGEP &DestGEP,
0126                               const DecomposedGEP &SrcGEP,
0127                               const AAQueryInfo &AAQI);
0128
0129   AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size,
0130                        const Value *V2, LocationSize V2Size,
0131                        const Value *UnderlyingV1, const Value *UnderlyingV2,
0132                        AAQueryInfo &AAQI);
0133
0134   AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize,
0135                        const Value *V2, LocationSize V2Size, AAQueryInfo &AAQI);
0136
0137   AliasResult aliasSelect(const SelectInst *SI, LocationSize SISize,
0138                           const Value *V2, LocationSize V2Size,
0139                           AAQueryInfo &AAQI);
0140
0141   AliasResult aliasCheck(const Value *V1, LocationSize V1Size, const Value *V2,
0142                          LocationSize V2Size, AAQueryInfo &AAQI,
0143                          const Instruction *CtxI);
0144
0145   AliasResult aliasCheckRecursive(const Value *V1, LocationSize V1Size,
0146                                   const Value *V2, LocationSize V2Size,
0147                                   AAQueryInfo &AAQI, const Value *O1,
0148                                   const Value *O2);
0149 };
0150
0151 /// Analysis pass providing a never-invalidated alias analysis result.
0152 class BasicAA : public AnalysisInfoMixin<BasicAA> {
0153   friend AnalysisInfoMixin<BasicAA>;
0154
0155   static AnalysisKey Key;
0156
0157 public:
0158   using Result = BasicAAResult;
0159
0160   BasicAAResult run(Function &F, FunctionAnalysisManager &AM);
0161 };
0162
0163 /// Legacy wrapper pass to provide the BasicAAResult object.
0164 class BasicAAWrapperPass : public FunctionPass {
0165   std::unique_ptr<BasicAAResult> Result;
0166
0167   virtual void anchor();
0168
0169 public:
0170   static char ID;
0171
0172   BasicAAWrapperPass();
0173
0174   BasicAAResult &getResult() { return *Result; }
0175   const BasicAAResult &getResult() const { return *Result; }
0176
0177   bool runOnFunction(Function &F) override;
0178   void getAnalysisUsage(AnalysisUsage &AU) const override;
0179 };
0180
0181 FunctionPass *createBasicAAWrapperPass();
0182
0183 } // end namespace llvm
0184
0185 #endif // LLVM_ANALYSIS_BASICALIASANALYSIS_H