URL
https://opencores.org/ocsvn/or1k/or1k/trunk
Subversion Repositories or1k
[/] [or1k/] [tags/] [nog_patch_39/] [or1ksim/] [cuc/] [insn.c] - Rev 883
Go to most recent revision | Compare with Previous | Blame | View Log
/* 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; } }
Go to most recent revision | Compare with Previous | Blame | View Log