* [PATCH GCC][4/6]Support regional coalesce and live range computation
@ 2018-05-04 16:23 Bin Cheng
2018-05-11 13:09 ` Richard Biener
0 siblings, 1 reply; 6+ messages in thread
From: Bin Cheng @ 2018-05-04 16:23 UTC (permalink / raw)
To: gcc-patches; +Cc: nd
[-- Attachment #1: Type: text/plain, Size: 1633 bytes --]
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?
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.
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0004-liverange-support-region-20180427.patch --]
[-- Type: text/x-patch; name="0004-liverange-support-region-20180427.patch", Size: 22019 bytes --]
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
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH GCC][4/6]Support regional coalesce and live range computation
2018-05-04 16:23 [PATCH GCC][4/6]Support regional coalesce and live range computation Bin Cheng
@ 2018-05-11 13:09 ` Richard Biener
2018-05-15 15:56 ` Bin.Cheng
0 siblings, 1 reply; 6+ messages in thread
From: Richard Biener @ 2018-05-11 13:09 UTC (permalink / raw)
To: Bin Cheng; +Cc: gcc-patches, nd
[-- Attachment #1: Type: text/plain, Size: 2825 bytes --]
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.
[-- Attachment #2: p --]
[-- Type: application/octet-stream, Size: 4409 bytes --]
Index: early-lto-debug/gcc/cfganal.c
===================================================================
--- early-lto-debug.orig/gcc/cfganal.c 2017-11-22 10:51:29.900136465 +0100
+++ early-lto-debug/gcc/cfganal.c 2017-11-22 10:51:54.296526920 +0100
@@ -1057,6 +1057,109 @@ pre_and_rev_post_order_compute (int *pre
return pre_order_num;
}
+/* Unline pre_and_rev_post_order_compute we fill rev_post_order backwards
+ so iterating in RPO order needs to start with rev_post_order[n - 1]
+ going to rev_post_order[0]. */
+
+int
+rev_post_order_and_mark_dfs_back_seme (struct function *fn, edge entry,
+ bitmap exit_bbs,
+ int *rev_post_order)
+{
+ int pre_order_num = 0;
+ int rev_post_order_num = 0;
+
+ /* Allocate stack for back-tracking up CFG. */
+ auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (fn) + 1);
+
+ int *pre = XNEWVEC (int, 2 * last_basic_block_for_fn (fn));
+ int *post = pre + last_basic_block_for_fn (fn);
+
+ /* ??? We could use BB flags that are guaranteed to be clear,
+ clearing them again in a sweep over the found blocks at the end. */
+ /* Bitmap to track nodes that have been visited. */
+ auto_bitmap visited;
+ /* Bitmap to track which nodes whave post[] assigned to avoid
+ zeroing post. */
+ auto_bitmap post_assigned;
+
+ /* Push the first edge on to the stack. Build a fake edge vector
+ for this we can call ei_start on. */
+ vec<edge, va_gc> dummy;
+ dummy.embedded_init (1, 0, 0);
+ dummy.quick_push (entry);
+ vec<edge, va_gc> *dummyp = &dummy;
+ stack.quick_push (ei_start (dummyp));
+
+ while (!stack.is_empty ())
+ {
+ basic_block src;
+ basic_block dest;
+
+ /* Look at the edge on the top of the stack. */
+ edge_iterator ei = stack.last ();
+ src = ei_edge (ei)->src;
+ dest = ei_edge (ei)->dest;
+ ei_edge (ei)->flags &= ~EDGE_DFS_BACK;
+
+ /* Check if the edge destination has been visited yet. */
+ if (! bitmap_bit_p (exit_bbs, dest->index)
+ && ! bitmap_bit_p (visited, dest->index))
+ {
+ /* Mark that we have visited the destination. */
+ bitmap_set_bit (visited, dest->index);
+
+ pre[dest->index] = pre_order_num++;
+
+ if (EDGE_COUNT (dest->succs) > 0)
+ /* Since the DEST node has been visited for the first
+ time, check its successors. */
+ stack.quick_push (ei_start (dest->succs));
+ else
+ {
+ /* There are no successors for the DEST node so assign
+ its reverse completion number. */
+ post[dest->index] = rev_post_order_num;
+ bitmap_set_bit (post_assigned, dest->index);
+ rev_post_order[rev_post_order_num] = dest->index;
+ rev_post_order_num++;
+ }
+ }
+ else
+ {
+ if (bitmap_bit_p (visited, dest->index)
+ && pre[src->index] >= pre[dest->index]
+ && ! bitmap_bit_p (post_assigned, dest->index))
+ ei_edge (ei)->flags |= EDGE_DFS_BACK;
+
+ if (ei_one_before_end_p (ei))
+ {
+ /* There are no more successors for the SRC node
+ so assign its reverse completion number. */
+ post[src->index] = rev_post_order_num;
+ bitmap_set_bit (post_assigned, src->index);
+ rev_post_order[rev_post_order_num] = src->index;
+ rev_post_order_num++;
+ }
+
+ if (!ei_one_before_end_p (ei))
+ ei_next (&stack.last ());
+ else
+ {
+ stack.pop ();
+ if (ei_edge (stack.last ()) == entry)
+ break;
+ }
+ }
+ }
+
+ free (pre);
+
+ return rev_post_order_num;
+}
+
+
+
/* Compute the depth first search order on the _reverse_ graph and
store in the array DFS_ORDER, marking the nodes visited in VISITED.
Returns the number of nodes visited.
Index: early-lto-debug/gcc/cfganal.h
===================================================================
--- early-lto-debug.orig/gcc/cfganal.h 2017-11-22 10:51:29.900136465 +0100
+++ early-lto-debug/gcc/cfganal.h 2017-11-22 10:51:54.296526920 +0100
@@ -67,6 +67,8 @@ extern void inverted_post_order_compute
extern int pre_and_rev_post_order_compute_fn (struct function *,
int *, int *, bool);
extern int pre_and_rev_post_order_compute (int *, int *, bool);
+extern int rev_post_order_and_mark_dfs_back_seme (struct function *, edge,
+ bitmap, int *);
extern int dfs_enumerate_from (basic_block, int,
bool (*)(const_basic_block, const void *),
basic_block *, int, const void *);
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH GCC][4/6]Support regional coalesce and live range computation
2018-05-11 13:09 ` Richard Biener
@ 2018-05-15 15:56 ` Bin.Cheng
2018-05-17 14:13 ` Richard Biener
0 siblings, 1 reply; 6+ messages in thread
From: Bin.Cheng @ 2018-05-15 15:56 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 4560 bytes --]
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.
[-- Attachment #2: 0004-liverange-support-region-20180504.patch --]
[-- Type: text/x-patch, Size: 27221 bytes --]
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
--
1.9.1
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH GCC][4/6]Support regional coalesce and live range computation
2018-05-15 15:56 ` Bin.Cheng
@ 2018-05-17 14:13 ` Richard Biener
2018-05-17 16:04 ` Bin.Cheng
0 siblings, 1 reply; 6+ messages in thread
From: Richard Biener @ 2018-05-17 14:13 UTC (permalink / raw)
To: Amker.Cheng; +Cc: GCC Patches
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.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH GCC][4/6]Support regional coalesce and live range computation
2018-05-17 14:13 ` Richard Biener
@ 2018-05-17 16:04 ` Bin.Cheng
2018-05-18 7:29 ` Richard Biener
0 siblings, 1 reply; 6+ messages in thread
From: Bin.Cheng @ 2018-05-17 16:04 UTC (permalink / raw)
To: Richard Biener; +Cc: GCC Patches
[-- Attachment #1: Type: text/plain, Size: 7185 bytes --]
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.
[-- Attachment #2: 0004-liverange-support-region-20180515.patch --]
[-- Type: text/x-patch, Size: 27247 bytes --]
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
--
1.9.1
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH GCC][4/6]Support regional coalesce and live range computation
2018-05-17 16:04 ` Bin.Cheng
@ 2018-05-18 7:29 ` Richard Biener
0 siblings, 0 replies; 6+ messages in thread
From: Richard Biener @ 2018-05-18 7:29 UTC (permalink / raw)
To: Amker.Cheng; +Cc: GCC Patches
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.
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2018-05-18 7:28 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-05-04 16:23 [PATCH GCC][4/6]Support regional coalesce and live range computation Bin Cheng
2018-05-11 13:09 ` Richard Biener
2018-05-15 15:56 ` Bin.Cheng
2018-05-17 14:13 ` Richard Biener
2018-05-17 16:04 ` Bin.Cheng
2018-05-18 7:29 ` Richard Biener
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).