On Fri, May 13, 2022 at 9:47 AM Alexandre Oliva <ol...@adacore.com> wrote:
>
> On May 12, 2022, Richard Biener <richard.guent...@gmail.com> wrote:
>
> > Note you are relying on an implementation detail here, it might be
> > better to mark blocks visited or iterate over the CFG in a more
> > defined manner
>
> *nod*, I was wondering whether that property could be relied on. I also
> see BB_NEW set in bb->flags in tree-cfg.cc:create_bb, which might be
> useful, but I'm not sure I could rely on that either.
Yeah, I'm not sure who clears that bit - grepping shows no user
besides the setter...
> Though I suppose it might be useful to document and enforce the property
> that a newly-created block takes up an index larger than any preexisting
> block,
Yes, if we want to commit on that. The behavior of FOR_EACH_BB_*
when doing CFG manipulations during the walk is also not documented
btw (they simply walk the next/prev_bb chain which has semantics
only in cfgrtl).
> since we haven't done that, I've reworked the code to gather the
> preexisting blocks in an auto_sbitmap, and to iterate only over them.
>
> Bootstrapping on x86_64-linux-gnu. Ok?
See below
>
> Avoid visiting newly-created blocks in harden-conditionals
>
> Reverse iteration over blocks, in gimple-harden-conditionals.cc, was
> supposed to avoid visiting blocks introduced by hardening and
> introducing further reversed conditionals and traps for them, but
> newly-created blocks may be inserted before the current block, as
> shown by the PR105455 testcase.
>
> Use an auto_sbitmap to gather preexisting blocks that need visiting.
>
>
> for gcc/ChangeLog
>
> * gimple-harden-conditionals.cc: Include sbitmap.h.
> (pass_harden_conditional_branches::execute): Skip new blocks.
> (pass_harden_compares::execute): Likewise.
> ---
> gcc/gimple-harden-conditionals.cc | 415
> +++++++++++++++++++------------------
> 1 file changed, 218 insertions(+), 197 deletions(-)
>
> diff --git a/gcc/gimple-harden-conditionals.cc
> b/gcc/gimple-harden-conditionals.cc
> index 19ceb8a4bd61e..811914f13fe1d 100644
> --- a/gcc/gimple-harden-conditionals.cc
> +++ b/gcc/gimple-harden-conditionals.cc
> @@ -36,6 +36,7 @@ along with GCC; see the file COPYING3. If not see
> #include "cfghooks.h"
> #include "cfgloop.h"
> #include "tree-eh.h"
> +#include "sbitmap.h"
> #include "diagnostic.h"
> #include "intl.h"
>
> @@ -303,9 +304,20 @@ insert_edge_check_and_trap (location_t loc, edge e,
> unsigned int
> pass_harden_conditional_branches::execute (function *fun)
> {
> + /* Record the preexisting blocks, to avoid visiting newly-created
> + blocks. */
> + auto_sbitmap to_visit (last_basic_block_for_fn (fun));
> +
I think you need to
bitmap_clear (to_visit);
here and in the other places otherwise sbitmap bits are uninitialized
at allocation.
Otherwise OK.
Thanks,
Richard.
> basic_block bb;
> - FOR_EACH_BB_REVERSE_FN (bb, fun)
> + FOR_EACH_BB_FN (bb, fun)
> + bitmap_set_bit (to_visit, bb->index);
> +
> + sbitmap_iterator it;
> + unsigned i;
> + EXECUTE_IF_SET_IN_BITMAP (to_visit, 0, i, it)
> {
> + bb = BASIC_BLOCK_FOR_FN (fun, i);
> +
> gimple_stmt_iterator gsi = gsi_last_bb (bb);
>
> if (gsi_end_p (gsi))
> @@ -385,205 +397,214 @@ non_eh_succ_edge (basic_block bb, edge *ehp = NULL)
> unsigned int
> pass_harden_compares::execute (function *fun)
> {
> + /* Record the preexisting blocks, to avoid visiting newly-created
> + blocks. */
> + auto_sbitmap to_visit (last_basic_block_for_fn (fun));
> +
> basic_block bb;
> - /* Go backwards over BBs and stmts, so that, even if we split the
> - block multiple times to insert a cond_expr after each compare we
> - find, we remain in the same block, visiting every preexisting
> - stmt exactly once, and not visiting newly-added blocks or
> - stmts. */
> - FOR_EACH_BB_REVERSE_FN (bb, fun)
> - for (gimple_stmt_iterator gsi = gsi_last_bb (bb);
> - !gsi_end_p (gsi); gsi_prev (&gsi))
> - {
> - gassign *asgn = dyn_cast <gassign *> (gsi_stmt (gsi));
> - if (!asgn)
> - continue;
> -
> - /* Turn:
> -
> - z = x op y;
> -
> - into:
> -
> - z = x op y;
> - z' = x' cop y';
> - if (z == z') __builtin_trap ();
> -
> - where cop is a complementary boolean operation to op; and x'
> - and y' hold the same value as x and y, but in a way that does
> - not enable the compiler to optimize the redundant compare
> - away.
> - */
> -
> - enum tree_code op = gimple_assign_rhs_code (asgn);
> -
> - enum tree_code cop;
> -
> - switch (op)
> - {
> - case EQ_EXPR:
> - case NE_EXPR:
> - case GT_EXPR:
> - case GE_EXPR:
> - case LT_EXPR:
> - case LE_EXPR:
> - case LTGT_EXPR:
> - case UNEQ_EXPR:
> - case UNGT_EXPR:
> - case UNGE_EXPR:
> - case UNLT_EXPR:
> - case UNLE_EXPR:
> - case ORDERED_EXPR:
> - case UNORDERED_EXPR:
> - cop = invert_tree_comparison (op,
> - HONOR_NANS
> - (gimple_assign_rhs1 (asgn)));
> -
> - if (cop == ERROR_MARK)
> - /* ??? Can we do better? */
> - continue;
> + FOR_EACH_BB_FN (bb, fun)
> + bitmap_set_bit (to_visit, bb->index);
> +
> + sbitmap_iterator it;
> + unsigned i;
> + EXECUTE_IF_SET_IN_BITMAP (to_visit, 0, i, it)
> + {
> + bb = BASIC_BLOCK_FOR_FN (fun, i);
>
> - break;
> -
> - /* ??? Maybe handle these too? */
> - case TRUTH_NOT_EXPR:
> - /* ??? The code below assumes binary ops, it would have to
> - be adjusted for TRUTH_NOT_EXPR, since it's unary. */
> - case TRUTH_ANDIF_EXPR:
> - case TRUTH_ORIF_EXPR:
> - case TRUTH_AND_EXPR:
> - case TRUTH_OR_EXPR:
> - case TRUTH_XOR_EXPR:
> - default:
> + for (gimple_stmt_iterator gsi = gsi_last_bb (bb);
> + !gsi_end_p (gsi); gsi_prev (&gsi))
> + {
> + gassign *asgn = dyn_cast <gassign *> (gsi_stmt (gsi));
> + if (!asgn)
> + continue;
> +
> + /* Turn:
> +
> + z = x op y;
> +
> + into:
> +
> + z = x op y;
> + z' = x' cop y';
> + if (z == z') __builtin_trap ();
> +
> + where cop is a complementary boolean operation to op; and x'
> + and y' hold the same value as x and y, but in a way that does
> + not enable the compiler to optimize the redundant compare
> + away.
> + */
> +
> + enum tree_code op = gimple_assign_rhs_code (asgn);
> +
> + enum tree_code cop;
> +
> + switch (op)
> + {
> + case EQ_EXPR:
> + case NE_EXPR:
> + case GT_EXPR:
> + case GE_EXPR:
> + case LT_EXPR:
> + case LE_EXPR:
> + case LTGT_EXPR:
> + case UNEQ_EXPR:
> + case UNGT_EXPR:
> + case UNGE_EXPR:
> + case UNLT_EXPR:
> + case UNLE_EXPR:
> + case ORDERED_EXPR:
> + case UNORDERED_EXPR:
> + cop = invert_tree_comparison (op,
> + HONOR_NANS
> + (gimple_assign_rhs1 (asgn)));
> +
> + if (cop == ERROR_MARK)
> + /* ??? Can we do better? */
> + continue;
> +
> + break;
> +
> + /* ??? Maybe handle these too? */
> + case TRUTH_NOT_EXPR:
> + /* ??? The code below assumes binary ops, it would have to
> + be adjusted for TRUTH_NOT_EXPR, since it's unary. */
> + case TRUTH_ANDIF_EXPR:
> + case TRUTH_ORIF_EXPR:
> + case TRUTH_AND_EXPR:
> + case TRUTH_OR_EXPR:
> + case TRUTH_XOR_EXPR:
> + default:
> + continue;
> + }
> +
> + /* These are the operands for the verification. */
> + tree lhs = gimple_assign_lhs (asgn);
> + tree op1 = gimple_assign_rhs1 (asgn);
> + tree op2 = gimple_assign_rhs2 (asgn);
> + location_t loc = gimple_location (asgn);
> +
> + /* Vector booleans can't be used in conditional branches. ???
> + Can we do better? How to reduce compare and
> + reversed-compare result vectors to a single boolean? */
> + if (VECTOR_TYPE_P (TREE_TYPE (op1)))
> continue;
> - }
> -
> - /* These are the operands for the verification. */
> - tree lhs = gimple_assign_lhs (asgn);
> - tree op1 = gimple_assign_rhs1 (asgn);
> - tree op2 = gimple_assign_rhs2 (asgn);
> - location_t loc = gimple_location (asgn);
> -
> - /* Vector booleans can't be used in conditional branches. ???
> - Can we do better? How to reduce compare and
> - reversed-compare result vectors to a single boolean? */
> - if (VECTOR_TYPE_P (TREE_TYPE (op1)))
> - continue;
> -
> - /* useless_type_conversion_p enables conversions from 1-bit
> - integer types to boolean to be discarded. */
> - gcc_checking_assert (TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE
> - || (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
> - && TYPE_PRECISION (TREE_TYPE (lhs)) == 1));
> -
> - tree rhs = copy_ssa_name (lhs);
> -
> - gimple_stmt_iterator gsi_split = gsi;
> - /* Don't separate the original assignment from debug stmts
> - that might be associated with it, and arrange to split the
> - block after debug stmts, so as to make sure the split block
> - won't be debug stmts only. */
> - gsi_next_nondebug (&gsi_split);
> -
> - bool throwing_compare_p = stmt_ends_bb_p (asgn);
> - if (throwing_compare_p)
> - {
> - basic_block nbb = split_edge (non_eh_succ_edge
> - (gimple_bb (asgn)));
> - gsi_split = gsi_start_bb (nbb);
> -
> - if (dump_file)
> - fprintf (dump_file,
> - "Splitting non-EH edge from block %i into %i"
> - " after a throwing compare\n",
> - gimple_bb (asgn)->index, nbb->index);
> - }
> -
> - bool same_p = (op1 == op2);
> - op1 = detach_value (loc, &gsi_split, op1);
> - op2 = same_p ? op1 : detach_value (loc, &gsi_split, op2);
> -
> - gassign *asgnck = gimple_build_assign (rhs, cop, op1, op2);
> - gimple_set_location (asgnck, loc);
> - gsi_insert_before (&gsi_split, asgnck, GSI_SAME_STMT);
> -
> - /* We wish to insert a cond_expr after the compare, so arrange
> - for it to be at the end of a block if it isn't, and for it
> - to have a single successor in case there's more than
> - one, as in PR104975. */
> - if (!gsi_end_p (gsi_split)
> - || !single_succ_p (gsi_bb (gsi_split)))
> - {
> - if (!gsi_end_p (gsi_split))
> - gsi_prev (&gsi_split);
> - else
> - gsi_split = gsi_last_bb (gsi_bb (gsi_split));
> - basic_block obb = gsi_bb (gsi_split);
> - basic_block nbb = split_block (obb, gsi_stmt (gsi_split))->dest;
> - gsi_next (&gsi_split);
> - gcc_checking_assert (gsi_end_p (gsi_split));
> -
> - single_succ_edge (bb)->goto_locus = loc;
> -
> - if (dump_file)
> - fprintf (dump_file,
> - "Splitting block %i into %i"
> - " before the conditional trap branch\n",
> - obb->index, nbb->index);
> - }
> -
> - /* If the check assignment must end a basic block, we can't
> - insert the conditional branch in the same block, so split
> - the block again, and prepare to insert the conditional
> - branch in the new block.
> -
> - Also assign an EH region to the compare. Even though it's
> - unlikely that the hardening compare will throw after the
> - original compare didn't, the compiler won't even know that
> - it's the same compare operands, so add the EH edge anyway. */
> - if (throwing_compare_p)
> - {
> - add_stmt_to_eh_lp (asgnck, lookup_stmt_eh_lp (asgn));
> - make_eh_edges (asgnck);
> -
> - edge ckeh;
> - basic_block nbb = split_edge (non_eh_succ_edge
> - (gimple_bb (asgnck), &ckeh));
> - gsi_split = gsi_start_bb (nbb);
> -
> - if (dump_file)
> - fprintf (dump_file,
> - "Splitting non-EH edge from block %i into %i after"
> - " the newly-inserted reversed throwing compare\n",
> - gimple_bb (asgnck)->index, nbb->index);
> -
> - if (!gimple_seq_empty_p (phi_nodes (ckeh->dest)))
> - {
> - edge aseh;
> - non_eh_succ_edge (gimple_bb (asgn), &aseh);
> -
> - gcc_checking_assert (aseh->dest == ckeh->dest);
> -
> - for (gphi_iterator psi = gsi_start_phis (ckeh->dest);
> - !gsi_end_p (psi); gsi_next (&psi))
> - {
> - gphi *phi = psi.phi ();
> - add_phi_arg (phi, PHI_ARG_DEF_FROM_EDGE (phi, aseh), ckeh,
> - gimple_phi_arg_location_from_edge (phi,
> aseh));
> - }
> -
> - if (dump_file)
> - fprintf (dump_file,
> - "Copying PHI args in EH block %i from %i to %i\n",
> - aseh->dest->index, aseh->src->index,
> ckeh->src->index);
> - }
> - }
> -
> - gcc_checking_assert (single_succ_p (gsi_bb (gsi_split)));
> -
> - insert_check_and_trap (loc, &gsi_split, EDGE_TRUE_VALUE,
> - EQ_EXPR, lhs, rhs);
> - }
> +
> + /* useless_type_conversion_p enables conversions from 1-bit
> + integer types to boolean to be discarded. */
> + gcc_checking_assert (TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE
> + || (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
> + && TYPE_PRECISION (TREE_TYPE (lhs)) == 1));
> +
> + tree rhs = copy_ssa_name (lhs);
> +
> + gimple_stmt_iterator gsi_split = gsi;
> + /* Don't separate the original assignment from debug stmts
> + that might be associated with it, and arrange to split the
> + block after debug stmts, so as to make sure the split block
> + won't be debug stmts only. */
> + gsi_next_nondebug (&gsi_split);
> +
> + bool throwing_compare_p = stmt_ends_bb_p (asgn);
> + if (throwing_compare_p)
> + {
> + basic_block nbb = split_edge (non_eh_succ_edge
> + (gimple_bb (asgn)));
> + gsi_split = gsi_start_bb (nbb);
> +
> + if (dump_file)
> + fprintf (dump_file,
> + "Splitting non-EH edge from block %i into %i"
> + " after a throwing compare\n",
> + gimple_bb (asgn)->index, nbb->index);
> + }
> +
> + bool same_p = (op1 == op2);
> + op1 = detach_value (loc, &gsi_split, op1);
> + op2 = same_p ? op1 : detach_value (loc, &gsi_split, op2);
> +
> + gassign *asgnck = gimple_build_assign (rhs, cop, op1, op2);
> + gimple_set_location (asgnck, loc);
> + gsi_insert_before (&gsi_split, asgnck, GSI_SAME_STMT);
> +
> + /* We wish to insert a cond_expr after the compare, so arrange
> + for it to be at the end of a block if it isn't, and for it
> + to have a single successor in case there's more than
> + one, as in PR104975. */
> + if (!gsi_end_p (gsi_split)
> + || !single_succ_p (gsi_bb (gsi_split)))
> + {
> + if (!gsi_end_p (gsi_split))
> + gsi_prev (&gsi_split);
> + else
> + gsi_split = gsi_last_bb (gsi_bb (gsi_split));
> + basic_block obb = gsi_bb (gsi_split);
> + basic_block nbb = split_block (obb, gsi_stmt (gsi_split))->dest;
> + gsi_next (&gsi_split);
> + gcc_checking_assert (gsi_end_p (gsi_split));
> +
> + single_succ_edge (bb)->goto_locus = loc;
> +
> + if (dump_file)
> + fprintf (dump_file,
> + "Splitting block %i into %i"
> + " before the conditional trap branch\n",
> + obb->index, nbb->index);
> + }
> +
> + /* If the check assignment must end a basic block, we can't
> + insert the conditional branch in the same block, so split
> + the block again, and prepare to insert the conditional
> + branch in the new block.
> +
> + Also assign an EH region to the compare. Even though it's
> + unlikely that the hardening compare will throw after the
> + original compare didn't, the compiler won't even know that
> + it's the same compare operands, so add the EH edge anyway. */
> + if (throwing_compare_p)
> + {
> + add_stmt_to_eh_lp (asgnck, lookup_stmt_eh_lp (asgn));
> + make_eh_edges (asgnck);
> +
> + edge ckeh;
> + basic_block nbb = split_edge (non_eh_succ_edge
> + (gimple_bb (asgnck), &ckeh));
> + gsi_split = gsi_start_bb (nbb);
> +
> + if (dump_file)
> + fprintf (dump_file,
> + "Splitting non-EH edge from block %i into %i after"
> + " the newly-inserted reversed throwing compare\n",
> + gimple_bb (asgnck)->index, nbb->index);
> +
> + if (!gimple_seq_empty_p (phi_nodes (ckeh->dest)))
> + {
> + edge aseh;
> + non_eh_succ_edge (gimple_bb (asgn), &aseh);
> +
> + gcc_checking_assert (aseh->dest == ckeh->dest);
> +
> + for (gphi_iterator psi = gsi_start_phis (ckeh->dest);
> + !gsi_end_p (psi); gsi_next (&psi))
> + {
> + gphi *phi = psi.phi ();
> + add_phi_arg (phi, PHI_ARG_DEF_FROM_EDGE (phi, aseh),
> ckeh,
> + gimple_phi_arg_location_from_edge (phi,
> aseh));
> + }
> +
> + if (dump_file)
> + fprintf (dump_file,
> + "Copying PHI args in EH block %i from %i to
> %i\n",
> + aseh->dest->index, aseh->src->index,
> + ckeh->src->index);
> + }
> + }
> +
> + gcc_checking_assert (single_succ_p (gsi_bb (gsi_split)));
> +
> + insert_check_and_trap (loc, &gsi_split, EDGE_TRUE_VALUE,
> + EQ_EXPR, lhs, rhs);
> + }
> + }
>
> return 0;
> }
>
>
> --
> Alexandre Oliva, happy hacker https://FSFLA.org/blogs/lxo/
> Free Software Activist GNU Toolchain Engineer
> Disinformation flourishes because many people care deeply about injustice
> but very few check the facts. Ask me about <https://stallmansupport.org>
