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

Subversion Repositories or1k

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

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 1046 markom 
 
611 
  /* Check if both choices can be pushed through */
612 1047 markom 
  if (ii->opt[1] & OPT_REF && ii->opt[2] & OPT_REF
613 
    /* Usually doesn't make sense to move conditionals though => more area */
614 
    && !(ii->type & IT_COND)) {
615 1046 markom 
    cuc_insn *a, *b;
616 
    a = &f->INSN(ii->op[1]);
617 
    b = &f->INSN(ii->op[2]);
618 
    if (a->index == b->index && !(a->type & IT_VOLATILE) && !(b->type & IT_VOLATILE)) {
619 
      int diff = -1;
620 
      int i;
621 
      for (i = 0; i < MAX_OPERANDS; i++)
622 
        if (a->opt[i] != b->opt[i] || !(a->op[i] == b->op[i] || a->opt[i] & OPT_REGISTER)) {
623 
          if (diff == -1) diff = i; else diff = -2;
624 
        }
625 
      /* If diff == -1, it will be eliminated by CSE */
626 
      if (diff >= 0) {
627 
        cuc_insn tmp, cmov;
628 
        int ref2 = REF (REF_BB (ref), REF_I (ref) + 1);
629 
        insert_insns (f, ref, 1);
630 
        a = &f->INSN(f->INSN(ref2).op[1]);
631 
        b = &f->INSN(f->INSN(ref2).op[2]);
632 
        cucdebug (4, "ref = %x %x %x\n", ref, f->INSN(ref2).op[1], f->INSN(ref2).op[2]);
633 
        if (cuc_debug >= 7) {
634 
          print_cuc_bb (f, "AAA");
635 
          cuc_check (f);
636 
        }
637 
        tmp = *a;
638 
        cmov = f->INSN(ref2);
639 
        tmp.op[diff] = ref; tmp.opt[diff] = OPT_REF;
640 
        cmov.op[1] = a->op[diff]; cmov.opt[1] = a->opt[diff];
641 
        cmov.op[2] = b->op[diff]; cmov.opt[2] = b->opt[diff];
642 
        change_insn_type (&cmov, II_CMOV);
643 
        cmov.type &= ~IT_COND;
644 
        cucdebug (4, "ref2 = %x %x %x\n", ref2, cmov.op[1], cmov.op[2]);
645 
        if (cmov.opt[1] & OPT_REF && cmov.opt[2] & OPT_REF
646 
         && f->INSN(cmov.op[1]).type & IT_COND) {
647 
          assert (f->INSN(cmov.op[2]).type & IT_COND);
648 
          cmov.type |= IT_COND;
649 
        }
650 
        f->INSN(ref) = cmov;
651 
        f->INSN(ref2) = tmp;
652 
        if (cuc_debug >= 6) print_cuc_bb (f, "BBB");
653 
        cuc_check (f);
654 1059 markom 
        return 1;
655 1046 markom 
      }
656 
    }
657 
  }
658 930 markom 
  return 0;
659 
}
660 
 
661 897 markom 
/* Optimizes dataflow tree */
662 931 markom 
int optimize_tree (cuc_func *f)
663 897 markom 
{
664 
  int b, i, j;
665 
  int modified;
666 931 markom 
  int gmodified = 0;
667 897 markom 
 
668 
  do {
669 
    modified = 0;
670 930 markom 
    if (cuc_debug) cuc_check (f);
671 897 markom 
    for (b = 0; b < f->num_bb; b++) if (!(f->bb[b].type & BB_DEAD)) {
672 
      for (i = 0; i < f->bb[b].ninsn; i++) {
673 
        cuc_insn *ii = &f->bb[b].insn[i];
674 
        /* We tend to have the third parameter const if instruction is cumutative */
675 929 markom 
        if ((ii->opt[1] & OPT_CONST) && !(ii->opt[2] & OPT_CONST)) {
676 
          int cond = ii->index == II_SFEQ || ii->index == II_SFNE
677 
                  || ii->index == II_SFLT || ii->index == II_SFLE
678 
                  || ii->index == II_SFGT || ii->index == II_SFGE;
679 
          if (known[ii->index].comutative || cond) {
680 
            unsigned long t = ii->opt[1];
681 
            ii->opt[1] = ii->opt[2];
682 
            ii->opt[2] = t;
683 
            t = ii->op[1];
684 
            ii->op[1] = ii->op[2];
685 
            ii->op[2] = t;
686 
            modified = 1; cucdebug (2, "%08x:<>\n", REF(b, i));
687 
            if (cond) {
688 
              if (ii->index == II_SFEQ) ii->index = II_SFNE;
689 
              else if (ii->index == II_SFNE) ii->index = II_SFEQ;
690 
              else if (ii->index == II_SFLE) ii->index = II_SFGT;
691 
              else if (ii->index == II_SFLT) ii->index = II_SFGE;
692 
              else if (ii->index == II_SFGE) ii->index = II_SFLT;
693 
              else if (ii->index == II_SFGT) ii->index = II_SFLE;
694 
              else assert (0);
695 
            }
696 
          }
697 897 markom 
        }
698 
 
699 
        /* Try to do the promotion */
700 
        /* We have two consecutive expressions, containing constants,
701 
         * if previous is a simple expression we can handle it simply: */
702 
        for (j = 0; j < MAX_OPERANDS; j++)
703 
          if (ii->opt[j] & OPT_REF) {
704 
            cuc_insn *t = &f->INSN(ii->op[j]);
705 
            if (f->INSN(ii->op[j]).index == II_ADD
706 
             && f->INSN(ii->op[j]).opt[2] & OPT_CONST
707 
             && f->INSN(ii->op[j]).op[2] == 0
708 931 markom 
             && !(ii->type & IT_MEMORY && t->type & IT_MEMADD)) {
709 897 markom 
            /* do not promote through add-mem, and branches */
710 
              modified = 1; cucdebug (2, "%8x:promote%i %8x %8x\n", REF (b, i), j, ii->op[j], t->op[1]);
711 
              ii->op[j] = t->op[1]; ii->opt[j] = t->opt[1];
712 
            }
713 
          }
714 930 markom 
 
715 
        /* handle some CMOV cases more deeply */
716 
        if (ii->index == II_CMOV && optimize_cmov_more (f, REF (b, i))) {
717 
          modified = 1;
718 
          continue;
719 897 markom 
        }
720 
 
721 
        /* Do nothing to volatile instructions */
722 
        if (ii->type & IT_VOLATILE) continue;
723 
 
724 
        /* Check whether we can simplify the instruction */
725 
        if (apply_edge_condition (ii)) {
726 
          modified = 1;
727 
          continue;
728 
        }
729 
        /* We cannot do anything more if at least one is not constant */
730 
        if (!(ii->opt[2] & OPT_CONST)) continue;
731 
 
732 
        if (ii->opt[1] & OPT_CONST) { /* We have constant expression */
733 
          unsigned long value;
734 
          int ok = 1;
735 
          /* Was constant expression already? */
736 
          if (ii->index == II_ADD && !ii->op[2]) continue;
737 
 
738 
          if (ii->index == II_ADD) value = ii->op[1] + ii->op[2];
739 
          else if (ii->index == II_SUB) value = ii->op[1] - ii->op[2];
740 
          else if (ii->index == II_SLL) value = ii->op[1] << ii->op[2];
741 
          else if (ii->index == II_SRL) value = ii->op[1] >> ii->op[2];
742 
          else if (ii->index == II_MUL) value = ii->op[1] * ii->op[2];
743 
          else if (ii->index == II_OR) value = ii->op[1] | ii->op[2];
744 
          else if (ii->index == II_XOR) value = ii->op[1] ^ ii->op[2];
745 
          else if (ii->index == II_AND) value = ii->op[1] & ii->op[2];
746 
          else ok = 0;
747 
          if (ok) {
748 
            change_insn_type (ii, II_ADD);
749 
            ii->op[0] = -1; ii->opt[0] = OPT_REGISTER | OPT_DEST;
750 
            ii->op[1] = value; ii->opt[1] = OPT_CONST;
751 
            ii->op[2] = 0; ii->opt[2] = OPT_CONST;
752 
            modified = 1; cucdebug (2, "%8x:const\n", REF (b, i));
753 
          }
754 
        } else if (ii->opt[1] & OPT_REF) {
755 
          cuc_insn *prev = &f->INSN(ii->op[1]);
756 930 markom 
          /* Is this just a move? */
757 897 markom 
          if (ii->index == II_ADD
758 
           && !(ii->type & IT_MEMADD) && ii->op[2] == 0) {
759 
            int b1, i1, j1;
760 
            cucdebug (2, "%8x:link      %8x: ", REF(b, i), ii->op[1]);
761 1059 markom 
            if (!(prev->type & (IT_OUTPUT | IT_VOLATILE))) {
762 
              assert (ii->opt[0] & OPT_DEST);
763 
              prev->op[0] = ii->op[0]; prev->opt[0] = ii->opt[0];
764 
              prev->type |= ii->type & IT_OUTPUT;
765 
              for (b1 = 0; b1 < f->num_bb; b1++) if (!(f->bb[b1].type & BB_DEAD))
766 
                for (i1 = 0; i1 < f->bb[b1].ninsn; i1++)
767 
                  for (j1 = 0; j1 < MAX_OPERANDS; j1++)
768 
                    if ((f->bb[b1].insn[i1].opt[j1] & OPT_REF)
769 
                     && f->bb[b1].insn[i1].op[j1] == REF(b, i)) {
770 
                      cucdebug (2, "%x ", REF (b1, i1));
771 
                      f->bb[b1].insn[i1].op[j1] = ii->op[1];
772 
                    }
773 
              cucdebug (2, "\n");
774 
              change_insn_type (ii, II_NOP);
775 
            }
776 897 markom 
          } else if (prev->opt[2] & OPT_CONST) {
777 
            /* Handle some common cases */
778 
            /* add - add joining */
779 
            if (ii->index == II_ADD && prev->index == II_ADD) {
780 
              ii->op[1] = prev->op[1]; ii->opt[1] = prev->opt[1];
781 
              ii->op[2] += prev->op[2];
782 
              modified = 1; cucdebug (2, "%8x: add-add\n", REF(b, i));
783 
            } else /* add - sub joining */
784 
            if (ii->index == II_ADD && prev->index == II_SUB) {
785 
              change_insn_type (&insn[i], II_SUB);
786 
              ii->op[1] = prev->op[1]; ii->opt[1] = prev->opt[1];
787 
              ii->op[2] += prev->op[2];
788 
              modified = 1; cucdebug (2, "%8x: add-sub\n", REF(b, i));
789 
            } else /* sub - add joining */
790 
            if (ii->index == II_SUB && prev->index == II_ADD) {
791 
              ii->op[1] = prev->op[1]; ii->opt[1] = prev->opt[1];
792 
              ii->op[2] += prev->op[2];
793 
              modified = 1; cucdebug (2, "%8x: sub-add\n", REF(b, i));
794 929 markom 
            } else /* add - sfxx joining */
795 
            if (prev->index == II_ADD && (
796 
                ii->index == II_SFEQ || ii->index == II_SFNE
797 
             || ii->index == II_SFLT || ii->index == II_SFLE
798 
             || ii->index == II_SFGT || ii->index == II_SFGE)) {
799 1041 markom 
              if (ii->opt[2] & OPT_CONST && ii->op[2] < 0x80000000) {
800 929 markom 
                ii->op[1] = prev->op[1]; ii->opt[1] = prev->opt[1];
801 
                ii->op[2] -= prev->op[2];
802 
                modified = 1; cucdebug (2, "%8x: add-sfxx\n", REF(b, i));
803 
              }
804 
            } else /* sub - sfxx joining */
805 
            if (prev->index == II_SUB && (
806 
                ii->index == II_SFEQ || ii->index == II_SFNE
807 
             || ii->index == II_SFLT || ii->index == II_SFLE
808 
             || ii->index == II_SFGT || ii->index == II_SFGE)) {
809 1046 markom 
              if (ii->opt[2] & OPT_CONST && ii->op[2] < 0x80000000) {
810 929 markom 
                ii->op[1] = prev->op[1]; ii->opt[1] = prev->opt[1];
811 
                ii->op[2] += prev->op[2];
812 
                modified = 1; cucdebug (2, "%8x: sub-sfxx\n", REF(b, i));
813 
              }
814 897 markom 
            }
815 
          }
816 
        }
817 
      }
818 
    }
819 931 markom 
    if (modified) gmodified = 1;
820 897 markom 
  } while (modified);
821 931 markom 
  return gmodified;
822 897 markom 
}
823 
 
824 
/* Remove nop instructions */
825 931 markom 
int remove_nops (cuc_func *f)
826 897 markom 
{
827 
  int b;
828 931 markom 
  int modified = 0;
829 897 markom 
  for (b = 0; b < f->num_bb; b++) {
830 
    int c, d = 0, i, j;
831 
    cuc_insn *insn = f->bb[b].insn;
832 
    for (i = 0; i < f->bb[b].ninsn; i++)
833 
      if (insn[i].index != II_NOP) {
834 
        reloc [i] = d;
835 
        insn[d++] = insn[i];
836 
      } else {
837 
        reloc[i] = d; /* For jumps only */
838 
      }
839 931 markom 
    if (f->bb[b].ninsn != d) modified = 1;
840 897 markom 
    f->bb[b].ninsn = d;
841 
 
842 
    /* Relocate references from all basic blocks */
843 
    for (c = 0; c < f->num_bb; c++)
844 
      for (i = 0; i < f->bb[c].ninsn; i++) {
845 
        dep_list *d = f->bb[c].insn[i].dep;
846 
        for (j = 0; j < MAX_OPERANDS; j++)
847 
          if ((f->bb[c].insn[i].opt[j] & OPT_REF)
848 
            && REF_BB(f->bb[c].insn[i].op[j]) == b)
849 
            f->bb[c].insn[i].op[j] = REF (b, reloc[REF_I (f->bb[c].insn[i].op[j])]);
850 
 
851 
        while (d) {
852 
          if (REF_BB(d->ref) == b) d->ref = REF (b, reloc[REF_I (d->ref)]);
853 
          d = d->next;
854 
        }
855 
      }
856 
  }
857 931 markom 
  return modified;
858 897 markom 
}
859 
 
860 932 markom 
static void unmark_tree (cuc_func *f, int ref)
861 
{
862 
  cuc_insn *ii = &f->INSN(ref);
863 973 markom 
  cucdebug (5, "%x ", ref);
864 932 markom 
  if (ii->type & IT_UNUSED) {
865 
    int j;
866 
    ii->type &= ~IT_UNUSED;
867 
    for (j = 0; j < MAX_OPERANDS; j++)
868 
      if (ii->opt[j] & OPT_REF) unmark_tree (f, ii->op[j]);
869 
  }
870 
}
871 
 
872 897 markom 
/* Remove unused assignments */
873 931 markom 
int remove_dead (cuc_func *f)
874 897 markom 
{
875 
  int b, i, j;
876 
  for (b = 0; b < f->num_bb; b++)
877 
    for (i = 0; i < f->bb[b].ninsn; i++)
878 932 markom 
      f->bb[b].insn[i].type |= IT_UNUSED;
879 897 markom 
 
880 932 markom 
  for (b = 0; b < f->num_bb; b++)
881 
    for (i = 0; i < f->bb[b].ninsn; i++) {
882 
      cuc_insn *ii = &f->bb[b].insn[i];
883 
      if (ii->type & IT_VOLATILE || ii->type & IT_OUTPUT
884 
       || II_IS_LOAD (ii->index) && (f->memory_order == MO_NONE || f->memory_order == MO_WEAK)
885 
       || II_IS_STORE (ii->index)) {
886 
        unmark_tree (f, REF (b, i));
887 973 markom 
        cucdebug (5, "\n");
888 932 markom 
      }
889 
    }
890 897 markom 
 
891 
  for (b = 0; b < f->num_bb; b++)
892 
    for (i = 0; i < f->bb[b].ninsn; i++)
893 
      if (f->bb[b].insn[i].type & IT_UNUSED) {
894 
        change_insn_type (&f->bb[b].insn[i], II_NOP);
895 
      }
896 
 
897 931 markom 
  return remove_nops (f);
898 897 markom 
}
899 
 
900 
/* Removes trivial register assignments */
901 931 markom 
int remove_trivial_regs (cuc_func *f)
902 897 markom 
{
903 
  int b, i;
904 939 markom 
  for (i = 0; i < MAX_REGS; i++) f->saved_regs[i] = caller_saved[i];
905 897 markom 
 
906 
  for (b = 0; b < f->num_bb; b++) {
907 
    cuc_insn *insn = f->bb[b].insn;
908 
    for (i = 0; i < f->bb[b].ninsn; i++) {
909 
      if (insn[i].index == II_ADD
910 
        && insn[i].opt[0] & OPT_REGISTER
911 
        && insn[i].opt[1] & OPT_REGISTER && insn[i].op[0] == insn[i].op[1]
912 
        && insn[i].opt[2] & OPT_CONST && insn[i].op[2] == 0) {
913 
          if (insn[i].type & IT_OUTPUT) f->saved_regs[insn[i].op[0]] = 1;
914 
          change_insn_type (&insn[i], II_NOP);
915 
        }
916 
    }
917 
  }
918 
  if (cuc_debug >= 2) {
919 997 markom 
    PRINTF ("saved regs ");
920 
    for (i = 0; i < MAX_REGS; i++) PRINTF ("%i:%i ", i, f->saved_regs[i]);
921 
    PRINTF ("\n");
922 897 markom 
  }
923 931 markom 
  return remove_nops (f);
924 897 markom 
}
925 
 
926 
/* Determine inputs and outputs */
927 
void set_io (cuc_func *f)
928 
{
929 
  int b, i, j;
930 
  /* Determine register usage */
931 
  for (i = 0; i < MAX_REGS; i++) {
932 
    f->lur[i] = -1;
933 
    f->used_regs[i] = 0;
934 
  }
935 902 markom 
  if (cuc_debug > 5) print_cuc_bb (f, "SET_IO");
936 897 markom 
  for (b = 0; b < f->num_bb; b++) {
937 
    for (i = 0; i < f->bb[b].ninsn; i++)
938 
      for (j = 0; j < MAX_OPERANDS; j++)
939 
        if (f->bb[b].insn[i].opt[j] & OPT_REGISTER && f->bb[b].insn[i].op[j] >= 0)
940 
          if (f->bb[b].insn[i].opt[j] & OPT_DEST) f->lur[f->bb[b].insn[i].op[j]] = REF (b, i);
941 
          else f->used_regs[f->bb[b].insn[i].op[j]] = 1;
942 
  }
943 
}
944 
 
945 
/* relocate all accesses inside of BB b to back/fwd */
946 
static void relocate_bb (cuc_bb *bb, int b, int back, int fwd)
947 
{
948 
  int i, j;
949 
  for (i = 0; i < bb->ninsn; i++)
950 
    for (j = 0; j < MAX_OPERANDS; j++)
951 
      if (bb->insn[i].opt[j] & OPT_REF
952 
       && REF_BB (bb->insn[i].op[j]) == b) {
953 
        int t = REF_I (bb->insn[i].op[j]);
954 
        if (t < i) bb->insn[i].op[j] = REF (back, t);
955 
        else bb->insn[i].op[j] = REF (fwd, t);
956 
      }
957 
}
958 
 
959 
/* Latch outputs in loops */
960 
void add_latches (cuc_func *f)
961 
{
962 
  int b, i, j;
963 
 
964 
  //print_cuc_bb (f, "ADD_LATCHES a");
965 
  /* Cuts the tree and marks registers */
966 
  mark_cut (f);
967 
 
968 
  /* Split BBs with more than one group */
969 
  for (b = 0; b < f->num_bb; b++) expand_bb (f, b);
970 
  remove_nops (f);
971 
  //print_cuc_bb (f, "ADD_LATCHES 0");
972 
 
973 
  /* Convert accesses in BB_INLOOP type block to latched */
974 
  for (b = 0; b < f->num_bb; b++) {
975 
    int j;
976 
    for (i = 0; i < f->bb[b].ninsn; i++)
977 
      for (j = 0; j < MAX_OPERANDS; j++) if (f->bb[b].insn[i].opt[j] == OPT_REF) {
978 
        int t = f->bb[b].insn[i].op[j];
979 
        /* If we are pointing to a INLOOP block from outside, or forward
980 
           (= previous loop iteration) we must register that data */
981 
        if ((f->bb[REF_BB(t)].type & BB_INLOOP || config.cuc.no_multicycle)
982 
         && !(f->INSN(t).type & (IT_BRANCH | IT_COND))
983 
         && (REF_BB(t) != b || REF_I(t) >= i)) {
984 
          f->INSN(t).type |= IT_LATCHED;
985 
        }
986 
      }
987 
  }
988 
  //print_cuc_bb (f, "ADD_LATCHES 1");
989 
 
990 
  /* Add latches at the end of blocks as needed */
991 
  for (b = 0; b < f->num_bb; b++) {
992 
    int nreg = 0;
993 
    cuc_insn *insn;
994 
    for (i = 0; i < f->bb[b].ninsn; i++)
995 
      if (f->bb[b].insn[i].type & IT_LATCHED) nreg++;
996 
    if (nreg) {
997 
      insn = (cuc_insn *) malloc (sizeof (cuc_insn) * (f->bb[b].ninsn + nreg));
998 
      j = 0;
999 
      for (i = 0; i < f->bb[b].ninsn; i++) {
1000 
        insn[i] = f->bb[b].insn[i];
1001 
        if (insn[i].type & IT_LATCHED) {
1002 
          cuc_insn *ii = &insn[f->bb[b].ninsn + j++];
1003 
          change_insn_type (ii, II_REG);
1004 
          ii->op[0] = -1; ii->opt[0] = OPT_DEST | OPT_REGISTER;
1005 
          ii->op[1] = REF (b, i); ii->opt[1] = OPT_REF;
1006 
          ii->opt[2] = ii->opt[3] = OPT_NONE;
1007 
          ii->dep = NULL;
1008 
          ii->type = IT_VOLATILE;
1009 
          sprintf (ii->disasm, "reg %i_%i", b, i);
1010 
        }
1011 
      }
1012 
      f->bb[b].ninsn += nreg;
1013 
      free (f->bb[b].insn);
1014 
      f->bb[b].insn = insn;
1015 
    }
1016 
  }
1017 
  //print_cuc_bb (f, "ADD_LATCHES 2");
1018 
 
1019 
  /* Repair references */
1020 
  for (b = 0; b < f->num_bb; b++)
1021 
    for (i = 0; i < f->bb[b].ninsn; i++)
1022 
      for (j = 0; j < MAX_OPERANDS; j++)
1023 
        /* If destination instruction is latched, use register instead */
1024 
        if (f->bb[b].insn[i].opt[j] == OPT_REF
1025 
         && f->INSN(f->bb[b].insn[i].op[j]).type & IT_LATCHED) {
1026 
          int b1, i1;
1027 
          b1 = REF_BB (f->bb[b].insn[i].op[j]);
1028 
          //cucdebug (2, "%i.%i.%i %x\n", b, i, j, f->bb[b].insn[i].op[j]);
1029 
          if (b1 != b || REF_I(f->bb[b].insn[i].op[j]) >= i) {
1030 
            for (i1 = f->bb[b1].ninsn - 1; i1 >= 0; i1--) {
1031 
              assert (f->bb[b1].insn[i1].index == II_REG);
1032 
              if (f->bb[b1].insn[i1].op[1] == f->bb[b].insn[i].op[j]) {
1033 
                f->bb[b].insn[i].op[j] = REF (b1, i1);
1034 
                break;
1035 
              }
1036 
            }
1037 
          }
1038 
        }
1039 
}
1040 
 
1041 883 markom 
/* CSE -- common subexpression elimination */
1042 931 markom 
int cse (cuc_func *f)
1043 883 markom 
{
1044 931 markom 
  int modified = 0;
1045 883 markom 
  int b, i, j, b1, i1, b2, i2, j2;
1046 
  for (b1 = 0; b1 < f->num_bb; b1++)
1047 930 markom 
    for (i1 = 0; i1 < f->bb[b1].ninsn; i1++) if (f->bb[b1].insn[i1].index != II_NOP
1048 
       && f->bb[b1].insn[i1].index != II_LRBB && !(f->bb[b1].insn[i1].type & IT_MEMORY)
1049 
       && !(f->bb[b1].insn[i1].type & IT_MEMADD))
1050 883 markom 
      for (b2 = 0; b2 < f->num_bb; b2++)
1051 930 markom 
        for (i2 = 0; i2 < f->bb[b2].ninsn; i2++)
1052 
          if (f->bb[b2].insn[i2].index != II_NOP && f->bb[b2].insn[i2].index != II_LRBB
1053 
           && !(f->bb[b2].insn[i2].type & IT_MEMORY) && !(f->bb[b2].insn[i2].type & IT_MEMADD)
1054 
           && (b1 != b2 || i2 > i1)) {
1055 
            cuc_insn *ii1 = &f->bb[b1].insn[i1];
1056 
            cuc_insn *ii2 = &f->bb[b2].insn[i2];
1057 
            int ok = 1;
1058 883 markom 
 
1059 930 markom 
            /* Do we have an exact match? */
1060 
            if (ii1->index != ii2->index) continue;
1061 
            if (ii2->type & IT_VOLATILE) continue;
1062 
 
1063 
            /* Check all operands also */
1064 
            for (j = 0; j < MAX_OPERANDS; j++) {
1065 
              if (ii1->opt[j] != ii2->opt[j]) {
1066 
                ok = 0;
1067 
                break;
1068 
              }
1069 
              if (ii1->opt[j] & OPT_DEST) continue;
1070 
              if (ii1->opt[j] != OPT_NONE && ii1->op[j] != ii2->op[j]) {
1071 
                ok = 0;
1072 
                break;
1073 
              }
1074 
            }
1075 
 
1076 
            if (ok) {
1077 
              /* remove duplicated instruction and relink the references */
1078 
              cucdebug (3, "%x - %x are same\n", REF(b1, i1), REF(b2, i2));
1079 
              change_insn_type (ii2, II_NOP);
1080 931 markom 
              modified = 1;
1081 930 markom 
              for (b = 0; b < f->num_bb; b++)
1082 
                for (i = 0; i < f->bb[b].ninsn; i++)
1083 
                  for (j = 0; j < MAX_OPERANDS; j++)
1084 
                    if (f->bb[b].insn[i].opt[j] & OPT_REF
1085 
                     && f->bb[b].insn[i].op[j] == REF (b2, i2))
1086 
                      f->bb[b].insn[i].op[j] = REF (b1, i1);
1087 
            }
1088 
          }
1089 931 markom 
  return modified;
1090 883 markom 
}
1091 
 
1092 
static int count_cmovs (cuc_insn *ii, int match)
1093 
{
1094 
  int c = 0, j;
1095 
  if (match & 2) {
1096 
    for (j = 0; j < MAX_OPERANDS; j++)
1097 
      if (ii->opt[j] & OPT_DEST) c++;
1098 
  }
1099 
  if (match & 1) {
1100 
    for (j = 0; j < MAX_OPERANDS; j++)
1101 
      if (!(ii->opt[j] & OPT_DEST) && ii->opt[j] & OPT_REF) c++;
1102 
  } else {
1103 
    for (j = 0; j < MAX_OPERANDS; j++)
1104 
      if (!(ii->opt[j] & OPT_DEST) && ii->opt[j] != OPT_NONE) c++;
1105 
  }
1106 
  return c;
1107 
}
1108 
 
1109 897 markom 
static void search_csm (int iter, cuc_func *f, cuc_shared_list *list);
1110 
static cuc_shared_list *main_list;
1111 883 markom 
static int *iteration;
1112 
 
1113 897 markom 
/* CSM -- common subexpression matching -- resource sharing
1114 
   We try to match tree of instruction inside a BB with as many
1115 
   matches as possible. All possibilities are collected and
1116 
   options, making situation worse are removed */
1117 883 markom 
void csm (cuc_func *f)
1118 
{
1119 
  int b, i, j;
1120 
  int cnt;
1121 897 markom 
  cuc_shared_list *list;
1122 883 markom 
  cuc_timings timings;
1123 
 
1124 
  analyse_timings (f, &timings);
1125 
  main_list = NULL;
1126 
  for (b = 0; b < f->num_bb; b++) {
1127 
    assert (iteration = (int *)malloc (sizeof (int) * f->bb[b].ninsn));
1128 
    for (i = 0; i < f->bb[b].ninsn; i++) {
1129 
      int cnt = 0, cntc = 0;
1130 
      double size = 0., sizec = 0.;
1131 
      int j2 = 0;
1132 
      for (j = 0; j < f->bb[b].ninsn; j++)
1133 
        if (f->bb[b].insn[i].index == f->bb[b].insn[j].index) {
1134 
          int ok = 1;
1135 
          for (j2 = 0; j2 < MAX_OPERANDS; j2++) if (!(f->bb[b].insn[j].opt[j2] & OPT_REF))
1136 
            if (f->bb[b].insn[j].opt[j2] != f->bb[b].insn[i].opt[j2]
1137 
             || f->bb[b].insn[j].op[j2] != f->bb[b].insn[i].opt[j2]) {
1138 
              ok = 0;
1139 
              break;
1140 
            }
1141 
          if (ok) {
1142 
            cntc++;
1143 
            sizec = sizec + insn_size (&f->bb[b].insn[j]);
1144 
          } else {
1145 
            cnt++;
1146 
            size = size + insn_size (&f->bb[b].insn[j]);
1147 
          }
1148 
          iteration[j] = 0;
1149 
        } else iteration[j] = -1;
1150 
      if (cntc > 1) {
1151 897 markom 
        assert (list = (cuc_shared_list *)malloc (sizeof (cuc_shared_list)));
1152 883 markom 
        list->next = main_list;
1153 
        list->from = NULL;
1154 
        list->ref = REF (b, i);
1155 
        list->cnt = cnt;
1156 
        list->cmatch = 1;
1157 
        list->cmovs = count_cmovs (&f->bb[b].insn[i], 3);
1158 
        list->osize = sizec;
1159 
        list->size = ii_size (f->bb[b].insn[i].index, 1);
1160 
        main_list = list;
1161 
        search_csm (0, f, list);
1162 
      }
1163 
      if (cnt > 1) {
1164 897 markom 
        assert (list = (cuc_shared_list *)malloc (sizeof (cuc_shared_list)));
1165 883 markom 
        list->next = main_list;
1166 
        list->from = NULL;
1167 
        list->ref = REF (b, i);
1168 
        list->cnt = cnt + cntc;
1169 
        list->cmatch = 0;
1170 
        list->cmovs = count_cmovs (&f->bb[b].insn[i], 2);
1171 
        list->osize = size + sizec;
1172 
        list->size = ii_size (f->bb[b].insn[i].index, 0);
1173 
        main_list = list;
1174 
        search_csm (0, f, list);
1175 
      }
1176 
    }
1177 
    free (iteration);
1178 
  }
1179 
 
1180 
  for (list = main_list; list; list = list->next) list->dead = 0;
1181 
  cnt = 0;
1182 
  for (list = main_list; list; list = list->next) if (!list->dead) cnt++;
1183 
  cucdebug (1, "noptions = %i\n", cnt);
1184 
 
1185 
  /* Now we will check the real size of the 'improvements'; if the size
1186 
     actually increases, we abandom the option */
1187 
  for (list = main_list; list; list = list->next)
1188 
    if (list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size >= list->osize) list->dead = 1;
1189 
 
1190 
  cnt = 0;
1191 
  for (list = main_list; list; list = list->next) if (!list->dead) cnt++;
1192 
  cucdebug (1, "noptions = %i\n", cnt);
1193 
 
1194 
  /* Count number of instructions grouped */
1195 
  for (list = main_list; list; list = list->next) {
1196 897 markom 
    cuc_shared_list *l = list;
1197 883 markom 
    int c = 0;
1198 
    while (l) {
1199 
      c++;
1200 
      if (f->INSN(l->ref).type & (IT_VOLATILE | IT_MEMORY | IT_MEMADD)) list->dead = 1;
1201 
      l = l->from;
1202 
    }
1203 
    list->ninsn = c;
1204 
  }
1205 
 
1206 
  cnt = 0;
1207 
  for (list = main_list; list; list = list->next)
1208 
    if (!list->dead) cnt++;
1209 
  cucdebug (1, "noptions = %i\n", cnt);
1210 
 
1211 
#if 1
1212 
  /* We can get a lot of options here, so we will delete duplicates */
1213 
  for (list = main_list; list; list = list->next) if (!list->dead) {
1214 897 markom 
    cuc_shared_list *l;
1215 883 markom 
    for (l = list->next; l; l = l->next) if (!l->dead) {
1216 
      int ok = 1;
1217 897 markom 
      cuc_shared_list *t1 = list;
1218 
      cuc_shared_list *t2 = l;
1219 883 markom 
      while (ok && t1 && t2) {
1220 
        if (f->INSN(t1->ref).index == f->INSN(t2->ref).index) {
1221 
          /* If other operands are matching, we must check for them also */
1222 
          if (t1->cmatch) {
1223 
            int j;
1224 
            for (j = 0; j < MAX_OPERANDS; j++)
1225 
              if (!(f->INSN(t1->ref).opt[j] & OPT_REF) || !(f->INSN(t2->ref).opt[j] & OPT_REF)
1226 
               || f->INSN(t1->ref).opt[j] != f->INSN(t2->ref).opt[j]
1227 
               || f->INSN(t1->ref).op[j] != f->INSN(t2->ref).op[j]) {
1228 
                ok = 0;
1229 
                break;
1230 
              }
1231 
          }
1232 
 
1233 
          /* This option is duplicate, remove */
1234 
          if (ok) t1->dead = 1;
1235 
        }
1236 
        t1 = t1->from;
1237 
        t2 = t2->from;
1238 
      }
1239 
    }
1240 
  }
1241 
  cnt = 0;
1242 
  for (list = main_list; list; list = list->next) if (!list->dead) cnt++;
1243 
  cucdebug (1, "noptions = %i\n", cnt);
1244 
#endif
1245 
  /* Print out */
1246 
  for (list = main_list; list; list = list->next) if (!list->dead) {
1247 897 markom 
    cuc_shared_list *l = list;
1248 883 markom 
    cucdebug (1, "%-4s cnt %3i ninsn %3i size %8.1f osize %8.1f cmovs %3i @",
1249 
           cuc_insn_name (&f->INSN(list->ref)), list->cnt, list->ninsn,
1250 
           list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size, list->osize, list->cmovs);
1251 
    while (l) {
1252 
      cucdebug (1, "%c%x,", l->cmatch ? '.' : '!', l->ref);
1253 
      l = l->from;
1254 
    }
1255 
    cucdebug (1, "\n");
1256 
  }
1257 
 
1258 
  /* Calculate estimated timings */
1259 
  for (b = 0; b < f->num_bb; b++) {
1260 
    cnt = 0;
1261 
    for (list = main_list; list; list = list->next)
1262 
      if (!list->dead && REF_BB(list->ref) == b) cnt++;
1263 
 
1264 
    f->bb[b].ntim = cnt;
1265 
    if (!cnt) {
1266 
      f->bb[b].tim = NULL;
1267 
      continue;
1268 
    }
1269 
    assert (f->bb[b].tim = (cuc_timings *)malloc (sizeof (cuc_timings) * cnt));
1270 
 
1271 
    cnt = 0;
1272 
    for (list = main_list; list; list = list->next) if (!list->dead && REF_BB(list->ref) == b) {
1273 897 markom 
      cuc_shared_list *l = list;
1274 883 markom 
      f->bb[b].tim[cnt].b = b;
1275 
      f->bb[b].tim[cnt].preroll = f->bb[b].tim[cnt].unroll = 1;
1276 
      f->bb[b].tim[cnt].nshared = list->ninsn;
1277 897 markom 
      assert (f->bb[b].tim[cnt].shared = (cuc_shared_item *)
1278 
            malloc (sizeof(cuc_shared_item) * list->ninsn));
1279 
      for (i =  0; i < list->ninsn; i++, l = l->from) {
1280 
        f->bb[b].tim[cnt].shared[i].ref = l->ref;
1281 
        f->bb[b].tim[cnt].shared[i].cmatch = l->cmatch;
1282 
      }
1283 883 markom 
      f->bb[b].tim[cnt].new_time = timings.new_time + f->bb[b].cnt * (list->cnt - 1);
1284 897 markom 
      f->bb[b].tim[cnt].size = timings.size +
1285 
             list->cmovs * ii_size (II_CMOV, 0) * (list->cnt - 1) + list->size - list->osize;
1286 883 markom 
      cnt++;
1287 
    }
1288 
  }
1289 
}
1290 
 
1291 
/* Recursive function for searching through instruction graph */
1292 897 markom 
static void search_csm (int iter, cuc_func *f, cuc_shared_list *list)
1293 883 markom 
{
1294 
  int b, i, j, i1;
1295 897 markom 
  cuc_shared_list *l;
1296 883 markom 
  b = REF_BB(list->ref);
1297 
  i = REF_I(list->ref);
1298 
 
1299 
  for (j = 0; j < MAX_OPERANDS; j++) if (f->bb[b].insn[i].opt[j] & OPT_REF) {
1300 
    int t = f->bb[b].insn[i].op[j];
1301 
    int cnt = 0, cntc = 0;
1302 
    double size = 0., sizec = 0.;
1303 
 
1304 
    /* Mark neighbours */
1305 
    for (i1 = 0; i1 < f->bb[b].ninsn; i1++) {
1306 
      if (iteration[i1] == iter && f->bb[b].insn[i1].opt[j] & OPT_REF) {
1307 
        int t2 = f->bb[b].insn[i1].op[j];
1308 
        if (f->INSN(t).index == f->INSN(t2).index && f->INSN(t2).opt[j] & OPT_REF) {
1309 
          int j2;
1310 
          int ok = 1;
1311 
          iteration[REF_I(t2)] = iter + 1;
1312 
          for (j2 = 0; j2 < MAX_OPERANDS; j2++) if (!(f->bb[b].insn[i1].opt[j2] & OPT_REF))
1313 
            if (f->bb[b].insn[i1].opt[j2] != f->bb[b].insn[i].opt[j2]
1314 
             || f->bb[b].insn[i1].op[j2] != f->bb[b].insn[i].opt[j2]) {
1315 
              ok = 0;
1316 
              break;
1317 
            }
1318 
          if (ok) {
1319 
            cntc++;
1320 
            sizec = sizec + insn_size (&f->bb[b].insn[i1]);
1321 
          } else {
1322 
            cnt++;
1323 
            size = size + insn_size (&f->bb[b].insn[i1]);
1324 
          }
1325 
        }
1326 
      }
1327 
    }
1328 
 
1329 
    if (cntc > 1) {
1330 897 markom 
      assert (l = (cuc_shared_list *)malloc (sizeof (cuc_shared_list)));
1331 883 markom 
      l->next = main_list;
1332 
      main_list = l;
1333 
      l->from = list;
1334 
      l->ref = t;
1335 
      l->cnt = cnt;
1336 
      l->cmatch = 1;
1337 
      l->cmovs = list->cmovs + count_cmovs (&f->bb[b].insn[i], 1) - 1;
1338 
      l->size = list->size + ii_size (f->bb[b].insn[i].index, 1);
1339 
      l->osize = sizec;
1340 
      search_csm (iter + 1, f, l);
1341 
    }
1342 
    if (cnt > 1) {
1343 897 markom 
      assert (l = (cuc_shared_list *)malloc (sizeof (cuc_shared_list)));
1344 883 markom 
      l->next = main_list;
1345 
      main_list = l;
1346 
      l->from = list;
1347 
      l->ref = t;
1348 
      l->cnt = cnt + cntc;
1349 
      l->cmatch = 0;
1350 
      l->osize = size + sizec;
1351 
      l->cmovs = list->cmovs + count_cmovs (&f->bb[b].insn[i], 0) - 1;
1352 
      l->size = list->size + ii_size (f->bb[b].insn[i].index, 0);
1353 
      search_csm (iter + 1, f, l);
1354 
    }
1355 
 
1356 
    /* Unmark them back */
1357 
    for (i1 = 0; i1 < f->bb[b].ninsn; i1++) if (iteration[i1] > iter) iteration[i1] = -1;
1358 
  }
1359 
}
1360 
 
1361 897 markom 
/* Displays shared instructions */
1362 
void print_shared (cuc_func *rf, cuc_shared_item *shared, int nshared)
1363 
{
1364 
  int i, first = 1;
1365 
  for (i = 0; i < nshared; i++) {
1366 997 markom 
    PRINTF ("%s%s%s", first ? "" : "-", cuc_insn_name (&rf->INSN(shared[i].ref)),
1367 897 markom 
                    shared[i].cmatch ? "!" : "");
1368 
    first = 0;
1369 
  }
1370 
}
1371 
 
1372 
/* Common subexpression matching -- resource sharing, generation pass
1373 
 
1374 
   Situation here is much simpler than with analysis -- we know the instruction sequence
1375 
   we are going to share, but we are going to do this on whole function, not just one BB.
1376 
   We can find sequence in reference function, as pointed from "shared" */
1377 
void csm_gen (cuc_func *f, cuc_func *rf, cuc_shared_item *shared, int nshared)
1378 
{
1379 
  int b, i, j, cnt = 0;
1380 
#warning   some code here (2)
1381 997 markom 
  PRINTF ("Replacing: ");
1382 897 markom 
  print_shared (rf, shared, nshared);
1383 
 
1384 
  for (b = 0; b < f->num_bb; b++)
1385 
    for (i = 0; i < f->bb[b].ninsn; i++) {
1386 
    }
1387 
 
1388 997 markom 
  PRINTF ("\nFound %i matches.\n", cnt);
1389 897 markom 
}
1390 
 

powered by: WebSVN 2.1.0

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