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

Subversion Repositories or1k

[/] [or1k/] [tags/] [stable_0_2_0_rc2/] [or1ksim/] [cuc/] [insn.c] - Blame information for rev 1041

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

powered by: WebSVN 2.1.0

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