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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [or1ksim/] [cuc/] [adv.c] - Blame information for rev 609

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

Line No. Rev Author Line
1 19 jeremybenn
/* adv.c -- OpenRISC Custom Unit Compiler, Advanced Optimizations
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
 
25
#include "config.h"
26
 
27
#include "port.h"
28
#include "arch.h"
29
#include "sim-config.h"
30
#include "abstract.h"
31
#include "cuc.h"
32
#include "insn.h"
33
#include "support/profile.h"
34
#include "misc.h"
35
 
36
/* Marks successor of b with mask m */
37
static void mark_successors (cuc_func *f, int b, int m, int stopb)
38
{
39
  if (b < 0 || b == BBID_END) return;
40
  if (f->bb[b].tmp & m) return;
41
  f->bb[b].tmp |= m;
42
  /* mark stopb also; and stop searching -- we will gen new result in stopb */
43
  if (b == stopb) return;
44
  mark_successors (f, f->bb[b].next[0], m, stopb);
45
  mark_successors (f, f->bb[b].next[1], m, stopb);
46
}
47
 
48
static unsigned long mask (unsigned long c)
49
{
50
  if (c) return (1 << (log2_int (c) + 1)) - 1;
51
  else return 0;
52
}
53
 
54
/* Calculates facts, that are determined by conditionals */
55
void insert_conditional_facts (cuc_func *f)
56
{
57
  int b, j;
58
  int b1, i1, j1;
59
  cuc_insn n[2];
60
  for (b = 0; b < f->num_bb; b++) if (f->bb[b].ninsn > 0) {
61
    cuc_insn *ii = &f->bb[b].insn[f->bb[b].ninsn - 1];
62
    /* We have following situation
63
       x <= ...
64
       sfxx f, x, CONST
65
       bf ..., f */
66
    if (ii->type & IT_BRANCH && ii->opt[1] & OPT_REF && REF_BB(ii->op[1]) == b
67
     && f->INSN(ii->op[1]).opt[2] & OPT_CONST) {
68
      int ok = 0;
69
      unsigned long c = f->INSN(ii->op[1]).op[2];
70
      int rref = f->INSN(ii->op[1]).op[1];
71
      unsigned long r;
72
      if (!(f->INSN(ii->op[1]).opt[1] & OPT_REF)) continue;
73
      r = f->INSN(rref).op[0];
74
 
75
      /* Assignment must be in same basic block */
76
      if (REF_BB(rref) != b) continue;
77
 
78
      for (j = 0; j < 2; j++) {
79
        change_insn_type (&n[j], II_ADD);
80
        n[j].type = 0;
81
        n[j].dep = NULL;
82
        n[j].op[0] = r; n[j].opt[0] = OPT_REGISTER | OPT_DEST;
83
        n[j].op[1] = 0; n[j].opt[1] = OPT_CONST;
84
        n[j].op[2] = rref; n[j].opt[2] = OPT_REF;
85
        n[j].opt[3] = OPT_NONE;
86
        sprintf (n[j].disasm, "conditional %s fact", j ? "false" : "true");
87
      }
88
 
89
      /* First get the conditional and two instruction to place after the current BB */
90
      switch (f->INSN(ii->op[1]).index) {
91
        case II_SFEQ:
92
          change_insn_type (&n[0], II_ADD);
93
          n[0].op[0] = r; n[0].opt[0] = OPT_REGISTER | OPT_DEST;
94
          n[0].op[1] = 0; n[0].opt[1] = OPT_CONST;
95
          n[0].op[2] = c; n[0].opt[2] = OPT_CONST;
96
          ok = 1;
97
          break;
98
        case II_SFNE:
99
          change_insn_type (&n[1], II_ADD);
100
          n[1].op[0] = r; n[1].opt[0] = OPT_REGISTER | OPT_DEST;
101
          n[1].op[1] = 0; n[1].opt[1] = OPT_CONST;
102
          n[1].op[2] = c; n[1].opt[2] = OPT_CONST;
103
          ok = 2;
104
          break;
105
        case II_SFLT:
106
          change_insn_type (&n[0], II_AND);
107
          n[0].op[0] = r; n[0].opt[0] = OPT_REGISTER | OPT_DEST;
108
          n[0].op[1] = rref; n[0].opt[1] = OPT_REF;
109
          n[0].op[2] = mask (c); n[0].opt[2] = OPT_CONST;
110
          ok = 1;
111
          break;
112
        case II_SFGT:
113
          change_insn_type (&n[1], II_ADD);
114
          n[1].op[0] = r; n[1].opt[0] = OPT_REGISTER | OPT_DEST;
115
          n[1].op[1] = rref; n[1].opt[1] = OPT_REF;
116
          n[1].op[2] = mask (c + 1); n[1].opt[2] = OPT_CONST;
117
          ok = 2;
118
          break;
119
        case II_SFLE:
120
          change_insn_type (&n[0], II_AND);
121
          n[0].op[0] = r; n[0].opt[0] = OPT_REGISTER | OPT_DEST;
122
          n[0].op[1] = rref; n[0].opt[1] = OPT_REF;
123
          n[0].op[2] = mask (c); n[0].opt[2] = OPT_CONST;
124
          ok = 1;
125
          break;
126
        case II_SFGE:
127
          change_insn_type (&n[1], II_ADD);
128
          n[1].op[0] = r; n[1].opt[0] = OPT_REGISTER | OPT_DEST;
129
          n[1].op[1] = rref; n[1].opt[1] = OPT_REF;
130
          n[1].op[2] = mask (c + 1); n[1].opt[2] = OPT_CONST;
131
          ok = 2;
132
          break;
133
        default:
134
          ok = 0;
135
          break;
136
      }
137
 
138
      /* Now add two BBs at the end and relink */
139
      if (ok) {
140
        int cnt = 0;
141
        cucdebug (1, "%x rref %x cnt %i\n", b, rref, cnt);
142
        fflush (stdout);
143
        for (j = 0; j < 2; j++) {
144
          int nb = f->num_bb++;
145
          int sb;
146
          assert (nb < MAX_BB);
147
          f->bb[nb].type = 0;
148
          f->bb[nb].first = -1; f->bb[nb].last = -1;
149
          f->bb[nb].prev[0] = b; f->bb[nb].prev[1] = -1;
150
          sb = f->bb[nb].next[0] = f->bb[b].next[j]; f->bb[nb].next[1] = -1;
151
          assert (cnt >= 0);
152
          cucdebug (2, "%x %x %x rref %x cnt %i\n", b, sb, nb, rref, cnt);
153
          fflush (stdout);
154
          assert (sb >= 0);
155
          f->bb[b].next[j] = nb;
156
          if (sb != BBID_END) {
157
            if (f->bb[sb].prev[0] == b) f->bb[sb].prev[0] = nb;
158
            else if (f->bb[sb].prev[1] == b) f->bb[sb].prev[1] = nb;
159
            else assert (0);
160
          }
161
          f->bb[nb].insn = (cuc_insn *) malloc (sizeof (cuc_insn) * (cnt + 1));
162
          assert (f->bb[nb].insn);
163
          f->bb[nb].insn[0] = n[j];
164
          f->bb[nb].ninsn = cnt + 1;
165
          f->bb[nb].mdep = NULL;
166
          f->bb[nb].nmemory = 0;
167
          f->bb[nb].cnt = 0;
168
          f->bb[nb].unrolled = 0;
169
          f->bb[nb].ntim = 0;
170
          f->bb[nb].selected_tim = -1;
171
        }
172
        for (b1 = 0; b1 < f->num_bb; b1++) f->bb[b1].tmp = 0;
173
 
174
        /* Find successor blocks and change links accordingly */
175
        mark_successors (f, f->num_bb - 2, 2, b);
176
        mark_successors (f, f->num_bb - 1, 1, b);
177
        for (b1 = 0; b1 < f->num_bb - 2; b1++) if (f->bb[b1].tmp == 1 || f->bb[b1].tmp == 2) {
178
          int end;
179
          if (REF_BB (rref) == b1) end = REF_I (rref) + 1;
180
          else end = f->bb[b1].ninsn;
181
          for (i1 = 0; i1 < end; i1++)
182
            for (j1 = 0; j1 < MAX_OPERANDS; j1++)
183
              if (f->bb[b1].insn[i1].opt[j1] & OPT_REF && f->bb[b1].insn[i1].op[j1] == rref)
184
                f->bb[b1].insn[i1].op[j1] = REF (f->num_bb - f->bb[b1].tmp, 0);
185
        }
186
        if (cuc_debug >= 3) print_cuc_bb (f, "FACT");
187
      }
188
    }
189
  }
190
}
191
 
192
static unsigned long max_op (cuc_func *f, int ref, int o)
193
{
194
  if (f->INSN(ref).opt[o] & OPT_REF) return f->INSN(f->INSN(ref).op[o]).max;
195
  else if (f->INSN(ref).opt[o] & OPT_CONST) return f->INSN(ref).op[o];
196
  else if (f->INSN(ref).opt[o] & OPT_REGISTER) return 0xffffffff;
197
  else assert (0);
198
  return 0;
199
}
200
 
201
/* Returns maximum value, based on inputs */
202
static unsigned long calc_max (cuc_func *f, int ref)
203
{
204
  cuc_insn *ii = &f->INSN(ref);
205
  if (ii->type & IT_COND) return 1;
206
  switch (ii->index) {
207
    case II_ADD : return MIN ((unsigned long long) max_op (f, ref, 1)
208
                            + (unsigned long long)max_op (f, ref, 2), 0xffffffff);
209
    case II_SUB : return 0xffffffff;
210
    case II_AND : return MIN (max_op (f, ref, 1), max_op (f, ref, 2));
211
    case II_OR  : return max_op (f, ref, 1) | max_op (f, ref, 2);
212
    case II_XOR : return max_op (f, ref, 1) | max_op (f, ref, 2);
213
    case II_MUL : return MIN ((unsigned long long) max_op (f, ref, 1)
214
                            * (unsigned long long)max_op (f, ref, 2), 0xffffffff);
215
    case II_SLL : if (ii->opt[2] & OPT_CONST) return max_op (f, ref, 1) << ii->op[2];
216
                  else return max_op (f, ref, 1);
217
    case II_SRA : return max_op (f, ref, 1);
218
    case II_SRL : if (ii->opt[2] & OPT_CONST) return max_op (f, ref, 1) >> ii->op[2];
219
                  else return max_op (f, ref, 1);
220
    case II_LB  : return 0xff;
221
    case II_LH  : return 0xffff;
222
    case II_LW  : return 0xffffffff;
223
    case II_SB  :
224
    case II_SH  :
225
    case II_SW  : return 0;
226
    case II_SFEQ:
227
    case II_SFNE:
228
    case II_SFLE:
229
    case II_SFLT:
230
    case II_SFGE:
231
    case II_SFGT: return 1;
232
    case II_BF  : return 0;
233
    case II_LRBB: return 1;
234
    case II_CMOV: return MAX (max_op (f, ref, 1), max_op (f, ref, 2));
235
    case II_REG : return max_op (f, ref, 1);
236
    case II_NOP : assert (0);
237
    case II_CALL: assert (0);
238
    default:  assert (0);
239
  }
240
  return -1;
241
}
242
 
243
/* Width optimization -- detect maximum values;
244
   these values are actually estimates, since the problem
245
   is to hard otherwise...
246
   We calculate these maximums iteratively -- we are slowly
247
   approaching final solution. This algorithm is surely finite,
248
   but can be very slow; so we stop after some iterations;
249
   normal loops should be in this range */
250
void detect_max_values (cuc_func *f)
251
{
252
  int b, i;
253
  int modified = 0;
254
  int iteration = 0;
255
 
256
  for (b = 0; b < f->num_bb; b++) {
257
    for (i = 0; i < f->bb[b].ninsn; i++) f->bb[b].insn[i].max = 0;
258
    f->bb[b].tmp = 1;
259
  }
260
 
261
  /* Repeat until something is changing */
262
  do {
263
    modified = 0;
264
    for (b = 0; b < f->num_bb; b++) {
265
      if (f->bb[b].tmp) {
266
        for (i = 0; i < f->bb[b].ninsn; i++) {
267
          unsigned long m = calc_max (f, REF (b, i));
268
          if (m > f->bb[b].insn[i].max) {
269
            f->bb[b].insn[i].max = m;
270
            modified = 1;
271
          }
272
        }
273
      }
274
    }
275
    if (iteration++ > CUC_WIDTH_ITERATIONS) break;
276
  } while (modified);
277
 
278
  /* Something bad has happened; now we will assign 0xffffffff to all unsatisfied
279
     instructions; this one is stoppable in O(n ^ 2) */
280
  if (iteration > CUC_WIDTH_ITERATIONS) {
281
    do {
282
      modified = 0;
283
      for (b = 0; b < f->num_bb; b++)
284
        for (i = 0; i < f->bb[b].ninsn; i++) {
285
          unsigned long m = calc_max (f, REF (b, i));
286
          if (m > f->bb[b].insn[i].max) {
287
            f->bb[b].insn[i].max = 0xffffffff;
288
            modified = 1;
289
          }
290
        }
291
    } while (modified);
292
  }
293
  cucdebug (1, "detect_max_values %i iterations\n", iteration);
294
}
295
 

powered by: WebSVN 2.1.0

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