Control dependence vs. builtin_unreachable

[Steven Bosscher <stevenb dot gcc at gmail dot com>]

Hello,

Consider the following test case:

void bar (void);
int foo (int b, int c, int d)
{
  int r = 0;
  if (b)
    res = b * 2 + 4;
  if (c)
    {
      if (d)
        r = res;
      else
        __builtin_unreachable ();
    }
  return r;
}

This is typical for code in GCC itself in places where
gcc_unreachable() is used.

The corresponding CFG looks like this:

            +-----+
            | bb0 |
            +-----+
              |
              |
              v
            +-----+
            | bb2 | -+
            +-----+  |
              |      |
              |      |
              v      |
            +-----+  |
            | bb3 |  |
            +-----+  |
              |      |
              |      |
              v      |
+-----+     +-----+  |
| bb8 | <-- | bb4 | <+
+-----+     +-----+
  |           |
  |           |
  |           v
  |         +-----+     +-----+
  |         | bb5 | --> | bb7 |
  |         +-----+     +-----+
  |           |
  |           |
  |           v
  |         +-----+
  |         | bb6 |
  |         +-----+
  |           |
  |           |
  |           v
  |         +-----+
  +-------> | bb9 |
            +-----+
              |
              |
              v
            +-----+
            | bb1 |
            +-----+

In the postdominator tree of the test case, the basic block containing
the call to __builtin_unreachable is postdominated by the EXIT block
(either via fake edges to exit, or by the dead-end handling code in
dominance.c), which makes the "return r" statement control-dependent
on "if (c)" and "if (d)". See the attached CFG dump (t.c.012.cfg.dot)
and the corresponding CFG, postdominator tree, and control dependence
graphs (cdg_bad.dot). Here is the CDG in ascii:

            +-----+
            | bb0 |
            +-----+
              |
   +----------+-----------+
   |          |           |
   v          v           v
+-----+     +-----+     +-----+
| bb2 |     | bb4 |     | bb1 |
+-----+     +-----+     +-----+
   |          |
   |          +-----------+-----------+
   |          |           |           |
   v          v           v           |
+-----+     +-----+     +-----+       |
| bb3 |     | bb5 |     | bb8 |       |
+-----+     +-----+     +-----+       |
              |                       |
   +----------+-----------+           |
   |          |           |           |
   v          v           v           |
+-----+     +-----+     +-----+       |
| bb6 |     | bb7 |     | bb9 |<------+
+-----+     +-----+     +-----+


My question here, is whether __builtin_unreachable (or any other
empty, dead-end basic block) should be taken into account for control
dependence.

Since, by definition, __builtin_unreachable is not reachable, so the
statement "return r" is always executed. So it seems to me that the
"correct" CDG should look like the one in the attached cdg_wish.dot,
or in ascii:

            +-----+
            | bb0 |
            +-----+
              |
   +----------+-----------+-----------+
   |          |           |           |
   v          v           v           v
+-----+     +-----+     +-----+     +-----+
| bb2 |     | bb4 |     | bb9 |     | bb1 |
+-----+     +-----+     +-----+     +-----+
   |          |
   |          +-----------+
   |          |           |
   v          v           v
+-----+     +-----+     +-----+
| bb3 |     | bb5 |     | bb8 |
+-----+     +-----+     +-----+
              |
   +----------+
   |          |
   v          v
+-----+     +-----+
| bb6 |     | bb7 |
+-----+     +-----+


These "false" control dependences are in my way for a couple of
tree-ssa-sink improvements, and probably are harmful for other
control-dependence based transformations as well. It also makes the
control dependence graph larger and more complex than necessary.

Thoughts/comments, ye respected experienced folks? :-)

Thanks,

Ciao!
Steven

Attachment: cdg_bad.dot
Description: Binary data

Attachment: cdg_wish.dot
Description: Binary data

Attachment: t.c.012t.cfg.dot
Description: Binary data