Re: [RFC] Meta-description for tree and gimple folding
On Thu, 24 Apr 2014, Jeff Law wrote: > On 02/28/14 08:21, Kai Tietz wrote: > > Hmm, this all reminds me about the approach Andrew Pinski and I came > > up with two years ago. All in all I think it might be worth to > > express folding-patterns in a more abstract way. So the md-like Lisp > > syntax for this seems to be just stringent. We make use of such a > > script-language already for machine-description. > > > > Nevertheless I doubt that we really want to have same facility for > > fold-const and gimple. Instead I got the impression that we would > > prefer to have all folding-optimizations instead in Middle-end > > (GIMPLE). We need folding in front-end (AST) mostly for determination > > of constant-expression detection. Otherwise we want to keep maximum of > > original AST to have best results for debugging (and even to think > > about having alternative FE on our middle/backend) and code-analyzers. > This is the core of what I want to see happening. I'm open to whatever > methods we use to take us in that direction. > > The way I tend to think leads me to a "hmm, fold-const.c does X, move it to > gimple" and iterate approach. But again, that's just the way I tend to look > at problems. > > If we can describe significant hunks of folding using a pattern selection > language and generate code to recognize and transform the IL, then that seems > good to me as long as we keep the goal of moving most folding out of the > front-ends. > > So if Richi and GSOC students want to experiment in this space, possibly > baking off with other approaches that delay folding, that's fine with me. Btw, while there is the possibility to generate GENERIC foldings from the meta-description for each and every pattern and use that from fold it is not necessary to do that. Note that the work also includes adding API that gets rid of most (if not all) [fold_]buildN and force_gimple_operand_* calls from GIMPLE passes (thus, not building GENERIC - just for the ability to fold it - and then gimplifying it). Instead of tree x = fold_build2 (PLUS_EXPR, type, y, build_int_cst (type, 1)); tree ex = fold_build2 (EQ_EXPR, boolean_type_node, x, y); ex = force_gimple_operand (ex, &stmts, true, NULL_TREE); you do tree x = gimple_build (&stmts, PLUS_EXPR, type, y, build_int_cst (type, 1)); tree ex = gimple_build (&stmts, EQ_EXPR, boolean_type_node, x, y); where the implementation on the branch (obviously) relies on the patterns to simplify the built expressions. This should also help Andrew with his GIMPLE type re-org as it frees him from touching fold ... (well, if all code is properly converted). It of course remains to be seen if we can reasonably translate the main part of the foldings passes rely on to the pattern representation. Nothing prevents us from providing a "tail" of manually written simplifications of course, used by the same API, but I'd like to avoid that. I hope that for 4.10 we get up to the point of using the machinery for a gimple-combine pass (currently tree forwprop) and stop adding simplifications to forwprop and instead extend the pattern description. I also hope to convert most passes over to gimple_build (requires mostly simple arithmetic simplification and simplification of conditionals). Comments on the actual code are always welcome - we'll do all the GSOC project discussions on implementation details in public to invite others to comment. Richard.
Re: [RFC] Meta-description for tree and gimple folding
On 03/03/14 07:05, Kai Tietz wrote: [the possibility to use offline verification tools for the transforms comes to my mind as well] This is actually a pretty interesting idea. As it would allow us to do testing for this area without side-effects by high-level passes, target-properties, etc Yea, the question is are there offline tools that we can use for this purpose? I simply haven't explored that space at all.; Additional I think we need to some related conceptional decisions here too. I saw here some missing concept for abstraction of back-end/target specific limitations in middle-end. For example the branch-cost optimization, or the target's pattern-preferences, etc. We lack to make a consequent difference between target-agnostic and target-specific passes in middle-end. There were introduced diagnostics in late passes. For latter see "possible integral overflow on additions in loops" as one sample. Such stuff hinders us to do better job on pattern-folding in many places. Right now we tend to introduce backend-representation too early (eg branch-cost, avoiding packing of conditional patterns due some limitiation on some targets, too early jump-threading, etc). So I think we should think about at least some passes doing target/backend agnostic folding/normalization, and doing target/backend-specific pattern-transformation explicit in latter passes. There's a lot of open questions in this space -- but I don't think we necessarily have to tie them together. If we can express simplifications in the way Richi wants, that seems largely independent of most of these issues. jeff
Re: [RFC] Meta-description for tree and gimple folding
On 02/28/14 08:21, Kai Tietz wrote: Hmm, this all reminds me about the approach Andrew Pinski and I came up with two years ago. All in all I think it might be worth to express folding-patterns in a more abstract way. So the md-like Lisp syntax for this seems to be just stringent. We make use of such a script-language already for machine-description. Nevertheless I doubt that we really want to have same facility for fold-const and gimple. Instead I got the impression that we would prefer to have all folding-optimizations instead in Middle-end (GIMPLE). We need folding in front-end (AST) mostly for determination of constant-expression detection. Otherwise we want to keep maximum of original AST to have best results for debugging (and even to think about having alternative FE on our middle/backend) and code-analyzers. This is the core of what I want to see happening. I'm open to whatever methods we use to take us in that direction. The way I tend to think leads me to a "hmm, fold-const.c does X, move it to gimple" and iterate approach. But again, that's just the way I tend to look at problems. If we can describe significant hunks of folding using a pattern selection language and generate code to recognize and transform the IL, then that seems good to me as long as we keep the goal of moving most folding out of the front-ends. So if Richi and GSOC students want to experiment in this space, possibly baking off with other approaches that delay folding, that's fine with me. Jeff
Re: [RFC] Meta-description for tree and gimple folding
On Wed, 12 Mar 2014, Marc Glisse wrote: > On Wed, 12 Mar 2014, Richard Biener wrote: > > > On Tue, 11 Mar 2014, Marc Glisse wrote: > > > > > On Mon, 3 Mar 2014, Richard Biener wrote: > > > > > > > > How do you handle a > > > > > transformation that currently tries to recursively fold something else > > > > > and > > > > > does the main transformation only if that simplified? > > > > > > > > And doesn't do the other folding (because it's not in the IL > > > > literally?)? > > > > Similar to the cst without overflow case, by writing custom C code > > > > and allowing that to signal failure. > > > > > > Note that for this kind of simplification, it can be inconvenient to have > > > canonicalization included with the "real" simplifications. Imagine I am > > > looking at (x?3:5)+y. If 3+y "simplifies" to y+3 and 5+y "simplifies" to > > > y+5, > > > then it looks worth it to replace the expression with x?y+3:(y+5). > > > > > > Would there be a convenient way to separate them, so it can tell me that > > > 3+y > > > should be replaced with y+3 but that it is not a simplification? > > > > You could certainly "mark" those patterns in a special way (though > > the specific case, 3 + y to y + 3 will happen behind patterns back, > > so in this case it won't tell you that 3 + y simplifies). > > Ah, that's good, maybe what I was asking for is mostly already there :-) > > > Note that > > you can't write patterns that apply "if 3 + y simplifies", at > > least not without doing sth as awkward as > > > > (match_and_simplify > > (plus (cond @0 @1 @2) @3) > > if (gimple_match_and_simplify (PLUS_EXPR, TREE_TYPE (@1), @1, @3, NULL, > > NULL) > > || gimple_match_and_simplify (PLUS_EXPR, TREE_TYPE (@2), @2, @3, > > NULL, NULL)) > > (cond @0 (plus @1 @3) (plus @2 @3))) > > I think it's ok having to write something a bit longer when doing complicated > things, as long as it is doable at all. > > > that is, very much do extra work. > > Ah, because the simplification of each PLUS_EXPR will be done twice? Yes. > > OTOH, I'd rather avoid adding those kind of patterns for now. There > > are interesting enough challenges with existing "simple" ones. > > Sure.
Re: [RFC] Meta-description for tree and gimple folding
On Wed, 12 Mar 2014, Richard Biener wrote: On Tue, 11 Mar 2014, Marc Glisse wrote: On Mon, 3 Mar 2014, Richard Biener wrote: How do you handle a transformation that currently tries to recursively fold something else and does the main transformation only if that simplified? And doesn't do the other folding (because it's not in the IL literally?)? Similar to the cst without overflow case, by writing custom C code and allowing that to signal failure. Note that for this kind of simplification, it can be inconvenient to have canonicalization included with the "real" simplifications. Imagine I am looking at (x?3:5)+y. If 3+y "simplifies" to y+3 and 5+y "simplifies" to y+5, then it looks worth it to replace the expression with x?y+3:(y+5). Would there be a convenient way to separate them, so it can tell me that 3+y should be replaced with y+3 but that it is not a simplification? You could certainly "mark" those patterns in a special way (though the specific case, 3 + y to y + 3 will happen behind patterns back, so in this case it won't tell you that 3 + y simplifies). Ah, that's good, maybe what I was asking for is mostly already there :-) Note that you can't write patterns that apply "if 3 + y simplifies", at least not without doing sth as awkward as (match_and_simplify (plus (cond @0 @1 @2) @3) if (gimple_match_and_simplify (PLUS_EXPR, TREE_TYPE (@1), @1, @3, NULL, NULL) || gimple_match_and_simplify (PLUS_EXPR, TREE_TYPE (@2), @2, @3, NULL, NULL)) (cond @0 (plus @1 @3) (plus @2 @3))) I think it's ok having to write something a bit longer when doing complicated things, as long as it is doable at all. that is, very much do extra work. Ah, because the simplification of each PLUS_EXPR will be done twice? OTOH, I'd rather avoid adding those kind of patterns for now. There are interesting enough challenges with existing "simple" ones. Sure. -- Marc Glisse
Re: [RFC] Meta-description for tree and gimple folding
On Tue, 11 Mar 2014, Marc Glisse wrote: > On Mon, 3 Mar 2014, Richard Biener wrote: > > > > How do you handle a > > > transformation that currently tries to recursively fold something else and > > > does the main transformation only if that simplified? > > > > And doesn't do the other folding (because it's not in the IL literally?)? > > Similar to the cst without overflow case, by writing custom C code > > and allowing that to signal failure. > > Note that for this kind of simplification, it can be inconvenient to have > canonicalization included with the "real" simplifications. Imagine I am > looking at (x?3:5)+y. If 3+y "simplifies" to y+3 and 5+y "simplifies" to y+5, > then it looks worth it to replace the expression with x?y+3:(y+5). > > Would there be a convenient way to separate them, so it can tell me that 3+y > should be replaced with y+3 but that it is not a simplification? You could certainly "mark" those patterns in a special way (though the specific case, 3 + y to y + 3 will happen behind patterns back, so in this case it won't tell you that 3 + y simplifies). Note that you can't write patterns that apply "if 3 + y simplifies", at least not without doing sth as awkward as (match_and_simplify (plus (cond @0 @1 @2) @3) if (gimple_match_and_simplify (PLUS_EXPR, TREE_TYPE (@1), @1, @3, NULL, NULL) || gimple_match_and_simplify (PLUS_EXPR, TREE_TYPE (@2), @2, @3, NULL, NULL)) (cond @0 (plus @1 @3) (plus @2 @3))) that is, very much do extra work. We'd maybe want to be able to instead write (match_and_simplify (plus (cond @0 @1 @2) @3) (cond @0 (plus:simplifies_p @1 @3) (plus:simplifies_p @2 @3))) but I'm not sure how to best express whether both expressions have to simplify or only one ... (eventually only allow || here, as we should commit to use a simplification once we created it, not throw it away eventually). Or sth like (match_and_simplify (plus (cond @0 @1 @2) @3) if simplifies (plus@4 @1 @3) (cond @0 @4 (plus @2 @3)) not sure how to do || vs. && (or even two simplifies conditions) best. OTOH, I'd rather avoid adding those kind of patterns for now. There are interesting enough challenges with existing "simple" ones. Richard.
Re: [RFC] Meta-description for tree and gimple folding
On Mon, 3 Mar 2014, Richard Biener wrote: How do you handle a transformation that currently tries to recursively fold something else and does the main transformation only if that simplified? And doesn't do the other folding (because it's not in the IL literally?)? Similar to the cst without overflow case, by writing custom C code and allowing that to signal failure. Note that for this kind of simplification, it can be inconvenient to have canonicalization included with the "real" simplifications. Imagine I am looking at (x?3:5)+y. If 3+y "simplifies" to y+3 and 5+y "simplifies" to y+5, then it looks worth it to replace the expression with x?y+3:(y+5). Would there be a convenient way to separate them, so it can tell me that 3+y should be replaced with y+3 but that it is not a simplification? -- Marc Glisse
Re: [RFC] Meta-description for tree and gimple folding
On Fri, 7 Mar 2014, Kai Tietz wrote: > 2014-03-04 14:14 GMT+01:00 Richard Biener : > > On Mon, 3 Mar 2014, Kai Tietz wrote: > > > >> 2014-03-03 12:33 GMT+01:00 Richard Biener : > >> > On Fri, 28 Feb 2014, Kai Tietz wrote: > >> > > >> >> Hmm, this all reminds me about the approach Andrew Pinski and I came > >> >> up with two years ago. > >> > > >> > You are talking about the gimple folding interface? Yes, but it's > >> > more similar to what I proposed before that. > >> > >> Well, this interface was for rtl, gimple, and tree AFAIR. > >> > >> > >> >> So I doubt that we want to keep fold-const patterns similar to gimple > >> >> (forward-prop) ones. > >> >> Wouldn't it make more sense to move fold-const patterns completely > >> >> into gimple, and having a facility in FE to ask gimple to *pre*-fold a > >> >> given tree to see if a constant-expression can be achieved? > >> > > >> > That was proposed by somebody, yes. The FE would hand off an > >> > expression to 1) the gimplifier to gimplify it, then 2) to the > >> > gimple folder to simplify it. Not sure if that's a good design > >> > but yes, it mimics the awkward thing we do now (genericize for > >> > folding in fold_stmt), just the other way around - and it makes > >> > it very costly. > >> > >> Right, if we would redo step one, and two each time we visit same > >> statement again, then of course we would produce pretty high load. > >> By hashing this *pre*-computed gimple-expression I think the load of > >> such an approach would lower pretty much. Of course it is true that > >> we move gimplification-costs to FE. Nevertheless the avarage costs > >> should be in general the same as we have them now. > >> > >> > >> > Having a single meta-description of simplifications makes it > >> > possible to have the best of both worlds (no need to GENERICIZE > >> > back from GIMPLE and no need to GIMPLIFY from GENERIC) with > >> > a single point of maintainance. > >> > >> True. I am fully agreeing to the positive effects of a single > >> meta-description for this area. For sure it is worth to avoid the > >> re-doing of the same folding for GENERIC/GIMPLE again and again. > >> > >> > [the possibility to use offline verification tools for the > >> > transforms comes to my mind as well] > >> This is actually a pretty interesting idea. As it would allow us to > >> do testing for this area without side-effects by high-level passes, > >> target-properties, etc > >> > >> > If you think the .md style pattern definitions are too limiting > >> > can you think of sth more powerful without removing the possibility > >> > of implementing the matching with a state machine to make it O(1)? > >> > >> Well, I am not opposed to the use of .md style pattern defintions at > >> all. I see just some weaknesses on the current tree-folding > >> mechanism. > >> AST folder tries to fold into statementes by recursion into. This > >> causes pretty high load in different areas. Like stack-growth, > >> unnecessary repetition of operations on inner-statements, and complex > >> patterns for expression associative/distributive/commutative rules for > >> current operation-code. > > > > Actually it doesn't recurse - it avoids recursion by requiring > > each sub-pattern to be already folded. > > Right, in general that is true. Sorry I expressed myself wrong. I > mean things like fold_truth_andor. That still may happen - "folded" results are still re-matched and simplified, and I think we want to retain that property (though as it's auto-generated putting in a recursion limit is easy). > >> I am thinking about a model where we use just for the > >> base-fold-operations the .md-style pattern definitions. On top of this > >> model we set a layer implementing associative/commutative/distributive > >> properties for statements in an optimize form. > > > > Sure, that would be a pass using the match-and-simplify infrastructure. > > In fact the infrastructure alone only provides enough to do the > > bare folding. > > Well, I am not sure if it is the best approach to have > commutative/associative/distributive only within a pass. Sure > forward-propagation-pass would be a candidate for this. nevertheless > should we fold generated conditions (and other generated > code-patterns) at time of generation including handling those laws? Yes, sure. The API now provides 'gimple_build' similar to how we now use fold_buildN. Thus, tree expr = fold_build2 (EQ_EXPR, boolean_type_node, fold_build2 (PLUS_EXPR, integer_type_node, op1, op2), op3); expr = force_gimple_operand (expr, &seq, true, NULL_TREE); becomes tree expr = gimple_build (&seq, EQ_EXPR, boolean_type_node, gimple_build (&seq, PLUS_EXPR, integer_type_node, op1, op2), op3); thus it will both simplify and create a gimple sequence rather than a GENERIC tree that you need to gimplify. Richard.
Re: [RFC] Meta-description for tree and gimple folding
2014-03-04 14:14 GMT+01:00 Richard Biener : > On Mon, 3 Mar 2014, Kai Tietz wrote: > >> 2014-03-03 12:33 GMT+01:00 Richard Biener : >> > On Fri, 28 Feb 2014, Kai Tietz wrote: >> > >> >> Hmm, this all reminds me about the approach Andrew Pinski and I came >> >> up with two years ago. >> > >> > You are talking about the gimple folding interface? Yes, but it's >> > more similar to what I proposed before that. >> >> Well, this interface was for rtl, gimple, and tree AFAIR. >> >> >> >> So I doubt that we want to keep fold-const patterns similar to gimple >> >> (forward-prop) ones. >> >> Wouldn't it make more sense to move fold-const patterns completely >> >> into gimple, and having a facility in FE to ask gimple to *pre*-fold a >> >> given tree to see if a constant-expression can be achieved? >> > >> > That was proposed by somebody, yes. The FE would hand off an >> > expression to 1) the gimplifier to gimplify it, then 2) to the >> > gimple folder to simplify it. Not sure if that's a good design >> > but yes, it mimics the awkward thing we do now (genericize for >> > folding in fold_stmt), just the other way around - and it makes >> > it very costly. >> >> Right, if we would redo step one, and two each time we visit same >> statement again, then of course we would produce pretty high load. >> By hashing this *pre*-computed gimple-expression I think the load of >> such an approach would lower pretty much. Of course it is true that >> we move gimplification-costs to FE. Nevertheless the avarage costs >> should be in general the same as we have them now. >> >> >> > Having a single meta-description of simplifications makes it >> > possible to have the best of both worlds (no need to GENERICIZE >> > back from GIMPLE and no need to GIMPLIFY from GENERIC) with >> > a single point of maintainance. >> >> True. I am fully agreeing to the positive effects of a single >> meta-description for this area. For sure it is worth to avoid the >> re-doing of the same folding for GENERIC/GIMPLE again and again. >> >> > [the possibility to use offline verification tools for the >> > transforms comes to my mind as well] >> This is actually a pretty interesting idea. As it would allow us to >> do testing for this area without side-effects by high-level passes, >> target-properties, etc >> >> > If you think the .md style pattern definitions are too limiting >> > can you think of sth more powerful without removing the possibility >> > of implementing the matching with a state machine to make it O(1)? >> >> Well, I am not opposed to the use of .md style pattern defintions at >> all. I see just some weaknesses on the current tree-folding >> mechanism. >> AST folder tries to fold into statementes by recursion into. This >> causes pretty high load in different areas. Like stack-growth, >> unnecessary repetition of operations on inner-statements, and complex >> patterns for expression associative/distributive/commutative rules for >> current operation-code. > > Actually it doesn't recurse - it avoids recursion by requiring > each sub-pattern to be already folded. Right, in general that is true. Sorry I expressed myself wrong. I mean things like fold_truth_andor. >> I am thinking about a model where we use just for the >> base-fold-operations the .md-style pattern definitions. On top of this >> model we set a layer implementing associative/commutative/distributive >> properties for statements in an optimize form. > > Sure, that would be a pass using the match-and-simplify infrastructure. > In fact the infrastructure alone only provides enough to do the > bare folding. Well, I am not sure if it is the best approach to have commutative/associative/distributive only within a pass. Sure forward-propagation-pass would be a candidate for this. nevertheless should we fold generated conditions (and other generated code-patterns) at time of generation including handling those laws? Kai
Re: [RFC] Meta-description for tree and gimple folding
On Tue, 4 Mar 2014, Marc Glisse wrote: > On Mon, 3 Mar 2014, Richard Biener wrote: > > > > How do I restrict some subexpression to have > > > a single use? > > > > This kind of restrictions come via the valueize() hook - simply > > valueize to NULL_TREE to make the match fail (for example > > SSA_NAME_OCCURS_IN_ABNORMAL_PHI could be made fail that way). > > Shouldn't that single-use property depend more on the transformation and less > on where it is called from? a+b-b -> a is always going to be a good idea > (well, register pressure aside), even if a+b is used in many other places. But > if you are using a*b elsewhere, turning a*b+c into FMA doesn't make so much > sense. Yeah, that's true. > Well, we can always call has_single_use on some @i if it is an SSA_NAME. Sure. As I have to add the capability to guard patterns with flags doing an additional has_single_use test there is easy (but of course that's something only available when in SSA form - something to keep in mind if we also want to create a GENERIC variant of the transform). Note that the concept of having a single-use makes whether a pattern matches possibly dependent on the order of processing uses and dependent on dead code being removed. Just sth to keep in mind if you want the maximum number of transforms rather than being cautious by default. > > > If I write a COND_EXPR matcher, could it generate code for phiopt as > > > well? > > > > Not sure, what do you have in mind specifically? > > fold-const.c has the equivalent of: > (define_match_and_simplify abs > (COND_EXPR (LT_EXPR @0 zero_p) (NEGATE_EXPR @0) @0) > (ABS_EXPR @0)) > > (it would help to be able to write LT_EXPR|LE_EXPR, maybe even to try > automatically simplify(!a)?c:b for a?b:c) > which works well on trees, but requires more complicated code in phiopt (same > for min/max). Yeah, inventing short-cuts for stuff like LT_EXPR|LE_EXPR or (PLUS_EXPR sub-expr1 sub-expr2) vs. (PLUS_EXPR sub-expr2 sub-expr1) is on my list. In the end it will (internally) duplicate the pattern to have one for each variant. I'm still pondering over the exact syntax for both (I can easily add builtin knowledge for commutative operators of course). Eventually the preprocessor comes to our rescue here ... #define X(CMP) \ (define_match_and_simplify \ ((COND_EXPR (CMP @0 zero_p) (NEGATE_EXPR @0) @0) \ (ABS_EXPR @0)) X(LT_EXPR) X(LE_EXPR) uglier than sth like (define_op LT_OR_LE_EXPR LT_EXPR|LE_EXPR) (define_match_and_simplify ((COND_EXPR (LT_OR_LE_EXPR @0 zero_p) ... or what you proposed. But how do you handle (BIT_IOR_EXPR (LT_EXPR|LE_EXPR @0 @1) (GE_EXPR|GT_EXPR @0 @1)) for example? a) Match variants in lock-step? b) Have the above generate 4 variants? c) Disallow it (looks error-prone)? I'd rather keep it simple for now ;) > > > How do you handle a > > > transformation that currently tries to recursively fold something else and > > > does the main transformation only if that simplified? > > > > And doesn't do the other folding (because it's not in the IL literally?)? > > Similar to the cst without overflow case, by writing custom C code > > and allowing that to signal failure. > > I am not sure if it will be easy to write code that works for generic and > gimple. I'll see... That's true - though GIMPLE and GENERIC share trees which makes it easy enough for most of the cases. We'll see ... For now I'm concentrating of fitting the framework into forwprop, replacing manual patterns that occur there. Richard.
Re: [RFC] Meta-description for tree and gimple folding
On Mon, 3 Mar 2014, Richard Biener wrote: How do I restrict some subexpression to have a single use? This kind of restrictions come via the valueize() hook - simply valueize to NULL_TREE to make the match fail (for example SSA_NAME_OCCURS_IN_ABNORMAL_PHI could be made fail that way). Shouldn't that single-use property depend more on the transformation and less on where it is called from? a+b-b -> a is always going to be a good idea (well, register pressure aside), even if a+b is used in many other places. But if you are using a*b elsewhere, turning a*b+c into FMA doesn't make so much sense. Well, we can always call has_single_use on some @i if it is an SSA_NAME. If I write a COND_EXPR matcher, could it generate code for phiopt as well? Not sure, what do you have in mind specifically? fold-const.c has the equivalent of: (define_match_and_simplify abs (COND_EXPR (LT_EXPR @0 zero_p) (NEGATE_EXPR @0) @0) (ABS_EXPR @0)) (it would help to be able to write LT_EXPR|LE_EXPR, maybe even to try automatically simplify(!a)?c:b for a?b:c) which works well on trees, but requires more complicated code in phiopt (same for min/max). How do you handle a transformation that currently tries to recursively fold something else and does the main transformation only if that simplified? And doesn't do the other folding (because it's not in the IL literally?)? Similar to the cst without overflow case, by writing custom C code and allowing that to signal failure. I am not sure if it will be easy to write code that works for generic and gimple. I'll see... -- Marc Glisse
Re: [RFC] Meta-description for tree and gimple folding
On Mon, 3 Mar 2014, Kai Tietz wrote: > 2014-03-03 12:33 GMT+01:00 Richard Biener : > > On Fri, 28 Feb 2014, Kai Tietz wrote: > > > >> Hmm, this all reminds me about the approach Andrew Pinski and I came > >> up with two years ago. > > > > You are talking about the gimple folding interface? Yes, but it's > > more similar to what I proposed before that. > > Well, this interface was for rtl, gimple, and tree AFAIR. > > > >> So I doubt that we want to keep fold-const patterns similar to gimple > >> (forward-prop) ones. > >> Wouldn't it make more sense to move fold-const patterns completely > >> into gimple, and having a facility in FE to ask gimple to *pre*-fold a > >> given tree to see if a constant-expression can be achieved? > > > > That was proposed by somebody, yes. The FE would hand off an > > expression to 1) the gimplifier to gimplify it, then 2) to the > > gimple folder to simplify it. Not sure if that's a good design > > but yes, it mimics the awkward thing we do now (genericize for > > folding in fold_stmt), just the other way around - and it makes > > it very costly. > > Right, if we would redo step one, and two each time we visit same > statement again, then of course we would produce pretty high load. > By hashing this *pre*-computed gimple-expression I think the load of > such an approach would lower pretty much. Of course it is true that > we move gimplification-costs to FE. Nevertheless the avarage costs > should be in general the same as we have them now. > > > > Having a single meta-description of simplifications makes it > > possible to have the best of both worlds (no need to GENERICIZE > > back from GIMPLE and no need to GIMPLIFY from GENERIC) with > > a single point of maintainance. > > True. I am fully agreeing to the positive effects of a single > meta-description for this area. For sure it is worth to avoid the > re-doing of the same folding for GENERIC/GIMPLE again and again. > > > [the possibility to use offline verification tools for the > > transforms comes to my mind as well] > This is actually a pretty interesting idea. As it would allow us to > do testing for this area without side-effects by high-level passes, > target-properties, etc > > > If you think the .md style pattern definitions are too limiting > > can you think of sth more powerful without removing the possibility > > of implementing the matching with a state machine to make it O(1)? > > Well, I am not opposed to the use of .md style pattern defintions at > all. I see just some weaknesses on the current tree-folding > mechanism. > AST folder tries to fold into statementes by recursion into. This > causes pretty high load in different areas. Like stack-growth, > unnecessary repetition of operations on inner-statements, and complex > patterns for expression associative/distributive/commutative rules for > current operation-code. Actually it doesn't recurse - it avoids recursion by requiring each sub-pattern to be already folded. > I am thinking about a model where we use just for the > base-fold-operations the .md-style pattern definitions. On top of this > model we set a layer implementing associative/commutative/distributive > properties for statements in an optimize form. Sure, that would be a pass using the match-and-simplify infrastructure. In fact the infrastructure alone only provides enough to do the bare folding. > By this we can do two different things with lower load. One hand we > can do "virtual" folding and avoid tree-rebuilding without need. On > the second hand we can use same pass for "normalize" tree structure of > expression-chains. > Additionally we can get rid of the than pretty useless reassociation > pass, which is IMHO just necessary by gimple-folders inability to do > that. Well ... you still need a pass that re-associates (or distributes or applies whatever properties) to feed the match-and-simplify infrastructure with proper input. So no, reassoc won't get and isn't useless. Richard.
Re: [RFC] Meta-description for tree and gimple folding
2014-03-03 12:33 GMT+01:00 Richard Biener : > On Fri, 28 Feb 2014, Kai Tietz wrote: > >> Hmm, this all reminds me about the approach Andrew Pinski and I came >> up with two years ago. > > You are talking about the gimple folding interface? Yes, but it's > more similar to what I proposed before that. Well, this interface was for rtl, gimple, and tree AFAIR. >> So I doubt that we want to keep fold-const patterns similar to gimple >> (forward-prop) ones. >> Wouldn't it make more sense to move fold-const patterns completely >> into gimple, and having a facility in FE to ask gimple to *pre*-fold a >> given tree to see if a constant-expression can be achieved? > > That was proposed by somebody, yes. The FE would hand off an > expression to 1) the gimplifier to gimplify it, then 2) to the > gimple folder to simplify it. Not sure if that's a good design > but yes, it mimics the awkward thing we do now (genericize for > folding in fold_stmt), just the other way around - and it makes > it very costly. Right, if we would redo step one, and two each time we visit same statement again, then of course we would produce pretty high load. By hashing this *pre*-computed gimple-expression I think the load of such an approach would lower pretty much. Of course it is true that we move gimplification-costs to FE. Nevertheless the avarage costs should be in general the same as we have them now. > Having a single meta-description of simplifications makes it > possible to have the best of both worlds (no need to GENERICIZE > back from GIMPLE and no need to GIMPLIFY from GENERIC) with > a single point of maintainance. True. I am fully agreeing to the positive effects of a single meta-description for this area. For sure it is worth to avoid the re-doing of the same folding for GENERIC/GIMPLE again and again. > [the possibility to use offline verification tools for the > transforms comes to my mind as well] This is actually a pretty interesting idea. As it would allow us to do testing for this area without side-effects by high-level passes, target-properties, etc > If you think the .md style pattern definitions are too limiting > can you think of sth more powerful without removing the possibility > of implementing the matching with a state machine to make it O(1)? Well, I am not opposed to the use of .md style pattern defintions at all. I see just some weaknesses on the current tree-folding mechanism. AST folder tries to fold into statementes by recursion into. This causes pretty high load in different areas. Like stack-growth, unnecessary repetition of operations on inner-statements, and complex patterns for expression associative/distributive/commutative rules for current operation-code. I am thinking about a model where we use just for the base-fold-operations the .md-style pattern definitions. On top of this model we set a layer implementing associative/commutative/distributive properties for statements in an optimize form. By this we can do two different things with lower load. One hand we can do "virtual" folding and avoid tree-rebuilding without need. On the second hand we can use same pass for "normalize" tree structure of expression-chains. Additionally we can get rid of the than pretty useless reassociation pass, which is IMHO just necessary by gimple-folders inability to do that. > Thanks, > Richard. Additional I think we need to some related conceptional decisions here too. I saw here some missing concept for abstraction of back-end/target specific limitations in middle-end. For example the branch-cost optimization, or the target's pattern-preferences, etc. We lack to make a consequent difference between target-agnostic and target-specific passes in middle-end. There were introduced diagnostics in late passes. For latter see "possible integral overflow on additions in loops" as one sample. Such stuff hinders us to do better job on pattern-folding in many places. Right now we tend to introduce backend-representation too early (eg branch-cost, avoiding packing of conditional patterns due some limitiation on some targets, too early jump-threading, etc). So I think we should think about at least some passes doing target/backend agnostic folding/normalization, and doing target/backend-specific pattern-transformation explicit in latter passes. Regards, Kai
Re: [RFC] Meta-description for tree and gimple folding
On Fri, 28 Feb 2014, Kai Tietz wrote: > Hmm, this all reminds me about the approach Andrew Pinski and I came > up with two years ago. You are talking about the gimple folding interface? Yes, but it's more similar to what I proposed before that. > All in all I think it might be worth to > express folding-patterns in a more abstract way. So the md-like Lisp > syntax for this seems to be just stringent. We make use of such a > script-language already for machine-description. That's the reason I use something similar. Because that form proved useful for instruction selection and peephole-like transforms. Exactly what you can generate a state machine for for matching (the current serial try-fail-try-fail... processing of cases is bad). > Nevertheless I doubt that we really want to have same facility for > fold-const and gimple. Instead I got the impression that we would > prefer to have all folding-optimizations instead in Middle-end > (GIMPLE). We need folding in front-end (AST) mostly for determination > of constant-expression detection. Otherwise we want to keep maximum of > original AST to have best results for debugging (and even to think > about having alternative FE on our middle/backend) and code-analyzers. True, but it's a dead end to rely on FEs implementing their own folding to be able to remove sth from fold-const.c. And we don't exactly have to implement the GENERIC code generation part. > So I doubt that we want to keep fold-const patterns similar to gimple > (forward-prop) ones. > Wouldn't it make more sense to move fold-const patterns completely > into gimple, and having a facility in FE to ask gimple to *pre*-fold a > given tree to see if a constant-expression can be achieved? That was proposed by somebody, yes. The FE would hand off an expression to 1) the gimplifier to gimplify it, then 2) to the gimple folder to simplify it. Not sure if that's a good design but yes, it mimics the awkward thing we do now (genericize for folding in fold_stmt), just the other way around - and it makes it very costly. Having a single meta-description of simplifications makes it possible to have the best of both worlds (no need to GENERICIZE back from GIMPLE and no need to GIMPLIFY from GENERIC) with a single point of maintainance. [the possibility to use offline verification tools for the transforms comes to my mind as well] If you think the .md style pattern definitions are too limiting can you think of sth more powerful without removing the possibility of implementing the matching with a state machine to make it O(1)? Thanks, Richard.
Re: [RFC] Meta-description for tree and gimple folding
On Fri, 28 Feb 2014, Diego Novillo wrote:
> On Thu, Feb 27, 2014 at 9:34 AM, Richard Biener wrote:
>
> > Comments or suggestions?
>
> On the surface it looks like a nice idea. However, I would like to
> understand the scope of this. Are you thinking of a pattern matcher
> with peephole like actions? Or would you like to evolve a DSL capable
> of writing compiler passes? (much like MELT).
>
> I prefer keeping it simple and limit the scope to pattern matching and
> replacement. There will be other things to handle, however (overflow,
> trapping arithmetic, etc). The language will grow over time.
>
> In terms of the mini-language, I don't like the lisp syntax but I
> appreciate that it is a familiar language for GCC since the backend
> uses it extensively.
>
> Please consider testing facilities as well. We should be able to write
> unit tests in this language to test its syntax validation, semantic
> actions, and transformations.
Ok, so let me summarize some of the goals which should answer most
of the questions above.
1) The IL matching should be translatable to a state machine
so it becomes O(1) and not O(number of patterns). [so we
should be able to move to "mandatory folding" on stmt
changes in GIMPLE, similar to how we've done it with
requiring you to use fold_buildN instead of buildN.
Currently that has a very high cost because we re-build
GENERIC on folding GIMPLE and dispatch to fold-const.c]
2) The generator should be able to target both GENERIC and
GIMPLE so we can "move" things from fold-const.c to GIMPLE
("move" as in add it to GIMPLE but leave it in fold-const.c
to not regress frontend dependences on it).
3) The whole thing should enable transitioning away from
using force_gimple_operand (fold_buildN ()) by providing
the GIMPLE equivalent of fold_buildN. [less trees in the
middle-end]
4) The API to the match-and-simplify routine should allow
(SSA) propagators to use the routine for simplifying
stmts with their current lattice value (CCP, DOM and
SCCVN are the obvious candidates here).
So yes, because of 1) the matching part will be similar to
how the machine description handles insns. The actual
transform can be more complex (and I expect it so, see my
reply to Marc).
I expect the language to grow over the existing proposal
but not so much over time (at least I hope so - heh).
As of testing facilities ... I don't see how I can use
the language to write tests? Do you think of sth like
(very simplified)
/* Match and simplify CST + CST to CST'. */
(define_match_and_simplify baz
(PLUS_EXPR INTEGER_CST_P@0 INTEGER_CST_P@1)
{ int_const_binop (PLUS_EXPR, captures[0], captures[1]); })
(test baz
(PLUS_EXPR 1 2)
3)
?
Thanks,
Richard.
Re: [RFC] Meta-description for tree and gimple folding
On Fri, 28 Feb 2014, Marc Glisse wrote:
> On Thu, 27 Feb 2014, Richard Biener wrote:
>
> > I've been hacking on a prototype that generates matching and
> > simplification code from a meta-description. The goal is
> > to provide a single source of transforms currently spread
> > over the compiler, mostly fold-const.c, gimple-fold.c and
> > tree-ssa-forwprop.c. Another goal is to make these transforms
> > (which are most of the form of generating a simpler form of
> > a pattern-matched IL piece) more readily available to passes
> > like value-numbering so they can be used on-the-fly, using
> > information provided by the pass lattice. The ultimate
> > goal is to generate (most of) fold-const.c and gimple-fold.c
> > and tree-ssa-forwprop.c from a single meta description.
> [...]
> > Comments or suggestions?
>
> It is hard to judge from such simple examples. What if I want to do the
> transformation only if CST+CST' doesn't overflow?
We'd probably make the generator possibly fail, eventually adding the
ability for a variant like
/* Match and simplify CST + CST to CST'. */
(define_match_and_simplify baz
(PLUS_EXPR INTEGER_CST_P@0 INTEGER_CST_P@1)
{
captures[0] = int_const_binop (PLUS_EXPR, captures[0], captures[1]);
if (TREE_OVERFLOW (captures[0]))
captures[0] = NULL_TREE;
}
@0)
that is, allow a complete manual transform step with a possible
FAIL outcome.
> Can I make it handle commutative operations cleverly?
As the goal is to allow a state machine to be generated for the matching
(to make the matching O(1) independent of the number of patterns)
the generator would have to duplicate the pattern internally. But yes,
I've thought about commutativeness.
> How do I restrict some subexpression to have
> a single use?
This kind of restrictions come via the valueize() hook - simply
valueize to NULL_TREE to make the match fail (for example
SSA_NAME_OCCURS_IN_ABNORMAL_PHI could be made fail that way).
> If I want to check some flag_*, do I have to create a predicate
> that tests for that as well as whatever other test the specific operand
> needed?
You mean like a pattern that is enabled conditinal on, for example,
flag_unsafe_math_optimizations? Didn't think of that yet, but we
can easily add an optional overall pattern condition like we have
in the RTL md files.
> Won't valueize create a lot of not-so-necessary trees when used on
> gimple?
No, valueize should only valueize to SSA names or constants, not
expressions. It's purpose is to integrate well with a SSA propagator
lattice - for example the tree-ssa-sccvn.c integration (subsume
it's "simplify" implementation) would be
Index: gcc/tree-ssa-sccvn.c
===
--- gcc/tree-ssa-sccvn.c(revision 208269)
+++ gcc/tree-ssa-sccvn.c(working copy)
@@ -3344,35 +3344,23 @@ try_to_simplify (gimple stmt)
if (code == SSA_NAME)
return NULL_TREE;
- /* First try constant folding based on our current lattice. */
+ /* First try constant folding based on our current lattice.
+ ??? Should be subsumed by gimple_match_and_simplify. */
tem = gimple_fold_stmt_to_constant_1 (stmt, vn_valueize);
if (tem
&& (TREE_CODE (tem) == SSA_NAME
|| is_gimple_min_invariant (tem)))
return tem;
- /* If that didn't work try combining multiple statements. */
- switch (TREE_CODE_CLASS (code))
-{
-case tcc_reference:
- /* Fallthrough for some unary codes that can operate on registers.
*/
- if (!(code == REALPART_EXPR
- || code == IMAGPART_EXPR
- || code == VIEW_CONVERT_EXPR
- || code == BIT_FIELD_REF))
- break;
- /* We could do a little more with unary ops, if they expand
-into binary ops, but it's debatable whether it is worth it. */
-case tcc_unary:
- return simplify_unary_expression (stmt);
-
-case tcc_comparison:
-case tcc_binary:
- return simplify_binary_expression (stmt);
-
-default:
- break;
-}
+ /* If that didn't work try combining multiple statements.
+ ??? Handle multiple stmts being generated by storing
+ at most one in VN_INFO->expr? But then we'd have to
+ transparently support materializing temporary SSA names
+ created by gimple_match_and_simplify - or we never value-number
+ to them. */
+ if (TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME)
+ return gimple_match_and_simplify (gimple_assign_lhs (stmt),
+ NULL, vn_valueize);
return NULL_TREE;
}
> If I write a COND_EXPR matcher, could it generate code for phiopt as
> well?
Not sure, what do you have in mind specifically?
> What is the point of gimple_match (without _and_substitute)? Will it
> clean up the new dead statements after itself?
No, the low-level interface won't. I'm not yet decided if we should
have an alternate interface taking a stmt iterator rather than a
SSA name and sequence pointer
Re: [RFC] Meta-description for tree and gimple folding
Am 02/27/2014 03:34 PM, schrieb Richard Biener:
I've been hacking on a prototype that generates matching and
simplification code from a meta-description. The goal is
to provide a single source of transforms currently spread
over the compiler, mostly fold-const.c, gimple-fold.c and
tree-ssa-forwprop.c. Another goal is to make these transforms
(which are most of the form of generating a simpler form of
a pattern-matched IL piece) more readily available to passes
like value-numbering so they can be used on-the-fly, using
information provided by the pass lattice. The ultimate
goal is to generate (most of) fold-const.c and gimple-fold.c
and tree-ssa-forwprop.c from a single meta description.
Currently the prototype can generate code to match and simplify
on the GIMPLE IL and it uses a very simple description right now
(following the lispy style we have for machine descriptions).
For example
(define_match_and_simplify foo
(PLUS_EXPR (MINUS_EXPR integral_op_p@0 @1) @1)
@0)
Matches (A - B) + B and transforms it to A. More complex
replacements involving modifying of matches operands can be
done with inlined C code:
(define_match_and_simplify bar
(PLUS_EXPR INTEGER_CST_P@0 (PLUS_EXPR @1 INTEGER_CST_P@2))
(PLUS_EXPR { int_const_binop (PLUS_EXPR, captures[0], captures[2]); } @1))
which matches CST1 + (X + CST2) and transforms it to (CST1 + CST2) + X
(thus it reassociates but it also simplifies the constant part).
Hi Richard,
in the past there were some bugs in folding that introduced undefined behaviour
because they produced different signed overflow.
One example is PR56899 that folded
(1 - X) * CST1
to
X * (-CST1) + CST1
How is this expressed in the pattern. Is there something like a condition (like
in insns)? Or will this be encoded in the operation?
Johann
Writing patterns will require a few new predicates like
INTEGER_CST_P or integral_op_p.
At this point I'll try integrating the result into a few
GIMPLE passes (forwprop and SCCVN) to see if the interface
works well enough. Currently the GIMPLE interface is
tree
gimple_match_and_simplify (tree name, gimple_seq *seq,
tree (*valueize)(tree));
where the simplification happens on the defining statement
of the SSA name name and a is_gimple_val result is returned.
Any intermediate stmts are appended to 'seq' (or NULL_TREE
is returned if that would be necessary and 'seq' is NULL)
and all SSA names matched and generated are valueized using
the valueize callback (if not NULL). Thus for the first
example above we'd return A and do not touch seq while
for the second example we'd return a new temporary SSA
name and append name = CST' + X to seq (we might want
to allow in-place modification of the def stmt of name
as well, I'm not sure yet - that's the forwprop way of operation)
Patch below for reference.
Comments or suggestions?
Thanks,
Richard.
Re: [RFC] Meta-description for tree and gimple folding
Hmm, this all reminds me about the approach Andrew Pinski and I came up with two years ago. All in all I think it might be worth to express folding-patterns in a more abstract way. So the md-like Lisp syntax for this seems to be just stringent. We make use of such a script-language already for machine-description. Nevertheless I doubt that we really want to have same facility for fold-const and gimple. Instead I got the impression that we would prefer to have all folding-optimizations instead in Middle-end (GIMPLE). We need folding in front-end (AST) mostly for determination of constant-expression detection. Otherwise we want to keep maximum of original AST to have best results for debugging (and even to think about having alternative FE on our middle/backend) and code-analyzers. So I doubt that we want to keep fold-const patterns similar to gimple (forward-prop) ones. Wouldn't it make more sense to move fold-const patterns completely into gimple, and having a facility in FE to ask gimple to *pre*-fold a given tree to see if a constant-expression can be achieved? Regards, Kai
Re: [RFC] Meta-description for tree and gimple folding
On Thu, Feb 27, 2014 at 9:34 AM, Richard Biener wrote: > Comments or suggestions? On the surface it looks like a nice idea. However, I would like to understand the scope of this. Are you thinking of a pattern matcher with peephole like actions? Or would you like to evolve a DSL capable of writing compiler passes? (much like MELT). I prefer keeping it simple and limit the scope to pattern matching and replacement. There will be other things to handle, however (overflow, trapping arithmetic, etc). The language will grow over time. In terms of the mini-language, I don't like the lisp syntax but I appreciate that it is a familiar language for GCC since the backend uses it extensively. Please consider testing facilities as well. We should be able to write unit tests in this language to test its syntax validation, semantic actions, and transformations. Diego.
Re: [RFC] Meta-description for tree and gimple folding
On Thu, 27 Feb 2014, Richard Biener wrote: I've been hacking on a prototype that generates matching and simplification code from a meta-description. The goal is to provide a single source of transforms currently spread over the compiler, mostly fold-const.c, gimple-fold.c and tree-ssa-forwprop.c. Another goal is to make these transforms (which are most of the form of generating a simpler form of a pattern-matched IL piece) more readily available to passes like value-numbering so they can be used on-the-fly, using information provided by the pass lattice. The ultimate goal is to generate (most of) fold-const.c and gimple-fold.c and tree-ssa-forwprop.c from a single meta description. [...] Comments or suggestions? It is hard to judge from such simple examples. What if I want to do the transformation only if CST+CST' doesn't overflow? Can I make it handle commutative operations cleverly? How do I restrict some subexpression to have a single use? If I want to check some flag_*, do I have to create a predicate that tests for that as well as whatever other test the specific operand needed? Won't valueize create a lot of not-so-necessary trees when used on gimple? If I write a COND_EXPR matcher, could it generate code for phiopt as well? What is the point of gimple_match (without _and_substitute)? Will it clean up the new dead statements after itself? Can I write (PLUS_EXPR@0 @1 @2) so I can still refer to this subexpression later? How do you handle a transformation that currently tries to recursively fold something else and does the main transformation only if that simplified? I guess most of the answers will become obvious once you have converted a few existing transformations and I can look at those... Since this is going to require a rewrite of many transformations, I wonder if there are things that should be improved before starting so we can write the right tests directly. For A+B-B, we can do the transformation if the type is an integer for which overflow either wraps or is undefined or traps-but-it-is-ok-to-remove-those-traps (but not if it traps and we promise to preserve traps, or if the type saturates), or the type is a float and we have the unsafe math flag, or the type is a vector/complex and the transformation is valid for the element type. Ok, maybe not the best example, but we have for instance -ftrapping-math for which a split was discussed (PR 53805#c4). -- Marc Glisse
Re: [RFC] Meta-description for tree and gimple folding
On Thu, 2014-02-27 at 15:34 +0100, Richard Biener wrote:
>
> I've been hacking on a prototype that generates matching and
> simplification code from a meta-description.
For what it is worth, MELT has a similar feature. http://gcc-melt.org/
regards
--
Basile STARYNKEVITCH http://starynkevitch.net/Basile/
email: basilestarynkevitchnet mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mine, sont seulement les miennes} ***
