Hi, This patch adds removal of redundant (covered by other) checks into checker optimization.
Thanks, Ilya -- 2014-10-08 Ilya Enkovich <ilya.enkov...@intel.com> * tree-chkp.c (chkp_compare_checks): New. (chkp_remove_redundant_checks): New. (chkp_opt_execute): Run redundant checks removal algorithm. diff --git a/gcc/tree-chkp.c b/gcc/tree-chkp.c index ade546b..37ab729 100644 --- a/gcc/tree-chkp.c +++ b/gcc/tree-chkp.c @@ -4972,6 +4972,211 @@ chkp_remove_constant_checks (void) } } +/* Compare two checks CI1 and CI2 to find redundant one. + CI1 is known to dominate CI2. POSTDOM indicated if + CI2 postdominateds CI1. + + Few conditions are checked to find redundant check: + 1. Checks has the same type + 2. Checks use the same bounds + 3. One check fail means other check fail + 4. Stronger check is always executed if weaker one is executed + + If redundant check is found it is removed. If removed check is CI1 + then CI2 is moved to CI1's position to avoid bound violation happened + before check is executed. */ +void +chkp_compare_checks (struct check_info *ci1, + struct check_info *ci2, + bool postdom) +{ + address_t delta; + int sign; + + if (ci1->type != ci2->type) + return; + + if (ci1->bounds != ci2->bounds) + return; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " Comparing checks...\n"); + fprintf (dump_file, " First check: "); + print_gimple_stmt (dump_file, ci1->stmt, 0, 0); + fprintf (dump_file, " Second check: "); + print_gimple_stmt (dump_file, ci2->stmt, 0, 0); + } + + delta.pol = ci1->addr.pol.copy (); + chkp_sub_addr_addr (delta, ci2->addr); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " Delta: "); + chkp_print_addr (delta); + fprintf (dump_file, "\n"); + } + + if (!chkp_is_constant_addr (delta, &sign)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " Action: skip (delta is not constant)\n"); + } + else + { + if (sign) + { + if ((sign > 0 && ci1->type == CHECK_UPPER_BOUND) + || (sign < 0 && ci1->type == CHECK_LOWER_BOUND)) + { + gimple_stmt_iterator i = gsi_for_stmt (ci2->stmt); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " Action: delete the second check\n"); + + gsi_remove (&i, true); + unlink_stmt_vdef (ci2->stmt); + release_defs (ci2->stmt); + ci2->stmt = NULL; + } + else if (postdom) + { + gimple_stmt_iterator i = gsi_for_stmt (ci2->stmt); + gimple_seq seq = NULL; + tree addr = gimple_call_arg (ci1->stmt, 0); + unsigned int n; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " Action: replace the first " + "check with the second one\n"); + + gsi_remove (&i, true); + unlink_stmt_vdef (ci2->stmt); + release_defs (ci2->stmt); + ci2->stmt = NULL; + + for (n = 0; n < delta.pol.length (); n++) + if (delta.pol[n].var == NULL) + { + tree tmp = fold_build2 (MINUS_EXPR, + TREE_TYPE (delta.pol[n].cst), + integer_zero_node, + delta.pol[n].cst); + addr = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (addr), + addr, convert_to_ptrofftype (tmp)); + } + else if (integer_onep (delta.pol[n].cst)) + { + tree tmp = fold_build2 (MINUS_EXPR, + TREE_TYPE (delta.pol[n].var), + integer_zero_node, + delta.pol[n].var); + addr = build2 (POINTER_PLUS_EXPR, TREE_TYPE (addr), + addr, convert_to_ptrofftype (tmp)); + } + else if (tree_int_cst_compare (delta.pol[n].cst, + integer_minus_one_node) == 0) + addr = build2 (POINTER_PLUS_EXPR, TREE_TYPE (addr), + addr, convert_to_ptrofftype (delta.pol[n].var)); + else + { + tree tmp = fold_build2 (MULT_EXPR, + TREE_TYPE (delta.pol[n].var), + delta.pol[n].var, + delta.pol[n].cst); + tmp = fold_build2 (MINUS_EXPR, TREE_TYPE (tmp), + integer_zero_node, tmp); + addr = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (addr), + addr, convert_to_ptrofftype (tmp)); + } + + addr = force_gimple_operand (unshare_expr (addr), &seq, + true, NULL_TREE); + + i = gsi_for_stmt (ci1->stmt); + gsi_insert_seq_before (&i, seq, GSI_CONTINUE_LINKING); + gimple_call_set_arg (ci1->stmt, 0, addr); + update_stmt (ci1->stmt); + + ci1->addr.pol.release (); + chkp_fill_check_info (ci1->stmt, ci1); + } + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " Action: skip (the first check is " + "not post-dominanted by the second check)\n"); + } + } + else + { + gimple_stmt_iterator i = gsi_for_stmt (ci2->stmt); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + " Action: delete the second check (same addresses)\n"); + + gsi_remove (&i, true); + unlink_stmt_vdef (ci2->stmt); + release_defs (ci2->stmt); + ci2->stmt = NULL; + } + } + + delta.pol.release (); +} + +/* Here we try to find checks which are covered by other checks + and thus can be removed. To do it we simply find all pairs of + checks where the first check dominates the second one and + call chkp_compare_checks to find and remove redundant ones. */ +void +chkp_remove_redundant_checks (void) +{ + basic_block bb; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Searching for redundant checks...\n"); + + FOR_EACH_BB_FN (bb, cfun) + { + struct bb_checks *bbc = &check_infos[bb->index]; + unsigned int no; + + /* Iterate throw all found checks in BB. */ + for (no = 0; no < bbc->checks.length (); no++) + if (bbc->checks[no].stmt) + { + vec<basic_block> dom_bbs; + unsigned bb_no, other; + + /* Compare check with all other following checks in this BB. */ + for (other = no + 1; other < bbc->checks.length (); other++) + if (bbc->checks[other].stmt) + chkp_compare_checks (&bbc->checks[no], &bbc->checks[other], + true); + + /* Now compare with checks in BBs dominated by current one. */ + dom_bbs = get_all_dominated_blocks (CDI_DOMINATORS, bb); + for (bb_no = 0; bb_no < dom_bbs.length (); bb_no++) + { + struct bb_checks *dom_bbc = &check_infos[dom_bbs[bb_no]->index]; + + if (dom_bbs[bb_no] == bb) + continue; + + for (other = 0; other < dom_bbc->checks.length (); other++) + if (dom_bbc->checks[other].stmt) + chkp_compare_checks (&bbc->checks[no], + &dom_bbc->checks[other], + dominated_by_p (CDI_POST_DOMINATORS, bb, + dom_bbs[bb_no])); + } + } + } +} + /* Return fast version of string function FNCODE. */ tree chkp_get_nobnd_fndecl (enum built_in_function fncode) @@ -5257,6 +5462,8 @@ chkp_opt_execute (void) chkp_remove_constant_checks (); + chkp_remove_redundant_checks (); + chkp_release_check_info (); chkp_opt_fini ();