[3/6] New file computing regional register pressure on TREE SSA

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 97259ac..abfd4bc 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1534,6 +1534,7 @@  OBJS = \
 	tree-ssa-pre.o \
 	tree-ssa-propagate.o \
 	tree-ssa-reassoc.o \
+	tree-ssa-regpressure.o \
 	tree-ssa-sccvn.o \
 	tree-ssa-scopedtables.o \
 	tree-ssa-sink.o \
diff --git a/gcc/tree-ssa-regpressure.c b/gcc/tree-ssa-regpressure.c
new file mode 100644
index 0000000..ebc6576
--- /dev/null
+++ b/gcc/tree-ssa-regpressure.c
@@ -0,0 +1,829 @@ 
+/* Reg Pressure Model and Live Range Shrinking Optimization on TREE SSA.
+   Copyright (C) 2017 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 3, or (at your option) any
+later version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "rtl.h"
+#include "memmodel.h"
+#include "ira.h"
+#include "tree.h"
+#include "gimple.h"
+#include "cfghooks.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "gimple-pretty-print.h"
+#include "stor-layout.h"
+#include "fold-const.h"
+#include "gimple-iterator.h"
+#include "cfgloop.h"
+#include "tree-ssa-regpressure.h"
+
+
+/* Entry for invariant hash table.  */
+struct inv_entry
+{
+  tree expr;
+  unsigned id;
+  hashval_t hash;
+};
+
+/* Helpers for invariant hash table.  */
+
+struct inv_hasher : delete_ptr_hash <inv_entry>
+{
+  static inline hashval_t hash (const inv_entry *);
+  static inline bool equal (const inv_entry *, const inv_entry *);
+};
+
+/* Hash function for invariant hash table.  */
+
+inline hashval_t
+inv_hasher::hash (const inv_entry *entry)
+{
+  return entry->hash;
+}
+
+/* Hash table equality function for invariant hash table.  */
+
+inline bool
+inv_hasher::equal (const inv_entry *entry1, const inv_entry *entry2)
+{
+  return (entry1->hash == entry2->hash
+	  && operand_equal_p (entry1->expr, entry2->expr, 0)
+	  && (TYPE_PRECISION (TREE_TYPE (entry1->expr))
+	      == TYPE_PRECISION (TREE_TYPE (entry2->expr))));
+}
+
+/* Reg_alloc structure, coalesced from ssa variables.  */
+typedef struct reg_alloc
+{
+  /* ID of this reg_alloc.  */
+  unsigned id;
+  /* The type of ssa variables of this reg_alloc.  */
+  tree type;
+  /* Ssa variables coalesced to this reg_alloc.  */
+  bitmap vars;
+}*reg_alloc_t;
+
+/* Live range information for a basic block.  */
+struct bb_lr_info
+{
+  /* Geenrated live ranges.  */
+  bitmap gen;
+  /* Killed live ranges.  */
+  bitmap kill;
+  /* In live ranges at the begining of basic block.  */
+  bitmap in;
+  /* Out live range at the end of basic block.  */
+  bitmap out;
+  /* Maximum register pressure of this basic block.  */
+  unsigned max_pressure[N_REG_CLASSES];
+};
+
+/* 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;
+};
+
+/* Live range region structure.  */
+struct lr_region
+{
+  /* The loop from which this region is formed.  */
+  struct loop * loop;
+  /* Number of basic blocks in this region.  */
+  unsigned size;
+  /* Basic blocks of this region.  */
+  basic_block *body;
+  /* Live range information of region's basic blocks.  */
+  struct bb_lr_info *bb_lr_info;
+  /* Reg_allocs of this region.  */
+  vec<struct reg_alloc*> vallocs;
+  /* Map from ssa variable to reg_alloc id.  */
+  hash_map<tree, unsigned> *var_alloc_map;
+  /* Live out reg_allocs of this region.  */
+  bitmap live_out_allocs;
+  /* Map from basic block to its id in this region.  */
+  hash_map<basic_block, unsigned> *bb_idx_map;
+  /* Hash table recording loop invariant expressions.  This is necessary
+     because invariants are not propagated/CSEed at the stage reg pressure
+     is computed.  Otherwise it results in duplicated pressure.  */
+  hash_table<inv_hasher> *inv_table;
+  /* Map from gimple stmt to its live range information.  */
+  hash_map<gimple *, stmt_lr_info *> *stmt_lr_info_map;
+  /* Maximum register pressure of this region.  */
+  unsigned max_pressure[N_REG_CLASSES];
+};
+
+/* 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;
+}
+
+/* Create and return live range region for LOOP.  */
+static struct lr_region *
+create_loop_lr_region (struct loop *loop)
+{
+  struct lr_region *region = XCNEW (struct lr_region);
+
+  region->loop = loop;
+  region->size = loop->num_nodes;
+  region->body = get_loop_body_in_dom_order (loop);
+  region->vallocs.create (20);
+  region->var_alloc_map = new hash_map <tree, unsigned> (13);
+  region->live_out_allocs = BITMAP_ALLOC (NULL);
+  region->bb_idx_map = new hash_map <basic_block, unsigned> (13);
+  region->bb_lr_info = XCNEWVEC (struct bb_lr_info, region->size);
+  region->inv_table = new hash_table<inv_hasher> (13);
+  region->stmt_lr_info_map = new hash_map<gimple *, stmt_lr_info *> (13);
+  for (unsigned i = 0; i < region->size; i++)
+    {
+      basic_block bb = region->body[i];
+      unsigned *slot = &region->bb_idx_map->get_or_insert (bb);
+      *slot = i;
+    }
+  return region;
+}
+
+/* Store basic block BB's id in REGION to IDX.
+   Return true if BB is in REGION, return false otherwisely.  */
+static bool
+get_bb_idx_in_region (struct lr_region *region, basic_block bb, unsigned *idx)
+{
+  unsigned *slot = region->bb_idx_map->get (bb);
+  if (slot == NULL)
+    return false;
+
+  *idx = *slot;
+  return true;
+}
+
+/* Free live range REGION.  */
+void
+free_lr_region (struct lr_region *region)
+{
+  unsigned i;
+
+  free (region->body);
+
+  for (i = 0; i < region->size; i++)
+    {
+      BITMAP_FREE (region->bb_lr_info[i].gen);
+      BITMAP_FREE (region->bb_lr_info[i].kill);
+      BITMAP_FREE (region->bb_lr_info[i].in);
+      BITMAP_FREE (region->bb_lr_info[i].out);
+    }
+  free (region->bb_lr_info);
+  for (i = 0; i < region->vallocs.length (); i++)
+    {
+      struct reg_alloc *ra = region->vallocs[i];
+      BITMAP_FREE (ra->vars);
+      free (ra);
+    }
+  region->vallocs.release ();
+  delete region->var_alloc_map;
+  BITMAP_FREE (region->live_out_allocs);
+  delete region->bb_idx_map;
+  delete region->inv_table;
+  region->stmt_lr_info_map->traverse<void *, free_stmt_lr_info> (NULL);
+  delete region->stmt_lr_info_map;
+  region->stmt_lr_info_map = NULL;
+}
+
+/* Create and return new reg_alloc for VAR in REGION.  */
+static struct reg_alloc *
+create_reg_alloc (struct lr_region *region, tree var)
+{
+  bool exist_p;
+  unsigned *slot;
+  struct reg_alloc *ra = XCNEW (struct reg_alloc);
+
+  ra->id = region->vallocs.length ();
+  ra->type = TREE_TYPE (var);
+  ra->vars = BITMAP_ALLOC (NULL);
+  bitmap_set_bit (ra->vars, SSA_NAME_VERSION (var));
+  region->vallocs.safe_push (ra);
+  slot = &region->var_alloc_map->get_or_insert (var, &exist_p);
+  gcc_assert (!exist_p);
+  *slot = ra->id;
+
+  return ra;
+}
+
+/* Add new VAR to reg_alloc RA in REGION.  They must have compatible types.  */
+static void
+join_reg_alloc (struct lr_region *region, struct reg_alloc *ra, tree var)
+{
+  bool exist_p;
+  unsigned *slot;
+
+  gcc_assert (types_compatible_p (TREE_TYPE (var), ra->type));
+  gcc_assert (!bitmap_bit_p (ra->vars, SSA_NAME_VERSION (var)));
+  bitmap_set_bit (ra->vars, SSA_NAME_VERSION (var));
+  slot = &region->var_alloc_map->get_or_insert (var, &exist_p);
+  gcc_assert (!exist_p);
+  *slot = ra->id;
+}
+
+/* Find and return the reg_alloc for VAR in REGION.  Return NULL if no such
+   reg_alloc.  */
+static struct reg_alloc *
+find_reg_alloc (struct lr_region *region, tree var)
+{
+  unsigned *slot = region->var_alloc_map->get (var);
+  if (!slot)
+    return NULL;
+
+  gcc_assert (*slot < region->vallocs.length ());
+  return region->vallocs[*slot];
+}
+
+/* Dump all reg_allocs in REGION.  */
+static void
+dump_reg_allocs (FILE *file, struct lr_region *region)
+{
+  unsigned i, j;
+  bitmap_iterator bi;
+  struct reg_alloc *ra;
+
+  fprintf (file, "Reg_Alloc:\n");
+  for (i = 0; i < region->vallocs.length (); i++)
+    {
+      ra = region->vallocs[i];
+      fprintf (file, "  %d: ", ra->id);
+      EXECUTE_IF_SET_IN_BITMAP (ra->vars, 0, j, bi)
+	{
+	  print_generic_expr (file, ssa_name (j), TDF_SLIM);
+	  fprintf (file, " ");
+	}
+      fprintf (file, "\n");
+    }
+}
+
+/*Record reg_alloc for invariant VAR defined by STMT in REGION.  */
+static void
+record_reg_alloc_for_inv (struct lr_region *region, tree var, gimple *stmt)
+{
+  struct inv_entry **slot;
+  struct reg_alloc *ra = find_reg_alloc (region, var);
+  if (ra != NULL)
+    return;
+
+  slot = NULL;
+  if (is_gimple_assign (stmt) && gimple_assign_single_p (stmt))
+    {
+      /* Check the invariant table.  */
+      struct inv_entry ent;
+      ent.expr = gimple_assign_rhs1 (stmt);
+      ent.hash = iterative_hash_expr (ent.expr, 0);
+      slot = region->inv_table->find_slot (&ent, INSERT);
+      /* Record stmt's rhs in hash table if not exists yet.  This is to
+	 avoid counting loop invariant constant repeatly when it is not
+	 propagated.  */
+      if (*slot != NULL)
+	{
+	  gcc_assert ((*slot)->id < region->vallocs.length ());
+	  ra = region->vallocs[(*slot)->id];
+	  join_reg_alloc (region, ra, var);
+	  return;
+	}
+      *slot = new inv_entry ();
+      (*slot)->expr = ent.expr;
+      (*slot)->hash = ent.hash;
+    }
+  ra = create_reg_alloc (region, var);
+  /* Record it in invariant table if necessary.  */
+  if (slot != NULL && *slot != NULL)
+    (*slot)->id = ra->id;
+}
+
+/* Compute live out reg_allocs for REGION.  */
+static void
+compute_live_out_reg_allocs (struct lr_region *region)
+{
+  for (unsigned i = 0; i < region->vallocs.length (); i++)
+    {
+      unsigned j;
+      bitmap_iterator bi;
+      struct reg_alloc *ra = region->vallocs[i];
+
+      EXECUTE_IF_SET_IN_BITMAP (ra->vars, 0, j, bi)
+	{
+	  tree var = ssa_name (j);
+	  use_operand_p use_p;
+	  imm_use_iterator imm_iter;
+
+	  FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
+	    {
+	      gimple *use_stmt = USE_STMT (use_p);
+	      if (is_gimple_debug (use_stmt))
+		continue;
+
+	      basic_block use_bb = gimple_bb (use_stmt);
+	      unsigned use_bb_idx;
+	      if (get_bb_idx_in_region (region, use_bb, &use_bb_idx))
+		continue;
+
+	      /* Set reg_alloc as live out if it's defined in this region
+		 but used outside.  */
+	      bitmap_set_bit (region->live_out_allocs, ra->id);
+	      break;
+	    }
+	  if (bitmap_bit_p (region->live_out_allocs, ra->id))
+	    break;
+	}
+    }
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Live out reg_allocs: \n  ");
+      dump_bitmap (dump_file, region->live_out_allocs);
+    }
+}
+
+/* Create and return live range information for STMT in REGION.  */
+static struct stmt_lr_info *
+create_stmt_lr_info (struct lr_region *region, gimple *stmt)
+{
+  bool exist_p;
+  struct stmt_lr_info **slot;
+
+  slot = &region->stmt_lr_info_map->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;
+}
+
+/* Compute reg_allocs for REGION by coalescing ssa variables.  */
+static void
+compute_reg_allocs (struct lr_region *region)
+{
+  unsigned i, j;
+  gimple_stmt_iterator bsi;
+
+  for (i = 0; i < region->size; i++)
+    {
+      basic_block bb = region->body[i];
+      /* First create new reg_alloc for PHIs.  */
+      for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+	{
+	  gimple *phi = gsi_stmt (bsi);
+	  tree res = gimple_phi_result (phi);
+	  if (virtual_operand_p (res))
+	    continue;
+
+	  if (region->var_alloc_map->get (res) == NULL)
+	    create_reg_alloc (region, res);
+	}
+      /* Coalesce PHI args with existing reg_allocs.  This has to be done
+	 independently to avoid coalescing swapping PHIs like:
+
+	   loop_header:
+	     a = PHI <a, b>
+	     b = PHI <b, a>.  */
+      for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+	{
+	  gimple *phi = gsi_stmt (bsi);
+	  tree res = gimple_phi_result (phi);
+	  if (virtual_operand_p (res))
+	    continue;
+
+	  struct reg_alloc *ra = find_reg_alloc (region, res);
+	  gcc_assert (ra != NULL);
+	  for (j = 0; j < gimple_phi_num_args (phi); j++)
+	    {
+	      tree arg = gimple_phi_arg_def (phi, j);
+	      if (TREE_CODE (arg) == SSA_NAME
+		  && (find_reg_alloc (region, arg) == NULL))
+		join_reg_alloc (region, ra, arg);
+	    }
+	}
+      /* Now process all stmts.  */
+      for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+	{
+	  gimple *stmt = gsi_stmt (bsi);
+	  if (is_gimple_debug (stmt))
+	    continue;
+
+	  tree var;
+	  ssa_op_iter iter;
+	  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
+	    {
+	      if (find_reg_alloc (region, var) == NULL)
+		create_reg_alloc (region, var);
+	    }
+	  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
+	    {
+	      unsigned def_idx;
+	      basic_block def_bb;
+	      gimple *def_stmt = SSA_NAME_DEF_STMT (var);
+	      /* Create reg_alloc for ssa_var defined outside of region.  */
+	      if (gimple_code (def_stmt) == GIMPLE_NOP
+		  || ((def_bb = gimple_bb (def_stmt)) != NULL
+		      && !get_bb_idx_in_region (region, def_bb, &def_idx)))
+		record_reg_alloc_for_inv (region, var, def_stmt);
+	    }
+	}
+    }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    dump_reg_allocs (dump_file, region);
+
+  delete region->inv_table;
+  region->inv_table = NULL;
+}
+
+/* Update GEN/KILL bitmaps by backward executing STMT.  */
+static void
+update_gen_kill_by_stmt (struct lr_region *region, gimple *stmt,
+			 bitmap gen, bitmap kill)
+{
+  tree var;
+  ssa_op_iter iter;
+  struct reg_alloc *ra;
+
+  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
+    {
+      ra = find_reg_alloc (region, var);
+      gcc_assert (ra != NULL);
+      if (kill != NULL)
+	bitmap_set_bit (kill, ra->id);
+      bitmap_clear_bit (gen, ra->id);
+    }
+  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
+    {
+      ra = find_reg_alloc (region, var);
+      gcc_assert (ra != NULL);
+      bitmap_set_bit (gen, ra->id);
+    }
+}
+
+/* Update GEN/KILL bitmaps by backward executing PHI.  */
+static void
+update_gen_kill_by_phi (struct lr_region *region, gimple *phi,
+			bitmap gen, bitmap kill)
+{
+  tree res = gimple_phi_result (phi);
+  if (virtual_operand_p (res))
+    return;
+
+  struct reg_alloc *ra = find_reg_alloc (region, res);
+  gcc_assert (ra != NULL);
+  bitmap_set_bit (kill, ra->id);
+  bitmap_clear_bit (gen, ra->id);
+}
+
+/* Initialize live range information for BB in REGION.  */
+static void
+initialize_bb_lr_info (struct lr_region *region, basic_block bb)
+{
+  edge e;
+  edge_iterator ei;
+  gimple_stmt_iterator gsi;
+  unsigned i, idx;
+  struct bb_lr_info *bb_info;
+  bool in_region_p = get_bb_idx_in_region (region, bb, &idx);
+
+  gcc_assert (in_region_p);
+  bb_info = &region->bb_lr_info[idx];
+  bb_info->gen = BITMAP_ALLOC (NULL);
+  bb_info->kill = BITMAP_ALLOC (NULL);
+  bb_info->in = BITMAP_ALLOC (NULL);
+  bb_info->out = BITMAP_ALLOC (NULL);
+  bitmap_copy (bb_info->out, region->live_out_allocs);
+
+  /* Handle PHI arg as use of source basic block of the incoming edge.  */
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    {
+      unsigned dst_idx;
+      basic_block dst = e->dest;
+
+      if (get_bb_idx_in_region (region, dst, &dst_idx))
+	{
+	  for (gsi = gsi_start_phis (dst); !gsi_end_p (gsi); gsi_next (&gsi))
+	    {
+	      gimple *phi = gsi_stmt (gsi);
+	      if (virtual_operand_p (gimple_phi_result (phi)))
+		continue;
+
+	      for (i = 0; i < gimple_phi_num_args (phi); i++)
+		{
+		  tree arg = gimple_phi_arg_def (phi, i);
+		  if (TREE_CODE (arg) != SSA_NAME)
+		    continue;
+
+		  struct reg_alloc *arg_ra = find_reg_alloc (region, arg);
+		  gcc_assert (arg_ra != NULL);
+		  bitmap_set_bit (bb_info->gen, arg_ra->id);
+		}
+	    }
+	}
+    }
+
+  /* Compute local gen/kill information by reversely traversing stmts.  */
+  for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
+    {
+      gimple *stmt = gsi_stmt (gsi);
+      if (is_gimple_debug (stmt))
+	continue;
+
+      update_gen_kill_by_stmt (region, stmt, bb_info->gen, bb_info->kill);
+    }
+
+  /* And the phis -- the order of traversing does not matter.  */
+  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      gimple *phi = gsi_stmt (gsi);
+      update_gen_kill_by_phi (region, phi, bb_info->gen, bb_info->kill);
+    }
+}
+
+/* Update live range information for BB in REGION.  This is the update
+   function of live range data flow equation.  */
+static bool
+update_bb_lr_info (struct lr_region *region, basic_block bb)
+{
+  edge e;
+  edge_iterator ei;
+  unsigned idx, dst_idx;
+  struct bb_lr_info *bb_info, *dst_info;
+  bool in_region_p = get_bb_idx_in_region (region, bb, &idx);
+
+  gcc_assert (in_region_p);
+  bb_info = &region->bb_lr_info[idx];
+
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    if (get_bb_idx_in_region (region, e->dest, &dst_idx))
+      {
+	dst_info = &region->bb_lr_info[dst_idx];
+	(void) bitmap_ior_into (bb_info->out, dst_info->in);
+      }
+
+  return bitmap_ior_and_compl (bb_info->in, bb_info->gen,
+			       bb_info->out, bb_info->kill);
+}
+
+/* Dump live range information for REGION.  */
+static void
+dump_live_ranges (FILE *file, struct lr_region *region)
+{
+  fprintf (file, "BB Live Range Info:\n");
+  for (unsigned i = 0; i < region->size; i++)
+    {
+      basic_block bb = region->body[i];
+      struct bb_lr_info *bb_info = &region->bb_lr_info[i];
+
+      fprintf (file, "  bb %d:\n", bb->index);
+      fprintf (file, "    in: ");
+      dump_bitmap (file, bb_info->in);
+      fprintf (file, "    out: ");
+      dump_bitmap (file, bb_info->out);
+      fprintf (file, "    gen: ");
+      dump_bitmap (file, bb_info->gen);
+      fprintf (file, "    kill: ");
+      dump_bitmap (file, bb_info->kill);
+    }
+}
+
+/* Compute live range information for REGION.  */
+static void
+compute_live_ranges (struct lr_region *region)
+{
+  basic_block bb;
+  unsigned i, idx;
+  bitmap worklist = BITMAP_ALLOC (NULL);
+
+  compute_live_out_reg_allocs (region);
+
+  for (i = 0; i < region->size; i++)
+    initialize_bb_lr_info (region, region->body[i]);
+
+  /* Initialize start worklist for all exit edges.  */
+  for (i = 0; i < region->size; i++)
+    {
+      edge e;
+      edge_iterator ei;
+
+      FOR_EACH_EDGE (e, ei, region->body[i]->succs)
+	if (!get_bb_idx_in_region (region, e->dest, &idx))
+	  {
+	    bitmap_set_bit (worklist, i);
+	    break;
+	  }
+    }
+
+  /* Solve live range data flow problem.  */
+  while (!bitmap_empty_p (worklist))
+    {
+      edge e;
+      edge_iterator ei;
+
+      idx = bitmap_first_set_bit (worklist);
+      bitmap_clear_bit (worklist, idx);
+      bb = region->body[idx];
+      if (update_bb_lr_info (region, bb))
+	FOR_EACH_EDGE (e, ei, bb->preds)
+	  if (get_bb_idx_in_region (region, e->src, &idx))
+	    bitmap_set_bit (worklist, idx);
+    }
+  BITMAP_FREE (worklist);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    dump_live_ranges (dump_file, region);
+}
+
+/* Compute live range information all stmts in REGION.  */
+static void
+compute_stmt_lr_info (struct lr_region *region)
+{
+  unsigned i;
+  gimple *stmt;
+  basic_block bb;
+  gimple_stmt_iterator bsi;
+  struct stmt_lr_info *stmt_info, **slot;
+  struct bb_lr_info *bb_info;
+  bitmap live_ranges = BITMAP_ALLOC (NULL);
+
+  for (i = 0; i < region->size; i++)
+    {
+      bb = region->body[i];
+      bb_info = &region->bb_lr_info[i];
+      bitmap_copy (live_ranges, bb_info->out);
+
+      for (bsi = gsi_last_bb (bb); !gsi_end_p (bsi); gsi_prev (&bsi))
+	{
+	  stmt = gsi_stmt (bsi);
+	  stmt_info = create_stmt_lr_info (region, stmt);
+	  /* No need to compute live range information for debug stmt.  */
+	  if (is_gimple_debug (stmt))
+	    continue;
+
+	  stmt_info->lr_after_stmt = BITMAP_ALLOC (NULL);
+	  bitmap_copy (stmt_info->lr_after_stmt, live_ranges);
+	  update_gen_kill_by_stmt (region, stmt, live_ranges, NULL);
+	}
+    }
+  BITMAP_FREE (live_ranges);
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Stmt Live Range:\n");
+      for (i = 0; i < region->size; i++)
+	{
+	  bb = region->body[i];
+
+	  for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+	    {
+	      stmt = gsi_stmt (bsi);
+	      if (is_gimple_debug (stmt))
+		continue;
+
+	      slot = region->stmt_lr_info_map->get (stmt);
+	      fprintf (dump_file, "  ");
+	      print_gimple_stmt (dump_file, stmt, 0, 0);
+	      fprintf (dump_file, "    ");
+	      dump_bitmap (dump_file, (*slot)->lr_after_stmt);
+	    }
+	}
+    }
+}
+
+/* Compute register pression information for REGION.  */
+static void
+compute_reg_pressure (struct lr_region *region)
+{
+  int k;
+  unsigned i, j;
+  gimple *stmt;
+  basic_block bb;
+  bitmap_iterator bi;
+  gimple_stmt_iterator bsi;
+  struct bb_lr_info *bb_info;
+  unsigned reg_pressure[N_REG_CLASSES];
+
+  for (i = 0; i < region->size; i++)
+    {
+      bb = region->body[i];
+      bb_info = &region->bb_lr_info[i];
+
+      EXECUTE_IF_SET_IN_BITMAP (bb_info->out, 0, j, bi)
+	{
+	  struct reg_alloc *ra = region->vallocs[j];
+	  unsigned reg_class = ira_mode_classes[TYPE_MODE (ra->type)];
+	  bb_info->max_pressure[reg_class]++;
+	}
+      bool last_stmt_p = true;
+      for (bsi = gsi_last_bb (bb); !gsi_end_p (bsi); gsi_prev (&bsi))
+	{
+	  stmt = gsi_stmt (bsi);
+	  if (is_gimple_debug (stmt))
+	    continue;
+
+	  if (last_stmt_p)
+	    {
+	      last_stmt_p = false;
+	      continue;
+	    }
+	  memset (reg_pressure, 0, N_REG_CLASSES * sizeof (unsigned));
+	  struct stmt_lr_info **slot = region->stmt_lr_info_map->get (stmt);
+	  gcc_assert (slot != NULL);
+	  EXECUTE_IF_SET_IN_BITMAP ((*slot)->lr_after_stmt, 0, j, bi)
+	    {
+	      struct reg_alloc *ra = region->vallocs[j];
+	      unsigned reg_class = ira_mode_classes[TYPE_MODE (ra->type)];
+	      reg_pressure[reg_class]++;
+	    }
+	  for (k = 0; k < N_REG_CLASSES; k++)
+	    if (reg_pressure[k] > bb_info->max_pressure[k])
+	      bb_info->max_pressure[k] = reg_pressure[k];
+	}
+      for (k = 0; k < N_REG_CLASSES; k++)
+	if (bb_info->max_pressure[k] > region->max_pressure[k])
+	  region->max_pressure[k] = bb_info->max_pressure[k];
+    }
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Reg Pressure:\n");
+      for (i = 0; i < region->size; i++)
+	{
+	  bb = region->body[i];
+	  bb_info = &region->bb_lr_info[i];
+	  fprintf (dump_file, "  BB %d:\n", bb->index);
+	  for (k = 0; k < N_REG_CLASSES; k++)
+	    {
+	      if (bb_info->max_pressure[k] != 0)
+		fprintf (dump_file, "    %s: %d\n",
+			 reg_class_names[k], bb_info->max_pressure[k]);
+	    }
+	}
+    }
+}
+
+/* Check if PRESSURE is high according to target information about available
+   registers.  */
+static inline bool
+high_reg_pressure (unsigned *pressure)
+{
+  int k;
+
+  gcc_assert (pressure != NULL);
+
+  for (k = 0; k < N_REG_CLASSES; k++)
+    if (pressure[k] > 8 && pressure[k] > target_avail_regs[k])
+      return true;
+
+  return false;
+}
+
+/*Compute maximum register pressure information for LOOP and store it in
+  MAX_PRESSURE.  If HIGH_PRESSURE_P is not NULL, set it to true if loop
+  has high register pressure.  */
+void
+compute_loop_reg_pressure (struct loop *loop, unsigned *max_pressure,
+			   bool *high_pressure_p)
+{
+  struct lr_region *region;
+
+  region = create_loop_lr_region (loop);
+  compute_reg_allocs (region);
+  compute_live_ranges (region);
+  compute_stmt_lr_info (region);
+  compute_reg_pressure (region);
+  if (high_pressure_p != NULL)
+    *high_pressure_p = high_reg_pressure (region->max_pressure);
+
+  gcc_assert (max_pressure != NULL);
+  memcpy (max_pressure, region->max_pressure,
+	  sizeof (unsigned) * N_REG_CLASSES);
+  free_lr_region (region);
+}
diff --git a/gcc/tree-ssa-regpressure.h b/gcc/tree-ssa-regpressure.h
new file mode 100644
index 0000000..a288921
--- /dev/null
+++ b/gcc/tree-ssa-regpressure.h
@@ -0,0 +1,21 @@ 
+/* Header file for Reg Pressure Model and Live Range Shrinking Optimization
+   on TREE SSA.
+   Copyright (C) 2017 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+extern void compute_loop_reg_pressure (struct loop*, unsigned*, bool*);