Subversion Repositories or1k

/* insn.c -- OpenRISC Custom Unit Compiler, instruction support

 *    Copyright (C) 2002 Marko Mlinar, markom@opencores.org

 *

 *    This file is part of OpenRISC 1000 Architectural Simulator.

 *

 *    This program 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 2 of the License, or

 *    (at your option) any later version.

 *

 *    This program 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 this program; if not, write to the Free Software

 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */

#include <stdio.h>

#include <stdlib.h>

#include <stdarg.h>

#include <assert.h>

#include "cuc.h"

#include "insn.h"

/* Table of known instructions.  Watch out for indexes I_*! */

const cuc_known_insn known[II_LAST + 1] = {

{"add", 1, "assign \1 = \2 + \3;"},

{"sub", 0, "assign \1 = \2 - \3;"},

{"and", 1, "assign \1 = \2 & \3;"},

{"or",  1, "assign \1 = \2 | \3;"},

{"xor", 1, "assign \1 = \2 ^ \3;"},

{"mul", 1, "assign \1 = \2 * \3;"},

{"srl", 0, "assign \1 = \2 >> \3;"},

{"sll", 0, "assign \1 = \2 << \3;"},

{"sra", 0, "assign \1 = ({32{\2[31]}} << (6'd32-{1'b0, \3}))\n\

                 | \2 >> \3;"},

{"lb",  0, "always @(posedge clk or posedge rst)"},

{"lh",  0, "always @(posedge clk or posedge rst)"},

{"lw",  0, "always @(posedge clk or posedge rst)"},

{"sb",  0, "/* mem8[\2] = \1 */"},

{"sh",  0, "/* mem16[\2] = \1 */"},

{"sw",  0, "/* mem32[\2] = \1 */"},

{"sfeq", 1, "assign \1 = \2 == \3;"},

{"sfne", 1, "assign \1 = \2 != \3;"},

{"sfle", 0, "assign \1 = \2 <= \3;"},

{"sflt", 0, "assign \1 = \2 < \3;"},

{"sfgt", 0, "assign \1 = \2 > \3;"},

{"sfge", 0, "assign \1 = \2 >= \3;"},

{"sfor", 1, "assign \1 = \2 || \3;"},

{"bf",  0, ""},

{"lrbb", 0,"always @(posedge clk or posedge rst)"},

{"cmov", 0,"assign \1 = \4 ? \2 : \3;"},

{"reg", 0, "always @(posedge clk or posedge rst)"},

{"nop", 0, NULL}};

/* Find known instruction and attach them to insn */

void change_insn_type (cuc_insn *i, int index)

{

  int j;

  assert (index >= 0 && index <= II_LAST);

  i->index = index;

  if (i->index == II_NOP) {

    for (j = 0; j < MAX_OPERANDS; j++) i->opt[j] = OPT_NONE;

    i->type = 0;

    i->dep = NULL;

  }

}

/* Returns instruction name */

const char *cuc_insn_name (cuc_insn *ii) {

  if (ii->index < 0 || ii->index > II_LAST) return "???";

  else return known[ii->index].name;

}

/* CSE -- common subexpression elimination */

void cse (cuc_func *f)

{

  int b, i, j, b1, i1, b2, i2, j2;

  for (b1 = 0; b1 < f->num_bb; b1++)

    for (i1 = 0; i1 < f->bb[b1].ninsn; i1++)

      for (b2 = 0; b2 < f->num_bb; b2++)

        for (i2 = 0; i2 < f->bb[b2].ninsn; i2++) {

          cuc_insn *ii1 = &f->bb[b1].insn[i1];

          cuc_insn *ii2 = &f->bb[b2].insn[i2];

          /* Do we have an exact match? */

          if (ii1->index == ii2->index) continue;

          if (ii1->type & IT_VOLATILE) continue;

          if (ii1->op[1] != ii2->op[1] || ii1->opt[1] != ii2->opt[1]) continue;

          if (ii1->op[2] != ii2->op[2] || ii1->opt[2] != ii2->opt[2]) continue;

          if (ii1->opt[3] != ii2->opt[3]) continue;

          if (ii1->opt[3] != OPT_NONE && ii1->op[3] != ii2->op[3]) continue;

          /* Check if we drive outputs? */

          if ((ii1->opt[0] & OPT_REGISTER) && ii1->op[0] >= 0)

            if ((ii2->opt[0] & OPT_REGISTER) && ii2->op[0] >= 0) continue;

            else ii2->op[0] = ii1->op[0];

          /* remove duplicated instruction and relink the references */

          change_insn_type (ii2, II_NOP);

          for (b = 0; b < f->num_bb; b++)

            for (i = 0; i < f->bb[b].ninsn; i++)

              for (j = 0; j < MAX_OPERANDS; j++)

                if (f->bb[b].insn[i].opt[j] & OPT_REF && f->bb[b].insn[i].op[j] == REF (b2, i2))

                  f->bb[b].insn[i].op[j] = REF (b1, i1);

        }

}

static int count_cmovs (cuc_insn *ii, int match)

{

  int c = 0, j;

  if (match & 2) {

    for (j = 0; j < MAX_OPERANDS; j++)

      if (ii->opt[j] & OPT_DEST) c++;

  }

  if (match & 1) {

    for (j = 0; j < MAX_OPERANDS; j++)

      if (!(ii->opt[j] & OPT_DEST) && ii->opt[j] & OPT_REF) c++;

  } else {

    for (j = 0; j < MAX_OPERANDS; j++)

      if (!(ii->opt[j] & OPT_DEST) && ii->opt[j] != OPT_NONE) c++;

  }

  return c;

}

static void search_csm (int iter, cuc_func *f, cuc_shared *list);

static cuc_shared *main_list;

static int *iteration;

/* CSM -- common subexpression matching -- resource sharing */

void csm (cuc_func *f)

{

  int b, i, j;

  int cnt;

  cuc_shared *list;

  cuc_timings timings;

  analyse_timings (f, &timings);

  main_list = NULL;

  for (b = 0; b < f->num_bb; b++) {

    assert (iteration = (int *)malloc (sizeof (int) * f->bb[b].ninsn));

    for (i = 0; i < f->bb[b].ninsn; i++) {

      int cnt = 0, cntc = 0;

      double size = 0., sizec = 0.;

      int j2 = 0;

      for (j = 0; j < f->bb[b].ninsn; j++)

        if (f->bb[b].insn[i].index == f->bb[b].insn[j].index) {

          int ok = 1;

          for (j2 = 0; j2 < MAX_OPERANDS; j2++) if (!(f->bb[b].insn[j].opt[j2] & OPT_REF))

            if (f->bb[b].insn[j].opt[j2] != f->bb[b].insn[i].opt[j2]

             || f->bb[b].insn[j].op[j2] != f->bb[b].insn[i].opt[j2]) {

              ok = 0;

              break;

            }

          if (ok) {

            cntc++;

            sizec = sizec + insn_size (&f->bb[b].insn[j]);

          } else {

            cnt++;

            size = size + insn_size (&f->bb[b].insn[j]);

          }

          iteration[j] = 0;

        } else iteration[j] = -1;

      if (cntc > 1) {

        assert (list = (cuc_shared *)malloc (sizeof (cuc_shared)));

        list->next = main_list;

        list->from = NULL;

        list->ref = REF (b, i);

        list->cnt = cnt;

        list->cmatch = 1;

        list->cmovs = count_cmovs (&f->bb[b].insn[i], 3);

        list->osize = sizec;

        list->size = ii_size (f->bb[b].insn[i].index, 1);

        main_list = list;

        search_csm (0, f, list);

      }

      if (cnt > 1) {

        assert (list = (cuc_shared *)malloc (sizeof (cuc_shared)));

        list->next = main_list;

        list->from = NULL;

        list->ref = REF (b, i);

        list->cnt = cnt + cntc;

        list->cmatch = 0;

        list->cmovs = count_cmovs (&f->bb[b].insn[i], 2);

        list->osize = size + sizec;

        list->size = ii_size (f->bb[b].insn[i].index, 0);

        main_list = list;

        search_csm (0, f, list);

      }

    }

    free (iteration);

  }

  for (list = main_list; list; list = list->next) list->dead = 0;

  cnt = 0;

  for (list = main_list; list; list = list->next) if (!list->dead) cnt++;

  cucdebug (1, "noptions = %i\n", cnt);

  /* Now we will check the real size of the 'improvements'; if the size

     actually increases, we abandom the option */

  for (list = main_list; list; list = list->next)

    if (list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size >= list->osize) list->dead = 1;

  cnt = 0;

  for (list = main_list; list; list = list->next) if (!list->dead) cnt++;

  cucdebug (1, "noptions = %i\n", cnt);

  /* Count number of instructions grouped */

  for (list = main_list; list; list = list->next) {

    cuc_shared *l = list;

    int c = 0;

    while (l) {

      c++;

      if (f->INSN(l->ref).type & (IT_VOLATILE | IT_MEMORY | IT_MEMADD)) list->dead = 1;

      l = l->from;

    }

    list->ninsn = c;

  }

  cnt = 0;

  for (list = main_list; list; list = list->next)

    if (!list->dead) cnt++;

  cucdebug (1, "noptions = %i\n", cnt);

#if 1

  /* We can get a lot of options here, so we will delete duplicates */

  for (list = main_list; list; list = list->next) if (!list->dead) {

    cuc_shared *l;

    for (l = list->next; l; l = l->next) if (!l->dead) {

      int ok = 1;

      cuc_shared *t1 = list;

      cuc_shared *t2 = l;

      while (ok && t1 && t2) {

        if (f->INSN(t1->ref).index == f->INSN(t2->ref).index) {

          /* If other operands are matching, we must check for them also */

          if (t1->cmatch) {

            int j;

            for (j = 0; j < MAX_OPERANDS; j++)

              if (!(f->INSN(t1->ref).opt[j] & OPT_REF) || !(f->INSN(t2->ref).opt[j] & OPT_REF)

               || f->INSN(t1->ref).opt[j] != f->INSN(t2->ref).opt[j]

               || f->INSN(t1->ref).op[j] != f->INSN(t2->ref).op[j]) {

                ok = 0;

                break;

              }

          }

          /* This option is duplicate, remove */

          if (ok) t1->dead = 1;

        }

        t1 = t1->from;

        t2 = t2->from;

      }

    }

  }

  cnt = 0;

  for (list = main_list; list; list = list->next) if (!list->dead) cnt++;

  cucdebug (1, "noptions = %i\n", cnt);

#endif

  /* Print out */

  for (list = main_list; list; list = list->next) if (!list->dead) {

    cuc_shared *l = list;

    cucdebug (1, "%-4s cnt %3i ninsn %3i size %8.1f osize %8.1f cmovs %3i @",

           cuc_insn_name (&f->INSN(list->ref)), list->cnt, list->ninsn,

           list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size, list->osize, list->cmovs);

    while (l) {

      cucdebug (1, "%c%x,", l->cmatch ? '.' : '!', l->ref);

      l = l->from;

    }

    cucdebug (1, "\n");

  }

  /* Calculate estimated timings */

  for (b = 0; b < f->num_bb; b++) {

    cnt = 0;

    for (list = main_list; list; list = list->next)

      if (!list->dead && REF_BB(list->ref) == b) cnt++;

    f->bb[b].ntim = cnt;

    if (!cnt) {

      f->bb[b].tim = NULL;

      continue;

    }

    assert (f->bb[b].tim = (cuc_timings *)malloc (sizeof (cuc_timings) * cnt));

    cnt = 0;

    for (list = main_list; list; list = list->next) if (!list->dead && REF_BB(list->ref) == b) {

      cuc_shared *l = list;

      f->bb[b].tim[cnt].b = b;

      f->bb[b].tim[cnt].preroll = f->bb[b].tim[cnt].unroll = 1;

      f->bb[b].tim[cnt].nshared = list->ninsn;

      assert (f->bb[b].tim[cnt].shared = (int *) malloc (sizeof(int) * list->ninsn));

      for (i =  0; i < list->ninsn; i++, l = l->from) f->bb[b].tim[cnt].shared[i] = l->ref;

      f->bb[b].tim[cnt].new_time = timings.new_time + f->bb[b].cnt * (list->cnt - 1);

      f->bb[b].tim[cnt].size = timings.size + list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size - list->osize;

      cnt++;

    }

  }

}

/* Recursive function for searching through instruction graph */

static void search_csm (int iter, cuc_func *f, cuc_shared *list)

{

  int b, i, j, i1;

  cuc_shared *l;

  b = REF_BB(list->ref);

  i = REF_I(list->ref);

  for (j = 0; j < MAX_OPERANDS; j++) if (f->bb[b].insn[i].opt[j] & OPT_REF) {

    int t = f->bb[b].insn[i].op[j];

    int cnt = 0, cntc = 0;

    double size = 0., sizec = 0.;

    /* Mark neighbours */

    for (i1 = 0; i1 < f->bb[b].ninsn; i1++) {

      if (iteration[i1] == iter && f->bb[b].insn[i1].opt[j] & OPT_REF) {

        int t2 = f->bb[b].insn[i1].op[j];

        if (f->INSN(t).index == f->INSN(t2).index && f->INSN(t2).opt[j] & OPT_REF) {

          int j2;

          int ok = 1;

          iteration[REF_I(t2)] = iter + 1;

          for (j2 = 0; j2 < MAX_OPERANDS; j2++) if (!(f->bb[b].insn[i1].opt[j2] & OPT_REF))

            if (f->bb[b].insn[i1].opt[j2] != f->bb[b].insn[i].opt[j2]

             || f->bb[b].insn[i1].op[j2] != f->bb[b].insn[i].opt[j2]) {

              ok = 0;

              break;

            }

          if (ok) {

            cntc++;

            sizec = sizec + insn_size (&f->bb[b].insn[i1]);

          } else {

            cnt++;

            size = size + insn_size (&f->bb[b].insn[i1]);

          }

        }

      }

    }

    if (cntc > 1) {

      assert (l = (cuc_shared *)malloc (sizeof (cuc_shared)));

      l->next = main_list;

      main_list = l;

      l->from = list;

      l->ref = t;

      l->cnt = cnt;

      l->cmatch = 1;

      l->cmovs = list->cmovs + count_cmovs (&f->bb[b].insn[i], 1) - 1;

      l->size = list->size + ii_size (f->bb[b].insn[i].index, 1);

      l->osize = sizec;

      search_csm (iter + 1, f, l);

    }

    if (cnt > 1) {

      assert (l = (cuc_shared *)malloc (sizeof (cuc_shared)));

      l->next = main_list;

      main_list = l;

      l->from = list;

      l->ref = t;

      l->cnt = cnt + cntc;

      l->cmatch = 0;

      l->osize = size + sizec;

      l->cmovs = list->cmovs + count_cmovs (&f->bb[b].insn[i], 0) - 1;

      l->size = list->size + ii_size (f->bb[b].insn[i].index, 0);

      search_csm (iter + 1, f, l);

    }

    /* Unmark them back */

    for (i1 = 0; i1 < f->bb[b].ninsn; i1++) if (iteration[i1] > iter) iteration[i1] = -1;

  }

}