Optionally trap on impossible devirtualization

Hi,

the patch below might be useful for testcase preparation and debugging
compiler bugs such as PR 60965.  When
-ftrap-on-impossible-devirtualization is supplied on the command line,
it makes the devirtualization produce __builtin_trap instead of
__builtin_unreachable when it comes to the conclusion that there is no
legal target of a virtual call.

Apart from dealing with our bugs, it may be even useful to debug
compiled programs when a user triggers some sort of illegal
devirtualization, typically by missing a type check somewhere.
Currently the compiled program might simply take a wrong branch, with
the patch it will abort.

Bootstrapped and tested (with the option on) on x86_64-linux, I have
also successfully LTO built Firefox with it.  If I add some
documentation, would like to see this in trunk?

Thanks,

Martin


2014-04-03  Martin Jambor  <mjambor@suse.cz>

	* cgraph.c (verify_edge_corresponds_to_fndecl): Also always accept
	builtin_trap.
	* cgraphclones.c (cgraph_clone_node): Do not redirect calls to
	builtin_trap.
	* cgraphunit.c (walk_polymorphic_call_targets): Use
	ipa_impossible_devirt_target_node.
	* common.opt (ftrap-on-impossible-devirtualization): New option.
	* gimple-fold.c (fold_gimple_assign): Use
	ipa_impossible_devirt_target_decl.
	(gimple_fold_call): Likewise.
	(gimple_get_virt_method_for_vtable): Likewise.
	* ipa-cp.c (ipa_get_indirect_edge_target_1): Check also for
	builtin_trap, use ipa_impossible_devirt_target_decl.
	* ipa-devirt.c (ipa_impossible_devirt_target_decl): New function.
	(ipa_impossible_devirt_target_node): Likewise.
	* ipa-prop.c (ipa_make_edge_direct_to_target): Use
	ipa_impossible_devirt_target_decl.
	(try_make_edge_direct_virtual_call): Check also for builtin_trap, use
	ipa_impossible_devirt_target_decl.
	* ipa-utils.h (ipa_impossible_devirt_target_decl): Declare.
	(ipa_impossible_devirt_target_node): Likewise.
	* ipa.c (walk_polymorphic_call_targets): Use
	ipa_impossible_devirt_target_node.

On Fri, Apr 25, 2014 at 5:35 PM, Martin Jambor <mjambor@suse.cz> wrote:
> Hi,
>
> the patch below might be useful for testcase preparation and debugging
> compiler bugs such as PR 60965.  When
> -ftrap-on-impossible-devirtualization is supplied on the command line,
> it makes the devirtualization produce __builtin_trap instead of
> __builtin_unreachable when it comes to the conclusion that there is no
> legal target of a virtual call.
>
> Apart from dealing with our bugs, it may be even useful to debug
> compiled programs when a user triggers some sort of illegal
> devirtualization, typically by missing a type check somewhere.
> Currently the compiled program might simply take a wrong branch, with
> the patch it will abort.
>
> Bootstrapped and tested (with the option on) on x86_64-linux, I have
> also successfully LTO built Firefox with it.  If I add some
> documentation, would like to see this in trunk?

It's useful for debugging, so yes.  Not sure about the option name though.
Maybe we should have a generic -ftrap-on-unreachable flag instead
and handle all __builtin_unreachable () like that (for example by
folding or by simply make __builtin_unreachable () alias to __builtin_trap ()).

Richard.

> Thanks,
>
> Martin
>
>
> 2014-04-03  Martin Jambor  <mjambor@suse.cz>
>
>         * cgraph.c (verify_edge_corresponds_to_fndecl): Also always accept
>         builtin_trap.
>         * cgraphclones.c (cgraph_clone_node): Do not redirect calls to
>         builtin_trap.
>         * cgraphunit.c (walk_polymorphic_call_targets): Use
>         ipa_impossible_devirt_target_node.
>         * common.opt (ftrap-on-impossible-devirtualization): New option.
>         * gimple-fold.c (fold_gimple_assign): Use
>         ipa_impossible_devirt_target_decl.
>         (gimple_fold_call): Likewise.
>         (gimple_get_virt_method_for_vtable): Likewise.
>         * ipa-cp.c (ipa_get_indirect_edge_target_1): Check also for
>         builtin_trap, use ipa_impossible_devirt_target_decl.
>         * ipa-devirt.c (ipa_impossible_devirt_target_decl): New function.
>         (ipa_impossible_devirt_target_node): Likewise.
>         * ipa-prop.c (ipa_make_edge_direct_to_target): Use
>         ipa_impossible_devirt_target_decl.
>         (try_make_edge_direct_virtual_call): Check also for builtin_trap, use
>         ipa_impossible_devirt_target_decl.
>         * ipa-utils.h (ipa_impossible_devirt_target_decl): Declare.
>         (ipa_impossible_devirt_target_node): Likewise.
>         * ipa.c (walk_polymorphic_call_targets): Use
>         ipa_impossible_devirt_target_node.
>
>
> diff --git a/gcc/cgraph.c b/gcc/cgraph.c
> index be3661a..25e0775 100644
> --- a/gcc/cgraph.c
> +++ b/gcc/cgraph.c
> @@ -2664,9 +2664,10 @@ verify_edge_corresponds_to_fndecl (struct cgraph_edge *e, tree decl)
>      return false;
>
>    /* Optimizers can redirect unreachable calls or calls triggering undefined
> -     behaviour to builtin_unreachable.  */
> +     behaviour to builtin_unreachable or builtin_trap.  */
>    if (DECL_BUILT_IN_CLASS (e->callee->decl) == BUILT_IN_NORMAL
> -      && DECL_FUNCTION_CODE (e->callee->decl) == BUILT_IN_UNREACHABLE)
> +      && (DECL_FUNCTION_CODE (e->callee->decl) == BUILT_IN_UNREACHABLE
> +         || DECL_FUNCTION_CODE (e->callee->decl) == BUILT_IN_TRAP))
>      return false;
>    node = cgraph_function_or_thunk_node (node, NULL);
>
> diff --git a/gcc/cgraphclones.c b/gcc/cgraphclones.c
> index cd2d73d..e7bebe3 100644
> --- a/gcc/cgraphclones.c
> +++ b/gcc/cgraphclones.c
> @@ -449,8 +449,9 @@ cgraph_clone_node (struct cgraph_node *n, tree decl, gcov_type count, int freq,
>          be unreachable during the clonning procedure.  */
>        if (!e->callee
>           || DECL_BUILT_IN_CLASS (e->callee->decl) != BUILT_IN_NORMAL
> -         || DECL_FUNCTION_CODE (e->callee->decl) != BUILT_IN_UNREACHABLE)
> -        redirect_edge_duplicating_thunks (e, new_node, args_to_skip);
> +         || (DECL_FUNCTION_CODE (e->callee->decl) != BUILT_IN_UNREACHABLE
> +             && DECL_FUNCTION_CODE (e->callee->decl) != BUILT_IN_TRAP))
> +        cgraph_redirect_edge_callee (e, new_node);
>      }
>
>
> diff --git a/gcc/cgraphunit.c b/gcc/cgraphunit.c
> index 06283fc..6c56c90 100644
> --- a/gcc/cgraphunit.c
> +++ b/gcc/cgraphunit.c
> @@ -892,8 +892,7 @@ walk_polymorphic_call_targets (pointer_set_t *reachable_call_targets,
>           if (targets.length () == 1)
>             target = targets[0];
>           else
> -           target = cgraph_get_create_node
> -                      (builtin_decl_implicit (BUILT_IN_UNREACHABLE));
> +           target = ipa_impossible_devirt_target_node ();
>
>           if (cgraph_dump_file)
>             {
> diff --git a/gcc/common.opt b/gcc/common.opt
> index da275e5..3e8b359 100644
> --- a/gcc/common.opt
> +++ b/gcc/common.opt
> @@ -1019,6 +1019,10 @@ fdevirtualize
>  Common Report Var(flag_devirtualize) Optimization
>  Try to convert virtual calls to direct ones.
>
> +ftrap-on-impossible-devirtualization
> +Common Report Var(flag_trap_impossible_devirt)
> +Convert virtual calls that cannot have any target to builtin_trap.
> +
>  fdiagnostics-show-location=
>  Common Joined RejectNegative Enum(diagnostic_prefixing_rule)
>  -fdiagnostics-show-location=[once|every-line]  How often to emit source location at the beginning of line-wrapped diagnostics
> diff --git a/gcc/gimple-fold.c b/gcc/gimple-fold.c
> index 6402cce..e0dfcb9 100644
> --- a/gcc/gimple-fold.c
> +++ b/gcc/gimple-fold.c
> @@ -392,7 +392,7 @@ fold_gimple_assign (gimple_stmt_iterator *si)
>                     if (targets.length () == 1)
>                       fndecl = targets[0]->decl;
>                     else
> -                     fndecl = builtin_decl_implicit (BUILT_IN_UNREACHABLE);
> +                     fndecl = ipa_impossible_devirt_target_decl ();
>                     val = fold_convert (TREE_TYPE (val), fndecl);
>                     STRIP_USELESS_TYPE_CONVERSION (val);
>                     return val;
> @@ -1146,7 +1146,7 @@ gimple_fold_call (gimple_stmt_iterator *gsi, bool inplace)
>                 }
>               else
>                 {
> -                 tree fndecl = builtin_decl_implicit (BUILT_IN_UNREACHABLE);
> +                 tree fndecl = ipa_impossible_devirt_target_decl ();
>                   gimple new_stmt = gimple_build_call (fndecl, 0);
>                   gimple_set_location (new_stmt, gimple_location (stmt));
>                   if (lhs && TREE_CODE (lhs) == SSA_NAME)
> @@ -3332,7 +3332,7 @@ gimple_get_virt_method_for_vtable (HOST_WIDE_INT token,
>    if (!fn
>        || (TREE_CODE (fn) != ADDR_EXPR && TREE_CODE (fn) != FDESC_EXPR)
>        || TREE_CODE (TREE_OPERAND (fn, 0)) != FUNCTION_DECL)
> -    fn = builtin_decl_implicit (BUILT_IN_UNREACHABLE);
> +    fn = ipa_impossible_devirt_target_decl ();
>    else
>      {
>        fn = TREE_OPERAND (fn, 0);
> diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c
> index 479963c..124f31d 100644
> --- a/gcc/ipa-cp.c
> +++ b/gcc/ipa-cp.c
> @@ -1584,7 +1584,8 @@ ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie,
>           if (target)
>             {
>               if ((TREE_CODE (TREE_TYPE (target)) == FUNCTION_TYPE
> -                  && DECL_FUNCTION_CODE (target) == BUILT_IN_UNREACHABLE)
> +                  && (DECL_FUNCTION_CODE (target) == BUILT_IN_UNREACHABLE
> +                      || DECL_FUNCTION_CODE (target) == BUILT_IN_TRAP))
>                   || !possible_polymorphic_call_target_p
>                        (ie, cgraph_get_node (target)))
>                 {
> @@ -1593,7 +1594,7 @@ ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie,
>                              "Type inconsident devirtualization: %s/%i->%s\n",
>                              ie->caller->name (), ie->caller->order,
>                              IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (target)));
> -                 target = builtin_decl_implicit (BUILT_IN_UNREACHABLE);
> +                 target = ipa_impossible_devirt_target_decl ();
>                   cgraph_get_create_node (target);
>                 }
>               return target;
> @@ -1629,7 +1630,7 @@ ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie,
>        if (targets.length () == 1)
>         target = targets[0]->decl;
>        else
> -       target = builtin_decl_implicit (BUILT_IN_UNREACHABLE);
> +       target = ipa_impossible_devirt_target_decl ();
>      }
>    else
>      {
> @@ -1649,7 +1650,7 @@ ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie,
>                  "Type inconsident devirtualization: %s/%i->%s\n",
>                  ie->caller->name (), ie->caller->order,
>                  IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (target)));
> -      target = builtin_decl_implicit (BUILT_IN_UNREACHABLE);
> +      target = ipa_impossible_devirt_target_decl ();
>        cgraph_get_create_node (target);
>      }
>
> diff --git a/gcc/ipa-devirt.c b/gcc/ipa-devirt.c
> index d484b20..600836d 100644
> --- a/gcc/ipa-devirt.c
> +++ b/gcc/ipa-devirt.c
> @@ -2148,4 +2148,26 @@ make_pass_ipa_devirt (gcc::context *ctxt)
>    return new pass_ipa_devirt (ctxt);
>  }
>
> +/* Return function declaration that we want to generate call to when
> +   encountering a a virtual call which cannot have any valid target. */
> +
> +tree
> +ipa_impossible_devirt_target_decl (void)
> +{
> +  if (flag_trap_impossible_devirt)
> +    return builtin_decl_implicit (BUILT_IN_TRAP);
> +  else
> +    return builtin_decl_implicit (BUILT_IN_UNREACHABLE);
> +}
> +
> +/* Return call graph node of a function that we want to generate call to when
> +   encountering a a virtual call which cannot have any valid target. */
> +
> +cgraph_node *
> +ipa_impossible_devirt_target_node (void)
> +{
> +  return cgraph_get_create_node (ipa_impossible_devirt_target_decl ());
> +}
> +
> +
>  #include "gt-ipa-devirt.h"
> diff --git a/gcc/ipa-prop.c b/gcc/ipa-prop.c
> index 9f144fa..42623f4 100644
> --- a/gcc/ipa-prop.c
> +++ b/gcc/ipa-prop.c
> @@ -2494,7 +2494,7 @@ ipa_make_edge_direct_to_target (struct cgraph_edge *ie, tree target)
>             fprintf (dump_file, "ipa-prop: Discovered direct call to non-function"
>                                 " in %s/%i, making it unreachable.\n",
>                      ie->caller->name (), ie->caller->order);
> -         target = builtin_decl_implicit (BUILT_IN_UNREACHABLE);
> +         target = ipa_impossible_devirt_target_decl ();
>           callee = cgraph_get_create_node (target);
>           unreachable = true;
>         }
> @@ -2732,7 +2732,8 @@ try_make_edge_direct_virtual_call (struct cgraph_edge *ie,
>           if (target)
>             {
>               if ((TREE_CODE (TREE_TYPE (target)) == FUNCTION_TYPE
> -                  && DECL_FUNCTION_CODE (target) == BUILT_IN_UNREACHABLE)
> +                  && (DECL_FUNCTION_CODE (target) == BUILT_IN_UNREACHABLE
> +                      || DECL_FUNCTION_CODE (target) == BUILT_IN_TRAP))
>                   || !possible_polymorphic_call_target_p
>                        (ie, cgraph_get_node (target)))
>                 {
> @@ -2741,7 +2742,7 @@ try_make_edge_direct_virtual_call (struct cgraph_edge *ie,
>                              "Type inconsident devirtualization: %s/%i->%s\n",
>                              ie->caller->name (), ie->caller->order,
>                              IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (target)));
> -                 target = builtin_decl_implicit (BUILT_IN_UNREACHABLE);
> +                 target = ipa_impossible_devirt_target_decl ();
>                   cgraph_get_create_node (target);
>                 }
>               return ipa_make_edge_direct_to_target (ie, target);
> @@ -2774,7 +2775,7 @@ try_make_edge_direct_virtual_call (struct cgraph_edge *ie,
>         target = targets[0]->decl;
>        else
>         {
> -          target = builtin_decl_implicit (BUILT_IN_UNREACHABLE);
> +          target = ipa_impossible_devirt_target_decl ();
>           cgraph_get_create_node (target);
>         }
>      }
> diff --git a/gcc/ipa-utils.h b/gcc/ipa-utils.h
> index a2c985a..81c7983 100644
> --- a/gcc/ipa-utils.h
> +++ b/gcc/ipa-utils.h
> @@ -186,6 +186,10 @@ possible_polymorphic_call_target_p (tree call,
>                                              ipa_dummy_polymorphic_call_context,
>                                              n);
>  }
> +
> +tree ipa_impossible_devirt_target_decl (void);
> +cgraph_node *ipa_impossible_devirt_target_node (void);
> +
>  #endif  /* GCC_IPA_UTILS_H  */
>
>
> diff --git a/gcc/ipa.c b/gcc/ipa.c
> index 8b65abd..e8fd04d 100644
> --- a/gcc/ipa.c
> +++ b/gcc/ipa.c
> @@ -219,8 +219,7 @@ walk_polymorphic_call_targets (pointer_set_t *reachable_call_targets,
>           if (targets.length () == 1)
>             target = targets[0];
>           else
> -           target = cgraph_get_create_node
> -                      (builtin_decl_implicit (BUILT_IN_UNREACHABLE));
> +           target = ipa_impossible_devirt_target_node ();
>
>           if (dump_file)
>             fprintf (dump_file,

On Mon, Apr 28, 2014 at 11:05:06AM +0200, Richard Biener wrote:
> On Fri, Apr 25, 2014 at 5:35 PM, Martin Jambor <mjambor@suse.cz> wrote:
> > Hi,
> >
> > the patch below might be useful for testcase preparation and debugging
> > compiler bugs such as PR 60965.  When
> > -ftrap-on-impossible-devirtualization is supplied on the command line,
> > it makes the devirtualization produce __builtin_trap instead of
> > __builtin_unreachable when it comes to the conclusion that there is no
> > legal target of a virtual call.
> >
> > Apart from dealing with our bugs, it may be even useful to debug
> > compiled programs when a user triggers some sort of illegal
> > devirtualization, typically by missing a type check somewhere.
> > Currently the compiled program might simply take a wrong branch, with
> > the patch it will abort.
> >
> > Bootstrapped and tested (with the option on) on x86_64-linux, I have
> > also successfully LTO built Firefox with it.  If I add some
> > documentation, would like to see this in trunk?
> 
> It's useful for debugging, so yes.  Not sure about the option name though.
> Maybe we should have a generic -ftrap-on-unreachable flag instead
> and handle all __builtin_unreachable () like that (for example by
> folding or by simply make __builtin_unreachable () alias to __builtin_trap ()).

-fsanitize=unreachable should already do that.  With
-fsanitize=unreachable -fsanitize-undefined-trap-on-error
it should fold __builtin_unreachable () to __builtin_trap (), otherwise
to __ubsan_handle_builtin_unreachable () call.

So, from this POV, the new option is redundant.

	Jakub

On Mon, Apr 28, 2014 at 11:10:41AM +0200, Jakub Jelinek wrote:
> On Mon, Apr 28, 2014 at 11:05:06AM +0200, Richard Biener wrote:
> > On Fri, Apr 25, 2014 at 5:35 PM, Martin Jambor <mjambor@suse.cz> wrote:
> > > Hi,
> > >
> > > the patch below might be useful for testcase preparation and debugging
> > > compiler bugs such as PR 60965.  When
> > > -ftrap-on-impossible-devirtualization is supplied on the command line,
> > > it makes the devirtualization produce __builtin_trap instead of
> > > __builtin_unreachable when it comes to the conclusion that there is no
> > > legal target of a virtual call.
> > >
> > > Apart from dealing with our bugs, it may be even useful to debug
> > > compiled programs when a user triggers some sort of illegal
> > > devirtualization, typically by missing a type check somewhere.
> > > Currently the compiled program might simply take a wrong branch, with
> > > the patch it will abort.
> > >
> > > Bootstrapped and tested (with the option on) on x86_64-linux, I have
> > > also successfully LTO built Firefox with it.  If I add some
> > > documentation, would like to see this in trunk?
> > 
> > It's useful for debugging, so yes.  Not sure about the option name though.
> > Maybe we should have a generic -ftrap-on-unreachable flag instead
> > and handle all __builtin_unreachable () like that (for example by
> > folding or by simply make __builtin_unreachable () alias to __builtin_trap ()).
> 
> -fsanitize=unreachable should already do that.  With
> -fsanitize=unreachable -fsanitize-undefined-trap-on-error
> it should fold __builtin_unreachable () to __builtin_trap (), otherwise
> to __ubsan_handle_builtin_unreachable () call.
> 
> So, from this POV, the new option is redundant.

That sounds like good news except that it does not work, at least not
for me when I tried it on the testcase from comment #2 from PR 60965.
The behavior of the executable is just the same, I do not get any
traps.  Is this supposed to work at -O2?  If so, should I file a ubsan
bug?  (If not, then I suppose some additional non-ubsan mechanism for
this might be also useful.)

Thanks,

Martin

> On Mon, Apr 28, 2014 at 11:10:41AM +0200, Jakub Jelinek wrote:
> > On Mon, Apr 28, 2014 at 11:05:06AM +0200, Richard Biener wrote:
> > > On Fri, Apr 25, 2014 at 5:35 PM, Martin Jambor <mjambor@suse.cz> wrote:
> > > > Hi,
> > > >
> > > > the patch below might be useful for testcase preparation and debugging
> > > > compiler bugs such as PR 60965.  When
> > > > -ftrap-on-impossible-devirtualization is supplied on the command line,
> > > > it makes the devirtualization produce __builtin_trap instead of
> > > > __builtin_unreachable when it comes to the conclusion that there is no
> > > > legal target of a virtual call.
> > > >
> > > > Apart from dealing with our bugs, it may be even useful to debug
> > > > compiled programs when a user triggers some sort of illegal
> > > > devirtualization, typically by missing a type check somewhere.
> > > > Currently the compiled program might simply take a wrong branch, with
> > > > the patch it will abort.
> > > >
> > > > Bootstrapped and tested (with the option on) on x86_64-linux, I have
> > > > also successfully LTO built Firefox with it.  If I add some
> > > > documentation, would like to see this in trunk?
> > > 
> > > It's useful for debugging, so yes.  Not sure about the option name though.
> > > Maybe we should have a generic -ftrap-on-unreachable flag instead
> > > and handle all __builtin_unreachable () like that (for example by
> > > folding or by simply make __builtin_unreachable () alias to __builtin_trap ()).
> > 
> > -fsanitize=unreachable should already do that.  With
> > -fsanitize=unreachable -fsanitize-undefined-trap-on-error
> > it should fold __builtin_unreachable () to __builtin_trap (), otherwise
> > to __ubsan_handle_builtin_unreachable () call.
> > 
> > So, from this POV, the new option is redundant.
> 
> That sounds like good news except that it does not work, at least not
> for me when I tried it on the testcase from comment #2 from PR 60965.
> The behavior of the executable is just the same, I do not get any
> traps.  Is this supposed to work at -O2?  If so, should I file a ubsan
> bug?  (If not, then I suppose some additional non-ubsan mechanism for
> this might be also useful.)

As i wrote in the other email, I think the problem is when the transformation
happen and if we re-fold the statement.

Indeed, we ought to fix this. (It works in one of the PRs I looked into, but
only for mainline, not for 4.9)

Honza
> 
> Thanks,
> 
> Martin