From 18968352a63cf668a7e0592e2be8cdf6c70c995a Mon Sep 17 00:00:00 2001 From: Mike Danes Date: Thu, 23 Feb 2017 08:45:02 +0200 Subject: [PATCH] Generate OAK_NO_THROW assertions from (uint)i < (uint)a.len checks If "(uint)i < (uint)a.len" is true then we know that "i" is always within bounds and so "a[i]" does not need a range check. Commit migrated from https://github.com/dotnet/coreclr/commit/7e04389b73e7bf593b49367543fce51da206123c --- src/coreclr/src/jit/assertionprop.cpp | 53 ++++++++++++++++++++++++++++++----- src/coreclr/src/jit/compiler.h | 7 +++++ src/coreclr/src/jit/valuenum.cpp | 45 +++++++++++++++++++++++++++++ src/coreclr/src/jit/valuenum.h | 14 +++++++++ 4 files changed, 112 insertions(+), 7 deletions(-) diff --git a/src/coreclr/src/jit/assertionprop.cpp b/src/coreclr/src/jit/assertionprop.cpp index d2ae516..cf7190b 100644 --- a/src/coreclr/src/jit/assertionprop.cpp +++ b/src/coreclr/src/jit/assertionprop.cpp @@ -1771,6 +1771,8 @@ Compiler::AssertionIndex Compiler::optCreateJTrueBoundsAssertion(GenTreePtr tree GenTreePtr op2 = relop->gtGetOp2(); 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" @@ -1826,6 +1828,32 @@ Compiler::AssertionIndex 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)) + { + assert(arrLenUnsignedBnd.vnIdx != ValueNumStore::NoVN); + assert((arrLenUnsignedBnd.cmpOper == VNF_LT_UN) || (arrLenUnsignedBnd.cmpOper == VNF_GE_UN)); + assert(vnStore->IsVNArrLen(arrLenUnsignedBnd.vnLen)); + + 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.op2.kind = O2K_INVALID; + dsc.op2.vn = ValueNumStore::NoVN; + + AssertionIndex index = optAddAssertion(&dsc); + if ((arrLenUnsignedBnd.cmpOper == VNF_GE_UN) && (index != NO_ASSERTION_INDEX)) + { + // 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". + index |= OAE_NEXT_EDGE; + } + return index; + } // Cases where op1 holds the condition bound check and op2 is 0. // Loop condition like: "i < 100 == 0" // Assertion: "i < 100 == false" @@ -4463,17 +4491,28 @@ ASSERT_TP* Compiler::optComputeAssertionGen() ASSERT_TP jumpDestValueGen = BitVecOps::MakeCopy(apTraits, valueGen); AssertionIndex index = jtrue->GetAssertion(); - if (index != NO_ASSERTION_INDEX) + if ((index & OAE_INDEX_MASK) != NO_ASSERTION_INDEX) { - optImpliedAssertions(index, jumpDestValueGen); - BitVecOps::AddElemD(apTraits, jumpDestValueGen, index - 1); - - index = optFindComplementary(index); - if (index != NO_ASSERTION_INDEX) + if ((index & OAE_NEXT_EDGE) != 0) { - optImpliedAssertions(index, valueGen); + index &= OAE_INDEX_MASK; + // Currently OAE_NEXT_EDGE is only used with OAK_NO_THROW assertions + assert(optGetAssertion(index)->assertionKind == OAK_NO_THROW); + // Don't bother with implied/complementary assertions, there aren't any for OAK_NO_THROW BitVecOps::AddElemD(apTraits, valueGen, index - 1); } + else + { + optImpliedAssertions(index, jumpDestValueGen); + BitVecOps::AddElemD(apTraits, jumpDestValueGen, index - 1); + + index = optFindComplementary(index); + if (index != NO_ASSERTION_INDEX) + { + optImpliedAssertions(index, valueGen); + BitVecOps::AddElemD(apTraits, valueGen, index - 1); + } + } } jumpDestGen[block->bbNum] = jumpDestValueGen; diff --git a/src/coreclr/src/jit/compiler.h b/src/coreclr/src/jit/compiler.h index 651aac3..2f96b85 100644 --- a/src/coreclr/src/jit/compiler.h +++ b/src/coreclr/src/jit/compiler.h @@ -5882,6 +5882,13 @@ public: typedef unsigned short AssertionIndex; + enum optAssertionEdge : AssertionIndex + { + // OAE_JUMP_EDGE = 0x0000, // assertion holds for bbJumpDest (default) + OAE_NEXT_EDGE = 0x8000, // assertion holds for bbNext + OAE_INDEX_MASK = 0x7fff + }; + protected: static fgWalkPreFn optAddCopiesCallback; static fgWalkPreFn optVNAssertionPropCurStmtVisitor; diff --git a/src/coreclr/src/jit/valuenum.cpp b/src/coreclr/src/jit/valuenum.cpp index 3ab27e4..03cfb5b 100644 --- a/src/coreclr/src/jit/valuenum.cpp +++ b/src/coreclr/src/jit/valuenum.cpp @@ -3163,6 +3163,51 @@ void ValueNumStore::GetConstantBoundInfo(ValueNum vn, ConstantBoundInfo* info) } } +//------------------------------------------------------------------------ +// IsVNArrLenUnsignedBound: Checks if the specified vn represents an +// expression such as "(uint)i < (uint)a.len" that imply that the +// array index is valid (0 <= i && i < a.len). +// +// Arguments: +// vn - Value number to query +// info - Pointer to a ArrLenUnsignedBoundInfo object to return +// information about the expression. Not populated if the +// vn expression isn't suitable (e.g. i <= a.len) + +bool ValueNumStore::IsVNArrLenUnsignedBound(ValueNum vn, ArrLenUnsignedBoundInfo* info) +{ + VNFuncApp funcApp; + + if (GetVNFunc(vn, &funcApp)) + { + if (IsVNArrLen(funcApp.m_args[1])) + { + // We only care about "(uint)i < (uint)a.len" and its negation "(uint)i >= (uint)a.len" + if ((funcApp.m_func == VNF_LT_UN) || (funcApp.m_func == VNF_GE_UN)) + { + info->vnIdx = funcApp.m_args[0]; + info->cmpOper = funcApp.m_func; + info->vnLen = funcApp.m_args[1]; + return true; + } + } + else if (IsVNArrLen(funcApp.m_args[0])) + { + // We only care about "(uint)a.len > (uint)i" and its negation "(uint)a.len <= (uint)i" + if ((funcApp.m_func == VNF_GT_UN) || (funcApp.m_func == VNF_LE_UN)) + { + info->vnIdx = funcApp.m_args[1]; + // Let's keep a consistent operand order - it's always i < a.len, never a.len > i + info->cmpOper = (funcApp.m_func == VNF_GT_UN) ? VNF_LT_UN : VNF_GE_UN; + info->vnLen = funcApp.m_args[0]; + return true; + } + } + } + + return false; +} + bool ValueNumStore::IsVNArrLenBound(ValueNum vn) { // Do we have "var < a.len"? diff --git a/src/coreclr/src/jit/valuenum.h b/src/coreclr/src/jit/valuenum.h index 98d5091..d434b81 100644 --- a/src/coreclr/src/jit/valuenum.h +++ b/src/coreclr/src/jit/valuenum.h @@ -537,6 +537,17 @@ public: // Returns true iff the VN represents an integeral constant. bool IsVNInt32Constant(ValueNum vn); + struct ArrLenUnsignedBoundInfo + { + unsigned cmpOper; + ValueNum vnIdx; + ValueNum vnLen; + + ArrLenUnsignedBoundInfo() : cmpOper(GT_NONE), vnIdx(NoVN), vnLen(NoVN) + { + } + }; + struct ArrLenArithBoundInfo { // (vnArr.len - 1) > vnOp @@ -607,6 +618,9 @@ 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 "var < a.len" or "a.len <= var" return true. bool IsVNArrLenBound(ValueNum vn); -- 2.7.4