On Sat, Jan 5, 2013 at 9:10 PM, Steven Bosscher <stevenb....@gmail.com> wrote:
> 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?
Does it handle side-effects on the builtin-unreachable path correctly?
int b;
int a;
extern void foo ();
int main()
{
if (!a)
{
if (!b)
foo ();
__builtin_unreachable ();
}
}
---
void foo () { puts("Hello"); exit(0); }
? Users are not _required_ to annotate noreturn functions. The BB with
__builtin_unreachable () is still empty otherwise.
Thanks,
Richard.
> Ciao!
> Steven
