Re: Control dependence vs. builtin_unreachable

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

On Thu, Jan 3, 2013 at 9:51 PM, Jeff Law wrote:
> On 01/03/2013 12:01 PM, Steven Bosscher wrote:
>>
>> 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 |
>>              +-----+
>
> Presumably BB7 was created in response to the builtin_unreachable?

Yes. The block only contains the BB_UNREACHABLE call. It is cleaned up
at the end of the GIMPLE passes pipeline, in the fold-all-builtins
pass (most __builtin_unreachable calls are, but not all).


> One
> could argue that an empty dead-end basic block should just be removed and
> the CFG appropriately simplified.

The problem with this, is that __builtin_unreachable actually exposes
optimization opportunities: more const/copy props of "implicit sets"
in the predicate guarding the __builtin_unreachable call, more
optimistic value numbering, etc. It also helps improve maybe-unused
warnings accuracy. So simply removing these "dead ends" in the CFG is
probably not a good idea.


> You might want to look  at a discussion from Oct/Nov 2011 "New pass to
> delete unexecutable paths in the CFG" which touches on some of this stuff.

That's a really interesting discussion! I must have missed it at the time :-)


> It's not 100% the same, but the concept of eliminating edges from the CFG
> which we can never traverse in a conforming program applies to both your
> example and the stuff I was playing with.

I think there is one important difference: In the thread you referred
to, you're removing paths in the CFG that are implicitly not
executable (for some languages anyway), whereas a
__builtin_unreachable call is an explicit marker for "this can never
happen". I think this difference is important:

* The explicit marker may have been put there on purpose (e.g. to get
rid of a false-positive warning). The compiler should respect that. An
implicit unreachable path can be optimized away without regard for the
user's intent.

* The explicit marker should not inhibit optimizations. For an
implicit unreachable path the compiler should be conservative. But for
a __builtin_unreachable call that is the only statement in a basic
block, the compiler should be allowed to work as if the block really
is never reached.

The attached patch implements these ideas. During a tree-CFG cleanup,
basic blocks containing only a __builtin_unreachable call are marked
with a new flag BB_NEVER_REACHED. The flag is used in post-dominance:
A marked block is not considered in the computations of the immediate
post-dominator of the predecessor blocks. The result is a more
optimistic post-dominance tree: Without the patch all predecessors of
these BB_NEVER_REACHED blocks have the EXIT block as their
post-dominator, but with the patch this non-executable path in the CFG
is ignored and the post-dominators are those that would result if the
BB_NEVER_REACHED blocks are not there at all (the BB_NEVER_REACHED
blocks themselves are only post-dominated by the EXIT block).

I've also added a control dependence calculation function. It's not
currently used, but it shows how the BB_NEVER_REACHED flag is used in
this case to avoid the "false" control dependences that I showed in
the graphs in http://gcc.gnu.org/ml/gcc/2013-01/msg00021.html.

Bootstrapped&tested on powerpc64-unknown-linux-gnu.
What do you think of this approach?

Ciao!
Steven

Attachment: pdom_b_i_u.diff.txt
Description: Text document