Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 1 | //===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- 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 | // |
| 10 | // This file defines the generic AliasAnalysis interface, which is used as the |
| 11 | // common interface used by all clients of alias analysis information, and |
| 12 | // implemented by all alias analysis implementations. Mod/Ref information is |
| 13 | // also captured by this interface. |
| 14 | // |
| 15 | // Implementations of this interface must implement the various virtual methods, |
| 16 | // which automatically provides functionality for the entire suite of client |
| 17 | // APIs. |
| 18 | // |
| 19 | // This API identifies memory regions with the MemoryLocation class. The pointer |
| 20 | // component specifies the base memory address of the region. The Size specifies |
| 21 | // the maximum size (in address units) of the memory region, or |
| 22 | // MemoryLocation::UnknownSize if the size is not known. The TBAA tag |
| 23 | // identifies the "type" of the memory reference; see the |
| 24 | // TypeBasedAliasAnalysis class for details. |
| 25 | // |
| 26 | // Some non-obvious details include: |
| 27 | // - Pointers that point to two completely different objects in memory never |
| 28 | // alias, regardless of the value of the Size component. |
| 29 | // - NoAlias doesn't imply inequal pointers. The most obvious example of this |
| 30 | // is two pointers to constant memory. Even if they are equal, constant |
| 31 | // memory is never stored to, so there will never be any dependencies. |
| 32 | // In this and other situations, the pointers may be both NoAlias and |
| 33 | // MustAlias at the same time. The current API can only return one result, |
| 34 | // though this is rarely a problem in practice. |
| 35 | // |
| 36 | //===----------------------------------------------------------------------===// |
| 37 | |
| 38 | #ifndef LLVM_ANALYSIS_ALIASANALYSIS_H |
| 39 | #define LLVM_ANALYSIS_ALIASANALYSIS_H |
| 40 | |
| 41 | #include "llvm/ADT/None.h" |
| 42 | #include "llvm/ADT/Optional.h" |
| 43 | #include "llvm/ADT/SmallVector.h" |
| 44 | #include "llvm/Analysis/MemoryLocation.h" |
| 45 | #include "llvm/Analysis/TargetLibraryInfo.h" |
| 46 | #include "llvm/IR/CallSite.h" |
| 47 | #include "llvm/IR/Function.h" |
| 48 | #include "llvm/IR/Instruction.h" |
| 49 | #include "llvm/IR/Instructions.h" |
| 50 | #include "llvm/IR/PassManager.h" |
| 51 | #include "llvm/Pass.h" |
| 52 | #include <cstdint> |
| 53 | #include <functional> |
| 54 | #include <memory> |
| 55 | #include <vector> |
| 56 | |
| 57 | namespace llvm { |
| 58 | |
| 59 | class AnalysisUsage; |
| 60 | class BasicAAResult; |
| 61 | class BasicBlock; |
| 62 | class DominatorTree; |
| 63 | class OrderedBasicBlock; |
| 64 | class Value; |
| 65 | |
| 66 | /// The possible results of an alias query. |
| 67 | /// |
| 68 | /// These results are always computed between two MemoryLocation objects as |
| 69 | /// a query to some alias analysis. |
| 70 | /// |
| 71 | /// Note that these are unscoped enumerations because we would like to support |
| 72 | /// implicitly testing a result for the existence of any possible aliasing with |
| 73 | /// a conversion to bool, but an "enum class" doesn't support this. The |
| 74 | /// canonical names from the literature are suffixed and unique anyways, and so |
| 75 | /// they serve as global constants in LLVM for these results. |
| 76 | /// |
| 77 | /// See docs/AliasAnalysis.html for more information on the specific meanings |
| 78 | /// of these values. |
| 79 | enum AliasResult : uint8_t { |
| 80 | /// The two locations do not alias at all. |
| 81 | /// |
| 82 | /// This value is arranged to convert to false, while all other values |
| 83 | /// convert to true. This allows a boolean context to convert the result to |
| 84 | /// a binary flag indicating whether there is the possibility of aliasing. |
| 85 | NoAlias = 0, |
| 86 | /// The two locations may or may not alias. This is the least precise result. |
| 87 | MayAlias, |
| 88 | /// The two locations alias, but only due to a partial overlap. |
| 89 | PartialAlias, |
| 90 | /// The two locations precisely alias each other. |
| 91 | MustAlias, |
| 92 | }; |
| 93 | |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame^] | 94 | /// << operator for AliasResult. |
| 95 | raw_ostream &operator<<(raw_ostream &OS, AliasResult AR); |
| 96 | |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 97 | /// Flags indicating whether a memory access modifies or references memory. |
| 98 | /// |
| 99 | /// This is no access at all, a modification, a reference, or both |
| 100 | /// a modification and a reference. These are specifically structured such that |
| 101 | /// they form a three bit matrix and bit-tests for 'mod' or 'ref' or 'must' |
| 102 | /// work with any of the possible values. |
| 103 | enum class ModRefInfo : uint8_t { |
| 104 | /// Must is provided for completeness, but no routines will return only |
| 105 | /// Must today. See definition of Must below. |
| 106 | Must = 0, |
| 107 | /// The access may reference the value stored in memory, |
| 108 | /// a mustAlias relation was found, and no mayAlias or partialAlias found. |
| 109 | MustRef = 1, |
| 110 | /// The access may modify the value stored in memory, |
| 111 | /// a mustAlias relation was found, and no mayAlias or partialAlias found. |
| 112 | MustMod = 2, |
| 113 | /// The access may reference, modify or both the value stored in memory, |
| 114 | /// a mustAlias relation was found, and no mayAlias or partialAlias found. |
| 115 | MustModRef = MustRef | MustMod, |
| 116 | /// The access neither references nor modifies the value stored in memory. |
| 117 | NoModRef = 4, |
| 118 | /// The access may reference the value stored in memory. |
| 119 | Ref = NoModRef | MustRef, |
| 120 | /// The access may modify the value stored in memory. |
| 121 | Mod = NoModRef | MustMod, |
| 122 | /// The access may reference and may modify the value stored in memory. |
| 123 | ModRef = Ref | Mod, |
| 124 | |
| 125 | /// About Must: |
| 126 | /// Must is set in a best effort manner. |
| 127 | /// We usually do not try our best to infer Must, instead it is merely |
| 128 | /// another piece of "free" information that is presented when available. |
| 129 | /// Must set means there was certainly a MustAlias found. For calls, |
| 130 | /// where multiple arguments are checked (argmemonly), this translates to |
| 131 | /// only MustAlias or NoAlias was found. |
| 132 | /// Must is not set for RAR accesses, even if the two locations must |
| 133 | /// alias. The reason is that two read accesses translate to an early return |
| 134 | /// of NoModRef. An additional alias check to set Must may be |
| 135 | /// expensive. Other cases may also not set Must(e.g. callCapturesBefore). |
| 136 | /// We refer to Must being *set* when the most significant bit is *cleared*. |
| 137 | /// Conversely we *clear* Must information by *setting* the Must bit to 1. |
| 138 | }; |
| 139 | |
| 140 | LLVM_NODISCARD inline bool isNoModRef(const ModRefInfo MRI) { |
| 141 | return (static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef)) == |
| 142 | static_cast<int>(ModRefInfo::Must); |
| 143 | } |
| 144 | LLVM_NODISCARD inline bool isModOrRefSet(const ModRefInfo MRI) { |
| 145 | return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef); |
| 146 | } |
| 147 | LLVM_NODISCARD inline bool isModAndRefSet(const ModRefInfo MRI) { |
| 148 | return (static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef)) == |
| 149 | static_cast<int>(ModRefInfo::MustModRef); |
| 150 | } |
| 151 | LLVM_NODISCARD inline bool isModSet(const ModRefInfo MRI) { |
| 152 | return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustMod); |
| 153 | } |
| 154 | LLVM_NODISCARD inline bool isRefSet(const ModRefInfo MRI) { |
| 155 | return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustRef); |
| 156 | } |
| 157 | LLVM_NODISCARD inline bool isMustSet(const ModRefInfo MRI) { |
| 158 | return !(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::NoModRef)); |
| 159 | } |
| 160 | |
| 161 | LLVM_NODISCARD inline ModRefInfo setMod(const ModRefInfo MRI) { |
| 162 | return ModRefInfo(static_cast<int>(MRI) | |
| 163 | static_cast<int>(ModRefInfo::MustMod)); |
| 164 | } |
| 165 | LLVM_NODISCARD inline ModRefInfo setRef(const ModRefInfo MRI) { |
| 166 | return ModRefInfo(static_cast<int>(MRI) | |
| 167 | static_cast<int>(ModRefInfo::MustRef)); |
| 168 | } |
| 169 | LLVM_NODISCARD inline ModRefInfo setMust(const ModRefInfo MRI) { |
| 170 | return ModRefInfo(static_cast<int>(MRI) & |
| 171 | static_cast<int>(ModRefInfo::MustModRef)); |
| 172 | } |
| 173 | LLVM_NODISCARD inline ModRefInfo setModAndRef(const ModRefInfo MRI) { |
| 174 | return ModRefInfo(static_cast<int>(MRI) | |
| 175 | static_cast<int>(ModRefInfo::MustModRef)); |
| 176 | } |
| 177 | LLVM_NODISCARD inline ModRefInfo clearMod(const ModRefInfo MRI) { |
| 178 | return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Ref)); |
| 179 | } |
| 180 | LLVM_NODISCARD inline ModRefInfo clearRef(const ModRefInfo MRI) { |
| 181 | return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Mod)); |
| 182 | } |
| 183 | LLVM_NODISCARD inline ModRefInfo clearMust(const ModRefInfo MRI) { |
| 184 | return ModRefInfo(static_cast<int>(MRI) | |
| 185 | static_cast<int>(ModRefInfo::NoModRef)); |
| 186 | } |
| 187 | LLVM_NODISCARD inline ModRefInfo unionModRef(const ModRefInfo MRI1, |
| 188 | const ModRefInfo MRI2) { |
| 189 | return ModRefInfo(static_cast<int>(MRI1) | static_cast<int>(MRI2)); |
| 190 | } |
| 191 | LLVM_NODISCARD inline ModRefInfo intersectModRef(const ModRefInfo MRI1, |
| 192 | const ModRefInfo MRI2) { |
| 193 | return ModRefInfo(static_cast<int>(MRI1) & static_cast<int>(MRI2)); |
| 194 | } |
| 195 | |
| 196 | /// The locations at which a function might access memory. |
| 197 | /// |
| 198 | /// These are primarily used in conjunction with the \c AccessKind bits to |
| 199 | /// describe both the nature of access and the locations of access for a |
| 200 | /// function call. |
| 201 | enum FunctionModRefLocation { |
| 202 | /// Base case is no access to memory. |
| 203 | FMRL_Nowhere = 0, |
| 204 | /// Access to memory via argument pointers. |
| 205 | FMRL_ArgumentPointees = 8, |
| 206 | /// Memory that is inaccessible via LLVM IR. |
| 207 | FMRL_InaccessibleMem = 16, |
| 208 | /// Access to any memory. |
| 209 | FMRL_Anywhere = 32 | FMRL_InaccessibleMem | FMRL_ArgumentPointees |
| 210 | }; |
| 211 | |
| 212 | /// Summary of how a function affects memory in the program. |
| 213 | /// |
| 214 | /// Loads from constant globals are not considered memory accesses for this |
| 215 | /// interface. Also, functions may freely modify stack space local to their |
| 216 | /// invocation without having to report it through these interfaces. |
| 217 | enum FunctionModRefBehavior { |
| 218 | /// This function does not perform any non-local loads or stores to memory. |
| 219 | /// |
| 220 | /// This property corresponds to the GCC 'const' attribute. |
| 221 | /// This property corresponds to the LLVM IR 'readnone' attribute. |
| 222 | /// This property corresponds to the IntrNoMem LLVM intrinsic flag. |
| 223 | FMRB_DoesNotAccessMemory = |
| 224 | FMRL_Nowhere | static_cast<int>(ModRefInfo::NoModRef), |
| 225 | |
| 226 | /// The only memory references in this function (if it has any) are |
| 227 | /// non-volatile loads from objects pointed to by its pointer-typed |
| 228 | /// arguments, with arbitrary offsets. |
| 229 | /// |
| 230 | /// This property corresponds to the IntrReadArgMem LLVM intrinsic flag. |
| 231 | FMRB_OnlyReadsArgumentPointees = |
| 232 | FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::Ref), |
| 233 | |
| 234 | /// The only memory references in this function (if it has any) are |
| 235 | /// non-volatile loads and stores from objects pointed to by its |
| 236 | /// pointer-typed arguments, with arbitrary offsets. |
| 237 | /// |
| 238 | /// This property corresponds to the IntrArgMemOnly LLVM intrinsic flag. |
| 239 | FMRB_OnlyAccessesArgumentPointees = |
| 240 | FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::ModRef), |
| 241 | |
| 242 | /// The only memory references in this function (if it has any) are |
| 243 | /// references of memory that is otherwise inaccessible via LLVM IR. |
| 244 | /// |
| 245 | /// This property corresponds to the LLVM IR inaccessiblememonly attribute. |
| 246 | FMRB_OnlyAccessesInaccessibleMem = |
| 247 | FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::ModRef), |
| 248 | |
| 249 | /// The function may perform non-volatile loads and stores of objects |
| 250 | /// pointed to by its pointer-typed arguments, with arbitrary offsets, and |
| 251 | /// it may also perform loads and stores of memory that is otherwise |
| 252 | /// inaccessible via LLVM IR. |
| 253 | /// |
| 254 | /// This property corresponds to the LLVM IR |
| 255 | /// inaccessiblemem_or_argmemonly attribute. |
| 256 | FMRB_OnlyAccessesInaccessibleOrArgMem = FMRL_InaccessibleMem | |
| 257 | FMRL_ArgumentPointees | |
| 258 | static_cast<int>(ModRefInfo::ModRef), |
| 259 | |
| 260 | /// This function does not perform any non-local stores or volatile loads, |
| 261 | /// but may read from any memory location. |
| 262 | /// |
| 263 | /// This property corresponds to the GCC 'pure' attribute. |
| 264 | /// This property corresponds to the LLVM IR 'readonly' attribute. |
| 265 | /// This property corresponds to the IntrReadMem LLVM intrinsic flag. |
| 266 | FMRB_OnlyReadsMemory = FMRL_Anywhere | static_cast<int>(ModRefInfo::Ref), |
| 267 | |
| 268 | // This function does not read from memory anywhere, but may write to any |
| 269 | // memory location. |
| 270 | // |
| 271 | // This property corresponds to the LLVM IR 'writeonly' attribute. |
| 272 | // This property corresponds to the IntrWriteMem LLVM intrinsic flag. |
| 273 | FMRB_DoesNotReadMemory = FMRL_Anywhere | static_cast<int>(ModRefInfo::Mod), |
| 274 | |
| 275 | /// This indicates that the function could not be classified into one of the |
| 276 | /// behaviors above. |
| 277 | FMRB_UnknownModRefBehavior = |
| 278 | FMRL_Anywhere | static_cast<int>(ModRefInfo::ModRef) |
| 279 | }; |
| 280 | |
| 281 | // Wrapper method strips bits significant only in FunctionModRefBehavior, |
| 282 | // to obtain a valid ModRefInfo. The benefit of using the wrapper is that if |
| 283 | // ModRefInfo enum changes, the wrapper can be updated to & with the new enum |
| 284 | // entry with all bits set to 1. |
| 285 | LLVM_NODISCARD inline ModRefInfo |
| 286 | createModRefInfo(const FunctionModRefBehavior FMRB) { |
| 287 | return ModRefInfo(FMRB & static_cast<int>(ModRefInfo::ModRef)); |
| 288 | } |
| 289 | |
| 290 | class AAResults { |
| 291 | public: |
| 292 | // Make these results default constructable and movable. We have to spell |
| 293 | // these out because MSVC won't synthesize them. |
| 294 | AAResults(const TargetLibraryInfo &TLI) : TLI(TLI) {} |
| 295 | AAResults(AAResults &&Arg); |
| 296 | ~AAResults(); |
| 297 | |
| 298 | /// Register a specific AA result. |
| 299 | template <typename AAResultT> void addAAResult(AAResultT &AAResult) { |
| 300 | // FIXME: We should use a much lighter weight system than the usual |
| 301 | // polymorphic pattern because we don't own AAResult. It should |
| 302 | // ideally involve two pointers and no separate allocation. |
| 303 | AAs.emplace_back(new Model<AAResultT>(AAResult, *this)); |
| 304 | } |
| 305 | |
| 306 | /// Register a function analysis ID that the results aggregation depends on. |
| 307 | /// |
| 308 | /// This is used in the new pass manager to implement the invalidation logic |
| 309 | /// where we must invalidate the results aggregation if any of our component |
| 310 | /// analyses become invalid. |
| 311 | void addAADependencyID(AnalysisKey *ID) { AADeps.push_back(ID); } |
| 312 | |
| 313 | /// Handle invalidation events in the new pass manager. |
| 314 | /// |
| 315 | /// The aggregation is invalidated if any of the underlying analyses is |
| 316 | /// invalidated. |
| 317 | bool invalidate(Function &F, const PreservedAnalyses &PA, |
| 318 | FunctionAnalysisManager::Invalidator &Inv); |
| 319 | |
| 320 | //===--------------------------------------------------------------------===// |
| 321 | /// \name Alias Queries |
| 322 | /// @{ |
| 323 | |
| 324 | /// The main low level interface to the alias analysis implementation. |
| 325 | /// Returns an AliasResult indicating whether the two pointers are aliased to |
| 326 | /// each other. This is the interface that must be implemented by specific |
| 327 | /// alias analysis implementations. |
| 328 | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB); |
| 329 | |
| 330 | /// A convenience wrapper around the primary \c alias interface. |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame^] | 331 | AliasResult alias(const Value *V1, LocationSize V1Size, const Value *V2, |
| 332 | LocationSize V2Size) { |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 333 | return alias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size)); |
| 334 | } |
| 335 | |
| 336 | /// A convenience wrapper around the primary \c alias interface. |
| 337 | AliasResult alias(const Value *V1, const Value *V2) { |
| 338 | return alias(V1, MemoryLocation::UnknownSize, V2, |
| 339 | MemoryLocation::UnknownSize); |
| 340 | } |
| 341 | |
| 342 | /// A trivial helper function to check to see if the specified pointers are |
| 343 | /// no-alias. |
| 344 | bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { |
| 345 | return alias(LocA, LocB) == NoAlias; |
| 346 | } |
| 347 | |
| 348 | /// A convenience wrapper around the \c isNoAlias helper interface. |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame^] | 349 | bool isNoAlias(const Value *V1, LocationSize V1Size, const Value *V2, |
| 350 | LocationSize V2Size) { |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 351 | return isNoAlias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size)); |
| 352 | } |
| 353 | |
| 354 | /// A convenience wrapper around the \c isNoAlias helper interface. |
| 355 | bool isNoAlias(const Value *V1, const Value *V2) { |
| 356 | return isNoAlias(MemoryLocation(V1), MemoryLocation(V2)); |
| 357 | } |
| 358 | |
| 359 | /// A trivial helper function to check to see if the specified pointers are |
| 360 | /// must-alias. |
| 361 | bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { |
| 362 | return alias(LocA, LocB) == MustAlias; |
| 363 | } |
| 364 | |
| 365 | /// A convenience wrapper around the \c isMustAlias helper interface. |
| 366 | bool isMustAlias(const Value *V1, const Value *V2) { |
| 367 | return alias(V1, 1, V2, 1) == MustAlias; |
| 368 | } |
| 369 | |
| 370 | /// Checks whether the given location points to constant memory, or if |
| 371 | /// \p OrLocal is true whether it points to a local alloca. |
| 372 | bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false); |
| 373 | |
| 374 | /// A convenience wrapper around the primary \c pointsToConstantMemory |
| 375 | /// interface. |
| 376 | bool pointsToConstantMemory(const Value *P, bool OrLocal = false) { |
| 377 | return pointsToConstantMemory(MemoryLocation(P), OrLocal); |
| 378 | } |
| 379 | |
| 380 | /// @} |
| 381 | //===--------------------------------------------------------------------===// |
| 382 | /// \name Simple mod/ref information |
| 383 | /// @{ |
| 384 | |
| 385 | /// Get the ModRef info associated with a pointer argument of a callsite. The |
| 386 | /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note |
| 387 | /// that these bits do not necessarily account for the overall behavior of |
| 388 | /// the function, but rather only provide additional per-argument |
| 389 | /// information. This never sets ModRefInfo::Must. |
| 390 | ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx); |
| 391 | |
| 392 | /// Return the behavior of the given call site. |
| 393 | FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS); |
| 394 | |
| 395 | /// Return the behavior when calling the given function. |
| 396 | FunctionModRefBehavior getModRefBehavior(const Function *F); |
| 397 | |
| 398 | /// Checks if the specified call is known to never read or write memory. |
| 399 | /// |
| 400 | /// Note that if the call only reads from known-constant memory, it is also |
| 401 | /// legal to return true. Also, calls that unwind the stack are legal for |
| 402 | /// this predicate. |
| 403 | /// |
| 404 | /// Many optimizations (such as CSE and LICM) can be performed on such calls |
| 405 | /// without worrying about aliasing properties, and many calls have this |
| 406 | /// property (e.g. calls to 'sin' and 'cos'). |
| 407 | /// |
| 408 | /// This property corresponds to the GCC 'const' attribute. |
| 409 | bool doesNotAccessMemory(ImmutableCallSite CS) { |
| 410 | return getModRefBehavior(CS) == FMRB_DoesNotAccessMemory; |
| 411 | } |
| 412 | |
| 413 | /// Checks if the specified function is known to never read or write memory. |
| 414 | /// |
| 415 | /// Note that if the function only reads from known-constant memory, it is |
| 416 | /// also legal to return true. Also, function that unwind the stack are legal |
| 417 | /// for this predicate. |
| 418 | /// |
| 419 | /// Many optimizations (such as CSE and LICM) can be performed on such calls |
| 420 | /// to such functions without worrying about aliasing properties, and many |
| 421 | /// functions have this property (e.g. 'sin' and 'cos'). |
| 422 | /// |
| 423 | /// This property corresponds to the GCC 'const' attribute. |
| 424 | bool doesNotAccessMemory(const Function *F) { |
| 425 | return getModRefBehavior(F) == FMRB_DoesNotAccessMemory; |
| 426 | } |
| 427 | |
| 428 | /// Checks if the specified call is known to only read from non-volatile |
| 429 | /// memory (or not access memory at all). |
| 430 | /// |
| 431 | /// Calls that unwind the stack are legal for this predicate. |
| 432 | /// |
| 433 | /// This property allows many common optimizations to be performed in the |
| 434 | /// absence of interfering store instructions, such as CSE of strlen calls. |
| 435 | /// |
| 436 | /// This property corresponds to the GCC 'pure' attribute. |
| 437 | bool onlyReadsMemory(ImmutableCallSite CS) { |
| 438 | return onlyReadsMemory(getModRefBehavior(CS)); |
| 439 | } |
| 440 | |
| 441 | /// Checks if the specified function is known to only read from non-volatile |
| 442 | /// memory (or not access memory at all). |
| 443 | /// |
| 444 | /// Functions that unwind the stack are legal for this predicate. |
| 445 | /// |
| 446 | /// This property allows many common optimizations to be performed in the |
| 447 | /// absence of interfering store instructions, such as CSE of strlen calls. |
| 448 | /// |
| 449 | /// This property corresponds to the GCC 'pure' attribute. |
| 450 | bool onlyReadsMemory(const Function *F) { |
| 451 | return onlyReadsMemory(getModRefBehavior(F)); |
| 452 | } |
| 453 | |
| 454 | /// Checks if functions with the specified behavior are known to only read |
| 455 | /// from non-volatile memory (or not access memory at all). |
| 456 | static bool onlyReadsMemory(FunctionModRefBehavior MRB) { |
| 457 | return !isModSet(createModRefInfo(MRB)); |
| 458 | } |
| 459 | |
| 460 | /// Checks if functions with the specified behavior are known to only write |
| 461 | /// memory (or not access memory at all). |
| 462 | static bool doesNotReadMemory(FunctionModRefBehavior MRB) { |
| 463 | return !isRefSet(createModRefInfo(MRB)); |
| 464 | } |
| 465 | |
| 466 | /// Checks if functions with the specified behavior are known to read and |
| 467 | /// write at most from objects pointed to by their pointer-typed arguments |
| 468 | /// (with arbitrary offsets). |
| 469 | static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB) { |
| 470 | return !(MRB & FMRL_Anywhere & ~FMRL_ArgumentPointees); |
| 471 | } |
| 472 | |
| 473 | /// Checks if functions with the specified behavior are known to potentially |
| 474 | /// read or write from objects pointed to be their pointer-typed arguments |
| 475 | /// (with arbitrary offsets). |
| 476 | static bool doesAccessArgPointees(FunctionModRefBehavior MRB) { |
| 477 | return isModOrRefSet(createModRefInfo(MRB)) && |
| 478 | (MRB & FMRL_ArgumentPointees); |
| 479 | } |
| 480 | |
| 481 | /// Checks if functions with the specified behavior are known to read and |
| 482 | /// write at most from memory that is inaccessible from LLVM IR. |
| 483 | static bool onlyAccessesInaccessibleMem(FunctionModRefBehavior MRB) { |
| 484 | return !(MRB & FMRL_Anywhere & ~FMRL_InaccessibleMem); |
| 485 | } |
| 486 | |
| 487 | /// Checks if functions with the specified behavior are known to potentially |
| 488 | /// read or write from memory that is inaccessible from LLVM IR. |
| 489 | static bool doesAccessInaccessibleMem(FunctionModRefBehavior MRB) { |
| 490 | return isModOrRefSet(createModRefInfo(MRB)) && (MRB & FMRL_InaccessibleMem); |
| 491 | } |
| 492 | |
| 493 | /// Checks if functions with the specified behavior are known to read and |
| 494 | /// write at most from memory that is inaccessible from LLVM IR or objects |
| 495 | /// pointed to by their pointer-typed arguments (with arbitrary offsets). |
| 496 | static bool onlyAccessesInaccessibleOrArgMem(FunctionModRefBehavior MRB) { |
| 497 | return !(MRB & FMRL_Anywhere & |
| 498 | ~(FMRL_InaccessibleMem | FMRL_ArgumentPointees)); |
| 499 | } |
| 500 | |
| 501 | /// getModRefInfo (for call sites) - Return information about whether |
| 502 | /// a particular call site modifies or reads the specified memory location. |
| 503 | ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc); |
| 504 | |
| 505 | /// getModRefInfo (for call sites) - A convenience wrapper. |
| 506 | ModRefInfo getModRefInfo(ImmutableCallSite CS, const Value *P, |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame^] | 507 | LocationSize Size) { |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 508 | return getModRefInfo(CS, MemoryLocation(P, Size)); |
| 509 | } |
| 510 | |
| 511 | /// getModRefInfo (for calls) - Return information about whether |
| 512 | /// a particular call modifies or reads the specified memory location. |
| 513 | ModRefInfo getModRefInfo(const CallInst *C, const MemoryLocation &Loc) { |
| 514 | return getModRefInfo(ImmutableCallSite(C), Loc); |
| 515 | } |
| 516 | |
| 517 | /// getModRefInfo (for calls) - A convenience wrapper. |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame^] | 518 | ModRefInfo getModRefInfo(const CallInst *C, const Value *P, |
| 519 | LocationSize Size) { |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 520 | return getModRefInfo(C, MemoryLocation(P, Size)); |
| 521 | } |
| 522 | |
| 523 | /// getModRefInfo (for invokes) - Return information about whether |
| 524 | /// a particular invoke modifies or reads the specified memory location. |
| 525 | ModRefInfo getModRefInfo(const InvokeInst *I, const MemoryLocation &Loc) { |
| 526 | return getModRefInfo(ImmutableCallSite(I), Loc); |
| 527 | } |
| 528 | |
| 529 | /// getModRefInfo (for invokes) - A convenience wrapper. |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame^] | 530 | ModRefInfo getModRefInfo(const InvokeInst *I, const Value *P, |
| 531 | LocationSize Size) { |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 532 | return getModRefInfo(I, MemoryLocation(P, Size)); |
| 533 | } |
| 534 | |
| 535 | /// getModRefInfo (for loads) - Return information about whether |
| 536 | /// a particular load modifies or reads the specified memory location. |
| 537 | ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc); |
| 538 | |
| 539 | /// getModRefInfo (for loads) - A convenience wrapper. |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame^] | 540 | ModRefInfo getModRefInfo(const LoadInst *L, const Value *P, |
| 541 | LocationSize Size) { |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 542 | return getModRefInfo(L, MemoryLocation(P, Size)); |
| 543 | } |
| 544 | |
| 545 | /// getModRefInfo (for stores) - Return information about whether |
| 546 | /// a particular store modifies or reads the specified memory location. |
| 547 | ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc); |
| 548 | |
| 549 | /// getModRefInfo (for stores) - A convenience wrapper. |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame^] | 550 | ModRefInfo getModRefInfo(const StoreInst *S, const Value *P, |
| 551 | LocationSize Size) { |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 552 | return getModRefInfo(S, MemoryLocation(P, Size)); |
| 553 | } |
| 554 | |
| 555 | /// getModRefInfo (for fences) - Return information about whether |
| 556 | /// a particular store modifies or reads the specified memory location. |
| 557 | ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc); |
| 558 | |
| 559 | /// getModRefInfo (for fences) - A convenience wrapper. |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame^] | 560 | ModRefInfo getModRefInfo(const FenceInst *S, const Value *P, |
| 561 | LocationSize Size) { |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 562 | return getModRefInfo(S, MemoryLocation(P, Size)); |
| 563 | } |
| 564 | |
| 565 | /// getModRefInfo (for cmpxchges) - Return information about whether |
| 566 | /// a particular cmpxchg modifies or reads the specified memory location. |
| 567 | ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, |
| 568 | const MemoryLocation &Loc); |
| 569 | |
| 570 | /// getModRefInfo (for cmpxchges) - A convenience wrapper. |
| 571 | ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, const Value *P, |
| 572 | unsigned Size) { |
| 573 | return getModRefInfo(CX, MemoryLocation(P, Size)); |
| 574 | } |
| 575 | |
| 576 | /// getModRefInfo (for atomicrmws) - Return information about whether |
| 577 | /// a particular atomicrmw modifies or reads the specified memory location. |
| 578 | ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc); |
| 579 | |
| 580 | /// getModRefInfo (for atomicrmws) - A convenience wrapper. |
| 581 | ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const Value *P, |
| 582 | unsigned Size) { |
| 583 | return getModRefInfo(RMW, MemoryLocation(P, Size)); |
| 584 | } |
| 585 | |
| 586 | /// getModRefInfo (for va_args) - Return information about whether |
| 587 | /// a particular va_arg modifies or reads the specified memory location. |
| 588 | ModRefInfo getModRefInfo(const VAArgInst *I, const MemoryLocation &Loc); |
| 589 | |
| 590 | /// getModRefInfo (for va_args) - A convenience wrapper. |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame^] | 591 | ModRefInfo getModRefInfo(const VAArgInst *I, const Value *P, |
| 592 | LocationSize Size) { |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 593 | return getModRefInfo(I, MemoryLocation(P, Size)); |
| 594 | } |
| 595 | |
| 596 | /// getModRefInfo (for catchpads) - Return information about whether |
| 597 | /// a particular catchpad modifies or reads the specified memory location. |
| 598 | ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc); |
| 599 | |
| 600 | /// getModRefInfo (for catchpads) - A convenience wrapper. |
| 601 | ModRefInfo getModRefInfo(const CatchPadInst *I, const Value *P, |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame^] | 602 | LocationSize Size) { |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 603 | return getModRefInfo(I, MemoryLocation(P, Size)); |
| 604 | } |
| 605 | |
| 606 | /// getModRefInfo (for catchrets) - Return information about whether |
| 607 | /// a particular catchret modifies or reads the specified memory location. |
| 608 | ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc); |
| 609 | |
| 610 | /// getModRefInfo (for catchrets) - A convenience wrapper. |
| 611 | ModRefInfo getModRefInfo(const CatchReturnInst *I, const Value *P, |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame^] | 612 | LocationSize Size) { |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 613 | return getModRefInfo(I, MemoryLocation(P, Size)); |
| 614 | } |
| 615 | |
| 616 | /// Check whether or not an instruction may read or write the optionally |
| 617 | /// specified memory location. |
| 618 | /// |
| 619 | /// |
| 620 | /// An instruction that doesn't read or write memory may be trivially LICM'd |
| 621 | /// for example. |
| 622 | /// |
| 623 | /// For function calls, this delegates to the alias-analysis specific |
| 624 | /// call-site mod-ref behavior queries. Otherwise it delegates to the specific |
| 625 | /// helpers above. |
| 626 | ModRefInfo getModRefInfo(const Instruction *I, |
| 627 | const Optional<MemoryLocation> &OptLoc) { |
| 628 | if (OptLoc == None) { |
| 629 | if (auto CS = ImmutableCallSite(I)) { |
| 630 | return createModRefInfo(getModRefBehavior(CS)); |
| 631 | } |
| 632 | } |
| 633 | |
| 634 | const MemoryLocation &Loc = OptLoc.getValueOr(MemoryLocation()); |
| 635 | |
| 636 | switch (I->getOpcode()) { |
| 637 | case Instruction::VAArg: return getModRefInfo((const VAArgInst*)I, Loc); |
| 638 | case Instruction::Load: return getModRefInfo((const LoadInst*)I, Loc); |
| 639 | case Instruction::Store: return getModRefInfo((const StoreInst*)I, Loc); |
| 640 | case Instruction::Fence: return getModRefInfo((const FenceInst*)I, Loc); |
| 641 | case Instruction::AtomicCmpXchg: |
| 642 | return getModRefInfo((const AtomicCmpXchgInst*)I, Loc); |
| 643 | case Instruction::AtomicRMW: |
| 644 | return getModRefInfo((const AtomicRMWInst*)I, Loc); |
| 645 | case Instruction::Call: return getModRefInfo((const CallInst*)I, Loc); |
| 646 | case Instruction::Invoke: return getModRefInfo((const InvokeInst*)I,Loc); |
| 647 | case Instruction::CatchPad: |
| 648 | return getModRefInfo((const CatchPadInst *)I, Loc); |
| 649 | case Instruction::CatchRet: |
| 650 | return getModRefInfo((const CatchReturnInst *)I, Loc); |
| 651 | default: |
| 652 | return ModRefInfo::NoModRef; |
| 653 | } |
| 654 | } |
| 655 | |
| 656 | /// A convenience wrapper for constructing the memory location. |
| 657 | ModRefInfo getModRefInfo(const Instruction *I, const Value *P, |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame^] | 658 | LocationSize Size) { |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 659 | return getModRefInfo(I, MemoryLocation(P, Size)); |
| 660 | } |
| 661 | |
| 662 | /// Return information about whether a call and an instruction may refer to |
| 663 | /// the same memory locations. |
| 664 | ModRefInfo getModRefInfo(Instruction *I, ImmutableCallSite Call); |
| 665 | |
| 666 | /// Return information about whether two call sites may refer to the same set |
| 667 | /// of memory locations. See the AA documentation for details: |
| 668 | /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo |
| 669 | ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2); |
| 670 | |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame^] | 671 | /// Return information about whether a particular call site modifies |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 672 | /// or reads the specified memory location \p MemLoc before instruction \p I |
| 673 | /// in a BasicBlock. An ordered basic block \p OBB can be used to speed up |
| 674 | /// instruction ordering queries inside the BasicBlock containing \p I. |
| 675 | /// Early exits in callCapturesBefore may lead to ModRefInfo::Must not being |
| 676 | /// set. |
| 677 | ModRefInfo callCapturesBefore(const Instruction *I, |
| 678 | const MemoryLocation &MemLoc, DominatorTree *DT, |
| 679 | OrderedBasicBlock *OBB = nullptr); |
| 680 | |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame^] | 681 | /// A convenience wrapper to synthesize a memory location. |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 682 | ModRefInfo callCapturesBefore(const Instruction *I, const Value *P, |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame^] | 683 | LocationSize Size, DominatorTree *DT, |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 684 | OrderedBasicBlock *OBB = nullptr) { |
| 685 | return callCapturesBefore(I, MemoryLocation(P, Size), DT, OBB); |
| 686 | } |
| 687 | |
| 688 | /// @} |
| 689 | //===--------------------------------------------------------------------===// |
| 690 | /// \name Higher level methods for querying mod/ref information. |
| 691 | /// @{ |
| 692 | |
| 693 | /// Check if it is possible for execution of the specified basic block to |
| 694 | /// modify the location Loc. |
| 695 | bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc); |
| 696 | |
| 697 | /// A convenience wrapper synthesizing a memory location. |
| 698 | bool canBasicBlockModify(const BasicBlock &BB, const Value *P, |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame^] | 699 | LocationSize Size) { |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 700 | return canBasicBlockModify(BB, MemoryLocation(P, Size)); |
| 701 | } |
| 702 | |
| 703 | /// Check if it is possible for the execution of the specified instructions |
| 704 | /// to mod\ref (according to the mode) the location Loc. |
| 705 | /// |
| 706 | /// The instructions to consider are all of the instructions in the range of |
| 707 | /// [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block. |
| 708 | bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, |
| 709 | const MemoryLocation &Loc, |
| 710 | const ModRefInfo Mode); |
| 711 | |
| 712 | /// A convenience wrapper synthesizing a memory location. |
| 713 | bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, |
Andrew Scull | cdfcccc | 2018-10-05 20:58:37 +0100 | [diff] [blame^] | 714 | const Value *Ptr, LocationSize Size, |
Andrew Scull | 5e1ddfa | 2018-08-14 10:06:54 +0100 | [diff] [blame] | 715 | const ModRefInfo Mode) { |
| 716 | return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode); |
| 717 | } |
| 718 | |
| 719 | private: |
| 720 | class Concept; |
| 721 | |
| 722 | template <typename T> class Model; |
| 723 | |
| 724 | template <typename T> friend class AAResultBase; |
| 725 | |
| 726 | const TargetLibraryInfo &TLI; |
| 727 | |
| 728 | std::vector<std::unique_ptr<Concept>> AAs; |
| 729 | |
| 730 | std::vector<AnalysisKey *> AADeps; |
| 731 | }; |
| 732 | |
| 733 | /// Temporary typedef for legacy code that uses a generic \c AliasAnalysis |
| 734 | /// pointer or reference. |
| 735 | using AliasAnalysis = AAResults; |
| 736 | |
| 737 | /// A private abstract base class describing the concept of an individual alias |
| 738 | /// analysis implementation. |
| 739 | /// |
| 740 | /// This interface is implemented by any \c Model instantiation. It is also the |
| 741 | /// interface which a type used to instantiate the model must provide. |
| 742 | /// |
| 743 | /// All of these methods model methods by the same name in the \c |
| 744 | /// AAResults class. Only differences and specifics to how the |
| 745 | /// implementations are called are documented here. |
| 746 | class AAResults::Concept { |
| 747 | public: |
| 748 | virtual ~Concept() = 0; |
| 749 | |
| 750 | /// An update API used internally by the AAResults to provide |
| 751 | /// a handle back to the top level aggregation. |
| 752 | virtual void setAAResults(AAResults *NewAAR) = 0; |
| 753 | |
| 754 | //===--------------------------------------------------------------------===// |
| 755 | /// \name Alias Queries |
| 756 | /// @{ |
| 757 | |
| 758 | /// The main low level interface to the alias analysis implementation. |
| 759 | /// Returns an AliasResult indicating whether the two pointers are aliased to |
| 760 | /// each other. This is the interface that must be implemented by specific |
| 761 | /// alias analysis implementations. |
| 762 | virtual AliasResult alias(const MemoryLocation &LocA, |
| 763 | const MemoryLocation &LocB) = 0; |
| 764 | |
| 765 | /// Checks whether the given location points to constant memory, or if |
| 766 | /// \p OrLocal is true whether it points to a local alloca. |
| 767 | virtual bool pointsToConstantMemory(const MemoryLocation &Loc, |
| 768 | bool OrLocal) = 0; |
| 769 | |
| 770 | /// @} |
| 771 | //===--------------------------------------------------------------------===// |
| 772 | /// \name Simple mod/ref information |
| 773 | /// @{ |
| 774 | |
| 775 | /// Get the ModRef info associated with a pointer argument of a callsite. The |
| 776 | /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note |
| 777 | /// that these bits do not necessarily account for the overall behavior of |
| 778 | /// the function, but rather only provide additional per-argument |
| 779 | /// information. |
| 780 | virtual ModRefInfo getArgModRefInfo(ImmutableCallSite CS, |
| 781 | unsigned ArgIdx) = 0; |
| 782 | |
| 783 | /// Return the behavior of the given call site. |
| 784 | virtual FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) = 0; |
| 785 | |
| 786 | /// Return the behavior when calling the given function. |
| 787 | virtual FunctionModRefBehavior getModRefBehavior(const Function *F) = 0; |
| 788 | |
| 789 | /// getModRefInfo (for call sites) - Return information about whether |
| 790 | /// a particular call site modifies or reads the specified memory location. |
| 791 | virtual ModRefInfo getModRefInfo(ImmutableCallSite CS, |
| 792 | const MemoryLocation &Loc) = 0; |
| 793 | |
| 794 | /// Return information about whether two call sites may refer to the same set |
| 795 | /// of memory locations. See the AA documentation for details: |
| 796 | /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo |
| 797 | virtual ModRefInfo getModRefInfo(ImmutableCallSite CS1, |
| 798 | ImmutableCallSite CS2) = 0; |
| 799 | |
| 800 | /// @} |
| 801 | }; |
| 802 | |
| 803 | /// A private class template which derives from \c Concept and wraps some other |
| 804 | /// type. |
| 805 | /// |
| 806 | /// This models the concept by directly forwarding each interface point to the |
| 807 | /// wrapped type which must implement a compatible interface. This provides |
| 808 | /// a type erased binding. |
| 809 | template <typename AAResultT> class AAResults::Model final : public Concept { |
| 810 | AAResultT &Result; |
| 811 | |
| 812 | public: |
| 813 | explicit Model(AAResultT &Result, AAResults &AAR) : Result(Result) { |
| 814 | Result.setAAResults(&AAR); |
| 815 | } |
| 816 | ~Model() override = default; |
| 817 | |
| 818 | void setAAResults(AAResults *NewAAR) override { Result.setAAResults(NewAAR); } |
| 819 | |
| 820 | AliasResult alias(const MemoryLocation &LocA, |
| 821 | const MemoryLocation &LocB) override { |
| 822 | return Result.alias(LocA, LocB); |
| 823 | } |
| 824 | |
| 825 | bool pointsToConstantMemory(const MemoryLocation &Loc, |
| 826 | bool OrLocal) override { |
| 827 | return Result.pointsToConstantMemory(Loc, OrLocal); |
| 828 | } |
| 829 | |
| 830 | ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) override { |
| 831 | return Result.getArgModRefInfo(CS, ArgIdx); |
| 832 | } |
| 833 | |
| 834 | FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) override { |
| 835 | return Result.getModRefBehavior(CS); |
| 836 | } |
| 837 | |
| 838 | FunctionModRefBehavior getModRefBehavior(const Function *F) override { |
| 839 | return Result.getModRefBehavior(F); |
| 840 | } |
| 841 | |
| 842 | ModRefInfo getModRefInfo(ImmutableCallSite CS, |
| 843 | const MemoryLocation &Loc) override { |
| 844 | return Result.getModRefInfo(CS, Loc); |
| 845 | } |
| 846 | |
| 847 | ModRefInfo getModRefInfo(ImmutableCallSite CS1, |
| 848 | ImmutableCallSite CS2) override { |
| 849 | return Result.getModRefInfo(CS1, CS2); |
| 850 | } |
| 851 | }; |
| 852 | |
| 853 | /// A CRTP-driven "mixin" base class to help implement the function alias |
| 854 | /// analysis results concept. |
| 855 | /// |
| 856 | /// Because of the nature of many alias analysis implementations, they often |
| 857 | /// only implement a subset of the interface. This base class will attempt to |
| 858 | /// implement the remaining portions of the interface in terms of simpler forms |
| 859 | /// of the interface where possible, and otherwise provide conservatively |
| 860 | /// correct fallback implementations. |
| 861 | /// |
| 862 | /// Implementors of an alias analysis should derive from this CRTP, and then |
| 863 | /// override specific methods that they wish to customize. There is no need to |
| 864 | /// use virtual anywhere, the CRTP base class does static dispatch to the |
| 865 | /// derived type passed into it. |
| 866 | template <typename DerivedT> class AAResultBase { |
| 867 | // Expose some parts of the interface only to the AAResults::Model |
| 868 | // for wrapping. Specifically, this allows the model to call our |
| 869 | // setAAResults method without exposing it as a fully public API. |
| 870 | friend class AAResults::Model<DerivedT>; |
| 871 | |
| 872 | /// A pointer to the AAResults object that this AAResult is |
| 873 | /// aggregated within. May be null if not aggregated. |
| 874 | AAResults *AAR; |
| 875 | |
| 876 | /// Helper to dispatch calls back through the derived type. |
| 877 | DerivedT &derived() { return static_cast<DerivedT &>(*this); } |
| 878 | |
| 879 | /// A setter for the AAResults pointer, which is used to satisfy the |
| 880 | /// AAResults::Model contract. |
| 881 | void setAAResults(AAResults *NewAAR) { AAR = NewAAR; } |
| 882 | |
| 883 | protected: |
| 884 | /// This proxy class models a common pattern where we delegate to either the |
| 885 | /// top-level \c AAResults aggregation if one is registered, or to the |
| 886 | /// current result if none are registered. |
| 887 | class AAResultsProxy { |
| 888 | AAResults *AAR; |
| 889 | DerivedT &CurrentResult; |
| 890 | |
| 891 | public: |
| 892 | AAResultsProxy(AAResults *AAR, DerivedT &CurrentResult) |
| 893 | : AAR(AAR), CurrentResult(CurrentResult) {} |
| 894 | |
| 895 | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) { |
| 896 | return AAR ? AAR->alias(LocA, LocB) : CurrentResult.alias(LocA, LocB); |
| 897 | } |
| 898 | |
| 899 | bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal) { |
| 900 | return AAR ? AAR->pointsToConstantMemory(Loc, OrLocal) |
| 901 | : CurrentResult.pointsToConstantMemory(Loc, OrLocal); |
| 902 | } |
| 903 | |
| 904 | ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) { |
| 905 | return AAR ? AAR->getArgModRefInfo(CS, ArgIdx) : CurrentResult.getArgModRefInfo(CS, ArgIdx); |
| 906 | } |
| 907 | |
| 908 | FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) { |
| 909 | return AAR ? AAR->getModRefBehavior(CS) : CurrentResult.getModRefBehavior(CS); |
| 910 | } |
| 911 | |
| 912 | FunctionModRefBehavior getModRefBehavior(const Function *F) { |
| 913 | return AAR ? AAR->getModRefBehavior(F) : CurrentResult.getModRefBehavior(F); |
| 914 | } |
| 915 | |
| 916 | ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc) { |
| 917 | return AAR ? AAR->getModRefInfo(CS, Loc) |
| 918 | : CurrentResult.getModRefInfo(CS, Loc); |
| 919 | } |
| 920 | |
| 921 | ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) { |
| 922 | return AAR ? AAR->getModRefInfo(CS1, CS2) : CurrentResult.getModRefInfo(CS1, CS2); |
| 923 | } |
| 924 | }; |
| 925 | |
| 926 | explicit AAResultBase() = default; |
| 927 | |
| 928 | // Provide all the copy and move constructors so that derived types aren't |
| 929 | // constrained. |
| 930 | AAResultBase(const AAResultBase &Arg) {} |
| 931 | AAResultBase(AAResultBase &&Arg) {} |
| 932 | |
| 933 | /// Get a proxy for the best AA result set to query at this time. |
| 934 | /// |
| 935 | /// When this result is part of a larger aggregation, this will proxy to that |
| 936 | /// aggregation. When this result is used in isolation, it will just delegate |
| 937 | /// back to the derived class's implementation. |
| 938 | /// |
| 939 | /// Note that callers of this need to take considerable care to not cause |
| 940 | /// performance problems when they use this routine, in the case of a large |
| 941 | /// number of alias analyses being aggregated, it can be expensive to walk |
| 942 | /// back across the chain. |
| 943 | AAResultsProxy getBestAAResults() { return AAResultsProxy(AAR, derived()); } |
| 944 | |
| 945 | public: |
| 946 | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) { |
| 947 | return MayAlias; |
| 948 | } |
| 949 | |
| 950 | bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal) { |
| 951 | return false; |
| 952 | } |
| 953 | |
| 954 | ModRefInfo getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) { |
| 955 | return ModRefInfo::ModRef; |
| 956 | } |
| 957 | |
| 958 | FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS) { |
| 959 | return FMRB_UnknownModRefBehavior; |
| 960 | } |
| 961 | |
| 962 | FunctionModRefBehavior getModRefBehavior(const Function *F) { |
| 963 | return FMRB_UnknownModRefBehavior; |
| 964 | } |
| 965 | |
| 966 | ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc) { |
| 967 | return ModRefInfo::ModRef; |
| 968 | } |
| 969 | |
| 970 | ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) { |
| 971 | return ModRefInfo::ModRef; |
| 972 | } |
| 973 | }; |
| 974 | |
| 975 | /// Return true if this pointer is returned by a noalias function. |
| 976 | bool isNoAliasCall(const Value *V); |
| 977 | |
| 978 | /// Return true if this is an argument with the noalias attribute. |
| 979 | bool isNoAliasArgument(const Value *V); |
| 980 | |
| 981 | /// Return true if this pointer refers to a distinct and identifiable object. |
| 982 | /// This returns true for: |
| 983 | /// Global Variables and Functions (but not Global Aliases) |
| 984 | /// Allocas |
| 985 | /// ByVal and NoAlias Arguments |
| 986 | /// NoAlias returns (e.g. calls to malloc) |
| 987 | /// |
| 988 | bool isIdentifiedObject(const Value *V); |
| 989 | |
| 990 | /// Return true if V is umabigously identified at the function-level. |
| 991 | /// Different IdentifiedFunctionLocals can't alias. |
| 992 | /// Further, an IdentifiedFunctionLocal can not alias with any function |
| 993 | /// arguments other than itself, which is not necessarily true for |
| 994 | /// IdentifiedObjects. |
| 995 | bool isIdentifiedFunctionLocal(const Value *V); |
| 996 | |
| 997 | /// A manager for alias analyses. |
| 998 | /// |
| 999 | /// This class can have analyses registered with it and when run, it will run |
| 1000 | /// all of them and aggregate their results into single AA results interface |
| 1001 | /// that dispatches across all of the alias analysis results available. |
| 1002 | /// |
| 1003 | /// Note that the order in which analyses are registered is very significant. |
| 1004 | /// That is the order in which the results will be aggregated and queried. |
| 1005 | /// |
| 1006 | /// This manager effectively wraps the AnalysisManager for registering alias |
| 1007 | /// analyses. When you register your alias analysis with this manager, it will |
| 1008 | /// ensure the analysis itself is registered with its AnalysisManager. |
| 1009 | class AAManager : public AnalysisInfoMixin<AAManager> { |
| 1010 | public: |
| 1011 | using Result = AAResults; |
| 1012 | |
| 1013 | /// Register a specific AA result. |
| 1014 | template <typename AnalysisT> void registerFunctionAnalysis() { |
| 1015 | ResultGetters.push_back(&getFunctionAAResultImpl<AnalysisT>); |
| 1016 | } |
| 1017 | |
| 1018 | /// Register a specific AA result. |
| 1019 | template <typename AnalysisT> void registerModuleAnalysis() { |
| 1020 | ResultGetters.push_back(&getModuleAAResultImpl<AnalysisT>); |
| 1021 | } |
| 1022 | |
| 1023 | Result run(Function &F, FunctionAnalysisManager &AM) { |
| 1024 | Result R(AM.getResult<TargetLibraryAnalysis>(F)); |
| 1025 | for (auto &Getter : ResultGetters) |
| 1026 | (*Getter)(F, AM, R); |
| 1027 | return R; |
| 1028 | } |
| 1029 | |
| 1030 | private: |
| 1031 | friend AnalysisInfoMixin<AAManager>; |
| 1032 | |
| 1033 | static AnalysisKey Key; |
| 1034 | |
| 1035 | SmallVector<void (*)(Function &F, FunctionAnalysisManager &AM, |
| 1036 | AAResults &AAResults), |
| 1037 | 4> ResultGetters; |
| 1038 | |
| 1039 | template <typename AnalysisT> |
| 1040 | static void getFunctionAAResultImpl(Function &F, |
| 1041 | FunctionAnalysisManager &AM, |
| 1042 | AAResults &AAResults) { |
| 1043 | AAResults.addAAResult(AM.template getResult<AnalysisT>(F)); |
| 1044 | AAResults.addAADependencyID(AnalysisT::ID()); |
| 1045 | } |
| 1046 | |
| 1047 | template <typename AnalysisT> |
| 1048 | static void getModuleAAResultImpl(Function &F, FunctionAnalysisManager &AM, |
| 1049 | AAResults &AAResults) { |
| 1050 | auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F); |
| 1051 | auto &MAM = MAMProxy.getManager(); |
| 1052 | if (auto *R = MAM.template getCachedResult<AnalysisT>(*F.getParent())) { |
| 1053 | AAResults.addAAResult(*R); |
| 1054 | MAMProxy |
| 1055 | .template registerOuterAnalysisInvalidation<AnalysisT, AAManager>(); |
| 1056 | } |
| 1057 | } |
| 1058 | }; |
| 1059 | |
| 1060 | /// A wrapper pass to provide the legacy pass manager access to a suitably |
| 1061 | /// prepared AAResults object. |
| 1062 | class AAResultsWrapperPass : public FunctionPass { |
| 1063 | std::unique_ptr<AAResults> AAR; |
| 1064 | |
| 1065 | public: |
| 1066 | static char ID; |
| 1067 | |
| 1068 | AAResultsWrapperPass(); |
| 1069 | |
| 1070 | AAResults &getAAResults() { return *AAR; } |
| 1071 | const AAResults &getAAResults() const { return *AAR; } |
| 1072 | |
| 1073 | bool runOnFunction(Function &F) override; |
| 1074 | |
| 1075 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
| 1076 | }; |
| 1077 | |
| 1078 | FunctionPass *createAAResultsWrapperPass(); |
| 1079 | |
| 1080 | /// A wrapper pass around a callback which can be used to populate the |
| 1081 | /// AAResults in the AAResultsWrapperPass from an external AA. |
| 1082 | /// |
| 1083 | /// The callback provided here will be used each time we prepare an AAResults |
| 1084 | /// object, and will receive a reference to the function wrapper pass, the |
| 1085 | /// function, and the AAResults object to populate. This should be used when |
| 1086 | /// setting up a custom pass pipeline to inject a hook into the AA results. |
| 1087 | ImmutablePass *createExternalAAWrapperPass( |
| 1088 | std::function<void(Pass &, Function &, AAResults &)> Callback); |
| 1089 | |
| 1090 | /// A helper for the legacy pass manager to create a \c AAResults |
| 1091 | /// object populated to the best of our ability for a particular function when |
| 1092 | /// inside of a \c ModulePass or a \c CallGraphSCCPass. |
| 1093 | /// |
| 1094 | /// If a \c ModulePass or a \c CallGraphSCCPass calls \p |
| 1095 | /// createLegacyPMAAResults, it also needs to call \p addUsedAAAnalyses in \p |
| 1096 | /// getAnalysisUsage. |
| 1097 | AAResults createLegacyPMAAResults(Pass &P, Function &F, BasicAAResult &BAR); |
| 1098 | |
| 1099 | /// A helper for the legacy pass manager to populate \p AU to add uses to make |
| 1100 | /// sure the analyses required by \p createLegacyPMAAResults are available. |
| 1101 | void getAAResultsAnalysisUsage(AnalysisUsage &AU); |
| 1102 | |
| 1103 | } // end namespace llvm |
| 1104 | |
| 1105 | #endif // LLVM_ANALYSIS_ALIASANALYSIS_H |