1 |
879 |
markom |
/* bb.c -- OpenRISC Custom Unit Compiler, Basic Block handling
|
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 |
|
|
#include "abstract.h"
|
26 |
879 |
markom |
#include "cuc.h"
|
27 |
|
|
#include "insn.h"
|
28 |
|
|
#include "support/profile.h"
|
29 |
|
|
|
30 |
|
|
/* Print out basic blocks */
|
31 |
|
|
void print_cuc_bb (cuc_func *f, char *s)
|
32 |
|
|
{
|
33 |
|
|
int i;
|
34 |
|
|
printf ("------- %s -------\n", s);
|
35 |
|
|
for (i = 0; i < f->num_bb; i++) {
|
36 |
|
|
if (f->bb[i].insn) printf ("\n---- BB%-2x * %x ---- ", i, f->bb[i].cnt);
|
37 |
|
|
else printf ("BB%-2x: %4x-%-4x", i, f->bb[i].first, f->bb[i].last);
|
38 |
|
|
printf (" type %02x tmp %i ", f->bb[i].type, f->bb[i].tmp);
|
39 |
|
|
if (f->bb[i].next[0] >= 0) printf ("next %2x ", f->bb[i].next[0]);
|
40 |
|
|
else printf ("next * ");
|
41 |
|
|
if (f->bb[i].next[1] >= 0) printf ("%2x ", f->bb[i].next[1]);
|
42 |
|
|
else printf ("* ");
|
43 |
|
|
if (f->bb[i].prev[0] >= 0) printf ("prev %2x ", f->bb[i].prev[0]);
|
44 |
|
|
else printf ("prev * ");
|
45 |
|
|
if (f->bb[i].prev[1] >= 0) printf ("%2x\n", f->bb[i].prev[1]);
|
46 |
|
|
else printf ("*\n");
|
47 |
|
|
|
48 |
|
|
if (f->bb[i].insn) print_insns (f->bb[i].insn, f->bb[i].ninsn, 0);
|
49 |
|
|
}
|
50 |
|
|
printf ("\n");
|
51 |
897 |
markom |
fflush (stdout);
|
52 |
879 |
markom |
}
|
53 |
|
|
|
54 |
|
|
/* Copies src basic block into destination */
|
55 |
|
|
cuc_bb *cpy_bb (cuc_bb *dest, cuc_bb *src)
|
56 |
|
|
{
|
57 |
897 |
markom |
int i, j;
|
58 |
|
|
assert (dest != src);
|
59 |
879 |
markom |
*dest = *src;
|
60 |
|
|
assert (dest->insn = malloc (sizeof (cuc_insn) * src->ninsn));
|
61 |
|
|
for (i = 0; i < src->ninsn; i++)
|
62 |
|
|
dest->insn[i] = src->insn[i];
|
63 |
|
|
if (src->ntim) {
|
64 |
|
|
assert (dest->tim = malloc (sizeof (cuc_timings) * src->ntim));
|
65 |
897 |
markom |
for (i = 0; i < src->ntim; i++) {
|
66 |
|
|
dest->tim[i] = src->tim[i];
|
67 |
|
|
if (src->tim[i].nshared) {
|
68 |
|
|
assert (dest->tim[i].shared = malloc (sizeof (int) * src->tim[i].nshared));
|
69 |
|
|
for (j = 0; j < src->tim[i].nshared; j++)
|
70 |
|
|
dest->tim[i].shared[j] = src->tim[i].shared[j];
|
71 |
|
|
}
|
72 |
|
|
}
|
73 |
879 |
markom |
}
|
74 |
|
|
}
|
75 |
|
|
|
76 |
|
|
/* Duplicates function */
|
77 |
|
|
cuc_func *dup_func (cuc_func *f)
|
78 |
|
|
{
|
79 |
|
|
cuc_func *n = (cuc_func *) malloc (sizeof (cuc_func));
|
80 |
|
|
int b, i;
|
81 |
|
|
for (b = 0; b < f->num_bb; b++) cpy_bb (&n->bb[b], &f->bb[b]);
|
82 |
|
|
n->num_bb = f->num_bb;
|
83 |
|
|
assert (n->init_bb_reloc = (int *)malloc (sizeof (int) * f->num_init_bb));
|
84 |
|
|
for (b = 0; b < f->num_init_bb; b++) n->init_bb_reloc[b] = f->init_bb_reloc[b];
|
85 |
|
|
n->num_init_bb = f->num_init_bb;
|
86 |
|
|
for (i = 0; i < MAX_REGS; i++) n->saved_regs[i] = f->saved_regs[i];
|
87 |
|
|
n->start_addr = f->start_addr;
|
88 |
|
|
n->end_addr = f->end_addr;
|
89 |
|
|
n->orig_time = f->orig_time;
|
90 |
|
|
n->nmsched = f->nmsched;
|
91 |
|
|
for (i = 0; i < f->nmsched; i++) {
|
92 |
|
|
n->msched[i] = f->msched[i];
|
93 |
|
|
n->mtype[i] = f->mtype[i];
|
94 |
|
|
}
|
95 |
|
|
return n;
|
96 |
|
|
}
|
97 |
|
|
|
98 |
|
|
/* Releases memory allocated by function */
|
99 |
|
|
void free_func (cuc_func *f)
|
100 |
|
|
{
|
101 |
|
|
int b, i;
|
102 |
|
|
for (b = 0; b < f->num_bb; b++) {
|
103 |
|
|
for (i = 0; i < f->bb[b].ninsn; i++)
|
104 |
|
|
dispose_list (&f->bb[b].insn[i].dep);
|
105 |
|
|
if (f->bb[b].insn) free (f->bb[b].insn);
|
106 |
897 |
markom |
for (i = 0; i < f->bb[b].ntim; i++)
|
107 |
|
|
if (f->bb[b].tim[i].nshared && f->bb[b].tim[i].shared)
|
108 |
|
|
free (f->bb[b].tim[i].shared);
|
109 |
879 |
markom |
if (f->bb[b].tim && f->bb[b].ntim) free (f->bb[b].tim);
|
110 |
|
|
}
|
111 |
|
|
free (f);
|
112 |
|
|
}
|
113 |
|
|
|
114 |
|
|
|
115 |
|
|
/* Recalculates last_used_reg */
|
116 |
|
|
void recalc_last_used_reg (cuc_func *f, int b)
|
117 |
|
|
{
|
118 |
|
|
int i;
|
119 |
|
|
cuc_bb *bb = &f->bb[b];
|
120 |
|
|
|
121 |
|
|
/* rebuild last used reg array */
|
122 |
|
|
if (bb->insn[0].index == II_LRBB) bb->last_used_reg[LRBB_REG] = 0;
|
123 |
|
|
else bb->last_used_reg[LRBB_REG] = -1;
|
124 |
|
|
|
125 |
|
|
for (i = 1; i < MAX_REGS - 1; i++) bb->last_used_reg[i] = -1;
|
126 |
|
|
|
127 |
|
|
/* Create references */
|
128 |
|
|
for (i = 0; i < bb->ninsn; i++) {
|
129 |
|
|
int k;
|
130 |
|
|
/* Now check for destination operand(s) */
|
131 |
|
|
for (k = 0; k < MAX_OPERANDS; k++) if (bb->insn[i].opt[k] & OPT_DEST)
|
132 |
|
|
if ((bb->insn[i].opt[k] & ~OPT_DEST) == OPT_REGISTER
|
133 |
|
|
&& (int)bb->insn[i].op[k] >= 0) {
|
134 |
|
|
bb->last_used_reg[bb->insn[i].op[k]] = REF (b, i);
|
135 |
|
|
}
|
136 |
|
|
}
|
137 |
|
|
}
|
138 |
|
|
|
139 |
|
|
/* Set the BB limits */
|
140 |
|
|
void detect_bb (cuc_func *f)
|
141 |
|
|
{
|
142 |
|
|
int i, j, end_bb = 0, eb = 0;
|
143 |
|
|
|
144 |
|
|
/* Mark block starts/ends */
|
145 |
|
|
for (i = 0; i < num_insn; i++) {
|
146 |
|
|
if (end_bb) insn[i].type |= IT_BBSTART;
|
147 |
|
|
end_bb = 0;
|
148 |
|
|
if (insn[i].type & IT_BRANCH) {
|
149 |
|
|
int jt = insn[i].op[0];
|
150 |
|
|
insn[i].type |= IT_BBEND;
|
151 |
|
|
end_bb = 1;
|
152 |
|
|
if (jt < 0 || jt >= num_insn) {
|
153 |
|
|
fprintf (stderr, "Instruction #%i:Jump out of function '%s'.\n", i, insn[i].disasm);
|
154 |
|
|
exit (1);
|
155 |
|
|
}
|
156 |
|
|
if (jt > 0) insn[jt - 1].type |= IT_BBEND;
|
157 |
|
|
insn[jt].type |= IT_BBSTART;
|
158 |
|
|
}
|
159 |
|
|
}
|
160 |
|
|
|
161 |
|
|
/* Initialize bb array */
|
162 |
|
|
insn[0].type |= IT_BBSTART;
|
163 |
|
|
insn[num_insn - 1].type |= IT_BBEND;
|
164 |
|
|
f->num_bb = 0;
|
165 |
|
|
for (i = 0; i < num_insn; i++) {
|
166 |
|
|
if (insn[i].type & IT_BBSTART) {
|
167 |
|
|
f->bb[f->num_bb].first = i;
|
168 |
|
|
f->bb[f->num_bb].cnt = 0;
|
169 |
|
|
}
|
170 |
|
|
/* Determine repetitions of a loop */
|
171 |
|
|
if (insn[i].type & IT_BBEND) {
|
172 |
|
|
f->bb[f->num_bb].type = 0;
|
173 |
|
|
f->bb[f->num_bb].last = i;
|
174 |
|
|
f->bb[f->num_bb].next[0] = f->bb[f->num_bb].next[1] = -1;
|
175 |
|
|
f->bb[f->num_bb].tmp = 0;
|
176 |
|
|
f->bb[f->num_bb].ntim = 0;
|
177 |
|
|
f->num_bb++;
|
178 |
|
|
assert (f->num_bb < MAX_BB);
|
179 |
|
|
}
|
180 |
|
|
}
|
181 |
883 |
markom |
if (cuc_debug >= 3) print_cuc_bb (f, "AFTER_INIT");
|
182 |
879 |
markom |
|
183 |
|
|
/* Build forward connections between BBs */
|
184 |
|
|
for (i = 0; i < f->num_bb; i++)
|
185 |
|
|
if (insn[f->bb[i].last].type & IT_BRANCH) {
|
186 |
|
|
int j;
|
187 |
|
|
assert (insn[f->bb[i].last].index == II_BF);
|
188 |
|
|
/* Find block this instruction jumps to */
|
189 |
|
|
for (j = 0; j < f->num_bb; j++)
|
190 |
|
|
if (f->bb[j].first == insn[f->bb[i].last].op[0]) break;
|
191 |
|
|
assert (j < f->num_bb);
|
192 |
|
|
|
193 |
|
|
/* Convert the jump address to BB link */
|
194 |
|
|
insn[f->bb[i].last].op[0] = j; insn[f->bb[i].last].opt[0] = OPT_BB;
|
195 |
|
|
|
196 |
|
|
/* Make a link */
|
197 |
|
|
f->bb[i].next[0] = j;
|
198 |
|
|
if (++f->bb[j].tmp > 2) eb++;
|
199 |
|
|
f->bb[i].next[1] = i + 1;
|
200 |
|
|
if (++f->bb[i + 1].tmp > 2) eb++;
|
201 |
|
|
} else if (f->bb[i].last == num_insn - 1) { /* Last instruction doesn't have to do anything */
|
202 |
|
|
f->bb[i].type |= BB_END;
|
203 |
|
|
} else {
|
204 |
|
|
f->bb[i].next[0] = i + 1;
|
205 |
|
|
if (++f->bb[i + 1].tmp > 2) eb++;
|
206 |
|
|
}
|
207 |
|
|
|
208 |
883 |
markom |
if (cuc_debug >= 3) print_cuc_bb (f, "AFTER_NEXT");
|
209 |
879 |
markom |
|
210 |
|
|
/* Build backward connections, but first insert artificial blocks
|
211 |
|
|
* to handle more than 2 connections */
|
212 |
883 |
markom |
cucdebug (6, "artificial %i %i\n", f->num_bb, eb);
|
213 |
879 |
markom |
end_bb = f->num_bb + eb;
|
214 |
|
|
for (i = f->num_bb - 1; i >= 0; i--) {
|
215 |
|
|
j = f->bb[i].tmp;
|
216 |
|
|
if (f->bb[i].tmp > 2) f->bb[i].tmp = -f->bb[i].tmp;
|
217 |
|
|
f->bb[--end_bb] = f->bb[i];
|
218 |
|
|
reloc[i] = end_bb;
|
219 |
|
|
while (j-- > 2) {
|
220 |
|
|
f->bb[--end_bb].first = f->bb[i].first;
|
221 |
|
|
f->bb[end_bb].last = -1;
|
222 |
|
|
f->bb[end_bb].next[0] = -1;
|
223 |
|
|
f->bb[end_bb].next[1] = -1;
|
224 |
|
|
f->bb[end_bb].tmp = 0;
|
225 |
|
|
f->bb[end_bb].cnt = f->bb[i].cnt;
|
226 |
|
|
f->bb[end_bb].ntim = 0;
|
227 |
|
|
}
|
228 |
|
|
}
|
229 |
|
|
f->num_bb += eb;
|
230 |
|
|
|
231 |
|
|
/* relocate jump instructions */
|
232 |
|
|
for (i = 0; i < num_insn; i++)
|
233 |
|
|
for (j = 0; j < MAX_OPERANDS; j++)
|
234 |
|
|
if (insn[i].opt[j] & OPT_BB)
|
235 |
|
|
insn[i].op[j] = reloc[insn[i].op[j]];
|
236 |
883 |
markom |
if (cuc_debug >= 3) print_cuc_bb (f, "AFTER_INSERT-reloc");
|
237 |
879 |
markom |
for (i = 0; i < f->num_bb; i++) {
|
238 |
|
|
if (f->bb[i].next[0] >= 0) {
|
239 |
|
|
int t = reloc[f->bb[i].next[0]];
|
240 |
|
|
if (f->bb[t].tmp < 0) {
|
241 |
|
|
f->bb[t].tmp = -f->bb[t].tmp;
|
242 |
|
|
t -= f->bb[t].tmp - 2;
|
243 |
|
|
} else if (f->bb[t].tmp > 2) t -= f->bb[t].tmp-- - 2;
|
244 |
|
|
f->bb[i].next[0] = t;
|
245 |
|
|
}
|
246 |
|
|
if (f->bb[i].next[1] >= 0) {
|
247 |
|
|
int t = reloc[f->bb[i].next[1]];
|
248 |
|
|
if (f->bb[t].tmp < 0) {
|
249 |
|
|
f->bb[t].tmp = -f->bb[t].tmp;
|
250 |
|
|
t -= f->bb[t].tmp - 2;
|
251 |
|
|
} else if (f->bb[t].tmp > 2) t -= f->bb[t].tmp-- - 2;
|
252 |
|
|
f->bb[i].next[1] = t;
|
253 |
|
|
}
|
254 |
|
|
/* artificial blocks do not have relocations, hardcode them */
|
255 |
|
|
if (f->bb[i].last < 0) f->bb[i].next[0] = i + 1;
|
256 |
|
|
}
|
257 |
883 |
markom |
if (cuc_debug >= 3) print_cuc_bb (f, "AFTER_INSERT");
|
258 |
879 |
markom |
|
259 |
|
|
/* Uncoditional branched do not continue to next block */
|
260 |
|
|
for (i = 0; i < f->num_bb; i++) {
|
261 |
|
|
cuc_insn *ii;
|
262 |
|
|
if (f->bb[i].last < 0) continue;
|
263 |
|
|
ii = &insn[f->bb[i].last];
|
264 |
|
|
/* Unconditional branch? */
|
265 |
|
|
if (ii->type & IT_BRANCH && ii->opt[1] & OPT_CONST) {
|
266 |
|
|
change_insn_type (ii, II_NOP);
|
267 |
|
|
if (f->bb[i].next[1] == i + 1) f->bb[i].next[0] = f->bb[i].next[1];
|
268 |
|
|
f->bb[i].next[1] = -1;
|
269 |
|
|
}
|
270 |
|
|
}
|
271 |
883 |
markom |
if (cuc_debug >= 3) print_cuc_bb (f, "AFTER_UNCOND_JUMP");
|
272 |
879 |
markom |
|
273 |
|
|
/* Add backward connections */
|
274 |
|
|
for (i = 0; i < f->num_bb; i++)
|
275 |
|
|
f->bb[i].prev[0] = f->bb[i].prev[1] = -1;
|
276 |
|
|
|
277 |
|
|
for (i = 0; i < f->num_bb; i++) {
|
278 |
|
|
if (f->bb[i].next[0] >= 0) {
|
279 |
|
|
int t = f->bb[i].next[0];
|
280 |
|
|
if (f->bb[t].prev[0] < 0) f->bb[t].prev[0] = i;
|
281 |
|
|
else {
|
282 |
|
|
assert (f->bb[t].prev[1] < 0);
|
283 |
|
|
f->bb[t].prev[1] = i;
|
284 |
|
|
}
|
285 |
|
|
}
|
286 |
|
|
if (f->bb[i].next[1] >= 0) {
|
287 |
|
|
int t = f->bb[i].next[1];
|
288 |
|
|
if (f->bb[t].prev[0] < 0) f->bb[t].prev[0] = i;
|
289 |
|
|
else {
|
290 |
|
|
assert (f->bb[t].prev[1] < 0);
|
291 |
|
|
f->bb[t].prev[1] = i;
|
292 |
|
|
}
|
293 |
|
|
}
|
294 |
|
|
}
|
295 |
883 |
markom |
if (cuc_debug >= 3) print_cuc_bb (f, "AFTER_PREV");
|
296 |
879 |
markom |
}
|
297 |
|
|
|
298 |
|
|
/* Build basic blocks */
|
299 |
|
|
void build_bb (cuc_func *f)
|
300 |
|
|
{
|
301 |
|
|
int i, j, k;
|
302 |
|
|
for (i = 0; i < f->num_bb; i++) {
|
303 |
|
|
if (f->bb[i].last < 0) f->bb[i].ninsn = MAX_REGS - 1;
|
304 |
|
|
else f->bb[i].ninsn = f->bb[i].last - f->bb[i].first + 1 + MAX_REGS - 1;
|
305 |
|
|
assert (f->bb[i].ninsn >= MAX_REGS - 1);
|
306 |
|
|
f->bb[i].insn = (cuc_insn *) malloc (sizeof (cuc_insn) * f->bb[i].ninsn);
|
307 |
|
|
assert (f->bb[i].insn);
|
308 |
|
|
f->bb[i].nmemory = 0;
|
309 |
|
|
f->bb[i].unrolled = 1;
|
310 |
|
|
|
311 |
|
|
/* Save space for conditional moves, exclude r0, place lrbb instead */
|
312 |
|
|
change_insn_type (&f->bb[i].insn[0], II_LRBB);
|
313 |
|
|
strcpy (f->bb[i].insn[0].disasm, "lrbb");
|
314 |
|
|
f->bb[i].insn[0].type = IT_UNUSED;
|
315 |
|
|
f->bb[i].insn[0].dep = NULL;
|
316 |
|
|
f->bb[i].insn[0].op[0] = LRBB_REG; f->bb[i].insn[0].opt[0] = OPT_REGISTER | OPT_DEST;
|
317 |
|
|
f->bb[i].insn[0].opt[1] = OPT_LRBB;
|
318 |
|
|
f->bb[i].insn[0].opt[2] = f->bb[i].insn[0].opt[3] = OPT_NONE;
|
319 |
|
|
for (j = 1; j < MAX_REGS - 1; j++) {
|
320 |
|
|
change_insn_type (&f->bb[i].insn[j], II_CMOV);
|
321 |
|
|
strcpy (f->bb[i].insn[j].disasm, "cmov");
|
322 |
|
|
f->bb[i].insn[j].type = 0;
|
323 |
|
|
f->bb[i].insn[j].dep = NULL;
|
324 |
|
|
f->bb[i].insn[j].opt[0] = f->bb[i].insn[j].opt[1] = f->bb[i].insn[j].opt[2] = OPT_REGISTER;
|
325 |
|
|
f->bb[i].insn[j].opt[0] |= OPT_DEST;
|
326 |
|
|
f->bb[i].insn[j].op[0] = f->bb[i].insn[j].op[1] = f->bb[i].insn[j].op[2] = j;
|
327 |
|
|
f->bb[i].insn[j].op[3] = LRBB_REG; f->bb[i].insn[j].opt[3] = OPT_REGISTER;
|
328 |
|
|
}
|
329 |
897 |
markom |
|
330 |
|
|
/* Relocate instructions */
|
331 |
879 |
markom |
for (j = MAX_REGS - 1; j < f->bb[i].ninsn; j++) {
|
332 |
|
|
f->bb[i].insn[j] = insn[f->bb[i].first + j - (MAX_REGS - 1)];
|
333 |
|
|
for (k = 0; k < MAX_OPERANDS; k++)
|
334 |
|
|
if (f->bb[i].insn[j].opt[k] & OPT_REF) {
|
335 |
|
|
int b1;
|
336 |
|
|
for (b1 = 0; b1 < i; b1++)
|
337 |
898 |
markom |
if (f->bb[b1].first <= (signed) f->bb[i].insn[j].op[k]
|
338 |
|
|
&& (signed)f->bb[i].insn[j].op[k] <= f->bb[b1].last) break;
|
339 |
879 |
markom |
assert (b1 < f->num_bb);
|
340 |
|
|
f->bb[i].insn[j].op[k] = REF (b1, f->bb[i].insn[j].op[k] - f->bb[b1].first + MAX_REGS - 1);
|
341 |
|
|
}
|
342 |
|
|
if (f->bb[i].insn[j].type & IT_MEMORY) f->bb[i].nmemory++;
|
343 |
|
|
}
|
344 |
|
|
}
|
345 |
897 |
markom |
|
346 |
|
|
/* We do a quick check if there are some anomalies */
|
347 |
|
|
for (i = 0; i < f->num_bb; i++)
|
348 |
|
|
for (j = 0; j < f->bb[i].ninsn; j++)
|
349 |
|
|
for (k = 0; k < MAX_OPERANDS; k++)
|
350 |
|
|
if (f->bb[i].insn[j].opt[k] & OPT_REF) {
|
351 |
|
|
int t = f->bb[i].insn[j].op[k];
|
352 |
898 |
markom |
if (REF_I (t) >= f->bb[REF_BB(t)].ninsn) {
|
353 |
|
|
printf ("Anomaly detected at %x.%x[%i]\n", i, j, k);
|
354 |
|
|
print_cuc_bb (f, "ANOMALY");
|
355 |
|
|
exit (1);
|
356 |
|
|
}
|
357 |
897 |
markom |
}
|
358 |
879 |
markom |
}
|
359 |
|
|
|
360 |
|
|
/* type == 0; keep predecessor condition
|
361 |
|
|
* type == 1; keep successor condition
|
362 |
|
|
* type == 2; join loop unrolled blocks */
|
363 |
|
|
static void join_bb (cuc_func *f, int pred, int succ, int type)
|
364 |
|
|
{
|
365 |
|
|
int i, j, k, add, ninsn, add_cond = 0;
|
366 |
|
|
unsigned long cond_op, cond_opt;
|
367 |
|
|
cuc_insn *insn;
|
368 |
|
|
|
369 |
897 |
markom |
cucdebug (3, "%x <= %x+%x (%i)\n", pred, pred, succ, type);
|
370 |
|
|
cucdebug (3, "%x %x\n", f->bb[pred].ninsn, f->bb[succ].ninsn);
|
371 |
|
|
if (cuc_debug >= 3) fflush (stdout);
|
372 |
879 |
markom |
|
373 |
|
|
add = f->bb[pred].ninsn;
|
374 |
|
|
if (f->bb[pred].ninsn <= 0
|
375 |
|
|
|| !(f->bb[pred].insn[f->bb[pred].ninsn - 1].type & IT_BRANCH)) type = 1;
|
376 |
|
|
if (type == 0 && f->bb[succ].prev[0] == f->bb[succ].next[0]) add_cond = 1;
|
377 |
|
|
|
378 |
|
|
ninsn = f->bb[pred].ninsn + f->bb[succ].ninsn + (type == 0 || type == 2 ? 1 : 0)
|
379 |
|
|
+ (add_cond ? MAX_REGS : 0);
|
380 |
|
|
|
381 |
|
|
insn = (cuc_insn *) malloc (ninsn * sizeof (cuc_insn));
|
382 |
|
|
for (i = 0; i < add; i++) insn[i] = f->bb[pred].insn[i];
|
383 |
|
|
/* when type == 0, we copy the last (jump) instruction to the end */
|
384 |
|
|
if (type == 0 || type == 2) {
|
385 |
|
|
insn[ninsn - 1] = insn[add - 1];
|
386 |
|
|
cond_op = insn[add - 1].op[1];
|
387 |
|
|
cond_opt = insn[add - 1].opt[1];
|
388 |
|
|
change_insn_type (&insn[add - 1], II_NOP);
|
389 |
|
|
/* and when type == 2, we must add sfor instruction, to quit when either is true */
|
390 |
|
|
if (type == 2) {
|
391 |
|
|
/* TODO */
|
392 |
|
|
assert (0);
|
393 |
|
|
}
|
394 |
|
|
}
|
395 |
|
|
/* Copy second block */
|
396 |
|
|
for (i = 0; i < f->bb[succ].ninsn; i++) insn[i + f->bb[pred].ninsn] = f->bb[succ].insn[i];
|
397 |
|
|
|
398 |
|
|
for (i = 0; i < ninsn; i++) reloc[i] = -1;
|
399 |
|
|
|
400 |
|
|
/* Add conditional instructions if required */
|
401 |
|
|
if (add_cond) {
|
402 |
|
|
recalc_last_used_reg (f, pred);
|
403 |
|
|
recalc_last_used_reg (f, succ);
|
404 |
|
|
|
405 |
|
|
/* r0 -- add nop for it */
|
406 |
|
|
change_insn_type (&insn[add + f->bb[succ].ninsn], II_NOP);
|
407 |
|
|
for (i = 1; i < MAX_REGS; i++) {
|
408 |
|
|
cuc_insn *ii = &insn[add + f->bb[succ].ninsn + i];
|
409 |
|
|
int a = f->bb[pred].last_used_reg[i];
|
410 |
|
|
int b = f->bb[succ].last_used_reg[i];
|
411 |
|
|
|
412 |
|
|
if (b < 0) change_insn_type (ii, II_NOP);
|
413 |
|
|
else if (a < 0) {
|
414 |
|
|
change_insn_type (ii, II_ADD);
|
415 |
|
|
ii->type = 0;
|
416 |
|
|
ii->dep = NULL;
|
417 |
|
|
ii->op[0] = i; ii->opt[0] = OPT_REGISTER | OPT_DEST;
|
418 |
|
|
ii->op[1] = b; ii->opt[1] = OPT_REF;
|
419 |
|
|
ii->op[2] = 0; ii->opt[2] = OPT_CONST;
|
420 |
|
|
ii->op[3] = OPT_NONE;
|
421 |
|
|
} else if (b >= 0) {
|
422 |
|
|
change_insn_type (ii, II_CMOV);
|
423 |
|
|
ii->type = 0;
|
424 |
|
|
ii->dep = NULL;
|
425 |
|
|
ii->op[0] = i; ii->opt[0] = OPT_REGISTER | OPT_DEST;
|
426 |
|
|
ii->op[1] = a; ii->opt[1] = OPT_REF;
|
427 |
|
|
ii->op[2] = b; ii->opt[2] = OPT_REF;
|
428 |
|
|
ii->op[3] = cond_op; ii->opt[3] = cond_opt;
|
429 |
|
|
reloc[REF_I(a)] = REF (pred, add + f->bb[succ].ninsn + i);
|
430 |
|
|
}
|
431 |
|
|
sprintf (ii->disasm, "cmov (join BB)");
|
432 |
|
|
}
|
433 |
|
|
}
|
434 |
|
|
|
435 |
|
|
f->bb[pred].type |= f->bb[succ].type;
|
436 |
|
|
i = 0;
|
437 |
|
|
assert (f->bb[pred].next[0] >= 0);
|
438 |
|
|
switch (type) {
|
439 |
|
|
case 0:
|
440 |
|
|
if (f->bb[pred].next[0] == succ) f->bb[pred].next[0] = f->bb[succ].next[0];
|
441 |
|
|
if (f->bb[pred].next[1] == succ) f->bb[pred].next[1] = f->bb[succ].next[0];
|
442 |
|
|
assert (f->bb[succ].next[1] < 0);
|
443 |
|
|
break;
|
444 |
|
|
case 1:
|
445 |
|
|
f->bb[pred].next[0] = f->bb[succ].next[0];
|
446 |
|
|
f->bb[pred].next[1] = f->bb[succ].next[1];
|
447 |
|
|
break;
|
448 |
|
|
}
|
449 |
|
|
if (f->bb[pred].next[0] == f->bb[pred].next[1]) f->bb[pred].next[1] = -1;
|
450 |
|
|
f->bb[succ].type = BB_DEAD;
|
451 |
|
|
|
452 |
|
|
/* Set max count */
|
453 |
|
|
if (f->bb[pred].cnt < f->bb[succ].cnt) f->bb[pred].cnt = f->bb[succ].cnt;
|
454 |
|
|
f->bb[pred].ninsn = ninsn;
|
455 |
|
|
free (f->bb[pred].insn); f->bb[pred].insn = NULL;
|
456 |
|
|
free (f->bb[succ].insn); f->bb[succ].insn = NULL;
|
457 |
|
|
f->bb[pred].insn = insn;
|
458 |
|
|
for (i = 0; i < f->num_bb; i++) if (!(f->bb[i].type & BB_DEAD)) {
|
459 |
|
|
if (f->bb[i].prev[0] == succ) f->bb[i].prev[0] = pred;
|
460 |
|
|
if (f->bb[i].prev[1] == succ) f->bb[i].prev[1] = pred;
|
461 |
|
|
if (f->bb[i].prev[0] == f->bb[i].prev[1]) f->bb[i].prev[1] = -1;
|
462 |
|
|
for (j = 0; j < f->bb[i].ninsn; j++)
|
463 |
|
|
for (k = 0; k < MAX_OPERANDS; k++)
|
464 |
|
|
if (f->bb[i].insn[j].opt[k] & OPT_REF) {
|
465 |
|
|
/* Check if we are referencing successor BB -> relocate to second part of
|
466 |
|
|
the new block */
|
467 |
|
|
if (REF_BB (f->bb[i].insn[j].op[k]) == succ) {
|
468 |
|
|
if (type == 0 && f->bb[i].insn[j].op[j] == REF (succ, ninsn - 1))
|
469 |
|
|
f->bb[i].insn[j].op[j] = REF (pred, f->bb[pred].ninsn);
|
470 |
|
|
else {
|
471 |
|
|
int t = f->bb[i].insn[j].op[k];
|
472 |
|
|
int ndest = REF (pred, REF_I (t) + add);
|
473 |
|
|
|
474 |
|
|
/* We've found a reference to succ. block, being removed, relocate */
|
475 |
|
|
if (add_cond && i != succ && !(i == pred && j >= ninsn - MAX_REGS)) {
|
476 |
|
|
//printf ("%x!\n", t);
|
477 |
|
|
//printf ("%x!\n", f->INSN(ndest).op[0]);
|
478 |
|
|
/* interblock dependency should have physical register attached */
|
479 |
|
|
assert (f->INSN(ndest).opt[0] == OPT_DEST | OPT_REGISTER);
|
480 |
|
|
assert (f->INSN(ndest).op[0] >= 0);
|
481 |
|
|
f->bb[i].insn[j].op[k] = REF (pred, add + f->bb[succ].ninsn + f->INSN(ndest).op[0]);
|
482 |
|
|
} else f->bb[i].insn[j].op[k] = ndest;
|
483 |
|
|
}
|
484 |
|
|
} else if (REF_BB(f->bb[i].insn[j].op[k]) == pred) {
|
485 |
|
|
if (i != pred && reloc[REF_I(f->bb[i].insn[j].op[k])] >= 0) {
|
486 |
|
|
f->bb[i].insn[j].op[k] = reloc[REF_I(f->bb[i].insn[j].op[k])];
|
487 |
|
|
}
|
488 |
|
|
}
|
489 |
|
|
}
|
490 |
|
|
}
|
491 |
|
|
|
492 |
883 |
markom |
if (cuc_debug >= 3) print_cuc_bb (f, "join");
|
493 |
879 |
markom |
}
|
494 |
|
|
|
495 |
|
|
/* Optimize basic blocks */
|
496 |
|
|
void optimize_bb (cuc_func *f)
|
497 |
|
|
{
|
498 |
|
|
int i, j;
|
499 |
|
|
remove_lrbb:
|
500 |
|
|
/* we can remove lrbb instructions from blocks with just one predecessor */
|
501 |
|
|
for (i = 0; i < f->num_bb; i++) if (!(f->bb[i].type & BB_DEAD)) {
|
502 |
|
|
if (f->bb[i].prev[0] >= 0 && f->bb[i].prev[1] < 0) { /* exactly one predecessor */
|
503 |
|
|
for (j = 0; j < f->bb[i].ninsn; j++)
|
504 |
|
|
if (f->bb[i].insn[j].index == II_LRBB) {
|
505 |
|
|
cuc_insn *t;
|
506 |
883 |
markom |
cucdebug (4, "-lrbb %i.%i\n", i, j);
|
507 |
879 |
markom |
|
508 |
|
|
/* Change to add LRBB, 0, 0 */
|
509 |
|
|
change_insn_type (&f->bb[i].insn[j], II_ADD);
|
510 |
|
|
f->bb[i].insn[j].type &= ~IT_VOLATILE;
|
511 |
|
|
t = &f->bb[f->bb[i].prev[0]].insn[f->bb[f->bb[i].prev[0]].ninsn - 1];
|
512 |
|
|
f->bb[i].insn[j].opt[1] = f->bb[i].insn[j].opt[2] = OPT_CONST;
|
513 |
|
|
f->bb[i].insn[j].op[1] = f->bb[i].insn[j].op[2] = 0; /* always use left block */
|
514 |
|
|
f->bb[i].insn[j].opt[3] = OPT_NONE;
|
515 |
|
|
|
516 |
|
|
/* If the predecessor still has a conditional jump instruction, we must be careful.
|
517 |
|
|
This could only have occured when we found out that next[0] == next[1] and have
|
518 |
|
|
joined them. Now we will link lrbb and correct the situation */
|
519 |
|
|
if (t->type & IT_BRANCH) { /* We must set a reference to branch result */
|
520 |
|
|
f->bb[i].insn[j].opt[1] = t->opt[1];
|
521 |
|
|
f->bb[i].insn[j].op[1] = t->op[1];
|
522 |
|
|
change_insn_type (t, II_NOP);
|
523 |
|
|
}
|
524 |
|
|
}
|
525 |
|
|
}
|
526 |
|
|
}
|
527 |
|
|
|
528 |
|
|
/* Type 0 joining
|
529 |
|
|
1. link between pred & succ
|
530 |
|
|
2. no memory accesses in succ
|
531 |
|
|
3. optional pred's second successors
|
532 |
|
|
4. max. one succ's successors */
|
533 |
|
|
for (i = 0; i < f->num_bb; i++) if (!(f->bb[i].type & BB_DEAD))
|
534 |
|
|
if (f->bb[i].prev[0] >= 0 && f->bb[i].prev[1] < 0 /* one predecessor */
|
535 |
|
|
&& f->bb[i].next[1] < 0 /* max. one successor */
|
536 |
|
|
&& f->bb[i].nmemory == 0) { /* and no memory acceses */
|
537 |
|
|
join_bb (f, f->bb[i].prev[0], i, 0);
|
538 |
|
|
goto remove_lrbb;
|
539 |
|
|
}
|
540 |
|
|
|
541 |
|
|
/* Type 1 joining
|
542 |
|
|
1. link between pred & succ
|
543 |
|
|
2. no other pred's successors
|
544 |
|
|
3. no other succ's predecessors */
|
545 |
|
|
for (i = 0; i < f->num_bb; i++) if (!(f->bb[i].type & BB_DEAD))
|
546 |
|
|
if (f->bb[i].prev[0] >= 0 && f->bb[i].prev[1] < 0 /* one predecessor */
|
547 |
|
|
&& f->bb[f->bb[i].prev[0]].next[0] >= 0 && f->bb[f->bb[i].prev[0]].next[1] < 0) { /* one successor */
|
548 |
|
|
join_bb (f, f->bb[i].prev[0], i, 1);
|
549 |
|
|
goto remove_lrbb;
|
550 |
|
|
}
|
551 |
|
|
|
552 |
|
|
#if 1
|
553 |
|
|
/* Type 2 joining
|
554 |
|
|
1. link between pred & succ
|
555 |
|
|
2. succ has exactly one predeccessor
|
556 |
|
|
3. pred & succ share common successor
|
557 |
|
|
4. optional succ's second successor */
|
558 |
|
|
for (i = 0; i < f->num_bb; i++) if (!(f->bb[i].type & BB_DEAD))
|
559 |
|
|
if (f->bb[i].prev[0] >= 0 && f->bb[i].prev[1] < 0) { /* one predecessor */
|
560 |
|
|
int p = f->bb[i].prev[0];
|
561 |
897 |
markom |
if (f->bb[p].next[0] == i && f->bb[p].next[1] == f->bb[p].next[1]) {
|
562 |
|
|
join_bb (f, f->bb[i].prev[0], i, 2);
|
563 |
|
|
goto remove_lrbb;
|
564 |
|
|
}
|
565 |
879 |
markom |
}
|
566 |
|
|
#endif
|
567 |
|
|
}
|
568 |
|
|
|
569 |
|
|
/* Removes BBs marked as dead */
|
570 |
|
|
void remove_dead_bb (cuc_func *f)
|
571 |
|
|
{
|
572 |
|
|
int i, j, k, d = 0;
|
573 |
|
|
|
574 |
|
|
for (i = 0; i < f->num_bb; i++) if (f->bb[i].type & BB_DEAD) {
|
575 |
|
|
if (f->bb[i].insn) free (f->bb[i].insn);
|
576 |
|
|
f->bb[i].insn = NULL;
|
577 |
|
|
reloc[i] = -1;
|
578 |
|
|
} else {
|
579 |
|
|
reloc[i] = d;
|
580 |
|
|
f->bb[d++] = f->bb[i];
|
581 |
|
|
}
|
582 |
|
|
f->num_bb = d;
|
583 |
|
|
|
584 |
|
|
/* relocate initial blocks */
|
585 |
|
|
for (i = 0; i < f->num_init_bb; i++)
|
586 |
|
|
f->init_bb_reloc[i] = reloc[f->init_bb_reloc[i]];
|
587 |
|
|
|
588 |
|
|
/* repair references */
|
589 |
|
|
for (i = 0; i < f->num_bb; i++) if (!(f->bb[i].type & BB_DEAD)) {
|
590 |
|
|
if (f->bb[i].prev[0] >= 0) assert ((f->bb[i].prev[0] = reloc[f->bb[i].prev[0]]) >= 0);
|
591 |
|
|
if (f->bb[i].prev[1] >= 0) assert ((f->bb[i].prev[1] = reloc[f->bb[i].prev[1]]) >= 0);
|
592 |
|
|
if (f->bb[i].next[0] >= 0) assert ((f->bb[i].next[0] = reloc[f->bb[i].next[0]]) >= 0);
|
593 |
|
|
if (f->bb[i].next[1] >= 0) assert ((f->bb[i].next[1] = reloc[f->bb[i].next[1]]) >= 0);
|
594 |
|
|
if (f->bb[i].prev[0] == f->bb[i].prev[1]) f->bb[i].prev[1] = -1;
|
595 |
|
|
if (f->bb[i].next[0] == f->bb[i].next[1]) f->bb[i].next[1] = -1;
|
596 |
|
|
|
597 |
|
|
for (j = 0; j < f->bb[i].ninsn; j++)
|
598 |
|
|
for (k = 0; k < MAX_OPERANDS; k++)
|
599 |
|
|
if (f->bb[i].insn[j].opt[k] & OPT_BB && (signed)f->bb[i].insn[j].op[k] >= 0)
|
600 |
|
|
assert ((f->bb[i].insn[j].op[k] = reloc[f->bb[i].insn[j].op[k]]) >= 0);
|
601 |
|
|
else if (f->bb[i].insn[j].opt[k] & OPT_REF) {
|
602 |
|
|
int t = f->bb[i].insn[j].op[k];
|
603 |
|
|
assert (reloc[REF_BB(t)] >= 0);
|
604 |
|
|
f->bb[i].insn[j].op[k] = REF (reloc[REF_BB(t)], REF_I (t));
|
605 |
|
|
}
|
606 |
|
|
}
|
607 |
|
|
}
|
608 |
|
|
|
609 |
|
|
/* Recursive calculation of dependencies */
|
610 |
|
|
static int reg_dep_rec (cuc_func *f, int cur)
|
611 |
|
|
{
|
612 |
|
|
int i, j;
|
613 |
|
|
cuc_insn *insn = f->bb[cur].insn;
|
614 |
|
|
|
615 |
|
|
//printf ("\n %i", cur);
|
616 |
|
|
/* Spread only, do not loop */
|
617 |
|
|
if (f->bb[cur].tmp) return;
|
618 |
|
|
f->bb[cur].tmp = 1;
|
619 |
|
|
//printf ("! ");
|
620 |
|
|
|
621 |
|
|
for (i = 0; i < f->bb[cur].ninsn; i++) {
|
622 |
|
|
/* Check for destination operand(s) */
|
623 |
|
|
for (j = 0; j < MAX_OPERANDS; j++) if (insn[i].opt[j] & OPT_DEST)
|
624 |
|
|
if ((insn[i].opt[j] & ~OPT_DEST) == OPT_REGISTER && (signed)insn[i].op[j] >= 0) {
|
625 |
|
|
//printf ("%i:%i,%x ", insn[i].op[j], i, REF (cur, i));
|
626 |
|
|
assert (insn[i].op[j] > 0 && insn[i].op[j] < MAX_REGS); /* r0 should never be dest */
|
627 |
|
|
f->bb[cur].last_used_reg[insn[i].op[j]] = REF (cur, i);
|
628 |
|
|
}
|
629 |
|
|
}
|
630 |
|
|
|
631 |
|
|
if (f->bb[cur].next[0] >= 0) reg_dep_rec (f, f->bb[cur].next[0]);
|
632 |
|
|
if (f->bb[cur].next[1] >= 0) reg_dep_rec (f, f->bb[cur].next[1]);
|
633 |
|
|
}
|
634 |
|
|
|
635 |
|
|
/* Detect register dependencies */
|
636 |
|
|
void reg_dep (cuc_func *f)
|
637 |
|
|
{
|
638 |
|
|
int i, b, c;
|
639 |
|
|
|
640 |
|
|
/* Set dead blocks */
|
641 |
|
|
for (b = 0; b < f->num_bb; b++) {
|
642 |
|
|
f->bb[b].tmp = 0;
|
643 |
|
|
for (i = 0; i < MAX_REGS; i++) f->bb[b].last_used_reg[i] = -1;
|
644 |
|
|
}
|
645 |
|
|
|
646 |
|
|
/* Start with first block and set dependecies of all reachable blocks */
|
647 |
|
|
/* At the same time set last_used_regs */
|
648 |
|
|
reg_dep_rec (f, 0);
|
649 |
|
|
|
650 |
|
|
for (i = 0; i < f->num_bb; i++)
|
651 |
|
|
if (f->bb[i].tmp) f->bb[i].tmp = 0;
|
652 |
|
|
else f->bb[i].type |= BB_DEAD;
|
653 |
|
|
|
654 |
|
|
/* Detect loops; mark BBs where loops must be broken */
|
655 |
|
|
for (c = 0; c < f->num_bb; c++) {
|
656 |
|
|
int min = 3, minb;
|
657 |
|
|
|
658 |
|
|
/* search though all non-visited for minimum number of unvisited predecessors */
|
659 |
|
|
for (b = 0; b < f->num_bb; b++) if (!f->bb[b].tmp) {
|
660 |
|
|
int tmp = 0;
|
661 |
|
|
if (f->bb[b].prev[0] >= 0 && !f->bb[f->bb[b].prev[0]].tmp) tmp++;
|
662 |
|
|
if (f->bb[b].prev[1] >= 0 && !f->bb[f->bb[b].prev[1]].tmp) tmp++;
|
663 |
|
|
if (tmp < min) {
|
664 |
|
|
minb = b;
|
665 |
|
|
min = tmp;
|
666 |
|
|
if (tmp == 0) break; /* We already have the best one */
|
667 |
|
|
}
|
668 |
|
|
}
|
669 |
|
|
b = minb;
|
670 |
|
|
f->bb[b].tmp = 1; /* Mark visited */
|
671 |
883 |
markom |
cucdebug (3, "minb %i min %i\n", minb, min);
|
672 |
879 |
markom |
if (min) { /* We just broke the loop */
|
673 |
|
|
f->bb[b].type |= BB_INLOOP;
|
674 |
|
|
}
|
675 |
|
|
}
|
676 |
|
|
|
677 |
|
|
/* Set real predecessors in cmov instructions to previous blocks */
|
678 |
|
|
for (b = 0; b < f->num_bb; b++)
|
679 |
|
|
for (i = 1; i < MAX_REGS - 1; i++) {
|
680 |
|
|
int pa, pb;
|
681 |
|
|
assert (f->bb[b].insn[i].index == II_CMOV);
|
682 |
|
|
assert (f->bb[b].insn[i].opt[0] == OPT_REGISTER | OPT_DEST);
|
683 |
|
|
assert (f->bb[b].insn[i].op[0] == i);
|
684 |
|
|
if (f->bb[b].prev[0] < 0) pa = -1;
|
685 |
|
|
else pa = f->bb[f->bb[b].prev[0]].last_used_reg[i];
|
686 |
|
|
if (f->bb[b].prev[1] < 0) pb = -1;
|
687 |
|
|
else pb = f->bb[f->bb[b].prev[1]].last_used_reg[i];
|
688 |
|
|
|
689 |
|
|
/* We do some very simple optimizations right away to make things more readable */
|
690 |
|
|
if (pa < 0 && pb < 0) {
|
691 |
|
|
/* Was not used at all */
|
692 |
|
|
change_insn_type (&f->bb[b].insn[i], II_ADD);
|
693 |
|
|
f->bb[b].insn[i].op[2] = 0; f->bb[b].insn[i].opt[2] = OPT_CONST;
|
694 |
|
|
f->bb[b].insn[i].opt[3] = OPT_NONE;
|
695 |
|
|
} else if (pa < 0) {
|
696 |
|
|
change_insn_type (&f->bb[b].insn[i], II_ADD);
|
697 |
|
|
assert (f->INSN(pb).opt[0] == (OPT_REGISTER | OPT_DEST));
|
698 |
|
|
f->bb[b].insn[i].op[1] = pb; f->bb[b].insn[i].opt[1] = OPT_REF;
|
699 |
|
|
f->bb[b].insn[i].op[2] = 0; f->bb[b].insn[i].opt[2] = OPT_CONST;
|
700 |
|
|
f->bb[b].insn[i].opt[3] = OPT_NONE;
|
701 |
|
|
} else if (pb < 0) {
|
702 |
|
|
change_insn_type (&f->bb[b].insn[i], II_ADD);
|
703 |
|
|
assert (f->INSN(pa).opt[0] == (OPT_REGISTER | OPT_DEST));
|
704 |
|
|
f->bb[b].insn[i].op[1] = pa; f->bb[b].insn[i].opt[1] = OPT_REF;
|
705 |
|
|
f->bb[b].insn[i].op[2] = 0; f->bb[b].insn[i].opt[2] = OPT_CONST;
|
706 |
|
|
f->bb[b].insn[i].opt[3] = OPT_NONE;
|
707 |
|
|
} else {
|
708 |
|
|
int t = REF (b, 0); /* lrbb should be first instruction */
|
709 |
|
|
assert (f->INSN(t).index == II_LRBB);
|
710 |
|
|
|
711 |
|
|
f->bb[b].insn[i].op[1] = pa; f->bb[b].insn[i].opt[1] = OPT_REF;
|
712 |
|
|
assert (f->INSN(pa).opt[0] == (OPT_REGISTER | OPT_DEST));
|
713 |
|
|
|
714 |
|
|
f->bb[b].insn[i].op[2] = pb; f->bb[b].insn[i].opt[2] = OPT_REF;
|
715 |
|
|
assert (f->INSN(pb).opt[0] == (OPT_REGISTER | OPT_DEST));
|
716 |
|
|
|
717 |
|
|
/* Update op[3] -- flag register */
|
718 |
|
|
assert (f->bb[b].insn[i].opt[3] == OPT_REGISTER);
|
719 |
|
|
assert (f->bb[b].insn[i].op[3] == LRBB_REG);
|
720 |
|
|
assert (t >= 0);
|
721 |
|
|
f->bb[b].insn[i].opt[3] = OPT_REF; /* Convert already used regs to references */
|
722 |
|
|
f->bb[b].insn[i].op[3] = t;
|
723 |
|
|
assert (f->INSN(t).opt[0] == (OPT_REGISTER | OPT_DEST));
|
724 |
|
|
}
|
725 |
|
|
}
|
726 |
|
|
|
727 |
|
|
/* assign register references */
|
728 |
|
|
for (b = 0; b < f->num_bb; b++) {
|
729 |
|
|
/* rebuild last used reg array */
|
730 |
|
|
f->bb[b].last_used_reg[0] = -1;
|
731 |
|
|
if (f->bb[b].insn[0].index == II_LRBB) f->bb[b].last_used_reg[LRBB_REG] = 0;
|
732 |
|
|
else f->bb[b].last_used_reg[LRBB_REG] = -1;
|
733 |
|
|
|
734 |
|
|
for (i = 1; i < MAX_REGS - 1; i++)
|
735 |
|
|
f->bb[b].last_used_reg[i] = -1;
|
736 |
|
|
|
737 |
|
|
/* Create references */
|
738 |
|
|
for (i = 0; i < f->bb[b].ninsn; i++) {
|
739 |
|
|
int k;
|
740 |
|
|
/* Check for source operands first */
|
741 |
|
|
for (k = 0; k < MAX_OPERANDS; k++) {
|
742 |
|
|
if (!(f->bb[b].insn[i].opt[k] & OPT_DEST))
|
743 |
|
|
if (f->bb[b].insn[i].opt[k] & OPT_REGISTER) {
|
744 |
|
|
int t = f->bb[b].last_used_reg[f->bb[b].insn[i].op[k]];
|
745 |
|
|
|
746 |
|
|
if (f->bb[b].insn[i].op[k] == 0) { /* Convert r0 to const0 */
|
747 |
|
|
f->bb[b].insn[i].opt[k] = OPT_CONST;
|
748 |
|
|
f->bb[b].insn[i].op[k] = 0;
|
749 |
|
|
} else if (t >= 0) {
|
750 |
|
|
f->bb[b].insn[i].opt[k] = OPT_REF; /* Convert already used regs to references */
|
751 |
|
|
f->bb[b].insn[i].op[k] = t;
|
752 |
|
|
assert (f->INSN(t).opt[0] == (OPT_REGISTER | OPT_DEST));
|
753 |
|
|
//f->INSN(t).op[0] = -1;
|
754 |
|
|
}
|
755 |
|
|
} else if (f->bb[b].insn[i].opt[k] & OPT_REF) {
|
756 |
|
|
//f->INSN(f->bb[b].insn[i].op[k]).op[0] = -1; /* Mark referenced */
|
757 |
|
|
f->INSN(f->bb[b].insn[i].op[k]).type &= ~IT_UNUSED;
|
758 |
|
|
}
|
759 |
|
|
}
|
760 |
|
|
|
761 |
|
|
/* Now check for destination operand(s) */
|
762 |
|
|
for (k = 0; k < MAX_OPERANDS; k++) if (f->bb[b].insn[i].opt[k] & OPT_DEST)
|
763 |
|
|
if ((f->bb[b].insn[i].opt[k] & ~OPT_DEST) == OPT_REGISTER
|
764 |
|
|
&& (int)f->bb[b].insn[i].op[k] >= 0) {
|
765 |
|
|
int t = f->bb[b].last_used_reg[f->bb[b].insn[i].op[k]];
|
766 |
|
|
assert (f->bb[b].insn[i].op[k] != 0); /* r0 should never be dest */
|
767 |
|
|
f->bb[b].last_used_reg[f->bb[b].insn[i].op[k]] = REF (b, i);
|
768 |
|
|
}
|
769 |
|
|
}
|
770 |
|
|
}
|
771 |
|
|
|
772 |
|
|
/* Remove all unused lrbb */
|
773 |
|
|
for (b = 0; b < f->num_bb; b++)
|
774 |
|
|
for (i = 0; i < f->bb[b].ninsn; i++)
|
775 |
|
|
if (f->bb[b].insn[i].type & IT_UNUSED) change_insn_type (&f->bb[b].insn[i], II_NOP);
|
776 |
|
|
|
777 |
|
|
/* SSAs with final register value are marked as outputs */
|
778 |
|
|
assert (f->bb[f->num_bb - 1].type & BB_END);
|
779 |
|
|
for (i = 0; i < MAX_REGS; i++) if (!call_saved[i]) {
|
780 |
|
|
int t = f->bb[f->num_bb - 1].last_used_reg[i];
|
781 |
|
|
/* Mark them volatile, so optimizer does not remove them */
|
782 |
|
|
if (t >= 0) f->bb[REF_BB(t)].insn[REF_I(t)].type |= IT_OUTPUT;
|
783 |
|
|
}
|
784 |
|
|
}
|
785 |
|
|
|
786 |
897 |
markom |
/* split the BB, based on the group numbers in .tmp */
|
787 |
|
|
void expand_bb (cuc_func *f, int b)
|
788 |
|
|
{
|
789 |
|
|
int n = f->num_bb;
|
790 |
|
|
int mg = 0;
|
791 |
|
|
int b1, i, j;
|
792 |
|
|
|
793 |
|
|
for (i = 0; i < f->bb[b].ninsn; i++)
|
794 |
|
|
if (f->bb[b].insn[i].tmp > mg) mg = f->bb[b].insn[i].tmp;
|
795 |
|
|
|
796 |
|
|
/* Create copies */
|
797 |
|
|
for (b1 = 1; b1 <= mg; b1++) {
|
798 |
|
|
assert (f->num_bb < MAX_BB);
|
799 |
|
|
cpy_bb (&f->bb[f->num_bb], &f->bb[b]);
|
800 |
|
|
f->num_bb++;
|
801 |
|
|
}
|
802 |
|
|
|
803 |
|
|
/* Relocate */
|
804 |
|
|
for (b1 = 0; b1 < f->num_bb; b1++)
|
805 |
|
|
for (i = 0; i < f->bb[b1].ninsn; i++) {
|
806 |
|
|
dep_list *d = f->bb[b1].insn[i].dep;
|
807 |
|
|
for (j = 0; j < MAX_OPERANDS; j++)
|
808 |
|
|
if (f->bb[b1].insn[i].opt[j] & OPT_REF) {
|
809 |
|
|
int t = f->bb[b1].insn[i].op[j];
|
810 |
|
|
if (REF_BB(t) == b && f->INSN(t).tmp != 0)
|
811 |
|
|
f->bb[b1].insn[i].op[j] = REF (n + f->INSN(t).tmp - 1, REF_I(t));
|
812 |
|
|
}
|
813 |
|
|
while (d) {
|
814 |
|
|
if (REF_BB (d->ref) == b && f->INSN(d->ref).tmp != 0)
|
815 |
|
|
d->ref = REF (n + f->INSN(d->ref).tmp - 1, REF_I(d->ref));
|
816 |
|
|
d = d->next;
|
817 |
|
|
}
|
818 |
|
|
}
|
819 |
|
|
|
820 |
|
|
/* Delete unused instructions */
|
821 |
|
|
for (j = 0; j <= mg; j++) {
|
822 |
|
|
if (j == 0) b1 = b;
|
823 |
|
|
else b1 = n + j - 1;
|
824 |
|
|
for (i = 0; i < f->bb[b1].ninsn; i++) {
|
825 |
|
|
if (f->bb[b1].insn[i].tmp != j)
|
826 |
|
|
change_insn_type (&f->bb[b1].insn[i], II_NOP);
|
827 |
|
|
f->bb[b1].insn[i].tmp = 0;
|
828 |
|
|
}
|
829 |
|
|
if (j < mg) {
|
830 |
|
|
f->bb[b1].next[0] = n + j;
|
831 |
|
|
f->bb[b1].next[1] = -1;
|
832 |
|
|
f->bb[n + j].prev[0] = b1;
|
833 |
|
|
f->bb[n + j].prev[1] = -1;
|
834 |
|
|
} else {
|
835 |
|
|
i = f->bb[b1].next[0];
|
836 |
|
|
f->bb[n + j].prev[0] = j == 1 ? b : b1 - 1;
|
837 |
|
|
f->bb[n + j].prev[1] = -1;
|
838 |
|
|
if (i >= 0) {
|
839 |
|
|
if (f->bb[i].prev[0] == b) f->bb[i].prev[0] = b1;
|
840 |
|
|
if (f->bb[i].prev[1] == b) f->bb[i].prev[1] = b1;
|
841 |
|
|
}
|
842 |
|
|
i = f->bb[b1].next[1];
|
843 |
|
|
if (i >= 0) {
|
844 |
|
|
if (f->bb[i].prev[0] == b) f->bb[i].prev[0] = b1;
|
845 |
|
|
if (f->bb[i].prev[1] == b) f->bb[i].prev[1] = b1;
|
846 |
|
|
}
|
847 |
|
|
}
|
848 |
|
|
}
|
849 |
|
|
}
|
850 |
|
|
|
851 |
879 |
markom |
/* Scans sequence of BBs and set bb[].cnt */
|
852 |
|
|
void generate_bb_seq (cuc_func *f, char *mp_filename, char *bb_filename)
|
853 |
|
|
{
|
854 |
|
|
FILE *fi, *fo;
|
855 |
|
|
struct mprofentry_struct *buf;
|
856 |
|
|
const int bufsize = 256;
|
857 |
|
|
unsigned long *bb_start;
|
858 |
|
|
unsigned long *bb_end;
|
859 |
|
|
int b, i, r;
|
860 |
|
|
int curbb, prevbb = -1;
|
861 |
|
|
unsigned long addr = -1;
|
862 |
|
|
unsigned long prevaddr = -1;
|
863 |
897 |
markom |
int mssum = 0;
|
864 |
|
|
int mlsum = 0;
|
865 |
|
|
int mscnt = 0;
|
866 |
|
|
int mlcnt = 0;
|
867 |
879 |
markom |
|
868 |
|
|
assert (fi = fopen (mp_filename, "rb"));
|
869 |
|
|
assert (fo = fopen (bb_filename, "wb+"));
|
870 |
|
|
|
871 |
|
|
assert (bb_start = (unsigned long *) malloc (sizeof (unsigned long) * f->num_bb));
|
872 |
|
|
assert (bb_end = (unsigned long *) malloc (sizeof (unsigned long) * f->num_bb));
|
873 |
|
|
for (b = 0; b < f->num_bb; b++) {
|
874 |
|
|
bb_start[b] = f->start_addr + f->bb[b].first * 4;
|
875 |
|
|
bb_end[b] = f->start_addr + f->bb[b].last * 4;
|
876 |
|
|
//printf ("%i %x %x\n", b, bb_start[b], bb_end[b]);
|
877 |
|
|
f->bb[0].cnt = 0;
|
878 |
|
|
}
|
879 |
|
|
|
880 |
|
|
buf = (struct mprofentry_struct *) malloc (sizeof (struct mprofentry_struct) * bufsize);
|
881 |
|
|
assert (buf);
|
882 |
|
|
|
883 |
|
|
//printf ("BBSEQ:\n");
|
884 |
|
|
do {
|
885 |
|
|
r = fread (buf, sizeof (struct mprofentry_struct), bufsize, fi);
|
886 |
|
|
//printf ("r%i : ", r);
|
887 |
|
|
for (i = 0; i < r; i++) {
|
888 |
|
|
if (buf[i].type & MPROF_FETCH) {
|
889 |
|
|
//printf ("%x, ", buf[i].addr);
|
890 |
|
|
if (buf[i].addr >= f->start_addr && buf[i].addr <= f->end_addr) {
|
891 |
|
|
assert (buf[i].type & MPROF_32);
|
892 |
|
|
prevaddr = addr;
|
893 |
|
|
addr = buf[i].addr;
|
894 |
|
|
for (b = 0; b < f->num_bb; b++)
|
895 |
|
|
if (bb_start[b] <= addr && addr <= bb_end[b]) break;
|
896 |
|
|
assert (b < f->num_bb);
|
897 |
|
|
curbb = b;
|
898 |
|
|
if (prevaddr + 4 != addr) prevbb = -1;
|
899 |
|
|
} else curbb = -1;
|
900 |
|
|
|
901 |
|
|
#warning TODO: do not count interrupts
|
902 |
|
|
if (curbb != prevbb && curbb >= 0) {
|
903 |
|
|
fwrite (&curbb, sizeof (unsigned long), 1, fo);
|
904 |
|
|
//printf (" [%i] ", curbb);
|
905 |
|
|
f->bb[curbb].cnt++;
|
906 |
|
|
prevbb = curbb;
|
907 |
|
|
}
|
908 |
897 |
markom |
} else {
|
909 |
|
|
if (verify_memoryarea(buf[i].addr))
|
910 |
|
|
if (buf[i].type & MPROF_WRITE) mscnt++, mssum += cur_area->delayw;
|
911 |
|
|
else mlcnt++, mlsum += cur_area->delayw;
|
912 |
879 |
markom |
}
|
913 |
|
|
}
|
914 |
|
|
//printf ("\n");
|
915 |
|
|
} while (r == bufsize);
|
916 |
|
|
//printf ("\n");
|
917 |
|
|
|
918 |
897 |
markom |
runtime.cuc.mdelay[0] = (1. * mlsum) / mlcnt;
|
919 |
|
|
runtime.cuc.mdelay[1] = (1. * mlsum) / mlcnt;
|
920 |
|
|
runtime.cuc.mdelay[2] = runtime.cuc.mdelay[3] = 1;
|
921 |
883 |
markom |
f->num_runs = f->bb[0].cnt;
|
922 |
879 |
markom |
fclose (fi);
|
923 |
|
|
fclose (fo);
|
924 |
|
|
free (buf);
|
925 |
|
|
free (bb_end);
|
926 |
|
|
free (bb_start);
|
927 |
|
|
|
928 |
|
|
/* Initialize basic block relocations */
|
929 |
|
|
f->num_init_bb = f->num_bb;
|
930 |
|
|
//printf ("num_init_bb = %i\n", f->num_init_bb);
|
931 |
|
|
assert (f->init_bb_reloc = (int *)malloc (sizeof (int) * f->num_init_bb));
|
932 |
|
|
for (b = 0; b < f->num_init_bb; b++) f->init_bb_reloc[b] = b;
|
933 |
|
|
}
|
934 |
|
|
|
935 |
|
|
/* Scans sequence of BBs and set counts for pre/unrolled loop for BB b */
|
936 |
|
|
void count_bb_seq (cuc_func *f, int b, char *bb_filename, int *counts, int preroll, int unroll)
|
937 |
|
|
{
|
938 |
|
|
FILE *fi;
|
939 |
|
|
const int bufsize = 256;
|
940 |
|
|
int i, r;
|
941 |
|
|
int *buf;
|
942 |
|
|
int cnt = 0;
|
943 |
|
|
int times = preroll - 1 + unroll;
|
944 |
|
|
|
945 |
|
|
assert (fi = fopen (bb_filename, "rb"));
|
946 |
|
|
for (i = 0; i < times; i++) counts[i] = 0;
|
947 |
|
|
assert (buf = (int *) malloc (sizeof (int) * bufsize));
|
948 |
|
|
|
949 |
|
|
do {
|
950 |
|
|
r = fread (buf, sizeof (int), bufsize, fi);
|
951 |
|
|
for (i = 0; i < r; i++) {
|
952 |
|
|
/* count consecutive acesses */
|
953 |
|
|
if (f->init_bb_reloc[buf[i]] == b) {
|
954 |
|
|
counts[cnt]++;
|
955 |
|
|
if (++cnt >= times) cnt = preroll - 1;
|
956 |
|
|
} else cnt = 0;
|
957 |
|
|
}
|
958 |
|
|
} while (r == bufsize);
|
959 |
|
|
|
960 |
|
|
log ("Counts %i,%i :", preroll, unroll);
|
961 |
|
|
for (i = 0; i < times; i++) log ("%x ", counts[i]);
|
962 |
|
|
log ("\n");
|
963 |
|
|
|
964 |
|
|
fclose (fi);
|
965 |
|
|
free (buf);
|
966 |
|
|
}
|
967 |
|
|
|
968 |
|
|
/* relocate all accesses inside of BB b to back/fwd */
|
969 |
|
|
static void relocate_bb (cuc_bb *bb, int b, int back, int fwd)
|
970 |
|
|
{
|
971 |
|
|
int i, j;
|
972 |
|
|
for (i = 0; i < bb->ninsn; i++)
|
973 |
|
|
for (j = 0; j < MAX_OPERANDS; j++)
|
974 |
|
|
if (bb->insn[i].opt[j] & OPT_REF
|
975 |
|
|
&& REF_BB (bb->insn[i].op[j]) == b) {
|
976 |
|
|
int t = REF_I (bb->insn[i].op[j]);
|
977 |
|
|
if (t < i) bb->insn[i].op[j] = REF (back, t);
|
978 |
|
|
else bb->insn[i].op[j] = REF (fwd, t);
|
979 |
|
|
}
|
980 |
|
|
}
|
981 |
|
|
|
982 |
|
|
/* Unroll loop b unroll times and return new function. Original
|
983 |
|
|
function is unmodified. */
|
984 |
|
|
static cuc_func *unroll_loop (cuc_func *f, int b, int unroll)
|
985 |
|
|
{
|
986 |
|
|
int b1, t, i, j, prevb, prevart_b;
|
987 |
|
|
cuc_func *n = dup_func (f);
|
988 |
|
|
cuc_bb *ob = &f->bb[b];
|
989 |
|
|
cuc_insn *ii;
|
990 |
|
|
|
991 |
|
|
assert (unroll > 1);
|
992 |
|
|
//printf ("unroll BB%i x %i (num_bb %i)\n", b, unroll, n->num_bb);
|
993 |
|
|
unroll--;
|
994 |
|
|
assert (n->num_bb + unroll * 2 < MAX_BB);
|
995 |
|
|
|
996 |
|
|
prevb = b;
|
997 |
|
|
prevart_b = b;
|
998 |
|
|
/* Duplicate the BB */
|
999 |
|
|
for (t = 0; t < unroll; t++) {
|
1000 |
|
|
cuc_bb *pb = &n->bb[prevart_b];
|
1001 |
|
|
/* Add new block and set links */
|
1002 |
|
|
b1 = n->num_bb++;
|
1003 |
|
|
cpy_bb (&n->bb[b1], ob);
|
1004 |
|
|
/* Only one should be in loop, so we remove any INLOOP flags from duplicates */
|
1005 |
|
|
n->bb[b1].type &= ~(BB_END | BB_INLOOP);
|
1006 |
|
|
|
1007 |
|
|
/* Set predecessor's successor */
|
1008 |
|
|
if (n->bb[prevb].next[0] == b) {
|
1009 |
|
|
n->bb[prevb].next[0] = b1;
|
1010 |
|
|
if (pb->next[0] < 0) pb->next[0] = b1 + 1;
|
1011 |
|
|
else pb->next[1] = b1 + 1;
|
1012 |
|
|
n->bb[b1].next[1] = b1 + 1;
|
1013 |
|
|
} else if (n->bb[prevb].next[1] == b) {
|
1014 |
|
|
if (pb->next[0] < 0) pb->next[0] = b1 + 1;
|
1015 |
|
|
else pb->next[1] = b1 + 1;
|
1016 |
|
|
n->bb[b1].next[0] = b1 + 1;
|
1017 |
|
|
n->bb[prevb].next[1] = b1;
|
1018 |
|
|
} else assert (0);
|
1019 |
|
|
|
1020 |
|
|
/* Set predecessor */
|
1021 |
|
|
n->bb[b1].prev[0] = prevb;
|
1022 |
|
|
n->bb[b1].prev[1] = -1;
|
1023 |
|
|
|
1024 |
|
|
/* Relocate backward references to current instance and forward references
|
1025 |
|
|
to previous one */
|
1026 |
|
|
relocate_bb (&n->bb[b1], b, b1, prevb);
|
1027 |
|
|
|
1028 |
|
|
/* add artificial block, just to join accesses */
|
1029 |
|
|
b1 = n->num_bb++;
|
1030 |
|
|
cpy_bb (&n->bb[b1], ob);
|
1031 |
|
|
n->bb[b1].cnt = 0;
|
1032 |
|
|
|
1033 |
|
|
for (i = 0; i < ob->ninsn - 1; i++) {
|
1034 |
|
|
ii = &n->bb[b1].insn[i];
|
1035 |
|
|
if (ob->insn[i].opt[0] & OPT_DEST) {
|
1036 |
|
|
change_insn_type (ii, II_CMOV);
|
1037 |
|
|
ii->op[0] = -1; ii->opt[0] = OPT_REGISTER | OPT_DEST;
|
1038 |
|
|
ii->op[1] = REF (prevart_b, i); ii->opt[1] = OPT_REF;
|
1039 |
|
|
ii->op[2] = REF (b1 - 1, i); ii->opt[2] = OPT_REF;
|
1040 |
|
|
|
1041 |
|
|
/* Take left one, if we should have finished the first iteration*/
|
1042 |
|
|
if (pb->insn[pb->ninsn - 1].type & IT_BRANCH) {
|
1043 |
|
|
ii->op[3] = pb->insn[pb->ninsn - 1].op[1]; ii->opt[3] = pb->insn[pb->ninsn - 1].opt[1];
|
1044 |
|
|
} else {
|
1045 |
|
|
assert (pb->insn[pb->ninsn - 1].type & IT_COND);
|
1046 |
|
|
ii->op[3] = REF (prevart_b, pb->ninsn - 1); ii->opt[3] = OPT_REF;
|
1047 |
|
|
}
|
1048 |
|
|
ii->dep = NULL;
|
1049 |
|
|
ii->type = 0;
|
1050 |
|
|
} else {
|
1051 |
|
|
change_insn_type (ii, II_NOP);
|
1052 |
|
|
}
|
1053 |
|
|
}
|
1054 |
|
|
|
1055 |
|
|
/* Add sfor instruction at the end, prioritizing flags */
|
1056 |
|
|
ii = &n->bb[b1].insn[ob->ninsn - 1];
|
1057 |
|
|
change_insn_type (ii, II_SFOR);
|
1058 |
|
|
ii->op[0] = FLAG_REG; ii->opt[0] = OPT_REGISTER | OPT_DEST;
|
1059 |
|
|
if (pb->insn[pb->ninsn - 1].type & IT_BRANCH) {
|
1060 |
|
|
ii->op[1] = pb->insn[pb->ninsn - 1].op[1];
|
1061 |
|
|
ii->opt[1] = pb->insn[pb->ninsn - 1].opt[1];
|
1062 |
|
|
} else {
|
1063 |
|
|
ii->op[1] = REF (prevart_b, pb->ninsn - 1);
|
1064 |
|
|
ii->opt[1] = OPT_REF;
|
1065 |
|
|
}
|
1066 |
|
|
if (n->bb[b1 - 1].insn[pb->ninsn - 1].type & IT_BRANCH) {
|
1067 |
|
|
ii->op[2] = n->bb[b1 - 1].insn[pb->ninsn - 1].op[1];
|
1068 |
|
|
ii->opt[2] = n->bb[b1 - 1].insn[pb->ninsn - 1].opt[1];
|
1069 |
|
|
} else {
|
1070 |
|
|
ii->op[2] = REF (b1 - 1, pb->ninsn - 1);
|
1071 |
|
|
ii->opt[2] = OPT_REF;
|
1072 |
|
|
}
|
1073 |
|
|
ii->opt[3] = OPT_NONE;
|
1074 |
|
|
ii->type = IT_COND;
|
1075 |
|
|
|
1076 |
|
|
/* Only one should be in loop, so we remove any INLOOP flags from duplicates */
|
1077 |
|
|
n->bb[b1].type &= ~(BB_END | BB_INLOOP);
|
1078 |
|
|
n->bb[b1].prev[0] = prevart_b;
|
1079 |
|
|
n->bb[b1].prev[1] = b1 - 1;
|
1080 |
|
|
n->bb[b1].next[0] = ob->next[0] == b ? ob->next[1] : ob->next[0];
|
1081 |
|
|
n->bb[b1].next[1] = -1;
|
1082 |
|
|
|
1083 |
|
|
prevb = b1 - 1;
|
1084 |
|
|
prevart_b = b1;
|
1085 |
|
|
}
|
1086 |
|
|
if (ob->type & BB_END) {
|
1087 |
|
|
n->bb[prevart_b].type |= BB_END;
|
1088 |
|
|
n->bb[b].type &= ~BB_END;
|
1089 |
|
|
}
|
1090 |
|
|
|
1091 |
|
|
//print_cuc_bb (n, "unroll1");
|
1092 |
|
|
/* repair BB after loop, to point back to latest artificial BB */
|
1093 |
|
|
b1 = n->bb[prevart_b].next[0];
|
1094 |
|
|
if (b1 >= 0) {
|
1095 |
897 |
markom |
if (n->bb[b1].prev[0] == b) n->bb[b1].prev[0] = prevart_b;
|
1096 |
|
|
else if (n->bb[b1].prev[1] == b) n->bb[b1].prev[1] = prevart_b;
|
1097 |
879 |
markom |
else assert (0);
|
1098 |
|
|
}
|
1099 |
|
|
|
1100 |
|
|
/* Relink back to start of the loop */
|
1101 |
|
|
/* Set predecessor's successor */
|
1102 |
|
|
if (n->bb[prevb].next[0] == b) n->bb[prevb].next[0] = b;
|
1103 |
|
|
else if (n->bb[prevb].next[1] == b) n->bb[prevb].next[1] = b;
|
1104 |
|
|
else assert (0);
|
1105 |
|
|
|
1106 |
|
|
/* Set predecessor */
|
1107 |
|
|
if (n->bb[b].prev[0] == b) n->bb[b].prev[0] = prevb;
|
1108 |
|
|
else if (n->bb[b].prev[1] == b) n->bb[b].prev[1] = prevb;
|
1109 |
|
|
else assert (0);
|
1110 |
|
|
|
1111 |
|
|
//print_cuc_bb (n, "unroll2");
|
1112 |
|
|
|
1113 |
|
|
/* Relocate backward references to current instance and forward references
|
1114 |
|
|
to previous one */
|
1115 |
|
|
relocate_bb (&n->bb[b], b, b, prevb);
|
1116 |
|
|
|
1117 |
|
|
/* Relocate all other blocks to point to latest prevart_b */
|
1118 |
|
|
for (i = 0; i < f->num_bb; i++)
|
1119 |
|
|
if (i != b) relocate_bb (&n->bb[i], b, prevart_b, prevart_b);
|
1120 |
|
|
|
1121 |
|
|
return n;
|
1122 |
|
|
}
|
1123 |
|
|
|
1124 |
|
|
/* Preroll loop b preroll times and return new function. Original
|
1125 |
|
|
function is unmodified. */
|
1126 |
|
|
static cuc_func *preroll_loop (cuc_func *f, int b, int preroll)
|
1127 |
|
|
{
|
1128 |
|
|
int b1, t, i, j, prevb, prevart_b;
|
1129 |
|
|
cuc_func *n = dup_func (f);
|
1130 |
|
|
cuc_bb *ob = &f->bb[b];
|
1131 |
|
|
cuc_insn *ii;
|
1132 |
|
|
|
1133 |
|
|
assert (preroll > 1);
|
1134 |
|
|
//printf ("preroll BB%i x %i (num_bb %i)\n", b, preroll, n->num_bb);
|
1135 |
|
|
preroll--;
|
1136 |
|
|
assert (n->num_bb + preroll * 2 < MAX_BB);
|
1137 |
|
|
|
1138 |
|
|
prevb = b;
|
1139 |
|
|
prevart_b = b;
|
1140 |
|
|
/* Duplicate the BB */
|
1141 |
|
|
for (t = 0; t < preroll; t++) {
|
1142 |
|
|
cuc_bb *pb = &n->bb[prevart_b];
|
1143 |
|
|
/* Add new block and set links */
|
1144 |
|
|
b1 = n->num_bb++;
|
1145 |
|
|
cpy_bb (&n->bb[b1], ob);
|
1146 |
|
|
/* Only one should be in loop, so we remove any INLOOP flags from duplicates */
|
1147 |
|
|
n->bb[b1].type &= ~(BB_END | BB_INLOOP);
|
1148 |
|
|
|
1149 |
|
|
/* Set predecessor's successor */
|
1150 |
|
|
if (n->bb[prevb].next[0] == b) {
|
1151 |
|
|
n->bb[prevb].next[0] = b1;
|
1152 |
|
|
if (pb->next[0] < 0) pb->next[0] = b1 + 1;
|
1153 |
|
|
else pb->next[1] = b1 + 1;
|
1154 |
|
|
n->bb[b1].next[1] = b1 + 1;
|
1155 |
|
|
} else if (n->bb[prevb].next[1] == b) {
|
1156 |
|
|
if (pb->next[0] < 0) pb->next[0] = b1 + 1;
|
1157 |
|
|
else pb->next[1] = b1 + 1;
|
1158 |
|
|
n->bb[b1].next[0] = b1 + 1;
|
1159 |
|
|
n->bb[prevb].next[1] = b1;
|
1160 |
|
|
} else assert (0);
|
1161 |
|
|
|
1162 |
|
|
/* Set predecessor */
|
1163 |
|
|
n->bb[b1].prev[0] = prevb;
|
1164 |
|
|
n->bb[b1].prev[1] = -1;
|
1165 |
|
|
|
1166 |
|
|
/* Relocate backward references to current instance and forward references
|
1167 |
|
|
to previous one */
|
1168 |
|
|
relocate_bb (&n->bb[b1], b, b1, prevb);
|
1169 |
|
|
|
1170 |
|
|
/* add artificial block, just to join accesses */
|
1171 |
|
|
b1 = n->num_bb++;
|
1172 |
|
|
cpy_bb (&n->bb[b1], ob);
|
1173 |
|
|
n->bb[b1].cnt = 0;
|
1174 |
|
|
|
1175 |
|
|
for (i = 0; i < ob->ninsn - 1; i++) {
|
1176 |
|
|
ii = &n->bb[b1].insn[i];
|
1177 |
|
|
if (ob->insn[i].opt[0] & OPT_DEST) {
|
1178 |
|
|
change_insn_type (ii, II_CMOV);
|
1179 |
|
|
ii->op[0] = -1; ii->opt[0] = OPT_REGISTER | OPT_DEST;
|
1180 |
|
|
ii->op[1] = REF (prevart_b, i); ii->opt[1] = OPT_REF;
|
1181 |
|
|
ii->op[2] = REF (b1 - 1, i); ii->opt[2] = OPT_REF;
|
1182 |
|
|
|
1183 |
|
|
/* Take left one, if we should have finished the first iteration*/
|
1184 |
|
|
if (pb->insn[pb->ninsn - 1].type & IT_BRANCH) {
|
1185 |
|
|
ii->op[3] = pb->insn[pb->ninsn - 1].op[1]; ii->opt[3] = pb->insn[pb->ninsn - 1].opt[1];
|
1186 |
|
|
} else {
|
1187 |
|
|
assert (pb->insn[pb->ninsn - 1].type & IT_COND);
|
1188 |
|
|
ii->op[3] = REF (prevart_b, pb->ninsn - 1); ii->opt[3] = OPT_REF;
|
1189 |
|
|
}
|
1190 |
|
|
ii->dep = NULL;
|
1191 |
|
|
ii->type = 0;
|
1192 |
|
|
} else {
|
1193 |
|
|
change_insn_type (ii, II_NOP);
|
1194 |
|
|
}
|
1195 |
|
|
}
|
1196 |
|
|
|
1197 |
|
|
/* Add sfor instruction at the end, prioritizing flags */
|
1198 |
|
|
ii = &n->bb[b1].insn[ob->ninsn - 1];
|
1199 |
|
|
change_insn_type (ii, II_SFOR);
|
1200 |
|
|
ii->op[0] = FLAG_REG; ii->opt[0] = OPT_REGISTER | OPT_DEST;
|
1201 |
|
|
if (pb->insn[pb->ninsn - 1].type & IT_BRANCH) {
|
1202 |
|
|
ii->op[1] = pb->insn[pb->ninsn - 1].op[1];
|
1203 |
|
|
ii->opt[1] = pb->insn[pb->ninsn - 1].opt[1];
|
1204 |
|
|
} else {
|
1205 |
|
|
ii->op[1] = REF (prevart_b, pb->ninsn - 1);
|
1206 |
|
|
ii->opt[1] = OPT_REF;
|
1207 |
|
|
}
|
1208 |
|
|
if (n->bb[b1 - 1].insn[pb->ninsn - 1].type & IT_BRANCH) {
|
1209 |
|
|
ii->op[2] = n->bb[b1 - 1].insn[pb->ninsn - 1].op[1];
|
1210 |
|
|
ii->opt[2] = n->bb[b1 - 1].insn[pb->ninsn - 1].opt[1];
|
1211 |
|
|
} else {
|
1212 |
|
|
ii->op[2] = REF (b1 - 1, pb->ninsn - 1);
|
1213 |
|
|
ii->opt[2] = OPT_REF;
|
1214 |
|
|
}
|
1215 |
|
|
ii->opt[3] = OPT_NONE;
|
1216 |
|
|
ii->type = IT_COND;
|
1217 |
|
|
|
1218 |
|
|
/* Only one should be in loop, so we remove any INLOOP flags from duplicates */
|
1219 |
|
|
n->bb[b1].type &= ~(BB_END | BB_INLOOP);
|
1220 |
|
|
n->bb[b1].prev[0] = prevart_b;
|
1221 |
|
|
n->bb[b1].prev[1] = b1 - 1;
|
1222 |
|
|
n->bb[b1].next[0] = ob->next[0] == b ? ob->next[1] : ob->next[0];
|
1223 |
|
|
n->bb[b1].next[1] = -1;
|
1224 |
|
|
|
1225 |
|
|
prevb = b1 - 1;
|
1226 |
|
|
prevart_b = b1;
|
1227 |
|
|
}
|
1228 |
|
|
if (ob->type & BB_END) {
|
1229 |
|
|
n->bb[prevart_b].type |= BB_END;
|
1230 |
|
|
n->bb[b].type &= ~BB_END;
|
1231 |
|
|
}
|
1232 |
|
|
|
1233 |
|
|
//print_cuc_bb (n, "preroll1");
|
1234 |
|
|
/* repair BB after loop, to point back to latest artificial BB */
|
1235 |
|
|
b1 = n->bb[prevart_b].next[0];
|
1236 |
|
|
if (b1 >= 0) {
|
1237 |
897 |
markom |
if (n->bb[b1].prev[0] == b) n->bb[b1].prev[0] = prevart_b;
|
1238 |
|
|
else if (n->bb[b1].prev[1] == b) n->bb[b1].prev[1] = prevart_b;
|
1239 |
879 |
markom |
else assert (0);
|
1240 |
|
|
}
|
1241 |
|
|
|
1242 |
|
|
/* Relink to itself */
|
1243 |
|
|
/* Set predecessor's successor */
|
1244 |
|
|
if (n->bb[prevb].next[0] == b) n->bb[prevb].next[0] = prevb;
|
1245 |
|
|
else if (n->bb[prevb].next[1] == b) n->bb[prevb].next[1] = prevb;
|
1246 |
|
|
else assert (0);
|
1247 |
|
|
n->bb[prevb].prev[1] = prevb;
|
1248 |
|
|
|
1249 |
|
|
if (n->bb[b].prev[0] == b) {
|
1250 |
|
|
n->bb[b].prev[0] = n->bb[b].prev[1];
|
1251 |
|
|
n->bb[b].prev[1] = -1;
|
1252 |
|
|
} else if (n->bb[b].prev[1] == b) {
|
1253 |
|
|
n->bb[b].prev[1] = -1;
|
1254 |
|
|
}
|
1255 |
|
|
|
1256 |
|
|
//print_cuc_bb (n, "preroll2");
|
1257 |
|
|
|
1258 |
|
|
/* Relocate backward references to current instance and forward references
|
1259 |
|
|
to previous one */
|
1260 |
|
|
relocate_bb (&n->bb[b], b, b, prevb);
|
1261 |
|
|
|
1262 |
|
|
/* Relocate all other blocks to point to latest prevart_b */
|
1263 |
|
|
for (i = 0; i < f->num_bb; i++)
|
1264 |
|
|
if (i != b) relocate_bb (&n->bb[i], b, prevart_b, prevart_b);
|
1265 |
|
|
|
1266 |
|
|
return n;
|
1267 |
|
|
}
|
1268 |
|
|
|
1269 |
|
|
/* Unroll loop b unroll times and return new function. Original
|
1270 |
|
|
function is unmodified. */
|
1271 |
|
|
cuc_func *preunroll_loop (cuc_func *f, int b, int preroll, int unroll, char *bb_filename)
|
1272 |
|
|
{
|
1273 |
|
|
int b1, i;
|
1274 |
|
|
cuc_func *n, *t;
|
1275 |
|
|
int *counts;
|
1276 |
|
|
int *bb_reloc;
|
1277 |
|
|
|
1278 |
|
|
if (preroll > 1) {
|
1279 |
|
|
t = preroll_loop (f, b, preroll);
|
1280 |
|
|
b1 = t->num_bb - 2;
|
1281 |
|
|
if (unroll > 1) {
|
1282 |
|
|
//print_cuc_bb (t, "preunroll1");
|
1283 |
|
|
n = unroll_loop (t, b1, unroll);
|
1284 |
|
|
free_func (t);
|
1285 |
|
|
} else n = t;
|
1286 |
|
|
} else {
|
1287 |
|
|
b1 = b;
|
1288 |
897 |
markom |
if (unroll > 1) n = unroll_loop (f, b1, unroll);
|
1289 |
|
|
else return dup_func (f);
|
1290 |
879 |
markom |
}
|
1291 |
|
|
|
1292 |
897 |
markom |
/* Assign new counts to functions */
|
1293 |
879 |
markom |
assert (counts = (int *)malloc (sizeof (int) * (preroll - 1 + unroll)));
|
1294 |
|
|
count_bb_seq (n, b, bb_filename, counts, preroll, unroll);
|
1295 |
|
|
for (i = 0; i < preroll - 1 + unroll; i++) {
|
1296 |
|
|
if (i == 0) b1 = b;
|
1297 |
|
|
else b1 = f->num_bb + (i - 1) * 2;
|
1298 |
|
|
n->bb[b1].cnt = counts[i];
|
1299 |
|
|
}
|
1300 |
|
|
|
1301 |
|
|
//print_cuc_bb (n, "preunroll");
|
1302 |
|
|
free (counts);
|
1303 |
|
|
return n;
|
1304 |
|
|
}
|