Incorrect integer calculation

[TorstenStueber]

Describe the bug Simple integer calculation inside a pure function returns the wrong result. This happens for the compiler target Polkadot.

To Reproduce Compile the following contract for the Polkadot compiler target:

contract Test {
    function test()
        external view
        returns (uint256 result)
    {
        return f(10_000_000_000);
    }

    function f(uint256 x)
        internal pure
        returns (uint256)
    {
        return x * x / 10_000_000_000;
    }
}

Deploy this contract and send the test message. The result will be 776_627_963 although it should be 10_000_000_000.

Compiling this contract for Ethereum and running it on an EVM (e.g., on Remix) yields the correct result:

    uint256: result 10000000000

It seems that the smallest constant where this effect starts to appear is 0x200000001 (replacing both occurrences of 10_000_000_000 by this number).

Hyperledger Solang version Latest main branch (commit 01fbc6b)

[xermicus]

I can confirm the bug. Seems like the strength reduction optimization pass is at fault here; compiling with --no-strength-reduce fixes the reproducer contract.

[xermicus]

Strenght reduce thinks that for the divide expression (x * x) / 10_000_000_000, the maximum value of the left hand (x * x) is one (1). And based of that, x gets optimized into a narrower int type. Which is clearly wrong. I don't understand why strength reduce doesn't just assume the expression types max value, if it's not a constant expression anyways. CC @LucasSte could you please have a look at this?

[seanyoung]

I wrote strength reduce. You are right, there is a problem with the calculation of the possible values of x * x, or of any unsigned multiply. We want an unknown bit mask for n..m where m is the maximum values of a b. The n can be set to the sum of the leading 0 bits of a and b, since 0x10000 unknown always has 4 leading 0 bits.