[Pointer,Bounds,Checker,14/x] Passes [13/n] Optimize bounds intersections

diff --git a/gcc/testsuite/gcc.target/i386/chkp-remove-bndint-1.c b/gcc/testsuite/gcc.target/i386/chkp-remove-bndint-1.c
new file mode 100644
index 0000000..db71004
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/chkp-remove-bndint-1.c
@@ -0,0 +1,17 @@ 
+/* { dg-do compile } */
+/* { dg-options "-fcheck-pointer-bounds -mmpx -O2 -fdump-tree-optimized" } */
+/* { dg-final { scan-tree-dump-not "bndint" "optimized" } } */
+
+
+struct S
+{
+  int a;
+  int b;
+  int c;
+};
+
+int test (struct S *ps)
+{
+  int *pi = &ps->b;
+  return *pi;
+}
diff --git a/gcc/testsuite/gcc.target/i386/chkp-remove-bndint-2.c b/gcc/testsuite/gcc.target/i386/chkp-remove-bndint-2.c
new file mode 100644
index 0000000..c97ac27
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/chkp-remove-bndint-2.c
@@ -0,0 +1,17 @@ 
+/* { dg-do compile } */
+/* { dg-options "-fcheck-pointer-bounds -mmpx -O2 -fdump-tree-optimized -Wchkp" } */
+/* { dg-final { scan-tree-dump-not "bndint" "optimized" } } */
+
+
+struct S
+{
+  int a;
+  int b;
+  int c;
+};
+
+int test (struct S *ps)
+{
+  int *pi = &ps->b;
+  return *(pi + 1); /* { dg-warning "memory access check always fail" "" } */
+}
diff --git a/gcc/tree-chkp-opt.c b/gcc/tree-chkp-opt.c
index 56315c0..b3b7295 100644
--- a/gcc/tree-chkp-opt.c
+++ b/gcc/tree-chkp-opt.c
@@ -448,6 +448,336 @@  chkp_fill_check_info (gimple stmt, struct check_info *ci)
   ci->stmt = stmt;
 }
 
+/* Release structures holding check information
+   for current function.  */
+static void
+chkp_release_check_info (void)
+{
+  unsigned int n, m;
+
+  if (check_infos.exists ())
+    {
+      for (n = 0; n < check_infos.length (); n++)
+	{
+	  for (m = 0; m < check_infos[n].checks.length (); m++)
+	    if (check_infos[n].checks[m].addr.pol.exists ())
+	      check_infos[n].checks[m].addr.pol.release ();
+	  check_infos[n].checks.release ();
+	}
+      check_infos.release ();
+    }
+}
+
+/* Create structures to hold check information
+   for current function.  */
+static void
+chkp_init_check_info (void)
+{
+  struct bb_checks empty_bbc;
+  int n;
+
+  empty_bbc.checks = vNULL;
+
+  chkp_release_check_info ();
+
+  check_infos.create (last_basic_block_for_fn (cfun));
+  for (n = 0; n < last_basic_block_for_fn (cfun); n++)
+    {
+      check_infos.safe_push (empty_bbc);
+      check_infos.last ().checks.create (0);
+    }
+}
+
+/* Find all checks in current function and store info about them
+   in check_infos.  */
+static void
+chkp_gather_checks_info (void)
+{
+  basic_block bb;
+  gimple_stmt_iterator i;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "Gathering information about checks...\n");
+
+  chkp_init_check_info ();
+
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      struct bb_checks *bbc = &check_infos[bb->index];
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Searching checks in BB%d...\n", bb->index);
+
+      for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
+        {
+	  gimple stmt = gsi_stmt (i);
+
+	  if (gimple_code (stmt) != GIMPLE_CALL)
+	    continue;
+
+	  if (gimple_call_fndecl (stmt) == chkp_checkl_fndecl
+	      || gimple_call_fndecl (stmt) == chkp_checku_fndecl)
+	    {
+	      struct check_info ci;
+
+	      chkp_fill_check_info (stmt, &ci);
+	      bbc->checks.safe_push (ci);
+
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		{
+		  fprintf (dump_file, "Adding check information:\n");
+		  fprintf (dump_file, "  bounds: ");
+		  print_generic_expr (dump_file, ci.bounds, 0);
+		  fprintf (dump_file, "\n  address: ");
+		  chkp_print_addr (ci.addr);
+		  fprintf (dump_file, "\n  check: ");
+		  print_gimple_stmt (dump_file, stmt, 0, 0);
+		}
+	    }
+	}
+    }
+}
+
+/* Return 1 if check CI against BOUNDS always pass,
+   -1 if check CI against BOUNDS always fails and
+   0 if we cannot compute check result.  */
+static int
+chkp_get_check_result (struct check_info *ci, tree bounds)
+{
+  gimple bnd_def;
+  address_t bound_val;
+  int sign, res = 0;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Trying to compute result of the check\n");
+      fprintf (dump_file, "  check: ");
+      print_gimple_stmt (dump_file, ci->stmt, 0, 0);
+      fprintf (dump_file, "  address: ");
+      chkp_print_addr (ci->addr);
+      fprintf (dump_file, "\n  bounds: ");
+      print_generic_expr (dump_file, bounds, 0);
+      fprintf (dump_file, "\n");
+    }
+
+  if (TREE_CODE (bounds) != SSA_NAME)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "  result: bounds tree code is not ssa_name\n");
+      return 0;
+    }
+
+  bnd_def = SSA_NAME_DEF_STMT (bounds);
+  /* Currently we handle cases when bounds are result of bndmk
+     or loaded static bounds var.  */
+  if (gimple_code (bnd_def) == GIMPLE_CALL
+      && gimple_call_fndecl (bnd_def) == chkp_bndmk_fndecl)
+    {
+      bound_val.pol.create (0);
+      chkp_collect_value (gimple_call_arg (bnd_def, 0), bound_val);
+      if (ci->type == CHECK_UPPER_BOUND)
+	{
+	  address_t size_val;
+	  size_val.pol.create (0);
+	  chkp_collect_value (gimple_call_arg (bnd_def, 1), size_val);
+	  chkp_add_addr_addr (bound_val, size_val);
+	  size_val.pol.release ();
+	  chkp_add_addr_item (bound_val, integer_minus_one_node, NULL);
+	}
+    }
+  else if (gimple_code (bnd_def) == GIMPLE_ASSIGN
+	   && gimple_assign_rhs1 (bnd_def) == chkp_get_zero_bounds_var ())
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "  result: always pass with zero bounds\n");
+      return 1;
+    }
+  else if (gimple_code (bnd_def) == GIMPLE_ASSIGN
+	   && gimple_assign_rhs1 (bnd_def) == chkp_get_none_bounds_var ())
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "  result: always fails with none bounds\n");
+      return -1;
+    }
+  else if (gimple_code (bnd_def) == GIMPLE_ASSIGN
+	   && TREE_CODE (gimple_assign_rhs1 (bnd_def)) == VAR_DECL)
+    {
+      tree bnd_var = gimple_assign_rhs1 (bnd_def);
+      tree var;
+      tree size;
+
+      if (!DECL_INITIAL (bnd_var)
+	  || DECL_INITIAL (bnd_var) == error_mark_node)
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "  result: cannot compute bounds\n");
+	  return 0;
+	}
+
+      gcc_assert (TREE_CODE (DECL_INITIAL (bnd_var)) == ADDR_EXPR);
+      var = TREE_OPERAND (DECL_INITIAL (bnd_var), 0);
+
+      bound_val.pol.create (0);
+      chkp_collect_value (DECL_INITIAL (bnd_var), bound_val);
+      if (ci->type == CHECK_UPPER_BOUND)
+	{
+	  if (TREE_CODE (var) == VAR_DECL)
+	    {
+	      if (DECL_SIZE (var)
+		  && !chkp_variable_size_type (TREE_TYPE (var)))
+		size = DECL_SIZE_UNIT (var);
+	      else
+		{
+		  if (dump_file && (dump_flags & TDF_DETAILS))
+		    fprintf (dump_file, "  result: cannot compute bounds\n");
+		  return 0;
+		}
+	    }
+	  else
+	    {
+	      gcc_assert (TREE_CODE (var) == STRING_CST);
+	      size = build_int_cst (size_type_node,
+				    TREE_STRING_LENGTH (var));
+	    }
+
+	  address_t size_val;
+	  size_val.pol.create (0);
+	  chkp_collect_value (size, size_val);
+	  chkp_add_addr_addr (bound_val, size_val);
+	  size_val.pol.release ();
+	  chkp_add_addr_item (bound_val, integer_minus_one_node, NULL);
+	}
+    }
+  else
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "  result: cannot compute bounds\n");
+      return 0;
+    }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "  bound value: ");
+      chkp_print_addr (bound_val);
+      fprintf (dump_file, "\n");
+    }
+
+  chkp_sub_addr_addr (bound_val, ci->addr);
+
+  if (!chkp_is_constant_addr (bound_val, &sign))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "  result: cannot compute result\n");
+
+      res = 0;
+    }
+  else if (sign == 0
+	   || (ci->type == CHECK_UPPER_BOUND && sign > 0)
+	   || (ci->type == CHECK_LOWER_BOUND && sign < 0))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "  result: always pass\n");
+
+      res = 1;
+    }
+  else
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "  result: always fail\n");
+
+      res = -1;
+    }
+
+  bound_val.pol.release ();
+
+  return res;
+}
+
+/* For bounds used in CI check if bounds are produced by
+   intersection and we may use outer bounds instead.  If
+   transformation is possible then fix check statement and
+   recompute its info.  */
+static void
+chkp_use_outer_bounds_if_possible (struct check_info *ci)
+{
+  gimple bnd_def;
+  tree bnd1, bnd2, bnd_res = NULL;
+  int check_res1, check_res2;
+
+  if (TREE_CODE (ci->bounds) != SSA_NAME)
+    return;
+
+  bnd_def = SSA_NAME_DEF_STMT (ci->bounds);
+  if (gimple_code (bnd_def) != GIMPLE_CALL
+      || gimple_call_fndecl (bnd_def) != chkp_intersect_fndecl)
+    return;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Check if bounds intersection is redundant: \n");
+      fprintf (dump_file, "  check: ");
+      print_gimple_stmt (dump_file, ci->stmt, 0, 0);
+      fprintf (dump_file, "  intersection: ");
+      print_gimple_stmt (dump_file, bnd_def, 0, 0);
+      fprintf (dump_file, "\n");
+    }
+
+  bnd1 = gimple_call_arg (bnd_def, 0);
+  bnd2 = gimple_call_arg (bnd_def, 1);
+
+  check_res1 = chkp_get_check_result (ci, bnd1);
+  check_res2 = chkp_get_check_result (ci, bnd2);
+  if (check_res1 == 1)
+    bnd_res = bnd2;
+  else if (check_res1 == -1)
+    bnd_res = bnd1;
+  else if (check_res2 == 1)
+    bnd_res = bnd1;
+  else if (check_res2 == -1)
+    bnd_res = bnd2;
+
+  if (bnd_res)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "  action: use ");
+	  print_generic_expr (dump_file, bnd2, 0);
+	  fprintf (dump_file, " instead of ");
+	  print_generic_expr (dump_file, ci->bounds, 0);
+	  fprintf (dump_file, "\n");
+	}
+
+      ci->bounds = bnd_res;
+      gimple_call_set_arg (ci->stmt, 1, bnd_res);
+      update_stmt (ci->stmt);
+      chkp_fill_check_info (ci->stmt, ci);
+    }
+}
+
+/*  Try to find checks whose bounds were produced by intersection
+    which does not affect check result.  In such check outer bounds
+    are used instead.  It allows to remove excess intersections
+    and helps to compare checks.  */
+static void
+chkp_remove_excess_intersections (void)
+{
+  basic_block bb;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "Searching for redundant bounds intersections...\n");
+
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      struct bb_checks *bbc = &check_infos[bb->index];
+      unsigned int no;
+
+      /* Iterate through all found checks in BB.  */
+      for (no = 0; no < bbc->checks.length (); no++)
+	if (bbc->checks[no].stmt)
+	  chkp_use_outer_bounds_if_possible (&bbc->checks[no]);
+    }
+}
+
 /* Return fast version of string function FNCODE.  */
 static tree
 chkp_get_nobnd_fndecl (enum built_in_function fncode)
@@ -711,6 +1041,12 @@  chkp_opt_execute (void)
      and thus we put it before checks search.  */
   chkp_optimize_string_function_calls ();
 
+  chkp_gather_checks_info ();
+
+  chkp_remove_excess_intersections ();
+
+  chkp_release_check_info ();
+
   chkp_opt_fini ();
 
   return 0;