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