[PATCH, Pointer Bounds Checker 14/x] Passes [15/n] Optimize redundant checks

[Ilya Enkovich]

Hi,

This patch adds removal of redundant (covered by other) checks into checker optimization.

Thanks,
Ilya
--
2014-10-08 Ilya Enkovich <***@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 ();

[Jeff Law]

Post by Ilya Enkovich
Hi,
This patch adds removal of redundant (covered by other) checks into checker optimization.
Thanks,
Ilya
--
* tree-chkp.c (chkp_compare_checks): New.
(chkp_remove_redundant_checks): New.
(chkp_opt_execute): Run redundant checks removal
algorithm.

Wouldn't pure removal be better modeled in existing optimizers? DOM
would seem to be a natural fit?

Similarly, isn't the swapping very similar to a reverse DOM walk
DSE-like optimizer?

Deferring further review until those questions are answered?

jeff