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

[Ilya Enkovich]

Hi,

This patch adds a bounds lifetime reduction into checker optimization.

Thanks,
Ilya
--
2014-10-08 Ilya Enkovich <***@intel.com>

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


diff --git a/gcc/tree-chkp.c b/gcc/tree-chkp.c
index 37ab729..60e4c11 100644
--- a/gcc/tree-chkp.c
+++ b/gcc/tree-chkp.c
@@ -5420,6 +5420,155 @@ 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. */
+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;
+ }
+
+ 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. */
void
chkp_opt_init (void)
@@ -5464,6 +5613,8 @@ chkp_opt_execute (void)

chkp_remove_redundant_checks ();

+ chkp_reduce_bounds_lifetime ();
+
chkp_release_check_info ();

chkp_opt_fini ();

[Jeff Law]

Post by Ilya Enkovich
Hi,
This patch adds a bounds lifetime reduction into checker optimization.
Thanks,
Ilya
--
* 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?

Post by Ilya Enkovich
+ /* 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