On 01/15/2018 12:22 AM, Bernhard Reutner-Fischer wrote:
> Can you please post CSiBE numbers? Ideally throwing in gcc-3.4.6 numbers too?
>
> thanks,
Hi.
I've just retested the patch and looks fine. There are numbers of CSiBE. I'm
sorry I don't
have such old version of GCC:
+-------------------+--------+------------------+------------------+-----------------+--------------------+
| object | trunk | Trunk w/ patch | Gcc 7.3.1 | patch vs.
trunk | Gcc 7.3.1 vs trunk |
+-------------------+--------+------------------+------------------+-----------------+--------------------+
| buf.c.o | 2531 | 2531 | 2531 |
0 | 0 |
| ccl.c.o | 2520 | 2520 | 2519 |
0 | -1 |
| dfa.c.o | 9909 | 9909 | 9909 |
0 | 0 |
| ecs.c.o | 1432 | 1432 | 1432 |
0 | 0 |
| filter.c.o | 4810 | 4810 | 4810 |
0 | 0 |
| gen.c.o | 28696 | 28696 | 28805 |
0 | 109 |
| libmain.c.o | 88 | 88 | 88 |
0 | 0 |
| libyywrap.c.o | 54 | 54 | 67 |
0 | 13 |
| main.c.o | 22132 | 22132 | 22129 |
0 | -3 |
| misc.c.o | 9765 | 9765 | 9811 |
0 | 46 |
| nfa.c.o | 6449 | 6467 | 6449 |
18 | 0 |
| options.c.o | 1240 | 1240 | 1240 |
0 | 0 |
| parse.c.o | 15737 | 15737 | 15742 |
0 | 5 |
| regex.c.o | 1374 | 1374 | 1374 |
0 | 0 |
| scan.c.o | 66844 | 66896 | 66944 |
52 | 100 |
| scanflags.c.o | 422 | 422 | 435 |
0 | 13 |
| scanopt.c.o | 8170 | 8201 | 8198 |
31 | 28 |
| skel.c.o | 91010 | 91010 | 91010 |
0 | 0 |
| sym.c.o | 1796 | 1796 | 1796 |
0 | 0 |
| tables.c.o | 5000 | 5070 | 4998 |
70 | -2 |
| tables_shared.c.o | 122 | 122 | 122 |
0 | 0 |
| tblcmp.c.o | 5587 | 5587 | 5578 |
0 | -9 |
| yylex.c.o | 2166 | 2332 | 2122 |
166 | -44 |
| blocksort.c.o | 13850 | 13850 | 13862 |
0 | 12 |
| bzip2.c.o | 23540 | 23702 | 23535 |
162 | -5 |
| bzip2recover.c.o | 4863 | 4863 | 4865 |
0 | 2 |
| bzlib.c.o | 21359 | 21433 | 21393 |
74 | 34 |
| compress.c.o | 24424 | 24424 | 24409 |
0 | -15 |
| crctable.c.o | 0 | 0 | 0 |
0 | 0 |
| decompress.c.o | 23467 | 23467 | 23464 |
0 | -3 |
| dlltest.c.o | 1213 | 1213 | 1213 |
0 | 0 |
| huffman.c.o | 2180 | 2180 | 2180 |
0 | 0 |
| mk251.c.o | 103 | 103 | 103 |
0 | 0 |
| randtable.c.o | 0 | 0 | 0 |
0 | 0 |
| spewG.c.o | 477 | 477 | 480 |
0 | 3 |
| unzcrash.c.o | 1284 | 1284 | 1284 |
0 | 0 |
| SUM | 404614 | 405187 | 404897 |
573 | 283 |
| ratio | | 1.00141616454201 | 0.99928428108503 |
| |
+-------------------+--------+------------------+------------------+-----------------+--------------------+
So the patch looks fine, only very very slightly binary is produced. I'm going
to install the patch so that
I can carry on more complex patches based on this one.
Bernhard: I'm able to build only flex and bzip2. Do you know why? I noticed
there are other projects in toplevel
directory.
./csibe.py
-- The C compiler identification is GNU 7.3.1
-- The CXX compiler identification is GNU 7.3.1
-- Check for working C compiler: /usr/bin/cc
-- Check for working C compiler: /usr/bin/cc -- works
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Detecting C compile features
-- Detecting C compile features - done
-- Check for working CXX compiler: /usr/bin/c++
-- Check for working CXX compiler: /usr/bin/c++ -- works
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Configuring done
-- Generating done
-- Build files have been written to: /tmp/csibe/build/native
make: Entering directory '/tmp/csibe/build/native'
make[1]: Entering directory '/tmp/csibe/build/native'
make[2]: Entering directory '/tmp/csibe/build/native'
Scanning dependencies of target bzip2-1.0.6
make[2]: Leaving directory '/tmp/csibe/build/native'
make[2]: Entering directory '/tmp/csibe/build/native'
[ 2%] Building C object
gen/bzip2-1.0.6/CMakeFiles/bzip2-1.0.6.dir/__/__/src/bzip2-1.0.6/blocksort.c.o
[ 5%] Building C object
gen/bzip2-1.0.6/CMakeFiles/bzip2-1.0.6.dir/__/__/src/bzip2-1.0.6/bzip2.c.o
[ 8%] Building C object
gen/bzip2-1.0.6/CMakeFiles/bzip2-1.0.6.dir/__/__/src/bzip2-1.0.6/bzip2recover.c.o
[ 11%] Building C object
gen/bzip2-1.0.6/CMakeFiles/bzip2-1.0.6.dir/__/__/src/bzip2-1.0.6/bzlib.c.o
[ 13%] Building C object
gen/bzip2-1.0.6/CMakeFiles/bzip2-1.0.6.dir/__/__/src/bzip2-1.0.6/compress.c.o
[ 16%] Building C object
gen/bzip2-1.0.6/CMakeFiles/bzip2-1.0.6.dir/__/__/src/bzip2-1.0.6/crctable.c.o
[ 19%] Building C object
gen/bzip2-1.0.6/CMakeFiles/bzip2-1.0.6.dir/__/__/src/bzip2-1.0.6/decompress.c.o
[ 22%] Building C object
gen/bzip2-1.0.6/CMakeFiles/bzip2-1.0.6.dir/__/__/src/bzip2-1.0.6/dlltest.c.o
[ 25%] Building C object
gen/bzip2-1.0.6/CMakeFiles/bzip2-1.0.6.dir/__/__/src/bzip2-1.0.6/huffman.c.o
[ 27%] Building C object
gen/bzip2-1.0.6/CMakeFiles/bzip2-1.0.6.dir/__/__/src/bzip2-1.0.6/mk251.c.o
[ 30%] Building C object
gen/bzip2-1.0.6/CMakeFiles/bzip2-1.0.6.dir/__/__/src/bzip2-1.0.6/randtable.c.o
[ 33%] Building C object
gen/bzip2-1.0.6/CMakeFiles/bzip2-1.0.6.dir/__/__/src/bzip2-1.0.6/spewG.c.o
[ 36%] Building C object
gen/bzip2-1.0.6/CMakeFiles/bzip2-1.0.6.dir/__/__/src/bzip2-1.0.6/unzcrash.c.o
make[2]: Leaving directory '/tmp/csibe/build/native'
[ 36%] Built target bzip2-1.0.6
make[2]: Entering directory '/tmp/csibe/build/native'
Scanning dependencies of target flex-2.6.0
make[2]: Leaving directory '/tmp/csibe/build/native'
make[2]: Entering directory '/tmp/csibe/build/native'
[ 38%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/buf.c.o
[ 41%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/ccl.c.o
[ 44%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/dfa.c.o
[ 47%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/ecs.c.o
[ 50%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/filter.c.o
[ 52%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/gen.c.o
[ 55%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/libmain.c.o
[ 58%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/libyywrap.c.o
[ 61%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/main.c.o
[ 63%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/misc.c.o
[ 66%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/nfa.c.o
[ 69%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/options.c.o
[ 72%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/parse.c.o
[ 75%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/regex.c.o
[ 77%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/scan.c.o
[ 80%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/scanflags.c.o
[ 83%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/scanopt.c.o
[ 86%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/skel.c.o
[ 88%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/sym.c.o
[ 91%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/tables.c.o
[ 94%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/tables_shared.c.o
[ 97%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/tblcmp.c.o
[100%] Building C object
gen/flex-2.6.0/CMakeFiles/flex-2.6.0.dir/__/__/src/flex-2.6.0/src/yylex.c.o
make[2]: Leaving directory '/tmp/csibe/build/native'
[100%] Built target flex-2.6.0
make[1]: Leaving directory '/tmp/csibe/build/native'
make: Leaving directory '/tmp/csibe/build/native'
make: Entering directory '/tmp/csibe/build/native'
make[1]: Entering directory '/tmp/csibe/build/native'
make[2]: Entering directory '/tmp/csibe/build/native'
make[3]: Entering directory '/tmp/csibe/build/native'
make[3]: Leaving directory '/tmp/csibe/build/native'
[ 60%] Built target flex-2.6.0
make[3]: Entering directory '/tmp/csibe/build/native'
Scanning dependencies of target flex-2.6.0_size
make[3]: Leaving directory '/tmp/csibe/build/native'
make[3]: Entering directory '/tmp/csibe/build/native'
[ 63%] Generating result.csv
make[3]: Leaving directory '/tmp/csibe/build/native'
[ 63%] Built target flex-2.6.0_size
make[3]: Entering directory '/tmp/csibe/build/native'
make[3]: Leaving directory '/tmp/csibe/build/native'
[ 97%] Built target bzip2-1.0.6
make[3]: Entering directory '/tmp/csibe/build/native'
Scanning dependencies of target bzip2-1.0.6_size
make[3]: Leaving directory '/tmp/csibe/build/native'
make[3]: Entering directory '/tmp/csibe/build/native'
[100%] Generating result.csv
make[3]: Leaving directory '/tmp/csibe/build/native'
[100%] Built target bzip2-1.0.6_size
make[3]: Entering directory '/tmp/csibe/build/native'
Scanning dependencies of target size
make[3]: Leaving directory '/tmp/csibe/build/native'
make[3]: Entering directory '/tmp/csibe/build/native'
make[3]: Leaving directory '/tmp/csibe/build/native'
[100%] Built target size
make[2]: Leaving directory '/tmp/csibe/build/native'
make[1]: Leaving directory '/tmp/csibe/build/native'
make: Leaving directory '/tmp/csibe/build/native'
Martin
>From 1ee3fd1cd03a47ad44b7f2b475c3ddcaf2f4c6a9 Mon Sep 17 00:00:00 2001
From: marxin <mli...@suse.cz>
Date: Tue, 5 Sep 2017 12:11:13 +0200
Subject: [PATCH] Radically simplify emission of balanced tree for switch
statements.
gcc/ChangeLog:
2017-09-14 Martin Liska <mli...@suse.cz>
* passes.def: Add pass_lower_switch and pass_lower_switch_O0.
* tree-pass.h (make_pass_lower_switch_O0): New function.
* tree-switch-conversion.c (node_has_low_bound): Remove.
(node_has_high_bound): Likewise.
(node_is_bounded): Likewise.
(class pass_lower_switch): Make it a template type and create
two instances.
(pass_lower_switch::execute): Add template argument.
(make_pass_lower_switch): New function.
(make_pass_lower_switch_O0): New function.
(do_jump_if_equal): Remove.
(emit_case_nodes): Simplify to just handle all 3 cases and leave
all the hard work to tree optimization passes.
gcc/testsuite/ChangeLog:
2017-09-14 Martin Liska <mli...@suse.cz>
* gcc.dg/tree-ssa/vrp104.c: Adjust dump file that is scanned.
* gcc.dg/tree-prof/update-loopch.c: Likewise.
---
gcc/passes.def | 3 +
gcc/testsuite/gcc.dg/tree-prof/update-loopch.c | 2 +-
gcc/testsuite/gcc.dg/tree-ssa/vrp104.c | 2 +-
gcc/tree-pass.h | 1 +
gcc/tree-switch-conversion.c | 604 +++----------------------
5 files changed, 72 insertions(+), 540 deletions(-)
diff --git a/gcc/passes.def b/gcc/passes.def
index 3ebcfc30349..050009464ea 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -317,6 +317,7 @@ along with GCC; see the file COPYING3. If not see
POP_INSERT_PASSES ()
NEXT_PASS (pass_simduid_cleanup);
NEXT_PASS (pass_lower_vector_ssa);
+ NEXT_PASS (pass_lower_switch);
NEXT_PASS (pass_cse_reciprocals);
NEXT_PASS (pass_sprintf_length, true);
NEXT_PASS (pass_reassoc, false /* insert_powi_p */);
@@ -362,6 +363,7 @@ along with GCC; see the file COPYING3. If not see
/* Lower remaining pieces of GIMPLE. */
NEXT_PASS (pass_lower_complex);
NEXT_PASS (pass_lower_vector_ssa);
+ NEXT_PASS (pass_lower_switch);
/* Perform simple scalar cleanup which is constant/copy propagation. */
NEXT_PASS (pass_ccp, true /* nonzero_p */);
NEXT_PASS (pass_post_ipa_warn);
@@ -397,6 +399,7 @@ along with GCC; see the file COPYING3. If not see
NEXT_PASS (pass_lower_vaarg);
NEXT_PASS (pass_lower_vector);
NEXT_PASS (pass_lower_complex_O0);
+ NEXT_PASS (pass_lower_switch_O0);
NEXT_PASS (pass_sancov_O0);
NEXT_PASS (pass_lower_switch);
NEXT_PASS (pass_asan_O0);
diff --git a/gcc/testsuite/gcc.dg/tree-prof/update-loopch.c b/gcc/testsuite/gcc.dg/tree-prof/update-loopch.c
index 73efc878ec0..15baada1081 100644
--- a/gcc/testsuite/gcc.dg/tree-prof/update-loopch.c
+++ b/gcc/testsuite/gcc.dg/tree-prof/update-loopch.c
@@ -1,4 +1,4 @@
-/* { dg-options "-O2 -fdump-ipa-profile-blocks-details -fdump-tree-switchlower-blocks-details" } */
+/* { dg-options "-O2 -fdump-ipa-profile-blocks-details -fdump-tree-switchlower1-blocks-details" } */
int max = 33333;
int a[8];
int
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c
index d4691fcf041..71fa3bfa2ca 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c
@@ -2,7 +2,7 @@
/* { dg-options "-O2 -fdump-tree-switchlower" } */
/* We scan for 2 switches as the dump file reports a transformation,
IL really contains just a single. */
-/* { dg-final { scan-tree-dump-times "switch \\(i_" 2 "switchlower" } } */
+/* { dg-final { scan-tree-dump-times "switch" 2 "switchlower1" } } */
void foo (void);
void bar (void);
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index 93a6a99eb7a..7625d1963ff 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -413,6 +413,7 @@ extern gimple_opt_pass *make_pass_strip_predict_hints (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_lower_complex_O0 (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_lower_complex (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_lower_switch (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_lower_switch_O0 (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_lower_vector (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_lower_vector_ssa (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_lower_omp (gcc::context *ctxt);
diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
index b0470ef1b5e..dc60b34f506 100644
--- a/gcc/tree-switch-conversion.c
+++ b/gcc/tree-switch-conversion.c
@@ -1691,9 +1691,6 @@ typedef case_node *case_node_ptr;
static basic_block emit_case_nodes (basic_block, tree, case_node_ptr,
basic_block, tree, profile_probability,
tree, hash_map<tree, tree> *);
-static bool node_has_low_bound (case_node_ptr, tree);
-static bool node_has_high_bound (case_node_ptr, tree);
-static bool node_is_bounded (case_node_ptr, tree);
/* Return the smallest number of different values for which it is best to use a
jump-table instead of a tree of conditional branches. */
@@ -2169,10 +2166,31 @@ try_switch_expansion (gswitch *stmt)
namespace {
-const pass_data pass_data_lower_switch =
+template <bool O0> class pass_lower_switch: public gimple_opt_pass
{
- GIMPLE_PASS, /* type */
- "switchlower", /* name */
+public:
+ pass_lower_switch (gcc::context *ctxt) : gimple_opt_pass (data, ctxt) {}
+
+ static const pass_data data;
+ opt_pass *
+ clone ()
+ {
+ return new pass_lower_switch<O0> (m_ctxt);
+ }
+
+ virtual bool
+ gate (function *)
+ {
+ return !O0 || !optimize;
+ }
+
+ virtual unsigned int execute (function *fun);
+}; // class pass_lower_switch
+
+template <bool O0>
+const pass_data pass_lower_switch<O0>::data = {
+ GIMPLE_PASS, /* type */
+ O0 ? "switchlower_O0" : "switchlower", /* name */
OPTGROUP_NONE, /* optinfo_flags */
TV_TREE_SWITCH_LOWERING, /* tv_id */
( PROP_cfg | PROP_ssa ), /* properties_required */
@@ -2182,21 +2200,9 @@ const pass_data pass_data_lower_switch =
TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */
};
-class pass_lower_switch : public gimple_opt_pass
-{
-public:
- pass_lower_switch (gcc::context *ctxt)
- : gimple_opt_pass (pass_data_lower_switch, ctxt)
- {}
-
- /* opt_pass methods: */
- virtual bool gate (function *) { return true; }
- virtual unsigned int execute (function *);
-
-}; // class pass_lower_switch
-
+template <bool O0>
unsigned int
-pass_lower_switch::execute (function *fun)
+pass_lower_switch<O0>::execute (function *fun)
{
basic_block bb;
bool expanded = false;
@@ -2234,33 +2240,14 @@ pass_lower_switch::execute (function *fun)
} // anon namespace
gimple_opt_pass *
-make_pass_lower_switch (gcc::context *ctxt)
+make_pass_lower_switch_O0 (gcc::context *ctxt)
{
- return new pass_lower_switch (ctxt);
+ return new pass_lower_switch<true> (ctxt);
}
-
-/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE.
- PROB is the probability of jumping to LABEL. */
-static basic_block
-do_jump_if_equal (basic_block bb, tree op0, tree op1, basic_block label_bb,
- profile_probability prob, hash_map<tree, tree> *phi_mapping)
+gimple_opt_pass *
+make_pass_lower_switch (gcc::context *ctxt)
{
- gcond *cond = gimple_build_cond (EQ_EXPR, op0, op1, NULL_TREE, NULL_TREE);
- gimple_stmt_iterator gsi = gsi_last_bb (bb);
- gsi_insert_before (&gsi, cond, GSI_SAME_STMT);
-
- gcc_assert (single_succ_p (bb));
-
- /* Make a new basic block where false branch will take place. */
- edge false_edge = split_block (bb, cond);
- false_edge->flags = EDGE_FALSE_VALUE;
- false_edge->probability = prob.invert ();
-
- edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
- fix_phi_operands_for_edge (true_edge, phi_mapping);
- true_edge->probability = prob;
-
- return false_edge->dest;
+ return new pass_lower_switch<false> (ctxt);
}
/* Generate code to compare X with Y so that the condition codes are
@@ -2323,28 +2310,7 @@ conditional_probability (profile_probability target_prob,
/* Emit step-by-step code to select a case for the value of INDEX.
The thus generated decision tree follows the form of the
case-node binary tree NODE, whose nodes represent test conditions.
- INDEX_TYPE is the type of the index of the switch.
-
- Care is taken to prune redundant tests from the decision tree
- by detecting any boundary conditions already checked by
- emitted rtx. (See node_has_high_bound, node_has_low_bound
- and node_is_bounded, above.)
-
- Where the test conditions can be shown to be redundant we emit
- an unconditional jump to the target code. As a further
- optimization, the subordinates of a tree node are examined to
- check for bounded nodes. In this case conditional and/or
- unconditional jumps as a result of the boundary check for the
- current node are arranged to target the subordinates associated
- code for out of bound conditions on the current node.
-
- We can assume that when control reaches the code generated here,
- the index value has already been compared with the parents
- of this node, and determined to be on the same side of each parent
- as this node is. Thus, if this node tests for the value 51,
- and a parent tested for 52, we don't need to consider
- the possibility of a value greater than 51. If another parent
- tests for the value 50, then this node need not test anything. */
+ INDEX_TYPE is the type of the index of the switch. */
static basic_block
emit_case_nodes (basic_block bb, tree index, case_node_ptr node,
@@ -2352,482 +2318,44 @@ emit_case_nodes (basic_block bb, tree index, case_node_ptr node,
profile_probability default_prob, tree index_type,
hash_map<tree, tree> *phi_mapping)
{
- /* If INDEX has an unsigned type, we must make unsigned branches. */
- profile_probability probability;
- profile_probability prob = node->prob, subtree_prob = node->subtree_prob;
-
- /* See if our parents have already tested everything for us.
- If they have, emit an unconditional jump for this node. */
- if (node_is_bounded (node, index_type))
- {
- emit_jump (bb, node->case_bb, phi_mapping);
- return NULL;
- }
-
- else if (tree_int_cst_equal (node->low, node->high))
- {
- probability = conditional_probability (prob, subtree_prob + default_prob);
- /* Node is single valued. First see if the index expression matches
- this node and then check our children, if any. */
- bb = do_jump_if_equal (bb, index, node->low, node->case_bb, probability,
- phi_mapping);
- /* Since this case is taken at this point, reduce its weight from
- subtree_weight. */
- subtree_prob -= prob;
- if (node->right != 0 && node->left != 0)
- {
- /* This node has children on both sides.
- Dispatch to one side or the other
- by comparing the index value with this node's value.
- If one subtree is bounded, check that one first,
- so we can avoid real branches in the tree. */
-
- if (node_is_bounded (node->right, index_type))
- {
- probability
- = conditional_probability (node->right->prob,
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
- node->right->case_bb, probability,
- phi_mapping);
- bb = emit_case_nodes (bb, index, node->left, default_bb,
- default_label, default_prob, index_type,
- phi_mapping);
- }
-
- else if (node_is_bounded (node->left, index_type))
- {
- probability
- = conditional_probability (node->left->prob,
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR,
- node->left->case_bb, probability,
- phi_mapping);
- bb = emit_case_nodes (bb, index, node->right, default_bb,
- default_label, default_prob, index_type,
- phi_mapping);
- }
-
- /* If both children are single-valued cases with no
- children, finish up all the work. This way, we can save
- one ordered comparison. */
- else if (tree_int_cst_equal (node->right->low, node->right->high)
- && node->right->left == 0 && node->right->right == 0
- && tree_int_cst_equal (node->left->low, node->left->high)
- && node->left->left == 0 && node->left->right == 0)
- {
- /* Neither node is bounded. First distinguish the two sides;
- then emit the code for one side at a time. */
-
- /* See if the value matches what the right hand side
- wants. */
- probability
- = conditional_probability (node->right->prob,
- subtree_prob + default_prob);
- bb = do_jump_if_equal (bb, index, node->right->low,
- node->right->case_bb, probability,
- phi_mapping);
-
- /* See if the value matches what the left hand side
- wants. */
- probability
- = conditional_probability (node->left->prob,
- subtree_prob + default_prob);
- bb = do_jump_if_equal (bb, index, node->left->low,
- node->left->case_bb, probability,
- phi_mapping);
- }
-
- else
- {
- /* Neither node is bounded. First distinguish the two sides;
- then emit the code for one side at a time. */
-
- basic_block test_bb = split_edge (single_succ_edge (bb));
- redirect_edge_succ (single_pred_edge (test_bb),
- single_succ_edge (bb)->dest);
-
- /* The default label could be reached either through the right
- subtree or the left subtree. Divide the probability
- equally. */
- probability
- = conditional_probability (node->right->subtree_prob
- + default_prob.apply_scale (1, 2),
- subtree_prob + default_prob);
- /* See if the value is on the right. */
- bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
- test_bb, probability, phi_mapping);
- default_prob = default_prob.apply_scale (1, 2);
-
- /* Value must be on the left.
- Handle the left-hand subtree. */
- bb = emit_case_nodes (bb, index, node->left, default_bb,
- default_label, default_prob, index_type,
- phi_mapping);
- /* If left-hand subtree does nothing,
- go to default. */
-
- if (bb && default_bb)
- emit_jump (bb, default_bb, phi_mapping);
-
- /* Code branches here for the right-hand subtree. */
- bb = emit_case_nodes (test_bb, index, node->right, default_bb,
- default_label, default_prob, index_type,
- phi_mapping);
- }
- }
- else if (node->right != 0 && node->left == 0)
- {
- /* Here we have a right child but no left so we issue a conditional
- branch to default and process the right child.
-
- Omit the conditional branch to default if the right child
- does not have any children and is single valued; it would
- cost too much space to save so little time. */
-
- if (node->right->right || node->right->left
- || !tree_int_cst_equal (node->right->low, node->right->high))
- {
- if (!node_has_low_bound (node, index_type))
- {
- probability
- = conditional_probability (default_prob.apply_scale (1, 2),
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR,
- default_bb, probability,
- phi_mapping);
- default_prob = default_prob.apply_scale (1, 2);
- }
-
- bb = emit_case_nodes (bb, index, node->right, default_bb,
- default_label, default_prob, index_type,
- phi_mapping);
- }
- else
- {
- probability
- = conditional_probability (node->right->subtree_prob,
- subtree_prob + default_prob);
- /* We cannot process node->right normally
- since we haven't ruled out the numbers less than
- this node's value. So handle node->right explicitly. */
- bb = do_jump_if_equal (bb, index, node->right->low,
- node->right->case_bb, probability,
- phi_mapping);
- }
- }
-
- else if (node->right == 0 && node->left != 0)
- {
- /* Just one subtree, on the left. */
- if (node->left->left || node->left->right
- || !tree_int_cst_equal (node->left->low, node->left->high))
- {
- if (!node_has_high_bound (node, index_type))
- {
- probability
- = conditional_probability (default_prob.apply_scale (1, 2),
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
- default_bb, probability,
- phi_mapping);
- default_prob = default_prob.apply_scale (1, 2);
- }
-
- bb = emit_case_nodes (bb, index, node->left, default_bb,
- default_label, default_prob, index_type,
- phi_mapping);
- }
- else
- {
- probability
- = conditional_probability (node->left->subtree_prob,
- subtree_prob + default_prob);
- /* We cannot process node->left normally
- since we haven't ruled out the numbers less than
- this node's value. So handle node->left explicitly. */
- do_jump_if_equal (bb, index, node->left->low, node->left->case_bb,
- probability, phi_mapping);
- }
- }
- }
- else
- {
- /* Node is a range. These cases are very similar to those for a single
- value, except that we do not start by testing whether this node
- is the one to branch to. */
-
- if (node->right != 0 && node->left != 0)
- {
- /* Node has subtrees on both sides.
- If the right-hand subtree is bounded,
- test for it first, since we can go straight there.
- Otherwise, we need to make a branch in the control structure,
- then handle the two subtrees. */
- basic_block test_bb = NULL;
-
- if (node_is_bounded (node->right, index_type))
- {
- /* Right hand node is fully bounded so we can eliminate any
- testing and branch directly to the target code. */
- probability
- = conditional_probability (node->right->subtree_prob,
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
- node->right->case_bb, probability,
- phi_mapping);
- }
- else
- {
- /* Right hand node requires testing.
- Branch to a label where we will handle it later. */
-
- test_bb = split_edge (single_succ_edge (bb));
- redirect_edge_succ (single_pred_edge (test_bb),
- single_succ_edge (bb)->dest);
-
- probability
- = conditional_probability (node->right->subtree_prob
- + default_prob.apply_scale (1, 2),
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
- test_bb, probability, phi_mapping);
- default_prob = default_prob.apply_scale (1, 2);
- }
-
- /* Value belongs to this node or to the left-hand subtree. */
-
- probability
- = conditional_probability (prob, subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR,
- node->case_bb, probability,
- phi_mapping);
-
- /* Handle the left-hand subtree. */
- bb = emit_case_nodes (bb, index, node->left, default_bb,
- default_label, default_prob, index_type,
+ /* If node is null, we are done. */
+ if (node == NULL)
+ return bb;
+
+ /* Branch to a label where we will handle it later. */
+ basic_block test_bb = split_edge (single_succ_edge (bb));
+ redirect_edge_succ (single_pred_edge (test_bb),
+ single_succ_edge (bb)->dest);
+
+ profile_probability probability
+ = node->right ? node->right->subtree_prob : profile_probability::never ();
+ probability
+ = conditional_probability (probability + default_prob.apply_scale (1, 2),
+ node->subtree_prob + default_prob);
+ bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
+ test_bb, probability, phi_mapping);
+ default_prob = default_prob.apply_scale (1, 2);
+
+ /* Value belongs to this node or to the left-hand subtree. */
+ probability
+ = conditional_probability (node->prob, node->subtree_prob + default_prob);
+ bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR,
+ node->case_bb, probability,
phi_mapping);
- /* If right node had to be handled later, do that now. */
- if (test_bb)
- {
- /* If the left-hand subtree fell through,
- don't let it fall into the right-hand subtree. */
- if (bb && default_bb)
- emit_jump (bb, default_bb, phi_mapping);
-
- bb = emit_case_nodes (test_bb, index, node->right, default_bb,
- default_label, default_prob, index_type,
- phi_mapping);
- }
- }
-
- else if (node->right != 0 && node->left == 0)
- {
- /* Deal with values to the left of this node,
- if they are possible. */
- if (!node_has_low_bound (node, index_type))
- {
- probability
- = conditional_probability (default_prob.apply_scale (1, 2),
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR,
- default_bb, probability,
- phi_mapping);
- default_prob = default_prob.apply_scale (1, 2);
- }
-
- /* Value belongs to this node or to the right-hand subtree. */
-
- probability
- = conditional_probability (prob, subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->high, LE_EXPR,
- node->case_bb, probability,
- phi_mapping);
-
- bb = emit_case_nodes (bb, index, node->right, default_bb,
- default_label, default_prob, index_type,
- phi_mapping);
- }
-
- else if (node->right == 0 && node->left != 0)
- {
- /* Deal with values to the right of this node,
- if they are possible. */
- if (!node_has_high_bound (node, index_type))
- {
- probability
- = conditional_probability (default_prob.apply_scale (1, 2),
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
- default_bb, probability,
- phi_mapping);
- default_prob = default_prob.apply_scale (1, 2);
- }
-
- /* Value belongs to this node or to the left-hand subtree. */
+ /* Handle the left-hand subtree. */
+ bb = emit_case_nodes (bb, index, node->left, default_bb,
+ default_label, default_prob, index_type,
+ phi_mapping);
- probability
- = conditional_probability (prob, subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR,
- node->case_bb, probability,
- phi_mapping);
-
- bb = emit_case_nodes (bb, index, node->left, default_bb,
- default_label, default_prob, index_type,
- phi_mapping);
- }
-
- else
- {
- /* Node has no children so we check low and high bounds to remove
- redundant tests. Only one of the bounds can exist,
- since otherwise this node is bounded--a case tested already. */
- bool high_bound = node_has_high_bound (node, index_type);
- bool low_bound = node_has_low_bound (node, index_type);
-
- if (!high_bound && low_bound)
- {
- probability
- = conditional_probability (default_prob,
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
- default_bb, probability,
- phi_mapping);
- }
-
- else if (!low_bound && high_bound)
- {
- probability
- = conditional_probability (default_prob,
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR,
- default_bb, probability,
- phi_mapping);
- }
- else if (!low_bound && !high_bound)
- {
- tree lhs, rhs;
- generate_range_test (bb, index, node->low, node->high,
- &lhs, &rhs);
- probability
- = conditional_probability (default_prob,
- subtree_prob + default_prob);
- bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR,
- default_bb, probability,
- phi_mapping);
- }
+ /* If the left-hand subtree fell through,
+ don't let it fall into the right-hand subtree. */
+ if (default_bb)
+ emit_jump (bb, default_bb, phi_mapping);
- emit_jump (bb, node->case_bb, phi_mapping);
- return NULL;
- }
- }
+ bb = emit_case_nodes (test_bb, index, node->right, default_bb,
+ default_label, default_prob, index_type,
+ phi_mapping);
return bb;
}
-
-/* Search the parent sections of the case node tree
- to see if a test for the lower bound of NODE would be redundant.
- INDEX_TYPE is the type of the index expression.
-
- The instructions to generate the case decision tree are
- output in the same order as nodes are processed so it is
- known that if a parent node checks the range of the current
- node minus one that the current node is bounded at its lower
- span. Thus the test would be redundant. */
-
-static bool
-node_has_low_bound (case_node_ptr node, tree index_type)
-{
- tree low_minus_one;
- case_node_ptr pnode;
-
- /* If the lower bound of this node is the lowest value in the index type,
- we need not test it. */
-
- if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
- return true;
-
- /* If this node has a left branch, the value at the left must be less
- than that at this node, so it cannot be bounded at the bottom and
- we need not bother testing any further. */
-
- if (node->left)
- return false;
-
- low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low), node->low,
- build_int_cst (TREE_TYPE (node->low), 1));
-
- /* If the subtraction above overflowed, we can't verify anything.
- Otherwise, look for a parent that tests our value - 1. */
-
- if (!tree_int_cst_lt (low_minus_one, node->low))
- return false;
-
- for (pnode = node->parent; pnode; pnode = pnode->parent)
- if (tree_int_cst_equal (low_minus_one, pnode->high))
- return true;
-
- return false;
-}
-
-/* Search the parent sections of the case node tree
- to see if a test for the upper bound of NODE would be redundant.
- INDEX_TYPE is the type of the index expression.
-
- The instructions to generate the case decision tree are
- output in the same order as nodes are processed so it is
- known that if a parent node checks the range of the current
- node plus one that the current node is bounded at its upper
- span. Thus the test would be redundant. */
-
-static bool
-node_has_high_bound (case_node_ptr node, tree index_type)
-{
- tree high_plus_one;
- case_node_ptr pnode;
-
- /* If there is no upper bound, obviously no test is needed. */
-
- if (TYPE_MAX_VALUE (index_type) == NULL)
- return true;
-
- /* If the upper bound of this node is the highest value in the type
- of the index expression, we need not test against it. */
-
- if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
- return true;
-
- /* If this node has a right branch, the value at the right must be greater
- than that at this node, so it cannot be bounded at the top and
- we need not bother testing any further. */
-
- if (node->right)
- return false;
-
- high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high), node->high,
- build_int_cst (TREE_TYPE (node->high), 1));
-
- /* If the addition above overflowed, we can't verify anything.
- Otherwise, look for a parent that tests our value + 1. */
-
- if (!tree_int_cst_lt (node->high, high_plus_one))
- return false;
-
- for (pnode = node->parent; pnode; pnode = pnode->parent)
- if (tree_int_cst_equal (high_plus_one, pnode->low))
- return true;
-
- return false;
-}
-
-/* Search the parent sections of the
- case node tree to see if both tests for the upper and lower
- bounds of NODE would be redundant. */
-
-static bool
-node_is_bounded (case_node_ptr node, tree index_type)
-{
- return (node_has_low_bound (node, index_type)
- && node_has_high_bound (node, index_type));
-}
--
2.16.3
