Re: [patch tree-optimization]: Improve handling of conditional-branches on targets with high branch costs

[Kai Tietz <ktietz70 at googlemail dot com>]

2011/10/10 Richard Guenther <richard.guenther@gmail.com>:
> On Mon, Oct 10, 2011 at 12:35 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
>> 2011/10/7 Kai Tietz <ktietz70@googlemail.com>:
>>> Hello,
>>>
>>> this is the updated version with the suggestion
>>>
>>> 2011/10/7 Richard Guenther <richard.guenther@gmail.com>:
>>>> On Thu, Oct 6, 2011 at 4:25 PM, Kai Tietz <ktietz@redhat.com> wrote:
>>>>> + ? ? ?&& ((TREE_CODE_CLASS (TREE_CODE (arg1)) != tcc_comparison
>>>>> + ? ? ? ? ? && TREE_CODE (arg1) != TRUTH_NOT_EXPR
>>>>> + ? ? ? ? ? && simple_operand_p (arg1))
>>>>
>>>> As I said previously simple_operand_p already rejects covers
>>>> comparisons and TRUTH_NOT_EXPR. ?Also arg1 had better
>>>> TREE_SIDE_EFFECTS set if the comparison might trap, as
>>>> it might just be hidden in something more complicated - so
>>>> the simple check isn't enough anyway (and if simple_operand_p
>>>> would cover it, the check would be better placed there).
>>>
>>> I reworked simple_operand_p so that it does this special-casing and additionally
>>> also checks for trapping.
>>>
>>>>> + ? ? ?if (TREE_CODE (arg0) == code
>>>>> + ? ? ? ? ?&& !TREE_SIDE_EFFECTS (TREE_OPERAND (arg0, 1))
>>>>> + ? ? ? ? ?&& simple_operand_p (TREE_OPERAND (arg0, 1)))
>>>>> + ? ? ? {
>>>>> + ? ? ? ? tem = build2_loc (loc,
>>>>> + ? ? ? ? ? ? ? ? ? ? ? ? ? (code == TRUTH_ANDIF_EXPR ? TRUTH_AND_EXPR
>>>>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? : TRUTH_OR_EXPR),
>>>>> + ? ? ? ? ? ? ? ? ? ? ? ? ? type, TREE_OPERAND (arg0, 1), arg1);
>>>>> + ? ? ? ? return build2_loc (loc, code, type, TREE_OPERAND (arg0, 0),
>>>>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ?tem);
>>>>
>>>> All trees should be folded, don't use plain build without a good reason.
>>>
>>> Ok, done
>>>
>>>>> + ? ? ? }
>>>>> + ? ? ?/* Convert X TRUTH-ANDORIF Y to X TRUTH-ANDOR Y, if X and Y
>>>>> + ? ? ? ?are simple operands and have no side-effects. ?*/
>>>>> + ? ? ?if (simple_operand_p (arg0)
>>>>> + ? ? ? ? ?&& !TREE_SIDE_EFFECTS (arg0))
>>>>
>>>> Again, the checks you do for arg0 do not match those for arg1. ?OTOH
>>>> it doesn't matter whether arg0 is simple or not or has side-effects or
>>>> not for this transformation, so why check it at all?
>>>
>>> It is required. ?For left-hand operand, if it isn't a logical
>>> and/or/xor, we need to check for side-effects (and for trapping). ?I
>>> see that calling of simple_operand_p is wrong here, as it rejects too
>>> much. ?Nevertheless the check for side-effects is necessary for having
>>> valid sequence-points. ?Without that checking a simple test
>>
>> So said, it is even required to use for right-hand and left-hand side
>> of arguments, if one of them have side-effects or isn't simple. ?Means
>> the check in my patch should use for
>>
>>> + ? ? else if (TREE_CODE (arg0) != TRUTH_AND_EXPR
>>> + ? ? ? ? ? ? && TREE_CODE (arg0) != TRUTH_OR_EXPR
>>> + ? ? ? ? ? ? && TREE_CODE (arg0) != TRUTH_ANDIF_EXPR
>>> + ? ? ? ? ? ? && TREE_CODE (arg0) != TRUTH_ORIF_EXPR
>>> + ? ? ? ? ? ? && TREE_CODE (arg0) != TRUTH_XOR_EXPR
>>> + ? ? ? ? ? ? /* Needed for sequence points and trappings, or side-effects. ?*/
>>> + ? ? ? ? ? ? && !TREE_SIDE_EFFECTS (arg0)
>>> + ? ? ? ? ? ? && !tree_could_trap_p (arg0))
>>> + ? ? ? return fold_build2_loc (loc, ncode, type, arg0, arg1);
>>
>> instead if (!TREE_SIDE_EFFECTS (arg0) && simple_operand_p (arg0)) ....
>> instead.
>>
>> The cause for this are the consitancies of sequences in tree. ?I
>> noticed that by tests in gcc.dg/tree-ssa about builitin_expect.
>>
>> for example we have
>>
>> extern int foo (void); /* foo modifies gbl1 */
>> int gbl1 = 0;
>>
>> int foo (int ns1)
>> {
>> ?if (ns1 && foo () && gbl1)
>> ? ?return 1;
>> ?return 0;
>> }
>>
>> so chain of trees has to look like this:
>> (ANDIF (ns1 (ANDIF foo () gbl1))
>>
>> but if we don't check here for side-effects for left-hand chaining
>> operand, then we end up with
>> (AND ns1 (ANDIF foo () gbl1))
>
> No we don't, as the right-hand (ANDIF foo () glbl1) has side-effects.
>
>> As AND and has associative property, tree says that right-hand and
>> left-hand are exchangable, which is obviously wrong.
>
> The poitn is that if the right-hand does not have side-effects it doesn't
> matter if we execute it before the left-hand (independent on whether
> that has side-effects or not).
>
> Richard.

thats just true as long as we don't make use of associative law for
AND expressions.
Otherwise we would fail for much simpler cases like
entern int doo ();
int foo ()
{
  int c, r = 0;
  if ((c = foo ()) != 0 && c < 20)
    r = 1;
  return 0;
}

as for this left-hand operand has side-effects, but as it is the first
one, we would chain it as AND.  So we get wrong sequence.

Kai