Re: RFC: Handle conditional expression in sccvn/fre/pre

[Richard Guenther <richard dot guenther at gmail dot com>]

On Wed, Feb 29, 2012 at 3:50 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Mon, Jan 2, 2012 at 10:54 PM, Richard Guenther
> <richard.guenther@gmail.com> wrote:
>> On Mon, Jan 2, 2012 at 3:09 PM, Amker.Cheng <amker.cheng@gmail.com> wrote:
>>> On Mon, Jan 2, 2012 at 9:37 PM, Richard Guenther
>>> <richard.guenther@gmail.com> wrote:
>>>
>>>> Well, with
>>>>
>>>> Index: gcc/tree-ssa-pre.c
>>>> ===================================================================
>>>> --- gcc/tree-ssa-pre.c ?(revision 182784)
>>>> +++ gcc/tree-ssa-pre.c ?(working copy)
>>>> @@ -4335,16 +4335,23 @@ eliminate (void)
>>>> ? ? ? ? ? ? available value-numbers. ?*/
>>>> ? ? ? ? ?else if (gimple_code (stmt) == GIMPLE_COND)
>>>> ? ? ? ? ? ?{
>>>> - ? ? ? ? ? ? tree op0 = gimple_cond_lhs (stmt);
>>>> - ? ? ? ? ? ? tree op1 = gimple_cond_rhs (stmt);
>>>> + ? ? ? ? ? ? tree op[2];
>>>> ? ? ? ? ? ? ?tree result;
>>>> + ? ? ? ? ? ? vn_nary_op_t nary;
>>>>
>>>> - ? ? ? ? ? ? if (TREE_CODE (op0) == SSA_NAME)
>>>> - ? ? ? ? ? ? ? op0 = VN_INFO (op0)->valnum;
>>>> - ? ? ? ? ? ? if (TREE_CODE (op1) == SSA_NAME)
>>>> - ? ? ? ? ? ? ? op1 = VN_INFO (op1)->valnum;
>>>> + ? ? ? ? ? ? op[0] = gimple_cond_lhs (stmt);
>>>> + ? ? ? ? ? ? op[1] = gimple_cond_rhs (stmt);
>>>> + ? ? ? ? ? ? if (TREE_CODE (op[0]) == SSA_NAME)
>>>> + ? ? ? ? ? ? ? op[0] = VN_INFO (op[0])->valnum;
>>>> + ? ? ? ? ? ? if (TREE_CODE (op[1]) == SSA_NAME)
>>>> + ? ? ? ? ? ? ? op[1] = VN_INFO (op[1])->valnum;
>>>> ? ? ? ? ? ? ?result = fold_binary (gimple_cond_code (stmt), boolean_type_node,
>>>> - ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? op0, op1);
>>>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? op[0], op[1]);
>>>> + ? ? ? ? ? ? if (!result)
>>>> + ? ? ? ? ? ? ? result = vn_nary_op_lookup_pieces (2, gimple_cond_code (stmt),
>>>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?boolean_type_node,
>>>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?op, &nary);
>>>> +
>>>> ? ? ? ? ? ? ?if (result && TREE_CODE (result) == INTEGER_CST)
>>>> ? ? ? ? ? ? ? ?{
>>>> ? ? ? ? ? ? ? ? ?if (integer_zerop (result))
>>>> @@ -4354,6 +4361,13 @@ eliminate (void)
>>>> ? ? ? ? ? ? ? ? ?update_stmt (stmt);
>>>> ? ? ? ? ? ? ? ? ?todo = TODO_cleanup_cfg;
>>>> ? ? ? ? ? ? ? ?}
>>>> + ? ? ? ? ? ? else if (result && TREE_CODE (result) == SSA_NAME)
>>>> + ? ? ? ? ? ? ? {
>>>> + ? ? ? ? ? ? ? ? gimple_cond_set_code (stmt, NE_EXPR);
>>>> + ? ? ? ? ? ? ? ? gimple_cond_set_lhs (stmt, result);
>>>> + ? ? ? ? ? ? ? ? gimple_cond_set_rhs (stmt, boolean_false_node);
>>>> + ? ? ? ? ? ? ? ? update_stmt (stmt);
>>>> + ? ? ? ? ? ? ? }
>>>> ? ? ? ? ? ?}
>>>> ? ? ? ? ?/* Visit indirect calls and turn them into direct calls if
>>>> ? ? ? ? ? ? possible. ?*/
>>>>
>>>> you get the CSE (too simple patch, you need to check leaders properly).
>>>> You can then add similar lookups for an inverted conditional.
>>>
>>> Thanks for your explanation. On shortcoming of this method is that it
>>> cannot find/take cond_expr(and the implicitly defined variable) as the
>>> leader in pre. I guess this is why you said it can handle a subset of all
>>> cases in previous message?
>>
>> Yes. ?It won't handle
>>
>> ?if (x > 1)
>> ? ...
>> ?tem = x > 1;
>>
>> or
>>
>> ?if (x > 1)
>> ? ...
>> ?if (x > 1)
>>
>> though maybe we could teach PRE to do the insertion by properly
>> putting x > 1 into EXP_GEN in compute_avail (but not into AVAIL_OUT).
>> Not sure about this though. ?Currently we don't do anything to
>> GIMPLE_COND operands (which seems odd anyway, we should
>> at least add the operands to EXP_GEN).
> I spent some time on this issue again.
> Yes, we can insert compare EXPR in EXP_GEN(but not AVAIL_OUT).
> We also can teach PRE to insert the recorded compare EXPR in previous
> mentioned special cases to solve the problem.
> But, this way it's not different from factoring compare EXPR out of
> GIMPLE_COND, since insertion/elimination itself is a kind of rewriting.
> Thus I think the problem should be fixed by rewriting/factoring compare
> EXPR out of GIMPLE_COND.

Yes, see http://gcc.gnu.org/ml/gcc-patches/2010-08/msg02098.html
unfortunately it is a non-trivial task ;)

> Second point, as you said, PRE often get confused and moves compare
> EXPR far from jump statement. Could we rely on register re-materialize
> to handle this, or any other solution?

Well, a simple kind of solution would be to preprocess the IL before
redundancy elimination and separate the predicate computation from
their uses and then as followup combine predicates back (tree forwprop
would do that, for example - even for multiple uses).  The question is
what you gain in the end.

> I would like to learn more about this case, so do you have any opinion on
> how this should be fixed for now.

The GIMPLE IL should be better here, especially if you consider that
we force away predicate computation that may trap for -fnon-call-exceptions
already.  So, simplifying the IL is still the way to go IMHO.  But as I said
above - it's a non-trivial task with possibly much fallout.

Richard.

> Thanks
> --
> Best Regards.