Canonical form of the RTL CFG for an IF-THEN-ELSE block?

[Kenneth Zadeck]

Jan Hubicka wrote:

>>Hi,
>>
>>We would like to know if there is some way to find the true and false
>>branches of a conditional jump in RTL.  In the tree CFG, we have two
>>edge flags for that, EDGE_{TRUE,FALSE}_VALUE, but those flags have no
>>meaning for the RTL CFG.  So our question is, is there some other way
>>to tell what edge will be taken in a conditional jump if the condition
>>is true?
>>
>>It seems that some passes assume a canonical form of IF-THEN-ELSE even
>>on RTL.  From ifcvt.c:find_if_header:
>>
>>  /* The THEN edge is canonically the one that falls through.  */
>>  if (then_edge->flags & EDGE_FALLTHRU)
>>    ;
>>  else if (else_edge->flags & EDGE_FALLTHRU)
>>    {
>>      edge e = else_edge;
>>      else_edge = then_edge;
>>      then_edge = e;
>>    }
>>  else
>>    /* Otherwise this must be a multiway branch of some sort.  */
>>    return NULL;
>>
>>On the other hand, in cfgexpand.c:expand_gimple_cond_expr we have,
>>
>>  false_edge->flags |= EDGE_FALLTHRU;
>>
>>and loop-unswitch.c assumes that the BRANCH_EDGE is the true_edge:
>>
>>  true_edge = BRANCH_EDGE (unswitch_on_alt);
>>  false_edge = FALLTHRU_EDGE (unswitch_on);
>>
>>So which is it?  Is BRANCH_EDGE always taken if the condition is true,
>>or FALLTHRU_EDGE, or do you have to look at the condition to know?
>>Who knows an answer?  :-)
>>    
>>
>
>:) It depends on how the conditional is constructed.
>If you use get_condition the edge taken when conditional is true is
>always BRANCH_EDGE if some exists (it is possible to have conditional
>jump to the following instruction where you have only one edge with
>EDGE_FALLTHRU flag).
>Otherwise you have to look into conditional jump RTL yourself to figure
>out if it has form
>(set (pc) (if_then_else (cond) (pc) (label_ref xxx))
>or
>(set (pc) (if_then_else (cond) (label_ref xxx) (pc))
>
>In the first case we are taking barnch edge when conditional is false.
>
>  
>
It seems there are two approaches to solving this problem, constructive 
and preservative.   According to danny, the constructive approach is 
what is used in the rtl level if-conversion and is dead slow.  In the 
preservative approach, you keep the markings that are inserted from the 
tree code and track their changes as the rtl gets modified.  This 
assumes that we do not throw away the cfg right before rtl generation, 
which may be a big assumption or at least you add notes in the rtl that 
preserves this information for later reconstruction.

I have to admit that I am always a fan of preserving information rather 
than reconstructing it.  This need to just keep rescanning the 
intermediate representation over and over again is a big flaw in gcc and 
contributes adversely to the performance. 

kenny


>Honza
>  
>
>>Gr.
>>Steven
>>    
>>