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