This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH, Pointer Bounds Checker 14/x] Passes [16/n] Reduce bounds lifetime


On 09 Oct 11:32, Jeff Law wrote:
> On 10/08/14 13:24, Ilya Enkovich wrote:
> >Hi,
> >
> >This patch adds a bounds lifetime reduction into checker optimization.
> >
> >Thanks,
> >Ilya
> >--
> >2014-10-08  Ilya Enkovich  <ilya.enkovich@intel.com>
> >
> >	* tree-chkp.c (chkp_reduce_bounds_lifetime): New.
> >	(chkp_opt_execute): Run bounds lifetime reduction
> >	algorithm.
> Basic tests & pull into a file with the other optimization work.
> 
> How expensive is nearest_common_dominator?  Would it make more sense
> to use something like the concept of an anticipated expression from
> LCM?

nearest_common_dominator searches for the nearest common ancestor in a tree so I expect it to be not more expensive than O(h), h - height of a tree.  I suppose LCM would be more efficient in case of many processed bounds and many their uses.  But this optimization is only for INIT bounds, NULL bounds and bounds for statically allocated objects.  Thus their usage is quite limited.

> 
> 
> 
> 
> >+      /* Check we do not increase other values lifetime.  */
> >+      FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
> >+	{
> >+	  op = USE_FROM_PTR (use_p);
> >+
> >+	  if (TREE_CODE (op) == SSA_NAME
> >+	      && gimple_code (SSA_NAME_DEF_STMT (op)) != GIMPLE_NOP)
> >+	    deps = true;
> Might as well break out of the FOR_EACH_PHI_OR_STMT_USE loop here.
> Note that some of our iterators have special mechanisms to break out
> of the loop, but my recollection is those are for the immediate use
> iterators to ensure the marker is removed.
> 
> Code is probably OK if LCM/anticipated isn't reasonable and the
> above issues are dealt with.
> 
> jeff
> 

Here is an updated version with break and testcase added.

Thanks,
Ilya
--
gcc/

2014-10-14  Ilya Enkovich  <ilya.enkovich@intel.com>

	* tree-chkp-opt.c (chkp_reduce_bounds_lifetime): New.
	(chkp_opt_execute): Run bounds lifetime reduction
	algorithm.

gcc/testsuite/

2014-10-14  Ilya Enkovich  <ilya.enkovich@intel.com>

	* gcc.target/i386/chkp-lifetime-1.c: New.


diff --git a/gcc/testsuite/gcc.target/i386/chkp-lifetime-1.c b/gcc/testsuite/gcc.target/i386/chkp-lifetime-1.c
new file mode 100644
index 0000000..bcecdd0
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/chkp-lifetime-1.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-fcheck-pointer-bounds -mmpx -O2 -fdump-tree-chkpopt-details" } */
+/* { dg-final { scan-tree-dump "Moving creation of \[^ \]+ down to its use" "chkpopt" } } */
+
+extern int arr[];
+
+int test (int i)
+{
+  int res;
+  if (i >= 0)
+    res = arr[i];
+  else
+    res = -i;
+  return res;
+}
diff --git a/gcc/tree-chkp-opt.c b/gcc/tree-chkp-opt.c
index b3ff433..37da035 100644
--- a/gcc/tree-chkp-opt.c
+++ b/gcc/tree-chkp-opt.c
@@ -1277,6 +1277,158 @@ chkp_optimize_string_function_calls (void)
     }
 }
 
+/* Intrumentation pass inserts most of bounds creation code
+   in the header of the function.  We want to move bounds
+   creation closer to bounds usage to reduce bounds lifetime.
+   We also try to avoid bounds creation code on paths where
+   bounds are not used.  */
+static void
+chkp_reduce_bounds_lifetime (void)
+{
+  basic_block bb = FALLTHRU_EDGE (ENTRY_BLOCK_PTR_FOR_FN (cfun))->dest;
+  gimple_stmt_iterator i;
+
+  for (i = gsi_start_bb (bb); !gsi_end_p (i); )
+    {
+      gimple dom_use, use_stmt, stmt = gsi_stmt (i);
+      basic_block dom_bb;
+      ssa_op_iter iter;
+      imm_use_iterator use_iter;
+      use_operand_p use_p;
+      tree op;
+      bool want_move = false;
+      bool deps = false;
+
+      if (gimple_code (stmt) == GIMPLE_CALL
+	  && gimple_call_fndecl (stmt) == chkp_bndmk_fndecl)
+	want_move = true;
+
+      if (gimple_code (stmt) == GIMPLE_ASSIGN
+	  && POINTER_BOUNDS_P (gimple_assign_lhs (stmt))
+	  && gimple_assign_rhs_code (stmt) == VAR_DECL)
+	want_move = true;
+
+      if (!want_move)
+	{
+	  gsi_next (&i);
+	  continue;
+	}
+
+      /* Check we do not increase other values lifetime.  */
+      FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
+	{
+	  op = USE_FROM_PTR (use_p);
+
+	  if (TREE_CODE (op) == SSA_NAME
+	      && gimple_code (SSA_NAME_DEF_STMT (op)) != GIMPLE_NOP)
+	    {
+	      deps = true;
+	      break;
+	    }
+	}
+
+      if (deps)
+	{
+	  gsi_next (&i);
+	  continue;
+	}
+
+      /* Check all usages of bounds.  */
+      if (gimple_code (stmt) == GIMPLE_CALL)
+	op = gimple_call_lhs (stmt);
+      else
+	{
+	  gcc_assert (gimple_code (stmt) == GIMPLE_ASSIGN);
+	  op = gimple_assign_lhs (stmt);
+	}
+
+      dom_use = NULL;
+      dom_bb = NULL;
+
+      FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, op)
+	{
+	  if (dom_bb &&
+	      dominated_by_p (CDI_DOMINATORS,
+			      dom_bb, gimple_bb (use_stmt)))
+	    {
+	      dom_use = use_stmt;
+	      dom_bb = NULL;
+	    }
+	  else if (dom_bb)
+	    dom_bb = nearest_common_dominator (CDI_DOMINATORS, dom_bb,
+					       gimple_bb (use_stmt));
+	  else if (!dom_use)
+	    dom_use = use_stmt;
+	  else if (stmt_dominates_stmt_p (use_stmt, dom_use))
+	    dom_use = use_stmt;
+	  else if (!stmt_dominates_stmt_p (dom_use, use_stmt)
+		   /* If dom_use and use_stmt are PHI nodes in one BB
+		      then it is OK to keep any of them as dom_use.
+		      stmt_dominates_stmt_p returns 0 for such
+		      combination, so check it here manually.  */
+		   && (gimple_code (dom_use) != GIMPLE_PHI
+		       || gimple_code (use_stmt) != GIMPLE_PHI
+		       || gimple_bb (use_stmt) != gimple_bb (dom_use))
+		   )
+	    {
+	      dom_bb = nearest_common_dominator (CDI_DOMINATORS,
+						 gimple_bb (use_stmt),
+						 gimple_bb (dom_use));
+	      dom_use = NULL;
+	    }
+	}
+
+      /* In case there is a single use, just move bounds
+	 creation to the use.  */
+      if (dom_use || dom_bb)
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "Moving creation of ");
+	      print_generic_expr (dump_file, op, 0);
+	      fprintf (dump_file, " down to its use.\n");
+	    }
+
+	  if (dom_use && gimple_code (dom_use) == GIMPLE_PHI)
+	    {
+	      dom_bb = get_immediate_dominator (CDI_DOMINATORS,
+						gimple_bb (dom_use));
+	      dom_use = NULL;
+	    }
+
+	  if (dom_bb == bb
+	      || (dom_use && gimple_bb (dom_use) == bb))
+	    {
+		  if (dump_file && (dump_flags & TDF_DETAILS))
+		    fprintf (dump_file, "Cannot move statement bacause there is no "
+			     "suitable dominator block other than entry block.\n");
+
+		  gsi_next (&i);
+	    }
+	  else
+	    {
+	      if (dom_bb)
+		{
+		  gimple_stmt_iterator last = gsi_last_bb (dom_bb);
+		  if (!gsi_end_p (last) && stmt_ends_bb_p (gsi_stmt (last)))
+		    gsi_move_before (&i, &last);
+		  else
+		    gsi_move_after (&i, &last);
+		}
+	      else
+		{
+		  gimple_stmt_iterator gsi = gsi_for_stmt (dom_use);
+		  gsi_move_before (&i, &gsi);
+		}
+
+	      update_stmt (stmt);
+	    }
+	}
+      else
+	gsi_next (&i);
+    }
+}
+
 /* Initilize checker optimization pass.  */
 static void
 chkp_opt_init (void)
@@ -1318,6 +1470,8 @@ chkp_opt_execute (void)
 
   chkp_remove_redundant_checks ();
 
+  chkp_reduce_bounds_lifetime ();
+
   chkp_release_check_info ();
 
   chkp_opt_fini ();


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]