Re: [patches] Re: crossjumping speedups

[Jan Hubicka <jh at suse dot cz>]

> Ok, it took me a while, but I think I finally understand what you
> were after here -- the duplicates come not within a single invocation
> of try_crossjump_bb, but from the sum of all of them.
Yes.
> 
> As such, the check you added _still_ doesn't really make sense.
> How exactly does the IOR in (e->src->succ == e || e2->src->succ == e2)
> apply to this situation?
I can't require both edges to be the first one, as other optimization
I do apply is to always crossjump to the later edge in the list, so in a
combination, I may disqualify then all meeting BBs.
> 
> !       /* Non-obvious work limiting check: Recognize that we're going
> !        to call try_crossjump_bb on every basic block.  So if we have
> !        two blocks with lots of outgoing edges (a switch) and they
> !        share lots of common destinations, then we would do the
> !        cross-jump check once for each common destination.
> !       
> !        Now, if the blocks actually are cross-jump candidates, then
> !        all of their destinations will be shared.  Which means that
> !        we only need check them for cross-jump candidacy once.  We
> !        can eliminate redundant checks of crossjump(A,B) by arbitrarily
> !        choosing to do the check from the block for which the edge
> !        in question is the first successor of A.  */
Yes, this is eaxactly what I am shooting for.
> !       if (e->src->succ != e)
> !       continue;
> [...]
> !         /* The "first successor" check above only prevents multiple
> !            checks of crossjump(A,B).  In order to prevent redundant
> !            checks of crossjump(B,A), require that A be the block
> !            with the lowest index.  */
> !         /* ??? Perhaps better is lowest execution frequency.  */
> !         if (e->src->index > e2->src->index)
> !           continue;
> 
> Correct me if I'm wrong.  And if I am wrong, you're going to
> need several paragraphs with pretty ascii diagrams to show me.
> 
> In the course of trying to figure out what was going on here, I
> took the liberty of cleaning up the grammar in the comments, and
Thansk a lot!
> expanding on them in some instances, as well as tweaking the code
> in various ways that seemed like a good idea at the time.
> 
> I added a couple of ??? comments that I think you need to either
> address or answer:
> 
> !   /* ??? Won't we have eliminated these by now?  */
> 
> !   /* ??? Non-jump?  You mean GET_CODE (e1->src-end) != JUMP_INSN?
> !      This fails for computed-goto as well, which may in fact be joinable.  */
> 
> 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 :)

> is evolving.  I have a feeling we'd be much better off with
> more smaller loops over n_basic_blocks.  I also have some ideas

Problem is, that crossjumping requires other simplifications to apply,
as by merging the paths it opens new possibilities for edge forwarding
and condjump-around-jump simplifier, that in turn opens new possibilities
for crossjumping.

Thats what I run into problems with when I hoped to eliminate everything,
except the crossjumping out of the

> for eliminating the bulk of the forwarder_block_p checks, but

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.
>   static bool
>   try_forward_edges (b)
>        basic_block b;
>   {
> !   bool changed = false;
> !   edge e, next;
> ! 
> !   for (e = b->succ; e ; e = next)
>       {
> !       basic_block target, first;
> !       int counter;
>   
> !       next = e->succ_next;
> ! 
> !       /* 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.

Later we also may want to be able redirect complex edges, but till then,
the test is surely OK.
> --- 3524,3589 ----
>     if (forwarder_block_p (e2->dest)
>         && forwarder_block_p (e2->dest->succ->dest))
>       return false;
> ! 
> !   /* 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.

> !   if (!src1->pred || !src2->pred)
>       return false;
> ! 
> !   /* 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.
>     if (e1->flags & EDGE_COMPLEX)
>       return false;
> --- 3599,3762 ----
>   	  s2->dest->frequency -= ((s->probability * s->src->frequency)
>   				  / REG_BR_PROB_BASE);
>   	}
> !       if (!redirect_to->frequency && !src1->frequency)
>   	s->probability = (s->probability + s2->probability) / 2;
>         else
>   	s->probability =
>   	  ((s->probability * redirect_to->frequency +
> ! 	    s2->probability * src1->frequency)
> ! 	   / (redirect_to->frequency + src1->frequency));
I think I will add EDGE_FREQUENCY macro for computing outgoing edge frequency.
This seems to be too common now...
> !       /* Non-obvious work limiting check: Recognize that we're going
> ! 	 to call try_crossjump_bb on every basic block.  So if we have
> ! 	 two blocks with lots of outgoing edges (a switch) and they
> ! 	 share lots of common destinations, then we would do the
> ! 	 cross-jump check once for each common destination.
> ! 
> ! 	 Now, if the blocks actually are cross-jump candidates, then
> ! 	 all of their destinations will be shared.  Which means that
> ! 	 we only need check them for cross-jump candidacy once.  We
> ! 	 can eliminate redundant checks of crossjump(A,B) by arbitrarily
> ! 	 choosing to do the check from the block for which the edge
> ! 	 in question is the first successor of A.  */
> !       if (e->src->succ != e)
> ! 	continue;
> ! 	  if (e->src->index > e2->src->index)
> ! 	    continue;

OK, it took me a while understand, but it looks correct and probably easier
than my solution.

> ! 	  /* ??? 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.
Frequencies are not unique and there may be multiple blocks with the same
frequency.


WOW, you've done wonderfull job!
Thanks a lot

Should I take care for removing the FALLTHRU test? What about the ??? comments.
Are my explanations enought to add into code?

Honza