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

Subversion Repositories or1k

[/] [or1k/] [tags/] [nog_patch_34/] [or1ksim/] [cuc/] [insn.c] - Blame information for rev 897

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

Line No. Rev Author Line
1 879 markom 
/* insn.c -- OpenRISC Custom Unit Compiler, instruction support
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 
/* Table of known instructions.  Watch out for indexes I_*! */
29 
const cuc_known_insn known[II_LAST + 1] = {
30 
{"add", 1, "assign \1 = \2 + \3;"},
31 
{"sub", 0, "assign \1 = \2 - \3;"},
32 
{"and", 1, "assign \1 = \2 & \3;"},
33 
{"or",  1, "assign \1 = \2 | \3;"},
34 
{"xor", 1, "assign \1 = \2 ^ \3;"},
35 
{"mul", 1, "assign \1 = \2 * \3;"},
36 
 
37 
{"srl", 0, "assign \1 = \2 >> \3;"},
38 
{"sll", 0, "assign \1 = \2 << \3;"},
39 
{"sra", 0, "assign \1 = ({32{\2[31]}} << (6'd32-{1'b0, \3}))\n\
40 
                 | \2 >> \3;"},
41 
 
42 
{"lb",  0, "always @(posedge clk or posedge rst)"},
43 
{"lh",  0, "always @(posedge clk or posedge rst)"},
44 
{"lw",  0, "always @(posedge clk or posedge rst)"},
45 
{"sb",  0, "/* mem8[\2] = \1 */"},
46 
{"sh",  0, "/* mem16[\2] = \1 */"},
47 
{"sw",  0, "/* mem32[\2] = \1 */"},
48 
 
49 
{"sfeq", 1, "assign \1 = \2 == \3;"},
50 
{"sfne", 1, "assign \1 = \2 != \3;"},
51 
{"sfle", 0, "assign \1 = \2 <= \3;"},
52 
{"sflt", 0, "assign \1 = \2 < \3;"},
53 
{"sfgt", 0, "assign \1 = \2 > \3;"},
54 
{"sfge", 0, "assign \1 = \2 >= \3;"},
55 
{"sfor", 1, "assign \1 = \2 || \3;"},
56 
{"bf",  0, ""},
57 
 
58 
{"lrbb", 0,"always @(posedge clk or posedge rst)"},
59 
{"cmov", 0,"assign \1 = \4 ? \2 : \3;"},
60 
{"reg", 0, "always @(posedge clk or posedge rst)"},
61 
 
62 
{"nop", 0, NULL}};
63 
 
64 
/* Find known instruction and attach them to insn */
65 
void change_insn_type (cuc_insn *i, int index)
66 
{
67 
  int j;
68 
  assert (index >= 0 && index <= II_LAST);
69 
  i->index = index;
70 
  if (i->index == II_NOP) {
71 
    for (j = 0; j < MAX_OPERANDS; j++) i->opt[j] = OPT_NONE;
72 
    i->type = 0;
73 
    i->dep = NULL;
74 
  }
75 
}
76 
 
77 
/* Returns instruction name */
78 
const char *cuc_insn_name (cuc_insn *ii) {
79 
  if (ii->index < 0 || ii->index > II_LAST) return "???";
80 
  else return known[ii->index].name;
81 
}
82 883 markom 
 
83 897 markom 
/* Prints out instructions */
84 
void print_insns (cuc_insn *insn, int ninsn, int verbose)
85 
{
86 
  int i, j;
87 
  for (i = 0; i < ninsn; i++) {
88 
    dep_list *l = insn[i].dep;
89 
    printf ("%4x%c %-4s ", i, insn[i].index >= 0 ? ':' : '?', cuc_insn_name (&insn[i]));
90 
    if (verbose) {
91 
      printf ("%-20s insn = %08x, index = %i, type = %04x ",
92 
                      insn[i].disasm, insn[i].insn, insn[i].index, insn[i].type);
93 
    } else printf ("type = %04x ", insn[i].type);
94 
    for (j = 0; j < MAX_OPERANDS; j++) {
95 
      if (insn[i].opt[j] & OPT_DEST) printf ("*");
96 
      switch (insn[i].opt[j] & ~OPT_DEST) {
97 
        case OPT_NONE: break;
98 
        case OPT_CONST: printf ("0x%08x, ", insn[i].op[j]); break;
99 
        case OPT_JUMP: printf ("J%x ", insn[i].op[j]); break;
100 
        case OPT_REGISTER: printf ("r%i, ", insn[i].op[j]); break;
101 
        case OPT_REF: printf ("[%x.%x], ", REF_BB(insn[i].op[j]), REF_I(insn[i].op[j])); break;
102 
        case OPT_BB: printf ("BB%x, ", insn[i].op[j]); break;
103 
        case OPT_LRBB: printf ("LRBB, "); break;
104 
        default:
105 
          fprintf (stderr, "Invalid operand type %s(%x.%x) = %x\n",
106 
                         cuc_insn_name (&insn[i]), i, j, insn[i].opt[j]);
107 
          assert (0);
108 
      }
109 
    }
110 
    if (l) {
111 
      printf ("\n\tdep:");
112 
      while (l) {
113 
        printf (" [%x.%x],", REF_BB (l->ref), REF_I (l->ref));
114 
        l = l->next;
115 
      }
116 
    }
117 
    printf ("\n");
118 
  }
119 
}
120 
 
121 
void add_dep (dep_list **list, int dep)
122 
{
123 
  dep_list *ndep;
124 
  dep_list **tmp = list;
125 
 
126 
  while (*tmp) {
127 
    if ((*tmp)->ref == dep) return; /* already there */
128 
    tmp = &((*tmp)->next);
129 
  }
130 
  ndep = (dep_list *)malloc (sizeof (dep_list));
131 
  ndep->ref = dep;
132 
  ndep->next = NULL;
133 
  *tmp = ndep;
134 
}
135 
 
136 
void dispose_list (dep_list **list)
137 
{
138 
  while (*list) {
139 
    dep_list *tmp = *list;
140 
    *list = tmp->next;
141 
    free (tmp);
142 
  }
143 
}
144 
 
145 
void add_data_dep (cuc_func *f)
146 
{
147 
  int b, i, j;
148 
  dep_list *tmp;
149 
  for (b = 0; b < f->num_bb; b++) {
150 
    cuc_insn *insn = f->bb[b].insn;
151 
    for (i = 0; i < f->bb[b].ninsn; i++)
152 
      for (j = 0; j < MAX_OPERANDS; j++) {
153 
        fflush (stdout);
154 
        if (insn[i].opt[j] & OPT_REF) {
155 
          /* Copy list from predecessor */
156 
          dep_list *l = f->INSN(insn[i].op[j]).dep;
157 
          while (l) {
158 
            add_dep (&insn[i].dep, l->ref);
159 
            l = l->next;
160 
          }
161 
          /* add predecessor */
162 
          add_dep (&insn[i].dep, insn[i].op[j]);
163 
        }
164 
      }
165 
  }
166 
}
167 
 
168 
/* returns nonzero, if instruction was simplified */
169 
int apply_edge_condition (cuc_insn *ii)
170 
{
171 
  unsigned int c = ii->op[2];
172 
 
173 
  if (ii->index == II_AND) {
174 
    if (ii->opt[2] & OPT_CONST && c == 0) {
175 
      change_insn_type (ii, II_ADD);
176 
      ii->op[1] = 0; ii->opt[1] = OPT_CONST;
177 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
178 
      return 1;
179 
    }
180 
  } else if (ii->index == II_OR) {
181 
    if (ii->opt[2] & OPT_CONST && c == 0xffffffff) {
182 
      change_insn_type (ii, II_ADD);
183 
      ii->op[1] = c; ii->opt[1] = OPT_CONST;
184 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
185 
      return 1;
186 
    }
187 
  } else if (ii->index == II_SUB) {
188 
    if (ii->opt[1] == ii->opt[2] && ii->op[1] == ii->op[2]) {
189 
      change_insn_type (ii, II_ADD);
190 
      ii->op[1] = 0; ii->opt[1] = OPT_CONST;
191 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
192 
      return 1;
193 
    }
194 
  } else if (ii->index == II_MUL) {
195 
    if (ii->opt[2] & OPT_CONST && c == 0) {
196 
      change_insn_type (ii, II_ADD);
197 
      ii->op[1] = 0; ii->opt[1] = OPT_CONST;
198 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
199 
      return 1;
200 
    } else
201 
    if (ii->opt[2] & OPT_CONST && c == 1) {
202 
      change_insn_type (ii, II_ADD);
203 
      ii->op[1] = c; ii->opt[1] = OPT_CONST;
204 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
205 
      return 1;
206 
    } else
207 
    if (ii->opt[2] & OPT_CONST && c == 0xffffffff) {
208 
      change_insn_type (ii, II_SUB);
209 
      ii->op[2] = ii->op[1]; ii->opt[2] = ii->opt[1];
210 
      ii->op[1] = 0; ii->opt[1] = OPT_CONST;
211 
      return 1;
212 
    }
213 
  } else if (ii->index == II_SRL) {
214 
    if (ii->opt[2] & OPT_CONST && c == 0) {
215 
      change_insn_type (ii, II_ADD);
216 
      ii->op[1] = c; ii->opt[1] = OPT_CONST;
217 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
218 
      return 1;
219 
    } else if (ii->opt[2] & OPT_CONST && c >= 32) {
220 
      change_insn_type (ii, II_ADD);
221 
      ii->op[1] = 0; ii->opt[1] = OPT_CONST;
222 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
223 
      return 1;
224 
    }
225 
  } else if (ii->index == II_SLL) {
226 
    if (ii->opt[2] & OPT_CONST && c == 0) {
227 
      change_insn_type (ii, II_ADD);
228 
      ii->op[1] = c; ii->opt[1] = OPT_CONST;
229 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
230 
      return 1;
231 
    } else if (ii->opt[2] & OPT_CONST && c >= 32) {
232 
      change_insn_type (ii, II_ADD);
233 
      ii->op[1] = 0; ii->opt[1] = OPT_CONST;
234 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
235 
      return 1;
236 
    }
237 
  } else if (ii->index == II_SRA) {
238 
    if (ii->opt[2] & OPT_CONST && c == 0) {
239 
      change_insn_type (ii, II_ADD);
240 
      ii->op[1] = c; ii->opt[1] = OPT_CONST;
241 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
242 
      return 1;
243 
    }
244 
  } else if (ii->index == II_CMOV) {
245 
    if (ii->opt[1] == ii->opt[2] && ii->op[1] == ii->op[2]) {
246 
      change_insn_type (ii, II_ADD);
247 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
248 
      ii->opt[3] = OPT_NONE;
249 
      return 1;
250 
    }
251 
  }
252 
  return 0;
253 
}
254 
 
255 
/* Optimizes dataflow tree */
256 
void optimize_tree (cuc_func *f)
257 
{
258 
  int b, i, j;
259 
  int modified;
260 
 
261 
  do {
262 
    modified = 0;
263 
    for (b = 0; b < f->num_bb; b++) if (!(f->bb[b].type & BB_DEAD)) {
264 
      for (i = 0; i < f->bb[b].ninsn; i++) {
265 
        cuc_insn *ii = &f->bb[b].insn[i];
266 
        /* We tend to have the third parameter const if instruction is cumutative */
267 
        if ((ii->opt[1] & OPT_CONST) && !(ii->opt[2] & OPT_CONST)
268 
            && known[ii->index].comutative) {
269 
          unsigned long t = ii->opt[1];
270 
          ii->opt[1] = ii->opt[2];
271 
          ii->opt[2] = t;
272 
          t = ii->op[1];
273 
          ii->op[1] = ii->op[2];
274 
          ii->op[2] = t;
275 
          modified = 1; cucdebug (2, "%08x:<>\n", REF(b, i));
276 
        }
277 
 
278 
        /* Try to do the promotion */
279 
        /* We have two consecutive expressions, containing constants,
280 
         * if previous is a simple expression we can handle it simply: */
281 
        for (j = 0; j < MAX_OPERANDS; j++)
282 
          if (ii->opt[j] & OPT_REF) {
283 
            cuc_insn *t = &f->INSN(ii->op[j]);
284 
            if (f->INSN(ii->op[j]).index == II_ADD
285 
             && f->INSN(ii->op[j]).opt[2] & OPT_CONST
286 
             && f->INSN(ii->op[j]).op[2] == 0
287 
             && !(ii->type & IT_MEMORY && t->type & IT_MEMADD)
288 
             && !(ii->type & IT_BRANCH) && !(t->type & IT_COND)) {
289 
            /* do not promote through add-mem, and branches */
290 
              modified = 1; cucdebug (2, "%8x:promote%i %8x %8x\n", REF (b, i), j, ii->op[j], t->op[1]);
291 
              ii->op[j] = t->op[1]; ii->opt[j] = t->opt[1];
292 
            }
293 
          }
294 
 
295 
        /* In case of x = cmov x, y; or x = cmov y, x; we have
296 
           asynchroneous loop -> remove it */
297 
        if (ii->index == II_CMOV) {
298 
          int f = 0;
299 
          if ((ii->opt[1] & OPT_REF) && ii->op[1] == REF (b, i)) f = 1;
300 
          if ((ii->opt[2] & OPT_REF) && ii->op[2] == REF (b, i)) f = 2;
301 
          if (ii->opt[1] == ii->opt[2] && ii->op[1] == ii->op[2]) f = 2;
302 
          if (f) {
303 
            change_insn_type (ii, II_ADD);
304 
            cucdebug (2, "%8x:cmov     %i\n", REF(b, i), f);
305 
            ii->opt[f] = OPT_CONST;
306 
            ii->op[f] = 0;
307 
            ii->opt[3] = OPT_NONE;
308 
            modified = 1;
309 
            continue;
310 
          }
311 
        }
312 
 
313 
        /* Do nothing to volatile instructions */
314 
        if (ii->type & IT_VOLATILE) continue;
315 
 
316 
        /* Check whether we can simplify the instruction */
317 
        if (apply_edge_condition (ii)) {
318 
          modified = 1;
319 
          continue;
320 
        }
321 
        /* We cannot do anything more if at least one is not constant */
322 
        if (!(ii->opt[2] & OPT_CONST)) continue;
323 
 
324 
        if (ii->opt[1] & OPT_CONST) { /* We have constant expression */
325 
          unsigned long value;
326 
          int ok = 1;
327 
          /* Was constant expression already? */
328 
          if (ii->index == II_ADD && !ii->op[2]) continue;
329 
 
330 
          if (ii->index == II_ADD) value = ii->op[1] + ii->op[2];
331 
          else if (ii->index == II_SUB) value = ii->op[1] - ii->op[2];
332 
          else if (ii->index == II_SLL) value = ii->op[1] << ii->op[2];
333 
          else if (ii->index == II_SRL) value = ii->op[1] >> ii->op[2];
334 
          else if (ii->index == II_MUL) value = ii->op[1] * ii->op[2];
335 
          else if (ii->index == II_OR) value = ii->op[1] | ii->op[2];
336 
          else if (ii->index == II_XOR) value = ii->op[1] ^ ii->op[2];
337 
          else if (ii->index == II_AND) value = ii->op[1] & ii->op[2];
338 
          else ok = 0;
339 
          if (ok) {
340 
            change_insn_type (ii, II_ADD);
341 
            ii->op[0] = -1; ii->opt[0] = OPT_REGISTER | OPT_DEST;
342 
            ii->op[1] = value; ii->opt[1] = OPT_CONST;
343 
            ii->op[2] = 0; ii->opt[2] = OPT_CONST;
344 
            modified = 1; cucdebug (2, "%8x:const\n", REF (b, i));
345 
          }
346 
        } else if (ii->opt[1] & OPT_REF) {
347 
          cuc_insn *prev = &f->INSN(ii->op[1]);
348 
          /* Is this just a link? */
349 
          if (ii->index == II_ADD
350 
           && !(ii->type & IT_MEMADD) && ii->op[2] == 0) {
351 
            int b1, i1, j1;
352 
            cucdebug (2, "%8x:link      %8x: ", REF(b, i), ii->op[1]);
353 
            for (b1 = 0; b1 < f->num_bb; b1++) if (!(f->bb[b1].type & BB_DEAD))
354 
              for (i1 = 0; i1 < f->bb[b1].ninsn; i1++)
355 
                for (j1 = 0; j1 < MAX_OPERANDS; j1++)
356 
                  if ((f->bb[b1].insn[i1].opt[j1] & OPT_REF)
357 
                   && f->bb[b1].insn[i1].op[j1] == REF(b, i)) {
358 
                    cucdebug (2, "%x ", REF (b1, i1));
359 
                    f->bb[b1].insn[i1].op[j1] = ii->op[1];
360 
                  }
361 
            cucdebug (2, "\n");
362 
            change_insn_type (ii, II_NOP);
363 
          } else if (prev->opt[2] & OPT_CONST) {
364 
            /* Handle some common cases */
365 
            /* add - add joining */
366 
            if (ii->index == II_ADD && prev->index == II_ADD) {
367 
              ii->op[1] = prev->op[1]; ii->opt[1] = prev->opt[1];
368 
              ii->op[2] += prev->op[2];
369 
              modified = 1; cucdebug (2, "%8x: add-add\n", REF(b, i));
370 
            } else /* add - sub joining */
371 
            if (ii->index == II_ADD && prev->index == II_SUB) {
372 
              change_insn_type (&insn[i], II_SUB);
373 
              ii->op[1] = prev->op[1]; ii->opt[1] = prev->opt[1];
374 
              ii->op[2] += prev->op[2];
375 
              modified = 1; cucdebug (2, "%8x: add-sub\n", REF(b, i));
376 
            } else /* sub - add joining */
377 
            if (ii->index == II_SUB && prev->index == II_ADD) {
378 
              ii->op[1] = prev->op[1]; ii->opt[1] = prev->opt[1];
379 
              ii->op[2] += prev->op[2];
380 
              modified = 1; cucdebug (2, "%8x: sub-add\n", REF(b, i));
381 
            }
382 
          }
383 
        }
384 
      }
385 
    }
386 
  } while (modified);
387 
}
388 
 
389 
/* Remove nop instructions */
390 
void remove_nops (cuc_func *f)
391 
{
392 
  int b;
393 
  for (b = 0; b < f->num_bb; b++) {
394 
    int c, d = 0, i, j;
395 
    cuc_insn *insn = f->bb[b].insn;
396 
    for (i = 0; i < f->bb[b].ninsn; i++)
397 
      if (insn[i].index != II_NOP) {
398 
        reloc [i] = d;
399 
        insn[d++] = insn[i];
400 
      } else {
401 
        reloc[i] = d; /* For jumps only */
402 
      }
403 
    f->bb[b].ninsn = d;
404 
 
405 
    /* Relocate references from all basic blocks */
406 
    for (c = 0; c < f->num_bb; c++)
407 
      for (i = 0; i < f->bb[c].ninsn; i++) {
408 
        dep_list *d = f->bb[c].insn[i].dep;
409 
        for (j = 0; j < MAX_OPERANDS; j++)
410 
          if ((f->bb[c].insn[i].opt[j] & OPT_REF)
411 
            && REF_BB(f->bb[c].insn[i].op[j]) == b)
412 
            f->bb[c].insn[i].op[j] = REF (b, reloc[REF_I (f->bb[c].insn[i].op[j])]);
413 
 
414 
        while (d) {
415 
          if (REF_BB(d->ref) == b) d->ref = REF (b, reloc[REF_I (d->ref)]);
416 
          d = d->next;
417 
        }
418 
      }
419 
  }
420 
}
421 
 
422 
/* Remove unused assignments */
423 
void remove_dead (cuc_func *f)
424 
{
425 
  int b, i, j;
426 
  for (b = 0; b < f->num_bb; b++)
427 
    for (i = 0; i < f->bb[b].ninsn; i++)
428 
      if (!(f->bb[b].insn[i].type & (IT_VOLATILE | IT_OUTPUT)))
429 
        f->bb[b].insn[i].type |= IT_UNUSED;
430 
 
431 
  for (b = 0; b < f->num_bb; b++) {
432 
    for (i = 0; i < f->bb[b].ninsn; i++)
433 
      for (j = 0; j < MAX_OPERANDS; j++)
434 
        if (f->bb[b].insn[i].opt[j] & OPT_REF) {
435 
          f->INSN(f->bb[b].insn[i].op[j]).type &= ~IT_UNUSED;
436 
        }
437 
  }
438 
 
439 
  for (b = 0; b < f->num_bb; b++)
440 
    for (i = 0; i < f->bb[b].ninsn; i++)
441 
      if (f->bb[b].insn[i].type & IT_UNUSED) {
442 
        change_insn_type (&f->bb[b].insn[i], II_NOP);
443 
      }
444 
 
445 
  remove_nops (f);
446 
}
447 
 
448 
/* Removes trivial register assignments */
449 
void remove_trivial_regs (cuc_func *f)
450 
{
451 
  int b, i;
452 
  for (i = 0; i < MAX_REGS; i++) f->saved_regs[i] = call_saved[i];
453 
 
454 
  for (b = 0; b < f->num_bb; b++) {
455 
    cuc_insn *insn = f->bb[b].insn;
456 
    for (i = 0; i < f->bb[b].ninsn; i++) {
457 
      if (insn[i].index == II_ADD
458 
        && insn[i].opt[0] & OPT_REGISTER
459 
        && insn[i].opt[1] & OPT_REGISTER && insn[i].op[0] == insn[i].op[1]
460 
        && insn[i].opt[2] & OPT_CONST && insn[i].op[2] == 0) {
461 
          if (insn[i].type & IT_OUTPUT) f->saved_regs[insn[i].op[0]] = 1;
462 
          change_insn_type (&insn[i], II_NOP);
463 
        }
464 
    }
465 
  }
466 
  if (cuc_debug >= 2) {
467 
    printf ("saved regs ");
468 
    for (i = 0; i < MAX_REGS; i++) printf ("%i:%i ", i, f->saved_regs[i]);
469 
    printf ("\n");
470 
  }
471 
  remove_nops (f);
472 
}
473 
 
474 
/* Determine inputs and outputs */
475 
void set_io (cuc_func *f)
476 
{
477 
  int b, i, j;
478 
  /* Determine register usage */
479 
  for (i = 0; i < MAX_REGS; i++) {
480 
    f->lur[i] = -1;
481 
    f->used_regs[i] = 0;
482 
  }
483 
  for (b = 0; b < f->num_bb; b++) {
484 
    for (i = 0; i < f->bb[b].ninsn; i++)
485 
      for (j = 0; j < MAX_OPERANDS; j++)
486 
        if (f->bb[b].insn[i].opt[j] & OPT_REGISTER && f->bb[b].insn[i].op[j] >= 0)
487 
          if (f->bb[b].insn[i].opt[j] & OPT_DEST) f->lur[f->bb[b].insn[i].op[j]] = REF (b, i);
488 
          else f->used_regs[f->bb[b].insn[i].op[j]] = 1;
489 
  }
490 
}
491 
 
492 
/* relocate all accesses inside of BB b to back/fwd */
493 
static void relocate_bb (cuc_bb *bb, int b, int back, int fwd)
494 
{
495 
  int i, j;
496 
  for (i = 0; i < bb->ninsn; i++)
497 
    for (j = 0; j < MAX_OPERANDS; j++)
498 
      if (bb->insn[i].opt[j] & OPT_REF
499 
       && REF_BB (bb->insn[i].op[j]) == b) {
500 
        int t = REF_I (bb->insn[i].op[j]);
501 
        if (t < i) bb->insn[i].op[j] = REF (back, t);
502 
        else bb->insn[i].op[j] = REF (fwd, t);
503 
      }
504 
}
505 
 
506 
/* Latch outputs in loops */
507 
void add_latches (cuc_func *f)
508 
{
509 
  int b, i, j;
510 
 
511 
  //print_cuc_bb (f, "ADD_LATCHES a");
512 
  /* Cuts the tree and marks registers */
513 
  mark_cut (f);
514 
 
515 
  /* Split BBs with more than one group */
516 
  for (b = 0; b < f->num_bb; b++) expand_bb (f, b);
517 
  remove_nops (f);
518 
  //print_cuc_bb (f, "ADD_LATCHES 0");
519 
 
520 
  /* Convert accesses in BB_INLOOP type block to latched */
521 
  for (b = 0; b < f->num_bb; b++) {
522 
    int j;
523 
    for (i = 0; i < f->bb[b].ninsn; i++)
524 
      for (j = 0; j < MAX_OPERANDS; j++) if (f->bb[b].insn[i].opt[j] == OPT_REF) {
525 
        int t = f->bb[b].insn[i].op[j];
526 
        /* If we are pointing to a INLOOP block from outside, or forward
527 
           (= previous loop iteration) we must register that data */
528 
        if ((f->bb[REF_BB(t)].type & BB_INLOOP || config.cuc.no_multicycle)
529 
         && !(f->INSN(t).type & (IT_BRANCH | IT_COND))
530 
         && (REF_BB(t) != b || REF_I(t) >= i)) {
531 
          f->INSN(t).type |= IT_LATCHED;
532 
        }
533 
      }
534 
  }
535 
  //print_cuc_bb (f, "ADD_LATCHES 1");
536 
 
537 
  /* Add latches at the end of blocks as needed */
538 
  for (b = 0; b < f->num_bb; b++) {
539 
    int nreg = 0;
540 
    cuc_insn *insn;
541 
    for (i = 0; i < f->bb[b].ninsn; i++)
542 
      if (f->bb[b].insn[i].type & IT_LATCHED) nreg++;
543 
    if (nreg) {
544 
      insn = (cuc_insn *) malloc (sizeof (cuc_insn) * (f->bb[b].ninsn + nreg));
545 
      j = 0;
546 
      for (i = 0; i < f->bb[b].ninsn; i++) {
547 
        insn[i] = f->bb[b].insn[i];
548 
        if (insn[i].type & IT_LATCHED) {
549 
          cuc_insn *ii = &insn[f->bb[b].ninsn + j++];
550 
          change_insn_type (ii, II_REG);
551 
          ii->op[0] = -1; ii->opt[0] = OPT_DEST | OPT_REGISTER;
552 
          ii->op[1] = REF (b, i); ii->opt[1] = OPT_REF;
553 
          ii->opt[2] = ii->opt[3] = OPT_NONE;
554 
          ii->dep = NULL;
555 
          ii->type = IT_VOLATILE;
556 
          sprintf (ii->disasm, "reg %i_%i", b, i);
557 
        }
558 
      }
559 
      f->bb[b].ninsn += nreg;
560 
      free (f->bb[b].insn);
561 
      f->bb[b].insn = insn;
562 
    }
563 
  }
564 
  //print_cuc_bb (f, "ADD_LATCHES 2");
565 
 
566 
  /* Repair references */
567 
  for (b = 0; b < f->num_bb; b++)
568 
    for (i = 0; i < f->bb[b].ninsn; i++)
569 
      for (j = 0; j < MAX_OPERANDS; j++)
570 
        /* If destination instruction is latched, use register instead */
571 
        if (f->bb[b].insn[i].opt[j] == OPT_REF
572 
         && f->INSN(f->bb[b].insn[i].op[j]).type & IT_LATCHED) {
573 
          int b1, i1;
574 
          b1 = REF_BB (f->bb[b].insn[i].op[j]);
575 
          //cucdebug (2, "%i.%i.%i %x\n", b, i, j, f->bb[b].insn[i].op[j]);
576 
          if (b1 != b || REF_I(f->bb[b].insn[i].op[j]) >= i) {
577 
            for (i1 = f->bb[b1].ninsn - 1; i1 >= 0; i1--) {
578 
              assert (f->bb[b1].insn[i1].index == II_REG);
579 
              if (f->bb[b1].insn[i1].op[1] == f->bb[b].insn[i].op[j]) {
580 
                f->bb[b].insn[i].op[j] = REF (b1, i1);
581 
                break;
582 
              }
583 
            }
584 
          }
585 
        }
586 
}
587 
 
588 883 markom 
/* CSE -- common subexpression elimination */
589 
void cse (cuc_func *f)
590 
{
591 
  int b, i, j, b1, i1, b2, i2, j2;
592 
  for (b1 = 0; b1 < f->num_bb; b1++)
593 
    for (i1 = 0; i1 < f->bb[b1].ninsn; i1++)
594 
      for (b2 = 0; b2 < f->num_bb; b2++)
595 
        for (i2 = 0; i2 < f->bb[b2].ninsn; i2++) {
596 
          cuc_insn *ii1 = &f->bb[b1].insn[i1];
597 
          cuc_insn *ii2 = &f->bb[b2].insn[i2];
598 
 
599 
          /* Do we have an exact match? */
600 
          if (ii1->index == ii2->index) continue;
601 
          if (ii1->type & IT_VOLATILE) continue;
602 
 
603 
          if (ii1->op[1] != ii2->op[1] || ii1->opt[1] != ii2->opt[1]) continue;
604 
          if (ii1->op[2] != ii2->op[2] || ii1->opt[2] != ii2->opt[2]) continue;
605 
          if (ii1->opt[3] != ii2->opt[3]) continue;
606 
          if (ii1->opt[3] != OPT_NONE && ii1->op[3] != ii2->op[3]) continue;
607 
 
608 
          /* Check if we drive outputs? */
609 
          if ((ii1->opt[0] & OPT_REGISTER) && ii1->op[0] >= 0)
610 
            if ((ii2->opt[0] & OPT_REGISTER) && ii2->op[0] >= 0) continue;
611 
            else ii2->op[0] = ii1->op[0];
612 
 
613 
          /* remove duplicated instruction and relink the references */
614 
          change_insn_type (ii2, II_NOP);
615 
          for (b = 0; b < f->num_bb; b++)
616 
            for (i = 0; i < f->bb[b].ninsn; i++)
617 
              for (j = 0; j < MAX_OPERANDS; j++)
618 
                if (f->bb[b].insn[i].opt[j] & OPT_REF && f->bb[b].insn[i].op[j] == REF (b2, i2))
619 
                  f->bb[b].insn[i].op[j] = REF (b1, i1);
620 
        }
621 
}
622 
 
623 
static int count_cmovs (cuc_insn *ii, int match)
624 
{
625 
  int c = 0, j;
626 
  if (match & 2) {
627 
    for (j = 0; j < MAX_OPERANDS; j++)
628 
      if (ii->opt[j] & OPT_DEST) c++;
629 
  }
630 
  if (match & 1) {
631 
    for (j = 0; j < MAX_OPERANDS; j++)
632 
      if (!(ii->opt[j] & OPT_DEST) && ii->opt[j] & OPT_REF) c++;
633 
  } else {
634 
    for (j = 0; j < MAX_OPERANDS; j++)
635 
      if (!(ii->opt[j] & OPT_DEST) && ii->opt[j] != OPT_NONE) c++;
636 
  }
637 
  return c;
638 
}
639 
 
640 897 markom 
static void search_csm (int iter, cuc_func *f, cuc_shared_list *list);
641 
static cuc_shared_list *main_list;
642 883 markom 
static int *iteration;
643 
 
644 897 markom 
/* CSM -- common subexpression matching -- resource sharing
645 
   We try to match tree of instruction inside a BB with as many
646 
   matches as possible. All possibilities are collected and
647 
   options, making situation worse are removed */
648 883 markom 
void csm (cuc_func *f)
649 
{
650 
  int b, i, j;
651 
  int cnt;
652 897 markom 
  cuc_shared_list *list;
653 883 markom 
  cuc_timings timings;
654 
 
655 
  analyse_timings (f, &timings);
656 
  main_list = NULL;
657 
  for (b = 0; b < f->num_bb; b++) {
658 
    assert (iteration = (int *)malloc (sizeof (int) * f->bb[b].ninsn));
659 
    for (i = 0; i < f->bb[b].ninsn; i++) {
660 
      int cnt = 0, cntc = 0;
661 
      double size = 0., sizec = 0.;
662 
      int j2 = 0;
663 
      for (j = 0; j < f->bb[b].ninsn; j++)
664 
        if (f->bb[b].insn[i].index == f->bb[b].insn[j].index) {
665 
          int ok = 1;
666 
          for (j2 = 0; j2 < MAX_OPERANDS; j2++) if (!(f->bb[b].insn[j].opt[j2] & OPT_REF))
667 
            if (f->bb[b].insn[j].opt[j2] != f->bb[b].insn[i].opt[j2]
668 
             || f->bb[b].insn[j].op[j2] != f->bb[b].insn[i].opt[j2]) {
669 
              ok = 0;
670 
              break;
671 
            }
672 
          if (ok) {
673 
            cntc++;
674 
            sizec = sizec + insn_size (&f->bb[b].insn[j]);
675 
          } else {
676 
            cnt++;
677 
            size = size + insn_size (&f->bb[b].insn[j]);
678 
          }
679 
          iteration[j] = 0;
680 
        } else iteration[j] = -1;
681 
      if (cntc > 1) {
682 897 markom 
        assert (list = (cuc_shared_list *)malloc (sizeof (cuc_shared_list)));
683 883 markom 
        list->next = main_list;
684 
        list->from = NULL;
685 
        list->ref = REF (b, i);
686 
        list->cnt = cnt;
687 
        list->cmatch = 1;
688 
        list->cmovs = count_cmovs (&f->bb[b].insn[i], 3);
689 
        list->osize = sizec;
690 
        list->size = ii_size (f->bb[b].insn[i].index, 1);
691 
        main_list = list;
692 
        search_csm (0, f, list);
693 
      }
694 
      if (cnt > 1) {
695 897 markom 
        assert (list = (cuc_shared_list *)malloc (sizeof (cuc_shared_list)));
696 883 markom 
        list->next = main_list;
697 
        list->from = NULL;
698 
        list->ref = REF (b, i);
699 
        list->cnt = cnt + cntc;
700 
        list->cmatch = 0;
701 
        list->cmovs = count_cmovs (&f->bb[b].insn[i], 2);
702 
        list->osize = size + sizec;
703 
        list->size = ii_size (f->bb[b].insn[i].index, 0);
704 
        main_list = list;
705 
        search_csm (0, f, list);
706 
      }
707 
    }
708 
    free (iteration);
709 
  }
710 
 
711 
  for (list = main_list; list; list = list->next) list->dead = 0;
712 
  cnt = 0;
713 
  for (list = main_list; list; list = list->next) if (!list->dead) cnt++;
714 
  cucdebug (1, "noptions = %i\n", cnt);
715 
 
716 
  /* Now we will check the real size of the 'improvements'; if the size
717 
     actually increases, we abandom the option */
718 
  for (list = main_list; list; list = list->next)
719 
    if (list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size >= list->osize) list->dead = 1;
720 
 
721 
  cnt = 0;
722 
  for (list = main_list; list; list = list->next) if (!list->dead) cnt++;
723 
  cucdebug (1, "noptions = %i\n", cnt);
724 
 
725 
  /* Count number of instructions grouped */
726 
  for (list = main_list; list; list = list->next) {
727 897 markom 
    cuc_shared_list *l = list;
728 883 markom 
    int c = 0;
729 
    while (l) {
730 
      c++;
731 
      if (f->INSN(l->ref).type & (IT_VOLATILE | IT_MEMORY | IT_MEMADD)) list->dead = 1;
732 
      l = l->from;
733 
    }
734 
    list->ninsn = c;
735 
  }
736 
 
737 
  cnt = 0;
738 
  for (list = main_list; list; list = list->next)
739 
    if (!list->dead) cnt++;
740 
  cucdebug (1, "noptions = %i\n", cnt);
741 
 
742 
#if 1
743 
  /* We can get a lot of options here, so we will delete duplicates */
744 
  for (list = main_list; list; list = list->next) if (!list->dead) {
745 897 markom 
    cuc_shared_list *l;
746 883 markom 
    for (l = list->next; l; l = l->next) if (!l->dead) {
747 
      int ok = 1;
748 897 markom 
      cuc_shared_list *t1 = list;
749 
      cuc_shared_list *t2 = l;
750 883 markom 
      while (ok && t1 && t2) {
751 
        if (f->INSN(t1->ref).index == f->INSN(t2->ref).index) {
752 
          /* If other operands are matching, we must check for them also */
753 
          if (t1->cmatch) {
754 
            int j;
755 
            for (j = 0; j < MAX_OPERANDS; j++)
756 
              if (!(f->INSN(t1->ref).opt[j] & OPT_REF) || !(f->INSN(t2->ref).opt[j] & OPT_REF)
757 
               || f->INSN(t1->ref).opt[j] != f->INSN(t2->ref).opt[j]
758 
               || f->INSN(t1->ref).op[j] != f->INSN(t2->ref).op[j]) {
759 
                ok = 0;
760 
                break;
761 
              }
762 
          }
763 
 
764 
          /* This option is duplicate, remove */
765 
          if (ok) t1->dead = 1;
766 
        }
767 
        t1 = t1->from;
768 
        t2 = t2->from;
769 
      }
770 
    }
771 
  }
772 
  cnt = 0;
773 
  for (list = main_list; list; list = list->next) if (!list->dead) cnt++;
774 
  cucdebug (1, "noptions = %i\n", cnt);
775 
#endif
776 
  /* Print out */
777 
  for (list = main_list; list; list = list->next) if (!list->dead) {
778 897 markom 
    cuc_shared_list *l = list;
779 883 markom 
    cucdebug (1, "%-4s cnt %3i ninsn %3i size %8.1f osize %8.1f cmovs %3i @",
780 
           cuc_insn_name (&f->INSN(list->ref)), list->cnt, list->ninsn,
781 
           list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size, list->osize, list->cmovs);
782 
    while (l) {
783 
      cucdebug (1, "%c%x,", l->cmatch ? '.' : '!', l->ref);
784 
      l = l->from;
785 
    }
786 
    cucdebug (1, "\n");
787 
  }
788 
 
789 
  /* Calculate estimated timings */
790 
  for (b = 0; b < f->num_bb; b++) {
791 
    cnt = 0;
792 
    for (list = main_list; list; list = list->next)
793 
      if (!list->dead && REF_BB(list->ref) == b) cnt++;
794 
 
795 
    f->bb[b].ntim = cnt;
796 
    if (!cnt) {
797 
      f->bb[b].tim = NULL;
798 
      continue;
799 
    }
800 
    assert (f->bb[b].tim = (cuc_timings *)malloc (sizeof (cuc_timings) * cnt));
801 
 
802 
    cnt = 0;
803 
    for (list = main_list; list; list = list->next) if (!list->dead && REF_BB(list->ref) == b) {
804 897 markom 
      cuc_shared_list *l = list;
805 883 markom 
      f->bb[b].tim[cnt].b = b;
806 
      f->bb[b].tim[cnt].preroll = f->bb[b].tim[cnt].unroll = 1;
807 
      f->bb[b].tim[cnt].nshared = list->ninsn;
808 897 markom 
      assert (f->bb[b].tim[cnt].shared = (cuc_shared_item *)
809 
            malloc (sizeof(cuc_shared_item) * list->ninsn));
810 
      for (i =  0; i < list->ninsn; i++, l = l->from) {
811 
        f->bb[b].tim[cnt].shared[i].ref = l->ref;
812 
        f->bb[b].tim[cnt].shared[i].cmatch = l->cmatch;
813 
      }
814 883 markom 
      f->bb[b].tim[cnt].new_time = timings.new_time + f->bb[b].cnt * (list->cnt - 1);
815 897 markom 
      f->bb[b].tim[cnt].size = timings.size +
816 
             list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size - list->osize;
817 883 markom 
      cnt++;
818 
    }
819 
  }
820 
}
821 
 
822 
/* Recursive function for searching through instruction graph */
823 897 markom 
static void search_csm (int iter, cuc_func *f, cuc_shared_list *list)
824 883 markom 
{
825 
  int b, i, j, i1;
826 897 markom 
  cuc_shared_list *l;
827 883 markom 
  b = REF_BB(list->ref);
828 
  i = REF_I(list->ref);
829 
 
830 
  for (j = 0; j < MAX_OPERANDS; j++) if (f->bb[b].insn[i].opt[j] & OPT_REF) {
831 
    int t = f->bb[b].insn[i].op[j];
832 
    int cnt = 0, cntc = 0;
833 
    double size = 0., sizec = 0.;
834 
 
835 
    /* Mark neighbours */
836 
    for (i1 = 0; i1 < f->bb[b].ninsn; i1++) {
837 
      if (iteration[i1] == iter && f->bb[b].insn[i1].opt[j] & OPT_REF) {
838 
        int t2 = f->bb[b].insn[i1].op[j];
839 
        if (f->INSN(t).index == f->INSN(t2).index && f->INSN(t2).opt[j] & OPT_REF) {
840 
          int j2;
841 
          int ok = 1;
842 
          iteration[REF_I(t2)] = iter + 1;
843 
          for (j2 = 0; j2 < MAX_OPERANDS; j2++) if (!(f->bb[b].insn[i1].opt[j2] & OPT_REF))
844 
            if (f->bb[b].insn[i1].opt[j2] != f->bb[b].insn[i].opt[j2]
845 
             || f->bb[b].insn[i1].op[j2] != f->bb[b].insn[i].opt[j2]) {
846 
              ok = 0;
847 
              break;
848 
            }
849 
          if (ok) {
850 
            cntc++;
851 
            sizec = sizec + insn_size (&f->bb[b].insn[i1]);
852 
          } else {
853 
            cnt++;
854 
            size = size + insn_size (&f->bb[b].insn[i1]);
855 
          }
856 
        }
857 
      }
858 
    }
859 
 
860 
    if (cntc > 1) {
861 897 markom 
      assert (l = (cuc_shared_list *)malloc (sizeof (cuc_shared_list)));
862 883 markom 
      l->next = main_list;
863 
      main_list = l;
864 
      l->from = list;
865 
      l->ref = t;
866 
      l->cnt = cnt;
867 
      l->cmatch = 1;
868 
      l->cmovs = list->cmovs + count_cmovs (&f->bb[b].insn[i], 1) - 1;
869 
      l->size = list->size + ii_size (f->bb[b].insn[i].index, 1);
870 
      l->osize = sizec;
871 
      search_csm (iter + 1, f, l);
872 
    }
873 
    if (cnt > 1) {
874 897 markom 
      assert (l = (cuc_shared_list *)malloc (sizeof (cuc_shared_list)));
875 883 markom 
      l->next = main_list;
876 
      main_list = l;
877 
      l->from = list;
878 
      l->ref = t;
879 
      l->cnt = cnt + cntc;
880 
      l->cmatch = 0;
881 
      l->osize = size + sizec;
882 
      l->cmovs = list->cmovs + count_cmovs (&f->bb[b].insn[i], 0) - 1;
883 
      l->size = list->size + ii_size (f->bb[b].insn[i].index, 0);
884 
      search_csm (iter + 1, f, l);
885 
    }
886 
 
887 
    /* Unmark them back */
888 
    for (i1 = 0; i1 < f->bb[b].ninsn; i1++) if (iteration[i1] > iter) iteration[i1] = -1;
889 
  }
890 
}
891 
 
892 897 markom 
/* Displays shared instructions */
893 
void print_shared (cuc_func *rf, cuc_shared_item *shared, int nshared)
894 
{
895 
  int i, first = 1;
896 
  for (i = 0; i < nshared; i++) {
897 
    printf ("%s%s%s", first ? "" : "-", cuc_insn_name (rf->INSN(shared[i].ref).index),
898 
                    shared[i].cmatch ? "!" : "");
899 
    first = 0;
900 
  }
901 
}
902 
 
903 
/* Common subexpression matching -- resource sharing, generation pass
904 
 
905 
   Situation here is much simpler than with analysis -- we know the instruction sequence
906 
   we are going to share, but we are going to do this on whole function, not just one BB.
907 
   We can find sequence in reference function, as pointed from "shared" */
908 
void csm_gen (cuc_func *f, cuc_func *rf, cuc_shared_item *shared, int nshared)
909 
{
910 
  int b, i, j, cnt = 0;
911 
#warning   some code here (2)
912 
  printf ("Replacing: ");
913 
  print_shared (rf, shared, nshared);
914 
 
915 
  for (b = 0; b < f->num_bb; b++)
916 
    for (i = 0; i < f->bb[b].ninsn; i++) {
917 
    }
918 
 
919 
  printf ("\nFound %i matches.\n", cnt);
920 
}
921 
 

powered by: WebSVN 2.1.0

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