Message ID | DB6PR0802MB250419B22C2EABF9A56798F5E7860@DB6PR0802MB2504.eurprd08.prod.outlook.com |
---|---|
State | New |
Headers | show |
Series | [1/6] Compute type mode and register class mapping | expand |
On Fri, May 4, 2018 at 6:23 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: > Hi, > Following Jeff's suggestion, I am now using existing tree-ssa-live.c and > tree-ssa-coalesce.c to compute register pressure, rather than inventing > another live range solver. > > The major change is to record region's basic blocks in var_map and use that > information in computation, rather than FOR_EACH_BB_FN. For now only loop > and function type regions are supported. The default one is function type > region which is used in out-of-ssa. Loop type region will be used in next > patch to compute information for a loop. > > Bootstrap and test on x86_64 and AArch64 ongoing. Any comments? I believe your changes to create_outofssa_var_map should be done differently by simply only calling it from the coalescing context and passing in the var_map rather than initializing it therein and returning it. This also means the coalesce_vars_p flag in the var_map structure looks somewhat out-of-place. That is, it looks you could do with many less changes if you refactored what calls what slightly? For example the extra arg to gimple_can_coalesce_p looks unneeded. Just as a note I do have a CFG helper pending that computes RPO order for SEME regions (attached). loops are SEME regions, so your RTYPE_SESE is somewhat odd - I guess RTYPE_LOOP exists only because of the convenience of passing in a loop * to the "constructor". I'd rather drop this region_type thing and always assume a SEME region - at least I didn't see anything in the patch that depends on any of the forms apart from the initial BB gathering. Thanks, Richard. > Thanks, > bin > 2018-04-27 Bin Cheng <bin.cheng@arm.com> > > * tree-outof-ssa.c (remove_ssa_form): Update use. > * tree-ssa-coalesce.c (build_ssa_conflict_graph): Support regional > coalesce. > (coalesce_with_default): Update comment. > (create_outofssa_var_map): Support regional coalesce. Rename to... > (create_var_map): ...this. > (coalesce_partitions): Support regional coalesce. > (gimple_can_coalesce_p, compute_optimized_partition_bases): Ditto. > (coalesce_ssa_name): Ditto. > * tree-ssa-coalesce.h (coalesce_ssa_name, gimple_can_coalesce_p): > Add parameter in declarations. > * tree-ssa-live.c (init_var_map, delete_var_map): Support regional > coalesce. > (new_tree_live_info, loe_visit_block, set_var_live_on_entry): Ditto. > (calculate_live_on_exit, verify_live_on_entry): Ditto. > * tree-ssa-live.h (enum region_type): New. > (struct _var_map): New fields. > (init_var_map): Add parameter in declaration. > (function_region_p, region_contains_p): New. > * tree-ssa-uncprop.c (uncprop_into_successor_phis): Update uses.
On Fri, May 11, 2018 at 1:53 PM, Richard Biener <richard.guenther@gmail.com> wrote: > On Fri, May 4, 2018 at 6:23 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: >> Hi, >> Following Jeff's suggestion, I am now using existing tree-ssa-live.c and >> tree-ssa-coalesce.c to compute register pressure, rather than inventing >> another live range solver. >> >> The major change is to record region's basic blocks in var_map and use that >> information in computation, rather than FOR_EACH_BB_FN. For now only loop >> and function type regions are supported. The default one is function type >> region which is used in out-of-ssa. Loop type region will be used in next >> patch to compute information for a loop. >> >> Bootstrap and test on x86_64 and AArch64 ongoing. Any comments? > > I believe your changes to create_outofssa_var_map should be done differently > by simply only calling it from the coalescing context and passing in the > var_map rather than initializing it therein and returning it. > > This also means the coalesce_vars_p flag in the var_map structure looks > somewhat out-of-place. That is, it looks you could do with many less > changes if you refactored what calls what slightly? For example > the extra arg to gimple_can_coalesce_p looks unneeded. > > Just as a note I do have a CFG helper pending that computes RPO order > for SEME regions (attached). loops are SEME regions, so your RTYPE_SESE > is somewhat odd - I guess RTYPE_LOOP exists only because of the > convenience of passing in a loop * to the "constructor". I'd rather > drop this region_type thing and always assume a SEME region - at least > I didn't see anything in the patch that depends on any of the forms > apart from the initial BB gathering. Hi Richard, Thanks for reviewing. I refactored tree-ssa-live.c and tree-ssa-coalesce.c following your comments. Basically I did following changes: 1) Remove region_type and only support loop region live range computation. Also I added one boolean field in var_map indicating whether we are computing loop region live range or out-of-ssa. 2) Refactored create_outofssa_var_map into create_coalesce_list_for_region and populate_coalesce_list_for_outofssa. Actually the original function name doesn't quite make sense because it has nothing to do with var_map. 3) Hoist init_var_map up in call stack. Now it's called by caller (out-of-ssa or live range) and the returned var_map is passed to coalesce_* stuff. 4) Move global functions to tree-outof-ssa.c and make them static. 5) Save/restore flag_tree_coalesce_vars in order to avoid updating checks on the flag. So how is this one? Patch attached. Thanks, bin 2018-05-15 Bin Cheng <bin.cheng@arm.com> * tree-outof-ssa.c (tree-ssa.h, tree-dfa.h): Include header files. (create_default_def, for_all_parms): Moved from tree-ssa-coalesce.c. (parm_default_def_partition_arg): Ditto. (set_parm_default_def_partition): Ditto. (get_parm_default_def_partitions): Ditto and make it static. (get_undefined_value_partitions): Ditto and make it static. (remove_ssa_form): Refactor call to init_var_map here. * tree-ssa-coalesce.c (build_ssa_conflict_graph): Support live range computation for loop region. (coalesce_partitions, compute_optimized_partition_bases): Ditto. (register_default_def): Delete. (for_all_parms, create_default_def): Move to tree-outof-ssa.c. (parm_default_def_partition_arg): Ditto. (set_parm_default_def_partition): Ditto. (get_parm_default_def_partitions): Ditto and make it static. (get_undefined_value_partitions): Ditto and make it static. (coalesce_with_default, coalesce_with_default): Update comment. (create_coalesce_list_for_region): New func factored out from create_outofssa_var_map. (populate_coalesce_list_for_outofssa): New func factored out from create_outofssa_var_map and coalesce_ssa_name. (create_outofssa_var_map): Delete. (coalesce_ssa_name): Refactor to support live range computation. * tree-ssa-coalesce.h (coalesce_ssa_name): Change decl. (get_parm_default_def_partitions): Delete. (get_undefined_value_partitions): Ditto. * tree-ssa-live.c (init_var_map, delete_var_map): Support live range computation for loop region. (new_tree_live_info, loe_visit_block): Ditto. (live_worklist, set_var_live_on_entry): Ditto. (calculate_live_on_exit, verify_live_on_entry): Ditto. * tree-ssa-live.h (struct _var_map): New fields. (init_var_map): Change decl. (region_contains_p): New. From 1043540cd5325c65e60df25cad22c343e4312fd4 Mon Sep 17 00:00:00 2001 From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com> Date: Fri, 4 May 2018 09:39:17 +0100 Subject: [PATCH 4/6] liverange-support-region-20180504 --- gcc/tree-outof-ssa.c | 102 +++++++++++++++- gcc/tree-ssa-coalesce.c | 317 +++++++++++++++++------------------------------- gcc/tree-ssa-coalesce.h | 4 +- gcc/tree-ssa-live.c | 78 ++++++++---- gcc/tree-ssa-live.h | 30 ++++- 5 files changed, 298 insertions(+), 233 deletions(-) diff --git a/gcc/tree-outof-ssa.c b/gcc/tree-outof-ssa.c index 59bdcd6..3f880ef 100644 --- a/gcc/tree-outof-ssa.c +++ b/gcc/tree-outof-ssa.c @@ -27,10 +27,12 @@ along with GCC; see the file COPYING3. If not see #include "gimple.h" #include "cfghooks.h" #include "ssa.h" +#include "tree-ssa.h" #include "memmodel.h" #include "emit-rtl.h" #include "gimple-pretty-print.h" #include "diagnostic-core.h" +#include "tree-dfa.h" #include "stor-layout.h" #include "cfgrtl.h" #include "cfganal.h" @@ -888,6 +890,102 @@ rewrite_trees (var_map map) } } +/* Create a default def for VAR. */ + +static void +create_default_def (tree var, void *arg ATTRIBUTE_UNUSED) +{ + if (!is_gimple_reg (var)) + return; + + tree ssa = get_or_create_ssa_default_def (cfun, var); + gcc_assert (ssa); +} + +/* Call CALLBACK for all PARM_DECLs and RESULT_DECLs for which + assign_parms may ask for a default partition. */ + +static void +for_all_parms (void (*callback)(tree var, void *arg), void *arg) +{ + for (tree var = DECL_ARGUMENTS (current_function_decl); var; + var = DECL_CHAIN (var)) + callback (var, arg); + if (!VOID_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl)))) + callback (DECL_RESULT (current_function_decl), arg); + if (cfun->static_chain_decl) + callback (cfun->static_chain_decl, arg); +} + +/* We need to pass two arguments to set_parm_default_def_partition, + but for_all_parms only supports one. Use a pair. */ + +typedef std::pair<var_map, bitmap> parm_default_def_partition_arg; + +/* Set in ARG's PARTS bitmap the bit corresponding to the partition in + ARG's MAP containing VAR's default def. */ + +static void +set_parm_default_def_partition (tree var, void *arg_) +{ + parm_default_def_partition_arg *arg = (parm_default_def_partition_arg *)arg_; + var_map map = arg->first; + bitmap parts = arg->second; + + if (!is_gimple_reg (var)) + return; + + tree ssa = ssa_default_def (cfun, var); + gcc_assert (ssa); + + int version = var_to_partition (map, ssa); + gcc_assert (version != NO_PARTITION); + + bool changed = bitmap_set_bit (parts, version); + gcc_assert (changed); +} + +/* Allocate and return a bitmap that has a bit set for each partition + that contains a default def for a parameter. */ + +static bitmap +get_parm_default_def_partitions (var_map map) +{ + bitmap parm_default_def_parts = BITMAP_ALLOC (NULL); + + parm_default_def_partition_arg + arg = std::make_pair (map, parm_default_def_parts); + + for_all_parms (set_parm_default_def_partition, &arg); + + return parm_default_def_parts; +} + +/* Allocate and return a bitmap that has a bit set for each partition + that contains an undefined value. */ + +static bitmap +get_undefined_value_partitions (var_map map) +{ + bitmap undefined_value_parts = BITMAP_ALLOC (NULL); + + for (unsigned int i = 1; i < num_ssa_names; i++) + { + tree var = ssa_name (i); + if (var + && !virtual_operand_p (var) + && !has_zero_uses (var) + && ssa_undefined_value_p (var)) + { + const int p = var_to_partition (map, var); + if (p != NO_PARTITION) + bitmap_set_bit (undefined_value_parts, p); + } + } + + return undefined_value_parts; +} + /* Given the out-of-ssa info object SA (with prepared partitions) eliminate all phi nodes in all basic blocks. Afterwards no basic block will have phi nodes anymore and there are possibly @@ -945,7 +1043,9 @@ remove_ssa_form (bool perform_ter, struct ssaexpand *sa) bitmap values = NULL; var_map map; - map = coalesce_ssa_name (); + for_all_parms (create_default_def, NULL); + map = init_var_map (num_ssa_names); + coalesce_ssa_name (map); /* Return to viewing the variable list as just all reference variables after coalescing has been performed. */ diff --git a/gcc/tree-ssa-coalesce.c b/gcc/tree-ssa-coalesce.c index 5cc0aca..d0773fd 100644 --- a/gcc/tree-ssa-coalesce.c +++ b/gcc/tree-ssa-coalesce.c @@ -879,7 +879,7 @@ build_ssa_conflict_graph (tree_live_info_p liveinfo) live = new_live_track (map); - FOR_EACH_BB_FN (bb, cfun) + for (unsigned i = 0; liveinfo->map->vec_bbs->iterate (i, &bb); ++i) { /* Start with live on exit temporaries. */ live_track_init (live, live_on_exit (liveinfo, bb)); @@ -944,6 +944,8 @@ build_ssa_conflict_graph (tree_live_info_p liveinfo) { gphi *phi = gsi.phi (); tree result = PHI_RESULT (phi); + if (virtual_operand_p (result)) + continue; if (live_track_live_p (live, result)) live_track_process_def (live, result, graph); } @@ -1012,48 +1014,9 @@ fail_abnormal_edge_coalesce (int x, int y) internal_error ("SSA corruption"); } -/* Call CALLBACK for all PARM_DECLs and RESULT_DECLs for which - assign_parms may ask for a default partition. */ - -static void -for_all_parms (void (*callback)(tree var, void *arg), void *arg) -{ - for (tree var = DECL_ARGUMENTS (current_function_decl); var; - var = DECL_CHAIN (var)) - callback (var, arg); - if (!VOID_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl)))) - callback (DECL_RESULT (current_function_decl), arg); - if (cfun->static_chain_decl) - callback (cfun->static_chain_decl, arg); -} - -/* Create a default def for VAR. */ - -static void -create_default_def (tree var, void *arg ATTRIBUTE_UNUSED) -{ - if (!is_gimple_reg (var)) - return; - - tree ssa = get_or_create_ssa_default_def (cfun, var); - gcc_assert (ssa); -} - -/* Register VAR's default def in MAP. */ - -static void -register_default_def (tree var, void *arg ATTRIBUTE_UNUSED) -{ - if (!is_gimple_reg (var)) - return; - - tree ssa = ssa_default_def (cfun, var); - gcc_assert (ssa); -} - /* If VAR is an SSA_NAME associated with a PARM_DECL or a RESULT_DECL, and the DECL's default def is unused (i.e., it was introduced by - create_default_def), mark VAR and the default def for + create_default_def for out-of-ssa), mark VAR and the default def for coalescing. */ static void @@ -1070,32 +1033,25 @@ coalesce_with_default (tree var, coalesce_list *cl, bitmap used_in_copy) add_cost_one_coalesce (cl, SSA_NAME_VERSION (ssa), SSA_NAME_VERSION (var)); bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var)); - /* Default defs will have their used_in_copy bits set at the end of - create_outofssa_var_map. */ + /* Default defs will have their used_in_copy bits set at the beginning of + populate_coalesce_list_for_outofssa. */ } -/* This function creates a var_map for the current function as well as creating - a coalesce list for use later in the out of ssa process. */ -static var_map -create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy) +/* Given var_map MAP for a region, this function creates and returns a coalesce + list as well as recording related ssa names in USED_IN_COPIES for use later + in the out-of-ssa or live range computation process. */ + +static coalesce_list * +create_coalesce_list_for_region (var_map map, bitmap used_in_copy) { gimple_stmt_iterator gsi; basic_block bb; - tree var; + coalesce_list *cl = create_coalesce_list (); gimple *stmt; - tree first; - var_map map; int v1, v2, cost; - unsigned i; - - for_all_parms (create_default_def, NULL); - - map = init_var_map (num_ssa_names); - - for_all_parms (register_default_def, NULL); - FOR_EACH_BB_FN (bb, cfun) + for (unsigned j = 0; map->vec_bbs->iterate (j, &bb); ++j) { tree arg; @@ -1110,6 +1066,8 @@ create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy) bool saw_copy = false; res = gimple_phi_result (phi); + if (virtual_operand_p (res)) + continue; ver = SSA_NAME_VERSION (res); /* Register ssa_names and coalesces between the args and the result @@ -1249,8 +1207,44 @@ create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy) } } - /* Now process result decls and live on entry variables for entry into - the coalesce list. */ + return cl; +} + + +/* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR. */ + +struct ssa_name_var_hash : nofree_ptr_hash <tree_node> +{ + static inline hashval_t hash (const tree_node *); + static inline int equal (const tree_node *, const tree_node *); +}; + +inline hashval_t +ssa_name_var_hash::hash (const_tree n) +{ + return DECL_UID (SSA_NAME_VAR (n)); +} + +inline int +ssa_name_var_hash::equal (const tree_node *n1, const tree_node *n2) +{ + return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2); +} + + +/* This function populates coalesce list CL as well as recording related ssa + names in USED_IN_COPIES for use later in the out-of-ssa process. */ + +static void +populate_coalesce_list_for_outofssa (coalesce_list *cl, bitmap used_in_copy) +{ + tree var; + tree first; + int v1, v2, cost; + unsigned i; + + /* Process result decls and live on entry variables for entry into the + coalesce list. */ first = NULL_TREE; FOR_EACH_SSA_NAME (i, var, cfun) { @@ -1285,7 +1279,46 @@ create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy) } } - return map; + /* If this optimization is disabled, we need to coalesce all the + names originating from the same SSA_NAME_VAR so debug info + remains undisturbed. */ + if (!flag_tree_coalesce_vars) + { + tree a; + hash_table<ssa_name_var_hash> ssa_name_hash (10); + + FOR_EACH_SSA_NAME (i, a, cfun) + { + if (SSA_NAME_VAR (a) + && !DECL_IGNORED_P (SSA_NAME_VAR (a)) + && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a) + || !VAR_P (SSA_NAME_VAR (a)))) + { + tree *slot = ssa_name_hash.find_slot (a, INSERT); + + if (!*slot) + *slot = a; + else + { + /* If the variable is a PARM_DECL or a RESULT_DECL, we + _require_ that all the names originating from it be + coalesced, because there must be a single partition + containing all the names so that it can be assigned + the canonical RTL location of the DECL safely. + If in_lto_p, a function could have been compiled + originally with optimizations and only the link + performed at -O0, so we can't actually require it. */ + const int cost + = (TREE_CODE (SSA_NAME_VAR (a)) == VAR_DECL || in_lto_p) + ? MUST_COALESCE_COST - 1 : MUST_COALESCE_COST; + add_coalesce (cl, SSA_NAME_VERSION (a), + SSA_NAME_VERSION (*slot), cost); + bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (a)); + bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (*slot)); + } + } + } + } } @@ -1384,13 +1417,15 @@ coalesce_partitions (var_map map, ssa_conflicts *graph, coalesce_list *cl, gsi_next (&gsi)) { gphi *phi = gsi.phi (); + tree res = PHI_RESULT (phi); + if (virtual_operand_p (res)) + continue; 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); @@ -1420,27 +1455,6 @@ coalesce_partitions (var_map map, ssa_conflicts *graph, coalesce_list *cl, } -/* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR. */ - -struct ssa_name_var_hash : nofree_ptr_hash <tree_node> -{ - static inline hashval_t hash (const tree_node *); - static inline int equal (const tree_node *, const tree_node *); -}; - -inline hashval_t -ssa_name_var_hash::hash (const_tree n) -{ - return DECL_UID (SSA_NAME_VAR (n)); -} - -inline int -ssa_name_var_hash::equal (const tree_node *n1, const tree_node *n2) -{ - return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2); -} - - /* Output partition map MAP with coalescing plan PART to file F. */ void @@ -1629,8 +1643,9 @@ compute_optimized_partition_bases (var_map map, bitmap used_in_copies, /* And also with abnormal edges. */ basic_block bb; edge e; + unsigned i; edge_iterator ei; - FOR_EACH_BB_FN (bb, cfun) + for (i = 0; map->vec_bbs->iterate (i, &bb); ++i) { FOR_EACH_EDGE (e, ei, bb->preds) if (e->flags & EDGE_ABNORMAL) @@ -1640,14 +1655,15 @@ compute_optimized_partition_bases (var_map map, bitmap used_in_copies, gsi_next (&gsi)) { gphi *phi = gsi.phi (); + tree res = PHI_RESULT (phi); + if (virtual_operand_p (res)) + continue; 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 p1 = partition_find (tentative, var_to_partition (map, res)); int p2 = partition_find (tentative, var_to_partition (map, arg)); @@ -1675,7 +1691,6 @@ compute_optimized_partition_bases (var_map map, bitmap used_in_copies, between all SSA versions that ended up in the same potential coalesce partition. */ bitmap_iterator bi; - unsigned i; EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi) { int pidx = var_to_partition (map, ssa_name (i)); @@ -1784,62 +1799,22 @@ compute_samebase_partition_bases (var_map map) free (mapstorage); } -/* Reduce the number of copies by coalescing variables in the function. Return - a partition map with the resulting coalesces. */ +/* Given an initial var_map MAP, coalesce variables and return a partition map + with the resulting coalesce. Note that this function is called in either + live range computation context or out-of-ssa context, indicated by MAP. */ -extern var_map -coalesce_ssa_name (void) +extern void +coalesce_ssa_name (var_map map) { tree_live_info_p liveinfo; ssa_conflicts *graph; coalesce_list *cl; auto_bitmap used_in_copies; - var_map map; - unsigned int i; - tree a; - cl = create_coalesce_list (); - map = create_outofssa_var_map (cl, used_in_copies); + cl = create_coalesce_list_for_region (map, used_in_copies); + if (map->outofssa_p) + populate_coalesce_list_for_outofssa (cl, used_in_copies); - /* If this optimization is disabled, we need to coalesce all the - names originating from the same SSA_NAME_VAR so debug info - remains undisturbed. */ - if (!flag_tree_coalesce_vars) - { - hash_table<ssa_name_var_hash> ssa_name_hash (10); - - FOR_EACH_SSA_NAME (i, a, cfun) - { - if (SSA_NAME_VAR (a) - && !DECL_IGNORED_P (SSA_NAME_VAR (a)) - && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a) - || !VAR_P (SSA_NAME_VAR (a)))) - { - tree *slot = ssa_name_hash.find_slot (a, INSERT); - - if (!*slot) - *slot = a; - else - { - /* If the variable is a PARM_DECL or a RESULT_DECL, we - _require_ that all the names originating from it be - coalesced, because there must be a single partition - containing all the names so that it can be assigned - the canonical RTL location of the DECL safely. - If in_lto_p, a function could have been compiled - originally with optimizations and only the link - performed at -O0, so we can't actually require it. */ - const int cost - = (TREE_CODE (SSA_NAME_VAR (a)) == VAR_DECL || in_lto_p) - ? MUST_COALESCE_COST - 1 : MUST_COALESCE_COST; - add_coalesce (cl, SSA_NAME_VERSION (a), - SSA_NAME_VERSION (*slot), cost); - bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (a)); - bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (*slot)); - } - } - } - } if (dump_file && (dump_flags & TDF_DETAILS)) dump_var_map (dump_file, map); @@ -1853,7 +1828,7 @@ coalesce_ssa_name (void) if (num_var_partitions (map) < 1) { delete_coalesce_list (cl); - return map; + return; } if (dump_file && (dump_flags & TDF_DETAILS)) @@ -1890,75 +1865,5 @@ coalesce_ssa_name (void) delete_coalesce_list (cl); ssa_conflicts_delete (graph); - - return map; } -/* We need to pass two arguments to set_parm_default_def_partition, - but for_all_parms only supports one. Use a pair. */ - -typedef std::pair<var_map, bitmap> parm_default_def_partition_arg; - -/* Set in ARG's PARTS bitmap the bit corresponding to the partition in - ARG's MAP containing VAR's default def. */ - -static void -set_parm_default_def_partition (tree var, void *arg_) -{ - parm_default_def_partition_arg *arg = (parm_default_def_partition_arg *)arg_; - var_map map = arg->first; - bitmap parts = arg->second; - - if (!is_gimple_reg (var)) - return; - - tree ssa = ssa_default_def (cfun, var); - gcc_assert (ssa); - - int version = var_to_partition (map, ssa); - gcc_assert (version != NO_PARTITION); - - bool changed = bitmap_set_bit (parts, version); - gcc_assert (changed); -} - -/* Allocate and return a bitmap that has a bit set for each partition - that contains a default def for a parameter. */ - -bitmap -get_parm_default_def_partitions (var_map map) -{ - bitmap parm_default_def_parts = BITMAP_ALLOC (NULL); - - parm_default_def_partition_arg - arg = std::make_pair (map, parm_default_def_parts); - - for_all_parms (set_parm_default_def_partition, &arg); - - return parm_default_def_parts; -} - -/* Allocate and return a bitmap that has a bit set for each partition - that contains an undefined value. */ - -bitmap -get_undefined_value_partitions (var_map map) -{ - bitmap undefined_value_parts = BITMAP_ALLOC (NULL); - - for (unsigned int i = 1; i < num_ssa_names; i++) - { - tree var = ssa_name (i); - if (var - && !virtual_operand_p (var) - && !has_zero_uses (var) - && ssa_undefined_value_p (var)) - { - const int p = var_to_partition (map, var); - if (p != NO_PARTITION) - bitmap_set_bit (undefined_value_parts, p); - } - } - - return undefined_value_parts; -} diff --git a/gcc/tree-ssa-coalesce.h b/gcc/tree-ssa-coalesce.h index 89d8474..f787637 100644 --- a/gcc/tree-ssa-coalesce.h +++ b/gcc/tree-ssa-coalesce.h @@ -20,9 +20,7 @@ along with GCC; see the file COPYING3. If not see #ifndef GCC_TREE_SSA_COALESCE_H #define GCC_TREE_SSA_COALESCE_H -extern var_map coalesce_ssa_name (void); +extern void coalesce_ssa_name (var_map); extern bool gimple_can_coalesce_p (tree, tree); -extern bitmap get_parm_default_def_partitions (var_map); -extern bitmap get_undefined_value_partitions (var_map); #endif /* GCC_TREE_SSA_COALESCE_H */ diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c index 62316ba..c79e635 100644 --- a/gcc/tree-ssa-live.c +++ b/gcc/tree-ssa-live.c @@ -71,10 +71,12 @@ var_map_base_fini (var_map map) map->num_basevars = 0; } } -/* Create a variable partition map of SIZE, initialize and return it. */ +/* Create a variable partition map of SIZE for region, initialize and return + it. Region is a loop if LOOP is non-NULL, otherwise is the current + function. */ var_map -init_var_map (int size) +init_var_map (int size, struct loop *loop) { var_map map; @@ -87,6 +89,29 @@ init_var_map (int size) map->partition_size = size; map->num_basevars = 0; map->partition_to_base_index = NULL; + map->bmp_bbs = BITMAP_ALLOC (NULL); + map->vec_bbs = new vec<basic_block> (); + if (loop) + { + map->outofssa_p = false; + basic_block *bbs = get_loop_body_in_dom_order (loop); + for (unsigned i = 0; i < loop->num_nodes; ++i) + { + bitmap_set_bit (map->bmp_bbs, bbs[i]->index); + map->vec_bbs->safe_push (bbs[i]); + } + free (bbs); + } + else + { + map->outofssa_p = true; + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + { + bitmap_set_bit (map->bmp_bbs, bb->index); + map->vec_bbs->safe_push (bb); + } + } return map; } @@ -100,6 +125,9 @@ delete_var_map (var_map map) partition_delete (map->var_partition); free (map->partition_to_view); free (map->view_to_partition); + BITMAP_FREE (map->bmp_bbs); + map->vec_bbs->release (); + delete map->vec_bbs; free (map); } @@ -901,13 +929,14 @@ new_tree_live_info (var_map map) bitmap_obstack_initialize (&live->livein_obstack); bitmap_obstack_initialize (&live->liveout_obstack); - live->livein = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun)); - FOR_EACH_BB_FN (bb, cfun) - bitmap_initialize (&live->livein[bb->index], &live->livein_obstack); - live->liveout = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun)); - FOR_EACH_BB_FN (bb, cfun) - bitmap_initialize (&live->liveout[bb->index], &live->liveout_obstack); + live->livein = XCNEWVEC (bitmap_head, last_basic_block_for_fn (cfun)); + live->liveout = XCNEWVEC (bitmap_head, last_basic_block_for_fn (cfun)); + for (unsigned i = 0; map->vec_bbs->iterate (i, &bb); ++i) + { + bitmap_initialize (&live->livein[bb->index], &live->livein_obstack); + bitmap_initialize (&live->liveout[bb->index], &live->liveout_obstack); + } live->work_stack = XNEWVEC (int, last_basic_block_for_fn (cfun)); live->stack_top = live->work_stack; @@ -960,7 +989,7 @@ loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited) FOR_EACH_EDGE (e, ei, bb->preds) { pred_bb = e->src; - if (pred_bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)) + if (!region_contains_p (live->map, pred_bb)) continue; /* Variables live-on-entry from BB that aren't defined in the predecessor block. This should be the live on entry vars to pred. @@ -993,9 +1022,10 @@ live_worklist (tree_live_info_p live) bitmap_clear (visited); - /* Visit all the blocks in reverse order and propagate live on entry values + /* Visit region's blocks in reverse order and propagate live on entry values into the predecessors blocks. */ - FOR_EACH_BB_REVERSE_FN (bb, cfun) + for (unsigned i = live->map->vec_bbs->length () - 1; + live->map->vec_bbs->iterate (i, &bb); --i) loe_visit_block (live, bb, visited); /* Process any blocks which require further iteration. */ @@ -1030,7 +1060,7 @@ set_var_live_on_entry (tree ssa_name, tree_live_info_p live) { def_bb = gimple_bb (stmt); /* Mark defs in liveout bitmap temporarily. */ - if (def_bb) + if (def_bb && region_contains_p (live->map, def_bb)) bitmap_set_bit (&live->liveout[def_bb->index], p); } else @@ -1054,11 +1084,8 @@ set_var_live_on_entry (tree ssa_name, tree_live_info_p live) defined in that block, or whether its live on entry. */ int index = PHI_ARG_INDEX_FROM_USE (use); edge e = gimple_phi_arg_edge (as_a <gphi *> (use_stmt), index); - if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)) - { - if (e->src != def_bb) - add_block = e->src; - } + if (e->src != def_bb && region_contains_p (live->map, e->src)) + add_block = e->src; } else if (is_gimple_debug (use_stmt)) continue; @@ -1066,7 +1093,7 @@ set_var_live_on_entry (tree ssa_name, tree_live_info_p live) { /* If its not defined in this block, its live on entry. */ basic_block use_bb = gimple_bb (use_stmt); - if (use_bb != def_bb) + if (use_bb != def_bb && region_contains_p (live->map, use_bb)) add_block = use_bb; } @@ -1095,7 +1122,7 @@ calculate_live_on_exit (tree_live_info_p liveinfo) edge_iterator ei; /* live on entry calculations used liveout vectors for defs, clear them. */ - FOR_EACH_BB_FN (bb, cfun) + for (unsigned i = 0; liveinfo->map->vec_bbs->iterate (i, &bb); ++i) bitmap_clear (&liveinfo->liveout[bb->index]); /* Set all the live-on-exit bits for uses in PHIs. */ @@ -1108,6 +1135,8 @@ calculate_live_on_exit (tree_live_info_p liveinfo) for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { gphi *phi = gsi.phi (); + if (virtual_operand_p (gimple_phi_result (phi))) + continue; for (i = 0; i < gimple_phi_num_args (phi); i++) { tree t = PHI_ARG_DEF (phi, i); @@ -1120,14 +1149,17 @@ calculate_live_on_exit (tree_live_info_p liveinfo) if (p == NO_PARTITION) continue; e = gimple_phi_arg_edge (phi, i); - if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)) + if (region_contains_p (liveinfo->map, e->src)) bitmap_set_bit (&liveinfo->liveout[e->src->index], p); } } + if (!region_contains_p (liveinfo->map, bb)) + continue; + /* Add each successors live on entry to this bock live on exit. */ FOR_EACH_EDGE (e, ei, bb->succs) - if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) + if (region_contains_p (liveinfo->map, e->dest)) bitmap_ior_into (&liveinfo->liveout[bb->index], live_on_entry (liveinfo, e->dest)); } @@ -1314,7 +1346,7 @@ verify_live_on_entry (tree_live_info_p live) FOR_EACH_EDGE (e, ei, bb->succs) { int entry_block = e->dest->index; - if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) + if (!region_contains_p (live->map, e->dest)) continue; for (i = 0; i < (unsigned)num_var_partitions (map); i++) { @@ -1380,6 +1412,8 @@ verify_live_on_entry (tree_live_info_p live) gsi_next (&gsi)) { gphi *phi = gsi.phi (); + if (virtual_operand_p (gimple_phi_result (phi))) + continue; for (z = 0; z < gimple_phi_num_args (phi); z++) if (var == gimple_phi_arg_def (phi, z)) { diff --git a/gcc/tree-ssa-live.h b/gcc/tree-ssa-live.h index 448aaf9..13aea90 100644 --- a/gcc/tree-ssa-live.h +++ b/gcc/tree-ssa-live.h @@ -62,13 +62,25 @@ typedef struct _var_map /* Map of partitions numbers to base variable table indexes. */ int *partition_to_base_index; + + /* Bitmap of basic block. It describes the region within which the analysis + is done. */ + bitmap bmp_bbs; + + /* Vector of basic block in the region. */ + vec<basic_block> *vec_bbs; + + /* True if this map is for out-of-ssa, otherwise for live range + computation. When for out-of-ssa, it also means the var map is computed + for whole current function. */ + bool outofssa_p; } *var_map; /* Value used to represent no partition number. */ #define NO_PARTITION -1 -extern var_map init_var_map (int); +extern var_map init_var_map (int, struct loop* = NULL); extern void delete_var_map (var_map); extern int var_union (var_map, tree, tree); extern void partition_view_normal (var_map); @@ -82,6 +94,22 @@ extern void debug (_var_map &ref); extern void debug (_var_map *ptr); +/* Return TRUE if region of the MAP contains basic block BB. */ + +inline bool +region_contains_p (var_map map, basic_block bb) +{ + if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) + || bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) + return false; + + if (map->outofssa_p) + return true; + + return bitmap_bit_p (map->bmp_bbs, bb->index); +} + + /* Return number of partitions in MAP. */ static inline unsigned
On Tue, May 15, 2018 at 5:44 PM Bin.Cheng <amker.cheng@gmail.com> wrote: > On Fri, May 11, 2018 at 1:53 PM, Richard Biener > <richard.guenther@gmail.com> wrote: > > On Fri, May 4, 2018 at 6:23 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: > >> Hi, > >> Following Jeff's suggestion, I am now using existing tree-ssa-live.c and > >> tree-ssa-coalesce.c to compute register pressure, rather than inventing > >> another live range solver. > >> > >> The major change is to record region's basic blocks in var_map and use that > >> information in computation, rather than FOR_EACH_BB_FN. For now only loop > >> and function type regions are supported. The default one is function type > >> region which is used in out-of-ssa. Loop type region will be used in next > >> patch to compute information for a loop. > >> > >> Bootstrap and test on x86_64 and AArch64 ongoing. Any comments? > > > > I believe your changes to create_outofssa_var_map should be done differently > > by simply only calling it from the coalescing context and passing in the > > var_map rather than initializing it therein and returning it. > > > > This also means the coalesce_vars_p flag in the var_map structure looks > > somewhat out-of-place. That is, it looks you could do with many less > > changes if you refactored what calls what slightly? For example > > the extra arg to gimple_can_coalesce_p looks unneeded. > > > > Just as a note I do have a CFG helper pending that computes RPO order > > for SEME regions (attached). loops are SEME regions, so your RTYPE_SESE > > is somewhat odd - I guess RTYPE_LOOP exists only because of the > > convenience of passing in a loop * to the "constructor". I'd rather > > drop this region_type thing and always assume a SEME region - at least > > I didn't see anything in the patch that depends on any of the forms > > apart from the initial BB gathering. > Hi Richard, > Thanks for reviewing. I refactored tree-ssa-live.c and > tree-ssa-coalesce.c following your comments. > Basically I did following changes: > 1) Remove region_type and only support loop region live range computation. > Also I added one boolean field in var_map indicating whether we > are computing > loop region live range or out-of-ssa. > 2) Refactored create_outofssa_var_map into create_coalesce_list_for_region and > populate_coalesce_list_for_outofssa. Actually the original > function name doesn't > quite make sense because it has nothing to do with var_map. > 3) Hoist init_var_map up in call stack. Now it's called by caller > (out-of-ssa or live range) > and the returned var_map is passed to coalesce_* stuff. > 4) Move global functions to tree-outof-ssa.c and make them static. > 5) Save/restore flag_tree_coalesce_vars in order to avoid updating > checks on the flag. > So how is this one? Patch attached. A lot better. Few things I noticed: + map->bmp_bbs = BITMAP_ALLOC (NULL); use a bitmap_head member and bitmap_initialize (). + map->vec_bbs = new vec<basic_block> (); use a vec<> member and map->vec_bbs = vNULL; Both changes remove an unnecessary indirection. + map->outofssa_p = true; + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + { + bitmap_set_bit (map->bmp_bbs, bb->index); + map->vec_bbs->safe_push (bb); + } I think you can avoid populating the bitmap and return true unconditionally for outofssa_p in the contains function? Ah, you already do - so why populate the bitmap? +/* Return TRUE if region of the MAP contains basic block BB. */ + +inline bool +region_contains_p (var_map map, basic_block bb) +{ + if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) + || bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) + return false; + + if (map->outofssa_p) + return true; + + return bitmap_bit_p (map->bmp_bbs, bb->index); the entry/exit block check should be conditional in map->outofssa_p but I think we should never get the function called with those args so we can as well use a gcc_checking_assert ()? I think as followup we should try to get a BB order that is more suited for the dataflow problem. Btw, I was thinking about adding anoter "visited" BB flag that is guaranteed to be unset and free to be used by infrastructure. So the bitmap could be elided for a bb flag check (but we need to clear that flag at the end of processing). Not sure if it's worth to add a machinery to dynamically assign pass-specific flags... it would at least be less error prone. Sth to think about. So -- I think the patch is ok with the two indirections removed, the rest can be optimized as followup. Thanks, Richard. > Thanks, > bin > 2018-05-15 Bin Cheng <bin.cheng@arm.com> > * tree-outof-ssa.c (tree-ssa.h, tree-dfa.h): Include header files. > (create_default_def, for_all_parms): Moved from tree-ssa-coalesce.c. > (parm_default_def_partition_arg): Ditto. > (set_parm_default_def_partition): Ditto. > (get_parm_default_def_partitions): Ditto and make it static. > (get_undefined_value_partitions): Ditto and make it static. > (remove_ssa_form): Refactor call to init_var_map here. > * tree-ssa-coalesce.c (build_ssa_conflict_graph): Support live range > computation for loop region. > (coalesce_partitions, compute_optimized_partition_bases): Ditto. > (register_default_def): Delete. > (for_all_parms, create_default_def): Move to tree-outof-ssa.c. > (parm_default_def_partition_arg): Ditto. > (set_parm_default_def_partition): Ditto. > (get_parm_default_def_partitions): Ditto and make it static. > (get_undefined_value_partitions): Ditto and make it static. > (coalesce_with_default, coalesce_with_default): Update comment. > (create_coalesce_list_for_region): New func factored out from > create_outofssa_var_map. > (populate_coalesce_list_for_outofssa): New func factored out from > create_outofssa_var_map and coalesce_ssa_name. > (create_outofssa_var_map): Delete. > (coalesce_ssa_name): Refactor to support live range computation. > * tree-ssa-coalesce.h (coalesce_ssa_name): Change decl. > (get_parm_default_def_partitions): Delete. > (get_undefined_value_partitions): Ditto. > * tree-ssa-live.c (init_var_map, delete_var_map): Support live range > computation for loop region. > (new_tree_live_info, loe_visit_block): Ditto. > (live_worklist, set_var_live_on_entry): Ditto. > (calculate_live_on_exit, verify_live_on_entry): Ditto. > * tree-ssa-live.h (struct _var_map): New fields. > (init_var_map): Change decl. > (region_contains_p): New.
On Thu, May 17, 2018 at 3:04 PM, Richard Biener <richard.guenther@gmail.com> wrote: > On Tue, May 15, 2018 at 5:44 PM Bin.Cheng <amker.cheng@gmail.com> wrote: > >> On Fri, May 11, 2018 at 1:53 PM, Richard Biener >> <richard.guenther@gmail.com> wrote: >> > On Fri, May 4, 2018 at 6:23 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: >> >> Hi, >> >> Following Jeff's suggestion, I am now using existing tree-ssa-live.c > and >> >> tree-ssa-coalesce.c to compute register pressure, rather than inventing >> >> another live range solver. >> >> >> >> The major change is to record region's basic blocks in var_map and use > that >> >> information in computation, rather than FOR_EACH_BB_FN. For now only > loop >> >> and function type regions are supported. The default one is function > type >> >> region which is used in out-of-ssa. Loop type region will be used in > next >> >> patch to compute information for a loop. >> >> >> >> Bootstrap and test on x86_64 and AArch64 ongoing. Any comments? >> > >> > I believe your changes to create_outofssa_var_map should be done > differently >> > by simply only calling it from the coalescing context and passing in the >> > var_map rather than initializing it therein and returning it. >> > >> > This also means the coalesce_vars_p flag in the var_map structure looks >> > somewhat out-of-place. That is, it looks you could do with many less >> > changes if you refactored what calls what slightly? For example >> > the extra arg to gimple_can_coalesce_p looks unneeded. >> > >> > Just as a note I do have a CFG helper pending that computes RPO order >> > for SEME regions (attached). loops are SEME regions, so your RTYPE_SESE >> > is somewhat odd - I guess RTYPE_LOOP exists only because of the >> > convenience of passing in a loop * to the "constructor". I'd rather >> > drop this region_type thing and always assume a SEME region - at least >> > I didn't see anything in the patch that depends on any of the forms >> > apart from the initial BB gathering. > >> Hi Richard, > >> Thanks for reviewing. I refactored tree-ssa-live.c and >> tree-ssa-coalesce.c following your comments. >> Basically I did following changes: >> 1) Remove region_type and only support loop region live range computation. >> Also I added one boolean field in var_map indicating whether we >> are computing >> loop region live range or out-of-ssa. >> 2) Refactored create_outofssa_var_map into > create_coalesce_list_for_region and >> populate_coalesce_list_for_outofssa. Actually the original >> function name doesn't >> quite make sense because it has nothing to do with var_map. >> 3) Hoist init_var_map up in call stack. Now it's called by caller >> (out-of-ssa or live range) >> and the returned var_map is passed to coalesce_* stuff. >> 4) Move global functions to tree-outof-ssa.c and make them static. >> 5) Save/restore flag_tree_coalesce_vars in order to avoid updating >> checks on the flag. > >> So how is this one? Patch attached. > > A lot better. Few things I noticed: > > + map->bmp_bbs = BITMAP_ALLOC (NULL); > > use a bitmap_head member and bitmap_initialize (). > > + map->vec_bbs = new vec<basic_block> (); > > use a vec<> member and map->vec_bbs = vNULL; > > Both changes remove an unnecessary indirection. > > + map->outofssa_p = true; > + basic_block bb; > + FOR_EACH_BB_FN (bb, cfun) > + { > + bitmap_set_bit (map->bmp_bbs, bb->index); > + map->vec_bbs->safe_push (bb); > + } > > I think you can avoid populating the bitmap and return > true unconditionally for outofssa_p in the contains function? > Ah, you already do - so why populate the bitmap? > > +/* Return TRUE if region of the MAP contains basic block BB. */ > + > +inline bool > +region_contains_p (var_map map, basic_block bb) > +{ > + if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) > + || bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) > + return false; > + > + if (map->outofssa_p) > + return true; > + > + return bitmap_bit_p (map->bmp_bbs, bb->index); > > the entry/exit block check should be conditional in map->outofssa_p > but I think we should never get the function called with those args > so we can as well use a gcc_checking_assert ()? > > I think as followup we should try to get a BB order that > is more suited for the dataflow problem. Btw, I was > thinking about adding anoter "visited" BB flag that is guaranteed to > be unset and free to be used by infrastructure. So the bitmap > could be elided for a bb flag check (but we need to clear that flag > at the end of processing). Not sure if it's worth to add a machinery > to dynamically assign pass-specific flags... it would at least be > less error prone. Sth to think about. > > So -- I think the patch is ok with the two indirections removed, > the rest can be optimized as followup. Hi, This is the updated patch. I moved checks on ENTRY/EXIT blocks under outofssa_p, as well as changed vec_bbs into object. Note bmp_bbs is kept in pointer so that we can avoid allocating memory in out-of-ssa case. Bootstrap and test ongoing. Is it OK? Thanks, bin > > Thanks, > Richard. > > >> Thanks, >> bin >> 2018-05-15 Bin Cheng <bin.cheng@arm.com> > >> * tree-outof-ssa.c (tree-ssa.h, tree-dfa.h): Include header files. >> (create_default_def, for_all_parms): Moved from tree-ssa-coalesce.c. >> (parm_default_def_partition_arg): Ditto. >> (set_parm_default_def_partition): Ditto. >> (get_parm_default_def_partitions): Ditto and make it static. >> (get_undefined_value_partitions): Ditto and make it static. >> (remove_ssa_form): Refactor call to init_var_map here. >> * tree-ssa-coalesce.c (build_ssa_conflict_graph): Support live range >> computation for loop region. >> (coalesce_partitions, compute_optimized_partition_bases): Ditto. >> (register_default_def): Delete. >> (for_all_parms, create_default_def): Move to tree-outof-ssa.c. >> (parm_default_def_partition_arg): Ditto. >> (set_parm_default_def_partition): Ditto. >> (get_parm_default_def_partitions): Ditto and make it static. >> (get_undefined_value_partitions): Ditto and make it static. >> (coalesce_with_default, coalesce_with_default): Update comment. >> (create_coalesce_list_for_region): New func factored out from >> create_outofssa_var_map. >> (populate_coalesce_list_for_outofssa): New func factored out from >> create_outofssa_var_map and coalesce_ssa_name. >> (create_outofssa_var_map): Delete. >> (coalesce_ssa_name): Refactor to support live range computation. >> * tree-ssa-coalesce.h (coalesce_ssa_name): Change decl. >> (get_parm_default_def_partitions): Delete. >> (get_undefined_value_partitions): Ditto. >> * tree-ssa-live.c (init_var_map, delete_var_map): Support live range >> computation for loop region. >> (new_tree_live_info, loe_visit_block): Ditto. >> (live_worklist, set_var_live_on_entry): Ditto. >> (calculate_live_on_exit, verify_live_on_entry): Ditto. >> * tree-ssa-live.h (struct _var_map): New fields. >> (init_var_map): Change decl. >> (region_contains_p): New. From e75498725921848330c9d2e7772da8b5c5b2dfe2 Mon Sep 17 00:00:00 2001 From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com> Date: Fri, 4 May 2018 09:39:17 +0100 Subject: [PATCH 4/6] liverange-support-region-20180515 --- gcc/tree-outof-ssa.c | 102 +++++++++++++++- gcc/tree-ssa-coalesce.c | 317 +++++++++++++++++------------------------------- gcc/tree-ssa-coalesce.h | 4 +- gcc/tree-ssa-live.c | 76 ++++++++---- gcc/tree-ssa-live.h | 27 ++++- 5 files changed, 293 insertions(+), 233 deletions(-) diff --git a/gcc/tree-outof-ssa.c b/gcc/tree-outof-ssa.c index 59bdcd6..3f880ef 100644 --- a/gcc/tree-outof-ssa.c +++ b/gcc/tree-outof-ssa.c @@ -27,10 +27,12 @@ along with GCC; see the file COPYING3. If not see #include "gimple.h" #include "cfghooks.h" #include "ssa.h" +#include "tree-ssa.h" #include "memmodel.h" #include "emit-rtl.h" #include "gimple-pretty-print.h" #include "diagnostic-core.h" +#include "tree-dfa.h" #include "stor-layout.h" #include "cfgrtl.h" #include "cfganal.h" @@ -888,6 +890,102 @@ rewrite_trees (var_map map) } } +/* Create a default def for VAR. */ + +static void +create_default_def (tree var, void *arg ATTRIBUTE_UNUSED) +{ + if (!is_gimple_reg (var)) + return; + + tree ssa = get_or_create_ssa_default_def (cfun, var); + gcc_assert (ssa); +} + +/* Call CALLBACK for all PARM_DECLs and RESULT_DECLs for which + assign_parms may ask for a default partition. */ + +static void +for_all_parms (void (*callback)(tree var, void *arg), void *arg) +{ + for (tree var = DECL_ARGUMENTS (current_function_decl); var; + var = DECL_CHAIN (var)) + callback (var, arg); + if (!VOID_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl)))) + callback (DECL_RESULT (current_function_decl), arg); + if (cfun->static_chain_decl) + callback (cfun->static_chain_decl, arg); +} + +/* We need to pass two arguments to set_parm_default_def_partition, + but for_all_parms only supports one. Use a pair. */ + +typedef std::pair<var_map, bitmap> parm_default_def_partition_arg; + +/* Set in ARG's PARTS bitmap the bit corresponding to the partition in + ARG's MAP containing VAR's default def. */ + +static void +set_parm_default_def_partition (tree var, void *arg_) +{ + parm_default_def_partition_arg *arg = (parm_default_def_partition_arg *)arg_; + var_map map = arg->first; + bitmap parts = arg->second; + + if (!is_gimple_reg (var)) + return; + + tree ssa = ssa_default_def (cfun, var); + gcc_assert (ssa); + + int version = var_to_partition (map, ssa); + gcc_assert (version != NO_PARTITION); + + bool changed = bitmap_set_bit (parts, version); + gcc_assert (changed); +} + +/* Allocate and return a bitmap that has a bit set for each partition + that contains a default def for a parameter. */ + +static bitmap +get_parm_default_def_partitions (var_map map) +{ + bitmap parm_default_def_parts = BITMAP_ALLOC (NULL); + + parm_default_def_partition_arg + arg = std::make_pair (map, parm_default_def_parts); + + for_all_parms (set_parm_default_def_partition, &arg); + + return parm_default_def_parts; +} + +/* Allocate and return a bitmap that has a bit set for each partition + that contains an undefined value. */ + +static bitmap +get_undefined_value_partitions (var_map map) +{ + bitmap undefined_value_parts = BITMAP_ALLOC (NULL); + + for (unsigned int i = 1; i < num_ssa_names; i++) + { + tree var = ssa_name (i); + if (var + && !virtual_operand_p (var) + && !has_zero_uses (var) + && ssa_undefined_value_p (var)) + { + const int p = var_to_partition (map, var); + if (p != NO_PARTITION) + bitmap_set_bit (undefined_value_parts, p); + } + } + + return undefined_value_parts; +} + /* Given the out-of-ssa info object SA (with prepared partitions) eliminate all phi nodes in all basic blocks. Afterwards no basic block will have phi nodes anymore and there are possibly @@ -945,7 +1043,9 @@ remove_ssa_form (bool perform_ter, struct ssaexpand *sa) bitmap values = NULL; var_map map; - map = coalesce_ssa_name (); + for_all_parms (create_default_def, NULL); + map = init_var_map (num_ssa_names); + coalesce_ssa_name (map); /* Return to viewing the variable list as just all reference variables after coalescing has been performed. */ diff --git a/gcc/tree-ssa-coalesce.c b/gcc/tree-ssa-coalesce.c index 5cc0aca..e4f576f 100644 --- a/gcc/tree-ssa-coalesce.c +++ b/gcc/tree-ssa-coalesce.c @@ -879,7 +879,7 @@ build_ssa_conflict_graph (tree_live_info_p liveinfo) live = new_live_track (map); - FOR_EACH_BB_FN (bb, cfun) + for (unsigned i = 0; liveinfo->map->vec_bbs.iterate (i, &bb); ++i) { /* Start with live on exit temporaries. */ live_track_init (live, live_on_exit (liveinfo, bb)); @@ -944,6 +944,8 @@ build_ssa_conflict_graph (tree_live_info_p liveinfo) { gphi *phi = gsi.phi (); tree result = PHI_RESULT (phi); + if (virtual_operand_p (result)) + continue; if (live_track_live_p (live, result)) live_track_process_def (live, result, graph); } @@ -1012,48 +1014,9 @@ fail_abnormal_edge_coalesce (int x, int y) internal_error ("SSA corruption"); } -/* Call CALLBACK for all PARM_DECLs and RESULT_DECLs for which - assign_parms may ask for a default partition. */ - -static void -for_all_parms (void (*callback)(tree var, void *arg), void *arg) -{ - for (tree var = DECL_ARGUMENTS (current_function_decl); var; - var = DECL_CHAIN (var)) - callback (var, arg); - if (!VOID_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl)))) - callback (DECL_RESULT (current_function_decl), arg); - if (cfun->static_chain_decl) - callback (cfun->static_chain_decl, arg); -} - -/* Create a default def for VAR. */ - -static void -create_default_def (tree var, void *arg ATTRIBUTE_UNUSED) -{ - if (!is_gimple_reg (var)) - return; - - tree ssa = get_or_create_ssa_default_def (cfun, var); - gcc_assert (ssa); -} - -/* Register VAR's default def in MAP. */ - -static void -register_default_def (tree var, void *arg ATTRIBUTE_UNUSED) -{ - if (!is_gimple_reg (var)) - return; - - tree ssa = ssa_default_def (cfun, var); - gcc_assert (ssa); -} - /* If VAR is an SSA_NAME associated with a PARM_DECL or a RESULT_DECL, and the DECL's default def is unused (i.e., it was introduced by - create_default_def), mark VAR and the default def for + create_default_def for out-of-ssa), mark VAR and the default def for coalescing. */ static void @@ -1070,32 +1033,25 @@ coalesce_with_default (tree var, coalesce_list *cl, bitmap used_in_copy) add_cost_one_coalesce (cl, SSA_NAME_VERSION (ssa), SSA_NAME_VERSION (var)); bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var)); - /* Default defs will have their used_in_copy bits set at the end of - create_outofssa_var_map. */ + /* Default defs will have their used_in_copy bits set at the beginning of + populate_coalesce_list_for_outofssa. */ } -/* This function creates a var_map for the current function as well as creating - a coalesce list for use later in the out of ssa process. */ -static var_map -create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy) +/* Given var_map MAP for a region, this function creates and returns a coalesce + list as well as recording related ssa names in USED_IN_COPIES for use later + in the out-of-ssa or live range computation process. */ + +static coalesce_list * +create_coalesce_list_for_region (var_map map, bitmap used_in_copy) { gimple_stmt_iterator gsi; basic_block bb; - tree var; + coalesce_list *cl = create_coalesce_list (); gimple *stmt; - tree first; - var_map map; int v1, v2, cost; - unsigned i; - - for_all_parms (create_default_def, NULL); - - map = init_var_map (num_ssa_names); - - for_all_parms (register_default_def, NULL); - FOR_EACH_BB_FN (bb, cfun) + for (unsigned j = 0; map->vec_bbs.iterate (j, &bb); ++j) { tree arg; @@ -1110,6 +1066,8 @@ create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy) bool saw_copy = false; res = gimple_phi_result (phi); + if (virtual_operand_p (res)) + continue; ver = SSA_NAME_VERSION (res); /* Register ssa_names and coalesces between the args and the result @@ -1249,8 +1207,44 @@ create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy) } } - /* Now process result decls and live on entry variables for entry into - the coalesce list. */ + return cl; +} + + +/* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR. */ + +struct ssa_name_var_hash : nofree_ptr_hash <tree_node> +{ + static inline hashval_t hash (const tree_node *); + static inline int equal (const tree_node *, const tree_node *); +}; + +inline hashval_t +ssa_name_var_hash::hash (const_tree n) +{ + return DECL_UID (SSA_NAME_VAR (n)); +} + +inline int +ssa_name_var_hash::equal (const tree_node *n1, const tree_node *n2) +{ + return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2); +} + + +/* This function populates coalesce list CL as well as recording related ssa + names in USED_IN_COPIES for use later in the out-of-ssa process. */ + +static void +populate_coalesce_list_for_outofssa (coalesce_list *cl, bitmap used_in_copy) +{ + tree var; + tree first; + int v1, v2, cost; + unsigned i; + + /* Process result decls and live on entry variables for entry into the + coalesce list. */ first = NULL_TREE; FOR_EACH_SSA_NAME (i, var, cfun) { @@ -1285,7 +1279,46 @@ create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy) } } - return map; + /* If this optimization is disabled, we need to coalesce all the + names originating from the same SSA_NAME_VAR so debug info + remains undisturbed. */ + if (!flag_tree_coalesce_vars) + { + tree a; + hash_table<ssa_name_var_hash> ssa_name_hash (10); + + FOR_EACH_SSA_NAME (i, a, cfun) + { + if (SSA_NAME_VAR (a) + && !DECL_IGNORED_P (SSA_NAME_VAR (a)) + && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a) + || !VAR_P (SSA_NAME_VAR (a)))) + { + tree *slot = ssa_name_hash.find_slot (a, INSERT); + + if (!*slot) + *slot = a; + else + { + /* If the variable is a PARM_DECL or a RESULT_DECL, we + _require_ that all the names originating from it be + coalesced, because there must be a single partition + containing all the names so that it can be assigned + the canonical RTL location of the DECL safely. + If in_lto_p, a function could have been compiled + originally with optimizations and only the link + performed at -O0, so we can't actually require it. */ + const int cost + = (TREE_CODE (SSA_NAME_VAR (a)) == VAR_DECL || in_lto_p) + ? MUST_COALESCE_COST - 1 : MUST_COALESCE_COST; + add_coalesce (cl, SSA_NAME_VERSION (a), + SSA_NAME_VERSION (*slot), cost); + bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (a)); + bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (*slot)); + } + } + } + } } @@ -1384,13 +1417,15 @@ coalesce_partitions (var_map map, ssa_conflicts *graph, coalesce_list *cl, gsi_next (&gsi)) { gphi *phi = gsi.phi (); + tree res = PHI_RESULT (phi); + if (virtual_operand_p (res)) + continue; 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); @@ -1420,27 +1455,6 @@ coalesce_partitions (var_map map, ssa_conflicts *graph, coalesce_list *cl, } -/* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR. */ - -struct ssa_name_var_hash : nofree_ptr_hash <tree_node> -{ - static inline hashval_t hash (const tree_node *); - static inline int equal (const tree_node *, const tree_node *); -}; - -inline hashval_t -ssa_name_var_hash::hash (const_tree n) -{ - return DECL_UID (SSA_NAME_VAR (n)); -} - -inline int -ssa_name_var_hash::equal (const tree_node *n1, const tree_node *n2) -{ - return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2); -} - - /* Output partition map MAP with coalescing plan PART to file F. */ void @@ -1629,8 +1643,9 @@ compute_optimized_partition_bases (var_map map, bitmap used_in_copies, /* And also with abnormal edges. */ basic_block bb; edge e; + unsigned i; edge_iterator ei; - FOR_EACH_BB_FN (bb, cfun) + for (i = 0; map->vec_bbs.iterate (i, &bb); ++i) { FOR_EACH_EDGE (e, ei, bb->preds) if (e->flags & EDGE_ABNORMAL) @@ -1640,14 +1655,15 @@ compute_optimized_partition_bases (var_map map, bitmap used_in_copies, gsi_next (&gsi)) { gphi *phi = gsi.phi (); + tree res = PHI_RESULT (phi); + if (virtual_operand_p (res)) + continue; 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 p1 = partition_find (tentative, var_to_partition (map, res)); int p2 = partition_find (tentative, var_to_partition (map, arg)); @@ -1675,7 +1691,6 @@ compute_optimized_partition_bases (var_map map, bitmap used_in_copies, between all SSA versions that ended up in the same potential coalesce partition. */ bitmap_iterator bi; - unsigned i; EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi) { int pidx = var_to_partition (map, ssa_name (i)); @@ -1784,62 +1799,22 @@ compute_samebase_partition_bases (var_map map) free (mapstorage); } -/* Reduce the number of copies by coalescing variables in the function. Return - a partition map with the resulting coalesces. */ +/* Given an initial var_map MAP, coalesce variables and return a partition map + with the resulting coalesce. Note that this function is called in either + live range computation context or out-of-ssa context, indicated by MAP. */ -extern var_map -coalesce_ssa_name (void) +extern void +coalesce_ssa_name (var_map map) { tree_live_info_p liveinfo; ssa_conflicts *graph; coalesce_list *cl; auto_bitmap used_in_copies; - var_map map; - unsigned int i; - tree a; - cl = create_coalesce_list (); - map = create_outofssa_var_map (cl, used_in_copies); + cl = create_coalesce_list_for_region (map, used_in_copies); + if (map->outofssa_p) + populate_coalesce_list_for_outofssa (cl, used_in_copies); - /* If this optimization is disabled, we need to coalesce all the - names originating from the same SSA_NAME_VAR so debug info - remains undisturbed. */ - if (!flag_tree_coalesce_vars) - { - hash_table<ssa_name_var_hash> ssa_name_hash (10); - - FOR_EACH_SSA_NAME (i, a, cfun) - { - if (SSA_NAME_VAR (a) - && !DECL_IGNORED_P (SSA_NAME_VAR (a)) - && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a) - || !VAR_P (SSA_NAME_VAR (a)))) - { - tree *slot = ssa_name_hash.find_slot (a, INSERT); - - if (!*slot) - *slot = a; - else - { - /* If the variable is a PARM_DECL or a RESULT_DECL, we - _require_ that all the names originating from it be - coalesced, because there must be a single partition - containing all the names so that it can be assigned - the canonical RTL location of the DECL safely. - If in_lto_p, a function could have been compiled - originally with optimizations and only the link - performed at -O0, so we can't actually require it. */ - const int cost - = (TREE_CODE (SSA_NAME_VAR (a)) == VAR_DECL || in_lto_p) - ? MUST_COALESCE_COST - 1 : MUST_COALESCE_COST; - add_coalesce (cl, SSA_NAME_VERSION (a), - SSA_NAME_VERSION (*slot), cost); - bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (a)); - bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (*slot)); - } - } - } - } if (dump_file && (dump_flags & TDF_DETAILS)) dump_var_map (dump_file, map); @@ -1853,7 +1828,7 @@ coalesce_ssa_name (void) if (num_var_partitions (map) < 1) { delete_coalesce_list (cl); - return map; + return; } if (dump_file && (dump_flags & TDF_DETAILS)) @@ -1890,75 +1865,5 @@ coalesce_ssa_name (void) delete_coalesce_list (cl); ssa_conflicts_delete (graph); - - return map; } -/* We need to pass two arguments to set_parm_default_def_partition, - but for_all_parms only supports one. Use a pair. */ - -typedef std::pair<var_map, bitmap> parm_default_def_partition_arg; - -/* Set in ARG's PARTS bitmap the bit corresponding to the partition in - ARG's MAP containing VAR's default def. */ - -static void -set_parm_default_def_partition (tree var, void *arg_) -{ - parm_default_def_partition_arg *arg = (parm_default_def_partition_arg *)arg_; - var_map map = arg->first; - bitmap parts = arg->second; - - if (!is_gimple_reg (var)) - return; - - tree ssa = ssa_default_def (cfun, var); - gcc_assert (ssa); - - int version = var_to_partition (map, ssa); - gcc_assert (version != NO_PARTITION); - - bool changed = bitmap_set_bit (parts, version); - gcc_assert (changed); -} - -/* Allocate and return a bitmap that has a bit set for each partition - that contains a default def for a parameter. */ - -bitmap -get_parm_default_def_partitions (var_map map) -{ - bitmap parm_default_def_parts = BITMAP_ALLOC (NULL); - - parm_default_def_partition_arg - arg = std::make_pair (map, parm_default_def_parts); - - for_all_parms (set_parm_default_def_partition, &arg); - - return parm_default_def_parts; -} - -/* Allocate and return a bitmap that has a bit set for each partition - that contains an undefined value. */ - -bitmap -get_undefined_value_partitions (var_map map) -{ - bitmap undefined_value_parts = BITMAP_ALLOC (NULL); - - for (unsigned int i = 1; i < num_ssa_names; i++) - { - tree var = ssa_name (i); - if (var - && !virtual_operand_p (var) - && !has_zero_uses (var) - && ssa_undefined_value_p (var)) - { - const int p = var_to_partition (map, var); - if (p != NO_PARTITION) - bitmap_set_bit (undefined_value_parts, p); - } - } - - return undefined_value_parts; -} diff --git a/gcc/tree-ssa-coalesce.h b/gcc/tree-ssa-coalesce.h index 89d8474..f787637 100644 --- a/gcc/tree-ssa-coalesce.h +++ b/gcc/tree-ssa-coalesce.h @@ -20,9 +20,7 @@ along with GCC; see the file COPYING3. If not see #ifndef GCC_TREE_SSA_COALESCE_H #define GCC_TREE_SSA_COALESCE_H -extern var_map coalesce_ssa_name (void); +extern void coalesce_ssa_name (var_map); extern bool gimple_can_coalesce_p (tree, tree); -extern bitmap get_parm_default_def_partitions (var_map); -extern bitmap get_undefined_value_partitions (var_map); #endif /* GCC_TREE_SSA_COALESCE_H */ diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c index 62316ba..7447f7a 100644 --- a/gcc/tree-ssa-live.c +++ b/gcc/tree-ssa-live.c @@ -71,10 +71,12 @@ var_map_base_fini (var_map map) map->num_basevars = 0; } } -/* Create a variable partition map of SIZE, initialize and return it. */ +/* Create a variable partition map of SIZE for region, initialize and return + it. Region is a loop if LOOP is non-NULL, otherwise is the current + function. */ var_map -init_var_map (int size) +init_var_map (int size, struct loop *loop) { var_map map; @@ -87,6 +89,27 @@ init_var_map (int size) map->partition_size = size; map->num_basevars = 0; map->partition_to_base_index = NULL; + map->vec_bbs = vNULL; + if (loop) + { + map->bmp_bbs = BITMAP_ALLOC (NULL); + map->outofssa_p = false; + basic_block *bbs = get_loop_body_in_dom_order (loop); + for (unsigned i = 0; i < loop->num_nodes; ++i) + { + bitmap_set_bit (map->bmp_bbs, bbs[i]->index); + map->vec_bbs.safe_push (bbs[i]); + } + free (bbs); + } + else + { + map->bmp_bbs = NULL; + map->outofssa_p = true; + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + map->vec_bbs.safe_push (bb); + } return map; } @@ -100,6 +123,9 @@ delete_var_map (var_map map) partition_delete (map->var_partition); free (map->partition_to_view); free (map->view_to_partition); + if (map->bmp_bbs) + BITMAP_FREE (map->bmp_bbs); + map->vec_bbs.release (); free (map); } @@ -901,13 +927,14 @@ new_tree_live_info (var_map map) bitmap_obstack_initialize (&live->livein_obstack); bitmap_obstack_initialize (&live->liveout_obstack); - live->livein = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun)); - FOR_EACH_BB_FN (bb, cfun) - bitmap_initialize (&live->livein[bb->index], &live->livein_obstack); - live->liveout = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun)); - FOR_EACH_BB_FN (bb, cfun) - bitmap_initialize (&live->liveout[bb->index], &live->liveout_obstack); + live->livein = XCNEWVEC (bitmap_head, last_basic_block_for_fn (cfun)); + live->liveout = XCNEWVEC (bitmap_head, last_basic_block_for_fn (cfun)); + for (unsigned i = 0; map->vec_bbs.iterate (i, &bb); ++i) + { + bitmap_initialize (&live->livein[bb->index], &live->livein_obstack); + bitmap_initialize (&live->liveout[bb->index], &live->liveout_obstack); + } live->work_stack = XNEWVEC (int, last_basic_block_for_fn (cfun)); live->stack_top = live->work_stack; @@ -960,7 +987,7 @@ loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited) FOR_EACH_EDGE (e, ei, bb->preds) { pred_bb = e->src; - if (pred_bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)) + if (!region_contains_p (live->map, pred_bb)) continue; /* Variables live-on-entry from BB that aren't defined in the predecessor block. This should be the live on entry vars to pred. @@ -993,9 +1020,10 @@ live_worklist (tree_live_info_p live) bitmap_clear (visited); - /* Visit all the blocks in reverse order and propagate live on entry values + /* Visit region's blocks in reverse order and propagate live on entry values into the predecessors blocks. */ - FOR_EACH_BB_REVERSE_FN (bb, cfun) + for (unsigned i = live->map->vec_bbs.length () - 1; + live->map->vec_bbs.iterate (i, &bb); --i) loe_visit_block (live, bb, visited); /* Process any blocks which require further iteration. */ @@ -1030,7 +1058,7 @@ set_var_live_on_entry (tree ssa_name, tree_live_info_p live) { def_bb = gimple_bb (stmt); /* Mark defs in liveout bitmap temporarily. */ - if (def_bb) + if (def_bb && region_contains_p (live->map, def_bb)) bitmap_set_bit (&live->liveout[def_bb->index], p); } else @@ -1054,11 +1082,8 @@ set_var_live_on_entry (tree ssa_name, tree_live_info_p live) defined in that block, or whether its live on entry. */ int index = PHI_ARG_INDEX_FROM_USE (use); edge e = gimple_phi_arg_edge (as_a <gphi *> (use_stmt), index); - if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)) - { - if (e->src != def_bb) - add_block = e->src; - } + if (e->src != def_bb && region_contains_p (live->map, e->src)) + add_block = e->src; } else if (is_gimple_debug (use_stmt)) continue; @@ -1066,7 +1091,7 @@ set_var_live_on_entry (tree ssa_name, tree_live_info_p live) { /* If its not defined in this block, its live on entry. */ basic_block use_bb = gimple_bb (use_stmt); - if (use_bb != def_bb) + if (use_bb != def_bb && region_contains_p (live->map, use_bb)) add_block = use_bb; } @@ -1095,7 +1120,7 @@ calculate_live_on_exit (tree_live_info_p liveinfo) edge_iterator ei; /* live on entry calculations used liveout vectors for defs, clear them. */ - FOR_EACH_BB_FN (bb, cfun) + for (unsigned i = 0; liveinfo->map->vec_bbs.iterate (i, &bb); ++i) bitmap_clear (&liveinfo->liveout[bb->index]); /* Set all the live-on-exit bits for uses in PHIs. */ @@ -1108,6 +1133,8 @@ calculate_live_on_exit (tree_live_info_p liveinfo) for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { gphi *phi = gsi.phi (); + if (virtual_operand_p (gimple_phi_result (phi))) + continue; for (i = 0; i < gimple_phi_num_args (phi); i++) { tree t = PHI_ARG_DEF (phi, i); @@ -1120,14 +1147,17 @@ calculate_live_on_exit (tree_live_info_p liveinfo) if (p == NO_PARTITION) continue; e = gimple_phi_arg_edge (phi, i); - if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)) + if (region_contains_p (liveinfo->map, e->src)) bitmap_set_bit (&liveinfo->liveout[e->src->index], p); } } + if (!region_contains_p (liveinfo->map, bb)) + continue; + /* Add each successors live on entry to this bock live on exit. */ FOR_EACH_EDGE (e, ei, bb->succs) - if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) + if (region_contains_p (liveinfo->map, e->dest)) bitmap_ior_into (&liveinfo->liveout[bb->index], live_on_entry (liveinfo, e->dest)); } @@ -1314,7 +1344,7 @@ verify_live_on_entry (tree_live_info_p live) FOR_EACH_EDGE (e, ei, bb->succs) { int entry_block = e->dest->index; - if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) + if (!region_contains_p (live->map, e->dest)) continue; for (i = 0; i < (unsigned)num_var_partitions (map); i++) { @@ -1380,6 +1410,8 @@ verify_live_on_entry (tree_live_info_p live) gsi_next (&gsi)) { gphi *phi = gsi.phi (); + if (virtual_operand_p (gimple_phi_result (phi))) + continue; for (z = 0; z < gimple_phi_num_args (phi); z++) if (var == gimple_phi_arg_def (phi, z)) { diff --git a/gcc/tree-ssa-live.h b/gcc/tree-ssa-live.h index 448aaf9..9aa5418 100644 --- a/gcc/tree-ssa-live.h +++ b/gcc/tree-ssa-live.h @@ -62,13 +62,25 @@ typedef struct _var_map /* Map of partitions numbers to base variable table indexes. */ int *partition_to_base_index; + + /* Bitmap of basic block. It describes the region within which the analysis + is done. Using pointer avoids allocating memory in out-of-ssa case. */ + bitmap bmp_bbs; + + /* Vector of basic block in the region. */ + vec<basic_block> vec_bbs; + + /* True if this map is for out-of-ssa, otherwise for live range + computation. When for out-of-ssa, it also means the var map is computed + for whole current function. */ + bool outofssa_p; } *var_map; /* Value used to represent no partition number. */ #define NO_PARTITION -1 -extern var_map init_var_map (int); +extern var_map init_var_map (int, struct loop* = NULL); extern void delete_var_map (var_map); extern int var_union (var_map, tree, tree); extern void partition_view_normal (var_map); @@ -82,6 +94,19 @@ extern void debug (_var_map &ref); extern void debug (_var_map *ptr); +/* Return TRUE if region of the MAP contains basic block BB. */ + +inline bool +region_contains_p (var_map map, basic_block bb) +{ + /* It's possible that the function is called with ENTRY_BLOCK/EXIT_BLOCK. */ + if (map->outofssa_p) + return (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK); + + return bitmap_bit_p (map->bmp_bbs, bb->index); +} + + /* Return number of partitions in MAP. */ static inline unsigned
On Thu, May 17, 2018 at 5:49 PM Bin.Cheng <amker.cheng@gmail.com> wrote: > On Thu, May 17, 2018 at 3:04 PM, Richard Biener > <richard.guenther@gmail.com> wrote: > > On Tue, May 15, 2018 at 5:44 PM Bin.Cheng <amker.cheng@gmail.com> wrote: > > > >> On Fri, May 11, 2018 at 1:53 PM, Richard Biener > >> <richard.guenther@gmail.com> wrote: > >> > On Fri, May 4, 2018 at 6:23 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: > >> >> Hi, > >> >> Following Jeff's suggestion, I am now using existing tree-ssa-live.c > > and > >> >> tree-ssa-coalesce.c to compute register pressure, rather than inventing > >> >> another live range solver. > >> >> > >> >> The major change is to record region's basic blocks in var_map and use > > that > >> >> information in computation, rather than FOR_EACH_BB_FN. For now only > > loop > >> >> and function type regions are supported. The default one is function > > type > >> >> region which is used in out-of-ssa. Loop type region will be used in > > next > >> >> patch to compute information for a loop. > >> >> > >> >> Bootstrap and test on x86_64 and AArch64 ongoing. Any comments? > >> > > >> > I believe your changes to create_outofssa_var_map should be done > > differently > >> > by simply only calling it from the coalescing context and passing in the > >> > var_map rather than initializing it therein and returning it. > >> > > >> > This also means the coalesce_vars_p flag in the var_map structure looks > >> > somewhat out-of-place. That is, it looks you could do with many less > >> > changes if you refactored what calls what slightly? For example > >> > the extra arg to gimple_can_coalesce_p looks unneeded. > >> > > >> > Just as a note I do have a CFG helper pending that computes RPO order > >> > for SEME regions (attached). loops are SEME regions, so your RTYPE_SESE > >> > is somewhat odd - I guess RTYPE_LOOP exists only because of the > >> > convenience of passing in a loop * to the "constructor". I'd rather > >> > drop this region_type thing and always assume a SEME region - at least > >> > I didn't see anything in the patch that depends on any of the forms > >> > apart from the initial BB gathering. > > > >> Hi Richard, > > > >> Thanks for reviewing. I refactored tree-ssa-live.c and > >> tree-ssa-coalesce.c following your comments. > >> Basically I did following changes: > >> 1) Remove region_type and only support loop region live range computation. > >> Also I added one boolean field in var_map indicating whether we > >> are computing > >> loop region live range or out-of-ssa. > >> 2) Refactored create_outofssa_var_map into > > create_coalesce_list_for_region and > >> populate_coalesce_list_for_outofssa. Actually the original > >> function name doesn't > >> quite make sense because it has nothing to do with var_map. > >> 3) Hoist init_var_map up in call stack. Now it's called by caller > >> (out-of-ssa or live range) > >> and the returned var_map is passed to coalesce_* stuff. > >> 4) Move global functions to tree-outof-ssa.c and make them static. > >> 5) Save/restore flag_tree_coalesce_vars in order to avoid updating > >> checks on the flag. > > > >> So how is this one? Patch attached. > > > > A lot better. Few things I noticed: > > > > + map->bmp_bbs = BITMAP_ALLOC (NULL); > > > > use a bitmap_head member and bitmap_initialize (). > > > > + map->vec_bbs = new vec<basic_block> (); > > > > use a vec<> member and map->vec_bbs = vNULL; > > > > Both changes remove an unnecessary indirection. > > > > + map->outofssa_p = true; > > + basic_block bb; > > + FOR_EACH_BB_FN (bb, cfun) > > + { > > + bitmap_set_bit (map->bmp_bbs, bb->index); > > + map->vec_bbs->safe_push (bb); > > + } > > > > I think you can avoid populating the bitmap and return > > true unconditionally for outofssa_p in the contains function? > > Ah, you already do - so why populate the bitmap? > > > > +/* Return TRUE if region of the MAP contains basic block BB. */ > > + > > +inline bool > > +region_contains_p (var_map map, basic_block bb) > > +{ > > + if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) > > + || bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) > > + return false; > > + > > + if (map->outofssa_p) > > + return true; > > + > > + return bitmap_bit_p (map->bmp_bbs, bb->index); > > > > the entry/exit block check should be conditional in map->outofssa_p > > but I think we should never get the function called with those args > > so we can as well use a gcc_checking_assert ()? > > > > I think as followup we should try to get a BB order that > > is more suited for the dataflow problem. Btw, I was > > thinking about adding anoter "visited" BB flag that is guaranteed to > > be unset and free to be used by infrastructure. So the bitmap > > could be elided for a bb flag check (but we need to clear that flag > > at the end of processing). Not sure if it's worth to add a machinery > > to dynamically assign pass-specific flags... it would at least be > > less error prone. Sth to think about. > > > > So -- I think the patch is ok with the two indirections removed, > > the rest can be optimized as followup. > Hi, > This is the updated patch. I moved checks on ENTRY/EXIT blocks under > outofssa_p, > as well as changed vec_bbs into object. Note bmp_bbs is kept in > pointer so that we > can avoid allocating memory in out-of-ssa case. > Bootstrap and test ongoing. Is it OK? Yes. Thanks, Richard. > Thanks, > bin > > > > Thanks, > > Richard. > > > > > >> Thanks, > >> bin > >> 2018-05-15 Bin Cheng <bin.cheng@arm.com> > > > >> * tree-outof-ssa.c (tree-ssa.h, tree-dfa.h): Include header files. > >> (create_default_def, for_all_parms): Moved from tree-ssa-coalesce.c. > >> (parm_default_def_partition_arg): Ditto. > >> (set_parm_default_def_partition): Ditto. > >> (get_parm_default_def_partitions): Ditto and make it static. > >> (get_undefined_value_partitions): Ditto and make it static. > >> (remove_ssa_form): Refactor call to init_var_map here. > >> * tree-ssa-coalesce.c (build_ssa_conflict_graph): Support live range > >> computation for loop region. > >> (coalesce_partitions, compute_optimized_partition_bases): Ditto. > >> (register_default_def): Delete. > >> (for_all_parms, create_default_def): Move to tree-outof-ssa.c. > >> (parm_default_def_partition_arg): Ditto. > >> (set_parm_default_def_partition): Ditto. > >> (get_parm_default_def_partitions): Ditto and make it static. > >> (get_undefined_value_partitions): Ditto and make it static. > >> (coalesce_with_default, coalesce_with_default): Update comment. > >> (create_coalesce_list_for_region): New func factored out from > >> create_outofssa_var_map. > >> (populate_coalesce_list_for_outofssa): New func factored out from > >> create_outofssa_var_map and coalesce_ssa_name. > >> (create_outofssa_var_map): Delete. > >> (coalesce_ssa_name): Refactor to support live range computation. > >> * tree-ssa-coalesce.h (coalesce_ssa_name): Change decl. > >> (get_parm_default_def_partitions): Delete. > >> (get_undefined_value_partitions): Ditto. > >> * tree-ssa-live.c (init_var_map, delete_var_map): Support live range > >> computation for loop region. > >> (new_tree_live_info, loe_visit_block): Ditto. > >> (live_worklist, set_var_live_on_entry): Ditto. > >> (calculate_live_on_exit, verify_live_on_entry): Ditto. > >> * tree-ssa-live.h (struct _var_map): New fields. > >> (init_var_map): Change decl. > >> (region_contains_p): New.
From 6b7b80eb40c0bd08c25c14b3f7c33937941bdfaa Mon Sep 17 00:00:00 2001 From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com> Date: Fri, 4 May 2018 09:39:17 +0100 Subject: [PATCH 4/6] liverange-support-region-20180427 --- gcc/tree-outof-ssa.c | 2 +- gcc/tree-ssa-coalesce.c | 77 ++++++++++++++++++++++++++++++----------------- gcc/tree-ssa-coalesce.h | 4 +-- gcc/tree-ssa-live.c | 80 +++++++++++++++++++++++++++++++++++-------------- gcc/tree-ssa-live.h | 51 ++++++++++++++++++++++++++++++- gcc/tree-ssa-uncprop.c | 5 ++-- 6 files changed, 163 insertions(+), 56 deletions(-) diff --git a/gcc/tree-outof-ssa.c b/gcc/tree-outof-ssa.c index 59bdcd6..81edbc5 100644 --- a/gcc/tree-outof-ssa.c +++ b/gcc/tree-outof-ssa.c @@ -945,7 +945,7 @@ remove_ssa_form (bool perform_ter, struct ssaexpand *sa) bitmap values = NULL; var_map map; - map = coalesce_ssa_name (); + map = coalesce_ssa_name (NULL, flag_tree_coalesce_vars); /* Return to viewing the variable list as just all reference variables after coalescing has been performed. */ diff --git a/gcc/tree-ssa-coalesce.c b/gcc/tree-ssa-coalesce.c index 5cc0aca..7269eb1 100644 --- a/gcc/tree-ssa-coalesce.c +++ b/gcc/tree-ssa-coalesce.c @@ -869,7 +869,7 @@ build_ssa_conflict_graph (tree_live_info_p liveinfo) coalesce variables from different base variables, including different parameters, so we have to make sure default defs live at the entry block conflict with each other. */ - if (flag_tree_coalesce_vars) + if (liveinfo->map->coalesce_vars_p) entry = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)); else entry = NULL; @@ -879,7 +879,7 @@ build_ssa_conflict_graph (tree_live_info_p liveinfo) live = new_live_track (map); - FOR_EACH_BB_FN (bb, cfun) + for (unsigned i = 0; liveinfo->map->vec_bbs->iterate (i, &bb); ++i) { /* Start with live on exit temporaries. */ live_track_init (live, live_on_exit (liveinfo, bb)); @@ -944,6 +944,8 @@ build_ssa_conflict_graph (tree_live_info_p liveinfo) { gphi *phi = gsi.phi (); tree result = PHI_RESULT (phi); + if (virtual_operand_p (result)) + continue; if (live_track_live_p (live, result)) live_track_process_def (live, result, graph); } @@ -1071,14 +1073,18 @@ coalesce_with_default (tree var, coalesce_list *cl, bitmap used_in_copy) add_cost_one_coalesce (cl, SSA_NAME_VERSION (ssa), SSA_NAME_VERSION (var)); bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var)); /* Default defs will have their used_in_copy bits set at the end of - create_outofssa_var_map. */ + create_var_map. */ } -/* This function creates a var_map for the current function as well as creating - a coalesce list for use later in the out of ssa process. */ +/* This function creates a var_map for a region indicated by BBS in the current + function as well as creating a coalesce list for use later in the out of ssa + process. Region is a loop if LOOP is not NULL, otherwise the function. + COALESCE_VARS_P is true if we coalesce version of different user-defined + variables. */ static var_map -create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy) +create_var_map (struct loop *loop, coalesce_list *cl, bitmap used_in_copy, + bool coalesce_vars_p) { gimple_stmt_iterator gsi; basic_block bb; @@ -1091,11 +1097,11 @@ create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy) for_all_parms (create_default_def, NULL); - map = init_var_map (num_ssa_names); + map = init_var_map (loop, num_ssa_names, coalesce_vars_p); for_all_parms (register_default_def, NULL); - FOR_EACH_BB_FN (bb, cfun) + for (unsigned j = 0; map->vec_bbs->iterate (j, &bb); ++j) { tree arg; @@ -1110,6 +1116,8 @@ create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy) bool saw_copy = false; res = gimple_phi_result (phi); + if (virtual_operand_p (res)) + continue; ver = SSA_NAME_VERSION (res); /* Register ssa_names and coalesces between the args and the result @@ -1121,7 +1129,7 @@ create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy) if (TREE_CODE (arg) != SSA_NAME) continue; - if (gimple_can_coalesce_p (arg, res) + if (gimple_can_coalesce_p (arg, res, coalesce_vars_p) || (e->flags & EDGE_ABNORMAL)) { saw_copy = true; @@ -1155,7 +1163,7 @@ create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy) tree lhs = gimple_assign_lhs (stmt); tree rhs1 = gimple_assign_rhs1 (stmt); if (gimple_assign_ssa_name_copy_p (stmt) - && gimple_can_coalesce_p (lhs, rhs1)) + && gimple_can_coalesce_p (lhs, rhs1, coalesce_vars_p)) { v1 = SSA_NAME_VERSION (lhs); v2 = SSA_NAME_VERSION (rhs1); @@ -1179,7 +1187,7 @@ create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy) tree lhs = ssa_default_def (cfun, res); gcc_assert (lhs); if (TREE_CODE (rhs1) == SSA_NAME - && gimple_can_coalesce_p (lhs, rhs1)) + && gimple_can_coalesce_p (lhs, rhs1, coalesce_vars_p)) { v1 = SSA_NAME_VERSION (lhs); v2 = SSA_NAME_VERSION (rhs1); @@ -1231,7 +1239,8 @@ create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy) v1 = SSA_NAME_VERSION (outputs[match]); v2 = SSA_NAME_VERSION (input); - if (gimple_can_coalesce_p (outputs[match], input)) + if (gimple_can_coalesce_p (outputs[match], input, + coalesce_vars_p)) { cost = coalesce_cost (REG_BR_PROB_BASE, optimize_bb_for_size_p (bb)); @@ -1249,6 +1258,9 @@ create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy) } } + if (!function_region_p (map)) + return map; + /* Now process result decls and live on entry variables for entry into the coalesce list. */ first = NULL_TREE; @@ -1267,7 +1279,8 @@ create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy) first = var; else { - gcc_assert (gimple_can_coalesce_p (var, first)); + gcc_assert (gimple_can_coalesce_p (var, first, + coalesce_vars_p)); v1 = SSA_NAME_VERSION (first); v2 = SSA_NAME_VERSION (var); cost = coalesce_cost_bb (EXIT_BLOCK_PTR_FOR_FN (cfun)); @@ -1384,13 +1397,15 @@ coalesce_partitions (var_map map, ssa_conflicts *graph, coalesce_list *cl, gsi_next (&gsi)) { gphi *phi = gsi.phi (); + tree res = PHI_RESULT (phi); + if (virtual_operand_p (res)) + continue; 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); @@ -1411,7 +1426,7 @@ coalesce_partitions (var_map map, ssa_conflicts *graph, coalesce_list *cl, var2 = ssa_name (y); /* Assert the coalesces have the same base variable. */ - gcc_assert (gimple_can_coalesce_p (var1, var2)); + gcc_assert (gimple_can_coalesce_p (var1, var2, map->coalesce_vars_p)); if (debug) fprintf (debug, "Coalesce list: "); @@ -1493,13 +1508,15 @@ dump_part_var_map (FILE *f, partition part, var_map map) } /* Given SSA_NAMEs NAME1 and NAME2, return true if they are candidates for - coalescing together, false otherwise. + coalescing together, false otherwise. If COALESCE_VARS_P is TRUE, we + try to coalesce versions of different user-defined variables. Normally + -ftree-coalesce-vars is passed in. This must stay consistent with compute_samebase_partition_bases and compute_optimized_partition_bases. */ bool -gimple_can_coalesce_p (tree name1, tree name2) +gimple_can_coalesce_p (tree name1, tree name2, bool coalesce_vars_p) { /* First check the SSA_NAME's associated DECL. Without optimization, we only want to coalesce if they have the same DECL @@ -1508,7 +1525,7 @@ gimple_can_coalesce_p (tree name1, tree name2) tree var2 = SSA_NAME_VAR (name2); var1 = (var1 && (!VAR_P (var1) || !DECL_IGNORED_P (var1))) ? var1 : NULL_TREE; var2 = (var2 && (!VAR_P (var2) || !DECL_IGNORED_P (var2))) ? var2 : NULL_TREE; - if (var1 != var2 && !flag_tree_coalesce_vars) + if (var1 != var2 && !coalesce_vars_p) return false; /* Now check the types. If the types are the same, then we should @@ -1565,7 +1582,7 @@ gimple_can_coalesce_p (tree name1, tree name2) In the non-optimized case, we must first test TYPE_CANONICAL because we use it to compute the partition_to_base_index of the map. */ - if (flag_tree_coalesce_vars) + if (coalesce_vars_p) { if (types_compatible_p (t1, t2)) goto check_modes; @@ -1629,8 +1646,9 @@ compute_optimized_partition_bases (var_map map, bitmap used_in_copies, /* And also with abnormal edges. */ basic_block bb; edge e; + unsigned i; edge_iterator ei; - FOR_EACH_BB_FN (bb, cfun) + for (i = 0; map->vec_bbs->iterate (i, &bb); ++i) { FOR_EACH_EDGE (e, ei, bb->preds) if (e->flags & EDGE_ABNORMAL) @@ -1640,14 +1658,15 @@ compute_optimized_partition_bases (var_map map, bitmap used_in_copies, gsi_next (&gsi)) { gphi *phi = gsi.phi (); + tree res = PHI_RESULT (phi); + if (virtual_operand_p (res)) + continue; 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 p1 = partition_find (tentative, var_to_partition (map, res)); int p2 = partition_find (tentative, var_to_partition (map, arg)); @@ -1675,7 +1694,6 @@ compute_optimized_partition_bases (var_map map, bitmap used_in_copies, between all SSA versions that ended up in the same potential coalesce partition. */ bitmap_iterator bi; - unsigned i; EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi) { int pidx = var_to_partition (map, ssa_name (i)); @@ -1785,10 +1803,13 @@ compute_samebase_partition_bases (var_map map) } /* Reduce the number of copies by coalescing variables in the function. Return - a partition map with the resulting coalesces. */ + a partition map with the resulting coalesces. The coalesce is done on a + region basis; and the region is a loop if LOOP is not NULL, otherwise is the + function. COALESCE_VARS_P is true if we coalesce version of different + user-defined variables. */ extern var_map -coalesce_ssa_name (void) +coalesce_ssa_name (struct loop *loop, bool coalesce_vars_p) { tree_live_info_p liveinfo; ssa_conflicts *graph; @@ -1799,12 +1820,12 @@ coalesce_ssa_name (void) tree a; cl = create_coalesce_list (); - map = create_outofssa_var_map (cl, used_in_copies); + map = create_var_map (loop, cl, used_in_copies, coalesce_vars_p); /* If this optimization is disabled, we need to coalesce all the names originating from the same SSA_NAME_VAR so debug info remains undisturbed. */ - if (!flag_tree_coalesce_vars) + if (!map->coalesce_vars_p) { hash_table<ssa_name_var_hash> ssa_name_hash (10); @@ -1845,7 +1866,7 @@ coalesce_ssa_name (void) partition_view_bitmap (map, used_in_copies); - if (flag_tree_coalesce_vars) + if (map->coalesce_vars_p) compute_optimized_partition_bases (map, used_in_copies, cl); else compute_samebase_partition_bases (map); diff --git a/gcc/tree-ssa-coalesce.h b/gcc/tree-ssa-coalesce.h index 89d8474..66acb18 100644 --- a/gcc/tree-ssa-coalesce.h +++ b/gcc/tree-ssa-coalesce.h @@ -20,8 +20,8 @@ along with GCC; see the file COPYING3. If not see #ifndef GCC_TREE_SSA_COALESCE_H #define GCC_TREE_SSA_COALESCE_H -extern var_map coalesce_ssa_name (void); -extern bool gimple_can_coalesce_p (tree, tree); +extern var_map coalesce_ssa_name (struct loop*, bool); +extern bool gimple_can_coalesce_p (tree, tree, bool); extern bitmap get_parm_default_def_partitions (var_map); extern bitmap get_undefined_value_partitions (var_map); diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c index 62316ba..ccb0d99 100644 --- a/gcc/tree-ssa-live.c +++ b/gcc/tree-ssa-live.c @@ -71,10 +71,13 @@ var_map_base_fini (var_map map) map->num_basevars = 0; } } -/* Create a variable partition map of SIZE, initialize and return it. */ +/* Create a variable partition map of SIZE for region, initialize and return + it. Region is a loop if LOOP is non-NULL, otherwise is current function. + COALESCE_VARS_P is true if we coalesce versions of different user-defined + variables. */ var_map -init_var_map (int size) +init_var_map (struct loop *loop, int size, bool coalesce_vars_p) { var_map map; @@ -87,6 +90,30 @@ init_var_map (int size) map->partition_size = size; map->num_basevars = 0; map->partition_to_base_index = NULL; + map->bmp_bbs = BITMAP_ALLOC (NULL); + map->vec_bbs = new vec<basic_block> (); + if (loop) + { + map->region_type = RTYPE_LOOP; + basic_block *bbs = get_loop_body_in_dom_order (loop); + for (unsigned i = 0; i < loop->num_nodes; ++i) + { + bitmap_set_bit (map->bmp_bbs, bbs[i]->index); + map->vec_bbs->safe_push (bbs[i]); + } + free (bbs); + } + else + { + map->region_type = RTYPE_FUNC; + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + { + bitmap_set_bit (map->bmp_bbs, bb->index); + map->vec_bbs->safe_push (bb); + } + } + map->coalesce_vars_p = coalesce_vars_p; return map; } @@ -100,6 +127,9 @@ delete_var_map (var_map map) partition_delete (map->var_partition); free (map->partition_to_view); free (map->view_to_partition); + BITMAP_FREE (map->bmp_bbs); + map->vec_bbs->release (); + delete map->vec_bbs; free (map); } @@ -901,13 +931,14 @@ new_tree_live_info (var_map map) bitmap_obstack_initialize (&live->livein_obstack); bitmap_obstack_initialize (&live->liveout_obstack); - live->livein = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun)); - FOR_EACH_BB_FN (bb, cfun) - bitmap_initialize (&live->livein[bb->index], &live->livein_obstack); - live->liveout = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun)); - FOR_EACH_BB_FN (bb, cfun) - bitmap_initialize (&live->liveout[bb->index], &live->liveout_obstack); + live->livein = XCNEWVEC (bitmap_head, last_basic_block_for_fn (cfun)); + live->liveout = XCNEWVEC (bitmap_head, last_basic_block_for_fn (cfun)); + for (unsigned i = 0; map->vec_bbs->iterate (i, &bb); ++i) + { + bitmap_initialize (&live->livein[bb->index], &live->livein_obstack); + bitmap_initialize (&live->liveout[bb->index], &live->liveout_obstack); + } live->work_stack = XNEWVEC (int, last_basic_block_for_fn (cfun)); live->stack_top = live->work_stack; @@ -960,7 +991,7 @@ loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited) FOR_EACH_EDGE (e, ei, bb->preds) { pred_bb = e->src; - if (pred_bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)) + if (!region_contains_p (live->map, pred_bb)) continue; /* Variables live-on-entry from BB that aren't defined in the predecessor block. This should be the live on entry vars to pred. @@ -993,9 +1024,10 @@ live_worklist (tree_live_info_p live) bitmap_clear (visited); - /* Visit all the blocks in reverse order and propagate live on entry values + /* Visit region's blocks in reverse order and propagate live on entry values into the predecessors blocks. */ - FOR_EACH_BB_REVERSE_FN (bb, cfun) + for (unsigned i = live->map->vec_bbs->length () - 1; + live->map->vec_bbs->iterate (i, &bb); --i) loe_visit_block (live, bb, visited); /* Process any blocks which require further iteration. */ @@ -1030,7 +1062,7 @@ set_var_live_on_entry (tree ssa_name, tree_live_info_p live) { def_bb = gimple_bb (stmt); /* Mark defs in liveout bitmap temporarily. */ - if (def_bb) + if (def_bb && region_contains_p (live->map, def_bb)) bitmap_set_bit (&live->liveout[def_bb->index], p); } else @@ -1054,11 +1086,8 @@ set_var_live_on_entry (tree ssa_name, tree_live_info_p live) defined in that block, or whether its live on entry. */ int index = PHI_ARG_INDEX_FROM_USE (use); edge e = gimple_phi_arg_edge (as_a <gphi *> (use_stmt), index); - if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)) - { - if (e->src != def_bb) - add_block = e->src; - } + if (e->src != def_bb && region_contains_p (live->map, e->src)) + add_block = e->src; } else if (is_gimple_debug (use_stmt)) continue; @@ -1066,7 +1095,7 @@ set_var_live_on_entry (tree ssa_name, tree_live_info_p live) { /* If its not defined in this block, its live on entry. */ basic_block use_bb = gimple_bb (use_stmt); - if (use_bb != def_bb) + if (use_bb != def_bb && region_contains_p (live->map, use_bb)) add_block = use_bb; } @@ -1095,7 +1124,7 @@ calculate_live_on_exit (tree_live_info_p liveinfo) edge_iterator ei; /* live on entry calculations used liveout vectors for defs, clear them. */ - FOR_EACH_BB_FN (bb, cfun) + for (unsigned i = 0; liveinfo->map->vec_bbs->iterate (i, &bb); ++i) bitmap_clear (&liveinfo->liveout[bb->index]); /* Set all the live-on-exit bits for uses in PHIs. */ @@ -1108,6 +1137,8 @@ calculate_live_on_exit (tree_live_info_p liveinfo) for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { gphi *phi = gsi.phi (); + if (virtual_operand_p (gimple_phi_result (phi))) + continue; for (i = 0; i < gimple_phi_num_args (phi); i++) { tree t = PHI_ARG_DEF (phi, i); @@ -1120,14 +1151,17 @@ calculate_live_on_exit (tree_live_info_p liveinfo) if (p == NO_PARTITION) continue; e = gimple_phi_arg_edge (phi, i); - if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)) + if (region_contains_p (liveinfo->map, e->src)) bitmap_set_bit (&liveinfo->liveout[e->src->index], p); } } + if (!region_contains_p (liveinfo->map, bb)) + continue; + /* Add each successors live on entry to this bock live on exit. */ FOR_EACH_EDGE (e, ei, bb->succs) - if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) + if (region_contains_p (liveinfo->map, e->dest)) bitmap_ior_into (&liveinfo->liveout[bb->index], live_on_entry (liveinfo, e->dest)); } @@ -1314,7 +1348,7 @@ verify_live_on_entry (tree_live_info_p live) FOR_EACH_EDGE (e, ei, bb->succs) { int entry_block = e->dest->index; - if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) + if (!region_contains_p (live->map, e->dest)) continue; for (i = 0; i < (unsigned)num_var_partitions (map); i++) { @@ -1380,6 +1414,8 @@ verify_live_on_entry (tree_live_info_p live) gsi_next (&gsi)) { gphi *phi = gsi.phi (); + if (virtual_operand_p (gimple_phi_result (phi))) + continue; for (z = 0; z < gimple_phi_num_args (phi); z++) if (var == gimple_phi_arg_def (phi, z)) { diff --git a/gcc/tree-ssa-live.h b/gcc/tree-ssa-live.h index 448aaf9..fa6f68d 100644 --- a/gcc/tree-ssa-live.h +++ b/gcc/tree-ssa-live.h @@ -42,6 +42,16 @@ along with GCC; see the file COPYING3. If not see Note that members of a partition MUST all have the same base variable. */ +/* The type of region within which live range is computed. For now we only + support loop and function type regions. */ +enum region_type +{ + RTYPE_BB, + RTYPE_LOOP, + RTYPE_SESE, + RTYPE_FUNC +}; + typedef struct _var_map { /* The partition manager of all variables. */ @@ -62,13 +72,27 @@ typedef struct _var_map /* Map of partitions numbers to base variable table indexes. */ int *partition_to_base_index; + + /* Bitmap of basic block. It describes the region within which the analysis + is done. */ + bitmap bmp_bbs; + + /* Vector of basic block in the region. */ + vec<basic_block> *vec_bbs; + + /* Type of region. */ + enum region_type region_type; + + /* Attemp to reduce copying by coalescing versions of user defined variables + if TRUE. */ + bool coalesce_vars_p; } *var_map; /* Value used to represent no partition number. */ #define NO_PARTITION -1 -extern var_map init_var_map (int); +extern var_map init_var_map (struct loop*, int, bool); extern void delete_var_map (var_map); extern int var_union (var_map, tree, tree); extern void partition_view_normal (var_map); @@ -82,6 +106,31 @@ extern void debug (_var_map &ref); extern void debug (_var_map *ptr); +/* Return TRUE if region of the MAP is the whole function. */ + +inline bool +function_region_p (var_map map) +{ + return map->region_type == RTYPE_FUNC; +} + + +/* Return TRUE if region of the MAP contains basic block BB. */ + +inline bool +region_contains_p (var_map map, basic_block bb) +{ + if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) + || bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) + return false; + + if (function_region_p (map)) + return true; + + return bitmap_bit_p (map->bmp_bbs, bb->index); +} + + /* Return number of partitions in MAP. */ static inline unsigned diff --git a/gcc/tree-ssa-uncprop.c b/gcc/tree-ssa-uncprop.c index 7d863a7..89863de 100644 --- a/gcc/tree-ssa-uncprop.c +++ b/gcc/tree-ssa-uncprop.c @@ -374,7 +374,7 @@ uncprop_into_successor_phis (basic_block bb) coalesced with the result, then there's no point in un-propagating the argument. */ if (!is_gimple_min_invariant (arg) - && gimple_can_coalesce_p (arg, res)) + && gimple_can_coalesce_p (arg, res, flag_tree_coalesce_vars)) continue; /* Lookup this argument's value in the hash table. */ @@ -390,7 +390,8 @@ uncprop_into_successor_phis (basic_block bb) { tree equiv = (*equivalences)[j]; - if (gimple_can_coalesce_p (equiv, res)) + if (gimple_can_coalesce_p (equiv, res, + flag_tree_coalesce_vars)) { SET_PHI_ARG_DEF (phi, e->dest_idx, equiv); break; -- 1.9.1