This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: fold() can't fold simple expressions?
On September 14, 2016 6:39:14 PM GMT+02:00, Jeff Law <law@redhat.com> wrote:
>On 09/14/2016 08:08 AM, Andrew MacLeod wrote:
>> On 09/14/2016 09:33 AM, Richard Biener wrote:
>>> On Wed, Sep 14, 2016 at 3:25 PM, Aldy Hernandez <aldyh@redhat.com>
>wrote:
>>>> Hi folks. I'm working on better range information with Macleod,
>and
>>>> I've
>>>> been playing with folding arbitrary range expressions, which I
>expect
>>>> fold()
>>>> to ahem...fold.
>>>>
>>>> I'm surprised that even seemingly simple trees can't be folded
>after
>>>> they've
>>>> been built, because AFAICT, fold actually just works by recognizing
>>>> patterns
>>>> it recognizes at the top level, not by recursing down to the
>sub-trees.
>>>>
>>>> For example, I was surprised at this:
>>>>
>>>> #define INT(N) build_int_cst (integer_type_node, (N))
>>>> tree x = build2 (PLUS_EXPR, integer_type_node,
>>>> build2 (MULT_EXPR, integer_type_node, INT(20),
>>>> INT(3)),
>>>> INT(10));
>>>>
>>>> (gdb) call debug_generic_stmt(x)
>>>> 20 * 3 + 10;
>>>>
>>>> (gdb) call debug_generic_stmt(fold(x))
>>>> 20 * 3 + 10;
>>> Yep.
>>>
>>>> I do know I can build everything with fold_buildN() and fold on the
>>>> fly, but
>>>> I can't because these are expressions that can have an SSA_NAME
>>>> somewhere in
>>>> there, and then after the fact, we substitute a constant in it. So
>>>> it is
>>>> only after the fact that we realize we can reduce said expression
>to a
>>>> constant.
>>>>
>>>> Am I missing something? Is there another entry point for a
>toplevel
>>>> fold()?
>>> You are not missing anything. This is all by design to improve
>>> complexity
>>> of fold ().
>>>
>>>> For now I'm just refolding everything which does the trick, and may
>even
>>>> work efficiently for small trees, but I'm hoping I'm not missing
>>>> something
>>>> completely obvious here. For the record...the refolder:
>>>>
>>>> static tree
>>>> refold (tree t)
>>>> {
>>>> enum tree_code code = TREE_CODE (t);
>>>> enum tree_code_class kind = TREE_CODE_CLASS (code);
>>>> if (IS_EXPR_CODE_CLASS (kind))
>>>> {
>>>> tree type = TREE_TYPE (t);
>>>> tree op0, op1, op2;
>>>>
>>>> switch (TREE_CODE_LENGTH (code))
>>>> {
>>>> case 1:
>>>> op0 = TREE_OPERAND (t, 0);
>>>> if (TREE_CODE (op0) != INTEGER_CST)
>>>> op0 = refold (op0);
>>>> return fold_build1 (code, type, op0);
>>>> case 2:
>>>> op0 = TREE_OPERAND (t, 0);
>>>> op1 = TREE_OPERAND (t, 1);
>>>> if (TREE_CODE (op0) != INTEGER_CST)
>>>> op0 = refold (op0);
>>>> if (TREE_CODE (op1) != INTEGER_CST)
>>>> op1 = refold (op1);
>>>> return fold_build2 (code, type, op0, op1);
>>>> case 3:
>>>> op0 = TREE_OPERAND (t, 0);
>>>> op1 = TREE_OPERAND (t, 1);
>>>> op2 = TREE_OPERAND (t, 2);
>>>> if (TREE_CODE (op0) != INTEGER_CST)
>>>> op0 = refold (op0);
>>>> if (TREE_CODE (op1) != INTEGER_CST)
>>>> op1 = refold (op1);
>>>> if (TREE_CODE (op2) != INTEGER_CST)
>>>> op1 = refold (op2);
>>>> return fold_build3 (code, type, op0, op1, op2);
>>>> default:
>>>> return t;
>>>> }
>>>> }
>>>> return t;
>>>> }
>>> .. which is horribly inefficient.
>>>
>>> Now my first question with "I get SSA names substituted" is ... WTF
>>> are you even
>>> having GENERIC trees when you are in SSA form? On GIMPLE you'd have
>sth
>>> like
>>>
>>> substitute-X-for-Y:
>>>
>>> FOR_EACH_IMM_USE_STMT (...)
>>> FOR_EACH_IMM_USE_ON_STMT (...)
>>> SET_USE (...)
>>> update_stmt ()
>>> if (fold_stmt ())
>>> maybe-fold-uses-of-defs
>>>
>>> Richard.
>>>
>>
>> We're sometimes evaluating ranges symbolically for a period of time
>> before we resolve them to an actual constant. So we can determine
>that
>> the range of same ssa_name based on how its calculated.
>> d_7 = a_3 + 2
>> d_8 = d_7 *2
>> if (d_8 < b_6)
>>
>> we can determine the range of d_8 to be [MIN_INT, b_6] on the true
>side
>> of the if.
>>
>> we can also determine that d_7 has a range as well
>> if (d_7 *2 < b_6) begets if (d_7 < b_6 / 2) so d_7 has a
>range
>> of [MIN_INT, b_6 / 2]
>> and furthermore,
>> if (a_3 +2 <b_6 / 2) begets if (a_3 < b_6 / 2 - 2) resulting is
>> a_3 having a range of [MIN_INT, b_6 / 2 -2]
>>
>>
>> If a request is made for a_3 on that edge, and VRP or some other
>> mechanism can determine that b_6 has a range of [0, 20] we can
>simply
>> fold 20 / 2 -2 and determine we also know a_3 has the range [0 , 8]
>>
>> So we currently end up with a small expression tree we'd like to
>fold.
>> It pretty trivial to roll our own little folder for the operations
>the
>> range generator understands, we just thought it would be handy to
>> leverage the folder during the proof of concept stage.
>It's also worth noting that a backwards substitution based threading,
>redundancy elimination, etc pass would need similar capabilities.
>
>Essentially you start with some gimple expression, say a + b. You then
>
>start walking backwards substituting the RHS of defining statements
>into
>the expression and simplifying as you go.
It's what match-and-simplify does as well.
I question the need to build GENERIC here though. M-a-s happily gets you a simplified expression as sequence of GIMPLE statements. (But does not yet provide a way to build a simplified GENERIC expression from GIMPLE IL)
Richard.
>
>So you can easily end up with an expression that is non-gimple. It's
>not in the IL though.
>
>Oh, and the similarities with RTL combine are significant :-)
>
>jeff