1 /* Integrated Register Allocator (IRA) entry point.
2 Copyright (C) 2006-2014 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* The integrated register allocator (IRA) is a
22 regional register allocator performing graph coloring on a top-down
23 traversal of nested regions. Graph coloring in a region is based
24 on Chaitin-Briggs algorithm. It is called integrated because
25 register coalescing, register live range splitting, and choosing a
26 better hard register are done on-the-fly during coloring. Register
27 coalescing and choosing a cheaper hard register is done by hard
28 register preferencing during hard register assigning. The live
29 range splitting is a byproduct of the regional register allocation.
31 Major IRA notions are:
33 o *Region* is a part of CFG where graph coloring based on
34 Chaitin-Briggs algorithm is done. IRA can work on any set of
35 nested CFG regions forming a tree. Currently the regions are
36 the entire function for the root region and natural loops for
37 the other regions. Therefore data structure representing a
38 region is called loop_tree_node.
40 o *Allocno class* is a register class used for allocation of
41 given allocno. It means that only hard register of given
42 register class can be assigned to given allocno. In reality,
43 even smaller subset of (*profitable*) hard registers can be
44 assigned. In rare cases, the subset can be even smaller
45 because our modification of Chaitin-Briggs algorithm requires
46 that sets of hard registers can be assigned to allocnos forms a
47 forest, i.e. the sets can be ordered in a way where any
48 previous set is not intersected with given set or is a superset
51 o *Pressure class* is a register class belonging to a set of
52 register classes containing all of the hard-registers available
53 for register allocation. The set of all pressure classes for a
54 target is defined in the corresponding machine-description file
55 according some criteria. Register pressure is calculated only
56 for pressure classes and it affects some IRA decisions as
57 forming allocation regions.
59 o *Allocno* represents the live range of a pseudo-register in a
60 region. Besides the obvious attributes like the corresponding
61 pseudo-register number, allocno class, conflicting allocnos and
62 conflicting hard-registers, there are a few allocno attributes
63 which are important for understanding the allocation algorithm:
65 - *Live ranges*. This is a list of ranges of *program points*
66 where the allocno lives. Program points represent places
67 where a pseudo can be born or become dead (there are
68 approximately two times more program points than the insns)
69 and they are represented by integers starting with 0. The
70 live ranges are used to find conflicts between allocnos.
71 They also play very important role for the transformation of
72 the IRA internal representation of several regions into a one
73 region representation. The later is used during the reload
74 pass work because each allocno represents all of the
75 corresponding pseudo-registers.
77 - *Hard-register costs*. This is a vector of size equal to the
78 number of available hard-registers of the allocno class. The
79 cost of a callee-clobbered hard-register for an allocno is
80 increased by the cost of save/restore code around the calls
81 through the given allocno's life. If the allocno is a move
82 instruction operand and another operand is a hard-register of
83 the allocno class, the cost of the hard-register is decreased
86 When an allocno is assigned, the hard-register with minimal
87 full cost is used. Initially, a hard-register's full cost is
88 the corresponding value from the hard-register's cost vector.
89 If the allocno is connected by a *copy* (see below) to
90 another allocno which has just received a hard-register, the
91 cost of the hard-register is decreased. Before choosing a
92 hard-register for an allocno, the allocno's current costs of
93 the hard-registers are modified by the conflict hard-register
94 costs of all of the conflicting allocnos which are not
97 - *Conflict hard-register costs*. This is a vector of the same
98 size as the hard-register costs vector. To permit an
99 unassigned allocno to get a better hard-register, IRA uses
100 this vector to calculate the final full cost of the
101 available hard-registers. Conflict hard-register costs of an
102 unassigned allocno are also changed with a change of the
103 hard-register cost of the allocno when a copy involving the
104 allocno is processed as described above. This is done to
105 show other unassigned allocnos that a given allocno prefers
106 some hard-registers in order to remove the move instruction
107 corresponding to the copy.
109 o *Cap*. If a pseudo-register does not live in a region but
110 lives in a nested region, IRA creates a special allocno called
111 a cap in the outer region. A region cap is also created for a
114 o *Copy*. Allocnos can be connected by copies. Copies are used
115 to modify hard-register costs for allocnos during coloring.
116 Such modifications reflects a preference to use the same
117 hard-register for the allocnos connected by copies. Usually
118 copies are created for move insns (in this case it results in
119 register coalescing). But IRA also creates copies for operands
120 of an insn which should be assigned to the same hard-register
121 due to constraints in the machine description (it usually
122 results in removing a move generated in reload to satisfy
123 the constraints) and copies referring to the allocno which is
124 the output operand of an instruction and the allocno which is
125 an input operand dying in the instruction (creation of such
126 copies results in less register shuffling). IRA *does not*
127 create copies between the same register allocnos from different
128 regions because we use another technique for propagating
129 hard-register preference on the borders of regions.
131 Allocnos (including caps) for the upper region in the region tree
132 *accumulate* information important for coloring from allocnos with
133 the same pseudo-register from nested regions. This includes
134 hard-register and memory costs, conflicts with hard-registers,
135 allocno conflicts, allocno copies and more. *Thus, attributes for
136 allocnos in a region have the same values as if the region had no
137 subregions*. It means that attributes for allocnos in the
138 outermost region corresponding to the function have the same values
139 as though the allocation used only one region which is the entire
140 function. It also means that we can look at IRA work as if the
141 first IRA did allocation for all function then it improved the
142 allocation for loops then their subloops and so on.
144 IRA major passes are:
146 o Building IRA internal representation which consists of the
149 * First, IRA builds regions and creates allocnos (file
150 ira-build.c) and initializes most of their attributes.
152 * Then IRA finds an allocno class for each allocno and
153 calculates its initial (non-accumulated) cost of memory and
154 each hard-register of its allocno class (file ira-cost.c).
156 * IRA creates live ranges of each allocno, calculates register
157 pressure for each pressure class in each region, sets up
158 conflict hard registers for each allocno and info about calls
159 the allocno lives through (file ira-lives.c).
161 * IRA removes low register pressure loops from the regions
162 mostly to speed IRA up (file ira-build.c).
164 * IRA propagates accumulated allocno info from lower region
165 allocnos to corresponding upper region allocnos (file
168 * IRA creates all caps (file ira-build.c).
170 * Having live-ranges of allocnos and their classes, IRA creates
171 conflicting allocnos for each allocno. Conflicting allocnos
172 are stored as a bit vector or array of pointers to the
173 conflicting allocnos whatever is more profitable (file
174 ira-conflicts.c). At this point IRA creates allocno copies.
176 o Coloring. Now IRA has all necessary info to start graph coloring
177 process. It is done in each region on top-down traverse of the
178 region tree (file ira-color.c). There are following subpasses:
180 * Finding profitable hard registers of corresponding allocno
181 class for each allocno. For example, only callee-saved hard
182 registers are frequently profitable for allocnos living
183 through colors. If the profitable hard register set of
184 allocno does not form a tree based on subset relation, we use
185 some approximation to form the tree. This approximation is
186 used to figure out trivial colorability of allocnos. The
187 approximation is a pretty rare case.
189 * Putting allocnos onto the coloring stack. IRA uses Briggs
190 optimistic coloring which is a major improvement over
191 Chaitin's coloring. Therefore IRA does not spill allocnos at
192 this point. There is some freedom in the order of putting
193 allocnos on the stack which can affect the final result of
194 the allocation. IRA uses some heuristics to improve the
195 order. The major one is to form *threads* from colorable
196 allocnos and push them on the stack by threads. Thread is a
197 set of non-conflicting colorable allocnos connected by
198 copies. The thread contains allocnos from the colorable
199 bucket or colorable allocnos already pushed onto the coloring
200 stack. Pushing thread allocnos one after another onto the
201 stack increases chances of removing copies when the allocnos
202 get the same hard reg.
204 We also use a modification of Chaitin-Briggs algorithm which
205 works for intersected register classes of allocnos. To
206 figure out trivial colorability of allocnos, the mentioned
207 above tree of hard register sets is used. To get an idea how
208 the algorithm works in i386 example, let us consider an
209 allocno to which any general hard register can be assigned.
210 If the allocno conflicts with eight allocnos to which only
211 EAX register can be assigned, given allocno is still
212 trivially colorable because all conflicting allocnos might be
213 assigned only to EAX and all other general hard registers are
216 To get an idea of the used trivial colorability criterion, it
217 is also useful to read article "Graph-Coloring Register
218 Allocation for Irregular Architectures" by Michael D. Smith
219 and Glen Holloway. Major difference between the article
220 approach and approach used in IRA is that Smith's approach
221 takes register classes only from machine description and IRA
222 calculate register classes from intermediate code too
223 (e.g. an explicit usage of hard registers in RTL code for
224 parameter passing can result in creation of additional
225 register classes which contain or exclude the hard
226 registers). That makes IRA approach useful for improving
227 coloring even for architectures with regular register files
228 and in fact some benchmarking shows the improvement for
229 regular class architectures is even bigger than for irregular
230 ones. Another difference is that Smith's approach chooses
231 intersection of classes of all insn operands in which a given
232 pseudo occurs. IRA can use bigger classes if it is still
233 more profitable than memory usage.
235 * Popping the allocnos from the stack and assigning them hard
236 registers. If IRA can not assign a hard register to an
237 allocno and the allocno is coalesced, IRA undoes the
238 coalescing and puts the uncoalesced allocnos onto the stack in
239 the hope that some such allocnos will get a hard register
240 separately. If IRA fails to assign hard register or memory
241 is more profitable for it, IRA spills the allocno. IRA
242 assigns the allocno the hard-register with minimal full
243 allocation cost which reflects the cost of usage of the
244 hard-register for the allocno and cost of usage of the
245 hard-register for allocnos conflicting with given allocno.
247 * Chaitin-Briggs coloring assigns as many pseudos as possible
248 to hard registers. After coloring we try to improve
249 allocation with cost point of view. We improve the
250 allocation by spilling some allocnos and assigning the freed
251 hard registers to other allocnos if it decreases the overall
254 * After allocno assigning in the region, IRA modifies the hard
255 register and memory costs for the corresponding allocnos in
256 the subregions to reflect the cost of possible loads, stores,
257 or moves on the border of the region and its subregions.
258 When default regional allocation algorithm is used
259 (-fira-algorithm=mixed), IRA just propagates the assignment
260 for allocnos if the register pressure in the region for the
261 corresponding pressure class is less than number of available
262 hard registers for given pressure class.
264 o Spill/restore code moving. When IRA performs an allocation
265 by traversing regions in top-down order, it does not know what
266 happens below in the region tree. Therefore, sometimes IRA
267 misses opportunities to perform a better allocation. A simple
268 optimization tries to improve allocation in a region having
269 subregions and containing in another region. If the
270 corresponding allocnos in the subregion are spilled, it spills
271 the region allocno if it is profitable. The optimization
272 implements a simple iterative algorithm performing profitable
273 transformations while they are still possible. It is fast in
274 practice, so there is no real need for a better time complexity
277 o Code change. After coloring, two allocnos representing the
278 same pseudo-register outside and inside a region respectively
279 may be assigned to different locations (hard-registers or
280 memory). In this case IRA creates and uses a new
281 pseudo-register inside the region and adds code to move allocno
282 values on the region's borders. This is done during top-down
283 traversal of the regions (file ira-emit.c). In some
284 complicated cases IRA can create a new allocno to move allocno
285 values (e.g. when a swap of values stored in two hard-registers
286 is needed). At this stage, the new allocno is marked as
287 spilled. IRA still creates the pseudo-register and the moves
288 on the region borders even when both allocnos were assigned to
289 the same hard-register. If the reload pass spills a
290 pseudo-register for some reason, the effect will be smaller
291 because another allocno will still be in the hard-register. In
292 most cases, this is better then spilling both allocnos. If
293 reload does not change the allocation for the two
294 pseudo-registers, the trivial move will be removed by
295 post-reload optimizations. IRA does not generate moves for
296 allocnos assigned to the same hard register when the default
297 regional allocation algorithm is used and the register pressure
298 in the region for the corresponding pressure class is less than
299 number of available hard registers for given pressure class.
300 IRA also does some optimizations to remove redundant stores and
301 to reduce code duplication on the region borders.
303 o Flattening internal representation. After changing code, IRA
304 transforms its internal representation for several regions into
305 one region representation (file ira-build.c). This process is
306 called IR flattening. Such process is more complicated than IR
307 rebuilding would be, but is much faster.
309 o After IR flattening, IRA tries to assign hard registers to all
310 spilled allocnos. This is implemented by a simple and fast
311 priority coloring algorithm (see function
312 ira_reassign_conflict_allocnos::ira-color.c). Here new allocnos
313 created during the code change pass can be assigned to hard
316 o At the end IRA calls the reload pass. The reload pass
317 communicates with IRA through several functions in file
318 ira-color.c to improve its decisions in
320 * sharing stack slots for the spilled pseudos based on IRA info
321 about pseudo-register conflicts.
323 * reassigning hard-registers to all spilled pseudos at the end
324 of each reload iteration.
326 * choosing a better hard-register to spill based on IRA info
327 about pseudo-register live ranges and the register pressure
328 in places where the pseudo-register lives.
330 IRA uses a lot of data representing the target processors. These
331 data are initialized in file ira.c.
333 If function has no loops (or the loops are ignored when
334 -fira-algorithm=CB is used), we have classic Chaitin-Briggs
335 coloring (only instead of separate pass of coalescing, we use hard
336 register preferencing). In such case, IRA works much faster
337 because many things are not made (like IR flattening, the
338 spill/restore optimization, and the code change).
340 Literature is worth to read for better understanding the code:
342 o Preston Briggs, Keith D. Cooper, Linda Torczon. Improvements to
343 Graph Coloring Register Allocation.
345 o David Callahan, Brian Koblenz. Register allocation via
346 hierarchical graph coloring.
348 o Keith Cooper, Anshuman Dasgupta, Jason Eckhardt. Revisiting Graph
349 Coloring Register Allocation: A Study of the Chaitin-Briggs and
350 Callahan-Koblenz Algorithms.
352 o Guei-Yuan Lueh, Thomas Gross, and Ali-Reza Adl-Tabatabai. Global
353 Register Allocation Based on Graph Fusion.
355 o Michael D. Smith and Glenn Holloway. Graph-Coloring Register
356 Allocation for Irregular Architectures
358 o Vladimir Makarov. The Integrated Register Allocator for GCC.
360 o Vladimir Makarov. The top-down register allocator for irregular
361 register file architectures.
368 #include "coretypes.h"
378 #include "hard-reg-set.h"
379 #include "basic-block.h"
384 #include "tree-pass.h"
388 #include "diagnostic-core.h"
389 #include "function.h"
395 #include "rtl-iter.h"
396 #include "shrink-wrap.h"
398 struct target_ira default_target_ira
;
399 struct target_ira_int default_target_ira_int
;
400 #if SWITCHABLE_TARGET
401 struct target_ira
*this_target_ira
= &default_target_ira
;
402 struct target_ira_int
*this_target_ira_int
= &default_target_ira_int
;
405 /* A modified value of flag `-fira-verbose' used internally. */
406 int internal_flag_ira_verbose
;
408 /* Dump file of the allocator if it is not NULL. */
411 /* The number of elements in the following array. */
412 int ira_spilled_reg_stack_slots_num
;
414 /* The following array contains info about spilled pseudo-registers
415 stack slots used in current function so far. */
416 struct ira_spilled_reg_stack_slot
*ira_spilled_reg_stack_slots
;
418 /* Correspondingly overall cost of the allocation, overall cost before
419 reload, cost of the allocnos assigned to hard-registers, cost of
420 the allocnos assigned to memory, cost of loads, stores and register
421 move insns generated for pseudo-register live range splitting (see
423 int ira_overall_cost
, overall_cost_before
;
424 int ira_reg_cost
, ira_mem_cost
;
425 int ira_load_cost
, ira_store_cost
, ira_shuffle_cost
;
426 int ira_move_loops_num
, ira_additional_jumps_num
;
428 /* All registers that can be eliminated. */
430 HARD_REG_SET eliminable_regset
;
432 /* Value of max_reg_num () before IRA work start. This value helps
433 us to recognize a situation when new pseudos were created during
435 static int max_regno_before_ira
;
437 /* Temporary hard reg set used for a different calculation. */
438 static HARD_REG_SET temp_hard_regset
;
440 #define last_mode_for_init_move_cost \
441 (this_target_ira_int->x_last_mode_for_init_move_cost)
444 /* The function sets up the map IRA_REG_MODE_HARD_REGSET. */
446 setup_reg_mode_hard_regset (void)
448 int i
, m
, hard_regno
;
450 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
451 for (hard_regno
= 0; hard_regno
< FIRST_PSEUDO_REGISTER
; hard_regno
++)
453 CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset
[hard_regno
][m
]);
454 for (i
= hard_regno_nregs
[hard_regno
][m
] - 1; i
>= 0; i
--)
455 if (hard_regno
+ i
< FIRST_PSEUDO_REGISTER
)
456 SET_HARD_REG_BIT (ira_reg_mode_hard_regset
[hard_regno
][m
],
462 #define no_unit_alloc_regs \
463 (this_target_ira_int->x_no_unit_alloc_regs)
465 /* The function sets up the three arrays declared above. */
467 setup_class_hard_regs (void)
469 int cl
, i
, hard_regno
, n
;
470 HARD_REG_SET processed_hard_reg_set
;
472 ira_assert (SHRT_MAX
>= FIRST_PSEUDO_REGISTER
);
473 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
475 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
476 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
477 CLEAR_HARD_REG_SET (processed_hard_reg_set
);
478 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
480 ira_non_ordered_class_hard_regs
[cl
][i
] = -1;
481 ira_class_hard_reg_index
[cl
][i
] = -1;
483 for (n
= 0, i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
485 #ifdef REG_ALLOC_ORDER
486 hard_regno
= reg_alloc_order
[i
];
490 if (TEST_HARD_REG_BIT (processed_hard_reg_set
, hard_regno
))
492 SET_HARD_REG_BIT (processed_hard_reg_set
, hard_regno
);
493 if (! TEST_HARD_REG_BIT (temp_hard_regset
, hard_regno
))
494 ira_class_hard_reg_index
[cl
][hard_regno
] = -1;
497 ira_class_hard_reg_index
[cl
][hard_regno
] = n
;
498 ira_class_hard_regs
[cl
][n
++] = hard_regno
;
501 ira_class_hard_regs_num
[cl
] = n
;
502 for (n
= 0, i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
503 if (TEST_HARD_REG_BIT (temp_hard_regset
, i
))
504 ira_non_ordered_class_hard_regs
[cl
][n
++] = i
;
505 ira_assert (ira_class_hard_regs_num
[cl
] == n
);
509 /* Set up global variables defining info about hard registers for the
510 allocation. These depend on USE_HARD_FRAME_P whose TRUE value means
511 that we can use the hard frame pointer for the allocation. */
513 setup_alloc_regs (bool use_hard_frame_p
)
515 #ifdef ADJUST_REG_ALLOC_ORDER
516 ADJUST_REG_ALLOC_ORDER
;
518 COPY_HARD_REG_SET (no_unit_alloc_regs
, fixed_reg_set
);
519 if (! use_hard_frame_p
)
520 SET_HARD_REG_BIT (no_unit_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
521 setup_class_hard_regs ();
526 #define alloc_reg_class_subclasses \
527 (this_target_ira_int->x_alloc_reg_class_subclasses)
529 /* Initialize the table of subclasses of each reg class. */
531 setup_reg_subclasses (void)
534 HARD_REG_SET temp_hard_regset2
;
536 for (i
= 0; i
< N_REG_CLASSES
; i
++)
537 for (j
= 0; j
< N_REG_CLASSES
; j
++)
538 alloc_reg_class_subclasses
[i
][j
] = LIM_REG_CLASSES
;
540 for (i
= 0; i
< N_REG_CLASSES
; i
++)
542 if (i
== (int) NO_REGS
)
545 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[i
]);
546 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
547 if (hard_reg_set_empty_p (temp_hard_regset
))
549 for (j
= 0; j
< N_REG_CLASSES
; j
++)
554 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[j
]);
555 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
556 if (! hard_reg_set_subset_p (temp_hard_regset
,
559 p
= &alloc_reg_class_subclasses
[j
][0];
560 while (*p
!= LIM_REG_CLASSES
) p
++;
561 *p
= (enum reg_class
) i
;
568 /* Set up IRA_MEMORY_MOVE_COST and IRA_MAX_MEMORY_MOVE_COST. */
570 setup_class_subset_and_memory_move_costs (void)
572 int cl
, cl2
, mode
, cost
;
573 HARD_REG_SET temp_hard_regset2
;
575 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
576 ira_memory_move_cost
[mode
][NO_REGS
][0]
577 = ira_memory_move_cost
[mode
][NO_REGS
][1] = SHRT_MAX
;
578 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
580 if (cl
!= (int) NO_REGS
)
581 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
583 ira_max_memory_move_cost
[mode
][cl
][0]
584 = ira_memory_move_cost
[mode
][cl
][0]
585 = memory_move_cost ((enum machine_mode
) mode
,
586 (reg_class_t
) cl
, false);
587 ira_max_memory_move_cost
[mode
][cl
][1]
588 = ira_memory_move_cost
[mode
][cl
][1]
589 = memory_move_cost ((enum machine_mode
) mode
,
590 (reg_class_t
) cl
, true);
591 /* Costs for NO_REGS are used in cost calculation on the
592 1st pass when the preferred register classes are not
593 known yet. In this case we take the best scenario. */
594 if (ira_memory_move_cost
[mode
][NO_REGS
][0]
595 > ira_memory_move_cost
[mode
][cl
][0])
596 ira_max_memory_move_cost
[mode
][NO_REGS
][0]
597 = ira_memory_move_cost
[mode
][NO_REGS
][0]
598 = ira_memory_move_cost
[mode
][cl
][0];
599 if (ira_memory_move_cost
[mode
][NO_REGS
][1]
600 > ira_memory_move_cost
[mode
][cl
][1])
601 ira_max_memory_move_cost
[mode
][NO_REGS
][1]
602 = ira_memory_move_cost
[mode
][NO_REGS
][1]
603 = ira_memory_move_cost
[mode
][cl
][1];
606 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
607 for (cl2
= (int) N_REG_CLASSES
- 1; cl2
>= 0; cl2
--)
609 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
610 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
611 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl2
]);
612 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
613 ira_class_subset_p
[cl
][cl2
]
614 = hard_reg_set_subset_p (temp_hard_regset
, temp_hard_regset2
);
615 if (! hard_reg_set_empty_p (temp_hard_regset2
)
616 && hard_reg_set_subset_p (reg_class_contents
[cl2
],
617 reg_class_contents
[cl
]))
618 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
620 cost
= ira_memory_move_cost
[mode
][cl2
][0];
621 if (cost
> ira_max_memory_move_cost
[mode
][cl
][0])
622 ira_max_memory_move_cost
[mode
][cl
][0] = cost
;
623 cost
= ira_memory_move_cost
[mode
][cl2
][1];
624 if (cost
> ira_max_memory_move_cost
[mode
][cl
][1])
625 ira_max_memory_move_cost
[mode
][cl
][1] = cost
;
628 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
629 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
631 ira_memory_move_cost
[mode
][cl
][0]
632 = ira_max_memory_move_cost
[mode
][cl
][0];
633 ira_memory_move_cost
[mode
][cl
][1]
634 = ira_max_memory_move_cost
[mode
][cl
][1];
636 setup_reg_subclasses ();
641 /* Define the following macro if allocation through malloc if
643 #define IRA_NO_OBSTACK
645 #ifndef IRA_NO_OBSTACK
646 /* Obstack used for storing all dynamic data (except bitmaps) of the
648 static struct obstack ira_obstack
;
651 /* Obstack used for storing all bitmaps of the IRA. */
652 static struct bitmap_obstack ira_bitmap_obstack
;
654 /* Allocate memory of size LEN for IRA data. */
656 ira_allocate (size_t len
)
660 #ifndef IRA_NO_OBSTACK
661 res
= obstack_alloc (&ira_obstack
, len
);
668 /* Free memory ADDR allocated for IRA data. */
670 ira_free (void *addr ATTRIBUTE_UNUSED
)
672 #ifndef IRA_NO_OBSTACK
680 /* Allocate and returns bitmap for IRA. */
682 ira_allocate_bitmap (void)
684 return BITMAP_ALLOC (&ira_bitmap_obstack
);
687 /* Free bitmap B allocated for IRA. */
689 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED
)
696 /* Output information about allocation of all allocnos (except for
697 caps) into file F. */
699 ira_print_disposition (FILE *f
)
705 fprintf (f
, "Disposition:");
706 max_regno
= max_reg_num ();
707 for (n
= 0, i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
708 for (a
= ira_regno_allocno_map
[i
];
710 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
715 fprintf (f
, " %4d:r%-4d", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
716 if ((bb
= ALLOCNO_LOOP_TREE_NODE (a
)->bb
) != NULL
)
717 fprintf (f
, "b%-3d", bb
->index
);
719 fprintf (f
, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a
)->loop_num
);
720 if (ALLOCNO_HARD_REGNO (a
) >= 0)
721 fprintf (f
, " %3d", ALLOCNO_HARD_REGNO (a
));
728 /* Outputs information about allocation of all allocnos into
731 ira_debug_disposition (void)
733 ira_print_disposition (stderr
);
738 /* Set up ira_stack_reg_pressure_class which is the biggest pressure
739 register class containing stack registers or NO_REGS if there are
740 no stack registers. To find this class, we iterate through all
741 register pressure classes and choose the first register pressure
742 class containing all the stack registers and having the biggest
745 setup_stack_reg_pressure_class (void)
747 ira_stack_reg_pressure_class
= NO_REGS
;
752 HARD_REG_SET temp_hard_regset2
;
754 CLEAR_HARD_REG_SET (temp_hard_regset
);
755 for (i
= FIRST_STACK_REG
; i
<= LAST_STACK_REG
; i
++)
756 SET_HARD_REG_BIT (temp_hard_regset
, i
);
758 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
760 cl
= ira_pressure_classes
[i
];
761 COPY_HARD_REG_SET (temp_hard_regset2
, temp_hard_regset
);
762 AND_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl
]);
763 size
= hard_reg_set_size (temp_hard_regset2
);
767 ira_stack_reg_pressure_class
= cl
;
774 /* Find pressure classes which are register classes for which we
775 calculate register pressure in IRA, register pressure sensitive
776 insn scheduling, and register pressure sensitive loop invariant
779 To make register pressure calculation easy, we always use
780 non-intersected register pressure classes. A move of hard
781 registers from one register pressure class is not more expensive
782 than load and store of the hard registers. Most likely an allocno
783 class will be a subset of a register pressure class and in many
784 cases a register pressure class. That makes usage of register
785 pressure classes a good approximation to find a high register
788 setup_pressure_classes (void)
790 int cost
, i
, n
, curr
;
792 enum reg_class pressure_classes
[N_REG_CLASSES
];
794 HARD_REG_SET temp_hard_regset2
;
798 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
800 if (ira_class_hard_regs_num
[cl
] == 0)
802 if (ira_class_hard_regs_num
[cl
] != 1
803 /* A register class without subclasses may contain a few
804 hard registers and movement between them is costly
805 (e.g. SPARC FPCC registers). We still should consider it
806 as a candidate for a pressure class. */
807 && alloc_reg_class_subclasses
[cl
][0] < cl
)
809 /* Check that the moves between any hard registers of the
810 current class are not more expensive for a legal mode
811 than load/store of the hard registers of the current
812 class. Such class is a potential candidate to be a
813 register pressure class. */
814 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
816 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
817 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
818 AND_COMPL_HARD_REG_SET (temp_hard_regset
,
819 ira_prohibited_class_mode_regs
[cl
][m
]);
820 if (hard_reg_set_empty_p (temp_hard_regset
))
822 ira_init_register_move_cost_if_necessary ((enum machine_mode
) m
);
823 cost
= ira_register_move_cost
[m
][cl
][cl
];
824 if (cost
<= ira_max_memory_move_cost
[m
][cl
][1]
825 || cost
<= ira_max_memory_move_cost
[m
][cl
][0])
828 if (m
>= NUM_MACHINE_MODES
)
833 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
834 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
835 /* Remove so far added pressure classes which are subset of the
836 current candidate class. Prefer GENERAL_REGS as a pressure
837 register class to another class containing the same
838 allocatable hard registers. We do this because machine
839 dependent cost hooks might give wrong costs for the latter
840 class but always give the right cost for the former class
842 for (i
= 0; i
< n
; i
++)
844 cl2
= pressure_classes
[i
];
845 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl2
]);
846 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
847 if (hard_reg_set_subset_p (temp_hard_regset
, temp_hard_regset2
)
848 && (! hard_reg_set_equal_p (temp_hard_regset
, temp_hard_regset2
)
849 || cl2
== (int) GENERAL_REGS
))
851 pressure_classes
[curr
++] = (enum reg_class
) cl2
;
855 if (hard_reg_set_subset_p (temp_hard_regset2
, temp_hard_regset
)
856 && (! hard_reg_set_equal_p (temp_hard_regset2
, temp_hard_regset
)
857 || cl
== (int) GENERAL_REGS
))
859 if (hard_reg_set_equal_p (temp_hard_regset2
, temp_hard_regset
))
861 pressure_classes
[curr
++] = (enum reg_class
) cl2
;
863 /* If the current candidate is a subset of a so far added
864 pressure class, don't add it to the list of the pressure
867 pressure_classes
[curr
++] = (enum reg_class
) cl
;
870 #ifdef ENABLE_IRA_CHECKING
872 HARD_REG_SET ignore_hard_regs
;
874 /* Check pressure classes correctness: here we check that hard
875 registers from all register pressure classes contains all hard
876 registers available for the allocation. */
877 CLEAR_HARD_REG_SET (temp_hard_regset
);
878 CLEAR_HARD_REG_SET (temp_hard_regset2
);
879 COPY_HARD_REG_SET (ignore_hard_regs
, no_unit_alloc_regs
);
880 for (cl
= 0; cl
< LIM_REG_CLASSES
; cl
++)
882 /* For some targets (like MIPS with MD_REGS), there are some
883 classes with hard registers available for allocation but
884 not able to hold value of any mode. */
885 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
886 if (contains_reg_of_mode
[cl
][m
])
888 if (m
>= NUM_MACHINE_MODES
)
890 IOR_HARD_REG_SET (ignore_hard_regs
, reg_class_contents
[cl
]);
893 for (i
= 0; i
< n
; i
++)
894 if ((int) pressure_classes
[i
] == cl
)
896 IOR_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl
]);
898 IOR_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
900 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
901 /* Some targets (like SPARC with ICC reg) have allocatable regs
902 for which no reg class is defined. */
903 if (REGNO_REG_CLASS (i
) == NO_REGS
)
904 SET_HARD_REG_BIT (ignore_hard_regs
, i
);
905 AND_COMPL_HARD_REG_SET (temp_hard_regset
, ignore_hard_regs
);
906 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, ignore_hard_regs
);
907 ira_assert (hard_reg_set_subset_p (temp_hard_regset2
, temp_hard_regset
));
910 ira_pressure_classes_num
= 0;
911 for (i
= 0; i
< n
; i
++)
913 cl
= (int) pressure_classes
[i
];
914 ira_reg_pressure_class_p
[cl
] = true;
915 ira_pressure_classes
[ira_pressure_classes_num
++] = (enum reg_class
) cl
;
917 setup_stack_reg_pressure_class ();
920 /* Set up IRA_UNIFORM_CLASS_P. Uniform class is a register class
921 whose register move cost between any registers of the class is the
922 same as for all its subclasses. We use the data to speed up the
923 2nd pass of calculations of allocno costs. */
925 setup_uniform_class_p (void)
929 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
931 ira_uniform_class_p
[cl
] = false;
932 if (ira_class_hard_regs_num
[cl
] == 0)
934 /* We can not use alloc_reg_class_subclasses here because move
935 cost hooks does not take into account that some registers are
936 unavailable for the subtarget. E.g. for i686, INT_SSE_REGS
937 is element of alloc_reg_class_subclasses for GENERAL_REGS
938 because SSE regs are unavailable. */
939 for (i
= 0; (cl2
= reg_class_subclasses
[cl
][i
]) != LIM_REG_CLASSES
; i
++)
941 if (ira_class_hard_regs_num
[cl2
] == 0)
943 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
944 if (contains_reg_of_mode
[cl
][m
] && contains_reg_of_mode
[cl2
][m
])
946 ira_init_register_move_cost_if_necessary ((enum machine_mode
) m
);
947 if (ira_register_move_cost
[m
][cl
][cl
]
948 != ira_register_move_cost
[m
][cl2
][cl2
])
951 if (m
< NUM_MACHINE_MODES
)
954 if (cl2
== LIM_REG_CLASSES
)
955 ira_uniform_class_p
[cl
] = true;
959 /* Set up IRA_ALLOCNO_CLASSES, IRA_ALLOCNO_CLASSES_NUM,
960 IRA_IMPORTANT_CLASSES, and IRA_IMPORTANT_CLASSES_NUM.
962 Target may have many subtargets and not all target hard registers can
963 be used for allocation, e.g. x86 port in 32-bit mode can not use
964 hard registers introduced in x86-64 like r8-r15). Some classes
965 might have the same allocatable hard registers, e.g. INDEX_REGS
966 and GENERAL_REGS in x86 port in 32-bit mode. To decrease different
967 calculations efforts we introduce allocno classes which contain
968 unique non-empty sets of allocatable hard-registers.
970 Pseudo class cost calculation in ira-costs.c is very expensive.
971 Therefore we are trying to decrease number of classes involved in
972 such calculation. Register classes used in the cost calculation
973 are called important classes. They are allocno classes and other
974 non-empty classes whose allocatable hard register sets are inside
975 of an allocno class hard register set. From the first sight, it
976 looks like that they are just allocno classes. It is not true. In
977 example of x86-port in 32-bit mode, allocno classes will contain
978 GENERAL_REGS but not LEGACY_REGS (because allocatable hard
979 registers are the same for the both classes). The important
980 classes will contain GENERAL_REGS and LEGACY_REGS. It is done
981 because a machine description insn constraint may refers for
982 LEGACY_REGS and code in ira-costs.c is mostly base on investigation
983 of the insn constraints. */
985 setup_allocno_and_important_classes (void)
989 HARD_REG_SET temp_hard_regset2
;
990 static enum reg_class classes
[LIM_REG_CLASSES
+ 1];
993 /* Collect classes which contain unique sets of allocatable hard
994 registers. Prefer GENERAL_REGS to other classes containing the
995 same set of hard registers. */
996 for (i
= 0; i
< LIM_REG_CLASSES
; i
++)
998 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[i
]);
999 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1000 for (j
= 0; j
< n
; j
++)
1003 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl
]);
1004 AND_COMPL_HARD_REG_SET (temp_hard_regset2
,
1005 no_unit_alloc_regs
);
1006 if (hard_reg_set_equal_p (temp_hard_regset
,
1011 classes
[n
++] = (enum reg_class
) i
;
1012 else if (i
== GENERAL_REGS
)
1013 /* Prefer general regs. For i386 example, it means that
1014 we prefer GENERAL_REGS over INDEX_REGS or LEGACY_REGS
1015 (all of them consists of the same available hard
1017 classes
[j
] = (enum reg_class
) i
;
1019 classes
[n
] = LIM_REG_CLASSES
;
1021 /* Set up classes which can be used for allocnos as classes
1022 containing non-empty unique sets of allocatable hard
1024 ira_allocno_classes_num
= 0;
1025 for (i
= 0; (cl
= classes
[i
]) != LIM_REG_CLASSES
; i
++)
1026 if (ira_class_hard_regs_num
[cl
] > 0)
1027 ira_allocno_classes
[ira_allocno_classes_num
++] = (enum reg_class
) cl
;
1028 ira_important_classes_num
= 0;
1029 /* Add non-allocno classes containing to non-empty set of
1030 allocatable hard regs. */
1031 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1032 if (ira_class_hard_regs_num
[cl
] > 0)
1034 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
1035 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1037 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1039 COPY_HARD_REG_SET (temp_hard_regset2
,
1040 reg_class_contents
[ira_allocno_classes
[j
]]);
1041 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
1042 if ((enum reg_class
) cl
== ira_allocno_classes
[j
])
1044 else if (hard_reg_set_subset_p (temp_hard_regset
,
1048 if (set_p
&& j
>= ira_allocno_classes_num
)
1049 ira_important_classes
[ira_important_classes_num
++]
1050 = (enum reg_class
) cl
;
1052 /* Now add allocno classes to the important classes. */
1053 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1054 ira_important_classes
[ira_important_classes_num
++]
1055 = ira_allocno_classes
[j
];
1056 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1058 ira_reg_allocno_class_p
[cl
] = false;
1059 ira_reg_pressure_class_p
[cl
] = false;
1061 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1062 ira_reg_allocno_class_p
[ira_allocno_classes
[j
]] = true;
1063 setup_pressure_classes ();
1064 setup_uniform_class_p ();
1067 /* Setup translation in CLASS_TRANSLATE of all classes into a class
1068 given by array CLASSES of length CLASSES_NUM. The function is used
1069 make translation any reg class to an allocno class or to an
1070 pressure class. This translation is necessary for some
1071 calculations when we can use only allocno or pressure classes and
1072 such translation represents an approximate representation of all
1075 The translation in case when allocatable hard register set of a
1076 given class is subset of allocatable hard register set of a class
1077 in CLASSES is pretty simple. We use smallest classes from CLASSES
1078 containing a given class. If allocatable hard register set of a
1079 given class is not a subset of any corresponding set of a class
1080 from CLASSES, we use the cheapest (with load/store point of view)
1081 class from CLASSES whose set intersects with given class set. */
1083 setup_class_translate_array (enum reg_class
*class_translate
,
1084 int classes_num
, enum reg_class
*classes
)
1087 enum reg_class aclass
, best_class
, *cl_ptr
;
1088 int i
, cost
, min_cost
, best_cost
;
1090 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1091 class_translate
[cl
] = NO_REGS
;
1093 for (i
= 0; i
< classes_num
; i
++)
1095 aclass
= classes
[i
];
1096 for (cl_ptr
= &alloc_reg_class_subclasses
[aclass
][0];
1097 (cl
= *cl_ptr
) != LIM_REG_CLASSES
;
1099 if (class_translate
[cl
] == NO_REGS
)
1100 class_translate
[cl
] = aclass
;
1101 class_translate
[aclass
] = aclass
;
1103 /* For classes which are not fully covered by one of given classes
1104 (in other words covered by more one given class), use the
1106 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1108 if (cl
== NO_REGS
|| class_translate
[cl
] != NO_REGS
)
1110 best_class
= NO_REGS
;
1111 best_cost
= INT_MAX
;
1112 for (i
= 0; i
< classes_num
; i
++)
1114 aclass
= classes
[i
];
1115 COPY_HARD_REG_SET (temp_hard_regset
,
1116 reg_class_contents
[aclass
]);
1117 AND_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
1118 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1119 if (! hard_reg_set_empty_p (temp_hard_regset
))
1122 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
1124 cost
= (ira_memory_move_cost
[mode
][aclass
][0]
1125 + ira_memory_move_cost
[mode
][aclass
][1]);
1126 if (min_cost
> cost
)
1129 if (best_class
== NO_REGS
|| best_cost
> min_cost
)
1131 best_class
= aclass
;
1132 best_cost
= min_cost
;
1136 class_translate
[cl
] = best_class
;
1140 /* Set up array IRA_ALLOCNO_CLASS_TRANSLATE and
1141 IRA_PRESSURE_CLASS_TRANSLATE. */
1143 setup_class_translate (void)
1145 setup_class_translate_array (ira_allocno_class_translate
,
1146 ira_allocno_classes_num
, ira_allocno_classes
);
1147 setup_class_translate_array (ira_pressure_class_translate
,
1148 ira_pressure_classes_num
, ira_pressure_classes
);
1151 /* Order numbers of allocno classes in original target allocno class
1152 array, -1 for non-allocno classes. */
1153 static int allocno_class_order
[N_REG_CLASSES
];
1155 /* The function used to sort the important classes. */
1157 comp_reg_classes_func (const void *v1p
, const void *v2p
)
1159 enum reg_class cl1
= *(const enum reg_class
*) v1p
;
1160 enum reg_class cl2
= *(const enum reg_class
*) v2p
;
1161 enum reg_class tcl1
, tcl2
;
1164 tcl1
= ira_allocno_class_translate
[cl1
];
1165 tcl2
= ira_allocno_class_translate
[cl2
];
1166 if (tcl1
!= NO_REGS
&& tcl2
!= NO_REGS
1167 && (diff
= allocno_class_order
[tcl1
] - allocno_class_order
[tcl2
]) != 0)
1169 return (int) cl1
- (int) cl2
;
1172 /* For correct work of function setup_reg_class_relation we need to
1173 reorder important classes according to the order of their allocno
1174 classes. It places important classes containing the same
1175 allocatable hard register set adjacent to each other and allocno
1176 class with the allocatable hard register set right after the other
1177 important classes with the same set.
1179 In example from comments of function
1180 setup_allocno_and_important_classes, it places LEGACY_REGS and
1181 GENERAL_REGS close to each other and GENERAL_REGS is after
1184 reorder_important_classes (void)
1188 for (i
= 0; i
< N_REG_CLASSES
; i
++)
1189 allocno_class_order
[i
] = -1;
1190 for (i
= 0; i
< ira_allocno_classes_num
; i
++)
1191 allocno_class_order
[ira_allocno_classes
[i
]] = i
;
1192 qsort (ira_important_classes
, ira_important_classes_num
,
1193 sizeof (enum reg_class
), comp_reg_classes_func
);
1194 for (i
= 0; i
< ira_important_classes_num
; i
++)
1195 ira_important_class_nums
[ira_important_classes
[i
]] = i
;
1198 /* Set up IRA_REG_CLASS_SUBUNION, IRA_REG_CLASS_SUPERUNION,
1199 IRA_REG_CLASS_SUPER_CLASSES, IRA_REG_CLASSES_INTERSECT, and
1200 IRA_REG_CLASSES_INTERSECT_P. For the meaning of the relations,
1201 please see corresponding comments in ira-int.h. */
1203 setup_reg_class_relations (void)
1205 int i
, cl1
, cl2
, cl3
;
1206 HARD_REG_SET intersection_set
, union_set
, temp_set2
;
1207 bool important_class_p
[N_REG_CLASSES
];
1209 memset (important_class_p
, 0, sizeof (important_class_p
));
1210 for (i
= 0; i
< ira_important_classes_num
; i
++)
1211 important_class_p
[ira_important_classes
[i
]] = true;
1212 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1214 ira_reg_class_super_classes
[cl1
][0] = LIM_REG_CLASSES
;
1215 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1217 ira_reg_classes_intersect_p
[cl1
][cl2
] = false;
1218 ira_reg_class_intersect
[cl1
][cl2
] = NO_REGS
;
1219 ira_reg_class_subset
[cl1
][cl2
] = NO_REGS
;
1220 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl1
]);
1221 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1222 COPY_HARD_REG_SET (temp_set2
, reg_class_contents
[cl2
]);
1223 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1224 if (hard_reg_set_empty_p (temp_hard_regset
)
1225 && hard_reg_set_empty_p (temp_set2
))
1227 /* The both classes have no allocatable hard registers
1228 -- take all class hard registers into account and use
1229 reg_class_subunion and reg_class_superunion. */
1232 cl3
= reg_class_subclasses
[cl1
][i
];
1233 if (cl3
== LIM_REG_CLASSES
)
1235 if (reg_class_subset_p (ira_reg_class_intersect
[cl1
][cl2
],
1236 (enum reg_class
) cl3
))
1237 ira_reg_class_intersect
[cl1
][cl2
] = (enum reg_class
) cl3
;
1239 ira_reg_class_subunion
[cl1
][cl2
] = reg_class_subunion
[cl1
][cl2
];
1240 ira_reg_class_superunion
[cl1
][cl2
] = reg_class_superunion
[cl1
][cl2
];
1243 ira_reg_classes_intersect_p
[cl1
][cl2
]
1244 = hard_reg_set_intersect_p (temp_hard_regset
, temp_set2
);
1245 if (important_class_p
[cl1
] && important_class_p
[cl2
]
1246 && hard_reg_set_subset_p (temp_hard_regset
, temp_set2
))
1248 /* CL1 and CL2 are important classes and CL1 allocatable
1249 hard register set is inside of CL2 allocatable hard
1250 registers -- make CL1 a superset of CL2. */
1253 p
= &ira_reg_class_super_classes
[cl1
][0];
1254 while (*p
!= LIM_REG_CLASSES
)
1256 *p
++ = (enum reg_class
) cl2
;
1257 *p
= LIM_REG_CLASSES
;
1259 ira_reg_class_subunion
[cl1
][cl2
] = NO_REGS
;
1260 ira_reg_class_superunion
[cl1
][cl2
] = NO_REGS
;
1261 COPY_HARD_REG_SET (intersection_set
, reg_class_contents
[cl1
]);
1262 AND_HARD_REG_SET (intersection_set
, reg_class_contents
[cl2
]);
1263 AND_COMPL_HARD_REG_SET (intersection_set
, no_unit_alloc_regs
);
1264 COPY_HARD_REG_SET (union_set
, reg_class_contents
[cl1
]);
1265 IOR_HARD_REG_SET (union_set
, reg_class_contents
[cl2
]);
1266 AND_COMPL_HARD_REG_SET (union_set
, no_unit_alloc_regs
);
1267 for (cl3
= 0; cl3
< N_REG_CLASSES
; cl3
++)
1269 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl3
]);
1270 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1271 if (hard_reg_set_subset_p (temp_hard_regset
, intersection_set
))
1273 /* CL3 allocatable hard register set is inside of
1274 intersection of allocatable hard register sets
1276 if (important_class_p
[cl3
])
1281 [(int) ira_reg_class_intersect
[cl1
][cl2
]]);
1282 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1283 if (! hard_reg_set_subset_p (temp_hard_regset
, temp_set2
)
1284 /* If the allocatable hard register sets are
1285 the same, prefer GENERAL_REGS or the
1286 smallest class for debugging
1288 || (hard_reg_set_equal_p (temp_hard_regset
, temp_set2
)
1289 && (cl3
== GENERAL_REGS
1290 || ((ira_reg_class_intersect
[cl1
][cl2
]
1292 && hard_reg_set_subset_p
1293 (reg_class_contents
[cl3
],
1296 ira_reg_class_intersect
[cl1
][cl2
]])))))
1297 ira_reg_class_intersect
[cl1
][cl2
] = (enum reg_class
) cl3
;
1301 reg_class_contents
[(int) ira_reg_class_subset
[cl1
][cl2
]]);
1302 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1303 if (! hard_reg_set_subset_p (temp_hard_regset
, temp_set2
)
1304 /* Ignore unavailable hard registers and prefer
1305 smallest class for debugging purposes. */
1306 || (hard_reg_set_equal_p (temp_hard_regset
, temp_set2
)
1307 && hard_reg_set_subset_p
1308 (reg_class_contents
[cl3
],
1310 [(int) ira_reg_class_subset
[cl1
][cl2
]])))
1311 ira_reg_class_subset
[cl1
][cl2
] = (enum reg_class
) cl3
;
1313 if (important_class_p
[cl3
]
1314 && hard_reg_set_subset_p (temp_hard_regset
, union_set
))
1316 /* CL3 allocatable hard register set is inside of
1317 union of allocatable hard register sets of CL1
1321 reg_class_contents
[(int) ira_reg_class_subunion
[cl1
][cl2
]]);
1322 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1323 if (ira_reg_class_subunion
[cl1
][cl2
] == NO_REGS
1324 || (hard_reg_set_subset_p (temp_set2
, temp_hard_regset
)
1326 && (! hard_reg_set_equal_p (temp_set2
,
1328 || cl3
== GENERAL_REGS
1329 /* If the allocatable hard register sets are the
1330 same, prefer GENERAL_REGS or the smallest
1331 class for debugging purposes. */
1332 || (ira_reg_class_subunion
[cl1
][cl2
] != GENERAL_REGS
1333 && hard_reg_set_subset_p
1334 (reg_class_contents
[cl3
],
1336 [(int) ira_reg_class_subunion
[cl1
][cl2
]])))))
1337 ira_reg_class_subunion
[cl1
][cl2
] = (enum reg_class
) cl3
;
1339 if (hard_reg_set_subset_p (union_set
, temp_hard_regset
))
1341 /* CL3 allocatable hard register set contains union
1342 of allocatable hard register sets of CL1 and
1346 reg_class_contents
[(int) ira_reg_class_superunion
[cl1
][cl2
]]);
1347 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1348 if (ira_reg_class_superunion
[cl1
][cl2
] == NO_REGS
1349 || (hard_reg_set_subset_p (temp_hard_regset
, temp_set2
)
1351 && (! hard_reg_set_equal_p (temp_set2
,
1353 || cl3
== GENERAL_REGS
1354 /* If the allocatable hard register sets are the
1355 same, prefer GENERAL_REGS or the smallest
1356 class for debugging purposes. */
1357 || (ira_reg_class_superunion
[cl1
][cl2
] != GENERAL_REGS
1358 && hard_reg_set_subset_p
1359 (reg_class_contents
[cl3
],
1361 [(int) ira_reg_class_superunion
[cl1
][cl2
]])))))
1362 ira_reg_class_superunion
[cl1
][cl2
] = (enum reg_class
) cl3
;
1369 /* Output all uniform and important classes into file F. */
1371 print_unform_and_important_classes (FILE *f
)
1373 static const char *const reg_class_names
[] = REG_CLASS_NAMES
;
1376 fprintf (f
, "Uniform classes:\n");
1377 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1378 if (ira_uniform_class_p
[cl
])
1379 fprintf (f
, " %s", reg_class_names
[cl
]);
1380 fprintf (f
, "\nImportant classes:\n");
1381 for (i
= 0; i
< ira_important_classes_num
; i
++)
1382 fprintf (f
, " %s", reg_class_names
[ira_important_classes
[i
]]);
1386 /* Output all possible allocno or pressure classes and their
1387 translation map into file F. */
1389 print_translated_classes (FILE *f
, bool pressure_p
)
1391 int classes_num
= (pressure_p
1392 ? ira_pressure_classes_num
: ira_allocno_classes_num
);
1393 enum reg_class
*classes
= (pressure_p
1394 ? ira_pressure_classes
: ira_allocno_classes
);
1395 enum reg_class
*class_translate
= (pressure_p
1396 ? ira_pressure_class_translate
1397 : ira_allocno_class_translate
);
1398 static const char *const reg_class_names
[] = REG_CLASS_NAMES
;
1401 fprintf (f
, "%s classes:\n", pressure_p
? "Pressure" : "Allocno");
1402 for (i
= 0; i
< classes_num
; i
++)
1403 fprintf (f
, " %s", reg_class_names
[classes
[i
]]);
1404 fprintf (f
, "\nClass translation:\n");
1405 for (i
= 0; i
< N_REG_CLASSES
; i
++)
1406 fprintf (f
, " %s -> %s\n", reg_class_names
[i
],
1407 reg_class_names
[class_translate
[i
]]);
1410 /* Output all possible allocno and translation classes and the
1411 translation maps into stderr. */
1413 ira_debug_allocno_classes (void)
1415 print_unform_and_important_classes (stderr
);
1416 print_translated_classes (stderr
, false);
1417 print_translated_classes (stderr
, true);
1420 /* Set up different arrays concerning class subsets, allocno and
1421 important classes. */
1423 find_reg_classes (void)
1425 setup_allocno_and_important_classes ();
1426 setup_class_translate ();
1427 reorder_important_classes ();
1428 setup_reg_class_relations ();
1433 /* Set up the array above. */
1435 setup_hard_regno_aclass (void)
1439 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1442 ira_hard_regno_allocno_class
[i
]
1443 = (TEST_HARD_REG_BIT (no_unit_alloc_regs
, i
)
1445 : ira_allocno_class_translate
[REGNO_REG_CLASS (i
)]);
1449 ira_hard_regno_allocno_class
[i
] = NO_REGS
;
1450 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1452 cl
= ira_allocno_classes
[j
];
1453 if (ira_class_hard_reg_index
[cl
][i
] >= 0)
1455 ira_hard_regno_allocno_class
[i
] = cl
;
1465 /* Form IRA_REG_CLASS_MAX_NREGS and IRA_REG_CLASS_MIN_NREGS maps. */
1467 setup_reg_class_nregs (void)
1471 for (m
= 0; m
< MAX_MACHINE_MODE
; m
++)
1473 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1474 ira_reg_class_max_nregs
[cl
][m
]
1475 = ira_reg_class_min_nregs
[cl
][m
]
1476 = targetm
.class_max_nregs ((reg_class_t
) cl
, (enum machine_mode
) m
);
1477 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1479 (cl2
= alloc_reg_class_subclasses
[cl
][i
]) != LIM_REG_CLASSES
;
1481 if (ira_reg_class_min_nregs
[cl2
][m
]
1482 < ira_reg_class_min_nregs
[cl
][m
])
1483 ira_reg_class_min_nregs
[cl
][m
] = ira_reg_class_min_nregs
[cl2
][m
];
1489 /* Set up IRA_PROHIBITED_CLASS_MODE_REGS and IRA_CLASS_SINGLETON.
1490 This function is called once IRA_CLASS_HARD_REGS has been initialized. */
1492 setup_prohibited_class_mode_regs (void)
1494 int j
, k
, hard_regno
, cl
, last_hard_regno
, count
;
1496 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
1498 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
1499 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1500 for (j
= 0; j
< NUM_MACHINE_MODES
; j
++)
1503 last_hard_regno
= -1;
1504 CLEAR_HARD_REG_SET (ira_prohibited_class_mode_regs
[cl
][j
]);
1505 for (k
= ira_class_hard_regs_num
[cl
] - 1; k
>= 0; k
--)
1507 hard_regno
= ira_class_hard_regs
[cl
][k
];
1508 if (! HARD_REGNO_MODE_OK (hard_regno
, (enum machine_mode
) j
))
1509 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1511 else if (in_hard_reg_set_p (temp_hard_regset
,
1512 (enum machine_mode
) j
, hard_regno
))
1514 last_hard_regno
= hard_regno
;
1518 ira_class_singleton
[cl
][j
] = (count
== 1 ? last_hard_regno
: -1);
1523 /* Clarify IRA_PROHIBITED_CLASS_MODE_REGS by excluding hard registers
1524 spanning from one register pressure class to another one. It is
1525 called after defining the pressure classes. */
1527 clarify_prohibited_class_mode_regs (void)
1529 int j
, k
, hard_regno
, cl
, pclass
, nregs
;
1531 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
1532 for (j
= 0; j
< NUM_MACHINE_MODES
; j
++)
1534 CLEAR_HARD_REG_SET (ira_useful_class_mode_regs
[cl
][j
]);
1535 for (k
= ira_class_hard_regs_num
[cl
] - 1; k
>= 0; k
--)
1537 hard_regno
= ira_class_hard_regs
[cl
][k
];
1538 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
], hard_regno
))
1540 nregs
= hard_regno_nregs
[hard_regno
][j
];
1541 if (hard_regno
+ nregs
> FIRST_PSEUDO_REGISTER
)
1543 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1547 pclass
= ira_pressure_class_translate
[REGNO_REG_CLASS (hard_regno
)];
1548 for (nregs
-- ;nregs
>= 0; nregs
--)
1549 if (((enum reg_class
) pclass
1550 != ira_pressure_class_translate
[REGNO_REG_CLASS
1551 (hard_regno
+ nregs
)]))
1553 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1557 if (!TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1559 add_to_hard_reg_set (&ira_useful_class_mode_regs
[cl
][j
],
1560 (enum machine_mode
) j
, hard_regno
);
1565 /* Allocate and initialize IRA_REGISTER_MOVE_COST, IRA_MAY_MOVE_IN_COST
1566 and IRA_MAY_MOVE_OUT_COST for MODE. */
1568 ira_init_register_move_cost (enum machine_mode mode
)
1570 static unsigned short last_move_cost
[N_REG_CLASSES
][N_REG_CLASSES
];
1571 bool all_match
= true;
1572 unsigned int cl1
, cl2
;
1574 ira_assert (ira_register_move_cost
[mode
] == NULL
1575 && ira_may_move_in_cost
[mode
] == NULL
1576 && ira_may_move_out_cost
[mode
] == NULL
);
1577 ira_assert (have_regs_of_mode
[mode
]);
1578 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1579 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1582 if (!contains_reg_of_mode
[cl1
][mode
]
1583 || !contains_reg_of_mode
[cl2
][mode
])
1585 if ((ira_reg_class_max_nregs
[cl1
][mode
]
1586 > ira_class_hard_regs_num
[cl1
])
1587 || (ira_reg_class_max_nregs
[cl2
][mode
]
1588 > ira_class_hard_regs_num
[cl2
]))
1591 cost
= (ira_memory_move_cost
[mode
][cl1
][0]
1592 + ira_memory_move_cost
[mode
][cl2
][1]) * 2;
1596 cost
= register_move_cost (mode
, (enum reg_class
) cl1
,
1597 (enum reg_class
) cl2
);
1598 ira_assert (cost
< 65535);
1600 all_match
&= (last_move_cost
[cl1
][cl2
] == cost
);
1601 last_move_cost
[cl1
][cl2
] = cost
;
1603 if (all_match
&& last_mode_for_init_move_cost
!= -1)
1605 ira_register_move_cost
[mode
]
1606 = ira_register_move_cost
[last_mode_for_init_move_cost
];
1607 ira_may_move_in_cost
[mode
]
1608 = ira_may_move_in_cost
[last_mode_for_init_move_cost
];
1609 ira_may_move_out_cost
[mode
]
1610 = ira_may_move_out_cost
[last_mode_for_init_move_cost
];
1613 last_mode_for_init_move_cost
= mode
;
1614 ira_register_move_cost
[mode
] = XNEWVEC (move_table
, N_REG_CLASSES
);
1615 ira_may_move_in_cost
[mode
] = XNEWVEC (move_table
, N_REG_CLASSES
);
1616 ira_may_move_out_cost
[mode
] = XNEWVEC (move_table
, N_REG_CLASSES
);
1617 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1618 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1621 enum reg_class
*p1
, *p2
;
1623 if (last_move_cost
[cl1
][cl2
] == 65535)
1625 ira_register_move_cost
[mode
][cl1
][cl2
] = 65535;
1626 ira_may_move_in_cost
[mode
][cl1
][cl2
] = 65535;
1627 ira_may_move_out_cost
[mode
][cl1
][cl2
] = 65535;
1631 cost
= last_move_cost
[cl1
][cl2
];
1633 for (p2
= ®_class_subclasses
[cl2
][0];
1634 *p2
!= LIM_REG_CLASSES
; p2
++)
1635 if (ira_class_hard_regs_num
[*p2
] > 0
1636 && (ira_reg_class_max_nregs
[*p2
][mode
]
1637 <= ira_class_hard_regs_num
[*p2
]))
1638 cost
= MAX (cost
, ira_register_move_cost
[mode
][cl1
][*p2
]);
1640 for (p1
= ®_class_subclasses
[cl1
][0];
1641 *p1
!= LIM_REG_CLASSES
; p1
++)
1642 if (ira_class_hard_regs_num
[*p1
] > 0
1643 && (ira_reg_class_max_nregs
[*p1
][mode
]
1644 <= ira_class_hard_regs_num
[*p1
]))
1645 cost
= MAX (cost
, ira_register_move_cost
[mode
][*p1
][cl2
]);
1647 ira_assert (cost
<= 65535);
1648 ira_register_move_cost
[mode
][cl1
][cl2
] = cost
;
1650 if (ira_class_subset_p
[cl1
][cl2
])
1651 ira_may_move_in_cost
[mode
][cl1
][cl2
] = 0;
1653 ira_may_move_in_cost
[mode
][cl1
][cl2
] = cost
;
1655 if (ira_class_subset_p
[cl2
][cl1
])
1656 ira_may_move_out_cost
[mode
][cl1
][cl2
] = 0;
1658 ira_may_move_out_cost
[mode
][cl1
][cl2
] = cost
;
1665 /* This is called once during compiler work. It sets up
1666 different arrays whose values don't depend on the compiled
1669 ira_init_once (void)
1671 ira_init_costs_once ();
1675 /* Free ira_max_register_move_cost, ira_may_move_in_cost and
1676 ira_may_move_out_cost for each mode. */
1678 target_ira_int::free_register_move_costs (void)
1682 /* Reset move_cost and friends, making sure we only free shared
1683 table entries once. */
1684 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
1685 if (x_ira_register_move_cost
[mode
])
1688 i
< mode
&& (x_ira_register_move_cost
[i
]
1689 != x_ira_register_move_cost
[mode
]);
1694 free (x_ira_register_move_cost
[mode
]);
1695 free (x_ira_may_move_in_cost
[mode
]);
1696 free (x_ira_may_move_out_cost
[mode
]);
1699 memset (x_ira_register_move_cost
, 0, sizeof x_ira_register_move_cost
);
1700 memset (x_ira_may_move_in_cost
, 0, sizeof x_ira_may_move_in_cost
);
1701 memset (x_ira_may_move_out_cost
, 0, sizeof x_ira_may_move_out_cost
);
1702 last_mode_for_init_move_cost
= -1;
1705 target_ira_int::~target_ira_int ()
1708 free_register_move_costs ();
1711 /* This is called every time when register related information is
1716 this_target_ira_int
->free_register_move_costs ();
1717 setup_reg_mode_hard_regset ();
1718 setup_alloc_regs (flag_omit_frame_pointer
!= 0);
1719 setup_class_subset_and_memory_move_costs ();
1720 setup_reg_class_nregs ();
1721 setup_prohibited_class_mode_regs ();
1722 find_reg_classes ();
1723 clarify_prohibited_class_mode_regs ();
1724 setup_hard_regno_aclass ();
1729 #define ira_prohibited_mode_move_regs_initialized_p \
1730 (this_target_ira_int->x_ira_prohibited_mode_move_regs_initialized_p)
1732 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS. */
1734 setup_prohibited_mode_move_regs (void)
1737 rtx test_reg1
, test_reg2
, move_pat
;
1738 rtx_insn
*move_insn
;
1740 if (ira_prohibited_mode_move_regs_initialized_p
)
1742 ira_prohibited_mode_move_regs_initialized_p
= true;
1743 test_reg1
= gen_rtx_REG (VOIDmode
, 0);
1744 test_reg2
= gen_rtx_REG (VOIDmode
, 0);
1745 move_pat
= gen_rtx_SET (VOIDmode
, test_reg1
, test_reg2
);
1746 move_insn
= gen_rtx_INSN (VOIDmode
, 0, 0, 0, move_pat
, 0, -1, 0);
1747 for (i
= 0; i
< NUM_MACHINE_MODES
; i
++)
1749 SET_HARD_REG_SET (ira_prohibited_mode_move_regs
[i
]);
1750 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1752 if (! HARD_REGNO_MODE_OK (j
, (enum machine_mode
) i
))
1754 SET_REGNO_RAW (test_reg1
, j
);
1755 PUT_MODE (test_reg1
, (enum machine_mode
) i
);
1756 SET_REGNO_RAW (test_reg2
, j
);
1757 PUT_MODE (test_reg2
, (enum machine_mode
) i
);
1758 INSN_CODE (move_insn
) = -1;
1759 recog_memoized (move_insn
);
1760 if (INSN_CODE (move_insn
) < 0)
1762 extract_insn (move_insn
);
1763 if (! constrain_operands (1))
1765 CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs
[i
], j
);
1772 /* Setup possible alternatives in ALTS for INSN. */
1774 ira_setup_alts (rtx_insn
*insn
, HARD_REG_SET
&alts
)
1776 /* MAP nalt * nop -> start of constraints for given operand and
1778 static vec
<const char *> insn_constraints
;
1783 int commutative
= -1;
1785 extract_insn (insn
);
1786 CLEAR_HARD_REG_SET (alts
);
1787 insn_constraints
.release ();
1788 insn_constraints
.safe_grow_cleared (recog_data
.n_operands
1789 * recog_data
.n_alternatives
+ 1);
1790 /* Check that the hard reg set is enough for holding all
1791 alternatives. It is hard to imagine the situation when the
1792 assertion is wrong. */
1793 ira_assert (recog_data
.n_alternatives
1794 <= (int) MAX (sizeof (HARD_REG_ELT_TYPE
) * CHAR_BIT
,
1795 FIRST_PSEUDO_REGISTER
));
1796 for (curr_swapped
= false;; curr_swapped
= true)
1798 /* Calculate some data common for all alternatives to speed up the
1800 for (nop
= 0; nop
< recog_data
.n_operands
; nop
++)
1802 for (nalt
= 0, p
= recog_data
.constraints
[nop
];
1803 nalt
< recog_data
.n_alternatives
;
1806 insn_constraints
[nop
* recog_data
.n_alternatives
+ nalt
] = p
;
1807 while (*p
&& *p
!= ',')
1813 for (nalt
= 0; nalt
< recog_data
.n_alternatives
; nalt
++)
1815 if (!TEST_BIT (recog_data
.enabled_alternatives
, nalt
)
1816 || TEST_HARD_REG_BIT (alts
, nalt
))
1819 for (nop
= 0; nop
< recog_data
.n_operands
; nop
++)
1823 op
= recog_data
.operand
[nop
];
1824 p
= insn_constraints
[nop
* recog_data
.n_alternatives
+ nalt
];
1825 if (*p
== 0 || *p
== ',')
1829 switch (c
= *p
, len
= CONSTRAINT_LEN (c
, p
), c
)
1839 /* We only support one commutative marker, the
1840 first one. We already set commutative
1842 if (commutative
< 0)
1846 case '0': case '1': case '2': case '3': case '4':
1847 case '5': case '6': case '7': case '8': case '9':
1857 enum constraint_num cn
= lookup_constraint (p
);
1858 switch (get_constraint_type (cn
))
1861 if (reg_class_for_constraint (cn
) != NO_REGS
)
1866 if (CONST_INT_P (op
)
1867 && (insn_const_int_ok_for_constraint
1877 if (constraint_satisfied_p (op
, cn
))
1884 while (p
+= len
, c
);
1889 if (nop
>= recog_data
.n_operands
)
1890 SET_HARD_REG_BIT (alts
, nalt
);
1892 if (commutative
< 0)
1896 op
= recog_data
.operand
[commutative
];
1897 recog_data
.operand
[commutative
] = recog_data
.operand
[commutative
+ 1];
1898 recog_data
.operand
[commutative
+ 1] = op
;
1903 /* Return the number of the output non-early clobber operand which
1904 should be the same in any case as operand with number OP_NUM (or
1905 negative value if there is no such operand). The function takes
1906 only really possible alternatives into consideration. */
1908 ira_get_dup_out_num (int op_num
, HARD_REG_SET
&alts
)
1910 int curr_alt
, c
, original
, dup
;
1911 bool ignore_p
, use_commut_op_p
;
1914 if (op_num
< 0 || recog_data
.n_alternatives
== 0)
1916 /* We should find duplications only for input operands. */
1917 if (recog_data
.operand_type
[op_num
] != OP_IN
)
1919 str
= recog_data
.constraints
[op_num
];
1920 use_commut_op_p
= false;
1923 rtx op
= recog_data
.operand
[op_num
];
1925 for (curr_alt
= 0, ignore_p
= !TEST_HARD_REG_BIT (alts
, curr_alt
),
1936 ignore_p
= !TEST_HARD_REG_BIT (alts
, curr_alt
);
1938 else if (! ignore_p
)
1945 enum constraint_num cn
= lookup_constraint (str
);
1946 enum reg_class cl
= reg_class_for_constraint (cn
);
1948 && !targetm
.class_likely_spilled_p (cl
))
1950 if (constraint_satisfied_p (op
, cn
))
1955 case '0': case '1': case '2': case '3': case '4':
1956 case '5': case '6': case '7': case '8': case '9':
1957 if (original
!= -1 && original
!= c
)
1962 str
+= CONSTRAINT_LEN (c
, str
);
1967 for (ignore_p
= false, str
= recog_data
.constraints
[original
- '0'];
1975 else if (*str
== '#')
1977 else if (! ignore_p
)
1980 dup
= original
- '0';
1981 /* It is better ignore an alternative with early clobber. */
1982 else if (*str
== '&')
1988 if (use_commut_op_p
)
1990 use_commut_op_p
= true;
1991 if (recog_data
.constraints
[op_num
][0] == '%')
1992 str
= recog_data
.constraints
[op_num
+ 1];
1993 else if (op_num
> 0 && recog_data
.constraints
[op_num
- 1][0] == '%')
1994 str
= recog_data
.constraints
[op_num
- 1];
2003 /* Search forward to see if the source register of a copy insn dies
2004 before either it or the destination register is modified, but don't
2005 scan past the end of the basic block. If so, we can replace the
2006 source with the destination and let the source die in the copy
2009 This will reduce the number of registers live in that range and may
2010 enable the destination and the source coalescing, thus often saving
2011 one register in addition to a register-register copy. */
2014 decrease_live_ranges_number (void)
2018 rtx set
, src
, dest
, dest_death
, q
, note
;
2022 if (! flag_expensive_optimizations
)
2026 fprintf (ira_dump_file
, "Starting decreasing number of live ranges...\n");
2028 FOR_EACH_BB_FN (bb
, cfun
)
2029 FOR_BB_INSNS (bb
, insn
)
2031 set
= single_set (insn
);
2034 src
= SET_SRC (set
);
2035 dest
= SET_DEST (set
);
2036 if (! REG_P (src
) || ! REG_P (dest
)
2037 || find_reg_note (insn
, REG_DEAD
, src
))
2039 sregno
= REGNO (src
);
2040 dregno
= REGNO (dest
);
2042 /* We don't want to mess with hard regs if register classes
2044 if (sregno
== dregno
2045 || (targetm
.small_register_classes_for_mode_p (GET_MODE (src
))
2046 && (sregno
< FIRST_PSEUDO_REGISTER
2047 || dregno
< FIRST_PSEUDO_REGISTER
))
2048 /* We don't see all updates to SP if they are in an
2049 auto-inc memory reference, so we must disallow this
2050 optimization on them. */
2051 || sregno
== STACK_POINTER_REGNUM
2052 || dregno
== STACK_POINTER_REGNUM
)
2055 dest_death
= NULL_RTX
;
2057 for (p
= NEXT_INSN (insn
); p
; p
= NEXT_INSN (p
))
2061 if (BLOCK_FOR_INSN (p
) != bb
)
2064 if (reg_set_p (src
, p
) || reg_set_p (dest
, p
)
2065 /* If SRC is an asm-declared register, it must not be
2066 replaced in any asm. Unfortunately, the REG_EXPR
2067 tree for the asm variable may be absent in the SRC
2068 rtx, so we can't check the actual register
2069 declaration easily (the asm operand will have it,
2070 though). To avoid complicating the test for a rare
2071 case, we just don't perform register replacement
2072 for a hard reg mentioned in an asm. */
2073 || (sregno
< FIRST_PSEUDO_REGISTER
2074 && asm_noperands (PATTERN (p
)) >= 0
2075 && reg_overlap_mentioned_p (src
, PATTERN (p
)))
2076 /* Don't change hard registers used by a call. */
2077 || (CALL_P (p
) && sregno
< FIRST_PSEUDO_REGISTER
2078 && find_reg_fusage (p
, USE
, src
))
2079 /* Don't change a USE of a register. */
2080 || (GET_CODE (PATTERN (p
)) == USE
2081 && reg_overlap_mentioned_p (src
, XEXP (PATTERN (p
), 0))))
2084 /* See if all of SRC dies in P. This test is slightly
2085 more conservative than it needs to be. */
2086 if ((note
= find_regno_note (p
, REG_DEAD
, sregno
))
2087 && GET_MODE (XEXP (note
, 0)) == GET_MODE (src
))
2091 /* We can do the optimization. Scan forward from INSN
2092 again, replacing regs as we go. Set FAILED if a
2093 replacement can't be done. In that case, we can't
2094 move the death note for SRC. This should be
2097 /* Set to stop at next insn. */
2098 for (q
= next_real_insn (insn
);
2099 q
!= next_real_insn (p
);
2100 q
= next_real_insn (q
))
2102 if (reg_overlap_mentioned_p (src
, PATTERN (q
)))
2104 /* If SRC is a hard register, we might miss
2105 some overlapping registers with
2106 validate_replace_rtx, so we would have to
2107 undo it. We can't if DEST is present in
2108 the insn, so fail in that combination of
2110 if (sregno
< FIRST_PSEUDO_REGISTER
2111 && reg_mentioned_p (dest
, PATTERN (q
)))
2114 /* Attempt to replace all uses. */
2115 else if (!validate_replace_rtx (src
, dest
, q
))
2118 /* If this succeeded, but some part of the
2119 register is still present, undo the
2121 else if (sregno
< FIRST_PSEUDO_REGISTER
2122 && reg_overlap_mentioned_p (src
, PATTERN (q
)))
2124 validate_replace_rtx (dest
, src
, q
);
2129 /* If DEST dies here, remove the death note and
2130 save it for later. Make sure ALL of DEST dies
2131 here; again, this is overly conservative. */
2133 && (dest_death
= find_regno_note (q
, REG_DEAD
, dregno
)))
2135 if (GET_MODE (XEXP (dest_death
, 0)) == GET_MODE (dest
))
2136 remove_note (q
, dest_death
);
2147 /* Move death note of SRC from P to INSN. */
2148 remove_note (p
, note
);
2149 XEXP (note
, 1) = REG_NOTES (insn
);
2150 REG_NOTES (insn
) = note
;
2153 /* DEST is also dead if INSN has a REG_UNUSED note for
2157 = find_regno_note (insn
, REG_UNUSED
, dregno
)))
2159 PUT_REG_NOTE_KIND (dest_death
, REG_DEAD
);
2160 remove_note (insn
, dest_death
);
2163 /* Put death note of DEST on P if we saw it die. */
2166 XEXP (dest_death
, 1) = REG_NOTES (p
);
2167 REG_NOTES (p
) = dest_death
;
2172 /* If SRC is a hard register which is set or killed in
2173 some other way, we can't do this optimization. */
2174 else if (sregno
< FIRST_PSEUDO_REGISTER
&& dead_or_set_p (p
, src
))
2182 /* Return nonzero if REGNO is a particularly bad choice for reloading X. */
2184 ira_bad_reload_regno_1 (int regno
, rtx x
)
2188 enum reg_class pref
;
2190 /* We only deal with pseudo regs. */
2191 if (! x
|| GET_CODE (x
) != REG
)
2194 x_regno
= REGNO (x
);
2195 if (x_regno
< FIRST_PSEUDO_REGISTER
)
2198 /* If the pseudo prefers REGNO explicitly, then do not consider
2199 REGNO a bad spill choice. */
2200 pref
= reg_preferred_class (x_regno
);
2201 if (reg_class_size
[pref
] == 1)
2202 return !TEST_HARD_REG_BIT (reg_class_contents
[pref
], regno
);
2204 /* If the pseudo conflicts with REGNO, then we consider REGNO a
2205 poor choice for a reload regno. */
2206 a
= ira_regno_allocno_map
[x_regno
];
2207 n
= ALLOCNO_NUM_OBJECTS (a
);
2208 for (i
= 0; i
< n
; i
++)
2210 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2211 if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), regno
))
2217 /* Return nonzero if REGNO is a particularly bad choice for reloading
2220 ira_bad_reload_regno (int regno
, rtx in
, rtx out
)
2222 return (ira_bad_reload_regno_1 (regno
, in
)
2223 || ira_bad_reload_regno_1 (regno
, out
));
2226 /* Add register clobbers from asm statements. */
2228 compute_regs_asm_clobbered (void)
2232 FOR_EACH_BB_FN (bb
, cfun
)
2235 FOR_BB_INSNS_REVERSE (bb
, insn
)
2239 if (NONDEBUG_INSN_P (insn
) && extract_asm_operands (PATTERN (insn
)))
2240 FOR_EACH_INSN_DEF (def
, insn
)
2242 unsigned int dregno
= DF_REF_REGNO (def
);
2243 if (HARD_REGISTER_NUM_P (dregno
))
2244 add_to_hard_reg_set (&crtl
->asm_clobbers
,
2245 GET_MODE (DF_REF_REAL_REG (def
)),
2253 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and
2256 ira_setup_eliminable_regset (void)
2258 #ifdef ELIMINABLE_REGS
2260 static const struct {const int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
2262 /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
2263 sp for alloca. So we can't eliminate the frame pointer in that
2264 case. At some point, we should improve this by emitting the
2265 sp-adjusting insns for this case. */
2266 frame_pointer_needed
2267 = (! flag_omit_frame_pointer
2268 || (cfun
->calls_alloca
&& EXIT_IGNORE_STACK
)
2269 /* We need the frame pointer to catch stack overflow exceptions
2270 if the stack pointer is moving. */
2271 || (flag_stack_check
&& STACK_CHECK_MOVING_SP
)
2272 || crtl
->accesses_prior_frames
2273 || (SUPPORTS_STACK_ALIGNMENT
&& crtl
->stack_realign_needed
)
2274 /* We need a frame pointer for all Cilk Plus functions that use
2276 || (flag_cilkplus
&& cfun
->is_cilk_function
)
2277 || targetm
.frame_pointer_required ());
2279 /* The chance that FRAME_POINTER_NEEDED is changed from inspecting
2280 RTL is very small. So if we use frame pointer for RA and RTL
2281 actually prevents this, we will spill pseudos assigned to the
2282 frame pointer in LRA. */
2284 if (frame_pointer_needed
)
2285 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM
, true);
2287 COPY_HARD_REG_SET (ira_no_alloc_regs
, no_unit_alloc_regs
);
2288 CLEAR_HARD_REG_SET (eliminable_regset
);
2290 compute_regs_asm_clobbered ();
2292 /* Build the regset of all eliminable registers and show we can't
2293 use those that we already know won't be eliminated. */
2294 #ifdef ELIMINABLE_REGS
2295 for (i
= 0; i
< (int) ARRAY_SIZE (eliminables
); i
++)
2298 = (! targetm
.can_eliminate (eliminables
[i
].from
, eliminables
[i
].to
)
2299 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& frame_pointer_needed
));
2301 if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
, eliminables
[i
].from
))
2303 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
2306 SET_HARD_REG_BIT (ira_no_alloc_regs
, eliminables
[i
].from
);
2308 else if (cannot_elim
)
2309 error ("%s cannot be used in asm here",
2310 reg_names
[eliminables
[i
].from
]);
2312 df_set_regs_ever_live (eliminables
[i
].from
, true);
2314 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
2315 if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
, HARD_FRAME_POINTER_REGNUM
))
2317 SET_HARD_REG_BIT (eliminable_regset
, HARD_FRAME_POINTER_REGNUM
);
2318 if (frame_pointer_needed
)
2319 SET_HARD_REG_BIT (ira_no_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
2321 else if (frame_pointer_needed
)
2322 error ("%s cannot be used in asm here",
2323 reg_names
[HARD_FRAME_POINTER_REGNUM
]);
2325 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM
, true);
2329 if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
, HARD_FRAME_POINTER_REGNUM
))
2331 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
2332 if (frame_pointer_needed
)
2333 SET_HARD_REG_BIT (ira_no_alloc_regs
, FRAME_POINTER_REGNUM
);
2335 else if (frame_pointer_needed
)
2336 error ("%s cannot be used in asm here", reg_names
[FRAME_POINTER_REGNUM
]);
2338 df_set_regs_ever_live (FRAME_POINTER_REGNUM
, true);
2344 /* Vector of substitutions of register numbers,
2345 used to map pseudo regs into hardware regs.
2346 This is set up as a result of register allocation.
2347 Element N is the hard reg assigned to pseudo reg N,
2348 or is -1 if no hard reg was assigned.
2349 If N is a hard reg number, element N is N. */
2350 short *reg_renumber
;
2352 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
2353 the allocation found by IRA. */
2355 setup_reg_renumber (void)
2357 int regno
, hard_regno
;
2359 ira_allocno_iterator ai
;
2361 caller_save_needed
= 0;
2362 FOR_EACH_ALLOCNO (a
, ai
)
2364 if (ira_use_lra_p
&& ALLOCNO_CAP_MEMBER (a
) != NULL
)
2366 /* There are no caps at this point. */
2367 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
2368 if (! ALLOCNO_ASSIGNED_P (a
))
2369 /* It can happen if A is not referenced but partially anticipated
2370 somewhere in a region. */
2371 ALLOCNO_ASSIGNED_P (a
) = true;
2372 ira_free_allocno_updated_costs (a
);
2373 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2374 regno
= ALLOCNO_REGNO (a
);
2375 reg_renumber
[regno
] = (hard_regno
< 0 ? -1 : hard_regno
);
2376 if (hard_regno
>= 0)
2379 enum reg_class pclass
;
2382 pclass
= ira_pressure_class_translate
[REGNO_REG_CLASS (hard_regno
)];
2383 nwords
= ALLOCNO_NUM_OBJECTS (a
);
2384 for (i
= 0; i
< nwords
; i
++)
2386 obj
= ALLOCNO_OBJECT (a
, i
);
2387 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
2388 reg_class_contents
[pclass
]);
2390 if (ALLOCNO_CALLS_CROSSED_NUM (a
) != 0
2391 && ira_hard_reg_set_intersection_p (hard_regno
, ALLOCNO_MODE (a
),
2394 ira_assert (!optimize
|| flag_caller_saves
2395 || (ALLOCNO_CALLS_CROSSED_NUM (a
)
2396 == ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
))
2397 || regno
>= ira_reg_equiv_len
2398 || ira_equiv_no_lvalue_p (regno
));
2399 caller_save_needed
= 1;
2405 /* Set up allocno assignment flags for further allocation
2408 setup_allocno_assignment_flags (void)
2412 ira_allocno_iterator ai
;
2414 FOR_EACH_ALLOCNO (a
, ai
)
2416 if (! ALLOCNO_ASSIGNED_P (a
))
2417 /* It can happen if A is not referenced but partially anticipated
2418 somewhere in a region. */
2419 ira_free_allocno_updated_costs (a
);
2420 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2421 /* Don't assign hard registers to allocnos which are destination
2422 of removed store at the end of loop. It has no sense to keep
2423 the same value in different hard registers. It is also
2424 impossible to assign hard registers correctly to such
2425 allocnos because the cost info and info about intersected
2426 calls are incorrect for them. */
2427 ALLOCNO_ASSIGNED_P (a
) = (hard_regno
>= 0
2428 || ALLOCNO_EMIT_DATA (a
)->mem_optimized_dest_p
2429 || (ALLOCNO_MEMORY_COST (a
)
2430 - ALLOCNO_CLASS_COST (a
)) < 0);
2433 || ira_hard_reg_in_set_p (hard_regno
, ALLOCNO_MODE (a
),
2434 reg_class_contents
[ALLOCNO_CLASS (a
)]));
2438 /* Evaluate overall allocation cost and the costs for using hard
2439 registers and memory for allocnos. */
2441 calculate_allocation_cost (void)
2443 int hard_regno
, cost
;
2445 ira_allocno_iterator ai
;
2447 ira_overall_cost
= ira_reg_cost
= ira_mem_cost
= 0;
2448 FOR_EACH_ALLOCNO (a
, ai
)
2450 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2451 ira_assert (hard_regno
< 0
2452 || (ira_hard_reg_in_set_p
2453 (hard_regno
, ALLOCNO_MODE (a
),
2454 reg_class_contents
[ALLOCNO_CLASS (a
)])));
2457 cost
= ALLOCNO_MEMORY_COST (a
);
2458 ira_mem_cost
+= cost
;
2460 else if (ALLOCNO_HARD_REG_COSTS (a
) != NULL
)
2462 cost
= (ALLOCNO_HARD_REG_COSTS (a
)
2463 [ira_class_hard_reg_index
2464 [ALLOCNO_CLASS (a
)][hard_regno
]]);
2465 ira_reg_cost
+= cost
;
2469 cost
= ALLOCNO_CLASS_COST (a
);
2470 ira_reg_cost
+= cost
;
2472 ira_overall_cost
+= cost
;
2475 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
2477 fprintf (ira_dump_file
,
2478 "+++Costs: overall %d, reg %d, mem %d, ld %d, st %d, move %d\n",
2479 ira_overall_cost
, ira_reg_cost
, ira_mem_cost
,
2480 ira_load_cost
, ira_store_cost
, ira_shuffle_cost
);
2481 fprintf (ira_dump_file
, "+++ move loops %d, new jumps %d\n",
2482 ira_move_loops_num
, ira_additional_jumps_num
);
2487 #ifdef ENABLE_IRA_CHECKING
2488 /* Check the correctness of the allocation. We do need this because
2489 of complicated code to transform more one region internal
2490 representation into one region representation. */
2492 check_allocation (void)
2495 int hard_regno
, nregs
, conflict_nregs
;
2496 ira_allocno_iterator ai
;
2498 FOR_EACH_ALLOCNO (a
, ai
)
2500 int n
= ALLOCNO_NUM_OBJECTS (a
);
2503 if (ALLOCNO_CAP_MEMBER (a
) != NULL
2504 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0)
2506 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (a
)];
2508 /* We allocated a single hard register. */
2511 /* We allocated multiple hard registers, and we will test
2512 conflicts in a granularity of single hard regs. */
2515 for (i
= 0; i
< n
; i
++)
2517 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2518 ira_object_t conflict_obj
;
2519 ira_object_conflict_iterator oci
;
2520 int this_regno
= hard_regno
;
2523 if (REG_WORDS_BIG_ENDIAN
)
2524 this_regno
+= n
- i
- 1;
2528 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2530 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2531 int conflict_hard_regno
= ALLOCNO_HARD_REGNO (conflict_a
);
2532 if (conflict_hard_regno
< 0)
2537 [conflict_hard_regno
][ALLOCNO_MODE (conflict_a
)]);
2539 if (ALLOCNO_NUM_OBJECTS (conflict_a
) > 1
2540 && conflict_nregs
== ALLOCNO_NUM_OBJECTS (conflict_a
))
2542 if (REG_WORDS_BIG_ENDIAN
)
2543 conflict_hard_regno
+= (ALLOCNO_NUM_OBJECTS (conflict_a
)
2544 - OBJECT_SUBWORD (conflict_obj
) - 1);
2546 conflict_hard_regno
+= OBJECT_SUBWORD (conflict_obj
);
2550 if ((conflict_hard_regno
<= this_regno
2551 && this_regno
< conflict_hard_regno
+ conflict_nregs
)
2552 || (this_regno
<= conflict_hard_regno
2553 && conflict_hard_regno
< this_regno
+ nregs
))
2555 fprintf (stderr
, "bad allocation for %d and %d\n",
2556 ALLOCNO_REGNO (a
), ALLOCNO_REGNO (conflict_a
));
2565 /* Allocate REG_EQUIV_INIT. Set up it from IRA_REG_EQUIV which should
2566 be already calculated. */
2568 setup_reg_equiv_init (void)
2571 int max_regno
= max_reg_num ();
2573 for (i
= 0; i
< max_regno
; i
++)
2574 reg_equiv_init (i
) = ira_reg_equiv
[i
].init_insns
;
2577 /* Update equiv regno from movement of FROM_REGNO to TO_REGNO. INSNS
2578 are insns which were generated for such movement. It is assumed
2579 that FROM_REGNO and TO_REGNO always have the same value at the
2580 point of any move containing such registers. This function is used
2581 to update equiv info for register shuffles on the region borders
2582 and for caller save/restore insns. */
2584 ira_update_equiv_info_by_shuffle_insn (int to_regno
, int from_regno
, rtx_insn
*insns
)
2589 if (! ira_reg_equiv
[from_regno
].defined_p
2590 && (! ira_reg_equiv
[to_regno
].defined_p
2591 || ((x
= ira_reg_equiv
[to_regno
].memory
) != NULL_RTX
2592 && ! MEM_READONLY_P (x
))))
2595 if (NEXT_INSN (insn
) != NULL_RTX
)
2597 if (! ira_reg_equiv
[to_regno
].defined_p
)
2599 ira_assert (ira_reg_equiv
[to_regno
].init_insns
== NULL_RTX
);
2602 ira_reg_equiv
[to_regno
].defined_p
= false;
2603 ira_reg_equiv
[to_regno
].memory
2604 = ira_reg_equiv
[to_regno
].constant
2605 = ira_reg_equiv
[to_regno
].invariant
2606 = ira_reg_equiv
[to_regno
].init_insns
= NULL
;
2607 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2608 fprintf (ira_dump_file
,
2609 " Invalidating equiv info for reg %d\n", to_regno
);
2612 /* It is possible that FROM_REGNO still has no equivalence because
2613 in shuffles to_regno<-from_regno and from_regno<-to_regno the 2nd
2614 insn was not processed yet. */
2615 if (ira_reg_equiv
[from_regno
].defined_p
)
2617 ira_reg_equiv
[to_regno
].defined_p
= true;
2618 if ((x
= ira_reg_equiv
[from_regno
].memory
) != NULL_RTX
)
2620 ira_assert (ira_reg_equiv
[from_regno
].invariant
== NULL_RTX
2621 && ira_reg_equiv
[from_regno
].constant
== NULL_RTX
);
2622 ira_assert (ira_reg_equiv
[to_regno
].memory
== NULL_RTX
2623 || rtx_equal_p (ira_reg_equiv
[to_regno
].memory
, x
));
2624 ira_reg_equiv
[to_regno
].memory
= x
;
2625 if (! MEM_READONLY_P (x
))
2626 /* We don't add the insn to insn init list because memory
2627 equivalence is just to say what memory is better to use
2628 when the pseudo is spilled. */
2631 else if ((x
= ira_reg_equiv
[from_regno
].constant
) != NULL_RTX
)
2633 ira_assert (ira_reg_equiv
[from_regno
].invariant
== NULL_RTX
);
2634 ira_assert (ira_reg_equiv
[to_regno
].constant
== NULL_RTX
2635 || rtx_equal_p (ira_reg_equiv
[to_regno
].constant
, x
));
2636 ira_reg_equiv
[to_regno
].constant
= x
;
2640 x
= ira_reg_equiv
[from_regno
].invariant
;
2641 ira_assert (x
!= NULL_RTX
);
2642 ira_assert (ira_reg_equiv
[to_regno
].invariant
== NULL_RTX
2643 || rtx_equal_p (ira_reg_equiv
[to_regno
].invariant
, x
));
2644 ira_reg_equiv
[to_regno
].invariant
= x
;
2646 if (find_reg_note (insn
, REG_EQUIV
, x
) == NULL_RTX
)
2648 note
= set_unique_reg_note (insn
, REG_EQUIV
, x
);
2649 gcc_assert (note
!= NULL_RTX
);
2650 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2652 fprintf (ira_dump_file
,
2653 " Adding equiv note to insn %u for reg %d ",
2654 INSN_UID (insn
), to_regno
);
2655 dump_value_slim (ira_dump_file
, x
, 1);
2656 fprintf (ira_dump_file
, "\n");
2660 ira_reg_equiv
[to_regno
].init_insns
2661 = gen_rtx_INSN_LIST (VOIDmode
, insn
,
2662 ira_reg_equiv
[to_regno
].init_insns
);
2663 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2664 fprintf (ira_dump_file
,
2665 " Adding equiv init move insn %u to reg %d\n",
2666 INSN_UID (insn
), to_regno
);
2669 /* Fix values of array REG_EQUIV_INIT after live range splitting done
2672 fix_reg_equiv_init (void)
2674 int max_regno
= max_reg_num ();
2675 int i
, new_regno
, max
;
2676 rtx x
, prev
, next
, insn
, set
;
2678 if (max_regno_before_ira
< max_regno
)
2680 max
= vec_safe_length (reg_equivs
);
2682 for (i
= FIRST_PSEUDO_REGISTER
; i
< max
; i
++)
2683 for (prev
= NULL_RTX
, x
= reg_equiv_init (i
);
2689 set
= single_set (as_a
<rtx_insn
*> (insn
));
2690 ira_assert (set
!= NULL_RTX
2691 && (REG_P (SET_DEST (set
)) || REG_P (SET_SRC (set
))));
2692 if (REG_P (SET_DEST (set
))
2693 && ((int) REGNO (SET_DEST (set
)) == i
2694 || (int) ORIGINAL_REGNO (SET_DEST (set
)) == i
))
2695 new_regno
= REGNO (SET_DEST (set
));
2696 else if (REG_P (SET_SRC (set
))
2697 && ((int) REGNO (SET_SRC (set
)) == i
2698 || (int) ORIGINAL_REGNO (SET_SRC (set
)) == i
))
2699 new_regno
= REGNO (SET_SRC (set
));
2706 /* Remove the wrong list element. */
2707 if (prev
== NULL_RTX
)
2708 reg_equiv_init (i
) = next
;
2710 XEXP (prev
, 1) = next
;
2711 XEXP (x
, 1) = reg_equiv_init (new_regno
);
2712 reg_equiv_init (new_regno
) = x
;
2718 #ifdef ENABLE_IRA_CHECKING
2719 /* Print redundant memory-memory copies. */
2721 print_redundant_copies (void)
2725 ira_copy_t cp
, next_cp
;
2726 ira_allocno_iterator ai
;
2728 FOR_EACH_ALLOCNO (a
, ai
)
2730 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2733 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2734 if (hard_regno
>= 0)
2736 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2738 next_cp
= cp
->next_first_allocno_copy
;
2741 next_cp
= cp
->next_second_allocno_copy
;
2742 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
2743 && cp
->insn
!= NULL_RTX
2744 && ALLOCNO_HARD_REGNO (cp
->first
) == hard_regno
)
2745 fprintf (ira_dump_file
,
2746 " Redundant move from %d(freq %d):%d\n",
2747 INSN_UID (cp
->insn
), cp
->freq
, hard_regno
);
2753 /* Setup preferred and alternative classes for new pseudo-registers
2754 created by IRA starting with START. */
2756 setup_preferred_alternate_classes_for_new_pseudos (int start
)
2759 int max_regno
= max_reg_num ();
2761 for (i
= start
; i
< max_regno
; i
++)
2763 old_regno
= ORIGINAL_REGNO (regno_reg_rtx
[i
]);
2764 ira_assert (i
!= old_regno
);
2765 setup_reg_classes (i
, reg_preferred_class (old_regno
),
2766 reg_alternate_class (old_regno
),
2767 reg_allocno_class (old_regno
));
2768 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
2769 fprintf (ira_dump_file
,
2770 " New r%d: setting preferred %s, alternative %s\n",
2771 i
, reg_class_names
[reg_preferred_class (old_regno
)],
2772 reg_class_names
[reg_alternate_class (old_regno
)]);
2777 /* The number of entries allocated in reg_info. */
2778 static int allocated_reg_info_size
;
2780 /* Regional allocation can create new pseudo-registers. This function
2781 expands some arrays for pseudo-registers. */
2783 expand_reg_info (void)
2786 int size
= max_reg_num ();
2789 for (i
= allocated_reg_info_size
; i
< size
; i
++)
2790 setup_reg_classes (i
, GENERAL_REGS
, ALL_REGS
, GENERAL_REGS
);
2791 setup_preferred_alternate_classes_for_new_pseudos (allocated_reg_info_size
);
2792 allocated_reg_info_size
= size
;
2795 /* Return TRUE if there is too high register pressure in the function.
2796 It is used to decide when stack slot sharing is worth to do. */
2798 too_high_register_pressure_p (void)
2801 enum reg_class pclass
;
2803 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2805 pclass
= ira_pressure_classes
[i
];
2806 if (ira_loop_tree_root
->reg_pressure
[pclass
] > 10000)
2814 /* Indicate that hard register number FROM was eliminated and replaced with
2815 an offset from hard register number TO. The status of hard registers live
2816 at the start of a basic block is updated by replacing a use of FROM with
2820 mark_elimination (int from
, int to
)
2825 FOR_EACH_BB_FN (bb
, cfun
)
2828 if (bitmap_bit_p (r
, from
))
2830 bitmap_clear_bit (r
, from
);
2831 bitmap_set_bit (r
, to
);
2835 r
= DF_LIVE_IN (bb
);
2836 if (bitmap_bit_p (r
, from
))
2838 bitmap_clear_bit (r
, from
);
2839 bitmap_set_bit (r
, to
);
2846 /* The length of the following array. */
2847 int ira_reg_equiv_len
;
2849 /* Info about equiv. info for each register. */
2850 struct ira_reg_equiv_s
*ira_reg_equiv
;
2852 /* Expand ira_reg_equiv if necessary. */
2854 ira_expand_reg_equiv (void)
2856 int old
= ira_reg_equiv_len
;
2858 if (ira_reg_equiv_len
> max_reg_num ())
2860 ira_reg_equiv_len
= max_reg_num () * 3 / 2 + 1;
2862 = (struct ira_reg_equiv_s
*) xrealloc (ira_reg_equiv
,
2864 * sizeof (struct ira_reg_equiv_s
));
2865 gcc_assert (old
< ira_reg_equiv_len
);
2866 memset (ira_reg_equiv
+ old
, 0,
2867 sizeof (struct ira_reg_equiv_s
) * (ira_reg_equiv_len
- old
));
2871 init_reg_equiv (void)
2873 ira_reg_equiv_len
= 0;
2874 ira_reg_equiv
= NULL
;
2875 ira_expand_reg_equiv ();
2879 finish_reg_equiv (void)
2881 free (ira_reg_equiv
);
2888 /* Set when a REG_EQUIV note is found or created. Use to
2889 keep track of what memory accesses might be created later,
2894 /* The list of each instruction which initializes this register.
2896 NULL indicates we know nothing about this register's equivalence
2899 An INSN_LIST with a NULL insn indicates this pseudo is already
2900 known to not have a valid equivalence. */
2901 rtx_insn_list
*init_insns
;
2903 /* Loop depth is used to recognize equivalences which appear
2904 to be present within the same loop (or in an inner loop). */
2906 /* Nonzero if this had a preexisting REG_EQUIV note. */
2907 unsigned char is_arg_equivalence
: 1;
2908 /* Set when an attempt should be made to replace a register
2909 with the associated src_p entry. */
2910 unsigned char replace
: 1;
2911 /* Set if this register has no known equivalence. */
2912 unsigned char no_equiv
: 1;
2915 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
2916 structure for that register. */
2917 static struct equivalence
*reg_equiv
;
2919 /* Used for communication between the following two functions: contains
2920 a MEM that we wish to ensure remains unchanged. */
2921 static rtx equiv_mem
;
2923 /* Set nonzero if EQUIV_MEM is modified. */
2924 static int equiv_mem_modified
;
2926 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
2927 Called via note_stores. */
2929 validate_equiv_mem_from_store (rtx dest
, const_rtx set ATTRIBUTE_UNUSED
,
2930 void *data ATTRIBUTE_UNUSED
)
2933 && reg_overlap_mentioned_p (dest
, equiv_mem
))
2935 && anti_dependence (equiv_mem
, dest
)))
2936 equiv_mem_modified
= 1;
2939 /* Verify that no store between START and the death of REG invalidates
2940 MEMREF. MEMREF is invalidated by modifying a register used in MEMREF,
2941 by storing into an overlapping memory location, or with a non-const
2944 Return 1 if MEMREF remains valid. */
2946 validate_equiv_mem (rtx_insn
*start
, rtx reg
, rtx memref
)
2952 equiv_mem_modified
= 0;
2954 /* If the memory reference has side effects or is volatile, it isn't a
2955 valid equivalence. */
2956 if (side_effects_p (memref
))
2959 for (insn
= start
; insn
&& ! equiv_mem_modified
; insn
= NEXT_INSN (insn
))
2961 if (! INSN_P (insn
))
2964 if (find_reg_note (insn
, REG_DEAD
, reg
))
2967 /* This used to ignore readonly memory and const/pure calls. The problem
2968 is the equivalent form may reference a pseudo which gets assigned a
2969 call clobbered hard reg. When we later replace REG with its
2970 equivalent form, the value in the call-clobbered reg has been
2971 changed and all hell breaks loose. */
2975 note_stores (PATTERN (insn
), validate_equiv_mem_from_store
, NULL
);
2977 /* If a register mentioned in MEMREF is modified via an
2978 auto-increment, we lose the equivalence. Do the same if one
2979 dies; although we could extend the life, it doesn't seem worth
2982 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
2983 if ((REG_NOTE_KIND (note
) == REG_INC
2984 || REG_NOTE_KIND (note
) == REG_DEAD
)
2985 && REG_P (XEXP (note
, 0))
2986 && reg_overlap_mentioned_p (XEXP (note
, 0), memref
))
2993 /* Returns zero if X is known to be invariant. */
2995 equiv_init_varies_p (rtx x
)
2997 RTX_CODE code
= GET_CODE (x
);
3004 return !MEM_READONLY_P (x
) || equiv_init_varies_p (XEXP (x
, 0));
3013 return reg_equiv
[REGNO (x
)].replace
== 0 && rtx_varies_p (x
, 0);
3016 if (MEM_VOLATILE_P (x
))
3025 fmt
= GET_RTX_FORMAT (code
);
3026 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3029 if (equiv_init_varies_p (XEXP (x
, i
)))
3032 else if (fmt
[i
] == 'E')
3035 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
3036 if (equiv_init_varies_p (XVECEXP (x
, i
, j
)))
3043 /* Returns nonzero if X (used to initialize register REGNO) is movable.
3044 X is only movable if the registers it uses have equivalent initializations
3045 which appear to be within the same loop (or in an inner loop) and movable
3046 or if they are not candidates for local_alloc and don't vary. */
3048 equiv_init_movable_p (rtx x
, int regno
)
3052 enum rtx_code code
= GET_CODE (x
);
3057 return equiv_init_movable_p (SET_SRC (x
), regno
);
3072 return ((reg_equiv
[REGNO (x
)].loop_depth
>= reg_equiv
[regno
].loop_depth
3073 && reg_equiv
[REGNO (x
)].replace
)
3074 || (REG_BASIC_BLOCK (REGNO (x
)) < NUM_FIXED_BLOCKS
3075 && ! rtx_varies_p (x
, 0)));
3077 case UNSPEC_VOLATILE
:
3081 if (MEM_VOLATILE_P (x
))
3090 fmt
= GET_RTX_FORMAT (code
);
3091 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3095 if (! equiv_init_movable_p (XEXP (x
, i
), regno
))
3099 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
3100 if (! equiv_init_movable_p (XVECEXP (x
, i
, j
), regno
))
3108 /* TRUE if X uses any registers for which reg_equiv[REGNO].replace is
3111 contains_replace_regs (rtx x
)
3115 enum rtx_code code
= GET_CODE (x
);
3129 return reg_equiv
[REGNO (x
)].replace
;
3135 fmt
= GET_RTX_FORMAT (code
);
3136 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3140 if (contains_replace_regs (XEXP (x
, i
)))
3144 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
3145 if (contains_replace_regs (XVECEXP (x
, i
, j
)))
3153 /* TRUE if X references a memory location that would be affected by a store
3156 memref_referenced_p (rtx memref
, rtx x
)
3160 enum rtx_code code
= GET_CODE (x
);
3175 return (reg_equiv
[REGNO (x
)].replacement
3176 && memref_referenced_p (memref
,
3177 reg_equiv
[REGNO (x
)].replacement
));
3180 if (true_dependence (memref
, VOIDmode
, x
))
3185 /* If we are setting a MEM, it doesn't count (its address does), but any
3186 other SET_DEST that has a MEM in it is referencing the MEM. */
3187 if (MEM_P (SET_DEST (x
)))
3189 if (memref_referenced_p (memref
, XEXP (SET_DEST (x
), 0)))
3192 else if (memref_referenced_p (memref
, SET_DEST (x
)))
3195 return memref_referenced_p (memref
, SET_SRC (x
));
3201 fmt
= GET_RTX_FORMAT (code
);
3202 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3206 if (memref_referenced_p (memref
, XEXP (x
, i
)))
3210 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
3211 if (memref_referenced_p (memref
, XVECEXP (x
, i
, j
)))
3219 /* TRUE if some insn in the range (START, END] references a memory location
3220 that would be affected by a store to MEMREF. */
3222 memref_used_between_p (rtx memref
, rtx_insn
*start
, rtx_insn
*end
)
3226 for (insn
= NEXT_INSN (start
); insn
!= NEXT_INSN (end
);
3227 insn
= NEXT_INSN (insn
))
3229 if (!NONDEBUG_INSN_P (insn
))
3232 if (memref_referenced_p (memref
, PATTERN (insn
)))
3235 /* Nonconst functions may access memory. */
3236 if (CALL_P (insn
) && (! RTL_CONST_CALL_P (insn
)))
3243 /* Mark REG as having no known equivalence.
3244 Some instructions might have been processed before and furnished
3245 with REG_EQUIV notes for this register; these notes will have to be
3247 STORE is the piece of RTL that does the non-constant / conflicting
3248 assignment - a SET, CLOBBER or REG_INC note. It is currently not used,
3249 but needs to be there because this function is called from note_stores. */
3251 no_equiv (rtx reg
, const_rtx store ATTRIBUTE_UNUSED
,
3252 void *data ATTRIBUTE_UNUSED
)
3255 rtx_insn_list
*list
;
3259 regno
= REGNO (reg
);
3260 reg_equiv
[regno
].no_equiv
= 1;
3261 list
= reg_equiv
[regno
].init_insns
;
3262 if (list
&& list
->insn () == NULL
)
3264 reg_equiv
[regno
].init_insns
= gen_rtx_INSN_LIST (VOIDmode
, NULL_RTX
, NULL
);
3265 reg_equiv
[regno
].replacement
= NULL_RTX
;
3266 /* This doesn't matter for equivalences made for argument registers, we
3267 should keep their initialization insns. */
3268 if (reg_equiv
[regno
].is_arg_equivalence
)
3270 ira_reg_equiv
[regno
].defined_p
= false;
3271 ira_reg_equiv
[regno
].init_insns
= NULL
;
3272 for (; list
; list
= list
->next ())
3274 rtx_insn
*insn
= list
->insn ();
3275 remove_note (insn
, find_reg_note (insn
, REG_EQUIV
, NULL_RTX
));
3279 /* Check whether the SUBREG is a paradoxical subreg and set the result
3283 set_paradoxical_subreg (rtx_insn
*insn
, bool *pdx_subregs
)
3285 subrtx_iterator::array_type array
;
3286 FOR_EACH_SUBRTX (iter
, array
, PATTERN (insn
), NONCONST
)
3288 const_rtx subreg
= *iter
;
3289 if (GET_CODE (subreg
) == SUBREG
)
3291 const_rtx reg
= SUBREG_REG (subreg
);
3292 if (REG_P (reg
) && paradoxical_subreg_p (subreg
))
3293 pdx_subregs
[REGNO (reg
)] = true;
3298 /* In DEBUG_INSN location adjust REGs from CLEARED_REGS bitmap to the
3299 equivalent replacement. */
3302 adjust_cleared_regs (rtx loc
, const_rtx old_rtx ATTRIBUTE_UNUSED
, void *data
)
3306 bitmap cleared_regs
= (bitmap
) data
;
3307 if (bitmap_bit_p (cleared_regs
, REGNO (loc
)))
3308 return simplify_replace_fn_rtx (copy_rtx (*reg_equiv
[REGNO (loc
)].src_p
),
3309 NULL_RTX
, adjust_cleared_regs
, data
);
3314 /* Nonzero if we recorded an equivalence for a LABEL_REF. */
3315 static int recorded_label_ref
;
3317 /* Find registers that are equivalent to a single value throughout the
3318 compilation (either because they can be referenced in memory or are
3319 set once from a single constant). Lower their priority for a
3322 If such a register is only referenced once, try substituting its
3323 value into the using insn. If it succeeds, we can eliminate the
3324 register completely.
3326 Initialize init_insns in ira_reg_equiv array.
3328 Return non-zero if jump label rebuilding should be done. */
3330 update_equiv_regs (void)
3335 bitmap cleared_regs
;
3338 /* We need to keep track of whether or not we recorded a LABEL_REF so
3339 that we know if the jump optimizer needs to be rerun. */
3340 recorded_label_ref
= 0;
3342 /* Use pdx_subregs to show whether a reg is used in a paradoxical
3344 pdx_subregs
= XCNEWVEC (bool, max_regno
);
3346 reg_equiv
= XCNEWVEC (struct equivalence
, max_regno
);
3349 init_alias_analysis ();
3351 /* Scan insns and set pdx_subregs[regno] if the reg is used in a
3352 paradoxical subreg. Don't set such reg equivalent to a mem,
3353 because lra will not substitute such equiv memory in order to
3354 prevent access beyond allocated memory for paradoxical memory subreg. */
3355 FOR_EACH_BB_FN (bb
, cfun
)
3356 FOR_BB_INSNS (bb
, insn
)
3357 if (NONDEBUG_INSN_P (insn
))
3358 set_paradoxical_subreg (insn
, pdx_subregs
);
3360 /* Scan the insns and find which registers have equivalences. Do this
3361 in a separate scan of the insns because (due to -fcse-follow-jumps)
3362 a register can be set below its use. */
3363 FOR_EACH_BB_FN (bb
, cfun
)
3365 loop_depth
= bb_loop_depth (bb
);
3367 for (insn
= BB_HEAD (bb
);
3368 insn
!= NEXT_INSN (BB_END (bb
));
3369 insn
= NEXT_INSN (insn
))
3376 if (! INSN_P (insn
))
3379 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
3380 if (REG_NOTE_KIND (note
) == REG_INC
)
3381 no_equiv (XEXP (note
, 0), note
, NULL
);
3383 set
= single_set (insn
);
3385 /* If this insn contains more (or less) than a single SET,
3386 only mark all destinations as having no known equivalence. */
3387 if (set
== NULL_RTX
)
3389 note_stores (PATTERN (insn
), no_equiv
, NULL
);
3392 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
3396 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
3398 rtx part
= XVECEXP (PATTERN (insn
), 0, i
);
3400 note_stores (part
, no_equiv
, NULL
);
3404 dest
= SET_DEST (set
);
3405 src
= SET_SRC (set
);
3407 /* See if this is setting up the equivalence between an argument
3408 register and its stack slot. */
3409 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
3412 gcc_assert (REG_P (dest
));
3413 regno
= REGNO (dest
);
3415 /* Note that we don't want to clear init_insns in
3416 ira_reg_equiv even if there are multiple sets of this
3418 reg_equiv
[regno
].is_arg_equivalence
= 1;
3420 /* The insn result can have equivalence memory although
3421 the equivalence is not set up by the insn. We add
3422 this insn to init insns as it is a flag for now that
3423 regno has an equivalence. We will remove the insn
3424 from init insn list later. */
3425 if (rtx_equal_p (src
, XEXP (note
, 0)) || MEM_P (XEXP (note
, 0)))
3426 ira_reg_equiv
[regno
].init_insns
3427 = gen_rtx_INSN_LIST (VOIDmode
, insn
,
3428 ira_reg_equiv
[regno
].init_insns
);
3430 /* Continue normally in case this is a candidate for
3437 /* We only handle the case of a pseudo register being set
3438 once, or always to the same value. */
3439 /* ??? The mn10200 port breaks if we add equivalences for
3440 values that need an ADDRESS_REGS register and set them equivalent
3441 to a MEM of a pseudo. The actual problem is in the over-conservative
3442 handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
3443 calculate_needs, but we traditionally work around this problem
3444 here by rejecting equivalences when the destination is in a register
3445 that's likely spilled. This is fragile, of course, since the
3446 preferred class of a pseudo depends on all instructions that set
3450 || (regno
= REGNO (dest
)) < FIRST_PSEUDO_REGISTER
3451 || (reg_equiv
[regno
].init_insns
3452 && reg_equiv
[regno
].init_insns
->insn () == NULL
)
3453 || (targetm
.class_likely_spilled_p (reg_preferred_class (regno
))
3454 && MEM_P (src
) && ! reg_equiv
[regno
].is_arg_equivalence
))
3456 /* This might be setting a SUBREG of a pseudo, a pseudo that is
3457 also set somewhere else to a constant. */
3458 note_stores (set
, no_equiv
, NULL
);
3462 /* Don't set reg (if pdx_subregs[regno] == true) equivalent to a mem. */
3463 if (MEM_P (src
) && pdx_subregs
[regno
])
3465 note_stores (set
, no_equiv
, NULL
);
3469 note
= find_reg_note (insn
, REG_EQUAL
, NULL_RTX
);
3471 /* cse sometimes generates function invariants, but doesn't put a
3472 REG_EQUAL note on the insn. Since this note would be redundant,
3473 there's no point creating it earlier than here. */
3474 if (! note
&& ! rtx_varies_p (src
, 0))
3475 note
= set_unique_reg_note (insn
, REG_EQUAL
, copy_rtx (src
));
3477 /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
3478 since it represents a function call. */
3479 if (note
&& GET_CODE (XEXP (note
, 0)) == EXPR_LIST
)
3482 if (DF_REG_DEF_COUNT (regno
) != 1)
3484 bool equal_p
= true;
3485 rtx_insn_list
*list
;
3487 /* If we have already processed this pseudo and determined it
3488 can not have an equivalence, then honor that decision. */
3489 if (reg_equiv
[regno
].no_equiv
)
3493 || rtx_varies_p (XEXP (note
, 0), 0)
3494 || (reg_equiv
[regno
].replacement
3495 && ! rtx_equal_p (XEXP (note
, 0),
3496 reg_equiv
[regno
].replacement
)))
3498 no_equiv (dest
, set
, NULL
);
3502 list
= reg_equiv
[regno
].init_insns
;
3503 for (; list
; list
= list
->next ())
3508 insn_tmp
= list
->insn ();
3509 note_tmp
= find_reg_note (insn_tmp
, REG_EQUAL
, NULL_RTX
);
3510 gcc_assert (note_tmp
);
3511 if (! rtx_equal_p (XEXP (note
, 0), XEXP (note_tmp
, 0)))
3520 no_equiv (dest
, set
, NULL
);
3525 /* Record this insn as initializing this register. */
3526 reg_equiv
[regno
].init_insns
3527 = gen_rtx_INSN_LIST (VOIDmode
, insn
, reg_equiv
[regno
].init_insns
);
3529 /* If this register is known to be equal to a constant, record that
3530 it is always equivalent to the constant. */
3531 if (DF_REG_DEF_COUNT (regno
) == 1
3532 && note
&& ! rtx_varies_p (XEXP (note
, 0), 0))
3534 rtx note_value
= XEXP (note
, 0);
3535 remove_note (insn
, note
);
3536 set_unique_reg_note (insn
, REG_EQUIV
, note_value
);
3539 /* If this insn introduces a "constant" register, decrease the priority
3540 of that register. Record this insn if the register is only used once
3541 more and the equivalence value is the same as our source.
3543 The latter condition is checked for two reasons: First, it is an
3544 indication that it may be more efficient to actually emit the insn
3545 as written (if no registers are available, reload will substitute
3546 the equivalence). Secondly, it avoids problems with any registers
3547 dying in this insn whose death notes would be missed.
3549 If we don't have a REG_EQUIV note, see if this insn is loading
3550 a register used only in one basic block from a MEM. If so, and the
3551 MEM remains unchanged for the life of the register, add a REG_EQUIV
3553 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
3555 if (note
== NULL_RTX
&& REG_BASIC_BLOCK (regno
) >= NUM_FIXED_BLOCKS
3556 && MEM_P (SET_SRC (set
))
3557 && validate_equiv_mem (insn
, dest
, SET_SRC (set
)))
3558 note
= set_unique_reg_note (insn
, REG_EQUIV
, copy_rtx (SET_SRC (set
)));
3562 int regno
= REGNO (dest
);
3563 rtx x
= XEXP (note
, 0);
3565 /* If we haven't done so, record for reload that this is an
3566 equivalencing insn. */
3567 if (!reg_equiv
[regno
].is_arg_equivalence
)
3568 ira_reg_equiv
[regno
].init_insns
3569 = gen_rtx_INSN_LIST (VOIDmode
, insn
,
3570 ira_reg_equiv
[regno
].init_insns
);
3572 /* Record whether or not we created a REG_EQUIV note for a LABEL_REF.
3573 We might end up substituting the LABEL_REF for uses of the
3574 pseudo here or later. That kind of transformation may turn an
3575 indirect jump into a direct jump, in which case we must rerun the
3576 jump optimizer to ensure that the JUMP_LABEL fields are valid. */
3577 if (GET_CODE (x
) == LABEL_REF
3578 || (GET_CODE (x
) == CONST
3579 && GET_CODE (XEXP (x
, 0)) == PLUS
3580 && (GET_CODE (XEXP (XEXP (x
, 0), 0)) == LABEL_REF
)))
3581 recorded_label_ref
= 1;
3583 reg_equiv
[regno
].replacement
= x
;
3584 reg_equiv
[regno
].src_p
= &SET_SRC (set
);
3585 reg_equiv
[regno
].loop_depth
= (short) loop_depth
;
3587 /* Don't mess with things live during setjmp. */
3588 if (REG_LIVE_LENGTH (regno
) >= 0 && optimize
)
3590 /* Note that the statement below does not affect the priority
3592 REG_LIVE_LENGTH (regno
) *= 2;
3594 /* If the register is referenced exactly twice, meaning it is
3595 set once and used once, indicate that the reference may be
3596 replaced by the equivalence we computed above. Do this
3597 even if the register is only used in one block so that
3598 dependencies can be handled where the last register is
3599 used in a different block (i.e. HIGH / LO_SUM sequences)
3600 and to reduce the number of registers alive across
3603 if (REG_N_REFS (regno
) == 2
3604 && (rtx_equal_p (x
, src
)
3605 || ! equiv_init_varies_p (src
))
3606 && NONJUMP_INSN_P (insn
)
3607 && equiv_init_movable_p (PATTERN (insn
), regno
))
3608 reg_equiv
[regno
].replace
= 1;
3617 /* A second pass, to gather additional equivalences with memory. This needs
3618 to be done after we know which registers we are going to replace. */
3620 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
3625 if (! INSN_P (insn
))
3628 set
= single_set (insn
);
3632 dest
= SET_DEST (set
);
3633 src
= SET_SRC (set
);
3635 /* If this sets a MEM to the contents of a REG that is only used
3636 in a single basic block, see if the register is always equivalent
3637 to that memory location and if moving the store from INSN to the
3638 insn that set REG is safe. If so, put a REG_EQUIV note on the
3641 Don't add a REG_EQUIV note if the insn already has one. The existing
3642 REG_EQUIV is likely more useful than the one we are adding.
3644 If one of the regs in the address has reg_equiv[REGNO].replace set,
3645 then we can't add this REG_EQUIV note. The reg_equiv[REGNO].replace
3646 optimization may move the set of this register immediately before
3647 insn, which puts it after reg_equiv[REGNO].init_insns, and hence
3648 the mention in the REG_EQUIV note would be to an uninitialized
3651 if (MEM_P (dest
) && REG_P (src
)
3652 && (regno
= REGNO (src
)) >= FIRST_PSEUDO_REGISTER
3653 && REG_BASIC_BLOCK (regno
) >= NUM_FIXED_BLOCKS
3654 && DF_REG_DEF_COUNT (regno
) == 1
3655 && reg_equiv
[regno
].init_insns
!= NULL
3656 && reg_equiv
[regno
].init_insns
->insn () != NULL
3657 && ! find_reg_note (XEXP (reg_equiv
[regno
].init_insns
, 0),
3658 REG_EQUIV
, NULL_RTX
)
3659 && ! contains_replace_regs (XEXP (dest
, 0))
3660 && ! pdx_subregs
[regno
])
3662 rtx_insn
*init_insn
=
3663 as_a
<rtx_insn
*> (XEXP (reg_equiv
[regno
].init_insns
, 0));
3664 if (validate_equiv_mem (init_insn
, src
, dest
)
3665 && ! memref_used_between_p (dest
, init_insn
, insn
)
3666 /* Attaching a REG_EQUIV note will fail if INIT_INSN has
3668 && set_unique_reg_note (init_insn
, REG_EQUIV
, copy_rtx (dest
)))
3670 /* This insn makes the equivalence, not the one initializing
3672 ira_reg_equiv
[regno
].init_insns
3673 = gen_rtx_INSN_LIST (VOIDmode
, insn
, NULL_RTX
);
3674 df_notes_rescan (init_insn
);
3679 cleared_regs
= BITMAP_ALLOC (NULL
);
3680 /* Now scan all regs killed in an insn to see if any of them are
3681 registers only used that once. If so, see if we can replace the
3682 reference with the equivalent form. If we can, delete the
3683 initializing reference and this register will go away. If we
3684 can't replace the reference, and the initializing reference is
3685 within the same loop (or in an inner loop), then move the register
3686 initialization just before the use, so that they are in the same
3688 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
3690 loop_depth
= bb_loop_depth (bb
);
3691 for (insn
= BB_END (bb
);
3692 insn
!= PREV_INSN (BB_HEAD (bb
));
3693 insn
= PREV_INSN (insn
))
3697 if (! INSN_P (insn
))
3700 /* Don't substitute into a non-local goto, this confuses CFG. */
3702 && find_reg_note (insn
, REG_NON_LOCAL_GOTO
, NULL_RTX
))
3705 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
3707 if (REG_NOTE_KIND (link
) == REG_DEAD
3708 /* Make sure this insn still refers to the register. */
3709 && reg_mentioned_p (XEXP (link
, 0), PATTERN (insn
)))
3711 int regno
= REGNO (XEXP (link
, 0));
3714 if (! reg_equiv
[regno
].replace
3715 || reg_equiv
[regno
].loop_depth
< (short) loop_depth
3716 /* There is no sense to move insns if live range
3717 shrinkage or register pressure-sensitive
3718 scheduling were done because it will not
3719 improve allocation but worsen insn schedule
3720 with a big probability. */
3721 || flag_live_range_shrinkage
3722 || (flag_sched_pressure
&& flag_schedule_insns
))
3725 /* reg_equiv[REGNO].replace gets set only when
3726 REG_N_REFS[REGNO] is 2, i.e. the register is set
3727 once and used once. (If it were only set, but
3728 not used, flow would have deleted the setting
3729 insns.) Hence there can only be one insn in
3730 reg_equiv[REGNO].init_insns. */
3731 gcc_assert (reg_equiv
[regno
].init_insns
3732 && !XEXP (reg_equiv
[regno
].init_insns
, 1));
3733 equiv_insn
= XEXP (reg_equiv
[regno
].init_insns
, 0);
3735 /* We may not move instructions that can throw, since
3736 that changes basic block boundaries and we are not
3737 prepared to adjust the CFG to match. */
3738 if (can_throw_internal (equiv_insn
))
3741 if (asm_noperands (PATTERN (equiv_insn
)) < 0
3742 && validate_replace_rtx (regno_reg_rtx
[regno
],
3743 *(reg_equiv
[regno
].src_p
), insn
))
3749 /* Find the last note. */
3750 for (last_link
= link
; XEXP (last_link
, 1);
3751 last_link
= XEXP (last_link
, 1))
3754 /* Append the REG_DEAD notes from equiv_insn. */
3755 equiv_link
= REG_NOTES (equiv_insn
);
3759 equiv_link
= XEXP (equiv_link
, 1);
3760 if (REG_NOTE_KIND (note
) == REG_DEAD
)
3762 remove_note (equiv_insn
, note
);
3763 XEXP (last_link
, 1) = note
;
3764 XEXP (note
, 1) = NULL_RTX
;
3769 remove_death (regno
, insn
);
3770 SET_REG_N_REFS (regno
, 0);
3771 REG_FREQ (regno
) = 0;
3772 delete_insn (equiv_insn
);
3774 reg_equiv
[regno
].init_insns
3775 = reg_equiv
[regno
].init_insns
->next ();
3777 ira_reg_equiv
[regno
].init_insns
= NULL
;
3778 bitmap_set_bit (cleared_regs
, regno
);
3780 /* Move the initialization of the register to just before
3781 INSN. Update the flow information. */
3782 else if (prev_nondebug_insn (insn
) != equiv_insn
)
3786 new_insn
= emit_insn_before (PATTERN (equiv_insn
), insn
);
3787 REG_NOTES (new_insn
) = REG_NOTES (equiv_insn
);
3788 REG_NOTES (equiv_insn
) = 0;
3789 /* Rescan it to process the notes. */
3790 df_insn_rescan (new_insn
);
3792 /* Make sure this insn is recognized before
3793 reload begins, otherwise
3794 eliminate_regs_in_insn will die. */
3795 INSN_CODE (new_insn
) = INSN_CODE (equiv_insn
);
3797 delete_insn (equiv_insn
);
3799 XEXP (reg_equiv
[regno
].init_insns
, 0) = new_insn
;
3801 REG_BASIC_BLOCK (regno
) = bb
->index
;
3802 REG_N_CALLS_CROSSED (regno
) = 0;
3803 REG_FREQ_CALLS_CROSSED (regno
) = 0;
3804 REG_N_THROWING_CALLS_CROSSED (regno
) = 0;
3805 REG_LIVE_LENGTH (regno
) = 2;
3807 if (insn
== BB_HEAD (bb
))
3808 BB_HEAD (bb
) = PREV_INSN (insn
);
3810 ira_reg_equiv
[regno
].init_insns
3811 = gen_rtx_INSN_LIST (VOIDmode
, new_insn
, NULL_RTX
);
3812 bitmap_set_bit (cleared_regs
, regno
);
3819 if (!bitmap_empty_p (cleared_regs
))
3821 FOR_EACH_BB_FN (bb
, cfun
)
3823 bitmap_and_compl_into (DF_LR_IN (bb
), cleared_regs
);
3824 bitmap_and_compl_into (DF_LR_OUT (bb
), cleared_regs
);
3827 bitmap_and_compl_into (DF_LIVE_IN (bb
), cleared_regs
);
3828 bitmap_and_compl_into (DF_LIVE_OUT (bb
), cleared_regs
);
3831 /* Last pass - adjust debug insns referencing cleared regs. */
3832 if (MAY_HAVE_DEBUG_INSNS
)
3833 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
3834 if (DEBUG_INSN_P (insn
))
3836 rtx old_loc
= INSN_VAR_LOCATION_LOC (insn
);
3837 INSN_VAR_LOCATION_LOC (insn
)
3838 = simplify_replace_fn_rtx (old_loc
, NULL_RTX
,
3839 adjust_cleared_regs
,
3840 (void *) cleared_regs
);
3841 if (old_loc
!= INSN_VAR_LOCATION_LOC (insn
))
3842 df_insn_rescan (insn
);
3846 BITMAP_FREE (cleared_regs
);
3851 end_alias_analysis ();
3854 return recorded_label_ref
;
3859 /* Set up fields memory, constant, and invariant from init_insns in
3860 the structures of array ira_reg_equiv. */
3862 setup_reg_equiv (void)
3865 rtx_insn_list
*elem
, *prev_elem
, *next_elem
;
3869 for (i
= FIRST_PSEUDO_REGISTER
; i
< ira_reg_equiv_len
; i
++)
3870 for (prev_elem
= NULL
, elem
= ira_reg_equiv
[i
].init_insns
;
3872 prev_elem
= elem
, elem
= next_elem
)
3874 next_elem
= elem
->next ();
3875 insn
= elem
->insn ();
3876 set
= single_set (insn
);
3878 /* Init insns can set up equivalence when the reg is a destination or
3879 a source (in this case the destination is memory). */
3880 if (set
!= 0 && (REG_P (SET_DEST (set
)) || REG_P (SET_SRC (set
))))
3882 if ((x
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
)) != NULL
)
3885 if (REG_P (SET_DEST (set
))
3886 && REGNO (SET_DEST (set
)) == (unsigned int) i
3887 && ! rtx_equal_p (SET_SRC (set
), x
) && MEM_P (x
))
3889 /* This insn reporting the equivalence but
3890 actually not setting it. Remove it from the
3892 if (prev_elem
== NULL
)
3893 ira_reg_equiv
[i
].init_insns
= next_elem
;
3895 XEXP (prev_elem
, 1) = next_elem
;
3899 else if (REG_P (SET_DEST (set
))
3900 && REGNO (SET_DEST (set
)) == (unsigned int) i
)
3904 gcc_assert (REG_P (SET_SRC (set
))
3905 && REGNO (SET_SRC (set
)) == (unsigned int) i
);
3908 if (! function_invariant_p (x
)
3910 /* A function invariant is often CONSTANT_P but may
3911 include a register. We promise to only pass
3912 CONSTANT_P objects to LEGITIMATE_PIC_OPERAND_P. */
3913 || (CONSTANT_P (x
) && LEGITIMATE_PIC_OPERAND_P (x
)))
3915 /* It can happen that a REG_EQUIV note contains a MEM
3916 that is not a legitimate memory operand. As later
3917 stages of reload assume that all addresses found in
3918 the lra_regno_equiv_* arrays were originally
3919 legitimate, we ignore such REG_EQUIV notes. */
3920 if (memory_operand (x
, VOIDmode
))
3922 ira_reg_equiv
[i
].defined_p
= true;
3923 ira_reg_equiv
[i
].memory
= x
;
3926 else if (function_invariant_p (x
))
3928 enum machine_mode mode
;
3930 mode
= GET_MODE (SET_DEST (set
));
3931 if (GET_CODE (x
) == PLUS
3932 || x
== frame_pointer_rtx
|| x
== arg_pointer_rtx
)
3933 /* This is PLUS of frame pointer and a constant,
3935 ira_reg_equiv
[i
].invariant
= x
;
3936 else if (targetm
.legitimate_constant_p (mode
, x
))
3937 ira_reg_equiv
[i
].constant
= x
;
3940 ira_reg_equiv
[i
].memory
= force_const_mem (mode
, x
);
3941 if (ira_reg_equiv
[i
].memory
== NULL_RTX
)
3943 ira_reg_equiv
[i
].defined_p
= false;
3944 ira_reg_equiv
[i
].init_insns
= NULL
;
3948 ira_reg_equiv
[i
].defined_p
= true;
3953 ira_reg_equiv
[i
].defined_p
= false;
3954 ira_reg_equiv
[i
].init_insns
= NULL
;
3961 /* Print chain C to FILE. */
3963 print_insn_chain (FILE *file
, struct insn_chain
*c
)
3965 fprintf (file
, "insn=%d, ", INSN_UID (c
->insn
));
3966 bitmap_print (file
, &c
->live_throughout
, "live_throughout: ", ", ");
3967 bitmap_print (file
, &c
->dead_or_set
, "dead_or_set: ", "\n");
3971 /* Print all reload_insn_chains to FILE. */
3973 print_insn_chains (FILE *file
)
3975 struct insn_chain
*c
;
3976 for (c
= reload_insn_chain
; c
; c
= c
->next
)
3977 print_insn_chain (file
, c
);
3980 /* Return true if pseudo REGNO should be added to set live_throughout
3981 or dead_or_set of the insn chains for reload consideration. */
3983 pseudo_for_reload_consideration_p (int regno
)
3985 /* Consider spilled pseudos too for IRA because they still have a
3986 chance to get hard-registers in the reload when IRA is used. */
3987 return (reg_renumber
[regno
] >= 0 || ira_conflicts_p
);
3990 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
3991 REG to the number of nregs, and INIT_VALUE to get the
3992 initialization. ALLOCNUM need not be the regno of REG. */
3994 init_live_subregs (bool init_value
, sbitmap
*live_subregs
,
3995 bitmap live_subregs_used
, int allocnum
, rtx reg
)
3997 unsigned int regno
= REGNO (SUBREG_REG (reg
));
3998 int size
= GET_MODE_SIZE (GET_MODE (regno_reg_rtx
[regno
]));
4000 gcc_assert (size
> 0);
4002 /* Been there, done that. */
4003 if (bitmap_bit_p (live_subregs_used
, allocnum
))
4006 /* Create a new one. */
4007 if (live_subregs
[allocnum
] == NULL
)
4008 live_subregs
[allocnum
] = sbitmap_alloc (size
);
4010 /* If the entire reg was live before blasting into subregs, we need
4011 to init all of the subregs to ones else init to 0. */
4013 bitmap_ones (live_subregs
[allocnum
]);
4015 bitmap_clear (live_subregs
[allocnum
]);
4017 bitmap_set_bit (live_subregs_used
, allocnum
);
4020 /* Walk the insns of the current function and build reload_insn_chain,
4021 and record register life information. */
4023 build_insn_chain (void)
4026 struct insn_chain
**p
= &reload_insn_chain
;
4028 struct insn_chain
*c
= NULL
;
4029 struct insn_chain
*next
= NULL
;
4030 bitmap live_relevant_regs
= BITMAP_ALLOC (NULL
);
4031 bitmap elim_regset
= BITMAP_ALLOC (NULL
);
4032 /* live_subregs is a vector used to keep accurate information about
4033 which hardregs are live in multiword pseudos. live_subregs and
4034 live_subregs_used are indexed by pseudo number. The live_subreg
4035 entry for a particular pseudo is only used if the corresponding
4036 element is non zero in live_subregs_used. The sbitmap size of
4037 live_subreg[allocno] is number of bytes that the pseudo can
4039 sbitmap
*live_subregs
= XCNEWVEC (sbitmap
, max_regno
);
4040 bitmap live_subregs_used
= BITMAP_ALLOC (NULL
);
4042 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
4043 if (TEST_HARD_REG_BIT (eliminable_regset
, i
))
4044 bitmap_set_bit (elim_regset
, i
);
4045 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
4050 CLEAR_REG_SET (live_relevant_regs
);
4051 bitmap_clear (live_subregs_used
);
4053 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb
), 0, i
, bi
)
4055 if (i
>= FIRST_PSEUDO_REGISTER
)
4057 bitmap_set_bit (live_relevant_regs
, i
);
4060 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb
),
4061 FIRST_PSEUDO_REGISTER
, i
, bi
)
4063 if (pseudo_for_reload_consideration_p (i
))
4064 bitmap_set_bit (live_relevant_regs
, i
);
4067 FOR_BB_INSNS_REVERSE (bb
, insn
)
4069 if (!NOTE_P (insn
) && !BARRIER_P (insn
))
4071 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
4074 c
= new_insn_chain ();
4081 c
->block
= bb
->index
;
4083 if (NONDEBUG_INSN_P (insn
))
4084 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
4086 unsigned int regno
= DF_REF_REGNO (def
);
4088 /* Ignore may clobbers because these are generated
4089 from calls. However, every other kind of def is
4090 added to dead_or_set. */
4091 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
4093 if (regno
< FIRST_PSEUDO_REGISTER
)
4095 if (!fixed_regs
[regno
])
4096 bitmap_set_bit (&c
->dead_or_set
, regno
);
4098 else if (pseudo_for_reload_consideration_p (regno
))
4099 bitmap_set_bit (&c
->dead_or_set
, regno
);
4102 if ((regno
< FIRST_PSEUDO_REGISTER
4103 || reg_renumber
[regno
] >= 0
4105 && (!DF_REF_FLAGS_IS_SET (def
, DF_REF_CONDITIONAL
)))
4107 rtx reg
= DF_REF_REG (def
);
4109 /* We can model subregs, but not if they are
4110 wrapped in ZERO_EXTRACTS. */
4111 if (GET_CODE (reg
) == SUBREG
4112 && !DF_REF_FLAGS_IS_SET (def
, DF_REF_ZERO_EXTRACT
))
4114 unsigned int start
= SUBREG_BYTE (reg
);
4115 unsigned int last
= start
4116 + GET_MODE_SIZE (GET_MODE (reg
));
4119 (bitmap_bit_p (live_relevant_regs
, regno
),
4120 live_subregs
, live_subregs_used
, regno
, reg
);
4122 if (!DF_REF_FLAGS_IS_SET
4123 (def
, DF_REF_STRICT_LOW_PART
))
4125 /* Expand the range to cover entire words.
4126 Bytes added here are "don't care". */
4128 = start
/ UNITS_PER_WORD
* UNITS_PER_WORD
;
4129 last
= ((last
+ UNITS_PER_WORD
- 1)
4130 / UNITS_PER_WORD
* UNITS_PER_WORD
);
4133 /* Ignore the paradoxical bits. */
4134 if (last
> SBITMAP_SIZE (live_subregs
[regno
]))
4135 last
= SBITMAP_SIZE (live_subregs
[regno
]);
4137 while (start
< last
)
4139 bitmap_clear_bit (live_subregs
[regno
], start
);
4143 if (bitmap_empty_p (live_subregs
[regno
]))
4145 bitmap_clear_bit (live_subregs_used
, regno
);
4146 bitmap_clear_bit (live_relevant_regs
, regno
);
4149 /* Set live_relevant_regs here because
4150 that bit has to be true to get us to
4151 look at the live_subregs fields. */
4152 bitmap_set_bit (live_relevant_regs
, regno
);
4156 /* DF_REF_PARTIAL is generated for
4157 subregs, STRICT_LOW_PART, and
4158 ZERO_EXTRACT. We handle the subreg
4159 case above so here we have to keep from
4160 modeling the def as a killing def. */
4161 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
))
4163 bitmap_clear_bit (live_subregs_used
, regno
);
4164 bitmap_clear_bit (live_relevant_regs
, regno
);
4170 bitmap_and_compl_into (live_relevant_regs
, elim_regset
);
4171 bitmap_copy (&c
->live_throughout
, live_relevant_regs
);
4173 if (NONDEBUG_INSN_P (insn
))
4174 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
4176 unsigned int regno
= DF_REF_REGNO (use
);
4177 rtx reg
= DF_REF_REG (use
);
4179 /* DF_REF_READ_WRITE on a use means that this use
4180 is fabricated from a def that is a partial set
4181 to a multiword reg. Here, we only model the
4182 subreg case that is not wrapped in ZERO_EXTRACT
4183 precisely so we do not need to look at the
4185 if (DF_REF_FLAGS_IS_SET (use
, DF_REF_READ_WRITE
)
4186 && !DF_REF_FLAGS_IS_SET (use
, DF_REF_ZERO_EXTRACT
)
4187 && DF_REF_FLAGS_IS_SET (use
, DF_REF_SUBREG
))
4190 /* Add the last use of each var to dead_or_set. */
4191 if (!bitmap_bit_p (live_relevant_regs
, regno
))
4193 if (regno
< FIRST_PSEUDO_REGISTER
)
4195 if (!fixed_regs
[regno
])
4196 bitmap_set_bit (&c
->dead_or_set
, regno
);
4198 else if (pseudo_for_reload_consideration_p (regno
))
4199 bitmap_set_bit (&c
->dead_or_set
, regno
);
4202 if (regno
< FIRST_PSEUDO_REGISTER
4203 || pseudo_for_reload_consideration_p (regno
))
4205 if (GET_CODE (reg
) == SUBREG
4206 && !DF_REF_FLAGS_IS_SET (use
,
4208 | DF_REF_ZERO_EXTRACT
))
4210 unsigned int start
= SUBREG_BYTE (reg
);
4211 unsigned int last
= start
4212 + GET_MODE_SIZE (GET_MODE (reg
));
4215 (bitmap_bit_p (live_relevant_regs
, regno
),
4216 live_subregs
, live_subregs_used
, regno
, reg
);
4218 /* Ignore the paradoxical bits. */
4219 if (last
> SBITMAP_SIZE (live_subregs
[regno
]))
4220 last
= SBITMAP_SIZE (live_subregs
[regno
]);
4222 while (start
< last
)
4224 bitmap_set_bit (live_subregs
[regno
], start
);
4229 /* Resetting the live_subregs_used is
4230 effectively saying do not use the subregs
4231 because we are reading the whole
4233 bitmap_clear_bit (live_subregs_used
, regno
);
4234 bitmap_set_bit (live_relevant_regs
, regno
);
4240 /* FIXME!! The following code is a disaster. Reload needs to see the
4241 labels and jump tables that are just hanging out in between
4242 the basic blocks. See pr33676. */
4243 insn
= BB_HEAD (bb
);
4245 /* Skip over the barriers and cruft. */
4246 while (insn
&& (BARRIER_P (insn
) || NOTE_P (insn
)
4247 || BLOCK_FOR_INSN (insn
) == bb
))
4248 insn
= PREV_INSN (insn
);
4250 /* While we add anything except barriers and notes, the focus is
4251 to get the labels and jump tables into the
4252 reload_insn_chain. */
4255 if (!NOTE_P (insn
) && !BARRIER_P (insn
))
4257 if (BLOCK_FOR_INSN (insn
))
4260 c
= new_insn_chain ();
4266 /* The block makes no sense here, but it is what the old
4268 c
->block
= bb
->index
;
4270 bitmap_copy (&c
->live_throughout
, live_relevant_regs
);
4272 insn
= PREV_INSN (insn
);
4276 reload_insn_chain
= c
;
4279 for (i
= 0; i
< (unsigned int) max_regno
; i
++)
4280 if (live_subregs
[i
] != NULL
)
4281 sbitmap_free (live_subregs
[i
]);
4282 free (live_subregs
);
4283 BITMAP_FREE (live_subregs_used
);
4284 BITMAP_FREE (live_relevant_regs
);
4285 BITMAP_FREE (elim_regset
);
4288 print_insn_chains (dump_file
);
4291 /* Examine the rtx found in *LOC, which is read or written to as determined
4292 by TYPE. Return false if we find a reason why an insn containing this
4293 rtx should not be moved (such as accesses to non-constant memory), true
4296 rtx_moveable_p (rtx
*loc
, enum op_type type
)
4300 enum rtx_code code
= GET_CODE (x
);
4303 code
= GET_CODE (x
);
4313 return type
== OP_IN
;
4319 if (x
== frame_pointer_rtx
)
4321 if (HARD_REGISTER_P (x
))
4327 if (type
== OP_IN
&& MEM_READONLY_P (x
))
4328 return rtx_moveable_p (&XEXP (x
, 0), OP_IN
);
4332 return (rtx_moveable_p (&SET_SRC (x
), OP_IN
)
4333 && rtx_moveable_p (&SET_DEST (x
), OP_OUT
));
4335 case STRICT_LOW_PART
:
4336 return rtx_moveable_p (&XEXP (x
, 0), OP_OUT
);
4340 return (rtx_moveable_p (&XEXP (x
, 0), type
)
4341 && rtx_moveable_p (&XEXP (x
, 1), OP_IN
)
4342 && rtx_moveable_p (&XEXP (x
, 2), OP_IN
));
4345 return rtx_moveable_p (&SET_DEST (x
), OP_OUT
);
4351 fmt
= GET_RTX_FORMAT (code
);
4352 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4356 if (!rtx_moveable_p (&XEXP (x
, i
), type
))
4359 else if (fmt
[i
] == 'E')
4360 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
4362 if (!rtx_moveable_p (&XVECEXP (x
, i
, j
), type
))
4369 /* A wrapper around dominated_by_p, which uses the information in UID_LUID
4370 to give dominance relationships between two insns I1 and I2. */
4372 insn_dominated_by_p (rtx i1
, rtx i2
, int *uid_luid
)
4374 basic_block bb1
= BLOCK_FOR_INSN (i1
);
4375 basic_block bb2
= BLOCK_FOR_INSN (i2
);
4378 return uid_luid
[INSN_UID (i2
)] < uid_luid
[INSN_UID (i1
)];
4379 return dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
);
4382 /* Record the range of register numbers added by find_moveable_pseudos. */
4383 int first_moveable_pseudo
, last_moveable_pseudo
;
4385 /* These two vectors hold data for every register added by
4386 find_movable_pseudos, with index 0 holding data for the
4387 first_moveable_pseudo. */
4388 /* The original home register. */
4389 static vec
<rtx
> pseudo_replaced_reg
;
4391 /* Look for instances where we have an instruction that is known to increase
4392 register pressure, and whose result is not used immediately. If it is
4393 possible to move the instruction downwards to just before its first use,
4394 split its lifetime into two ranges. We create a new pseudo to compute the
4395 value, and emit a move instruction just before the first use. If, after
4396 register allocation, the new pseudo remains unallocated, the function
4397 move_unallocated_pseudos then deletes the move instruction and places
4398 the computation just before the first use.
4400 Such a move is safe and profitable if all the input registers remain live
4401 and unchanged between the original computation and its first use. In such
4402 a situation, the computation is known to increase register pressure, and
4403 moving it is known to at least not worsen it.
4405 We restrict moves to only those cases where a register remains unallocated,
4406 in order to avoid interfering too much with the instruction schedule. As
4407 an exception, we may move insns which only modify their input register
4408 (typically induction variables), as this increases the freedom for our
4409 intended transformation, and does not limit the second instruction
4413 find_moveable_pseudos (void)
4416 int max_regs
= max_reg_num ();
4417 int max_uid
= get_max_uid ();
4419 int *uid_luid
= XNEWVEC (int, max_uid
);
4420 rtx_insn
**closest_uses
= XNEWVEC (rtx_insn
*, max_regs
);
4421 /* A set of registers which are live but not modified throughout a block. */
4422 bitmap_head
*bb_transp_live
= XNEWVEC (bitmap_head
,
4423 last_basic_block_for_fn (cfun
));
4424 /* A set of registers which only exist in a given basic block. */
4425 bitmap_head
*bb_local
= XNEWVEC (bitmap_head
,
4426 last_basic_block_for_fn (cfun
));
4427 /* A set of registers which are set once, in an instruction that can be
4428 moved freely downwards, but are otherwise transparent to a block. */
4429 bitmap_head
*bb_moveable_reg_sets
= XNEWVEC (bitmap_head
,
4430 last_basic_block_for_fn (cfun
));
4431 bitmap_head live
, used
, set
, interesting
, unusable_as_input
;
4433 bitmap_initialize (&interesting
, 0);
4435 first_moveable_pseudo
= max_regs
;
4436 pseudo_replaced_reg
.release ();
4437 pseudo_replaced_reg
.safe_grow_cleared (max_regs
);
4440 calculate_dominance_info (CDI_DOMINATORS
);
4443 bitmap_initialize (&live
, 0);
4444 bitmap_initialize (&used
, 0);
4445 bitmap_initialize (&set
, 0);
4446 bitmap_initialize (&unusable_as_input
, 0);
4447 FOR_EACH_BB_FN (bb
, cfun
)
4450 bitmap transp
= bb_transp_live
+ bb
->index
;
4451 bitmap moveable
= bb_moveable_reg_sets
+ bb
->index
;
4452 bitmap local
= bb_local
+ bb
->index
;
4454 bitmap_initialize (local
, 0);
4455 bitmap_initialize (transp
, 0);
4456 bitmap_initialize (moveable
, 0);
4457 bitmap_copy (&live
, df_get_live_out (bb
));
4458 bitmap_and_into (&live
, df_get_live_in (bb
));
4459 bitmap_copy (transp
, &live
);
4460 bitmap_clear (moveable
);
4461 bitmap_clear (&live
);
4462 bitmap_clear (&used
);
4463 bitmap_clear (&set
);
4464 FOR_BB_INSNS (bb
, insn
)
4465 if (NONDEBUG_INSN_P (insn
))
4467 df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
4470 uid_luid
[INSN_UID (insn
)] = i
++;
4472 def
= df_single_def (insn_info
);
4473 use
= df_single_use (insn_info
);
4476 && DF_REF_REGNO (use
) == DF_REF_REGNO (def
)
4477 && !bitmap_bit_p (&set
, DF_REF_REGNO (use
))
4478 && rtx_moveable_p (&PATTERN (insn
), OP_IN
))
4480 unsigned regno
= DF_REF_REGNO (use
);
4481 bitmap_set_bit (moveable
, regno
);
4482 bitmap_set_bit (&set
, regno
);
4483 bitmap_set_bit (&used
, regno
);
4484 bitmap_clear_bit (transp
, regno
);
4487 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
4489 unsigned regno
= DF_REF_REGNO (use
);
4490 bitmap_set_bit (&used
, regno
);
4491 if (bitmap_clear_bit (moveable
, regno
))
4492 bitmap_clear_bit (transp
, regno
);
4495 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
4497 unsigned regno
= DF_REF_REGNO (def
);
4498 bitmap_set_bit (&set
, regno
);
4499 bitmap_clear_bit (transp
, regno
);
4500 bitmap_clear_bit (moveable
, regno
);
4505 bitmap_clear (&live
);
4506 bitmap_clear (&used
);
4507 bitmap_clear (&set
);
4509 FOR_EACH_BB_FN (bb
, cfun
)
4511 bitmap local
= bb_local
+ bb
->index
;
4514 FOR_BB_INSNS (bb
, insn
)
4515 if (NONDEBUG_INSN_P (insn
))
4517 df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
4519 rtx closest_use
, note
;
4522 bool all_dominated
, all_local
;
4523 enum machine_mode mode
;
4525 def
= df_single_def (insn_info
);
4526 /* There must be exactly one def in this insn. */
4527 if (!def
|| !single_set (insn
))
4529 /* This must be the only definition of the reg. We also limit
4530 which modes we deal with so that we can assume we can generate
4531 move instructions. */
4532 regno
= DF_REF_REGNO (def
);
4533 mode
= GET_MODE (DF_REF_REG (def
));
4534 if (DF_REG_DEF_COUNT (regno
) != 1
4535 || !DF_REF_INSN_INFO (def
)
4536 || HARD_REGISTER_NUM_P (regno
)
4537 || DF_REG_EQ_USE_COUNT (regno
) > 0
4538 || (!INTEGRAL_MODE_P (mode
) && !FLOAT_MODE_P (mode
)))
4540 def_insn
= DF_REF_INSN (def
);
4542 for (note
= REG_NOTES (def_insn
); note
; note
= XEXP (note
, 1))
4543 if (REG_NOTE_KIND (note
) == REG_EQUIV
&& MEM_P (XEXP (note
, 0)))
4549 fprintf (dump_file
, "Ignoring reg %d, has equiv memory\n",
4551 bitmap_set_bit (&unusable_as_input
, regno
);
4555 use
= DF_REG_USE_CHAIN (regno
);
4556 all_dominated
= true;
4558 closest_use
= NULL_RTX
;
4559 for (; use
; use
= DF_REF_NEXT_REG (use
))
4562 if (!DF_REF_INSN_INFO (use
))
4564 all_dominated
= false;
4568 insn
= DF_REF_INSN (use
);
4569 if (DEBUG_INSN_P (insn
))
4571 if (BLOCK_FOR_INSN (insn
) != BLOCK_FOR_INSN (def_insn
))
4573 if (!insn_dominated_by_p (insn
, def_insn
, uid_luid
))
4574 all_dominated
= false;
4575 if (closest_use
!= insn
&& closest_use
!= const0_rtx
)
4577 if (closest_use
== NULL_RTX
)
4579 else if (insn_dominated_by_p (closest_use
, insn
, uid_luid
))
4581 else if (!insn_dominated_by_p (insn
, closest_use
, uid_luid
))
4582 closest_use
= const0_rtx
;
4588 fprintf (dump_file
, "Reg %d not all uses dominated by set\n",
4593 bitmap_set_bit (local
, regno
);
4594 if (closest_use
== const0_rtx
|| closest_use
== NULL
4595 || next_nonnote_nondebug_insn (def_insn
) == closest_use
)
4598 fprintf (dump_file
, "Reg %d uninteresting%s\n", regno
,
4599 closest_use
== const0_rtx
|| closest_use
== NULL
4600 ? " (no unique first use)" : "");
4604 if (reg_referenced_p (cc0_rtx
, PATTERN (closest_use
)))
4607 fprintf (dump_file
, "Reg %d: closest user uses cc0\n",
4612 bitmap_set_bit (&interesting
, regno
);
4613 /* If we get here, we know closest_use is a non-NULL insn
4614 (as opposed to const_0_rtx). */
4615 closest_uses
[regno
] = as_a
<rtx_insn
*> (closest_use
);
4617 if (dump_file
&& (all_local
|| all_dominated
))
4619 fprintf (dump_file
, "Reg %u:", regno
);
4621 fprintf (dump_file
, " local to bb %d", bb
->index
);
4623 fprintf (dump_file
, " def dominates all uses");
4624 if (closest_use
!= const0_rtx
)
4625 fprintf (dump_file
, " has unique first use");
4626 fputs ("\n", dump_file
);
4631 EXECUTE_IF_SET_IN_BITMAP (&interesting
, 0, i
, bi
)
4633 df_ref def
= DF_REG_DEF_CHAIN (i
);
4634 rtx_insn
*def_insn
= DF_REF_INSN (def
);
4635 basic_block def_block
= BLOCK_FOR_INSN (def_insn
);
4636 bitmap def_bb_local
= bb_local
+ def_block
->index
;
4637 bitmap def_bb_moveable
= bb_moveable_reg_sets
+ def_block
->index
;
4638 bitmap def_bb_transp
= bb_transp_live
+ def_block
->index
;
4639 bool local_to_bb_p
= bitmap_bit_p (def_bb_local
, i
);
4640 rtx_insn
*use_insn
= closest_uses
[i
];
4643 bool all_transp
= true;
4645 if (!REG_P (DF_REF_REG (def
)))
4651 fprintf (dump_file
, "Reg %u not local to one basic block\n",
4655 if (reg_equiv_init (i
) != NULL_RTX
)
4658 fprintf (dump_file
, "Ignoring reg %u with equiv init insn\n",
4662 if (!rtx_moveable_p (&PATTERN (def_insn
), OP_IN
))
4665 fprintf (dump_file
, "Found def insn %d for %d to be not moveable\n",
4666 INSN_UID (def_insn
), i
);
4670 fprintf (dump_file
, "Examining insn %d, def for %d\n",
4671 INSN_UID (def_insn
), i
);
4672 FOR_EACH_INSN_USE (use
, def_insn
)
4674 unsigned regno
= DF_REF_REGNO (use
);
4675 if (bitmap_bit_p (&unusable_as_input
, regno
))
4679 fprintf (dump_file
, " found unusable input reg %u.\n", regno
);
4682 if (!bitmap_bit_p (def_bb_transp
, regno
))
4684 if (bitmap_bit_p (def_bb_moveable
, regno
)
4685 && !control_flow_insn_p (use_insn
)
4687 && !sets_cc0_p (use_insn
)
4691 if (modified_between_p (DF_REF_REG (use
), def_insn
, use_insn
))
4693 rtx_insn
*x
= NEXT_INSN (def_insn
);
4694 while (!modified_in_p (DF_REF_REG (use
), x
))
4696 gcc_assert (x
!= use_insn
);
4700 fprintf (dump_file
, " input reg %u modified but insn %d moveable\n",
4701 regno
, INSN_UID (x
));
4702 emit_insn_after (PATTERN (x
), use_insn
);
4703 set_insn_deleted (x
);
4708 fprintf (dump_file
, " input reg %u modified between def and use\n",
4719 if (!dbg_cnt (ira_move
))
4722 fprintf (dump_file
, " all ok%s\n", all_transp
? " and transp" : "");
4726 rtx def_reg
= DF_REF_REG (def
);
4727 rtx newreg
= ira_create_new_reg (def_reg
);
4728 if (validate_change (def_insn
, DF_REF_REAL_LOC (def
), newreg
, 0))
4730 unsigned nregno
= REGNO (newreg
);
4731 emit_insn_before (gen_move_insn (def_reg
, newreg
), use_insn
);
4733 pseudo_replaced_reg
[nregno
] = def_reg
;
4738 FOR_EACH_BB_FN (bb
, cfun
)
4740 bitmap_clear (bb_local
+ bb
->index
);
4741 bitmap_clear (bb_transp_live
+ bb
->index
);
4742 bitmap_clear (bb_moveable_reg_sets
+ bb
->index
);
4744 bitmap_clear (&interesting
);
4745 bitmap_clear (&unusable_as_input
);
4747 free (closest_uses
);
4749 free (bb_transp_live
);
4750 free (bb_moveable_reg_sets
);
4752 last_moveable_pseudo
= max_reg_num ();
4754 fix_reg_equiv_init ();
4756 regstat_free_n_sets_and_refs ();
4758 regstat_init_n_sets_and_refs ();
4759 regstat_compute_ri ();
4760 free_dominance_info (CDI_DOMINATORS
);
4763 /* If SET pattern SET is an assignment from a hard register to a pseudo which
4764 is live at CALL_DOM (if non-NULL, otherwise this check is omitted), return
4765 the destination. Otherwise return NULL. */
4768 interesting_dest_for_shprep_1 (rtx set
, basic_block call_dom
)
4770 rtx src
= SET_SRC (set
);
4771 rtx dest
= SET_DEST (set
);
4772 if (!REG_P (src
) || !HARD_REGISTER_P (src
)
4773 || !REG_P (dest
) || HARD_REGISTER_P (dest
)
4774 || (call_dom
&& !bitmap_bit_p (df_get_live_in (call_dom
), REGNO (dest
))))
4779 /* If insn is interesting for parameter range-splitting shrink-wrapping
4780 preparation, i.e. it is a single set from a hard register to a pseudo, which
4781 is live at CALL_DOM (if non-NULL, otherwise this check is omitted), or a
4782 parallel statement with only one such statement, return the destination.
4783 Otherwise return NULL. */
4786 interesting_dest_for_shprep (rtx_insn
*insn
, basic_block call_dom
)
4790 rtx pat
= PATTERN (insn
);
4791 if (GET_CODE (pat
) == SET
)
4792 return interesting_dest_for_shprep_1 (pat
, call_dom
);
4794 if (GET_CODE (pat
) != PARALLEL
)
4797 for (int i
= 0; i
< XVECLEN (pat
, 0); i
++)
4799 rtx sub
= XVECEXP (pat
, 0, i
);
4800 if (GET_CODE (sub
) == USE
|| GET_CODE (sub
) == CLOBBER
)
4802 if (GET_CODE (sub
) != SET
4803 || side_effects_p (sub
))
4805 rtx dest
= interesting_dest_for_shprep_1 (sub
, call_dom
);
4814 /* Split live ranges of pseudos that are loaded from hard registers in the
4815 first BB in a BB that dominates all non-sibling call if such a BB can be
4816 found and is not in a loop. Return true if the function has made any
4820 split_live_ranges_for_shrink_wrap (void)
4822 basic_block bb
, call_dom
= NULL
;
4823 basic_block first
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
4824 rtx_insn
*insn
, *last_interesting_insn
= NULL
;
4825 bitmap_head need_new
, reachable
;
4826 vec
<basic_block
> queue
;
4828 if (!SHRINK_WRAPPING_ENABLED
)
4831 bitmap_initialize (&need_new
, 0);
4832 bitmap_initialize (&reachable
, 0);
4833 queue
.create (n_basic_blocks_for_fn (cfun
));
4835 FOR_EACH_BB_FN (bb
, cfun
)
4836 FOR_BB_INSNS (bb
, insn
)
4837 if (CALL_P (insn
) && !SIBLING_CALL_P (insn
))
4841 bitmap_clear (&need_new
);
4842 bitmap_clear (&reachable
);
4847 bitmap_set_bit (&need_new
, bb
->index
);
4848 bitmap_set_bit (&reachable
, bb
->index
);
4849 queue
.quick_push (bb
);
4853 if (queue
.is_empty ())
4855 bitmap_clear (&need_new
);
4856 bitmap_clear (&reachable
);
4861 while (!queue
.is_empty ())
4867 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4868 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
4869 && bitmap_set_bit (&reachable
, e
->dest
->index
))
4870 queue
.quick_push (e
->dest
);
4874 FOR_BB_INSNS (first
, insn
)
4876 rtx dest
= interesting_dest_for_shprep (insn
, NULL
);
4880 if (DF_REG_DEF_COUNT (REGNO (dest
)) > 1)
4882 bitmap_clear (&need_new
);
4883 bitmap_clear (&reachable
);
4887 for (df_ref use
= DF_REG_USE_CHAIN (REGNO(dest
));
4889 use
= DF_REF_NEXT_REG (use
))
4891 int ubbi
= DF_REF_BB (use
)->index
;
4892 if (bitmap_bit_p (&reachable
, ubbi
))
4893 bitmap_set_bit (&need_new
, ubbi
);
4895 last_interesting_insn
= insn
;
4898 bitmap_clear (&reachable
);
4899 if (!last_interesting_insn
)
4901 bitmap_clear (&need_new
);
4905 call_dom
= nearest_common_dominator_for_set (CDI_DOMINATORS
, &need_new
);
4906 bitmap_clear (&need_new
);
4907 if (call_dom
== first
)
4910 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
4911 while (bb_loop_depth (call_dom
) > 0)
4912 call_dom
= get_immediate_dominator (CDI_DOMINATORS
, call_dom
);
4913 loop_optimizer_finalize ();
4915 if (call_dom
== first
)
4918 calculate_dominance_info (CDI_POST_DOMINATORS
);
4919 if (dominated_by_p (CDI_POST_DOMINATORS
, first
, call_dom
))
4921 free_dominance_info (CDI_POST_DOMINATORS
);
4924 free_dominance_info (CDI_POST_DOMINATORS
);
4927 fprintf (dump_file
, "Will split live ranges of parameters at BB %i\n",
4931 FOR_BB_INSNS (first
, insn
)
4933 rtx dest
= interesting_dest_for_shprep (insn
, call_dom
);
4934 if (!dest
|| dest
== pic_offset_table_rtx
)
4937 rtx newreg
= NULL_RTX
;
4939 for (use
= DF_REG_USE_CHAIN (REGNO (dest
)); use
; use
= next
)
4941 rtx_insn
*uin
= DF_REF_INSN (use
);
4942 next
= DF_REF_NEXT_REG (use
);
4944 basic_block ubb
= BLOCK_FOR_INSN (uin
);
4946 || dominated_by_p (CDI_DOMINATORS
, ubb
, call_dom
))
4949 newreg
= ira_create_new_reg (dest
);
4950 validate_change (uin
, DF_REF_REAL_LOC (use
), newreg
, true);
4956 rtx new_move
= gen_move_insn (newreg
, dest
);
4957 emit_insn_after (new_move
, bb_note (call_dom
));
4960 fprintf (dump_file
, "Split live-range of register ");
4961 print_rtl_single (dump_file
, dest
);
4966 if (insn
== last_interesting_insn
)
4969 apply_change_group ();
4973 /* Perform the second half of the transformation started in
4974 find_moveable_pseudos. We look for instances where the newly introduced
4975 pseudo remains unallocated, and remove it by moving the definition to
4976 just before its use, replacing the move instruction generated by
4977 find_moveable_pseudos. */
4979 move_unallocated_pseudos (void)
4982 for (i
= first_moveable_pseudo
; i
< last_moveable_pseudo
; i
++)
4983 if (reg_renumber
[i
] < 0)
4985 int idx
= i
- first_moveable_pseudo
;
4986 rtx other_reg
= pseudo_replaced_reg
[idx
];
4987 rtx_insn
*def_insn
= DF_REF_INSN (DF_REG_DEF_CHAIN (i
));
4988 /* The use must follow all definitions of OTHER_REG, so we can
4989 insert the new definition immediately after any of them. */
4990 df_ref other_def
= DF_REG_DEF_CHAIN (REGNO (other_reg
));
4991 rtx_insn
*move_insn
= DF_REF_INSN (other_def
);
4992 rtx_insn
*newinsn
= emit_insn_after (PATTERN (def_insn
), move_insn
);
4997 fprintf (dump_file
, "moving def of %d (insn %d now) ",
4998 REGNO (other_reg
), INSN_UID (def_insn
));
5000 delete_insn (move_insn
);
5001 while ((other_def
= DF_REG_DEF_CHAIN (REGNO (other_reg
))))
5002 delete_insn (DF_REF_INSN (other_def
));
5003 delete_insn (def_insn
);
5005 set
= single_set (newinsn
);
5006 success
= validate_change (newinsn
, &SET_DEST (set
), other_reg
, 0);
5007 gcc_assert (success
);
5009 fprintf (dump_file
, " %d) rather than keep unallocated replacement %d\n",
5010 INSN_UID (newinsn
), i
);
5011 SET_REG_N_REFS (i
, 0);
5015 /* If the backend knows where to allocate pseudos for hard
5016 register initial values, register these allocations now. */
5018 allocate_initial_values (void)
5020 if (targetm
.allocate_initial_value
)
5025 for (i
= 0; HARD_REGISTER_NUM_P (i
); i
++)
5027 if (! initial_value_entry (i
, &hreg
, &preg
))
5030 x
= targetm
.allocate_initial_value (hreg
);
5031 regno
= REGNO (preg
);
5032 if (x
&& REG_N_SETS (regno
) <= 1)
5035 reg_equiv_memory_loc (regno
) = x
;
5041 gcc_assert (REG_P (x
));
5042 new_regno
= REGNO (x
);
5043 reg_renumber
[regno
] = new_regno
;
5044 /* Poke the regno right into regno_reg_rtx so that even
5045 fixed regs are accepted. */
5046 SET_REGNO (preg
, new_regno
);
5047 /* Update global register liveness information. */
5048 FOR_EACH_BB_FN (bb
, cfun
)
5050 if (REGNO_REG_SET_P (df_get_live_in (bb
), regno
))
5051 SET_REGNO_REG_SET (df_get_live_in (bb
), new_regno
);
5052 if (REGNO_REG_SET_P (df_get_live_out (bb
), regno
))
5053 SET_REGNO_REG_SET (df_get_live_out (bb
), new_regno
);
5059 gcc_checking_assert (! initial_value_entry (FIRST_PSEUDO_REGISTER
,
5065 /* True when we use LRA instead of reload pass for the current
5069 /* True if we have allocno conflicts. It is false for non-optimized
5070 mode or when the conflict table is too big. */
5071 bool ira_conflicts_p
;
5073 /* Saved between IRA and reload. */
5074 static int saved_flag_ira_share_spill_slots
;
5076 /* This is the main entry of IRA. */
5081 int ira_max_point_before_emit
;
5083 bool saved_flag_caller_saves
= flag_caller_saves
;
5084 enum ira_region saved_flag_ira_region
= flag_ira_region
;
5086 /* Perform target specific PIC register initialization. */
5087 targetm
.init_pic_reg ();
5089 ira_conflicts_p
= optimize
> 0;
5091 ira_use_lra_p
= targetm
.lra_p ();
5092 /* If there are too many pseudos and/or basic blocks (e.g. 10K
5093 pseudos and 10K blocks or 100K pseudos and 1K blocks), we will
5094 use simplified and faster algorithms in LRA. */
5097 && max_reg_num () >= (1 << 26) / last_basic_block_for_fn (cfun
));
5100 /* It permits to skip live range splitting in LRA. */
5101 flag_caller_saves
= false;
5102 /* There is no sense to do regional allocation when we use
5104 flag_ira_region
= IRA_REGION_ONE
;
5105 ira_conflicts_p
= false;
5108 #ifndef IRA_NO_OBSTACK
5109 gcc_obstack_init (&ira_obstack
);
5111 bitmap_obstack_initialize (&ira_bitmap_obstack
);
5113 /* LRA uses its own infrastructure to handle caller save registers. */
5114 if (flag_caller_saves
&& !ira_use_lra_p
)
5115 init_caller_save ();
5117 if (flag_ira_verbose
< 10)
5119 internal_flag_ira_verbose
= flag_ira_verbose
;
5124 internal_flag_ira_verbose
= flag_ira_verbose
- 10;
5125 ira_dump_file
= stderr
;
5128 setup_prohibited_mode_move_regs ();
5129 decrease_live_ranges_number ();
5130 df_note_add_problem ();
5132 /* DF_LIVE can't be used in the register allocator, too many other
5133 parts of the compiler depend on using the "classic" liveness
5134 interpretation of the DF_LR problem. See PR38711.
5135 Remove the problem, so that we don't spend time updating it in
5136 any of the df_analyze() calls during IRA/LRA. */
5138 df_remove_problem (df_live
);
5139 gcc_checking_assert (df_live
== NULL
);
5141 #ifdef ENABLE_CHECKING
5142 df
->changeable_flags
|= DF_VERIFY_SCHEDULED
;
5147 if (ira_conflicts_p
)
5149 calculate_dominance_info (CDI_DOMINATORS
);
5151 if (split_live_ranges_for_shrink_wrap ())
5154 free_dominance_info (CDI_DOMINATORS
);
5157 df_clear_flags (DF_NO_INSN_RESCAN
);
5159 regstat_init_n_sets_and_refs ();
5160 regstat_compute_ri ();
5162 /* If we are not optimizing, then this is the only place before
5163 register allocation where dataflow is done. And that is needed
5164 to generate these warnings. */
5166 generate_setjmp_warnings ();
5168 /* Determine if the current function is a leaf before running IRA
5169 since this can impact optimizations done by the prologue and
5170 epilogue thus changing register elimination offsets. */
5171 crtl
->is_leaf
= leaf_function_p ();
5173 if (resize_reg_info () && flag_ira_loop_pressure
)
5174 ira_set_pseudo_classes (true, ira_dump_file
);
5176 rebuild_p
= update_equiv_regs ();
5178 setup_reg_equiv_init ();
5180 if (optimize
&& rebuild_p
)
5182 timevar_push (TV_JUMP
);
5183 rebuild_jump_labels (get_insns ());
5184 if (purge_all_dead_edges ())
5185 delete_unreachable_blocks ();
5186 timevar_pop (TV_JUMP
);
5189 allocated_reg_info_size
= max_reg_num ();
5191 if (delete_trivially_dead_insns (get_insns (), max_reg_num ()))
5194 /* It is not worth to do such improvement when we use a simple
5195 allocation because of -O0 usage or because the function is too
5197 if (ira_conflicts_p
)
5198 find_moveable_pseudos ();
5200 max_regno_before_ira
= max_reg_num ();
5201 ira_setup_eliminable_regset ();
5203 ira_overall_cost
= ira_reg_cost
= ira_mem_cost
= 0;
5204 ira_load_cost
= ira_store_cost
= ira_shuffle_cost
= 0;
5205 ira_move_loops_num
= ira_additional_jumps_num
= 0;
5207 ira_assert (current_loops
== NULL
);
5208 if (flag_ira_region
== IRA_REGION_ALL
|| flag_ira_region
== IRA_REGION_MIXED
)
5209 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
| LOOPS_HAVE_RECORDED_EXITS
);
5211 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
5212 fprintf (ira_dump_file
, "Building IRA IR\n");
5213 loops_p
= ira_build ();
5215 ira_assert (ira_conflicts_p
|| !loops_p
);
5217 saved_flag_ira_share_spill_slots
= flag_ira_share_spill_slots
;
5218 if (too_high_register_pressure_p () || cfun
->calls_setjmp
)
5219 /* It is just wasting compiler's time to pack spilled pseudos into
5220 stack slots in this case -- prohibit it. We also do this if
5221 there is setjmp call because a variable not modified between
5222 setjmp and longjmp the compiler is required to preserve its
5223 value and sharing slots does not guarantee it. */
5224 flag_ira_share_spill_slots
= FALSE
;
5228 ira_max_point_before_emit
= ira_max_point
;
5230 ira_initiate_emit_data ();
5234 max_regno
= max_reg_num ();
5235 if (ira_conflicts_p
)
5239 if (! ira_use_lra_p
)
5240 ira_initiate_assign ();
5249 ira_allocno_iterator ai
;
5251 FOR_EACH_ALLOCNO (a
, ai
)
5252 ALLOCNO_REGNO (a
) = REGNO (ALLOCNO_EMIT_DATA (a
)->reg
);
5256 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
5257 fprintf (ira_dump_file
, "Flattening IR\n");
5258 ira_flattening (max_regno_before_ira
, ira_max_point_before_emit
);
5260 /* New insns were generated: add notes and recalculate live
5264 /* ??? Rebuild the loop tree, but why? Does the loop tree
5265 change if new insns were generated? Can that be handled
5266 by updating the loop tree incrementally? */
5267 loop_optimizer_finalize ();
5268 free_dominance_info (CDI_DOMINATORS
);
5269 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
5270 | LOOPS_HAVE_RECORDED_EXITS
);
5272 if (! ira_use_lra_p
)
5274 setup_allocno_assignment_flags ();
5275 ira_initiate_assign ();
5276 ira_reassign_conflict_allocnos (max_regno
);
5281 ira_finish_emit_data ();
5283 setup_reg_renumber ();
5285 calculate_allocation_cost ();
5287 #ifdef ENABLE_IRA_CHECKING
5288 if (ira_conflicts_p
)
5289 check_allocation ();
5292 if (max_regno
!= max_regno_before_ira
)
5294 regstat_free_n_sets_and_refs ();
5296 regstat_init_n_sets_and_refs ();
5297 regstat_compute_ri ();
5300 overall_cost_before
= ira_overall_cost
;
5301 if (! ira_conflicts_p
)
5305 fix_reg_equiv_init ();
5307 #ifdef ENABLE_IRA_CHECKING
5308 print_redundant_copies ();
5310 if (! ira_use_lra_p
)
5312 ira_spilled_reg_stack_slots_num
= 0;
5313 ira_spilled_reg_stack_slots
5314 = ((struct ira_spilled_reg_stack_slot
*)
5315 ira_allocate (max_regno
5316 * sizeof (struct ira_spilled_reg_stack_slot
)));
5317 memset (ira_spilled_reg_stack_slots
, 0,
5318 max_regno
* sizeof (struct ira_spilled_reg_stack_slot
));
5321 allocate_initial_values ();
5323 /* See comment for find_moveable_pseudos call. */
5324 if (ira_conflicts_p
)
5325 move_unallocated_pseudos ();
5327 /* Restore original values. */
5330 flag_caller_saves
= saved_flag_caller_saves
;
5331 flag_ira_region
= saved_flag_ira_region
;
5340 unsigned pic_offset_table_regno
= INVALID_REGNUM
;
5342 if (flag_ira_verbose
< 10)
5343 ira_dump_file
= dump_file
;
5345 /* If pic_offset_table_rtx is a pseudo register, then keep it so
5346 after reload to avoid possible wrong usages of hard reg assigned
5348 if (pic_offset_table_rtx
5349 && REGNO (pic_offset_table_rtx
) >= FIRST_PSEUDO_REGISTER
)
5350 pic_offset_table_regno
= REGNO (pic_offset_table_rtx
);
5352 timevar_push (TV_RELOAD
);
5355 if (current_loops
!= NULL
)
5357 loop_optimizer_finalize ();
5358 free_dominance_info (CDI_DOMINATORS
);
5360 FOR_ALL_BB_FN (bb
, cfun
)
5361 bb
->loop_father
= NULL
;
5362 current_loops
= NULL
;
5366 lra (ira_dump_file
);
5367 /* ???!!! Move it before lra () when we use ira_reg_equiv in
5369 vec_free (reg_equivs
);
5375 df_set_flags (DF_NO_INSN_RESCAN
);
5376 build_insn_chain ();
5378 need_dce
= reload (get_insns (), ira_conflicts_p
);
5382 timevar_pop (TV_RELOAD
);
5384 timevar_push (TV_IRA
);
5386 if (ira_conflicts_p
&& ! ira_use_lra_p
)
5388 ira_free (ira_spilled_reg_stack_slots
);
5389 ira_finish_assign ();
5392 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
5393 && overall_cost_before
!= ira_overall_cost
)
5394 fprintf (ira_dump_file
, "+++Overall after reload %d\n", ira_overall_cost
);
5396 flag_ira_share_spill_slots
= saved_flag_ira_share_spill_slots
;
5398 if (! ira_use_lra_p
)
5401 if (current_loops
!= NULL
)
5403 loop_optimizer_finalize ();
5404 free_dominance_info (CDI_DOMINATORS
);
5406 FOR_ALL_BB_FN (bb
, cfun
)
5407 bb
->loop_father
= NULL
;
5408 current_loops
= NULL
;
5411 regstat_free_n_sets_and_refs ();
5415 cleanup_cfg (CLEANUP_EXPENSIVE
);
5417 finish_reg_equiv ();
5419 bitmap_obstack_release (&ira_bitmap_obstack
);
5420 #ifndef IRA_NO_OBSTACK
5421 obstack_free (&ira_obstack
, NULL
);
5424 /* The code after the reload has changed so much that at this point
5425 we might as well just rescan everything. Note that
5426 df_rescan_all_insns is not going to help here because it does not
5427 touch the artificial uses and defs. */
5428 df_finish_pass (true);
5429 df_scan_alloc (NULL
);
5434 df_live_add_problem ();
5435 df_live_set_all_dirty ();
5441 if (need_dce
&& optimize
)
5444 /* Diagnose uses of the hard frame pointer when it is used as a global
5445 register. Often we can get away with letting the user appropriate
5446 the frame pointer, but we should let them know when code generation
5447 makes that impossible. */
5448 if (global_regs
[HARD_FRAME_POINTER_REGNUM
] && frame_pointer_needed
)
5450 tree decl
= global_regs_decl
[HARD_FRAME_POINTER_REGNUM
];
5451 error_at (DECL_SOURCE_LOCATION (current_function_decl
),
5452 "frame pointer required, but reserved");
5453 inform (DECL_SOURCE_LOCATION (decl
), "for %qD", decl
);
5456 if (pic_offset_table_regno
!= INVALID_REGNUM
)
5457 pic_offset_table_rtx
= gen_rtx_REG (Pmode
, pic_offset_table_regno
);
5459 timevar_pop (TV_IRA
);
5462 /* Run the integrated register allocator. */
5466 const pass_data pass_data_ira
=
5468 RTL_PASS
, /* type */
5470 OPTGROUP_NONE
, /* optinfo_flags */
5472 0, /* properties_required */
5473 0, /* properties_provided */
5474 0, /* properties_destroyed */
5475 0, /* todo_flags_start */
5476 TODO_do_not_ggc_collect
, /* todo_flags_finish */
5479 class pass_ira
: public rtl_opt_pass
5482 pass_ira (gcc::context
*ctxt
)
5483 : rtl_opt_pass (pass_data_ira
, ctxt
)
5486 /* opt_pass methods: */
5487 virtual unsigned int execute (function
*)
5493 }; // class pass_ira
5498 make_pass_ira (gcc::context
*ctxt
)
5500 return new pass_ira (ctxt
);
5505 const pass_data pass_data_reload
=
5507 RTL_PASS
, /* type */
5508 "reload", /* name */
5509 OPTGROUP_NONE
, /* optinfo_flags */
5510 TV_RELOAD
, /* tv_id */
5511 0, /* properties_required */
5512 0, /* properties_provided */
5513 0, /* properties_destroyed */
5514 0, /* todo_flags_start */
5515 0, /* todo_flags_finish */
5518 class pass_reload
: public rtl_opt_pass
5521 pass_reload (gcc::context
*ctxt
)
5522 : rtl_opt_pass (pass_data_reload
, ctxt
)
5525 /* opt_pass methods: */
5526 virtual unsigned int execute (function
*)
5532 }; // class pass_reload
5537 make_pass_reload (gcc::context
*ctxt
)
5539 return new pass_reload (ctxt
);