1 /* Integrated Register Allocator (IRA) entry point.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011, 2012
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 *Allocno class* is a register class used for allocation of
42 given allocno. It means that only hard register of given
43 register class can be assigned to given allocno. In reality,
44 even smaller subset of (*profitable*) hard registers can be
45 assigned. In rare cases, the subset can be even smaller
46 because our modification of Chaitin-Briggs algorithm requires
47 that sets of hard registers can be assigned to allocnos forms a
48 forest, i.e. the sets can be ordered in a way where any
49 previous set is not intersected with given set or is a superset
52 o *Pressure class* is a register class belonging to a set of
53 register classes containing all of the hard-registers available
54 for register allocation. The set of all pressure classes for a
55 target is defined in the corresponding machine-description file
56 according some criteria. Register pressure is calculated only
57 for pressure classes and it affects some IRA decisions as
58 forming allocation regions.
60 o *Allocno* represents the live range of a pseudo-register in a
61 region. Besides the obvious attributes like the corresponding
62 pseudo-register number, allocno class, conflicting allocnos and
63 conflicting hard-registers, there are a few allocno attributes
64 which are important for understanding the allocation algorithm:
66 - *Live ranges*. This is a list of ranges of *program points*
67 where the allocno lives. Program points represent places
68 where a pseudo can be born or become dead (there are
69 approximately two times more program points than the insns)
70 and they are represented by integers starting with 0. The
71 live ranges are used to find conflicts between allocnos.
72 They also play very important role for the transformation of
73 the IRA internal representation of several regions into a one
74 region representation. The later is used during the reload
75 pass work because each allocno represents all of the
76 corresponding pseudo-registers.
78 - *Hard-register costs*. This is a vector of size equal to the
79 number of available hard-registers of the allocno class. The
80 cost of a callee-clobbered hard-register for an allocno is
81 increased by the cost of save/restore code around the calls
82 through the given allocno's life. If the allocno is a move
83 instruction operand and another operand is a hard-register of
84 the allocno class, the cost of the hard-register is decreased
87 When an allocno is assigned, the hard-register with minimal
88 full cost is used. Initially, a hard-register's full cost is
89 the corresponding value from the hard-register's cost vector.
90 If the allocno is connected by a *copy* (see below) to
91 another allocno which has just received a hard-register, the
92 cost of the hard-register is decreased. Before choosing a
93 hard-register for an allocno, the allocno's current costs of
94 the hard-registers are modified by the conflict hard-register
95 costs of all of the conflicting allocnos which are not
98 - *Conflict hard-register costs*. This is a vector of the same
99 size as the hard-register costs vector. To permit an
100 unassigned allocno to get a better hard-register, IRA uses
101 this vector to calculate the final full cost of the
102 available hard-registers. Conflict hard-register costs of an
103 unassigned allocno are also changed with a change of the
104 hard-register cost of the allocno when a copy involving the
105 allocno is processed as described above. This is done to
106 show other unassigned allocnos that a given allocno prefers
107 some hard-registers in order to remove the move instruction
108 corresponding to the copy.
110 o *Cap*. If a pseudo-register does not live in a region but
111 lives in a nested region, IRA creates a special allocno called
112 a cap in the outer region. A region cap is also created for a
115 o *Copy*. Allocnos can be connected by copies. Copies are used
116 to modify hard-register costs for allocnos during coloring.
117 Such modifications reflects a preference to use the same
118 hard-register for the allocnos connected by copies. Usually
119 copies are created for move insns (in this case it results in
120 register coalescing). But IRA also creates copies for operands
121 of an insn which should be assigned to the same hard-register
122 due to constraints in the machine description (it usually
123 results in removing a move generated in reload to satisfy
124 the constraints) and copies referring to the allocno which is
125 the output operand of an instruction and the allocno which is
126 an input operand dying in the instruction (creation of such
127 copies results in less register shuffling). IRA *does not*
128 create copies between the same register allocnos from different
129 regions because we use another technique for propagating
130 hard-register preference on the borders of regions.
132 Allocnos (including caps) for the upper region in the region tree
133 *accumulate* information important for coloring from allocnos with
134 the same pseudo-register from nested regions. This includes
135 hard-register and memory costs, conflicts with hard-registers,
136 allocno conflicts, allocno copies and more. *Thus, attributes for
137 allocnos in a region have the same values as if the region had no
138 subregions*. It means that attributes for allocnos in the
139 outermost region corresponding to the function have the same values
140 as though the allocation used only one region which is the entire
141 function. It also means that we can look at IRA work as if the
142 first IRA did allocation for all function then it improved the
143 allocation for loops then their subloops and so on.
145 IRA major passes are:
147 o Building IRA internal representation which consists of the
150 * First, IRA builds regions and creates allocnos (file
151 ira-build.c) and initializes most of their attributes.
153 * Then IRA finds an allocno class for each allocno and
154 calculates its initial (non-accumulated) cost of memory and
155 each hard-register of its allocno class (file ira-cost.c).
157 * IRA creates live ranges of each allocno, calulates register
158 pressure for each pressure class in each region, sets up
159 conflict hard registers for each allocno and info about calls
160 the allocno lives through (file ira-lives.c).
162 * IRA removes low register pressure loops from the regions
163 mostly to speed IRA up (file ira-build.c).
165 * IRA propagates accumulated allocno info from lower region
166 allocnos to corresponding upper region allocnos (file
169 * IRA creates all caps (file ira-build.c).
171 * Having live-ranges of allocnos and their classes, IRA creates
172 conflicting allocnos for each allocno. Conflicting allocnos
173 are stored as a bit vector or array of pointers to the
174 conflicting allocnos whatever is more profitable (file
175 ira-conflicts.c). At this point IRA creates allocno copies.
177 o Coloring. Now IRA has all necessary info to start graph coloring
178 process. It is done in each region on top-down traverse of the
179 region tree (file ira-color.c). There are following subpasses:
181 * Finding profitable hard registers of corresponding allocno
182 class for each allocno. For example, only callee-saved hard
183 registers are frequently profitable for allocnos living
184 through colors. If the profitable hard register set of
185 allocno does not form a tree based on subset relation, we use
186 some approximation to form the tree. This approximation is
187 used to figure out trivial colorability of allocnos. The
188 approximation is a pretty rare case.
190 * Putting allocnos onto the coloring stack. IRA uses Briggs
191 optimistic coloring which is a major improvement over
192 Chaitin's coloring. Therefore IRA does not spill allocnos at
193 this point. There is some freedom in the order of putting
194 allocnos on the stack which can affect the final result of
195 the allocation. IRA uses some heuristics to improve the
198 We also use a modification of Chaitin-Briggs algorithm which
199 works for intersected register classes of allocnos. To
200 figure out trivial colorability of allocnos, the mentioned
201 above tree of hard register sets is used. To get an idea how
202 the algorithm works in i386 example, let us consider an
203 allocno to which any general hard register can be assigned.
204 If the allocno conflicts with eight allocnos to which only
205 EAX register can be assigned, given allocno is still
206 trivially colorable because all conflicting allocnos might be
207 assigned only to EAX and all other general hard registers are
210 To get an idea of the used trivial colorability criterion, it
211 is also useful to read article "Graph-Coloring Register
212 Allocation for Irregular Architectures" by Michael D. Smith
213 and Glen Holloway. Major difference between the article
214 approach and approach used in IRA is that Smith's approach
215 takes register classes only from machine description and IRA
216 calculate register classes from intermediate code too
217 (e.g. an explicit usage of hard registers in RTL code for
218 parameter passing can result in creation of additional
219 register classes which contain or exclude the hard
220 registers). That makes IRA approach useful for improving
221 coloring even for architectures with regular register files
222 and in fact some benchmarking shows the improvement for
223 regular class architectures is even bigger than for irregular
224 ones. Another difference is that Smith's approach chooses
225 intersection of classes of all insn operands in which a given
226 pseudo occurs. IRA can use bigger classes if it is still
227 more profitable than memory usage.
229 * Popping the allocnos from the stack and assigning them hard
230 registers. If IRA can not assign a hard register to an
231 allocno and the allocno is coalesced, IRA undoes the
232 coalescing and puts the uncoalesced allocnos onto the stack in
233 the hope that some such allocnos will get a hard register
234 separately. If IRA fails to assign hard register or memory
235 is more profitable for it, IRA spills the allocno. IRA
236 assigns the allocno the hard-register with minimal full
237 allocation cost which reflects the cost of usage of the
238 hard-register for the allocno and cost of usage of the
239 hard-register for allocnos conflicting with given allocno.
241 * Chaitin-Briggs coloring assigns as many pseudos as possible
242 to hard registers. After coloringh we try to improve
243 allocation with cost point of view. We improve the
244 allocation by spilling some allocnos and assigning the freed
245 hard registers to other allocnos if it decreases the overall
248 * After allono assigning in the region, IRA modifies the hard
249 register and memory costs for the corresponding allocnos in
250 the subregions to reflect the cost of possible loads, stores,
251 or moves on the border of the region and its subregions.
252 When default regional allocation algorithm is used
253 (-fira-algorithm=mixed), IRA just propagates the assignment
254 for allocnos if the register pressure in the region for the
255 corresponding pressure class is less than number of available
256 hard registers for given pressure class.
258 o Spill/restore code moving. When IRA performs an allocation
259 by traversing regions in top-down order, it does not know what
260 happens below in the region tree. Therefore, sometimes IRA
261 misses opportunities to perform a better allocation. A simple
262 optimization tries to improve allocation in a region having
263 subregions and containing in another region. If the
264 corresponding allocnos in the subregion are spilled, it spills
265 the region allocno if it is profitable. The optimization
266 implements a simple iterative algorithm performing profitable
267 transformations while they are still possible. It is fast in
268 practice, so there is no real need for a better time complexity
271 o Code change. After coloring, two allocnos representing the
272 same pseudo-register outside and inside a region respectively
273 may be assigned to different locations (hard-registers or
274 memory). In this case IRA creates and uses a new
275 pseudo-register inside the region and adds code to move allocno
276 values on the region's borders. This is done during top-down
277 traversal of the regions (file ira-emit.c). In some
278 complicated cases IRA can create a new allocno to move allocno
279 values (e.g. when a swap of values stored in two hard-registers
280 is needed). At this stage, the new allocno is marked as
281 spilled. IRA still creates the pseudo-register and the moves
282 on the region borders even when both allocnos were assigned to
283 the same hard-register. If the reload pass spills a
284 pseudo-register for some reason, the effect will be smaller
285 because another allocno will still be in the hard-register. In
286 most cases, this is better then spilling both allocnos. If
287 reload does not change the allocation for the two
288 pseudo-registers, the trivial move will be removed by
289 post-reload optimizations. IRA does not generate moves for
290 allocnos assigned to the same hard register when the default
291 regional allocation algorithm is used and the register pressure
292 in the region for the corresponding pressure class is less than
293 number of available hard registers for given pressure class.
294 IRA also does some optimizations to remove redundant stores and
295 to reduce code duplication on the region borders.
297 o Flattening internal representation. After changing code, IRA
298 transforms its internal representation for several regions into
299 one region representation (file ira-build.c). This process is
300 called IR flattening. Such process is more complicated than IR
301 rebuilding would be, but is much faster.
303 o After IR flattening, IRA tries to assign hard registers to all
304 spilled allocnos. This is impelemented by a simple and fast
305 priority coloring algorithm (see function
306 ira_reassign_conflict_allocnos::ira-color.c). Here new allocnos
307 created during the code change pass can be assigned to hard
310 o At the end IRA calls the reload pass. The reload pass
311 communicates with IRA through several functions in file
312 ira-color.c to improve its decisions in
314 * sharing stack slots for the spilled pseudos based on IRA info
315 about pseudo-register conflicts.
317 * reassigning hard-registers to all spilled pseudos at the end
318 of each reload iteration.
320 * choosing a better hard-register to spill based on IRA info
321 about pseudo-register live ranges and the register pressure
322 in places where the pseudo-register lives.
324 IRA uses a lot of data representing the target processors. These
325 data are initilized in file ira.c.
327 If function has no loops (or the loops are ignored when
328 -fira-algorithm=CB is used), we have classic Chaitin-Briggs
329 coloring (only instead of separate pass of coalescing, we use hard
330 register preferencing). In such case, IRA works much faster
331 because many things are not made (like IR flattening, the
332 spill/restore optimization, and the code change).
334 Literature is worth to read for better understanding the code:
336 o Preston Briggs, Keith D. Cooper, Linda Torczon. Improvements to
337 Graph Coloring Register Allocation.
339 o David Callahan, Brian Koblenz. Register allocation via
340 hierarchical graph coloring.
342 o Keith Cooper, Anshuman Dasgupta, Jason Eckhardt. Revisiting Graph
343 Coloring Register Allocation: A Study of the Chaitin-Briggs and
344 Callahan-Koblenz Algorithms.
346 o Guei-Yuan Lueh, Thomas Gross, and Ali-Reza Adl-Tabatabai. Global
347 Register Allocation Based on Graph Fusion.
349 o Michael D. Smith and Glenn Holloway. Graph-Coloring Register
350 Allocation for Irregular Architectures
352 o Vladimir Makarov. The Integrated Register Allocator for GCC.
354 o Vladimir Makarov. The top-down register allocator for irregular
355 register file architectures.
362 #include "coretypes.h"
371 #include "hard-reg-set.h"
372 #include "basic-block.h"
377 #include "tree-pass.h"
381 #include "diagnostic-core.h"
382 #include "function.h"
388 struct target_ira default_target_ira
;
389 struct target_ira_int default_target_ira_int
;
390 #if SWITCHABLE_TARGET
391 struct target_ira
*this_target_ira
= &default_target_ira
;
392 struct target_ira_int
*this_target_ira_int
= &default_target_ira_int
;
395 /* A modified value of flag `-fira-verbose' used internally. */
396 int internal_flag_ira_verbose
;
398 /* Dump file of the allocator if it is not NULL. */
401 /* The number of elements in the following array. */
402 int ira_spilled_reg_stack_slots_num
;
404 /* The following array contains info about spilled pseudo-registers
405 stack slots used in current function so far. */
406 struct ira_spilled_reg_stack_slot
*ira_spilled_reg_stack_slots
;
408 /* Correspondingly overall cost of the allocation, overall cost before
409 reload, cost of the allocnos assigned to hard-registers, cost of
410 the allocnos assigned to memory, cost of loads, stores and register
411 move insns generated for pseudo-register live range splitting (see
413 int ira_overall_cost
, overall_cost_before
;
414 int ira_reg_cost
, ira_mem_cost
;
415 int ira_load_cost
, ira_store_cost
, ira_shuffle_cost
;
416 int ira_move_loops_num
, ira_additional_jumps_num
;
418 /* All registers that can be eliminated. */
420 HARD_REG_SET eliminable_regset
;
422 /* Temporary hard reg set used for a different calculation. */
423 static HARD_REG_SET temp_hard_regset
;
425 #define last_mode_for_init_move_cost \
426 (this_target_ira_int->x_last_mode_for_init_move_cost)
429 /* The function sets up the map IRA_REG_MODE_HARD_REGSET. */
431 setup_reg_mode_hard_regset (void)
433 int i
, m
, hard_regno
;
435 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
436 for (hard_regno
= 0; hard_regno
< FIRST_PSEUDO_REGISTER
; hard_regno
++)
438 CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset
[hard_regno
][m
]);
439 for (i
= hard_regno_nregs
[hard_regno
][m
] - 1; i
>= 0; i
--)
440 if (hard_regno
+ i
< FIRST_PSEUDO_REGISTER
)
441 SET_HARD_REG_BIT (ira_reg_mode_hard_regset
[hard_regno
][m
],
447 #define no_unit_alloc_regs \
448 (this_target_ira_int->x_no_unit_alloc_regs)
450 /* The function sets up the three arrays declared above. */
452 setup_class_hard_regs (void)
454 int cl
, i
, hard_regno
, n
;
455 HARD_REG_SET processed_hard_reg_set
;
457 ira_assert (SHRT_MAX
>= FIRST_PSEUDO_REGISTER
);
458 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
460 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
461 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
462 CLEAR_HARD_REG_SET (processed_hard_reg_set
);
463 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
465 ira_non_ordered_class_hard_regs
[cl
][i
] = -1;
466 ira_class_hard_reg_index
[cl
][i
] = -1;
468 for (n
= 0, i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
470 #ifdef REG_ALLOC_ORDER
471 hard_regno
= reg_alloc_order
[i
];
475 if (TEST_HARD_REG_BIT (processed_hard_reg_set
, hard_regno
))
477 SET_HARD_REG_BIT (processed_hard_reg_set
, hard_regno
);
478 if (! TEST_HARD_REG_BIT (temp_hard_regset
, hard_regno
))
479 ira_class_hard_reg_index
[cl
][hard_regno
] = -1;
482 ira_class_hard_reg_index
[cl
][hard_regno
] = n
;
483 ira_class_hard_regs
[cl
][n
++] = hard_regno
;
486 ira_class_hard_regs_num
[cl
] = n
;
487 for (n
= 0, i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
488 if (TEST_HARD_REG_BIT (temp_hard_regset
, i
))
489 ira_non_ordered_class_hard_regs
[cl
][n
++] = i
;
490 ira_assert (ira_class_hard_regs_num
[cl
] == n
);
494 /* Set up global variables defining info about hard registers for the
495 allocation. These depend on USE_HARD_FRAME_P whose TRUE value means
496 that we can use the hard frame pointer for the allocation. */
498 setup_alloc_regs (bool use_hard_frame_p
)
500 #ifdef ADJUST_REG_ALLOC_ORDER
501 ADJUST_REG_ALLOC_ORDER
;
503 COPY_HARD_REG_SET (no_unit_alloc_regs
, fixed_reg_set
);
504 if (! use_hard_frame_p
)
505 SET_HARD_REG_BIT (no_unit_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
506 setup_class_hard_regs ();
511 #define alloc_reg_class_subclasses \
512 (this_target_ira_int->x_alloc_reg_class_subclasses)
514 /* Initialize the table of subclasses of each reg class. */
516 setup_reg_subclasses (void)
519 HARD_REG_SET temp_hard_regset2
;
521 for (i
= 0; i
< N_REG_CLASSES
; i
++)
522 for (j
= 0; j
< N_REG_CLASSES
; j
++)
523 alloc_reg_class_subclasses
[i
][j
] = LIM_REG_CLASSES
;
525 for (i
= 0; i
< N_REG_CLASSES
; i
++)
527 if (i
== (int) NO_REGS
)
530 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[i
]);
531 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
532 if (hard_reg_set_empty_p (temp_hard_regset
))
534 for (j
= 0; j
< N_REG_CLASSES
; j
++)
539 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[j
]);
540 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
541 if (! hard_reg_set_subset_p (temp_hard_regset
,
544 p
= &alloc_reg_class_subclasses
[j
][0];
545 while (*p
!= LIM_REG_CLASSES
) p
++;
546 *p
= (enum reg_class
) i
;
553 /* Set up IRA_MEMORY_MOVE_COST and IRA_MAX_MEMORY_MOVE_COST. */
555 setup_class_subset_and_memory_move_costs (void)
557 int cl
, cl2
, mode
, cost
;
558 HARD_REG_SET temp_hard_regset2
;
560 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
561 ira_memory_move_cost
[mode
][NO_REGS
][0]
562 = ira_memory_move_cost
[mode
][NO_REGS
][1] = SHRT_MAX
;
563 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
565 if (cl
!= (int) NO_REGS
)
566 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
568 ira_max_memory_move_cost
[mode
][cl
][0]
569 = ira_memory_move_cost
[mode
][cl
][0]
570 = memory_move_cost ((enum machine_mode
) mode
,
571 (reg_class_t
) cl
, false);
572 ira_max_memory_move_cost
[mode
][cl
][1]
573 = ira_memory_move_cost
[mode
][cl
][1]
574 = memory_move_cost ((enum machine_mode
) mode
,
575 (reg_class_t
) cl
, true);
576 /* Costs for NO_REGS are used in cost calculation on the
577 1st pass when the preferred register classes are not
578 known yet. In this case we take the best scenario. */
579 if (ira_memory_move_cost
[mode
][NO_REGS
][0]
580 > ira_memory_move_cost
[mode
][cl
][0])
581 ira_max_memory_move_cost
[mode
][NO_REGS
][0]
582 = ira_memory_move_cost
[mode
][NO_REGS
][0]
583 = ira_memory_move_cost
[mode
][cl
][0];
584 if (ira_memory_move_cost
[mode
][NO_REGS
][1]
585 > ira_memory_move_cost
[mode
][cl
][1])
586 ira_max_memory_move_cost
[mode
][NO_REGS
][1]
587 = ira_memory_move_cost
[mode
][NO_REGS
][1]
588 = ira_memory_move_cost
[mode
][cl
][1];
591 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
592 for (cl2
= (int) N_REG_CLASSES
- 1; cl2
>= 0; cl2
--)
594 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
595 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
596 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl2
]);
597 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
598 ira_class_subset_p
[cl
][cl2
]
599 = hard_reg_set_subset_p (temp_hard_regset
, temp_hard_regset2
);
600 if (! hard_reg_set_empty_p (temp_hard_regset2
)
601 && hard_reg_set_subset_p (reg_class_contents
[cl2
],
602 reg_class_contents
[cl
]))
603 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
605 cost
= ira_memory_move_cost
[mode
][cl2
][0];
606 if (cost
> ira_max_memory_move_cost
[mode
][cl
][0])
607 ira_max_memory_move_cost
[mode
][cl
][0] = cost
;
608 cost
= ira_memory_move_cost
[mode
][cl2
][1];
609 if (cost
> ira_max_memory_move_cost
[mode
][cl
][1])
610 ira_max_memory_move_cost
[mode
][cl
][1] = cost
;
613 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
614 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
616 ira_memory_move_cost
[mode
][cl
][0]
617 = ira_max_memory_move_cost
[mode
][cl
][0];
618 ira_memory_move_cost
[mode
][cl
][1]
619 = ira_max_memory_move_cost
[mode
][cl
][1];
621 setup_reg_subclasses ();
626 /* Define the following macro if allocation through malloc if
628 #define IRA_NO_OBSTACK
630 #ifndef IRA_NO_OBSTACK
631 /* Obstack used for storing all dynamic data (except bitmaps) of the
633 static struct obstack ira_obstack
;
636 /* Obstack used for storing all bitmaps of the IRA. */
637 static struct bitmap_obstack ira_bitmap_obstack
;
639 /* Allocate memory of size LEN for IRA data. */
641 ira_allocate (size_t len
)
645 #ifndef IRA_NO_OBSTACK
646 res
= obstack_alloc (&ira_obstack
, len
);
653 /* Free memory ADDR allocated for IRA data. */
655 ira_free (void *addr ATTRIBUTE_UNUSED
)
657 #ifndef IRA_NO_OBSTACK
665 /* Allocate and returns bitmap for IRA. */
667 ira_allocate_bitmap (void)
669 return BITMAP_ALLOC (&ira_bitmap_obstack
);
672 /* Free bitmap B allocated for IRA. */
674 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED
)
681 /* Output information about allocation of all allocnos (except for
682 caps) into file F. */
684 ira_print_disposition (FILE *f
)
690 fprintf (f
, "Disposition:");
691 max_regno
= max_reg_num ();
692 for (n
= 0, i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
693 for (a
= ira_regno_allocno_map
[i
];
695 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
700 fprintf (f
, " %4d:r%-4d", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
701 if ((bb
= ALLOCNO_LOOP_TREE_NODE (a
)->bb
) != NULL
)
702 fprintf (f
, "b%-3d", bb
->index
);
704 fprintf (f
, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a
)->loop_num
);
705 if (ALLOCNO_HARD_REGNO (a
) >= 0)
706 fprintf (f
, " %3d", ALLOCNO_HARD_REGNO (a
));
713 /* Outputs information about allocation of all allocnos into
716 ira_debug_disposition (void)
718 ira_print_disposition (stderr
);
723 /* Set up ira_stack_reg_pressure_class which is the biggest pressure
724 register class containing stack registers or NO_REGS if there are
725 no stack registers. To find this class, we iterate through all
726 register pressure classes and choose the first register pressure
727 class containing all the stack registers and having the biggest
730 setup_stack_reg_pressure_class (void)
732 ira_stack_reg_pressure_class
= NO_REGS
;
737 HARD_REG_SET temp_hard_regset2
;
739 CLEAR_HARD_REG_SET (temp_hard_regset
);
740 for (i
= FIRST_STACK_REG
; i
<= LAST_STACK_REG
; i
++)
741 SET_HARD_REG_BIT (temp_hard_regset
, i
);
743 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
745 cl
= ira_pressure_classes
[i
];
746 COPY_HARD_REG_SET (temp_hard_regset2
, temp_hard_regset
);
747 AND_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl
]);
748 size
= hard_reg_set_size (temp_hard_regset2
);
752 ira_stack_reg_pressure_class
= cl
;
759 /* Find pressure classes which are register classes for which we
760 calculate register pressure in IRA, register pressure sensitive
761 insn scheduling, and register pressure sensitive loop invariant
764 To make register pressure calculation easy, we always use
765 non-intersected register pressure classes. A move of hard
766 registers from one register pressure class is not more expensive
767 than load and store of the hard registers. Most likely an allocno
768 class will be a subset of a register pressure class and in many
769 cases a register pressure class. That makes usage of register
770 pressure classes a good approximation to find a high register
773 setup_pressure_classes (void)
775 int cost
, i
, n
, curr
;
777 enum reg_class pressure_classes
[N_REG_CLASSES
];
779 HARD_REG_SET temp_hard_regset2
;
783 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
785 if (ira_class_hard_regs_num
[cl
] == 0)
787 if (ira_class_hard_regs_num
[cl
] != 1
788 /* A register class without subclasses may contain a few
789 hard registers and movement between them is costly
790 (e.g. SPARC FPCC registers). We still should consider it
791 as a candidate for a pressure class. */
792 && alloc_reg_class_subclasses
[cl
][0] < cl
)
794 /* Check that the moves between any hard registers of the
795 current class are not more expensive for a legal mode
796 than load/store of the hard registers of the current
797 class. Such class is a potential candidate to be a
798 register pressure class. */
799 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
801 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
802 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
803 AND_COMPL_HARD_REG_SET (temp_hard_regset
,
804 ira_prohibited_class_mode_regs
[cl
][m
]);
805 if (hard_reg_set_empty_p (temp_hard_regset
))
807 ira_init_register_move_cost_if_necessary ((enum machine_mode
) m
);
808 cost
= ira_register_move_cost
[m
][cl
][cl
];
809 if (cost
<= ira_max_memory_move_cost
[m
][cl
][1]
810 || cost
<= ira_max_memory_move_cost
[m
][cl
][0])
813 if (m
>= NUM_MACHINE_MODES
)
818 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
819 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
820 /* Remove so far added pressure classes which are subset of the
821 current candidate class. Prefer GENERAL_REGS as a pressure
822 register class to another class containing the same
823 allocatable hard registers. We do this because machine
824 dependent cost hooks might give wrong costs for the latter
825 class but always give the right cost for the former class
827 for (i
= 0; i
< n
; i
++)
829 cl2
= pressure_classes
[i
];
830 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl2
]);
831 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
832 if (hard_reg_set_subset_p (temp_hard_regset
, temp_hard_regset2
)
833 && (! hard_reg_set_equal_p (temp_hard_regset
, temp_hard_regset2
)
834 || cl2
== (int) GENERAL_REGS
))
836 pressure_classes
[curr
++] = (enum reg_class
) cl2
;
840 if (hard_reg_set_subset_p (temp_hard_regset2
, temp_hard_regset
)
841 && (! hard_reg_set_equal_p (temp_hard_regset2
, temp_hard_regset
)
842 || cl
== (int) GENERAL_REGS
))
844 if (hard_reg_set_equal_p (temp_hard_regset2
, temp_hard_regset
))
846 pressure_classes
[curr
++] = (enum reg_class
) cl2
;
848 /* If the current candidate is a subset of a so far added
849 pressure class, don't add it to the list of the pressure
852 pressure_classes
[curr
++] = (enum reg_class
) cl
;
855 #ifdef ENABLE_IRA_CHECKING
857 HARD_REG_SET ignore_hard_regs
;
859 /* Check pressure classes correctness: here we check that hard
860 registers from all register pressure classes contains all hard
861 registers available for the allocation. */
862 CLEAR_HARD_REG_SET (temp_hard_regset
);
863 CLEAR_HARD_REG_SET (temp_hard_regset2
);
864 COPY_HARD_REG_SET (ignore_hard_regs
, no_unit_alloc_regs
);
865 for (cl
= 0; cl
< LIM_REG_CLASSES
; cl
++)
867 /* For some targets (like MIPS with MD_REGS), there are some
868 classes with hard registers available for allocation but
869 not able to hold value of any mode. */
870 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
871 if (contains_reg_of_mode
[cl
][m
])
873 if (m
>= NUM_MACHINE_MODES
)
875 IOR_HARD_REG_SET (ignore_hard_regs
, reg_class_contents
[cl
]);
878 for (i
= 0; i
< n
; i
++)
879 if ((int) pressure_classes
[i
] == cl
)
881 IOR_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl
]);
883 IOR_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
885 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
886 /* Some targets (like SPARC with ICC reg) have alocatable regs
887 for which no reg class is defined. */
888 if (REGNO_REG_CLASS (i
) == NO_REGS
)
889 SET_HARD_REG_BIT (ignore_hard_regs
, i
);
890 AND_COMPL_HARD_REG_SET (temp_hard_regset
, ignore_hard_regs
);
891 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, ignore_hard_regs
);
892 ira_assert (hard_reg_set_subset_p (temp_hard_regset2
, temp_hard_regset
));
895 ira_pressure_classes_num
= 0;
896 for (i
= 0; i
< n
; i
++)
898 cl
= (int) pressure_classes
[i
];
899 ira_reg_pressure_class_p
[cl
] = true;
900 ira_pressure_classes
[ira_pressure_classes_num
++] = (enum reg_class
) cl
;
902 setup_stack_reg_pressure_class ();
905 /* Set up IRA_UNIFORM_CLASS_P. Uniform class is a register class
906 whose register move cost between any registers of the class is the
907 same as for all its subclasses. We use the data to speed up the
908 2nd pass of calculations of allocno costs. */
910 setup_uniform_class_p (void)
914 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
916 ira_uniform_class_p
[cl
] = false;
917 if (ira_class_hard_regs_num
[cl
] == 0)
919 /* We can not use alloc_reg_class_subclasses here because move
920 cost hooks does not take into account that some registers are
921 unavailable for the subtarget. E.g. for i686, INT_SSE_REGS
922 is element of alloc_reg_class_subclasses for GENERAL_REGS
923 because SSE regs are unavailable. */
924 for (i
= 0; (cl2
= reg_class_subclasses
[cl
][i
]) != LIM_REG_CLASSES
; i
++)
926 if (ira_class_hard_regs_num
[cl2
] == 0)
928 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
929 if (contains_reg_of_mode
[cl
][m
] && contains_reg_of_mode
[cl2
][m
])
931 ira_init_register_move_cost_if_necessary ((enum machine_mode
) m
);
932 if (ira_register_move_cost
[m
][cl
][cl
]
933 != ira_register_move_cost
[m
][cl2
][cl2
])
936 if (m
< NUM_MACHINE_MODES
)
939 if (cl2
== LIM_REG_CLASSES
)
940 ira_uniform_class_p
[cl
] = true;
944 /* Set up IRA_ALLOCNO_CLASSES, IRA_ALLOCNO_CLASSES_NUM,
945 IRA_IMPORTANT_CLASSES, and IRA_IMPORTANT_CLASSES_NUM.
947 Target may have many subtargets and not all target hard regiters can
948 be used for allocation, e.g. x86 port in 32-bit mode can not use
949 hard registers introduced in x86-64 like r8-r15). Some classes
950 might have the same allocatable hard registers, e.g. INDEX_REGS
951 and GENERAL_REGS in x86 port in 32-bit mode. To decrease different
952 calculations efforts we introduce allocno classes which contain
953 unique non-empty sets of allocatable hard-registers.
955 Pseudo class cost calculation in ira-costs.c is very expensive.
956 Therefore we are trying to decrease number of classes involved in
957 such calculation. Register classes used in the cost calculation
958 are called important classes. They are allocno classes and other
959 non-empty classes whose allocatable hard register sets are inside
960 of an allocno class hard register set. From the first sight, it
961 looks like that they are just allocno classes. It is not true. In
962 example of x86-port in 32-bit mode, allocno classes will contain
963 GENERAL_REGS but not LEGACY_REGS (because allocatable hard
964 registers are the same for the both classes). The important
965 classes will contain GENERAL_REGS and LEGACY_REGS. It is done
966 because a machine description insn constraint may refers for
967 LEGACY_REGS and code in ira-costs.c is mostly base on investigation
968 of the insn constraints. */
970 setup_allocno_and_important_classes (void)
974 HARD_REG_SET temp_hard_regset2
;
975 static enum reg_class classes
[LIM_REG_CLASSES
+ 1];
978 /* Collect classes which contain unique sets of allocatable hard
979 registers. Prefer GENERAL_REGS to other classes containing the
980 same set of hard registers. */
981 for (i
= 0; i
< LIM_REG_CLASSES
; i
++)
983 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[i
]);
984 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
985 for (j
= 0; j
< n
; j
++)
988 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl
]);
989 AND_COMPL_HARD_REG_SET (temp_hard_regset2
,
991 if (hard_reg_set_equal_p (temp_hard_regset
,
996 classes
[n
++] = (enum reg_class
) i
;
997 else if (i
== GENERAL_REGS
)
998 /* Prefer general regs. For i386 example, it means that
999 we prefer GENERAL_REGS over INDEX_REGS or LEGACY_REGS
1000 (all of them consists of the same available hard
1002 classes
[j
] = (enum reg_class
) i
;
1004 classes
[n
] = LIM_REG_CLASSES
;
1006 /* Set up classes which can be used for allocnos as classes
1007 conatining non-empty unique sets of allocatable hard
1009 ira_allocno_classes_num
= 0;
1010 for (i
= 0; (cl
= classes
[i
]) != LIM_REG_CLASSES
; i
++)
1011 if (ira_class_hard_regs_num
[cl
] > 0)
1012 ira_allocno_classes
[ira_allocno_classes_num
++] = (enum reg_class
) cl
;
1013 ira_important_classes_num
= 0;
1014 /* Add non-allocno classes containing to non-empty set of
1015 allocatable hard regs. */
1016 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1017 if (ira_class_hard_regs_num
[cl
] > 0)
1019 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
1020 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1022 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1024 COPY_HARD_REG_SET (temp_hard_regset2
,
1025 reg_class_contents
[ira_allocno_classes
[j
]]);
1026 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
1027 if ((enum reg_class
) cl
== ira_allocno_classes
[j
])
1029 else if (hard_reg_set_subset_p (temp_hard_regset
,
1033 if (set_p
&& j
>= ira_allocno_classes_num
)
1034 ira_important_classes
[ira_important_classes_num
++]
1035 = (enum reg_class
) cl
;
1037 /* Now add allocno classes to the important classes. */
1038 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1039 ira_important_classes
[ira_important_classes_num
++]
1040 = ira_allocno_classes
[j
];
1041 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1043 ira_reg_allocno_class_p
[cl
] = false;
1044 ira_reg_pressure_class_p
[cl
] = false;
1046 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1047 ira_reg_allocno_class_p
[ira_allocno_classes
[j
]] = true;
1048 setup_pressure_classes ();
1049 setup_uniform_class_p ();
1052 /* Setup translation in CLASS_TRANSLATE of all classes into a class
1053 given by array CLASSES of length CLASSES_NUM. The function is used
1054 make translation any reg class to an allocno class or to an
1055 pressure class. This translation is necessary for some
1056 calculations when we can use only allocno or pressure classes and
1057 such translation represents an approximate representation of all
1060 The translation in case when allocatable hard register set of a
1061 given class is subset of allocatable hard register set of a class
1062 in CLASSES is pretty simple. We use smallest classes from CLASSES
1063 containing a given class. If allocatable hard register set of a
1064 given class is not a subset of any corresponding set of a class
1065 from CLASSES, we use the cheapest (with load/store point of view)
1066 class from CLASSES whose set intersects with given class set */
1068 setup_class_translate_array (enum reg_class
*class_translate
,
1069 int classes_num
, enum reg_class
*classes
)
1072 enum reg_class aclass
, best_class
, *cl_ptr
;
1073 int i
, cost
, min_cost
, best_cost
;
1075 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1076 class_translate
[cl
] = NO_REGS
;
1078 for (i
= 0; i
< classes_num
; i
++)
1080 aclass
= classes
[i
];
1081 for (cl_ptr
= &alloc_reg_class_subclasses
[aclass
][0];
1082 (cl
= *cl_ptr
) != LIM_REG_CLASSES
;
1084 if (class_translate
[cl
] == NO_REGS
)
1085 class_translate
[cl
] = aclass
;
1086 class_translate
[aclass
] = aclass
;
1088 /* For classes which are not fully covered by one of given classes
1089 (in other words covered by more one given class), use the
1091 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1093 if (cl
== NO_REGS
|| class_translate
[cl
] != NO_REGS
)
1095 best_class
= NO_REGS
;
1096 best_cost
= INT_MAX
;
1097 for (i
= 0; i
< classes_num
; i
++)
1099 aclass
= classes
[i
];
1100 COPY_HARD_REG_SET (temp_hard_regset
,
1101 reg_class_contents
[aclass
]);
1102 AND_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
1103 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1104 if (! hard_reg_set_empty_p (temp_hard_regset
))
1107 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
1109 cost
= (ira_memory_move_cost
[mode
][cl
][0]
1110 + ira_memory_move_cost
[mode
][cl
][1]);
1111 if (min_cost
> cost
)
1114 if (best_class
== NO_REGS
|| best_cost
> min_cost
)
1116 best_class
= aclass
;
1117 best_cost
= min_cost
;
1121 class_translate
[cl
] = best_class
;
1125 /* Set up array IRA_ALLOCNO_CLASS_TRANSLATE and
1126 IRA_PRESSURE_CLASS_TRANSLATE. */
1128 setup_class_translate (void)
1130 setup_class_translate_array (ira_allocno_class_translate
,
1131 ira_allocno_classes_num
, ira_allocno_classes
);
1132 setup_class_translate_array (ira_pressure_class_translate
,
1133 ira_pressure_classes_num
, ira_pressure_classes
);
1136 /* Order numbers of allocno classes in original target allocno class
1137 array, -1 for non-allocno classes. */
1138 static int allocno_class_order
[N_REG_CLASSES
];
1140 /* The function used to sort the important classes. */
1142 comp_reg_classes_func (const void *v1p
, const void *v2p
)
1144 enum reg_class cl1
= *(const enum reg_class
*) v1p
;
1145 enum reg_class cl2
= *(const enum reg_class
*) v2p
;
1146 enum reg_class tcl1
, tcl2
;
1149 tcl1
= ira_allocno_class_translate
[cl1
];
1150 tcl2
= ira_allocno_class_translate
[cl2
];
1151 if (tcl1
!= NO_REGS
&& tcl2
!= NO_REGS
1152 && (diff
= allocno_class_order
[tcl1
] - allocno_class_order
[tcl2
]) != 0)
1154 return (int) cl1
- (int) cl2
;
1157 /* For correct work of function setup_reg_class_relation we need to
1158 reorder important classes according to the order of their allocno
1159 classes. It places important classes containing the same
1160 allocatable hard register set adjacent to each other and allocno
1161 class with the allocatable hard register set right after the other
1162 important classes with the same set.
1164 In example from comments of function
1165 setup_allocno_and_important_classes, it places LEGACY_REGS and
1166 GENERAL_REGS close to each other and GENERAL_REGS is after
1169 reorder_important_classes (void)
1173 for (i
= 0; i
< N_REG_CLASSES
; i
++)
1174 allocno_class_order
[i
] = -1;
1175 for (i
= 0; i
< ira_allocno_classes_num
; i
++)
1176 allocno_class_order
[ira_allocno_classes
[i
]] = i
;
1177 qsort (ira_important_classes
, ira_important_classes_num
,
1178 sizeof (enum reg_class
), comp_reg_classes_func
);
1179 for (i
= 0; i
< ira_important_classes_num
; i
++)
1180 ira_important_class_nums
[ira_important_classes
[i
]] = i
;
1183 /* Set up IRA_REG_CLASS_SUBUNION, IRA_REG_CLASS_SUPERUNION,
1184 IRA_REG_CLASS_SUPER_CLASSES, IRA_REG_CLASSES_INTERSECT, and
1185 IRA_REG_CLASSES_INTERSECT_P. For the meaning of the relations,
1186 please see corresponding comments in ira-int.h. */
1188 setup_reg_class_relations (void)
1190 int i
, cl1
, cl2
, cl3
;
1191 HARD_REG_SET intersection_set
, union_set
, temp_set2
;
1192 bool important_class_p
[N_REG_CLASSES
];
1194 memset (important_class_p
, 0, sizeof (important_class_p
));
1195 for (i
= 0; i
< ira_important_classes_num
; i
++)
1196 important_class_p
[ira_important_classes
[i
]] = true;
1197 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1199 ira_reg_class_super_classes
[cl1
][0] = LIM_REG_CLASSES
;
1200 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1202 ira_reg_classes_intersect_p
[cl1
][cl2
] = false;
1203 ira_reg_class_intersect
[cl1
][cl2
] = NO_REGS
;
1204 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl1
]);
1205 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1206 COPY_HARD_REG_SET (temp_set2
, reg_class_contents
[cl2
]);
1207 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1208 if (hard_reg_set_empty_p (temp_hard_regset
)
1209 && hard_reg_set_empty_p (temp_set2
))
1211 /* The both classes have no allocatable hard registers
1212 -- take all class hard registers into account and use
1213 reg_class_subunion and reg_class_superunion. */
1216 cl3
= reg_class_subclasses
[cl1
][i
];
1217 if (cl3
== LIM_REG_CLASSES
)
1219 if (reg_class_subset_p (ira_reg_class_intersect
[cl1
][cl2
],
1220 (enum reg_class
) cl3
))
1221 ira_reg_class_intersect
[cl1
][cl2
] = (enum reg_class
) cl3
;
1223 ira_reg_class_subunion
[cl1
][cl2
] = reg_class_subunion
[cl1
][cl2
];
1224 ira_reg_class_superunion
[cl1
][cl2
] = reg_class_superunion
[cl1
][cl2
];
1227 ira_reg_classes_intersect_p
[cl1
][cl2
]
1228 = hard_reg_set_intersect_p (temp_hard_regset
, temp_set2
);
1229 if (important_class_p
[cl1
] && important_class_p
[cl2
]
1230 && hard_reg_set_subset_p (temp_hard_regset
, temp_set2
))
1232 /* CL1 and CL2 are important classes and CL1 allocatable
1233 hard register set is inside of CL2 allocatable hard
1234 registers -- make CL1 a superset of CL2. */
1237 p
= &ira_reg_class_super_classes
[cl1
][0];
1238 while (*p
!= LIM_REG_CLASSES
)
1240 *p
++ = (enum reg_class
) cl2
;
1241 *p
= LIM_REG_CLASSES
;
1243 ira_reg_class_subunion
[cl1
][cl2
] = NO_REGS
;
1244 ira_reg_class_superunion
[cl1
][cl2
] = NO_REGS
;
1245 COPY_HARD_REG_SET (intersection_set
, reg_class_contents
[cl1
]);
1246 AND_HARD_REG_SET (intersection_set
, reg_class_contents
[cl2
]);
1247 AND_COMPL_HARD_REG_SET (intersection_set
, no_unit_alloc_regs
);
1248 COPY_HARD_REG_SET (union_set
, reg_class_contents
[cl1
]);
1249 IOR_HARD_REG_SET (union_set
, reg_class_contents
[cl2
]);
1250 AND_COMPL_HARD_REG_SET (union_set
, no_unit_alloc_regs
);
1251 for (i
= 0; i
< ira_important_classes_num
; i
++)
1253 cl3
= ira_important_classes
[i
];
1254 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl3
]);
1255 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1256 if (hard_reg_set_subset_p (temp_hard_regset
, intersection_set
))
1258 /* CL3 allocatable hard register set is inside of
1259 intersection of allocatable hard register sets
1263 reg_class_contents
[(int)
1264 ira_reg_class_intersect
[cl1
][cl2
]]);
1265 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1266 if (! hard_reg_set_subset_p (temp_hard_regset
, temp_set2
)
1267 /* If the allocatable hard register sets are the
1268 same, prefer GENERAL_REGS or the smallest
1269 class for debugging purposes. */
1270 || (hard_reg_set_equal_p (temp_hard_regset
, temp_set2
)
1271 && (cl3
== GENERAL_REGS
1272 || (ira_reg_class_intersect
[cl1
][cl2
] != GENERAL_REGS
1273 && hard_reg_set_subset_p
1274 (reg_class_contents
[cl3
],
1276 [(int) ira_reg_class_intersect
[cl1
][cl2
]])))))
1277 ira_reg_class_intersect
[cl1
][cl2
] = (enum reg_class
) cl3
;
1279 if (hard_reg_set_subset_p (temp_hard_regset
, union_set
))
1281 /* CL3 allocatbale hard register set is inside of
1282 union of allocatable hard register sets of CL1
1286 reg_class_contents
[(int) ira_reg_class_subunion
[cl1
][cl2
]]);
1287 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1288 if (ira_reg_class_subunion
[cl1
][cl2
] == NO_REGS
1289 || (hard_reg_set_subset_p (temp_set2
, temp_hard_regset
)
1291 && (! hard_reg_set_equal_p (temp_set2
,
1293 || cl3
== GENERAL_REGS
1294 /* If the allocatable hard register sets are the
1295 same, prefer GENERAL_REGS or the smallest
1296 class for debugging purposes. */
1297 || (ira_reg_class_subunion
[cl1
][cl2
] != GENERAL_REGS
1298 && hard_reg_set_subset_p
1299 (reg_class_contents
[cl3
],
1301 [(int) ira_reg_class_subunion
[cl1
][cl2
]])))))
1302 ira_reg_class_subunion
[cl1
][cl2
] = (enum reg_class
) cl3
;
1304 if (hard_reg_set_subset_p (union_set
, temp_hard_regset
))
1306 /* CL3 allocatable hard register set contains union
1307 of allocatable hard register sets of CL1 and
1311 reg_class_contents
[(int) ira_reg_class_superunion
[cl1
][cl2
]]);
1312 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1313 if (ira_reg_class_superunion
[cl1
][cl2
] == NO_REGS
1314 || (hard_reg_set_subset_p (temp_hard_regset
, temp_set2
)
1316 && (! hard_reg_set_equal_p (temp_set2
,
1318 || cl3
== GENERAL_REGS
1319 /* If the allocatable hard register sets are the
1320 same, prefer GENERAL_REGS or the smallest
1321 class for debugging purposes. */
1322 || (ira_reg_class_superunion
[cl1
][cl2
] != GENERAL_REGS
1323 && hard_reg_set_subset_p
1324 (reg_class_contents
[cl3
],
1326 [(int) ira_reg_class_superunion
[cl1
][cl2
]])))))
1327 ira_reg_class_superunion
[cl1
][cl2
] = (enum reg_class
) cl3
;
1334 /* Output all unifrom and important classes into file F. */
1336 print_unform_and_important_classes (FILE *f
)
1338 static const char *const reg_class_names
[] = REG_CLASS_NAMES
;
1341 fprintf (f
, "Uniform classes:\n");
1342 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1343 if (ira_uniform_class_p
[cl
])
1344 fprintf (f
, " %s", reg_class_names
[cl
]);
1345 fprintf (f
, "\nImportant classes:\n");
1346 for (i
= 0; i
< ira_important_classes_num
; i
++)
1347 fprintf (f
, " %s", reg_class_names
[ira_important_classes
[i
]]);
1351 /* Output all possible allocno or pressure classes and their
1352 translation map into file F. */
1354 print_translated_classes (FILE *f
, bool pressure_p
)
1356 int classes_num
= (pressure_p
1357 ? ira_pressure_classes_num
: ira_allocno_classes_num
);
1358 enum reg_class
*classes
= (pressure_p
1359 ? ira_pressure_classes
: ira_allocno_classes
);
1360 enum reg_class
*class_translate
= (pressure_p
1361 ? ira_pressure_class_translate
1362 : ira_allocno_class_translate
);
1363 static const char *const reg_class_names
[] = REG_CLASS_NAMES
;
1366 fprintf (f
, "%s classes:\n", pressure_p
? "Pressure" : "Allocno");
1367 for (i
= 0; i
< classes_num
; i
++)
1368 fprintf (f
, " %s", reg_class_names
[classes
[i
]]);
1369 fprintf (f
, "\nClass translation:\n");
1370 for (i
= 0; i
< N_REG_CLASSES
; i
++)
1371 fprintf (f
, " %s -> %s\n", reg_class_names
[i
],
1372 reg_class_names
[class_translate
[i
]]);
1375 /* Output all possible allocno and translation classes and the
1376 translation maps into stderr. */
1378 ira_debug_allocno_classes (void)
1380 print_unform_and_important_classes (stderr
);
1381 print_translated_classes (stderr
, false);
1382 print_translated_classes (stderr
, true);
1385 /* Set up different arrays concerning class subsets, allocno and
1386 important classes. */
1388 find_reg_classes (void)
1390 setup_allocno_and_important_classes ();
1391 setup_class_translate ();
1392 reorder_important_classes ();
1393 setup_reg_class_relations ();
1398 /* Set up the array above. */
1400 setup_hard_regno_aclass (void)
1404 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1407 ira_hard_regno_allocno_class
[i
]
1408 = (TEST_HARD_REG_BIT (no_unit_alloc_regs
, i
)
1410 : ira_allocno_class_translate
[REGNO_REG_CLASS (i
)]);
1414 ira_hard_regno_allocno_class
[i
] = NO_REGS
;
1415 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1417 cl
= ira_allocno_classes
[j
];
1418 if (ira_class_hard_reg_index
[cl
][i
] >= 0)
1420 ira_hard_regno_allocno_class
[i
] = cl
;
1430 /* Form IRA_REG_CLASS_MAX_NREGS and IRA_REG_CLASS_MIN_NREGS maps. */
1432 setup_reg_class_nregs (void)
1436 for (m
= 0; m
< MAX_MACHINE_MODE
; m
++)
1438 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1439 ira_reg_class_max_nregs
[cl
][m
]
1440 = ira_reg_class_min_nregs
[cl
][m
]
1441 = targetm
.class_max_nregs ((reg_class_t
) cl
, (enum machine_mode
) m
);
1442 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1444 (cl2
= alloc_reg_class_subclasses
[cl
][i
]) != LIM_REG_CLASSES
;
1446 if (ira_reg_class_min_nregs
[cl2
][m
]
1447 < ira_reg_class_min_nregs
[cl
][m
])
1448 ira_reg_class_min_nregs
[cl
][m
] = ira_reg_class_min_nregs
[cl2
][m
];
1454 /* Set up IRA_PROHIBITED_CLASS_MODE_REGS and IRA_CLASS_SINGLETON.
1455 This function is called once IRA_CLASS_HARD_REGS has been initialized. */
1457 setup_prohibited_class_mode_regs (void)
1459 int j
, k
, hard_regno
, cl
, last_hard_regno
, count
;
1461 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
1463 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
1464 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1465 for (j
= 0; j
< NUM_MACHINE_MODES
; j
++)
1468 last_hard_regno
= -1;
1469 CLEAR_HARD_REG_SET (ira_prohibited_class_mode_regs
[cl
][j
]);
1470 for (k
= ira_class_hard_regs_num
[cl
] - 1; k
>= 0; k
--)
1472 hard_regno
= ira_class_hard_regs
[cl
][k
];
1473 if (! HARD_REGNO_MODE_OK (hard_regno
, (enum machine_mode
) j
))
1474 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1476 else if (in_hard_reg_set_p (temp_hard_regset
,
1477 (enum machine_mode
) j
, hard_regno
))
1479 last_hard_regno
= hard_regno
;
1483 ira_class_singleton
[cl
][j
] = (count
== 1 ? last_hard_regno
: -1);
1488 /* Clarify IRA_PROHIBITED_CLASS_MODE_REGS by excluding hard registers
1489 spanning from one register pressure class to another one. It is
1490 called after defining the pressure classes. */
1492 clarify_prohibited_class_mode_regs (void)
1494 int j
, k
, hard_regno
, cl
, pclass
, nregs
;
1496 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
1497 for (j
= 0; j
< NUM_MACHINE_MODES
; j
++)
1499 CLEAR_HARD_REG_SET (ira_useful_class_mode_regs
[cl
][j
]);
1500 for (k
= ira_class_hard_regs_num
[cl
] - 1; k
>= 0; k
--)
1502 hard_regno
= ira_class_hard_regs
[cl
][k
];
1503 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
], hard_regno
))
1505 nregs
= hard_regno_nregs
[hard_regno
][j
];
1506 if (hard_regno
+ nregs
> FIRST_PSEUDO_REGISTER
)
1508 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1512 pclass
= ira_pressure_class_translate
[REGNO_REG_CLASS (hard_regno
)];
1513 for (nregs
-- ;nregs
>= 0; nregs
--)
1514 if (((enum reg_class
) pclass
1515 != ira_pressure_class_translate
[REGNO_REG_CLASS
1516 (hard_regno
+ nregs
)]))
1518 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1522 if (!TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1524 add_to_hard_reg_set (&ira_useful_class_mode_regs
[cl
][j
],
1525 (enum machine_mode
) j
, hard_regno
);
1530 /* Allocate and initialize IRA_REGISTER_MOVE_COST, IRA_MAY_MOVE_IN_COST
1531 and IRA_MAY_MOVE_OUT_COST for MODE. */
1533 ira_init_register_move_cost (enum machine_mode mode
)
1535 static unsigned short last_move_cost
[N_REG_CLASSES
][N_REG_CLASSES
];
1536 bool all_match
= true;
1537 unsigned int cl1
, cl2
;
1539 ira_assert (ira_register_move_cost
[mode
] == NULL
1540 && ira_may_move_in_cost
[mode
] == NULL
1541 && ira_may_move_out_cost
[mode
] == NULL
);
1542 ira_assert (have_regs_of_mode
[mode
]);
1543 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1544 if (contains_reg_of_mode
[cl1
][mode
])
1545 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1548 if (!contains_reg_of_mode
[cl2
][mode
])
1552 cost
= register_move_cost (mode
, (enum reg_class
) cl1
,
1553 (enum reg_class
) cl2
);
1554 ira_assert (cost
< 65535);
1556 all_match
&= (last_move_cost
[cl1
][cl2
] == cost
);
1557 last_move_cost
[cl1
][cl2
] = cost
;
1559 if (all_match
&& last_mode_for_init_move_cost
!= -1)
1561 ira_register_move_cost
[mode
]
1562 = ira_register_move_cost
[last_mode_for_init_move_cost
];
1563 ira_may_move_in_cost
[mode
]
1564 = ira_may_move_in_cost
[last_mode_for_init_move_cost
];
1565 ira_may_move_out_cost
[mode
]
1566 = ira_may_move_out_cost
[last_mode_for_init_move_cost
];
1569 last_mode_for_init_move_cost
= mode
;
1570 ira_register_move_cost
[mode
] = XNEWVEC (move_table
, N_REG_CLASSES
);
1571 ira_may_move_in_cost
[mode
] = XNEWVEC (move_table
, N_REG_CLASSES
);
1572 ira_may_move_out_cost
[mode
] = XNEWVEC (move_table
, N_REG_CLASSES
);
1573 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1574 if (contains_reg_of_mode
[cl1
][mode
])
1575 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1578 enum reg_class
*p1
, *p2
;
1580 if (last_move_cost
[cl1
][cl2
] == 65535)
1582 ira_register_move_cost
[mode
][cl1
][cl2
] = 65535;
1583 ira_may_move_in_cost
[mode
][cl1
][cl2
] = 65535;
1584 ira_may_move_out_cost
[mode
][cl1
][cl2
] = 65535;
1588 cost
= last_move_cost
[cl1
][cl2
];
1590 for (p2
= ®_class_subclasses
[cl2
][0];
1591 *p2
!= LIM_REG_CLASSES
; p2
++)
1592 if (ira_class_hard_regs_num
[*p2
] > 0
1593 && (ira_reg_class_max_nregs
[*p2
][mode
]
1594 <= ira_class_hard_regs_num
[*p2
]))
1595 cost
= MAX (cost
, ira_register_move_cost
[mode
][cl1
][*p2
]);
1597 for (p1
= ®_class_subclasses
[cl1
][0];
1598 *p1
!= LIM_REG_CLASSES
; p1
++)
1599 if (ira_class_hard_regs_num
[*p1
] > 0
1600 && (ira_reg_class_max_nregs
[*p1
][mode
]
1601 <= ira_class_hard_regs_num
[*p1
]))
1602 cost
= MAX (cost
, ira_register_move_cost
[mode
][*p1
][cl2
]);
1604 ira_assert (cost
<= 65535);
1605 ira_register_move_cost
[mode
][cl1
][cl2
] = cost
;
1607 if (ira_class_subset_p
[cl1
][cl2
])
1608 ira_may_move_in_cost
[mode
][cl1
][cl2
] = 0;
1610 ira_may_move_in_cost
[mode
][cl1
][cl2
] = cost
;
1612 if (ira_class_subset_p
[cl2
][cl1
])
1613 ira_may_move_out_cost
[mode
][cl1
][cl2
] = 0;
1615 ira_may_move_out_cost
[mode
][cl1
][cl2
] = cost
;
1619 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1621 ira_register_move_cost
[mode
][cl1
][cl2
] = 65535;
1622 ira_may_move_in_cost
[mode
][cl1
][cl2
] = 65535;
1623 ira_may_move_out_cost
[mode
][cl1
][cl2
] = 65535;
1628 /* This is called once during compiler work. It sets up
1629 different arrays whose values don't depend on the compiled
1632 ira_init_once (void)
1634 ira_init_costs_once ();
1637 /* Free ira_max_register_move_cost, ira_may_move_in_cost and
1638 ira_may_move_out_cost for each mode. */
1640 free_register_move_costs (void)
1644 /* Reset move_cost and friends, making sure we only free shared
1645 table entries once. */
1646 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
1647 if (ira_register_move_cost
[mode
])
1650 i
< mode
&& (ira_register_move_cost
[i
]
1651 != ira_register_move_cost
[mode
]);
1656 free (ira_register_move_cost
[mode
]);
1657 free (ira_may_move_in_cost
[mode
]);
1658 free (ira_may_move_out_cost
[mode
]);
1661 memset (ira_register_move_cost
, 0, sizeof ira_register_move_cost
);
1662 memset (ira_may_move_in_cost
, 0, sizeof ira_may_move_in_cost
);
1663 memset (ira_may_move_out_cost
, 0, sizeof ira_may_move_out_cost
);
1664 last_mode_for_init_move_cost
= -1;
1667 /* This is called every time when register related information is
1672 free_register_move_costs ();
1673 setup_reg_mode_hard_regset ();
1674 setup_alloc_regs (flag_omit_frame_pointer
!= 0);
1675 setup_class_subset_and_memory_move_costs ();
1676 setup_reg_class_nregs ();
1677 setup_prohibited_class_mode_regs ();
1678 find_reg_classes ();
1679 clarify_prohibited_class_mode_regs ();
1680 setup_hard_regno_aclass ();
1684 /* Function called once at the end of compiler work. */
1686 ira_finish_once (void)
1688 ira_finish_costs_once ();
1689 free_register_move_costs ();
1693 #define ira_prohibited_mode_move_regs_initialized_p \
1694 (this_target_ira_int->x_ira_prohibited_mode_move_regs_initialized_p)
1696 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS. */
1698 setup_prohibited_mode_move_regs (void)
1701 rtx test_reg1
, test_reg2
, move_pat
, move_insn
;
1703 if (ira_prohibited_mode_move_regs_initialized_p
)
1705 ira_prohibited_mode_move_regs_initialized_p
= true;
1706 test_reg1
= gen_rtx_REG (VOIDmode
, 0);
1707 test_reg2
= gen_rtx_REG (VOIDmode
, 0);
1708 move_pat
= gen_rtx_SET (VOIDmode
, test_reg1
, test_reg2
);
1709 move_insn
= gen_rtx_INSN (VOIDmode
, 0, 0, 0, 0, move_pat
, 0, -1, 0);
1710 for (i
= 0; i
< NUM_MACHINE_MODES
; i
++)
1712 SET_HARD_REG_SET (ira_prohibited_mode_move_regs
[i
]);
1713 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1715 if (! HARD_REGNO_MODE_OK (j
, (enum machine_mode
) i
))
1717 SET_REGNO_RAW (test_reg1
, j
);
1718 PUT_MODE (test_reg1
, (enum machine_mode
) i
);
1719 SET_REGNO_RAW (test_reg2
, j
);
1720 PUT_MODE (test_reg2
, (enum machine_mode
) i
);
1721 INSN_CODE (move_insn
) = -1;
1722 recog_memoized (move_insn
);
1723 if (INSN_CODE (move_insn
) < 0)
1725 extract_insn (move_insn
);
1726 if (! constrain_operands (1))
1728 CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs
[i
], j
);
1735 /* Return nonzero if REGNO is a particularly bad choice for reloading X. */
1737 ira_bad_reload_regno_1 (int regno
, rtx x
)
1741 enum reg_class pref
;
1743 /* We only deal with pseudo regs. */
1744 if (! x
|| GET_CODE (x
) != REG
)
1747 x_regno
= REGNO (x
);
1748 if (x_regno
< FIRST_PSEUDO_REGISTER
)
1751 /* If the pseudo prefers REGNO explicitly, then do not consider
1752 REGNO a bad spill choice. */
1753 pref
= reg_preferred_class (x_regno
);
1754 if (reg_class_size
[pref
] == 1)
1755 return !TEST_HARD_REG_BIT (reg_class_contents
[pref
], regno
);
1757 /* If the pseudo conflicts with REGNO, then we consider REGNO a
1758 poor choice for a reload regno. */
1759 a
= ira_regno_allocno_map
[x_regno
];
1760 n
= ALLOCNO_NUM_OBJECTS (a
);
1761 for (i
= 0; i
< n
; i
++)
1763 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
1764 if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), regno
))
1770 /* Return nonzero if REGNO is a particularly bad choice for reloading
1773 ira_bad_reload_regno (int regno
, rtx in
, rtx out
)
1775 return (ira_bad_reload_regno_1 (regno
, in
)
1776 || ira_bad_reload_regno_1 (regno
, out
));
1779 /* Return TRUE if *LOC contains an asm. */
1781 insn_contains_asm_1 (rtx
*loc
, void *data ATTRIBUTE_UNUSED
)
1785 if (GET_CODE (*loc
) == ASM_OPERANDS
)
1791 /* Return TRUE if INSN contains an ASM. */
1793 insn_contains_asm (rtx insn
)
1795 return for_each_rtx (&insn
, insn_contains_asm_1
, NULL
);
1798 /* Add register clobbers from asm statements. */
1800 compute_regs_asm_clobbered (void)
1807 FOR_BB_INSNS_REVERSE (bb
, insn
)
1811 if (insn_contains_asm (insn
))
1812 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
1814 df_ref def
= *def_rec
;
1815 unsigned int dregno
= DF_REF_REGNO (def
);
1816 if (HARD_REGISTER_NUM_P (dregno
))
1817 add_to_hard_reg_set (&crtl
->asm_clobbers
,
1818 GET_MODE (DF_REF_REAL_REG (def
)),
1826 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and REGS_EVER_LIVE. */
1828 ira_setup_eliminable_regset (void)
1830 #ifdef ELIMINABLE_REGS
1832 static const struct {const int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
1834 /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
1835 sp for alloca. So we can't eliminate the frame pointer in that
1836 case. At some point, we should improve this by emitting the
1837 sp-adjusting insns for this case. */
1839 = (! flag_omit_frame_pointer
1840 || (cfun
->calls_alloca
&& EXIT_IGNORE_STACK
)
1841 /* We need the frame pointer to catch stack overflow exceptions
1842 if the stack pointer is moving. */
1843 || (flag_stack_check
&& STACK_CHECK_MOVING_SP
)
1844 || crtl
->accesses_prior_frames
1845 || crtl
->stack_realign_needed
1846 || targetm
.frame_pointer_required ());
1848 frame_pointer_needed
= need_fp
;
1850 COPY_HARD_REG_SET (ira_no_alloc_regs
, no_unit_alloc_regs
);
1851 CLEAR_HARD_REG_SET (eliminable_regset
);
1853 compute_regs_asm_clobbered ();
1855 /* Build the regset of all eliminable registers and show we can't
1856 use those that we already know won't be eliminated. */
1857 #ifdef ELIMINABLE_REGS
1858 for (i
= 0; i
< (int) ARRAY_SIZE (eliminables
); i
++)
1861 = (! targetm
.can_eliminate (eliminables
[i
].from
, eliminables
[i
].to
)
1862 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& need_fp
));
1864 if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
, eliminables
[i
].from
))
1866 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
1869 SET_HARD_REG_BIT (ira_no_alloc_regs
, eliminables
[i
].from
);
1871 else if (cannot_elim
)
1872 error ("%s cannot be used in asm here",
1873 reg_names
[eliminables
[i
].from
]);
1875 df_set_regs_ever_live (eliminables
[i
].from
, true);
1877 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
1878 if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
, HARD_FRAME_POINTER_REGNUM
))
1880 SET_HARD_REG_BIT (eliminable_regset
, HARD_FRAME_POINTER_REGNUM
);
1882 SET_HARD_REG_BIT (ira_no_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
1885 error ("%s cannot be used in asm here",
1886 reg_names
[HARD_FRAME_POINTER_REGNUM
]);
1888 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM
, true);
1892 if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
, HARD_FRAME_POINTER_REGNUM
))
1894 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
1896 SET_HARD_REG_BIT (ira_no_alloc_regs
, FRAME_POINTER_REGNUM
);
1899 error ("%s cannot be used in asm here", reg_names
[FRAME_POINTER_REGNUM
]);
1901 df_set_regs_ever_live (FRAME_POINTER_REGNUM
, true);
1907 /* The length of the following two arrays. */
1908 int ira_reg_equiv_len
;
1910 /* The element value is TRUE if the corresponding regno value is
1912 bool *ira_reg_equiv_invariant_p
;
1914 /* The element value is equiv constant of given pseudo-register or
1916 rtx
*ira_reg_equiv_const
;
1918 /* Set up the two arrays declared above. */
1920 find_reg_equiv_invariant_const (void)
1924 rtx list
, insn
, note
, constant
, x
;
1926 for (i
= FIRST_PSEUDO_REGISTER
; i
< VEC_length (reg_equivs_t
, reg_equivs
); i
++)
1928 constant
= NULL_RTX
;
1929 invariant_p
= false;
1930 for (list
= reg_equiv_init (i
); list
!= NULL_RTX
; list
= XEXP (list
, 1))
1932 insn
= XEXP (list
, 0);
1933 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
1935 if (note
== NULL_RTX
)
1940 if (! CONSTANT_P (x
)
1941 || ! flag_pic
|| LEGITIMATE_PIC_OPERAND_P (x
))
1943 /* It can happen that a REG_EQUIV note contains a MEM
1944 that is not a legitimate memory operand. As later
1945 stages of the reload assume that all addresses found
1946 in the reg_equiv_* arrays were originally legitimate,
1947 we ignore such REG_EQUIV notes. */
1948 if (memory_operand (x
, VOIDmode
))
1949 invariant_p
= MEM_READONLY_P (x
);
1950 else if (function_invariant_p (x
))
1952 if (GET_CODE (x
) == PLUS
1953 || x
== frame_pointer_rtx
|| x
== arg_pointer_rtx
)
1960 ira_reg_equiv_invariant_p
[i
] = invariant_p
;
1961 ira_reg_equiv_const
[i
] = constant
;
1967 /* Vector of substitutions of register numbers,
1968 used to map pseudo regs into hardware regs.
1969 This is set up as a result of register allocation.
1970 Element N is the hard reg assigned to pseudo reg N,
1971 or is -1 if no hard reg was assigned.
1972 If N is a hard reg number, element N is N. */
1973 short *reg_renumber
;
1975 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
1976 the allocation found by IRA. */
1978 setup_reg_renumber (void)
1980 int regno
, hard_regno
;
1982 ira_allocno_iterator ai
;
1984 caller_save_needed
= 0;
1985 FOR_EACH_ALLOCNO (a
, ai
)
1987 /* There are no caps at this point. */
1988 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
1989 if (! ALLOCNO_ASSIGNED_P (a
))
1990 /* It can happen if A is not referenced but partially anticipated
1991 somewhere in a region. */
1992 ALLOCNO_ASSIGNED_P (a
) = true;
1993 ira_free_allocno_updated_costs (a
);
1994 hard_regno
= ALLOCNO_HARD_REGNO (a
);
1995 regno
= ALLOCNO_REGNO (a
);
1996 reg_renumber
[regno
] = (hard_regno
< 0 ? -1 : hard_regno
);
1997 if (hard_regno
>= 0)
2000 enum reg_class pclass
;
2003 pclass
= ira_pressure_class_translate
[REGNO_REG_CLASS (hard_regno
)];
2004 nwords
= ALLOCNO_NUM_OBJECTS (a
);
2005 for (i
= 0; i
< nwords
; i
++)
2007 obj
= ALLOCNO_OBJECT (a
, i
);
2008 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
2009 reg_class_contents
[pclass
]);
2011 if (ALLOCNO_CALLS_CROSSED_NUM (a
) != 0
2012 && ira_hard_reg_set_intersection_p (hard_regno
, ALLOCNO_MODE (a
),
2015 ira_assert (!optimize
|| flag_caller_saves
2016 || (ALLOCNO_CALLS_CROSSED_NUM (a
)
2017 == ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
))
2018 || regno
>= ira_reg_equiv_len
2019 || ira_reg_equiv_const
[regno
]
2020 || ira_reg_equiv_invariant_p
[regno
]);
2021 caller_save_needed
= 1;
2027 /* Set up allocno assignment flags for further allocation
2030 setup_allocno_assignment_flags (void)
2034 ira_allocno_iterator ai
;
2036 FOR_EACH_ALLOCNO (a
, ai
)
2038 if (! ALLOCNO_ASSIGNED_P (a
))
2039 /* It can happen if A is not referenced but partially anticipated
2040 somewhere in a region. */
2041 ira_free_allocno_updated_costs (a
);
2042 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2043 /* Don't assign hard registers to allocnos which are destination
2044 of removed store at the end of loop. It has no sense to keep
2045 the same value in different hard registers. It is also
2046 impossible to assign hard registers correctly to such
2047 allocnos because the cost info and info about intersected
2048 calls are incorrect for them. */
2049 ALLOCNO_ASSIGNED_P (a
) = (hard_regno
>= 0
2050 || ALLOCNO_EMIT_DATA (a
)->mem_optimized_dest_p
2051 || (ALLOCNO_MEMORY_COST (a
)
2052 - ALLOCNO_CLASS_COST (a
)) < 0);
2055 || ira_hard_reg_in_set_p (hard_regno
, ALLOCNO_MODE (a
),
2056 reg_class_contents
[ALLOCNO_CLASS (a
)]));
2060 /* Evaluate overall allocation cost and the costs for using hard
2061 registers and memory for allocnos. */
2063 calculate_allocation_cost (void)
2065 int hard_regno
, cost
;
2067 ira_allocno_iterator ai
;
2069 ira_overall_cost
= ira_reg_cost
= ira_mem_cost
= 0;
2070 FOR_EACH_ALLOCNO (a
, ai
)
2072 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2073 ira_assert (hard_regno
< 0
2074 || (ira_hard_reg_in_set_p
2075 (hard_regno
, ALLOCNO_MODE (a
),
2076 reg_class_contents
[ALLOCNO_CLASS (a
)])));
2079 cost
= ALLOCNO_MEMORY_COST (a
);
2080 ira_mem_cost
+= cost
;
2082 else if (ALLOCNO_HARD_REG_COSTS (a
) != NULL
)
2084 cost
= (ALLOCNO_HARD_REG_COSTS (a
)
2085 [ira_class_hard_reg_index
2086 [ALLOCNO_CLASS (a
)][hard_regno
]]);
2087 ira_reg_cost
+= cost
;
2091 cost
= ALLOCNO_CLASS_COST (a
);
2092 ira_reg_cost
+= cost
;
2094 ira_overall_cost
+= cost
;
2097 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
2099 fprintf (ira_dump_file
,
2100 "+++Costs: overall %d, reg %d, mem %d, ld %d, st %d, move %d\n",
2101 ira_overall_cost
, ira_reg_cost
, ira_mem_cost
,
2102 ira_load_cost
, ira_store_cost
, ira_shuffle_cost
);
2103 fprintf (ira_dump_file
, "+++ move loops %d, new jumps %d\n",
2104 ira_move_loops_num
, ira_additional_jumps_num
);
2109 #ifdef ENABLE_IRA_CHECKING
2110 /* Check the correctness of the allocation. We do need this because
2111 of complicated code to transform more one region internal
2112 representation into one region representation. */
2114 check_allocation (void)
2117 int hard_regno
, nregs
, conflict_nregs
;
2118 ira_allocno_iterator ai
;
2120 FOR_EACH_ALLOCNO (a
, ai
)
2122 int n
= ALLOCNO_NUM_OBJECTS (a
);
2125 if (ALLOCNO_CAP_MEMBER (a
) != NULL
2126 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0)
2128 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (a
)];
2130 /* We allocated a single hard register. */
2133 /* We allocated multiple hard registers, and we will test
2134 conflicts in a granularity of single hard regs. */
2137 for (i
= 0; i
< n
; i
++)
2139 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2140 ira_object_t conflict_obj
;
2141 ira_object_conflict_iterator oci
;
2142 int this_regno
= hard_regno
;
2145 if (REG_WORDS_BIG_ENDIAN
)
2146 this_regno
+= n
- i
- 1;
2150 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2152 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2153 int conflict_hard_regno
= ALLOCNO_HARD_REGNO (conflict_a
);
2154 if (conflict_hard_regno
< 0)
2159 [conflict_hard_regno
][ALLOCNO_MODE (conflict_a
)]);
2161 if (ALLOCNO_NUM_OBJECTS (conflict_a
) > 1
2162 && conflict_nregs
== ALLOCNO_NUM_OBJECTS (conflict_a
))
2164 if (REG_WORDS_BIG_ENDIAN
)
2165 conflict_hard_regno
+= (ALLOCNO_NUM_OBJECTS (conflict_a
)
2166 - OBJECT_SUBWORD (conflict_obj
) - 1);
2168 conflict_hard_regno
+= OBJECT_SUBWORD (conflict_obj
);
2172 if ((conflict_hard_regno
<= this_regno
2173 && this_regno
< conflict_hard_regno
+ conflict_nregs
)
2174 || (this_regno
<= conflict_hard_regno
2175 && conflict_hard_regno
< this_regno
+ nregs
))
2177 fprintf (stderr
, "bad allocation for %d and %d\n",
2178 ALLOCNO_REGNO (a
), ALLOCNO_REGNO (conflict_a
));
2187 /* Fix values of array REG_EQUIV_INIT after live range splitting done
2190 fix_reg_equiv_init (void)
2192 unsigned int max_regno
= max_reg_num ();
2193 int i
, new_regno
, max
;
2194 rtx x
, prev
, next
, insn
, set
;
2196 if (VEC_length (reg_equivs_t
, reg_equivs
) < max_regno
)
2198 max
= VEC_length (reg_equivs_t
, reg_equivs
);
2200 for (i
= FIRST_PSEUDO_REGISTER
; i
< max
; i
++)
2201 for (prev
= NULL_RTX
, x
= reg_equiv_init (i
);
2207 set
= single_set (insn
);
2208 ira_assert (set
!= NULL_RTX
2209 && (REG_P (SET_DEST (set
)) || REG_P (SET_SRC (set
))));
2210 if (REG_P (SET_DEST (set
))
2211 && ((int) REGNO (SET_DEST (set
)) == i
2212 || (int) ORIGINAL_REGNO (SET_DEST (set
)) == i
))
2213 new_regno
= REGNO (SET_DEST (set
));
2214 else if (REG_P (SET_SRC (set
))
2215 && ((int) REGNO (SET_SRC (set
)) == i
2216 || (int) ORIGINAL_REGNO (SET_SRC (set
)) == i
))
2217 new_regno
= REGNO (SET_SRC (set
));
2224 if (prev
== NULL_RTX
)
2225 reg_equiv_init (i
) = next
;
2227 XEXP (prev
, 1) = next
;
2228 XEXP (x
, 1) = reg_equiv_init (new_regno
);
2229 reg_equiv_init (new_regno
) = x
;
2235 #ifdef ENABLE_IRA_CHECKING
2236 /* Print redundant memory-memory copies. */
2238 print_redundant_copies (void)
2242 ira_copy_t cp
, next_cp
;
2243 ira_allocno_iterator ai
;
2245 FOR_EACH_ALLOCNO (a
, ai
)
2247 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2250 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2251 if (hard_regno
>= 0)
2253 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2255 next_cp
= cp
->next_first_allocno_copy
;
2258 next_cp
= cp
->next_second_allocno_copy
;
2259 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
2260 && cp
->insn
!= NULL_RTX
2261 && ALLOCNO_HARD_REGNO (cp
->first
) == hard_regno
)
2262 fprintf (ira_dump_file
,
2263 " Redundant move from %d(freq %d):%d\n",
2264 INSN_UID (cp
->insn
), cp
->freq
, hard_regno
);
2270 /* Setup preferred and alternative classes for new pseudo-registers
2271 created by IRA starting with START. */
2273 setup_preferred_alternate_classes_for_new_pseudos (int start
)
2276 int max_regno
= max_reg_num ();
2278 for (i
= start
; i
< max_regno
; i
++)
2280 old_regno
= ORIGINAL_REGNO (regno_reg_rtx
[i
]);
2281 ira_assert (i
!= old_regno
);
2282 setup_reg_classes (i
, reg_preferred_class (old_regno
),
2283 reg_alternate_class (old_regno
),
2284 reg_allocno_class (old_regno
));
2285 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
2286 fprintf (ira_dump_file
,
2287 " New r%d: setting preferred %s, alternative %s\n",
2288 i
, reg_class_names
[reg_preferred_class (old_regno
)],
2289 reg_class_names
[reg_alternate_class (old_regno
)]);
2294 /* The number of entries allocated in teg_info. */
2295 static int allocated_reg_info_size
;
2297 /* Regional allocation can create new pseudo-registers. This function
2298 expands some arrays for pseudo-registers. */
2300 expand_reg_info (void)
2303 int size
= max_reg_num ();
2306 for (i
= allocated_reg_info_size
; i
< size
; i
++)
2307 setup_reg_classes (i
, GENERAL_REGS
, ALL_REGS
, GENERAL_REGS
);
2308 setup_preferred_alternate_classes_for_new_pseudos (allocated_reg_info_size
);
2309 allocated_reg_info_size
= size
;
2312 /* Return TRUE if there is too high register pressure in the function.
2313 It is used to decide when stack slot sharing is worth to do. */
2315 too_high_register_pressure_p (void)
2318 enum reg_class pclass
;
2320 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2322 pclass
= ira_pressure_classes
[i
];
2323 if (ira_loop_tree_root
->reg_pressure
[pclass
] > 10000)
2331 /* Indicate that hard register number FROM was eliminated and replaced with
2332 an offset from hard register number TO. The status of hard registers live
2333 at the start of a basic block is updated by replacing a use of FROM with
2337 mark_elimination (int from
, int to
)
2343 /* We don't use LIVE info in IRA. */
2344 bitmap r
= DF_LR_IN (bb
);
2346 if (REGNO_REG_SET_P (r
, from
))
2348 CLEAR_REGNO_REG_SET (r
, from
);
2349 SET_REGNO_REG_SET (r
, to
);
2358 /* Set when a REG_EQUIV note is found or created. Use to
2359 keep track of what memory accesses might be created later,
2363 /* The list of each instruction which initializes this register. */
2365 /* Loop depth is used to recognize equivalences which appear
2366 to be present within the same loop (or in an inner loop). */
2368 /* Nonzero if this had a preexisting REG_EQUIV note. */
2369 int is_arg_equivalence
;
2370 /* Set when an attempt should be made to replace a register
2371 with the associated src_p entry. */
2375 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
2376 structure for that register. */
2377 static struct equivalence
*reg_equiv
;
2379 /* Used for communication between the following two functions: contains
2380 a MEM that we wish to ensure remains unchanged. */
2381 static rtx equiv_mem
;
2383 /* Set nonzero if EQUIV_MEM is modified. */
2384 static int equiv_mem_modified
;
2386 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
2387 Called via note_stores. */
2389 validate_equiv_mem_from_store (rtx dest
, const_rtx set ATTRIBUTE_UNUSED
,
2390 void *data ATTRIBUTE_UNUSED
)
2393 && reg_overlap_mentioned_p (dest
, equiv_mem
))
2395 && true_dependence (dest
, VOIDmode
, equiv_mem
)))
2396 equiv_mem_modified
= 1;
2399 /* Verify that no store between START and the death of REG invalidates
2400 MEMREF. MEMREF is invalidated by modifying a register used in MEMREF,
2401 by storing into an overlapping memory location, or with a non-const
2404 Return 1 if MEMREF remains valid. */
2406 validate_equiv_mem (rtx start
, rtx reg
, rtx memref
)
2412 equiv_mem_modified
= 0;
2414 /* If the memory reference has side effects or is volatile, it isn't a
2415 valid equivalence. */
2416 if (side_effects_p (memref
))
2419 for (insn
= start
; insn
&& ! equiv_mem_modified
; insn
= NEXT_INSN (insn
))
2421 if (! INSN_P (insn
))
2424 if (find_reg_note (insn
, REG_DEAD
, reg
))
2427 /* This used to ignore readonly memory and const/pure calls. The problem
2428 is the equivalent form may reference a pseudo which gets assigned a
2429 call clobbered hard reg. When we later replace REG with its
2430 equivalent form, the value in the call-clobbered reg has been
2431 changed and all hell breaks loose. */
2435 note_stores (PATTERN (insn
), validate_equiv_mem_from_store
, NULL
);
2437 /* If a register mentioned in MEMREF is modified via an
2438 auto-increment, we lose the equivalence. Do the same if one
2439 dies; although we could extend the life, it doesn't seem worth
2442 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
2443 if ((REG_NOTE_KIND (note
) == REG_INC
2444 || REG_NOTE_KIND (note
) == REG_DEAD
)
2445 && REG_P (XEXP (note
, 0))
2446 && reg_overlap_mentioned_p (XEXP (note
, 0), memref
))
2453 /* Returns zero if X is known to be invariant. */
2455 equiv_init_varies_p (rtx x
)
2457 RTX_CODE code
= GET_CODE (x
);
2464 return !MEM_READONLY_P (x
) || equiv_init_varies_p (XEXP (x
, 0));
2473 return reg_equiv
[REGNO (x
)].replace
== 0 && rtx_varies_p (x
, 0);
2476 if (MEM_VOLATILE_P (x
))
2485 fmt
= GET_RTX_FORMAT (code
);
2486 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2489 if (equiv_init_varies_p (XEXP (x
, i
)))
2492 else if (fmt
[i
] == 'E')
2495 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2496 if (equiv_init_varies_p (XVECEXP (x
, i
, j
)))
2503 /* Returns nonzero if X (used to initialize register REGNO) is movable.
2504 X is only movable if the registers it uses have equivalent initializations
2505 which appear to be within the same loop (or in an inner loop) and movable
2506 or if they are not candidates for local_alloc and don't vary. */
2508 equiv_init_movable_p (rtx x
, int regno
)
2512 enum rtx_code code
= GET_CODE (x
);
2517 return equiv_init_movable_p (SET_SRC (x
), regno
);
2532 return ((reg_equiv
[REGNO (x
)].loop_depth
>= reg_equiv
[regno
].loop_depth
2533 && reg_equiv
[REGNO (x
)].replace
)
2534 || (REG_BASIC_BLOCK (REGNO (x
)) < NUM_FIXED_BLOCKS
2535 && ! rtx_varies_p (x
, 0)));
2537 case UNSPEC_VOLATILE
:
2541 if (MEM_VOLATILE_P (x
))
2550 fmt
= GET_RTX_FORMAT (code
);
2551 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2555 if (! equiv_init_movable_p (XEXP (x
, i
), regno
))
2559 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2560 if (! equiv_init_movable_p (XVECEXP (x
, i
, j
), regno
))
2568 /* TRUE if X uses any registers for which reg_equiv[REGNO].replace is
2571 contains_replace_regs (rtx x
)
2575 enum rtx_code code
= GET_CODE (x
);
2589 return reg_equiv
[REGNO (x
)].replace
;
2595 fmt
= GET_RTX_FORMAT (code
);
2596 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2600 if (contains_replace_regs (XEXP (x
, i
)))
2604 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2605 if (contains_replace_regs (XVECEXP (x
, i
, j
)))
2613 /* TRUE if X references a memory location that would be affected by a store
2616 memref_referenced_p (rtx memref
, rtx x
)
2620 enum rtx_code code
= GET_CODE (x
);
2635 return (reg_equiv
[REGNO (x
)].replacement
2636 && memref_referenced_p (memref
,
2637 reg_equiv
[REGNO (x
)].replacement
));
2640 if (true_dependence (memref
, VOIDmode
, x
))
2645 /* If we are setting a MEM, it doesn't count (its address does), but any
2646 other SET_DEST that has a MEM in it is referencing the MEM. */
2647 if (MEM_P (SET_DEST (x
)))
2649 if (memref_referenced_p (memref
, XEXP (SET_DEST (x
), 0)))
2652 else if (memref_referenced_p (memref
, SET_DEST (x
)))
2655 return memref_referenced_p (memref
, SET_SRC (x
));
2661 fmt
= GET_RTX_FORMAT (code
);
2662 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2666 if (memref_referenced_p (memref
, XEXP (x
, i
)))
2670 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2671 if (memref_referenced_p (memref
, XVECEXP (x
, i
, j
)))
2679 /* TRUE if some insn in the range (START, END] references a memory location
2680 that would be affected by a store to MEMREF. */
2682 memref_used_between_p (rtx memref
, rtx start
, rtx end
)
2686 for (insn
= NEXT_INSN (start
); insn
!= NEXT_INSN (end
);
2687 insn
= NEXT_INSN (insn
))
2689 if (!NONDEBUG_INSN_P (insn
))
2692 if (memref_referenced_p (memref
, PATTERN (insn
)))
2695 /* Nonconst functions may access memory. */
2696 if (CALL_P (insn
) && (! RTL_CONST_CALL_P (insn
)))
2703 /* Mark REG as having no known equivalence.
2704 Some instructions might have been processed before and furnished
2705 with REG_EQUIV notes for this register; these notes will have to be
2707 STORE is the piece of RTL that does the non-constant / conflicting
2708 assignment - a SET, CLOBBER or REG_INC note. It is currently not used,
2709 but needs to be there because this function is called from note_stores. */
2711 no_equiv (rtx reg
, const_rtx store ATTRIBUTE_UNUSED
,
2712 void *data ATTRIBUTE_UNUSED
)
2719 regno
= REGNO (reg
);
2720 list
= reg_equiv
[regno
].init_insns
;
2721 if (list
== const0_rtx
)
2723 reg_equiv
[regno
].init_insns
= const0_rtx
;
2724 reg_equiv
[regno
].replacement
= NULL_RTX
;
2725 /* This doesn't matter for equivalences made for argument registers, we
2726 should keep their initialization insns. */
2727 if (reg_equiv
[regno
].is_arg_equivalence
)
2729 reg_equiv_init (regno
) = NULL_RTX
;
2730 for (; list
; list
= XEXP (list
, 1))
2732 rtx insn
= XEXP (list
, 0);
2733 remove_note (insn
, find_reg_note (insn
, REG_EQUIV
, NULL_RTX
));
2737 /* In DEBUG_INSN location adjust REGs from CLEARED_REGS bitmap to the
2738 equivalent replacement. */
2741 adjust_cleared_regs (rtx loc
, const_rtx old_rtx ATTRIBUTE_UNUSED
, void *data
)
2745 bitmap cleared_regs
= (bitmap
) data
;
2746 if (bitmap_bit_p (cleared_regs
, REGNO (loc
)))
2747 return simplify_replace_fn_rtx (*reg_equiv
[REGNO (loc
)].src_p
,
2748 NULL_RTX
, adjust_cleared_regs
, data
);
2753 /* Nonzero if we recorded an equivalence for a LABEL_REF. */
2754 static int recorded_label_ref
;
2756 /* Find registers that are equivalent to a single value throughout the
2757 compilation (either because they can be referenced in memory or are
2758 set once from a single constant). Lower their priority for a
2761 If such a register is only referenced once, try substituting its
2762 value into the using insn. If it succeeds, we can eliminate the
2763 register completely.
2765 Initialize the REG_EQUIV_INIT array of initializing insns.
2767 Return non-zero if jump label rebuilding should be done. */
2769 update_equiv_regs (void)
2774 bitmap cleared_regs
;
2776 /* We need to keep track of whether or not we recorded a LABEL_REF so
2777 that we know if the jump optimizer needs to be rerun. */
2778 recorded_label_ref
= 0;
2780 reg_equiv
= XCNEWVEC (struct equivalence
, max_regno
);
2783 init_alias_analysis ();
2785 /* Scan the insns and find which registers have equivalences. Do this
2786 in a separate scan of the insns because (due to -fcse-follow-jumps)
2787 a register can be set below its use. */
2790 loop_depth
= bb_loop_depth (bb
);
2792 for (insn
= BB_HEAD (bb
);
2793 insn
!= NEXT_INSN (BB_END (bb
));
2794 insn
= NEXT_INSN (insn
))
2801 if (! INSN_P (insn
))
2804 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
2805 if (REG_NOTE_KIND (note
) == REG_INC
)
2806 no_equiv (XEXP (note
, 0), note
, NULL
);
2808 set
= single_set (insn
);
2810 /* If this insn contains more (or less) than a single SET,
2811 only mark all destinations as having no known equivalence. */
2814 note_stores (PATTERN (insn
), no_equiv
, NULL
);
2817 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2821 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
2823 rtx part
= XVECEXP (PATTERN (insn
), 0, i
);
2825 note_stores (part
, no_equiv
, NULL
);
2829 dest
= SET_DEST (set
);
2830 src
= SET_SRC (set
);
2832 /* See if this is setting up the equivalence between an argument
2833 register and its stack slot. */
2834 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
2837 gcc_assert (REG_P (dest
));
2838 regno
= REGNO (dest
);
2840 /* Note that we don't want to clear reg_equiv_init even if there
2841 are multiple sets of this register. */
2842 reg_equiv
[regno
].is_arg_equivalence
= 1;
2844 /* Record for reload that this is an equivalencing insn. */
2845 if (rtx_equal_p (src
, XEXP (note
, 0)))
2846 reg_equiv_init (regno
)
2847 = gen_rtx_INSN_LIST (VOIDmode
, insn
, reg_equiv_init (regno
));
2849 /* Continue normally in case this is a candidate for
2856 /* We only handle the case of a pseudo register being set
2857 once, or always to the same value. */
2858 /* ??? The mn10200 port breaks if we add equivalences for
2859 values that need an ADDRESS_REGS register and set them equivalent
2860 to a MEM of a pseudo. The actual problem is in the over-conservative
2861 handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
2862 calculate_needs, but we traditionally work around this problem
2863 here by rejecting equivalences when the destination is in a register
2864 that's likely spilled. This is fragile, of course, since the
2865 preferred class of a pseudo depends on all instructions that set
2869 || (regno
= REGNO (dest
)) < FIRST_PSEUDO_REGISTER
2870 || reg_equiv
[regno
].init_insns
== const0_rtx
2871 || (targetm
.class_likely_spilled_p (reg_preferred_class (regno
))
2872 && MEM_P (src
) && ! reg_equiv
[regno
].is_arg_equivalence
))
2874 /* This might be setting a SUBREG of a pseudo, a pseudo that is
2875 also set somewhere else to a constant. */
2876 note_stores (set
, no_equiv
, NULL
);
2880 note
= find_reg_note (insn
, REG_EQUAL
, NULL_RTX
);
2882 /* cse sometimes generates function invariants, but doesn't put a
2883 REG_EQUAL note on the insn. Since this note would be redundant,
2884 there's no point creating it earlier than here. */
2885 if (! note
&& ! rtx_varies_p (src
, 0))
2886 note
= set_unique_reg_note (insn
, REG_EQUAL
, copy_rtx (src
));
2888 /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
2889 since it represents a function call */
2890 if (note
&& GET_CODE (XEXP (note
, 0)) == EXPR_LIST
)
2893 if (DF_REG_DEF_COUNT (regno
) != 1
2895 || rtx_varies_p (XEXP (note
, 0), 0)
2896 || (reg_equiv
[regno
].replacement
2897 && ! rtx_equal_p (XEXP (note
, 0),
2898 reg_equiv
[regno
].replacement
))))
2900 no_equiv (dest
, set
, NULL
);
2903 /* Record this insn as initializing this register. */
2904 reg_equiv
[regno
].init_insns
2905 = gen_rtx_INSN_LIST (VOIDmode
, insn
, reg_equiv
[regno
].init_insns
);
2907 /* If this register is known to be equal to a constant, record that
2908 it is always equivalent to the constant. */
2909 if (DF_REG_DEF_COUNT (regno
) == 1
2910 && note
&& ! rtx_varies_p (XEXP (note
, 0), 0))
2912 rtx note_value
= XEXP (note
, 0);
2913 remove_note (insn
, note
);
2914 set_unique_reg_note (insn
, REG_EQUIV
, note_value
);
2917 /* If this insn introduces a "constant" register, decrease the priority
2918 of that register. Record this insn if the register is only used once
2919 more and the equivalence value is the same as our source.
2921 The latter condition is checked for two reasons: First, it is an
2922 indication that it may be more efficient to actually emit the insn
2923 as written (if no registers are available, reload will substitute
2924 the equivalence). Secondly, it avoids problems with any registers
2925 dying in this insn whose death notes would be missed.
2927 If we don't have a REG_EQUIV note, see if this insn is loading
2928 a register used only in one basic block from a MEM. If so, and the
2929 MEM remains unchanged for the life of the register, add a REG_EQUIV
2932 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
2934 if (note
== 0 && REG_BASIC_BLOCK (regno
) >= NUM_FIXED_BLOCKS
2935 && MEM_P (SET_SRC (set
))
2936 && validate_equiv_mem (insn
, dest
, SET_SRC (set
)))
2937 note
= set_unique_reg_note (insn
, REG_EQUIV
, copy_rtx (SET_SRC (set
)));
2941 int regno
= REGNO (dest
);
2942 rtx x
= XEXP (note
, 0);
2944 /* If we haven't done so, record for reload that this is an
2945 equivalencing insn. */
2946 if (!reg_equiv
[regno
].is_arg_equivalence
)
2947 reg_equiv_init (regno
)
2948 = gen_rtx_INSN_LIST (VOIDmode
, insn
, reg_equiv_init (regno
));
2950 /* Record whether or not we created a REG_EQUIV note for a LABEL_REF.
2951 We might end up substituting the LABEL_REF for uses of the
2952 pseudo here or later. That kind of transformation may turn an
2953 indirect jump into a direct jump, in which case we must rerun the
2954 jump optimizer to ensure that the JUMP_LABEL fields are valid. */
2955 if (GET_CODE (x
) == LABEL_REF
2956 || (GET_CODE (x
) == CONST
2957 && GET_CODE (XEXP (x
, 0)) == PLUS
2958 && (GET_CODE (XEXP (XEXP (x
, 0), 0)) == LABEL_REF
)))
2959 recorded_label_ref
= 1;
2961 reg_equiv
[regno
].replacement
= x
;
2962 reg_equiv
[regno
].src_p
= &SET_SRC (set
);
2963 reg_equiv
[regno
].loop_depth
= loop_depth
;
2965 /* Don't mess with things live during setjmp. */
2966 if (REG_LIVE_LENGTH (regno
) >= 0 && optimize
)
2968 /* Note that the statement below does not affect the priority
2970 REG_LIVE_LENGTH (regno
) *= 2;
2972 /* If the register is referenced exactly twice, meaning it is
2973 set once and used once, indicate that the reference may be
2974 replaced by the equivalence we computed above. Do this
2975 even if the register is only used in one block so that
2976 dependencies can be handled where the last register is
2977 used in a different block (i.e. HIGH / LO_SUM sequences)
2978 and to reduce the number of registers alive across
2981 if (REG_N_REFS (regno
) == 2
2982 && (rtx_equal_p (x
, src
)
2983 || ! equiv_init_varies_p (src
))
2984 && NONJUMP_INSN_P (insn
)
2985 && equiv_init_movable_p (PATTERN (insn
), regno
))
2986 reg_equiv
[regno
].replace
= 1;
2995 /* A second pass, to gather additional equivalences with memory. This needs
2996 to be done after we know which registers we are going to replace. */
2998 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
3003 if (! INSN_P (insn
))
3006 set
= single_set (insn
);
3010 dest
= SET_DEST (set
);
3011 src
= SET_SRC (set
);
3013 /* If this sets a MEM to the contents of a REG that is only used
3014 in a single basic block, see if the register is always equivalent
3015 to that memory location and if moving the store from INSN to the
3016 insn that set REG is safe. If so, put a REG_EQUIV note on the
3019 Don't add a REG_EQUIV note if the insn already has one. The existing
3020 REG_EQUIV is likely more useful than the one we are adding.
3022 If one of the regs in the address has reg_equiv[REGNO].replace set,
3023 then we can't add this REG_EQUIV note. The reg_equiv[REGNO].replace
3024 optimization may move the set of this register immediately before
3025 insn, which puts it after reg_equiv[REGNO].init_insns, and hence
3026 the mention in the REG_EQUIV note would be to an uninitialized
3029 if (MEM_P (dest
) && REG_P (src
)
3030 && (regno
= REGNO (src
)) >= FIRST_PSEUDO_REGISTER
3031 && REG_BASIC_BLOCK (regno
) >= NUM_FIXED_BLOCKS
3032 && DF_REG_DEF_COUNT (regno
) == 1
3033 && reg_equiv
[regno
].init_insns
!= 0
3034 && reg_equiv
[regno
].init_insns
!= const0_rtx
3035 && ! find_reg_note (XEXP (reg_equiv
[regno
].init_insns
, 0),
3036 REG_EQUIV
, NULL_RTX
)
3037 && ! contains_replace_regs (XEXP (dest
, 0)))
3039 rtx init_insn
= XEXP (reg_equiv
[regno
].init_insns
, 0);
3040 if (validate_equiv_mem (init_insn
, src
, dest
)
3041 && ! memref_used_between_p (dest
, init_insn
, insn
)
3042 /* Attaching a REG_EQUIV note will fail if INIT_INSN has
3044 && set_unique_reg_note (init_insn
, REG_EQUIV
, copy_rtx (dest
)))
3046 /* This insn makes the equivalence, not the one initializing
3048 reg_equiv_init (regno
)
3049 = gen_rtx_INSN_LIST (VOIDmode
, insn
, NULL_RTX
);
3050 df_notes_rescan (init_insn
);
3055 cleared_regs
= BITMAP_ALLOC (NULL
);
3056 /* Now scan all regs killed in an insn to see if any of them are
3057 registers only used that once. If so, see if we can replace the
3058 reference with the equivalent form. If we can, delete the
3059 initializing reference and this register will go away. If we
3060 can't replace the reference, and the initializing reference is
3061 within the same loop (or in an inner loop), then move the register
3062 initialization just before the use, so that they are in the same
3064 FOR_EACH_BB_REVERSE (bb
)
3066 loop_depth
= bb_loop_depth (bb
);
3067 for (insn
= BB_END (bb
);
3068 insn
!= PREV_INSN (BB_HEAD (bb
));
3069 insn
= PREV_INSN (insn
))
3073 if (! INSN_P (insn
))
3076 /* Don't substitute into a non-local goto, this confuses CFG. */
3078 && find_reg_note (insn
, REG_NON_LOCAL_GOTO
, NULL_RTX
))
3081 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
3083 if (REG_NOTE_KIND (link
) == REG_DEAD
3084 /* Make sure this insn still refers to the register. */
3085 && reg_mentioned_p (XEXP (link
, 0), PATTERN (insn
)))
3087 int regno
= REGNO (XEXP (link
, 0));
3090 if (! reg_equiv
[regno
].replace
3091 || reg_equiv
[regno
].loop_depth
< loop_depth
3092 /* There is no sense to move insns if we did
3093 register pressure-sensitive scheduling was
3094 done because it will not improve allocation
3095 but worsen insn schedule with a big
3097 || (flag_sched_pressure
&& flag_schedule_insns
))
3100 /* reg_equiv[REGNO].replace gets set only when
3101 REG_N_REFS[REGNO] is 2, i.e. the register is set
3102 once and used once. (If it were only set, but not used,
3103 flow would have deleted the setting insns.) Hence
3104 there can only be one insn in reg_equiv[REGNO].init_insns. */
3105 gcc_assert (reg_equiv
[regno
].init_insns
3106 && !XEXP (reg_equiv
[regno
].init_insns
, 1));
3107 equiv_insn
= XEXP (reg_equiv
[regno
].init_insns
, 0);
3109 /* We may not move instructions that can throw, since
3110 that changes basic block boundaries and we are not
3111 prepared to adjust the CFG to match. */
3112 if (can_throw_internal (equiv_insn
))
3115 if (asm_noperands (PATTERN (equiv_insn
)) < 0
3116 && validate_replace_rtx (regno_reg_rtx
[regno
],
3117 *(reg_equiv
[regno
].src_p
), insn
))
3123 /* Find the last note. */
3124 for (last_link
= link
; XEXP (last_link
, 1);
3125 last_link
= XEXP (last_link
, 1))
3128 /* Append the REG_DEAD notes from equiv_insn. */
3129 equiv_link
= REG_NOTES (equiv_insn
);
3133 equiv_link
= XEXP (equiv_link
, 1);
3134 if (REG_NOTE_KIND (note
) == REG_DEAD
)
3136 remove_note (equiv_insn
, note
);
3137 XEXP (last_link
, 1) = note
;
3138 XEXP (note
, 1) = NULL_RTX
;
3143 remove_death (regno
, insn
);
3144 SET_REG_N_REFS (regno
, 0);
3145 REG_FREQ (regno
) = 0;
3146 delete_insn (equiv_insn
);
3148 reg_equiv
[regno
].init_insns
3149 = XEXP (reg_equiv
[regno
].init_insns
, 1);
3151 reg_equiv_init (regno
) = NULL_RTX
;
3152 bitmap_set_bit (cleared_regs
, regno
);
3154 /* Move the initialization of the register to just before
3155 INSN. Update the flow information. */
3156 else if (prev_nondebug_insn (insn
) != equiv_insn
)
3160 new_insn
= emit_insn_before (PATTERN (equiv_insn
), insn
);
3161 REG_NOTES (new_insn
) = REG_NOTES (equiv_insn
);
3162 REG_NOTES (equiv_insn
) = 0;
3163 /* Rescan it to process the notes. */
3164 df_insn_rescan (new_insn
);
3166 /* Make sure this insn is recognized before
3167 reload begins, otherwise
3168 eliminate_regs_in_insn will die. */
3169 INSN_CODE (new_insn
) = INSN_CODE (equiv_insn
);
3171 delete_insn (equiv_insn
);
3173 XEXP (reg_equiv
[regno
].init_insns
, 0) = new_insn
;
3175 REG_BASIC_BLOCK (regno
) = bb
->index
;
3176 REG_N_CALLS_CROSSED (regno
) = 0;
3177 REG_FREQ_CALLS_CROSSED (regno
) = 0;
3178 REG_N_THROWING_CALLS_CROSSED (regno
) = 0;
3179 REG_LIVE_LENGTH (regno
) = 2;
3181 if (insn
== BB_HEAD (bb
))
3182 BB_HEAD (bb
) = PREV_INSN (insn
);
3184 reg_equiv_init (regno
)
3185 = gen_rtx_INSN_LIST (VOIDmode
, new_insn
, NULL_RTX
);
3186 bitmap_set_bit (cleared_regs
, regno
);
3193 if (!bitmap_empty_p (cleared_regs
))
3197 bitmap_and_compl_into (DF_LIVE_IN (bb
), cleared_regs
);
3198 bitmap_and_compl_into (DF_LIVE_OUT (bb
), cleared_regs
);
3199 bitmap_and_compl_into (DF_LR_IN (bb
), cleared_regs
);
3200 bitmap_and_compl_into (DF_LR_OUT (bb
), cleared_regs
);
3203 /* Last pass - adjust debug insns referencing cleared regs. */
3204 if (MAY_HAVE_DEBUG_INSNS
)
3205 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
3206 if (DEBUG_INSN_P (insn
))
3208 rtx old_loc
= INSN_VAR_LOCATION_LOC (insn
);
3209 INSN_VAR_LOCATION_LOC (insn
)
3210 = simplify_replace_fn_rtx (old_loc
, NULL_RTX
,
3211 adjust_cleared_regs
,
3212 (void *) cleared_regs
);
3213 if (old_loc
!= INSN_VAR_LOCATION_LOC (insn
))
3214 df_insn_rescan (insn
);
3218 BITMAP_FREE (cleared_regs
);
3223 end_alias_analysis ();
3225 return recorded_label_ref
;
3230 /* Print chain C to FILE. */
3232 print_insn_chain (FILE *file
, struct insn_chain
*c
)
3234 fprintf (file
, "insn=%d, ", INSN_UID(c
->insn
));
3235 bitmap_print (file
, &c
->live_throughout
, "live_throughout: ", ", ");
3236 bitmap_print (file
, &c
->dead_or_set
, "dead_or_set: ", "\n");
3240 /* Print all reload_insn_chains to FILE. */
3242 print_insn_chains (FILE *file
)
3244 struct insn_chain
*c
;
3245 for (c
= reload_insn_chain
; c
; c
= c
->next
)
3246 print_insn_chain (file
, c
);
3249 /* Return true if pseudo REGNO should be added to set live_throughout
3250 or dead_or_set of the insn chains for reload consideration. */
3252 pseudo_for_reload_consideration_p (int regno
)
3254 /* Consider spilled pseudos too for IRA because they still have a
3255 chance to get hard-registers in the reload when IRA is used. */
3256 return (reg_renumber
[regno
] >= 0 || ira_conflicts_p
);
3259 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
3260 REG to the number of nregs, and INIT_VALUE to get the
3261 initialization. ALLOCNUM need not be the regno of REG. */
3263 init_live_subregs (bool init_value
, sbitmap
*live_subregs
,
3264 bitmap live_subregs_used
, int allocnum
, rtx reg
)
3266 unsigned int regno
= REGNO (SUBREG_REG (reg
));
3267 int size
= GET_MODE_SIZE (GET_MODE (regno_reg_rtx
[regno
]));
3269 gcc_assert (size
> 0);
3271 /* Been there, done that. */
3272 if (bitmap_bit_p (live_subregs_used
, allocnum
))
3275 /* Create a new one. */
3276 if (live_subregs
[allocnum
] == NULL
)
3277 live_subregs
[allocnum
] = sbitmap_alloc (size
);
3279 /* If the entire reg was live before blasting into subregs, we need
3280 to init all of the subregs to ones else init to 0. */
3282 sbitmap_ones (live_subregs
[allocnum
]);
3284 sbitmap_zero (live_subregs
[allocnum
]);
3286 bitmap_set_bit (live_subregs_used
, allocnum
);
3289 /* Walk the insns of the current function and build reload_insn_chain,
3290 and record register life information. */
3292 build_insn_chain (void)
3295 struct insn_chain
**p
= &reload_insn_chain
;
3297 struct insn_chain
*c
= NULL
;
3298 struct insn_chain
*next
= NULL
;
3299 bitmap live_relevant_regs
= BITMAP_ALLOC (NULL
);
3300 bitmap elim_regset
= BITMAP_ALLOC (NULL
);
3301 /* live_subregs is a vector used to keep accurate information about
3302 which hardregs are live in multiword pseudos. live_subregs and
3303 live_subregs_used are indexed by pseudo number. The live_subreg
3304 entry for a particular pseudo is only used if the corresponding
3305 element is non zero in live_subregs_used. The sbitmap size of
3306 live_subreg[allocno] is number of bytes that the pseudo can
3308 sbitmap
*live_subregs
= XCNEWVEC (sbitmap
, max_regno
);
3309 bitmap live_subregs_used
= BITMAP_ALLOC (NULL
);
3311 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3312 if (TEST_HARD_REG_BIT (eliminable_regset
, i
))
3313 bitmap_set_bit (elim_regset
, i
);
3314 FOR_EACH_BB_REVERSE (bb
)
3319 CLEAR_REG_SET (live_relevant_regs
);
3320 bitmap_clear (live_subregs_used
);
3322 EXECUTE_IF_SET_IN_BITMAP (DF_LR_OUT (bb
), 0, i
, bi
)
3324 if (i
>= FIRST_PSEUDO_REGISTER
)
3326 bitmap_set_bit (live_relevant_regs
, i
);
3329 EXECUTE_IF_SET_IN_BITMAP (DF_LR_OUT (bb
),
3330 FIRST_PSEUDO_REGISTER
, i
, bi
)
3332 if (pseudo_for_reload_consideration_p (i
))
3333 bitmap_set_bit (live_relevant_regs
, i
);
3336 FOR_BB_INSNS_REVERSE (bb
, insn
)
3338 if (!NOTE_P (insn
) && !BARRIER_P (insn
))
3340 unsigned int uid
= INSN_UID (insn
);
3344 c
= new_insn_chain ();
3351 c
->block
= bb
->index
;
3354 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3356 df_ref def
= *def_rec
;
3357 unsigned int regno
= DF_REF_REGNO (def
);
3359 /* Ignore may clobbers because these are generated
3360 from calls. However, every other kind of def is
3361 added to dead_or_set. */
3362 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
3364 if (regno
< FIRST_PSEUDO_REGISTER
)
3366 if (!fixed_regs
[regno
])
3367 bitmap_set_bit (&c
->dead_or_set
, regno
);
3369 else if (pseudo_for_reload_consideration_p (regno
))
3370 bitmap_set_bit (&c
->dead_or_set
, regno
);
3373 if ((regno
< FIRST_PSEUDO_REGISTER
3374 || reg_renumber
[regno
] >= 0
3376 && (!DF_REF_FLAGS_IS_SET (def
, DF_REF_CONDITIONAL
)))
3378 rtx reg
= DF_REF_REG (def
);
3380 /* We can model subregs, but not if they are
3381 wrapped in ZERO_EXTRACTS. */
3382 if (GET_CODE (reg
) == SUBREG
3383 && !DF_REF_FLAGS_IS_SET (def
, DF_REF_ZERO_EXTRACT
))
3385 unsigned int start
= SUBREG_BYTE (reg
);
3386 unsigned int last
= start
3387 + GET_MODE_SIZE (GET_MODE (reg
));
3390 (bitmap_bit_p (live_relevant_regs
, regno
),
3391 live_subregs
, live_subregs_used
, regno
, reg
);
3393 if (!DF_REF_FLAGS_IS_SET
3394 (def
, DF_REF_STRICT_LOW_PART
))
3396 /* Expand the range to cover entire words.
3397 Bytes added here are "don't care". */
3399 = start
/ UNITS_PER_WORD
* UNITS_PER_WORD
;
3400 last
= ((last
+ UNITS_PER_WORD
- 1)
3401 / UNITS_PER_WORD
* UNITS_PER_WORD
);
3404 /* Ignore the paradoxical bits. */
3405 if (last
> SBITMAP_SIZE (live_subregs
[regno
]))
3406 last
= SBITMAP_SIZE (live_subregs
[regno
]);
3408 while (start
< last
)
3410 RESET_BIT (live_subregs
[regno
], start
);
3414 if (sbitmap_empty_p (live_subregs
[regno
]))
3416 bitmap_clear_bit (live_subregs_used
, regno
);
3417 bitmap_clear_bit (live_relevant_regs
, regno
);
3420 /* Set live_relevant_regs here because
3421 that bit has to be true to get us to
3422 look at the live_subregs fields. */
3423 bitmap_set_bit (live_relevant_regs
, regno
);
3427 /* DF_REF_PARTIAL is generated for
3428 subregs, STRICT_LOW_PART, and
3429 ZERO_EXTRACT. We handle the subreg
3430 case above so here we have to keep from
3431 modeling the def as a killing def. */
3432 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
))
3434 bitmap_clear_bit (live_subregs_used
, regno
);
3435 bitmap_clear_bit (live_relevant_regs
, regno
);
3441 bitmap_and_compl_into (live_relevant_regs
, elim_regset
);
3442 bitmap_copy (&c
->live_throughout
, live_relevant_regs
);
3445 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
3447 df_ref use
= *use_rec
;
3448 unsigned int regno
= DF_REF_REGNO (use
);
3449 rtx reg
= DF_REF_REG (use
);
3451 /* DF_REF_READ_WRITE on a use means that this use
3452 is fabricated from a def that is a partial set
3453 to a multiword reg. Here, we only model the
3454 subreg case that is not wrapped in ZERO_EXTRACT
3455 precisely so we do not need to look at the
3457 if (DF_REF_FLAGS_IS_SET (use
, DF_REF_READ_WRITE
)
3458 && !DF_REF_FLAGS_IS_SET (use
, DF_REF_ZERO_EXTRACT
)
3459 && DF_REF_FLAGS_IS_SET (use
, DF_REF_SUBREG
))
3462 /* Add the last use of each var to dead_or_set. */
3463 if (!bitmap_bit_p (live_relevant_regs
, regno
))
3465 if (regno
< FIRST_PSEUDO_REGISTER
)
3467 if (!fixed_regs
[regno
])
3468 bitmap_set_bit (&c
->dead_or_set
, regno
);
3470 else if (pseudo_for_reload_consideration_p (regno
))
3471 bitmap_set_bit (&c
->dead_or_set
, regno
);
3474 if (regno
< FIRST_PSEUDO_REGISTER
3475 || pseudo_for_reload_consideration_p (regno
))
3477 if (GET_CODE (reg
) == SUBREG
3478 && !DF_REF_FLAGS_IS_SET (use
,
3480 | DF_REF_ZERO_EXTRACT
))
3482 unsigned int start
= SUBREG_BYTE (reg
);
3483 unsigned int last
= start
3484 + GET_MODE_SIZE (GET_MODE (reg
));
3487 (bitmap_bit_p (live_relevant_regs
, regno
),
3488 live_subregs
, live_subregs_used
, regno
, reg
);
3490 /* Ignore the paradoxical bits. */
3491 if (last
> SBITMAP_SIZE (live_subregs
[regno
]))
3492 last
= SBITMAP_SIZE (live_subregs
[regno
]);
3494 while (start
< last
)
3496 SET_BIT (live_subregs
[regno
], start
);
3501 /* Resetting the live_subregs_used is
3502 effectively saying do not use the subregs
3503 because we are reading the whole
3505 bitmap_clear_bit (live_subregs_used
, regno
);
3506 bitmap_set_bit (live_relevant_regs
, regno
);
3512 /* FIXME!! The following code is a disaster. Reload needs to see the
3513 labels and jump tables that are just hanging out in between
3514 the basic blocks. See pr33676. */
3515 insn
= BB_HEAD (bb
);
3517 /* Skip over the barriers and cruft. */
3518 while (insn
&& (BARRIER_P (insn
) || NOTE_P (insn
)
3519 || BLOCK_FOR_INSN (insn
) == bb
))
3520 insn
= PREV_INSN (insn
);
3522 /* While we add anything except barriers and notes, the focus is
3523 to get the labels and jump tables into the
3524 reload_insn_chain. */
3527 if (!NOTE_P (insn
) && !BARRIER_P (insn
))
3529 if (BLOCK_FOR_INSN (insn
))
3532 c
= new_insn_chain ();
3538 /* The block makes no sense here, but it is what the old
3540 c
->block
= bb
->index
;
3542 bitmap_copy (&c
->live_throughout
, live_relevant_regs
);
3544 insn
= PREV_INSN (insn
);
3548 reload_insn_chain
= c
;
3551 for (i
= 0; i
< (unsigned int) max_regno
; i
++)
3552 if (live_subregs
[i
] != NULL
)
3553 sbitmap_free (live_subregs
[i
]);
3554 free (live_subregs
);
3555 BITMAP_FREE (live_subregs_used
);
3556 BITMAP_FREE (live_relevant_regs
);
3557 BITMAP_FREE (elim_regset
);
3560 print_insn_chains (dump_file
);
3563 /* Examine the rtx found in *LOC, which is read or written to as determined
3564 by TYPE. Return false if we find a reason why an insn containing this
3565 rtx should not be moved (such as accesses to non-constant memory), true
3568 rtx_moveable_p (rtx
*loc
, enum op_type type
)
3572 enum rtx_code code
= GET_CODE (x
);
3575 code
= GET_CODE (x
);
3585 return type
== OP_IN
;
3591 if (x
== frame_pointer_rtx
)
3593 if (HARD_REGISTER_P (x
))
3599 if (type
== OP_IN
&& MEM_READONLY_P (x
))
3600 return rtx_moveable_p (&XEXP (x
, 0), OP_IN
);
3604 return (rtx_moveable_p (&SET_SRC (x
), OP_IN
)
3605 && rtx_moveable_p (&SET_DEST (x
), OP_OUT
));
3607 case STRICT_LOW_PART
:
3608 return rtx_moveable_p (&XEXP (x
, 0), OP_OUT
);
3612 return (rtx_moveable_p (&XEXP (x
, 0), type
)
3613 && rtx_moveable_p (&XEXP (x
, 1), OP_IN
)
3614 && rtx_moveable_p (&XEXP (x
, 2), OP_IN
));
3617 return rtx_moveable_p (&SET_DEST (x
), OP_OUT
);
3623 fmt
= GET_RTX_FORMAT (code
);
3624 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3628 if (!rtx_moveable_p (&XEXP (x
, i
), type
))
3631 else if (fmt
[i
] == 'E')
3632 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
3634 if (!rtx_moveable_p (&XVECEXP (x
, i
, j
), type
))
3641 /* A wrapper around dominated_by_p, which uses the information in UID_LUID
3642 to give dominance relationships between two insns I1 and I2. */
3644 insn_dominated_by_p (rtx i1
, rtx i2
, int *uid_luid
)
3646 basic_block bb1
= BLOCK_FOR_INSN (i1
);
3647 basic_block bb2
= BLOCK_FOR_INSN (i2
);
3650 return uid_luid
[INSN_UID (i2
)] < uid_luid
[INSN_UID (i1
)];
3651 return dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
);
3654 /* Record the range of register numbers added by find_moveable_pseudos. */
3655 int first_moveable_pseudo
, last_moveable_pseudo
;
3657 /* These two vectors hold data for every register added by
3658 find_movable_pseudos, with index 0 holding data for the
3659 first_moveable_pseudo. */
3660 /* The original home register. */
3661 static VEC (rtx
, heap
) *pseudo_replaced_reg
;
3663 /* Look for instances where we have an instruction that is known to increase
3664 register pressure, and whose result is not used immediately. If it is
3665 possible to move the instruction downwards to just before its first use,
3666 split its lifetime into two ranges. We create a new pseudo to compute the
3667 value, and emit a move instruction just before the first use. If, after
3668 register allocation, the new pseudo remains unallocated, the function
3669 move_unallocated_pseudos then deletes the move instruction and places
3670 the computation just before the first use.
3672 Such a move is safe and profitable if all the input registers remain live
3673 and unchanged between the original computation and its first use. In such
3674 a situation, the computation is known to increase register pressure, and
3675 moving it is known to at least not worsen it.
3677 We restrict moves to only those cases where a register remains unallocated,
3678 in order to avoid interfering too much with the instruction schedule. As
3679 an exception, we may move insns which only modify their input register
3680 (typically induction variables), as this increases the freedom for our
3681 intended transformation, and does not limit the second instruction
3685 find_moveable_pseudos (void)
3688 int max_regs
= max_reg_num ();
3689 int max_uid
= get_max_uid ();
3691 int *uid_luid
= XNEWVEC (int, max_uid
);
3692 rtx
*closest_uses
= XNEWVEC (rtx
, max_regs
);
3693 /* A set of registers which are live but not modified throughout a block. */
3694 bitmap_head
*bb_transp_live
= XNEWVEC (bitmap_head
, last_basic_block
);
3695 /* A set of registers which only exist in a given basic block. */
3696 bitmap_head
*bb_local
= XNEWVEC (bitmap_head
, last_basic_block
);
3697 /* A set of registers which are set once, in an instruction that can be
3698 moved freely downwards, but are otherwise transparent to a block. */
3699 bitmap_head
*bb_moveable_reg_sets
= XNEWVEC (bitmap_head
, last_basic_block
);
3700 bitmap_head live
, used
, set
, interesting
, unusable_as_input
;
3702 bitmap_initialize (&interesting
, 0);
3704 first_moveable_pseudo
= max_regs
;
3705 VEC_free (rtx
, heap
, pseudo_replaced_reg
);
3706 VEC_safe_grow (rtx
, heap
, pseudo_replaced_reg
, max_regs
);
3709 calculate_dominance_info (CDI_DOMINATORS
);
3712 bitmap_initialize (&live
, 0);
3713 bitmap_initialize (&used
, 0);
3714 bitmap_initialize (&set
, 0);
3715 bitmap_initialize (&unusable_as_input
, 0);
3719 bitmap transp
= bb_transp_live
+ bb
->index
;
3720 bitmap moveable
= bb_moveable_reg_sets
+ bb
->index
;
3721 bitmap local
= bb_local
+ bb
->index
;
3723 bitmap_initialize (local
, 0);
3724 bitmap_initialize (transp
, 0);
3725 bitmap_initialize (moveable
, 0);
3726 bitmap_copy (&live
, df_get_live_out (bb
));
3727 bitmap_and_into (&live
, df_get_live_in (bb
));
3728 bitmap_copy (transp
, &live
);
3729 bitmap_clear (moveable
);
3730 bitmap_clear (&live
);
3731 bitmap_clear (&used
);
3732 bitmap_clear (&set
);
3733 FOR_BB_INSNS (bb
, insn
)
3734 if (NONDEBUG_INSN_P (insn
))
3736 df_ref
*u_rec
, *d_rec
;
3738 uid_luid
[INSN_UID (insn
)] = i
++;
3740 u_rec
= DF_INSN_USES (insn
);
3741 d_rec
= DF_INSN_DEFS (insn
);
3742 if (d_rec
[0] != NULL
&& d_rec
[1] == NULL
3743 && u_rec
[0] != NULL
&& u_rec
[1] == NULL
3744 && DF_REF_REGNO (*u_rec
) == DF_REF_REGNO (*d_rec
)
3745 && !bitmap_bit_p (&set
, DF_REF_REGNO (*u_rec
))
3746 && rtx_moveable_p (&PATTERN (insn
), OP_IN
))
3748 unsigned regno
= DF_REF_REGNO (*u_rec
);
3749 bitmap_set_bit (moveable
, regno
);
3750 bitmap_set_bit (&set
, regno
);
3751 bitmap_set_bit (&used
, regno
);
3752 bitmap_clear_bit (transp
, regno
);
3757 unsigned regno
= DF_REF_REGNO (*u_rec
);
3758 bitmap_set_bit (&used
, regno
);
3759 if (bitmap_clear_bit (moveable
, regno
))
3760 bitmap_clear_bit (transp
, regno
);
3766 unsigned regno
= DF_REF_REGNO (*d_rec
);
3767 bitmap_set_bit (&set
, regno
);
3768 bitmap_clear_bit (transp
, regno
);
3769 bitmap_clear_bit (moveable
, regno
);
3775 bitmap_clear (&live
);
3776 bitmap_clear (&used
);
3777 bitmap_clear (&set
);
3781 bitmap local
= bb_local
+ bb
->index
;
3784 FOR_BB_INSNS (bb
, insn
)
3785 if (NONDEBUG_INSN_P (insn
))
3787 rtx def_insn
, closest_use
, note
;
3788 df_ref
*def_rec
, def
, use
;
3790 bool all_dominated
, all_local
;
3791 enum machine_mode mode
;
3793 def_rec
= DF_INSN_DEFS (insn
);
3794 /* There must be exactly one def in this insn. */
3796 if (!def
|| def_rec
[1] || !single_set (insn
))
3798 /* This must be the only definition of the reg. We also limit
3799 which modes we deal with so that we can assume we can generate
3800 move instructions. */
3801 regno
= DF_REF_REGNO (def
);
3802 mode
= GET_MODE (DF_REF_REG (def
));
3803 if (DF_REG_DEF_COUNT (regno
) != 1
3804 || !DF_REF_INSN_INFO (def
)
3805 || HARD_REGISTER_NUM_P (regno
)
3806 || DF_REG_EQ_USE_COUNT (regno
) > 0
3807 || (!INTEGRAL_MODE_P (mode
) && !FLOAT_MODE_P (mode
)))
3809 def_insn
= DF_REF_INSN (def
);
3811 for (note
= REG_NOTES (def_insn
); note
; note
= XEXP (note
, 1))
3812 if (REG_NOTE_KIND (note
) == REG_EQUIV
&& MEM_P (XEXP (note
, 0)))
3818 fprintf (dump_file
, "Ignoring reg %d, has equiv memory\n",
3820 bitmap_set_bit (&unusable_as_input
, regno
);
3824 use
= DF_REG_USE_CHAIN (regno
);
3825 all_dominated
= true;
3827 closest_use
= NULL_RTX
;
3828 for (; use
; use
= DF_REF_NEXT_REG (use
))
3831 if (!DF_REF_INSN_INFO (use
))
3833 all_dominated
= false;
3837 insn
= DF_REF_INSN (use
);
3838 if (DEBUG_INSN_P (insn
))
3840 if (BLOCK_FOR_INSN (insn
) != BLOCK_FOR_INSN (def_insn
))
3842 if (!insn_dominated_by_p (insn
, def_insn
, uid_luid
))
3843 all_dominated
= false;
3844 if (closest_use
!= insn
&& closest_use
!= const0_rtx
)
3846 if (closest_use
== NULL_RTX
)
3848 else if (insn_dominated_by_p (closest_use
, insn
, uid_luid
))
3850 else if (!insn_dominated_by_p (insn
, closest_use
, uid_luid
))
3851 closest_use
= const0_rtx
;
3857 fprintf (dump_file
, "Reg %d not all uses dominated by set\n",
3862 bitmap_set_bit (local
, regno
);
3863 if (closest_use
== const0_rtx
|| closest_use
== NULL
3864 || next_nonnote_nondebug_insn (def_insn
) == closest_use
)
3867 fprintf (dump_file
, "Reg %d uninteresting%s\n", regno
,
3868 closest_use
== const0_rtx
|| closest_use
== NULL
3869 ? " (no unique first use)" : "");
3873 if (reg_referenced_p (cc0_rtx
, PATTERN (closest_use
)))
3876 fprintf (dump_file
, "Reg %d: closest user uses cc0\n",
3881 bitmap_set_bit (&interesting
, regno
);
3882 closest_uses
[regno
] = closest_use
;
3884 if (dump_file
&& (all_local
|| all_dominated
))
3886 fprintf (dump_file
, "Reg %u:", regno
);
3888 fprintf (dump_file
, " local to bb %d", bb
->index
);
3890 fprintf (dump_file
, " def dominates all uses");
3891 if (closest_use
!= const0_rtx
)
3892 fprintf (dump_file
, " has unique first use");
3893 fputs ("\n", dump_file
);
3898 EXECUTE_IF_SET_IN_BITMAP (&interesting
, 0, i
, bi
)
3900 df_ref def
= DF_REG_DEF_CHAIN (i
);
3901 rtx def_insn
= DF_REF_INSN (def
);
3902 basic_block def_block
= BLOCK_FOR_INSN (def_insn
);
3903 bitmap def_bb_local
= bb_local
+ def_block
->index
;
3904 bitmap def_bb_moveable
= bb_moveable_reg_sets
+ def_block
->index
;
3905 bitmap def_bb_transp
= bb_transp_live
+ def_block
->index
;
3906 bool local_to_bb_p
= bitmap_bit_p (def_bb_local
, i
);
3907 rtx use_insn
= closest_uses
[i
];
3908 df_ref
*def_insn_use_rec
= DF_INSN_USES (def_insn
);
3910 bool all_transp
= true;
3912 if (!REG_P (DF_REF_REG (def
)))
3918 fprintf (dump_file
, "Reg %u not local to one basic block\n",
3922 if (reg_equiv_init (i
) != NULL_RTX
)
3925 fprintf (dump_file
, "Ignoring reg %u with equiv init insn\n",
3929 if (!rtx_moveable_p (&PATTERN (def_insn
), OP_IN
))
3932 fprintf (dump_file
, "Found def insn %d for %d to be not moveable\n",
3933 INSN_UID (def_insn
), i
);
3937 fprintf (dump_file
, "Examining insn %d, def for %d\n",
3938 INSN_UID (def_insn
), i
);
3939 while (*def_insn_use_rec
!= NULL
)
3941 df_ref use
= *def_insn_use_rec
;
3942 unsigned regno
= DF_REF_REGNO (use
);
3943 if (bitmap_bit_p (&unusable_as_input
, regno
))
3947 fprintf (dump_file
, " found unusable input reg %u.\n", regno
);
3950 if (!bitmap_bit_p (def_bb_transp
, regno
))
3952 if (bitmap_bit_p (def_bb_moveable
, regno
)
3953 && !control_flow_insn_p (use_insn
)
3955 && !sets_cc0_p (use_insn
)
3959 if (modified_between_p (DF_REF_REG (use
), def_insn
, use_insn
))
3961 rtx x
= NEXT_INSN (def_insn
);
3962 while (!modified_in_p (DF_REF_REG (use
), x
))
3964 gcc_assert (x
!= use_insn
);
3968 fprintf (dump_file
, " input reg %u modified but insn %d moveable\n",
3969 regno
, INSN_UID (x
));
3970 emit_insn_after (PATTERN (x
), use_insn
);
3971 set_insn_deleted (x
);
3976 fprintf (dump_file
, " input reg %u modified between def and use\n",
3989 if (!dbg_cnt (ira_move
))
3992 fprintf (dump_file
, " all ok%s\n", all_transp
? " and transp" : "");
3996 rtx def_reg
= DF_REF_REG (def
);
3997 rtx newreg
= ira_create_new_reg (def_reg
);
3998 if (validate_change (def_insn
, DF_REF_LOC (def
), newreg
, 0))
4000 unsigned nregno
= REGNO (newreg
);
4001 emit_insn_before (gen_move_insn (def_reg
, newreg
), use_insn
);
4003 VEC_replace (rtx
, pseudo_replaced_reg
, nregno
, def_reg
);
4010 bitmap_clear (bb_local
+ bb
->index
);
4011 bitmap_clear (bb_transp_live
+ bb
->index
);
4012 bitmap_clear (bb_moveable_reg_sets
+ bb
->index
);
4014 bitmap_clear (&interesting
);
4015 bitmap_clear (&unusable_as_input
);
4017 free (closest_uses
);
4019 free (bb_transp_live
);
4020 free (bb_moveable_reg_sets
);
4022 last_moveable_pseudo
= max_reg_num ();
4024 fix_reg_equiv_init ();
4026 regstat_free_n_sets_and_refs ();
4028 regstat_init_n_sets_and_refs ();
4029 regstat_compute_ri ();
4030 free_dominance_info (CDI_DOMINATORS
);
4033 /* Perform the second half of the transformation started in
4034 find_moveable_pseudos. We look for instances where the newly introduced
4035 pseudo remains unallocated, and remove it by moving the definition to
4036 just before its use, replacing the move instruction generated by
4037 find_moveable_pseudos. */
4039 move_unallocated_pseudos (void)
4042 for (i
= first_moveable_pseudo
; i
< last_moveable_pseudo
; i
++)
4043 if (reg_renumber
[i
] < 0)
4045 int idx
= i
- first_moveable_pseudo
;
4046 rtx other_reg
= VEC_index (rtx
, pseudo_replaced_reg
, idx
);
4047 rtx def_insn
= DF_REF_INSN (DF_REG_DEF_CHAIN (i
));
4048 /* The use must follow all definitions of OTHER_REG, so we can
4049 insert the new definition immediately after any of them. */
4050 df_ref other_def
= DF_REG_DEF_CHAIN (REGNO (other_reg
));
4051 rtx move_insn
= DF_REF_INSN (other_def
);
4052 rtx newinsn
= emit_insn_after (PATTERN (def_insn
), move_insn
);
4057 fprintf (dump_file
, "moving def of %d (insn %d now) ",
4058 REGNO (other_reg
), INSN_UID (def_insn
));
4060 delete_insn (move_insn
);
4061 while ((other_def
= DF_REG_DEF_CHAIN (REGNO (other_reg
))))
4062 delete_insn (DF_REF_INSN (other_def
));
4063 delete_insn (def_insn
);
4065 set
= single_set (newinsn
);
4066 success
= validate_change (newinsn
, &SET_DEST (set
), other_reg
, 0);
4067 gcc_assert (success
);
4069 fprintf (dump_file
, " %d) rather than keep unallocated replacement %d\n",
4070 INSN_UID (newinsn
), i
);
4071 SET_REG_N_REFS (i
, 0);
4075 /* If the backend knows where to allocate pseudos for hard
4076 register initial values, register these allocations now. */
4078 allocate_initial_values (void)
4080 if (targetm
.allocate_initial_value
)
4085 for (i
= 0; HARD_REGISTER_NUM_P (i
); i
++)
4087 if (! initial_value_entry (i
, &hreg
, &preg
))
4090 x
= targetm
.allocate_initial_value (hreg
);
4091 regno
= REGNO (preg
);
4092 if (x
&& REG_N_SETS (regno
) <= 1)
4095 reg_equiv_memory_loc (regno
) = x
;
4101 gcc_assert (REG_P (x
));
4102 new_regno
= REGNO (x
);
4103 reg_renumber
[regno
] = new_regno
;
4104 /* Poke the regno right into regno_reg_rtx so that even
4105 fixed regs are accepted. */
4106 SET_REGNO (preg
, new_regno
);
4107 /* Update global register liveness information. */
4110 if (REGNO_REG_SET_P(df_get_live_in (bb
), regno
))
4111 SET_REGNO_REG_SET (df_get_live_in (bb
), new_regno
);
4112 if (REGNO_REG_SET_P(df_get_live_out (bb
), regno
))
4113 SET_REGNO_REG_SET (df_get_live_out (bb
), new_regno
);
4119 gcc_checking_assert (! initial_value_entry (FIRST_PSEUDO_REGISTER
,
4124 /* All natural loops. */
4125 struct loops ira_loops
;
4127 /* True if we have allocno conflicts. It is false for non-optimized
4128 mode or when the conflict table is too big. */
4129 bool ira_conflicts_p
;
4131 /* Saved between IRA and reload. */
4132 static int saved_flag_ira_share_spill_slots
;
4134 /* This is the main entry of IRA. */
4139 int max_regno_before_ira
, ira_max_point_before_emit
;
4142 if (flag_caller_saves
)
4143 init_caller_save ();
4145 if (flag_ira_verbose
< 10)
4147 internal_flag_ira_verbose
= flag_ira_verbose
;
4152 internal_flag_ira_verbose
= flag_ira_verbose
- 10;
4153 ira_dump_file
= stderr
;
4156 ira_conflicts_p
= optimize
> 0;
4157 setup_prohibited_mode_move_regs ();
4159 df_note_add_problem ();
4163 df_live_add_problem ();
4164 df_live_set_all_dirty ();
4166 #ifdef ENABLE_CHECKING
4167 df
->changeable_flags
|= DF_VERIFY_SCHEDULED
;
4170 df_clear_flags (DF_NO_INSN_RESCAN
);
4171 regstat_init_n_sets_and_refs ();
4172 regstat_compute_ri ();
4174 /* If we are not optimizing, then this is the only place before
4175 register allocation where dataflow is done. And that is needed
4176 to generate these warnings. */
4178 generate_setjmp_warnings ();
4180 /* Determine if the current function is a leaf before running IRA
4181 since this can impact optimizations done by the prologue and
4182 epilogue thus changing register elimination offsets. */
4183 crtl
->is_leaf
= leaf_function_p ();
4185 if (resize_reg_info () && flag_ira_loop_pressure
)
4186 ira_set_pseudo_classes (ira_dump_file
);
4188 rebuild_p
= update_equiv_regs ();
4190 #ifndef IRA_NO_OBSTACK
4191 gcc_obstack_init (&ira_obstack
);
4193 bitmap_obstack_initialize (&ira_bitmap_obstack
);
4196 max_regno
= max_reg_num ();
4197 ira_reg_equiv_len
= max_regno
;
4198 ira_reg_equiv_invariant_p
4199 = (bool *) ira_allocate (max_regno
* sizeof (bool));
4200 memset (ira_reg_equiv_invariant_p
, 0, max_regno
* sizeof (bool));
4201 ira_reg_equiv_const
= (rtx
*) ira_allocate (max_regno
* sizeof (rtx
));
4202 memset (ira_reg_equiv_const
, 0, max_regno
* sizeof (rtx
));
4203 find_reg_equiv_invariant_const ();
4206 timevar_push (TV_JUMP
);
4207 rebuild_jump_labels (get_insns ());
4208 if (purge_all_dead_edges ())
4209 delete_unreachable_blocks ();
4210 timevar_pop (TV_JUMP
);
4214 allocated_reg_info_size
= max_reg_num ();
4216 if (delete_trivially_dead_insns (get_insns (), max_reg_num ()))
4219 /* It is not worth to do such improvement when we use a simple
4220 allocation because of -O0 usage or because the function is too
4222 if (ira_conflicts_p
)
4223 find_moveable_pseudos ();
4225 max_regno_before_ira
= max_reg_num ();
4226 ira_setup_eliminable_regset ();
4228 ira_overall_cost
= ira_reg_cost
= ira_mem_cost
= 0;
4229 ira_load_cost
= ira_store_cost
= ira_shuffle_cost
= 0;
4230 ira_move_loops_num
= ira_additional_jumps_num
= 0;
4232 ira_assert (current_loops
== NULL
);
4233 if (flag_ira_region
== IRA_REGION_ALL
|| flag_ira_region
== IRA_REGION_MIXED
)
4235 flow_loops_find (&ira_loops
);
4236 record_loop_exits ();
4237 current_loops
= &ira_loops
;
4240 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
4241 fprintf (ira_dump_file
, "Building IRA IR\n");
4242 loops_p
= ira_build ();
4244 ira_assert (ira_conflicts_p
|| !loops_p
);
4246 saved_flag_ira_share_spill_slots
= flag_ira_share_spill_slots
;
4247 if (too_high_register_pressure_p () || cfun
->calls_setjmp
)
4248 /* It is just wasting compiler's time to pack spilled pseudos into
4249 stack slots in this case -- prohibit it. We also do this if
4250 there is setjmp call because a variable not modified between
4251 setjmp and longjmp the compiler is required to preserve its
4252 value and sharing slots does not guarantee it. */
4253 flag_ira_share_spill_slots
= FALSE
;
4257 ira_max_point_before_emit
= ira_max_point
;
4259 ira_initiate_emit_data ();
4263 if (ira_conflicts_p
)
4265 max_regno
= max_reg_num ();
4268 ira_initiate_assign ();
4273 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
4274 fprintf (ira_dump_file
, "Flattening IR\n");
4275 ira_flattening (max_regno_before_ira
, ira_max_point_before_emit
);
4276 /* New insns were generated: add notes and recalculate live
4280 flow_loops_find (&ira_loops
);
4281 record_loop_exits ();
4282 current_loops
= &ira_loops
;
4284 setup_allocno_assignment_flags ();
4285 ira_initiate_assign ();
4286 ira_reassign_conflict_allocnos (max_regno
);
4290 ira_finish_emit_data ();
4292 setup_reg_renumber ();
4294 calculate_allocation_cost ();
4296 #ifdef ENABLE_IRA_CHECKING
4297 if (ira_conflicts_p
)
4298 check_allocation ();
4301 if (max_regno
!= max_regno_before_ira
)
4303 regstat_free_n_sets_and_refs ();
4305 regstat_init_n_sets_and_refs ();
4306 regstat_compute_ri ();
4309 overall_cost_before
= ira_overall_cost
;
4310 if (! ira_conflicts_p
)
4314 fix_reg_equiv_init ();
4316 #ifdef ENABLE_IRA_CHECKING
4317 print_redundant_copies ();
4320 ira_spilled_reg_stack_slots_num
= 0;
4321 ira_spilled_reg_stack_slots
4322 = ((struct ira_spilled_reg_stack_slot
*)
4323 ira_allocate (max_regno
4324 * sizeof (struct ira_spilled_reg_stack_slot
)));
4325 memset (ira_spilled_reg_stack_slots
, 0,
4326 max_regno
* sizeof (struct ira_spilled_reg_stack_slot
));
4328 allocate_initial_values ();
4330 /* See comment for find_moveable_pseudos call. */
4331 if (ira_conflicts_p
)
4332 move_unallocated_pseudos ();
4341 if (flag_ira_verbose
< 10)
4342 ira_dump_file
= dump_file
;
4344 df_set_flags (DF_NO_INSN_RESCAN
);
4345 build_insn_chain ();
4347 need_dce
= reload (get_insns (), ira_conflicts_p
);
4349 timevar_push (TV_IRA
);
4351 if (ira_conflicts_p
)
4353 ira_free (ira_spilled_reg_stack_slots
);
4355 ira_finish_assign ();
4357 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
4358 && overall_cost_before
!= ira_overall_cost
)
4359 fprintf (ira_dump_file
, "+++Overall after reload %d\n", ira_overall_cost
);
4362 flag_ira_share_spill_slots
= saved_flag_ira_share_spill_slots
;
4364 if (current_loops
!= NULL
)
4366 flow_loops_free (&ira_loops
);
4367 free_dominance_info (CDI_DOMINATORS
);
4370 bb
->loop_father
= NULL
;
4371 current_loops
= NULL
;
4374 regstat_free_n_sets_and_refs ();
4378 cleanup_cfg (CLEANUP_EXPENSIVE
);
4380 ira_free (ira_reg_equiv_invariant_p
);
4381 ira_free (ira_reg_equiv_const
);
4384 bitmap_obstack_release (&ira_bitmap_obstack
);
4385 #ifndef IRA_NO_OBSTACK
4386 obstack_free (&ira_obstack
, NULL
);
4389 /* The code after the reload has changed so much that at this point
4390 we might as well just rescan everything. Note that
4391 df_rescan_all_insns is not going to help here because it does not
4392 touch the artificial uses and defs. */
4393 df_finish_pass (true);
4395 df_live_add_problem ();
4396 df_scan_alloc (NULL
);
4402 if (need_dce
&& optimize
)
4405 timevar_pop (TV_IRA
);
4408 /* Run the integrated register allocator. */
4410 rest_of_handle_ira (void)
4416 struct rtl_opt_pass pass_ira
=
4422 rest_of_handle_ira
, /* execute */
4425 0, /* static_pass_number */
4427 0, /* properties_required */
4428 0, /* properties_provided */
4429 0, /* properties_destroyed */
4430 0, /* todo_flags_start */
4431 0, /* todo_flags_finish */
4436 rest_of_handle_reload (void)
4442 struct rtl_opt_pass pass_reload
=
4446 "reload", /* name */
4448 rest_of_handle_reload
, /* execute */
4451 0, /* static_pass_number */
4452 TV_RELOAD
, /* tv_id */
4453 0, /* properties_required */
4454 0, /* properties_provided */
4455 0, /* properties_destroyed */
4456 0, /* todo_flags_start */
4457 TODO_ggc_collect
/* todo_flags_finish */