/* insn.c -- OpenRISC Custom Unit Compiler, instruction support
|
/* insn.c -- OpenRISC Custom Unit Compiler, instruction support
|
* Copyright (C) 2002 Marko Mlinar, markom@opencores.org
|
* Copyright (C) 2002 Marko Mlinar, markom@opencores.org
|
*
|
*
|
* This file is part of OpenRISC 1000 Architectural Simulator.
|
* This file is part of OpenRISC 1000 Architectural Simulator.
|
*
|
*
|
* This program is free software; you can redistribute it and/or modify
|
* 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
|
* it under the terms of the GNU General Public License as published by
|
* the Free Software Foundation; either version 2 of the License, or
|
* the Free Software Foundation; either version 2 of the License, or
|
* (at your option) any later version.
|
* (at your option) any later version.
|
*
|
*
|
* This program is distributed in the hope that it will be useful,
|
* This program is distributed in the hope that it will be useful,
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
* GNU General Public License for more details.
|
* GNU General Public License for more details.
|
*
|
*
|
* You should have received a copy of the GNU General Public License
|
* You should have received a copy of the GNU General Public License
|
* along with this program; if not, write to the Free Software
|
* along with this program; if not, write to the Free Software
|
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
|
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
|
|
|
#include <stdio.h>
|
#include <stdio.h>
|
#include <stdlib.h>
|
#include <stdlib.h>
|
#include <stdarg.h>
|
#include <stdarg.h>
|
#include <assert.h>
|
#include <assert.h>
|
#include "cuc.h"
|
#include "cuc.h"
|
#include "insn.h"
|
#include "insn.h"
|
|
|
/* Table of known instructions. Watch out for indexes I_*! */
|
/* Table of known instructions. Watch out for indexes I_*! */
|
const cuc_known_insn known[II_LAST + 1] = {
|
const cuc_known_insn known[II_LAST + 1] = {
|
{"add", 1, "assign \1 = \2 + \3;"},
|
{"add", 1, "assign \1 = \2 + \3;"},
|
{"sub", 0, "assign \1 = \2 - \3;"},
|
{"sub", 0, "assign \1 = \2 - \3;"},
|
{"and", 1, "assign \1 = \2 & \3;"},
|
{"and", 1, "assign \1 = \2 & \3;"},
|
{"or", 1, "assign \1 = \2 | \3;"},
|
{"or", 1, "assign \1 = \2 | \3;"},
|
{"xor", 1, "assign \1 = \2 ^ \3;"},
|
{"xor", 1, "assign \1 = \2 ^ \3;"},
|
{"mul", 1, "assign \1 = \2 * \3;"},
|
{"mul", 1, "assign \1 = \2 * \3;"},
|
|
|
{"srl", 0, "assign \1 = \2 >> \3;"},
|
{"srl", 0, "assign \1 = \2 >> \3;"},
|
{"sll", 0, "assign \1 = \2 << \3;"},
|
{"sll", 0, "assign \1 = \2 << \3;"},
|
{"sra", 0, "assign \1 = ({32{\2[31]}} << (6'd32-{1'b0, \3}))\n\
|
{"sra", 0, "assign \1 = ({32{\2[31]}} << (6'd32-{1'b0, \3}))\n\
|
| \2 >> \3;"},
|
| \2 >> \3;"},
|
|
|
{"lb", 0, "always @(posedge clk or posedge rst)"},
|
{"lb", 0, "always @(posedge clk or posedge rst)"},
|
{"lh", 0, "always @(posedge clk or posedge rst)"},
|
{"lh", 0, "always @(posedge clk or posedge rst)"},
|
{"lw", 0, "always @(posedge clk or posedge rst)"},
|
{"lw", 0, "always @(posedge clk or posedge rst)"},
|
{"sb", 0, "/* mem8[\2] = \1 */"},
|
{"sb", 0, "/* mem8[\2] = \1 */"},
|
{"sh", 0, "/* mem16[\2] = \1 */"},
|
{"sh", 0, "/* mem16[\2] = \1 */"},
|
{"sw", 0, "/* mem32[\2] = \1 */"},
|
{"sw", 0, "/* mem32[\2] = \1 */"},
|
|
|
{"sfeq", 1, "assign \1 = \2 == \3;"},
|
{"sfeq", 1, "assign \1 = \2 == \3;"},
|
{"sfne", 1, "assign \1 = \2 != \3;"},
|
{"sfne", 1, "assign \1 = \2 != \3;"},
|
{"sfle", 0, "assign \1 = \2 <= \3;"},
|
{"sfle", 0, "assign \1 = \2 <= \3;"},
|
{"sflt", 0, "assign \1 = \2 < \3;"},
|
{"sflt", 0, "assign \1 = \2 < \3;"},
|
{"sfgt", 0, "assign \1 = \2 > \3;"},
|
{"sfgt", 0, "assign \1 = \2 > \3;"},
|
{"sfge", 0, "assign \1 = \2 >= \3;"},
|
{"sfge", 0, "assign \1 = \2 >= \3;"},
|
{"sfor", 1, "assign \1 = \2 || \3;"},
|
{"sfor", 1, "assign \1 = \2 || \3;"},
|
{"bf", 0, ""},
|
{"bf", 0, ""},
|
|
|
{"lrbb", 0,"always @(posedge clk or posedge rst)"},
|
{"lrbb", 0,"always @(posedge clk or posedge rst)"},
|
{"cmov", 0,"assign \1 = \4 ? \2 : \3;"},
|
{"cmov", 0,"assign \1 = \4 ? \2 : \3;"},
|
{"reg", 0, "always @(posedge clk or posedge rst)"},
|
{"reg", 0, "always @(posedge clk or posedge rst)"},
|
|
|
{"nop", 0, NULL}};
|
{"nop", 0, NULL}};
|
|
|
/* Find known instruction and attach them to insn */
|
/* Find known instruction and attach them to insn */
|
void change_insn_type (cuc_insn *i, int index)
|
void change_insn_type (cuc_insn *i, int index)
|
{
|
{
|
int j;
|
int j;
|
assert (index >= 0 && index <= II_LAST);
|
assert (index >= 0 && index <= II_LAST);
|
i->index = index;
|
i->index = index;
|
if (i->index == II_NOP) {
|
if (i->index == II_NOP) {
|
for (j = 0; j < MAX_OPERANDS; j++) i->opt[j] = OPT_NONE;
|
for (j = 0; j < MAX_OPERANDS; j++) i->opt[j] = OPT_NONE;
|
i->type = 0;
|
i->type = 0;
|
i->dep = NULL;
|
i->dep = NULL;
|
}
|
}
|
}
|
}
|
|
|
/* Returns instruction name */
|
/* Returns instruction name */
|
const char *cuc_insn_name (cuc_insn *ii) {
|
const char *cuc_insn_name (cuc_insn *ii) {
|
if (ii->index < 0 || ii->index > II_LAST) return "???";
|
if (ii->index < 0 || ii->index > II_LAST) return "???";
|
else return known[ii->index].name;
|
else return known[ii->index].name;
|
}
|
}
|
|
|
No newline at end of file
|
No newline at end of file
|
|
/* 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;
|
|
}
|
|
}
|
|
|
|
|
No newline at end of file
|
No newline at end of file
|