pretty-ipa merge 18: function finiteness testing in ipa-pure-const.c

[Jan Hubicka <hubicka at ucw dot cz>]

Hi,
this patch makes ipa-pure-const to use finite_loop_p test to try to
prove that even function with looping CFG is pure/const.  This improves
noticeably analysis of STL headers and also improve measurably bootstrap
time on pretty-ipa despite fact that firing up SCEV is quite
non-trivial.  It happens quite rearely because we do it only if function
look pure/const otherwise, so the test ends up being quite cheap.

Patch makes even more difference on bootstrap time if loops are assumed
finite by default, I still need to analyze why.

THe code needs mark_irreducible_loops to return true if irreducible loop
was found.  Richi requirested not doing so by static variable, but
problem is that check_irred is called by for_each_edge that does not
allow other kind of communication.

Since for_each_edge is just two nested loops, it seems better to write
it by hand than use indirect call etc etc.

Bootstrapped/regtested x86_64-linux.
Honza

	* cfgloopanal.c (check_irred): Move into ..
	(mark_irreducible_loops): ... here; return true if ireducible
	loops was found.
	* ipa-pure-const.c: Include cfgloop.h and tree-scalar-evolution.h
	(analyze_function): Try to prove loop finiteness.
	* cfgloop.h (mark_irreducible_loops): Update prototype.
	* Makefile.in (ipa-pure-const.o): Add dependency on SCEV and CFGLOOP.
Index: cfgloopanal.c
===================================================================
*** cfgloopanal.c	(revision 147057)
--- cfgloopanal.c	(working copy)
*************** just_once_each_iteration_p (const struct
*** 52,77 ****
    return true;
  }
  
- /* Marks the edge E in graph G irreducible if it connects two vertices in the
-    same scc.  */
- 
- static void
- check_irred (struct graph *g, struct graph_edge *e)
- {
-   edge real = (edge) e->data;
- 
-   /* All edges should lead from a component with higher number to the
-      one with lower one.  */
-   gcc_assert (g->vertices[e->src].component >= g->vertices[e->dest].component);
- 
-   if (g->vertices[e->src].component != g->vertices[e->dest].component)
-     return;
- 
-   real->flags |= EDGE_IRREDUCIBLE_LOOP;
-   if (flow_bb_inside_loop_p (real->src->loop_father, real->dest))
-     real->src->flags |= BB_IRREDUCIBLE_LOOP;
- }
- 
  /* Marks blocks and edges that are part of non-recognized loops; i.e. we
     throw away all latch edges and mark blocks inside any remaining cycle.
     Everything is a bit complicated due to fact we do not want to do this
--- 52,57 ----
*************** check_irred (struct graph *g, struct gra
*** 84,93 ****
  #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block)
  #define BB_REPR(BB) ((BB)->index + 1)
  
! void
  mark_irreducible_loops (void)
  {
    basic_block act;
    edge e;
    edge_iterator ei;
    int src, dest;
--- 64,74 ----
  #define LOOP_REPR(LOOP) ((LOOP)->num + last_basic_block)
  #define BB_REPR(BB) ((BB)->index + 1)
  
! bool
  mark_irreducible_loops (void)
  {
    basic_block act;
+   struct graph_edge *ge;
    edge e;
    edge_iterator ei;
    int src, dest;
*************** mark_irreducible_loops (void)
*** 95,100 ****
--- 76,83 ----
    struct graph *g;
    int num = number_of_loops ();
    struct loop *cloop;
+   bool irred_loop_found = false;
+   int i;
  
    gcc_assert (current_loops != NULL);
  
*************** mark_irreducible_loops (void)
*** 154,164 ****
    graphds_scc (g, NULL);
  
    /* Mark the irreducible loops.  */
!   for_each_edge (g, check_irred);
  
    free_graph (g);
  
    loops_state_set (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
  }
  
  /* Counts number of insns inside LOOP.  */
--- 137,166 ----
    graphds_scc (g, NULL);
  
    /* Mark the irreducible loops.  */
!   for (i = 0; i < g->n_vertices; i++)
!     for (ge = g->vertices[i].succ; ge; ge = ge->succ_next)
!       {
! 	edge real = (edge) ge->data;
! 	/* edge E in graph G is irreducible if it connects two vertices in the
! 	   same scc.  */
! 
! 	/* All edges should lead from a component with higher number to the
! 	   one with lower one.  */
! 	gcc_assert (g->vertices[ge->src].component >= g->vertices[ge->dest].component);
! 
! 	if (g->vertices[ge->src].component != g->vertices[ge->dest].component)
! 	  continue;
! 
! 	real->flags |= EDGE_IRREDUCIBLE_LOOP;
! 	irred_loop_found = true;
! 	if (flow_bb_inside_loop_p (real->src->loop_father, real->dest))
! 	  real->src->flags |= BB_IRREDUCIBLE_LOOP;
!       }
  
    free_graph (g);
  
    loops_state_set (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
+   return irred_loop_found;
  }
  
  /* Counts number of insns inside LOOP.  */
Index: ipa-pure-const.c
===================================================================
*** ipa-pure-const.c	(revision 147057)
--- ipa-pure-const.c	(working copy)
*************** along with GCC; see the file COPYING3.  
*** 51,56 ****
--- 51,58 ----
  #include "diagnostic.h"
  #include "langhooks.h"
  #include "target.h"
+ #include "cfgloop.h"
+ #include "tree-scalar-evolution.h"
  
  static struct pointer_set_t *visited_nodes;
  
*************** end:
*** 522,529 ****
  	 indication of possible infinite loop side
  	 effect.  */
        if (mark_dfs_back_edges ())
! 	l->looping = true;
!       
      }
  
    if (TREE_READONLY (decl))
--- 524,556 ----
  	 indication of possible infinite loop side
  	 effect.  */
        if (mark_dfs_back_edges ())
!         {
! 	  loop_optimizer_init (LOOPS_HAVE_PREHEADERS);
! 	  if (dump_file && (dump_flags & TDF_DETAILS))
! 	    flow_loops_dump (dump_file, NULL, 0);
! 	  if (mark_irreducible_loops ())
! 	    {
! 	      if (dump_file)
! 	        fprintf (dump_file, "    has irreducible loops\n");
! 	      l->looping = true;
! 	    }
! 	  else 
! 	    {
! 	      loop_iterator li;
! 	      struct loop *loop;
! 	      scev_initialize ();
! 	      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);
! 		    l->looping =true;
! 		    break;
! 		  }
! 	      scev_finalize ();
! 	    }
!           loop_optimizer_finalize ();
! 	}
      }
  
    if (TREE_READONLY (decl))
Index: cfgloop.h
===================================================================
*** cfgloop.h	(revision 147057)
--- cfgloop.h	(working copy)
*************** struct loop *alloc_loop (void);
*** 205,211 ****
  extern void flow_loop_free (struct loop *);
  int flow_loop_nodes_find (basic_block, struct loop *);
  void fix_loop_structure (bitmap changed_bbs);
! void mark_irreducible_loops (void);
  void release_recorded_exits (void);
  void record_loop_exits (void);
  void rescan_loop_exit (edge, bool, bool);
--- 205,211 ----
  extern void flow_loop_free (struct loop *);
  int flow_loop_nodes_find (basic_block, struct loop *);
  void fix_loop_structure (bitmap changed_bbs);
! bool mark_irreducible_loops (void);
  void release_recorded_exits (void);
  void record_loop_exits (void);
  void rescan_loop_exit (edge, bool, bool);
Index: Makefile.in
===================================================================
*** Makefile.in	(revision 147057)
--- Makefile.in	(working copy)
*************** ipa-pure-const.o : ipa-pure-const.c $(CO
*** 2653,2659 ****
     coretypes.h $(TM_H) $(TREE_H) $(TREE_FLOW_H) $(TREE_INLINE_H) langhooks.h \
     pointer-set.h $(GGC_H) $(IPA_UTILS_H) $(C_COMMON_H) $(TARGET_H) \
     $(GIMPLE_H) $(CGRAPH_H) output.h $(FLAGS_H) $(TREE_PASS_H) $(TIMEVAR_H) \
!    $(DIAGNOSTIC_H)
  ipa-type-escape.o : ipa-type-escape.c $(CONFIG_H) $(SYSTEM_H) \
     coretypes.h $(TM_H) $(TREE_H) $(TREE_FLOW_H) $(TREE_INLINE_H) langhooks.h \
     pointer-set.h $(GGC_H) $(IPA_TYPE_ESCAPE_H) $(IPA_UTILS_H) $(C_COMMON_H) \
--- 2653,2659 ----
     coretypes.h $(TM_H) $(TREE_H) $(TREE_FLOW_H) $(TREE_INLINE_H) langhooks.h \
     pointer-set.h $(GGC_H) $(IPA_UTILS_H) $(C_COMMON_H) $(TARGET_H) \
     $(GIMPLE_H) $(CGRAPH_H) output.h $(FLAGS_H) $(TREE_PASS_H) $(TIMEVAR_H) \
!    $(DIAGNOSTIC_H) $(CFGLOOP_H) $(SCEV_H)
  ipa-type-escape.o : ipa-type-escape.c $(CONFIG_H) $(SYSTEM_H) \
     coretypes.h $(TM_H) $(TREE_H) $(TREE_FLOW_H) $(TREE_INLINE_H) langhooks.h \
     pointer-set.h $(GGC_H) $(IPA_TYPE_ESCAPE_H) $(IPA_UTILS_H) $(C_COMMON_H) \