RFD: fixup_fallthru_exit_predecessor bug (Was: Re: [PATCH/RFA] PR target/13250)

[Joern Rennecke <joern dot rennecke at superh dot com>]

[This was before in gcc-patches, but now I am at a point where I would like
 some input from the creators /maintainers of the cfg* files.]

> Thanks for the testcase (sent off-list).
> It turns out that the loop optimizer has inserted a jump between
> the call and the instruction that copied the return value.

I have now managed to track down the reason why this jump is inserted.
fixup_fallthru_exit_predecessor finds that the basic block that used
to be the last one, and which still has a fallthrough edge to the
exit block, is not anymore the last block.  It uses a brute force
search to find the predecessor block, unlinks the block from the chain,
and links it in at the end.  Unfortunately, this block is the one that
copies the call result to a pseudo, and its old predecessor ends with
a call.  fixup_reorder_chain then inserts the jump as a to compensate
for the fallthrough edge being between non-adjacent blocks.

I believe that fixup_fallthru_exit_predecessor should never have separated
the basic block that does the call from the one that copies its return
value.  I.e. if the block to be moved to the end has a fallthrough
predecessor edge, the source of which ends in a call (if you like you can
refine this test by checking that a hard register is involved), then
this predecessor block should also be moved.  And since it is going
to be moved, it should also be checked for a similar predecessor.
This is relatively simple to code with a linear search like in the
existing code, however, this gives us quadratic complexity.
I can avoid this if I can use a flag in the basic block structure or
the rbi structure, by first clearing this flag for all blocks, and
then scanning backwards as far as necessary and setting the flag.
Then the re-ordering can be done in a single pass, i.e. linear
complexity.
Is a flag in the basic block structure or the rbi structure readily
available?
Or should I create a new one?  The basic block structure has a flags
field with a number of unused bits, or I could add a new member to rbi.
If I do the latter, should I make it narrow and make existing members
narrower to avoid using more space?

Finally, I think it would be best for performance if we preserve
not only the fall-through edges that are necessary to avoid increasing
SMALL_REGISTER_CLASSES register pressure, but all fall-through edges
connected to the moved exit-block predecessor.