[google] Use minimum cost circulation, not minimum cost flow to smooth profiles other minor fixes. (issue4536106)

Martin Thuresson martint@google.com
Thu Jun 2 18:00:00 GMT 2011


This patch from Neil Vachharajani and Dehao Chen improves mcf by using
minimum cost circulation instead of minimum cost flow to smooth profiles.
It also introduces a parameter for controlling running time of the algorithm.
This was what was originally presented in the academic work and handles
certain cases where the function entry and exit have incorrect profile
weights.

For now, this is for google/main. Once I have collected performance results
from SPEC I will propose this patch for trunk as well.

Bootstraps and no test regressions. Ok for google/main?

2011-06-02  Neil Vachharajani  <nvachhar@gmail.com>, Dehao Chen
	<danielcdh@gmail.com>

	* gcc/doc/invoke.texi (min-mcf-cancel-iters): Document.
	* gcc/mcf.c (MAX_ITER): Use new param PARAM_MIN_MCF_CANCEL_ITERS.
	(edge_type): Add SINK_SOURCE_EDGE.
	(dump_fixup_edge): Handle SINK_SOURCE_EDGE.
	(create_fixup_graph): Make problem miminum cost circulation.
	(cancel_negative_cycle): Update handling of infinite capacity.
	(compute_residual_flow): Update handling of infinite capacity.
	(find_max_flow): Update handling of infinite capacity.
	(modify_sink_source_capacity): New function.
	(find_minimum_cost_flow): Make problem miminum cost circulation.
	Use param PARAM_MIN_MCF_CANCEL_ITERS.
	* gcc/params.def (PARAM_MIN_MCF_CANCEL_ITERS): Define.

Index: gcc/doc/invoke.texi
===================================================================
--- gcc/doc/invoke.texi	(revision 174456)
+++ gcc/doc/invoke.texi	(working copy)
@@ -8341,6 +8341,12 @@ whether the result of a complex multipli
 
 The default is @option{-fno-cx-fortran-rules}.
 
+@item min-mcf-cancel-iters
+The minimum number of iterations of negative cycle cancellation during
+MCF profile correction before early termination.  This parameter is
+only useful when using @option{-fprofile-correction}.
+
+
 @end table
 
 The following options control optimizations that may improve
Index: gcc/mcf.c
===================================================================
--- gcc/mcf.c	(revision 174456)
+++ gcc/mcf.c	(working copy)
@@ -52,6 +52,8 @@ along with GCC; see the file COPYING3.  
 #include "langhooks.h"
 #include "tree.h"
 #include "gcov-io.h"
+#include "params.h"
+#include "diagnostic-core.h"
 
 #include "profile.h"
 
@@ -64,15 +66,18 @@ along with GCC; see the file COPYING3.  
 #define COST(k, w)      ((k) / mcf_ln ((w) + 2))
 /* Limit the number of iterations for cancel_negative_cycles() to ensure
    reasonable compile time.  */
-#define MAX_ITER(n, e)  10 + (1000000 / ((n) * (e)))
+#define MAX_ITER(n, e)  (PARAM_VALUE (PARAM_MIN_MCF_CANCEL_ITERS) + \
+			 (1000000 / ((n) * (e))))
+
 typedef enum
 {
-  INVALID_EDGE,
+  INVALID_EDGE = 0,
   VERTEX_SPLIT_EDGE,	    /* Edge to represent vertex with w(e) = w(v).  */
   REDIRECT_EDGE,	    /* Edge after vertex transformation.  */
   REVERSE_EDGE,
   SOURCE_CONNECT_EDGE,	    /* Single edge connecting to single source.  */
   SINK_CONNECT_EDGE,	    /* Single edge connecting to single sink.  */
+  SINK_SOURCE_EDGE,	    /* Single edge connecting sink to source.  */
   BALANCE_EDGE,		    /* Edge connecting with source/sink: cp(e) = 0.  */
   REDIRECT_NORMALIZED_EDGE, /* Normalized edge for a redirect edge.  */
   REVERSE_NORMALIZED_EDGE   /* Normalized edge for a reverse edge.  */
@@ -250,6 +255,10 @@ dump_fixup_edge (FILE *file, fixup_graph
 	  fputs (" @SINK_CONNECT_EDGE", file);
 	  break;
 
+	case SINK_SOURCE_EDGE:
+	  fputs (" @SINK_SOURCE_EDGE", file);
+	  break;
+
 	case REVERSE_EDGE:
 	  fputs (" @REVERSE_EDGE", file);
 	  break;
@@ -465,7 +474,7 @@ create_fixup_graph (fixup_graph_type *fi
   double k_neg = 0;
   /* Vector to hold D(v) = sum_out_edges(v) - sum_in_edges(v).  */
   gcov_type *diff_out_in = NULL;
-  gcov_type supply_value = 1, demand_value = 0;
+  gcov_type supply_value = 0, demand_value = 0;
   gcov_type fcost = 0;
   int new_entry_index = 0, new_exit_index = 0;
   int i = 0, j = 0;
@@ -486,14 +495,15 @@ create_fixup_graph (fixup_graph_type *fi
     fnum_vertices_after_transform + n_edges + n_basic_blocks + 2;
 
   /* In create_fixup_graph: Each basic block and edge can be split into 3
-     edges. Number of balance edges = n_basic_blocks. So after
-     create_fixup_graph:
-     max_edges = 4 * n_basic_blocks + 3 * n_edges
+     edges. Number of balance edges = n_basic_blocks - 1. And there is 1 edge
+     connecting new_entry and new_exit, and 2 edges connecting new_entry to
+     entry, and exit to new_exit. So after create_fixup_graph:
+     max_edges = 4 * n_basic_blocks + 3 * n_edges + 2
      Accounting for residual flow edges
-     max_edges = 2 * (4 * n_basic_blocks + 3 * n_edges)
-     = 8 * n_basic_blocks + 6 * n_edges
-     < 8 * n_basic_blocks + 8 * n_edges.  */
-  int fmax_num_edges = 8 * (n_basic_blocks + n_edges);
+     max_edges = 2 * (4 * n_basic_blocks + 3 * n_edges + 2)
+     = 8 * n_basic_blocks + 6 * n_edges + 4
+     < 8 * n_basic_blocks + 8 * n_edges + 8.  */
+  int fmax_num_edges = 8 * (n_basic_blocks + n_edges + 1);
 
   /* Initial num of vertices in the fixup graph.  */
   fixup_graph->num_vertices = n_basic_blocks;
@@ -512,7 +522,7 @@ create_fixup_graph (fixup_graph_type *fi
 
   /* Compute constants b, k_pos, k_neg used in the cost function calculation.
      b = sqrt(avg_vertex_weight(cfg)); k_pos = b; k_neg = 50b.  */
-  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+  FOR_ALL_BB (bb)
     total_vertex_weight += bb->count;
 
   sqrt_avg_vertex_weight = mcf_sqrt (total_vertex_weight / n_basic_blocks);
@@ -526,10 +536,11 @@ create_fixup_graph (fixup_graph_type *fi
   if (dump_file)
     fprintf (dump_file, "\nVertex transformation:\n");
 
-  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
+  FOR_ALL_BB (bb)
   {
     /* v'->v'': index1->(index1+1).  */
     i = 2 * bb->index;
+
     fcost = (gcov_type) COST (k_pos, bb->count);
     add_fixup_edge (fixup_graph, i, i + 1, VERTEX_SPLIT_EDGE, bb->count,
                     fcost, CAP_INFINITY);
@@ -593,23 +604,45 @@ create_fixup_graph (fixup_graph_type *fi
 
   new_entry_index = fixup_graph->new_entry_index = fixup_graph->num_vertices;
   fixup_graph->num_vertices++;
-  /* Set supply_value to 1 to avoid zero count function ENTRY.  */
-  add_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK, SOURCE_CONNECT_EDGE,
-		  1 /* supply_value */, 0, 1 /* supply_value */);
+  /* Set capacity to 0 initially, it will be updated after
+     supply_value is computed. */
+  add_fixup_edge (fixup_graph, new_entry_index, ENTRY_BLOCK,
+		  SOURCE_CONNECT_EDGE, 0 /* supply_value */, 0,
+		  0 /* supply_value */);
+  add_fixup_edge (fixup_graph, ENTRY_BLOCK, new_entry_index,
+                  SOURCE_CONNECT_EDGE, 0 /* supply_value */, 0,
+                  0 /* supply_value */);
 
-  /* Create new exit with EXIT_BLOCK as single pred.  */
+
+  /* Set capacity to 0 initially, it will be updated after
+     demand_value is computed. */
   new_exit_index = fixup_graph->new_exit_index = fixup_graph->num_vertices;
   fixup_graph->num_vertices++;
   add_fixup_edge (fixup_graph, 2 * EXIT_BLOCK + 1, new_exit_index,
                   SINK_CONNECT_EDGE,
                   0 /* demand_value */, 0, 0 /* demand_value */);
+  add_fixup_edge (fixup_graph, new_exit_index, 2 * EXIT_BLOCK + 1,
+                  SINK_CONNECT_EDGE,
+                  0 /* demand_value */, 0, 0 /* demand_value */);
+
+
+  /* Create a back edge from the new_exit to the new_entry.
+     Initially, its capacity will be set to 0 so that it does not
+     affect max flow, but later its capacity will be changed to
+     infinity to cancel negative cycles. */
+  add_fixup_edge (fixup_graph, new_exit_index, new_entry_index,
+		  SINK_SOURCE_EDGE, 0, 0, 0);
+
+
 
   /* Connect vertices with unbalanced D(v) to source/sink.  */
   if (dump_file)
     fprintf (dump_file, "\nD(v) balance:\n");
-  /* Skip vertices for ENTRY (0, 1) and EXIT (2,3) blocks, so start with i = 4.
-     diff_out_in[v''] will be 0, so skip v'' vertices, hence i += 2.  */
-  for (i = 4; i < new_entry_index; i += 2)
+
+  /* Skip vertices for ENTRY (0, 1) and EXIT (2,3) blocks, so start
+     with i = 4.  diff_out_in[v''] should be 0, but may not be due to
+     rounding error.  So here we consider all vertices.  */
+  for (i = 4; i < new_entry_index; i += 1)
     {
       if (diff_out_in[i] > 0)
 	{
@@ -674,7 +707,6 @@ create_fixup_graph (fixup_graph_type *fi
 	      fprintf (dump_file, "------------------\n");
 	    }
 
-	  pfedge->cost /= 2;
 	  pfedge->norm_vertex_index = new_index;
 	  if (dump_file)
 	    {
@@ -684,7 +716,7 @@ create_fixup_graph (fixup_graph_type *fi
 
 	  /* Add a new fixup edge: new_index->src.  */
 	  add_fixup_edge (fixup_graph, new_index, pfedge->src,
-			  REVERSE_NORMALIZED_EDGE, 0, r_pfedge->cost,
+			  REVERSE_NORMALIZED_EDGE, 0, 0,
 			  r_pfedge->max_capacity);
 	  gcc_assert (fixup_graph->num_vertices <= fmax_num_vertices);
 
@@ -692,7 +724,6 @@ create_fixup_graph (fixup_graph_type *fi
              ==> r_pfedge->src -> new_index.  */
 	  r_pfedge->dest = new_index;
 	  r_pfedge->type = REVERSE_NORMALIZED_EDGE;
-	  r_pfedge->cost = pfedge->cost;
 	  r_pfedge->max_capacity = pfedge->max_capacity;
 	  if (dump_file)
 	    dump_fixup_edge (dump_file, fixup_graph, r_pfedge);
@@ -794,14 +825,12 @@ cancel_negative_cycle (fixup_graph_type 
   bool found_cycle = false;
   int cycle_start = 0, cycle_end = 0;
   gcov_type sum_cost = 0, cycle_flow = 0;
-  int new_entry_index;
   bool propagated = false;
 
   gcc_assert (fixup_graph);
   fnum_vertices = fixup_graph->num_vertices;
   fnum_edges = fixup_graph->num_edges;
   fedge_list = fixup_graph->edge_list;
-  new_entry_index = fixup_graph->new_entry_index;
 
   /* Initialize.  */
   /* Skip ENTRY.  */
@@ -820,8 +849,6 @@ cancel_negative_cycle (fixup_graph_type 
     for (i = 0; i < fnum_edges; i++)
       {
 	pfedge = fedge_list + i;
-	if (pfedge->src == new_entry_index)
-	  continue;
 	if (pfedge->is_rflow_valid && pfedge->rflow
             && d[pfedge->src] != CAP_INFINITY
 	    && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost))
@@ -843,8 +870,6 @@ cancel_negative_cycle (fixup_graph_type 
   for (i = 0; i < fnum_edges; i++)
     {
       pfedge = fedge_list + i;
-      if (pfedge->src == new_entry_index)
-	continue;
       if (pfedge->is_rflow_valid && pfedge->rflow
           && d[pfedge->src] != CAP_INFINITY
 	  && (d[pfedge->dest] > d[pfedge->src] + pfedge->cost))
@@ -912,10 +937,12 @@ cancel_negative_cycle (fixup_graph_type 
     {
       pfedge = find_fixup_edge (fixup_graph, cycle[k + 1], cycle[k]);
       r_pfedge = find_fixup_edge (fixup_graph, cycle[k], cycle[k + 1]);
-      pfedge->rflow -= cycle_flow;
+      if (pfedge->rflow != CAP_INFINITY)
+        pfedge->rflow -= cycle_flow;
       if (pfedge->type)
 	pfedge->flow += cycle_flow;
-      r_pfedge->rflow += cycle_flow;
+      if (r_pfedge->rflow != CAP_INFINITY)
+        r_pfedge->rflow += cycle_flow;
       if (r_pfedge->type)
 	r_pfedge->flow -= cycle_flow;
     }
@@ -945,7 +972,8 @@ compute_residual_flow (fixup_graph_type 
   for (i = 0; i < fnum_edges; i++)
     {
       pfedge = fedge_list + i;
-      pfedge->rflow = pfedge->max_capacity - pfedge->flow;
+      pfedge->rflow = pfedge->max_capacity == CAP_INFINITY ?
+                      CAP_INFINITY : pfedge->max_capacity - pfedge->flow;
       pfedge->is_rflow_valid = true;
       add_rfixup_edge (fixup_graph, pfedge->dest, pfedge->src, pfedge->flow,
 		       -pfedge->cost);
@@ -1070,20 +1098,22 @@ find_max_flow (fixup_graph_type *fixup_g
 	{
 	  pfedge = find_fixup_edge (fixup_graph, bb_pred[u], u);
 	  r_pfedge = find_fixup_edge (fixup_graph, u, bb_pred[u]);
+
+          if (pfedge->rflow != CAP_INFINITY)
+	    pfedge->rflow -= increment;
+          if (r_pfedge->rflow != CAP_INFINITY)
+	    r_pfedge->rflow += increment;
+
 	  if (pfedge->type)
 	    {
 	      /* forward edge.  */
 	      pfedge->flow += increment;
-	      pfedge->rflow -= increment;
-	      r_pfedge->rflow += increment;
 	    }
 	  else
 	    {
 	      /* backward edge.  */
 	      gcc_assert (r_pfedge->type);
-	      r_pfedge->rflow += increment;
 	      r_pfedge->flow -= increment;
-	      pfedge->rflow -= increment;
 	    }
 	}
 
@@ -1302,6 +1332,60 @@ adjust_cfg_counts (fixup_graph_type *fix
 }
 
 
+/* Called before negative_cycle_cancellation, to form a cycle between
+ * new_exit to new_entry in FIXUP_GRAPH with capacity MAX_FLOW. We
+ * don't want the flow in the BALANCE_EDGE to be modified, so we set
+ * the residural flow of those edges to 0 */
+
+static void
+modify_sink_source_capacity (fixup_graph_type *fixup_graph, gcov_type max_flow)
+{
+  fixup_edge_p edge, r_edge;
+  int i;
+  int entry = ENTRY_BLOCK;
+  int exit = 2 * EXIT_BLOCK + 1;
+  int new_entry = fixup_graph->new_entry_index;
+  int new_exit = fixup_graph->new_exit_index;
+
+  edge = find_fixup_edge (fixup_graph, new_entry, entry);
+  edge->max_capacity = CAP_INFINITY;
+  edge->rflow = CAP_INFINITY;
+
+  edge = find_fixup_edge (fixup_graph, entry, new_entry);
+  edge->max_capacity = CAP_INFINITY;
+  edge->rflow = CAP_INFINITY;
+
+  edge = find_fixup_edge (fixup_graph, exit, new_exit);
+  edge->max_capacity = CAP_INFINITY;
+  edge->rflow = CAP_INFINITY;
+
+  edge = find_fixup_edge (fixup_graph, new_exit, exit);
+  edge->max_capacity = CAP_INFINITY;
+  edge->rflow = CAP_INFINITY;
+
+  edge = find_fixup_edge (fixup_graph, new_exit, new_entry);
+  edge->max_capacity = CAP_INFINITY;
+  edge->flow = max_flow;
+  edge->rflow = CAP_INFINITY;
+
+  r_edge = find_fixup_edge (fixup_graph, new_entry, new_exit);
+  r_edge->rflow = max_flow;
+
+  /* Find all the backwards residual edges corresponding to
+     BALANCE_EDGEs and set their residual flow to 0 to enforce a
+     minimum flow constraint on these edges. */
+  for (i = 4; i < new_entry; i += 1)
+    {
+      edge = find_fixup_edge (fixup_graph, i, new_entry);
+      if (edge)
+	edge->rflow = 0;
+      edge = find_fixup_edge (fixup_graph, new_exit, i);
+      if (edge)
+	edge->rflow = 0;
+    }
+}
+
+
 /* Implements the negative cycle canceling algorithm to compute a minimum cost
    flow.
 Algorithm:
@@ -1330,13 +1414,18 @@ find_minimum_cost_flow (fixup_graph_type
   int fnum_vertices;
   int new_exit_index;
   int new_entry_index;
+  gcov_type max_flow;
 
   gcc_assert (fixup_graph);
   fnum_vertices = fixup_graph->num_vertices;
   new_exit_index = fixup_graph->new_exit_index;
   new_entry_index = fixup_graph->new_entry_index;
 
-  find_max_flow (fixup_graph, new_entry_index, new_exit_index);
+  max_flow = find_max_flow (fixup_graph, new_entry_index, new_exit_index);
+
+  /* Adjust the fixup graph to translate things into a minimum cost
+     circulation problem. */
+  modify_sink_source_capacity (fixup_graph, max_flow);
 
   /* Initialize the structures for find_negative_cycle().  */
   pred = (int *) xcalloc (fnum_vertices, sizeof (int));
@@ -1352,7 +1441,12 @@ find_minimum_cost_flow (fixup_graph_type
       iteration++;
       if (iteration > MAX_ITER (fixup_graph->num_vertices,
                                 fixup_graph->num_edges))
-        break;
+	{
+	  inform (DECL_SOURCE_LOCATION (current_function_decl),
+		  "Exiting profile correction early to avoid excessive "
+		  "compile time");
+	  break;
+	}
     }
 
   if (dump_file)
Index: gcc/params.def
===================================================================
--- gcc/params.def	(revision 174456)
+++ gcc/params.def	(working copy)
@@ -977,6 +977,12 @@ DEFPARAM (MIN_PARTITION_SIZE,
 	  "Size of minimal paritition for WHOPR (in estimated instructions)",
 	  1000, 0, 0)
 
+DEFPARAM (PARAM_MIN_MCF_CANCEL_ITERS,
+	  "min-mcf-cancel-iters",
+	  "the minimum number of iterations of negative cycle cancellation "
+	  "in MCF",
+	  10, 1, 0)
+
 /* Diagnostic parameters.  */
 
 DEFPARAM (CXX_MAX_NAMESPACES_FOR_DIAGNOSTIC_HELP,

--
This patch is available for review at http://codereview.appspot.com/4536106



More information about the Gcc-patches mailing list