[5/6] implement live range, reg pressure computation class

Hi,
Based on previous patch, this one implements live range, reg pressure computation
class in tree-ssa-live.c.  The user would only need to instantiate the class and
call the computation interface as in next patch.
During the work, I think it's also worthwhile to classify all live range and coalesce
data structures and algorithms in the future.

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

Thanks,
bin
2018-04-27  Bin Cheng  <bin.cheng@arm.com>

	* tree-ssa-live.c (memmodel.h, ira.h, tree-ssa-coalesce.h): Include.
	(struct stmt_lr_info, free_stmt_lr_info): New.
	(lr_region::lr_region, lr_region::~lr_region): New.
	(lr_region::create_stmt_lr_info): New.
	(lr_region::update_live_range_by_stmt): New.
	(lr_region::calculate_coalesced_pressure): New.
	(lr_region::calculate_pressure): New.
	* tree-ssa-live.h (struct stmt_lr_info): New declaration.
	(class lr_region): New class.

On Fri, May 4, 2018 at 5:23 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
> Hi,
> Based on previous patch, this one implements live range, reg pressure computation
> class in tree-ssa-live.c.  The user would only need to instantiate the class and
> call the computation interface as in next patch.
> During the work, I think it's also worthwhile to classify all live range and coalesce
> data structures and algorithms in the future.
>
> Bootstrap and test on x86_64 and AArch64 ongoing.  Any comments?

Updated patch in line with change of previous patch.

Thanks,
bin
>
> Thanks,
> bin
> 2018-04-27  Bin Cheng  <bin.cheng@arm.com>
>
>         * tree-ssa-live.c (memmodel.h, ira.h, tree-ssa-coalesce.h): Include.
>         (struct stmt_lr_info, free_stmt_lr_info): New.
>         (lr_region::lr_region, lr_region::~lr_region): New.
>         (lr_region::create_stmt_lr_info): New.
>         (lr_region::update_live_range_by_stmt): New.
>         (lr_region::calculate_coalesced_pressure): New.
>         (lr_region::calculate_pressure): New.
>         * tree-ssa-live.h (struct stmt_lr_info): New declaration.
>         (class lr_region): New class.
From 98a97779ac475f89bd7f476a7c5fd045d83b79d6 Mon Sep 17 00:00:00 2001
From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com>
Date: Fri, 4 May 2018 09:42:04 +0100
Subject: [PATCH 5/6] region-reg-pressure-20180504

---
 gcc/tree-ssa-live.c | 167 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 gcc/tree-ssa-live.h |  49 +++++++++++++++
 2 files changed, 216 insertions(+)

diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c
index 7447f7a..e432bbe 100644
--- a/gcc/tree-ssa-live.c
+++ b/gcc/tree-ssa-live.c
@@ -23,6 +23,8 @@ along with GCC; see the file COPYING3.  If not see
 #include "coretypes.h"
 #include "backend.h"
 #include "rtl.h"
+#include "memmodel.h"
+#include "ira.h"
 #include "tree.h"
 #include "gimple.h"
 #include "timevar.h"
@@ -34,6 +36,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-dfa.h"
 #include "dumpfile.h"
 #include "tree-ssa-live.h"
+#include "tree-ssa-coalesce.h"
 #include "debug.h"
 #include "tree-ssa.h"
 #include "ipa-utils.h"
@@ -1200,6 +1203,170 @@ calculate_live_ranges (var_map map, bool want_livein)
 }
 
 
+/* Live range information for a gimple stmt.  */
+struct stmt_lr_info
+{
+  /*  ID of the stmt.  */
+  unsigned id;
+  gimple *stmt;
+  /* Live ranges after the stmt.  */
+  bitmap lr_after_stmt;
+};
+
+/* Call back function to free live range INFO of gimple STMT.  */
+
+bool
+free_stmt_lr_info (gimple *const & stmt, stmt_lr_info *const &info, void *)
+{
+  gcc_assert (info->stmt == stmt);
+  if (info->lr_after_stmt != NULL)
+    BITMAP_FREE (info->lr_after_stmt);
+
+  free (info);
+  return true;
+}
+
+lr_region::lr_region (struct loop *loop)
+  : m_loop (loop),
+    m_varmap (NULL),
+    m_liveinfo (NULL),
+    m_stmtmap (new hash_map<gimple *, stmt_lr_info *> (13))
+{
+  memset (m_pressure, 0, sizeof (unsigned) * N_REG_CLASSES);
+}
+
+lr_region::~lr_region ()
+{
+  m_stmtmap->traverse<void *, free_stmt_lr_info> (NULL);
+  delete m_stmtmap;
+}
+
+struct stmt_lr_info *
+lr_region::create_stmt_lr_info (gimple *stmt)
+{
+  bool exist_p;
+  struct stmt_lr_info **slot = &m_stmtmap->get_or_insert (stmt, &exist_p);
+
+  gcc_assert (!exist_p);
+  *slot = XCNEW (struct stmt_lr_info);
+  (*slot)->stmt = stmt;
+  (*slot)->lr_after_stmt = NULL;
+  return *slot;
+}
+
+void
+lr_region::update_live_range_by_stmt (gimple *stmt, bitmap live_ranges,
+				      unsigned *pressure)
+{
+  int p;
+  tree var;
+  ssa_op_iter iter;
+
+  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
+    {
+      p = var_to_partition (m_varmap, var);
+      gcc_assert (p != NO_PARTITION);
+      if (bitmap_clear_bit (live_ranges, p))
+	pressure[ira_mode_classes[TYPE_MODE (TREE_TYPE (var))]]--;
+    }
+  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
+    {
+      p = var_to_partition (m_varmap, var);
+      gcc_assert (p != NO_PARTITION);
+      if (bitmap_set_bit (live_ranges, p))
+	pressure[ira_mode_classes[TYPE_MODE (TREE_TYPE (var))]]++;
+    }
+}
+
+void
+lr_region::calculate_coalesced_pressure ()
+{
+  unsigned i, j, reg_class, pressure[N_REG_CLASSES];
+  bitmap_iterator bi, bj;
+  gimple_stmt_iterator bsi;
+  auto_bitmap live_ranges;
+  bitmap bbs = get_bbs ();
+
+  EXECUTE_IF_SET_IN_BITMAP (bbs, 0, i, bi)
+    {
+      basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
+      bitmap_copy (live_ranges, &m_liveinfo->liveout[bb->index]);
+
+      memset (pressure, 0, sizeof (unsigned) * N_REG_CLASSES);
+      EXECUTE_IF_SET_IN_BITMAP (live_ranges, 0, j, bj)
+	{
+	  tree var = partition_to_var (m_varmap, j);
+	  reg_class = ira_mode_classes[TYPE_MODE (TREE_TYPE (var))];
+	  pressure[reg_class]++;
+	}
+
+      for (bsi = gsi_last_bb (bb); !gsi_end_p (bsi); gsi_prev (&bsi))
+	{
+	  gimple *stmt = gsi_stmt (bsi);
+	  struct stmt_lr_info *stmt_info = create_stmt_lr_info (stmt);
+	  /* No need to compute live range information for debug stmt.  */
+	  if (is_gimple_debug (stmt))
+	    continue;
+
+	  for (j = 0; j < N_REG_CLASSES; j++)
+	    if (pressure[j] > m_pressure[j])
+	      m_pressure[j] = pressure[j];
+
+	  stmt_info->lr_after_stmt = BITMAP_ALLOC (NULL);
+	  bitmap_copy (stmt_info->lr_after_stmt, live_ranges);
+	  update_live_range_by_stmt (stmt, live_ranges, pressure);
+	}
+    }
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Max Reg Pressure:\n");
+      for (i = 0; i < N_REG_CLASSES; ++i)
+	if (m_pressure[i] != 0)
+	  fprintf (dump_file, "    %s: \t%d\n",
+		   reg_class_names[i], m_pressure[i]);
+    }
+}
+
+bool
+lr_region::calculate_pressure (unsigned *max_pressure)
+{
+  /* Save flag_tree_coalesce_vars.  */
+  bool saved_flag_tree_coalesce_vars = flag_tree_coalesce_vars;
+
+  m_varmap = init_var_map (num_ssa_names, m_loop);
+
+  /* Coalesce SSA variables.  For computing live ranges, we do want to coalesce
+     versions of different user-defined variables.  */
+  flag_tree_coalesce_vars = true;
+  coalesce_ssa_name (m_varmap);
+  /* Restore flag_tree_coalesce_vars.  */
+  flag_tree_coalesce_vars = saved_flag_tree_coalesce_vars;
+
+  partition_view_normal (m_varmap);
+
+  /* Calculate live ranges for region based on coalesced variables.  */
+  m_liveinfo = calculate_live_ranges (m_varmap, true);
+
+  /* Calculate register pressure.  */
+  calculate_coalesced_pressure ();
+
+  bool high_pressure_p = false;
+  for (unsigned k = 0; k < N_REG_CLASSES; k++)
+    {
+      if (m_pressure[k] >= pressure_threshold ()
+	  && m_pressure[k] > target_avail_regs[k])
+	high_pressure_p = true;
+
+      max_pressure[k] = m_pressure[k];
+    }
+
+  delete_tree_live_info (m_liveinfo);
+  delete_var_map (m_varmap);
+
+  return high_pressure_p;
+}
+
+
 /* Output partition map MAP to file F.  */
 
 void
diff --git a/gcc/tree-ssa-live.h b/gcc/tree-ssa-live.h
index 9aa5418..c1840b3 100644
--- a/gcc/tree-ssa-live.h
+++ b/gcc/tree-ssa-live.h
@@ -323,4 +323,53 @@ make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
   bitmap_set_bit (live->global, p);
 }
 
+struct stmt_lr_info;
+
+/* Live range region class.  Only loop region is supported for now.  */
+class lr_region
+{
+public:
+  lr_region (struct loop *loop);
+  ~lr_region ();
+
+  /* Threshold for register pressure above which is considered as high.  */
+  unsigned pressure_threshold () const { return 16; }
+
+  /* Calculate maximum reg pressure information for region and store it in
+     MAX_PRESSURE.  Return true if the reg pressure is high.  */
+  bool calculate_pressure (unsigned *max_pressure);
+private:
+  lr_region (const lr_region&);
+  lr_region &operator= (const lr_region&);
+
+  /* Return bitmap of basic blocks in this region.  */
+  bitmap get_bbs () const { return m_varmap->bmp_bbs; }
+
+  /* Create and return live range information for STMT.  */
+  struct stmt_lr_info *create_stmt_lr_info (gimple *stmt);
+
+  /* Update LIVE_RANGES bitmap and register PRESSURE information by backward
+     executing STMT.  */
+  void update_live_range_by_stmt (gimple *stmt, bitmap live_range,
+				  unsigned *pressure);
+
+  /* Calculate reg pressure information for REGION.  */
+  void calculate_coalesced_pressure ();
+
+  /* The loop from which this region is formed.  */
+  struct loop* m_loop;
+
+  /* SSA variable map for coalescing and reg pressure computation.  */
+  var_map m_varmap;
+
+  /* Live range information of this region.  */
+  tree_live_info_p m_liveinfo;
+
+  /* Map from gimple stmt to its live range information.  */
+  hash_map<gimple *, stmt_lr_info *> *m_stmtmap;
+
+  /* Register pressure information.  */
+  unsigned m_pressure[N_REG_CLASSES];
+};
+
 #endif /* _TREE_SSA_LIVE_H  */

On Fri, May 18, 2018 at 1:57 PM Bin.Cheng <amker.cheng@gmail.com> wrote:

> On Fri, May 4, 2018 at 5:23 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
> > Hi,
> > Based on previous patch, this one implements live range, reg pressure
computation
> > class in tree-ssa-live.c.  The user would only need to instantiate the
class and
> > call the computation interface as in next patch.
> > During the work, I think it's also worthwhile to classify all live
range and coalesce
> > data structures and algorithms in the future.
> >
> > Bootstrap and test on x86_64 and AArch64 ongoing.  Any comments?

> Updated patch in line with change of previous patch.

So I see you do not want to expose the magic '16' in pressure_threshold to
the
user because in theory the target should provide enough information.  But
why
need it at all?  Also

+  /* Calculate maximum reg pressure information for region and store it in
+     MAX_PRESSURE.  Return true if the reg pressure is high.  */
+  bool calculate_pressure (unsigned *max_pressure);

it looks like you expect a [N_REG_CLASSES] sized output array here, that's
not
clear from the documentation.

The output information is a little shallow - I'd be interested in the
number of
live through region regs being separated from live in / out.  That is, can
you
add additional outputs to the above and thus make it more like

   bool calculate_pressure (unsigned max_pressure[], unsigned live_in[],
unsigned live_out[], unsigned live_through[]);

with the numbers being on the region?

It also seems to be a fire-and-forget class so I wonder why liveness is not
computed at construction
time so intermediate data can be freed and only the results stored?

stmt_lr_info -> id seems to be unused?  In fact what is the point of this
structure (and the per stmt bitmap)?
It looks write-only to me...

Thanks and sorry for the delay in review.
Richard.

> Thanks,
> bin
> >
> > Thanks,
> > bin
> > 2018-04-27  Bin Cheng  <bin.cheng@arm.com>
> >
> >         * tree-ssa-live.c (memmodel.h, ira.h, tree-ssa-coalesce.h):
Include.
> >         (struct stmt_lr_info, free_stmt_lr_info): New.
> >         (lr_region::lr_region, lr_region::~lr_region): New.
> >         (lr_region::create_stmt_lr_info): New.
> >         (lr_region::update_live_range_by_stmt): New.
> >         (lr_region::calculate_coalesced_pressure): New.
> >         (lr_region::calculate_pressure): New.
> >         * tree-ssa-live.h (struct stmt_lr_info): New declaration.
> >         (class lr_region): New class.

On Mon, May 28, 2018 at 12:22 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Fri, May 18, 2018 at 1:57 PM Bin.Cheng <amker.cheng@gmail.com> wrote:
>
>> On Fri, May 4, 2018 at 5:23 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>> > Hi,
>> > Based on previous patch, this one implements live range, reg pressure
> computation
>> > class in tree-ssa-live.c.  The user would only need to instantiate the
> class and
>> > call the computation interface as in next patch.
>> > During the work, I think it's also worthwhile to classify all live
> range and coalesce
>> > data structures and algorithms in the future.
>> >
>> > Bootstrap and test on x86_64 and AArch64 ongoing.  Any comments?
>
>> Updated patch in line with change of previous patch.

Thanks for reviewing.

>
> So I see you do not want to expose the magic '16' in pressure_threshold to
> the
> user because in theory the target should provide enough information.  But
> why
> need it at all?  Also
Typically, we consider register pressure high if it exceeds available registers,
while for extreme targets, for example, with only 4~5 available registers, do we
consider a loop region with register pressure 8 as high?  It could be
a very small
loop and if we do, that would basically disable optimizations.  So
here the number
is used as an absolute criteria for high register pressure.  Given
max_pressure is
computed on GIMPLE and there might be scheduling issue exaggerating register
pressure, I chose this relative big number (16).

>
> +  /* Calculate maximum reg pressure information for region and store it in
> +     MAX_PRESSURE.  Return true if the reg pressure is high.  */
> +  bool calculate_pressure (unsigned *max_pressure);
>
> it looks like you expect a [N_REG_CLASSES] sized output array here, that's
> not
> clear from the documentation.
>
> The output information is a little shallow - I'd be interested in the
> number of
> live through region regs being separated from live in / out.  That is, can
> you
> add additional outputs to the above and thus make it more like
>
>    bool calculate_pressure (unsigned max_pressure[], unsigned live_in[],
> unsigned live_out[], unsigned live_through[]);
Done.

>
> with the numbers being on the region?
>
> It also seems to be a fire-and-forget class so I wonder why liveness is not
> computed at construction
> time so intermediate data can be freed and only the results stored?
>
> stmt_lr_info -> id seems to be unused?  In fact what is the point of this
> structure (and the per stmt bitmap)?
> It looks write-only to me...
Yes, this was legacy code from my draft patch where it computes live ranges
for within-block scheduling.  Now it's all removed/simplified.

Any comment on this version?  Also I will withhold it till ISA
interface exposing issue addressed.

Thanks,
bin

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

    * tree-ssa-live.c (memmodel.h, ira.h, tree-ssa-coalesce.h): Include.
    (lr_region::update_live_range_by_stmt): New.
    (lr_region::count_pressure_for_live_ranges): New.
    (lr_region::calculate_coalesced_pressure): New.
    (lr_region::calculate_pressure): New.
    * tree-ssa-live.h (class lr_region): New class.
From a51dc3bde02a24d4a6d17b5f14d13859a8766824 Mon Sep 17 00:00:00 2001
From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com>
Date: Fri, 4 May 2018 09:42:04 +0100
Subject: [PATCH 5/6] region-reg-pressure-20180528

---
 gcc/tree-ssa-live.c | 140 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 gcc/tree-ssa-live.h |  84 +++++++++++++++++++++++++++++++
 2 files changed, 224 insertions(+)

diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c
index 7447f7a..830b050 100644
--- a/gcc/tree-ssa-live.c
+++ b/gcc/tree-ssa-live.c
@@ -23,6 +23,8 @@ along with GCC; see the file COPYING3.  If not see
 #include "coretypes.h"
 #include "backend.h"
 #include "rtl.h"
+#include "memmodel.h"
+#include "ira.h"
 #include "tree.h"
 #include "gimple.h"
 #include "timevar.h"
@@ -34,6 +36,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-dfa.h"
 #include "dumpfile.h"
 #include "tree-ssa-live.h"
+#include "tree-ssa-coalesce.h"
 #include "debug.h"
 #include "tree-ssa.h"
 #include "ipa-utils.h"
@@ -1200,6 +1203,143 @@ calculate_live_ranges (var_map map, bool want_livein)
 }
 
 
+/* Implementation for class lr_region.  */
+
+void
+lr_region::update_live_range_by_stmt (gimple *stmt, bitmap live_ranges,
+				      unsigned pressure[])
+{
+  int p;
+  tree var;
+  ssa_op_iter iter;
+
+  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
+    {
+      p = var_to_partition (m_varmap, var);
+      gcc_assert (p != NO_PARTITION);
+      if (bitmap_clear_bit (live_ranges, p))
+	pressure[ira_mode_classes[TYPE_MODE (TREE_TYPE (var))]]--;
+    }
+  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
+    {
+      p = var_to_partition (m_varmap, var);
+      gcc_assert (p != NO_PARTITION);
+      if (bitmap_set_bit (live_ranges, p))
+	pressure[ira_mode_classes[TYPE_MODE (TREE_TYPE (var))]]++;
+    }
+}
+
+void
+lr_region::count_pressure_for_live_ranges (bitmap live_ranges,
+					   unsigned pressure[])
+{
+  unsigned i, reg_class;
+  bitmap_iterator bi;
+
+  memset (pressure, 0, sizeof (unsigned) * N_REG_CLASSES);
+  EXECUTE_IF_SET_IN_BITMAP (live_ranges, 0, i, bi)
+    {
+      tree var = partition_to_var (m_varmap, i);
+      reg_class = ira_mode_classes[TYPE_MODE (TREE_TYPE (var))];
+      pressure[reg_class]++;
+    }
+}
+
+void
+lr_region::calculate_coalesced_pressure ()
+{
+  unsigned i, j, pressure[N_REG_CLASSES];
+  bitmap_iterator bi;
+  gimple_stmt_iterator bsi;
+  auto_bitmap live_ranges, live_in, live_out;
+  bitmap bbs = get_bbs ();
+
+  memset (m_pressure, 0, sizeof (unsigned) * N_REG_CLASSES);
+  EXECUTE_IF_SET_IN_BITMAP (bbs, 0, i, bi)
+    {
+      basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
+
+      if (m_in && is_region_entry (bb))
+	bitmap_ior_into (live_in, &m_liveinfo->livein[bb->index]);
+      if (m_out && is_region_exit (bb))
+	bitmap_ior_into (live_out, &m_liveinfo->liveout[bb->index]);
+
+      bitmap_copy (live_ranges, &m_liveinfo->liveout[bb->index]);
+      count_pressure_for_live_ranges (live_ranges, pressure);
+
+      for (bsi = gsi_last_bb (bb); !gsi_end_p (bsi); gsi_prev (&bsi))
+	{
+	  gimple *stmt = gsi_stmt (bsi);
+	  /* No need to compute live range information for debug stmt.  */
+	  if (is_gimple_debug (stmt))
+	    continue;
+
+	  for (j = 0; j < N_REG_CLASSES; j++)
+	    if (pressure[j] > m_pressure[j])
+	      m_pressure[j] = pressure[j];
+
+	  update_live_range_by_stmt (stmt, live_ranges, pressure);
+	}
+    }
+
+  if (m_in)
+    count_pressure_for_live_ranges (live_in, m_in);
+  if (m_out)
+    count_pressure_for_live_ranges (live_out, m_out);
+  if (m_through)
+    {
+      bitmap_and_into (live_in, live_out);
+      count_pressure_for_live_ranges (live_in, m_through);
+    }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Reg Pressure: \tMax.\tIn\tOut\tThrough\n");
+      for (i = 0; i < N_REG_CLASSES; ++i)
+	if (m_pressure[i] != 0)
+	  fprintf (dump_file, "    %s: \t%d\t%d\t%d\t%d\n",
+		   reg_class_names[i], m_pressure[i],
+		   (m_in != NULL) ? m_in[i] : -1,
+		   (m_out != NULL) ? m_out[i] : -1,
+		   (m_through != NULL) ? m_through[i] : -1);
+    }
+}
+
+bool
+lr_region::calculate_pressure ()
+{
+  /* Save flag_tree_coalesce_vars.  */
+  bool saved_flag_tree_coalesce_vars = flag_tree_coalesce_vars;
+
+  m_varmap = init_var_map (num_ssa_names, m_loop);
+
+  /* Coalesce SSA variables.  For computing live ranges, we do want to coalesce
+     versions of different user-defined variables.  */
+  flag_tree_coalesce_vars = true;
+  coalesce_ssa_name (m_varmap);
+  /* Restore flag_tree_coalesce_vars.  */
+  flag_tree_coalesce_vars = saved_flag_tree_coalesce_vars;
+
+  partition_view_normal (m_varmap);
+
+  /* Calculate live ranges for region based on coalesced variables.  */
+  m_liveinfo = calculate_live_ranges (m_varmap, true);
+
+  /* Calculate register pressure.  */
+  calculate_coalesced_pressure ();
+
+  delete_tree_live_info (m_liveinfo);
+  delete_var_map (m_varmap);
+
+  for (unsigned k = 0; k < N_REG_CLASSES; k++)
+    if (m_pressure[k] >= pressure_threshold ()
+	&& m_pressure[k] > target_avail_regs[k])
+      return true;
+
+  return false;
+}
+
+
 /* Output partition map MAP to file F.  */
 
 void
diff --git a/gcc/tree-ssa-live.h b/gcc/tree-ssa-live.h
index 9aa5418..b77d7a7 100644
--- a/gcc/tree-ssa-live.h
+++ b/gcc/tree-ssa-live.h
@@ -323,4 +323,88 @@ make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
   bitmap_set_bit (live->global, p);
 }
 
+/* Live range region class.  Only loop region is supported for now.  */
+class lr_region
+{
+public:
+  lr_region (struct loop *loop, unsigned pressure[], unsigned in[],
+	     unsigned out[], unsigned through[])
+    : m_loop (loop), m_varmap (NULL), m_liveinfo (NULL),
+      m_pressure (pressure), m_in (in), m_out (out), m_through (through)
+    {
+      if (m_in == NULL || m_out == NULL)
+	m_through = NULL;
+    }
+  ~lr_region () { }
+
+  /* Calculate maximum reg pressure information for region.  Return true if
+     the reg pressure is high.  */
+  bool calculate_pressure ();
+private:
+  lr_region (const lr_region&);
+  lr_region &operator= (const lr_region&);
+
+  /* Threshold for register pressure above which is considered as high.  */
+  unsigned pressure_threshold () const { return 16; }
+
+  /* Return bitmap of basic blocks in this region.  */
+  bitmap get_bbs () const { return m_varmap->bmp_bbs; }
+
+  /* Return true if BB is an entry block of this region.  */
+  bool is_region_entry (basic_block bb)
+    {
+      edge e;
+      edge_iterator ei;
+
+      FOR_EACH_EDGE (e, ei, bb->preds)
+	if (!region_contains_p (m_varmap, e->src))
+	  return true;
+
+      return false;
+    }
+
+  /* Return true if BB is an exit block of this region.  */
+  bool is_region_exit (basic_block bb)
+    {
+      edge e;
+      edge_iterator ei;
+
+      FOR_EACH_EDGE (e, ei, bb->succs)
+	if (!region_contains_p (m_varmap, e->dest))
+	  return true;
+
+      return false;
+    }
+
+  /* Update LIVE_RANGES bitmap and register PRESSURE information by backward
+     executing STMT.  */
+  void update_live_range_by_stmt (gimple *stmt, bitmap live_range,
+				  unsigned pressure[]);
+
+  /* Count register pressure per reg_class for LIVE_RANGES and record the info
+     in array PRESSURE.  */
+  void count_pressure_for_live_ranges (bitmap live_ranges, unsigned pressure[]);
+
+  /* Calculate reg pressure information for REGION.  */
+  void calculate_coalesced_pressure ();
+
+  /* The loop from which this region is formed.  */
+  struct loop* m_loop;
+
+  /* SSA variable map for coalescing and reg pressure computation.  */
+  var_map m_varmap;
+
+  /* Live range information of this region.  */
+  tree_live_info_p m_liveinfo;
+
+  /* Register pressure information for this region: Max reg pressure.  */
+  unsigned *m_pressure;
+  /* Reg pressure into this region.  */
+  unsigned *m_in;
+  /* Reg pressure out of this region.  */
+  unsigned *m_out;
+  /* Reg pressure through this region.  */
+  unsigned *m_through;
+};
+
 #endif /* _TREE_SSA_LIVE_H  */