Patchwork [RFC] Fix PR54824, deal with BBs with no successor

login
register
mail settings
Submitter Steven Bosscher
Date Oct. 24, 2012, 7:50 p.m.
Message ID <CABu31nPmZKHZXSWsJcjm_kZX0MGMm0YssUHe-ZE-C-=skfFk3g@mail.gmail.com>
Download mbox | patch
Permalink /patch/193941/
State New
Headers show

Comments

Steven Bosscher - Oct. 24, 2012, 7:50 p.m.
On Wed, Oct 24, 2012 at 4:25 PM, Richard Biener <rguenther@suse.de> wrote:
> Comments?  Should find_many_sub_basic_blocks really do what
> it does here?  Or is the CFG in fact "invalid" (but we don't
> check that in verification)?

If a "noreturn" function is inlined, doesn't the inliner detect that
the inlined body does in fact return?? The error is that the function
"bar()" returns, the documentation for noreturn makes it pretty clear
that such functions should never return:

In this case, bar() returns but the compiler has already used its
noreturn attribute to construct a dead end in the CFG (i.e. your basic
block without successors). But the fact that bar() returns is
undefined behavior. I'm not sure it is possible to know where the
function would continue after returning from bar(), after lowering to
GIMPLE.

IMHO find_many_sub_basic_blocks should not connect this block to the
rest of the CFG, so expanding a trap or a barrier is my preferred
solution, like so:



At least this way the GIMPLE and RTL CFGs should be more alike than
with an infinite loop.

But, really, why inline noreturn functions at all?

Ciao!
Steven
Richard Guenther - Oct. 25, 2012, 10:31 a.m.
On Wed, 24 Oct 2012, Steven Bosscher wrote:

> On Wed, Oct 24, 2012 at 4:25 PM, Richard Biener <rguenther@suse.de> wrote:
> > Comments?  Should find_many_sub_basic_blocks really do what
> > it does here?  Or is the CFG in fact "invalid" (but we don't
> > check that in verification)?
> 
> If a "noreturn" function is inlined, doesn't the inliner detect that
> the inlined body does in fact return?? The error is that the function
> "bar()" returns, the documentation for noreturn makes it pretty clear
> that such functions should never return:
> 
> In this case, bar() returns but the compiler has already used its
> noreturn attribute to construct a dead end in the CFG (i.e. your basic
> block without successors). But the fact that bar() returns is
> undefined behavior. I'm not sure it is possible to know where the
> function would continue after returning from bar(), after lowering to
> GIMPLE.
> 
> IMHO find_many_sub_basic_blocks should not connect this block to the
> rest of the CFG, so expanding a trap or a barrier is my preferred
> solution, like so:
> 
> Index: cfgexpand.c
> ===================================================================
> --- cfgexpand.c (revision 192696)
> +++ cfgexpand.c (working copy)
> @@ -3989,6 +3989,12 @@ expand_gimple_basic_block (basic_block b
> 
>    do_pending_stack_adjust ();
> 
> +  /* If this block has no successors at all, make sure that
> +     find_many_sub_basic_blocks does not connect this "dead end"
> +     to the rest of the function.  */
> +  if (EDGE_COUNT (bb->succs) == 0)
> +    expand_builtin_unreachable ();
> +
>    /* Find the block tail.  The last insn in the block is the insn
>       before a barrier and/or table jump insn.  */
>    last = get_last_insn ();
> 
> 
> At least this way the GIMPLE and RTL CFGs should be more alike than
> with an infinite loop.

Sure.  My patch made sure we never have a BB without successor
like this on GIMPLE either.  I suppose DOM computation wouldn't
like it (not sure if noreturn/infinite-loop to exit connect does
the right thing here).

Other places to fix it up like you do (with __builtin_uneachable ())
are in lowering a noreturn function (place a unreachable () instead of
a return stmt in the return block), the inliner (place a unreachable ()
on the exit edge) and fixup_cfg (where I put the endless loop in).

> But, really, why inline noreturn functions at all?

That's a good question.  The question then is, why not?

And the question still stands: is a BB without successor ok?

Thanks,
Richard.
Steven Bosscher - Oct. 25, 2012, 10:55 a.m.
On Thu, Oct 25, 2012 at 12:31 PM, Richard Biener <rguenther@suse.de> wrote:
>> But, really, why inline noreturn functions at all?
>
> That's a good question.  The question then is, why not?

Because noreturn functions are usually on error paths. To inline a
called noreturn function is to drag overhead into the caller,
potentially resulting in poorer icache behavior, increased code size,
...

But I suppose inlining things like wrappers around exit() and abort()
should be a win. Maybe a noreturn function should get a size/time
penalty to avoid inlining relatively large noreturn functions.

> And the question still stands: is a BB without successor ok?

Yes, this is OK.

Ciao!
Steven
Richard Guenther - Oct. 25, 2012, 10:58 a.m.
On Thu, 25 Oct 2012, Steven Bosscher wrote:

> On Thu, Oct 25, 2012 at 12:31 PM, Richard Biener <rguenther@suse.de> wrote:
> >> But, really, why inline noreturn functions at all?
> >
> > That's a good question.  The question then is, why not?
> 
> Because noreturn functions are usually on error paths. To inline a
> called noreturn function is to drag overhead into the caller,
> potentially resulting in poorer icache behavior, increased code size,
> ...
> 
> But I suppose inlining things like wrappers around exit() and abort()
> should be a win. Maybe a noreturn function should get a size/time
> penalty to avoid inlining relatively large noreturn functions.

In this case the function is empty ;)  Btw, even without inlining it
in the LTO case we may discover it is after all not noreturn and
thus face the same situation - a non-noreturn call ending a basic
block with no successor edges.

> > And the question still stands: is a BB without successor ok?
> 
> Yes, this is OK.

So the bug here is really in find_many_sub_basic_blocks then
and your patch would certainly avoid triggering its bug
(or its wrong expectations).  I'll give it testing.

Richard.
Jakub Jelinek - Oct. 25, 2012, 12:15 p.m.
On Thu, Oct 25, 2012 at 12:58:26PM +0200, Richard Biener wrote:
> So the bug here is really in find_many_sub_basic_blocks then
> and your patch would certainly avoid triggering its bug
> (or its wrong expectations).  I'll give it testing.

I'd say we should insert the __builtin_unreachable already far earlier than
that, either when inlining the noreturn function and figuring out
it might return (perhaps conditionally on something that never happens),
or if LTO does something similar with it even without inlining.

	Jakub
Richard Guenther - Oct. 25, 2012, 12:31 p.m.
On Thu, 25 Oct 2012, Jakub Jelinek wrote:

> On Thu, Oct 25, 2012 at 12:58:26PM +0200, Richard Biener wrote:
> > So the bug here is really in find_many_sub_basic_blocks then
> > and your patch would certainly avoid triggering its bug
> > (or its wrong expectations).  I'll give it testing.
> 
> I'd say we should insert the __builtin_unreachable already far earlier than
> that, either when inlining the noreturn function and figuring out
> it might return (perhaps conditionally on something that never happens),
> or if LTO does something similar with it even without inlining.

That would be fixup_cfg which is supposed to deal with this kind of
"fallout", like in my original patch (just using __builtin_unreachable ()
instead of an infinite loop edge)
  
Honza?

Richard.
Richard Guenther - Oct. 25, 2012, 1:34 p.m.
On Thu, 25 Oct 2012, Richard Biener wrote:

> On Thu, 25 Oct 2012, Jakub Jelinek wrote:
> 
> > On Thu, Oct 25, 2012 at 12:58:26PM +0200, Richard Biener wrote:
> > > So the bug here is really in find_many_sub_basic_blocks then
> > > and your patch would certainly avoid triggering its bug
> > > (or its wrong expectations).  I'll give it testing.
> > 
> > I'd say we should insert the __builtin_unreachable already far earlier than
> > that, either when inlining the noreturn function and figuring out
> > it might return (perhaps conditionally on something that never happens),
> > or if LTO does something similar with it even without inlining.
> 
> That would be fixup_cfg which is supposed to deal with this kind of
> "fallout", like in my original patch (just using __builtin_unreachable ()
> instead of an infinite loop edge)
>   
> Honza?

Like the following, bootstrap & regtest pending on 
x86_64-unknown-linux-gnu.

Richard.

2012-10-15  Richard Biener  <rguenther@suse.de>

	PR middle-end/54824
	* tree-optimize.c (execute_fixup_cfg): Insert __builtin_unreachable
	at the end of blocks with no successors.

	* gcc.dg/torture/pr54824.c: New testcase.

Index: gcc/tree-optimize.c
===================================================================
*** gcc/tree-optimize.c	(revision 192803)
--- gcc/tree-optimize.c	(working copy)
*************** execute_fixup_cfg (void)
*** 180,185 ****
--- 180,204 ----
        FOR_EACH_EDGE (e, ei, bb->succs)
          e->count = (e->count * count_scale
  		    + REG_BR_PROB_BASE / 2) / REG_BR_PROB_BASE;
+ 
+       /* If we have a basic-block with no successors that does not
+ 	 end with a control statement or a noreturn call connect it
+ 	 to itself.  This situation can occur when inlining a noreturn
+ 	 call that does in fact return.  */
+       if (EDGE_COUNT (bb->succs) == 0)
+ 	{
+ 	  gimple stmt = last_stmt (bb);
+ 	  if (!stmt
+ 	      || (!is_ctrl_stmt (stmt)
+ 		  && (!is_gimple_call (stmt)
+ 		      || (gimple_call_flags (stmt) & ECF_NORETURN) == 0)))
+ 	    {
+ 	      stmt = gimple_build_call
+ 		  (builtin_decl_implicit (BUILT_IN_UNREACHABLE), 0);
+ 	      gimple_stmt_iterator gsi = gsi_last_bb (bb);
+ 	      gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
+ 	    }
+ 	}
      }
    if (count_scale != REG_BR_PROB_BASE)
      compute_function_frequency ();
Index: gcc/testsuite/gcc.dg/torture/pr54824.c
===================================================================
*** gcc/testsuite/gcc.dg/torture/pr54824.c	(revision 0)
--- gcc/testsuite/gcc.dg/torture/pr54824.c	(working copy)
***************
*** 0 ****
--- 1,16 ----
+ /* { dg-do compile } */
+ /* { dg-options "-w" } */
+ 
+ void __attribute__((noreturn)) bar(void)
+ {
+ }
+ 
+ void foo(int i, char *p, char *q)
+ {
+   while (*p++) {
+       if (i)
+ 	p++;
+       if (!*q++)
+ 	bar();
+   }
+ }
Steven Bosscher - Oct. 25, 2012, 1:41 p.m.
On Thu, Oct 25, 2012 at 3:34 PM, Richard Biener <rguenther@suse.de> wrote:
> +
> +       /* If we have a basic-block with no successors that does not
> +        end with a control statement or a noreturn call connect it
> +        to itself.  This situation can occur when inlining a noreturn
> +        call that does in fact return.  */

Might want to update the comment.

Ciao!
Steven
Eric Botcazou - Oct. 25, 2012, 2 p.m.
> +       /* If we have a basic-block with no successors that does not
> + 	 end with a control statement or a noreturn call connect it
> + 	 to itself.  This situation can occur when inlining a noreturn
> + 	 call that does in fact return.  */

The '-' is superfluous in basic-block.  And the comment seems to be outdated.

Patch

Index: cfgexpand.c
===================================================================
--- cfgexpand.c (revision 192696)
+++ cfgexpand.c (working copy)
@@ -3989,6 +3989,12 @@  expand_gimple_basic_block (basic_block b

   do_pending_stack_adjust ();

+  /* If this block has no successors at all, make sure that
+     find_many_sub_basic_blocks does not connect this "dead end"
+     to the rest of the function.  */
+  if (EDGE_COUNT (bb->succs) == 0)
+    expand_builtin_unreachable ();
+
   /* Find the block tail.  The last insn in the block is the insn
      before a barrier and/or table jump insn.  */
   last = get_last_insn ();