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

[Kai Tietz]

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))

As AND and has associative property, tree says that right-hand and
left-hand are exchangable, which is obviously wrong.

Cheers,
Kai