On Thu, Mar 7, 2024 at 10:49 PM Richard Biener <richard.guent...@gmail.com> wrote: > > On Thu, Mar 7, 2024 at 8:29 PM Ken Matsui <kmat...@cs.washington.edu> wrote: > > > > On Tue, Mar 5, 2024 at 7:58 AM Richard Biener > > <richard.guent...@gmail.com> wrote: > > > > > > On Tue, Mar 5, 2024 at 1:51 PM Ken Matsui <kmat...@cs.washington.edu> > > > wrote: > > > > > > > > On Tue, Mar 5, 2024 at 12:38 AM Richard Biener > > > > <richard.guent...@gmail.com> wrote: > > > > > > > > > > On Mon, Mar 4, 2024 at 9:40 PM Ken Matsui <kmat...@gcc.gnu.org> wrote: > > > > > > > > > > > > (x - y) CMP 0 is equivalent to x CMP y where x and y are signed > > > > > > integers and CMP is <, <=, >, or >=. Similarly, 0 CMP (x - y) is > > > > > > equivalent to y CMP x. As reported in PR middle-end/113680, this > > > > > > equivalence does not hold for types other than signed integers. > > > > > > When > > > > > > it comes to conditions, the former was translated to a combination > > > > > > of > > > > > > sub and test, whereas the latter was translated to a single cmp. > > > > > > Thus, this optimization pass tries to optimize the former to the > > > > > > latter. > > > > > > > > > > > > When `-fwrapv` is enabled, GCC treats the overflow of signed > > > > > > integers > > > > > > as defined behavior, specifically, wrapping around according to > > > > > > two's > > > > > > complement arithmetic. This has implications for optimizations that > > > > > > rely on the standard behavior of signed integers, where overflow is > > > > > > undefined. Consider the example given: > > > > > > > > > > > > long long llmax = __LONG_LONG_MAX__; > > > > > > long long llmin = -llmax - 1; > > > > > > > > > > > > Here, `llmax - llmin` effectively becomes `llmax - (-llmax - 1)`, > > > > > > which > > > > > > simplifies to `2 * llmax + 1`. Given that `llmax` is the maximum > > > > > > value > > > > > > for a `long long`, this calculation overflows in a defined manner > > > > > > (wrapping around), which under `-fwrapv` is a legal operation that > > > > > > produces a negative value due to two's complement wraparound. > > > > > > Therefore, `llmax - llmin < 0` is true. > > > > > > > > > > > > However, the direct comparison `llmax < llmin` is false since > > > > > > `llmax` > > > > > > is the maximum possible value and `llmin` is the minimum. Hence, > > > > > > optimizations that rely on the equivalence of `(x - y) CMP 0` to > > > > > > `x CMP y` (and vice versa) cannot be safely applied when `-fwrapv` > > > > > > is > > > > > > enabled. This is why this optimization pass is disabled under > > > > > > `-fwrapv`. > > > > > > > > > > > > This optimization pass must run before the Jump Threading pass and > > > > > > the > > > > > > VRP pass, as it may modify conditions. For example, in the VRP pass: > > > > > > > > > > > > (1) > > > > > > int diff = x - y; > > > > > > if (diff > 0) > > > > > > foo(); > > > > > > if (diff < 0) > > > > > > bar(); > > > > > > > > > > > > The second condition would be converted to diff != 0 in the VRP pass > > > > > > because we know the postcondition of the first condition is diff <= > > > > > > 0, > > > > > > and then diff != 0 is cheaper than diff < 0. If we apply this pass > > > > > > after this VRP, we get: > > > > > > > > > > > > (2) > > > > > > int diff = x - y; > > > > > > if (x > y) > > > > > > foo(); > > > > > > if (diff != 0) > > > > > > bar(); > > > > > > > > > > > > This generates sub and test for the second condition and cmp for the > > > > > > first condition. However, if we apply this pass beforehand, we > > > > > > simply > > > > > > get: > > > > > > > > > > > > (3) > > > > > > int diff = x - y; > > > > > > if (x > y) > > > > > > foo(); > > > > > > if (x < y) > > > > > > bar(); > > > > > > > > > > > > In this code, diff will be eliminated as a dead code, and sub and > > > > > > test > > > > > > will not be generated, which is more efficient. > > > > > > > > > > > > For the Jump Threading pass, without this optimization pass, (1) and > > > > > > (3) above are recognized as different, which prevents TCO. > > > > > > > > > > > > PR middle-end/113680 > > > > > > > > > > This shouldn't be done as a new optimization pass. It fits either > > > > > the explicit code present in the forwprop pass or a new match.pd > > > > > pattern. There's possible interaction with x - y value being used > > > > > elsewhere and thus exposing a CSE opportunity as well as > > > > > a comparison against zero being possibly implemented by > > > > > a flag setting subtraction instruction. > > > > > > > > > > > > > Thank you so much for your review! Although the forwprop pass runs > > > > multiple times, we might not need to apply this optimization multiple > > > > times. Would it be acceptable to add such optimization? More > > > > generally, I would like to know how to determine where to put > > > > optimization in the future. > > > > > > This kind of pattern matching expression simplification is best > > > addressed by patterns in match.pd though historically the forwprop > > > pass still catches cases not in match.pd in its > > > forward_propagate_into_comparison_1 (and callers). > > > > > > > I see. When would patterns in match.pd be applied? Around forwprop > > or somewhere else? (Also, could you please tell me a document I can > > learn about these if it exists?) I ask because this optimization > > should be applied before the Jump Threading and VRP passes. > > match.pd patterns get used whenever an expression is simplified. And > yes, the forwprop pass tries to simplify expressions rooted at each stmt. > In general each pass changing a statement or one of its operands should > re-simplify the expression rooted at it, so the theory is that all expressions > always remain simplified. > > There's no documentation about the patterns present in match.pd if > you meant that.
What I meant was the high-level structure around match.pd and other passes, but it is answered! That makes sense. Thank you for your time! > I'm usually writing small testcases to "query" match.pd > and use -fdump-tree-all-folding looking into .original (when folded at > generic time), .gimple, .ccp and .forwprop which are the usual early > places where simplifications are triggered. This is really helpful, thank you! > > Richard. > > > > > FYI, I read this page: https://gcc.gnu.org/wiki/OptimizationCourse > > > > > > > > > Our VN pass has some tricks to anticipate CSE opportunities > > > > > like this, but it's not done "properly" in the way of anticipating > > > > > both forms during PRE. > > > > > > > > > > I'll note we have > > > > > > > > > > /* (A - B) != 0 ? (A - B) : (B - A) same as (A - B) */ > > > > > (for cmp (ne ltgt) > > > > > > > > > > and similar which might be confused by canonicalizing to A != B. > > > > > > > > I will investigate and update my patch (after my final exam ends...)! > > > > > > > > > I'm also surprised we don't already have the pattern you add. > > > > > > > > Hmm, so am I. > > > > > > It looks like we do it for equality compares which can also handle > > > types where overflow is undefined. -fdump-tree-all-folding shows > > > in the 005t.original dump we simplify a - b != 0 via match.pd:6105: > > > > > > /* Transform comparisons of the form X - Y CMP 0 to X CMP Y. > > > ??? The transformation is valid for the other operators if overflow > > > is undefined for the type, but performing it here badly interacts > > > with the transformation in fold_cond_expr_with_comparison which > > > attempts to synthetize ABS_EXPR. */ > > > (for cmp (eq ne) > > > (for sub (minus pointer_diff) > > > (simplify > > > (cmp (sub@2 @0 @1) integer_zerop) > > > (if (single_use (@2)) > > > (cmp @0 @1))))) > > > > > > and the comment explains why we don't perform the transform > > > it the way you intend. That comment might no longer apply > > > but I would guess there's testsuite fallout when you amend this > > > pattern. > > > > Thank you so much! I will check this out. > > > > > > > > Richard. > > > > > > > I saw that this optimization sometimes messes up VRP > > > > while sometimes helping it (as I described in my comment). I also > > > > need to research this. > > > > > > > > > > > > > > Richard. > > > > > > > > > > > gcc/ChangeLog: > > > > > > > > > > > > * Makefile.in: Add tree-ssa-cmp.o to OBJS. > > > > > > * common.opt: Define ftree-cmp > > > > > > * doc/invoke.texi: Document ftree-cmp. > > > > > > * opts.cc (default_options_table): Handle OPT_ftree_cmp. > > > > > > * passes.def (pass_cmp): New optimization pass. > > > > > > * timevar.def (TV_TREE_CMP): New variable for timing. > > > > > > * tree-pass.h (make_pass_cmp): New declaration. > > > > > > * tree-ssa-cmp.cc: New file. > > > > > > > > > > > > gcc/testsuite/ChangeLog: > > > > > > > > > > > > * gcc.dg/pr113680.c: New test. > > > > > > > > > > > > Signed-off-by: Ken Matsui <kmat...@gcc.gnu.org> > > > > > > --- > > > > > > gcc/Makefile.in | 1 + > > > > > > gcc/common.opt | 4 + > > > > > > gcc/doc/invoke.texi | 11 +- > > > > > > gcc/opts.cc | 1 + > > > > > > gcc/passes.def | 3 + > > > > > > gcc/testsuite/gcc.dg/pr113680.c | 47 ++++++ > > > > > > gcc/timevar.def | 1 + > > > > > > gcc/tree-pass.h | 1 + > > > > > > gcc/tree-ssa-cmp.cc | 262 > > > > > > ++++++++++++++++++++++++++++++++ > > > > > > 9 files changed, 330 insertions(+), 1 deletion(-) > > > > > > create mode 100644 gcc/testsuite/gcc.dg/pr113680.c > > > > > > create mode 100644 gcc/tree-ssa-cmp.cc > > > > > > > > > > > > diff --git a/gcc/Makefile.in b/gcc/Makefile.in > > > > > > index a74761b7ab3..935b80b6947 100644 > > > > > > --- a/gcc/Makefile.in > > > > > > +++ b/gcc/Makefile.in > > > > > > @@ -1731,6 +1731,7 @@ OBJS = \ > > > > > > tree-ssa-address.o \ > > > > > > tree-ssa-alias.o \ > > > > > > tree-ssa-ccp.o \ > > > > > > + tree-ssa-cmp.o \ > > > > > > tree-ssa-coalesce.o \ > > > > > > tree-ssa-copy.o \ > > > > > > tree-ssa-dce.o \ > > > > > > diff --git a/gcc/common.opt b/gcc/common.opt > > > > > > index 51c4a17da83..7c853224458 100644 > > > > > > --- a/gcc/common.opt > > > > > > +++ b/gcc/common.opt > > > > > > @@ -3053,6 +3053,10 @@ ftree-ch > > > > > > Common Var(flag_tree_ch) Optimization > > > > > > Enable loop header copying on trees. > > > > > > > > > > > > +ftree-cmp > > > > > > +Common Var(flag_tree_cmp) Optimization > > > > > > +Enable SSA comparison optimization on trees. > > > > > > + > > > > > > ftree-coalesce-inlined-vars > > > > > > Common Ignore RejectNegative > > > > > > Does nothing. Preserved for backward compatibility. > > > > > > diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi > > > > > > index bdf05be387d..04762d490a3 100644 > > > > > > --- a/gcc/doc/invoke.texi > > > > > > +++ b/gcc/doc/invoke.texi > > > > > > @@ -619,7 +619,7 @@ Objective-C and Objective-C++ Dialects}. > > > > > > -fsplit-wide-types -fsplit-wide-types-early -fssa-backprop > > > > > > -fssa-phiopt > > > > > > -fstdarg-opt -fstore-merging -fstrict-aliasing > > > > > > -fipa-strict-aliasing > > > > > > -fthread-jumps -ftracer -ftree-bit-ccp > > > > > > --ftree-builtin-call-dce -ftree-ccp -ftree-ch > > > > > > +-ftree-builtin-call-dce -ftree-ccp -ftree-ch -ftree-cmp > > > > > > -ftree-coalesce-vars -ftree-copy-prop -ftree-dce > > > > > > -ftree-dominator-opts > > > > > > -ftree-dse -ftree-forwprop -ftree-fre -fcode-hoisting > > > > > > -ftree-loop-if-convert -ftree-loop-im > > > > > > @@ -12377,6 +12377,7 @@ compilation time. > > > > > > -ftree-bit-ccp > > > > > > -ftree-ccp > > > > > > -ftree-ch > > > > > > +-ftree-cmp > > > > > > -ftree-coalesce-vars > > > > > > -ftree-copy-prop > > > > > > -ftree-dce > > > > > > @@ -13707,6 +13708,14 @@ effectiveness of code motion > > > > > > optimizations. It also saves one jump. This flag > > > > > > is enabled by default at @option{-O1} and higher. It is not > > > > > > enabled > > > > > > for @option{-Os}, since it usually increases code size. > > > > > > > > > > > > +@opindex ftree-cmp > > > > > > +@item -ftree-cmp > > > > > > +Perform comparison optimization on trees. This decreases > > > > > > unnecessary > > > > > > +instructions for comparisons. This flag is enabled by default at > > > > > > +@option{-O1} and higher. This optimization is automatically > > > > > > disabled when > > > > > > +@option{-fwrapv} is specified to ensure correct behavior under > > > > > > signed integer > > > > > > +overflow wrapping. > > > > > > + > > > > > > @opindex ftree-loop-optimize > > > > > > @item -ftree-loop-optimize > > > > > > Perform loop optimizations on trees. This flag is enabled by > > > > > > default > > > > > > diff --git a/gcc/opts.cc b/gcc/opts.cc > > > > > > index 3333600e0ea..9ee64a48313 100644 > > > > > > --- a/gcc/opts.cc > > > > > > +++ b/gcc/opts.cc > > > > > > @@ -589,6 +589,7 @@ static const struct default_options > > > > > > default_options_table[] = > > > > > > { OPT_LEVELS_1_PLUS, OPT_ftree_builtin_call_dce, NULL, 1 }, > > > > > > { OPT_LEVELS_1_PLUS, OPT_ftree_ccp, NULL, 1 }, > > > > > > { OPT_LEVELS_1_PLUS, OPT_ftree_ch, NULL, 1 }, > > > > > > + { OPT_LEVELS_1_PLUS, OPT_ftree_cmp, NULL, 1 }, > > > > > > { OPT_LEVELS_1_PLUS, OPT_ftree_coalesce_vars, NULL, 1 }, > > > > > > { OPT_LEVELS_1_PLUS, OPT_ftree_copy_prop, NULL, 1 }, > > > > > > { OPT_LEVELS_1_PLUS, OPT_ftree_dce, NULL, 1 }, > > > > > > diff --git a/gcc/passes.def b/gcc/passes.def > > > > > > index 1cbbd413097..e28a2d3c309 100644 > > > > > > --- a/gcc/passes.def > > > > > > +++ b/gcc/passes.def > > > > > > @@ -84,6 +84,9 @@ along with GCC; see the file COPYING3. If not see > > > > > > /* After CCP we rewrite no longer addressed locals into > > > > > > SSA > > > > > > form if possible. */ > > > > > > NEXT_PASS (pass_forwprop); > > > > > > + /* Do cmp before early_thread_jumps and vrp since it may > > > > > > + modify conditions. */ > > > > > > + NEXT_PASS (pass_cmp); > > > > > > NEXT_PASS (pass_early_thread_jumps, /*first=*/true); > > > > > > NEXT_PASS (pass_sra_early); > > > > > > /* pass_build_ealias is a dummy pass that ensures that we > > > > > > diff --git a/gcc/testsuite/gcc.dg/pr113680.c > > > > > > b/gcc/testsuite/gcc.dg/pr113680.c > > > > > > new file mode 100644 > > > > > > index 00000000000..59cd865aa21 > > > > > > --- /dev/null > > > > > > +++ b/gcc/testsuite/gcc.dg/pr113680.c > > > > > > @@ -0,0 +1,47 @@ > > > > > > +/* { dg-do compile } */ > > > > > > +/* { dg-options "-Os -fdump-tree-optimized" } */ > > > > > > + > > > > > > +volatile int i = 0; > > > > > > + > > > > > > +void foo() { i = 1; } > > > > > > +void bar() { i = 2; } > > > > > > + > > > > > > +void f1(int x, int y) > > > > > > +{ > > > > > > + int diff = x - y; > > > > > > + if (diff > 0) > > > > > > + foo(); > > > > > > + if (diff < 0) > > > > > > + bar(); > > > > > > +} > > > > > > + > > > > > > +void f2(int x, int y) > > > > > > +{ > > > > > > + if ((x - y) > 0) > > > > > > + foo(); > > > > > > + if ((x - y) < 0) > > > > > > + bar(); > > > > > > +} > > > > > > + > > > > > > +void f3(int x, int y) > > > > > > +{ > > > > > > + if (x > y) > > > > > > + foo(); > > > > > > + if (x < y) > > > > > > + bar(); > > > > > > +} > > > > > > + > > > > > > +void f4(int x, int y) > > > > > > +{ > > > > > > + int diff = x - y; > > > > > > + if (diff > 0) > > > > > > + foo(); > > > > > > + if (x < y) > > > > > > + bar(); > > > > > > +} > > > > > > + > > > > > > +/* { dg-final { scan-tree-dump-not " - " "optimized" } } */ > > > > > > +/* { dg-final { scan-assembler-times "cmp" 1 { target { i?86-*-* > > > > > > x86_64-*-* } } } } */ > > > > > > +/* { dg-final { scan-assembler-times "jmp\[ \t\]+f1" 3 { target { > > > > > > i?86-*-* x86_64-*-* } } } } */ > > > > > > +/* { dg-final { scan-assembler-not "sub" { target { i?86-*-* > > > > > > x86_64-*-* } } } } */ > > > > > > +/* { dg-final { scan-assembler-not "test" { target { i?86-*-* > > > > > > x86_64-*-* } } } } */ > > > > > > diff --git a/gcc/timevar.def b/gcc/timevar.def > > > > > > index 8e2168e0817..468266d0c56 100644 > > > > > > --- a/gcc/timevar.def > > > > > > +++ b/gcc/timevar.def > > > > > > @@ -157,6 +157,7 @@ DEFTIMEVAR (TV_TREE_EH , > > > > > > "tree eh") > > > > > > DEFTIMEVAR (TV_TREE_CFG , "tree CFG > > > > > > construction") > > > > > > DEFTIMEVAR (TV_TREE_CLEANUP_CFG , "tree CFG cleanup") > > > > > > DEFTIMEVAR (TV_TREE_TAIL_MERGE , "tree tail merge") > > > > > > +DEFTIMEVAR (TV_TREE_CMP , "tree cmp") > > > > > > DEFTIMEVAR (TV_TREE_VRP , "tree VRP") > > > > > > DEFTIMEVAR (TV_TREE_VRP_THREADER , "tree VRP threader") > > > > > > DEFTIMEVAR (TV_TREE_EARLY_VRP , "tree Early VRP") > > > > > > diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h > > > > > > index 29267589eeb..71789a279c0 100644 > > > > > > --- a/gcc/tree-pass.h > > > > > > +++ b/gcc/tree-pass.h > > > > > > @@ -401,6 +401,7 @@ extern gimple_opt_pass *make_pass_ch > > > > > > (gcc::context *ctxt); > > > > > > extern gimple_opt_pass *make_pass_ch_vect (gcc::context *ctxt); > > > > > > extern gimple_opt_pass *make_pass_sccopy (gcc::context *ctxt); > > > > > > extern gimple_opt_pass *make_pass_ccp (gcc::context *ctxt); > > > > > > +extern gimple_opt_pass *make_pass_cmp (gcc::context *ctxt); > > > > > > extern gimple_opt_pass *make_pass_split_paths (gcc::context *ctxt); > > > > > > extern gimple_opt_pass *make_pass_build_ssa (gcc::context *ctxt); > > > > > > extern gimple_opt_pass *make_pass_build_alias (gcc::context *ctxt); > > > > > > diff --git a/gcc/tree-ssa-cmp.cc b/gcc/tree-ssa-cmp.cc > > > > > > new file mode 100644 > > > > > > index 00000000000..41d4a58a5b5 > > > > > > --- /dev/null > > > > > > +++ b/gcc/tree-ssa-cmp.cc > > > > > > @@ -0,0 +1,262 @@ > > > > > > +/* Global, SSA-based optimizations using comparison identities. > > > > > > + Copyright (C) 2024 Free Software Foundation, Inc. > > > > > > + > > > > > > +This file is part of GCC. > > > > > > + > > > > > > +GCC is free software; you can redistribute it and/or modify it > > > > > > +under the terms of the GNU General Public License as published by > > > > > > the > > > > > > +Free Software Foundation; either version 3, or (at your option) any > > > > > > +later version. > > > > > > + > > > > > > +GCC is distributed in the hope that it will be useful, but WITHOUT > > > > > > +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY > > > > > > or > > > > > > +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public > > > > > > License > > > > > > +for more details. > > > > > > + > > > > > > +You should have received a copy of the GNU General Public License > > > > > > +along with GCC; see the file COPYING3. If not see > > > > > > +<http://www.gnu.org/licenses/>. */ > > > > > > + > > > > > > +/* (x - y) CMP 0 is equivalent to x CMP y where x and y are signed > > > > > > integers and > > > > > > + CMP is <, <=, >, or >=. Similarly, 0 CMP (x - y) is equivalent > > > > > > to y CMP x. > > > > > > + As reported in PR middle-end/113680, this equivalence does not > > > > > > hold for > > > > > > + types other than signed integers. When it comes to conditions, > > > > > > the former > > > > > > + was translated to a combination of sub and test, whereas the > > > > > > latter was > > > > > > + translated to a single cmp. Thus, this optimization pass tries > > > > > > to optimize > > > > > > + the former to the latter. > > > > > > + > > > > > > + When `-fwrapv` is enabled, GCC treats the overflow of signed > > > > > > integers as > > > > > > + defined behavior, specifically, wrapping around according to > > > > > > two's > > > > > > + complement arithmetic. This has implications for optimizations > > > > > > that > > > > > > + rely on the standard behavior of signed integers, where > > > > > > overflow is > > > > > > + undefined. Consider the example given: > > > > > > + > > > > > > + long long llmax = __LONG_LONG_MAX__; > > > > > > + long long llmin = -llmax - 1; > > > > > > + > > > > > > + Here, `llmax - llmin` effectively becomes `llmax - (-llmax - > > > > > > 1)`, which > > > > > > + simplifies to `2 * llmax + 1`. Given that `llmax` is the > > > > > > maximum value for > > > > > > + a `long long`, this calculation overflows in a defined manner > > > > > > + (wrapping around), which under `-fwrapv` is a legal operation > > > > > > that produces > > > > > > + a negative value due to two's complement wraparound. Therefore, > > > > > > + `llmax - llmin < 0` is true. > > > > > > + > > > > > > + However, the direct comparison `llmax < llmin` is false since > > > > > > `llmax` is the > > > > > > + maximum possible value and `llmin` is the minimum. Hence, > > > > > > optimizations > > > > > > + that rely on the equivalence of `(x - y) CMP 0` to `x CMP y` > > > > > > (and vice versa) > > > > > > + cannot be safely applied when `-fwrapv` is enabled. This is > > > > > > why this > > > > > > + optimization pass is disabled under `-fwrapv`. > > > > > > + > > > > > > + This optimization pass must run before the Jump Threading pass > > > > > > and > > > > > > + the VRP pass, as it may modify conditions. For example, in the > > > > > > VRP pass: > > > > > > + > > > > > > + (1) > > > > > > + int diff = x - y; > > > > > > + if (diff > 0) > > > > > > + foo(); > > > > > > + if (diff < 0) > > > > > > + bar(); > > > > > > + > > > > > > + The second condition would be converted to diff != 0 in the VRP > > > > > > pass because > > > > > > + we know the postcondition of the first condition is diff <= 0, > > > > > > and then > > > > > > + diff != 0 is cheaper than diff < 0. If we apply this pass after > > > > > > this VRP, > > > > > > + we get: > > > > > > + > > > > > > + (2) > > > > > > + int diff = x - y; > > > > > > + if (x > y) > > > > > > + foo(); > > > > > > + if (diff != 0) > > > > > > + bar(); > > > > > > + > > > > > > + This generates sub and test for the second condition and cmp > > > > > > for the first > > > > > > + condition. However, if we apply this pass beforehand, we simply > > > > > > get: > > > > > > + > > > > > > + (3) > > > > > > + int diff = x - y; > > > > > > + if (x > y) > > > > > > + foo(); > > > > > > + if (x < y) > > > > > > + bar(); > > > > > > + > > > > > > + In this code, diff will be eliminated as a dead code, and sub > > > > > > and test will > > > > > > + not be generated, which is more efficient. > > > > > > + > > > > > > + For the Jump Threading pass, without this optimization pass, > > > > > > (1) and (3) > > > > > > + above are recognized as different, which prevents TCO. */ > > > > > > + > > > > > > +#include "config.h" > > > > > > +#include "system.h" > > > > > > +#include "coretypes.h" > > > > > > +#include "backend.h" > > > > > > +#include "tree.h" > > > > > > +#include "gimple.h" > > > > > > +#include "tree-pass.h" > > > > > > +#include "ssa.h" > > > > > > +#include "gimple-iterator.h" > > > > > > +#include "domwalk.h" > > > > > > + > > > > > > +/* True if VAR is a signed integer, false otherwise. */ > > > > > > + > > > > > > +static bool > > > > > > +is_signed_integer(const_tree var) > > > > > > +{ > > > > > > + return (TREE_CODE (TREE_TYPE (var)) == INTEGER_TYPE > > > > > > + && !TYPE_UNSIGNED (TREE_TYPE (var))); > > > > > > +} > > > > > > + > > > > > > +/* If EXPR is an integer zero, return it. If EXPR is SSA_NAME, > > > > > > and its > > > > > > + defining statement is a subtraction of two signed integers, > > > > > > return the > > > > > > + MINUS_EXPR. Otherwise, return NULL_TREE. */ > > > > > > + > > > > > > +static const_tree > > > > > > +prop_integer_zero_or_minus_expr (const_tree expr) > > > > > > +{ > > > > > > + if (integer_zerop (expr)) > > > > > > + return expr; > > > > > > + > > > > > > + if (TREE_CODE (expr) != SSA_NAME) > > > > > > + return NULL_TREE; > > > > > > + > > > > > > + gimple *defining_stmt = SSA_NAME_DEF_STMT (expr); > > > > > > + if (!is_gimple_assign (defining_stmt) > > > > > > + || gimple_assign_rhs_code (defining_stmt) != MINUS_EXPR) > > > > > > + return NULL_TREE; > > > > > > + > > > > > > + tree rhs1 = gimple_assign_rhs1 (defining_stmt); > > > > > > + if (!is_signed_integer (rhs1)) > > > > > > + return NULL_TREE; > > > > > > + > > > > > > + tree rhs2 = gimple_assign_rhs2 (defining_stmt); > > > > > > + if (!is_signed_integer (rhs2)) > > > > > > + return NULL_TREE; > > > > > > + > > > > > > + return build2 (MINUS_EXPR, TREE_TYPE (expr), rhs1, rhs2); > > > > > > +} > > > > > > + > > > > > > +/* Optimize: > > > > > > + > > > > > > + 1. (x - y) CMP 0 > > > > > > + 2. 0 CMP (x - y) > > > > > > + > > > > > > + to: > > > > > > + > > > > > > + 1. x CMP y > > > > > > + 2. y CMP x > > > > > > + > > > > > > + where CMP is either <, <=, >, or >=. */ > > > > > > + > > > > > > +static void > > > > > > +optimize_signed_comparison (gcond *stmt) > > > > > > +{ > > > > > > + const enum tree_code code = gimple_cond_code (stmt); > > > > > > + if (code < LT_EXPR || GE_EXPR < code) > > > > > > + return; > > > > > > + > > > > > > + const_tree lhs = prop_integer_zero_or_minus_expr > > > > > > (gimple_cond_lhs (stmt)); > > > > > > + if (lhs == NULL_TREE) > > > > > > + return; > > > > > > + > > > > > > + const_tree rhs = prop_integer_zero_or_minus_expr > > > > > > (gimple_cond_rhs (stmt)); > > > > > > + if (rhs == NULL_TREE) > > > > > > + return; > > > > > > + > > > > > > + if (TREE_CODE (lhs) == MINUS_EXPR && integer_zerop (rhs)) > > > > > > + { > > > > > > + /* Case 1: (x - y) CMP 0 */ > > > > > > + tree x = TREE_OPERAND (lhs, 0); > > > > > > + tree y = TREE_OPERAND (lhs, 1); > > > > > > + > > > > > > + /* => x CMP y */ > > > > > > + gimple_cond_set_lhs (stmt, x); > > > > > > + gimple_cond_set_rhs (stmt, y); > > > > > > + update_stmt (stmt); > > > > > > + } > > > > > > + else if (integer_zerop (lhs) && TREE_CODE (rhs) == MINUS_EXPR) > > > > > > + { > > > > > > + /* Case 2: 0 CMP (x - y) */ > > > > > > + tree x = TREE_OPERAND (rhs, 0); > > > > > > + tree y = TREE_OPERAND (rhs, 1); > > > > > > + > > > > > > + /* => y CMP x */ > > > > > > + gimple_cond_set_lhs (stmt, y); > > > > > > + gimple_cond_set_rhs (stmt, x); > > > > > > + update_stmt (stmt); > > > > > > + } > > > > > > +} > > > > > > + > > > > > > +/* Find signed integer comparisons where the operands are > > > > > > MINUS_EXPR and > > > > > > + 0, and replace them with the equivalent comparison of the > > > > > > operands of > > > > > > + the MINUS_EXPR without the subtraction. */ > > > > > > + > > > > > > +namespace { > > > > > > + > > > > > > +const pass_data pass_data_cmp = > > > > > > +{ > > > > > > + GIMPLE_PASS, /* type */ > > > > > > + "cmp", /* name */ > > > > > > + OPTGROUP_NONE, /* optinfo_flags */ > > > > > > + TV_TREE_CMP, /* tv_id */ > > > > > > + PROP_ssa, /* properties_required */ > > > > > > + 0, /* properties_provided */ > > > > > > + 0, /* properties_destroyed */ > > > > > > + 0, /* todo_flags_start */ > > > > > > + TODO_remove_unused_locals, /* todo_flags_finish */ > > > > > > +}; > > > > > > + > > > > > > +class pass_cmp : public gimple_opt_pass > > > > > > +{ > > > > > > +public: > > > > > > + pass_cmp (gcc::context *ctxt) > > > > > > + : gimple_opt_pass (pass_data_cmp, ctxt) > > > > > > + {} > > > > > > + > > > > > > + /* opt_pass methods: */ > > > > > > + bool gate (function *) final override > > > > > > + { > > > > > > + /* If -fwrapv is enabled, this pass cannot be safely applied > > > > > > as described > > > > > > + in the comment at the top of this file. */ > > > > > > + return flag_tree_cmp != 0 && flag_wrapv == 0; > > > > > > + } > > > > > > + > > > > > > + unsigned int execute (function *) final override; > > > > > > + > > > > > > +}; // class pass_cmp > > > > > > + > > > > > > +class cmp_dom_walker : public dom_walker > > > > > > +{ > > > > > > +public: > > > > > > + cmp_dom_walker () : dom_walker (CDI_DOMINATORS) {} > > > > > > + > > > > > > + void after_dom_children (basic_block) final override; > > > > > > +}; > > > > > > + > > > > > > +void > > > > > > +cmp_dom_walker::after_dom_children (basic_block bb) > > > > > > +{ > > > > > > + gimple_stmt_iterator gsi; > > > > > > + > > > > > > + for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next > > > > > > (&gsi)) > > > > > > + { > > > > > > + gimple *stmt = gsi_stmt (gsi); > > > > > > + if (gimple_code (stmt) == GIMPLE_COND) > > > > > > + optimize_signed_comparison (as_a <gcond *> (stmt)); > > > > > > + } > > > > > > +} > > > > > > + > > > > > > + > > > > > > +unsigned int > > > > > > +pass_cmp::execute (function *) > > > > > > +{ > > > > > > + calculate_dominance_info (CDI_DOMINATORS); > > > > > > + cmp_dom_walker ().walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); > > > > > > + return 0; > > > > > > +} > > > > > > + > > > > > > +} // anon namespace > > > > > > + > > > > > > +gimple_opt_pass * > > > > > > +make_pass_cmp (gcc::context *ctxt) > > > > > > +{ > > > > > > + return new pass_cmp (ctxt); > > > > > > +} > > > > > > -- > > > > > > 2.44.0 > > > > > >
