Go to the documentation of this file.
48 #define DEBUG_TYPE "loop-peel"
50 STATISTIC(NumPeeled,
"Number of loops peeled");
54 cl::desc(
"Set the unroll peeling count, for testing purposes"));
58 cl::desc(
"Allows loops to be peeled when the dynamic "
59 "trip count is known to be low."));
64 cl::desc(
"Allows loop nests to be peeled."));
68 cl::desc(
"Max average trip count which will cause loop peeling."));
72 cl::desc(
"Force a peel count regardless of profiling information."));
124 "Non-loop Phi should not be checked for turning into invariant.");
127 auto I = IterationsToInvariance.find(Phi);
128 if (
I != IterationsToInvariance.end())
135 IterationsToInvariance[Phi] =
None;
140 else if (
PHINode *IncPhi = dyn_cast<PHINode>(Input)) {
142 if (IncPhi->getParent() != L->
getHeader())
147 IncPhi, L, BackEdge, IterationsToInvariance);
148 if (InputToInvariance)
149 ToInvariance = *InputToInvariance + 1u;
154 IterationsToInvariance[Phi] = ToInvariance;
174 return !isa<UnreachableInst>(
BB->getTerminator());
189 if (
I.mayWriteToMemory())
192 auto Iter = LoadUsers.
find(&
I);
193 if (Iter != LoadUsers.
end()) {
194 for (
Value *U :
I.users())
201 if (
auto *LI = dyn_cast<LoadInst>(&
I)) {
202 Value *Ptr = LI->getPointerOperand();
205 for (
Value *U :
I.users())
231 unsigned DesiredPeelCount = 0;
234 auto *BI = dyn_cast<BranchInst>(
BB->getTerminator());
235 if (!BI || BI->isUnconditional())
242 Value *Condition = BI->getCondition();
243 Value *LeftVal, *RightVal;
258 if (!isa<SCEVAddRecExpr>(LeftSCEV)) {
259 if (isa<SCEVAddRecExpr>(RightSCEV)) {
278 unsigned NewPeelCount = DesiredPeelCount;
291 auto PeelOneMoreIteration = [&IterVal, &NextIterVal, &SE, Step,
293 IterVal = NextIterVal;
294 NextIterVal = SE.getAddExpr(IterVal, Step);
298 auto CanPeelOneMoreIteration = [&NewPeelCount, &MaxPeelCount]() {
299 return NewPeelCount < MaxPeelCount;
302 while (CanPeelOneMoreIteration() &&
303 SE.isKnownPredicate(Pred, IterVal, RightSCEV))
304 PeelOneMoreIteration();
318 !SE.isKnownPredicate(Pred, IterVal, RightSCEV) &&
319 SE.isKnownPredicate(Pred, NextIterVal, RightSCEV)) {
320 if (!CanPeelOneMoreIteration())
322 PeelOneMoreIteration();
325 DesiredPeelCount =
std::max(DesiredPeelCount, NewPeelCount);
328 return DesiredPeelCount;
346 "At least one edge out of the latch must go to the header");
361 assert(LoopSize > 0 &&
"Zero loop size is not allowed!");
379 <<
" iterations.\n");
390 if (2 * LoopSize > Threshold)
393 unsigned AlreadyPeeled = 0;
395 AlreadyPeeled = *Peeled;
412 unsigned DesiredPeelCount = TargetPeelCount;
414 assert(BackEdge &&
"Loop is not in simplified form?");
415 for (
auto BI = L->
getHeader()->
begin(); isa<PHINode>(&*BI); ++BI) {
416 PHINode *Phi = cast<PHINode>(&*BI);
418 IterationsToInvariance);
420 DesiredPeelCount =
std::max(DesiredPeelCount, *ToInvariance);
425 MaxPeelCount =
std::min(MaxPeelCount, Threshold / LoopSize - 1);
427 DesiredPeelCount =
std::max(DesiredPeelCount,
430 if (DesiredPeelCount == 0)
433 if (DesiredPeelCount > 0) {
434 DesiredPeelCount =
std::min(DesiredPeelCount, MaxPeelCount);
436 assert(DesiredPeelCount > 0 &&
"Wrong loop size estimation?");
439 <<
" iteration(s) to turn"
440 <<
" some Phis into invariants.\n");
464 if (!EstimatedTripCount)
468 << *EstimatedTripCount <<
"\n");
470 if (*EstimatedTripCount) {
471 if (*EstimatedTripCount + AlreadyPeeled <= MaxPeelCount) {
472 unsigned PeelCount = *EstimatedTripCount;
473 LLVM_DEBUG(
dbgs() <<
"Peeling first " << PeelCount <<
" iterations.\n");
477 LLVM_DEBUG(
dbgs() <<
"Already peel count: " << AlreadyPeeled <<
"\n");
482 << (Threshold / LoopSize - 1) <<
"\n");
512 if (!FallThroughWeight)
515 unsigned HeaderIdx = (LatchBR->
getSuccessor(0) == Header ? 0 : 1);
520 LatchBR->
setMetadata(LLVMContext::MD_prof, WeightNode);
522 FallThroughWeight > ExitWeight ? FallThroughWeight - ExitWeight : 1;
537 unsigned HeaderIdx = LatchBR->
getSuccessor(0) == Header ? 0 : 1;
538 ExitWeight = HeaderIdx ? TrueWeight : FalseWeight;
539 FallThroughWeight = HeaderIdx ? FalseWeight : TrueWeight;
553 if (!FallThroughWeight)
558 unsigned HeaderIdx = LatchBR->
getSuccessor(0) == Header ? 0 : 1;
562 LatchBR->
setMetadata(LLVMContext::MD_prof, WeightNode);
595 NewBlocks.push_back(NewBB);
628 for (
Loop *ChildLoop : *L) {
629 cloneLoop(ChildLoop, ParentLoop, VMap, LI,
nullptr);
643 BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]);
662 PHINode *NewPHI = cast<PHINode>(VMap[&*
I]);
663 if (IterNumber == 0) {
667 Instruction *LatchInst = dyn_cast<Instruction>(LatchVal);
668 if (LatchInst && L->contains(LatchInst))
669 VMap[&*
I] = LVMap[LatchInst];
671 VMap[&*
I] = LatchVal;
673 cast<BasicBlock>(VMap[Header])->getInstList().erase(NewPHI);
680 for (
auto Edge : ExitEdges)
681 for (
PHINode &PHI : Edge.second->phis()) {
682 Value *LatchVal = PHI.getIncomingValueForBlock(Edge.first);
683 Instruction *LatchInst = dyn_cast<Instruction>(LatchVal);
684 if (LatchInst && L->contains(LatchInst))
685 LatchVal = VMap[LatchVal];
686 PHI.addIncoming(LatchVal, cast<BasicBlock>(VMap[Edge.first]));
693 LVMap[KV.first] = KV.second;
699 Optional<bool> UserAllowProfileBasedPeeling,
bool UnrollingSpecficValues) {
712 if (UnrollingSpecficValues) {
724 if (UserAllowProfileBasedPeeling.
hasValue())
741 bool PreserveLCSSA) {
742 assert(PeelCount > 0 &&
"Attempt to peel out zero iterations?");
743 assert(
canPeel(L) &&
"Attempt to peel a loop which is not peelable?");
762 for (
auto *ChildDomNode : BBDomNode->children()) {
763 auto *ChildBB = ChildDomNode->getBlock();
765 ChildrenToUpdate.push_back(ChildBB);
772 for (
auto *ChildBB : ChildrenToUpdate)
773 NonLoopBlocksIDom[ChildBB] = NewIDom;
838 cast<BranchInst>(cast<BasicBlock>(Latch)->getTerminator());
839 uint64_t ExitWeight = 0, FallThroughWeight = 0;
848 for (
unsigned Iter = 0; Iter < PeelCount; ++Iter) {
853 LoopBlocks, VMap, LVMap, &DT, LI,
854 LoopLocalNoAliasDeclScopes, *SE);
862 for (
auto BBIDom : NonLoopBlocksIDom)
864 cast<BasicBlock>(LVMap[BBIDom.second]));
865 #ifdef EXPENSIVE_CHECKS
869 auto *LatchBRCopy = cast<BranchInst>(VMap[LatchBR]);
873 LatchBRCopy->setMetadata(LLVMContext::MD_loop,
nullptr);
875 InsertTop = InsertBot;
880 F->getBasicBlockList(),
881 NewBlocks[0]->getIterator(),
F->end());
889 Instruction *LatchInst = dyn_cast<Instruction>(NewVal);
890 if (LatchInst && L->
contains(LatchInst))
891 NewVal = LVMap[LatchInst];
899 unsigned AlreadyPeeled = 0;
901 AlreadyPeeled = *Peeled;
910 #ifdef EXPENSIVE_CHECKS
916 simplifyLoop(L, &DT, LI, SE, AC,
nullptr, PreserveLCSSA);
static cl::opt< unsigned > UnrollPeelCount("unroll-peel-count", cl::Hidden, cl::desc("Set the unroll peeling count, for testing purposes"))
const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
static void fixupBranchWeights(BasicBlock *Header, BranchInst *LatchBR, uint64_t ExitWeight, uint64_t FallThroughWeight)
Update the weights of original Latch block after peeling off all iterations.
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
This is an optimization pass for GlobalISel generic memory operations.
NodeT * findNearestCommonDominator(NodeT *A, NodeT *B) const
Find nearest common dominator basic block for basic block A and B.
static void initBranchWeights(BasicBlock *Header, BranchInst *LatchBR, uint64_t &ExitWeight, uint64_t &FallThroughWeight)
Initialize the weights.
A parsed version of the target data layout string in and methods for querying it.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
InstListType::iterator iterator
Instruction iterators...
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
const Function * getParent() const
Return the enclosing method, or null if none.
static bool violatesLegacyMultiExitLoopCheck(Loop *L)
This "heuristic" exactly matches implicit behavior which used to exist inside getLoopEstimatedTripCou...
Represents a single loop in the control flow graph.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
static Optional< unsigned > calculateIterationsToInvariance(PHINode *Phi, Loop *L, BasicBlock *BackEdge, SmallDenseMap< PHINode *, Optional< unsigned > > &IterationsToInvariance)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
static cl::opt< unsigned > UnrollPeelMaxCount("unroll-peel-max-count", cl::init(7), cl::Hidden, cl::desc("Max average trip count which will cause loop peeling."))
The main scalar evolution driver.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isEquality() const
Return true if this predicate is either EQ or NE.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
void getExitEdges(SmallVectorImpl< Edge > &ExitEdges) const
Return all pairs of (inside_block,outside_block).
unsigned getNumSuccessors() const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Optional< bool > evaluatePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Check whether the condition described by Pred, LHS, and RHS is true or false.
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
DomTreeNodeBase * getIDom() const
static unsigned peelToTurnInvariantLoadsDerefencebale(Loop &L, DominatorTree &DT)
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
void setSuccessor(unsigned idx, BasicBlock *NewSucc)
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
LLVM Basic Block Representation.
constexpr bool hasValue() const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
static const char * PeeledCountMetaData
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
llvm::Optional< int > getOptionalIntLoopAttribute(const Loop *TheLoop, StringRef Name)
Find named metadata for a loop with an integer value.
bool match(Val *V, const Pattern &P)
static unsigned countToEliminateCompares(Loop &L, unsigned MaxPeelCount, ScalarEvolution &SE)
iterator begin()
Instruction iterator methods.
void remapInstructionsInBlocks(const SmallVectorImpl< BasicBlock * > &Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight)
Return metadata containing two branch weights.
static cl::opt< unsigned > UnrollForcePeelCount("unroll-force-peel-count", cl::init(0), cl::Hidden, cl::desc("Force a peel count regardless of profiling information."))
Loop * cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, LoopInfo *LI, LPPassManager *LPM)
Recursively clone the specified loop and all of its children, mapping the blocks with the specified m...
iterator_range< block_iterator > blocks() const
Value * getIncomingValueForBlock(const BasicBlock *BB) const
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
void computePeelCount(Loop *L, unsigned LoopSize, TargetTransformInfo::PeelingPreferences &PP, unsigned TripCount, DominatorTree &DT, ScalarEvolution &SE, unsigned Threshold=UINT_MAX)
RPOIterator endRPO() const
bool isDereferenceablePointer(const Value *V, Type *Ty, const DataLayout &DL, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if this is always a dereferenceable pointer.
STATISTIC(NumFunctions, "Total number of functions")
void setName(const Twine &Name)
Change the name of the value.
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
Return all blocks inside the loop that have successors outside of the loop.
int getNumOccurrences() const
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
bool extractProfMetadata(uint64_t &TrueVal, uint64_t &FalseVal) const
Retrieve the raw weight values of a conditional branch or select.
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
std::vector< BasicBlock * >::const_reverse_iterator RPOIterator
Store the result of a depth first search within basic blocks contained by a single loop.
void cloneAndAdaptNoAliasScopes(ArrayRef< MDNode * > NoAliasDeclScopes, ArrayRef< BasicBlock * > NewBlocks, LLVMContext &Context, StringRef Ext)
Clone the specified noalias decl scopes.
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
BasicBlock * CloneBasicBlock(const BasicBlock *BB, ValueToValueMapTy &VMap, const Twine &NameSuffix="", Function *F=nullptr, ClonedCodeInfo *CodeInfo=nullptr, DebugInfoFinder *DIFinder=nullptr)
Return a copy of the specified basic block, but without embedding the block into a particular functio...
This class represents an analyzed expression in the program.
iterator find(ConstPtrType Ptr) const
void addStringMetadataToLoop(Loop *TheLoop, const char *MDString, unsigned V=0)
Set input string into loop metadata by keeping other values intact.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
bool hasNoSelfWrap() const
initializer< Ty > init(const Ty &Val)
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
Optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
void setIncomingValueForBlock(const BasicBlock *BB, Value *V)
Set every incoming value(s) for block BB to V.
bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE, DominatorTree &DT, AssumptionCache *AC, bool PreserveLCSSA)
Peel off the first PeelCount iterations of loop L.
void forgetTopmostLoop(const Loop *L)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
void identifyNoAliasScopesToClone(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< MDNode * > &NoAliasDeclScopes)
Find the 'llvm.experimental.noalias.scope.decl' intrinsics in the specified basic blocks and extract ...
A cache of @llvm.assume calls within a function.
void setSuccessor(unsigned Idx, BasicBlock *BB)
Update the specified successor to point at the provided block.
const SCEV * getConstant(ConstantInt *V)
Type * getType() const
All values are typed, get the type of this value.
static cl::opt< bool > UnrollAllowLoopNestsPeeling("unroll-allow-loop-nests-peeling", cl::init(false), cl::Hidden, cl::desc("Allows loop nests to be peeled."))
LLVMContext & getContext() const
All values hold a context through their type.
self_iterator getIterator()
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static cl::opt< bool > UnrollAllowPeeling("unroll-allow-peeling", cl::init(true), cl::Hidden, cl::desc("Allows loops to be peeled when the dynamic " "trip count is known to be low."))
StringRef getName() const
Return a constant reference to the value's name.
void getUniqueNonLatchExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
Return all unique successor blocks of this loop except successors from Latch block are not considered...
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
LLVMContext & getContext() const
Get the context in which this basic block lives.
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
const Loop * getLoop() const
static void updateBranchWeights(BasicBlock *Header, BranchInst *LatchBR, uint64_t ExitWeight, uint64_t &FallThroughWeight)
Update the branch weights of the latch of a peeled-off loop iteration.
This node represents a polynomial recurrence on the trip count of the specified loop.
BlockT * getHeader() const
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
bool hasProfileData(bool IncludeSynthetic=false) const
Return true if the function is annotated with profile data.
bool IsBlockFollowedByDeoptOrUnreachable(const BasicBlock *BB)
Check if we can prove that all paths starting from this block converge to a block that either has a @...
static void cloneLoopBlocks(Loop *L, unsigned IterNumber, BasicBlock *InsertTop, BasicBlock *InsertBot, SmallVectorImpl< std::pair< BasicBlock *, BasicBlock * >> &ExitEdges, SmallVectorImpl< BasicBlock * > &NewBlocks, LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap, ValueToValueMapTy &LVMap, DominatorTree *DT, LoopInfo *LI, ArrayRef< MDNode * > LoopLocalNoAliasDeclScopes, ScalarEvolution &SE)
Clones the body of the loop L, putting it between InsertTop and InsertBot.
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
const BasicBlock * getParent() const
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Type * getType() const
Return the LLVM type of this SCEV expression.
const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Conditional or Unconditional Branch instruction.
bool contains(ConstPtrType Ptr) const
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
Optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)
Returns a loop's estimated trip count based on branch weight metadata.
LLVM Value Representation.
TargetTransformInfo::PeelingPreferences gatherPeelingPreferences(Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, Optional< bool > UserAllowPeeling, Optional< bool > UserAllowProfileBasedPeeling, bool UnrollingSpecficValues=false)
BasicBlock * getSuccessor(unsigned i) const
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.