[4/6] Support regional coalesce and live range computation

Message ID DB6PR0802MB250419B22C2EABF9A56798F5E7860@DB6PR0802MB2504.eurprd08.prod.outlook.com
State New
Headers show
Series
  • [1/6] Compute type mode and register class mapping
Related show

Commit Message

Bin Cheng May 4, 2018, 4:23 p.m.
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.

Comments

Richard Biener May 11, 2018, 12:53 p.m. | #1
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.
Bin.Cheng May 15, 2018, 3:44 p.m. | #2
On Fri, May 11, 2018 at 1:53 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Fri, May 4, 2018 at 6:23 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:

>> Hi,

>> Following Jeff's suggestion, I am now using existing tree-ssa-live.c and

>> tree-ssa-coalesce.c to compute register pressure, rather than inventing

>> another live range solver.

>>

>> The major change is to record region's basic blocks in var_map and use that

>> information in computation, rather than FOR_EACH_BB_FN.  For now only loop

>> and function type regions are supported.  The default one is function type

>> region which is used in out-of-ssa.  Loop type region will be used in next

>> patch to compute information for a loop.

>>

>> Bootstrap and test on x86_64 and AArch64 ongoing.  Any comments?

>

> I believe your changes to create_outofssa_var_map should be done differently

> by simply only calling it from the coalescing context and passing in the

> var_map rather than initializing it therein and returning it.

>

> This also means the coalesce_vars_p flag in the var_map structure looks

> somewhat out-of-place.  That is, it looks you could do with many less

> changes if you refactored what calls what slightly?  For example

> the extra arg to gimple_can_coalesce_p looks unneeded.

>

> Just as a note I do have a CFG helper pending that computes RPO order

> for SEME regions (attached).  loops are SEME regions, so your RTYPE_SESE

> is somewhat odd - I guess RTYPE_LOOP exists only because of the

> convenience of passing in a loop * to the "constructor".  I'd rather

> drop this region_type thing and always assume a SEME region - at least

> I didn't see anything in the patch that depends on any of the forms

> apart from the initial BB gathering.


Hi Richard,

Thanks for reviewing.  I refactored tree-ssa-live.c and
tree-ssa-coalesce.c following your comments.
Basically I did following changes:
1) Remove region_type and only support loop region live range computation.
    Also I added one boolean field in var_map indicating whether we
are computing
    loop region live range or out-of-ssa.
2) Refactored create_outofssa_var_map into create_coalesce_list_for_region and
    populate_coalesce_list_for_outofssa.  Actually the original
function name doesn't
    quite make sense because it has nothing to do with var_map.
3) Hoist init_var_map up in call stack.  Now it's called by caller
(out-of-ssa or live range)
    and the returned var_map is passed to coalesce_* stuff.
4) Move global functions to tree-outof-ssa.c and make them static.
5) Save/restore flag_tree_coalesce_vars in order to avoid updating
checks on the flag.

So how is this one?  Patch attached.

Thanks,
bin
2018-05-15  Bin Cheng  <bin.cheng@arm.com>

    * tree-outof-ssa.c (tree-ssa.h, tree-dfa.h): Include header files.
    (create_default_def, for_all_parms): Moved from tree-ssa-coalesce.c.
    (parm_default_def_partition_arg): Ditto.
    (set_parm_default_def_partition): Ditto.
    (get_parm_default_def_partitions): Ditto and make it static.
    (get_undefined_value_partitions): Ditto and make it static.
    (remove_ssa_form): Refactor call to init_var_map here.
    * tree-ssa-coalesce.c (build_ssa_conflict_graph): Support live range
    computation for loop region.
    (coalesce_partitions, compute_optimized_partition_bases): Ditto.
    (register_default_def): Delete.
    (for_all_parms, create_default_def): Move to tree-outof-ssa.c.
    (parm_default_def_partition_arg): Ditto.
    (set_parm_default_def_partition): Ditto.
    (get_parm_default_def_partitions): Ditto and make it static.
    (get_undefined_value_partitions): Ditto and make it static.
    (coalesce_with_default, coalesce_with_default): Update comment.
    (create_coalesce_list_for_region): New func factored out from
    create_outofssa_var_map.
    (populate_coalesce_list_for_outofssa): New func factored out from
    create_outofssa_var_map and coalesce_ssa_name.
    (create_outofssa_var_map): Delete.
    (coalesce_ssa_name): Refactor to support live range computation.
    * tree-ssa-coalesce.h (coalesce_ssa_name): Change decl.
    (get_parm_default_def_partitions): Delete.
    (get_undefined_value_partitions): Ditto.
    * tree-ssa-live.c (init_var_map, delete_var_map): Support live range
    computation for loop region.
    (new_tree_live_info, loe_visit_block): Ditto.
    (live_worklist, set_var_live_on_entry): Ditto.
    (calculate_live_on_exit, verify_live_on_entry): Ditto.
    * tree-ssa-live.h (struct _var_map): New fields.
    (init_var_map): Change decl.
    (region_contains_p): New.
From 1043540cd5325c65e60df25cad22c343e4312fd4 Mon Sep 17 00:00:00 2001
From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com>
Date: Fri, 4 May 2018 09:39:17 +0100
Subject: [PATCH 4/6] liverange-support-region-20180504

---
 gcc/tree-outof-ssa.c    | 102 +++++++++++++++-
 gcc/tree-ssa-coalesce.c | 317 +++++++++++++++++-------------------------------
 gcc/tree-ssa-coalesce.h |   4 +-
 gcc/tree-ssa-live.c     |  78 ++++++++----
 gcc/tree-ssa-live.h     |  30 ++++-
 5 files changed, 298 insertions(+), 233 deletions(-)

diff --git a/gcc/tree-outof-ssa.c b/gcc/tree-outof-ssa.c
index 59bdcd6..3f880ef 100644
--- a/gcc/tree-outof-ssa.c
+++ b/gcc/tree-outof-ssa.c
@@ -27,10 +27,12 @@ along with GCC; see the file COPYING3.  If not see
 #include "gimple.h"
 #include "cfghooks.h"
 #include "ssa.h"
+#include "tree-ssa.h"
 #include "memmodel.h"
 #include "emit-rtl.h"
 #include "gimple-pretty-print.h"
 #include "diagnostic-core.h"
+#include "tree-dfa.h"
 #include "stor-layout.h"
 #include "cfgrtl.h"
 #include "cfganal.h"
@@ -888,6 +890,102 @@ rewrite_trees (var_map map)
     }
 }
 
+/* Create a default def for VAR.  */
+
+static void
+create_default_def (tree var, void *arg ATTRIBUTE_UNUSED)
+{
+  if (!is_gimple_reg (var))
+    return;
+
+  tree ssa = get_or_create_ssa_default_def (cfun, var);
+  gcc_assert (ssa);
+}
+
+/* Call CALLBACK for all PARM_DECLs and RESULT_DECLs for which
+   assign_parms may ask for a default partition.  */
+
+static void
+for_all_parms (void (*callback)(tree var, void *arg), void *arg)
+{
+  for (tree var = DECL_ARGUMENTS (current_function_decl); var;
+       var = DECL_CHAIN (var))
+    callback (var, arg);
+  if (!VOID_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
+    callback (DECL_RESULT (current_function_decl), arg);
+  if (cfun->static_chain_decl)
+    callback (cfun->static_chain_decl, arg);
+}
+
+/* We need to pass two arguments to set_parm_default_def_partition,
+   but for_all_parms only supports one.  Use a pair.  */
+
+typedef std::pair<var_map, bitmap> parm_default_def_partition_arg;
+
+/* Set in ARG's PARTS bitmap the bit corresponding to the partition in
+   ARG's MAP containing VAR's default def.  */
+
+static void
+set_parm_default_def_partition (tree var, void *arg_)
+{
+  parm_default_def_partition_arg *arg = (parm_default_def_partition_arg *)arg_;
+  var_map map = arg->first;
+  bitmap parts = arg->second;
+
+  if (!is_gimple_reg (var))
+    return;
+
+  tree ssa = ssa_default_def (cfun, var);
+  gcc_assert (ssa);
+
+  int version = var_to_partition (map, ssa);
+  gcc_assert (version != NO_PARTITION);
+
+  bool changed = bitmap_set_bit (parts, version);
+  gcc_assert (changed);
+}
+
+/* Allocate and return a bitmap that has a bit set for each partition
+   that contains a default def for a parameter.  */
+
+static bitmap
+get_parm_default_def_partitions (var_map map)
+{
+  bitmap parm_default_def_parts = BITMAP_ALLOC (NULL);
+
+  parm_default_def_partition_arg
+    arg = std::make_pair (map, parm_default_def_parts);
+
+  for_all_parms (set_parm_default_def_partition, &arg);
+
+  return parm_default_def_parts;
+}
+
+/* Allocate and return a bitmap that has a bit set for each partition
+   that contains an undefined value.  */
+
+static bitmap
+get_undefined_value_partitions (var_map map)
+{
+  bitmap undefined_value_parts = BITMAP_ALLOC (NULL);
+
+  for (unsigned int i = 1; i < num_ssa_names; i++)
+    {
+      tree var = ssa_name (i);
+      if (var
+	  && !virtual_operand_p (var)
+	  && !has_zero_uses (var)
+	  && ssa_undefined_value_p (var))
+	{
+	  const int p = var_to_partition (map, var);
+	  if (p != NO_PARTITION)
+	    bitmap_set_bit (undefined_value_parts, p);
+	}
+    }
+
+  return undefined_value_parts;
+}
+
 /* Given the out-of-ssa info object SA (with prepared partitions)
    eliminate all phi nodes in all basic blocks.  Afterwards no
    basic block will have phi nodes anymore and there are possibly
@@ -945,7 +1043,9 @@ remove_ssa_form (bool perform_ter, struct ssaexpand *sa)
   bitmap values = NULL;
   var_map map;
 
-  map = coalesce_ssa_name ();
+  for_all_parms (create_default_def, NULL);
+  map = init_var_map (num_ssa_names);
+  coalesce_ssa_name (map);
 
   /* Return to viewing the variable list as just all reference variables after
      coalescing has been performed.  */
diff --git a/gcc/tree-ssa-coalesce.c b/gcc/tree-ssa-coalesce.c
index 5cc0aca..d0773fd 100644
--- a/gcc/tree-ssa-coalesce.c
+++ b/gcc/tree-ssa-coalesce.c
@@ -879,7 +879,7 @@ build_ssa_conflict_graph (tree_live_info_p liveinfo)
 
   live = new_live_track (map);
 
-  FOR_EACH_BB_FN (bb, cfun)
+  for (unsigned i = 0; liveinfo->map->vec_bbs->iterate (i, &bb); ++i)
     {
       /* Start with live on exit temporaries.  */
       live_track_init (live, live_on_exit (liveinfo, bb));
@@ -944,6 +944,8 @@ build_ssa_conflict_graph (tree_live_info_p liveinfo)
 	{
 	  gphi *phi = gsi.phi ();
 	  tree result = PHI_RESULT (phi);
+	  if (virtual_operand_p (result))
+	    continue;
 	  if (live_track_live_p (live, result))
 	    live_track_process_def (live, result, graph);
 	}
@@ -1012,48 +1014,9 @@ fail_abnormal_edge_coalesce (int x, int y)
   internal_error ("SSA corruption");
 }
 
-/* Call CALLBACK for all PARM_DECLs and RESULT_DECLs for which
-   assign_parms may ask for a default partition.  */
-
-static void
-for_all_parms (void (*callback)(tree var, void *arg), void *arg)
-{
-  for (tree var = DECL_ARGUMENTS (current_function_decl); var;
-       var = DECL_CHAIN (var))
-    callback (var, arg);
-  if (!VOID_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
-    callback (DECL_RESULT (current_function_decl), arg);
-  if (cfun->static_chain_decl)
-    callback (cfun->static_chain_decl, arg);
-}
-
-/* Create a default def for VAR.  */
-
-static void
-create_default_def (tree var, void *arg ATTRIBUTE_UNUSED)
-{
-  if (!is_gimple_reg (var))
-    return;
-
-  tree ssa = get_or_create_ssa_default_def (cfun, var);
-  gcc_assert (ssa);
-}
-
-/* Register VAR's default def in MAP.  */
-
-static void
-register_default_def (tree var, void *arg ATTRIBUTE_UNUSED)
-{
-  if (!is_gimple_reg (var))
-    return;
-
-  tree ssa = ssa_default_def (cfun, var);
-  gcc_assert (ssa);
-}
-
 /* If VAR is an SSA_NAME associated with a PARM_DECL or a RESULT_DECL,
    and the DECL's default def is unused (i.e., it was introduced by
-   create_default_def), mark VAR and the default def for
+   create_default_def for out-of-ssa), mark VAR and the default def for
    coalescing.  */
 
 static void
@@ -1070,32 +1033,25 @@ coalesce_with_default (tree var, coalesce_list *cl, bitmap used_in_copy)
 
   add_cost_one_coalesce (cl, SSA_NAME_VERSION (ssa), SSA_NAME_VERSION (var));
   bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
-  /* Default defs will have their used_in_copy bits set at the end of
-     create_outofssa_var_map.  */
+  /* Default defs will have their used_in_copy bits set at the beginning of
+     populate_coalesce_list_for_outofssa.  */
 }
 
-/* This function creates a var_map for the current function as well as creating
-   a coalesce list for use later in the out of ssa process.  */
 
-static var_map
-create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy)
+/* Given var_map MAP for a region, this function creates and returns a coalesce
+   list as well as recording related ssa names in USED_IN_COPIES for use later
+   in the out-of-ssa or live range computation process.  */
+
+static coalesce_list *
+create_coalesce_list_for_region (var_map map, bitmap used_in_copy)
 {
   gimple_stmt_iterator gsi;
   basic_block bb;
-  tree var;
+  coalesce_list *cl = create_coalesce_list ();
   gimple *stmt;
-  tree first;
-  var_map map;
   int v1, v2, cost;
-  unsigned i;
-
-  for_all_parms (create_default_def, NULL);
-
-  map = init_var_map (num_ssa_names);
-
-  for_all_parms (register_default_def, NULL);
 
-  FOR_EACH_BB_FN (bb, cfun)
+  for (unsigned j = 0; map->vec_bbs->iterate (j, &bb); ++j)
     {
       tree arg;
 
@@ -1110,6 +1066,8 @@ create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy)
 	  bool saw_copy = false;
 
 	  res = gimple_phi_result (phi);
+	  if (virtual_operand_p (res))
+	    continue;
 	  ver = SSA_NAME_VERSION (res);
 
 	  /* Register ssa_names and coalesces between the args and the result
@@ -1249,8 +1207,44 @@ create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy)
 	}
     }
 
-  /* Now process result decls and live on entry variables for entry into
-     the coalesce list.  */
+  return cl;
+}
+
+
+/* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR.  */
+
+struct ssa_name_var_hash : nofree_ptr_hash <tree_node>
+{
+  static inline hashval_t hash (const tree_node *);
+  static inline int equal (const tree_node *, const tree_node *);
+};
+
+inline hashval_t
+ssa_name_var_hash::hash (const_tree n)
+{
+  return DECL_UID (SSA_NAME_VAR (n));
+}
+
+inline int
+ssa_name_var_hash::equal (const tree_node *n1, const tree_node *n2)
+{
+  return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2);
+}
+
+
+/* This function populates coalesce list CL as well as recording related ssa
+   names in USED_IN_COPIES for use later in the out-of-ssa process.  */
+
+static void
+populate_coalesce_list_for_outofssa (coalesce_list *cl, bitmap used_in_copy)
+{
+  tree var;
+  tree first;
+  int v1, v2, cost;
+  unsigned i;
+
+  /* Process result decls and live on entry variables for entry into the
+     coalesce list.  */
   first = NULL_TREE;
   FOR_EACH_SSA_NAME (i, var, cfun)
     {
@@ -1285,7 +1279,46 @@ create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy)
 	}
     }
 
-  return map;
+  /* If this optimization is disabled, we need to coalesce all the
+     names originating from the same SSA_NAME_VAR so debug info
+     remains undisturbed.  */
+  if (!flag_tree_coalesce_vars)
+    {
+      tree a;
+      hash_table<ssa_name_var_hash> ssa_name_hash (10);
+
+      FOR_EACH_SSA_NAME (i, a, cfun)
+	{
+	  if (SSA_NAME_VAR (a)
+	      && !DECL_IGNORED_P (SSA_NAME_VAR (a))
+	      && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a)
+		  || !VAR_P (SSA_NAME_VAR (a))))
+	    {
+	      tree *slot = ssa_name_hash.find_slot (a, INSERT);
+
+	      if (!*slot)
+		*slot = a;
+	      else
+		{
+		  /* If the variable is a PARM_DECL or a RESULT_DECL, we
+		     _require_ that all the names originating from it be
+		     coalesced, because there must be a single partition
+		     containing all the names so that it can be assigned
+		     the canonical RTL location of the DECL safely.
+		     If in_lto_p, a function could have been compiled
+		     originally with optimizations and only the link
+		     performed at -O0, so we can't actually require it.  */
+		  const int cost
+		    = (TREE_CODE (SSA_NAME_VAR (a)) == VAR_DECL || in_lto_p)
+		      ? MUST_COALESCE_COST - 1 : MUST_COALESCE_COST;
+		  add_coalesce (cl, SSA_NAME_VERSION (a),
+				SSA_NAME_VERSION (*slot), cost);
+		  bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (a));
+		  bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (*slot));
+		}
+	    }
+	}
+    }
 }
 
 
@@ -1384,13 +1417,15 @@ coalesce_partitions (var_map map, ssa_conflicts *graph, coalesce_list *cl,
 		 gsi_next (&gsi))
 	      {
 		gphi *phi = gsi.phi ();
+		tree res = PHI_RESULT (phi);
+		if (virtual_operand_p (res))
+		  continue;
 		tree arg = PHI_ARG_DEF (phi, e->dest_idx);
 		if (SSA_NAME_IS_DEFAULT_DEF (arg)
 		    && (!SSA_NAME_VAR (arg)
 			|| TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL))
 		  continue;
 
-		tree res = PHI_RESULT (phi);
 		int v1 = SSA_NAME_VERSION (res);
 		int v2 = SSA_NAME_VERSION (arg);
 
@@ -1420,27 +1455,6 @@ coalesce_partitions (var_map map, ssa_conflicts *graph, coalesce_list *cl,
 }
 
 
-/* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR.  */
-
-struct ssa_name_var_hash : nofree_ptr_hash <tree_node>
-{
-  static inline hashval_t hash (const tree_node *);
-  static inline int equal (const tree_node *, const tree_node *);
-};
-
-inline hashval_t
-ssa_name_var_hash::hash (const_tree n)
-{
-  return DECL_UID (SSA_NAME_VAR (n));
-}
-
-inline int
-ssa_name_var_hash::equal (const tree_node *n1, const tree_node *n2)
-{
-  return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2);
-}
-
-
 /* Output partition map MAP with coalescing plan PART to file F.  */
 
 void
@@ -1629,8 +1643,9 @@ compute_optimized_partition_bases (var_map map, bitmap used_in_copies,
   /* And also with abnormal edges.  */
   basic_block bb;
   edge e;
+  unsigned i;
   edge_iterator ei;
-  FOR_EACH_BB_FN (bb, cfun)
+  for (i = 0; map->vec_bbs->iterate (i, &bb); ++i)
     {
       FOR_EACH_EDGE (e, ei, bb->preds)
 	if (e->flags & EDGE_ABNORMAL)
@@ -1640,14 +1655,15 @@ compute_optimized_partition_bases (var_map map, bitmap used_in_copies,
 		 gsi_next (&gsi))
 	      {
 		gphi *phi = gsi.phi ();
+		tree res = PHI_RESULT (phi);
+		if (virtual_operand_p (res))
+		  continue;
 		tree arg = PHI_ARG_DEF (phi, e->dest_idx);
 		if (SSA_NAME_IS_DEFAULT_DEF (arg)
 		    && (!SSA_NAME_VAR (arg)
 			|| TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL))
 		  continue;
 
-		tree res = PHI_RESULT (phi);
-
 		int p1 = partition_find (tentative, var_to_partition (map, res));
 		int p2 = partition_find (tentative, var_to_partition (map, arg));
 
@@ -1675,7 +1691,6 @@ compute_optimized_partition_bases (var_map map, bitmap used_in_copies,
      between all SSA versions that ended up in the same potential
      coalesce partition.  */
   bitmap_iterator bi;
-  unsigned i;
   EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
     {
       int pidx = var_to_partition (map, ssa_name (i));
@@ -1784,62 +1799,22 @@ compute_samebase_partition_bases (var_map map)
   free (mapstorage);
 }
 
-/* Reduce the number of copies by coalescing variables in the function.  Return
-   a partition map with the resulting coalesces.  */
+/* Given an initial var_map MAP, coalesce variables and return a partition map
+   with the resulting coalesce.  Note that this function is called in either
+   live range computation context or out-of-ssa context, indicated by MAP.  */
 
-extern var_map
-coalesce_ssa_name (void)
+extern void
+coalesce_ssa_name (var_map map)
 {
   tree_live_info_p liveinfo;
   ssa_conflicts *graph;
   coalesce_list *cl;
   auto_bitmap used_in_copies;
-  var_map map;
-  unsigned int i;
-  tree a;
 
-  cl = create_coalesce_list ();
-  map = create_outofssa_var_map (cl, used_in_copies);
+  cl = create_coalesce_list_for_region (map, used_in_copies);
+  if (map->outofssa_p)
+    populate_coalesce_list_for_outofssa (cl, used_in_copies);
 
-  /* If this optimization is disabled, we need to coalesce all the
-     names originating from the same SSA_NAME_VAR so debug info
-     remains undisturbed.  */
-  if (!flag_tree_coalesce_vars)
-    {
-      hash_table<ssa_name_var_hash> ssa_name_hash (10);
-
-      FOR_EACH_SSA_NAME (i, a, cfun)
-	{
-	  if (SSA_NAME_VAR (a)
-	      && !DECL_IGNORED_P (SSA_NAME_VAR (a))
-	      && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a)
-		  || !VAR_P (SSA_NAME_VAR (a))))
-	    {
-	      tree *slot = ssa_name_hash.find_slot (a, INSERT);
-
-	      if (!*slot)
-		*slot = a;
-	      else
-		{
-		  /* If the variable is a PARM_DECL or a RESULT_DECL, we
-		     _require_ that all the names originating from it be
-		     coalesced, because there must be a single partition
-		     containing all the names so that it can be assigned
-		     the canonical RTL location of the DECL safely.
-		     If in_lto_p, a function could have been compiled
-		     originally with optimizations and only the link
-		     performed at -O0, so we can't actually require it.  */
-		  const int cost
-		    = (TREE_CODE (SSA_NAME_VAR (a)) == VAR_DECL || in_lto_p)
-		      ? MUST_COALESCE_COST - 1 : MUST_COALESCE_COST;
-		  add_coalesce (cl, SSA_NAME_VERSION (a),
-				SSA_NAME_VERSION (*slot), cost);
-		  bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (a));
-		  bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (*slot));
-		}
-	    }
-	}
-    }
   if (dump_file && (dump_flags & TDF_DETAILS))
     dump_var_map (dump_file, map);
 
@@ -1853,7 +1828,7 @@ coalesce_ssa_name (void)
   if (num_var_partitions (map) < 1)
     {
       delete_coalesce_list (cl);
-      return map;
+      return;
     }
 
   if (dump_file && (dump_flags & TDF_DETAILS))
@@ -1890,75 +1865,5 @@ coalesce_ssa_name (void)
 
   delete_coalesce_list (cl);
   ssa_conflicts_delete (graph);
-
-  return map;
 }
 
-/* We need to pass two arguments to set_parm_default_def_partition,
-   but for_all_parms only supports one.  Use a pair.  */
-
-typedef std::pair<var_map, bitmap> parm_default_def_partition_arg;
-
-/* Set in ARG's PARTS bitmap the bit corresponding to the partition in
-   ARG's MAP containing VAR's default def.  */
-
-static void
-set_parm_default_def_partition (tree var, void *arg_)
-{
-  parm_default_def_partition_arg *arg = (parm_default_def_partition_arg *)arg_;
-  var_map map = arg->first;
-  bitmap parts = arg->second;
-
-  if (!is_gimple_reg (var))
-    return;
-
-  tree ssa = ssa_default_def (cfun, var);
-  gcc_assert (ssa);
-
-  int version = var_to_partition (map, ssa);
-  gcc_assert (version != NO_PARTITION);
-
-  bool changed = bitmap_set_bit (parts, version);
-  gcc_assert (changed);
-}
-
-/* Allocate and return a bitmap that has a bit set for each partition
-   that contains a default def for a parameter.  */
-
-bitmap
-get_parm_default_def_partitions (var_map map)
-{
-  bitmap parm_default_def_parts = BITMAP_ALLOC (NULL);
-
-  parm_default_def_partition_arg
-    arg = std::make_pair (map, parm_default_def_parts);
-
-  for_all_parms (set_parm_default_def_partition, &arg);
-
-  return parm_default_def_parts;
-}
-
-/* Allocate and return a bitmap that has a bit set for each partition
-   that contains an undefined value.  */
-
-bitmap
-get_undefined_value_partitions (var_map map)
-{
-  bitmap undefined_value_parts = BITMAP_ALLOC (NULL);
-
-  for (unsigned int i = 1; i < num_ssa_names; i++)
-    {
-      tree var = ssa_name (i);
-      if (var
-	  && !virtual_operand_p (var)
-	  && !has_zero_uses (var)
-	  && ssa_undefined_value_p (var))
-	{
-	  const int p = var_to_partition (map, var);
-	  if (p != NO_PARTITION)
-	    bitmap_set_bit (undefined_value_parts, p);
-	}
-    }
-
-  return undefined_value_parts;
-}
diff --git a/gcc/tree-ssa-coalesce.h b/gcc/tree-ssa-coalesce.h
index 89d8474..f787637 100644
--- a/gcc/tree-ssa-coalesce.h
+++ b/gcc/tree-ssa-coalesce.h
@@ -20,9 +20,7 @@ along with GCC; see the file COPYING3.  If not see
 #ifndef GCC_TREE_SSA_COALESCE_H
 #define GCC_TREE_SSA_COALESCE_H
 
-extern var_map coalesce_ssa_name (void);
+extern void coalesce_ssa_name (var_map);
 extern bool gimple_can_coalesce_p (tree, tree);
-extern bitmap get_parm_default_def_partitions (var_map);
-extern bitmap get_undefined_value_partitions (var_map);
 
 #endif /* GCC_TREE_SSA_COALESCE_H */
diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c
index 62316ba..c79e635 100644
--- a/gcc/tree-ssa-live.c
+++ b/gcc/tree-ssa-live.c
@@ -71,10 +71,12 @@ var_map_base_fini (var_map map)
       map->num_basevars = 0;
     }
 }
-/* Create a variable partition map of SIZE, initialize and return it.  */
+/* Create a variable partition map of SIZE for region, initialize and return
+   it.  Region is a loop if LOOP is non-NULL, otherwise is the current
+   function.  */
 
 var_map
-init_var_map (int size)
+init_var_map (int size, struct loop *loop)
 {
   var_map map;
 
@@ -87,6 +89,29 @@ init_var_map (int size)
   map->partition_size = size;
   map->num_basevars = 0;
   map->partition_to_base_index = NULL;
+  map->bmp_bbs = BITMAP_ALLOC (NULL);
+  map->vec_bbs = new vec<basic_block> ();
+  if (loop)
+    {
+      map->outofssa_p = false;
+      basic_block *bbs = get_loop_body_in_dom_order (loop);
+      for (unsigned i = 0; i < loop->num_nodes; ++i)
+	{
+	  bitmap_set_bit (map->bmp_bbs, bbs[i]->index);
+	  map->vec_bbs->safe_push (bbs[i]);
+	}
+      free (bbs);
+    }
+  else
+    {
+      map->outofssa_p = true;
+      basic_block bb;
+      FOR_EACH_BB_FN (bb, cfun)
+	{
+	  bitmap_set_bit (map->bmp_bbs, bb->index);
+	  map->vec_bbs->safe_push (bb);
+	}
+    }
   return map;
 }
 
@@ -100,6 +125,9 @@ delete_var_map (var_map map)
   partition_delete (map->var_partition);
   free (map->partition_to_view);
   free (map->view_to_partition);
+  BITMAP_FREE (map->bmp_bbs);
+  map->vec_bbs->release ();
+  delete map->vec_bbs;
   free (map);
 }
 
@@ -901,13 +929,14 @@ new_tree_live_info (var_map map)
 
   bitmap_obstack_initialize (&live->livein_obstack);
   bitmap_obstack_initialize (&live->liveout_obstack);
-  live->livein = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
-  FOR_EACH_BB_FN (bb, cfun)
-    bitmap_initialize (&live->livein[bb->index], &live->livein_obstack);
 
-  live->liveout = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
-  FOR_EACH_BB_FN (bb, cfun)
-    bitmap_initialize (&live->liveout[bb->index], &live->liveout_obstack);
+  live->livein = XCNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
+  live->liveout = XCNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
+  for (unsigned i = 0; map->vec_bbs->iterate (i, &bb); ++i)
+    {
+      bitmap_initialize (&live->livein[bb->index], &live->livein_obstack);
+      bitmap_initialize (&live->liveout[bb->index], &live->liveout_obstack);
+    }
 
   live->work_stack = XNEWVEC (int, last_basic_block_for_fn (cfun));
   live->stack_top = live->work_stack;
@@ -960,7 +989,7 @@ loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited)
   FOR_EACH_EDGE (e, ei, bb->preds)
     {
       pred_bb = e->src;
-      if (pred_bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
+      if (!region_contains_p (live->map, pred_bb))
 	continue;
       /* Variables live-on-entry from BB that aren't defined in the
 	 predecessor block.  This should be the live on entry vars to pred.
@@ -993,9 +1022,10 @@ live_worklist (tree_live_info_p live)
 
   bitmap_clear (visited);
 
-  /* Visit all the blocks in reverse order and propagate live on entry values
+  /* Visit region's blocks in reverse order and propagate live on entry values
      into the predecessors blocks.  */
-  FOR_EACH_BB_REVERSE_FN (bb, cfun)
+  for (unsigned i = live->map->vec_bbs->length () - 1;
+       live->map->vec_bbs->iterate (i, &bb); --i)
     loe_visit_block (live, bb, visited);
 
   /* Process any blocks which require further iteration.  */
@@ -1030,7 +1060,7 @@ set_var_live_on_entry (tree ssa_name, tree_live_info_p live)
     {
       def_bb = gimple_bb (stmt);
       /* Mark defs in liveout bitmap temporarily.  */
-      if (def_bb)
+      if (def_bb && region_contains_p (live->map, def_bb))
 	bitmap_set_bit (&live->liveout[def_bb->index], p);
     }
   else
@@ -1054,11 +1084,8 @@ set_var_live_on_entry (tree ssa_name, tree_live_info_p live)
 	     defined in that block, or whether its live on entry.  */
 	  int index = PHI_ARG_INDEX_FROM_USE (use);
 	  edge e = gimple_phi_arg_edge (as_a <gphi *> (use_stmt), index);
-	  if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
-	    {
-	      if (e->src != def_bb)
-		add_block = e->src;
-	    }
+	  if (e->src != def_bb && region_contains_p (live->map, e->src))
+	    add_block = e->src;
 	}
       else if (is_gimple_debug (use_stmt))
 	continue;
@@ -1066,7 +1093,7 @@ set_var_live_on_entry (tree ssa_name, tree_live_info_p live)
         {
 	  /* If its not defined in this block, its live on entry.  */
 	  basic_block use_bb = gimple_bb (use_stmt);
-	  if (use_bb != def_bb)
+	  if (use_bb != def_bb && region_contains_p (live->map, use_bb))
 	    add_block = use_bb;
 	}
 
@@ -1095,7 +1122,7 @@ calculate_live_on_exit (tree_live_info_p liveinfo)
   edge_iterator ei;
 
   /* live on entry calculations used liveout vectors for defs, clear them.  */
-  FOR_EACH_BB_FN (bb, cfun)
+  for (unsigned i = 0; liveinfo->map->vec_bbs->iterate (i, &bb); ++i)
     bitmap_clear (&liveinfo->liveout[bb->index]);
 
   /* Set all the live-on-exit bits for uses in PHIs.  */
@@ -1108,6 +1135,8 @@ calculate_live_on_exit (tree_live_info_p liveinfo)
       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 	{
 	  gphi *phi = gsi.phi ();
+	  if (virtual_operand_p (gimple_phi_result (phi)))
+	    continue;
 	  for (i = 0; i < gimple_phi_num_args (phi); i++)
 	    {
 	      tree t = PHI_ARG_DEF (phi, i);
@@ -1120,14 +1149,17 @@ calculate_live_on_exit (tree_live_info_p liveinfo)
 	      if (p == NO_PARTITION)
 		continue;
 	      e = gimple_phi_arg_edge (phi, i);
-	      if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
+	      if (region_contains_p (liveinfo->map, e->src))
 		bitmap_set_bit (&liveinfo->liveout[e->src->index], p);
 	    }
 	}
 
+      if (!region_contains_p (liveinfo->map, bb))
+	continue;
+
       /* Add each successors live on entry to this bock live on exit.  */
       FOR_EACH_EDGE (e, ei, bb->succs)
-	if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
+	if (region_contains_p (liveinfo->map, e->dest))
 	  bitmap_ior_into (&liveinfo->liveout[bb->index],
 			   live_on_entry (liveinfo, e->dest));
     }
@@ -1314,7 +1346,7 @@ verify_live_on_entry (tree_live_info_p live)
   FOR_EACH_EDGE (e, ei, bb->succs)
     {
       int entry_block = e->dest->index;
-      if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
+      if (!region_contains_p (live->map, e->dest))
         continue;
       for (i = 0; i < (unsigned)num_var_partitions (map); i++)
 	{
@@ -1380,6 +1412,8 @@ verify_live_on_entry (tree_live_info_p live)
 		     gsi_next (&gsi))
 		  {
 		    gphi *phi = gsi.phi ();
+		    if (virtual_operand_p (gimple_phi_result (phi)))
+		      continue;
 		    for (z = 0; z < gimple_phi_num_args (phi); z++)
 		      if (var == gimple_phi_arg_def (phi, z))
 			{
diff --git a/gcc/tree-ssa-live.h b/gcc/tree-ssa-live.h
index 448aaf9..13aea90 100644
--- a/gcc/tree-ssa-live.h
+++ b/gcc/tree-ssa-live.h
@@ -62,13 +62,25 @@ typedef struct _var_map
 
   /* Map of partitions numbers to base variable table indexes.  */
   int *partition_to_base_index;
+
+  /* Bitmap of basic block.  It describes the region within which the analysis
+     is done.  */
+  bitmap bmp_bbs;
+
+  /* Vector of basic block in the region.  */
+  vec<basic_block> *vec_bbs;
+
+  /* True if this map is for out-of-ssa, otherwise for live range
+     computation.  When for out-of-ssa, it also means the var map is computed
+     for whole current function.  */
+  bool outofssa_p;
 } *var_map;
 
 
 /* Value used to represent no partition number.  */
 #define NO_PARTITION		-1
 
-extern var_map init_var_map (int);
+extern var_map init_var_map (int, struct loop* = NULL);
 extern void delete_var_map (var_map);
 extern int var_union (var_map, tree, tree);
 extern void partition_view_normal (var_map);
@@ -82,6 +94,22 @@ extern void debug (_var_map &ref);
 extern void debug (_var_map *ptr);
 
 
+/* Return TRUE if region of the MAP contains basic block BB.  */
+
+inline bool
+region_contains_p (var_map map, basic_block bb)
+{
+  if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
+      || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
+    return false;
+
+  if (map->outofssa_p)
+    return true;
+
+  return bitmap_bit_p (map->bmp_bbs, bb->index);
+}
+
+
 /* Return number of partitions in MAP.  */
 
 static inline unsigned
Richard Biener May 17, 2018, 2:04 p.m. | #3
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.
Bin.Cheng May 17, 2018, 3:49 p.m. | #4
On Thu, May 17, 2018 at 3:04 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Tue, May 15, 2018 at 5:44 PM Bin.Cheng <amker.cheng@gmail.com> wrote:

>

>> On Fri, May 11, 2018 at 1:53 PM, Richard Biener

>> <richard.guenther@gmail.com> wrote:

>> > On Fri, May 4, 2018 at 6:23 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:

>> >> Hi,

>> >> Following Jeff's suggestion, I am now using existing tree-ssa-live.c

> and

>> >> tree-ssa-coalesce.c to compute register pressure, rather than inventing

>> >> another live range solver.

>> >>

>> >> The major change is to record region's basic blocks in var_map and use

> that

>> >> information in computation, rather than FOR_EACH_BB_FN.  For now only

> loop

>> >> and function type regions are supported.  The default one is function

> type

>> >> region which is used in out-of-ssa.  Loop type region will be used in

> next

>> >> patch to compute information for a loop.

>> >>

>> >> Bootstrap and test on x86_64 and AArch64 ongoing.  Any comments?

>> >

>> > I believe your changes to create_outofssa_var_map should be done

> differently

>> > by simply only calling it from the coalescing context and passing in the

>> > var_map rather than initializing it therein and returning it.

>> >

>> > This also means the coalesce_vars_p flag in the var_map structure looks

>> > somewhat out-of-place.  That is, it looks you could do with many less

>> > changes if you refactored what calls what slightly?  For example

>> > the extra arg to gimple_can_coalesce_p looks unneeded.

>> >

>> > Just as a note I do have a CFG helper pending that computes RPO order

>> > for SEME regions (attached).  loops are SEME regions, so your RTYPE_SESE

>> > is somewhat odd - I guess RTYPE_LOOP exists only because of the

>> > convenience of passing in a loop * to the "constructor".  I'd rather

>> > drop this region_type thing and always assume a SEME region - at least

>> > I didn't see anything in the patch that depends on any of the forms

>> > apart from the initial BB gathering.

>

>> Hi Richard,

>

>> Thanks for reviewing.  I refactored tree-ssa-live.c and

>> tree-ssa-coalesce.c following your comments.

>> Basically I did following changes:

>> 1) Remove region_type and only support loop region live range computation.

>>      Also I added one boolean field in var_map indicating whether we

>> are computing

>>      loop region live range or out-of-ssa.

>> 2) Refactored create_outofssa_var_map into

> create_coalesce_list_for_region and

>>      populate_coalesce_list_for_outofssa.  Actually the original

>> function name doesn't

>>      quite make sense because it has nothing to do with var_map.

>> 3) Hoist init_var_map up in call stack.  Now it's called by caller

>> (out-of-ssa or live range)

>>      and the returned var_map is passed to coalesce_* stuff.

>> 4) Move global functions to tree-outof-ssa.c and make them static.

>> 5) Save/restore flag_tree_coalesce_vars in order to avoid updating

>> checks on the flag.

>

>> So how is this one?  Patch attached.

>

> A lot better.  Few things I noticed:

>

> +  map->bmp_bbs = BITMAP_ALLOC (NULL);

>

> use a bitmap_head member and bitmap_initialize ().

>

> +  map->vec_bbs = new vec<basic_block> ();

>

> use a vec<> member and map->vec_bbs = vNULL;

>

> Both changes remove an unnecessary indirection.

>

> +      map->outofssa_p = true;

> +      basic_block bb;

> +      FOR_EACH_BB_FN (bb, cfun)

> +       {

> +         bitmap_set_bit (map->bmp_bbs, bb->index);

> +         map->vec_bbs->safe_push (bb);

> +       }

>

> I think you can avoid populating the bitmap and return

> true unconditionally for outofssa_p in the contains function?

> Ah, you already do - so why populate the bitmap?

>

> +/* Return TRUE if region of the MAP contains basic block BB.  */

> +

> +inline bool

> +region_contains_p (var_map map, basic_block bb)

> +{

> +  if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)

> +      || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))

> +    return false;

> +

> +  if (map->outofssa_p)

> +    return true;

> +

> +  return bitmap_bit_p (map->bmp_bbs, bb->index);

>

> the entry/exit block check should be conditional in map->outofssa_p

> but I think we should never get the function called with those args

> so we can as well use a gcc_checking_assert ()?

>

> I think as followup we should try to get a BB order that

> is more suited for the dataflow problem.  Btw, I was

> thinking about adding anoter "visited" BB flag that is guaranteed to

> be unset and free to be used by infrastructure.  So the bitmap

> could be elided for a bb flag check (but we need to clear that flag

> at the end of processing).  Not sure if it's worth to add a machinery

> to dynamically assign pass-specific flags...  it would at least be

> less error prone.  Sth to think about.

>

> So -- I think the patch is ok with the two indirections removed,

> the rest can be optimized as followup.

Hi,
This is the updated patch.  I moved checks on ENTRY/EXIT blocks under
outofssa_p,
as well as changed vec_bbs into object.  Note bmp_bbs is kept in
pointer so that we
can avoid allocating memory in out-of-ssa case.
Bootstrap and test ongoing.  Is it OK?

Thanks,
bin
>

> Thanks,

> Richard.

>

>

>> Thanks,

>> bin

>> 2018-05-15  Bin Cheng  <bin.cheng@arm.com>

>

>>      * tree-outof-ssa.c (tree-ssa.h, tree-dfa.h): Include header files.

>>      (create_default_def, for_all_parms): Moved from tree-ssa-coalesce.c.

>>      (parm_default_def_partition_arg): Ditto.

>>      (set_parm_default_def_partition): Ditto.

>>      (get_parm_default_def_partitions): Ditto and make it static.

>>      (get_undefined_value_partitions): Ditto and make it static.

>>      (remove_ssa_form): Refactor call to init_var_map here.

>>      * tree-ssa-coalesce.c (build_ssa_conflict_graph): Support live range

>>      computation for loop region.

>>      (coalesce_partitions, compute_optimized_partition_bases): Ditto.

>>      (register_default_def): Delete.

>>      (for_all_parms, create_default_def): Move to tree-outof-ssa.c.

>>      (parm_default_def_partition_arg): Ditto.

>>      (set_parm_default_def_partition): Ditto.

>>      (get_parm_default_def_partitions): Ditto and make it static.

>>      (get_undefined_value_partitions): Ditto and make it static.

>>      (coalesce_with_default, coalesce_with_default): Update comment.

>>      (create_coalesce_list_for_region): New func factored out from

>>      create_outofssa_var_map.

>>      (populate_coalesce_list_for_outofssa): New func factored out from

>>      create_outofssa_var_map and coalesce_ssa_name.

>>      (create_outofssa_var_map): Delete.

>>      (coalesce_ssa_name): Refactor to support live range computation.

>>      * tree-ssa-coalesce.h (coalesce_ssa_name): Change decl.

>>      (get_parm_default_def_partitions): Delete.

>>      (get_undefined_value_partitions): Ditto.

>>      * tree-ssa-live.c (init_var_map, delete_var_map): Support live range

>>      computation for loop region.

>>      (new_tree_live_info, loe_visit_block): Ditto.

>>      (live_worklist, set_var_live_on_entry): Ditto.

>>      (calculate_live_on_exit, verify_live_on_entry): Ditto.

>>      * tree-ssa-live.h (struct _var_map): New fields.

>>      (init_var_map): Change decl.

>>      (region_contains_p): New.
From e75498725921848330c9d2e7772da8b5c5b2dfe2 Mon Sep 17 00:00:00 2001
From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com>
Date: Fri, 4 May 2018 09:39:17 +0100
Subject: [PATCH 4/6] liverange-support-region-20180515

---
 gcc/tree-outof-ssa.c    | 102 +++++++++++++++-
 gcc/tree-ssa-coalesce.c | 317 +++++++++++++++++-------------------------------
 gcc/tree-ssa-coalesce.h |   4 +-
 gcc/tree-ssa-live.c     |  76 ++++++++----
 gcc/tree-ssa-live.h     |  27 ++++-
 5 files changed, 293 insertions(+), 233 deletions(-)

diff --git a/gcc/tree-outof-ssa.c b/gcc/tree-outof-ssa.c
index 59bdcd6..3f880ef 100644
--- a/gcc/tree-outof-ssa.c
+++ b/gcc/tree-outof-ssa.c
@@ -27,10 +27,12 @@ along with GCC; see the file COPYING3.  If not see
 #include "gimple.h"
 #include "cfghooks.h"
 #include "ssa.h"
+#include "tree-ssa.h"
 #include "memmodel.h"
 #include "emit-rtl.h"
 #include "gimple-pretty-print.h"
 #include "diagnostic-core.h"
+#include "tree-dfa.h"
 #include "stor-layout.h"
 #include "cfgrtl.h"
 #include "cfganal.h"
@@ -888,6 +890,102 @@ rewrite_trees (var_map map)
     }
 }
 
+/* Create a default def for VAR.  */
+
+static void
+create_default_def (tree var, void *arg ATTRIBUTE_UNUSED)
+{
+  if (!is_gimple_reg (var))
+    return;
+
+  tree ssa = get_or_create_ssa_default_def (cfun, var);
+  gcc_assert (ssa);
+}
+
+/* Call CALLBACK for all PARM_DECLs and RESULT_DECLs for which
+   assign_parms may ask for a default partition.  */
+
+static void
+for_all_parms (void (*callback)(tree var, void *arg), void *arg)
+{
+  for (tree var = DECL_ARGUMENTS (current_function_decl); var;
+       var = DECL_CHAIN (var))
+    callback (var, arg);
+  if (!VOID_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
+    callback (DECL_RESULT (current_function_decl), arg);
+  if (cfun->static_chain_decl)
+    callback (cfun->static_chain_decl, arg);
+}
+
+/* We need to pass two arguments to set_parm_default_def_partition,
+   but for_all_parms only supports one.  Use a pair.  */
+
+typedef std::pair<var_map, bitmap> parm_default_def_partition_arg;
+
+/* Set in ARG's PARTS bitmap the bit corresponding to the partition in
+   ARG's MAP containing VAR's default def.  */
+
+static void
+set_parm_default_def_partition (tree var, void *arg_)
+{
+  parm_default_def_partition_arg *arg = (parm_default_def_partition_arg *)arg_;
+  var_map map = arg->first;
+  bitmap parts = arg->second;
+
+  if (!is_gimple_reg (var))
+    return;
+
+  tree ssa = ssa_default_def (cfun, var);
+  gcc_assert (ssa);
+
+  int version = var_to_partition (map, ssa);
+  gcc_assert (version != NO_PARTITION);
+
+  bool changed = bitmap_set_bit (parts, version);
+  gcc_assert (changed);
+}
+
+/* Allocate and return a bitmap that has a bit set for each partition
+   that contains a default def for a parameter.  */
+
+static bitmap
+get_parm_default_def_partitions (var_map map)
+{
+  bitmap parm_default_def_parts = BITMAP_ALLOC (NULL);
+
+  parm_default_def_partition_arg
+    arg = std::make_pair (map, parm_default_def_parts);
+
+  for_all_parms (set_parm_default_def_partition, &arg);
+
+  return parm_default_def_parts;
+}
+
+/* Allocate and return a bitmap that has a bit set for each partition
+   that contains an undefined value.  */
+
+static bitmap
+get_undefined_value_partitions (var_map map)
+{
+  bitmap undefined_value_parts = BITMAP_ALLOC (NULL);
+
+  for (unsigned int i = 1; i < num_ssa_names; i++)
+    {
+      tree var = ssa_name (i);
+      if (var
+	  && !virtual_operand_p (var)
+	  && !has_zero_uses (var)
+	  && ssa_undefined_value_p (var))
+	{
+	  const int p = var_to_partition (map, var);
+	  if (p != NO_PARTITION)
+	    bitmap_set_bit (undefined_value_parts, p);
+	}
+    }
+
+  return undefined_value_parts;
+}
+
 /* Given the out-of-ssa info object SA (with prepared partitions)
    eliminate all phi nodes in all basic blocks.  Afterwards no
    basic block will have phi nodes anymore and there are possibly
@@ -945,7 +1043,9 @@ remove_ssa_form (bool perform_ter, struct ssaexpand *sa)
   bitmap values = NULL;
   var_map map;
 
-  map = coalesce_ssa_name ();
+  for_all_parms (create_default_def, NULL);
+  map = init_var_map (num_ssa_names);
+  coalesce_ssa_name (map);
 
   /* Return to viewing the variable list as just all reference variables after
      coalescing has been performed.  */
diff --git a/gcc/tree-ssa-coalesce.c b/gcc/tree-ssa-coalesce.c
index 5cc0aca..e4f576f 100644
--- a/gcc/tree-ssa-coalesce.c
+++ b/gcc/tree-ssa-coalesce.c
@@ -879,7 +879,7 @@ build_ssa_conflict_graph (tree_live_info_p liveinfo)
 
   live = new_live_track (map);
 
-  FOR_EACH_BB_FN (bb, cfun)
+  for (unsigned i = 0; liveinfo->map->vec_bbs.iterate (i, &bb); ++i)
     {
       /* Start with live on exit temporaries.  */
       live_track_init (live, live_on_exit (liveinfo, bb));
@@ -944,6 +944,8 @@ build_ssa_conflict_graph (tree_live_info_p liveinfo)
 	{
 	  gphi *phi = gsi.phi ();
 	  tree result = PHI_RESULT (phi);
+	  if (virtual_operand_p (result))
+	    continue;
 	  if (live_track_live_p (live, result))
 	    live_track_process_def (live, result, graph);
 	}
@@ -1012,48 +1014,9 @@ fail_abnormal_edge_coalesce (int x, int y)
   internal_error ("SSA corruption");
 }
 
-/* Call CALLBACK for all PARM_DECLs and RESULT_DECLs for which
-   assign_parms may ask for a default partition.  */
-
-static void
-for_all_parms (void (*callback)(tree var, void *arg), void *arg)
-{
-  for (tree var = DECL_ARGUMENTS (current_function_decl); var;
-       var = DECL_CHAIN (var))
-    callback (var, arg);
-  if (!VOID_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
-    callback (DECL_RESULT (current_function_decl), arg);
-  if (cfun->static_chain_decl)
-    callback (cfun->static_chain_decl, arg);
-}
-
-/* Create a default def for VAR.  */
-
-static void
-create_default_def (tree var, void *arg ATTRIBUTE_UNUSED)
-{
-  if (!is_gimple_reg (var))
-    return;
-
-  tree ssa = get_or_create_ssa_default_def (cfun, var);
-  gcc_assert (ssa);
-}
-
-/* Register VAR's default def in MAP.  */
-
-static void
-register_default_def (tree var, void *arg ATTRIBUTE_UNUSED)
-{
-  if (!is_gimple_reg (var))
-    return;
-
-  tree ssa = ssa_default_def (cfun, var);
-  gcc_assert (ssa);
-}
-
 /* If VAR is an SSA_NAME associated with a PARM_DECL or a RESULT_DECL,
    and the DECL's default def is unused (i.e., it was introduced by
-   create_default_def), mark VAR and the default def for
+   create_default_def for out-of-ssa), mark VAR and the default def for
    coalescing.  */
 
 static void
@@ -1070,32 +1033,25 @@ coalesce_with_default (tree var, coalesce_list *cl, bitmap used_in_copy)
 
   add_cost_one_coalesce (cl, SSA_NAME_VERSION (ssa), SSA_NAME_VERSION (var));
   bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (var));
-  /* Default defs will have their used_in_copy bits set at the end of
-     create_outofssa_var_map.  */
+  /* Default defs will have their used_in_copy bits set at the beginning of
+     populate_coalesce_list_for_outofssa.  */
 }
 
-/* This function creates a var_map for the current function as well as creating
-   a coalesce list for use later in the out of ssa process.  */
 
-static var_map
-create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy)
+/* Given var_map MAP for a region, this function creates and returns a coalesce
+   list as well as recording related ssa names in USED_IN_COPIES for use later
+   in the out-of-ssa or live range computation process.  */
+
+static coalesce_list *
+create_coalesce_list_for_region (var_map map, bitmap used_in_copy)
 {
   gimple_stmt_iterator gsi;
   basic_block bb;
-  tree var;
+  coalesce_list *cl = create_coalesce_list ();
   gimple *stmt;
-  tree first;
-  var_map map;
   int v1, v2, cost;
-  unsigned i;
-
-  for_all_parms (create_default_def, NULL);
-
-  map = init_var_map (num_ssa_names);
-
-  for_all_parms (register_default_def, NULL);
 
-  FOR_EACH_BB_FN (bb, cfun)
+  for (unsigned j = 0; map->vec_bbs.iterate (j, &bb); ++j)
     {
       tree arg;
 
@@ -1110,6 +1066,8 @@ create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy)
 	  bool saw_copy = false;
 
 	  res = gimple_phi_result (phi);
+	  if (virtual_operand_p (res))
+	    continue;
 	  ver = SSA_NAME_VERSION (res);
 
 	  /* Register ssa_names and coalesces between the args and the result
@@ -1249,8 +1207,44 @@ create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy)
 	}
     }
 
-  /* Now process result decls and live on entry variables for entry into
-     the coalesce list.  */
+  return cl;
+}
+
+
+/* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR.  */
+
+struct ssa_name_var_hash : nofree_ptr_hash <tree_node>
+{
+  static inline hashval_t hash (const tree_node *);
+  static inline int equal (const tree_node *, const tree_node *);
+};
+
+inline hashval_t
+ssa_name_var_hash::hash (const_tree n)
+{
+  return DECL_UID (SSA_NAME_VAR (n));
+}
+
+inline int
+ssa_name_var_hash::equal (const tree_node *n1, const tree_node *n2)
+{
+  return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2);
+}
+
+
+/* This function populates coalesce list CL as well as recording related ssa
+   names in USED_IN_COPIES for use later in the out-of-ssa process.  */
+
+static void
+populate_coalesce_list_for_outofssa (coalesce_list *cl, bitmap used_in_copy)
+{
+  tree var;
+  tree first;
+  int v1, v2, cost;
+  unsigned i;
+
+  /* Process result decls and live on entry variables for entry into the
+     coalesce list.  */
   first = NULL_TREE;
   FOR_EACH_SSA_NAME (i, var, cfun)
     {
@@ -1285,7 +1279,46 @@ create_outofssa_var_map (coalesce_list *cl, bitmap used_in_copy)
 	}
     }
 
-  return map;
+  /* If this optimization is disabled, we need to coalesce all the
+     names originating from the same SSA_NAME_VAR so debug info
+     remains undisturbed.  */
+  if (!flag_tree_coalesce_vars)
+    {
+      tree a;
+      hash_table<ssa_name_var_hash> ssa_name_hash (10);
+
+      FOR_EACH_SSA_NAME (i, a, cfun)
+	{
+	  if (SSA_NAME_VAR (a)
+	      && !DECL_IGNORED_P (SSA_NAME_VAR (a))
+	      && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a)
+		  || !VAR_P (SSA_NAME_VAR (a))))
+	    {
+	      tree *slot = ssa_name_hash.find_slot (a, INSERT);
+
+	      if (!*slot)
+		*slot = a;
+	      else
+		{
+		  /* If the variable is a PARM_DECL or a RESULT_DECL, we
+		     _require_ that all the names originating from it be
+		     coalesced, because there must be a single partition
+		     containing all the names so that it can be assigned
+		     the canonical RTL location of the DECL safely.
+		     If in_lto_p, a function could have been compiled
+		     originally with optimizations and only the link
+		     performed at -O0, so we can't actually require it.  */
+		  const int cost
+		    = (TREE_CODE (SSA_NAME_VAR (a)) == VAR_DECL || in_lto_p)
+		      ? MUST_COALESCE_COST - 1 : MUST_COALESCE_COST;
+		  add_coalesce (cl, SSA_NAME_VERSION (a),
+				SSA_NAME_VERSION (*slot), cost);
+		  bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (a));
+		  bitmap_set_bit (used_in_copy, SSA_NAME_VERSION (*slot));
+		}
+	    }
+	}
+    }
 }
 
 
@@ -1384,13 +1417,15 @@ coalesce_partitions (var_map map, ssa_conflicts *graph, coalesce_list *cl,
 		 gsi_next (&gsi))
 	      {
 		gphi *phi = gsi.phi ();
+		tree res = PHI_RESULT (phi);
+		if (virtual_operand_p (res))
+		  continue;
 		tree arg = PHI_ARG_DEF (phi, e->dest_idx);
 		if (SSA_NAME_IS_DEFAULT_DEF (arg)
 		    && (!SSA_NAME_VAR (arg)
 			|| TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL))
 		  continue;
 
-		tree res = PHI_RESULT (phi);
 		int v1 = SSA_NAME_VERSION (res);
 		int v2 = SSA_NAME_VERSION (arg);
 
@@ -1420,27 +1455,6 @@ coalesce_partitions (var_map map, ssa_conflicts *graph, coalesce_list *cl,
 }
 
 
-/* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR.  */
-
-struct ssa_name_var_hash : nofree_ptr_hash <tree_node>
-{
-  static inline hashval_t hash (const tree_node *);
-  static inline int equal (const tree_node *, const tree_node *);
-};
-
-inline hashval_t
-ssa_name_var_hash::hash (const_tree n)
-{
-  return DECL_UID (SSA_NAME_VAR (n));
-}
-
-inline int
-ssa_name_var_hash::equal (const tree_node *n1, const tree_node *n2)
-{
-  return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2);
-}
-
-
 /* Output partition map MAP with coalescing plan PART to file F.  */
 
 void
@@ -1629,8 +1643,9 @@ compute_optimized_partition_bases (var_map map, bitmap used_in_copies,
   /* And also with abnormal edges.  */
   basic_block bb;
   edge e;
+  unsigned i;
   edge_iterator ei;
-  FOR_EACH_BB_FN (bb, cfun)
+  for (i = 0; map->vec_bbs.iterate (i, &bb); ++i)
     {
       FOR_EACH_EDGE (e, ei, bb->preds)
 	if (e->flags & EDGE_ABNORMAL)
@@ -1640,14 +1655,15 @@ compute_optimized_partition_bases (var_map map, bitmap used_in_copies,
 		 gsi_next (&gsi))
 	      {
 		gphi *phi = gsi.phi ();
+		tree res = PHI_RESULT (phi);
+		if (virtual_operand_p (res))
+		  continue;
 		tree arg = PHI_ARG_DEF (phi, e->dest_idx);
 		if (SSA_NAME_IS_DEFAULT_DEF (arg)
 		    && (!SSA_NAME_VAR (arg)
 			|| TREE_CODE (SSA_NAME_VAR (arg)) != PARM_DECL))
 		  continue;
 
-		tree res = PHI_RESULT (phi);
-
 		int p1 = partition_find (tentative, var_to_partition (map, res));
 		int p2 = partition_find (tentative, var_to_partition (map, arg));
 
@@ -1675,7 +1691,6 @@ compute_optimized_partition_bases (var_map map, bitmap used_in_copies,
      between all SSA versions that ended up in the same potential
      coalesce partition.  */
   bitmap_iterator bi;
-  unsigned i;
   EXECUTE_IF_SET_IN_BITMAP (used_in_copies, 0, i, bi)
     {
       int pidx = var_to_partition (map, ssa_name (i));
@@ -1784,62 +1799,22 @@ compute_samebase_partition_bases (var_map map)
   free (mapstorage);
 }
 
-/* Reduce the number of copies by coalescing variables in the function.  Return
-   a partition map with the resulting coalesces.  */
+/* Given an initial var_map MAP, coalesce variables and return a partition map
+   with the resulting coalesce.  Note that this function is called in either
+   live range computation context or out-of-ssa context, indicated by MAP.  */
 
-extern var_map
-coalesce_ssa_name (void)
+extern void
+coalesce_ssa_name (var_map map)
 {
   tree_live_info_p liveinfo;
   ssa_conflicts *graph;
   coalesce_list *cl;
   auto_bitmap used_in_copies;
-  var_map map;
-  unsigned int i;
-  tree a;
 
-  cl = create_coalesce_list ();
-  map = create_outofssa_var_map (cl, used_in_copies);
+  cl = create_coalesce_list_for_region (map, used_in_copies);
+  if (map->outofssa_p)
+    populate_coalesce_list_for_outofssa (cl, used_in_copies);
 
-  /* If this optimization is disabled, we need to coalesce all the
-     names originating from the same SSA_NAME_VAR so debug info
-     remains undisturbed.  */
-  if (!flag_tree_coalesce_vars)
-    {
-      hash_table<ssa_name_var_hash> ssa_name_hash (10);
-
-      FOR_EACH_SSA_NAME (i, a, cfun)
-	{
-	  if (SSA_NAME_VAR (a)
-	      && !DECL_IGNORED_P (SSA_NAME_VAR (a))
-	      && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a)
-		  || !VAR_P (SSA_NAME_VAR (a))))
-	    {
-	      tree *slot = ssa_name_hash.find_slot (a, INSERT);
-
-	      if (!*slot)
-		*slot = a;
-	      else
-		{
-		  /* If the variable is a PARM_DECL or a RESULT_DECL, we
-		     _require_ that all the names originating from it be
-		     coalesced, because there must be a single partition
-		     containing all the names so that it can be assigned
-		     the canonical RTL location of the DECL safely.
-		     If in_lto_p, a function could have been compiled
-		     originally with optimizations and only the link
-		     performed at -O0, so we can't actually require it.  */
-		  const int cost
-		    = (TREE_CODE (SSA_NAME_VAR (a)) == VAR_DECL || in_lto_p)
-		      ? MUST_COALESCE_COST - 1 : MUST_COALESCE_COST;
-		  add_coalesce (cl, SSA_NAME_VERSION (a),
-				SSA_NAME_VERSION (*slot), cost);
-		  bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (a));
-		  bitmap_set_bit (used_in_copies, SSA_NAME_VERSION (*slot));
-		}
-	    }
-	}
-    }
   if (dump_file && (dump_flags & TDF_DETAILS))
     dump_var_map (dump_file, map);
 
@@ -1853,7 +1828,7 @@ coalesce_ssa_name (void)
   if (num_var_partitions (map) < 1)
     {
       delete_coalesce_list (cl);
-      return map;
+      return;
     }
 
   if (dump_file && (dump_flags & TDF_DETAILS))
@@ -1890,75 +1865,5 @@ coalesce_ssa_name (void)
 
   delete_coalesce_list (cl);
   ssa_conflicts_delete (graph);
-
-  return map;
 }
 
-/* We need to pass two arguments to set_parm_default_def_partition,
-   but for_all_parms only supports one.  Use a pair.  */
-
-typedef std::pair<var_map, bitmap> parm_default_def_partition_arg;
-
-/* Set in ARG's PARTS bitmap the bit corresponding to the partition in
-   ARG's MAP containing VAR's default def.  */
-
-static void
-set_parm_default_def_partition (tree var, void *arg_)
-{
-  parm_default_def_partition_arg *arg = (parm_default_def_partition_arg *)arg_;
-  var_map map = arg->first;
-  bitmap parts = arg->second;
-
-  if (!is_gimple_reg (var))
-    return;
-
-  tree ssa = ssa_default_def (cfun, var);
-  gcc_assert (ssa);
-
-  int version = var_to_partition (map, ssa);
-  gcc_assert (version != NO_PARTITION);
-
-  bool changed = bitmap_set_bit (parts, version);
-  gcc_assert (changed);
-}
-
-/* Allocate and return a bitmap that has a bit set for each partition
-   that contains a default def for a parameter.  */
-
-bitmap
-get_parm_default_def_partitions (var_map map)
-{
-  bitmap parm_default_def_parts = BITMAP_ALLOC (NULL);
-
-  parm_default_def_partition_arg
-    arg = std::make_pair (map, parm_default_def_parts);
-
-  for_all_parms (set_parm_default_def_partition, &arg);
-
-  return parm_default_def_parts;
-}
-
-/* Allocate and return a bitmap that has a bit set for each partition
-   that contains an undefined value.  */
-
-bitmap
-get_undefined_value_partitions (var_map map)
-{
-  bitmap undefined_value_parts = BITMAP_ALLOC (NULL);
-
-  for (unsigned int i = 1; i < num_ssa_names; i++)
-    {
-      tree var = ssa_name (i);
-      if (var
-	  && !virtual_operand_p (var)
-	  && !has_zero_uses (var)
-	  && ssa_undefined_value_p (var))
-	{
-	  const int p = var_to_partition (map, var);
-	  if (p != NO_PARTITION)
-	    bitmap_set_bit (undefined_value_parts, p);
-	}
-    }
-
-  return undefined_value_parts;
-}
diff --git a/gcc/tree-ssa-coalesce.h b/gcc/tree-ssa-coalesce.h
index 89d8474..f787637 100644
--- a/gcc/tree-ssa-coalesce.h
+++ b/gcc/tree-ssa-coalesce.h
@@ -20,9 +20,7 @@ along with GCC; see the file COPYING3.  If not see
 #ifndef GCC_TREE_SSA_COALESCE_H
 #define GCC_TREE_SSA_COALESCE_H
 
-extern var_map coalesce_ssa_name (void);
+extern void coalesce_ssa_name (var_map);
 extern bool gimple_can_coalesce_p (tree, tree);
-extern bitmap get_parm_default_def_partitions (var_map);
-extern bitmap get_undefined_value_partitions (var_map);
 
 #endif /* GCC_TREE_SSA_COALESCE_H */
diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c
index 62316ba..7447f7a 100644
--- a/gcc/tree-ssa-live.c
+++ b/gcc/tree-ssa-live.c
@@ -71,10 +71,12 @@ var_map_base_fini (var_map map)
       map->num_basevars = 0;
     }
 }
-/* Create a variable partition map of SIZE, initialize and return it.  */
+/* Create a variable partition map of SIZE for region, initialize and return
+   it.  Region is a loop if LOOP is non-NULL, otherwise is the current
+   function.  */
 
 var_map
-init_var_map (int size)
+init_var_map (int size, struct loop *loop)
 {
   var_map map;
 
@@ -87,6 +89,27 @@ init_var_map (int size)
   map->partition_size = size;
   map->num_basevars = 0;
   map->partition_to_base_index = NULL;
+  map->vec_bbs = vNULL;
+  if (loop)
+    {
+      map->bmp_bbs = BITMAP_ALLOC (NULL);
+      map->outofssa_p = false;
+      basic_block *bbs = get_loop_body_in_dom_order (loop);
+      for (unsigned i = 0; i < loop->num_nodes; ++i)
+	{
+	  bitmap_set_bit (map->bmp_bbs, bbs[i]->index);
+	  map->vec_bbs.safe_push (bbs[i]);
+	}
+      free (bbs);
+    }
+  else
+    {
+      map->bmp_bbs = NULL;
+      map->outofssa_p = true;
+      basic_block bb;
+      FOR_EACH_BB_FN (bb, cfun)
+	map->vec_bbs.safe_push (bb);
+    }
   return map;
 }
 
@@ -100,6 +123,9 @@ delete_var_map (var_map map)
   partition_delete (map->var_partition);
   free (map->partition_to_view);
   free (map->view_to_partition);
+  if (map->bmp_bbs)
+    BITMAP_FREE (map->bmp_bbs);
+  map->vec_bbs.release ();
   free (map);
 }
 
@@ -901,13 +927,14 @@ new_tree_live_info (var_map map)
 
   bitmap_obstack_initialize (&live->livein_obstack);
   bitmap_obstack_initialize (&live->liveout_obstack);
-  live->livein = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
-  FOR_EACH_BB_FN (bb, cfun)
-    bitmap_initialize (&live->livein[bb->index], &live->livein_obstack);
 
-  live->liveout = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
-  FOR_EACH_BB_FN (bb, cfun)
-    bitmap_initialize (&live->liveout[bb->index], &live->liveout_obstack);
+  live->livein = XCNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
+  live->liveout = XCNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
+  for (unsigned i = 0; map->vec_bbs.iterate (i, &bb); ++i)
+    {
+      bitmap_initialize (&live->livein[bb->index], &live->livein_obstack);
+      bitmap_initialize (&live->liveout[bb->index], &live->liveout_obstack);
+    }
 
   live->work_stack = XNEWVEC (int, last_basic_block_for_fn (cfun));
   live->stack_top = live->work_stack;
@@ -960,7 +987,7 @@ loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited)
   FOR_EACH_EDGE (e, ei, bb->preds)
     {
       pred_bb = e->src;
-      if (pred_bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
+      if (!region_contains_p (live->map, pred_bb))
 	continue;
       /* Variables live-on-entry from BB that aren't defined in the
 	 predecessor block.  This should be the live on entry vars to pred.
@@ -993,9 +1020,10 @@ live_worklist (tree_live_info_p live)
 
   bitmap_clear (visited);
 
-  /* Visit all the blocks in reverse order and propagate live on entry values
+  /* Visit region's blocks in reverse order and propagate live on entry values
      into the predecessors blocks.  */
-  FOR_EACH_BB_REVERSE_FN (bb, cfun)
+  for (unsigned i = live->map->vec_bbs.length () - 1;
+       live->map->vec_bbs.iterate (i, &bb); --i)
     loe_visit_block (live, bb, visited);
 
   /* Process any blocks which require further iteration.  */
@@ -1030,7 +1058,7 @@ set_var_live_on_entry (tree ssa_name, tree_live_info_p live)
     {
       def_bb = gimple_bb (stmt);
       /* Mark defs in liveout bitmap temporarily.  */
-      if (def_bb)
+      if (def_bb && region_contains_p (live->map, def_bb))
 	bitmap_set_bit (&live->liveout[def_bb->index], p);
     }
   else
@@ -1054,11 +1082,8 @@ set_var_live_on_entry (tree ssa_name, tree_live_info_p live)
 	     defined in that block, or whether its live on entry.  */
 	  int index = PHI_ARG_INDEX_FROM_USE (use);
 	  edge e = gimple_phi_arg_edge (as_a <gphi *> (use_stmt), index);
-	  if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
-	    {
-	      if (e->src != def_bb)
-		add_block = e->src;
-	    }
+	  if (e->src != def_bb && region_contains_p (live->map, e->src))
+	    add_block = e->src;
 	}
       else if (is_gimple_debug (use_stmt))
 	continue;
@@ -1066,7 +1091,7 @@ set_var_live_on_entry (tree ssa_name, tree_live_info_p live)
         {
 	  /* If its not defined in this block, its live on entry.  */
 	  basic_block use_bb = gimple_bb (use_stmt);
-	  if (use_bb != def_bb)
+	  if (use_bb != def_bb && region_contains_p (live->map, use_bb))
 	    add_block = use_bb;
 	}
 
@@ -1095,7 +1120,7 @@ calculate_live_on_exit (tree_live_info_p liveinfo)
   edge_iterator ei;
 
   /* live on entry calculations used liveout vectors for defs, clear them.  */
-  FOR_EACH_BB_FN (bb, cfun)
+  for (unsigned i = 0; liveinfo->map->vec_bbs.iterate (i, &bb); ++i)
     bitmap_clear (&liveinfo->liveout[bb->index]);
 
   /* Set all the live-on-exit bits for uses in PHIs.  */
@@ -1108,6 +1133,8 @@ calculate_live_on_exit (tree_live_info_p liveinfo)
       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 	{
 	  gphi *phi = gsi.phi ();
+	  if (virtual_operand_p (gimple_phi_result (phi)))
+	    continue;
 	  for (i = 0; i < gimple_phi_num_args (phi); i++)
 	    {
 	      tree t = PHI_ARG_DEF (phi, i);
@@ -1120,14 +1147,17 @@ calculate_live_on_exit (tree_live_info_p liveinfo)
 	      if (p == NO_PARTITION)
 		continue;
 	      e = gimple_phi_arg_edge (phi, i);
-	      if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
+	      if (region_contains_p (liveinfo->map, e->src))
 		bitmap_set_bit (&liveinfo->liveout[e->src->index], p);
 	    }
 	}
 
+      if (!region_contains_p (liveinfo->map, bb))
+	continue;
+
       /* Add each successors live on entry to this bock live on exit.  */
       FOR_EACH_EDGE (e, ei, bb->succs)
-	if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
+	if (region_contains_p (liveinfo->map, e->dest))
 	  bitmap_ior_into (&liveinfo->liveout[bb->index],
 			   live_on_entry (liveinfo, e->dest));
     }
@@ -1314,7 +1344,7 @@ verify_live_on_entry (tree_live_info_p live)
   FOR_EACH_EDGE (e, ei, bb->succs)
     {
       int entry_block = e->dest->index;
-      if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
+      if (!region_contains_p (live->map, e->dest))
         continue;
       for (i = 0; i < (unsigned)num_var_partitions (map); i++)
 	{
@@ -1380,6 +1410,8 @@ verify_live_on_entry (tree_live_info_p live)
 		     gsi_next (&gsi))
 		  {
 		    gphi *phi = gsi.phi ();
+		    if (virtual_operand_p (gimple_phi_result (phi)))
+		      continue;
 		    for (z = 0; z < gimple_phi_num_args (phi); z++)
 		      if (var == gimple_phi_arg_def (phi, z))
 			{
diff --git a/gcc/tree-ssa-live.h b/gcc/tree-ssa-live.h
index 448aaf9..9aa5418 100644
--- a/gcc/tree-ssa-live.h
+++ b/gcc/tree-ssa-live.h
@@ -62,13 +62,25 @@ typedef struct _var_map
 
   /* Map of partitions numbers to base variable table indexes.  */
   int *partition_to_base_index;
+
+  /* Bitmap of basic block.  It describes the region within which the analysis
+     is done.  Using pointer avoids allocating memory in out-of-ssa case.  */
+  bitmap bmp_bbs;
+
+  /* Vector of basic block in the region.  */
+  vec<basic_block> vec_bbs;
+
+  /* True if this map is for out-of-ssa, otherwise for live range
+     computation.  When for out-of-ssa, it also means the var map is computed
+     for whole current function.  */
+  bool outofssa_p;
 } *var_map;
 
 
 /* Value used to represent no partition number.  */
 #define NO_PARTITION		-1
 
-extern var_map init_var_map (int);
+extern var_map init_var_map (int, struct loop* = NULL);
 extern void delete_var_map (var_map);
 extern int var_union (var_map, tree, tree);
 extern void partition_view_normal (var_map);
@@ -82,6 +94,19 @@ extern void debug (_var_map &ref);
 extern void debug (_var_map *ptr);
 
 
+/* Return TRUE if region of the MAP contains basic block BB.  */
+
+inline bool
+region_contains_p (var_map map, basic_block bb)
+{
+  /* It's possible that the function is called with ENTRY_BLOCK/EXIT_BLOCK.  */
+  if (map->outofssa_p)
+    return (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK);
+
+  return bitmap_bit_p (map->bmp_bbs, bb->index);
+}
+
+
 /* Return number of partitions in MAP.  */
 
 static inline unsigned
Richard Biener May 18, 2018, 7:27 a.m. | #5
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.

Patch

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