decrement_and_branch_until_zero pattern

decrement_and_branch_until_zero pattern

[Paul Koning]

I'm a bit puzzled by the decrement_and_branch_until_zero looping pattern.  The manual described it as a named pattern, through from the description it isn't clear that it's referenced by name.  I see those only in m68k and pa.  There are similar looking but anonymous patterns in pdp11 and vax, suggesting that those were meant to be recognized by their structure.

One puzzle is that the body of gcc doesn't reference that pattern name as far as I can see.

The other puzzle is that I see no sign that the pattern works.  I made up my own simple test file and I can't get pdp11, vax, or m68k to generate a loop using that pattern.  Stranger yet, there is a test case gcc.c-torture/execution/dbra-1.c -- a name that suggests it's meant to test this mechanism because dbra is the m68k name for the relevant instruction.  That test case doesn't generate these looping instructions either (I tried those also with m68k, vax, pdp11).  Finally, I tried that file with an old 4.8.0 build for pdp11 I happened to have lying around.

None of these seem to use that loop optimization, with -O2 or -Os.  Did I miss some magic switch to turn on something else that isn't on by default?  Or is this a feature that was broken long ago and not noticed?  If so, any hints where I might look for a reason?

	paul

Re: decrement_and_branch_until_zero pattern

[Andreas Schwab]

On Jun 07 2018, Paul Koning <paulkoning@comcast.net> wrote:

> None of these seem to use that loop optimization, with -O2 or -Os.  Did I
> miss some magic switch to turn on something else that isn't on by default?
> Or is this a feature that was broken long ago and not noticed?  If so, any
> hints where I might look for a reason?

commit 7d3c6452d7
Author: rakdver <rakdver@138bc75d-0d04-0410-961f-82ee72b054a4>
Date:   Thu Mar 2 23:50:55 2006 +0000

            * loop.c: Removed.
    
    
    
    git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@111650 138bc75d-0d04-0410-961f-82ee72b054a4

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

Re: decrement_and_branch_until_zero pattern

[Paul Koning]

> On Jun 8, 2018, at 6:59 AM, Andreas Schwab <schwab@linux-m68k.org> wrote:
> 
> On Jun 07 2018, Paul Koning <paulkoning@comcast.net> wrote:
> 
>> None of these seem to use that loop optimization, with -O2 or -Os.  Did I
>> miss some magic switch to turn on something else that isn't on by default?
>> Or is this a feature that was broken long ago and not noticed?  If so, any
>> hints where I might look for a reason?
> 
> commit 7d3c6452d7
> Author: rakdver <rakdver@138bc75d-0d04-0410-961f-82ee72b054a4>
> Date:   Thu Mar 2 23:50:55 2006 +0000
> 
>            * loop.c: Removed.

Interesting.  The ChangeLog doesn't give any background.  I suppose I should plan to approximate the effect of this pattern with a define-peephole2 ?  

	paul

Re: decrement_and_branch_until_zero pattern

[Jim Wilson]

On 06/08/2018 06:21 AM, Paul Koning wrote:
> Interesting.  The ChangeLog doesn't give any background.  I suppose I should plan to approximate the effect of this pattern with a define-peephole2 ?

The old RTL loop optimizer was replaced with a new RTL loop optimizer. 
When the old one was written, m68k was a major target, and the dbra 
optimization was written for it.  When the new one was written, m68k was 
not a major target, and this support was written differently.  We now 
have doloop_begin and doloop_end patterns that do almost the same thing, 
and can be created by the loop-doloop.c code.

There is a section in the internals docs that talks about this.
https://gcc.gnu.org/onlinedocs/gccint/Looping-Patterns.html

The fact that we still have decrement_and_branch_until_zero references 
in docs and target md files looks like a bug.  The target md files 
should use doloop patterns instead, and the doc references should be 
dropped.

Jim

Re: decrement_and_branch_until_zero pattern

[Paul Koning]

> On Jun 8, 2018, at 2:29 PM, Jim Wilson <jimw@sifive.com> wrote:
> 
> On 06/08/2018 06:21 AM, Paul Koning wrote:
>> Interesting.  The ChangeLog doesn't give any background.  I suppose I should plan to approximate the effect of this pattern with a define-peephole2 ?
> 
> The old RTL loop optimizer was replaced with a new RTL loop optimizer. When the old one was written, m68k was a major target, and the dbra optimization was written for it.  When the new one was written, m68k was not a major target, and this support was written differently.  We now have doloop_begin and doloop_end patterns that do almost the same thing, and can be created by the loop-doloop.c code.
> 
> There is a section in the internals docs that talks about this.
> https://gcc.gnu.org/onlinedocs/gccint/Looping-Patterns.html
> 
> The fact that we still have decrement_and_branch_until_zero references in docs and target md files looks like a bug.  The target md files should use doloop patterns instead, and the doc references should be dropped.

Thanks.  I saw those sections and interpreted them as support for signal processor style fast hardware loops.  If they can be adapted for dbra type looping, great.  I'll give that a try.

Meanwhile, yes, it looks like there is a documentation bug.  I can clean that up.  It's more than a few lines, but does that qualify for an "obvious" change?

	paul

Re: decrement_and_branch_until_zero pattern

[Jim Wilson]

On Fri, Jun 8, 2018 at 1:12 PM, Paul Koning <paulkoning@comcast.net> wrote:
> Thanks.  I saw those sections and interpreted them as support for signal processor style fast hardware loops.  If they can be adapted for dbra type looping, great.  I'll give that a try.

The rs6000 port uses it for bdnz (branch decrement not zero) for
instance, which is similar to the m68k dbra.

> Meanwhile, yes, it looks like there is a documentation bug.  I can clean that up.  It's more than a few lines, but does that qualify for an "obvious" change?

I think the obvious rule should only apply to trivial patches, and
this will require some non-trivial changes to fix the looping pattern
section.  Just deleting the decrement_and_branch_until_zero named
pattern section looks trivial.  It looks like the REG_NONNEG section
should  mention the doloop_end pattern instead of
decrement_and_branch_until_zero, since I think the same rule applies
that they only get generated if the doloop_end pattern exists.

Jim

Re: decrement_and_branch_until_zero pattern

[Paul Koning]

> On Jun 8, 2018, at 6:16 PM, Jim Wilson <jimw@sifive.com> wrote:
> 
> On Fri, Jun 8, 2018 at 1:12 PM, Paul Koning <paulkoning@comcast.net> wrote:
>> Thanks.  I saw those sections and interpreted them as support for signal processor style fast hardware loops.  If they can be adapted for dbra type looping, great.  I'll give that a try.
> 
> The rs6000 port uses it for bdnz (branch decrement not zero) for
> instance, which is similar to the m68k dbra.
> 
>> Meanwhile, yes, it looks like there is a documentation bug.  I can clean that up.  It's more than a few lines, but does that qualify for an "obvious" change?
> 
> I think the obvious rule should only apply to trivial patches, and
> this will require some non-trivial changes to fix the looping pattern
> section.  Just deleting the decrement_and_branch_until_zero named
> pattern section looks trivial.  It looks like the REG_NONNEG section
> should  mention the doloop_end pattern instead of
> decrement_and_branch_until_zero, since I think the same rule applies
> that they only get generated if the doloop_end pattern exists.

It appears that doloop_end doesn't get a REG_NONNEG pattern.  I just added doloop_end to my target and I don't see any such note in the RTL dumps.

By the way, the documentation makes it clear that the register used in the doloop isn't available as an "induction variable".  I wonder if there is a way to make that restriction go away, since my target -- and I suspect several others as well -- use a general register for the loop control.  So as far as the target is concerned the loop control register is definitely available.  I understand the original restriction for machines like DSPs that loop using special-purpose loop registers, but that isn't a universal limitation.

	paul