URL https://opencores.org/ocsvn/or1k/or1k/trunk

Subversion Repositories or1k

[/] [or1k/] [tags/] [nog_patch_61/] [or1ksim/] [cuc/] [memory.c] - Blame information for rev 879

Go to most recent revision | Details | Compare with Previous | 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 "cuc.h"
#include "insn.h"
 
/* Checks for memory conflicts between two instructions; returns 1 if detected
 
static int check_memory_conflict (cuc_func *f, cuc_insn *a, cuc_insn *b, int otype)
{
  switch (otype) {
    case 0: /* exact */
    case 1: /* strong */
      return 1;
    case 2: /* 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 3: /* none */
      return 0;
    default:
      assert (0);
  }
  return 1;
}
 
/* Adds memory dependencies based on ordering type:
 
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
 
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 == 2 || otype == 3) 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 == 2 || otype == 3) {
    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 (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;
        }
      }
    }
  }
}

Browse

Tools

Subversion Repositories or1k

[/] [or1k/] [tags/] [nog_patch_61/] [or1ksim/] [cuc/] [memory.c] - Blame information for rev 879

Line No.	Rev	Author	Line
1	879	markom	`/* memory.c -- OpenRISC Custom Unit Compiler, memory optimization and scheduling`
2			`* Copyright (C) 2002 Marko Mlinar, markom@opencores.org`
3			`*`
4			`* This file is part of OpenRISC 1000 Architectural Simulator.`
5			`*`
6			`* This program is free software; you can redistribute it and/or modify`
7			`* it under the terms of the GNU General Public License as published by`
8			`* the Free Software Foundation; either version 2 of the License, or`
9			`* (at your option) any later version.`
10			`*`
11			`* This program is distributed in the hope that it will be useful,`
12			`* but WITHOUT ANY WARRANTY; without even the implied warranty of`
13			`* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the`
14			`* GNU General Public License for more details.`
15			`*`
16			`* You should have received a copy of the GNU General Public License`
17			`* along with this program; if not, write to the Free Software`
18			`* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */`
19
20			`#include <stdio.h>`
21			`#include <stdlib.h>`
22			`#include <stdarg.h>`
23			`#include <assert.h>`
24			`#include "cuc.h"`
25			`#include "insn.h"`
26
27			`/* Checks for memory conflicts between two instructions; returns 1 if detected`
28
29			`static int check_memory_conflict (cuc_func f, cuc_insn a, cuc_insn *b, int otype)`
30			`{`
31			`switch (otype) {`
32			`case 0: /* exact */`
33			`case 1: /* strong */`
34			`return 1;`
35			`case 2: /* weak */`
36			`assert (a->type & IT_MEMORY);`
37			`assert (b->type & IT_MEMORY);`
38			`if ((a->opt[1] & OPT_REF) && f->INSN(a->op[1]).index == II_ADD`
39			`&&(b->opt[1] & OPT_REF) && f->INSN(b->op[1]).index == II_ADD) {`
40			`int aw, bw;`
41			`assert ((aw = II_MEM_WIDTH (a->index)) >= 0);`
42			`assert ((bw = II_MEM_WIDTH (b->index)) >= 0);`
43
44			`a = &f->INSN(a->op[1]);`
45			`b = &f->INSN(b->op[1]);`
46			`if (a->opt[1] != b->opt[1] \|\| a->op[1] != b->op[1]`
47			`\|\| a->opt[2] != OPT_CONST \|\| b->opt[2] != OPT_CONST) return 1;`
48
49			`/* Check if they overlap */`
50			`if (a->op[2] >= b->op[2] && a->op[2] < b->op[2] + bw) return 1;`
51			`if (b->op[2] >= a->op[2] && b->op[2] < a->op[2] + aw) return 1;`
52			`return 0;`
53			`} else return 1;`
54			`case 3: /* none */`
55			`return 0;`
56			`default:`
57			`assert (0);`
58			`}`
59			`return 1;`
60			`}`
61
62			`/* Adds memory dependencies based on ordering type:`
63
64			`void add_memory_dep (cuc_func *f, int otype)`
65			`{`
66			`int b, i;`
67			`dep_list *all_mem = NULL;`
68
69			`for (b = 0; b < f->num_bb; b++) {`
70			`cuc_insn *insn = f->bb[b].insn;`
71			`for (i = 0; i < f->bb[b].ninsn; i++)`
72			`if (insn[i].type & IT_MEMORY) {`
73			`dep_list *tmp = all_mem;`
74			`while (tmp) {`
75			`//printf ("%x %x\n", REF (b,i), tmp->ref);`
76			`if (check_memory_conflict (f, &insn[i], &f->INSN(tmp->ref), otype))`
77			`add_dep (&insn[i].dep, tmp->ref);`
78			`tmp = tmp->next;`
79			`}`
80			`add_dep (&all_mem, REF (b, i));`
81			`}`
82			`}`
83			`dispose_list (&all_mem);`
84			`}`
85
86			`/* returns nonzero if a < b */`
87			`int mem_ordering_cmp (cuc_func f, cuc_insn a, cuc_insn *b)`
88			`{`
89			`assert (a->type & IT_MEMORY);`
90			`assert (b->type & IT_MEMORY);`
91			`if ((a->opt[1] & OPT_REF) && f->INSN(a->op[1]).index == II_ADD`
92			`&&(b->opt[1] & OPT_REF) && f->INSN(b->op[1]).index == II_ADD) {`
93			`a = &f->INSN(a->op[1]);`
94			`b = &f->INSN(b->op[1]);`
95			`if (a->opt[1] != b->opt[1] \|\| a->op[1] != b->op[1]`
96			`\|\| a->opt[2] != OPT_CONST \|\| b->opt[2] != OPT_CONST) return 0;`
97
98			`/* Order linearly, we can then join them to bursts */`
99			`return a->op[2] < b->op[2];`
100			`} else return 0;`
101			`}`
102
103			`/* Schedule memory accesses`
104
105			`void schedule_memory (cuc_func *f, int otype)`
106			`{`
107			`int b, i, j;`
108			`f->nmsched = 0;`
109
110			`for (b = 0; b < f->num_bb; b++) {`
111			`cuc_insn *insn = f->bb[b].insn;`
112			`for (i = 0; i < f->bb[b].ninsn; i++)`
113			`if (insn[i].type & IT_MEMORY) {`
114			`f->msched[f->nmsched++] = REF (b, i);`
115			`if (otype == 2 \|\| otype == 3) insn[i].type \|= IT_FLAG1; /* mark unscheduled */`
116			`}`
117			`}`
118			`#if 0`
119			`for (i = 0; i < f->nmsched; i++)`
120			`printf ("[%i]%i%c ", f->msched[i], f->mtype[i] & MT_WIDTH, (f->mtype[i] & MT_BURST) ? (f->mtype[i] & MT_BURSTE) ? 'E' : 'B' : ' ');`
121			`printf ("\n");`
122			`#endif`
123
124			`/* We can reorder just more loose types`
125			`We assume, that memory accesses are currently in valid (but not neccesserly)`
126			`optimal order */`
127			`if (otype == 2 \|\| otype == 3) {`
128			`for (i = 0; i < f->nmsched; i++) {`
129			`int best = i;`
130			`int tmp;`
131			`for (j = i + 1; j < f->nmsched; j++) if (REF_BB(f->msched[j]) == REF_BB(f->msched[best])) {`
132			`if (mem_ordering_cmp (f, &f->INSN (f->msched[j]), &f->INSN(f->msched[best]))) {`
133			`/* Check dependencies */`
134			`dep_list *t = f->INSN(f->msched[j]).dep;`
135			`while (t) {`
136			`if (f->INSN(t->ref).type & IT_FLAG1) break;`
137			`t = t->next;`
138			`}`
139			`if (!t) best = j; /* no conflicts -> ok */`
140			`}`
141			`}`
142
143			`/* we have to shift instructions up, to maintain valid dependencies`
144			`and make space for best candidate */`
145
146			`/* make local copy */`
147			`tmp = f->msched[best];`
148			`for (j = best; j > i; j--) f->msched[j] = f->msched[j - 1];`
149			`f->msched[i] = tmp;`
150			`f->INSN(f->msched[i]).type &= ~IT_FLAG1; /* mark scheduled */`
151			`}`
152			`}`
153
154			`#if 0`
155			`for (i = 0; i < f->nmsched; i++)`
156			`printf ("[%i]%i%c ", f->msched[i], f->mtype[i] & MT_WIDTH, (f->mtype[i] & MT_BURST) ? (f->mtype[i] & MT_BURSTE) ? 'E' : 'B' : ' ');`
157			`printf ("\n");`
158			`#endif`
159
160			`for (i = 0; i < f->nmsched; i++) {`
161			`cuc_insn *a = &f->INSN(f->msched[i]);`
162			`f->mtype[i] = !II_IS_LOAD(a->index) ? MT_WRITE : 0;`
163			`f->mtype[i] \|= II_MEM_WIDTH (a->index);`
164			`if (a->type & IT_SIGNED) f->mtype[i] \|= MT_SIGNED;`
165			`}`
166
167			`if (enable_bursts) {`
168			`//printf ("\n");`
169			`for (i = 1; i < f->nmsched; i++) {`
170			`cuc_insn *a = &f->INSN(f->msched[i - 1]);`
171			`cuc_insn *b = &f->INSN(f->msched[i]);`
172			`int aw = f->mtype[i - 1] & MT_WIDTH;`
173
174			`if ((a->opt[1] & OPT_REF) && f->INSN(a->op[1]).index == II_ADD`
175			`&&(b->opt[1] & OPT_REF) && f->INSN(b->op[1]).index == II_ADD) {`
176			`a = &f->INSN(a->op[1]);`
177			`b = &f->INSN(b->op[1]);`
178			`/* Not in usual form? */`
179			`if (a->opt[1] != b->opt[1] \|\| a->op[1] != b->op[1]`
180			`\|\| a->opt[2] != OPT_CONST \|\| b->opt[2] != OPT_CONST) continue;`
181
182			`//printf ("%i %i, ", a->op[2], b->op[2]);`
183
184			`/* Check if they touch together */`
185			`if (a->op[2] + aw == b->op[2]) {`
186			`/* yes => do burst */`
187			`f->mtype[i - 1] &= ~MT_BURSTE;`
188			`f->mtype[i - 1] \|= MT_BURST;`
189			`f->mtype[i] \|= MT_BURST \| MT_BURSTE;`
190			`}`
191			`}`
192			`}`
193			`}`
194
195			`#if 0`
196			`printf ("\n");`
197			`for (i = 0; i < f->nmsched; i++)`
198			`printf ("[%i]%i%c ", f->msched[i], f->mtype[i] & MT_WIDTH, (f->mtype[i] & MT_BURST) ? (f->mtype[i] & MT_BURSTE) ? 'E' : 'B' : ' ');`
199			`printf ("\n");`
200			`#endif`
201
202			`/* We don't need dependencies in non-memory instructions */`
203			`for (b = 0; b < f->num_bb; b++) {`
204			`cuc_insn *insn = f->bb[b].insn;`
205			`for (i = 0; i < f->bb[b].ninsn; i++) if (!(insn[i].type & IT_MEMORY))`
206			`dispose_list (&insn[i].dep);`
207			`}`
208
209			`/* Reduce number of dependecies, keeping just direct dependencies, based on memory schedule */`
210			`{`
211			`int lastl[2] = {-1, -1}, lasts[2] = {-1, -1};`
212			`int last_load = -1, last_store = -1;`
213			`for (i = 0; i < f->nmsched; i++) {`
214			`int t = (f->mtype[i] & MT_WRITE) ? 1 : 0;`
215			`int maxl = lastl[t];`
216			`int maxs = lasts[t];`
217			`dep_list *tmp = f->INSN(f->msched[i]).dep;`
218			`while (tmp) {`
219			`if (f->INSN(tmp->ref).type & IT_MEMORY && REF_BB(tmp->ref) == REF_BB(f->msched[i])) {`
220			`/* Search for the reference */`
221			`for (j = 0; j < f->nmsched; j++) if (f->msched[j] == tmp->ref) break;`
222			`assert (j < f->nmsched);`
223			`if (f->mtype[j] & MT_WRITE) {`
224			`if (maxs < j) maxs = j;`
225			`} else {`
226			`if (maxl < j) maxl = j;`
227			`}`
228			`}`
229			`tmp = tmp->next;`
230			`}`
231			`dispose_list (&f->INSN(f->msched[i]).dep);`
232			`if (f->mtype[i] & MT_WRITE) {`
233			`maxs = last_store;`
234			`last_store = i;`
235			`} else {`
236			`maxl = last_load;`
237			`last_load = i;`
238			`}`
239
240			`if (maxl > lastl[t]) {`
241			`add_dep (&f->INSN(f->msched[i]).dep, f->msched[maxl]);`
242			`lastl[t] = maxl;`
243			`}`
244			`if (maxs > lasts[t]) {`
245			`add_dep (&f->INSN(f->msched[i]).dep, f->msched[maxs]);`
246			`lasts[t] = maxs;`
247			`}`
248			`//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);`
249
250			`/* What we have to wait to finish this BB? */`
251			`if (i + 1 >= f->nmsched \|\| REF_BB(f->msched[i + 1]) != REF_BB(f->msched[i])) {`
252			`if (last_load > lastl[t]) {`
253			`add_dep (&f->bb[REF_BB(f->msched[i])].mdep, f->msched[last_load]);`
254			`lastl[t] = last_load;`
255			`}`
256			`if (last_store > lasts[t]) {`
257			`add_dep (&f->bb[REF_BB(f->msched[i])].mdep, f->msched[last_store]);`
258			`lasts[t] = last_store;`
259			`}`
260			`}`
261			`}`
262			`}`
263			`}`