From eb63c01f65d475f7f05d1979f66c1c41faa61da9 Mon Sep 17 00:00:00 2001 From: Martin Liska Date: Fri, 18 May 2018 10:43:19 +0200 Subject: [PATCH] Radically simplify emission of balanced tree for switch statements. 2018-05-18 Martin Liska * 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. 2018-05-18 Martin Liska * gcc.dg/tree-ssa/vrp104.c: Adjust dump file that is scanned. * gcc.dg/tree-prof/update-loopch.c: Likewise. From-SVN: r260350 --- gcc/ChangeLog | 16 + gcc/passes.def | 3 + gcc/testsuite/ChangeLog | 5 + .../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 ++---------------- 7 files changed, 93 insertions(+), 540 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index dc5483625df..8215995cb14 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,19 @@ +2018-05-18 Martin Liska + + * 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. + 2018-05-18 Martin Liska * dbgcnt.c (limit_low): Renamed from limit. 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/ChangeLog b/gcc/testsuite/ChangeLog index 01b897a33e4..765e08cf4c0 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2018-05-18 Martin Liska + + * gcc.dg/tree-ssa/vrp104.c: Adjust dump file that is scanned. + * gcc.dg/tree-prof/update-loopch.c: Likewise. + 2018-05-18 Martin Liska * gcc.dg/ipa/ipa-icf-39.c: New test. 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 *); -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 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 (m_ctxt); + } + + virtual bool + gate (function *) + { + return !O0 || !optimize; + } + + virtual unsigned int execute (function *fun); +}; // class pass_lower_switch + +template +const pass_data pass_lower_switch::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 unsigned int -pass_lower_switch::execute (function *fun) +pass_lower_switch::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 (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 *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 (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 *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.30.2