[hsa 10/10] HSA register allocator

[Martin Jambor <mjambor at suse dot cz>]

Hi,

because HSA backend is not based on RTL,we need our own, and it is in
this patch.  The allocator has been written by Michael Matz and I have
put it into a separate email so that I can add him to CC, because he
is much better suited to answer any questions or review comments.

Thanks,

Martin


2015-12-04  Michael Matz <matz@suse.de>
	    Martin Jambor  <mjambor@suse.cz>

	* hsa-regalloc.c: New file.

diff --git a/gcc/hsa-regalloc.c b/gcc/hsa-regalloc.c
new file mode 100644
index 0000000..9db4c1d
--- /dev/null
+++ b/gcc/hsa-regalloc.c
@@ -0,0 +1,719 @@
+/* HSAIL IL Register allocation and out-of-SSA.
+   Copyright (C) 2013-15 Free Software Foundation, Inc.
+   Contributed by Michael Matz <matz@suse.de>
+
+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 "tm.h"
+#include "is-a.h"
+#include "vec.h"
+#include "tree.h"
+#include "dominance.h"
+#include "cfg.h"
+#include "cfganal.h"
+#include "function.h"
+#include "bitmap.h"
+#include "dumpfile.h"
+#include "cgraph.h"
+#include "print-tree.h"
+#include "cfghooks.h"
+#include "symbol-summary.h"
+#include "hsa.h"
+
+
+/* Process a PHI node PHI of basic block BB as a part of naive out-f-ssa.  */
+
+static void
+naive_process_phi (hsa_insn_phi *phi)
+{
+  unsigned count = phi->operand_count ();
+  for (unsigned i = 0; i < count; i++)
+    {
+      gcc_checking_assert (phi->get_op (i));
+      hsa_op_base *op = phi->get_op (i);
+      hsa_bb *hbb;
+      edge e;
+
+      if (!op)
+	break;
+
+      e = EDGE_PRED (phi->m_bb, i);
+      if (single_succ_p (e->src))
+	hbb = hsa_bb_for_bb (e->src);
+      else
+	{
+	  basic_block old_dest = e->dest;
+	  hbb = hsa_init_new_bb (split_edge (e));
+
+	  /* If switch insn used this edge, fix jump table.  */
+	  hsa_bb *source = hsa_bb_for_bb (e->src);
+	  hsa_insn_sbr *sbr;
+	  if (source->m_last_insn
+	      && (sbr = dyn_cast <hsa_insn_sbr *> (source->m_last_insn)))
+	    sbr->replace_all_labels (old_dest, hbb->m_bb);
+	}
+
+      hsa_build_append_simple_mov (phi->m_dest, op, hbb);
+    }
+}
+
+/* Naive out-of SSA.  */
+
+static void
+naive_outof_ssa (void)
+{
+  basic_block bb;
+
+  hsa_cfun->m_in_ssa = false;
+
+  FOR_ALL_BB_FN (bb, cfun)
+  {
+    hsa_bb *hbb = hsa_bb_for_bb (bb);
+    hsa_insn_phi *phi;
+
+    for (phi = hbb->m_first_phi;
+	 phi;
+	 phi = phi->m_next ? as_a <hsa_insn_phi *> (phi->m_next): NULL)
+      naive_process_phi (phi);
+
+    /* Zap PHI nodes, they will be deallocated when everything else will.  */
+    hbb->m_first_phi = NULL;
+    hbb->m_last_phi = NULL;
+  }
+}
+
+/* Return register class number for the given HSA TYPE.  0 means the 'c' one
+   bit register class, 1 means 's' 32 bit class, 2 stands for 'd' 64 bit class
+   and 3 for 'q' 128 bit class.  */
+
+static int
+m_reg_class_for_type (BrigType16_t type)
+{
+  switch (type)
+    {
+    case BRIG_TYPE_B1:
+      return 0;
+
+    case BRIG_TYPE_U8:
+    case BRIG_TYPE_U16:
+    case BRIG_TYPE_U32:
+    case BRIG_TYPE_S8:
+    case BRIG_TYPE_S16:
+    case BRIG_TYPE_S32:
+    case BRIG_TYPE_F16:
+    case BRIG_TYPE_F32:
+    case BRIG_TYPE_B8:
+    case BRIG_TYPE_B16:
+    case BRIG_TYPE_B32:
+    case BRIG_TYPE_U8X4:
+    case BRIG_TYPE_S8X4:
+    case BRIG_TYPE_U16X2:
+    case BRIG_TYPE_S16X2:
+    case BRIG_TYPE_F16X2:
+      return 1;
+
+    case BRIG_TYPE_U64:
+    case BRIG_TYPE_S64:
+    case BRIG_TYPE_F64:
+    case BRIG_TYPE_B64:
+    case BRIG_TYPE_U8X8:
+    case BRIG_TYPE_S8X8:
+    case BRIG_TYPE_U16X4:
+    case BRIG_TYPE_S16X4:
+    case BRIG_TYPE_F16X4:
+    case BRIG_TYPE_U32X2:
+    case BRIG_TYPE_S32X2:
+    case BRIG_TYPE_F32X2:
+      return 2;
+
+    case BRIG_TYPE_B128:
+    case BRIG_TYPE_U8X16:
+    case BRIG_TYPE_S8X16:
+    case BRIG_TYPE_U16X8:
+    case BRIG_TYPE_S16X8:
+    case BRIG_TYPE_F16X8:
+    case BRIG_TYPE_U32X4:
+    case BRIG_TYPE_U64X2:
+    case BRIG_TYPE_S32X4:
+    case BRIG_TYPE_S64X2:
+    case BRIG_TYPE_F32X4:
+    case BRIG_TYPE_F64X2:
+      return 3;
+
+    default:
+      gcc_unreachable ();
+    }
+}
+
+/* If the Ith operands of INSN is or contains a register (in an address),
+   return the address of that register operand.  If not return NULL.  */
+
+static hsa_op_reg **
+insn_reg_addr (hsa_insn_basic *insn, int i)
+{
+  hsa_op_base *op = insn->get_op (i);
+  if (!op)
+    return NULL;
+  hsa_op_reg *reg = dyn_cast <hsa_op_reg *> (op);
+  if (reg)
+    return (hsa_op_reg **) insn->get_op_addr (i);
+  hsa_op_address *addr = dyn_cast <hsa_op_address *> (op);
+  if (addr && addr->m_reg)
+    return &addr->m_reg;
+  return NULL;
+}
+
+struct m_reg_class_desc
+{
+  unsigned next_avail, max_num;
+  unsigned used_num, max_used;
+  uint64_t used[2];
+  char cl_char;
+};
+
+/* Rewrite the instructions in BB to observe spilled live ranges.
+   CLASSES is the global register class state.  */
+
+static void
+rewrite_code_bb (basic_block bb, struct m_reg_class_desc *classes)
+{
+  hsa_bb *hbb = hsa_bb_for_bb (bb);
+  hsa_insn_basic *insn, *next_insn;
+
+  for (insn = hbb->m_first_insn; insn; insn = next_insn)
+    {
+      next_insn = insn->m_next;
+      unsigned count = insn->operand_count ();
+      for (unsigned i = 0; i < count; i++)
+	{
+	  gcc_checking_assert (insn->get_op (i));
+	  hsa_op_reg **regaddr = insn_reg_addr (insn, i);
+
+	  if (regaddr)
+	    {
+	      hsa_op_reg *reg = *regaddr;
+	      if (reg->m_reg_class)
+		continue;
+	      gcc_assert (reg->m_spill_sym);
+
+	      int cl = m_reg_class_for_type (reg->m_type);
+	      hsa_op_reg *tmp, *tmp2;
+	      if (insn->op_output_p (i))
+		tmp = hsa_spill_out (insn, reg, &tmp2);
+	      else
+		tmp = hsa_spill_in (insn, reg, &tmp2);
+
+	      *regaddr = tmp;
+
+	      tmp->m_reg_class = classes[cl].cl_char;
+	      tmp->m_hard_num = (char) (classes[cl].max_num + i);
+	      if (tmp2)
+		{
+		  gcc_assert (cl == 0);
+		  tmp2->m_reg_class = classes[1].cl_char;
+		  tmp2->m_hard_num = (char) (classes[1].max_num + i);
+		}
+	    }
+	}
+    }
+}
+
+/* Dump current function to dump file F, with info specific
+   to register allocation.  */
+
+void
+dump_hsa_cfun_regalloc (FILE *f)
+{
+  basic_block bb;
+
+  fprintf (f, "\nHSAIL IL for %s\n", hsa_cfun->m_name);
+
+  FOR_ALL_BB_FN (bb, cfun)
+  {
+    hsa_bb *hbb = (struct hsa_bb *) bb->aux;
+    bitmap_print (dump_file, hbb->m_livein, "m_livein  ", "\n");
+    dump_hsa_bb (f, hbb);
+    bitmap_print (dump_file, hbb->m_liveout, "m_liveout ", "\n");
+  }
+}
+
+/* Given the global register allocation state CLASSES and a
+   register REG, try to give it a hardware register.  If successful,
+   store that hardreg in REG and return it, otherwise return -1.
+   Also changes CLASSES to accommodate for the allocated register.  */
+
+static int
+try_alloc_reg (struct m_reg_class_desc *classes, hsa_op_reg *reg)
+{
+  int cl = m_reg_class_for_type (reg->m_type);
+  int ret = -1;
+  if (classes[1].used_num + classes[2].used_num * 2 + classes[3].used_num * 4
+      >= 128 - 5)
+    return -1;
+  if (classes[cl].used_num < classes[cl].max_num)
+    {
+      unsigned int i;
+      classes[cl].used_num++;
+      if (classes[cl].used_num > classes[cl].max_used)
+	classes[cl].max_used = classes[cl].used_num;
+      for (i = 0; i < classes[cl].used_num; i++)
+	if (! (classes[cl].used[i / 64] & (((uint64_t)1) << (i & 63))))
+	  break;
+      ret = i;
+      classes[cl].used[i / 64] |= (((uint64_t)1) << (i & 63));
+      reg->m_reg_class = classes[cl].cl_char;
+      reg->m_hard_num = i;
+    }
+  return ret;
+}
+
+/* Free up hardregs used by REG, into allocation state CLASSES.  */
+
+static void
+free_reg (struct m_reg_class_desc *classes, hsa_op_reg *reg)
+{
+  int cl = m_reg_class_for_type (reg->m_type);
+  int ret = reg->m_hard_num;
+  gcc_assert (reg->m_reg_class == classes[cl].cl_char);
+  classes[cl].used_num--;
+  classes[cl].used[ret / 64] &= ~(((uint64_t)1) << (ret & 63));
+}
+
+/* Note that the live range for REG ends at least at END.  */
+
+static void
+note_lr_end (hsa_op_reg *reg, int end)
+{
+  if (reg->m_lr_end < end)
+    reg->m_lr_end = end;
+}
+
+/* Note that the live range for REG starts at least at BEGIN.  */
+
+static void
+note_lr_begin (hsa_op_reg *reg, int begin)
+{
+  if (reg->m_lr_begin > begin)
+    reg->m_lr_begin = begin;
+}
+
+/* Given two registers A and B, return -1, 0 or 1 if A's live range
+   starts before, at or after B's live range.  */
+
+static int
+cmp_begin (const void *a, const void *b)
+{
+  const hsa_op_reg * const *rega = (const hsa_op_reg * const *)a;
+  const hsa_op_reg * const *regb = (const hsa_op_reg * const *)b;
+  int ret;
+  if (rega == regb)
+    return 0;
+  ret = (*rega)->m_lr_begin - (*regb)->m_lr_begin;
+  if (ret)
+    return ret;
+  return ((*rega)->m_order - (*regb)->m_order);
+}
+
+/* Given two registers REGA and REGB, return true if REGA's
+   live range ends after REGB's.  This results in a sorting order
+   with earlier end points at the end.  */
+
+static bool
+cmp_end (hsa_op_reg * const &rega, hsa_op_reg * const &regb)
+{
+  int ret;
+  if (rega == regb)
+    return false;
+  ret = (regb)->m_lr_end - (rega)->m_lr_end;
+  if (ret)
+    return ret < 0;
+  return (((regb)->m_order - (rega)->m_order)) < 0;
+}
+
+/* Expire all old intervals in ACTIVE (a per-regclass vector),
+   that is, those that end before the interval REG starts.  Give
+   back resources freed so into the state CLASSES.  */
+
+static void
+expire_old_intervals (hsa_op_reg *reg, vec<hsa_op_reg*> *active,
+		      struct m_reg_class_desc *classes)
+{
+  for (int i = 0; i < 4; i++)
+    while (!active[i].is_empty ())
+      {
+	hsa_op_reg *a = active[i].pop ();
+	if (a->m_lr_end > reg->m_lr_begin)
+	  {
+	    active[i].quick_push (a);
+	    break;
+	  }
+	free_reg (classes, a);
+      }
+}
+
+/* The interval REG didn't get a hardreg.  Spill it or one of those
+   from ACTIVE (if the latter, then REG will become allocated to the
+   hardreg that formerly was used by it).  */
+
+static void
+spill_at_interval (hsa_op_reg *reg, vec<hsa_op_reg*> *active)
+{
+  int cl = m_reg_class_for_type (reg->m_type);
+  gcc_assert (!active[cl].is_empty ());
+  hsa_op_reg *cand = active[cl][0];
+  if (cand->m_lr_end > reg->m_lr_end)
+    {
+      reg->m_reg_class = cand->m_reg_class;
+      reg->m_hard_num = cand->m_hard_num;
+      active[cl].ordered_remove (0);
+      unsigned place = active[cl].lower_bound (reg, cmp_end);
+      active[cl].quick_insert (place, reg);
+    }
+  else
+    cand = reg;
+
+  gcc_assert (!cand->m_spill_sym);
+  BrigType16_t type = cand->m_type;
+  if (type == BRIG_TYPE_B1)
+    type = BRIG_TYPE_U8;
+  cand->m_reg_class = 0;
+  cand->m_spill_sym = hsa_get_spill_symbol (type);
+  cand->m_spill_sym->m_name_number = cand->m_order;
+}
+
+/* Given the global register state CLASSES allocate all HSA virtual
+   registers either to hardregs or to a spill symbol.  */
+
+static void
+linear_scan_regalloc (struct m_reg_class_desc *classes)
+{
+  /* Compute liveness.  */
+  bool changed;
+  int i, n;
+  int insn_order;
+  int *bbs = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
+  bitmap work = BITMAP_ALLOC (NULL);
+  vec<hsa_op_reg*> ind2reg = vNULL;
+  vec<hsa_op_reg*> active[4] = {vNULL, vNULL, vNULL, vNULL};
+  hsa_insn_basic *m_last_insn;
+
+  /* We will need the reverse post order for linearization,
+     and the post order for liveness analysis, which is the same
+     backward.  */
+  n = pre_and_rev_post_order_compute (NULL, bbs, true);
+  ind2reg.safe_grow_cleared (hsa_cfun->m_reg_count);
+
+  /* Give all instructions a linearized number, at the same time
+     build a mapping from register index to register.  */
+  insn_order = 1;
+  for (i = 0; i < n; i++)
+    {
+      basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bbs[i]);
+      hsa_bb *hbb = hsa_bb_for_bb (bb);
+      hsa_insn_basic *insn;
+      for (insn = hbb->m_first_insn; insn; insn = insn->m_next)
+	{
+	  unsigned opi;
+	  insn->m_number = insn_order++;
+	  for (opi = 0; opi < insn->operand_count (); opi++)
+	    {
+	      gcc_checking_assert (insn->get_op (opi));
+	      hsa_op_reg **regaddr = insn_reg_addr (insn, opi);
+	      if (regaddr)
+		ind2reg[(*regaddr)->m_order] = *regaddr;
+	    }
+	}
+    }
+
+  /* Initialize all live ranges to [after-end, 0).  */
+  for (i = 0; i < hsa_cfun->m_reg_count; i++)
+    if (ind2reg[i])
+      ind2reg[i]->m_lr_begin = insn_order, ind2reg[i]->m_lr_end = 0;
+
+  /* Classic liveness analysis, as long as something changes:
+       m_liveout is union (m_livein of successors)
+       m_livein is m_liveout minus defs plus uses.  */
+  do
+    {
+      changed = false;
+      for (i = n - 1; i >= 0; i--)
+	{
+	  edge e;
+	  edge_iterator ei;
+	  basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bbs[i]);
+	  hsa_bb *hbb = hsa_bb_for_bb (bb);
+
+	  /* Union of successors m_livein (or empty if none).  */
+	  bool first = true;
+	  FOR_EACH_EDGE (e, ei, bb->succs)
+	    if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
+	      {
+		hsa_bb *succ = hsa_bb_for_bb (e->dest);
+		if (first)
+		  {
+		    bitmap_copy (work, succ->m_livein);
+		    first = false;
+		  }
+		else
+		  bitmap_ior_into (work, succ->m_livein);
+	      }
+	  if (first)
+	    bitmap_clear (work);
+
+	  bitmap_copy (hbb->m_liveout, work);
+
+	  /* Remove defs, include uses in a backward insn walk.  */
+	  hsa_insn_basic *insn;
+	  for (insn = hbb->m_last_insn; insn; insn = insn->m_prev)
+	    {
+	      unsigned opi;
+	      unsigned ndefs = insn->input_count ();
+	      for (opi = 0; opi < ndefs && insn->get_op (opi); opi++)
+		{
+		  gcc_checking_assert (insn->get_op (opi));
+		  hsa_op_reg **regaddr = insn_reg_addr (insn, opi);
+		  if (regaddr)
+		    bitmap_clear_bit (work, (*regaddr)->m_order);
+		}
+	      for (; opi < insn->operand_count (); opi++)
+		{
+		  gcc_checking_assert (insn->get_op (opi));
+		  hsa_op_reg **regaddr = insn_reg_addr (insn, opi);
+		  if (regaddr)
+		    bitmap_set_bit (work, (*regaddr)->m_order);
+		}
+	    }
+
+	  /* Note if that changed something.  */
+	  if (bitmap_ior_into (hbb->m_livein, work))
+	    changed = true;
+	}
+    }
+  while (changed);
+
+  /* Make one pass through all instructions in linear order,
+     noting and merging possible live range start and end points.  */
+  m_last_insn = NULL;
+  for (i = n - 1; i >= 0; i--)
+    {
+      basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bbs[i]);
+      hsa_bb *hbb = hsa_bb_for_bb (bb);
+      hsa_insn_basic *insn;
+      int after_end_number;
+      unsigned bit;
+      bitmap_iterator bi;
+
+      if (m_last_insn)
+	after_end_number = m_last_insn->m_number;
+      else
+	after_end_number = insn_order;
+      /* Everything live-out in this BB has at least an end point
+         after us. */
+      EXECUTE_IF_SET_IN_BITMAP (hbb->m_liveout, 0, bit, bi)
+	note_lr_end (ind2reg[bit], after_end_number);
+
+      for (insn = hbb->m_last_insn; insn; insn = insn->m_prev)
+	{
+	  unsigned opi;
+	  unsigned ndefs = insn->input_count ();
+	  for (opi = 0; opi < insn->operand_count (); opi++)
+	    {
+	      gcc_checking_assert (insn->get_op (opi));
+	      hsa_op_reg **regaddr = insn_reg_addr (insn, opi);
+	      if (regaddr)
+		{
+		  hsa_op_reg *reg = *regaddr;
+		  if (opi < ndefs)
+		    note_lr_begin (reg, insn->m_number);
+		  else
+		    note_lr_end (reg, insn->m_number);
+		}
+	    }
+	}
+
+      /* Everything live-in in this BB has a start point before
+         our first insn.  */
+      int before_start_number;
+      if (hbb->m_first_insn)
+	before_start_number = hbb->m_first_insn->m_number;
+      else
+	before_start_number = after_end_number;
+      before_start_number--;
+      EXECUTE_IF_SET_IN_BITMAP (hbb->m_livein, 0, bit, bi)
+	note_lr_begin (ind2reg[bit], before_start_number);
+
+      if (hbb->m_first_insn)
+	m_last_insn = hbb->m_first_insn;
+    }
+
+  for (i = 0; i < hsa_cfun->m_reg_count; i++)
+    if (ind2reg[i])
+      {
+	/* All regs that have still their start at after all code actually
+	   are defined at the start of the routine (prologue).  */
+	if (ind2reg[i]->m_lr_begin == insn_order)
+	  ind2reg[i]->m_lr_begin = 0;
+	/* All regs that have no use but a def will have lr_end == 0, 
+	   they are actually live from def until after the insn they are
+	   defined in.  */
+	if (ind2reg[i]->m_lr_end == 0)
+	  ind2reg[i]->m_lr_end = ind2reg[i]->m_lr_begin + 1;
+      }
+
+  /* Sort all intervals by increasing start point.  */
+  gcc_assert (ind2reg.length () == (size_t) hsa_cfun->m_reg_count);
+
+#ifdef ENABLE_CHECKING
+  for (unsigned i = 0; i < ind2reg.length (); i++)
+    gcc_assert (ind2reg[i]);
+#endif
+
+  ind2reg.qsort (cmp_begin);
+  for (i = 0; i < 4; i++)
+    active[i].reserve_exact (hsa_cfun->m_reg_count);
+
+  /* Now comes the linear scan allocation.  */
+  for (i = 0; i < hsa_cfun->m_reg_count; i++)
+    {
+      hsa_op_reg *reg = ind2reg[i];
+      if (!reg)
+	continue;
+      expire_old_intervals (reg, active, classes);
+      int cl = m_reg_class_for_type (reg->m_type);
+      if (try_alloc_reg (classes, reg) >= 0)
+	{
+	  unsigned place = active[cl].lower_bound (reg, cmp_end);
+	  active[cl].quick_insert (place, reg);
+	}
+      else
+	spill_at_interval (reg, active);
+
+      /* Some interesting dumping as we go.  */
+      if (dump_file)
+	{
+	  fprintf (dump_file, "  reg%d: [%5d, %5d)->",
+		   reg->m_order, reg->m_lr_begin, reg->m_lr_end);
+	  if (reg->m_reg_class)
+	    fprintf (dump_file, "$%c%i", reg->m_reg_class, reg->m_hard_num);
+	  else
+	    fprintf (dump_file, "[%%__%s_%i]",
+		     hsa_seg_name (reg->m_spill_sym->m_segment),
+		     reg->m_spill_sym->m_name_number);
+	  for (int cl = 0; cl < 4; cl++)
+	    {
+	      bool first = true;
+	      hsa_op_reg *r;
+	      fprintf (dump_file, " {");
+	      for (int j = 0; active[cl].iterate (j, &r); j++)
+		if (first)
+		  {
+		    fprintf (dump_file, "%d", r->m_order);
+		    first = false;
+		  }
+		else
+		  fprintf (dump_file, ", %d", r->m_order);
+	      fprintf (dump_file, "}");
+	    }
+	  fprintf (dump_file, "\n");
+	}
+    }
+
+  BITMAP_FREE (work);
+  free (bbs);
+
+  if (dump_file)
+    {
+      fprintf (dump_file, "------- After liveness: -------\n");
+      dump_hsa_cfun_regalloc (dump_file);
+      fprintf (dump_file, "  ----- Intervals:\n");
+      for (i = 0; i < hsa_cfun->m_reg_count; i++)
+	{
+	  hsa_op_reg *reg = ind2reg[i];
+	  if (!reg)
+	    continue;
+	  fprintf (dump_file, "  reg%d: [%5d, %5d)->", reg->m_order,
+		   reg->m_lr_begin, reg->m_lr_end);
+	  if (reg->m_reg_class)
+	    fprintf (dump_file, "$%c%i\n", reg->m_reg_class, reg->m_hard_num);
+	  else
+	    fprintf (dump_file, "[%%__%s_%i]\n",
+		     hsa_seg_name (reg->m_spill_sym->m_segment),
+		     reg->m_spill_sym->m_name_number);
+	}
+    }
+
+  for (i = 0; i < 4; i++)
+    active[i].release ();
+  ind2reg.release ();
+}
+
+/* Entry point for register allocation.  */
+
+static void
+regalloc (void)
+{
+  basic_block bb;
+  m_reg_class_desc classes[4];
+
+  /* If there are no registers used in the function, exit right away. */
+  if (hsa_cfun->m_reg_count == 0)
+    return;
+
+  memset (classes, 0, sizeof (classes));
+  classes[0].next_avail = 0;
+  classes[0].max_num = 7;
+  classes[0].cl_char = 'c';
+  classes[1].cl_char = 's';
+  classes[2].cl_char = 'd';
+  classes[3].cl_char = 'q';
+
+  for (int i = 1; i < 4; i++)
+    {
+      classes[i].next_avail = 0;
+      classes[i].max_num = 20;
+    }
+
+  linear_scan_regalloc (classes);
+
+  FOR_ALL_BB_FN (bb, cfun)
+    rewrite_code_bb (bb, classes);
+}
+
+/* Out of SSA and register allocation on HSAIL IL.  */
+
+void
+hsa_regalloc (void)
+{
+  naive_outof_ssa ();
+
+  if (dump_file)
+    {
+      fprintf (dump_file, "------- After out-of-SSA: -------\n");
+      dump_hsa_cfun (dump_file);
+    }
+
+  regalloc ();
+
+  if (dump_file)
+    {
+      fprintf (dump_file, "------- After register allocation: -------\n");
+      dump_hsa_cfun (dump_file);
+    }
+}