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

Subversion Repositories or1k

[/] [or1k/] [tags/] [nog_patch_69/] [or1ksim/] [cuc/] [insn.c] - Blame information for rev 932

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

powered by: WebSVN 2.1.0

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