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

Subversion Repositories or1k

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

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

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

powered by: WebSVN 2.1.0

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