[Bug tree-optimization/20492] New: [tcb] update_ssa (..., true) places an invalid PHI node.

[kazu at cs dot umass dot edu]

Change update_ssa (..., false) in tree-vrp.c to update_ssa (..., true).

Then compile the following, reduced from find_unreachable_blocks:

struct basic_block_def;

struct edge_def
{
  struct basic_block_def *dest;
};

typedef struct edge_def *edge;
typedef struct VEC_edge
{
  unsigned num;
  edge vec[1];
} VEC_edge;

struct basic_block_def
{
  VEC_edge *succs;
  int flags;
};

typedef struct basic_block_def *basic_block;

void
foo (basic_block * tos, basic_block * worklist)
{
  while (tos != worklist)
    {
      basic_block b = *--tos;
      unsigned ei_index = 0;

      while (1)
        {
          basic_block dest;
          edge e = b->succs->vec[ei_index];

          if (e == 0)
            break;

          dest = e->dest;
          if (dest->flags == 0)
            {
              *tos++ = dest;
              dest->flags = 1;
            }
          ei_index++;
        }
    }
}

I get:

kazu.c: In function ‘foo’:
kazu.c:25: error: Definition in block 2 does not dominate use in block 0
for SSA_NAME: tos_1 in statement:
tos_37 = PHI <tos_1(0), tos_1(2)>;
PHI argument
tos_1
for PHI node
tos_37 = PHI <tos_1(0), tos_1(2)>;
kazu.c:25: internal compiler error: verify_ssa failed.
Please submit a full bug report,
with preprocessed source if appropriate.
See <URL:http://gcc.gnu.org/bugs.html> for instructions.

I've verified that calling verify_ssa immediately after calling
update_ssa would catch this error.  That is, update_ssa is doing something
strange.

Here is the dump with ASSERT_EXPRs.

SSA form after inserting ASSERT_EXPRs
foo (tos, worklist)
{
  struct edge_def * e;
  struct basic_block_def * dest;
  unsigned int ei_index;
  struct basic_block_def * b;
  int D.1155;
  unsigned int ei_index.0;
  struct VEC_edge * D.1153;

  # BLOCK 0
  # PRED: ENTRY (fallthru,exec)
  goto <bb 6> (<L5>);
  # SUCC: 6 (fallthru,exec)

  # BLOCK 1
  # PRED: 6 (true,exec)
<L0>:;
  tos_34 = ASSERT_EXPR <tos_3, tos_3 != worklist_6>;
  tos_7 = tos_34 - 4B;
  b_8 = *tos_7;
  tos_11 = ASSERT_EXPR <tos_7, tos_7 != 0B>;
  # SUCC: 2 (fallthru,exec)

  # BLOCK 2
  # PRED: 1 (fallthru,exec) 5 (fallthru,exec)
  # ei_index_4 = PHI <0(1), ei_index_15(5)>;
  # tos_1 = PHI <tos_11(1), tos_2(5)>;
<L1>:;
  D.1153_10 = b_8->succs;
  b_9 = ASSERT_EXPR <b_8, b_8 != 0B>;
  e_12 = D.1153_10->vec[ei_index_4];
  D.1153_28 = ASSERT_EXPR <D.1153_10, D.1153_10 != 0B>;
  if (e_12 == 0B) goto <L5>; else goto <L2>;
  # SUCC: 6 (true,exec) 3 (false,exec)

  # BLOCK 3
  # PRED: 2 (false,exec)
<L2>:;
  e_33 = ASSERT_EXPR <e_12, e_12 != 0B>;
  dest_13 = e_33->dest;
  e_29 = ASSERT_EXPR <e_33, e_33 != 0B>;
  D.1155_14 = dest_13->flags;
  dest_30 = ASSERT_EXPR <dest_13, dest_13 != 0B>;
  if (D.1155_14 == 0) goto <L3>; else goto <L4>;
  # SUCC: 4 (true,exec) 5 (false,exec)

  # BLOCK 4
  # PRED: 3 (true,exec)
<L3>:;
  *tos_1 = dest_30;
  tos_31 = ASSERT_EXPR <tos_1, tos_1 != 0B>;
  tos_16 = tos_31 + 4B;
  dest_30->flags = 1;
  dest_32 = ASSERT_EXPR <dest_30, dest_30 != 0B>;
  # SUCC: 5 (fallthru,exec)

  # BLOCK 5
  # PRED: 3 (false,exec) 4 (fallthru,exec)
  # tos_36 = PHI <tos_1(3), tos_1(4)>;
  # tos_2 = PHI <tos_1(3), tos_16(4)>;
<L4>:;
  ei_index_15 = ei_index_4 + 1;
  goto <bb 2> (<L1>);
  # SUCC: 2 (fallthru,exec)

  # BLOCK 6
  # PRED: 0 (fallthru,exec) 2 (true,exec)
  # tos_37 = PHI <tos_1(0), tos_1(2)>;
  # tos_3 = PHI <tos_5(0), tos_1(2)>;
<L5>:;
  if (tos_3 != worklist_6) goto <L0>; else goto <L7>;
  # SUCC: 1 (true,exec) 7 (false,exec)

  # BLOCK 7
  # PRED: 6 (false,exec)
<L7>:;
  tos_35 = worklist_6;
  return;
  # SUCC: EXIT

}

Notice that tos_1(0) in

  # tos_37 = PHI <tos_1(0), tos_1(2)>;

Since this use of tos_1 appears in a PHI node, it is considered to be used
in the block 0, which is the very first basic block.
Since tos_1 is defined in block 2, and block 2 does not dominate block 0,
we get the ICE.

-- 
           Summary: [tcb] update_ssa (..., true) places an invalid PHI node.
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: kazu at cs dot umass dot edu
                CC: dnovillo at redhat dot com,gcc-bugs at gcc dot gnu dot
                    org


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