Re: bug in dominance algorithm

[Daniel Berlin <dan at cgsoftware dot com>]

Taking a flying leap here (I'm about to leave for the airport), it may
be this code:
   /* It has no immediate dom or only ENTRY_BLOCK or EXIT_BLOCK.
             If it is a child of ENTRY_BLOCK that's OK, and it's only
             dominated by itself; if it's _not_ a child of ENTRY_BLOCK, it
             means, it is unreachable.  That case has been disallowed in the
             building of the DFS tree, so we are save here.  For the reverse
             flow graph it means, it has no children, so, to be compatible
             with the old code, we set the post_dominators to all one.  */
          if (!di->dom[i])
            {
              sbitmap_ones (dominators[bb]);
            }


The idoms are correct (right?):
	  0 =   2
	  1 =  -1
	  2 =   4
	  3 =  -1
	  4 =  -1

Which means it must be in the idom->dom stuff. And the above code is
the only part of that i can really see causing this.

I'm only semi-coherent right now, so if i'm not making any sense, just
ignore me.
:)
--Dan

>> Jan Hubicka <jh@suse.cz> writes:
>> 
>> > Hi,
>> > it looks like there is a bug in our dominance tree computation.
>> > In case I have two basic blocks with no successors, they are always
>> > postdominating each other, that is IMO false.
>> > Can someone more familiar with the algorithm check it?
>> 
>> I checked it against the implementations in other compilers (Almost
>> all use the same algorithm), and it looks just fine.
>> I didn't do an exhaustive check, however, and may have missed
>> something.
>> 
>> Can you send me some quick C code to demonstrate the problem?
>> I'm having a bit of trouble generating two basic blocks with no
>> successors, that it say postdominate each other.
> I was reproducing it on something like
> 
> #include <stdlib.h>
> test(int a, int b)
> {
>   if (a)
>     abort();
>   if (b)
>     abort();
>}
> 
> Now my branch predicting algorithm identifies two blocks with no exists
> (1 and 3). Then it does for each of them (B) following:
> 
> looks and for each basic block (C) that has postdominator B it looks for each
> entry edge.  If some of the edge goes from block that has no postdominator B,
> it marks the edge as improbable.
> 
> Problem is that each edge gets marked as many times as many aborts are in the
> function.
> I've checked that 1 is set as postdominator of 3 and vice vesa.
> Both is wrong IMO
> 
> Honza
>> 
>> --Dan
>> > 
>> > Honza
>> 
>> -- 
>> "This is my impression of a bowling ball...  (Drags the mike
>> along the floor, then lifts it...)  Gutter...
>> "-Steven Wright

-- 
"Do you think that when they asked George Washington for ID that
he just whipped out a quarter?
"-Steven Wright