Re: Defect in linearization of short circuit &&

[Christopher Li <sparse@chrisli.org>]

On Tue, Feb 16, 2010 at 1:28 AM, Bernd Petrovitsch
<bernd@petrovitsch.priv.at> wrote:
>> $ ./test-linearize parser_check.c
>> parser_check:
>> .L0x7f4e12de3130:
>>       <entry-point>
>>       br          %arg1, .L0x7f4e12de32e0, .L0x7f4e12de3250
> I assume this means "if %arg1 == NULL goto .L0x7f4e12de32e0 else goto .L0x7f4e12de3250"

That is right.

> I assume this is the "i > 0" check.

No, this is the not the i > 0 check yet. This is setting the expression value
of the false branch to 0.

>>       phisrc.1    %phi2 <- $0
>>       br          .L0x7f4e12de3298
>>
>> .L0x7f4e12de3298:
>>       phi.1       %r8 <- %phi1, %phi2
>>       setgt.32    %r10 <- %arg2, $0

This is the "i > 0" check. (%arg2 is "i")

>>       and-bool.1  %r11 <- %r8, %r10
>>       br          %r11, .L0x7f4e12de3178, .L0x7f4e12de31c0
>>
>> .L0x7f4e12de3178:
>>       call        execute_a, %arg1, %arg2
>>       br          .L0x7f4e12de3328
>>
>> In the fast test, the false branch is L0x7f4e12de3250.
>> Which is doing the (i > 0) part and it is safe to do so.

> Are saying that he "i >0 " test done while "st == NULL"?
> This is actually wrong as it shouldn't be done (independent of the used
> variables and especially if the expression has side effects).

That is right. "i > 0" is still being tested.

Consider this example. The same source code and be compile into two
different piece of machine code. They produce the exact same result.
The one with this optimization runs faster than the other one. Do you still
thing that is wrong? How about x86 CPU internally re-ordering the instruction,
is that wrong too?

So I think as long as this behavior is *internal* and *correct*. It is fine.
Of course it'd better be faster as well. Otherwise, what is the point.

The goal of the this optimization is trading the branch instruction
with cheaper arithmetic instruction.

For modern CPU, the branch instruction is likely more expensive
than normal arithmetic instruction. In X86, branch instruction *might*
flush the instruction pipe line while arithmetic operation can usually done
in one cycle.

That is why this optimization is using a cost model. If the left hand
side cost is lower than the branch instruction cost, and it is *safe* to
do so. It turn the branch instruction into arithmetic instruction.

However, in this case, the optimization did not consider this expression
is used in the if statement, and if statement has build-in branch instruction
associate with it. So this optimization might not worthy while here.

But for this expression:

a = st && st->foo && st->bar && i > 0;

This optimization might be worth while.

If the optimization produce incorrect result. That is fatal and that
is a serious bug.
I just want to confirm that is no the case here.

Chris
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html