Collapsing control-flow that leads to undefined behavior

[Richard Guenther]

On Wed, Oct 7, 2009 at 8:53 AM, Charles J. Tabony
<tabonyee@austin.rr.com> wrote:
> Fellow GCC developers,
>
> Does GCC make any effort to collapse control-flow that is guaranteed to
> have undefined behavior?  Such an optimization would improve performance
> of Proc_2 from Dhrystone:
>
>
> typedef int     One_Fifty;
>  typedef       enum    {Ident_1, Ident_2, Ident_3, Ident_4, Ident_5}
>                Enumeration;
> char            Ch_1_Glob,
>                Ch_2_Glob;
> int             Int_Glob;
>
> Proc_2 (Int_Par_Ref)
> /******************/
>    /* executed once */
>    /* *Int_Par_Ref == 1, becomes 4 */
>
> One_Fifty   *Int_Par_Ref;
> {
>  One_Fifty  Int_Loc;
>  Enumeration   Enum_Loc;
>
>  Int_Loc = *Int_Par_Ref + 10;
>  do /* executed once */
>    if (Ch_1_Glob == 'A')
>      /* then, executed */
>    {
>      Int_Loc -= 1;
>      *Int_Par_Ref = Int_Loc - Int_Glob;
>      Enum_Loc = Ident_1;
>    } /* if */
>  while (Enum_Loc != Ident_1); /* false */
> } /* Proc_2 */
>
>
> The variable Enum_Loc is referenced in the condition of the do-while
> loop, but the only place it is set is inside the if block.  For this
> code to have defined behavior, the code in the if block must be
> executed.  Thus, it is valid to transform the code to the equivalent of
>
>
> Proc_2 (Int_Par_Ref)
> One_Fifty   *Int_Par_Ref;
> {
>  *Int_Par_Ref += 9 - Int_Glob;
> }
>
>
> Does any pass in GCC attempt to do anything like this?  If not, how
> feasible would it be?
>
> GCC already eliminates the do-while loop during the Conditional Constant
> Propogation pass.  It appears that ccp1 is able to deduce that the value
> of Enum_Loc in the do-while condition is either Ident_1 or undefined.
> It proceeds to substitute Ident_1 for Enum_Loc and fold the condition.
>
> Once ccp1 (or some earlier pass) finds a basic block that references a
> variable that is undefined on an incoming edge, how feasible would it be
> to eliminate that edge and any control-flow post-dominated by that edge?

Hum - it's not difficult, you could simply split the basic-block at
the reference of a SSA name default definition, replace that reference
by a __builtin_trap (), remove the fallthrough edge and remove
unreachable blocks.

That is, you of course have to ensure the SSA name use really
invokes undefined behavior (as opposed to, say 0 * x_2(D)).

Richard.

> Thank you,
> Charles J. Tabony
>
>