Re: [patches] Re: crossjumping speedups

[Jan Hubicka <jh at suse dot cz>]

> > 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
This is similar to my idea above.
> 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.
I was thinking about this step too.  At the moment it seems to bring, at least
confusion with random data around forwarders - line number notes etc.
Also it would make us to re-emit forwarders after finishing cleanup_cfg
each time, that looks like waste right now.

Assuming that I convert rest of passes to CFG, we can in longer term think
about unlinking the blocks entirely.  This is still relativly far, as
reload, cse, regmove and few other small passes still needs updating in
this respect.

Yes, forwarder blocks are anoying - for instance ifcvt.c would need updating in
this area too...  It woud be great to kill them.

I want to test this transformation for BB reordering algorithm first, then
possibly use elsewhere.  It means to implement two functions -
kill_fallthru_forwarders and re_emit_fallthru_forwarders.

> 
> 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.  ;-)
Sure!
Would you pre-approve wording:
/* Normally forwarding fallthru edges is impossible too, but we still may win
   by forwarding the fallthru edge to same place as the condjump destination
   and convert the conditional jump to unconditional jump.  */
> 
> > > !   /* 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.
We can wind this into block forwarding code then, but deleting blocks is tricky,
as deleting labels is, so we would need to move that to separate function.
> 
> > > !   /* 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.
/* Likewise for complex edges.  We may want to handle computed jumps later,
   but ignore them for now.  */
> 
> > > ! 	  /* ??? 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.
This is true.  I am prioritizing the fallthru edge right now, but
we can switch to most frequent path later, once reload is converted (today?).
Lets keep the comment for now.
> 
> > Frequencies are not unique and there may be multiple blocks with the same
> > frequency.
> 
> Obviously.  We'd use the block index to break ties.
Yes.
I see it now.

BTW we also may want to crossjump noreturn calls...

Thanks,
Honza
> 
> 
> r~