hardcfr: support checking at abnormal edges [PR111943]

hardcfr: support checking at abnormal edges [PR111943]

[Alexandre Oliva]

Control flow redundancy may choose abnormal edges for early checking,
but that breaks because we can't insert checks on such edges.

Introduce conditional checking on the dest block of abnormal edges,
and leave it for the optimizer to drop the conditional.

Also, oops, I noticed the new files went in with an incorrect copyright
notice, that this patch fixes.

Regstrapped on x86_64-linux-gnu.  Ok to install?


for  gcc/ChangeLog

	PR tree-optimization/111943
	* gimple-harden-control-flow.cc: Adjust copyright year.
	(rt_bb_visited): Add vfalse and vtrue data members.
	Zero-initialize them in the ctor.
	(rt_bb_visited::insert_exit_check_on_edge): Upon encountering
	abnormal edges, insert initializers for vfalse and vtrue on
	entry, and insert the check sequence guarded by a conditional
	in the dest block.

for  libgcc/ChangeLog

	* hardcfr.c: Adjust copyright year.

for  gcc/testsuite/ChangeLog

	PR tree-optimization/111943
	* gcc.dg/harden-cfr-pr111943.c: New.
---
 gcc/gimple-harden-control-flow.cc          |   78 +++++++++++++++++++++++++++-
 gcc/testsuite/gcc.dg/harden-cfr-pr111943.c |   33 ++++++++++++
 libgcc/hardcfr.c                           |    2 -
 3 files changed, 109 insertions(+), 4 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/harden-cfr-pr111943.c

diff --git a/gcc/gimple-harden-control-flow.cc b/gcc/gimple-harden-control-flow.cc
index 3711b25d09123..77c140178060e 100644
--- a/gcc/gimple-harden-control-flow.cc
+++ b/gcc/gimple-harden-control-flow.cc
@@ -1,5 +1,5 @@
 /* Control flow redundancy hardening.
-   Copyright (C) 2022 Free Software Foundation, Inc.
+   Copyright (C) 2022-2023 Free Software Foundation, Inc.
    Contributed by Alexandre Oliva <oliva@adacore.com>.
 
 This file is part of GCC.
@@ -460,6 +460,10 @@ class rt_bb_visited
      at the end of a block's predecessors or successors list.  */
   tree ckfail, ckpart, ckinv, ckblk;
 
+  /* If we need to deal with abnormal edges, we insert SSA_NAMEs for
+     boolean true and false.  */
+  tree vfalse, vtrue;
+
   /* Convert a block index N to a block vindex, the index used to
      identify it in the VISITED array.  Check that it's in range:
      neither ENTRY nor EXIT, but maybe one-past-the-end, to compute
@@ -596,7 +600,8 @@ public:
   /* Prepare to add control flow redundancy testing to CFUN.  */
   rt_bb_visited (int checkpoints)
     : nblocks (n_basic_blocks_for_fn (cfun)),
-      vword_type (NULL), ckseq (NULL), rtcfg (NULL)
+      vword_type (NULL), ckseq (NULL), rtcfg (NULL),
+      vfalse (NULL), vtrue (NULL)
   {
     /* If we've already added a declaration for the builtin checker,
        extract vword_type and vword_bits from its declaration.  */
@@ -703,7 +708,74 @@ public:
   /* Insert SEQ on E.  */
   void insert_exit_check_on_edge (gimple_seq seq, edge e)
   {
-    gsi_insert_seq_on_edge_immediate (e, seq);
+    if (!(e->flags & EDGE_ABNORMAL))
+      {
+	gsi_insert_seq_on_edge_immediate (e, seq);
+	return;
+      }
+
+    /* Initialize SSA boolean constants for use in abnormal PHIs.  */
+    if (!vfalse)
+      {
+	vfalse = make_ssa_name (boolean_type_node);
+	vtrue = make_ssa_name (boolean_type_node);
+
+	gimple_seq vft_seq = NULL;
+	gassign *vfalse_init = gimple_build_assign (vfalse, boolean_false_node);
+	gimple_seq_add_stmt (&vft_seq, vfalse_init);
+	gassign *vtrue_init = gimple_build_assign (vtrue, boolean_true_node);
+	gimple_seq_add_stmt (&vft_seq, vtrue_init);
+
+	gsi_insert_seq_on_edge_immediate (single_succ_edge
+					  (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
+					  vft_seq);
+      }
+
+    /* We can't insert on abnormal edges, but we can arrange for SEQ
+       to execute conditionally at dest.  Add a PHI boolean with TRUE
+       from E and FALES from other preds, split the whole block, add a
+       test for the PHI to run a new block with SEQ or skip straight
+       to the original block.  If there are multiple incoming abnormal
+       edges, we'll do this multiple times.  ??? Unless there are
+       multiple abnormal edges with different postcheck status, we
+       could split the block and redirect other edges, rearranging the
+       PHI nodes.  Optimizers already know how to do this, so we can
+       keep things simple here.  */
+    basic_block bb = e->dest;
+    basic_block bb_postcheck = split_block_after_labels (bb)->dest;
+
+    basic_block bb_check = create_empty_bb (e->dest);
+    bb_check->count = e->count ();
+    if (dom_info_available_p (CDI_DOMINATORS))
+      set_immediate_dominator (CDI_DOMINATORS, bb_check, bb);
+    if (current_loops)
+      add_bb_to_loop (bb_check, current_loops->tree_root);
+
+    gimple_stmt_iterator chkpt = gsi_after_labels (bb_check);
+    gsi_insert_seq_before_without_update (&chkpt, seq, GSI_SAME_STMT);
+    edge edge_postcheck = make_edge (bb_check, bb_postcheck, EDGE_FALLTHRU);
+    edge_postcheck->probability = profile_probability::always ();
+
+    tree cond_var = make_ssa_name (boolean_type_node);
+    gcond *cond = gimple_build_cond (NE_EXPR, cond_var, boolean_false_node,
+				     NULL, NULL);
+    gimple_stmt_iterator condpt = gsi_after_labels (bb);
+    gsi_insert_before (&condpt, cond, GSI_SAME_STMT);
+    edge edge_nocheck = single_succ_edge (bb);
+    edge_nocheck->flags &= ~EDGE_FALLTHRU;
+    edge_nocheck->flags |= EDGE_FALSE_VALUE;
+    edge edge_check = make_edge (bb, bb_check, EDGE_TRUE_VALUE);
+    edge_check->probability = e->count ().probability_in (bb->count);
+    edge_nocheck->probability = edge_check->probability.invert ();
+
+    gphi *cond_phi = create_phi_node (cond_var, bb);
+    for (int i = 0, ei = EDGE_COUNT (bb->preds); i < ei; i++)
+      {
+	edge pred = EDGE_PRED (bb, i);
+	bool check_edge = pred == e;
+	tree val = check_edge ? vtrue : vfalse;
+	add_phi_arg (cond_phi, val, pred, UNKNOWN_LOCATION);
+      }
   }
 
   /* Add checking code to CHK_EDGES and CHKCALL_BLOCKS, and
diff --git a/gcc/testsuite/gcc.dg/harden-cfr-pr111943.c b/gcc/testsuite/gcc.dg/harden-cfr-pr111943.c
new file mode 100644
index 0000000000000..5a5a2133b1368
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/harden-cfr-pr111943.c
@@ -0,0 +1,33 @@
+/* { dg-do compile } */
+/* { dg-options "-fharden-control-flow-redundancy --param=max-jump-thread-duplication-stmts=0 -Ofast -fdump-tree-hardcfr -fdump-tree-optimized" } */
+/* { dg-require-effective-target indirect_jumps } */
+/* { dg-require-effective-target label_values } */
+
+/* Based on gcc.c-torture/compile/20050510-1.c.  */
+
+extern void dont_remove (void);
+
+void bar (int k)
+{
+  void *label = (k) ? &&x : &&y;
+
+  if (k >= 0)
+    goto *label;
+
+x:
+  if (k <= 0)
+    dont_remove ();
+  /* else goto y; */
+
+y:
+  return;
+}
+
+/* Check before calling dont_remove(), in the 'else goto y' edge, and in the
+   abnormal edge to y.  */
+/* { dg-final { scan-tree-dump-times "hardcfr_check" 3 "hardcfr" } } */
+/* { dg-final { scan-tree-dump-times "hardcfr_check" 3 "optimized" } } */
+/* Check that hardcfr introduces an abnormal PHI node (this could be avoided,
+   but it's not worth the effort), and that it gets optimized out.  */
+/* { dg-final { scan-tree-dump-times {\(ab\) = PHI .*\(ab\)} 1 "hardcfr" } } */
+/* { dg-final { scan-tree-dump-not {\(ab\) = PHI .*\(ab\)} "optimized" } } */
diff --git a/libgcc/hardcfr.c b/libgcc/hardcfr.c
index 7496095b8666c..25ff06742cb44 100644
--- a/libgcc/hardcfr.c
+++ b/libgcc/hardcfr.c
@@ -1,5 +1,5 @@
 /* Control flow redundancy hardening
-   Copyright (C) 2022 Free Software Foundation, Inc.
+   Copyright (C) 2022-2023 Free Software Foundation, Inc.
    Contributed by Alexandre Oliva <oliva@adacore.com>
 
 This file is part of GCC.

-- 
Alexandre Oliva, happy hacker            https://FSFLA.org/blogs/lxo/
   Free Software Activist                   GNU Toolchain Engineer
More tolerance and less prejudice are key for inclusion and diversity
Excluding neuro-others for not behaving ""normal"" is *not* inclusive

Re: hardcfr: support checking at abnormal edges [PR111943]

[Richard Biener]

On Thu, Oct 26, 2023 at 5:44 PM Alexandre Oliva <oliva@adacore.com> wrote:
>
>
> Control flow redundancy may choose abnormal edges for early checking,
> but that breaks because we can't insert checks on such edges.
>
> Introduce conditional checking on the dest block of abnormal edges,
> and leave it for the optimizer to drop the conditional.
>
> Also, oops, I noticed the new files went in with an incorrect copyright
> notice, that this patch fixes.
>
> Regstrapped on x86_64-linux-gnu.  Ok to install?

OK.


>
> for  gcc/ChangeLog
>
>         PR tree-optimization/111943
>         * gimple-harden-control-flow.cc: Adjust copyright year.
>         (rt_bb_visited): Add vfalse and vtrue data members.
>         Zero-initialize them in the ctor.
>         (rt_bb_visited::insert_exit_check_on_edge): Upon encountering
>         abnormal edges, insert initializers for vfalse and vtrue on
>         entry, and insert the check sequence guarded by a conditional
>         in the dest block.
>
> for  libgcc/ChangeLog
>
>         * hardcfr.c: Adjust copyright year.
>
> for  gcc/testsuite/ChangeLog
>
>         PR tree-optimization/111943
>         * gcc.dg/harden-cfr-pr111943.c: New.
> ---
>  gcc/gimple-harden-control-flow.cc          |   78 +++++++++++++++++++++++++++-
>  gcc/testsuite/gcc.dg/harden-cfr-pr111943.c |   33 ++++++++++++
>  libgcc/hardcfr.c                           |    2 -
>  3 files changed, 109 insertions(+), 4 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.dg/harden-cfr-pr111943.c
>
> diff --git a/gcc/gimple-harden-control-flow.cc b/gcc/gimple-harden-control-flow.cc
> index 3711b25d09123..77c140178060e 100644
> --- a/gcc/gimple-harden-control-flow.cc
> +++ b/gcc/gimple-harden-control-flow.cc
> @@ -1,5 +1,5 @@
>  /* Control flow redundancy hardening.
> -   Copyright (C) 2022 Free Software Foundation, Inc.
> +   Copyright (C) 2022-2023 Free Software Foundation, Inc.
>     Contributed by Alexandre Oliva <oliva@adacore.com>.
>
>  This file is part of GCC.
> @@ -460,6 +460,10 @@ class rt_bb_visited
>       at the end of a block's predecessors or successors list.  */
>    tree ckfail, ckpart, ckinv, ckblk;
>
> +  /* If we need to deal with abnormal edges, we insert SSA_NAMEs for
> +     boolean true and false.  */
> +  tree vfalse, vtrue;
> +
>    /* Convert a block index N to a block vindex, the index used to
>       identify it in the VISITED array.  Check that it's in range:
>       neither ENTRY nor EXIT, but maybe one-past-the-end, to compute
> @@ -596,7 +600,8 @@ public:
>    /* Prepare to add control flow redundancy testing to CFUN.  */
>    rt_bb_visited (int checkpoints)
>      : nblocks (n_basic_blocks_for_fn (cfun)),
> -      vword_type (NULL), ckseq (NULL), rtcfg (NULL)
> +      vword_type (NULL), ckseq (NULL), rtcfg (NULL),
> +      vfalse (NULL), vtrue (NULL)
>    {
>      /* If we've already added a declaration for the builtin checker,
>         extract vword_type and vword_bits from its declaration.  */
> @@ -703,7 +708,74 @@ public:
>    /* Insert SEQ on E.  */
>    void insert_exit_check_on_edge (gimple_seq seq, edge e)
>    {
> -    gsi_insert_seq_on_edge_immediate (e, seq);
> +    if (!(e->flags & EDGE_ABNORMAL))
> +      {
> +       gsi_insert_seq_on_edge_immediate (e, seq);
> +       return;
> +      }
> +
> +    /* Initialize SSA boolean constants for use in abnormal PHIs.  */
> +    if (!vfalse)
> +      {
> +       vfalse = make_ssa_name (boolean_type_node);
> +       vtrue = make_ssa_name (boolean_type_node);
> +
> +       gimple_seq vft_seq = NULL;
> +       gassign *vfalse_init = gimple_build_assign (vfalse, boolean_false_node);
> +       gimple_seq_add_stmt (&vft_seq, vfalse_init);
> +       gassign *vtrue_init = gimple_build_assign (vtrue, boolean_true_node);
> +       gimple_seq_add_stmt (&vft_seq, vtrue_init);
> +
> +       gsi_insert_seq_on_edge_immediate (single_succ_edge
> +                                         (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
> +                                         vft_seq);
> +      }
> +
> +    /* We can't insert on abnormal edges, but we can arrange for SEQ
> +       to execute conditionally at dest.  Add a PHI boolean with TRUE
> +       from E and FALES from other preds, split the whole block, add a
> +       test for the PHI to run a new block with SEQ or skip straight
> +       to the original block.  If there are multiple incoming abnormal
> +       edges, we'll do this multiple times.  ??? Unless there are
> +       multiple abnormal edges with different postcheck status, we
> +       could split the block and redirect other edges, rearranging the
> +       PHI nodes.  Optimizers already know how to do this, so we can
> +       keep things simple here.  */
> +    basic_block bb = e->dest;
> +    basic_block bb_postcheck = split_block_after_labels (bb)->dest;
> +
> +    basic_block bb_check = create_empty_bb (e->dest);
> +    bb_check->count = e->count ();
> +    if (dom_info_available_p (CDI_DOMINATORS))
> +      set_immediate_dominator (CDI_DOMINATORS, bb_check, bb);
> +    if (current_loops)
> +      add_bb_to_loop (bb_check, current_loops->tree_root);
> +
> +    gimple_stmt_iterator chkpt = gsi_after_labels (bb_check);
> +    gsi_insert_seq_before_without_update (&chkpt, seq, GSI_SAME_STMT);
> +    edge edge_postcheck = make_edge (bb_check, bb_postcheck, EDGE_FALLTHRU);
> +    edge_postcheck->probability = profile_probability::always ();
> +
> +    tree cond_var = make_ssa_name (boolean_type_node);
> +    gcond *cond = gimple_build_cond (NE_EXPR, cond_var, boolean_false_node,
> +                                    NULL, NULL);
> +    gimple_stmt_iterator condpt = gsi_after_labels (bb);
> +    gsi_insert_before (&condpt, cond, GSI_SAME_STMT);
> +    edge edge_nocheck = single_succ_edge (bb);
> +    edge_nocheck->flags &= ~EDGE_FALLTHRU;
> +    edge_nocheck->flags |= EDGE_FALSE_VALUE;
> +    edge edge_check = make_edge (bb, bb_check, EDGE_TRUE_VALUE);
> +    edge_check->probability = e->count ().probability_in (bb->count);
> +    edge_nocheck->probability = edge_check->probability.invert ();
> +
> +    gphi *cond_phi = create_phi_node (cond_var, bb);
> +    for (int i = 0, ei = EDGE_COUNT (bb->preds); i < ei; i++)
> +      {
> +       edge pred = EDGE_PRED (bb, i);
> +       bool check_edge = pred == e;
> +       tree val = check_edge ? vtrue : vfalse;
> +       add_phi_arg (cond_phi, val, pred, UNKNOWN_LOCATION);
> +      }
>    }
>
>    /* Add checking code to CHK_EDGES and CHKCALL_BLOCKS, and
> diff --git a/gcc/testsuite/gcc.dg/harden-cfr-pr111943.c b/gcc/testsuite/gcc.dg/harden-cfr-pr111943.c
> new file mode 100644
> index 0000000000000..5a5a2133b1368
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/harden-cfr-pr111943.c
> @@ -0,0 +1,33 @@
> +/* { dg-do compile } */
> +/* { dg-options "-fharden-control-flow-redundancy --param=max-jump-thread-duplication-stmts=0 -Ofast -fdump-tree-hardcfr -fdump-tree-optimized" } */
> +/* { dg-require-effective-target indirect_jumps } */
> +/* { dg-require-effective-target label_values } */
> +
> +/* Based on gcc.c-torture/compile/20050510-1.c.  */
> +
> +extern void dont_remove (void);
> +
> +void bar (int k)
> +{
> +  void *label = (k) ? &&x : &&y;
> +
> +  if (k >= 0)
> +    goto *label;
> +
> +x:
> +  if (k <= 0)
> +    dont_remove ();
> +  /* else goto y; */
> +
> +y:
> +  return;
> +}
> +
> +/* Check before calling dont_remove(), in the 'else goto y' edge, and in the
> +   abnormal edge to y.  */
> +/* { dg-final { scan-tree-dump-times "hardcfr_check" 3 "hardcfr" } } */
> +/* { dg-final { scan-tree-dump-times "hardcfr_check" 3 "optimized" } } */
> +/* Check that hardcfr introduces an abnormal PHI node (this could be avoided,
> +   but it's not worth the effort), and that it gets optimized out.  */
> +/* { dg-final { scan-tree-dump-times {\(ab\) = PHI .*\(ab\)} 1 "hardcfr" } } */
> +/* { dg-final { scan-tree-dump-not {\(ab\) = PHI .*\(ab\)} "optimized" } } */
> diff --git a/libgcc/hardcfr.c b/libgcc/hardcfr.c
> index 7496095b8666c..25ff06742cb44 100644
> --- a/libgcc/hardcfr.c
> +++ b/libgcc/hardcfr.c
> @@ -1,5 +1,5 @@
>  /* Control flow redundancy hardening
> -   Copyright (C) 2022 Free Software Foundation, Inc.
> +   Copyright (C) 2022-2023 Free Software Foundation, Inc.
>     Contributed by Alexandre Oliva <oliva@adacore.com>
>
>  This file is part of GCC.
>
> --
> Alexandre Oliva, happy hacker            https://FSFLA.org/blogs/lxo/
>    Free Software Activist                   GNU Toolchain Engineer
> More tolerance and less prejudice are key for inclusion and diversity
> Excluding neuro-others for not behaving ""normal"" is *not* inclusive

Re: hardcfr: support checking at abnormal edges [PR111943]

[Alexandre Oliva]

[adding list]

On Oct 27, 2023, rep.dot.nop@gmail.com wrote:

> +       from E and FALES from other preds, split the whole block, add a

> s/FALES/FALSE/

Thanks, I've just installed the patch including the typo fix.

-- 
Alexandre Oliva, happy hacker            https://FSFLA.org/blogs/lxo/
   Free Software Activist                   GNU Toolchain Engineer
More tolerance and less prejudice are key for inclusion and diversity
Excluding neuro-others for not behaving ""normal"" is *not* inclusive