URL
https://opencores.org/ocsvn/or1k/or1k/trunk
Subversion Repositories or1k
[/] [or1k/] [tags/] [nog_patch_64/] [or1ksim/] [cuc/] [memory.c] - Rev 897
Go to most recent revision | Compare with Previous | Blame | View Log
/* memory.c -- OpenRISC Custom Unit Compiler, memory optimization and scheduling * 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 "sim-config.h" #include "cuc.h" #include "insn.h" /* Checks for memory conflicts between two instructions; returns 1 if detected 0 - exact; 1 - strong; 2 - weak; 3 - none */ static int check_memory_conflict (cuc_func *f, cuc_insn *a, cuc_insn *b, int otype) { switch (otype) { case MO_EXACT: /* exact */ case MO_STRONG: /* strong */ return 1; case MO_WEAK: /* weak */ assert (a->type & IT_MEMORY); assert (b->type & IT_MEMORY); if ((a->opt[1] & OPT_REF) && f->INSN(a->op[1]).index == II_ADD &&(b->opt[1] & OPT_REF) && f->INSN(b->op[1]).index == II_ADD) { int aw, bw; assert ((aw = II_MEM_WIDTH (a->index)) >= 0); assert ((bw = II_MEM_WIDTH (b->index)) >= 0); a = &f->INSN(a->op[1]); b = &f->INSN(b->op[1]); if (a->opt[1] != b->opt[1] || a->op[1] != b->op[1] || a->opt[2] != OPT_CONST || b->opt[2] != OPT_CONST) return 1; /* Check if they overlap */ if (a->op[2] >= b->op[2] && a->op[2] < b->op[2] + bw) return 1; if (b->op[2] >= a->op[2] && b->op[2] < a->op[2] + aw) return 1; return 0; } else return 1; case MO_NONE: /* none */ return 0; default: assert (0); } return 1; } /* Adds memory dependencies based on ordering type: 0 - exact; 1 - strong; 2 - weak; 3 - none */ void add_memory_dep (cuc_func *f, int otype) { int b, i; dep_list *all_mem = NULL; for (b = 0; b < f->num_bb; b++) { cuc_insn *insn = f->bb[b].insn; for (i = 0; i < f->bb[b].ninsn; i++) if (insn[i].type & IT_MEMORY) { dep_list *tmp = all_mem; while (tmp) { //printf ("%x %x\n", REF (b,i), tmp->ref); if (check_memory_conflict (f, &insn[i], &f->INSN(tmp->ref), otype)) add_dep (&insn[i].dep, tmp->ref); tmp = tmp->next; } add_dep (&all_mem, REF (b, i)); } } dispose_list (&all_mem); } /* returns nonzero if a < b */ int mem_ordering_cmp (cuc_func *f, cuc_insn *a, cuc_insn *b) { assert (a->type & IT_MEMORY); assert (b->type & IT_MEMORY); if ((a->opt[1] & OPT_REF) && f->INSN(a->op[1]).index == II_ADD &&(b->opt[1] & OPT_REF) && f->INSN(b->op[1]).index == II_ADD) { a = &f->INSN(a->op[1]); b = &f->INSN(b->op[1]); if (a->opt[1] != b->opt[1] || a->op[1] != b->op[1] || a->opt[2] != OPT_CONST || b->opt[2] != OPT_CONST) return 0; /* Order linearly, we can then join them to bursts */ return a->op[2] < b->op[2]; } else return 0; } /* Schedule memory accesses 0 - exact; 1 - strong; 2 - weak; 3 - none */ void schedule_memory (cuc_func *f, int otype) { int b, i, j; f->nmsched = 0; for (b = 0; b < f->num_bb; b++) { cuc_insn *insn = f->bb[b].insn; for (i = 0; i < f->bb[b].ninsn; i++) if (insn[i].type & IT_MEMORY) { f->msched[f->nmsched++] = REF (b, i); if (otype == MO_NONE || otype == MO_WEAK) insn[i].type |= IT_FLAG1; /* mark unscheduled */ } } #if 0 for (i = 0; i < f->nmsched; i++) printf ("[%i]%i%c ", f->msched[i], f->mtype[i] & MT_WIDTH, (f->mtype[i] & MT_BURST) ? (f->mtype[i] & MT_BURSTE) ? 'E' : 'B' : ' '); printf ("\n"); #endif /* We can reorder just more loose types We assume, that memory accesses are currently in valid (but not neccesserly) optimal order */ if (otype == MO_WEAK || otype == MO_NONE) { for (i = 0; i < f->nmsched; i++) { int best = i; int tmp; for (j = i + 1; j < f->nmsched; j++) if (REF_BB(f->msched[j]) == REF_BB(f->msched[best])) { if (mem_ordering_cmp (f, &f->INSN (f->msched[j]), &f->INSN(f->msched[best]))) { /* Check dependencies */ dep_list *t = f->INSN(f->msched[j]).dep; while (t) { if (f->INSN(t->ref).type & IT_FLAG1) break; t = t->next; } if (!t) best = j; /* no conflicts -> ok */ } } /* we have to shift instructions up, to maintain valid dependencies and make space for best candidate */ /* make local copy */ tmp = f->msched[best]; for (j = best; j > i; j--) f->msched[j] = f->msched[j - 1]; f->msched[i] = tmp; f->INSN(f->msched[i]).type &= ~IT_FLAG1; /* mark scheduled */ } } #if 0 for (i = 0; i < f->nmsched; i++) printf ("[%i]%i%c ", f->msched[i], f->mtype[i] & MT_WIDTH, (f->mtype[i] & MT_BURST) ? (f->mtype[i] & MT_BURSTE) ? 'E' : 'B' : ' '); printf ("\n"); #endif for (i = 0; i < f->nmsched; i++) { cuc_insn *a = &f->INSN(f->msched[i]); f->mtype[i] = !II_IS_LOAD(a->index) ? MT_WRITE : 0; f->mtype[i] |= II_MEM_WIDTH (a->index); if (a->type & IT_SIGNED) f->mtype[i] |= MT_SIGNED; } if (config.cuc.enable_bursts) { //printf ("\n"); for (i = 1; i < f->nmsched; i++) { cuc_insn *a = &f->INSN(f->msched[i - 1]); cuc_insn *b = &f->INSN(f->msched[i]); int aw = f->mtype[i - 1] & MT_WIDTH; if ((a->opt[1] & OPT_REF) && f->INSN(a->op[1]).index == II_ADD &&(b->opt[1] & OPT_REF) && f->INSN(b->op[1]).index == II_ADD) { a = &f->INSN(a->op[1]); b = &f->INSN(b->op[1]); /* Not in usual form? */ if (a->opt[1] != b->opt[1] || a->op[1] != b->op[1] || a->opt[2] != OPT_CONST || b->opt[2] != OPT_CONST) continue; //printf ("%i %i, ", a->op[2], b->op[2]); /* Check if they touch together */ if (a->op[2] + aw == b->op[2]) { /* yes => do burst */ f->mtype[i - 1] &= ~MT_BURSTE; f->mtype[i - 1] |= MT_BURST; f->mtype[i] |= MT_BURST | MT_BURSTE; } } } } #if 0 printf ("\n"); for (i = 0; i < f->nmsched; i++) printf ("[%i]%i%c ", f->msched[i], f->mtype[i] & MT_WIDTH, (f->mtype[i] & MT_BURST) ? (f->mtype[i] & MT_BURSTE) ? 'E' : 'B' : ' '); printf ("\n"); #endif /* We don't need dependencies in non-memory instructions */ for (b = 0; b < f->num_bb; b++) { cuc_insn *insn = f->bb[b].insn; for (i = 0; i < f->bb[b].ninsn; i++) if (!(insn[i].type & IT_MEMORY)) dispose_list (&insn[i].dep); } /* Reduce number of dependecies, keeping just direct dependencies, based on memory schedule */ { int lastl[2] = {-1, -1}, lasts[2] = {-1, -1}; int last_load = -1, last_store = -1; for (i = 0; i < f->nmsched; i++) { int t = (f->mtype[i] & MT_WRITE) ? 1 : 0; int maxl = lastl[t]; int maxs = lasts[t]; dep_list *tmp = f->INSN(f->msched[i]).dep; while (tmp) { if (f->INSN(tmp->ref).type & IT_MEMORY && REF_BB(tmp->ref) == REF_BB(f->msched[i])) { /* Search for the reference */ for (j = 0; j < f->nmsched; j++) if (f->msched[j] == tmp->ref) break; assert (j < f->nmsched); if (f->mtype[j] & MT_WRITE) { if (maxs < j) maxs = j; } else { if (maxl < j) maxl = j; } } tmp = tmp->next; } dispose_list (&f->INSN(f->msched[i]).dep); if (f->mtype[i] & MT_WRITE) { maxs = last_store; last_store = i; } else { maxl = last_load; last_load = i; } if (maxl > lastl[t]) { add_dep (&f->INSN(f->msched[i]).dep, f->msched[maxl]); lastl[t] = maxl; } if (maxs > lasts[t]) { add_dep (&f->INSN(f->msched[i]).dep, f->msched[maxs]); lasts[t] = maxs; } //printf ("%i(%i)> ml %i(%i) ms %i(%i) lastl %i %i lasts %i %i last_load %i last_store %i\n", i, f->msched[i], maxl, f->msched[maxl], maxs, f->msched[maxs], lastl[0], lastl[1], lasts[0], lasts[1], last_load, last_store); /* What we have to wait to finish this BB? */ if (i + 1 >= f->nmsched || REF_BB(f->msched[i + 1]) != REF_BB(f->msched[i])) { if (last_load > lastl[t]) { add_dep (&f->bb[REF_BB(f->msched[i])].mdep, f->msched[last_load]); lastl[t] = last_load; } if (last_store > lasts[t]) { add_dep (&f->bb[REF_BB(f->msched[i])].mdep, f->msched[last_store]); lasts[t] = last_store; } } } } }
Go to most recent revision | Compare with Previous | Blame | View Log