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 * Putting allocnos onto the coloring stack. IRA uses Briggs
172 optimistic coloring which is a major improvement over
173 Chaitin's coloring. Therefore IRA does not spill allocnos at
174 this point. There is some freedom in the order of putting
175 allocnos on the stack which can affect the final result of
176 the allocation. IRA uses some heuristics to improve the order.
178 * Popping the allocnos from the stack and assigning them hard
179 registers. If IRA can not assign a hard register to an
180 allocno and the allocno is coalesced, IRA undoes the
181 coalescing and puts the uncoalesced allocnos onto the stack in
182 the hope that some such allocnos will get a hard register
183 separately. If IRA fails to assign hard register or memory
184 is more profitable for it, IRA spills the allocno. IRA
185 assigns the allocno the hard-register with minimal full
186 allocation cost which reflects the cost of usage of the
187 hard-register for the allocno and cost of usage of the
188 hard-register for allocnos conflicting with given allocno.
190 * After allono assigning in the region, IRA modifies the hard
191 register and memory costs for the corresponding allocnos in
192 the subregions to reflect the cost of possible loads, stores,
193 or moves on the border of the region and its subregions.
194 When default regional allocation algorithm is used
195 (-fira-algorithm=mixed), IRA just propagates the assignment
196 for allocnos if the register pressure in the region for the
197 corresponding cover class is less than number of available
198 hard registers for given cover class.
200 o Spill/restore code moving. When IRA performs an allocation
201 by traversing regions in top-down order, it does not know what
202 happens below in the region tree. Therefore, sometimes IRA
203 misses opportunities to perform a better allocation. A simple
204 optimization tries to improve allocation in a region having
205 subregions and containing in another region. If the
206 corresponding allocnos in the subregion are spilled, it spills
207 the region allocno if it is profitable. The optimization
208 implements a simple iterative algorithm performing profitable
209 transformations while they are still possible. It is fast in
210 practice, so there is no real need for a better time complexity
213 o Code change. After coloring, two allocnos representing the same
214 pseudo-register outside and inside a region respectively may be
215 assigned to different locations (hard-registers or memory). In
216 this case IRA creates and uses a new pseudo-register inside the
217 region and adds code to move allocno values on the region's
218 borders. This is done during top-down traversal of the regions
219 (file ira-emit.c). In some complicated cases IRA can create a
220 new allocno to move allocno values (e.g. when a swap of values
221 stored in two hard-registers is needed). At this stage, the
222 new allocno is marked as spilled. IRA still creates the
223 pseudo-register and the moves on the region borders even when
224 both allocnos were assigned to the same hard-register. If the
225 reload pass spills a pseudo-register for some reason, the
226 effect will be smaller because another allocno will still be in
227 the hard-register. In most cases, this is better then spilling
228 both allocnos. If reload does not change the allocation
229 for the two pseudo-registers, the trivial move will be removed
230 by post-reload optimizations. IRA does not generate moves for
231 allocnos assigned to the same hard register when the default
232 regional allocation algorithm is used and the register pressure
233 in the region for the corresponding allocno cover class is less
234 than number of available hard registers for given cover class.
235 IRA also does some optimizations to remove redundant stores and
236 to reduce code duplication on the region borders.
238 o Flattening internal representation. After changing code, IRA
239 transforms its internal representation for several regions into
240 one region representation (file ira-build.c). This process is
241 called IR flattening. Such process is more complicated than IR
242 rebuilding would be, but is much faster.
244 o After IR flattening, IRA tries to assign hard registers to all
245 spilled allocnos. This is impelemented by a simple and fast
246 priority coloring algorithm (see function
247 ira_reassign_conflict_allocnos::ira-color.c). Here new allocnos
248 created during the code change pass can be assigned to hard
251 o At the end IRA calls the reload pass. The reload pass
252 communicates with IRA through several functions in file
253 ira-color.c to improve its decisions in
255 * sharing stack slots for the spilled pseudos based on IRA info
256 about pseudo-register conflicts.
258 * reassigning hard-registers to all spilled pseudos at the end
259 of each reload iteration.
261 * choosing a better hard-register to spill based on IRA info
262 about pseudo-register live ranges and the register pressure
263 in places where the pseudo-register lives.
265 IRA uses a lot of data representing the target processors. These
266 data are initilized in file ira.c.
268 If function has no loops (or the loops are ignored when
269 -fira-algorithm=CB is used), we have classic Chaitin-Briggs
270 coloring (only instead of separate pass of coalescing, we use hard
271 register preferencing). In such case, IRA works much faster
272 because many things are not made (like IR flattening, the
273 spill/restore optimization, and the code change).
275 Literature is worth to read for better understanding the code:
277 o Preston Briggs, Keith D. Cooper, Linda Torczon. Improvements to
278 Graph Coloring Register Allocation.
280 o David Callahan, Brian Koblenz. Register allocation via
281 hierarchical graph coloring.
283 o Keith Cooper, Anshuman Dasgupta, Jason Eckhardt. Revisiting Graph
284 Coloring Register Allocation: A Study of the Chaitin-Briggs and
285 Callahan-Koblenz Algorithms.
287 o Guei-Yuan Lueh, Thomas Gross, and Ali-Reza Adl-Tabatabai. Global
288 Register Allocation Based on Graph Fusion.
290 o Vladimir Makarov. The Integrated Register Allocator for GCC.
292 o Vladimir Makarov. The top-down register allocator for irregular
293 register file architectures.
300 #include "coretypes.h"
309 #include "hard-reg-set.h"
310 #include "basic-block.h"
316 #include "tree-pass.h"
320 #include "diagnostic-core.h"
321 #include "integrate.h"
326 struct target_ira default_target_ira
;
327 struct target_ira_int default_target_ira_int
;
328 #if SWITCHABLE_TARGET
329 struct target_ira
*this_target_ira
= &default_target_ira
;
330 struct target_ira_int
*this_target_ira_int
= &default_target_ira_int
;
333 /* A modified value of flag `-fira-verbose' used internally. */
334 int internal_flag_ira_verbose
;
336 /* Dump file of the allocator if it is not NULL. */
339 /* The number of elements in the following array. */
340 int ira_spilled_reg_stack_slots_num
;
342 /* The following array contains info about spilled pseudo-registers
343 stack slots used in current function so far. */
344 struct ira_spilled_reg_stack_slot
*ira_spilled_reg_stack_slots
;
346 /* Correspondingly overall cost of the allocation, cost of the
347 allocnos assigned to hard-registers, cost of the allocnos assigned
348 to memory, cost of loads, stores and register move insns generated
349 for pseudo-register live range splitting (see ira-emit.c). */
350 int ira_overall_cost
;
351 int ira_reg_cost
, ira_mem_cost
;
352 int ira_load_cost
, ira_store_cost
, ira_shuffle_cost
;
353 int ira_move_loops_num
, ira_additional_jumps_num
;
355 /* All registers that can be eliminated. */
357 HARD_REG_SET eliminable_regset
;
359 /* Temporary hard reg set used for a different calculation. */
360 static HARD_REG_SET temp_hard_regset
;
364 /* The function sets up the map IRA_REG_MODE_HARD_REGSET. */
366 setup_reg_mode_hard_regset (void)
368 int i
, m
, hard_regno
;
370 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
371 for (hard_regno
= 0; hard_regno
< FIRST_PSEUDO_REGISTER
; hard_regno
++)
373 CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset
[hard_regno
][m
]);
374 for (i
= hard_regno_nregs
[hard_regno
][m
] - 1; i
>= 0; i
--)
375 if (hard_regno
+ i
< FIRST_PSEUDO_REGISTER
)
376 SET_HARD_REG_BIT (ira_reg_mode_hard_regset
[hard_regno
][m
],
382 #define no_unit_alloc_regs \
383 (this_target_ira_int->x_no_unit_alloc_regs)
385 /* The function sets up the three arrays declared above. */
387 setup_class_hard_regs (void)
389 int cl
, i
, hard_regno
, n
;
390 HARD_REG_SET processed_hard_reg_set
;
392 ira_assert (SHRT_MAX
>= FIRST_PSEUDO_REGISTER
);
393 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
395 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
396 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
397 CLEAR_HARD_REG_SET (processed_hard_reg_set
);
398 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
400 ira_non_ordered_class_hard_regs
[cl
][i
] = -1;
401 ira_class_hard_reg_index
[cl
][i
] = -1;
403 for (n
= 0, i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
405 #ifdef REG_ALLOC_ORDER
406 hard_regno
= reg_alloc_order
[i
];
410 if (TEST_HARD_REG_BIT (processed_hard_reg_set
, hard_regno
))
412 SET_HARD_REG_BIT (processed_hard_reg_set
, hard_regno
);
413 if (! TEST_HARD_REG_BIT (temp_hard_regset
, hard_regno
))
414 ira_class_hard_reg_index
[cl
][hard_regno
] = -1;
417 ira_class_hard_reg_index
[cl
][hard_regno
] = n
;
418 ira_class_hard_regs
[cl
][n
++] = hard_regno
;
421 ira_class_hard_regs_num
[cl
] = n
;
422 for (n
= 0, i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
423 if (TEST_HARD_REG_BIT (temp_hard_regset
, i
))
424 ira_non_ordered_class_hard_regs
[cl
][n
++] = i
;
425 ira_assert (ira_class_hard_regs_num
[cl
] == n
);
429 /* Set up IRA_AVAILABLE_CLASS_REGS. */
431 setup_available_class_regs (void)
435 memset (ira_available_class_regs
, 0, sizeof (ira_available_class_regs
));
436 for (i
= 0; i
< N_REG_CLASSES
; i
++)
438 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[i
]);
439 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
440 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
441 if (TEST_HARD_REG_BIT (temp_hard_regset
, j
))
442 ira_available_class_regs
[i
]++;
446 /* Set up global variables defining info about hard registers for the
447 allocation. These depend on USE_HARD_FRAME_P whose TRUE value means
448 that we can use the hard frame pointer for the allocation. */
450 setup_alloc_regs (bool use_hard_frame_p
)
452 #ifdef ADJUST_REG_ALLOC_ORDER
453 ADJUST_REG_ALLOC_ORDER
;
455 COPY_HARD_REG_SET (no_unit_alloc_regs
, fixed_reg_set
);
456 if (! use_hard_frame_p
)
457 SET_HARD_REG_BIT (no_unit_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
458 setup_class_hard_regs ();
459 setup_available_class_regs ();
464 /* Set up IRA_MEMORY_MOVE_COST, IRA_REGISTER_MOVE_COST. */
466 setup_class_subset_and_memory_move_costs (void)
469 HARD_REG_SET temp_hard_regset2
;
471 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
472 ira_memory_move_cost
[mode
][NO_REGS
][0]
473 = ira_memory_move_cost
[mode
][NO_REGS
][1] = SHRT_MAX
;
474 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
476 if (cl
!= (int) NO_REGS
)
477 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
479 ira_memory_move_cost
[mode
][cl
][0] =
480 memory_move_cost ((enum machine_mode
) mode
,
481 (enum reg_class
) cl
, false);
482 ira_memory_move_cost
[mode
][cl
][1] =
483 memory_move_cost ((enum machine_mode
) mode
,
484 (enum reg_class
) cl
, true);
485 /* Costs for NO_REGS are used in cost calculation on the
486 1st pass when the preferred register classes are not
487 known yet. In this case we take the best scenario. */
488 if (ira_memory_move_cost
[mode
][NO_REGS
][0]
489 > ira_memory_move_cost
[mode
][cl
][0])
490 ira_memory_move_cost
[mode
][NO_REGS
][0]
491 = ira_memory_move_cost
[mode
][cl
][0];
492 if (ira_memory_move_cost
[mode
][NO_REGS
][1]
493 > ira_memory_move_cost
[mode
][cl
][1])
494 ira_memory_move_cost
[mode
][NO_REGS
][1]
495 = ira_memory_move_cost
[mode
][cl
][1];
497 for (cl2
= (int) N_REG_CLASSES
- 1; cl2
>= 0; cl2
--)
499 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
500 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
501 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl2
]);
502 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
503 ira_class_subset_p
[cl
][cl2
]
504 = hard_reg_set_subset_p (temp_hard_regset
, temp_hard_regset2
);
511 /* Define the following macro if allocation through malloc if
513 #define IRA_NO_OBSTACK
515 #ifndef IRA_NO_OBSTACK
516 /* Obstack used for storing all dynamic data (except bitmaps) of the
518 static struct obstack ira_obstack
;
521 /* Obstack used for storing all bitmaps of the IRA. */
522 static struct bitmap_obstack ira_bitmap_obstack
;
524 /* Allocate memory of size LEN for IRA data. */
526 ira_allocate (size_t len
)
530 #ifndef IRA_NO_OBSTACK
531 res
= obstack_alloc (&ira_obstack
, len
);
538 /* Reallocate memory PTR of size LEN for IRA data. */
540 ira_reallocate (void *ptr
, size_t len
)
544 #ifndef IRA_NO_OBSTACK
545 res
= obstack_alloc (&ira_obstack
, len
);
547 res
= xrealloc (ptr
, len
);
552 /* Free memory ADDR allocated for IRA data. */
554 ira_free (void *addr ATTRIBUTE_UNUSED
)
556 #ifndef IRA_NO_OBSTACK
564 /* Allocate and returns bitmap for IRA. */
566 ira_allocate_bitmap (void)
568 return BITMAP_ALLOC (&ira_bitmap_obstack
);
571 /* Free bitmap B allocated for IRA. */
573 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED
)
580 /* Output information about allocation of all allocnos (except for
581 caps) into file F. */
583 ira_print_disposition (FILE *f
)
589 fprintf (f
, "Disposition:");
590 max_regno
= max_reg_num ();
591 for (n
= 0, i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
592 for (a
= ira_regno_allocno_map
[i
];
594 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
599 fprintf (f
, " %4d:r%-4d", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
600 if ((bb
= ALLOCNO_LOOP_TREE_NODE (a
)->bb
) != NULL
)
601 fprintf (f
, "b%-3d", bb
->index
);
603 fprintf (f
, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a
)->loop
->num
);
604 if (ALLOCNO_HARD_REGNO (a
) >= 0)
605 fprintf (f
, " %3d", ALLOCNO_HARD_REGNO (a
));
612 /* Outputs information about allocation of all allocnos into
615 ira_debug_disposition (void)
617 ira_print_disposition (stderr
);
621 #define alloc_reg_class_subclasses \
622 (this_target_ira_int->x_alloc_reg_class_subclasses)
624 /* Initialize the table of subclasses of each reg class. */
626 setup_reg_subclasses (void)
629 HARD_REG_SET temp_hard_regset2
;
631 for (i
= 0; i
< N_REG_CLASSES
; i
++)
632 for (j
= 0; j
< N_REG_CLASSES
; j
++)
633 alloc_reg_class_subclasses
[i
][j
] = LIM_REG_CLASSES
;
635 for (i
= 0; i
< N_REG_CLASSES
; i
++)
637 if (i
== (int) NO_REGS
)
640 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[i
]);
641 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
642 if (hard_reg_set_empty_p (temp_hard_regset
))
644 for (j
= 0; j
< N_REG_CLASSES
; j
++)
649 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[j
]);
650 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
651 if (! hard_reg_set_subset_p (temp_hard_regset
,
654 p
= &alloc_reg_class_subclasses
[j
][0];
655 while (*p
!= LIM_REG_CLASSES
) p
++;
656 *p
= (enum reg_class
) i
;
663 /* Set the four global variables defined above. */
665 setup_cover_and_important_classes (void)
669 const reg_class_t
*cover_classes
;
670 HARD_REG_SET temp_hard_regset2
;
671 static enum reg_class classes
[LIM_REG_CLASSES
+ 1];
673 if (targetm
.ira_cover_classes
== NULL
)
674 cover_classes
= NULL
;
676 cover_classes
= targetm
.ira_cover_classes ();
677 if (cover_classes
== NULL
)
678 ira_assert (flag_ira_algorithm
== IRA_ALGORITHM_PRIORITY
);
681 for (i
= 0; (cl
= cover_classes
[i
]) != LIM_REG_CLASSES
; i
++)
682 classes
[i
] = (enum reg_class
) cl
;
683 classes
[i
] = LIM_REG_CLASSES
;
686 if (flag_ira_algorithm
== IRA_ALGORITHM_PRIORITY
)
689 for (i
= 0; i
<= LIM_REG_CLASSES
; i
++)
693 #ifdef CONSTRAINT_NUM_DEFINED_P
694 for (j
= 0; j
< CONSTRAINT__LIMIT
; j
++)
695 if ((int) REG_CLASS_FOR_CONSTRAINT ((enum constraint_num
) j
) == i
)
697 if (j
< CONSTRAINT__LIMIT
)
699 classes
[n
++] = (enum reg_class
) i
;
703 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[i
]);
704 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
705 for (j
= 0; j
< LIM_REG_CLASSES
; j
++)
709 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[j
]);
710 AND_COMPL_HARD_REG_SET (temp_hard_regset2
,
712 if (hard_reg_set_equal_p (temp_hard_regset
,
717 classes
[n
++] = (enum reg_class
) i
;
719 classes
[n
] = LIM_REG_CLASSES
;
722 ira_reg_class_cover_size
= 0;
723 for (i
= 0; (cl
= classes
[i
]) != LIM_REG_CLASSES
; i
++)
725 for (j
= 0; j
< i
; j
++)
726 if (flag_ira_algorithm
!= IRA_ALGORITHM_PRIORITY
727 && reg_classes_intersect_p ((enum reg_class
) cl
, classes
[j
]))
729 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
730 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
731 if (! hard_reg_set_empty_p (temp_hard_regset
))
732 ira_reg_class_cover
[ira_reg_class_cover_size
++] = (enum reg_class
) cl
;
734 ira_important_classes_num
= 0;
735 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
737 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
738 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
739 if (! hard_reg_set_empty_p (temp_hard_regset
))
742 for (j
= 0; j
< ira_reg_class_cover_size
; j
++)
744 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
745 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
746 COPY_HARD_REG_SET (temp_hard_regset2
,
747 reg_class_contents
[ira_reg_class_cover
[j
]]);
748 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
749 if ((enum reg_class
) cl
== ira_reg_class_cover
[j
]
750 || hard_reg_set_equal_p (temp_hard_regset
,
753 else if (hard_reg_set_subset_p (temp_hard_regset
,
757 if (set_p
&& j
>= ira_reg_class_cover_size
)
758 ira_important_classes
[ira_important_classes_num
++]
759 = (enum reg_class
) cl
;
762 for (j
= 0; j
< ira_reg_class_cover_size
; j
++)
763 ira_important_classes
[ira_important_classes_num
++]
764 = ira_reg_class_cover
[j
];
767 /* Set up array IRA_CLASS_TRANSLATE. */
769 setup_class_translate (void)
772 enum reg_class cover_class
, best_class
, *cl_ptr
;
773 int i
, cost
, min_cost
, best_cost
;
775 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
776 ira_class_translate
[cl
] = NO_REGS
;
778 if (flag_ira_algorithm
== IRA_ALGORITHM_PRIORITY
)
779 for (cl
= 0; cl
< LIM_REG_CLASSES
; cl
++)
781 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
782 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
783 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
785 HARD_REG_SET temp_hard_regset2
;
787 cover_class
= ira_reg_class_cover
[i
];
788 COPY_HARD_REG_SET (temp_hard_regset2
,
789 reg_class_contents
[cover_class
]);
790 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
791 if (hard_reg_set_equal_p (temp_hard_regset
, temp_hard_regset2
))
792 ira_class_translate
[cl
] = cover_class
;
795 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
797 cover_class
= ira_reg_class_cover
[i
];
798 if (flag_ira_algorithm
!= IRA_ALGORITHM_PRIORITY
)
799 for (cl_ptr
= &alloc_reg_class_subclasses
[cover_class
][0];
800 (cl
= *cl_ptr
) != LIM_REG_CLASSES
;
803 if (ira_class_translate
[cl
] == NO_REGS
)
804 ira_class_translate
[cl
] = cover_class
;
805 #ifdef ENABLE_IRA_CHECKING
808 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
809 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
810 if (! hard_reg_set_empty_p (temp_hard_regset
))
815 ira_class_translate
[cover_class
] = cover_class
;
817 /* For classes which are not fully covered by a cover class (in
818 other words covered by more one cover class), use the cheapest
820 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
822 if (cl
== NO_REGS
|| ira_class_translate
[cl
] != NO_REGS
)
824 best_class
= NO_REGS
;
826 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
828 cover_class
= ira_reg_class_cover
[i
];
829 COPY_HARD_REG_SET (temp_hard_regset
,
830 reg_class_contents
[cover_class
]);
831 AND_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
832 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
833 if (! hard_reg_set_empty_p (temp_hard_regset
))
836 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
838 cost
= (ira_memory_move_cost
[mode
][cl
][0]
839 + ira_memory_move_cost
[mode
][cl
][1]);
843 if (best_class
== NO_REGS
|| best_cost
> min_cost
)
845 best_class
= cover_class
;
846 best_cost
= min_cost
;
850 ira_class_translate
[cl
] = best_class
;
854 /* Order numbers of cover classes in original target cover class
855 array, -1 for non-cover classes. This is only live during
856 reorder_important_classes. */
857 static int cover_class_order
[N_REG_CLASSES
];
859 /* The function used to sort the important classes. */
861 comp_reg_classes_func (const void *v1p
, const void *v2p
)
863 enum reg_class cl1
= *(const enum reg_class
*) v1p
;
864 enum reg_class cl2
= *(const enum reg_class
*) v2p
;
867 cl1
= ira_class_translate
[cl1
];
868 cl2
= ira_class_translate
[cl2
];
869 if (cl1
!= NO_REGS
&& cl2
!= NO_REGS
870 && (diff
= cover_class_order
[cl1
] - cover_class_order
[cl2
]) != 0)
872 return (int) cl1
- (int) cl2
;
875 /* Reorder important classes according to the order of their cover
878 reorder_important_classes (void)
882 for (i
= 0; i
< N_REG_CLASSES
; i
++)
883 cover_class_order
[i
] = -1;
884 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
885 cover_class_order
[ira_reg_class_cover
[i
]] = i
;
886 qsort (ira_important_classes
, ira_important_classes_num
,
887 sizeof (enum reg_class
), comp_reg_classes_func
);
890 /* Set up the above reg class relations. */
892 setup_reg_class_relations (void)
894 int i
, cl1
, cl2
, cl3
;
895 HARD_REG_SET intersection_set
, union_set
, temp_set2
;
896 bool important_class_p
[N_REG_CLASSES
];
898 memset (important_class_p
, 0, sizeof (important_class_p
));
899 for (i
= 0; i
< ira_important_classes_num
; i
++)
900 important_class_p
[ira_important_classes
[i
]] = true;
901 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
903 ira_reg_class_super_classes
[cl1
][0] = LIM_REG_CLASSES
;
904 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
906 ira_reg_classes_intersect_p
[cl1
][cl2
] = false;
907 ira_reg_class_intersect
[cl1
][cl2
] = NO_REGS
;
908 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl1
]);
909 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
910 COPY_HARD_REG_SET (temp_set2
, reg_class_contents
[cl2
]);
911 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
912 if (hard_reg_set_empty_p (temp_hard_regset
)
913 && hard_reg_set_empty_p (temp_set2
))
917 cl3
= reg_class_subclasses
[cl1
][i
];
918 if (cl3
== LIM_REG_CLASSES
)
920 if (reg_class_subset_p (ira_reg_class_intersect
[cl1
][cl2
],
921 (enum reg_class
) cl3
))
922 ira_reg_class_intersect
[cl1
][cl2
] = (enum reg_class
) cl3
;
924 ira_reg_class_union
[cl1
][cl2
] = reg_class_subunion
[cl1
][cl2
];
927 ira_reg_classes_intersect_p
[cl1
][cl2
]
928 = hard_reg_set_intersect_p (temp_hard_regset
, temp_set2
);
929 if (important_class_p
[cl1
] && important_class_p
[cl2
]
930 && hard_reg_set_subset_p (temp_hard_regset
, temp_set2
))
934 p
= &ira_reg_class_super_classes
[cl1
][0];
935 while (*p
!= LIM_REG_CLASSES
)
937 *p
++ = (enum reg_class
) cl2
;
938 *p
= LIM_REG_CLASSES
;
940 ira_reg_class_union
[cl1
][cl2
] = NO_REGS
;
941 COPY_HARD_REG_SET (intersection_set
, reg_class_contents
[cl1
]);
942 AND_HARD_REG_SET (intersection_set
, reg_class_contents
[cl2
]);
943 AND_COMPL_HARD_REG_SET (intersection_set
, no_unit_alloc_regs
);
944 COPY_HARD_REG_SET (union_set
, reg_class_contents
[cl1
]);
945 IOR_HARD_REG_SET (union_set
, reg_class_contents
[cl2
]);
946 AND_COMPL_HARD_REG_SET (union_set
, no_unit_alloc_regs
);
947 for (i
= 0; i
< ira_important_classes_num
; i
++)
949 cl3
= ira_important_classes
[i
];
950 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl3
]);
951 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
952 if (hard_reg_set_subset_p (temp_hard_regset
, intersection_set
))
956 reg_class_contents
[(int)
957 ira_reg_class_intersect
[cl1
][cl2
]]);
958 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
959 if (! hard_reg_set_subset_p (temp_hard_regset
, temp_set2
)
960 /* Ignore unavailable hard registers and prefer
961 smallest class for debugging purposes. */
962 || (hard_reg_set_equal_p (temp_hard_regset
, temp_set2
)
963 && hard_reg_set_subset_p
964 (reg_class_contents
[cl3
],
966 [(int) ira_reg_class_intersect
[cl1
][cl2
]])))
967 ira_reg_class_intersect
[cl1
][cl2
] = (enum reg_class
) cl3
;
969 if (hard_reg_set_subset_p (temp_hard_regset
, union_set
))
973 reg_class_contents
[(int) ira_reg_class_union
[cl1
][cl2
]]);
974 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
975 if (ira_reg_class_union
[cl1
][cl2
] == NO_REGS
976 || (hard_reg_set_subset_p (temp_set2
, temp_hard_regset
)
978 && (! hard_reg_set_equal_p (temp_set2
,
980 /* Ignore unavailable hard registers and
981 prefer smallest class for debugging
983 || hard_reg_set_subset_p
984 (reg_class_contents
[cl3
],
986 [(int) ira_reg_class_union
[cl1
][cl2
]]))))
987 ira_reg_class_union
[cl1
][cl2
] = (enum reg_class
) cl3
;
994 /* Output all cover classes and the translation map into file F. */
996 print_class_cover (FILE *f
)
998 static const char *const reg_class_names
[] = REG_CLASS_NAMES
;
1001 fprintf (f
, "Class cover:\n");
1002 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1003 fprintf (f
, " %s", reg_class_names
[ira_reg_class_cover
[i
]]);
1004 fprintf (f
, "\nClass translation:\n");
1005 for (i
= 0; i
< N_REG_CLASSES
; i
++)
1006 fprintf (f
, " %s -> %s\n", reg_class_names
[i
],
1007 reg_class_names
[ira_class_translate
[i
]]);
1010 /* Output all cover classes and the translation map into
1013 ira_debug_class_cover (void)
1015 print_class_cover (stderr
);
1018 /* Set up different arrays concerning class subsets, cover and
1019 important classes. */
1021 find_reg_class_closure (void)
1023 setup_reg_subclasses ();
1024 setup_cover_and_important_classes ();
1025 setup_class_translate ();
1026 reorder_important_classes ();
1027 setup_reg_class_relations ();
1032 /* Set up the array above. */
1034 setup_hard_regno_cover_class (void)
1038 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1040 ira_hard_regno_cover_class
[i
]
1041 = (TEST_HARD_REG_BIT (no_unit_alloc_regs
, i
)
1043 : ira_class_translate
[REGNO_REG_CLASS (i
)]);
1049 /* Form IRA_REG_CLASS_NREGS map. */
1051 setup_reg_class_nregs (void)
1055 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1056 for (m
= 0; m
< MAX_MACHINE_MODE
; m
++)
1057 ira_reg_class_nregs
[cl
][m
] = CLASS_MAX_NREGS ((enum reg_class
) cl
,
1058 (enum machine_mode
) m
);
1063 /* Set up PROHIBITED_CLASS_MODE_REGS. */
1065 setup_prohibited_class_mode_regs (void)
1067 int i
, j
, k
, hard_regno
;
1070 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1072 cl
= ira_reg_class_cover
[i
];
1073 for (j
= 0; j
< NUM_MACHINE_MODES
; j
++)
1075 CLEAR_HARD_REG_SET (prohibited_class_mode_regs
[cl
][j
]);
1076 for (k
= ira_class_hard_regs_num
[cl
] - 1; k
>= 0; k
--)
1078 hard_regno
= ira_class_hard_regs
[cl
][k
];
1079 if (! HARD_REGNO_MODE_OK (hard_regno
, (enum machine_mode
) j
))
1080 SET_HARD_REG_BIT (prohibited_class_mode_regs
[cl
][j
],
1089 /* Allocate and initialize IRA_REGISTER_MOVE_COST,
1090 IRA_MAY_MOVE_IN_COST, and IRA_MAY_MOVE_OUT_COST for MODE if it is
1093 ira_init_register_move_cost (enum machine_mode mode
)
1097 ira_assert (ira_register_move_cost
[mode
] == NULL
1098 && ira_may_move_in_cost
[mode
] == NULL
1099 && ira_may_move_out_cost
[mode
] == NULL
);
1100 if (move_cost
[mode
] == NULL
)
1101 init_move_cost (mode
);
1102 ira_register_move_cost
[mode
] = move_cost
[mode
];
1103 /* Don't use ira_allocate because the tables exist out of scope of a
1105 ira_may_move_in_cost
[mode
]
1106 = (move_table
*) xmalloc (sizeof (move_table
) * N_REG_CLASSES
);
1107 memcpy (ira_may_move_in_cost
[mode
], may_move_in_cost
[mode
],
1108 sizeof (move_table
) * N_REG_CLASSES
);
1109 ira_may_move_out_cost
[mode
]
1110 = (move_table
*) xmalloc (sizeof (move_table
) * N_REG_CLASSES
);
1111 memcpy (ira_may_move_out_cost
[mode
], may_move_out_cost
[mode
],
1112 sizeof (move_table
) * N_REG_CLASSES
);
1113 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1115 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1117 if (ira_class_subset_p
[cl1
][cl2
])
1118 ira_may_move_in_cost
[mode
][cl1
][cl2
] = 0;
1119 if (ira_class_subset_p
[cl2
][cl1
])
1120 ira_may_move_out_cost
[mode
][cl1
][cl2
] = 0;
1127 /* This is called once during compiler work. It sets up
1128 different arrays whose values don't depend on the compiled
1131 ira_init_once (void)
1135 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
1137 ira_register_move_cost
[mode
] = NULL
;
1138 ira_may_move_in_cost
[mode
] = NULL
;
1139 ira_may_move_out_cost
[mode
] = NULL
;
1141 ira_init_costs_once ();
1144 /* Free ira_register_move_cost, ira_may_move_in_cost, and
1145 ira_may_move_out_cost for each mode. */
1147 free_register_move_costs (void)
1151 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
1153 if (ira_may_move_in_cost
[mode
] != NULL
)
1154 free (ira_may_move_in_cost
[mode
]);
1155 if (ira_may_move_out_cost
[mode
] != NULL
)
1156 free (ira_may_move_out_cost
[mode
]);
1157 ira_register_move_cost
[mode
] = NULL
;
1158 ira_may_move_in_cost
[mode
] = NULL
;
1159 ira_may_move_out_cost
[mode
] = NULL
;
1163 /* This is called every time when register related information is
1168 free_register_move_costs ();
1169 setup_reg_mode_hard_regset ();
1170 setup_alloc_regs (flag_omit_frame_pointer
!= 0);
1171 setup_class_subset_and_memory_move_costs ();
1172 find_reg_class_closure ();
1173 setup_hard_regno_cover_class ();
1174 setup_reg_class_nregs ();
1175 setup_prohibited_class_mode_regs ();
1179 /* Function called once at the end of compiler work. */
1181 ira_finish_once (void)
1183 ira_finish_costs_once ();
1184 free_register_move_costs ();
1188 #define ira_prohibited_mode_move_regs_initialized_p \
1189 (this_target_ira_int->x_ira_prohibited_mode_move_regs_initialized_p)
1191 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS. */
1193 setup_prohibited_mode_move_regs (void)
1196 rtx test_reg1
, test_reg2
, move_pat
, move_insn
;
1198 if (ira_prohibited_mode_move_regs_initialized_p
)
1200 ira_prohibited_mode_move_regs_initialized_p
= true;
1201 test_reg1
= gen_rtx_REG (VOIDmode
, 0);
1202 test_reg2
= gen_rtx_REG (VOIDmode
, 0);
1203 move_pat
= gen_rtx_SET (VOIDmode
, test_reg1
, test_reg2
);
1204 move_insn
= gen_rtx_INSN (VOIDmode
, 0, 0, 0, 0, move_pat
, 0, -1, 0);
1205 for (i
= 0; i
< NUM_MACHINE_MODES
; i
++)
1207 SET_HARD_REG_SET (ira_prohibited_mode_move_regs
[i
]);
1208 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1210 if (! HARD_REGNO_MODE_OK (j
, (enum machine_mode
) i
))
1212 SET_REGNO_RAW (test_reg1
, j
);
1213 PUT_MODE (test_reg1
, (enum machine_mode
) i
);
1214 SET_REGNO_RAW (test_reg2
, j
);
1215 PUT_MODE (test_reg2
, (enum machine_mode
) i
);
1216 INSN_CODE (move_insn
) = -1;
1217 recog_memoized (move_insn
);
1218 if (INSN_CODE (move_insn
) < 0)
1220 extract_insn (move_insn
);
1221 if (! constrain_operands (1))
1223 CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs
[i
], j
);
1230 /* Return nonzero if REGNO is a particularly bad choice for reloading X. */
1232 ira_bad_reload_regno_1 (int regno
, rtx x
)
1236 enum reg_class pref
;
1238 /* We only deal with pseudo regs. */
1239 if (! x
|| GET_CODE (x
) != REG
)
1242 x_regno
= REGNO (x
);
1243 if (x_regno
< FIRST_PSEUDO_REGISTER
)
1246 /* If the pseudo prefers REGNO explicitly, then do not consider
1247 REGNO a bad spill choice. */
1248 pref
= reg_preferred_class (x_regno
);
1249 if (reg_class_size
[pref
] == 1)
1250 return !TEST_HARD_REG_BIT (reg_class_contents
[pref
], regno
);
1252 /* If the pseudo conflicts with REGNO, then we consider REGNO a
1253 poor choice for a reload regno. */
1254 a
= ira_regno_allocno_map
[x_regno
];
1255 n
= ALLOCNO_NUM_OBJECTS (a
);
1256 for (i
= 0; i
< n
; i
++)
1258 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
1259 if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), regno
))
1265 /* Return nonzero if REGNO is a particularly bad choice for reloading
1268 ira_bad_reload_regno (int regno
, rtx in
, rtx out
)
1270 return (ira_bad_reload_regno_1 (regno
, in
)
1271 || ira_bad_reload_regno_1 (regno
, out
));
1274 /* Function specific hard registers that can not be used for the
1275 register allocation. */
1276 HARD_REG_SET ira_no_alloc_regs
;
1278 /* Return TRUE if *LOC contains an asm. */
1280 insn_contains_asm_1 (rtx
*loc
, void *data ATTRIBUTE_UNUSED
)
1284 if (GET_CODE (*loc
) == ASM_OPERANDS
)
1290 /* Return TRUE if INSN contains an ASM. */
1292 insn_contains_asm (rtx insn
)
1294 return for_each_rtx (&insn
, insn_contains_asm_1
, NULL
);
1297 /* Add register clobbers from asm statements. */
1299 compute_regs_asm_clobbered (void)
1306 FOR_BB_INSNS_REVERSE (bb
, insn
)
1310 if (insn_contains_asm (insn
))
1311 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
1313 df_ref def
= *def_rec
;
1314 unsigned int dregno
= DF_REF_REGNO (def
);
1315 if (dregno
< FIRST_PSEUDO_REGISTER
)
1318 enum machine_mode mode
= GET_MODE (DF_REF_REAL_REG (def
));
1319 unsigned int end
= dregno
1320 + hard_regno_nregs
[dregno
][mode
] - 1;
1322 for (i
= dregno
; i
<= end
; ++i
)
1323 SET_HARD_REG_BIT(crtl
->asm_clobbers
, i
);
1331 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and REGS_EVER_LIVE. */
1333 ira_setup_eliminable_regset (void)
1335 #ifdef ELIMINABLE_REGS
1337 static const struct {const int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
1339 /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
1340 sp for alloca. So we can't eliminate the frame pointer in that
1341 case. At some point, we should improve this by emitting the
1342 sp-adjusting insns for this case. */
1344 = (! flag_omit_frame_pointer
1345 || (cfun
->calls_alloca
&& EXIT_IGNORE_STACK
)
1346 /* We need the frame pointer to catch stack overflow exceptions
1347 if the stack pointer is moving. */
1348 || (flag_stack_check
&& STACK_CHECK_MOVING_SP
)
1349 || crtl
->accesses_prior_frames
1350 || crtl
->stack_realign_needed
1351 || targetm
.frame_pointer_required ());
1353 frame_pointer_needed
= need_fp
;
1355 COPY_HARD_REG_SET (ira_no_alloc_regs
, no_unit_alloc_regs
);
1356 CLEAR_HARD_REG_SET (eliminable_regset
);
1358 compute_regs_asm_clobbered ();
1360 /* Build the regset of all eliminable registers and show we can't
1361 use those that we already know won't be eliminated. */
1362 #ifdef ELIMINABLE_REGS
1363 for (i
= 0; i
< (int) ARRAY_SIZE (eliminables
); i
++)
1366 = (! targetm
.can_eliminate (eliminables
[i
].from
, eliminables
[i
].to
)
1367 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& need_fp
));
1369 if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
, eliminables
[i
].from
))
1371 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
1374 SET_HARD_REG_BIT (ira_no_alloc_regs
, eliminables
[i
].from
);
1376 else if (cannot_elim
)
1377 error ("%s cannot be used in asm here",
1378 reg_names
[eliminables
[i
].from
]);
1380 df_set_regs_ever_live (eliminables
[i
].from
, true);
1382 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
1383 if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
, HARD_FRAME_POINTER_REGNUM
))
1385 SET_HARD_REG_BIT (eliminable_regset
, HARD_FRAME_POINTER_REGNUM
);
1387 SET_HARD_REG_BIT (ira_no_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
1390 error ("%s cannot be used in asm here",
1391 reg_names
[HARD_FRAME_POINTER_REGNUM
]);
1393 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM
, true);
1397 if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
, HARD_FRAME_POINTER_REGNUM
))
1399 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
1401 SET_HARD_REG_BIT (ira_no_alloc_regs
, FRAME_POINTER_REGNUM
);
1404 error ("%s cannot be used in asm here", reg_names
[FRAME_POINTER_REGNUM
]);
1406 df_set_regs_ever_live (FRAME_POINTER_REGNUM
, true);
1412 /* The length of the following two arrays. */
1413 int ira_reg_equiv_len
;
1415 /* The element value is TRUE if the corresponding regno value is
1417 bool *ira_reg_equiv_invariant_p
;
1419 /* The element value is equiv constant of given pseudo-register or
1421 rtx
*ira_reg_equiv_const
;
1423 /* Set up the two arrays declared above. */
1425 find_reg_equiv_invariant_const (void)
1429 rtx list
, insn
, note
, constant
, x
;
1431 for (i
= FIRST_PSEUDO_REGISTER
; i
< reg_equiv_init_size
; i
++)
1433 constant
= NULL_RTX
;
1434 invariant_p
= false;
1435 for (list
= reg_equiv_init
[i
]; list
!= NULL_RTX
; list
= XEXP (list
, 1))
1437 insn
= XEXP (list
, 0);
1438 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
1440 if (note
== NULL_RTX
)
1445 if (! CONSTANT_P (x
)
1446 || ! flag_pic
|| LEGITIMATE_PIC_OPERAND_P (x
))
1448 /* It can happen that a REG_EQUIV note contains a MEM
1449 that is not a legitimate memory operand. As later
1450 stages of the reload assume that all addresses found
1451 in the reg_equiv_* arrays were originally legitimate,
1452 we ignore such REG_EQUIV notes. */
1453 if (memory_operand (x
, VOIDmode
))
1454 invariant_p
= MEM_READONLY_P (x
);
1455 else if (function_invariant_p (x
))
1457 if (GET_CODE (x
) == PLUS
1458 || x
== frame_pointer_rtx
|| x
== arg_pointer_rtx
)
1465 ira_reg_equiv_invariant_p
[i
] = invariant_p
;
1466 ira_reg_equiv_const
[i
] = constant
;
1472 /* Vector of substitutions of register numbers,
1473 used to map pseudo regs into hardware regs.
1474 This is set up as a result of register allocation.
1475 Element N is the hard reg assigned to pseudo reg N,
1476 or is -1 if no hard reg was assigned.
1477 If N is a hard reg number, element N is N. */
1478 short *reg_renumber
;
1480 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
1481 the allocation found by IRA. */
1483 setup_reg_renumber (void)
1485 int regno
, hard_regno
;
1487 ira_allocno_iterator ai
;
1489 caller_save_needed
= 0;
1490 FOR_EACH_ALLOCNO (a
, ai
)
1492 /* There are no caps at this point. */
1493 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
1494 if (! ALLOCNO_ASSIGNED_P (a
))
1495 /* It can happen if A is not referenced but partially anticipated
1496 somewhere in a region. */
1497 ALLOCNO_ASSIGNED_P (a
) = true;
1498 ira_free_allocno_updated_costs (a
);
1499 hard_regno
= ALLOCNO_HARD_REGNO (a
);
1500 regno
= (int) REGNO (ALLOCNO_REG (a
));
1501 reg_renumber
[regno
] = (hard_regno
< 0 ? -1 : hard_regno
);
1502 if (hard_regno
>= 0 && ALLOCNO_CALLS_CROSSED_NUM (a
) != 0
1503 && ! ira_hard_reg_not_in_set_p (hard_regno
, ALLOCNO_MODE (a
),
1506 ira_assert (!optimize
|| flag_caller_saves
1507 || regno
>= ira_reg_equiv_len
1508 || ira_reg_equiv_const
[regno
]
1509 || ira_reg_equiv_invariant_p
[regno
]);
1510 caller_save_needed
= 1;
1515 /* Set up allocno assignment flags for further allocation
1518 setup_allocno_assignment_flags (void)
1522 ira_allocno_iterator ai
;
1524 FOR_EACH_ALLOCNO (a
, ai
)
1526 if (! ALLOCNO_ASSIGNED_P (a
))
1527 /* It can happen if A is not referenced but partially anticipated
1528 somewhere in a region. */
1529 ira_free_allocno_updated_costs (a
);
1530 hard_regno
= ALLOCNO_HARD_REGNO (a
);
1531 /* Don't assign hard registers to allocnos which are destination
1532 of removed store at the end of loop. It has no sense to keep
1533 the same value in different hard registers. It is also
1534 impossible to assign hard registers correctly to such
1535 allocnos because the cost info and info about intersected
1536 calls are incorrect for them. */
1537 ALLOCNO_ASSIGNED_P (a
) = (hard_regno
>= 0
1538 || ALLOCNO_MEM_OPTIMIZED_DEST_P (a
)
1539 || (ALLOCNO_MEMORY_COST (a
)
1540 - ALLOCNO_COVER_CLASS_COST (a
)) < 0);
1541 ira_assert (hard_regno
< 0
1542 || ! ira_hard_reg_not_in_set_p (hard_regno
, ALLOCNO_MODE (a
),
1544 [ALLOCNO_COVER_CLASS (a
)]));
1548 /* Evaluate overall allocation cost and the costs for using hard
1549 registers and memory for allocnos. */
1551 calculate_allocation_cost (void)
1553 int hard_regno
, cost
;
1555 ira_allocno_iterator ai
;
1557 ira_overall_cost
= ira_reg_cost
= ira_mem_cost
= 0;
1558 FOR_EACH_ALLOCNO (a
, ai
)
1560 hard_regno
= ALLOCNO_HARD_REGNO (a
);
1561 ira_assert (hard_regno
< 0
1562 || ! ira_hard_reg_not_in_set_p
1563 (hard_regno
, ALLOCNO_MODE (a
),
1564 reg_class_contents
[ALLOCNO_COVER_CLASS (a
)]));
1567 cost
= ALLOCNO_MEMORY_COST (a
);
1568 ira_mem_cost
+= cost
;
1570 else if (ALLOCNO_HARD_REG_COSTS (a
) != NULL
)
1572 cost
= (ALLOCNO_HARD_REG_COSTS (a
)
1573 [ira_class_hard_reg_index
1574 [ALLOCNO_COVER_CLASS (a
)][hard_regno
]]);
1575 ira_reg_cost
+= cost
;
1579 cost
= ALLOCNO_COVER_CLASS_COST (a
);
1580 ira_reg_cost
+= cost
;
1582 ira_overall_cost
+= cost
;
1585 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
1587 fprintf (ira_dump_file
,
1588 "+++Costs: overall %d, reg %d, mem %d, ld %d, st %d, move %d\n",
1589 ira_overall_cost
, ira_reg_cost
, ira_mem_cost
,
1590 ira_load_cost
, ira_store_cost
, ira_shuffle_cost
);
1591 fprintf (ira_dump_file
, "+++ move loops %d, new jumps %d\n",
1592 ira_move_loops_num
, ira_additional_jumps_num
);
1597 #ifdef ENABLE_IRA_CHECKING
1598 /* Check the correctness of the allocation. We do need this because
1599 of complicated code to transform more one region internal
1600 representation into one region representation. */
1602 check_allocation (void)
1605 int hard_regno
, nregs
, conflict_nregs
;
1606 ira_allocno_iterator ai
;
1608 FOR_EACH_ALLOCNO (a
, ai
)
1610 int n
= ALLOCNO_NUM_OBJECTS (a
);
1613 if (ALLOCNO_CAP_MEMBER (a
) != NULL
1614 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0)
1616 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (a
)];
1618 /* We allocated a single hard register. */
1621 /* We allocated multiple hard registers, and we will test
1622 conflicts in a granularity of single hard regs. */
1625 for (i
= 0; i
< n
; i
++)
1627 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
1628 ira_object_t conflict_obj
;
1629 ira_object_conflict_iterator oci
;
1630 int this_regno
= hard_regno
;
1633 if (WORDS_BIG_ENDIAN
)
1634 this_regno
+= n
- i
- 1;
1638 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
1640 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
1641 int conflict_hard_regno
= ALLOCNO_HARD_REGNO (conflict_a
);
1642 if (conflict_hard_regno
< 0)
1647 [conflict_hard_regno
][ALLOCNO_MODE (conflict_a
)]);
1649 if (ALLOCNO_NUM_OBJECTS (conflict_a
) > 1
1650 && conflict_nregs
== ALLOCNO_NUM_OBJECTS (conflict_a
))
1652 if (WORDS_BIG_ENDIAN
)
1653 conflict_hard_regno
+= (ALLOCNO_NUM_OBJECTS (conflict_a
)
1654 - OBJECT_SUBWORD (conflict_obj
) - 1);
1656 conflict_hard_regno
+= OBJECT_SUBWORD (conflict_obj
);
1660 if ((conflict_hard_regno
<= this_regno
1661 && this_regno
< conflict_hard_regno
+ conflict_nregs
)
1662 || (this_regno
<= conflict_hard_regno
1663 && conflict_hard_regno
< this_regno
+ nregs
))
1665 fprintf (stderr
, "bad allocation for %d and %d\n",
1666 ALLOCNO_REGNO (a
), ALLOCNO_REGNO (conflict_a
));
1675 /* Fix values of array REG_EQUIV_INIT after live range splitting done
1678 fix_reg_equiv_init (void)
1680 int max_regno
= max_reg_num ();
1682 rtx x
, prev
, next
, insn
, set
;
1684 if (reg_equiv_init_size
< max_regno
)
1686 reg_equiv_init
= GGC_RESIZEVEC (rtx
, reg_equiv_init
, max_regno
);
1687 while (reg_equiv_init_size
< max_regno
)
1688 reg_equiv_init
[reg_equiv_init_size
++] = NULL_RTX
;
1689 for (i
= FIRST_PSEUDO_REGISTER
; i
< reg_equiv_init_size
; i
++)
1690 for (prev
= NULL_RTX
, x
= reg_equiv_init
[i
]; x
!= NULL_RTX
; x
= next
)
1694 set
= single_set (insn
);
1695 ira_assert (set
!= NULL_RTX
1696 && (REG_P (SET_DEST (set
)) || REG_P (SET_SRC (set
))));
1697 if (REG_P (SET_DEST (set
))
1698 && ((int) REGNO (SET_DEST (set
)) == i
1699 || (int) ORIGINAL_REGNO (SET_DEST (set
)) == i
))
1700 new_regno
= REGNO (SET_DEST (set
));
1701 else if (REG_P (SET_SRC (set
))
1702 && ((int) REGNO (SET_SRC (set
)) == i
1703 || (int) ORIGINAL_REGNO (SET_SRC (set
)) == i
))
1704 new_regno
= REGNO (SET_SRC (set
));
1711 if (prev
== NULL_RTX
)
1712 reg_equiv_init
[i
] = next
;
1714 XEXP (prev
, 1) = next
;
1715 XEXP (x
, 1) = reg_equiv_init
[new_regno
];
1716 reg_equiv_init
[new_regno
] = x
;
1722 #ifdef ENABLE_IRA_CHECKING
1723 /* Print redundant memory-memory copies. */
1725 print_redundant_copies (void)
1729 ira_copy_t cp
, next_cp
;
1730 ira_allocno_iterator ai
;
1732 FOR_EACH_ALLOCNO (a
, ai
)
1734 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
1737 hard_regno
= ALLOCNO_HARD_REGNO (a
);
1738 if (hard_regno
>= 0)
1740 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
1742 next_cp
= cp
->next_first_allocno_copy
;
1745 next_cp
= cp
->next_second_allocno_copy
;
1746 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
1747 && cp
->insn
!= NULL_RTX
1748 && ALLOCNO_HARD_REGNO (cp
->first
) == hard_regno
)
1749 fprintf (ira_dump_file
,
1750 " Redundant move from %d(freq %d):%d\n",
1751 INSN_UID (cp
->insn
), cp
->freq
, hard_regno
);
1757 /* Setup preferred and alternative classes for new pseudo-registers
1758 created by IRA starting with START. */
1760 setup_preferred_alternate_classes_for_new_pseudos (int start
)
1763 int max_regno
= max_reg_num ();
1765 for (i
= start
; i
< max_regno
; i
++)
1767 old_regno
= ORIGINAL_REGNO (regno_reg_rtx
[i
]);
1768 ira_assert (i
!= old_regno
);
1769 setup_reg_classes (i
, reg_preferred_class (old_regno
),
1770 reg_alternate_class (old_regno
),
1771 reg_cover_class (old_regno
));
1772 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1773 fprintf (ira_dump_file
,
1774 " New r%d: setting preferred %s, alternative %s\n",
1775 i
, reg_class_names
[reg_preferred_class (old_regno
)],
1776 reg_class_names
[reg_alternate_class (old_regno
)]);
1782 /* Regional allocation can create new pseudo-registers. This function
1783 expands some arrays for pseudo-registers. */
1785 expand_reg_info (int old_size
)
1788 int size
= max_reg_num ();
1791 for (i
= old_size
; i
< size
; i
++)
1792 setup_reg_classes (i
, GENERAL_REGS
, ALL_REGS
, GENERAL_REGS
);
1795 /* Return TRUE if there is too high register pressure in the function.
1796 It is used to decide when stack slot sharing is worth to do. */
1798 too_high_register_pressure_p (void)
1801 enum reg_class cover_class
;
1803 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1805 cover_class
= ira_reg_class_cover
[i
];
1806 if (ira_loop_tree_root
->reg_pressure
[cover_class
] > 10000)
1814 /* Indicate that hard register number FROM was eliminated and replaced with
1815 an offset from hard register number TO. The status of hard registers live
1816 at the start of a basic block is updated by replacing a use of FROM with
1820 mark_elimination (int from
, int to
)
1826 /* We don't use LIVE info in IRA. */
1827 bitmap r
= DF_LR_IN (bb
);
1829 if (REGNO_REG_SET_P (r
, from
))
1831 CLEAR_REGNO_REG_SET (r
, from
);
1832 SET_REGNO_REG_SET (r
, to
);
1841 /* Set when a REG_EQUIV note is found or created. Use to
1842 keep track of what memory accesses might be created later,
1846 /* The list of each instruction which initializes this register. */
1848 /* Loop depth is used to recognize equivalences which appear
1849 to be present within the same loop (or in an inner loop). */
1851 /* Nonzero if this had a preexisting REG_EQUIV note. */
1852 int is_arg_equivalence
;
1853 /* Set when an attempt should be made to replace a register
1854 with the associated src_p entry. */
1858 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
1859 structure for that register. */
1860 static struct equivalence
*reg_equiv
;
1862 /* Used for communication between the following two functions: contains
1863 a MEM that we wish to ensure remains unchanged. */
1864 static rtx equiv_mem
;
1866 /* Set nonzero if EQUIV_MEM is modified. */
1867 static int equiv_mem_modified
;
1869 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
1870 Called via note_stores. */
1872 validate_equiv_mem_from_store (rtx dest
, const_rtx set ATTRIBUTE_UNUSED
,
1873 void *data ATTRIBUTE_UNUSED
)
1876 && reg_overlap_mentioned_p (dest
, equiv_mem
))
1878 && true_dependence (dest
, VOIDmode
, equiv_mem
, rtx_varies_p
)))
1879 equiv_mem_modified
= 1;
1882 /* Verify that no store between START and the death of REG invalidates
1883 MEMREF. MEMREF is invalidated by modifying a register used in MEMREF,
1884 by storing into an overlapping memory location, or with a non-const
1887 Return 1 if MEMREF remains valid. */
1889 validate_equiv_mem (rtx start
, rtx reg
, rtx memref
)
1895 equiv_mem_modified
= 0;
1897 /* If the memory reference has side effects or is volatile, it isn't a
1898 valid equivalence. */
1899 if (side_effects_p (memref
))
1902 for (insn
= start
; insn
&& ! equiv_mem_modified
; insn
= NEXT_INSN (insn
))
1904 if (! INSN_P (insn
))
1907 if (find_reg_note (insn
, REG_DEAD
, reg
))
1910 /* This used to ignore readonly memory and const/pure calls. The problem
1911 is the equivalent form may reference a pseudo which gets assigned a
1912 call clobbered hard reg. When we later replace REG with its
1913 equivalent form, the value in the call-clobbered reg has been
1914 changed and all hell breaks loose. */
1918 note_stores (PATTERN (insn
), validate_equiv_mem_from_store
, NULL
);
1920 /* If a register mentioned in MEMREF is modified via an
1921 auto-increment, we lose the equivalence. Do the same if one
1922 dies; although we could extend the life, it doesn't seem worth
1925 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1926 if ((REG_NOTE_KIND (note
) == REG_INC
1927 || REG_NOTE_KIND (note
) == REG_DEAD
)
1928 && REG_P (XEXP (note
, 0))
1929 && reg_overlap_mentioned_p (XEXP (note
, 0), memref
))
1936 /* Returns zero if X is known to be invariant. */
1938 equiv_init_varies_p (rtx x
)
1940 RTX_CODE code
= GET_CODE (x
);
1947 return !MEM_READONLY_P (x
) || equiv_init_varies_p (XEXP (x
, 0));
1959 return reg_equiv
[REGNO (x
)].replace
== 0 && rtx_varies_p (x
, 0);
1962 if (MEM_VOLATILE_P (x
))
1971 fmt
= GET_RTX_FORMAT (code
);
1972 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1975 if (equiv_init_varies_p (XEXP (x
, i
)))
1978 else if (fmt
[i
] == 'E')
1981 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1982 if (equiv_init_varies_p (XVECEXP (x
, i
, j
)))
1989 /* Returns nonzero if X (used to initialize register REGNO) is movable.
1990 X is only movable if the registers it uses have equivalent initializations
1991 which appear to be within the same loop (or in an inner loop) and movable
1992 or if they are not candidates for local_alloc and don't vary. */
1994 equiv_init_movable_p (rtx x
, int regno
)
1998 enum rtx_code code
= GET_CODE (x
);
2003 return equiv_init_movable_p (SET_SRC (x
), regno
);
2018 return (reg_equiv
[REGNO (x
)].loop_depth
>= reg_equiv
[regno
].loop_depth
2019 && reg_equiv
[REGNO (x
)].replace
)
2020 || (REG_BASIC_BLOCK (REGNO (x
)) < NUM_FIXED_BLOCKS
&& ! rtx_varies_p (x
, 0));
2022 case UNSPEC_VOLATILE
:
2026 if (MEM_VOLATILE_P (x
))
2035 fmt
= GET_RTX_FORMAT (code
);
2036 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2040 if (! equiv_init_movable_p (XEXP (x
, i
), regno
))
2044 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2045 if (! equiv_init_movable_p (XVECEXP (x
, i
, j
), regno
))
2053 /* TRUE if X uses any registers for which reg_equiv[REGNO].replace is true. */
2055 contains_replace_regs (rtx x
)
2059 enum rtx_code code
= GET_CODE (x
);
2076 return reg_equiv
[REGNO (x
)].replace
;
2082 fmt
= GET_RTX_FORMAT (code
);
2083 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2087 if (contains_replace_regs (XEXP (x
, i
)))
2091 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2092 if (contains_replace_regs (XVECEXP (x
, i
, j
)))
2100 /* TRUE if X references a memory location that would be affected by a store
2103 memref_referenced_p (rtx memref
, rtx x
)
2107 enum rtx_code code
= GET_CODE (x
);
2125 return (reg_equiv
[REGNO (x
)].replacement
2126 && memref_referenced_p (memref
,
2127 reg_equiv
[REGNO (x
)].replacement
));
2130 if (true_dependence (memref
, VOIDmode
, x
, rtx_varies_p
))
2135 /* If we are setting a MEM, it doesn't count (its address does), but any
2136 other SET_DEST that has a MEM in it is referencing the MEM. */
2137 if (MEM_P (SET_DEST (x
)))
2139 if (memref_referenced_p (memref
, XEXP (SET_DEST (x
), 0)))
2142 else if (memref_referenced_p (memref
, SET_DEST (x
)))
2145 return memref_referenced_p (memref
, SET_SRC (x
));
2151 fmt
= GET_RTX_FORMAT (code
);
2152 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2156 if (memref_referenced_p (memref
, XEXP (x
, i
)))
2160 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2161 if (memref_referenced_p (memref
, XVECEXP (x
, i
, j
)))
2169 /* TRUE if some insn in the range (START, END] references a memory location
2170 that would be affected by a store to MEMREF. */
2172 memref_used_between_p (rtx memref
, rtx start
, rtx end
)
2176 for (insn
= NEXT_INSN (start
); insn
!= NEXT_INSN (end
);
2177 insn
= NEXT_INSN (insn
))
2179 if (!NONDEBUG_INSN_P (insn
))
2182 if (memref_referenced_p (memref
, PATTERN (insn
)))
2185 /* Nonconst functions may access memory. */
2186 if (CALL_P (insn
) && (! RTL_CONST_CALL_P (insn
)))
2193 /* Mark REG as having no known equivalence.
2194 Some instructions might have been processed before and furnished
2195 with REG_EQUIV notes for this register; these notes will have to be
2197 STORE is the piece of RTL that does the non-constant / conflicting
2198 assignment - a SET, CLOBBER or REG_INC note. It is currently not used,
2199 but needs to be there because this function is called from note_stores. */
2201 no_equiv (rtx reg
, const_rtx store ATTRIBUTE_UNUSED
, void *data ATTRIBUTE_UNUSED
)
2208 regno
= REGNO (reg
);
2209 list
= reg_equiv
[regno
].init_insns
;
2210 if (list
== const0_rtx
)
2212 reg_equiv
[regno
].init_insns
= const0_rtx
;
2213 reg_equiv
[regno
].replacement
= NULL_RTX
;
2214 /* This doesn't matter for equivalences made for argument registers, we
2215 should keep their initialization insns. */
2216 if (reg_equiv
[regno
].is_arg_equivalence
)
2218 reg_equiv_init
[regno
] = NULL_RTX
;
2219 for (; list
; list
= XEXP (list
, 1))
2221 rtx insn
= XEXP (list
, 0);
2222 remove_note (insn
, find_reg_note (insn
, REG_EQUIV
, NULL_RTX
));
2226 /* In DEBUG_INSN location adjust REGs from CLEARED_REGS bitmap to the
2227 equivalent replacement. */
2230 adjust_cleared_regs (rtx loc
, const_rtx old_rtx ATTRIBUTE_UNUSED
, void *data
)
2234 bitmap cleared_regs
= (bitmap
) data
;
2235 if (bitmap_bit_p (cleared_regs
, REGNO (loc
)))
2236 return simplify_replace_fn_rtx (*reg_equiv
[REGNO (loc
)].src_p
,
2237 NULL_RTX
, adjust_cleared_regs
, data
);
2242 /* Nonzero if we recorded an equivalence for a LABEL_REF. */
2243 static int recorded_label_ref
;
2245 /* Find registers that are equivalent to a single value throughout the
2246 compilation (either because they can be referenced in memory or are set once
2247 from a single constant). Lower their priority for a register.
2249 If such a register is only referenced once, try substituting its value
2250 into the using insn. If it succeeds, we can eliminate the register
2253 Initialize the REG_EQUIV_INIT array of initializing insns.
2255 Return non-zero if jump label rebuilding should be done. */
2257 update_equiv_regs (void)
2262 bitmap cleared_regs
;
2264 /* We need to keep track of whether or not we recorded a LABEL_REF so
2265 that we know if the jump optimizer needs to be rerun. */
2266 recorded_label_ref
= 0;
2268 reg_equiv
= XCNEWVEC (struct equivalence
, max_regno
);
2269 reg_equiv_init
= ggc_alloc_cleared_vec_rtx (max_regno
);
2270 reg_equiv_init_size
= max_regno
;
2272 init_alias_analysis ();
2274 /* Scan the insns and find which registers have equivalences. Do this
2275 in a separate scan of the insns because (due to -fcse-follow-jumps)
2276 a register can be set below its use. */
2279 loop_depth
= bb
->loop_depth
;
2281 for (insn
= BB_HEAD (bb
);
2282 insn
!= NEXT_INSN (BB_END (bb
));
2283 insn
= NEXT_INSN (insn
))
2290 if (! INSN_P (insn
))
2293 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
2294 if (REG_NOTE_KIND (note
) == REG_INC
)
2295 no_equiv (XEXP (note
, 0), note
, NULL
);
2297 set
= single_set (insn
);
2299 /* If this insn contains more (or less) than a single SET,
2300 only mark all destinations as having no known equivalence. */
2303 note_stores (PATTERN (insn
), no_equiv
, NULL
);
2306 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2310 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
2312 rtx part
= XVECEXP (PATTERN (insn
), 0, i
);
2314 note_stores (part
, no_equiv
, NULL
);
2318 dest
= SET_DEST (set
);
2319 src
= SET_SRC (set
);
2321 /* See if this is setting up the equivalence between an argument
2322 register and its stack slot. */
2323 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
2326 gcc_assert (REG_P (dest
));
2327 regno
= REGNO (dest
);
2329 /* Note that we don't want to clear reg_equiv_init even if there
2330 are multiple sets of this register. */
2331 reg_equiv
[regno
].is_arg_equivalence
= 1;
2333 /* Record for reload that this is an equivalencing insn. */
2334 if (rtx_equal_p (src
, XEXP (note
, 0)))
2335 reg_equiv_init
[regno
]
2336 = gen_rtx_INSN_LIST (VOIDmode
, insn
, reg_equiv_init
[regno
]);
2338 /* Continue normally in case this is a candidate for
2345 /* We only handle the case of a pseudo register being set
2346 once, or always to the same value. */
2347 /* ??? The mn10200 port breaks if we add equivalences for
2348 values that need an ADDRESS_REGS register and set them equivalent
2349 to a MEM of a pseudo. The actual problem is in the over-conservative
2350 handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
2351 calculate_needs, but we traditionally work around this problem
2352 here by rejecting equivalences when the destination is in a register
2353 that's likely spilled. This is fragile, of course, since the
2354 preferred class of a pseudo depends on all instructions that set
2358 || (regno
= REGNO (dest
)) < FIRST_PSEUDO_REGISTER
2359 || reg_equiv
[regno
].init_insns
== const0_rtx
2360 || (targetm
.class_likely_spilled_p (reg_preferred_class (regno
))
2361 && MEM_P (src
) && ! reg_equiv
[regno
].is_arg_equivalence
))
2363 /* This might be setting a SUBREG of a pseudo, a pseudo that is
2364 also set somewhere else to a constant. */
2365 note_stores (set
, no_equiv
, NULL
);
2369 note
= find_reg_note (insn
, REG_EQUAL
, NULL_RTX
);
2371 /* cse sometimes generates function invariants, but doesn't put a
2372 REG_EQUAL note on the insn. Since this note would be redundant,
2373 there's no point creating it earlier than here. */
2374 if (! note
&& ! rtx_varies_p (src
, 0))
2375 note
= set_unique_reg_note (insn
, REG_EQUAL
, copy_rtx (src
));
2377 /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
2378 since it represents a function call */
2379 if (note
&& GET_CODE (XEXP (note
, 0)) == EXPR_LIST
)
2382 if (DF_REG_DEF_COUNT (regno
) != 1
2384 || rtx_varies_p (XEXP (note
, 0), 0)
2385 || (reg_equiv
[regno
].replacement
2386 && ! rtx_equal_p (XEXP (note
, 0),
2387 reg_equiv
[regno
].replacement
))))
2389 no_equiv (dest
, set
, NULL
);
2392 /* Record this insn as initializing this register. */
2393 reg_equiv
[regno
].init_insns
2394 = gen_rtx_INSN_LIST (VOIDmode
, insn
, reg_equiv
[regno
].init_insns
);
2396 /* If this register is known to be equal to a constant, record that
2397 it is always equivalent to the constant. */
2398 if (DF_REG_DEF_COUNT (regno
) == 1
2399 && note
&& ! rtx_varies_p (XEXP (note
, 0), 0))
2401 rtx note_value
= XEXP (note
, 0);
2402 remove_note (insn
, note
);
2403 set_unique_reg_note (insn
, REG_EQUIV
, note_value
);
2406 /* If this insn introduces a "constant" register, decrease the priority
2407 of that register. Record this insn if the register is only used once
2408 more and the equivalence value is the same as our source.
2410 The latter condition is checked for two reasons: First, it is an
2411 indication that it may be more efficient to actually emit the insn
2412 as written (if no registers are available, reload will substitute
2413 the equivalence). Secondly, it avoids problems with any registers
2414 dying in this insn whose death notes would be missed.
2416 If we don't have a REG_EQUIV note, see if this insn is loading
2417 a register used only in one basic block from a MEM. If so, and the
2418 MEM remains unchanged for the life of the register, add a REG_EQUIV
2421 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
2423 if (note
== 0 && REG_BASIC_BLOCK (regno
) >= NUM_FIXED_BLOCKS
2424 && MEM_P (SET_SRC (set
))
2425 && validate_equiv_mem (insn
, dest
, SET_SRC (set
)))
2426 note
= set_unique_reg_note (insn
, REG_EQUIV
, copy_rtx (SET_SRC (set
)));
2430 int regno
= REGNO (dest
);
2431 rtx x
= XEXP (note
, 0);
2433 /* If we haven't done so, record for reload that this is an
2434 equivalencing insn. */
2435 if (!reg_equiv
[regno
].is_arg_equivalence
)
2436 reg_equiv_init
[regno
]
2437 = gen_rtx_INSN_LIST (VOIDmode
, insn
, reg_equiv_init
[regno
]);
2439 /* Record whether or not we created a REG_EQUIV note for a LABEL_REF.
2440 We might end up substituting the LABEL_REF for uses of the
2441 pseudo here or later. That kind of transformation may turn an
2442 indirect jump into a direct jump, in which case we must rerun the
2443 jump optimizer to ensure that the JUMP_LABEL fields are valid. */
2444 if (GET_CODE (x
) == LABEL_REF
2445 || (GET_CODE (x
) == CONST
2446 && GET_CODE (XEXP (x
, 0)) == PLUS
2447 && (GET_CODE (XEXP (XEXP (x
, 0), 0)) == LABEL_REF
)))
2448 recorded_label_ref
= 1;
2450 reg_equiv
[regno
].replacement
= x
;
2451 reg_equiv
[regno
].src_p
= &SET_SRC (set
);
2452 reg_equiv
[regno
].loop_depth
= loop_depth
;
2454 /* Don't mess with things live during setjmp. */
2455 if (REG_LIVE_LENGTH (regno
) >= 0 && optimize
)
2457 /* Note that the statement below does not affect the priority
2459 REG_LIVE_LENGTH (regno
) *= 2;
2461 /* If the register is referenced exactly twice, meaning it is
2462 set once and used once, indicate that the reference may be
2463 replaced by the equivalence we computed above. Do this
2464 even if the register is only used in one block so that
2465 dependencies can be handled where the last register is
2466 used in a different block (i.e. HIGH / LO_SUM sequences)
2467 and to reduce the number of registers alive across
2470 if (REG_N_REFS (regno
) == 2
2471 && (rtx_equal_p (x
, src
)
2472 || ! equiv_init_varies_p (src
))
2473 && NONJUMP_INSN_P (insn
)
2474 && equiv_init_movable_p (PATTERN (insn
), regno
))
2475 reg_equiv
[regno
].replace
= 1;
2484 /* A second pass, to gather additional equivalences with memory. This needs
2485 to be done after we know which registers we are going to replace. */
2487 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
2492 if (! INSN_P (insn
))
2495 set
= single_set (insn
);
2499 dest
= SET_DEST (set
);
2500 src
= SET_SRC (set
);
2502 /* If this sets a MEM to the contents of a REG that is only used
2503 in a single basic block, see if the register is always equivalent
2504 to that memory location and if moving the store from INSN to the
2505 insn that set REG is safe. If so, put a REG_EQUIV note on the
2508 Don't add a REG_EQUIV note if the insn already has one. The existing
2509 REG_EQUIV is likely more useful than the one we are adding.
2511 If one of the regs in the address has reg_equiv[REGNO].replace set,
2512 then we can't add this REG_EQUIV note. The reg_equiv[REGNO].replace
2513 optimization may move the set of this register immediately before
2514 insn, which puts it after reg_equiv[REGNO].init_insns, and hence
2515 the mention in the REG_EQUIV note would be to an uninitialized
2518 if (MEM_P (dest
) && REG_P (src
)
2519 && (regno
= REGNO (src
)) >= FIRST_PSEUDO_REGISTER
2520 && REG_BASIC_BLOCK (regno
) >= NUM_FIXED_BLOCKS
2521 && DF_REG_DEF_COUNT (regno
) == 1
2522 && reg_equiv
[regno
].init_insns
!= 0
2523 && reg_equiv
[regno
].init_insns
!= const0_rtx
2524 && ! find_reg_note (XEXP (reg_equiv
[regno
].init_insns
, 0),
2525 REG_EQUIV
, NULL_RTX
)
2526 && ! contains_replace_regs (XEXP (dest
, 0)))
2528 rtx init_insn
= XEXP (reg_equiv
[regno
].init_insns
, 0);
2529 if (validate_equiv_mem (init_insn
, src
, dest
)
2530 && ! memref_used_between_p (dest
, init_insn
, insn
)
2531 /* Attaching a REG_EQUIV note will fail if INIT_INSN has
2533 && set_unique_reg_note (init_insn
, REG_EQUIV
, copy_rtx (dest
)))
2535 /* This insn makes the equivalence, not the one initializing
2537 reg_equiv_init
[regno
]
2538 = gen_rtx_INSN_LIST (VOIDmode
, insn
, NULL_RTX
);
2539 df_notes_rescan (init_insn
);
2544 cleared_regs
= BITMAP_ALLOC (NULL
);
2545 /* Now scan all regs killed in an insn to see if any of them are
2546 registers only used that once. If so, see if we can replace the
2547 reference with the equivalent form. If we can, delete the
2548 initializing reference and this register will go away. If we
2549 can't replace the reference, and the initializing reference is
2550 within the same loop (or in an inner loop), then move the register
2551 initialization just before the use, so that they are in the same
2553 FOR_EACH_BB_REVERSE (bb
)
2555 loop_depth
= bb
->loop_depth
;
2556 for (insn
= BB_END (bb
);
2557 insn
!= PREV_INSN (BB_HEAD (bb
));
2558 insn
= PREV_INSN (insn
))
2562 if (! INSN_P (insn
))
2565 /* Don't substitute into a non-local goto, this confuses CFG. */
2567 && find_reg_note (insn
, REG_NON_LOCAL_GOTO
, NULL_RTX
))
2570 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2572 if (REG_NOTE_KIND (link
) == REG_DEAD
2573 /* Make sure this insn still refers to the register. */
2574 && reg_mentioned_p (XEXP (link
, 0), PATTERN (insn
)))
2576 int regno
= REGNO (XEXP (link
, 0));
2579 if (! reg_equiv
[regno
].replace
2580 || reg_equiv
[regno
].loop_depth
< loop_depth
2581 /* There is no sense to move insns if we did
2582 register pressure-sensitive scheduling was
2583 done because it will not improve allocation
2584 but worsen insn schedule with a big
2586 || (flag_sched_pressure
&& flag_schedule_insns
))
2589 /* reg_equiv[REGNO].replace gets set only when
2590 REG_N_REFS[REGNO] is 2, i.e. the register is set
2591 once and used once. (If it were only set, but not used,
2592 flow would have deleted the setting insns.) Hence
2593 there can only be one insn in reg_equiv[REGNO].init_insns. */
2594 gcc_assert (reg_equiv
[regno
].init_insns
2595 && !XEXP (reg_equiv
[regno
].init_insns
, 1));
2596 equiv_insn
= XEXP (reg_equiv
[regno
].init_insns
, 0);
2598 /* We may not move instructions that can throw, since
2599 that changes basic block boundaries and we are not
2600 prepared to adjust the CFG to match. */
2601 if (can_throw_internal (equiv_insn
))
2604 if (asm_noperands (PATTERN (equiv_insn
)) < 0
2605 && validate_replace_rtx (regno_reg_rtx
[regno
],
2606 *(reg_equiv
[regno
].src_p
), insn
))
2612 /* Find the last note. */
2613 for (last_link
= link
; XEXP (last_link
, 1);
2614 last_link
= XEXP (last_link
, 1))
2617 /* Append the REG_DEAD notes from equiv_insn. */
2618 equiv_link
= REG_NOTES (equiv_insn
);
2622 equiv_link
= XEXP (equiv_link
, 1);
2623 if (REG_NOTE_KIND (note
) == REG_DEAD
)
2625 remove_note (equiv_insn
, note
);
2626 XEXP (last_link
, 1) = note
;
2627 XEXP (note
, 1) = NULL_RTX
;
2632 remove_death (regno
, insn
);
2633 SET_REG_N_REFS (regno
, 0);
2634 REG_FREQ (regno
) = 0;
2635 delete_insn (equiv_insn
);
2637 reg_equiv
[regno
].init_insns
2638 = XEXP (reg_equiv
[regno
].init_insns
, 1);
2640 reg_equiv_init
[regno
] = NULL_RTX
;
2641 bitmap_set_bit (cleared_regs
, regno
);
2643 /* Move the initialization of the register to just before
2644 INSN. Update the flow information. */
2645 else if (prev_nondebug_insn (insn
) != equiv_insn
)
2649 new_insn
= emit_insn_before (PATTERN (equiv_insn
), insn
);
2650 REG_NOTES (new_insn
) = REG_NOTES (equiv_insn
);
2651 REG_NOTES (equiv_insn
) = 0;
2652 /* Rescan it to process the notes. */
2653 df_insn_rescan (new_insn
);
2655 /* Make sure this insn is recognized before
2656 reload begins, otherwise
2657 eliminate_regs_in_insn will die. */
2658 INSN_CODE (new_insn
) = INSN_CODE (equiv_insn
);
2660 delete_insn (equiv_insn
);
2662 XEXP (reg_equiv
[regno
].init_insns
, 0) = new_insn
;
2664 REG_BASIC_BLOCK (regno
) = bb
->index
;
2665 REG_N_CALLS_CROSSED (regno
) = 0;
2666 REG_FREQ_CALLS_CROSSED (regno
) = 0;
2667 REG_N_THROWING_CALLS_CROSSED (regno
) = 0;
2668 REG_LIVE_LENGTH (regno
) = 2;
2670 if (insn
== BB_HEAD (bb
))
2671 BB_HEAD (bb
) = PREV_INSN (insn
);
2673 reg_equiv_init
[regno
]
2674 = gen_rtx_INSN_LIST (VOIDmode
, new_insn
, NULL_RTX
);
2675 bitmap_set_bit (cleared_regs
, regno
);
2682 if (!bitmap_empty_p (cleared_regs
))
2686 bitmap_and_compl_into (DF_LIVE_IN (bb
), cleared_regs
);
2687 bitmap_and_compl_into (DF_LIVE_OUT (bb
), cleared_regs
);
2688 bitmap_and_compl_into (DF_LR_IN (bb
), cleared_regs
);
2689 bitmap_and_compl_into (DF_LR_OUT (bb
), cleared_regs
);
2692 /* Last pass - adjust debug insns referencing cleared regs. */
2693 if (MAY_HAVE_DEBUG_INSNS
)
2694 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
2695 if (DEBUG_INSN_P (insn
))
2697 rtx old_loc
= INSN_VAR_LOCATION_LOC (insn
);
2698 INSN_VAR_LOCATION_LOC (insn
)
2699 = simplify_replace_fn_rtx (old_loc
, NULL_RTX
,
2700 adjust_cleared_regs
,
2701 (void *) cleared_regs
);
2702 if (old_loc
!= INSN_VAR_LOCATION_LOC (insn
))
2703 df_insn_rescan (insn
);
2707 BITMAP_FREE (cleared_regs
);
2712 end_alias_analysis ();
2714 return recorded_label_ref
;
2719 /* Print chain C to FILE. */
2721 print_insn_chain (FILE *file
, struct insn_chain
*c
)
2723 fprintf (file
, "insn=%d, ", INSN_UID(c
->insn
));
2724 bitmap_print (file
, &c
->live_throughout
, "live_throughout: ", ", ");
2725 bitmap_print (file
, &c
->dead_or_set
, "dead_or_set: ", "\n");
2729 /* Print all reload_insn_chains to FILE. */
2731 print_insn_chains (FILE *file
)
2733 struct insn_chain
*c
;
2734 for (c
= reload_insn_chain
; c
; c
= c
->next
)
2735 print_insn_chain (file
, c
);
2738 /* Return true if pseudo REGNO should be added to set live_throughout
2739 or dead_or_set of the insn chains for reload consideration. */
2741 pseudo_for_reload_consideration_p (int regno
)
2743 /* Consider spilled pseudos too for IRA because they still have a
2744 chance to get hard-registers in the reload when IRA is used. */
2745 return (reg_renumber
[regno
] >= 0 || ira_conflicts_p
);
2748 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
2749 REG to the number of nregs, and INIT_VALUE to get the
2750 initialization. ALLOCNUM need not be the regno of REG. */
2752 init_live_subregs (bool init_value
, sbitmap
*live_subregs
,
2753 int *live_subregs_used
, int allocnum
, rtx reg
)
2755 unsigned int regno
= REGNO (SUBREG_REG (reg
));
2756 int size
= GET_MODE_SIZE (GET_MODE (regno_reg_rtx
[regno
]));
2758 gcc_assert (size
> 0);
2760 /* Been there, done that. */
2761 if (live_subregs_used
[allocnum
])
2764 /* Create a new one with zeros. */
2765 if (live_subregs
[allocnum
] == NULL
)
2766 live_subregs
[allocnum
] = sbitmap_alloc (size
);
2768 /* If the entire reg was live before blasting into subregs, we need
2769 to init all of the subregs to ones else init to 0. */
2771 sbitmap_ones (live_subregs
[allocnum
]);
2773 sbitmap_zero (live_subregs
[allocnum
]);
2775 /* Set the number of bits that we really want. */
2776 live_subregs_used
[allocnum
] = size
;
2779 /* Walk the insns of the current function and build reload_insn_chain,
2780 and record register life information. */
2782 build_insn_chain (void)
2785 struct insn_chain
**p
= &reload_insn_chain
;
2787 struct insn_chain
*c
= NULL
;
2788 struct insn_chain
*next
= NULL
;
2789 bitmap live_relevant_regs
= BITMAP_ALLOC (NULL
);
2790 bitmap elim_regset
= BITMAP_ALLOC (NULL
);
2791 /* live_subregs is a vector used to keep accurate information about
2792 which hardregs are live in multiword pseudos. live_subregs and
2793 live_subregs_used are indexed by pseudo number. The live_subreg
2794 entry for a particular pseudo is only used if the corresponding
2795 element is non zero in live_subregs_used. The value in
2796 live_subregs_used is number of bytes that the pseudo can
2798 sbitmap
*live_subregs
= XCNEWVEC (sbitmap
, max_regno
);
2799 int *live_subregs_used
= XNEWVEC (int, max_regno
);
2801 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2802 if (TEST_HARD_REG_BIT (eliminable_regset
, i
))
2803 bitmap_set_bit (elim_regset
, i
);
2804 FOR_EACH_BB_REVERSE (bb
)
2809 CLEAR_REG_SET (live_relevant_regs
);
2810 memset (live_subregs_used
, 0, max_regno
* sizeof (int));
2812 EXECUTE_IF_SET_IN_BITMAP (DF_LR_OUT (bb
), 0, i
, bi
)
2814 if (i
>= FIRST_PSEUDO_REGISTER
)
2816 bitmap_set_bit (live_relevant_regs
, i
);
2819 EXECUTE_IF_SET_IN_BITMAP (DF_LR_OUT (bb
),
2820 FIRST_PSEUDO_REGISTER
, i
, bi
)
2822 if (pseudo_for_reload_consideration_p (i
))
2823 bitmap_set_bit (live_relevant_regs
, i
);
2826 FOR_BB_INSNS_REVERSE (bb
, insn
)
2828 if (!NOTE_P (insn
) && !BARRIER_P (insn
))
2830 unsigned int uid
= INSN_UID (insn
);
2834 c
= new_insn_chain ();
2841 c
->block
= bb
->index
;
2844 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
2846 df_ref def
= *def_rec
;
2847 unsigned int regno
= DF_REF_REGNO (def
);
2849 /* Ignore may clobbers because these are generated
2850 from calls. However, every other kind of def is
2851 added to dead_or_set. */
2852 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
2854 if (regno
< FIRST_PSEUDO_REGISTER
)
2856 if (!fixed_regs
[regno
])
2857 bitmap_set_bit (&c
->dead_or_set
, regno
);
2859 else if (pseudo_for_reload_consideration_p (regno
))
2860 bitmap_set_bit (&c
->dead_or_set
, regno
);
2863 if ((regno
< FIRST_PSEUDO_REGISTER
2864 || reg_renumber
[regno
] >= 0
2866 && (!DF_REF_FLAGS_IS_SET (def
, DF_REF_CONDITIONAL
)))
2868 rtx reg
= DF_REF_REG (def
);
2870 /* We can model subregs, but not if they are
2871 wrapped in ZERO_EXTRACTS. */
2872 if (GET_CODE (reg
) == SUBREG
2873 && !DF_REF_FLAGS_IS_SET (def
, DF_REF_ZERO_EXTRACT
))
2875 unsigned int start
= SUBREG_BYTE (reg
);
2876 unsigned int last
= start
2877 + GET_MODE_SIZE (GET_MODE (reg
));
2880 (bitmap_bit_p (live_relevant_regs
, regno
),
2881 live_subregs
, live_subregs_used
, regno
, reg
);
2883 if (!DF_REF_FLAGS_IS_SET
2884 (def
, DF_REF_STRICT_LOW_PART
))
2886 /* Expand the range to cover entire words.
2887 Bytes added here are "don't care". */
2889 = start
/ UNITS_PER_WORD
* UNITS_PER_WORD
;
2890 last
= ((last
+ UNITS_PER_WORD
- 1)
2891 / UNITS_PER_WORD
* UNITS_PER_WORD
);
2894 /* Ignore the paradoxical bits. */
2895 if ((int)last
> live_subregs_used
[regno
])
2896 last
= live_subregs_used
[regno
];
2898 while (start
< last
)
2900 RESET_BIT (live_subregs
[regno
], start
);
2904 if (sbitmap_empty_p (live_subregs
[regno
]))
2906 live_subregs_used
[regno
] = 0;
2907 bitmap_clear_bit (live_relevant_regs
, regno
);
2910 /* Set live_relevant_regs here because
2911 that bit has to be true to get us to
2912 look at the live_subregs fields. */
2913 bitmap_set_bit (live_relevant_regs
, regno
);
2917 /* DF_REF_PARTIAL is generated for
2918 subregs, STRICT_LOW_PART, and
2919 ZERO_EXTRACT. We handle the subreg
2920 case above so here we have to keep from
2921 modeling the def as a killing def. */
2922 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
))
2924 bitmap_clear_bit (live_relevant_regs
, regno
);
2925 live_subregs_used
[regno
] = 0;
2931 bitmap_and_compl_into (live_relevant_regs
, elim_regset
);
2932 bitmap_copy (&c
->live_throughout
, live_relevant_regs
);
2935 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
2937 df_ref use
= *use_rec
;
2938 unsigned int regno
= DF_REF_REGNO (use
);
2939 rtx reg
= DF_REF_REG (use
);
2941 /* DF_REF_READ_WRITE on a use means that this use
2942 is fabricated from a def that is a partial set
2943 to a multiword reg. Here, we only model the
2944 subreg case that is not wrapped in ZERO_EXTRACT
2945 precisely so we do not need to look at the
2947 if (DF_REF_FLAGS_IS_SET (use
, DF_REF_READ_WRITE
)
2948 && !DF_REF_FLAGS_IS_SET (use
, DF_REF_ZERO_EXTRACT
)
2949 && DF_REF_FLAGS_IS_SET (use
, DF_REF_SUBREG
))
2952 /* Add the last use of each var to dead_or_set. */
2953 if (!bitmap_bit_p (live_relevant_regs
, regno
))
2955 if (regno
< FIRST_PSEUDO_REGISTER
)
2957 if (!fixed_regs
[regno
])
2958 bitmap_set_bit (&c
->dead_or_set
, regno
);
2960 else if (pseudo_for_reload_consideration_p (regno
))
2961 bitmap_set_bit (&c
->dead_or_set
, regno
);
2964 if (regno
< FIRST_PSEUDO_REGISTER
2965 || pseudo_for_reload_consideration_p (regno
))
2967 if (GET_CODE (reg
) == SUBREG
2968 && !DF_REF_FLAGS_IS_SET (use
,
2970 | DF_REF_ZERO_EXTRACT
))
2972 unsigned int start
= SUBREG_BYTE (reg
);
2973 unsigned int last
= start
2974 + GET_MODE_SIZE (GET_MODE (reg
));
2977 (bitmap_bit_p (live_relevant_regs
, regno
),
2978 live_subregs
, live_subregs_used
, regno
, reg
);
2980 /* Ignore the paradoxical bits. */
2981 if ((int)last
> live_subregs_used
[regno
])
2982 last
= live_subregs_used
[regno
];
2984 while (start
< last
)
2986 SET_BIT (live_subregs
[regno
], start
);
2991 /* Resetting the live_subregs_used is
2992 effectively saying do not use the subregs
2993 because we are reading the whole
2995 live_subregs_used
[regno
] = 0;
2996 bitmap_set_bit (live_relevant_regs
, regno
);
3002 /* FIXME!! The following code is a disaster. Reload needs to see the
3003 labels and jump tables that are just hanging out in between
3004 the basic blocks. See pr33676. */
3005 insn
= BB_HEAD (bb
);
3007 /* Skip over the barriers and cruft. */
3008 while (insn
&& (BARRIER_P (insn
) || NOTE_P (insn
)
3009 || BLOCK_FOR_INSN (insn
) == bb
))
3010 insn
= PREV_INSN (insn
);
3012 /* While we add anything except barriers and notes, the focus is
3013 to get the labels and jump tables into the
3014 reload_insn_chain. */
3017 if (!NOTE_P (insn
) && !BARRIER_P (insn
))
3019 if (BLOCK_FOR_INSN (insn
))
3022 c
= new_insn_chain ();
3028 /* The block makes no sense here, but it is what the old
3030 c
->block
= bb
->index
;
3032 bitmap_copy (&c
->live_throughout
, live_relevant_regs
);
3034 insn
= PREV_INSN (insn
);
3038 for (i
= 0; i
< (unsigned int) max_regno
; i
++)
3039 if (live_subregs
[i
])
3040 free (live_subregs
[i
]);
3042 reload_insn_chain
= c
;
3045 free (live_subregs
);
3046 free (live_subregs_used
);
3047 BITMAP_FREE (live_relevant_regs
);
3048 BITMAP_FREE (elim_regset
);
3051 print_insn_chains (dump_file
);
3054 /* Allocate memory for reg_equiv_memory_loc. */
3056 init_reg_equiv_memory_loc (void)
3058 max_regno
= max_reg_num ();
3060 /* And the reg_equiv_memory_loc array. */
3061 VEC_safe_grow (rtx
, gc
, reg_equiv_memory_loc_vec
, max_regno
);
3062 memset (VEC_address (rtx
, reg_equiv_memory_loc_vec
), 0,
3063 sizeof (rtx
) * max_regno
);
3064 reg_equiv_memory_loc
= VEC_address (rtx
, reg_equiv_memory_loc_vec
);
3067 /* All natural loops. */
3068 struct loops ira_loops
;
3070 /* True if we have allocno conflicts. It is false for non-optimized
3071 mode or when the conflict table is too big. */
3072 bool ira_conflicts_p
;
3074 /* This is the main entry of IRA. */
3078 int overall_cost_before
, allocated_reg_info_size
;
3080 int max_regno_before_ira
, ira_max_point_before_emit
;
3082 int saved_flag_ira_share_spill_slots
;
3085 timevar_push (TV_IRA
);
3087 if (flag_caller_saves
)
3088 init_caller_save ();
3090 if (flag_ira_verbose
< 10)
3092 internal_flag_ira_verbose
= flag_ira_verbose
;
3097 internal_flag_ira_verbose
= flag_ira_verbose
- 10;
3098 ira_dump_file
= stderr
;
3101 ira_conflicts_p
= optimize
> 0;
3102 setup_prohibited_mode_move_regs ();
3104 df_note_add_problem ();
3108 df_live_add_problem ();
3109 df_live_set_all_dirty ();
3111 #ifdef ENABLE_CHECKING
3112 df
->changeable_flags
|= DF_VERIFY_SCHEDULED
;
3115 df_clear_flags (DF_NO_INSN_RESCAN
);
3116 regstat_init_n_sets_and_refs ();
3117 regstat_compute_ri ();
3119 /* If we are not optimizing, then this is the only place before
3120 register allocation where dataflow is done. And that is needed
3121 to generate these warnings. */
3123 generate_setjmp_warnings ();
3125 /* Determine if the current function is a leaf before running IRA
3126 since this can impact optimizations done by the prologue and
3127 epilogue thus changing register elimination offsets. */
3128 current_function_is_leaf
= leaf_function_p ();
3130 if (resize_reg_info () && flag_ira_loop_pressure
)
3131 ira_set_pseudo_classes (ira_dump_file
);
3133 rebuild_p
= update_equiv_regs ();
3135 #ifndef IRA_NO_OBSTACK
3136 gcc_obstack_init (&ira_obstack
);
3138 bitmap_obstack_initialize (&ira_bitmap_obstack
);
3141 max_regno
= max_reg_num ();
3142 ira_reg_equiv_len
= max_regno
;
3143 ira_reg_equiv_invariant_p
3144 = (bool *) ira_allocate (max_regno
* sizeof (bool));
3145 memset (ira_reg_equiv_invariant_p
, 0, max_regno
* sizeof (bool));
3146 ira_reg_equiv_const
= (rtx
*) ira_allocate (max_regno
* sizeof (rtx
));
3147 memset (ira_reg_equiv_const
, 0, max_regno
* sizeof (rtx
));
3148 find_reg_equiv_invariant_const ();
3151 timevar_push (TV_JUMP
);
3152 rebuild_jump_labels (get_insns ());
3153 if (purge_all_dead_edges ())
3154 delete_unreachable_blocks ();
3155 timevar_pop (TV_JUMP
);
3159 max_regno_before_ira
= allocated_reg_info_size
= max_reg_num ();
3160 ira_setup_eliminable_regset ();
3162 ira_overall_cost
= ira_reg_cost
= ira_mem_cost
= 0;
3163 ira_load_cost
= ira_store_cost
= ira_shuffle_cost
= 0;
3164 ira_move_loops_num
= ira_additional_jumps_num
= 0;
3166 ira_assert (current_loops
== NULL
);
3167 flow_loops_find (&ira_loops
);
3168 record_loop_exits ();
3169 current_loops
= &ira_loops
;
3171 init_reg_equiv_memory_loc ();
3173 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
3174 fprintf (ira_dump_file
, "Building IRA IR\n");
3175 loops_p
= ira_build (optimize
3176 && (flag_ira_region
== IRA_REGION_ALL
3177 || flag_ira_region
== IRA_REGION_MIXED
));
3179 ira_assert (ira_conflicts_p
|| !loops_p
);
3181 saved_flag_ira_share_spill_slots
= flag_ira_share_spill_slots
;
3182 if (too_high_register_pressure_p () || cfun
->calls_setjmp
)
3183 /* It is just wasting compiler's time to pack spilled pseudos into
3184 stack slots in this case -- prohibit it. We also do this if
3185 there is setjmp call because a variable not modified between
3186 setjmp and longjmp the compiler is required to preserve its
3187 value and sharing slots does not guarantee it. */
3188 flag_ira_share_spill_slots
= FALSE
;
3192 ira_max_point_before_emit
= ira_max_point
;
3196 if (ira_conflicts_p
)
3198 max_regno
= max_reg_num ();
3201 ira_initiate_assign ();
3204 expand_reg_info (allocated_reg_info_size
);
3205 setup_preferred_alternate_classes_for_new_pseudos
3206 (allocated_reg_info_size
);
3207 allocated_reg_info_size
= max_regno
;
3209 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
3210 fprintf (ira_dump_file
, "Flattening IR\n");
3211 ira_flattening (max_regno_before_ira
, ira_max_point_before_emit
);
3212 /* New insns were generated: add notes and recalculate live
3216 flow_loops_find (&ira_loops
);
3217 record_loop_exits ();
3218 current_loops
= &ira_loops
;
3220 setup_allocno_assignment_flags ();
3221 ira_initiate_assign ();
3222 ira_reassign_conflict_allocnos (max_regno
);
3226 setup_reg_renumber ();
3228 calculate_allocation_cost ();
3230 #ifdef ENABLE_IRA_CHECKING
3231 if (ira_conflicts_p
)
3232 check_allocation ();
3235 delete_trivially_dead_insns (get_insns (), max_reg_num ());
3237 init_reg_equiv_memory_loc ();
3239 if (max_regno
!= max_regno_before_ira
)
3241 regstat_free_n_sets_and_refs ();
3243 regstat_init_n_sets_and_refs ();
3244 regstat_compute_ri ();
3247 allocate_initial_values (reg_equiv_memory_loc
);
3249 overall_cost_before
= ira_overall_cost
;
3250 if (ira_conflicts_p
)
3252 fix_reg_equiv_init ();
3254 #ifdef ENABLE_IRA_CHECKING
3255 print_redundant_copies ();
3258 ira_spilled_reg_stack_slots_num
= 0;
3259 ira_spilled_reg_stack_slots
3260 = ((struct ira_spilled_reg_stack_slot
*)
3261 ira_allocate (max_regno
3262 * sizeof (struct ira_spilled_reg_stack_slot
)));
3263 memset (ira_spilled_reg_stack_slots
, 0,
3264 max_regno
* sizeof (struct ira_spilled_reg_stack_slot
));
3267 timevar_pop (TV_IRA
);
3269 timevar_push (TV_RELOAD
);
3270 df_set_flags (DF_NO_INSN_RESCAN
);
3271 build_insn_chain ();
3273 reload_completed
= !reload (get_insns (), ira_conflicts_p
);
3275 timevar_pop (TV_RELOAD
);
3277 timevar_push (TV_IRA
);
3279 if (ira_conflicts_p
)
3281 ira_free (ira_spilled_reg_stack_slots
);
3283 ira_finish_assign ();
3286 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
3287 && overall_cost_before
!= ira_overall_cost
)
3288 fprintf (ira_dump_file
, "+++Overall after reload %d\n", ira_overall_cost
);
3291 flag_ira_share_spill_slots
= saved_flag_ira_share_spill_slots
;
3293 flow_loops_free (&ira_loops
);
3294 free_dominance_info (CDI_DOMINATORS
);
3296 bb
->loop_father
= NULL
;
3297 current_loops
= NULL
;
3300 regstat_free_n_sets_and_refs ();
3304 cleanup_cfg (CLEANUP_EXPENSIVE
);
3306 ira_free (ira_reg_equiv_invariant_p
);
3307 ira_free (ira_reg_equiv_const
);
3310 bitmap_obstack_release (&ira_bitmap_obstack
);
3311 #ifndef IRA_NO_OBSTACK
3312 obstack_free (&ira_obstack
, NULL
);
3315 /* The code after the reload has changed so much that at this point
3316 we might as well just rescan everything. Not that
3317 df_rescan_all_insns is not going to help here because it does not
3318 touch the artificial uses and defs. */
3319 df_finish_pass (true);
3321 df_live_add_problem ();
3322 df_scan_alloc (NULL
);
3328 timevar_pop (TV_IRA
);
3339 /* Run the integrated register allocator. */
3341 rest_of_handle_ira (void)
3347 struct rtl_opt_pass pass_ira
=
3352 gate_ira
, /* gate */
3353 rest_of_handle_ira
, /* execute */
3356 0, /* static_pass_number */
3357 TV_NONE
, /* tv_id */
3358 0, /* properties_required */
3359 0, /* properties_provided */
3360 0, /* properties_destroyed */
3361 0, /* todo_flags_start */
3363 TODO_ggc_collect
/* todo_flags_finish */