This is the mail archive of the
`gcc@gcc.gnu.org`
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] |

*From*: Richard Biener <richard dot guenther at gmail dot com>*To*: Jeff Law <law at redhat dot com>,Andrew MacLeod <amacleod at redhat dot com>,Aldy Hernandez <aldyh at redhat dot com>*Cc*: GCC Mailing List <gcc at gcc dot gnu dot org>*Date*: Wed, 14 Sep 2016 21:29:58 +0200*Subject*: Re: fold() can't fold simple expressions?*Authentication-results*: sourceware.org; auth=none*References*: <57D94FC9.9070907@redhat.com> <CAFiYyc3ptSB9sJnAJgvrP8JC671pGX3K+wYxpZ0HYhD3niHCVg@mail.gmail.com> <57D959D9.2060004@redhat.com> <6df7ce2e-29c3-8a7f-7724-a10a4c046762@redhat.com>

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

**Follow-Ups**:**Re: fold() can't fold simple expressions?***From:*Andrew MacLeod

**Re: fold() can't fold simple expressions?***From:*Jeff Law

**References**:**fold() can't fold simple expressions?***From:*Aldy Hernandez

**Re: fold() can't fold simple expressions?***From:*Richard Biener

**Re: fold() can't fold simple expressions?***From:*Andrew MacLeod

**Re: fold() can't fold simple expressions?***From:*Jeff Law

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |