gcc/hsa-regalloc.c - gcc - Git at Google

 /* HSAIL IL Register allocation and out-of-SSA.
    Copyright (C) 2013-2018 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 "basic-block.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-common.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, const vec<edge> &predecessors)
 {
   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 = predecessors[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;

     /* naive_process_phi can call split_edge on an incoming edge which order if
        the incoming edges to the basic block and thus make it inconsistent with
        the ordering of PHI arguments, so we collect them in advance.  */
     auto_vec<edge, 8> predecessors;
     unsigned pred_count = EDGE_COUNT (bb->preds);
     for (unsigned i = 0; i < pred_count; i++)
       predecessors.safe_push (EDGE_PRED (bb, i));

     for (phi = hbb->m_first_phi;
 	 phi;
 	 phi = phi->m_next ? as_a <hsa_insn_phi *> (phi->m_next) : NULL)
       naive_process_phi (phi, predecessors);

     /* 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);

   if (flag_checking)
     for (unsigned i = 0; i < ind2reg.length (); i++)
       gcc_assert (ind2reg[i]);

   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 && (dump_flags & TDF_DETAILS))
 	{
 	  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 && (dump_flags & TDF_DETAILS))
     {
       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)
 {
   hsa_cfun->update_dominance ();
   naive_outof_ssa ();

   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       fprintf (dump_file, "------- After out-of-SSA: -------\n");
       dump_hsa_cfun (dump_file);
     }

   regalloc ();

   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       fprintf (dump_file, "------- After register allocation: -------\n");
       dump_hsa_cfun (dump_file);
     }
 }
	/* HSAIL IL Register allocation and out-of-SSA.
	Copyright (C) 2013-2018 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 "basic-block.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-common.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, const vec<edge> &predecessors)
	{
	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 = predecessors[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;

	/* naive_process_phi can call split_edge on an incoming edge which order if
	the incoming edges to the basic block and thus make it inconsistent with
	the ordering of PHI arguments, so we collect them in advance. */
	auto_vec<edge, 8> predecessors;
	unsigned pred_count = EDGE_COUNT (bb->preds);
	for (unsigned i = 0; i < pred_count; i++)
	predecessors.safe_push (EDGE_PRED (bb, i));

	for (phi = hbb->m_first_phi;
	phi;
	phi = phi->m_next ? as_a <hsa_insn_phi *> (phi->m_next) : NULL)
	naive_process_phi (phi, predecessors);

	/* 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);

	if (flag_checking)
	for (unsigned i = 0; i < ind2reg.length (); i++)
	gcc_assert (ind2reg[i]);

	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 && (dump_flags & TDF_DETAILS))
	{
	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 && (dump_flags & TDF_DETAILS))
	{
	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)
	{
	hsa_cfun->update_dominance ();
	naive_outof_ssa ();

	if (dump_file && (dump_flags & TDF_DETAILS))
	{
	fprintf (dump_file, "------- After out-of-SSA: -------\n");
	dump_hsa_cfun (dump_file);
	}

	regalloc ();

	if (dump_file && (dump_flags & TDF_DETAILS))
	{
	fprintf (dump_file, "------- After register allocation: -------\n");
	dump_hsa_cfun (dump_file);
	}
	}