Mercurial > hg > CbC > CbC_gcc
comparison gcc/hsa-regalloc.c @ 111:04ced10e8804
gcc 7
author | kono |
---|---|
date | Fri, 27 Oct 2017 22:46:09 +0900 |
parents | |
children | 84e7813d76e9 |
comparison
equal
deleted
inserted
replaced
68:561a7518be6b | 111:04ced10e8804 |
---|---|
1 /* HSAIL IL Register allocation and out-of-SSA. | |
2 Copyright (C) 2013-2017 Free Software Foundation, Inc. | |
3 Contributed by Michael Matz <matz@suse.de> | |
4 | |
5 This file is part of GCC. | |
6 | |
7 GCC is free software; you can redistribute it and/or modify | |
8 it under the terms of the GNU General Public License as published by | |
9 the Free Software Foundation; either version 3, or (at your option) | |
10 any later version. | |
11 | |
12 GCC is distributed in the hope that it will be useful, | |
13 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 GNU General Public License for more details. | |
16 | |
17 You should have received a copy of the GNU General Public License | |
18 along with GCC; see the file COPYING3. If not see | |
19 <http://www.gnu.org/licenses/>. */ | |
20 | |
21 #include "config.h" | |
22 #include "system.h" | |
23 #include "coretypes.h" | |
24 #include "tm.h" | |
25 #include "is-a.h" | |
26 #include "vec.h" | |
27 #include "tree.h" | |
28 #include "dominance.h" | |
29 #include "basic-block.h" | |
30 #include "cfg.h" | |
31 #include "cfganal.h" | |
32 #include "function.h" | |
33 #include "bitmap.h" | |
34 #include "dumpfile.h" | |
35 #include "cgraph.h" | |
36 #include "print-tree.h" | |
37 #include "cfghooks.h" | |
38 #include "symbol-summary.h" | |
39 #include "hsa-common.h" | |
40 | |
41 | |
42 /* Process a PHI node PHI of basic block BB as a part of naive out-f-ssa. */ | |
43 | |
44 static void | |
45 naive_process_phi (hsa_insn_phi *phi, const vec<edge> &predecessors) | |
46 { | |
47 unsigned count = phi->operand_count (); | |
48 for (unsigned i = 0; i < count; i++) | |
49 { | |
50 gcc_checking_assert (phi->get_op (i)); | |
51 hsa_op_base *op = phi->get_op (i); | |
52 hsa_bb *hbb; | |
53 edge e; | |
54 | |
55 if (!op) | |
56 break; | |
57 | |
58 e = predecessors[i]; | |
59 if (single_succ_p (e->src)) | |
60 hbb = hsa_bb_for_bb (e->src); | |
61 else | |
62 { | |
63 basic_block old_dest = e->dest; | |
64 hbb = hsa_init_new_bb (split_edge (e)); | |
65 | |
66 /* If switch insn used this edge, fix jump table. */ | |
67 hsa_bb *source = hsa_bb_for_bb (e->src); | |
68 hsa_insn_sbr *sbr; | |
69 if (source->m_last_insn | |
70 && (sbr = dyn_cast <hsa_insn_sbr *> (source->m_last_insn))) | |
71 sbr->replace_all_labels (old_dest, hbb->m_bb); | |
72 } | |
73 | |
74 hsa_build_append_simple_mov (phi->m_dest, op, hbb); | |
75 } | |
76 } | |
77 | |
78 /* Naive out-of SSA. */ | |
79 | |
80 static void | |
81 naive_outof_ssa (void) | |
82 { | |
83 basic_block bb; | |
84 | |
85 hsa_cfun->m_in_ssa = false; | |
86 | |
87 FOR_ALL_BB_FN (bb, cfun) | |
88 { | |
89 hsa_bb *hbb = hsa_bb_for_bb (bb); | |
90 hsa_insn_phi *phi; | |
91 | |
92 /* naive_process_phi can call split_edge on an incoming edge which order if | |
93 the incoming edges to the basic block and thus make it inconsistent with | |
94 the ordering of PHI arguments, so we collect them in advance. */ | |
95 auto_vec<edge, 8> predecessors; | |
96 unsigned pred_count = EDGE_COUNT (bb->preds); | |
97 for (unsigned i = 0; i < pred_count; i++) | |
98 predecessors.safe_push (EDGE_PRED (bb, i)); | |
99 | |
100 for (phi = hbb->m_first_phi; | |
101 phi; | |
102 phi = phi->m_next ? as_a <hsa_insn_phi *> (phi->m_next) : NULL) | |
103 naive_process_phi (phi, predecessors); | |
104 | |
105 /* Zap PHI nodes, they will be deallocated when everything else will. */ | |
106 hbb->m_first_phi = NULL; | |
107 hbb->m_last_phi = NULL; | |
108 } | |
109 } | |
110 | |
111 /* Return register class number for the given HSA TYPE. 0 means the 'c' one | |
112 bit register class, 1 means 's' 32 bit class, 2 stands for 'd' 64 bit class | |
113 and 3 for 'q' 128 bit class. */ | |
114 | |
115 static int | |
116 m_reg_class_for_type (BrigType16_t type) | |
117 { | |
118 switch (type) | |
119 { | |
120 case BRIG_TYPE_B1: | |
121 return 0; | |
122 | |
123 case BRIG_TYPE_U8: | |
124 case BRIG_TYPE_U16: | |
125 case BRIG_TYPE_U32: | |
126 case BRIG_TYPE_S8: | |
127 case BRIG_TYPE_S16: | |
128 case BRIG_TYPE_S32: | |
129 case BRIG_TYPE_F16: | |
130 case BRIG_TYPE_F32: | |
131 case BRIG_TYPE_B8: | |
132 case BRIG_TYPE_B16: | |
133 case BRIG_TYPE_B32: | |
134 case BRIG_TYPE_U8X4: | |
135 case BRIG_TYPE_S8X4: | |
136 case BRIG_TYPE_U16X2: | |
137 case BRIG_TYPE_S16X2: | |
138 case BRIG_TYPE_F16X2: | |
139 return 1; | |
140 | |
141 case BRIG_TYPE_U64: | |
142 case BRIG_TYPE_S64: | |
143 case BRIG_TYPE_F64: | |
144 case BRIG_TYPE_B64: | |
145 case BRIG_TYPE_U8X8: | |
146 case BRIG_TYPE_S8X8: | |
147 case BRIG_TYPE_U16X4: | |
148 case BRIG_TYPE_S16X4: | |
149 case BRIG_TYPE_F16X4: | |
150 case BRIG_TYPE_U32X2: | |
151 case BRIG_TYPE_S32X2: | |
152 case BRIG_TYPE_F32X2: | |
153 return 2; | |
154 | |
155 case BRIG_TYPE_B128: | |
156 case BRIG_TYPE_U8X16: | |
157 case BRIG_TYPE_S8X16: | |
158 case BRIG_TYPE_U16X8: | |
159 case BRIG_TYPE_S16X8: | |
160 case BRIG_TYPE_F16X8: | |
161 case BRIG_TYPE_U32X4: | |
162 case BRIG_TYPE_U64X2: | |
163 case BRIG_TYPE_S32X4: | |
164 case BRIG_TYPE_S64X2: | |
165 case BRIG_TYPE_F32X4: | |
166 case BRIG_TYPE_F64X2: | |
167 return 3; | |
168 | |
169 default: | |
170 gcc_unreachable (); | |
171 } | |
172 } | |
173 | |
174 /* If the Ith operands of INSN is or contains a register (in an address), | |
175 return the address of that register operand. If not return NULL. */ | |
176 | |
177 static hsa_op_reg ** | |
178 insn_reg_addr (hsa_insn_basic *insn, int i) | |
179 { | |
180 hsa_op_base *op = insn->get_op (i); | |
181 if (!op) | |
182 return NULL; | |
183 hsa_op_reg *reg = dyn_cast <hsa_op_reg *> (op); | |
184 if (reg) | |
185 return (hsa_op_reg **) insn->get_op_addr (i); | |
186 hsa_op_address *addr = dyn_cast <hsa_op_address *> (op); | |
187 if (addr && addr->m_reg) | |
188 return &addr->m_reg; | |
189 return NULL; | |
190 } | |
191 | |
192 struct m_reg_class_desc | |
193 { | |
194 unsigned next_avail, max_num; | |
195 unsigned used_num, max_used; | |
196 uint64_t used[2]; | |
197 char cl_char; | |
198 }; | |
199 | |
200 /* Rewrite the instructions in BB to observe spilled live ranges. | |
201 CLASSES is the global register class state. */ | |
202 | |
203 static void | |
204 rewrite_code_bb (basic_block bb, struct m_reg_class_desc *classes) | |
205 { | |
206 hsa_bb *hbb = hsa_bb_for_bb (bb); | |
207 hsa_insn_basic *insn, *next_insn; | |
208 | |
209 for (insn = hbb->m_first_insn; insn; insn = next_insn) | |
210 { | |
211 next_insn = insn->m_next; | |
212 unsigned count = insn->operand_count (); | |
213 for (unsigned i = 0; i < count; i++) | |
214 { | |
215 gcc_checking_assert (insn->get_op (i)); | |
216 hsa_op_reg **regaddr = insn_reg_addr (insn, i); | |
217 | |
218 if (regaddr) | |
219 { | |
220 hsa_op_reg *reg = *regaddr; | |
221 if (reg->m_reg_class) | |
222 continue; | |
223 gcc_assert (reg->m_spill_sym); | |
224 | |
225 int cl = m_reg_class_for_type (reg->m_type); | |
226 hsa_op_reg *tmp, *tmp2; | |
227 if (insn->op_output_p (i)) | |
228 tmp = hsa_spill_out (insn, reg, &tmp2); | |
229 else | |
230 tmp = hsa_spill_in (insn, reg, &tmp2); | |
231 | |
232 *regaddr = tmp; | |
233 | |
234 tmp->m_reg_class = classes[cl].cl_char; | |
235 tmp->m_hard_num = (char) (classes[cl].max_num + i); | |
236 if (tmp2) | |
237 { | |
238 gcc_assert (cl == 0); | |
239 tmp2->m_reg_class = classes[1].cl_char; | |
240 tmp2->m_hard_num = (char) (classes[1].max_num + i); | |
241 } | |
242 } | |
243 } | |
244 } | |
245 } | |
246 | |
247 /* Dump current function to dump file F, with info specific | |
248 to register allocation. */ | |
249 | |
250 void | |
251 dump_hsa_cfun_regalloc (FILE *f) | |
252 { | |
253 basic_block bb; | |
254 | |
255 fprintf (f, "\nHSAIL IL for %s\n", hsa_cfun->m_name); | |
256 | |
257 FOR_ALL_BB_FN (bb, cfun) | |
258 { | |
259 hsa_bb *hbb = (struct hsa_bb *) bb->aux; | |
260 bitmap_print (dump_file, hbb->m_livein, "m_livein ", "\n"); | |
261 dump_hsa_bb (f, hbb); | |
262 bitmap_print (dump_file, hbb->m_liveout, "m_liveout ", "\n"); | |
263 } | |
264 } | |
265 | |
266 /* Given the global register allocation state CLASSES and a | |
267 register REG, try to give it a hardware register. If successful, | |
268 store that hardreg in REG and return it, otherwise return -1. | |
269 Also changes CLASSES to accommodate for the allocated register. */ | |
270 | |
271 static int | |
272 try_alloc_reg (struct m_reg_class_desc *classes, hsa_op_reg *reg) | |
273 { | |
274 int cl = m_reg_class_for_type (reg->m_type); | |
275 int ret = -1; | |
276 if (classes[1].used_num + classes[2].used_num * 2 + classes[3].used_num * 4 | |
277 >= 128 - 5) | |
278 return -1; | |
279 if (classes[cl].used_num < classes[cl].max_num) | |
280 { | |
281 unsigned int i; | |
282 classes[cl].used_num++; | |
283 if (classes[cl].used_num > classes[cl].max_used) | |
284 classes[cl].max_used = classes[cl].used_num; | |
285 for (i = 0; i < classes[cl].used_num; i++) | |
286 if (! (classes[cl].used[i / 64] & (((uint64_t)1) << (i & 63)))) | |
287 break; | |
288 ret = i; | |
289 classes[cl].used[i / 64] |= (((uint64_t)1) << (i & 63)); | |
290 reg->m_reg_class = classes[cl].cl_char; | |
291 reg->m_hard_num = i; | |
292 } | |
293 return ret; | |
294 } | |
295 | |
296 /* Free up hardregs used by REG, into allocation state CLASSES. */ | |
297 | |
298 static void | |
299 free_reg (struct m_reg_class_desc *classes, hsa_op_reg *reg) | |
300 { | |
301 int cl = m_reg_class_for_type (reg->m_type); | |
302 int ret = reg->m_hard_num; | |
303 gcc_assert (reg->m_reg_class == classes[cl].cl_char); | |
304 classes[cl].used_num--; | |
305 classes[cl].used[ret / 64] &= ~(((uint64_t)1) << (ret & 63)); | |
306 } | |
307 | |
308 /* Note that the live range for REG ends at least at END. */ | |
309 | |
310 static void | |
311 note_lr_end (hsa_op_reg *reg, int end) | |
312 { | |
313 if (reg->m_lr_end < end) | |
314 reg->m_lr_end = end; | |
315 } | |
316 | |
317 /* Note that the live range for REG starts at least at BEGIN. */ | |
318 | |
319 static void | |
320 note_lr_begin (hsa_op_reg *reg, int begin) | |
321 { | |
322 if (reg->m_lr_begin > begin) | |
323 reg->m_lr_begin = begin; | |
324 } | |
325 | |
326 /* Given two registers A and B, return -1, 0 or 1 if A's live range | |
327 starts before, at or after B's live range. */ | |
328 | |
329 static int | |
330 cmp_begin (const void *a, const void *b) | |
331 { | |
332 const hsa_op_reg * const *rega = (const hsa_op_reg * const *)a; | |
333 const hsa_op_reg * const *regb = (const hsa_op_reg * const *)b; | |
334 int ret; | |
335 if (rega == regb) | |
336 return 0; | |
337 ret = (*rega)->m_lr_begin - (*regb)->m_lr_begin; | |
338 if (ret) | |
339 return ret; | |
340 return ((*rega)->m_order - (*regb)->m_order); | |
341 } | |
342 | |
343 /* Given two registers REGA and REGB, return true if REGA's | |
344 live range ends after REGB's. This results in a sorting order | |
345 with earlier end points at the end. */ | |
346 | |
347 static bool | |
348 cmp_end (hsa_op_reg * const ®a, hsa_op_reg * const ®b) | |
349 { | |
350 int ret; | |
351 if (rega == regb) | |
352 return false; | |
353 ret = (regb)->m_lr_end - (rega)->m_lr_end; | |
354 if (ret) | |
355 return ret < 0; | |
356 return (((regb)->m_order - (rega)->m_order)) < 0; | |
357 } | |
358 | |
359 /* Expire all old intervals in ACTIVE (a per-regclass vector), | |
360 that is, those that end before the interval REG starts. Give | |
361 back resources freed so into the state CLASSES. */ | |
362 | |
363 static void | |
364 expire_old_intervals (hsa_op_reg *reg, vec<hsa_op_reg*> *active, | |
365 struct m_reg_class_desc *classes) | |
366 { | |
367 for (int i = 0; i < 4; i++) | |
368 while (!active[i].is_empty ()) | |
369 { | |
370 hsa_op_reg *a = active[i].pop (); | |
371 if (a->m_lr_end > reg->m_lr_begin) | |
372 { | |
373 active[i].quick_push (a); | |
374 break; | |
375 } | |
376 free_reg (classes, a); | |
377 } | |
378 } | |
379 | |
380 /* The interval REG didn't get a hardreg. Spill it or one of those | |
381 from ACTIVE (if the latter, then REG will become allocated to the | |
382 hardreg that formerly was used by it). */ | |
383 | |
384 static void | |
385 spill_at_interval (hsa_op_reg *reg, vec<hsa_op_reg*> *active) | |
386 { | |
387 int cl = m_reg_class_for_type (reg->m_type); | |
388 gcc_assert (!active[cl].is_empty ()); | |
389 hsa_op_reg *cand = active[cl][0]; | |
390 if (cand->m_lr_end > reg->m_lr_end) | |
391 { | |
392 reg->m_reg_class = cand->m_reg_class; | |
393 reg->m_hard_num = cand->m_hard_num; | |
394 active[cl].ordered_remove (0); | |
395 unsigned place = active[cl].lower_bound (reg, cmp_end); | |
396 active[cl].quick_insert (place, reg); | |
397 } | |
398 else | |
399 cand = reg; | |
400 | |
401 gcc_assert (!cand->m_spill_sym); | |
402 BrigType16_t type = cand->m_type; | |
403 if (type == BRIG_TYPE_B1) | |
404 type = BRIG_TYPE_U8; | |
405 cand->m_reg_class = 0; | |
406 cand->m_spill_sym = hsa_get_spill_symbol (type); | |
407 cand->m_spill_sym->m_name_number = cand->m_order; | |
408 } | |
409 | |
410 /* Given the global register state CLASSES allocate all HSA virtual | |
411 registers either to hardregs or to a spill symbol. */ | |
412 | |
413 static void | |
414 linear_scan_regalloc (struct m_reg_class_desc *classes) | |
415 { | |
416 /* Compute liveness. */ | |
417 bool changed; | |
418 int i, n; | |
419 int insn_order; | |
420 int *bbs = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); | |
421 bitmap work = BITMAP_ALLOC (NULL); | |
422 vec<hsa_op_reg*> ind2reg = vNULL; | |
423 vec<hsa_op_reg*> active[4] = {vNULL, vNULL, vNULL, vNULL}; | |
424 hsa_insn_basic *m_last_insn; | |
425 | |
426 /* We will need the reverse post order for linearization, | |
427 and the post order for liveness analysis, which is the same | |
428 backward. */ | |
429 n = pre_and_rev_post_order_compute (NULL, bbs, true); | |
430 ind2reg.safe_grow_cleared (hsa_cfun->m_reg_count); | |
431 | |
432 /* Give all instructions a linearized number, at the same time | |
433 build a mapping from register index to register. */ | |
434 insn_order = 1; | |
435 for (i = 0; i < n; i++) | |
436 { | |
437 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bbs[i]); | |
438 hsa_bb *hbb = hsa_bb_for_bb (bb); | |
439 hsa_insn_basic *insn; | |
440 for (insn = hbb->m_first_insn; insn; insn = insn->m_next) | |
441 { | |
442 unsigned opi; | |
443 insn->m_number = insn_order++; | |
444 for (opi = 0; opi < insn->operand_count (); opi++) | |
445 { | |
446 gcc_checking_assert (insn->get_op (opi)); | |
447 hsa_op_reg **regaddr = insn_reg_addr (insn, opi); | |
448 if (regaddr) | |
449 ind2reg[(*regaddr)->m_order] = *regaddr; | |
450 } | |
451 } | |
452 } | |
453 | |
454 /* Initialize all live ranges to [after-end, 0). */ | |
455 for (i = 0; i < hsa_cfun->m_reg_count; i++) | |
456 if (ind2reg[i]) | |
457 ind2reg[i]->m_lr_begin = insn_order, ind2reg[i]->m_lr_end = 0; | |
458 | |
459 /* Classic liveness analysis, as long as something changes: | |
460 m_liveout is union (m_livein of successors) | |
461 m_livein is m_liveout minus defs plus uses. */ | |
462 do | |
463 { | |
464 changed = false; | |
465 for (i = n - 1; i >= 0; i--) | |
466 { | |
467 edge e; | |
468 edge_iterator ei; | |
469 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bbs[i]); | |
470 hsa_bb *hbb = hsa_bb_for_bb (bb); | |
471 | |
472 /* Union of successors m_livein (or empty if none). */ | |
473 bool first = true; | |
474 FOR_EACH_EDGE (e, ei, bb->succs) | |
475 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) | |
476 { | |
477 hsa_bb *succ = hsa_bb_for_bb (e->dest); | |
478 if (first) | |
479 { | |
480 bitmap_copy (work, succ->m_livein); | |
481 first = false; | |
482 } | |
483 else | |
484 bitmap_ior_into (work, succ->m_livein); | |
485 } | |
486 if (first) | |
487 bitmap_clear (work); | |
488 | |
489 bitmap_copy (hbb->m_liveout, work); | |
490 | |
491 /* Remove defs, include uses in a backward insn walk. */ | |
492 hsa_insn_basic *insn; | |
493 for (insn = hbb->m_last_insn; insn; insn = insn->m_prev) | |
494 { | |
495 unsigned opi; | |
496 unsigned ndefs = insn->input_count (); | |
497 for (opi = 0; opi < ndefs && insn->get_op (opi); opi++) | |
498 { | |
499 gcc_checking_assert (insn->get_op (opi)); | |
500 hsa_op_reg **regaddr = insn_reg_addr (insn, opi); | |
501 if (regaddr) | |
502 bitmap_clear_bit (work, (*regaddr)->m_order); | |
503 } | |
504 for (; opi < insn->operand_count (); opi++) | |
505 { | |
506 gcc_checking_assert (insn->get_op (opi)); | |
507 hsa_op_reg **regaddr = insn_reg_addr (insn, opi); | |
508 if (regaddr) | |
509 bitmap_set_bit (work, (*regaddr)->m_order); | |
510 } | |
511 } | |
512 | |
513 /* Note if that changed something. */ | |
514 if (bitmap_ior_into (hbb->m_livein, work)) | |
515 changed = true; | |
516 } | |
517 } | |
518 while (changed); | |
519 | |
520 /* Make one pass through all instructions in linear order, | |
521 noting and merging possible live range start and end points. */ | |
522 m_last_insn = NULL; | |
523 for (i = n - 1; i >= 0; i--) | |
524 { | |
525 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bbs[i]); | |
526 hsa_bb *hbb = hsa_bb_for_bb (bb); | |
527 hsa_insn_basic *insn; | |
528 int after_end_number; | |
529 unsigned bit; | |
530 bitmap_iterator bi; | |
531 | |
532 if (m_last_insn) | |
533 after_end_number = m_last_insn->m_number; | |
534 else | |
535 after_end_number = insn_order; | |
536 /* Everything live-out in this BB has at least an end point | |
537 after us. */ | |
538 EXECUTE_IF_SET_IN_BITMAP (hbb->m_liveout, 0, bit, bi) | |
539 note_lr_end (ind2reg[bit], after_end_number); | |
540 | |
541 for (insn = hbb->m_last_insn; insn; insn = insn->m_prev) | |
542 { | |
543 unsigned opi; | |
544 unsigned ndefs = insn->input_count (); | |
545 for (opi = 0; opi < insn->operand_count (); opi++) | |
546 { | |
547 gcc_checking_assert (insn->get_op (opi)); | |
548 hsa_op_reg **regaddr = insn_reg_addr (insn, opi); | |
549 if (regaddr) | |
550 { | |
551 hsa_op_reg *reg = *regaddr; | |
552 if (opi < ndefs) | |
553 note_lr_begin (reg, insn->m_number); | |
554 else | |
555 note_lr_end (reg, insn->m_number); | |
556 } | |
557 } | |
558 } | |
559 | |
560 /* Everything live-in in this BB has a start point before | |
561 our first insn. */ | |
562 int before_start_number; | |
563 if (hbb->m_first_insn) | |
564 before_start_number = hbb->m_first_insn->m_number; | |
565 else | |
566 before_start_number = after_end_number; | |
567 before_start_number--; | |
568 EXECUTE_IF_SET_IN_BITMAP (hbb->m_livein, 0, bit, bi) | |
569 note_lr_begin (ind2reg[bit], before_start_number); | |
570 | |
571 if (hbb->m_first_insn) | |
572 m_last_insn = hbb->m_first_insn; | |
573 } | |
574 | |
575 for (i = 0; i < hsa_cfun->m_reg_count; i++) | |
576 if (ind2reg[i]) | |
577 { | |
578 /* All regs that have still their start at after all code actually | |
579 are defined at the start of the routine (prologue). */ | |
580 if (ind2reg[i]->m_lr_begin == insn_order) | |
581 ind2reg[i]->m_lr_begin = 0; | |
582 /* All regs that have no use but a def will have lr_end == 0, | |
583 they are actually live from def until after the insn they are | |
584 defined in. */ | |
585 if (ind2reg[i]->m_lr_end == 0) | |
586 ind2reg[i]->m_lr_end = ind2reg[i]->m_lr_begin + 1; | |
587 } | |
588 | |
589 /* Sort all intervals by increasing start point. */ | |
590 gcc_assert (ind2reg.length () == (size_t) hsa_cfun->m_reg_count); | |
591 | |
592 if (flag_checking) | |
593 for (unsigned i = 0; i < ind2reg.length (); i++) | |
594 gcc_assert (ind2reg[i]); | |
595 | |
596 ind2reg.qsort (cmp_begin); | |
597 for (i = 0; i < 4; i++) | |
598 active[i].reserve_exact (hsa_cfun->m_reg_count); | |
599 | |
600 /* Now comes the linear scan allocation. */ | |
601 for (i = 0; i < hsa_cfun->m_reg_count; i++) | |
602 { | |
603 hsa_op_reg *reg = ind2reg[i]; | |
604 if (!reg) | |
605 continue; | |
606 expire_old_intervals (reg, active, classes); | |
607 int cl = m_reg_class_for_type (reg->m_type); | |
608 if (try_alloc_reg (classes, reg) >= 0) | |
609 { | |
610 unsigned place = active[cl].lower_bound (reg, cmp_end); | |
611 active[cl].quick_insert (place, reg); | |
612 } | |
613 else | |
614 spill_at_interval (reg, active); | |
615 | |
616 /* Some interesting dumping as we go. */ | |
617 if (dump_file && (dump_flags & TDF_DETAILS)) | |
618 { | |
619 fprintf (dump_file, " reg%d: [%5d, %5d)->", | |
620 reg->m_order, reg->m_lr_begin, reg->m_lr_end); | |
621 if (reg->m_reg_class) | |
622 fprintf (dump_file, "$%c%i", reg->m_reg_class, reg->m_hard_num); | |
623 else | |
624 fprintf (dump_file, "[%%__%s_%i]", | |
625 hsa_seg_name (reg->m_spill_sym->m_segment), | |
626 reg->m_spill_sym->m_name_number); | |
627 for (int cl = 0; cl < 4; cl++) | |
628 { | |
629 bool first = true; | |
630 hsa_op_reg *r; | |
631 fprintf (dump_file, " {"); | |
632 for (int j = 0; active[cl].iterate (j, &r); j++) | |
633 if (first) | |
634 { | |
635 fprintf (dump_file, "%d", r->m_order); | |
636 first = false; | |
637 } | |
638 else | |
639 fprintf (dump_file, ", %d", r->m_order); | |
640 fprintf (dump_file, "}"); | |
641 } | |
642 fprintf (dump_file, "\n"); | |
643 } | |
644 } | |
645 | |
646 BITMAP_FREE (work); | |
647 free (bbs); | |
648 | |
649 if (dump_file && (dump_flags & TDF_DETAILS)) | |
650 { | |
651 fprintf (dump_file, "------- After liveness: -------\n"); | |
652 dump_hsa_cfun_regalloc (dump_file); | |
653 fprintf (dump_file, " ----- Intervals:\n"); | |
654 for (i = 0; i < hsa_cfun->m_reg_count; i++) | |
655 { | |
656 hsa_op_reg *reg = ind2reg[i]; | |
657 if (!reg) | |
658 continue; | |
659 fprintf (dump_file, " reg%d: [%5d, %5d)->", reg->m_order, | |
660 reg->m_lr_begin, reg->m_lr_end); | |
661 if (reg->m_reg_class) | |
662 fprintf (dump_file, "$%c%i\n", reg->m_reg_class, reg->m_hard_num); | |
663 else | |
664 fprintf (dump_file, "[%%__%s_%i]\n", | |
665 hsa_seg_name (reg->m_spill_sym->m_segment), | |
666 reg->m_spill_sym->m_name_number); | |
667 } | |
668 } | |
669 | |
670 for (i = 0; i < 4; i++) | |
671 active[i].release (); | |
672 ind2reg.release (); | |
673 } | |
674 | |
675 /* Entry point for register allocation. */ | |
676 | |
677 static void | |
678 regalloc (void) | |
679 { | |
680 basic_block bb; | |
681 m_reg_class_desc classes[4]; | |
682 | |
683 /* If there are no registers used in the function, exit right away. */ | |
684 if (hsa_cfun->m_reg_count == 0) | |
685 return; | |
686 | |
687 memset (classes, 0, sizeof (classes)); | |
688 classes[0].next_avail = 0; | |
689 classes[0].max_num = 7; | |
690 classes[0].cl_char = 'c'; | |
691 classes[1].cl_char = 's'; | |
692 classes[2].cl_char = 'd'; | |
693 classes[3].cl_char = 'q'; | |
694 | |
695 for (int i = 1; i < 4; i++) | |
696 { | |
697 classes[i].next_avail = 0; | |
698 classes[i].max_num = 20; | |
699 } | |
700 | |
701 linear_scan_regalloc (classes); | |
702 | |
703 FOR_ALL_BB_FN (bb, cfun) | |
704 rewrite_code_bb (bb, classes); | |
705 } | |
706 | |
707 /* Out of SSA and register allocation on HSAIL IL. */ | |
708 | |
709 void | |
710 hsa_regalloc (void) | |
711 { | |
712 hsa_cfun->update_dominance (); | |
713 naive_outof_ssa (); | |
714 | |
715 if (dump_file && (dump_flags & TDF_DETAILS)) | |
716 { | |
717 fprintf (dump_file, "------- After out-of-SSA: -------\n"); | |
718 dump_hsa_cfun (dump_file); | |
719 } | |
720 | |
721 regalloc (); | |
722 | |
723 if (dump_file && (dump_flags & TDF_DETAILS)) | |
724 { | |
725 fprintf (dump_file, "------- After register allocation: -------\n"); | |
726 dump_hsa_cfun (dump_file); | |
727 } | |
728 } |