From a563c2869215ff2581159dc8fa429d8b969477e6 Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Tue, 10 Mar 2015 11:16:33 +0000 Subject: [PATCH] re PR middle-end/63155 (memory hog) 2015-03-10 Richard Biener PR middle-end/63155 * tree-ssa-coalesce.h (verify_ssa_coalescing): Declare. * tree-ssa-coalesce.c: Include timevar.h. (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. From-SVN: r221318 --- gcc/ChangeLog | 14 ++++ gcc/tree-ssa-coalesce.c | 154 ++++++++++++++++++++++++++++++++++------ gcc/tree-ssa-coalesce.h | 1 + 3 files changed, 148 insertions(+), 21 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index d278f26f596..363d56f22a6 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,17 @@ +2015-03-10 Richard Biener + + PR middle-end/63155 + * tree-ssa-coalesce.h (verify_ssa_coalescing): Declare. + * tree-ssa-coalesce.c: Include timevar.h. + (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. + 2015-03-10 Georg-Johann Lay PR target/65296 diff --git a/gcc/tree-ssa-coalesce.c b/gcc/tree-ssa-coalesce.c index 1afeefef2ef..dd6b9c04f8b 100644 --- a/gcc/tree-ssa-coalesce.c +++ b/gcc/tree-ssa-coalesce.c @@ -59,6 +59,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-ssa-live.h" #include "tree-ssa-coalesce.h" #include "diagnostic-core.h" +#include "timevar.h" /* This set of routines implements a coalesce_list. This is an object which @@ -1121,8 +1122,8 @@ create_outofssa_var_map (coalesce_list_p cl, bitmap used_in_copy) /* 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. */ + 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, @@ -1154,7 +1155,8 @@ attempt_coalesce (var_map map, ssa_conflicts_p graph, int x, int y, fprintf (debug, " [map: %d, %d] ", p1, p2); - if (!ssa_conflicts_test_p (graph, p1, p2)) + if (!graph + || !ssa_conflicts_test_p (graph, p1, p2)) { var1 = partition_to_var (map, p1); var2 = partition_to_var (map, p2); @@ -1168,10 +1170,13 @@ attempt_coalesce (var_map map, ssa_conflicts_p graph, int x, int y, /* 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 (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); @@ -1185,24 +1190,16 @@ attempt_coalesce (var_map map, ssa_conflicts_p graph, int x, int y, } -/* 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. */ +/* Perform all abnormal coalescing on MAP. + 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) +perform_abnormal_coalescing (var_map map, 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) @@ -1226,11 +1223,23 @@ coalesce_partitions (var_map map, ssa_conflicts_p graph, coalesce_list_p cl, if (debug) fprintf (debug, "Abnormal coalesce: "); - if (!attempt_coalesce (map, graph, v1, v2, debug)) + 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. */ @@ -1285,6 +1294,11 @@ coalesce_ssa_name (void) 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); @@ -1341,6 +1355,15 @@ coalesce_ssa_name (void) 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); @@ -1371,11 +1394,100 @@ coalesce_ssa_name (void) /* Now coalesce everything in the list. */ coalesce_partitions (map, graph, cl, - ((dump_flags & TDF_DETAILS) ? dump_file - : NULL)); + ((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); + + int v1 = SSA_NAME_VERSION (res); + int v2 = SSA_NAME_VERSION (arg); + if (used_in_copies) + { + 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)) + fail_abnormal_edge_coalesce (v1, v2); + 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) +{ + auto_timevar tv (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 (num_ssa_names); + 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); +} diff --git a/gcc/tree-ssa-coalesce.h b/gcc/tree-ssa-coalesce.h index 99b188a3931..06c33bfc7ee 100644 --- a/gcc/tree-ssa-coalesce.h +++ b/gcc/tree-ssa-coalesce.h @@ -21,5 +21,6 @@ along with GCC; see the file COPYING3. If not see #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 */ -- 2.30.2