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