Nov 4, 2020 · May 2, 2020 · Nov 3, 2020 · Nov 2, 2020
diff --git a/src/coreclr/src/jit/assertionprop.cpp b/src/coreclr/src/jit/assertionprop.cpp
    return optAssertionPropLocal_RelOp(assertions, tree, stmt);
 }

 /*************************************************************************************
 *
 *  Given the set of "assertions" to look up a relop assertion about the relop "tree",
 *  perform Value numbering based relop assertion propagation on the tree.
 *
 */
 //------------------------------------------------------------------------
 // optAssertionProp: try and optimize a relop via assertion propagation
 //    (and dominator based redundant branch elimination)
 //
 // Arguments:
 //   assertions  - set of live assertions
 //   tree        - tree to possibly optimize
 //   stmt        - statement containing the tree
 //
 // Returns:
 //   The modified tree, or nullptr if no assertion prop took place.
 //
 // Notes:
 //   Redundant branch elimination doesn't rely on assertions currently,
 //   it is done here out of convenience.
 //
 GenTree* Compiler::optAssertionPropGlobal_RelOp(ASSERT_VALARG_TP assertions, GenTree* tree, Statement* stmt)
 {
    GenTree* newTree = tree;
    GenTree* op1     = tree->AsOp()->gtOp1;
    GenTree* op2     = tree->AsOp()->gtOp2;

    // First, walk up the dom tree and see if any dominating block has branched on
    // exactly this tree's VN...
    //
    BasicBlock* prevBlock  = compCurBB;
    BasicBlock* domBlock   = compCurBB->bbIDom;
    int         relopValue = -1;

    while (domBlock != nullptr)
    {
        if (prevBlock == compCurBB)
        {
            JITDUMP("\nVN relop, checking " FMT_BB " for redundancy\n", compCurBB->bbNum);
        }

        // Check the current dominator
        //
        JITDUMP(" ... checking dom " FMT_BB "\n", domBlock->bbNum);

        if (domBlock->bbJumpKind == BBJ_COND)
        {
            Statement* const domJumpStmt = domBlock->lastStmt();
            GenTree* const   domJumpTree = domJumpStmt->GetRootNode();
            assert(domJumpTree->OperIs(GT_JTRUE));
            GenTree* const domCmpTree = domJumpTree->AsOp()->gtGetOp1();

            if (domCmpTree->OperKind() & GTK_RELOP)
            {
                ValueNum domCmpVN = domCmpTree->GetVN(VNK_Conservative);

                // Note we could also infer the tree relop's value from similar relops higher in the dom tree.
                // For example, (x >= 0) dominating (x > 0), or (x < 0) dominating (x > 0).
                //
                // That is left as a future enhancement.
                //
                if (domCmpVN == tree->GetVN(VNK_Conservative))
                {
                    // Thes compare in "tree" is redundant.
                    // Is there a unique path from the dominating compare?
                    JITDUMP(" Redundant compare; current relop:\n");
                    DISPTREE(tree);
                    JITDUMP(" dominating relop in " FMT_BB " with same VN:\n", domBlock->bbNum);
                    DISPTREE(domCmpTree);

                    BasicBlock* trueSuccessor  = domBlock->bbJumpDest;
                    BasicBlock* falseSuccessor = domBlock->bbNext;

                    const bool trueReaches  = fgReachable(trueSuccessor, compCurBB);
                    const bool falseReaches = fgReachable(falseSuccessor, compCurBB);

                    if (trueReaches && falseReaches)
                    {
                        // Both dominating compare outcomes reach the current block so we can't infer the
                        // value of the relop.
                        //
                        // If the dominating compare is close to the current compare, this may be a missed
                        // opportunity to tail duplicate.
                        //
                        JITDUMP("Both successors of " FMT_BB " reach, can't optimize\n", domBlock->bbNum);

                        if ((trueSuccessor->GetUniqueSucc() == compCurBB) ||
                            (falseSuccessor->GetUniqueSucc() == compCurBB))
                        {
                            JITDUMP("Perhaps we should have tail duplicated " FMT_BB "\n", compCurBB->bbNum);
                        }
                    }
                    else if (trueReaches)
                    {
                        // Taken jump in dominator reaches, fall through doesn't; relop must be true.
                        //
                        JITDUMP("Jump successor " FMT_BB " of " FMT_BB " reaches, relop must be true\n",
                                domBlock->bbJumpDest->bbNum, domBlock->bbNum);
                        relopValue = 1;
                        break;
                    }
                    else if (falseReaches)
                    {
                        // Fall through from dominator reaches, taken jump doesn't; relop must be false.
                        //
                        JITDUMP("Fall through successor " FMT_BB " of " FMT_BB " reaches, relop must be false\n",
                                domBlock->bbNext->bbNum, domBlock->bbNum);
                        relopValue = 0;
                        break;
                    }
                    else
                    {
                        // No apparent path from the dominating BB.
                        //
                        // If domBlock or compCurBB is in an EH handler we may fail to find a path.
                        // Just ignore those cases.
                        //
                        // No point in looking further up the tree.
                        //
                        break;
                    }
                }
            }
        }

        // Keep looking higher up in the tree
        //
        prevBlock = domBlock;
        domBlock  = domBlock->bbIDom;
    }

    // Did we determine the relop value via dominance checks? If so, optimize.
    //
    if (relopValue == -1)
    {
        JITDUMP("Failed to find a suitable dominating compare, so we won't optimize\n");
    }
    else
    {
        // Bail out if tree is has certain side effects
        //
        // Note we really shouldn't get here if the tree has non-exception effects,
        // as they should have impacted the value number.
        //
        if ((tree->gtFlags & GTF_SIDE_EFFECT) != 0)
        {
            // Bail if there is a non-exception effect.
            //
            if ((tree->gtFlags & GTF_SIDE_EFFECT) != GTF_EXCEPT)
            {
                JITDUMP("Current relop has non-exception side effects, so we won't optimize\n");
                return nullptr;
            }

            // Be conservative if there is an exception effect and we're in an EH region
            // as we might not model the full extent of EH flow.
            //
            if (compCurBB->hasTryIndex())
            {
                JITDUMP("Current relop has exception side effect and is in a try, so we won't optimize\n");
                return nullptr;
            }
        }

        JITDUMP("\nVN relop based redundant branch opt in " FMT_BB ":\n", compCurBB->bbNum);

        tree->ChangeOperConst(GT_CNS_INT);
        tree->AsIntCon()->gtIconVal = relopValue;

        newTree = fgMorphTree(tree);
        DISPTREE(newTree);
        return optAssertionProp_Update(newTree, tree, stmt);
    }

    // Look for assertions of the form (tree EQ/NE 0)
    AssertionIndex index = optGlobalAssertionIsEqualOrNotEqualZero(assertions, tree);
Original file line number	Diff line number	Diff line change
Expand Up		@@ -3203,18 +3203,175 @@ GenTree* Compiler::optAssertionProp_RelOp(ASSERT_VALARG_TP assertions, GenTree*
		return optAssertionPropLocal_RelOp(assertions, tree, stmt);
		}

		/*************************************************************************************
		*
		* Given the set of "assertions" to look up a relop assertion about the relop "tree",
		* perform Value numbering based relop assertion propagation on the tree.
		*
		*/
		//------------------------------------------------------------------------
		// optAssertionProp: try and optimize a relop via assertion propagation
		// (and dominator based redundant branch elimination)
		//
		// Arguments:
		// assertions - set of live assertions
		// tree - tree to possibly optimize
		// stmt - statement containing the tree
		//
		// Returns:
		// The modified tree, or nullptr if no assertion prop took place.
		//
		// Notes:
		// Redundant branch elimination doesn't rely on assertions currently,
		// it is done here out of convenience.
		//
		GenTree* Compiler::optAssertionPropGlobal_RelOp(ASSERT_VALARG_TP assertions, GenTree* tree, Statement* stmt)
		{
		GenTree* newTree = tree;
		GenTree* op1 = tree->AsOp()->gtOp1;
		GenTree* op2 = tree->AsOp()->gtOp2;

		// First, walk up the dom tree and see if any dominating block has branched on
Copy link Contributor briansullNov 2, 2020 Choose a reason for hiding this comment The reason will be displayed to describe this comment to others.Learn more. You should update the method header to the standard header and underNote: add comment saying that we also do this special case optimization.
		// exactly this tree's VN...
		//
		BasicBlock* prevBlock = compCurBB;
		BasicBlock* domBlock = compCurBB->bbIDom;
		int relopValue = -1;

		while (domBlock != nullptr)
		{
		if (prevBlock == compCurBB)
		{
		JITDUMP("\nVN relop, checking " FMT_BB " for redundancy\n", compCurBB->bbNum);
		}

		// Check the current dominator
		//
		JITDUMP(" ... checking dom " FMT_BB "\n", domBlock->bbNum);

		if (domBlock->bbJumpKind == BBJ_COND)
		{
		Statement* const domJumpStmt = domBlock->lastStmt();
		GenTree* const domJumpTree = domJumpStmt->GetRootNode();
		assert(domJumpTree->OperIs(GT_JTRUE));
		GenTree* const domCmpTree = domJumpTree->AsOp()->gtGetOp1();

		if (domCmpTree->OperKind() & GTK_RELOP)
		{
		ValueNum domCmpVN = domCmpTree->GetVN(VNK_Conservative);

		// Note we could also infer the tree relop's value from similar relops higher in the dom tree.
		// For example, (x >= 0) dominating (x > 0), or (x < 0) dominating (x > 0).
		//
		// That is left as a future enhancement.
		//
		if (domCmpVN == tree->GetVN(VNK_Conservative))
		{
		// Thes compare in "tree" is redundant.
		// Is there a unique path from the dominating compare?
		JITDUMP(" Redundant compare; current relop:\n");
		DISPTREE(tree);
		JITDUMP(" dominating relop in " FMT_BB " with same VN:\n", domBlock->bbNum);
		DISPTREE(domCmpTree);

		BasicBlock* trueSuccessor = domBlock->bbJumpDest;
		BasicBlock* falseSuccessor = domBlock->bbNext;

		const bool trueReaches = fgReachable(trueSuccessor, compCurBB);
		const bool falseReaches = fgReachable(falseSuccessor, compCurBB);

		if (trueReaches && falseReaches)
		{
		// Both dominating compare outcomes reach the current block so we can't infer the
		// value of the relop.
		//
		// If the dominating compare is close to the current compare, this may be a missed
		// opportunity to tail duplicate.
		//
		JITDUMP("Both successors of " FMT_BB " reach, can't optimize\n", domBlock->bbNum);

		if ((trueSuccessor->GetUniqueSucc() == compCurBB) \|\|
		(falseSuccessor->GetUniqueSucc() == compCurBB))
		{
		JITDUMP("Perhaps we should have tail duplicated " FMT_BB "\n", compCurBB->bbNum);
		}
		}
		else if (trueReaches)
		{
		// Taken jump in dominator reaches, fall through doesn't; relop must be true.
		//
		JITDUMP("Jump successor " FMT_BB " of " FMT_BB " reaches, relop must be true\n",
		domBlock->bbJumpDest->bbNum, domBlock->bbNum);
		relopValue = 1;
		break;
		}
		else if (falseReaches)
		{
		// Fall through from dominator reaches, taken jump doesn't; relop must be false.
		//
		JITDUMP("Fall through successor " FMT_BB " of " FMT_BB " reaches, relop must be false\n",
		domBlock->bbNext->bbNum, domBlock->bbNum);
		relopValue = 0;
		break;
		}
		else
		{
		// No apparent path from the dominating BB.
		//
		// If domBlock or compCurBB is in an EH handler we may fail to find a path.
		// Just ignore those cases.
		//
		// No point in looking further up the tree.
		//
		break;
		}
		}
		}
		}

		// Keep looking higher up in the tree
		//
		prevBlock = domBlock;
		domBlock = domBlock->bbIDom;
		}

		// Did we determine the relop value via dominance checks? If so, optimize.
		//
		if (relopValue == -1)
		{
		JITDUMP("Failed to find a suitable dominating compare, so we won't optimize\n");
		}
		else
		{
		// Bail out if tree is has certain side effects
		//
		// Note we really shouldn't get here if the tree has non-exception effects,
		// as they should have impacted the value number.
		//
		if ((tree->gtFlags & GTF_SIDE_EFFECT) != 0)
		{
		// Bail if there is a non-exception effect.
		//
		if ((tree->gtFlags & GTF_SIDE_EFFECT) != GTF_EXCEPT)
		{
		JITDUMP("Current relop has non-exception side effects, so we won't optimize\n");
		return nullptr;
		}

		// Be conservative if there is an exception effect and we're in an EH region
		// as we might not model the full extent of EH flow.
		//
		if (compCurBB->hasTryIndex())
		{
		JITDUMP("Current relop has exception side effect and is in a try, so we won't optimize\n");
		return nullptr;
		}
		}

		JITDUMP("\nVN relop based redundant branch opt in " FMT_BB ":\n", compCurBB->bbNum);

		tree->ChangeOperConst(GT_CNS_INT);
		tree->AsIntCon()->gtIconVal = relopValue;

		newTree = fgMorphTree(tree);
		DISPTREE(newTree);
		return optAssertionProp_Update(newTree, tree, stmt);
		}

		// Look for assertions of the form (tree EQ/NE 0)
		AssertionIndex index = optGlobalAssertionIsEqualOrNotEqualZero(assertions, tree);

Expand Down