[patch] Make cfg cleanup more loop-friendly

[patch] Make cfg cleanup more loop-friendly

[Zdenek Dvorak]

Hello,

this patch introduces two changes that make cfg cleanup behave nicer
with respect to loops:

1) It makes cleanup_tree_cfg detect automatically whether loop
   information needs to be updated (so it is not neccessary to
   use cleanup_tree_cfg_loop).
2) Adds a new flag to loops' state (LOOPS_NEED_FIXUP) to indicate that
   the structure of the loops may need fixing:  In some cases, jump
   threading will damage structure of the loops (move some blocks out
   of the loops, etc.), so we want fix_loop_structure to be run.
   However, it may happen that cfg cleanup will not change
   anything, in which case we currently assume that the information
   about loops is correct and do not run fix_loop_structure.  With the patch
   we base the decision on the presence of LOOPS_NEED_FIXUP flag.
   For now we set this flag whenever anything is changed in jump threading
   or cfg cleanup, but later we may want to only set it in cases
   when we know that the loops may be affected by some transformation.

Bootstrapped & regtested on i686.

Zdenek

	* tree-ssa-threadupdate.c (thread_through_all_blocks): Record that
	the loop structures may need fixing.
	* tree-cfgcleanup.c (cleanup_tree_cfg_noloop, repair_loop_structures):
	New functions.
	(cleanup_tree_cfg_loop): Removed.
	(cleanup_tree_cfg): If loops need fixing, call repair_loop_structures.
	* tree-predcom.c (tree_predictive_commoning): Return TODO_cleanup_cfg
	instead of running cleanup_tree_cfg_loop.
	* cfgloop.h (LOOPS_NEED_FIXUP): New constant.
	* tree-flow.h (cleanup_tree_cfg_loop): Declaration removed.
	(tree_predictive_commoning): Declaration changed.
	* passes.c (execute_function_todo): Do not use cleanup_tree_cfg_loop.

Index: tree-ssa-threadupdate.c
===================================================================
*** tree-ssa-threadupdate.c	(revision 126869)
--- tree-ssa-threadupdate.c	(working copy)
*************** thread_through_all_blocks (bool may_peel
*** 1076,1081 ****
--- 1076,1084 ----
    VEC_free (edge, heap, threaded_edges);
    threaded_edges = NULL;
  
+   if (retval)
+     current_loops->state |= LOOPS_NEED_FIXUP;
+ 
    return retval;
  }
  
Index: tree-cfgcleanup.c
===================================================================
*** tree-cfgcleanup.c	(revision 126869)
--- tree-cfgcleanup.c	(working copy)
*************** cleanup_tree_cfg_1 (void)
*** 593,604 ****
    return retval;
  }
  
 
  /* Remove unreachable blocks and other miscellaneous clean up work.
     Return true if the flowgraph was modified, false otherwise.  */
  
! bool
! cleanup_tree_cfg (void)
  {
    bool changed;
  
--- 593,604 ----
    return retval;
  }


  /* Remove unreachable blocks and other miscellaneous clean up work.
     Return true if the flowgraph was modified, false otherwise.  */
  
! static bool
! cleanup_tree_cfg_noloop (void)
  {
    bool changed;
  
*************** cleanup_tree_cfg (void)
*** 633,666 ****
  
    timevar_pop (TV_TREE_CLEANUP_CFG);
  
    return changed;
  }
  
! /* Cleanup cfg and repair loop structures.  */
  
! bool
! cleanup_tree_cfg_loop (void)
  {
!   bool changed = cleanup_tree_cfg ();
  
!   if (changed && current_loops != NULL)
!     {
!       bitmap changed_bbs = BITMAP_ALLOC (NULL);
!       fix_loop_structure (changed_bbs);
  
!       /* This usually does nothing.  But sometimes parts of cfg that originally
! 	 were inside a loop get out of it due to edge removal (since they
! 	 become unreachable by back edges from latch).  */
!       if ((current_loops->state & LOOP_CLOSED_SSA) != 0)
! 	rewrite_into_loop_closed_ssa (changed_bbs, TODO_update_ssa);
! 
!       BITMAP_FREE (changed_bbs);
  
  #ifdef ENABLE_CHECKING
!       verify_loop_structure ();
  #endif
!       scev_reset ();
!     }
    return changed;
  }
  
--- 632,678 ----
  
    timevar_pop (TV_TREE_CLEANUP_CFG);
  
+   if (changed && current_loops)
+     current_loops->state |= LOOPS_NEED_FIXUP;
+ 
    return changed;
  }
  
! /* Repairs loop structures.  */
  
! static void
! repair_loop_structures (void)
  {
!   bitmap changed_bbs = BITMAP_ALLOC (NULL);
!   fix_loop_structure (changed_bbs);
  
!   /* This usually does nothing.  But sometimes parts of cfg that originally
!      were inside a loop get out of it due to edge removal (since they
!      become unreachable by back edges from latch).  */
!   if ((current_loops->state & LOOP_CLOSED_SSA) != 0)
!     rewrite_into_loop_closed_ssa (changed_bbs, TODO_update_ssa);
  
!   BITMAP_FREE (changed_bbs);
  
  #ifdef ENABLE_CHECKING
!   verify_loop_structure ();
  #endif
!   scev_reset ();
! 
!   current_loops->state &= ~LOOPS_NEED_FIXUP;
! }
! 
! /* Cleanup cfg and repair loop structures.  */
! 
! bool
! cleanup_tree_cfg (void)
! {
!   bool changed = cleanup_tree_cfg_noloop ();
! 
!   if (current_loops != NULL
!       && (current_loops->state & LOOPS_NEED_FIXUP))
!     repair_loop_structures ();
! 
    return changed;
  }
  
Index: tree-predcom.c
===================================================================
*** tree-predcom.c	(revision 126869)
--- tree-predcom.c	(working copy)
*************** end: ;
*** 2583,2594 ****
  
  /* Runs predictive commoning.  */
  
! void
  tree_predictive_commoning (void)
  {
    bool unrolled = false;
    struct loop *loop;
    loop_iterator li;
  
    initialize_original_copy_tables ();
    FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
--- 2583,2595 ----
  
  /* Runs predictive commoning.  */
  
! unsigned
  tree_predictive_commoning (void)
  {
    bool unrolled = false;
    struct loop *loop;
    loop_iterator li;
+   unsigned ret = 0;
  
    initialize_original_copy_tables ();
    FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
*************** tree_predictive_commoning (void)
*** 2599,2605 ****
    if (unrolled)
      {
        scev_reset ();
!       cleanup_tree_cfg_loop ();
      }
    free_original_copy_tables ();
  }
--- 2600,2608 ----
    if (unrolled)
      {
        scev_reset ();
!       ret = TODO_cleanup_cfg;
      }
    free_original_copy_tables ();
+ 
+   return ret;
  }
Index: cfgloop.h
===================================================================
*** cfgloop.h	(revision 126869)
--- cfgloop.h	(working copy)
*************** enum
*** 171,177 ****
    LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4,
    LOOPS_HAVE_RECORDED_EXITS = 8,
    LOOPS_MAY_HAVE_MULTIPLE_LATCHES = 16,
!   LOOP_CLOSED_SSA = 32
  };
  
  #define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \
--- 171,178 ----
    LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4,
    LOOPS_HAVE_RECORDED_EXITS = 8,
    LOOPS_MAY_HAVE_MULTIPLE_LATCHES = 16,
!   LOOP_CLOSED_SSA = 32,
!   LOOPS_NEED_FIXUP = 64
  };
  
  #define LOOPS_NORMAL (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \
Index: tree-flow.h
===================================================================
*** tree-flow.h	(revision 126869)
--- tree-flow.h	(working copy)
*************** void remove_edge_and_dominated_blocks (e
*** 782,788 ****
  /* In tree-cfgcleanup.c  */
  extern bitmap cfgcleanup_altered_bbs;
  extern bool cleanup_tree_cfg (void);
- extern bool cleanup_tree_cfg_loop (void);
  
  /* In tree-pretty-print.c.  */
  extern void dump_generic_bb (FILE *, basic_block, int, int);
--- 782,787 ----
*************** unsigned int tree_unroll_loops_completel
*** 974,980 ****
  unsigned int tree_ssa_prefetch_arrays (void);
  unsigned int remove_empty_loops (void);
  void tree_ssa_iv_optimize (void);
! void tree_predictive_commoning (void);
  
  bool number_of_iterations_exit (struct loop *, edge,
  				struct tree_niter_desc *niter, bool);
--- 973,979 ----
  unsigned int tree_ssa_prefetch_arrays (void);
  unsigned int remove_empty_loops (void);
  void tree_ssa_iv_optimize (void);
! unsigned tree_predictive_commoning (void);
  
  bool number_of_iterations_exit (struct loop *, edge,
  				struct tree_niter_desc *niter, bool);
Index: passes.c
===================================================================
*** passes.c	(revision 126869)
--- passes.c	(working copy)
*************** execute_function_todo (void *data)
*** 892,903 ****
    /* Always cleanup the CFG before trying to update SSA.  */
    if (flags & TODO_cleanup_cfg)
      {
!       bool cleanup;
! 
!       if (current_loops)
! 	cleanup = cleanup_tree_cfg_loop ();
!       else
! 	cleanup = cleanup_tree_cfg ();
  
        if (cleanup && (cfun->curr_properties & PROP_ssa))
  	flags |= TODO_remove_unused_locals;
--- 892,898 ----
    /* Always cleanup the CFG before trying to update SSA.  */
    if (flags & TODO_cleanup_cfg)
      {
!       bool cleanup = cleanup_tree_cfg ();
  
        if (cleanup && (cfun->curr_properties & PROP_ssa))
  	flags |= TODO_remove_unused_locals;

Re: [patch] Make cfg cleanup more loop-friendly

[Diego Novillo]

On 7/25/07 7:42 PM, Zdenek Dvorak wrote:

> 	* tree-ssa-threadupdate.c (thread_through_all_blocks): Record that
> 	the loop structures may need fixing.
> 	* tree-cfgcleanup.c (cleanup_tree_cfg_noloop, repair_loop_structures):
> 	New functions.
> 	(cleanup_tree_cfg_loop): Removed.
> 	(cleanup_tree_cfg): If loops need fixing, call repair_loop_structures.
> 	* tree-predcom.c (tree_predictive_commoning): Return TODO_cleanup_cfg
> 	instead of running cleanup_tree_cfg_loop.
> 	* cfgloop.h (LOOPS_NEED_FIXUP): New constant.
> 	* tree-flow.h (cleanup_tree_cfg_loop): Declaration removed.
> 	(tree_predictive_commoning): Declaration changed.
> 	* passes.c (execute_function_todo): Do not use cleanup_tree_cfg_loop.
> 

> +   if (retval)
> +     current_loops->state |= LOOPS_NEED_FIXUP;

Minor cleanup nit, could you hide this state manipulation behind an API?
 Not for this patch, but maybe for some future cleanup.  Instead of
allowing direct access to the loop fields, we could have something like
'mark_loops_for_fixup (current_loops)'.


The rest is OK.