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.enkov...@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.
diff --git a/gcc/tree-chkp.c b/gcc/tree-chkp.c
index 6f73699..aae9681 100644
--- a/gcc/tree-chkp.c
+++ b/gcc/tree-chkp.c
@@ -328,10 +328,47 @@ along with GCC; see the file COPYING3. If not see
typedef void (*assign_handler)(tree, tree, void *);
+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 tree chkp_get_zero_bounds ();
static tree chkp_find_bounds (tree ptr, gimple_stmt_iterator *iter);
static tree chkp_find_bounds_loaded (tree ptr, tree ptr_src,
gimple_stmt_iterator *iter);
+static void chkp_collect_value (tree ssa_name, address_t &res);
static void chkp_parse_array_and_component_ref (tree node, tree *ptr,
tree *elt, bool *safe,
bool *bitfield,
@@ -4179,6 +4216,357 @@ chkp_gate (void)
|| lookup_attribute ("chkp ctor", DECL_ATTRIBUTES (cfun->decl));
}
+/* Comparator for pol_item structures I1 and I2 to be used
+ to find items with equal var. Also used for polynomial
+ sorting. */
+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 plynomial item in ADDR with var equal to VAR
+ and return its index. Return -1 if item was not
+ found. */
+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. */
+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. */
+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. */
+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. */
+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. */
+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. */
+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. */
+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. */
+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. */
+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. */
+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. */
+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;
+}
+
namespace {
const pass_data pass_data_chkp =
