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 <rguent...@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 <rguent...@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 */
