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 94 /// << operator for AliasResult. 95 raw_ostream &operator<<(raw_ostream &OS, AliasResult AR); 96 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. 331 AliasResult alias(const Value *V1, LocationSize V1Size, const Value *V2, 332 LocationSize V2Size) { 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. 349 bool isNoAlias(const Value *V1, LocationSize V1Size, const Value *V2, 350 LocationSize V2Size) { 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, 507 LocationSize Size) { 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. 518 ModRefInfo getModRefInfo(const CallInst *C, const Value *P, 519 LocationSize Size) { 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. 530 ModRefInfo getModRefInfo(const InvokeInst *I, const Value *P, 531 LocationSize Size) { 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. 540 ModRefInfo getModRefInfo(const LoadInst *L, const Value *P, 541 LocationSize Size) { 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. 550 ModRefInfo getModRefInfo(const StoreInst *S, const Value *P, 551 LocationSize Size) { 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. 560 ModRefInfo getModRefInfo(const FenceInst *S, const Value *P, 561 LocationSize Size) { 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. 591 ModRefInfo getModRefInfo(const VAArgInst *I, const Value *P, 592 LocationSize Size) { 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, 602 LocationSize Size) { 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, 612 LocationSize Size) { 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, 658 LocationSize Size) { 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 671 /// Return information about whether a particular call site modifies 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 681 /// A convenience wrapper to synthesize a memory location. 682 ModRefInfo callCapturesBefore(const Instruction *I, const Value *P, 683 LocationSize Size, DominatorTree *DT, 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, 699 LocationSize Size) { 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, 714 const Value *Ptr, LocationSize Size, 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 1106