Re: [PATCH 2/2] shrink-wrap: Rewrite try_shrink_wrapping

[H.J. Lu]

On Thu, Sep 10, 2015 at 8:14 AM, Segher Boessenkool
 wrote:
> This patch rewrites the shrink-wrapping algorithm, allowing non-linear
> pieces of CFG to be duplicated for use without prologue instead of just
> linear pieces.
>
> On PowerPC, this enables shrink-wrapping of about 2%-3% more functions.
> I expected more, but in most cases this would help we cannot yet shrink-
> wrap because there are non-volatile registers used, often in the first
> block already.
>
> Since with this patch you still get only one prologue, it doesn't do
> much either for the case where there are many no-return error paths
> (common in an enable-checking compiler build); all those paths end in
> a no-return call, and those need a prologue (are not sibling calls).
> There are PRs about this.  For shrink-wrapping, because all those
> paths want a prologue we put a prologue early in the function, although
> none of the "regular" code needs it.
>
> I instrumented things a bit (not in the patch).  We can get about 10%
> to 20% more functions shrink-wrapped by allowing multiple edges that
> need a prologue inserted (edges to one and the same block); this can be
> easily done by just inserting an extra block.  I'll work on this.
>
> Of the blocks chosen to have the prologue inserted, about 70% need a
> prologue because there is a call, 25% for other reasons (non-volatile
> register sets mostly), and only 5% do not themselves need a prologue.
>
> There are also cases where no block needs a prologue at all, but GCC
> thinks the function needs one nevertheless.  This happens for example
> if a stack frame was created for an address-taken local variable, but
> that variable was optimised away later.  This doesn't happen much in
> most cases (one in a thousand or so).  There are some cases (like -pg)
> where the compiler forces a stack frame even if nothing uses it.
>
> Shrink-wrapping is run at -O1, and basic block reordering is not.
> Shrink-wrapping would often benefit from some simple reordering.  There
> are quite a few targets that do not want the STC bbro at all, either;
> we should have a simple bbro that runs at -O1 as well, does not increase
> code size, and can be used for those targets that do not want STC.
>
> It also would be nice to get rid of the silly games shrink-wrapping
> plays (together with function.c) making fake edges for where the
> simple_returns should be inserted.  It would simplify a lot of code
> if we would (could) just insert them directly.
>
> Bootstrapped and regression tested on powerpc64-linux.  Is this okay
> for mainline?
>
>
> Segher
>
>
> 2015-09-10  Segher Boessenkool  
>
> * shrink-wrap.c (requires_stack_frame_p): Fix formatting.
> (dup_block_and_redirect): Delete function.
> (can_dup_for_shrink_wrapping): New function.
> (fix_fake_fallthrough_edge): New function.
> (try_shrink_wrapping): Rewrite function.
> (convert_to_simple_return): Call fix_fake_fallthrough_edge.
>

This caused:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67587


H.J.

Re: [PATCH 2/2] shrink-wrap: Rewrite try_shrink_wrapping

[Segher Boessenkool]

On Fri, Sep 11, 2015 at 03:40:53PM +0100, Jiong Wang wrote:
> >> A quick check shows > 30% more functions shrink-wrapped during
> >> bootstrapping by a the following command:
> >> 
> >> cd $TOP_BUILD ; find . -name "*.pro_and_epilogue" | xargs grep 
> >> "Perform.*shrink" | wc -l
> >
> > Wow, that is a lot!  But this is mostly the testsuite?  Shorter functions
> > can be wrapped a whole lot more often.
> 
> They all comes from gcc source code, not from testsuite as my bootstrap
> command is "make BOOT_CFLAGS=-O2 -fdump-rtl-pro_and_epilogue". testsuite
> itself is not involved in bootstrap.
> 
> And I can confirm I get >30% more functions shrink-wrapped by
> 
> cd $TOP_BUILD/gcc ; grep "Perform.*shrink" *.pro_and_epilogue | wc -l
> 
> This only count shrink-wrap performed on gcc core source code during
> final stage in bootstrapping. I also do some quick check, new
> shrink-wrap opportunites come from files like dwarf2out.c, emit-rtl.c,
> tree.c, tree-into-ssa.c etc, so they are valid.

It turns out for powerpc64-linux this particular "benchmark" shows 7.4%
increase as well, much more than average code.  Something in GCC code
likes shrink-wrapping a lot, maybe all the checking code.

> I know shrink-wrap is very sensitive to the RTL instruction sequences,
> looks like your re-write make it much more friendly to AArch64 :)

Yes indeed.  I wonder what it is about AArch64 code gen :-)

The old algorithm gave up if any block that would need duplicating could
not in fact be duplicated; the new one does not (it places the prologue
earlier and tries again).  Maybe that explains (some of) it.


Segher

Re: [PATCH 2/2] shrink-wrap: Rewrite try_shrink_wrapping

[Bernd Schmidt]

On 09/10/2015 05:14 PM, Segher Boessenkool wrote:

This patch rewrites the shrink-wrapping algorithm, allowing non-linear
pieces of CFG to be duplicated for use without prologue instead of just
linear pieces.


An example would be good for this kind of patch, also in the comments.



-  add_to_hard_reg_set (, GET_MODE (dreg),
-  REGNO (dreg));
+  add_to_hard_reg_set (, GET_MODE (dreg), REGNO (dreg));
  }


In general please try to avoid mixing formatting changes with functional 
ones. No need to remove these ones from future versions of the patch though.



+  /* If there is more than one predecessor of PRO not dominated by PRO,
+ fail.  We don't have to do this (can split the block), but do this
+ for now (the original code disallowed this, too).


Comments shouldn't reference previous versions. Also, a comment 
describing the why rather than just what is being done would be more 
helpful.


I'm wondering how your new algorithm prevents the prologue from being 
placed inside a loop. Can you have a situation where this picks a 
predecessor that is reachable but not dominated by PRO?



+  int num = (*entry_edge)->probability;
+  int den = REG_BR_PROB_BASE;
+
+
+  if (*entry_edge == orig_entry_edge)
+goto out;


There are a couple of places where there are multiple blank lines. I 
think we avoid that.



+   FOR_EACH_EDGE (e, ei, src->succs)
+ {
+   if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
  {
-   all_set = false;
-   break;
  }


Minor, but I'd prefer a continue rather than an empty { } block.

Other than that it looks pretty good.


Bernd

Re: [PATCH 2/2] shrink-wrap: Rewrite try_shrink_wrapping

[Jiong Wang]

Segher Boessenkool writes:

> On Thu, Sep 10, 2015 at 08:14:29AM -0700, Segher Boessenkool wrote:
>> This patch rewrites the shrink-wrapping algorithm, allowing non-linear
>> pieces of CFG to be duplicated for use without prologue instead of just
>> linear pieces.
>
>> Bootstrapped and regression tested on powerpc64-linux.  Is this okay
>> for mainline?
>
> Now also bootstrapped and regression tested on x86_64-linux.

+ AArch64 boostrapping OK.

A quick check shows > 30% more functions shrink-wrapped during
bootstrapping by a the following command:

cd $TOP_BUILD ; find . -name "*.pro_and_epilogue" | xargs grep 
"Perform.*shrink" | wc -l

-- 
Regards,
Jiong

Re: [PATCH 2/2] shrink-wrap: Rewrite try_shrink_wrapping

[Segher Boessenkool]

On Fri, Sep 11, 2015 at 10:24:42AM +0100, Jiong Wang wrote:
> 
> Segher Boessenkool writes:
> 
> > On Thu, Sep 10, 2015 at 08:14:29AM -0700, Segher Boessenkool wrote:
> >> This patch rewrites the shrink-wrapping algorithm, allowing non-linear
> >> pieces of CFG to be duplicated for use without prologue instead of just
> >> linear pieces.
> >
> >> Bootstrapped and regression tested on powerpc64-linux.  Is this okay
> >> for mainline?
> >
> > Now also bootstrapped and regression tested on x86_64-linux.
> 
> + AArch64 boostrapping OK.

Thank you for testing!

> A quick check shows > 30% more functions shrink-wrapped during
> bootstrapping by a the following command:
> 
> cd $TOP_BUILD ; find . -name "*.pro_and_epilogue" | xargs grep 
> "Perform.*shrink" | wc -l

Wow, that is a lot!  But this is mostly the testsuite?  Shorter functions
can be wrapped a whole lot more often.


Segher

Re: [PATCH 2/2] shrink-wrap: Rewrite try_shrink_wrapping

[Segher Boessenkool]

On Fri, Sep 11, 2015 at 11:19:40AM +0200, Bernd Schmidt wrote:
> On 09/10/2015 05:14 PM, Segher Boessenkool wrote:
> >This patch rewrites the shrink-wrapping algorithm, allowing non-linear
> >pieces of CFG to be duplicated for use without prologue instead of just
> >linear pieces.
> 
> An example would be good for this kind of patch, also in the comments.

I'll make up something for v2.

> >+  /* If there is more than one predecessor of PRO not dominated by PRO,
> >+ fail.  We don't have to do this (can split the block), but do this
> >+ for now (the original code disallowed this, too).
> 
> Comments shouldn't reference previous versions. Also, a comment 
> describing the why rather than just what is being done would be more 
> helpful.

I'll just remove that second sentence, it just describes what we do not
yet do.

> I'm wondering how your new algorithm prevents the prologue from being 
> placed inside a loop. Can you have a situation where this picks a 
> predecessor that is reachable but not dominated by PRO?

It doesn't prevent it!

The prologue will not be _inside_ the loop: there is one prologue, and it
is executed exactly once for any block needing it.  But the code can copy
part of the first iteration of a loop, if there are early exits.  Example
(from the testsuite, pr39943.c, -Os I think):

(_B_egin, _R_eturn, _S_imple_return; edges without arrowhead are down or
to the right, to simplify the diagram):

Block 3 needs a prologue (it has a call), the rest doesn't:



  B   3<--  B   ->3<--
  |   |   | |  |  |   |
  |   v   |   becomes   |  |  v   |
  2---4---  2---5--   4---
  | | |
  R S R


by copying bb 4 to bb 5, and inserting the prologue on the edge 5->3.

> Other than that it looks pretty good.

Thanks, and thanks for the review!  I'll send v2 later today.


Segher

Re: [PATCH 2/2] shrink-wrap: Rewrite try_shrink_wrapping

[Bernd Schmidt]

On 09/11/2015 02:36 PM, Segher Boessenkool wrote:


I'm wondering how your new algorithm prevents the prologue from being
placed inside a loop. Can you have a situation where this picks a
predecessor that is reachable but not dominated by PRO?


It doesn't prevent it!

The prologue will not be _inside_ the loop: there is one prologue, and it
is executed exactly once for any block needing it.  But the code can copy
part of the first iteration of a loop, if there are early exits.  Example
(from the testsuite, pr39943.c, -Os I think):


I was wondering if that was the intention. This also ought to be spelled 
out in the comments.



Bernd

Re: [PATCH 2/2] shrink-wrap: Rewrite try_shrink_wrapping

[Jiong Wang]

Segher Boessenkool writes:

> On Fri, Sep 11, 2015 at 10:24:42AM +0100, Jiong Wang wrote:
>> 
>> Segher Boessenkool writes:
>> 
>> > On Thu, Sep 10, 2015 at 08:14:29AM -0700, Segher Boessenkool wrote:
>> >> This patch rewrites the shrink-wrapping algorithm, allowing non-linear
>> >> pieces of CFG to be duplicated for use without prologue instead of just
>> >> linear pieces.
>> >
>> >> Bootstrapped and regression tested on powerpc64-linux.  Is this okay
>> >> for mainline?
>> >
>> > Now also bootstrapped and regression tested on x86_64-linux.
>> 
>> + AArch64 boostrapping OK.
>
> Thank you for testing!
>
>> A quick check shows > 30% more functions shrink-wrapped during
>> bootstrapping by a the following command:
>> 
>> cd $TOP_BUILD ; find . -name "*.pro_and_epilogue" | xargs grep 
>> "Perform.*shrink" | wc -l
>
> Wow, that is a lot!  But this is mostly the testsuite?  Shorter functions
> can be wrapped a whole lot more often.

They all comes from gcc source code, not from testsuite as my bootstrap
command is "make BOOT_CFLAGS=-O2 -fdump-rtl-pro_and_epilogue". testsuite
itself is not involved in bootstrap.

And I can confirm I get >30% more functions shrink-wrapped by

cd $TOP_BUILD/gcc ; grep "Perform.*shrink" *.pro_and_epilogue | wc -l

This only count shrink-wrap performed on gcc core source code during
final stage in bootstrapping. I also do some quick check, new
shrink-wrap opportunites come from files like dwarf2out.c, emit-rtl.c,
tree.c, tree-into-ssa.c etc, so they are valid.

I know shrink-wrap is very sensitive to the RTL instruction sequences,
looks like your re-write make it much more friendly to AArch64 :)

-- 
Regards,
Jiong

Re: [PATCH 2/2] shrink-wrap: Rewrite try_shrink_wrapping

[Segher Boessenkool]

On Thu, Sep 10, 2015 at 04:22:34PM +0100, Jiong Wang wrote:
> 
> Segher Boessenkool writes:
> 
> > 2015-09-10  Segher Boessenkool  
> >
> > * shrink-wrap.c (requires_stack_frame_p): Fix formatting.
> > (dup_block_and_redirect): Delete function.
> > (can_dup_for_shrink_wrapping): New function.
> > (fix_fake_fallthrough_edge): New function.
> > (try_shrink_wrapping): Rewrite function.
> > (convert_to_simple_return): Call fix_fake_fallthrough_edge.
> 
> I am interested in the impact on AArch64, but the patch attached can't
> apply on trunk cleanly after I apply your [1/2], the .rej is quite big.

I rebased it to trunk only yesterday.   Huh.  I'll have a look.

[PATCH 2/2] shrink-wrap: Rewrite try_shrink_wrapping

[Segher Boessenkool]

This patch rewrites the shrink-wrapping algorithm, allowing non-linear
pieces of CFG to be duplicated for use without prologue instead of just
linear pieces.

On PowerPC, this enables shrink-wrapping of about 2%-3% more functions.
I expected more, but in most cases this would help we cannot yet shrink-
wrap because there are non-volatile registers used, often in the first
block already.

Since with this patch you still get only one prologue, it doesn't do
much either for the case where there are many no-return error paths
(common in an enable-checking compiler build); all those paths end in
a no-return call, and those need a prologue (are not sibling calls).
There are PRs about this.  For shrink-wrapping, because all those
paths want a prologue we put a prologue early in the function, although
none of the "regular" code needs it.

I instrumented things a bit (not in the patch).  We can get about 10%
to 20% more functions shrink-wrapped by allowing multiple edges that
need a prologue inserted (edges to one and the same block); this can be
easily done by just inserting an extra block.  I'll work on this.

Of the blocks chosen to have the prologue inserted, about 70% need a
prologue because there is a call, 25% for other reasons (non-volatile
register sets mostly), and only 5% do not themselves need a prologue.

There are also cases where no block needs a prologue at all, but GCC
thinks the function needs one nevertheless.  This happens for example
if a stack frame was created for an address-taken local variable, but
that variable was optimised away later.  This doesn't happen much in
most cases (one in a thousand or so).  There are some cases (like -pg)
where the compiler forces a stack frame even if nothing uses it.

Shrink-wrapping is run at -O1, and basic block reordering is not.
Shrink-wrapping would often benefit from some simple reordering.  There
are quite a few targets that do not want the STC bbro at all, either;
we should have a simple bbro that runs at -O1 as well, does not increase
code size, and can be used for those targets that do not want STC.

It also would be nice to get rid of the silly games shrink-wrapping
plays (together with function.c) making fake edges for where the
simple_returns should be inserted.  It would simplify a lot of code
if we would (could) just insert them directly.

Bootstrapped and regression tested on powerpc64-linux.  Is this okay
for mainline?


Segher


2015-09-10  Segher Boessenkool  

* shrink-wrap.c (requires_stack_frame_p): Fix formatting.
(dup_block_and_redirect): Delete function.
(can_dup_for_shrink_wrapping): New function.
(fix_fake_fallthrough_edge): New function.
(try_shrink_wrapping): Rewrite function.
(convert_to_simple_return): Call fix_fake_fallthrough_edge.

---
 gcc/shrink-wrap.c | 762 --
 1 file changed, 395 insertions(+), 367 deletions(-)

diff --git a/gcc/shrink-wrap.c b/gcc/shrink-wrap.c
index 0ece4cf..63866b0 100644
--- a/gcc/shrink-wrap.c
+++ b/gcc/shrink-wrap.c
@@ -91,8 +91,7 @@ requires_stack_frame_p (rtx_insn *insn, HARD_REG_SET 
prologue_used,
   if (!REG_P (dreg))
continue;
 
-  add_to_hard_reg_set (, GET_MODE (dreg),
-  REGNO (dreg));
+  add_to_hard_reg_set (, GET_MODE (dreg), REGNO (dreg));
 }
   if (hard_reg_set_intersect_p (hardregs, prologue_used))
 return true;
@@ -463,414 +462,441 @@ prepare_shrink_wrap (basic_block entry_block)
   }
 }
 
-/* Create a copy of BB instructions and insert at BEFORE.  Redirect
-   preds of BB to COPY_BB if they don't appear in NEED_PROLOGUE.  */
-static void
-dup_block_and_redirect (basic_block bb, basic_block copy_bb, rtx_insn *before,
-   bitmap_head *need_prologue)
+/* Return whether we can duplicate basic block BB for shrink wrapping.  We
+   cannot if the block cannot be duplicated at all, or if any of its incoming
+   edges are complex and come from a block that does not require a prologue
+   (we cannot redirect such edges), or if the block is too big to copy.
+   PRO is the basic block before which we would put the prologue, MAX_SIZE is
+   the maximum size block we allow to be copied.  */
+
+static bool
+can_dup_for_shrink_wrapping (basic_block bb, basic_block pro, unsigned 
max_size)
 {
-  edge_iterator ei;
-  edge e;
-  rtx_insn *insn = BB_END (bb);
+  if (!can_duplicate_block_p (bb))
+return false;
 
-  /* We know BB has a single successor, so there is no need to copy a
- simple jump at the end of BB.  */
-  if (simplejump_p (insn))
-insn = PREV_INSN (insn);
+  edge e;
+  edge_iterator ei;
+  FOR_EACH_EDGE (e, ei, bb->preds)
+if (e->flags & EDGE_COMPLEX
+   && !dominated_by_p (CDI_DOMINATORS, e->src, pro))
+  return false;
 
-  start_sequence ();
-  duplicate_insn_chain (BB_HEAD (bb), insn);
-  if (dump_file)
-{
-  unsigned count = 0;
-  for (insn = 

Re: [PATCH 2/2] shrink-wrap: Rewrite try_shrink_wrapping

[Jiong Wang]

Segher Boessenkool writes:

> 2015-09-10  Segher Boessenkool  
>
> * shrink-wrap.c (requires_stack_frame_p): Fix formatting.
> (dup_block_and_redirect): Delete function.
> (can_dup_for_shrink_wrapping): New function.
> (fix_fake_fallthrough_edge): New function.
> (try_shrink_wrapping): Rewrite function.
> (convert_to_simple_return): Call fix_fake_fallthrough_edge.

I am interested in the impact on AArch64, but the patch attached can't
apply on trunk cleanly after I apply your [1/2], the .rej is quite big.

-- 
Regards,
Jiong

Re: [PATCH 2/2] shrink-wrap: Rewrite try_shrink_wrapping

[Segher Boessenkool]

On Thu, Sep 10, 2015 at 10:41:53AM -0500, Segher Boessenkool wrote:
> > > * shrink-wrap.c (requires_stack_frame_p): Fix formatting.
> > > (dup_block_and_redirect): Delete function.
> > > (can_dup_for_shrink_wrapping): New function.
> > > (fix_fake_fallthrough_edge): New function.
> > > (try_shrink_wrapping): Rewrite function.
> > > (convert_to_simple_return): Call fix_fake_fallthrough_edge.
> > 
> > I am interested in the impact on AArch64, but the patch attached can't
> > apply on trunk cleanly after I apply your [1/2], the .rej is quite big.
> 
> I rebased it to trunk only yesterday.   Huh.  I'll have a look.

The patch (taken from the email) applies to trunk just fine for me,
both using git-am and patch.


Segher

Re: [PATCH 2/2] shrink-wrap: Rewrite try_shrink_wrapping

[Segher Boessenkool]

On Thu, Sep 10, 2015 at 08:14:29AM -0700, Segher Boessenkool wrote:
> This patch rewrites the shrink-wrapping algorithm, allowing non-linear
> pieces of CFG to be duplicated for use without prologue instead of just
> linear pieces.

> Bootstrapped and regression tested on powerpc64-linux.  Is this okay
> for mainline?

Now also bootstrapped and regression tested on x86_64-linux.


Segher