[tree-ssa] COND_EXPR lowering.

[Andrew MacLeod <amacleod at redhat dot com>]

Jeff ought to look at the jump threading since hes doing related work in
the dominator optimizations.

>   basic_block
> *************** make_goto_expr_edges (basic_block bb)
> *** 1172,1197 ****

>        in the CFG.  */
>     FOR_EACH_BB (target_bb)
>       {
> !       block_stmt_iterator bsi;
>   
> !       for (bsi = bsi_start (target_bb); !bsi_end_p (bsi); bsi_next (&bsi))
> ! 	{
> ! 	  tree target = bsi_stmt (bsi);
> ! 
> ! 	  if (TREE_CODE (target) != LABEL_EXPR)
> ! 	    break;
>   
> ! 	  /* Computed GOTOs.  Make an edge to every label block that has
> ! 	     been marked as a potential target for a computed goto.  */
> ! 	  if (TREE_CODE (dest) != LABEL_DECL
> ! 	      && TREE_CODE (target) == LABEL_EXPR
> ! 	      && FORCED_LABEL (LABEL_EXPR_LABEL (target))
> ! 	      && for_call == 0)
> ! 	    make_edge (bb, target_bb, edge_flags);
> ! 
> ! 	  /* Nonlocal GOTO target.  Make an edge to every label block that has
> ! 	     been marked as a potential target for a nonlocal goto.  */
> ! 	  else if (TREE_CODE (dest) != LABEL_DECL
> ! 		   && TREE_CODE (target) == LABEL_EXPR
> ! 		   && NONLOCAL_LABEL (LABEL_EXPR_LABEL (target))
> ! 		   && for_call == 1)
> ! 	    make_edge (bb, target_bb, edge_flags);

We might as well break out of the for loop after make_edge(). It doesnt
really serve a purpose to keep going.


>     cleanup_control_flow ();
> +   thread_jumps ();
> +   cleanup_control_flow ();
>     remove_unreachable_blocks ();

<...>

> *************** remove_bb (basic_block bb, int remove_st
> *** 1860,1867 ****
>           {
>   	  int ctrl_struct = is_ctrl_structure (stmt);
>   
> ! 	  loc.file = get_filename (stmt);
> ! 	  loc.line = get_lineno (stmt);
>   	  if ((ctrl_struct && (remove_stmt_flags & REMOVE_CONTROL_STRUCTS))
>   	      || (!ctrl_struct && (remove_stmt_flags & REMOVE_NON_CONTROL_STRUCTS)))
>   	    bsi_remove (&i);
> --- 1823,1838 ----
>           {
>   	  int ctrl_struct = is_ctrl_structure (stmt);
>   
> ! 	  if (get_lineno (stmt) != -1
> ! 	      /* Don't warn for removed gotos.  Gotos are often removed due to jump threading,
> ! 		 thus resulting into bogus warnings.  Not great, since this way we lose warnings
> ! 		 for gotos in the original program that are indeed unreachable.  */
> ! 	      && TREE_CODE (stmt) != GOTO_EXPR)
> ! 	    {
> ! 	      loc.file = get_filename (stmt);
> ! 	      loc.line = get_lineno (stmt);
> ! 	      empty = false;
> ! 	    }

How big a deal is it that we issue the warning about unreachable goto's?

In order to get it right, we'd almost have to pass a flag into
remove_unreachable_blocks indicating whether we want to issue the
warning, and then add a call to remove_unreachable_blocks() after the
cleanup_control_flow() call, and before jump threading.  And presumably
we'd only want to so this the first time cleanup_tree_cfg() is called
for a function.. Which implies a bit in the functions DECL node, or a
global flag set in optimize_function_tree for each function. 
giving up something like

  cleanup_control_flow ();
  if (!performed_cleanup_call)
    {
       performed_cleanup_call = true;
       remove_unreachable_blocks (true);
    }
  thread_jumps ();
  cleanup_control_flow ();
  remove_unreachable_blocks (false);

So do we need to get this warning right?

> *************** cleanup_control_flow (void)
> *** 2146,2186 ****
>     basic_block bb;

>     FOR_EACH_BB (bb)
> !     {
> !       tree last = last_stmt (bb);
> !       if (last)
> ! 	{
> ! 	  enum tree_code code = TREE_CODE (last);
> ! 	  if (code == COND_EXPR)
> ! 	    cleanup_cond_expr_graph (bb, last);
> ! 	  else if (code == SWITCH_EXPR)
> ! 	    cleanup_switch_expr_graph (bb, last);
> ! 	}
> !     }
>   }

> *************** cleanup_cond_expr_graph (basic_block bb,
> *** 2195,2201 ****
> --- 2169,2184 ----
>   	      retval = true;
>   	    }
>   	}
> + 
> +       bsi = bsi_last (bb);
> +       if (taken_edge->flags & EDGE_TRUE_VALUE)
> + 	bsi_replace (bsi, COND_EXPR_THEN (cond_expr));
> +       else if (taken_edge->flags & EDGE_FALSE_VALUE)
> + 	bsi_replace (bsi, COND_EXPR_ELSE (cond_expr));
> +       else
> + 	abort ();
>       }
> + 
>     return retval;
>   }
>   

Since stmt_last and bsi_last do the same thing, and under some
circumstance can be expensive, I'd suggest using bsi_last() in
cleanup_control_flow() instead of last_stmt, and passing the BSI into
cleanup_cond_expr_graph () avoiding the second call.



> + 
> + 	  slow = e->dest;
> + 	  set_slow = 0;
> + 
> + 	  last = e->dest->succ;
> + 	  for (dest = e->dest->succ->dest;
> + 	       tree_forwarder_block_p (dest);
> + 	       last = dest->succ,
> + 	       dest = dest->succ->dest,
> + 	       set_slow ^= 1)
> + 	    {
> + 	      /* Infinite loop detected.  */
> + 	      if (slow == dest)
> + 		break;
> + 	      if (set_slow)
> + 		slow = slow->succ->dest;
> + 
> + 	      if (dest->succ->dest == EXIT_BLOCK_PTR)
> + 		break;
> + 	    }
> + 
> + 	  if (dest == e->dest)
> + 	    continue;
> + 	      

So if we do detect and infinite loop, we might still redirect the edges
anyway? Does that actually serve a purpose? It looks like we'd be
threading into an arbitary point in the cycle?



I get 2 additional failures in gcc, which I haven't looked at. I beleive
you said there would be at least one.

< PASS: gcc.dg/old-style-asm-1.c scan-assembler L(:|\$0*)?2
---
> FAIL: gcc.dg/old-style-asm-1.c scan-assembler L(:|\$0*)?2
24081c24081
< PASS: gcc.dg/tree-ssa/20030710-1.c scan-tree-dump-not blah \(\)
---
> FAIL: gcc.dg/tree-ssa/20030710-1.c scan-tree-dump-not blah \(\)
24519,24520c24519,24520


The only other thing that I think Diego agreed with (yes? no?) is that
we probably ought to set the BB for the 2 goto's on the arms of the
COND_EXPR. Yeah, they aren't real stmt's, but there is no reason someone
couldn't look at them as real stmts.. ie, someone doing path following
may want to process the 2 arms exactly like they process a GOTO, so we
ought to make them behave like a GOTO stmt for consistancy, so we ought
to set their BB.
ie, we could see something like:
if (TREE_CODE (expr) == GOTO_EXPR
  follow_goto (expr)
else
if (TREE_CODE (expr) == COND_EXPR)
  {
    follow_goto (COND_EXPR_THEN (expr));
    follow_goto (COND_EXPR_ELSE (expr));
  }
where follow_goto wants to treat it just like a stmt, and may ask for
the BB...

Other than that, it looks good to go to me.

Oops, my x86 bootstrap with this patch just died in PRE:

insn-recog.c:17561: internal compiler error: virtual array
basic_block_info[5349]: element 3537031808 out of bounds in
insert_occ_in_preorder_dt_order_1, at tree-ssa-pre.c:903
Please submit a full bug report,
with preprocessed source if appropriate.
See <URL:http://gcc.gnu.org/bugs.html> for instructions.
make[1]: *** [insn-recog.o] Error 1
make[1]: Leaving directory `/build/tree-ssa/2003-10-21/gcc'
make: *** [stage2_build] Error 2

My source tree is a couple of days old, I'll try it with a fresh tree
too.

Andrew