1 /* IRA processing allocno lives to build allocno live ranges.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "regs.h"
27 #include "rtl.h"
28 #include "tm_p.h"
29 #include "target.h"
30 #include "flags.h"
31 #include "except.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
34 #include "insn-config.h"
35 #include "recog.h"
36 #include "diagnostic-core.h"
37 #include "params.h"
38 #include "df.h"
39 #include "sbitmap.h"
40 #include "sparseset.h"
41 #include "ira-int.h"
42
43 /* The code in this file is similar to one in global but the code
44 works on the allocno basis and creates live ranges instead of
45 pseudo-register conflicts. */
46
47 /* Program points are enumerated by numbers from range
48 0..IRA_MAX_POINT-1. There are approximately two times more program
49 points than insns. Program points are places in the program where
50 liveness info can be changed. In most general case (there are more
51 complicated cases too) some program points correspond to places
52 where input operand dies and other ones correspond to places where
53 output operands are born. */
54 int ira_max_point;
55
56 /* Arrays of size IRA_MAX_POINT mapping a program point to the allocno
57 live ranges with given start/finish point. */
58 live_range_t *ira_start_point_ranges, *ira_finish_point_ranges;
59
60 /* Number of the current program point. */
61 static int curr_point;
62
63 /* Point where register pressure excess started or -1 if there is no
64 register pressure excess. Excess pressure for a register class at
65 some point means that there are more allocnos of given register
66 class living at the point than number of hard-registers of the
67 class available for the allocation. It is defined only for
68 pressure classes. */
69 static int high_pressure_start_point[N_REG_CLASSES];
70
71 /* Objects live at current point in the scan. */
72 static sparseset objects_live;
73
74 /* A temporary bitmap used in functions that wish to avoid visiting an allocno
75 multiple times. */
76 static sparseset allocnos_processed;
77
78 /* Set of hard regs (except eliminable ones) currently live. */
79 static HARD_REG_SET hard_regs_live;
80
81 /* The loop tree node corresponding to the current basic block. */
82 static ira_loop_tree_node_t curr_bb_node;
83
84 /* The number of the last processed call. */
85 static int last_call_num;
86 /* The number of last call at which given allocno was saved. */
87 static int *allocno_saved_at_call;
88
89 /* Record the birth of hard register REGNO, updating hard_regs_live and
90 hard reg conflict information for living allocnos. */
91 static void
make_hard_regno_born(int regno)92 make_hard_regno_born (int regno)
93 {
94 unsigned int i;
95
96 SET_HARD_REG_BIT (hard_regs_live, regno);
97 EXECUTE_IF_SET_IN_SPARSESET (objects_live, i)
98 {
99 ira_object_t obj = ira_object_id_map[i];
100
101 SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj), regno);
102 SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), regno);
103 }
104 }
105
106 /* Process the death of hard register REGNO. This updates
107 hard_regs_live. */
108 static void
make_hard_regno_dead(int regno)109 make_hard_regno_dead (int regno)
110 {
111 CLEAR_HARD_REG_BIT (hard_regs_live, regno);
112 }
113
114 /* Record the birth of object OBJ. Set a bit for it in objects_live,
115 start a new live range for it if necessary and update hard register
116 conflicts. */
117 static void
make_object_born(ira_object_t obj)118 make_object_born (ira_object_t obj)
119 {
120 live_range_t lr = OBJECT_LIVE_RANGES (obj);
121
122 sparseset_set_bit (objects_live, OBJECT_CONFLICT_ID (obj));
123 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), hard_regs_live);
124 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), hard_regs_live);
125
126 if (lr == NULL
127 || (lr->finish != curr_point && lr->finish + 1 != curr_point))
128 ira_add_live_range_to_object (obj, curr_point, -1);
129 }
130
131 /* Update ALLOCNO_EXCESS_PRESSURE_POINTS_NUM for the allocno
132 associated with object OBJ. */
133 static void
update_allocno_pressure_excess_length(ira_object_t obj)134 update_allocno_pressure_excess_length (ira_object_t obj)
135 {
136 ira_allocno_t a = OBJECT_ALLOCNO (obj);
137 int start, i;
138 enum reg_class aclass, pclass, cl;
139 live_range_t p;
140
141 aclass = ALLOCNO_CLASS (a);
142 pclass = ira_pressure_class_translate[aclass];
143 for (i = 0;
144 (cl = ira_reg_class_super_classes[pclass][i]) != LIM_REG_CLASSES;
145 i++)
146 {
147 if (! ira_reg_pressure_class_p[cl])
148 continue;
149 if (high_pressure_start_point[cl] < 0)
150 continue;
151 p = OBJECT_LIVE_RANGES (obj);
152 ira_assert (p != NULL);
153 start = (high_pressure_start_point[cl] > p->start
154 ? high_pressure_start_point[cl] : p->start);
155 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) += curr_point - start + 1;
156 }
157 }
158
159 /* Process the death of object OBJ, which is associated with allocno
160 A. This finishes the current live range for it. */
161 static void
make_object_dead(ira_object_t obj)162 make_object_dead (ira_object_t obj)
163 {
164 live_range_t lr;
165
166 sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (obj));
167 lr = OBJECT_LIVE_RANGES (obj);
168 ira_assert (lr != NULL);
169 lr->finish = curr_point;
170 update_allocno_pressure_excess_length (obj);
171 }
172
173 /* The current register pressures for each pressure class for the current
174 basic block. */
175 static int curr_reg_pressure[N_REG_CLASSES];
176
177 /* Record that register pressure for PCLASS increased by N registers.
178 Update the current register pressure, maximal register pressure for
179 the current BB and the start point of the register pressure
180 excess. */
181 static void
inc_register_pressure(enum reg_class pclass,int n)182 inc_register_pressure (enum reg_class pclass, int n)
183 {
184 int i;
185 enum reg_class cl;
186
187 for (i = 0;
188 (cl = ira_reg_class_super_classes[pclass][i]) != LIM_REG_CLASSES;
189 i++)
190 {
191 if (! ira_reg_pressure_class_p[cl])
192 continue;
193 curr_reg_pressure[cl] += n;
194 if (high_pressure_start_point[cl] < 0
195 && (curr_reg_pressure[cl] > ira_available_class_regs[cl]))
196 high_pressure_start_point[cl] = curr_point;
197 if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl])
198 curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl];
199 }
200 }
201
202 /* Record that register pressure for PCLASS has decreased by NREGS
203 registers; update current register pressure, start point of the
204 register pressure excess, and register pressure excess length for
205 living allocnos. */
206
207 static void
dec_register_pressure(enum reg_class pclass,int nregs)208 dec_register_pressure (enum reg_class pclass, int nregs)
209 {
210 int i;
211 unsigned int j;
212 enum reg_class cl;
213 bool set_p = false;
214
215 for (i = 0;
216 (cl = ira_reg_class_super_classes[pclass][i]) != LIM_REG_CLASSES;
217 i++)
218 {
219 if (! ira_reg_pressure_class_p[cl])
220 continue;
221 curr_reg_pressure[cl] -= nregs;
222 ira_assert (curr_reg_pressure[cl] >= 0);
223 if (high_pressure_start_point[cl] >= 0
224 && curr_reg_pressure[cl] <= ira_available_class_regs[cl])
225 set_p = true;
226 }
227 if (set_p)
228 {
229 EXECUTE_IF_SET_IN_SPARSESET (objects_live, j)
230 update_allocno_pressure_excess_length (ira_object_id_map[j]);
231 for (i = 0;
232 (cl = ira_reg_class_super_classes[pclass][i]) != LIM_REG_CLASSES;
233 i++)
234 {
235 if (! ira_reg_pressure_class_p[cl])
236 continue;
237 if (high_pressure_start_point[cl] >= 0
238 && curr_reg_pressure[cl] <= ira_available_class_regs[cl])
239 high_pressure_start_point[cl] = -1;
240 }
241 }
242 }
243
244 /* Mark the pseudo register REGNO as live. Update all information about
245 live ranges and register pressure. */
246 static void
mark_pseudo_regno_live(int regno)247 mark_pseudo_regno_live (int regno)
248 {
249 ira_allocno_t a = ira_curr_regno_allocno_map[regno];
250 enum reg_class pclass;
251 int i, n, nregs;
252
253 if (a == NULL)
254 return;
255
256 /* Invalidate because it is referenced. */
257 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
258
259 n = ALLOCNO_NUM_OBJECTS (a);
260 pclass = ira_pressure_class_translate[ALLOCNO_CLASS (a)];
261 nregs = ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
262 if (n > 1)
263 {
264 /* We track every subobject separately. */
265 gcc_assert (nregs == n);
266 nregs = 1;
267 }
268
269 for (i = 0; i < n; i++)
270 {
271 ira_object_t obj = ALLOCNO_OBJECT (a, i);
272
273 if (sparseset_bit_p (objects_live, OBJECT_CONFLICT_ID (obj)))
274 continue;
275
276 inc_register_pressure (pclass, nregs);
277 make_object_born (obj);
278 }
279 }
280
281 /* Like mark_pseudo_regno_live, but try to only mark one subword of
282 the pseudo as live. SUBWORD indicates which; a value of 0
283 indicates the low part. */
284 static void
mark_pseudo_regno_subword_live(int regno,int subword)285 mark_pseudo_regno_subword_live (int regno, int subword)
286 {
287 ira_allocno_t a = ira_curr_regno_allocno_map[regno];
288 int n;
289 enum reg_class pclass;
290 ira_object_t obj;
291
292 if (a == NULL)
293 return;
294
295 /* Invalidate because it is referenced. */
296 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
297
298 n = ALLOCNO_NUM_OBJECTS (a);
299 if (n == 1)
300 {
301 mark_pseudo_regno_live (regno);
302 return;
303 }
304
305 pclass = ira_pressure_class_translate[ALLOCNO_CLASS (a)];
306 gcc_assert
307 (n == ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
308 obj = ALLOCNO_OBJECT (a, subword);
309
310 if (sparseset_bit_p (objects_live, OBJECT_CONFLICT_ID (obj)))
311 return;
312
313 inc_register_pressure (pclass, 1);
314 make_object_born (obj);
315 }
316
317 /* Mark the register REG as live. Store a 1 in hard_regs_live for
318 this register, record how many consecutive hardware registers it
319 actually needs. */
320 static void
mark_hard_reg_live(rtx reg)321 mark_hard_reg_live (rtx reg)
322 {
323 int regno = REGNO (reg);
324
325 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
326 {
327 int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
328 enum reg_class aclass, pclass;
329
330 while (regno < last)
331 {
332 if (! TEST_HARD_REG_BIT (hard_regs_live, regno)
333 && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
334 {
335 aclass = ira_hard_regno_allocno_class[regno];
336 pclass = ira_pressure_class_translate[aclass];
337 inc_register_pressure (pclass, 1);
338 make_hard_regno_born (regno);
339 }
340 regno++;
341 }
342 }
343 }
344
345 /* Mark a pseudo, or one of its subwords, as live. REGNO is the pseudo's
346 register number; ORIG_REG is the access in the insn, which may be a
347 subreg. */
348 static void
mark_pseudo_reg_live(rtx orig_reg,unsigned regno)349 mark_pseudo_reg_live (rtx orig_reg, unsigned regno)
350 {
351 if (df_read_modify_subreg_p (orig_reg))
352 {
353 mark_pseudo_regno_subword_live (regno,
354 subreg_lowpart_p (orig_reg) ? 0 : 1);
355 }
356 else
357 mark_pseudo_regno_live (regno);
358 }
359
360 /* Mark the register referenced by use or def REF as live. */
361 static void
mark_ref_live(df_ref ref)362 mark_ref_live (df_ref ref)
363 {
364 rtx reg = DF_REF_REG (ref);
365 rtx orig_reg = reg;
366
367 if (GET_CODE (reg) == SUBREG)
368 reg = SUBREG_REG (reg);
369
370 if (REGNO (reg) >= FIRST_PSEUDO_REGISTER)
371 mark_pseudo_reg_live (orig_reg, REGNO (reg));
372 else
373 mark_hard_reg_live (reg);
374 }
375
376 /* Mark the pseudo register REGNO as dead. Update all information about
377 live ranges and register pressure. */
378 static void
mark_pseudo_regno_dead(int regno)379 mark_pseudo_regno_dead (int regno)
380 {
381 ira_allocno_t a = ira_curr_regno_allocno_map[regno];
382 int n, i, nregs;
383 enum reg_class cl;
384
385 if (a == NULL)
386 return;
387
388 /* Invalidate because it is referenced. */
389 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
390
391 n = ALLOCNO_NUM_OBJECTS (a);
392 cl = ira_pressure_class_translate[ALLOCNO_CLASS (a)];
393 nregs = ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
394 if (n > 1)
395 {
396 /* We track every subobject separately. */
397 gcc_assert (nregs == n);
398 nregs = 1;
399 }
400 for (i = 0; i < n; i++)
401 {
402 ira_object_t obj = ALLOCNO_OBJECT (a, i);
403 if (!sparseset_bit_p (objects_live, OBJECT_CONFLICT_ID (obj)))
404 continue;
405
406 dec_register_pressure (cl, nregs);
407 make_object_dead (obj);
408 }
409 }
410
411 /* Like mark_pseudo_regno_dead, but called when we know that only part of the
412 register dies. SUBWORD indicates which; a value of 0 indicates the low part. */
413 static void
mark_pseudo_regno_subword_dead(int regno,int subword)414 mark_pseudo_regno_subword_dead (int regno, int subword)
415 {
416 ira_allocno_t a = ira_curr_regno_allocno_map[regno];
417 int n;
418 enum reg_class cl;
419 ira_object_t obj;
420
421 if (a == NULL)
422 return;
423
424 /* Invalidate because it is referenced. */
425 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
426
427 n = ALLOCNO_NUM_OBJECTS (a);
428 if (n == 1)
429 /* The allocno as a whole doesn't die in this case. */
430 return;
431
432 cl = ira_pressure_class_translate[ALLOCNO_CLASS (a)];
433 gcc_assert
434 (n == ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
435
436 obj = ALLOCNO_OBJECT (a, subword);
437 if (!sparseset_bit_p (objects_live, OBJECT_CONFLICT_ID (obj)))
438 return;
439
440 dec_register_pressure (cl, 1);
441 make_object_dead (obj);
442 }
443
444 /* Mark the hard register REG as dead. Store a 0 in hard_regs_live for the
445 register. */
446 static void
mark_hard_reg_dead(rtx reg)447 mark_hard_reg_dead (rtx reg)
448 {
449 int regno = REGNO (reg);
450
451 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
452 {
453 int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
454 enum reg_class aclass, pclass;
455
456 while (regno < last)
457 {
458 if (TEST_HARD_REG_BIT (hard_regs_live, regno))
459 {
460 aclass = ira_hard_regno_allocno_class[regno];
461 pclass = ira_pressure_class_translate[aclass];
462 dec_register_pressure (pclass, 1);
463 make_hard_regno_dead (regno);
464 }
465 regno++;
466 }
467 }
468 }
469
470 /* Mark a pseudo, or one of its subwords, as dead. REGNO is the pseudo's
471 register number; ORIG_REG is the access in the insn, which may be a
472 subreg. */
473 static void
mark_pseudo_reg_dead(rtx orig_reg,unsigned regno)474 mark_pseudo_reg_dead (rtx orig_reg, unsigned regno)
475 {
476 if (df_read_modify_subreg_p (orig_reg))
477 {
478 mark_pseudo_regno_subword_dead (regno,
479 subreg_lowpart_p (orig_reg) ? 0 : 1);
480 }
481 else
482 mark_pseudo_regno_dead (regno);
483 }
484
485 /* Mark the register referenced by definition DEF as dead, if the
486 definition is a total one. */
487 static void
mark_ref_dead(df_ref def)488 mark_ref_dead (df_ref def)
489 {
490 rtx reg = DF_REF_REG (def);
491 rtx orig_reg = reg;
492
493 if (DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL))
494 return;
495
496 if (GET_CODE (reg) == SUBREG)
497 reg = SUBREG_REG (reg);
498
499 if (DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL)
500 && (GET_CODE (orig_reg) != SUBREG
501 || REGNO (reg) < FIRST_PSEUDO_REGISTER
502 || !df_read_modify_subreg_p (orig_reg)))
503 return;
504
505 if (REGNO (reg) >= FIRST_PSEUDO_REGISTER)
506 mark_pseudo_reg_dead (orig_reg, REGNO (reg));
507 else
508 mark_hard_reg_dead (reg);
509 }
510
511 /* If REG is a pseudo or a subreg of it, and the class of its allocno
512 intersects CL, make a conflict with pseudo DREG. ORIG_DREG is the
513 rtx actually accessed, it may be indentical to DREG or a subreg of it.
514 Advance the current program point before making the conflict if
515 ADVANCE_P. Return TRUE if we will need to advance the current
516 program point. */
517 static bool
make_pseudo_conflict(rtx reg,enum reg_class cl,rtx dreg,rtx orig_dreg,bool advance_p)518 make_pseudo_conflict (rtx reg, enum reg_class cl, rtx dreg, rtx orig_dreg,
519 bool advance_p)
520 {
521 rtx orig_reg = reg;
522 ira_allocno_t a;
523
524 if (GET_CODE (reg) == SUBREG)
525 reg = SUBREG_REG (reg);
526
527 if (! REG_P (reg) || REGNO (reg) < FIRST_PSEUDO_REGISTER)
528 return advance_p;
529
530 a = ira_curr_regno_allocno_map[REGNO (reg)];
531 if (! reg_classes_intersect_p (cl, ALLOCNO_CLASS (a)))
532 return advance_p;
533
534 if (advance_p)
535 curr_point++;
536
537 mark_pseudo_reg_live (orig_reg, REGNO (reg));
538 mark_pseudo_reg_live (orig_dreg, REGNO (dreg));
539 mark_pseudo_reg_dead (orig_reg, REGNO (reg));
540 mark_pseudo_reg_dead (orig_dreg, REGNO (dreg));
541
542 return false;
543 }
544
545 /* Check and make if necessary conflicts for pseudo DREG of class
546 DEF_CL of the current insn with input operand USE of class USE_CL.
547 ORIG_DREG is the rtx actually accessed, it may be indentical to
548 DREG or a subreg of it. Advance the current program point before
549 making the conflict if ADVANCE_P. Return TRUE if we will need to
550 advance the current program point. */
551 static bool
check_and_make_def_use_conflict(rtx dreg,rtx orig_dreg,enum reg_class def_cl,int use,enum reg_class use_cl,bool advance_p)552 check_and_make_def_use_conflict (rtx dreg, rtx orig_dreg,
553 enum reg_class def_cl, int use,
554 enum reg_class use_cl, bool advance_p)
555 {
556 if (! reg_classes_intersect_p (def_cl, use_cl))
557 return advance_p;
558
559 advance_p = make_pseudo_conflict (recog_data.operand[use],
560 use_cl, dreg, orig_dreg, advance_p);
561
562 /* Reload may end up swapping commutative operands, so you
563 have to take both orderings into account. The
564 constraints for the two operands can be completely
565 different. (Indeed, if the constraints for the two
566 operands are the same for all alternatives, there's no
567 point marking them as commutative.) */
568 if (use < recog_data.n_operands - 1
569 && recog_data.constraints[use][0] == '%')
570 advance_p
571 = make_pseudo_conflict (recog_data.operand[use + 1],
572 use_cl, dreg, orig_dreg, advance_p);
573 if (use >= 1
574 && recog_data.constraints[use - 1][0] == '%')
575 advance_p
576 = make_pseudo_conflict (recog_data.operand[use - 1],
577 use_cl, dreg, orig_dreg, advance_p);
578 return advance_p;
579 }
580
581 /* Check and make if necessary conflicts for definition DEF of class
582 DEF_CL of the current insn with input operands. Process only
583 constraints of alternative ALT. */
584 static void
check_and_make_def_conflict(int alt,int def,enum reg_class def_cl)585 check_and_make_def_conflict (int alt, int def, enum reg_class def_cl)
586 {
587 int use, use_match;
588 ira_allocno_t a;
589 enum reg_class use_cl, acl;
590 bool advance_p;
591 rtx dreg = recog_data.operand[def];
592 rtx orig_dreg = dreg;
593
594 if (def_cl == NO_REGS)
595 return;
596
597 if (GET_CODE (dreg) == SUBREG)
598 dreg = SUBREG_REG (dreg);
599
600 if (! REG_P (dreg) || REGNO (dreg) < FIRST_PSEUDO_REGISTER)
601 return;
602
603 a = ira_curr_regno_allocno_map[REGNO (dreg)];
604 acl = ALLOCNO_CLASS (a);
605 if (! reg_classes_intersect_p (acl, def_cl))
606 return;
607
608 advance_p = true;
609
610 for (use = 0; use < recog_data.n_operands; use++)
611 {
612 int alt1;
613
614 if (use == def || recog_data.operand_type[use] == OP_OUT)
615 continue;
616
617 if (recog_op_alt[use][alt].anything_ok)
618 use_cl = ALL_REGS;
619 else
620 use_cl = recog_op_alt[use][alt].cl;
621
622 /* If there's any alternative that allows USE to match DEF, do not
623 record a conflict. If that causes us to create an invalid
624 instruction due to the earlyclobber, reload must fix it up. */
625 for (alt1 = 0; alt1 < recog_data.n_alternatives; alt1++)
626 if (recog_op_alt[use][alt1].matches == def
627 || (use < recog_data.n_operands - 1
628 && recog_data.constraints[use][0] == '%'
629 && recog_op_alt[use + 1][alt1].matches == def)
630 || (use >= 1
631 && recog_data.constraints[use - 1][0] == '%'
632 && recog_op_alt[use - 1][alt1].matches == def))
633 break;
634
635 if (alt1 < recog_data.n_alternatives)
636 continue;
637
638 advance_p = check_and_make_def_use_conflict (dreg, orig_dreg, def_cl,
639 use, use_cl, advance_p);
640
641 if ((use_match = recog_op_alt[use][alt].matches) >= 0)
642 {
643 if (use_match == def)
644 continue;
645
646 if (recog_op_alt[use_match][alt].anything_ok)
647 use_cl = ALL_REGS;
648 else
649 use_cl = recog_op_alt[use_match][alt].cl;
650 advance_p = check_and_make_def_use_conflict (dreg, orig_dreg, def_cl,
651 use, use_cl, advance_p);
652 }
653 }
654 }
655
656 /* Make conflicts of early clobber pseudo registers of the current
657 insn with its inputs. Avoid introducing unnecessary conflicts by
658 checking classes of the constraints and pseudos because otherwise
659 significant code degradation is possible for some targets. */
660 static void
make_early_clobber_and_input_conflicts(void)661 make_early_clobber_and_input_conflicts (void)
662 {
663 int alt;
664 int def, def_match;
665 enum reg_class def_cl;
666
667 for (alt = 0; alt < recog_data.n_alternatives; alt++)
668 for (def = 0; def < recog_data.n_operands; def++)
669 {
670 def_cl = NO_REGS;
671 if (recog_op_alt[def][alt].earlyclobber)
672 {
673 if (recog_op_alt[def][alt].anything_ok)
674 def_cl = ALL_REGS;
675 else
676 def_cl = recog_op_alt[def][alt].cl;
677 check_and_make_def_conflict (alt, def, def_cl);
678 }
679 if ((def_match = recog_op_alt[def][alt].matches) >= 0
680 && (recog_op_alt[def_match][alt].earlyclobber
681 || recog_op_alt[def][alt].earlyclobber))
682 {
683 if (recog_op_alt[def_match][alt].anything_ok)
684 def_cl = ALL_REGS;
685 else
686 def_cl = recog_op_alt[def_match][alt].cl;
687 check_and_make_def_conflict (alt, def, def_cl);
688 }
689 }
690 }
691
692 /* Mark early clobber hard registers of the current INSN as live (if
693 LIVE_P) or dead. Return true if there are such registers. */
694 static bool
mark_hard_reg_early_clobbers(rtx insn,bool live_p)695 mark_hard_reg_early_clobbers (rtx insn, bool live_p)
696 {
697 df_ref *def_rec;
698 bool set_p = false;
699
700 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
701 if (DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MUST_CLOBBER))
702 {
703 rtx dreg = DF_REF_REG (*def_rec);
704
705 if (GET_CODE (dreg) == SUBREG)
706 dreg = SUBREG_REG (dreg);
707 if (! REG_P (dreg) || REGNO (dreg) >= FIRST_PSEUDO_REGISTER)
708 continue;
709
710 /* Hard register clobbers are believed to be early clobber
711 because there is no way to say that non-operand hard
712 register clobbers are not early ones. */
713 if (live_p)
714 mark_ref_live (*def_rec);
715 else
716 mark_ref_dead (*def_rec);
717 set_p = true;
718 }
719
720 return set_p;
721 }
722
723 /* Checks that CONSTRAINTS permits to use only one hard register. If
724 it is so, the function returns the class of the hard register.
725 Otherwise it returns NO_REGS. */
726 static enum reg_class
single_reg_class(const char * constraints,rtx op,rtx equiv_const)727 single_reg_class (const char *constraints, rtx op, rtx equiv_const)
728 {
729 int curr_alt, c;
730 bool ignore_p;
731 enum reg_class cl, next_cl;
732
733 cl = NO_REGS;
734 for (ignore_p = false, curr_alt = 0;
735 (c = *constraints);
736 constraints += CONSTRAINT_LEN (c, constraints))
737 if (c == '#' || !recog_data.alternative_enabled_p[curr_alt])
738 ignore_p = true;
739 else if (c == ',')
740 {
741 curr_alt++;
742 ignore_p = false;
743 }
744 else if (! ignore_p)
745 switch (c)
746 {
747 case ' ':
748 case '\t':
749 case '=':
750 case '+':
751 case '*':
752 case '&':
753 case '%':
754 case '!':
755 case '?':
756 break;
757 case 'i':
758 if (CONSTANT_P (op)
759 || (equiv_const != NULL_RTX && CONSTANT_P (equiv_const)))
760 return NO_REGS;
761 break;
762
763 case 'n':
764 if (CONST_INT_P (op)
765 || (GET_CODE (op) == CONST_DOUBLE && GET_MODE (op) == VOIDmode)
766 || (equiv_const != NULL_RTX
767 && (CONST_INT_P (equiv_const)
768 || (GET_CODE (equiv_const) == CONST_DOUBLE
769 && GET_MODE (equiv_const) == VOIDmode))))
770 return NO_REGS;
771 break;
772
773 case 's':
774 if ((CONSTANT_P (op) && !CONST_INT_P (op)
775 && (GET_CODE (op) != CONST_DOUBLE || GET_MODE (op) != VOIDmode))
776 || (equiv_const != NULL_RTX
777 && CONSTANT_P (equiv_const)
778 && !CONST_INT_P (equiv_const)
779 && (GET_CODE (equiv_const) != CONST_DOUBLE
780 || GET_MODE (equiv_const) != VOIDmode)))
781 return NO_REGS;
782 break;
783
784 case 'I':
785 case 'J':
786 case 'K':
787 case 'L':
788 case 'M':
789 case 'N':
790 case 'O':
791 case 'P':
792 if ((CONST_INT_P (op)
793 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), c, constraints))
794 || (equiv_const != NULL_RTX
795 && CONST_INT_P (equiv_const)
796 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (equiv_const),
797 c, constraints)))
798 return NO_REGS;
799 break;
800
801 case 'E':
802 case 'F':
803 if (GET_CODE (op) == CONST_DOUBLE
804 || (GET_CODE (op) == CONST_VECTOR
805 && GET_MODE_CLASS (GET_MODE (op)) == MODE_VECTOR_FLOAT)
806 || (equiv_const != NULL_RTX
807 && (GET_CODE (equiv_const) == CONST_DOUBLE
808 || (GET_CODE (equiv_const) == CONST_VECTOR
809 && (GET_MODE_CLASS (GET_MODE (equiv_const))
810 == MODE_VECTOR_FLOAT)))))
811 return NO_REGS;
812 break;
813
814 case 'G':
815 case 'H':
816 if ((GET_CODE (op) == CONST_DOUBLE
817 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op, c, constraints))
818 || (equiv_const != NULL_RTX
819 && GET_CODE (equiv_const) == CONST_DOUBLE
820 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (equiv_const,
821 c, constraints)))
822 return NO_REGS;
823 /* ??? what about memory */
824 case 'r':
825 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
826 case 'h': case 'j': case 'k': case 'l':
827 case 'q': case 't': case 'u':
828 case 'v': case 'w': case 'x': case 'y': case 'z':
829 case 'A': case 'B': case 'C': case 'D':
830 case 'Q': case 'R': case 'S': case 'T': case 'U':
831 case 'W': case 'Y': case 'Z':
832 next_cl = (c == 'r'
833 ? GENERAL_REGS
834 : REG_CLASS_FROM_CONSTRAINT (c, constraints));
835 if ((cl != NO_REGS && next_cl != cl)
836 || (ira_available_class_regs[next_cl]
837 > ira_reg_class_max_nregs[next_cl][GET_MODE (op)]))
838 return NO_REGS;
839 cl = next_cl;
840 break;
841
842 case '0': case '1': case '2': case '3': case '4':
843 case '5': case '6': case '7': case '8': case '9':
844 next_cl
845 = single_reg_class (recog_data.constraints[c - '0'],
846 recog_data.operand[c - '0'], NULL_RTX);
847 if ((cl != NO_REGS && next_cl != cl)
848 || next_cl == NO_REGS
849 || (ira_available_class_regs[next_cl]
850 > ira_reg_class_max_nregs[next_cl][GET_MODE (op)]))
851 return NO_REGS;
852 cl = next_cl;
853 break;
854
855 default:
856 return NO_REGS;
857 }
858 return cl;
859 }
860
861 /* The function checks that operand OP_NUM of the current insn can use
862 only one hard register. If it is so, the function returns the
863 class of the hard register. Otherwise it returns NO_REGS. */
864 static enum reg_class
single_reg_operand_class(int op_num)865 single_reg_operand_class (int op_num)
866 {
867 if (op_num < 0 || recog_data.n_alternatives == 0)
868 return NO_REGS;
869 return single_reg_class (recog_data.constraints[op_num],
870 recog_data.operand[op_num], NULL_RTX);
871 }
872
873 /* The function sets up hard register set *SET to hard registers which
874 might be used by insn reloads because the constraints are too
875 strict. */
876 void
ira_implicitly_set_insn_hard_regs(HARD_REG_SET * set)877 ira_implicitly_set_insn_hard_regs (HARD_REG_SET *set)
878 {
879 int i, curr_alt, c, regno = 0;
880 bool ignore_p;
881 enum reg_class cl;
882 rtx op;
883 enum machine_mode mode;
884
885 CLEAR_HARD_REG_SET (*set);
886 for (i = 0; i < recog_data.n_operands; i++)
887 {
888 op = recog_data.operand[i];
889
890 if (GET_CODE (op) == SUBREG)
891 op = SUBREG_REG (op);
892
893 if (GET_CODE (op) == SCRATCH
894 || (REG_P (op) && (regno = REGNO (op)) >= FIRST_PSEUDO_REGISTER))
895 {
896 const char *p = recog_data.constraints[i];
897
898 mode = (GET_CODE (op) == SCRATCH
899 ? GET_MODE (op) : PSEUDO_REGNO_MODE (regno));
900 cl = NO_REGS;
901 for (ignore_p = false, curr_alt = 0;
902 (c = *p);
903 p += CONSTRAINT_LEN (c, p))
904 if (c == '#' || !recog_data.alternative_enabled_p[curr_alt])
905 ignore_p = true;
906 else if (c == ',')
907 {
908 curr_alt++;
909 ignore_p = false;
910 }
911 else if (! ignore_p)
912 switch (c)
913 {
914 case 'r':
915 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
916 case 'h': case 'j': case 'k': case 'l':
917 case 'q': case 't': case 'u':
918 case 'v': case 'w': case 'x': case 'y': case 'z':
919 case 'A': case 'B': case 'C': case 'D':
920 case 'Q': case 'R': case 'S': case 'T': case 'U':
921 case 'W': case 'Y': case 'Z':
922 cl = (c == 'r'
923 ? GENERAL_REGS
924 : REG_CLASS_FROM_CONSTRAINT (c, p));
925 if (cl != NO_REGS
926 /* There is no register pressure problem if all of the
927 regs in this class are fixed. */
928 && ira_available_class_regs[cl] != 0
929 && (ira_available_class_regs[cl]
930 <= ira_reg_class_max_nregs[cl][mode]))
931 IOR_HARD_REG_SET (*set, reg_class_contents[cl]);
932 break;
933 }
934 }
935 }
936 }
937 /* Processes input operands, if IN_P, or output operands otherwise of
938 the current insn with FREQ to find allocno which can use only one
939 hard register and makes other currently living allocnos conflicting
940 with the hard register. */
941 static void
process_single_reg_class_operands(bool in_p,int freq)942 process_single_reg_class_operands (bool in_p, int freq)
943 {
944 int i, regno;
945 unsigned int px;
946 enum reg_class cl;
947 rtx operand;
948 ira_allocno_t operand_a, a;
949
950 for (i = 0; i < recog_data.n_operands; i++)
951 {
952 operand = recog_data.operand[i];
953 if (in_p && recog_data.operand_type[i] != OP_IN
954 && recog_data.operand_type[i] != OP_INOUT)
955 continue;
956 if (! in_p && recog_data.operand_type[i] != OP_OUT
957 && recog_data.operand_type[i] != OP_INOUT)
958 continue;
959 cl = single_reg_operand_class (i);
960 if (cl == NO_REGS)
961 continue;
962
963 operand_a = NULL;
964
965 if (GET_CODE (operand) == SUBREG)
966 operand = SUBREG_REG (operand);
967
968 if (REG_P (operand)
969 && (regno = REGNO (operand)) >= FIRST_PSEUDO_REGISTER)
970 {
971 enum reg_class aclass;
972
973 operand_a = ira_curr_regno_allocno_map[regno];
974 aclass = ALLOCNO_CLASS (operand_a);
975 if (ira_class_subset_p[cl][aclass]
976 && ira_class_hard_regs_num[cl] != 0)
977 {
978 /* View the desired allocation of OPERAND as:
979
980 (REG:YMODE YREGNO),
981
982 a simplification of:
983
984 (subreg:YMODE (reg:XMODE XREGNO) OFFSET). */
985 enum machine_mode ymode, xmode;
986 int xregno, yregno;
987 HOST_WIDE_INT offset;
988
989 xmode = recog_data.operand_mode[i];
990 xregno = ira_class_hard_regs[cl][0];
991 ymode = ALLOCNO_MODE (operand_a);
992 offset = subreg_lowpart_offset (ymode, xmode);
993 yregno = simplify_subreg_regno (xregno, xmode, offset, ymode);
994 if (yregno >= 0
995 && ira_class_hard_reg_index[aclass][yregno] >= 0)
996 {
997 int cost;
998
999 ira_allocate_and_set_costs
1000 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a),
1001 aclass, 0);
1002 ira_init_register_move_cost_if_necessary (xmode);
1003 cost = freq * (in_p
1004 ? ira_register_move_cost[xmode][aclass][cl]
1005 : ira_register_move_cost[xmode][cl][aclass]);
1006 ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a)
1007 [ira_class_hard_reg_index[aclass][yregno]] -= cost;
1008 }
1009 }
1010 }
1011
1012 EXECUTE_IF_SET_IN_SPARSESET (objects_live, px)
1013 {
1014 ira_object_t obj = ira_object_id_map[px];
1015 a = OBJECT_ALLOCNO (obj);
1016 if (a != operand_a)
1017 {
1018 /* We could increase costs of A instead of making it
1019 conflicting with the hard register. But it works worse
1020 because it will be spilled in reload in anyway. */
1021 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
1022 reg_class_contents[cl]);
1023 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
1024 reg_class_contents[cl]);
1025 }
1026 }
1027 }
1028 }
1029
1030 /* Return true when one of the predecessor edges of BB is marked with
1031 EDGE_ABNORMAL_CALL or EDGE_EH. */
1032 static bool
bb_has_abnormal_call_pred(basic_block bb)1033 bb_has_abnormal_call_pred (basic_block bb)
1034 {
1035 edge e;
1036 edge_iterator ei;
1037
1038 FOR_EACH_EDGE (e, ei, bb->preds)
1039 {
1040 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
1041 return true;
1042 }
1043 return false;
1044 }
1045
1046 /* Process insns of the basic block given by its LOOP_TREE_NODE to
1047 update allocno live ranges, allocno hard register conflicts,
1048 intersected calls, and register pressure info for allocnos for the
1049 basic block for and regions containing the basic block. */
1050 static void
process_bb_node_lives(ira_loop_tree_node_t loop_tree_node)1051 process_bb_node_lives (ira_loop_tree_node_t loop_tree_node)
1052 {
1053 int i, freq;
1054 unsigned int j;
1055 basic_block bb;
1056 rtx insn;
1057 bitmap_iterator bi;
1058 bitmap reg_live_out;
1059 unsigned int px;
1060 bool set_p;
1061
1062 bb = loop_tree_node->bb;
1063 if (bb != NULL)
1064 {
1065 for (i = 0; i < ira_pressure_classes_num; i++)
1066 {
1067 curr_reg_pressure[ira_pressure_classes[i]] = 0;
1068 high_pressure_start_point[ira_pressure_classes[i]] = -1;
1069 }
1070 curr_bb_node = loop_tree_node;
1071 reg_live_out = DF_LR_OUT (bb);
1072 sparseset_clear (objects_live);
1073 REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
1074 AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset);
1075 AND_COMPL_HARD_REG_SET (hard_regs_live, ira_no_alloc_regs);
1076 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1077 if (TEST_HARD_REG_BIT (hard_regs_live, i))
1078 {
1079 enum reg_class aclass, pclass, cl;
1080
1081 aclass = ira_allocno_class_translate[REGNO_REG_CLASS (i)];
1082 pclass = ira_pressure_class_translate[aclass];
1083 for (j = 0;
1084 (cl = ira_reg_class_super_classes[pclass][j])
1085 != LIM_REG_CLASSES;
1086 j++)
1087 {
1088 if (! ira_reg_pressure_class_p[cl])
1089 continue;
1090 curr_reg_pressure[cl]++;
1091 if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl])
1092 curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl];
1093 ira_assert (curr_reg_pressure[cl]
1094 <= ira_available_class_regs[cl]);
1095 }
1096 }
1097 EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
1098 mark_pseudo_regno_live (j);
1099
1100 freq = REG_FREQ_FROM_BB (bb);
1101 if (freq == 0)
1102 freq = 1;
1103
1104 /* Invalidate all allocno_saved_at_call entries. */
1105 last_call_num++;
1106
1107 /* Scan the code of this basic block, noting which allocnos and
1108 hard regs are born or die.
1109
1110 Note that this loop treats uninitialized values as live until
1111 the beginning of the block. For example, if an instruction
1112 uses (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever
1113 set, FOO will remain live until the beginning of the block.
1114 Likewise if FOO is not set at all. This is unnecessarily
1115 pessimistic, but it probably doesn't matter much in practice. */
1116 FOR_BB_INSNS_REVERSE (bb, insn)
1117 {
1118 df_ref *def_rec, *use_rec;
1119 bool call_p;
1120
1121 if (!NONDEBUG_INSN_P (insn))
1122 continue;
1123
1124 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1125 fprintf (ira_dump_file, " Insn %u(l%d): point = %d\n",
1126 INSN_UID (insn), loop_tree_node->parent->loop_num,
1127 curr_point);
1128
1129 /* Mark each defined value as live. We need to do this for
1130 unused values because they still conflict with quantities
1131 that are live at the time of the definition.
1132
1133 Ignore DF_REF_MAY_CLOBBERs on a call instruction. Such
1134 references represent the effect of the called function
1135 on a call-clobbered register. Marking the register as
1136 live would stop us from allocating it to a call-crossing
1137 allocno. */
1138 call_p = CALL_P (insn);
1139 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
1140 if (!call_p || !DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MAY_CLOBBER))
1141 mark_ref_live (*def_rec);
1142
1143 /* If INSN has multiple outputs, then any value used in one
1144 of the outputs conflicts with the other outputs. Model this
1145 by making the used value live during the output phase.
1146
1147 It is unsafe to use !single_set here since it will ignore
1148 an unused output. Just because an output is unused does
1149 not mean the compiler can assume the side effect will not
1150 occur. Consider if ALLOCNO appears in the address of an
1151 output and we reload the output. If we allocate ALLOCNO
1152 to the same hard register as an unused output we could
1153 set the hard register before the output reload insn. */
1154 if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
1155 for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
1156 {
1157 int i;
1158 rtx reg;
1159
1160 reg = DF_REF_REG (*use_rec);
1161 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
1162 {
1163 rtx set;
1164
1165 set = XVECEXP (PATTERN (insn), 0, i);
1166 if (GET_CODE (set) == SET
1167 && reg_overlap_mentioned_p (reg, SET_DEST (set)))
1168 {
1169 /* After the previous loop, this is a no-op if
1170 REG is contained within SET_DEST (SET). */
1171 mark_ref_live (*use_rec);
1172 break;
1173 }
1174 }
1175 }
1176
1177 extract_insn (insn);
1178 preprocess_constraints ();
1179 process_single_reg_class_operands (false, freq);
1180
1181 /* See which defined values die here. */
1182 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
1183 if (!call_p || !DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MAY_CLOBBER))
1184 mark_ref_dead (*def_rec);
1185
1186 if (call_p)
1187 {
1188 last_call_num++;
1189 sparseset_clear (allocnos_processed);
1190 /* The current set of live allocnos are live across the call. */
1191 EXECUTE_IF_SET_IN_SPARSESET (objects_live, i)
1192 {
1193 ira_object_t obj = ira_object_id_map[i];
1194 ira_allocno_t a = OBJECT_ALLOCNO (obj);
1195 int num = ALLOCNO_NUM (a);
1196
1197 /* Don't allocate allocnos that cross setjmps or any
1198 call, if this function receives a nonlocal
1199 goto. */
1200 if (cfun->has_nonlocal_label
1201 || find_reg_note (insn, REG_SETJMP,
1202 NULL_RTX) != NULL_RTX)
1203 {
1204 SET_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj));
1205 SET_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
1206 }
1207 if (can_throw_internal (insn))
1208 {
1209 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
1210 call_used_reg_set);
1211 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
1212 call_used_reg_set);
1213 }
1214
1215 if (sparseset_bit_p (allocnos_processed, num))
1216 continue;
1217 sparseset_set_bit (allocnos_processed, num);
1218
1219 if (allocno_saved_at_call[num] != last_call_num)
1220 /* Here we are mimicking caller-save.c behaviour
1221 which does not save hard register at a call if
1222 it was saved on previous call in the same basic
1223 block and the hard register was not mentioned
1224 between the two calls. */
1225 ALLOCNO_CALL_FREQ (a) += freq;
1226 /* Mark it as saved at the next call. */
1227 allocno_saved_at_call[num] = last_call_num + 1;
1228 ALLOCNO_CALLS_CROSSED_NUM (a)++;
1229 }
1230 }
1231
1232 make_early_clobber_and_input_conflicts ();
1233
1234 curr_point++;
1235
1236 /* Mark each used value as live. */
1237 for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
1238 mark_ref_live (*use_rec);
1239
1240 process_single_reg_class_operands (true, freq);
1241
1242 set_p = mark_hard_reg_early_clobbers (insn, true);
1243
1244 if (set_p)
1245 {
1246 mark_hard_reg_early_clobbers (insn, false);
1247
1248 /* Mark each hard reg as live again. For example, a
1249 hard register can be in clobber and in an insn
1250 input. */
1251 for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
1252 {
1253 rtx ureg = DF_REF_REG (*use_rec);
1254
1255 if (GET_CODE (ureg) == SUBREG)
1256 ureg = SUBREG_REG (ureg);
1257 if (! REG_P (ureg) || REGNO (ureg) >= FIRST_PSEUDO_REGISTER)
1258 continue;
1259
1260 mark_ref_live (*use_rec);
1261 }
1262 }
1263
1264 curr_point++;
1265 }
1266
1267 #ifdef EH_RETURN_DATA_REGNO
1268 if (bb_has_eh_pred (bb))
1269 for (j = 0; ; ++j)
1270 {
1271 unsigned int regno = EH_RETURN_DATA_REGNO (j);
1272 if (regno == INVALID_REGNUM)
1273 break;
1274 make_hard_regno_born (regno);
1275 }
1276 #endif
1277
1278 /* Allocnos can't go in stack regs at the start of a basic block
1279 that is reached by an abnormal edge. Likewise for call
1280 clobbered regs, because caller-save, fixup_abnormal_edges and
1281 possibly the table driven EH machinery are not quite ready to
1282 handle such allocnos live across such edges. */
1283 if (bb_has_abnormal_pred (bb))
1284 {
1285 #ifdef STACK_REGS
1286 EXECUTE_IF_SET_IN_SPARSESET (objects_live, px)
1287 {
1288 ira_allocno_t a = OBJECT_ALLOCNO (ira_object_id_map[px]);
1289
1290 ALLOCNO_NO_STACK_REG_P (a) = true;
1291 ALLOCNO_TOTAL_NO_STACK_REG_P (a) = true;
1292 }
1293 for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
1294 make_hard_regno_born (px);
1295 #endif
1296 /* No need to record conflicts for call clobbered regs if we
1297 have nonlocal labels around, as we don't ever try to
1298 allocate such regs in this case. */
1299 if (!cfun->has_nonlocal_label && bb_has_abnormal_call_pred (bb))
1300 for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
1301 if (call_used_regs[px])
1302 make_hard_regno_born (px);
1303 }
1304
1305 EXECUTE_IF_SET_IN_SPARSESET (objects_live, i)
1306 make_object_dead (ira_object_id_map[i]);
1307
1308 curr_point++;
1309
1310 }
1311 /* Propagate register pressure to upper loop tree nodes: */
1312 if (loop_tree_node != ira_loop_tree_root)
1313 for (i = 0; i < ira_pressure_classes_num; i++)
1314 {
1315 enum reg_class pclass;
1316
1317 pclass = ira_pressure_classes[i];
1318 if (loop_tree_node->reg_pressure[pclass]
1319 > loop_tree_node->parent->reg_pressure[pclass])
1320 loop_tree_node->parent->reg_pressure[pclass]
1321 = loop_tree_node->reg_pressure[pclass];
1322 }
1323 }
1324
1325 /* Create and set up IRA_START_POINT_RANGES and
1326 IRA_FINISH_POINT_RANGES. */
1327 static void
create_start_finish_chains(void)1328 create_start_finish_chains (void)
1329 {
1330 ira_object_t obj;
1331 ira_object_iterator oi;
1332 live_range_t r;
1333
1334 ira_start_point_ranges
1335 = (live_range_t *) ira_allocate (ira_max_point * sizeof (live_range_t));
1336 memset (ira_start_point_ranges, 0, ira_max_point * sizeof (live_range_t));
1337 ira_finish_point_ranges
1338 = (live_range_t *) ira_allocate (ira_max_point * sizeof (live_range_t));
1339 memset (ira_finish_point_ranges, 0, ira_max_point * sizeof (live_range_t));
1340 FOR_EACH_OBJECT (obj, oi)
1341 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
1342 {
1343 r->start_next = ira_start_point_ranges[r->start];
1344 ira_start_point_ranges[r->start] = r;
1345 r->finish_next = ira_finish_point_ranges[r->finish];
1346 ira_finish_point_ranges[r->finish] = r;
1347 }
1348 }
1349
1350 /* Rebuild IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES after
1351 new live ranges and program points were added as a result if new
1352 insn generation. */
1353 void
ira_rebuild_start_finish_chains(void)1354 ira_rebuild_start_finish_chains (void)
1355 {
1356 ira_free (ira_finish_point_ranges);
1357 ira_free (ira_start_point_ranges);
1358 create_start_finish_chains ();
1359 }
1360
1361 /* Compress allocno live ranges by removing program points where
1362 nothing happens. */
1363 static void
remove_some_program_points_and_update_live_ranges(void)1364 remove_some_program_points_and_update_live_ranges (void)
1365 {
1366 unsigned i;
1367 int n;
1368 int *map;
1369 ira_object_t obj;
1370 ira_object_iterator oi;
1371 live_range_t r;
1372 sbitmap born_or_dead, born, dead;
1373 sbitmap_iterator sbi;
1374 bool born_p, dead_p, prev_born_p, prev_dead_p;
1375
1376 born = sbitmap_alloc (ira_max_point);
1377 dead = sbitmap_alloc (ira_max_point);
1378 sbitmap_zero (born);
1379 sbitmap_zero (dead);
1380 FOR_EACH_OBJECT (obj, oi)
1381 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
1382 {
1383 ira_assert (r->start <= r->finish);
1384 SET_BIT (born, r->start);
1385 SET_BIT (dead, r->finish);
1386 }
1387
1388 born_or_dead = sbitmap_alloc (ira_max_point);
1389 sbitmap_a_or_b (born_or_dead, born, dead);
1390 map = (int *) ira_allocate (sizeof (int) * ira_max_point);
1391 n = -1;
1392 prev_born_p = prev_dead_p = false;
1393 EXECUTE_IF_SET_IN_SBITMAP (born_or_dead, 0, i, sbi)
1394 {
1395 born_p = TEST_BIT (born, i);
1396 dead_p = TEST_BIT (dead, i);
1397 if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
1398 || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
1399 map[i] = n;
1400 else
1401 map[i] = ++n;
1402 prev_born_p = born_p;
1403 prev_dead_p = dead_p;
1404 }
1405 sbitmap_free (born_or_dead);
1406 sbitmap_free (born);
1407 sbitmap_free (dead);
1408 n++;
1409 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1410 fprintf (ira_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
1411 ira_max_point, n, 100 * n / ira_max_point);
1412 ira_max_point = n;
1413
1414 FOR_EACH_OBJECT (obj, oi)
1415 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
1416 {
1417 r->start = map[r->start];
1418 r->finish = map[r->finish];
1419 }
1420
1421 ira_free (map);
1422 }
1423
1424 /* Print live ranges R to file F. */
1425 void
ira_print_live_range_list(FILE * f,live_range_t r)1426 ira_print_live_range_list (FILE *f, live_range_t r)
1427 {
1428 for (; r != NULL; r = r->next)
1429 fprintf (f, " [%d..%d]", r->start, r->finish);
1430 fprintf (f, "\n");
1431 }
1432
1433 /* Print live ranges R to stderr. */
1434 void
ira_debug_live_range_list(live_range_t r)1435 ira_debug_live_range_list (live_range_t r)
1436 {
1437 ira_print_live_range_list (stderr, r);
1438 }
1439
1440 /* Print live ranges of object OBJ to file F. */
1441 static void
print_object_live_ranges(FILE * f,ira_object_t obj)1442 print_object_live_ranges (FILE *f, ira_object_t obj)
1443 {
1444 ira_print_live_range_list (f, OBJECT_LIVE_RANGES (obj));
1445 }
1446
1447 /* Print live ranges of allocno A to file F. */
1448 static void
print_allocno_live_ranges(FILE * f,ira_allocno_t a)1449 print_allocno_live_ranges (FILE *f, ira_allocno_t a)
1450 {
1451 int n = ALLOCNO_NUM_OBJECTS (a);
1452 int i;
1453
1454 for (i = 0; i < n; i++)
1455 {
1456 fprintf (f, " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1457 if (n > 1)
1458 fprintf (f, " [%d]", i);
1459 fprintf (f, "):");
1460 print_object_live_ranges (f, ALLOCNO_OBJECT (a, i));
1461 }
1462 }
1463
1464 /* Print live ranges of allocno A to stderr. */
1465 void
ira_debug_allocno_live_ranges(ira_allocno_t a)1466 ira_debug_allocno_live_ranges (ira_allocno_t a)
1467 {
1468 print_allocno_live_ranges (stderr, a);
1469 }
1470
1471 /* Print live ranges of all allocnos to file F. */
1472 static void
print_live_ranges(FILE * f)1473 print_live_ranges (FILE *f)
1474 {
1475 ira_allocno_t a;
1476 ira_allocno_iterator ai;
1477
1478 FOR_EACH_ALLOCNO (a, ai)
1479 print_allocno_live_ranges (f, a);
1480 }
1481
1482 /* Print live ranges of all allocnos to stderr. */
1483 void
ira_debug_live_ranges(void)1484 ira_debug_live_ranges (void)
1485 {
1486 print_live_ranges (stderr);
1487 }
1488
1489 /* The main entry function creates live ranges, set up
1490 CONFLICT_HARD_REGS and TOTAL_CONFLICT_HARD_REGS for objects, and
1491 calculate register pressure info. */
1492 void
ira_create_allocno_live_ranges(void)1493 ira_create_allocno_live_ranges (void)
1494 {
1495 objects_live = sparseset_alloc (ira_objects_num);
1496 allocnos_processed = sparseset_alloc (ira_allocnos_num);
1497 curr_point = 0;
1498 last_call_num = 0;
1499 allocno_saved_at_call
1500 = (int *) ira_allocate (ira_allocnos_num * sizeof (int));
1501 memset (allocno_saved_at_call, 0, ira_allocnos_num * sizeof (int));
1502 ira_traverse_loop_tree (true, ira_loop_tree_root, NULL,
1503 process_bb_node_lives);
1504 ira_max_point = curr_point;
1505 create_start_finish_chains ();
1506 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1507 print_live_ranges (ira_dump_file);
1508 /* Clean up. */
1509 ira_free (allocno_saved_at_call);
1510 sparseset_free (objects_live);
1511 sparseset_free (allocnos_processed);
1512 }
1513
1514 /* Compress allocno live ranges. */
1515 void
ira_compress_allocno_live_ranges(void)1516 ira_compress_allocno_live_ranges (void)
1517 {
1518 remove_some_program_points_and_update_live_ranges ();
1519 ira_rebuild_start_finish_chains ();
1520 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1521 {
1522 fprintf (ira_dump_file, "Ranges after the compression:\n");
1523 print_live_ranges (ira_dump_file);
1524 }
1525 }
1526
1527 /* Free arrays IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES. */
1528 void
ira_finish_allocno_live_ranges(void)1529 ira_finish_allocno_live_ranges (void)
1530 {
1531 ira_free (ira_finish_point_ranges);
1532 ira_free (ira_start_point_ranges);
1533 }
1534