Re: PATCH: reorg branch displacement fix

Re: PATCH: reorg branch displacement fix

[Joern Rennecke]

> > * reorg.c (relax_delay_slots): Don't thread conditional jump
> > through unconditional jump if the conditional jump can't reach
> > the branch target on this processor target.
> This is wrong.  reorg does not and should not be checking branch displacements.
> That is a problem for shorten-branches and the backend.

The SH does some early branch shortening in machine_dependent_reorg because
a long conditional branch has to be split into a short conditional branch
around an unconditional branch, or a short conditional branch to an unconditional
branch (that might have been inserted elsewhere after an inverted condbranch).
Unconditional branches have mandatory delay slots, so we get additional
delay slots exposed by doing this splitting before reorg, and the conditional
branches have optional delay slots, which obviously can't be used in the same
way when the branch is reversed or redirected.
Thus, machine_dependent_reorg already makes sure all the conditional branches
that need splitting are split.  If reorg redirects conditional branches
willy-nilly, it destroys the very data it is supposed to operate on.
	
-- 
--------------------------
SuperH (UK) Ltd.
2410 Aztec West / Almondsbury / BRISTOL / BS32 4QX
T:+44 1454 465658

Re: PATCH: reorg branch displacement fix

[Jeff Law]

In message <3DC2FC6F.D75062A5@superh.com>, Joern Rennecke writes:
 >> > * reorg.c (relax_delay_slots): Don't thread conditional jump
 >> > through unconditional jump if the conditional jump can't reach
 >> > the branch target on this processor target.
 >> This is wrong.  reorg does not and should not be checking branch displaceme
 >nts.
 >> That is a problem for shorten-branches and the backend.
 >
 >The SH does some early branch shortening in machine_dependent_reorg because
 >a long conditional branch has to be split into a short conditional branch
 >around an unconditional branch, or a short conditional branch to an unconditi
 >onal
 >branch (that might have been inserted elsewhere after an inverted condbranch)
 >.
 >Unconditional branches have mandatory delay slots, so we get additional
 >delay slots exposed by doing this splitting before reorg, and the conditional
 >branches have optional delay slots, which obviously can't be used in the same
 >way when the branch is reversed or redirected.
 >Thus, machine_dependent_reorg already makes sure all the conditional branches
 >that need splitting are split.  If reorg redirects conditional branches
 >willy-nilly, it destroys the very data it is supposed to operate on.
Regardless, reorg has never been designed to deal with this issue.  It can
lengthen the distance between branches in various ways other than simple
redirection.

This is _NOT_ reorg's problem to solve.  This is the backend's problem to
solve.

jeff

Re: PATCH: reorg branch displacement fix

[tm]

On Fri, 1 Nov 2002, Jeff Law wrote:

> In message <3DC2FC6F.D75062A5@superh.com>, Joern Rennecke writes:
>  >> > * reorg.c (relax_delay_slots): Don't thread conditional jump
>  >> > through unconditional jump if the conditional jump can't reach
>  >> > the branch target on this processor target.
>  >> This is wrong.  reorg does not and should not be checking branch displaceme
>  >nts.
>  >> That is a problem for shorten-branches and the backend.
>  >
>  >The SH does some early branch shortening in machine_dependent_reorg because
>  >a long conditional branch has to be split into a short conditional branch
>  >around an unconditional branch, or a short conditional branch to an unconditi
>  >onal
>  >branch (that might have been inserted elsewhere after an inverted condbranch)
>  >.
>  >Unconditional branches have mandatory delay slots, so we get additional
>  >delay slots exposed by doing this splitting before reorg, and the conditional
>  >branches have optional delay slots, which obviously can't be used in the same
>  >way when the branch is reversed or redirected.
>  >Thus, machine_dependent_reorg already makes sure all the conditional branches
>  >that need splitting are split.  If reorg redirects conditional branches
>  >willy-nilly, it destroys the very data it is supposed to operate on.
> Regardless, reorg has never been designed to deal with this issue.  It can
> lengthen the distance between branches in various ways other than simple
> redirection.
> 
> This is _NOT_ reorg's problem to solve.  This is the backend's problem to
> solve.

Can we poison MD_CAN_REDIRECT_BRANCH in reorg.c once we remove the other
reference to it?

Toshi

Re: PATCH: reorg branch displacement fix

[Joern Rennecke]

Jeff Law wrote:
> 
> In message <3DC2FC6F.D75062A5@superh.com>, Joern Rennecke writes:
>  >The SH does some early branch shortening in machine_dependent_reorg because
>  >a long conditional branch has to be split into a short conditional branch
>  >around an unconditional branch, or a short conditional branch to an unconditi
>  >onal
>  >branch (that might have been inserted elsewhere after an inverted condbranch)
>  >.
>  >Unconditional branches have mandatory delay slots, so we get additional
>  >delay slots exposed by doing this splitting before reorg, and the conditional
>  >branches have optional delay slots, which obviously can't be used in the same
>  >way when the branch is reversed or redirected.
>  >Thus, machine_dependent_reorg already makes sure all the conditional branches
>  >that need splitting are split.  If reorg redirects conditional branches
>  >willy-nilly, it destroys the very data it is supposed to operate on.
> Regardless, reorg has never been designed to deal with this issue.  It can
> lengthen the distance between branches in various ways other than simple
> redirection.

But these lengthening transformations have reasonable upper bounds, so you can
take them into account by considering an instruction x bytes longer. 	
	
> This is _NOT_ reorg's problem to solve.  This is the backend's problem to
> solve.

It used to be possible to hide these spurious redirection 'opportunities',
but reorg has become more aggressive in this aspect.  We are not talking
about a problem of making an optimization in reorg, but about avoiding invalid transformations there.
There is no such thing as a conditional branch with an infinite offset on the SH,
and hence machine_dependent_reorg is within its remit to fix them up into whatever
sequence of instruction is suitable.
Are you suggesting I should disable the putatively machine-independent delay slot
scheduling for the SH and instead roll my own in the SH backend?
	
-- 
--------------------------
SuperH (UK) Ltd.
2410 Aztec West / Almondsbury / BRISTOL / BS32 4QX
T:+44 1454 465658

Re: PATCH: reorg branch displacement fix

[Jeff Law]

In message <3DC30C82.89D0FFEC@superh.com>, Joern Rennecke writes:
 >It used to be possible to hide these spurious redirection 'opportunities',
 >but reorg has become more aggressive in this aspect.
Which means that your backend is abusing the facilities in the generic
parts of the compiler.

 > We are not talking
 >about a problem of making an optimization in reorg, but about avoiding invali
 >d transformations there.
Reorg has always been designed to not worry about the potential of 
lengthening branches.  Those are for shorten-branches and the backend
to deal with.  reorg has always worked under the assumption that it can
thread a branch and not worry about if that lengthens the branch.  In
fact that's part of its fundamental design.


 >There is no such thing as a conditional branch with an infinite offset on the
 > SH,
Similarly for the PA, sparc and various other ports.  

 >Are you suggesting I should disable the putatively machine-independent delay 
 >slot
 >scheduling for the SH and instead roll my own in the SH backend?
I'm suggesting you fix your backend to work within the framework and
assumptions made by the generic parts of the compiler.
jeff

Re: PATCH: reorg branch displacement fix

[tm]

On Fri, 1 Nov 2002, Joern Rennecke wrote:

> > > * reorg.c (relax_delay_slots): Don't thread conditional jump
> > > through unconditional jump if the conditional jump can't reach
> > > the branch target on this processor target.
> > This is wrong.  reorg does not and should not be checking branch displacements.
> > That is a problem for shorten-branches and the backend.
> 
> The SH does some early branch shortening in machine_dependent_reorg because
> a long conditional branch has to be split into a short conditional branch
> around an unconditional branch, or a short conditional branch to an unconditional
> branch (that might have been inserted elsewhere after an inverted condbranch).
> Unconditional branches have mandatory delay slots, so we get additional
> delay slots exposed by doing this splitting before reorg, and the conditional
> branches have optional delay slots, which obviously can't be used in the same
> way when the branch is reversed or redirected.
> Thus, machine_dependent_reorg already makes sure all the conditional branches
> that need splitting are split.  If reorg redirects conditional branches
> willy-nilly, it destroys the very data it is supposed to operate on.

It sounds like there should be a machine-independent branch-lengthening
pass for machines which have limited branch displacements. There must be
other processors which have this same problem?

Toshi

Re: PATCH: reorg branch displacement fix

[Jeff Law]

In message <Pine.LNX.4.21.0211011443240.4972-100000@mail.kloo.net>, tm writes:
 >On Fri, 1 Nov 2002, Joern Rennecke wrote:
 >
 >> > > * reorg.c (relax_delay_slots): Don't thread conditional jump
 >> > > through unconditional jump if the conditional jump can't reach
 >> > > the branch target on this processor target.
 >> > This is wrong.  reorg does not and should not be checking branch displace
 >ments.
 >> > That is a problem for shorten-branches and the backend.
 >> 
 >> The SH does some early branch shortening in machine_dependent_reorg because
 >> a long conditional branch has to be split into a short conditional branch
 >> around an unconditional branch, or a short conditional branch to an uncondi
 >tional
 >> branch (that might have been inserted elsewhere after an inverted condbranc
 >h).
 >> Unconditional branches have mandatory delay slots, so we get additional
 >> delay slots exposed by doing this splitting before reorg, and the condition
 >al
 >> branches have optional delay slots, which obviously can't be used in the sa
 >me
 >> way when the branch is reversed or redirected.
 >> Thus, machine_dependent_reorg already makes sure all the conditional branch
 >es
 >> that need splitting are split.  If reorg redirects conditional branches
 >> willy-nilly, it destroys the very data it is supposed to operate on.
 >
 >It sounds like there should be a machine-independent branch-lengthening
 >pass for machines which have limited branch displacements. There must be
 >other processors which have this same problem?
Or the SH port should use the model that all the other ports with
variable length insns + limited branch displacements + delay slots use.

That model is we don't worry about such things in reorg and deal with
branch shortening entirely in the branch shortening pass.

jeff

Re: PATCH: reorg branch displacement fix

[Joern Rennecke]

Jeff Law wrote:
> 
> In message <Pine.LNX.4.21.0211011443240.4972-100000@mail.kloo.net>, tm writes:
>  >It sounds like there should be a machine-independent branch-lengthening
>  >pass for machines which have limited branch displacements. There must be
>  >other processors which have this same problem?

I think it would actually be worth-while to marry the local constant pool
generation (which is currently in machine_dependent_reorg, because it must be
sub-function granularity to ensure that the offsets reach) with an early
branch shortening pass.  This would allow us to put the costants for far
branches into larger constant pools, thus improving Icache / Dcache locality
and saving some bytes of alignment for 32 bit branches.  Also, we should
be able to increase the coverage range of unconditional branches as targets
for conditional branches, thus saving some more space.
	
> Or the SH port should use the model that all the other ports with
> variable length insns + limited branch displacements + delay slots use.

That would be the fr30.  And the model it uses is to pretend it has
arbitrary long branches, and then it takes 8 or 10 bytes per branch
when it gets out of range.
Looking in google for fr30, it appears as if Fujitsu doesn't care about
gcc at the moment; they talk about their 'Softune' IDE, but no word about
GNU tools.  Also the fr30 gdb port has been obsoleted...

In detail:
The SH has 9 bit signed offsets for conditional branches.  Longer branches
are synthesized using unconditional branches; these come in 13, 16 and 32
bit signed offset variants.  The 13 bit unconditional branches always have
a delay slot, the 16 and 32 bit ones have one if register scavenging
(which also happens in machine_dependent_reorg) has been sucessful.
13 bit jumps take 2 bytes, and if register scavenging is successful
(which it is most of the times, since there is usually a dead gpr
 at the start of a basic block) 16 bit ones take 6 bytes + slot, and 32
bit ones take 8-10 bytes + slot; if not, it's 10 bytes and 12-14 bytes,
respectively.

I find that most branches can be done with 9 or 13 bit offset, and almost
all of the rest can be handled with 16 bit.  So let's define
'limited branch displacements' for the sake of this discussion as
'less than 16 bits'; things that happen very infrequently are not
interesting for optimization (as long as we get them right).

grep shows that the list of ports that mention define_delay at all is
rather limited:
config/arc/arc.md:2
config/c4x/c4x.md:5
config/cris/cris.md:1
config/d30v/d30v.md:8
config/fr30/fr30.md:1
config/frv/frv.md:8
config/m88k/m88k.md:2	
config/mips/mips.md:3
config/pa/pa.md:6
config/romp/romp.md:1
config/sh/sh.md:4
config/sparc/sparc.md:4

Now let's have a look at these ports:
	
- arc and m88k have (or pretend to have) uniform size branches.
- The c4x and cris do not even have a length attribute.
- d30v and frv mention define_delay only in comments.
- The fr30 has 9 bit conditional branch offsets.  It can annul-true
  the delay slots, just like the SH, but that is not described in the
  fr30.md file.  Short unconditional jumps only have a 9 bit offset,
  and there is only one other type in use for any given compilation,
  which takes 6 bytes for the small memory model, and 8 bytes for the
  large model.  Because of the small range for the 2 byte unconditional
  branch, the fr30 suffers even more from lack of intelligent branch
  splitting than the SH did, but apparently, no-one cares enough about
  the fr30 gcc code to make it generate decent code.
- mips: 'short' branches are 4 bytes long and have a 17 bit offset.
- pa: 'short' branches have a length of 4 and 14 bit offset; there
  is also a medium length variant available that takes 8 bytes and
  has a 19 bit offset, and has still just one delay slot with also
  has the same annull direction as the one for the short branch.
  When the 19 bit offset is exceeded, and optimization is enabled,
  the compiler aborts.  Huh, what a nice role model.
- romp: branches have lengths of 2 (with 9 bit offset) or 4; again,
  the delay slot stays the same irrespective of insn length.
  The md file seems to assume that delay slots for 2 byte insns don't
  work, and that they can be disabled by testing the length attribute
  (that doesn't work because you'll always see the default length of 4
  during delay slot scheduling).  Maybe that is some remnant of gcc 1?
- sparc: 'short' branches have a length of 4 and 19 bit offset for
  integer and fp comparisons, 16 bit for sparc v9 register comparisons.
  When more offset is needed, a sequence with an unused second delay
  slot is used.

> That model is we don't worry about such things in reorg and deal with
> branch shortening entirely in the branch shortening pass.

This is inappropriate when a considerable amount of your delay slots
depend on branch shortening.
	
-- 
--------------------------
SuperH (UK) Ltd.
2410 Aztec West / Almondsbury / BRISTOL / BS32 4QX
T:+44 1454 465658

Re: PATCH: reorg branch displacement fix

[Hans-Peter Nilsson]

On Mon, 4 Nov 2002, Joern Rennecke wrote:
> Looking in google for fr30, it appears as if Fujitsu doesn't care about
> gcc at the moment; they talk about their 'Softune' IDE, but no word about
> GNU tools.  Also the fr30 gdb port has been obsoleted...

And the fr30 port has been broken since some time after
2002-05-29.  Build succeeded then but all the tests timed out.
I haven't tried it since.  Hmm... better do that, then...

> - The c4x and cris do not even have a length attribute.

For the record: as you may imagine, the CRIS port trusts GAS
relaxation to handle varying-length branches (9-bit and 16-bit
including sign).  It's my informed opinion that this is not
worth doing in GCC (for this target) just for sake of branch
shortening since asm:s *must* in GCC be considered of inordinate
length; GCC can't do better here than GAS anyway.  (Still worth
doing for sake of switch tables; on the virtual TODO list.
Thanks to GAS broken-.word [don't puke!], offsets aren't too
long, though.)

brgds, H-P

Re: PATCH: reorg branch displacement fix

[tm]

On Fri, 1 Nov 2002, Joern Rennecke wrote:

> > > * reorg.c (relax_delay_slots): Don't thread conditional jump
> > > through unconditional jump if the conditional jump can't reach
> > > the branch target on this processor target.
> > This is wrong.  reorg does not and should not be checking branch displacements.
> > That is a problem for shorten-branches and the backend.
> 
> The SH does some early branch shortening in machine_dependent_reorg because
> a long conditional branch has to be split into a short conditional branch
> around an unconditional branch, or a short conditional branch to an unconditional
> branch (that might have been inserted elsewhere after an inverted condbranch).
> Unconditional branches have mandatory delay slots, so we get additional
> delay slots exposed by doing this splitting before reorg, and the conditional
> branches have optional delay slots, which obviously can't be used in the same
> way when the branch is reversed or redirected.
> Thus, machine_dependent_reorg already makes sure all the conditional branches
> that need splitting are split.  If reorg redirects conditional branches
> willy-nilly, it destroys the very data it is supposed to operate on.

Maybe I'm misunderstanding something, but the two goals of:

1) Unconstrained branch rethreading in reorg

2) Efficiently utilized branch delay slots

do not seem to be mutually exclusive.

The SH has only a single conditional branch, but if we model this in reorg
as multiple conditional branches with varying displacement capabilities
with varying number of annulled/non-annulled delay slots, we can satisfy
both conditions?

Toshi

Re: PATCH: reorg branch displacement fix

[Joern Rennecke]

tm wrote:
> 
> On Fri, 1 Nov 2002, Joern Rennecke wrote:
> 
> > > > * reorg.c (relax_delay_slots): Don't thread conditional jump
> > > > through unconditional jump if the conditional jump can't reach
> > > > the branch target on this processor target.
> > > This is wrong.  reorg does not and should not be checking branch displacements.
> > > That is a problem for shorten-branches and the backend.
> >
> > The SH does some early branch shortening in machine_dependent_reorg because
> > a long conditional branch has to be split into a short conditional branch
> > around an unconditional branch, or a short conditional branch to an unconditional
> > branch (that might have been inserted elsewhere after an inverted condbranch).
> > Unconditional branches have mandatory delay slots, so we get additional
> > delay slots exposed by doing this splitting before reorg, and the conditional
> > branches have optional delay slots, which obviously can't be used in the same
> > way when the branch is reversed or redirected.
> > Thus, machine_dependent_reorg already makes sure all the conditional branches
> > that need splitting are split.  If reorg redirects conditional branches
> > willy-nilly, it destroys the very data it is supposed to operate on.
> 
> Maybe I'm misunderstanding something, but the two goals of:
> 
> 1) Unconstrained branch rethreading in reorg

That asumes that branch rethreading in reorg is always a win.  However, for the
SH, its usually a pessimization.
	
> 2) Efficiently utilized branch delay slots
> 
> do not seem to be mutually exclusive.
> 
> The SH has only a single conditional branch, but if we model this in reorg
> as multiple conditional branches with varying displacement capabilities
> with varying number of annulled/non-annulled delay slots, we can satisfy
> both conditions?

You make it actually more complex this way.  It is better to describe the
branches that do actually exist.  That would also be the prerequisite to
doing a machine-independent combined local constant pool / early branch
shortening & splitting pass.

I think a branch range can be described with three numbers, or if a constant
pool entry is needed, seven numbers a strings:
(define_branch_range <name> <length> <min_offset> <max_offset>
 <condition>
 <scratch_register> <pool_entry_size> <min_entry_offset> <max_entry_offset> <entry_bias>)

min_offset would represent the minimum offset from the start of the branch
instruction, while max_offset would represent the maximum offset from the
byte after the end of the branch instruction.
Small additive constants that are applied to the branch destination can be
expressed by adjusting the min_offset / max_offset bounds accordingly, but
if a pool entry is needed, they need to be mentioned in entry_bias so that
the right pool entry can be created.
<scratch_register> is a constraint string for a scratch register to be scavanged.
If the constraint can't be matched for the available free registers, it might fail,
causing this brnch range to be ignored.
length can be a string with comma-separated numbers, so that you can have
multi-alternative ranges, e.g. for the SH, you'd have:

(define_branch_range "cbranch" 2 -252 254
  "TARGET_SH1")

;; bra; nop
(define_branch_range "bra_range" 4 -4092 4094
  "TARGET_SH1")

;; mov.w 1f,rx; braf rx; nop; 0:;...; 1: .word target-0b
;; mov.l r13,-@r15; mov.w 1f,rx; braf r13; mov.l @r15+,r13; 0:;...; 1: .word target-0b
(define_branch_range "branch_16bit" "6,8" -32762 32767
  "TARGET_SH2"
  "r,X" 2 0 508 6)

;; mov.l 1f,rx; braf rx; nop; 0:;...; 1: .long target-0b
;; mov.l r13,-@r15; mov.l 1f,rx; braf r13; mov.l @r15+,r13; 0:;...; 1: .long target-0b
(define_branch_range "branch_32bit" "6,8" -4294967294 4294967294	
  "TARGET_SH2"
  "r,X" 4 0 1018 6)	

;; mov.l 1f,rx; jmp rx; nop; 0:;...; 1: .word target-0b
;; mov.l r13,-@r15; mov.l 1f,rx; jmp r13; mov.l @r15+,r13; 0:;...; 1: .long target
(define_branch_range "jump_range" "6,8" -4294967294 4294967294
  "TARGET_SH1 && ! flag_pic"
  "r,X" 4 0 1018 "absolute")
	
The individual conditional branches and jump instructions can then use an
attribute to select one or more applicable branch ranges, e.g.:

(define_attr "branch_range" "bra_range,branch_16bit,branch_32bit,jump_range")

If a pool entry is created, this can be communicated by changing the branch
destination to:
(plus (mem (label_ref <pool_entry>)) (plus (pc) (const_int <entry_bias>)))

where the (plus (pc) (const_int <entry_bias>)) rtl may be shared with
other branches.  Or, if a scratch register has been scavenged, a move
to that register is inserted, and the branch destination becomes
(plus (reg) (plus (pc) (const_int <entry_bias>))) - or just (reg) in the
absolute case.
	
Likewise, switch table dispatch should be described so that the machine-independent
code can get at the ranges without having to try them out:

(define_addr_diff_vec_range <name>
 <dispatch_length> <entry_length> <entry_whence> <min_entry_offset> <max_entry_offset>
 <condition>
 <min_table_offset> <max_table_offset>)
	
<min_table_offset> and <max_table_offset> describe where the table may be relative
to the dispatch insn.  Some targets require 0 / 0 here, while others are more
flexible.

<entry_whence> would describe what the offset in an individual entry is relative to,
and be one of "dispatch", "table_start", "table_end", "table_entry" ;

and a "addr_diff_vec_range" attribute is added to the dispatch insn(s).

We also need a mechanism to tell which constant should be put into local constant
pools, and how to address them.  I suppose we can use a contraint modifier, e.g.
'^', to say that following letters are valid for register preferencing and reload
(unless stated otherwise by # / *), but should cause the values that are matched
against them (and not an earlier letter) to be put into a local constant pool when
these are created.

The constants that are identified this way are than matched against pool_entry
definitions, e.g.:

(define_pool_entry "sh_hi_const_pool_entry" (match_operand:HI "hi_pool_const" "Q") 0 510)

(define_pool_entry "sh_sf_const_pool_entry" (match_operand:SF "sf_pool_const" ">") 0 1020)
	
The latter entry wouldn't match (mem:label_ref), but it would match an
alternative that has an "X" constraint in a position where a scratch
register (r0) is allocated.
The constant pool code would then load the address into this scratch
register.  Moreover, for a ">" constraint, it can elide scratch register
loads for consecutive constant references with the same scratch register
as long as the scratch register is not clobbered in-between.

If some instructions need different forms of pool entries than others,
they can select a list of appropriate entries with an attribute.
		
-- 
--------------------------
SuperH (UK) Ltd.
2410 Aztec West / Almondsbury / BRISTOL / BS32 4QX
T:+44 1454 465658

PATCH: reorg branch displacement fix

[tm]

This fixes the problem mentioned in:

http://gcc.gnu.org/ml/gcc-bugs/2002-06/msg00896.html

When a conditional branch jumps to an unconditional branch, reorg will
thread the branch without checking if the conditional branch has enough
displacement bits to branch to the target.

This patch uses MD_CAN_REDIRECT_BRANCH (as suggested by Joern in followup
messages to original message) to implement the substitution checking.

Please review and if correct, commit as I don't have CVS access.

Toshi

Thu Oct 31  Toshiyasu Morita  <toshiyasu.morita@hsa.hitachi.com>

	* reorg.c (relax_delay_slots): Don't thread conditional jump
        through unconditional jump if the conditional jump can't reach
        the branch target on this processor target.

*** reorg.c	Thu Oct 31 13:38:29 2002
--- reorg.c.new	Thu Oct 31 13:37:24 2002
*************** relax_delay_slots (first)
*** 3290,3297 ****
  	    trial = find_end_label ();
  
  	  if (trial != target_label
! 	      && redirect_with_delay_slots_safe_p (delay_insn, trial, insn))
! 	    {
  	      reorg_redirect_jump (delay_insn, trial);
  	      target_label = trial;
  	    }
--- 3290,3304 ----
  	    trial = find_end_label ();
  
  	  if (trial != target_label
! 	      && redirect_with_delay_slots_safe_p (delay_insn, trial, insn)
! #ifdef MD_CAN_REDIRECT_BRANCH
!               /* Ensure the conditional branch has enough jump displacement
!                  to reach the target of the unconditional branch before
!                  we redirect the unconditional branch.  */
!               && MD_CAN_REDIRECT_BRANCH (delay_insn, next)
! #endif
!               )
! {
  	      reorg_redirect_jump (delay_insn, trial);
  	      target_label = trial;
  	    }

Re: PATCH: reorg branch displacement fix

[Jeff Law]

In message <Pine.LNX.4.21.0210311508160.3016-100000@mail.kloo.net>, tm writes:
 >
 >This fixes the problem mentioned in:
 >
 >http://gcc.gnu.org/ml/gcc-bugs/2002-06/msg00896.html
 >
 >When a conditional branch jumps to an unconditional branch, reorg will
 >thread the branch without checking if the conditional branch has enough
 >displacement bits to branch to the target.
 >
 >This patch uses MD_CAN_REDIRECT_BRANCH (as suggested by Joern in followup
 >messages to original message) to implement the substitution checking.
 >
 >Please review and if correct, commit as I don't have CVS access.
 >
 >Toshi
 >
 >Thu Oct 31  Toshiyasu Morita  <toshiyasu.morita@hsa.hitachi.com>
 >
 >	* reorg.c (relax_delay_slots): Don't thread conditional jump
 >        through unconditional jump if the conditional jump can't reach
 >        the branch target on this processor target.
This is wrong.  reorg does not and should not be checking branch displacements.
That is a problem for shorten-branches and the backend.

jeff

Re: PATCH: reorg branch displacement fix

[tm]

On Fri, 1 Nov 2002, Jeff Law wrote:

> In message <Pine.LNX.4.21.0210311508160.3016-100000@mail.kloo.net>, tm writes:
>  >
>  >This fixes the problem mentioned in:
>  >
>  >http://gcc.gnu.org/ml/gcc-bugs/2002-06/msg00896.html
>  >
>  >When a conditional branch jumps to an unconditional branch, reorg will
>  >thread the branch without checking if the conditional branch has enough
>  >displacement bits to branch to the target.
>  >
>  >This patch uses MD_CAN_REDIRECT_BRANCH (as suggested by Joern in followup
>  >messages to original message) to implement the substitution checking.
>  >
>  >Please review and if correct, commit as I don't have CVS access.
>  >
>  >Toshi
>  >
>  >Thu Oct 31  Toshiyasu Morita  <toshiyasu.morita@hsa.hitachi.com>
>  >
>  >	* reorg.c (relax_delay_slots): Don't thread conditional jump
>  >        through unconditional jump if the conditional jump can't reach
>  >        the branch target on this processor target.
> This is wrong.  reorg does not and should not be checking branch displacements.
> That is a problem for shorten-branches and the backend.
> 
> jeff

Aha! I see now. I will try disabling that chunk of code, and testing.

Incidentially, MD_CAN_REDIRECT_BRANCH is already used in reorg in one
other place, in steal_delay_list_from_target():

#ifdef MD_CAN_REDIRECT_BRANCH
  /* On some targets, branches with delay slots can have a limited
     displacement.  Give the back end a chance to tell us we can't do
     this.  */
  if (! MD_CAN_REDIRECT_BRANCH (insn, XVECEXP (seq, 0, 0)))
    return delay_list;
#endif

This should probably be fixed as well.

Toshi

Re: PATCH: reorg branch displacement fix

[Jeff Law]

In message <Pine.LNX.4.21.0211011127060.4789-100000@mail.kloo.net>, tm writes:
 >On Fri, 1 Nov 2002, Jeff Law wrote:
 >
 >> In message <Pine.LNX.4.21.0210311508160.3016-100000@mail.kloo.net>, tm writ
 >es:
 >>  >
 >>  >This fixes the problem mentioned in:
 >>  >
 >>  >http://gcc.gnu.org/ml/gcc-bugs/2002-06/msg00896.html
 >>  >
 >>  >When a conditional branch jumps to an unconditional branch, reorg will
 >>  >thread the branch without checking if the conditional branch has enough
 >>  >displacement bits to branch to the target.
 >>  >
 >>  >This patch uses MD_CAN_REDIRECT_BRANCH (as suggested by Joern in followup
 >>  >messages to original message) to implement the substitution checking.
 >>  >
 >>  >Please review and if correct, commit as I don't have CVS access.
 >>  >
 >>  >Toshi
 >>  >
 >>  >Thu Oct 31  Toshiyasu Morita  <toshiyasu.morita@hsa.hitachi.com>
 >>  >
 >>  >	* reorg.c (relax_delay_slots): Don't thread conditional jump
 >>  >        through unconditional jump if the conditional jump can't reach
 >>  >        the branch target on this processor target.
 >> This is wrong.  reorg does not and should not be checking branch displaceme
 >nts.
 >> That is a problem for shorten-branches and the backend.
 >> 
 >> jeff
 >
 >Aha! I see now. I will try disabling that chunk of code, and testing.
 >
 >Incidentially, MD_CAN_REDIRECT_BRANCH is already used in reorg in one
 >other place, in steal_delay_list_from_target():
 >
 >#ifdef MD_CAN_REDIRECT_BRANCH
 >  /* On some targets, branches with delay slots can have a limited
 >     displacement.  Give the back end a chance to tell us we can't do
 >     this.  */
 >  if (! MD_CAN_REDIRECT_BRANCH (insn, XVECEXP (seq, 0, 0)))
 >    return delay_list;
 >#endif
 >
 >This should probably be fixed as well.
Yup.  That code never should have gone into reorg.  It't counter to one of
the fundamental design decisions we made when creating the reorg pass.

jeff

Re: PATCH: reorg branch displacement fix

[tm]

On Fri, 1 Nov 2002, Jeff Law wrote:

> In message <Pine.LNX.4.21.0210311508160.3016-100000@mail.kloo.net>, tm writes:
>  >
>  >This fixes the problem mentioned in:
>  >
>  >http://gcc.gnu.org/ml/gcc-bugs/2002-06/msg00896.html
>  >
>  >When a conditional branch jumps to an unconditional branch, reorg will
>  >thread the branch without checking if the conditional branch has enough
>  >displacement bits to branch to the target.
>  >
>  >This patch uses MD_CAN_REDIRECT_BRANCH (as suggested by Joern in followup
>  >messages to original message) to implement the substitution checking.
>  >
>  >Please review and if correct, commit as I don't have CVS access.
>  >
>  >Toshi
>  >
>  >Thu Oct 31  Toshiyasu Morita  <toshiyasu.morita@hsa.hitachi.com>
>  >
>  >	* reorg.c (relax_delay_slots): Don't thread conditional jump
>  >        through unconditional jump if the conditional jump can't reach
>  >        the branch target on this processor target.
> This is wrong.  reorg does not and should not be checking branch displacements.
> That is a problem for shorten-branches and the backend.
> 

Okay, here's a revised patch:

2002-10-31  Toshiyasu Morita  <toshiyasu.morita@hsa.hitachi.com>

	* reorg.c (relax_delay_slots): Don't thread conditional branches.

*** reorg.c.bak	Thu Oct 31 13:38:29 2002
--- reorg.c	Fri Nov  1 13:13:20 2002
*************** relax_delay_slots (first)
*** 3277,3300 ****
  
        if (target_label)
  	{
! 	  /* If this jump goes to another unconditional jump, thread it, but
! 	     don't convert a jump into a RETURN here.  */
! 	  trial = follow_jumps (target_label);
! 	  /* We use next_real_insn instead of next_active_insn, so that
! 	     the special USE insns emitted by reorg won't be ignored.
! 	     If they are ignored, then they will get deleted if target_label
! 	     is now unreachable, and that would cause mark_target_live_regs
! 	     to fail.  */
! 	  trial = prev_label (next_real_insn (trial));
! 	  if (trial == 0 && target_label != 0)
! 	    trial = find_end_label ();
! 
! 	  if (trial != target_label
! 	      && redirect_with_delay_slots_safe_p (delay_insn, trial, insn))
! 	    {
! 	      reorg_redirect_jump (delay_insn, trial);
! 	      target_label = trial;
! 	    }
  
  	  /* If the first insn at TARGET_LABEL is redundant with a previous
  	     insn, redirect the jump to the following insn process again.  */
--- 3277,3285 ----
  
        if (target_label)
  	{
!           /* Code previously here to thread unconditional jumps was deleted
!              because it caused problems and this should be handled by
!              shorten_branches and/or machine_dependent_reorg anyway.  */
  
  	  /* If the first insn at TARGET_LABEL is redundant with a previous
  	     insn, redirect the jump to the following insn process again.  */

Re: PATCH: reorg branch displacement fix

[Jeff Law]

In message <Pine.LNX.4.21.0211011446480.4972-100000@mail.kloo.net>, tm writes:
 >On Fri, 1 Nov 2002, Jeff Law wrote:
 >
 >> In message <Pine.LNX.4.21.0210311508160.3016-100000@mail.kloo.net>, tm writ
 >es:
 >>  >
 >>  >This fixes the problem mentioned in:
 >>  >
 >>  >http://gcc.gnu.org/ml/gcc-bugs/2002-06/msg00896.html
 >>  >
 >>  >When a conditional branch jumps to an unconditional branch, reorg will
 >>  >thread the branch without checking if the conditional branch has enough
 >>  >displacement bits to branch to the target.
 >>  >
 >>  >This patch uses MD_CAN_REDIRECT_BRANCH (as suggested by Joern in followup
 >>  >messages to original message) to implement the substitution checking.
 >>  >
 >>  >Please review and if correct, commit as I don't have CVS access.
 >>  >
 >>  >Toshi
 >>  >
 >>  >Thu Oct 31  Toshiyasu Morita  <toshiyasu.morita@hsa.hitachi.com>
 >>  >
 >>  >	* reorg.c (relax_delay_slots): Don't thread conditional jump
 >>  >        through unconditional jump if the conditional jump can't reach
 >>  >        the branch target on this processor target.
 >> This is wrong.  reorg does not and should not be checking branch displaceme
 >nts.
 >> That is a problem for shorten-branches and the backend.
 >> 
 >
 >Okay, here's a revised patch:
 >
 >2002-10-31  Toshiyasu Morita  <toshiyasu.morita@hsa.hitachi.com>
 >
 >	* reorg.c (relax_delay_slots): Don't thread conditional branches.
No.  Wrong again.

The fundamental problem is the SH is abusing the various pases.

reorg is allowed (and has been designed) to ignore branch lengths.  If it
has a branch, it is allowed to thread the branch.

jeff