Mercurial > hg > CbC > CbC_gcc

comparison gcc/ira-lives.c @ 0:a06113de4d67

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Fri, 17 Jul 2009 14:47:48 +0900
parents
children 58ad6c70ea60
comparison
equal deleted inserted replaced
-1:000000000000 0:a06113de4d67
1 /* IRA processing allocno lives to build allocno live ranges.
2 Copyright (C) 2006, 2007, 2008, 2009
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 "toplev.h"
37 #include "params.h"
38 #include "df.h"
39 #include "sparseset.h"
40 #include "ira-int.h"
41
42 /* The code in this file is similar to one in global but the code
43 works on the allocno basis and creates live ranges instead of
44 pseudo-register conflicts. */
45
46 /* Program points are enumerated by numbers from range
47 0..IRA_MAX_POINT-1. There are approximately two times more program
48 points than insns. Program points are places in the program where
49 liveness info can be changed. In most general case (there are more
50 complicated cases too) some program points correspond to places
51 where input operand dies and other ones correspond to places where
52 output operands are born. */
53 int ira_max_point;
54
55 /* Arrays of size IRA_MAX_POINT mapping a program point to the allocno
56 live ranges with given start/finish point. */
57 allocno_live_range_t *ira_start_point_ranges, *ira_finish_point_ranges;
58
59 /* Number of the current program point. */
60 static int curr_point;
61
62 /* Point where register pressure excess started or -1 if there is no
63 register pressure excess. Excess pressure for a register class at
64 some point means that there are more allocnos of given register
65 class living at the point than number of hard-registers of the
66 class available for the allocation. It is defined only for cover
67 classes. */
68 static int high_pressure_start_point[N_REG_CLASSES];
69
70 /* Allocnos live at current point in the scan. */
71 static sparseset allocnos_live;
72
73 /* Set of hard regs (except eliminable ones) currently live. */
74 static HARD_REG_SET hard_regs_live;
75
76 /* The loop tree node corresponding to the current basic block. */
77 static ira_loop_tree_node_t curr_bb_node;
78
79 /* The number of the last processed call. */
80 static int last_call_num;
81 /* The number of last call at which given allocno was saved. */
82 static int *allocno_saved_at_call;
83
84 /* The function processing birth of register REGNO. It updates living
85 hard regs and conflict hard regs for living allocnos or starts a
86 new live range for the allocno corresponding to REGNO if it is
87 necessary. */
88 static void
89 make_regno_born (int regno)
90 {
91 unsigned int i;
92 ira_allocno_t a;
93 allocno_live_range_t p;
94
95 if (regno < FIRST_PSEUDO_REGISTER)
96 {
97 SET_HARD_REG_BIT (hard_regs_live, regno);
98 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
99 {
100 SET_HARD_REG_BIT (ALLOCNO_CONFLICT_HARD_REGS (ira_allocnos[i]),
101 regno);
102 SET_HARD_REG_BIT (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (ira_allocnos[i]),
103 regno);
104 }
105 return;
106 }
107 a = ira_curr_regno_allocno_map[regno];
108 if (a == NULL)
109 return;
110 if ((p = ALLOCNO_LIVE_RANGES (a)) == NULL
111 || (p->finish != curr_point && p->finish + 1 != curr_point))
112 ALLOCNO_LIVE_RANGES (a)
113 = ira_create_allocno_live_range (a, curr_point, -1,
114 ALLOCNO_LIVE_RANGES (a));
115 }
116
117 /* Update ALLOCNO_EXCESS_PRESSURE_POINTS_NUM for allocno A. */
118 static void
119 update_allocno_pressure_excess_length (ira_allocno_t a)
120 {
121 int start, i;
122 enum reg_class cover_class, cl;
123 allocno_live_range_t p;
124
125 cover_class = ALLOCNO_COVER_CLASS (a);
126 for (i = 0;
127 (cl = ira_reg_class_super_classes[cover_class][i]) != LIM_REG_CLASSES;
128 i++)
129 {
130 if (high_pressure_start_point[cl] < 0)
131 continue;
132 p = ALLOCNO_LIVE_RANGES (a);
133 ira_assert (p != NULL);
134 start = (high_pressure_start_point[cl] > p->start
135 ? high_pressure_start_point[cl] : p->start);
136 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) += curr_point - start + 1;
137 }
138 }
139
140 /* Process the death of register REGNO. This updates hard_regs_live
141 or finishes the current live range for the allocno corresponding to
142 REGNO. */
143 static void
144 make_regno_dead (int regno)
145 {
146 ira_allocno_t a;
147 allocno_live_range_t p;
148
149 if (regno < FIRST_PSEUDO_REGISTER)
150 {
151 CLEAR_HARD_REG_BIT (hard_regs_live, regno);
152 return;
153 }
154 a = ira_curr_regno_allocno_map[regno];
155 if (a == NULL)
156 return;
157 p = ALLOCNO_LIVE_RANGES (a);
158 ira_assert (p != NULL);
159 p->finish = curr_point;
160 update_allocno_pressure_excess_length (a);
161 }
162
163 /* The current register pressures for each cover class for the current
164 basic block. */
165 static int curr_reg_pressure[N_REG_CLASSES];
166
167 /* Mark allocno A as currently living and update current register
168 pressure, maximal register pressure for the current BB, start point
169 of the register pressure excess, and conflicting hard registers of
170 A. */
171 static void
172 set_allocno_live (ira_allocno_t a)
173 {
174 int i;
175 enum reg_class cover_class, cl;
176
177 /* Invalidate because it is referenced. */
178 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
179 if (sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
180 return;
181 sparseset_set_bit (allocnos_live, ALLOCNO_NUM (a));
182 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a), hard_regs_live);
183 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), hard_regs_live);
184 cover_class = ALLOCNO_COVER_CLASS (a);
185 for (i = 0;
186 (cl = ira_reg_class_super_classes[cover_class][i]) != LIM_REG_CLASSES;
187 i++)
188 {
189 curr_reg_pressure[cl] += ira_reg_class_nregs[cl][ALLOCNO_MODE (a)];
190 if (high_pressure_start_point[cl] < 0
191 && (curr_reg_pressure[cl] > ira_available_class_regs[cl]))
192 high_pressure_start_point[cl] = curr_point;
193 if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl])
194 curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl];
195 }
196 }
197
198 /* Mark allocno A as currently not living and update current register
199 pressure, start point of the register pressure excess, and register
200 pressure excess length for living allocnos. */
201 static void
202 clear_allocno_live (ira_allocno_t a)
203 {
204 int i;
205 unsigned int j;
206 enum reg_class cover_class, cl;
207 bool set_p;
208
209 /* Invalidate because it is referenced. */
210 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
211 if (sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
212 {
213 cover_class = ALLOCNO_COVER_CLASS (a);
214 set_p = false;
215 for (i = 0;
216 (cl = ira_reg_class_super_classes[cover_class][i])
217 != LIM_REG_CLASSES;
218 i++)
219 {
220 curr_reg_pressure[cl] -= ira_reg_class_nregs[cl][ALLOCNO_MODE (a)];
221 ira_assert (curr_reg_pressure[cl] >= 0);
222 if (high_pressure_start_point[cl] >= 0
223 && curr_reg_pressure[cl] <= ira_available_class_regs[cl])
224 set_p = true;
225 }
226 if (set_p)
227 {
228 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, j)
229 update_allocno_pressure_excess_length (ira_allocnos[j]);
230 for (i = 0;
231 (cl = ira_reg_class_super_classes[cover_class][i])
232 != LIM_REG_CLASSES;
233 i++)
234 if (high_pressure_start_point[cl] >= 0
235 && curr_reg_pressure[cl] <= ira_available_class_regs[cl])
236 high_pressure_start_point[cl] = -1;
237
238 }
239 }
240 sparseset_clear_bit (allocnos_live, ALLOCNO_NUM (a));
241 }
242
243 /* Mark the register REG as live. Store a 1 in hard_regs_live or
244 allocnos_live for this register or the corresponding allocno,
245 record how many consecutive hardware registers it actually
246 needs. */
247 static void
248 mark_reg_live (rtx reg)
249 {
250 int i, regno;
251
252 gcc_assert (REG_P (reg));
253 regno = REGNO (reg);
254
255 if (regno >= FIRST_PSEUDO_REGISTER)
256 {
257 ira_allocno_t a = ira_curr_regno_allocno_map[regno];
258
259 if (a != NULL)
260 {
261 if (sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
262 {
263 /* Invalidate because it is referenced. */
264 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
265 return;
266 }
267 set_allocno_live (a);
268 }
269 make_regno_born (regno);
270 }
271 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
272 {
273 int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
274 enum reg_class cover_class, cl;
275
276 while (regno < last)
277 {
278 if (! TEST_HARD_REG_BIT (hard_regs_live, regno)
279 && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
280 {
281 cover_class = ira_hard_regno_cover_class[regno];
282 for (i = 0;
283 (cl = ira_reg_class_super_classes[cover_class][i])
284 != LIM_REG_CLASSES;
285 i++)
286 {
287 curr_reg_pressure[cl]++;
288 if (high_pressure_start_point[cl] < 0
289 && (curr_reg_pressure[cl]
290 > ira_available_class_regs[cl]))
291 high_pressure_start_point[cl] = curr_point;
292 }
293 make_regno_born (regno);
294 for (i = 0;
295 (cl = ira_reg_class_super_classes[cover_class][i])
296 != LIM_REG_CLASSES;
297 i++)
298 {
299 if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl])
300 curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl];
301 }
302 }
303 regno++;
304 }
305 }
306 }
307
308 /* Mark the register referenced by use or def REF as live. */
309 static void
310 mark_ref_live (df_ref ref)
311 {
312 rtx reg;
313
314 reg = DF_REF_REG (ref);
315 if (GET_CODE (reg) == SUBREG)
316 reg = SUBREG_REG (reg);
317 mark_reg_live (reg);
318 }
319
320 /* Mark the register REG as dead. Store a 0 in hard_regs_live or
321 allocnos_live for the register. */
322 static void
323 mark_reg_dead (rtx reg)
324 {
325 int regno;
326
327 gcc_assert (REG_P (reg));
328 regno = REGNO (reg);
329
330 if (regno >= FIRST_PSEUDO_REGISTER)
331 {
332 ira_allocno_t a = ira_curr_regno_allocno_map[regno];
333
334 if (a != NULL)
335 {
336 if (! sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)))
337 {
338 /* Invalidate because it is referenced. */
339 allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
340 return;
341 }
342 clear_allocno_live (a);
343 }
344 make_regno_dead (regno);
345 }
346 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno))
347 {
348 int i;
349 unsigned int j;
350 int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
351 enum reg_class cover_class, cl;
352 bool set_p;
353
354 while (regno < last)
355 {
356 if (TEST_HARD_REG_BIT (hard_regs_live, regno))
357 {
358 set_p = false;
359 cover_class = ira_hard_regno_cover_class[regno];
360 for (i = 0;
361 (cl = ira_reg_class_super_classes[cover_class][i])
362 != LIM_REG_CLASSES;
363 i++)
364 {
365 curr_reg_pressure[cl]--;
366 if (high_pressure_start_point[cl] >= 0
367 && curr_reg_pressure[cl] <= ira_available_class_regs[cl])
368 set_p = true;
369 ira_assert (curr_reg_pressure[cl] >= 0);
370 }
371 if (set_p)
372 {
373 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, j)
374 update_allocno_pressure_excess_length (ira_allocnos[j]);
375 for (i = 0;
376 (cl = ira_reg_class_super_classes[cover_class][i])
377 != LIM_REG_CLASSES;
378 i++)
379 if (high_pressure_start_point[cl] >= 0
380 && (curr_reg_pressure[cl]
381 <= ira_available_class_regs[cl]))
382 high_pressure_start_point[cl] = -1;
383 }
384 make_regno_dead (regno);
385 }
386 regno++;
387 }
388 }
389 }
390
391 /* Mark the register referenced by definition DEF as dead, if the
392 definition is a total one. */
393 static void
394 mark_ref_dead (df_ref def)
395 {
396 rtx reg;
397
398 if (DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL)
399 || DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL))
400 return;
401
402 reg = DF_REF_REG (def);
403 if (GET_CODE (reg) == SUBREG)
404 reg = SUBREG_REG (reg);
405 mark_reg_dead (reg);
406 }
407
408 /* Make pseudo REG conflicting with pseudo DREG, if the 1st pseudo
409 class is intersected with class CL. Advance the current program
410 point before making the conflict if ADVANCE_P. Return TRUE if we
411 will need to advance the current program point. */
412 static bool
413 make_pseudo_conflict (rtx reg, enum reg_class cl, rtx dreg, bool advance_p)
414 {
415 ira_allocno_t a;
416
417 if (GET_CODE (reg) == SUBREG)
418 reg = SUBREG_REG (reg);
419
420 if (! REG_P (reg) || REGNO (reg) < FIRST_PSEUDO_REGISTER)
421 return advance_p;
422
423 a = ira_curr_regno_allocno_map[REGNO (reg)];
424 if (! reg_classes_intersect_p (cl, ALLOCNO_COVER_CLASS (a)))
425 return advance_p;
426
427 if (advance_p)
428 curr_point++;
429
430 mark_reg_live (reg);
431 mark_reg_live (dreg);
432 mark_reg_dead (reg);
433 mark_reg_dead (dreg);
434
435 return false;
436 }
437
438 /* Check and make if necessary conflicts for pseudo DREG of class
439 DEF_CL of the current insn with input operand USE of class USE_CL.
440 Advance the current program point before making the conflict if
441 ADVANCE_P. Return TRUE if we will need to advance the current
442 program point. */
443 static bool
444 check_and_make_def_use_conflict (rtx dreg, enum reg_class def_cl,
445 int use, enum reg_class use_cl,
446 bool advance_p)
447 {
448 if (! reg_classes_intersect_p (def_cl, use_cl))
449 return advance_p;
450
451 advance_p = make_pseudo_conflict (recog_data.operand[use],
452 use_cl, dreg, advance_p);
453 /* Reload may end up swapping commutative operands, so you
454 have to take both orderings into account. The
455 constraints for the two operands can be completely
456 different. (Indeed, if the constraints for the two
457 operands are the same for all alternatives, there's no
458 point marking them as commutative.) */
459 if (use < recog_data.n_operands + 1
460 && recog_data.constraints[use][0] == '%')
461 advance_p
462 = make_pseudo_conflict (recog_data.operand[use + 1],
463 use_cl, dreg, advance_p);
464 if (use >= 1
465 && recog_data.constraints[use - 1][0] == '%')
466 advance_p
467 = make_pseudo_conflict (recog_data.operand[use - 1],
468 use_cl, dreg, advance_p);
469 return advance_p;
470 }
471
472 /* Check and make if necessary conflicts for definition DEF of class
473 DEF_CL of the current insn with input operands. Process only
474 constraints of alternative ALT. */
475 static void
476 check_and_make_def_conflict (int alt, int def, enum reg_class def_cl)
477 {
478 int use, use_match;
479 ira_allocno_t a;
480 enum reg_class use_cl, acl;
481 bool advance_p;
482 rtx dreg = recog_data.operand[def];
483
484 if (def_cl == NO_REGS)
485 return;
486
487 if (GET_CODE (dreg) == SUBREG)
488 dreg = SUBREG_REG (dreg);
489
490 if (! REG_P (dreg) || REGNO (dreg) < FIRST_PSEUDO_REGISTER)
491 return;
492
493 a = ira_curr_regno_allocno_map[REGNO (dreg)];
494 acl = ALLOCNO_COVER_CLASS (a);
495 if (! reg_classes_intersect_p (acl, def_cl))
496 return;
497
498 advance_p = true;
499
500 for (use = 0; use < recog_data.n_operands; use++)
501 {
502 if (use == def || recog_data.operand_type[use] == OP_OUT)
503 return;
504
505 if (recog_op_alt[use][alt].anything_ok)
506 use_cl = ALL_REGS;
507 else
508 use_cl = recog_op_alt[use][alt].cl;
509
510 advance_p = check_and_make_def_use_conflict (dreg, def_cl, use,
511 use_cl, advance_p);
512
513 if ((use_match = recog_op_alt[use][alt].matches) >= 0)
514 {
515 if (use_match == def)
516 return;
517
518 if (recog_op_alt[use_match][alt].anything_ok)
519 use_cl = ALL_REGS;
520 else
521 use_cl = recog_op_alt[use_match][alt].cl;
522 advance_p = check_and_make_def_use_conflict (dreg, def_cl, use,
523 use_cl, advance_p);
524 }
525 }
526 }
527
528 /* Make conflicts of early clobber pseudo registers of the current
529 insn with its inputs. Avoid introducing unnecessary conflicts by
530 checking classes of the constraints and pseudos because otherwise
531 significant code degradation is possible for some targets. */
532 static void
533 make_early_clobber_and_input_conflicts (void)
534 {
535 int alt;
536 int def, def_match;
537 enum reg_class def_cl;
538
539 for (alt = 0; alt < recog_data.n_alternatives; alt++)
540 for (def = 0; def < recog_data.n_operands; def++)
541 {
542 def_cl = NO_REGS;
543 if (recog_op_alt[def][alt].earlyclobber)
544 {
545 if (recog_op_alt[def][alt].anything_ok)
546 def_cl = ALL_REGS;
547 else
548 def_cl = recog_op_alt[def][alt].cl;
549 check_and_make_def_conflict (alt, def, def_cl);
550 }
551 if ((def_match = recog_op_alt[def][alt].matches) >= 0
552 && (recog_op_alt[def_match][alt].earlyclobber
553 || recog_op_alt[def][alt].earlyclobber))
554 {
555 if (recog_op_alt[def_match][alt].anything_ok)
556 def_cl = ALL_REGS;
557 else
558 def_cl = recog_op_alt[def_match][alt].cl;
559 check_and_make_def_conflict (alt, def, def_cl);
560 }
561 }
562 }
563
564 /* Mark early clobber hard registers of the current INSN as live (if
565 LIVE_P) or dead. Return true if there are such registers. */
566 static bool
567 mark_hard_reg_early_clobbers (rtx insn, bool live_p)
568 {
569 df_ref *def_rec;
570 bool set_p = false;
571
572 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
573 if (DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MUST_CLOBBER))
574 {
575 rtx dreg = DF_REF_REG (*def_rec);
576
577 if (GET_CODE (dreg) == SUBREG)
578 dreg = SUBREG_REG (dreg);
579 if (! REG_P (dreg) || REGNO (dreg) >= FIRST_PSEUDO_REGISTER)
580 continue;
581
582 /* Hard register clobbers are believed to be early clobber
583 because there is no way to say that non-operand hard
584 register clobbers are not early ones. */
585 if (live_p)
586 mark_ref_live (*def_rec);
587 else
588 mark_ref_dead (*def_rec);
589 set_p = true;
590 }
591
592 return set_p;
593 }
594
595 /* Checks that CONSTRAINTS permits to use only one hard register. If
596 it is so, the function returns the class of the hard register.
597 Otherwise it returns NO_REGS. */
598 static enum reg_class
599 single_reg_class (const char *constraints, rtx op, rtx equiv_const)
600 {
601 int ignore_p;
602 enum reg_class cl, next_cl;
603 int c;
604
605 cl = NO_REGS;
606 for (ignore_p = false;
607 (c = *constraints);
608 constraints += CONSTRAINT_LEN (c, constraints))
609 if (c == '#')
610 ignore_p = true;
611 else if (c == ',')
612 ignore_p = false;
613 else if (! ignore_p)
614 switch (c)
615 {
616 case ' ':
617 case '\t':
618 case '=':
619 case '+':
620 case '*':
621 case '&':
622 case '%':
623 case '!':
624 case '?':
625 break;
626 case 'i':
627 if (CONSTANT_P (op)
628 || (equiv_const != NULL_RTX && CONSTANT_P (equiv_const)))
629 return NO_REGS;
630 break;
631
632 case 'n':
633 if (GET_CODE (op) == CONST_INT
634 || (GET_CODE (op) == CONST_DOUBLE && GET_MODE (op) == VOIDmode)
635 || (equiv_const != NULL_RTX
636 && (GET_CODE (equiv_const) == CONST_INT
637 || (GET_CODE (equiv_const) == CONST_DOUBLE
638 && GET_MODE (equiv_const) == VOIDmode))))
639 return NO_REGS;
640 break;
641
642 case 's':
643 if ((CONSTANT_P (op) && GET_CODE (op) != CONST_INT
644 && (GET_CODE (op) != CONST_DOUBLE || GET_MODE (op) != VOIDmode))
645 || (equiv_const != NULL_RTX
646 && CONSTANT_P (equiv_const)
647 && GET_CODE (equiv_const) != CONST_INT
648 && (GET_CODE (equiv_const) != CONST_DOUBLE
649 || GET_MODE (equiv_const) != VOIDmode)))
650 return NO_REGS;
651 break;
652
653 case 'I':
654 case 'J':
655 case 'K':
656 case 'L':
657 case 'M':
658 case 'N':
659 case 'O':
660 case 'P':
661 if ((GET_CODE (op) == CONST_INT
662 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op), c, constraints))
663 || (equiv_const != NULL_RTX
664 && GET_CODE (equiv_const) == CONST_INT
665 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (equiv_const),
666 c, constraints)))
667 return NO_REGS;
668 break;
669
670 case 'E':
671 case 'F':
672 if (GET_CODE (op) == CONST_DOUBLE
673 || (GET_CODE (op) == CONST_VECTOR
674 && GET_MODE_CLASS (GET_MODE (op)) == MODE_VECTOR_FLOAT)
675 || (equiv_const != NULL_RTX
676 && (GET_CODE (equiv_const) == CONST_DOUBLE
677 || (GET_CODE (equiv_const) == CONST_VECTOR
678 && (GET_MODE_CLASS (GET_MODE (equiv_const))
679 == MODE_VECTOR_FLOAT)))))
680 return NO_REGS;
681 break;
682
683 case 'G':
684 case 'H':
685 if ((GET_CODE (op) == CONST_DOUBLE
686 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op, c, constraints))
687 || (equiv_const != NULL_RTX
688 && GET_CODE (equiv_const) == CONST_DOUBLE
689 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (equiv_const,
690 c, constraints)))
691 return NO_REGS;
692 /* ??? what about memory */
693 case 'r':
694 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
695 case 'h': case 'j': case 'k': case 'l':
696 case 'q': case 't': case 'u':
697 case 'v': case 'w': case 'x': case 'y': case 'z':
698 case 'A': case 'B': case 'C': case 'D':
699 case 'Q': case 'R': case 'S': case 'T': case 'U':
700 case 'W': case 'Y': case 'Z':
701 next_cl = (c == 'r'
702 ? GENERAL_REGS
703 : REG_CLASS_FROM_CONSTRAINT (c, constraints));
704 if ((cl != NO_REGS && next_cl != cl)
705 || ira_available_class_regs[next_cl] > 1)
706 return NO_REGS;
707 cl = next_cl;
708 break;
709
710 case '0': case '1': case '2': case '3': case '4':
711 case '5': case '6': case '7': case '8': case '9':
712 next_cl
713 = single_reg_class (recog_data.constraints[c - '0'],
714 recog_data.operand[c - '0'], NULL_RTX);
715 if ((cl != NO_REGS && next_cl != cl) || next_cl == NO_REGS
716 || ira_available_class_regs[next_cl] > 1)
717 return NO_REGS;
718 cl = next_cl;
719 break;
720
721 default:
722 return NO_REGS;
723 }
724 return cl;
725 }
726
727 /* The function checks that operand OP_NUM of the current insn can use
728 only one hard register. If it is so, the function returns the
729 class of the hard register. Otherwise it returns NO_REGS. */
730 static enum reg_class
731 single_reg_operand_class (int op_num)
732 {
733 if (op_num < 0 || recog_data.n_alternatives == 0)
734 return NO_REGS;
735 return single_reg_class (recog_data.constraints[op_num],
736 recog_data.operand[op_num], NULL_RTX);
737 }
738
739 /* Processes input operands, if IN_P, or output operands otherwise of
740 the current insn with FREQ to find allocno which can use only one
741 hard register and makes other currently living allocnos conflicting
742 with the hard register. */
743 static void
744 process_single_reg_class_operands (bool in_p, int freq)
745 {
746 int i, regno, cost;
747 unsigned int px;
748 enum reg_class cl, cover_class;
749 rtx operand;
750 ira_allocno_t operand_a, a;
751
752 for (i = 0; i < recog_data.n_operands; i++)
753 {
754 operand = recog_data.operand[i];
755 if (in_p && recog_data.operand_type[i] != OP_IN
756 && recog_data.operand_type[i] != OP_INOUT)
757 continue;
758 if (! in_p && recog_data.operand_type[i] != OP_OUT
759 && recog_data.operand_type[i] != OP_INOUT)
760 continue;
761 cl = single_reg_operand_class (i);
762 if (cl == NO_REGS)
763 continue;
764
765 operand_a = NULL;
766
767 if (GET_CODE (operand) == SUBREG)
768 operand = SUBREG_REG (operand);
769
770 if (REG_P (operand)
771 && (regno = REGNO (operand)) >= FIRST_PSEUDO_REGISTER)
772 {
773 enum machine_mode mode;
774 enum reg_class cover_class;
775
776 operand_a = ira_curr_regno_allocno_map[regno];
777 mode = ALLOCNO_MODE (operand_a);
778 cover_class = ALLOCNO_COVER_CLASS (operand_a);
779 if (ira_class_subset_p[cl][cover_class]
780 && ira_class_hard_regs_num[cl] != 0
781 && (ira_class_hard_reg_index[cover_class]
782 [ira_class_hard_regs[cl][0]]) >= 0
783 && reg_class_size[cl] <= (unsigned) CLASS_MAX_NREGS (cl, mode))
784 {
785 /* ??? FREQ */
786 cost = freq * (in_p
787 ? ira_register_move_cost[mode][cover_class][cl]
788 : ira_register_move_cost[mode][cl][cover_class]);
789 ira_allocate_and_set_costs
790 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a), cover_class, 0);
791 ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a)
792 [ira_class_hard_reg_index
793 [cover_class][ira_class_hard_regs[cl][0]]]
794 -= cost;
795 }
796 }
797
798 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, px)
799 {
800 a = ira_allocnos[px];
801 cover_class = ALLOCNO_COVER_CLASS (a);
802 if (a != operand_a)
803 {
804 /* We could increase costs of A instead of making it
805 conflicting with the hard register. But it works worse
806 because it will be spilled in reload in anyway. */
807 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
808 reg_class_contents[cl]);
809 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
810 reg_class_contents[cl]);
811 }
812 }
813 }
814 }
815
816 /* Process insns of the basic block given by its LOOP_TREE_NODE to
817 update allocno live ranges, allocno hard register conflicts,
818 intersected calls, and register pressure info for allocnos for the
819 basic block for and regions containing the basic block. */
820 static void
821 process_bb_node_lives (ira_loop_tree_node_t loop_tree_node)
822 {
823 int i, freq;
824 unsigned int j;
825 basic_block bb;
826 rtx insn;
827 bitmap_iterator bi;
828 bitmap reg_live_out;
829 unsigned int px;
830 bool set_p;
831
832 bb = loop_tree_node->bb;
833 if (bb != NULL)
834 {
835 for (i = 0; i < ira_reg_class_cover_size; i++)
836 {
837 curr_reg_pressure[ira_reg_class_cover[i]] = 0;
838 high_pressure_start_point[ira_reg_class_cover[i]] = -1;
839 }
840 curr_bb_node = loop_tree_node;
841 reg_live_out = DF_LR_OUT (bb);
842 sparseset_clear (allocnos_live);
843 REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
844 AND_COMPL_HARD_REG_SET (hard_regs_live, eliminable_regset);
845 AND_COMPL_HARD_REG_SET (hard_regs_live, ira_no_alloc_regs);
846 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
847 if (TEST_HARD_REG_BIT (hard_regs_live, i))
848 {
849 enum reg_class cover_class, cl;
850
851 cover_class = ira_class_translate[REGNO_REG_CLASS (i)];
852 for (j = 0;
853 (cl = ira_reg_class_super_classes[cover_class][j])
854 != LIM_REG_CLASSES;
855 j++)
856 {
857 curr_reg_pressure[cl]++;
858 if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl])
859 curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl];
860 ira_assert (curr_reg_pressure[cl]
861 <= ira_available_class_regs[cl]);
862 }
863 }
864 EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
865 {
866 ira_allocno_t a = ira_curr_regno_allocno_map[j];
867
868 if (a == NULL)
869 continue;
870 ira_assert (! sparseset_bit_p (allocnos_live, ALLOCNO_NUM (a)));
871 set_allocno_live (a);
872 make_regno_born (j);
873 }
874
875 freq = REG_FREQ_FROM_BB (bb);
876 if (freq == 0)
877 freq = 1;
878
879 /* Invalidate all allocno_saved_at_call entries. */
880 last_call_num++;
881
882 /* Scan the code of this basic block, noting which allocnos and
883 hard regs are born or die.
884
885 Note that this loop treats uninitialized values as live until
886 the beginning of the block. For example, if an instruction
887 uses (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever
888 set, FOO will remain live until the beginning of the block.
889 Likewise if FOO is not set at all. This is unnecessarily
890 pessimistic, but it probably doesn't matter much in practice. */
891 FOR_BB_INSNS_REVERSE (bb, insn)
892 {
893 df_ref *def_rec, *use_rec;
894 bool call_p;
895
896 if (! INSN_P (insn))
897 continue;
898
899 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
900 fprintf (ira_dump_file, " Insn %u(l%d): point = %d\n",
901 INSN_UID (insn), loop_tree_node->parent->loop->num,
902 curr_point);
903
904 /* Mark each defined value as live. We need to do this for
905 unused values because they still conflict with quantities
906 that are live at the time of the definition.
907
908 Ignore DF_REF_MAY_CLOBBERs on a call instruction. Such
909 references represent the effect of the called function
910 on a call-clobbered register. Marking the register as
911 live would stop us from allocating it to a call-crossing
912 allocno. */
913 call_p = CALL_P (insn);
914 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
915 if (!call_p || !DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MAY_CLOBBER))
916 mark_ref_live (*def_rec);
917
918 /* If INSN has multiple outputs, then any value used in one
919 of the outputs conflicts with the other outputs. Model this
920 by making the used value live during the output phase.
921
922 It is unsafe to use !single_set here since it will ignore
923 an unused output. Just because an output is unused does
924 not mean the compiler can assume the side effect will not
925 occur. Consider if ALLOCNO appears in the address of an
926 output and we reload the output. If we allocate ALLOCNO
927 to the same hard register as an unused output we could
928 set the hard register before the output reload insn. */
929 if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
930 for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
931 {
932 int i;
933 rtx reg;
934
935 reg = DF_REF_REG (*use_rec);
936 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
937 {
938 rtx set;
939
940 set = XVECEXP (PATTERN (insn), 0, i);
941 if (GET_CODE (set) == SET
942 && reg_overlap_mentioned_p (reg, SET_DEST (set)))
943 {
944 /* After the previous loop, this is a no-op if
945 REG is contained within SET_DEST (SET). */
946 mark_ref_live (*use_rec);
947 break;
948 }
949 }
950 }
951
952 extract_insn (insn);
953 preprocess_constraints ();
954 process_single_reg_class_operands (false, freq);
955
956 /* See which defined values die here. */
957 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
958 if (!call_p || !DF_REF_FLAGS_IS_SET (*def_rec, DF_REF_MAY_CLOBBER))
959 mark_ref_dead (*def_rec);
960
961 if (call_p)
962 {
963 last_call_num++;
964 /* The current set of live allocnos are live across the call. */
965 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
966 {
967 ira_allocno_t a = ira_allocnos[i];
968
969 if (allocno_saved_at_call[i] != last_call_num)
970 /* Here we are mimicking caller-save.c behaviour
971 which does not save hard register at a call if
972 it was saved on previous call in the same basic
973 block and the hard register was not mentioned
974 between the two calls. */
975 ALLOCNO_CALL_FREQ (a) += freq;
976 /* Mark it as saved at the next call. */
977 allocno_saved_at_call[i] = last_call_num + 1;
978 ALLOCNO_CALLS_CROSSED_NUM (a)++;
979 /* Don't allocate allocnos that cross setjmps or any
980 call, if this function receives a nonlocal
981 goto. */
982 if (cfun->has_nonlocal_label
983 || find_reg_note (insn, REG_SETJMP,
984 NULL_RTX) != NULL_RTX)
985 {
986 SET_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a));
987 SET_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
988 }
989 if (can_throw_internal (insn))
990 {
991 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
992 call_used_reg_set);
993 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
994 call_used_reg_set);
995 }
996 }
997 }
998
999 make_early_clobber_and_input_conflicts ();
1000
1001 curr_point++;
1002
1003 /* Mark each used value as live. */
1004 for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
1005 mark_ref_live (*use_rec);
1006
1007 process_single_reg_class_operands (true, freq);
1008
1009 set_p = mark_hard_reg_early_clobbers (insn, true);
1010
1011 if (set_p)
1012 {
1013 mark_hard_reg_early_clobbers (insn, false);
1014
1015 /* Mark each hard reg as live again. For example, a
1016 hard register can be in clobber and in an insn
1017 input. */
1018 for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
1019 {
1020 rtx ureg = DF_REF_REG (*use_rec);
1021
1022 if (GET_CODE (ureg) == SUBREG)
1023 ureg = SUBREG_REG (ureg);
1024 if (! REG_P (ureg) || REGNO (ureg) >= FIRST_PSEUDO_REGISTER)
1025 continue;
1026
1027 mark_ref_live (*use_rec);
1028 }
1029 }
1030
1031 curr_point++;
1032 }
1033
1034 #ifdef EH_RETURN_DATA_REGNO
1035 if (bb_has_eh_pred (bb))
1036 for (j = 0; ; ++j)
1037 {
1038 unsigned int regno = EH_RETURN_DATA_REGNO (j);
1039 if (regno == INVALID_REGNUM)
1040 break;
1041 make_regno_born (regno);
1042 }
1043 #endif
1044
1045 /* Allocnos can't go in stack regs at the start of a basic block
1046 that is reached by an abnormal edge. Likewise for call
1047 clobbered regs, because caller-save, fixup_abnormal_edges and
1048 possibly the table driven EH machinery are not quite ready to
1049 handle such allocnos live across such edges. */
1050 if (bb_has_abnormal_pred (bb))
1051 {
1052 #ifdef STACK_REGS
1053 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, px)
1054 {
1055 ALLOCNO_NO_STACK_REG_P (ira_allocnos[px]) = true;
1056 ALLOCNO_TOTAL_NO_STACK_REG_P (ira_allocnos[px]) = true;
1057 }
1058 for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
1059 make_regno_born (px);
1060 #endif
1061 /* No need to record conflicts for call clobbered regs if we
1062 have nonlocal labels around, as we don't ever try to
1063 allocate such regs in this case. */
1064 if (!cfun->has_nonlocal_label)
1065 for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
1066 if (call_used_regs[px])
1067 make_regno_born (px);
1068 }
1069
1070 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, i)
1071 {
1072 make_regno_dead (ALLOCNO_REGNO (ira_allocnos[i]));
1073 }
1074
1075 curr_point++;
1076
1077 }
1078 /* Propagate register pressure to upper loop tree nodes: */
1079 if (loop_tree_node != ira_loop_tree_root)
1080 for (i = 0; i < ira_reg_class_cover_size; i++)
1081 {
1082 enum reg_class cover_class;
1083
1084 cover_class = ira_reg_class_cover[i];
1085 if (loop_tree_node->reg_pressure[cover_class]
1086 > loop_tree_node->parent->reg_pressure[cover_class])
1087 loop_tree_node->parent->reg_pressure[cover_class]
1088 = loop_tree_node->reg_pressure[cover_class];
1089 }
1090 }
1091
1092 /* Create and set up IRA_START_POINT_RANGES and
1093 IRA_FINISH_POINT_RANGES. */
1094 static void
1095 create_start_finish_chains (void)
1096 {
1097 ira_allocno_t a;
1098 ira_allocno_iterator ai;
1099 allocno_live_range_t r;
1100
1101 ira_start_point_ranges
1102 = (allocno_live_range_t *) ira_allocate (ira_max_point
1103 * sizeof (allocno_live_range_t));
1104 memset (ira_start_point_ranges, 0,
1105 ira_max_point * sizeof (allocno_live_range_t));
1106 ira_finish_point_ranges
1107 = (allocno_live_range_t *) ira_allocate (ira_max_point
1108 * sizeof (allocno_live_range_t));
1109 memset (ira_finish_point_ranges, 0,
1110 ira_max_point * sizeof (allocno_live_range_t));
1111 FOR_EACH_ALLOCNO (a, ai)
1112 {
1113 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
1114 {
1115 r->start_next = ira_start_point_ranges[r->start];
1116 ira_start_point_ranges[r->start] = r;
1117 r->finish_next = ira_finish_point_ranges[r->finish];
1118 ira_finish_point_ranges[r->finish] = r;
1119 }
1120 }
1121 }
1122
1123 /* Rebuild IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES after
1124 new live ranges and program points were added as a result if new
1125 insn generation. */
1126 void
1127 ira_rebuild_start_finish_chains (void)
1128 {
1129 ira_free (ira_finish_point_ranges);
1130 ira_free (ira_start_point_ranges);
1131 create_start_finish_chains ();
1132 }
1133
1134 /* Compress allocno live ranges by removing program points where
1135 nothing happens. */
1136 static void
1137 remove_some_program_points_and_update_live_ranges (void)
1138 {
1139 unsigned i;
1140 int n;
1141 int *map;
1142 ira_allocno_t a;
1143 ira_allocno_iterator ai;
1144 allocno_live_range_t r;
1145 bitmap born_or_died;
1146 bitmap_iterator bi;
1147
1148 born_or_died = ira_allocate_bitmap ();
1149 FOR_EACH_ALLOCNO (a, ai)
1150 {
1151 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
1152 {
1153 ira_assert (r->start <= r->finish);
1154 bitmap_set_bit (born_or_died, r->start);
1155 bitmap_set_bit (born_or_died, r->finish);
1156 }
1157 }
1158 map = (int *) ira_allocate (sizeof (int) * ira_max_point);
1159 n = 0;
1160 EXECUTE_IF_SET_IN_BITMAP(born_or_died, 0, i, bi)
1161 {
1162 map[i] = n++;
1163 }
1164 ira_free_bitmap (born_or_died);
1165 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1166 fprintf (ira_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
1167 ira_max_point, n, 100 * n / ira_max_point);
1168 ira_max_point = n;
1169 FOR_EACH_ALLOCNO (a, ai)
1170 {
1171 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
1172 {
1173 r->start = map[r->start];
1174 r->finish = map[r->finish];
1175 }
1176 }
1177 ira_free (map);
1178 }
1179
1180 /* Print live ranges R to file F. */
1181 void
1182 ira_print_live_range_list (FILE *f, allocno_live_range_t r)
1183 {
1184 for (; r != NULL; r = r->next)
1185 fprintf (f, " [%d..%d]", r->start, r->finish);
1186 fprintf (f, "\n");
1187 }
1188
1189 /* Print live ranges R to stderr. */
1190 void
1191 ira_debug_live_range_list (allocno_live_range_t r)
1192 {
1193 ira_print_live_range_list (stderr, r);
1194 }
1195
1196 /* Print live ranges of allocno A to file F. */
1197 static void
1198 print_allocno_live_ranges (FILE *f, ira_allocno_t a)
1199 {
1200 fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1201 ira_print_live_range_list (f, ALLOCNO_LIVE_RANGES (a));
1202 }
1203
1204 /* Print live ranges of allocno A to stderr. */
1205 void
1206 ira_debug_allocno_live_ranges (ira_allocno_t a)
1207 {
1208 print_allocno_live_ranges (stderr, a);
1209 }
1210
1211 /* Print live ranges of all allocnos to file F. */
1212 static void
1213 print_live_ranges (FILE *f)
1214 {
1215 ira_allocno_t a;
1216 ira_allocno_iterator ai;
1217
1218 FOR_EACH_ALLOCNO (a, ai)
1219 print_allocno_live_ranges (f, a);
1220 }
1221
1222 /* Print live ranges of all allocnos to stderr. */
1223 void
1224 ira_debug_live_ranges (void)
1225 {
1226 print_live_ranges (stderr);
1227 }
1228
1229 /* The main entry function creates live ranges, set up
1230 CONFLICT_HARD_REGS and TOTAL_CONFLICT_HARD_REGS for allocnos, and
1231 calculate register pressure info. */
1232 void
1233 ira_create_allocno_live_ranges (void)
1234 {
1235 allocnos_live = sparseset_alloc (ira_allocnos_num);
1236 curr_point = 0;
1237 last_call_num = 0;
1238 allocno_saved_at_call
1239 = (int *) ira_allocate (ira_allocnos_num * sizeof (int));
1240 memset (allocno_saved_at_call, 0, ira_allocnos_num * sizeof (int));
1241 ira_traverse_loop_tree (true, ira_loop_tree_root, NULL,
1242 process_bb_node_lives);
1243 ira_max_point = curr_point;
1244 create_start_finish_chains ();
1245 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1246 print_live_ranges (ira_dump_file);
1247 /* Clean up. */
1248 ira_free (allocno_saved_at_call);
1249 sparseset_free (allocnos_live);
1250 }
1251
1252 /* Compress allocno live ranges. */
1253 void
1254 ira_compress_allocno_live_ranges (void)
1255 {
1256 remove_some_program_points_and_update_live_ranges ();
1257 ira_rebuild_start_finish_chains ();
1258 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1259 {
1260 fprintf (ira_dump_file, "Ranges after the compression:\n");
1261 print_live_ranges (ira_dump_file);
1262 }
1263 }
1264
1265 /* Free arrays IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES. */
1266 void
1267 ira_finish_allocno_live_ranges (void)
1268 {
1269 ira_free (ira_finish_point_ranges);
1270 ira_free (ira_start_point_ranges);
1271 }