Re: [patches] Re: crossjumping speedups

[Richard Henderson <rth at redhat dot com>]

On Mon, Jul 23, 2001 at 12:11:10PM +0200, Jan Hubicka wrote:
> > On review, I'm somewhat concerned about how try_optimize_cfg
> 
> Yes, lets discuss that.
> I am thinking about possible restructuring too.  First I needed to meet
> the functionallity I do have now, so now I want to concentrate on possible
> cleanup/making code more reusable. During development, try_optimize_cfg
> gave me a course what is needed to do :)

I don't quite know how it *should* be handled, but I know how
it shouldn't be.  ;-)  I'll have to think about it some more.

> One obvious way to avoid forwarder_block_p checkes is to change way we
> forward edges - not forward all outgoing edges from each basic block
> separately, but instead when processing basic block, discover, that it is
> an forwarder and take care for all incomming edges.
> 
> This second alternative makes it more dificult to do jump threading in the
> same come. Thats why I tought about moving it into ifcvt.c instead, if it
> makes more sense.

The best way I can think of is to remove _all_ forwarder blocks, except
for those with edges to themselves (that is, empty infinite loops).  At
the same time, adjust the edges in the CFG to reflect where the forwarding
would have taken them.  We can then do block merging, cross-jumping, and
so forth without having to worry about them.

So how do we return to legal straight-line code, you might ask?
See fixup_reorder_chain in bb-reorder.c.  That code knows how to
re-add exactly the right number of jumps to make things come out.

Plus, bb-reorder knows how to adjust the lexical block tree when
moving blocks around, which merge_blocks doesn't.  So we'd preserve
more of our debug information than we currently do.

> > !       /* Skip complex edges because we don't know how to update them.
> > ! 	 Skip fallthru edges because there's no jump to update.  */
> > !       if (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))
> Skipping fallthru is an lose.
> We may suceed to forward fallthru edge to the same place as branch edge is
> and eliminate the conditional completely.

Hmm.  Hadn't thought about that.  You can remove the fallthru
check if you add a comment documenting the case you're hoping
to catch.  Otherwise I'll wind up adding the check back in 6
months.  ;-)

> > !   /* Likewise with dead code.  */
> > !   /* ??? Won't we have eliminated these by now?  */
> These may get created by the previous transforamtions.
> We blast of the dead basic block when we reach it in the main loop.  Edge
> forwarding and other changes may create dead blocks in the already visited,
> or not-yet searched code.

Hum.  Seems like it would be a win to delete these more
aggressively then.

> > !   /* Likewise with non-jump edges.  */
> > !   /* ??? Non-jump?  You mean GET_CODE (e1->src-end) != JUMP_INSN?
> > !      This fails for computed-goto as well, which may in fact be joinable.  */
> Here I meant an abnormal edges, such as those created by EH.
> I didn't wanted to deal with computed goto in the first go, but I will do so
> later.

Ok, update the comment then.

> > ! 	  /* ??? Perhaps better is lowest execution frequency.  */
> This is job of bb-reorder.  I would not mess with this here. Whole issue
> is compilicated enought now.

You misunderstand -- bb-reorder has nothing to do with this.
Unless the entire blocks match, we'll be adding an extra jump
to one of the paths.  Clearly the extra jump should go on the
path executed less frequently.

> Frequencies are not unique and there may be multiple blocks with the same
> frequency.

Obviously.  We'd use the block index to break ties.


r~