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

Subversion Repositories or1k

[/] [or1k/] [tags/] [nog_patch_68/] [or1ksim/] [cuc/] [insn.c] - Blame information for rev 953

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 937 markom 
{"nop", 1, ""},
62 917 markom 
{"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 937 markom 
    i->disasm[0] = '\0';
75 879 markom 
  }
76 
}
77 
 
78 
/* Returns instruction name */
79 
const char *cuc_insn_name (cuc_insn *ii) {
80 
  if (ii->index < 0 || ii->index > II_LAST) return "???";
81 
  else return known[ii->index].name;
82 
}
83 883 markom 
 
84 897 markom 
/* Prints out instructions */
85 
void print_insns (cuc_insn *insn, int ninsn, int verbose)
86 
{
87 
  int i, j;
88 
  for (i = 0; i < ninsn; i++) {
89 
    dep_list *l = insn[i].dep;
90 
    printf ("%4x%c %-4s ", i, insn[i].index >= 0 ? ':' : '?', cuc_insn_name (&insn[i]));
91 
    if (verbose) {
92 
      printf ("%-20s insn = %08x, index = %i, type = %04x ",
93 
                      insn[i].disasm, insn[i].insn, insn[i].index, insn[i].type);
94 937 markom 
    } else printf ("type = %04x ", insn[i].type);
95 897 markom 
    for (j = 0; j < MAX_OPERANDS; j++) {
96 
      if (insn[i].opt[j] & OPT_DEST) printf ("*");
97 
      switch (insn[i].opt[j] & ~OPT_DEST) {
98 
        case OPT_NONE: break;
99 937 markom 
        case OPT_CONST: if (insn[i].type & IT_COND && (insn[i].index == II_CMOV
100 
                         || insn[i].index == II_ADD)) printf ("%x, ", insn[i].op[j]);
101 
                        else printf ("0x%08x, ", insn[i].op[j]); break;
102 897 markom 
        case OPT_JUMP: printf ("J%x ", insn[i].op[j]); break;
103 
        case OPT_REGISTER: printf ("r%i, ", insn[i].op[j]); break;
104 
        case OPT_REF: printf ("[%x.%x], ", REF_BB(insn[i].op[j]), REF_I(insn[i].op[j])); break;
105 925 markom 
        case OPT_BB: printf ("BB "); print_bb_num (insn[i].op[j]); printf (", "); break;
106 897 markom 
        case OPT_LRBB: printf ("LRBB, "); break;
107 
        default:
108 
          fprintf (stderr, "Invalid operand type %s(%x.%x) = %x\n",
109 
                         cuc_insn_name (&insn[i]), i, j, insn[i].opt[j]);
110 
          assert (0);
111 
      }
112 
    }
113 
    if (l) {
114 
      printf ("\n\tdep:");
115 
      while (l) {
116 
        printf (" [%x.%x],", REF_BB (l->ref), REF_I (l->ref));
117 
        l = l->next;
118 
      }
119 
    }
120 
    printf ("\n");
121 
  }
122 
}
123 
 
124 
void add_dep (dep_list **list, int dep)
125 
{
126 
  dep_list *ndep;
127 
  dep_list **tmp = list;
128 
 
129 
  while (*tmp) {
130 
    if ((*tmp)->ref == dep) return; /* already there */
131 
    tmp = &((*tmp)->next);
132 
  }
133 
  ndep = (dep_list *)malloc (sizeof (dep_list));
134 
  ndep->ref = dep;
135 
  ndep->next = NULL;
136 
  *tmp = ndep;
137 
}
138 
 
139 
void dispose_list (dep_list **list)
140 
{
141 
  while (*list) {
142 
    dep_list *tmp = *list;
143 
    *list = tmp->next;
144 
    free (tmp);
145 
  }
146 
}
147 
 
148 
void add_data_dep (cuc_func *f)
149 
{
150 
  int b, i, j;
151 
  dep_list *tmp;
152 
  for (b = 0; b < f->num_bb; b++) {
153 
    cuc_insn *insn = f->bb[b].insn;
154 
    for (i = 0; i < f->bb[b].ninsn; i++)
155 
      for (j = 0; j < MAX_OPERANDS; j++) {
156 
        fflush (stdout);
157 
        if (insn[i].opt[j] & OPT_REF) {
158 
          /* Copy list from predecessor */
159 
          dep_list *l = f->INSN(insn[i].op[j]).dep;
160 
          while (l) {
161 
            add_dep (&insn[i].dep, l->ref);
162 
            l = l->next;
163 
          }
164 
          /* add predecessor */
165 
          add_dep (&insn[i].dep, insn[i].op[j]);
166 
        }
167 
      }
168 
  }
169 
}
170 
 
171 953 markom 
/* Inserts n nops before insn 'ref' */
172 
void insert_insns (cuc_func *f, int ref, int n)
173 
{
174 
  int b1, i, j;
175 
  int b = REF_BB(ref);
176 
  int ins = REF_I(ref);
177 
 
178 
  assert (b < f->num_bb);
179 
  assert (ins <= f->bb[b].ninsn);
180 
  assert (f->bb[b].ninsn + n < MAX_INSNS);
181 
  print_cuc_bb (f, "PREINSERT");
182 
  f->bb[b].insn = (cuc_insn *) realloc (f->bb[b].insn,
183 
                                        (f->bb[b].ninsn + n) * sizeof (cuc_insn));
184 
 
185 
  /* Set up relocations */
186 
  for (i = 0; i < f->bb[b].ninsn; i++)
187 
    if (i < ins) reloc[i] = i;
188 
    else reloc[i] = i + n;
189 
 
190 
  /* Move instructions, based on relocations */
191 
  for (i = f->bb[b].ninsn - 1; i >= 0; i--) f->bb[b].insn[reloc[i]] = f->bb[b].insn[i];
192 
  for (i = 0; i < n; i++) change_insn_type (&f->bb[b].insn[ins + i], II_NOP);
193 
 
194 
  f->bb[b].ninsn += n;
195 
  for (b1 = 0; b1 < f->num_bb; b1++) {
196 
    dep_list *d = f->bb[b1].mdep;
197 
    while (d) {
198 
      if (REF_BB (d->ref) == b && REF_I (d->ref) >= ins)
199 
        d->ref = REF (b, REF_I (d->ref) + n);
200 
      d = d->next;
201 
    }
202 
    for (i = 0; i < f->bb[b1].ninsn; i++) {
203 
      d = f->bb[b1].insn[i].dep;
204 
      while (d) {
205 
        if (REF_BB (d->ref) == b && REF_I (d->ref) >= ins)
206 
          d->ref = REF (b, REF_I (d->ref) + n);
207 
        d = d->next;
208 
      }
209 
      for (j = 0; j < MAX_OPERANDS; j++)
210 
        if (f->bb[b1].insn[i].opt[j] & OPT_REF && REF_BB (f->bb[b1].insn[i].op[j]) == b
211 
         && REF_I (f->bb[b1].insn[i].op[j]) >= ins)
212 
          f->bb[b1].insn[i].op[j] = REF (b, REF_I (f->bb[b1].insn[i].op[j]) + n);
213 
    }
214 
  }
215 
  for (i = 0; i < f->nmsched; i++)
216 
    if (REF_BB(f->msched[i]) == b) f->msched[i] = REF (b, reloc[REF_I (f->msched[i])]);
217 
  print_cuc_bb (f, "POSTINSERT");
218 
  cuc_check (f);
219 
}
220 
 
221 897 markom 
/* returns nonzero, if instruction was simplified */
222 
int apply_edge_condition (cuc_insn *ii)
223 
{
224 
  unsigned int c = ii->op[2];
225 
 
226 931 markom 
  switch (ii->index) {
227 
  case II_AND:
228 897 markom 
    if (ii->opt[2] & OPT_CONST && c == 0) {
229 
      change_insn_type (ii, II_ADD);
230 
      ii->op[1] = 0; ii->opt[1] = OPT_CONST;
231 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
232 
      return 1;
233 932 markom 
    } else if (ii->opt[2] & OPT_CONST && c == 0xffffffff) {
234 
      change_insn_type (ii, II_ADD);
235 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
236 
      return 1;
237 931 markom 
    } else break;
238 
  case II_OR:
239 932 markom 
    if (ii->opt[2] & OPT_CONST && c == 0x0) {
240 897 markom 
      change_insn_type (ii, II_ADD);
241 
      ii->op[1] = c; ii->opt[1] = OPT_CONST;
242 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
243 
      return 1;
244 932 markom 
    } else if (ii->opt[2] & OPT_CONST && c == 0xffffffff) {
245 
      change_insn_type (ii, II_ADD);
246 
      ii->op[1] = 0xffffffff; ii->opt[1] = OPT_CONST;
247 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
248 
      return 1;
249 931 markom 
    } else break;
250 
  case II_SUB:
251 897 markom 
    if (ii->opt[1] == ii->opt[2] && ii->op[1] == ii->op[2]) {
252 
      change_insn_type (ii, II_ADD);
253 
      ii->op[1] = 0; ii->opt[1] = OPT_CONST;
254 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
255 
      return 1;
256 931 markom 
    } else break;
257 
  case II_MUL:
258 897 markom 
    if (ii->opt[2] & OPT_CONST && c == 0) {
259 
      change_insn_type (ii, II_ADD);
260 
      ii->op[1] = 0; ii->opt[1] = OPT_CONST;
261 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
262 
      return 1;
263 
    } else
264 
    if (ii->opt[2] & OPT_CONST && c == 1) {
265 
      change_insn_type (ii, II_ADD);
266 
      ii->op[1] = c; ii->opt[1] = OPT_CONST;
267 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
268 
      return 1;
269 
    } else
270 
    if (ii->opt[2] & OPT_CONST && c == 0xffffffff) {
271 
      change_insn_type (ii, II_SUB);
272 
      ii->op[2] = ii->op[1]; ii->opt[2] = ii->opt[1];
273 
      ii->op[1] = 0; ii->opt[1] = OPT_CONST;
274 
      return 1;
275 931 markom 
    } else break;
276 
  case II_SRL:
277 897 markom 
    if (ii->opt[2] & OPT_CONST && c == 0) {
278 
      change_insn_type (ii, II_ADD);
279 
      ii->op[1] = c; ii->opt[1] = OPT_CONST;
280 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
281 
      return 1;
282 
    } else if (ii->opt[2] & OPT_CONST && c >= 32) {
283 
      change_insn_type (ii, II_ADD);
284 
      ii->op[1] = 0; ii->opt[1] = OPT_CONST;
285 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
286 
      return 1;
287 931 markom 
    } else break;
288 
  case II_SLL:
289 897 markom 
    if (ii->opt[2] & OPT_CONST && c == 0) {
290 
      change_insn_type (ii, II_ADD);
291 
      ii->op[1] = c; ii->opt[1] = OPT_CONST;
292 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
293 
      return 1;
294 
    } else if (ii->opt[2] & OPT_CONST && c >= 32) {
295 
      change_insn_type (ii, II_ADD);
296 
      ii->op[1] = 0; ii->opt[1] = OPT_CONST;
297 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
298 
      return 1;
299 931 markom 
    } else break;
300 
  case II_SRA:
301 897 markom 
    if (ii->opt[2] & OPT_CONST && c == 0) {
302 
      change_insn_type (ii, II_ADD);
303 
      ii->op[1] = c; ii->opt[1] = OPT_CONST;
304 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
305 
      return 1;
306 931 markom 
    } else break;
307 
  case II_SFEQ:
308 
    if (ii->opt[1] & OPT_CONST && ii->opt[2] & OPT_CONST) {
309 
      change_insn_type (ii, II_ADD);
310 
      ii->op[1] = ii->op[1] == ii->op[2]; ii->opt[1] = OPT_CONST;
311 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
312 
      return 1;
313 
    } else break;
314 
  case II_SFNE:
315 
    if (ii->opt[1] & OPT_CONST && ii->opt[2] & OPT_CONST) {
316 
      change_insn_type (ii, II_ADD);
317 
      ii->op[1] = ii->op[1] != ii->op[2]; ii->opt[1] = OPT_CONST;
318 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
319 
      return 1;
320 
    } else break;
321 
  case II_SFLE:
322 
    if (ii->opt[1] & OPT_CONST && ii->opt[2] & OPT_CONST) {
323 
      change_insn_type (ii, II_ADD);
324 
      ii->op[1] = ii->op[1] <= ii->op[2]; ii->opt[1] = OPT_CONST;
325 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
326 
      return 1;
327 
    } else break;
328 
  case II_SFLT:
329 
    if (ii->opt[1] & OPT_CONST && ii->opt[2] & OPT_CONST) {
330 
      change_insn_type (ii, II_ADD);
331 
      ii->op[1] = ii->op[1] < ii->op[2]; ii->opt[1] = OPT_CONST;
332 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
333 
      return 1;
334 
    } else break;
335 
  case II_SFGE:
336 
    if (ii->opt[1] & OPT_CONST && ii->opt[2] & OPT_CONST) {
337 
      change_insn_type (ii, II_ADD);
338 
      ii->op[1] = ii->op[1] >= ii->op[2]; ii->opt[1] = OPT_CONST;
339 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
340 
      return 1;
341 
    } else break;
342 
  case II_SFGT:
343 
    if (ii->opt[1] & OPT_CONST && ii->opt[2] & OPT_CONST) {
344 
      change_insn_type (ii, II_ADD);
345 
      ii->op[1] = ii->op[1] > ii->op[2]; ii->opt[1] = OPT_CONST;
346 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
347 
      return 1;
348 
    } else break;
349 
  case II_CMOV:
350 897 markom 
    if (ii->opt[1] == ii->opt[2] && ii->op[1] == ii->op[2]) {
351 
      change_insn_type (ii, II_ADD);
352 
      ii->op[2] = 0; ii->opt[2] = OPT_CONST;
353 
      ii->opt[3] = OPT_NONE;
354 
      return 1;
355 
    }
356 905 markom 
    if (ii->opt[3] & OPT_CONST) {
357 
      change_insn_type (ii, II_ADD);
358 
      if (ii->op[3]) {
359 
        ii->op[2] = 0; ii->opt[2] = OPT_CONST;
360 
      } else {
361 
        ii->op[1] = 0; ii->opt[1] = OPT_CONST;
362 
      }
363 
      ii->opt[3] = OPT_NONE;
364 
      return 1;
365 
    }
366 927 markom 
    if (ii->type & IT_COND) {
367 
      if (ii->opt[1] & OPT_CONST && ii->opt[2] & OPT_CONST) {
368 
        if (ii->op[1] && !ii->op[2]) {
369 
          change_insn_type (ii, II_ADD);
370 
          ii->op[1] = ii->op[3]; ii->opt[1] = ii->opt[3];
371 
          ii->op[2] = 0; ii->opt[2] = OPT_CONST;
372 
          ii->opt[3] = OPT_NONE;
373 
          return 1;
374 
        }
375 
        if (ii->op[1] && ii->op[2]) {
376 
          change_insn_type (ii, II_ADD);
377 
          ii->op[1] = 1; ii->opt[1] = OPT_CONST;
378 
          ii->op[2] = 0; ii->opt[2] = OPT_CONST;
379 
          ii->opt[3] = OPT_NONE;
380 
          return 1;
381 
        }
382 
        if (!ii->op[1] && !ii->op[2]) {
383 
          change_insn_type (ii, II_ADD);
384 
          ii->op[1] = 0; ii->opt[1] = OPT_CONST;
385 
          ii->op[2] = 0; ii->opt[2] = OPT_CONST;
386 
          ii->opt[3] = OPT_NONE;
387 930 markom 
          return 1;
388 927 markom 
        }
389 
      }
390 931 markom 
      if (ii->op[1] == ii->op[3] && ii->opt[1] == ii->opt[3]) {
391 
        ii->op[1] = 1; ii->opt[1] = OPT_CONST;
392 
        return 1;
393 
      }
394 
      if (ii->op[2] == ii->op[3] && ii->opt[2] == ii->opt[3]) {
395 
        ii->op[2] = 0; ii->opt[2] = OPT_CONST;
396 
        return 1;
397 
      }
398 927 markom 
    }
399 931 markom 
    break;
400 897 markom 
  }
401 
  return 0;
402 
}
403 
 
404 902 markom 
/* First primary input */
405 
static unsigned long tmp_op, tmp_opt;
406 
 
407 
/* Recursive function that searches for primary inputs;
408 
   returns 0 if cmov can be replaced by add */
409 
static int cmov_needed (cuc_func *f, int ref)
410 
{
411 
  cuc_insn *ii = &f->INSN(ref);
412 
  int j;
413 
 
414 903 markom 
  cucdebug (4, " %x", ref);
415 902 markom 
  /* mark visited, if already marked, we have a loop, ignore */
416 
  if (ii->tmp) return 0;
417 
  ii->tmp = 1;
418 
 
419 
  /* handle normal movs separately */
420 917 markom 
  if (ii->index == II_ADD && !(ii->type & IT_VOLATILE)
421 902 markom 
    && ii->opt[2] == OPT_CONST && ii->op[2] == 0) {
422 
    if (ii->opt[1] == OPT_REF) {
423 
      if (cmov_needed (f, ii->op[1])) {
424 
        ii->tmp = 0;
425 
        return 1;
426 
      }
427 
    } else {
428 
      if (tmp_opt == OPT_NONE) {
429 
        tmp_op = ii->op[1];
430 
        tmp_opt = ii->opt[1];
431 
      } else if (tmp_opt != ii->opt[1] || tmp_op != ii->op[1]) {
432 
        ii->tmp = 0;
433 
        return 1;
434 
      }
435 
    }
436 
    ii->tmp = 0;
437 
    return 0;
438 
  }
439 
 
440 
  /* Is this instruction CMOV? no => add to primary inputs */
441 
  if (ii->index != II_CMOV || ii->type & IT_VOLATILE)
442 
    if (tmp_opt == OPT_NONE) {
443 
      tmp_op = ref;
444 
      tmp_opt = OPT_REF;
445 
      ii->tmp = 0;
446 
      return 0;
447 
    } else if (tmp_opt != OPT_REF || tmp_op != ref) {
448 
      ii->tmp = 0;
449 
      return 1;
450 917 markom 
    } else {
451 
      ii->tmp = 0;
452 
      return 0;
453 902 markom 
    }
454 
 
455 
  for (j = 1; j < 3; j++) {
456 903 markom 
    cucdebug (4, "(%x:%i)", ref, j);
457 902 markom 
    if (ii->opt[j] == OPT_REF) {
458 
      if (cmov_needed (f, ii->op[j])) {
459 
        ii->tmp = 0;
460 
        return 1;
461 
      }
462 
    } else {
463 
      if (tmp_opt == OPT_NONE) {
464 
        tmp_op = ii->op[j];
465 
        tmp_opt = ii->opt[j];
466 
      } else if (tmp_opt != ii->opt[j] || tmp_op != ii->op[j]) {
467 
        ii->tmp = 0;
468 
        return 1;
469 
      }
470 
    }
471 
  }
472 
 
473 
  ii->tmp = 0;
474 
  return 0;
475 
}
476 
 
477 
/* Search and optimize complex cmov assignments */
478 931 markom 
int optimize_cmovs (cuc_func *f)
479 902 markom 
{
480 931 markom 
  int modified = 0;
481 902 markom 
  int b, i, j;
482 
 
483 
  /* Mark all instructions unvisited */
484 
  for (b = 0; b < f->num_bb; b++) if (!(f->bb[b].type & BB_DEAD))
485 
    for (i = 0; i < f->bb[b].ninsn; i++) f->bb[b].insn[i].tmp = 0;
486 
 
487 
  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 
      if (ii->index == II_CMOV && !(ii->type & IT_VOLATILE)) {
491 
        tmp_opt = OPT_NONE;
492 903 markom 
        cucdebug (4, "\n");
493 902 markom 
        if (!cmov_needed (f, REF(b, i))) {
494 
          assert (tmp_opt != OPT_NONE);
495 
          change_insn_type (ii, II_ADD);
496 
          ii->op[1] = tmp_op; ii->opt[1] = tmp_opt;
497 
          ii->op[2] = 0; ii->opt[2] = OPT_CONST;
498 
          ii->opt[3] = OPT_NONE;
499 931 markom 
          modified = 1;
500 902 markom 
        }
501 
      }
502 
    }
503 
  }
504 931 markom 
  return modified;
505 902 markom 
}
506 
 
507 930 markom 
/* returns number of instructions, using instruction ref */
508 
static int insn_uses (cuc_func *f, int ref)
509 
{
510 
  int b, i, j;
511 
  int cnt = 0;
512 
  for (b = 0; b < f->num_bb; b++)
513 
    for (i = 0; i < f->bb[b].ninsn; i++)
514 
      for (j = 0; j < MAX_OPERANDS; j++)
515 
        if (f->bb[b].insn[i].opt[j] & OPT_REF && f->bb[b].insn[i].op[j] == ref) cnt++;
516 
  return cnt;
517 
}
518 
 
519 
/* handles some common CMOV, CMOV-CMOV cases;
520 
   returns nonzero if anything optimized */
521 
static int optimize_cmov_more (cuc_func *f, int ref)
522 
{
523 
  int t = 0;
524 
  cuc_insn *ii = &f->INSN(ref);
525 
  assert (ii->index == II_CMOV);
526 
 
527 
  /* In case of x = cmov x, y; or x = cmov y, x; we have
528 
     asynchroneous loop -> remove it */
529 
  if ((ii->opt[1] & OPT_REF) && ii->op[1] == ref) t = 1;
530 
  if ((ii->opt[2] & OPT_REF) && ii->op[2] == ref) t = 2;
531 
  if (ii->opt[1] == ii->opt[2] && ii->op[1] == ii->op[2]) t = 2;
532 
  if (t) {
533 
    change_insn_type (ii, II_ADD);
534 
    cucdebug (2, "%8x:cmov     %i\n", ref, t);
535 
    ii->opt[t] = OPT_CONST;
536 
    ii->op[t] = 0;
537 
    ii->opt[3] = OPT_NONE;
538 
    return 1;
539 
  }
540 
  if (!(ii->type & IT_COND)) {
541 
    for (t = 1; t <= 2; t++) {
542 
      /*   cmov L, X, Y, C1
543 
           cmov Z, L, Y, C2
544 
         can be replaced with simpler:
545 
           cmov L, C1, C2, C2
546 
           cmov Z, X, Y, L */
547 
      if (ii->opt[t] == OPT_REF && f->INSN(ii->op[t]).index == II_CMOV) {
548 
        int r = ii->op[t];
549 
        unsigned long x, xt, y, yt;
550 
        cuc_insn *prev = &f->INSN(r);
551 
        cuc_check (f);
552 
        cucdebug (3, "%x-%x\n", ref, r);
553 
        assert (!(prev->type & IT_COND));
554 
        if (prev->op[3 - t] != ii->op[3 - t] || prev->opt[3 - t] != ii->opt[3 - t]
555 
         || insn_uses (f, r) > 1) continue;
556 
        cucdebug (3, "%x-%x cmov more\n", ref, r);
557 
        prev->type |= IT_COND;
558 
        x = prev->op[t]; xt = prev->opt[t];
559 
        y = prev->op[3 - t]; yt = prev->opt[3 - t];
560 
        prev->op[t] = ii->op[3]; prev->opt[t] = ii->opt[3];     /* C2 */
561 
        ii->op[3] = r; ii->opt[3] = OPT_REF;                    /* L */
562 
        prev->op[3 - t] = prev->op[3]; prev->opt[3 - t] = prev->opt[3]; /* C1 */
563 
        prev->op[3] = prev->op[t]; prev->opt[3] = prev->opt[t]; /* C2 */
564 
        ii->op[t] = x; ii->opt[t] = xt;                         /* X */
565 
        ii->op[3 - t] = y; ii->opt[3 - t] = yt;                 /* Y */
566 
        prev->op[0] = -1; prev->opt[0] = OPT_REGISTER | OPT_DEST;
567 
        cuc_check (f);
568 
        return 1;
569 
      }
570 
    }
571 
  }
572 
 
573 938 markom 
  if (ii->opt[3] & OPT_REF) {
574 930 markom 
    cuc_insn *prev = &f->INSN(ii->op[3]);
575 
    assert (prev->type & IT_COND);
576 
    if (prev->index == II_CMOV) {
577 931 markom 
      /* negated conditional:
578 
           cmov x, 0, 1, y
579 
           cmov z, a, b, x
580 
         is replaced by
581 
           cmov z, b, a, y */
582 
      if (prev->opt[1] & OPT_CONST && prev->opt[2] & OPT_CONST
583 
       && !prev->op[1] && prev->op[2]) {
584 
        unsigned long t;
585 
        t = ii->op[1]; ii->op[1] = ii->op[2]; ii->op[2] = t;
586 
        t = ii->opt[1]; ii->opt[1] = ii->opt[2]; ii->opt[2] = t;
587 
        ii->op[3] = prev->op[3]; ii->opt[3] = prev->opt[3];
588 
      }
589 930 markom 
    } else if (prev->index == II_ADD) {
590 931 markom 
      /*   add x, y, 0
591 
           cmov z, a, b, x
592 
        is replaced by
593 
           cmov z, a, b, y */
594 930 markom 
      if (prev->opt[2] & OPT_CONST && prev->op[2] == 0) {
595 
        ii->op[3] = prev->op[1]; ii->opt[3] = prev->opt[1];
596 
        return 1;
597 
      }
598 
    }
599 
  }
600 
  return 0;
601 
}
602 
 
603 897 markom 
/* Optimizes dataflow tree */
604 931 markom 
int optimize_tree (cuc_func *f)
605 897 markom 
{
606 
  int b, i, j;
607 
  int modified;
608 931 markom 
  int gmodified = 0;
609 897 markom 
 
610 
  do {
611 
    modified = 0;
612 930 markom 
    if (cuc_debug) cuc_check (f);
613 897 markom 
    for (b = 0; b < f->num_bb; b++) if (!(f->bb[b].type & BB_DEAD)) {
614 
      for (i = 0; i < f->bb[b].ninsn; i++) {
615 
        cuc_insn *ii = &f->bb[b].insn[i];
616 
        /* We tend to have the third parameter const if instruction is cumutative */
617 929 markom 
        if ((ii->opt[1] & OPT_CONST) && !(ii->opt[2] & OPT_CONST)) {
618 
          int cond = 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 (known[ii->index].comutative || cond) {
622 
            unsigned long t = ii->opt[1];
623 
            ii->opt[1] = ii->opt[2];
624 
            ii->opt[2] = t;
625 
            t = ii->op[1];
626 
            ii->op[1] = ii->op[2];
627 
            ii->op[2] = t;
628 
            modified = 1; cucdebug (2, "%08x:<>\n", REF(b, i));
629 
            if (cond) {
630 
              if (ii->index == II_SFEQ) ii->index = II_SFNE;
631 
              else if (ii->index == II_SFNE) ii->index = II_SFEQ;
632 
              else if (ii->index == II_SFLE) ii->index = II_SFGT;
633 
              else if (ii->index == II_SFLT) ii->index = II_SFGE;
634 
              else if (ii->index == II_SFGE) ii->index = II_SFLT;
635 
              else if (ii->index == II_SFGT) ii->index = II_SFLE;
636 
              else assert (0);
637 
            }
638 
          }
639 897 markom 
        }
640 
 
641 
        /* Try to do the promotion */
642 
        /* We have two consecutive expressions, containing constants,
643 
         * if previous is a simple expression we can handle it simply: */
644 
        for (j = 0; j < MAX_OPERANDS; j++)
645 
          if (ii->opt[j] & OPT_REF) {
646 
            cuc_insn *t = &f->INSN(ii->op[j]);
647 
            if (f->INSN(ii->op[j]).index == II_ADD
648 
             && f->INSN(ii->op[j]).opt[2] & OPT_CONST
649 
             && f->INSN(ii->op[j]).op[2] == 0
650 931 markom 
             && !(ii->type & IT_MEMORY && t->type & IT_MEMADD)) {
651 897 markom 
            /* do not promote through add-mem, and branches */
652 
              modified = 1; cucdebug (2, "%8x:promote%i %8x %8x\n", REF (b, i), j, ii->op[j], t->op[1]);
653 
              ii->op[j] = t->op[1]; ii->opt[j] = t->opt[1];
654 
            }
655 
          }
656 930 markom 
 
657 
        /* handle some CMOV cases more deeply */
658 
        if (ii->index == II_CMOV && optimize_cmov_more (f, REF (b, i))) {
659 
          modified = 1;
660 
          continue;
661 897 markom 
        }
662 
 
663 
        /* Do nothing to volatile instructions */
664 
        if (ii->type & IT_VOLATILE) continue;
665 
 
666 
        /* Check whether we can simplify the instruction */
667 
        if (apply_edge_condition (ii)) {
668 
          modified = 1;
669 
          continue;
670 
        }
671 
        /* We cannot do anything more if at least one is not constant */
672 
        if (!(ii->opt[2] & OPT_CONST)) continue;
673 
 
674 
        if (ii->opt[1] & OPT_CONST) { /* We have constant expression */
675 
          unsigned long value;
676 
          int ok = 1;
677 
          /* Was constant expression already? */
678 
          if (ii->index == II_ADD && !ii->op[2]) continue;
679 
 
680 
          if (ii->index == II_ADD) value = ii->op[1] + ii->op[2];
681 
          else if (ii->index == II_SUB) value = ii->op[1] - ii->op[2];
682 
          else if (ii->index == II_SLL) value = ii->op[1] << ii->op[2];
683 
          else if (ii->index == II_SRL) value = ii->op[1] >> ii->op[2];
684 
          else if (ii->index == II_MUL) value = ii->op[1] * ii->op[2];
685 
          else if (ii->index == II_OR) value = ii->op[1] | ii->op[2];
686 
          else if (ii->index == II_XOR) value = ii->op[1] ^ ii->op[2];
687 
          else if (ii->index == II_AND) value = ii->op[1] & ii->op[2];
688 
          else ok = 0;
689 
          if (ok) {
690 
            change_insn_type (ii, II_ADD);
691 
            ii->op[0] = -1; ii->opt[0] = OPT_REGISTER | OPT_DEST;
692 
            ii->op[1] = value; ii->opt[1] = OPT_CONST;
693 
            ii->op[2] = 0; ii->opt[2] = OPT_CONST;
694 
            modified = 1; cucdebug (2, "%8x:const\n", REF (b, i));
695 
          }
696 
        } else if (ii->opt[1] & OPT_REF) {
697 
          cuc_insn *prev = &f->INSN(ii->op[1]);
698 930 markom 
          /* Is this just a move? */
699 897 markom 
          if (ii->index == II_ADD
700 
           && !(ii->type & IT_MEMADD) && ii->op[2] == 0) {
701 
            int b1, i1, j1;
702 
            cucdebug (2, "%8x:link      %8x: ", REF(b, i), ii->op[1]);
703 
            for (b1 = 0; b1 < f->num_bb; b1++) if (!(f->bb[b1].type & BB_DEAD))
704 
              for (i1 = 0; i1 < f->bb[b1].ninsn; i1++)
705 
                for (j1 = 0; j1 < MAX_OPERANDS; j1++)
706 
                  if ((f->bb[b1].insn[i1].opt[j1] & OPT_REF)
707 
                   && f->bb[b1].insn[i1].op[j1] == REF(b, i)) {
708 
                    cucdebug (2, "%x ", REF (b1, i1));
709 
                    f->bb[b1].insn[i1].op[j1] = ii->op[1];
710 
                  }
711 
            cucdebug (2, "\n");
712 
            change_insn_type (ii, II_NOP);
713 
          } else if (prev->opt[2] & OPT_CONST) {
714 
            /* Handle some common cases */
715 
            /* add - add joining */
716 
            if (ii->index == II_ADD && prev->index == II_ADD) {
717 
              ii->op[1] = prev->op[1]; ii->opt[1] = prev->opt[1];
718 
              ii->op[2] += prev->op[2];
719 
              modified = 1; cucdebug (2, "%8x: add-add\n", REF(b, i));
720 
            } else /* add - sub joining */
721 
            if (ii->index == II_ADD && prev->index == II_SUB) {
722 
              change_insn_type (&insn[i], II_SUB);
723 
              ii->op[1] = prev->op[1]; ii->opt[1] = prev->opt[1];
724 
              ii->op[2] += prev->op[2];
725 
              modified = 1; cucdebug (2, "%8x: add-sub\n", REF(b, i));
726 
            } else /* sub - add joining */
727 
            if (ii->index == II_SUB && prev->index == II_ADD) {
728 
              ii->op[1] = prev->op[1]; ii->opt[1] = prev->opt[1];
729 
              ii->op[2] += prev->op[2];
730 
              modified = 1; cucdebug (2, "%8x: sub-add\n", REF(b, i));
731 929 markom 
            } else /* add - sfxx joining */
732 
            if (prev->index == II_ADD && (
733 
                ii->index == II_SFEQ || ii->index == II_SFNE
734 
             || ii->index == II_SFLT || ii->index == II_SFLE
735 
             || ii->index == II_SFGT || ii->index == II_SFGE)) {
736 
              if (ii->opt[2] & OPT_CONST) {
737 
                ii->op[1] = prev->op[1]; ii->opt[1] = prev->opt[1];
738 
                ii->op[2] -= prev->op[2];
739 
                modified = 1; cucdebug (2, "%8x: add-sfxx\n", REF(b, i));
740 
              }
741 
            } else /* sub - sfxx joining */
742 
            if (prev->index == II_SUB && (
743 
                ii->index == II_SFEQ || ii->index == II_SFNE
744 
             || ii->index == II_SFLT || ii->index == II_SFLE
745 
             || ii->index == II_SFGT || ii->index == II_SFGE)) {
746 
              if (ii->opt[2] & OPT_CONST) {
747 
                ii->op[1] = prev->op[1]; ii->opt[1] = prev->opt[1];
748 
                ii->op[2] += prev->op[2];
749 
                modified = 1; cucdebug (2, "%8x: sub-sfxx\n", REF(b, i));
750 
              }
751 897 markom 
            }
752 
          }
753 
        }
754 
      }
755 
    }
756 931 markom 
    if (modified) gmodified = 1;
757 897 markom 
  } while (modified);
758 931 markom 
  return gmodified;
759 897 markom 
}
760 
 
761 
/* Remove nop instructions */
762 931 markom 
int remove_nops (cuc_func *f)
763 897 markom 
{
764 
  int b;
765 931 markom 
  int modified = 0;
766 897 markom 
  for (b = 0; b < f->num_bb; b++) {
767 
    int c, d = 0, i, j;
768 
    cuc_insn *insn = f->bb[b].insn;
769 
    for (i = 0; i < f->bb[b].ninsn; i++)
770 
      if (insn[i].index != II_NOP) {
771 
        reloc [i] = d;
772 
        insn[d++] = insn[i];
773 
      } else {
774 
        reloc[i] = d; /* For jumps only */
775 
      }
776 931 markom 
    if (f->bb[b].ninsn != d) modified = 1;
777 897 markom 
    f->bb[b].ninsn = d;
778 
 
779 
    /* Relocate references from all basic blocks */
780 
    for (c = 0; c < f->num_bb; c++)
781 
      for (i = 0; i < f->bb[c].ninsn; i++) {
782 
        dep_list *d = f->bb[c].insn[i].dep;
783 
        for (j = 0; j < MAX_OPERANDS; j++)
784 
          if ((f->bb[c].insn[i].opt[j] & OPT_REF)
785 
            && REF_BB(f->bb[c].insn[i].op[j]) == b)
786 
            f->bb[c].insn[i].op[j] = REF (b, reloc[REF_I (f->bb[c].insn[i].op[j])]);
787 
 
788 
        while (d) {
789 
          if (REF_BB(d->ref) == b) d->ref = REF (b, reloc[REF_I (d->ref)]);
790 
          d = d->next;
791 
        }
792 
      }
793 
  }
794 931 markom 
  return modified;
795 897 markom 
}
796 
 
797 932 markom 
static void unmark_tree (cuc_func *f, int ref)
798 
{
799 
  cuc_insn *ii = &f->INSN(ref);
800 
  printf ("%x ", ref);
801 
  if (ii->type & IT_UNUSED) {
802 
    int j;
803 
    ii->type &= ~IT_UNUSED;
804 
    for (j = 0; j < MAX_OPERANDS; j++)
805 
      if (ii->opt[j] & OPT_REF) unmark_tree (f, ii->op[j]);
806 
  }
807 
}
808 
 
809 897 markom 
/* Remove unused assignments */
810 931 markom 
int remove_dead (cuc_func *f)
811 897 markom 
{
812 
  int b, i, j;
813 
  for (b = 0; b < f->num_bb; b++)
814 
    for (i = 0; i < f->bb[b].ninsn; i++)
815 932 markom 
      f->bb[b].insn[i].type |= IT_UNUSED;
816 897 markom 
 
817 932 markom 
  for (b = 0; b < f->num_bb; b++)
818 
    for (i = 0; i < f->bb[b].ninsn; i++) {
819 
      cuc_insn *ii = &f->bb[b].insn[i];
820 
      if (ii->type & IT_VOLATILE || ii->type & IT_OUTPUT
821 
       || II_IS_LOAD (ii->index) && (f->memory_order == MO_NONE || f->memory_order == MO_WEAK)
822 
       || II_IS_STORE (ii->index)) {
823 
        unmark_tree (f, REF (b, i));
824 
        printf ("\n");
825 
      }
826 
    }
827 897 markom 
 
828 
  for (b = 0; b < f->num_bb; b++)
829 
    for (i = 0; i < f->bb[b].ninsn; i++)
830 
      if (f->bb[b].insn[i].type & IT_UNUSED) {
831 
        change_insn_type (&f->bb[b].insn[i], II_NOP);
832 
      }
833 
 
834 931 markom 
  return remove_nops (f);
835 897 markom 
}
836 
 
837 
/* Removes trivial register assignments */
838 931 markom 
int remove_trivial_regs (cuc_func *f)
839 897 markom 
{
840 
  int b, i;
841 939 markom 
  for (i = 0; i < MAX_REGS; i++) f->saved_regs[i] = caller_saved[i];
842 897 markom 
 
843 
  for (b = 0; b < f->num_bb; b++) {
844 
    cuc_insn *insn = f->bb[b].insn;
845 
    for (i = 0; i < f->bb[b].ninsn; i++) {
846 
      if (insn[i].index == II_ADD
847 
        && insn[i].opt[0] & OPT_REGISTER
848 
        && insn[i].opt[1] & OPT_REGISTER && insn[i].op[0] == insn[i].op[1]
849 
        && insn[i].opt[2] & OPT_CONST && insn[i].op[2] == 0) {
850 
          if (insn[i].type & IT_OUTPUT) f->saved_regs[insn[i].op[0]] = 1;
851 
          change_insn_type (&insn[i], II_NOP);
852 
        }
853 
    }
854 
  }
855 
  if (cuc_debug >= 2) {
856 
    printf ("saved regs ");
857 
    for (i = 0; i < MAX_REGS; i++) printf ("%i:%i ", i, f->saved_regs[i]);
858 
    printf ("\n");
859 
  }
860 931 markom 
  return remove_nops (f);
861 897 markom 
}
862 
 
863 
/* Determine inputs and outputs */
864 
void set_io (cuc_func *f)
865 
{
866 
  int b, i, j;
867 
  /* Determine register usage */
868 
  for (i = 0; i < MAX_REGS; i++) {
869 
    f->lur[i] = -1;
870 
    f->used_regs[i] = 0;
871 
  }
872 902 markom 
  if (cuc_debug > 5) print_cuc_bb (f, "SET_IO");
873 897 markom 
  for (b = 0; b < f->num_bb; b++) {
874 
    for (i = 0; i < f->bb[b].ninsn; i++)
875 
      for (j = 0; j < MAX_OPERANDS; j++)
876 
        if (f->bb[b].insn[i].opt[j] & OPT_REGISTER && f->bb[b].insn[i].op[j] >= 0)
877 
          if (f->bb[b].insn[i].opt[j] & OPT_DEST) f->lur[f->bb[b].insn[i].op[j]] = REF (b, i);
878 
          else f->used_regs[f->bb[b].insn[i].op[j]] = 1;
879 
  }
880 
}
881 
 
882 
/* relocate all accesses inside of BB b to back/fwd */
883 
static void relocate_bb (cuc_bb *bb, int b, int back, int fwd)
884 
{
885 
  int i, j;
886 
  for (i = 0; i < bb->ninsn; i++)
887 
    for (j = 0; j < MAX_OPERANDS; j++)
888 
      if (bb->insn[i].opt[j] & OPT_REF
889 
       && REF_BB (bb->insn[i].op[j]) == b) {
890 
        int t = REF_I (bb->insn[i].op[j]);
891 
        if (t < i) bb->insn[i].op[j] = REF (back, t);
892 
        else bb->insn[i].op[j] = REF (fwd, t);
893 
      }
894 
}
895 
 
896 
/* Latch outputs in loops */
897 
void add_latches (cuc_func *f)
898 
{
899 
  int b, i, j;
900 
 
901 
  //print_cuc_bb (f, "ADD_LATCHES a");
902 
  /* Cuts the tree and marks registers */
903 
  mark_cut (f);
904 
 
905 
  /* Split BBs with more than one group */
906 
  for (b = 0; b < f->num_bb; b++) expand_bb (f, b);
907 
  remove_nops (f);
908 
  //print_cuc_bb (f, "ADD_LATCHES 0");
909 
 
910 
  /* Convert accesses in BB_INLOOP type block to latched */
911 
  for (b = 0; b < f->num_bb; b++) {
912 
    int j;
913 
    for (i = 0; i < f->bb[b].ninsn; i++)
914 
      for (j = 0; j < MAX_OPERANDS; j++) if (f->bb[b].insn[i].opt[j] == OPT_REF) {
915 
        int t = f->bb[b].insn[i].op[j];
916 
        /* If we are pointing to a INLOOP block from outside, or forward
917 
           (= previous loop iteration) we must register that data */
918 
        if ((f->bb[REF_BB(t)].type & BB_INLOOP || config.cuc.no_multicycle)
919 
         && !(f->INSN(t).type & (IT_BRANCH | IT_COND))
920 
         && (REF_BB(t) != b || REF_I(t) >= i)) {
921 
          f->INSN(t).type |= IT_LATCHED;
922 
        }
923 
      }
924 
  }
925 
  //print_cuc_bb (f, "ADD_LATCHES 1");
926 
 
927 
  /* Add latches at the end of blocks as needed */
928 
  for (b = 0; b < f->num_bb; b++) {
929 
    int nreg = 0;
930 
    cuc_insn *insn;
931 
    for (i = 0; i < f->bb[b].ninsn; i++)
932 
      if (f->bb[b].insn[i].type & IT_LATCHED) nreg++;
933 
    if (nreg) {
934 
      insn = (cuc_insn *) malloc (sizeof (cuc_insn) * (f->bb[b].ninsn + nreg));
935 
      j = 0;
936 
      for (i = 0; i < f->bb[b].ninsn; i++) {
937 
        insn[i] = f->bb[b].insn[i];
938 
        if (insn[i].type & IT_LATCHED) {
939 
          cuc_insn *ii = &insn[f->bb[b].ninsn + j++];
940 
          change_insn_type (ii, II_REG);
941 
          ii->op[0] = -1; ii->opt[0] = OPT_DEST | OPT_REGISTER;
942 
          ii->op[1] = REF (b, i); ii->opt[1] = OPT_REF;
943 
          ii->opt[2] = ii->opt[3] = OPT_NONE;
944 
          ii->dep = NULL;
945 
          ii->type = IT_VOLATILE;
946 
          sprintf (ii->disasm, "reg %i_%i", b, i);
947 
        }
948 
      }
949 
      f->bb[b].ninsn += nreg;
950 
      free (f->bb[b].insn);
951 
      f->bb[b].insn = insn;
952 
    }
953 
  }
954 
  //print_cuc_bb (f, "ADD_LATCHES 2");
955 
 
956 
  /* Repair references */
957 
  for (b = 0; b < f->num_bb; b++)
958 
    for (i = 0; i < f->bb[b].ninsn; i++)
959 
      for (j = 0; j < MAX_OPERANDS; j++)
960 
        /* If destination instruction is latched, use register instead */
961 
        if (f->bb[b].insn[i].opt[j] == OPT_REF
962 
         && f->INSN(f->bb[b].insn[i].op[j]).type & IT_LATCHED) {
963 
          int b1, i1;
964 
          b1 = REF_BB (f->bb[b].insn[i].op[j]);
965 
          //cucdebug (2, "%i.%i.%i %x\n", b, i, j, f->bb[b].insn[i].op[j]);
966 
          if (b1 != b || REF_I(f->bb[b].insn[i].op[j]) >= i) {
967 
            for (i1 = f->bb[b1].ninsn - 1; i1 >= 0; i1--) {
968 
              assert (f->bb[b1].insn[i1].index == II_REG);
969 
              if (f->bb[b1].insn[i1].op[1] == f->bb[b].insn[i].op[j]) {
970 
                f->bb[b].insn[i].op[j] = REF (b1, i1);
971 
                break;
972 
              }
973 
            }
974 
          }
975 
        }
976 
}
977 
 
978 883 markom 
/* CSE -- common subexpression elimination */
979 931 markom 
int cse (cuc_func *f)
980 883 markom 
{
981 931 markom 
  int modified = 0;
982 883 markom 
  int b, i, j, b1, i1, b2, i2, j2;
983 
  for (b1 = 0; b1 < f->num_bb; b1++)
984 930 markom 
    for (i1 = 0; i1 < f->bb[b1].ninsn; i1++) if (f->bb[b1].insn[i1].index != II_NOP
985 
       && f->bb[b1].insn[i1].index != II_LRBB && !(f->bb[b1].insn[i1].type & IT_MEMORY)
986 
       && !(f->bb[b1].insn[i1].type & IT_MEMADD))
987 883 markom 
      for (b2 = 0; b2 < f->num_bb; b2++)
988 930 markom 
        for (i2 = 0; i2 < f->bb[b2].ninsn; i2++)
989 
          if (f->bb[b2].insn[i2].index != II_NOP && f->bb[b2].insn[i2].index != II_LRBB
990 
           && !(f->bb[b2].insn[i2].type & IT_MEMORY) && !(f->bb[b2].insn[i2].type & IT_MEMADD)
991 
           && (b1 != b2 || i2 > i1)) {
992 
            cuc_insn *ii1 = &f->bb[b1].insn[i1];
993 
            cuc_insn *ii2 = &f->bb[b2].insn[i2];
994 
            int ok = 1;
995 883 markom 
 
996 930 markom 
            /* Do we have an exact match? */
997 
            if (ii1->index != ii2->index) continue;
998 
            if (ii2->type & IT_VOLATILE) continue;
999 
 
1000 
            /* Check all operands also */
1001 
            for (j = 0; j < MAX_OPERANDS; j++) {
1002 
              if (ii1->opt[j] != ii2->opt[j]) {
1003 
                ok = 0;
1004 
                break;
1005 
              }
1006 
              if (ii1->opt[j] & OPT_DEST) continue;
1007 
              if (ii1->opt[j] != OPT_NONE && ii1->op[j] != ii2->op[j]) {
1008 
                ok = 0;
1009 
                break;
1010 
              }
1011 
            }
1012 
 
1013 
            if (ok) {
1014 
              /* remove duplicated instruction and relink the references */
1015 
              cucdebug (3, "%x - %x are same\n", REF(b1, i1), REF(b2, i2));
1016 
              change_insn_type (ii2, II_NOP);
1017 931 markom 
              modified = 1;
1018 930 markom 
              for (b = 0; b < f->num_bb; b++)
1019 
                for (i = 0; i < f->bb[b].ninsn; i++)
1020 
                  for (j = 0; j < MAX_OPERANDS; j++)
1021 
                    if (f->bb[b].insn[i].opt[j] & OPT_REF
1022 
                     && f->bb[b].insn[i].op[j] == REF (b2, i2))
1023 
                      f->bb[b].insn[i].op[j] = REF (b1, i1);
1024 
            }
1025 
          }
1026 931 markom 
  return modified;
1027 883 markom 
}
1028 
 
1029 
static int count_cmovs (cuc_insn *ii, int match)
1030 
{
1031 
  int c = 0, j;
1032 
  if (match & 2) {
1033 
    for (j = 0; j < MAX_OPERANDS; j++)
1034 
      if (ii->opt[j] & OPT_DEST) c++;
1035 
  }
1036 
  if (match & 1) {
1037 
    for (j = 0; j < MAX_OPERANDS; j++)
1038 
      if (!(ii->opt[j] & OPT_DEST) && ii->opt[j] & OPT_REF) c++;
1039 
  } else {
1040 
    for (j = 0; j < MAX_OPERANDS; j++)
1041 
      if (!(ii->opt[j] & OPT_DEST) && ii->opt[j] != OPT_NONE) c++;
1042 
  }
1043 
  return c;
1044 
}
1045 
 
1046 897 markom 
static void search_csm (int iter, cuc_func *f, cuc_shared_list *list);
1047 
static cuc_shared_list *main_list;
1048 883 markom 
static int *iteration;
1049 
 
1050 897 markom 
/* CSM -- common subexpression matching -- resource sharing
1051 
   We try to match tree of instruction inside a BB with as many
1052 
   matches as possible. All possibilities are collected and
1053 
   options, making situation worse are removed */
1054 883 markom 
void csm (cuc_func *f)
1055 
{
1056 
  int b, i, j;
1057 
  int cnt;
1058 897 markom 
  cuc_shared_list *list;
1059 883 markom 
  cuc_timings timings;
1060 
 
1061 
  analyse_timings (f, &timings);
1062 
  main_list = NULL;
1063 
  for (b = 0; b < f->num_bb; b++) {
1064 
    assert (iteration = (int *)malloc (sizeof (int) * f->bb[b].ninsn));
1065 
    for (i = 0; i < f->bb[b].ninsn; i++) {
1066 
      int cnt = 0, cntc = 0;
1067 
      double size = 0., sizec = 0.;
1068 
      int j2 = 0;
1069 
      for (j = 0; j < f->bb[b].ninsn; j++)
1070 
        if (f->bb[b].insn[i].index == f->bb[b].insn[j].index) {
1071 
          int ok = 1;
1072 
          for (j2 = 0; j2 < MAX_OPERANDS; j2++) if (!(f->bb[b].insn[j].opt[j2] & OPT_REF))
1073 
            if (f->bb[b].insn[j].opt[j2] != f->bb[b].insn[i].opt[j2]
1074 
             || f->bb[b].insn[j].op[j2] != f->bb[b].insn[i].opt[j2]) {
1075 
              ok = 0;
1076 
              break;
1077 
            }
1078 
          if (ok) {
1079 
            cntc++;
1080 
            sizec = sizec + insn_size (&f->bb[b].insn[j]);
1081 
          } else {
1082 
            cnt++;
1083 
            size = size + insn_size (&f->bb[b].insn[j]);
1084 
          }
1085 
          iteration[j] = 0;
1086 
        } else iteration[j] = -1;
1087 
      if (cntc > 1) {
1088 897 markom 
        assert (list = (cuc_shared_list *)malloc (sizeof (cuc_shared_list)));
1089 883 markom 
        list->next = main_list;
1090 
        list->from = NULL;
1091 
        list->ref = REF (b, i);
1092 
        list->cnt = cnt;
1093 
        list->cmatch = 1;
1094 
        list->cmovs = count_cmovs (&f->bb[b].insn[i], 3);
1095 
        list->osize = sizec;
1096 
        list->size = ii_size (f->bb[b].insn[i].index, 1);
1097 
        main_list = list;
1098 
        search_csm (0, f, list);
1099 
      }
1100 
      if (cnt > 1) {
1101 897 markom 
        assert (list = (cuc_shared_list *)malloc (sizeof (cuc_shared_list)));
1102 883 markom 
        list->next = main_list;
1103 
        list->from = NULL;
1104 
        list->ref = REF (b, i);
1105 
        list->cnt = cnt + cntc;
1106 
        list->cmatch = 0;
1107 
        list->cmovs = count_cmovs (&f->bb[b].insn[i], 2);
1108 
        list->osize = size + sizec;
1109 
        list->size = ii_size (f->bb[b].insn[i].index, 0);
1110 
        main_list = list;
1111 
        search_csm (0, f, list);
1112 
      }
1113 
    }
1114 
    free (iteration);
1115 
  }
1116 
 
1117 
  for (list = main_list; list; list = list->next) list->dead = 0;
1118 
  cnt = 0;
1119 
  for (list = main_list; list; list = list->next) if (!list->dead) cnt++;
1120 
  cucdebug (1, "noptions = %i\n", cnt);
1121 
 
1122 
  /* Now we will check the real size of the 'improvements'; if the size
1123 
     actually increases, we abandom the option */
1124 
  for (list = main_list; list; list = list->next)
1125 
    if (list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size >= list->osize) list->dead = 1;
1126 
 
1127 
  cnt = 0;
1128 
  for (list = main_list; list; list = list->next) if (!list->dead) cnt++;
1129 
  cucdebug (1, "noptions = %i\n", cnt);
1130 
 
1131 
  /* Count number of instructions grouped */
1132 
  for (list = main_list; list; list = list->next) {
1133 897 markom 
    cuc_shared_list *l = list;
1134 883 markom 
    int c = 0;
1135 
    while (l) {
1136 
      c++;
1137 
      if (f->INSN(l->ref).type & (IT_VOLATILE | IT_MEMORY | IT_MEMADD)) list->dead = 1;
1138 
      l = l->from;
1139 
    }
1140 
    list->ninsn = c;
1141 
  }
1142 
 
1143 
  cnt = 0;
1144 
  for (list = main_list; list; list = list->next)
1145 
    if (!list->dead) cnt++;
1146 
  cucdebug (1, "noptions = %i\n", cnt);
1147 
 
1148 
#if 1
1149 
  /* We can get a lot of options here, so we will delete duplicates */
1150 
  for (list = main_list; list; list = list->next) if (!list->dead) {
1151 897 markom 
    cuc_shared_list *l;
1152 883 markom 
    for (l = list->next; l; l = l->next) if (!l->dead) {
1153 
      int ok = 1;
1154 897 markom 
      cuc_shared_list *t1 = list;
1155 
      cuc_shared_list *t2 = l;
1156 883 markom 
      while (ok && t1 && t2) {
1157 
        if (f->INSN(t1->ref).index == f->INSN(t2->ref).index) {
1158 
          /* If other operands are matching, we must check for them also */
1159 
          if (t1->cmatch) {
1160 
            int j;
1161 
            for (j = 0; j < MAX_OPERANDS; j++)
1162 
              if (!(f->INSN(t1->ref).opt[j] & OPT_REF) || !(f->INSN(t2->ref).opt[j] & OPT_REF)
1163 
               || f->INSN(t1->ref).opt[j] != f->INSN(t2->ref).opt[j]
1164 
               || f->INSN(t1->ref).op[j] != f->INSN(t2->ref).op[j]) {
1165 
                ok = 0;
1166 
                break;
1167 
              }
1168 
          }
1169 
 
1170 
          /* This option is duplicate, remove */
1171 
          if (ok) t1->dead = 1;
1172 
        }
1173 
        t1 = t1->from;
1174 
        t2 = t2->from;
1175 
      }
1176 
    }
1177 
  }
1178 
  cnt = 0;
1179 
  for (list = main_list; list; list = list->next) if (!list->dead) cnt++;
1180 
  cucdebug (1, "noptions = %i\n", cnt);
1181 
#endif
1182 
  /* Print out */
1183 
  for (list = main_list; list; list = list->next) if (!list->dead) {
1184 897 markom 
    cuc_shared_list *l = list;
1185 883 markom 
    cucdebug (1, "%-4s cnt %3i ninsn %3i size %8.1f osize %8.1f cmovs %3i @",
1186 
           cuc_insn_name (&f->INSN(list->ref)), list->cnt, list->ninsn,
1187 
           list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size, list->osize, list->cmovs);
1188 
    while (l) {
1189 
      cucdebug (1, "%c%x,", l->cmatch ? '.' : '!', l->ref);
1190 
      l = l->from;
1191 
    }
1192 
    cucdebug (1, "\n");
1193 
  }
1194 
 
1195 
  /* Calculate estimated timings */
1196 
  for (b = 0; b < f->num_bb; b++) {
1197 
    cnt = 0;
1198 
    for (list = main_list; list; list = list->next)
1199 
      if (!list->dead && REF_BB(list->ref) == b) cnt++;
1200 
 
1201 
    f->bb[b].ntim = cnt;
1202 
    if (!cnt) {
1203 
      f->bb[b].tim = NULL;
1204 
      continue;
1205 
    }
1206 
    assert (f->bb[b].tim = (cuc_timings *)malloc (sizeof (cuc_timings) * cnt));
1207 
 
1208 
    cnt = 0;
1209 
    for (list = main_list; list; list = list->next) if (!list->dead && REF_BB(list->ref) == b) {
1210 897 markom 
      cuc_shared_list *l = list;
1211 883 markom 
      f->bb[b].tim[cnt].b = b;
1212 
      f->bb[b].tim[cnt].preroll = f->bb[b].tim[cnt].unroll = 1;
1213 
      f->bb[b].tim[cnt].nshared = list->ninsn;
1214 897 markom 
      assert (f->bb[b].tim[cnt].shared = (cuc_shared_item *)
1215 
            malloc (sizeof(cuc_shared_item) * list->ninsn));
1216 
      for (i =  0; i < list->ninsn; i++, l = l->from) {
1217 
        f->bb[b].tim[cnt].shared[i].ref = l->ref;
1218 
        f->bb[b].tim[cnt].shared[i].cmatch = l->cmatch;
1219 
      }
1220 883 markom 
      f->bb[b].tim[cnt].new_time = timings.new_time + f->bb[b].cnt * (list->cnt - 1);
1221 897 markom 
      f->bb[b].tim[cnt].size = timings.size +
1222 
             list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size - list->osize;
1223 883 markom 
      cnt++;
1224 
    }
1225 
  }
1226 
}
1227 
 
1228 
/* Recursive function for searching through instruction graph */
1229 897 markom 
static void search_csm (int iter, cuc_func *f, cuc_shared_list *list)
1230 883 markom 
{
1231 
  int b, i, j, i1;
1232 897 markom 
  cuc_shared_list *l;
1233 883 markom 
  b = REF_BB(list->ref);
1234 
  i = REF_I(list->ref);
1235 
 
1236 
  for (j = 0; j < MAX_OPERANDS; j++) if (f->bb[b].insn[i].opt[j] & OPT_REF) {
1237 
    int t = f->bb[b].insn[i].op[j];
1238 
    int cnt = 0, cntc = 0;
1239 
    double size = 0., sizec = 0.;
1240 
 
1241 
    /* Mark neighbours */
1242 
    for (i1 = 0; i1 < f->bb[b].ninsn; i1++) {
1243 
      if (iteration[i1] == iter && f->bb[b].insn[i1].opt[j] & OPT_REF) {
1244 
        int t2 = f->bb[b].insn[i1].op[j];
1245 
        if (f->INSN(t).index == f->INSN(t2).index && f->INSN(t2).opt[j] & OPT_REF) {
1246 
          int j2;
1247 
          int ok = 1;
1248 
          iteration[REF_I(t2)] = iter + 1;
1249 
          for (j2 = 0; j2 < MAX_OPERANDS; j2++) if (!(f->bb[b].insn[i1].opt[j2] & OPT_REF))
1250 
            if (f->bb[b].insn[i1].opt[j2] != f->bb[b].insn[i].opt[j2]
1251 
             || f->bb[b].insn[i1].op[j2] != f->bb[b].insn[i].opt[j2]) {
1252 
              ok = 0;
1253 
              break;
1254 
            }
1255 
          if (ok) {
1256 
            cntc++;
1257 
            sizec = sizec + insn_size (&f->bb[b].insn[i1]);
1258 
          } else {
1259 
            cnt++;
1260 
            size = size + insn_size (&f->bb[b].insn[i1]);
1261 
          }
1262 
        }
1263 
      }
1264 
    }
1265 
 
1266 
    if (cntc > 1) {
1267 897 markom 
      assert (l = (cuc_shared_list *)malloc (sizeof (cuc_shared_list)));
1268 883 markom 
      l->next = main_list;
1269 
      main_list = l;
1270 
      l->from = list;
1271 
      l->ref = t;
1272 
      l->cnt = cnt;
1273 
      l->cmatch = 1;
1274 
      l->cmovs = list->cmovs + count_cmovs (&f->bb[b].insn[i], 1) - 1;
1275 
      l->size = list->size + ii_size (f->bb[b].insn[i].index, 1);
1276 
      l->osize = sizec;
1277 
      search_csm (iter + 1, f, l);
1278 
    }
1279 
    if (cnt > 1) {
1280 897 markom 
      assert (l = (cuc_shared_list *)malloc (sizeof (cuc_shared_list)));
1281 883 markom 
      l->next = main_list;
1282 
      main_list = l;
1283 
      l->from = list;
1284 
      l->ref = t;
1285 
      l->cnt = cnt + cntc;
1286 
      l->cmatch = 0;
1287 
      l->osize = size + sizec;
1288 
      l->cmovs = list->cmovs + count_cmovs (&f->bb[b].insn[i], 0) - 1;
1289 
      l->size = list->size + ii_size (f->bb[b].insn[i].index, 0);
1290 
      search_csm (iter + 1, f, l);
1291 
    }
1292 
 
1293 
    /* Unmark them back */
1294 
    for (i1 = 0; i1 < f->bb[b].ninsn; i1++) if (iteration[i1] > iter) iteration[i1] = -1;
1295 
  }
1296 
}
1297 
 
1298 897 markom 
/* Displays shared instructions */
1299 
void print_shared (cuc_func *rf, cuc_shared_item *shared, int nshared)
1300 
{
1301 
  int i, first = 1;
1302 
  for (i = 0; i < nshared; i++) {
1303 906 markom 
    printf ("%s%s%s", first ? "" : "-", cuc_insn_name (&rf->INSN(shared[i].ref)),
1304 897 markom 
                    shared[i].cmatch ? "!" : "");
1305 
    first = 0;
1306 
  }
1307 
}
1308 
 
1309 
/* Common subexpression matching -- resource sharing, generation pass
1310 
 
1311 
   Situation here is much simpler than with analysis -- we know the instruction sequence
1312 
   we are going to share, but we are going to do this on whole function, not just one BB.
1313 
   We can find sequence in reference function, as pointed from "shared" */
1314 
void csm_gen (cuc_func *f, cuc_func *rf, cuc_shared_item *shared, int nshared)
1315 
{
1316 
  int b, i, j, cnt = 0;
1317 
#warning   some code here (2)
1318 
  printf ("Replacing: ");
1319 
  print_shared (rf, shared, nshared);
1320 
 
1321 
  for (b = 0; b < f->num_bb; b++)
1322 
    for (i = 0; i < f->bb[b].ninsn; i++) {
1323 
    }
1324 
 
1325 
  printf ("\nFound %i matches.\n", cnt);
1326 
}
1327 
 

powered by: WebSVN 2.1.0

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