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

Subversion Repositories or1k

[/] [or1k/] [tags/] [nog_patch_34/] [or1ksim/] [cuc/] [insn.c] - Blame information for rev 1046

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

powered by: WebSVN 2.1.0

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