From 72e126a75d57682d78790f2499be50adf862f866 Mon Sep 17 00:00:00 2001 From: Joseph Tremoulet Date: Wed, 10 May 2017 17:57:31 -0700 Subject: Propagate assertions for more checked bounds Generalize (and rename) the assertion/limit code for tracking array lengths (which have until now been recognized by the VNFunc being GT_ARR_LENGTH) to track all values that appear in the function as length arguments to bounds chcks nodes. Add a hashtable to identify that set of value numbers, `m_checkedBoundVNs` to the VNStore object, and populate it during value-numbering. Wherever names were adjusted, the generalization of "array length" is called "checked bound". This allows the array bound check removal machinery to operate on span bound checks as well. --- src/jit/assertionprop.cpp | 68 ++++++++++++------------ src/jit/compiler.h | 20 +++---- src/jit/optcse.cpp | 116 +++++++++++++++++++++------------------- src/jit/rangecheck.cpp | 124 +++++++++++++++++++++---------------------- src/jit/valuenum.cpp | 132 ++++++++++++++++++++++++++++++---------------- src/jit/valuenum.h | 63 ++++++++++++++-------- 6 files changed, 292 insertions(+), 231 deletions(-) (limited to 'src/jit') diff --git a/src/jit/assertionprop.cpp b/src/jit/assertionprop.cpp index 04f2fbed4c..6b322490aa 100644 --- a/src/jit/assertionprop.cpp +++ b/src/jit/assertionprop.cpp @@ -627,12 +627,12 @@ void Compiler::optPrintAssertion(AssertionDsc* curAssertion, AssertionIndex asse vnStore->vnDump(this, curAssertion->op1.bnd.vnLen); printf("]"); } - else if (curAssertion->op1.kind == O1K_ARRLEN_OPER_BND) + else if (curAssertion->op1.kind == O1K_BOUND_OPER_BND) { printf("Oper_Bnd"); vnStore->vnDump(this, curAssertion->op1.vn); } - else if (curAssertion->op1.kind == O1K_ARRLEN_LOOP_BND) + else if (curAssertion->op1.kind == O1K_BOUND_LOOP_BND) { printf("Loop_Bnd"); vnStore->vnDump(this, curAssertion->op1.vn); @@ -711,12 +711,12 @@ void Compiler::optPrintAssertion(AssertionDsc* curAssertion, AssertionIndex asse printf("MT(%08X)", dspPtr(curAssertion->op2.u1.iconVal)); assert(curAssertion->op2.u1.iconFlags != 0); } - else if (curAssertion->op1.kind == O1K_ARRLEN_OPER_BND) + else if (curAssertion->op1.kind == O1K_BOUND_OPER_BND) { assert(!optLocalAssertionProp); vnStore->vnDump(this, curAssertion->op2.vn); } - else if (curAssertion->op1.kind == O1K_ARRLEN_LOOP_BND) + else if (curAssertion->op1.kind == O1K_BOUND_LOOP_BND) { assert(!optLocalAssertionProp); vnStore->vnDump(this, curAssertion->op2.vn); @@ -1625,8 +1625,8 @@ void Compiler::optDebugCheckAssertion(AssertionDsc* assertion) case O1K_ARR_BND: // It would be good to check that bnd.vnIdx and bnd.vnLen are valid value numbers. break; - case O1K_ARRLEN_OPER_BND: - case O1K_ARRLEN_LOOP_BND: + case O1K_BOUND_OPER_BND: + case O1K_BOUND_LOOP_BND: case O1K_CONSTANT_LOOP_BND: case O1K_VALUE_NUMBER: assert(!optLocalAssertionProp); @@ -1702,7 +1702,7 @@ void Compiler::optCreateComplementaryAssertion(AssertionIndex assertionIndex, Ge } AssertionDsc& candidateAssertion = *optGetAssertion(assertionIndex); - if (candidateAssertion.op1.kind == O1K_ARRLEN_OPER_BND || candidateAssertion.op1.kind == O1K_ARRLEN_LOOP_BND || + if (candidateAssertion.op1.kind == O1K_BOUND_OPER_BND || candidateAssertion.op1.kind == O1K_BOUND_LOOP_BND || candidateAssertion.op1.kind == O1K_CONSTANT_LOOP_BND) { AssertionDsc dsc = candidateAssertion; @@ -1768,17 +1768,17 @@ AssertionInfo Compiler::optCreateJTrueBoundsAssertion(GenTreePtr tree) ValueNum vn = op1->gtVNPair.GetConservative(); - ValueNumStore::ArrLenUnsignedBoundInfo arrLenUnsignedBnd; - // Cases where op1 holds the condition with array arithmetic and op2 is 0. - // Loop condition like: "i < a.len +/-k == 0" - // Assertion: "i < a.len +/- k == 0" - if (vnStore->IsVNArrLenArithBound(vn) && + ValueNumStore::UnsignedCompareCheckedBoundInfo unsignedCompareBnd; + // Cases where op1 holds the upper bound arithmetic and op2 is 0. + // Loop condition like: "i < bnd +/-k == 0" + // Assertion: "i < bnd +/- k == 0" + if (vnStore->IsVNCompareCheckedBoundArith(vn) && op2->gtVNPair.GetConservative() == vnStore->VNZeroForType(op2->TypeGet()) && (relop->gtOper == GT_EQ || relop->gtOper == GT_NE)) { AssertionDsc dsc; dsc.assertionKind = relop->gtOper == GT_EQ ? OAK_EQUAL : OAK_NOT_EQUAL; - dsc.op1.kind = O1K_ARRLEN_OPER_BND; + dsc.op1.kind = O1K_BOUND_OPER_BND; dsc.op1.vn = vn; dsc.op2.kind = O2K_CONST_INT; dsc.op2.vn = vnStore->VNZeroForType(op2->TypeGet()); @@ -1788,16 +1788,16 @@ AssertionInfo Compiler::optCreateJTrueBoundsAssertion(GenTreePtr tree) optCreateComplementaryAssertion(index, nullptr, nullptr); return index; } - // Cases where op1 holds the condition array length and op2 is 0. - // Loop condition like: "i < a.len == 0" - // Assertion: "i < a.len == false" - else if (vnStore->IsVNArrLenBound(vn) && + // Cases where op1 holds the upper bound and op2 is 0. + // Loop condition like: "i < bnd == 0" + // Assertion: "i < bnd == false" + else if (vnStore->IsVNCompareCheckedBound(vn) && (op2->gtVNPair.GetConservative() == vnStore->VNZeroForType(op2->TypeGet())) && (relop->gtOper == GT_EQ || relop->gtOper == GT_NE)) { AssertionDsc dsc; dsc.assertionKind = relop->gtOper == GT_EQ ? OAK_EQUAL : OAK_NOT_EQUAL; - dsc.op1.kind = O1K_ARRLEN_LOOP_BND; + dsc.op1.kind = O1K_BOUND_LOOP_BND; dsc.op1.vn = vn; dsc.op2.kind = O2K_CONST_INT; dsc.op2.vn = vnStore->VNZeroForType(op2->TypeGet()); @@ -1807,14 +1807,14 @@ AssertionInfo Compiler::optCreateJTrueBoundsAssertion(GenTreePtr tree) optCreateComplementaryAssertion(index, nullptr, nullptr); return index; } - // Cases where op1 holds the lhs of the condition op2 holds rhs. - // Loop condition like "i < a.len" - // Assertion: "i < a.len != 0" - else if (vnStore->IsVNArrLenBound(relop->gtVNPair.GetConservative())) + // Cases where op1 holds the lhs of the condition op2 holds the bound. + // Loop condition like "i < bnd" + // Assertion: "i < bnd != 0" + else if (vnStore->IsVNCompareCheckedBound(relop->gtVNPair.GetConservative())) { AssertionDsc dsc; dsc.assertionKind = OAK_NOT_EQUAL; - dsc.op1.kind = O1K_ARRLEN_LOOP_BND; + dsc.op1.kind = O1K_BOUND_LOOP_BND; dsc.op1.vn = relop->gtVNPair.GetConservative(); dsc.op2.kind = O2K_CONST_INT; dsc.op2.vn = vnStore->VNZeroForType(TYP_INT); @@ -1824,28 +1824,28 @@ AssertionInfo Compiler::optCreateJTrueBoundsAssertion(GenTreePtr tree) optCreateComplementaryAssertion(index, nullptr, nullptr); return index; } - // Loop condition like "(uint)i < (uint)a.len" or equivalent - // Assertion: "no throw" since this condition guarantees that i is both >= 0 and < a.len (on the appropiate edge) - else if (vnStore->IsVNArrLenUnsignedBound(relop->gtVNPair.GetConservative(), &arrLenUnsignedBnd)) + // Loop condition like "(uint)i < (uint)bnd" or equivalent + // Assertion: "no throw" since this condition guarantees that i is both >= 0 and < bnd (on the appropiate edge) + else if (vnStore->IsVNUnsignedCompareCheckedBound(relop->gtVNPair.GetConservative(), &unsignedCompareBnd)) { - assert(arrLenUnsignedBnd.vnIdx != ValueNumStore::NoVN); - assert((arrLenUnsignedBnd.cmpOper == VNF_LT_UN) || (arrLenUnsignedBnd.cmpOper == VNF_GE_UN)); - assert(vnStore->IsVNArrLen(arrLenUnsignedBnd.vnLen)); + assert(unsignedCompareBnd.vnIdx != ValueNumStore::NoVN); + assert((unsignedCompareBnd.cmpOper == VNF_LT_UN) || (unsignedCompareBnd.cmpOper == VNF_GE_UN)); + assert(vnStore->IsVNCheckedBound(unsignedCompareBnd.vnBound)); AssertionDsc dsc; dsc.assertionKind = OAK_NO_THROW; dsc.op1.kind = O1K_ARR_BND; dsc.op1.vn = relop->gtVNPair.GetConservative(); - dsc.op1.bnd.vnIdx = arrLenUnsignedBnd.vnIdx; - dsc.op1.bnd.vnLen = arrLenUnsignedBnd.vnLen; + dsc.op1.bnd.vnIdx = unsignedCompareBnd.vnIdx; + dsc.op1.bnd.vnLen = unsignedCompareBnd.vnBound; dsc.op2.kind = O2K_INVALID; dsc.op2.vn = ValueNumStore::NoVN; AssertionIndex index = optAddAssertion(&dsc); - if (arrLenUnsignedBnd.cmpOper == VNF_GE_UN) + if (unsignedCompareBnd.cmpOper == VNF_GE_UN) { - // By default JTRUE generated assertions hold on the "jump" edge. We have i >= a.len but we're really - // after i < a.len so we need to change the assertion edge to "next". + // By default JTRUE generated assertions hold on the "jump" edge. We have i >= bnd but we're really + // after i < bnd so we need to change the assertion edge to "next". return AssertionInfo::ForNextEdge(index); } return index; diff --git a/src/jit/compiler.h b/src/jit/compiler.h index 30c46eee30..377560a2a3 100644 --- a/src/jit/compiler.h +++ b/src/jit/compiler.h @@ -5493,11 +5493,11 @@ protected: typedef SimplerHashTable, GenTreePtr, JitSimplerHashBehavior> NodeToNodeMap; - NodeToNodeMap* optCseArrLenMap; // Maps array length nodes to ancestor compares that should be - // re-numbered with the array length to improve range check elimination + NodeToNodeMap* optCseCheckedBoundMap; // Maps bound nodes to ancestor compares that should be + // re-numbered with the bound to improve range check elimination - // Given a compare, look for a cse candidate arrlen feeding it and add a map entry if found. - void optCseUpdateArrLenMap(GenTreePtr compare); + // Given a compare, look for a cse candidate checked bound feeding it and add a map entry if found. + void optCseUpdateCheckedBoundMap(GenTreePtr compare); void optCSEstop(); @@ -5726,8 +5726,8 @@ public: O1K_INVALID, O1K_LCLVAR, O1K_ARR_BND, - O1K_ARRLEN_OPER_BND, - O1K_ARRLEN_LOOP_BND, + O1K_BOUND_OPER_BND, + O1K_BOUND_LOOP_BND, O1K_CONSTANT_LOOP_BND, O1K_EXACT_TYPE, O1K_SUBTYPE, @@ -5792,13 +5792,13 @@ public: }; } op2; - bool IsArrLenArithBound() + bool IsCheckedBoundArithBound() { - return ((assertionKind == OAK_EQUAL || assertionKind == OAK_NOT_EQUAL) && op1.kind == O1K_ARRLEN_OPER_BND); + return ((assertionKind == OAK_EQUAL || assertionKind == OAK_NOT_EQUAL) && op1.kind == O1K_BOUND_OPER_BND); } - bool IsArrLenBound() + bool IsCheckedBoundBound() { - return ((assertionKind == OAK_EQUAL || assertionKind == OAK_NOT_EQUAL) && op1.kind == O1K_ARRLEN_LOOP_BND); + return ((assertionKind == OAK_EQUAL || assertionKind == OAK_NOT_EQUAL) && op1.kind == O1K_BOUND_LOOP_BND); } bool IsConstantBound() { diff --git a/src/jit/optcse.cpp b/src/jit/optcse.cpp index 41aad403d9..c5ad916f83 100644 --- a/src/jit/optcse.cpp +++ b/src/jit/optcse.cpp @@ -507,8 +507,8 @@ void Compiler::optValnumCSE_Init() optCSECandidateCount = 0; optDoCSE = false; // Stays false until we find duplicate CSE tree - // optCseArrLenMap is unused in most functions, allocated only when used - optCseArrLenMap = nullptr; + // optCseCheckedBoundMap is unused in most functions, allocated only when used + optCseCheckedBoundMap = nullptr; } /***************************************************************************** @@ -705,10 +705,10 @@ unsigned Compiler::optValnumCSE_Locate() { if (tree->OperIsCompare() && stmtHasArrLenCandidate) { - // Check if this compare is a function of (one of) the arrary - // length candidate(s); we may want to update its value number + // Check if this compare is a function of (one of) the checked + // bound candidate(s); we may want to update its value number. // if the array length gets CSEd - optCseUpdateArrLenMap(tree); + optCseUpdateCheckedBoundMap(tree); } if (!optIsCSEcandidate(tree)) @@ -763,16 +763,16 @@ unsigned Compiler::optValnumCSE_Locate() } //------------------------------------------------------------------------ -// optCseUpdateArrLenMap: Check if this compare is a tractable function of -// an array length that is a CSE candidate, and insert -// an entry in the optCseArrLenMap if so. This facilitates +// optCseUpdateCheckedBoundMap: Check if this compare is a tractable function of +// a checked bound that is a CSE candidate, and insert +// an entry in the optCseCheckedBoundMap if so. This facilitates // subsequently updating the compare's value number if -// the array length gets CSEd. +// the bound gets CSEd. // // Arguments: // compare - The compare node to check -void Compiler::optCseUpdateArrLenMap(GenTreePtr compare) +void Compiler::optCseUpdateCheckedBoundMap(GenTreePtr compare) { assert(compare->OperIsCompare()); @@ -787,73 +787,72 @@ void Compiler::optCseUpdateArrLenMap(GenTreePtr compare) return; } - // Now look for an array length feeding the compare - ValueNumStore::ArrLenArithBoundInfo info; - GenTreePtr arrLenParent = nullptr; + // Now look for a checked bound feeding the compare + ValueNumStore::CompareCheckedBoundArithInfo info; - if (vnStore->IsVNArrLenBound(compareVN)) + GenTreePtr boundParent = nullptr; + + if (vnStore->IsVNCompareCheckedBound(compareVN)) { - // Simple compare of an array legnth against something else. + // Simple compare of an bound against something else. - vnStore->GetArrLenBoundInfo(compareVN, &info); - arrLenParent = compare; + vnStore->GetCompareCheckedBound(compareVN, &info); + boundParent = compare; } - else if (vnStore->IsVNArrLenArithBound(compareVN)) + else if (vnStore->IsVNCompareCheckedBoundArith(compareVN)) { - // Compare of an array length +/- some offset to something else. + // Compare of a bound +/- some offset to something else. GenTreePtr op1 = compare->gtGetOp1(); GenTreePtr op2 = compare->gtGetOp2(); - vnStore->GetArrLenArithBoundInfo(compareVN, &info); + vnStore->GetCompareCheckedBoundArithInfo(compareVN, &info); if (GetVNFuncForOper(op1->OperGet(), op1->IsUnsigned()) == (VNFunc)info.arrOper) { - // The arithmetic node is the array length's parent. - arrLenParent = op1; + // The arithmetic node is the bound's parent. + boundParent = op1; } else if (GetVNFuncForOper(op2->OperGet(), op2->IsUnsigned()) == (VNFunc)info.arrOper) { - // The arithmetic node is the array length's parent. - arrLenParent = op2; + // The arithmetic node is the bound's parent. + boundParent = op2; } } - if (arrLenParent != nullptr) + if (boundParent != nullptr) { - GenTreePtr arrLen = nullptr; + GenTreePtr bound = nullptr; - // Find which child of arrLenParent is the array length. Abort if its - // conservative value number doesn't match the one from the compare VN. + // Find which child of boundParent is the bound. Abort if neither + // conservative value number matches the one from the compare VN. - GenTreePtr child1 = arrLenParent->gtGetOp1(); - if ((child1->OperGet() == GT_ARR_LENGTH) && IS_CSE_INDEX(child1->gtCSEnum) && - (info.vnArray == child1->AsArrLen()->ArrRef()->gtVNPair.GetConservative())) + GenTreePtr child1 = boundParent->gtGetOp1(); + if ((info.vnBound == child1->gtVNPair.GetConservative()) && IS_CSE_INDEX(child1->gtCSEnum)) { - arrLen = child1; + bound = child1; } else { - GenTreePtr child2 = arrLenParent->gtGetOp2(); - if ((child2->OperGet() == GT_ARR_LENGTH) && IS_CSE_INDEX(child2->gtCSEnum) && - (info.vnArray == child2->AsArrLen()->ArrRef()->gtVNPair.GetConservative())) + GenTreePtr child2 = boundParent->gtGetOp2(); + if ((info.vnBound == child2->gtVNPair.GetConservative()) && IS_CSE_INDEX(child2->gtCSEnum)) { - arrLen = child2; + bound = child2; } } - if (arrLen != nullptr) + if (bound != nullptr) { - // Found an arrayLen feeding a compare that is a tracatable function of it; - // record this in the map so we can update the compare VN if the array length + // Found a checked bound feeding a compare that is a tractable function of it; + // record this in the map so we can update the compare VN if the bound // node gets CSEd. - if (optCseArrLenMap == nullptr) + if (optCseCheckedBoundMap == nullptr) { // Allocate map on first use. - optCseArrLenMap = new (getAllocator()) NodeToNodeMap(getAllocator()); + optCseCheckedBoundMap = new (getAllocator()) NodeToNodeMap(getAllocator()); } - optCseArrLenMap->Set(arrLen, compare); + optCseCheckedBoundMap->Set(bound, compare); } } } @@ -2023,31 +2022,40 @@ public: // conservative VN to this use. This can help range check elimination later on. cse->gtVNPair.SetConservative(defConservativeVN); + // If the old VN was flagged as a checked bound, propagate that to the new VN + // to make sure assertion prop will pay attention to this VN. + ValueNumStore* vnStore = m_pCompiler->vnStore; + ValueNum oldVN = exp->gtVNPair.GetConservative(); + if (!vnStore->IsVNConstant(defConservativeVN) && vnStore->IsVNCheckedBound(oldVN)) + { + vnStore->SetVNIsCheckedBound(defConservativeVN); + } + GenTreePtr cmp; - if ((exp->OperGet() == GT_ARR_LENGTH) && (m_pCompiler->optCseArrLenMap != nullptr) && - (m_pCompiler->optCseArrLenMap->Lookup(exp, &cmp))) + if ((m_pCompiler->optCseCheckedBoundMap != nullptr) && + (m_pCompiler->optCseCheckedBoundMap->Lookup(exp, &cmp))) { // Propagate the new value number to this compare node as well, since // subsequent range check elimination will try to correlate it with // the other appearances that are getting CSEd. - ValueNumStore* vnStore = m_pCompiler->vnStore; - ValueNum oldCmpVN = cmp->gtVNPair.GetConservative(); - ValueNumStore::ArrLenArithBoundInfo info; - ValueNum newCmpArgVN; - if (vnStore->IsVNArrLenBound(oldCmpVN)) + ValueNum oldCmpVN = cmp->gtVNPair.GetConservative(); + ValueNum newCmpArgVN; + + ValueNumStore::CompareCheckedBoundArithInfo info; + if (vnStore->IsVNCompareCheckedBound(oldCmpVN)) { - // Comparison is against the array length directly. + // Comparison is against the bound directly. newCmpArgVN = defConservativeVN; - vnStore->GetArrLenBoundInfo(oldCmpVN, &info); + vnStore->GetCompareCheckedBound(oldCmpVN, &info); } else { - // Comparison is against the array length +/- some offset. + // Comparison is against the bound +/- some offset. - assert(vnStore->IsVNArrLenArithBound(oldCmpVN)); - vnStore->GetArrLenArithBoundInfo(oldCmpVN, &info); + assert(vnStore->IsVNCompareCheckedBoundArith(oldCmpVN)); + vnStore->GetCompareCheckedBoundArithInfo(oldCmpVN, &info); newCmpArgVN = vnStore->VNForFunc(vnStore->TypeOfVN(info.arrOp), (VNFunc)info.arrOper, info.arrOp, defConservativeVN); } diff --git a/src/jit/rangecheck.cpp b/src/jit/rangecheck.cpp index 91ae81e322..f6c14ff017 100644 --- a/src/jit/rangecheck.cpp +++ b/src/jit/rangecheck.cpp @@ -68,6 +68,8 @@ bool RangeCheck::BetweenBounds(Range& range, int lower, GenTreePtr upper) } #endif // DEBUG + ValueNumStore* vnStore = m_pCompiler->vnStore; + // Get the VN for the upper limit. ValueNum uLimitVN = upper->gtVNPair.GetConservative(); @@ -75,15 +77,14 @@ bool RangeCheck::BetweenBounds(Range& range, int lower, GenTreePtr upper) JITDUMP("VN%04X upper bound is: ", uLimitVN); if (m_pCompiler->verbose) { - m_pCompiler->vnStore->vnDump(m_pCompiler, uLimitVN); + vnStore->vnDump(m_pCompiler, uLimitVN); } JITDUMP("\n"); #endif - ValueNum arrRefVN = ValueNumStore::NoVN; - int arrSize = 0; + int arrSize = 0; - if (m_pCompiler->vnStore->IsVNConstant(uLimitVN)) + if (vnStore->IsVNConstant(uLimitVN)) { ssize_t constVal = -1; unsigned iconFlags = 0; @@ -93,47 +94,38 @@ bool RangeCheck::BetweenBounds(Range& range, int lower, GenTreePtr upper) arrSize = (int)constVal; } } - else if (m_pCompiler->vnStore->IsVNArrLen(uLimitVN)) + else if (vnStore->IsVNArrLen(uLimitVN)) { // Get the array reference from the length. - arrRefVN = m_pCompiler->vnStore->GetArrForLenVn(uLimitVN); + ValueNum arrRefVN = vnStore->GetArrForLenVn(uLimitVN); // Check if array size can be obtained. - arrSize = m_pCompiler->vnStore->GetNewArrSize(arrRefVN); + arrSize = vnStore->GetNewArrSize(arrRefVN); } - else + else if (!vnStore->IsVNCheckedBound(uLimitVN)) { // If the upper limit is not length, then bail. return false; } -#ifdef DEBUG - JITDUMP("Array ref VN"); - if (m_pCompiler->verbose) - { - m_pCompiler->vnStore->vnDump(m_pCompiler, arrRefVN); - } - JITDUMP("\n"); -#endif - JITDUMP("Array size is: %d\n", arrSize); - // Upper limit: a.len + ucns (upper limit constant). + // Upper limit: len + ucns (upper limit constant). if (range.UpperLimit().IsBinOpArray()) { - if (range.UpperLimit().vn != arrRefVN) + if (range.UpperLimit().vn != uLimitVN) { return false; } int ucns = range.UpperLimit().GetConstant(); - // Upper limit: a.Len + [0..n] + // Upper limit: Len + [0..n] if (ucns >= 0) { return false; } - // If lower limit is a.len return false. + // If lower limit is len return false. if (range.LowerLimit().IsArray()) { return false; @@ -152,8 +144,8 @@ bool RangeCheck::BetweenBounds(Range& range, int lower, GenTreePtr upper) } // At this point, - // upper limit = a.len + ucns. ucns < 0 - // lower limit = a.len + lcns. + // upper limit = len + ucns. ucns < 0 + // lower limit = len + lcns. if (range.LowerLimit().IsBinOpArray()) { int lcns = range.LowerLimit().GetConstant(); @@ -161,7 +153,7 @@ bool RangeCheck::BetweenBounds(Range& range, int lower, GenTreePtr upper) { return false; } - return (range.LowerLimit().vn == arrRefVN && lcns <= ucns); + return (range.LowerLimit().vn == uLimitVN && lcns <= ucns); } } // If upper limit is constant @@ -185,13 +177,13 @@ bool RangeCheck::BetweenBounds(Range& range, int lower, GenTreePtr upper) if (range.LowerLimit().IsBinOpArray()) { int lcns = range.LowerLimit().GetConstant(); - // a.len + lcns, make sure we don't subtract too much from a.len. + // len + lcns, make sure we don't subtract too much from len. if (lcns >= 0 || -lcns > arrSize) { return false; } // Make sure a.len + lcns <= ucns. - return (range.LowerLimit().vn == arrRefVN && (arrSize + lcns) <= ucns); + return (range.LowerLimit().vn == uLimitVN && (arrSize + lcns) <= ucns); } } @@ -508,8 +500,9 @@ void RangeCheck::MergeEdgeAssertions(GenTreePtr tree, const ASSERT_VALARG_TP ass Compiler::AssertionDsc* curAssertion = m_pCompiler->optGetAssertion((AssertionIndex)index); - // Current assertion is about array length. - if (!curAssertion->IsArrLenArithBound() && !curAssertion->IsArrLenBound() && !curAssertion->IsConstantBound()) + // Current assertion is about compare against constant or checked bound. + if (!curAssertion->IsCheckedBoundArithBound() && !curAssertion->IsCheckedBoundBound() && + !curAssertion->IsConstantBound()) { continue; } @@ -521,20 +514,20 @@ void RangeCheck::MergeEdgeAssertions(GenTreePtr tree, const ASSERT_VALARG_TP ass } #endif - assert(m_pCompiler->vnStore->IsVNArrLenArithBound(curAssertion->op1.vn) || - m_pCompiler->vnStore->IsVNArrLenBound(curAssertion->op1.vn) || + assert(m_pCompiler->vnStore->IsVNCompareCheckedBoundArith(curAssertion->op1.vn) || + m_pCompiler->vnStore->IsVNCompareCheckedBound(curAssertion->op1.vn) || m_pCompiler->vnStore->IsVNConstantBound(curAssertion->op1.vn)); Limit limit(Limit::keUndef); genTreeOps cmpOper = GT_NONE; - // Current assertion is of the form (i < a.len - cns) != 0 - if (curAssertion->IsArrLenArithBound()) + // Current assertion is of the form (i < len - cns) != 0 + if (curAssertion->IsCheckedBoundArithBound()) { - ValueNumStore::ArrLenArithBoundInfo info; + ValueNumStore::CompareCheckedBoundArithInfo info; - // Get i, a.len, cns and < as "info." - m_pCompiler->vnStore->GetArrLenArithBoundInfo(curAssertion->op1.vn, &info); + // Get i, len, cns and < as "info." + m_pCompiler->vnStore->GetCompareCheckedBoundArithInfo(curAssertion->op1.vn, &info); if (m_pCompiler->lvaTable[lcl->gtLclNum].GetPerSsaData(lcl->gtSsaNum)->m_vnPair.GetConservative() != info.cmpOp) @@ -547,26 +540,26 @@ void RangeCheck::MergeEdgeAssertions(GenTreePtr tree, const ASSERT_VALARG_TP ass case GT_SUB: case GT_ADD: { - // If the operand that operates on the array is not constant, then done. + // If the operand that operates on the bound is not constant, then done. if (!m_pCompiler->vnStore->IsVNConstant(info.arrOp) || m_pCompiler->vnStore->TypeOfVN(info.arrOp) != TYP_INT) { break; } int cons = m_pCompiler->vnStore->ConstantValue(info.arrOp); - limit = Limit(Limit::keBinOpArray, info.vnArray, info.arrOper == GT_SUB ? -cons : cons); + limit = Limit(Limit::keBinOpArray, info.vnBound, info.arrOper == GT_SUB ? -cons : cons); } } cmpOper = (genTreeOps)info.cmpOper; } - // Current assertion is of the form (i < a.len) != 0 - else if (curAssertion->IsArrLenBound()) + // Current assertion is of the form (i < len) != 0 + else if (curAssertion->IsCheckedBoundBound()) { - ValueNumStore::ArrLenArithBoundInfo info; + ValueNumStore::CompareCheckedBoundArithInfo info; - // Get the info as "i", "<" and "a.len" - m_pCompiler->vnStore->GetArrLenBoundInfo(curAssertion->op1.vn, &info); + // Get the info as "i", "<" and "len" + m_pCompiler->vnStore->GetCompareCheckedBound(curAssertion->op1.vn, &info); ValueNum lclVn = m_pCompiler->lvaTable[lcl->gtLclNum].GetPerSsaData(lcl->gtSsaNum)->m_vnPair.GetConservative(); @@ -576,7 +569,7 @@ void RangeCheck::MergeEdgeAssertions(GenTreePtr tree, const ASSERT_VALARG_TP ass continue; } limit.type = Limit::keArray; - limit.vn = info.vnArray; + limit.vn = info.vnBound; cmpOper = (genTreeOps)info.cmpOper; } // Current assertion is of the form (i < 100) != 0 @@ -624,30 +617,31 @@ void RangeCheck::MergeEdgeAssertions(GenTreePtr tree, const ASSERT_VALARG_TP ass noway_assert(limit.IsBinOpArray() || limit.IsArray() || limit.IsConstant()); ValueNum arrLenVN = m_pCurBndsChk->gtArrLen->gtVNPair.GetConservative(); - ValueNum arrRefVN = ValueNumStore::NoVN; - if (m_pCompiler->vnStore->IsVNArrLen(arrLenVN)) + if (m_pCompiler->vnStore->IsVNConstant(arrLenVN)) { - // Get the array reference from the length. - arrRefVN = m_pCompiler->vnStore->GetArrForLenVn(arrLenVN); + // Set arrLenVN to NoVN; this will make it match the "vn" recorded on + // constant limits (where we explicitly track the constant and don't + // redundantly store its VN in the "vn" field). + arrLenVN = ValueNumStore::NoVN; } // During assertion prop we add assertions of the form: // - // (i < a.Length) == 0 - // (i < a.Length) != 0 + // (i < length) == 0 + // (i < length) != 0 // (i < 100) == 0 // (i < 100) != 0 // - // At this point, we have detected that op1.vn is (i < a.Length) or (i < a.Length + cns) or + // At this point, we have detected that op1.vn is (i < length) or (i < length + cns) or // (i < 100) and the op2.vn is 0. // // Now, let us check if we are == 0 (i.e., op1 assertion is false) or != 0 (op1 assertion // is true.), // // If we have an assertion of the form == 0 (i.e., equals false), then reverse relop. - // The relop has to be reversed because we have: (i < a.Length) is false which is the same - // as (i >= a.Length). + // The relop has to be reversed because we have: (i < length) is false which is the same + // as (i >= length). if (curAssertion->assertionKind == Compiler::OAK_EQUAL) { cmpOper = GenTree::ReverseRelop(cmpOper); @@ -665,26 +659,26 @@ void RangeCheck::MergeEdgeAssertions(GenTreePtr tree, const ASSERT_VALARG_TP ass } // Doesn't tighten the current bound. So skip. - if (pRange->uLimit.IsConstant() && limit.vn != arrRefVN) + if (pRange->uLimit.IsConstant() && limit.vn != arrLenVN) { continue; } // Check if the incoming limit from assertions tightens the existing upper limit. - if ((pRange->uLimit.IsArray() || pRange->uLimit.IsBinOpArray()) && pRange->uLimit.vn == arrRefVN) + if ((pRange->uLimit.IsArray() || pRange->uLimit.IsBinOpArray()) && pRange->uLimit.vn == arrLenVN) { // We have checked the current range's (pRange's) upper limit is either of the form: - // a.Length - // a.Length + cns - // and a == the bndsChkCandidate's arrRef + // length + // length + cns + // and length == the bndsChkCandidate's arrLen // - // We want to check if the incoming limit tightens the bound, and for that the - // we need to make sure that incoming limit is also on a.Length or a.Length + cns - // and not b.Length or some c.Length. + // We want to check if the incoming limit tightens the bound, and for that + // we need to make sure that incoming limit is also on the same length (or + // length + cns) and not some other length. - if (limit.vn != arrRefVN) + if (limit.vn != arrLenVN) { - JITDUMP("Array ref did not match cur=$%x, assert=$%x\n", arrRefVN, limit.vn); + JITDUMP("Array length VN did not match cur=$%x, assert=$%x\n", arrLenVN, limit.vn); continue; } @@ -700,14 +694,14 @@ void RangeCheck::MergeEdgeAssertions(GenTreePtr tree, const ASSERT_VALARG_TP ass } else { - // Current range's upper bound is not "a.Length or a.Length + cns" and the - // incoming limit is not on the same arrRef as the bounds check candidate. + // Current range's upper bound is not "length or length + cns" and the + // incoming limit is not on the same length as the bounds check candidate. // So we could skip this assertion. But in cases, of Dependent or Unknown // type of upper limit, the incoming assertion still tightens the upper // bound to a saner value. So do not skip the assertion. } - // cmpOp (loop index i) cmpOper a.len +/- cns + // cmpOp (loop index i) cmpOper len +/- cns switch (cmpOper) { case GT_LT: diff --git a/src/jit/valuenum.cpp b/src/jit/valuenum.cpp index 5b40122f1e..7273fd91ac 100644 --- a/src/jit/valuenum.cpp +++ b/src/jit/valuenum.cpp @@ -64,6 +64,7 @@ ValueNumStore::ValueNumStore(Compiler* comp, IAllocator* alloc) #endif m_nextChunkBase(0) , m_fixedPointMapSels(alloc, 8) + , m_checkedBoundVNs(comp) , m_chunks(alloc, 8) , m_intCnsMap(nullptr) , m_longCnsMap(nullptr) @@ -3211,18 +3212,18 @@ void ValueNumStore::GetConstantBoundInfo(ValueNum vn, ConstantBoundInfo* info) //------------------------------------------------------------------------ // IsVNArrLenUnsignedBound: Checks if the specified vn represents an expression -// such as "(uint)i < (uint)a.len" that implies that the array index is valid +// such as "(uint)i < (uint)len" that implies that the index is valid // (0 <= i && i < a.len). // // Arguments: // vn - Value number to query -// info - Pointer to an ArrLenUnsignedBoundInfo object to return information about -// the expression. Not populated if the vn expression isn't suitable (e.g. i <= a.len). +// info - Pointer to an UnsignedCompareCheckedBoundInfo object to return information about +// the expression. Not populated if the vn expression isn't suitable (e.g. i <= len). // This enables optCreateJTrueBoundAssertion to immediatly create an OAK_NO_THROW // assertion instead of the OAK_EQUAL/NOT_EQUAL assertions created by signed compares -// (IsVNArrLenBound, IsVNArrLenArithBound) that require further processing. +// (IsVNCompareCheckedBound, IsVNCompareCheckedBoundArith) that require further processing. -bool ValueNumStore::IsVNArrLenUnsignedBound(ValueNum vn, ArrLenUnsignedBoundInfo* info) +bool ValueNumStore::IsVNUnsignedCompareCheckedBound(ValueNum vn, UnsignedCompareCheckedBoundInfo* info) { VNFuncApp funcApp; @@ -3230,24 +3231,24 @@ bool ValueNumStore::IsVNArrLenUnsignedBound(ValueNum vn, ArrLenUnsignedBoundInfo { if ((funcApp.m_func == VNF_LT_UN) || (funcApp.m_func == VNF_GE_UN)) { - // We only care about "(uint)i < (uint)a.len" and its negation "(uint)i >= (uint)a.len" - if (IsVNArrLen(funcApp.m_args[1])) + // We only care about "(uint)i < (uint)len" and its negation "(uint)i >= (uint)len" + if (IsVNCheckedBound(funcApp.m_args[1])) { info->vnIdx = funcApp.m_args[0]; info->cmpOper = funcApp.m_func; - info->vnLen = funcApp.m_args[1]; + info->vnBound = funcApp.m_args[1]; return true; } } else if ((funcApp.m_func == VNF_GT_UN) || (funcApp.m_func == VNF_LE_UN)) { // We only care about "(uint)a.len > (uint)i" and its negation "(uint)a.len <= (uint)i" - if (IsVNArrLen(funcApp.m_args[0])) + if (IsVNCheckedBound(funcApp.m_args[0])) { info->vnIdx = funcApp.m_args[1]; - // Let's keep a consistent operand order - it's always i < a.len, never a.len > i + // Let's keep a consistent operand order - it's always i < len, never len > i info->cmpOper = (funcApp.m_func == VNF_GT_UN) ? VNF_LT_UN : VNF_GE_UN; - info->vnLen = funcApp.m_args[0]; + info->vnBound = funcApp.m_args[0]; return true; } } @@ -3256,9 +3257,9 @@ bool ValueNumStore::IsVNArrLenUnsignedBound(ValueNum vn, ArrLenUnsignedBoundInfo return false; } -bool ValueNumStore::IsVNArrLenBound(ValueNum vn) +bool ValueNumStore::IsVNCompareCheckedBound(ValueNum vn) { - // Do we have "var < a.len"? + // Do we have "var < len"? if (vn == NoVN) { return false; @@ -3274,7 +3275,7 @@ bool ValueNumStore::IsVNArrLenBound(ValueNum vn) { return false; } - if (!IsVNArrLen(funcAttr.m_args[0]) && !IsVNArrLen(funcAttr.m_args[1])) + if (!IsVNCheckedBound(funcAttr.m_args[0]) && !IsVNCheckedBound(funcAttr.m_args[1])) { return false; } @@ -3282,30 +3283,30 @@ bool ValueNumStore::IsVNArrLenBound(ValueNum vn) return true; } -void ValueNumStore::GetArrLenBoundInfo(ValueNum vn, ArrLenArithBoundInfo* info) +void ValueNumStore::GetCompareCheckedBound(ValueNum vn, CompareCheckedBoundArithInfo* info) { - assert(IsVNArrLenBound(vn)); + assert(IsVNCompareCheckedBound(vn)); // Do we have var < a.len? VNFuncApp funcAttr; GetVNFunc(vn, &funcAttr); - bool isOp1ArrLen = IsVNArrLen(funcAttr.m_args[1]); - if (isOp1ArrLen) + bool isOp1CheckedBound = IsVNCheckedBound(funcAttr.m_args[1]); + if (isOp1CheckedBound) { info->cmpOper = funcAttr.m_func; info->cmpOp = funcAttr.m_args[0]; - info->vnArray = GetArrForLenVn(funcAttr.m_args[1]); + info->vnBound = funcAttr.m_args[1]; } else { info->cmpOper = GenTree::SwapRelop((genTreeOps)funcAttr.m_func); info->cmpOp = funcAttr.m_args[1]; - info->vnArray = GetArrForLenVn(funcAttr.m_args[0]); + info->vnBound = funcAttr.m_args[0]; } } -bool ValueNumStore::IsVNArrLenArith(ValueNum vn) +bool ValueNumStore::IsVNCheckedBoundArith(ValueNum vn) { // Do we have "a.len +or- var" if (vn == NoVN) @@ -3315,34 +3316,34 @@ bool ValueNumStore::IsVNArrLenArith(ValueNum vn) VNFuncApp funcAttr; - return GetVNFunc(vn, &funcAttr) && // vn is a func. - (funcAttr.m_func == (VNFunc)GT_ADD || funcAttr.m_func == (VNFunc)GT_SUB) && // the func is +/- - (IsVNArrLen(funcAttr.m_args[0]) || IsVNArrLen(funcAttr.m_args[1])); // either op1 or op2 is a.len + return GetVNFunc(vn, &funcAttr) && // vn is a func. + (funcAttr.m_func == (VNFunc)GT_ADD || funcAttr.m_func == (VNFunc)GT_SUB) && // the func is +/- + (IsVNCheckedBound(funcAttr.m_args[0]) || IsVNCheckedBound(funcAttr.m_args[1])); // either op1 or op2 is a.len } -void ValueNumStore::GetArrLenArithInfo(ValueNum vn, ArrLenArithBoundInfo* info) +void ValueNumStore::GetCheckedBoundArithInfo(ValueNum vn, CompareCheckedBoundArithInfo* info) { // Do we have a.len +/- var? - assert(IsVNArrLenArith(vn)); + assert(IsVNCheckedBoundArith(vn)); VNFuncApp funcArith; GetVNFunc(vn, &funcArith); - bool isOp1ArrLen = IsVNArrLen(funcArith.m_args[1]); - if (isOp1ArrLen) + bool isOp1CheckedBound = IsVNCheckedBound(funcArith.m_args[1]); + if (isOp1CheckedBound) { info->arrOper = funcArith.m_func; info->arrOp = funcArith.m_args[0]; - info->vnArray = GetArrForLenVn(funcArith.m_args[1]); + info->vnBound = funcArith.m_args[1]; } else { info->arrOper = funcArith.m_func; info->arrOp = funcArith.m_args[1]; - info->vnArray = GetArrForLenVn(funcArith.m_args[0]); + info->vnBound = funcArith.m_args[0]; } } -bool ValueNumStore::IsVNArrLenArithBound(ValueNum vn) +bool ValueNumStore::IsVNCompareCheckedBoundArith(ValueNum vn) { // Do we have: "var < a.len - var" if (vn == NoVN) @@ -3364,7 +3365,7 @@ bool ValueNumStore::IsVNArrLenArithBound(ValueNum vn) } // Either the op0 or op1 is arr len arithmetic. - if (!IsVNArrLenArith(funcAttr.m_args[0]) && !IsVNArrLenArith(funcAttr.m_args[1])) + if (!IsVNCheckedBoundArith(funcAttr.m_args[0]) && !IsVNCheckedBoundArith(funcAttr.m_args[1])) { return false; } @@ -3372,26 +3373,26 @@ bool ValueNumStore::IsVNArrLenArithBound(ValueNum vn) return true; } -void ValueNumStore::GetArrLenArithBoundInfo(ValueNum vn, ArrLenArithBoundInfo* info) +void ValueNumStore::GetCompareCheckedBoundArithInfo(ValueNum vn, CompareCheckedBoundArithInfo* info) { - assert(IsVNArrLenArithBound(vn)); + assert(IsVNCompareCheckedBoundArith(vn)); VNFuncApp funcAttr; GetVNFunc(vn, &funcAttr); - // Check whether op0 or op1 ia arr len arithmetic. - bool isOp1ArrLenArith = IsVNArrLenArith(funcAttr.m_args[1]); - if (isOp1ArrLenArith) + // Check whether op0 or op1 is checked bound arithmetic. + bool isOp1CheckedBoundArith = IsVNCheckedBoundArith(funcAttr.m_args[1]); + if (isOp1CheckedBoundArith) { info->cmpOper = funcAttr.m_func; info->cmpOp = funcAttr.m_args[0]; - GetArrLenArithInfo(funcAttr.m_args[1], info); + GetCheckedBoundArithInfo(funcAttr.m_args[1], info); } else { info->cmpOper = GenTree::SwapRelop((genTreeOps)funcAttr.m_func); info->cmpOp = funcAttr.m_args[1]; - GetArrLenArithInfo(funcAttr.m_args[0], info); + GetCheckedBoundArithInfo(funcAttr.m_args[0], info); } } @@ -3448,6 +3449,39 @@ bool ValueNumStore::IsVNArrLen(ValueNum vn) return (GetVNFunc(vn, &funcAttr) && funcAttr.m_func == (VNFunc)GT_ARR_LENGTH); } +bool ValueNumStore::IsVNCheckedBound(ValueNum vn) +{ + bool dummy; + if (m_checkedBoundVNs.TryGetValue(vn, &dummy)) + { + // This VN appeared as the conservative VN of the length argument of some + // GT_ARR_BOUND node. + return true; + } + if (IsVNArrLen(vn)) + { + // Even if we haven't seen this VN in a bounds check, if it is an array length + // VN then consider it a checked bound VN. This facilitates better bounds check + // removal by ensuring that compares against array lengths get put in the + // optCseCheckedBoundMap; such an array length might get CSEd with one that was + // directly used in a bounds check, and having the map entry will let us update + // the compare's VN so that OptimizeRangeChecks can recognize such compares. + return true; + } + + return false; +} + +void ValueNumStore::SetVNIsCheckedBound(ValueNum vn) +{ + // This is meant to flag VNs for lengths that aren't known at compile time, so we can + // form and propagate assertions about them. Ensure that callers filter out constant + // VNs since they're not what we're looking to flag, and assertion prop can reason + // directly about constants. + assert(!IsVNConstant(vn)); + m_checkedBoundVNs.AddOrUpdate(vn, true); +} + ValueNum ValueNumStore::EvalMathFuncUnary(var_types typ, CorInfoIntrinsics gtMathFN, ValueNum arg0VN) { assert(arg0VN == VNNormVal(arg0VN)); @@ -3902,16 +3936,16 @@ void ValueNumStore::vnDump(Compiler* comp, ValueNum vn, bool isPtr) unreached(); } } - else if (IsVNArrLenBound(vn)) + else if (IsVNCompareCheckedBound(vn)) { - ArrLenArithBoundInfo info; - GetArrLenBoundInfo(vn, &info); + CompareCheckedBoundArithInfo info; + GetCompareCheckedBound(vn, &info); info.dump(this); } - else if (IsVNArrLenArithBound(vn)) + else if (IsVNCompareCheckedBoundArith(vn)) { - ArrLenArithBoundInfo info; - GetArrLenArithBoundInfo(vn, &info); + CompareCheckedBoundArithInfo info; + GetCompareCheckedBoundArithInfo(vn, &info); info.dump(this); } else if (IsVNFunc(vn)) @@ -7028,6 +7062,14 @@ void Compiler::fgValueNumberTree(GenTreePtr tree, bool evalAsgLhsInd) excSet = vnStore->VNPExcSetUnion(excSet, vnStore->VNPExcVal(tree->AsBoundsChk()->gtArrLen->gtVNPair)); tree->gtVNPair = vnStore->VNPWithExc(vnStore->VNPForVoid(), excSet); + + // Record non-constant value numbers that are used as the length argument to bounds checks, so that + // assertion prop will know that comparisons against them are worth analyzing. + ValueNum lengthVN = tree->AsBoundsChk()->gtArrLen->gtVNPair.GetConservative(); + if ((lengthVN != ValueNumStore::NoVN) && !vnStore->IsVNConstant(lengthVN)) + { + vnStore->SetVNIsCheckedBound(lengthVN); + } } break; diff --git a/src/jit/valuenum.h b/src/jit/valuenum.h index 2be48491df..fcf6d8699a 100644 --- a/src/jit/valuenum.h +++ b/src/jit/valuenum.h @@ -30,6 +30,8 @@ #include "gentree.h" // Defines the type ValueNum. #include "valuenumtype.h" +// Defines the type SmallHashTable. +#include "smallhash.h" // A "ValueNumStore" represents the "universe" of value numbers used in a single // compilation. @@ -537,27 +539,39 @@ public: // Returns true iff the VN represents an integeral constant. bool IsVNInt32Constant(ValueNum vn); - struct ArrLenUnsignedBoundInfo + typedef SmallHashTable CheckedBoundVNSet; + + // Returns true if the VN is known or likely to appear as the conservative value number + // of the length argument to a GT_ARR_BOUNDS_CHECK node. + bool IsVNCheckedBound(ValueNum vn); + + // Record that a VN is known to appear as the conservative value number of the length + // argument to a GT_ARR_BOUNDS_CHECK node. + void SetVNIsCheckedBound(ValueNum vn); + + // Information about the individual components of a value number representing an unsigned + // comparison of some value against a checked bound VN. + struct UnsignedCompareCheckedBoundInfo { unsigned cmpOper; ValueNum vnIdx; - ValueNum vnLen; + ValueNum vnBound; - ArrLenUnsignedBoundInfo() : cmpOper(GT_NONE), vnIdx(NoVN), vnLen(NoVN) + UnsignedCompareCheckedBoundInfo() : cmpOper(GT_NONE), vnIdx(NoVN), vnBound(NoVN) { } }; - struct ArrLenArithBoundInfo + struct CompareCheckedBoundArithInfo { - // (vnArr.len - 1) > vnOp - // (vnArr.len arrOper arrOp) cmpOper cmpOp - ValueNum vnArray; + // (vnBound - 1) > vnOp + // (vnBound arrOper arrOp) cmpOper cmpOp + ValueNum vnBound; unsigned arrOper; ValueNum arrOp; unsigned cmpOper; ValueNum cmpOp; - ArrLenArithBoundInfo() : vnArray(NoVN), arrOper(GT_NONE), arrOp(NoVN), cmpOper(GT_NONE), cmpOp(NoVN) + CompareCheckedBoundArithInfo() : vnBound(NoVN), arrOper(GT_NONE), arrOp(NoVN), cmpOper(GT_NONE), cmpOp(NoVN) { } #ifdef DEBUG @@ -567,7 +581,7 @@ public: printf(" "); printf(vnStore->VNFuncName((VNFunc)cmpOper)); printf(" "); - vnStore->vnDump(vnStore->m_pComp, vnArray); + vnStore->vnDump(vnStore->m_pComp, vnBound); if (arrOper != GT_NONE) { printf(vnStore->VNFuncName((VNFunc)arrOper)); @@ -618,26 +632,26 @@ public: // If "vn" is constant bound, then populate the "info" fields for constVal, cmpOp, cmpOper. void GetConstantBoundInfo(ValueNum vn, ConstantBoundInfo* info); - // If "vn" is of the form "(uint)var < (uint)a.len" (or equivalent) return true. - bool IsVNArrLenUnsignedBound(ValueNum vn, ArrLenUnsignedBoundInfo* info); + // If "vn" is of the form "(uint)var < (uint)len" (or equivalent) return true. + bool IsVNUnsignedCompareCheckedBound(ValueNum vn, UnsignedCompareCheckedBoundInfo* info); - // If "vn" is of the form "var < a.len" or "a.len <= var" return true. - bool IsVNArrLenBound(ValueNum vn); + // If "vn" is of the form "var < len" or "len <= var" return true. + bool IsVNCompareCheckedBound(ValueNum vn); - // If "vn" is arr len bound, then populate the "info" fields for the arrVn, cmpOp, cmpOper. - void GetArrLenBoundInfo(ValueNum vn, ArrLenArithBoundInfo* info); + // If "vn" is checked bound, then populate the "info" fields for the boundVn, cmpOp, cmpOper. + void GetCompareCheckedBound(ValueNum vn, CompareCheckedBoundArithInfo* info); - // If "vn" is of the form "a.len +/- var" return true. - bool IsVNArrLenArith(ValueNum vn); + // If "vn" is of the form "len +/- var" return true. + bool IsVNCheckedBoundArith(ValueNum vn); - // If "vn" is arr len arith, then populate the "info" fields for arrOper, arrVn, arrOp. - void GetArrLenArithInfo(ValueNum vn, ArrLenArithBoundInfo* info); + // If "vn" is checked bound arith, then populate the "info" fields for arrOper, arrVn, arrOp. + void GetCheckedBoundArithInfo(ValueNum vn, CompareCheckedBoundArithInfo* info); - // If "vn" is of the form "var < a.len +/- k" return true. - bool IsVNArrLenArithBound(ValueNum vn); + // If "vn" is of the form "var < len +/- k" return true. + bool IsVNCompareCheckedBoundArith(ValueNum vn); - // If "vn" is arr len arith bound, then populate the "info" fields for cmpOp, cmpOper. - void GetArrLenArithBoundInfo(ValueNum vn, ArrLenArithBoundInfo* info); + // If "vn" is checked bound arith, then populate the "info" fields for cmpOp, cmpOper. + void GetCompareCheckedBoundArithInfo(ValueNum vn, CompareCheckedBoundArithInfo* info); // Returns the flags on the current handle. GTF_ICON_SCOPE_HDL for example. unsigned GetHandleFlags(ValueNum vn); @@ -1040,6 +1054,9 @@ private: // Returns true if "sel(map, ind)" is a member of "m_fixedPointMapSels". bool SelectIsBeingEvaluatedRecursively(ValueNum map, ValueNum ind); + // This is the set of value numbers that have been flagged as arguments to bounds checks, in the length position. + CheckedBoundVNSet m_checkedBoundVNs; + // This is a map from "chunk number" to the attributes of the chunk. ExpandArrayStack m_chunks; -- cgit v1.2.3