| Message ID | 27f38089-c8cb-430c-8b3f-843df092d7db@zmail06.collab.prod.int.phx2.redhat.com |
|---|---|
| State | New |
| Headers | show |
On Thu, Oct 6, 2011 at 11:28 AM, Kai Tietz <ktietz@redhat.com> wrote: > Hello, > > Sorry attached non-updated change. Here with proper attached patch. > This patch improves in fold_truth_andor the generation of branch-conditions for targets having LOGICAL_OP_NON_SHORT_CIRCUIT set. If right-hand side operation of a TRUTH_(OR|AND)IF_EXPR is simple operand, has no side-effects, and doesn't trap, then try to convert expression to a TRUTH_(AND|OR)_EXPR, if left-hand operand is a simple operand, and has no side-effects. > > ChangeLog > > 2011-10-06 Kai Tietz <ktietz@redhat.com> > > * fold-const.c (fold_truth_andor): Convert TRUTH_(AND|OR)IF_EXPR > to TRUTH_OR_EXPR, if suitable. > > Bootstrapped and tested for all languages (including Ada and Obj-C++) on host x86_64-unknown-linux-gnu. Ok for apply? > > Regards, > Kai > > > ndex: fold-const.c > =================================================================== > --- fold-const.c (revision 179592) > +++ fold-const.c (working copy) > @@ -8387,6 +8387,33 @@ > if ((tem = fold_truthop (loc, code, type, arg0, arg1)) != 0) > return tem; > > + if ((code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR) > + && !TREE_SIDE_EFFECTS (arg1) > + && simple_operand_p (arg1) > + && LOGICAL_OP_NON_SHORT_CIRCUIT Why only for LOGICAL_OP_NON_SHORT_CIRCUIT? It doesn't make a difference for !LOGICAL_OP_NON_SHORT_CIRCUIT targets, but ... > + && !FLOAT_TYPE_P (TREE_TYPE (arg1)) ? I hope we don't have &&|| float. > + && ((TREE_CODE_CLASS (TREE_CODE (arg1)) != tcc_comparison > + && TREE_CODE (arg1) != TRUTH_NOT_EXPR) > + || !FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg1, 0))))) ? simple_operand_p would have rejected both ! and comparisons. I miss a test for side-effects on arg0 (and probably simple_operand_p there, as well). > + { > + if (TREE_CODE (arg0) == code > + && !TREE_SIDE_EFFECTS (TREE_OPERAND (arg0, 1)) > + && simple_operand_p (TREE_OPERAND (arg0, 1))) Err ... so why do you recurse here (and associate)? Even with different predicates than above ... And similar transforms seem to happen in fold_truthop - did you investigate why it didn't trigger there. And I'm missing a testcase. Richard. > + { > + tem = build2_loc (loc, > + (code == TRUTH_ANDIF_EXPR ? TRUTH_AND_EXPR > + : TRUTH_OR_EXPR), > + type, TREE_OPERAND (arg0, 1), arg1); > + return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0), tem); > + } > + if (!TREE_SIDE_EFFECTS (arg0) > + && simple_operand_p (arg0)) > + return build2_loc (loc, > + (code == TRUTH_ANDIF_EXPR ? TRUTH_AND_EXPR > + : TRUTH_OR_EXPR), > + type, arg0, arg1); > + } > + > return NULL_TREE; > } > >
2011/10/6 Richard Guenther <richard.guenther@gmail.com>: > On Thu, Oct 6, 2011 at 11:28 AM, Kai Tietz <ktietz@redhat.com> wrote: >> Hello, >> >> Sorry attached non-updated change. Here with proper attached patch. >> This patch improves in fold_truth_andor the generation of branch-conditions for targets having LOGICAL_OP_NON_SHORT_CIRCUIT set. If right-hand side operation of a TRUTH_(OR|AND)IF_EXPR is simple operand, has no side-effects, and doesn't trap, then try to convert expression to a TRUTH_(AND|OR)_EXPR, if left-hand operand is a simple operand, and has no side-effects. >> >> ChangeLog >> >> 2011-10-06 Kai Tietz <ktietz@redhat.com> >> >> * fold-const.c (fold_truth_andor): Convert TRUTH_(AND|OR)IF_EXPR >> to TRUTH_OR_EXPR, if suitable. >> >> Bootstrapped and tested for all languages (including Ada and Obj-C++) on host x86_64-unknown-linux-gnu. Ok for apply? >> >> Regards, >> Kai >> >> >> ndex: fold-const.c >> =================================================================== >> --- fold-const.c (revision 179592) >> +++ fold-const.c (working copy) >> @@ -8387,6 +8387,33 @@ >> if ((tem = fold_truthop (loc, code, type, arg0, arg1)) != 0) >> return tem; >> >> + if ((code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR) >> + && !TREE_SIDE_EFFECTS (arg1) >> + && simple_operand_p (arg1) >> + && LOGICAL_OP_NON_SHORT_CIRCUIT > > Why only for LOGICAL_OP_NON_SHORT_CIRCUIT? It doesn't make > a difference for !LOGICAL_OP_NON_SHORT_CIRCUIT targets, but ... Well, I used this check only for not doing this transformation for targets, which have low-cost branches. This is the same thing as in fold_truthop. It does this transformation only if LOGICAL_OP_NON_SHORT_CIRCUIT is true. >> + && !FLOAT_TYPE_P (TREE_TYPE (arg1)) > > ? I hope we don't have &&|| float. This can happen. Operands of TRUTH_AND|OR(IF)_EXPR aren't necessarily of integral type. After expansion in gimplifier, we have for sure comparisons, but not in c-tree. >> + && ((TREE_CODE_CLASS (TREE_CODE (arg1)) != tcc_comparison >> + && TREE_CODE (arg1) != TRUTH_NOT_EXPR) >> + || !FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg1, 0))))) > > ? simple_operand_p would have rejected both ! and comparisons. This check is the same as in fold_truthop. I used this check. The point here is that floats might trap. > I miss a test for side-effects on arg0 (and probably simple_operand_p there, > as well). See inner of if condition for those checks. I moved those checks for arg1 out of the inner conditions to avoid double-checking. >> + { >> + if (TREE_CODE (arg0) == code >> + && !TREE_SIDE_EFFECTS (TREE_OPERAND (arg0, 1)) >> + && simple_operand_p (TREE_OPERAND (arg0, 1))) > > Err ... so why do you recurse here (and associate)? Even with different > predicates than above ... See, here is the missing check. Point is that even if arg0 has side-effects and is a (AND|OR)IF expression, we might be able to associate with right-hand argument of arg0, if for it no side-effects are existing. Otherwise we wouldn't catch this case. We have here in maximum a recursion level of one. > And similar transforms seem to happen in fold_truthop - did you > investigate why it didn't trigger there. This is pretty simple. The point is that only for comparisons this transformation is done. But in c-tree we don't have here necessarily for TRUTH_(AND|OR)[IF]_EXPR comparison arguments, not necessarily integral ones (see above). > And I'm missing a testcase. Ok, I'll add one. Effect can be seen best after gimplification. > Richard. > >> + { >> + tem = build2_loc (loc, >> + (code == TRUTH_ANDIF_EXPR ? TRUTH_AND_EXPR >> + : TRUTH_OR_EXPR), >> + type, TREE_OPERAND (arg0, 1), arg1); >> + return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0), tem); >> + } >> + if (!TREE_SIDE_EFFECTS (arg0) >> + && simple_operand_p (arg0)) >> + return build2_loc (loc, >> + (code == TRUTH_ANDIF_EXPR ? TRUTH_AND_EXPR >> + : TRUTH_OR_EXPR), >> + type, arg0, arg1); >> + } >> + >> return NULL_TREE; >> } Regards. Kai
Hi, On Thu, 6 Oct 2011, Richard Guenther wrote: > > + && ((TREE_CODE_CLASS (TREE_CODE (arg1)) != tcc_comparison > > + && TREE_CODE (arg1) != TRUTH_NOT_EXPR) > > + || !FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg1, 0))))) > > ? simple_operand_p would have rejected both ! and comparisons. > > I miss a test for side-effects on arg0 (and probably simple_operand_p there, > as well). He has it in the if() body. But why? The point of ANDIF/ORIF is to not evaluate the second argument for side-effects when the first argument is false/true already, and further to establish an order between both evaluations. The sideeffect on the first arg is always evaluated. AND/OR always evaluate both arguments (in unspecified order), but as he checks the second one for being free of side effects already that alone is already equivalent to ANDIF/ORIF. No need to check something on the first argument. Ciao, Michael.
On Thu, Oct 6, 2011 at 3:49 PM, Michael Matz <matz@suse.de> wrote: > Hi, > > On Thu, 6 Oct 2011, Richard Guenther wrote: > >> > + && ((TREE_CODE_CLASS (TREE_CODE (arg1)) != tcc_comparison >> > + && TREE_CODE (arg1) != TRUTH_NOT_EXPR) >> > + || !FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg1, 0))))) >> >> ? simple_operand_p would have rejected both ! and comparisons. >> >> I miss a test for side-effects on arg0 (and probably simple_operand_p there, >> as well). > > He has it in the if() body. But why? The point of ANDIF/ORIF is to not > evaluate the second argument for side-effects when the first argument is > false/true already, and further to establish an order between both > evaluations. The sideeffect on the first arg is always evaluated. > AND/OR always evaluate both arguments (in unspecified order), but as he > checks the second one for being free of side effects already that alone is > already equivalent to ANDIF/ORIF. No need to check something on the first > argument. It seems to me it should then simply be if (!TREE_SIDE_EFFECTS (arg1) && simple_operand_p (arg1)) return fold-the-not-and-variant (); Richard.
2011/10/6 Michael Matz <matz@suse.de>: > Hi, > > On Thu, 6 Oct 2011, Richard Guenther wrote: > >> > + && ((TREE_CODE_CLASS (TREE_CODE (arg1)) != tcc_comparison >> > + && TREE_CODE (arg1) != TRUTH_NOT_EXPR) >> > + || !FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg1, 0))))) >> >> ? simple_operand_p would have rejected both ! and comparisons. >> >> I miss a test for side-effects on arg0 (and probably simple_operand_p there, >> as well). > > He has it in the if() body. But why? The point of ANDIF/ORIF is to not > evaluate the second argument for side-effects when the first argument is > false/true already, and further to establish an order between both > evaluations. The sideeffect on the first arg is always evaluated. > AND/OR always evaluate both arguments (in unspecified order), but as he > checks the second one for being free of side effects already that alone is > already equivalent to ANDIF/ORIF. No need to check something on the first > argument. > > > Ciao, > Michael. That's not the hole story. The difference between TRUTH_(AND|OR)IF_EXPR and TRUTH_(AND|OR)_EXPR are, that for TRUTH_(AND|OR)IF_EXPR gimplifier creates a COND expression, but for TRUTH_(AND|OR)_EXPR it doesn't. Regards, Kai
Hi, On Thu, 6 Oct 2011, Kai Tietz wrote: > That's not the hole story. The difference between TRUTH_(AND|OR)IF_EXPR > and TRUTH_(AND|OR)_EXPR are, that for TRUTH_(AND|OR)IF_EXPR gimplifier > creates a COND expression, but for TRUTH_(AND|OR)_EXPR it doesn't. Yes, of course. That is what implements the short-circuit semantics. But as Richard already mentioned I also don't understand why you do the reassociation at that point. Why not simply rewrite ANDIF -> AND (when possible, i.e. no sideeffects on arg1, and desirable, i.e. when LOGICAL_OP_NON_SHORT_CIRCUIT, and simple_operand(arg1)) and let other folders do reassociation? I ask because your comments states to transform: ((W AND X) ANDIF Y) ANDIF Z into (W AND X) ANDIF (Y AND Z) (under condition that Y and Z are simple operands). In fact you don't check the form of arg0,0, i.e. the "W AND X" here. Independend of that it doesn't make sense, because if Y and Z are easy (simple and no side-effects), then "Y AND Z" is too, and therefore you should transform this (if at all) into: (W AND X) AND (Y AND Z) at which point this association doesn't make sense anymore, as ((W AND X) AND Y) AND Z is just as fine. So, the reassociation looks fishy at best, better get rid of it? (which of the testcases breaks without it?) Ciao, Michael.
2011/10/6 Michael Matz <matz@suse.de>: > Hi, > > On Thu, 6 Oct 2011, Kai Tietz wrote: > >> That's not the hole story. The difference between TRUTH_(AND|OR)IF_EXPR >> and TRUTH_(AND|OR)_EXPR are, that for TRUTH_(AND|OR)IF_EXPR gimplifier >> creates a COND expression, but for TRUTH_(AND|OR)_EXPR it doesn't. > > Yes, of course. That is what implements the short-circuit semantics. But > as Richard already mentioned I also don't understand why you do the > reassociation at that point. Why not simply rewrite ANDIF -> AND (when > possible, i.e. no sideeffects on arg1, and desirable, i.e. when > LOGICAL_OP_NON_SHORT_CIRCUIT, and simple_operand(arg1)) and let other > folders do reassociation? I ask because your comments states to > transform: > > ((W AND X) ANDIF Y) ANDIF Z > into > (W AND X) ANDIF (Y AND Z) > > (under condition that Y and Z are simple operands). > > In fact you don't check the form of arg0,0, i.e. the "W AND X" here. > Independend of that it doesn't make sense, because if Y and Z are easy > (simple and no side-effects), then "Y AND Z" is too, and therefore you > should transform this (if at all) into: > > (W AND X) AND (Y AND Z) > > at which point this association doesn't make sense anymore, as Sorry, exactly this doesn't happen, due an ANDIF isn't simple, and therefore it isn't transformed into and AND. > ((W AND X) AND Y) AND Z > > is just as fine. So, the reassociation looks fishy at best, better get > rid of it? (which of the testcases breaks without it?) None. I had this implemented first. But Richard was concerned about making non-IF conditions too long. I understand that point that it might not that good to always modify unconditionally to AND/OR chain. For example if (a1 && a2 && a3 && .... && a100) return 1; would be packed by this patch into 50 branches. If we would modify all of them into AND, then we would calculate for all 100 values the result, even if the first a1 is zero. This doesn't improve speed pretty well. But you are right, that from the point of reassociation optimization it could be in some cases more profitable to have packed all elements into on AND-chain. Regards, Kai
On Thu, Oct 06, 2011 at 05:28:36PM +0200, Kai Tietz wrote: > None. I had this implemented first. But Richard was concerned about > making non-IF conditions too long. I understand that point that it > might not that good to always modify unconditionally to AND/OR chain. > For example > > if (a1 && a2 && a3 && .... && a100) return 1; > > would be packed by this patch into 50 branches. If we would modify > all of them into AND, then we would calculate for all 100 values the > result, even if the first a1 is zero. This doesn't improve speed > pretty well. > > But you are right, that from the point of reassociation optimization > it could be in some cases more profitable to have packed all elements > into on AND-chain. Yeah. Perhaps we should break them up after reassoc2, or on the other side teach reassoc (or some other pass) to be able to do the optimizations on a series of GIMPLE_COND with no side-effects in between. See e.g. PR46309, return a == 3 || a == 1 || a == 2 || a == 4; isn't optimized into (a - 1U) < 4U, although it could, if branch cost cause it to be broken up into several GIMPLE_COND stmts. Or if user writes: if (a == 3) return 1; if (a == 1) return 1; if (a == 2) return 1; if (a == 4) return 1; return 0; (more probably using enums). Jakub
Hi, On Thu, 6 Oct 2011, Kai Tietz wrote: > > at which point this association doesn't make sense anymore, as > > Sorry, exactly this doesn't happen, due an ANDIF isn't simple, and > therefore it isn't transformed into and AND. Right ... > > ((W AND X) AND Y) AND Z > > > > is just as fine. So, the reassociation looks fishy at best, better get > > rid of it? (which of the testcases breaks without it?) > > None. I had this implemented first. But Richard was concerned about > making non-IF conditions too long. I understand that point that it > might not that good to always modify unconditionally to AND/OR chain. ... and I see that (that's why the transformation should be desirable for some definition of desirable, which probably includes "and RHS not too long chain"). As it stands right now your transformation seems to be a fairly ad-hoc try at avoiding this problem. That's why I wonder why to do the reassoc at all? Which testcases break _without_ the reassociation, i.e. with only rewriting ANDIF -> AND at the outermost level? Ciao, Michael.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 10/06/11 09:37, Jakub Jelinek wrote: > On Thu, Oct 06, 2011 at 05:28:36PM +0200, Kai Tietz wrote: >> None. I had this implemented first. But Richard was concerned >> about making non-IF conditions too long. I understand that >> point that it might not that good to always modify >> unconditionally to AND/OR chain. For example >> >> if (a1 && a2 && a3 && .... && a100) return 1; >> >> would be packed by this patch into 50 branches. If we would >> modify all of them into AND, then we would calculate for all 100 >> values the result, even if the first a1 is zero. This doesn't >> improve speed pretty well. >> >> But you are right, that from the point of reassociation >> optimization it could be in some cases more profitable to have >> packed all elements into on AND-chain. > > Yeah. Perhaps we should break them up after reassoc2, or on the > other side teach reassoc (or some other pass) to be able to do the > optimizations on a series of GIMPLE_COND with no side-effects in > between. See e.g. PR46309, return a == 3 || a == 1 || a == 2 || a > == 4; isn't optimized into (a - 1U) < 4U, although it could, if > branch cost cause it to be broken up into several GIMPLE_COND > stmts. Or if user writes: if (a == 3) return 1; if (a == 1) return > 1; if (a == 2) return 1; if (a == 4) return 1; return 0; (more > probably using enums). I haven't followed this thread as closely as perhaps I should; what I'm seeing discussed now looks a lot like condition merging and I'm pretty sure there's some research in this area that might guide us. multi-variable condition merging is the term the authors used. jeff -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iQEcBAEBAgAGBQJOjeYFAAoJEBRtltQi2kC7eFMIALjFM/GIg1DDryU59EoFQe5A x7pvx3FSlcjLWeyIlzYJvWF4wGybRNNXp5qziIedO6qp0Z/06VvCU07A10VoWSig /EFufo5l+Jef5s1d0mA6mBJ9A52HDL2ipOK8YDQbVzJWqHdaXLrrzUni3wGwcUVs v3UIi5OevjRhJ55fRVxBcReJKF6YAzxFDxqOnVGAbf9R3BEJ2T9JW2CLhIcd/T1L D9K+6YymHaN9eYh7B7gPKG88q+5JjcStHuMQODKSAegt3T4iP9CH/G5dV8u95Y+q 6mxo8gOGAwYR7N/U6fuXRaGJEzWSdrqRy2EBF5B7+Rt6lSWXdfzUEBusT24i67A= =HIrU -----END PGP SIGNATURE-----
2011/10/6 Michael Matz <matz@suse.de>: > Hi, > > On Thu, 6 Oct 2011, Kai Tietz wrote: > >> > at which point this association doesn't make sense anymore, as >> >> Sorry, exactly this doesn't happen, due an ANDIF isn't simple, and >> therefore it isn't transformed into and AND. > > Right ... > >> > ((W AND X) AND Y) AND Z >> > >> > is just as fine. So, the reassociation looks fishy at best, better get >> > rid of it? (which of the testcases breaks without it?) >> >> None. I had this implemented first. But Richard was concerned about >> making non-IF conditions too long. I understand that point that it >> might not that good to always modify unconditionally to AND/OR chain. > > ... and I see that (that's why the transformation should be desirable for > some definition of desirable, which probably includes "and RHS not too > long chain"). As it stands right now your transformation seems to be a > fairly ad-hoc try at avoiding this problem. That's why I wonder why to do > the reassoc at all? Which testcases break _without_ the reassociation, > i.e. with only rewriting ANDIF -> AND at the outermost level? I don't do here reassociation in inner. See that patch calls build2_loc, and not fold_build2_loc anymore. So it doesn't retries to associate in inner anymore (which might be something of interest for the issue Jakub mentioned). There is no test actual failing AFAICS. I just noticed size-differences by this. Nevertheless it might be better to enhance reassociation pass to break-up (and repropagate) GIMPLE_CONDs with non-side-effect, as Jakub suggested. The other chance might be here to allow deeper chains then two elements within one AND/OR element, but this would be architecture dependent. For x86 -as example- used instruction cycles for a common for branching would suggest that it might be profitable to have here 3 or 4 leafs within one AND|OR chain. But for sure on other architectures the amount of leafs varies. Regards, Kai
=================================================================== --- fold-const.c (revision 179592) +++ fold-const.c (working copy) @@ -8387,6 +8387,33 @@ if ((tem = fold_truthop (loc, code, type, arg0, arg1)) != 0) return tem; + if ((code == TRUTH_ANDIF_EXPR || code == TRUTH_ORIF_EXPR) + && !TREE_SIDE_EFFECTS (arg1) + && simple_operand_p (arg1) + && LOGICAL_OP_NON_SHORT_CIRCUIT + && !FLOAT_TYPE_P (TREE_TYPE (arg1)) + && ((TREE_CODE_CLASS (TREE_CODE (arg1)) != tcc_comparison + && TREE_CODE (arg1) != TRUTH_NOT_EXPR) + || !FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (arg1, 0))))) + { + if (TREE_CODE (arg0) == code + && !TREE_SIDE_EFFECTS (TREE_OPERAND (arg0, 1)) + && simple_operand_p (TREE_OPERAND (arg0, 1))) + { + tem = build2_loc (loc, + (code == TRUTH_ANDIF_EXPR ? TRUTH_AND_EXPR + : TRUTH_OR_EXPR), + type, TREE_OPERAND (arg0, 1), arg1); + return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0), tem); + } + if (!TREE_SIDE_EFFECTS (arg0) + && simple_operand_p (arg0)) + return build2_loc (loc, + (code == TRUTH_ANDIF_EXPR ? TRUTH_AND_EXPR + : TRUTH_OR_EXPR), + type, arg0, arg1); + } + return NULL_TREE; }
Hello, Sorry attached non-updated change. Here with proper attached patch. This patch improves in fold_truth_andor the generation of branch-conditions for targets having LOGICAL_OP_NON_SHORT_CIRCUIT set. If right-hand side operation of a TRUTH_(OR|AND)IF_EXPR is simple operand, has no side-effects, and doesn't trap, then try to convert expression to a TRUTH_(AND|OR)_EXPR, if left-hand operand is a simple operand, and has no side-effects. ChangeLog 2011-10-06 Kai Tietz <ktietz@redhat.com> * fold-const.c (fold_truth_andor): Convert TRUTH_(AND|OR)IF_EXPR to TRUTH_OR_EXPR, if suitable. Bootstrapped and tested for all languages (including Ada and Obj-C++) on host x86_64-unknown-linux-gnu. Ok for apply? Regards, Kai ndex: fold-const.c