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