Re: [tree-ssa] COND_EXPR lowering

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

> > eh lowering created a few conflicts, here is a new version.
> 
> OK, Ive given it a quick run through.  I had to make a few changes to
> get it to work with the current branch. In particular, tree-ssa-dce.c is
> completely different, and I dont think it needs any further changes.
> 
> -The threading routine in tree-ssa-dom.c didn't delete gracefully, I
> dont know if additional changes were made to our branch are relevant or
> not. And remove_useless_vars... had been restructured.
> 
> I've attached your patch with these modifications so that it compiles.
> (I didn;t touch gimple-low.c, so I didnt include it) I've built and run
> it through the testsuites with the current branch. There are 28
> regressions in g++ and 13 or so in gcc. I havent looked at any of them.

this seems to be a wrong version of the patch :-( My fault, I took it
from other tree.  I will send the right version (with those suggestions
of yours that apply) as soon as possible.

> I also have some comments/questions:
> 
> > *************** set_parent_stmt (tree *stmt_p, tree pare
> > *** 630,635 ****
> > --- 592,601 ----
> >   {
> >     tree t;
> >   
> > +   if (parent_stmt
> > +       && TREE_CODE (parent_stmt) == COND_EXPR)
> > +     abort ();
> > + 
> >     /* Associate *STMT_P (and the trees it contains) to its control parent.  */
> >     t = *stmt_p;
> >     do
> 
> 
> Now the that COND_EXPR has a goto on each arm, are we deciding to treat
> the arms *not* as stmt's at all?  ie, It appears to me that we never set
> the basic block nor the parent of the GOTO's on each arm. Im not sure
> that this is a good thing. What do others think? That means if you have
> gneric code that does something with goto's, or follows paths, or
> whetever, processing COND_EXPR_THEN(stmt)  is going to give you a
> GOTO_EXPR that doesn't exactly match the pattern of a normal GOTO. (ie,
> BB will be NULL, it wont have any annotations, etc).   Now perhaps this
> is OK... I dont know, but it seems to me that it *might* cause a problem
> somewhere where this is unexpected. 
> 
> what is others opinions? I can see the argument from both sides and not
> sure at this moment what I think.

GOTOs in branches are not statements.  The whole cond_expr is considered
a single statement.  IMHO this is the whole point of the lowering -- to
simplify structured statements.  I don't see any problems with this --
everything that works over "paths" should work over cfg (and currently
it also does).  Not that it would be hard to add the annotation bits you
mention, but making this extra work unless it is actually needed by some
pass seems useless to me.

> > *************** remove_useless_stmts_and_vars (tree *fir
> > *** 1178,1249 ****
> <...>
> > ! 	  else if (TREE_CODE (then_clause) == GOTO_EXPR
> > ! 	      && TREE_CODE (else_clause) == GOTO_EXPR
> > ! 	      && (GOTO_DESTINATION (then_clause)
> > ! 		  == GOTO_DESTINATION (else_clause)))
> > ! 	    {
> > ! 	      *stmt_p = then_clause;
> > ! 	      repeat = 1;
> > ! 	    }
> 
> This has ben removed. Is cleanup_cfg() going to catch this and turn it
> into a straight goto?

yes.

> >   
> > *************** cleanup_cond_expr_graph (basic_block bb)
> > *** 1904,1917 ****
> >     tree cond_expr = last_stmt (bb);
> >     tree val;
> >     edge taken_edge;
> >   
> >   #if defined ENABLE_CHECKING
> >     if (cond_expr == NULL_TREE || TREE_CODE (cond_expr) != COND_EXPR)
> >       abort ();
> >   #endif
> >   
> > !   val = COND_EXPR_COND (cond_expr);
> > !   taken_edge = find_taken_edge (bb, val);
> >     if (taken_edge)
> >       {
> >         edge e, next;
> > --- 1793,1815 ----
> >     tree cond_expr = last_stmt (bb);
> >     tree val;
> >     edge taken_edge;
> > +   block_stmt_iterator bsi;
> >   
> >   #if defined ENABLE_CHECKING
> >     if (cond_expr == NULL_TREE || TREE_CODE (cond_expr) != COND_EXPR)
> >       abort ();
> >   #endif
> >   
> > !   if (!bb->succ)
> > !     return;
> > !   if (bb->succ->succ_next)
> > !     {
> > !       val = COND_EXPR_COND (cond_expr);
> > !       taken_edge = find_taken_edge (bb, val);
> > !     }
> > !   else
> > !     taken_edge = bb->succ;
> > ! 
> 
> When would !bb->succ not be an error.

When both successor blocks were removed.  This may happen in cases when
the block becomes unreachable (I don't remember details just now, but
it happened to me), and is later in the cleanup removed.

> Shouldn't a COND_EXPR *always*
> have 2 goto's? and therefor shouldn't it always have at least 1
> successor, in the case that both labels goto the same destination?
> 
> Or is this because the target label was deleted and the GOTO wasn't?
> Oughtn't that trigger an error? 
> 
> 
> 
> >   
> > *************** find_taken_edge (basic_block bb, tree va
> > *** 2019,2025 ****
> >     stmt = last_stmt (bb);
> >   
> >   #if defined ENABLE_CHECKING
> > !   if (stmt == NULL_TREE || !is_ctrl_structure (stmt))
> >       abort ();
> >   #endif
> >   
> > --- 1925,1931 ----
> >     stmt = last_stmt (bb);
> >   
> >   #if defined ENABLE_CHECKING
> > !   if (stmt == NULL_TREE || !is_ctrl_stmt (stmt))
> >       abort ();
> >   #endif
> >   
> 
> find_taken_edge is called from switch processing as well, and a
> SWITCH_EXPr is going to fail this test (it's a ctrl_structure). So I
> don't think we ought to change this just yet.

is_ctrl_structure implies is_ctrl_stmt.

> > *************** find_taken_edge_cond_expr (basic_block b
> > *** 2064,2072 ****
> >   	|| ((e->flags & EDGE_FALSE_VALUE) && always_false))
> >         return e;
> >   
> > !   /* If E is not going to the THEN nor the ELSE clause, then it's
> > !      the fallthru edge to the successor block of the if() block.  */
> > !   return find_edge (bb, successor_block (bb));
> >   }
> >   
> >   
> > --- 1970,1976 ----
> >   	|| ((e->flags & EDGE_FALSE_VALUE) && always_false))
> >         return e;
> >   
> > !   return NULL;
> >   }
> >   
> 
> Wouldn't this be an abort() situation too?  How can one of the edges of
> a COND_EXPR not be taken?

Probably. I will try.

> >   static int
> > ! phi_alternatives_equal (basic_block dest, edge e1, edge e2)
> >   {
> > !   tree phi, val1, val2;
> >   
> > !   for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
> >       {
> > !       val1 = PHI_ARG_DEF (phi, phi_arg_from_edge (phi, e1));
> > !       val2 = PHI_ARG_DEF (phi, phi_arg_from_edge (phi, e2));
> >   
> > !       if (!operand_equal_p (val1, val2, false))
> > ! 	break;
> >       }
> >   
> > !   return !phi;
> >   }
> 
> under ENABLE_CHECKING, we probably ought to make sure that
> phi_arg_from_edge() returns a valid argument. We have caught cases where
> we've screwed up PHI nodes by doing this.

I will add this check.

> > *************** dump_tree_bb (FILE *outf, const char *pr
> > *** 2402,2408 ****
> >     for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
> >       {
> >         fprintf (outf, "%s%s%d  ", s_indent, prefix, get_lineno (bsi_stmt (si)));
> > !       print_generic_stmt (outf, bsi_stmt (si), TDF_SLIM);
> >         fprintf (outf, "\n");
> >       }
> >   }
> > --- 2155,2164 ----
> >     for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
> >       {
> >         fprintf (outf, "%s%s%d  ", s_indent, prefix, get_lineno (bsi_stmt (si)));
> > !       if (TREE_CODE (bsi_stmt (si)) == COND_EXPR)
> > ! 	print_generic_stmt (outf, bsi_stmt (si), 0);
> > !       else
> > ! 	print_generic_stmt (outf, bsi_stmt (si), TDF_SLIM);
> >         fprintf (outf, "\n");
> >       }
> >   }
> 
> I think I'd rather teach dump_generic_node that under TDF_SLIM, if
> *both* sides of a COND_EXPR are GOTO's to also dump out the goto's. That
> was the interface stays consistant.. ie, there are lots of other places
> that we print stmt's and pass in TDF_SLIM... so I think it ought to show
> the GOTO's.

I am not sure whether it would not break other dumps; I will try.

> > --- 4151,4190 ----
> >   static int
> >   tree_verify_flow_info (void)
> >   {
> > !   int err = 0;
> > !   basic_block bb;
> > !   block_stmt_iterator bsi;
> > !   tree stmt;
> > ! 
> > !   FOR_EACH_BB (bb)
> > !     {
> > !       bsi = bsi_last (bb);
> > !       if (bsi_end_p (bsi))
> > ! 	continue;
> > ! 
> > !       stmt = bsi_stmt (bsi);
> > !       switch (TREE_CODE (stmt))
> > ! 	{
> > ! 	case COND_EXPR:
> > ! 	  if (TREE_CODE (COND_EXPR_THEN (stmt)) != GOTO_EXPR
> > ! 	      || TREE_CODE (COND_EXPR_ELSE (stmt)) != GOTO_EXPR)
> > ! 	    {
> > ! 	      fprintf (stderr, "Structured COND_EXPR at end of bb %d\n",
> > ! 		       bb->index);
> > ! 	      err = 1;
> > ! 	    }
> > ! 	  if (bb->flags & BB_CONTROL_STRUCTURE)
> > ! 	    {
> > ! 	      fprintf (stderr, "COND_EXPR in BB_CONTROL_STRUCTURE bb %d\n",
> > ! 		       bb->index);
> > ! 	      err = 1;
> > ! 	    }
> > ! 	  break;
> > ! 	default: ;
> > ! 	}
> > !     }
> > ! 
> > !   return err;
> >   }
> >   
> 
> I'd also like to see the entire body of tree_verify_flow_info() under an
> ENABLE_CHECKING flag.

this is not necessary, since verify_flow_info is only ever invoked with
ENABLE_CHECKING.

> > + /* Redirects edge E to basic block DEST.  Returns the new edge to DEST.  */
> > + edge
> > + thread_edge (edge e, basic_block dest)
> > + {
> > +   block_stmt_iterator dest_iterator = bsi_start (dest);
> 
> I didn't look at any of the edge threading code :-)
> 
> > Index: tree-eh.c
> > ===================================================================
> > RCS file: /cvs/gcc/gcc/gcc/Attic/tree-eh.c,v
> > retrieving revision 1.1.2.3
> > diff -c -3 -p -r1.1.2.3 tree-eh.c
> > *** tree-eh.c	18 Sep 2003 14:14:59 -0000	1.1.2.3
> > --- tree-eh.c	18 Sep 2003 19:33:30 -0000
> > *************** lower_eh_constructs_1 (struct leh_state 
> > *** 1492,1498 ****
> >   	  switch (TREE_CODE (tsi_stmt (j)))
> >   	    {
> >   	    case CATCH_EXPR:
> > - 	      lower_catch (state, tp);
> >   	      break;
> >   	    case EH_FILTER_EXPR:
> >   	      lower_eh_filter (state, tp);
> 
> 
> Why delete this?

This is of course wrong; it got in because I took it from wrong branch
(although I am not quite sure what it was doing there, anyway)

> > Index: tree-ssa-copyprop.c
> > ===================================================================
> > RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-copyprop.c,v
> > retrieving revision 1.1.2.14
> > diff -c -3 -p -r1.1.2.14 tree-ssa-copyprop.c
> > *** tree-ssa-copyprop.c	17 Sep 2003 17:06:34 -0000	1.1.2.14
> > --- tree-ssa-copyprop.c	18 Sep 2003 19:33:30 -0000
> > *************** propagate_copy (tree *op_p, tree var, tr
> > *** 241,247 ****
> >   void
> >   fixup_var_scope (tree var, tree scope)
> >   {
> > !   tree old_scope = var_ann (SSA_NAME_VAR (var))->scope;
> >   
> >     /* If there is no old_scope, it is a newly created temporary, i.e. it is
> >        in the topmost bind_expr and we have nothing to do.  */
> > --- 241,251 ----
> >   void
> >   fixup_var_scope (tree var, tree scope)
> >   {
> > !   tree old_scope;
> > !   
> > !   if (TREE_CODE (var) == SSA_NAME)
> > !     var = SSA_NAME_VAR (var);
> > !   old_scope = var_ann (var)->scope;
> >   
> >     /* If there is no old_scope, it is a newly created temporary, i.e. it is
> >        in the topmost bind_expr and we have nothing to do.  */
> > *************** fixup_var_scope (tree var, tree scope)
> > *** 256,262 ****
> >   	    scope = stmt_ann (scope)->scope;
> >   	}
> >         if (scope != old_scope)
> > ! 	move_var_to_scope (SSA_NAME_VAR (var), old_scope,
> >   			   DECL_SAVED_TREE (current_function_decl));
> >       }
> >   }
> > --- 260,266 ----
> >   	    scope = stmt_ann (scope)->scope;
> >   	}
> >         if (scope != old_scope)
> > ! 	move_var_to_scope (var, old_scope,
> >   			   DECL_SAVED_TREE (current_function_decl));
> >       }
> >   }
> 
> 
> These changes do not seem relevant to COND_EXPr lowering.. I assume its
> from something else? So we oughta remove these changes from the patch.

They are here because cond_expr lowering exposed some new problems with
scope assignment, so it is also necessary to call fixup_var_scope in
out-of-ssa pass, when variables are no longer inside SSA_NAME_VAR.

> > Index: tree-ssa.c
> > ===================================================================
> > RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
> > retrieving revision 1.1.4.127
> > diff -c -3 -p -r1.1.4.127 tree-ssa.c
> > *** tree-ssa.c	18 Sep 2003 08:39:34 -0000	1.1.4.127
> > --- tree-ssa.c	18 Sep 2003 19:33:31 -0000
> > *************** create_temp (tree t)
> > *** 895,901 ****
> >   static void
> >   insert_copy_on_edge (edge e, tree dest, tree src)
> >   {
> > !   tree copy;
> >   
> >     copy = build (MODIFY_EXPR, TREE_TYPE (dest), dest, src);
> >     set_is_used (dest);
> > --- 895,901 ----
> >   static void
> >   insert_copy_on_edge (edge e, tree dest, tree src)
> >   {
> > !   tree copy, scope, s1, s2;
> >   
> >     copy = build (MODIFY_EXPR, TREE_TYPE (dest), dest, src);
> >     set_is_used (dest);
> > *************** insert_copy_on_edge (edge e, tree dest, 
> > *** 910,915 ****
> > --- 910,932 ----
> >         print_generic_expr (dump_file, copy, dump_flags);
> >         fprintf (dump_file, "\n");
> >       }
> > +   /* If we are inserting a variable on boundaries of scopes, rather reset
> > +      the scope completely, since we don't know for sure where it should
> > +      be placed.  */
> > +   s1 = last_stmt (e->src);
> > +   s2 = last_stmt (e->dest);
> > +   if (!s1
> > +       || !s2
> > +       || !stmt_ann (s1)->scope
> > +       || !stmt_ann (s2)->scope
> > +       || stmt_ann (s1)->scope != stmt_ann (s2)->scope)
> > +     scope = NULL_TREE;
> > +   else
> > +     scope = stmt_ann (s1)->scope;
> > + 
> > +   if (TREE_CODE (src) == VAR_DECL)
> > +     fixup_var_scope (src, scope);
> > +   fixup_var_scope (dest, scope);
> >     bsi_insert_on_edge (e, copy);
> >   }
> 
> This looks like more unrelated scoping changes?

yes, it is just a problem exposed by the patch.  Since I could not
reproduce it without the patch, I did not post it separately.

> > 
> > /* Lowers the EXPR.  Unlike gimplification the statements are not relowered
> >    when they are changed -- if this has to be done, the lowering routine must
> >    do it explicitly.  */
> > 
> > void
> > lower_expr (tree *expr)
> > {
> >   tree_stmt_iterator tsi;
> > 
> >   for (tsi = tsi_start (expr); !tsi_end_p (tsi); tsi_next (&tsi))
> >     lower_stmt (&tsi);
> > }
> 
> lower_expr seems misleading to me. I would have assumed that its lowers
> and expression, not an entire list of stmts starting with the container
> passed in.  Perhaps a more appropriate name would be something like
> lower_stmts() or lower_stmt_chain() or lower_chain() or something of
> that nature.

it is already renamed in the correct version :-)

> > 
> > /* Lowers statement TSI.  */
> > static void
> > lower_stmt (tree_stmt_iterator *tsi)
> > {
> 
> Why are we passing a pointer to a tree iterator in to lower_stmt? Is it
> because someday the stmt being passed in might be replaced? Like a
> BIND_EXPR or a LOOP_EXPR?

Yes, it is here for case of BIND_EXPR removals.

> In that case, mightn't we have problems with the for loop in lower_expr?

Yes, it had to be slightly modified in BIND_EXPR removal patch.

Zdenek