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

Subversion Repositories or1k

[/] [or1k/] [tags/] [rel-0-3-0-rc1/] [or1ksim/] [cuc/] [insn.c] - Blame information for rev 1765

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 879 markom 
/* insn.c -- OpenRISC Custom Unit Compiler, instruction support
2 
 
3 1748 jeremybenn 
   Copyright (C) 2002 Marko Mlinar, markom@opencores.org
4 
   Copyright (C) 2008 Embecosm Limited
5 1308 phoenix 
 
6 1748 jeremybenn 
   Contributor Jeremy Bennett <jeremy.bennett@embecosm.com>
7 
 
8 
   This file is part of Or1ksim, the OpenRISC 1000 Architectural Simulator.
9 
 
10 
   This program is free software; you can redistribute it and/or modify it
11 
   under the terms of the GNU General Public License as published by the Free
12 
   Software Foundation; either version 3 of the License, or (at your option)
13 
   any later version.
14 
 
15 
   This program is distributed in the hope that it will be useful, but WITHOUT
16 
   ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 
   FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
18 
   more details.
19 
 
20 
   You should have received a copy of the GNU General Public License along
21 
   with this program.  If not, see <http://www.gnu.org/licenses/>.  */
22 
 
23 
/* This program is commented throughout in a fashion suitable for processing
24 
   with Doxygen. */
25 
 
26 
 
27 
/* Autoconf and/or portability configuration */
28 1350 nogj 
#include "config.h"
29 
 
30 1748 jeremybenn 
/* System includes */
31 
#include <stdlib.h>
32 
#include <assert.h>
33 1350 nogj 
 
34 1748 jeremybenn 
/* Package includes */
35 
#include "insn.h"
36 897 markom 
#include "sim-config.h"
37 879 markom 
 
38 1748 jeremybenn 
 
39 879 markom 
/* Table of known instructions.  Watch out for indexes I_*! */
40 
const cuc_known_insn known[II_LAST + 1] = {
41 1748 jeremybenn 
  {"add", 1, "assign \1 = \2 + \3;"},
42 
  {"sub", 0, "assign \1 = \2 - \3;"},
43 
  {"and", 1, "assign \1 = \2 & \3;"},
44 
  {"or", 1, "assign \1 = \2 | \3;"},
45 
  {"xor", 1, "assign \1 = \2 ^ \3;"},
46 
  {"mul", 1, "assign \1 = \2 * \3;"},
47 
 
48 
  {"srl", 0, "assign \1 = \2 >> \3;"},
49 
  {"sll", 0, "assign \1 = \2 << \3;"},
50 
  {"sra", 0, "assign \1 = ({32{\2[31]}} << (6'd32-{1'b0, \3}))\n\
51 879 markom 
                 | \2 >> \3;"},
52 
 
53 1748 jeremybenn 
  {"lb", 0, "always @(posedge clk)"},
54 
  {"lh", 0, "always @(posedge clk)"},
55 
  {"lw", 0, "always @(posedge clk)"},
56 
  {"sb", 0, "/* mem8[\2] = \1 */"},
57 
  {"sh", 0, "/* mem16[\2] = \1 */"},
58 
  {"sw", 0, "/* mem32[\2] = \1 */"},
59 879 markom 
 
60 1748 jeremybenn 
  {"sfeq", 1, "assign \1 = \2 == \3;"},
61 
  {"sfne", 1, "assign \1 = \2 != \3;"},
62 
  {"sfle", 0, "assign \1 = \2 <= \3;"},
63 
  {"sflt", 0, "assign \1 = \2 < \3;"},
64 
  {"sfge", 0, "assign \1 = \2 >= \3;"},
65 
  {"sfgt", 0, "assign \1 = \2 > \3;"},
66 
  {"bf", 0, ""},
67 879 markom 
 
68 1748 jeremybenn 
  {"lrbb", 0, "always @(posedge clk or posedge rst)"},
69 
  {"cmov", 0, "assign \1 = \4 ? \2 : \3;"},
70 
  {"reg", 0, "always @(posedge clk)"},
71 879 markom 
 
72 1748 jeremybenn 
  {"nop", 1, ""},
73 
  {"call", 0, "/* function call */"}
74 
};
75 879 markom 
 
76 
/* Find known instruction and attach them to insn */
77 1748 jeremybenn 
void
78 
change_insn_type (cuc_insn * i, int index)
79 879 markom 
{
80 
  int j;
81 
  assert (index >= 0 && index <= II_LAST);
82 
  i->index = index;
83 1748 jeremybenn 
  if (i->index == II_NOP)
84 
    {
85 
      for (j = 0; j < MAX_OPERANDS; j++)
86 
        i->opt[j] = OPT_NONE;
87 
      i->type = 0;
88 
      i->dep = NULL;
89 
      i->disasm[0] = '\0';
90 
    }
91 879 markom 
}
92 
 
93 
/* Returns instruction name */
94 1748 jeremybenn 
const char *
95 
cuc_insn_name (cuc_insn * ii)
96 
{
97 
  if (ii->index < 0 || ii->index > II_LAST)
98 
    return "???";
99 
  else
100 
    return known[ii->index].name;
101 879 markom 
}
102 883 markom 
 
103 897 markom 
/* Prints out instructions */
104 1748 jeremybenn 
void
105 
print_insns (int bb, cuc_insn * insn, int ninsn, int verbose)
106 897 markom 
{
107 
  int i, j;
108 1748 jeremybenn 
  for (i = 0; i < ninsn; i++)
109 
    {
110 
      char tmp[10];
111 
      dep_list *l = insn[i].dep;
112 
      sprintf (tmp, "[%x_%x]", bb, i);
113 
      PRINTF ("%-8s%c %-4s ", tmp, insn[i].index >= 0 ? ':' : '?',
114 
              cuc_insn_name (&insn[i]));
115 
      if (verbose)
116 
        {
117 
          PRINTF ("%-20s insn = %08lx, index = %i, type = %04x ",
118 
                  insn[i].disasm, insn[i].insn, insn[i].index, insn[i].type);
119 
        }
120 
      else
121 
        PRINTF ("type = %04x ", insn[i].type);
122 
      for (j = 0; j < MAX_OPERANDS; j++)
123 
        {
124 
          if (insn[i].opt[j] & OPT_DEST)
125 
            PRINTF ("*");
126 
          switch (insn[i].opt[j] & ~OPT_DEST)
127 
            {
128 
            case OPT_NONE:
129 
              break;
130 
            case OPT_CONST:
131 
              if (insn[i].type & IT_COND && (insn[i].index == II_CMOV
132 
                                             || insn[i].index == II_ADD))
133 
                PRINTF ("%lx, ", insn[i].op[j]);
134 
              else
135 
                PRINTF ("0x%08lx, ", insn[i].op[j]);
136 
              break;
137 
            case OPT_JUMP:
138 
              PRINTF ("J%lx, ", insn[i].op[j]);
139 
              break;
140 
            case OPT_REGISTER:
141 
              PRINTF ("r%li, ", insn[i].op[j]);
142 
              break;
143 
            case OPT_REF:
144 
              PRINTF ("[%lx_%lx], ", REF_BB (insn[i].op[j]),
145 
                      REF_I (insn[i].op[j]));
146 
              break;
147 
            case OPT_BB:
148 
              PRINTF ("BB ");
149 
              print_bb_num (insn[i].op[j]);
150 
              PRINTF (", ");
151 
              break;
152 
            case OPT_LRBB:
153 
              PRINTF ("LRBB, ");
154 
              break;
155 
            default:
156 
              fprintf (stderr, "Invalid operand type %s(%x_%x) = %x\n",
157 
                       cuc_insn_name (&insn[i]), i, j, insn[i].opt[j]);
158 
              assert (0);
159 
            }
160 
        }
161 
      if (l)
162 
        {
163 
          PRINTF ("\n\tdep:");
164 
          while (l)
165 
            {
166 
              PRINTF (" [%lx_%lx],", REF_BB (l->ref), REF_I (l->ref));
167 
              l = l->next;
168 
            }
169 
        }
170 
      PRINTF ("\n");
171 897 markom 
    }
172 
}
173 
 
174 1748 jeremybenn 
void
175 
add_dep (dep_list ** list, int dep)
176 897 markom 
{
177 
  dep_list *ndep;
178 
  dep_list **tmp = list;
179 
 
180 1748 jeremybenn 
  while (*tmp)
181 
    {
182 
      if ((*tmp)->ref == dep)
183 
        return;                 /* already there */
184 
      tmp = &((*tmp)->next);
185 
    }
186 
  ndep = (dep_list *) malloc (sizeof (dep_list));
187 897 markom 
  ndep->ref = dep;
188 
  ndep->next = NULL;
189 
  *tmp = ndep;
190 
}
191 
 
192 1748 jeremybenn 
void
193 
dispose_list (dep_list ** list)
194 897 markom 
{
195 1748 jeremybenn 
  while (*list)
196 
    {
197 
      dep_list *tmp = *list;
198 
      *list = tmp->next;
199 
      free (tmp);
200 
    }
201 897 markom 
}
202 
 
203 1748 jeremybenn 
void
204 
add_data_dep (cuc_func * f)
205 897 markom 
{
206 
  int b, i, j;
207 1748 jeremybenn 
  for (b = 0; b < f->num_bb; b++)
208 
    {
209 
      cuc_insn *insn = f->bb[b].insn;
210 
      for (i = 0; i < f->bb[b].ninsn; i++)
211 
        for (j = 0; j < MAX_OPERANDS; j++)
212 
          {
213 
            fflush (stdout);
214 
            if (insn[i].opt[j] & OPT_REF)
215 
              {
216 
                /* Copy list from predecessor */
217 
                dep_list *l = f->INSN (insn[i].op[j]).dep;
218 
                while (l)
219 
                  {
220 
                    add_dep (&insn[i].dep, l->ref);
221 
                    l = l->next;
222 
                  }
223 
                /* add predecessor */
224 
                add_dep (&insn[i].dep, insn[i].op[j]);
225 
              }
226 
          }
227 
    }
228 897 markom 
}
229 
 
230 953 markom 
/* Inserts n nops before insn 'ref' */
231 1748 jeremybenn 
void
232 
insert_insns (cuc_func * f, int ref, int n)
233 953 markom 
{
234 
  int b1, i, j;
235 1748 jeremybenn 
  int b = REF_BB (ref);
236 
  int ins = REF_I (ref);
237 
 
238 953 markom 
  assert (b < f->num_bb);
239 
  assert (ins <= f->bb[b].ninsn);
240 
  assert (f->bb[b].ninsn + n < MAX_INSNS);
241 1748 jeremybenn 
  if (cuc_debug >= 8)
242 
    print_cuc_bb (f, "PREINSERT");
243 953 markom 
  f->bb[b].insn = (cuc_insn *) realloc (f->bb[b].insn,
244 1748 jeremybenn 
                                        (f->bb[b].ninsn +
245 
                                         n) * sizeof (cuc_insn));
246 953 markom 
 
247 
  /* Set up relocations */
248 
  for (i = 0; i < f->bb[b].ninsn; i++)
249 1748 jeremybenn 
    if (i < ins)
250 
      reloc[i] = i;
251 
    else
252 
      reloc[i] = i + n;
253 953 markom 
 
254 
  /* Move instructions, based on relocations */
255 1748 jeremybenn 
  for (i = f->bb[b].ninsn - 1; i >= 0; i--)
256 
    f->bb[b].insn[reloc[i]] = f->bb[b].insn[i];
257 
  for (i = 0; i < n; i++)
258 
    change_insn_type (&f->bb[b].insn[ins + i], II_NOP);
259 953 markom 
 
260 
  f->bb[b].ninsn += n;
261 1748 jeremybenn 
  for (b1 = 0; b1 < f->num_bb; b1++)
262 
    {
263 
      dep_list *d = f->bb[b1].mdep;
264 
      while (d)
265 
        {
266 
          if (REF_BB (d->ref) == b && REF_I (d->ref) >= ins)
267 
            d->ref = REF (b, REF_I (d->ref) + n);
268 
          d = d->next;
269 
        }
270 
      for (i = 0; i < f->bb[b1].ninsn; i++)
271 
        {
272 
          d = f->bb[b1].insn[i].dep;
273 
          while (d)
274 
            {
275 
              if (REF_BB (d->ref) == b && REF_I (d->ref) >= ins)
276 
                d->ref = REF (b, REF_I (d->ref) + n);
277 
              d = d->next;
278 
            }
279 
          for (j = 0; j < MAX_OPERANDS; j++)
280 
            if (f->bb[b1].insn[i].opt[j] & OPT_REF
281 
                && REF_BB (f->bb[b1].insn[i].op[j]) == b
282 
                && REF_I (f->bb[b1].insn[i].op[j]) >= ins)
283 
              f->bb[b1].insn[i].op[j] =
284 
                REF (b, REF_I (f->bb[b1].insn[i].op[j]) + n);
285 
        }
286 953 markom 
    }
287 
  for (i = 0; i < f->nmsched; i++)
288 1748 jeremybenn 
    if (REF_BB (f->msched[i]) == b)
289 
      f->msched[i] = REF (b, reloc[REF_I (f->msched[i])]);
290 
  if (cuc_debug >= 8)
291 
    print_cuc_bb (f, "POSTINSERT");
292 953 markom 
  cuc_check (f);
293 
}
294 
 
295 897 markom 
/* returns nonzero, if instruction was simplified */
296 1748 jeremybenn 
int
297 
apply_edge_condition (cuc_insn * ii)
298 897 markom 
{
299 
  unsigned int c = ii->op[2];
300 
 
301 1748 jeremybenn 
  switch (ii->index)
302 
    {
303 
    case II_AND:
304 
      if (ii->opt[2] & OPT_CONST && c == 0)
305 
        {
306 
          change_insn_type (ii, II_ADD);
307 
          ii->op[1] = 0;
308 
          ii->opt[1] = OPT_CONST;
309 
          ii->op[2] = 0;
310 
          ii->opt[2] = OPT_CONST;
311 
          return 1;
312 
        }
313 
      else if (ii->opt[2] & OPT_CONST && c == 0xffffffff)
314 
        {
315 
          change_insn_type (ii, II_ADD);
316 
          ii->op[2] = 0;
317 
          ii->opt[2] = OPT_CONST;
318 
          return 1;
319 
        }
320 
      else
321 
        break;
322 
    case II_OR:
323 
      if (ii->opt[2] & OPT_CONST && c == 0x0)
324 
        {
325 
          change_insn_type (ii, II_ADD);
326 
          ii->op[1] = c;
327 
          ii->opt[1] = OPT_CONST;
328 
          ii->op[2] = 0;
329 
          ii->opt[2] = OPT_CONST;
330 
          return 1;
331 
        }
332 
      else if (ii->opt[2] & OPT_CONST && c == 0xffffffff)
333 
        {
334 
          change_insn_type (ii, II_ADD);
335 
          ii->op[1] = 0xffffffff;
336 
          ii->opt[1] = OPT_CONST;
337 
          ii->op[2] = 0;
338 
          ii->opt[2] = OPT_CONST;
339 
          return 1;
340 
        }
341 
      else
342 
        break;
343 
    case II_SUB:
344 
      if (ii->opt[1] == ii->opt[2] && ii->op[1] == ii->op[2])
345 
        {
346 
          change_insn_type (ii, II_ADD);
347 
          ii->op[1] = 0;
348 
          ii->opt[1] = OPT_CONST;
349 
          ii->op[2] = 0;
350 
          ii->opt[2] = OPT_CONST;
351 
          return 1;
352 
        }
353 
      else
354 
        break;
355 
    case II_MUL:
356 
      if (ii->opt[2] & OPT_CONST && c == 0)
357 
        {
358 
          change_insn_type (ii, II_ADD);
359 
          ii->op[1] = 0;
360 
          ii->opt[1] = OPT_CONST;
361 
          ii->op[2] = 0;
362 
          ii->opt[2] = OPT_CONST;
363 
          return 1;
364 
        }
365 
      else if (ii->opt[2] & OPT_CONST && c == 1)
366 
        {
367 
          change_insn_type (ii, II_ADD);
368 
          ii->op[1] = c;
369 
          ii->opt[1] = OPT_CONST;
370 
          ii->op[2] = 0;
371 
          ii->opt[2] = OPT_CONST;
372 
          return 1;
373 
        }
374 
      else if (ii->opt[2] & OPT_CONST && c == 0xffffffff)
375 
        {
376 
          change_insn_type (ii, II_SUB);
377 
          ii->op[2] = ii->op[1];
378 
          ii->opt[2] = ii->opt[1];
379 
          ii->op[1] = 0;
380 
          ii->opt[1] = OPT_CONST;
381 
          return 1;
382 
        }
383 
      else
384 
        break;
385 
    case II_SRL:
386 
      if (ii->opt[2] & OPT_CONST && c == 0)
387 
        {
388 
          change_insn_type (ii, II_ADD);
389 
          ii->op[1] = c;
390 
          ii->opt[1] = OPT_CONST;
391 
          ii->op[2] = 0;
392 
          ii->opt[2] = OPT_CONST;
393 
          return 1;
394 
        }
395 
      else if (ii->opt[2] & OPT_CONST && c >= 32)
396 
        {
397 
          change_insn_type (ii, II_ADD);
398 
          ii->op[1] = 0;
399 
          ii->opt[1] = OPT_CONST;
400 
          ii->op[2] = 0;
401 
          ii->opt[2] = OPT_CONST;
402 
          return 1;
403 
        }
404 
      else
405 
        break;
406 
    case II_SLL:
407 
      if (ii->opt[2] & OPT_CONST && c == 0)
408 
        {
409 
          change_insn_type (ii, II_ADD);
410 
          ii->op[1] = c;
411 
          ii->opt[1] = OPT_CONST;
412 
          ii->op[2] = 0;
413 
          ii->opt[2] = OPT_CONST;
414 
          return 1;
415 
        }
416 
      else if (ii->opt[2] & OPT_CONST && c >= 32)
417 
        {
418 
          change_insn_type (ii, II_ADD);
419 
          ii->op[1] = 0;
420 
          ii->opt[1] = OPT_CONST;
421 
          ii->op[2] = 0;
422 
          ii->opt[2] = OPT_CONST;
423 
          return 1;
424 
        }
425 
      else
426 
        break;
427 
    case II_SRA:
428 
      if (ii->opt[2] & OPT_CONST && c == 0)
429 
        {
430 
          change_insn_type (ii, II_ADD);
431 
          ii->op[1] = c;
432 
          ii->opt[1] = OPT_CONST;
433 
          ii->op[2] = 0;
434 
          ii->opt[2] = OPT_CONST;
435 
          return 1;
436 
        }
437 
      else
438 
        break;
439 
    case II_SFEQ:
440 
      if (ii->opt[1] & OPT_CONST && ii->opt[2] & OPT_CONST)
441 
        {
442 
          change_insn_type (ii, II_ADD);
443 
          ii->op[1] = ii->op[1] == ii->op[2];
444 
          ii->opt[1] = OPT_CONST;
445 
          ii->op[2] = 0;
446 
          ii->opt[2] = OPT_CONST;
447 
          return 1;
448 
        }
449 
      else
450 
        break;
451 
    case II_SFNE:
452 
      if (ii->opt[1] & OPT_CONST && ii->opt[2] & OPT_CONST)
453 
        {
454 
          change_insn_type (ii, II_ADD);
455 
          ii->op[1] = ii->op[1] != ii->op[2];
456 
          ii->opt[1] = OPT_CONST;
457 
          ii->op[2] = 0;
458 
          ii->opt[2] = OPT_CONST;
459 
          return 1;
460 
        }
461 
      else
462 
        break;
463 
    case II_SFLE:
464 
      if (ii->opt[1] & OPT_CONST && ii->opt[2] & OPT_CONST)
465 
        {
466 
          change_insn_type (ii, II_ADD);
467 
          ii->op[1] = ii->op[1] <= ii->op[2];
468 
          ii->opt[1] = OPT_CONST;
469 
          ii->op[2] = 0;
470 
          ii->opt[2] = OPT_CONST;
471 
          return 1;
472 
        }
473 
      else if (ii->opt[2] && OPT_CONST && ii->op[2] == 0)
474 
        {
475 
          change_insn_type (ii, II_SFEQ);
476 
        }
477 
      else
478 
        break;
479 
    case II_SFLT:
480 
      if (ii->opt[1] & OPT_CONST && ii->opt[2] & OPT_CONST)
481 
        {
482 
          change_insn_type (ii, II_ADD);
483 
          ii->op[1] = ii->op[1] < ii->op[2];
484 
          ii->opt[1] = OPT_CONST;
485 
          ii->op[2] = 0;
486 
          ii->opt[2] = OPT_CONST;
487 
          return 1;
488 
        }
489 
      else if (ii->opt[2] && OPT_CONST && ii->op[2] == 0)
490 
        {
491 
          change_insn_type (ii, II_ADD);
492 
          ii->op[1] = 0;
493 
          ii->opt[1] = OPT_CONST;
494 
        }
495 
      break;
496 
    case II_SFGE:
497 
      if (ii->opt[1] & OPT_CONST && ii->opt[2] & OPT_CONST)
498 
        {
499 
          change_insn_type (ii, II_ADD);
500 
          ii->op[1] = ii->op[1] >= ii->op[2];
501 
          ii->opt[1] = OPT_CONST;
502 
          ii->op[2] = 0;
503 
          ii->opt[2] = OPT_CONST;
504 
          return 1;
505 
        }
506 
      else if (ii->opt[2] && OPT_CONST && ii->op[2] == 0)
507 
        {
508 
          change_insn_type (ii, II_ADD);
509 
          ii->op[1] = 1;
510 
          ii->opt[1] = OPT_CONST;
511 
        }
512 
      else
513 
        break;
514 
    case II_SFGT:
515 
      if (ii->opt[1] & OPT_CONST && ii->opt[2] & OPT_CONST)
516 
        {
517 
          change_insn_type (ii, II_ADD);
518 
          ii->op[1] = ii->op[1] > ii->op[2];
519 
          ii->opt[1] = OPT_CONST;
520 
          ii->op[2] = 0;
521 
          ii->opt[2] = OPT_CONST;
522 
          return 1;
523 
        }
524 
      else if (ii->opt[2] && OPT_CONST && ii->op[2] == 0)
525 
        {
526 
          change_insn_type (ii, II_SFNE);
527 
        }
528 
      else
529 
        break;
530 
    case II_CMOV:
531 
      if (ii->opt[1] == ii->opt[2] && ii->op[1] == ii->op[2])
532 
        {
533 
          change_insn_type (ii, II_ADD);
534 
          ii->op[2] = 0;
535 
          ii->opt[2] = OPT_CONST;
536 
          ii->opt[3] = OPT_NONE;
537 
          return 1;
538 
        }
539 
      if (ii->opt[3] & OPT_CONST)
540 
        {
541 
          change_insn_type (ii, II_ADD);
542 
          if (ii->op[3])
543 
            {
544 
              ii->op[2] = 0;
545 
              ii->opt[2] = OPT_CONST;
546 
            }
547 
          else
548 
            {
549 
              ii->op[1] = 0;
550 
              ii->opt[1] = OPT_CONST;
551 
            }
552 
          ii->opt[3] = OPT_NONE;
553 
          return 1;
554 
        }
555 
      if (ii->type & IT_COND)
556 
        {
557 
          if (ii->opt[1] & OPT_CONST && ii->opt[2] & OPT_CONST)
558 
            {
559 
              if (ii->op[1] && !ii->op[2])
560 
                {
561 
                  change_insn_type (ii, II_ADD);
562 
                  ii->op[1] = ii->op[3];
563 
                  ii->opt[1] = ii->opt[3];
564 
                  ii->op[2] = 0;
565 
                  ii->opt[2] = OPT_CONST;
566 
                  ii->opt[3] = OPT_NONE;
567 
                  return 1;
568 
                }
569 
              if (ii->op[1] && ii->op[2])
570 
                {
571 
                  change_insn_type (ii, II_ADD);
572 
                  ii->op[1] = 1;
573 
                  ii->opt[1] = OPT_CONST;
574 
                  ii->op[2] = 0;
575 
                  ii->opt[2] = OPT_CONST;
576 
                  ii->opt[3] = OPT_NONE;
577 
                  return 1;
578 
                }
579 
              if (!ii->op[1] && !ii->op[2])
580 
                {
581 
                  change_insn_type (ii, II_ADD);
582 
                  ii->op[1] = 0;
583 
                  ii->opt[1] = OPT_CONST;
584 
                  ii->op[2] = 0;
585 
                  ii->opt[2] = OPT_CONST;
586 
                  ii->opt[3] = OPT_NONE;
587 
                  return 1;
588 
                }
589 
            }
590 
          if (ii->op[1] == ii->op[3] && ii->opt[1] == ii->opt[3])
591 
            {
592 
              ii->op[1] = 1;
593 
              ii->opt[1] = OPT_CONST;
594 
              return 1;
595 
            }
596 
          if (ii->op[2] == ii->op[3] && ii->opt[2] == ii->opt[3])
597 
            {
598 
              ii->op[2] = 0;
599 
              ii->opt[2] = OPT_CONST;
600 
              return 1;
601 
            }
602 
        }
603 
      break;
604 897 markom 
    }
605 
  return 0;
606 
}
607 
 
608 902 markom 
/* First primary input */
609 
static unsigned long tmp_op, tmp_opt;
610 
 
611 
/* Recursive function that searches for primary inputs;
612 
   returns 0 if cmov can be replaced by add */
613 1748 jeremybenn 
static int
614 
cmov_needed (cuc_func * f, int ref)
615 902 markom 
{
616 1748 jeremybenn 
  cuc_insn *ii = &f->INSN (ref);
617 902 markom 
  int j;
618 1748 jeremybenn 
 
619 903 markom 
  cucdebug (4, " %x", ref);
620 902 markom 
  /* mark visited, if already marked, we have a loop, ignore */
621 1748 jeremybenn 
  if (ii->tmp)
622 
    return 0;
623 902 markom 
  ii->tmp = 1;
624 
 
625 
  /* handle normal movs separately */
626 917 markom 
  if (ii->index == II_ADD && !(ii->type & IT_VOLATILE)
627 1748 jeremybenn 
      && ii->opt[2] == OPT_CONST && ii->op[2] == 0)
628 
    {
629 
      if (ii->opt[1] == OPT_REF)
630 
        {
631 
          if (cmov_needed (f, ii->op[1]))
632 
            {
633 
              ii->tmp = 0;
634 
              return 1;
635 
            }
636 
        }
637 
      else
638 
        {
639 
          if (tmp_opt == OPT_NONE)
640 
            {
641 
              tmp_op = ii->op[1];
642 
              tmp_opt = ii->opt[1];
643 
            }
644 
          else if (tmp_opt != ii->opt[1] || tmp_op != ii->op[1])
645 
            {
646 
              ii->tmp = 0;
647 
              return 1;
648 
            }
649 
        }
650 
      ii->tmp = 0;
651 
      return 0;
652 902 markom 
    }
653 
 
654 
  /* Is this instruction CMOV? no => add to primary inputs */
655 1748 jeremybenn 
  if ((ii->index != II_CMOV) || (ii->type & IT_VOLATILE))
656 
    {
657 
      if (tmp_opt == OPT_NONE)
658 
        {
659 
          tmp_op = ref;
660 
          tmp_opt = OPT_REF;
661 
          ii->tmp = 0;
662 
          return 0;
663 
        }
664 
      else if (tmp_opt != OPT_REF || tmp_op != ref)
665 
        {
666 
          ii->tmp = 0;
667 
          return 1;
668 
        }
669 
      else
670 
        {
671 
          ii->tmp = 0;
672 
          return 0;
673 
        }
674 902 markom 
    }
675 
 
676 1748 jeremybenn 
  for (j = 1; j < 3; j++)
677 
    {
678 
      cucdebug (4, "(%x:%i)", ref, j);
679 
      if (ii->opt[j] == OPT_REF)
680 
        {
681 
          if (cmov_needed (f, ii->op[j]))
682 
            {
683 
              ii->tmp = 0;
684 
              return 1;
685 
            }
686 
        }
687 
      else
688 
        {
689 
          if (tmp_opt == OPT_NONE)
690 
            {
691 
              tmp_op = ii->op[j];
692 
              tmp_opt = ii->opt[j];
693 
            }
694 
          else if (tmp_opt != ii->opt[j] || tmp_op != ii->op[j])
695 
            {
696 
              ii->tmp = 0;
697 
              return 1;
698 
            }
699 
        }
700 902 markom 
    }
701 
 
702 
  ii->tmp = 0;
703 
  return 0;
704 
}
705 
 
706 
/* Search and optimize complex cmov assignments */
707 1748 jeremybenn 
int
708 
optimize_cmovs (cuc_func * f)
709 902 markom 
{
710 931 markom 
  int modified = 0;
711 1308 phoenix 
  int b, i;
712 902 markom 
 
713 
  /* Mark all instructions unvisited */
714 1748 jeremybenn 
  for (b = 0; b < f->num_bb; b++)
715 
    if (!(f->bb[b].type & BB_DEAD))
716 
      for (i = 0; i < f->bb[b].ninsn; i++)
717 
        f->bb[b].insn[i].tmp = 0;
718 
 
719 
  for (b = 0; b < f->num_bb; b++)
720 
    if (!(f->bb[b].type & BB_DEAD))
721 
      {
722 
        for (i = 0; i < f->bb[b].ninsn; i++)
723 
          {
724 
            cuc_insn *ii = &f->bb[b].insn[i];
725 
            if (ii->index == II_CMOV && !(ii->type & IT_VOLATILE))
726 
              {
727 
                tmp_opt = OPT_NONE;
728 
                cucdebug (4, "\n");
729 
                if (!cmov_needed (f, REF (b, i)))
730 
                  {
731 
                    assert (tmp_opt != OPT_NONE);
732 
                    change_insn_type (ii, II_ADD);
733 
                    ii->op[1] = tmp_op;
734 
                    ii->opt[1] = tmp_opt;
735 
                    ii->op[2] = 0;
736 
                    ii->opt[2] = OPT_CONST;
737 
                    ii->opt[3] = OPT_NONE;
738 
                    modified = 1;
739 
                  }
740 
              }
741 
          }
742 902 markom 
      }
743 931 markom 
  return modified;
744 902 markom 
}
745 
 
746 930 markom 
/* returns number of instructions, using instruction ref */
747 1748 jeremybenn 
static int
748 
insn_uses (cuc_func * f, int ref)
749 930 markom 
{
750 
  int b, i, j;
751 
  int cnt = 0;
752 
  for (b = 0; b < f->num_bb; b++)
753 
    for (i = 0; i < f->bb[b].ninsn; i++)
754 
      for (j = 0; j < MAX_OPERANDS; j++)
755 1748 jeremybenn 
        if (f->bb[b].insn[i].opt[j] & OPT_REF
756 
            && f->bb[b].insn[i].op[j] == ref)
757 
          cnt++;
758 930 markom 
  return cnt;
759 
}
760 
 
761 
/* handles some common CMOV, CMOV-CMOV cases;
762 
   returns nonzero if anything optimized */
763 1748 jeremybenn 
static int
764 
optimize_cmov_more (cuc_func * f, int ref)
765 930 markom 
{
766 
  int t = 0;
767 1748 jeremybenn 
  cuc_insn *ii = &f->INSN (ref);
768 930 markom 
  assert (ii->index == II_CMOV);
769 1748 jeremybenn 
 
770 930 markom 
  /* In case of x = cmov x, y; or x = cmov y, x; we have
771 
     asynchroneous loop -> remove it */
772 1748 jeremybenn 
  if ((ii->opt[1] & OPT_REF) && ii->op[1] == ref)
773 
    t = 1;
774 
  if ((ii->opt[2] & OPT_REF) && ii->op[2] == ref)
775 
    t = 2;
776 
  if (ii->opt[1] == ii->opt[2] && ii->op[1] == ii->op[2])
777 
    t = 2;
778 
  if (t)
779 
    {
780 
      change_insn_type (ii, II_ADD);
781 
      cucdebug (2, "%8x:cmov     %i\n", ref, t);
782 
      ii->opt[t] = OPT_CONST;
783 
      ii->op[t] = 0;
784 
      ii->opt[3] = OPT_NONE;
785 
      return 1;
786 930 markom 
    }
787 1748 jeremybenn 
  if (!(ii->type & IT_COND))
788 
    {
789 
      for (t = 1; t <= 2; t++)
790 
        {
791 
          /*   cmov L, X, Y, C1
792 
             cmov Z, L, Y, C2
793 
             can be replaced with simpler:
794 
             cmov L, C1, C2, C2
795 
             cmov Z, X, Y, L */
796 
          if (ii->opt[t] == OPT_REF && f->INSN (ii->op[t]).index == II_CMOV)
797 
            {
798 
              int r = ii->op[t];
799 
              unsigned long x, xt, y, yt;
800 
              cuc_insn *prev = &f->INSN (r);
801 
              cuc_check (f);
802 
              cucdebug (3, "%x-%x\n", ref, r);
803 
              assert (!(prev->type & IT_COND));
804 
              if (prev->op[3 - t] != ii->op[3 - t]
805 
                  || prev->opt[3 - t] != ii->opt[3 - t]
806 
                  || insn_uses (f, r) > 1)
807 
                continue;
808 
              cucdebug (3, "%x-%x cmov more\n", ref, r);
809 
              prev->type |= IT_COND;
810 
              x = prev->op[t];
811 
              xt = prev->opt[t];
812 
              y = prev->op[3 - t];
813 
              yt = prev->opt[3 - t];
814 
              prev->op[t] = ii->op[3];
815 
              prev->opt[t] = ii->opt[3];        /* C2 */
816 
              ii->op[3] = r;
817 
              ii->opt[3] = OPT_REF;     /* L */
818 
              prev->op[3 - t] = prev->op[3];
819 
              prev->opt[3 - t] = prev->opt[3];  /* C1 */
820 
              prev->op[3] = prev->op[t];
821 
              prev->opt[3] = prev->opt[t];      /* C2 */
822 
              ii->op[t] = x;
823 
              ii->opt[t] = xt;  /* X */
824 
              ii->op[3 - t] = y;
825 
              ii->opt[3 - t] = yt;      /* Y */
826 
              prev->op[0] = -1;
827 
              prev->opt[0] = OPT_REGISTER | OPT_DEST;
828 
              cuc_check (f);
829 
              return 1;
830 
            }
831 
        }
832 
    }
833 930 markom 
 
834 1748 jeremybenn 
  if (ii->opt[3] & OPT_REF)
835 
    {
836 
      cuc_insn *prev = &f->INSN (ii->op[3]);
837 
      assert (prev->type & IT_COND);
838 
      if (prev->index == II_CMOV)
839 
        {
840 
          /* negated conditional:
841 
             cmov x, 0, 1, y
842 
             cmov z, a, b, x
843 
             is replaced by
844 
             cmov z, b, a, y */
845 
          if (prev->opt[1] & OPT_CONST && prev->opt[2] & OPT_CONST
846 
              && !prev->op[1] && prev->op[2])
847 
            {
848 
              unsigned long t;
849 
              t = ii->op[1];
850 
              ii->op[1] = ii->op[2];
851 
              ii->op[2] = t;
852 
              t = ii->opt[1];
853 
              ii->opt[1] = ii->opt[2];
854 
              ii->opt[2] = t;
855 
              ii->op[3] = prev->op[3];
856 
              ii->opt[3] = prev->opt[3];
857 
            }
858 
        }
859 
      else if (prev->index == II_ADD)
860 
        {
861 
          /*   add x, y, 0
862 
             cmov z, a, b, x
863 
             is replaced by
864 
             cmov z, a, b, y */
865 
          if (prev->opt[2] & OPT_CONST && prev->op[2] == 0)
866 
            {
867 
              ii->op[3] = prev->op[1];
868 
              ii->opt[3] = prev->opt[1];
869 
              return 1;
870 
            }
871 
        }
872 930 markom 
    }
873 1046 markom 
 
874 
  /* Check if both choices can be pushed through */
875 1047 markom 
  if (ii->opt[1] & OPT_REF && ii->opt[2] & OPT_REF
876 1748 jeremybenn 
      /* Usually doesn't make sense to move conditionals though => more area */
877 
      && !(ii->type & IT_COND))
878 
    {
879 
      cuc_insn *a, *b;
880 
      a = &f->INSN (ii->op[1]);
881 
      b = &f->INSN (ii->op[2]);
882 
      if (a->index == b->index && !(a->type & IT_VOLATILE)
883 
          && !(b->type & IT_VOLATILE))
884 
        {
885 
          int diff = -1;
886 
          int i;
887 
          for (i = 0; i < MAX_OPERANDS; i++)
888 
            if (a->opt[i] != b->opt[i]
889 
                || !(a->op[i] == b->op[i] || a->opt[i] & OPT_REGISTER))
890 
              {
891 
                if (diff == -1)
892 
                  diff = i;
893 
                else
894 
                  diff = -2;
895 
              }
896 
          /* If diff == -1, it will be eliminated by CSE */
897 
          if (diff >= 0)
898 
            {
899 
              cuc_insn tmp, cmov;
900 
              int ref2 = REF (REF_BB (ref), REF_I (ref) + 1);
901 
              insert_insns (f, ref, 1);
902 
              a = &f->INSN (f->INSN (ref2).op[1]);
903 
              b = &f->INSN (f->INSN (ref2).op[2]);
904 
              cucdebug (4, "ref = %x %lx %lx\n", ref, f->INSN (ref2).op[1],
905 
                        f->INSN (ref2).op[2]);
906 
              if (cuc_debug >= 7)
907 
                {
908 
                  print_cuc_bb (f, "AAA");
909 
                  cuc_check (f);
910 
                }
911 
              tmp = *a;
912 
              cmov = f->INSN (ref2);
913 
              tmp.op[diff] = ref;
914 
              tmp.opt[diff] = OPT_REF;
915 
              cmov.op[0] = -1;
916 
              cmov.opt[0] = OPT_REGISTER | OPT_DEST;
917 
              cmov.op[1] = a->op[diff];
918 
              cmov.opt[1] = a->opt[diff];
919 
              cmov.op[2] = b->op[diff];
920 
              cmov.opt[2] = b->opt[diff];
921 
              change_insn_type (&cmov, II_CMOV);
922 
              cmov.type &= ~IT_COND;
923 
              cucdebug (4, "ref2 = %x %lx %lx\n", ref2, cmov.op[1],
924 
                        cmov.op[2]);
925 
              if (cmov.opt[1] & OPT_REF && cmov.opt[2] & OPT_REF
926 
                  && f->INSN (cmov.op[1]).type & IT_COND)
927 
                {
928 
                  assert (f->INSN (cmov.op[2]).type & IT_COND);
929 
                  cmov.type |= IT_COND;
930 
                }
931 
              f->INSN (ref) = cmov;
932 
              f->INSN (ref2) = tmp;
933 
              if (cuc_debug >= 6)
934 
                print_cuc_bb (f, "BBB");
935 
              cuc_check (f);
936 
              return 1;
937 
            }
938 
        }
939 1046 markom 
    }
940 930 markom 
  return 0;
941 
}
942 
 
943 897 markom 
/* Optimizes dataflow tree */
944 1748 jeremybenn 
int
945 
optimize_tree (cuc_func * f)
946 897 markom 
{
947 
  int b, i, j;
948 
  int modified;
949 931 markom 
  int gmodified = 0;
950 897 markom 
 
951 1748 jeremybenn 
  do
952 
    {
953 
      modified = 0;
954 
      if (cuc_debug)
955 
        cuc_check (f);
956 
      for (b = 0; b < f->num_bb; b++)
957 
        if (!(f->bb[b].type & BB_DEAD))
958 
          {
959 
            for (i = 0; i < f->bb[b].ninsn; i++)
960 
              {
961 
                cuc_insn *ii = &f->bb[b].insn[i];
962 
                /* We tend to have the third parameter const if instruction is cumutative */
963 
                if ((ii->opt[1] & OPT_CONST) && !(ii->opt[2] & OPT_CONST))
964 
                  {
965 
                    int cond = ii->index == II_SFEQ || ii->index == II_SFNE
966 
                      || ii->index == II_SFLT || ii->index == II_SFLE
967 
                      || ii->index == II_SFGT || ii->index == II_SFGE;
968 
                    if (known[ii->index].comutative || cond)
969 
                      {
970 
                        unsigned long t = ii->opt[1];
971 
                        ii->opt[1] = ii->opt[2];
972 
                        ii->opt[2] = t;
973 
                        t = ii->op[1];
974 
                        ii->op[1] = ii->op[2];
975 
                        ii->op[2] = t;
976 
                        modified = 1;
977 
                        cucdebug (2, "%08x:<>\n", REF (b, i));
978 
                        if (cond)
979 
                          {
980 
                            if (ii->index == II_SFEQ)
981 
                              ii->index = II_SFNE;
982 
                            else if (ii->index == II_SFNE)
983 
                              ii->index = II_SFEQ;
984 
                            else if (ii->index == II_SFLE)
985 
                              ii->index = II_SFGT;
986 
                            else if (ii->index == II_SFLT)
987 
                              ii->index = II_SFGE;
988 
                            else if (ii->index == II_SFGE)
989 
                              ii->index = II_SFLT;
990 
                            else if (ii->index == II_SFGT)
991 
                              ii->index = II_SFLE;
992 
                            else
993 
                              assert (0);
994 
                          }
995 
                      }
996 
                  }
997 897 markom 
 
998 1748 jeremybenn 
                /* Try to do the promotion */
999 
                /* We have two consecutive expressions, containing constants,
1000 
                 * if previous is a simple expression we can handle it simply: */
1001 
                for (j = 0; j < MAX_OPERANDS; j++)
1002 
                  if (ii->opt[j] & OPT_REF)
1003 
                    {
1004 
                      cuc_insn *t = &f->INSN (ii->op[j]);
1005 
                      if (f->INSN (ii->op[j]).index == II_ADD
1006 
                          && f->INSN (ii->op[j]).opt[2] & OPT_CONST
1007 
                          && f->INSN (ii->op[j]).op[2] == 0
1008 
                          && !(ii->type & IT_MEMORY && t->type & IT_MEMADD))
1009 
                        {
1010 
                          /* do not promote through add-mem, and branches */
1011 
                          modified = 1;
1012 
                          cucdebug (2, "%8x:promote%i %8lx %8lx\n",
1013 
                                    REF (b, i), j, ii->op[j], t->op[1]);
1014 
                          ii->op[j] = t->op[1];
1015 
                          ii->opt[j] = t->opt[1];
1016 
                        }
1017 
                    }
1018 897 markom 
 
1019 1748 jeremybenn 
                /* handle some CMOV cases more deeply */
1020 
                if (ii->index == II_CMOV
1021 
                    && optimize_cmov_more (f, REF (b, i)))
1022 
                  {
1023 
                    modified = 1;
1024 
                    continue;
1025 
                  }
1026 
 
1027 
                /* Do nothing to volatile instructions */
1028 
                if (ii->type & IT_VOLATILE)
1029 
                  continue;
1030 
 
1031 
                /* Check whether we can simplify the instruction */
1032 
                if (apply_edge_condition (ii))
1033 
                  {
1034 
                    modified = 1;
1035 
                    continue;
1036 
                  }
1037 
                /* We cannot do anything more if at least one is not constant */
1038 
                if (!(ii->opt[2] & OPT_CONST))
1039 
                  continue;
1040 
 
1041 
                if (ii->opt[1] & OPT_CONST)
1042 
                  {             /* We have constant expression */
1043 
                    unsigned long value;
1044 
                    int ok = 1;
1045 
                    /* Was constant expression already? */
1046 
                    if (ii->index == II_ADD && !ii->op[2])
1047 
                      continue;
1048 
 
1049 
                    if (ii->index == II_ADD)
1050 
                      value = ii->op[1] + ii->op[2];
1051 
                    else if (ii->index == II_SUB)
1052 
                      value = ii->op[1] - ii->op[2];
1053 
                    else if (ii->index == II_SLL)
1054 
                      value = ii->op[1] << ii->op[2];
1055 
                    else if (ii->index == II_SRL)
1056 
                      value = ii->op[1] >> ii->op[2];
1057 
                    else if (ii->index == II_MUL)
1058 
                      value = ii->op[1] * ii->op[2];
1059 
                    else if (ii->index == II_OR)
1060 
                      value = ii->op[1] | ii->op[2];
1061 
                    else if (ii->index == II_XOR)
1062 
                      value = ii->op[1] ^ ii->op[2];
1063 
                    else if (ii->index == II_AND)
1064 
                      value = ii->op[1] & ii->op[2];
1065 
                    else
1066 
                      ok = 0;
1067 
                    if (ok)
1068 
                      {
1069 
                        change_insn_type (ii, II_ADD);
1070 
                        ii->op[0] = -1;
1071 
                        ii->opt[0] = OPT_REGISTER | OPT_DEST;
1072 
                        ii->op[1] = value;
1073 
                        ii->opt[1] = OPT_CONST;
1074 
                        ii->op[2] = 0;
1075 
                        ii->opt[2] = OPT_CONST;
1076 
                        modified = 1;
1077 
                        cucdebug (2, "%8x:const\n", REF (b, i));
1078 
                      }
1079 
                  }
1080 
                else if (ii->opt[1] & OPT_REF)
1081 
                  {
1082 
                    cuc_insn *prev = &f->INSN (ii->op[1]);
1083 
                    /* Is this just a move? */
1084 
                    if (ii->index == II_ADD
1085 
                        && !(ii->type & IT_MEMADD) && ii->op[2] == 0)
1086 
                      {
1087 
                        int b1, i1, j1;
1088 
                        cucdebug (2, "%8x:link      %8lx: ", REF (b, i),
1089 
                                  ii->op[1]);
1090 
                        if (!(prev->type & (IT_OUTPUT | IT_VOLATILE)))
1091 
                          {
1092 
                            assert (ii->opt[0] & OPT_DEST);
1093 
                            prev->op[0] = ii->op[0];
1094 
                            prev->opt[0] = ii->opt[0];
1095 
                            prev->type |= ii->type & IT_OUTPUT;
1096 
                            for (b1 = 0; b1 < f->num_bb; b1++)
1097 
                              if (!(f->bb[b1].type & BB_DEAD))
1098 
                                for (i1 = 0; i1 < f->bb[b1].ninsn; i1++)
1099 
                                  for (j1 = 0; j1 < MAX_OPERANDS; j1++)
1100 
                                    if ((f->bb[b1].insn[i1].opt[j1] & OPT_REF)
1101 
                                        && f->bb[b1].insn[i1].op[j1] ==
1102 
                                        REF (b, i))
1103 
                                      {
1104 
                                        cucdebug (2, "%x ", REF (b1, i1));
1105 
                                        f->bb[b1].insn[i1].op[j1] = ii->op[1];
1106 
                                      }
1107 
                            cucdebug (2, "\n");
1108 
                            change_insn_type (ii, II_NOP);
1109 
                          }
1110 
                      }
1111 
                    else if (prev->opt[2] & OPT_CONST)
1112 
                      {
1113 
                        /* Handle some common cases */
1114 
                        /* add - add joining */
1115 
                        if (ii->index == II_ADD && prev->index == II_ADD)
1116 
                          {
1117 
                            ii->op[1] = prev->op[1];
1118 
                            ii->opt[1] = prev->opt[1];
1119 
                            ii->op[2] += prev->op[2];
1120 
                            modified = 1;
1121 
                            cucdebug (2, "%8x: add-add\n", REF (b, i));
1122 
                          }
1123 
                        else /* add - sub joining */ if (ii->index == II_ADD
1124 
                                                         && prev->index ==
1125 
                                                         II_SUB)
1126 
                          {
1127 
                            change_insn_type (&insn[i], II_SUB);
1128 
                            ii->op[1] = prev->op[1];
1129 
                            ii->opt[1] = prev->opt[1];
1130 
                            ii->op[2] += prev->op[2];
1131 
                            modified = 1;
1132 
                            cucdebug (2, "%8x: add-sub\n", REF (b, i));
1133 
                          }
1134 
                        else /* sub - add joining */ if (ii->index == II_SUB
1135 
                                                         && prev->index ==
1136 
                                                         II_ADD)
1137 
                          {
1138 
                            ii->op[1] = prev->op[1];
1139 
                            ii->opt[1] = prev->opt[1];
1140 
                            ii->op[2] += prev->op[2];
1141 
                            modified = 1;
1142 
                            cucdebug (2, "%8x: sub-add\n", REF (b, i));
1143 
                          }
1144 
                        else /* add - sfxx joining */ if (prev->index ==
1145 
                                                          II_ADD && (
1146 
                                                                       ii->
1147 
                                                                       index
1148 
                                                                       ==
1149 
                                                                       II_SFEQ
1150 
                                                                       || ii->
1151 
                                                                       index
1152 
                                                                       ==
1153 
                                                                       II_SFNE
1154 
                                                                       || ii->
1155 
                                                                       index
1156 
                                                                       ==
1157 
                                                                       II_SFLT
1158 
                                                                       || ii->
1159 
                                                                       index
1160 
                                                                       ==
1161 
                                                                       II_SFLE
1162 
                                                                       || ii->
1163 
                                                                       index
1164 
                                                                       ==
1165 
                                                                       II_SFGT
1166 
                                                                       || ii->
1167 
                                                                       index
1168 
                                                                       ==
1169 
                                                                       II_SFGE))
1170 
                          {
1171 
                            if (ii->opt[2] & OPT_CONST
1172 
                                && ii->op[2] < 0x80000000)
1173 
                              {
1174 
                                ii->op[1] = prev->op[1];
1175 
                                ii->opt[1] = prev->opt[1];
1176 
                                ii->op[2] -= prev->op[2];
1177 
                                modified = 1;
1178 
                                cucdebug (2, "%8x: add-sfxx\n", REF (b, i));
1179 
                              }
1180 
                          }
1181 
                        else /* sub - sfxx joining */ if (prev->index ==
1182 
                                                          II_SUB && (
1183 
                                                                       ii->
1184 
                                                                       index
1185 
                                                                       ==
1186 
                                                                       II_SFEQ
1187 
                                                                       || ii->
1188 
                                                                       index
1189 
                                                                       ==
1190 
                                                                       II_SFNE
1191 
                                                                       || ii->
1192 
                                                                       index
1193 
                                                                       ==
1194 
                                                                       II_SFLT
1195 
                                                                       || ii->
1196 
                                                                       index
1197 
                                                                       ==
1198 
                                                                       II_SFLE
1199 
                                                                       || ii->
1200 
                                                                       index
1201 
                                                                       ==
1202 
                                                                       II_SFGT
1203 
                                                                       || ii->
1204 
                                                                       index
1205 
                                                                       ==
1206 
                                                                       II_SFGE))
1207 
                          {
1208 
                            if (ii->opt[2] & OPT_CONST
1209 
                                && ii->op[2] < 0x80000000)
1210 
                              {
1211 
                                ii->op[1] = prev->op[1];
1212 
                                ii->opt[1] = prev->opt[1];
1213 
                                ii->op[2] += prev->op[2];
1214 
                                modified = 1;
1215 
                                cucdebug (2, "%8x: sub-sfxx\n", REF (b, i));
1216 
                              }
1217 
                          }
1218 
                      }
1219 
                  }
1220 
              }
1221 
          }
1222 
      if (modified)
1223 
        gmodified = 1;
1224 897 markom 
    }
1225 1748 jeremybenn 
  while (modified);
1226 931 markom 
  return gmodified;
1227 897 markom 
}
1228 
 
1229 
/* Remove nop instructions */
1230 1748 jeremybenn 
int
1231 
remove_nops (cuc_func * f)
1232 897 markom 
{
1233 
  int b;
1234 931 markom 
  int modified = 0;
1235 1748 jeremybenn 
  for (b = 0; b < f->num_bb; b++)
1236 
    {
1237 
      int c, d = 0, i, j;
1238 
      cuc_insn *insn = f->bb[b].insn;
1239 
      for (i = 0; i < f->bb[b].ninsn; i++)
1240 
        if (insn[i].index != II_NOP)
1241 
          {
1242 
            reloc[i] = d;
1243 
            insn[d++] = insn[i];
1244 
          }
1245 
        else
1246 
          {
1247 
            reloc[i] = d;       /* For jumps only */
1248 
          }
1249 
      if (f->bb[b].ninsn != d)
1250 
        modified = 1;
1251 
      f->bb[b].ninsn = d;
1252 
 
1253 
      /* Relocate references from all basic blocks */
1254 
      for (c = 0; c < f->num_bb; c++)
1255 
        for (i = 0; i < f->bb[c].ninsn; i++)
1256 
          {
1257 
            dep_list *d = f->bb[c].insn[i].dep;
1258 
            for (j = 0; j < MAX_OPERANDS; j++)
1259 
              if ((f->bb[c].insn[i].opt[j] & OPT_REF)
1260 
                  && REF_BB (f->bb[c].insn[i].op[j]) == b)
1261 
                f->bb[c].insn[i].op[j] =
1262 
                  REF (b, reloc[REF_I (f->bb[c].insn[i].op[j])]);
1263 
 
1264 
            while (d)
1265 
              {
1266 
                if (REF_BB (d->ref) == b)
1267 
                  d->ref = REF (b, reloc[REF_I (d->ref)]);
1268 
                d = d->next;
1269 
              }
1270 
          }
1271 
    }
1272 931 markom 
  return modified;
1273 897 markom 
}
1274 
 
1275 1748 jeremybenn 
static void
1276 
unmark_tree (cuc_func * f, int ref)
1277 932 markom 
{
1278 1748 jeremybenn 
  cuc_insn *ii = &f->INSN (ref);
1279 973 markom 
  cucdebug (5, "%x ", ref);
1280 1748 jeremybenn 
  if (ii->type & IT_UNUSED)
1281 
    {
1282 
      int j;
1283 
      ii->type &= ~IT_UNUSED;
1284 
      for (j = 0; j < MAX_OPERANDS; j++)
1285 
        if (ii->opt[j] & OPT_REF)
1286 
          unmark_tree (f, ii->op[j]);
1287 
    }
1288 932 markom 
}
1289 
 
1290 897 markom 
/* Remove unused assignments */
1291 1748 jeremybenn 
int
1292 
remove_dead (cuc_func * f)
1293 897 markom 
{
1294 1308 phoenix 
  int b, i;
1295 897 markom 
  for (b = 0; b < f->num_bb; b++)
1296 
    for (i = 0; i < f->bb[b].ninsn; i++)
1297 1748 jeremybenn 
      f->bb[b].insn[i].type |= IT_UNUSED;
1298 897 markom 
 
1299 932 markom 
  for (b = 0; b < f->num_bb; b++)
1300 1748 jeremybenn 
    for (i = 0; i < f->bb[b].ninsn; i++)
1301 
      {
1302 
        cuc_insn *ii = &f->bb[b].insn[i];
1303 
        if (ii->type & IT_VOLATILE || ii->type & IT_OUTPUT
1304 
            || (II_IS_LOAD (ii->index)
1305 
                && (f->memory_order == MO_NONE || f->memory_order == MO_WEAK))
1306 
            || II_IS_STORE (ii->index))
1307 
          {
1308 
            unmark_tree (f, REF (b, i));
1309 
            cucdebug (5, "\n");
1310 
          }
1311 932 markom 
      }
1312 1748 jeremybenn 
 
1313 897 markom 
  for (b = 0; b < f->num_bb; b++)
1314 
    for (i = 0; i < f->bb[b].ninsn; i++)
1315 1748 jeremybenn 
      if (f->bb[b].insn[i].type & IT_UNUSED)
1316 
        {
1317 
          change_insn_type (&f->bb[b].insn[i], II_NOP);
1318 
        }
1319 897 markom 
 
1320 931 markom 
  return remove_nops (f);
1321 897 markom 
}
1322 
 
1323 
/* Removes trivial register assignments */
1324 1748 jeremybenn 
int
1325 
remove_trivial_regs (cuc_func * f)
1326 897 markom 
{
1327 
  int b, i;
1328 1748 jeremybenn 
  for (i = 0; i < MAX_REGS; i++)
1329 
    f->saved_regs[i] = caller_saved[i];
1330 897 markom 
 
1331 1748 jeremybenn 
  for (b = 0; b < f->num_bb; b++)
1332 
    {
1333 
      cuc_insn *insn = f->bb[b].insn;
1334 
      for (i = 0; i < f->bb[b].ninsn; i++)
1335 
        {
1336 
          if (insn[i].index == II_ADD
1337 
              && insn[i].opt[0] & OPT_REGISTER
1338 
              && insn[i].opt[1] & OPT_REGISTER
1339 
              && insn[i].op[0] == insn[i].op[1] && insn[i].opt[2] & OPT_CONST
1340 
              && insn[i].op[2] == 0)
1341 
            {
1342 
              if (insn[i].type & IT_OUTPUT)
1343 
                f->saved_regs[insn[i].op[0]] = 1;
1344 
              change_insn_type (&insn[i], II_NOP);
1345 
            }
1346 
        }
1347 897 markom 
    }
1348 1748 jeremybenn 
  if (cuc_debug >= 2)
1349 
    {
1350 
      PRINTF ("saved regs ");
1351 
      for (i = 0; i < MAX_REGS; i++)
1352 
        PRINTF ("%i:%i ", i, f->saved_regs[i]);
1353 
      PRINTF ("\n");
1354 
    }
1355 931 markom 
  return remove_nops (f);
1356 897 markom 
}
1357 
 
1358 
/* Determine inputs and outputs */
1359 1748 jeremybenn 
void
1360 
set_io (cuc_func * f)
1361 897 markom 
{
1362 
  int b, i, j;
1363 
  /* Determine register usage */
1364 1748 jeremybenn 
  for (i = 0; i < MAX_REGS; i++)
1365 
    {
1366 
      f->lur[i] = -1;
1367 
      f->used_regs[i] = 0;
1368 
    }
1369 
  if (cuc_debug > 5)
1370 
    print_cuc_bb (f, "SET_IO");
1371 
  for (b = 0; b < f->num_bb; b++)
1372 
    {
1373 
      for (i = 0; i < f->bb[b].ninsn; i++)
1374 
        for (j = 0; j < MAX_OPERANDS; j++)
1375 
          if (f->bb[b].insn[i].opt[j] & OPT_REGISTER
1376 
              && f->bb[b].insn[i].op[j] >= 0)
1377 
            {
1378 
              if (f->bb[b].insn[i].opt[j] & OPT_DEST)
1379 
                f->lur[f->bb[b].insn[i].op[j]] = REF (b, i);
1380 
              else
1381 
                f->used_regs[f->bb[b].insn[i].op[j]] = 1;
1382 
            }
1383 
    }
1384 897 markom 
}
1385 
 
1386 
/* relocate all accesses inside of BB b to back/fwd */
1387 1557 nogj 
#if 0
1388 1748 jeremybenn 
static void
1389 
relocate_bb (cuc_bb * bb, int b, int back, int fwd)
1390 897 markom 
{
1391 
  int i, j;
1392 
  for (i = 0; i < bb->ninsn; i++)
1393 
    for (j = 0; j < MAX_OPERANDS; j++)
1394 1748 jeremybenn 
      if (bb->insn[i].opt[j] & OPT_REF && REF_BB (bb->insn[i].op[j]) == b)
1395 
        {
1396 
          int t = REF_I (bb->insn[i].op[j]);
1397 
          if (t < i)
1398 
            bb->insn[i].op[j] = REF (back, t);
1399 
          else
1400 
            bb->insn[i].op[j] = REF (fwd, t);
1401 
        }
1402 897 markom 
}
1403 1557 nogj 
#endif
1404 897 markom 
 
1405 
/* Latch outputs in loops */
1406 1748 jeremybenn 
void
1407 
add_latches (cuc_func * f)
1408 897 markom 
{
1409 
  int b, i, j;
1410 
 
1411 
  //print_cuc_bb (f, "ADD_LATCHES a");
1412 
  /* Cuts the tree and marks registers */
1413 
  mark_cut (f);
1414 
 
1415 
  /* Split BBs with more than one group */
1416 1748 jeremybenn 
  for (b = 0; b < f->num_bb; b++)
1417 
    expand_bb (f, b);
1418 897 markom 
  remove_nops (f);
1419 
  //print_cuc_bb (f, "ADD_LATCHES 0");
1420 
 
1421 
  /* Convert accesses in BB_INLOOP type block to latched */
1422 1748 jeremybenn 
  for (b = 0; b < f->num_bb; b++)
1423 
    {
1424 
      int j;
1425 
      for (i = 0; i < f->bb[b].ninsn; i++)
1426 
        for (j = 0; j < MAX_OPERANDS; j++)
1427 
          if (f->bb[b].insn[i].opt[j] == OPT_REF)
1428 
            {
1429 
              int t = f->bb[b].insn[i].op[j];
1430 
              /* If we are pointing to a INLOOP block from outside, or forward
1431 
                 (= previous loop iteration) we must register that data */
1432 
              if ((f->bb[REF_BB (t)].type & BB_INLOOP
1433 
                   || config.cuc.no_multicycle)
1434 
                  && !(f->INSN (t).type & (IT_BRANCH | IT_COND))
1435 
                  && (REF_BB (t) != b || REF_I (t) >= i))
1436 
                {
1437 
                  f->INSN (t).type |= IT_LATCHED;
1438 
                }
1439 
            }
1440 
    }
1441 897 markom 
  //print_cuc_bb (f, "ADD_LATCHES 1");
1442 
 
1443 
  /* Add latches at the end of blocks as needed */
1444 1748 jeremybenn 
  for (b = 0; b < f->num_bb; b++)
1445 
    {
1446 
      int nreg = 0;
1447 
      cuc_insn *insn;
1448 
      for (i = 0; i < f->bb[b].ninsn; i++)
1449 
        if (f->bb[b].insn[i].type & IT_LATCHED)
1450 
          nreg++;
1451 
      if (nreg)
1452 
        {
1453 
          insn =
1454 
            (cuc_insn *) malloc (sizeof (cuc_insn) * (f->bb[b].ninsn + nreg));
1455 
          j = 0;
1456 
          for (i = 0; i < f->bb[b].ninsn; i++)
1457 
            {
1458 
              insn[i] = f->bb[b].insn[i];
1459 
              if (insn[i].type & IT_LATCHED)
1460 
                {
1461 
                  cuc_insn *ii = &insn[f->bb[b].ninsn + j++];
1462 
                  change_insn_type (ii, II_REG);
1463 
                  ii->op[0] = -1;
1464 
                  ii->opt[0] = OPT_DEST | OPT_REGISTER;
1465 
                  ii->op[1] = REF (b, i);
1466 
                  ii->opt[1] = OPT_REF;
1467 
                  ii->opt[2] = ii->opt[3] = OPT_NONE;
1468 
                  ii->dep = NULL;
1469 
                  ii->type = IT_VOLATILE;
1470 
                  sprintf (ii->disasm, "reg %i_%i", b, i);
1471 
                }
1472 
            }
1473 
          f->bb[b].ninsn += nreg;
1474 
          free (f->bb[b].insn);
1475 
          f->bb[b].insn = insn;
1476 
        }
1477 897 markom 
    }
1478 
  //print_cuc_bb (f, "ADD_LATCHES 2");
1479 
 
1480 
  /* Repair references */
1481 
  for (b = 0; b < f->num_bb; b++)
1482 
    for (i = 0; i < f->bb[b].ninsn; i++)
1483 
      for (j = 0; j < MAX_OPERANDS; j++)
1484 1748 jeremybenn 
        /* If destination instruction is latched, use register instead */
1485 
        if (f->bb[b].insn[i].opt[j] == OPT_REF
1486 
            && f->INSN (f->bb[b].insn[i].op[j]).type & IT_LATCHED)
1487 
          {
1488 
            int b1, i1;
1489 
            b1 = REF_BB (f->bb[b].insn[i].op[j]);
1490 
            //cucdebug (2, "%i.%i.%i %x\n", b, i, j, f->bb[b].insn[i].op[j]);
1491 
            if (b1 != b || REF_I (f->bb[b].insn[i].op[j]) >= i)
1492 
              {
1493 
                for (i1 = f->bb[b1].ninsn - 1; i1 >= 0; i1--)
1494 
                  {
1495 
                    assert (f->bb[b1].insn[i1].index == II_REG);
1496 
                    if (f->bb[b1].insn[i1].op[1] == f->bb[b].insn[i].op[j])
1497 
                      {
1498 
                        f->bb[b].insn[i].op[j] = REF (b1, i1);
1499 
                        break;
1500 
                      }
1501 
                  }
1502 
              }
1503 
          }
1504 897 markom 
}
1505 
 
1506 883 markom 
/* CSE -- common subexpression elimination */
1507 1748 jeremybenn 
int
1508 
cse (cuc_func * f)
1509 883 markom 
{
1510 931 markom 
  int modified = 0;
1511 1308 phoenix 
  int b, i, j, b1, i1, b2, i2;
1512 883 markom 
  for (b1 = 0; b1 < f->num_bb; b1++)
1513 1748 jeremybenn 
    for (i1 = 0; i1 < f->bb[b1].ninsn; i1++)
1514 
      if (f->bb[b1].insn[i1].index != II_NOP
1515 
          && f->bb[b1].insn[i1].index != II_LRBB
1516 
          && !(f->bb[b1].insn[i1].type & IT_MEMORY)
1517 
          && !(f->bb[b1].insn[i1].type & IT_MEMADD))
1518 
        for (b2 = 0; b2 < f->num_bb; b2++)
1519 
          for (i2 = 0; i2 < f->bb[b2].ninsn; i2++)
1520 
            if (f->bb[b2].insn[i2].index != II_NOP
1521 
                && f->bb[b2].insn[i2].index != II_LRBB
1522 
                && !(f->bb[b2].insn[i2].type & IT_MEMORY)
1523 
                && !(f->bb[b2].insn[i2].type & IT_MEMADD) && (b1 != b2
1524 
                                                              || i2 > i1))
1525 
              {
1526 
                cuc_insn *ii1 = &f->bb[b1].insn[i1];
1527 
                cuc_insn *ii2 = &f->bb[b2].insn[i2];
1528 
                int ok = 1;
1529 883 markom 
 
1530 1748 jeremybenn 
                /* Do we have an exact match? */
1531 
                if (ii1->index != ii2->index)
1532 
                  continue;
1533 
                if (ii2->type & IT_VOLATILE)
1534 
                  continue;
1535 930 markom 
 
1536 1748 jeremybenn 
                /* Check all operands also */
1537 
                for (j = 0; j < MAX_OPERANDS; j++)
1538 
                  {
1539 
                    if (ii1->opt[j] != ii2->opt[j])
1540 
                      {
1541 
                        ok = 0;
1542 
                        break;
1543 
                      }
1544 
                    if (ii1->opt[j] & OPT_DEST)
1545 
                      continue;
1546 
                    if (ii1->opt[j] != OPT_NONE && ii1->op[j] != ii2->op[j])
1547 
                      {
1548 
                        ok = 0;
1549 
                        break;
1550 
                      }
1551 
                  }
1552 
 
1553 
                if (ok)
1554 
                  {
1555 
                    /* remove duplicated instruction and relink the references */
1556 
                    cucdebug (3, "%x - %x are same\n", REF (b1, i1),
1557 
                              REF (b2, i2));
1558 
                    change_insn_type (ii2, II_NOP);
1559 
                    modified = 1;
1560 
                    for (b = 0; b < f->num_bb; b++)
1561 
                      for (i = 0; i < f->bb[b].ninsn; i++)
1562 
                        for (j = 0; j < MAX_OPERANDS; j++)
1563 
                          if (f->bb[b].insn[i].opt[j] & OPT_REF
1564 
                              && f->bb[b].insn[i].op[j] == REF (b2, i2))
1565 
                            f->bb[b].insn[i].op[j] = REF (b1, i1);
1566 
                  }
1567 
              }
1568 931 markom 
  return modified;
1569 883 markom 
}
1570 
 
1571 1748 jeremybenn 
static int
1572 
count_cmovs (cuc_insn * ii, int match)
1573 883 markom 
{
1574 
  int c = 0, j;
1575 1748 jeremybenn 
  if (match & 2)
1576 
    {
1577 
      for (j = 0; j < MAX_OPERANDS; j++)
1578 
        if (ii->opt[j] & OPT_DEST)
1579 
          c++;
1580 
    }
1581 
  if (match & 1)
1582 
    {
1583 
      for (j = 0; j < MAX_OPERANDS; j++)
1584 
        if (!(ii->opt[j] & OPT_DEST) && ii->opt[j] & OPT_REF)
1585 
          c++;
1586 
    }
1587 
  else
1588 
    {
1589 
      for (j = 0; j < MAX_OPERANDS; j++)
1590 
        if (!(ii->opt[j] & OPT_DEST) && ii->opt[j] != OPT_NONE)
1591 
          c++;
1592 
    }
1593 883 markom 
  return c;
1594 
}
1595 
 
1596 1748 jeremybenn 
static void search_csm (int iter, cuc_func * f, cuc_shared_list * list);
1597 897 markom 
static cuc_shared_list *main_list;
1598 883 markom 
static int *iteration;
1599 
 
1600 897 markom 
/* CSM -- common subexpression matching -- resource sharing
1601 
   We try to match tree of instruction inside a BB with as many
1602 
   matches as possible. All possibilities are collected and
1603 
   options, making situation worse are removed */
1604 1748 jeremybenn 
void
1605 
csm (cuc_func * f)
1606 883 markom 
{
1607 
  int b, i, j;
1608 
  int cnt;
1609 897 markom 
  cuc_shared_list *list;
1610 883 markom 
  cuc_timings timings;
1611 
 
1612 
  analyse_timings (f, &timings);
1613 
  main_list = NULL;
1614 1748 jeremybenn 
  for (b = 0; b < f->num_bb; b++)
1615 
    {
1616 
      assert (iteration = (int *) malloc (sizeof (int) * f->bb[b].ninsn));
1617 
      for (i = 0; i < f->bb[b].ninsn; i++)
1618 
        {
1619 
          int cnt = 0, cntc = 0;
1620 
          double size = 0., sizec = 0.;
1621 
          int j2 = 0;
1622 
          for (j = 0; j < f->bb[b].ninsn; j++)
1623 
            if (f->bb[b].insn[i].index == f->bb[b].insn[j].index)
1624 
              {
1625 
                int ok = 1;
1626 
                for (j2 = 0; j2 < MAX_OPERANDS; j2++)
1627 
                  if (!(f->bb[b].insn[j].opt[j2] & OPT_REF))
1628 
                    if (f->bb[b].insn[j].opt[j2] != f->bb[b].insn[i].opt[j2]
1629 
                        || f->bb[b].insn[j].op[j2] !=
1630 
                        f->bb[b].insn[i].opt[j2])
1631 
                      {
1632 
                        ok = 0;
1633 
                        break;
1634 
                      }
1635 
                if (ok)
1636 
                  {
1637 
                    cntc++;
1638 
                    sizec = sizec + insn_size (&f->bb[b].insn[j]);
1639 
                  }
1640 
                else
1641 
                  {
1642 
                    cnt++;
1643 
                    size = size + insn_size (&f->bb[b].insn[j]);
1644 
                  }
1645 
                iteration[j] = 0;
1646 
              }
1647 
            else
1648 
              iteration[j] = -1;
1649 
          if (cntc > 1)
1650 
            {
1651 
              assert (list =
1652 
                      (cuc_shared_list *) malloc (sizeof (cuc_shared_list)));
1653 
              list->next = main_list;
1654 
              list->from = NULL;
1655 
              list->ref = REF (b, i);
1656 
              list->cnt = cnt;
1657 
              list->cmatch = 1;
1658 
              list->cmovs = count_cmovs (&f->bb[b].insn[i], 3);
1659 
              list->osize = sizec;
1660 
              list->size = ii_size (f->bb[b].insn[i].index, 1);
1661 
              main_list = list;
1662 
              search_csm (0, f, list);
1663 
            }
1664 
          if (cnt > 1)
1665 
            {
1666 
              assert (list =
1667 
                      (cuc_shared_list *) malloc (sizeof (cuc_shared_list)));
1668 
              list->next = main_list;
1669 
              list->from = NULL;
1670 
              list->ref = REF (b, i);
1671 
              list->cnt = cnt + cntc;
1672 
              list->cmatch = 0;
1673 
              list->cmovs = count_cmovs (&f->bb[b].insn[i], 2);
1674 
              list->osize = size + sizec;
1675 
              list->size = ii_size (f->bb[b].insn[i].index, 0);
1676 
              main_list = list;
1677 
              search_csm (0, f, list);
1678 
            }
1679 
        }
1680 
      free (iteration);
1681 883 markom 
    }
1682 1748 jeremybenn 
 
1683 
  for (list = main_list; list; list = list->next)
1684 
    list->dead = 0;
1685 883 markom 
  cnt = 0;
1686 1748 jeremybenn 
  for (list = main_list; list; list = list->next)
1687 
    if (!list->dead)
1688 
      cnt++;
1689 883 markom 
  cucdebug (1, "noptions = %i\n", cnt);
1690 1748 jeremybenn 
 
1691 883 markom 
  /* Now we will check the real size of the 'improvements'; if the size
1692 
     actually increases, we abandom the option */
1693 
  for (list = main_list; list; list = list->next)
1694 1748 jeremybenn 
    if (list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size >=
1695 
        list->osize)
1696 
      list->dead = 1;
1697 
 
1698 883 markom 
  cnt = 0;
1699 1748 jeremybenn 
  for (list = main_list; list; list = list->next)
1700 
    if (!list->dead)
1701 
      cnt++;
1702 883 markom 
  cucdebug (1, "noptions = %i\n", cnt);
1703 
 
1704 
  /* Count number of instructions grouped */
1705 1748 jeremybenn 
  for (list = main_list; list; list = list->next)
1706 
    {
1707 
      cuc_shared_list *l = list;
1708 
      int c = 0;
1709 
      while (l)
1710 
        {
1711 
          c++;
1712 
          if (f->INSN (l->ref).type & (IT_VOLATILE | IT_MEMORY | IT_MEMADD))
1713 
            list->dead = 1;
1714 
          l = l->from;
1715 
        }
1716 
      list->ninsn = c;
1717 883 markom 
    }
1718 
 
1719 
  cnt = 0;
1720 
  for (list = main_list; list; list = list->next)
1721 1748 jeremybenn 
    if (!list->dead)
1722 
      cnt++;
1723 883 markom 
  cucdebug (1, "noptions = %i\n", cnt);
1724 
 
1725 
#if 1
1726 
  /* We can get a lot of options here, so we will delete duplicates */
1727 1748 jeremybenn 
  for (list = main_list; list; list = list->next)
1728 
    if (!list->dead)
1729 
      {
1730 
        cuc_shared_list *l;
1731 
        for (l = list->next; l; l = l->next)
1732 
          if (!l->dead)
1733 
            {
1734 
              int ok = 1;
1735 
              cuc_shared_list *t1 = list;
1736 
              cuc_shared_list *t2 = l;
1737 
              while (ok && t1 && t2)
1738 
                {
1739 
                  if (f->INSN (t1->ref).index == f->INSN (t2->ref).index)
1740 
                    {
1741 
                      /* If other operands are matching, we must check for them also */
1742 
                      if (t1->cmatch)
1743 
                        {
1744 
                          int j;
1745 
                          for (j = 0; j < MAX_OPERANDS; j++)
1746 
                            if (!(f->INSN (t1->ref).opt[j] & OPT_REF)
1747 
                                || !(f->INSN (t2->ref).opt[j] & OPT_REF)
1748 
                                || f->INSN (t1->ref).opt[j] !=
1749 
                                f->INSN (t2->ref).opt[j]
1750 
                                || f->INSN (t1->ref).op[j] !=
1751 
                                f->INSN (t2->ref).op[j])
1752 
                              {
1753 
                                ok = 0;
1754 
                                break;
1755 
                              }
1756 
                        }
1757 
 
1758 
                      /* This option is duplicate, remove */
1759 
                      if (ok)
1760 
                        t1->dead = 1;
1761 
                    }
1762 
                  t1 = t1->from;
1763 
                  t2 = t2->from;
1764 
                }
1765 
            }
1766 883 markom 
      }
1767 
  cnt = 0;
1768 1748 jeremybenn 
  for (list = main_list; list; list = list->next)
1769 
    if (!list->dead)
1770 
      cnt++;
1771 883 markom 
  cucdebug (1, "noptions = %i\n", cnt);
1772 
#endif
1773 
  /* Print out */
1774 1748 jeremybenn 
  for (list = main_list; list; list = list->next)
1775 
    if (!list->dead)
1776 
      {
1777 
        cuc_shared_list *l = list;
1778 
        cucdebug (1,
1779 
                  "%-4s cnt %3i ninsn %3i size %8.1f osize %8.1f cmovs %3i @",
1780 
                  cuc_insn_name (&f->INSN (list->ref)), list->cnt,
1781 
                  list->ninsn, list->cmovs * ii_size (II_CMOV,
1782 
                                                      0) * (list->cnt - 1) +
1783 
                  list->size, list->osize, list->cmovs);
1784 
        while (l)
1785 
          {
1786 
            cucdebug (1, "%c%x,", l->cmatch ? '.' : '!', l->ref);
1787 
            l = l->from;
1788 
          }
1789 
        cucdebug (1, "\n");
1790 
      }
1791 883 markom 
 
1792 
  /* Calculate estimated timings */
1793 1748 jeremybenn 
  for (b = 0; b < f->num_bb; b++)
1794 
    {
1795 
      cnt = 0;
1796 
      for (list = main_list; list; list = list->next)
1797 
        if (!list->dead && REF_BB (list->ref) == b)
1798 
          cnt++;
1799 
 
1800 
      f->bb[b].ntim = cnt;
1801 
      if (!cnt)
1802 
        {
1803 
          f->bb[b].tim = NULL;
1804 
          continue;
1805 
        }
1806 
      assert (f->bb[b].tim =
1807 
              (cuc_timings *) malloc (sizeof (cuc_timings) * cnt));
1808 
 
1809 
      cnt = 0;
1810 
      for (list = main_list; list; list = list->next)
1811 
        if (!list->dead && REF_BB (list->ref) == b)
1812 
          {
1813 
            cuc_shared_list *l = list;
1814 
            f->bb[b].tim[cnt].b = b;
1815 
            f->bb[b].tim[cnt].preroll = f->bb[b].tim[cnt].unroll = 1;
1816 
            f->bb[b].tim[cnt].nshared = list->ninsn;
1817 
            assert (f->bb[b].tim[cnt].shared = (cuc_shared_item *)
1818 
                    malloc (sizeof (cuc_shared_item) * list->ninsn));
1819 
            for (i = 0; i < list->ninsn; i++, l = l->from)
1820 
              {
1821 
                f->bb[b].tim[cnt].shared[i].ref = l->ref;
1822 
                f->bb[b].tim[cnt].shared[i].cmatch = l->cmatch;
1823 
              }
1824 
            f->bb[b].tim[cnt].new_time =
1825 
              timings.new_time + f->bb[b].cnt * (list->cnt - 1);
1826 
            f->bb[b].tim[cnt].size =
1827 
              timings.size + list->cmovs * ii_size (II_CMOV,
1828 
                                                    0) * (list->cnt - 1) +
1829 
              list->size - list->osize;
1830 
            cnt++;
1831 
          }
1832 883 markom 
    }
1833 
}
1834 
 
1835 
/* Recursive function for searching through instruction graph */
1836 1748 jeremybenn 
static void
1837 
search_csm (int iter, cuc_func * f, cuc_shared_list * list)
1838 883 markom 
{
1839 
  int b, i, j, i1;
1840 897 markom 
  cuc_shared_list *l;
1841 1748 jeremybenn 
  b = REF_BB (list->ref);
1842 
  i = REF_I (list->ref);
1843 883 markom 
 
1844 1748 jeremybenn 
  for (j = 0; j < MAX_OPERANDS; j++)
1845 
    if (f->bb[b].insn[i].opt[j] & OPT_REF)
1846 
      {
1847 
        int t = f->bb[b].insn[i].op[j];
1848 
        int cnt = 0, cntc = 0;
1849 
        double size = 0., sizec = 0.;
1850 883 markom 
 
1851 1748 jeremybenn 
        /* Mark neighbours */
1852 
        for (i1 = 0; i1 < f->bb[b].ninsn; i1++)
1853 
          {
1854 
            if (iteration[i1] == iter && f->bb[b].insn[i1].opt[j] & OPT_REF)
1855 
              {
1856 
                int t2 = f->bb[b].insn[i1].op[j];
1857 
                if (f->INSN (t).index == f->INSN (t2).index
1858 
                    && f->INSN (t2).opt[j] & OPT_REF)
1859 
                  {
1860 
                    int j2;
1861 
                    int ok = 1;
1862 
                    iteration[REF_I (t2)] = iter + 1;
1863 
                    for (j2 = 0; j2 < MAX_OPERANDS; j2++)
1864 
                      if (!(f->bb[b].insn[i1].opt[j2] & OPT_REF))
1865 
                        if (f->bb[b].insn[i1].opt[j2] !=
1866 
                            f->bb[b].insn[i].opt[j2]
1867 
                            || f->bb[b].insn[i1].op[j2] !=
1868 
                            f->bb[b].insn[i].opt[j2])
1869 
                          {
1870 
                            ok = 0;
1871 
                            break;
1872 
                          }
1873 
                    if (ok)
1874 
                      {
1875 
                        cntc++;
1876 
                        sizec = sizec + insn_size (&f->bb[b].insn[i1]);
1877 
                      }
1878 
                    else
1879 
                      {
1880 
                        cnt++;
1881 
                        size = size + insn_size (&f->bb[b].insn[i1]);
1882 
                      }
1883 
                  }
1884 
              }
1885 
          }
1886 883 markom 
 
1887 1748 jeremybenn 
        if (cntc > 1)
1888 
          {
1889 
            assert (l =
1890 
                    (cuc_shared_list *) malloc (sizeof (cuc_shared_list)));
1891 
            l->next = main_list;
1892 
            main_list = l;
1893 
            l->from = list;
1894 
            l->ref = t;
1895 
            l->cnt = cnt;
1896 
            l->cmatch = 1;
1897 
            l->cmovs = list->cmovs + count_cmovs (&f->bb[b].insn[i], 1) - 1;
1898 
            l->size = list->size + ii_size (f->bb[b].insn[i].index, 1);
1899 
            l->osize = sizec;
1900 
            search_csm (iter + 1, f, l);
1901 
          }
1902 
        if (cnt > 1)
1903 
          {
1904 
            assert (l =
1905 
                    (cuc_shared_list *) malloc (sizeof (cuc_shared_list)));
1906 
            l->next = main_list;
1907 
            main_list = l;
1908 
            l->from = list;
1909 
            l->ref = t;
1910 
            l->cnt = cnt + cntc;
1911 
            l->cmatch = 0;
1912 
            l->osize = size + sizec;
1913 
            l->cmovs = list->cmovs + count_cmovs (&f->bb[b].insn[i], 0) - 1;
1914 
            l->size = list->size + ii_size (f->bb[b].insn[i].index, 0);
1915 
            search_csm (iter + 1, f, l);
1916 
          }
1917 
 
1918 
        /* Unmark them back */
1919 
        for (i1 = 0; i1 < f->bb[b].ninsn; i1++)
1920 
          if (iteration[i1] > iter)
1921 
            iteration[i1] = -1;
1922 
      }
1923 883 markom 
}
1924 
 
1925 897 markom 
/* Displays shared instructions */
1926 1748 jeremybenn 
void
1927 
print_shared (cuc_func * rf, cuc_shared_item * shared, int nshared)
1928 897 markom 
{
1929 
  int i, first = 1;
1930 1748 jeremybenn 
  for (i = 0; i < nshared; i++)
1931 
    {
1932 
      PRINTF ("%s%s%s", first ? "" : "-",
1933 
              cuc_insn_name (&rf->INSN (shared[i].ref)),
1934 
              shared[i].cmatch ? "!" : "");
1935 
      first = 0;
1936 
    }
1937 897 markom 
}
1938 
 
1939 
/* Common subexpression matching -- resource sharing, generation pass
1940 
 
1941 
   Situation here is much simpler than with analysis -- we know the instruction sequence
1942 
   we are going to share, but we are going to do this on whole function, not just one BB.
1943 
   We can find sequence in reference function, as pointed from "shared" */
1944 1748 jeremybenn 
void
1945 
csm_gen (cuc_func * f, cuc_func * rf, cuc_shared_item * shared, int nshared)
1946 897 markom 
{
1947 1308 phoenix 
  int b, i, cnt = 0;
1948 1557 nogj 
  /* FIXME: some code here (2) */
1949 997 markom 
  PRINTF ("Replacing: ");
1950 897 markom 
  print_shared (rf, shared, nshared);
1951 1748 jeremybenn 
 
1952 897 markom 
  for (b = 0; b < f->num_bb; b++)
1953 1748 jeremybenn 
    for (i = 0; i < f->bb[b].ninsn; i++)
1954 
      {
1955 
      }
1956 
 
1957 997 markom 
  PRINTF ("\nFound %i matches.\n", cnt);
1958 897 markom 
}

powered by: WebSVN 2.1.0

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