# Changeset View

Changeset View

# Standalone View

Standalone View

# lib/Analysis/BasicAliasAnalysis.cpp

Show First 20 Lines • Show All 625 Lines • ▼ Show 20 Line(s) | 442 | bool BasicAAResult::DecomposeGEPExpression(const Value *V, | |||
---|---|---|---|---|---|

626 | SearchLimitReached++; | 626 | SearchLimitReached++; | ||

627 | return true; | 627 | return true; | ||

628 | } | 628 | } | ||

629 | 629 | | |||

630 | /// Returns whether the given pointer value points to memory that is local to | 630 | /// Returns whether the given pointer value points to memory that is local to | ||

631 | /// the function, with global constants being considered local to all | 631 | /// the function, with global constants being considered local to all | ||

632 | /// functions. | 632 | /// functions. | ||

633 | bool BasicAAResult::pointsToConstantMemory(const MemoryLocation &Loc, | 633 | bool BasicAAResult::pointsToConstantMemory(const MemoryLocation &Loc, | ||

634 | bool OrLocal) { | 634 | AAQueryInfo &AAQI, bool OrLocal) { | ||

635 | assert(Visited.empty() && "Visited must be cleared after use!"); | 635 | assert(Visited.empty() && "Visited must be cleared after use!"); | ||

636 | 636 | | |||

637 | unsigned MaxLookup = 8; | 637 | unsigned MaxLookup = 8; | ||

638 | SmallVector<const Value *, 16> Worklist; | 638 | SmallVector<const Value *, 16> Worklist; | ||

639 | Worklist.push_back(Loc.Ptr); | 639 | Worklist.push_back(Loc.Ptr); | ||

640 | do { | 640 | do { | ||

641 | const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), DL); | 641 | const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), DL); | ||

642 | if (!Visited.insert(V).second) { | 642 | if (!Visited.insert(V).second) { | ||

643 | Visited.clear(); | 643 | Visited.clear(); | ||

644 | return AAResultBase::pointsToConstantMemory(Loc, OrLocal); | 644 | return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal); | ||

645 | } | 645 | } | ||

646 | 646 | | |||

647 | // An alloca instruction defines local memory. | 647 | // An alloca instruction defines local memory. | ||

648 | if (OrLocal && isa<AllocaInst>(V)) | 648 | if (OrLocal && isa<AllocaInst>(V)) | ||

649 | continue; | 649 | continue; | ||

650 | 650 | | |||

651 | // A global constant counts as local memory for our purposes. | 651 | // A global constant counts as local memory for our purposes. | ||

652 | if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { | 652 | if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { | ||

653 | // Note: this doesn't require GV to be "ODR" because it isn't legal for a | 653 | // Note: this doesn't require GV to be "ODR" because it isn't legal for a | ||

654 | // global to be marked constant in some modules and non-constant in | 654 | // global to be marked constant in some modules and non-constant in | ||

655 | // others. GV may even be a declaration, not a definition. | 655 | // others. GV may even be a declaration, not a definition. | ||

656 | if (!GV->isConstant()) { | 656 | if (!GV->isConstant()) { | ||

657 | Visited.clear(); | 657 | Visited.clear(); | ||

658 | return AAResultBase::pointsToConstantMemory(Loc, OrLocal); | 658 | return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal); | ||

659 | } | 659 | } | ||

660 | continue; | 660 | continue; | ||

661 | } | 661 | } | ||

662 | 662 | | |||

663 | // If both select values point to local memory, then so does the select. | 663 | // If both select values point to local memory, then so does the select. | ||

664 | if (const SelectInst *SI = dyn_cast<SelectInst>(V)) { | 664 | if (const SelectInst *SI = dyn_cast<SelectInst>(V)) { | ||

665 | Worklist.push_back(SI->getTrueValue()); | 665 | Worklist.push_back(SI->getTrueValue()); | ||

666 | Worklist.push_back(SI->getFalseValue()); | 666 | Worklist.push_back(SI->getFalseValue()); | ||

667 | continue; | 667 | continue; | ||

668 | } | 668 | } | ||

669 | 669 | | |||

670 | // If all values incoming to a phi node point to local memory, then so does | 670 | // If all values incoming to a phi node point to local memory, then so does | ||

671 | // the phi. | 671 | // the phi. | ||

672 | if (const PHINode *PN = dyn_cast<PHINode>(V)) { | 672 | if (const PHINode *PN = dyn_cast<PHINode>(V)) { | ||

673 | // Don't bother inspecting phi nodes with many operands. | 673 | // Don't bother inspecting phi nodes with many operands. | ||

674 | if (PN->getNumIncomingValues() > MaxLookup) { | 674 | if (PN->getNumIncomingValues() > MaxLookup) { | ||

675 | Visited.clear(); | 675 | Visited.clear(); | ||

676 | return AAResultBase::pointsToConstantMemory(Loc, OrLocal); | 676 | return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal); | ||

677 | } | 677 | } | ||

678 | for (Value *IncValue : PN->incoming_values()) | 678 | for (Value *IncValue : PN->incoming_values()) | ||

679 | Worklist.push_back(IncValue); | 679 | Worklist.push_back(IncValue); | ||

680 | continue; | 680 | continue; | ||

681 | } | 681 | } | ||

682 | 682 | | |||

683 | // Otherwise be conservative. | 683 | // Otherwise be conservative. | ||

684 | Visited.clear(); | 684 | Visited.clear(); | ||

685 | return AAResultBase::pointsToConstantMemory(Loc, OrLocal); | 685 | return AAResultBase::pointsToConstantMemory(Loc, AAQI, OrLocal); | ||

686 | } while (!Worklist.empty() && --MaxLookup); | 686 | } while (!Worklist.empty() && --MaxLookup); | ||

687 | 687 | | |||

688 | Visited.clear(); | 688 | Visited.clear(); | ||

689 | return Worklist.empty(); | 689 | return Worklist.empty(); | ||

690 | } | 690 | } | ||

691 | 691 | | |||

692 | /// Returns the behavior when calling the given call site. | 692 | /// Returns the behavior when calling the given call site. | ||

693 | FunctionModRefBehavior BasicAAResult::getModRefBehavior(const CallBase *Call) { | 693 | FunctionModRefBehavior BasicAAResult::getModRefBehavior(const CallBase *Call) { | ||

▲ Show 20 Lines • Show All 118 Lines • ▼ Show 20 Line(s) | 810 | static bool notDifferentParent(const Value *O1, const Value *O2) { | |||

812 | const Function *F1 = getParent(O1); | 812 | const Function *F1 = getParent(O1); | ||

813 | const Function *F2 = getParent(O2); | 813 | const Function *F2 = getParent(O2); | ||

814 | 814 | | |||

815 | return !F1 || !F2 || F1 == F2; | 815 | return !F1 || !F2 || F1 == F2; | ||

816 | } | 816 | } | ||

817 | #endif | 817 | #endif | ||

818 | 818 | | |||

819 | AliasResult BasicAAResult::alias(const MemoryLocation &LocA, | 819 | AliasResult BasicAAResult::alias(const MemoryLocation &LocA, | ||

820 | const MemoryLocation &LocB) { | 820 | const MemoryLocation &LocB, | ||

821 | AAQueryInfo &AAQI) { | ||||

821 | assert(notDifferentParent(LocA.Ptr, LocB.Ptr) && | 822 | assert(notDifferentParent(LocA.Ptr, LocB.Ptr) && | ||

822 | "BasicAliasAnalysis doesn't support interprocedural queries."); | 823 | "BasicAliasAnalysis doesn't support interprocedural queries."); | ||

823 | 824 | | |||

824 | // If we have a directly cached entry for these locations, we have recursed | 825 | // If we have a directly cached entry for these locations, we have recursed | ||

825 | // through this once, so just return the cached results. Notably, when this | 826 | // through this once, so just return the cached results. Notably, when this | ||

826 | // happens, we don't clear the cache. | 827 | // happens, we don't clear the cache. | ||

827 | auto CacheIt = AliasCache.find(LocPair(LocA, LocB)); | 828 | auto CacheIt = AAQI.AliasCache.find(AAQueryInfo::LocPair(LocA, LocB)); | ||

828 | if (CacheIt != AliasCache.end()) | 829 | if (CacheIt != AAQI.AliasCache.end()) | ||

830 | return CacheIt->second; | ||||

831 | | ||||

832 | CacheIt = AAQI.AliasCache.find(AAQueryInfo::LocPair(LocB, LocA)); | ||||

833 | if (CacheIt != AAQI.AliasCache.end()) | ||||

829 | return CacheIt->second; | 834 | return CacheIt->second; | ||

830 | 835 | | |||

831 | AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags, LocB.Ptr, | 836 | AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags, LocB.Ptr, | ||

832 | LocB.Size, LocB.AATags); | 837 | LocB.Size, LocB.AATags, AAQI); | ||

833 | // AliasCache rarely has more than 1 or 2 elements, always use | 838 | | ||

834 | // shrink_and_clear so it quickly returns to the inline capacity of the | | |||

835 | // SmallDenseMap if it ever grows larger. | | |||

836 | // FIXME: This should really be shrink_to_inline_capacity_and_clear(). | | |||

837 | AliasCache.shrink_and_clear(); | | |||

838 | IsCapturedCache.shrink_and_clear(); | | |||

839 | VisitedPhiBBs.clear(); | 839 | VisitedPhiBBs.clear(); | ||

840 | return Alias; | 840 | return Alias; | ||

841 | } | 841 | } | ||

842 | 842 | | |||

843 | /// Checks to see if the specified callsite can clobber the specified memory | 843 | /// Checks to see if the specified callsite can clobber the specified memory | ||

844 | /// object. | 844 | /// object. | ||

845 | /// | 845 | /// | ||

846 | /// Since we only look at local properties of this function, we really can't | 846 | /// Since we only look at local properties of this function, we really can't | ||

847 | /// say much about this query. We do, however, use simple "address taken" | 847 | /// say much about this query. We do, however, use simple "address taken" | ||

848 | /// analysis on local objects. | 848 | /// analysis on local objects. | ||

849 | ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call, | 849 | ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call, | ||

850 | const MemoryLocation &Loc) { | 850 | const MemoryLocation &Loc, | ||

851 | AAQueryInfo &AAQI) { | ||||

851 | assert(notDifferentParent(Call, Loc.Ptr) && | 852 | assert(notDifferentParent(Call, Loc.Ptr) && | ||

852 | "AliasAnalysis query involving multiple functions!"); | 853 | "AliasAnalysis query involving multiple functions!"); | ||

853 | 854 | | |||

854 | const Value *Object = GetUnderlyingObject(Loc.Ptr, DL); | 855 | const Value *Object = GetUnderlyingObject(Loc.Ptr, DL); | ||

855 | 856 | | |||

856 | // Calls marked 'tail' cannot read or write allocas from the current frame | 857 | // Calls marked 'tail' cannot read or write allocas from the current frame | ||

857 | // because the current frame might be destroyed by the time they run. However, | 858 | // because the current frame might be destroyed by the time they run. However, | ||

858 | // a tail call may use an alloca with byval. Calling with byval copies the | 859 | // a tail call may use an alloca with byval. Calling with byval copies the | ||

Show All 10 Lines | |||||

869 | if (auto *AI = dyn_cast<AllocaInst>(Object)) | 870 | if (auto *AI = dyn_cast<AllocaInst>(Object)) | ||

870 | if (!AI->isStaticAlloca() && isIntrinsicCall(Call, Intrinsic::stackrestore)) | 871 | if (!AI->isStaticAlloca() && isIntrinsicCall(Call, Intrinsic::stackrestore)) | ||

871 | return ModRefInfo::Mod; | 872 | return ModRefInfo::Mod; | ||

872 | 873 | | |||

873 | // If the pointer is to a locally allocated object that does not escape, | 874 | // If the pointer is to a locally allocated object that does not escape, | ||

874 | // then the call can not mod/ref the pointer unless the call takes the pointer | 875 | // then the call can not mod/ref the pointer unless the call takes the pointer | ||

875 | // as an argument, and itself doesn't capture it. | 876 | // as an argument, and itself doesn't capture it. | ||

876 | if (!isa<Constant>(Object) && Call != Object && | 877 | if (!isa<Constant>(Object) && Call != Object && | ||

877 | isNonEscapingLocalObject(Object)) { | 878 | isNonEscapingLocalObject(Object, &AAQI.IsCapturedCache)) { | ||

878 | 879 | | |||

879 | // Optimistically assume that call doesn't touch Object and check this | 880 | // Optimistically assume that call doesn't touch Object and check this | ||

880 | // assumption in the following loop. | 881 | // assumption in the following loop. | ||

881 | ModRefInfo Result = ModRefInfo::NoModRef; | 882 | ModRefInfo Result = ModRefInfo::NoModRef; | ||

882 | bool IsMustAlias = true; | 883 | bool IsMustAlias = true; | ||

883 | 884 | | |||

884 | unsigned OperandNo = 0; | 885 | unsigned OperandNo = 0; | ||

885 | for (auto CI = Call->data_operands_begin(), CE = Call->data_operands_end(); | 886 | for (auto CI = Call->data_operands_begin(), CE = Call->data_operands_end(); | ||

Show All 9 Lines | |||||

895 | 896 | | |||

896 | // Call doesn't access memory through this operand, so we don't care | 897 | // Call doesn't access memory through this operand, so we don't care | ||

897 | // if it aliases with Object. | 898 | // if it aliases with Object. | ||

898 | if (Call->doesNotAccessMemory(OperandNo)) | 899 | if (Call->doesNotAccessMemory(OperandNo)) | ||

899 | continue; | 900 | continue; | ||

900 | 901 | | |||

901 | // If this is a no-capture pointer argument, see if we can tell that it | 902 | // If this is a no-capture pointer argument, see if we can tell that it | ||

902 | // is impossible to alias the pointer we're checking. | 903 | // is impossible to alias the pointer we're checking. | ||

903 | AliasResult AR = | 904 | AliasResult AR = getBestAAResults().alias(MemoryLocation(*CI), | ||

904 | getBestAAResults().alias(MemoryLocation(*CI), MemoryLocation(Object)); | 905 | MemoryLocation(Object), AAQI); | ||

905 | if (AR != MustAlias) | 906 | if (AR != MustAlias) | ||

906 | IsMustAlias = false; | 907 | IsMustAlias = false; | ||

907 | // Operand doesn't alias 'Object', continue looking for other aliases | 908 | // Operand doesn't alias 'Object', continue looking for other aliases | ||

908 | if (AR == NoAlias) | 909 | if (AR == NoAlias) | ||

909 | continue; | 910 | continue; | ||

910 | // Operand aliases 'Object', but call doesn't modify it. Strengthen | 911 | // Operand aliases 'Object', but call doesn't modify it. Strengthen | ||

911 | // initial assumption and keep looking in case if there are more aliases. | 912 | // initial assumption and keep looking in case if there are more aliases. | ||

912 | if (Call->onlyReadsMemory(OperandNo)) { | 913 | if (Call->onlyReadsMemory(OperandNo)) { | ||

Show All 29 Lines | |||||

942 | // modify any IR visible value. This is only valid because we assume these | 943 | // modify any IR visible value. This is only valid because we assume these | ||

943 | // routines do not read values visible in the IR. TODO: Consider special | 944 | // routines do not read values visible in the IR. TODO: Consider special | ||

944 | // casing realloc and strdup routines which access only their arguments as | 945 | // casing realloc and strdup routines which access only their arguments as | ||

945 | // well. Or alternatively, replace all of this with inaccessiblememonly once | 946 | // well. Or alternatively, replace all of this with inaccessiblememonly once | ||

946 | // that's implemented fully. | 947 | // that's implemented fully. | ||

947 | if (isMallocOrCallocLikeFn(Call, &TLI)) { | 948 | if (isMallocOrCallocLikeFn(Call, &TLI)) { | ||

948 | // Be conservative if the accessed pointer may alias the allocation - | 949 | // Be conservative if the accessed pointer may alias the allocation - | ||

949 | // fallback to the generic handling below. | 950 | // fallback to the generic handling below. | ||

950 | if (getBestAAResults().alias(MemoryLocation(Call), Loc) == NoAlias) | 951 | if (getBestAAResults().alias(MemoryLocation(Call), Loc, AAQI) == NoAlias) | ||

951 | return ModRefInfo::NoModRef; | 952 | return ModRefInfo::NoModRef; | ||

952 | } | 953 | } | ||

953 | 954 | | |||

954 | // The semantics of memcpy intrinsics forbid overlap between their respective | 955 | // The semantics of memcpy intrinsics forbid overlap between their respective | ||

955 | // operands, i.e., source and destination of any given memcpy must no-alias. | 956 | // operands, i.e., source and destination of any given memcpy must no-alias. | ||

956 | // If Loc must-aliases either one of these two locations, then it necessarily | 957 | // If Loc must-aliases either one of these two locations, then it necessarily | ||

957 | // no-aliases the other. | 958 | // no-aliases the other. | ||

958 | if (auto *Inst = dyn_cast<AnyMemCpyInst>(Call)) { | 959 | if (auto *Inst = dyn_cast<AnyMemCpyInst>(Call)) { | ||

959 | AliasResult SrcAA, DestAA; | 960 | AliasResult SrcAA, DestAA; | ||

960 | 961 | | |||

961 | if ((SrcAA = getBestAAResults().alias(MemoryLocation::getForSource(Inst), | 962 | if ((SrcAA = getBestAAResults().alias(MemoryLocation::getForSource(Inst), | ||

962 | Loc)) == MustAlias) | 963 | Loc, AAQI)) == MustAlias) | ||

963 | // Loc is exactly the memcpy source thus disjoint from memcpy dest. | 964 | // Loc is exactly the memcpy source thus disjoint from memcpy dest. | ||

964 | return ModRefInfo::Ref; | 965 | return ModRefInfo::Ref; | ||

965 | if ((DestAA = getBestAAResults().alias(MemoryLocation::getForDest(Inst), | 966 | if ((DestAA = getBestAAResults().alias(MemoryLocation::getForDest(Inst), | ||

966 | Loc)) == MustAlias) | 967 | Loc, AAQI)) == MustAlias) | ||

967 | // The converse case. | 968 | // The converse case. | ||

968 | return ModRefInfo::Mod; | 969 | return ModRefInfo::Mod; | ||

969 | 970 | | |||

970 | // It's also possible for Loc to alias both src and dest, or neither. | 971 | // It's also possible for Loc to alias both src and dest, or neither. | ||

971 | ModRefInfo rv = ModRefInfo::NoModRef; | 972 | ModRefInfo rv = ModRefInfo::NoModRef; | ||

972 | if (SrcAA != NoAlias) | 973 | if (SrcAA != NoAlias) | ||

973 | rv = setRef(rv); | 974 | rv = setRef(rv); | ||

974 | if (DestAA != NoAlias) | 975 | if (DestAA != NoAlias) | ||

Show All 39 Lines | |||||

1014 | // | 1015 | // | ||

1015 | // The transformation will cause the second store to be ignored (based on | 1016 | // The transformation will cause the second store to be ignored (based on | ||

1016 | // rules of invariant.start) and print 40, while the first program always | 1017 | // rules of invariant.start) and print 40, while the first program always | ||

1017 | // prints 50. | 1018 | // prints 50. | ||

1018 | if (isIntrinsicCall(Call, Intrinsic::invariant_start)) | 1019 | if (isIntrinsicCall(Call, Intrinsic::invariant_start)) | ||

1019 | return ModRefInfo::Ref; | 1020 | return ModRefInfo::Ref; | ||

1020 | 1021 | | |||

1021 | // The AAResultBase base class has some smarts, lets use them. | 1022 | // The AAResultBase base class has some smarts, lets use them. | ||

1022 | return AAResultBase::getModRefInfo(Call, Loc); | 1023 | return AAResultBase::getModRefInfo(Call, Loc, AAQI); | ||

1023 | } | 1024 | } | ||

1024 | 1025 | | |||

1025 | ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call1, | 1026 | ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call1, | ||

1026 | const CallBase *Call2) { | 1027 | const CallBase *Call2, | ||

1028 | AAQueryInfo &AAQI) { | ||||

1027 | // While the assume intrinsic is marked as arbitrarily writing so that | 1029 | // While the assume intrinsic is marked as arbitrarily writing so that | ||

1028 | // proper control dependencies will be maintained, it never aliases any | 1030 | // proper control dependencies will be maintained, it never aliases any | ||

1029 | // particular memory location. | 1031 | // particular memory location. | ||

1030 | if (isIntrinsicCall(Call1, Intrinsic::assume) || | 1032 | if (isIntrinsicCall(Call1, Intrinsic::assume) || | ||

1031 | isIntrinsicCall(Call2, Intrinsic::assume)) | 1033 | isIntrinsicCall(Call2, Intrinsic::assume)) | ||

1032 | return ModRefInfo::NoModRef; | 1034 | return ModRefInfo::NoModRef; | ||

1033 | 1035 | | |||

1034 | // Like assumes, guard intrinsics are also marked as arbitrarily writing so | 1036 | // Like assumes, guard intrinsics are also marked as arbitrarily writing so | ||

Show All 13 Lines | 1048 | return isModSet(createModRefInfo(getModRefBehavior(Call2))) | |||

1048 | : ModRefInfo::NoModRef; | 1050 | : ModRefInfo::NoModRef; | ||

1049 | 1051 | | |||

1050 | if (isIntrinsicCall(Call2, Intrinsic::experimental_guard)) | 1052 | if (isIntrinsicCall(Call2, Intrinsic::experimental_guard)) | ||

1051 | return isModSet(createModRefInfo(getModRefBehavior(Call1))) | 1053 | return isModSet(createModRefInfo(getModRefBehavior(Call1))) | ||

1052 | ? ModRefInfo::Mod | 1054 | ? ModRefInfo::Mod | ||

1053 | : ModRefInfo::NoModRef; | 1055 | : ModRefInfo::NoModRef; | ||

1054 | 1056 | | |||

1055 | // The AAResultBase base class has some smarts, lets use them. | 1057 | // The AAResultBase base class has some smarts, lets use them. | ||

1056 | return AAResultBase::getModRefInfo(Call1, Call2); | 1058 | return AAResultBase::getModRefInfo(Call1, Call2, AAQI); | ||

1057 | } | 1059 | } | ||

1058 | 1060 | | |||

1059 | /// Provide ad-hoc rules to disambiguate accesses through two GEP operators, | 1061 | /// Provide ad-hoc rules to disambiguate accesses through two GEP operators, | ||

1060 | /// both having the exact same pointer operand. | 1062 | /// both having the exact same pointer operand. | ||

1061 | static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1, | 1063 | static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1, | ||

1062 | LocationSize MaybeV1Size, | 1064 | LocationSize MaybeV1Size, | ||

1063 | const GEPOperator *GEP2, | 1065 | const GEPOperator *GEP2, | ||

1064 | LocationSize MaybeV2Size, | 1066 | LocationSize MaybeV2Size, | ||

▲ Show 20 Lines • Show All 215 Lines • ▼ Show 20 Line(s) | |||||

1280 | } | 1282 | } | ||

1281 | 1283 | | |||

1282 | /// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against | 1284 | /// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against | ||

1283 | /// another pointer. | 1285 | /// another pointer. | ||

1284 | /// | 1286 | /// | ||

1285 | /// We know that V1 is a GEP, but we don't know anything about V2. | 1287 | /// We know that V1 is a GEP, but we don't know anything about V2. | ||

1286 | /// UnderlyingV1 is GetUnderlyingObject(GEP1, DL), UnderlyingV2 is the same for | 1288 | /// UnderlyingV1 is GetUnderlyingObject(GEP1, DL), UnderlyingV2 is the same for | ||

1287 | /// V2. | 1289 | /// V2. | ||

1288 | AliasResult | 1290 | AliasResult BasicAAResult::aliasGEP( | ||

1289 | BasicAAResult::aliasGEP(const GEPOperator *GEP1, LocationSize V1Size, | 1291 | const GEPOperator *GEP1, LocationSize V1Size, const AAMDNodes &V1AAInfo, | ||

1290 | const AAMDNodes &V1AAInfo, const Value *V2, | 1292 | const Value *V2, LocationSize V2Size, const AAMDNodes &V2AAInfo, | ||

1291 | LocationSize V2Size, const AAMDNodes &V2AAInfo, | 1293 | const Value *UnderlyingV1, const Value *UnderlyingV2, AAQueryInfo &AAQI) { | ||

1292 | const Value *UnderlyingV1, const Value *UnderlyingV2) { | | |||

1293 | DecomposedGEP DecompGEP1, DecompGEP2; | 1294 | DecomposedGEP DecompGEP1, DecompGEP2; | ||

1294 | unsigned MaxPointerSize = getMaxPointerSize(DL); | 1295 | unsigned MaxPointerSize = getMaxPointerSize(DL); | ||

1295 | DecompGEP1.StructOffset = DecompGEP1.OtherOffset = APInt(MaxPointerSize, 0); | 1296 | DecompGEP1.StructOffset = DecompGEP1.OtherOffset = APInt(MaxPointerSize, 0); | ||

1296 | DecompGEP2.StructOffset = DecompGEP2.OtherOffset = APInt(MaxPointerSize, 0); | 1297 | DecompGEP2.StructOffset = DecompGEP2.OtherOffset = APInt(MaxPointerSize, 0); | ||

1297 | 1298 | | |||

1298 | bool GEP1MaxLookupReached = | 1299 | bool GEP1MaxLookupReached = | ||

1299 | DecomposeGEPExpression(GEP1, DecompGEP1, DL, &AC, DT); | 1300 | DecomposeGEPExpression(GEP1, DecompGEP1, DL, &AC, DT); | ||

1300 | bool GEP2MaxLookupReached = | 1301 | bool GEP2MaxLookupReached = | ||

Show All 19 Lines | 1320 | if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) { | |||

1320 | // Check for the GEP base being at a negative offset, this time in the other | 1321 | // Check for the GEP base being at a negative offset, this time in the other | ||

1321 | // direction. | 1322 | // direction. | ||

1322 | if (!GEP1MaxLookupReached && !GEP2MaxLookupReached && | 1323 | if (!GEP1MaxLookupReached && !GEP2MaxLookupReached && | ||

1323 | isGEPBaseAtNegativeOffset(GEP2, DecompGEP2, DecompGEP1, V1Size)) | 1324 | isGEPBaseAtNegativeOffset(GEP2, DecompGEP2, DecompGEP1, V1Size)) | ||

1324 | return NoAlias; | 1325 | return NoAlias; | ||

1325 | // Do the base pointers alias? | 1326 | // Do the base pointers alias? | ||

1326 | AliasResult BaseAlias = | 1327 | AliasResult BaseAlias = | ||

1327 | aliasCheck(UnderlyingV1, LocationSize::unknown(), AAMDNodes(), | 1328 | aliasCheck(UnderlyingV1, LocationSize::unknown(), AAMDNodes(), | ||

1328 | UnderlyingV2, LocationSize::unknown(), AAMDNodes()); | 1329 | UnderlyingV2, LocationSize::unknown(), AAMDNodes(), AAQI); | ||

1329 | 1330 | | |||

1330 | // Check for geps of non-aliasing underlying pointers where the offsets are | 1331 | // Check for geps of non-aliasing underlying pointers where the offsets are | ||

1331 | // identical. | 1332 | // identical. | ||

1332 | if ((BaseAlias == MayAlias) && V1Size == V2Size) { | 1333 | if ((BaseAlias == MayAlias) && V1Size == V2Size) { | ||

1333 | // Do the base pointers alias assuming type and size. | 1334 | // Do the base pointers alias assuming type and size. | ||

1334 | AliasResult PreciseBaseAlias = aliasCheck(UnderlyingV1, V1Size, V1AAInfo, | 1335 | AliasResult PreciseBaseAlias = aliasCheck( | ||

1335 | UnderlyingV2, V2Size, V2AAInfo); | 1336 | UnderlyingV1, V1Size, V1AAInfo, UnderlyingV2, V2Size, V2AAInfo, AAQI); | ||

1336 | if (PreciseBaseAlias == NoAlias) { | 1337 | if (PreciseBaseAlias == NoAlias) { | ||

1337 | // See if the computed offset from the common pointer tells us about the | 1338 | // See if the computed offset from the common pointer tells us about the | ||

1338 | // relation of the resulting pointer. | 1339 | // relation of the resulting pointer. | ||

1339 | // If the max search depth is reached the result is undefined | 1340 | // If the max search depth is reached the result is undefined | ||

1340 | if (GEP2MaxLookupReached || GEP1MaxLookupReached) | 1341 | if (GEP2MaxLookupReached || GEP1MaxLookupReached) | ||

1341 | return MayAlias; | 1342 | return MayAlias; | ||

1342 | 1343 | | |||

1343 | // Same offsets. | 1344 | // Same offsets. | ||

Show All 38 Lines | 1382 | } else { | |||

1382 | // Check to see if these two pointers are related by the getelementptr | 1383 | // Check to see if these two pointers are related by the getelementptr | ||

1383 | // instruction. If one pointer is a GEP with a non-zero index of the other | 1384 | // instruction. If one pointer is a GEP with a non-zero index of the other | ||

1384 | // pointer, we know they cannot alias. | 1385 | // pointer, we know they cannot alias. | ||

1385 | 1386 | | |||

1386 | // If both accesses are unknown size, we can't do anything useful here. | 1387 | // If both accesses are unknown size, we can't do anything useful here. | ||

1387 | if (V1Size == LocationSize::unknown() && V2Size == LocationSize::unknown()) | 1388 | if (V1Size == LocationSize::unknown() && V2Size == LocationSize::unknown()) | ||

1388 | return MayAlias; | 1389 | return MayAlias; | ||

1389 | 1390 | | |||

1390 | AliasResult R = | 1391 | AliasResult R = aliasCheck(UnderlyingV1, LocationSize::unknown(), | ||

1391 | aliasCheck(UnderlyingV1, LocationSize::unknown(), AAMDNodes(), V2, | 1392 | AAMDNodes(), V2, LocationSize::unknown(), | ||

1392 | LocationSize::unknown(), V2AAInfo, nullptr, UnderlyingV2); | 1393 | V2AAInfo, AAQI, nullptr, UnderlyingV2); | ||

1393 | if (R != MustAlias) { | 1394 | if (R != MustAlias) { | ||

1394 | // If V2 may alias GEP base pointer, conservatively returns MayAlias. | 1395 | // If V2 may alias GEP base pointer, conservatively returns MayAlias. | ||

1395 | // If V2 is known not to alias GEP base pointer, then the two values | 1396 | // If V2 is known not to alias GEP base pointer, then the two values | ||

1396 | // cannot alias per GEP semantics: "Any memory access must be done through | 1397 | // cannot alias per GEP semantics: "Any memory access must be done through | ||

1397 | // a pointer value associated with an address range of the memory access, | 1398 | // a pointer value associated with an address range of the memory access, | ||

1398 | // otherwise the behavior is undefined.". | 1399 | // otherwise the behavior is undefined.". | ||

1399 | assert(R == NoAlias || R == MayAlias); | 1400 | assert(R == NoAlias || R == MayAlias); | ||

1400 | return R; | 1401 | return R; | ||

▲ Show 20 Lines • Show All 117 Lines • ▼ Show 20 Line(s) | 1518 | if ((A == PartialAlias && B == MustAlias) || | |||

1518 | (B == PartialAlias && A == MustAlias)) | 1519 | (B == PartialAlias && A == MustAlias)) | ||

1519 | return PartialAlias; | 1520 | return PartialAlias; | ||

1520 | // Otherwise, we don't know anything. | 1521 | // Otherwise, we don't know anything. | ||

1521 | return MayAlias; | 1522 | return MayAlias; | ||

1522 | } | 1523 | } | ||

1523 | 1524 | | |||

1524 | /// Provides a bunch of ad-hoc rules to disambiguate a Select instruction | 1525 | /// Provides a bunch of ad-hoc rules to disambiguate a Select instruction | ||

1525 | /// against another. | 1526 | /// against another. | ||

1526 | AliasResult BasicAAResult::aliasSelect(const SelectInst *SI, | 1527 | AliasResult | ||

1527 | LocationSize SISize, | 1528 | BasicAAResult::aliasSelect(const SelectInst *SI, LocationSize SISize, | ||

1528 | const AAMDNodes &SIAAInfo, | 1529 | const AAMDNodes &SIAAInfo, const Value *V2, | ||

1529 | const Value *V2, LocationSize V2Size, | 1530 | LocationSize V2Size, const AAMDNodes &V2AAInfo, | ||

1530 | const AAMDNodes &V2AAInfo, | 1531 | const Value *UnderV2, AAQueryInfo &AAQI) { | ||

1531 | const Value *UnderV2) { | | |||

1532 | // If the values are Selects with the same condition, we can do a more precise | 1532 | // If the values are Selects with the same condition, we can do a more precise | ||

1533 | // check: just check for aliases between the values on corresponding arms. | 1533 | // check: just check for aliases between the values on corresponding arms. | ||

1534 | if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2)) | 1534 | if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2)) | ||

1535 | if (SI->getCondition() == SI2->getCondition()) { | 1535 | if (SI->getCondition() == SI2->getCondition()) { | ||

1536 | AliasResult Alias = aliasCheck(SI->getTrueValue(), SISize, SIAAInfo, | 1536 | AliasResult Alias = | ||

1537 | SI2->getTrueValue(), V2Size, V2AAInfo); | 1537 | aliasCheck(SI->getTrueValue(), SISize, SIAAInfo, SI2->getTrueValue(), | ||

1538 | V2Size, V2AAInfo, AAQI); | ||||

1538 | if (Alias == MayAlias) | 1539 | if (Alias == MayAlias) | ||

1539 | return MayAlias; | 1540 | return MayAlias; | ||

1540 | AliasResult ThisAlias = | 1541 | AliasResult ThisAlias = | ||

1541 | aliasCheck(SI->getFalseValue(), SISize, SIAAInfo, | 1542 | aliasCheck(SI->getFalseValue(), SISize, SIAAInfo, | ||

1542 | SI2->getFalseValue(), V2Size, V2AAInfo); | 1543 | SI2->getFalseValue(), V2Size, V2AAInfo, AAQI); | ||

1543 | return MergeAliasResults(ThisAlias, Alias); | 1544 | return MergeAliasResults(ThisAlias, Alias); | ||

1544 | } | 1545 | } | ||

1545 | 1546 | | |||

1546 | // If both arms of the Select node NoAlias or MustAlias V2, then returns | 1547 | // If both arms of the Select node NoAlias or MustAlias V2, then returns | ||

1547 | // NoAlias / MustAlias. Otherwise, returns MayAlias. | 1548 | // NoAlias / MustAlias. Otherwise, returns MayAlias. | ||

1548 | AliasResult Alias = | 1549 | AliasResult Alias = aliasCheck(V2, V2Size, V2AAInfo, SI->getTrueValue(), | ||

1549 | aliasCheck(V2, V2Size, V2AAInfo, SI->getTrueValue(), | 1550 | SISize, SIAAInfo, AAQI, UnderV2); | ||

1550 | SISize, SIAAInfo, UnderV2); | | |||

1551 | if (Alias == MayAlias) | 1551 | if (Alias == MayAlias) | ||

1552 | return MayAlias; | 1552 | return MayAlias; | ||

1553 | 1553 | | |||

1554 | AliasResult ThisAlias = | 1554 | AliasResult ThisAlias = aliasCheck(V2, V2Size, V2AAInfo, SI->getFalseValue(), | ||

1555 | aliasCheck(V2, V2Size, V2AAInfo, SI->getFalseValue(), SISize, SIAAInfo, | 1555 | SISize, SIAAInfo, AAQI, UnderV2); | ||

1556 | UnderV2); | | |||

1557 | return MergeAliasResults(ThisAlias, Alias); | 1556 | return MergeAliasResults(ThisAlias, Alias); | ||

1558 | } | 1557 | } | ||

1559 | 1558 | | |||

1560 | /// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against | 1559 | /// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against | ||

1561 | /// another. | 1560 | /// another. | ||

1562 | AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize, | 1561 | AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize, | ||

1563 | const AAMDNodes &PNAAInfo, const Value *V2, | 1562 | const AAMDNodes &PNAAInfo, const Value *V2, | ||

1564 | LocationSize V2Size, | 1563 | LocationSize V2Size, | ||

1565 | const AAMDNodes &V2AAInfo, | 1564 | const AAMDNodes &V2AAInfo, | ||

1566 | const Value *UnderV2) { | 1565 | const Value *UnderV2, AAQueryInfo &AAQI) { | ||

1567 | // Track phi nodes we have visited. We use this information when we determine | 1566 | // Track phi nodes we have visited. We use this information when we determine | ||

1568 | // value equivalence. | 1567 | // value equivalence. | ||

1569 | VisitedPhiBBs.insert(PN->getParent()); | 1568 | VisitedPhiBBs.insert(PN->getParent()); | ||

1570 | 1569 | | |||

1571 | // If the values are PHIs in the same block, we can do a more precise | 1570 | // If the values are PHIs in the same block, we can do a more precise | ||

1572 | // as well as efficient check: just check for aliases between the values | 1571 | // as well as efficient check: just check for aliases between the values | ||

1573 | // on corresponding edges. | 1572 | // on corresponding edges. | ||

1574 | if (const PHINode *PN2 = dyn_cast<PHINode>(V2)) | 1573 | if (const PHINode *PN2 = dyn_cast<PHINode>(V2)) | ||

1575 | if (PN2->getParent() == PN->getParent()) { | 1574 | if (PN2->getParent() == PN->getParent()) { | ||

1576 | LocPair Locs(MemoryLocation(PN, PNSize, PNAAInfo), | 1575 | AAQueryInfo::LocPair Locs(MemoryLocation(PN, PNSize, PNAAInfo), | ||

1577 | MemoryLocation(V2, V2Size, V2AAInfo)); | 1576 | MemoryLocation(V2, V2Size, V2AAInfo)); | ||

1578 | if (PN > V2) | 1577 | if (PN > V2) | ||

1579 | std::swap(Locs.first, Locs.second); | 1578 | std::swap(Locs.first, Locs.second); | ||

1580 | // Analyse the PHIs' inputs under the assumption that the PHIs are | 1579 | // Analyse the PHIs' inputs under the assumption that the PHIs are | ||

1581 | // NoAlias. | 1580 | // NoAlias. | ||

1582 | // If the PHIs are May/MustAlias there must be (recursively) an input | 1581 | // If the PHIs are May/MustAlias there must be (recursively) an input | ||

1583 | // operand from outside the PHIs' cycle that is MayAlias/MustAlias or | 1582 | // operand from outside the PHIs' cycle that is MayAlias/MustAlias or | ||

1584 | // there must be an operation on the PHIs within the PHIs' value cycle | 1583 | // there must be an operation on the PHIs within the PHIs' value cycle | ||

1585 | // that causes a MayAlias. | 1584 | // that causes a MayAlias. | ||

1586 | // Pretend the phis do not alias. | 1585 | // Pretend the phis do not alias. | ||

1587 | AliasResult Alias = NoAlias; | 1586 | AliasResult Alias = NoAlias; | ||

1588 | AliasResult OrigAliasResult; | 1587 | AliasResult OrigAliasResult; | ||

1589 | { | 1588 | { | ||

1590 | // Limited lifetime iterator invalidated by the aliasCheck call below. | 1589 | // Limited lifetime iterator invalidated by the aliasCheck call below. | ||

1591 | auto CacheIt = AliasCache.find(Locs); | 1590 | auto CacheIt = AAQI.AliasCache.find(Locs); | ||

1592 | assert((CacheIt != AliasCache.end()) && | 1591 | assert((CacheIt != AAQI.AliasCache.end()) && | ||

1593 | "There must exist an entry for the phi node"); | 1592 | "There must exist an entry for the phi node"); | ||

1594 | OrigAliasResult = CacheIt->second; | 1593 | OrigAliasResult = CacheIt->second; | ||

1595 | CacheIt->second = NoAlias; | 1594 | CacheIt->second = NoAlias; | ||

1596 | } | 1595 | } | ||

1597 | 1596 | | |||

1598 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { | 1597 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { | ||

1599 | AliasResult ThisAlias = | 1598 | AliasResult ThisAlias = | ||

1600 | aliasCheck(PN->getIncomingValue(i), PNSize, PNAAInfo, | 1599 | aliasCheck(PN->getIncomingValue(i), PNSize, PNAAInfo, | ||

1601 | PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), | 1600 | PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), | ||

1602 | V2Size, V2AAInfo); | 1601 | V2Size, V2AAInfo, AAQI); | ||

1603 | Alias = MergeAliasResults(ThisAlias, Alias); | 1602 | Alias = MergeAliasResults(ThisAlias, Alias); | ||

1604 | if (Alias == MayAlias) | 1603 | if (Alias == MayAlias) | ||

1605 | break; | 1604 | break; | ||

1606 | } | 1605 | } | ||

1607 | 1606 | | |||

1608 | // Reset if speculation failed. | 1607 | // Reset if speculation failed. | ||

1609 | if (Alias != NoAlias) { | 1608 | if (Alias != NoAlias) { | ||

1610 | auto Pair = AliasCache.insert(std::make_pair(Locs, OrigAliasResult)); | 1609 | auto Pair = | ||

1610 | AAQI.AliasCache.insert(std::make_pair(Locs, OrigAliasResult)); | ||||

1611 | assert(!Pair.second && "Entry must have existed"); | 1611 | assert(!Pair.second && "Entry must have existed"); | ||

1612 | Pair.first->second = OrigAliasResult; | 1612 | Pair.first->second = OrigAliasResult; | ||

1613 | } | 1613 | } | ||

1614 | return Alias; | 1614 | return Alias; | ||

1615 | } | 1615 | } | ||

1616 | 1616 | | |||

1617 | SmallVector<Value *, 4> V1Srcs; | 1617 | SmallVector<Value *, 4> V1Srcs; | ||

1618 | bool isRecursive = false; | 1618 | bool isRecursive = false; | ||

▲ Show 20 Lines • Show All 60 Lines • ▼ Show 20 Line(s) | 1678 | if (V1Srcs.empty()) | |||

1679 | return MayAlias; | 1679 | return MayAlias; | ||

1680 | 1680 | | |||

1681 | // If this PHI node is recursive, set the size of the accessed memory to | 1681 | // If this PHI node is recursive, set the size of the accessed memory to | ||

1682 | // unknown to represent all the possible values the GEP could advance the | 1682 | // unknown to represent all the possible values the GEP could advance the | ||

1683 | // pointer to. | 1683 | // pointer to. | ||

1684 | if (isRecursive) | 1684 | if (isRecursive) | ||

1685 | PNSize = LocationSize::unknown(); | 1685 | PNSize = LocationSize::unknown(); | ||

1686 | 1686 | | |||

1687 | AliasResult Alias = | 1687 | AliasResult Alias = aliasCheck(V2, V2Size, V2AAInfo, V1Srcs[0], PNSize, | ||

1688 | aliasCheck(V2, V2Size, V2AAInfo, V1Srcs[0], | 1688 | PNAAInfo, AAQI, UnderV2); | ||

1689 | PNSize, PNAAInfo, UnderV2); | | |||

1690 | 1689 | | |||

1691 | // Early exit if the check of the first PHI source against V2 is MayAlias. | 1690 | // Early exit if the check of the first PHI source against V2 is MayAlias. | ||

1692 | // Other results are not possible. | 1691 | // Other results are not possible. | ||

1693 | if (Alias == MayAlias) | 1692 | if (Alias == MayAlias) | ||

1694 | return MayAlias; | 1693 | return MayAlias; | ||

1695 | 1694 | | |||

1696 | // If all sources of the PHI node NoAlias or MustAlias V2, then returns | 1695 | // If all sources of the PHI node NoAlias or MustAlias V2, then returns | ||

1697 | // NoAlias / MustAlias. Otherwise, returns MayAlias. | 1696 | // NoAlias / MustAlias. Otherwise, returns MayAlias. | ||

1698 | for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { | 1697 | for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { | ||

1699 | Value *V = V1Srcs[i]; | 1698 | Value *V = V1Srcs[i]; | ||

1700 | 1699 | | |||

1701 | AliasResult ThisAlias = | 1700 | AliasResult ThisAlias = | ||

1702 | aliasCheck(V2, V2Size, V2AAInfo, V, PNSize, PNAAInfo, UnderV2); | 1701 | aliasCheck(V2, V2Size, V2AAInfo, V, PNSize, PNAAInfo, AAQI, UnderV2); | ||

1703 | Alias = MergeAliasResults(ThisAlias, Alias); | 1702 | Alias = MergeAliasResults(ThisAlias, Alias); | ||

1704 | if (Alias == MayAlias) | 1703 | if (Alias == MayAlias) | ||

1705 | break; | 1704 | break; | ||

1706 | } | 1705 | } | ||

1707 | 1706 | | |||

1708 | return Alias; | 1707 | return Alias; | ||

1709 | } | 1708 | } | ||

1710 | 1709 | | |||

1711 | /// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as | 1710 | /// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as | ||

1712 | /// array references. | 1711 | /// array references. | ||

1713 | AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size, | 1712 | AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size, | ||

1714 | AAMDNodes V1AAInfo, const Value *V2, | 1713 | AAMDNodes V1AAInfo, const Value *V2, | ||

1715 | LocationSize V2Size, AAMDNodes V2AAInfo, | 1714 | LocationSize V2Size, AAMDNodes V2AAInfo, | ||

1716 | const Value *O1, const Value *O2) { | 1715 | AAQueryInfo &AAQI, const Value *O1, | ||

1716 | const Value *O2) { | ||||

1717 | // If either of the memory references is empty, it doesn't matter what the | 1717 | // If either of the memory references is empty, it doesn't matter what the | ||

1718 | // pointer values are. | 1718 | // pointer values are. | ||

1719 | if (V1Size.isZero() || V2Size.isZero()) | 1719 | if (V1Size.isZero() || V2Size.isZero()) | ||

1720 | return NoAlias; | 1720 | return NoAlias; | ||

1721 | 1721 | | |||

1722 | // Strip off any casts if they exist. | 1722 | // Strip off any casts if they exist. | ||

1723 | V1 = V1->stripPointerCastsAndInvariantGroups(); | 1723 | V1 = V1->stripPointerCastsAndInvariantGroups(); | ||

1724 | V2 = V2->stripPointerCastsAndInvariantGroups(); | 1724 | V2 = V2->stripPointerCastsAndInvariantGroups(); | ||

▲ Show 20 Lines • Show All 51 Lines • ▼ Show 20 Line(s) | 1759 | if (O1 != O2) { | |||

1776 | // non-escaping local object within the same function, then we know the | 1776 | // non-escaping local object within the same function, then we know the | ||

1777 | // object couldn't escape to a point where the call could return it. | 1777 | // object couldn't escape to a point where the call could return it. | ||

1778 | // | 1778 | // | ||

1779 | // Note that if the pointers are in different functions, there are a | 1779 | // Note that if the pointers are in different functions, there are a | ||

1780 | // variety of complications. A call with a nocapture argument may still | 1780 | // variety of complications. A call with a nocapture argument may still | ||

1781 | // temporary store the nocapture argument's value in a temporary memory | 1781 | // temporary store the nocapture argument's value in a temporary memory | ||

1782 | // location if that memory location doesn't escape. Or it may pass a | 1782 | // location if that memory location doesn't escape. Or it may pass a | ||

1783 | // nocapture value to other functions as long as they don't capture it. | 1783 | // nocapture value to other functions as long as they don't capture it. | ||

1784 | if (isEscapeSource(O1) && isNonEscapingLocalObject(O2, &IsCapturedCache)) | 1784 | if (isEscapeSource(O1) && | ||

1785 | isNonEscapingLocalObject(O2, &AAQI.IsCapturedCache)) | ||||

1785 | return NoAlias; | 1786 | return NoAlias; | ||

1786 | if (isEscapeSource(O2) && isNonEscapingLocalObject(O1, &IsCapturedCache)) | 1787 | if (isEscapeSource(O2) && | ||

1788 | isNonEscapingLocalObject(O1, &AAQI.IsCapturedCache)) | ||||

1787 | return NoAlias; | 1789 | return NoAlias; | ||

1788 | } | 1790 | } | ||

1789 | 1791 | | |||

1790 | // If the size of one access is larger than the entire object on the other | 1792 | // If the size of one access is larger than the entire object on the other | ||

1791 | // side, then we know such behavior is undefined and can assume no alias. | 1793 | // side, then we know such behavior is undefined and can assume no alias. | ||

1792 | bool NullIsValidLocation = NullPointerIsDefined(&F); | 1794 | bool NullIsValidLocation = NullPointerIsDefined(&F); | ||

1793 | if ((V1Size.isPrecise() && isObjectSmallerThan(O2, V1Size.getValue(), DL, TLI, | 1795 | if ((V1Size.isPrecise() && isObjectSmallerThan(O2, V1Size.getValue(), DL, TLI, | ||

1794 | NullIsValidLocation)) || | 1796 | NullIsValidLocation)) || | ||

1795 | (V2Size.isPrecise() && isObjectSmallerThan(O1, V2Size.getValue(), DL, TLI, | 1797 | (V2Size.isPrecise() && isObjectSmallerThan(O1, V2Size.getValue(), DL, TLI, | ||

1796 | NullIsValidLocation))) | 1798 | NullIsValidLocation))) | ||

1797 | return NoAlias; | 1799 | return NoAlias; | ||

1798 | 1800 | | |||

1799 | // Check the cache before climbing up use-def chains. This also terminates | 1801 | // Check the cache before climbing up use-def chains. This also terminates | ||

1800 | // otherwise infinitely recursive queries. | 1802 | // otherwise infinitely recursive queries. | ||

1801 | LocPair Locs(MemoryLocation(V1, V1Size, V1AAInfo), | 1803 | AAQueryInfo::LocPair Locs(MemoryLocation(V1, V1Size, V1AAInfo), | ||

1802 | MemoryLocation(V2, V2Size, V2AAInfo)); | 1804 | MemoryLocation(V2, V2Size, V2AAInfo)); | ||

1803 | if (V1 > V2) | 1805 | if (V1 > V2) | ||

1804 | std::swap(Locs.first, Locs.second); | 1806 | std::swap(Locs.first, Locs.second); | ||

1805 | std::pair<AliasCacheTy::iterator, bool> Pair = | 1807 | std::pair<AAQueryInfo::AliasCacheT::iterator, bool> Pair = | ||

1806 | AliasCache.try_emplace(Locs, MayAlias); | 1808 | AAQI.AliasCache.try_emplace(Locs, MayAlias); | ||

1807 | if (!Pair.second) | 1809 | if (!Pair.second) | ||

1808 | return Pair.first->second; | 1810 | return Pair.first->second; | ||

1809 | 1811 | | |||

1810 | // FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the | 1812 | // FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the | ||

1811 | // GEP can't simplify, we don't even look at the PHI cases. | 1813 | // GEP can't simplify, we don't even look at the PHI cases. | ||

1812 | if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) { | 1814 | if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) { | ||

1813 | std::swap(V1, V2); | 1815 | std::swap(V1, V2); | ||

1814 | std::swap(V1Size, V2Size); | 1816 | std::swap(V1Size, V2Size); | ||

1815 | std::swap(O1, O2); | 1817 | std::swap(O1, O2); | ||

1816 | std::swap(V1AAInfo, V2AAInfo); | 1818 | std::swap(V1AAInfo, V2AAInfo); | ||

1817 | } | 1819 | } | ||

1818 | if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) { | 1820 | if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) { | ||

1819 | AliasResult Result = | 1821 | AliasResult Result = | ||

1820 | aliasGEP(GV1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O1, O2); | 1822 | aliasGEP(GV1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O1, O2, AAQI); | ||

1821 | if (Result != MayAlias) | 1823 | if (Result != MayAlias) { | ||

1822 | return AliasCache[Locs] = Result; | 1824 | auto ItInsPair = AAQI.AliasCache.insert(std::make_pair(Locs, Result)); | ||

1825 | assert(!ItInsPair.second && "Entry must have existed"); | ||||

1826 | ItInsPair.first->second = Result; | ||||

1827 | return Result; | ||||

1828 | } | ||||

1823 | } | 1829 | } | ||

1824 | 1830 | | |||

1825 | if (isa<PHINode>(V2) && !isa<PHINode>(V1)) { | 1831 | if (isa<PHINode>(V2) && !isa<PHINode>(V1)) { | ||

1826 | std::swap(V1, V2); | 1832 | std::swap(V1, V2); | ||

1827 | std::swap(O1, O2); | 1833 | std::swap(O1, O2); | ||

1828 | std::swap(V1Size, V2Size); | 1834 | std::swap(V1Size, V2Size); | ||

1829 | std::swap(V1AAInfo, V2AAInfo); | 1835 | std::swap(V1AAInfo, V2AAInfo); | ||

1830 | } | 1836 | } | ||

1831 | if (const PHINode *PN = dyn_cast<PHINode>(V1)) { | 1837 | if (const PHINode *PN = dyn_cast<PHINode>(V1)) { | ||

1832 | AliasResult Result = aliasPHI(PN, V1Size, V1AAInfo, | 1838 | AliasResult Result = | ||

1833 | V2, V2Size, V2AAInfo, O2); | 1839 | aliasPHI(PN, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O2, AAQI); | ||

1834 | if (Result != MayAlias) { | 1840 | if (Result != MayAlias) { | ||

1835 | Pair = AliasCache.try_emplace(Locs, Result); | 1841 | Pair = AAQI.AliasCache.try_emplace(Locs, Result); | ||

1836 | assert(!Pair.second && "Entry must have existed"); | 1842 | assert(!Pair.second && "Entry must have existed"); | ||

1837 | return Pair.first->second = Result; | 1843 | return Pair.first->second = Result; | ||

1838 | } | 1844 | } | ||

1839 | } | 1845 | } | ||

1840 | 1846 | | |||

1841 | if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) { | 1847 | if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) { | ||

1842 | std::swap(V1, V2); | 1848 | std::swap(V1, V2); | ||

1843 | std::swap(O1, O2); | 1849 | std::swap(O1, O2); | ||

1844 | std::swap(V1Size, V2Size); | 1850 | std::swap(V1Size, V2Size); | ||

1845 | std::swap(V1AAInfo, V2AAInfo); | 1851 | std::swap(V1AAInfo, V2AAInfo); | ||

1846 | } | 1852 | } | ||

1847 | if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) { | 1853 | if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) { | ||

1848 | AliasResult Result = | 1854 | AliasResult Result = | ||

1849 | aliasSelect(S1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O2); | 1855 | aliasSelect(S1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O2, AAQI); | ||

1850 | if (Result != MayAlias) { | 1856 | if (Result != MayAlias) { | ||

1851 | Pair = AliasCache.try_emplace(Locs, Result); | 1857 | Pair = AAQI.AliasCache.try_emplace(Locs, Result); | ||

1852 | assert(!Pair.second && "Entry must have existed"); | 1858 | assert(!Pair.second && "Entry must have existed"); | ||

1853 | return Pair.first->second = Result; | 1859 | return Pair.first->second = Result; | ||

1854 | } | 1860 | } | ||

1855 | } | 1861 | } | ||

1856 | 1862 | | |||

1857 | // If both pointers are pointing into the same object and one of them | 1863 | // If both pointers are pointing into the same object and one of them | ||

1858 | // accesses the entire object, then the accesses must overlap in some way. | 1864 | // accesses the entire object, then the accesses must overlap in some way. | ||

1859 | if (O1 == O2) | 1865 | if (O1 == O2) | ||

1860 | if (V1Size.isPrecise() && V2Size.isPrecise() && | 1866 | if (V1Size.isPrecise() && V2Size.isPrecise() && | ||

1861 | (isObjectSize(O1, V1Size.getValue(), DL, TLI, NullIsValidLocation) || | 1867 | (isObjectSize(O1, V1Size.getValue(), DL, TLI, NullIsValidLocation) || | ||

1862 | isObjectSize(O2, V2Size.getValue(), DL, TLI, NullIsValidLocation))) { | 1868 | isObjectSize(O2, V2Size.getValue(), DL, TLI, NullIsValidLocation))) { | ||

1863 | Pair = AliasCache.try_emplace(Locs, PartialAlias); | 1869 | Pair = AAQI.AliasCache.try_emplace(Locs, PartialAlias); | ||

1864 | assert(!Pair.second && "Entry must have existed"); | 1870 | assert(!Pair.second && "Entry must have existed"); | ||

1865 | return Pair.first->second = PartialAlias; | 1871 | return Pair.first->second = PartialAlias; | ||

1866 | } | 1872 | } | ||

1867 | 1873 | | |||

1868 | // Recurse back into the best AA results we have, potentially with refined | 1874 | // Recurse back into the best AA results we have, potentially with refined | ||

1869 | // memory locations. We have already ensured that BasicAA has a MayAlias | 1875 | // memory locations. We have already ensured that BasicAA has a MayAlias | ||

1870 | // cache result for these, so any recursion back into BasicAA won't loop. | 1876 | // cache result for these, so any recursion back into BasicAA won't loop. | ||

1871 | AliasResult Result = getBestAAResults().alias(Locs.first, Locs.second); | 1877 | AliasResult Result = getBestAAResults().alias(Locs.first, Locs.second, AAQI); | ||

1872 | Pair = AliasCache.try_emplace(Locs, Result); | 1878 | Pair = AAQI.AliasCache.try_emplace(Locs, Result); | ||

1873 | assert(!Pair.second && "Entry must have existed"); | 1879 | assert(!Pair.second && "Entry must have existed"); | ||

1874 | return Pair.first->second = Result; | 1880 | return Pair.first->second = Result; | ||

1875 | } | 1881 | } | ||

1876 | 1882 | | |||

1877 | /// Check whether two Values can be considered equivalent. | 1883 | /// Check whether two Values can be considered equivalent. | ||

1878 | /// | 1884 | /// | ||

1879 | /// In addition to pointer equivalence of \p V1 and \p V2 this checks whether | 1885 | /// In addition to pointer equivalence of \p V1 and \p V2 this checks whether | ||

1880 | /// they can not be part of a cycle in the value graph by looking at all | 1886 | /// they can not be part of a cycle in the value graph by looking at all | ||

▲ Show 20 Lines • Show All 192 Lines • Show Last 20 Lines |