OpenCores
URL https://opencores.org/ocsvn/or1k_old/or1k_old/trunk

Subversion Repositories or1k_old

[/] [or1k_old/] [trunk/] [or1ksim/] [cuc/] [memory.c] - Blame information for rev 907

Go to most recent revision | Details | Compare with Previous | View Log

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 897 markom 
#include "sim-config.h"
25 879 markom 
#include "cuc.h"
26 
#include "insn.h"
27 
 
28 
/* Checks for memory conflicts between two instructions; returns 1 if detected
29 
 
30 
static int check_memory_conflict (cuc_func *f, cuc_insn *a, cuc_insn *b, int otype)
31 
{
32 
  switch (otype) {
33 897 markom 
    case MO_EXACT: /* exact */
34 
    case MO_STRONG: /* strong */
35 879 markom 
      return 1;
36 897 markom 
    case MO_WEAK: /* weak */
37 879 markom 
      assert (a->type & IT_MEMORY);
38 
      assert (b->type & IT_MEMORY);
39 
      if ((a->opt[1] & OPT_REF) && f->INSN(a->op[1]).index == II_ADD
40 
        &&(b->opt[1] & OPT_REF) && f->INSN(b->op[1]).index == II_ADD) {
41 
        int aw, bw;
42 
        assert ((aw = II_MEM_WIDTH (a->index)) >= 0);
43 
        assert ((bw = II_MEM_WIDTH (b->index)) >= 0);
44 
 
45 
        a = &f->INSN(a->op[1]);
46 
        b = &f->INSN(b->op[1]);
47 
        if (a->opt[1] != b->opt[1] || a->op[1] != b->op[1]
48 
         || a->opt[2] != OPT_CONST || b->opt[2] != OPT_CONST) return 1;
49 
 
50 
        /* Check if they overlap */
51 
        if (a->op[2] >= b->op[2] && a->op[2] < b->op[2] + bw) return 1;
52 
        if (b->op[2] >= a->op[2] && b->op[2] < a->op[2] + aw) return 1;
53 
        return 0;
54 
      } else return 1;
55 897 markom 
    case MO_NONE: /* none */
56 879 markom 
      return 0;
57 
    default:
58 
      assert (0);
59 
  }
60 
  return 1;
61 
}
62 
 
63 
/* Adds memory dependencies based on ordering type:
64 
 
65 
void add_memory_dep (cuc_func *f, int otype)
66 
{
67 
  int b, i;
68 
  dep_list *all_mem = NULL;
69 
 
70 
  for (b = 0; b < f->num_bb; b++) {
71 
    cuc_insn *insn = f->bb[b].insn;
72 
    for (i = 0; i < f->bb[b].ninsn; i++)
73 
      if (insn[i].type & IT_MEMORY) {
74 
        dep_list *tmp = all_mem;
75 
        while (tmp) {
76 
          //printf ("%x %x\n", REF (b,i), tmp->ref);
77 
          if (check_memory_conflict (f, &insn[i], &f->INSN(tmp->ref), otype))
78 
            add_dep (&insn[i].dep, tmp->ref);
79 
          tmp = tmp->next;
80 
        }
81 
        add_dep (&all_mem, REF (b, i));
82 
      }
83 
  }
84 
  dispose_list (&all_mem);
85 
}
86 
 
87 
/* returns nonzero if a < b */
88 
int mem_ordering_cmp (cuc_func *f, cuc_insn *a, cuc_insn *b)
89 
{
90 
  assert (a->type & IT_MEMORY);
91 
  assert (b->type & IT_MEMORY);
92 
  if ((a->opt[1] & OPT_REF) && f->INSN(a->op[1]).index == II_ADD
93 
    &&(b->opt[1] & OPT_REF) && f->INSN(b->op[1]).index == II_ADD) {
94 
    a = &f->INSN(a->op[1]);
95 
    b = &f->INSN(b->op[1]);
96 
    if (a->opt[1] != b->opt[1] || a->op[1] != b->op[1]
97 
     || a->opt[2] != OPT_CONST || b->opt[2] != OPT_CONST) return 0;
98 
 
99 
    /* Order linearly, we can then join them to bursts */
100 
    return a->op[2] < b->op[2];
101 
  } else return 0;
102 
}
103 
 
104 
/* Schedule memory accesses
105 
 
106 
void schedule_memory (cuc_func *f, int otype)
107 
{
108 
  int b, i, j;
109 
  f->nmsched = 0;
110 
 
111 
  for (b = 0; b < f->num_bb; b++) {
112 
    cuc_insn *insn = f->bb[b].insn;
113 
    for (i = 0; i < f->bb[b].ninsn; i++)
114 
      if (insn[i].type & IT_MEMORY) {
115 
        f->msched[f->nmsched++] = REF (b, i);
116 897 markom 
        if (otype == MO_NONE || otype == MO_WEAK) insn[i].type |= IT_FLAG1; /* mark unscheduled */
117 879 markom 
      }
118 
  }
119 
#if 0
120 
  for (i = 0; i < f->nmsched; i++)
121 
    printf ("[%i]%i%c ", f->msched[i], f->mtype[i] & MT_WIDTH, (f->mtype[i] & MT_BURST) ? (f->mtype[i] & MT_BURSTE) ? 'E' : 'B' : ' ');
122 
  printf ("\n");
123 
#endif
124 
 
125 
  /* We can reorder just more loose types
126 
     We assume, that memory accesses are currently in valid (but not neccesserly)
127 
     optimal order */
128 897 markom 
  if (otype == MO_WEAK || otype == MO_NONE) {
129 879 markom 
    for (i = 0; i < f->nmsched; i++) {
130 
      int best = i;
131 
      int tmp;
132 
      for (j = i + 1; j < f->nmsched; j++) if (REF_BB(f->msched[j]) == REF_BB(f->msched[best])) {
133 
        if (mem_ordering_cmp (f, &f->INSN (f->msched[j]), &f->INSN(f->msched[best]))) {
134 
          /* Check dependencies */
135 
          dep_list *t = f->INSN(f->msched[j]).dep;
136 
          while (t) {
137 
            if (f->INSN(t->ref).type & IT_FLAG1) break;
138 
            t = t->next;
139 
          }
140 
          if (!t) best = j; /* no conflicts -> ok */
141 
        }
142 
      }
143 
 
144 
      /* we have to shift instructions up, to maintain valid dependencies
145 
         and make space for best candidate */
146 
 
147 
      /* make local copy */
148 
      tmp = f->msched[best];
149 
      for (j = best; j > i; j--) f->msched[j] = f->msched[j - 1];
150 
      f->msched[i] = tmp;
151 
      f->INSN(f->msched[i]).type &= ~IT_FLAG1; /* mark scheduled */
152 
    }
153 
  }
154 
 
155 
#if 0
156 
  for (i = 0; i < f->nmsched; i++)
157 
    printf ("[%i]%i%c ", f->msched[i], f->mtype[i] & MT_WIDTH, (f->mtype[i] & MT_BURST) ? (f->mtype[i] & MT_BURSTE) ? 'E' : 'B' : ' ');
158 
  printf ("\n");
159 
#endif
160 
 
161 904 markom 
  /* Assign memory types */
162 879 markom 
  for (i = 0; i < f->nmsched; i++) {
163 
    cuc_insn *a = &f->INSN(f->msched[i]);
164 907 markom 
    f->mtype[i] = !II_IS_LOAD(a->index) ? MT_STORE : MT_LOAD;
165 879 markom 
    f->mtype[i] |= II_MEM_WIDTH (a->index);
166 
    if (a->type & IT_SIGNED) f->mtype[i] |= MT_SIGNED;
167 
  }
168 
 
169 904 markom 
  /* Check if they address the same location, so we can join them */
170 
  if (otype == MO_WEAK || otype == MO_NONE) {
171 
    for (i = 1, j = 1; i < f->nmsched; i++)
172 
      /* Exclude memory stores and different memory types */
173 907 markom 
      if (f->mtype[i - 1] == f->mtype[i] && f->mtype[i] & MT_LOAD) {
174 904 markom 
        cuc_insn *a = &f->INSN(f->msched[i - 1]);
175 
        cuc_insn *b = &f->INSN(f->msched[i]);
176 
        if ((a->opt[1] & OPT_REF) && f->INSN(a->op[1]).index == II_ADD
177 
          &&(b->opt[1] & OPT_REF) && f->INSN(b->op[1]).index == II_ADD) {
178 
          a = &f->INSN(a->op[1]);
179 
          b = &f->INSN(b->op[1]);
180 
          /* Not in usual form? */
181 
          if (a->opt[1] != b->opt[1] || a->op[1] != b->op[1]
182 
           || a->opt[2] != OPT_CONST || b->opt[2] != OPT_CONST) goto keep;
183 
 
184 
          //printf ("%i %i, ", a->op[2], b->op[2]);
185 
 
186 
          /* Check if they are the same => do not copy */
187 
          if (a->op[2] == b->op[2]
188 
            && REF_BB(f->msched[i - 1]) == REF_BB(f->msched[i])) {
189 
            /* yes => remove actual instruction */
190 
            int t1 = MIN (f->msched[i - 1], f->msched[i]);
191 
            int t2 = MAX (f->msched[i - 1], f->msched[i]);
192 
            int b, i, j;
193 
            cucdebug (2, "Removing %x_%x and using %x_%x instead.\n",
194 
              REF_BB(t2), REF_I(t2), REF_BB(t1), REF_I(t1));
195 
            change_insn_type (&f->INSN(t2), II_NOP);
196 
            /* Update references */
197 
            for (b = 0; b < f->num_bb; b++)
198 
              for (i = 0; i < f->bb[b].ninsn; i++)
199 
                for (j = 0; j < MAX_OPERANDS; j++)
200 
                  if (f->bb[b].insn[i].opt[j] & OPT_REF && f->bb[b].insn[i].op[j] == t2)
201 
                    f->bb[b].insn[i].op[j] = t1;
202 
 
203 
          } else goto keep;
204 
        }
205 
      } else {
206 
keep:
207 
        f->msched[j] = f->msched[i];
208 
        f->mtype[j++] = f->mtype[i];
209 
      }
210 
    f->nmsched = j;
211 
  }
212 
 
213 897 markom 
  if (config.cuc.enable_bursts) {
214 879 markom 
    //printf ("\n");
215 
    for (i = 1; i < f->nmsched; i++) {
216 
      cuc_insn *a = &f->INSN(f->msched[i - 1]);
217 
      cuc_insn *b = &f->INSN(f->msched[i]);
218 
      int aw = f->mtype[i - 1] & MT_WIDTH;
219 
 
220 
      if ((a->opt[1] & OPT_REF) && f->INSN(a->op[1]).index == II_ADD
221 
        &&(b->opt[1] & OPT_REF) && f->INSN(b->op[1]).index == II_ADD) {
222 
        a = &f->INSN(a->op[1]);
223 
        b = &f->INSN(b->op[1]);
224 
        /* Not in usual form? */
225 
        if (a->opt[1] != b->opt[1] || a->op[1] != b->op[1]
226 
         || a->opt[2] != OPT_CONST || b->opt[2] != OPT_CONST) continue;
227 
 
228 
        //printf ("%i %i, ", a->op[2], b->op[2]);
229 
 
230 
        /* Check if they touch together */
231 
        if (a->op[2] + aw == b->op[2]) {
232 
          /* yes => do burst */
233 
          f->mtype[i - 1] &= ~MT_BURSTE;
234 
          f->mtype[i - 1] |= MT_BURST;
235 
          f->mtype[i] |= MT_BURST | MT_BURSTE;
236 
        }
237 
      }
238 
    }
239 
  }
240 
 
241 
#if 0
242 
  printf ("\n");
243 
  for (i = 0; i < f->nmsched; i++)
244 
    printf ("[%i]%i%c ", f->msched[i], f->mtype[i] & MT_WIDTH, (f->mtype[i] & MT_BURST) ? (f->mtype[i] & MT_BURSTE) ? 'E' : 'B' : ' ');
245 
  printf ("\n");
246 
#endif
247 
 
248 
  /* We don't need dependencies in non-memory instructions */
249 
  for (b = 0; b < f->num_bb; b++) {
250 
    cuc_insn *insn = f->bb[b].insn;
251 
    for (i = 0; i < f->bb[b].ninsn; i++) if (!(insn[i].type & IT_MEMORY))
252 
      dispose_list (&insn[i].dep);
253 
  }
254 
 
255 
  /* Reduce number of dependecies, keeping just direct dependencies, based on memory schedule */
256 
  {
257 907 markom 
    int lastl[3] = {-1, -1, -1};
258 
    int lasts[3] = {-1, -1, -1};
259 
    int lastc[3] = {-1, -1, -1};
260 
    int last_load = -1, last_store = -1, last_call = -1;
261 879 markom 
    for (i = 0; i < f->nmsched; i++) {
262 907 markom 
      int t = f->mtype[i] & MT_LOAD ? 0 : f->mtype[i] & MT_STORE ? 1 : 2;
263 879 markom 
      int maxl = lastl[t];
264 
      int maxs = lasts[t];
265 907 markom 
      int maxc = lastc[t];
266 879 markom 
      dep_list *tmp = f->INSN(f->msched[i]).dep;
267 
      while (tmp) {
268 
        if (f->INSN(tmp->ref).type & IT_MEMORY && REF_BB(tmp->ref) == REF_BB(f->msched[i])) {
269 
          /* Search for the reference */
270 
          for (j = 0; j < f->nmsched; j++) if (f->msched[j] == tmp->ref) break;
271 
          assert (j < f->nmsched);
272 907 markom 
          if (f->mtype[j] & MT_STORE) {
273 879 markom 
            if (maxs < j) maxs = j;
274 907 markom 
          } else if (f->mtype[j] & MT_LOAD) {
275 879 markom 
            if (maxl < j) maxl = j;
276 907 markom 
          } else if (f->mtype[j] & MT_CALL) {
277 
            if (maxc < j) maxc = j;
278 879 markom 
          }
279 
        }
280 
        tmp = tmp->next;
281 
      }
282 
      dispose_list (&f->INSN(f->msched[i]).dep);
283 907 markom 
      if (f->mtype[i] & MT_STORE) {
284 879 markom 
        maxs = last_store;
285 
        last_store = i;
286 907 markom 
      } else if (f->mtype[i] & MT_LOAD) {
287 879 markom 
        maxl = last_load;
288 
        last_load = i;
289 907 markom 
      } else if (f->mtype[i] & MT_CALL) {
290 
        maxc = last_call;
291 
        last_call = i;
292 879 markom 
      }
293 
 
294 
      if (maxl > lastl[t]) {
295 
        add_dep (&f->INSN(f->msched[i]).dep, f->msched[maxl]);
296 
        lastl[t] = maxl;
297 
      }
298 
      if (maxs > lasts[t]) {
299 
        add_dep (&f->INSN(f->msched[i]).dep, f->msched[maxs]);
300 
        lasts[t] = maxs;
301 
      }
302 907 markom 
      if (maxc > lastc[t]) {
303 
        add_dep (&f->INSN(f->msched[i]).dep, f->msched[maxc]);
304 
        lastc[t] = maxc;
305 
      }
306 879 markom 
      //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);
307 
 
308 
      /* What we have to wait to finish this BB? */
309 
      if (i + 1 >= f->nmsched || REF_BB(f->msched[i + 1]) != REF_BB(f->msched[i])) {
310 
        if (last_load > lastl[t]) {
311 
          add_dep (&f->bb[REF_BB(f->msched[i])].mdep, f->msched[last_load]);
312 
          lastl[t] = last_load;
313 
        }
314 
        if (last_store > lasts[t]) {
315 
          add_dep (&f->bb[REF_BB(f->msched[i])].mdep, f->msched[last_store]);
316 
          lasts[t] = last_store;
317 
        }
318 907 markom 
        if (last_call > lastc[t]) {
319 
          add_dep (&f->bb[REF_BB(f->msched[i])].mdep, f->msched[last_call]);
320 
          lastc[t] = last_call;
321 
        }
322 879 markom 
      }
323 
    }
324 
  }
325 
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.