1 /* Integrated Register Allocator entry point.
2 Contributed by Vladimir Makarov.
3 Copyright (C) 2006 Free Software Foundation, Inc.
5 This file is part of GCC.
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 2, or (at your option) any later
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
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
22 /* The integrated register allocator (IRA) is called integrated
23 because register coalescing and register live range splitting are
24 done on-the-fly during coloring. Register coalescing is done by
25 hard register preferencing during hard register assigning. The
26 live range splitting is a byproduct of the regional register
29 The regional allocation is top-down process. The first we do
30 allocation for all function then we improve it for loops then their
31 subloops and so on. To reduce register shuffling, the same
32 mechanism of hard register prefrencing is used. This approach
33 works as good as Callahan-Koblentz algorithm but it is simpler.
34 We use Chaitin-Briggs coloring for each loop (or function) with
35 optional biased coloring. If pseudo-registers got different
36 location on loop borders we rename them inside the loop and
37 generate pseudo-register move insns. Some optimizations (like
38 removing redundant stores, moving register shuffling to less
39 frequent points, and code duplication reducing) to minimize effect
40 of register shuffling is done
42 If we don't improve register allocation for loops we get classic
43 Chaitin-Briggs coloring (only instead of separate pass of
44 coalescing, we use hard register preferencing).
46 Optionally we implements Chow's priority coloring only for all
47 function. It is quite analogous to the current gcc global register
48 allocator only we use more sophisticated hard register
51 Literature is worth to read for better understanding the code:
53 o Preston Briggs, Keith D. Cooper, Linda Torczon. Improvements to
54 Graph Coloring Register Allocation.
56 o David Callahan, Brian Koblenz. Register allocation via
57 hierarchical graph coloring
59 o Keith Cooper, Anshuman Dasgupta, Jason Eckhardt. Revisiting Graph
60 Coloring Register Allocation: A Study of the Chaitin-Briggs and
61 Callahan-Koblenz Algorithms.
63 o Guei-Yuan Lueh, Thomas Gross, and Ali-Reza Adl-Tabatabai. Global
64 Register Allocation Based on Graph Fusion.
71 #include "coretypes.h"
80 #include "hard-reg-set.h"
81 #include "basic-block.h"
86 #include "tree-pass.h"
90 #include "integrate.h"
95 static void setup_inner_mode (void);
96 static void setup_reg_mode_hard_regset (void);
97 static void setup_class_subset_and_move_costs (void);
98 static void setup_class_hard_regs (void);
99 static void setup_available_class_regs (void);
100 static void setup_alloc_regs (int);
101 static void setup_reg_subclasses (void);
102 #ifdef IRA_COVER_CLASSES
103 static void setup_cover_classes (void);
104 static void setup_class_translate (void);
106 static void print_class_cover (FILE *);
107 static void find_reg_class_closure (void);
108 static void setup_reg_class_nregs (void);
109 static void setup_prohibited_class_mode_regs (void);
110 static void setup_eliminable_regset (void);
111 static void find_reg_equiv_invariant_const (void);
112 static void setup_reg_renumber (void);
113 static void calculate_allocation_cost (void);
114 #ifdef ENABLE_IRA_CHECKING
115 static void check_allocation (void);
117 static void fix_reg_equiv_init (void);
118 #ifdef ENABLE_IRA_CHECKING
119 static void print_redundant_copies (void);
121 static void setup_preferred_alternate_classes (void);
123 static bool gate_ira (void);
124 static unsigned int rest_of_handle_ira (void);
126 /* Dump file for IRA. */
129 /* The number of elements in the following array. */
130 int spilled_reg_stack_slots_num
;
132 /* The following array contains description of spilled registers stack
133 slots have been used in the current function so far. */
134 struct spilled_reg_stack_slot
*spilled_reg_stack_slots
;
136 /* The following variable values are correspondingly overall cost of
137 the allocation, cost of hard register usage for the pseudos, cost
138 of memory usage for the pseudos, cost of loads, stores and register
139 move insns generated for register live range splitting. */
141 int reg_cost
, mem_cost
;
142 int load_cost
, store_cost
, shuffle_cost
;
143 int move_loops_num
, additional_jumps_num
;
145 /* A mode whose value is immediately contained in given mode
147 unsigned char mode_inner_mode
[NUM_MACHINE_MODES
];
149 /* The following array is a map hard regs X modes -> number registers
150 for store value of given mode starting with given hard
152 HARD_REG_SET reg_mode_hard_regset
[FIRST_PSEUDO_REGISTER
] [NUM_MACHINE_MODES
];
154 /* The following two variables are array analog of macros
155 MEMORY_MOVE_COST and REGISTER_MOVE_COST. */
156 int memory_move_cost
[MAX_MACHINE_MODE
] [N_REG_CLASSES
] [2];
157 int register_move_cost
[MAX_MACHINE_MODE
] [N_REG_CLASSES
] [N_REG_CLASSES
];
159 /* Nonzero value of element of the following array means that the
160 1st class is a subset of the 2nd class. */
161 int class_subset_p
[N_REG_CLASSES
] [N_REG_CLASSES
];
163 /* Temporary hard reg set used for different calculation. */
164 static HARD_REG_SET temp_hard_regset
;
168 /* The function sets up mode_inner_mode array. */
170 setup_inner_mode (void)
173 enum machine_mode wider
;
175 for (i
= 0; i
< NUM_MACHINE_MODES
; i
++)
176 mode_inner_mode
[i
] = VOIDmode
;
177 for (i
= 0; i
< NUM_MACHINE_MODES
; i
++)
179 wider
= GET_MODE_WIDER_MODE (i
);
180 if (wider
!= VOIDmode
)
182 ira_assert (mode_inner_mode
[wider
] == VOIDmode
);
183 mode_inner_mode
[wider
] = i
;
190 /* The function sets up map REG_MODE_HARD_REGSET. */
192 setup_reg_mode_hard_regset (void)
194 int i
, m
, hard_regno
;
196 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
197 for (hard_regno
= 0; hard_regno
< FIRST_PSEUDO_REGISTER
; hard_regno
++)
199 CLEAR_HARD_REG_SET (reg_mode_hard_regset
[hard_regno
] [m
]);
200 for (i
= hard_regno_nregs
[hard_regno
] [m
] - 1; i
>= 0; i
--)
201 if (hard_regno
+ i
< FIRST_PSEUDO_REGISTER
)
202 SET_HARD_REG_BIT (reg_mode_hard_regset
[hard_regno
] [m
],
209 /* The function sets up MEMORY_MOVE_COST, REGISTER_MOVE_COST and
212 setup_class_subset_and_move_costs (void)
215 enum machine_mode mode
;
217 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
219 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
221 memory_move_cost
[mode
] [cl
] [0] = MEMORY_MOVE_COST (mode
, cl
, 0);
222 memory_move_cost
[mode
] [cl
] [1] = MEMORY_MOVE_COST (mode
, cl
, 1);
225 for (cl2
= (int) N_REG_CLASSES
- 1; cl2
>= 0; cl2
--)
227 if (cl
!= NO_REGS
&& cl2
!= NO_REGS
)
228 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
229 register_move_cost
[mode
] [cl
] [cl2
]
230 = REGISTER_MOVE_COST (mode
, cl
, cl2
);
231 GO_IF_HARD_REG_SUBSET (reg_class_contents
[cl
],
232 reg_class_contents
[cl2
],
234 class_subset_p
[cl
] [cl2
] = FALSE
;
238 class_subset_p
[cl
] [cl2
] = TRUE
;
245 /* Hard registers can not be used for the register allocator for all
246 functions of the current compile unit. */
247 static HARD_REG_SET no_unit_alloc_regs
;
249 /* Hard registers which can be used for the allocation of given
250 register class. The order is defined by the allocation order. */
251 short class_hard_regs
[N_REG_CLASSES
] [FIRST_PSEUDO_REGISTER
];
253 /* The size of the above array for given register class. */
254 int class_hard_regs_num
[N_REG_CLASSES
];
256 /* Index (in class_hard_regs) for given register class and hard
257 register (in general case a hard register can belong to several
258 register classes). */
259 short class_hard_reg_index
[N_REG_CLASSES
] [FIRST_PSEUDO_REGISTER
];
261 /* The function sets up the three arrays declared above. */
263 setup_class_hard_regs (void)
265 int cl
, i
, hard_regno
, n
;
266 HARD_REG_SET processed_hard_reg_set
;
268 ira_assert (SHRT_MAX
>= FIRST_PSEUDO_REGISTER
);
269 /* We could call ORDER_REGS_FOR_LOCAL_ALLOC here (it is usually
270 putting hard callee-used hard registers first). But our
271 heuristics work better. */
272 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
274 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
275 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
276 CLEAR_HARD_REG_SET (processed_hard_reg_set
);
277 for (n
= 0, i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
279 #ifdef REG_ALLOC_ORDER
280 hard_regno
= reg_alloc_order
[i
];
284 if (TEST_HARD_REG_BIT (processed_hard_reg_set
, hard_regno
))
286 SET_HARD_REG_BIT (processed_hard_reg_set
, hard_regno
);
287 if (! TEST_HARD_REG_BIT (temp_hard_regset
, hard_regno
))
288 class_hard_reg_index
[cl
] [hard_regno
] = -1;
291 class_hard_reg_index
[cl
] [hard_regno
] = n
;
292 class_hard_regs
[cl
] [n
++] = hard_regno
;
295 class_hard_regs_num
[cl
] = n
;
299 /* Number of class hard registers available for the register
300 allocation for given classes. */
301 int available_class_regs
[N_REG_CLASSES
];
303 /* Function setting up AVAILABLE_CLASS_REGS. */
305 setup_available_class_regs (void)
309 memset (available_class_regs
, 0, sizeof (available_class_regs
));
310 for (i
= 0; i
< N_REG_CLASSES
; i
++)
312 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[i
]);
313 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
314 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
315 if (TEST_HARD_REG_BIT (temp_hard_regset
, j
))
316 available_class_regs
[i
]++;
320 /* The function setting up different global variables defining hard
321 registers for the allocation. It depends on USE_HARD_FRAME_P whose
322 nonzero value means that we can use hard frame pointer for the
325 setup_alloc_regs (int use_hard_frame_p
)
327 COPY_HARD_REG_SET (no_unit_alloc_regs
, fixed_reg_set
);
328 if (! use_hard_frame_p
)
329 SET_HARD_REG_BIT (no_unit_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
330 setup_class_hard_regs ();
331 setup_available_class_regs ();
336 /* Define the following macro if allocation through malloc if
338 /*#define IRA_NO_OBSTACK*/
340 #ifndef IRA_NO_OBSTACK
341 /* Obstack used for storing all dynamic data (except bitmaps) of the
343 static struct obstack ira_obstack
;
346 /* Obstack used for storing all bitmaps of the IRA. */
347 static struct bitmap_obstack ira_bitmap_obstack
;
349 /* The function allocates memory of size LEN for IRA data. */
351 ira_allocate (size_t len
)
355 #ifndef IRA_NO_OBSTACK
356 res
= obstack_alloc (&ira_obstack
, len
);
363 /* The function free memory ADDR allocated for IRA data. */
365 ira_free (void *addr ATTRIBUTE_UNUSED
)
367 #ifndef IRA_NO_OBSTACK
375 /* The function allocates bitmap for IRA. */
377 ira_allocate_bitmap (void)
379 return BITMAP_ALLOC (&ira_bitmap_obstack
);
382 /* The function frees bitmap B allocated for IRA. */
384 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED
)
389 /* The function allocates regset for IRA. */
391 ira_allocate_regset (void)
393 return ALLOC_REG_SET (&ira_bitmap_obstack
);
396 /* The function frees regset R allocated for IRA. */
398 ira_free_regset (regset r ATTRIBUTE_UNUSED
)
405 /* The function returns nonzero if hard registers starting with
406 HARD_REGNO and containing value of MODE are not in set
409 hard_reg_not_in_set_p (int hard_regno
, enum machine_mode mode
,
410 HARD_REG_SET hard_regset
)
414 ira_assert (hard_regno
>= 0);
415 for (i
= hard_regno_nregs
[hard_regno
] [mode
] - 1; i
>= 0; i
--)
416 if (TEST_HARD_REG_BIT (hard_regset
, hard_regno
+ i
))
423 /* The function outputs information about allocation of all pseudos
426 print_disposition (FILE *f
)
432 fprintf (f
, "Disposition:");
433 max_regno
= max_reg_num ();
434 for (n
= 0, i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
435 for (p
= regno_pseudo_map
[i
]; p
!= NULL
; p
= PSEUDO_NEXT_REGNO_PSEUDO (p
))
440 fprintf (f
, " %4d:r%-4d", PSEUDO_NUM (p
), PSEUDO_REGNO (p
));
441 if ((bb
= PSEUDO_LOOP_TREE_NODE (p
)->bb
) != NULL
)
442 fprintf (f
, "b%-3d", bb
->index
);
444 fprintf (f
, "l%-3d", PSEUDO_LOOP_TREE_NODE (p
)->loop
->num
);
445 if (PSEUDO_HARD_REGNO (p
) >= 0)
446 fprintf (f
, " %3d", PSEUDO_HARD_REGNO (p
));
453 /* The function outputs information about allocation of all pseudos
456 debug_disposition (void)
458 print_disposition (stderr
);
463 /* For each reg class, table listing all the classes contained in it
464 (excluding the class itself. Fixed registers are excluded from the
466 static enum reg_class alloc_reg_class_subclasses
[N_REG_CLASSES
][N_REG_CLASSES
];
468 /* The function initializes the tables of subclasses of each reg
471 setup_reg_subclasses (void)
475 for (i
= 0; i
< N_REG_CLASSES
; i
++)
476 for (j
= 0; j
< N_REG_CLASSES
; j
++)
477 alloc_reg_class_subclasses
[i
] [j
] = LIM_REG_CLASSES
;
479 for (i
= 0; i
< N_REG_CLASSES
; i
++)
481 if (i
== (int) NO_REGS
)
484 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[i
]);
485 AND_COMPL_HARD_REG_SET (temp_hard_regset
, fixed_reg_set
);
486 GO_IF_HARD_REG_EQUAL (temp_hard_regset
, zero_hard_reg_set
, cont
);
491 for (j
= 0; j
< N_REG_CLASSES
; j
++)
496 GO_IF_HARD_REG_SUBSET (reg_class_contents
[i
],
497 reg_class_contents
[j
], subclass
);
500 p
= &alloc_reg_class_subclasses
[j
] [0];
501 while (*p
!= LIM_REG_CLASSES
) p
++;
502 *p
= (enum reg_class
) i
;
509 /* The value is size of the subsequent array. */
510 int reg_class_cover_size
;
512 /* The array containing cover classes whose hard registers are used
513 for the allocation -- see also comments for macro
514 IRA_COVER_CLASSES. */
515 enum reg_class reg_class_cover
[N_REG_CLASSES
];
518 #ifdef IRA_COVER_CLASSES
520 /* The function checks IRA_COVER_CLASSES and sets the two global
521 variables defined above. */
523 setup_cover_classes (void)
527 static enum reg_class classes
[] = IRA_COVER_CLASSES
;
529 reg_class_cover_size
= 0;
530 for (i
= 0; (cl
= classes
[i
]) != LIM_REG_CLASSES
; i
++)
532 for (j
= 0; j
< i
; j
++)
533 if (reg_classes_intersect_p (cl
, classes
[j
]))
535 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
536 AND_COMPL_HARD_REG_SET (temp_hard_regset
, fixed_reg_set
);
537 GO_IF_HARD_REG_EQUAL (temp_hard_regset
, zero_hard_reg_set
, cont
);
538 reg_class_cover
[reg_class_cover_size
++] = cl
;
545 /* Map of register classes to corresponding cover class containing the
546 given class. If given class is not a subset of a cover class, we
547 translate it into the cheapest cover class. */
548 enum reg_class class_translate
[N_REG_CLASSES
];
550 #ifdef IRA_COVER_CLASSES
552 /* The function sets up array CLASS_TRANSLATE. */
554 setup_class_translate (void)
556 enum reg_class cl
, cover_class
, best_class
, *cl_ptr
;
557 enum machine_mode mode
;
558 int i
, cost
, min_cost
, best_cost
;
560 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
561 class_translate
[cl
] = NO_REGS
;
562 for (i
= 0; i
< reg_class_cover_size
; i
++)
564 cover_class
= reg_class_cover
[i
];
565 for (cl_ptr
= &alloc_reg_class_subclasses
[cover_class
] [0];
566 (cl
= *cl_ptr
) != LIM_REG_CLASSES
;
569 if (class_translate
[cl
] == NO_REGS
)
570 class_translate
[cl
] = cover_class
;
571 #ifdef ENABLE_IRA_CHECKING
574 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
575 AND_COMPL_HARD_REG_SET (temp_hard_regset
, fixed_reg_set
);
576 GO_IF_HARD_REG_SUBSET (temp_hard_regset
, zero_hard_reg_set
, ok
);
583 class_translate
[cover_class
] = cover_class
;
585 /* For classes which are not fully covered by a cover class (in
586 other words covered by more one cover class), use the cheapest
588 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
590 if (cl
== NO_REGS
|| class_translate
[cl
] != NO_REGS
)
592 best_class
= NO_REGS
;
594 for (i
= 0; i
< reg_class_cover_size
; i
++)
596 cover_class
= reg_class_cover
[i
];
597 COPY_HARD_REG_SET (temp_hard_regset
,
598 reg_class_contents
[cover_class
]);
599 AND_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
600 GO_IF_HARD_REG_EQUAL (temp_hard_regset
, zero_hard_reg_set
,
603 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
605 cost
= (memory_move_cost
[mode
] [cl
] [0]
606 + memory_move_cost
[mode
] [cl
] [1]);
610 if (best_class
== NO_REGS
|| best_cost
> min_cost
)
612 best_class
= cover_class
;
613 best_cost
= min_cost
;
618 class_translate
[cl
] = best_class
;
623 /* The function outputs all cover classes and the translation map into
626 print_class_cover (FILE *f
)
628 static const char *const reg_class_names
[] = REG_CLASS_NAMES
;
631 fprintf (f
, "Class cover:\n");
632 for (i
= 0; i
< reg_class_cover_size
; i
++)
633 fprintf (f
, " %s", reg_class_names
[reg_class_cover
[i
]]);
634 fprintf (f
, "\nClass translation:\n");
635 for (i
= 0; i
< N_REG_CLASSES
; i
++)
636 fprintf (f
, " %s -> %s\n", reg_class_names
[i
],
637 reg_class_names
[class_translate
[i
]]);
640 /* The function outputs all cover classes and the translation map into
643 debug_class_cover (void)
645 print_class_cover (stderr
);
648 /* Function setting up different arrays concerning class subsets and
651 find_reg_class_closure (void)
653 setup_reg_subclasses ();
654 #ifdef IRA_COVER_CLASSES
655 setup_cover_classes ();
656 setup_class_translate ();
662 /* Map: register class x machine mode -> number of hard registers of
663 given class needed to store value of given mode. If the number is
664 different, the size will be negative. */
665 int reg_class_nregs
[N_REG_CLASSES
] [MAX_MACHINE_MODE
];
667 /* Maximal value of the previous array elements. */
670 /* Function forming REG_CLASS_NREGS map. */
672 setup_reg_class_nregs (void)
678 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
679 for (m
= 0; m
< MAX_MACHINE_MODE
; m
++)
681 reg_class_nregs
[cl
] [m
] = CLASS_MAX_NREGS (cl
, m
);
682 if (max_nregs
< reg_class_nregs
[cl
] [m
])
683 max_nregs
= reg_class_nregs
[cl
] [m
];
689 /* Array whose values are hard regset of hard registers of given
690 register class whose HARD_REGNO_MODE_OK values are zero. */
691 HARD_REG_SET prohibited_class_mode_regs
[N_REG_CLASSES
] [NUM_MACHINE_MODES
];
693 /* The function setting up PROHIBITED_CLASS_MODE_REGS. */
695 setup_prohibited_class_mode_regs (void)
697 int i
, j
, k
, hard_regno
;
700 for (i
= 0; i
< reg_class_cover_size
; i
++)
702 cl
= reg_class_cover
[i
];
703 for (j
= 0; j
< NUM_MACHINE_MODES
; j
++)
705 CLEAR_HARD_REG_SET (prohibited_class_mode_regs
[cl
] [j
]);
706 for (k
= class_hard_regs_num
[cl
] - 1; k
>= 0; k
--)
708 hard_regno
= class_hard_regs
[cl
] [k
];
709 if (! HARD_REGNO_MODE_OK (hard_regno
, j
))
710 SET_HARD_REG_BIT (prohibited_class_mode_regs
[cl
] [j
],
719 /* Hard regsets whose all bits are correspondingly zero or one. */
720 HARD_REG_SET zero_hard_reg_set
;
721 HARD_REG_SET one_hard_reg_set
;
723 /* Function called once during compiler work. It sets up different
724 arrays whose values don't depend on the compiled function. */
728 CLEAR_HARD_REG_SET (zero_hard_reg_set
);
729 SET_HARD_REG_SET (one_hard_reg_set
);
731 setup_reg_mode_hard_regset ();
732 setup_class_subset_and_move_costs ();
733 setup_alloc_regs (flag_omit_frame_pointer
!= 0);
734 find_reg_class_closure ();
735 setup_reg_class_nregs ();
736 setup_prohibited_class_mode_regs ();
737 init_ira_costs_once ();
742 /* Function specific hard registers excluded from the allocation. */
743 HARD_REG_SET no_alloc_regs
;
745 /* The function sets up ELIMINABLE_REGSET, NO_ALLOC_REGS, and
748 setup_eliminable_regset (void)
751 #ifdef ELIMINABLE_REGS
752 static const struct {const int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
755 = (! flag_omit_frame_pointer
756 || (current_function_calls_alloca
&& EXIT_IGNORE_STACK
)
757 || FRAME_POINTER_REQUIRED
);
759 COPY_HARD_REG_SET (no_alloc_regs
, no_unit_alloc_regs
);
760 CLEAR_HARD_REG_SET (eliminable_regset
);
761 /* Build the regset of all eliminable registers and show we can't
762 use those that we already know won't be eliminated. */
763 #ifdef ELIMINABLE_REGS
764 for (i
= 0; i
< (int) ARRAY_SIZE (eliminables
); i
++)
767 = (! CAN_ELIMINATE (eliminables
[i
].from
, eliminables
[i
].to
)
768 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& need_fp
));
770 if (! regs_asm_clobbered
[eliminables
[i
].from
])
772 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
775 SET_HARD_REG_BIT (no_alloc_regs
, eliminables
[i
].from
);
777 else if (cannot_elim
)
778 error ("%s cannot be used in asm here",
779 reg_names
[eliminables
[i
].from
]);
781 regs_ever_live
[eliminables
[i
].from
] = 1;
783 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
784 if (! regs_asm_clobbered
[HARD_FRAME_POINTER_REGNUM
])
786 SET_HARD_REG_BIT (eliminable_regset
, HARD_FRAME_POINTER_REGNUM
);
788 SET_HARD_REG_BIT (no_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
791 error ("%s cannot be used in asm here",
792 reg_names
[HARD_FRAME_POINTER_REGNUM
]);
794 regs_ever_live
[HARD_FRAME_POINTER_REGNUM
] = 1;
798 if (! regs_asm_clobbered
[FRAME_POINTER_REGNUM
])
800 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
802 SET_HARD_REG_BIT (no_alloc_regs
, FRAME_POINTER_REGNUM
);
805 error ("%s cannot be used in asm here", reg_names
[FRAME_POINTER_REGNUM
]);
807 regs_ever_live
[FRAME_POINTER_REGNUM
] = 1;
813 /* The element value is nonzero if the corresponding regno value is
815 int *reg_equiv_invariant_p
;
817 /* The element value is equiv constant or NULL_RTX. */
818 rtx
*reg_equiv_const
;
820 /* The function sets up the two array declaraed above. */
822 find_reg_equiv_invariant_const (void)
825 rtx list
, insn
, note
, constant
, x
;
827 for (i
= FIRST_PSEUDO_REGISTER
; i
< reg_equiv_init_size
; i
++)
831 for (list
= reg_equiv_init
[i
]; list
!= NULL_RTX
; list
= XEXP (list
, 1))
833 insn
= XEXP (list
, 0);
834 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
836 if (note
== NULL_RTX
)
841 if (! function_invariant_p (x
)
843 /* A function invariant is often CONSTANT_P but may
844 include a register. We promise to only pass CONSTANT_P
845 objects to LEGITIMATE_PIC_OPERAND_P. */
846 || (CONSTANT_P (x
) && LEGITIMATE_PIC_OPERAND_P (x
)))
848 /* It can happen that a REG_EQUIV note contains a MEM that
849 is not a legitimate memory operand. As later stages of
850 reload assume that all addresses found in the
851 reg_equiv_* arrays were originally legitimate, we
852 ignore such REG_EQUIV notes. */
853 if (memory_operand (x
, VOIDmode
))
855 else if (function_invariant_p (x
))
857 if (GET_CODE (x
) == PLUS
858 || x
== frame_pointer_rtx
|| x
== arg_pointer_rtx
)
865 reg_equiv_invariant_p
[i
] = invariant_p
;
866 reg_equiv_const
[i
] = constant
;
872 /* The function sets up REG_RENUMBER and CALLER_SAVE_NEEDED used by
873 reload from the allocation found by IRA. */
875 setup_reg_renumber (void)
880 for (i
= 0; i
< pseudos_num
; i
++)
883 if (PSEUDO_REGNO (p
) < 0)
886 hard_regno
= PSEUDO_HARD_REGNO (p
);
887 reg_renumber
[REGNO (PSEUDO_REG (p
))]
888 = (hard_regno
< 0 ? -1 : hard_regno
);
889 if (hard_regno
>= 0 && PSEUDO_CALLS_CROSSED_NUM (p
) != 0
890 && ! hard_reg_not_in_set_p (hard_regno
, PSEUDO_MODE (p
),
893 ira_assert (flag_caller_saves
);
894 caller_save_needed
= 1;
899 /* The function calculates cost of the found register allocation. */
901 calculate_allocation_cost (void)
903 int i
, hard_regno
, cost
;
906 overall_cost
= reg_cost
= mem_cost
= 0;
907 for (i
= 0; i
< pseudos_num
; i
++)
910 hard_regno
= PSEUDO_HARD_REGNO (p
) = reg_renumber
[PSEUDO_REGNO (p
)];
911 PSEUDO_ASSIGNED_P (p
) = TRUE
;
914 cost
= PSEUDO_MEMORY_COST (p
);
919 cost
= (PSEUDO_HARD_REG_COSTS (p
)
920 [class_hard_reg_index
921 [PSEUDO_COVER_CLASS (p
)] [hard_regno
]]);
924 overall_cost
+= cost
;
927 if (ira_dump_file
!= NULL
)
929 fprintf (ira_dump_file
,
930 "+++Costs: overall %d, reg %d, mem %d, ld %d, st %d, move %d\n",
931 overall_cost
, reg_cost
, mem_cost
,
932 load_cost
, store_cost
, shuffle_cost
);
933 fprintf (ira_dump_file
, "+++ move loops %d, new jumps %d\n",
934 move_loops_num
, additional_jumps_num
);
939 #ifdef ENABLE_IRA_CHECKING
940 /* The function checks correctness of the allocation. */
942 check_allocation (void)
944 pseudo_t p
, conflict_p
, *pseudo_vec
;
945 int i
, hard_regno
, conflict_hard_regno
, j
, nregs
, conflict_nregs
;
947 for (i
= 0; i
< pseudos_num
; i
++)
950 if (PSEUDO_REGNO (p
) < 0 || (hard_regno
= PSEUDO_HARD_REGNO (p
)) < 0)
952 nregs
= hard_regno_nregs
[hard_regno
] [PSEUDO_MODE (p
)];
953 pseudo_vec
= PSEUDO_CONFLICT_PSEUDO_VEC (p
);
954 for (j
= 0; (conflict_p
= pseudo_vec
[j
]) != NULL
; j
++)
955 if ((conflict_hard_regno
= PSEUDO_HARD_REGNO (conflict_p
)) >= 0)
959 [conflict_hard_regno
] [PSEUDO_MODE (conflict_p
)]);
960 if ((conflict_hard_regno
<= hard_regno
961 && hard_regno
< conflict_hard_regno
+ conflict_nregs
)
962 || (hard_regno
<= conflict_hard_regno
963 && conflict_hard_regno
< hard_regno
+ nregs
))
965 fprintf (stderr
, "bad allocation for %d and %d\n",
966 PSEUDO_REGNO (p
), PSEUDO_REGNO (conflict_p
));
974 /* The function fixes values of array REG_EQUIV_INIT after live range
975 splitting done by IRA. */
977 fix_reg_equiv_init (void)
979 int max_regno
= max_reg_num ();
981 rtx x
, prev
, next
, insn
, set
;
984 if (reg_equiv_init_size
< max_regno
)
986 reg_equiv_init
= ggc_realloc (reg_equiv_init
, max_regno
* sizeof (rtx
));
987 while (reg_equiv_init_size
< max_regno
)
988 reg_equiv_init
[reg_equiv_init_size
++] = NULL_RTX
;
989 for (i
= FIRST_PSEUDO_REGISTER
; i
< reg_equiv_init_size
; i
++)
990 for (prev
= NULL_RTX
, x
= reg_equiv_init
[i
]; x
!= NULL_RTX
; x
= next
)
994 set
= single_set (insn
);
995 ira_assert (set
!= NULL_RTX
996 && (REG_P (SET_DEST (set
)) || REG_P (SET_SRC (set
))));
997 if (REG_P (SET_DEST (set
))
998 && ((int) REGNO (SET_DEST (set
)) == i
999 || (int) ORIGINAL_REGNO (SET_DEST (set
)) == i
))
1000 new_regno
= REGNO (SET_DEST (set
));
1001 else if (REG_P (SET_SRC (set
))
1002 && ((int) REGNO (SET_SRC (set
)) == i
1003 || (int) ORIGINAL_REGNO (SET_SRC (set
)) == i
))
1004 new_regno
= REGNO (SET_SRC (set
));
1011 if (prev
== NULL_RTX
)
1012 reg_equiv_init
[i
] = next
;
1014 XEXP (prev
, 1) = next
;
1015 XEXP (x
, 1) = reg_equiv_init
[new_regno
];
1016 reg_equiv_init
[new_regno
] = x
;
1022 #ifdef ENABLE_IRA_CHECKING
1023 /* The function prints redundant memory memory copies. */
1025 print_redundant_copies (void)
1029 struct pseudo_copy
*cp
, *next_cp
;
1031 for (i
= 0; i
< pseudos_num
; i
++)
1034 if (PSEUDO_REGNO (p
) < 0)
1037 hard_regno
= PSEUDO_HARD_REGNO (p
);
1038 if (hard_regno
>= 0)
1040 for (cp
= PSEUDO_COPIES (p
); cp
!= NULL
; cp
= next_cp
)
1042 next_cp
= cp
->next_first_pseudo_copy
;
1045 next_cp
= cp
->next_second_pseudo_copy
;
1046 if (ira_dump_file
!= NULL
&& cp
->move_insn
!= NULL_RTX
1047 && PSEUDO_HARD_REGNO (cp
->first
) == hard_regno
)
1048 fprintf (ira_dump_file
, "move %d(freq %d):%d\n",
1049 INSN_UID (cp
->move_insn
), cp
->freq
, hard_regno
);
1055 /* Setup preferred and alternative classes for pseudo-registers for
1058 setup_preferred_alternate_classes (void)
1061 enum reg_class cover_class
;
1064 for (i
= 0; i
< pseudos_num
; i
++)
1067 cover_class
= PSEUDO_COVER_CLASS (p
);
1068 if (cover_class
== NO_REGS
)
1069 cover_class
= GENERAL_REGS
;
1070 setup_reg_classes (PSEUDO_REGNO (p
), cover_class
, NO_REGS
);
1076 /* This is the main entry of IRA. */
1080 int overall_cost_before
, loops_p
;
1087 rebuild_p
= update_equiv_regs ();
1089 #ifndef IRA_NO_OBSTACK
1090 gcc_obstack_init (&ira_obstack
);
1092 bitmap_obstack_initialize (&ira_bitmap_obstack
);
1094 reg_equiv_invariant_p
= ira_allocate (max_reg_num () * sizeof (int));
1095 memset (reg_equiv_invariant_p
, 0, max_reg_num () * sizeof (int));
1096 reg_equiv_const
= ira_allocate (max_reg_num () * sizeof (rtx
));
1097 memset (reg_equiv_const
, 0, max_reg_num () * sizeof (rtx
));
1098 find_reg_equiv_invariant_const ();
1101 rebuild_jump_labels (get_insns ());
1102 purge_all_dead_edges ();
1103 delete_unreachable_blocks ();
1105 setup_eliminable_regset ();
1107 overall_cost
= reg_cost
= mem_cost
= 0;
1108 load_cost
= store_cost
= shuffle_cost
= 0;
1109 move_loops_num
= additional_jumps_num
= 0;
1110 loops_p
= ira_build (flag_ira_algorithm
== IRA_ALGORITHM_REGIONAL
);
1115 max_regno
= max_reg_num ();
1117 /* Allocate the reg_renumber array. */
1118 allocate_reg_info (max_regno
, FALSE
, TRUE
);
1120 setup_reg_renumber ();
1125 /* Even if new registers are not created rebuild IRA internal
1126 representation to use correct regno pseudo map. */
1131 calculate_allocation_cost ();
1133 #ifdef ENABLE_IRA_CHECKING
1134 check_allocation ();
1137 max_regno
= max_reg_num ();
1138 delete_trivially_dead_insns (get_insns (), max_regno
);
1139 /* The allocator makes live register information inaccurate. */
1140 life_analysis (PROP_DEATH_NOTES
| PROP_LOG_LINKS
| PROP_REG_INFO
);
1141 max_regno
= max_reg_num ();
1143 /* Determine if the current function is a leaf before running IRA
1144 since this can impact optimizations done by the prologue and
1145 epilogue thus changing register elimination offsets. */
1146 current_function_is_leaf
= leaf_function_p ();
1148 /* Allocate the reg_renumber array. */
1149 allocate_reg_info (max_regno
, FALSE
, TRUE
);
1151 /* And the reg_equiv_memory_loc array. */
1152 VEC_safe_grow (rtx
, gc
, reg_equiv_memory_loc_vec
, max_regno
);
1153 memset (VEC_address (rtx
, reg_equiv_memory_loc_vec
), 0,
1154 sizeof (rtx
) * max_regno
);
1155 reg_equiv_memory_loc
= VEC_address (rtx
, reg_equiv_memory_loc_vec
);
1157 allocate_initial_values (reg_equiv_memory_loc
);
1159 fix_reg_equiv_init ();
1161 setup_preferred_alternate_classes ();
1163 #ifdef ENABLE_IRA_CHECKING
1164 print_redundant_copies ();
1167 overall_cost_before
= overall_cost
;
1169 spilled_reg_stack_slots_num
= 0;
1170 spilled_reg_stack_slots
1171 = ira_allocate (max_regno
* sizeof (struct spilled_reg_stack_slot
));
1173 build_insn_chain (get_insns ());
1174 reload_completed
= ! reload (get_insns (), 1);
1176 ira_free (spilled_reg_stack_slots
);
1178 if (ira_dump_file
!= NULL
&& overall_cost_before
!= overall_cost
)
1179 fprintf (ira_dump_file
, "+++Overall after reload %d\n", overall_cost
);
1183 cleanup_cfg (CLEANUP_EXPENSIVE
);
1185 ira_free (reg_equiv_invariant_p
);
1186 ira_free (reg_equiv_const
);
1188 bitmap_obstack_release (&ira_bitmap_obstack
);
1189 #ifndef IRA_NO_OBSTACK
1190 obstack_free (&ira_obstack
, NULL
);
1193 reload_completed
= 1;
1201 return flag_ira
!= 0;
1204 /* Run the integrated register allocator. */
1206 rest_of_handle_ira (void)
1212 struct tree_opt_pass pass_ira
=
1215 gate_ira
, /* gate */
1216 rest_of_handle_ira
, /* execute */
1219 0, /* static_pass_number */
1221 0, /* properties_required */
1222 0, /* properties_provided */
1223 0, /* properties_destroyed */
1224 0, /* todo_flags_start */
1226 TODO_ggc_collect
, /* todo_flags_finish */