Re: [tree-ssa] COND_EXPR lowering preview

[Andrew MacLeod <amacleod at redhat dot com>]

On Fri, 2003-08-29 at 15:17, Andrew MacLeod wrote:
> On Fri, 2003-08-29 at 15:08, law@redhat.com wrote:
> > In message <1062014434.4452.15.camel@frodo.toronto.redhat.com>, Diego Novillo w
> 
> Is it? If we mark all the control stmts as necessary, and remove our
> control flow checking code, you are left with something which seems
> fairly  minimal to me.. A pass through the IL to see whats needed, and
> then visit any stmts which are forced as necessary by other stms which
> are necessary... (the worklist).  You'd never visit any stmt more than
> twice, and you never have to go hunting for anything.  control stmts
> would never be looked at again.
> 

So here's option 1.  Never try to remove control flow in DCE. This
streamlines the algorithm quite a bit. We simply mark anything which is
control flow or the target of control flow as necessary. So we make one
pass through looking for interesting stmts, and the thr worklist is used
to visit stmts that become necessary. So at worst, stmt's are visted
twice.

This passes all the tests, and is bootstrapping as I speak.

If we ever decide we want to put control flow analysis back in, I have
the code handy. Maybe if we go this route we can simply put the issue to
bed for the moment. I am getting weary of hedging. I think we should
just do this for now.   opinions?


Andrew

PS, it occurs to me there is some marginal room for improvement if we
process the stmts bottom-up. We could do something with the fact that we
haven't visited the dependant stmt's yet, and may be able to bypass some
of the worklist. Something simple like mark dependant stmt's as
necesaary and if the algorithm hasn't finished visiting the block the
stmt is in yet, simply wait until we get to it to handle dependant
stmts.  The prevents the check on opcode at the start of
interetsing_stmt too. I think You could bypass the worklist completely
this way, and never get into too much recursiveness.. only around back
edges.  Perhaps we simple use the worklist for stmts which are necessary
whihc are in blocks we have already visited. Thats sounds fairly
efficient. No recursiveness, and a minimally sized worklist.... MOst
stuff handled during the first pass.

I'll fool with that when I get a chance.



	tree-ssa-dce.c (dom_info, pdom_info): Remove.
	(mark_tree_necessary): Rename to mark_neccesary, no return value.
	(mark_necessary): Remove.
	(stmt_useful_p): Control stmts are always useful.
	(process_worklist): Never examine control flow.
	(remove_dead_stmts): No need for dominance info.
	(remove_dead_stmt): Abort if trying to delete a control flow stmt. Remove
	basic_block parameter.
	(remopve_conditional): Remove.


Index: tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dce.c,v
retrieving revision 1.1.2.52
diff -c -p -r1.1.2.52 tree-ssa-dce.c
*** tree-ssa-dce.c	8 Aug 2003 00:27:10 -0000	1.1.2.52
--- tree-ssa-dce.c	29 Aug 2003 20:15:01 -0000
*************** static FILE *dump_file;
*** 69,76 ****
  static int dump_flags;
  
  static varray_type worklist;
- static dominance_info dom_info = NULL;
- static dominance_info pdom_info = NULL;
  
  static struct stmt_stats
  {
--- 69,74 ----
*************** static htab_t needed_stmts;
*** 84,90 ****
  
  /* Forward function prototypes.  */
  static bool necessary_p (tree);
- static int mark_tree_necessary (tree);
  static void mark_necessary (tree);
  static void print_stats (void);
  static bool need_to_preserve_store (tree);
--- 82,87 ----
*************** static void find_useful_stmts (void);
*** 92,100 ****
  static bool stmt_useful_p (tree);
  static void process_worklist (void);
  static void remove_dead_stmts (void);
! static void remove_dead_stmt (block_stmt_iterator *, basic_block);
  static void remove_dead_phis (basic_block);
- static void remove_conditional (basic_block);
  
  
  /* Is a tree necessary?  */
--- 89,96 ----
  static bool stmt_useful_p (tree);
  static void process_worklist (void);
  static void remove_dead_stmts (void);
! static void remove_dead_stmt (block_stmt_iterator *);
  static void remove_dead_phis (basic_block);
  
  
  /* Is a tree necessary?  */
*************** necessary_p (tree t)
*** 106,122 ****
  }
  
  
! /* Mark a tree as necessary.  Return 1 if it was not already marked.  */
  
! static int
! mark_tree_necessary (tree t)
  {
    void **slot;
  
    if (t == NULL
        || t == error_mark_node
        || necessary_p (t))
!     return 0;
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
--- 102,118 ----
  }
  
  
! /* Mark a tree as necessary.  */
  
! static void
! mark_necessary (tree t)
  {
    void **slot;
  
    if (t == NULL
        || t == error_mark_node
        || necessary_p (t))
!     return;
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
*************** mark_tree_necessary (tree t)
*** 128,156 ****
    slot = htab_find_slot (needed_stmts, t, INSERT);
    *slot = (void *) t;
    VARRAY_PUSH_TREE (worklist, t);
- 
-   return 1;
- }
- 
- 
- /* Mark a tree as necessary, and mark it's control parents as well.  */
- 
- static void
- mark_necessary (tree t)
- {
-   if (mark_tree_necessary (t))
-     {
-       /* Mark control parent statements as necessary.  */
-       tree parent = parent_stmt (t);
-       while (parent)
- 	{
- 	  mark_tree_necessary (parent);
- 	  parent = parent_stmt (parent);
- 	}
-     }
  }
  
- 
  /* Print out removed statement statistics.  */
  
  static void
--- 124,131 ----
*************** stmt_useful_p (tree stmt)
*** 262,281 ****
        || (TREE_CODE (stmt) == CATCH_EXPR))
      return true;
  
!   /* GOTO_EXPR nodes to nonlocal labels need to be kept (This fixes
!      gcc.c-torture/execute/920501-7.c and others that have nested functions
!      with nonlocal gotos).  FIXME: If we were doing IPA we could determine
!      if the label is actually reachable.  */
!   if (TREE_CODE (stmt) == GOTO_EXPR)
!     {
!       edge e;
!       basic_block bb = bb_for_stmt (stmt);
! 
!       if (bb)
! 	for (e = bb->succ; e; e = e->succ_next)
! 	  if (e->dest == EXIT_BLOCK_PTR && e->flags & EDGE_ABNORMAL)
! 	    return true;
!     }
  
    /* Examine all the stores in this statement.  */
    get_stmt_operands (stmt);
--- 237,244 ----
        || (TREE_CODE (stmt) == CATCH_EXPR))
      return true;
  
!   if (is_ctrl_stmt (stmt) || is_ctrl_altering_stmt (stmt))
!     return true;
  
    /* Examine all the stores in this statement.  */
    get_stmt_operands (stmt);
*************** static void
*** 306,317 ****
  process_worklist (void)
  {
    basic_block bb;
!   tree i, j;
!   edge e;
!   bitmap cond_checked, goto_checked;
! 
!   cond_checked = BITMAP_XMALLOC ();
!   goto_checked = BITMAP_XMALLOC ();
  
    while (VARRAY_ACTIVE_SIZE (worklist) > 0)
      {
--- 269,275 ----
  process_worklist (void)
  {
    basic_block bb;
!   tree i;
  
    while (VARRAY_ACTIVE_SIZE (worklist) > 0)
      {
*************** process_worklist (void)
*** 330,349 ****
  	 as necessary since it is control flow.  A block's predecessors only
  	 need to be checked once.  */
        bb = bb_for_stmt (i);
-       if (bb && !bitmap_bit_p (goto_checked, bb->index))
-         {
- 	  bitmap_set_bit (goto_checked, bb->index);
- 	  for (e = bb->pred; e != NULL; e = e->pred_next)
- 	    {
- 	      basic_block p = e->src;
- 	      if (p == ENTRY_BLOCK_PTR)
- 		continue;
- 	      j = last_stmt (p);
- 	      if ((e->flags & EDGE_ABNORMAL)
- 		  || (j && TREE_CODE (j) == GOTO_EXPR))
- 		mark_necessary (j);
- 	    }
- 	}
        
        if (TREE_CODE (i) == PHI_NODE)
  	{
--- 288,293 ----
*************** process_worklist (void)
*** 357,392 ****
  	      if (TREE_CODE (arg) == SSA_NAME)
  		mark_necessary (SSA_NAME_DEF_STMT (PHI_ARG_DEF (i, k)));
  	    }
- 
- 	  /* Look at all the predecessors, and if this PHI is being fed
- 	     from a conditional expression, mark that conditional
- 	     as necessary.   Copies may be needed on an edge later. 
- 	     This only needs to be done once per block.  */
- 
- 	  k = bb_for_stmt (i)->index;
- 	  if (!bitmap_bit_p (cond_checked, k))
- 	    {
- 	      bitmap_set_bit (cond_checked, k);
- 	      for (e = bb->pred; e; e = e->pred_next)
- 		{
- 		  basic_block pred, par;
- 		  pred = e->src;
- 		  if (pred != ENTRY_BLOCK_PTR)
- 		    {
- 		      par = parent_block (pred);
- 		      if (par)
- 			{
- 			  tree last;
- 			  last = last_stmt (par);
- 			  if (last && (TREE_CODE (last) == COND_EXPR
- 				       || TREE_CODE (last) == SWITCH_EXPR))
- 			    {
- 			      mark_necessary (last);
- 			    }
- 			}
- 		    }
- 		}
- 	    }
  	}
        else
  	{
--- 301,306 ----
*************** process_worklist (void)
*** 423,430 ****
  	    }
  	}
      }
-   BITMAP_XFREE (cond_checked);
-   BITMAP_XFREE (goto_checked);
  }
  
  
--- 337,342 ----
*************** remove_dead_stmts (void)
*** 438,446 ****
    tree t;
    block_stmt_iterator i;
  
-   dom_info = NULL;
-   pdom_info = NULL;
- 
    FOR_EACH_BB_REVERSE (bb)
      {
        bsi_list_p stack;
--- 350,355 ----
*************** remove_dead_stmts (void)
*** 455,470 ****
  
  	  /* If `i' is not in `necessary' then remove from B.  */
  	  if (!necessary_p (t))
! 	    remove_dead_stmt (&i, bb);
  	}
      }
- 
-   /* If we needed the dominance info, free it now.  */
-   if (dom_info != NULL)
-     free_dominance_info (dom_info);
- 
-   if (pdom_info != NULL)
-     free_dominance_info (pdom_info);
  }
  
  
--- 364,372 ----
  
  	  /* If `i' is not in `necessary' then remove from B.  */
  	  if (!necessary_p (t))
! 	    remove_dead_stmt (&i);
  	}
      }
  }
  
  
*************** remove_dead_phis (basic_block bb)
*** 508,514 ****
  /* Remove dead statement pointed by iterator I from block BB.  */
  
  static void
! remove_dead_stmt (block_stmt_iterator *i, basic_block bb)
  {
    tree t;
  
--- 410,416 ----
  /* Remove dead statement pointed by iterator I from block BB.  */
  
  static void
! remove_dead_stmt (block_stmt_iterator *i)
  {
    tree t;
  
*************** remove_dead_stmt (block_stmt_iterator *i
*** 529,546 ****
       post-dominator.  The flow graph will remove the blocks we are
       circumventing, and this block will then simply fall-thru to the
       post-dominator.  This prevents us from having to add any branch
!      instuctions to replace the conditional statement.
! 
!      Only remove a conditional if its parent statement is live.  This avoids
!      unnecessary calls to remove_conditional in the event of dead nested 
!      conditionals.  */
  
!   if (TREE_CODE (t) == COND_EXPR || TREE_CODE (t) == SWITCH_EXPR)
!     {
!       tree parent = parent_stmt (t);
!       if (parent == NULL_TREE || necessary_p (parent))
! 	remove_conditional (bb);
!     }
  
    bsi_remove (i);
  }
--- 431,442 ----
       post-dominator.  The flow graph will remove the blocks we are
       circumventing, and this block will then simply fall-thru to the
       post-dominator.  This prevents us from having to add any branch
!      instuctions to replace the conditional statement.  */
  
! #ifdef ENABLE_CHECKING
!   if (is_ctrl_stmt (t) || is_ctrl_altering_stmt (t))
!     abort ();
! #endif
  
    bsi_remove (i);
  }
*************** tree_ssa_dce (tree fndecl)
*** 591,651 ****
    htab_delete (needed_stmts);
  
    timevar_pop (TV_TREE_DCE);
- }
- 
- 
- /* Remove the conditional statement starting at block BB.  */
- 
- static void
- remove_conditional (basic_block bb)
- {
-   basic_block pdom_bb;
-   edge e;
- 
-   /* Calculate dominance info, if it hasn't been computed yet.  */
-   if (pdom_info == NULL)
-     pdom_info = calculate_dominance_info (CDI_POST_DOMINATORS);
- 
-   if (dom_info == NULL)
-     dom_info = calculate_dominance_info (CDI_DOMINATORS);
- 
-   pdom_bb = get_immediate_dominator (pdom_info, bb);
- 
-   /* Remove all outgoing edges.  */
-   for (e = bb->succ; e; )
-     {
-       edge tmp = e->succ_next;
-       /* If the edge BB->PDO_BB exists already, don't remove it.  */
-       if (e->dest != pdom_bb)
- 	ssa_remove_edge (e);
-       e = tmp;
-     }
- 
-   /* If we haven't removed all the edges, there is no need to update the
-      PHI nodes at PDOM_BB because all the superfluous arguments have been
-      removed by ssa_remove_edge and we don't need any new arguments.  */
-   if (bb->succ)
-     return;
- 
-   /* If there is no post dominator, then this block is going to the
-      exit node.  */
-   if (pdom_bb == NULL)
-     pdom_bb = EXIT_BLOCK_PTR;
- 
-   /* If the post dominator has any PHI nodes in it at all, the 
-      conditional has been marked as necessary. This means no PHI
-      node updating is required. If there are any PHI nodes, its a bug
-      in DCE.  */
- 
- #ifdef ENABLE_CHECKING
-   {
-     tree phi;
-     for (phi = phi_nodes (pdom_bb); phi; phi = TREE_CHAIN (phi))
-       if (necessary_p (phi))
-         abort ();
-   }
- #endif
- 
-   /* Add an edge to BB's post dominator.  */
-   make_edge (bb, pdom_bb,  EDGE_FALLTHRU);
  }
--- 487,490 ----