/* HSAIL IL Register allocation and out-of-SSA.
   Copyright (C) 2013-2016 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);

  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);
    }
}