[Bug tree-optimization/55124] [4.8 Regression] ICE in find_or_generate_expression, at tree-ssa-pre.c:2803

["rguenth at gcc dot gnu.org" <gcc-bugzilla at gcc dot gnu dot org>]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55124

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> 2012-11-30 12:33:03 UTC ---
This issue is latent and papered over heavily by find_or_generate_expression
which does

static tree
find_or_generate_expression (basic_block block, tree op, gimple_seq *stmts)
{
  pre_expr expr = get_or_alloc_expr_for (op);
  unsigned int lookfor = get_expr_value_id (expr);
  pre_expr leader = bitmap_find_leader (AVAIL_OUT (block), lookfor);
  if (leader)
    {
      if (leader->kind == NAME)
        return PRE_EXPR_NAME (leader);
      else if (leader->kind == CONSTANT)
        return PRE_EXPR_CONSTANT (leader);
    }

  /* It must be a complex expression, so generate it recursively.  */
  bitmap exprset = value_expressions[lookfor];
  bitmap_iterator bi;
  unsigned int i;
  EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
    {
      pre_expr temp = expression_for_id (i);
      if (temp->kind != NAME)
        return create_expression_by_pieces (block, temp, stmts,
                                            get_expr_type (expr));
    }


thus - it picks some _random_ expression and tries to generate it.
Most of the time it happens to pick the correct one.

In theory - with proper insert ordering - we should never end up
here with no leader, we should never even end up with a complex
leader either!  (in fact bitmap_find_leader should, according to
its documentation, never return a complex leader)

Now, for tree-ssa/ssa-pre-28.c we have

  <bb 2>:
  if (b_2(D) != 0)
    goto <bb 5>;
  else
    goto <bb 3>;

  <bb 5>:
  goto <bb 4>;

  <bb 3>:

  <bb 4>:
  # mask_1 = PHI <-2(5), 0(3)>
  result_4 = i_3(D) + 1;
  result_5 = mask_1 & result_4;
  return result_5;

we start to try inserting both i_3(D) + 1 and mask_1 & result_4 (simplified to
0 in bb3!) in bb 5.  But i_3(D) + 1 is neither available in bb3 nor in bb5 so
we don't insert it.  This means upon trying to insert mask_1 & result_4 in
bb 5 we don't find a leader for result_4 because we didn't insert the
expression (we thought it was not profitable or necessary to do so).

Which means insertion works in an awkward way currently.  It seems it should
compute which expressions it likes to insert (and where, and using the
translated expressions) and then add value-dependencies out of that set.
And only in a second step actually perform the insertions (but then in
proper order).