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

[Bernhard Fischer]

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);

  /* Finally remove the nack set from the legitimate candidates.  */
  tmp = bitmap_set_subtract (candidates, nack);
  bitmap_set_free (candidates);
  candidates = tmp;
}
to find candidates. And then try to resolve and touch them via something
like:
  FOR_EACH_EXPR_ID_IN_SET (candidates, i, bi)
    {
      tree expr = expression_for_id (i);

      if (!bitmap_set_contains_value (AVAIL_OUT (bb),
				      get_value_handle (expr)))
	{
	  tree gen;
	  tree stmts = alloc_stmt_list();

	  changed = true;

	  if (dump_file)
	    {
	      fprintf (dump_file, "Pondering to insert expr ");
	      print_generic_stmt (dump_file, expr, TDF_MEMSYMS);
	      fprintf (dump_file, "\n");
	    }

	  if (can_PRE_operation (expr))
	    {
	      gen = create_expression_by_pieces (bb, expr, stmts,
						 NULL_TREE);
	      if (gen)
		bsi_insert_after (&bsi, stmts, BSI_NEW_STMT);
/* The above sometimes fails since some don't have parents! */
	    }
	  bitmap_value_replace_in_set (AVAIL_OUT (bb), expr);
	}
      else
	fprintf (dump_file, "Nothing to insert..\n");


I will take a closer look at the ior logic.

What about the rest, i.e. moving the {init,fini}_antic()? :)