This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
| Other format: | [Raw text] | |
Hello.
The patch adds a new pass that identifies a series of if-elseif
statements and transform then into a GIMPLE switch (if possible).
The pass runs right after tree-ssa pass and I decided to implement
matching of various forms that are introduced by folder (fold_range_test):
1) if condition with equal operation:
<bb 2> :
if (argc_8(D) == 1)
goto <bb 3>; [INV]
else
goto <bb 4>; [INV]
2) if condition with a range check:
<bb 3> :
_4 = c_13(D) + 198;
if (_4 <= 1)
goto <bb 7>; [INV]
else
goto <bb 4>; [INV]
3) mixture of 1) and 2) with a or condition:
<bb 2> :
_1 = aChar_8(D) == 1;
_2 = aChar_8(D) == 10;
_3 = _1 | _2;
if (_3 != 0)
goto <bb 5>; [INV]
else
goto <bb 3>; [INV]
or:
<bb 2> :
aChar.1_1 = (unsigned int) aChar_10(D);
_2 = aChar.1_1 + 4294967287;
_3 = _2 <= 1;
_4 = aChar_10(D) == 12;
_5 = _3 | _4;
if (_5 != 0)
goto <bb 5>; [INV]
else
goto <bb 3>; [INV]
The motivation example in PR88702 is transformed now into:
IsHTMLWhitespace (int aChar)
{
int iftmp.0_1;
<bb 2> [local count: 1073741824]:
switch (aChar_2(D)) <default: <L6> [50.00%], case 9 ... 10: <L7> [50.00%], case 12 ... 13: <L7> [50.00%], case 32: <L7> [50.00%]>
<bb 3> [local count: 536870913]:
<L6>:
<bb 4> [local count: 1073741824]:
# iftmp.0_1 = PHI <1(2), 0(3)>
<L7>:
return iftmp.0_1;
}
I'm also attaching if-elseif chains that are transformed in make all-host of the GCC compiler.
There are ~800 such transformations. The most beautiful transformation is this one:
$ cat -n gcc/c-family/c-common.c
...
2895 /* This used to be a switch, but Genix compiler can't handle that. */
2896 if (code == NE_EXPR)
2897 {
2898 if (max_lt || min_gt)
2899 val = truthvalue_true_node;
2900 }
2901 else if (code == EQ_EXPR)
2902 {
2903 if (max_lt || min_gt)
2904 val = truthvalue_false_node;
2905 }
...
Patch can bootstrap on x86_64-linux-gnu and survives regression tests.
Thoughts?
Thanks,
Martin
gcc/ChangeLog:
2019-11-04 Martin Liska <mliska@suse.cz>
PR tree-optimization/14799
PR ipa/88702
* Makefile.in: Include new tree-if-to-switch.o.
* common.opt: Document -ftree-if-to-switch.
* doc/invoke.texi: Likewise.
* opts.c: Enable the pass with -O2+.
* passes.def: Add ne pass.
* timevar.def (TV_TREE_IF_TO_SWITCH): Add new
timevar.
* tree-if-to-switch.c: New file.
* tree-pass.h (make_pass_if_to_switch): New.
gcc/testsuite/ChangeLog:
2019-11-04 Martin Liska <mliska@suse.cz>
PR tree-optimization/14799
PR ipa/88702
* gcc.dg/tree-ssa/if-to-switch-1.c: New test.
* gcc.dg/tree-ssa/if-to-switch-2.c: New test.
* gcc.dg/tree-ssa/if-to-switch-3.c: New test.
* gcc.dg/tree-ssa/if-to-switch-4.c: New test.
* gcc.dg/tree-ssa/if-to-switch-5.c: New test.
* gcc.dg/tree-ssa/reassoc-32.c: Disable tree-if-to-switch
in order to transform the range test.
* gcc.dg/tree-ssa/reassoc-33.c: Likewise.
---
gcc/Makefile.in | 1 +
gcc/common.opt | 4 +
gcc/doc/invoke.texi | 10 +-
gcc/opts.c | 1 +
gcc/passes.def | 1 +
.../gcc.dg/tree-ssa/if-to-switch-1.c | 35 +
.../gcc.dg/tree-ssa/if-to-switch-2.c | 11 +
.../gcc.dg/tree-ssa/if-to-switch-3.c | 11 +
.../gcc.dg/tree-ssa/if-to-switch-4.c | 35 +
.../gcc.dg/tree-ssa/if-to-switch-5.c | 12 +
gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c | 2 +-
gcc/testsuite/gcc.dg/tree-ssa/reassoc-33.c | 2 +-
gcc/timevar.def | 1 +
gcc/tree-if-to-switch.c | 611 ++++++++++++++++++
gcc/tree-pass.h | 1 +
15 files changed, 735 insertions(+), 3 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-1.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-2.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-3.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-4.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-5.c
create mode 100644 gcc/tree-if-to-switch.c
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 035b58f50c0..0d92347ad9b 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1525,6 +1525,7 @@ OBJS = \
tree-eh.o \
tree-emutls.o \
tree-if-conv.o \
+ tree-if-to-switch.o \
tree-inline.o \
tree-into-ssa.o \
tree-iterator.o \
diff --git a/gcc/common.opt b/gcc/common.opt
index cc279f411d7..671b2a99391 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -2649,6 +2649,10 @@ ftree-switch-conversion
Common Report Var(flag_tree_switch_conversion) Optimization
Perform conversions of switch initializations.
+ftree-if-to-switch
+Common Report Var(flag_tree_if_to_switch) Optimization
+Perform conversions of if-elseif chain into a switch statement.
+
ftree-dce
Common Report Var(flag_tree_dce) Optimization
Enable SSA dead code elimination optimization on trees.
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index faa7fa95a0e..125b34e7f43 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -478,7 +478,7 @@ Objective-C and Objective-C++ Dialects}.
-fthread-jumps -ftracer -ftree-bit-ccp @gol
-ftree-builtin-call-dce -ftree-ccp -ftree-ch @gol
-ftree-coalesce-vars -ftree-copy-prop -ftree-dce -ftree-dominator-opts @gol
--ftree-dse -ftree-forwprop -ftree-fre -fcode-hoisting @gol
+-ftree-dse -ftree-forwprop -ftree-fre -ftree-if-to-switch -fcode-hoisting @gol
-ftree-loop-if-convert -ftree-loop-im @gol
-ftree-phiprop -ftree-loop-distribution -ftree-loop-distribute-patterns @gol
-ftree-loop-ivcanon -ftree-loop-linear -ftree-loop-optimize @gol
@@ -8443,6 +8443,7 @@ also turns on the following optimization flags:
-fstrict-aliasing @gol
-fthread-jumps @gol
-ftree-builtin-call-dce @gol
+-ftree-if-to-switch @gol
-ftree-pre @gol
-ftree-switch-conversion -ftree-tail-merge @gol
-ftree-vrp}
@@ -9628,6 +9629,13 @@ Perform conversion of simple initializations in a switch to
initializations from a scalar array. This flag is enabled by default
at @option{-O2} and higher.
+@item -ftree-if-to-switch
+@opindex ftree-if-to-switch
+Perform conversion of an if cascade into a switch statement.
+The transformation can help to produce a faster code for
+the switch statement. This flag is enabled by default
+at @option{-O2} and higher.
+
@item -ftree-tail-merge
@opindex ftree-tail-merge
Look for identical code sequences. When found, replace one with a jump to the
diff --git a/gcc/opts.c b/gcc/opts.c
index 10b9f108f8d..f781cfd5709 100644
--- a/gcc/opts.c
+++ b/gcc/opts.c
@@ -524,6 +524,7 @@ static const struct default_options default_options_table[] =
{ OPT_LEVELS_2_PLUS, OPT_fthread_jumps, NULL, 1 },
{ OPT_LEVELS_2_PLUS, OPT_ftree_pre, NULL, 1 },
{ OPT_LEVELS_2_PLUS, OPT_ftree_switch_conversion, NULL, 1 },
+ { OPT_LEVELS_2_PLUS, OPT_ftree_if_to_switch, NULL, 1 },
{ OPT_LEVELS_2_PLUS, OPT_ftree_tail_merge, NULL, 1 },
{ OPT_LEVELS_2_PLUS, OPT_ftree_vrp, NULL, 1 },
{ OPT_LEVELS_2_PLUS, OPT_fvect_cost_model_, NULL, VECT_COST_MODEL_CHEAP },
diff --git a/gcc/passes.def b/gcc/passes.def
index 798a391bd35..2bd2c348fb3 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -59,6 +59,7 @@ along with GCC; see the file COPYING3. If not see
NEXT_PASS (pass_early_warn_uninitialized);
NEXT_PASS (pass_ubsan);
NEXT_PASS (pass_nothrow);
+ NEXT_PASS (pass_if_to_switch);
NEXT_PASS (pass_rebuild_cgraph_edges);
POP_INSERT_PASSES ()
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-1.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-1.c
new file mode 100644
index 00000000000..bcb8ef2a160
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-1.c
@@ -0,0 +1,35 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int global;
+int foo ();
+
+int main(int argc, char **argv)
+{
+ if (argc == 1)
+ foo ();
+ else if (argc == 2)
+ {
+ global += 1;
+ }
+ else if (argc == 3)
+ {
+ foo ();
+ foo ();
+ }
+ else if (argc == 4)
+ {
+ foo ();
+ }
+ else if (argc == 5)
+ {
+ global = 2;
+ }
+ else
+ global -= 123;
+
+ global -= 12;
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "Condition chain \\(at .*if-to-switch-1.c:9\\) with 5 conditions \\(5 BBs\\) transformed into a switch statement." "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-2.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-2.c
new file mode 100644
index 00000000000..316e772ec29
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-2.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int IsHTMLWhitespaceNoRange(int aChar)
+{
+ return aChar == 0x0001 || aChar == 0x000A ||
+ aChar == 0x000C || aChar == 0x000E ||
+ aChar == 0x0020;
+}
+
+/* { dg-final { scan-tree-dump "Condition chain \\(at .*if-to-switch-2.c:7\\) with 5 conditions \\(3 BBs\\) transformed into a switch statement." "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-3.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-3.c
new file mode 100644
index 00000000000..fd07d909a3c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-3.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int IsHTMLWhitespace(int aChar)
+{
+ return aChar == 0x0009 || aChar == 0x000A ||
+ aChar == 0x000C || aChar == 0x000D ||
+ aChar == 0x0020 || aChar == 0x0030;
+}
+
+/* { dg-final { scan-tree-dump "Condition chain \\(at .*if-to-switch-3.c:8\\) with 5 conditions \\(3 BBs\\) transformed into a switch statement." "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-4.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-4.c
new file mode 100644
index 00000000000..4e047505a2b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-4.c
@@ -0,0 +1,35 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int global;
+int foo ();
+
+int main(int argc, char **argv)
+{
+ if (argc == 1)
+ foo ();
+ else if (argc == 2)
+ {
+ global += 1;
+ }
+ else if (argc == 3)
+ {
+ foo ();
+ foo ();
+ }
+ else if (argc == 4)
+ {
+ foo ();
+ }
+ else if (argc == 1)
+ {
+ global = 2;
+ }
+ else
+ global -= 123;
+
+ global -= 12;
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-not "Condition chain " "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-5.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-5.c
new file mode 100644
index 00000000000..acb8b4b1211
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-5.c
@@ -0,0 +1,12 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int crud (unsigned char c)
+{
+ return (((((((((((int) c == 46) || (int) c == 44)
+ || (int) c == 58) || (int) c == 59) || (int) c == 60)
+ || (int) c == 62) || (int) c == 34) || (int) c == 92)
+ || (int) c == 39) != 0);
+}
+
+/* { dg-final { scan-tree-dump "Condition chain \\(at .*if-to-switch-5.c:9\\) with 8 conditions \\(5 BBs\\) transformed into a switch statement." "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c
index 944362ad076..0d4411fecf7 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c
@@ -1,6 +1,6 @@
/* { dg-do run { target { ! "m68k*-*-* mmix*-*-* bfin*-*-* v850*-*-* moxie*-*-* cris*-*-* m32c*-*-* fr30*-*-* mcore*-*-* powerpc*-*-* xtensa*-*-*"} } } */
-/* { dg-options "-O2 -fno-inline -fdump-tree-reassoc1-details --param logical-op-non-short-circuit=1" } */
+/* { dg-options "-O2 -fno-inline -fdump-tree-reassoc1-details --param logical-op-non-short-circuit=1 -fno-tree-if-to-switch" } */
/* { dg-additional-options "-mbranch-cost=2" { target branch_cost } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-33.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-33.c
index db0ce4c8463..d52860fa2f4 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-33.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-33.c
@@ -1,6 +1,6 @@
/* { dg-do run { target { ! "m68k*-*-* mmix*-*-* bfin*-*-* v850*-*-* moxie*-*-* cris*-*-* m32c*-*-* fr30*-*-* mcore*-*-* powerpc*-*-* xtensa*-*-* hppa*-*-* nios2*-*-* or1k-*-*-* pru*-*-*"} } } */
-/* { dg-options "-O2 -fno-inline -fdump-tree-reassoc1-details --param logical-op-non-short-circuit=1" } */
+/* { dg-options "-O2 -fno-inline -fdump-tree-reassoc1-details --param logical-op-non-short-circuit=1 -fno-tree-if-to-switch" } */
/* { dg-additional-options "-mbranch-cost=2" { target branch_cost } } */
int test (int a, int b, int c)
diff --git a/gcc/timevar.def b/gcc/timevar.def
index 357fcfd65c5..20ea20a6178 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -290,6 +290,7 @@ DEFTIMEVAR (TV_VAR_TRACKING , "variable tracking")
DEFTIMEVAR (TV_VAR_TRACKING_DATAFLOW , "var-tracking dataflow")
DEFTIMEVAR (TV_VAR_TRACKING_EMIT , "var-tracking emit")
DEFTIMEVAR (TV_TREE_IFCOMBINE , "tree if-combine")
+DEFTIMEVAR (TV_TREE_IF_TO_SWITCH , "if to switch conversion")
DEFTIMEVAR (TV_TREE_UNINIT , "uninit var analysis")
DEFTIMEVAR (TV_PLUGIN_INIT , "plugin initialization")
DEFTIMEVAR (TV_PLUGIN_RUN , "plugin execution")
diff --git a/gcc/tree-if-to-switch.c b/gcc/tree-if-to-switch.c
new file mode 100644
index 00000000000..43984b6b7e4
--- /dev/null
+++ b/gcc/tree-if-to-switch.c
@@ -0,0 +1,611 @@
+/* If-elseif-else to switch conversion pass
+ Copyright (C) 2019 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/>. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "rtl.h"
+#include "tree.h"
+#include "gimple.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "gimple-pretty-print.h"
+#include "fold-const.h"
+#include "gimple-iterator.h"
+#include "tree-cfg.h"
+#include "tree-dfa.h"
+#include "domwalk.h"
+#include "tree-cfgcleanup.h"
+#include "params.h"
+#include "alias.h"
+#include "tree-ssa-loop.h"
+#include "diagnostic.h"
+#include "cfghooks.h"
+#include "tree-into-ssa.h"
+#include "cfganal.h"
+
+/* Tuple that holds minimum and maximum values in a case. */
+
+struct case_range
+{
+ /* Default constructor. */
+ case_range ():
+ m_min (NULL_TREE), m_max (NULL_TREE)
+ {}
+
+ /* Minimum case value. */
+ tree m_min;
+ /* Maximum case value. */
+ tree m_max;
+};
+
+/* One entry of a if chain. */
+
+struct if_chain_entry
+{
+ /* Constructor. */
+ if_chain_entry (basic_block bb, edge true_edge, edge false_edge)
+ : m_case_values (), m_bb (bb),
+ m_true_edge (true_edge), m_false_edge (false_edge)
+ {
+ m_case_values.create (2);
+ }
+
+ /* Vector of at maximum 2 case ranges. */
+ vec<case_range> m_case_values;
+ /* Basic block of the original condition. */
+ basic_block m_bb;
+ /* True edge of the gimple condition. */
+ edge m_true_edge;
+ /* False edge of the gimple condition. */
+ edge m_false_edge;
+};
+
+/* Master structure for one if to switch conversion candidate. */
+
+struct if_chain
+{
+ /* Default constructor. */
+ if_chain():
+ m_first_condition (NULL), m_index (NULL_TREE), m_entries ()
+ {
+ m_entries.create (2);
+ }
+
+ /* Set index and check that it is not a different one. */
+ bool set_and_check_index (tree index);
+
+ /* Verify that all case ranges do not overlap. */
+ bool check_non_overlapping_cases ();
+
+ /* First condition of the chain. */
+ gcond *m_first_condition;
+ /* Switch index. */
+ tree m_index;
+ /* If chain entries. */
+ vec<if_chain_entry> m_entries;
+};
+
+bool
+if_chain::set_and_check_index (tree index)
+{
+ if (TREE_CODE (index) != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (index)))
+ return false;
+
+ if (m_index == NULL)
+ m_index = index;
+
+ return index == m_index;
+}
+
+/* Compare two case ranges by minimum value. */
+
+static int
+range_cmp (const void *a, const void *b)
+{
+ const case_range *cr1 = *(const case_range * const *) a;
+ const case_range *cr2 = *(const case_range * const *) b;
+
+ return tree_int_cst_compare (cr1->m_min, cr2->m_min);
+}
+
+bool
+if_chain::check_non_overlapping_cases ()
+{
+ auto_vec<case_range *> all_ranges;
+ for (unsigned i = 0; i < m_entries.length (); i++)
+ for (unsigned j =0; j < m_entries[i].m_case_values.length (); j++)
+ all_ranges.safe_push (&m_entries[i].m_case_values[j]);
+
+ all_ranges.qsort (range_cmp);
+
+ for (unsigned i = 0; i < all_ranges.length () - 1; i++)
+ {
+ case_range *left = all_ranges[i];
+ case_range *right = all_ranges[i + 1];
+ if (tree_int_cst_le (left->m_min, right->m_min)
+ && tree_int_cst_le (right->m_min, left->m_max))
+ return false;
+ }
+
+ return true;
+}
+
+/* DOM walker for if to switch conversion. */
+
+class if_dom_walker : public dom_walker
+{
+public:
+ if_dom_walker (cdi_direction direction)
+ : dom_walker (direction), all_candidates (), m_visited_bbs ()
+ {}
+
+ virtual edge before_dom_children (basic_block);
+
+ /* List of all found candidates. */
+ auto_vec<if_chain> all_candidates;
+
+private:
+ /* Bitmap of all visited basic blocks. */
+ auto_bitmap m_visited_bbs;
+};
+
+/* Build case label with MIN and MAX values of a given basic block DEST. */
+
+static tree
+build_case_label (tree min, tree max, basic_block dest)
+{
+ tree label = gimple_block_label (dest);
+ return build_case_label (min, min == max ? NULL_TREE : max, label);
+}
+
+/* Compare two integer constants. */
+
+static int
+label_cmp (const void *a, const void *b)
+{
+ const_tree l1 = *(const const_tree *) a;
+ const_tree l2 = *(const const_tree *) b;
+
+ return tree_int_cst_compare (CASE_LOW (l1), CASE_LOW (l2));
+}
+
+/* Record all original phi arguments into PHI_MAX. Do it for
+ a given edge E. */
+
+static void
+record_phi_arguments (hash_map<basic_block, vec<tree> > *phi_map, edge e)
+{
+ if (phi_map->get (e->dest) == NULL)
+ {
+ vec<tree> phi_arguments;
+ phi_arguments.create (4);
+ for (gphi_iterator gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ {
+ gphi *phi = gsi.phi ();
+ if (!virtual_operand_p (gimple_phi_result (phi)))
+ phi_arguments.safe_push (PHI_ARG_DEF_FROM_EDGE (phi, e));
+ }
+
+ phi_map->put (e->dest, phi_arguments);
+ }
+}
+
+/* Convert a given if CHAIN into a switch GIMPLE statement. */
+
+static void
+convert_if_conditions_to_switch (if_chain &chain)
+{
+ auto_vec<tree> labels;
+ if_chain_entry first_cond = chain.m_entries[0];
+
+ unsigned entries = chain.m_entries.length ();
+ edge default_edge = chain.m_entries[entries - 1].m_false_edge;
+ basic_block default_bb = default_edge->dest;
+
+ /* Recond all PHI nodes that will later be fixed. */
+ hash_map<basic_block, vec<tree> > phi_map;
+ for (unsigned i = 0; i < chain.m_entries.length (); i++)
+ record_phi_arguments (&phi_map, chain.m_entries[i].m_true_edge);
+ record_phi_arguments (&phi_map, chain.m_entries[entries - 1].m_false_edge);
+
+ for (unsigned i = 0; i < chain.m_entries.length (); i++)
+ {
+ if_chain_entry entry = chain.m_entries[i];
+
+ basic_block case_bb = entry.m_true_edge->dest;
+
+ for (unsigned j = 0; j < entry.m_case_values.length (); j++)
+ labels.safe_push (build_case_label (entry.m_case_values[j].m_min,
+ entry.m_case_values[j].m_max,
+ case_bb));
+ default_bb = entry.m_false_edge->dest;
+
+ if (i == 0)
+ {
+ remove_edge (first_cond.m_true_edge);
+ remove_edge (first_cond.m_false_edge);
+ }
+ else
+ delete_basic_block (entry.m_bb);
+
+ make_edge (first_cond.m_bb, case_bb, 0);
+ }
+
+ labels.qsort (label_cmp);
+
+ edge e = find_edge (first_cond.m_bb, default_bb);
+ if (e == NULL)
+ e = make_edge (first_cond.m_bb, default_bb, 0);
+ gswitch *s
+ = gimple_build_switch (chain.m_index,
+ build_case_label (NULL_TREE, NULL_TREE, default_bb),
+ labels);
+
+ gimple_stmt_iterator gsi = gsi_for_stmt (chain.m_first_condition);
+ gsi_remove (&gsi, true);
+ gsi_insert_before (&gsi, s, GSI_NEW_STMT);
+
+ /* Fill up missing PHI node arguments. */
+ for (hash_map<basic_block, vec<tree> >::iterator it = phi_map.begin ();
+ it != phi_map.end (); ++it)
+ {
+ edge e = find_edge (first_cond.m_bb, (*it).first);
+ unsigned i = 0;
+ for (gphi_iterator gsi = gsi_start_phis ((*it).first); !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ {
+ gphi *phi = gsi.phi ();
+ if (!virtual_operand_p (gimple_phi_result (phi)))
+ add_phi_arg (phi, (*it).second[i++], e, UNKNOWN_LOCATION);
+ }
+ }
+}
+
+static bool
+extract_case_from_stmt (tree rhs1, tree rhs2, tree_code code, tree *index,
+ case_range *range, unsigned *visited_stmt_count)
+{
+ if (code == EQ_EXPR)
+ {
+ /* Handle situation 2a:
+ _1 = aChar_8(D) == 1; */
+ *index = rhs1;
+ range->m_min = rhs2;
+ range->m_max = range->m_min;
+
+ if (TREE_CODE (rhs2) != INTEGER_CST)
+ return false;
+
+ *visited_stmt_count += 1;
+ return true;
+ }
+ else if (code == LE_EXPR)
+ {
+ /* Handle situation 2b:
+ aChar.1_1 = (unsigned int) aChar_10(D);
+ _2 = aChar.1_1 + 4294967287;
+ _3 = _2 <= 1; */
+ tree ssa = rhs1;
+ tree range_size = rhs2;
+ if (TREE_CODE (ssa) != SSA_NAME
+ || TREE_CODE (range_size) != INTEGER_CST)
+ return false;
+
+ gassign *subtraction = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (ssa));
+ if (subtraction == NULL
+ || gimple_assign_rhs_code (subtraction) != PLUS_EXPR)
+ return false;
+
+ tree casted = gimple_assign_rhs1 (subtraction);
+ tree min = gimple_assign_rhs2 (subtraction);
+ if (TREE_CODE (casted) != SSA_NAME
+ || TREE_CODE (min) != INTEGER_CST)
+ return false;
+
+ if (!SSA_NAME_IS_DEFAULT_DEF (casted))
+ {
+ gassign *to_unsigned
+ = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (casted));
+ if (to_unsigned == NULL
+ || !gimple_assign_unary_nop_p (to_unsigned)
+ || !TYPE_UNSIGNED (TREE_TYPE (casted)))
+ return false;
+ *index = gimple_assign_rhs1 (to_unsigned);
+ ++(*visited_stmt_count);
+ }
+ else
+ *index = casted;
+
+ tree type = TREE_TYPE (*index);
+ tree range_min = fold_convert (type, const_unop (NEGATE_EXPR, type, min));
+
+ range->m_min = range_min;
+ range->m_max = const_binop (PLUS_EXPR, TREE_TYPE (*index),
+ range_min, fold_convert (type, range_size));
+ *visited_stmt_count += 2;
+ return true;
+ }
+ else
+ return false;
+}
+
+edge
+if_dom_walker::before_dom_children (basic_block bb)
+{
+ if_chain chain;
+ unsigned total_case_values = 0;
+
+ while (true)
+ {
+ bool first = chain.m_entries.is_empty ();
+ if (bitmap_bit_p (m_visited_bbs, bb->index))
+ break;
+ bitmap_set_bit (m_visited_bbs, bb->index);
+
+ gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
+ if (gsi_end_p (gsi))
+ break;
+
+ if (!chain.m_entries.is_empty () && EDGE_COUNT (bb->preds) != 1)
+ break;
+
+ gcond *cond = dyn_cast<gcond *> (gsi_stmt (gsi));
+ if (cond == NULL)
+ break;
+
+ if (first)
+ chain.m_first_condition = cond;
+
+ edge true_edge, false_edge;
+ extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
+
+ if_chain_entry entry (bb, true_edge, false_edge);
+
+ /* Current we support following patterns (situations):
+
+ 1) if condition with equal operation:
+
+ <bb 2> :
+ if (argc_8(D) == 1)
+ goto <bb 3>; [INV]
+ else
+ goto <bb 4>; [INV]
+
+ 2) if condition with a range check:
+
+ <bb 3> :
+ _4 = c_13(D) + 198;
+ if (_4 <= 1)
+ goto <bb 7>; [INV]
+ else
+ goto <bb 4>; [INV]
+
+ 3) mixture of 1) and 2) with a or condition:
+
+ <bb 2> :
+ _1 = aChar_8(D) == 1;
+ _2 = aChar_8(D) == 10;
+ _3 = _1 | _2;
+ if (_3 != 0)
+ goto <bb 5>; [INV]
+ else
+ goto <bb 3>; [INV]
+
+ or:
+
+ <bb 2> :
+ aChar.1_1 = (unsigned int) aChar_10(D);
+ _2 = aChar.1_1 + 4294967287;
+ _3 = _2 <= 1;
+ _4 = aChar_10(D) == 12;
+ _5 = _3 | _4;
+ if (_5 != 0)
+ goto <bb 5>; [INV]
+ else
+ goto <bb 3>; [INV]
+ */
+
+ tree lhs = gimple_cond_lhs (cond);
+ tree rhs = gimple_cond_rhs (cond);
+ tree_code code = gimple_cond_code (cond);
+ unsigned visited_stmt_count = 0;
+ unsigned case_values = 0;
+ tree index;
+
+ /* Situation 1. */
+ if (code == EQ_EXPR)
+ {
+ case_range range;
+ if (!extract_case_from_stmt (lhs, rhs, code, &index, &range,
+ &visited_stmt_count))
+ break;
+ if (!chain.set_and_check_index (index))
+ break;
+ entry.m_case_values.safe_push (range);
+ case_values = 1;
+ }
+ /* Situation 2. */
+ else if (code == LE_EXPR)
+ {
+ case_range range;
+ if (!extract_case_from_stmt (lhs, rhs, code, &index, &range,
+ &visited_stmt_count))
+ break;
+ if (!chain.set_and_check_index (index))
+ break;
+ entry.m_case_values.safe_push (range);
+ case_values = 1;
+ }
+ /* Situation 3. */
+ else if (code == NE_EXPR
+ && integer_zerop (rhs)
+ && TREE_CODE (lhs) == SSA_NAME
+ && TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE)
+ {
+ gassign *def = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (lhs));
+ if (def == NULL
+ || gimple_assign_rhs_code (def) != BIT_IOR_EXPR
+ || gimple_bb (def) != bb)
+ break;
+
+ tree rhs1 = gimple_assign_rhs1 (def);
+ tree rhs2 = gimple_assign_rhs2 (def);
+ if (TREE_CODE (rhs1) != SSA_NAME || TREE_CODE (rhs2) != SSA_NAME)
+ break;
+
+ gassign *def1 = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (rhs1));
+ gassign *def2 = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (rhs2));
+ if (def1 == NULL
+ || def2 == NULL
+ || def1 == def2
+ || gimple_bb (def1) != bb
+ || gimple_bb (def2) != bb)
+ break;
+
+ case_range range1;
+ if (!extract_case_from_stmt (gimple_assign_rhs1 (def1),
+ gimple_assign_rhs2 (def1),
+ gimple_assign_rhs_code (def1),
+ &index, &range1,
+ &visited_stmt_count))
+ break;
+ rhs = gimple_assign_rhs2 (def1);
+ if (!chain.set_and_check_index (index))
+ break;
+ entry.m_case_values.safe_push (range1);
+
+ case_range range2;
+ if (!extract_case_from_stmt (gimple_assign_rhs1 (def2),
+ gimple_assign_rhs2 (def2),
+ gimple_assign_rhs_code (def2),
+ &index, &range2,
+ &visited_stmt_count))
+ break;
+ rhs = gimple_assign_rhs2 (def2);
+ if (!chain.set_and_check_index (index))
+ break;
+ entry.m_case_values.safe_push (range2);
+ case_values = 2;
+ visited_stmt_count += 2;
+ }
+ else
+ break;
+
+ /* If it's not the first condition, then we need a BB without
+ any statements. */
+ if (!first)
+ {
+ unsigned stmt_count = 0;
+ for (gimple_stmt_iterator gsi = gsi_start_nondebug_bb (bb);
+ !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
+ ++stmt_count;
+
+ if (stmt_count - visited_stmt_count != 0)
+ break;
+ }
+
+ total_case_values += case_values;
+ chain.m_entries.safe_push (entry);
+
+ /* Follow if-elseif-elseif chain. */
+ bb = false_edge->dest;
+ }
+
+ if (total_case_values >= 3
+ && chain.check_non_overlapping_cases ())
+ {
+ if (dump_file)
+ {
+ expanded_location loc
+ = expand_location (gimple_location (chain.m_first_condition));
+ fprintf (dump_file, "Condition chain (at %s:%d) with %d conditions "
+ "(%d BBs) transformed into a switch statement.\n",
+ loc.file, loc.line, total_case_values,
+ chain.m_entries.length ());
+ }
+
+ all_candidates.safe_push (chain);
+ }
+
+ return NULL;
+}
+
+namespace {
+
+const pass_data pass_data_if_to_switch =
+{
+ GIMPLE_PASS, /* type */
+ "iftoswitch", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_TREE_IF_TO_SWITCH, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_cleanup_cfg | TODO_update_ssa /* todo_flags_finish */
+};
+
+class pass_if_to_switch : public gimple_opt_pass
+{
+public:
+ pass_if_to_switch (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_if_to_switch, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *) { return flag_tree_if_to_switch != 0; }
+ virtual unsigned int execute (function *);
+
+}; // class pass_if_to_switch
+
+unsigned int
+pass_if_to_switch::execute (function *fun)
+{
+ /* We might consider making this a property of each pass so that it
+ can be [re]computed on an as-needed basis. Particularly since
+ this pass could be seen as an extension of DCE which needs post
+ dominators. */
+ calculate_dominance_info (CDI_DOMINATORS);
+
+ /* Dead store elimination is fundamentally a walk of the post-dominator
+ tree and a backwards walk of statements within each block. */
+ if_dom_walker walker (CDI_DOMINATORS);
+ walker.walk (fun->cfg->x_entry_block_ptr);
+
+ for (unsigned i = 0; i < walker.all_candidates.length (); i++)
+ convert_if_conditions_to_switch (walker.all_candidates[i]);
+
+ /* For now, just wipe the dominator information. */
+ free_dominance_info (CDI_DOMINATORS);
+
+ mark_virtual_operands_for_renaming (cfun);
+
+ return 0;
+}
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_if_to_switch (gcc::context *ctxt)
+{
+ return new pass_if_to_switch (ctxt);
+}
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index a987661530e..84c498cb26e 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -374,6 +374,7 @@ extern gimple_opt_pass *make_pass_empty_loop (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_graphite (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_graphite_transforms (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_if_conversion (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_if_to_switch (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_loop_distribution (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_vectorize (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_simduid_cleanup (gcc::context *ctxt);
Attachment:
if-to-switch-in-gcc.txt
Description: Text document
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |