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 939

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

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