1 /* Integrated Register Allocator (IRA) entry point.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
6 This file is part of GCC.
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
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
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/>. */
22 /* The integrated register allocator (IRA) is a
23 regional register allocator performing graph coloring on a top-down
24 traversal of nested regions. Graph coloring in a region is based
25 on Chaitin-Briggs algorithm. It is called integrated because
26 register coalescing, register live range splitting, and choosing a
27 better hard register are done on-the-fly during coloring. Register
28 coalescing and choosing a cheaper hard register is done by hard
29 register preferencing during hard register assigning. The live
30 range splitting is a byproduct of the regional register allocation.
32 Major IRA notions are:
34 o *Region* is a part of CFG where graph coloring based on
35 Chaitin-Briggs algorithm is done. IRA can work on any set of
36 nested CFG regions forming a tree. Currently the regions are
37 the entire function for the root region and natural loops for
38 the other regions. Therefore data structure representing a
39 region is called loop_tree_node.
41 o *Cover class* is a register class belonging to a set of
42 non-intersecting register classes containing all of the
43 hard-registers available for register allocation. The set of
44 all cover classes for a target is defined in the corresponding
45 machine-description file according some criteria. Such notion
46 is needed because Chaitin-Briggs algorithm works on
47 non-intersected register classes.
49 o *Allocno* represents the live range of a pseudo-register in a
50 region. Besides the obvious attributes like the corresponding
51 pseudo-register number, cover class, conflicting allocnos and
52 conflicting hard-registers, there are a few allocno attributes
53 which are important for understanding the allocation algorithm:
55 - *Live ranges*. This is a list of ranges of *program
56 points* where the allocno lives. Program points represent
57 places where a pseudo can be born or become dead (there are
58 approximately two times more program points than the insns)
59 and they are represented by integers starting with 0. The
60 live ranges are used to find conflicts between allocnos of
61 different cover classes. They also play very important role
62 for the transformation of the IRA internal representation of
63 several regions into a one region representation. The later is
64 used during the reload pass work because each allocno
65 represents all of the corresponding pseudo-registers.
67 - *Hard-register costs*. This is a vector of size equal to the
68 number of available hard-registers of the allocno's cover
69 class. The cost of a callee-clobbered hard-register for an
70 allocno is increased by the cost of save/restore code around
71 the calls through the given allocno's life. If the allocno
72 is a move instruction operand and another operand is a
73 hard-register of the allocno's cover class, the cost of the
74 hard-register is decreased by the move cost.
76 When an allocno is assigned, the hard-register with minimal
77 full cost is used. Initially, a hard-register's full cost is
78 the corresponding value from the hard-register's cost vector.
79 If the allocno is connected by a *copy* (see below) to
80 another allocno which has just received a hard-register, the
81 cost of the hard-register is decreased. Before choosing a
82 hard-register for an allocno, the allocno's current costs of
83 the hard-registers are modified by the conflict hard-register
84 costs of all of the conflicting allocnos which are not
87 - *Conflict hard-register costs*. This is a vector of the same
88 size as the hard-register costs vector. To permit an
89 unassigned allocno to get a better hard-register, IRA uses
90 this vector to calculate the final full cost of the
91 available hard-registers. Conflict hard-register costs of an
92 unassigned allocno are also changed with a change of the
93 hard-register cost of the allocno when a copy involving the
94 allocno is processed as described above. This is done to
95 show other unassigned allocnos that a given allocno prefers
96 some hard-registers in order to remove the move instruction
97 corresponding to the copy.
99 o *Cap*. If a pseudo-register does not live in a region but
100 lives in a nested region, IRA creates a special allocno called
101 a cap in the outer region. A region cap is also created for a
104 o *Copy*. Allocnos can be connected by copies. Copies are used
105 to modify hard-register costs for allocnos during coloring.
106 Such modifications reflects a preference to use the same
107 hard-register for the allocnos connected by copies. Usually
108 copies are created for move insns (in this case it results in
109 register coalescing). But IRA also creates copies for operands
110 of an insn which should be assigned to the same hard-register
111 due to constraints in the machine description (it usually
112 results in removing a move generated in reload to satisfy
113 the constraints) and copies referring to the allocno which is
114 the output operand of an instruction and the allocno which is
115 an input operand dying in the instruction (creation of such
116 copies results in less register shuffling). IRA *does not*
117 create copies between the same register allocnos from different
118 regions because we use another technique for propagating
119 hard-register preference on the borders of regions.
121 Allocnos (including caps) for the upper region in the region tree
122 *accumulate* information important for coloring from allocnos with
123 the same pseudo-register from nested regions. This includes
124 hard-register and memory costs, conflicts with hard-registers,
125 allocno conflicts, allocno copies and more. *Thus, attributes for
126 allocnos in a region have the same values as if the region had no
127 subregions*. It means that attributes for allocnos in the
128 outermost region corresponding to the function have the same values
129 as though the allocation used only one region which is the entire
130 function. It also means that we can look at IRA work as if the
131 first IRA did allocation for all function then it improved the
132 allocation for loops then their subloops and so on.
134 IRA major passes are:
136 o Building IRA internal representation which consists of the
139 * First, IRA builds regions and creates allocnos (file
140 ira-build.c) and initializes most of their attributes.
142 * Then IRA finds a cover class for each allocno and calculates
143 its initial (non-accumulated) cost of memory and each
144 hard-register of its cover class (file ira-cost.c).
146 * IRA creates live ranges of each allocno, calulates register
147 pressure for each cover class in each region, sets up
148 conflict hard registers for each allocno and info about calls
149 the allocno lives through (file ira-lives.c).
151 * IRA removes low register pressure loops from the regions
152 mostly to speed IRA up (file ira-build.c).
154 * IRA propagates accumulated allocno info from lower region
155 allocnos to corresponding upper region allocnos (file
158 * IRA creates all caps (file ira-build.c).
160 * Having live-ranges of allocnos and their cover classes, IRA
161 creates conflicting allocnos of the same cover class for each
162 allocno. Conflicting allocnos are stored as a bit vector or
163 array of pointers to the conflicting allocnos whatever is
164 more profitable (file ira-conflicts.c). At this point IRA
165 creates allocno copies.
167 o Coloring. Now IRA has all necessary info to start graph coloring
168 process. It is done in each region on top-down traverse of the
169 region tree (file ira-color.c). There are following subpasses:
171 * Optional aggressive coalescing of allocnos in the region.
173 * Putting allocnos onto the coloring stack. IRA uses Briggs
174 optimistic coloring which is a major improvement over
175 Chaitin's coloring. Therefore IRA does not spill allocnos at
176 this point. There is some freedom in the order of putting
177 allocnos on the stack which can affect the final result of
178 the allocation. IRA uses some heuristics to improve the order.
180 * Popping the allocnos from the stack and assigning them hard
181 registers. If IRA can not assign a hard register to an
182 allocno and the allocno is coalesced, IRA undoes the
183 coalescing and puts the uncoalesced allocnos onto the stack in
184 the hope that some such allocnos will get a hard register
185 separately. If IRA fails to assign hard register or memory
186 is more profitable for it, IRA spills the allocno. IRA
187 assigns the allocno the hard-register with minimal full
188 allocation cost which reflects the cost of usage of the
189 hard-register for the allocno and cost of usage of the
190 hard-register for allocnos conflicting with given allocno.
192 * After allono assigning in the region, IRA modifies the hard
193 register and memory costs for the corresponding allocnos in
194 the subregions to reflect the cost of possible loads, stores,
195 or moves on the border of the region and its subregions.
196 When default regional allocation algorithm is used
197 (-fira-algorithm=mixed), IRA just propagates the assignment
198 for allocnos if the register pressure in the region for the
199 corresponding cover class is less than number of available
200 hard registers for given cover class.
202 o Spill/restore code moving. When IRA performs an allocation
203 by traversing regions in top-down order, it does not know what
204 happens below in the region tree. Therefore, sometimes IRA
205 misses opportunities to perform a better allocation. A simple
206 optimization tries to improve allocation in a region having
207 subregions and containing in another region. If the
208 corresponding allocnos in the subregion are spilled, it spills
209 the region allocno if it is profitable. The optimization
210 implements a simple iterative algorithm performing profitable
211 transformations while they are still possible. It is fast in
212 practice, so there is no real need for a better time complexity
215 o Code change. After coloring, two allocnos representing the same
216 pseudo-register outside and inside a region respectively may be
217 assigned to different locations (hard-registers or memory). In
218 this case IRA creates and uses a new pseudo-register inside the
219 region and adds code to move allocno values on the region's
220 borders. This is done during top-down traversal of the regions
221 (file ira-emit.c). In some complicated cases IRA can create a
222 new allocno to move allocno values (e.g. when a swap of values
223 stored in two hard-registers is needed). At this stage, the
224 new allocno is marked as spilled. IRA still creates the
225 pseudo-register and the moves on the region borders even when
226 both allocnos were assigned to the same hard-register. If the
227 reload pass spills a pseudo-register for some reason, the
228 effect will be smaller because another allocno will still be in
229 the hard-register. In most cases, this is better then spilling
230 both allocnos. If reload does not change the allocation
231 for the two pseudo-registers, the trivial move will be removed
232 by post-reload optimizations. IRA does not generate moves for
233 allocnos assigned to the same hard register when the default
234 regional allocation algorithm is used and the register pressure
235 in the region for the corresponding allocno cover class is less
236 than number of available hard registers for given cover class.
237 IRA also does some optimizations to remove redundant stores and
238 to reduce code duplication on the region borders.
240 o Flattening internal representation. After changing code, IRA
241 transforms its internal representation for several regions into
242 one region representation (file ira-build.c). This process is
243 called IR flattening. Such process is more complicated than IR
244 rebuilding would be, but is much faster.
246 o After IR flattening, IRA tries to assign hard registers to all
247 spilled allocnos. This is impelemented by a simple and fast
248 priority coloring algorithm (see function
249 ira_reassign_conflict_allocnos::ira-color.c). Here new allocnos
250 created during the code change pass can be assigned to hard
253 o At the end IRA calls the reload pass. The reload pass
254 communicates with IRA through several functions in file
255 ira-color.c to improve its decisions in
257 * sharing stack slots for the spilled pseudos based on IRA info
258 about pseudo-register conflicts.
260 * reassigning hard-registers to all spilled pseudos at the end
261 of each reload iteration.
263 * choosing a better hard-register to spill based on IRA info
264 about pseudo-register live ranges and the register pressure
265 in places where the pseudo-register lives.
267 IRA uses a lot of data representing the target processors. These
268 data are initilized in file ira.c.
270 If function has no loops (or the loops are ignored when
271 -fira-algorithm=CB is used), we have classic Chaitin-Briggs
272 coloring (only instead of separate pass of coalescing, we use hard
273 register preferencing). In such case, IRA works much faster
274 because many things are not made (like IR flattening, the
275 spill/restore optimization, and the code change).
277 Literature is worth to read for better understanding the code:
279 o Preston Briggs, Keith D. Cooper, Linda Torczon. Improvements to
280 Graph Coloring Register Allocation.
282 o David Callahan, Brian Koblenz. Register allocation via
283 hierarchical graph coloring.
285 o Keith Cooper, Anshuman Dasgupta, Jason Eckhardt. Revisiting Graph
286 Coloring Register Allocation: A Study of the Chaitin-Briggs and
287 Callahan-Koblenz Algorithms.
289 o Guei-Yuan Lueh, Thomas Gross, and Ali-Reza Adl-Tabatabai. Global
290 Register Allocation Based on Graph Fusion.
292 o Vladimir Makarov. The Integrated Register Allocator for GCC.
294 o Vladimir Makarov. The top-down register allocator for irregular
295 register file architectures.
302 #include "coretypes.h"
311 #include "hard-reg-set.h"
312 #include "basic-block.h"
318 #include "tree-pass.h"
322 #include "diagnostic-core.h"
323 #include "integrate.h"
328 struct target_ira default_target_ira;
329 struct target_ira_int default_target_ira_int;
330 #if SWITCHABLE_TARGET
331 struct target_ira *this_target_ira = &default_target_ira;
332 struct target_ira_int *this_target_ira_int = &default_target_ira_int;
335 /* A modified value of flag `-fira-verbose' used internally. */
336 int internal_flag_ira_verbose;
338 /* Dump file of the allocator if it is not NULL. */
341 /* The number of elements in the following array. */
342 int ira_spilled_reg_stack_slots_num;
344 /* The following array contains info about spilled pseudo-registers
345 stack slots used in current function so far. */
346 struct ira_spilled_reg_stack_slot *ira_spilled_reg_stack_slots;
348 /* Correspondingly overall cost of the allocation, cost of the
349 allocnos assigned to hard-registers, cost of the allocnos assigned
350 to memory, cost of loads, stores and register move insns generated
351 for pseudo-register live range splitting (see ira-emit.c). */
352 int ira_overall_cost;
353 int ira_reg_cost, ira_mem_cost;
354 int ira_load_cost, ira_store_cost, ira_shuffle_cost;
355 int ira_move_loops_num, ira_additional_jumps_num;
357 /* All registers that can be eliminated. */
359 HARD_REG_SET eliminable_regset;
361 /* Temporary hard reg set used for a different calculation. */
362 static HARD_REG_SET temp_hard_regset;
366 /* The function sets up the map IRA_REG_MODE_HARD_REGSET. */
368 setup_reg_mode_hard_regset (void)
370 int i, m, hard_regno;
372 for (m = 0; m < NUM_MACHINE_MODES; m++)
373 for (hard_regno = 0; hard_regno < FIRST_PSEUDO_REGISTER; hard_regno++)
375 CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset[hard_regno][m]);
376 for (i = hard_regno_nregs[hard_regno][m] - 1; i >= 0; i--)
377 if (hard_regno + i < FIRST_PSEUDO_REGISTER)
378 SET_HARD_REG_BIT (ira_reg_mode_hard_regset[hard_regno][m],
384 #define no_unit_alloc_regs \
385 (this_target_ira_int->x_no_unit_alloc_regs)
387 /* The function sets up the three arrays declared above. */
389 setup_class_hard_regs (void)
391 int cl, i, hard_regno, n;
392 HARD_REG_SET processed_hard_reg_set;
394 ira_assert (SHRT_MAX >= FIRST_PSEUDO_REGISTER);
395 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
397 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
398 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
399 CLEAR_HARD_REG_SET (processed_hard_reg_set);
400 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
402 ira_non_ordered_class_hard_regs[cl][0] = -1;
403 ira_class_hard_reg_index[cl][0] = -1;
405 for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
407 #ifdef REG_ALLOC_ORDER
408 hard_regno = reg_alloc_order[i];
412 if (TEST_HARD_REG_BIT (processed_hard_reg_set, hard_regno))
414 SET_HARD_REG_BIT (processed_hard_reg_set, hard_regno);
415 if (! TEST_HARD_REG_BIT (temp_hard_regset, hard_regno))
416 ira_class_hard_reg_index[cl][hard_regno] = -1;
419 ira_class_hard_reg_index[cl][hard_regno] = n;
420 ira_class_hard_regs[cl][n++] = hard_regno;
423 ira_class_hard_regs_num[cl] = n;
424 for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
425 if (TEST_HARD_REG_BIT (temp_hard_regset, i))
426 ira_non_ordered_class_hard_regs[cl][n++] = i;
427 ira_assert (ira_class_hard_regs_num[cl] == n);
431 /* Set up IRA_AVAILABLE_CLASS_REGS. */
433 setup_available_class_regs (void)
437 memset (ira_available_class_regs, 0, sizeof (ira_available_class_regs));
438 for (i = 0; i < N_REG_CLASSES; i++)
440 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
441 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
442 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
443 if (TEST_HARD_REG_BIT (temp_hard_regset, j))
444 ira_available_class_regs[i]++;
448 /* Set up global variables defining info about hard registers for the
449 allocation. These depend on USE_HARD_FRAME_P whose TRUE value means
450 that we can use the hard frame pointer for the allocation. */
452 setup_alloc_regs (bool use_hard_frame_p)
454 #ifdef ADJUST_REG_ALLOC_ORDER
455 ADJUST_REG_ALLOC_ORDER;
457 COPY_HARD_REG_SET (no_unit_alloc_regs, fixed_reg_set);
458 if (! use_hard_frame_p)
459 SET_HARD_REG_BIT (no_unit_alloc_regs, HARD_FRAME_POINTER_REGNUM);
460 setup_class_hard_regs ();
461 setup_available_class_regs ();
466 /* Set up IRA_MEMORY_MOVE_COST, IRA_REGISTER_MOVE_COST. */
468 setup_class_subset_and_memory_move_costs (void)
471 HARD_REG_SET temp_hard_regset2;
473 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
474 ira_memory_move_cost[mode][NO_REGS][0]
475 = ira_memory_move_cost[mode][NO_REGS][1] = SHRT_MAX;
476 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
478 if (cl != (int) NO_REGS)
479 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
481 ira_memory_move_cost[mode][cl][0] =
482 memory_move_cost ((enum machine_mode) mode,
483 (enum reg_class) cl, false);
484 ira_memory_move_cost[mode][cl][1] =
485 memory_move_cost ((enum machine_mode) mode,
486 (enum reg_class) cl, true);
487 /* Costs for NO_REGS are used in cost calculation on the
488 1st pass when the preferred register classes are not
489 known yet. In this case we take the best scenario. */
490 if (ira_memory_move_cost[mode][NO_REGS][0]
491 > ira_memory_move_cost[mode][cl][0])
492 ira_memory_move_cost[mode][NO_REGS][0]
493 = ira_memory_move_cost[mode][cl][0];
494 if (ira_memory_move_cost[mode][NO_REGS][1]
495 > ira_memory_move_cost[mode][cl][1])
496 ira_memory_move_cost[mode][NO_REGS][1]
497 = ira_memory_move_cost[mode][cl][1];
499 for (cl2 = (int) N_REG_CLASSES - 1; cl2 >= 0; cl2--)
501 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
502 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
503 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]);
504 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
505 ira_class_subset_p[cl][cl2]
506 = hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2);
513 /* Define the following macro if allocation through malloc if
515 #define IRA_NO_OBSTACK
517 #ifndef IRA_NO_OBSTACK
518 /* Obstack used for storing all dynamic data (except bitmaps) of the
520 static struct obstack ira_obstack;
523 /* Obstack used for storing all bitmaps of the IRA. */
524 static struct bitmap_obstack ira_bitmap_obstack;
526 /* Allocate memory of size LEN for IRA data. */
528 ira_allocate (size_t len)
532 #ifndef IRA_NO_OBSTACK
533 res = obstack_alloc (&ira_obstack, len);
540 /* Reallocate memory PTR of size LEN for IRA data. */
542 ira_reallocate (void *ptr, size_t len)
546 #ifndef IRA_NO_OBSTACK
547 res = obstack_alloc (&ira_obstack, len);
549 res = xrealloc (ptr, len);
554 /* Free memory ADDR allocated for IRA data. */
556 ira_free (void *addr ATTRIBUTE_UNUSED)
558 #ifndef IRA_NO_OBSTACK
566 /* Allocate and returns bitmap for IRA. */
568 ira_allocate_bitmap (void)
570 return BITMAP_ALLOC (&ira_bitmap_obstack);
573 /* Free bitmap B allocated for IRA. */
575 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED)
582 /* Output information about allocation of all allocnos (except for
583 caps) into file F. */
585 ira_print_disposition (FILE *f)
591 fprintf (f, "Disposition:");
592 max_regno = max_reg_num ();
593 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
594 for (a = ira_regno_allocno_map[i];
596 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
601 fprintf (f, " %4d:r%-4d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
602 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
603 fprintf (f, "b%-3d", bb->index);
605 fprintf (f, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
606 if (ALLOCNO_HARD_REGNO (a) >= 0)
607 fprintf (f, " %3d", ALLOCNO_HARD_REGNO (a));
614 /* Outputs information about allocation of all allocnos into
617 ira_debug_disposition (void)
619 ira_print_disposition (stderr);
623 #define alloc_reg_class_subclasses \
624 (this_target_ira_int->x_alloc_reg_class_subclasses)
626 /* Initialize the table of subclasses of each reg class. */
628 setup_reg_subclasses (void)
631 HARD_REG_SET temp_hard_regset2;
633 for (i = 0; i < N_REG_CLASSES; i++)
634 for (j = 0; j < N_REG_CLASSES; j++)
635 alloc_reg_class_subclasses[i][j] = LIM_REG_CLASSES;
637 for (i = 0; i < N_REG_CLASSES; i++)
639 if (i == (int) NO_REGS)
642 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
643 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
644 if (hard_reg_set_empty_p (temp_hard_regset))
646 for (j = 0; j < N_REG_CLASSES; j++)
651 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[j]);
652 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
653 if (! hard_reg_set_subset_p (temp_hard_regset,
656 p = &alloc_reg_class_subclasses[j][0];
657 while (*p != LIM_REG_CLASSES) p++;
658 *p = (enum reg_class) i;
665 /* Set the four global variables defined above. */
667 setup_cover_and_important_classes (void)
671 const reg_class_t *cover_classes;
672 HARD_REG_SET temp_hard_regset2;
673 static enum reg_class classes[LIM_REG_CLASSES + 1];
675 if (targetm.ira_cover_classes == NULL)
676 cover_classes = NULL;
678 cover_classes = targetm.ira_cover_classes ();
679 if (cover_classes == NULL)
680 ira_assert (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY);
683 for (i = 0; (cl = cover_classes[i]) != LIM_REG_CLASSES; i++)
684 classes[i] = (enum reg_class) cl;
685 classes[i] = LIM_REG_CLASSES;
688 if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
691 for (i = 0; i <= LIM_REG_CLASSES; i++)
695 #ifdef CONSTRAINT_NUM_DEFINED_P
696 for (j = 0; j < CONSTRAINT__LIMIT; j++)
697 if ((int) REG_CLASS_FOR_CONSTRAINT ((enum constraint_num) j) == i)
699 if (j < CONSTRAINT__LIMIT)
701 classes[n++] = (enum reg_class) i;
705 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
706 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
707 for (j = 0; j < LIM_REG_CLASSES; j++)
711 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[j]);
712 AND_COMPL_HARD_REG_SET (temp_hard_regset2,
714 if (hard_reg_set_equal_p (temp_hard_regset,
719 classes[n++] = (enum reg_class) i;
721 classes[n] = LIM_REG_CLASSES;
724 ira_reg_class_cover_size = 0;
725 for (i = 0; (cl = classes[i]) != LIM_REG_CLASSES; i++)
727 for (j = 0; j < i; j++)
728 if (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
729 && reg_classes_intersect_p ((enum reg_class) cl, classes[j]))
731 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
732 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
733 if (! hard_reg_set_empty_p (temp_hard_regset))
734 ira_reg_class_cover[ira_reg_class_cover_size++] = (enum reg_class) cl;
736 ira_important_classes_num = 0;
737 for (cl = 0; cl < N_REG_CLASSES; cl++)
739 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
740 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
741 if (! hard_reg_set_empty_p (temp_hard_regset))
744 for (j = 0; j < ira_reg_class_cover_size; j++)
746 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
747 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
748 COPY_HARD_REG_SET (temp_hard_regset2,
749 reg_class_contents[ira_reg_class_cover[j]]);
750 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
751 if ((enum reg_class) cl == ira_reg_class_cover[j]
752 || hard_reg_set_equal_p (temp_hard_regset,
755 else if (hard_reg_set_subset_p (temp_hard_regset,
759 if (set_p && j >= ira_reg_class_cover_size)
760 ira_important_classes[ira_important_classes_num++]
761 = (enum reg_class) cl;
764 for (j = 0; j < ira_reg_class_cover_size; j++)
765 ira_important_classes[ira_important_classes_num++]
766 = ira_reg_class_cover[j];
769 /* Set up array IRA_CLASS_TRANSLATE. */
771 setup_class_translate (void)
774 enum reg_class cover_class, best_class, *cl_ptr;
775 int i, cost, min_cost, best_cost;
777 for (cl = 0; cl < N_REG_CLASSES; cl++)
778 ira_class_translate[cl] = NO_REGS;
780 if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
781 for (cl = 0; cl < LIM_REG_CLASSES; cl++)
783 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
784 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
785 for (i = 0; i < ira_reg_class_cover_size; i++)
787 HARD_REG_SET temp_hard_regset2;
789 cover_class = ira_reg_class_cover[i];
790 COPY_HARD_REG_SET (temp_hard_regset2,
791 reg_class_contents[cover_class]);
792 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
793 if (hard_reg_set_equal_p (temp_hard_regset, temp_hard_regset2))
794 ira_class_translate[cl] = cover_class;
797 for (i = 0; i < ira_reg_class_cover_size; i++)
799 cover_class = ira_reg_class_cover[i];
800 if (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY)
801 for (cl_ptr = &alloc_reg_class_subclasses[cover_class][0];
802 (cl = *cl_ptr) != LIM_REG_CLASSES;
805 if (ira_class_translate[cl] == NO_REGS)
806 ira_class_translate[cl] = cover_class;
807 #ifdef ENABLE_IRA_CHECKING
810 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
811 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
812 if (! hard_reg_set_empty_p (temp_hard_regset))
817 ira_class_translate[cover_class] = cover_class;
819 /* For classes which are not fully covered by a cover class (in
820 other words covered by more one cover class), use the cheapest
822 for (cl = 0; cl < N_REG_CLASSES; cl++)
824 if (cl == NO_REGS || ira_class_translate[cl] != NO_REGS)
826 best_class = NO_REGS;
828 for (i = 0; i < ira_reg_class_cover_size; i++)
830 cover_class = ira_reg_class_cover[i];
831 COPY_HARD_REG_SET (temp_hard_regset,
832 reg_class_contents[cover_class]);
833 AND_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
834 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
835 if (! hard_reg_set_empty_p (temp_hard_regset))
838 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
840 cost = (ira_memory_move_cost[mode][cl][0]
841 + ira_memory_move_cost[mode][cl][1]);
845 if (best_class == NO_REGS || best_cost > min_cost)
847 best_class = cover_class;
848 best_cost = min_cost;
852 ira_class_translate[cl] = best_class;
856 /* Order numbers of cover classes in original target cover class
857 array, -1 for non-cover classes. This is only live during
858 reorder_important_classes. */
859 static int cover_class_order[N_REG_CLASSES];
861 /* The function used to sort the important classes. */
863 comp_reg_classes_func (const void *v1p, const void *v2p)
865 enum reg_class cl1 = *(const enum reg_class *) v1p;
866 enum reg_class cl2 = *(const enum reg_class *) v2p;
869 cl1 = ira_class_translate[cl1];
870 cl2 = ira_class_translate[cl2];
871 if (cl1 != NO_REGS && cl2 != NO_REGS
872 && (diff = cover_class_order[cl1] - cover_class_order[cl2]) != 0)
874 return (int) cl1 - (int) cl2;
877 /* Reorder important classes according to the order of their cover
880 reorder_important_classes (void)
884 for (i = 0; i < N_REG_CLASSES; i++)
885 cover_class_order[i] = -1;
886 for (i = 0; i < ira_reg_class_cover_size; i++)
887 cover_class_order[ira_reg_class_cover[i]] = i;
888 qsort (ira_important_classes, ira_important_classes_num,
889 sizeof (enum reg_class), comp_reg_classes_func);
892 /* Set up the above reg class relations. */
894 setup_reg_class_relations (void)
896 int i, cl1, cl2, cl3;
897 HARD_REG_SET intersection_set, union_set, temp_set2;
898 bool important_class_p[N_REG_CLASSES];
900 memset (important_class_p, 0, sizeof (important_class_p));
901 for (i = 0; i < ira_important_classes_num; i++)
902 important_class_p[ira_important_classes[i]] = true;
903 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
905 ira_reg_class_super_classes[cl1][0] = LIM_REG_CLASSES;
906 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
908 ira_reg_classes_intersect_p[cl1][cl2] = false;
909 ira_reg_class_intersect[cl1][cl2] = NO_REGS;
910 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl1]);
911 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
912 COPY_HARD_REG_SET (temp_set2, reg_class_contents[cl2]);
913 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
914 if (hard_reg_set_empty_p (temp_hard_regset)
915 && hard_reg_set_empty_p (temp_set2))
919 cl3 = reg_class_subclasses[cl1][i];
920 if (cl3 == LIM_REG_CLASSES)
922 if (reg_class_subset_p (ira_reg_class_intersect[cl1][cl2],
923 (enum reg_class) cl3))
924 ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
926 ira_reg_class_union[cl1][cl2] = reg_class_subunion[cl1][cl2];
929 ira_reg_classes_intersect_p[cl1][cl2]
930 = hard_reg_set_intersect_p (temp_hard_regset, temp_set2);
931 if (important_class_p[cl1] && important_class_p[cl2]
932 && hard_reg_set_subset_p (temp_hard_regset, temp_set2))
936 p = &ira_reg_class_super_classes[cl1][0];
937 while (*p != LIM_REG_CLASSES)
939 *p++ = (enum reg_class) cl2;
940 *p = LIM_REG_CLASSES;
942 ira_reg_class_union[cl1][cl2] = NO_REGS;
943 COPY_HARD_REG_SET (intersection_set, reg_class_contents[cl1]);
944 AND_HARD_REG_SET (intersection_set, reg_class_contents[cl2]);
945 AND_COMPL_HARD_REG_SET (intersection_set, no_unit_alloc_regs);
946 COPY_HARD_REG_SET (union_set, reg_class_contents[cl1]);
947 IOR_HARD_REG_SET (union_set, reg_class_contents[cl2]);
948 AND_COMPL_HARD_REG_SET (union_set, no_unit_alloc_regs);
949 for (i = 0; i < ira_important_classes_num; i++)
951 cl3 = ira_important_classes[i];
952 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl3]);
953 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
954 if (hard_reg_set_subset_p (temp_hard_regset, intersection_set))
958 reg_class_contents[(int)
959 ira_reg_class_intersect[cl1][cl2]]);
960 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
961 if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
962 /* Ignore unavailable hard registers and prefer
963 smallest class for debugging purposes. */
964 || (hard_reg_set_equal_p (temp_hard_regset, temp_set2)
965 && hard_reg_set_subset_p
966 (reg_class_contents[cl3],
968 [(int) ira_reg_class_intersect[cl1][cl2]])))
969 ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
971 if (hard_reg_set_subset_p (temp_hard_regset, union_set))
975 reg_class_contents[(int) ira_reg_class_union[cl1][cl2]]);
976 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
977 if (ira_reg_class_union[cl1][cl2] == NO_REGS
978 || (hard_reg_set_subset_p (temp_set2, temp_hard_regset)
980 && (! hard_reg_set_equal_p (temp_set2,
982 /* Ignore unavailable hard registers and
983 prefer smallest class for debugging
985 || hard_reg_set_subset_p
986 (reg_class_contents[cl3],
988 [(int) ira_reg_class_union[cl1][cl2]]))))
989 ira_reg_class_union[cl1][cl2] = (enum reg_class) cl3;
996 /* Output all cover classes and the translation map into file F. */
998 print_class_cover (FILE *f)
1000 static const char *const reg_class_names[] = REG_CLASS_NAMES;
1003 fprintf (f, "Class cover:\n");
1004 for (i = 0; i < ira_reg_class_cover_size; i++)
1005 fprintf (f, " %s", reg_class_names[ira_reg_class_cover[i]]);
1006 fprintf (f, "\nClass translation:\n");
1007 for (i = 0; i < N_REG_CLASSES; i++)
1008 fprintf (f, " %s -> %s\n", reg_class_names[i],
1009 reg_class_names[ira_class_translate[i]]);
1012 /* Output all cover classes and the translation map into
1015 ira_debug_class_cover (void)
1017 print_class_cover (stderr);
1020 /* Set up different arrays concerning class subsets, cover and
1021 important classes. */
1023 find_reg_class_closure (void)
1025 setup_reg_subclasses ();
1026 setup_cover_and_important_classes ();
1027 setup_class_translate ();
1028 reorder_important_classes ();
1029 setup_reg_class_relations ();
1034 /* Set up the array above. */
1036 setup_hard_regno_cover_class (void)
1041 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1043 ira_hard_regno_cover_class[i] = NO_REGS;
1044 for (j = 0; j < ira_reg_class_cover_size; j++)
1046 cl = ira_reg_class_cover[j];
1047 if (ira_class_hard_reg_index[cl][i] >= 0)
1049 ira_hard_regno_cover_class[i] = cl;
1059 /* Form IRA_REG_CLASS_NREGS map. */
1061 setup_reg_class_nregs (void)
1065 for (cl = 0; cl < N_REG_CLASSES; cl++)
1066 for (m = 0; m < MAX_MACHINE_MODE; m++)
1067 ira_reg_class_nregs[cl][m] = CLASS_MAX_NREGS ((enum reg_class) cl,
1068 (enum machine_mode) m);
1073 /* Set up PROHIBITED_CLASS_MODE_REGS. */
1075 setup_prohibited_class_mode_regs (void)
1077 int i, j, k, hard_regno;
1080 for (i = 0; i < ira_reg_class_cover_size; i++)
1082 cl = ira_reg_class_cover[i];
1083 for (j = 0; j < NUM_MACHINE_MODES; j++)
1085 CLEAR_HARD_REG_SET (prohibited_class_mode_regs[cl][j]);
1086 for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1088 hard_regno = ira_class_hard_regs[cl][k];
1089 if (! HARD_REGNO_MODE_OK (hard_regno, (enum machine_mode) j))
1090 SET_HARD_REG_BIT (prohibited_class_mode_regs[cl][j],
1099 /* Allocate and initialize IRA_REGISTER_MOVE_COST,
1100 IRA_MAY_MOVE_IN_COST, and IRA_MAY_MOVE_OUT_COST for MODE if it is
1103 ira_init_register_move_cost (enum machine_mode mode)
1107 ira_assert (ira_register_move_cost[mode] == NULL
1108 && ira_may_move_in_cost[mode] == NULL
1109 && ira_may_move_out_cost[mode] == NULL);
1110 if (move_cost[mode] == NULL)
1111 init_move_cost (mode);
1112 ira_register_move_cost[mode] = move_cost[mode];
1113 /* Don't use ira_allocate because the tables exist out of scope of a
1115 ira_may_move_in_cost[mode]
1116 = (move_table *) xmalloc (sizeof (move_table) * N_REG_CLASSES);
1117 memcpy (ira_may_move_in_cost[mode], may_move_in_cost[mode],
1118 sizeof (move_table) * N_REG_CLASSES);
1119 ira_may_move_out_cost[mode]
1120 = (move_table *) xmalloc (sizeof (move_table) * N_REG_CLASSES);
1121 memcpy (ira_may_move_out_cost[mode], may_move_out_cost[mode],
1122 sizeof (move_table) * N_REG_CLASSES);
1123 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1125 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1127 if (ira_class_subset_p[cl1][cl2])
1128 ira_may_move_in_cost[mode][cl1][cl2] = 0;
1129 if (ira_class_subset_p[cl2][cl1])
1130 ira_may_move_out_cost[mode][cl1][cl2] = 0;
1137 /* This is called once during compiler work. It sets up
1138 different arrays whose values don't depend on the compiled
1141 ira_init_once (void)
1145 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1147 ira_register_move_cost[mode] = NULL;
1148 ira_may_move_in_cost[mode] = NULL;
1149 ira_may_move_out_cost[mode] = NULL;
1151 ira_init_costs_once ();
1154 /* Free ira_register_move_cost, ira_may_move_in_cost, and
1155 ira_may_move_out_cost for each mode. */
1157 free_register_move_costs (void)
1161 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1163 if (ira_may_move_in_cost[mode] != NULL)
1164 free (ira_may_move_in_cost[mode]);
1165 if (ira_may_move_out_cost[mode] != NULL)
1166 free (ira_may_move_out_cost[mode]);
1167 ira_register_move_cost[mode] = NULL;
1168 ira_may_move_in_cost[mode] = NULL;
1169 ira_may_move_out_cost[mode] = NULL;
1173 /* This is called every time when register related information is
1178 free_register_move_costs ();
1179 setup_reg_mode_hard_regset ();
1180 setup_alloc_regs (flag_omit_frame_pointer != 0);
1181 setup_class_subset_and_memory_move_costs ();
1182 find_reg_class_closure ();
1183 setup_hard_regno_cover_class ();
1184 setup_reg_class_nregs ();
1185 setup_prohibited_class_mode_regs ();
1189 /* Function called once at the end of compiler work. */
1191 ira_finish_once (void)
1193 ira_finish_costs_once ();
1194 free_register_move_costs ();
1198 #define ira_prohibited_mode_move_regs_initialized_p \
1199 (this_target_ira_int->x_ira_prohibited_mode_move_regs_initialized_p)
1201 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS. */
1203 setup_prohibited_mode_move_regs (void)
1206 rtx test_reg1, test_reg2, move_pat, move_insn;
1208 if (ira_prohibited_mode_move_regs_initialized_p)
1210 ira_prohibited_mode_move_regs_initialized_p = true;
1211 test_reg1 = gen_rtx_REG (VOIDmode, 0);
1212 test_reg2 = gen_rtx_REG (VOIDmode, 0);
1213 move_pat = gen_rtx_SET (VOIDmode, test_reg1, test_reg2);
1214 move_insn = gen_rtx_INSN (VOIDmode, 0, 0, 0, 0, 0, move_pat, -1, 0);
1215 for (i = 0; i < NUM_MACHINE_MODES; i++)
1217 SET_HARD_REG_SET (ira_prohibited_mode_move_regs[i]);
1218 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1220 if (! HARD_REGNO_MODE_OK (j, (enum machine_mode) i))
1222 SET_REGNO (test_reg1, j);
1223 PUT_MODE (test_reg1, (enum machine_mode) i);
1224 SET_REGNO (test_reg2, j);
1225 PUT_MODE (test_reg2, (enum machine_mode) i);
1226 INSN_CODE (move_insn) = -1;
1227 recog_memoized (move_insn);
1228 if (INSN_CODE (move_insn) < 0)
1230 extract_insn (move_insn);
1231 if (! constrain_operands (1))
1233 CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs[i], j);
1240 /* Return nonzero if REGNO is a particularly bad choice for reloading X. */
1242 ira_bad_reload_regno_1 (int regno, rtx x)
1246 enum reg_class pref;
1248 /* We only deal with pseudo regs. */
1249 if (! x || GET_CODE (x) != REG)
1252 x_regno = REGNO (x);
1253 if (x_regno < FIRST_PSEUDO_REGISTER)
1256 /* If the pseudo prefers REGNO explicitly, then do not consider
1257 REGNO a bad spill choice. */
1258 pref = reg_preferred_class (x_regno);
1259 if (reg_class_size[pref] == 1)
1260 return !TEST_HARD_REG_BIT (reg_class_contents[pref], regno);
1262 /* If the pseudo conflicts with REGNO, then we consider REGNO a
1263 poor choice for a reload regno. */
1264 a = ira_regno_allocno_map[x_regno];
1265 if (TEST_HARD_REG_BIT (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), regno))
1271 /* Return nonzero if REGNO is a particularly bad choice for reloading
1274 ira_bad_reload_regno (int regno, rtx in, rtx out)
1276 return (ira_bad_reload_regno_1 (regno, in)
1277 || ira_bad_reload_regno_1 (regno, out));
1280 /* Function specific hard registers that can not be used for the
1281 register allocation. */
1282 HARD_REG_SET ira_no_alloc_regs;
1284 /* Return TRUE if *LOC contains an asm. */
1286 insn_contains_asm_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
1290 if (GET_CODE (*loc) == ASM_OPERANDS)
1296 /* Return TRUE if INSN contains an ASM. */
1298 insn_contains_asm (rtx insn)
1300 return for_each_rtx (&insn, insn_contains_asm_1, NULL);
1303 /* Add register clobbers from asm statements. */
1305 compute_regs_asm_clobbered (void)
1312 FOR_BB_INSNS_REVERSE (bb, insn)
1316 if (insn_contains_asm (insn))
1317 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
1319 df_ref def = *def_rec;
1320 unsigned int dregno = DF_REF_REGNO (def);
1321 if (dregno < FIRST_PSEUDO_REGISTER)
1324 enum machine_mode mode = GET_MODE (DF_REF_REAL_REG (def));
1325 unsigned int end = dregno
1326 + hard_regno_nregs[dregno][mode] - 1;
1328 for (i = dregno; i <= end; ++i)
1329 SET_HARD_REG_BIT(crtl->asm_clobbers, i);
1337 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and REGS_EVER_LIVE. */
1339 ira_setup_eliminable_regset (void)
1341 #ifdef ELIMINABLE_REGS
1343 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
1345 /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
1346 sp for alloca. So we can't eliminate the frame pointer in that
1347 case. At some point, we should improve this by emitting the
1348 sp-adjusting insns for this case. */
1350 = (! flag_omit_frame_pointer
1351 || (cfun->calls_alloca && EXIT_IGNORE_STACK)
1352 /* We need the frame pointer to catch stack overflow exceptions
1353 if the stack pointer is moving. */
1354 || (flag_stack_check && STACK_CHECK_MOVING_SP)
1355 || crtl->accesses_prior_frames
1356 || crtl->stack_realign_needed
1357 || targetm.frame_pointer_required ());
1359 frame_pointer_needed = need_fp;
1361 COPY_HARD_REG_SET (ira_no_alloc_regs, no_unit_alloc_regs);
1362 CLEAR_HARD_REG_SET (eliminable_regset);
1364 compute_regs_asm_clobbered ();
1366 /* Build the regset of all eliminable registers and show we can't
1367 use those that we already know won't be eliminated. */
1368 #ifdef ELIMINABLE_REGS
1369 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
1372 = (! targetm.can_eliminate (eliminables[i].from, eliminables[i].to)
1373 || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp));
1375 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, eliminables[i].from))
1377 SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
1380 SET_HARD_REG_BIT (ira_no_alloc_regs, eliminables[i].from);
1382 else if (cannot_elim)
1383 error ("%s cannot be used in asm here",
1384 reg_names[eliminables[i].from]);
1386 df_set_regs_ever_live (eliminables[i].from, true);
1388 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
1389 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM))
1391 SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
1393 SET_HARD_REG_BIT (ira_no_alloc_regs, HARD_FRAME_POINTER_REGNUM);
1396 error ("%s cannot be used in asm here",
1397 reg_names[HARD_FRAME_POINTER_REGNUM]);
1399 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
1403 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM))
1405 SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
1407 SET_HARD_REG_BIT (ira_no_alloc_regs, FRAME_POINTER_REGNUM);
1410 error ("%s cannot be used in asm here", reg_names[FRAME_POINTER_REGNUM]);
1412 df_set_regs_ever_live (FRAME_POINTER_REGNUM, true);
1418 /* The length of the following two arrays. */
1419 int ira_reg_equiv_len;
1421 /* The element value is TRUE if the corresponding regno value is
1423 bool *ira_reg_equiv_invariant_p;
1425 /* The element value is equiv constant of given pseudo-register or
1427 rtx *ira_reg_equiv_const;
1429 /* Set up the two arrays declared above. */
1431 find_reg_equiv_invariant_const (void)
1435 rtx list, insn, note, constant, x;
1437 for (i = FIRST_PSEUDO_REGISTER; i < reg_equiv_init_size; i++)
1439 constant = NULL_RTX;
1440 invariant_p = false;
1441 for (list = reg_equiv_init[i]; list != NULL_RTX; list = XEXP (list, 1))
1443 insn = XEXP (list, 0);
1444 note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
1446 if (note == NULL_RTX)
1451 if (! CONSTANT_P (x)
1452 || ! flag_pic || LEGITIMATE_PIC_OPERAND_P (x))
1454 /* It can happen that a REG_EQUIV note contains a MEM
1455 that is not a legitimate memory operand. As later
1456 stages of the reload assume that all addresses found
1457 in the reg_equiv_* arrays were originally legitimate,
1458 we ignore such REG_EQUIV notes. */
1459 if (memory_operand (x, VOIDmode))
1460 invariant_p = MEM_READONLY_P (x);
1461 else if (function_invariant_p (x))
1463 if (GET_CODE (x) == PLUS
1464 || x == frame_pointer_rtx || x == arg_pointer_rtx)
1471 ira_reg_equiv_invariant_p[i] = invariant_p;
1472 ira_reg_equiv_const[i] = constant;
1478 /* Vector of substitutions of register numbers,
1479 used to map pseudo regs into hardware regs.
1480 This is set up as a result of register allocation.
1481 Element N is the hard reg assigned to pseudo reg N,
1482 or is -1 if no hard reg was assigned.
1483 If N is a hard reg number, element N is N. */
1484 short *reg_renumber;
1486 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
1487 the allocation found by IRA. */
1489 setup_reg_renumber (void)
1491 int regno, hard_regno;
1493 ira_allocno_iterator ai;
1495 caller_save_needed = 0;
1496 FOR_EACH_ALLOCNO (a, ai)
1498 /* There are no caps at this point. */
1499 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
1500 if (! ALLOCNO_ASSIGNED_P (a))
1501 /* It can happen if A is not referenced but partially anticipated
1502 somewhere in a region. */
1503 ALLOCNO_ASSIGNED_P (a) = true;
1504 ira_free_allocno_updated_costs (a);
1505 hard_regno = ALLOCNO_HARD_REGNO (a);
1506 regno = (int) REGNO (ALLOCNO_REG (a));
1507 reg_renumber[regno] = (hard_regno < 0 ? -1 : hard_regno);
1508 if (hard_regno >= 0 && ALLOCNO_CALLS_CROSSED_NUM (a) != 0
1509 && ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
1512 ira_assert (!optimize || flag_caller_saves
1513 || regno >= ira_reg_equiv_len
1514 || ira_reg_equiv_const[regno]
1515 || ira_reg_equiv_invariant_p[regno]);
1516 caller_save_needed = 1;
1521 /* Set up allocno assignment flags for further allocation
1524 setup_allocno_assignment_flags (void)
1528 ira_allocno_iterator ai;
1530 FOR_EACH_ALLOCNO (a, ai)
1532 if (! ALLOCNO_ASSIGNED_P (a))
1533 /* It can happen if A is not referenced but partially anticipated
1534 somewhere in a region. */
1535 ira_free_allocno_updated_costs (a);
1536 hard_regno = ALLOCNO_HARD_REGNO (a);
1537 /* Don't assign hard registers to allocnos which are destination
1538 of removed store at the end of loop. It has no sense to keep
1539 the same value in different hard registers. It is also
1540 impossible to assign hard registers correctly to such
1541 allocnos because the cost info and info about intersected
1542 calls are incorrect for them. */
1543 ALLOCNO_ASSIGNED_P (a) = (hard_regno >= 0
1544 || ALLOCNO_MEM_OPTIMIZED_DEST_P (a)
1545 || (ALLOCNO_MEMORY_COST (a)
1546 - ALLOCNO_COVER_CLASS_COST (a)) < 0);
1547 ira_assert (hard_regno < 0
1548 || ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
1550 [ALLOCNO_COVER_CLASS (a)]));
1554 /* Evaluate overall allocation cost and the costs for using hard
1555 registers and memory for allocnos. */
1557 calculate_allocation_cost (void)
1559 int hard_regno, cost;
1561 ira_allocno_iterator ai;
1563 ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
1564 FOR_EACH_ALLOCNO (a, ai)
1566 hard_regno = ALLOCNO_HARD_REGNO (a);
1567 ira_assert (hard_regno < 0
1568 || ! ira_hard_reg_not_in_set_p
1569 (hard_regno, ALLOCNO_MODE (a),
1570 reg_class_contents[ALLOCNO_COVER_CLASS (a)]));
1573 cost = ALLOCNO_MEMORY_COST (a);
1574 ira_mem_cost += cost;
1576 else if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
1578 cost = (ALLOCNO_HARD_REG_COSTS (a)
1579 [ira_class_hard_reg_index
1580 [ALLOCNO_COVER_CLASS (a)][hard_regno]]);
1581 ira_reg_cost += cost;
1585 cost = ALLOCNO_COVER_CLASS_COST (a);
1586 ira_reg_cost += cost;
1588 ira_overall_cost += cost;
1591 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
1593 fprintf (ira_dump_file,
1594 "+++Costs: overall %d, reg %d, mem %d, ld %d, st %d, move %d\n",
1595 ira_overall_cost, ira_reg_cost, ira_mem_cost,
1596 ira_load_cost, ira_store_cost, ira_shuffle_cost);
1597 fprintf (ira_dump_file, "+++ move loops %d, new jumps %d\n",
1598 ira_move_loops_num, ira_additional_jumps_num);
1603 #ifdef ENABLE_IRA_CHECKING
1604 /* Check the correctness of the allocation. We do need this because
1605 of complicated code to transform more one region internal
1606 representation into one region representation. */
1608 check_allocation (void)
1610 ira_allocno_t a, conflict_a;
1611 int hard_regno, conflict_hard_regno, nregs, conflict_nregs;
1612 ira_allocno_conflict_iterator aci;
1613 ira_allocno_iterator ai;
1615 FOR_EACH_ALLOCNO (a, ai)
1617 if (ALLOCNO_CAP_MEMBER (a) != NULL
1618 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
1620 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
1621 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
1622 if ((conflict_hard_regno = ALLOCNO_HARD_REGNO (conflict_a)) >= 0)
1626 [conflict_hard_regno][ALLOCNO_MODE (conflict_a)]);
1627 if ((conflict_hard_regno <= hard_regno
1628 && hard_regno < conflict_hard_regno + conflict_nregs)
1629 || (hard_regno <= conflict_hard_regno
1630 && conflict_hard_regno < hard_regno + nregs))
1632 fprintf (stderr, "bad allocation for %d and %d\n",
1633 ALLOCNO_REGNO (a), ALLOCNO_REGNO (conflict_a));
1641 /* Fix values of array REG_EQUIV_INIT after live range splitting done
1644 fix_reg_equiv_init (void)
1646 int max_regno = max_reg_num ();
1648 rtx x, prev, next, insn, set;
1650 if (reg_equiv_init_size < max_regno)
1652 reg_equiv_init = GGC_RESIZEVEC (rtx, reg_equiv_init, max_regno);
1653 while (reg_equiv_init_size < max_regno)
1654 reg_equiv_init[reg_equiv_init_size++] = NULL_RTX;
1655 for (i = FIRST_PSEUDO_REGISTER; i < reg_equiv_init_size; i++)
1656 for (prev = NULL_RTX, x = reg_equiv_init[i]; x != NULL_RTX; x = next)
1660 set = single_set (insn);
1661 ira_assert (set != NULL_RTX
1662 && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))));
1663 if (REG_P (SET_DEST (set))
1664 && ((int) REGNO (SET_DEST (set)) == i
1665 || (int) ORIGINAL_REGNO (SET_DEST (set)) == i))
1666 new_regno = REGNO (SET_DEST (set));
1667 else if (REG_P (SET_SRC (set))
1668 && ((int) REGNO (SET_SRC (set)) == i
1669 || (int) ORIGINAL_REGNO (SET_SRC (set)) == i))
1670 new_regno = REGNO (SET_SRC (set));
1677 if (prev == NULL_RTX)
1678 reg_equiv_init[i] = next;
1680 XEXP (prev, 1) = next;
1681 XEXP (x, 1) = reg_equiv_init[new_regno];
1682 reg_equiv_init[new_regno] = x;
1688 #ifdef ENABLE_IRA_CHECKING
1689 /* Print redundant memory-memory copies. */
1691 print_redundant_copies (void)
1695 ira_copy_t cp, next_cp;
1696 ira_allocno_iterator ai;
1698 FOR_EACH_ALLOCNO (a, ai)
1700 if (ALLOCNO_CAP_MEMBER (a) != NULL)
1703 hard_regno = ALLOCNO_HARD_REGNO (a);
1704 if (hard_regno >= 0)
1706 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1708 next_cp = cp->next_first_allocno_copy;
1711 next_cp = cp->next_second_allocno_copy;
1712 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL
1713 && cp->insn != NULL_RTX
1714 && ALLOCNO_HARD_REGNO (cp->first) == hard_regno)
1715 fprintf (ira_dump_file,
1716 " Redundant move from %d(freq %d):%d\n",
1717 INSN_UID (cp->insn), cp->freq, hard_regno);
1723 /* Setup preferred and alternative classes for new pseudo-registers
1724 created by IRA starting with START. */
1726 setup_preferred_alternate_classes_for_new_pseudos (int start)
1729 int max_regno = max_reg_num ();
1731 for (i = start; i < max_regno; i++)
1733 old_regno = ORIGINAL_REGNO (regno_reg_rtx[i]);
1734 ira_assert (i != old_regno);
1735 setup_reg_classes (i, reg_preferred_class (old_regno),
1736 reg_alternate_class (old_regno),
1737 reg_cover_class (old_regno));
1738 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1739 fprintf (ira_dump_file,
1740 " New r%d: setting preferred %s, alternative %s\n",
1741 i, reg_class_names[reg_preferred_class (old_regno)],
1742 reg_class_names[reg_alternate_class (old_regno)]);
1748 /* Regional allocation can create new pseudo-registers. This function
1749 expands some arrays for pseudo-registers. */
1751 expand_reg_info (int old_size)
1754 int size = max_reg_num ();
1757 for (i = old_size; i < size; i++)
1758 setup_reg_classes (i, GENERAL_REGS, ALL_REGS, GENERAL_REGS);
1761 /* Return TRUE if there is too high register pressure in the function.
1762 It is used to decide when stack slot sharing is worth to do. */
1764 too_high_register_pressure_p (void)
1767 enum reg_class cover_class;
1769 for (i = 0; i < ira_reg_class_cover_size; i++)
1771 cover_class = ira_reg_class_cover[i];
1772 if (ira_loop_tree_root->reg_pressure[cover_class] > 10000)
1780 /* Indicate that hard register number FROM was eliminated and replaced with
1781 an offset from hard register number TO. The status of hard registers live
1782 at the start of a basic block is updated by replacing a use of FROM with
1786 mark_elimination (int from, int to)
1792 /* We don't use LIVE info in IRA. */
1793 bitmap r = DF_LR_IN (bb);
1795 if (REGNO_REG_SET_P (r, from))
1797 CLEAR_REGNO_REG_SET (r, from);
1798 SET_REGNO_REG_SET (r, to);
1807 /* Set when a REG_EQUIV note is found or created. Use to
1808 keep track of what memory accesses might be created later,
1812 /* The list of each instruction which initializes this register. */
1814 /* Loop depth is used to recognize equivalences which appear
1815 to be present within the same loop (or in an inner loop). */
1817 /* Nonzero if this had a preexisting REG_EQUIV note. */
1818 int is_arg_equivalence;
1819 /* Set when an attempt should be made to replace a register
1820 with the associated src_p entry. */
1824 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
1825 structure for that register. */
1826 static struct equivalence *reg_equiv;
1828 /* Used for communication between the following two functions: contains
1829 a MEM that we wish to ensure remains unchanged. */
1830 static rtx equiv_mem;
1832 /* Set nonzero if EQUIV_MEM is modified. */
1833 static int equiv_mem_modified;
1835 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
1836 Called via note_stores. */
1838 validate_equiv_mem_from_store (rtx dest, const_rtx set ATTRIBUTE_UNUSED,
1839 void *data ATTRIBUTE_UNUSED)
1842 && reg_overlap_mentioned_p (dest, equiv_mem))
1844 && true_dependence (dest, VOIDmode, equiv_mem, rtx_varies_p)))
1845 equiv_mem_modified = 1;
1848 /* Verify that no store between START and the death of REG invalidates
1849 MEMREF. MEMREF is invalidated by modifying a register used in MEMREF,
1850 by storing into an overlapping memory location, or with a non-const
1853 Return 1 if MEMREF remains valid. */
1855 validate_equiv_mem (rtx start, rtx reg, rtx memref)
1861 equiv_mem_modified = 0;
1863 /* If the memory reference has side effects or is volatile, it isn't a
1864 valid equivalence. */
1865 if (side_effects_p (memref))
1868 for (insn = start; insn && ! equiv_mem_modified; insn = NEXT_INSN (insn))
1870 if (! INSN_P (insn))
1873 if (find_reg_note (insn, REG_DEAD, reg))
1876 if (CALL_P (insn) && ! MEM_READONLY_P (memref)
1877 && ! RTL_CONST_OR_PURE_CALL_P (insn))
1880 note_stores (PATTERN (insn), validate_equiv_mem_from_store, NULL);
1882 /* If a register mentioned in MEMREF is modified via an
1883 auto-increment, we lose the equivalence. Do the same if one
1884 dies; although we could extend the life, it doesn't seem worth
1887 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1888 if ((REG_NOTE_KIND (note) == REG_INC
1889 || REG_NOTE_KIND (note) == REG_DEAD)
1890 && REG_P (XEXP (note, 0))
1891 && reg_overlap_mentioned_p (XEXP (note, 0), memref))
1898 /* Returns zero if X is known to be invariant. */
1900 equiv_init_varies_p (rtx x)
1902 RTX_CODE code = GET_CODE (x);
1909 return !MEM_READONLY_P (x) || equiv_init_varies_p (XEXP (x, 0));
1921 return reg_equiv[REGNO (x)].replace == 0 && rtx_varies_p (x, 0);
1924 if (MEM_VOLATILE_P (x))
1933 fmt = GET_RTX_FORMAT (code);
1934 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1937 if (equiv_init_varies_p (XEXP (x, i)))
1940 else if (fmt[i] == 'E')
1943 for (j = 0; j < XVECLEN (x, i); j++)
1944 if (equiv_init_varies_p (XVECEXP (x, i, j)))
1951 /* Returns nonzero if X (used to initialize register REGNO) is movable.
1952 X is only movable if the registers it uses have equivalent initializations
1953 which appear to be within the same loop (or in an inner loop) and movable
1954 or if they are not candidates for local_alloc and don't vary. */
1956 equiv_init_movable_p (rtx x, int regno)
1960 enum rtx_code code = GET_CODE (x);
1965 return equiv_init_movable_p (SET_SRC (x), regno);
1980 return (reg_equiv[REGNO (x)].loop_depth >= reg_equiv[regno].loop_depth
1981 && reg_equiv[REGNO (x)].replace)
1982 || (REG_BASIC_BLOCK (REGNO (x)) < NUM_FIXED_BLOCKS && ! rtx_varies_p (x, 0));
1984 case UNSPEC_VOLATILE:
1988 if (MEM_VOLATILE_P (x))
1997 fmt = GET_RTX_FORMAT (code);
1998 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2002 if (! equiv_init_movable_p (XEXP (x, i), regno))
2006 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2007 if (! equiv_init_movable_p (XVECEXP (x, i, j), regno))
2015 /* TRUE if X uses any registers for which reg_equiv[REGNO].replace is true. */
2017 contains_replace_regs (rtx x)
2021 enum rtx_code code = GET_CODE (x);
2038 return reg_equiv[REGNO (x)].replace;
2044 fmt = GET_RTX_FORMAT (code);
2045 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2049 if (contains_replace_regs (XEXP (x, i)))
2053 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2054 if (contains_replace_regs (XVECEXP (x, i, j)))
2062 /* TRUE if X references a memory location that would be affected by a store
2065 memref_referenced_p (rtx memref, rtx x)
2069 enum rtx_code code = GET_CODE (x);
2087 return (reg_equiv[REGNO (x)].replacement
2088 && memref_referenced_p (memref,
2089 reg_equiv[REGNO (x)].replacement));
2092 if (true_dependence (memref, VOIDmode, x, rtx_varies_p))
2097 /* If we are setting a MEM, it doesn't count (its address does), but any
2098 other SET_DEST that has a MEM in it is referencing the MEM. */
2099 if (MEM_P (SET_DEST (x)))
2101 if (memref_referenced_p (memref, XEXP (SET_DEST (x), 0)))
2104 else if (memref_referenced_p (memref, SET_DEST (x)))
2107 return memref_referenced_p (memref, SET_SRC (x));
2113 fmt = GET_RTX_FORMAT (code);
2114 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2118 if (memref_referenced_p (memref, XEXP (x, i)))
2122 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2123 if (memref_referenced_p (memref, XVECEXP (x, i, j)))
2131 /* TRUE if some insn in the range (START, END] references a memory location
2132 that would be affected by a store to MEMREF. */
2134 memref_used_between_p (rtx memref, rtx start, rtx end)
2138 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2139 insn = NEXT_INSN (insn))
2141 if (!NONDEBUG_INSN_P (insn))
2144 if (memref_referenced_p (memref, PATTERN (insn)))
2147 /* Nonconst functions may access memory. */
2148 if (CALL_P (insn) && (! RTL_CONST_CALL_P (insn)))
2155 /* Mark REG as having no known equivalence.
2156 Some instructions might have been processed before and furnished
2157 with REG_EQUIV notes for this register; these notes will have to be
2159 STORE is the piece of RTL that does the non-constant / conflicting
2160 assignment - a SET, CLOBBER or REG_INC note. It is currently not used,
2161 but needs to be there because this function is called from note_stores. */
2163 no_equiv (rtx reg, const_rtx store ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED)
2170 regno = REGNO (reg);
2171 list = reg_equiv[regno].init_insns;
2172 if (list == const0_rtx)
2174 reg_equiv[regno].init_insns = const0_rtx;
2175 reg_equiv[regno].replacement = NULL_RTX;
2176 /* This doesn't matter for equivalences made for argument registers, we
2177 should keep their initialization insns. */
2178 if (reg_equiv[regno].is_arg_equivalence)
2180 reg_equiv_init[regno] = NULL_RTX;
2181 for (; list; list = XEXP (list, 1))
2183 rtx insn = XEXP (list, 0);
2184 remove_note (insn, find_reg_note (insn, REG_EQUIV, NULL_RTX));
2188 /* In DEBUG_INSN location adjust REGs from CLEARED_REGS bitmap to the
2189 equivalent replacement. */
2192 adjust_cleared_regs (rtx loc, const_rtx old_rtx ATTRIBUTE_UNUSED, void *data)
2196 bitmap cleared_regs = (bitmap) data;
2197 if (bitmap_bit_p (cleared_regs, REGNO (loc)))
2198 return simplify_replace_fn_rtx (*reg_equiv[REGNO (loc)].src_p,
2199 NULL_RTX, adjust_cleared_regs, data);
2204 /* Nonzero if we recorded an equivalence for a LABEL_REF. */
2205 static int recorded_label_ref;
2207 /* Find registers that are equivalent to a single value throughout the
2208 compilation (either because they can be referenced in memory or are set once
2209 from a single constant). Lower their priority for a register.
2211 If such a register is only referenced once, try substituting its value
2212 into the using insn. If it succeeds, we can eliminate the register
2215 Initialize the REG_EQUIV_INIT array of initializing insns.
2217 Return non-zero if jump label rebuilding should be done. */
2219 update_equiv_regs (void)
2224 bitmap cleared_regs;
2226 /* We need to keep track of whether or not we recorded a LABEL_REF so
2227 that we know if the jump optimizer needs to be rerun. */
2228 recorded_label_ref = 0;
2230 reg_equiv = XCNEWVEC (struct equivalence, max_regno);
2231 reg_equiv_init = ggc_alloc_cleared_vec_rtx (max_regno);
2232 reg_equiv_init_size = max_regno;
2234 init_alias_analysis ();
2236 /* Scan the insns and find which registers have equivalences. Do this
2237 in a separate scan of the insns because (due to -fcse-follow-jumps)
2238 a register can be set below its use. */
2241 loop_depth = bb->loop_depth;
2243 for (insn = BB_HEAD (bb);
2244 insn != NEXT_INSN (BB_END (bb));
2245 insn = NEXT_INSN (insn))
2252 if (! INSN_P (insn))
2255 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2256 if (REG_NOTE_KIND (note) == REG_INC)
2257 no_equiv (XEXP (note, 0), note, NULL);
2259 set = single_set (insn);
2261 /* If this insn contains more (or less) than a single SET,
2262 only mark all destinations as having no known equivalence. */
2265 note_stores (PATTERN (insn), no_equiv, NULL);
2268 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2272 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
2274 rtx part = XVECEXP (PATTERN (insn), 0, i);
2276 note_stores (part, no_equiv, NULL);
2280 dest = SET_DEST (set);
2281 src = SET_SRC (set);
2283 /* See if this is setting up the equivalence between an argument
2284 register and its stack slot. */
2285 note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
2288 gcc_assert (REG_P (dest));
2289 regno = REGNO (dest);
2291 /* Note that we don't want to clear reg_equiv_init even if there
2292 are multiple sets of this register. */
2293 reg_equiv[regno].is_arg_equivalence = 1;
2295 /* Record for reload that this is an equivalencing insn. */
2296 if (rtx_equal_p (src, XEXP (note, 0)))
2297 reg_equiv_init[regno]
2298 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init[regno]);
2300 /* Continue normally in case this is a candidate for
2307 /* We only handle the case of a pseudo register being set
2308 once, or always to the same value. */
2309 /* ??? The mn10200 port breaks if we add equivalences for
2310 values that need an ADDRESS_REGS register and set them equivalent
2311 to a MEM of a pseudo. The actual problem is in the over-conservative
2312 handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
2313 calculate_needs, but we traditionally work around this problem
2314 here by rejecting equivalences when the destination is in a register
2315 that's likely spilled. This is fragile, of course, since the
2316 preferred class of a pseudo depends on all instructions that set
2320 || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER
2321 || reg_equiv[regno].init_insns == const0_rtx
2322 || (CLASS_LIKELY_SPILLED_P (reg_preferred_class (regno))
2323 && MEM_P (src) && ! reg_equiv[regno].is_arg_equivalence))
2325 /* This might be setting a SUBREG of a pseudo, a pseudo that is
2326 also set somewhere else to a constant. */
2327 note_stores (set, no_equiv, NULL);
2331 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
2333 /* cse sometimes generates function invariants, but doesn't put a
2334 REG_EQUAL note on the insn. Since this note would be redundant,
2335 there's no point creating it earlier than here. */
2336 if (! note && ! rtx_varies_p (src, 0))
2337 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
2339 /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
2340 since it represents a function call */
2341 if (note && GET_CODE (XEXP (note, 0)) == EXPR_LIST)
2344 if (DF_REG_DEF_COUNT (regno) != 1
2346 || rtx_varies_p (XEXP (note, 0), 0)
2347 || (reg_equiv[regno].replacement
2348 && ! rtx_equal_p (XEXP (note, 0),
2349 reg_equiv[regno].replacement))))
2351 no_equiv (dest, set, NULL);
2354 /* Record this insn as initializing this register. */
2355 reg_equiv[regno].init_insns
2356 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv[regno].init_insns);
2358 /* If this register is known to be equal to a constant, record that
2359 it is always equivalent to the constant. */
2360 if (DF_REG_DEF_COUNT (regno) == 1
2361 && note && ! rtx_varies_p (XEXP (note, 0), 0))
2363 rtx note_value = XEXP (note, 0);
2364 remove_note (insn, note);
2365 set_unique_reg_note (insn, REG_EQUIV, note_value);
2368 /* If this insn introduces a "constant" register, decrease the priority
2369 of that register. Record this insn if the register is only used once
2370 more and the equivalence value is the same as our source.
2372 The latter condition is checked for two reasons: First, it is an
2373 indication that it may be more efficient to actually emit the insn
2374 as written (if no registers are available, reload will substitute
2375 the equivalence). Secondly, it avoids problems with any registers
2376 dying in this insn whose death notes would be missed.
2378 If we don't have a REG_EQUIV note, see if this insn is loading
2379 a register used only in one basic block from a MEM. If so, and the
2380 MEM remains unchanged for the life of the register, add a REG_EQUIV
2383 note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
2385 if (note == 0 && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
2386 && MEM_P (SET_SRC (set))
2387 && validate_equiv_mem (insn, dest, SET_SRC (set)))
2388 note = set_unique_reg_note (insn, REG_EQUIV, copy_rtx (SET_SRC (set)));
2392 int regno = REGNO (dest);
2393 rtx x = XEXP (note, 0);
2395 /* If we haven't done so, record for reload that this is an
2396 equivalencing insn. */
2397 if (!reg_equiv[regno].is_arg_equivalence)
2398 reg_equiv_init[regno]
2399 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init[regno]);
2401 /* Record whether or not we created a REG_EQUIV note for a LABEL_REF.
2402 We might end up substituting the LABEL_REF for uses of the
2403 pseudo here or later. That kind of transformation may turn an
2404 indirect jump into a direct jump, in which case we must rerun the
2405 jump optimizer to ensure that the JUMP_LABEL fields are valid. */
2406 if (GET_CODE (x) == LABEL_REF
2407 || (GET_CODE (x) == CONST
2408 && GET_CODE (XEXP (x, 0)) == PLUS
2409 && (GET_CODE (XEXP (XEXP (x, 0), 0)) == LABEL_REF)))
2410 recorded_label_ref = 1;
2412 reg_equiv[regno].replacement = x;
2413 reg_equiv[regno].src_p = &SET_SRC (set);
2414 reg_equiv[regno].loop_depth = loop_depth;
2416 /* Don't mess with things live during setjmp. */
2417 if (REG_LIVE_LENGTH (regno) >= 0 && optimize)
2419 /* Note that the statement below does not affect the priority
2421 REG_LIVE_LENGTH (regno) *= 2;
2423 /* If the register is referenced exactly twice, meaning it is
2424 set once and used once, indicate that the reference may be
2425 replaced by the equivalence we computed above. Do this
2426 even if the register is only used in one block so that
2427 dependencies can be handled where the last register is
2428 used in a different block (i.e. HIGH / LO_SUM sequences)
2429 and to reduce the number of registers alive across
2432 if (REG_N_REFS (regno) == 2
2433 && (rtx_equal_p (x, src)
2434 || ! equiv_init_varies_p (src))
2435 && NONJUMP_INSN_P (insn)
2436 && equiv_init_movable_p (PATTERN (insn), regno))
2437 reg_equiv[regno].replace = 1;
2446 /* A second pass, to gather additional equivalences with memory. This needs
2447 to be done after we know which registers we are going to replace. */
2449 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2454 if (! INSN_P (insn))
2457 set = single_set (insn);
2461 dest = SET_DEST (set);
2462 src = SET_SRC (set);
2464 /* If this sets a MEM to the contents of a REG that is only used
2465 in a single basic block, see if the register is always equivalent
2466 to that memory location and if moving the store from INSN to the
2467 insn that set REG is safe. If so, put a REG_EQUIV note on the
2470 Don't add a REG_EQUIV note if the insn already has one. The existing
2471 REG_EQUIV is likely more useful than the one we are adding.
2473 If one of the regs in the address has reg_equiv[REGNO].replace set,
2474 then we can't add this REG_EQUIV note. The reg_equiv[REGNO].replace
2475 optimization may move the set of this register immediately before
2476 insn, which puts it after reg_equiv[REGNO].init_insns, and hence
2477 the mention in the REG_EQUIV note would be to an uninitialized
2480 if (MEM_P (dest) && REG_P (src)
2481 && (regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
2482 && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
2483 && DF_REG_DEF_COUNT (regno) == 1
2484 && reg_equiv[regno].init_insns != 0
2485 && reg_equiv[regno].init_insns != const0_rtx
2486 && ! find_reg_note (XEXP (reg_equiv[regno].init_insns, 0),
2487 REG_EQUIV, NULL_RTX)
2488 && ! contains_replace_regs (XEXP (dest, 0)))
2490 rtx init_insn = XEXP (reg_equiv[regno].init_insns, 0);
2491 if (validate_equiv_mem (init_insn, src, dest)
2492 && ! memref_used_between_p (dest, init_insn, insn)
2493 /* Attaching a REG_EQUIV note will fail if INIT_INSN has
2495 && set_unique_reg_note (init_insn, REG_EQUIV, copy_rtx (dest)))
2497 /* This insn makes the equivalence, not the one initializing
2499 reg_equiv_init[regno]
2500 = gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
2501 df_notes_rescan (init_insn);
2506 cleared_regs = BITMAP_ALLOC (NULL);
2507 /* Now scan all regs killed in an insn to see if any of them are
2508 registers only used that once. If so, see if we can replace the
2509 reference with the equivalent form. If we can, delete the
2510 initializing reference and this register will go away. If we
2511 can't replace the reference, and the initializing reference is
2512 within the same loop (or in an inner loop), then move the register
2513 initialization just before the use, so that they are in the same
2515 FOR_EACH_BB_REVERSE (bb)
2517 loop_depth = bb->loop_depth;
2518 for (insn = BB_END (bb);
2519 insn != PREV_INSN (BB_HEAD (bb));
2520 insn = PREV_INSN (insn))
2524 if (! INSN_P (insn))
2527 /* Don't substitute into a non-local goto, this confuses CFG. */
2529 && find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
2532 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2534 if (REG_NOTE_KIND (link) == REG_DEAD
2535 /* Make sure this insn still refers to the register. */
2536 && reg_mentioned_p (XEXP (link, 0), PATTERN (insn)))
2538 int regno = REGNO (XEXP (link, 0));
2541 if (! reg_equiv[regno].replace
2542 || reg_equiv[regno].loop_depth < loop_depth)
2545 /* reg_equiv[REGNO].replace gets set only when
2546 REG_N_REFS[REGNO] is 2, i.e. the register is set
2547 once and used once. (If it were only set, but not used,
2548 flow would have deleted the setting insns.) Hence
2549 there can only be one insn in reg_equiv[REGNO].init_insns. */
2550 gcc_assert (reg_equiv[regno].init_insns
2551 && !XEXP (reg_equiv[regno].init_insns, 1));
2552 equiv_insn = XEXP (reg_equiv[regno].init_insns, 0);
2554 /* We may not move instructions that can throw, since
2555 that changes basic block boundaries and we are not
2556 prepared to adjust the CFG to match. */
2557 if (can_throw_internal (equiv_insn))
2560 if (asm_noperands (PATTERN (equiv_insn)) < 0
2561 && validate_replace_rtx (regno_reg_rtx[regno],
2562 *(reg_equiv[regno].src_p), insn))
2568 /* Find the last note. */
2569 for (last_link = link; XEXP (last_link, 1);
2570 last_link = XEXP (last_link, 1))
2573 /* Append the REG_DEAD notes from equiv_insn. */
2574 equiv_link = REG_NOTES (equiv_insn);
2578 equiv_link = XEXP (equiv_link, 1);
2579 if (REG_NOTE_KIND (note) == REG_DEAD)
2581 remove_note (equiv_insn, note);
2582 XEXP (last_link, 1) = note;
2583 XEXP (note, 1) = NULL_RTX;
2588 remove_death (regno, insn);
2589 SET_REG_N_REFS (regno, 0);
2590 REG_FREQ (regno) = 0;
2591 delete_insn (equiv_insn);
2593 reg_equiv[regno].init_insns
2594 = XEXP (reg_equiv[regno].init_insns, 1);
2596 reg_equiv_init[regno] = NULL_RTX;
2597 bitmap_set_bit (cleared_regs, regno);
2599 /* Move the initialization of the register to just before
2600 INSN. Update the flow information. */
2601 else if (prev_nondebug_insn (insn) != equiv_insn)
2605 new_insn = emit_insn_before (PATTERN (equiv_insn), insn);
2606 REG_NOTES (new_insn) = REG_NOTES (equiv_insn);
2607 REG_NOTES (equiv_insn) = 0;
2608 /* Rescan it to process the notes. */
2609 df_insn_rescan (new_insn);
2611 /* Make sure this insn is recognized before
2612 reload begins, otherwise
2613 eliminate_regs_in_insn will die. */
2614 INSN_CODE (new_insn) = INSN_CODE (equiv_insn);
2616 delete_insn (equiv_insn);
2618 XEXP (reg_equiv[regno].init_insns, 0) = new_insn;
2620 REG_BASIC_BLOCK (regno) = bb->index;
2621 REG_N_CALLS_CROSSED (regno) = 0;
2622 REG_FREQ_CALLS_CROSSED (regno) = 0;
2623 REG_N_THROWING_CALLS_CROSSED (regno) = 0;
2624 REG_LIVE_LENGTH (regno) = 2;
2626 if (insn == BB_HEAD (bb))
2627 BB_HEAD (bb) = PREV_INSN (insn);
2629 reg_equiv_init[regno]
2630 = gen_rtx_INSN_LIST (VOIDmode, new_insn, NULL_RTX);
2631 bitmap_set_bit (cleared_regs, regno);
2638 if (!bitmap_empty_p (cleared_regs))
2642 bitmap_and_compl_into (DF_LIVE_IN (bb), cleared_regs);
2643 bitmap_and_compl_into (DF_LIVE_OUT (bb), cleared_regs);
2644 bitmap_and_compl_into (DF_LR_IN (bb), cleared_regs);
2645 bitmap_and_compl_into (DF_LR_OUT (bb), cleared_regs);
2648 /* Last pass - adjust debug insns referencing cleared regs. */
2649 if (MAY_HAVE_DEBUG_INSNS)
2650 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2651 if (DEBUG_INSN_P (insn))
2653 rtx old_loc = INSN_VAR_LOCATION_LOC (insn);
2654 INSN_VAR_LOCATION_LOC (insn)
2655 = simplify_replace_fn_rtx (old_loc, NULL_RTX,
2656 adjust_cleared_regs,
2657 (void *) cleared_regs);
2658 if (old_loc != INSN_VAR_LOCATION_LOC (insn))
2659 df_insn_rescan (insn);
2663 BITMAP_FREE (cleared_regs);
2668 end_alias_analysis ();
2670 return recorded_label_ref;
2675 /* Print chain C to FILE. */
2677 print_insn_chain (FILE *file, struct insn_chain *c)
2679 fprintf (file, "insn=%d, ", INSN_UID(c->insn));
2680 bitmap_print (file, &c->live_throughout, "live_throughout: ", ", ");
2681 bitmap_print (file, &c->dead_or_set, "dead_or_set: ", "\n");
2685 /* Print all reload_insn_chains to FILE. */
2687 print_insn_chains (FILE *file)
2689 struct insn_chain *c;
2690 for (c = reload_insn_chain; c ; c = c->next)
2691 print_insn_chain (file, c);
2694 /* Return true if pseudo REGNO should be added to set live_throughout
2695 or dead_or_set of the insn chains for reload consideration. */
2697 pseudo_for_reload_consideration_p (int regno)
2699 /* Consider spilled pseudos too for IRA because they still have a
2700 chance to get hard-registers in the reload when IRA is used. */
2701 return (reg_renumber[regno] >= 0
2702 || (ira_conflicts_p && flag_ira_share_spill_slots));
2705 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
2706 REG to the number of nregs, and INIT_VALUE to get the
2707 initialization. ALLOCNUM need not be the regno of REG. */
2709 init_live_subregs (bool init_value, sbitmap *live_subregs,
2710 int *live_subregs_used, int allocnum, rtx reg)
2712 unsigned int regno = REGNO (SUBREG_REG (reg));
2713 int size = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno]));
2715 gcc_assert (size > 0);
2717 /* Been there, done that. */
2718 if (live_subregs_used[allocnum])
2721 /* Create a new one with zeros. */
2722 if (live_subregs[allocnum] == NULL)
2723 live_subregs[allocnum] = sbitmap_alloc (size);
2725 /* If the entire reg was live before blasting into subregs, we need
2726 to init all of the subregs to ones else init to 0. */
2728 sbitmap_ones (live_subregs[allocnum]);
2730 sbitmap_zero (live_subregs[allocnum]);
2732 /* Set the number of bits that we really want. */
2733 live_subregs_used[allocnum] = size;
2736 /* Walk the insns of the current function and build reload_insn_chain,
2737 and record register life information. */
2739 build_insn_chain (void)
2742 struct insn_chain **p = &reload_insn_chain;
2744 struct insn_chain *c = NULL;
2745 struct insn_chain *next = NULL;
2746 bitmap live_relevant_regs = BITMAP_ALLOC (NULL);
2747 bitmap elim_regset = BITMAP_ALLOC (NULL);
2748 /* live_subregs is a vector used to keep accurate information about
2749 which hardregs are live in multiword pseudos. live_subregs and
2750 live_subregs_used are indexed by pseudo number. The live_subreg
2751 entry for a particular pseudo is only used if the corresponding
2752 element is non zero in live_subregs_used. The value in
2753 live_subregs_used is number of bytes that the pseudo can
2755 sbitmap *live_subregs = XCNEWVEC (sbitmap, max_regno);
2756 int *live_subregs_used = XNEWVEC (int, max_regno);
2758 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2759 if (TEST_HARD_REG_BIT (eliminable_regset, i))
2760 bitmap_set_bit (elim_regset, i);
2761 FOR_EACH_BB_REVERSE (bb)
2766 CLEAR_REG_SET (live_relevant_regs);
2767 memset (live_subregs_used, 0, max_regno * sizeof (int));
2769 EXECUTE_IF_SET_IN_BITMAP (DF_LR_OUT (bb), 0, i, bi)
2771 if (i >= FIRST_PSEUDO_REGISTER)
2773 bitmap_set_bit (live_relevant_regs, i);
2776 EXECUTE_IF_SET_IN_BITMAP (DF_LR_OUT (bb),
2777 FIRST_PSEUDO_REGISTER, i, bi)
2779 if (pseudo_for_reload_consideration_p (i))
2780 bitmap_set_bit (live_relevant_regs, i);
2783 FOR_BB_INSNS_REVERSE (bb, insn)
2785 if (!NOTE_P (insn) && !BARRIER_P (insn))
2787 unsigned int uid = INSN_UID (insn);
2791 c = new_insn_chain ();
2798 c->block = bb->index;
2801 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
2803 df_ref def = *def_rec;
2804 unsigned int regno = DF_REF_REGNO (def);
2806 /* Ignore may clobbers because these are generated
2807 from calls. However, every other kind of def is
2808 added to dead_or_set. */
2809 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
2811 if (regno < FIRST_PSEUDO_REGISTER)
2813 if (!fixed_regs[regno])
2814 bitmap_set_bit (&c->dead_or_set, regno);
2816 else if (pseudo_for_reload_consideration_p (regno))
2817 bitmap_set_bit (&c->dead_or_set, regno);
2820 if ((regno < FIRST_PSEUDO_REGISTER
2821 || reg_renumber[regno] >= 0
2823 && (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)))
2825 rtx reg = DF_REF_REG (def);
2827 /* We can model subregs, but not if they are
2828 wrapped in ZERO_EXTRACTS. */
2829 if (GET_CODE (reg) == SUBREG
2830 && !DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT))
2832 unsigned int start = SUBREG_BYTE (reg);
2833 unsigned int last = start
2834 + GET_MODE_SIZE (GET_MODE (reg));
2837 (bitmap_bit_p (live_relevant_regs, regno),
2838 live_subregs, live_subregs_used, regno, reg);
2840 if (!DF_REF_FLAGS_IS_SET
2841 (def, DF_REF_STRICT_LOW_PART))
2843 /* Expand the range to cover entire words.
2844 Bytes added here are "don't care". */
2846 = start / UNITS_PER_WORD * UNITS_PER_WORD;
2847 last = ((last + UNITS_PER_WORD - 1)
2848 / UNITS_PER_WORD * UNITS_PER_WORD);
2851 /* Ignore the paradoxical bits. */
2852 if ((int)last > live_subregs_used[regno])
2853 last = live_subregs_used[regno];
2855 while (start < last)
2857 RESET_BIT (live_subregs[regno], start);
2861 if (sbitmap_empty_p (live_subregs[regno]))
2863 live_subregs_used[regno] = 0;
2864 bitmap_clear_bit (live_relevant_regs, regno);
2867 /* Set live_relevant_regs here because
2868 that bit has to be true to get us to
2869 look at the live_subregs fields. */
2870 bitmap_set_bit (live_relevant_regs, regno);
2874 /* DF_REF_PARTIAL is generated for
2875 subregs, STRICT_LOW_PART, and
2876 ZERO_EXTRACT. We handle the subreg
2877 case above so here we have to keep from
2878 modeling the def as a killing def. */
2879 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL))
2881 bitmap_clear_bit (live_relevant_regs, regno);
2882 live_subregs_used[regno] = 0;
2888 bitmap_and_compl_into (live_relevant_regs, elim_regset);
2889 bitmap_copy (&c->live_throughout, live_relevant_regs);
2892 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
2894 df_ref use = *use_rec;
2895 unsigned int regno = DF_REF_REGNO (use);
2896 rtx reg = DF_REF_REG (use);
2898 /* DF_REF_READ_WRITE on a use means that this use
2899 is fabricated from a def that is a partial set
2900 to a multiword reg. Here, we only model the
2901 subreg case that is not wrapped in ZERO_EXTRACT
2902 precisely so we do not need to look at the
2904 if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE)
2905 && !DF_REF_FLAGS_IS_SET (use, DF_REF_ZERO_EXTRACT)
2906 && DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG))
2909 /* Add the last use of each var to dead_or_set. */
2910 if (!bitmap_bit_p (live_relevant_regs, regno))
2912 if (regno < FIRST_PSEUDO_REGISTER)
2914 if (!fixed_regs[regno])
2915 bitmap_set_bit (&c->dead_or_set, regno);
2917 else if (pseudo_for_reload_consideration_p (regno))
2918 bitmap_set_bit (&c->dead_or_set, regno);
2921 if (regno < FIRST_PSEUDO_REGISTER
2922 || pseudo_for_reload_consideration_p (regno))
2924 if (GET_CODE (reg) == SUBREG
2925 && !DF_REF_FLAGS_IS_SET (use,
2927 | DF_REF_ZERO_EXTRACT))
2929 unsigned int start = SUBREG_BYTE (reg);
2930 unsigned int last = start
2931 + GET_MODE_SIZE (GET_MODE (reg));
2934 (bitmap_bit_p (live_relevant_regs, regno),
2935 live_subregs, live_subregs_used, regno, reg);
2937 /* Ignore the paradoxical bits. */
2938 if ((int)last > live_subregs_used[regno])
2939 last = live_subregs_used[regno];
2941 while (start < last)
2943 SET_BIT (live_subregs[regno], start);
2948 /* Resetting the live_subregs_used is
2949 effectively saying do not use the subregs
2950 because we are reading the whole
2952 live_subregs_used[regno] = 0;
2953 bitmap_set_bit (live_relevant_regs, regno);
2959 /* FIXME!! The following code is a disaster. Reload needs to see the
2960 labels and jump tables that are just hanging out in between
2961 the basic blocks. See pr33676. */
2962 insn = BB_HEAD (bb);
2964 /* Skip over the barriers and cruft. */
2965 while (insn && (BARRIER_P (insn) || NOTE_P (insn)
2966 || BLOCK_FOR_INSN (insn) == bb))
2967 insn = PREV_INSN (insn);
2969 /* While we add anything except barriers and notes, the focus is
2970 to get the labels and jump tables into the
2971 reload_insn_chain. */
2974 if (!NOTE_P (insn) && !BARRIER_P (insn))
2976 if (BLOCK_FOR_INSN (insn))
2979 c = new_insn_chain ();
2985 /* The block makes no sense here, but it is what the old
2987 c->block = bb->index;
2989 bitmap_copy (&c->live_throughout, live_relevant_regs);
2991 insn = PREV_INSN (insn);
2995 for (i = 0; i < (unsigned int) max_regno; i++)
2996 if (live_subregs[i])
2997 free (live_subregs[i]);
2999 reload_insn_chain = c;
3002 free (live_subregs);
3003 free (live_subregs_used);
3004 BITMAP_FREE (live_relevant_regs);
3005 BITMAP_FREE (elim_regset);
3008 print_insn_chains (dump_file);
3011 /* Allocate memory for reg_equiv_memory_loc. */
3013 init_reg_equiv_memory_loc (void)
3015 max_regno = max_reg_num ();
3017 /* And the reg_equiv_memory_loc array. */
3018 VEC_safe_grow (rtx, gc, reg_equiv_memory_loc_vec, max_regno);
3019 memset (VEC_address (rtx, reg_equiv_memory_loc_vec), 0,
3020 sizeof (rtx) * max_regno);
3021 reg_equiv_memory_loc = VEC_address (rtx, reg_equiv_memory_loc_vec);
3024 /* All natural loops. */
3025 struct loops ira_loops;
3027 /* True if we have allocno conflicts. It is false for non-optimized
3028 mode or when the conflict table is too big. */
3029 bool ira_conflicts_p;
3031 /* This is the main entry of IRA. */
3035 int overall_cost_before, allocated_reg_info_size;
3037 int max_regno_before_ira, ira_max_point_before_emit;
3039 int saved_flag_ira_share_spill_slots;
3042 timevar_push (TV_IRA);
3044 if (flag_caller_saves)
3045 init_caller_save ();
3047 if (flag_ira_verbose < 10)
3049 internal_flag_ira_verbose = flag_ira_verbose;
3054 internal_flag_ira_verbose = flag_ira_verbose - 10;
3055 ira_dump_file = stderr;
3058 ira_conflicts_p = optimize > 0;
3059 setup_prohibited_mode_move_regs ();
3061 df_note_add_problem ();
3065 df_live_add_problem ();
3066 df_live_set_all_dirty ();
3068 #ifdef ENABLE_CHECKING
3069 df->changeable_flags |= DF_VERIFY_SCHEDULED;
3072 df_clear_flags (DF_NO_INSN_RESCAN);
3073 regstat_init_n_sets_and_refs ();
3074 regstat_compute_ri ();
3076 /* If we are not optimizing, then this is the only place before
3077 register allocation where dataflow is done. And that is needed
3078 to generate these warnings. */
3080 generate_setjmp_warnings ();
3082 /* Determine if the current function is a leaf before running IRA
3083 since this can impact optimizations done by the prologue and
3084 epilogue thus changing register elimination offsets. */
3085 current_function_is_leaf = leaf_function_p ();
3087 if (resize_reg_info () && flag_ira_loop_pressure)
3088 ira_set_pseudo_classes (ira_dump_file);
3090 rebuild_p = update_equiv_regs ();
3092 #ifndef IRA_NO_OBSTACK
3093 gcc_obstack_init (&ira_obstack);
3095 bitmap_obstack_initialize (&ira_bitmap_obstack);
3098 max_regno = max_reg_num ();
3099 ira_reg_equiv_len = max_regno;
3100 ira_reg_equiv_invariant_p
3101 = (bool *) ira_allocate (max_regno * sizeof (bool));
3102 memset (ira_reg_equiv_invariant_p, 0, max_regno * sizeof (bool));
3103 ira_reg_equiv_const = (rtx *) ira_allocate (max_regno * sizeof (rtx));
3104 memset (ira_reg_equiv_const, 0, max_regno * sizeof (rtx));
3105 find_reg_equiv_invariant_const ();
3108 timevar_push (TV_JUMP);
3109 rebuild_jump_labels (get_insns ());
3110 purge_all_dead_edges ();
3111 timevar_pop (TV_JUMP);
3115 max_regno_before_ira = allocated_reg_info_size = max_reg_num ();
3116 ira_setup_eliminable_regset ();
3118 ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
3119 ira_load_cost = ira_store_cost = ira_shuffle_cost = 0;
3120 ira_move_loops_num = ira_additional_jumps_num = 0;
3122 ira_assert (current_loops == NULL);
3123 flow_loops_find (&ira_loops);
3124 record_loop_exits ();
3125 current_loops = &ira_loops;
3127 init_reg_equiv_memory_loc ();
3129 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3130 fprintf (ira_dump_file, "Building IRA IR\n");
3131 loops_p = ira_build (optimize
3132 && (flag_ira_region == IRA_REGION_ALL
3133 || flag_ira_region == IRA_REGION_MIXED));
3135 ira_assert (ira_conflicts_p || !loops_p);
3137 saved_flag_ira_share_spill_slots = flag_ira_share_spill_slots;
3138 if (too_high_register_pressure_p ())
3139 /* It is just wasting compiler's time to pack spilled pseudos into
3140 stack slots in this case -- prohibit it. */
3141 flag_ira_share_spill_slots = FALSE;
3145 ira_max_point_before_emit = ira_max_point;
3149 if (ira_conflicts_p)
3151 max_regno = max_reg_num ();
3154 ira_initiate_assign ();
3157 expand_reg_info (allocated_reg_info_size);
3158 setup_preferred_alternate_classes_for_new_pseudos
3159 (allocated_reg_info_size);
3160 allocated_reg_info_size = max_regno;
3162 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3163 fprintf (ira_dump_file, "Flattening IR\n");
3164 ira_flattening (max_regno_before_ira, ira_max_point_before_emit);
3165 /* New insns were generated: add notes and recalculate live
3169 flow_loops_find (&ira_loops);
3170 record_loop_exits ();
3171 current_loops = &ira_loops;
3173 setup_allocno_assignment_flags ();
3174 ira_initiate_assign ();
3175 ira_reassign_conflict_allocnos (max_regno);
3179 setup_reg_renumber ();
3181 calculate_allocation_cost ();
3183 #ifdef ENABLE_IRA_CHECKING
3184 if (ira_conflicts_p)
3185 check_allocation ();
3188 delete_trivially_dead_insns (get_insns (), max_reg_num ());
3190 init_reg_equiv_memory_loc ();
3192 if (max_regno != max_regno_before_ira)
3194 regstat_free_n_sets_and_refs ();
3196 regstat_init_n_sets_and_refs ();
3197 regstat_compute_ri ();
3200 allocate_initial_values (reg_equiv_memory_loc);
3202 overall_cost_before = ira_overall_cost;
3203 if (ira_conflicts_p)
3205 fix_reg_equiv_init ();
3207 #ifdef ENABLE_IRA_CHECKING
3208 print_redundant_copies ();
3211 ira_spilled_reg_stack_slots_num = 0;
3212 ira_spilled_reg_stack_slots
3213 = ((struct ira_spilled_reg_stack_slot *)
3214 ira_allocate (max_regno
3215 * sizeof (struct ira_spilled_reg_stack_slot)));
3216 memset (ira_spilled_reg_stack_slots, 0,
3217 max_regno * sizeof (struct ira_spilled_reg_stack_slot));
3220 timevar_pop (TV_IRA);
3222 timevar_push (TV_RELOAD);
3223 df_set_flags (DF_NO_INSN_RESCAN);
3224 build_insn_chain ();
3226 reload_completed = !reload (get_insns (), ira_conflicts_p);
3228 finish_subregs_of_mode ();
3230 timevar_pop (TV_RELOAD);
3232 timevar_push (TV_IRA);
3234 if (ira_conflicts_p)
3236 ira_free (ira_spilled_reg_stack_slots);
3238 ira_finish_assign ();
3241 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL
3242 && overall_cost_before != ira_overall_cost)
3243 fprintf (ira_dump_file, "+++Overall after reload %d\n", ira_overall_cost);
3246 flag_ira_share_spill_slots = saved_flag_ira_share_spill_slots;
3248 flow_loops_free (&ira_loops);
3249 free_dominance_info (CDI_DOMINATORS);
3251 bb->loop_father = NULL;
3252 current_loops = NULL;
3255 regstat_free_n_sets_and_refs ();
3259 cleanup_cfg (CLEANUP_EXPENSIVE);
3261 ira_free (ira_reg_equiv_invariant_p);
3262 ira_free (ira_reg_equiv_const);
3265 bitmap_obstack_release (&ira_bitmap_obstack);
3266 #ifndef IRA_NO_OBSTACK
3267 obstack_free (&ira_obstack, NULL);
3270 /* The code after the reload has changed so much that at this point
3271 we might as well just rescan everything. Not that
3272 df_rescan_all_insns is not going to help here because it does not
3273 touch the artificial uses and defs. */
3274 df_finish_pass (true);
3276 df_live_add_problem ();
3277 df_scan_alloc (NULL);
3283 timevar_pop (TV_IRA);
3294 /* Run the integrated register allocator. */
3296 rest_of_handle_ira (void)
3302 struct rtl_opt_pass pass_ira =
3307 gate_ira, /* gate */
3308 rest_of_handle_ira, /* execute */
3311 0, /* static_pass_number */
3312 TV_NONE, /* tv_id */
3313 0, /* properties_required */
3314 0, /* properties_provided */
3315 0, /* properties_destroyed */
3316 0, /* todo_flags_start */
3318 TODO_ggc_collect /* todo_flags_finish */