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 [11/n] Optimization helpers


On 10 Oct 10:14, Jeff Law wrote:
> On 10/10/14 08:24, Ilya Enkovich wrote:
> >On 09 Oct 12:09, Jeff Law wrote:
> >>On 10/08/14 13:16, Ilya Enkovich wrote:
> >>>Hi,
> >>>
> >>>This patch introduces structures and manipulation functions used by simple checker optimizations.  Structures are used to hold checks information - type of check and checked address in a polinomial form.
> >>>
> >>>Thanks,
> >>>Ilya
> >>>--
> >>>2014-10-08  Ilya Enkovich  <ilya.enkovich@intel.com>
> >>>
> >>>	* tree-chkp.c (check_type): New.
> >>>	(pol_item): New.
> >>>	(address_t): New.
> >>>	(check_info): New.
> >>>	(bb_checks): New.
> >>>	(chkp_pol_item_compare): New.
> >>>	(chkp_pol_find): New.
> >>>	(chkp_extend_const): New.
> >>>	(chkp_add_addr_item): New.
> >>>	(chkp_sub_addr_item): New.
> >>>	(chkp_add_addr_addr): New.
> >>>	(chkp_sub_addr_addr): New.
> >>>	(chkp_mult_addr): New.
> >>>	(chkp_is_constant_addr): New.
> >>>	(chkp_print_addr): New.
> >>>	(chkp_collect_addr_value): New.
> >>>	(chkp_collect_value): New.
> >>>	(chkp_fill_check_info): New.
> >>>
> >>>
> >>>+/* Find plynomial item in ADDR with var equal to VAR
> >>s/plynomial/polynomial/
> >>
> >>With nit fixed and functions moved into whatever new file gets
> >>created for the optimization work  this will be OK.
> >>jeff
> >
> >Thanks for review!  Here is a fixed version.
> >
> >Ilya
> >--
> >2014-10-10  Ilya Enkovich  <ilya.enkovich@intel.com>
> >
> >	* tree-chkp-opt.c: New.
> >	* Makefile.in (OBJS): Add tree-chkp-opt.o.
> >
> >
> >diff --git a/gcc/Makefile.in b/gcc/Makefile.in
> >index d8c8488..cd45b29 100644
> >--- a/gcc/Makefile.in
> >+++ b/gcc/Makefile.in
> >@@ -1389,6 +1389,7 @@ OBJS = \
> >  	tree-parloops.o \
> >  	tree-phinodes.o \
> >  	tree-chkp.o \
> >+	tree-chkp-opt.o \
> >  	tree-predcom.o \
> >  	tree-pretty-print.o \
> >  	tree-profile.o \
> >diff --git a/gcc/tree-chkp-opt.c b/gcc/tree-chkp-opt.c
> >new file mode 100644
> >index 0000000..103c4bb
> >--- /dev/null
> >+++ b/gcc/tree-chkp-opt.c
> >@@ -0,0 +1,463 @@
> >+/* Pointer Bounds Checker optimization pass.
> >+   Copyright (C) 2014 Free Software Foundation, Inc.
> >+   Contributed by Ilya Enkovich (ilya.enkovich@intel.com)
> >+
> >+This file is part of GCC.
> >+
> >+GCC is free software; you can redistribute it and/or modify it under
> >+the terms of the GNU General Public License as published by the Free
> >+Software Foundation; either version 3, or (at your option) any later
> >+version.
> >+
> >+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
> >+WARRANTY; without even the implied warranty of MERCHANTABILITY or
> >+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
> >+for more details.
> >+
> >+You should have received a copy of the GNU General Public License
> >+along with GCC; see the file COPYING3.  If not see
> >+<http://www.gnu.org/licenses/>.  */
> >+
> >+#include "config.h"
> >+#include "system.h"
> >+#include "coretypes.h"
> >+#include "tree-core.h"
> >+#include "stor-layout.h"
> >+#include "varasm.h"
> >+#include "tree.h"
> >+#include "target.h"
> >+#include "tree-iterator.h"
> >+#include "tree-cfg.h"
> >+#include "langhooks.h"
> >+#include "tree-pass.h"
> >+#include "hashtab.h"
> >+#include "diagnostic.h"
> >+#include "ggc.h"
> >+#include "output.h"
> >+#include "internal-fn.h"
> >+#include "is-a.h"
> >+#include "predict.h"
> >+#include "cfgloop.h"
> >+#include "stringpool.h"
> >+#include "tree-ssa-alias.h"
> >+#include "tree-ssanames.h"
> >+#include "tree-ssa-operands.h"
> >+#include "tree-ssa-address.h"
> >+#include "tree-ssa.h"
> >+#include "ipa-inline.h"
> >+#include "basic-block.h"
> >+#include "tree-ssa-loop-niter.h"
> >+#include "gimple-expr.h"
> >+#include "gimple.h"
> >+#include "tree-phinodes.h"
> >+#include "gimple-ssa.h"
> >+#include "ssa-iterators.h"
> >+#include "gimple-pretty-print.h"
> >+#include "gimple-iterator.h"
> >+#include "gimplify.h"
> >+#include "gimplify-me.h"
> >+#include "print-tree.h"
> >+#include "expr.h"
> >+#include "tree-ssa-propagate.h"
> >+#include "gimple-fold.h"
> >+#include "gimple-walk.h"
> >+#include "tree-dfa.h"
> >+#include "tree-chkp.h"
> Thanks.  Looks good.
> 
> As a follow-up, can you try to trim down what appear to be the
> over-zealous includes?   It's a minor thing, but we are trying to be
> a bit saner about that kind of stuff than we've been in the past.
> 
> If you've already done that, then, well, we've clearly still got a
> ways to go.  For example, I can't see why you'd need output.h here
> :-0
> 
> 
> Jeff

Thanks for review!  This includes list is from tree-chkp.c and surely is reducible.  I also revisited tree-chkp.c and removed few includes from there.  Here is a new version.

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

	* tree-chkp-opt.c: New.
	* Makefile.in (OBJS): Add tree-chkp-opt.o.


diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index d8c8488..cd45b29 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1389,6 +1389,7 @@ OBJS = \
 	tree-parloops.o \
 	tree-phinodes.o \
 	tree-chkp.o \
+	tree-chkp-opt.o \
 	tree-predcom.o \
 	tree-pretty-print.o \
 	tree-profile.o \
diff --git a/gcc/tree-chkp-opt.c b/gcc/tree-chkp-opt.c
new file mode 100644
index 0000000..08be848
--- /dev/null
+++ b/gcc/tree-chkp-opt.c
@@ -0,0 +1,447 @@
+/* Pointer Bounds Checker optimization pass.
+   Copyright (C) 2014 Free Software Foundation, Inc.
+   Contributed by Ilya Enkovich (ilya.enkovich@intel.com)
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tree-core.h"
+#include "tree.h"
+#include "target.h"
+#include "tree-cfg.h"
+#include "tree-pass.h"
+#include "is-a.h"
+#include "cfgloop.h"
+#include "stringpool.h"
+#include "tree-ssa-alias.h"
+#include "tree-ssanames.h"
+#include "tree-ssa-operands.h"
+#include "tree-ssa-address.h"
+#include "tree-ssa.h"
+#include "basic-block.h"
+#include "tree-ssa-loop-niter.h"
+#include "gimple-expr.h"
+#include "gimple.h"
+#include "tree-phinodes.h"
+#include "gimple-ssa.h"
+#include "ssa-iterators.h"
+#include "gimple-pretty-print.h"
+#include "gimple-iterator.h"
+#include "gimplify.h"
+#include "gimplify-me.h"
+#include "expr.h"
+#include "tree-chkp.h"
+
+enum check_type
+{
+  CHECK_LOWER_BOUND,
+  CHECK_UPPER_BOUND
+};
+
+struct pol_item
+{
+  tree cst;
+  tree var;
+};
+
+struct address_t
+{
+  vec<struct pol_item> pol;
+};
+
+/* Structure to hold check informtation.  */
+struct check_info
+{
+  /* Type of the check.  */
+  check_type type;
+  /* Address used for the check.  */
+  address_t addr;
+  /* Bounds used for the check.  */
+  tree bounds;
+  /* Check statement.  Can be NULL for removed checks.  */
+  gimple stmt;
+};
+
+/* Structure to hold checks information for BB.  */
+struct bb_checks
+{
+  vec<struct check_info, va_heap, vl_ptr> checks;
+};
+
+static void chkp_collect_value (tree ssa_name, address_t &res);
+
+#define chkp_bndmk_fndecl \
+  (targetm.builtin_chkp_function (BUILT_IN_CHKP_BNDMK))
+#define chkp_intersect_fndecl \
+  (targetm.builtin_chkp_function (BUILT_IN_CHKP_INTERSECT))
+#define chkp_checkl_fndecl \
+  (targetm.builtin_chkp_function (BUILT_IN_CHKP_BNDCL))
+#define chkp_checku_fndecl \
+  (targetm.builtin_chkp_function (BUILT_IN_CHKP_BNDCU))
+
+/* Comparator for pol_item structures I1 and I2 to be used
+   to find items with equal var.  Also used for polynomial
+   sorting.  */
+static int
+chkp_pol_item_compare (const void *i1, const void *i2)
+{
+  const struct pol_item *p1 = (const struct pol_item *)i1;
+  const struct pol_item *p2 = (const struct pol_item *)i2;
+
+  if (p1->var == p2->var)
+    return 0;
+  else if (p1->var > p2->var)
+    return 1;
+  else
+    return -1;
+}
+
+/* Find polynomial item in ADDR with var equal to VAR
+   and return its index.  Return -1 if item was not
+   found.  */
+static int
+chkp_pol_find (address_t &addr, tree var)
+{
+  int left = 0;
+  int right = addr.pol.length () - 1;
+  int n;
+
+  while (right >= left)
+    {
+      n = (left + right) / 2;
+
+      if (addr.pol[n].var == var
+	  || (var && addr.pol[n].var
+	      && TREE_CODE (var) == ADDR_EXPR
+	      && TREE_CODE (addr.pol[n].var) == ADDR_EXPR
+	      && TREE_OPERAND (var, 0) == TREE_OPERAND (addr.pol[n].var, 0)))
+	return n;
+      else if (addr.pol[n].var > var)
+	right = n - 1;
+      else
+	left = n + 1;
+    }
+
+  return -1;
+}
+
+/* Return constant CST extended to size type.  */
+static tree
+chkp_extend_const (tree cst)
+{
+  if (TYPE_PRECISION (TREE_TYPE (cst)) < TYPE_PRECISION (size_type_node))
+    return build_int_cst_type (size_type_node, tree_to_shwi (cst));
+
+  return cst;
+}
+
+/* Add polynomial item CST * VAR to ADDR.  */
+static void
+chkp_add_addr_item (address_t &addr, tree cst, tree var)
+{
+  int n = chkp_pol_find (addr, var);
+
+  cst = chkp_extend_const (cst);
+
+  if (n < 0)
+    {
+      struct pol_item item;
+      item.cst = cst;
+      item.var = var;
+
+      addr.pol.safe_push (item);
+      addr.pol.qsort (&chkp_pol_item_compare);
+    }
+  else
+    {
+      addr.pol[n].cst = fold_build2 (PLUS_EXPR, TREE_TYPE (addr.pol[n].cst),
+				     addr.pol[n].cst, cst);
+      if (TREE_CODE (addr.pol[n].cst) == INTEGER_CST
+	  && integer_zerop (addr.pol[n].cst))
+	addr.pol.ordered_remove (n);
+    }
+}
+
+/* Subtract polynomial item CST * VAR from ADDR.  */
+static void
+chkp_sub_addr_item (address_t &addr, tree cst, tree var)
+{
+  int n = chkp_pol_find (addr, var);
+
+  cst = chkp_extend_const (cst);
+
+  if (n < 0)
+    {
+      struct pol_item item;
+      item.cst = fold_build2 (MINUS_EXPR, TREE_TYPE (cst),
+			      integer_zero_node, cst);
+      item.var = var;
+
+      addr.pol.safe_push (item);
+      addr.pol.qsort (&chkp_pol_item_compare);
+    }
+  else
+    {
+      addr.pol[n].cst = fold_build2 (MINUS_EXPR, TREE_TYPE (addr.pol[n].cst),
+				     addr.pol[n].cst, cst);
+      if (TREE_CODE (addr.pol[n].cst) == INTEGER_CST
+	  && integer_zerop (addr.pol[n].cst))
+	addr.pol.ordered_remove (n);
+    }
+}
+
+/* Add address DELTA to ADDR.  */
+static void
+chkp_add_addr_addr (address_t &addr, address_t &delta)
+{
+  unsigned int i;
+  for (i = 0; i < delta.pol.length (); i++)
+    chkp_add_addr_item (addr, delta.pol[i].cst, delta.pol[i].var);
+}
+
+/* Subtract address DELTA from ADDR.  */
+static void
+chkp_sub_addr_addr (address_t &addr, address_t &delta)
+{
+  unsigned int i;
+  for (i = 0; i < delta.pol.length (); i++)
+    chkp_sub_addr_item (addr, delta.pol[i].cst, delta.pol[i].var);
+}
+
+/* Mutiply address ADDR by integer constant MULT.  */
+static void
+chkp_mult_addr (address_t &addr, tree mult)
+{
+  unsigned int i;
+  for (i = 0; i < addr.pol.length (); i++)
+    addr.pol[i].cst = fold_build2 (MULT_EXPR, TREE_TYPE (addr.pol[i].cst),
+				   addr.pol[i].cst, mult);
+}
+
+/* Return 1 if we may prove ADDR has a constant value with
+   determined sign, which is put into *SIGN.  Otherwise
+   return 0.  */
+static bool
+chkp_is_constant_addr (const address_t &addr, int *sign)
+{
+  *sign = 0;
+
+  if (addr.pol.length () == 0)
+    return true;
+  else if (addr.pol.length () > 1)
+    return false;
+  else if (addr.pol[0].var)
+    return false;
+  else if (integer_zerop (addr.pol[0].cst))
+    *sign = 0;
+  else if  (tree_int_cst_sign_bit (addr.pol[0].cst))
+    *sign = -1;
+  else
+    *sign = 1;
+
+  return true;
+}
+
+/* Dump ADDR into dump_file.  */
+static void
+chkp_print_addr (const address_t &addr)
+{
+  unsigned int n = 0;
+  for (n = 0; n < addr.pol.length (); n++)
+    {
+      if (n > 0)
+	fprintf (dump_file, " + ");
+
+      if (addr.pol[n].var == NULL_TREE)
+	print_generic_expr (dump_file, addr.pol[n].cst, 0);
+      else
+	{
+	  if (TREE_CODE (addr.pol[n].cst) != INTEGER_CST
+	      || !integer_onep (addr.pol[n].cst))
+	    {
+	      print_generic_expr (dump_file, addr.pol[n].cst, 0);
+	      fprintf (dump_file, " * ");
+	    }
+	  print_generic_expr (dump_file, addr.pol[n].var, 0);
+	}
+    }
+}
+
+/* Compute value of PTR and put it into address RES.
+   PTR has to be ADDR_EXPR.  */
+static void
+chkp_collect_addr_value (tree ptr, address_t &res)
+{
+  tree obj = TREE_OPERAND (ptr, 0);
+  address_t addr;
+
+  switch (TREE_CODE (obj))
+    {
+    case INDIRECT_REF:
+      chkp_collect_value (TREE_OPERAND (obj, 0), res);
+      break;
+
+    case MEM_REF:
+      chkp_collect_value (TREE_OPERAND (obj, 0), res);
+      addr.pol.create (0);
+      chkp_collect_value (TREE_OPERAND (obj, 1), addr);
+      chkp_add_addr_addr (res, addr);
+      addr.pol.release ();
+      break;
+
+    case ARRAY_REF:
+      chkp_collect_value (build_fold_addr_expr (TREE_OPERAND (obj, 0)), res);
+      addr.pol.create (0);
+      chkp_collect_value (TREE_OPERAND (obj, 1), addr);
+      chkp_mult_addr (addr, array_ref_element_size (obj));
+      chkp_add_addr_addr (res, addr);
+      addr.pol.release ();
+      break;
+
+    case COMPONENT_REF:
+      {
+	tree str = TREE_OPERAND (obj, 0);
+	tree field = TREE_OPERAND (obj, 1);
+	chkp_collect_value (build_fold_addr_expr (str), res);
+	addr.pol.create (0);
+	chkp_collect_value (component_ref_field_offset (obj), addr);
+	chkp_add_addr_addr (res, addr);
+	addr.pol.release ();
+	if (DECL_FIELD_BIT_OFFSET (field))
+	  {
+	    addr.pol.create (0);
+	    chkp_collect_value (fold_build2 (TRUNC_DIV_EXPR, size_type_node,
+					     DECL_FIELD_BIT_OFFSET (field),
+					     size_int (BITS_PER_UNIT)),
+			   addr);
+	    chkp_add_addr_addr (res, addr);
+	    addr.pol.release ();
+	  }
+      }
+      break;
+
+    default:
+      chkp_add_addr_item (res, integer_one_node, ptr);
+      break;
+    }
+}
+
+/* Compute value of PTR and put it into address RES.  */
+static void
+chkp_collect_value (tree ptr, address_t &res)
+{
+  gimple def_stmt;
+  enum gimple_code code;
+  enum tree_code rhs_code;
+  address_t addr;
+  tree rhs1;
+
+  if (TREE_CODE (ptr) == INTEGER_CST)
+    {
+      chkp_add_addr_item (res, ptr, NULL);
+      return;
+    }
+  else if (TREE_CODE (ptr) == ADDR_EXPR)
+    {
+      chkp_collect_addr_value (ptr, res);
+      return;
+    }
+  else if (TREE_CODE (ptr) != SSA_NAME)
+    {
+      chkp_add_addr_item (res, integer_one_node, ptr);
+      return;
+    }
+
+  /* Now we handle the case when polynomial is computed
+     for SSA NAME.  */
+  def_stmt = SSA_NAME_DEF_STMT (ptr);
+  code = gimple_code (def_stmt);
+
+  /* Currently we do not walk through statements other
+     than assignment.  */
+  if (code != GIMPLE_ASSIGN)
+    {
+      chkp_add_addr_item (res, integer_one_node, ptr);
+      return;
+    }
+
+  rhs_code = gimple_assign_rhs_code (def_stmt);
+  rhs1 = gimple_assign_rhs1 (def_stmt);
+
+  switch (rhs_code)
+    {
+    case SSA_NAME:
+    case INTEGER_CST:
+    case ADDR_EXPR:
+      chkp_collect_value (rhs1, res);
+      break;
+
+    case PLUS_EXPR:
+    case POINTER_PLUS_EXPR:
+      chkp_collect_value (rhs1, res);
+      addr.pol.create (0);
+      chkp_collect_value (gimple_assign_rhs2 (def_stmt), addr);
+      chkp_add_addr_addr (res, addr);
+      addr.pol.release ();
+      break;
+
+    case MINUS_EXPR:
+      chkp_collect_value (rhs1, res);
+      addr.pol.create (0);
+      chkp_collect_value (gimple_assign_rhs2 (def_stmt), addr);
+      chkp_sub_addr_addr (res, addr);
+      addr.pol.release ();
+      break;
+
+    case MULT_EXPR:
+      if (TREE_CODE (rhs1) == SSA_NAME
+	  && TREE_CODE (gimple_assign_rhs2 (def_stmt)) == INTEGER_CST)
+	{
+	  chkp_collect_value (rhs1, res);
+	  chkp_mult_addr (res, gimple_assign_rhs2 (def_stmt));
+	}
+      else if (TREE_CODE (gimple_assign_rhs2 (def_stmt)) == SSA_NAME
+	       && TREE_CODE (rhs1) == INTEGER_CST)
+	{
+	  chkp_collect_value (gimple_assign_rhs2 (def_stmt), res);
+	  chkp_mult_addr (res, rhs1);
+	}
+      else
+	chkp_add_addr_item (res, integer_one_node, ptr);
+      break;
+
+    default:
+      chkp_add_addr_item (res, integer_one_node, ptr);
+      break;
+    }
+}
+
+/* Fill check_info structure *CI with information about
+   check STMT.  */
+static void
+chkp_fill_check_info (gimple stmt, struct check_info *ci)
+{
+  ci->addr.pol.create (0);
+  ci->bounds = gimple_call_arg (stmt, 1);
+  chkp_collect_value (gimple_call_arg (stmt, 0), ci->addr);
+  ci->type = (gimple_call_fndecl (stmt) == chkp_checkl_fndecl
+	     ? CHECK_LOWER_BOUND
+	     : CHECK_UPPER_BOUND);
+  ci->stmt = stmt;
+}


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