QBE
spill.c
См. документацию.
1 #include "all.h"
2 
3 static void
4 aggreg(Blk *hd, Blk *b)
5 {
6  int k;
7 
8  /* aggregate looping information at
9  * loop headers */
10  bsunion(hd->gen, b->gen);
11  for (k=0; k<2; k++)
12  if (b->nlive[k] > hd->nlive[k])
13  hd->nlive[k] = b->nlive[k];
14 }
15 
16 static void
17 tmpuse(Ref r, int use, int loop, Fn *fn)
18 {
19  Mem *m;
20  Tmp *t;
21 
22  if (rtype(r) == RMem) {
23  m = &fn->mem[r.val];
24  tmpuse(m->base, 1, loop, fn);
25  tmpuse(m->index, 1, loop, fn);
26  }
27  else if (rtype(r) == RTmp && r.val >= Tmp0) {
28  t = &fn->tmp[r.val];
29  t->nuse += use;
30  t->ndef += !use;
31  t->cost += loop;
32  }
33 }
34 
35 /* evaluate spill costs of temporaries,
36  * this also fills usage information
37  * requires rpo, preds
38  */
39 void
41 {
42  int n;
43  uint a;
44  Blk *b;
45  Ins *i;
46  Tmp *t;
47  Phi *p;
48 
49  loopiter(fn, aggreg);
50  if (debug['S']) {
51  fprintf(stderr, "\n> Loop information:\n");
52  for (b=fn->start; b; b=b->link) {
53  for (a=0; a<b->npred; ++a)
54  if (b->id <= b->pred[a]->id)
55  break;
56  if (a != b->npred) {
57  fprintf(stderr, "\t%-10s", b->name);
58  fprintf(stderr, " (% 3d ", b->nlive[0]);
59  fprintf(stderr, "% 3d) ", b->nlive[1]);
60  dumpts(b->gen, fn->tmp, stderr);
61  }
62  }
63  }
64  for (t=fn->tmp; t-fn->tmp < fn->ntmp; t++) {
65  t->cost = t-fn->tmp < Tmp0 ? UINT_MAX : 0;
66  t->nuse = 0;
67  t->ndef = 0;
68  }
69  for (b=fn->start; b; b=b->link) {
70  for (p=b->phi; p; p=p->link) {
71  t = &fn->tmp[p->to.val];
72  tmpuse(p->to, 0, 0, fn);
73  for (a=0; a<p->narg; a++) {
74  n = p->blk[a]->loop;
75  t->cost += n;
76  tmpuse(p->arg[a], 1, n, fn);
77  }
78  }
79  n = b->loop;
80  for (i=b->ins; i-b->ins < b->nins; i++) {
81  tmpuse(i->to, 0, n, fn);
82  tmpuse(i->arg[0], 1, n, fn);
83  tmpuse(i->arg[1], 1, n, fn);
84  }
85  tmpuse(b->jmp.arg, 1, n, fn);
86  }
87  if (debug['S']) {
88  fprintf(stderr, "\n> Spill costs:\n");
89  for (n=Tmp0; n<fn->ntmp; n++)
90  fprintf(stderr, "\t%-10s %d\n",
91  fn->tmp[n].name,
92  fn->tmp[n].cost);
93  fprintf(stderr, "\n");
94  }
95 }
96 
97 static BSet *fst; /* temps to prioritize in registers (for tcmp1) */
98 static Tmp *tmp; /* current temporaries (for tcmpX) */
99 static int ntmp; /* current # of temps (for limit) */
100 static int locs; /* stack size used by locals */
101 static int slot4; /* next slot of 4 bytes */
102 static int slot8; /* ditto, 8 bytes */
103 static BSet mask[2][1]; /* class masks */
104 
105 static int
106 tcmp0(const void *pa, const void *pb)
107 {
108  uint ca, cb;
109 
110  ca = tmp[*(int *)pa].cost;
111  cb = tmp[*(int *)pb].cost;
112  return (cb < ca) ? -1 : (cb > ca);
113 }
114 
115 static int
116 tcmp1(const void *pa, const void *pb)
117 {
118  int c;
119 
120  c = bshas(fst, *(int *)pb) - bshas(fst, *(int *)pa);
121  return c ? c : tcmp0(pa, pb);
122 }
123 
124 static Ref
125 slot(int t)
126 {
127  int s;
128 
129  assert(t >= Tmp0 && "cannot spill register");
130  s = tmp[t].slot;
131  if (s == -1) {
132  /* specific to NAlign == 3 */
133  /* nice logic to pack stack slots
134  * on demand, there can be only
135  * one hole and slot4 points to it
136  *
137  * invariant: slot4 <= slot8
138  */
139  if (KWIDE(tmp[t].cls)) {
140  s = slot8;
141  if (slot4 == slot8)
142  slot4 += 2;
143  slot8 += 2;
144  } else {
145  s = slot4;
146  if (slot4 == slot8) {
147  slot8 += 2;
148  slot4 += 1;
149  } else
150  slot4 = slot8;
151  }
152  s += locs;
153  tmp[t].slot = s;
154  }
155  return SLOT(s);
156 }
157 
158 static void
159 limit(BSet *b, int k, BSet *f)
160 {
161  static int *tarr, maxt;
162  int i, t, nt;
163 
164  nt = bscount(b);
165  if (nt <= k)
166  return;
167  if (nt > maxt) {
168  free(tarr);
169  tarr = emalloc(nt * sizeof tarr[0]);
170  maxt = nt;
171  }
172  for (i=0, t=0; bsiter(b, &t); t++) {
173  bsclr(b, t);
174  tarr[i++] = t;
175  }
176  if (!f)
177  qsort(tarr, nt, sizeof tarr[0], tcmp0);
178  else {
179  fst = f;
180  qsort(tarr, nt, sizeof tarr[0], tcmp1);
181  }
182  for (i=0; i<k && i<nt; i++)
183  bsset(b, tarr[i]);
184  for (; i<nt; i++)
185  slot(tarr[i]);
186 }
187 
188 static void
189 limit2(BSet *b1, int k1, int k2, BSet *fst)
190 {
191  BSet b2[1];
192 
193  bsinit(b2, ntmp); /* todo, free those */
194  bscopy(b2, b1);
195  bsinter(b1, mask[0]);
196  bsinter(b2, mask[1]);
197  limit(b1, T.ngpr - k1, fst);
198  limit(b2, T.nfpr - k2, fst);
199  bsunion(b1, b2);
200 }
201 
202 static void
203 sethint(BSet *u, bits r)
204 {
205  int t;
206 
207  for (t=Tmp0; bsiter(u, &t); t++)
208  tmp[phicls(t, tmp)].hint.m |= r;
209 }
210 
211 static void
212 reloads(BSet *u, BSet *v)
213 {
214  int t;
215 
216  for (t=Tmp0; bsiter(u, &t); t++)
217  if (!bshas(v, t))
218  emit(Oload, tmp[t].cls, TMP(t), slot(t), R);
219 }
220 
221 static void
222 store(Ref r, int s)
223 {
224  if (s != -1)
225  emit(Ostorew + tmp[r.val].cls, 0, R, r, SLOT(s));
226 }
227 
228 static int
229 regcpy(Ins *i)
230 {
231  return i->op == Ocopy && isreg(i->arg[0]);
232 }
233 
234 static Ins *
235 dopm(Blk *b, Ins *i, BSet *v)
236 {
237  int n, t;
238  BSet u[1];
239  Ins *i1;
240  bits r;
241 
242  bsinit(u, ntmp); /* todo, free those */
243  /* consecutive copies from
244  * registers need to be handled
245  * as one large instruction
246  *
247  * fixme: there is an assumption
248  * that calls are always followed
249  * by copy instructions here, this
250  * might not be true if previous
251  * passes change
252  */
253  i1 = ++i;
254  do {
255  i--;
256  t = i->to.val;
257  if (!req(i->to, R))
258  if (bshas(v, t)) {
259  bsclr(v, t);
260  store(i->to, tmp[t].slot);
261  }
262  bsset(v, i->arg[0].val);
263  } while (i != b->ins && regcpy(i-1));
264  bscopy(u, v);
265  if (i != b->ins && (i-1)->op == Ocall) {
266  v->t[0] &= ~T.retregs((i-1)->arg[1], 0);
267  limit2(v, T.nrsave[0], T.nrsave[1], 0);
268  for (n=0, r=0; T.rsave[n]>=0; n++)
269  r |= BIT(T.rsave[n]);
270  v->t[0] |= T.argregs((i-1)->arg[1], 0);
271  } else {
272  limit2(v, 0, 0, 0);
273  r = v->t[0];
274  }
275  sethint(v, r);
276  reloads(u, v);
277  do
278  emiti(*--i1);
279  while (i1 != i);
280  return i;
281 }
282 
283 /* spill code insertion
284  * requires spill costs, rpo, liveness
285  *
286  * Note: this will replace liveness
287  * information (in, out) with temporaries
288  * that must be in registers at block
289  * borders
290  *
291  * Be careful with:
292  * - Ocopy instructions to ensure register
293  * constraints
294  */
295 void
296 spill(Fn *fn)
297 {
298  Blk *b, *s1, *s2, *hd, **bp;
299  int j, l, t, k, lvarg[2];
300  uint n;
301  BSet u[1], v[1], w[1];
302  Ins *i;
303  Phi *p;
304  Mem *m;
305  bits r;
306 
307  tmp = fn->tmp;
308  ntmp = fn->ntmp;
309  bsinit(u, ntmp);
310  bsinit(v, ntmp);
311  bsinit(w, ntmp);
312  bsinit(mask[0], ntmp);
313  bsinit(mask[1], ntmp);
314  locs = fn->slot;
315  slot4 = 0;
316  slot8 = 0;
317  for (t=0; t<ntmp; t++) {
318  k = 0;
319  if (t >= T.fpr0 && t < T.fpr0 + T.nfpr)
320  k = 1;
321  if (t >= Tmp0)
322  k = KBASE(tmp[t].cls);
323  bsset(mask[k], t);
324  }
325 
326  for (bp=&fn->rpo[fn->nblk]; bp!=fn->rpo;) {
327  b = *--bp;
328  /* invariant: all bocks with bigger rpo got
329  * their in,out updated. */
330 
331  /* 1. find temporaries in registers at
332  * the end of the block (put them in v) */
333  curi = 0;
334  s1 = b->s1;
335  s2 = b->s2;
336  hd = 0;
337  if (s1 && s1->id <= b->id)
338  hd = s1;
339  if (s2 && s2->id <= b->id)
340  if (!hd || s2->id >= hd->id)
341  hd = s2;
342  if (hd) {
343  /* back-edge */
344  bszero(v);
345  hd->gen->t[0] |= T.rglob; /* don't spill registers */
346  for (k=0; k<2; k++) {
347  n = k == 0 ? T.ngpr : T.nfpr;
348  bscopy(u, b->out);
349  bsinter(u, mask[k]);
350  bscopy(w, u);
351  bsinter(u, hd->gen);
352  bsdiff(w, hd->gen);
353  if (bscount(u) < n) {
354  j = bscount(w); /* live through */
355  l = hd->nlive[k];
356  limit(w, n - (l - j), 0);
357  bsunion(u, w);
358  } else
359  limit(u, n, 0);
360  bsunion(v, u);
361  }
362  } else if (s1) {
363  liveon(v, b, s1);
364  if (s2) {
365  liveon(u, b, s2);
366  bscopy(w, u);
367  bsinter(w, v);
368  bsunion(v, u);
369  }
370  limit2(v, 0, 0, w);
371  } else {
372  bscopy(v, b->out);
373  if (rtype(b->jmp.arg) == RCall)
374  v->t[0] |= T.retregs(b->jmp.arg, 0);
375  }
376  for (t=Tmp0; bsiter(b->out, &t); t++)
377  if (!bshas(v, t))
378  slot(t);
379  bscopy(b->out, v);
380 
381  /* 2. process the block instructions */
382  r = v->t[0];
383  curi = &insb[NIns];
384  for (i=&b->ins[b->nins]; i!=b->ins;) {
385  i--;
386  if (regcpy(i)) {
387  i = dopm(b, i, v);
388  continue;
389  }
390  bszero(w);
391  if (!req(i->to, R)) {
392  assert(rtype(i->to) == RTmp);
393  t = i->to.val;
394  if (bshas(v, t))
395  bsclr(v, t);
396  else {
397  /* make sure we have a reg
398  * for the result */
399  bsset(v, t);
400  bsset(w, t);
401  }
402  }
403  j = T.memargs(i->op);
404  for (n=0; n<2; n++)
405  if (rtype(i->arg[n]) == RMem)
406  j--;
407  for (n=0; n<2; n++)
408  switch (rtype(i->arg[n])) {
409  case RMem:
410  t = i->arg[n].val;
411  m = &fn->mem[t];
412  if (rtype(m->base) == RTmp) {
413  bsset(v, m->base.val);
414  bsset(w, m->base.val);
415  }
416  if (rtype(m->index) == RTmp) {
417  bsset(v, m->index.val);
418  bsset(w, m->index.val);
419  }
420  break;
421  case RTmp:
422  t = i->arg[n].val;
423  lvarg[n] = bshas(v, t);
424  bsset(v, t);
425  if (j-- <= 0)
426  bsset(w, t);
427  break;
428  }
429  bscopy(u, v);
430  limit2(v, 0, 0, w);
431  for (n=0; n<2; n++)
432  if (rtype(i->arg[n]) == RTmp) {
433  t = i->arg[n].val;
434  if (!bshas(v, t)) {
435  /* do not reload if the
436  * the temporary was dead
437  */
438  if (!lvarg[n])
439  bsclr(u, t);
440  i->arg[n] = slot(t);
441  }
442  }
443  reloads(u, v);
444  if (!req(i->to, R)) {
445  t = i->to.val;
446  store(i->to, tmp[t].slot);
447  bsclr(v, t);
448  }
449  emiti(*i);
450  r = v->t[0]; /* Tmp0 is NBit */
451  if (r)
452  sethint(v, r);
453  }
454  assert(r == T.rglob || b == fn->start);
455 
456  for (p=b->phi; p; p=p->link) {
457  assert(rtype(p->to) == RTmp);
458  t = p->to.val;
459  if (bshas(v, t)) {
460  bsclr(v, t);
461  store(p->to, tmp[t].slot);
462  } else if (bshas(b->in, t))
463  /* only if the phi is live */
464  p->to = slot(p->to.val);
465  }
466  bscopy(b->in, v);
467  b->nins = &insb[NIns] - curi;
468  idup(&b->ins, curi, b->nins);
469  }
470 
471  /* align the locals to a 16 byte boundary */
472  /* specific to NAlign == 3 */
473  slot8 += slot8 & 3;
474  fn->slot += slot8;
475 
476  if (debug['S']) {
477  fprintf(stderr, "\n> Block information:\n");
478  for (b=fn->start; b; b=b->link) {
479  fprintf(stderr, "\t%-10s (% 5d) ", b->name, b->loop);
480  dumpts(b->out, fn->tmp, stderr);
481  }
482  fprintf(stderr, "\n> After spilling:\n");
483  printfn(fn, stderr);
484  }
485 }
unsigned int uint
Definition: all.h:12
char name[NString]
Definition: all.h:279
void fillcost(Fn *fn)
Definition: spill.c:40
void bsset(BSet *, uint)
Definition: util.c:467
Ins insb[NIns]
Definition: util.c:34
Mem * mem
Definition: all.h:388
int nfpr
Definition: all.h:46
Blk * start
Указатель на блок функции, являющийся её входной точкой
Definition: all.h:385
Blk ** pred
Definition: all.h:274
bits * t
Definition: all.h:68
void * emalloc(size_t)
Definition: util.c:66
uint narg
Definition: all.h:246
void emit(int, int, Ref, Ref, Ref)
Definition: util.c:229
int fpr0
Definition: all.h:45
Definition: all.h:303
void bsunion(BSet *, BSet *)
Definition: util.c:492
int ngpr
Definition: all.h:44
Структура, хранящая информацию об инструкциях.
Definition: all.h:235
Definition: all.h:275
#define KWIDE(k)
Definition: all.h:219
#define KBASE(k)
Definition: all.h:220
int nrsave[2]
Definition: all.h:50
Definition: all.h:84
Ref index
Definition: all.h:374
Definition: all.h:88
short slot
-1 for unset
Definition: all.h:332
Phi * link
Definition: all.h:248
Blk * s1
Definition: all.h:262
BSet gen[1]
Definition: all.h:276
#define SLOT(x)
Definition: all.h:96
uint ndef
Количество блоков, в которых есть объявление переменной
Definition: all.h:329
#define BIT(n)
Definition: all.h:59
Definition: all.h:66
Ins * curi
Definition: util.c:34
void bsinit(BSet *, uint)
Definition: util.c:403
void bscopy(BSet *, BSet *)
Definition: util.c:491
Ref arg[NPred]
Definition: all.h:244
Ref base
Definition: all.h:373
Структура, хранящая описание переменных (более подробное описание переменной ищите в Tmp)...
Definition: all.h:77
Содержит информацию о переменной
Definition: all.h:326
Tmp * tmp
Массив используемых функцией переменных
Definition: all.h:386
int slot
Definition: all.h:397
Ref arg
Definition: all.h:260
Ref to
Definition: all.h:243
BSet in[1]
Definition: all.h:276
int ntmp
Размер массива tmp.
Definition: all.h:389
Blk * s2
Definition: all.h:263
Непосредственно информация о базовом блоке.
Definition: all.h:254
int bsiter(BSet *, int *)
Definition: util.c:521
void idup(Ins **, Ins *, ulong)
Definition: util.c:246
void printfn(Fn *, FILE *)
Definition: parse.c:1160
#define TMP(x)
Definition: all.h:93
void spill(Fn *fn)
Definition: spill.c:296
void loopiter(Fn *, void(*)(Blk *, Blk *))
Blk * link
Definition: all.h:264
void bszero(BSet *)
Definition: util.c:509
uint cost
Definition: all.h:331
uint nins
Definition: all.h:257
char name[NString]
Имя переменной
Definition: all.h:327
Definition: all.h:237
Definition: all.h:89
int loop
Definition: all.h:278
Ref to
Definition: all.h:237
void bsclr(BSet *, uint)
Definition: util.c:474
Target T
uint nblk
Количество блоков в функции
Definition: all.h:392
uint npred
Definition: all.h:275
bits(* retregs)(Ref, int[2])
Definition: all.h:51
Ins * ins
Definition: all.h:256
Phi * phi
Definition: all.h:255
Blk ** rpo
Ссылка на массив блоков, пронумерованных в порядке Reverse-Post Order, заполняется функцией fillrpo...
Definition: all.h:395
Definition: all.h:371
int isreg(Ref)
Definition: util.c:193
bits(* argregs)(Ref, int[2])
Definition: all.h:52
Ref arg[2]
Definition: all.h:238
Номер (в массиве Fn->tmp) первой не регистровой переменной
Definition: all.h:63
Definition: all.h:248
void bsinter(BSet *, BSet *)
Definition: util.c:493
uint val
Definition: all.h:80
int nlive[2]
Definition: all.h:277
uint id
Definition: all.h:266
BSet out[1]
Definition: all.h:276
int(* memargs)(int)
Definition: all.h:53
int phicls(int, Tmp *)
Definition: util.c:313
bits rglob
Definition: all.h:47
void bsdiff(BSet *, BSet *)
Definition: util.c:494
#define R
Definition: all.h:92
void liveon(BSet *, Blk *, Blk *)
Definition: live.c:4
void dumpts(BSet *, Tmp *, FILE *)
Definition: util.c:543
int cls
Definition: rega.c:23
Blk * blk[NPred]
Definition: all.h:245
struct Blk::@5 jmp
Структура, хранящая в себе информацию о функции
Definition: all.h:384
Definition: all.h:36
void emiti(Ins)
Definition: util.c:240
uint nuse
Количество блоков, в которых переменная используется
Definition: all.h:329
uint op
Definition: all.h:236
char debug['Z'+1]
uint bscount(BSet *)
Definition: util.c:450
unsigned long long bits
Definition: all.h:14
Definition: all.h:242
int * rsave
Definition: all.h:49