Extending jumps after block reordering

Extending jumps after block reordering

[Gregory B. Prokopski]

+++ Ian Lance Taylor [06/07/07 09:16 -0700]:
> shorten_branches should work correctly--you shouldn't need to do
> anything special.  My only guess is that there is something wrong with
> the way you are reordering the blocks.  For example, perhaps you are
> simply reordering the CFG without reordering the insn chain.  Note
> that shorten_branches is not (yet) CFG aware.  It simply walks the
> insn chain.
> 
> I think that should work.  Although it's bb->aux, not bb->rbi->next.
> I'm not sure what bb->rbi is; which version of gcc are you using?

It's the latest one now, so I have bb->aux.

+++ Jim Wilson [09/07/07 15:36 -0700]:
> that the main call to it is
>   shorten_branches (get_insns ());
> which runs it on the entire function.  This is probably what you want.

Recap: I am reordering the basic blocks in a special manner and it seems to
be done properly, I do update the insns order after.  The problem is on PPC
some branches are too short to reach their targets which at assembly time
results in assembler errors:

Error: operand out of range (0x0000000000017ef0 is not between
  0xffffffffffff8000 and 0x0000000000007fff)

In passes.c shorten_branches() is already run AFTER my pass (which is run
just before pass_duplicate_computed_gotos).

What I believe I need to do:
a) find which branches cannot reach their destination, e.g. cond branches
with relative addr, with targets beyond the maximum distance,
b) split these branches into a cond branch to a non-cond branch, which should
have a longer target span (create a new BB w/ non-cond branch to the target
label and redirect the original branch to it)

Questions:
* shorten_branches() computes sizes of instructions so I know what the
  distance is between a jump instr and its target label.  But how do I know
  what is the maximum distance each kind of branch can safely take?
  bb-reorder.c assumes that its only when cold/hot partitions are crossed it
  has to use indirect jumps, which is not the appropriate test in my case.
* do I get it right that shorten_branches() does not really modify
  instructions but it helps to shorten branches by providing more accurate
  insns lengths?

Thanks,

Gregory

-- 
Gregory B. Prokopski       <gproko@sable.mcgill.ca>
Sable Research Group       http://www.sable.mcgill.ca
Montreal, Quebec, Canada

Re: Extending jumps after block reordering

[Eric Botcazou]

> Questions:
> * shorten_branches() computes sizes of instructions so I know what the
>   distance is between a jump instr and its target label.  But how do I know
>   what is the maximum distance each kind of branch can safely take?
>   bb-reorder.c assumes that its only when cold/hot partitions are crossed
> it has to use indirect jumps, which is not the appropriate test in my case.

You cannot easily, it's buried in the architecture back-ends.

> * do I get it right that shorten_branches() does not really modify
> instructions but it helps to shorten branches by providing more accurate
> insns lengths?

Yes, but this should work automatically.  IOW, as Ian said, you shouldn't need 
to do anything special.  Maybe it's simply a latent bug in the PPC back-end.

-- 
Eric Botcazou

Re: Extending jumps after block reordering

[Gregory B. Prokopski]

+++ Eric Botcazou [02/11/07 09:56 +0100]:
> > Questions:
> > * shorten_branches() computes sizes of instructions so I know what the
> >   distance is between a jump instr and its target label.  But how do I know
> >   what is the maximum distance each kind of branch can safely take?
> >   bb-reorder.c assumes that its only when cold/hot partitions are crossed
> > it has to use indirect jumps, which is not the appropriate test in my case.
> 
> You cannot easily, it's buried in the architecture back-ends.
> 
> > * do I get it right that shorten_branches() does not really modify
> > instructions but it helps to shorten branches by providing more accurate
> > insns lengths?
> 
> Yes, but this should work automatically.  IOW, as Ian said, you shouldn't need 
> to do anything special.  Maybe it's simply a latent bug in the PPC back-end.

Got it working.  It turns out I was renumbering the instructions just before
pass_final and it was messing up the creation of jump islands in PPC (and I
believe other archs with short cond branches).  I changed my code not to
require the renumbering and it's all working now.

Thanks a lot,

Gregory

-- 
Gregory B. Prokopski       <gproko@sable.mcgill.ca>
Sable Research Group       http://www.sable.mcgill.ca
Montreal, Quebec, Canada