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 ();

Reply via email to