Re: [PATCH][RFC] Fix PR63155

[Richard Biener <rguenther@suse.de>]

On Mon, 9 Mar 2015, Richard Biener wrote:

> On Fri, 6 Mar 2015, Jeff Law wrote:
> 
> > On 03/06/15 06:16, Richard Biener wrote:
> > > 
> > > This fixes PR63155 and reduces the memory usage at -O0 from reported
> > > 10GB (couldn't verify/update on my small box) to 350MB (still worse
> > > compared to 4.8 which needs only 50MB).
> > > 
> > > It fixes this by no longer computing live info or building a conflict
> > > graph for coalescing of SSA names flowing over abnormal edges
> > > (which needs to succeed).
> > > 
> > > Of course this also removes verification that this coalescing is valid
> > > (but computing this has quadratic cost).  With this it turns
> > > ICEs into miscompiles.
> > > 
> > > We could restrict verifying that we can perform abnormal coalescing
> > > to ENABLE_CHECKING (and I've wanted a verifier pass that can verify
> > > this multiple times to be able to catch what breaks it and not having
> > > to work back from out-of-SSA ICEing...).
> > > 
> > > So any opinion on this patch welcome.
> > > 
> > > Bootstrap and regtest running on x86_64-unknown-linux-gnu.
> > > 
> > > Ok for trunk? ;)
> > > 
> > > Thanks,
> > > Richard.
> > > 
> > > 2015-03-06  Richard Biener  <rguenther@suse.de>
> > > 
> > > 	PR middle-end/63155
> > > 	* tree-ssa-coalesce.c (attempt_coalesce): Handle graph being NULL.
> > > 	(coalesce_partitions): Split out abnormal coalescing to ...
> > > 	(perform_abnormal_coalescing): ... this function.
> > > 	(coalesce_ssa_name): Perform abnormal coalescing without computing
> > > 	live/conflict.
> > I'd personally like to keep the checking when ENABLE_CHECKING.
> > 
> > I haven't followed this discussion real closely, but I wonder if some kind of
> > blocking approach would work without blowing up the memory consumption.
> > There's no inherent reason why we have to coalesce everything at the same
> > time.  We can use a blocking factor and do coalescing on some N number of
> > SSA_NAMEs at a time.
> 
> Yes, that's possible at (quite?) some compile-time cost.  Note that we
> can't really guarantee that the resulting live/conflict problems shrink
> significantly enough without sorting the coalesces in a different way
> (not after important coalesces but after their basevars).
>  
> > I suspect we can select an N that ultimately degenerates into the current "do
> > everything together" for the common case and only has to iterate over blocks
> > of SSA_NAMEs in extreme cases.
> 
> I've attached a patch to the PR that adds such a number N after which we
> simply stop coalescing.  Of course that doesn't work for abnormals where
> we _must_ coalesce.  Thus this patch ...
> 
> As said, it's simple to keep the checking with ENABLE_CHECKING (I wonder
> if we should make some of the checking we do a runtime choice rather
> than a compile-time one...).  I'll update the patch.

Ok, like the following which adds a verify_ssa_coalescing () function
(which could in theory be called from IL verification like verify_ssa)
and calls it when ENABLE_CHECKING is defined.

Bootstrap & regtest running on x86_64-unknown-linux-gnu.

It didn't look appropriate for this stage to implement virtual operand
verification.

Ok this way?

Thanks,
Richard.

2015-03-06  Richard Biener  <rguenther@suse.de>

	PR middle-end/63155
	* tree-ssa-coalesce.h (verify_ssa_coalescing): Declare.
	* tree-ssa-coalesce.c (attempt_coalesce): Handle graph being NULL.
	(coalesce_partitions): Call verify_ssa_coalescing if ENABLE_CHECKING.
	Split out abnormal coalescing to ...
	(perform_abnormal_coalescing): ... this function.
	(coalesce_ssa_name): Perform abnormal coalescing without computing
	live/conflict.
	(verify_ssa_coalescing_worker): New function.
	(verify_ssa_coalescing): Likewise.

Index: gcc/tree-ssa-coalesce.c
===================================================================
*** gcc/tree-ssa-coalesce.c	(revision 221278)
--- gcc/tree-ssa-coalesce.c	(working copy)
*************** create_outofssa_var_map (coalesce_list_p
*** 1121,1128 ****
  
  
  /* Attempt to coalesce ssa versions X and Y together using the partition
!    mapping in MAP and checking conflicts in GRAPH.  Output any debug info to
!    DEBUG, if it is nun-NULL.  */
  
  static inline bool
  attempt_coalesce (var_map map, ssa_conflicts_p graph, int x, int y,
--- 1121,1128 ----
  
  
  /* Attempt to coalesce ssa versions X and Y together using the partition
!    mapping in MAP and checking conflicts in GRAPH if not NULL.
!    Output any debug info to DEBUG, if it is nun-NULL.  */
  
  static inline bool
  attempt_coalesce (var_map map, ssa_conflicts_p graph, int x, int y,
*************** attempt_coalesce (var_map map, ssa_confl
*** 1154,1160 ****
      fprintf (debug, " [map: %d, %d] ", p1, p2);
  
  
!   if (!ssa_conflicts_test_p (graph, p1, p2))
      {
        var1 = partition_to_var (map, p1);
        var2 = partition_to_var (map, p2);
--- 1154,1161 ----
      fprintf (debug, " [map: %d, %d] ", p1, p2);
  
  
!   if (!graph
!       || !ssa_conflicts_test_p (graph, p1, p2))
      {
        var1 = partition_to_var (map, p1);
        var2 = partition_to_var (map, p2);
*************** attempt_coalesce (var_map map, ssa_confl
*** 1168,1177 ****
  
        /* z is the new combined partition.  Remove the other partition from
  	 the list, and merge the conflicts.  */
!       if (z == p1)
! 	ssa_conflicts_merge (graph, p1, p2);
!       else
! 	ssa_conflicts_merge (graph, p2, p1);
  
        if (debug)
  	fprintf (debug, ": Success -> %d\n", z);
--- 1169,1181 ----
  
        /* z is the new combined partition.  Remove the other partition from
  	 the list, and merge the conflicts.  */
!       if (graph)
! 	{
! 	  if (z == p1)
! 	    ssa_conflicts_merge (graph, p1, p2);
! 	  else
! 	    ssa_conflicts_merge (graph, p2, p1);
! 	}
  
        if (debug)
  	fprintf (debug, ": Success -> %d\n", z);
*************** attempt_coalesce (var_map map, ssa_confl
*** 1185,1208 ****
  }
  
  
! /* Attempt to Coalesce partitions in MAP which occur in the list CL using
!    GRAPH.  Debug output is sent to DEBUG if it is non-NULL.  */
  
  static void
! coalesce_partitions (var_map map, ssa_conflicts_p graph, coalesce_list_p cl,
! 		     FILE *debug)
  {
-   int x = 0, y = 0;
-   tree var1, var2;
-   int cost;
    basic_block bb;
    edge e;
    edge_iterator ei;
  
-   /* First, coalesce all the copies across abnormal edges.  These are not placed
-      in the coalesce list because they do not need to be sorted, and simply
-      consume extra memory/compilation time in large programs.  */
- 
    FOR_EACH_BB_FN (bb, cfun)
      {
        FOR_EACH_EDGE (e, ei, bb->preds)
--- 1189,1204 ----
  }
  
  
! /* Perform all abnormal coalescing on MAP.
!    Debug output is sent to DEBUG if it is non-NULL.  */
  
  static void
! perform_abnormal_coalescing (var_map map, FILE *debug)
  {
    basic_block bb;
    edge e;
    edge_iterator ei;
  
    FOR_EACH_BB_FN (bb, cfun)
      {
        FOR_EACH_EDGE (e, ei, bb->preds)
*************** coalesce_partitions (var_map map, ssa_co
*** 1226,1236 ****
  		if (debug)
  		  fprintf (debug, "Abnormal coalesce: ");
  
! 		if (!attempt_coalesce (map, graph, v1, v2, debug))
  		  fail_abnormal_edge_coalesce (v1, v2);
  	      }
  	  }
      }
  
    /* Now process the items in the coalesce list.  */
  
--- 1222,1244 ----
  		if (debug)
  		  fprintf (debug, "Abnormal coalesce: ");
  
! 		if (!attempt_coalesce (map, NULL, v1, v2, debug))
  		  fail_abnormal_edge_coalesce (v1, v2);
  	      }
  	  }
      }
+ }
+ 
+ /* Attempt to Coalesce partitions in MAP which occur in the list CL using
+    GRAPH.  Debug output is sent to DEBUG if it is non-NULL.  */
+ 
+ static void
+ coalesce_partitions (var_map map, ssa_conflicts_p graph, coalesce_list_p cl,
+ 		     FILE *debug)
+ {
+   int x = 0, y = 0;
+   tree var1, var2;
+   int cost;
  
    /* Now process the items in the coalesce list.  */
  
*************** coalesce_ssa_name (void)
*** 1285,1290 ****
--- 1293,1303 ----
    var_map map;
    unsigned int i;
  
+ #ifdef ENABLE_CHECKING
+   /* Verify we can perform all must coalesces.  */
+   verify_ssa_coalescing ();
+ #endif
+ 
    cl = create_coalesce_list ();
    map = create_outofssa_var_map (cl, used_in_copies);
  
*************** coalesce_ssa_name (void)
*** 1341,1346 ****
--- 1354,1368 ----
        return map;
      }
  
+   /* First, coalesce all the copies across abnormal edges.  These are not placed
+      in the coalesce list because they do not need to be sorted, and simply
+      consume extra memory/compilation time in large programs.
+      Performing abnormal coalescing also needs no live/conflict computation
+      because it must succeed (but we lose checking that it indeed does).
+      Still for PR63155 this reduces memory usage from 10GB to zero.  */
+   perform_abnormal_coalescing (map,
+ 			       ((dump_flags & TDF_DETAILS) ? dump_file : NULL));
+ 
    if (dump_file && (dump_flags & TDF_DETAILS))
      dump_var_map (dump_file, map);
  
*************** coalesce_ssa_name (void)
*** 1371,1381 ****
  
    /* Now coalesce everything in the list.  */
    coalesce_partitions (map, graph, cl,
! 		       ((dump_flags & TDF_DETAILS) ? dump_file
! 						   : NULL));
  
    delete_coalesce_list (cl);
    ssa_conflicts_delete (graph);
  
    return map;
  }
--- 1393,1493 ----
  
    /* Now coalesce everything in the list.  */
    coalesce_partitions (map, graph, cl,
! 		       ((dump_flags & TDF_DETAILS) ? dump_file : NULL));
  
    delete_coalesce_list (cl);
    ssa_conflicts_delete (graph);
  
    return map;
  }
+ 
+ 
+ /* Helper for verify_ssa_coalescing.  Operates in two modes:
+    1) scan the function for coalesces we must perform and store the
+       SSA names participating in USED_IN_COPIES
+    2) scan the function for coalesces and verify they can be performed
+       under the constraints of GRAPH updating MAP in the process
+    FIXME:  This can be extended to verify that the virtual operands
+    form a factored use-def chain (coalescing the active virtual use
+    with the virtual def at virtual def point).  */
+ 
+ static void
+ verify_ssa_coalescing_worker (bitmap used_in_copies,
+ 			      var_map map, ssa_conflicts_p graph)
+ {
+   basic_block bb;
+ 
+   FOR_EACH_BB_FN (bb, cfun)
+     {
+       edge e;
+       edge_iterator ei;
+ 
+       FOR_EACH_EDGE (e, ei, bb->preds)
+ 	if (e->flags & EDGE_ABNORMAL)
+ 	  {
+ 	    gphi_iterator gsi;
+ 	    for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
+ 		 gsi_next (&gsi))
+ 	      {
+ 		gphi *phi = gsi.phi ();
+ 		tree arg = PHI_ARG_DEF (phi, e->dest_idx);
+ 		if (SSA_NAME_IS_DEFAULT_DEF (arg)
+ 		    && (!SSA_NAME_VAR (arg)
+ 			|| TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL))
+ 		  continue;
+ 
+ 		tree res = PHI_RESULT (phi);
+ 
+ 		if (used_in_copies)
+ 		  {
+ 		    int v1 = SSA_NAME_VERSION (res);
+ 		    int v2 = SSA_NAME_VERSION (arg);
+ 		    bitmap_set_bit (used_in_copies, v1);
+ 		    bitmap_set_bit (used_in_copies, v2);
+ 		  }
+ 		else
+ 		  {
+ 		    int p1 = var_to_partition (map, res);
+ 		    int p2 = var_to_partition (map, arg);
+ 		    if (p1 != p2)
+ 		      {
+ 			if (ssa_conflicts_test_p (graph, p1, p2))
+ 			  error ("Overlapping life-ranges for SSA names");
+ 			int z = var_union (map,
+ 					   partition_to_var (map, p1),
+ 					   partition_to_var (map, p2));
+ 			if (z == p1)
+ 			  ssa_conflicts_merge (graph, p1, p2);
+ 			else
+ 			  ssa_conflicts_merge (graph, p2, p1);
+ 		      }
+ 		  }
+ 	      }
+ 	  }
+     }
+ }
+ 
+ /* Verify that we can coalesce SSA names we must coalesce.  */
+ 
+ DEBUG_FUNCTION void
+ verify_ssa_coalescing (void)
+ {
+   timevar_push (TV_TREE_SSA_VERIFY);
+   bitmap used_in_copies = BITMAP_ALLOC (NULL);
+   verify_ssa_coalescing_worker (used_in_copies, NULL, NULL);
+   if (bitmap_empty_p (used_in_copies))
+     {
+       BITMAP_FREE (used_in_copies);
+       return;
+     }
+   var_map map = init_var_map (bitmap_last_set_bit (used_in_copies) + 1);
+   partition_view_bitmap (map, used_in_copies, true);
+   BITMAP_FREE (used_in_copies);
+   tree_live_info_p liveinfo = calculate_live_ranges (map, false);
+   ssa_conflicts_p graph = build_ssa_conflict_graph (liveinfo);
+   delete_tree_live_info (liveinfo);
+   verify_ssa_coalescing_worker (NULL, map, graph);
+   ssa_conflicts_delete (graph);
+   delete_var_map (map);
+   timevar_pop (TV_TREE_SSA_VERIFY);
+ }
Index: gcc/tree-ssa-coalesce.h
===================================================================
*** gcc/tree-ssa-coalesce.h	(revision 221278)
--- gcc/tree-ssa-coalesce.h	(working copy)
*************** along with GCC; see the file COPYING3.
*** 21,25 ****
--- 21,26 ----
  #define GCC_TREE_SSA_COALESCE_H
  
  extern var_map coalesce_ssa_name (void);
+ extern void verify_ssa_coalescing (void);
  
  #endif /* GCC_TREE_SSA_COALESCE_H */