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

Subversion Repositories or1k

[/] [or1k/] [trunk/] [or1ksim/] [cuc/] [insn.c] - Blame information for rev 931

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

powered by: WebSVN 2.1.0

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