@@ -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 \
new file mode 100644
@@ -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"
+
+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;
+}