This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: fold() can't fold simple expressions?

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 <> wrote:
Hi folks.  I'm working on better range information with Macleod, and
been playing with folding arbitrary range expressions, which I expect
to ahem...fold.

I'm surprised that even seemingly simple trees can't be folded after
been built, because AFAICT, fold actually just works by recognizing
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),

(gdb) call debug_generic_stmt(x)
20 * 3 + 10;

(gdb) call debug_generic_stmt(fold(x))
20 * 3 + 10;

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

Am I missing something?  Is there another entry point for a toplevel
You are not missing anything.  This is all by design to improve
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
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);
           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


         SET_USE (...)
     update_stmt ()
     if (fold_stmt ())


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.

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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]