# Changeset View

Changeset View

# Standalone View

Standalone View

# lib/Analysis/ValueTracking.cpp

Show First 20 Lines • Show All 524 Lines • ▼ Show 20 Line(s) | 523 | } else if (Inv->getParent() == CxtI->getParent()->getSinglePredecessor()) { | |||
---|---|---|---|---|---|

525 | return true; | 525 | return true; | ||

526 | } | 526 | } | ||

527 | 527 | | |||

528 | // With or without a DT, the only remaining case we will check is if the | 528 | // With or without a DT, the only remaining case we will check is if the | ||

529 | // instructions are in the same BB. Give up if that is not the case. | 529 | // instructions are in the same BB. Give up if that is not the case. | ||

530 | if (Inv->getParent() != CxtI->getParent()) | 530 | if (Inv->getParent() != CxtI->getParent()) | ||

531 | return false; | 531 | return false; | ||

532 | 532 | | |||

533 | // If we have a dom tree, then we now know that the assume doens't dominate | 533 | // If we have a dom tree, then we now know that the assume doesn't dominate | ||

534 | // the other instruction. If we don't have a dom tree then we can check if | 534 | // the other instruction. If we don't have a dom tree then we can check if | ||

535 | // the assume is first in the BB. | 535 | // the assume is first in the BB. | ||

536 | if (!DT) { | 536 | if (!DT) { | ||

537 | // Search forward from the assume until we reach the context (or the end | 537 | // Search forward from the assume until we reach the context (or the end | ||

538 | // of the block); the common case is that the assume will come first. | 538 | // of the block); the common case is that the assume will come first. | ||

539 | for (auto I = std::next(BasicBlock::const_iterator(Inv)), | 539 | for (auto I = std::next(BasicBlock::const_iterator(Inv)), | ||

540 | IE = Inv->getParent()->end(); I != IE; ++I) | 540 | IE = Inv->getParent()->end(); I != IE; ++I) | ||

541 | if (&*I == CxtI) | 541 | if (&*I == CxtI) | ||

Show All 27 Lines | 568 | for (auto &AssumeVH : Q.AC->assumptionsFor(V)) { | |||

569 | if (!AssumeVH) | 569 | if (!AssumeVH) | ||

570 | continue; | 570 | continue; | ||

571 | CallInst *I = cast<CallInst>(AssumeVH); | 571 | CallInst *I = cast<CallInst>(AssumeVH); | ||

572 | assert(I->getParent()->getParent() == Q.CxtI->getParent()->getParent() && | 572 | assert(I->getParent()->getParent() == Q.CxtI->getParent()->getParent() && | ||

573 | "Got assumption for the wrong function!"); | 573 | "Got assumption for the wrong function!"); | ||

574 | if (Q.isExcluded(I)) | 574 | if (Q.isExcluded(I)) | ||

575 | continue; | 575 | continue; | ||

576 | 576 | | |||

577 | // Warning: This loop can end up being somewhat performance sensetive. | 577 | // Warning: This loop can end up being somewhat performance sensitive. | ||

578 | // We're running this loop for once for each value queried resulting in a | 578 | // We're running this loop for once for each value queried resulting in a | ||

579 | // runtime of ~O(#assumes * #values). | 579 | // runtime of ~O(#assumes * #values). | ||

580 | 580 | | |||

581 | assert(I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume && | 581 | assert(I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume && | ||

582 | "must be an assume intrinsic"); | 582 | "must be an assume intrinsic"); | ||

583 | 583 | | |||

584 | Value *Arg = I->getArgOperand(0); | 584 | Value *Arg = I->getArgOperand(0); | ||

585 | 585 | | |||

▲ Show 20 Lines • Show All 265 Lines • ▼ Show 20 Line(s) | 849 | << "Detected conflicting code assumptions. Program may " | |||

851 | "internal error."; | 851 | "internal error."; | ||

852 | }); | 852 | }); | ||

853 | } | 853 | } | ||

854 | } | 854 | } | ||

855 | 855 | | |||

856 | /// Compute known bits from a shift operator, including those with a | 856 | /// Compute known bits from a shift operator, including those with a | ||

857 | /// non-constant shift amount. Known is the output of this function. Known2 is a | 857 | /// non-constant shift amount. Known is the output of this function. Known2 is a | ||

858 | /// pre-allocated temporary with the same bit width as Known. KZF and KOF are | 858 | /// pre-allocated temporary with the same bit width as Known. KZF and KOF are | ||

859 | /// operator-specific functors that, given the known-zero or known-one bits | 859 | /// operator-specific functions that, given the known-zero or known-one bits | ||

860 | /// respectively, and a shift amount, compute the implied known-zero or | 860 | /// respectively, and a shift amount, compute the implied known-zero or | ||

861 | /// known-one bits of the shift operator's result respectively for that shift | 861 | /// known-one bits of the shift operator's result respectively for that shift | ||

862 | /// amount. The results from calling KZF and KOF are conservatively combined for | 862 | /// amount. The results from calling KZF and KOF are conservatively combined for | ||

863 | /// all permitted shift amounts. | 863 | /// all permitted shift amounts. | ||

864 | static void computeKnownBitsFromShiftOperator( | 864 | static void computeKnownBitsFromShiftOperator( | ||

865 | const Operator *I, KnownBits &Known, KnownBits &Known2, | 865 | const Operator *I, KnownBits &Known, KnownBits &Known2, | ||

866 | unsigned Depth, const Query &Q, | 866 | unsigned Depth, const Query &Q, | ||

867 | function_ref<APInt(const APInt &, unsigned)> KZF, | 867 | function_ref<APInt(const APInt &, unsigned)> KZF, | ||

▲ Show 20 Lines • Show All 1319 Lines • ▼ Show 20 Line(s) | 2183 | static unsigned ComputeNumSignBits(const Value *V, unsigned Depth, | |||

2187 | return Result; | 2187 | return Result; | ||

2188 | } | 2188 | } | ||

2189 | 2189 | | |||

2190 | /// Return the number of times the sign bit of the register is replicated into | 2190 | /// Return the number of times the sign bit of the register is replicated into | ||

2191 | /// the other bits. We know that at least 1 bit is always equal to the sign bit | 2191 | /// the other bits. We know that at least 1 bit is always equal to the sign bit | ||

2192 | /// (itself), but other cases can give us information. For example, immediately | 2192 | /// (itself), but other cases can give us information. For example, immediately | ||

2193 | /// after an "ashr X, 2", we know that the top 3 bits are all equal to each | 2193 | /// after an "ashr X, 2", we know that the top 3 bits are all equal to each | ||

2194 | /// other, so we return 3. For vectors, return the number of sign bits for the | 2194 | /// other, so we return 3. For vectors, return the number of sign bits for the | ||

2195 | /// vector element with the mininum number of known sign bits. | 2195 | /// vector element with the minimum number of known sign bits. | ||

2196 | static unsigned ComputeNumSignBitsImpl(const Value *V, unsigned Depth, | 2196 | static unsigned ComputeNumSignBitsImpl(const Value *V, unsigned Depth, | ||

2197 | const Query &Q) { | 2197 | const Query &Q) { | ||

2198 | assert(Depth <= MaxDepth && "Limit Search Depth"); | 2198 | assert(Depth <= MaxDepth && "Limit Search Depth"); | ||

2199 | 2199 | | |||

2200 | // We return the minimum number of sign bits that are guaranteed to be present | 2200 | // We return the minimum number of sign bits that are guaranteed to be present | ||

2201 | // in V, so for undef we have to conservatively return 1. We don't have the | 2201 | // in V, so for undef we have to conservatively return 1. We don't have the | ||

2202 | // same behavior for poison though -- that's a FIXME today. | 2202 | // same behavior for poison though -- that's a FIXME today. | ||

2203 | 2203 | | |||

▲ Show 20 Lines • Show All 770 Lines • ▼ Show 20 Line(s) | 2940 | static Value *BuildSubAggregate(Value *From, Value* To, Type *IndexedType, | |||

2974 | // we might be able to find the complete struct somewhere. | 2974 | // we might be able to find the complete struct somewhere. | ||

2975 | 2975 | | |||

2976 | // Find the value that is at that particular spot | 2976 | // Find the value that is at that particular spot | ||

2977 | Value *V = FindInsertedValue(From, Idxs); | 2977 | Value *V = FindInsertedValue(From, Idxs); | ||

2978 | 2978 | | |||

2979 | if (!V) | 2979 | if (!V) | ||

2980 | return nullptr; | 2980 | return nullptr; | ||

2981 | 2981 | | |||

2982 | // Insert the value in the new (sub) aggregrate | 2982 | // Insert the value in the new (sub) aggregate | ||

2983 | return InsertValueInst::Create(To, V, makeArrayRef(Idxs).slice(IdxSkip), | 2983 | return InsertValueInst::Create(To, V, makeArrayRef(Idxs).slice(IdxSkip), | ||

2984 | "tmp", InsertBefore); | 2984 | "tmp", InsertBefore); | ||

2985 | } | 2985 | } | ||

2986 | 2986 | | |||

2987 | // This helper takes a nested struct and extracts a part of it (which is again a | 2987 | // This helper takes a nested struct and extracts a part of it (which is again a | ||

2988 | // struct) into a new value. For example, given the struct: | 2988 | // struct) into a new value. For example, given the struct: | ||

2989 | // { a, { b, { c, d }, e } } | 2989 | // { a, { b, { c, d }, e } } | ||

2990 | // and the indices "1, 1" this returns | 2990 | // and the indices "1, 1" this returns | ||

Show All 12 Lines | 3002 | Type *IndexedType = ExtractValueInst::getIndexedType(From->getType(), | |||

3003 | idx_range); | 3003 | idx_range); | ||

3004 | Value *To = UndefValue::get(IndexedType); | 3004 | Value *To = UndefValue::get(IndexedType); | ||

3005 | SmallVector<unsigned, 10> Idxs(idx_range.begin(), idx_range.end()); | 3005 | SmallVector<unsigned, 10> Idxs(idx_range.begin(), idx_range.end()); | ||

3006 | unsigned IdxSkip = Idxs.size(); | 3006 | unsigned IdxSkip = Idxs.size(); | ||

3007 | 3007 | | |||

3008 | return BuildSubAggregate(From, To, IndexedType, Idxs, IdxSkip, InsertBefore); | 3008 | return BuildSubAggregate(From, To, IndexedType, Idxs, IdxSkip, InsertBefore); | ||

3009 | } | 3009 | } | ||

3010 | 3010 | | |||

3011 | /// Given an aggregrate and an sequence of indices, see if | 3011 | /// Given an aggregate and a sequence of indices, see if | ||

JDevlieghere: Since you're touching these lines anyway, it might be nice to reflow the comment. | |||||

3012 | /// the scalar value indexed is already around as a register, for example if it | 3012 | /// the scalar value indexed is already around as a register, for example if it | ||

3013 | /// were inserted directly into the aggregrate. | 3013 | /// was inserted directly into the aggregate. | ||

3014 | /// | 3014 | /// | ||

3015 | /// If InsertBefore is not null, this function will duplicate (modified) | 3015 | /// If InsertBefore is not null, this function will duplicate (modified) | ||

3016 | /// insertvalues when a part of a nested struct is extracted. | 3016 | /// insertvalues when a part of a nested struct is extracted. | ||

3017 | Value *llvm::FindInsertedValue(Value *V, ArrayRef<unsigned> idx_range, | 3017 | Value *llvm::FindInsertedValue(Value *V, ArrayRef<unsigned> idx_range, | ||

3018 | Instruction *InsertBefore) { | 3018 | Instruction *InsertBefore) { | ||

3019 | // Nothing to index? Just return V then (this is useful at the end of our | 3019 | // Nothing to index? Just return V then (this is useful at the end of our | ||

3020 | // recursion). | 3020 | // recursion). | ||

3021 | if (idx_range.empty()) | 3021 | if (idx_range.empty()) | ||

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

Since you're touching these lines anyway, it might be nice to reflow the comment.