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

Subversion Repositories or1k

[/] [or1k/] [branches/] [stable_0_2_x/] [or1ksim/] [cuc/] [insn.c] - Blame information for rev 1047

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

powered by: WebSVN 2.1.0

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