[PATCH] factor out generic (de)initialization of ANTIC and AVAIL in PRE

[Daniel Berlin]

On Wed, Jun 18, 2008 at 3:57 PM, Bernhard Fischer <rep.dot.nop@gmail.com> wrote:
> On Wed, Jun 18, 2008 at 03:30:27PM -0400, Daniel Berlin wrote:
>>On Wed, Jun 18, 2008 at 3:18 PM, Bernhard Fischer <rep.dot.nop@gmail.com> wrote:
>>> Hi,
>>>
>>> The attached patch factors the (de)initialization of ANTIC and AVAIL
>>> sets used by PRE into init_antic() and fini_antic().
>>>
>>> The patch was bootstrapped and regtested with languages=c,fortran on
>>> i686 with no regressions.
>>> OK for trunk?
>>+static bool
>>+bitmap_set_empty_p (const bitmap_set_t set)
>>+{
>>+  return !((set->values && !bitmap_empty_p (set->values))
>>+         && (set->expressions && !bitmap_empty_p (set->expressions)));
>>
>>Uh, why not "!set->values || bitmap_empty_p (set->values) ||
>>!set->expressions || bitmap_empty_p (set->expressions)"
>>
>>(IE the not in front of the things and the && are confusing to me)
>
> Ok, i'll rephrase this.
>>
>>
>>+static void
>>+bitmap_set_ior_into (bitmap_set_t dest, bitmap_set_t orig)
>>+{
>>+  if (dest != orig)
>>+    {
>>+      bitmap_ior_into (dest->values, orig->values);
>>+      bitmap_ior_into (dest->expressions, orig->expressions);
>>+    }
>>+}
>>
>>This isn't right.
>>
>>The bitmap sets maintain the invariant that only one leader for a
>>given value exists in the set.
>>
>>IE it is not possible to have a set like so:
>>
>>ANTIC_IN[5] = { a_3 (VH.4), b_7 (VH.4) }
>>
>>(Note that both are leaders for the value 4).
>>
>>Your bitmap_ior will break this invariant.
>>
>>The code is carefully written to maintain this invariant (This is why
>>there are things like bitmap_insert_into_set for places we know don't
>>have a leader, and bitmap_value_insert_into_set for places where we
>>don't).
>>
>>
>>The correct way to ior the sets is to do either:
>>1. Assuming you want leaders in dest to not be overridden by leaders in src
>>for each expression in src
>>if !bitmap_set_contains_value (dest)
>>  bitmap_insert_into_set(dest, expression)
>>
>>2.  Assuming you want leaders in dest to be overridden by leaders in src
>>For each expression in src
>>bitmap_value_replace_into_set (dest, expression):
>>
>>
>>This is a "value-wise" union.
>>This is what the code
>>
>>* Then union in the ANTIC_OUT - TMP_GEN values,
>>     to get ANTIC_OUT U EXP_GEN - TMP_GEN */
>>  FOR_EACH_EXPR_ID_IN_SET (S, bii, bi)
>>    bitmap_value_insert_into_set (ANTIC_IN (block),
>>                                  expression_for_id (bii));
>>
>>
>>Is doing.
>
> Would this explain why i see intermittent stmts that are (VN*) for e.g.
> PR5738 ? i.e. I get statements that point to some VN, which of course
> fails miserably if i try to move them, which led me to think that
> something went amiss in VN since i would have assumed that i get a
> fully "resolved" tree, without intermittent VN.
> Though that doesn't come into play WRT this ior AFAIR. I would only
> possibly consider wrong stmts, but still, all stmts should be fully
> resolvable, i think.
>
> Currently, i basically do
>
> FOR_EACH_EDGE (e, ei, bb->succs)
> {
>  if (is_new)
>    {
>      nack = bitmap_set_new ();
>      candidates = bitmap_set_new ();
>      bitmap_set_copy (candidates, ANTIC_IN (e->dest));
>      /* Disregard values that are already available in the bb.  */
>      tmp = bitmap_set_subtract (candidates, AVAIL_OUT (bb));
>      bitmap_set_free (candidates);
>      candidates = tmp;
>      is_new = false;
>    }
>
>  tmp = bitmap_set_subtract (ANTIC_IN (e->dest), candidates);
>
>  bitmap_set_ior_into (nack, tmp);
>  bitmap_set_free (tmp);
>
>  tmp = bitmap_set_subtract (candidates, ANTIC_IN (e->dest));
>
>  bitmap_set_ior_into (nack, tmp);
>  bitmap_set_free (tmp);

This won't work.

nack can end up with multiple expressions for the same value, and PRE
will only ever "see" (IE the bitamp_find_leader/etc functions) the
first one it comes across in the expression list.

The easy way to check this is to assert (bitmap_count_bits
(nack->expressions) == bitmap_count_bits (nack->values));
> What about the rest, i.e. moving the {init,fini}_antic()? :)
>

The rest looks okay to me ;)