Collapsing control-flow that leads to undefined behavior

Collapsing control-flow that leads to undefined behavior

[Charles J. Tabony]

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?

Thank you,
Charles J. Tabony

Re: 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
>
>