Re: Allow CD-DCE to remove (finite) empty loops

[Richard Guenther <rguenther at suse dot de>]

On Fri, 3 Jul 2009, Jan Hubicka wrote:

> Hi
> this patch removes empty loop removal pass and adds corresponding logic to
> cd-dce.  The motivation is that cd-dce is less restricted that empty loop
> removal (i.e. it can handle empty loops with multiple exits, nested empty loops
> or loops only controlling number of iterations of other empty loop) and that we
> can do this during early optimizations avoiding some confussion of inliner
> metrics on code using pooma. (yes, tramo3d ;)
> 
> I looked for cases where empty loop removal pass still matches, there 
> are 3 in bootstrap, all of them because of loop that has 
> __builtin_expect in exit conditoin.  Before inlining we don't estimate 
> number of iterations since we scalar evolution code does not see through 
> __builtin_expect, while after inlining we remove the hint and get count 
> right. The loops are removed by later cddce pass, so code quality is 
> same.

Can you open a bugreport for this?  I think SCEV should look through
__builtin_expect.

> While patch removes a pass, it is not compile time improvement per se, since
> initialization/deinitialization of SCEV is more expnesive that trivial pass
> through already initialized datastructures. However I tried to benchmark it on
> tramp3d and on GCC modules and didn't measured any off-noise difference.
> 
> The patch also adds hunk removing phi nodes Richard requested to be removed from
> previous patch.  Now the following testcase ICE without testsuite/gcc.c-torture/compile/921011-2.c:
> 
> extern int foobar1 ();
> 
> typedef struct
>   {
>     unsigned long colormap;
>     unsigned long red_max;
>     unsigned long red_mult;
>     unsigned long green_max;
>     unsigned long green_mult;
>     unsigned long blue_max;
>     unsigned long blue_mult;
>     unsigned long base_pixel;
>     unsigned long visualid;
>     unsigned long killid;
>   }
> frotz;
> 
> int
> foobar (stdcmap, count)
>      frotz **stdcmap;
>      int *count;
> {
>   register int i;
>   frotz *data = ((void *) 0);
> 
>   unsigned long nitems;
>   int ncmaps;
>   int old_style = 0;
>   unsigned long def_visual = 0L;
>   frotz *cmaps;
> 
> 
>   if ( foobar1 (&data) != 0)
>     return 0;
>   if (nitems < 10)
>     {
>       ncmaps = 1;
>       if (nitems < 9)
> 	{
> 	}
>     }
>   else
>     ncmaps = (nitems / 10);
> 
>   {
>     register frotz *map;
>     register frotz *prop;
> 
>     for (i = ncmaps, map = cmaps, prop = data; i > 0; i--, map++, prop++)
>       {
> 	map->colormap = prop->colormap;
> 	map->red_max = prop->red_max;
> 	map->red_mult = prop->red_mult;
> 	map->green_max = prop->green_max;
> 	map->green_mult = prop->green_mult;
> 	map->blue_max = prop->blue_max;
> 	map->blue_mult = prop->blue_mult;
> 	map->base_pixel = prop->base_pixel;
> 	map->visualid = (def_visual ? def_visual : prop->visualid);
> 	map->killid = (old_style ? 0L : prop->killid);
>       }
>   }
>   *stdcmap = cmaps;
>   *count = ncmaps;
> }
> 
> Bootstrapped/regtested x86_64-linux, OK?

Ok.

Thanks,
Richard.

> 2009-07-03  Jan Hubicka  <jh@suse.cz>
> 	* tree-ssa-loop-iv-canon.c (empty_loop_p, remove_empty_loop,
> 	try_remove_empty_loop, remove_empty_loops): Remove.
> 	* tree-ssa-loop.c (tree_ssa_empty_loop, pass_empty_loop): Remove.
> 	* tree-ssa-dce.c (find_obviously_necessary_stmts): Use finiteness info
> 	to mark regular loops as neccesary.
> 	(eliminate_unnecessary_stmts): Take care to remove uses of results of
> 	virtual PHI nodes that became unreachable.
> 	(perform_tree_ssa_dce): Initialize/deinitialize loop optimizer.
> 	* tree-flow.h (remove_empty_loops): Remove.
> 	* passes.c (init_optimization_passes): Remove.
> Index: tree-ssa-loop-ivcanon.c
> ===================================================================
> *** tree-ssa-loop-ivcanon.c	(revision 149199)
> --- tree-ssa-loop-ivcanon.c	(working copy)
> *************** tree_unroll_loops_completely (bool may_i
> *** 558,744 ****
>   
>     return 0;
>   }
> - 
> - /* Checks whether LOOP is empty.  */
> - 
> - static bool
> - empty_loop_p (struct loop *loop)
> - {
> -   edge exit;
> -   basic_block *body;
> -   gimple_stmt_iterator gsi;
> -   unsigned i;
> - 
> -   /* If the loop has multiple exits, it is too hard for us to handle.
> -      Similarly, if the exit is not dominating, we cannot determine
> -      whether the loop is not infinite.  */
> -   exit = single_dom_exit (loop);
> -   if (!exit)
> -     return false;
> - 
> -   /* The loop must be finite.  */
> -   if (!finite_loop_p (loop))
> -     return false;
> - 
> -   /* Values of all loop exit phi nodes must be invariants.  */
> -   for (gsi = gsi_start(phi_nodes (exit->dest)); !gsi_end_p (gsi); gsi_next (&gsi))
> -     {
> -       gimple phi = gsi_stmt (gsi);
> -       tree def;
> - 
> -       if (!is_gimple_reg (PHI_RESULT (phi)))
> - 	continue;
> - 
> -       def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
> - 
> -       if (!expr_invariant_in_loop_p (loop, def))
> - 	return false;
> -     }
> - 
> -   /* And there should be no memory modifying or from other reasons
> -      unremovable statements.  */
> -   body = get_loop_body (loop);
> -   for (i = 0; i < loop->num_nodes; i++)
> -     {
> -       /* Irreducible region might be infinite.  */
> -       if (body[i]->flags & BB_IRREDUCIBLE_LOOP)
> - 	{
> - 	  free (body);
> - 	  return false;
> - 	}
> - 	
> -       for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
> - 	{
> - 	  gimple stmt = gsi_stmt (gsi);
> - 
> - 	  if (gimple_vdef (stmt)
> - 	      || gimple_has_volatile_ops (stmt))
> - 	    {
> - 	      free (body);
> - 	      return false;
> - 	    }
> - 
> - 	  /* Also, asm statements and calls may have side effects and we
> - 	     cannot change the number of times they are executed.  */
> - 	  switch (gimple_code (stmt))
> - 	    {
> - 	    case GIMPLE_CALL:
> - 	      if (gimple_has_side_effects (stmt))
> - 		{
> - 		  free (body);
> - 		  return false;
> - 		}
> - 	      break;
> - 
> - 	    case GIMPLE_ASM:
> - 	      /* We cannot remove volatile assembler.  */
> - 	      if (gimple_asm_volatile_p (stmt))
> - 		{
> - 		  free (body);
> - 		  return false;
> - 		}
> - 	      break;
> - 
> - 	    default:
> - 	      break;
> - 	    }
> - 	}
> -       }
> -   free (body);
> - 
> -   return true;
> - }
> - 
> - /* Remove LOOP by making it exit in the first iteration.  */
> - 
> - static void
> - remove_empty_loop (struct loop *loop)
> - {
> -   edge exit = single_dom_exit (loop), non_exit;
> -   gimple cond_stmt = last_stmt (exit->src);
> -   basic_block *body;
> -   unsigned n_before, freq_in, freq_h;
> -   gcov_type exit_count = exit->count;
> - 
> -   if (dump_file)
> -     fprintf (dump_file, "Removing empty loop %d\n", loop->num);
> - 
> -   non_exit = EDGE_SUCC (exit->src, 0);
> -   if (non_exit == exit)
> -     non_exit = EDGE_SUCC (exit->src, 1);
> - 
> -   if (exit->flags & EDGE_TRUE_VALUE)
> -     gimple_cond_make_true (cond_stmt);
> -   else
> -     gimple_cond_make_false (cond_stmt);
> -   update_stmt (cond_stmt);
> - 
> -   /* Let us set the probabilities of the edges coming from the exit block.  */
> -   exit->probability = REG_BR_PROB_BASE;
> -   non_exit->probability = 0;
> -   non_exit->count = 0;
> - 
> -   /* Update frequencies and counts.  Everything before
> -      the exit needs to be scaled FREQ_IN/FREQ_H times,
> -      where FREQ_IN is the frequency of the entry edge
> -      and FREQ_H is the frequency of the loop header.
> -      Everything after the exit has zero frequency.  */
> -   freq_h = loop->header->frequency;
> -   freq_in = EDGE_FREQUENCY (loop_preheader_edge (loop));
> -   if (freq_h != 0)
> -     {
> -       body = get_loop_body_in_dom_order (loop);
> -       for (n_before = 1; n_before <= loop->num_nodes; n_before++)
> - 	if (body[n_before - 1] == exit->src)
> - 	  break;
> -       scale_bbs_frequencies_int (body, n_before, freq_in, freq_h);
> -       scale_bbs_frequencies_int (body + n_before, loop->num_nodes - n_before,
> - 				 0, 1);
> -       free (body);
> -     }
> - 
> -   /* Number of executions of exit is not changed, thus we need to restore
> -      the original value.  */
> -   exit->count = exit_count;
> - }
> - 
> - /* Removes LOOP if it is empty.  Returns true if LOOP is removed.  CHANGED
> -    is set to true if LOOP or any of its subloops is removed.  */
> - 
> - static bool
> - try_remove_empty_loop (struct loop *loop, bool *changed)
> - {
> -   bool nonempty_subloop = false;
> -   struct loop *sub;
> - 
> -   /* First, all subloops must be removed.  */
> -   for (sub = loop->inner; sub; sub = sub->next)
> -     nonempty_subloop |= !try_remove_empty_loop (sub, changed);
> - 
> -   if (nonempty_subloop || !empty_loop_p (loop))
> -     return false;
> - 
> -   remove_empty_loop (loop);
> -   *changed = true;
> -   return true;
> - }
> - 
> - /* Remove the empty loops.  */
> - 
> - unsigned int
> - remove_empty_loops (void)
> - {
> -   bool changed = false;
> -   struct loop *loop;
> - 
> -   for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
> -     try_remove_empty_loop (loop, &changed);
> - 
> -   if (changed)
> -     {
> -       scev_reset ();
> -       return TODO_cleanup_cfg;
> -     }
> -   return 0;
> - }
> - 
> --- 558,560 ----
> Index: tree-ssa-loop.c
> ===================================================================
> *** tree-ssa-loop.c	(revision 149199)
> --- tree-ssa-loop.c	(working copy)
> *************** struct gimple_opt_pass pass_scev_cprop =
> *** 433,469 ****
>    }
>   };
>   
> - /* Remove empty loops.  */
> - 
> - static unsigned int
> - tree_ssa_empty_loop (void)
> - {
> -   if (number_of_loops () <= 1)
> -     return 0;
> - 
> -   return remove_empty_loops ();
> - }
> - 
> - struct gimple_opt_pass pass_empty_loop =
> - {
> -  {
> -   GIMPLE_PASS,
> -   "empty",				/* name */
> -   NULL,					/* gate */
> -   tree_ssa_empty_loop,		       	/* execute */
> -   NULL,					/* sub */
> -   NULL,					/* next */
> -   0,					/* static_pass_number */
> -   TV_COMPLETE_UNROLL,	  		/* tv_id */
> -   PROP_cfg | PROP_ssa,			/* properties_required */
> -   0,					/* properties_provided */
> -   0,					/* properties_destroyed */
> -   0,					/* todo_flags_start */
> -   TODO_dump_func | TODO_verify_loops 
> -     | TODO_ggc_collect			/* todo_flags_finish */
> -  }
> - };
> - 
>   /* Record bounds on numbers of iterations of loops.  */
>   
>   static unsigned int
> --- 433,438 ----
> Index: tree-ssa-dce.c
> ===================================================================
> *** tree-ssa-dce.c	(revision 149199)
> --- tree-ssa-dce.c	(working copy)
> *************** find_obviously_necessary_stmts (struct e
> *** 434,450 ****
>   	}
>       }
>   
>     if (el)
>       {
> !       /* Prevent the loops from being removed.  We must keep the infinite loops,
> ! 	 and we currently do not have a means to recognize the finite ones.  */
> !       FOR_EACH_BB (bb)
> ! 	{
> ! 	  edge_iterator ei;
> ! 	  FOR_EACH_EDGE (e, ei, bb->succs)
> ! 	    if (e->flags & EDGE_DFS_BACK)
> ! 	      mark_control_dependent_edges_necessary (e->dest, el);
> ! 	}
>       }
>   }
>   
> --- 434,475 ----
>   	}
>       }
>   
> +   /* Pure and const functions are finite and thus have no infinite loops in
> +      them.  */
> +   if ((TREE_READONLY (current_function_decl)
> +        || DECL_PURE_P (current_function_decl))
> +       && !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl))
> +     return;
> + 
> +   /* Prevent the empty possibly infinite loops from being removed.  */
>     if (el)
>       {
> !       loop_iterator li;
> !       struct loop *loop;
> !       scev_initialize ();
> !       if (mark_irreducible_loops ())
> ! 	FOR_EACH_BB (bb)
> ! 	  {
> ! 	    edge_iterator ei;
> ! 	    FOR_EACH_EDGE (e, ei, bb->succs)
> ! 	      if ((e->flags & EDGE_DFS_BACK)
> ! 		  && (e->flags & EDGE_IRREDUCIBLE_LOOP))
> ! 		{
> ! 	          if (dump_file)
> ! 	            fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n",
> ! 		    	     e->src->index, e->dest->index);
> ! 		  mark_control_dependent_edges_necessary (e->dest, el);
> ! 		}
> ! 	  }
> ! 
> !       FOR_EACH_LOOP (li, loop, 0)
> ! 	if (!finite_loop_p (loop))
> ! 	  {
> ! 	    if (dump_file)
> ! 	      fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num);
> ! 	    mark_control_dependent_edges_necessary (loop->latch, el);
> ! 	  }
> !       scev_finalize ();
>       }
>   }
>   
> *************** eliminate_unnecessary_stmts (void)
> *** 1094,1100 ****
>   	    }
>   	}
>       }
> ! 
>     FOR_EACH_BB (bb)
>       {
>         /* Remove dead PHI nodes.  */
> --- 1119,1160 ----
>   	    }
>   	}
>       }
> !   /* Since we don't track liveness of virtual PHI nodes, it is possible that we
> !      rendered some PHI nodes unreachable while they are still in use.
> !      Mark them for renaming.  */
> !   if (cfg_altered)
> !     {
> !       basic_block next_bb;
> !       find_unreachable_blocks ();
> !       for (bb = ENTRY_BLOCK_PTR->next_bb; bb != EXIT_BLOCK_PTR; bb = next_bb)
> ! 	{
> ! 	  next_bb = bb->next_bb;
> ! 	  if (!(bb->flags & BB_REACHABLE))
> ! 	    {
> ! 	      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> ! 		if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi))))
> ! 		  {
> ! 		    bool found = false;
> ! 		    imm_use_iterator iter;
> ! 
> ! 		    FOR_EACH_IMM_USE_STMT (stmt, iter, gimple_phi_result (gsi_stmt (gsi)))
> ! 		      {
> ! 			if (!(gimple_bb (stmt)->flags & BB_REACHABLE))
> ! 			  continue;
> ! 			if (gimple_code (stmt) == GIMPLE_PHI
> ! 			    || gimple_plf (stmt, STMT_NECESSARY))
> ! 			  {
> ! 			    found = true;
> ! 			    BREAK_FROM_IMM_USE_STMT (iter);
> ! 			  }
> ! 		      }
> ! 		    if (found)
> ! 		      mark_virtual_phi_result_for_renaming (gsi_stmt (gsi));
> ! 		  }
> ! 	      delete_basic_block (bb);
> ! 	    }
> ! 	}
> !     }
>     FOR_EACH_BB (bb)
>       {
>         /* Remove dead PHI nodes.  */
> *************** perform_tree_ssa_dce (bool aggressive)
> *** 1197,1202 ****
> --- 1257,1265 ----
>     struct edge_list *el = NULL;
>     bool something_changed = 0;
>   
> +   if (aggressive)
> +     loop_optimizer_init (LOOPS_HAVE_PREHEADERS);
> + 
>     tree_dce_init (aggressive);
>   
>     if (aggressive)
> *************** perform_tree_ssa_dce (bool aggressive)
> *** 1216,1221 ****
> --- 1279,1287 ----
>   
>     find_obviously_necessary_stmts (el);
>   
> +   if (aggressive)
> +     loop_optimizer_finalize ();
> + 
>     longest_chain = 0;
>     total_chain = 0;
>     chain_ovfl = false;
> Index: tree-flow.h
> ===================================================================
> *** tree-flow.h	(revision 149199)
> --- tree-flow.h	(working copy)
> *************** unsigned int tree_ssa_unswitch_loops (vo
> *** 745,751 ****
>   unsigned int canonicalize_induction_variables (void);
>   unsigned int tree_unroll_loops_completely (bool, bool);
>   unsigned int tree_ssa_prefetch_arrays (void);
> - unsigned int remove_empty_loops (void);
>   void tree_ssa_iv_optimize (void);
>   unsigned tree_predictive_commoning (void);
>   tree canonicalize_loop_ivs (struct loop *, htab_t, tree *);
> --- 745,750 ----
> Index: passes.c
> ===================================================================
> *** passes.c	(revision 149199)
> --- passes.c	(working copy)
> *************** init_optimization_passes (void)
> *** 651,657 ****
>   	  NEXT_PASS (pass_lim);
>   	  NEXT_PASS (pass_tree_unswitch);
>   	  NEXT_PASS (pass_scev_cprop);
> - 	  NEXT_PASS (pass_empty_loop);
>   	  NEXT_PASS (pass_record_bounds);
>   	  NEXT_PASS (pass_check_data_deps);
>   	  NEXT_PASS (pass_loop_distribution);
> --- 651,656 ----
> 
> 

-- 
Richard Guenther <rguenther@suse.de>
Novell / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 - GF: Markus Rex