blob: 9fdabefb6d5ddaebfea757418ca2235ad0301917 [file] [log] [blame]
sewardj73b58bc2004-07-01 18:30:56 +00001
2/*---------------------------------------------------------------*/
3/*--- ---*/
4/*--- This file (reg_alloc.c) is ---*/
5/*--- Copyright (c) 2004 OpenWorks LLP. All rights reserved. ---*/
6/*--- ---*/
7/*---------------------------------------------------------------*/
8
sewardjaf5a5222004-07-01 23:14:42 +00009#include <stdio.h>
10#include <malloc.h>
11
12#include "basictypes.h"
13#include "host_regs.h"
14
15
16/* How many 64-bit sized spill slots do we have? */
17#define N_SPILL64S 16
18
19
sewardj968396e2004-07-03 14:50:33 +000020/* TODO (critical)
21 - Need a way to statically establish the vreg classes,
22 else we can't allocate spill slots properly.
23 - Better consistency checking from what isMove tells us.
24*/
sewardj81497442004-07-02 17:30:07 +000025
sewardjaf5a5222004-07-01 23:14:42 +000026
sewardj73b58bc2004-07-01 18:30:56 +000027/* Records information on virtual register live ranges. Computed once
28 and remains unchanged after that. */
29typedef
30 struct {
31 /* Becomes live for the first time after this insn ... */
32 Int live_after;
33 /* Becomes dead for the last time before this insn ... */
34 Int dead_before;
35 /* The "home" spill slot, if needed. Never changes. */
36 Int spill_offset;
37 Int spill_size;
38 /* Preferencing info, if any. */
39 Bool has_preference;
40 HReg preferred_rreg; /* if True, where I would like to be */
41 }
42 VRegInfo;
43
44
45/* Records information on real-register live ranges. Computed once
46 and remains unchanged after that. */
47typedef
48 struct {
49 HReg rreg;
50 /* Becomes live after this insn ... */
51 Int live_after;
52 /* Becomes dead before this insn ... */
53 Int dead_before;
54 }
55 RRegInfo;
56
57
58/* An array of the following structs comprises the running state of
59 the allocator. It indicates what the current disposition of each
60 allocatable real register is. The array gets updated as the
61 allocator processes instructions. */
62typedef
63 struct {
64 /* Which rreg is this for? */
65 HReg rreg;
66 /* What's it's current disposition? */
67 enum { Free, /* available for use */
68 Unavail, /* in a real-reg live range */
69 Bound /* in use (holding value of some vreg) */
70 }
71 disp;
72 /* If RRegBound, what vreg is it bound to? */
73 HReg vreg;
sewardjaf5a5222004-07-01 23:14:42 +000074 /* Used when .disp == Bound and we are looking for vregs to
75 spill. */
76 Bool is_spill_cand;
sewardj73b58bc2004-07-01 18:30:56 +000077 }
78 RRegState;
79
80
81
sewardjb3d4ce72004-07-02 07:09:23 +000082/* Does this instruction mention a particular reg? */
83static Bool instrMentionsReg (
sewardj2cd80dc2004-07-02 15:20:40 +000084 void (*getRegUsage) (HRegUsage*, HInstr*),
sewardjb3d4ce72004-07-02 07:09:23 +000085 HInstr* instr,
86 HReg r
87)
88{
89 Int i;
90 HRegUsage reg_usage;
sewardj2cd80dc2004-07-02 15:20:40 +000091 (*getRegUsage)(&reg_usage, instr);
sewardjb3d4ce72004-07-02 07:09:23 +000092 for (i = 0; i < reg_usage.n_used; i++)
93 if (reg_usage.hreg[i] == r)
94 return True;
95 return False;
96}
sewardj73b58bc2004-07-01 18:30:56 +000097
sewardjb3d4ce72004-07-02 07:09:23 +000098
sewardj0ec33252004-07-03 13:30:00 +000099/* Search forward from some given point in the incoming instruction
100 sequence. Point is to select a virtual register to spill, by
101 finding the vreg which is mentioned as far ahead as possible, in
102 the hope that this will minimise the number of consequent reloads.
103
104 Only do the search for vregs which are Bound in the running state,
105 and for which the .mark field is set. This allows the caller to
106 arbitrarily restrict the set of spill candidates to be considered.
107
108 Returns an index into the state array indicating the (v,r) pair to
109 spill, or -1 if none was found. */
110static
111Int findMostDistantlyMentionedVReg (
112 void (*getRegUsage) (HRegUsage*, HInstr*),
113 HInstrArray* instrs_in,
114 Int search_from_instr,
115 RRegState* state,
116 Int n_state
117)
118{
119 Int k, m;
120 Int furthest_k = -1;
121 Int furthest = -1;
122 assert(search_from_instr >= 0);
123 for (k = 0; k < n_state; k++) {
124 if (!state[k].is_spill_cand)
125 continue;
126 assert(state[k].disp == Bound);
127 for (m = search_from_instr; m < instrs_in->arr_used; m++) {
128 if (instrMentionsReg(getRegUsage,
129 instrs_in->arr[m], state[k].vreg))
130 break;
131 }
132 if (m > furthest) {
133 furthest = m;
134 furthest_k = k;
135 }
136 }
137 return furthest_k;
138}
139
140
sewardjb3d4ce72004-07-02 07:09:23 +0000141/* A target-independent register allocator for Valgrind. Requires
142 various functions which it uses to deal abstractly with
143 instructions and registers, since it cannot have any
144 target-specific knowledge.
145
146 Returns a new list of instructions, which, as a result of the
147 behaviour of mapRegs, will be in-place modifications of the
148 original instructions.
sewardj73b58bc2004-07-01 18:30:56 +0000149
150 Requires that the incoming code has been generated using
151 vreg numbers 0, 1 .. n_vregs-1. Appearance of a vreg outside
sewardjaf5a5222004-07-01 23:14:42 +0000152 that range is a checked run-time error.
sewardjb3d4ce72004-07-02 07:09:23 +0000153
sewardj2cd80dc2004-07-02 15:20:40 +0000154 Takes an expandable array of pointers to unallocated insns.
155 Returns an expandable array of pointers to allocated insns.
sewardj73b58bc2004-07-01 18:30:56 +0000156*/
sewardj2cd80dc2004-07-02 15:20:40 +0000157HInstrArray* doRegisterAllocation (
sewardj73b58bc2004-07-01 18:30:56 +0000158
sewardj2cd80dc2004-07-02 15:20:40 +0000159 /* Incoming virtual-registerised code. */
160 HInstrArray* instrs_in,
161 Int n_vregs,
sewardj73b58bc2004-07-01 18:30:56 +0000162
163 /* An array listing all the real registers the allocator may use,
164 in no particular order. */
165 HReg* available_real_regs,
166 Int n_available_real_regs,
167
168 /* Return True iff the given insn is a reg-reg move, in which
169 case also return the src and dst regs. */
170 Bool (*isMove) (HInstr*, HReg*, HReg*),
171
172 /* Get info about register usage in this insn. */
sewardj2cd80dc2004-07-02 15:20:40 +0000173 void (*getRegUsage) (HRegUsage*, HInstr*),
sewardj73b58bc2004-07-01 18:30:56 +0000174
175 /* Apply a reg-reg mapping to an insn. */
sewardj2cd80dc2004-07-02 15:20:40 +0000176 void (*mapRegs) (HRegRemap*, HInstr*),
sewardj73b58bc2004-07-01 18:30:56 +0000177
178 /* Return an insn to spill/restore a real reg to a spill slot
179 offset. */
180 HInstr* (*genSpill) ( HReg, Int ),
sewardjaf5a5222004-07-01 23:14:42 +0000181 HInstr* (*genReload) ( HReg, Int )
sewardj73b58bc2004-07-01 18:30:56 +0000182)
183{
sewardjb3d4ce72004-07-02 07:09:23 +0000184 /* Iterators and temporaries. */
sewardj0ec33252004-07-03 13:30:00 +0000185 Int ii, j, k, m, spillee;
sewardj968396e2004-07-03 14:50:33 +0000186 HReg rreg, vreg, vregS, vregD;
sewardj73b58bc2004-07-01 18:30:56 +0000187 HRegUsage reg_usage;
sewardjaf5a5222004-07-01 23:14:42 +0000188
sewardjb3d4ce72004-07-02 07:09:23 +0000189 /* Info on vregs and rregs. Computed once and remains
190 unchanged. */
191 VRegInfo* vreg_info;
192 RRegInfo* rreg_info;
193 Int rreg_info_size;
194 Int rreg_info_used;
195
196 /* Used when constructing vreg_info (for allocating stack
197 slots). */
sewardjaf5a5222004-07-01 23:14:42 +0000198 Int ss_busy_until_before[N_SPILL64S];
199
sewardjb3d4ce72004-07-02 07:09:23 +0000200 /* Used when constructing rreg_info. */
201 Int* rreg_live_after;
202 Int* rreg_dead_before;
203
204 /* Running state of the core allocation algorithm. */
205 RRegState* state;
206 Int n_state;
207
208 /* The vreg -> rreg map constructed and then applied to each
209 instr. */
210 HRegRemap remap;
211
212 /* The output array of instructions. */
sewardj2cd80dc2004-07-02 15:20:40 +0000213 HInstrArray* instrs_out;
sewardjb3d4ce72004-07-02 07:09:23 +0000214
215
sewardjaf5a5222004-07-01 23:14:42 +0000216# define INVALID_INSTRNO (-2)
sewardj73b58bc2004-07-01 18:30:56 +0000217
sewardj0ec33252004-07-03 13:30:00 +0000218# define EMIT_INSTR(_instr) \
219 do { \
220 HInstr* _tmp = (_instr); \
221 if (1) { \
222 fprintf(stdout, "** "); \
223 ppX86Instr(stdout, _tmp); \
224 fprintf(stdout, "\n"); \
225 } \
226 addHInstr ( instrs_out, _tmp ); \
227 } while (0)
228
229
sewardjb3d4ce72004-07-02 07:09:23 +0000230 /* --------- Stage 0: set up output array. --------- */
sewardj2cd80dc2004-07-02 15:20:40 +0000231 instrs_out = newHInstrArray();
sewardjb3d4ce72004-07-02 07:09:23 +0000232
sewardj73b58bc2004-07-01 18:30:56 +0000233
234 /* --------- Stage 1: compute vreg live ranges. --------- */
235
236 /* This is relatively simple, because (1) we only seek the complete
237 end-to-end live range of each vreg, and are not interested in
238 any holes in it, and (2) the vregs are conveniently numbered 0
239 .. n_vregs-1, so we can just dump the results in a pre-allocated
240 array. */
241
242 vreg_info = NULL;
243 if (n_vregs > 0)
244 vreg_info = malloc(sizeof(VRegInfo) * n_vregs);
245
sewardjaf5a5222004-07-01 23:14:42 +0000246 for (j = 0; j < n_vregs; j++) {
247 vreg_info[j].live_after = INVALID_INSTRNO;
248 vreg_info[j].dead_before = INVALID_INSTRNO;
249 vreg_info[j].spill_offset = 0;
250 vreg_info[j].spill_size = 0;
251 vreg_info[j].has_preference = False;
252 vreg_info[j].preferred_rreg = INVALID_HREG;
sewardj73b58bc2004-07-01 18:30:56 +0000253 }
254
255 /* for each insn ... */
sewardj2cd80dc2004-07-02 15:20:40 +0000256 for (ii = 0; ii < instrs_in->arr_used; ii++) {
sewardj73b58bc2004-07-01 18:30:56 +0000257
sewardj2cd80dc2004-07-02 15:20:40 +0000258 (*getRegUsage)( &reg_usage, instrs_in->arr[ii] );
sewardj73b58bc2004-07-01 18:30:56 +0000259
sewardj81497442004-07-02 17:30:07 +0000260 fprintf(stdout, "\n%d stage1: ", ii);
261 ppX86Instr(stdout, instrs_in->arr[ii]);
262 fprintf(stdout, "\n");
263 ppHRegUsage(stdout, &reg_usage);
264
sewardj73b58bc2004-07-01 18:30:56 +0000265 /* for each reg mentioned in the insn ... */
sewardjaf5a5222004-07-01 23:14:42 +0000266 for (j = 0; j < reg_usage.n_used; j++) {
sewardj73b58bc2004-07-01 18:30:56 +0000267
268 /* only interested in virtual registers right now. */
sewardjaf5a5222004-07-01 23:14:42 +0000269 if (!hregIsVirtual(reg_usage.hreg[j]))
sewardj73b58bc2004-07-01 18:30:56 +0000270 continue;
sewardjaf5a5222004-07-01 23:14:42 +0000271 k = hregNumber(reg_usage.hreg[j]);
sewardj81497442004-07-02 17:30:07 +0000272 if (k < 0 || k >= n_vregs)
273 panic("doRegisterAllocation: out-of-range vreg");
sewardjaf5a5222004-07-01 23:14:42 +0000274 switch (reg_usage.mode[j]) {
sewardj73b58bc2004-07-01 18:30:56 +0000275 case HRmRead:
sewardjaf5a5222004-07-01 23:14:42 +0000276 if (vreg_info[k].live_after == INVALID_INSTRNO)
sewardj73b58bc2004-07-01 18:30:56 +0000277 panic("doRegisterAllocation: "
278 "first event for vreg is Read");
sewardjaf5a5222004-07-01 23:14:42 +0000279 vreg_info[k].dead_before = ii;
sewardj73b58bc2004-07-01 18:30:56 +0000280 break;
281 case HRmWrite:
sewardjaf5a5222004-07-01 23:14:42 +0000282 if (vreg_info[k].live_after == INVALID_INSTRNO)
283 vreg_info[k].live_after = ii;
284 vreg_info[k].dead_before = ii + 1;
sewardj73b58bc2004-07-01 18:30:56 +0000285 break;
286 case HRmModify:
sewardjaf5a5222004-07-01 23:14:42 +0000287 if (vreg_info[k].live_after == INVALID_INSTRNO)
sewardj73b58bc2004-07-01 18:30:56 +0000288 panic("doRegisterAllocation: "
289 "first event for vreg is Modify");
sewardjaf5a5222004-07-01 23:14:42 +0000290 vreg_info[k].dead_before = ii + 1;
sewardj73b58bc2004-07-01 18:30:56 +0000291 break;
292 default:
293 panic("doRegisterAllocation(1)");
294 } /* switch */
295
296 } /* iterate over registers */
297
298 } /* iterate over insns */
299
sewardj81497442004-07-02 17:30:07 +0000300 for (j = 0; j < n_vregs; j++) {
301 fprintf(stdout, "vreg %d: la = %d, db = %d\n",
302 j, vreg_info[j].live_after, vreg_info[j].dead_before );
303 }
sewardj73b58bc2004-07-01 18:30:56 +0000304
305 /* --------- Stage 2: compute rreg live ranges. --------- */
306
307 /* This is more complex than Stage 1, because we need to compute
308 exactly all the live ranges of all the allocatable real regs,
309 and we don't know in advance how many there will be. */
310
sewardj73b58bc2004-07-01 18:30:56 +0000311 rreg_info_used = 0;
312 rreg_info_size = 4;
313 rreg_info = malloc(rreg_info_size * sizeof(RRegInfo));
314
315 /* We'll need to track live range start/end points seperately for
316 each rreg. Sigh. */
sewardj73b58bc2004-07-01 18:30:56 +0000317 assert(n_available_real_regs > 0);
318 rreg_live_after = malloc(n_available_real_regs * sizeof(Int));
319 rreg_dead_before = malloc(n_available_real_regs * sizeof(Int));
320
sewardjaf5a5222004-07-01 23:14:42 +0000321 for (j = 0; j < n_available_real_regs; j++)
322 rreg_live_after[j] =
323 rreg_dead_before[j] = INVALID_INSTRNO;
sewardj73b58bc2004-07-01 18:30:56 +0000324
325 /* for each insn ... */
sewardj2cd80dc2004-07-02 15:20:40 +0000326 for (ii = 0; ii < instrs_in->arr_used; ii++) {
sewardj73b58bc2004-07-01 18:30:56 +0000327
sewardj2cd80dc2004-07-02 15:20:40 +0000328 (*getRegUsage)( &reg_usage, instrs_in->arr[ii] );
sewardj73b58bc2004-07-01 18:30:56 +0000329
330 /* for each reg mentioned in the insn ... */
sewardjaf5a5222004-07-01 23:14:42 +0000331 for (j = 0; j < reg_usage.n_used; j++) {
sewardj73b58bc2004-07-01 18:30:56 +0000332
sewardjb3d4ce72004-07-02 07:09:23 +0000333 /* Dummy initialisations of flush_la and flush_db to avoid
334 possible bogus uninit-var warnings from gcc. */
335 Int flush_la = INVALID_INSTRNO, flush_db = INVALID_INSTRNO;
sewardj73b58bc2004-07-01 18:30:56 +0000336 Bool flush;
sewardj73b58bc2004-07-01 18:30:56 +0000337
sewardjaf5a5222004-07-01 23:14:42 +0000338 rreg = reg_usage.hreg[j];
sewardj73b58bc2004-07-01 18:30:56 +0000339
340 /* only interested in real registers right now. */
sewardjaf5a5222004-07-01 23:14:42 +0000341 if (hregIsVirtual(rreg))
sewardj73b58bc2004-07-01 18:30:56 +0000342 continue;
343
344 /* Furthermore, we're not interested in this rreg unless it's
345 one of the allocatable ones. For example, it could be a
346 stack pointer register, or some other register beyond our
347 control, in which case we should just ignore it. */
sewardjaf5a5222004-07-01 23:14:42 +0000348 for (k = 0; k < n_available_real_regs; k++)
349 if (available_real_regs[k] == rreg)
350 break;
351 if (k == n_available_real_regs)
352 continue; /* not found -- ignore. */
sewardj73b58bc2004-07-01 18:30:56 +0000353 flush = False;
sewardjaf5a5222004-07-01 23:14:42 +0000354 switch (reg_usage.mode[j]) {
sewardj73b58bc2004-07-01 18:30:56 +0000355 case HRmWrite:
sewardjaf5a5222004-07-01 23:14:42 +0000356 flush_la = rreg_live_after[k];
357 flush_db = rreg_dead_before[k];
sewardj81497442004-07-02 17:30:07 +0000358 if (flush_la != INVALID_INSTRNO
359 && flush_db != INVALID_INSTRNO)
360 flush = True;
sewardjaf5a5222004-07-01 23:14:42 +0000361 rreg_live_after[k] = ii;
362 rreg_dead_before[k] = ii+1;
sewardj73b58bc2004-07-01 18:30:56 +0000363 break;
364 case HRmRead:
sewardjaf5a5222004-07-01 23:14:42 +0000365 if (rreg_live_after[k] == INVALID_INSTRNO)
sewardj73b58bc2004-07-01 18:30:56 +0000366 panic("doRegisterAllocation: "
367 "first event for rreg is Read");
sewardjaf5a5222004-07-01 23:14:42 +0000368 rreg_dead_before[k] = ii;
sewardj73b58bc2004-07-01 18:30:56 +0000369 break;
370 case HRmModify:
sewardjaf5a5222004-07-01 23:14:42 +0000371 if (rreg_live_after[k] == INVALID_INSTRNO)
sewardj73b58bc2004-07-01 18:30:56 +0000372 panic("doRegisterAllocation: "
373 "first event for rreg is Modify");
sewardjaf5a5222004-07-01 23:14:42 +0000374 rreg_dead_before[k] = ii+1;
sewardj73b58bc2004-07-01 18:30:56 +0000375 break;
376 default:
377 panic("doRegisterAllocation(2)");
378 }
379
380 if (flush) {
sewardj81497442004-07-02 17:30:07 +0000381 assert(flush_la != INVALID_INSTRNO);
382 assert(flush_db != INVALID_INSTRNO);
383 printf("FLUSH 1 (%d,%d)\n", flush_la, flush_db);
sewardj73b58bc2004-07-01 18:30:56 +0000384 if (rreg_info_used == rreg_info_size) {
385 panic("make rreg info array bigger(1)");
386 }
sewardjaf5a5222004-07-01 23:14:42 +0000387 rreg_info[rreg_info_used].rreg = rreg;
388 rreg_info[rreg_info_used].live_after = flush_la;
sewardj73b58bc2004-07-01 18:30:56 +0000389 rreg_info[rreg_info_used].dead_before = flush_db;
sewardj81497442004-07-02 17:30:07 +0000390 rreg_info_used++;
sewardj73b58bc2004-07-01 18:30:56 +0000391 }
392
393 } /* iterate over regs in the instr */
394
395 } /* iterate over instrs */
396
397 /* Now finish up any live ranges left over. */
sewardjaf5a5222004-07-01 23:14:42 +0000398 for (j = 0; j < n_available_real_regs; j++) {
sewardj81497442004-07-02 17:30:07 +0000399
400# if 0
401 printf("residual %d: %d %d\n", j, rreg_live_after[j],
402 rreg_dead_before[j]);
403# endif
404 assert( (rreg_live_after[j] == INVALID_INSTRNO
405 && rreg_dead_before[j] == INVALID_INSTRNO)
406 ||
407 (rreg_live_after[j] != INVALID_INSTRNO
408 && rreg_dead_before[j] != INVALID_INSTRNO)
409 );
410
sewardjaf5a5222004-07-01 23:14:42 +0000411 if (rreg_live_after[j] == INVALID_INSTRNO)
sewardj73b58bc2004-07-01 18:30:56 +0000412 continue;
413 if (rreg_info_used == rreg_info_size) {
414 panic("make rreg info array bigger(2)");
415 }
sewardjaf5a5222004-07-01 23:14:42 +0000416 rreg_info[rreg_info_used].rreg = available_real_regs[j];
417 rreg_info[rreg_info_used].live_after = rreg_live_after[j];
418 rreg_info[rreg_info_used].dead_before = rreg_dead_before[j];
sewardj81497442004-07-02 17:30:07 +0000419 rreg_info_used++;
sewardj73b58bc2004-07-01 18:30:56 +0000420 }
421
422 free(rreg_live_after);
423 free(rreg_dead_before);
424
sewardj81497442004-07-02 17:30:07 +0000425# if 1
426 for (j = 0; j < rreg_info_used; j++) {
427 ppHReg(stdout, rreg_info[j].rreg);
428 fprintf(stdout, " la = %d, db = %d\n",
429 rreg_info[j].live_after, rreg_info[j].dead_before );
430 }
431# endif
sewardj73b58bc2004-07-01 18:30:56 +0000432
433 /* --------- Stage 3: allocate spill slots. --------- */
434
435 /* Each spill slot is 8 bytes long. For 128-bit vregs
436 we'll have to allocate two spill slots. For now, tho,
437 ignore the 128-bit problem.
438
439 Do a rank-based allocation of vregs to spill slot numbers. We
440 put as few values as possible in spill slows, but nevertheless
441 need to have a spill slot available for all vregs, just in case.
442 */
sewardjb3d4ce72004-07-02 07:09:23 +0000443 /* max_ss_no = -1; */
sewardj73b58bc2004-07-01 18:30:56 +0000444
sewardjaf5a5222004-07-01 23:14:42 +0000445 for (j = 0; j < N_SPILL64S; j++)
446 ss_busy_until_before[j] = 0;
sewardj73b58bc2004-07-01 18:30:56 +0000447
sewardjaf5a5222004-07-01 23:14:42 +0000448 for (j = 0; j < n_vregs; j++) {
sewardj73b58bc2004-07-01 18:30:56 +0000449
450 /* True iff this vreg is unused. */
sewardjaf5a5222004-07-01 23:14:42 +0000451 if (vreg_info[j].live_after == INVALID_INSTRNO)
sewardj73b58bc2004-07-01 18:30:56 +0000452 continue;
453
454 /* Find the lowest-numbered spill slot which is available at the
455 start point of this interval, and assign the interval to
456 it. */
sewardjaf5a5222004-07-01 23:14:42 +0000457 for (k = 0; k < N_SPILL64S; k++)
458 if (ss_busy_until_before[k] <= vreg_info[j].live_after)
sewardj73b58bc2004-07-01 18:30:56 +0000459 break;
sewardjaf5a5222004-07-01 23:14:42 +0000460 if (k == N_SPILL64S) {
sewardj73b58bc2004-07-01 18:30:56 +0000461 panic("N_SPILL64S is too low");
462 }
sewardjaf5a5222004-07-01 23:14:42 +0000463 ss_busy_until_before[k] = vreg_info[j].dead_before;
464 vreg_info[j].spill_offset = k * 8;
sewardjb3d4ce72004-07-02 07:09:23 +0000465 /* if (j > max_ss_no) */
466 /* max_ss_no = j; */
sewardj73b58bc2004-07-01 18:30:56 +0000467 }
468
sewardj81497442004-07-02 17:30:07 +0000469 fprintf(stdout, "\n\n");
470 for (j = 0; j < n_vregs; j++)
471 fprintf(stdout, "vreg %d --> spill offset %d\n",
472 j, vreg_info[j].spill_offset);
sewardj73b58bc2004-07-01 18:30:56 +0000473
474 /* --------- Stage 4: establish rreg preferences --------- */
475
476 /* It may be advantageous to allocating certain vregs to specific
477 rregs, as a way of avoiding reg-reg moves later. Here we
478 establish which, if any, rreg each vreg would prefer to be in.
479 Note that this constrains the allocator -- ideally we end up
480 with as few as possible vregs expressing a preference. */
481
482 /* For now, ignore this. It's only an optimisation, not needed for
483 correctness. */
484
485
486 /* --------- Stage 5: process instructions --------- */
487
488 /* This is the main loop of the allocator. First, we need to
489 correctly set up our running state, which tracks the status of
490 each real register. */
491
sewardjaf5a5222004-07-01 23:14:42 +0000492 /* n_state is no more than a short name for n_available_real_regs. */
493 n_state = n_available_real_regs;
sewardj62c41422004-07-01 21:00:22 +0000494 state = malloc(n_available_real_regs * sizeof(RRegState));
sewardj73b58bc2004-07-01 18:30:56 +0000495
sewardjaf5a5222004-07-01 23:14:42 +0000496 for (j = 0; j < n_state; j++) {
497 state[j].rreg = available_real_regs[j];
498 state[j].disp = Free;
499 state[j].vreg = INVALID_HREG;
500 state[j].is_spill_cand = False;
sewardj73b58bc2004-07-01 18:30:56 +0000501 }
502
sewardj0ec33252004-07-03 13:30:00 +0000503 /* ------ BEGIN: Process each insn in turn. ------ */
504
sewardj2cd80dc2004-07-02 15:20:40 +0000505 for (ii = 0; ii < instrs_in->arr_used; ii++) {
sewardj73b58bc2004-07-01 18:30:56 +0000506
sewardj81497442004-07-02 17:30:07 +0000507 fprintf(stdout, "\n-----------\n%d ", ii);
508 ppX86Instr(stdout, instrs_in->arr[ii]);
509 fprintf(stdout, "\n");
510 for (j = 0; j < n_state; j++) {
511 ppHReg(stdout, state[j].rreg);
512 fprintf(stdout, "\t ");
513 switch (state[j].disp) {
514 case Free: fprintf(stdout, "Free\n"); break;
515 case Unavail: fprintf(stdout, "Unavail\n"); break;
516 case Bound: fprintf(stdout, "BoundTo ");
517 ppHReg(stdout, state[j].vreg);
518 fprintf(stdout, "\n"); break;
519 }
520 }
521 fprintf(stdout, "\n");
522
sewardj73b58bc2004-07-01 18:30:56 +0000523 /* ------ Sanity checks ------ */
524
525 /* Sanity check 1: all rregs with a hard live range crossing
526 this insn must be marked as unavailable in the running
527 state. */
sewardjaf5a5222004-07-01 23:14:42 +0000528 for (j = 0; j < rreg_info_used; j++) {
529 if (rreg_info[j].live_after < ii
530 && ii < rreg_info[j].dead_before) {
sewardj73b58bc2004-07-01 18:30:56 +0000531 /* ii is the middle of a hard live range for some real reg.
532 Check it's marked as such in the running state. */
sewardjaf5a5222004-07-01 23:14:42 +0000533 assert(state[rreg_info[j].rreg].disp == Unavail);
sewardj73b58bc2004-07-01 18:30:56 +0000534 }
535 }
536
537 /* Sanity check 2: conversely, all rregs marked as unavailable in
538 the running state must have a corresponding hard live range
539 entry in the rreg_info array. */
sewardjaf5a5222004-07-01 23:14:42 +0000540 for (j = 0; j < n_available_real_regs; j++) {
541 assert(state[j].disp == Free
542 || state[j].disp == Unavail
543 || state[j].disp == Bound);
544 if (state[j].disp != Unavail)
sewardj73b58bc2004-07-01 18:30:56 +0000545 continue;
sewardjaf5a5222004-07-01 23:14:42 +0000546 for (k = 0; k < rreg_info_used; k++)
547 if (rreg_info[k].rreg == state[j].rreg
548 && rreg_info[k].live_after < ii
549 && ii < rreg_info[k].dead_before)
sewardj73b58bc2004-07-01 18:30:56 +0000550 break;
sewardjaf5a5222004-07-01 23:14:42 +0000551 /* If this assertion fails, we couldn't find a correspond
552 HLR. */
553 assert(k < rreg_info_used);
sewardj73b58bc2004-07-01 18:30:56 +0000554 }
555
556 /* Sanity check 3: No vreg is bound to more than one rreg. */
sewardjaf5a5222004-07-01 23:14:42 +0000557 for (j = 0; j < n_state; j++) {
558 if (state[j].disp != Bound)
sewardj73b58bc2004-07-01 18:30:56 +0000559 continue;
sewardjaf5a5222004-07-01 23:14:42 +0000560 for (k = j+1; k < n_state; k++)
561 if (state[k].disp == Bound)
562 assert(state[k].vreg != state[j].vreg);
sewardj73b58bc2004-07-01 18:30:56 +0000563 }
564
565 /* Sanity check 4: all vreg-rreg bindings must bind registers of
566 the same class. */
sewardjaf5a5222004-07-01 23:14:42 +0000567 for (j = 0; j < n_state; j++) {
568 if (state[j].disp != Bound)
sewardj73b58bc2004-07-01 18:30:56 +0000569 continue;
sewardjaf5a5222004-07-01 23:14:42 +0000570 assert(hregClass(state[j].rreg) == hregClass(state[j].vreg));
571 assert( hregIsVirtual(state[j].vreg));
572 assert(!hregIsVirtual(state[j].rreg));
sewardj73b58bc2004-07-01 18:30:56 +0000573 }
574
575 /* ------ end of Sanity checks ------ */
576
577 /* Do various optimisations pertaining to register coalescing
578 and preferencing:
sewardj968396e2004-07-03 14:50:33 +0000579 MOV v <-> v coalescing (done here).
580 MOV v <-> r coalescing (not yet, if ever)
sewardj73b58bc2004-07-01 18:30:56 +0000581 */
sewardj968396e2004-07-03 14:50:33 +0000582 /* If doing a reg-reg move between two vregs, and the src's live
583 range ends here and the dst's live range starts here, bind
584 the dst to the src's rreg, and that's all. */
585 if ( (*isMove)( instrs_in->arr[ii], &vregS, &vregD ) ) {
586 if (!hregIsVirtual(vregS)) goto cannot_coalesce;
587 if (!hregIsVirtual(vregD)) goto cannot_coalesce;
588 /* Check that *isMove is not telling us a bunch of lies ... */
589 assert(hregClass(vregS) == hregClass(vregD));
590 k = hregNumber(vregS);
591 m = hregNumber(vregD);
592 assert(k >= 0 && k < n_vregs);
593 assert(m >= 0 && m < n_vregs);
594 if (vreg_info[k].dead_before != ii) goto cannot_coalesce;
595 if (vreg_info[m].live_after != ii) goto cannot_coalesce;
596 printf("COALESCE ");
597 ppHReg(stdout, vregS);
598 printf(" -> ");
599 ppHReg(stdout, vregD);
600 printf("\n");
601
602 /* Ok, we can do it. Find the state entry for vregS. */
603 for (m = 0; m < n_state; m++)
604 if (state[m].disp == Bound && state[m].vreg == vregS)
605 break;
606 /* If this fails, we have no binding for vregS, which
607 cannot be correct. */
608 assert(m < n_state);
609 /* Claim it for vregD. */
610 state[m].vreg = vregD;
611 /* Don't bother to copy this insn, just move on to the next
612 insn. */
613 continue;
614 }
615 cannot_coalesce:
sewardj73b58bc2004-07-01 18:30:56 +0000616
sewardj0ec33252004-07-03 13:30:00 +0000617 /* ------ Pre-instruction actions for fixed rreg uses ------ */
sewardj81497442004-07-02 17:30:07 +0000618
sewardj73b58bc2004-07-01 18:30:56 +0000619 /* Now we have to deal with rregs which are about to be made
620 live by this instruction -- in other words, are entering into
621 one of their live ranges. If any such rreg holds a vreg, we
sewardj0ec33252004-07-03 13:30:00 +0000622 will have to free up the rreg. The simplest solution which
623 is correct is to spill the rreg.
sewardj73b58bc2004-07-01 18:30:56 +0000624
625 Note we could do better:
626 * Could move it into some other free rreg, if one is available
627 * Don't bother to spill if the spill-slot value is known to
628 be consistent.
sewardj0ec33252004-07-03 13:30:00 +0000629 * If the associated vreg live range ends at this insn,
630 no point in spilling or moving, since (in principle) the
631 rreg will be free anyway after that.
sewardj73b58bc2004-07-01 18:30:56 +0000632
633 Simplest way to do this is to iterate over the collection
634 of rreg live ranges.
635 */
sewardjaf5a5222004-07-01 23:14:42 +0000636 for (j = 0; j < rreg_info_used; j++) {
sewardj0ec33252004-07-03 13:30:00 +0000637 if (rreg_info[j].live_after == ii) {
638 /* rreg_info[j].rreg needs to be freed up. Find
639 the associated state entry. */
640 printf("need to free up rreg: ");
641 ppHReg(stdout, rreg_info[j].rreg);
642 printf("\n");
643 for (k = 0; k < n_state; k++)
644 if (state[k].rreg == rreg_info[j].rreg)
645 break;
646 /* If this fails, we don't have an entry for this rreg.
647 Which we should. */
648 assert(k < n_state);
649 if (state[k].disp == Bound) {
650 /* Yes, there is an associated vreg. Spill it if it's
651 still live. */
sewardjaf5a5222004-07-01 23:14:42 +0000652 m = hregNumber(state[k].vreg);
653 assert(m >= 0 && m < n_vregs);
sewardj0ec33252004-07-03 13:30:00 +0000654 if (vreg_info[m].dead_before > ii)
655 EMIT_INSTR( (*genSpill)( state[k].rreg,
656 vreg_info[m].spill_offset ) );
sewardj62c41422004-07-01 21:00:22 +0000657 }
sewardj0ec33252004-07-03 13:30:00 +0000658 state[k].disp = Unavail;
659 state[k].vreg = INVALID_HREG;
sewardj62c41422004-07-01 21:00:22 +0000660 }
661 }
662
sewardj0ec33252004-07-03 13:30:00 +0000663 /* ------ Deal with the current instruction. ------ */
664
sewardj62c41422004-07-01 21:00:22 +0000665 /* Finally we can begin the processing of this instruction
666 itself. The aim is to free up enough rregs for this insn.
667 This may generate spill stores since we may have to evict
668 some vregs currently in rregs. Also generates spill loads.
669 We also build up the final vreg->rreg mapping to be applied
670 to the insn. */
671
sewardj2cd80dc2004-07-02 15:20:40 +0000672 (*getRegUsage)( &reg_usage, instrs_in->arr[ii] );
sewardj62c41422004-07-01 21:00:22 +0000673
sewardj62c41422004-07-01 21:00:22 +0000674 initHRegRemap(&remap);
675
676 /* for each reg mentioned in the insn ... */
677 for (j = 0; j < reg_usage.n_used; j++) {
678
679 vreg = reg_usage.hreg[j];
680
681 /* only interested in virtual registers right now. */
682 if (!hregIsVirtual(vreg))
683 continue;
684
sewardj0ec33252004-07-03 13:30:00 +0000685 printf("considering "); ppHReg(stdout, vreg); printf("\n");
686
sewardj62c41422004-07-01 21:00:22 +0000687 /* Now we're trying to find a rreg for "vreg". First of all,
688 if it already has an rreg assigned, we don't need to do
689 anything more. Search the current state to find out. */
690 for (k = 0; k < n_state; k++)
691 if (state[k].vreg == vreg && state[k].disp == Bound)
692 break;
693 if (k < n_state) {
sewardjaf5a5222004-07-01 23:14:42 +0000694 addToHRegRemap(&remap, vreg, state[k].rreg);
sewardj62c41422004-07-01 21:00:22 +0000695 continue;
696 }
697
698 /* No luck. The next thing to do is see if there is a
699 currently free rreg available, of the correct class. If
sewardj0ec33252004-07-03 13:30:00 +0000700 so, bag it. NOTE, we could improve this by selecting an
701 rreg for which the next live-range event is as far ahead
702 as possible. */
703 for (k = 0; k < n_state; k++) {
sewardj62c41422004-07-01 21:00:22 +0000704 if (state[k].disp == Free
sewardj0ec33252004-07-03 13:30:00 +0000705 && hregClass(state[k].rreg) == hregClass(vreg))
sewardj62c41422004-07-01 21:00:22 +0000706 break;
sewardj0ec33252004-07-03 13:30:00 +0000707 }
sewardj62c41422004-07-01 21:00:22 +0000708 if (k < n_state) {
709 state[k].disp = Bound;
710 state[k].vreg = vreg;
sewardjaf5a5222004-07-01 23:14:42 +0000711 addToHRegRemap(&remap, vreg, state[k].rreg);
sewardj0ec33252004-07-03 13:30:00 +0000712 /* Generate a reload if needed. */
713 if (reg_usage.mode[j] != HRmWrite) {
714 m = hregNumber(vreg);
715 assert(m >= 0 && m < n_vregs);
716 EMIT_INSTR( (*genReload)( state[k].rreg,
717 vreg_info[m].spill_offset ) );
718 }
sewardj62c41422004-07-01 21:00:22 +0000719 continue;
720 }
721
sewardj0ec33252004-07-03 13:30:00 +0000722 /* There are no free rregs, but perhaps we can find one which
723 is bound to a vreg which is now dead. If so, use that.
724 NOTE, we could improve this by selecting an rreg for which
725 the next live-range event is as far ahead as possible. */
726 for (k = 0; k < n_state; k++) {
727 if (state[k].disp == Bound
728 && hregClass(state[k].rreg) == hregClass(vreg)) {
729 m = hregNumber(state[k].vreg);
730 assert(m >= 0 && m < n_vregs);
731 if (vreg_info[m].dead_before <= ii) {
732 /* Ok, it's gone dead before this insn. We can use
733 it. */
734 break;
735 }
736 }
737 }
738 if (k < n_state) {
739 assert(state[k].disp == Bound);
740 state[k].vreg = vreg;
741 addToHRegRemap(&remap, vreg, state[k].rreg);
742 /* Generate a reload if needed. */
743 if (reg_usage.mode[j] != HRmWrite) {
744 m = hregNumber(vreg);
745 assert(m >= 0 && m < n_vregs);
746 EMIT_INSTR( (*genReload)( state[k].rreg,
747 vreg_info[m].spill_offset ) );
748 }
749 continue;
750 }
751
752 /* Well, now we have no option but to spill a vreg. It's
753 important to make a good choice of vreg to spill, and of
754 course we need to be careful not to spill a vreg which is
755 needed by this insn. */
sewardj62c41422004-07-01 21:00:22 +0000756
757 /* First, mark in the state, those rregs which are not spill
758 candidates, due to holding a vreg mentioned by this
759 instruction. Or being of the wrong class. */
760 for (k = 0; k < n_state; k++) {
sewardjb3d4ce72004-07-02 07:09:23 +0000761 state[k].is_spill_cand = False;
762 if (state[k].disp != Bound)
763 continue;
764 if (hregClass(state[k].rreg) != hregClass(vreg))
765 continue;
766 state[k].is_spill_cand = True;
767 for (m = 0; m < reg_usage.n_used; m++) {
768 if (state[k].vreg == reg_usage.hreg[m]) {
769 state[k].is_spill_cand = False;
770 break;
771 }
772 }
sewardj62c41422004-07-01 21:00:22 +0000773 }
774
sewardj0ec33252004-07-03 13:30:00 +0000775 /* We can choose to spill any rreg satisfying
776 state[r].is_spill_cand (so to speak). Choose r so that
777 the next use of its associated vreg is as far ahead as
778 possible, in the hope that this will minimise the number
779 of consequent reloads required. */
780 spillee
781 = findMostDistantlyMentionedVReg (
782 getRegUsage, instrs_in, ii+1, state, n_state );
sewardj62c41422004-07-01 21:00:22 +0000783
sewardj0ec33252004-07-03 13:30:00 +0000784 if (spillee == -1) {
sewardj62c41422004-07-01 21:00:22 +0000785 /* Hmmmmm. There don't appear to be any spill candidates.
786 We're hosed. */
787 fprintf(stderr, "reg_alloc: can't find a register in class: ");
788 ppHRegClass(stderr, hregClass(vreg));
789 fprintf(stderr, "\n");
790 panic("reg_alloc: can't create a free register.");
791 }
792
sewardj0ec33252004-07-03 13:30:00 +0000793 /* Right. So we're going to spill state[spillee]. */
794 assert(spillee >= 0 && spillee < n_state);
795 assert(state[spillee].disp == Bound);
sewardj62c41422004-07-01 21:00:22 +0000796 /* check it's the right class */
sewardj0ec33252004-07-03 13:30:00 +0000797 assert(hregClass(state[spillee].rreg) == hregClass(vreg));
sewardj62c41422004-07-01 21:00:22 +0000798 /* check we're not ejecting the vreg for which we are trying
799 to free up a register. */
sewardj0ec33252004-07-03 13:30:00 +0000800 assert(state[spillee].vreg != vreg);
sewardj62c41422004-07-01 21:00:22 +0000801
sewardj0ec33252004-07-03 13:30:00 +0000802 m = hregNumber(state[spillee].vreg);
sewardj62c41422004-07-01 21:00:22 +0000803 assert(m >= 0 && m < n_vregs);
sewardj62c41422004-07-01 21:00:22 +0000804
sewardj0ec33252004-07-03 13:30:00 +0000805 /* So here's the spill store. Assert that we're spilling a
806 live vreg. */
807 assert(vreg_info[m].dead_before > ii);
808 EMIT_INSTR( (*genSpill)( state[spillee].rreg,
809 vreg_info[m].spill_offset ) );
sewardj62c41422004-07-01 21:00:22 +0000810
811 /* Update the state to reflect the new assignment for this
812 rreg. */
sewardj0ec33252004-07-03 13:30:00 +0000813 state[spillee].vreg = vreg;
sewardj62c41422004-07-01 21:00:22 +0000814
815 /* Now, if this vreg is being read or modified (as opposed to
816 written), we have to generate a reload for it. */
817 if (reg_usage.mode[j] != HRmWrite) {
818 m = hregNumber(vreg);
819 assert(m >= 0 && m < n_vregs);
sewardj0ec33252004-07-03 13:30:00 +0000820 EMIT_INSTR( (*genReload)( state[spillee].rreg,
821 vreg_info[m].spill_offset ) );
822
sewardj62c41422004-07-01 21:00:22 +0000823 }
824
825 /* So after much twisting and turning, we have vreg mapped to
826 state[furthest_k].rreg. Note that in the map. */
sewardj0ec33252004-07-03 13:30:00 +0000827 addToHRegRemap(&remap, vreg, state[spillee].rreg);
sewardj62c41422004-07-01 21:00:22 +0000828
829 } /* iterate over registers in this instruction. */
830
831 /* We've finished clowning around with registers in this instruction.
832 Three results:
833 - the running state[] has been updated
834 - a suitable vreg->rreg mapping for this instruction has been
835 constructed
836 - spill and reload instructions may have been emitted.
837
838 The final step is to apply the mapping to the instruction,
839 and emit that.
840 */
841
sewardj2cd80dc2004-07-02 15:20:40 +0000842 /* NOTE, DESTRUCTIVELY MODIFIES instrs_in->arr[ii]. */
843 (*mapRegs)( &remap, instrs_in->arr[ii] );
sewardj0ec33252004-07-03 13:30:00 +0000844 EMIT_INSTR( instrs_in->arr[ii] );
845
846 /* ------ Post-instruction actions for fixed rreg uses ------ */
847
848 /* Now we need to check for rregs exiting fixed live ranges
849 after this instruction, and if so mark them as free. */
850
851 for (j = 0; j < rreg_info_used; j++) {
852 if (rreg_info[j].dead_before == ii+1) {
853 /* rreg_info[j].rreg is exiting a hard live range. Mark
854 it as such in the main state array. */
855 for (k = 0; k < n_state; k++)
856 if (state[k].rreg == rreg_info[j].rreg)
857 break;
858 /* If this assertion fails, we don't have an entry for
859 this rreg. Which we should. */
860 assert(k < n_state);
861 assert(state[k].disp == Unavail);
862 state[k].disp = Free;
863 state[k].vreg = INVALID_HREG;
864 }
865 }
sewardj73b58bc2004-07-01 18:30:56 +0000866
867 } /* iterate over insns */
868
sewardj0ec33252004-07-03 13:30:00 +0000869 /* ------ END: Process each insn in turn. ------ */
870
sewardj62c41422004-07-01 21:00:22 +0000871 free(state);
sewardj62c41422004-07-01 21:00:22 +0000872 free(rreg_info);
873 if (vreg_info) free(vreg_info);
sewardjaf5a5222004-07-01 23:14:42 +0000874
sewardjb3d4ce72004-07-02 07:09:23 +0000875 return instrs_out;
sewardjaf5a5222004-07-01 23:14:42 +0000876
sewardjb3d4ce72004-07-02 07:09:23 +0000877# undef INVALID_INSTRNO
878# undef EMIT_INSTR
sewardj73b58bc2004-07-01 18:30:56 +0000879}
880
881
882
883/*---------------------------------------------------------------*/
884/*--- reg_alloc.c ---*/
885/*---------------------------------------------------------------*/