[PATCH][RFC] Fix PR63155

[PATCH][RFC] Fix PR63155

[Richard Biener]

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.

Index: gcc/tree-ssa-coalesce.c
===================================================================
*** gcc/tree-ssa-coalesce.c	(revision 221237)
--- 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)
*** 1341,1346 ****
--- 1349,1363 ----
        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,1378 ****
  
    /* 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);
--- 1388,1394 ----
  
    /* 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);

Re: [PATCH][RFC] Fix PR63155

[Jeff Law]

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.

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.

Jeff

Re: [PATCH][RFC] Fix PR63155

[Richard Biener]

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.

Thanks,
Richard.

Re: [PATCH][RFC] Fix PR63155

[Richard Biener]

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 */

Re: [PATCH][RFC] Fix PR63155

[Jeff Law]

On 03/09/15 03:42, 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).
Yea, it's a class time/space tradeoff.  I guess it comes down to how 
much compile-time pain we'll take for reducing memory usage.

It may also be the case that some blocking factors are actually faster 
than doing everything at once, even for more common input graph sizes.

I actually ran into this when looking at the liveness computations for 
into-ssa eons ago.  We were computing liveness in parallel, but a 
blocking of 1 object is actually best:

https://gcc.gnu.org/ml/gcc-patches/2003-10/msg01301.html



Jeff

Re: [PATCH][RFC] Fix PR63155

[Jeff Law]

On 03/09/15 07:01, Richard Biener wrote:
>
> 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.
Looks good to me.

jeff

Re: [PATCH][RFC] Fix PR63155

[Alan Lawrence]

Following this patch (r221318), we're seeing what appears to be a miscompile of 
glibc on AArch64. This causes quite a bunch of tests to fail, segfaults etc., if 
LD_LIBRARY_PATH leads to a libc.so.6 built with that patch vs without (same 
glibc sources). We are still working on a reduced testcase, but this is proving 
difficult...

--Alan

Richard Biener wrote:
> 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 */
> 
> 

Re: [PATCH][RFC] Fix PR63155

[Richard Biener]

On March 18, 2015 4:59:30 PM GMT+01:00, Alan Lawrence <alan.lawrence@arm.com> wrote:
>Following this patch (r221318), we're seeing what appears to be a
>miscompile of 
>glibc on AArch64. This causes quite a bunch of tests to fail, segfaults
>etc., if 
>LD_LIBRARY_PATH leads to a libc.so.6 built with that patch vs without
>(same 
>glibc sources). We are still working on a reduced testcase, but this is
>proving 
>difficult...

The patch was supposed to end up in the very same code generation.  Thus it's enough to identify the problematic source file and send me preprocessed source and cc1 invocation so I can investigate with a cross.

Thanks,
Richard.

>--Alan
>
>Richard Biener wrote:
>> 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 */
>> 
>> 

Re: [PATCH][RFC] Fix PR63155

[Andrew Pinski]

On Wed, Mar 18, 2015 at 8:59 AM, Alan Lawrence <alan.lawrence@arm.com> wrote:
> Following this patch (r221318), we're seeing what appears to be a miscompile
> of glibc on AArch64. This causes quite a bunch of tests to fail, segfaults
> etc., if LD_LIBRARY_PATH leads to a libc.so.6 built with that patch vs
> without (same glibc sources). We are still working on a reduced testcase,
> but this is proving difficult...

I was just debugging the same issue.  From what I can tell vfprintf is
being miscompiled.
An example code which shows the issue but not self-contained yet as I
thought it was related to varargs but I suspect it is more related to
the computed gotos inside vprintf in glibc.
#include <stdarg.h>
#include <stdio.h>

int g(int a, va_list ap)
{
  int b;
  b = va_arg(ap, int);
  if (b != SECOND)
    __builtin_abort ();
  if (a != FIRST)
    __builtin_abort ();
  printf("first: %d.\n", a);
  printf("second: %d.\n", b);
}

int f(int a, ...)
{
  int b;
  va_list ap;
  va_start(ap, a);
  g(a, ap);
  va_end (ap);
  return 0;
}

int main(void)
{
  return f(2, FIRST, SECOND);
}
--- CUT ---
With the new glibc I get:
first: 4194304.
second: 1.

But with the old one I get :
first: 16.
second: 32.


Thanks,
Andrew Pinski


>
> --Alan
>
>
> Richard Biener wrote:
>>
>> 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 */
>>
>>
>
>

Re: [PATCH][RFC] Fix PR63155

[Richard Biener]

On Wed, 18 Mar 2015, Richard Biener wrote:

> On March 18, 2015 4:59:30 PM GMT+01:00, Alan Lawrence <alan.lawrence@arm.com> wrote:
> >Following this patch (r221318), we're seeing what appears to be a
> >miscompile of 
> >glibc on AArch64. This causes quite a bunch of tests to fail, segfaults
> >etc., if 
> >LD_LIBRARY_PATH leads to a libc.so.6 built with that patch vs without
> >(same 
> >glibc sources). We are still working on a reduced testcase, but this is
> >proving 
> >difficult...
> 
> The patch was supposed to end up in the very same code generation.  
> Thus it's enough to identify the problematic source file and send me 
> preprocessed source and cc1 invocation so I can investigate with a 
> cross.

Ok - I _think_ that live_track_process_def doesn't handle partitions
with more than one member.  It's too closely tied to SSA.

Thus the whole idea of iterating the coalescing doesn't work without
fixing that.  Like conservatively with

Index: gcc/tree-ssa-coalesce.c
===================================================================
--- gcc/tree-ssa-coalesce.c	(revision 221490)
+++ gcc/tree-ssa-coalesce.c	(working copy)
@@ -724,7 +724,10 @@ live_track_clear_var (live_track_p ptr,
   int p;
 
   p = var_to_partition (ptr->map, var);
-  if (p != NO_PARTITION)
+  if (p != NO_PARTITION
+      /* ???  If this partition has more than one member don't do anything.  */
+      && ptr->map->var_partition->elements[SSA_NAME_VERSION
+			  (partition_to_var (ptr->map, p))].class_count == 1)
     live_track_remove_partition (ptr, p);
 }
 
@@ -780,8 +783,11 @@ live_track_process_def (live_track_p ptr
   if (p == NO_PARTITION)
     return;
 
-  /* Clear the liveness bit.  */
-  live_track_remove_partition (ptr, p);
+  /* Clear the liveness bit.
+     ???  If this partition has more than one member we can't do that.  */
+  if (ptr->map->var_partition->elements[SSA_NAME_VERSION
+			  (partition_to_var (ptr->map, p))].class_count == 1)
+    live_track_remove_partition (ptr, p);
 
   /* If the bitmap isn't empty now, conflicts need to be added.  */
   root = basevar_index (ptr->map, p);
@@ -789,7 +795,8 @@ live_track_process_def (live_track_p ptr
     {
       b = ptr->live_base_partitions[root];
       EXECUTE_IF_SET_IN_BITMAP (b, 0, x, bi)
-        ssa_conflicts_add (graph, p, x);
+	if (x != (unsigned) p)
+	  ssa_conflicts_add (graph, p, x);
     }
 }
 

Does that fix it?

Given the issue I'll revert the patch.

Thanks,
Richard.

> Thanks,
> Richard.
> 
> >--Alan
> >
> >Richard Biener wrote:
> >> 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 */
> >> 
> >> 
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Jennifer Guild,
Dilip Upmanyu, Graham Norton HRB 21284 (AG Nuernberg)