assertionprop.cpp

// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.

/*XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX                                                                           XX
XX                          AssertionProp                                    XX
XX                                                                           XX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
*/

#include "jitpch.h"
#include "rangecheck.h"
#ifdef _MSC_VER
#pragma hdrstop
#endif

//------------------------------------------------------------------------
// Contains: Whether the range contains a given integral value, inclusive.
//
// Arguments:
//    value - the integral value in question
//
// Return Value:
//    "true" if the value is within the range's bounds, "false" otherwise.
//
bool IntegralRange::Contains(int64_t value) const
{
    int64_t lowerBound = SymbolicToRealValue(m_lowerBound);
    int64_t upperBound = SymbolicToRealValue(m_upperBound);

    return (lowerBound <= value) && (value <= upperBound);
}

//------------------------------------------------------------------------
// SymbolicToRealValue: Convert a symbolic value to a 64-bit signed integer.
//
// Arguments:
//    value - the symbolic value in question
//
// Return Value:
//    Integer corresponding to the symbolic value.
//
/* static */ int64_t IntegralRange::SymbolicToRealValue(SymbolicIntegerValue value)
{
    static const int64_t SymbolicToRealMap[]{
        INT64_MIN,               // SymbolicIntegerValue::LongMin
        INT32_MIN,               // SymbolicIntegerValue::IntMin
        INT16_MIN,               // SymbolicIntegerValue::ShortMin
        INT8_MIN,                // SymbolicIntegerValue::ByteMin
        0,                       // SymbolicIntegerValue::Zero
        1,                       // SymbolicIntegerValue::One
        INT8_MAX,                // SymbolicIntegerValue::ByteMax
        UINT8_MAX,               // SymbolicIntegerValue::UByteMax
        INT16_MAX,               // SymbolicIntegerValue::ShortMax
        UINT16_MAX,              // SymbolicIntegerValue::UShortMax
        CORINFO_Array_MaxLength, // SymbolicIntegerValue::ArrayLenMax
        INT32_MAX,               // SymbolicIntegerValue::IntMax
        UINT32_MAX,              // SymbolicIntegerValue::UIntMax
        INT64_MAX                // SymbolicIntegerValue::LongMax
    };

    assert(sizeof(SymbolicIntegerValue) == sizeof(int32_t));
    assert(SymbolicToRealMap[static_cast<int32_t>(SymbolicIntegerValue::LongMin)] == INT64_MIN);
    assert(SymbolicToRealMap[static_cast<int32_t>(SymbolicIntegerValue::Zero)] == 0);
    assert(SymbolicToRealMap[static_cast<int32_t>(SymbolicIntegerValue::LongMax)] == INT64_MAX);

    return SymbolicToRealMap[static_cast<int32_t>(value)];
}

//------------------------------------------------------------------------
// LowerBoundForType: Get the symbolic lower bound for a type.
//
// Arguments:
//    type - the integral type in question
//
// Return Value:
//    Symbolic value representing the smallest possible value "type" can represent.
//
/* static */ SymbolicIntegerValue IntegralRange::LowerBoundForType(var_types type)
{
    switch (type)
    {
        case TYP_UBYTE:
        case TYP_USHORT:
            return SymbolicIntegerValue::Zero;
        case TYP_BYTE:
            return SymbolicIntegerValue::ByteMin;
        case TYP_SHORT:
            return SymbolicIntegerValue::ShortMin;
        case TYP_INT:
            return SymbolicIntegerValue::IntMin;
        case TYP_LONG:
            return SymbolicIntegerValue::LongMin;
        default:
            unreached();
    }
}

//------------------------------------------------------------------------
// UpperBoundForType: Get the symbolic upper bound for a type.
//
// Arguments:
//    type - the integral type in question
//
// Return Value:
//    Symbolic value representing the largest possible value "type" can represent.
//
/* static */ SymbolicIntegerValue IntegralRange::UpperBoundForType(var_types type)
{
    switch (type)
    {
        case TYP_BYTE:
            return SymbolicIntegerValue::ByteMax;
        case TYP_UBYTE:
            return SymbolicIntegerValue::UByteMax;
        case TYP_SHORT:
            return SymbolicIntegerValue::ShortMax;
        case TYP_USHORT:
            return SymbolicIntegerValue::UShortMax;
        case TYP_INT:
            return SymbolicIntegerValue::IntMax;
        case TYP_UINT:
            return SymbolicIntegerValue::UIntMax;
        case TYP_LONG:
            return SymbolicIntegerValue::LongMax;
        default:
            unreached();
    }
}

//------------------------------------------------------------------------
// ForNode: Compute the integral range for a node.
//
// Arguments:
//    node     - the node, of an integral type, in question
//    compiler - the Compiler, used to retrieve additional info
//
// Return Value:
//    The integral range this node produces.
//
/* static */ IntegralRange IntegralRange::ForNode(GenTree* node, Compiler* compiler)
{
    assert(varTypeIsIntegral(node));

    var_types rangeType = node->TypeGet();

    switch (node->OperGet())
    {
        case GT_EQ:
        case GT_NE:
        case GT_LT:
        case GT_LE:
        case GT_GE:
        case GT_GT:
            return {SymbolicIntegerValue::Zero, SymbolicIntegerValue::One};

        case GT_AND:
        {
            IntegralRange leftRange  = IntegralRange::ForNode(node->gtGetOp1(), compiler);
            IntegralRange rightRange = IntegralRange::ForNode(node->gtGetOp2(), compiler);
            if (leftRange.IsNonNegative() && rightRange.IsNonNegative())
            {
                // If both sides are known to be non-negative, the result is non-negative.
                // Further, the top end of the range cannot exceed the min of the two upper bounds.
                return {SymbolicIntegerValue::Zero, min(leftRange.GetUpperBound(), rightRange.GetUpperBound())};
            }

            if (leftRange.IsNonNegative() || rightRange.IsNonNegative())
            {
                // If only one side is known to be non-negative, however it is harder to
                // reason about the upper bound.
                return {SymbolicIntegerValue::Zero, UpperBoundForType(rangeType)};
            }

            break;
        }

        case GT_ARR_LENGTH:
        case GT_MDARR_LENGTH:
            return {SymbolicIntegerValue::Zero, SymbolicIntegerValue::ArrayLenMax};

        case GT_CALL:
            if (node->AsCall()->NormalizesSmallTypesOnReturn())
            {
                rangeType = static_cast<var_types>(node->AsCall()->gtReturnType);
            }
            break;

        case GT_IND:
        {
            GenTree* const addr = node->AsIndir()->Addr();

            if (node->TypeIs(TYP_INT) && addr->OperIs(GT_ADD) && addr->gtGetOp1()->OperIs(GT_LCL_VAR) &&
                addr->gtGetOp2()->IsIntegralConst(OFFSETOF__CORINFO_Span__length))
            {
                GenTreeLclVar* const lclVar = addr->gtGetOp1()->AsLclVar();

                if (compiler->lvaGetDesc(lclVar->GetLclNum())->IsSpan())
                {
                    assert(compiler->lvaIsImplicitByRefLocal(lclVar->GetLclNum()));
                    return {SymbolicIntegerValue::Zero, UpperBoundForType(rangeType)};
                }
            }
            break;
        }

        case GT_LCL_FLD:
        {
            GenTreeLclFld* const lclFld = node->AsLclFld();
            LclVarDsc* const     varDsc = compiler->lvaGetDesc(lclFld);

            if (node->TypeIs(TYP_INT) && varDsc->IsSpan() && lclFld->GetLclOffs() == OFFSETOF__CORINFO_Span__length)
            {
                return {SymbolicIntegerValue::Zero, UpperBoundForType(rangeType)};
            }

            break;
        }

        case GT_LCL_VAR:
        {
            LclVarDsc* const varDsc = compiler->lvaGetDesc(node->AsLclVar());

            if (varDsc->lvNormalizeOnStore())
            {
                rangeType = compiler->lvaGetDesc(node->AsLclVar())->TypeGet();
            }

            if (varDsc->IsNeverNegative())
            {
                return {SymbolicIntegerValue::Zero, UpperBoundForType(rangeType)};
            }
            break;
        }

        case GT_CNS_INT:
        {
            if (node->IsIntegralConst(0) || node->IsIntegralConst(1))
            {
                return {SymbolicIntegerValue::Zero, SymbolicIntegerValue::One};
            }

            int64_t constValue = node->AsIntCon()->IntegralValue();
            if (constValue >= 0)
            {
                return {SymbolicIntegerValue::Zero, UpperBoundForType(rangeType)};
            }

            break;
        }

        case GT_QMARK:
            return Union(ForNode(node->AsQmark()->ThenNode(), compiler),
                         ForNode(node->AsQmark()->ElseNode(), compiler));

        case GT_CAST:
            return ForCastOutput(node->AsCast(), compiler);

#if defined(FEATURE_HW_INTRINSICS)
        case GT_HWINTRINSIC:
            switch (node->AsHWIntrinsic()->GetHWIntrinsicId())
            {
#if defined(TARGET_XARCH)
                case NI_Vector128_op_Equality:
                case NI_Vector128_op_Inequality:
                case NI_Vector256_op_Equality:
                case NI_Vector256_op_Inequality:
                case NI_Vector512_op_Equality:
                case NI_Vector512_op_Inequality:
                case NI_X86Base_CompareScalarOrderedEqual:
                case NI_X86Base_CompareScalarOrderedNotEqual:
                case NI_X86Base_CompareScalarOrderedLessThan:
                case NI_X86Base_CompareScalarOrderedLessThanOrEqual:
                case NI_X86Base_CompareScalarOrderedGreaterThan:
                case NI_X86Base_CompareScalarOrderedGreaterThanOrEqual:
                case NI_X86Base_CompareScalarUnorderedEqual:
                case NI_X86Base_CompareScalarUnorderedNotEqual:
                case NI_X86Base_CompareScalarUnorderedLessThanOrEqual:
                case NI_X86Base_CompareScalarUnorderedLessThan:
                case NI_X86Base_CompareScalarUnorderedGreaterThanOrEqual:
                case NI_X86Base_CompareScalarUnorderedGreaterThan:
                case NI_X86Base_TestC:
                case NI_X86Base_TestZ:
                case NI_X86Base_TestNotZAndNotC:
                case NI_AVX_TestC:
                case NI_AVX_TestZ:
                case NI_AVX_TestNotZAndNotC:
                    return {SymbolicIntegerValue::Zero, SymbolicIntegerValue::One};

                case NI_X86Base_Extract:
                case NI_X86Base_X64_Extract:
                case NI_Vector128_ToScalar:
                case NI_Vector256_ToScalar:
                case NI_Vector512_ToScalar:
                case NI_Vector128_GetElement:
                case NI_Vector256_GetElement:
                case NI_Vector512_GetElement:
                    if (varTypeIsSmall(node->AsHWIntrinsic()->GetSimdBaseType()))
                    {
                        return ForType(node->AsHWIntrinsic()->GetSimdBaseType());
                    }
                    break;

                case NI_AVX2_LeadingZeroCount:
                case NI_AVX2_TrailingZeroCount:
                case NI_AVX2_X64_LeadingZeroCount:
                case NI_AVX2_X64_TrailingZeroCount:
                case NI_X86Base_PopCount:
                case NI_X86Base_X64_PopCount:
                    // Note: No advantage in using a precise range for IntegralRange.
                    // Example: IntCns = 42 gives [0..127] with a non -precise range, [42,42] with a precise range.
                    return {SymbolicIntegerValue::Zero, SymbolicIntegerValue::ByteMax};
#elif defined(TARGET_ARM64)
                case NI_Vector64_op_Equality:
                case NI_Vector64_op_Inequality:
                case NI_Vector128_op_Equality:
                case NI_Vector128_op_Inequality:
                    return {SymbolicIntegerValue::Zero, SymbolicIntegerValue::One};

                case NI_AdvSimd_Extract:
                case NI_Vector64_ToScalar:
                case NI_Vector128_ToScalar:
                case NI_Vector64_GetElement:
                case NI_Vector128_GetElement:
                    if (varTypeIsSmall(node->AsHWIntrinsic()->GetSimdBaseType()))
                    {
                        return ForType(node->AsHWIntrinsic()->GetSimdBaseType());
                    }
                    break;

                case NI_AdvSimd_PopCount:
                case NI_AdvSimd_LeadingZeroCount:
                case NI_AdvSimd_LeadingSignCount:
                case NI_ArmBase_LeadingZeroCount:
                case NI_ArmBase_Arm64_LeadingZeroCount:
                case NI_ArmBase_Arm64_LeadingSignCount:
                    // Note: No advantage in using a precise range for IntegralRange.
                    // Example: IntCns = 42 gives [0..127] with a non -precise range, [42,42] with a precise range.
                    return {SymbolicIntegerValue::Zero, SymbolicIntegerValue::ByteMax};
#else
#error Unsupported platform
#endif
                default:
                    break;
            }
            break;
#endif // defined(FEATURE_HW_INTRINSICS)

        default:
            break;
    }

    return ForType(rangeType);
}

//------------------------------------------------------------------------
// ForCastInput: Get the non-overflowing input range for a cast.
//
// This routine computes the input range for a cast from
// an integer to an integer for which it will not overflow.
// See also the specification comment for IntegralRange.
//
// Arguments:
//    cast - the cast node for which the range will be computed
//
// Return Value:
//    The range this cast consumes without overflowing - see description.
//
/* static */ IntegralRange IntegralRange::ForCastInput(GenTreeCast* cast)
{
    var_types fromType     = genActualType(cast->CastOp());
    var_types toType       = cast->CastToType();
    bool      fromUnsigned = cast->IsUnsigned();

    assert((fromType == TYP_INT) || (fromType == TYP_LONG) || varTypeIsGC(fromType));
    assert(varTypeIsIntegral(toType));

    // Cast from a GC type is the same as a cast from TYP_I_IMPL for our purposes.
    if (varTypeIsGC(fromType))
    {
        fromType = TYP_I_IMPL;
    }

    if (!cast->gtOverflow())
    {
        // CAST(small type <- uint/int/ulong/long) - [TO_TYPE_MIN..TO_TYPE_MAX]
        if (varTypeIsSmall(toType))
        {
            return {LowerBoundForType(toType), UpperBoundForType(toType)};
        }

        // We choose to say here that representation-changing casts never overflow.
        // It does not really matter what we do here because representation-changing
        // non-overflowing casts cannot be deleted from the IR in any case.
        // CAST(uint/int <- uint/int)     - [INT_MIN..INT_MAX]
        // CAST(uint/int <- ulong/long)   - [LONG_MIN..LONG_MAX]
        // CAST(ulong/long <- uint/int)   - [INT_MIN..INT_MAX]
        // CAST(ulong/long <- ulong/long) - [LONG_MIN..LONG_MAX]
        return ForType(fromType);
    }

    SymbolicIntegerValue lowerBound;
    SymbolicIntegerValue upperBound;

    // CAST_OVF(small type <- int/long)   - [TO_TYPE_MIN..TO_TYPE_MAX]
    // CAST_OVF(small type <- uint/ulong) - [0..TO_TYPE_MAX]
    if (varTypeIsSmall(toType))
    {
        lowerBound = fromUnsigned ? SymbolicIntegerValue::Zero : LowerBoundForType(toType);
        upperBound = UpperBoundForType(toType);
    }
    else
    {
        switch (toType)
        {
            // CAST_OVF(uint <- uint)       - [INT_MIN..INT_MAX]
            // CAST_OVF(uint <- int)        - [0..INT_MAX]
            // CAST_OVF(uint <- ulong/long) - [0..UINT_MAX]
            case TYP_UINT:
                if (fromType == TYP_LONG)
                {
                    lowerBound = SymbolicIntegerValue::Zero;
                    upperBound = SymbolicIntegerValue::UIntMax;
                }
                else
                {
                    lowerBound = fromUnsigned ? SymbolicIntegerValue::IntMin : SymbolicIntegerValue::Zero;
                    upperBound = SymbolicIntegerValue::IntMax;
                }
                break;

            // CAST_OVF(int <- uint/ulong) - [0..INT_MAX]
            // CAST_OVF(int <- int/long)   - [INT_MIN..INT_MAX]
            case TYP_INT:
                lowerBound = fromUnsigned ? SymbolicIntegerValue::Zero : SymbolicIntegerValue::IntMin;
                upperBound = SymbolicIntegerValue::IntMax;
                break;

            // CAST_OVF(ulong <- uint)  - [INT_MIN..INT_MAX]
            // CAST_OVF(ulong <- int)   - [0..INT_MAX]
            // CAST_OVF(ulong <- ulong) - [LONG_MIN..LONG_MAX]
            // CAST_OVF(ulong <- long)  - [0..LONG_MAX]
            case TYP_ULONG:
                lowerBound = fromUnsigned ? LowerBoundForType(fromType) : SymbolicIntegerValue::Zero;
                upperBound = UpperBoundForType(fromType);
                break;

            // CAST_OVF(long <- uint/int) - [INT_MIN..INT_MAX]
            // CAST_OVF(long <- ulong)    - [0..LONG_MAX]
            // CAST_OVF(long <- long)     - [LONG_MIN..LONG_MAX]
            case TYP_LONG:
                if (fromUnsigned && (fromType == TYP_LONG))
                {
                    lowerBound = SymbolicIntegerValue::Zero;
                }
                else
                {
                    lowerBound = LowerBoundForType(fromType);
                }
                upperBound = UpperBoundForType(fromType);
                break;

            default:
                unreached();
        }
    }

    return {lowerBound, upperBound};
}

//------------------------------------------------------------------------
// ForCastOutput: Get the output range for a cast.
//
// This method is the "output" counterpart to ForCastInput, it returns
// a range produced by a cast (by definition, non-overflowing one).
// The output range is the same for representation-preserving casts, but
// can be different for others. One example is CAST_OVF(uint <- long).
// The input range is [0..UINT_MAX], while the output is [INT_MIN..INT_MAX].
// Unlike ForCastInput, this method supports casts from floating point types.
//
// Arguments:
//   cast     - the cast node for which the range will be computed
//   compiler - Compiler object
//
// Return Value:
//   The range this cast produces - see description.
//
/* static */ IntegralRange IntegralRange::ForCastOutput(GenTreeCast* cast, Compiler* compiler)
{
    var_types fromType     = genActualType(cast->CastOp());
    var_types toType       = cast->CastToType();
    bool      fromUnsigned = cast->IsUnsigned();

    assert((fromType == TYP_INT) || (fromType == TYP_LONG) || varTypeIsFloating(fromType) || varTypeIsGC(fromType));
    assert(varTypeIsIntegral(toType));

    // CAST/CAST_OVF(small type <- float/double) - [TO_TYPE_MIN..TO_TYPE_MAX]
    // CAST/CAST_OVF(uint/int <- float/double)   - [INT_MIN..INT_MAX]
    // CAST/CAST_OVF(ulong/long <- float/double) - [LONG_MIN..LONG_MAX]
    if (varTypeIsFloating(fromType))
    {
        if (!varTypeIsSmall(toType))
        {
            toType = genActualType(toType);
        }

        return IntegralRange::ForType(toType);
    }

    // Cast from a GC type is the same as a cast from TYP_I_IMPL for our purposes.
    if (varTypeIsGC(fromType))
    {
        fromType = TYP_I_IMPL;
    }

    if (varTypeIsSmall(toType) || (genActualType(toType) == fromType))
    {
        return ForCastInput(cast);
    }

    // if we're upcasting and the cast op is a known non-negative - consider
    // this cast unsigned
    if (!fromUnsigned && (genTypeSize(toType) >= genTypeSize(fromType)))
    {
        fromUnsigned = cast->CastOp()->IsNeverNegative(compiler);
    }

    // CAST(uint/int <- ulong/long) - [INT_MIN..INT_MAX]
    // CAST(ulong/long <- uint)     - [0..UINT_MAX]
    // CAST(ulong/long <- int)      - [INT_MIN..INT_MAX]
    if (!cast->gtOverflow())
    {
        if ((fromType == TYP_INT) && fromUnsigned)
        {
            return {SymbolicIntegerValue::Zero, SymbolicIntegerValue::UIntMax};
        }

        return {SymbolicIntegerValue::IntMin, SymbolicIntegerValue::IntMax};
    }

    SymbolicIntegerValue lowerBound;
    SymbolicIntegerValue upperBound;
    switch (toType)
    {
        // CAST_OVF(uint <- ulong) - [INT_MIN..INT_MAX]
        // CAST_OVF(uint <- long)  - [INT_MIN..INT_MAX]
        case TYP_UINT:
            lowerBound = SymbolicIntegerValue::IntMin;
            upperBound = SymbolicIntegerValue::IntMax;
            break;

        // CAST_OVF(int <- ulong) - [0..INT_MAX]
        // CAST_OVF(int <- long)  - [INT_MIN..INT_MAX]
        case TYP_INT:
            lowerBound = fromUnsigned ? SymbolicIntegerValue::Zero : SymbolicIntegerValue::IntMin;
            upperBound = SymbolicIntegerValue::IntMax;
            break;

        // CAST_OVF(ulong <- uint) - [0..UINT_MAX]
        // CAST_OVF(ulong <- int)  - [0..INT_MAX]
        case TYP_ULONG:
            lowerBound = SymbolicIntegerValue::Zero;
            upperBound = fromUnsigned ? SymbolicIntegerValue::UIntMax : SymbolicIntegerValue::IntMax;
            break;

        // CAST_OVF(long <- uint) - [0..UINT_MAX]
        // CAST_OVF(long <- int)  - [INT_MIN..INT_MAX]
        case TYP_LONG:
            lowerBound = fromUnsigned ? SymbolicIntegerValue::Zero : SymbolicIntegerValue::IntMin;
            upperBound = fromUnsigned ? SymbolicIntegerValue::UIntMax : SymbolicIntegerValue::IntMax;
            break;

        default:
            unreached();
    }

    return {lowerBound, upperBound};
}

/* static */ IntegralRange IntegralRange::Union(IntegralRange range1, IntegralRange range2)
{
    return IntegralRange(min(range1.GetLowerBound(), range2.GetLowerBound()),
                         max(range1.GetUpperBound(), range2.GetUpperBound()));
}

#ifdef DEBUG
/* static */ void IntegralRange::Print(IntegralRange range)
{
    printf("[%lld", SymbolicToRealValue(range.m_lowerBound));
    printf("..");
    printf("%lld]", SymbolicToRealValue(range.m_upperBound));
}
#endif // DEBUG

//------------------------------------------------------------------------------
// GetAssertionDep: Retrieve the assertions on this local variable
//
// Arguments:
//    lclNum    - The local var id.
//    mustExist - If true, assert that the dependent assertions must exist.
//
// Return Value:
//    The dependent assertions (assertions using the value of the local var)
//    of the local var.
//

ASSERT_TP& Compiler::GetAssertionDep(unsigned lclNum, bool mustExist)
{
    JitExpandArray<ASSERT_TP>& dep = *optAssertionDep;
    if (dep[lclNum] == nullptr)
    {
        if (mustExist)
        {
            assert(!"No dependent assertions for local var");
        }
        dep[lclNum] = BitVecOps::MakeEmpty(apTraits);
    }
    return dep[lclNum];
}

/*****************************************************************************
 *
 *  Initialize the assertion prop bitset traits and the default bitsets.
 */

void Compiler::optAssertionTraitsInit(AssertionIndex assertionCount)
{
    apTraits = new (this, CMK_AssertionProp) BitVecTraits(assertionCount, this);
    apFull   = BitVecOps::MakeFull(apTraits);
}

/*****************************************************************************
 *
 *  Initialize the assertion prop tracking logic.
 */

void Compiler::optAssertionInit(bool isLocalProp)
{
    assert(NO_ASSERTION_INDEX == 0);
    const unsigned maxTrackedLocals = (unsigned)JitConfig.JitMaxLocalsToTrack();

    // We initialize differently for local prop / global prop
    //
    if (isLocalProp)
    {
        optLocalAssertionProp           = true;
        optCrossBlockLocalAssertionProp = true;

        // Disable via config
        //
        if (JitConfig.JitEnableCrossBlockLocalAssertionProp() == 0)
        {
            JITDUMP("Disabling cross-block assertion prop by config setting\n");
            optCrossBlockLocalAssertionProp = false;
        }

#ifdef DEBUG
        // Disable per method via range
        //
        static ConfigMethodRange s_range;
        s_range.EnsureInit(JitConfig.JitEnableCrossBlockLocalAssertionPropRange());
        if (!s_range.Contains(info.compMethodHash()))
        {
            JITDUMP("Disabling cross-block assertion prop by config range\n");
            optCrossBlockLocalAssertionProp = false;
        }
#endif

        // Disable if too many locals
        //
        // The typical number of local assertions is roughly proportional
        // to the number of locals. So when we have huge numbers of locals,
        // just do within-block local assertion prop.
        //
        if (lvaCount > maxTrackedLocals)
        {
            JITDUMP("Disabling cross-block assertion prop: too many locals\n");
            optCrossBlockLocalAssertionProp = false;
        }

        if (optCrossBlockLocalAssertionProp)
        {
            // We may need a fairly large table. Keep size a multiple of 64.
            // Empirical studies show about 1.16 asserions/ tracked local.
            //
            if (lvaTrackedCount < 24)
            {
                optMaxAssertionCount = 64;
            }
            else if (lvaTrackedCount < 64)
            {
                optMaxAssertionCount = 128;
            }
            else
            {
                optMaxAssertionCount = (AssertionIndex)min(maxTrackedLocals, ((3 * lvaTrackedCount / 128) + 1) * 64);
            }

            JITDUMP("Cross-block table size %u (for %u tracked locals)\n", optMaxAssertionCount, lvaTrackedCount);
        }
        else
        {
            // The assertion table will be reset for each block, so it can be smaller.
            //
            optMaxAssertionCount = 64;
        }

        // Local assertion prop keeps mappings from each local var to the assertions about that var.
        //
        optAssertionDep =
            new (this, CMK_AssertionProp) JitExpandArray<ASSERT_TP>(getAllocator(CMK_AssertionProp), max(1u, lvaCount));

        if (optCrossBlockLocalAssertionProp)
        {
            optComplementaryAssertionMap = new (this, CMK_AssertionProp)
                AssertionIndex[optMaxAssertionCount + 1](); // zero-inited (NO_ASSERTION_INDEX)
        }
    }
    else
    {
        // General assertion prop.
        //
        optLocalAssertionProp           = false;
        optCrossBlockLocalAssertionProp = false;

        // Heuristic for sizing the assertion table.
        //
        // The weighting of basicBlocks vs locals reflects their relative contribution observed empirically.
        // Validated against 1,115,046 compiled methods:
        //   - 94.6% of methods stay at the floor of 64 (only 1.9% actually need more).
        //   - Underpredicts for 481 methods (0.043%), with a worst-case deficit of 127.
        //   - Only 0.4% of methods hit the 256 cap.
        optMaxAssertionCount = (AssertionIndex)max(64, min(256, (int)(lvaTrackedCount + 3 * fgBBcount + 48) >> 2));

        optComplementaryAssertionMap = new (this, CMK_AssertionProp)
            AssertionIndex[optMaxAssertionCount + 1](); // zero-inited (NO_ASSERTION_INDEX)
    }

    optAssertionTabPrivate = new (this, CMK_AssertionProp) AssertionDsc[optMaxAssertionCount];
    optAssertionTraitsInit(optMaxAssertionCount);

    optAssertionCount      = 0;
    optAssertionOverflow   = 0;
    optAssertionPropagated = false;
    bbJtrueAssertionOut    = nullptr;
    optCanPropLclVar       = false;
    optCanPropEqual        = false;
    optCanPropNonNull      = false;
    optCanPropBndsChk      = false;
    optCanPropSubRange     = false;
}

#ifdef DEBUG
void Compiler::optPrintAssertion(const AssertionDsc& curAssertion, AssertionIndex assertionIndex /* = 0 */)
{
    // Print assertion index if provided
    if (assertionIndex > 0)
    {
        optPrintAssertionIndex(assertionIndex);
        printf(" ");
    }

    switch (curAssertion.GetOp1().GetKind())
    {
        case O1K_LCLVAR:
            if (optLocalAssertionProp)
            {
                printf("lclvar V%02u", curAssertion.GetOp1().GetLclNum());
            }
            else
            {
                printf("lclvar " FMT_VN "", curAssertion.GetOp1().GetVN());
            }
            break;

        case O1K_VN:
            printf("VN " FMT_VN "", curAssertion.GetOp1().GetVN());
            break;

        case O1K_EXACT_TYPE:
            printf("ExactType " FMT_VN "", curAssertion.GetOp1().GetVN());
            break;

        case O1K_SUBTYPE:
            printf("SubType " FMT_VN "", curAssertion.GetOp1().GetVN());
            break;

        default:
            unreached();
            break;
    }

    switch (curAssertion.GetKind())
    {
        case OAK_EQUAL:
            printf(" == ");
            break;

        case OAK_NOT_EQUAL:
            printf(" != ");
            break;

        case OAK_LT:
            printf(" < ");
            break;

        case OAK_LT_UN:
            printf(" u< ");
            break;

        case OAK_LE:
            printf(" <= ");
            break;

        case OAK_LE_UN:
            printf(" u<= ");
            break;

        case OAK_GT:
            printf(" > ");
            break;

        case OAK_GT_UN:
            printf(" u> ");
            break;

        case OAK_GE:
            printf(" >= ");
            break;

        case OAK_GE_UN:
            printf(" u>= ");
            break;

        case OAK_SUBRANGE:
            printf(" in ");
            break;

        default:
            unreached();
            break;
    }

    switch (curAssertion.GetOp2().GetKind())
    {
        case O2K_LCLVAR_COPY:
            printf("lclvar V%02u", curAssertion.GetOp2().GetLclNum());
            break;

        case O2K_CONST_INT:
            if (curAssertion.GetOp1().KindIs(O1K_EXACT_TYPE, O1K_SUBTYPE))
            {
                ssize_t iconVal = curAssertion.GetOp2().GetIntConstant();
                if (IsAot())
                {
                    printf("MT(%p)", dspPtr(iconVal));
                }
                else
                {
                    printf("MT(%s)", eeGetClassName(reinterpret_cast<CORINFO_CLASS_HANDLE>(iconVal)));
                }
            }
            else if (curAssertion.GetOp2().IsNullConstant())
            {
                printf("null");
            }
            else if (curAssertion.GetOp2().HasIconFlag())
            {
                printf("[%p]", dspPtr(curAssertion.GetOp2().GetIntConstant()));
            }
            else
            {
                printf("%lld", (int64_t)curAssertion.GetOp2().GetIntConstant());
            }
            break;

        case O2K_CONST_DOUBLE:
            if (FloatingPointUtils::isNegativeZero(curAssertion.GetOp2().GetDoubleConstant()))
            {
                printf("-0.0");
            }
            else
            {
                printf("%#lg", curAssertion.GetOp2().GetDoubleConstant());
            }
            break;

        case O2K_ZEROOBJ:
            printf("ZeroObj");
            break;

        case O2K_SUBRANGE:
            IntegralRange::Print(curAssertion.GetOp2().GetIntegralRange());
            break;

        case O2K_CHECKED_BOUND_ADD_CNS:
            printf("(Checked_Bnd_BinOp " FMT_VN " + %d)", curAssertion.GetOp2().GetCheckedBound(),
                   curAssertion.GetOp2().GetCheckedBoundConstant());
            break;

        default:
            unreached();
            break;
    }

    printf("\n");
}

void Compiler::optPrintAssertionIndex(AssertionIndex index)
{
    if (index == NO_ASSERTION_INDEX)
    {
        printf("#NA");
        return;
    }

    printf("#%02u", index);
}

void Compiler::optPrintAssertionIndices(ASSERT_TP assertions)
{
    if (BitVecOps::IsEmpty(apTraits, assertions))
    {
        optPrintAssertionIndex(NO_ASSERTION_INDEX);
        return;
    }

    BitVecOps::Iter iter(apTraits, assertions);
    unsigned        bitIndex = 0;
    if (iter.NextElem(&bitIndex))
    {
        optPrintAssertionIndex(static_cast<AssertionIndex>(bitIndex + 1));
        while (iter.NextElem(&bitIndex))
        {
            printf(" ");
            optPrintAssertionIndex(static_cast<AssertionIndex>(bitIndex + 1));
        }
    }
}
#endif // DEBUG

/* static */
void Compiler::optDumpAssertionIndices(const char* header, ASSERT_TP assertions, const char* footer /* = nullptr */)
{
#ifdef DEBUG
    Compiler* compiler = JitTls::GetCompiler();
    if (compiler->verbose)
    {
        printf(header);
        compiler->optPrintAssertionIndices(assertions);
        if (footer != nullptr)
        {
            printf(footer);
        }
    }
#endif // DEBUG
}

/* static */
void Compiler::optDumpAssertionIndices(ASSERT_TP assertions, const char* footer /* = nullptr */)
{
    optDumpAssertionIndices("", assertions, footer);
}

/******************************************************************************
 *
 * Helper to retrieve the "assertIndex" assertion. Note that assertIndex 0
 * is NO_ASSERTION_INDEX and "optAssertionCount" is the last valid index.
 *
 */
const Compiler::AssertionDsc& Compiler::optGetAssertion(AssertionIndex assertIndex) const
{
    assert(NO_ASSERTION_INDEX == 0);
    assert(assertIndex != NO_ASSERTION_INDEX);
    assert(assertIndex <= optAssertionCount);
    const AssertionDsc& assertion = optAssertionTabPrivate[assertIndex - 1];
#ifdef DEBUG
    optDebugCheckAssertion(assertion);
#endif

    return assertion;
}

ValueNum Compiler::optConservativeNormalVN(GenTree* tree)
{
    if (optLocalAssertionProp)
    {
        return ValueNumStore::NoVN;
    }

    assert(vnStore != nullptr);
    return vnStore->VNConservativeNormalValue(tree->gtVNPair);
}

//------------------------------------------------------------------------
// optCastConstantSmall: Cast a constant to a small type.
//
// Parameters:
//   iconVal - the integer constant
//   smallType - the small type to cast to
//
// Returns:
//   The cast constant after sign/zero extension.
//
ssize_t Compiler::optCastConstantSmall(ssize_t iconVal, var_types smallType)
{
    switch (smallType)
    {
        case TYP_BYTE:
            return int8_t(iconVal);

        case TYP_SHORT:
            return int16_t(iconVal);

        case TYP_USHORT:
            return uint16_t(iconVal);

        case TYP_UBYTE:
            return uint8_t(iconVal);

        default:
            assert(!"Unexpected type to truncate to");
            return iconVal;
    }
}

//------------------------------------------------------------------------
// optCreateAssertion: Create an (op1 assertionKind op2) assertion.
//
// Arguments:
//    op1    - the first assertion operand
//    op2    - the second assertion operand
//    equals - the assertion kind (equals / not equals)

// Return Value:
//    The new assertion index or NO_ASSERTION_INDEX if a new assertion
//    was not created.
//
// Notes:
//    Assertion creation may fail either because the provided assertion
//    operands aren't supported or because the assertion table is full.
//
AssertionIndex Compiler::optCreateAssertion(GenTree* op1, GenTree* op2, bool equals)
{
    assert(op1 != nullptr);

    if (op2 == nullptr)
    {
        // Must be an OAK_NOT_EQUAL assertion
        assert(!equals);

        // Set op1 to the instance pointer of the indirection
        op1 = op1->gtEffectiveVal();

        // TODO-Cleanup: Replace with gtPeelOffset with proper fgBigOffset check
        // It will produce a few regressions.
        ssize_t offset = 0;
        while (op1->OperIs(GT_ADD) && op1->TypeIs(TYP_BYREF))
        {
            if (op1->gtGetOp2()->IsCnsIntOrI())
            {
                offset += op1->gtGetOp2()->AsIntCon()->gtIconVal;
                op1 = op1->gtGetOp1()->gtEffectiveVal();
            }
            else if (op1->gtGetOp1()->IsCnsIntOrI())
            {
                offset += op1->gtGetOp1()->AsIntCon()->gtIconVal;
                op1 = op1->gtGetOp2()->gtEffectiveVal();
            }
            else
            {
                break;
            }
        }

        if (!fgIsBigOffset(offset) && op1->OperIs(GT_LCL_VAR) && !lvaVarAddrExposed(op1->AsLclVar()->GetLclNum()))
        {
            if (optLocalAssertionProp)
            {
                AssertionDsc assertion = AssertionDsc::CreateLclNonNullAssertion(this, op1->AsLclVar()->GetLclNum());
                return optAddAssertion(assertion);
            }

            ValueNum op1VN = optConservativeNormalVN(op1);
            if (op1VN == ValueNumStore::NoVN)
            {
                return NO_ASSERTION_INDEX;
            }
            AssertionDsc assertion = AssertionDsc::CreateVNNonNullAssertion(this, op1VN);
            return optAddAssertion(assertion);
        }
    }
    //
    // Are we making an assertion about a local variable?
    //
    else if (op1->OperIsScalarLocal())
    {
        unsigned const   lclNum = op1->AsLclVarCommon()->GetLclNum();
        LclVarDsc* const lclVar = lvaGetDesc(lclNum);

        // If the local variable has its address exposed then bail
        //
        if (lclVar->IsAddressExposed())
        {
            return NO_ASSERTION_INDEX;
        }

        /* Skip over a GT_COMMA node(s), if necessary */
        while (op2->OperIs(GT_COMMA))
        {
            op2 = op2->AsOp()->gtOp2;
        }

        switch (op2->OperGet())
        {
            //
            //  Constant Assertions
            //
            case GT_CNS_DBL:
            {
                double dblCns = op2->AsDblCon()->DconValue();
                if (FloatingPointUtils::isNaN(dblCns))
                {
                    return NO_ASSERTION_INDEX;
                }

                ValueNum op1VN = optConservativeNormalVN(op1);
                ValueNum op2VN = optConservativeNormalVN(op2);
                if (!optLocalAssertionProp && (op1VN == ValueNumStore::NoVN || op2VN == ValueNumStore::NoVN))
                {
                    // GlobalAP requires valid VNs.
                    return NO_ASSERTION_INDEX;
                }

                AssertionDsc dsc = AssertionDsc::CreateConstLclVarAssertion(this, lclNum, op1VN, dblCns, op2VN, equals);
                return optAddAssertion(dsc);
            }

            case GT_CNS_INT:
            {
                ValueNum op1VN = optConservativeNormalVN(op1);
                ValueNum op2VN = optConservativeNormalVN(op2);
                if (!optLocalAssertionProp && (op1VN == ValueNumStore::NoVN || op2VN == ValueNumStore::NoVN))
                {
                    return NO_ASSERTION_INDEX;
                }

                ssize_t iconVal = op2->AsIntCon()->IconValue();
                if (op1->TypeIs(TYP_STRUCT))
                {
                    assert(iconVal == 0);
                    AssertionDsc dsc =
                        AssertionDsc::CreateConstLclVarAssertion(this, lclNum, op1VN, O2K_ZEROOBJ, op2VN, equals);
                    return optAddAssertion(dsc);
                }

                if (varTypeIsSmall(lclVar))
                {
                    ssize_t truncatedIconVal = optCastConstantSmall(iconVal, lclVar->TypeGet());
                    if (!op1->OperIs(GT_STORE_LCL_VAR) && (truncatedIconVal != iconVal))
                    {
                        // This assertion would be saying that a small local is equal to a value
                        // outside its range. It means this block is unreachable. Avoid creating
                        // such impossible assertions which can hit assertions in other places.
                        return NO_ASSERTION_INDEX;
                    }

                    iconVal = truncatedIconVal;
                    if (!optLocalAssertionProp)
                    {
                        op2VN = vnStore->VNForIntCon(static_cast<int>(iconVal));
                    }
                }

                AssertionDsc dsc =
                    AssertionDsc::CreateConstLclVarAssertion(this, lclNum, op1VN, iconVal, op2VN, equals,
                                                             op2->GetIconHandleFlag(), op2->AsIntCon()->gtFieldSeq);
                return optAddAssertion(dsc);
            }

            case GT_LCL_VAR:
            {
                if (!optLocalAssertionProp)
                {
                    // O2K_LCLVAR_COPY is local assertion prop only
                    return NO_ASSERTION_INDEX;
                }

                unsigned   lclNum2 = op2->AsLclVarCommon()->GetLclNum();
                LclVarDsc* lclVar2 = lvaGetDesc(lclNum2);

                // If the two locals are the same then bail
                if (lclNum == lclNum2)
                {
                    return NO_ASSERTION_INDEX;
                }

                // If the types are different then bail */
                if (lclVar->lvType != lclVar2->lvType)
                {
                    return NO_ASSERTION_INDEX;
                }

                // If we're making a copy of a "normalize on load" lclvar then the destination
                // has to be "normalize on load" as well, otherwise we risk skipping normalization.
                if (lclVar2->lvNormalizeOnLoad() && !lclVar->lvNormalizeOnLoad())
                {
                    return NO_ASSERTION_INDEX;
                }

                //  If the local variable has its address exposed then bail
                if (lclVar2->IsAddressExposed())
                {
                    return NO_ASSERTION_INDEX;
                }

                // We process locals when we see the LCL_VAR node instead
                // of at its actual use point (its parent). That opens us
                // up to problems in a case like the following, assuming we
                // allowed creating an assertion like V10 = V35:
                //
                // └──▌  ADD       int
                //    ├──▌  LCL_VAR   int    V10 tmp6        -> copy propagated to [V35 tmp31]
                //    └──▌  COMMA     int
                //       ├──▌  STORE_LCL_VAR int    V35 tmp31
                //       │  └──▌  LCL_FLD   int    V03 loc1         [+4]
                if (lclVar2->lvRedefinedInEmbeddedStatement)
                {
                    return NO_ASSERTION_INDEX;
                }

                // Ok everything has been set and the assertion looks good
                AssertionDsc assertion = AssertionDsc::CreateLclvarCopy(this, lclNum, lclNum2, equals);
                return optAddAssertion(assertion);
            }

            case GT_CALL:
            {
                if (optLocalAssertionProp)
                {
                    GenTreeCall* const call = op2->AsCall();
                    if (call->IsHelperCall() && s_helperCallProperties.NonNullReturn(call->GetHelperNum()))
                    {
                        AssertionDsc assertion = AssertionDsc::CreateLclNonNullAssertion(this, lclNum);
                        return optAddAssertion(assertion);
                    }
                }
                break;
            }

            default:
                break;
        }

        // Try and see if we can make a subrange assertion.
        if (optLocalAssertionProp && equals && varTypeIsIntegral(op2))
        {
            IntegralRange nodeRange = IntegralRange::ForNode(op2, this);
            IntegralRange typeRange = IntegralRange::ForType(genActualType(op2));
            assert(typeRange.Contains(nodeRange));

            if (!typeRange.Equals(nodeRange))
            {
                AssertionDsc assertion = AssertionDsc::CreateSubrange(this, lclNum, nodeRange);
                return optAddAssertion(assertion);
            }
        }
    }
    else
    {
        // Currently, O1K_VN serves as a backup for O1K_LCLVAR (where it's not a local),
        // but long term we should keep O1K_LCLVAR for local assertions only.
        if (!optLocalAssertionProp)
        {
            ValueNum op1VN = optConservativeNormalVN(op1);
            ValueNum op2VN = optConservativeNormalVN(op2);

            // For TP reasons, limited to 32-bit constants on the op2 side.
            if (op1VN != ValueNumStore::NoVN && op2VN != ValueNumStore::NoVN && vnStore->IsVNInt32Constant(op2VN) &&
                !vnStore->IsVNHandle(op2VN))
            {
                AssertionDsc assertion = AssertionDsc::CreateInt32ConstantVNAssertion(this, op1VN, op2VN, equals);
                return optAddAssertion(assertion);
            }
        }
    }
    return NO_ASSERTION_INDEX;
}

/*****************************************************************************
 *
 * If tree is a constant node holding an integral value, retrieve the value in
 * pConstant. If the method returns true, pConstant holds the appropriate
 * constant. Set "vnBased" to true to indicate local or global assertion prop.
 * "pFlags" indicates if the constant is a handle marked by GTF_ICON_HDL_MASK.
 */
bool Compiler::optIsTreeKnownIntValue(bool vnBased, GenTree* tree, ssize_t* pConstant, GenTreeFlags* pFlags)
{
    // Is Local assertion prop?
    if (!vnBased)
    {
        if (tree->OperIs(GT_CNS_INT))
        {
            *pConstant = tree->AsIntCon()->IconValue();
            *pFlags    = tree->GetIconHandleFlag();
            return true;
        }
        return false;
    }

    // Global assertion prop
    ValueNum vn = vnStore->VNConservativeNormalValue(tree->gtVNPair);
    if (!vnStore->IsVNConstant(vn))
    {
        return false;
    }

    // ValueNumber 'vn' indicates that this node evaluates to a constant

    var_types vnType = vnStore->TypeOfVN(vn);
    if (vnType == TYP_INT)
    {
        *pConstant = vnStore->ConstantValue<int>(vn);
        *pFlags    = vnStore->IsVNHandle(vn) ? vnStore->GetHandleFlags(vn) : GTF_EMPTY;
        return true;
    }
#ifdef TARGET_64BIT
    else if (vnType == TYP_LONG)
    {
        *pConstant = vnStore->ConstantValue<INT64>(vn);
        *pFlags    = vnStore->IsVNHandle(vn) ? vnStore->GetHandleFlags(vn) : GTF_EMPTY;
        return true;
    }
#endif

    return false;
}

/*****************************************************************************
 *
 *  Given an assertion add it to the assertion table
 *
 *  If it is already in the assertion table return the assertionIndex that
 *  we use to refer to this element.
 *  Otherwise add it to the assertion table and return the assertionIndex that
 *  we use to refer to this element.
 *  If we need to add to the table and the table is full return the value zero
 */
AssertionIndex Compiler::optAddAssertion(const AssertionDsc& newAssertion)
{
    bool canAddNewAssertions = optAssertionCount < optMaxAssertionCount;

    // See if we already have this assertion in the table.
    //
    // For local assertion prop we can speed things up by checking the dep vector.
    // Note we only need check the op1 vector; copies get indexed on both op1
    // and op2, so searching the first will find any existing match.
    //
    if (optLocalAssertionProp)
    {
        assert(newAssertion.GetOp1().KindIs(O1K_LCLVAR));

        unsigned        lclNum = newAssertion.GetOp1().GetLclNum();
        BitVecOps::Iter iter(apTraits, GetAssertionDep(lclNum));
        unsigned        bvIndex = 0;
        while (iter.NextElem(&bvIndex))
        {
            AssertionIndex const index        = GetAssertionIndex(bvIndex);
            const AssertionDsc&  curAssertion = optGetAssertion(index);

            if (curAssertion.Equals(newAssertion, /* vnBased */ false))
            {
                return index;
            }
        }
    }
    else
    {
        bool mayHaveDuplicates =
            optAssertionHasAssertionsForVN(newAssertion.GetOp1().GetVN(), /* addIfNotFound */ canAddNewAssertions);
        // We need to register op2.vn too, even if we know for sure there are no duplicates
        if (newAssertion.GetOp2().KindIs(O2K_CHECKED_BOUND_ADD_CNS))
        {
            mayHaveDuplicates |= optAssertionHasAssertionsForVN(newAssertion.GetOp2().GetCheckedBound(),
                                                                /* addIfNotFound */ canAddNewAssertions);

            // Additionally, check for the pattern of "VN + const == checkedBndVN" and register "VN" as well.
            ValueNum addOpVN;
            if (vnStore->IsVNBinFuncWithConst<int>(newAssertion.GetOp1().GetVN(), VNF_ADD, &addOpVN, nullptr))
            {
                mayHaveDuplicates |= optAssertionHasAssertionsForVN(addOpVN, /* addIfNotFound */ canAddNewAssertions);
            }
        }

        if (mayHaveDuplicates)
        {
            // For global prop we search the entire table.
            //
            // Check if exists already, so we can skip adding new one. Search backwards.
            for (AssertionIndex index = optAssertionCount; index >= 1; index--)
            {
                const AssertionDsc& curAssertion = optGetAssertion(index);
                if (curAssertion.Equals(newAssertion, /* vnBased */ true))
                {
                    return index;
                }
            }
        }
    }

    // Check if we are within max count.
    if (!canAddNewAssertions)
    {
        optAssertionOverflow++;
        return NO_ASSERTION_INDEX;
    }

    optAssertionTabPrivate[optAssertionCount] = newAssertion;
    optAssertionCount++;

#ifdef DEBUG
    if (verbose)
    {
        printf("GenTreeNode creates assertion:\n");
        gtDispTree(optAssertionPropCurrentTree, nullptr, nullptr, true);
        printf(optLocalAssertionProp ? "In " FMT_BB " New Local " : "In " FMT_BB " New Global ", compCurBB->bbNum);
        optPrintAssertion(newAssertion, optAssertionCount);
    }
#endif // DEBUG

    // Track the short-circuit criteria
    optCanPropLclVar |= newAssertion.CanPropLclVar();
    optCanPropEqual |= newAssertion.CanPropEqualOrNotEqual();
    optCanPropNonNull |= newAssertion.CanPropNonNull();
    optCanPropSubRange |= newAssertion.CanPropSubRange();
    optCanPropBndsChk |= newAssertion.CanPropBndsCheck();

    // Assertion mask bits are [index + 1].
    if (optLocalAssertionProp)
    {
        assert(newAssertion.GetOp1().KindIs(O1K_LCLVAR));

        // Mark the variables this index depends on
        unsigned lclNum = newAssertion.GetOp1().GetLclNum();
        BitVecOps::AddElemD(apTraits, GetAssertionDep(lclNum), optAssertionCount - 1);
        if (newAssertion.GetOp2().KindIs(O2K_LCLVAR_COPY))
        {
            lclNum = newAssertion.GetOp2().GetLclNum();
            BitVecOps::AddElemD(apTraits, GetAssertionDep(lclNum), optAssertionCount - 1);
        }
    }

#ifdef DEBUG
    optDebugCheckAssertions(optAssertionCount);
#endif
    return optAssertionCount;
}

//------------------------------------------------------------------------
// optAssertionHasAssertionsForVN: Check if we already have assertions for the given VN.
//    If "addIfNotFound" is true, add the VN to the map if it's not already there.
//
// Arguments:
//    vn            - the VN to check for
//    addIfNotFound - whether to add the VN to the map if it's not found
//
// Return Value:
//    true if we already have assertions for the given VN, false otherwise.
//
bool Compiler::optAssertionHasAssertionsForVN(ValueNum vn, bool addIfNotFound)
{
    assert(!optLocalAssertionProp);
    if (vn == ValueNumStore::NoVN)
    {
        assert(!addIfNotFound);
        return false;
    }

    if (addIfNotFound)
    {
        // Lazy initialize the map when we first need to add to it
        if (optAssertionVNsMap == nullptr)
        {
            optAssertionVNsMap = new (this, CMK_AssertionProp) VNSet(getAllocator(CMK_AssertionProp));
        }

        // Avoid double lookup by using the return value of LookupPointerOrAdd to
        // determine whether the VN was already in the map.
        bool* pValue = optAssertionVNsMap->LookupPointerOrAdd(vn, false);
        if (!*pValue)
        {
            *pValue = true;
            return false;
        }
        return true;
    }

    // Otherwise just do a normal lookup
    return (optAssertionVNsMap != nullptr) && optAssertionVNsMap->Lookup(vn);
}

#ifdef DEBUG
void Compiler::optDebugCheckAssertion(const AssertionDsc& assertion) const
{
    switch (assertion.GetOp1().GetKind())
    {
        case O1K_EXACT_TYPE:
        case O1K_SUBTYPE:
        case O1K_VN:
            assert(!optLocalAssertionProp);
            break;
        default:
            break;
    }

    switch (assertion.GetOp2().GetKind())
    {
        case O2K_SUBRANGE:
        case O2K_LCLVAR_COPY:
            assert(optLocalAssertionProp);
            break;

        case O2K_ZEROOBJ:
            // We only make these assertion for stores (not control flow).
            assert(assertion.KindIs(OAK_EQUAL));
            // We use "optLocalAssertionIsEqualOrNotEqual" to find these.
            break;

        case O2K_CONST_DOUBLE:
            assert(!FloatingPointUtils::isNaN(assertion.GetOp2().GetDoubleConstant()));
            break;

        default:
            // for all other 'assertion.GetOp2().GetKind()' values we don't check anything
            break;
    }
}

/*****************************************************************************
 *
 *  Verify that assertion prop related assumptions are valid. If "index"
 *  is 0 (i.e., NO_ASSERTION_INDEX) then verify all assertions in the table.
 *  If "index" is between 1 and optAssertionCount, then verify the assertion
 *  desc corresponding to "index."
 */
void Compiler::optDebugCheckAssertions(AssertionIndex index)
{
    AssertionIndex start = (index == NO_ASSERTION_INDEX) ? 1 : index;
    AssertionIndex end   = (index == NO_ASSERTION_INDEX) ? optAssertionCount : index;
    for (AssertionIndex ind = start; ind <= end; ++ind)
    {
        const AssertionDsc& assertion = optGetAssertion(ind);
        optDebugCheckAssertion(assertion);
    }
}
#endif

//------------------------------------------------------------------------
// optCreateComplementaryAssertion: Create an assertion that is the complementary
//     of the specified assertion.
//
// Arguments:
//    assertionIndex - the index of the assertion
//
// Notes:
//    The created complementary assertion is associated with the original
//    assertion such that it can be found by optFindComplementary.
//
void Compiler::optCreateComplementaryAssertion(AssertionIndex assertionIndex)
{
    if (assertionIndex == NO_ASSERTION_INDEX)
    {
        return;
    }

    const AssertionDsc& candidateAssertion = optGetAssertion(assertionIndex);
    if (candidateAssertion.KindIs(OAK_EQUAL))
    {
        // Don't create useless OAK_NOT_EQUAL assertions

        if (candidateAssertion.GetOp1().KindIs(O1K_LCLVAR, O1K_VN))
        {
            // "LCLVAR != CNS" is not a useful assertion (unless CNS is 0/1)
            if (candidateAssertion.GetOp2().KindIs(O2K_CONST_INT) &&
                (candidateAssertion.GetOp2().GetIntConstant() != 0) &&
                (candidateAssertion.GetOp2().GetIntConstant() != 1))
            {
                return;
            }

            // "LCLVAR != LCLVAR_COPY"
            if (candidateAssertion.GetOp2().KindIs(O2K_LCLVAR_COPY))
            {
                return;
            }
        }

        // "Object is not Class" is also not a useful assertion (at least for now)
        if (candidateAssertion.GetOp1().KindIs(O1K_EXACT_TYPE, O1K_SUBTYPE))
        {
            return;
        }
        AssertionDsc reversed = candidateAssertion.Reverse();
        optMapComplementary(optAddAssertion(reversed), assertionIndex);
    }
    else if (candidateAssertion.KindIs(OAK_LT_UN, OAK_LE_UN) &&
             candidateAssertion.GetOp2().KindIs(O2K_CHECKED_BOUND_ADD_CNS))
    {
        // Assertions such as "X > checkedBndVN" aren't very useful.
        return;
    }
    else if (AssertionDsc::IsReversible(candidateAssertion.GetKind()))
    {
        AssertionDsc reversed = candidateAssertion.Reverse();
        optMapComplementary(optAddAssertion(reversed), assertionIndex);
    }
}

//------------------------------------------------------------------------
// optCreateJtrueAssertions: Create assertions about a JTRUE's relop operands.
//
// Arguments:
//    op1    - the first assertion operand
//    op2    - the second assertion operand
//    equals - the assertion kind (equals / not equals)
//
// Return Value:
//    The new assertion index or NO_ASSERTION_INDEX if a new assertion
//    was not created.
//
// Notes:
//    Assertion creation may fail either because the provided assertion
//    operands aren't supported or because the assertion table is full.
//    If an assertion is created successfully then an attempt is made to also
//    create a second, complementary assertion. This may too fail, for the
//    same reasons as the first one.
//
AssertionIndex Compiler::optCreateJtrueAssertions(GenTree* op1, GenTree* op2, bool equals)
{
    AssertionIndex assertionIndex = optCreateAssertion(op1, op2, equals);
    // Don't bother if we don't have an assertion on the JTrue False path. Current implementation
    // allows for a complementary only if there is an assertion on the False path (tree->HasAssertion()).
    if (assertionIndex != NO_ASSERTION_INDEX)
    {
        optCreateComplementaryAssertion(assertionIndex);
    }
    return assertionIndex;
}

AssertionInfo Compiler::optCreateJTrueBoundsAssertion(GenTree* tree)
{
    // These assertions are VN based, so not relevant for local prop
    //
    if (optLocalAssertionProp)
    {
        return NO_ASSERTION_INDEX;
    }

    GenTree* relop = tree->gtGetOp1();
    if (!relop->OperIsCompare())
    {
        return NO_ASSERTION_INDEX;
    }

    ValueNum  relopVN = optConservativeNormalVN(relop);
    VNFuncApp relopFuncApp;
    if (!vnStore->GetVNFunc(relopVN, &relopFuncApp))
    {
        // We're expecting a relop here
        return NO_ASSERTION_INDEX;
    }

    bool isUnsignedRelop;
    if (relopFuncApp.FuncIs(VNF_LE, VNF_LT, VNF_GE, VNF_GT))
    {
        isUnsignedRelop = false;
    }
    else if (relopFuncApp.FuncIs(VNF_LE_UN, VNF_LT_UN, VNF_GE_UN, VNF_GT_UN))
    {
        isUnsignedRelop = true;
    }
    else
    {
        // Not a relop we're interested in.
        // Assertions for NE/EQ are handled elsewhere.
        return NO_ASSERTION_INDEX;
    }

    VNFunc   relopFunc = relopFuncApp.m_func;
    ValueNum op1VN     = relopFuncApp.m_args[0];
    ValueNum op2VN     = relopFuncApp.m_args[1];

    if ((genActualType(vnStore->TypeOfVN(op1VN)) != TYP_INT) || (genActualType(vnStore->TypeOfVN(op2VN)) != TYP_INT))
    {
        // For now, we don't have consumers for assertions derived from non-int32 comparisons
        return NO_ASSERTION_INDEX;
    }

    // "CheckedBnd <relop> X"
    if (!isUnsignedRelop && vnStore->IsVNCheckedBound(op1VN))
    {
        // Move the checked bound to the right side for simplicity
        relopFunc          = ValueNumStore::SwapRelop(relopFunc);
        AssertionDsc   dsc = AssertionDsc::CreateCompareCheckedBound(this, relopFunc, op2VN, op1VN, 0);
        AssertionIndex idx = optAddAssertion(dsc);
        optCreateComplementaryAssertion(idx);
        return idx;
    }

    // "X <relop> CheckedBnd"
    if (!isUnsignedRelop && vnStore->IsVNCheckedBound(op2VN))
    {
        AssertionDsc   dsc = AssertionDsc::CreateCompareCheckedBound(this, relopFunc, op1VN, op2VN, 0);
        AssertionIndex idx = optAddAssertion(dsc);
        optCreateComplementaryAssertion(idx);
        return idx;
    }

    // "(CheckedBnd + CNS) <relop> X"
    ValueNum checkedBnd;
    int      checkedBndCns;
    if (!isUnsignedRelop && vnStore->IsVNCheckedBoundAddConst(op1VN, &checkedBnd, &checkedBndCns))
    {
        // Move the (CheckedBnd + CNS) part to the right side for simplicity
        relopFunc          = ValueNumStore::SwapRelop(relopFunc);
        AssertionDsc   dsc = AssertionDsc::CreateCompareCheckedBound(this, relopFunc, op2VN, checkedBnd, checkedBndCns);
        AssertionIndex idx = optAddAssertion(dsc);
        optCreateComplementaryAssertion(idx);
        return idx;
    }

    // "X <relop> (CheckedBnd + CNS)"
    if (!isUnsignedRelop && vnStore->IsVNCheckedBoundAddConst(op2VN, &checkedBnd, &checkedBndCns))
    {
        AssertionDsc   dsc = AssertionDsc::CreateCompareCheckedBound(this, relopFunc, op1VN, checkedBnd, checkedBndCns);
        AssertionIndex idx = optAddAssertion(dsc);
        optCreateComplementaryAssertion(idx);
        return idx;
    }

    // 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 appropriate edge)
    ValueNumStore::UnsignedCompareCheckedBoundInfo unsignedCompareBnd;
    if (vnStore->IsVNUnsignedCompareCheckedBound(relopVN, &unsignedCompareBnd))
    {
        ValueNum idxVN = vnStore->VNNormalValue(unsignedCompareBnd.vnIdx);
        ValueNum lenVN = vnStore->VNNormalValue(unsignedCompareBnd.vnBound);

        AssertionDsc   dsc   = AssertionDsc::CreateNoThrowArrBnd(this, idxVN, lenVN);
        AssertionIndex index = optAddAssertion(dsc);
        if (unsignedCompareBnd.cmpOper == VNF_GE_UN)
        {
            // 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;
    }

    // Create "X relop CNS" assertion (both signed and unsigned relops)
    // Ignore non-positive constants for unsigned relops as they don't add any useful information.
    ssize_t cns;
    if (vnStore->IsVNIntegralConstant(op1VN, &cns) && (!isUnsignedRelop || (cns > 0)))
    {
        relopFunc          = ValueNumStore::SwapRelop(relopFunc);
        AssertionDsc   dsc = AssertionDsc::CreateConstantBound(this, relopFunc, op2VN, op1VN);
        AssertionIndex idx = optAddAssertion(dsc);
        optCreateComplementaryAssertion(idx);
        return idx;
    }

    if (vnStore->IsVNIntegralConstant(op2VN, &cns) && (!isUnsignedRelop || (cns > 0)))
    {
        AssertionDsc   dsc = AssertionDsc::CreateConstantBound(this, relopFunc, op1VN, op2VN);
        AssertionIndex idx = optAddAssertion(dsc);
        optCreateComplementaryAssertion(idx);
        return idx;
    }

    return NO_ASSERTION_INDEX;
}

/*****************************************************************************
 *
 *  Compute assertions for the JTrue node.
 */
AssertionInfo Compiler::optAssertionGenJtrue(GenTree* tree)
{
    GenTree* const relop = tree->AsOp()->gtOp1;
    if (!relop->OperIsCompare())
    {
        return NO_ASSERTION_INDEX;
    }

    AssertionInfo info = optCreateJTrueBoundsAssertion(tree);
    if (info.HasAssertion())
    {
        return info;
    }

    if (optLocalAssertionProp && !optCrossBlockLocalAssertionProp)
    {
        return NO_ASSERTION_INDEX;
    }

    // Find assertion kind.
    bool equals;
    switch (relop->gtOper)
    {
        case GT_EQ:
            equals = true;
            break;
        case GT_NE:
            equals = false;
            break;
        default:
            // TODO-CQ: add other relop operands. Disabled for now to measure perf
            // and not occupy assertion table slots. We'll add them when used.
            return NO_ASSERTION_INDEX;
    }

    // Look through any CSEs so we see the actual trees providing values, if possible.
    // This is important for exact type assertions, which need to see the GT_IND.
    //
    GenTree* op1 = relop->AsOp()->gtOp1->gtCommaStoreVal();
    GenTree* op2 = relop->AsOp()->gtOp2->gtCommaStoreVal();

    // Avoid creating local assertions for float types.
    //
    if (optLocalAssertionProp && varTypeIsFloating(op1))
    {
        return NO_ASSERTION_INDEX;
    }

    // See if we have IND(obj) ==/!= TypeHandle
    //
    if (!optLocalAssertionProp && op1->OperIs(GT_IND) && op1->gtGetOp1()->TypeIs(TYP_REF))
    {
        ValueNum objVN     = optConservativeNormalVN(op1->gtGetOp1());
        ValueNum typeHndVN = optConservativeNormalVN(op2);

        if ((objVN != ValueNumStore::NoVN) && vnStore->IsVNTypeHandle(typeHndVN))
        {
            AssertionDsc   dsc   = AssertionDsc::CreateSubtype(this, objVN, typeHndVN, /*exact*/ true);
            AssertionIndex index = optAddAssertion(dsc);

            // We don't need to create a complementary assertion here. We're only interested
            // in the assertion that the object is of a certain type. The opposite assertion
            // (that the object is not of a certain type) is not useful (at least not yet).
            //
            // So if we have "if (obj->pMT != CNS) then create the assertion for the "else" edge.
            if (relop->OperIs(GT_NE))
            {
                return AssertionInfo::ForNextEdge(index);
            }
            return index;
        }
    }

    // Check for op1 or op2 to be lcl var and if so, keep it in op1.
    if (!op1->OperIs(GT_LCL_VAR) && op2->OperIs(GT_LCL_VAR))
    {
        std::swap(op1, op2);
    }

    // If op1 is lcl and op2 is const or lcl, create assertion.
    if (op1->OperIs(GT_LCL_VAR) && (op2->OperIsConst() || op2->OperIs(GT_LCL_VAR))) // Fix for Dev10 851483
    {
        // Watch out for cases where long local(s) are implicitly truncated.
        //
        LclVarDsc* const lcl1Dsc = lvaGetDesc(op1->AsLclVarCommon());
        if (lcl1Dsc->TypeIs(TYP_LONG) && !op1->TypeIs(TYP_LONG))
        {
            return NO_ASSERTION_INDEX;
        }
        if (op2->OperIs(GT_LCL_VAR))
        {
            LclVarDsc* const lcl2Dsc = lvaGetDesc(op2->AsLclVarCommon());
            if (lcl2Dsc->TypeIs(TYP_LONG) && !op2->TypeIs(TYP_LONG))
            {
                return NO_ASSERTION_INDEX;
            }
        }

        return optCreateJtrueAssertions(op1, op2, equals);
    }
    else if (!optLocalAssertionProp)
    {
        ValueNum op1VN = vnStore->VNConservativeNormalValue(op1->gtVNPair);
        ValueNum op2VN = vnStore->VNConservativeNormalValue(op2->gtVNPair);

        if (vnStore->IsVNCheckedBound(op1VN) && vnStore->IsVNInt32Constant(op2VN))
        {
            assert(relop->OperIs(GT_EQ, GT_NE));
            return optCreateJtrueAssertions(op1, op2, equals);
        }
    }

    // Check op1 and op2 for an indirection of a GT_LCL_VAR and keep it in op1.
    if ((!op1->OperIs(GT_IND) || !op1->AsOp()->gtOp1->OperIs(GT_LCL_VAR)) &&
        (op2->OperIs(GT_IND) && op2->AsOp()->gtOp1->OperIs(GT_LCL_VAR)))
    {
        std::swap(op1, op2);
    }
    // If op1 is ind, then extract op1's oper.
    if (op1->OperIs(GT_IND) && op1->AsOp()->gtOp1->OperIs(GT_LCL_VAR))
    {
        return optCreateJtrueAssertions(op1, op2, equals);
    }

    // Look for a call to an IsInstanceOf helper compared to a nullptr
    if (!op2->OperIs(GT_CNS_INT) && op1->OperIs(GT_CNS_INT))
    {
        std::swap(op1, op2);
    }
    // Validate op1 and op2
    if (!op1->OperIs(GT_CALL) || !op1->AsCall()->IsHelperCall() || !op1->TypeIs(TYP_REF) || // op1
        !op2->OperIs(GT_CNS_INT) || (op2->AsIntCon()->gtIconVal != 0))                      // op2
    {
        return NO_ASSERTION_INDEX;
    }

    if (optLocalAssertionProp)
    {
        // O1K_SUBTYPE is Global Assertion Prop only
        return NO_ASSERTION_INDEX;
    }

    GenTreeCall* const call = op1->AsCall();

    // Note CORINFO_HELP_READYTORUN_ISINSTANCEOF does not have the same argument pattern.
    // In particular, it is not possible to deduce what class is being tested from its args.
    //
    // Also note The CASTCLASS helpers won't appear in predicates as they throw on failure.
    // So the helper list here is smaller than the one in optAssertionProp_Call.
    //
    CorInfoHelpFunc helper = eeGetHelperNum(call->gtCallMethHnd);
    if ((helper == CORINFO_HELP_ISINSTANCEOFINTERFACE) || (helper == CORINFO_HELP_ISINSTANCEOFARRAY) ||
        (helper == CORINFO_HELP_ISINSTANCEOFCLASS) || (helper == CORINFO_HELP_ISINSTANCEOFANY))
    {
        GenTree* objectNode      = call->gtArgs.GetUserArgByIndex(1)->GetNode();
        GenTree* methodTableNode = call->gtArgs.GetUserArgByIndex(0)->GetNode();

        // objectNode can be TYP_I_IMPL in case if it's a constant handle
        // (e.g. a string literal from frozen segments)
        //
        assert(objectNode->TypeIs(TYP_REF, TYP_I_IMPL));
        assert(methodTableNode->TypeIs(TYP_I_IMPL));

        ValueNum objVN     = optConservativeNormalVN(objectNode);
        ValueNum typeHndVN = optConservativeNormalVN(methodTableNode);

        if ((objVN != ValueNumStore::NoVN) && vnStore->IsVNTypeHandle(typeHndVN))
        {
            AssertionDsc   dsc   = AssertionDsc::CreateSubtype(this, objVN, typeHndVN, /*exact*/ false);
            AssertionIndex index = optAddAssertion(dsc);

            // We don't need to create a complementary assertion here. We're only interested
            // in the assertion that the object is of a certain type. The opposite assertion
            // (that the object is not of a certain type) is not useful (at least not yet).
            //
            // So if we have "if (ISINST(obj, pMT) == null) then create the assertion for the "else" edge.
            //
            if (relop->OperIs(GT_EQ))
            {
                return AssertionInfo::ForNextEdge(index);
            }
            return index;
        }
    }

    return NO_ASSERTION_INDEX;
}

/*****************************************************************************
 *
 *  If this node creates an assertion then assign an index to the assertion
 *  by adding it to the lookup table, if necessary.
 */
void Compiler::optAssertionGen(GenTree* tree)
{
    tree->ClearAssertion();

    // If there are QMARKs in the IR, we won't generate assertions
    // for conditionally executed code.
    //
    if (optLocalAssertionProp && ((tree->gtFlags & GTF_COLON_COND) != 0))
    {
        return;
    }

#ifdef DEBUG
    optAssertionPropCurrentTree = tree;
#endif

    AssertionInfo assertionInfo;
    switch (tree->OperGet())
    {
        case GT_STORE_LCL_VAR:
            // VN takes care of non local assertions for data flow.
            if (optLocalAssertionProp)
            {
                assertionInfo = optCreateAssertion(tree, tree->AsLclVar()->Data(), /*equals*/ true);
            }
            break;

        case GT_LCL_VAR:
            if (!optLocalAssertionProp && tree->TypeIs(TYP_INT) &&
                lvaGetDesc(tree->AsLclVarCommon())->IsNeverNegative())
            {
                // Create "LCL_VAR >= 0" assertion for int local variables that are never negative.
                // Typically, it's Span.Length.
                ValueNum opVN = optConservativeNormalVN(tree);
                if (opVN != ValueNumStore::NoVN)
                {
                    assertionInfo = optAddAssertion(
                        AssertionDsc::CreateConstantBound(this, VNF_GE, opVN, vnStore->VNZeroForType(TYP_INT)));
                }
            }
            break;

        case GT_IND:
        case GT_XAND:
        case GT_XORR:
        case GT_XADD:
        case GT_XCHG:
        case GT_CMPXCHG:
        case GT_BLK:
        case GT_STOREIND:
        case GT_STORE_BLK:
        case GT_NULLCHECK:
        case GT_ARR_LENGTH:
        case GT_MDARR_LENGTH:
        case GT_MDARR_LOWER_BOUND:
            // These indirs (esp. GT_IND and GT_STOREIND) are the most popular sources of assertions.
            if (tree->IndirMayFault(this))
            {
                assertionInfo = optCreateAssertion(tree->GetIndirOrArrMetaDataAddr(), nullptr, /*equals*/ false);
            }
            break;

        case GT_INTRINSIC:
            if (tree->AsIntrinsic()->gtIntrinsicName == NI_System_Object_GetType)
            {
                assertionInfo = optCreateAssertion(tree->AsIntrinsic()->gtGetOp1(), nullptr, /*equals*/ false);
            }
            break;

        case GT_BOUNDS_CHECK:
            if (!optLocalAssertionProp)
            {
                GenTree* arrLenNode = tree->AsBoundsChk()->GetArrayLength();
                ValueNum idxVN      = optConservativeNormalVN(tree->AsBoundsChk()->GetIndex());
                ValueNum lenVN      = optConservativeNormalVN(arrLenNode);
                if ((idxVN == ValueNumStore::NoVN) || (lenVN == ValueNumStore::NoVN))
                {
                    assertionInfo = NO_ASSERTION_INDEX;
                }
                else
                {
                    // GT_BOUNDS_CHECK node provides the following contract:
                    // * idxVN < lenVN
                    // * lenVN is non-negative
                    assertionInfo = optAddAssertion(AssertionDsc::CreateNoThrowArrBnd(this, idxVN, lenVN));
                }
            }
            break;

        case GT_ARR_ELEM:
            // An array element reference can create a non-null assertion
            assertionInfo = optCreateAssertion(tree->AsArrElem()->gtArrObj, nullptr, /*equals*/ false);
            break;

        case GT_CALL:
        {
            // A virtual call can create a non-null assertion. We transform some virtual calls into non-virtual calls
            // with a GTF_CALL_NULLCHECK flag set.
            // Ignore tail calls because they have 'this` pointer in the regular arg list and an implicit null check.
            GenTreeCall* const call = tree->AsCall();
            if (call->NeedsNullCheck() || (call->IsVirtual() && !call->IsTailCall()))
            {
                //  Retrieve the 'this' arg.
                GenTree* thisArg = call->gtArgs.GetThisArg()->GetNode();
                assert(thisArg != nullptr);
                assertionInfo = optCreateAssertion(thisArg, nullptr, /*equals*/ false);
            }
            else if (!optLocalAssertionProp)
            {
                // Array allocation creates an assertion that the length argument is non-negative.
                //
                // var arr = new int[n]; - creates n >= 0 assertion
                //
                GenTree* lenArg = getArrayLengthFromAllocation(call);
                if (lenArg != nullptr)
                {
                    ValueNum lenVN = vnStore->VNIgnoreIntToLongCast(optConservativeNormalVN(lenArg));
                    if ((lenVN != ValueNumStore::NoVN) && !vnStore->IsVNConstant(lenVN) &&
                        (vnStore->TypeOfVN(lenVN) == TYP_INT))
                    {
                        ValueNum zeroVN = vnStore->VNZeroForType(TYP_INT);
                        assertionInfo = optAddAssertion(AssertionDsc::CreateConstantBound(this, VNF_GE, lenVN, zeroVN));
                        break;
                    }
                }

                // CORINFO_HELP_ARRADDR_ST(arrRef, idx, value) creates an assertion that "idx" is within the bounds of
                // "arrRef" array
                //
                // arr[idx] = value; - creates idx is within bounds of arr assertion
                //
                CorInfoHelpFunc helperId = eeGetHelperNum(call->gtCallMethHnd);
                if ((helperId == CORINFO_HELP_ARRADDR_ST) || (helperId == CORINFO_HELP_LDELEMA_REF))
                {
                    assert(call->gtArgs.CountUserArgs() == 3);
                    GenTree* arrRef = call->gtArgs.GetUserArgByIndex(0)->GetNode();
                    GenTree* idx    = call->gtArgs.GetUserArgByIndex(1)->GetNode();

                    ValueNum idxVN = vnStore->VNIgnoreIntToLongCast(optConservativeNormalVN(idx));
                    if ((idxVN != ValueNumStore::NoVN) && (vnStore->TypeOfVN(idxVN) == TYP_INT))
                    {
                        ValueNum arrRefVN = optConservativeNormalVN(arrRef);
                        if (arrRefVN != ValueNumStore::NoVN)
                        {
                            // Compose a VN_ARR_LENGTH VN for the array reference and use it
                            // to create a bounds check assertion on the index.
                            ValueNum lenVN = vnStore->VNForFunc(TYP_INT, VNF_ARR_LENGTH, arrRefVN);
                            assertionInfo  = optAddAssertion(AssertionDsc::CreateNoThrowArrBnd(this, idxVN, lenVN));
                            break;
                        }
                    }
                }
            }
        }
        break;

        case GT_DIV:
        case GT_UDIV:
        case GT_MOD:
        case GT_UMOD:
            if (!optLocalAssertionProp)
            {
                // For division/modulo, we can create an assertion that the divisor is not zero
                //
                // c = a / b; - creates b != 0 assertion
                //
                ValueNum divisorVN = optConservativeNormalVN(tree->AsOp()->gtGetOp2());
                if ((divisorVN != ValueNumStore::NoVN) && !vnStore->IsVNConstant(divisorVN))
                {
                    var_types divisorType = vnStore->TypeOfVN(divisorVN);
                    if (varTypeIsIntegral(divisorType))
                    {
                        ValueNum zeroVN = vnStore->VNZeroForType(divisorType);
                        assertionInfo =
                            optAddAssertion(AssertionDsc::CreateConstantBound(this, VNF_NE, divisorVN, zeroVN));
                    }
                }
            }
            break;

        case GT_JTRUE:
            assertionInfo = optAssertionGenJtrue(tree);
            break;

        default:
            // All other gtOper node kinds, leave 'assertionIndex' = NO_ASSERTION_INDEX
            break;
    }

    if (assertionInfo.HasAssertion())
    {
        tree->SetAssertionInfo(assertionInfo);
    }
}

/*****************************************************************************
 *
 * Maps a complementary assertion to its original assertion so it can be
 * retrieved faster.
 */
void Compiler::optMapComplementary(AssertionIndex assertionIndex, AssertionIndex index)
{
    if (assertionIndex == NO_ASSERTION_INDEX || index == NO_ASSERTION_INDEX)
    {
        return;
    }

    assert(assertionIndex <= optMaxAssertionCount);
    assert(index <= optMaxAssertionCount);

    optComplementaryAssertionMap[assertionIndex] = index;
    optComplementaryAssertionMap[index]          = assertionIndex;
}

/*****************************************************************************
 *
 *  Given an assertion index, return the assertion index of the complementary
 *  assertion or 0 if one does not exist.
 */
AssertionIndex Compiler::optFindComplementary(AssertionIndex assertIndex)
{
    if (assertIndex == NO_ASSERTION_INDEX)
    {
        return NO_ASSERTION_INDEX;
    }
    const AssertionDsc& inputAssertion = optGetAssertion(assertIndex);

    // Must be an equal or not equal assertion.
    if (!AssertionDsc::IsReversible(inputAssertion.GetKind()))
    {
        return NO_ASSERTION_INDEX;
    }

    AssertionIndex index = optComplementaryAssertionMap[assertIndex];
    if (index != NO_ASSERTION_INDEX && index <= optAssertionCount)
    {
        return index;
    }

    for (AssertionIndex index = 1; index <= optAssertionCount; ++index)
    {
        // Make sure assertion kinds are complementary and op1, op2 kinds match.
        const AssertionDsc& curAssertion = optGetAssertion(index);
        if (curAssertion.Complementary(inputAssertion, !optLocalAssertionProp))
        {
            optMapComplementary(assertIndex, index);
            return index;
        }
    }
    return NO_ASSERTION_INDEX;
}

//------------------------------------------------------------------------
// optAssertionIsSubrange: Find a subrange assertion for the given range and tree.
//
// This function will return the index of the first assertion in "assertions"
// which claims that the value of "tree" is within the bounds of the provided
// "range" (i. e. "range.Contains(assertedRange)").
//
// Arguments:
//    tree       - the tree for which to find the assertion
//    range      - range the subrange of which to look for
//    assertions - the set of assertions
//
// Return Value:
//    Index of the found assertion, NO_ASSERTION_INDEX otherwise.
//
AssertionIndex Compiler::optAssertionIsSubrange(GenTree* tree, IntegralRange range, ASSERT_VALARG_TP assertions)
{
    assert(optLocalAssertionProp); // Subrange assertions are local only.
    if (!optCanPropSubRange)
    {
        return NO_ASSERTION_INDEX;
    }

    BitVecOps::Iter iter(apTraits, assertions);
    unsigned        bvIndex = 0;
    while (iter.NextElem(&bvIndex))
    {
        AssertionIndex const index        = GetAssertionIndex(bvIndex);
        const AssertionDsc&  curAssertion = optGetAssertion(index);
        if (curAssertion.CanPropSubRange())
        {
            if (curAssertion.GetOp1().GetLclNum() != tree->AsLclVarCommon()->GetLclNum())
            {
                continue;
            }

            if (range.Contains(curAssertion.GetOp2().GetIntegralRange()))
            {
                return index;
            }
        }
    }

    return NO_ASSERTION_INDEX;
}

/**********************************************************************************
 *
 * Given a "tree" that is usually arg1 of a isinst/cast kind of GT_CALL (a class
 * handle), and "methodTableArg" which is a const int (a class handle), then search
 * if there is an assertion in "assertions", that asserts the equality of the two
 * class handles and then returns the index of the assertion. If one such assertion
 * could not be found, then it returns NO_ASSERTION_INDEX.
 *
 */
AssertionIndex Compiler::optAssertionIsSubtype(GenTree* tree, GenTree* methodTableArg, ASSERT_VALARG_TP assertions)
{
    BitVecOps::Iter iter(apTraits, assertions);
    unsigned        bvIndex = 0;
    while (iter.NextElem(&bvIndex))
    {
        AssertionIndex const index        = GetAssertionIndex(bvIndex);
        const AssertionDsc&  curAssertion = optGetAssertion(index);
        if (!curAssertion.KindIs(OAK_EQUAL) || !curAssertion.GetOp1().KindIs(O1K_SUBTYPE, O1K_EXACT_TYPE))
        {
            // TODO-CQ: We might benefit from OAK_NOT_EQUAL assertion as well, e.g.:
            // if (obj is not MyClass) // obj is known to be never of MyClass class
            // {
            //     if (obj is MyClass) // can be folded to false
            //     {
            //
            continue;
        }

        if ((curAssertion.GetOp1().GetVN() != vnStore->VNConservativeNormalValue(tree->gtVNPair) ||
             !curAssertion.GetOp2().KindIs(O2K_CONST_INT)))
        {
            continue;
        }

        ssize_t      methodTableVal = 0;
        GenTreeFlags iconFlags      = GTF_EMPTY;
        if (!optIsTreeKnownIntValue(!optLocalAssertionProp, methodTableArg, &methodTableVal, &iconFlags))
        {
            continue;
        }

        if (curAssertion.GetOp2().GetIntConstant() == methodTableVal)
        {
            // TODO-CQ: if they don't match, we might still be able to prove that the result is foldable via
            // compareTypesForCast.
            return index;
        }
    }
    return NO_ASSERTION_INDEX;
}

//------------------------------------------------------------------------------
// optVNBasedFoldExpr_Call_Memset: Unrolls NI_System_SpanHelpers_Fill for constant length.
//
// Arguments:
//    call - NI_System_SpanHelpers_Fill call to unroll
//
// Return Value:
//    Returns a new tree or nullptr if nothing is changed.
//
GenTree* Compiler::optVNBasedFoldExpr_Call_Memset(GenTreeCall* call)
{
    assert(call->IsSpecialIntrinsic(this, NI_System_SpanHelpers_Fill));

    CallArg* dstArg = call->gtArgs.GetUserArgByIndex(0);
    CallArg* lenArg = call->gtArgs.GetUserArgByIndex(1);
    CallArg* valArg = call->gtArgs.GetUserArgByIndex(2);

    var_types valType     = valArg->GetSignatureType();
    unsigned  lengthScale = genTypeSize(valType);

    if (lengthScale == 1)
    {
        // Lower expands it slightly better.
        JITDUMP("...value's type is byte - leave it for lower to expand.\n");
        return nullptr;
    }

    if (varTypeIsStruct(valType) || varTypeIsGC(valType))
    {
        JITDUMP("...value's type is not supported - bail out.\n");
        return nullptr;
    }

    ValueNum lenVN = vnStore->VNConservativeNormalValue(lenArg->GetNode()->gtVNPair);
    if (!vnStore->IsVNConstant(lenVN))
    {
        JITDUMP("...length is not a constant - bail out.\n");
        return nullptr;
    }

    size_t len = vnStore->CoercedConstantValue<size_t>(lenVN);
    if ((len > getUnrollThreshold(Memset)) ||
        // The first condition prevents the overflow in the second condition.
        // since both len and lengthScale are expected to be small at this point.
        (len * lengthScale) > getUnrollThreshold(Memset))
    {
        JITDUMP("...length is too big to unroll - bail out.\n");
        return nullptr;
    }

    // Some arbitrary threshold if the value is not a constant,
    // since it is unlikely that we can optimize it further.
    if (!valArg->GetNode()->OperIsConst() && (len >= 8))
    {
        JITDUMP("...length is too big to unroll for non-constant value - bail out.\n");
        return nullptr;
    }

    // Spill the side effects directly in the args, we're going to
    // pick them up in the following gtExtractSideEffList
    GenTree* dst = fgMakeMultiUse(&dstArg->NodeRef());
    GenTree* val = fgMakeMultiUse(&valArg->NodeRef());

    GenTree* result = nullptr;
    gtExtractSideEffList(call, &result, GTF_ALL_EFFECT, true);

    for (size_t offset = 0; offset < len; offset++)
    {
        // Clone dst and add offset if necessary.
        GenTree*         offsetNode = gtNewIconNode((ssize_t)(offset * lengthScale), TYP_I_IMPL);
        GenTree*         currDst    = gtNewOperNode(GT_ADD, dst->TypeGet(), gtCloneExpr(dst), offsetNode);
        GenTreeStoreInd* storeInd =
            gtNewStoreIndNode(valType, currDst, gtCloneExpr(val), GTF_IND_UNALIGNED | GTF_IND_ALLOW_NON_ATOMIC);

        // Merge with the previous result.
        result = result == nullptr ? storeInd : gtNewOperNode(GT_COMMA, TYP_VOID, result, storeInd);
    }

    JITDUMP("...optimized into STOREIND(s):\n");
    DISPTREE(result);
    return result;
}

//------------------------------------------------------------------------------
// optVNBasedFoldExpr_Call_Memmove: Unrolls NI_System_SpanHelpers_Memmove/CORINFO_HELP_MEMCPY
//    if possible. This function effectively duplicates LowerCallMemmove.
//    However, unlike LowerCallMemmove, it is able to optimize src into constants with help of VN.
//
// Arguments:
//    call - NI_System_SpanHelpers_Memmove/CORINFO_HELP_MEMCPY call to unroll
//
// Return Value:
//    Returns a new tree or nullptr if nothing is changed.
//
GenTree* Compiler::optVNBasedFoldExpr_Call_Memmove(GenTreeCall* call)
{
    JITDUMP("See if we can optimize NI_System_SpanHelpers_Memmove with help of VN...\n")
    assert(call->IsSpecialIntrinsic(this, NI_System_SpanHelpers_Memmove) ||
           call->IsHelperCall(this, CORINFO_HELP_MEMCPY));

    CallArg* dstArg = call->gtArgs.GetUserArgByIndex(0);
    CallArg* srcArg = call->gtArgs.GetUserArgByIndex(1);
    CallArg* lenArg = call->gtArgs.GetUserArgByIndex(2);
    ValueNum lenVN  = vnStore->VNConservativeNormalValue(lenArg->GetNode()->gtVNPair);
    if (!vnStore->IsVNConstant(lenVN))
    {
        JITDUMP("...length is not a constant - bail out.\n");
        return nullptr;
    }

    size_t len = vnStore->CoercedConstantValue<size_t>(lenVN);
    if (len == 0)
    {
        // Memmove(dst, src, 0) -> no-op.
        // Memmove doesn't dereference src/dst pointers if length is 0.
        JITDUMP("...length is 0 -> optimize to no-op.\n");
        return gtWrapWithSideEffects(gtNewNothingNode(), call, GTF_ALL_EFFECT, true);
    }

    if (len > getUnrollThreshold(Memcpy))
    {
        JITDUMP("...length is too big to unroll - bail out.\n");
        return nullptr;
    }

    // if GetImmutableDataFromAddress returns true, it means that the src is a read-only constant.
    // Thus, dst and src do not overlap (if they do - it's an UB).
    uint8_t* buffer = new (this, CMK_AssertionProp) uint8_t[len];
    if (!GetImmutableDataFromAddress(srcArg->GetNode(), (int)len, buffer))
    {
        JITDUMP("...src is not a constant - fallback to LowerCallMemmove.\n");
        return nullptr;
    }

    // if dstArg is not simple, we replace the arg directly with a temp assignment and
    // continue using that temp - it allows us reliably extract all side effects.
    GenTree* dst = fgMakeMultiUse(&dstArg->NodeRef());

    // Now we're going to emit a chain of STOREIND via COMMA nodes.
    // the very first tree is expected to be side-effects from the original call (including all args)
    GenTree* result = nullptr;
    gtExtractSideEffList(call, &result, GTF_ALL_EFFECT, true);

    unsigned lenRemaining = (unsigned)len;
    while (lenRemaining > 0)
    {
        const ssize_t offset = (ssize_t)len - (ssize_t)lenRemaining;

        // Clone dst and add offset if necessary.
        GenTree* currDst = gtCloneExpr(dst);
        if (offset != 0)
        {
            currDst = gtNewOperNode(GT_ADD, dst->TypeGet(), currDst, gtNewIconNode(offset, TYP_I_IMPL));
        }

        // Create an unaligned STOREIND node using the largest possible word size.
        var_types        type     = roundDownMaxType(lenRemaining);
        GenTree*         srcCns   = gtNewGenericCon(type, buffer + offset);
        GenTreeStoreInd* storeInd = gtNewStoreIndNode(type, currDst, srcCns, GTF_IND_UNALIGNED);
        fgUpdateConstTreeValueNumber(srcCns);

        // Merge with the previous result.
        result = result == nullptr ? storeInd : gtNewOperNode(GT_COMMA, TYP_VOID, result, storeInd);

        lenRemaining -= genTypeSize(type);
    }

    JITDUMP("...optimized into STOREIND(s)!:\n");
    DISPTREE(result);
    return result;
}

//------------------------------------------------------------------------------
// optVNBasedFoldExpr_Call: Folds given call using VN to a simpler tree.
//
// Arguments:
//    block  -  The block containing the tree.
//    parent -  The parent node of the tree.
//    call   -  The call to fold
//
// Return Value:
//    Returns a new tree or nullptr if nothing is changed.
//
GenTree* Compiler::optVNBasedFoldExpr_Call(BasicBlock* block, GenTree* parent, GenTreeCall* call)
{
    switch (call->GetHelperNum())
    {
        case CORINFO_HELP_CHKCASTARRAY:
        case CORINFO_HELP_CHKCASTANY:
        case CORINFO_HELP_CHKCASTINTERFACE:
        case CORINFO_HELP_CHKCASTCLASS:
        case CORINFO_HELP_ISINSTANCEOFARRAY:
        case CORINFO_HELP_ISINSTANCEOFCLASS:
        case CORINFO_HELP_ISINSTANCEOFANY:
        case CORINFO_HELP_ISINSTANCEOFINTERFACE:
        {
            CallArg* castClsCallArg = call->gtArgs.GetUserArgByIndex(0);
            CallArg* castObjCallArg = call->gtArgs.GetUserArgByIndex(1);
            GenTree* castClsArg     = castClsCallArg->GetNode();
            GenTree* castObjArg     = castObjCallArg->GetNode();

            // If object has the same VN as the cast, then the cast is effectively a no-op.
            //
            if (castObjArg->gtVNPair == call->gtVNPair)
            {
                // if castObjArg is not simple, we replace the arg with a temp assignment and
                // continue using that temp - it allows us reliably extract all side effects
                castObjArg = fgMakeMultiUse(&castObjCallArg->NodeRef());
                return gtWrapWithSideEffects(castObjArg, call, GTF_ALL_EFFECT, true);
            }

            // Let's see if gtGetClassHandle may help us to fold the cast (since VNForCast did not).
            if (castClsArg->IsIconHandle(GTF_ICON_CLASS_HDL))
            {
                bool                 isExact;
                bool                 isNonNull;
                CORINFO_CLASS_HANDLE castFrom = gtGetClassHandle(castObjArg, &isExact, &isNonNull);
                if (castFrom != NO_CLASS_HANDLE)
                {
                    CORINFO_CLASS_HANDLE castTo = gtGetHelperArgClassHandle(castClsArg);
                    // Constant prop may fail to propagate compile time class handles, so verify we have
                    // a handle before invoking the runtime.
                    if ((castTo != NO_CLASS_HANDLE) &&
                        info.compCompHnd->compareTypesForCast(castFrom, castTo) == TypeCompareState::Must)
                    {
                        // if castObjArg is not simple, we replace the arg with a temp assignment and
                        // continue using that temp - it allows us reliably extract all side effects
                        castObjArg = fgMakeMultiUse(&castObjCallArg->NodeRef());
                        return gtWrapWithSideEffects(castObjArg, call, GTF_ALL_EFFECT, true);
                    }
                }
            }
        }
        break;

        default:
            break;
    }

    if (call->IsSpecialIntrinsic(this, NI_System_SpanHelpers_Memmove) || call->IsHelperCall(this, CORINFO_HELP_MEMCPY))
    {
        return optVNBasedFoldExpr_Call_Memmove(call);
    }

    if (call->IsSpecialIntrinsic(this, NI_System_SpanHelpers_Fill))
    {
        return optVNBasedFoldExpr_Call_Memset(call);
    }

    return nullptr;
}

//------------------------------------------------------------------------------
// optVNBasedFoldExpr: Folds given tree using VN to a constant or a simpler tree.
//
// Arguments:
//    block  -  The block containing the tree.
//    parent -  The parent node of the tree.
//    tree   -  The tree to fold.
//
// Return Value:
//    Returns a new tree or nullptr if nothing is changed.
//
GenTree* Compiler::optVNBasedFoldExpr(BasicBlock* block, GenTree* parent, GenTree* tree)
{
    // First, attempt to fold it to a constant if possible.
    GenTree* foldedToCns = optVNBasedFoldConstExpr(block, parent, tree);
    if (foldedToCns != nullptr)
    {
        return foldedToCns;
    }

    switch (tree->OperGet())
    {
        case GT_CALL:
            return optVNBasedFoldExpr_Call(block, parent, tree->AsCall());

            // We can add more VN-based foldings here.

        default:
            break;
    }
    return nullptr;
}

//------------------------------------------------------------------------------
// optVNBasedFoldConstExpr: Substitutes tree with an evaluated constant while
//                          managing side-effects.
//
// Arguments:
//    block  -  The block containing the tree.
//    parent -  The parent node of the tree.
//    tree   -  The tree node whose value is known at compile time.
//              The tree should have a constant value number.
//
// Return Value:
//    Returns a potentially new or a transformed tree node.
//    Returns nullptr when no transformation is possible.
//
// Description:
//    Transforms a tree node if its result evaluates to a constant. The
//    transformation can be a "ChangeOper" to a constant or a new constant node
//    with extracted side-effects.
//
//    Before replacing or substituting the "tree" with a constant, extracts any
//    side effects from the "tree" and creates a comma separated side effect list
//    and then appends the transformed node at the end of the list.
//    This comma separated list is then returned.
//
//    For JTrue nodes, side effects are not put into a comma separated list. If
//    the relop will evaluate to "true" or "false" statically, then the side-effects
//    will be put into new statements, presuming the JTrue will be folded away.
//
GenTree* Compiler::optVNBasedFoldConstExpr(BasicBlock* block, GenTree* parent, GenTree* tree)
{
    if (tree->OperIs(GT_JTRUE))
    {
        // Treat JTRUE separately to extract side effects into respective statements rather
        // than using a COMMA separated op1.
        return optVNConstantPropOnJTrue(block, tree);
    }
    // If relop is part of JTRUE, this should be optimized as part of the parent JTRUE.
    // Or if relop is part of QMARK or anything else, we simply bail here.
    else if (tree->OperIsCompare() && (tree->gtFlags & GTF_RELOP_JMP_USED))
    {
        return nullptr;
    }

    // We want to use the Normal ValueNumber when checking for constants.
    ValueNumPair vnPair = tree->gtVNPair;
    ValueNum     vnCns  = vnStore->VNConservativeNormalValue(vnPair);

    // Check if node evaluates to a constant
    if (!vnStore->IsVNConstant(vnCns))
    {
        // Last chance - propagate VNF_PtrToLoc(lcl, offset) as GT_LCL_ADDR node
        VNFuncApp funcApp;
        if (((tree->gtFlags & GTF_SIDE_EFFECT) == 0) && vnStore->GetVNFunc(vnCns, &funcApp) &&
            (funcApp.m_func == VNF_PtrToLoc))
        {
            unsigned lcl  = (unsigned)vnStore->CoercedConstantValue<size_t>(funcApp.m_args[0]);
            unsigned offs = (unsigned)vnStore->CoercedConstantValue<size_t>(funcApp.m_args[1]);
            return gtNewLclAddrNode(lcl, offs, tree->TypeGet());
        }

        return nullptr;
    }

    GenTree* conValTree = nullptr;
    switch (vnStore->TypeOfVN(vnCns))
    {
        case TYP_FLOAT:
        {
            float value = vnStore->ConstantValue<float>(vnCns);

            if (tree->TypeIs(TYP_INT))
            {
                // Same sized reinterpretation of bits to integer
                conValTree = gtNewIconNode(*(reinterpret_cast<int*>(&value)));
            }
            else
            {
                // Implicit conversion to float or double
                assert(varTypeIsFloating(tree->TypeGet()));
                conValTree = gtNewDconNode(FloatingPointUtils::convertToDouble(value), tree->TypeGet());
            }
            break;
        }

        case TYP_DOUBLE:
        {
            double value = vnStore->ConstantValue<double>(vnCns);

            if (tree->TypeIs(TYP_LONG))
            {
                conValTree = gtNewLconNode(*(reinterpret_cast<INT64*>(&value)));
            }
            else
            {
                // Implicit conversion to float or double
                assert(varTypeIsFloating(tree->TypeGet()));
                conValTree = gtNewDconNode(value, tree->TypeGet());
            }
            break;
        }

        case TYP_LONG:
        {
            INT64 value = vnStore->ConstantValue<INT64>(vnCns);

#ifdef TARGET_64BIT
            if (vnStore->IsVNHandle(vnCns))
            {
                // Don't perform constant folding that involves a handle that needs
                // to be recorded as a relocation with the VM.
                if (!opts.compReloc)
                {
                    conValTree = gtNewIconHandleNode(value, vnStore->GetHandleFlags(vnCns));
                }
            }
            else
#endif
            {
                switch (tree->TypeGet())
                {
                    case TYP_INT:
                        // Implicit conversion to smaller integer
                        conValTree = gtNewIconNode(static_cast<int>(value));
                        break;

                    case TYP_LONG:
                        // Same type no conversion required
                        conValTree = gtNewLconNode(value);
                        break;

                    case TYP_FLOAT:
                        // No implicit conversions from long to float and value numbering will
                        // not propagate through memory reinterpretations of different size.
                        unreached();
                        break;

                    case TYP_DOUBLE:
                        // Same sized reinterpretation of bits to double
                        conValTree = gtNewDconNodeD(*(reinterpret_cast<double*>(&value)));
                        break;

                    default:
                        // Do not support such optimization.
                        break;
                }
            }
        }
        break;

        case TYP_REF:
        {
            if (tree->TypeIs(TYP_REF))
            {
                const size_t value = vnStore->ConstantValue<size_t>(vnCns);
                if (value == 0)
                {
                    conValTree = gtNewNull();
                }
                else
                {
                    assert(vnStore->IsVNObjHandle(vnCns));
                    conValTree = gtNewIconHandleNode(value, GTF_ICON_OBJ_HDL);
                }
            }
        }
        break;

        case TYP_INT:
        {
            int value = vnStore->ConstantValue<int>(vnCns);
#ifndef TARGET_64BIT
            if (vnStore->IsVNHandle(vnCns))
            {
                // Don't perform constant folding that involves a handle that needs
                // to be recorded as a relocation with the VM.
                if (!opts.compReloc)
                {
                    conValTree = gtNewIconHandleNode(value, vnStore->GetHandleFlags(vnCns));
                }
            }
            else
#endif
            {
                switch (tree->TypeGet())
                {
                    case TYP_REF:
                    case TYP_INT:
                        // Same type no conversion required
                        conValTree = gtNewIconNode(value);
                        break;

                    case TYP_LONG:
                        // Implicit conversion to larger integer
                        conValTree = gtNewLconNode(value);
                        break;

                    case TYP_FLOAT:
                        // Same sized reinterpretation of bits to float
                        conValTree = gtNewDconNodeF(BitOperations::UInt32BitsToSingle((uint32_t)value));
                        break;

                    case TYP_DOUBLE:
                        // No implicit conversions from int to double and value numbering will
                        // not propagate through memory reinterpretations of different size.
                        unreached();
                        break;

                    case TYP_BYTE:
                    case TYP_UBYTE:
                    case TYP_SHORT:
                    case TYP_USHORT:
                        assert(FitsIn(tree->TypeGet(), value));
                        conValTree = gtNewIconNode(value);
                        break;

                    default:
                        // Do not support (e.g. byref(const int)).
                        break;
                }
            }
        }
        break;

#if defined(FEATURE_SIMD)
        case TYP_SIMD8:
        {
            simd8_t value = vnStore->ConstantValue<simd8_t>(vnCns);

            GenTreeVecCon* vecCon = gtNewVconNode(tree->TypeGet());
            memcpy(&vecCon->gtSimdVal, &value, sizeof(simd8_t));

            conValTree = vecCon;
            break;
        }

        case TYP_SIMD12:
        {
            simd12_t value = vnStore->ConstantValue<simd12_t>(vnCns);

            GenTreeVecCon* vecCon = gtNewVconNode(tree->TypeGet());
            memcpy(&vecCon->gtSimdVal, &value, sizeof(simd12_t));

            conValTree = vecCon;
            break;
        }

        case TYP_SIMD16:
        {
            simd16_t value = vnStore->ConstantValue<simd16_t>(vnCns);

            GenTreeVecCon* vecCon = gtNewVconNode(tree->TypeGet());
            memcpy(&vecCon->gtSimdVal, &value, sizeof(simd16_t));

            conValTree = vecCon;
            break;
        }

#if defined(TARGET_XARCH)
        case TYP_SIMD32:
        {
            simd32_t value = vnStore->ConstantValue<simd32_t>(vnCns);

            GenTreeVecCon* vecCon = gtNewVconNode(tree->TypeGet());
            memcpy(&vecCon->gtSimdVal, &value, sizeof(simd32_t));

            conValTree = vecCon;
            break;
        }

        case TYP_SIMD64:
        {
            simd64_t value = vnStore->ConstantValue<simd64_t>(vnCns);

            GenTreeVecCon* vecCon = gtNewVconNode(tree->TypeGet());
            memcpy(&vecCon->gtSimdVal, &value, sizeof(simd64_t));

            conValTree = vecCon;
            break;
        }
        break;

#endif // TARGET_XARCH
#endif // FEATURE_SIMD

#if defined(FEATURE_MASKED_HW_INTRINSICS)
        case TYP_MASK:
        {
            simdmask_t value = vnStore->ConstantValue<simdmask_t>(vnCns);

            GenTreeMskCon* mskCon = gtNewMskConNode(tree->TypeGet());
            memcpy(&mskCon->gtSimdMaskVal, &value, sizeof(simdmask_t));

            conValTree = mskCon;
            break;
        }
        break;
#endif // FEATURE_MASKED_HW_INTRINSICS

        case TYP_BYREF:
            // Do not support const byref optimization.
            break;

        default:
            // We do not record constants of other types.
            unreached();
            break;
    }

    if (conValTree != nullptr)
    {
        if (!optIsProfitableToSubstitute(tree, block, parent, conValTree))
        {
            // Not profitable to substitute
            return nullptr;
        }

        // Were able to optimize.
        conValTree->gtVNPair = vnPair;
        return gtWrapWithSideEffects(conValTree, tree, GTF_SIDE_EFFECT, true);
    }
    else
    {
        // Was not able to optimize.
        return nullptr;
    }
}

//------------------------------------------------------------------------------
// optIsProfitableToSubstitute: Checks if value worth substituting to dest
//
// Arguments:
//    dest       - destination to substitute value to
//    destBlock  - Basic block of destination
//    destParent - Parent of destination
//    value      - value we plan to substitute
//
// Returns:
//    False if it's likely not profitable to do substitution, True otherwise
//
bool Compiler::optIsProfitableToSubstitute(GenTree* dest, BasicBlock* destBlock, GenTree* destParent, GenTree* value)
{
    // Giving up on these kinds of handles demonstrated size improvements
    if (value->IsIconHandle(GTF_ICON_STATIC_HDL, GTF_ICON_CLASS_HDL))
    {
        return false;
    }

    // A simple heuristic: If the constant is defined outside of a loop (not far from its head)
    // and is used inside it - don't propagate.
    //
    // TODO: Extend on more kinds of trees

    if (!dest->OperIs(GT_LCL_VAR))
    {
        return true;
    }

    const GenTreeLclVar* lcl = dest->AsLclVar();

    if (value->IsCnsVec())
    {
#if defined(FEATURE_HW_INTRINSICS)
        // Many hwintrinsics can't benefit from constant prop because they don't support
        // constant folding nor do they support any specialized encodings. So, we want to
        // skip constant prop and preserve any user-defined locals in that scenario.
        //
        // However, if the local is only referenced once then we want to allow propagation
        // regardless since we can then contain the only actual usage and save a needless
        // instruction.
        //
        // To determine number of uses, we prefer checking SSA first since it is more exact
        // and can account for patterns where a local is reassigned later. However, if we
        // can't find an SSA then we fallback to the naive ref count of the local, noting
        // that we need to check for greater than 2 since it includes both the def and use.

        bool inspectIntrinsic = false;

        if ((destParent != nullptr) && destParent->OperIsHWIntrinsic())
        {
            LclVarDsc* varDsc = lvaGetDesc(lcl);

            if (lcl->HasSsaName())
            {
                inspectIntrinsic = varDsc->GetPerSsaData(lcl->GetSsaNum())->GetNumUses() > 1;
            }
            else
            {
                inspectIntrinsic = varDsc->lvRefCnt() > 2;
            }
        }

        if (inspectIntrinsic)
        {
            GenTreeHWIntrinsic* parent      = destParent->AsHWIntrinsic();
            NamedIntrinsic      intrinsicId = parent->GetHWIntrinsicId();

            if (!HWIntrinsicInfo::CanBenefitFromConstantProp(intrinsicId))
            {
                return false;
            }

            // For several of the scenarios we may skip the costing logic
            // since we know that the operand is always containable and therefore
            // is always cost effective to propagate.

            return parent->ShouldConstantProp(dest, value->AsVecCon());
        }
#endif // FEATURE_HW_INTRINSICS
    }
    else if (!value->IsCnsFltOrDbl() && !value->IsCnsMsk())
    {
        return true;
    }

    gtPrepareCost(value);

    if ((value->GetCostEx() > 1) && (value->GetCostSz() > 1))
    {
        // Try to find the block this constant was originally defined in
        if (lcl->HasSsaName())
        {
            BasicBlock* defBlock = lvaGetDesc(lcl)->GetPerSsaData(lcl->GetSsaNum())->GetBlock();
            if (defBlock != nullptr)
            {
                // Avoid propagating if the weighted use cost is significantly greater than the def cost.
                // NOTE: this currently does not take "a float living across a call" case into account
                // where we might end up with spill/restore on ABIs without callee-saved registers
                const weight_t defBlockWeight = defBlock->getBBWeight(this);
                const weight_t lclblockWeight = destBlock->getBBWeight(this);

                if ((defBlockWeight > 0) && ((lclblockWeight / defBlockWeight) >= BB_LOOP_WEIGHT_SCALE))
                {
                    JITDUMP("Constant propagation inside loop " FMT_BB " is not profitable\n", destBlock->bbNum);
                    return false;
                }
            }
        }
    }
    return true;
}

//------------------------------------------------------------------------------
// optConstantAssertionProp: Possibly substitute a constant for a local use
//
// Arguments:
//    curAssertion - assertion to propagate
//    tree         - tree to possibly modify
//    stmt         - statement containing the tree
//    index        - index of this assertion in the assertion table
//
// Returns:
//    Updated tree (may be the input tree, modified in place), or nullptr
//
// Notes:
//    stmt may be nullptr during local assertion prop
//
GenTree* Compiler::optConstantAssertionProp(const AssertionDsc&  curAssertion,
                                            GenTreeLclVarCommon* tree,
                                            Statement* stmt      DEBUGARG(AssertionIndex index))
{
    const unsigned lclNum = tree->GetLclNum();

    if (lclNumIsCSE(lclNum))
    {
        // Ignore the CSE flag in Global Assertion Prop for checked bound as those usually
        // unlock more opportunities for BCE.
        if (optLocalAssertionProp || !vnStore->IsVNCheckedBound(optConservativeNormalVN(tree)))
        {
            return nullptr;
        }
    }

    GenTree* newTree = tree;

    // Update 'newTree' with the new value from our table
    // Typically newTree == tree and we are updating the node in place
    switch (curAssertion.GetOp2().GetKind())
    {
        case O2K_CONST_DOUBLE:
            // There could be a positive zero and a negative zero, so don't propagate zeroes.
            if (curAssertion.GetOp2().GetDoubleConstant() == 0.0)
            {
                return nullptr;
            }
            newTree->BashToConst(curAssertion.GetOp2().GetDoubleConstant(), tree->TypeGet());
            break;

        case O2K_CONST_INT:

            // Don't propagate non-nulll non-static handles if we need to report relocs.
            if (opts.compReloc && curAssertion.GetOp2().HasIconFlag() && (curAssertion.GetOp2().GetIntConstant() != 0))
            {
                if (curAssertion.GetOp2().GetIconFlag() != GTF_ICON_STATIC_HDL)
                {
                    return nullptr;
                }
            }

            // We assume that we do not try to do assertion prop on mismatched
            // accesses (note that we widen normalize-on-load local accesses
            // and insert casts in morph, which would be problematic to track
            // here).
            assert(tree->TypeGet() == lvaGetDesc(lclNum)->TypeGet());

            if (curAssertion.GetOp2().HasIconFlag())
            {
                // Here we have to allocate a new 'large' node to replace the old one
                newTree =
                    gtNewIconHandleNode(curAssertion.GetOp2().GetIntConstant(), curAssertion.GetOp2().GetIconFlag(),
                                        curAssertion.GetOp2().GetIconFieldSeq());

                // Make sure we don't retype const gc handles to TYP_I_IMPL
                // Although, it's possible for e.g. GTF_ICON_STATIC_HDL

                if (!newTree->IsIntegralConst(0) && newTree->IsIconHandle(GTF_ICON_OBJ_HDL) && !tree->TypeIs(TYP_REF))
                {
                    // If the tree is not a TYP_REF, we should not propagate an ICON TYP_REF
                    // into it, as it may lead to incorrect code generation.
                    return nullptr;
                }

                newTree->ChangeType(tree->TypeGet());
            }
            else
            {
                assert(varTypeIsIntegralOrI(tree));
                newTree->BashToConst(curAssertion.GetOp2().GetIntConstant(), genActualType(tree));
            }
            break;

        default:
            return nullptr;
    }

    if (!optLocalAssertionProp)
    {
        assert(newTree->OperIsConst()); // We should have a simple Constant node for newTree
        assert(vnStore->IsVNConstant(curAssertion.GetOp2().GetVN())); // The value number stored for op2 should be a
                                                                      // valid VN representing the constant
        newTree->gtVNPair.SetBoth(curAssertion.GetOp2().GetVN()); // Set the ValueNumPair to the constant VN from op2
                                                                  // of the assertion
    }

#ifdef DEBUG
    if (verbose)
    {
        printf("\nAssertion prop in " FMT_BB ":\n", compCurBB->bbNum);
        optPrintAssertion(curAssertion, index);
        gtDispTree(newTree, nullptr, nullptr, true);
    }
#endif

    return optAssertionProp_Update(newTree, tree, stmt);
}

//------------------------------------------------------------------------------
// optZeroObjAssertionProp: Find and propagate a ZEROOBJ assertion for the given tree.
//
// Arguments:
//    assertions - set of live assertions
//    tree       - the tree to possibly replace, in-place, with a zero
//
// Returns:
//    Whether propagation took place.
//
// Notes:
//    Because not all users of struct nodes support "zero" operands, instead of
//    propagating ZEROOBJ on locals, we propagate it on their parents.
//
bool Compiler::optZeroObjAssertionProp(GenTree* tree, ASSERT_VALARG_TP assertions)
{
    // We only make ZEROOBJ assertions in local propagation.
    if (!optLocalAssertionProp)
    {
        return false;
    }

    // And only into local nodes
    if (!tree->OperIsLocal())
    {
        return false;
    }

    // No ZEROOBJ assertions for simd.
    //
    if (varTypeIsSIMD(tree))
    {
        return false;
    }

    LclVarDsc* const lclVarDsc = lvaGetDesc(tree->AsLclVarCommon());

    if (lclVarDsc->IsAddressExposed())
    {
        return false;
    }

    const unsigned lclNum         = tree->AsLclVarCommon()->GetLclNum();
    AssertionIndex assertionIndex = optLocalAssertionIsEqualOrNotEqual(O1K_LCLVAR, lclNum, O2K_ZEROOBJ, 0, assertions);
    if (assertionIndex == NO_ASSERTION_INDEX)
    {
        return false;
    }

    const AssertionDsc& assertion = optGetAssertion(assertionIndex);
    JITDUMP("\nAssertion prop in " FMT_BB ":\n", compCurBB->bbNum);
    JITDUMPEXEC(optPrintAssertion(assertion, assertionIndex));
    DISPNODE(tree);

    tree->BashToZeroConst(TYP_INT);

    JITDUMP(" =>\n");
    DISPNODE(tree);

    return true;
}

//------------------------------------------------------------------------------
// optAssertionProp_LclVarTypeCheck: verify compatible types for copy prop
//
// Arguments:
//    tree         - tree to possibly modify
//    lclVarDsc    - local accessed by tree
//    copyVarDsc   - local to possibly copy prop into tree
//
// Returns:
//    True if copy prop is safe.
//
// Notes:
//    Before substituting copyVar for lclVar, make sure using copyVar doesn't widen access.
//
bool Compiler::optAssertionProp_LclVarTypeCheck(GenTree* tree, LclVarDsc* lclVarDsc, LclVarDsc* copyVarDsc)
{
    /*
        Small struct field locals are stored using the exact width and loaded widened
        (i.e. lvNormalizeOnStore==false   lvNormalizeOnLoad==true),
        because the field locals might end up embedded in the parent struct local with the exact width.

            In other words, a store to a short field local should always done using an exact width store

                [00254538] 0x0009 ------------               const     int    0x1234
            [002545B8] 0x000B -A--G--NR---               =         short
                [00254570] 0x000A D------N----               lclVar    short  V43 tmp40

            mov   word  ptr [L_043], 0x1234

        Now, if we copy prop, say a short field local V43, to another short local V34
        for the following tree:

                [04E18650] 0x0001 ------------               lclVar    int   V34 tmp31
            [04E19714] 0x0002 -A----------               =         int
                [04E196DC] 0x0001 D------N----               lclVar    int   V36 tmp33

        We will end with this tree:

                [04E18650] 0x0001 ------------               lclVar    int   V43 tmp40
            [04E19714] 0x0002 -A-----NR---               =         int
                [04E196DC] 0x0001 D------N----               lclVar    int   V36 tmp33    EAX

        And eventually causing a fetch of 4-byte out from [L_043] :(
            mov     EAX, dword ptr [L_043]

        The following check is to make sure we only perform the copy prop
        when we don't retrieve the wider value.
    */

    if (copyVarDsc->lvIsStructField)
    {
        var_types varType = (var_types)copyVarDsc->lvType;
        // Make sure we don't retrieve the wider value.
        return !varTypeIsSmall(varType) || (varType == tree->TypeGet());
    }
    // Called in the context of a single copy assertion, so the types should have been
    // taken care by the assertion gen logic for other cases. Just return true.
    return true;
}

//------------------------------------------------------------------------
// optCopyAssertionProp: copy prop use of one local with another
//
// Arguments:
//    curAssertion - assertion triggering the possible copy
//    tree         - tree use to consider replacing
//    stmt         - statement containing the tree
//    index        - index of the assertion
//
// Returns:
//    Updated tree, or nullptr
//
// Notes:
//    stmt may be nullptr during local assertion prop
//
GenTree* Compiler::optCopyAssertionProp(const AssertionDsc&  curAssertion,
                                        GenTreeLclVarCommon* tree,
                                        Statement* stmt      DEBUGARG(AssertionIndex index))
{
    assert(optLocalAssertionProp);

    const AssertionDsc::AssertionDscOp1& op1 = curAssertion.GetOp1();
    const AssertionDsc::AssertionDscOp2& op2 = curAssertion.GetOp2();

    noway_assert(op1.GetLclNum() != op2.GetLclNum());

    const unsigned lclNum = tree->GetLclNum();

    // Make sure one of the lclNum of the assertion matches with that of the tree.
    if (op1.GetLclNum() != lclNum && op2.GetLclNum() != lclNum)
    {
        return nullptr;
    }

    // Extract the matching lclNum and ssaNum, as well as the field sequence.
    unsigned copyLclNum;
    if (op1.GetLclNum() == lclNum)
    {
        copyLclNum = op2.GetLclNum();
    }
    else
    {
        copyLclNum = op1.GetLclNum();
    }

    LclVarDsc* const copyVarDsc = lvaGetDesc(copyLclNum);
    LclVarDsc* const lclVarDsc  = lvaGetDesc(lclNum);

    // Make sure the types are compatible.
    if (!optAssertionProp_LclVarTypeCheck(tree, lclVarDsc, copyVarDsc))
    {
        return nullptr;
    }

    // Make sure we can perform this copy prop.
    if (optCopyProp_LclVarScore(lclVarDsc, copyVarDsc, curAssertion.GetOp1().GetLclNum() == lclNum) <= 0)
    {
        return nullptr;
    }

    // Heuristic: for LclFld prop, don't force the copy or its promoted fields to be in memory.
    //
    if (tree->OperIs(GT_LCL_FLD))
    {
        if (copyVarDsc->IsEnregisterableLcl() || copyVarDsc->lvPromoted)
        {
            return nullptr;
        }
        else
        {
            lvaSetVarDoNotEnregister(copyLclNum DEBUGARG(DoNotEnregisterReason::LocalField));
        }
    }

    tree->SetLclNum(copyLclNum);

    // Copy prop and last-use copy elision happens at the same time in morph.
    // This node may potentially not be a last use of the new local.
    //
    // TODO-CQ: It is probably better to avoid doing this propagation if we
    // would otherwise omit an implicit byref copy since this propagation will
    // force us to create another copy anyway.
    //
    tree->gtFlags &= ~GTF_VAR_DEATH;

#ifdef DEBUG
    if (verbose)
    {
        printf("\nAssertion prop in " FMT_BB ":\n", compCurBB->bbNum);
        optPrintAssertion(curAssertion, index);
        DISPNODE(tree);
    }
#endif

    // Update and morph the tree.
    return optAssertionProp_Update(tree, tree, stmt);
}

//------------------------------------------------------------------------
// optAssertionProp_LclVar: try and optimize a local var use via assertions
//
// Arguments:
//    assertions - set of live assertions
//    tree       - local use to optimize
//    stmt       - statement containing the tree
//
// Returns:
//    Updated tree, or nullptr
//
// Notes:
//   stmt may be nullptr during local assertion prop
//
GenTree* Compiler::optAssertionProp_LclVar(ASSERT_VALARG_TP assertions, GenTreeLclVarCommon* tree, Statement* stmt)
{
    // If we have a var definition then bail or
    // If this is the address of the var then it will have the GTF_DONT_CSE
    // flag set and we don't want to assertion prop on it.
    // TODO-ASG: delete.
    if (tree->gtFlags & (GTF_VAR_DEF | GTF_DONT_CSE))
    {
        return nullptr;
    }

    // There are no constant assertions for structs in global propagation.
    //
    if ((!optLocalAssertionProp && varTypeIsStruct(tree)) || !optCanPropLclVar)
    {
        return nullptr;
    }

    // For local assertion prop we can filter the assertion set down.
    //
    const unsigned lclNum = tree->GetLclNum();
    ValueNum       treeVN = optConservativeNormalVN(tree);

    ASSERT_TP filteredAssertions = assertions;
    if (optLocalAssertionProp)
    {
        filteredAssertions = BitVecOps::Intersection(apTraits, GetAssertionDep(lclNum), filteredAssertions);
    }
    else if (!optAssertionHasAssertionsForVN(treeVN))
    {
        // There are no assertions for this VN
        return nullptr;
    }

    BitVecOps::Iter iter(apTraits, filteredAssertions);
    unsigned        index = 0;
    while (iter.NextElem(&index))
    {
        AssertionIndex assertionIndex = GetAssertionIndex(index);
        if (assertionIndex > optAssertionCount)
        {
            break;
        }
        // See if the variable is equal to a constant or another variable.
        const AssertionDsc& curAssertion = optGetAssertion(assertionIndex);
        if (!curAssertion.CanPropLclVar())
        {
            continue;
        }

        // Copy prop.
        if (curAssertion.GetOp2().KindIs(O2K_LCLVAR_COPY))
        {
            // Cannot do copy prop during global assertion prop because of no knowledge
            // of kill sets. We will still make a == b copy assertions during the global phase to allow
            // for any implied assertions that can be retrieved. Because implied assertions look for
            // matching SSA numbers (i.e., if a0 == b1 and b1 == c0 then a0 == c0) they don't need kill sets.
            if (optLocalAssertionProp)
            {
                // Perform copy assertion prop.
                GenTree* newTree = optCopyAssertionProp(curAssertion, tree, stmt DEBUGARG(assertionIndex));
                if (newTree != nullptr)
                {
                    return newTree;
                }
            }

            continue;
        }

        // There are no constant assertions for structs.
        //
        if (varTypeIsStruct(tree))
        {
            continue;
        }

        // Verify types match
        if (tree->TypeGet() != lvaGetRealType(lclNum))
        {
            continue;
        }

        if (optLocalAssertionProp)
        {
            // Check lclNum in Local Assertion Prop
            if (curAssertion.GetOp1().GetLclNum() == lclNum)
            {
                return optConstantAssertionProp(curAssertion, tree, stmt DEBUGARG(assertionIndex));
            }
        }
        else
        {
            // Check VN in Global Assertion Prop
            if (curAssertion.GetOp1().GetVN() == treeVN)
            {
                return optConstantAssertionProp(curAssertion, tree, stmt DEBUGARG(assertionIndex));
            }
        }
    }

    return nullptr;
}

//------------------------------------------------------------------------
// optAssertionProp_LclFld: try and optimize a local field use via assertions
//
// Arguments:
//    assertions - set of live assertions
//    tree       - local field use to optimize
//    stmt       - statement containing the tree
//
// Returns:
//    Updated tree, or nullptr
//
// Notes:
//   stmt may be nullptr during local assertion prop
//
GenTree* Compiler::optAssertionProp_LclFld(ASSERT_VALARG_TP assertions, GenTreeLclVarCommon* tree, Statement* stmt)
{
    // If we have a var definition then bail or
    // If this is the address of the var then it will have the GTF_DONT_CSE
    // flag set and we don't want to assertion prop on it.
    // TODO-ASG: delete.
    if (tree->gtFlags & (GTF_VAR_DEF | GTF_DONT_CSE))
    {
        return nullptr;
    }

    // Only run during local prop and if copies are available.
    //
    if (!optLocalAssertionProp || !optCanPropLclVar)
    {
        return nullptr;
    }

    const unsigned lclNum             = tree->GetLclNum();
    ASSERT_TP      filteredAssertions = BitVecOps::Intersection(apTraits, GetAssertionDep(lclNum), assertions);

    BitVecOps::Iter iter(apTraits, filteredAssertions);
    unsigned        index = 0;
    while (iter.NextElem(&index))
    {
        AssertionIndex assertionIndex = GetAssertionIndex(index);
        if (assertionIndex > optAssertionCount)
        {
            break;
        }

        // See if the variable is equal to another variable.
        //
        const AssertionDsc& curAssertion = optGetAssertion(assertionIndex);
        if (curAssertion.CanPropLclVar() && curAssertion.GetOp2().KindIs(O2K_LCLVAR_COPY))
        {
            GenTree* const newTree = optCopyAssertionProp(curAssertion, tree, stmt DEBUGARG(assertionIndex));
            if (newTree != nullptr)
            {
                return newTree;
            }
        }
    }

    return nullptr;
}

//------------------------------------------------------------------------
// optAssertionProp_LocalStore: Try and optimize a local store via assertions.
//
// Propagates ZEROOBJ for the value. Suppresses no-op stores.
//
// Arguments:
//    assertions - set of live assertions
//    store      - the store to optimize
//    stmt       - statement containing "store"
//
// Returns:
//    Updated "store", or "nullptr"
//
// Notes:
//   stmt may be nullptr during local assertion prop
//
GenTree* Compiler::optAssertionProp_LocalStore(ASSERT_VALARG_TP assertions, GenTreeLclVarCommon* store, Statement* stmt)
{
    if (!optLocalAssertionProp)
    {
        // No ZEROOBJ assertions in global propagation.
        return nullptr;
    }

    // Try and simplify the value.
    //
    bool     madeChanges = false;
    GenTree* value       = store->Data();
    if (value->TypeIs(TYP_STRUCT) && optZeroObjAssertionProp(value, assertions))
    {
        madeChanges = true;
    }

    // If we're storing a value to a lcl/field that already has that value, suppress the store.
    //
    // For now we just check for zero.
    //
    // In particular we want to make sure that for struct S the "redundant init" pattern
    //
    //   S s = new S();
    //   s.field = 0;
    //
    // does not kill the zerobj assertion for s.
    //
    unsigned const       dstLclNum      = store->GetLclNum();
    bool const           dstLclIsStruct = lvaGetDesc(dstLclNum)->TypeIs(TYP_STRUCT);
    AssertionIndex const dstIndex =
        optLocalAssertionIsEqualOrNotEqual(O1K_LCLVAR, dstLclNum, dstLclIsStruct ? O2K_ZEROOBJ : O2K_CONST_INT, 0,
                                           assertions);
    if (dstIndex != NO_ASSERTION_INDEX)
    {
        const AssertionDsc& dstAssertion = optGetAssertion(dstIndex);
        if (dstAssertion.KindIs(OAK_EQUAL) &&
            (dstAssertion.GetOp2().KindIs(O2K_ZEROOBJ) || (dstAssertion.GetOp2().GetIntConstant() == 0)))
        {
            // Destination is zero. Is value a literal zero? If so we don't need the store.
            //
            // The latter part of the if below is a heuristic.
            //
            // If we elimiate a zero store for integral lclVars it can lead to unnecessary
            // cloning. We need to make sure `optExtractInitTestIncr` still sees zero loop
            // iter lower bounds.
            //
            if (value->IsIntegralConst(0) && (dstLclIsStruct || varTypeIsGC(store)))
            {
                JITDUMP("[%06u] is assigning a constant zero to a struct field or gc local that is already zero\n",
                        dspTreeID(store));
                JITDUMPEXEC(optPrintAssertion(dstAssertion));

                store->gtBashToNOP();
                return optAssertionProp_Update(store, store, stmt);
            }
        }
    }

    // We might have simplified the value but were not able to remove the store.
    //
    if (madeChanges)
    {
        return optAssertionProp_Update(store, store, stmt);
    }

    return nullptr;
}

//------------------------------------------------------------------------
// optAssertionProp_BlockStore: Try and optimize a struct store via assertions.
//
// Propagates ZEROOBJ for the value. Propagates non-null assertions.
//
// Arguments:
//    assertions - set of live assertions
//    store      - the store to optimize
//    stmt       - statement containing "store"
//
// Returns:
//    Updated "store", or "nullptr"
//
// Notes:
//   stmt may be nullptr during local assertion prop
//
GenTree* Compiler::optAssertionProp_BlockStore(ASSERT_VALARG_TP assertions, GenTreeBlk* store, Statement* stmt)
{
    assert(store->OperIs(GT_STORE_BLK));

    bool didZeroObjProp = optZeroObjAssertionProp(store->Data(), assertions);
    bool didNonNullProp = optNonNullAssertionProp_Ind(assertions, store);
    if (didZeroObjProp || didNonNullProp)
    {
        return optAssertionProp_Update(store, store, stmt);
    }

    return nullptr;
}

//------------------------------------------------------------------------
// optAssertionProp_RangeProperties: Obtains range properties for an arbitrary tree
//
// Arguments:
//    assertions         - set of live assertions
//    tree               - the integral tree to analyze
//    stmt               - statement containing "tree"
//    block              - block containing "stmt"
//    isKnownNonZero     - [OUT] set to true if the tree is known to be non-zero
//    isKnownNonNegative - [OUT] set to true if the tree is known to be non-negative
//
void Compiler::optAssertionProp_RangeProperties(ASSERT_VALARG_TP assertions,
                                                GenTree*         tree,
                                                Statement*       stmt,
                                                BasicBlock*      block,
                                                bool*            isKnownNonZero,
                                                bool*            isKnownNonNegative)
{
    *isKnownNonZero     = false;
    *isKnownNonNegative = false;

    if (optLocalAssertionProp || !varTypeIsIntegral(tree) || BitVecOps::MayBeUninit(assertions) ||
        BitVecOps::IsEmpty(apTraits, assertions))
    {
        return;
    }

    // First, check simple properties without assertions.
    *isKnownNonNegative = tree->IsNeverNegative(this);
    *isKnownNonZero     = tree->IsNeverZero();

    if (*isKnownNonZero && *isKnownNonNegative)
    {
        // TP: We already have both properties, no need to check assertions.
        return;
    }

    const ValueNum  treeVN = vnStore->VNConservativeNormalValue(tree->gtVNPair);
    BitVecOps::Iter iter(apTraits, assertions);
    unsigned        index = 0;
    while (iter.NextElem(&index))
    {
        const AssertionDsc& curAssertion = optGetAssertion(GetAssertionIndex(index));

        // First, analyze possible X ==/!= CNS assertions.
        if (curAssertion.IsConstantInt32Assertion() && (curAssertion.GetOp1().GetVN() == treeVN))
        {
            if (curAssertion.KindIs(OAK_NOT_EQUAL) && (curAssertion.GetOp2().GetIntConstant() == 0))
            {
                // X != 0 --> definitely non-zero
                // We can't say anything about X's non-negativity
                *isKnownNonZero = true;
            }
            else if (!curAssertion.KindIs(OAK_NOT_EQUAL))
            {
                // X == CNS --> definitely non-negative if CNS >= 0
                // and definitely non-zero if CNS != 0
                *isKnownNonNegative = curAssertion.GetOp2().GetIntConstant() >= 0;
                *isKnownNonZero     = curAssertion.GetOp2().GetIntConstant() != 0;
            }
        }

        if (curAssertion.IsRelop() && curAssertion.GetOp2().KindIs(O2K_CONST_INT) &&
            (curAssertion.GetOp1().GetVN() == treeVN) && curAssertion.GetOp2().GetIntConstant() >= 0)
        {
            if (curAssertion.KindIs(OAK_LT_UN, OAK_LE_UN))
            {
                // (uint)X <= CNS means X is [0..CNS]
                *isKnownNonNegative = true;
            }
            else if (curAssertion.KindIs(OAK_GE, OAK_GT))
            {
                // X >= CNS means X is [CNS..unknown]
                *isKnownNonNegative = true;
                *isKnownNonZero     = curAssertion.KindIs(OAK_GT) || (curAssertion.GetOp2().GetIntConstant() > 0);
            }
        }
    }

    if (*isKnownNonZero && *isKnownNonNegative)
    {
        return;
    }

    // Let's see if MergeEdgeAssertions can help us:
    if (genActualType(tree) == TYP_INT)
    {
        Range rng = RangeCheck::GetRangeFromAssertions(this, treeVN, assertions);
        assert(rng.IsConstantRange());
        if (rng.LowerLimit().GetConstant() >= 0)
        {
            *isKnownNonNegative = true;
        }
        if ((rng.LowerLimit().GetConstant() > 0) || (rng.UpperLimit().GetConstant() < 0))
        {
            *isKnownNonZero = true;
        }
    }
}

//------------------------------------------------------------------------
// optAssertionProp_AddMulSub: Optimizes MUL/ADD/SUB via assertions
//    1) Clears overflow flag if both operands are proven to be in a range that cannot overflow
//
// Arguments:
//    assertions - set of live assertions
//    tree       - the MUL/ADD/SUB node to optimize
//    stmt       - statement containing MUL/ADD/SUB
//
// Returns:
//    Updated MUL/ADD/SUB node, or nullptr
//
GenTree* Compiler::optAssertionProp_AddMulSub(ASSERT_VALARG_TP assertions, GenTreeOp* tree, Statement* stmt)
{
    assert(tree->OperIs(GT_MUL, GT_ADD, GT_SUB));

    if (!optLocalAssertionProp && tree->TypeIs(TYP_INT) && tree->gtOverflow())
    {
        GenTree* op1 = tree->gtGetOp1();
        GenTree* op2 = tree->gtGetOp2();

        Range op1Rng = RangeCheck::GetRangeFromAssertions(this, optConservativeNormalVN(op1), assertions);
        Range op2Rng = RangeCheck::GetRangeFromAssertions(this, optConservativeNormalVN(op2), assertions);
        Range result = Limit(Limit::keUnknown);
        if (tree->OperIs(GT_MUL))
        {
            result = RangeOps::Multiply(op1Rng, op2Rng, tree->IsUnsigned());
        }
        else if (tree->OperIs(GT_ADD))
        {
            result = RangeOps::Add(op1Rng, op2Rng, tree->IsUnsigned());
        }
        else
        {
            assert(tree->OperIs(GT_SUB));
            result = RangeOps::Subtract(op1Rng, op2Rng, tree->IsUnsigned());
        }

        // If it produced a constant range for the result, we know the operation
        // cannot overflow for any values consistent with the current assertions.
        if (result.IsConstantRange())
        {
            tree->ClearOverflow();
            return optAssertionProp_Update(tree, tree, stmt);
        }
    }
    return nullptr;
}

//------------------------------------------------------------------------
// optAssertionProp_ModDiv: Optimizes DIV/UDIV/MOD/UMOD via assertions
//    1) Convert DIV/MOD to UDIV/UMOD if both operands are proven to be never negative
//    2) Marks DIV/UDIV/MOD/UMOD with GTF_DIV_MOD_NO_BY_ZERO if divisor is proven to be never zero
//    3) Marks DIV/UDIV/MOD/UMOD with GTF_DIV_MOD_NO_OVERFLOW if both operands are proven to be never negative
//
// Arguments:
//    assertions - set of live assertions
//    tree       - the DIV/UDIV/MOD/UMOD node to optimize
//    stmt       - statement containing DIV/UDIV/MOD/UMOD
//    block      - the block containing the statement
//
// Returns:
//    Updated DIV/UDIV/MOD/UMOD node, or nullptr
//
GenTree* Compiler::optAssertionProp_ModDiv(ASSERT_VALARG_TP assertions,
                                           GenTreeOp*       tree,
                                           Statement*       stmt,
                                           BasicBlock*      block)
{
    GenTree* op1 = tree->gtGetOp1();
    GenTree* op2 = tree->gtGetOp2();

    bool op1IsNotZero;
    bool op2IsNotZero;
    bool op1IsNotNegative;
    bool op2IsNotNegative;
    optAssertionProp_RangeProperties(assertions, op1, stmt, block, &op1IsNotZero, &op1IsNotNegative);
    optAssertionProp_RangeProperties(assertions, op2, stmt, block, &op2IsNotZero, &op2IsNotNegative);

    bool changed = false;
    if (op1IsNotNegative && op2IsNotNegative && tree->OperIs(GT_DIV, GT_MOD))
    {
        JITDUMP("Converting DIV/MOD to unsigned UDIV/UMOD since both operands are never negative...\n")
        tree->SetOper(tree->OperIs(GT_DIV) ? GT_UDIV : GT_UMOD, GenTree::PRESERVE_VN);
        changed = true;
    }

    if (op2IsNotZero)
    {
        JITDUMP("Divisor for DIV/MOD is proven to be never negative...\n")
        tree->gtFlags |= GTF_DIV_MOD_NO_BY_ZERO;
        changed = true;
    }

    if (op1IsNotNegative || op2IsNotNegative)
    {
        JITDUMP("DIV/MOD is proven to never overflow...\n")
        tree->gtFlags |= GTF_DIV_MOD_NO_OVERFLOW;
        changed = true;
    }

    return changed ? optAssertionProp_Update(tree, tree, stmt) : nullptr;
}

//------------------------------------------------------------------------
// optAssertionProp_Return: Try and optimize a GT_RETURN/GT_SWIFT_ERROR_RET via assertions.
//
// Propagates ZEROOBJ for the return value.
//
// Arguments:
//    assertions - set of live assertions
//    ret        - the return node to optimize
//    stmt       - statement containing "ret"
//
// Returns:
//    Updated "ret", or "nullptr"
//
// Notes:
//   stmt may be nullptr during local assertion prop
//
GenTree* Compiler::optAssertionProp_Return(ASSERT_VALARG_TP assertions, GenTreeOp* ret, Statement* stmt)
{
    GenTree* retValue = ret->GetReturnValue();

    // Only propagate zeroes that lowering can deal with.
    if (!ret->TypeIs(TYP_VOID) && varTypeIsStruct(retValue) && !varTypeIsStruct(info.compRetNativeType))
    {
        if (optZeroObjAssertionProp(retValue, assertions))
        {
            return optAssertionProp_Update(ret, ret, stmt);
        }
    }

    return nullptr;
}

/*****************************************************************************
 *
 *  Given a set of "assertions" to search, find an assertion that matches
 *  op1Kind and lclNum, op2Kind and the constant value and is either equal or
 *  not equal assertion.
 */
AssertionIndex Compiler::optLocalAssertionIsEqualOrNotEqual(
    optOp1Kind op1Kind, unsigned lclNum, optOp2Kind op2Kind, ssize_t cnsVal, ASSERT_VALARG_TP assertions)
{
    noway_assert(op1Kind == O1K_LCLVAR);
    noway_assert((op2Kind == O2K_CONST_INT) || (op2Kind == O2K_ZEROOBJ));

    assert(optLocalAssertionProp);
    ASSERT_TP apDependent = BitVecOps::Intersection(apTraits, GetAssertionDep(lclNum), assertions);

    BitVecOps::Iter iter(apTraits, apDependent);
    unsigned        bvIndex = 0;
    while (iter.NextElem(&bvIndex))
    {
        AssertionIndex const index        = GetAssertionIndex(bvIndex);
        const AssertionDsc&  curAssertion = optGetAssertion(index);

        if (!curAssertion.CanPropEqualOrNotEqual())
        {
            continue;
        }

        if (curAssertion.GetOp1().KindIs(op1Kind) && (curAssertion.GetOp1().GetLclNum() == lclNum) &&
            curAssertion.GetOp2().KindIs(op2Kind))
        {
            // Check constant value. If both are ZEROOBJ then they are equal, otherwise compare integer constant values.
            // GetOp2().GetIntConstant() is not available for O2K_ZEROOBJ (implies zero value).
            bool constantIsEqual =
                curAssertion.GetOp2().KindIs(O2K_ZEROOBJ) || (curAssertion.GetOp2().GetIntConstant() == cnsVal);
            bool assertionIsEqual = curAssertion.KindIs(OAK_EQUAL);

            if (constantIsEqual || assertionIsEqual)
            {
                return index;
            }
        }
    }
    return NO_ASSERTION_INDEX;
}

//------------------------------------------------------------------------
// optGlobalAssertionIsEqualOrNotEqual: Look for an assertion in the specified
//        set that is one of op1 == op1, op1 != op2, or *op1 == op2,
//        where equality is based on value numbers.
//
// Arguments:
//      assertions: bit vector describing set of assertions
//      op1, op2:    the treen nodes in question
//
// Returns:
//      Index of first matching assertion, or NO_ASSERTION_INDEX if no
//      assertions in the set are matches.
//
// Notes:
//      Assertions based on *op1 are the result of exact type tests and are
//      only returned when op1 is a local var with ref type and the assertion
//      is an exact type equality.
//
AssertionIndex Compiler::optGlobalAssertionIsEqualOrNotEqual(ASSERT_VALARG_TP assertions, GenTree* op1, GenTree* op2)
{
    if (BitVecOps::IsEmpty(apTraits, assertions) || !optCanPropEqual)
    {
        return NO_ASSERTION_INDEX;
    }
    BitVecOps::Iter iter(apTraits, assertions);
    unsigned        index = 0;
    while (iter.NextElem(&index))
    {
        AssertionIndex assertionIndex = GetAssertionIndex(index);
        if (assertionIndex > optAssertionCount)
        {
            break;
        }
        const AssertionDsc& curAssertion = optGetAssertion(assertionIndex);
        if (!curAssertion.CanPropEqualOrNotEqual())
        {
            continue;
        }

        if ((curAssertion.GetOp1().GetVN() == vnStore->VNConservativeNormalValue(op1->gtVNPair)) &&
            (curAssertion.GetOp2().GetVN() == vnStore->VNConservativeNormalValue(op2->gtVNPair)))
        {
            return assertionIndex;
        }

        // Look for matching exact type assertions based on vtable accesses. E.g.:
        //
        //   op1:       VNF_InvariantNonNullLoad(myObj) or in other words: a vtable access
        //   op2:       'MyType' class handle
        //   Assertion: 'myObj's type is exactly MyType
        //
        if (curAssertion.KindIs(OAK_EQUAL) && curAssertion.GetOp1().KindIs(O1K_EXACT_TYPE) &&
            (curAssertion.GetOp2().GetVN() == vnStore->VNConservativeNormalValue(op2->gtVNPair)) &&
            op1->TypeIs(TYP_I_IMPL))
        {
            VNFuncApp funcApp;
            if (vnStore->GetVNFunc(vnStore->VNConservativeNormalValue(op1->gtVNPair), &funcApp) &&
                (funcApp.m_func == VNF_InvariantNonNullLoad) && (curAssertion.GetOp1().GetVN() == funcApp.m_args[0]))
            {
                return assertionIndex;
            }
        }
    }
    return NO_ASSERTION_INDEX;
}

/*****************************************************************************
 *
 *  Given a tree consisting of a RelOp and a set of available assertions
 *  we try to propagate an assertion and modify the RelOp tree if we can.
 *  We pass in the root of the tree via 'stmt', for local copy prop 'stmt' will be nullptr
 *  Returns the modified tree, or nullptr if no assertion prop took place
 */

GenTree* Compiler::optAssertionProp_RelOp(ASSERT_VALARG_TP assertions,
                                          GenTree*         tree,
                                          Statement*       stmt,
                                          BasicBlock*      block)
{
    assert(tree->OperIsCompare());

    if (!optLocalAssertionProp)
    {
        // If global assertion prop then use value numbering.
        return optAssertionPropGlobal_RelOp(assertions, tree, stmt, block);
    }

    //
    // Currently only GT_EQ or GT_NE are supported Relops for local AssertionProp
    //
    if (!tree->OperIs(GT_EQ, GT_NE))
    {
        return nullptr;
    }

    // If local assertion prop then use variable based prop.
    return optAssertionPropLocal_RelOp(assertions, tree, stmt);
}

//------------------------------------------------------------------------
// optAssertionProp: try and optimize a relop via assertion propagation
//
// Arguments:
//   assertions  - set of live assertions
//   tree        - tree to possibly optimize
//   stmt        - statement containing the tree
//   block       - the block containing the statement
//
// Returns:
//   The modified tree, or nullptr if no assertion prop took place.
//
GenTree* Compiler::optAssertionPropGlobal_RelOp(ASSERT_VALARG_TP assertions,
                                                GenTree*         tree,
                                                Statement*       stmt,
                                                BasicBlock*      block)
{
    assert(!optLocalAssertionProp);

    GenTree* newTree = tree;
    GenTree* op1     = tree->AsOp()->gtOp1;
    GenTree* op2     = tree->AsOp()->gtOp2;

    // Can we fold "X relop 0" based on assertions?
    if (op2->IsIntegralConst(0) && tree->OperIsCmpCompare())
    {
        bool isNonZero, isNeverNegative;
        optAssertionProp_RangeProperties(assertions, op1, stmt, block, &isNonZero, &isNeverNegative);

        if (tree->OperIs(GT_GE, GT_LT) && isNeverNegative)
        {
            // Assertions: X >= 0
            //
            // X >= 0 --> true
            // X < 0  --> false
            newTree = tree->OperIs(GT_GE) ? gtNewTrue() : gtNewFalse();
        }
        else if (tree->OperIs(GT_GT, GT_LE) && isNeverNegative && isNonZero)
        {
            // Assertions: X > 0
            //
            // X > 0  --> true
            // X <= 0 --> false
            newTree = tree->OperIs(GT_GT) ? gtNewTrue() : gtNewFalse();
        }
        else if (tree->OperIs(GT_EQ, GT_NE) && isNonZero)
        {
            // Assertions: X != 0
            //
            // X != 0 --> true
            // X == 0 --> false
            newTree = tree->OperIs(GT_NE) ? gtNewTrue() : gtNewFalse();
        }

        if (newTree != tree)
        {
            newTree = gtWrapWithSideEffects(newTree, tree, GTF_ALL_EFFECT);
            return optAssertionProp_Update(newTree, tree, stmt);
        }
    }

    // Check if we have an assertion that exactly matches the relop.
    ValueNum relopVN = optConservativeNormalVN(tree);
    if (!BitVecOps::IsEmpty(apTraits, assertions))
    {
        ValueNum op1VN   = optConservativeNormalVN(op1);
        ValueNum op2VN   = optConservativeNormalVN(op2);
        ValueNum falseVN = vnStore->VNZeroForType(TYP_INT);

        BitVecOps::Iter iter(apTraits, assertions);
        unsigned        index = 0;
        while (iter.NextElem(&index))
        {
            const AssertionDsc& curAssertion = optGetAssertion(GetAssertionIndex(index));

            // Look for a relop-like assertion that matches the current relop exactly.
            // Example: currentTree is "X >= Y" and we have an assertion "X >= Y" (or its inverse "X < Y").
            //
            if (curAssertion.IsRelop() && (curAssertion.GetOp1().GetVN() == op1VN) &&
                // O2K_CHECKED_BOUND_ADD_CNS means op2 is decomposed into op2.vn being checked bound
                // and op2.cns being the constant offset. We assemble the original relop VN if we want.
                // For now, just skip such assertions here.
                !curAssertion.GetOp2().KindIs(O2K_CHECKED_BOUND_ADD_CNS) && (curAssertion.GetOp2().GetVN() == op2VN))
            {
                bool       isUnsigned;
                genTreeOps assertionOper = AssertionDsc::ToCompareOper(curAssertion.GetKind(), &isUnsigned);

                if (tree->OperIs(assertionOper, GenTree::ReverseRelop(assertionOper)) &&
                    (tree->IsUnsigned() == isUnsigned))
                {
                    newTree = gtNewIconNode(tree->OperIs(assertionOper) ? 1 : 0);
                }
            }
            // Look for an equality assertion involving the entire relop and zero.
            // Example: currentTree is "X >= Y" and we have an assertion "(X >= Y) == 0"
            //
            else if (curAssertion.CanPropEqualOrNotEqual() && (curAssertion.GetOp1().GetVN() == relopVN) &&
                     (curAssertion.GetOp2().GetVN() == falseVN))
            {
                newTree = gtNewIconNode(curAssertion.KindIs(OAK_EQUAL) ? 0 : 1);
            }

            if (tree != newTree)
            {
                JITDUMP("Found matching assertion #%02u for tree %06u.", index, dspTreeID(tree));
                newTree = gtWrapWithSideEffects(newTree, tree, GTF_ALL_EFFECT);
                JITDUMP(". Folded into:\n");
                DISPTREE(newTree);
                return optAssertionProp_Update(newTree, tree, stmt);
            }
        }
    }

    // See if we can fold the relop based on range information.
    // We don't need the op1->TypeIs(TYP_INT) check, but it seems to improve the TP quite a bit.
    if (op1->TypeIs(TYP_INT))
    {
        Range relopRange = RangeCheck::GetRangeFromAssertions(this, relopVN, assertions);

        int relopResult;
        if (relopRange.IsSingleValueConstant(&relopResult))
        {
            assert((relopResult == 0) || (relopResult == 1));
            newTree = gtWrapWithSideEffects(relopResult == 1 ? gtNewTrue() : gtNewFalse(), tree, GTF_ALL_EFFECT);
            return optAssertionProp_Update(newTree, tree, stmt);
        }
    }

    // Else check if we have an equality check involving a local or an indir
    if (!tree->OperIs(GT_EQ, GT_NE))
    {
        return nullptr;
    }

    // Bail out if op1 is not side effect free. Note we'll be bashing it below, unlike op2.
    if ((op1->gtFlags & GTF_SIDE_EFFECT) != 0)
    {
        return nullptr;
    }

    if (!op1->OperIs(GT_LCL_VAR, GT_IND))
    {
        return nullptr;
    }

    // See if we have "PHI ==/!= null" tree. If so, we iterate over all PHI's arguments,
    // and if all of them are known to be non-null, we can bash the comparison to true/false.
    if (op2->IsIntegralConst(0) && op1->TypeIs(TYP_REF))
    {
        JITDUMP("Checking PHI [%06u] arguments for non-nullness\n", dspTreeID(op1))
        auto visitor = [this](ValueNum reachingVN, ASSERT_TP reachingAssertions) {
            return optAssertionVNIsNonNull(reachingVN, reachingAssertions) ? AssertVisit::Continue : AssertVisit::Abort;
        };

        ValueNum op1vn = vnStore->VNConservativeNormalValue(op1->gtVNPair);
        if (optVisitReachingAssertions(op1vn, visitor) == AssertVisit::Continue)
        {
            JITDUMP("... all of PHI's arguments are never null!\n");
            assert(newTree->OperIs(GT_EQ, GT_NE));
            newTree = tree->OperIs(GT_EQ) ? gtNewIconNode(0) : gtNewIconNode(1);
            return optAssertionProp_Update(newTree, tree, stmt);
        }
    }

    // Find an equal or not equal assertion involving "op1" and "op2".
    AssertionIndex index = optGlobalAssertionIsEqualOrNotEqual(assertions, op1, op2);

    if (index == NO_ASSERTION_INDEX)
    {
        return nullptr;
    }

    const AssertionDsc& curAssertion         = optGetAssertion(index);
    bool                assertionKindIsEqual = curAssertion.KindIs(OAK_EQUAL);

    // Allow or not to reverse condition for OAK_NOT_EQUAL assertions.
    bool allowReverse = true;

    // If the assertion involves "op2" and it is a constant, then check if "op1" also has a constant value.
    ValueNum vnCns = vnStore->VNConservativeNormalValue(op2->gtVNPair);
    if (vnStore->IsVNConstant(vnCns))
    {
#ifdef DEBUG
        if (verbose)
        {
            printf("\nVN relop based constant assertion prop in " FMT_BB ":\n", compCurBB->bbNum);
            printf("Assertion index=#%02u: ", index);
            printTreeID(op1);
            printf(" %s ", assertionKindIsEqual ? "==" : "!=");
            if (genActualType(op1->TypeGet()) == TYP_INT)
            {
                printf("%d\n", vnStore->ConstantValue<int>(vnCns));
            }
            else if (op1->TypeIs(TYP_LONG))
            {
                printf("%lld\n", vnStore->ConstantValue<INT64>(vnCns));
            }
            else if (op1->TypeIs(TYP_DOUBLE))
            {
                printf("%f\n", vnStore->ConstantValue<double>(vnCns));
            }
            else if (op1->TypeIs(TYP_FLOAT))
            {
                printf("%f\n", vnStore->ConstantValue<float>(vnCns));
            }
            else if (op1->TypeIs(TYP_REF))
            {
                // The only constant of TYP_REF that ValueNumbering supports is 'null'
                if (vnStore->ConstantValue<size_t>(vnCns) == 0)
                {
                    printf("null\n");
                }
                else
                {
                    printf("%d (gcref)\n", static_cast<target_ssize_t>(vnStore->ConstantValue<size_t>(vnCns)));
                }
            }
            else if (op1->TypeIs(TYP_BYREF))
            {
                printf("%d (byref)\n", static_cast<target_ssize_t>(vnStore->ConstantValue<size_t>(vnCns)));
            }
            else
            {
                printf("??unknown\n");
            }
            gtDispTree(tree, nullptr, nullptr, true);
        }
#endif
        // Change the oper to const.
        if (genActualType(op1->TypeGet()) == TYP_INT)
        {
            op1->BashToConst(vnStore->ConstantValue<int>(vnCns));

            if (vnStore->IsVNHandle(vnCns))
            {
                op1->gtFlags |= (vnStore->GetHandleFlags(vnCns) & GTF_ICON_HDL_MASK);
            }
        }
        else if (op1->TypeIs(TYP_LONG))
        {
            op1->BashToConst(vnStore->ConstantValue<INT64>(vnCns));

            if (vnStore->IsVNHandle(vnCns))
            {
                op1->gtFlags |= (vnStore->GetHandleFlags(vnCns) & GTF_ICON_HDL_MASK);
            }
        }
        else if (op1->TypeIs(TYP_DOUBLE))
        {
            double constant = vnStore->ConstantValue<double>(vnCns);
            op1->BashToConst(constant);

            // Nothing can be equal to NaN. So if IL had "op1 == NaN", then we already made op1 NaN,
            // which will yield a false correctly. Instead if IL had "op1 != NaN", then we already
            // made op1 NaN which will yield a true correctly. Note that this is irrespective of the
            // assertion we have made.
            allowReverse = !FloatingPointUtils::isNaN(constant);
        }
        else if (op1->TypeIs(TYP_FLOAT))
        {
            float constant = vnStore->ConstantValue<float>(vnCns);
            op1->BashToConst(constant);

            // See comments for TYP_DOUBLE.
            allowReverse = !FloatingPointUtils::isNaN(constant);
        }
        else if (op1->TypeIs(TYP_REF))
        {
            op1->BashToConst(static_cast<target_ssize_t>(vnStore->ConstantValue<size_t>(vnCns)), TYP_REF);
        }
        else if (op1->TypeIs(TYP_BYREF))
        {
            op1->BashToConst(static_cast<target_ssize_t>(vnStore->ConstantValue<size_t>(vnCns)), TYP_BYREF);
        }
        else
        {
            noway_assert(!"unknown type in Global_RelOp");
        }

        op1->gtVNPair.SetBoth(vnCns); // Preserve the ValueNumPair, as BashToConst will clear it.

        // set foldResult to either 0 or 1
        bool foldResult = assertionKindIsEqual;
        if (tree->OperIs(GT_NE))
        {
            foldResult = !foldResult;
        }

        // Set the value number on the relop to 1 (true) or 0 (false)
        if (foldResult)
        {
            tree->gtVNPair.SetBoth(vnStore->VNOneForType(TYP_INT));
        }
        else
        {
            tree->gtVNPair.SetBoth(vnStore->VNZeroForType(TYP_INT));
        }
    }
    // If the assertion involves "op2" and "op1" is also a local var, then just morph the tree.
    else if (op1->OperIs(GT_LCL_VAR) && op2->OperIs(GT_LCL_VAR))
    {
#ifdef DEBUG
        if (verbose)
        {
            printf("\nVN relop based copy assertion prop in " FMT_BB ":\n", compCurBB->bbNum);
            printf("Assertion index=#%02u: V%02d.%02d %s V%02d.%02d\n", index, op1->AsLclVar()->GetLclNum(),
                   op1->AsLclVar()->GetSsaNum(),
                   curAssertion.KindIs(OAK_EQUAL) ? "==" : "!=", op2->AsLclVar()->GetLclNum(),
                   op2->AsLclVar()->GetSsaNum());
            gtDispTree(tree, nullptr, nullptr, true);
        }
#endif
        // If floating point, don't just substitute op1 with op2, this won't work if
        // op2 is NaN. Just turn it into a "true" or "false" yielding expression.
        if (op1->TypeIs(TYP_FLOAT, TYP_DOUBLE))
        {
            // Note we can't trust the OAK_EQUAL as the value could end up being a NaN
            // violating the assertion. However, we create OAK_EQUAL assertions for floating
            // point only on JTrue nodes, so if the condition held earlier, it will hold
            // now. We don't create OAK_EQUAL assertion on floating point from stores
            // because we depend on value num which would constant prop the NaN.
            op1->BashToConst(0.0, op1->TypeGet());
            op2->BashToConst(0.0, op2->TypeGet());
        }
        // Change the op1 LclVar to the op2 LclVar
        else
        {
            noway_assert(varTypeIsIntegralOrI(op1->TypeGet()));
            op1->AsLclVarCommon()->SetLclNum(op2->AsLclVarCommon()->GetLclNum());
            op1->AsLclVarCommon()->SetSsaNum(op2->AsLclVarCommon()->GetSsaNum());
        }
    }
    else
    {
        return nullptr;
    }

    // Finally reverse the condition, if we have a not equal assertion.
    if (allowReverse && curAssertion.KindIs(OAK_NOT_EQUAL))
    {
        gtReverseCond(tree);
    }

    newTree = fgMorphTree(tree);

#ifdef DEBUG
    if (verbose)
    {
        gtDispTree(newTree, nullptr, nullptr, true);
    }
#endif

    return optAssertionProp_Update(newTree, tree, stmt);
}

/*************************************************************************************
 *
 *  Given the set of "assertions" to look up a relop assertion about the relop "tree",
 *  perform local variable name based relop assertion propagation on the tree.
 *
 */
GenTree* Compiler::optAssertionPropLocal_RelOp(ASSERT_VALARG_TP assertions, GenTree* tree, Statement* stmt)
{
    assert(tree->OperIs(GT_EQ) || tree->OperIs(GT_NE));

    GenTree* op1 = tree->AsOp()->gtOp1;
    GenTree* op2 = tree->AsOp()->gtOp2;

    // For Local AssertionProp we only can fold when op1 is a GT_LCL_VAR
    if (!op1->OperIs(GT_LCL_VAR))
    {
        return nullptr;
    }

    // For Local AssertionProp we only can fold when op2 is a GT_CNS_INT
    if (!op2->OperIs(GT_CNS_INT))
    {
        return nullptr;
    }

    optOp1Kind op1Kind = O1K_LCLVAR;
    optOp2Kind op2Kind = O2K_CONST_INT;
    ssize_t    cnsVal  = op2->AsIntCon()->gtIconVal;
    var_types  cmpType = op1->TypeGet();

    // Don't try to fold/optimize Floating Compares; there are multiple zero values.
    if (varTypeIsFloating(cmpType))
    {
        return nullptr;
    }

    // Find an equal or not equal assertion about op1 var.
    unsigned lclNum = op1->AsLclVarCommon()->GetLclNum();

    // Make sure the local is not truncated.
    if (!op1->TypeIs(lvaGetRealType(lclNum)))
    {
        return nullptr;
    }

    noway_assert(lclNum < lvaCount);
    AssertionIndex index = optLocalAssertionIsEqualOrNotEqual(op1Kind, lclNum, op2Kind, cnsVal, assertions);

    if (index == NO_ASSERTION_INDEX)
    {
        return nullptr;
    }

    const AssertionDsc& curAssertion = optGetAssertion(index);

    bool assertionKindIsEqual = curAssertion.KindIs(OAK_EQUAL);
    bool constantIsEqual      = false;

    if (genTypeSize(cmpType) == TARGET_POINTER_SIZE)
    {
        constantIsEqual = (curAssertion.GetOp2().GetIntConstant() == cnsVal);
    }
#ifdef TARGET_64BIT
    else if (genTypeSize(cmpType) == sizeof(INT32))
    {
        // Compare the low 32-bits only
        constantIsEqual = (((INT32)curAssertion.GetOp2().GetIntConstant()) == ((INT32)cnsVal));
    }
#endif
    else
    {
        // We currently don't fold/optimize when the GT_LCL_VAR has been cast to a small type
        return nullptr;
    }

    noway_assert(constantIsEqual || assertionKindIsEqual);

#ifdef DEBUG
    if (verbose)
    {
        printf("\nAssertion prop for index #%02u in " FMT_BB ":\n", index, compCurBB->bbNum);
        gtDispTree(tree, nullptr, nullptr, true);
    }
#endif

    // Return either CNS_INT 0 or CNS_INT 1.
    bool foldResult = (constantIsEqual == assertionKindIsEqual);
    if (tree->OperIs(GT_NE))
    {
        foldResult = !foldResult;
    }

    op2->BashToConst((ssize_t)foldResult, TYP_INT);

    return optAssertionProp_Update(op2, tree, stmt);
}

//------------------------------------------------------------------------
// optAssertionProp_Cast: Propagate assertion for a cast, possibly removing it.
//
// The function use "optAssertionIsSubrange" to find an assertion which claims the
// cast's operand (only locals are supported) is a subrange of the "input" range
// for the cast, as computed by "IntegralRange::ForCastInput", and, if such
// assertion is found, act on it - either remove the cast if it is not changing
// representation, or try to remove the GTF_OVERFLOW flag from it.
//
// Arguments:
//    assertions - the set of live assertions
//    cast       - the cast for which to propagate the assertions
//    stmt       - statement "cast" is a part of, "nullptr" for local prop
//    block      - the block containing the statement
//
// Return Value:
//    The, possibly modified, cast tree or "nullptr" if no propagation took place.
//
GenTree* Compiler::optAssertionProp_Cast(ASSERT_VALARG_TP assertions,
                                         GenTreeCast*     cast,
                                         Statement*       stmt,
                                         BasicBlock*      block)
{
    GenTree* op1 = cast->CastOp();

    // Bail if we have a cast involving floating point or GC types.
    if (!varTypeIsIntegral(cast) || !varTypeIsIntegral(op1))
    {
        return nullptr;
    }

    // Skip over a GT_COMMA node(s), if necessary to get to the lcl.
    GenTree* lcl = op1->gtEffectiveVal();

    // Try and see if we can make this cast into a cheaper zero-extending version
    // if the input is known to be non-negative.
    if (!cast->IsUnsigned() && genActualTypeIsInt(lcl) && cast->TypeIs(TYP_LONG) && (TARGET_POINTER_SIZE == 8))
    {
        bool isKnownNonZero;
        bool isKnownNonNegative;
        optAssertionProp_RangeProperties(assertions, lcl, stmt, block, &isKnownNonZero, &isKnownNonNegative);
        if (isKnownNonNegative)
        {
            cast->SetUnsigned();
        }
    }

    bool removeCast = false;
    if (!optLocalAssertionProp)
    {
        // Get the non-overflowing input range for a cast. ForCastInput takes care of special cases like
        // small types and IsUnsigned flag for checked casts.
        IntegralRange castRng = IntegralRange::ForCastInput(cast);
        int64_t       castLo  = IntegralRange::SymbolicToRealValue(castRng.GetLowerBound());
        int64_t       castHi  = IntegralRange::SymbolicToRealValue(castRng.GetUpperBound());
        if (FitsIn<int>(castLo) && FitsIn<int>(castHi))
        {
            Range castToTypeRange = Range(Limit(Limit::keConstant, (int)castLo), Limit(Limit::keConstant, (int)castHi));
            if (castToTypeRange.IsConstantRange() && (genActualType(cast->CastOp()) == TYP_INT))
            {
                ValueNum castOpVN  = optConservativeNormalVN(cast->CastOp());
                Range    castOpRng = RangeCheck::GetRangeFromAssertions(this, castOpVN, assertions);
                assert(castOpRng.IsConstantRange());

                int castFromLo = castOpRng.LowerLimit().GetConstant();
                int castFromHi = castOpRng.UpperLimit().GetConstant();
                int castToLo   = castToTypeRange.LowerLimit().GetConstant();
                int castToHi   = castToTypeRange.UpperLimit().GetConstant();

                if (castOpRng.IsConstantRange() && (castFromLo >= castToLo) && (castFromHi <= castToHi))
                {
                    removeCast = true;
                    if (!lcl->OperIs(GT_LCL_VAR))
                    {
                        // We cannot remove the cast, but can we just remove the GTF_OVERFLOW flag?
                        if (!cast->gtOverflow())
                        {
                            return nullptr;
                        }

                        // Just clear the overflow flag then.
                        JITDUMP("Clearing overflow flag for cast %06u based on assertions.\n", dspTreeID(cast));
                        cast->ClearOverflow();
                        return optAssertionProp_Update(cast, cast, stmt);
                    }
                }
            }
        }
    }
    else
    {
        removeCast = lcl->OperIs(GT_LCL_VAR) &&
                     optAssertionIsSubrange(lcl, IntegralRange::ForCastInput(cast), assertions) != NO_ASSERTION_INDEX;
    }

    if (removeCast)
    {
        LclVarDsc* varDsc = lvaGetDesc(lcl->AsLclVarCommon());

        // Representation-changing casts cannot be removed.
        if ((genActualType(cast) != genActualType(lcl)))
        {
            // Can we just remove the GTF_OVERFLOW flag?
            if (!cast->gtOverflow())
            {
                return nullptr;
            }

            JITDUMP("Clearing overflow flag for cast %06u based on assertions.\n", dspTreeID(cast));
            cast->ClearOverflow();
            return optAssertionProp_Update(cast, cast, stmt);
        }

        // We might need to retype a "normalize on load" local back to its original small type
        // so that codegen recognizes it needs to use narrow loads if the local ends up in memory.
        if (varDsc->lvNormalizeOnLoad())
        {
            // The Jit is known to play somewhat loose with small types, so let's restrict this code
            // to the pattern we know is "safe and sound", i. e. CAST(type <- LCL_VAR(int, V00 type)).
            if ((varDsc->TypeGet() != cast->CastToType()) || !lcl->TypeIs(TYP_INT))
            {
                return nullptr;
            }

            op1->ChangeType(varDsc->TypeGet());
        }

        JITDUMP("Removing cast %06u as redundant based on assertions.\n", dspTreeID(cast));
        return optAssertionProp_Update(op1, cast, stmt);
    }

    return nullptr;
}

/*****************************************************************************
 *
 *  Given a tree with an array bounds check node, eliminate it because it was
 *  checked already in the program.
 */
GenTree* Compiler::optAssertionProp_Comma(ASSERT_VALARG_TP assertions, GenTree* tree, Statement* stmt)
{
    // Remove the bounds check as part of the GT_COMMA node since we need parent pointer to remove nodes.
    // When processing visits the bounds check, it sets the throw kind to None if the check is redundant.
    if (tree->gtGetOp1()->OperIs(GT_BOUNDS_CHECK) && ((tree->gtGetOp1()->gtFlags & GTF_CHK_INDEX_INBND) != 0))
    {
        optRemoveCommaBasedRangeCheck(tree, stmt);
        return optAssertionProp_Update(tree, tree, stmt);
    }
    return nullptr;
}

//------------------------------------------------------------------------
// optAssertionProp_Ind: see if we can prove the indirection can't cause
//    and exception.
//
// 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:
//   stmt may be nullptr during local assertion prop
//
GenTree* Compiler::optAssertionProp_Ind(ASSERT_VALARG_TP assertions, GenTree* tree, Statement* stmt)
{
    assert(tree->OperIsIndirOrArrMetaData());

    bool updated = optNonNullAssertionProp_Ind(assertions, tree);
    if (tree->OperIs(GT_STOREIND))
    {
        updated |= optWriteBarrierAssertionProp_StoreInd(assertions, tree->AsStoreInd());
    }

    if (updated)
    {
        return optAssertionProp_Update(tree, tree, stmt);
    }
    return nullptr;
}

//------------------------------------------------------------------------
// optAssertionIsNonNull: see if we can prove a tree's value will be non-null
//   based on assertions
//
// Arguments:
//   op          - tree to check
//   assertions  - set of live assertions
//
// Return Value:
//   true if the tree's value will be non-null
//
bool Compiler::optAssertionIsNonNull(GenTree* op, ASSERT_VALARG_TP assertions)
{
    if (op->OperIs(GT_ADD) && op->AsOp()->gtGetOp2()->IsCnsIntOrI() &&
        !fgIsBigOffset(op->AsOp()->gtGetOp2()->AsIntCon()->IconValue()))
    {
        op = op->AsOp()->gtGetOp1();
    }

    // Fast path when we have a VN
    if (!optLocalAssertionProp && vnStore->IsKnownNonNull(op->gtVNPair.GetConservative()))
    {
        return true;
    }

    if (!optCanPropNonNull || BitVecOps::MayBeUninit(assertions))
    {
        return false;
    }

    op = op->gtEffectiveVal();
    if (!op->OperIs(GT_LCL_VAR))
    {
        return false;
    }

    // If local assertion prop use lcl comparison, else use VN comparison.
    if (!optLocalAssertionProp)
    {
        // Look at both the top-level vn, and
        // the vn we get by stripping off any constant adds.
        //
        ValueNum vn = vnStore->VNConservativeNormalValue(op->gtVNPair);
        if (vn == ValueNumStore::NoVN)
        {
            return false;
        }

        ValueNum       vnBase = vn;
        target_ssize_t offset = 0;
        vnStore->PeelOffsets(&vnBase, &offset);

        // Check each assertion to find if we have a vn != null assertion.
        //
        BitVecOps::Iter iter(apTraits, assertions);
        unsigned        index = 0;
        while (iter.NextElem(&index))
        {
            AssertionIndex      assertionIndex = GetAssertionIndex(index);
            const AssertionDsc& curAssertion   = optGetAssertion(assertionIndex);
            if (curAssertion.CanPropNonNull() &&
                ((curAssertion.GetOp1().GetVN() == vn) || (curAssertion.GetOp1().GetVN() == vnBase)))
            {
                return true;
            }
        }
    }
    else
    {
        // Find live assertions related to lclNum
        //
        unsigned const lclNum      = op->AsLclVarCommon()->GetLclNum();
        ASSERT_TP      apDependent = BitVecOps::Intersection(apTraits, GetAssertionDep(lclNum), assertions);

        // Scan those looking for a suitable assertion
        //
        BitVecOps::Iter iter(apTraits, apDependent);
        unsigned        index = 0;
        while (iter.NextElem(&index))
        {
            AssertionIndex      assertionIndex = GetAssertionIndex(index);
            const AssertionDsc& curAssertion   = optGetAssertion(assertionIndex);

            if (curAssertion.KindIs(OAK_NOT_EQUAL) &&          // kind
                curAssertion.GetOp1().KindIs(O1K_LCLVAR) &&    // op1
                curAssertion.GetOp2().KindIs(O2K_CONST_INT) && // op2
                (curAssertion.GetOp1().GetLclNum() == lclNum) && (curAssertion.GetOp2().GetIntConstant() == 0))
            {
                return true;
            }
        }
    }
    return false;
}

//------------------------------------------------------------------------
// optAssertionVNIsNonNull: See if we can prove that the value of a VN is
// non-null using assertions.
//
// Arguments:
//   vn         - VN to check
//   assertions - set of live assertions
//
// Return Value:
//   True if the VN could be proven non-null.
//
bool Compiler::optAssertionVNIsNonNull(ValueNum vn, ASSERT_VALARG_TP assertions)
{
    if (vnStore->IsKnownNonNull(vn))
    {
        return true;
    }

    if (!BitVecOps::MayBeUninit(assertions) && optAssertionHasAssertionsForVN(vn))
    {
        BitVecOps::Iter iter(apTraits, assertions);
        unsigned        index = 0;
        while (iter.NextElem(&index))
        {
            const AssertionDsc& curAssertion = optGetAssertion(GetAssertionIndex(index));
            if (curAssertion.CanPropNonNull() && curAssertion.GetOp1().GetVN() == vn)
            {
                return true;
            }
        }
    }

    return false;
}

/*****************************************************************************
 *
 *  Given a tree consisting of a call and a set of available assertions, we
 *  try to propagate a non-null assertion and modify the Call tree if we can.
 *  Returns the modified tree, or nullptr if no assertion prop took place.
 *
 */
GenTree* Compiler::optNonNullAssertionProp_Call(ASSERT_VALARG_TP assertions, GenTreeCall* call)
{
    if (!call->NeedsNullCheck())
    {
        return nullptr;
    }

    GenTree* op1 = call->gtArgs.GetThisArg()->GetNode();
    noway_assert(op1 != nullptr);

    if (optAssertionIsNonNull(op1, assertions))
    {
        JITDUMP("Non-null assertion prop for tree [%06d] in " FMT_BB ":\n", dspTreeID(op1), compCurBB->bbNum);

        call->gtFlags &= ~GTF_CALL_NULLCHECK;
        call->gtFlags &= ~GTF_EXCEPT;
        noway_assert(call->gtFlags & GTF_SIDE_EFFECT);
        return call;
    }

    return nullptr;
}

//------------------------------------------------------------------------
// optNonNullAssertionProp_Ind: Possibly prove an indirection non-faulting.
//
// Arguments:
//    assertions - Active assertions
//    indir      - The indirection
//
// Return Value:
//    Whether the indirection was found to be non-faulting and marked as such.
//
bool Compiler::optNonNullAssertionProp_Ind(ASSERT_VALARG_TP assertions, GenTree* indir)
{
    assert(indir->OperIsIndirOrArrMetaData());

    if ((indir->gtFlags & GTF_EXCEPT) == 0)
    {
        return false;
    }

    if (optAssertionIsNonNull(indir->GetIndirOrArrMetaDataAddr(), assertions))
    {
        JITDUMP("Non-null assertion prop for indirection [%06d] in " FMT_BB ":\n", dspTreeID(indir), compCurBB->bbNum);

        indir->gtFlags &= ~GTF_EXCEPT;
        indir->gtFlags |= GTF_IND_NONFAULTING;

        // Set this flag to prevent reordering
        indir->SetHasOrderingSideEffect();

        return true;
    }

    return false;
}

//------------------------------------------------------------------------
// GetWriteBarrierForm: Determinate the exact type of write barrier required for the
//    given address.
//
// Arguments:
//    vnStore - ValueNumStore object
//    vn      - VN of the address
//
// Return Value:
//    Exact type of write barrier required for the given address.
//
static GCInfo::WriteBarrierForm GetWriteBarrierForm(Compiler* comp, ValueNum vn)
{
    ValueNumStore*  vnStore = comp->vnStore;
    const var_types type    = vnStore->TypeOfVN(vn);
    if (type == TYP_REF)
    {
        return GCInfo::WriteBarrierForm::WBF_BarrierUnchecked;
    }
    if (type != TYP_BYREF)
    {
        return GCInfo::WriteBarrierForm::WBF_BarrierUnknown;
    }

    VNFuncApp funcApp;
    if (vnStore->GetVNFunc(vnStore->VNNormalValue(vn), &funcApp))
    {
        if (funcApp.m_func == VNF_PtrToArrElem)
        {
            // Check whether the array is on the heap
            ValueNum arrayVN = funcApp.m_args[1];
            return GetWriteBarrierForm(comp, arrayVN);
        }
        if (funcApp.m_func == VNF_PtrToLoc)
        {
            // Pointer to a local
            return GCInfo::WriteBarrierForm::WBF_NoBarrier;
        }
        if ((funcApp.m_func == VNF_PtrToStatic) && vnStore->IsVNHandle(funcApp.m_args[0], GTF_ICON_STATIC_BOX_PTR))
        {
            // Boxed static - always on the heap
            return GCInfo::WriteBarrierForm::WBF_BarrierUnchecked;
        }
        if (funcApp.m_func == VNFunc(GT_ADD))
        {
            // Check arguments of the GT_ADD
            // To make it conservative, we require one of the arguments to be a constant, e.g.:
            //
            //   addressOfLocal + cns    -> NoBarrier
            //   cns + addressWithinHeap -> BarrierUnchecked
            //
            // Because "addressOfLocal + nativeIntVariable" could be in fact a pointer to the heap.
            // if "nativeIntVariable == addressWithinHeap - addressOfLocal".
            //
            if (vnStore->IsVNConstantNonHandle(funcApp.m_args[0]))
            {
                return GetWriteBarrierForm(comp, funcApp.m_args[1]);
            }
            if (vnStore->IsVNConstantNonHandle(funcApp.m_args[1]))
            {
                return GetWriteBarrierForm(comp, funcApp.m_args[0]);
            }
        }
    }
    return GCInfo::WriteBarrierForm::WBF_BarrierUnknown;
}

//------------------------------------------------------------------------
// optWriteBarrierAssertionProp_StoreInd: This function assists gcIsWriteBarrierCandidate with help of
//    assertions and VNs since CSE may "hide" addresses/values under locals, making it impossible for
//    gcIsWriteBarrierCandidate to determine the exact type of write barrier required
//    (it's too late for it to rely on VNs).
//
//    There are three cases we handle here:
//     * Target is not on the heap - no write barrier is required
//     * Target could be on the heap, but the value being stored doesn't require any write barrier
//     * Target is definitely on the heap - checked (slower) write barrier is not required
//
// Arguments:
//    assertions - Active assertions
//    indir      - The STOREIND node
//
// Return Value:
//    Whether the exact type of write barrier was determined and marked on the STOREIND node.
//
bool Compiler::optWriteBarrierAssertionProp_StoreInd(ASSERT_VALARG_TP assertions, GenTreeStoreInd* indir)
{
    const GenTree* value = indir->AsIndir()->Data();
    const GenTree* addr  = indir->AsIndir()->Addr();

    if (optLocalAssertionProp || !indir->TypeIs(TYP_REF) || !value->TypeIs(TYP_REF) ||
        ((indir->gtFlags & GTF_IND_TGT_NOT_HEAP) != 0))
    {
        return false;
    }

    GCInfo::WriteBarrierForm barrierType = GCInfo::WriteBarrierForm::WBF_BarrierUnknown;

    // First, analyze the value being stored
    auto vnVisitor = [this](ValueNum vn) -> ValueNumStore::VNVisit {
        if ((vn == ValueNumStore::VNForNull()) || vnStore->IsVNObjHandle(vn))
        {
            // No write barrier is required for null or nongc object handles as values
            return ValueNumStore::VNVisit::Continue;
        }
        return ValueNumStore::VNVisit::Abort;
    };

    if (vnStore->VNVisitReachingVNs(value->gtVNPair.GetConservative(), vnVisitor) == ValueNumStore::VNVisit::Continue)
    {
        barrierType = GCInfo::WriteBarrierForm::WBF_NoBarrier;
    }
    // Next, analyze the address if we haven't already determined the barrier type from the value
    else if ((indir->gtFlags & GTF_IND_TGT_HEAP) == 0)
    {
        // NOTE: we might want to inspect indirs with GTF_IND_TGT_HEAP flag as well - what if we can prove
        // that they actually need no barrier? But that comes with a TP regression.
        barrierType = GetWriteBarrierForm(this, addr->gtVNPair.GetConservative());
    }

    JITDUMP("Trying to determine the exact type of write barrier for STOREIND [%d06]: ", dspTreeID(indir));
    if (barrierType == GCInfo::WriteBarrierForm::WBF_NoBarrier)
    {
        JITDUMP("is not needed at all.\n");
        indir->gtFlags |= GTF_IND_TGT_NOT_HEAP;
        return true;
    }
    if (barrierType == GCInfo::WriteBarrierForm::WBF_BarrierUnchecked)
    {
        JITDUMP("unchecked is fine.\n");
        indir->gtFlags |= GTF_IND_TGT_HEAP;
        return true;
    }

    JITDUMP("unknown (checked).\n");
    return false;
}

/*****************************************************************************
 *
 *  Given a tree consisting of a call and a set of available assertions, we
 *  try to propagate an assertion and modify the Call tree if we can. Our
 *  current modifications are limited to removing the nullptrCHECK flag from
 *  the call.
 *  We pass in the root of the tree via 'stmt', for local copy prop 'stmt'
 *  will be nullptr. Returns the modified tree, or nullptr if no assertion prop
 *  took place.
 *
 */

GenTree* Compiler::optAssertionProp_Call(ASSERT_VALARG_TP assertions, GenTreeCall* call, Statement* stmt)
{
    if (optNonNullAssertionProp_Call(assertions, call))
    {
        return optAssertionProp_Update(call, call, stmt);
    }

    if (!optLocalAssertionProp && call->IsHelperCall())
    {
        const CorInfoHelpFunc helper = eeGetHelperNum(call->gtCallMethHnd);
        if ((helper == CORINFO_HELP_ISINSTANCEOFINTERFACE) || (helper == CORINFO_HELP_ISINSTANCEOFARRAY) ||
            (helper == CORINFO_HELP_ISINSTANCEOFCLASS) || (helper == CORINFO_HELP_ISINSTANCEOFANY) ||
            (helper == CORINFO_HELP_CHKCASTINTERFACE) || (helper == CORINFO_HELP_CHKCASTARRAY) ||
            (helper == CORINFO_HELP_CHKCASTCLASS) || (helper == CORINFO_HELP_CHKCASTANY) ||
            (helper == CORINFO_HELP_CHKCASTCLASS_SPECIAL))
        {
            CallArg* castToCallArg = call->gtArgs.GetArgByIndex(0);
            CallArg* objCallArg    = call->gtArgs.GetArgByIndex(1);
            GenTree* castToArg     = castToCallArg->GetNode();
            GenTree* objArg        = objCallArg->GetNode();

            const unsigned index = optAssertionIsSubtype(objArg, castToArg, assertions);
            if (index != NO_ASSERTION_INDEX)
            {
                JITDUMP("\nDid VN based subtype prop for index #%02u in " FMT_BB ":\n", index, compCurBB->bbNum);
                DISPTREE(call);

                // if castObjArg is not simple, we replace the arg with a temp assignment and
                // continue using that temp - it allows us reliably extract all side effects
                objArg = fgMakeMultiUse(&objCallArg->NodeRef());
                objArg = gtWrapWithSideEffects(objArg, call, GTF_SIDE_EFFECT, true);
                return optAssertionProp_Update(objArg, call, stmt);
            }

            // Leave a hint for fgLateCastExpansion that obj is never null.
            // GTF_CALL_M_CAST_CAN_BE_EXPANDED check is to improve TP
            if (((call->gtCallMoreFlags & GTF_CALL_M_CAST_CAN_BE_EXPANDED) != 0) &&
                optAssertionIsNonNull(objArg, assertions))
            {
                call->gtCallMoreFlags |= GTF_CALL_M_CAST_OBJ_NONNULL;
                return optAssertionProp_Update(call, call, stmt);
            }
        }
    }

    return nullptr;
}

/*****************************************************************************
 *
 *  Given a tree with a bounds check, remove it if it has already been checked in the program flow.
 */
GenTree* Compiler::optAssertionProp_BndsChk(ASSERT_VALARG_TP assertions, GenTree* tree, Statement* stmt)
{
    if (optLocalAssertionProp || !optCanPropBndsChk)
    {
        return nullptr;
    }

    assert(tree->OperIs(GT_BOUNDS_CHECK));

#ifdef FEATURE_ENABLE_NO_RANGE_CHECKS
    if (JitConfig.JitNoRngChks())
    {
#ifdef DEBUG
        if (verbose)
        {
            printf("\nFlagging check redundant due to JitNoRngChks in " FMT_BB ":\n", compCurBB->bbNum);
            gtDispTree(tree, nullptr, nullptr, true);
        }
#endif // DEBUG
        tree->gtFlags |= GTF_CHK_INDEX_INBND;
        return nullptr;
    }
#endif // FEATURE_ENABLE_NO_RANGE_CHECKS

    GenTreeBoundsChk* arrBndsChk = tree->AsBoundsChk();
    ValueNum          vnCurIdx   = vnStore->VNConservativeNormalValue(arrBndsChk->GetIndex()->gtVNPair);
    ValueNum          vnCurLen   = vnStore->VNConservativeNormalValue(arrBndsChk->GetArrayLength()->gtVNPair);

    auto dropBoundsCheck = [&](INDEBUG(const char* reason)) -> GenTree* {
        JITDUMP("\nVN based redundant (%s) bounds check assertion prop in " FMT_BB ":\n", reason, compCurBB->bbNum);
        DISPTREE(tree);
        if (arrBndsChk != stmt->GetRootNode())
        {
            // Defer the removal.
            arrBndsChk->gtFlags |= GTF_CHK_INDEX_INBND;
            return nullptr;
        }

        GenTree* newTree = optRemoveStandaloneRangeCheck(arrBndsChk, stmt);
        return optAssertionProp_Update(newTree, arrBndsChk, stmt);
    };

    // First, check if we have arr[arr.Length - cns] when we know arr.Length is >= cns.
    VNFuncApp funcApp;
    if (vnStore->GetVNFunc(vnCurIdx, &funcApp) && (funcApp.m_func == VNF_ADD))
    {
        if (!vnStore->IsVNInt32Constant(funcApp.m_args[1]))
        {
            // Normalize constants to be on the right side
            std::swap(funcApp.m_args[0], funcApp.m_args[1]);
        }

        if ((funcApp.m_args[0] == vnCurLen) && vnStore->IsVNInt32Constant(funcApp.m_args[1]))
        {
            Range rng = RangeCheck::GetRangeFromAssertions(this, vnCurLen, assertions);
            // Lower known limit of ArrLen:
            const int lenLowerLimit = rng.LowerLimit().GetConstant();

            // Negative delta in the array access (ArrLen + -CNS)
            const int delta = vnStore->GetConstantInt32(funcApp.m_args[1]);
            if ((lenLowerLimit > 0) && (delta < 0) && (delta > INT_MIN) && (lenLowerLimit >= -delta))
            {
                return dropBoundsCheck(INDEBUG("a[a.Length-cns] when a.Length is known to be >= cns"));
            }
        }
    }

    BitVecOps::Iter iter(apTraits, assertions);
    unsigned        index = 0;
    while (iter.NextElem(&index))
    {
        AssertionIndex assertionIndex = GetAssertionIndex(index);
        if (assertionIndex > optAssertionCount)
        {
            break;
        }
        // If it is not a nothrow assertion, skip.
        const AssertionDsc& curAssertion = optGetAssertion(assertionIndex);
        if (!curAssertion.IsBoundsCheckNoThrow())
        {
            continue;
        }

        assert(curAssertion.GetOp2().GetCheckedBoundConstant() == 0);
        assert(curAssertion.GetOp2().IsCheckedBoundNeverNegative());

        // Do we have a previous range check involving the same 'vnLen' upper bound?
        if (curAssertion.GetOp2().GetCheckedBound() ==
            vnStore->VNConservativeNormalValue(arrBndsChk->GetArrayLength()->gtVNPair))
        {
            // Do we have the exact same lower bound 'vnIdx'?
            //       a[i] followed by a[i]
            if (curAssertion.GetOp1().GetVN() == vnCurIdx)
            {
                return dropBoundsCheck(INDEBUG("a[i] followed by a[i]"));
            }
            // Are we using zero as the index?
            // It can always be considered as redundant with any previous value
            //       a[*] followed by a[0]
            else if (vnCurIdx == vnStore->VNZeroForType(arrBndsChk->GetIndex()->TypeGet()))
            {
                return dropBoundsCheck(INDEBUG("a[*] followed by a[0]"));
            }
            else
            {
                // index1 doesn't have to be a constant, it can be a Phi each predecessor of which is a constant.
                // The smallest of those is what we can rely on. Example:
                //
                //  arr[cond ? 10 : 5] = 0;  // arr is at least 6 elements long
                //  arr[2] = 0;              // arr must be at least 3 elements long
                //
                // or even:
                //
                //  arr[cond ? 10 : 5] = 0; // arr is at least 6 elements long
                //  arr[cond ? 1 : 2] = 0;  // arr must be at least 3 elements long
                //
                auto tryGetMaxOrMinConst = [this](ValueNum vn, bool getMin, int* index) -> bool {
                    *index = getMin ? INT_MAX : INT_MIN;
                    return vnStore->VNVisitReachingVNs(vn,
                                                       [this, index, getMin](ValueNum vn) -> ValueNumStore::VNVisit {
                        int cns = 0;
                        if (vnStore->IsVNIntegralConstant(vn, &cns))
                        {
                            *index = getMin ? min(*index, cns) : max(*index, cns);
                            return ValueNumStore::VNVisit::Continue;
                        }
                        return ValueNumStore::VNVisit::Abort;
                    }) == ValueNumStore::VNVisit::Continue;
                };

                int index1;
                int index2;
                if (tryGetMaxOrMinConst(curAssertion.GetOp1().GetVN(), /*min*/ true, &index1) &&
                    tryGetMaxOrMinConst(vnCurIdx, /*max*/ false, &index2))
                {
                    // It can always be considered as redundant with any previous higher constant value
                    //       a[K1] followed by a[K2], with K2 >= 0 and K1 >= K2
                    if (index2 >= 0 && index1 >= index2)
                    {
                        return dropBoundsCheck(INDEBUG("a[K1] followed by a[K2], with K2 >= 0 and K1 >= K2"));
                    }
                }
            }
            // Extend this to remove additional redundant bounds checks:
            // i.e.  a[i+1] followed by a[i]  by using the VN(i+1) >= VN(i)
            //       a[i]   followed by a[j]  when j is known to be >= i
            //       a[i]   followed by a[5]  when i is known to be >= 5
        }
    }

    // Let's see if we can remove the bounds check based on the ranges.
    if ((genActualType(vnStore->TypeOfVN(vnCurIdx)) == TYP_INT) &&
        (genActualType(vnStore->TypeOfVN(vnCurLen)) == TYP_INT))
    {
        Range idxRng = RangeCheck::GetRangeFromAssertions(this, vnCurIdx, assertions);
        Range lenRng = RangeCheck::GetRangeFromAssertions(this, vnCurLen, assertions);
        if (idxRng.IsConstantRange() && lenRng.IsConstantRange())
        {
            // idx.lo >= 0 && idx.hi < len.lo --> drop bounds check
            if (idxRng.LowerLimit().GetConstant() >= 0 &&
                idxRng.UpperLimit().GetConstant() < lenRng.LowerLimit().GetConstant())
            {
                return dropBoundsCheck(INDEBUG("upper bound of index is less than lower bound of length"));
            }
        }
    }

    return nullptr;
}

/*****************************************************************************
 *
 *  Called when we have a successfully performed an assertion prop. We have
 *  the newTree in hand. This method will replace the existing tree in the
 *  stmt with the newTree.
 *
 */

GenTree* Compiler::optAssertionProp_Update(GenTree* newTree, GenTree* tree, Statement* stmt)
{
    assert(newTree != nullptr);
    assert(tree != nullptr);

    if (stmt == nullptr)
    {
        noway_assert(optLocalAssertionProp);
    }
    else
    {
        noway_assert(!optLocalAssertionProp);

        // If newTree == tree then we modified the tree in-place otherwise we have to
        // locate our parent node and update it so that it points to newTree.
        if (newTree != tree)
        {
            FindLinkData linkData = gtFindLink(stmt, tree);
            GenTree**    useEdge  = linkData.result;
            GenTree*     parent   = linkData.parent;
            noway_assert(useEdge != nullptr);

            if (parent != nullptr)
            {
                parent->ReplaceOperand(useEdge, newTree);

                // If the parent is a GT_IND and we replaced the child with a handle constant, we might need
                // to mark the GT_IND as invariant. This is the same as what gtNewIndOfIconHandleNode() does.
                // Review: should some kind of more general morphing take care of this?
                // Should this share code with gtNewIndOfIconHandleNode()?

                if (parent->OperIs(GT_IND) && newTree->IsIconHandle())
                {
                    GenTreeFlags iconFlags = newTree->GetIconHandleFlag();
                    if (GenTree::HandleKindDataIsInvariant(iconFlags))
                    {
                        parent->gtFlags |= GTF_IND_INVARIANT;
                        if (iconFlags == GTF_ICON_STR_HDL)
                        {
                            // String literals are never null
                            parent->gtFlags |= GTF_IND_NONNULL;
                        }
                    }
                }
            }
            else
            {
                // If there's no parent, the tree being replaced is the root of the
                // statement.
                assert((stmt->GetRootNode() == tree) && (stmt->GetRootNodePointer() == useEdge));
                stmt->SetRootNode(newTree);
            }

            // We only need to ensure that the gtNext field is set as it is used to traverse
            // to the next node in the tree. We will re-morph this entire statement in
            // optAssertionPropMain(). It will reset the gtPrev and gtNext links for all nodes.
            newTree->gtNext = tree->gtNext;

            // Old tree should not be referenced anymore.
            DEBUG_DESTROY_NODE(tree);
        }
    }

    // Record that we propagated the assertion.
    optAssertionPropagated            = true;
    optAssertionPropagatedCurrentStmt = true;

    return newTree;
}

//------------------------------------------------------------------------
// optAssertionProp: try and optimize a tree via assertion propagation
//
// Arguments:
//   assertions  - set of live assertions
//   tree        - tree to possibly optimize
//   stmt        - statement containing the tree
//   block       - block containing the statement
//
// Returns:
//   The modified tree, or nullptr if no assertion prop took place.
//
// Notes:
//   stmt may be nullptr during local assertion prop
//
GenTree* Compiler::optAssertionProp(ASSERT_VALARG_TP assertions, GenTree* tree, Statement* stmt, BasicBlock* block)
{
    switch (tree->gtOper)
    {
        case GT_LCL_VAR:
            return optAssertionProp_LclVar(assertions, tree->AsLclVarCommon(), stmt);

        case GT_LCL_FLD:
            return optAssertionProp_LclFld(assertions, tree->AsLclVarCommon(), stmt);

        case GT_STORE_LCL_VAR:
        case GT_STORE_LCL_FLD:
            return optAssertionProp_LocalStore(assertions, tree->AsLclVarCommon(), stmt);

        case GT_STORE_BLK:
            return optAssertionProp_BlockStore(assertions, tree->AsBlk(), stmt);

        case GT_RETURN:
        case GT_SWIFT_ERROR_RET:
            return optAssertionProp_Return(assertions, tree->AsOp(), stmt);

        case GT_SUB:
        case GT_MUL:
        case GT_ADD:
            return optAssertionProp_AddMulSub(assertions, tree->AsOp(), stmt);

        case GT_MOD:
        case GT_DIV:
        case GT_UMOD:
        case GT_UDIV:
            return optAssertionProp_ModDiv(assertions, tree->AsOp(), stmt, block);

        case GT_ARR_LENGTH:
            // Unfortunately, doing this in LocalAP produces an asymmetry in exception sets between
            // uses/defs that CSE does not manage to make good use of. As a result, some bounds checks are no longer
            // removed.
            // TODO-CSE: Allow CSE'ing uses with defs if the defs promise a superset of exceptions
            if (!optLocalAssertionProp)
            {
                return optAssertionProp_Ind(assertions, tree, stmt);
            }
            return nullptr;

        case GT_BLK:
        case GT_IND:
        case GT_STOREIND:
        case GT_NULLCHECK:
            return optAssertionProp_Ind(assertions, tree, stmt);

        case GT_BOUNDS_CHECK:
            return optAssertionProp_BndsChk(assertions, tree, stmt);

        case GT_COMMA:
            return optAssertionProp_Comma(assertions, tree, stmt);

        case GT_CAST:
            return optAssertionProp_Cast(assertions, tree->AsCast(), stmt, block);

        case GT_CALL:
            return optAssertionProp_Call(assertions, tree->AsCall(), stmt);

        case GT_EQ:
        case GT_NE:
        case GT_LT:
        case GT_LE:
        case GT_GT:
        case GT_GE:
            return optAssertionProp_RelOp(assertions, tree, stmt, block);

        case GT_JTRUE:
            if (block != nullptr)
            {
                return optVNConstantPropOnJTrue(block, tree);
            }
            return nullptr;

        default:
            return nullptr;
    }
}

//------------------------------------------------------------------------
// optCreateJumpTableImpliedAssertions: Create assertions for the switch statement
//     for each of its jump targets.
//
// Arguments:
//     switchBb - The switch statement block.
//
// Returns:
//     true if any modifications were made, false otherwise.
//
bool Compiler::optCreateJumpTableImpliedAssertions(BasicBlock* switchBb)
{
    assert(!optLocalAssertionProp);
    assert(switchBb->KindIs(BBJ_SWITCH));
    assert(switchBb->lastStmt() != nullptr);
    bool modified = false;

    GenTree* switchTree = switchBb->lastStmt()->GetRootNode()->gtEffectiveVal();
    assert(switchTree->OperIs(GT_SWITCH));

    // Case count is uint32_t, but it's unlikely to be more than INT32_MAX.
    noway_assert(switchBb->GetSwitchTargets()->GetCaseCount() <= INT32_MAX);

    ValueNum opVN = optConservativeNormalVN(switchTree->gtGetOp1());
    if (opVN == ValueNumStore::NoVN)
    {
        return modified;
    }

    if (vnStore->TypeOfVN(opVN) != TYP_INT)
    {
        // Should probably be an assert instead - GT_SWITCH is expected to be TYP_INT.
        return modified;
    }

    // Typically, the switch value is ADD(X, -cns), so we actually want to create the assertions for X
    int offset = 0;
    vnStore->PeelOffsetsI32(&opVN, &offset);

    int        jumpCount  = static_cast<int>(switchBb->GetSwitchTargets()->GetCaseCount());
    FlowEdge** jumpTable  = switchBb->GetSwitchTargets()->GetCases();
    bool       hasDefault = switchBb->GetSwitchTargets()->HasDefaultCase();

    for (int jmpTargetIdx = 0; jmpTargetIdx < jumpCount; jmpTargetIdx++)
    {
        // The value for each target is jmpTargetIdx - offset.
        if (CheckedOps::SubOverflows(jmpTargetIdx, offset, false))
        {
            continue;
        }
        int value = jmpTargetIdx - offset;

        // We can only make "X == caseValue" assertions for blocks with a single edge from the switch.
        FlowEdge* const   edge   = jumpTable[jmpTargetIdx];
        BasicBlock* const target = edge->getDestinationBlock();
        if (target->GetUniquePred(this) != switchBb)
        {
            // Target block is potentially reachable from multiple blocks (outside the switch).
            continue;
        }

        if (edge->getDupCount() > 1)
        {
            // We have just one predecessor (BBJ_SWITCH), but there may be multiple edges (cases) per target.
            continue;
        }

        AssertionInfo newAssertIdx = NO_ASSERTION_INDEX;

        // Is this target a default case?
        if (hasDefault && (jmpTargetIdx == jumpCount - 1))
        {
            // For default case we can create "X >= maxValue" assertion. Example:
            //
            //   void Test(ReadOnlySpan<byte> name)
            //   {
            //       switch (name.Length)
            //       {
            //           case 0: ...
            //           case 1: ...
            //           ...
            //           case 7: ...
            //           default: %name.Length is >= 8 here%
            //       }
            //
            // NOTE: if offset != 0, we only know that "X + offset >= maxJumpIdx", which is not very useful.
            if ((offset == 0) && (value > 0) && !vnStore->IsVNConstant(opVN))
            {
                if (vnStore->IsVNNeverNegative(opVN))
                {
                    // Create "X >= value" assertion (both operands are never negative)
                    AssertionDsc dsc =
                        AssertionDsc::CreateConstantBound(this, VNF_GE, opVN, vnStore->VNForIntCon(value));
                    newAssertIdx = optAddAssertion(dsc);
                }
                else
                {
                    // Create "X u>= value" assertion
                    AssertionDsc dsc =
                        AssertionDsc::CreateConstantBound(this, VNF_GE_UN, opVN, vnStore->VNForIntCon(value));
                    newAssertIdx = optAddAssertion(dsc);
                }
            }
            else
            {
                continue;
            }
        }
        else
        {
            // Create "VN == value" assertion.
            // TODO-Cleanup: Should use O1K_VN instead of O1K_LCLVAR
            ValueNum valueVN = vnStore->VNForIntCon(value);
            newAssertIdx     = optAddAssertion(
                AssertionDsc::CreateConstLclVarAssertion(this, BAD_VAR_NUM, opVN, value, valueVN, true));
        }

        if (newAssertIdx.HasAssertion())
        {
            // TODO-Cleanup: We shouldn't attach assertions to nodes in Global Assertion Prop.
            // It limits the ability to create multiple assertions for the same node.
            GenTree* tree = gtNewNothingNode();
            fgInsertStmtAtBeg(target, fgNewStmtFromTree(tree));

            modified = true;
            tree->SetAssertionInfo(newAssertIdx);
        }
    }

    return modified;
}

//------------------------------------------------------------------------
// optGetEdgeAssertions: Given a block and its predecessor, get the assertions
//                       the predecessor creates for the block.
//
// Arguments:
//      block     - The block to get the assertions for.
//      blockPred - The predecessor of the block (creating the assertions).
//
// Return Value:
//      The assertions we have about the value number.
//
ASSERT_VALRET_TP Compiler::optGetEdgeAssertions(const BasicBlock* block, const BasicBlock* blockPred) const
{
    assert(block != nullptr);
    if (blockPred->KindIs(BBJ_COND))
    {
        if (blockPred->TrueTargetIs(block))
        {
            if (bbJtrueAssertionOut != nullptr)
            {
                return bbJtrueAssertionOut[blockPred->bbNum];
            }
            return BitVecOps::MakeEmpty(apTraits);
        }

        // If block is not the false target either, the edge doesn't exist
        // (e.g. a stale PHI arg pred after edge redirection by RBO).
        // Return empty to avoid using assertions from an unrelated edge.
        if (!blockPred->FalseTargetIs(block))
        {
            return BitVecOps::MakeEmpty(apTraits);
        }
        return blockPred->bbAssertionOut;
    }

    for (BasicBlock* const pred : block->PredBlocks())
    {
        if (pred == blockPred)
        {
            return blockPred->bbAssertionOut;
        }
    }
    return BitVecOps::MakeEmpty(apTraits);
}

#include "dataflow.h"

/*****************************************************************************
 *
 * Dataflow visitor like callback so that all dataflow is in a single place
 *
 */
class AssertionPropFlowCallback
{
private:
    ASSERT_TP preMergeOut;
    ASSERT_TP preMergeJumpDestOut;

    ASSERT_TP* mJumpDestOut;
    ASSERT_TP* mJumpDestGen;

    BitVecTraits* apTraits;

public:
    AssertionPropFlowCallback(Compiler* pCompiler, ASSERT_TP* jumpDestOut, ASSERT_TP* jumpDestGen)
        : preMergeOut(BitVecOps::UninitVal())
        , preMergeJumpDestOut(BitVecOps::UninitVal())
        , mJumpDestOut(jumpDestOut)
        , mJumpDestGen(jumpDestGen)
        , apTraits(pCompiler->apTraits)
    {
    }

    // At the start of the merge function of the dataflow equations, initialize premerge state (to detect change.)
    void StartMerge(BasicBlock* block)
    {
        if (VerboseDataflow())
        {
            JITDUMP("StartMerge: " FMT_BB " ", block->bbNum);
            Compiler::optDumpAssertionIndices("in -> ", block->bbAssertionIn, "\n");
        }

        BitVecOps::Assign(apTraits, preMergeOut, block->bbAssertionOut);
        BitVecOps::Assign(apTraits, preMergeJumpDestOut, mJumpDestOut[block->bbNum]);
    }

    // During merge, perform the actual merging of the predecessor's (since this is a forward analysis) dataflow flags.
    void Merge(BasicBlock* block, BasicBlock* predBlock, unsigned dupCount)
    {
        ASSERT_TP pAssertionOut;

        if (predBlock->KindIs(BBJ_COND) && predBlock->TrueTargetIs(block))
        {
            pAssertionOut = mJumpDestOut[predBlock->bbNum];

            if (dupCount > 1)
            {
                // Scenario where next block and conditional block, both point to the same block.
                // In such case, intersect the assertions present on both the out edges of predBlock.
                assert(predBlock->FalseTargetIs(block));
                BitVecOps::IntersectionD(apTraits, pAssertionOut, predBlock->bbAssertionOut);

                if (VerboseDataflow())
                {
                    JITDUMP("Merge     : Duplicate flow, " FMT_BB " ", block->bbNum);
                    Compiler::optDumpAssertionIndices("in -> ", block->bbAssertionIn, "; ");
                    JITDUMP("pred " FMT_BB " ", predBlock->bbNum);
                    Compiler::optDumpAssertionIndices("out1 -> ", mJumpDestOut[predBlock->bbNum], "; ");
                    Compiler::optDumpAssertionIndices("out2 -> ", predBlock->bbAssertionOut, "\n");
                }
            }
        }
        else
        {
            pAssertionOut = predBlock->bbAssertionOut;
        }

        if (VerboseDataflow())
        {
            JITDUMP("Merge     : " FMT_BB " ", block->bbNum);
            Compiler::optDumpAssertionIndices("in -> ", block->bbAssertionIn, "; ");
            JITDUMP("pred " FMT_BB " ", predBlock->bbNum);
            Compiler::optDumpAssertionIndices("out -> ", pAssertionOut, "\n");
        }

        BitVecOps::IntersectionD(apTraits, block->bbAssertionIn, pAssertionOut);
    }

    //------------------------------------------------------------------------
    // MergeHandler: Merge assertions into the first exception handler/filter block.
    //
    // Arguments:
    //   block         - the block that is the start of a handler or filter;
    //   firstTryBlock - the first block of the try for "block" handler;
    //   lastTryBlock  - the last block of the try for "block" handler;.
    //
    // Notes:
    //   We can jump to the handler from any instruction in the try region. It
    //   means we can propagate only assertions that are valid for the whole
    //   try region.
    //
    //   It suffices to intersect with only the head 'try' block's assertions,
    //   since that block dominates all other blocks in the try, and since
    //   assertions are VN-based and can never become false.
    //
    void MergeHandler(BasicBlock* block, BasicBlock* firstTryBlock, BasicBlock* lastTryBlock)
    {
        if (VerboseDataflow())
        {
            JITDUMP("Merge     : " FMT_BB " ", block->bbNum);
            Compiler::optDumpAssertionIndices("in -> ", block->bbAssertionIn, "; ");
            JITDUMP("firstTryBlock " FMT_BB " ", firstTryBlock->bbNum);
            Compiler::optDumpAssertionIndices("in -> ", firstTryBlock->bbAssertionIn, "; ");
        }
        BitVecOps::IntersectionD(apTraits, block->bbAssertionIn, firstTryBlock->bbAssertionIn);
    }

    // At the end of the merge store results of the dataflow equations, in a postmerge state.
    bool EndMerge(BasicBlock* block)
    {
        if (VerboseDataflow())
        {
            JITDUMP("EndMerge  : " FMT_BB " ", block->bbNum);
            Compiler::optDumpAssertionIndices("in -> ", block->bbAssertionIn, "\n\n");
        }

        BitVecOps::DataFlowD(apTraits, block->bbAssertionOut, block->bbAssertionGen, block->bbAssertionIn);
        BitVecOps::DataFlowD(apTraits, mJumpDestOut[block->bbNum], mJumpDestGen[block->bbNum], block->bbAssertionIn);

        bool changed = (!BitVecOps::Equal(apTraits, preMergeOut, block->bbAssertionOut) ||
                        !BitVecOps::Equal(apTraits, preMergeJumpDestOut, mJumpDestOut[block->bbNum]));

        if (VerboseDataflow())
        {
            if (changed)
            {
                JITDUMP("Changed   : " FMT_BB " ", block->bbNum);
                Compiler::optDumpAssertionIndices("before out -> ", preMergeOut, "; ");
                Compiler::optDumpAssertionIndices("after out -> ", block->bbAssertionOut, ";\n        ");
                Compiler::optDumpAssertionIndices("jumpDest before out -> ", preMergeJumpDestOut, "; ");
                Compiler::optDumpAssertionIndices("jumpDest after out -> ", mJumpDestOut[block->bbNum], ";\n\n");
            }
            else
            {
                JITDUMP("Unchanged : " FMT_BB " ", block->bbNum);
                Compiler::optDumpAssertionIndices("out -> ", block->bbAssertionOut, "; ");
                Compiler::optDumpAssertionIndices("jumpDest out -> ", mJumpDestOut[block->bbNum], "\n\n");
            }
        }

        return changed;
    }

    // Can be enabled to get detailed debug output about dataflow for assertions.
    bool VerboseDataflow()
    {
#if 0
        return VERBOSE;
#endif
        return false;
    }
};

/*****************************************************************************
 *
 *   Compute the assertions generated by each block.
 */
ASSERT_TP* Compiler::optComputeAssertionGen()
{
    ASSERT_TP* jumpDestGen = fgAllocateTypeForEachBlk<ASSERT_TP>();

    for (BasicBlock* const block : Blocks())
    {
        ASSERT_TP valueGen = BitVecOps::MakeEmpty(apTraits);
        GenTree*  jtrue    = nullptr;

        // Walk the statement trees in this basic block.
        for (Statement* const stmt : block->Statements())
        {
            for (GenTree* const tree : stmt->TreeList())
            {
                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->GetNextStmt() == nullptr));
                    jtrue = tree;
                    break;
                }

                if (tree->GeneratesAssertion())
                {
                    AssertionInfo info = tree->GetAssertionInfo();
                    BitVecOps::AddElemD(apTraits, valueGen, info.GetAssertionIndex() - 1);
                }
            }
        }

        if (jtrue != nullptr)
        {
            // Copy whatever we have accumulated into jumpDest edge's valueGen.
            ASSERT_TP jumpDestValueGen = BitVecOps::MakeCopy(apTraits, valueGen);

            if (jtrue->GeneratesAssertion())
            {
                AssertionInfo  info = jtrue->GetAssertionInfo();
                AssertionIndex valueAssertionIndex;
                AssertionIndex jumpDestAssertionIndex;

                if (info.AssertionHoldsOnFalseEdge())
                {
                    valueAssertionIndex    = info.GetAssertionIndex();
                    jumpDestAssertionIndex = optFindComplementary(info.GetAssertionIndex());
                }
                else // is jump edge assertion
                {
                    jumpDestAssertionIndex = info.GetAssertionIndex();
                    valueAssertionIndex    = optFindComplementary(jumpDestAssertionIndex);
                }

                if (valueAssertionIndex != NO_ASSERTION_INDEX)
                {
                    // Update valueGen if we have an assertion for the bbNext edge
                    BitVecOps::AddElemD(apTraits, valueGen, valueAssertionIndex - 1);
                }

                if (jumpDestAssertionIndex != NO_ASSERTION_INDEX)
                {
                    // Update jumpDestValueGen if we have an assertion for the bbTarget edge
                    BitVecOps::AddElemD(apTraits, jumpDestValueGen, jumpDestAssertionIndex - 1);
                }
            }

            jumpDestGen[block->bbNum] = jumpDestValueGen;
        }
        else
        {
            jumpDestGen[block->bbNum] = BitVecOps::MakeEmpty(apTraits);
        }

        block->bbAssertionGen = valueGen;

#ifdef DEBUG
        if (verbose)
        {
            if (block == fgFirstBB)
            {
                printf("\n");
            }

            printf(FMT_BB " valueGen = ", block->bbNum);
            optPrintAssertionIndices(block->bbAssertionGen);
            if (block->KindIs(BBJ_COND))
            {
                printf(" => " FMT_BB " valueGen = ", block->GetTrueTarget()->bbNum);
                optPrintAssertionIndices(jumpDestGen[block->bbNum]);
            }
            printf("\n");

            if (block == fgLastBB)
            {
                printf("\n");
            }
        }
#endif
    }

    return jumpDestGen;
}

/*****************************************************************************
 *
 *   Initialize the assertion data flow flags that will be propagated.
 */

ASSERT_TP* Compiler::optInitAssertionDataflowFlags()
{
    ASSERT_TP* jumpDestOut = fgAllocateTypeForEachBlk<ASSERT_TP>();

    // The local assertion gen phase may have created unreachable blocks.
    // They will never be visited in the dataflow propagation phase, so they need to
    // be initialized correctly. This means that instead of setting their sets to
    // apFull (i.e. all possible bits set), we need to set the bits only for valid
    // assertions (note that at this point we are not creating any new assertions).
    // Also note that assertion indices start from 1.
    ASSERT_TP apValidFull = BitVecOps::MakeEmpty(apTraits);
    for (int i = 1; i <= optAssertionCount; i++)
    {
        BitVecOps::AddElemD(apTraits, apValidFull, i - 1);
    }

    // Initially estimate the OUT sets to everything except killed expressions
    // Also set the IN sets to 1, so that we can perform the intersection.
    for (BasicBlock* const block : Blocks())
    {
        block->bbAssertionIn      = BitVecOps::MakeCopy(apTraits, apValidFull);
        block->bbAssertionGen     = BitVecOps::MakeEmpty(apTraits);
        block->bbAssertionOut     = BitVecOps::MakeCopy(apTraits, apValidFull);
        jumpDestOut[block->bbNum] = BitVecOps::MakeCopy(apTraits, apValidFull);
    }
    // Compute the data flow values for all tracked expressions
    // IN and OUT never change for the initial basic block B1
    BitVecOps::ClearD(apTraits, fgFirstBB->bbAssertionIn);
    return jumpDestOut;
}

// Callback data for the VN based constant prop visitor.
struct VNAssertionPropVisitorInfo
{
    Compiler*   m_compiler;
    Statement*  stmt;
    BasicBlock* block;
    VNAssertionPropVisitorInfo(Compiler* pThis, BasicBlock* block, Statement* stmt)
        : m_compiler(pThis)
        , stmt(stmt)
        , block(block)
    {
    }
};

//------------------------------------------------------------------------------
// optVNConstantPropOnJTrue
//    Constant propagate on the JTrue node.
//
// Arguments:
//    block - The block that contains the JTrue.
//    test  - The JTrue node whose relop evaluates to 0 or non-zero value.
//
// Return Value:
//    nullptr if no constant propagation is done, else the modified JTrue node
//    containing "0==0" or "0!=0" relop node
//    (where op1 is wrapped with side effects if any).
//
GenTree* Compiler::optVNConstantPropOnJTrue(BasicBlock* block, GenTree* test)
{
    GenTree* relop = test->gtGetOp1();

    // VN based assertion non-null on this relop has been performed.
    if (!relop->OperIsCompare())
    {
        return nullptr;
    }

    //
    // Make sure GTF_RELOP_JMP_USED flag is set so that we can later skip constant
    // prop'ing a JTRUE's relop child node for a second time in the pre-order
    // tree walk.
    //
    assert((relop->gtFlags & GTF_RELOP_JMP_USED) != 0);

    // We want to use the Normal ValueNumber when checking for constants.
    ValueNum vnCns = vnStore->VNConservativeNormalValue(relop->gtVNPair);
    if (!vnStore->IsVNConstant(vnCns))
    {
        return nullptr;
    }

    GenTree* sideEffects = gtWrapWithSideEffects(gtNewNothingNode(), relop);
    if (!sideEffects->IsNothingNode())
    {
        // Insert side effects before the JTRUE stmt.
        Statement* newStmt = fgNewStmtNearEnd(block, sideEffects);
        fgMorphBlockStmt(block, newStmt DEBUGARG(__FUNCTION__));
    }

    // Let's maintain the invariant that JTRUE's operand is always a relop.
    // and if we have side effects, we wrap one of the operands with them, not the relop.
    const bool evalsToTrue = (vnStore->CoercedConstantValue<INT64>(vnCns) != 0);
    test->AsOp()->gtOp1    = gtNewOperNode(evalsToTrue ? GT_EQ : GT_NE, relop->TypeGet(), gtNewFalse(), gtNewFalse());
    return test;
}

//------------------------------------------------------------------------------
// optVNBasedFoldCurStmt: Performs VN-based folding
//    on the current statement's tree nodes using VN.
//
// Assumption:
//    This function is called as part of a post-order tree walk.
//
// Arguments:
//    tree   - The currently visited tree node.
//    stmt   - The statement node in which the "tree" is present.
//    parent - The parent node of the tree.
//    block  - The block that contains the statement that contains the tree.
//
// Return Value:
//    Returns the standard visitor walk result.
//
Compiler::fgWalkResult Compiler::optVNBasedFoldCurStmt(BasicBlock* block,
                                                       Statement*  stmt,
                                                       GenTree*    parent,
                                                       GenTree*    tree)
{
    // Don't try and fold expressions marked with GTF_DONT_CSE
    // TODO-ASG: delete.
    if (!tree->CanCSE())
    {
        return WALK_CONTINUE;
    }

    // Don't propagate floating-point constants into a TYP_STRUCT LclVar
    // This can occur for HFA return values (see hfa_sf3E_r.exe)
    if (tree->TypeIs(TYP_STRUCT))
    {
        return WALK_CONTINUE;
    }

    switch (tree->OperGet())
    {
        // Make sure we have an R-value.
        case GT_ADD:
        case GT_SUB:
        case GT_DIV:
        case GT_MOD:
        case GT_UDIV:
        case GT_UMOD:
        case GT_EQ:
        case GT_NE:
        case GT_LT:
        case GT_LE:
        case GT_GE:
        case GT_GT:
        case GT_OR:
        case GT_XOR:
        case GT_AND:
        case GT_LSH:
        case GT_RSH:
        case GT_RSZ:
        case GT_NEG:
        case GT_CAST:
        case GT_BITCAST:
        case GT_INTRINSIC:
#ifdef FEATURE_HW_INTRINSICS
        case GT_HWINTRINSIC:
#endif // FEATURE_HW_INTRINSICS
        case GT_ARR_LENGTH:
            break;

        case GT_BLK:
        case GT_IND:
        {
            const ValueNum vn = tree->GetVN(VNK_Conservative);
            if (vnStore->VNNormalValue(vn) != vn)
            {
                return WALK_CONTINUE;
            }
        }
        break;

        case GT_JTRUE:
            break;

        case GT_MUL:
            // Don't transform long multiplies.
            if (tree->gtFlags & GTF_MUL_64RSLT)
            {
                return WALK_CONTINUE;
            }
            break;

        case GT_LCL_VAR:
        case GT_LCL_FLD:
            // Let's not conflict with CSE (to save the movw/movt).
            if (lclNumIsCSE(tree->AsLclVarCommon()->GetLclNum()))
            {
                return WALK_CONTINUE;
            }
            break;

        case GT_CALL:
            // The checks aren't for correctness, but to avoid unnecessary work.
            if (!tree->AsCall()->IsPure(this) && !tree->AsCall()->IsSpecialIntrinsic())
            {
                return WALK_CONTINUE;
            }
            break;

        default:
            // Unknown node, continue to walk.
            return WALK_CONTINUE;
    }

    // Perform the VN-based folding:
    GenTree* newTree = optVNBasedFoldExpr(block, parent, tree);

    if (newTree == nullptr)
    {
        // Not propagated, keep going.
        return WALK_CONTINUE;
    }

    optAssertionProp_Update(newTree, tree, stmt);

    JITDUMP("After VN-based fold of [%06u]:\n", tree->gtTreeID);
    DBEXEC(VERBOSE, gtDispStmt(stmt));

    return WALK_CONTINUE;
}

//------------------------------------------------------------------------------
// optVnNonNullPropCurStmt
//    Performs VN based non-null propagation on the tree node.
//
// Assumption:
//    This function is called as part of a pre-order tree walk.
//
// Arguments:
//    block - The block that contains the statement that contains the tree.
//    stmt  - The statement node in which the "tree" is present.
//    tree  - The currently visited tree node.
//
// Return Value:
//    None.
//
// Description:
//    Performs value number based non-null propagation on GT_CALL and
//    indirections. This is different from flow based assertions and helps
//    unify VN based constant prop and non-null prop in a single pre-order walk.
//
void Compiler::optVnNonNullPropCurStmt(BasicBlock* block, Statement* stmt, GenTree* tree)
{
    ASSERT_TP empty   = BitVecOps::UninitVal();
    GenTree*  newTree = nullptr;
    if (tree->OperIs(GT_CALL))
    {
        newTree = optNonNullAssertionProp_Call(empty, tree->AsCall());
    }
    else if (tree->OperIsIndir())
    {
        newTree = optAssertionProp_Ind(empty, tree, stmt);
    }
    if (newTree)
    {
        assert(newTree == tree);
        optAssertionProp_Update(newTree, tree, stmt);
    }
}

//------------------------------------------------------------------------------
// optVNAssertionPropCurStmtVisitor
//    Unified Value Numbering based assertion propagation visitor.
//
// Assumption:
//    This function is called as part of a post-order tree walk.
//
// Return Value:
//    WALK_RESULTs.
//
// Description:
//    An unified value numbering based assertion prop visitor that
//    performs non-null and constant assertion propagation based on
//    value numbers.
//
/* static */
Compiler::fgWalkResult Compiler::optVNAssertionPropCurStmtVisitor(GenTree** ppTree, fgWalkData* data)
{
    VNAssertionPropVisitorInfo* pData = (VNAssertionPropVisitorInfo*)data->pCallbackData;
    Compiler*                   pThis = pData->m_compiler;

    pThis->optVnNonNullPropCurStmt(pData->block, pData->stmt, *ppTree);

    return pThis->optVNBasedFoldCurStmt(pData->block, pData->stmt, data->parent, *ppTree);
}

/*****************************************************************************
 *
 *   Perform VN based i.e., data flow based assertion prop first because
 *   even if we don't gen new control flow assertions, we still propagate
 *   these first.
 *
 *   Returns the skipped next stmt if the current statement or next few
 *   statements got removed, else just returns the incoming stmt.
 */
Statement* Compiler::optVNAssertionPropCurStmt(BasicBlock* block, Statement* stmt)
{
    // TODO-Review: EH successor/predecessor iteration seems broken.
    // See: SELF_HOST_TESTS_ARM\jit\Directed\ExcepFilters\fault\fault.exe
    if (block->CatchTypeIs(BBCT_FAULT))
    {
        return stmt;
    }

    // Preserve the prev link before the propagation and morph.
    Statement* prev = (stmt == block->firstStmt()) ? nullptr : stmt->GetPrevStmt();

    // Perform VN based assertion prop first, in case we don't find
    // anything in assertion gen.
    optAssertionPropagatedCurrentStmt = false;

    VNAssertionPropVisitorInfo data(this, block, stmt);
    fgWalkTreePost(stmt->GetRootNodePointer(), Compiler::optVNAssertionPropCurStmtVisitor, &data);

    if (optAssertionPropagatedCurrentStmt)
    {
        fgMorphBlockStmt(block, stmt DEBUGARG("optVNAssertionPropCurStmt"));
    }

    // Check if propagation removed statements starting from current stmt.
    // If so, advance to the next good statement.
    Statement* nextStmt = (prev == nullptr) ? block->firstStmt() : prev->GetNextStmt();
    return nextStmt;
}

//------------------------------------------------------------------------------
// optAssertionPropMain: assertion propagation phase
//
// Returns:
//    Suitable phase status.
//
PhaseStatus Compiler::optAssertionPropMain()
{
    if (fgSsaPassesCompleted == 0)
    {
        return PhaseStatus::MODIFIED_NOTHING;
    }

    optAssertionInit(false);

    noway_assert(optAssertionCount == 0);
    bool madeChanges = false;

    // Assertion prop can speculatively create trees.
    INDEBUG(const unsigned baseTreeID = compGenTreeID);

    // First discover all assertions and record them in the table.
    ArrayStack<BasicBlock*> switchBlocks(getAllocator(CMK_AssertionProp));
    for (BasicBlock* const block : Blocks())
    {
        compCurBB           = block;
        fgRemoveRestOfBlock = false;

        Statement* stmt = block->firstStmt();
        while (stmt != nullptr)
        {
            // We need to remove the rest of the block.
            if (fgRemoveRestOfBlock)
            {
                fgRemoveStmt(block, stmt);
                stmt        = stmt->GetNextStmt();
                madeChanges = true;
                continue;
            }
            else
            {
                // Perform VN based assertion prop before assertion gen.
                Statement* nextStmt = optVNAssertionPropCurStmt(block, stmt);
                madeChanges |= optAssertionPropagatedCurrentStmt;
                INDEBUG(madeChanges |= (baseTreeID != compGenTreeID));

                // Propagation resulted in removal of the remaining stmts, perform it.
                if (fgRemoveRestOfBlock)
                {
                    stmt = stmt->GetNextStmt();
                    continue;
                }

                // Propagation removed the current stmt or next few stmts, so skip them.
                if (stmt != nextStmt)
                {
                    stmt = nextStmt;
                    continue;
                }
            }

            // Perform assertion gen for control flow based assertions.
            for (GenTree* const tree : stmt->TreeList())
            {
                optAssertionGen(tree);
            }

            // Advance the iterator
            stmt = stmt->GetNextStmt();
        }

        if (block->KindIs(BBJ_SWITCH))
        {
            switchBlocks.Push(block);
        }
    }

    for (BasicBlock* const switchBlock : switchBlocks.BottomUpOrder())
    {
        madeChanges |= optCreateJumpTableImpliedAssertions(switchBlock);
    }

    if (optAssertionCount == 0)
    {
        // Zero out the bbAssertionIn values, as these can be referenced in RangeCheck::MergeAssertion
        // and this is sharedstate with the CSE phase: bbCseIn
        //
        for (BasicBlock* const block : Blocks())
        {
            block->bbAssertionIn = BitVecOps::MakeEmpty(apTraits);
        }
        return madeChanges ? PhaseStatus::MODIFIED_EVERYTHING : PhaseStatus::MODIFIED_NOTHING;
    }

#ifdef DEBUG
    fgDebugCheckLinks();
#endif

    // Allocate the bits for the predicate sensitive dataflow analysis
    bbJtrueAssertionOut    = optInitAssertionDataflowFlags();
    ASSERT_TP* jumpDestGen = optComputeAssertionGen();

    // Modified dataflow algorithm for available expressions.
    DataFlow                  flow(this);
    AssertionPropFlowCallback ap(this, bbJtrueAssertionOut, jumpDestGen);
    if (ap.VerboseDataflow())
    {
        JITDUMP("AssertionPropFlowCallback:\n\n")
    }
    flow.ForwardAnalysis(ap);

#ifdef DEBUG
    if (verbose)
    {
        for (BasicBlock* const block : Blocks())
        {
            printf(FMT_BB ":\n", block->bbNum);
            optDumpAssertionIndices(" in   = ", block->bbAssertionIn, "\n");
            optDumpAssertionIndices(" out  = ", block->bbAssertionOut, "\n");
            if (block->KindIs(BBJ_COND))
            {
                printf(" " FMT_BB " = ", block->GetTrueTarget()->bbNum);
                optDumpAssertionIndices(bbJtrueAssertionOut[block->bbNum], "\n");
            }
        }
        printf("\n");
    }
#endif // DEBUG

    ASSERT_TP assertions = BitVecOps::MakeEmpty(apTraits);

    // Perform assertion propagation (and constant folding)
    for (BasicBlock* const block : Blocks())
    {
        BitVecOps::Assign(apTraits, assertions, block->bbAssertionIn);

        // TODO-Review: EH successor/predecessor iteration seems broken.
        // SELF_HOST_TESTS_ARM\jit\Directed\ExcepFilters\fault\fault.exe
        if (block->CatchTypeIs(BBCT_FAULT))
        {
            continue;
        }

        // Make the current basic block address available globally.
        compCurBB           = block;
        fgRemoveRestOfBlock = false;

        // Walk the statement trees in this basic block
        Statement* stmt = block->FirstNonPhiDef();
        while (stmt != nullptr)
        {
            // Propagation tells us to remove the rest of the block. Remove it.
            if (fgRemoveRestOfBlock)
            {
                fgRemoveStmt(block, stmt);
                stmt        = stmt->GetNextStmt();
                madeChanges = true;
                continue;
            }

            // Preserve the prev link before the propagation and morph, to check if propagation
            // removes the current stmt.
            Statement* prevStmt = (stmt == block->firstStmt()) ? nullptr : stmt->GetPrevStmt();

            optAssertionPropagatedCurrentStmt = false; // set to true if a assertion propagation took place
                                                       // and thus we must morph, set order, re-link
            for (GenTree* tree = stmt->GetTreeList(); tree != nullptr; tree = tree->gtNext)
            {
                optDumpAssertionIndices("Propagating ", assertions, " ");
                JITDUMP("for " FMT_BB ", stmt " FMT_STMT ", tree [%06d]", block->bbNum, stmt->GetID(), dspTreeID(tree));
                JITDUMP(", tree -> ");
                JITDUMPEXEC(optPrintAssertionIndex(tree->GetAssertionInfo().GetAssertionIndex()));
                JITDUMP("\n");

                GenTree* newTree = optAssertionProp(assertions, tree, stmt, block);
                if (newTree)
                {
                    assert(optAssertionPropagatedCurrentStmt == true);
                    tree = newTree;
                }

                // If this tree makes an assertion - make it available.
                if (tree->GeneratesAssertion())
                {
                    AssertionInfo info = tree->GetAssertionInfo();
                    BitVecOps::AddElemD(apTraits, assertions, info.GetAssertionIndex() - 1);
                }
            }

            if (optAssertionPropagatedCurrentStmt)
            {
#ifdef DEBUG
                if (verbose)
                {
                    printf("Re-morphing this stmt:\n");
                    gtDispStmt(stmt);
                    printf("\n");
                }
#endif
                // Record BBJ_COND state before morphing so we can fix up
                // assertion out sets if morph changes the block's edges.
                bool        wasCond = block->KindIs(BBJ_COND);
                BasicBlock* trueBb  = wasCond ? block->GetTrueTarget() : nullptr;
                BasicBlock* falseBb = wasCond ? block->GetFalseTarget() : nullptr;

                // Re-morph the statement.
                fgMorphBlockStmt(block, stmt DEBUGARG("optAssertionPropMain"));
                madeChanges = true;

                // Fix up assertion out sets if morphing changed the block's edges in a way
                // that affects the semantics of the assertions.
                //
                if (wasCond && !optLocalAssertionProp)
                {
                    if (!block->KindIs(BBJ_COND))
                    {
                        // NOTE: if trueBb == falseBb then we don't know how assertions may change
                        // so we take the conservative path in that case.
                        //
                        if ((block->GetUniqueSucc() == trueBb) && (trueBb != falseBb))
                        {
                            // BBJ_COND was folded (e.g. to BBJ_ALWAYS).
                            // Fix up bbAssertionOut to match the retained edge.
                            //
                            BitVecOps::Assign(apTraits, block->bbAssertionOut, bbJtrueAssertionOut[block->bbNum]);
                        }
                        else if ((block->GetUniqueSucc() == falseBb) && (trueBb != falseBb))
                        {
                            // bbAssertionOut already has the false-edge assertions.
                        }
                        else
                        {
                            // Converted to something unexpected (e.g. BBJ_SWITCH) — conservatively
                            // just propagate the IN assertions, which is better than losing all assertions.
                            //
                            BitVecOps::Assign(apTraits, block->bbAssertionOut, block->bbAssertionIn);
                            // We can also quickly walk over the trees and accumulate more assertions if needed.
                            // NOTE: this is not valid for LocalAP as assertions may die in the middle of the block
                        }
                    }
                    else if ((block->GetTrueTarget() != trueBb) || (block->GetFalseTarget() != falseBb))
                    {
                        // Conservatively clear assertions if edges changed in any way that we don't expect.
                        // We still can be smart here and handle e.g. edge flip.
                        //
                        BitVecOps::Assign(apTraits, block->bbAssertionOut, block->bbAssertionIn);
                        BitVecOps::Assign(apTraits, bbJtrueAssertionOut[block->bbNum], block->bbAssertionIn);
                        // NOTE: this is not valid for LocalAP as assertions may die in the middle of the block
                    }
                }
            }

            // Check if propagation removed statements starting from current stmt.
            // If so, advance to the next good statement.
            Statement* nextStmt = (prevStmt == nullptr) ? block->firstStmt() : prevStmt->GetNextStmt();
            stmt                = (stmt == nextStmt) ? stmt->GetNextStmt() : nextStmt;
        }
        optAssertionPropagatedCurrentStmt = false; // clear it back as we are done with stmts.
    }

    return madeChanges ? PhaseStatus::MODIFIED_EVERYTHING : PhaseStatus::MODIFIED_NOTHING;
}