Branch instructions that depend on target distance

Branch instructions that depend on target distance

[Petr Tesarik]

[-- Attachment #1: Type: text/plain, Size: 1805 bytes --]

Hi all,

I'm looking into reviving the efforts to port gcc to VideoCore IV [1].
One issue I've run into is the need to find out target branch distance
at compile time. I looked around, and it's not the first one
architecture with such requirement, but AFAICS it has never been solved
properly.

For example, AVR tracks instruction length. Later, ret_cond_branch()
selects between a branch instruction and an inverted branch followed by
an unconditional jump based on these calculated lengths.

This works great ... until there's some inline asm() statement, for
which gcc cannot keep track of the length attribute, so it is probably
taken as zero. Linker then fails with a cryptic message:

> relocation truncated to fit: R_AVR_7_PCREL against `no symbol'

I can provide a minimal test case and report a bug if you want...

Developers work around the issue by rewriting their code when they are
bitten by this, but it is less than optimal, because you cannot really
get rid of all inline assembly, and it's in general unpredictable where
these inline asm() blocks will be placed by the compiler.

OTOH, the avr backend is pretty outdated, so there may be a better
alternative that I'm just not seeing. Any hints?

Background: There is a port of the VC4 port of the LK embedded kernel
[2]. I have tried to build that kernel with optimization turned on, but
I'm getting:

compiling kernel/thread.c
/tmp/ccJFdnfX.s: Assembler messages:
/tmp/ccJFdnfX.s:1451: Error: operand out of range (64 not between -64 and 63)

That's because there is an inline "di" (disable interrupts) instruction
inside a conditional statement in thread_yield(), which causes this
off-by-one miscalculation.

Petr T

[1] https://github.com/itszor/gcc-vc4
[2] https://github.com/librerpi/lk

[-- Attachment #2: Digitální podpis OpenPGP --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: Branch instructions that depend on target distance

[Jozef Lawrynowicz]

On Mon, 24 Feb 2020 12:05:28 +0100
Petr Tesarik <ptesarik@suse.cz> wrote:

> Hi all,
> 
> I'm looking into reviving the efforts to port gcc to VideoCore IV [1].
> One issue I've run into is the need to find out target branch distance
> at compile time. I looked around, and it's not the first one
> architecture with such requirement, but AFAICS it has never been solved
> properly.
> 
> For example, AVR tracks instruction length. Later, ret_cond_branch()
> selects between a branch instruction and an inverted branch followed by
> an unconditional jump based on these calculated lengths.
> 
> This works great ... until there's some inline asm() statement, for
> which gcc cannot keep track of the length attribute, so it is probably
> taken as zero. Linker then fails with a cryptic message:
> 
> > relocation truncated to fit: R_AVR_7_PCREL against `no symbol'  

The MSP430 backend just always generates maximum range branch instructions,
except for some special cases. We then rely on the linker to relax branch
instructions to shorter range "jump" instructions when the destination is
within range.

So the compiler output will always work, but not be the smallest possible code
size.

For that relocation truncated to fit error message you want to check that the
linker has the ability to relax whatever branch instruction it is failing on to
a longer range branch.

Jozef
> 
> I can provide a minimal test case and report a bug if you want...
> 
> Developers work around the issue by rewriting their code when they are
> bitten by this, but it is less than optimal, because you cannot really
> get rid of all inline assembly, and it's in general unpredictable where
> these inline asm() blocks will be placed by the compiler.
> 
> OTOH, the avr backend is pretty outdated, so there may be a better
> alternative that I'm just not seeing. Any hints?
> 
> Background: There is a port of the VC4 port of the LK embedded kernel
> [2]. I have tried to build that kernel with optimization turned on, but
> I'm getting:
> 
> compiling kernel/thread.c
> /tmp/ccJFdnfX.s: Assembler messages:
> /tmp/ccJFdnfX.s:1451: Error: operand out of range (64 not between -64 and 63)
> 
> That's because there is an inline "di" (disable interrupts) instruction
> inside a conditional statement in thread_yield(), which causes this
> off-by-one miscalculation.
> 
> Petr T
> 
> [1] https://github.com/itszor/gcc-vc4
> [2] https://github.com/librerpi/lk

Re: Branch instructions that depend on target distance

[Petr Tesarik]

[-- Attachment #1: Type: text/plain, Size: 3306 bytes --]

On Mon, 24 Feb 2020 11:14:44 +0000
Jozef Lawrynowicz <jozef.l@mittosystems.com> wrote:

> On Mon, 24 Feb 2020 12:05:28 +0100
> Petr Tesarik <ptesarik@suse.cz> wrote:
> 
> > Hi all,
> > 
> > I'm looking into reviving the efforts to port gcc to VideoCore IV [1].
> > One issue I've run into is the need to find out target branch distance
> > at compile time. I looked around, and it's not the first one
> > architecture with such requirement, but AFAICS it has never been solved
> > properly.
> > 
> > For example, AVR tracks instruction length. Later, ret_cond_branch()
> > selects between a branch instruction and an inverted branch followed by
> > an unconditional jump based on these calculated lengths.
> > 
> > This works great ... until there's some inline asm() statement, for
> > which gcc cannot keep track of the length attribute, so it is probably
> > taken as zero. Linker then fails with a cryptic message:
> >   
> > > relocation truncated to fit: R_AVR_7_PCREL against `no symbol'    
> 
> The MSP430 backend just always generates maximum range branch instructions,
> except for some special cases. We then rely on the linker to relax branch
> instructions to shorter range "jump" instructions when the destination is
> within range.
> 
> So the compiler output will always work, but not be the smallest possible code
> size.
> 
> For that relocation truncated to fit error message you want to check that the
> linker has the ability to relax whatever branch instruction it is failing on to
> a longer range branch.

But that would change the instruction length, so not really an option
AFAICS (unless I also switch to LTO).

Anyway, the situation is much worse on the VideoCore IV. The
alternatives here are:

1.
   addcmpbCC rx, 0, imm, target
   ; usually written as bCC rx, imm, target

2.
    cmp rx, imm
    bCC .+2
    j   target

The tricky part is that the addcmpbCC instruction does NOT modify
condition codes, while the cmp instruction does. Nothing you could
solve in the linker...

OK, it seems I'll have to go with the worst-case variant.

Petr T

> 
> Jozef
> > 
> > I can provide a minimal test case and report a bug if you want...
> > 
> > Developers work around the issue by rewriting their code when they
> > are bitten by this, but it is less than optimal, because you cannot
> > really get rid of all inline assembly, and it's in general
> > unpredictable where these inline asm() blocks will be placed by the
> > compiler.
> > 
> > OTOH, the avr backend is pretty outdated, so there may be a better
> > alternative that I'm just not seeing. Any hints?
> > 
> > Background: There is a port of the VC4 port of the LK embedded
> > kernel [2]. I have tried to build that kernel with optimization
> > turned on, but I'm getting:
> > 
> > compiling kernel/thread.c
> > /tmp/ccJFdnfX.s: Assembler messages:
> > /tmp/ccJFdnfX.s:1451: Error: operand out of range (64 not between
> > -64 and 63)
> > 
> > That's because there is an inline "di" (disable interrupts)
> > instruction inside a conditional statement in thread_yield(), which
> > causes this off-by-one miscalculation.
> > 
> > Petr T
> > 
> > [1] https://github.com/itszor/gcc-vc4
> > [2] https://github.com/librerpi/lk  
> 


[-- Attachment #2: Digitální podpis OpenPGP --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: Branch instructions that depend on target distance

[Jeff Law]

On Mon, 2020-02-24 at 12:36 +0100, Petr Tesarik wrote:
> On Mon, 24 Feb 2020 11:14:44 +0000
> Jozef Lawrynowicz <jozef.l@mittosystems.com> wrote:
> 
> > On Mon, 24 Feb 2020 12:05:28 +0100
> > Petr Tesarik <ptesarik@suse.cz> wrote:
> > 
> > > Hi all,
> > > 
> > > I'm looking into reviving the efforts to port gcc to VideoCore IV [1].
> > > One issue I've run into is the need to find out target branch distance
> > > at compile time. I looked around, and it's not the first one
> > > architecture with such requirement, but AFAICS it has never been solved
> > > properly.
> > > 
> > > For example, AVR tracks instruction length. Later, ret_cond_branch()
> > > selects between a branch instruction and an inverted branch followed by
> > > an unconditional jump based on these calculated lengths.
> > > 
> > > This works great ... until there's some inline asm() statement, for
> > > which gcc cannot keep track of the length attribute, so it is probably
> > > taken as zero. Linker then fails with a cryptic message:
> > >   
> > > > relocation truncated to fit: R_AVR_7_PCREL against `no symbol'    
> > 
> > The MSP430 backend just always generates maximum range branch instructions,
> > except for some special cases. We then rely on the linker to relax branch
> > instructions to shorter range "jump" instructions when the destination is
> > within range.
> > 
> > So the compiler output will always work, but not be the smallest possible code
> > size.
> > 
> > For that relocation truncated to fit error message you want to check that the
> > linker has the ability to relax whatever branch instruction it is failing on to
> > a longer range branch.
> 
> But that would change the instruction length, so not really an option
> AFAICS (unless I also switch to LTO).
> 
> Anyway, the situation is much worse on the VideoCore IV. The
> alternatives here are:
> 
> 1.
>    addcmpbCC rx, 0, imm, target
>    ; usually written as bCC rx, imm, target
> 
> 2.
>     cmp rx, imm
>     bCC .+2
>     j   target
Yea, this isn't that uncommon.  You can describe both of these to the
branch shortening pass.

> 
> The tricky part is that the addcmpbCC instruction does NOT modify
> condition codes, while the cmp instruction does. Nothing you could
> solve in the linker...
> 
> OK, it seems I'll have to go with the worst-case variant.
You can support both.  You output the short case when the target is
close enough and the longer variant otherwise.

Jeff

Re: Branch instructions that depend on target distance

[Andreas Schwab]

On Feb 24 2020, Petr Tesarik wrote:

> This works great ... until there's some inline asm() statement, for
> which gcc cannot keep track of the length attribute, so it is probably
> taken as zero.

GCC computes it by counting the number of asm insns.  You can use
ADJUST_INSN_LENGTH to adjust this as needed.

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: Branch instructions that depend on target distance

[Petr Tesarik]

[-- Attachment #1: Type: text/plain, Size: 873 bytes --]

On Mon, 24 Feb 2020 12:29:40 +0100
Andreas Schwab <schwab@suse.de> wrote:

> On Feb 24 2020, Petr Tesarik wrote:
> 
> > This works great ... until there's some inline asm() statement, for
> > which gcc cannot keep track of the length attribute, so it is probably
> > taken as zero.  
> 
> GCC computes it by counting the number of asm insns.  You can use
> ADJUST_INSN_LENGTH to adjust this as needed.

Hmm, that's interesting, but does it work for inline asm() statements?
The argument is essentially a free-form string (with some
substitution), and the compiler cannot know how many bytes they occupy.

Is there a way to set ADJUST_INSN_LENGTH in the asm() statement? Of
course, that would have to be inserted manually as some sort of
argument to asm() in the C code being compiled...

And yes, that would work for me if it is implemented.

Petr T

[-- Attachment #2: Digitální podpis OpenPGP --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: Branch instructions that depend on target distance

[Andreas Schwab]

On Feb 24 2020, Petr Tesarik wrote:

> On Mon, 24 Feb 2020 12:29:40 +0100
> Andreas Schwab <schwab@suse.de> wrote:
>
>> On Feb 24 2020, Petr Tesarik wrote:
>> 
>> > This works great ... until there's some inline asm() statement, for
>> > which gcc cannot keep track of the length attribute, so it is probably
>> > taken as zero.  
>> 
>> GCC computes it by counting the number of asm insns.  You can use
>> ADJUST_INSN_LENGTH to adjust this as needed.
>
> Hmm, that's interesting, but does it work for inline asm() statements?

Yes, for a suitable definition of work.

> The argument is essentially a free-form string (with some
> substitution), and the compiler cannot know how many bytes they occupy.

That's why ADJUST_INSN_LENGTH can adjust it.

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: Branch instructions that depend on target distance

[Alexander Monakov]

On Mon, 24 Feb 2020, Andreas Schwab wrote:

> On Feb 24 2020, Petr Tesarik wrote:
> 
> > On Mon, 24 Feb 2020 12:29:40 +0100
> > Andreas Schwab <schwab@suse.de> wrote:
> >
> >> On Feb 24 2020, Petr Tesarik wrote:
> >> 
> >> > This works great ... until there's some inline asm() statement, for
> >> > which gcc cannot keep track of the length attribute, so it is probably
> >> > taken as zero.  
> >> 
> >> GCC computes it by counting the number of asm insns.  You can use
> >> ADJUST_INSN_LENGTH to adjust this as needed.
> >
> > Hmm, that's interesting, but does it work for inline asm() statements?
> 
> Yes, for a suitable definition of work.
> 
> > The argument is essentially a free-form string (with some
> > substitution), and the compiler cannot know how many bytes they occupy.
> 
> That's why ADJUST_INSN_LENGTH can adjust it.

I think Petr might be unaware of the fact that GCC counts the **number of
instructions in an inline asm statement** by counting separators in the
asm string. This may overcount when a separator appears in a string literal
for example, but triggering under-counting is trickier.

Petr, please see https://gcc.gnu.org/onlinedocs/gcc/Size-of-an-asm.html
for some more discussion.

Alexander

Re: Branch instructions that depend on target distance

[Julian Brown]

On Mon, 24 Feb 2020 15:03:21 +0300 (MSK)
Alexander Monakov <amonakov@ispras.ru> wrote:

> On Mon, 24 Feb 2020, Andreas Schwab wrote:
> 
> > On Feb 24 2020, Petr Tesarik wrote:
> >   
> > > On Mon, 24 Feb 2020 12:29:40 +0100
> > > Andreas Schwab <schwab@suse.de> wrote:
> > >  
> > >> On Feb 24 2020, Petr Tesarik wrote:
> > >>   
> > >> > This works great ... until there's some inline asm()
> > >> > statement, for which gcc cannot keep track of the length
> > >> > attribute, so it is probably taken as zero.    
> > >> 
> > >> GCC computes it by counting the number of asm insns.  You can use
> > >> ADJUST_INSN_LENGTH to adjust this as needed.  
> > >
> > > Hmm, that's interesting, but does it work for inline asm()
> > > statements?  
> > 
> > Yes, for a suitable definition of work.
> >   
> > > The argument is essentially a free-form string (with some
> > > substitution), and the compiler cannot know how many bytes they
> > > occupy.  
> > 
> > That's why ADJUST_INSN_LENGTH can adjust it.  
> 
> I think Petr might be unaware of the fact that GCC counts the
> **number of instructions in an inline asm statement** by counting
> separators in the asm string. This may overcount when a separator
> appears in a string literal for example, but triggering
> under-counting is trickier.
> 
> Petr, please see
> https://gcc.gnu.org/onlinedocs/gcc/Size-of-an-asm.html for some more
> discussion.

VC4 instructions vary between 16 & 80 bits in length -- I guess you
need to arrange things so that the maximum is used for inline asms (per
instruction, counting by separators). That's not 100% ideal since most
instructions will be much shorter, but at least it should give working
code.

Julian

Re: Branch instructions that depend on target distance

[Petr Tesarik]

[-- Attachment #1: Type: text/plain, Size: 1974 bytes --]

On Mon, 24 Feb 2020 15:03:21 +0300 (MSK)
Alexander Monakov <amonakov@ispras.ru> wrote:

> On Mon, 24 Feb 2020, Andreas Schwab wrote:
> 
> > On Feb 24 2020, Petr Tesarik wrote:
> >   
> > > On Mon, 24 Feb 2020 12:29:40 +0100
> > > Andreas Schwab <schwab@suse.de> wrote:
> > >  
> > >> On Feb 24 2020, Petr Tesarik wrote:
> > >>   
> > >> > This works great ... until there's some inline asm() statement, for
> > >> > which gcc cannot keep track of the length attribute, so it is probably
> > >> > taken as zero.    
> > >> 
> > >> GCC computes it by counting the number of asm insns.  You can use
> > >> ADJUST_INSN_LENGTH to adjust this as needed.  
> > >
> > > Hmm, that's interesting, but does it work for inline asm() statements?  
> > 
> > Yes, for a suitable definition of work.
> >   
> > > The argument is essentially a free-form string (with some
> > > substitution), and the compiler cannot know how many bytes they occupy.  
> > 
> > That's why ADJUST_INSN_LENGTH can adjust it.  
> 
> I think Petr might be unaware of the fact that GCC counts the **number of
> instructions in an inline asm statement** by counting separators in the
> asm string. This may overcount when a separator appears in a string literal
> for example, but triggering under-counting is trickier.
> 
> Petr, please see https://gcc.gnu.org/onlinedocs/gcc/Size-of-an-asm.html
> for some more discussion.

Indeed. Thanks for the pointer. First, it explains why my AVR test case
was invalid (I used ".rept 64 ; nop ; .endr" to save me some work).
Second, it made me aware of "the longest instruction supported by that
processor".

IIUC, this should be the default value for (define_attr "length")
in a machine description file unless a better value can be calculated
from a known instruction. And it also explains why it is still
necessary to provide some value even if you define a "length" attribute
for all known instructions.

Cheers,
Petr T

[-- Attachment #2: Digitální podpis OpenPGP --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: Branch instructions that depend on target distance

[Andrew Stubbs]

On 24/02/2020 11:05, Petr Tesarik wrote:
> Hi all,
> 
> I'm looking into reviving the efforts to port gcc to VideoCore IV [1].
> One issue I've run into is the need to find out target branch distance
> at compile time. I looked around, and it's not the first one
> architecture with such requirement, but AFAICS it has never been solved
> properly.
> 
> For example, AVR tracks instruction length. Later, ret_cond_branch()
> selects between a branch instruction and an inverted branch followed by
> an unconditional jump based on these calculated lengths.
> 
> This works great ... until there's some inline asm() statement, for
> which gcc cannot keep track of the length attribute, so it is probably
> taken as zero. Linker then fails with a cryptic message:
> 
>> relocation truncated to fit: R_AVR_7_PCREL against `no symbol'

You can probably fix this by implementing the ADJUST_INSN_LENGTH macro 
and recognising the inline assembler. See the internals manual.

We encountered similar issues with the recent GCN port, and the correct 
solution was to add the length attribute everywhere. The attributes are 
often conservative estimates (rather than having extra alternatives for 
every possible encoding), so the asm problem is mitigated somewhat, at 
the cost of a few "far" branches where they're not strictly necessary.

There were also addition problems because "far" branches clobber the 
condition register, and "near" branches do not, but that's another story.

Andrew