Index: lib/Analysis/ValueTracking.cpp =================================================================== --- lib/Analysis/ValueTracking.cpp +++ lib/Analysis/ValueTracking.cpp @@ -79,34 +79,46 @@ return DL.getPointerTypeSizeInBits(Ty); } -// Many of these functions have internal versions that take an assumption -// exclusion set. This is because of the potential for mutual recursion to -// cause computeKnownBits to repeatedly visit the same assume intrinsic. The -// classic case of this is assume(x = y), which will attempt to determine -// bits in x from bits in y, which will attempt to determine bits in y from -// bits in x, etc. Regarding the mutual recursion, computeKnownBits can call -// isKnownNonZero, which calls computeKnownBits and ComputeSignBit and -// isKnownToBeAPowerOfTwo (all of which can call computeKnownBits), and so on. -typedef SmallPtrSet ExclInvsSet; - namespace { // Simplifying using an assume can only be done in a particular control-flow // context (the context instruction provides that context). If an assume and // the context instruction are not in the same block then the DT helps in // figuring out if we can use it. struct Query { - ExclInvsSet ExclInvs; AssumptionCache *AC; const Instruction *CxtI; const DominatorTree *DT; + /// Set of assumptions that should be excluded from further queries. + /// Many of these functions have internal versions that take an assumption + /// exclusion set. This is because of the potential for mutual recursion to + /// cause computeKnownBits to repeatedly visit the same assume intrinsic. The + /// classic case of this is assume(x = y), which will attempt to determine + /// bits in x from bits in y, which will attempt to determine bits in y from + /// bits in x, etc. Regarding the mutual recursion, computeKnownBits can call + /// isKnownNonZero, which calls computeKnownBits and ComputeSignBit and + /// isKnownToBeAPowerOfTwo (all of which can call computeKnownBits), and so + /// on. + const Value *Excluded[MaxDepth]; + unsigned NumExcluded; + Query(AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr) - : AC(AC), CxtI(CxtI), DT(DT) {} + : AC(AC), CxtI(CxtI), DT(DT), NumExcluded(0) {} Query(const Query &Q, const Value *NewExcl) - : ExclInvs(Q.ExclInvs), AC(Q.AC), CxtI(Q.CxtI), DT(Q.DT) { - ExclInvs.insert(NewExcl); + : AC(Q.AC), CxtI(Q.CxtI), DT(Q.DT), NumExcluded(Q.NumExcluded) { + *Excluded = *Q.Excluded; + assert(NumExcluded < array_lengthof(Excluded)); + Excluded[NumExcluded++] = NewExcl; + } + + bool isExcluded(const Value *Value) const { + for (unsigned I = 0; I < NumExcluded; ++I) { + if (Excluded[I] == Value) + return true; + } + return false; } }; } // end anonymous namespace @@ -740,7 +752,7 @@ CallInst *I = cast(AssumeVH); assert(I->getParent()->getParent() == Q.CxtI->getParent()->getParent() && "Got assumption for the wrong function!"); - if (Q.ExclInvs.count(I)) + if (Q.isExcluded(I)) continue; // Warning: This loop can end up being somewhat performance sensetive.