Delay branch scheduling vs. the CFG

Delay branch scheduling vs. the CFG

[Steven Bosscher]

Hi,

I'm trying to figure out how much effort it would take to make
dbr_schedule CFG aware.  One of the issues I'm running into is
that the RTL CFG stuff doesn't support SEQUENCEs at all.  So if
I have a delay slot filled, e.g.,

(sequence [
    (jump_insn (...))   ;; The branch with delay slots
    (insn (...))        ;; An insn in a delay slot
    ])

verify_flow_info immediately dies on this because the last insn
in a basic block is not a branch instruction.  It sees just the
sequence and not the instructions in it.

Now I could add some kind of flag "reorg_completed" and go hack
all the RTL cfg routines to support SEQUENCEs.  But I'd rather
not do that unless I'm really sure nobody thinks that is a Very
Bad Idea.  ;-)

Thoughts?

Gr.
Steven

Re: Delay branch scheduling vs. the CFG

[Jeffrey A Law]

On Sun, 2005-11-13 at 21:20 +0100, Steven Bosscher wrote:
> Hi,
> 
> I'm trying to figure out how much effort it would take to make
> dbr_schedule CFG aware.  One of the issues I'm running into is
> that the RTL CFG stuff doesn't support SEQUENCEs at all.  So if
> I have a delay slot filled, e.g.,
> 
> (sequence [
>     (jump_insn (...))   ;; The branch with delay slots
>     (insn (...))        ;; An insn in a delay slot
>     ])
> 
> verify_flow_info immediately dies on this because the last insn
> in a basic block is not a branch instruction.  It sees just the
> sequence and not the instructions in it.
> 
> Now I could add some kind of flag "reorg_completed" and go hack
> all the RTL cfg routines to support SEQUENCEs.  But I'd rather
> not do that unless I'm really sure nobody thinks that is a Very
> Bad Idea.  ;-)
No great insights on how to make dbr_schedule CFG aware -- just
remember that a filled delay slot can represent 3 different cases:

  1. An extension of the block containing the sequence.

  2. An extension of the block at the target of a branch.

  3. An extension of the fall-thru block.

  4. An entirely new basic block on its own.

Firing out which of these cases holds can be nontrivial.


I'm not sure what you're trying to accomplish, but if you're
really interested in improving reorg, a huge step in the right
direction would be to have it use insn dependency information
to determine what insns are candidates for filling delay slots.

The net result is all the resource tracking nonsense goes away
as do the compile-time issues associated with it. 

Jeff

Re: Delay branch scheduling vs. the CFG

[Steven Bosscher]

On Sunday 13 November 2005 22:02, Jeffrey A Law wrote:
> No great insights on how to make dbr_schedule CFG aware -- just
> remember that a filled delay slot can represent 3 different cases:
>
>   1. An extension of the block containing the sequence.
>
>   2. An extension of the block at the target of a branch.
>
>   3. An extension of the fall-thru block.
>
>   4. An entirely new basic block on its own.

When can option 4 happen??

Gr.
Steven

Re: Delay branch scheduling vs. the CFG

[Jeffrey A Law]

On Sun, 2005-11-13 at 22:20 +0100, Steven Bosscher wrote:
> On Sunday 13 November 2005 22:02, Jeffrey A Law wrote:
> > No great insights on how to make dbr_schedule CFG aware -- just
> > remember that a filled delay slot can represent 3 different cases:
> >
> >   1. An extension of the block containing the sequence.
> >
> >   2. An extension of the block at the target of a branch.
> >
> >   3. An extension of the fall-thru block.
> >
> >   4. An entirely new basic block on its own.
> 
> When can option 4 happen??
IIRC it occurs when there was only 1 insn in either the target
or fall-thru block.    When it gets sucked into the delay
slot of a branch, then it is effectively its own basic
block.

Or something along those lines -- it's been about 15 years since
I've had to reconstruct CFGs from PA assembly code and branch
traces ;)


jeff

Re: Delay branch scheduling vs. the CFG

[Richard Henderson]

On Sun, Nov 13, 2005 at 02:26:31PM -0700, Jeffrey A Law wrote:
> On Sun, 2005-11-13 at 22:20 +0100, Steven Bosscher wrote:
> > On Sunday 13 November 2005 22:02, Jeffrey A Law wrote:
> > > No great insights on how to make dbr_schedule CFG aware -- just
> > > remember that a filled delay slot can represent 3 different cases:
> > >
> > >   1. An extension of the block containing the sequence.
> > >
> > >   2. An extension of the block at the target of a branch.
> > >
> > >   3. An extension of the fall-thru block.
> > >
> > >   4. An entirely new basic block on its own.
> > 
> > When can option 4 happen??
> IIRC it occurs when there was only 1 insn in either the target
> or fall-thru block.    When it gets sucked into the delay
> slot of a branch, then it is effectively its own basic
> block.

I'd be comfortable modeling all of these as (1), with the
understanding that the delay slots may be conditionally
executed, as if with cond_exec.


r~

Re: Delay branch scheduling vs. the CFG

[Jeffrey A Law]

On Wed, 2005-11-16 at 12:06 -0800, Richard Henderson wrote:
> On Sun, Nov 13, 2005 at 02:26:31PM -0700, Jeffrey A Law wrote:
> > On Sun, 2005-11-13 at 22:20 +0100, Steven Bosscher wrote:
> > > On Sunday 13 November 2005 22:02, Jeffrey A Law wrote:
> > > > No great insights on how to make dbr_schedule CFG aware -- just
> > > > remember that a filled delay slot can represent 3 different cases:
> > > >
> > > >   1. An extension of the block containing the sequence.
> > > >
> > > >   2. An extension of the block at the target of a branch.
> > > >
> > > >   3. An extension of the fall-thru block.
> > > >
> > > >   4. An entirely new basic block on its own.
> > > 
> > > When can option 4 happen??
> > IIRC it occurs when there was only 1 insn in either the target
> > or fall-thru block.    When it gets sucked into the delay
> > slot of a branch, then it is effectively its own basic
> > block.
> 
> I'd be comfortable modeling all of these as (1), with the
> understanding that the delay slots may be conditionally
> executed, as if with cond_exec.
Seems clean enough to me.
jeff

Re: Delay branch scheduling vs. the CFG

[Joern RENNECKE]

 > > >   4. An entirely new basic block on its own.
 > >
 > > When can option 4 happen??
 > IIRC it occurs when there was only 1 insn in either the target
 > or fall-thru block.    When it gets sucked into the delay
 > slot of a branch, then it is effectively its own basic
 > block.

When the fall-through is ended by a code label, and has only one insn, 
and that is eligible for
a delay-slot which can be annulled-true, the fall-through block can end 
up in the delay slot.

When the target block is ended by an unconditional jump, and otherwise 
has only one insn,
which is elegible for a delay slot in preceding branch that can be 
anulled-false, the fall-through
block can end up in the delay slot.
Likwise if the fall-through block consists only of a branch-delay-slot 
eligible insn  and
an unconditional jump, the branch and fall-through block can be 
converted into an inverted
branch with anulled-false delay slot insn.

And finally, sometimes earlier reorg changes have changed the data flow 
so that actually
no anulled slots are required (if there were no changes before, jump 
optimization should
have caught these opportunities, placing the lone insn in front of the 
branch); or the only
data anti-dependency might have the branch condition itself.