X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FBasicAliasAnalysis.cpp;h=c3d280350b902d95ed4e41ff7c84c3a179478c37;hb=d77e9352a80c954cf91335c236224e4ca7d9c5f4;hp=dc24a85c97a810def6c562d4b5e3db56a6c92446;hpb=d3a5adc5ba41464aadb5e046e29127b849f163fc;p=oota-llvm.git diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp index dc24a85c97a..c3d280350b9 100644 --- a/lib/Analysis/BasicAliasAnalysis.cpp +++ b/lib/Analysis/BasicAliasAnalysis.cpp @@ -543,7 +543,6 @@ static bool isMemsetPattern16(const Function *MS, isa(MemsetType->getParamType(2))) return true; } - return false; } @@ -583,15 +582,17 @@ FunctionModRefBehavior BasicAAResult::getModRefBehavior(const Function *F) { if (F->onlyAccessesArgMemory()) Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesArgumentPointees); - if (isMemsetPattern16(F, TLI)) - Min = FMRB_OnlyAccessesArgumentPointees; - // Otherwise be conservative. return FunctionModRefBehavior(AAResultBase::getModRefBehavior(F) & Min); } -ModRefInfo BasicAAResult::getArgModRefInfo(ImmutableCallSite CS, - unsigned ArgIdx) { +/// Returns true if this is a writeonly (i.e Mod only) parameter. Currently, +/// we don't have a writeonly attribute, so this only knows about builtin +/// intrinsics and target library functions. We could consider adding a +/// writeonly attribute in the future and moving all of these facts to either +/// Intrinsics.td or InferFunctionAttr.cpp +static bool isWriteOnlyParam(ImmutableCallSite CS, unsigned ArgIdx, + const TargetLibraryInfo &TLI) { if (const IntrinsicInst *II = dyn_cast(CS.getInstruction())) switch (II->getIntrinsicID()) { default: @@ -599,32 +600,49 @@ ModRefInfo BasicAAResult::getArgModRefInfo(ImmutableCallSite CS, case Intrinsic::memset: case Intrinsic::memcpy: case Intrinsic::memmove: - assert((ArgIdx == 0 || ArgIdx == 1) && - "Invalid argument index for memory intrinsic"); - return ArgIdx ? MRI_Ref : MRI_Mod; + // We don't currently have a writeonly attribute. All other properties + // of these intrinsics are nicely described via attributes in + // Intrinsics.td and handled generically. + if (ArgIdx == 0) + return true; } // We can bound the aliasing properties of memset_pattern16 just as we can // for memcpy/memset. This is particularly important because the // LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16 - // whenever possible. - if (CS.getCalledFunction() && - isMemsetPattern16(CS.getCalledFunction(), TLI)) { - assert((ArgIdx == 0 || ArgIdx == 1) && - "Invalid argument index for memset_pattern16"); - return ArgIdx ? MRI_Ref : MRI_Mod; - } - // FIXME: Handle memset_pattern4 and memset_pattern8 also. + // whenever possible. Note that all but the missing writeonly attribute are + // handled via InferFunctionAttr. + if (CS.getCalledFunction() && isMemsetPattern16(CS.getCalledFunction(), TLI)) + if (ArgIdx == 0) + return true; + + // TODO: memset_pattern4, memset_pattern8 + // TODO: _chk variants + // TODO: strcmp, strcpy + + return false; +} + +ModRefInfo BasicAAResult::getArgModRefInfo(ImmutableCallSite CS, + unsigned ArgIdx) { + + // Emulate the missing writeonly attribute by checking for known builtin + // intrinsics and target library functions. + if (isWriteOnlyParam(CS, ArgIdx, TLI)) + return MRI_Mod; + + if (CS.paramHasAttr(ArgIdx + 1, Attribute::ReadOnly)) + return MRI_Ref; + + if (CS.paramHasAttr(ArgIdx + 1, Attribute::ReadNone)) + return MRI_NoModRef; return AAResultBase::getArgModRefInfo(CS, ArgIdx); } static bool isAssumeIntrinsic(ImmutableCallSite CS) { const IntrinsicInst *II = dyn_cast(CS.getInstruction()); - if (II && II->getIntrinsicID() == Intrinsic::assume) - return true; - - return false; + return II && II->getIntrinsicID() == Intrinsic::assume; } #ifndef NDEBUG @@ -776,10 +794,9 @@ static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1, ConstantInt *C2 = dyn_cast(GEP2->getOperand(GEP2->getNumOperands() - 1)); - // If the last (struct) indices aren't constants, we can't say anything. - // If they're identical, the other indices might be also be dynamically - // equal, so the GEPs can alias. - if (!C1 || !C2 || C1 == C2) + // If the last (struct) indices are constants and are equal, the other indices + // might be also be dynamically equal, so the GEPs can alias. + if (C1 && C2 && C1 == C2) return MayAlias; // Find the last-indexed type of the GEP, i.e., the type you'd get if @@ -802,12 +819,49 @@ static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1, IntermediateIndices.push_back(GEP1->getOperand(i + 1)); } - StructType *LastIndexedStruct = - dyn_cast(GetElementPtrInst::getIndexedType( - GEP1->getSourceElementType(), IntermediateIndices)); + auto *Ty = GetElementPtrInst::getIndexedType( + GEP1->getSourceElementType(), IntermediateIndices); + StructType *LastIndexedStruct = dyn_cast(Ty); - if (!LastIndexedStruct) + if (isa(Ty)) { + // We know that: + // - both GEPs begin indexing from the exact same pointer; + // - the last indices in both GEPs are constants, indexing into a sequential + // type (array or pointer); + // - both GEPs only index through arrays prior to that. + // + // Because array indices greater than the number of elements are valid in + // GEPs, unless we know the intermediate indices are identical between + // GEP1 and GEP2 we cannot guarantee that the last indexed arrays don't + // partially overlap. We also need to check that the loaded size matches + // the element size, otherwise we could still have overlap. + const uint64_t ElementSize = + DL.getTypeStoreSize(cast(Ty)->getElementType()); + if (V1Size != ElementSize || V2Size != ElementSize) + return MayAlias; + + for (unsigned i = 0, e = GEP1->getNumIndices() - 1; i != e; ++i) + if (GEP1->getOperand(i + 1) != GEP2->getOperand(i + 1)) + return MayAlias; + + // Now we know that the array/pointer that GEP1 indexes into and that + // that GEP2 indexes into must either precisely overlap or be disjoint. + // Because they cannot partially overlap and because fields in an array + // cannot overlap, if we can prove the final indices are different between + // GEP1 and GEP2, we can conclude GEP1 and GEP2 don't alias. + + // If the last indices are constants, we've already checked they don't + // equal each other so we can exit early. + if (C1 && C2) + return NoAlias; + if (isKnownNonEqual(GEP1->getOperand(GEP1->getNumOperands() - 1), + GEP2->getOperand(GEP2->getNumOperands() - 1), + DL)) + return NoAlias; + return MayAlias; + } else if (!LastIndexedStruct || !C1 || !C2) { return MayAlias; + } // We know that: // - both GEPs begin indexing from the exact same pointer; @@ -1238,7 +1292,7 @@ AliasResult BasicAAResult::aliasPHI(const PHINode *PN, uint64_t PNSize, return Alias; } -/// Provideis a bunch of ad-hoc rules to disambiguate in common cases, such as +/// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as /// array references. AliasResult BasicAAResult::aliasCheck(const Value *V1, uint64_t V1Size, AAMDNodes V1AAInfo, const Value *V2, @@ -1502,11 +1556,10 @@ bool BasicAAResult::constantOffsetHeuristic( // If we've been sext'ed then zext'd the maximum difference between Var0 and // Var1 is possible to calculate, but we're just interested in the absolute - // minumum difference between the two. The minimum distance may occur due to + // minimum difference between the two. The minimum distance may occur due to // wrapping; consider "add i3 %i, 5": if %i == 7 then 7 + 5 mod 8 == 4, and so // the minimum distance between %i and %i + 5 is 3. - APInt MinDiff = V0Offset - V1Offset, - Wrapped = APInt::getMaxValue(Width) - MinDiff + APInt(Width, 1); + APInt MinDiff = V0Offset - V1Offset, Wrapped = -MinDiff; MinDiff = APIntOps::umin(MinDiff, Wrapped); uint64_t MinDiffBytes = MinDiff.getZExtValue() * std::abs(Var0.Scale); @@ -1532,6 +1585,10 @@ BasicAAResult BasicAA::run(Function &F, AnalysisManager *AM) { AM->getCachedResult(F)); } +BasicAAWrapperPass::BasicAAWrapperPass() : FunctionPass(ID) { + initializeBasicAAWrapperPassPass(*PassRegistry::getPassRegistry()); +} + char BasicAAWrapperPass::ID = 0; void BasicAAWrapperPass::anchor() {}