Patchwork [3/3] Compute predicates for phi node results in ipa-inline-analysis.c

login
register
mail settings
Submitter Martin Jambor
Date July 2, 2012, 9:17 p.m.
Message ID <20120702211737.GA7599@virgil.arch.suse.de>
Download mbox | patch
Permalink /patch/168642/
State New
Headers show

Comments

Martin Jambor - July 2, 2012, 9:17 p.m.
Hi,

this third patch is basically a proof-of-concept aiming at alleviating
the following code found in Fortran functions when they look at the
contents of array descriptors:

  <bb 2>:
    stride.156_7 = strain_tensor_6(D)->dim[0].stride;
    if (stride.156_7 != 0)
      goto <bb 3>;
    else
      goto <bb 4>;

  <bb 3>:

  <bb 4>:
    # stride.156_4 = PHI <stride.156_7(3), 1(2)>

and stride.156_4 is then used for other computations.  Currently we
compute a predicate for SSA name stride.156_7 but the PHI node stops
us from having one for stride.156_4 and those computed from it.

This patch looks at phi nodes, and if its pairs of predecessors have
the same nearest common dominator, and the condition there is known to
be described by a predicate (computed either by
set_cond_stmt_execution_predicate or,
set_switch_stmt_execution_predicate, we depend on knowing how exactly
they behave), we use the parameter and offset from the predicate
condition and create one for the PHI node result, provided the
arguments of a phi node allow that, of course.

I hacked this together one evening a some timw ago and I expect to
talk with Honza about how we can perhaps access information abut edges
properly, nevertheless the patch passes bootstrap and testing on
x86_64.

On current trunk, I need to pass -finline-limit=204 to cut down
execution time of fatigue2 polyhedron benchmark from 155 seconds to 91
seconds.  With the patch, I only need -finline-limit=166.  So there's
still quite some way to go but something along these lines can be part
of it.

Thanks for all comments and suggestions,

Martin


2012-05-30  Martin Jambor  <mjambor@suse.cz>

	* ipa-inline-analysis.c (known_phi_condition_for_bb): New function.
	(predicate_for_phi_result): Likewise.
	(estimate_function_body_sizes): Use the above two functions.
	(inline_analyze_function): Calculate and free dominance info.
Jan Hubicka - Aug. 10, 2012, 3:32 a.m.
> Hi,
> 
> this third patch is basically a proof-of-concept aiming at alleviating
> the following code found in Fortran functions when they look at the
> contents of array descriptors:
> 
>   <bb 2>:
>     stride.156_7 = strain_tensor_6(D)->dim[0].stride;
>     if (stride.156_7 != 0)
>       goto <bb 3>;
>     else
>       goto <bb 4>;
> 
>   <bb 3>:
> 
>   <bb 4>:
>     # stride.156_4 = PHI <stride.156_7(3), 1(2)>
> 
> and stride.156_4 is then used for other computations.  Currently we
> compute a predicate for SSA name stride.156_7 but the PHI node stops
> us from having one for stride.156_4 and those computed from it.
> 
> This patch looks at phi nodes, and if its pairs of predecessors have
> the same nearest common dominator, and the condition there is known to
> be described by a predicate (computed either by
> set_cond_stmt_execution_predicate or,
> set_switch_stmt_execution_predicate, we depend on knowing how exactly
> they behave), we use the parameter and offset from the predicate
> condition and create one for the PHI node result, provided the
> arguments of a phi node allow that, of course.

Consider:

     b==0?
    T/  \F
    /    \
   /      \
 a==0?   a==0?
T/ \F   T/  \F
... \   /   ...
     \ /
     PHI

In this case vale of PHI is determined by a==0, but the condition in common
dominator would be b==0.  We can work this out from control dependency relation
or handle it by propagation engine, but perhaps it is overkill. What about
special casing (half) diamond CFG to start with?

Path is OK with that change.
Honza

Patch

Index: src/gcc/ipa-inline-analysis.c
===================================================================
--- src.orig/gcc/ipa-inline-analysis.c
+++ src/gcc/ipa-inline-analysis.c
@@ -1954,6 +1954,96 @@  param_change_prob (gimple stmt, int i)
   return REG_BR_PROB_BASE;
 }
 
+/* For basic block BB, find if all pairs of its predecesors have a common
+   dominator and if that dominator ends with a simple condition.  If so, return
+   TRUE and stor pointer to *C.  */
+
+static bool
+known_phi_condition_for_bb (struct inline_summary *info, basic_block bb,
+			    struct condition **c)
+{
+  edge_iterator ei;
+  edge e;
+  basic_block computed_dom = NULL;
+  basic_block prev = NULL;
+
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    {
+      if (prev)
+	{
+	  basic_block dom = nearest_common_dominator (CDI_DOMINATORS, prev,
+						      e->src);
+	  if (!computed_dom)
+	    computed_dom = dom;
+	  else if (dom != computed_dom)
+	    return false;
+
+	}
+      prev = e->src;
+    }
+
+  if (!computed_dom)
+    return false;
+
+  FOR_EACH_EDGE (e, ei, computed_dom->succs)
+    if (e->aux)
+      {
+	struct predicate *p;
+	int i;
+	p = (struct predicate *) e->aux;
+
+	if (p->clause[0] == 0 || p->clause[1] != 0)
+	  return false;
+	for (i = 0 ; i < NUM_CONDITIONS; i++)
+	  if (((1 << i) & p->clause[0]) == p->clause[0])
+	    break;
+	if (i == NUM_CONDITIONS || i < predicate_first_dynamic_condition)
+	  return false;
+
+	*c = VEC_index (condition, info->conds,
+			i - predicate_first_dynamic_condition);
+	return true;
+      }
+  return false;
+}
+
+/* Given a PHI statement STMT in a function described by inline properties INFO
+   and in a basic lock whose predecesors in CFG is selected according to a
+   parameter (and potentially offset) stored in condition *C, store a predicate
+   for the result of the PHI statement into NONCONSTANT_NAMES, if possible.  */
+
+static void
+predicate_for_phi_result (struct inline_summary *info, gimple stmt,
+			  struct condition *c,
+			  VEC (predicate_t, heap) *nonconstant_names)
+{
+  struct predicate p;
+  unsigned i;
+
+  for (i = 0; i < gimple_phi_num_args (stmt); i++)
+    {
+      tree arg = gimple_phi_arg (stmt, i)->def;
+      if (!is_gimple_min_invariant (arg))
+	{
+	  gcc_assert (TREE_CODE (arg) == SSA_NAME);
+	  if (true_predicate_p (VEC_index (predicate_t, nonconstant_names,
+					    SSA_NAME_VERSION (arg))))
+	      return;
+	}
+    }
+
+  p = add_condition (info, c->operand_num, c->agg_contents, c->offset,
+		     CHANGED, NULL);
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "  ");
+      print_gimple_stmt (dump_file, stmt, 0, 0);
+      fprintf (dump_file, "\t\tphi predicate: ");
+      dump_predicate (dump_file, info->conds, &p);
+    }
+  VEC_replace (predicate_t, nonconstant_names,
+	       SSA_NAME_VERSION (gimple_phi_result (stmt)), &p);
+}
 
 /* Compute function body size parameters for NODE.
    When EARLY is true, we compute only simple summaries without
@@ -2022,7 +2112,17 @@  estimate_function_body_sizes (struct cgr
 	  fprintf (dump_file, "\n BB %i predicate:", bb->index);
 	  dump_predicate (dump_file, info->conds, &bb_predicate);
 	}
-      
+
+      if (parms_info && nonconstant_names)
+	for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+	  {
+	    struct condition *phi_condition;
+	    if (!known_phi_condition_for_bb (info, bb, &phi_condition))
+	      break;
+	    predicate_for_phi_result (info, gsi_stmt (bsi), phi_condition,
+				      nonconstant_names);
+	  }
+
       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 	{
 	  gimple stmt = gsi_stmt (bsi);
@@ -3070,12 +3170,16 @@  inline_analyze_function (struct cgraph_n
   push_cfun (DECL_STRUCT_FUNCTION (node->symbol.decl));
   current_function_decl = node->symbol.decl;
 
+  if (cfun)
+    calculate_dominance_info (CDI_DOMINATORS);
   if (dump_file)
     fprintf (dump_file, "\nAnalyzing function: %s/%u\n",
 	     cgraph_node_name (node), node->uid);
   if (optimize && !node->thunk.thunk_p)
     inline_indirect_intraprocedural_analysis (node);
   compute_inline_parameters (node, false);
+  if (cfun)
+    free_dominance_info (CDI_DOMINATORS);
 
   current_function_decl = NULL;
   pop_cfun ();