1 /* Integrated Register Allocator (IRA) entry point.
2 Copyright (C) 2006-2023 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.cc) 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.cc).
161 * IRA removes low register pressure loops from the regions
162 mostly to speed IRA up (file ira-build.cc).
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.cc).
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.cc). 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.cc). 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 cannot 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.cc). 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.cc). 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.cc). 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.cc 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.cc.
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"
374 #include "memmodel.h"
376 #include "insn-config.h"
380 #include "diagnostic-core.h"
382 #include "cfgbuild.h"
383 #include "cfgcleanup.h"
385 #include "tree-pass.h"
392 #include "rtl-iter.h"
393 #include "shrink-wrap.h"
394 #include "print-rtl.h"
396 struct target_ira default_target_ira
;
397 class target_ira_int default_target_ira_int
;
398 #if SWITCHABLE_TARGET
399 struct target_ira
*this_target_ira
= &default_target_ira
;
400 class target_ira_int
*this_target_ira_int
= &default_target_ira_int
;
403 /* A modified value of flag `-fira-verbose' used internally. */
404 int internal_flag_ira_verbose
;
406 /* Dump file of the allocator if it is not NULL. */
409 /* The number of elements in the following array. */
410 int ira_spilled_reg_stack_slots_num
;
412 /* The following array contains info about spilled pseudo-registers
413 stack slots used in current function so far. */
414 class ira_spilled_reg_stack_slot
*ira_spilled_reg_stack_slots
;
416 /* Correspondingly overall cost of the allocation, overall cost before
417 reload, cost of the allocnos assigned to hard-registers, cost of
418 the allocnos assigned to memory, cost of loads, stores and register
419 move insns generated for pseudo-register live range splitting (see
421 int64_t ira_overall_cost
, overall_cost_before
;
422 int64_t ira_reg_cost
, ira_mem_cost
;
423 int64_t ira_load_cost
, ira_store_cost
, ira_shuffle_cost
;
424 int ira_move_loops_num
, ira_additional_jumps_num
;
426 /* All registers that can be eliminated. */
428 HARD_REG_SET eliminable_regset
;
430 /* Value of max_reg_num () before IRA work start. This value helps
431 us to recognize a situation when new pseudos were created during
433 static int max_regno_before_ira
;
435 /* Temporary hard reg set used for a different calculation. */
436 static HARD_REG_SET temp_hard_regset
;
438 #define last_mode_for_init_move_cost \
439 (this_target_ira_int->x_last_mode_for_init_move_cost)
442 /* The function sets up the map IRA_REG_MODE_HARD_REGSET. */
444 setup_reg_mode_hard_regset (void)
446 int i
, m
, hard_regno
;
448 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
449 for (hard_regno
= 0; hard_regno
< FIRST_PSEUDO_REGISTER
; hard_regno
++)
451 CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset
[hard_regno
][m
]);
452 for (i
= hard_regno_nregs (hard_regno
, (machine_mode
) m
) - 1;
454 if (hard_regno
+ i
< FIRST_PSEUDO_REGISTER
)
455 SET_HARD_REG_BIT (ira_reg_mode_hard_regset
[hard_regno
][m
],
461 #define no_unit_alloc_regs \
462 (this_target_ira_int->x_no_unit_alloc_regs)
464 /* The function sets up the three arrays declared above. */
466 setup_class_hard_regs (void)
468 int cl
, i
, hard_regno
, n
;
469 HARD_REG_SET processed_hard_reg_set
;
471 ira_assert (SHRT_MAX
>= FIRST_PSEUDO_REGISTER
);
472 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
474 temp_hard_regset
= reg_class_contents
[cl
] & ~no_unit_alloc_regs
;
475 CLEAR_HARD_REG_SET (processed_hard_reg_set
);
476 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
478 ira_non_ordered_class_hard_regs
[cl
][i
] = -1;
479 ira_class_hard_reg_index
[cl
][i
] = -1;
481 for (n
= 0, i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
483 #ifdef REG_ALLOC_ORDER
484 hard_regno
= reg_alloc_order
[i
];
488 if (TEST_HARD_REG_BIT (processed_hard_reg_set
, hard_regno
))
490 SET_HARD_REG_BIT (processed_hard_reg_set
, hard_regno
);
491 if (! TEST_HARD_REG_BIT (temp_hard_regset
, hard_regno
))
492 ira_class_hard_reg_index
[cl
][hard_regno
] = -1;
495 ira_class_hard_reg_index
[cl
][hard_regno
] = n
;
496 ira_class_hard_regs
[cl
][n
++] = hard_regno
;
499 ira_class_hard_regs_num
[cl
] = n
;
500 for (n
= 0, i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
501 if (TEST_HARD_REG_BIT (temp_hard_regset
, i
))
502 ira_non_ordered_class_hard_regs
[cl
][n
++] = i
;
503 ira_assert (ira_class_hard_regs_num
[cl
] == n
);
507 /* Set up global variables defining info about hard registers for the
508 allocation. These depend on USE_HARD_FRAME_P whose TRUE value means
509 that we can use the hard frame pointer for the allocation. */
511 setup_alloc_regs (bool use_hard_frame_p
)
513 #ifdef ADJUST_REG_ALLOC_ORDER
514 ADJUST_REG_ALLOC_ORDER
;
516 no_unit_alloc_regs
= fixed_nonglobal_reg_set
;
517 if (! use_hard_frame_p
)
518 add_to_hard_reg_set (&no_unit_alloc_regs
, Pmode
,
519 HARD_FRAME_POINTER_REGNUM
);
520 setup_class_hard_regs ();
525 #define alloc_reg_class_subclasses \
526 (this_target_ira_int->x_alloc_reg_class_subclasses)
528 /* Initialize the table of subclasses of each reg class. */
530 setup_reg_subclasses (void)
533 HARD_REG_SET temp_hard_regset2
;
535 for (i
= 0; i
< N_REG_CLASSES
; i
++)
536 for (j
= 0; j
< N_REG_CLASSES
; j
++)
537 alloc_reg_class_subclasses
[i
][j
] = LIM_REG_CLASSES
;
539 for (i
= 0; i
< N_REG_CLASSES
; i
++)
541 if (i
== (int) NO_REGS
)
544 temp_hard_regset
= reg_class_contents
[i
] & ~no_unit_alloc_regs
;
545 if (hard_reg_set_empty_p (temp_hard_regset
))
547 for (j
= 0; j
< N_REG_CLASSES
; j
++)
552 temp_hard_regset2
= reg_class_contents
[j
] & ~no_unit_alloc_regs
;
553 if (! hard_reg_set_subset_p (temp_hard_regset
,
556 p
= &alloc_reg_class_subclasses
[j
][0];
557 while (*p
!= LIM_REG_CLASSES
) p
++;
558 *p
= (enum reg_class
) i
;
565 /* Set up IRA_MEMORY_MOVE_COST and IRA_MAX_MEMORY_MOVE_COST. */
567 setup_class_subset_and_memory_move_costs (void)
569 int cl
, cl2
, mode
, cost
;
570 HARD_REG_SET temp_hard_regset2
;
572 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
573 ira_memory_move_cost
[mode
][NO_REGS
][0]
574 = ira_memory_move_cost
[mode
][NO_REGS
][1] = SHRT_MAX
;
575 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
577 if (cl
!= (int) NO_REGS
)
578 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
580 ira_max_memory_move_cost
[mode
][cl
][0]
581 = ira_memory_move_cost
[mode
][cl
][0]
582 = memory_move_cost ((machine_mode
) mode
,
583 (reg_class_t
) cl
, false);
584 ira_max_memory_move_cost
[mode
][cl
][1]
585 = ira_memory_move_cost
[mode
][cl
][1]
586 = memory_move_cost ((machine_mode
) mode
,
587 (reg_class_t
) cl
, true);
588 /* Costs for NO_REGS are used in cost calculation on the
589 1st pass when the preferred register classes are not
590 known yet. In this case we take the best scenario. */
591 if (ira_memory_move_cost
[mode
][NO_REGS
][0]
592 > ira_memory_move_cost
[mode
][cl
][0])
593 ira_max_memory_move_cost
[mode
][NO_REGS
][0]
594 = ira_memory_move_cost
[mode
][NO_REGS
][0]
595 = ira_memory_move_cost
[mode
][cl
][0];
596 if (ira_memory_move_cost
[mode
][NO_REGS
][1]
597 > ira_memory_move_cost
[mode
][cl
][1])
598 ira_max_memory_move_cost
[mode
][NO_REGS
][1]
599 = ira_memory_move_cost
[mode
][NO_REGS
][1]
600 = ira_memory_move_cost
[mode
][cl
][1];
603 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
604 for (cl2
= (int) N_REG_CLASSES
- 1; cl2
>= 0; cl2
--)
606 temp_hard_regset
= reg_class_contents
[cl
] & ~no_unit_alloc_regs
;
607 temp_hard_regset2
= reg_class_contents
[cl2
] & ~no_unit_alloc_regs
;
608 ira_class_subset_p
[cl
][cl2
]
609 = hard_reg_set_subset_p (temp_hard_regset
, temp_hard_regset2
);
610 if (! hard_reg_set_empty_p (temp_hard_regset2
)
611 && hard_reg_set_subset_p (reg_class_contents
[cl2
],
612 reg_class_contents
[cl
]))
613 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
615 cost
= ira_memory_move_cost
[mode
][cl2
][0];
616 if (cost
> ira_max_memory_move_cost
[mode
][cl
][0])
617 ira_max_memory_move_cost
[mode
][cl
][0] = cost
;
618 cost
= ira_memory_move_cost
[mode
][cl2
][1];
619 if (cost
> ira_max_memory_move_cost
[mode
][cl
][1])
620 ira_max_memory_move_cost
[mode
][cl
][1] = cost
;
623 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
624 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
626 ira_memory_move_cost
[mode
][cl
][0]
627 = ira_max_memory_move_cost
[mode
][cl
][0];
628 ira_memory_move_cost
[mode
][cl
][1]
629 = ira_max_memory_move_cost
[mode
][cl
][1];
631 setup_reg_subclasses ();
636 /* Define the following macro if allocation through malloc if
638 #define IRA_NO_OBSTACK
640 #ifndef IRA_NO_OBSTACK
641 /* Obstack used for storing all dynamic data (except bitmaps) of the
643 static struct obstack ira_obstack
;
646 /* Obstack used for storing all bitmaps of the IRA. */
647 static struct bitmap_obstack ira_bitmap_obstack
;
649 /* Allocate memory of size LEN for IRA data. */
651 ira_allocate (size_t len
)
655 #ifndef IRA_NO_OBSTACK
656 res
= obstack_alloc (&ira_obstack
, len
);
663 /* Free memory ADDR allocated for IRA data. */
665 ira_free (void *addr ATTRIBUTE_UNUSED
)
667 #ifndef IRA_NO_OBSTACK
675 /* Allocate and returns bitmap for IRA. */
677 ira_allocate_bitmap (void)
679 return BITMAP_ALLOC (&ira_bitmap_obstack
);
682 /* Free bitmap B allocated for IRA. */
684 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED
)
691 /* Output information about allocation of all allocnos (except for
692 caps) into file F. */
694 ira_print_disposition (FILE *f
)
700 fprintf (f
, "Disposition:");
701 max_regno
= max_reg_num ();
702 for (n
= 0, i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
703 for (a
= ira_regno_allocno_map
[i
];
705 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
710 fprintf (f
, " %4d:r%-4d", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
711 if ((bb
= ALLOCNO_LOOP_TREE_NODE (a
)->bb
) != NULL
)
712 fprintf (f
, "b%-3d", bb
->index
);
714 fprintf (f
, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a
)->loop_num
);
715 if (ALLOCNO_HARD_REGNO (a
) >= 0)
716 fprintf (f
, " %3d", ALLOCNO_HARD_REGNO (a
));
723 /* Outputs information about allocation of all allocnos into
726 ira_debug_disposition (void)
728 ira_print_disposition (stderr
);
733 /* Set up ira_stack_reg_pressure_class which is the biggest pressure
734 register class containing stack registers or NO_REGS if there are
735 no stack registers. To find this class, we iterate through all
736 register pressure classes and choose the first register pressure
737 class containing all the stack registers and having the biggest
740 setup_stack_reg_pressure_class (void)
742 ira_stack_reg_pressure_class
= NO_REGS
;
747 HARD_REG_SET temp_hard_regset2
;
749 CLEAR_HARD_REG_SET (temp_hard_regset
);
750 for (i
= FIRST_STACK_REG
; i
<= LAST_STACK_REG
; i
++)
751 SET_HARD_REG_BIT (temp_hard_regset
, i
);
753 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
755 cl
= ira_pressure_classes
[i
];
756 temp_hard_regset2
= temp_hard_regset
& reg_class_contents
[cl
];
757 size
= hard_reg_set_size (temp_hard_regset2
);
761 ira_stack_reg_pressure_class
= cl
;
768 /* Find pressure classes which are register classes for which we
769 calculate register pressure in IRA, register pressure sensitive
770 insn scheduling, and register pressure sensitive loop invariant
773 To make register pressure calculation easy, we always use
774 non-intersected register pressure classes. A move of hard
775 registers from one register pressure class is not more expensive
776 than load and store of the hard registers. Most likely an allocno
777 class will be a subset of a register pressure class and in many
778 cases a register pressure class. That makes usage of register
779 pressure classes a good approximation to find a high register
782 setup_pressure_classes (void)
784 int cost
, i
, n
, curr
;
786 enum reg_class pressure_classes
[N_REG_CLASSES
];
788 HARD_REG_SET temp_hard_regset2
;
791 if (targetm
.compute_pressure_classes
)
792 n
= targetm
.compute_pressure_classes (pressure_classes
);
796 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
798 if (ira_class_hard_regs_num
[cl
] == 0)
800 if (ira_class_hard_regs_num
[cl
] != 1
801 /* A register class without subclasses may contain a few
802 hard registers and movement between them is costly
803 (e.g. SPARC FPCC registers). We still should consider it
804 as a candidate for a pressure class. */
805 && alloc_reg_class_subclasses
[cl
][0] < cl
)
807 /* Check that the moves between any hard registers of the
808 current class are not more expensive for a legal mode
809 than load/store of the hard registers of the current
810 class. Such class is a potential candidate to be a
811 register pressure class. */
812 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
815 = (reg_class_contents
[cl
]
816 & ~(no_unit_alloc_regs
817 | ira_prohibited_class_mode_regs
[cl
][m
]));
818 if (hard_reg_set_empty_p (temp_hard_regset
))
820 ira_init_register_move_cost_if_necessary ((machine_mode
) m
);
821 cost
= ira_register_move_cost
[m
][cl
][cl
];
822 if (cost
<= ira_max_memory_move_cost
[m
][cl
][1]
823 || cost
<= ira_max_memory_move_cost
[m
][cl
][0])
826 if (m
>= NUM_MACHINE_MODES
)
831 temp_hard_regset
= reg_class_contents
[cl
] & ~no_unit_alloc_regs
;
832 /* Remove so far added pressure classes which are subset of the
833 current candidate class. Prefer GENERAL_REGS as a pressure
834 register class to another class containing the same
835 allocatable hard registers. We do this because machine
836 dependent cost hooks might give wrong costs for the latter
837 class but always give the right cost for the former class
839 for (i
= 0; i
< n
; i
++)
841 cl2
= pressure_classes
[i
];
842 temp_hard_regset2
= (reg_class_contents
[cl2
]
843 & ~no_unit_alloc_regs
);
844 if (hard_reg_set_subset_p (temp_hard_regset
, temp_hard_regset2
)
845 && (temp_hard_regset
!= temp_hard_regset2
846 || cl2
== (int) GENERAL_REGS
))
848 pressure_classes
[curr
++] = (enum reg_class
) cl2
;
852 if (hard_reg_set_subset_p (temp_hard_regset2
, temp_hard_regset
)
853 && (temp_hard_regset2
!= temp_hard_regset
854 || cl
== (int) GENERAL_REGS
))
856 if (temp_hard_regset2
== temp_hard_regset
)
858 pressure_classes
[curr
++] = (enum reg_class
) cl2
;
860 /* If the current candidate is a subset of a so far added
861 pressure class, don't add it to the list of the pressure
864 pressure_classes
[curr
++] = (enum reg_class
) cl
;
868 #ifdef ENABLE_IRA_CHECKING
870 HARD_REG_SET ignore_hard_regs
;
872 /* Check pressure classes correctness: here we check that hard
873 registers from all register pressure classes contains all hard
874 registers available for the allocation. */
875 CLEAR_HARD_REG_SET (temp_hard_regset
);
876 CLEAR_HARD_REG_SET (temp_hard_regset2
);
877 ignore_hard_regs
= no_unit_alloc_regs
;
878 for (cl
= 0; cl
< LIM_REG_CLASSES
; cl
++)
880 /* For some targets (like MIPS with MD_REGS), there are some
881 classes with hard registers available for allocation but
882 not able to hold value of any mode. */
883 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
884 if (contains_reg_of_mode
[cl
][m
])
886 if (m
>= NUM_MACHINE_MODES
)
888 ignore_hard_regs
|= reg_class_contents
[cl
];
891 for (i
= 0; i
< n
; i
++)
892 if ((int) pressure_classes
[i
] == cl
)
894 temp_hard_regset2
|= reg_class_contents
[cl
];
896 temp_hard_regset
|= reg_class_contents
[cl
];
898 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
899 /* Some targets (like SPARC with ICC reg) have allocatable regs
900 for which no reg class is defined. */
901 if (REGNO_REG_CLASS (i
) == NO_REGS
)
902 SET_HARD_REG_BIT (ignore_hard_regs
, i
);
903 temp_hard_regset
&= ~ignore_hard_regs
;
904 temp_hard_regset2
&= ~ignore_hard_regs
;
905 ira_assert (hard_reg_set_subset_p (temp_hard_regset2
, temp_hard_regset
));
908 ira_pressure_classes_num
= 0;
909 for (i
= 0; i
< n
; i
++)
911 cl
= (int) pressure_classes
[i
];
912 ira_reg_pressure_class_p
[cl
] = true;
913 ira_pressure_classes
[ira_pressure_classes_num
++] = (enum reg_class
) cl
;
915 setup_stack_reg_pressure_class ();
918 /* Set up IRA_UNIFORM_CLASS_P. Uniform class is a register class
919 whose register move cost between any registers of the class is the
920 same as for all its subclasses. We use the data to speed up the
921 2nd pass of calculations of allocno costs. */
923 setup_uniform_class_p (void)
927 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
929 ira_uniform_class_p
[cl
] = false;
930 if (ira_class_hard_regs_num
[cl
] == 0)
932 /* We cannot use alloc_reg_class_subclasses here because move
933 cost hooks does not take into account that some registers are
934 unavailable for the subtarget. E.g. for i686, INT_SSE_REGS
935 is element of alloc_reg_class_subclasses for GENERAL_REGS
936 because SSE regs are unavailable. */
937 for (i
= 0; (cl2
= reg_class_subclasses
[cl
][i
]) != LIM_REG_CLASSES
; i
++)
939 if (ira_class_hard_regs_num
[cl2
] == 0)
941 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
942 if (contains_reg_of_mode
[cl
][m
] && contains_reg_of_mode
[cl2
][m
])
944 ira_init_register_move_cost_if_necessary ((machine_mode
) m
);
945 if (ira_register_move_cost
[m
][cl
][cl
]
946 != ira_register_move_cost
[m
][cl2
][cl2
])
949 if (m
< NUM_MACHINE_MODES
)
952 if (cl2
== LIM_REG_CLASSES
)
953 ira_uniform_class_p
[cl
] = true;
957 /* Set up IRA_ALLOCNO_CLASSES, IRA_ALLOCNO_CLASSES_NUM,
958 IRA_IMPORTANT_CLASSES, and IRA_IMPORTANT_CLASSES_NUM.
960 Target may have many subtargets and not all target hard registers can
961 be used for allocation, e.g. x86 port in 32-bit mode cannot use
962 hard registers introduced in x86-64 like r8-r15). Some classes
963 might have the same allocatable hard registers, e.g. INDEX_REGS
964 and GENERAL_REGS in x86 port in 32-bit mode. To decrease different
965 calculations efforts we introduce allocno classes which contain
966 unique non-empty sets of allocatable hard-registers.
968 Pseudo class cost calculation in ira-costs.cc is very expensive.
969 Therefore we are trying to decrease number of classes involved in
970 such calculation. Register classes used in the cost calculation
971 are called important classes. They are allocno classes and other
972 non-empty classes whose allocatable hard register sets are inside
973 of an allocno class hard register set. From the first sight, it
974 looks like that they are just allocno classes. It is not true. In
975 example of x86-port in 32-bit mode, allocno classes will contain
976 GENERAL_REGS but not LEGACY_REGS (because allocatable hard
977 registers are the same for the both classes). The important
978 classes will contain GENERAL_REGS and LEGACY_REGS. It is done
979 because a machine description insn constraint may refers for
980 LEGACY_REGS and code in ira-costs.cc is mostly base on investigation
981 of the insn constraints. */
983 setup_allocno_and_important_classes (void)
987 HARD_REG_SET temp_hard_regset2
;
988 static enum reg_class classes
[LIM_REG_CLASSES
+ 1];
991 /* Collect classes which contain unique sets of allocatable hard
992 registers. Prefer GENERAL_REGS to other classes containing the
993 same set of hard registers. */
994 for (i
= 0; i
< LIM_REG_CLASSES
; i
++)
996 temp_hard_regset
= reg_class_contents
[i
] & ~no_unit_alloc_regs
;
997 for (j
= 0; j
< n
; j
++)
1000 temp_hard_regset2
= reg_class_contents
[cl
] & ~no_unit_alloc_regs
;
1001 if (temp_hard_regset
== temp_hard_regset2
)
1004 if (j
>= n
|| targetm
.additional_allocno_class_p (i
))
1005 classes
[n
++] = (enum reg_class
) i
;
1006 else if (i
== GENERAL_REGS
)
1007 /* Prefer general regs. For i386 example, it means that
1008 we prefer GENERAL_REGS over INDEX_REGS or LEGACY_REGS
1009 (all of them consists of the same available hard
1011 classes
[j
] = (enum reg_class
) i
;
1013 classes
[n
] = LIM_REG_CLASSES
;
1015 /* Set up classes which can be used for allocnos as classes
1016 containing non-empty unique sets of allocatable hard
1018 ira_allocno_classes_num
= 0;
1019 for (i
= 0; (cl
= classes
[i
]) != LIM_REG_CLASSES
; i
++)
1020 if (ira_class_hard_regs_num
[cl
] > 0)
1021 ira_allocno_classes
[ira_allocno_classes_num
++] = (enum reg_class
) cl
;
1022 ira_important_classes_num
= 0;
1023 /* Add non-allocno classes containing to non-empty set of
1024 allocatable hard regs. */
1025 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1026 if (ira_class_hard_regs_num
[cl
] > 0)
1028 temp_hard_regset
= reg_class_contents
[cl
] & ~no_unit_alloc_regs
;
1030 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1032 temp_hard_regset2
= (reg_class_contents
[ira_allocno_classes
[j
]]
1033 & ~no_unit_alloc_regs
);
1034 if ((enum reg_class
) cl
== ira_allocno_classes
[j
])
1036 else if (hard_reg_set_subset_p (temp_hard_regset
,
1040 if (set_p
&& j
>= ira_allocno_classes_num
)
1041 ira_important_classes
[ira_important_classes_num
++]
1042 = (enum reg_class
) cl
;
1044 /* Now add allocno classes to the important classes. */
1045 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1046 ira_important_classes
[ira_important_classes_num
++]
1047 = ira_allocno_classes
[j
];
1048 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1050 ira_reg_allocno_class_p
[cl
] = false;
1051 ira_reg_pressure_class_p
[cl
] = false;
1053 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1054 ira_reg_allocno_class_p
[ira_allocno_classes
[j
]] = true;
1055 setup_pressure_classes ();
1056 setup_uniform_class_p ();
1059 /* Setup translation in CLASS_TRANSLATE of all classes into a class
1060 given by array CLASSES of length CLASSES_NUM. The function is used
1061 make translation any reg class to an allocno class or to an
1062 pressure class. This translation is necessary for some
1063 calculations when we can use only allocno or pressure classes and
1064 such translation represents an approximate representation of all
1067 The translation in case when allocatable hard register set of a
1068 given class is subset of allocatable hard register set of a class
1069 in CLASSES is pretty simple. We use smallest classes from CLASSES
1070 containing a given class. If allocatable hard register set of a
1071 given class is not a subset of any corresponding set of a class
1072 from CLASSES, we use the cheapest (with load/store point of view)
1073 class from CLASSES whose set intersects with given class set. */
1075 setup_class_translate_array (enum reg_class
*class_translate
,
1076 int classes_num
, enum reg_class
*classes
)
1079 enum reg_class aclass
, best_class
, *cl_ptr
;
1080 int i
, cost
, min_cost
, best_cost
;
1082 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1083 class_translate
[cl
] = NO_REGS
;
1085 for (i
= 0; i
< classes_num
; i
++)
1087 aclass
= classes
[i
];
1088 for (cl_ptr
= &alloc_reg_class_subclasses
[aclass
][0];
1089 (cl
= *cl_ptr
) != LIM_REG_CLASSES
;
1091 if (class_translate
[cl
] == NO_REGS
)
1092 class_translate
[cl
] = aclass
;
1093 class_translate
[aclass
] = aclass
;
1095 /* For classes which are not fully covered by one of given classes
1096 (in other words covered by more one given class), use the
1098 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1100 if (cl
== NO_REGS
|| class_translate
[cl
] != NO_REGS
)
1102 best_class
= NO_REGS
;
1103 best_cost
= INT_MAX
;
1104 for (i
= 0; i
< classes_num
; i
++)
1106 aclass
= classes
[i
];
1107 temp_hard_regset
= (reg_class_contents
[aclass
]
1108 & reg_class_contents
[cl
]
1109 & ~no_unit_alloc_regs
);
1110 if (! hard_reg_set_empty_p (temp_hard_regset
))
1113 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
1115 cost
= (ira_memory_move_cost
[mode
][aclass
][0]
1116 + ira_memory_move_cost
[mode
][aclass
][1]);
1117 if (min_cost
> cost
)
1120 if (best_class
== NO_REGS
|| best_cost
> min_cost
)
1122 best_class
= aclass
;
1123 best_cost
= min_cost
;
1127 class_translate
[cl
] = best_class
;
1131 /* Set up array IRA_ALLOCNO_CLASS_TRANSLATE and
1132 IRA_PRESSURE_CLASS_TRANSLATE. */
1134 setup_class_translate (void)
1136 setup_class_translate_array (ira_allocno_class_translate
,
1137 ira_allocno_classes_num
, ira_allocno_classes
);
1138 setup_class_translate_array (ira_pressure_class_translate
,
1139 ira_pressure_classes_num
, ira_pressure_classes
);
1142 /* Order numbers of allocno classes in original target allocno class
1143 array, -1 for non-allocno classes. */
1144 static int allocno_class_order
[N_REG_CLASSES
];
1146 /* The function used to sort the important classes. */
1148 comp_reg_classes_func (const void *v1p
, const void *v2p
)
1150 enum reg_class cl1
= *(const enum reg_class
*) v1p
;
1151 enum reg_class cl2
= *(const enum reg_class
*) v2p
;
1152 enum reg_class tcl1
, tcl2
;
1155 tcl1
= ira_allocno_class_translate
[cl1
];
1156 tcl2
= ira_allocno_class_translate
[cl2
];
1157 if (tcl1
!= NO_REGS
&& tcl2
!= NO_REGS
1158 && (diff
= allocno_class_order
[tcl1
] - allocno_class_order
[tcl2
]) != 0)
1160 return (int) cl1
- (int) cl2
;
1163 /* For correct work of function setup_reg_class_relation we need to
1164 reorder important classes according to the order of their allocno
1165 classes. It places important classes containing the same
1166 allocatable hard register set adjacent to each other and allocno
1167 class with the allocatable hard register set right after the other
1168 important classes with the same set.
1170 In example from comments of function
1171 setup_allocno_and_important_classes, it places LEGACY_REGS and
1172 GENERAL_REGS close to each other and GENERAL_REGS is after
1175 reorder_important_classes (void)
1179 for (i
= 0; i
< N_REG_CLASSES
; i
++)
1180 allocno_class_order
[i
] = -1;
1181 for (i
= 0; i
< ira_allocno_classes_num
; i
++)
1182 allocno_class_order
[ira_allocno_classes
[i
]] = i
;
1183 qsort (ira_important_classes
, ira_important_classes_num
,
1184 sizeof (enum reg_class
), comp_reg_classes_func
);
1185 for (i
= 0; i
< ira_important_classes_num
; i
++)
1186 ira_important_class_nums
[ira_important_classes
[i
]] = i
;
1189 /* Set up IRA_REG_CLASS_SUBUNION, IRA_REG_CLASS_SUPERUNION,
1190 IRA_REG_CLASS_SUPER_CLASSES, IRA_REG_CLASSES_INTERSECT, and
1191 IRA_REG_CLASSES_INTERSECT_P. For the meaning of the relations,
1192 please see corresponding comments in ira-int.h. */
1194 setup_reg_class_relations (void)
1196 int i
, cl1
, cl2
, cl3
;
1197 HARD_REG_SET intersection_set
, union_set
, temp_set2
;
1198 bool important_class_p
[N_REG_CLASSES
];
1200 memset (important_class_p
, 0, sizeof (important_class_p
));
1201 for (i
= 0; i
< ira_important_classes_num
; i
++)
1202 important_class_p
[ira_important_classes
[i
]] = true;
1203 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1205 ira_reg_class_super_classes
[cl1
][0] = LIM_REG_CLASSES
;
1206 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1208 ira_reg_classes_intersect_p
[cl1
][cl2
] = false;
1209 ira_reg_class_intersect
[cl1
][cl2
] = NO_REGS
;
1210 ira_reg_class_subset
[cl1
][cl2
] = NO_REGS
;
1211 temp_hard_regset
= reg_class_contents
[cl1
] & ~no_unit_alloc_regs
;
1212 temp_set2
= reg_class_contents
[cl2
] & ~no_unit_alloc_regs
;
1213 if (hard_reg_set_empty_p (temp_hard_regset
)
1214 && hard_reg_set_empty_p (temp_set2
))
1216 /* The both classes have no allocatable hard registers
1217 -- take all class hard registers into account and use
1218 reg_class_subunion and reg_class_superunion. */
1221 cl3
= reg_class_subclasses
[cl1
][i
];
1222 if (cl3
== LIM_REG_CLASSES
)
1224 if (reg_class_subset_p (ira_reg_class_intersect
[cl1
][cl2
],
1225 (enum reg_class
) cl3
))
1226 ira_reg_class_intersect
[cl1
][cl2
] = (enum reg_class
) cl3
;
1228 ira_reg_class_subunion
[cl1
][cl2
] = reg_class_subunion
[cl1
][cl2
];
1229 ira_reg_class_superunion
[cl1
][cl2
] = reg_class_superunion
[cl1
][cl2
];
1232 ira_reg_classes_intersect_p
[cl1
][cl2
]
1233 = hard_reg_set_intersect_p (temp_hard_regset
, temp_set2
);
1234 if (important_class_p
[cl1
] && important_class_p
[cl2
]
1235 && hard_reg_set_subset_p (temp_hard_regset
, temp_set2
))
1237 /* CL1 and CL2 are important classes and CL1 allocatable
1238 hard register set is inside of CL2 allocatable hard
1239 registers -- make CL1 a superset of CL2. */
1242 p
= &ira_reg_class_super_classes
[cl1
][0];
1243 while (*p
!= LIM_REG_CLASSES
)
1245 *p
++ = (enum reg_class
) cl2
;
1246 *p
= LIM_REG_CLASSES
;
1248 ira_reg_class_subunion
[cl1
][cl2
] = NO_REGS
;
1249 ira_reg_class_superunion
[cl1
][cl2
] = NO_REGS
;
1250 intersection_set
= (reg_class_contents
[cl1
]
1251 & reg_class_contents
[cl2
]
1252 & ~no_unit_alloc_regs
);
1253 union_set
= ((reg_class_contents
[cl1
] | reg_class_contents
[cl2
])
1254 & ~no_unit_alloc_regs
);
1255 for (cl3
= 0; cl3
< N_REG_CLASSES
; cl3
++)
1257 temp_hard_regset
= reg_class_contents
[cl3
] & ~no_unit_alloc_regs
;
1258 if (hard_reg_set_subset_p (temp_hard_regset
, intersection_set
))
1260 /* CL3 allocatable hard register set is inside of
1261 intersection of allocatable hard register sets
1263 if (important_class_p
[cl3
])
1266 = (reg_class_contents
1267 [ira_reg_class_intersect
[cl1
][cl2
]]);
1268 temp_set2
&= ~no_unit_alloc_regs
;
1269 if (! hard_reg_set_subset_p (temp_hard_regset
, temp_set2
)
1270 /* If the allocatable hard register sets are
1271 the same, prefer GENERAL_REGS or the
1272 smallest class for debugging
1274 || (temp_hard_regset
== temp_set2
1275 && (cl3
== GENERAL_REGS
1276 || ((ira_reg_class_intersect
[cl1
][cl2
]
1278 && hard_reg_set_subset_p
1279 (reg_class_contents
[cl3
],
1282 ira_reg_class_intersect
[cl1
][cl2
]])))))
1283 ira_reg_class_intersect
[cl1
][cl2
] = (enum reg_class
) cl3
;
1286 = (reg_class_contents
[ira_reg_class_subset
[cl1
][cl2
]]
1287 & ~no_unit_alloc_regs
);
1288 if (! hard_reg_set_subset_p (temp_hard_regset
, temp_set2
)
1289 /* Ignore unavailable hard registers and prefer
1290 smallest class for debugging purposes. */
1291 || (temp_hard_regset
== temp_set2
1292 && hard_reg_set_subset_p
1293 (reg_class_contents
[cl3
],
1295 [(int) ira_reg_class_subset
[cl1
][cl2
]])))
1296 ira_reg_class_subset
[cl1
][cl2
] = (enum reg_class
) cl3
;
1298 if (important_class_p
[cl3
]
1299 && hard_reg_set_subset_p (temp_hard_regset
, union_set
))
1301 /* CL3 allocatable hard register set is inside of
1302 union of allocatable hard register sets of CL1
1305 = (reg_class_contents
[ira_reg_class_subunion
[cl1
][cl2
]]
1306 & ~no_unit_alloc_regs
);
1307 if (ira_reg_class_subunion
[cl1
][cl2
] == NO_REGS
1308 || (hard_reg_set_subset_p (temp_set2
, temp_hard_regset
)
1310 && (temp_set2
!= temp_hard_regset
1311 || cl3
== GENERAL_REGS
1312 /* If the allocatable hard register sets are the
1313 same, prefer GENERAL_REGS or the smallest
1314 class for debugging purposes. */
1315 || (ira_reg_class_subunion
[cl1
][cl2
] != GENERAL_REGS
1316 && hard_reg_set_subset_p
1317 (reg_class_contents
[cl3
],
1319 [(int) ira_reg_class_subunion
[cl1
][cl2
]])))))
1320 ira_reg_class_subunion
[cl1
][cl2
] = (enum reg_class
) cl3
;
1322 if (hard_reg_set_subset_p (union_set
, temp_hard_regset
))
1324 /* CL3 allocatable hard register set contains union
1325 of allocatable hard register sets of CL1 and
1328 = (reg_class_contents
[ira_reg_class_superunion
[cl1
][cl2
]]
1329 & ~no_unit_alloc_regs
);
1330 if (ira_reg_class_superunion
[cl1
][cl2
] == NO_REGS
1331 || (hard_reg_set_subset_p (temp_hard_regset
, temp_set2
)
1333 && (temp_set2
!= temp_hard_regset
1334 || cl3
== GENERAL_REGS
1335 /* If the allocatable hard register sets are the
1336 same, prefer GENERAL_REGS or the smallest
1337 class for debugging purposes. */
1338 || (ira_reg_class_superunion
[cl1
][cl2
] != GENERAL_REGS
1339 && hard_reg_set_subset_p
1340 (reg_class_contents
[cl3
],
1342 [(int) ira_reg_class_superunion
[cl1
][cl2
]])))))
1343 ira_reg_class_superunion
[cl1
][cl2
] = (enum reg_class
) cl3
;
1350 /* Output all uniform and important classes into file F. */
1352 print_uniform_and_important_classes (FILE *f
)
1356 fprintf (f
, "Uniform classes:\n");
1357 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1358 if (ira_uniform_class_p
[cl
])
1359 fprintf (f
, " %s", reg_class_names
[cl
]);
1360 fprintf (f
, "\nImportant classes:\n");
1361 for (i
= 0; i
< ira_important_classes_num
; i
++)
1362 fprintf (f
, " %s", reg_class_names
[ira_important_classes
[i
]]);
1366 /* Output all possible allocno or pressure classes and their
1367 translation map into file F. */
1369 print_translated_classes (FILE *f
, bool pressure_p
)
1371 int classes_num
= (pressure_p
1372 ? ira_pressure_classes_num
: ira_allocno_classes_num
);
1373 enum reg_class
*classes
= (pressure_p
1374 ? ira_pressure_classes
: ira_allocno_classes
);
1375 enum reg_class
*class_translate
= (pressure_p
1376 ? ira_pressure_class_translate
1377 : ira_allocno_class_translate
);
1380 fprintf (f
, "%s classes:\n", pressure_p
? "Pressure" : "Allocno");
1381 for (i
= 0; i
< classes_num
; i
++)
1382 fprintf (f
, " %s", reg_class_names
[classes
[i
]]);
1383 fprintf (f
, "\nClass translation:\n");
1384 for (i
= 0; i
< N_REG_CLASSES
; i
++)
1385 fprintf (f
, " %s -> %s\n", reg_class_names
[i
],
1386 reg_class_names
[class_translate
[i
]]);
1389 /* Output all possible allocno and translation classes and the
1390 translation maps into stderr. */
1392 ira_debug_allocno_classes (void)
1394 print_uniform_and_important_classes (stderr
);
1395 print_translated_classes (stderr
, false);
1396 print_translated_classes (stderr
, true);
1399 /* Set up different arrays concerning class subsets, allocno and
1400 important classes. */
1402 find_reg_classes (void)
1404 setup_allocno_and_important_classes ();
1405 setup_class_translate ();
1406 reorder_important_classes ();
1407 setup_reg_class_relations ();
1412 /* Set up the array above. */
1414 setup_hard_regno_aclass (void)
1418 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1421 ira_hard_regno_allocno_class
[i
]
1422 = (TEST_HARD_REG_BIT (no_unit_alloc_regs
, i
)
1424 : ira_allocno_class_translate
[REGNO_REG_CLASS (i
)]);
1428 ira_hard_regno_allocno_class
[i
] = NO_REGS
;
1429 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1431 cl
= ira_allocno_classes
[j
];
1432 if (ira_class_hard_reg_index
[cl
][i
] >= 0)
1434 ira_hard_regno_allocno_class
[i
] = cl
;
1444 /* Form IRA_REG_CLASS_MAX_NREGS and IRA_REG_CLASS_MIN_NREGS maps. */
1446 setup_reg_class_nregs (void)
1450 for (m
= 0; m
< MAX_MACHINE_MODE
; m
++)
1452 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1453 ira_reg_class_max_nregs
[cl
][m
]
1454 = ira_reg_class_min_nregs
[cl
][m
]
1455 = targetm
.class_max_nregs ((reg_class_t
) cl
, (machine_mode
) m
);
1456 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1458 (cl2
= alloc_reg_class_subclasses
[cl
][i
]) != LIM_REG_CLASSES
;
1460 if (ira_reg_class_min_nregs
[cl2
][m
]
1461 < ira_reg_class_min_nregs
[cl
][m
])
1462 ira_reg_class_min_nregs
[cl
][m
] = ira_reg_class_min_nregs
[cl2
][m
];
1468 /* Set up IRA_PROHIBITED_CLASS_MODE_REGS, IRA_EXCLUDE_CLASS_MODE_REGS, and
1469 IRA_CLASS_SINGLETON. This function is called once IRA_CLASS_HARD_REGS has
1470 been initialized. */
1472 setup_prohibited_and_exclude_class_mode_regs (void)
1474 int j
, k
, hard_regno
, cl
, last_hard_regno
, count
;
1476 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
1478 temp_hard_regset
= reg_class_contents
[cl
] & ~no_unit_alloc_regs
;
1479 for (j
= 0; j
< NUM_MACHINE_MODES
; j
++)
1482 last_hard_regno
= -1;
1483 CLEAR_HARD_REG_SET (ira_prohibited_class_mode_regs
[cl
][j
]);
1484 CLEAR_HARD_REG_SET (ira_exclude_class_mode_regs
[cl
][j
]);
1485 for (k
= ira_class_hard_regs_num
[cl
] - 1; k
>= 0; k
--)
1487 hard_regno
= ira_class_hard_regs
[cl
][k
];
1488 if (!targetm
.hard_regno_mode_ok (hard_regno
, (machine_mode
) j
))
1489 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1491 else if (in_hard_reg_set_p (temp_hard_regset
,
1492 (machine_mode
) j
, hard_regno
))
1494 last_hard_regno
= hard_regno
;
1499 SET_HARD_REG_BIT (ira_exclude_class_mode_regs
[cl
][j
], hard_regno
);
1502 ira_class_singleton
[cl
][j
] = (count
== 1 ? last_hard_regno
: -1);
1507 /* Clarify IRA_PROHIBITED_CLASS_MODE_REGS by excluding hard registers
1508 spanning from one register pressure class to another one. It is
1509 called after defining the pressure classes. */
1511 clarify_prohibited_class_mode_regs (void)
1513 int j
, k
, hard_regno
, cl
, pclass
, nregs
;
1515 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
1516 for (j
= 0; j
< NUM_MACHINE_MODES
; j
++)
1518 CLEAR_HARD_REG_SET (ira_useful_class_mode_regs
[cl
][j
]);
1519 for (k
= ira_class_hard_regs_num
[cl
] - 1; k
>= 0; k
--)
1521 hard_regno
= ira_class_hard_regs
[cl
][k
];
1522 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
], hard_regno
))
1524 nregs
= hard_regno_nregs (hard_regno
, (machine_mode
) j
);
1525 if (hard_regno
+ nregs
> FIRST_PSEUDO_REGISTER
)
1527 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1531 pclass
= ira_pressure_class_translate
[REGNO_REG_CLASS (hard_regno
)];
1532 for (nregs
-- ;nregs
>= 0; nregs
--)
1533 if (((enum reg_class
) pclass
1534 != ira_pressure_class_translate
[REGNO_REG_CLASS
1535 (hard_regno
+ nregs
)]))
1537 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1541 if (!TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1543 add_to_hard_reg_set (&ira_useful_class_mode_regs
[cl
][j
],
1544 (machine_mode
) j
, hard_regno
);
1549 /* Allocate and initialize IRA_REGISTER_MOVE_COST, IRA_MAY_MOVE_IN_COST
1550 and IRA_MAY_MOVE_OUT_COST for MODE. */
1552 ira_init_register_move_cost (machine_mode mode
)
1554 static unsigned short last_move_cost
[N_REG_CLASSES
][N_REG_CLASSES
];
1555 bool all_match
= true;
1556 unsigned int i
, cl1
, cl2
;
1557 HARD_REG_SET ok_regs
;
1559 ira_assert (ira_register_move_cost
[mode
] == NULL
1560 && ira_may_move_in_cost
[mode
] == NULL
1561 && ira_may_move_out_cost
[mode
] == NULL
);
1562 CLEAR_HARD_REG_SET (ok_regs
);
1563 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1564 if (targetm
.hard_regno_mode_ok (i
, mode
))
1565 SET_HARD_REG_BIT (ok_regs
, i
);
1567 /* Note that we might be asked about the move costs of modes that
1568 cannot be stored in any hard register, for example if an inline
1569 asm tries to create a register operand with an impossible mode.
1570 We therefore can't assert have_regs_of_mode[mode] here. */
1571 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1572 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1575 if (!hard_reg_set_intersect_p (ok_regs
, reg_class_contents
[cl1
])
1576 || !hard_reg_set_intersect_p (ok_regs
, reg_class_contents
[cl2
]))
1578 if ((ira_reg_class_max_nregs
[cl1
][mode
]
1579 > ira_class_hard_regs_num
[cl1
])
1580 || (ira_reg_class_max_nregs
[cl2
][mode
]
1581 > ira_class_hard_regs_num
[cl2
]))
1584 cost
= (ira_memory_move_cost
[mode
][cl1
][0]
1585 + ira_memory_move_cost
[mode
][cl2
][1]) * 2;
1589 cost
= register_move_cost (mode
, (enum reg_class
) cl1
,
1590 (enum reg_class
) cl2
);
1591 ira_assert (cost
< 65535);
1593 all_match
&= (last_move_cost
[cl1
][cl2
] == cost
);
1594 last_move_cost
[cl1
][cl2
] = cost
;
1596 if (all_match
&& last_mode_for_init_move_cost
!= -1)
1598 ira_register_move_cost
[mode
]
1599 = ira_register_move_cost
[last_mode_for_init_move_cost
];
1600 ira_may_move_in_cost
[mode
]
1601 = ira_may_move_in_cost
[last_mode_for_init_move_cost
];
1602 ira_may_move_out_cost
[mode
]
1603 = ira_may_move_out_cost
[last_mode_for_init_move_cost
];
1606 last_mode_for_init_move_cost
= mode
;
1607 ira_register_move_cost
[mode
] = XNEWVEC (move_table
, N_REG_CLASSES
);
1608 ira_may_move_in_cost
[mode
] = XNEWVEC (move_table
, N_REG_CLASSES
);
1609 ira_may_move_out_cost
[mode
] = XNEWVEC (move_table
, N_REG_CLASSES
);
1610 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1611 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1614 enum reg_class
*p1
, *p2
;
1616 if (last_move_cost
[cl1
][cl2
] == 65535)
1618 ira_register_move_cost
[mode
][cl1
][cl2
] = 65535;
1619 ira_may_move_in_cost
[mode
][cl1
][cl2
] = 65535;
1620 ira_may_move_out_cost
[mode
][cl1
][cl2
] = 65535;
1624 cost
= last_move_cost
[cl1
][cl2
];
1626 for (p2
= ®_class_subclasses
[cl2
][0];
1627 *p2
!= LIM_REG_CLASSES
; p2
++)
1628 if (ira_class_hard_regs_num
[*p2
] > 0
1629 && (ira_reg_class_max_nregs
[*p2
][mode
]
1630 <= ira_class_hard_regs_num
[*p2
]))
1631 cost
= MAX (cost
, ira_register_move_cost
[mode
][cl1
][*p2
]);
1633 for (p1
= ®_class_subclasses
[cl1
][0];
1634 *p1
!= LIM_REG_CLASSES
; p1
++)
1635 if (ira_class_hard_regs_num
[*p1
] > 0
1636 && (ira_reg_class_max_nregs
[*p1
][mode
]
1637 <= ira_class_hard_regs_num
[*p1
]))
1638 cost
= MAX (cost
, ira_register_move_cost
[mode
][*p1
][cl2
]);
1640 ira_assert (cost
<= 65535);
1641 ira_register_move_cost
[mode
][cl1
][cl2
] = cost
;
1643 if (ira_class_subset_p
[cl1
][cl2
])
1644 ira_may_move_in_cost
[mode
][cl1
][cl2
] = 0;
1646 ira_may_move_in_cost
[mode
][cl1
][cl2
] = cost
;
1648 if (ira_class_subset_p
[cl2
][cl1
])
1649 ira_may_move_out_cost
[mode
][cl1
][cl2
] = 0;
1651 ira_may_move_out_cost
[mode
][cl1
][cl2
] = cost
;
1658 /* This is called once during compiler work. It sets up
1659 different arrays whose values don't depend on the compiled
1662 ira_init_once (void)
1664 ira_init_costs_once ();
1667 ira_use_lra_p
= targetm
.lra_p ();
1670 /* Free ira_max_register_move_cost, ira_may_move_in_cost and
1671 ira_may_move_out_cost for each mode. */
1673 target_ira_int::free_register_move_costs (void)
1677 /* Reset move_cost and friends, making sure we only free shared
1678 table entries once. */
1679 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
1680 if (x_ira_register_move_cost
[mode
])
1683 i
< mode
&& (x_ira_register_move_cost
[i
]
1684 != x_ira_register_move_cost
[mode
]);
1689 free (x_ira_register_move_cost
[mode
]);
1690 free (x_ira_may_move_in_cost
[mode
]);
1691 free (x_ira_may_move_out_cost
[mode
]);
1694 memset (x_ira_register_move_cost
, 0, sizeof x_ira_register_move_cost
);
1695 memset (x_ira_may_move_in_cost
, 0, sizeof x_ira_may_move_in_cost
);
1696 memset (x_ira_may_move_out_cost
, 0, sizeof x_ira_may_move_out_cost
);
1697 last_mode_for_init_move_cost
= -1;
1700 target_ira_int::~target_ira_int ()
1703 free_register_move_costs ();
1706 /* This is called every time when register related information is
1711 this_target_ira_int
->free_register_move_costs ();
1712 setup_reg_mode_hard_regset ();
1713 setup_alloc_regs (flag_omit_frame_pointer
!= 0);
1714 setup_class_subset_and_memory_move_costs ();
1715 setup_reg_class_nregs ();
1716 setup_prohibited_and_exclude_class_mode_regs ();
1717 find_reg_classes ();
1718 clarify_prohibited_class_mode_regs ();
1719 setup_hard_regno_aclass ();
1724 #define ira_prohibited_mode_move_regs_initialized_p \
1725 (this_target_ira_int->x_ira_prohibited_mode_move_regs_initialized_p)
1727 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS. */
1729 setup_prohibited_mode_move_regs (void)
1732 rtx test_reg1
, test_reg2
, move_pat
;
1733 rtx_insn
*move_insn
;
1735 if (ira_prohibited_mode_move_regs_initialized_p
)
1737 ira_prohibited_mode_move_regs_initialized_p
= true;
1738 test_reg1
= gen_rtx_REG (word_mode
, LAST_VIRTUAL_REGISTER
+ 1);
1739 test_reg2
= gen_rtx_REG (word_mode
, LAST_VIRTUAL_REGISTER
+ 2);
1740 move_pat
= gen_rtx_SET (test_reg1
, test_reg2
);
1741 move_insn
= gen_rtx_INSN (VOIDmode
, 0, 0, 0, move_pat
, 0, -1, 0);
1742 for (i
= 0; i
< NUM_MACHINE_MODES
; i
++)
1744 SET_HARD_REG_SET (ira_prohibited_mode_move_regs
[i
]);
1745 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1747 if (!targetm
.hard_regno_mode_ok (j
, (machine_mode
) i
))
1749 set_mode_and_regno (test_reg1
, (machine_mode
) i
, j
);
1750 set_mode_and_regno (test_reg2
, (machine_mode
) i
, j
);
1751 INSN_CODE (move_insn
) = -1;
1752 recog_memoized (move_insn
);
1753 if (INSN_CODE (move_insn
) < 0)
1755 extract_insn (move_insn
);
1756 /* We don't know whether the move will be in code that is optimized
1757 for size or speed, so consider all enabled alternatives. */
1758 if (! constrain_operands (1, get_enabled_alternatives (move_insn
)))
1760 CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs
[i
], j
);
1767 /* Extract INSN and return the set of alternatives that we should consider.
1768 This excludes any alternatives whose constraints are obviously impossible
1769 to meet (e.g. because the constraint requires a constant and the operand
1770 is nonconstant). It also excludes alternatives that are bound to need
1771 a spill or reload, as long as we have other alternatives that match
1774 ira_setup_alts (rtx_insn
*insn
)
1779 int commutative
= -1;
1781 extract_insn (insn
);
1782 preprocess_constraints (insn
);
1783 alternative_mask preferred
= get_preferred_alternatives (insn
);
1784 alternative_mask alts
= 0;
1785 alternative_mask exact_alts
= 0;
1786 /* Check that the hard reg set is enough for holding all
1787 alternatives. It is hard to imagine the situation when the
1788 assertion is wrong. */
1789 ira_assert (recog_data
.n_alternatives
1790 <= (int) MAX (sizeof (HARD_REG_ELT_TYPE
) * CHAR_BIT
,
1791 FIRST_PSEUDO_REGISTER
));
1792 for (nop
= 0; nop
< recog_data
.n_operands
; nop
++)
1793 if (recog_data
.constraints
[nop
][0] == '%')
1798 for (curr_swapped
= false;; curr_swapped
= true)
1800 for (nalt
= 0; nalt
< recog_data
.n_alternatives
; nalt
++)
1802 if (!TEST_BIT (preferred
, nalt
) || TEST_BIT (exact_alts
, nalt
))
1805 const operand_alternative
*op_alt
1806 = &recog_op_alt
[nalt
* recog_data
.n_operands
];
1807 int this_reject
= 0;
1808 for (nop
= 0; nop
< recog_data
.n_operands
; nop
++)
1812 this_reject
+= op_alt
[nop
].reject
;
1814 rtx op
= recog_data
.operand
[nop
];
1815 p
= op_alt
[nop
].constraint
;
1816 if (*p
== 0 || *p
== ',')
1821 switch (c
= *p
, len
= CONSTRAINT_LEN (c
, p
), c
)
1832 /* The commutative modifier is handled above. */
1835 case '0': case '1': case '2': case '3': case '4':
1836 case '5': case '6': case '7': case '8': case '9':
1839 unsigned long dup
= strtoul (p
, &end
, 10);
1840 rtx other
= recog_data
.operand
[dup
];
1843 ? rtx_equal_p (other
, op
)
1844 : REG_P (op
) || SUBREG_P (op
))
1856 enum constraint_num cn
= lookup_constraint (p
);
1858 switch (get_constraint_type (cn
))
1861 if (reg_class_for_constraint (cn
) != NO_REGS
)
1863 if (REG_P (op
) || SUBREG_P (op
))
1870 if (CONST_INT_P (op
)
1871 && (insn_const_int_ok_for_constraint
1880 case CT_RELAXED_MEMORY
:
1883 case CT_SPECIAL_MEMORY
:
1885 mem
= extract_mem_from_operand (op
);
1892 if (constraint_satisfied_p (op
, cn
))
1899 while (p
+= len
, c
);
1902 /* We can make the alternative match by spilling a register
1903 to memory or loading something into a register. Count a
1904 cost of one reload (the equivalent of the '?' constraint). */
1910 if (nop
>= recog_data
.n_operands
)
1912 alts
|= ALTERNATIVE_BIT (nalt
);
1913 if (this_reject
== 0)
1914 exact_alts
|= ALTERNATIVE_BIT (nalt
);
1917 if (commutative
< 0)
1919 /* Swap forth and back to avoid changing recog_data. */
1920 std::swap (recog_data
.operand
[commutative
],
1921 recog_data
.operand
[commutative
+ 1]);
1925 return exact_alts
? exact_alts
: alts
;
1928 /* Return the number of the output non-early clobber operand which
1929 should be the same in any case as operand with number OP_NUM (or
1930 negative value if there is no such operand). ALTS is the mask
1931 of alternatives that we should consider. SINGLE_INPUT_OP_HAS_CSTR_P
1932 should be set in this function, it indicates whether there is only
1933 a single input operand which has the matching constraint on the
1934 output operand at the position specified in return value. If the
1935 pattern allows any one of several input operands holds the matching
1936 constraint, it's set as false, one typical case is destructive FMA
1937 instruction on target rs6000. Note that for a non-NO_REG preferred
1938 register class with no free register move copy, if the parameter
1939 PARAM_IRA_CONSIDER_DUP_IN_ALL_ALTS is set to one, this function
1940 will check all available alternatives for matching constraints,
1941 even if it has found or will find one alternative with non-NO_REG
1942 regclass, it can respect more cases with matching constraints. If
1943 PARAM_IRA_CONSIDER_DUP_IN_ALL_ALTS is set to zero,
1944 SINGLE_INPUT_OP_HAS_CSTR_P is always true, it will stop to find
1945 matching constraint relationship once it hits some alternative with
1946 some non-NO_REG regclass. */
1948 ira_get_dup_out_num (int op_num
, alternative_mask alts
,
1949 bool &single_input_op_has_cstr_p
)
1951 int curr_alt
, c
, original
;
1952 bool ignore_p
, use_commut_op_p
;
1955 if (op_num
< 0 || recog_data
.n_alternatives
== 0)
1957 /* We should find duplications only for input operands. */
1958 if (recog_data
.operand_type
[op_num
] != OP_IN
)
1960 str
= recog_data
.constraints
[op_num
];
1961 use_commut_op_p
= false;
1962 single_input_op_has_cstr_p
= true;
1964 rtx op
= recog_data
.operand
[op_num
];
1965 int op_regno
= reg_or_subregno (op
);
1966 enum reg_class op_pref_cl
= reg_preferred_class (op_regno
);
1967 machine_mode op_mode
= GET_MODE (op
);
1969 ira_init_register_move_cost_if_necessary (op_mode
);
1970 /* If the preferred regclass isn't NO_REG, continue to find the matching
1971 constraint in all available alternatives with preferred regclass, even
1972 if we have found or will find one alternative whose constraint stands
1973 for a REG (non-NO_REG) regclass. Note that it would be fine not to
1974 respect matching constraint if the register copy is free, so exclude
1976 bool respect_dup_despite_reg_cstr
1977 = param_ira_consider_dup_in_all_alts
1978 && op_pref_cl
!= NO_REGS
1979 && ira_register_move_cost
[op_mode
][op_pref_cl
][op_pref_cl
] > 0;
1981 /* Record the alternative whose constraint uses the same regclass as the
1982 preferred regclass, later if we find one matching constraint for this
1983 operand with preferred reclass, we will visit these recorded
1984 alternatives to check whether if there is one alternative in which no
1985 any INPUT operands have one matching constraint same as our candidate.
1986 If yes, it means there is one alternative which is perfectly fine
1987 without satisfying this matching constraint. If no, it means in any
1988 alternatives there is one other INPUT operand holding this matching
1989 constraint, it's fine to respect this matching constraint and further
1990 create this constraint copy since it would become harmless once some
1991 other takes preference and it's interfered. */
1992 alternative_mask pref_cl_alts
;
1998 for (curr_alt
= 0, ignore_p
= !TEST_BIT (alts
, curr_alt
),
2009 ignore_p
= !TEST_BIT (alts
, curr_alt
);
2011 else if (! ignore_p
)
2018 enum constraint_num cn
= lookup_constraint (str
);
2019 enum reg_class cl
= reg_class_for_constraint (cn
);
2020 if (cl
!= NO_REGS
&& !targetm
.class_likely_spilled_p (cl
))
2022 if (respect_dup_despite_reg_cstr
)
2024 /* If it's free to move from one preferred class to
2025 the one without matching constraint, it doesn't
2026 have to respect this constraint with costs. */
2027 if (cl
!= op_pref_cl
2028 && (ira_reg_class_intersect
[cl
][op_pref_cl
]
2030 && (ira_may_move_in_cost
[op_mode
][op_pref_cl
][cl
]
2033 else if (cl
== op_pref_cl
)
2034 pref_cl_alts
|= ALTERNATIVE_BIT (curr_alt
);
2039 if (constraint_satisfied_p (op
, cn
))
2044 case '0': case '1': case '2': case '3': case '4':
2045 case '5': case '6': case '7': case '8': case '9':
2048 int n
= (int) strtoul (str
, &end
, 10);
2050 if (original
!= -1 && original
!= n
)
2052 gcc_assert (n
< recog_data
.n_operands
);
2053 if (respect_dup_despite_reg_cstr
)
2055 const operand_alternative
*op_alt
2056 = &recog_op_alt
[curr_alt
* recog_data
.n_operands
];
2057 /* Only respect the one with preferred rclass, without
2058 respect_dup_despite_reg_cstr it's possible to get
2059 one whose regclass isn't preferred first before,
2060 but it would fail since there should be other
2061 alternatives with preferred regclass. */
2062 if (op_alt
[n
].cl
== op_pref_cl
)
2070 str
+= CONSTRAINT_LEN (c
, str
);
2074 if (recog_data
.operand_type
[original
] == OP_OUT
)
2076 if (pref_cl_alts
== 0)
2078 /* Visit these recorded alternatives to check whether
2079 there is one alternative in which no any INPUT operands
2080 have one matching constraint same as our candidate.
2081 Give up this candidate if so. */
2083 for (nalt
= 0; nalt
< recog_data
.n_alternatives
; nalt
++)
2085 if (!TEST_BIT (pref_cl_alts
, nalt
))
2087 const operand_alternative
*op_alt
2088 = &recog_op_alt
[nalt
* recog_data
.n_operands
];
2089 bool dup_in_other
= false;
2090 for (nop
= 0; nop
< recog_data
.n_operands
; nop
++)
2092 if (recog_data
.operand_type
[nop
] != OP_IN
)
2096 if (op_alt
[nop
].matches
== original
)
2098 dup_in_other
= true;
2105 single_input_op_has_cstr_p
= false;
2109 if (use_commut_op_p
)
2111 use_commut_op_p
= true;
2112 if (recog_data
.constraints
[op_num
][0] == '%')
2113 str
= recog_data
.constraints
[op_num
+ 1];
2114 else if (op_num
> 0 && recog_data
.constraints
[op_num
- 1][0] == '%')
2115 str
= recog_data
.constraints
[op_num
- 1];
2124 /* Search forward to see if the source register of a copy insn dies
2125 before either it or the destination register is modified, but don't
2126 scan past the end of the basic block. If so, we can replace the
2127 source with the destination and let the source die in the copy
2130 This will reduce the number of registers live in that range and may
2131 enable the destination and the source coalescing, thus often saving
2132 one register in addition to a register-register copy. */
2135 decrease_live_ranges_number (void)
2139 rtx set
, src
, dest
, dest_death
, note
;
2143 if (! flag_expensive_optimizations
)
2147 fprintf (ira_dump_file
, "Starting decreasing number of live ranges...\n");
2149 FOR_EACH_BB_FN (bb
, cfun
)
2150 FOR_BB_INSNS (bb
, insn
)
2152 set
= single_set (insn
);
2155 src
= SET_SRC (set
);
2156 dest
= SET_DEST (set
);
2157 if (! REG_P (src
) || ! REG_P (dest
)
2158 || find_reg_note (insn
, REG_DEAD
, src
))
2160 sregno
= REGNO (src
);
2161 dregno
= REGNO (dest
);
2163 /* We don't want to mess with hard regs if register classes
2165 if (sregno
== dregno
2166 || (targetm
.small_register_classes_for_mode_p (GET_MODE (src
))
2167 && (sregno
< FIRST_PSEUDO_REGISTER
2168 || dregno
< FIRST_PSEUDO_REGISTER
))
2169 /* We don't see all updates to SP if they are in an
2170 auto-inc memory reference, so we must disallow this
2171 optimization on them. */
2172 || sregno
== STACK_POINTER_REGNUM
2173 || dregno
== STACK_POINTER_REGNUM
)
2176 dest_death
= NULL_RTX
;
2178 for (p
= NEXT_INSN (insn
); p
; p
= NEXT_INSN (p
))
2182 if (BLOCK_FOR_INSN (p
) != bb
)
2185 if (reg_set_p (src
, p
) || reg_set_p (dest
, p
)
2186 /* If SRC is an asm-declared register, it must not be
2187 replaced in any asm. Unfortunately, the REG_EXPR
2188 tree for the asm variable may be absent in the SRC
2189 rtx, so we can't check the actual register
2190 declaration easily (the asm operand will have it,
2191 though). To avoid complicating the test for a rare
2192 case, we just don't perform register replacement
2193 for a hard reg mentioned in an asm. */
2194 || (sregno
< FIRST_PSEUDO_REGISTER
2195 && asm_noperands (PATTERN (p
)) >= 0
2196 && reg_overlap_mentioned_p (src
, PATTERN (p
)))
2197 /* Don't change hard registers used by a call. */
2198 || (CALL_P (p
) && sregno
< FIRST_PSEUDO_REGISTER
2199 && find_reg_fusage (p
, USE
, src
))
2200 /* Don't change a USE of a register. */
2201 || (GET_CODE (PATTERN (p
)) == USE
2202 && reg_overlap_mentioned_p (src
, XEXP (PATTERN (p
), 0))))
2205 /* See if all of SRC dies in P. This test is slightly
2206 more conservative than it needs to be. */
2207 if ((note
= find_regno_note (p
, REG_DEAD
, sregno
))
2208 && GET_MODE (XEXP (note
, 0)) == GET_MODE (src
))
2212 /* We can do the optimization. Scan forward from INSN
2213 again, replacing regs as we go. Set FAILED if a
2214 replacement can't be done. In that case, we can't
2215 move the death note for SRC. This should be
2218 /* Set to stop at next insn. */
2219 for (q
= next_real_insn (insn
);
2220 q
!= next_real_insn (p
);
2221 q
= next_real_insn (q
))
2223 if (reg_overlap_mentioned_p (src
, PATTERN (q
)))
2225 /* If SRC is a hard register, we might miss
2226 some overlapping registers with
2227 validate_replace_rtx, so we would have to
2228 undo it. We can't if DEST is present in
2229 the insn, so fail in that combination of
2231 if (sregno
< FIRST_PSEUDO_REGISTER
2232 && reg_mentioned_p (dest
, PATTERN (q
)))
2235 /* Attempt to replace all uses. */
2236 else if (!validate_replace_rtx (src
, dest
, q
))
2239 /* If this succeeded, but some part of the
2240 register is still present, undo the
2242 else if (sregno
< FIRST_PSEUDO_REGISTER
2243 && reg_overlap_mentioned_p (src
, PATTERN (q
)))
2245 validate_replace_rtx (dest
, src
, q
);
2250 /* If DEST dies here, remove the death note and
2251 save it for later. Make sure ALL of DEST dies
2252 here; again, this is overly conservative. */
2254 && (dest_death
= find_regno_note (q
, REG_DEAD
, dregno
)))
2256 if (GET_MODE (XEXP (dest_death
, 0)) == GET_MODE (dest
))
2257 remove_note (q
, dest_death
);
2268 /* Move death note of SRC from P to INSN. */
2269 remove_note (p
, note
);
2270 XEXP (note
, 1) = REG_NOTES (insn
);
2271 REG_NOTES (insn
) = note
;
2274 /* DEST is also dead if INSN has a REG_UNUSED note for
2278 = find_regno_note (insn
, REG_UNUSED
, dregno
)))
2280 PUT_REG_NOTE_KIND (dest_death
, REG_DEAD
);
2281 remove_note (insn
, dest_death
);
2284 /* Put death note of DEST on P if we saw it die. */
2287 XEXP (dest_death
, 1) = REG_NOTES (p
);
2288 REG_NOTES (p
) = dest_death
;
2293 /* If SRC is a hard register which is set or killed in
2294 some other way, we can't do this optimization. */
2295 else if (sregno
< FIRST_PSEUDO_REGISTER
&& dead_or_set_p (p
, src
))
2303 /* Return nonzero if REGNO is a particularly bad choice for reloading X. */
2305 ira_bad_reload_regno_1 (int regno
, rtx x
)
2309 enum reg_class pref
;
2311 /* We only deal with pseudo regs. */
2312 if (! x
|| GET_CODE (x
) != REG
)
2315 x_regno
= REGNO (x
);
2316 if (x_regno
< FIRST_PSEUDO_REGISTER
)
2319 /* If the pseudo prefers REGNO explicitly, then do not consider
2320 REGNO a bad spill choice. */
2321 pref
= reg_preferred_class (x_regno
);
2322 if (reg_class_size
[pref
] == 1)
2323 return !TEST_HARD_REG_BIT (reg_class_contents
[pref
], regno
);
2325 /* If the pseudo conflicts with REGNO, then we consider REGNO a
2326 poor choice for a reload regno. */
2327 a
= ira_regno_allocno_map
[x_regno
];
2328 n
= ALLOCNO_NUM_OBJECTS (a
);
2329 for (i
= 0; i
< n
; i
++)
2331 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2332 if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), regno
))
2338 /* Return nonzero if REGNO is a particularly bad choice for reloading
2341 ira_bad_reload_regno (int regno
, rtx in
, rtx out
)
2343 return (ira_bad_reload_regno_1 (regno
, in
)
2344 || ira_bad_reload_regno_1 (regno
, out
));
2347 /* Add register clobbers from asm statements. */
2349 compute_regs_asm_clobbered (void)
2353 FOR_EACH_BB_FN (bb
, cfun
)
2356 FOR_BB_INSNS_REVERSE (bb
, insn
)
2360 if (NONDEBUG_INSN_P (insn
) && asm_noperands (PATTERN (insn
)) >= 0)
2361 FOR_EACH_INSN_DEF (def
, insn
)
2363 unsigned int dregno
= DF_REF_REGNO (def
);
2364 if (HARD_REGISTER_NUM_P (dregno
))
2365 add_to_hard_reg_set (&crtl
->asm_clobbers
,
2366 GET_MODE (DF_REF_REAL_REG (def
)),
2374 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and
2377 ira_setup_eliminable_regset (void)
2380 static const struct {const int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
2381 int fp_reg_count
= hard_regno_nregs (HARD_FRAME_POINTER_REGNUM
, Pmode
);
2383 /* Setup is_leaf as frame_pointer_required may use it. This function
2384 is called by sched_init before ira if scheduling is enabled. */
2385 crtl
->is_leaf
= leaf_function_p ();
2387 /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
2388 sp for alloca. So we can't eliminate the frame pointer in that
2389 case. At some point, we should improve this by emitting the
2390 sp-adjusting insns for this case. */
2391 frame_pointer_needed
2392 = (! flag_omit_frame_pointer
2393 || (cfun
->calls_alloca
&& EXIT_IGNORE_STACK
)
2394 /* We need the frame pointer to catch stack overflow exceptions if
2395 the stack pointer is moving (as for the alloca case just above). */
2396 || (STACK_CHECK_MOVING_SP
2399 && cfun
->can_throw_non_call_exceptions
)
2400 || crtl
->accesses_prior_frames
2401 || (SUPPORTS_STACK_ALIGNMENT
&& crtl
->stack_realign_needed
)
2402 || targetm
.frame_pointer_required ());
2404 /* The chance that FRAME_POINTER_NEEDED is changed from inspecting
2405 RTL is very small. So if we use frame pointer for RA and RTL
2406 actually prevents this, we will spill pseudos assigned to the
2407 frame pointer in LRA. */
2409 if (frame_pointer_needed
)
2410 for (i
= 0; i
< fp_reg_count
; i
++)
2411 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM
+ i
, true);
2413 ira_no_alloc_regs
= no_unit_alloc_regs
;
2414 CLEAR_HARD_REG_SET (eliminable_regset
);
2416 compute_regs_asm_clobbered ();
2418 /* Build the regset of all eliminable registers and show we can't
2419 use those that we already know won't be eliminated. */
2420 for (i
= 0; i
< (int) ARRAY_SIZE (eliminables
); i
++)
2423 = (! targetm
.can_eliminate (eliminables
[i
].from
, eliminables
[i
].to
)
2424 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& frame_pointer_needed
));
2426 if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
, eliminables
[i
].from
))
2428 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
2431 SET_HARD_REG_BIT (ira_no_alloc_regs
, eliminables
[i
].from
);
2433 else if (cannot_elim
)
2434 error ("%s cannot be used in %<asm%> here",
2435 reg_names
[eliminables
[i
].from
]);
2437 df_set_regs_ever_live (eliminables
[i
].from
, true);
2439 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
)
2441 for (i
= 0; i
< fp_reg_count
; i
++)
2442 if (global_regs
[HARD_FRAME_POINTER_REGNUM
+ i
])
2443 /* Nothing to do: the register is already treated as live
2444 where appropriate, and cannot be eliminated. */
2446 else if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
,
2447 HARD_FRAME_POINTER_REGNUM
+ i
))
2449 SET_HARD_REG_BIT (eliminable_regset
,
2450 HARD_FRAME_POINTER_REGNUM
+ i
);
2451 if (frame_pointer_needed
)
2452 SET_HARD_REG_BIT (ira_no_alloc_regs
,
2453 HARD_FRAME_POINTER_REGNUM
+ i
);
2455 else if (frame_pointer_needed
)
2456 error ("%s cannot be used in %<asm%> here",
2457 reg_names
[HARD_FRAME_POINTER_REGNUM
+ i
]);
2459 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM
+ i
, true);
2465 /* Vector of substitutions of register numbers,
2466 used to map pseudo regs into hardware regs.
2467 This is set up as a result of register allocation.
2468 Element N is the hard reg assigned to pseudo reg N,
2469 or is -1 if no hard reg was assigned.
2470 If N is a hard reg number, element N is N. */
2471 short *reg_renumber
;
2473 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
2474 the allocation found by IRA. */
2476 setup_reg_renumber (void)
2478 int regno
, hard_regno
;
2480 ira_allocno_iterator ai
;
2482 caller_save_needed
= 0;
2483 FOR_EACH_ALLOCNO (a
, ai
)
2485 if (ira_use_lra_p
&& ALLOCNO_CAP_MEMBER (a
) != NULL
)
2487 /* There are no caps at this point. */
2488 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
2489 if (! ALLOCNO_ASSIGNED_P (a
))
2490 /* It can happen if A is not referenced but partially anticipated
2491 somewhere in a region. */
2492 ALLOCNO_ASSIGNED_P (a
) = true;
2493 ira_free_allocno_updated_costs (a
);
2494 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2495 regno
= ALLOCNO_REGNO (a
);
2496 reg_renumber
[regno
] = (hard_regno
< 0 ? -1 : hard_regno
);
2497 if (hard_regno
>= 0)
2500 enum reg_class pclass
;
2503 pclass
= ira_pressure_class_translate
[REGNO_REG_CLASS (hard_regno
)];
2504 nwords
= ALLOCNO_NUM_OBJECTS (a
);
2505 for (i
= 0; i
< nwords
; i
++)
2507 obj
= ALLOCNO_OBJECT (a
, i
);
2508 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
)
2509 |= ~reg_class_contents
[pclass
];
2511 if (ira_need_caller_save_p (a
, hard_regno
))
2513 ira_assert (!optimize
|| flag_caller_saves
2514 || (ALLOCNO_CALLS_CROSSED_NUM (a
)
2515 == ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
))
2516 || regno
>= ira_reg_equiv_len
2517 || ira_equiv_no_lvalue_p (regno
));
2518 caller_save_needed
= 1;
2524 /* Set up allocno assignment flags for further allocation
2527 setup_allocno_assignment_flags (void)
2531 ira_allocno_iterator ai
;
2533 FOR_EACH_ALLOCNO (a
, ai
)
2535 if (! ALLOCNO_ASSIGNED_P (a
))
2536 /* It can happen if A is not referenced but partially anticipated
2537 somewhere in a region. */
2538 ira_free_allocno_updated_costs (a
);
2539 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2540 /* Don't assign hard registers to allocnos which are destination
2541 of removed store at the end of loop. It has no sense to keep
2542 the same value in different hard registers. It is also
2543 impossible to assign hard registers correctly to such
2544 allocnos because the cost info and info about intersected
2545 calls are incorrect for them. */
2546 ALLOCNO_ASSIGNED_P (a
) = (hard_regno
>= 0
2547 || ALLOCNO_EMIT_DATA (a
)->mem_optimized_dest_p
2548 || (ALLOCNO_MEMORY_COST (a
)
2549 - ALLOCNO_CLASS_COST (a
)) < 0);
2552 || ira_hard_reg_in_set_p (hard_regno
, ALLOCNO_MODE (a
),
2553 reg_class_contents
[ALLOCNO_CLASS (a
)]));
2557 /* Evaluate overall allocation cost and the costs for using hard
2558 registers and memory for allocnos. */
2560 calculate_allocation_cost (void)
2562 int hard_regno
, cost
;
2564 ira_allocno_iterator ai
;
2566 ira_overall_cost
= ira_reg_cost
= ira_mem_cost
= 0;
2567 FOR_EACH_ALLOCNO (a
, ai
)
2569 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2570 ira_assert (hard_regno
< 0
2571 || (ira_hard_reg_in_set_p
2572 (hard_regno
, ALLOCNO_MODE (a
),
2573 reg_class_contents
[ALLOCNO_CLASS (a
)])));
2576 cost
= ALLOCNO_MEMORY_COST (a
);
2577 ira_mem_cost
+= cost
;
2579 else if (ALLOCNO_HARD_REG_COSTS (a
) != NULL
)
2581 cost
= (ALLOCNO_HARD_REG_COSTS (a
)
2582 [ira_class_hard_reg_index
2583 [ALLOCNO_CLASS (a
)][hard_regno
]]);
2584 ira_reg_cost
+= cost
;
2588 cost
= ALLOCNO_CLASS_COST (a
);
2589 ira_reg_cost
+= cost
;
2591 ira_overall_cost
+= cost
;
2594 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
2596 fprintf (ira_dump_file
,
2597 "+++Costs: overall %" PRId64
2603 ira_overall_cost
, ira_reg_cost
, ira_mem_cost
,
2604 ira_load_cost
, ira_store_cost
, ira_shuffle_cost
);
2605 fprintf (ira_dump_file
, "\n+++ move loops %d, new jumps %d\n",
2606 ira_move_loops_num
, ira_additional_jumps_num
);
2611 #ifdef ENABLE_IRA_CHECKING
2612 /* Check the correctness of the allocation. We do need this because
2613 of complicated code to transform more one region internal
2614 representation into one region representation. */
2616 check_allocation (void)
2619 int hard_regno
, nregs
, conflict_nregs
;
2620 ira_allocno_iterator ai
;
2622 FOR_EACH_ALLOCNO (a
, ai
)
2624 int n
= ALLOCNO_NUM_OBJECTS (a
);
2627 if (ALLOCNO_CAP_MEMBER (a
) != NULL
2628 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0)
2630 nregs
= hard_regno_nregs (hard_regno
, ALLOCNO_MODE (a
));
2632 /* We allocated a single hard register. */
2635 /* We allocated multiple hard registers, and we will test
2636 conflicts in a granularity of single hard regs. */
2639 for (i
= 0; i
< n
; i
++)
2641 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2642 ira_object_t conflict_obj
;
2643 ira_object_conflict_iterator oci
;
2644 int this_regno
= hard_regno
;
2647 if (REG_WORDS_BIG_ENDIAN
)
2648 this_regno
+= n
- i
- 1;
2652 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2654 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2655 int conflict_hard_regno
= ALLOCNO_HARD_REGNO (conflict_a
);
2656 if (conflict_hard_regno
< 0)
2658 if (ira_soft_conflict (a
, conflict_a
))
2661 conflict_nregs
= hard_regno_nregs (conflict_hard_regno
,
2662 ALLOCNO_MODE (conflict_a
));
2664 if (ALLOCNO_NUM_OBJECTS (conflict_a
) > 1
2665 && conflict_nregs
== ALLOCNO_NUM_OBJECTS (conflict_a
))
2667 if (REG_WORDS_BIG_ENDIAN
)
2668 conflict_hard_regno
+= (ALLOCNO_NUM_OBJECTS (conflict_a
)
2669 - OBJECT_SUBWORD (conflict_obj
) - 1);
2671 conflict_hard_regno
+= OBJECT_SUBWORD (conflict_obj
);
2675 if ((conflict_hard_regno
<= this_regno
2676 && this_regno
< conflict_hard_regno
+ conflict_nregs
)
2677 || (this_regno
<= conflict_hard_regno
2678 && conflict_hard_regno
< this_regno
+ nregs
))
2680 fprintf (stderr
, "bad allocation for %d and %d\n",
2681 ALLOCNO_REGNO (a
), ALLOCNO_REGNO (conflict_a
));
2690 /* Allocate REG_EQUIV_INIT. Set up it from IRA_REG_EQUIV which should
2691 be already calculated. */
2693 setup_reg_equiv_init (void)
2696 int max_regno
= max_reg_num ();
2698 for (i
= 0; i
< max_regno
; i
++)
2699 reg_equiv_init (i
) = ira_reg_equiv
[i
].init_insns
;
2702 /* Update equiv regno from movement of FROM_REGNO to TO_REGNO. INSNS
2703 are insns which were generated for such movement. It is assumed
2704 that FROM_REGNO and TO_REGNO always have the same value at the
2705 point of any move containing such registers. This function is used
2706 to update equiv info for register shuffles on the region borders
2707 and for caller save/restore insns. */
2709 ira_update_equiv_info_by_shuffle_insn (int to_regno
, int from_regno
, rtx_insn
*insns
)
2714 if (! ira_reg_equiv
[from_regno
].defined_p
2715 && (! ira_reg_equiv
[to_regno
].defined_p
2716 || ((x
= ira_reg_equiv
[to_regno
].memory
) != NULL_RTX
2717 && ! MEM_READONLY_P (x
))))
2720 if (NEXT_INSN (insn
) != NULL_RTX
)
2722 if (! ira_reg_equiv
[to_regno
].defined_p
)
2724 ira_assert (ira_reg_equiv
[to_regno
].init_insns
== NULL_RTX
);
2727 ira_reg_equiv
[to_regno
].defined_p
= false;
2728 ira_reg_equiv
[to_regno
].caller_save_p
= false;
2729 ira_reg_equiv
[to_regno
].memory
2730 = ira_reg_equiv
[to_regno
].constant
2731 = ira_reg_equiv
[to_regno
].invariant
2732 = ira_reg_equiv
[to_regno
].init_insns
= NULL
;
2733 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2734 fprintf (ira_dump_file
,
2735 " Invalidating equiv info for reg %d\n", to_regno
);
2738 /* It is possible that FROM_REGNO still has no equivalence because
2739 in shuffles to_regno<-from_regno and from_regno<-to_regno the 2nd
2740 insn was not processed yet. */
2741 if (ira_reg_equiv
[from_regno
].defined_p
)
2743 ira_reg_equiv
[to_regno
].defined_p
= true;
2744 if ((x
= ira_reg_equiv
[from_regno
].memory
) != NULL_RTX
)
2746 ira_assert (ira_reg_equiv
[from_regno
].invariant
== NULL_RTX
2747 && ira_reg_equiv
[from_regno
].constant
== NULL_RTX
);
2748 ira_assert (ira_reg_equiv
[to_regno
].memory
== NULL_RTX
2749 || rtx_equal_p (ira_reg_equiv
[to_regno
].memory
, x
));
2750 ira_reg_equiv
[to_regno
].memory
= x
;
2751 if (! MEM_READONLY_P (x
))
2752 /* We don't add the insn to insn init list because memory
2753 equivalence is just to say what memory is better to use
2754 when the pseudo is spilled. */
2757 else if ((x
= ira_reg_equiv
[from_regno
].constant
) != NULL_RTX
)
2759 ira_assert (ira_reg_equiv
[from_regno
].invariant
== NULL_RTX
);
2760 ira_assert (ira_reg_equiv
[to_regno
].constant
== NULL_RTX
2761 || rtx_equal_p (ira_reg_equiv
[to_regno
].constant
, x
));
2762 ira_reg_equiv
[to_regno
].constant
= x
;
2766 x
= ira_reg_equiv
[from_regno
].invariant
;
2767 ira_assert (x
!= NULL_RTX
);
2768 ira_assert (ira_reg_equiv
[to_regno
].invariant
== NULL_RTX
2769 || rtx_equal_p (ira_reg_equiv
[to_regno
].invariant
, x
));
2770 ira_reg_equiv
[to_regno
].invariant
= x
;
2772 if (find_reg_note (insn
, REG_EQUIV
, x
) == NULL_RTX
)
2774 note
= set_unique_reg_note (insn
, REG_EQUIV
, copy_rtx (x
));
2775 gcc_assert (note
!= NULL_RTX
);
2776 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2778 fprintf (ira_dump_file
,
2779 " Adding equiv note to insn %u for reg %d ",
2780 INSN_UID (insn
), to_regno
);
2781 dump_value_slim (ira_dump_file
, x
, 1);
2782 fprintf (ira_dump_file
, "\n");
2786 ira_reg_equiv
[to_regno
].init_insns
2787 = gen_rtx_INSN_LIST (VOIDmode
, insn
,
2788 ira_reg_equiv
[to_regno
].init_insns
);
2789 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2790 fprintf (ira_dump_file
,
2791 " Adding equiv init move insn %u to reg %d\n",
2792 INSN_UID (insn
), to_regno
);
2795 /* Fix values of array REG_EQUIV_INIT after live range splitting done
2798 fix_reg_equiv_init (void)
2800 int max_regno
= max_reg_num ();
2801 int i
, new_regno
, max
;
2803 rtx_insn_list
*x
, *next
, *prev
;
2806 if (max_regno_before_ira
< max_regno
)
2808 max
= vec_safe_length (reg_equivs
);
2810 for (i
= FIRST_PSEUDO_REGISTER
; i
< max
; i
++)
2811 for (prev
= NULL
, x
= reg_equiv_init (i
);
2817 set
= single_set (insn
);
2818 ira_assert (set
!= NULL_RTX
2819 && (REG_P (SET_DEST (set
)) || REG_P (SET_SRC (set
))));
2820 if (REG_P (SET_DEST (set
))
2821 && ((int) REGNO (SET_DEST (set
)) == i
2822 || (int) ORIGINAL_REGNO (SET_DEST (set
)) == i
))
2823 new_regno
= REGNO (SET_DEST (set
));
2824 else if (REG_P (SET_SRC (set
))
2825 && ((int) REGNO (SET_SRC (set
)) == i
2826 || (int) ORIGINAL_REGNO (SET_SRC (set
)) == i
))
2827 new_regno
= REGNO (SET_SRC (set
));
2834 /* Remove the wrong list element. */
2835 if (prev
== NULL_RTX
)
2836 reg_equiv_init (i
) = next
;
2838 XEXP (prev
, 1) = next
;
2839 XEXP (x
, 1) = reg_equiv_init (new_regno
);
2840 reg_equiv_init (new_regno
) = x
;
2846 #ifdef ENABLE_IRA_CHECKING
2847 /* Print redundant memory-memory copies. */
2849 print_redundant_copies (void)
2853 ira_copy_t cp
, next_cp
;
2854 ira_allocno_iterator ai
;
2856 FOR_EACH_ALLOCNO (a
, ai
)
2858 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2861 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2862 if (hard_regno
>= 0)
2864 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2866 next_cp
= cp
->next_first_allocno_copy
;
2869 next_cp
= cp
->next_second_allocno_copy
;
2870 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
2871 && cp
->insn
!= NULL_RTX
2872 && ALLOCNO_HARD_REGNO (cp
->first
) == hard_regno
)
2873 fprintf (ira_dump_file
,
2874 " Redundant move from %d(freq %d):%d\n",
2875 INSN_UID (cp
->insn
), cp
->freq
, hard_regno
);
2881 /* Setup preferred and alternative classes for new pseudo-registers
2882 created by IRA starting with START. */
2884 setup_preferred_alternate_classes_for_new_pseudos (int start
)
2887 int max_regno
= max_reg_num ();
2889 for (i
= start
; i
< max_regno
; i
++)
2891 old_regno
= ORIGINAL_REGNO (regno_reg_rtx
[i
]);
2892 ira_assert (i
!= old_regno
);
2893 setup_reg_classes (i
, reg_preferred_class (old_regno
),
2894 reg_alternate_class (old_regno
),
2895 reg_allocno_class (old_regno
));
2896 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
2897 fprintf (ira_dump_file
,
2898 " New r%d: setting preferred %s, alternative %s\n",
2899 i
, reg_class_names
[reg_preferred_class (old_regno
)],
2900 reg_class_names
[reg_alternate_class (old_regno
)]);
2905 /* The number of entries allocated in reg_info. */
2906 static int allocated_reg_info_size
;
2908 /* Regional allocation can create new pseudo-registers. This function
2909 expands some arrays for pseudo-registers. */
2911 expand_reg_info (void)
2914 int size
= max_reg_num ();
2917 for (i
= allocated_reg_info_size
; i
< size
; i
++)
2918 setup_reg_classes (i
, GENERAL_REGS
, ALL_REGS
, GENERAL_REGS
);
2919 setup_preferred_alternate_classes_for_new_pseudos (allocated_reg_info_size
);
2920 allocated_reg_info_size
= size
;
2923 /* Return TRUE if there is too high register pressure in the function.
2924 It is used to decide when stack slot sharing is worth to do. */
2926 too_high_register_pressure_p (void)
2929 enum reg_class pclass
;
2931 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2933 pclass
= ira_pressure_classes
[i
];
2934 if (ira_loop_tree_root
->reg_pressure
[pclass
] > 10000)
2942 /* Indicate that hard register number FROM was eliminated and replaced with
2943 an offset from hard register number TO. The status of hard registers live
2944 at the start of a basic block is updated by replacing a use of FROM with
2948 mark_elimination (int from
, int to
)
2953 FOR_EACH_BB_FN (bb
, cfun
)
2956 if (bitmap_bit_p (r
, from
))
2958 bitmap_clear_bit (r
, from
);
2959 bitmap_set_bit (r
, to
);
2963 r
= DF_LIVE_IN (bb
);
2964 if (bitmap_bit_p (r
, from
))
2966 bitmap_clear_bit (r
, from
);
2967 bitmap_set_bit (r
, to
);
2974 /* The length of the following array. */
2975 int ira_reg_equiv_len
;
2977 /* Info about equiv. info for each register. */
2978 struct ira_reg_equiv_s
*ira_reg_equiv
;
2980 /* Expand ira_reg_equiv if necessary. */
2982 ira_expand_reg_equiv (void)
2984 int old
= ira_reg_equiv_len
;
2986 if (ira_reg_equiv_len
> max_reg_num ())
2988 ira_reg_equiv_len
= max_reg_num () * 3 / 2 + 1;
2990 = (struct ira_reg_equiv_s
*) xrealloc (ira_reg_equiv
,
2992 * sizeof (struct ira_reg_equiv_s
));
2993 gcc_assert (old
< ira_reg_equiv_len
);
2994 memset (ira_reg_equiv
+ old
, 0,
2995 sizeof (struct ira_reg_equiv_s
) * (ira_reg_equiv_len
- old
));
2999 init_reg_equiv (void)
3001 ira_reg_equiv_len
= 0;
3002 ira_reg_equiv
= NULL
;
3003 ira_expand_reg_equiv ();
3007 finish_reg_equiv (void)
3009 free (ira_reg_equiv
);
3016 /* Set when a REG_EQUIV note is found or created. Use to
3017 keep track of what memory accesses might be created later,
3022 /* The list of each instruction which initializes this register.
3024 NULL indicates we know nothing about this register's equivalence
3027 An INSN_LIST with a NULL insn indicates this pseudo is already
3028 known to not have a valid equivalence. */
3029 rtx_insn_list
*init_insns
;
3031 /* Loop depth is used to recognize equivalences which appear
3032 to be present within the same loop (or in an inner loop). */
3034 /* Nonzero if this had a preexisting REG_EQUIV note. */
3035 unsigned char is_arg_equivalence
: 1;
3036 /* Set when an attempt should be made to replace a register
3037 with the associated src_p entry. */
3038 unsigned char replace
: 1;
3039 /* Set if this register has no known equivalence. */
3040 unsigned char no_equiv
: 1;
3041 /* Set if this register is mentioned in a paradoxical subreg. */
3042 unsigned char pdx_subregs
: 1;
3045 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
3046 structure for that register. */
3047 static struct equivalence
*reg_equiv
;
3049 /* Used for communication between the following two functions. */
3050 struct equiv_mem_data
3052 /* A MEM that we wish to ensure remains unchanged. */
3055 /* Set true if EQUIV_MEM is modified. */
3056 bool equiv_mem_modified
;
3059 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
3060 Called via note_stores. */
3062 validate_equiv_mem_from_store (rtx dest
, const_rtx set ATTRIBUTE_UNUSED
,
3065 struct equiv_mem_data
*info
= (struct equiv_mem_data
*) data
;
3068 && reg_overlap_mentioned_p (dest
, info
->equiv_mem
))
3070 && anti_dependence (info
->equiv_mem
, dest
)))
3071 info
->equiv_mem_modified
= true;
3074 static int equiv_init_varies_p (rtx x
);
3076 enum valid_equiv
{ valid_none
, valid_combine
, valid_reload
};
3078 /* Verify that no store between START and the death of REG invalidates
3079 MEMREF. MEMREF is invalidated by modifying a register used in MEMREF,
3080 by storing into an overlapping memory location, or with a non-const
3083 Return VALID_RELOAD if MEMREF remains valid for both reload and
3084 combine_and_move insns, VALID_COMBINE if only valid for
3085 combine_and_move_insns, and VALID_NONE otherwise. */
3086 static enum valid_equiv
3087 validate_equiv_mem (rtx_insn
*start
, rtx reg
, rtx memref
)
3091 struct equiv_mem_data info
= { memref
, false };
3092 enum valid_equiv ret
= valid_reload
;
3094 /* If the memory reference has side effects or is volatile, it isn't a
3095 valid equivalence. */
3096 if (side_effects_p (memref
))
3099 for (insn
= start
; insn
; insn
= NEXT_INSN (insn
))
3104 if (find_reg_note (insn
, REG_DEAD
, reg
))
3109 /* We can combine a reg def from one insn into a reg use in
3110 another over a call if the memory is readonly or the call
3111 const/pure. However, we can't set reg_equiv notes up for
3112 reload over any call. The problem is the equivalent form
3113 may reference a pseudo which gets assigned a call
3114 clobbered hard reg. When we later replace REG with its
3115 equivalent form, the value in the call-clobbered reg has
3116 been changed and all hell breaks loose. */
3117 ret
= valid_combine
;
3118 if (!MEM_READONLY_P (memref
)
3119 && (!RTL_CONST_OR_PURE_CALL_P (insn
)
3120 || equiv_init_varies_p (XEXP (memref
, 0))))
3124 note_stores (insn
, validate_equiv_mem_from_store
, &info
);
3125 if (info
.equiv_mem_modified
)
3128 /* If a register mentioned in MEMREF is modified via an
3129 auto-increment, we lose the equivalence. Do the same if one
3130 dies; although we could extend the life, it doesn't seem worth
3133 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
3134 if ((REG_NOTE_KIND (note
) == REG_INC
3135 || REG_NOTE_KIND (note
) == REG_DEAD
)
3136 && REG_P (XEXP (note
, 0))
3137 && reg_overlap_mentioned_p (XEXP (note
, 0), memref
))
3144 /* Returns zero if X is known to be invariant. */
3146 equiv_init_varies_p (rtx x
)
3148 RTX_CODE code
= GET_CODE (x
);
3155 return !MEM_READONLY_P (x
) || equiv_init_varies_p (XEXP (x
, 0));
3164 return reg_equiv
[REGNO (x
)].replace
== 0 && rtx_varies_p (x
, 0);
3167 if (MEM_VOLATILE_P (x
))
3176 fmt
= GET_RTX_FORMAT (code
);
3177 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3180 if (equiv_init_varies_p (XEXP (x
, i
)))
3183 else if (fmt
[i
] == 'E')
3186 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
3187 if (equiv_init_varies_p (XVECEXP (x
, i
, j
)))
3194 /* Returns nonzero if X (used to initialize register REGNO) is movable.
3195 X is only movable if the registers it uses have equivalent initializations
3196 which appear to be within the same loop (or in an inner loop) and movable
3197 or if they are not candidates for local_alloc and don't vary. */
3199 equiv_init_movable_p (rtx x
, int regno
)
3203 enum rtx_code code
= GET_CODE (x
);
3208 return equiv_init_movable_p (SET_SRC (x
), regno
);
3222 return ((reg_equiv
[REGNO (x
)].loop_depth
>= reg_equiv
[regno
].loop_depth
3223 && reg_equiv
[REGNO (x
)].replace
)
3224 || (REG_BASIC_BLOCK (REGNO (x
)) < NUM_FIXED_BLOCKS
3225 && ! rtx_varies_p (x
, 0)));
3227 case UNSPEC_VOLATILE
:
3231 if (MEM_VOLATILE_P (x
))
3240 fmt
= GET_RTX_FORMAT (code
);
3241 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3245 if (! equiv_init_movable_p (XEXP (x
, i
), regno
))
3249 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
3250 if (! equiv_init_movable_p (XVECEXP (x
, i
, j
), regno
))
3258 static bool memref_referenced_p (rtx memref
, rtx x
, bool read_p
);
3260 /* Auxiliary function for memref_referenced_p. Process setting X for
3263 process_set_for_memref_referenced_p (rtx memref
, rtx x
)
3265 /* If we are setting a MEM, it doesn't count (its address does), but any
3266 other SET_DEST that has a MEM in it is referencing the MEM. */
3269 if (memref_referenced_p (memref
, XEXP (x
, 0), true))
3272 else if (memref_referenced_p (memref
, x
, false))
3278 /* TRUE if X references a memory location (as a read if READ_P) that
3279 would be affected by a store to MEMREF. */
3281 memref_referenced_p (rtx memref
, rtx x
, bool read_p
)
3285 enum rtx_code code
= GET_CODE (x
);
3299 return (reg_equiv
[REGNO (x
)].replacement
3300 && memref_referenced_p (memref
,
3301 reg_equiv
[REGNO (x
)].replacement
, read_p
));
3304 /* Memory X might have another effective type than MEMREF. */
3305 if (read_p
|| true_dependence (memref
, VOIDmode
, x
))
3310 if (process_set_for_memref_referenced_p (memref
, SET_DEST (x
)))
3313 return memref_referenced_p (memref
, SET_SRC (x
), true);
3316 if (process_set_for_memref_referenced_p (memref
, XEXP (x
, 0)))
3325 if (process_set_for_memref_referenced_p (memref
, XEXP (x
, 0)))
3328 return memref_referenced_p (memref
, XEXP (x
, 0), true);
3332 /* op0 = op0 + op1 */
3333 if (process_set_for_memref_referenced_p (memref
, XEXP (x
, 0)))
3336 if (memref_referenced_p (memref
, XEXP (x
, 0), true))
3339 return memref_referenced_p (memref
, XEXP (x
, 1), true);
3345 fmt
= GET_RTX_FORMAT (code
);
3346 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3350 if (memref_referenced_p (memref
, XEXP (x
, i
), read_p
))
3354 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
3355 if (memref_referenced_p (memref
, XVECEXP (x
, i
, j
), read_p
))
3363 /* TRUE if some insn in the range (START, END] references a memory location
3364 that would be affected by a store to MEMREF.
3366 Callers should not call this routine if START is after END in the
3370 memref_used_between_p (rtx memref
, rtx_insn
*start
, rtx_insn
*end
)
3374 for (insn
= NEXT_INSN (start
);
3375 insn
&& insn
!= NEXT_INSN (end
);
3376 insn
= NEXT_INSN (insn
))
3378 if (!NONDEBUG_INSN_P (insn
))
3381 if (memref_referenced_p (memref
, PATTERN (insn
), false))
3384 /* Nonconst functions may access memory. */
3385 if (CALL_P (insn
) && (! RTL_CONST_CALL_P (insn
)))
3389 gcc_assert (insn
== NEXT_INSN (end
));
3393 /* Mark REG as having no known equivalence.
3394 Some instructions might have been processed before and furnished
3395 with REG_EQUIV notes for this register; these notes will have to be
3397 STORE is the piece of RTL that does the non-constant / conflicting
3398 assignment - a SET, CLOBBER or REG_INC note. It is currently not used,
3399 but needs to be there because this function is called from note_stores. */
3401 no_equiv (rtx reg
, const_rtx store ATTRIBUTE_UNUSED
,
3402 void *data ATTRIBUTE_UNUSED
)
3405 rtx_insn_list
*list
;
3409 regno
= REGNO (reg
);
3410 reg_equiv
[regno
].no_equiv
= 1;
3411 list
= reg_equiv
[regno
].init_insns
;
3412 if (list
&& list
->insn () == NULL
)
3414 reg_equiv
[regno
].init_insns
= gen_rtx_INSN_LIST (VOIDmode
, NULL_RTX
, NULL
);
3415 reg_equiv
[regno
].replacement
= NULL_RTX
;
3416 /* This doesn't matter for equivalences made for argument registers, we
3417 should keep their initialization insns. */
3418 if (reg_equiv
[regno
].is_arg_equivalence
)
3420 ira_reg_equiv
[regno
].defined_p
= false;
3421 ira_reg_equiv
[regno
].caller_save_p
= false;
3422 ira_reg_equiv
[regno
].init_insns
= NULL
;
3423 for (; list
; list
= list
->next ())
3425 rtx_insn
*insn
= list
->insn ();
3426 remove_note (insn
, find_reg_note (insn
, REG_EQUIV
, NULL_RTX
));
3430 /* Check whether the SUBREG is a paradoxical subreg and set the result
3434 set_paradoxical_subreg (rtx_insn
*insn
)
3436 subrtx_iterator::array_type array
;
3437 FOR_EACH_SUBRTX (iter
, array
, PATTERN (insn
), NONCONST
)
3439 const_rtx subreg
= *iter
;
3440 if (GET_CODE (subreg
) == SUBREG
)
3442 const_rtx reg
= SUBREG_REG (subreg
);
3443 if (REG_P (reg
) && paradoxical_subreg_p (subreg
))
3444 reg_equiv
[REGNO (reg
)].pdx_subregs
= true;
3449 /* In DEBUG_INSN location adjust REGs from CLEARED_REGS bitmap to the
3450 equivalent replacement. */
3453 adjust_cleared_regs (rtx loc
, const_rtx old_rtx ATTRIBUTE_UNUSED
, void *data
)
3457 bitmap cleared_regs
= (bitmap
) data
;
3458 if (bitmap_bit_p (cleared_regs
, REGNO (loc
)))
3459 return simplify_replace_fn_rtx (copy_rtx (*reg_equiv
[REGNO (loc
)].src_p
),
3460 NULL_RTX
, adjust_cleared_regs
, data
);
3465 /* Given register REGNO is set only once, return true if the defining
3466 insn dominates all uses. */
3469 def_dominates_uses (int regno
)
3471 df_ref def
= DF_REG_DEF_CHAIN (regno
);
3473 struct df_insn_info
*def_info
= DF_REF_INSN_INFO (def
);
3474 /* If this is an artificial def (eh handler regs, hard frame pointer
3475 for non-local goto, regs defined on function entry) then def_info
3476 is NULL and the reg is always live before any use. We might
3477 reasonably return true in that case, but since the only call
3478 of this function is currently here in ira.cc when we are looking
3479 at a defining insn we can't have an artificial def as that would
3480 bump DF_REG_DEF_COUNT. */
3481 gcc_assert (DF_REG_DEF_COUNT (regno
) == 1 && def_info
!= NULL
);
3483 rtx_insn
*def_insn
= DF_REF_INSN (def
);
3484 basic_block def_bb
= BLOCK_FOR_INSN (def_insn
);
3486 for (df_ref use
= DF_REG_USE_CHAIN (regno
);
3488 use
= DF_REF_NEXT_REG (use
))
3490 struct df_insn_info
*use_info
= DF_REF_INSN_INFO (use
);
3491 /* Only check real uses, not artificial ones. */
3494 rtx_insn
*use_insn
= DF_REF_INSN (use
);
3495 if (!DEBUG_INSN_P (use_insn
))
3497 basic_block use_bb
= BLOCK_FOR_INSN (use_insn
);
3498 if (use_bb
!= def_bb
3499 ? !dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
)
3500 : DF_INSN_INFO_LUID (use_info
) < DF_INSN_INFO_LUID (def_info
))
3508 /* Scan the instructions before update_equiv_regs. Record which registers
3509 are referenced as paradoxical subregs. Also check for cases in which
3510 the current function needs to save a register that one of its call
3511 instructions clobbers.
3513 These things are logically unrelated, but it's more efficient to do
3517 update_equiv_regs_prescan (void)
3521 function_abi_aggregator callee_abis
;
3523 FOR_EACH_BB_FN (bb
, cfun
)
3524 FOR_BB_INSNS (bb
, insn
)
3525 if (NONDEBUG_INSN_P (insn
))
3527 set_paradoxical_subreg (insn
);
3529 callee_abis
.note_callee_abi (insn_callee_abi (insn
));
3532 HARD_REG_SET extra_caller_saves
= callee_abis
.caller_save_regs (*crtl
->abi
);
3533 if (!hard_reg_set_empty_p (extra_caller_saves
))
3534 for (unsigned int regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; ++regno
)
3535 if (TEST_HARD_REG_BIT (extra_caller_saves
, regno
))
3536 df_set_regs_ever_live (regno
, true);
3539 /* Find registers that are equivalent to a single value throughout the
3540 compilation (either because they can be referenced in memory or are
3541 set once from a single constant). Lower their priority for a
3544 If such a register is only referenced once, try substituting its
3545 value into the using insn. If it succeeds, we can eliminate the
3546 register completely.
3548 Initialize init_insns in ira_reg_equiv array. */
3550 update_equiv_regs (void)
3555 /* Scan the insns and find which registers have equivalences. Do this
3556 in a separate scan of the insns because (due to -fcse-follow-jumps)
3557 a register can be set below its use. */
3558 bitmap setjmp_crosses
= regstat_get_setjmp_crosses ();
3559 FOR_EACH_BB_FN (bb
, cfun
)
3561 int loop_depth
= bb_loop_depth (bb
);
3563 for (insn
= BB_HEAD (bb
);
3564 insn
!= NEXT_INSN (BB_END (bb
));
3565 insn
= NEXT_INSN (insn
))
3572 if (! INSN_P (insn
))
3575 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
3576 if (REG_NOTE_KIND (note
) == REG_INC
)
3577 no_equiv (XEXP (note
, 0), note
, NULL
);
3579 set
= single_set (insn
);
3581 /* If this insn contains more (or less) than a single SET,
3582 only mark all destinations as having no known equivalence. */
3584 || side_effects_p (SET_SRC (set
)))
3586 note_pattern_stores (PATTERN (insn
), no_equiv
, NULL
);
3589 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
3593 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
3595 rtx part
= XVECEXP (PATTERN (insn
), 0, i
);
3597 note_pattern_stores (part
, no_equiv
, NULL
);
3601 dest
= SET_DEST (set
);
3602 src
= SET_SRC (set
);
3604 /* See if this is setting up the equivalence between an argument
3605 register and its stack slot. */
3606 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
3609 gcc_assert (REG_P (dest
));
3610 regno
= REGNO (dest
);
3612 /* Note that we don't want to clear init_insns in
3613 ira_reg_equiv even if there are multiple sets of this
3615 reg_equiv
[regno
].is_arg_equivalence
= 1;
3617 /* The insn result can have equivalence memory although
3618 the equivalence is not set up by the insn. We add
3619 this insn to init insns as it is a flag for now that
3620 regno has an equivalence. We will remove the insn
3621 from init insn list later. */
3622 if (rtx_equal_p (src
, XEXP (note
, 0)) || MEM_P (XEXP (note
, 0)))
3623 ira_reg_equiv
[regno
].init_insns
3624 = gen_rtx_INSN_LIST (VOIDmode
, insn
,
3625 ira_reg_equiv
[regno
].init_insns
);
3627 /* Continue normally in case this is a candidate for
3634 /* We only handle the case of a pseudo register being set
3635 once, or always to the same value. */
3636 /* ??? The mn10200 port breaks if we add equivalences for
3637 values that need an ADDRESS_REGS register and set them equivalent
3638 to a MEM of a pseudo. The actual problem is in the over-conservative
3639 handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
3640 calculate_needs, but we traditionally work around this problem
3641 here by rejecting equivalences when the destination is in a register
3642 that's likely spilled. This is fragile, of course, since the
3643 preferred class of a pseudo depends on all instructions that set
3647 || (regno
= REGNO (dest
)) < FIRST_PSEUDO_REGISTER
3648 || (reg_equiv
[regno
].init_insns
3649 && reg_equiv
[regno
].init_insns
->insn () == NULL
)
3650 || (targetm
.class_likely_spilled_p (reg_preferred_class (regno
))
3651 && MEM_P (src
) && ! reg_equiv
[regno
].is_arg_equivalence
))
3653 /* This might be setting a SUBREG of a pseudo, a pseudo that is
3654 also set somewhere else to a constant. */
3655 note_pattern_stores (set
, no_equiv
, NULL
);
3659 /* Don't set reg mentioned in a paradoxical subreg
3660 equivalent to a mem. */
3661 if (MEM_P (src
) && reg_equiv
[regno
].pdx_subregs
)
3663 note_pattern_stores (set
, no_equiv
, NULL
);
3667 note
= find_reg_note (insn
, REG_EQUAL
, NULL_RTX
);
3669 /* cse sometimes generates function invariants, but doesn't put a
3670 REG_EQUAL note on the insn. Since this note would be redundant,
3671 there's no point creating it earlier than here. */
3672 if (! note
&& ! rtx_varies_p (src
, 0))
3673 note
= set_unique_reg_note (insn
, REG_EQUAL
, copy_rtx (src
));
3675 /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
3676 since it represents a function call. */
3677 if (note
&& GET_CODE (XEXP (note
, 0)) == EXPR_LIST
)
3680 if (DF_REG_DEF_COUNT (regno
) != 1)
3682 bool equal_p
= true;
3683 rtx_insn_list
*list
;
3685 /* If we have already processed this pseudo and determined it
3686 cannot have an equivalence, then honor that decision. */
3687 if (reg_equiv
[regno
].no_equiv
)
3691 || rtx_varies_p (XEXP (note
, 0), 0)
3692 || (reg_equiv
[regno
].replacement
3693 && ! rtx_equal_p (XEXP (note
, 0),
3694 reg_equiv
[regno
].replacement
)))
3696 no_equiv (dest
, set
, NULL
);
3700 list
= reg_equiv
[regno
].init_insns
;
3701 for (; list
; list
= list
->next ())
3706 insn_tmp
= list
->insn ();
3707 note_tmp
= find_reg_note (insn_tmp
, REG_EQUAL
, NULL_RTX
);
3708 gcc_assert (note_tmp
);
3709 if (! rtx_equal_p (XEXP (note
, 0), XEXP (note_tmp
, 0)))
3718 no_equiv (dest
, set
, NULL
);
3723 /* Record this insn as initializing this register. */
3724 reg_equiv
[regno
].init_insns
3725 = gen_rtx_INSN_LIST (VOIDmode
, insn
, reg_equiv
[regno
].init_insns
);
3727 /* If this register is known to be equal to a constant, record that
3728 it is always equivalent to the constant.
3729 Note that it is possible to have a register use before
3730 the def in loops (see gcc.c-torture/execute/pr79286.c)
3731 where the reg is undefined on first use. If the def insn
3732 won't trap we can use it as an equivalence, effectively
3733 choosing the "undefined" value for the reg to be the
3734 same as the value set by the def. */
3735 if (DF_REG_DEF_COUNT (regno
) == 1
3737 && !rtx_varies_p (XEXP (note
, 0), 0)
3738 && (!may_trap_or_fault_p (XEXP (note
, 0))
3739 || def_dominates_uses (regno
)))
3741 rtx note_value
= XEXP (note
, 0);
3742 remove_note (insn
, note
);
3743 set_unique_reg_note (insn
, REG_EQUIV
, note_value
);
3746 /* If this insn introduces a "constant" register, decrease the priority
3747 of that register. Record this insn if the register is only used once
3748 more and the equivalence value is the same as our source.
3750 The latter condition is checked for two reasons: First, it is an
3751 indication that it may be more efficient to actually emit the insn
3752 as written (if no registers are available, reload will substitute
3753 the equivalence). Secondly, it avoids problems with any registers
3754 dying in this insn whose death notes would be missed.
3756 If we don't have a REG_EQUIV note, see if this insn is loading
3757 a register used only in one basic block from a MEM. If so, and the
3758 MEM remains unchanged for the life of the register, add a REG_EQUIV
3760 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
3762 rtx replacement
= NULL_RTX
;
3764 replacement
= XEXP (note
, 0);
3765 else if (REG_BASIC_BLOCK (regno
) >= NUM_FIXED_BLOCKS
3766 && MEM_P (SET_SRC (set
)))
3768 enum valid_equiv validity
;
3769 validity
= validate_equiv_mem (insn
, dest
, SET_SRC (set
));
3770 if (validity
!= valid_none
)
3772 replacement
= copy_rtx (SET_SRC (set
));
3773 if (validity
== valid_reload
)
3775 note
= set_unique_reg_note (insn
, REG_EQUIV
, replacement
);
3777 else if (ira_use_lra_p
)
3779 /* We still can use this equivalence for caller save
3780 optimization in LRA. Mark this. */
3781 ira_reg_equiv
[regno
].caller_save_p
= true;
3782 ira_reg_equiv
[regno
].init_insns
3783 = gen_rtx_INSN_LIST (VOIDmode
, insn
,
3784 ira_reg_equiv
[regno
].init_insns
);
3789 /* If we haven't done so, record for reload that this is an
3790 equivalencing insn. */
3791 if (note
&& !reg_equiv
[regno
].is_arg_equivalence
)
3792 ira_reg_equiv
[regno
].init_insns
3793 = gen_rtx_INSN_LIST (VOIDmode
, insn
,
3794 ira_reg_equiv
[regno
].init_insns
);
3798 reg_equiv
[regno
].replacement
= replacement
;
3799 reg_equiv
[regno
].src_p
= &SET_SRC (set
);
3800 reg_equiv
[regno
].loop_depth
= (short) loop_depth
;
3802 /* Don't mess with things live during setjmp. */
3803 if (optimize
&& !bitmap_bit_p (setjmp_crosses
, regno
))
3805 /* If the register is referenced exactly twice, meaning it is
3806 set once and used once, indicate that the reference may be
3807 replaced by the equivalence we computed above. Do this
3808 even if the register is only used in one block so that
3809 dependencies can be handled where the last register is
3810 used in a different block (i.e. HIGH / LO_SUM sequences)
3811 and to reduce the number of registers alive across
3814 if (REG_N_REFS (regno
) == 2
3815 && (rtx_equal_p (replacement
, src
)
3816 || ! equiv_init_varies_p (src
))
3817 && NONJUMP_INSN_P (insn
)
3818 && equiv_init_movable_p (PATTERN (insn
), regno
))
3819 reg_equiv
[regno
].replace
= 1;
3826 /* For insns that set a MEM to the contents of a REG that is only used
3827 in a single basic block, see if the register is always equivalent
3828 to that memory location and if moving the store from INSN to the
3829 insn that sets REG is safe. If so, put a REG_EQUIV note on the
3830 initializing insn. */
3832 add_store_equivs (void)
3834 auto_bitmap seen_insns
;
3836 for (rtx_insn
*insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
3840 rtx_insn
*init_insn
;
3842 bitmap_set_bit (seen_insns
, INSN_UID (insn
));
3844 if (! INSN_P (insn
))
3847 set
= single_set (insn
);
3851 dest
= SET_DEST (set
);
3852 src
= SET_SRC (set
);
3854 /* Don't add a REG_EQUIV note if the insn already has one. The existing
3855 REG_EQUIV is likely more useful than the one we are adding. */
3856 if (MEM_P (dest
) && REG_P (src
)
3857 && (regno
= REGNO (src
)) >= FIRST_PSEUDO_REGISTER
3858 && REG_BASIC_BLOCK (regno
) >= NUM_FIXED_BLOCKS
3859 && DF_REG_DEF_COUNT (regno
) == 1
3860 && ! reg_equiv
[regno
].pdx_subregs
3861 && reg_equiv
[regno
].init_insns
!= NULL
3862 && (init_insn
= reg_equiv
[regno
].init_insns
->insn ()) != 0
3863 && bitmap_bit_p (seen_insns
, INSN_UID (init_insn
))
3864 && ! find_reg_note (init_insn
, REG_EQUIV
, NULL_RTX
)
3865 && validate_equiv_mem (init_insn
, src
, dest
) == valid_reload
3866 && ! memref_used_between_p (dest
, init_insn
, insn
)
3867 /* Attaching a REG_EQUIV note will fail if INIT_INSN has
3869 && set_unique_reg_note (init_insn
, REG_EQUIV
, copy_rtx (dest
)))
3871 /* This insn makes the equivalence, not the one initializing
3873 ira_reg_equiv
[regno
].init_insns
3874 = gen_rtx_INSN_LIST (VOIDmode
, insn
, NULL_RTX
);
3875 df_notes_rescan (init_insn
);
3878 "Adding REG_EQUIV to insn %d for source of insn %d\n",
3879 INSN_UID (init_insn
),
3885 /* Scan all regs killed in an insn to see if any of them are registers
3886 only used that once. If so, see if we can replace the reference
3887 with the equivalent form. If we can, delete the initializing
3888 reference and this register will go away. If we can't replace the
3889 reference, and the initializing reference is within the same loop
3890 (or in an inner loop), then move the register initialization just
3891 before the use, so that they are in the same basic block. */
3893 combine_and_move_insns (void)
3895 auto_bitmap cleared_regs
;
3896 int max
= max_reg_num ();
3898 for (int regno
= FIRST_PSEUDO_REGISTER
; regno
< max
; regno
++)
3900 if (!reg_equiv
[regno
].replace
)
3903 rtx_insn
*use_insn
= 0;
3904 for (df_ref use
= DF_REG_USE_CHAIN (regno
);
3906 use
= DF_REF_NEXT_REG (use
))
3907 if (DF_REF_INSN_INFO (use
))
3909 if (DEBUG_INSN_P (DF_REF_INSN (use
)))
3911 gcc_assert (!use_insn
);
3912 use_insn
= DF_REF_INSN (use
);
3914 gcc_assert (use_insn
);
3916 /* Don't substitute into jumps. indirect_jump_optimize does
3917 this for anything we are prepared to handle. */
3918 if (JUMP_P (use_insn
))
3921 /* Also don't substitute into a conditional trap insn -- it can become
3922 an unconditional trap, and that is a flow control insn. */
3923 if (GET_CODE (PATTERN (use_insn
)) == TRAP_IF
)
3926 df_ref def
= DF_REG_DEF_CHAIN (regno
);
3927 gcc_assert (DF_REG_DEF_COUNT (regno
) == 1 && DF_REF_INSN_INFO (def
));
3928 rtx_insn
*def_insn
= DF_REF_INSN (def
);
3930 /* We may not move instructions that can throw, since that
3931 changes basic block boundaries and we are not prepared to
3932 adjust the CFG to match. */
3933 if (can_throw_internal (def_insn
))
3936 /* Instructions with multiple sets can only be moved if DF analysis is
3937 performed for all of the registers set. See PR91052. */
3938 if (multiple_sets (def_insn
))
3941 basic_block use_bb
= BLOCK_FOR_INSN (use_insn
);
3942 basic_block def_bb
= BLOCK_FOR_INSN (def_insn
);
3943 if (bb_loop_depth (use_bb
) > bb_loop_depth (def_bb
))
3946 if (asm_noperands (PATTERN (def_insn
)) < 0
3947 && validate_replace_rtx (regno_reg_rtx
[regno
],
3948 *reg_equiv
[regno
].src_p
, use_insn
))
3951 /* Append the REG_DEAD notes from def_insn. */
3952 for (rtx
*p
= ®_NOTES (def_insn
); (link
= *p
) != 0; )
3954 if (REG_NOTE_KIND (XEXP (link
, 0)) == REG_DEAD
)
3956 *p
= XEXP (link
, 1);
3957 XEXP (link
, 1) = REG_NOTES (use_insn
);
3958 REG_NOTES (use_insn
) = link
;
3961 p
= &XEXP (link
, 1);
3964 remove_death (regno
, use_insn
);
3965 SET_REG_N_REFS (regno
, 0);
3966 REG_FREQ (regno
) = 0;
3968 FOR_EACH_INSN_USE (use
, def_insn
)
3970 unsigned int use_regno
= DF_REF_REGNO (use
);
3971 if (!HARD_REGISTER_NUM_P (use_regno
))
3972 reg_equiv
[use_regno
].replace
= 0;
3975 delete_insn (def_insn
);
3977 reg_equiv
[regno
].init_insns
= NULL
;
3978 ira_reg_equiv
[regno
].init_insns
= NULL
;
3979 bitmap_set_bit (cleared_regs
, regno
);
3982 /* Move the initialization of the register to just before
3983 USE_INSN. Update the flow information. */
3984 else if (prev_nondebug_insn (use_insn
) != def_insn
)
3988 new_insn
= emit_insn_before (PATTERN (def_insn
), use_insn
);
3989 REG_NOTES (new_insn
) = REG_NOTES (def_insn
);
3990 REG_NOTES (def_insn
) = 0;
3991 /* Rescan it to process the notes. */
3992 df_insn_rescan (new_insn
);
3994 /* Make sure this insn is recognized before reload begins,
3995 otherwise eliminate_regs_in_insn will die. */
3996 INSN_CODE (new_insn
) = INSN_CODE (def_insn
);
3998 delete_insn (def_insn
);
4000 XEXP (reg_equiv
[regno
].init_insns
, 0) = new_insn
;
4002 REG_BASIC_BLOCK (regno
) = use_bb
->index
;
4003 REG_N_CALLS_CROSSED (regno
) = 0;
4005 if (use_insn
== BB_HEAD (use_bb
))
4006 BB_HEAD (use_bb
) = new_insn
;
4008 /* We know regno dies in use_insn, but inside a loop
4009 REG_DEAD notes might be missing when def_insn was in
4010 another basic block. However, when we move def_insn into
4011 this bb we'll definitely get a REG_DEAD note and reload
4012 will see the death. It's possible that update_equiv_regs
4013 set up an equivalence referencing regno for a reg set by
4014 use_insn, when regno was seen as non-local. Now that
4015 regno is local to this block, and dies, such an
4016 equivalence is invalid. */
4017 if (find_reg_note (use_insn
, REG_EQUIV
, regno_reg_rtx
[regno
]))
4019 rtx set
= single_set (use_insn
);
4020 if (set
&& REG_P (SET_DEST (set
)))
4021 no_equiv (SET_DEST (set
), set
, NULL
);
4024 ira_reg_equiv
[regno
].init_insns
4025 = gen_rtx_INSN_LIST (VOIDmode
, new_insn
, NULL_RTX
);
4026 bitmap_set_bit (cleared_regs
, regno
);
4030 if (!bitmap_empty_p (cleared_regs
))
4034 FOR_EACH_BB_FN (bb
, cfun
)
4036 bitmap_and_compl_into (DF_LR_IN (bb
), cleared_regs
);
4037 bitmap_and_compl_into (DF_LR_OUT (bb
), cleared_regs
);
4040 bitmap_and_compl_into (DF_LIVE_IN (bb
), cleared_regs
);
4041 bitmap_and_compl_into (DF_LIVE_OUT (bb
), cleared_regs
);
4044 /* Last pass - adjust debug insns referencing cleared regs. */
4045 if (MAY_HAVE_DEBUG_BIND_INSNS
)
4046 for (rtx_insn
*insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
4047 if (DEBUG_BIND_INSN_P (insn
))
4049 rtx old_loc
= INSN_VAR_LOCATION_LOC (insn
);
4050 INSN_VAR_LOCATION_LOC (insn
)
4051 = simplify_replace_fn_rtx (old_loc
, NULL_RTX
,
4052 adjust_cleared_regs
,
4053 (void *) cleared_regs
);
4054 if (old_loc
!= INSN_VAR_LOCATION_LOC (insn
))
4055 df_insn_rescan (insn
);
4060 /* A pass over indirect jumps, converting simple cases to direct jumps.
4061 Combine does this optimization too, but only within a basic block. */
4063 indirect_jump_optimize (void)
4066 bool rebuild_p
= false;
4068 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
4070 rtx_insn
*insn
= BB_END (bb
);
4072 || find_reg_note (insn
, REG_NON_LOCAL_GOTO
, NULL_RTX
))
4075 rtx x
= pc_set (insn
);
4076 if (!x
|| !REG_P (SET_SRC (x
)))
4079 int regno
= REGNO (SET_SRC (x
));
4080 if (DF_REG_DEF_COUNT (regno
) == 1)
4082 df_ref def
= DF_REG_DEF_CHAIN (regno
);
4083 if (!DF_REF_IS_ARTIFICIAL (def
))
4085 rtx_insn
*def_insn
= DF_REF_INSN (def
);
4087 rtx set
= single_set (def_insn
);
4088 if (set
&& GET_CODE (SET_SRC (set
)) == LABEL_REF
)
4089 lab
= SET_SRC (set
);
4092 rtx eqnote
= find_reg_note (def_insn
, REG_EQUAL
, NULL_RTX
);
4093 if (eqnote
&& GET_CODE (XEXP (eqnote
, 0)) == LABEL_REF
)
4094 lab
= XEXP (eqnote
, 0);
4096 if (lab
&& validate_replace_rtx (SET_SRC (x
), lab
, insn
))
4104 timevar_push (TV_JUMP
);
4105 rebuild_jump_labels (get_insns ());
4106 if (purge_all_dead_edges ())
4107 delete_unreachable_blocks ();
4108 timevar_pop (TV_JUMP
);
4112 /* Set up fields memory, constant, and invariant from init_insns in
4113 the structures of array ira_reg_equiv. */
4115 setup_reg_equiv (void)
4118 rtx_insn_list
*elem
, *prev_elem
, *next_elem
;
4122 for (i
= FIRST_PSEUDO_REGISTER
; i
< ira_reg_equiv_len
; i
++)
4123 for (prev_elem
= NULL
, elem
= ira_reg_equiv
[i
].init_insns
;
4125 prev_elem
= elem
, elem
= next_elem
)
4127 next_elem
= elem
->next ();
4128 insn
= elem
->insn ();
4129 set
= single_set (insn
);
4131 /* Init insns can set up equivalence when the reg is a destination or
4132 a source (in this case the destination is memory). */
4133 if (set
!= 0 && (REG_P (SET_DEST (set
)) || REG_P (SET_SRC (set
))))
4135 if ((x
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
)) != NULL
)
4138 if (REG_P (SET_DEST (set
))
4139 && REGNO (SET_DEST (set
)) == (unsigned int) i
4140 && ! rtx_equal_p (SET_SRC (set
), x
) && MEM_P (x
))
4142 /* This insn reporting the equivalence but
4143 actually not setting it. Remove it from the
4145 if (prev_elem
== NULL
)
4146 ira_reg_equiv
[i
].init_insns
= next_elem
;
4148 XEXP (prev_elem
, 1) = next_elem
;
4152 else if (REG_P (SET_DEST (set
))
4153 && REGNO (SET_DEST (set
)) == (unsigned int) i
)
4157 gcc_assert (REG_P (SET_SRC (set
))
4158 && REGNO (SET_SRC (set
)) == (unsigned int) i
);
4161 if (! function_invariant_p (x
)
4163 /* A function invariant is often CONSTANT_P but may
4164 include a register. We promise to only pass
4165 CONSTANT_P objects to LEGITIMATE_PIC_OPERAND_P. */
4166 || (CONSTANT_P (x
) && LEGITIMATE_PIC_OPERAND_P (x
)))
4168 /* It can happen that a REG_EQUIV note contains a MEM
4169 that is not a legitimate memory operand. As later
4170 stages of reload assume that all addresses found in
4171 the lra_regno_equiv_* arrays were originally
4172 legitimate, we ignore such REG_EQUIV notes. */
4173 if (memory_operand (x
, VOIDmode
))
4175 ira_reg_equiv
[i
].defined_p
= !ira_reg_equiv
[i
].caller_save_p
;
4176 ira_reg_equiv
[i
].memory
= x
;
4179 else if (function_invariant_p (x
))
4183 mode
= GET_MODE (SET_DEST (set
));
4184 if (GET_CODE (x
) == PLUS
4185 || x
== frame_pointer_rtx
|| x
== arg_pointer_rtx
)
4186 /* This is PLUS of frame pointer and a constant,
4188 ira_reg_equiv
[i
].invariant
= x
;
4189 else if (targetm
.legitimate_constant_p (mode
, x
))
4190 ira_reg_equiv
[i
].constant
= x
;
4193 ira_reg_equiv
[i
].memory
= force_const_mem (mode
, x
);
4194 if (ira_reg_equiv
[i
].memory
== NULL_RTX
)
4196 ira_reg_equiv
[i
].defined_p
= false;
4197 ira_reg_equiv
[i
].caller_save_p
= false;
4198 ira_reg_equiv
[i
].init_insns
= NULL
;
4202 ira_reg_equiv
[i
].defined_p
= true;
4207 ira_reg_equiv
[i
].defined_p
= false;
4208 ira_reg_equiv
[i
].caller_save_p
= false;
4209 ira_reg_equiv
[i
].init_insns
= NULL
;
4216 /* Print chain C to FILE. */
4218 print_insn_chain (FILE *file
, class insn_chain
*c
)
4220 fprintf (file
, "insn=%d, ", INSN_UID (c
->insn
));
4221 bitmap_print (file
, &c
->live_throughout
, "live_throughout: ", ", ");
4222 bitmap_print (file
, &c
->dead_or_set
, "dead_or_set: ", "\n");
4226 /* Print all reload_insn_chains to FILE. */
4228 print_insn_chains (FILE *file
)
4230 class insn_chain
*c
;
4231 for (c
= reload_insn_chain
; c
; c
= c
->next
)
4232 print_insn_chain (file
, c
);
4235 /* Return true if pseudo REGNO should be added to set live_throughout
4236 or dead_or_set of the insn chains for reload consideration. */
4238 pseudo_for_reload_consideration_p (int regno
)
4240 /* Consider spilled pseudos too for IRA because they still have a
4241 chance to get hard-registers in the reload when IRA is used. */
4242 return (reg_renumber
[regno
] >= 0 || ira_conflicts_p
);
4245 /* Return true if we can track the individual bytes of subreg X.
4246 When returning true, set *OUTER_SIZE to the number of bytes in
4247 X itself, *INNER_SIZE to the number of bytes in the inner register
4248 and *START to the offset of the first byte. */
4250 get_subreg_tracking_sizes (rtx x
, HOST_WIDE_INT
*outer_size
,
4251 HOST_WIDE_INT
*inner_size
, HOST_WIDE_INT
*start
)
4253 rtx reg
= regno_reg_rtx
[REGNO (SUBREG_REG (x
))];
4254 return (GET_MODE_SIZE (GET_MODE (x
)).is_constant (outer_size
)
4255 && GET_MODE_SIZE (GET_MODE (reg
)).is_constant (inner_size
)
4256 && SUBREG_BYTE (x
).is_constant (start
));
4259 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] for
4260 a register with SIZE bytes, making the register live if INIT_VALUE. */
4262 init_live_subregs (bool init_value
, sbitmap
*live_subregs
,
4263 bitmap live_subregs_used
, int allocnum
, int size
)
4265 gcc_assert (size
> 0);
4267 /* Been there, done that. */
4268 if (bitmap_bit_p (live_subregs_used
, allocnum
))
4271 /* Create a new one. */
4272 if (live_subregs
[allocnum
] == NULL
)
4273 live_subregs
[allocnum
] = sbitmap_alloc (size
);
4275 /* If the entire reg was live before blasting into subregs, we need
4276 to init all of the subregs to ones else init to 0. */
4278 bitmap_ones (live_subregs
[allocnum
]);
4280 bitmap_clear (live_subregs
[allocnum
]);
4282 bitmap_set_bit (live_subregs_used
, allocnum
);
4285 /* Walk the insns of the current function and build reload_insn_chain,
4286 and record register life information. */
4288 build_insn_chain (void)
4291 class insn_chain
**p
= &reload_insn_chain
;
4293 class insn_chain
*c
= NULL
;
4294 class insn_chain
*next
= NULL
;
4295 auto_bitmap live_relevant_regs
;
4296 auto_bitmap elim_regset
;
4297 /* live_subregs is a vector used to keep accurate information about
4298 which hardregs are live in multiword pseudos. live_subregs and
4299 live_subregs_used are indexed by pseudo number. The live_subreg
4300 entry for a particular pseudo is only used if the corresponding
4301 element is non zero in live_subregs_used. The sbitmap size of
4302 live_subreg[allocno] is number of bytes that the pseudo can
4304 sbitmap
*live_subregs
= XCNEWVEC (sbitmap
, max_regno
);
4305 auto_bitmap live_subregs_used
;
4307 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
4308 if (TEST_HARD_REG_BIT (eliminable_regset
, i
))
4309 bitmap_set_bit (elim_regset
, i
);
4310 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
4315 CLEAR_REG_SET (live_relevant_regs
);
4316 bitmap_clear (live_subregs_used
);
4318 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb
), 0, i
, bi
)
4320 if (i
>= FIRST_PSEUDO_REGISTER
)
4322 bitmap_set_bit (live_relevant_regs
, i
);
4325 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb
),
4326 FIRST_PSEUDO_REGISTER
, i
, bi
)
4328 if (pseudo_for_reload_consideration_p (i
))
4329 bitmap_set_bit (live_relevant_regs
, i
);
4332 FOR_BB_INSNS_REVERSE (bb
, insn
)
4334 if (!NOTE_P (insn
) && !BARRIER_P (insn
))
4336 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
4339 c
= new_insn_chain ();
4346 c
->block
= bb
->index
;
4348 if (NONDEBUG_INSN_P (insn
))
4349 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
4351 unsigned int regno
= DF_REF_REGNO (def
);
4353 /* Ignore may clobbers because these are generated
4354 from calls. However, every other kind of def is
4355 added to dead_or_set. */
4356 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
4358 if (regno
< FIRST_PSEUDO_REGISTER
)
4360 if (!fixed_regs
[regno
])
4361 bitmap_set_bit (&c
->dead_or_set
, regno
);
4363 else if (pseudo_for_reload_consideration_p (regno
))
4364 bitmap_set_bit (&c
->dead_or_set
, regno
);
4367 if ((regno
< FIRST_PSEUDO_REGISTER
4368 || reg_renumber
[regno
] >= 0
4370 && (!DF_REF_FLAGS_IS_SET (def
, DF_REF_CONDITIONAL
)))
4372 rtx reg
= DF_REF_REG (def
);
4373 HOST_WIDE_INT outer_size
, inner_size
, start
;
4375 /* We can usually track the liveness of individual
4376 bytes within a subreg. The only exceptions are
4377 subregs wrapped in ZERO_EXTRACTs and subregs whose
4378 size is not known; in those cases we need to be
4379 conservative and treat the definition as a partial
4380 definition of the full register rather than a full
4381 definition of a specific part of the register. */
4382 if (GET_CODE (reg
) == SUBREG
4383 && !DF_REF_FLAGS_IS_SET (def
, DF_REF_ZERO_EXTRACT
)
4384 && get_subreg_tracking_sizes (reg
, &outer_size
,
4385 &inner_size
, &start
))
4387 HOST_WIDE_INT last
= start
+ outer_size
;
4390 (bitmap_bit_p (live_relevant_regs
, regno
),
4391 live_subregs
, live_subregs_used
, regno
,
4394 if (!DF_REF_FLAGS_IS_SET
4395 (def
, DF_REF_STRICT_LOW_PART
))
4397 /* Expand the range to cover entire words.
4398 Bytes added here are "don't care". */
4400 = start
/ UNITS_PER_WORD
* UNITS_PER_WORD
;
4401 last
= ((last
+ UNITS_PER_WORD
- 1)
4402 / UNITS_PER_WORD
* UNITS_PER_WORD
);
4405 /* Ignore the paradoxical bits. */
4406 if (last
> SBITMAP_SIZE (live_subregs
[regno
]))
4407 last
= SBITMAP_SIZE (live_subregs
[regno
]);
4409 while (start
< last
)
4411 bitmap_clear_bit (live_subregs
[regno
], start
);
4415 if (bitmap_empty_p (live_subregs
[regno
]))
4417 bitmap_clear_bit (live_subregs_used
, regno
);
4418 bitmap_clear_bit (live_relevant_regs
, regno
);
4421 /* Set live_relevant_regs here because
4422 that bit has to be true to get us to
4423 look at the live_subregs fields. */
4424 bitmap_set_bit (live_relevant_regs
, regno
);
4428 /* DF_REF_PARTIAL is generated for
4429 subregs, STRICT_LOW_PART, and
4430 ZERO_EXTRACT. We handle the subreg
4431 case above so here we have to keep from
4432 modeling the def as a killing def. */
4433 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
))
4435 bitmap_clear_bit (live_subregs_used
, regno
);
4436 bitmap_clear_bit (live_relevant_regs
, regno
);
4442 bitmap_and_compl_into (live_relevant_regs
, elim_regset
);
4443 bitmap_copy (&c
->live_throughout
, live_relevant_regs
);
4445 if (NONDEBUG_INSN_P (insn
))
4446 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
4448 unsigned int regno
= DF_REF_REGNO (use
);
4449 rtx reg
= DF_REF_REG (use
);
4451 /* DF_REF_READ_WRITE on a use means that this use
4452 is fabricated from a def that is a partial set
4453 to a multiword reg. Here, we only model the
4454 subreg case that is not wrapped in ZERO_EXTRACT
4455 precisely so we do not need to look at the
4457 if (DF_REF_FLAGS_IS_SET (use
, DF_REF_READ_WRITE
)
4458 && !DF_REF_FLAGS_IS_SET (use
, DF_REF_ZERO_EXTRACT
)
4459 && DF_REF_FLAGS_IS_SET (use
, DF_REF_SUBREG
))
4462 /* Add the last use of each var to dead_or_set. */
4463 if (!bitmap_bit_p (live_relevant_regs
, regno
))
4465 if (regno
< FIRST_PSEUDO_REGISTER
)
4467 if (!fixed_regs
[regno
])
4468 bitmap_set_bit (&c
->dead_or_set
, regno
);
4470 else if (pseudo_for_reload_consideration_p (regno
))
4471 bitmap_set_bit (&c
->dead_or_set
, regno
);
4474 if (regno
< FIRST_PSEUDO_REGISTER
4475 || pseudo_for_reload_consideration_p (regno
))
4477 HOST_WIDE_INT outer_size
, inner_size
, start
;
4478 if (GET_CODE (reg
) == SUBREG
4479 && !DF_REF_FLAGS_IS_SET (use
,
4481 | DF_REF_ZERO_EXTRACT
)
4482 && get_subreg_tracking_sizes (reg
, &outer_size
,
4483 &inner_size
, &start
))
4485 HOST_WIDE_INT last
= start
+ outer_size
;
4488 (bitmap_bit_p (live_relevant_regs
, regno
),
4489 live_subregs
, live_subregs_used
, regno
,
4492 /* Ignore the paradoxical bits. */
4493 if (last
> SBITMAP_SIZE (live_subregs
[regno
]))
4494 last
= SBITMAP_SIZE (live_subregs
[regno
]);
4496 while (start
< last
)
4498 bitmap_set_bit (live_subregs
[regno
], start
);
4503 /* Resetting the live_subregs_used is
4504 effectively saying do not use the subregs
4505 because we are reading the whole
4507 bitmap_clear_bit (live_subregs_used
, regno
);
4508 bitmap_set_bit (live_relevant_regs
, regno
);
4514 /* FIXME!! The following code is a disaster. Reload needs to see the
4515 labels and jump tables that are just hanging out in between
4516 the basic blocks. See pr33676. */
4517 insn
= BB_HEAD (bb
);
4519 /* Skip over the barriers and cruft. */
4520 while (insn
&& (BARRIER_P (insn
) || NOTE_P (insn
)
4521 || BLOCK_FOR_INSN (insn
) == bb
))
4522 insn
= PREV_INSN (insn
);
4524 /* While we add anything except barriers and notes, the focus is
4525 to get the labels and jump tables into the
4526 reload_insn_chain. */
4529 if (!NOTE_P (insn
) && !BARRIER_P (insn
))
4531 if (BLOCK_FOR_INSN (insn
))
4534 c
= new_insn_chain ();
4540 /* The block makes no sense here, but it is what the old
4542 c
->block
= bb
->index
;
4544 bitmap_copy (&c
->live_throughout
, live_relevant_regs
);
4546 insn
= PREV_INSN (insn
);
4550 reload_insn_chain
= c
;
4553 for (i
= 0; i
< (unsigned int) max_regno
; i
++)
4554 if (live_subregs
[i
] != NULL
)
4555 sbitmap_free (live_subregs
[i
]);
4556 free (live_subregs
);
4559 print_insn_chains (dump_file
);
4562 /* Examine the rtx found in *LOC, which is read or written to as determined
4563 by TYPE. Return false if we find a reason why an insn containing this
4564 rtx should not be moved (such as accesses to non-constant memory), true
4567 rtx_moveable_p (rtx
*loc
, enum op_type type
)
4573 enum rtx_code code
= GET_CODE (x
);
4583 return type
== OP_IN
;
4586 if (x
== frame_pointer_rtx
)
4588 if (HARD_REGISTER_P (x
))
4594 if (type
== OP_IN
&& MEM_READONLY_P (x
))
4595 return rtx_moveable_p (&XEXP (x
, 0), OP_IN
);
4599 return (rtx_moveable_p (&SET_SRC (x
), OP_IN
)
4600 && rtx_moveable_p (&SET_DEST (x
), OP_OUT
));
4602 case STRICT_LOW_PART
:
4603 return rtx_moveable_p (&XEXP (x
, 0), OP_OUT
);
4607 return (rtx_moveable_p (&XEXP (x
, 0), type
)
4608 && rtx_moveable_p (&XEXP (x
, 1), OP_IN
)
4609 && rtx_moveable_p (&XEXP (x
, 2), OP_IN
));
4612 return rtx_moveable_p (&SET_DEST (x
), OP_OUT
);
4614 case UNSPEC_VOLATILE
:
4615 /* It is a bad idea to consider insns with such rtl
4616 as moveable ones. The insn scheduler also considers them as barrier
4621 /* The same is true for volatile asm: it has unknown side effects, it
4622 cannot be moved at will. */
4623 if (MEM_VOLATILE_P (x
))
4630 fmt
= GET_RTX_FORMAT (code
);
4631 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4635 if (!rtx_moveable_p (&XEXP (x
, i
), type
))
4638 else if (fmt
[i
] == 'E')
4639 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
4641 if (!rtx_moveable_p (&XVECEXP (x
, i
, j
), type
))
4648 /* A wrapper around dominated_by_p, which uses the information in UID_LUID
4649 to give dominance relationships between two insns I1 and I2. */
4651 insn_dominated_by_p (rtx i1
, rtx i2
, int *uid_luid
)
4653 basic_block bb1
= BLOCK_FOR_INSN (i1
);
4654 basic_block bb2
= BLOCK_FOR_INSN (i2
);
4657 return uid_luid
[INSN_UID (i2
)] < uid_luid
[INSN_UID (i1
)];
4658 return dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
);
4661 /* Record the range of register numbers added by find_moveable_pseudos. */
4662 int first_moveable_pseudo
, last_moveable_pseudo
;
4664 /* These two vectors hold data for every register added by
4665 find_movable_pseudos, with index 0 holding data for the
4666 first_moveable_pseudo. */
4667 /* The original home register. */
4668 static vec
<rtx
> pseudo_replaced_reg
;
4670 /* Look for instances where we have an instruction that is known to increase
4671 register pressure, and whose result is not used immediately. If it is
4672 possible to move the instruction downwards to just before its first use,
4673 split its lifetime into two ranges. We create a new pseudo to compute the
4674 value, and emit a move instruction just before the first use. If, after
4675 register allocation, the new pseudo remains unallocated, the function
4676 move_unallocated_pseudos then deletes the move instruction and places
4677 the computation just before the first use.
4679 Such a move is safe and profitable if all the input registers remain live
4680 and unchanged between the original computation and its first use. In such
4681 a situation, the computation is known to increase register pressure, and
4682 moving it is known to at least not worsen it.
4684 We restrict moves to only those cases where a register remains unallocated,
4685 in order to avoid interfering too much with the instruction schedule. As
4686 an exception, we may move insns which only modify their input register
4687 (typically induction variables), as this increases the freedom for our
4688 intended transformation, and does not limit the second instruction
4692 find_moveable_pseudos (void)
4695 int max_regs
= max_reg_num ();
4696 int max_uid
= get_max_uid ();
4698 int *uid_luid
= XNEWVEC (int, max_uid
);
4699 rtx_insn
**closest_uses
= XNEWVEC (rtx_insn
*, max_regs
);
4700 /* A set of registers which are live but not modified throughout a block. */
4701 bitmap_head
*bb_transp_live
= XNEWVEC (bitmap_head
,
4702 last_basic_block_for_fn (cfun
));
4703 /* A set of registers which only exist in a given basic block. */
4704 bitmap_head
*bb_local
= XNEWVEC (bitmap_head
,
4705 last_basic_block_for_fn (cfun
));
4706 /* A set of registers which are set once, in an instruction that can be
4707 moved freely downwards, but are otherwise transparent to a block. */
4708 bitmap_head
*bb_moveable_reg_sets
= XNEWVEC (bitmap_head
,
4709 last_basic_block_for_fn (cfun
));
4710 auto_bitmap live
, used
, set
, interesting
, unusable_as_input
;
4713 first_moveable_pseudo
= max_regs
;
4714 pseudo_replaced_reg
.release ();
4715 pseudo_replaced_reg
.safe_grow_cleared (max_regs
, true);
4718 calculate_dominance_info (CDI_DOMINATORS
);
4721 FOR_EACH_BB_FN (bb
, cfun
)
4724 bitmap transp
= bb_transp_live
+ bb
->index
;
4725 bitmap moveable
= bb_moveable_reg_sets
+ bb
->index
;
4726 bitmap local
= bb_local
+ bb
->index
;
4728 bitmap_initialize (local
, 0);
4729 bitmap_initialize (transp
, 0);
4730 bitmap_initialize (moveable
, 0);
4731 bitmap_copy (live
, df_get_live_out (bb
));
4732 bitmap_and_into (live
, df_get_live_in (bb
));
4733 bitmap_copy (transp
, live
);
4734 bitmap_clear (moveable
);
4735 bitmap_clear (live
);
4736 bitmap_clear (used
);
4738 FOR_BB_INSNS (bb
, insn
)
4739 if (NONDEBUG_INSN_P (insn
))
4741 df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
4744 uid_luid
[INSN_UID (insn
)] = i
++;
4746 def
= df_single_def (insn_info
);
4747 use
= df_single_use (insn_info
);
4750 && DF_REF_REGNO (use
) == DF_REF_REGNO (def
)
4751 && !bitmap_bit_p (set
, DF_REF_REGNO (use
))
4752 && rtx_moveable_p (&PATTERN (insn
), OP_IN
))
4754 unsigned regno
= DF_REF_REGNO (use
);
4755 bitmap_set_bit (moveable
, regno
);
4756 bitmap_set_bit (set
, regno
);
4757 bitmap_set_bit (used
, regno
);
4758 bitmap_clear_bit (transp
, regno
);
4761 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
4763 unsigned regno
= DF_REF_REGNO (use
);
4764 bitmap_set_bit (used
, regno
);
4765 if (bitmap_clear_bit (moveable
, regno
))
4766 bitmap_clear_bit (transp
, regno
);
4769 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
4771 unsigned regno
= DF_REF_REGNO (def
);
4772 bitmap_set_bit (set
, regno
);
4773 bitmap_clear_bit (transp
, regno
);
4774 bitmap_clear_bit (moveable
, regno
);
4779 FOR_EACH_BB_FN (bb
, cfun
)
4781 bitmap local
= bb_local
+ bb
->index
;
4784 FOR_BB_INSNS (bb
, insn
)
4785 if (NONDEBUG_INSN_P (insn
))
4787 df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
4789 rtx closest_use
, note
;
4792 bool all_dominated
, all_local
;
4795 def
= df_single_def (insn_info
);
4796 /* There must be exactly one def in this insn. */
4797 if (!def
|| !single_set (insn
))
4799 /* This must be the only definition of the reg. We also limit
4800 which modes we deal with so that we can assume we can generate
4801 move instructions. */
4802 regno
= DF_REF_REGNO (def
);
4803 mode
= GET_MODE (DF_REF_REG (def
));
4804 if (DF_REG_DEF_COUNT (regno
) != 1
4805 || !DF_REF_INSN_INFO (def
)
4806 || HARD_REGISTER_NUM_P (regno
)
4807 || DF_REG_EQ_USE_COUNT (regno
) > 0
4808 || (!INTEGRAL_MODE_P (mode
)
4809 && !FLOAT_MODE_P (mode
)
4810 && !OPAQUE_MODE_P (mode
)))
4812 def_insn
= DF_REF_INSN (def
);
4814 for (note
= REG_NOTES (def_insn
); note
; note
= XEXP (note
, 1))
4815 if (REG_NOTE_KIND (note
) == REG_EQUIV
&& MEM_P (XEXP (note
, 0)))
4821 fprintf (dump_file
, "Ignoring reg %d, has equiv memory\n",
4823 bitmap_set_bit (unusable_as_input
, regno
);
4827 use
= DF_REG_USE_CHAIN (regno
);
4828 all_dominated
= true;
4830 closest_use
= NULL_RTX
;
4831 for (; use
; use
= DF_REF_NEXT_REG (use
))
4834 if (!DF_REF_INSN_INFO (use
))
4836 all_dominated
= false;
4840 insn
= DF_REF_INSN (use
);
4841 if (DEBUG_INSN_P (insn
))
4843 if (BLOCK_FOR_INSN (insn
) != BLOCK_FOR_INSN (def_insn
))
4845 if (!insn_dominated_by_p (insn
, def_insn
, uid_luid
))
4846 all_dominated
= false;
4847 if (closest_use
!= insn
&& closest_use
!= const0_rtx
)
4849 if (closest_use
== NULL_RTX
)
4851 else if (insn_dominated_by_p (closest_use
, insn
, uid_luid
))
4853 else if (!insn_dominated_by_p (insn
, closest_use
, uid_luid
))
4854 closest_use
= const0_rtx
;
4860 fprintf (dump_file
, "Reg %d not all uses dominated by set\n",
4865 bitmap_set_bit (local
, regno
);
4866 if (closest_use
== const0_rtx
|| closest_use
== NULL
4867 || next_nonnote_nondebug_insn (def_insn
) == closest_use
)
4870 fprintf (dump_file
, "Reg %d uninteresting%s\n", regno
,
4871 closest_use
== const0_rtx
|| closest_use
== NULL
4872 ? " (no unique first use)" : "");
4876 bitmap_set_bit (interesting
, regno
);
4877 /* If we get here, we know closest_use is a non-NULL insn
4878 (as opposed to const_0_rtx). */
4879 closest_uses
[regno
] = as_a
<rtx_insn
*> (closest_use
);
4881 if (dump_file
&& (all_local
|| all_dominated
))
4883 fprintf (dump_file
, "Reg %u:", regno
);
4885 fprintf (dump_file
, " local to bb %d", bb
->index
);
4887 fprintf (dump_file
, " def dominates all uses");
4888 if (closest_use
!= const0_rtx
)
4889 fprintf (dump_file
, " has unique first use");
4890 fputs ("\n", dump_file
);
4895 EXECUTE_IF_SET_IN_BITMAP (interesting
, 0, i
, bi
)
4897 df_ref def
= DF_REG_DEF_CHAIN (i
);
4898 rtx_insn
*def_insn
= DF_REF_INSN (def
);
4899 basic_block def_block
= BLOCK_FOR_INSN (def_insn
);
4900 bitmap def_bb_local
= bb_local
+ def_block
->index
;
4901 bitmap def_bb_moveable
= bb_moveable_reg_sets
+ def_block
->index
;
4902 bitmap def_bb_transp
= bb_transp_live
+ def_block
->index
;
4903 bool local_to_bb_p
= bitmap_bit_p (def_bb_local
, i
);
4904 rtx_insn
*use_insn
= closest_uses
[i
];
4907 bool all_transp
= true;
4909 if (!REG_P (DF_REF_REG (def
)))
4915 fprintf (dump_file
, "Reg %u not local to one basic block\n",
4919 if (reg_equiv_init (i
) != NULL_RTX
)
4922 fprintf (dump_file
, "Ignoring reg %u with equiv init insn\n",
4926 if (!rtx_moveable_p (&PATTERN (def_insn
), OP_IN
))
4929 fprintf (dump_file
, "Found def insn %d for %d to be not moveable\n",
4930 INSN_UID (def_insn
), i
);
4934 fprintf (dump_file
, "Examining insn %d, def for %d\n",
4935 INSN_UID (def_insn
), i
);
4936 FOR_EACH_INSN_USE (use
, def_insn
)
4938 unsigned regno
= DF_REF_REGNO (use
);
4939 if (bitmap_bit_p (unusable_as_input
, regno
))
4943 fprintf (dump_file
, " found unusable input reg %u.\n", regno
);
4946 if (!bitmap_bit_p (def_bb_transp
, regno
))
4948 if (bitmap_bit_p (def_bb_moveable
, regno
)
4949 && !control_flow_insn_p (use_insn
))
4951 if (modified_between_p (DF_REF_REG (use
), def_insn
, use_insn
))
4953 rtx_insn
*x
= NEXT_INSN (def_insn
);
4954 while (!modified_in_p (DF_REF_REG (use
), x
))
4956 gcc_assert (x
!= use_insn
);
4960 fprintf (dump_file
, " input reg %u modified but insn %d moveable\n",
4961 regno
, INSN_UID (x
));
4962 emit_insn_after (PATTERN (x
), use_insn
);
4963 set_insn_deleted (x
);
4968 fprintf (dump_file
, " input reg %u modified between def and use\n",
4979 if (!dbg_cnt (ira_move
))
4982 fprintf (dump_file
, " all ok%s\n", all_transp
? " and transp" : "");
4986 rtx def_reg
= DF_REF_REG (def
);
4987 rtx newreg
= ira_create_new_reg (def_reg
);
4988 if (validate_change (def_insn
, DF_REF_REAL_LOC (def
), newreg
, 0))
4990 unsigned nregno
= REGNO (newreg
);
4991 emit_insn_before (gen_move_insn (def_reg
, newreg
), use_insn
);
4993 pseudo_replaced_reg
[nregno
] = def_reg
;
4998 FOR_EACH_BB_FN (bb
, cfun
)
5000 bitmap_clear (bb_local
+ bb
->index
);
5001 bitmap_clear (bb_transp_live
+ bb
->index
);
5002 bitmap_clear (bb_moveable_reg_sets
+ bb
->index
);
5005 free (closest_uses
);
5007 free (bb_transp_live
);
5008 free (bb_moveable_reg_sets
);
5010 last_moveable_pseudo
= max_reg_num ();
5012 fix_reg_equiv_init ();
5014 regstat_free_n_sets_and_refs ();
5016 regstat_init_n_sets_and_refs ();
5017 regstat_compute_ri ();
5018 free_dominance_info (CDI_DOMINATORS
);
5021 /* If SET pattern SET is an assignment from a hard register to a pseudo which
5022 is live at CALL_DOM (if non-NULL, otherwise this check is omitted), return
5023 the destination. Otherwise return NULL. */
5026 interesting_dest_for_shprep_1 (rtx set
, basic_block call_dom
)
5028 rtx src
= SET_SRC (set
);
5029 rtx dest
= SET_DEST (set
);
5030 if (!REG_P (src
) || !HARD_REGISTER_P (src
)
5031 || !REG_P (dest
) || HARD_REGISTER_P (dest
)
5032 || (call_dom
&& !bitmap_bit_p (df_get_live_in (call_dom
), REGNO (dest
))))
5037 /* If insn is interesting for parameter range-splitting shrink-wrapping
5038 preparation, i.e. it is a single set from a hard register to a pseudo, which
5039 is live at CALL_DOM (if non-NULL, otherwise this check is omitted), or a
5040 parallel statement with only one such statement, return the destination.
5041 Otherwise return NULL. */
5044 interesting_dest_for_shprep (rtx_insn
*insn
, basic_block call_dom
)
5048 rtx pat
= PATTERN (insn
);
5049 if (GET_CODE (pat
) == SET
)
5050 return interesting_dest_for_shprep_1 (pat
, call_dom
);
5052 if (GET_CODE (pat
) != PARALLEL
)
5055 for (int i
= 0; i
< XVECLEN (pat
, 0); i
++)
5057 rtx sub
= XVECEXP (pat
, 0, i
);
5058 if (GET_CODE (sub
) == USE
|| GET_CODE (sub
) == CLOBBER
)
5060 if (GET_CODE (sub
) != SET
5061 || side_effects_p (sub
))
5063 rtx dest
= interesting_dest_for_shprep_1 (sub
, call_dom
);
5072 /* Split live ranges of pseudos that are loaded from hard registers in the
5073 first BB in a BB that dominates all non-sibling call if such a BB can be
5074 found and is not in a loop. Return true if the function has made any
5078 split_live_ranges_for_shrink_wrap (void)
5080 basic_block bb
, call_dom
= NULL
;
5081 basic_block first
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
5082 rtx_insn
*insn
, *last_interesting_insn
= NULL
;
5083 auto_bitmap need_new
, reachable
;
5084 vec
<basic_block
> queue
;
5086 if (!SHRINK_WRAPPING_ENABLED
)
5089 queue
.create (n_basic_blocks_for_fn (cfun
));
5091 FOR_EACH_BB_FN (bb
, cfun
)
5092 FOR_BB_INSNS (bb
, insn
)
5093 if (CALL_P (insn
) && !SIBLING_CALL_P (insn
))
5101 bitmap_set_bit (need_new
, bb
->index
);
5102 bitmap_set_bit (reachable
, bb
->index
);
5103 queue
.quick_push (bb
);
5107 if (queue
.is_empty ())
5113 while (!queue
.is_empty ())
5119 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
5120 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
5121 && bitmap_set_bit (reachable
, e
->dest
->index
))
5122 queue
.quick_push (e
->dest
);
5126 FOR_BB_INSNS (first
, insn
)
5128 rtx dest
= interesting_dest_for_shprep (insn
, NULL
);
5132 if (DF_REG_DEF_COUNT (REGNO (dest
)) > 1)
5135 for (df_ref use
= DF_REG_USE_CHAIN (REGNO(dest
));
5137 use
= DF_REF_NEXT_REG (use
))
5139 int ubbi
= DF_REF_BB (use
)->index
;
5140 if (bitmap_bit_p (reachable
, ubbi
))
5141 bitmap_set_bit (need_new
, ubbi
);
5143 last_interesting_insn
= insn
;
5146 if (!last_interesting_insn
)
5149 call_dom
= nearest_common_dominator_for_set (CDI_DOMINATORS
, need_new
);
5150 if (call_dom
== first
)
5153 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
5154 while (bb_loop_depth (call_dom
) > 0)
5155 call_dom
= get_immediate_dominator (CDI_DOMINATORS
, call_dom
);
5156 loop_optimizer_finalize ();
5158 if (call_dom
== first
)
5161 calculate_dominance_info (CDI_POST_DOMINATORS
);
5162 if (dominated_by_p (CDI_POST_DOMINATORS
, first
, call_dom
))
5164 free_dominance_info (CDI_POST_DOMINATORS
);
5167 free_dominance_info (CDI_POST_DOMINATORS
);
5170 fprintf (dump_file
, "Will split live ranges of parameters at BB %i\n",
5174 FOR_BB_INSNS (first
, insn
)
5176 rtx dest
= interesting_dest_for_shprep (insn
, call_dom
);
5177 if (!dest
|| dest
== pic_offset_table_rtx
)
5180 bool need_newreg
= false;
5182 for (use
= DF_REG_USE_CHAIN (REGNO (dest
)); use
; use
= next
)
5184 rtx_insn
*uin
= DF_REF_INSN (use
);
5185 next
= DF_REF_NEXT_REG (use
);
5187 if (DEBUG_INSN_P (uin
))
5190 basic_block ubb
= BLOCK_FOR_INSN (uin
);
5192 || dominated_by_p (CDI_DOMINATORS
, ubb
, call_dom
))
5201 rtx newreg
= ira_create_new_reg (dest
);
5203 for (use
= DF_REG_USE_CHAIN (REGNO (dest
)); use
; use
= next
)
5205 rtx_insn
*uin
= DF_REF_INSN (use
);
5206 next
= DF_REF_NEXT_REG (use
);
5208 basic_block ubb
= BLOCK_FOR_INSN (uin
);
5210 || dominated_by_p (CDI_DOMINATORS
, ubb
, call_dom
))
5211 validate_change (uin
, DF_REF_REAL_LOC (use
), newreg
, true);
5214 rtx_insn
*new_move
= gen_move_insn (newreg
, dest
);
5215 emit_insn_after (new_move
, bb_note (call_dom
));
5218 fprintf (dump_file
, "Split live-range of register ");
5219 print_rtl_single (dump_file
, dest
);
5224 if (insn
== last_interesting_insn
)
5227 apply_change_group ();
5231 /* Perform the second half of the transformation started in
5232 find_moveable_pseudos. We look for instances where the newly introduced
5233 pseudo remains unallocated, and remove it by moving the definition to
5234 just before its use, replacing the move instruction generated by
5235 find_moveable_pseudos. */
5237 move_unallocated_pseudos (void)
5240 for (i
= first_moveable_pseudo
; i
< last_moveable_pseudo
; i
++)
5241 if (reg_renumber
[i
] < 0)
5243 int idx
= i
- first_moveable_pseudo
;
5244 rtx other_reg
= pseudo_replaced_reg
[idx
];
5245 /* The iterating range [first_moveable_pseudo, last_moveable_pseudo)
5246 covers every new pseudo created in find_moveable_pseudos,
5247 regardless of the validation with it is successful or not.
5248 So we need to skip the pseudos which were used in those failed
5249 validations to avoid unexpected DF info and consequent ICE.
5250 We only set pseudo_replaced_reg[] when the validation is successful
5251 in find_moveable_pseudos, it's enough to check it here. */
5254 rtx_insn
*def_insn
= DF_REF_INSN (DF_REG_DEF_CHAIN (i
));
5255 /* The use must follow all definitions of OTHER_REG, so we can
5256 insert the new definition immediately after any of them. */
5257 df_ref other_def
= DF_REG_DEF_CHAIN (REGNO (other_reg
));
5258 rtx_insn
*move_insn
= DF_REF_INSN (other_def
);
5259 rtx_insn
*newinsn
= emit_insn_after (PATTERN (def_insn
), move_insn
);
5264 fprintf (dump_file
, "moving def of %d (insn %d now) ",
5265 REGNO (other_reg
), INSN_UID (def_insn
));
5267 delete_insn (move_insn
);
5268 while ((other_def
= DF_REG_DEF_CHAIN (REGNO (other_reg
))))
5269 delete_insn (DF_REF_INSN (other_def
));
5270 delete_insn (def_insn
);
5272 set
= single_set (newinsn
);
5273 success
= validate_change (newinsn
, &SET_DEST (set
), other_reg
, 0);
5274 gcc_assert (success
);
5276 fprintf (dump_file
, " %d) rather than keep unallocated replacement %d\n",
5277 INSN_UID (newinsn
), i
);
5278 SET_REG_N_REFS (i
, 0);
5281 first_moveable_pseudo
= last_moveable_pseudo
= 0;
5286 /* Code dealing with scratches (changing them onto
5287 pseudos and restoring them from the pseudos).
5289 We change scratches into pseudos at the beginning of IRA to
5290 simplify dealing with them (conflicts, hard register assignments).
5292 If the pseudo denoting scratch was spilled it means that we do not
5293 need a hard register for it. Such pseudos are transformed back to
5294 scratches at the end of LRA. */
5296 /* Description of location of a former scratch operand. */
5299 rtx_insn
*insn
; /* Insn where the scratch was. */
5300 int nop
; /* Number of the operand which was a scratch. */
5301 unsigned regno
; /* regno gnerated instead of scratch */
5302 int icode
; /* Original icode from which scratch was removed. */
5305 typedef struct sloc
*sloc_t
;
5307 /* Locations of the former scratches. */
5308 static vec
<sloc_t
> scratches
;
5310 /* Bitmap of scratch regnos. */
5311 static bitmap_head scratch_bitmap
;
5313 /* Bitmap of scratch operands. */
5314 static bitmap_head scratch_operand_bitmap
;
5316 /* Return true if pseudo REGNO is made of SCRATCH. */
5318 ira_former_scratch_p (int regno
)
5320 return bitmap_bit_p (&scratch_bitmap
, regno
);
5323 /* Return true if the operand NOP of INSN is a former scratch. */
5325 ira_former_scratch_operand_p (rtx_insn
*insn
, int nop
)
5327 return bitmap_bit_p (&scratch_operand_bitmap
,
5328 INSN_UID (insn
) * MAX_RECOG_OPERANDS
+ nop
) != 0;
5331 /* Register operand NOP in INSN as a former scratch. It will be
5332 changed to scratch back, if it is necessary, at the LRA end. */
5334 ira_register_new_scratch_op (rtx_insn
*insn
, int nop
, int icode
)
5336 rtx op
= *recog_data
.operand_loc
[nop
];
5337 sloc_t loc
= XNEW (struct sloc
);
5338 ira_assert (REG_P (op
));
5341 loc
->regno
= REGNO (op
);
5343 scratches
.safe_push (loc
);
5344 bitmap_set_bit (&scratch_bitmap
, REGNO (op
));
5345 bitmap_set_bit (&scratch_operand_bitmap
,
5346 INSN_UID (insn
) * MAX_RECOG_OPERANDS
+ nop
);
5347 add_reg_note (insn
, REG_UNUSED
, op
);
5350 /* Return true if string STR contains constraint 'X'. */
5352 contains_X_constraint_p (const char *str
)
5358 str
+= CONSTRAINT_LEN (c
, str
);
5359 if (c
== 'X') return true;
5364 /* Change INSN's scratches into pseudos and save their location.
5365 Return true if we changed any scratch. */
5367 ira_remove_insn_scratches (rtx_insn
*insn
, bool all_p
, FILE *dump_file
,
5368 rtx (*get_reg
) (rtx original
))
5371 bool insn_changed_p
;
5374 extract_insn (insn
);
5375 insn_changed_p
= false;
5376 for (i
= 0; i
< recog_data
.n_operands
; i
++)
5378 loc
= recog_data
.operand_loc
[i
];
5379 if (GET_CODE (*loc
) == SCRATCH
&& GET_MODE (*loc
) != VOIDmode
)
5381 if (! all_p
&& contains_X_constraint_p (recog_data
.constraints
[i
]))
5383 insn_changed_p
= true;
5384 *loc
= reg
= get_reg (*loc
);
5385 ira_register_new_scratch_op (insn
, i
, INSN_CODE (insn
));
5386 if (ira_dump_file
!= NULL
)
5388 "Removing SCRATCH to p%u in insn #%u (nop %d)\n",
5389 REGNO (reg
), INSN_UID (insn
), i
);
5392 return insn_changed_p
;
5395 /* Return new register of the same mode as ORIGINAL. Used in
5396 remove_scratches. */
5398 get_scratch_reg (rtx original
)
5400 return gen_reg_rtx (GET_MODE (original
));
5403 /* Change scratches into pseudos and save their location. Return true
5404 if we changed any scratch. */
5406 remove_scratches (void)
5408 bool change_p
= false;
5412 scratches
.create (get_max_uid ());
5413 bitmap_initialize (&scratch_bitmap
, ®_obstack
);
5414 bitmap_initialize (&scratch_operand_bitmap
, ®_obstack
);
5415 FOR_EACH_BB_FN (bb
, cfun
)
5416 FOR_BB_INSNS (bb
, insn
)
5418 && ira_remove_insn_scratches (insn
, false, ira_dump_file
, get_scratch_reg
))
5420 /* Because we might use DF, we need to keep DF info up to date. */
5421 df_insn_rescan (insn
);
5427 /* Changes pseudos created by function remove_scratches onto scratches. */
5429 ira_restore_scratches (FILE *dump_file
)
5436 for (i
= 0; scratches
.iterate (i
, &loc
); i
++)
5438 /* Ignore already deleted insns. */
5439 if (NOTE_P (loc
->insn
)
5440 && NOTE_KIND (loc
->insn
) == NOTE_INSN_DELETED
)
5442 extract_insn (loc
->insn
);
5443 if (loc
->icode
!= INSN_CODE (loc
->insn
))
5445 /* The icode doesn't match, which means the insn has been modified
5446 (e.g. register elimination). The scratch cannot be restored. */
5449 op_loc
= recog_data
.operand_loc
[loc
->nop
];
5451 && ((regno
= REGNO (*op_loc
)) >= FIRST_PSEUDO_REGISTER
)
5452 && reg_renumber
[regno
] < 0)
5454 /* It should be only case when scratch register with chosen
5455 constraint 'X' did not get memory or hard register. */
5456 ira_assert (ira_former_scratch_p (regno
));
5457 *op_loc
= gen_rtx_SCRATCH (GET_MODE (*op_loc
));
5458 for (n
= 0; n
< recog_data
.n_dups
; n
++)
5459 *recog_data
.dup_loc
[n
]
5460 = *recog_data
.operand_loc
[(int) recog_data
.dup_num
[n
]];
5461 if (dump_file
!= NULL
)
5462 fprintf (dump_file
, "Restoring SCRATCH in insn #%u(nop %d)\n",
5463 INSN_UID (loc
->insn
), loc
->nop
);
5466 for (i
= 0; scratches
.iterate (i
, &loc
); i
++)
5468 scratches
.release ();
5469 bitmap_clear (&scratch_bitmap
);
5470 bitmap_clear (&scratch_operand_bitmap
);
5475 /* If the backend knows where to allocate pseudos for hard
5476 register initial values, register these allocations now. */
5478 allocate_initial_values (void)
5480 if (targetm
.allocate_initial_value
)
5485 for (i
= 0; HARD_REGISTER_NUM_P (i
); i
++)
5487 if (! initial_value_entry (i
, &hreg
, &preg
))
5490 x
= targetm
.allocate_initial_value (hreg
);
5491 regno
= REGNO (preg
);
5492 if (x
&& REG_N_SETS (regno
) <= 1)
5495 reg_equiv_memory_loc (regno
) = x
;
5501 gcc_assert (REG_P (x
));
5502 new_regno
= REGNO (x
);
5503 reg_renumber
[regno
] = new_regno
;
5504 /* Poke the regno right into regno_reg_rtx so that even
5505 fixed regs are accepted. */
5506 SET_REGNO (preg
, new_regno
);
5507 /* Update global register liveness information. */
5508 FOR_EACH_BB_FN (bb
, cfun
)
5510 if (REGNO_REG_SET_P (df_get_live_in (bb
), regno
))
5511 SET_REGNO_REG_SET (df_get_live_in (bb
), new_regno
);
5512 if (REGNO_REG_SET_P (df_get_live_out (bb
), regno
))
5513 SET_REGNO_REG_SET (df_get_live_out (bb
), new_regno
);
5519 gcc_checking_assert (! initial_value_entry (FIRST_PSEUDO_REGISTER
,
5527 /* True when we use LRA instead of reload pass for the current
5531 /* True if we have allocno conflicts. It is false for non-optimized
5532 mode or when the conflict table is too big. */
5533 bool ira_conflicts_p
;
5535 /* Saved between IRA and reload. */
5536 static int saved_flag_ira_share_spill_slots
;
5538 /* This is the main entry of IRA. */
5543 int ira_max_point_before_emit
;
5544 bool saved_flag_caller_saves
= flag_caller_saves
;
5545 enum ira_region saved_flag_ira_region
= flag_ira_region
;
5549 bool output_jump_reload_p
= false;
5553 /* First put potential jump output reloads on the output edges
5554 as USE which will be removed at the end of LRA. The major
5555 goal is actually to create BBs for critical edges for LRA and
5556 populate them later by live info. In LRA it will be
5557 difficult to do this. */
5558 FOR_EACH_BB_FN (bb
, cfun
)
5560 rtx_insn
*end
= BB_END (bb
);
5564 for (int i
= 0; i
< recog_data
.n_operands
; i
++)
5565 if (recog_data
.operand_type
[i
] != OP_IN
)
5567 bool skip_p
= false;
5568 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
5569 if (EDGE_CRITICAL_P (e
)
5570 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
5571 && (e
->flags
& EDGE_ABNORMAL
))
5578 output_jump_reload_p
= true;
5579 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
5580 if (EDGE_CRITICAL_P (e
)
5581 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
5584 /* We need to put some no-op insn here. We can
5585 not put a note as commit_edges insertion will
5587 emit_insn (gen_rtx_USE (VOIDmode
, const1_rtx
));
5588 rtx_insn
*insns
= get_insns ();
5590 insert_insn_on_edge (insns
, e
);
5595 if (output_jump_reload_p
)
5596 commit_edge_insertions ();
5599 if (flag_ira_verbose
< 10)
5601 internal_flag_ira_verbose
= flag_ira_verbose
;
5606 internal_flag_ira_verbose
= flag_ira_verbose
- 10;
5607 ira_dump_file
= stderr
;
5612 /* Determine if the current function is a leaf before running IRA
5613 since this can impact optimizations done by the prologue and
5614 epilogue thus changing register elimination offsets.
5615 Other target callbacks may use crtl->is_leaf too, including
5616 SHRINK_WRAPPING_ENABLED, so initialize as early as possible. */
5617 crtl
->is_leaf
= leaf_function_p ();
5619 /* Perform target specific PIC register initialization. */
5620 targetm
.init_pic_reg ();
5622 ira_conflicts_p
= optimize
> 0;
5624 /* Determine the number of pseudos actually requiring coloring. */
5625 unsigned int num_used_regs
= 0;
5626 for (unsigned int i
= FIRST_PSEUDO_REGISTER
; i
< DF_REG_SIZE (df
); i
++)
5627 if (DF_REG_DEF_COUNT (i
) || DF_REG_USE_COUNT (i
))
5630 /* If there are too many pseudos and/or basic blocks (e.g. 10K pseudos and
5631 10K blocks or 100K pseudos and 1K blocks) or we have too many function
5632 insns, we will use simplified and faster algorithms in LRA. */
5635 && (num_used_regs
>= (1U << 26) / last_basic_block_for_fn (cfun
)
5636 /* max uid is a good evaluation of the number of insns as most
5637 optimizations are done on tree-SSA level. */
5638 || ((uint64_t) get_max_uid ()
5639 > (uint64_t) param_ira_simple_lra_insn_threshold
* 1000)));
5643 /* It permits to skip live range splitting in LRA. */
5644 flag_caller_saves
= false;
5645 /* There is no sense to do regional allocation when we use
5647 flag_ira_region
= IRA_REGION_ONE
;
5648 ira_conflicts_p
= false;
5651 #ifndef IRA_NO_OBSTACK
5652 gcc_obstack_init (&ira_obstack
);
5654 bitmap_obstack_initialize (&ira_bitmap_obstack
);
5656 /* LRA uses its own infrastructure to handle caller save registers. */
5657 if (flag_caller_saves
&& !ira_use_lra_p
)
5658 init_caller_save ();
5660 setup_prohibited_mode_move_regs ();
5661 decrease_live_ranges_number ();
5662 df_note_add_problem ();
5664 /* DF_LIVE can't be used in the register allocator, too many other
5665 parts of the compiler depend on using the "classic" liveness
5666 interpretation of the DF_LR problem. See PR38711.
5667 Remove the problem, so that we don't spend time updating it in
5668 any of the df_analyze() calls during IRA/LRA. */
5670 df_remove_problem (df_live
);
5671 gcc_checking_assert (df_live
== NULL
);
5674 df
->changeable_flags
|= DF_VERIFY_SCHEDULED
;
5679 if (ira_conflicts_p
)
5681 calculate_dominance_info (CDI_DOMINATORS
);
5683 if (split_live_ranges_for_shrink_wrap ())
5686 free_dominance_info (CDI_DOMINATORS
);
5689 df_clear_flags (DF_NO_INSN_RESCAN
);
5691 indirect_jump_optimize ();
5692 if (delete_trivially_dead_insns (get_insns (), max_reg_num ()))
5695 regstat_init_n_sets_and_refs ();
5696 regstat_compute_ri ();
5698 /* If we are not optimizing, then this is the only place before
5699 register allocation where dataflow is done. And that is needed
5700 to generate these warnings. */
5702 generate_setjmp_warnings ();
5704 /* update_equiv_regs can use reg classes of pseudos and they are set up in
5705 register pressure sensitive scheduling and loop invariant motion and in
5706 live range shrinking. This info can become obsolete if we add new pseudos
5707 since the last set up. Recalculate it again if the new pseudos were
5709 if (resize_reg_info () && (flag_sched_pressure
|| flag_live_range_shrinkage
5710 || flag_ira_loop_pressure
))
5711 ira_set_pseudo_classes (true, ira_dump_file
);
5713 init_alias_analysis ();
5714 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
5715 reg_equiv
= XCNEWVEC (struct equivalence
, max_reg_num ());
5716 update_equiv_regs_prescan ();
5717 update_equiv_regs ();
5719 /* Don't move insns if live range shrinkage or register
5720 pressure-sensitive scheduling were done because it will not
5721 improve allocation but likely worsen insn scheduling. */
5723 && !flag_live_range_shrinkage
5724 && !(flag_sched_pressure
&& flag_schedule_insns
))
5725 combine_and_move_insns ();
5727 /* Gather additional equivalences with memory. */
5729 add_store_equivs ();
5731 loop_optimizer_finalize ();
5732 free_dominance_info (CDI_DOMINATORS
);
5733 end_alias_analysis ();
5736 /* Once max_regno changes, we need to free and re-init/re-compute
5737 some data structures like regstat_n_sets_and_refs and reg_info_p. */
5738 auto regstat_recompute_for_max_regno
= []() {
5739 regstat_free_n_sets_and_refs ();
5741 regstat_init_n_sets_and_refs ();
5742 regstat_compute_ri ();
5746 int max_regno_before_rm
= max_reg_num ();
5747 if (ira_use_lra_p
&& remove_scratches ())
5749 ira_expand_reg_equiv ();
5750 /* For now remove_scatches is supposed to create pseudos when it
5751 succeeds, assert this happens all the time. Once it doesn't
5752 hold, we should guard the regstat recompute for the case
5753 max_regno changes. */
5754 gcc_assert (max_regno_before_rm
!= max_reg_num ());
5755 regstat_recompute_for_max_regno ();
5760 setup_reg_equiv_init ();
5762 allocated_reg_info_size
= max_reg_num ();
5764 /* It is not worth to do such improvement when we use a simple
5765 allocation because of -O0 usage or because the function is too
5767 if (ira_conflicts_p
)
5768 find_moveable_pseudos ();
5770 max_regno_before_ira
= max_reg_num ();
5771 ira_setup_eliminable_regset ();
5773 ira_overall_cost
= ira_reg_cost
= ira_mem_cost
= 0;
5774 ira_load_cost
= ira_store_cost
= ira_shuffle_cost
= 0;
5775 ira_move_loops_num
= ira_additional_jumps_num
= 0;
5777 ira_assert (current_loops
== NULL
);
5778 if (flag_ira_region
== IRA_REGION_ALL
|| flag_ira_region
== IRA_REGION_MIXED
)
5779 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
| LOOPS_HAVE_RECORDED_EXITS
);
5781 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
5782 fprintf (ira_dump_file
, "Building IRA IR\n");
5783 loops_p
= ira_build ();
5785 ira_assert (ira_conflicts_p
|| !loops_p
);
5787 saved_flag_ira_share_spill_slots
= flag_ira_share_spill_slots
;
5788 if (too_high_register_pressure_p () || cfun
->calls_setjmp
)
5789 /* It is just wasting compiler's time to pack spilled pseudos into
5790 stack slots in this case -- prohibit it. We also do this if
5791 there is setjmp call because a variable not modified between
5792 setjmp and longjmp the compiler is required to preserve its
5793 value and sharing slots does not guarantee it. */
5794 flag_ira_share_spill_slots
= FALSE
;
5798 ira_max_point_before_emit
= ira_max_point
;
5800 ira_initiate_emit_data ();
5804 max_regno
= max_reg_num ();
5805 if (ira_conflicts_p
)
5809 if (! ira_use_lra_p
)
5810 ira_initiate_assign ();
5819 ira_allocno_iterator ai
;
5821 FOR_EACH_ALLOCNO (a
, ai
)
5823 int old_regno
= ALLOCNO_REGNO (a
);
5824 int new_regno
= REGNO (ALLOCNO_EMIT_DATA (a
)->reg
);
5826 ALLOCNO_REGNO (a
) = new_regno
;
5828 if (old_regno
!= new_regno
)
5829 setup_reg_classes (new_regno
, reg_preferred_class (old_regno
),
5830 reg_alternate_class (old_regno
),
5831 reg_allocno_class (old_regno
));
5836 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
5837 fprintf (ira_dump_file
, "Flattening IR\n");
5838 ira_flattening (max_regno_before_ira
, ira_max_point_before_emit
);
5840 /* New insns were generated: add notes and recalculate live
5844 /* ??? Rebuild the loop tree, but why? Does the loop tree
5845 change if new insns were generated? Can that be handled
5846 by updating the loop tree incrementally? */
5847 loop_optimizer_finalize ();
5848 free_dominance_info (CDI_DOMINATORS
);
5849 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
5850 | LOOPS_HAVE_RECORDED_EXITS
);
5852 if (! ira_use_lra_p
)
5854 setup_allocno_assignment_flags ();
5855 ira_initiate_assign ();
5856 ira_reassign_conflict_allocnos (max_regno
);
5861 ira_finish_emit_data ();
5863 setup_reg_renumber ();
5865 calculate_allocation_cost ();
5867 #ifdef ENABLE_IRA_CHECKING
5868 if (ira_conflicts_p
&& ! ira_use_lra_p
)
5869 /* Opposite to reload pass, LRA does not use any conflict info
5870 from IRA. We don't rebuild conflict info for LRA (through
5871 ira_flattening call) and cannot use the check here. We could
5872 rebuild this info for LRA in the check mode but there is a risk
5873 that code generated with the check and without it will be a bit
5874 different. Calling ira_flattening in any mode would be a
5875 wasting CPU time. So do not check the allocation for LRA. */
5876 check_allocation ();
5879 if (max_regno
!= max_regno_before_ira
)
5880 regstat_recompute_for_max_regno ();
5882 overall_cost_before
= ira_overall_cost
;
5883 if (! ira_conflicts_p
)
5887 fix_reg_equiv_init ();
5889 #ifdef ENABLE_IRA_CHECKING
5890 print_redundant_copies ();
5892 if (! ira_use_lra_p
)
5894 ira_spilled_reg_stack_slots_num
= 0;
5895 ira_spilled_reg_stack_slots
5896 = ((class ira_spilled_reg_stack_slot
*)
5897 ira_allocate (max_regno
5898 * sizeof (class ira_spilled_reg_stack_slot
)));
5899 memset ((void *)ira_spilled_reg_stack_slots
, 0,
5900 max_regno
* sizeof (class ira_spilled_reg_stack_slot
));
5903 allocate_initial_values ();
5905 /* See comment for find_moveable_pseudos call. */
5906 if (ira_conflicts_p
)
5907 move_unallocated_pseudos ();
5909 /* Restore original values. */
5912 flag_caller_saves
= saved_flag_caller_saves
;
5913 flag_ira_region
= saved_flag_ira_region
;
5917 /* Modify asm goto to avoid further trouble with this insn. We can
5918 not replace the insn by USE as in other asm insns as we still
5919 need to keep CFG consistency. */
5921 ira_nullify_asm_goto (rtx_insn
*insn
)
5923 ira_assert (JUMP_P (insn
) && INSN_CODE (insn
) < 0);
5924 rtx tmp
= extract_asm_operands (PATTERN (insn
));
5925 PATTERN (insn
) = gen_rtx_ASM_OPERANDS (VOIDmode
, ggc_strdup (""), "", 0,
5928 ASM_OPERANDS_LABEL_VEC (tmp
),
5929 ASM_OPERANDS_SOURCE_LOCATION(tmp
));
5937 unsigned pic_offset_table_regno
= INVALID_REGNUM
;
5939 if (flag_ira_verbose
< 10)
5940 ira_dump_file
= dump_file
;
5942 /* If pic_offset_table_rtx is a pseudo register, then keep it so
5943 after reload to avoid possible wrong usages of hard reg assigned
5945 if (pic_offset_table_rtx
5946 && REGNO (pic_offset_table_rtx
) >= FIRST_PSEUDO_REGISTER
)
5947 pic_offset_table_regno
= REGNO (pic_offset_table_rtx
);
5949 timevar_push (TV_RELOAD
);
5952 if (current_loops
!= NULL
)
5954 loop_optimizer_finalize ();
5955 free_dominance_info (CDI_DOMINATORS
);
5957 FOR_ALL_BB_FN (bb
, cfun
)
5958 bb
->loop_father
= NULL
;
5959 current_loops
= NULL
;
5963 lra (ira_dump_file
);
5964 /* ???!!! Move it before lra () when we use ira_reg_equiv in
5966 vec_free (reg_equivs
);
5972 df_set_flags (DF_NO_INSN_RESCAN
);
5973 build_insn_chain ();
5975 need_dce
= reload (get_insns (), ira_conflicts_p
);
5978 timevar_pop (TV_RELOAD
);
5980 timevar_push (TV_IRA
);
5982 if (ira_conflicts_p
&& ! ira_use_lra_p
)
5984 ira_free (ira_spilled_reg_stack_slots
);
5985 ira_finish_assign ();
5988 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
5989 && overall_cost_before
!= ira_overall_cost
)
5990 fprintf (ira_dump_file
, "+++Overall after reload %" PRId64
"\n",
5993 flag_ira_share_spill_slots
= saved_flag_ira_share_spill_slots
;
5995 if (! ira_use_lra_p
)
5998 if (current_loops
!= NULL
)
6000 loop_optimizer_finalize ();
6001 free_dominance_info (CDI_DOMINATORS
);
6003 FOR_ALL_BB_FN (bb
, cfun
)
6004 bb
->loop_father
= NULL
;
6005 current_loops
= NULL
;
6008 regstat_free_n_sets_and_refs ();
6012 cleanup_cfg (CLEANUP_EXPENSIVE
);
6014 finish_reg_equiv ();
6016 bitmap_obstack_release (&ira_bitmap_obstack
);
6017 #ifndef IRA_NO_OBSTACK
6018 obstack_free (&ira_obstack
, NULL
);
6021 /* The code after the reload has changed so much that at this point
6022 we might as well just rescan everything. Note that
6023 df_rescan_all_insns is not going to help here because it does not
6024 touch the artificial uses and defs. */
6025 df_finish_pass (true);
6026 df_scan_alloc (NULL
);
6031 df_live_add_problem ();
6032 df_live_set_all_dirty ();
6038 if (need_dce
&& optimize
)
6041 /* Diagnose uses of the hard frame pointer when it is used as a global
6042 register. Often we can get away with letting the user appropriate
6043 the frame pointer, but we should let them know when code generation
6044 makes that impossible. */
6045 if (global_regs
[HARD_FRAME_POINTER_REGNUM
] && frame_pointer_needed
)
6047 tree decl
= global_regs_decl
[HARD_FRAME_POINTER_REGNUM
];
6048 error_at (DECL_SOURCE_LOCATION (current_function_decl
),
6049 "frame pointer required, but reserved");
6050 inform (DECL_SOURCE_LOCATION (decl
), "for %qD", decl
);
6053 /* If we are doing generic stack checking, give a warning if this
6054 function's frame size is larger than we expect. */
6055 if (flag_stack_check
== GENERIC_STACK_CHECK
)
6057 poly_int64 size
= get_frame_size () + STACK_CHECK_FIXED_FRAME_SIZE
;
6059 for (int i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
6060 if (df_regs_ever_live_p (i
)
6062 && !crtl
->abi
->clobbers_full_reg_p (i
))
6063 size
+= UNITS_PER_WORD
;
6065 if (constant_lower_bound (size
) > STACK_CHECK_MAX_FRAME_SIZE
)
6066 warning (0, "frame size too large for reliable stack checking");
6069 if (pic_offset_table_regno
!= INVALID_REGNUM
)
6070 pic_offset_table_rtx
= gen_rtx_REG (Pmode
, pic_offset_table_regno
);
6072 timevar_pop (TV_IRA
);
6075 /* Run the integrated register allocator. */
6079 const pass_data pass_data_ira
=
6081 RTL_PASS
, /* type */
6083 OPTGROUP_NONE
, /* optinfo_flags */
6085 0, /* properties_required */
6086 0, /* properties_provided */
6087 0, /* properties_destroyed */
6088 0, /* todo_flags_start */
6089 TODO_do_not_ggc_collect
, /* todo_flags_finish */
6092 class pass_ira
: public rtl_opt_pass
6095 pass_ira (gcc::context
*ctxt
)
6096 : rtl_opt_pass (pass_data_ira
, ctxt
)
6099 /* opt_pass methods: */
6100 bool gate (function
*) final override
6102 return !targetm
.no_register_allocation
;
6104 unsigned int execute (function
*) final override
6110 }; // class pass_ira
6115 make_pass_ira (gcc::context
*ctxt
)
6117 return new pass_ira (ctxt
);
6122 const pass_data pass_data_reload
=
6124 RTL_PASS
, /* type */
6125 "reload", /* name */
6126 OPTGROUP_NONE
, /* optinfo_flags */
6127 TV_RELOAD
, /* tv_id */
6128 0, /* properties_required */
6129 0, /* properties_provided */
6130 0, /* properties_destroyed */
6131 0, /* todo_flags_start */
6132 0, /* todo_flags_finish */
6135 class pass_reload
: public rtl_opt_pass
6138 pass_reload (gcc::context
*ctxt
)
6139 : rtl_opt_pass (pass_data_reload
, ctxt
)
6142 /* opt_pass methods: */
6143 bool gate (function
*) final override
6145 return !targetm
.no_register_allocation
;
6147 unsigned int execute (function
*) final override
6153 }; // class pass_reload
6158 make_pass_reload (gcc::context
*ctxt
)
6160 return new pass_reload (ctxt
);