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.

4 files changed, 112 insertions, 7 deletions

diff --git a/src/jit/assertionprop.cpp b/src/jit/assertionprop.cpp
index d2ae5167f3..cf7190b257 100644
--- a/src/jit/assertionprop.cpp
+++ b/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/jit/compiler.h b/src/jit/compiler.h
index 651aac3a25..2f96b853ee 100644
--- a/src/jit/compiler.h
+++ b/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/jit/valuenum.cpp b/src/jit/valuenum.cpp
index 3ab27e4c1b..03cfb5b112 100644
--- a/src/jit/valuenum.cpp
+++ b/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/jit/valuenum.h b/src/jit/valuenum.h
index 98d5091f5d..d434b81aff 100644
--- a/src/jit/valuenum.h
+++ b/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);