Merge pull request #9773 from mikedn/user-range-check

Generate OAK_NO_THROW assertions from (uint)i < (uint)a.len checks

5 files changed, 161 insertions, 35 deletions

diff --git a/src/jit/assertionprop.cpp b/src/jit/assertionprop.cpp
index cb0832fe47..192ed5c6af 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"
@@ -4429,15 +4457,10 @@ ASSERT_TP* Compiler::optComputeAssertionGen()
 {
     ASSERT_TP* jumpDestGen = fgAllocateTypeForEachBlk<ASSERT_TP>();
 
-    ASSERT_TP valueGen         = BitVecOps::MakeEmpty(apTraits);
-    ASSERT_TP jumpDestValueGen = BitVecOps::MakeEmpty(apTraits);
-
     for (BasicBlock* block = fgFirstBB; block; block = block->bbNext)
     {
-        jumpDestGen[block->bbNum] = BitVecOps::MakeEmpty(apTraits);
-
-        BitVecOps::ClearD(apTraits, valueGen);
-        BitVecOps::ClearD(apTraits, jumpDestValueGen);
+        ASSERT_TP valueGen = BitVecOps::MakeEmpty(apTraits);
+        GenTree*  jtrue    = nullptr;
 
         // Walk the statement trees in this basic block.
         for (GenTreePtr stmt = block->bbTreeList; stmt; stmt = stmt->gtNext)
@@ -4446,47 +4469,72 @@ ASSERT_TP* Compiler::optComputeAssertionGen()
 
             for (GenTreePtr tree = stmt->gtStmt.gtStmtList; tree; tree = tree->gtNext)
             {
-                // Store whatever we have accumulated into jumpDest edge's valueGen.
                 if (tree->gtOper == GT_JTRUE)
                 {
-                    BitVecOps::Assign(apTraits, jumpDestValueGen, valueGen);
+                    // A GT_TRUE is always the last node in a tree, so we can break here
+                    assert((tree->gtNext == nullptr) && (stmt->gtNext == nullptr));
+                    jtrue = tree;
+                    break;
                 }
-                if (!tree->HasAssertion())
+
+                AssertionIndex index = tree->GetAssertion();
+                if (index != NO_ASSERTION_INDEX)
                 {
-                    continue;
+                    optImpliedAssertions(index, valueGen);
+                    BitVecOps::AddElemD(apTraits, valueGen, index - 1);
                 }
+            }
+        }
 
-                // For regular trees, just update valueGen. For GT_JTRUE, for false part,
-                // update valueGen and true part update jumpDestValueGen.
-                AssertionIndex assertionIndex[2] = {(AssertionIndex)tree->GetAssertion(),
-                                                    (tree->OperGet() == GT_JTRUE)
-                                                        ? optFindComplementary((AssertionIndex)tree->GetAssertion())
-                                                        : 0};
+        if (jtrue != nullptr)
+        {
+            // Copy whatever we have accumulated into jumpDest edge's valueGen.
+            ASSERT_TP jumpDestValueGen = BitVecOps::MakeCopy(apTraits, valueGen);
 
-                for (unsigned i = 0; i < 2; ++i)
+            AssertionIndex index = jtrue->GetAssertion();
+            if ((index & OAE_INDEX_MASK) != NO_ASSERTION_INDEX)
+            {
+                if ((index & OAE_NEXT_EDGE) != 0)
+                {
+                    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 assertions, there aren't any for OAK_NO_THROW
+                    BitVecOps::AddElemD(apTraits, valueGen, index - 1);
+                }
+                else
                 {
-                    if (assertionIndex[i] > 0)
+                    // If GT_JTRUE, and true path, update jumpDestValueGen.
+                    optImpliedAssertions(index, jumpDestValueGen);
+                    BitVecOps::AddElemD(apTraits, jumpDestValueGen, index - 1);
+
+                    index = optFindComplementary(index);
+                    if (index != NO_ASSERTION_INDEX)
                     {
-                        // If GT_JTRUE, and true part use jumpDestValueGen.
-                        ASSERT_TP& gen = (i == 0 && tree->OperGet() == GT_JTRUE) ? jumpDestValueGen : valueGen;
-                        optImpliedAssertions(assertionIndex[i], gen);
-                        BitVecOps::AddElemD(apTraits, gen, assertionIndex[i] - 1);
+                        // If GT_JTRUE, and false path and we have a complementary assertion available update valueGen
+                        optImpliedAssertions(index, valueGen);
+                        BitVecOps::AddElemD(apTraits, valueGen, index - 1);
                     }
                 }
             }
+
+            jumpDestGen[block->bbNum] = jumpDestValueGen;
+        }
+        else
+        {
+            jumpDestGen[block->bbNum] = BitVecOps::MakeEmpty(apTraits);
         }
 
-        BitVecOps::Assign(apTraits, block->bbAssertionGen, valueGen);
-        BitVecOps::Assign(apTraits, jumpDestGen[block->bbNum], jumpDestValueGen);
+        block->bbAssertionGen = valueGen;
 
 #ifdef DEBUG
         if (verbose)
         {
-            printf("\nBB%02u valueGen = %s", block->bbNum, BitVecOps::ToString(apTraits, valueGen));
+            printf("\nBB%02u valueGen = %s", block->bbNum, BitVecOps::ToString(apTraits, block->bbAssertionGen));
             if (block->bbJumpKind == BBJ_COND)
             {
                 printf(" => BB%02u valueGen = %s,", block->bbJumpDest->bbNum,
-                       BitVecOps::ToString(apTraits, jumpDestValueGen));
+                       BitVecOps::ToString(apTraits, jumpDestGen[block->bbNum]));
             }
         }
 #endif
@@ -5070,6 +5118,13 @@ void Compiler::optAssertionPropMain()
                                                        // and thus we must morph, set order, re-link
             for (GenTreePtr tree = stmt->gtStmt.gtStmtList; tree; tree = tree->gtNext)
             {
+                if (tree->OperIs(GT_JTRUE))
+                {
+                    // A GT_TRUE is always the last node in a tree, so we can break here
+                    assert((tree->gtNext == nullptr) && (stmt->gtNext == nullptr));
+                    break;
+                }
+
                 JITDUMP("Propagating %s assertions for BB%02d, stmt [%06d], tree [%06d], tree -> %d\n",
                         BitVecOps::ToString(apTraits, assertions), block->bbNum, dspTreeID(stmt), dspTreeID(tree),
                         tree->GetAssertion());
@@ -5081,16 +5136,12 @@ void Compiler::optAssertionPropMain()
                     tree = newTree;
                 }
 
-                // Is this an assignment to a local variable
-                GenTreeLclVarCommon* lclVarTree = nullptr;
-
                 // If this tree makes an assertion - make it available.
-                if (tree->HasAssertion())
+                AssertionIndex index = tree->GetAssertion();
+                if (index != NO_ASSERTION_INDEX)
                 {
-                    BitVecOps::AddElemD(apTraits, assertions, tree->GetAssertion() - 1);
-
-                    // Also include any implied assertions for the tree node.
-                    optImpliedAssertions((AssertionIndex)tree->GetAssertion(), assertions);
+                    optImpliedAssertions(index, assertions);
+                    BitVecOps::AddElemD(apTraits, assertions, index - 1);
                 }
             }
 
diff --git a/src/jit/compiler.h b/src/jit/compiler.h
index 651aac3a25..be71875565 100644
--- a/src/jit/compiler.h
+++ b/src/jit/compiler.h
@@ -5882,6 +5882,19 @@ public:
 
     typedef unsigned short AssertionIndex;
 
+    // By default the assertion generated by a GT_JTRUE node holds on the true (bbJumpDest) edge.
+    // If the OAE_NEXT_EDGE bit of the assertion index is set then the assertion holds on the false (bbNext) edge
+    // and the OAE_NEXT_EDGE bit needs to be masked to obtain the real assertion index.
+    // Currently this is used by OAK_NO_THROW assertions but it may also be useful for other kinds of assertions
+    // by removing the need to create unnecessary complementary assertions. However, this bit twiddling mechanism
+    // is fragile and should be replaced with something cleaner (e.g. struct + bitfield).
+    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/gentree.h b/src/jit/gentree.h
index a85ca20eba..a8a5018f22 100644
--- a/src/jit/gentree.h
+++ b/src/jit/gentree.h
@@ -397,6 +397,7 @@ struct GenTree
 
 #if ASSERTION_PROP
     unsigned short gtAssertionNum; // 0 or Assertion table index
+                                   // possibly ORed with optAssertionEdge::OAE_NEXT_EDGE
                                    // valid only for non-GT_STMT nodes
 
     bool HasAssertion() const
diff --git a/src/jit/valuenum.cpp b/src/jit/valuenum.cpp
index 3ab27e4c1b..b771bf6253 100644
--- a/src/jit/valuenum.cpp
+++ b/src/jit/valuenum.cpp
@@ -3163,6 +3163,53 @@ 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
+//    (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).
+//           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.
+
+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);