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

Subversion Repositories or1k

[/] [or1k/] [tags/] [nog_patch_47/] [or1ksim/] [cuc/] [insn.c] - Blame information for rev 929

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 926 markom 
{"lb",  0, "always @(posedge clk)"},
43 
{"lh",  0, "always @(posedge clk)"},
44 
{"lw",  0, "always @(posedge clk)"},
45 879 markom 
{"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 905 markom 
{"sfge", 0, "assign \1 = \2 >= \3;"},
54 879 markom 
{"sfgt", 0, "assign \1 = \2 > \3;"},
55 
{"bf",  0, ""},
56 
 
57 
{"lrbb", 0,"always @(posedge clk or posedge rst)"},
58 
{"cmov", 0,"assign \1 = \4 ? \2 : \3;"},
59 926 markom 
{"reg", 0, "always @(posedge clk)"},
60 879 markom 
 
61 917 markom 
{"nop", 0, NULL},
62 
{"call", 0, "/* function call */"}};
63 879 markom 
 
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 925 markom 
        case OPT_BB: printf ("BB "); print_bb_num (insn[i].op[j]); printf (", "); break;
103 897 markom 
        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 905 markom 
    if (ii->opt[3] & OPT_CONST) {
252 
      change_insn_type (ii, II_ADD);
253 
      if (ii->op[3]) {
254 
        ii->op[2] = 0; ii->opt[2] = OPT_CONST;
255 
      } else {
256 
        ii->op[1] = 0; ii->opt[1] = OPT_CONST;
257 
      }
258 
      ii->opt[3] = OPT_NONE;
259 
      return 1;
260 
    }
261 927 markom 
    if (ii->type & IT_COND) {
262 
      if (ii->opt[1] & OPT_CONST && ii->opt[2] & OPT_CONST) {
263 
        if (ii->op[1] && !ii->op[2]) {
264 
          change_insn_type (ii, II_ADD);
265 
          ii->op[1] = ii->op[3]; ii->opt[1] = ii->opt[3];
266 
          ii->op[2] = 0; ii->opt[2] = OPT_CONST;
267 
          ii->opt[3] = OPT_NONE;
268 
          return 1;
269 
        }
270 
        if (ii->op[1] && ii->op[2]) {
271 
          change_insn_type (ii, II_ADD);
272 
          ii->op[1] = 1; ii->opt[1] = OPT_CONST;
273 
          ii->op[2] = 0; ii->opt[2] = OPT_CONST;
274 
          ii->opt[3] = OPT_NONE;
275 
          return 1;
276 
        }
277 
        if (!ii->op[1] && !ii->op[2]) {
278 
          change_insn_type (ii, II_ADD);
279 
          ii->op[1] = 0; ii->opt[1] = OPT_CONST;
280 
          ii->op[2] = 0; ii->opt[2] = OPT_CONST;
281 
          ii->opt[3] = OPT_NONE;
282 
          return 0;
283 
        }
284 
      }
285 
    }
286 897 markom 
  }
287 
  return 0;
288 
}
289 
 
290 902 markom 
/* First primary input */
291 
static unsigned long tmp_op, tmp_opt;
292 
 
293 
/* Recursive function that searches for primary inputs;
294 
   returns 0 if cmov can be replaced by add */
295 
static int cmov_needed (cuc_func *f, int ref)
296 
{
297 
  cuc_insn *ii = &f->INSN(ref);
298 
  int j;
299 
 
300 903 markom 
  cucdebug (4, " %x", ref);
301 902 markom 
  /* mark visited, if already marked, we have a loop, ignore */
302 
  if (ii->tmp) return 0;
303 
  ii->tmp = 1;
304 
 
305 
  /* handle normal movs separately */
306 917 markom 
  if (ii->index == II_ADD && !(ii->type & IT_VOLATILE)
307 902 markom 
    && ii->opt[2] == OPT_CONST && ii->op[2] == 0) {
308 
    if (ii->opt[1] == OPT_REF) {
309 
      if (cmov_needed (f, ii->op[1])) {
310 
        ii->tmp = 0;
311 
        return 1;
312 
      }
313 
    } else {
314 
      if (tmp_opt == OPT_NONE) {
315 
        tmp_op = ii->op[1];
316 
        tmp_opt = ii->opt[1];
317 
      } else if (tmp_opt != ii->opt[1] || tmp_op != ii->op[1]) {
318 
        ii->tmp = 0;
319 
        return 1;
320 
      }
321 
    }
322 
    ii->tmp = 0;
323 
    return 0;
324 
  }
325 
 
326 
  /* Is this instruction CMOV? no => add to primary inputs */
327 
  if (ii->index != II_CMOV || ii->type & IT_VOLATILE)
328 
    if (tmp_opt == OPT_NONE) {
329 
      tmp_op = ref;
330 
      tmp_opt = OPT_REF;
331 
      ii->tmp = 0;
332 
      return 0;
333 
    } else if (tmp_opt != OPT_REF || tmp_op != ref) {
334 
      ii->tmp = 0;
335 
      return 1;
336 917 markom 
    } else {
337 
      ii->tmp = 0;
338 
      return 0;
339 902 markom 
    }
340 
 
341 
  for (j = 1; j < 3; j++) {
342 903 markom 
    cucdebug (4, "(%x:%i)", ref, j);
343 902 markom 
    if (ii->opt[j] == OPT_REF) {
344 
      if (cmov_needed (f, ii->op[j])) {
345 
        ii->tmp = 0;
346 
        return 1;
347 
      }
348 
    } else {
349 
      if (tmp_opt == OPT_NONE) {
350 
        tmp_op = ii->op[j];
351 
        tmp_opt = ii->opt[j];
352 
      } else if (tmp_opt != ii->opt[j] || tmp_op != ii->op[j]) {
353 
        ii->tmp = 0;
354 
        return 1;
355 
      }
356 
    }
357 
  }
358 
 
359 
  ii->tmp = 0;
360 
  return 0;
361 
}
362 
 
363 
/* Search and optimize complex cmov assignments */
364 
void optimize_cmovs (cuc_func *f)
365 
{
366 
  int b, i, j;
367 
 
368 
  /* Mark all instructions unvisited */
369 
  for (b = 0; b < f->num_bb; b++) if (!(f->bb[b].type & BB_DEAD))
370 
    for (i = 0; i < f->bb[b].ninsn; i++) f->bb[b].insn[i].tmp = 0;
371 
 
372 
  for (b = 0; b < f->num_bb; b++) if (!(f->bb[b].type & BB_DEAD)) {
373 
    for (i = 0; i < f->bb[b].ninsn; i++) {
374 
      cuc_insn *ii = &f->bb[b].insn[i];
375 
      if (ii->index == II_CMOV && !(ii->type & IT_VOLATILE)) {
376 
        tmp_opt = OPT_NONE;
377 903 markom 
        cucdebug (4, "\n");
378 902 markom 
        if (!cmov_needed (f, REF(b, i))) {
379 
          assert (tmp_opt != OPT_NONE);
380 
          change_insn_type (ii, II_ADD);
381 
          ii->op[1] = tmp_op; ii->opt[1] = tmp_opt;
382 
          ii->op[2] = 0; ii->opt[2] = OPT_CONST;
383 
          ii->opt[3] = OPT_NONE;
384 
        }
385 
      }
386 
    }
387 
  }
388 
}
389 
 
390 897 markom 
/* Optimizes dataflow tree */
391 
void optimize_tree (cuc_func *f)
392 
{
393 
  int b, i, j;
394 
  int modified;
395 
 
396 
  do {
397 
    modified = 0;
398 
    for (b = 0; b < f->num_bb; b++) if (!(f->bb[b].type & BB_DEAD)) {
399 
      for (i = 0; i < f->bb[b].ninsn; i++) {
400 
        cuc_insn *ii = &f->bb[b].insn[i];
401 
        /* We tend to have the third parameter const if instruction is cumutative */
402 929 markom 
        if ((ii->opt[1] & OPT_CONST) && !(ii->opt[2] & OPT_CONST)) {
403 
          int cond = ii->index == II_SFEQ || ii->index == II_SFNE
404 
                  || ii->index == II_SFLT || ii->index == II_SFLE
405 
                  || ii->index == II_SFGT || ii->index == II_SFGE;
406 
          if (known[ii->index].comutative || cond) {
407 
            unsigned long t = ii->opt[1];
408 
            ii->opt[1] = ii->opt[2];
409 
            ii->opt[2] = t;
410 
            t = ii->op[1];
411 
            ii->op[1] = ii->op[2];
412 
            ii->op[2] = t;
413 
            modified = 1; cucdebug (2, "%08x:<>\n", REF(b, i));
414 
            if (cond) {
415 
              if (ii->index == II_SFEQ) ii->index = II_SFNE;
416 
              else if (ii->index == II_SFNE) ii->index = II_SFEQ;
417 
              else if (ii->index == II_SFLE) ii->index = II_SFGT;
418 
              else if (ii->index == II_SFLT) ii->index = II_SFGE;
419 
              else if (ii->index == II_SFGE) ii->index = II_SFLT;
420 
              else if (ii->index == II_SFGT) ii->index = II_SFLE;
421 
              else assert (0);
422 
            }
423 
          }
424 897 markom 
        }
425 
 
426 
        /* Try to do the promotion */
427 
        /* We have two consecutive expressions, containing constants,
428 
         * if previous is a simple expression we can handle it simply: */
429 
        for (j = 0; j < MAX_OPERANDS; j++)
430 
          if (ii->opt[j] & OPT_REF) {
431 
            cuc_insn *t = &f->INSN(ii->op[j]);
432 
            if (f->INSN(ii->op[j]).index == II_ADD
433 
             && f->INSN(ii->op[j]).opt[2] & OPT_CONST
434 
             && f->INSN(ii->op[j]).op[2] == 0
435 
             && !(ii->type & IT_MEMORY && t->type & IT_MEMADD)
436 
             && !(ii->type & IT_BRANCH) && !(t->type & IT_COND)) {
437 
            /* do not promote through add-mem, and branches */
438 
              modified = 1; cucdebug (2, "%8x:promote%i %8x %8x\n", REF (b, i), j, ii->op[j], t->op[1]);
439 
              ii->op[j] = t->op[1]; ii->opt[j] = t->opt[1];
440 
            }
441 
          }
442 
 
443 
        /* In case of x = cmov x, y; or x = cmov y, x; we have
444 
           asynchroneous loop -> remove it */
445 
        if (ii->index == II_CMOV) {
446 
          int f = 0;
447 
          if ((ii->opt[1] & OPT_REF) && ii->op[1] == REF (b, i)) f = 1;
448 
          if ((ii->opt[2] & OPT_REF) && ii->op[2] == REF (b, i)) f = 2;
449 
          if (ii->opt[1] == ii->opt[2] && ii->op[1] == ii->op[2]) f = 2;
450 
          if (f) {
451 
            change_insn_type (ii, II_ADD);
452 
            cucdebug (2, "%8x:cmov     %i\n", REF(b, i), f);
453 
            ii->opt[f] = OPT_CONST;
454 
            ii->op[f] = 0;
455 
            ii->opt[3] = OPT_NONE;
456 
            modified = 1;
457 
            continue;
458 
          }
459 
        }
460 
 
461 
        /* Do nothing to volatile instructions */
462 
        if (ii->type & IT_VOLATILE) continue;
463 
 
464 
        /* Check whether we can simplify the instruction */
465 
        if (apply_edge_condition (ii)) {
466 
          modified = 1;
467 
          continue;
468 
        }
469 
        /* We cannot do anything more if at least one is not constant */
470 
        if (!(ii->opt[2] & OPT_CONST)) continue;
471 
 
472 
        if (ii->opt[1] & OPT_CONST) { /* We have constant expression */
473 
          unsigned long value;
474 
          int ok = 1;
475 
          /* Was constant expression already? */
476 
          if (ii->index == II_ADD && !ii->op[2]) continue;
477 
 
478 
          if (ii->index == II_ADD) value = ii->op[1] + ii->op[2];
479 
          else if (ii->index == II_SUB) value = ii->op[1] - ii->op[2];
480 
          else if (ii->index == II_SLL) value = ii->op[1] << ii->op[2];
481 
          else if (ii->index == II_SRL) value = ii->op[1] >> ii->op[2];
482 
          else if (ii->index == II_MUL) value = ii->op[1] * ii->op[2];
483 
          else if (ii->index == II_OR) value = ii->op[1] | ii->op[2];
484 
          else if (ii->index == II_XOR) value = ii->op[1] ^ ii->op[2];
485 
          else if (ii->index == II_AND) value = ii->op[1] & ii->op[2];
486 
          else ok = 0;
487 
          if (ok) {
488 
            change_insn_type (ii, II_ADD);
489 
            ii->op[0] = -1; ii->opt[0] = OPT_REGISTER | OPT_DEST;
490 
            ii->op[1] = value; ii->opt[1] = OPT_CONST;
491 
            ii->op[2] = 0; ii->opt[2] = OPT_CONST;
492 
            modified = 1; cucdebug (2, "%8x:const\n", REF (b, i));
493 
          }
494 
        } else if (ii->opt[1] & OPT_REF) {
495 
          cuc_insn *prev = &f->INSN(ii->op[1]);
496 
          /* Is this just a link? */
497 
          if (ii->index == II_ADD
498 
           && !(ii->type & IT_MEMADD) && ii->op[2] == 0) {
499 
            int b1, i1, j1;
500 
            cucdebug (2, "%8x:link      %8x: ", REF(b, i), ii->op[1]);
501 
            for (b1 = 0; b1 < f->num_bb; b1++) if (!(f->bb[b1].type & BB_DEAD))
502 
              for (i1 = 0; i1 < f->bb[b1].ninsn; i1++)
503 
                for (j1 = 0; j1 < MAX_OPERANDS; j1++)
504 
                  if ((f->bb[b1].insn[i1].opt[j1] & OPT_REF)
505 
                   && f->bb[b1].insn[i1].op[j1] == REF(b, i)) {
506 
                    cucdebug (2, "%x ", REF (b1, i1));
507 
                    f->bb[b1].insn[i1].op[j1] = ii->op[1];
508 
                  }
509 
            cucdebug (2, "\n");
510 
            change_insn_type (ii, II_NOP);
511 
          } else if (prev->opt[2] & OPT_CONST) {
512 
            /* Handle some common cases */
513 
            /* add - add joining */
514 
            if (ii->index == II_ADD && prev->index == II_ADD) {
515 
              ii->op[1] = prev->op[1]; ii->opt[1] = prev->opt[1];
516 
              ii->op[2] += prev->op[2];
517 
              modified = 1; cucdebug (2, "%8x: add-add\n", REF(b, i));
518 
            } else /* add - sub joining */
519 
            if (ii->index == II_ADD && prev->index == II_SUB) {
520 
              change_insn_type (&insn[i], II_SUB);
521 
              ii->op[1] = prev->op[1]; ii->opt[1] = prev->opt[1];
522 
              ii->op[2] += prev->op[2];
523 
              modified = 1; cucdebug (2, "%8x: add-sub\n", REF(b, i));
524 
            } else /* sub - add joining */
525 
            if (ii->index == II_SUB && prev->index == II_ADD) {
526 
              ii->op[1] = prev->op[1]; ii->opt[1] = prev->opt[1];
527 
              ii->op[2] += prev->op[2];
528 
              modified = 1; cucdebug (2, "%8x: sub-add\n", REF(b, i));
529 929 markom 
            } else /* add - sfxx joining */
530 
            if (prev->index == II_ADD && (
531 
                ii->index == II_SFEQ || ii->index == II_SFNE
532 
             || ii->index == II_SFLT || ii->index == II_SFLE
533 
             || ii->index == II_SFGT || ii->index == II_SFGE)) {
534 
              if (ii->opt[2] & OPT_CONST) {
535 
                ii->op[1] = prev->op[1]; ii->opt[1] = prev->opt[1];
536 
                ii->op[2] -= prev->op[2];
537 
                modified = 1; cucdebug (2, "%8x: add-sfxx\n", REF(b, i));
538 
              }
539 
            } else /* sub - sfxx joining */
540 
            if (prev->index == II_SUB && (
541 
                ii->index == II_SFEQ || ii->index == II_SFNE
542 
             || ii->index == II_SFLT || ii->index == II_SFLE
543 
             || ii->index == II_SFGT || ii->index == II_SFGE)) {
544 
              if (ii->opt[2] & OPT_CONST) {
545 
                ii->op[1] = prev->op[1]; ii->opt[1] = prev->opt[1];
546 
                ii->op[2] += prev->op[2];
547 
                modified = 1; cucdebug (2, "%8x: sub-sfxx\n", REF(b, i));
548 
              }
549 897 markom 
            }
550 
          }
551 
        }
552 
      }
553 
    }
554 
  } while (modified);
555 
}
556 
 
557 
/* Remove nop instructions */
558 
void remove_nops (cuc_func *f)
559 
{
560 
  int b;
561 
  for (b = 0; b < f->num_bb; b++) {
562 
    int c, d = 0, i, j;
563 
    cuc_insn *insn = f->bb[b].insn;
564 
    for (i = 0; i < f->bb[b].ninsn; i++)
565 
      if (insn[i].index != II_NOP) {
566 
        reloc [i] = d;
567 
        insn[d++] = insn[i];
568 
      } else {
569 
        reloc[i] = d; /* For jumps only */
570 
      }
571 
    f->bb[b].ninsn = d;
572 
 
573 
    /* Relocate references from all basic blocks */
574 
    for (c = 0; c < f->num_bb; c++)
575 
      for (i = 0; i < f->bb[c].ninsn; i++) {
576 
        dep_list *d = f->bb[c].insn[i].dep;
577 
        for (j = 0; j < MAX_OPERANDS; j++)
578 
          if ((f->bb[c].insn[i].opt[j] & OPT_REF)
579 
            && REF_BB(f->bb[c].insn[i].op[j]) == b)
580 
            f->bb[c].insn[i].op[j] = REF (b, reloc[REF_I (f->bb[c].insn[i].op[j])]);
581 
 
582 
        while (d) {
583 
          if (REF_BB(d->ref) == b) d->ref = REF (b, reloc[REF_I (d->ref)]);
584 
          d = d->next;
585 
        }
586 
      }
587 
  }
588 
}
589 
 
590 
/* Remove unused assignments */
591 
void remove_dead (cuc_func *f)
592 
{
593 
  int b, i, j;
594 
  for (b = 0; b < f->num_bb; b++)
595 
    for (i = 0; i < f->bb[b].ninsn; i++)
596 
      if (!(f->bb[b].insn[i].type & (IT_VOLATILE | IT_OUTPUT)))
597 
        f->bb[b].insn[i].type |= IT_UNUSED;
598 
 
599 
  for (b = 0; b < f->num_bb; b++) {
600 
    for (i = 0; i < f->bb[b].ninsn; i++)
601 
      for (j = 0; j < MAX_OPERANDS; j++)
602 
        if (f->bb[b].insn[i].opt[j] & OPT_REF) {
603 
          f->INSN(f->bb[b].insn[i].op[j]).type &= ~IT_UNUSED;
604 
        }
605 
  }
606 
 
607 
  for (b = 0; b < f->num_bb; b++)
608 
    for (i = 0; i < f->bb[b].ninsn; i++)
609 
      if (f->bb[b].insn[i].type & IT_UNUSED) {
610 
        change_insn_type (&f->bb[b].insn[i], II_NOP);
611 
      }
612 
 
613 
  remove_nops (f);
614 
}
615 
 
616 
/* Removes trivial register assignments */
617 
void remove_trivial_regs (cuc_func *f)
618 
{
619 
  int b, i;
620 
  for (i = 0; i < MAX_REGS; i++) f->saved_regs[i] = call_saved[i];
621 
 
622 
  for (b = 0; b < f->num_bb; b++) {
623 
    cuc_insn *insn = f->bb[b].insn;
624 
    for (i = 0; i < f->bb[b].ninsn; i++) {
625 
      if (insn[i].index == II_ADD
626 
        && insn[i].opt[0] & OPT_REGISTER
627 
        && insn[i].opt[1] & OPT_REGISTER && insn[i].op[0] == insn[i].op[1]
628 
        && insn[i].opt[2] & OPT_CONST && insn[i].op[2] == 0) {
629 
          if (insn[i].type & IT_OUTPUT) f->saved_regs[insn[i].op[0]] = 1;
630 
          change_insn_type (&insn[i], II_NOP);
631 
        }
632 
    }
633 
  }
634 
  if (cuc_debug >= 2) {
635 
    printf ("saved regs ");
636 
    for (i = 0; i < MAX_REGS; i++) printf ("%i:%i ", i, f->saved_regs[i]);
637 
    printf ("\n");
638 
  }
639 
  remove_nops (f);
640 
}
641 
 
642 
/* Determine inputs and outputs */
643 
void set_io (cuc_func *f)
644 
{
645 
  int b, i, j;
646 
  /* Determine register usage */
647 
  for (i = 0; i < MAX_REGS; i++) {
648 
    f->lur[i] = -1;
649 
    f->used_regs[i] = 0;
650 
  }
651 902 markom 
  if (cuc_debug > 5) print_cuc_bb (f, "SET_IO");
652 897 markom 
  for (b = 0; b < f->num_bb; b++) {
653 
    for (i = 0; i < f->bb[b].ninsn; i++)
654 
      for (j = 0; j < MAX_OPERANDS; j++)
655 
        if (f->bb[b].insn[i].opt[j] & OPT_REGISTER && f->bb[b].insn[i].op[j] >= 0)
656 
          if (f->bb[b].insn[i].opt[j] & OPT_DEST) f->lur[f->bb[b].insn[i].op[j]] = REF (b, i);
657 
          else f->used_regs[f->bb[b].insn[i].op[j]] = 1;
658 
  }
659 
}
660 
 
661 
/* relocate all accesses inside of BB b to back/fwd */
662 
static void relocate_bb (cuc_bb *bb, int b, int back, int fwd)
663 
{
664 
  int i, j;
665 
  for (i = 0; i < bb->ninsn; i++)
666 
    for (j = 0; j < MAX_OPERANDS; j++)
667 
      if (bb->insn[i].opt[j] & OPT_REF
668 
       && REF_BB (bb->insn[i].op[j]) == b) {
669 
        int t = REF_I (bb->insn[i].op[j]);
670 
        if (t < i) bb->insn[i].op[j] = REF (back, t);
671 
        else bb->insn[i].op[j] = REF (fwd, t);
672 
      }
673 
}
674 
 
675 
/* Latch outputs in loops */
676 
void add_latches (cuc_func *f)
677 
{
678 
  int b, i, j;
679 
 
680 
  //print_cuc_bb (f, "ADD_LATCHES a");
681 
  /* Cuts the tree and marks registers */
682 
  mark_cut (f);
683 
 
684 
  /* Split BBs with more than one group */
685 
  for (b = 0; b < f->num_bb; b++) expand_bb (f, b);
686 
  remove_nops (f);
687 
  //print_cuc_bb (f, "ADD_LATCHES 0");
688 
 
689 
  /* Convert accesses in BB_INLOOP type block to latched */
690 
  for (b = 0; b < f->num_bb; b++) {
691 
    int j;
692 
    for (i = 0; i < f->bb[b].ninsn; i++)
693 
      for (j = 0; j < MAX_OPERANDS; j++) if (f->bb[b].insn[i].opt[j] == OPT_REF) {
694 
        int t = f->bb[b].insn[i].op[j];
695 
        /* If we are pointing to a INLOOP block from outside, or forward
696 
           (= previous loop iteration) we must register that data */
697 
        if ((f->bb[REF_BB(t)].type & BB_INLOOP || config.cuc.no_multicycle)
698 
         && !(f->INSN(t).type & (IT_BRANCH | IT_COND))
699 
         && (REF_BB(t) != b || REF_I(t) >= i)) {
700 
          f->INSN(t).type |= IT_LATCHED;
701 
        }
702 
      }
703 
  }
704 
  //print_cuc_bb (f, "ADD_LATCHES 1");
705 
 
706 
  /* Add latches at the end of blocks as needed */
707 
  for (b = 0; b < f->num_bb; b++) {
708 
    int nreg = 0;
709 
    cuc_insn *insn;
710 
    for (i = 0; i < f->bb[b].ninsn; i++)
711 
      if (f->bb[b].insn[i].type & IT_LATCHED) nreg++;
712 
    if (nreg) {
713 
      insn = (cuc_insn *) malloc (sizeof (cuc_insn) * (f->bb[b].ninsn + nreg));
714 
      j = 0;
715 
      for (i = 0; i < f->bb[b].ninsn; i++) {
716 
        insn[i] = f->bb[b].insn[i];
717 
        if (insn[i].type & IT_LATCHED) {
718 
          cuc_insn *ii = &insn[f->bb[b].ninsn + j++];
719 
          change_insn_type (ii, II_REG);
720 
          ii->op[0] = -1; ii->opt[0] = OPT_DEST | OPT_REGISTER;
721 
          ii->op[1] = REF (b, i); ii->opt[1] = OPT_REF;
722 
          ii->opt[2] = ii->opt[3] = OPT_NONE;
723 
          ii->dep = NULL;
724 
          ii->type = IT_VOLATILE;
725 
          sprintf (ii->disasm, "reg %i_%i", b, i);
726 
        }
727 
      }
728 
      f->bb[b].ninsn += nreg;
729 
      free (f->bb[b].insn);
730 
      f->bb[b].insn = insn;
731 
    }
732 
  }
733 
  //print_cuc_bb (f, "ADD_LATCHES 2");
734 
 
735 
  /* Repair references */
736 
  for (b = 0; b < f->num_bb; b++)
737 
    for (i = 0; i < f->bb[b].ninsn; i++)
738 
      for (j = 0; j < MAX_OPERANDS; j++)
739 
        /* If destination instruction is latched, use register instead */
740 
        if (f->bb[b].insn[i].opt[j] == OPT_REF
741 
         && f->INSN(f->bb[b].insn[i].op[j]).type & IT_LATCHED) {
742 
          int b1, i1;
743 
          b1 = REF_BB (f->bb[b].insn[i].op[j]);
744 
          //cucdebug (2, "%i.%i.%i %x\n", b, i, j, f->bb[b].insn[i].op[j]);
745 
          if (b1 != b || REF_I(f->bb[b].insn[i].op[j]) >= i) {
746 
            for (i1 = f->bb[b1].ninsn - 1; i1 >= 0; i1--) {
747 
              assert (f->bb[b1].insn[i1].index == II_REG);
748 
              if (f->bb[b1].insn[i1].op[1] == f->bb[b].insn[i].op[j]) {
749 
                f->bb[b].insn[i].op[j] = REF (b1, i1);
750 
                break;
751 
              }
752 
            }
753 
          }
754 
        }
755 
}
756 
 
757 883 markom 
/* CSE -- common subexpression elimination */
758 
void cse (cuc_func *f)
759 
{
760 
  int b, i, j, b1, i1, b2, i2, j2;
761 
  for (b1 = 0; b1 < f->num_bb; b1++)
762 
    for (i1 = 0; i1 < f->bb[b1].ninsn; i1++)
763 
      for (b2 = 0; b2 < f->num_bb; b2++)
764 
        for (i2 = 0; i2 < f->bb[b2].ninsn; i2++) {
765 
          cuc_insn *ii1 = &f->bb[b1].insn[i1];
766 
          cuc_insn *ii2 = &f->bb[b2].insn[i2];
767 
 
768 
          /* Do we have an exact match? */
769 
          if (ii1->index == ii2->index) continue;
770 
          if (ii1->type & IT_VOLATILE) continue;
771 
 
772 
          if (ii1->op[1] != ii2->op[1] || ii1->opt[1] != ii2->opt[1]) continue;
773 
          if (ii1->op[2] != ii2->op[2] || ii1->opt[2] != ii2->opt[2]) continue;
774 
          if (ii1->opt[3] != ii2->opt[3]) continue;
775 
          if (ii1->opt[3] != OPT_NONE && ii1->op[3] != ii2->op[3]) continue;
776 
 
777 
          /* Check if we drive outputs? */
778 
          if ((ii1->opt[0] & OPT_REGISTER) && ii1->op[0] >= 0)
779 
            if ((ii2->opt[0] & OPT_REGISTER) && ii2->op[0] >= 0) continue;
780 
            else ii2->op[0] = ii1->op[0];
781 
 
782 
          /* remove duplicated instruction and relink the references */
783 
          change_insn_type (ii2, II_NOP);
784 
          for (b = 0; b < f->num_bb; b++)
785 
            for (i = 0; i < f->bb[b].ninsn; i++)
786 
              for (j = 0; j < MAX_OPERANDS; j++)
787 
                if (f->bb[b].insn[i].opt[j] & OPT_REF && f->bb[b].insn[i].op[j] == REF (b2, i2))
788 
                  f->bb[b].insn[i].op[j] = REF (b1, i1);
789 
        }
790 
}
791 
 
792 
static int count_cmovs (cuc_insn *ii, int match)
793 
{
794 
  int c = 0, j;
795 
  if (match & 2) {
796 
    for (j = 0; j < MAX_OPERANDS; j++)
797 
      if (ii->opt[j] & OPT_DEST) c++;
798 
  }
799 
  if (match & 1) {
800 
    for (j = 0; j < MAX_OPERANDS; j++)
801 
      if (!(ii->opt[j] & OPT_DEST) && ii->opt[j] & OPT_REF) c++;
802 
  } else {
803 
    for (j = 0; j < MAX_OPERANDS; j++)
804 
      if (!(ii->opt[j] & OPT_DEST) && ii->opt[j] != OPT_NONE) c++;
805 
  }
806 
  return c;
807 
}
808 
 
809 897 markom 
static void search_csm (int iter, cuc_func *f, cuc_shared_list *list);
810 
static cuc_shared_list *main_list;
811 883 markom 
static int *iteration;
812 
 
813 897 markom 
/* CSM -- common subexpression matching -- resource sharing
814 
   We try to match tree of instruction inside a BB with as many
815 
   matches as possible. All possibilities are collected and
816 
   options, making situation worse are removed */
817 883 markom 
void csm (cuc_func *f)
818 
{
819 
  int b, i, j;
820 
  int cnt;
821 897 markom 
  cuc_shared_list *list;
822 883 markom 
  cuc_timings timings;
823 
 
824 
  analyse_timings (f, &timings);
825 
  main_list = NULL;
826 
  for (b = 0; b < f->num_bb; b++) {
827 
    assert (iteration = (int *)malloc (sizeof (int) * f->bb[b].ninsn));
828 
    for (i = 0; i < f->bb[b].ninsn; i++) {
829 
      int cnt = 0, cntc = 0;
830 
      double size = 0., sizec = 0.;
831 
      int j2 = 0;
832 
      for (j = 0; j < f->bb[b].ninsn; j++)
833 
        if (f->bb[b].insn[i].index == f->bb[b].insn[j].index) {
834 
          int ok = 1;
835 
          for (j2 = 0; j2 < MAX_OPERANDS; j2++) if (!(f->bb[b].insn[j].opt[j2] & OPT_REF))
836 
            if (f->bb[b].insn[j].opt[j2] != f->bb[b].insn[i].opt[j2]
837 
             || f->bb[b].insn[j].op[j2] != f->bb[b].insn[i].opt[j2]) {
838 
              ok = 0;
839 
              break;
840 
            }
841 
          if (ok) {
842 
            cntc++;
843 
            sizec = sizec + insn_size (&f->bb[b].insn[j]);
844 
          } else {
845 
            cnt++;
846 
            size = size + insn_size (&f->bb[b].insn[j]);
847 
          }
848 
          iteration[j] = 0;
849 
        } else iteration[j] = -1;
850 
      if (cntc > 1) {
851 897 markom 
        assert (list = (cuc_shared_list *)malloc (sizeof (cuc_shared_list)));
852 883 markom 
        list->next = main_list;
853 
        list->from = NULL;
854 
        list->ref = REF (b, i);
855 
        list->cnt = cnt;
856 
        list->cmatch = 1;
857 
        list->cmovs = count_cmovs (&f->bb[b].insn[i], 3);
858 
        list->osize = sizec;
859 
        list->size = ii_size (f->bb[b].insn[i].index, 1);
860 
        main_list = list;
861 
        search_csm (0, f, list);
862 
      }
863 
      if (cnt > 1) {
864 897 markom 
        assert (list = (cuc_shared_list *)malloc (sizeof (cuc_shared_list)));
865 883 markom 
        list->next = main_list;
866 
        list->from = NULL;
867 
        list->ref = REF (b, i);
868 
        list->cnt = cnt + cntc;
869 
        list->cmatch = 0;
870 
        list->cmovs = count_cmovs (&f->bb[b].insn[i], 2);
871 
        list->osize = size + sizec;
872 
        list->size = ii_size (f->bb[b].insn[i].index, 0);
873 
        main_list = list;
874 
        search_csm (0, f, list);
875 
      }
876 
    }
877 
    free (iteration);
878 
  }
879 
 
880 
  for (list = main_list; list; list = list->next) list->dead = 0;
881 
  cnt = 0;
882 
  for (list = main_list; list; list = list->next) if (!list->dead) cnt++;
883 
  cucdebug (1, "noptions = %i\n", cnt);
884 
 
885 
  /* Now we will check the real size of the 'improvements'; if the size
886 
     actually increases, we abandom the option */
887 
  for (list = main_list; list; list = list->next)
888 
    if (list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size >= list->osize) list->dead = 1;
889 
 
890 
  cnt = 0;
891 
  for (list = main_list; list; list = list->next) if (!list->dead) cnt++;
892 
  cucdebug (1, "noptions = %i\n", cnt);
893 
 
894 
  /* Count number of instructions grouped */
895 
  for (list = main_list; list; list = list->next) {
896 897 markom 
    cuc_shared_list *l = list;
897 883 markom 
    int c = 0;
898 
    while (l) {
899 
      c++;
900 
      if (f->INSN(l->ref).type & (IT_VOLATILE | IT_MEMORY | IT_MEMADD)) list->dead = 1;
901 
      l = l->from;
902 
    }
903 
    list->ninsn = c;
904 
  }
905 
 
906 
  cnt = 0;
907 
  for (list = main_list; list; list = list->next)
908 
    if (!list->dead) cnt++;
909 
  cucdebug (1, "noptions = %i\n", cnt);
910 
 
911 
#if 1
912 
  /* We can get a lot of options here, so we will delete duplicates */
913 
  for (list = main_list; list; list = list->next) if (!list->dead) {
914 897 markom 
    cuc_shared_list *l;
915 883 markom 
    for (l = list->next; l; l = l->next) if (!l->dead) {
916 
      int ok = 1;
917 897 markom 
      cuc_shared_list *t1 = list;
918 
      cuc_shared_list *t2 = l;
919 883 markom 
      while (ok && t1 && t2) {
920 
        if (f->INSN(t1->ref).index == f->INSN(t2->ref).index) {
921 
          /* If other operands are matching, we must check for them also */
922 
          if (t1->cmatch) {
923 
            int j;
924 
            for (j = 0; j < MAX_OPERANDS; j++)
925 
              if (!(f->INSN(t1->ref).opt[j] & OPT_REF) || !(f->INSN(t2->ref).opt[j] & OPT_REF)
926 
               || f->INSN(t1->ref).opt[j] != f->INSN(t2->ref).opt[j]
927 
               || f->INSN(t1->ref).op[j] != f->INSN(t2->ref).op[j]) {
928 
                ok = 0;
929 
                break;
930 
              }
931 
          }
932 
 
933 
          /* This option is duplicate, remove */
934 
          if (ok) t1->dead = 1;
935 
        }
936 
        t1 = t1->from;
937 
        t2 = t2->from;
938 
      }
939 
    }
940 
  }
941 
  cnt = 0;
942 
  for (list = main_list; list; list = list->next) if (!list->dead) cnt++;
943 
  cucdebug (1, "noptions = %i\n", cnt);
944 
#endif
945 
  /* Print out */
946 
  for (list = main_list; list; list = list->next) if (!list->dead) {
947 897 markom 
    cuc_shared_list *l = list;
948 883 markom 
    cucdebug (1, "%-4s cnt %3i ninsn %3i size %8.1f osize %8.1f cmovs %3i @",
949 
           cuc_insn_name (&f->INSN(list->ref)), list->cnt, list->ninsn,
950 
           list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size, list->osize, list->cmovs);
951 
    while (l) {
952 
      cucdebug (1, "%c%x,", l->cmatch ? '.' : '!', l->ref);
953 
      l = l->from;
954 
    }
955 
    cucdebug (1, "\n");
956 
  }
957 
 
958 
  /* Calculate estimated timings */
959 
  for (b = 0; b < f->num_bb; b++) {
960 
    cnt = 0;
961 
    for (list = main_list; list; list = list->next)
962 
      if (!list->dead && REF_BB(list->ref) == b) cnt++;
963 
 
964 
    f->bb[b].ntim = cnt;
965 
    if (!cnt) {
966 
      f->bb[b].tim = NULL;
967 
      continue;
968 
    }
969 
    assert (f->bb[b].tim = (cuc_timings *)malloc (sizeof (cuc_timings) * cnt));
970 
 
971 
    cnt = 0;
972 
    for (list = main_list; list; list = list->next) if (!list->dead && REF_BB(list->ref) == b) {
973 897 markom 
      cuc_shared_list *l = list;
974 883 markom 
      f->bb[b].tim[cnt].b = b;
975 
      f->bb[b].tim[cnt].preroll = f->bb[b].tim[cnt].unroll = 1;
976 
      f->bb[b].tim[cnt].nshared = list->ninsn;
977 897 markom 
      assert (f->bb[b].tim[cnt].shared = (cuc_shared_item *)
978 
            malloc (sizeof(cuc_shared_item) * list->ninsn));
979 
      for (i =  0; i < list->ninsn; i++, l = l->from) {
980 
        f->bb[b].tim[cnt].shared[i].ref = l->ref;
981 
        f->bb[b].tim[cnt].shared[i].cmatch = l->cmatch;
982 
      }
983 883 markom 
      f->bb[b].tim[cnt].new_time = timings.new_time + f->bb[b].cnt * (list->cnt - 1);
984 897 markom 
      f->bb[b].tim[cnt].size = timings.size +
985 
             list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size - list->osize;
986 883 markom 
      cnt++;
987 
    }
988 
  }
989 
}
990 
 
991 
/* Recursive function for searching through instruction graph */
992 897 markom 
static void search_csm (int iter, cuc_func *f, cuc_shared_list *list)
993 883 markom 
{
994 
  int b, i, j, i1;
995 897 markom 
  cuc_shared_list *l;
996 883 markom 
  b = REF_BB(list->ref);
997 
  i = REF_I(list->ref);
998 
 
999 
  for (j = 0; j < MAX_OPERANDS; j++) if (f->bb[b].insn[i].opt[j] & OPT_REF) {
1000 
    int t = f->bb[b].insn[i].op[j];
1001 
    int cnt = 0, cntc = 0;
1002 
    double size = 0., sizec = 0.;
1003 
 
1004 
    /* Mark neighbours */
1005 
    for (i1 = 0; i1 < f->bb[b].ninsn; i1++) {
1006 
      if (iteration[i1] == iter && f->bb[b].insn[i1].opt[j] & OPT_REF) {
1007 
        int t2 = f->bb[b].insn[i1].op[j];
1008 
        if (f->INSN(t).index == f->INSN(t2).index && f->INSN(t2).opt[j] & OPT_REF) {
1009 
          int j2;
1010 
          int ok = 1;
1011 
          iteration[REF_I(t2)] = iter + 1;
1012 
          for (j2 = 0; j2 < MAX_OPERANDS; j2++) if (!(f->bb[b].insn[i1].opt[j2] & OPT_REF))
1013 
            if (f->bb[b].insn[i1].opt[j2] != f->bb[b].insn[i].opt[j2]
1014 
             || f->bb[b].insn[i1].op[j2] != f->bb[b].insn[i].opt[j2]) {
1015 
              ok = 0;
1016 
              break;
1017 
            }
1018 
          if (ok) {
1019 
            cntc++;
1020 
            sizec = sizec + insn_size (&f->bb[b].insn[i1]);
1021 
          } else {
1022 
            cnt++;
1023 
            size = size + insn_size (&f->bb[b].insn[i1]);
1024 
          }
1025 
        }
1026 
      }
1027 
    }
1028 
 
1029 
    if (cntc > 1) {
1030 897 markom 
      assert (l = (cuc_shared_list *)malloc (sizeof (cuc_shared_list)));
1031 883 markom 
      l->next = main_list;
1032 
      main_list = l;
1033 
      l->from = list;
1034 
      l->ref = t;
1035 
      l->cnt = cnt;
1036 
      l->cmatch = 1;
1037 
      l->cmovs = list->cmovs + count_cmovs (&f->bb[b].insn[i], 1) - 1;
1038 
      l->size = list->size + ii_size (f->bb[b].insn[i].index, 1);
1039 
      l->osize = sizec;
1040 
      search_csm (iter + 1, f, l);
1041 
    }
1042 
    if (cnt > 1) {
1043 897 markom 
      assert (l = (cuc_shared_list *)malloc (sizeof (cuc_shared_list)));
1044 883 markom 
      l->next = main_list;
1045 
      main_list = l;
1046 
      l->from = list;
1047 
      l->ref = t;
1048 
      l->cnt = cnt + cntc;
1049 
      l->cmatch = 0;
1050 
      l->osize = size + sizec;
1051 
      l->cmovs = list->cmovs + count_cmovs (&f->bb[b].insn[i], 0) - 1;
1052 
      l->size = list->size + ii_size (f->bb[b].insn[i].index, 0);
1053 
      search_csm (iter + 1, f, l);
1054 
    }
1055 
 
1056 
    /* Unmark them back */
1057 
    for (i1 = 0; i1 < f->bb[b].ninsn; i1++) if (iteration[i1] > iter) iteration[i1] = -1;
1058 
  }
1059 
}
1060 
 
1061 897 markom 
/* Displays shared instructions */
1062 
void print_shared (cuc_func *rf, cuc_shared_item *shared, int nshared)
1063 
{
1064 
  int i, first = 1;
1065 
  for (i = 0; i < nshared; i++) {
1066 906 markom 
    printf ("%s%s%s", first ? "" : "-", cuc_insn_name (&rf->INSN(shared[i].ref)),
1067 897 markom 
                    shared[i].cmatch ? "!" : "");
1068 
    first = 0;
1069 
  }
1070 
}
1071 
 
1072 
/* Common subexpression matching -- resource sharing, generation pass
1073 
 
1074 
   Situation here is much simpler than with analysis -- we know the instruction sequence
1075 
   we are going to share, but we are going to do this on whole function, not just one BB.
1076 
   We can find sequence in reference function, as pointed from "shared" */
1077 
void csm_gen (cuc_func *f, cuc_func *rf, cuc_shared_item *shared, int nshared)
1078 
{
1079 
  int b, i, j, cnt = 0;
1080 
#warning   some code here (2)
1081 
  printf ("Replacing: ");
1082 
  print_shared (rf, shared, nshared);
1083 
 
1084 
  for (b = 0; b < f->num_bb; b++)
1085 
    for (i = 0; i < f->bb[b].ninsn; i++) {
1086 
    }
1087 
 
1088 
  printf ("\nFound %i matches.\n", cnt);
1089 
}
1090 
 

powered by: WebSVN 2.1.0

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