Lines Matching +full:scaled +full:- +full:sync
1 //===- BasicAliasAnalysis.cpp - Stateless Alias Analysis Impl -------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
13 //===----------------------------------------------------------------------===//
69 static cl::opt<bool> EnableRecPhiAnalysis("basic-aa-recphi", cl::Hidden,
72 static cl::opt<bool> EnableSeparateStorageAnalysis("basic-aa-separate-storage",
100 //===----------------------------------------------------------------------===//
102 //===----------------------------------------------------------------------===//
145 // - either rewind the pointer q to the base-address of the object in in isObjectSmallerThan()
147 // - just give up. It is up to caller to make sure the pointer is pointing in isObjectSmallerThan()
198 //===----------------------------------------------------------------------===//
200 //===----------------------------------------------------------------------===//
211 BasicBlock *BB = const_cast<BasicBlock *>(I->getParent()); in isNotInCycle()
225 Object, *const_cast<Function *>(DT.getRoot()->getParent()), in isNotCapturedBefore()
229 Ins.first->second.push_back(Object); in isNotCapturedBefore()
231 Iter.first->second = EarliestCapture; in isNotCapturedBefore()
235 if (!Iter.first->second) in isNotCapturedBefore()
242 if (I == Iter.first->second) { in isNotCapturedBefore()
248 return !isPotentiallyReachable(Iter.first->second, I, nullptr, &DT, LI); in isNotCapturedBefore()
254 for (const Value *Obj : Iter->second) in removeInstruction()
260 //===----------------------------------------------------------------------===//
262 //===----------------------------------------------------------------------===//
271 /// Whether trunc(V) is non-negative.
281 return V->getType()->getPrimitiveSizeInBits() - TruncBits + ZExtBits + in getBitWidth()
292 unsigned ExtendBy = V->getType()->getPrimitiveSizeInBits() - in withZExtOfValue()
293 NewV->getType()->getPrimitiveSizeInBits(); in withZExtOfValue()
297 return CastedValue(NewV, ZExtBits, SExtBits, TruncBits - ExtendBy, in withZExtOfValue()
301 ExtendBy -= TruncBits; in withZExtOfValue()
312 unsigned ExtendBy = V->getType()->getPrimitiveSizeInBits() - in withSExtOfValue()
313 NewV->getType()->getPrimitiveSizeInBits(); in withSExtOfValue()
317 return CastedValue(NewV, ZExtBits, SExtBits, TruncBits - ExtendBy, in withSExtOfValue()
321 ExtendBy -= TruncBits; in withSExtOfValue()
328 assert(N.getBitWidth() == V->getType()->getPrimitiveSizeInBits() && in evaluateWith()
330 if (TruncBits) N = N.trunc(N.getBitWidth() - TruncBits); in evaluateWith()
337 assert(N.getBitWidth() == V->getType()->getPrimitiveSizeInBits() && in evaluateWith()
339 if (TruncBits) N = N.truncate(N.getBitWidth() - TruncBits); in evaluateWith()
404 Val.evaluateWith(Const->getValue()), true); in GetLinearExpression()
407 if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) { in GetLinearExpression()
408 APInt RHS = Val.evaluateWith(RHSC->getValue()); in GetLinearExpression()
409 // The only non-OBO case we deal with is or, and only limited to the in GetLinearExpression()
413 NUW &= BOp->hasNoUnsignedWrap(); in GetLinearExpression()
414 NSW &= BOp->hasNoSignedWrap(); in GetLinearExpression()
425 switch (BOp->getOpcode()) { in GetLinearExpression()
432 if (!cast<PossiblyDisjointInst>(BOp)->isDisjoint()) in GetLinearExpression()
437 E = GetLinearExpression(Val.withValue(BOp->getOperand(0), false), DL, in GetLinearExpression()
444 E = GetLinearExpression(Val.withValue(BOp->getOperand(0), false), DL, in GetLinearExpression()
446 E.Offset -= RHS; in GetLinearExpression()
451 E = GetLinearExpression(Val.withValue(BOp->getOperand(0), false), DL, in GetLinearExpression()
457 // shl i8 -128, 36 in GetLinearExpression()
464 E = GetLinearExpression(Val.withValue(BOp->getOperand(0), NSW), DL, in GetLinearExpression()
477 Val.withZExtOfValue(ZExt->getOperand(0), ZExt->hasNonNeg()), DL, in GetLinearExpression()
482 Val.withSExtOfValue(cast<CastInst>(Val.V)->getOperand(0)), in GetLinearExpression()
491 /// that rely on two's complement wrap-arounds for precise alias information
495 unsigned ShiftBits = Offset.getBitWidth() - IndexSize; in adjustToIndexSize()
516 /// negate the Scale, to avoid losing the NSW flag: X - INT_MIN*1 may be
517 /// non-wrapping, while X + INT_MIN*(-1) wraps.
522 return Scale == -Other.Scale; in hasNegatedScaleOf()
531 OS << "(V=" << Val.V->getName() in print()
543 // constant offsets, and variable scaled indices.
549 // Scaled variable (non-constant) indices.
551 // Are all operations inbounds GEPs or non-indexing operations?
560 OS << "(DecomposedGEP Base=" << Base->getName() in print()
574 /// with a constant offset and a number of scaled symbolic offsets.
576 /// The scaled symbolic offsets (represented by pairs of a Value* and a scale
577 /// in the VarIndices vector) are Value*'s that are known to be scaled by the
595 // The only non-operator case we can handle are GlobalAliases. in DecomposeGEPExpression()
597 if (!GA->isInterposable()) { in DecomposeGEPExpression()
598 V = GA->getAliasee(); in DecomposeGEPExpression()
606 if (Op->getOpcode() == Instruction::BitCast || in DecomposeGEPExpression()
607 Op->getOpcode() == Instruction::AddrSpaceCast) { in DecomposeGEPExpression()
608 V = Op->getOperand(0); in DecomposeGEPExpression()
615 // Look through single-arg phi nodes created by LCSSA. in DecomposeGEPExpression()
616 if (PHI->getNumIncomingValues() == 1) { in DecomposeGEPExpression()
617 V = PHI->getIncomingValue(0); in DecomposeGEPExpression()
627 // because it should be in sync with CaptureTracking. Not using it may in DecomposeGEPExpression()
643 Decomposed.InBounds = GEPOp->isInBounds(); in DecomposeGEPExpression()
644 else if (!GEPOp->isInBounds()) in DecomposeGEPExpression()
647 assert(GEPOp->getSourceElementType()->isSized() && "GEP must be sized"); in DecomposeGEPExpression()
649 unsigned AS = GEPOp->getPointerAddressSpace(); in DecomposeGEPExpression()
655 for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end(); in DecomposeGEPExpression()
661 unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue(); in DecomposeGEPExpression()
665 Decomposed.Offset += DL.getStructLayout(STy)->getElementOffset(FieldNo); in DecomposeGEPExpression()
669 // For an array/pointer, add the element offset, explicitly scaled. in DecomposeGEPExpression()
671 if (CIdx->isZero()) in DecomposeGEPExpression()
682 CIdx->getValue().sextOrTrunc(MaxIndexSize); in DecomposeGEPExpression()
696 unsigned Width = Index->getType()->getIntegerBitWidth(); in DecomposeGEPExpression()
697 unsigned SExtBits = IndexSize > Width ? IndexSize - Width : 0; in DecomposeGEPExpression()
698 unsigned TruncBits = IndexSize < Width ? Width - IndexSize : 0; in DecomposeGEPExpression()
704 LE = LE.mul(APInt(IndexSize, TypeSize), GEPOp->isInBounds()); in DecomposeGEPExpression()
710 // A[x][x] -> x*16 + x*4 -> x*20 in DecomposeGEPExpression()
734 // Take care of wrap-arounds in DecomposeGEPExpression()
739 V = GEPOp->getOperand(0); in DecomposeGEPExpression()
740 } while (--MaxLookup); in DecomposeGEPExpression()
775 if (Arg->hasNoAliasAttr() && Arg->onlyReadsMemory()) { in getModRefInfoMask()
784 // global to be marked constant in some modules and non-constant in in getModRefInfoMask()
786 if (!GV->isConstant()) in getModRefInfoMask()
793 Worklist.push_back(SI->getTrueValue()); in getModRefInfoMask()
794 Worklist.push_back(SI->getFalseValue()); in getModRefInfoMask()
802 if (PN->getNumIncomingValues() > MaxLookup) in getModRefInfoMask()
804 append_range(Worklist, PN->incoming_values()); in getModRefInfoMask()
810 } while (!Worklist.empty() && --MaxLookup); in getModRefInfoMask()
821 return II && II->getIntrinsicID() == IID; in isIntrinsicCall()
827 MemoryEffects Min = Call->getAttributes().getMemoryEffects(); in getMemoryEffects()
829 if (const Function *F = dyn_cast<Function>(Call->getCalledOperand())) { in getMemoryEffects()
833 if (Call->hasReadingOperandBundles()) in getMemoryEffects()
835 if (Call->hasClobberingOperandBundles()) in getMemoryEffects()
846 switch (F->getIntrinsicID()) { in getMemoryEffects()
855 return F->getMemoryEffects(); in getMemoryEffects()
860 if (Call->paramHasAttr(ArgIdx, Attribute::WriteOnly)) in getArgModRefInfo()
863 if (Call->paramHasAttr(ArgIdx, Attribute::ReadOnly)) in getArgModRefInfo()
866 if (Call->paramHasAttr(ArgIdx, Attribute::ReadNone)) in getArgModRefInfo()
875 if (!inst->getParent()) in getParent()
877 return inst->getParent()->getParent(); in getParent()
881 return arg->getParent(); in getParent()
924 if (CI->isTailCall() && in getModRefInfo()
925 !CI->getAttributes().hasAttrSomewhere(Attribute::ByVal)) in getModRefInfo()
931 if (!AI->isStaticAlloca() && isIntrinsicCall(Call, Intrinsic::stackrestore)) in getModRefInfo()
940 AAQI.CI->isNotCapturedBefore(Object, Call, /*OrAt*/ false)) { in getModRefInfo()
947 for (auto CI = Call->data_operands_begin(), CE = Call->data_operands_end(); in getModRefInfo()
949 if (!(*CI)->getType()->isPointerTy()) in getModRefInfo()
954 if (Call->doesNotAccessMemory(OperandNo)) in getModRefInfo()
957 // If this is a no-capture pointer argument, see if we can tell that it in getModRefInfo()
967 if (Call->onlyReadsMemory(OperandNo)) { in getModRefInfo()
972 if (Call->onlyWritesMemory(OperandNo)) { in getModRefInfo()
995 // Be conservative if the accessed pointer may alias the allocation - in getModRefInfo()
1063 /// not enough - For example, a negative offset from a noalias argument or call
1073 /// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against
1084 // TODO: This limitation exists for compile-time reasons. Relax it if we in aliasGEP()
1124 DecompGEP1.Offset.sle(-V1Size.getValue()) && in aliasGEP()
1166 // ---------------->| in aliasGEP()
1167 // |-->V1Size |-------> V2Size in aliasGEP()
1171 Off = -Off; in aliasGEP()
1186 // cache. Note that originally offset estimated as GEP1-V2, but in aliasGEP()
1188 AR.setOffset(-Off.getSExtValue()); in aliasGEP()
1205 // VScale Alias Analysis - Given one scalable offset between accesses and a in aliasGEP()
1215 ScalableVar.IsNegated ? -ScalableVar.Scale : ScalableVar.Scale; in aliasGEP()
1291 (GCD - ModOffset).uge(V1Size.getValue())) in aliasGEP()
1305 // VarIndex <= -MinAbsVarIndex || MinAbsVarIndex <= VarIndex. in aliasGEP()
1318 int ValOrigBW = Var.Val.V->getType()->getPrimitiveSizeInBits(); in aliasGEP()
1320 // The max value of abs(V) is 2^ValOrigBW - 1. Multiplying with a in aliasGEP()
1321 // constant smaller than 2^(bitwidth(Val) - ValOrigBW) won't wrap. in aliasGEP()
1322 int MaxScaleValueBW = Var.Val.getBitWidth() - ValOrigBW; in aliasGEP()
1336 // VarIndex = Scale*V0 + (-Scale)*V1. in aliasGEP()
1350 // The constant offset will have added at least +/-MinAbsVarIndex to it. in aliasGEP()
1351 APInt OffsetLo = DecompGEP1.Offset - *MinAbsVarIndex; in aliasGEP()
1354 if (OffsetLo.isNegative() && (-OffsetLo).uge(V1Size.getValue()) && in aliasGEP()
1380 /// Provides a bunch of ad-hoc rules to disambiguate a Select instruction
1389 if (isValueEqualInPotentialCycles(SI->getCondition(), SI2->getCondition(), in aliasSelect()
1392 AAQI.AAR.alias(MemoryLocation(SI->getTrueValue(), SISize), in aliasSelect()
1393 MemoryLocation(SI2->getTrueValue(), V2Size), AAQI); in aliasSelect()
1397 AAQI.AAR.alias(MemoryLocation(SI->getFalseValue(), SISize), in aliasSelect()
1398 MemoryLocation(SI2->getFalseValue(), V2Size), AAQI); in aliasSelect()
1404 AliasResult Alias = AAQI.AAR.alias(MemoryLocation(SI->getTrueValue(), SISize), in aliasSelect()
1410 AAQI.AAR.alias(MemoryLocation(SI->getFalseValue(), SISize), in aliasSelect()
1415 /// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against
1420 if (!PN->getNumIncomingValues()) in aliasPHI()
1426 if (PN2->getParent() == PN->getParent()) { in aliasPHI()
1428 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { in aliasPHI()
1430 MemoryLocation(PN->getIncomingValue(i), PNSize), in aliasPHI()
1432 PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), V2Size), in aliasPHI()
1461 for (Value *PV1 : PN->incoming_values()) { in aliasPHI()
1490 // If V1Srcs is empty then that means that the phi has no underlying non-phi in aliasPHI()
1533 /// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as
1545 V1 = V1->stripPointerCastsForAliasAnalysis(); in aliasCheck()
1546 V2 = V2->stripPointerCastsForAliasAnalysis(); in aliasCheck()
1562 if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy()) in aliasCheck()
1572 if (!NullPointerIsDefined(&F, CPN->getType()->getAddressSpace())) in aliasCheck()
1575 if (!NullPointerIsDefined(&F, CPN->getType()->getAddressSpace())) in aliasCheck()
1590 // non-escaping local object within the same function, then we know the in aliasCheck()
1598 if (isEscapeSource(O1) && AAQI.CI->isNotCapturedBefore( in aliasCheck()
1601 if (isEscapeSource(O2) && AAQI.CI->isNotCapturedBefore( in aliasCheck()
1623 OperandBundleUse OBU = Assume->getOperandBundleAt(Elem.Index); in aliasCheck()
1628 // This is often a no-op; instcombine rewrites this for us. No-op in aliasCheck()
1641 &*PtrA->getParent()->getEntryBlock().begin(); in aliasCheck()
1663 // by using unknown after-pointer sizes for both accesses. This is in aliasCheck()
1674 // FIXME: If this depth limit is hit, then we may cache sub-optimal results in aliasCheck()
1681 // Check the cache before climbing up use-def chains. This also terminates in aliasCheck()
1693 auto &Entry = Pair.first->second; in aliasCheck()
1715 auto &Entry = It->second; in aliasCheck()
1724 AAQI.NumAssumptionUses -= Entry.NumAssumptionUses; in aliasCheck()
1754 It->second.NumAssumptionUses = AAQueryInfo::CacheEntry::Definitive; in aliasCheck()
1827 // Non-instructions and instructions in the entry block cannot be part of in isValueEqualInPotentialCycles()
1830 if (!Inst || Inst->getParent()->isEntryBlock()) in isValueEqualInPotentialCycles()
1836 /// Computes the symbolic difference between two de-composed GEPs.
1840 DestGEP.Offset -= SrcGEP.Offset; in subtractDecomposedGEPs()
1854 Dest.Scale = -Dest.Scale; in subtractDecomposedGEPs()
1862 Dest.Scale -= Src.Scale; in subtractDecomposedGEPs()
1897 Var0.Val.V->getType() != Var1.Val.V->getType()) in constantOffsetHeuristic()
1912 // We have a hit - Var0 and Var1 only differ by a constant offset! in constantOffsetHeuristic()
1919 APInt MinDiff = E0.Offset - E1.Offset, Wrapped = -MinDiff; in constantOffsetHeuristic()
1932 //===----------------------------------------------------------------------===//
1934 //===----------------------------------------------------------------------===//
1953 INITIALIZE_PASS_BEGIN(BasicAAWrapperPass, "basic-aa",
1958 INITIALIZE_PASS_END(BasicAAWrapperPass, "basic-aa", in INITIALIZE_PASS_DEPENDENCY()