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

Subversion Repositories or1k

[/] [or1k/] [tags/] [nog_patch_61/] [or1ksim/] [cuc/] [insn.c] - Blame information for rev 930

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

powered by: WebSVN 2.1.0

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