Array_index inline hint

[Jan Hubicka <hubicka at ucw dot cz>]

Hi,
this should be last of inline hint patches for 4.8. It makes inliner to preffer inlining
of functions where array index will become constant.  This helps especially accesses to
Fortran arrays with array descriptors.
It helps some of Fotran benchmarks, most importantly probably to fotigue, where it 
unforutnately enables just half of the inlining that would be desirable because
of limitations of jump function analysis. This will probably have to wait for next
stage1.

Bootstrapped/regtested x86_64-linux, benchmarked on Mozilla/spec2006/spec2k/polyhedron

	 Ipa-inline.c (want_inline_small_function_p): Take aray index hint.
	(edge_badness): Likewise.
	* ipa-inline.h (inline_hints_vals): Add array_index and comments.
	(inline_summary_: Add ARRAY_INDEX.
	* ipa-inline-analysis.c (dump_inline_hints): Dump array_index hint.
	(reset_inline_summary): Handle array_index hint.
	(inline_node_duplication_hook): Likewise.
	(dump_inline_summary): Likewise.
	(array_index_predicate): New function.
	(estimate_function_body_sizes): Use it.
	(estimate_node_size_and_time): Use array_index hint.
	(inline_merge_summary, inline_read_section): Likewise.

Index: ipa-inline.c
===================================================================
*** ipa-inline.c	(revision 193405)
--- ipa-inline.c	(working copy)
*************** want_inline_small_function_p (struct cgr
*** 541,546 ****
--- 541,547 ----
  	       && !big_speedup
  	       && !(hints & (INLINE_HINT_indirect_call
  			     | INLINE_HINT_loop_iterations
+ 			     | INLINE_HINT_array_index
  			     | INLINE_HINT_loop_stride)))
  	{
            e->inline_failed = CIF_MAX_INLINE_INSNS_SINGLE_LIMIT;
*************** want_inline_small_function_p (struct cgr
*** 595,600 ****
--- 596,602 ----
  	       && !big_speedup
  	       && growth >= ((hints & (INLINE_HINT_indirect_call
  				       | INLINE_HINT_loop_iterations
+ 			               | INLINE_HINT_array_index
  				       | INLINE_HINT_loop_stride))
  			     ? MAX (MAX_INLINE_INSNS_AUTO,
  				    MAX_INLINE_INSNS_SINGLE)
*************** edge_badness (struct cgraph_edge *edge, 
*** 919,924 ****
--- 921,927 ----
        gcc_checking_assert (badness <=0 && badness >= INT_MIN / 16);
        if ((hints & (INLINE_HINT_indirect_call
  		    | INLINE_HINT_loop_iterations
+ 	            | INLINE_HINT_array_index
  		    | INLINE_HINT_loop_stride))
  	  || callee_info->growth <= 0)
  	badness *= 8;
Index: ipa-inline.h
===================================================================
*** ipa-inline.h	(revision 193405)
--- ipa-inline.h	(working copy)
*************** typedef struct GTY(()) condition
*** 44,59 ****
      unsigned by_ref : 1;
    } condition;
  
! /* Inline hints are reasons why inline heuristics should preffer inlining given function.
!    They are represtented as bitmap of the following values.  */
  enum inline_hints_vals {
    INLINE_HINT_indirect_call = 1,
    INLINE_HINT_loop_iterations = 2,
    INLINE_HINT_loop_stride = 4,
    INLINE_HINT_same_scc = 8,
    INLINE_HINT_in_scc = 16,
    INLINE_HINT_declared_inline = 32,
!   INLINE_HINT_cross_module = 64
  };
  typedef int inline_hints;
  
--- 44,75 ----
      unsigned by_ref : 1;
    } condition;
  
! /* Inline hints are reasons why inline heuristics should preffer inlining given
!    function.  They are represtented as bitmap of the following values.  */
  enum inline_hints_vals {
+   /* When inlining turns indirect call into a direct call,
+      it is good idea to do so.  */
    INLINE_HINT_indirect_call = 1,
+   /* Inlining may make loop iterations or loop stride known.  It is good idea
+      to do so because it enables loop optimizatoins.  */
    INLINE_HINT_loop_iterations = 2,
    INLINE_HINT_loop_stride = 4,
+   /* Inlining withing same strongly connected component of callgraph is often
+      a loss due to increased stack frame usage and prologue setup costs.  */
    INLINE_HINT_same_scc = 8,
+   /* Inlining functions in strongly connected component is not such a great
+      win.  */
    INLINE_HINT_in_scc = 16,
+   /* If function is declared inline by user, it may be good idea to inline
+      it.  */
    INLINE_HINT_declared_inline = 32,
!   /* Programs are usually still organized for non-LTO compilation and thus
!      if functions are in different modules, inlining may not be so important. 
!    */
!   INLINE_HINT_cross_module = 64,
!   /* If array indexes of loads/stores become known there may be room for
!      futher optimization.  */
!   INLINE_HINT_array_index = 128
  };
  typedef int inline_hints;
  
*************** struct GTY(()) inline_summary
*** 133,138 ****
--- 149,156 ----
    /* Predicate on when some loop in the function becomes to have known
       stride.   */
    struct predicate * GTY((skip)) loop_stride;
+   /* Predicate on when some array indexes become constants.  */
+   struct predicate * GTY((skip)) array_index;
    /* Estimated growth for inlining all copies of the function before start
       of small functions inlining.
       This value will get out of date as the callers are duplicated, but
Index: ipa-inline-analysis.c
===================================================================
*** ipa-inline-analysis.c	(revision 193405)
--- ipa-inline-analysis.c	(working copy)
*************** dump_inline_hints (FILE *f, inline_hints
*** 659,664 ****
--- 659,669 ----
        hints &= ~INLINE_HINT_declared_inline;
        fprintf (f, " declared_inline");
      }
+   if (hints & INLINE_HINT_array_index)
+     {
+       hints &= ~INLINE_HINT_array_index;
+       fprintf (f, " array_index");
+     }
    gcc_assert (!hints);
  }
  
*************** reset_inline_summary (struct cgraph_node
*** 1007,1012 ****
--- 1012,1022 ----
        pool_free (edge_predicate_pool, info->loop_stride);
        info->loop_stride = NULL;
      }
+   if (info->array_index)
+     {
+       pool_free (edge_predicate_pool, info->array_index);
+       info->array_index = NULL;
+     }
    VEC_free (condition, gc, info->conds);
    VEC_free (size_time_entry,gc, info->entry);
    for (e = node->callees; e; e = e->next_callee)
*************** inline_node_duplication_hook (struct cgr
*** 1201,1206 ****
--- 1211,1219 ----
        remap_hint_predicate_after_duplication (&info->loop_stride,
  					      possible_truths,
  					      info);
+       remap_hint_predicate_after_duplication (&info->array_index,
+ 					      possible_truths,
+ 					      info);
  
        /* If inliner or someone after inliner will ever start producing
  	 non-trivial clones, we will get trouble with lack of information
*************** inline_node_duplication_hook (struct cgr
*** 1224,1229 ****
--- 1237,1248 ----
  	  info->loop_stride = NULL;
  	  set_hint_predicate (&info->loop_stride, p);
  	}
+       if (info->array_index)
+ 	{
+ 	  predicate p = *info->array_index;
+ 	  info->array_index = NULL;
+ 	  set_hint_predicate (&info->array_index, p);
+ 	}
      }
    inline_update_overall_summary (dst);
  }
*************** dump_inline_summary (FILE * f, struct cg
*** 1413,1418 ****
--- 1432,1442 ----
  	  fprintf (f, "  loop stride:");
  	  dump_predicate (f, s->conds, s->loop_stride);
  	}
+       if (s->array_index)
+ 	{
+ 	  fprintf (f, "  array index:");
+ 	  dump_predicate (f, s->conds, s->array_index);
+ 	}
        fprintf (f, "  calls:\n");
        dump_inline_edge_summary (f, 4, node, s);
        fprintf (f, "\n");
*************** predicate_for_phi_result (struct inline_
*** 2262,2267 ****
--- 2286,2313 ----
  	       SSA_NAME_VERSION (gimple_phi_result (phi)), *p);
  }
  
+ /* Return predicate specifying when array index in access OP becomes non-constant.  */
+ 
+ static struct predicate
+ array_index_predicate (struct inline_summary *info,
+ 		       VEC (predicate_t, heap) *nonconstant_names, tree op)
+ {
+   struct predicate p = false_predicate ();
+   while (handled_component_p (op))
+     {
+       if (TREE_CODE (op) == ARRAY_REF
+ 	  || TREE_CODE (op) == ARRAY_RANGE_REF)
+         {
+ 	  if (TREE_CODE (TREE_OPERAND (op, 1)) == SSA_NAME)
+ 	     p = or_predicates (info->conds, &p,
+ 				&VEC_index (predicate_t, nonconstant_names,
+                                             SSA_NAME_VERSION (TREE_OPERAND (op, 1))));
+         }
+       op = TREE_OPERAND (op, 0);
+     }
+   return p;
+ }
+ 
  /* Compute function body size parameters for NODE.
     When EARLY is true, we compute only simple summaries without
     non-trivial predicates to drive the early inliner.  */
*************** estimate_function_body_sizes (struct cgr
*** 2284,2289 ****
--- 2330,2336 ----
    VEC (predicate_t, heap) *nonconstant_names = NULL;
    int nblocks, n;
    int *order;
+   predicate array_index = true_predicate ();
  
    info->conds = 0;
    info->entry = 0;
*************** estimate_function_body_sizes (struct cgr
*** 2380,2385 ****
--- 2427,2450 ----
  		       ((double)freq)/CGRAPH_FREQ_BASE, this_size, this_time);
  	    }
  
+ 	  if (gimple_assign_load_p (stmt) && nonconstant_names)
+ 	    {
+ 	      struct predicate this_array_index;
+ 	      this_array_index = array_index_predicate (info, nonconstant_names,
+ 						        gimple_assign_rhs1 (stmt));
+ 	      if (!false_predicate_p (&this_array_index))
+ 	        array_index = and_predicates (info->conds, &array_index, &this_array_index);
+ 	    }
+ 	  if (gimple_store_p (stmt) && nonconstant_names)
+ 	    {
+ 	      struct predicate this_array_index;
+ 	      this_array_index = array_index_predicate (info, nonconstant_names,
+ 						        gimple_get_lhs (stmt));
+ 	      if (!false_predicate_p (&this_array_index))
+ 	        array_index = and_predicates (info->conds, &array_index, &this_array_index);
+ 	    }
+ 	   
+ 
  	  if (is_gimple_call (stmt))
  	    {
  	      struct cgraph_edge *edge = cgraph_edge (node, stmt);
*************** estimate_function_body_sizes (struct cgr
*** 2476,2496 ****
  	    }
  	}
      }
!   FOR_ALL_BB_FN (bb, my_function)
!     {
!       edge e;
!       edge_iterator ei;
! 
!       if (bb->aux)
! 	pool_free (edge_predicate_pool, bb->aux);
!       bb->aux = NULL;
!       FOR_EACH_EDGE (e, ei, bb->succs)
! 	{
! 	  if (e->aux)
! 	    pool_free (edge_predicate_pool, e->aux);
! 	  e->aux = NULL;
! 	}
!     }
    time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
    if (time > MAX_TIME)
      time = MAX_TIME;
--- 2541,2547 ----
  	    }
  	}
      }
!   set_hint_predicate (&inline_summary (node)->array_index, array_index);
    time = (time + CGRAPH_FREQ_BASE / 2) / CGRAPH_FREQ_BASE;
    if (time > MAX_TIME)
      time = MAX_TIME;
*************** estimate_function_body_sizes (struct cgr
*** 2513,2518 ****
--- 2564,2570 ----
  	  unsigned int j, i;
  	  struct tree_niter_desc niter_desc;
  	  basic_block *body = get_loop_body (loop);
+ 	  bb_predicate = *(struct predicate *)loop->header->aux;
  
  	  exits = get_loop_exit_edges (loop);
            FOR_EACH_VEC_ELT (edge, exits, j, ex)
*************** estimate_function_body_sizes (struct cgr
*** 2522,2527 ****
--- 2574,2583 ----
  		predicate will_be_nonconstant
  		 = will_be_nonconstant_expr_predicate (parms_info, info,
  						       niter_desc.niter, nonconstant_names);
+ 	        if (!true_predicate_p (&will_be_nonconstant))
+ 		  will_be_nonconstant = and_predicates (info->conds,
+ 							&bb_predicate,
+ 							&will_be_nonconstant);
  		if (!true_predicate_p (&will_be_nonconstant)
  		    && !false_predicate_p (&will_be_nonconstant))
  		  /* This is slightly inprecise.  We may want to represent each loop with
*************** estimate_function_body_sizes (struct cgr
*** 2533,2538 ****
--- 2589,2595 ----
            for (i = 0; i < loop->num_nodes; i++)
  	    {
  	      gimple_stmt_iterator gsi;
+ 	      bb_predicate = *(struct predicate *)body[i]->aux;
  	      for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
  		{
  		  gimple stmt = gsi_stmt (gsi);
*************** estimate_function_body_sizes (struct cgr
*** 2550,2555 ****
--- 2607,2616 ----
  		      will_be_nonconstant
  		       = will_be_nonconstant_expr_predicate (parms_info, info,
  							     iv.step, nonconstant_names);
+ 		      if (!true_predicate_p (&will_be_nonconstant))
+ 			will_be_nonconstant = and_predicates (info->conds,
+ 							      &bb_predicate,
+ 							      &will_be_nonconstant);
  		      if (!true_predicate_p (&will_be_nonconstant)
  			  && !false_predicate_p (&will_be_nonconstant))
  			/* This is slightly inprecise.  We may want to represent each loop with
*************** estimate_function_body_sizes (struct cgr
*** 2564,2569 ****
--- 2625,2645 ----
        set_hint_predicate (&inline_summary (node)->loop_stride, loop_stride);
        scev_finalize ();
      }
+   FOR_ALL_BB_FN (bb, my_function)
+     {
+       edge e;
+       edge_iterator ei;
+ 
+       if (bb->aux)
+ 	pool_free (edge_predicate_pool, bb->aux);
+       bb->aux = NULL;
+       FOR_EACH_EDGE (e, ei, bb->succs)
+ 	{
+ 	  if (e->aux)
+ 	    pool_free (edge_predicate_pool, e->aux);
+ 	  e->aux = NULL;
+ 	}
+     }
    inline_summary (node)->self_time = time;
    inline_summary (node)->self_size = size;
    VEC_free (predicate_t, heap, nonconstant_names);
*************** estimate_node_size_and_time (struct cgra
*** 2881,2886 ****
--- 2957,2965 ----
    if (info->loop_stride
        && !evaluate_predicate (info->loop_stride, possible_truths))
      hints |=INLINE_HINT_loop_stride;
+   if (info->array_index
+       && !evaluate_predicate (info->array_index, possible_truths))
+     hints |=INLINE_HINT_array_index;
    if (info->scc_no)
      hints |= INLINE_HINT_in_scc;
    if (DECL_DECLARED_INLINE_P (node->symbol.decl))
*************** inline_merge_summary (struct cgraph_edge
*** 3311,3316 ****
--- 3390,3399 ----
  			&callee_info->loop_stride,
  			operand_map, offset_map,
  			clause, &toplev_predicate);
+   remap_hint_predicate (info, callee_info,
+ 			&callee_info->array_index,
+ 			operand_map, offset_map,
+ 			clause, &toplev_predicate);
  
    inline_update_callee_summaries (edge->callee,
  				  inline_edge_summary (edge)->loop_depth);
*************** inline_read_section (struct lto_file_dec
*** 3803,3808 ****
--- 3886,3893 ----
        set_hint_predicate (&info->loop_iterations, p);
        p = read_predicate (&ib);
        set_hint_predicate (&info->loop_stride, p);
+       p = read_predicate (&ib);
+       set_hint_predicate (&info->array_index, p);
        for (e = node->callees; e; e = e->next_callee)
  	read_inline_edge_summary (&ib, e);
        for (e = node->indirect_calls; e; e = e->next_callee)
*************** inline_write_summary (void)
*** 3954,3959 ****
--- 4039,4045 ----
  	    }
  	  write_predicate (ob, info->loop_iterations);
  	  write_predicate (ob, info->loop_stride);
+ 	  write_predicate (ob, info->array_index);
  	  for (edge = node->callees; edge; edge = edge->next_callee)
  	    write_inline_edge_summary (ob, edge);
  	  for (edge = node->indirect_calls; edge; edge = edge->next_callee)