cast_elision.cpp

//------------------------------------------------------------------------
// gtFoldExprCast: see if a cast is foldable
//
// Arguments:
//    cast - cast to examine
//
// Returns:
//    The original cast if no folding happened.
//    An alternative tree if folding happens.
//
// Notes:
//    Checks for casts which can be optimized
GenTree* Compiler::gtFoldExprCast(GenTreeCast* cast)
{
    GenTree* result = nullptr;

    if (opts.OptimizationDisabled())
    {
        // Don't fold if optimizations are disabled
        return cast;
    }

    GenTree* castOp = cast->CastOp();

    var_types fromType = cast->CastFromType();
    var_types toType   = cast->CastToType();
    var_types castType = cast->TypeGet();

    bool isLargerToSmaller = genTypeSize(fromType) > genTypeSize(toType);
    bool isOverflow        = cast->gtOverflow();
    bool isFromFloating    = varTypeIsFloating(fromType);
    bool isFromUnsigned    = cast->IsUnsigned();
    bool isToFloating      = varTypeIsFloating(toType);
    bool isToUnsigned      = varTypeIsUnsigned(toType);
    bool isSignChange      = isFromUnsigned != isToUnsigned;

    if (varTypeIsSmall(toType) && !isOverflow && castOp->TypeIs(TYP_INT) && castOp->OperIs(GT_AND))
    {
        GenTree* op2 = castOp->AsOp()->gtGetOp2();

        if (op2->OperIs(GT_CNS_INT))
        {
            ssize_t ival = op2->AsIntCon()->gtIconVal;
            ssize_t mask, umask;

            switch (toType)
            {
                case TYP_BYTE:
                case TYP_UBYTE:
                {
                    mask  = 0x00FF;
                    umask = 0x007F;
                    break;
                }

                case TYP_USHORT:
                case TYP_SHORT:
                {
                    mask  = 0xFFFF;
                    umask = 0x7FFF;
                    break;
                }

                default:
                {
                    assert(!"unexpected type");
                    return cast;
                }
            }

            if (((ival & umask) == ival) || (((ival & mask) == ival) && isFromUnsigned))
            {
                // Toss the cast, it's a waste of time
                result = castOp;
            }
            else if (ival == mask)
            {
                // Toss the masking, it's a waste of time, since
                // we sign-extend from the small value anyways

                result = castOp->AsOp()->gtGetOp1();
            }

            if (result != nullptr)
            {
                JITDUMP("\nFolding cast operator:\n");
                DISPTREE(cast);
                goto DONE_FOLD;
            }
        }
    }

    if (isOverflow && ((!isSignChange && !isLargerToSmaller) ||
                       (isFromUnsigned && (genTypeSize(fromType) < genTypeSize(toType)))))
    {
        // We are going from a smaller type to a larger or equal type without changing
        // the sign, or from a smaller unsigned type to a larger signed type, so it is
        // impossible for this to overflow.

        // This can occur, for example, on 64-bit builds when using nint to index
        // into an array. C# may emit a `nint->long->nint.ovfl`cast in this scenario
        // which is functionally `long->long->long.ovfl`.

        JITDUMP("\nFolding cast operator:\n");
        DISPTREE(cast);

        cast->gtFlags &= ~(GTF_OVERFLOW | GTF_EXCEPT);

        isOverflow = false;
        result     = cast;
    }

    // TODO: This currently asserts downstream in System.Collections.Concurrent for InitializeFromCollection
    //       as it produces a GT_FIELD where the parent is null during fgMorphStructField
    // 
    // if (!isOverflow && (fromType == castType) && (genTypeSize(castType) == genTypeSize(toType)))
    // {
    //     JITDUMP("\nFolding cast operator:\n");
    //     DISPTREE(cast);
    // 
    //     result = castOp;
    //     goto DONE_FOLD;
    // }

    if (!castOp->OperIs(GT_CAST))
    {
        if (result != nullptr)
        {
            // This exists to catch the case where we simply trimmed the overflow flag
            goto DONE_FOLD;
        }

        // Don't otherwise fold if the cast op isn't itself a cast
        return cast;
    }

    GenTreeCast* nestedCast = castOp->AsCast();

    var_types nestedFromType = nestedCast->CastFromType();
    var_types nestedToType   = nestedCast->CastToType();

    bool isNestedLargerToSmaller = genTypeSize(nestedFromType) > genTypeSize(nestedToType);
    bool isNestedOverflow        = nestedCast->gtOverflow();
    bool isNestedFromFloating    = varTypeIsFloating(nestedFromType);
    bool isNestedFromUnsigned    = nestedCast->IsUnsigned();
    bool isNestedToFloating      = varTypeIsFloating(nestedToType);
    bool isNestedToUnsigned      = varTypeIsUnsigned(nestedToType);
    bool isNestedSignChange      = isNestedFromUnsigned != isNestedToUnsigned;

    if (isNestedFromFloating || isNestedToFloating || isFromFloating || isToFloating)
    {
        if (isNestedOverflow || isOverflow || isNestedLargerToSmaller || !isLargerToSmaller)
        {
            if (result != nullptr)
            {
                // This exists to catch the case where we simply trimmed the overflow flag
                goto DONE_FOLD;
            }
        }
        else if (isNestedFromFloating && isNestedToFloating && isFromFloating && isToFloating)
        {
            JITDUMP("\nFolding cast operator:\n");
            DISPTREE(cast);

            // We are staying a floating-point op the entire time and
            // are doing `float->double->float`so we can elide the cast.
            result = nestedCast->CastOp();

            goto DONE_FOLD;
        }

        // Don't otherwise fold
        return cast;
    }

    if (result == nullptr)
    {
        JITDUMP("\nFolding cast operator:\n");
        DISPTREE(cast);

        result = cast;
    }

    assert(result == cast);

    // We should never hit cases such as the following as one of the overflow flags should have been stripped:
    // * uint->uint.ovf
    // * uint.ovf->uint
    // * uint->long.ovf
    // * uint->ulong.ovf
    // * int->int.ovf
    // * int.ovf->int
    // * int->long.ovf

    // Likewise, we should never encounter cases such as:
    // * uint->uint
    // * uint->int
    // * int->uint
    // * int->int

    if (isNestedLargerToSmaller)
    {
        if (isLargerToSmaller && (isNestedOverflow == isOverflow))
        {
            if (isOverflow && isNestedToUnsigned && !isFromUnsigned && !isToUnsigned)
            {
                // For example: `int->ushort.ovf->sbyte.ovf`
                //
                // Normally goes from [-2147483648, 2147483647] to [0, 65535] to [-32768, 32767] to [-128, 127]
                // Where [65408, 65535] become [-128, -1]
                //
                // Treating it as signed or unsigned would not handle [65408, 65535]

                // For example: `uint->ushort.ovf.un->sbyte.ovf`
                //
                // Normally goes from [0, 4294967295] to [0, 65535] to [-32768, 32767] to [-128, 127]
                // Where [65408, 65535] become [-128, -1]
                //
                // Treating it as signed or unsigned would not handle [65408, 65535]
            }
            else
            {
                // For example: `int->ushort->byte`, `int->ushort->sbyte`, `int->short->byte`, and `int->short->sbyte`
                //              `uint->ushort->byte`, `uint->ushort->sbyte`, `uint->short->byte`, and `uint->short->sbyte`
                // These are all effectively just `value & 0xFFFF & 0xFF`

                // For example: `int->ushort.ovf->byte.ovf`
                //
                // Normally goes from [-2147483648, 2147483647] to [0, 65535] to [-32768, 32767] to [0, 255]
                // Where [32768, 65535] become [-32768, -1] and [0, 255] become [0, 255]
                //
                // Treating it as signed or unsigned preserves the semantics as [0, 255] are the valid inputs

                // For example: `int->ushort.ovf->byte.ovf.un`
                //
                // Normally goes from [-2147483648, 2147483647] to [0, 65535] to [0, 255]
                //
                // Treating it as signed or unsigned preserves the semantics as [0, 255] are the valid inputs

                // For example: `int->ushort.ovf->sbyte.ovf.un`
                //
                // Normally goes from [-2147483648, 2147483647] to [0, 65535] to [0, 127]
                //
                // Treating it as signed would allow [4294967168, 4294967295] to become [-128, -1]
                // Treating it as unsigned preserves the smenatics as [0, 127] are the valid inputs

                // For example: `int->short.ovf->byte.ovf`
                //
                // Normally goes from [-2147483648, 2147483647] to [-32768, 32767] to [0, 255]
                //
                // Treating it as signed or unsigned preserves the semantics as [0, 255] are the valid inputs

                // For example: `int->short.ovf->byte.ovf.un`
                //
                // Normally goes from [-2147483648, 2147483647] to [-32768, 32767] to [0, 65535] to [0, 255]
                //
                // Treating it as signed or unsigned preserves the semantics as [0, 255] are the valid inputs

                // For example: `int->short.ovf->sbyte.ovf`
                //
                // Normally goes from [-2147483648, 2147483647] to [-32768, 32767] to [-128, 127]
                //
                // Treating it as signed preserves the semantics as [-128, 127] are the valid inputs
                // Treating it as unsigned would not handle [-128, -1]

                // For example: `int->short.ovf->sbyte.ovf.un`
                //
                // Normally goes from [-2147483648, 2147483647] to [-32768, 32767] to [0, 65535] to [0, 127]
                //
                // Treating it as signed would not handle [-128, -1]
                // Treating it as unsigned would preserves the semantics as [0, 127] are the valid inputs

                // For example: `uint->ushort.ovf.un->byte.ovf`
                //
                // Normally goes from [0, 4294967295] to [0, 65535] to [-32768, 32767] to [0, 255]
                // Where [32768, 65535] become [-32768, -1] and [0, 255] become [0, 255]
                //
                // Treating it as signed or unsigned preserves the semantics as [0, 255] are the valid inputs

                // For example: `uint->ushort.ovf.un->byte.ovf.un`
                //
                // Normally goes from [0, 4294967295] to [0, 65535] to [0, 255]
                //
                // Treating it as signed or unsigned preserves the semantics as [0, 255] are the valid inputs

                // For example: `uint->ushort.ovf.un->sbyte.ovf.un`
                //
                // Normally goes from [0, 4294967295] to [0, 65535] to [0, 127]
                //
                // Treating it as signed would allow [4294967168, 4294967295] to become [-128, -1]
                // Treating it as unsigned preserves the semantics as [0, 127] are the valid inputs

                // For example: `uint->short.ovf.un->byte.ovf`
                //
                // Normally goes from [0, 4294967295] to [0, 32767] to [0, 255]
                //
                // Treating it as signed or unsigned preserves the semantics as [0, 255] are the valid inputs

                // For example: `uint->short.ovf.un->byte.ovf.un`
                //
                // Normally goes from [0, 4294967295] to [0, 32767] to [0, 127]
                //
                // Treating it as signed would allow [4294967168, 4294967295] to become [-128, -1]
                // Treating it as unsigned preserves the semantics as [0, 127] are the valid inputs

                // For example: `uint->short.ovf.un->sbyte.ovf`
                //
                // Normally goes from [0, 4294967295] to [0, 32767] to [0, 127]
                //
                // Treating it as signed would allow [4294967168, 4294967295] to become [-128, -1]
                // Treating it as unsigned preserves the semantics as [0, 127] are the valid inputs

                // For example: `uint->short.ovf.un->sbyte.ovf.un`
                //
                // Normally goes from [0, 4294967295] to [0, 32767] to [0, 127]
                //
                // Treating it as signed would allow [4294967168, 4294967295] to become [-128, -1]
                // Treating it as unsigned preserves the semantics as [0, 127] are the valid inputs

                result->AsOp()->gtOp1 = nestedCast->CastOp();

                if (isOverflow && isNestedFromUnsigned && !isNestedToUnsigned && !isNestedFromUnsigned && !isNestedToUnsigned)
                {
                    result->gtFlags |= GTF_UNSIGNED;
                }
            }
        }
        else if (isNestedOverflow)
        {
            if (isOverflow)
            {
                // Since unsigned types can't overflow when getting larger the cast must be
                // either a signed type to an unsigned type or the unsigned type must be going
                // to a signed type of the same size.

                if (!isToUnsigned)
                {
                    assert(isFromUnsigned && (genTypeSize(fromType) == genTypeSize(toType)));

                    // For example: `long->int.ovf->int.ovf.un`
                    //
                    // Normally goes from [-9223372036854775808, 9223372036854775807] to [-2147483648, 2147483647]
                    // to [0, 4294967295] to [0, 2147483647]
                    //
                    // Treating it as signed would incorrectly handle [-2147483648, -1]
                    // Treating it as unsigned preserves the semantics as [0, 2147483647] are the valid inputs

                    // For example: `long->uint.ovf->int.ovf.un`
                    //
                    // Normally goes from [-9223372036854775808, 9223372036854775807] to [0, 4294967295]
                    // to [0, 2147483647]
                    //
                    // Treating it as signed would incorrectly handle [-2147483648, -1]
                    // Treating it as unsigned preserves the semantics as [0, 2147483647] are the valid inputs

                    // For example: `ulong->int.ovf.un->int.ovf.un`
                    //
                    // Normally goes from [0, 18446744073709551615] to [0, 2147483647] to [0, 2147483647]
                    // to [0, 2147483647]
                    //
                    // Treating it as signed would incorrectly handle [18446744071562067968, 18446744073709551615]
                    // Treating it as unsigned preserves the semantics as [0, 2147483647] are the valid inputs

                    // For example: `ulong->uint.ovf.un->int.ovf.un`
                    //
                    // Normally goes from [0, 18446744073709551615] to [0, 4294967295] to [0, 2147483647]
                    //
                    // Treating it as signed would incorrectly handle [18446744071562067968, 18446744073709551615]
                    // Treating it as unsigned preserves the semantics as [0, 2147483647] are the valid inputs

                    result->AsOp()->gtOp1 = nestedCast->CastOp();
                }
                else
                {
                    assert(!isFromUnsigned && isSignChange);

                    if (isNestedFromUnsigned)
                    {
                        // For example: `ulong->int.ovf.un->ulong.ovf`
                        //
                        // Normally goes from [0, 18446744073709551615] to [0, 2147483647] to [0, 2147483647]
                        //
                        // We can't elide the cast but we can remove the second overflow

                        // For example: `ulong->uint.ovf.un->ulong.ovf`
                        //
                        // Normally goes from [0, 18446744073709551615] to [0, 4294967295] to [0, 4294967295]
                        //
                        // We can't elide the cast but we can remove the second overflow

                        result->gtFlags &= ~(GTF_OVERFLOW | GTF_EXCEPT);
                    }
                    else
                    {
                        unreached();
                    }
                }
            }
            else
            {
                // If we are doing a single overflow, we can't elide either because we'd mishandle
                // cases like `int->ushort.ovf->byte` since 65537 should overflow. Likewise cases like
                // `int->ushort.ovf->int` should have overflowed for -1
            }
        }
        else if (isOverflow)
        {
            // If we are doing a single overflow, we can't elide either because we'd mishandle
            // cases like `int->ushort->byte.ovf` since 65537 should become 1. Likewise cases like
            // `uint->sbyte->ushort.ovf` needs to treat 257 as 1
        }
        else
        {
            // We can't fold cases such as `int->ushort->ulong` since that would
            // incorrectly handle 65537 whether it was treated as signed or unsigned
        }
    }
    else if (isLargerToSmaller && (isNestedOverflow == isOverflow))
    {
        assert(!isOverflow || isNestedToUnsigned);

        // For example: `int->uint->byte`, `int->uint->sbyte`, `int->long->byte`, and `int->long->sbyte`
        //              `uint->ulong->byte`, `uint->ulong->sbyte`, `uint->long->byte`, and `uint->long->sbyte`
        // These are all effectively just `value & 0xFFFF & 0xFF`

        // For example: `int->uint.ovf->byte.ovf`
        //
        // Normally goes from [-2147483648, 2147483647] to [0, 2147483647] to [0, 2147483647] to [0, 255]
        //
        // Treating it as signed or unsigned preserves the semantics as [0, 255] are the valid inputs

        // For example: `int->uint.ovf->byte.ovf.un`
        //
        // Normally goes from [-2147483648, 2147483647] to [0, 2147483647] to [0, 255]
        //
        // Treating it as signed or unsigned preserves the semantics as [0, 255] are the valid inputs

        // For example: `int->uint.ovf->sbyte.ovf`
        //
        // Normally goes from [-2147483648, 2147483647] to [0, 2147483647] to [0, 2147483647] to [0, 127]
        //
        // Treating it as signed would allow incorrectly handle `[-127, -1]`
        // Treating it as unsigned preserves the semantics as [0, 127] are the valid inputs

        // For example: `int->uint.ovf->sbyte.ovf.un`
        //
        // Normally goes from [-2147483648, 2147483647] to [0, 2147483647] to [0, 127]
        //
        // Treating it as signed would allow [4294967168, 4294967295] to become [-128, -1]
        // Treating it as unsigned preserves the semantics as [0, 127] are the valid inputs

        result->AsOp()->gtOp1 = nestedCast->CastOp();

        if (isOverflow && !isFromUnsigned && !isToUnsigned)
        {
            result->gtFlags |= GTF_UNSIGNED;
        }
    }
    else if (isNestedOverflow)
    {
        if (isOverflow)
        {
            // Since unsigned types can't overflow when getting larger the cast must be
            // either a signed type to an unsigned type or the unsigned type must be going
            // to a signed type of the same size.

            if (!isToUnsigned)
            {
                assert(isFromUnsigned && (genTypeSize(fromType) == genTypeSize(toType)));

                // For example: `int->uint.ovf->int.ovf.un`
                //
                // Normally goes from [-2147483648, 2147483647] to [0, 2147483647] to to [0, 2147483647]
                //
                // Treating it as signed would incorrectly handle [-2147483648, -1]
                // Treating it as unsigned preserves the semantics as [0, 2147483647] are the valid inputs

                result->AsOp()->gtOp1 = nestedCast->CastOp();
            }
            else
            {
                assert(!isFromUnsigned && isSignChange);

                if (isNestedFromUnsigned)
                {
                    // For example: `uint->int.ovf.un->uint.ovf`
                    //
                    // Normally goes from [0, 4294967295] to [0, 2147483647] to [0, 2147483647]
                    //
                    // Treating it as signed preserves the semantics as [0, 2147483647] are the valid inputs
                    // Treating it as unsigned would incorrectly handle [2147483648, 4294967295]

                    result->AsOp()->gtOp1 = nestedCast->CastOp();
                }
                else
                {
                    unreached();
                }
            }
        }
        else
        {
            // We can't fold cases such as `uint->int.ovf.un->long` since that would
            // incorrectly handle 2147483648 whether it was treated as signed or unsigned
        }
    }
    else
    {
        // We can't fold cases such as `short->ushort->ulong` since that would incorrectly handle -1
    }

DONE_FOLD:

    if (fgGlobalMorph)
    {
        fgMorphTreeDone(result, cast);
    }
    else if (result != cast)
    {
        result->gtPrev = cast->gtPrev;
        result->gtNext = cast->gtNext;

        DEBUG_DESTROY_NODE(cast);
    }

    JITDUMP("Transformed into:\n");
    DISPTREE(result);

    return result;
}