1 /* Integrated Register Allocator (IRA) entry point.
2 Copyright (C) 2006-2014 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* The integrated register allocator (IRA) is a
22 regional register allocator performing graph coloring on a top-down
23 traversal of nested regions. Graph coloring in a region is based
24 on Chaitin-Briggs algorithm. It is called integrated because
25 register coalescing, register live range splitting, and choosing a
26 better hard register are done on-the-fly during coloring. Register
27 coalescing and choosing a cheaper hard register is done by hard
28 register preferencing during hard register assigning. The live
29 range splitting is a byproduct of the regional register allocation.
31 Major IRA notions are:
33 o *Region* is a part of CFG where graph coloring based on
34 Chaitin-Briggs algorithm is done. IRA can work on any set of
35 nested CFG regions forming a tree. Currently the regions are
36 the entire function for the root region and natural loops for
37 the other regions. Therefore data structure representing a
38 region is called loop_tree_node.
40 o *Allocno class* is a register class used for allocation of
41 given allocno. It means that only hard register of given
42 register class can be assigned to given allocno. In reality,
43 even smaller subset of (*profitable*) hard registers can be
44 assigned. In rare cases, the subset can be even smaller
45 because our modification of Chaitin-Briggs algorithm requires
46 that sets of hard registers can be assigned to allocnos forms a
47 forest, i.e. the sets can be ordered in a way where any
48 previous set is not intersected with given set or is a superset
51 o *Pressure class* is a register class belonging to a set of
52 register classes containing all of the hard-registers available
53 for register allocation. The set of all pressure classes for a
54 target is defined in the corresponding machine-description file
55 according some criteria. Register pressure is calculated only
56 for pressure classes and it affects some IRA decisions as
57 forming allocation regions.
59 o *Allocno* represents the live range of a pseudo-register in a
60 region. Besides the obvious attributes like the corresponding
61 pseudo-register number, allocno class, conflicting allocnos and
62 conflicting hard-registers, there are a few allocno attributes
63 which are important for understanding the allocation algorithm:
65 - *Live ranges*. This is a list of ranges of *program points*
66 where the allocno lives. Program points represent places
67 where a pseudo can be born or become dead (there are
68 approximately two times more program points than the insns)
69 and they are represented by integers starting with 0. The
70 live ranges are used to find conflicts between allocnos.
71 They also play very important role for the transformation of
72 the IRA internal representation of several regions into a one
73 region representation. The later is used during the reload
74 pass work because each allocno represents all of the
75 corresponding pseudo-registers.
77 - *Hard-register costs*. This is a vector of size equal to the
78 number of available hard-registers of the allocno class. The
79 cost of a callee-clobbered hard-register for an allocno is
80 increased by the cost of save/restore code around the calls
81 through the given allocno's life. If the allocno is a move
82 instruction operand and another operand is a hard-register of
83 the allocno class, the cost of the hard-register is decreased
86 When an allocno is assigned, the hard-register with minimal
87 full cost is used. Initially, a hard-register's full cost is
88 the corresponding value from the hard-register's cost vector.
89 If the allocno is connected by a *copy* (see below) to
90 another allocno which has just received a hard-register, the
91 cost of the hard-register is decreased. Before choosing a
92 hard-register for an allocno, the allocno's current costs of
93 the hard-registers are modified by the conflict hard-register
94 costs of all of the conflicting allocnos which are not
97 - *Conflict hard-register costs*. This is a vector of the same
98 size as the hard-register costs vector. To permit an
99 unassigned allocno to get a better hard-register, IRA uses
100 this vector to calculate the final full cost of the
101 available hard-registers. Conflict hard-register costs of an
102 unassigned allocno are also changed with a change of the
103 hard-register cost of the allocno when a copy involving the
104 allocno is processed as described above. This is done to
105 show other unassigned allocnos that a given allocno prefers
106 some hard-registers in order to remove the move instruction
107 corresponding to the copy.
109 o *Cap*. If a pseudo-register does not live in a region but
110 lives in a nested region, IRA creates a special allocno called
111 a cap in the outer region. A region cap is also created for a
114 o *Copy*. Allocnos can be connected by copies. Copies are used
115 to modify hard-register costs for allocnos during coloring.
116 Such modifications reflects a preference to use the same
117 hard-register for the allocnos connected by copies. Usually
118 copies are created for move insns (in this case it results in
119 register coalescing). But IRA also creates copies for operands
120 of an insn which should be assigned to the same hard-register
121 due to constraints in the machine description (it usually
122 results in removing a move generated in reload to satisfy
123 the constraints) and copies referring to the allocno which is
124 the output operand of an instruction and the allocno which is
125 an input operand dying in the instruction (creation of such
126 copies results in less register shuffling). IRA *does not*
127 create copies between the same register allocnos from different
128 regions because we use another technique for propagating
129 hard-register preference on the borders of regions.
131 Allocnos (including caps) for the upper region in the region tree
132 *accumulate* information important for coloring from allocnos with
133 the same pseudo-register from nested regions. This includes
134 hard-register and memory costs, conflicts with hard-registers,
135 allocno conflicts, allocno copies and more. *Thus, attributes for
136 allocnos in a region have the same values as if the region had no
137 subregions*. It means that attributes for allocnos in the
138 outermost region corresponding to the function have the same values
139 as though the allocation used only one region which is the entire
140 function. It also means that we can look at IRA work as if the
141 first IRA did allocation for all function then it improved the
142 allocation for loops then their subloops and so on.
144 IRA major passes are:
146 o Building IRA internal representation which consists of the
149 * First, IRA builds regions and creates allocnos (file
150 ira-build.c) and initializes most of their attributes.
152 * Then IRA finds an allocno class for each allocno and
153 calculates its initial (non-accumulated) cost of memory and
154 each hard-register of its allocno class (file ira-cost.c).
156 * IRA creates live ranges of each allocno, calulates register
157 pressure for each pressure class in each region, sets up
158 conflict hard registers for each allocno and info about calls
159 the allocno lives through (file ira-lives.c).
161 * IRA removes low register pressure loops from the regions
162 mostly to speed IRA up (file ira-build.c).
164 * IRA propagates accumulated allocno info from lower region
165 allocnos to corresponding upper region allocnos (file
168 * IRA creates all caps (file ira-build.c).
170 * Having live-ranges of allocnos and their classes, IRA creates
171 conflicting allocnos for each allocno. Conflicting allocnos
172 are stored as a bit vector or array of pointers to the
173 conflicting allocnos whatever is more profitable (file
174 ira-conflicts.c). At this point IRA creates allocno copies.
176 o Coloring. Now IRA has all necessary info to start graph coloring
177 process. It is done in each region on top-down traverse of the
178 region tree (file ira-color.c). There are following subpasses:
180 * Finding profitable hard registers of corresponding allocno
181 class for each allocno. For example, only callee-saved hard
182 registers are frequently profitable for allocnos living
183 through colors. If the profitable hard register set of
184 allocno does not form a tree based on subset relation, we use
185 some approximation to form the tree. This approximation is
186 used to figure out trivial colorability of allocnos. The
187 approximation is a pretty rare case.
189 * Putting allocnos onto the coloring stack. IRA uses Briggs
190 optimistic coloring which is a major improvement over
191 Chaitin's coloring. Therefore IRA does not spill allocnos at
192 this point. There is some freedom in the order of putting
193 allocnos on the stack which can affect the final result of
194 the allocation. IRA uses some heuristics to improve the
195 order. The major one is to form *threads* from colorable
196 allocnos and push them on the stack by threads. Thread is a
197 set of non-conflicting colorable allocnos connected by
198 copies. The thread contains allocnos from the colorable
199 bucket or colorable allocnos already pushed onto the coloring
200 stack. Pushing thread allocnos one after another onto the
201 stack increases chances of removing copies when the allocnos
202 get the same hard reg.
204 We also use a modification of Chaitin-Briggs algorithm which
205 works for intersected register classes of allocnos. To
206 figure out trivial colorability of allocnos, the mentioned
207 above tree of hard register sets is used. To get an idea how
208 the algorithm works in i386 example, let us consider an
209 allocno to which any general hard register can be assigned.
210 If the allocno conflicts with eight allocnos to which only
211 EAX register can be assigned, given allocno is still
212 trivially colorable because all conflicting allocnos might be
213 assigned only to EAX and all other general hard registers are
216 To get an idea of the used trivial colorability criterion, it
217 is also useful to read article "Graph-Coloring Register
218 Allocation for Irregular Architectures" by Michael D. Smith
219 and Glen Holloway. Major difference between the article
220 approach and approach used in IRA is that Smith's approach
221 takes register classes only from machine description and IRA
222 calculate register classes from intermediate code too
223 (e.g. an explicit usage of hard registers in RTL code for
224 parameter passing can result in creation of additional
225 register classes which contain or exclude the hard
226 registers). That makes IRA approach useful for improving
227 coloring even for architectures with regular register files
228 and in fact some benchmarking shows the improvement for
229 regular class architectures is even bigger than for irregular
230 ones. Another difference is that Smith's approach chooses
231 intersection of classes of all insn operands in which a given
232 pseudo occurs. IRA can use bigger classes if it is still
233 more profitable than memory usage.
235 * Popping the allocnos from the stack and assigning them hard
236 registers. If IRA can not assign a hard register to an
237 allocno and the allocno is coalesced, IRA undoes the
238 coalescing and puts the uncoalesced allocnos onto the stack in
239 the hope that some such allocnos will get a hard register
240 separately. If IRA fails to assign hard register or memory
241 is more profitable for it, IRA spills the allocno. IRA
242 assigns the allocno the hard-register with minimal full
243 allocation cost which reflects the cost of usage of the
244 hard-register for the allocno and cost of usage of the
245 hard-register for allocnos conflicting with given allocno.
247 * Chaitin-Briggs coloring assigns as many pseudos as possible
248 to hard registers. After coloringh 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 allono assigning in the region, IRA modifies the hard
255 register and memory costs for the corresponding allocnos in
256 the subregions to reflect the cost of possible loads, stores,
257 or moves on the border of the region and its subregions.
258 When default regional allocation algorithm is used
259 (-fira-algorithm=mixed), IRA just propagates the assignment
260 for allocnos if the register pressure in the region for the
261 corresponding pressure class is less than number of available
262 hard registers for given pressure class.
264 o Spill/restore code moving. When IRA performs an allocation
265 by traversing regions in top-down order, it does not know what
266 happens below in the region tree. Therefore, sometimes IRA
267 misses opportunities to perform a better allocation. A simple
268 optimization tries to improve allocation in a region having
269 subregions and containing in another region. If the
270 corresponding allocnos in the subregion are spilled, it spills
271 the region allocno if it is profitable. The optimization
272 implements a simple iterative algorithm performing profitable
273 transformations while they are still possible. It is fast in
274 practice, so there is no real need for a better time complexity
277 o Code change. After coloring, two allocnos representing the
278 same pseudo-register outside and inside a region respectively
279 may be assigned to different locations (hard-registers or
280 memory). In this case IRA creates and uses a new
281 pseudo-register inside the region and adds code to move allocno
282 values on the region's borders. This is done during top-down
283 traversal of the regions (file ira-emit.c). In some
284 complicated cases IRA can create a new allocno to move allocno
285 values (e.g. when a swap of values stored in two hard-registers
286 is needed). At this stage, the new allocno is marked as
287 spilled. IRA still creates the pseudo-register and the moves
288 on the region borders even when both allocnos were assigned to
289 the same hard-register. If the reload pass spills a
290 pseudo-register for some reason, the effect will be smaller
291 because another allocno will still be in the hard-register. In
292 most cases, this is better then spilling both allocnos. If
293 reload does not change the allocation for the two
294 pseudo-registers, the trivial move will be removed by
295 post-reload optimizations. IRA does not generate moves for
296 allocnos assigned to the same hard register when the default
297 regional allocation algorithm is used and the register pressure
298 in the region for the corresponding pressure class is less than
299 number of available hard registers for given pressure class.
300 IRA also does some optimizations to remove redundant stores and
301 to reduce code duplication on the region borders.
303 o Flattening internal representation. After changing code, IRA
304 transforms its internal representation for several regions into
305 one region representation (file ira-build.c). This process is
306 called IR flattening. Such process is more complicated than IR
307 rebuilding would be, but is much faster.
309 o After IR flattening, IRA tries to assign hard registers to all
310 spilled allocnos. This is impelemented by a simple and fast
311 priority coloring algorithm (see function
312 ira_reassign_conflict_allocnos::ira-color.c). Here new allocnos
313 created during the code change pass can be assigned to hard
316 o At the end IRA calls the reload pass. The reload pass
317 communicates with IRA through several functions in file
318 ira-color.c to improve its decisions in
320 * sharing stack slots for the spilled pseudos based on IRA info
321 about pseudo-register conflicts.
323 * reassigning hard-registers to all spilled pseudos at the end
324 of each reload iteration.
326 * choosing a better hard-register to spill based on IRA info
327 about pseudo-register live ranges and the register pressure
328 in places where the pseudo-register lives.
330 IRA uses a lot of data representing the target processors. These
331 data are initilized in file ira.c.
333 If function has no loops (or the loops are ignored when
334 -fira-algorithm=CB is used), we have classic Chaitin-Briggs
335 coloring (only instead of separate pass of coalescing, we use hard
336 register preferencing). In such case, IRA works much faster
337 because many things are not made (like IR flattening, the
338 spill/restore optimization, and the code change).
340 Literature is worth to read for better understanding the code:
342 o Preston Briggs, Keith D. Cooper, Linda Torczon. Improvements to
343 Graph Coloring Register Allocation.
345 o David Callahan, Brian Koblenz. Register allocation via
346 hierarchical graph coloring.
348 o Keith Cooper, Anshuman Dasgupta, Jason Eckhardt. Revisiting Graph
349 Coloring Register Allocation: A Study of the Chaitin-Briggs and
350 Callahan-Koblenz Algorithms.
352 o Guei-Yuan Lueh, Thomas Gross, and Ali-Reza Adl-Tabatabai. Global
353 Register Allocation Based on Graph Fusion.
355 o Michael D. Smith and Glenn Holloway. Graph-Coloring Register
356 Allocation for Irregular Architectures
358 o Vladimir Makarov. The Integrated Register Allocator for GCC.
360 o Vladimir Makarov. The top-down register allocator for irregular
361 register file architectures.
368 #include "coretypes.h"
378 #include "hard-reg-set.h"
379 #include "basic-block.h"
384 #include "tree-pass.h"
388 #include "diagnostic-core.h"
389 #include "function.h"
396 struct target_ira default_target_ira
;
397 struct target_ira_int default_target_ira_int
;
398 #if SWITCHABLE_TARGET
399 struct target_ira
*this_target_ira
= &default_target_ira
;
400 struct 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 struct 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 int ira_overall_cost
, overall_cost_before
;
422 int ira_reg_cost
, ira_mem_cost
;
423 int 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
][m
] - 1; i
>= 0; i
--)
453 if (hard_regno
+ i
< FIRST_PSEUDO_REGISTER
)
454 SET_HARD_REG_BIT (ira_reg_mode_hard_regset
[hard_regno
][m
],
460 #define no_unit_alloc_regs \
461 (this_target_ira_int->x_no_unit_alloc_regs)
463 /* The function sets up the three arrays declared above. */
465 setup_class_hard_regs (void)
467 int cl
, i
, hard_regno
, n
;
468 HARD_REG_SET processed_hard_reg_set
;
470 ira_assert (SHRT_MAX
>= FIRST_PSEUDO_REGISTER
);
471 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
473 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
474 AND_COMPL_HARD_REG_SET (temp_hard_regset
, 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 COPY_HARD_REG_SET (no_unit_alloc_regs
, fixed_reg_set
);
517 if (! use_hard_frame_p
)
518 SET_HARD_REG_BIT (no_unit_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
519 setup_class_hard_regs ();
524 #define alloc_reg_class_subclasses \
525 (this_target_ira_int->x_alloc_reg_class_subclasses)
527 /* Initialize the table of subclasses of each reg class. */
529 setup_reg_subclasses (void)
532 HARD_REG_SET temp_hard_regset2
;
534 for (i
= 0; i
< N_REG_CLASSES
; i
++)
535 for (j
= 0; j
< N_REG_CLASSES
; j
++)
536 alloc_reg_class_subclasses
[i
][j
] = LIM_REG_CLASSES
;
538 for (i
= 0; i
< N_REG_CLASSES
; i
++)
540 if (i
== (int) NO_REGS
)
543 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[i
]);
544 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
545 if (hard_reg_set_empty_p (temp_hard_regset
))
547 for (j
= 0; j
< N_REG_CLASSES
; j
++)
552 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[j
]);
553 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
554 if (! hard_reg_set_subset_p (temp_hard_regset
,
557 p
= &alloc_reg_class_subclasses
[j
][0];
558 while (*p
!= LIM_REG_CLASSES
) p
++;
559 *p
= (enum reg_class
) i
;
566 /* Set up IRA_MEMORY_MOVE_COST and IRA_MAX_MEMORY_MOVE_COST. */
568 setup_class_subset_and_memory_move_costs (void)
570 int cl
, cl2
, mode
, cost
;
571 HARD_REG_SET temp_hard_regset2
;
573 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
574 ira_memory_move_cost
[mode
][NO_REGS
][0]
575 = ira_memory_move_cost
[mode
][NO_REGS
][1] = SHRT_MAX
;
576 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
578 if (cl
!= (int) NO_REGS
)
579 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
581 ira_max_memory_move_cost
[mode
][cl
][0]
582 = ira_memory_move_cost
[mode
][cl
][0]
583 = memory_move_cost ((enum machine_mode
) mode
,
584 (reg_class_t
) cl
, false);
585 ira_max_memory_move_cost
[mode
][cl
][1]
586 = ira_memory_move_cost
[mode
][cl
][1]
587 = memory_move_cost ((enum machine_mode
) mode
,
588 (reg_class_t
) cl
, true);
589 /* Costs for NO_REGS are used in cost calculation on the
590 1st pass when the preferred register classes are not
591 known yet. In this case we take the best scenario. */
592 if (ira_memory_move_cost
[mode
][NO_REGS
][0]
593 > ira_memory_move_cost
[mode
][cl
][0])
594 ira_max_memory_move_cost
[mode
][NO_REGS
][0]
595 = ira_memory_move_cost
[mode
][NO_REGS
][0]
596 = ira_memory_move_cost
[mode
][cl
][0];
597 if (ira_memory_move_cost
[mode
][NO_REGS
][1]
598 > ira_memory_move_cost
[mode
][cl
][1])
599 ira_max_memory_move_cost
[mode
][NO_REGS
][1]
600 = ira_memory_move_cost
[mode
][NO_REGS
][1]
601 = ira_memory_move_cost
[mode
][cl
][1];
604 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
605 for (cl2
= (int) N_REG_CLASSES
- 1; cl2
>= 0; cl2
--)
607 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
608 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
609 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl2
]);
610 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
611 ira_class_subset_p
[cl
][cl2
]
612 = hard_reg_set_subset_p (temp_hard_regset
, temp_hard_regset2
);
613 if (! hard_reg_set_empty_p (temp_hard_regset2
)
614 && hard_reg_set_subset_p (reg_class_contents
[cl2
],
615 reg_class_contents
[cl
]))
616 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
618 cost
= ira_memory_move_cost
[mode
][cl2
][0];
619 if (cost
> ira_max_memory_move_cost
[mode
][cl
][0])
620 ira_max_memory_move_cost
[mode
][cl
][0] = cost
;
621 cost
= ira_memory_move_cost
[mode
][cl2
][1];
622 if (cost
> ira_max_memory_move_cost
[mode
][cl
][1])
623 ira_max_memory_move_cost
[mode
][cl
][1] = cost
;
626 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
627 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
629 ira_memory_move_cost
[mode
][cl
][0]
630 = ira_max_memory_move_cost
[mode
][cl
][0];
631 ira_memory_move_cost
[mode
][cl
][1]
632 = ira_max_memory_move_cost
[mode
][cl
][1];
634 setup_reg_subclasses ();
639 /* Define the following macro if allocation through malloc if
641 #define IRA_NO_OBSTACK
643 #ifndef IRA_NO_OBSTACK
644 /* Obstack used for storing all dynamic data (except bitmaps) of the
646 static struct obstack ira_obstack
;
649 /* Obstack used for storing all bitmaps of the IRA. */
650 static struct bitmap_obstack ira_bitmap_obstack
;
652 /* Allocate memory of size LEN for IRA data. */
654 ira_allocate (size_t len
)
658 #ifndef IRA_NO_OBSTACK
659 res
= obstack_alloc (&ira_obstack
, len
);
666 /* Free memory ADDR allocated for IRA data. */
668 ira_free (void *addr ATTRIBUTE_UNUSED
)
670 #ifndef IRA_NO_OBSTACK
678 /* Allocate and returns bitmap for IRA. */
680 ira_allocate_bitmap (void)
682 return BITMAP_ALLOC (&ira_bitmap_obstack
);
685 /* Free bitmap B allocated for IRA. */
687 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED
)
694 /* Output information about allocation of all allocnos (except for
695 caps) into file F. */
697 ira_print_disposition (FILE *f
)
703 fprintf (f
, "Disposition:");
704 max_regno
= max_reg_num ();
705 for (n
= 0, i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
706 for (a
= ira_regno_allocno_map
[i
];
708 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
713 fprintf (f
, " %4d:r%-4d", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
714 if ((bb
= ALLOCNO_LOOP_TREE_NODE (a
)->bb
) != NULL
)
715 fprintf (f
, "b%-3d", bb
->index
);
717 fprintf (f
, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a
)->loop_num
);
718 if (ALLOCNO_HARD_REGNO (a
) >= 0)
719 fprintf (f
, " %3d", ALLOCNO_HARD_REGNO (a
));
726 /* Outputs information about allocation of all allocnos into
729 ira_debug_disposition (void)
731 ira_print_disposition (stderr
);
736 /* Set up ira_stack_reg_pressure_class which is the biggest pressure
737 register class containing stack registers or NO_REGS if there are
738 no stack registers. To find this class, we iterate through all
739 register pressure classes and choose the first register pressure
740 class containing all the stack registers and having the biggest
743 setup_stack_reg_pressure_class (void)
745 ira_stack_reg_pressure_class
= NO_REGS
;
750 HARD_REG_SET temp_hard_regset2
;
752 CLEAR_HARD_REG_SET (temp_hard_regset
);
753 for (i
= FIRST_STACK_REG
; i
<= LAST_STACK_REG
; i
++)
754 SET_HARD_REG_BIT (temp_hard_regset
, i
);
756 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
758 cl
= ira_pressure_classes
[i
];
759 COPY_HARD_REG_SET (temp_hard_regset2
, temp_hard_regset
);
760 AND_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl
]);
761 size
= hard_reg_set_size (temp_hard_regset2
);
765 ira_stack_reg_pressure_class
= cl
;
772 /* Find pressure classes which are register classes for which we
773 calculate register pressure in IRA, register pressure sensitive
774 insn scheduling, and register pressure sensitive loop invariant
777 To make register pressure calculation easy, we always use
778 non-intersected register pressure classes. A move of hard
779 registers from one register pressure class is not more expensive
780 than load and store of the hard registers. Most likely an allocno
781 class will be a subset of a register pressure class and in many
782 cases a register pressure class. That makes usage of register
783 pressure classes a good approximation to find a high register
786 setup_pressure_classes (void)
788 int cost
, i
, n
, curr
;
790 enum reg_class pressure_classes
[N_REG_CLASSES
];
792 HARD_REG_SET temp_hard_regset2
;
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
++)
814 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
815 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
816 AND_COMPL_HARD_REG_SET (temp_hard_regset
,
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 ((enum 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 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
832 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
833 /* Remove so far added pressure classes which are subset of the
834 current candidate class. Prefer GENERAL_REGS as a pressure
835 register class to another class containing the same
836 allocatable hard registers. We do this because machine
837 dependent cost hooks might give wrong costs for the latter
838 class but always give the right cost for the former class
840 for (i
= 0; i
< n
; i
++)
842 cl2
= pressure_classes
[i
];
843 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl2
]);
844 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
845 if (hard_reg_set_subset_p (temp_hard_regset
, temp_hard_regset2
)
846 && (! hard_reg_set_equal_p (temp_hard_regset
, temp_hard_regset2
)
847 || cl2
== (int) GENERAL_REGS
))
849 pressure_classes
[curr
++] = (enum reg_class
) cl2
;
853 if (hard_reg_set_subset_p (temp_hard_regset2
, temp_hard_regset
)
854 && (! hard_reg_set_equal_p (temp_hard_regset2
, temp_hard_regset
)
855 || cl
== (int) GENERAL_REGS
))
857 if (hard_reg_set_equal_p (temp_hard_regset2
, temp_hard_regset
))
859 pressure_classes
[curr
++] = (enum reg_class
) cl2
;
861 /* If the current candidate is a subset of a so far added
862 pressure class, don't add it to the list of the pressure
865 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 COPY_HARD_REG_SET (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 IOR_HARD_REG_SET (ignore_hard_regs
, reg_class_contents
[cl
]);
891 for (i
= 0; i
< n
; i
++)
892 if ((int) pressure_classes
[i
] == cl
)
894 IOR_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl
]);
896 IOR_HARD_REG_SET (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 alocatable 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 AND_COMPL_HARD_REG_SET (temp_hard_regset
, ignore_hard_regs
);
904 AND_COMPL_HARD_REG_SET (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 can not 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 ((enum 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 regiters can
961 be used for allocation, e.g. x86 port in 32-bit mode can not 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.c 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.c 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 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[i
]);
997 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
998 for (j
= 0; j
< n
; j
++)
1001 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl
]);
1002 AND_COMPL_HARD_REG_SET (temp_hard_regset2
,
1003 no_unit_alloc_regs
);
1004 if (hard_reg_set_equal_p (temp_hard_regset
,
1009 classes
[n
++] = (enum reg_class
) i
;
1010 else if (i
== GENERAL_REGS
)
1011 /* Prefer general regs. For i386 example, it means that
1012 we prefer GENERAL_REGS over INDEX_REGS or LEGACY_REGS
1013 (all of them consists of the same available hard
1015 classes
[j
] = (enum reg_class
) i
;
1017 classes
[n
] = LIM_REG_CLASSES
;
1019 /* Set up classes which can be used for allocnos as classes
1020 conatining non-empty unique sets of allocatable hard
1022 ira_allocno_classes_num
= 0;
1023 for (i
= 0; (cl
= classes
[i
]) != LIM_REG_CLASSES
; i
++)
1024 if (ira_class_hard_regs_num
[cl
] > 0)
1025 ira_allocno_classes
[ira_allocno_classes_num
++] = (enum reg_class
) cl
;
1026 ira_important_classes_num
= 0;
1027 /* Add non-allocno classes containing to non-empty set of
1028 allocatable hard regs. */
1029 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1030 if (ira_class_hard_regs_num
[cl
] > 0)
1032 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
1033 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1035 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1037 COPY_HARD_REG_SET (temp_hard_regset2
,
1038 reg_class_contents
[ira_allocno_classes
[j
]]);
1039 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
1040 if ((enum reg_class
) cl
== ira_allocno_classes
[j
])
1042 else if (hard_reg_set_subset_p (temp_hard_regset
,
1046 if (set_p
&& j
>= ira_allocno_classes_num
)
1047 ira_important_classes
[ira_important_classes_num
++]
1048 = (enum reg_class
) cl
;
1050 /* Now add allocno classes to the important classes. */
1051 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1052 ira_important_classes
[ira_important_classes_num
++]
1053 = ira_allocno_classes
[j
];
1054 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1056 ira_reg_allocno_class_p
[cl
] = false;
1057 ira_reg_pressure_class_p
[cl
] = false;
1059 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1060 ira_reg_allocno_class_p
[ira_allocno_classes
[j
]] = true;
1061 setup_pressure_classes ();
1062 setup_uniform_class_p ();
1065 /* Setup translation in CLASS_TRANSLATE of all classes into a class
1066 given by array CLASSES of length CLASSES_NUM. The function is used
1067 make translation any reg class to an allocno class or to an
1068 pressure class. This translation is necessary for some
1069 calculations when we can use only allocno or pressure classes and
1070 such translation represents an approximate representation of all
1073 The translation in case when allocatable hard register set of a
1074 given class is subset of allocatable hard register set of a class
1075 in CLASSES is pretty simple. We use smallest classes from CLASSES
1076 containing a given class. If allocatable hard register set of a
1077 given class is not a subset of any corresponding set of a class
1078 from CLASSES, we use the cheapest (with load/store point of view)
1079 class from CLASSES whose set intersects with given class set */
1081 setup_class_translate_array (enum reg_class
*class_translate
,
1082 int classes_num
, enum reg_class
*classes
)
1085 enum reg_class aclass
, best_class
, *cl_ptr
;
1086 int i
, cost
, min_cost
, best_cost
;
1088 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1089 class_translate
[cl
] = NO_REGS
;
1091 for (i
= 0; i
< classes_num
; i
++)
1093 aclass
= classes
[i
];
1094 for (cl_ptr
= &alloc_reg_class_subclasses
[aclass
][0];
1095 (cl
= *cl_ptr
) != LIM_REG_CLASSES
;
1097 if (class_translate
[cl
] == NO_REGS
)
1098 class_translate
[cl
] = aclass
;
1099 class_translate
[aclass
] = aclass
;
1101 /* For classes which are not fully covered by one of given classes
1102 (in other words covered by more one given class), use the
1104 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1106 if (cl
== NO_REGS
|| class_translate
[cl
] != NO_REGS
)
1108 best_class
= NO_REGS
;
1109 best_cost
= INT_MAX
;
1110 for (i
= 0; i
< classes_num
; i
++)
1112 aclass
= classes
[i
];
1113 COPY_HARD_REG_SET (temp_hard_regset
,
1114 reg_class_contents
[aclass
]);
1115 AND_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
1116 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1117 if (! hard_reg_set_empty_p (temp_hard_regset
))
1120 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
1122 cost
= (ira_memory_move_cost
[mode
][aclass
][0]
1123 + ira_memory_move_cost
[mode
][aclass
][1]);
1124 if (min_cost
> cost
)
1127 if (best_class
== NO_REGS
|| best_cost
> min_cost
)
1129 best_class
= aclass
;
1130 best_cost
= min_cost
;
1134 class_translate
[cl
] = best_class
;
1138 /* Set up array IRA_ALLOCNO_CLASS_TRANSLATE and
1139 IRA_PRESSURE_CLASS_TRANSLATE. */
1141 setup_class_translate (void)
1143 setup_class_translate_array (ira_allocno_class_translate
,
1144 ira_allocno_classes_num
, ira_allocno_classes
);
1145 setup_class_translate_array (ira_pressure_class_translate
,
1146 ira_pressure_classes_num
, ira_pressure_classes
);
1149 /* Order numbers of allocno classes in original target allocno class
1150 array, -1 for non-allocno classes. */
1151 static int allocno_class_order
[N_REG_CLASSES
];
1153 /* The function used to sort the important classes. */
1155 comp_reg_classes_func (const void *v1p
, const void *v2p
)
1157 enum reg_class cl1
= *(const enum reg_class
*) v1p
;
1158 enum reg_class cl2
= *(const enum reg_class
*) v2p
;
1159 enum reg_class tcl1
, tcl2
;
1162 tcl1
= ira_allocno_class_translate
[cl1
];
1163 tcl2
= ira_allocno_class_translate
[cl2
];
1164 if (tcl1
!= NO_REGS
&& tcl2
!= NO_REGS
1165 && (diff
= allocno_class_order
[tcl1
] - allocno_class_order
[tcl2
]) != 0)
1167 return (int) cl1
- (int) cl2
;
1170 /* For correct work of function setup_reg_class_relation we need to
1171 reorder important classes according to the order of their allocno
1172 classes. It places important classes containing the same
1173 allocatable hard register set adjacent to each other and allocno
1174 class with the allocatable hard register set right after the other
1175 important classes with the same set.
1177 In example from comments of function
1178 setup_allocno_and_important_classes, it places LEGACY_REGS and
1179 GENERAL_REGS close to each other and GENERAL_REGS is after
1182 reorder_important_classes (void)
1186 for (i
= 0; i
< N_REG_CLASSES
; i
++)
1187 allocno_class_order
[i
] = -1;
1188 for (i
= 0; i
< ira_allocno_classes_num
; i
++)
1189 allocno_class_order
[ira_allocno_classes
[i
]] = i
;
1190 qsort (ira_important_classes
, ira_important_classes_num
,
1191 sizeof (enum reg_class
), comp_reg_classes_func
);
1192 for (i
= 0; i
< ira_important_classes_num
; i
++)
1193 ira_important_class_nums
[ira_important_classes
[i
]] = i
;
1196 /* Set up IRA_REG_CLASS_SUBUNION, IRA_REG_CLASS_SUPERUNION,
1197 IRA_REG_CLASS_SUPER_CLASSES, IRA_REG_CLASSES_INTERSECT, and
1198 IRA_REG_CLASSES_INTERSECT_P. For the meaning of the relations,
1199 please see corresponding comments in ira-int.h. */
1201 setup_reg_class_relations (void)
1203 int i
, cl1
, cl2
, cl3
;
1204 HARD_REG_SET intersection_set
, union_set
, temp_set2
;
1205 bool important_class_p
[N_REG_CLASSES
];
1207 memset (important_class_p
, 0, sizeof (important_class_p
));
1208 for (i
= 0; i
< ira_important_classes_num
; i
++)
1209 important_class_p
[ira_important_classes
[i
]] = true;
1210 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1212 ira_reg_class_super_classes
[cl1
][0] = LIM_REG_CLASSES
;
1213 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1215 ira_reg_classes_intersect_p
[cl1
][cl2
] = false;
1216 ira_reg_class_intersect
[cl1
][cl2
] = NO_REGS
;
1217 ira_reg_class_subset
[cl1
][cl2
] = NO_REGS
;
1218 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl1
]);
1219 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1220 COPY_HARD_REG_SET (temp_set2
, reg_class_contents
[cl2
]);
1221 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1222 if (hard_reg_set_empty_p (temp_hard_regset
)
1223 && hard_reg_set_empty_p (temp_set2
))
1225 /* The both classes have no allocatable hard registers
1226 -- take all class hard registers into account and use
1227 reg_class_subunion and reg_class_superunion. */
1230 cl3
= reg_class_subclasses
[cl1
][i
];
1231 if (cl3
== LIM_REG_CLASSES
)
1233 if (reg_class_subset_p (ira_reg_class_intersect
[cl1
][cl2
],
1234 (enum reg_class
) cl3
))
1235 ira_reg_class_intersect
[cl1
][cl2
] = (enum reg_class
) cl3
;
1237 ira_reg_class_subunion
[cl1
][cl2
] = reg_class_subunion
[cl1
][cl2
];
1238 ira_reg_class_superunion
[cl1
][cl2
] = reg_class_superunion
[cl1
][cl2
];
1241 ira_reg_classes_intersect_p
[cl1
][cl2
]
1242 = hard_reg_set_intersect_p (temp_hard_regset
, temp_set2
);
1243 if (important_class_p
[cl1
] && important_class_p
[cl2
]
1244 && hard_reg_set_subset_p (temp_hard_regset
, temp_set2
))
1246 /* CL1 and CL2 are important classes and CL1 allocatable
1247 hard register set is inside of CL2 allocatable hard
1248 registers -- make CL1 a superset of CL2. */
1251 p
= &ira_reg_class_super_classes
[cl1
][0];
1252 while (*p
!= LIM_REG_CLASSES
)
1254 *p
++ = (enum reg_class
) cl2
;
1255 *p
= LIM_REG_CLASSES
;
1257 ira_reg_class_subunion
[cl1
][cl2
] = NO_REGS
;
1258 ira_reg_class_superunion
[cl1
][cl2
] = NO_REGS
;
1259 COPY_HARD_REG_SET (intersection_set
, reg_class_contents
[cl1
]);
1260 AND_HARD_REG_SET (intersection_set
, reg_class_contents
[cl2
]);
1261 AND_COMPL_HARD_REG_SET (intersection_set
, no_unit_alloc_regs
);
1262 COPY_HARD_REG_SET (union_set
, reg_class_contents
[cl1
]);
1263 IOR_HARD_REG_SET (union_set
, reg_class_contents
[cl2
]);
1264 AND_COMPL_HARD_REG_SET (union_set
, no_unit_alloc_regs
);
1265 for (cl3
= 0; cl3
< N_REG_CLASSES
; cl3
++)
1267 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl3
]);
1268 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1269 if (hard_reg_set_subset_p (temp_hard_regset
, intersection_set
))
1271 /* CL3 allocatable hard register set is inside of
1272 intersection of allocatable hard register sets
1274 if (important_class_p
[cl3
])
1279 [(int) ira_reg_class_intersect
[cl1
][cl2
]]);
1280 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1281 if (! hard_reg_set_subset_p (temp_hard_regset
, temp_set2
)
1282 /* If the allocatable hard register sets are
1283 the same, prefer GENERAL_REGS or the
1284 smallest class for debugging
1286 || (hard_reg_set_equal_p (temp_hard_regset
, temp_set2
)
1287 && (cl3
== GENERAL_REGS
1288 || ((ira_reg_class_intersect
[cl1
][cl2
]
1290 && hard_reg_set_subset_p
1291 (reg_class_contents
[cl3
],
1294 ira_reg_class_intersect
[cl1
][cl2
]])))))
1295 ira_reg_class_intersect
[cl1
][cl2
] = (enum reg_class
) cl3
;
1299 reg_class_contents
[(int) ira_reg_class_subset
[cl1
][cl2
]]);
1300 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1301 if (! hard_reg_set_subset_p (temp_hard_regset
, temp_set2
)
1302 /* Ignore unavailable hard registers and prefer
1303 smallest class for debugging purposes. */
1304 || (hard_reg_set_equal_p (temp_hard_regset
, temp_set2
)
1305 && hard_reg_set_subset_p
1306 (reg_class_contents
[cl3
],
1308 [(int) ira_reg_class_subset
[cl1
][cl2
]])))
1309 ira_reg_class_subset
[cl1
][cl2
] = (enum reg_class
) cl3
;
1311 if (important_class_p
[cl3
]
1312 && hard_reg_set_subset_p (temp_hard_regset
, union_set
))
1314 /* CL3 allocatbale hard register set is inside of
1315 union of allocatable hard register sets of CL1
1319 reg_class_contents
[(int) ira_reg_class_subunion
[cl1
][cl2
]]);
1320 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1321 if (ira_reg_class_subunion
[cl1
][cl2
] == NO_REGS
1322 || (hard_reg_set_subset_p (temp_set2
, temp_hard_regset
)
1324 && (! hard_reg_set_equal_p (temp_set2
,
1326 || cl3
== GENERAL_REGS
1327 /* If the allocatable hard register sets are the
1328 same, prefer GENERAL_REGS or the smallest
1329 class for debugging purposes. */
1330 || (ira_reg_class_subunion
[cl1
][cl2
] != GENERAL_REGS
1331 && hard_reg_set_subset_p
1332 (reg_class_contents
[cl3
],
1334 [(int) ira_reg_class_subunion
[cl1
][cl2
]])))))
1335 ira_reg_class_subunion
[cl1
][cl2
] = (enum reg_class
) cl3
;
1337 if (hard_reg_set_subset_p (union_set
, temp_hard_regset
))
1339 /* CL3 allocatable hard register set contains union
1340 of allocatable hard register sets of CL1 and
1344 reg_class_contents
[(int) ira_reg_class_superunion
[cl1
][cl2
]]);
1345 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1346 if (ira_reg_class_superunion
[cl1
][cl2
] == NO_REGS
1347 || (hard_reg_set_subset_p (temp_hard_regset
, temp_set2
)
1349 && (! hard_reg_set_equal_p (temp_set2
,
1351 || cl3
== GENERAL_REGS
1352 /* If the allocatable hard register sets are the
1353 same, prefer GENERAL_REGS or the smallest
1354 class for debugging purposes. */
1355 || (ira_reg_class_superunion
[cl1
][cl2
] != GENERAL_REGS
1356 && hard_reg_set_subset_p
1357 (reg_class_contents
[cl3
],
1359 [(int) ira_reg_class_superunion
[cl1
][cl2
]])))))
1360 ira_reg_class_superunion
[cl1
][cl2
] = (enum reg_class
) cl3
;
1367 /* Output all unifrom and important classes into file F. */
1369 print_unform_and_important_classes (FILE *f
)
1371 static const char *const reg_class_names
[] = REG_CLASS_NAMES
;
1374 fprintf (f
, "Uniform classes:\n");
1375 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1376 if (ira_uniform_class_p
[cl
])
1377 fprintf (f
, " %s", reg_class_names
[cl
]);
1378 fprintf (f
, "\nImportant classes:\n");
1379 for (i
= 0; i
< ira_important_classes_num
; i
++)
1380 fprintf (f
, " %s", reg_class_names
[ira_important_classes
[i
]]);
1384 /* Output all possible allocno or pressure classes and their
1385 translation map into file F. */
1387 print_translated_classes (FILE *f
, bool pressure_p
)
1389 int classes_num
= (pressure_p
1390 ? ira_pressure_classes_num
: ira_allocno_classes_num
);
1391 enum reg_class
*classes
= (pressure_p
1392 ? ira_pressure_classes
: ira_allocno_classes
);
1393 enum reg_class
*class_translate
= (pressure_p
1394 ? ira_pressure_class_translate
1395 : ira_allocno_class_translate
);
1396 static const char *const reg_class_names
[] = REG_CLASS_NAMES
;
1399 fprintf (f
, "%s classes:\n", pressure_p
? "Pressure" : "Allocno");
1400 for (i
= 0; i
< classes_num
; i
++)
1401 fprintf (f
, " %s", reg_class_names
[classes
[i
]]);
1402 fprintf (f
, "\nClass translation:\n");
1403 for (i
= 0; i
< N_REG_CLASSES
; i
++)
1404 fprintf (f
, " %s -> %s\n", reg_class_names
[i
],
1405 reg_class_names
[class_translate
[i
]]);
1408 /* Output all possible allocno and translation classes and the
1409 translation maps into stderr. */
1411 ira_debug_allocno_classes (void)
1413 print_unform_and_important_classes (stderr
);
1414 print_translated_classes (stderr
, false);
1415 print_translated_classes (stderr
, true);
1418 /* Set up different arrays concerning class subsets, allocno and
1419 important classes. */
1421 find_reg_classes (void)
1423 setup_allocno_and_important_classes ();
1424 setup_class_translate ();
1425 reorder_important_classes ();
1426 setup_reg_class_relations ();
1431 /* Set up the array above. */
1433 setup_hard_regno_aclass (void)
1437 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1440 ira_hard_regno_allocno_class
[i
]
1441 = (TEST_HARD_REG_BIT (no_unit_alloc_regs
, i
)
1443 : ira_allocno_class_translate
[REGNO_REG_CLASS (i
)]);
1447 ira_hard_regno_allocno_class
[i
] = NO_REGS
;
1448 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1450 cl
= ira_allocno_classes
[j
];
1451 if (ira_class_hard_reg_index
[cl
][i
] >= 0)
1453 ira_hard_regno_allocno_class
[i
] = cl
;
1463 /* Form IRA_REG_CLASS_MAX_NREGS and IRA_REG_CLASS_MIN_NREGS maps. */
1465 setup_reg_class_nregs (void)
1469 for (m
= 0; m
< MAX_MACHINE_MODE
; m
++)
1471 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1472 ira_reg_class_max_nregs
[cl
][m
]
1473 = ira_reg_class_min_nregs
[cl
][m
]
1474 = targetm
.class_max_nregs ((reg_class_t
) cl
, (enum machine_mode
) m
);
1475 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1477 (cl2
= alloc_reg_class_subclasses
[cl
][i
]) != LIM_REG_CLASSES
;
1479 if (ira_reg_class_min_nregs
[cl2
][m
]
1480 < ira_reg_class_min_nregs
[cl
][m
])
1481 ira_reg_class_min_nregs
[cl
][m
] = ira_reg_class_min_nregs
[cl2
][m
];
1487 /* Set up IRA_PROHIBITED_CLASS_MODE_REGS and IRA_CLASS_SINGLETON.
1488 This function is called once IRA_CLASS_HARD_REGS has been initialized. */
1490 setup_prohibited_class_mode_regs (void)
1492 int j
, k
, hard_regno
, cl
, last_hard_regno
, count
;
1494 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
1496 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
1497 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1498 for (j
= 0; j
< NUM_MACHINE_MODES
; j
++)
1501 last_hard_regno
= -1;
1502 CLEAR_HARD_REG_SET (ira_prohibited_class_mode_regs
[cl
][j
]);
1503 for (k
= ira_class_hard_regs_num
[cl
] - 1; k
>= 0; k
--)
1505 hard_regno
= ira_class_hard_regs
[cl
][k
];
1506 if (! HARD_REGNO_MODE_OK (hard_regno
, (enum machine_mode
) j
))
1507 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1509 else if (in_hard_reg_set_p (temp_hard_regset
,
1510 (enum machine_mode
) j
, hard_regno
))
1512 last_hard_regno
= hard_regno
;
1516 ira_class_singleton
[cl
][j
] = (count
== 1 ? last_hard_regno
: -1);
1521 /* Clarify IRA_PROHIBITED_CLASS_MODE_REGS by excluding hard registers
1522 spanning from one register pressure class to another one. It is
1523 called after defining the pressure classes. */
1525 clarify_prohibited_class_mode_regs (void)
1527 int j
, k
, hard_regno
, cl
, pclass
, nregs
;
1529 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
1530 for (j
= 0; j
< NUM_MACHINE_MODES
; j
++)
1532 CLEAR_HARD_REG_SET (ira_useful_class_mode_regs
[cl
][j
]);
1533 for (k
= ira_class_hard_regs_num
[cl
] - 1; k
>= 0; k
--)
1535 hard_regno
= ira_class_hard_regs
[cl
][k
];
1536 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
], hard_regno
))
1538 nregs
= hard_regno_nregs
[hard_regno
][j
];
1539 if (hard_regno
+ nregs
> FIRST_PSEUDO_REGISTER
)
1541 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1545 pclass
= ira_pressure_class_translate
[REGNO_REG_CLASS (hard_regno
)];
1546 for (nregs
-- ;nregs
>= 0; nregs
--)
1547 if (((enum reg_class
) pclass
1548 != ira_pressure_class_translate
[REGNO_REG_CLASS
1549 (hard_regno
+ nregs
)]))
1551 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1555 if (!TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1557 add_to_hard_reg_set (&ira_useful_class_mode_regs
[cl
][j
],
1558 (enum machine_mode
) j
, hard_regno
);
1563 /* Allocate and initialize IRA_REGISTER_MOVE_COST, IRA_MAY_MOVE_IN_COST
1564 and IRA_MAY_MOVE_OUT_COST for MODE. */
1566 ira_init_register_move_cost (enum machine_mode mode
)
1568 static unsigned short last_move_cost
[N_REG_CLASSES
][N_REG_CLASSES
];
1569 bool all_match
= true;
1570 unsigned int cl1
, cl2
;
1572 ira_assert (ira_register_move_cost
[mode
] == NULL
1573 && ira_may_move_in_cost
[mode
] == NULL
1574 && ira_may_move_out_cost
[mode
] == NULL
);
1575 ira_assert (have_regs_of_mode
[mode
]);
1576 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1577 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1580 if (!contains_reg_of_mode
[cl1
][mode
]
1581 || !contains_reg_of_mode
[cl2
][mode
])
1583 if ((ira_reg_class_max_nregs
[cl1
][mode
]
1584 > ira_class_hard_regs_num
[cl1
])
1585 || (ira_reg_class_max_nregs
[cl2
][mode
]
1586 > ira_class_hard_regs_num
[cl2
]))
1589 cost
= (ira_memory_move_cost
[mode
][cl1
][0]
1590 + ira_memory_move_cost
[mode
][cl2
][1]) * 2;
1594 cost
= register_move_cost (mode
, (enum reg_class
) cl1
,
1595 (enum reg_class
) cl2
);
1596 ira_assert (cost
< 65535);
1598 all_match
&= (last_move_cost
[cl1
][cl2
] == cost
);
1599 last_move_cost
[cl1
][cl2
] = cost
;
1601 if (all_match
&& last_mode_for_init_move_cost
!= -1)
1603 ira_register_move_cost
[mode
]
1604 = ira_register_move_cost
[last_mode_for_init_move_cost
];
1605 ira_may_move_in_cost
[mode
]
1606 = ira_may_move_in_cost
[last_mode_for_init_move_cost
];
1607 ira_may_move_out_cost
[mode
]
1608 = ira_may_move_out_cost
[last_mode_for_init_move_cost
];
1611 last_mode_for_init_move_cost
= mode
;
1612 ira_register_move_cost
[mode
] = XNEWVEC (move_table
, N_REG_CLASSES
);
1613 ira_may_move_in_cost
[mode
] = XNEWVEC (move_table
, N_REG_CLASSES
);
1614 ira_may_move_out_cost
[mode
] = XNEWVEC (move_table
, N_REG_CLASSES
);
1615 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1616 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1619 enum reg_class
*p1
, *p2
;
1621 if (last_move_cost
[cl1
][cl2
] == 65535)
1623 ira_register_move_cost
[mode
][cl1
][cl2
] = 65535;
1624 ira_may_move_in_cost
[mode
][cl1
][cl2
] = 65535;
1625 ira_may_move_out_cost
[mode
][cl1
][cl2
] = 65535;
1629 cost
= last_move_cost
[cl1
][cl2
];
1631 for (p2
= ®_class_subclasses
[cl2
][0];
1632 *p2
!= LIM_REG_CLASSES
; p2
++)
1633 if (ira_class_hard_regs_num
[*p2
] > 0
1634 && (ira_reg_class_max_nregs
[*p2
][mode
]
1635 <= ira_class_hard_regs_num
[*p2
]))
1636 cost
= MAX (cost
, ira_register_move_cost
[mode
][cl1
][*p2
]);
1638 for (p1
= ®_class_subclasses
[cl1
][0];
1639 *p1
!= LIM_REG_CLASSES
; p1
++)
1640 if (ira_class_hard_regs_num
[*p1
] > 0
1641 && (ira_reg_class_max_nregs
[*p1
][mode
]
1642 <= ira_class_hard_regs_num
[*p1
]))
1643 cost
= MAX (cost
, ira_register_move_cost
[mode
][*p1
][cl2
]);
1645 ira_assert (cost
<= 65535);
1646 ira_register_move_cost
[mode
][cl1
][cl2
] = cost
;
1648 if (ira_class_subset_p
[cl1
][cl2
])
1649 ira_may_move_in_cost
[mode
][cl1
][cl2
] = 0;
1651 ira_may_move_in_cost
[mode
][cl1
][cl2
] = cost
;
1653 if (ira_class_subset_p
[cl2
][cl1
])
1654 ira_may_move_out_cost
[mode
][cl1
][cl2
] = 0;
1656 ira_may_move_out_cost
[mode
][cl1
][cl2
] = cost
;
1663 /* This is called once during compiler work. It sets up
1664 different arrays whose values don't depend on the compiled
1667 ira_init_once (void)
1669 ira_init_costs_once ();
1673 /* Free ira_max_register_move_cost, ira_may_move_in_cost and
1674 ira_may_move_out_cost for each mode. */
1676 free_register_move_costs (void)
1680 /* Reset move_cost and friends, making sure we only free shared
1681 table entries once. */
1682 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
1683 if (ira_register_move_cost
[mode
])
1686 i
< mode
&& (ira_register_move_cost
[i
]
1687 != ira_register_move_cost
[mode
]);
1692 free (ira_register_move_cost
[mode
]);
1693 free (ira_may_move_in_cost
[mode
]);
1694 free (ira_may_move_out_cost
[mode
]);
1697 memset (ira_register_move_cost
, 0, sizeof ira_register_move_cost
);
1698 memset (ira_may_move_in_cost
, 0, sizeof ira_may_move_in_cost
);
1699 memset (ira_may_move_out_cost
, 0, sizeof ira_may_move_out_cost
);
1700 last_mode_for_init_move_cost
= -1;
1703 /* This is called every time when register related information is
1708 free_register_move_costs ();
1709 setup_reg_mode_hard_regset ();
1710 setup_alloc_regs (flag_omit_frame_pointer
!= 0);
1711 setup_class_subset_and_memory_move_costs ();
1712 setup_reg_class_nregs ();
1713 setup_prohibited_class_mode_regs ();
1714 find_reg_classes ();
1715 clarify_prohibited_class_mode_regs ();
1716 setup_hard_regno_aclass ();
1720 /* Function called once at the end of compiler work. */
1722 ira_finish_once (void)
1724 ira_finish_costs_once ();
1725 free_register_move_costs ();
1730 #define ira_prohibited_mode_move_regs_initialized_p \
1731 (this_target_ira_int->x_ira_prohibited_mode_move_regs_initialized_p)
1733 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS. */
1735 setup_prohibited_mode_move_regs (void)
1738 rtx test_reg1
, test_reg2
, move_pat
, move_insn
;
1740 if (ira_prohibited_mode_move_regs_initialized_p
)
1742 ira_prohibited_mode_move_regs_initialized_p
= true;
1743 test_reg1
= gen_rtx_REG (VOIDmode
, 0);
1744 test_reg2
= gen_rtx_REG (VOIDmode
, 0);
1745 move_pat
= gen_rtx_SET (VOIDmode
, test_reg1
, test_reg2
);
1746 move_insn
= gen_rtx_INSN (VOIDmode
, 0, 0, 0, move_pat
, 0, -1, 0);
1747 for (i
= 0; i
< NUM_MACHINE_MODES
; i
++)
1749 SET_HARD_REG_SET (ira_prohibited_mode_move_regs
[i
]);
1750 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1752 if (! HARD_REGNO_MODE_OK (j
, (enum machine_mode
) i
))
1754 SET_REGNO_RAW (test_reg1
, j
);
1755 PUT_MODE (test_reg1
, (enum machine_mode
) i
);
1756 SET_REGNO_RAW (test_reg2
, j
);
1757 PUT_MODE (test_reg2
, (enum machine_mode
) i
);
1758 INSN_CODE (move_insn
) = -1;
1759 recog_memoized (move_insn
);
1760 if (INSN_CODE (move_insn
) < 0)
1762 extract_insn (move_insn
);
1763 if (! constrain_operands (1))
1765 CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs
[i
], j
);
1772 /* Setup possible alternatives in ALTS for INSN. */
1774 ira_setup_alts (rtx insn
, HARD_REG_SET
&alts
)
1776 /* MAP nalt * nop -> start of constraints for given operand and
1778 static vec
<const char *> insn_constraints
;
1783 int commutative
= -1;
1785 extract_insn (insn
);
1786 CLEAR_HARD_REG_SET (alts
);
1787 insn_constraints
.release ();
1788 insn_constraints
.safe_grow_cleared (recog_data
.n_operands
1789 * recog_data
.n_alternatives
+ 1);
1790 /* Check that the hard reg set is enough for holding all
1791 alternatives. It is hard to imagine the situation when the
1792 assertion is wrong. */
1793 ira_assert (recog_data
.n_alternatives
1794 <= (int) MAX (sizeof (HARD_REG_ELT_TYPE
) * CHAR_BIT
,
1795 FIRST_PSEUDO_REGISTER
));
1796 for (curr_swapped
= false;; curr_swapped
= true)
1798 /* Calculate some data common for all alternatives to speed up the
1800 for (nop
= 0; nop
< recog_data
.n_operands
; nop
++)
1802 for (nalt
= 0, p
= recog_data
.constraints
[nop
];
1803 nalt
< recog_data
.n_alternatives
;
1806 insn_constraints
[nop
* recog_data
.n_alternatives
+ nalt
] = p
;
1807 while (*p
&& *p
!= ',')
1813 for (nalt
= 0; nalt
< recog_data
.n_alternatives
; nalt
++)
1815 if (!TEST_BIT (recog_data
.enabled_alternatives
, nalt
)
1816 || TEST_HARD_REG_BIT (alts
, nalt
))
1819 for (nop
= 0; nop
< recog_data
.n_operands
; nop
++)
1823 op
= recog_data
.operand
[nop
];
1824 p
= insn_constraints
[nop
* recog_data
.n_alternatives
+ nalt
];
1825 if (*p
== 0 || *p
== ',')
1829 switch (c
= *p
, len
= CONSTRAINT_LEN (c
, p
), c
)
1838 case '?': case '!': case '*': case '=': case '+':
1842 /* We only support one commutative marker, the
1843 first one. We already set commutative
1845 if (commutative
< 0)
1852 case '0': case '1': case '2': case '3': case '4':
1853 case '5': case '6': case '7': case '8': case '9':
1860 case TARGET_MEM_CONSTRAINT
:
1866 && (GET_CODE (XEXP (op
, 0)) == PRE_DEC
1867 || GET_CODE (XEXP (op
, 0)) == POST_DEC
))
1873 && (GET_CODE (XEXP (op
, 0)) == PRE_INC
1874 || GET_CODE (XEXP (op
, 0)) == POST_INC
))
1880 if (CONST_DOUBLE_AS_FLOAT_P (op
)
1881 || (GET_CODE (op
) == CONST_VECTOR
1882 && GET_MODE_CLASS (GET_MODE (op
)) == MODE_VECTOR_FLOAT
))
1888 if (CONST_DOUBLE_AS_FLOAT_P (op
)
1889 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op
, c
, p
))
1894 if (CONST_SCALAR_INT_P (op
))
1897 if (CONSTANT_P (op
))
1902 if (CONST_SCALAR_INT_P (op
))
1914 if (CONST_INT_P (op
)
1915 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op
), c
, p
))
1920 if (MEM_P (op
) && ! offsettable_memref_p (op
))
1932 cl
= (c
== 'r' ? GENERAL_REGS
: REG_CLASS_FROM_CONSTRAINT (c
, p
));
1935 #ifdef EXTRA_CONSTRAINT_STR
1936 else if (EXTRA_CONSTRAINT_STR (op
, c
, p
))
1938 else if (EXTRA_MEMORY_CONSTRAINT (c
, p
))
1940 else if (EXTRA_ADDRESS_CONSTRAINT (c
, p
))
1946 while (p
+= len
, c
);
1951 if (nop
>= recog_data
.n_operands
)
1952 SET_HARD_REG_BIT (alts
, nalt
);
1954 if (commutative
< 0)
1958 op
= recog_data
.operand
[commutative
];
1959 recog_data
.operand
[commutative
] = recog_data
.operand
[commutative
+ 1];
1960 recog_data
.operand
[commutative
+ 1] = op
;
1965 /* Return the number of the output non-early clobber operand which
1966 should be the same in any case as operand with number OP_NUM (or
1967 negative value if there is no such operand). The function takes
1968 only really possible alternatives into consideration. */
1970 ira_get_dup_out_num (int op_num
, HARD_REG_SET
&alts
)
1972 int curr_alt
, c
, original
, dup
;
1973 bool ignore_p
, use_commut_op_p
;
1975 #ifdef EXTRA_CONSTRAINT_STR
1979 if (op_num
< 0 || recog_data
.n_alternatives
== 0)
1981 /* We should find duplications only for input operands. */
1982 if (recog_data
.operand_type
[op_num
] != OP_IN
)
1984 str
= recog_data
.constraints
[op_num
];
1985 use_commut_op_p
= false;
1988 #ifdef EXTRA_CONSTRAINT_STR
1989 op
= recog_data
.operand
[op_num
];
1992 for (curr_alt
= 0, ignore_p
= !TEST_HARD_REG_BIT (alts
, curr_alt
),
2003 ignore_p
= !TEST_HARD_REG_BIT (alts
, curr_alt
);
2005 else if (! ignore_p
)
2013 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
2014 case 'h': case 'j': case 'k': case 'l':
2015 case 'q': case 't': case 'u':
2016 case 'v': case 'w': case 'x': case 'y': case 'z':
2017 case 'A': case 'B': case 'C': case 'D':
2018 case 'Q': case 'R': case 'S': case 'T': case 'U':
2019 case 'W': case 'Y': case 'Z':
2024 ? GENERAL_REGS
: REG_CLASS_FROM_CONSTRAINT (c
, str
));
2027 if (! targetm
.class_likely_spilled_p (cl
))
2030 #ifdef EXTRA_CONSTRAINT_STR
2031 else if (EXTRA_CONSTRAINT_STR (op
, c
, str
))
2037 case '0': case '1': case '2': case '3': case '4':
2038 case '5': case '6': case '7': case '8': case '9':
2039 if (original
!= -1 && original
!= c
)
2044 str
+= CONSTRAINT_LEN (c
, str
);
2049 for (ignore_p
= false, str
= recog_data
.constraints
[original
- '0'];
2057 else if (*str
== '#')
2059 else if (! ignore_p
)
2062 dup
= original
- '0';
2063 /* It is better ignore an alternative with early clobber. */
2064 else if (*str
== '&')
2070 if (use_commut_op_p
)
2072 use_commut_op_p
= true;
2073 if (recog_data
.constraints
[op_num
][0] == '%')
2074 str
= recog_data
.constraints
[op_num
+ 1];
2075 else if (op_num
> 0 && recog_data
.constraints
[op_num
- 1][0] == '%')
2076 str
= recog_data
.constraints
[op_num
- 1];
2085 /* Search forward to see if the source register of a copy insn dies
2086 before either it or the destination register is modified, but don't
2087 scan past the end of the basic block. If so, we can replace the
2088 source with the destination and let the source die in the copy
2091 This will reduce the number of registers live in that range and may
2092 enable the destination and the source coalescing, thus often saving
2093 one register in addition to a register-register copy. */
2096 decrease_live_ranges_number (void)
2099 rtx insn
, set
, src
, dest
, dest_death
, p
, q
, note
;
2102 if (! flag_expensive_optimizations
)
2106 fprintf (ira_dump_file
, "Starting decreasing number of live ranges...\n");
2108 FOR_EACH_BB_FN (bb
, cfun
)
2109 FOR_BB_INSNS (bb
, insn
)
2111 set
= single_set (insn
);
2114 src
= SET_SRC (set
);
2115 dest
= SET_DEST (set
);
2116 if (! REG_P (src
) || ! REG_P (dest
)
2117 || find_reg_note (insn
, REG_DEAD
, src
))
2119 sregno
= REGNO (src
);
2120 dregno
= REGNO (dest
);
2122 /* We don't want to mess with hard regs if register classes
2124 if (sregno
== dregno
2125 || (targetm
.small_register_classes_for_mode_p (GET_MODE (src
))
2126 && (sregno
< FIRST_PSEUDO_REGISTER
2127 || dregno
< FIRST_PSEUDO_REGISTER
))
2128 /* We don't see all updates to SP if they are in an
2129 auto-inc memory reference, so we must disallow this
2130 optimization on them. */
2131 || sregno
== STACK_POINTER_REGNUM
2132 || dregno
== STACK_POINTER_REGNUM
)
2135 dest_death
= NULL_RTX
;
2137 for (p
= NEXT_INSN (insn
); p
; p
= NEXT_INSN (p
))
2141 if (BLOCK_FOR_INSN (p
) != bb
)
2144 if (reg_set_p (src
, p
) || reg_set_p (dest
, p
)
2145 /* If SRC is an asm-declared register, it must not be
2146 replaced in any asm. Unfortunately, the REG_EXPR
2147 tree for the asm variable may be absent in the SRC
2148 rtx, so we can't check the actual register
2149 declaration easily (the asm operand will have it,
2150 though). To avoid complicating the test for a rare
2151 case, we just don't perform register replacement
2152 for a hard reg mentioned in an asm. */
2153 || (sregno
< FIRST_PSEUDO_REGISTER
2154 && asm_noperands (PATTERN (p
)) >= 0
2155 && reg_overlap_mentioned_p (src
, PATTERN (p
)))
2156 /* Don't change hard registers used by a call. */
2157 || (CALL_P (p
) && sregno
< FIRST_PSEUDO_REGISTER
2158 && find_reg_fusage (p
, USE
, src
))
2159 /* Don't change a USE of a register. */
2160 || (GET_CODE (PATTERN (p
)) == USE
2161 && reg_overlap_mentioned_p (src
, XEXP (PATTERN (p
), 0))))
2164 /* See if all of SRC dies in P. This test is slightly
2165 more conservative than it needs to be. */
2166 if ((note
= find_regno_note (p
, REG_DEAD
, sregno
))
2167 && GET_MODE (XEXP (note
, 0)) == GET_MODE (src
))
2171 /* We can do the optimization. Scan forward from INSN
2172 again, replacing regs as we go. Set FAILED if a
2173 replacement can't be done. In that case, we can't
2174 move the death note for SRC. This should be
2177 /* Set to stop at next insn. */
2178 for (q
= next_real_insn (insn
);
2179 q
!= next_real_insn (p
);
2180 q
= next_real_insn (q
))
2182 if (reg_overlap_mentioned_p (src
, PATTERN (q
)))
2184 /* If SRC is a hard register, we might miss
2185 some overlapping registers with
2186 validate_replace_rtx, so we would have to
2187 undo it. We can't if DEST is present in
2188 the insn, so fail in that combination of
2190 if (sregno
< FIRST_PSEUDO_REGISTER
2191 && reg_mentioned_p (dest
, PATTERN (q
)))
2194 /* Attempt to replace all uses. */
2195 else if (!validate_replace_rtx (src
, dest
, q
))
2198 /* If this succeeded, but some part of the
2199 register is still present, undo the
2201 else if (sregno
< FIRST_PSEUDO_REGISTER
2202 && reg_overlap_mentioned_p (src
, PATTERN (q
)))
2204 validate_replace_rtx (dest
, src
, q
);
2209 /* If DEST dies here, remove the death note and
2210 save it for later. Make sure ALL of DEST dies
2211 here; again, this is overly conservative. */
2213 && (dest_death
= find_regno_note (q
, REG_DEAD
, dregno
)))
2215 if (GET_MODE (XEXP (dest_death
, 0)) == GET_MODE (dest
))
2216 remove_note (q
, dest_death
);
2227 /* Move death note of SRC from P to INSN. */
2228 remove_note (p
, note
);
2229 XEXP (note
, 1) = REG_NOTES (insn
);
2230 REG_NOTES (insn
) = note
;
2233 /* DEST is also dead if INSN has a REG_UNUSED note for
2237 = find_regno_note (insn
, REG_UNUSED
, dregno
)))
2239 PUT_REG_NOTE_KIND (dest_death
, REG_DEAD
);
2240 remove_note (insn
, dest_death
);
2243 /* Put death note of DEST on P if we saw it die. */
2246 XEXP (dest_death
, 1) = REG_NOTES (p
);
2247 REG_NOTES (p
) = dest_death
;
2252 /* If SRC is a hard register which is set or killed in
2253 some other way, we can't do this optimization. */
2254 else if (sregno
< FIRST_PSEUDO_REGISTER
&& dead_or_set_p (p
, src
))
2262 /* Return nonzero if REGNO is a particularly bad choice for reloading X. */
2264 ira_bad_reload_regno_1 (int regno
, rtx x
)
2268 enum reg_class pref
;
2270 /* We only deal with pseudo regs. */
2271 if (! x
|| GET_CODE (x
) != REG
)
2274 x_regno
= REGNO (x
);
2275 if (x_regno
< FIRST_PSEUDO_REGISTER
)
2278 /* If the pseudo prefers REGNO explicitly, then do not consider
2279 REGNO a bad spill choice. */
2280 pref
= reg_preferred_class (x_regno
);
2281 if (reg_class_size
[pref
] == 1)
2282 return !TEST_HARD_REG_BIT (reg_class_contents
[pref
], regno
);
2284 /* If the pseudo conflicts with REGNO, then we consider REGNO a
2285 poor choice for a reload regno. */
2286 a
= ira_regno_allocno_map
[x_regno
];
2287 n
= ALLOCNO_NUM_OBJECTS (a
);
2288 for (i
= 0; i
< n
; i
++)
2290 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2291 if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), regno
))
2297 /* Return nonzero if REGNO is a particularly bad choice for reloading
2300 ira_bad_reload_regno (int regno
, rtx in
, rtx out
)
2302 return (ira_bad_reload_regno_1 (regno
, in
)
2303 || ira_bad_reload_regno_1 (regno
, out
));
2306 /* Return TRUE if *LOC contains an asm. */
2308 insn_contains_asm_1 (rtx
*loc
, void *data ATTRIBUTE_UNUSED
)
2312 if (GET_CODE (*loc
) == ASM_OPERANDS
)
2318 /* Return TRUE if INSN contains an ASM. */
2320 insn_contains_asm (rtx insn
)
2322 return for_each_rtx (&insn
, insn_contains_asm_1
, NULL
);
2325 /* Add register clobbers from asm statements. */
2327 compute_regs_asm_clobbered (void)
2331 FOR_EACH_BB_FN (bb
, cfun
)
2334 FOR_BB_INSNS_REVERSE (bb
, insn
)
2338 if (insn_contains_asm (insn
))
2339 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
2341 df_ref def
= *def_rec
;
2342 unsigned int dregno
= DF_REF_REGNO (def
);
2343 if (HARD_REGISTER_NUM_P (dregno
))
2344 add_to_hard_reg_set (&crtl
->asm_clobbers
,
2345 GET_MODE (DF_REF_REAL_REG (def
)),
2353 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and
2356 ira_setup_eliminable_regset (void)
2358 #ifdef ELIMINABLE_REGS
2360 static const struct {const int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
2362 /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
2363 sp for alloca. So we can't eliminate the frame pointer in that
2364 case. At some point, we should improve this by emitting the
2365 sp-adjusting insns for this case. */
2366 frame_pointer_needed
2367 = (! flag_omit_frame_pointer
2368 || (cfun
->calls_alloca
&& EXIT_IGNORE_STACK
)
2369 /* We need the frame pointer to catch stack overflow exceptions
2370 if the stack pointer is moving. */
2371 || (flag_stack_check
&& STACK_CHECK_MOVING_SP
)
2372 || crtl
->accesses_prior_frames
2373 || (SUPPORTS_STACK_ALIGNMENT
&& crtl
->stack_realign_needed
)
2374 /* We need a frame pointer for all Cilk Plus functions that use
2376 || (flag_cilkplus
&& cfun
->is_cilk_function
)
2377 || targetm
.frame_pointer_required ());
2379 /* The chance that FRAME_POINTER_NEEDED is changed from inspecting
2380 RTL is very small. So if we use frame pointer for RA and RTL
2381 actually prevents this, we will spill pseudos assigned to the
2382 frame pointer in LRA. */
2384 if (frame_pointer_needed
)
2385 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM
, true);
2387 COPY_HARD_REG_SET (ira_no_alloc_regs
, no_unit_alloc_regs
);
2388 CLEAR_HARD_REG_SET (eliminable_regset
);
2390 compute_regs_asm_clobbered ();
2392 /* Build the regset of all eliminable registers and show we can't
2393 use those that we already know won't be eliminated. */
2394 #ifdef ELIMINABLE_REGS
2395 for (i
= 0; i
< (int) ARRAY_SIZE (eliminables
); i
++)
2398 = (! targetm
.can_eliminate (eliminables
[i
].from
, eliminables
[i
].to
)
2399 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& frame_pointer_needed
));
2401 if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
, eliminables
[i
].from
))
2403 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
2406 SET_HARD_REG_BIT (ira_no_alloc_regs
, eliminables
[i
].from
);
2408 else if (cannot_elim
)
2409 error ("%s cannot be used in asm here",
2410 reg_names
[eliminables
[i
].from
]);
2412 df_set_regs_ever_live (eliminables
[i
].from
, true);
2414 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
2415 if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
, HARD_FRAME_POINTER_REGNUM
))
2417 SET_HARD_REG_BIT (eliminable_regset
, HARD_FRAME_POINTER_REGNUM
);
2418 if (frame_pointer_needed
)
2419 SET_HARD_REG_BIT (ira_no_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
2421 else if (frame_pointer_needed
)
2422 error ("%s cannot be used in asm here",
2423 reg_names
[HARD_FRAME_POINTER_REGNUM
]);
2425 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM
, true);
2429 if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
, HARD_FRAME_POINTER_REGNUM
))
2431 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
2432 if (frame_pointer_needed
)
2433 SET_HARD_REG_BIT (ira_no_alloc_regs
, FRAME_POINTER_REGNUM
);
2435 else if (frame_pointer_needed
)
2436 error ("%s cannot be used in asm here", reg_names
[FRAME_POINTER_REGNUM
]);
2438 df_set_regs_ever_live (FRAME_POINTER_REGNUM
, true);
2444 /* Vector of substitutions of register numbers,
2445 used to map pseudo regs into hardware regs.
2446 This is set up as a result of register allocation.
2447 Element N is the hard reg assigned to pseudo reg N,
2448 or is -1 if no hard reg was assigned.
2449 If N is a hard reg number, element N is N. */
2450 short *reg_renumber
;
2452 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
2453 the allocation found by IRA. */
2455 setup_reg_renumber (void)
2457 int regno
, hard_regno
;
2459 ira_allocno_iterator ai
;
2461 caller_save_needed
= 0;
2462 FOR_EACH_ALLOCNO (a
, ai
)
2464 if (ira_use_lra_p
&& ALLOCNO_CAP_MEMBER (a
) != NULL
)
2466 /* There are no caps at this point. */
2467 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
2468 if (! ALLOCNO_ASSIGNED_P (a
))
2469 /* It can happen if A is not referenced but partially anticipated
2470 somewhere in a region. */
2471 ALLOCNO_ASSIGNED_P (a
) = true;
2472 ira_free_allocno_updated_costs (a
);
2473 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2474 regno
= ALLOCNO_REGNO (a
);
2475 reg_renumber
[regno
] = (hard_regno
< 0 ? -1 : hard_regno
);
2476 if (hard_regno
>= 0)
2479 enum reg_class pclass
;
2482 pclass
= ira_pressure_class_translate
[REGNO_REG_CLASS (hard_regno
)];
2483 nwords
= ALLOCNO_NUM_OBJECTS (a
);
2484 for (i
= 0; i
< nwords
; i
++)
2486 obj
= ALLOCNO_OBJECT (a
, i
);
2487 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
2488 reg_class_contents
[pclass
]);
2490 if (ALLOCNO_CALLS_CROSSED_NUM (a
) != 0
2491 && ira_hard_reg_set_intersection_p (hard_regno
, ALLOCNO_MODE (a
),
2494 ira_assert (!optimize
|| flag_caller_saves
2495 || (ALLOCNO_CALLS_CROSSED_NUM (a
)
2496 == ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
))
2497 || regno
>= ira_reg_equiv_len
2498 || ira_equiv_no_lvalue_p (regno
));
2499 caller_save_needed
= 1;
2505 /* Set up allocno assignment flags for further allocation
2508 setup_allocno_assignment_flags (void)
2512 ira_allocno_iterator ai
;
2514 FOR_EACH_ALLOCNO (a
, ai
)
2516 if (! ALLOCNO_ASSIGNED_P (a
))
2517 /* It can happen if A is not referenced but partially anticipated
2518 somewhere in a region. */
2519 ira_free_allocno_updated_costs (a
);
2520 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2521 /* Don't assign hard registers to allocnos which are destination
2522 of removed store at the end of loop. It has no sense to keep
2523 the same value in different hard registers. It is also
2524 impossible to assign hard registers correctly to such
2525 allocnos because the cost info and info about intersected
2526 calls are incorrect for them. */
2527 ALLOCNO_ASSIGNED_P (a
) = (hard_regno
>= 0
2528 || ALLOCNO_EMIT_DATA (a
)->mem_optimized_dest_p
2529 || (ALLOCNO_MEMORY_COST (a
)
2530 - ALLOCNO_CLASS_COST (a
)) < 0);
2533 || ira_hard_reg_in_set_p (hard_regno
, ALLOCNO_MODE (a
),
2534 reg_class_contents
[ALLOCNO_CLASS (a
)]));
2538 /* Evaluate overall allocation cost and the costs for using hard
2539 registers and memory for allocnos. */
2541 calculate_allocation_cost (void)
2543 int hard_regno
, cost
;
2545 ira_allocno_iterator ai
;
2547 ira_overall_cost
= ira_reg_cost
= ira_mem_cost
= 0;
2548 FOR_EACH_ALLOCNO (a
, ai
)
2550 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2551 ira_assert (hard_regno
< 0
2552 || (ira_hard_reg_in_set_p
2553 (hard_regno
, ALLOCNO_MODE (a
),
2554 reg_class_contents
[ALLOCNO_CLASS (a
)])));
2557 cost
= ALLOCNO_MEMORY_COST (a
);
2558 ira_mem_cost
+= cost
;
2560 else if (ALLOCNO_HARD_REG_COSTS (a
) != NULL
)
2562 cost
= (ALLOCNO_HARD_REG_COSTS (a
)
2563 [ira_class_hard_reg_index
2564 [ALLOCNO_CLASS (a
)][hard_regno
]]);
2565 ira_reg_cost
+= cost
;
2569 cost
= ALLOCNO_CLASS_COST (a
);
2570 ira_reg_cost
+= cost
;
2572 ira_overall_cost
+= cost
;
2575 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
2577 fprintf (ira_dump_file
,
2578 "+++Costs: overall %d, reg %d, mem %d, ld %d, st %d, move %d\n",
2579 ira_overall_cost
, ira_reg_cost
, ira_mem_cost
,
2580 ira_load_cost
, ira_store_cost
, ira_shuffle_cost
);
2581 fprintf (ira_dump_file
, "+++ move loops %d, new jumps %d\n",
2582 ira_move_loops_num
, ira_additional_jumps_num
);
2587 #ifdef ENABLE_IRA_CHECKING
2588 /* Check the correctness of the allocation. We do need this because
2589 of complicated code to transform more one region internal
2590 representation into one region representation. */
2592 check_allocation (void)
2595 int hard_regno
, nregs
, conflict_nregs
;
2596 ira_allocno_iterator ai
;
2598 FOR_EACH_ALLOCNO (a
, ai
)
2600 int n
= ALLOCNO_NUM_OBJECTS (a
);
2603 if (ALLOCNO_CAP_MEMBER (a
) != NULL
2604 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0)
2606 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (a
)];
2608 /* We allocated a single hard register. */
2611 /* We allocated multiple hard registers, and we will test
2612 conflicts in a granularity of single hard regs. */
2615 for (i
= 0; i
< n
; i
++)
2617 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2618 ira_object_t conflict_obj
;
2619 ira_object_conflict_iterator oci
;
2620 int this_regno
= hard_regno
;
2623 if (REG_WORDS_BIG_ENDIAN
)
2624 this_regno
+= n
- i
- 1;
2628 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2630 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2631 int conflict_hard_regno
= ALLOCNO_HARD_REGNO (conflict_a
);
2632 if (conflict_hard_regno
< 0)
2637 [conflict_hard_regno
][ALLOCNO_MODE (conflict_a
)]);
2639 if (ALLOCNO_NUM_OBJECTS (conflict_a
) > 1
2640 && conflict_nregs
== ALLOCNO_NUM_OBJECTS (conflict_a
))
2642 if (REG_WORDS_BIG_ENDIAN
)
2643 conflict_hard_regno
+= (ALLOCNO_NUM_OBJECTS (conflict_a
)
2644 - OBJECT_SUBWORD (conflict_obj
) - 1);
2646 conflict_hard_regno
+= OBJECT_SUBWORD (conflict_obj
);
2650 if ((conflict_hard_regno
<= this_regno
2651 && this_regno
< conflict_hard_regno
+ conflict_nregs
)
2652 || (this_regno
<= conflict_hard_regno
2653 && conflict_hard_regno
< this_regno
+ nregs
))
2655 fprintf (stderr
, "bad allocation for %d and %d\n",
2656 ALLOCNO_REGNO (a
), ALLOCNO_REGNO (conflict_a
));
2665 /* Allocate REG_EQUIV_INIT. Set up it from IRA_REG_EQUIV which should
2666 be already calculated. */
2668 setup_reg_equiv_init (void)
2671 int max_regno
= max_reg_num ();
2673 for (i
= 0; i
< max_regno
; i
++)
2674 reg_equiv_init (i
) = ira_reg_equiv
[i
].init_insns
;
2677 /* Update equiv regno from movement of FROM_REGNO to TO_REGNO. INSNS
2678 are insns which were generated for such movement. It is assumed
2679 that FROM_REGNO and TO_REGNO always have the same value at the
2680 point of any move containing such registers. This function is used
2681 to update equiv info for register shuffles on the region borders
2682 and for caller save/restore insns. */
2684 ira_update_equiv_info_by_shuffle_insn (int to_regno
, int from_regno
, rtx insns
)
2688 if (! ira_reg_equiv
[from_regno
].defined_p
2689 && (! ira_reg_equiv
[to_regno
].defined_p
2690 || ((x
= ira_reg_equiv
[to_regno
].memory
) != NULL_RTX
2691 && ! MEM_READONLY_P (x
))))
2694 if (NEXT_INSN (insn
) != NULL_RTX
)
2696 if (! ira_reg_equiv
[to_regno
].defined_p
)
2698 ira_assert (ira_reg_equiv
[to_regno
].init_insns
== NULL_RTX
);
2701 ira_reg_equiv
[to_regno
].defined_p
= false;
2702 ira_reg_equiv
[to_regno
].memory
2703 = ira_reg_equiv
[to_regno
].constant
2704 = ira_reg_equiv
[to_regno
].invariant
2705 = ira_reg_equiv
[to_regno
].init_insns
= NULL_RTX
;
2706 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2707 fprintf (ira_dump_file
,
2708 " Invalidating equiv info for reg %d\n", to_regno
);
2711 /* It is possible that FROM_REGNO still has no equivalence because
2712 in shuffles to_regno<-from_regno and from_regno<-to_regno the 2nd
2713 insn was not processed yet. */
2714 if (ira_reg_equiv
[from_regno
].defined_p
)
2716 ira_reg_equiv
[to_regno
].defined_p
= true;
2717 if ((x
= ira_reg_equiv
[from_regno
].memory
) != NULL_RTX
)
2719 ira_assert (ira_reg_equiv
[from_regno
].invariant
== NULL_RTX
2720 && ira_reg_equiv
[from_regno
].constant
== NULL_RTX
);
2721 ira_assert (ira_reg_equiv
[to_regno
].memory
== NULL_RTX
2722 || rtx_equal_p (ira_reg_equiv
[to_regno
].memory
, x
));
2723 ira_reg_equiv
[to_regno
].memory
= x
;
2724 if (! MEM_READONLY_P (x
))
2725 /* We don't add the insn to insn init list because memory
2726 equivalence is just to say what memory is better to use
2727 when the pseudo is spilled. */
2730 else if ((x
= ira_reg_equiv
[from_regno
].constant
) != NULL_RTX
)
2732 ira_assert (ira_reg_equiv
[from_regno
].invariant
== NULL_RTX
);
2733 ira_assert (ira_reg_equiv
[to_regno
].constant
== NULL_RTX
2734 || rtx_equal_p (ira_reg_equiv
[to_regno
].constant
, x
));
2735 ira_reg_equiv
[to_regno
].constant
= x
;
2739 x
= ira_reg_equiv
[from_regno
].invariant
;
2740 ira_assert (x
!= NULL_RTX
);
2741 ira_assert (ira_reg_equiv
[to_regno
].invariant
== NULL_RTX
2742 || rtx_equal_p (ira_reg_equiv
[to_regno
].invariant
, x
));
2743 ira_reg_equiv
[to_regno
].invariant
= x
;
2745 if (find_reg_note (insn
, REG_EQUIV
, x
) == NULL_RTX
)
2747 note
= set_unique_reg_note (insn
, REG_EQUIV
, x
);
2748 gcc_assert (note
!= NULL_RTX
);
2749 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2751 fprintf (ira_dump_file
,
2752 " Adding equiv note to insn %u for reg %d ",
2753 INSN_UID (insn
), to_regno
);
2754 dump_value_slim (ira_dump_file
, x
, 1);
2755 fprintf (ira_dump_file
, "\n");
2759 ira_reg_equiv
[to_regno
].init_insns
2760 = gen_rtx_INSN_LIST (VOIDmode
, insn
,
2761 ira_reg_equiv
[to_regno
].init_insns
);
2762 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2763 fprintf (ira_dump_file
,
2764 " Adding equiv init move insn %u to reg %d\n",
2765 INSN_UID (insn
), to_regno
);
2768 /* Fix values of array REG_EQUIV_INIT after live range splitting done
2771 fix_reg_equiv_init (void)
2773 int max_regno
= max_reg_num ();
2774 int i
, new_regno
, max
;
2775 rtx x
, prev
, next
, insn
, set
;
2777 if (max_regno_before_ira
< max_regno
)
2779 max
= vec_safe_length (reg_equivs
);
2781 for (i
= FIRST_PSEUDO_REGISTER
; i
< max
; i
++)
2782 for (prev
= NULL_RTX
, x
= reg_equiv_init (i
);
2788 set
= single_set (insn
);
2789 ira_assert (set
!= NULL_RTX
2790 && (REG_P (SET_DEST (set
)) || REG_P (SET_SRC (set
))));
2791 if (REG_P (SET_DEST (set
))
2792 && ((int) REGNO (SET_DEST (set
)) == i
2793 || (int) ORIGINAL_REGNO (SET_DEST (set
)) == i
))
2794 new_regno
= REGNO (SET_DEST (set
));
2795 else if (REG_P (SET_SRC (set
))
2796 && ((int) REGNO (SET_SRC (set
)) == i
2797 || (int) ORIGINAL_REGNO (SET_SRC (set
)) == i
))
2798 new_regno
= REGNO (SET_SRC (set
));
2805 /* Remove the wrong list element. */
2806 if (prev
== NULL_RTX
)
2807 reg_equiv_init (i
) = next
;
2809 XEXP (prev
, 1) = next
;
2810 XEXP (x
, 1) = reg_equiv_init (new_regno
);
2811 reg_equiv_init (new_regno
) = x
;
2817 #ifdef ENABLE_IRA_CHECKING
2818 /* Print redundant memory-memory copies. */
2820 print_redundant_copies (void)
2824 ira_copy_t cp
, next_cp
;
2825 ira_allocno_iterator ai
;
2827 FOR_EACH_ALLOCNO (a
, ai
)
2829 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2832 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2833 if (hard_regno
>= 0)
2835 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2837 next_cp
= cp
->next_first_allocno_copy
;
2840 next_cp
= cp
->next_second_allocno_copy
;
2841 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
2842 && cp
->insn
!= NULL_RTX
2843 && ALLOCNO_HARD_REGNO (cp
->first
) == hard_regno
)
2844 fprintf (ira_dump_file
,
2845 " Redundant move from %d(freq %d):%d\n",
2846 INSN_UID (cp
->insn
), cp
->freq
, hard_regno
);
2852 /* Setup preferred and alternative classes for new pseudo-registers
2853 created by IRA starting with START. */
2855 setup_preferred_alternate_classes_for_new_pseudos (int start
)
2858 int max_regno
= max_reg_num ();
2860 for (i
= start
; i
< max_regno
; i
++)
2862 old_regno
= ORIGINAL_REGNO (regno_reg_rtx
[i
]);
2863 ira_assert (i
!= old_regno
);
2864 setup_reg_classes (i
, reg_preferred_class (old_regno
),
2865 reg_alternate_class (old_regno
),
2866 reg_allocno_class (old_regno
));
2867 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
2868 fprintf (ira_dump_file
,
2869 " New r%d: setting preferred %s, alternative %s\n",
2870 i
, reg_class_names
[reg_preferred_class (old_regno
)],
2871 reg_class_names
[reg_alternate_class (old_regno
)]);
2876 /* The number of entries allocated in teg_info. */
2877 static int allocated_reg_info_size
;
2879 /* Regional allocation can create new pseudo-registers. This function
2880 expands some arrays for pseudo-registers. */
2882 expand_reg_info (void)
2885 int size
= max_reg_num ();
2888 for (i
= allocated_reg_info_size
; i
< size
; i
++)
2889 setup_reg_classes (i
, GENERAL_REGS
, ALL_REGS
, GENERAL_REGS
);
2890 setup_preferred_alternate_classes_for_new_pseudos (allocated_reg_info_size
);
2891 allocated_reg_info_size
= size
;
2894 /* Return TRUE if there is too high register pressure in the function.
2895 It is used to decide when stack slot sharing is worth to do. */
2897 too_high_register_pressure_p (void)
2900 enum reg_class pclass
;
2902 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2904 pclass
= ira_pressure_classes
[i
];
2905 if (ira_loop_tree_root
->reg_pressure
[pclass
] > 10000)
2913 /* Indicate that hard register number FROM was eliminated and replaced with
2914 an offset from hard register number TO. The status of hard registers live
2915 at the start of a basic block is updated by replacing a use of FROM with
2919 mark_elimination (int from
, int to
)
2924 FOR_EACH_BB_FN (bb
, cfun
)
2927 if (bitmap_bit_p (r
, from
))
2929 bitmap_clear_bit (r
, from
);
2930 bitmap_set_bit (r
, to
);
2934 r
= DF_LIVE_IN (bb
);
2935 if (bitmap_bit_p (r
, from
))
2937 bitmap_clear_bit (r
, from
);
2938 bitmap_set_bit (r
, to
);
2945 /* The length of the following array. */
2946 int ira_reg_equiv_len
;
2948 /* Info about equiv. info for each register. */
2949 struct ira_reg_equiv_s
*ira_reg_equiv
;
2951 /* Expand ira_reg_equiv if necessary. */
2953 ira_expand_reg_equiv (void)
2955 int old
= ira_reg_equiv_len
;
2957 if (ira_reg_equiv_len
> max_reg_num ())
2959 ira_reg_equiv_len
= max_reg_num () * 3 / 2 + 1;
2961 = (struct ira_reg_equiv_s
*) xrealloc (ira_reg_equiv
,
2963 * sizeof (struct ira_reg_equiv_s
));
2964 gcc_assert (old
< ira_reg_equiv_len
);
2965 memset (ira_reg_equiv
+ old
, 0,
2966 sizeof (struct ira_reg_equiv_s
) * (ira_reg_equiv_len
- old
));
2970 init_reg_equiv (void)
2972 ira_reg_equiv_len
= 0;
2973 ira_reg_equiv
= NULL
;
2974 ira_expand_reg_equiv ();
2978 finish_reg_equiv (void)
2980 free (ira_reg_equiv
);
2987 /* Set when a REG_EQUIV note is found or created. Use to
2988 keep track of what memory accesses might be created later,
2992 /* The list of each instruction which initializes this register. */
2994 /* Loop depth is used to recognize equivalences which appear
2995 to be present within the same loop (or in an inner loop). */
2997 /* Nonzero if this had a preexisting REG_EQUIV note. */
2998 int is_arg_equivalence
;
2999 /* Set when an attempt should be made to replace a register
3000 with the associated src_p entry. */
3004 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
3005 structure for that register. */
3006 static struct equivalence
*reg_equiv
;
3008 /* Used for communication between the following two functions: contains
3009 a MEM that we wish to ensure remains unchanged. */
3010 static rtx equiv_mem
;
3012 /* Set nonzero if EQUIV_MEM is modified. */
3013 static int equiv_mem_modified
;
3015 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
3016 Called via note_stores. */
3018 validate_equiv_mem_from_store (rtx dest
, const_rtx set ATTRIBUTE_UNUSED
,
3019 void *data ATTRIBUTE_UNUSED
)
3022 && reg_overlap_mentioned_p (dest
, equiv_mem
))
3024 && anti_dependence (equiv_mem
, dest
)))
3025 equiv_mem_modified
= 1;
3028 /* Verify that no store between START and the death of REG invalidates
3029 MEMREF. MEMREF is invalidated by modifying a register used in MEMREF,
3030 by storing into an overlapping memory location, or with a non-const
3033 Return 1 if MEMREF remains valid. */
3035 validate_equiv_mem (rtx start
, rtx reg
, rtx memref
)
3041 equiv_mem_modified
= 0;
3043 /* If the memory reference has side effects or is volatile, it isn't a
3044 valid equivalence. */
3045 if (side_effects_p (memref
))
3048 for (insn
= start
; insn
&& ! equiv_mem_modified
; insn
= NEXT_INSN (insn
))
3050 if (! INSN_P (insn
))
3053 if (find_reg_note (insn
, REG_DEAD
, reg
))
3056 /* This used to ignore readonly memory and const/pure calls. The problem
3057 is the equivalent form may reference a pseudo which gets assigned a
3058 call clobbered hard reg. When we later replace REG with its
3059 equivalent form, the value in the call-clobbered reg has been
3060 changed and all hell breaks loose. */
3064 note_stores (PATTERN (insn
), validate_equiv_mem_from_store
, NULL
);
3066 /* If a register mentioned in MEMREF is modified via an
3067 auto-increment, we lose the equivalence. Do the same if one
3068 dies; although we could extend the life, it doesn't seem worth
3071 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
3072 if ((REG_NOTE_KIND (note
) == REG_INC
3073 || REG_NOTE_KIND (note
) == REG_DEAD
)
3074 && REG_P (XEXP (note
, 0))
3075 && reg_overlap_mentioned_p (XEXP (note
, 0), memref
))
3082 /* Returns zero if X is known to be invariant. */
3084 equiv_init_varies_p (rtx x
)
3086 RTX_CODE code
= GET_CODE (x
);
3093 return !MEM_READONLY_P (x
) || equiv_init_varies_p (XEXP (x
, 0));
3102 return reg_equiv
[REGNO (x
)].replace
== 0 && rtx_varies_p (x
, 0);
3105 if (MEM_VOLATILE_P (x
))
3114 fmt
= GET_RTX_FORMAT (code
);
3115 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3118 if (equiv_init_varies_p (XEXP (x
, i
)))
3121 else if (fmt
[i
] == 'E')
3124 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
3125 if (equiv_init_varies_p (XVECEXP (x
, i
, j
)))
3132 /* Returns nonzero if X (used to initialize register REGNO) is movable.
3133 X is only movable if the registers it uses have equivalent initializations
3134 which appear to be within the same loop (or in an inner loop) and movable
3135 or if they are not candidates for local_alloc and don't vary. */
3137 equiv_init_movable_p (rtx x
, int regno
)
3141 enum rtx_code code
= GET_CODE (x
);
3146 return equiv_init_movable_p (SET_SRC (x
), regno
);
3161 return ((reg_equiv
[REGNO (x
)].loop_depth
>= reg_equiv
[regno
].loop_depth
3162 && reg_equiv
[REGNO (x
)].replace
)
3163 || (REG_BASIC_BLOCK (REGNO (x
)) < NUM_FIXED_BLOCKS
3164 && ! rtx_varies_p (x
, 0)));
3166 case UNSPEC_VOLATILE
:
3170 if (MEM_VOLATILE_P (x
))
3179 fmt
= GET_RTX_FORMAT (code
);
3180 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3184 if (! equiv_init_movable_p (XEXP (x
, i
), regno
))
3188 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
3189 if (! equiv_init_movable_p (XVECEXP (x
, i
, j
), regno
))
3197 /* TRUE if X uses any registers for which reg_equiv[REGNO].replace is
3200 contains_replace_regs (rtx x
)
3204 enum rtx_code code
= GET_CODE (x
);
3218 return reg_equiv
[REGNO (x
)].replace
;
3224 fmt
= GET_RTX_FORMAT (code
);
3225 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3229 if (contains_replace_regs (XEXP (x
, i
)))
3233 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
3234 if (contains_replace_regs (XVECEXP (x
, i
, j
)))
3242 /* TRUE if X references a memory location that would be affected by a store
3245 memref_referenced_p (rtx memref
, rtx x
)
3249 enum rtx_code code
= GET_CODE (x
);
3264 return (reg_equiv
[REGNO (x
)].replacement
3265 && memref_referenced_p (memref
,
3266 reg_equiv
[REGNO (x
)].replacement
));
3269 if (true_dependence (memref
, VOIDmode
, x
))
3274 /* If we are setting a MEM, it doesn't count (its address does), but any
3275 other SET_DEST that has a MEM in it is referencing the MEM. */
3276 if (MEM_P (SET_DEST (x
)))
3278 if (memref_referenced_p (memref
, XEXP (SET_DEST (x
), 0)))
3281 else if (memref_referenced_p (memref
, SET_DEST (x
)))
3284 return memref_referenced_p (memref
, SET_SRC (x
));
3290 fmt
= GET_RTX_FORMAT (code
);
3291 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3295 if (memref_referenced_p (memref
, XEXP (x
, i
)))
3299 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
3300 if (memref_referenced_p (memref
, XVECEXP (x
, i
, j
)))
3308 /* TRUE if some insn in the range (START, END] references a memory location
3309 that would be affected by a store to MEMREF. */
3311 memref_used_between_p (rtx memref
, rtx start
, rtx end
)
3315 for (insn
= NEXT_INSN (start
); insn
!= NEXT_INSN (end
);
3316 insn
= NEXT_INSN (insn
))
3318 if (!NONDEBUG_INSN_P (insn
))
3321 if (memref_referenced_p (memref
, PATTERN (insn
)))
3324 /* Nonconst functions may access memory. */
3325 if (CALL_P (insn
) && (! RTL_CONST_CALL_P (insn
)))
3332 /* Mark REG as having no known equivalence.
3333 Some instructions might have been processed before and furnished
3334 with REG_EQUIV notes for this register; these notes will have to be
3336 STORE is the piece of RTL that does the non-constant / conflicting
3337 assignment - a SET, CLOBBER or REG_INC note. It is currently not used,
3338 but needs to be there because this function is called from note_stores. */
3340 no_equiv (rtx reg
, const_rtx store ATTRIBUTE_UNUSED
,
3341 void *data ATTRIBUTE_UNUSED
)
3348 regno
= REGNO (reg
);
3349 list
= reg_equiv
[regno
].init_insns
;
3350 if (list
== const0_rtx
)
3352 reg_equiv
[regno
].init_insns
= const0_rtx
;
3353 reg_equiv
[regno
].replacement
= NULL_RTX
;
3354 /* This doesn't matter for equivalences made for argument registers, we
3355 should keep their initialization insns. */
3356 if (reg_equiv
[regno
].is_arg_equivalence
)
3358 ira_reg_equiv
[regno
].defined_p
= false;
3359 ira_reg_equiv
[regno
].init_insns
= NULL_RTX
;
3360 for (; list
; list
= XEXP (list
, 1))
3362 rtx insn
= XEXP (list
, 0);
3363 remove_note (insn
, find_reg_note (insn
, REG_EQUIV
, NULL_RTX
));
3367 /* Check whether the SUBREG is a paradoxical subreg and set the result
3371 set_paradoxical_subreg (rtx
*subreg
, void *pdx_subregs
)
3375 if ((*subreg
) == NULL_RTX
)
3377 if (GET_CODE (*subreg
) != SUBREG
)
3379 reg
= SUBREG_REG (*subreg
);
3383 if (paradoxical_subreg_p (*subreg
))
3384 ((bool *)pdx_subregs
)[REGNO (reg
)] = true;
3389 /* In DEBUG_INSN location adjust REGs from CLEARED_REGS bitmap to the
3390 equivalent replacement. */
3393 adjust_cleared_regs (rtx loc
, const_rtx old_rtx ATTRIBUTE_UNUSED
, void *data
)
3397 bitmap cleared_regs
= (bitmap
) data
;
3398 if (bitmap_bit_p (cleared_regs
, REGNO (loc
)))
3399 return simplify_replace_fn_rtx (copy_rtx (*reg_equiv
[REGNO (loc
)].src_p
),
3400 NULL_RTX
, adjust_cleared_regs
, data
);
3405 /* Nonzero if we recorded an equivalence for a LABEL_REF. */
3406 static int recorded_label_ref
;
3408 /* Find registers that are equivalent to a single value throughout the
3409 compilation (either because they can be referenced in memory or are
3410 set once from a single constant). Lower their priority for a
3413 If such a register is only referenced once, try substituting its
3414 value into the using insn. If it succeeds, we can eliminate the
3415 register completely.
3417 Initialize init_insns in ira_reg_equiv array.
3419 Return non-zero if jump label rebuilding should be done. */
3421 update_equiv_regs (void)
3426 bitmap cleared_regs
;
3429 /* We need to keep track of whether or not we recorded a LABEL_REF so
3430 that we know if the jump optimizer needs to be rerun. */
3431 recorded_label_ref
= 0;
3433 /* Use pdx_subregs to show whether a reg is used in a paradoxical
3435 pdx_subregs
= XCNEWVEC (bool, max_regno
);
3437 reg_equiv
= XCNEWVEC (struct equivalence
, max_regno
);
3440 init_alias_analysis ();
3442 /* Scan insns and set pdx_subregs[regno] if the reg is used in a
3443 paradoxical subreg. Don't set such reg sequivalent to a mem,
3444 because lra will not substitute such equiv memory in order to
3445 prevent access beyond allocated memory for paradoxical memory subreg. */
3446 FOR_EACH_BB_FN (bb
, cfun
)
3447 FOR_BB_INSNS (bb
, insn
)
3448 if (NONDEBUG_INSN_P (insn
))
3449 for_each_rtx (&insn
, set_paradoxical_subreg
, (void *) pdx_subregs
);
3451 /* Scan the insns and find which registers have equivalences. Do this
3452 in a separate scan of the insns because (due to -fcse-follow-jumps)
3453 a register can be set below its use. */
3454 FOR_EACH_BB_FN (bb
, cfun
)
3456 loop_depth
= bb_loop_depth (bb
);
3458 for (insn
= BB_HEAD (bb
);
3459 insn
!= NEXT_INSN (BB_END (bb
));
3460 insn
= NEXT_INSN (insn
))
3467 if (! INSN_P (insn
))
3470 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
3471 if (REG_NOTE_KIND (note
) == REG_INC
)
3472 no_equiv (XEXP (note
, 0), note
, NULL
);
3474 set
= single_set (insn
);
3476 /* If this insn contains more (or less) than a single SET,
3477 only mark all destinations as having no known equivalence. */
3480 note_stores (PATTERN (insn
), no_equiv
, NULL
);
3483 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
3487 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
3489 rtx part
= XVECEXP (PATTERN (insn
), 0, i
);
3491 note_stores (part
, no_equiv
, NULL
);
3495 dest
= SET_DEST (set
);
3496 src
= SET_SRC (set
);
3498 /* See if this is setting up the equivalence between an argument
3499 register and its stack slot. */
3500 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
3503 gcc_assert (REG_P (dest
));
3504 regno
= REGNO (dest
);
3506 /* Note that we don't want to clear init_insns in
3507 ira_reg_equiv even if there are multiple sets of this
3509 reg_equiv
[regno
].is_arg_equivalence
= 1;
3511 /* The insn result can have equivalence memory although
3512 the equivalence is not set up by the insn. We add
3513 this insn to init insns as it is a flag for now that
3514 regno has an equivalence. We will remove the insn
3515 from init insn list later. */
3516 if (rtx_equal_p (src
, XEXP (note
, 0)) || MEM_P (XEXP (note
, 0)))
3517 ira_reg_equiv
[regno
].init_insns
3518 = gen_rtx_INSN_LIST (VOIDmode
, insn
,
3519 ira_reg_equiv
[regno
].init_insns
);
3521 /* Continue normally in case this is a candidate for
3528 /* We only handle the case of a pseudo register being set
3529 once, or always to the same value. */
3530 /* ??? The mn10200 port breaks if we add equivalences for
3531 values that need an ADDRESS_REGS register and set them equivalent
3532 to a MEM of a pseudo. The actual problem is in the over-conservative
3533 handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
3534 calculate_needs, but we traditionally work around this problem
3535 here by rejecting equivalences when the destination is in a register
3536 that's likely spilled. This is fragile, of course, since the
3537 preferred class of a pseudo depends on all instructions that set
3541 || (regno
= REGNO (dest
)) < FIRST_PSEUDO_REGISTER
3542 || reg_equiv
[regno
].init_insns
== const0_rtx
3543 || (targetm
.class_likely_spilled_p (reg_preferred_class (regno
))
3544 && MEM_P (src
) && ! reg_equiv
[regno
].is_arg_equivalence
))
3546 /* This might be setting a SUBREG of a pseudo, a pseudo that is
3547 also set somewhere else to a constant. */
3548 note_stores (set
, no_equiv
, NULL
);
3552 /* Don't set reg (if pdx_subregs[regno] == true) equivalent to a mem. */
3553 if (MEM_P (src
) && pdx_subregs
[regno
])
3555 note_stores (set
, no_equiv
, NULL
);
3559 note
= find_reg_note (insn
, REG_EQUAL
, NULL_RTX
);
3561 /* cse sometimes generates function invariants, but doesn't put a
3562 REG_EQUAL note on the insn. Since this note would be redundant,
3563 there's no point creating it earlier than here. */
3564 if (! note
&& ! rtx_varies_p (src
, 0))
3565 note
= set_unique_reg_note (insn
, REG_EQUAL
, copy_rtx (src
));
3567 /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
3568 since it represents a function call */
3569 if (note
&& GET_CODE (XEXP (note
, 0)) == EXPR_LIST
)
3572 if (DF_REG_DEF_COUNT (regno
) != 1
3574 || rtx_varies_p (XEXP (note
, 0), 0)
3575 || (reg_equiv
[regno
].replacement
3576 && ! rtx_equal_p (XEXP (note
, 0),
3577 reg_equiv
[regno
].replacement
))))
3579 no_equiv (dest
, set
, NULL
);
3582 /* Record this insn as initializing this register. */
3583 reg_equiv
[regno
].init_insns
3584 = gen_rtx_INSN_LIST (VOIDmode
, insn
, reg_equiv
[regno
].init_insns
);
3586 /* If this register is known to be equal to a constant, record that
3587 it is always equivalent to the constant. */
3588 if (DF_REG_DEF_COUNT (regno
) == 1
3589 && note
&& ! rtx_varies_p (XEXP (note
, 0), 0))
3591 rtx note_value
= XEXP (note
, 0);
3592 remove_note (insn
, note
);
3593 set_unique_reg_note (insn
, REG_EQUIV
, note_value
);
3596 /* If this insn introduces a "constant" register, decrease the priority
3597 of that register. Record this insn if the register is only used once
3598 more and the equivalence value is the same as our source.
3600 The latter condition is checked for two reasons: First, it is an
3601 indication that it may be more efficient to actually emit the insn
3602 as written (if no registers are available, reload will substitute
3603 the equivalence). Secondly, it avoids problems with any registers
3604 dying in this insn whose death notes would be missed.
3606 If we don't have a REG_EQUIV note, see if this insn is loading
3607 a register used only in one basic block from a MEM. If so, and the
3608 MEM remains unchanged for the life of the register, add a REG_EQUIV
3611 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
3613 if (note
== 0 && REG_BASIC_BLOCK (regno
) >= NUM_FIXED_BLOCKS
3614 && MEM_P (SET_SRC (set
))
3615 && validate_equiv_mem (insn
, dest
, SET_SRC (set
)))
3616 note
= set_unique_reg_note (insn
, REG_EQUIV
, copy_rtx (SET_SRC (set
)));
3620 int regno
= REGNO (dest
);
3621 rtx x
= XEXP (note
, 0);
3623 /* If we haven't done so, record for reload that this is an
3624 equivalencing insn. */
3625 if (!reg_equiv
[regno
].is_arg_equivalence
)
3626 ira_reg_equiv
[regno
].init_insns
3627 = gen_rtx_INSN_LIST (VOIDmode
, insn
,
3628 ira_reg_equiv
[regno
].init_insns
);
3630 /* Record whether or not we created a REG_EQUIV note for a LABEL_REF.
3631 We might end up substituting the LABEL_REF for uses of the
3632 pseudo here or later. That kind of transformation may turn an
3633 indirect jump into a direct jump, in which case we must rerun the
3634 jump optimizer to ensure that the JUMP_LABEL fields are valid. */
3635 if (GET_CODE (x
) == LABEL_REF
3636 || (GET_CODE (x
) == CONST
3637 && GET_CODE (XEXP (x
, 0)) == PLUS
3638 && (GET_CODE (XEXP (XEXP (x
, 0), 0)) == LABEL_REF
)))
3639 recorded_label_ref
= 1;
3641 reg_equiv
[regno
].replacement
= x
;
3642 reg_equiv
[regno
].src_p
= &SET_SRC (set
);
3643 reg_equiv
[regno
].loop_depth
= loop_depth
;
3645 /* Don't mess with things live during setjmp. */
3646 if (REG_LIVE_LENGTH (regno
) >= 0 && optimize
)
3648 /* Note that the statement below does not affect the priority
3650 REG_LIVE_LENGTH (regno
) *= 2;
3652 /* If the register is referenced exactly twice, meaning it is
3653 set once and used once, indicate that the reference may be
3654 replaced by the equivalence we computed above. Do this
3655 even if the register is only used in one block so that
3656 dependencies can be handled where the last register is
3657 used in a different block (i.e. HIGH / LO_SUM sequences)
3658 and to reduce the number of registers alive across
3661 if (REG_N_REFS (regno
) == 2
3662 && (rtx_equal_p (x
, src
)
3663 || ! equiv_init_varies_p (src
))
3664 && NONJUMP_INSN_P (insn
)
3665 && equiv_init_movable_p (PATTERN (insn
), regno
))
3666 reg_equiv
[regno
].replace
= 1;
3675 /* A second pass, to gather additional equivalences with memory. This needs
3676 to be done after we know which registers we are going to replace. */
3678 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
3683 if (! INSN_P (insn
))
3686 set
= single_set (insn
);
3690 dest
= SET_DEST (set
);
3691 src
= SET_SRC (set
);
3693 /* If this sets a MEM to the contents of a REG that is only used
3694 in a single basic block, see if the register is always equivalent
3695 to that memory location and if moving the store from INSN to the
3696 insn that set REG is safe. If so, put a REG_EQUIV note on the
3699 Don't add a REG_EQUIV note if the insn already has one. The existing
3700 REG_EQUIV is likely more useful than the one we are adding.
3702 If one of the regs in the address has reg_equiv[REGNO].replace set,
3703 then we can't add this REG_EQUIV note. The reg_equiv[REGNO].replace
3704 optimization may move the set of this register immediately before
3705 insn, which puts it after reg_equiv[REGNO].init_insns, and hence
3706 the mention in the REG_EQUIV note would be to an uninitialized
3709 if (MEM_P (dest
) && REG_P (src
)
3710 && (regno
= REGNO (src
)) >= FIRST_PSEUDO_REGISTER
3711 && REG_BASIC_BLOCK (regno
) >= NUM_FIXED_BLOCKS
3712 && DF_REG_DEF_COUNT (regno
) == 1
3713 && reg_equiv
[regno
].init_insns
!= 0
3714 && reg_equiv
[regno
].init_insns
!= const0_rtx
3715 && ! find_reg_note (XEXP (reg_equiv
[regno
].init_insns
, 0),
3716 REG_EQUIV
, NULL_RTX
)
3717 && ! contains_replace_regs (XEXP (dest
, 0))
3718 && ! pdx_subregs
[regno
])
3720 rtx init_insn
= XEXP (reg_equiv
[regno
].init_insns
, 0);
3721 if (validate_equiv_mem (init_insn
, src
, dest
)
3722 && ! memref_used_between_p (dest
, init_insn
, insn
)
3723 /* Attaching a REG_EQUIV note will fail if INIT_INSN has
3725 && set_unique_reg_note (init_insn
, REG_EQUIV
, copy_rtx (dest
)))
3727 /* This insn makes the equivalence, not the one initializing
3729 ira_reg_equiv
[regno
].init_insns
3730 = gen_rtx_INSN_LIST (VOIDmode
, insn
, NULL_RTX
);
3731 df_notes_rescan (init_insn
);
3736 cleared_regs
= BITMAP_ALLOC (NULL
);
3737 /* Now scan all regs killed in an insn to see if any of them are
3738 registers only used that once. If so, see if we can replace the
3739 reference with the equivalent form. If we can, delete the
3740 initializing reference and this register will go away. If we
3741 can't replace the reference, and the initializing reference is
3742 within the same loop (or in an inner loop), then move the register
3743 initialization just before the use, so that they are in the same
3745 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
3747 loop_depth
= bb_loop_depth (bb
);
3748 for (insn
= BB_END (bb
);
3749 insn
!= PREV_INSN (BB_HEAD (bb
));
3750 insn
= PREV_INSN (insn
))
3754 if (! INSN_P (insn
))
3757 /* Don't substitute into a non-local goto, this confuses CFG. */
3759 && find_reg_note (insn
, REG_NON_LOCAL_GOTO
, NULL_RTX
))
3762 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
3764 if (REG_NOTE_KIND (link
) == REG_DEAD
3765 /* Make sure this insn still refers to the register. */
3766 && reg_mentioned_p (XEXP (link
, 0), PATTERN (insn
)))
3768 int regno
= REGNO (XEXP (link
, 0));
3771 if (! reg_equiv
[regno
].replace
3772 || reg_equiv
[regno
].loop_depth
< loop_depth
3773 /* There is no sense to move insns if live range
3774 shrinkage or register pressure-sensitive
3775 scheduling were done because it will not
3776 improve allocation but worsen insn schedule
3777 with a big probability. */
3778 || flag_live_range_shrinkage
3779 || (flag_sched_pressure
&& flag_schedule_insns
))
3782 /* reg_equiv[REGNO].replace gets set only when
3783 REG_N_REFS[REGNO] is 2, i.e. the register is set
3784 once and used once. (If it were only set, but
3785 not used, flow would have deleted the setting
3786 insns.) Hence there can only be one insn in
3787 reg_equiv[REGNO].init_insns. */
3788 gcc_assert (reg_equiv
[regno
].init_insns
3789 && !XEXP (reg_equiv
[regno
].init_insns
, 1));
3790 equiv_insn
= XEXP (reg_equiv
[regno
].init_insns
, 0);
3792 /* We may not move instructions that can throw, since
3793 that changes basic block boundaries and we are not
3794 prepared to adjust the CFG to match. */
3795 if (can_throw_internal (equiv_insn
))
3798 if (asm_noperands (PATTERN (equiv_insn
)) < 0
3799 && validate_replace_rtx (regno_reg_rtx
[regno
],
3800 *(reg_equiv
[regno
].src_p
), insn
))
3806 /* Find the last note. */
3807 for (last_link
= link
; XEXP (last_link
, 1);
3808 last_link
= XEXP (last_link
, 1))
3811 /* Append the REG_DEAD notes from equiv_insn. */
3812 equiv_link
= REG_NOTES (equiv_insn
);
3816 equiv_link
= XEXP (equiv_link
, 1);
3817 if (REG_NOTE_KIND (note
) == REG_DEAD
)
3819 remove_note (equiv_insn
, note
);
3820 XEXP (last_link
, 1) = note
;
3821 XEXP (note
, 1) = NULL_RTX
;
3826 remove_death (regno
, insn
);
3827 SET_REG_N_REFS (regno
, 0);
3828 REG_FREQ (regno
) = 0;
3829 delete_insn (equiv_insn
);
3831 reg_equiv
[regno
].init_insns
3832 = XEXP (reg_equiv
[regno
].init_insns
, 1);
3834 ira_reg_equiv
[regno
].init_insns
= NULL_RTX
;
3835 bitmap_set_bit (cleared_regs
, regno
);
3837 /* Move the initialization of the register to just before
3838 INSN. Update the flow information. */
3839 else if (prev_nondebug_insn (insn
) != equiv_insn
)
3843 new_insn
= emit_insn_before (PATTERN (equiv_insn
), insn
);
3844 REG_NOTES (new_insn
) = REG_NOTES (equiv_insn
);
3845 REG_NOTES (equiv_insn
) = 0;
3846 /* Rescan it to process the notes. */
3847 df_insn_rescan (new_insn
);
3849 /* Make sure this insn is recognized before
3850 reload begins, otherwise
3851 eliminate_regs_in_insn will die. */
3852 INSN_CODE (new_insn
) = INSN_CODE (equiv_insn
);
3854 delete_insn (equiv_insn
);
3856 XEXP (reg_equiv
[regno
].init_insns
, 0) = new_insn
;
3858 REG_BASIC_BLOCK (regno
) = bb
->index
;
3859 REG_N_CALLS_CROSSED (regno
) = 0;
3860 REG_FREQ_CALLS_CROSSED (regno
) = 0;
3861 REG_N_THROWING_CALLS_CROSSED (regno
) = 0;
3862 REG_LIVE_LENGTH (regno
) = 2;
3864 if (insn
== BB_HEAD (bb
))
3865 BB_HEAD (bb
) = PREV_INSN (insn
);
3867 ira_reg_equiv
[regno
].init_insns
3868 = gen_rtx_INSN_LIST (VOIDmode
, new_insn
, NULL_RTX
);
3869 bitmap_set_bit (cleared_regs
, regno
);
3876 if (!bitmap_empty_p (cleared_regs
))
3878 FOR_EACH_BB_FN (bb
, cfun
)
3880 bitmap_and_compl_into (DF_LR_IN (bb
), cleared_regs
);
3881 bitmap_and_compl_into (DF_LR_OUT (bb
), cleared_regs
);
3884 bitmap_and_compl_into (DF_LIVE_IN (bb
), cleared_regs
);
3885 bitmap_and_compl_into (DF_LIVE_OUT (bb
), cleared_regs
);
3888 /* Last pass - adjust debug insns referencing cleared regs. */
3889 if (MAY_HAVE_DEBUG_INSNS
)
3890 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
3891 if (DEBUG_INSN_P (insn
))
3893 rtx old_loc
= INSN_VAR_LOCATION_LOC (insn
);
3894 INSN_VAR_LOCATION_LOC (insn
)
3895 = simplify_replace_fn_rtx (old_loc
, NULL_RTX
,
3896 adjust_cleared_regs
,
3897 (void *) cleared_regs
);
3898 if (old_loc
!= INSN_VAR_LOCATION_LOC (insn
))
3899 df_insn_rescan (insn
);
3903 BITMAP_FREE (cleared_regs
);
3908 end_alias_analysis ();
3911 return recorded_label_ref
;
3916 /* Set up fields memory, constant, and invariant from init_insns in
3917 the structures of array ira_reg_equiv. */
3919 setup_reg_equiv (void)
3922 rtx elem
, prev_elem
, next_elem
, insn
, set
, x
;
3924 for (i
= FIRST_PSEUDO_REGISTER
; i
< ira_reg_equiv_len
; i
++)
3925 for (prev_elem
= NULL
, elem
= ira_reg_equiv
[i
].init_insns
;
3927 prev_elem
= elem
, elem
= next_elem
)
3929 next_elem
= XEXP (elem
, 1);
3930 insn
= XEXP (elem
, 0);
3931 set
= single_set (insn
);
3933 /* Init insns can set up equivalence when the reg is a destination or
3934 a source (in this case the destination is memory). */
3935 if (set
!= 0 && (REG_P (SET_DEST (set
)) || REG_P (SET_SRC (set
))))
3937 if ((x
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
)) != NULL
)
3940 if (REG_P (SET_DEST (set
))
3941 && REGNO (SET_DEST (set
)) == (unsigned int) i
3942 && ! rtx_equal_p (SET_SRC (set
), x
) && MEM_P (x
))
3944 /* This insn reporting the equivalence but
3945 actually not setting it. Remove it from the
3947 if (prev_elem
== NULL
)
3948 ira_reg_equiv
[i
].init_insns
= next_elem
;
3950 XEXP (prev_elem
, 1) = next_elem
;
3954 else if (REG_P (SET_DEST (set
))
3955 && REGNO (SET_DEST (set
)) == (unsigned int) i
)
3959 gcc_assert (REG_P (SET_SRC (set
))
3960 && REGNO (SET_SRC (set
)) == (unsigned int) i
);
3963 if (! function_invariant_p (x
)
3965 /* A function invariant is often CONSTANT_P but may
3966 include a register. We promise to only pass
3967 CONSTANT_P objects to LEGITIMATE_PIC_OPERAND_P. */
3968 || (CONSTANT_P (x
) && LEGITIMATE_PIC_OPERAND_P (x
)))
3970 /* It can happen that a REG_EQUIV note contains a MEM
3971 that is not a legitimate memory operand. As later
3972 stages of reload assume that all addresses found in
3973 the lra_regno_equiv_* arrays were originally
3974 legitimate, we ignore such REG_EQUIV notes. */
3975 if (memory_operand (x
, VOIDmode
))
3977 ira_reg_equiv
[i
].defined_p
= true;
3978 ira_reg_equiv
[i
].memory
= x
;
3981 else if (function_invariant_p (x
))
3983 enum machine_mode mode
;
3985 mode
= GET_MODE (SET_DEST (set
));
3986 if (GET_CODE (x
) == PLUS
3987 || x
== frame_pointer_rtx
|| x
== arg_pointer_rtx
)
3988 /* This is PLUS of frame pointer and a constant,
3990 ira_reg_equiv
[i
].invariant
= x
;
3991 else if (targetm
.legitimate_constant_p (mode
, x
))
3992 ira_reg_equiv
[i
].constant
= x
;
3995 ira_reg_equiv
[i
].memory
= force_const_mem (mode
, x
);
3996 if (ira_reg_equiv
[i
].memory
== NULL_RTX
)
3998 ira_reg_equiv
[i
].defined_p
= false;
3999 ira_reg_equiv
[i
].init_insns
= NULL_RTX
;
4003 ira_reg_equiv
[i
].defined_p
= true;
4008 ira_reg_equiv
[i
].defined_p
= false;
4009 ira_reg_equiv
[i
].init_insns
= NULL_RTX
;
4016 /* Print chain C to FILE. */
4018 print_insn_chain (FILE *file
, struct insn_chain
*c
)
4020 fprintf (file
, "insn=%d, ", INSN_UID (c
->insn
));
4021 bitmap_print (file
, &c
->live_throughout
, "live_throughout: ", ", ");
4022 bitmap_print (file
, &c
->dead_or_set
, "dead_or_set: ", "\n");
4026 /* Print all reload_insn_chains to FILE. */
4028 print_insn_chains (FILE *file
)
4030 struct insn_chain
*c
;
4031 for (c
= reload_insn_chain
; c
; c
= c
->next
)
4032 print_insn_chain (file
, c
);
4035 /* Return true if pseudo REGNO should be added to set live_throughout
4036 or dead_or_set of the insn chains for reload consideration. */
4038 pseudo_for_reload_consideration_p (int regno
)
4040 /* Consider spilled pseudos too for IRA because they still have a
4041 chance to get hard-registers in the reload when IRA is used. */
4042 return (reg_renumber
[regno
] >= 0 || ira_conflicts_p
);
4045 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
4046 REG to the number of nregs, and INIT_VALUE to get the
4047 initialization. ALLOCNUM need not be the regno of REG. */
4049 init_live_subregs (bool init_value
, sbitmap
*live_subregs
,
4050 bitmap live_subregs_used
, int allocnum
, rtx reg
)
4052 unsigned int regno
= REGNO (SUBREG_REG (reg
));
4053 int size
= GET_MODE_SIZE (GET_MODE (regno_reg_rtx
[regno
]));
4055 gcc_assert (size
> 0);
4057 /* Been there, done that. */
4058 if (bitmap_bit_p (live_subregs_used
, allocnum
))
4061 /* Create a new one. */
4062 if (live_subregs
[allocnum
] == NULL
)
4063 live_subregs
[allocnum
] = sbitmap_alloc (size
);
4065 /* If the entire reg was live before blasting into subregs, we need
4066 to init all of the subregs to ones else init to 0. */
4068 bitmap_ones (live_subregs
[allocnum
]);
4070 bitmap_clear (live_subregs
[allocnum
]);
4072 bitmap_set_bit (live_subregs_used
, allocnum
);
4075 /* Walk the insns of the current function and build reload_insn_chain,
4076 and record register life information. */
4078 build_insn_chain (void)
4081 struct insn_chain
**p
= &reload_insn_chain
;
4083 struct insn_chain
*c
= NULL
;
4084 struct insn_chain
*next
= NULL
;
4085 bitmap live_relevant_regs
= BITMAP_ALLOC (NULL
);
4086 bitmap elim_regset
= BITMAP_ALLOC (NULL
);
4087 /* live_subregs is a vector used to keep accurate information about
4088 which hardregs are live in multiword pseudos. live_subregs and
4089 live_subregs_used are indexed by pseudo number. The live_subreg
4090 entry for a particular pseudo is only used if the corresponding
4091 element is non zero in live_subregs_used. The sbitmap size of
4092 live_subreg[allocno] is number of bytes that the pseudo can
4094 sbitmap
*live_subregs
= XCNEWVEC (sbitmap
, max_regno
);
4095 bitmap live_subregs_used
= BITMAP_ALLOC (NULL
);
4097 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
4098 if (TEST_HARD_REG_BIT (eliminable_regset
, i
))
4099 bitmap_set_bit (elim_regset
, i
);
4100 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
4105 CLEAR_REG_SET (live_relevant_regs
);
4106 bitmap_clear (live_subregs_used
);
4108 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb
), 0, i
, bi
)
4110 if (i
>= FIRST_PSEUDO_REGISTER
)
4112 bitmap_set_bit (live_relevant_regs
, i
);
4115 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb
),
4116 FIRST_PSEUDO_REGISTER
, i
, bi
)
4118 if (pseudo_for_reload_consideration_p (i
))
4119 bitmap_set_bit (live_relevant_regs
, i
);
4122 FOR_BB_INSNS_REVERSE (bb
, insn
)
4124 if (!NOTE_P (insn
) && !BARRIER_P (insn
))
4126 unsigned int uid
= INSN_UID (insn
);
4130 c
= new_insn_chain ();
4137 c
->block
= bb
->index
;
4139 if (NONDEBUG_INSN_P (insn
))
4140 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
4142 df_ref def
= *def_rec
;
4143 unsigned int regno
= DF_REF_REGNO (def
);
4145 /* Ignore may clobbers because these are generated
4146 from calls. However, every other kind of def is
4147 added to dead_or_set. */
4148 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
4150 if (regno
< FIRST_PSEUDO_REGISTER
)
4152 if (!fixed_regs
[regno
])
4153 bitmap_set_bit (&c
->dead_or_set
, regno
);
4155 else if (pseudo_for_reload_consideration_p (regno
))
4156 bitmap_set_bit (&c
->dead_or_set
, regno
);
4159 if ((regno
< FIRST_PSEUDO_REGISTER
4160 || reg_renumber
[regno
] >= 0
4162 && (!DF_REF_FLAGS_IS_SET (def
, DF_REF_CONDITIONAL
)))
4164 rtx reg
= DF_REF_REG (def
);
4166 /* We can model subregs, but not if they are
4167 wrapped in ZERO_EXTRACTS. */
4168 if (GET_CODE (reg
) == SUBREG
4169 && !DF_REF_FLAGS_IS_SET (def
, DF_REF_ZERO_EXTRACT
))
4171 unsigned int start
= SUBREG_BYTE (reg
);
4172 unsigned int last
= start
4173 + GET_MODE_SIZE (GET_MODE (reg
));
4176 (bitmap_bit_p (live_relevant_regs
, regno
),
4177 live_subregs
, live_subregs_used
, regno
, reg
);
4179 if (!DF_REF_FLAGS_IS_SET
4180 (def
, DF_REF_STRICT_LOW_PART
))
4182 /* Expand the range to cover entire words.
4183 Bytes added here are "don't care". */
4185 = start
/ UNITS_PER_WORD
* UNITS_PER_WORD
;
4186 last
= ((last
+ UNITS_PER_WORD
- 1)
4187 / UNITS_PER_WORD
* UNITS_PER_WORD
);
4190 /* Ignore the paradoxical bits. */
4191 if (last
> SBITMAP_SIZE (live_subregs
[regno
]))
4192 last
= SBITMAP_SIZE (live_subregs
[regno
]);
4194 while (start
< last
)
4196 bitmap_clear_bit (live_subregs
[regno
], start
);
4200 if (bitmap_empty_p (live_subregs
[regno
]))
4202 bitmap_clear_bit (live_subregs_used
, regno
);
4203 bitmap_clear_bit (live_relevant_regs
, regno
);
4206 /* Set live_relevant_regs here because
4207 that bit has to be true to get us to
4208 look at the live_subregs fields. */
4209 bitmap_set_bit (live_relevant_regs
, regno
);
4213 /* DF_REF_PARTIAL is generated for
4214 subregs, STRICT_LOW_PART, and
4215 ZERO_EXTRACT. We handle the subreg
4216 case above so here we have to keep from
4217 modeling the def as a killing def. */
4218 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
))
4220 bitmap_clear_bit (live_subregs_used
, regno
);
4221 bitmap_clear_bit (live_relevant_regs
, regno
);
4227 bitmap_and_compl_into (live_relevant_regs
, elim_regset
);
4228 bitmap_copy (&c
->live_throughout
, live_relevant_regs
);
4230 if (NONDEBUG_INSN_P (insn
))
4231 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
4233 df_ref use
= *use_rec
;
4234 unsigned int regno
= DF_REF_REGNO (use
);
4235 rtx reg
= DF_REF_REG (use
);
4237 /* DF_REF_READ_WRITE on a use means that this use
4238 is fabricated from a def that is a partial set
4239 to a multiword reg. Here, we only model the
4240 subreg case that is not wrapped in ZERO_EXTRACT
4241 precisely so we do not need to look at the
4243 if (DF_REF_FLAGS_IS_SET (use
, DF_REF_READ_WRITE
)
4244 && !DF_REF_FLAGS_IS_SET (use
, DF_REF_ZERO_EXTRACT
)
4245 && DF_REF_FLAGS_IS_SET (use
, DF_REF_SUBREG
))
4248 /* Add the last use of each var to dead_or_set. */
4249 if (!bitmap_bit_p (live_relevant_regs
, regno
))
4251 if (regno
< FIRST_PSEUDO_REGISTER
)
4253 if (!fixed_regs
[regno
])
4254 bitmap_set_bit (&c
->dead_or_set
, regno
);
4256 else if (pseudo_for_reload_consideration_p (regno
))
4257 bitmap_set_bit (&c
->dead_or_set
, regno
);
4260 if (regno
< FIRST_PSEUDO_REGISTER
4261 || pseudo_for_reload_consideration_p (regno
))
4263 if (GET_CODE (reg
) == SUBREG
4264 && !DF_REF_FLAGS_IS_SET (use
,
4266 | DF_REF_ZERO_EXTRACT
))
4268 unsigned int start
= SUBREG_BYTE (reg
);
4269 unsigned int last
= start
4270 + GET_MODE_SIZE (GET_MODE (reg
));
4273 (bitmap_bit_p (live_relevant_regs
, regno
),
4274 live_subregs
, live_subregs_used
, regno
, reg
);
4276 /* Ignore the paradoxical bits. */
4277 if (last
> SBITMAP_SIZE (live_subregs
[regno
]))
4278 last
= SBITMAP_SIZE (live_subregs
[regno
]);
4280 while (start
< last
)
4282 bitmap_set_bit (live_subregs
[regno
], start
);
4287 /* Resetting the live_subregs_used is
4288 effectively saying do not use the subregs
4289 because we are reading the whole
4291 bitmap_clear_bit (live_subregs_used
, regno
);
4292 bitmap_set_bit (live_relevant_regs
, regno
);
4298 /* FIXME!! The following code is a disaster. Reload needs to see the
4299 labels and jump tables that are just hanging out in between
4300 the basic blocks. See pr33676. */
4301 insn
= BB_HEAD (bb
);
4303 /* Skip over the barriers and cruft. */
4304 while (insn
&& (BARRIER_P (insn
) || NOTE_P (insn
)
4305 || BLOCK_FOR_INSN (insn
) == bb
))
4306 insn
= PREV_INSN (insn
);
4308 /* While we add anything except barriers and notes, the focus is
4309 to get the labels and jump tables into the
4310 reload_insn_chain. */
4313 if (!NOTE_P (insn
) && !BARRIER_P (insn
))
4315 if (BLOCK_FOR_INSN (insn
))
4318 c
= new_insn_chain ();
4324 /* The block makes no sense here, but it is what the old
4326 c
->block
= bb
->index
;
4328 bitmap_copy (&c
->live_throughout
, live_relevant_regs
);
4330 insn
= PREV_INSN (insn
);
4334 reload_insn_chain
= c
;
4337 for (i
= 0; i
< (unsigned int) max_regno
; i
++)
4338 if (live_subregs
[i
] != NULL
)
4339 sbitmap_free (live_subregs
[i
]);
4340 free (live_subregs
);
4341 BITMAP_FREE (live_subregs_used
);
4342 BITMAP_FREE (live_relevant_regs
);
4343 BITMAP_FREE (elim_regset
);
4346 print_insn_chains (dump_file
);
4349 /* Examine the rtx found in *LOC, which is read or written to as determined
4350 by TYPE. Return false if we find a reason why an insn containing this
4351 rtx should not be moved (such as accesses to non-constant memory), true
4354 rtx_moveable_p (rtx
*loc
, enum op_type type
)
4358 enum rtx_code code
= GET_CODE (x
);
4361 code
= GET_CODE (x
);
4371 return type
== OP_IN
;
4377 if (x
== frame_pointer_rtx
)
4379 if (HARD_REGISTER_P (x
))
4385 if (type
== OP_IN
&& MEM_READONLY_P (x
))
4386 return rtx_moveable_p (&XEXP (x
, 0), OP_IN
);
4390 return (rtx_moveable_p (&SET_SRC (x
), OP_IN
)
4391 && rtx_moveable_p (&SET_DEST (x
), OP_OUT
));
4393 case STRICT_LOW_PART
:
4394 return rtx_moveable_p (&XEXP (x
, 0), OP_OUT
);
4398 return (rtx_moveable_p (&XEXP (x
, 0), type
)
4399 && rtx_moveable_p (&XEXP (x
, 1), OP_IN
)
4400 && rtx_moveable_p (&XEXP (x
, 2), OP_IN
));
4403 return rtx_moveable_p (&SET_DEST (x
), OP_OUT
);
4409 fmt
= GET_RTX_FORMAT (code
);
4410 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4414 if (!rtx_moveable_p (&XEXP (x
, i
), type
))
4417 else if (fmt
[i
] == 'E')
4418 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
4420 if (!rtx_moveable_p (&XVECEXP (x
, i
, j
), type
))
4427 /* A wrapper around dominated_by_p, which uses the information in UID_LUID
4428 to give dominance relationships between two insns I1 and I2. */
4430 insn_dominated_by_p (rtx i1
, rtx i2
, int *uid_luid
)
4432 basic_block bb1
= BLOCK_FOR_INSN (i1
);
4433 basic_block bb2
= BLOCK_FOR_INSN (i2
);
4436 return uid_luid
[INSN_UID (i2
)] < uid_luid
[INSN_UID (i1
)];
4437 return dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
);
4440 /* Record the range of register numbers added by find_moveable_pseudos. */
4441 int first_moveable_pseudo
, last_moveable_pseudo
;
4443 /* These two vectors hold data for every register added by
4444 find_movable_pseudos, with index 0 holding data for the
4445 first_moveable_pseudo. */
4446 /* The original home register. */
4447 static vec
<rtx
> pseudo_replaced_reg
;
4449 /* Look for instances where we have an instruction that is known to increase
4450 register pressure, and whose result is not used immediately. If it is
4451 possible to move the instruction downwards to just before its first use,
4452 split its lifetime into two ranges. We create a new pseudo to compute the
4453 value, and emit a move instruction just before the first use. If, after
4454 register allocation, the new pseudo remains unallocated, the function
4455 move_unallocated_pseudos then deletes the move instruction and places
4456 the computation just before the first use.
4458 Such a move is safe and profitable if all the input registers remain live
4459 and unchanged between the original computation and its first use. In such
4460 a situation, the computation is known to increase register pressure, and
4461 moving it is known to at least not worsen it.
4463 We restrict moves to only those cases where a register remains unallocated,
4464 in order to avoid interfering too much with the instruction schedule. As
4465 an exception, we may move insns which only modify their input register
4466 (typically induction variables), as this increases the freedom for our
4467 intended transformation, and does not limit the second instruction
4471 find_moveable_pseudos (void)
4474 int max_regs
= max_reg_num ();
4475 int max_uid
= get_max_uid ();
4477 int *uid_luid
= XNEWVEC (int, max_uid
);
4478 rtx
*closest_uses
= XNEWVEC (rtx
, max_regs
);
4479 /* A set of registers which are live but not modified throughout a block. */
4480 bitmap_head
*bb_transp_live
= XNEWVEC (bitmap_head
,
4481 last_basic_block_for_fn (cfun
));
4482 /* A set of registers which only exist in a given basic block. */
4483 bitmap_head
*bb_local
= XNEWVEC (bitmap_head
,
4484 last_basic_block_for_fn (cfun
));
4485 /* A set of registers which are set once, in an instruction that can be
4486 moved freely downwards, but are otherwise transparent to a block. */
4487 bitmap_head
*bb_moveable_reg_sets
= XNEWVEC (bitmap_head
,
4488 last_basic_block_for_fn (cfun
));
4489 bitmap_head live
, used
, set
, interesting
, unusable_as_input
;
4491 bitmap_initialize (&interesting
, 0);
4493 first_moveable_pseudo
= max_regs
;
4494 pseudo_replaced_reg
.release ();
4495 pseudo_replaced_reg
.safe_grow_cleared (max_regs
);
4498 calculate_dominance_info (CDI_DOMINATORS
);
4501 bitmap_initialize (&live
, 0);
4502 bitmap_initialize (&used
, 0);
4503 bitmap_initialize (&set
, 0);
4504 bitmap_initialize (&unusable_as_input
, 0);
4505 FOR_EACH_BB_FN (bb
, cfun
)
4508 bitmap transp
= bb_transp_live
+ bb
->index
;
4509 bitmap moveable
= bb_moveable_reg_sets
+ bb
->index
;
4510 bitmap local
= bb_local
+ bb
->index
;
4512 bitmap_initialize (local
, 0);
4513 bitmap_initialize (transp
, 0);
4514 bitmap_initialize (moveable
, 0);
4515 bitmap_copy (&live
, df_get_live_out (bb
));
4516 bitmap_and_into (&live
, df_get_live_in (bb
));
4517 bitmap_copy (transp
, &live
);
4518 bitmap_clear (moveable
);
4519 bitmap_clear (&live
);
4520 bitmap_clear (&used
);
4521 bitmap_clear (&set
);
4522 FOR_BB_INSNS (bb
, insn
)
4523 if (NONDEBUG_INSN_P (insn
))
4525 df_ref
*u_rec
, *d_rec
;
4527 uid_luid
[INSN_UID (insn
)] = i
++;
4529 u_rec
= DF_INSN_USES (insn
);
4530 d_rec
= DF_INSN_DEFS (insn
);
4531 if (d_rec
[0] != NULL
&& d_rec
[1] == NULL
4532 && u_rec
[0] != NULL
&& u_rec
[1] == NULL
4533 && DF_REF_REGNO (*u_rec
) == DF_REF_REGNO (*d_rec
)
4534 && !bitmap_bit_p (&set
, DF_REF_REGNO (*u_rec
))
4535 && rtx_moveable_p (&PATTERN (insn
), OP_IN
))
4537 unsigned regno
= DF_REF_REGNO (*u_rec
);
4538 bitmap_set_bit (moveable
, regno
);
4539 bitmap_set_bit (&set
, regno
);
4540 bitmap_set_bit (&used
, regno
);
4541 bitmap_clear_bit (transp
, regno
);
4546 unsigned regno
= DF_REF_REGNO (*u_rec
);
4547 bitmap_set_bit (&used
, regno
);
4548 if (bitmap_clear_bit (moveable
, regno
))
4549 bitmap_clear_bit (transp
, regno
);
4555 unsigned regno
= DF_REF_REGNO (*d_rec
);
4556 bitmap_set_bit (&set
, regno
);
4557 bitmap_clear_bit (transp
, regno
);
4558 bitmap_clear_bit (moveable
, regno
);
4564 bitmap_clear (&live
);
4565 bitmap_clear (&used
);
4566 bitmap_clear (&set
);
4568 FOR_EACH_BB_FN (bb
, cfun
)
4570 bitmap local
= bb_local
+ bb
->index
;
4573 FOR_BB_INSNS (bb
, insn
)
4574 if (NONDEBUG_INSN_P (insn
))
4576 rtx def_insn
, closest_use
, note
;
4577 df_ref
*def_rec
, def
, use
;
4579 bool all_dominated
, all_local
;
4580 enum machine_mode mode
;
4582 def_rec
= DF_INSN_DEFS (insn
);
4583 /* There must be exactly one def in this insn. */
4585 if (!def
|| def_rec
[1] || !single_set (insn
))
4587 /* This must be the only definition of the reg. We also limit
4588 which modes we deal with so that we can assume we can generate
4589 move instructions. */
4590 regno
= DF_REF_REGNO (def
);
4591 mode
= GET_MODE (DF_REF_REG (def
));
4592 if (DF_REG_DEF_COUNT (regno
) != 1
4593 || !DF_REF_INSN_INFO (def
)
4594 || HARD_REGISTER_NUM_P (regno
)
4595 || DF_REG_EQ_USE_COUNT (regno
) > 0
4596 || (!INTEGRAL_MODE_P (mode
) && !FLOAT_MODE_P (mode
)))
4598 def_insn
= DF_REF_INSN (def
);
4600 for (note
= REG_NOTES (def_insn
); note
; note
= XEXP (note
, 1))
4601 if (REG_NOTE_KIND (note
) == REG_EQUIV
&& MEM_P (XEXP (note
, 0)))
4607 fprintf (dump_file
, "Ignoring reg %d, has equiv memory\n",
4609 bitmap_set_bit (&unusable_as_input
, regno
);
4613 use
= DF_REG_USE_CHAIN (regno
);
4614 all_dominated
= true;
4616 closest_use
= NULL_RTX
;
4617 for (; use
; use
= DF_REF_NEXT_REG (use
))
4620 if (!DF_REF_INSN_INFO (use
))
4622 all_dominated
= false;
4626 insn
= DF_REF_INSN (use
);
4627 if (DEBUG_INSN_P (insn
))
4629 if (BLOCK_FOR_INSN (insn
) != BLOCK_FOR_INSN (def_insn
))
4631 if (!insn_dominated_by_p (insn
, def_insn
, uid_luid
))
4632 all_dominated
= false;
4633 if (closest_use
!= insn
&& closest_use
!= const0_rtx
)
4635 if (closest_use
== NULL_RTX
)
4637 else if (insn_dominated_by_p (closest_use
, insn
, uid_luid
))
4639 else if (!insn_dominated_by_p (insn
, closest_use
, uid_luid
))
4640 closest_use
= const0_rtx
;
4646 fprintf (dump_file
, "Reg %d not all uses dominated by set\n",
4651 bitmap_set_bit (local
, regno
);
4652 if (closest_use
== const0_rtx
|| closest_use
== NULL
4653 || next_nonnote_nondebug_insn (def_insn
) == closest_use
)
4656 fprintf (dump_file
, "Reg %d uninteresting%s\n", regno
,
4657 closest_use
== const0_rtx
|| closest_use
== NULL
4658 ? " (no unique first use)" : "");
4662 if (reg_referenced_p (cc0_rtx
, PATTERN (closest_use
)))
4665 fprintf (dump_file
, "Reg %d: closest user uses cc0\n",
4670 bitmap_set_bit (&interesting
, regno
);
4671 closest_uses
[regno
] = closest_use
;
4673 if (dump_file
&& (all_local
|| all_dominated
))
4675 fprintf (dump_file
, "Reg %u:", regno
);
4677 fprintf (dump_file
, " local to bb %d", bb
->index
);
4679 fprintf (dump_file
, " def dominates all uses");
4680 if (closest_use
!= const0_rtx
)
4681 fprintf (dump_file
, " has unique first use");
4682 fputs ("\n", dump_file
);
4687 EXECUTE_IF_SET_IN_BITMAP (&interesting
, 0, i
, bi
)
4689 df_ref def
= DF_REG_DEF_CHAIN (i
);
4690 rtx def_insn
= DF_REF_INSN (def
);
4691 basic_block def_block
= BLOCK_FOR_INSN (def_insn
);
4692 bitmap def_bb_local
= bb_local
+ def_block
->index
;
4693 bitmap def_bb_moveable
= bb_moveable_reg_sets
+ def_block
->index
;
4694 bitmap def_bb_transp
= bb_transp_live
+ def_block
->index
;
4695 bool local_to_bb_p
= bitmap_bit_p (def_bb_local
, i
);
4696 rtx use_insn
= closest_uses
[i
];
4697 df_ref
*def_insn_use_rec
= DF_INSN_USES (def_insn
);
4699 bool all_transp
= true;
4701 if (!REG_P (DF_REF_REG (def
)))
4707 fprintf (dump_file
, "Reg %u not local to one basic block\n",
4711 if (reg_equiv_init (i
) != NULL_RTX
)
4714 fprintf (dump_file
, "Ignoring reg %u with equiv init insn\n",
4718 if (!rtx_moveable_p (&PATTERN (def_insn
), OP_IN
))
4721 fprintf (dump_file
, "Found def insn %d for %d to be not moveable\n",
4722 INSN_UID (def_insn
), i
);
4726 fprintf (dump_file
, "Examining insn %d, def for %d\n",
4727 INSN_UID (def_insn
), i
);
4728 while (*def_insn_use_rec
!= NULL
)
4730 df_ref use
= *def_insn_use_rec
;
4731 unsigned regno
= DF_REF_REGNO (use
);
4732 if (bitmap_bit_p (&unusable_as_input
, regno
))
4736 fprintf (dump_file
, " found unusable input reg %u.\n", regno
);
4739 if (!bitmap_bit_p (def_bb_transp
, regno
))
4741 if (bitmap_bit_p (def_bb_moveable
, regno
)
4742 && !control_flow_insn_p (use_insn
)
4744 && !sets_cc0_p (use_insn
)
4748 if (modified_between_p (DF_REF_REG (use
), def_insn
, use_insn
))
4750 rtx x
= NEXT_INSN (def_insn
);
4751 while (!modified_in_p (DF_REF_REG (use
), x
))
4753 gcc_assert (x
!= use_insn
);
4757 fprintf (dump_file
, " input reg %u modified but insn %d moveable\n",
4758 regno
, INSN_UID (x
));
4759 emit_insn_after (PATTERN (x
), use_insn
);
4760 set_insn_deleted (x
);
4765 fprintf (dump_file
, " input reg %u modified between def and use\n",
4778 if (!dbg_cnt (ira_move
))
4781 fprintf (dump_file
, " all ok%s\n", all_transp
? " and transp" : "");
4785 rtx def_reg
= DF_REF_REG (def
);
4786 rtx newreg
= ira_create_new_reg (def_reg
);
4787 if (validate_change (def_insn
, DF_REF_REAL_LOC (def
), newreg
, 0))
4789 unsigned nregno
= REGNO (newreg
);
4790 emit_insn_before (gen_move_insn (def_reg
, newreg
), use_insn
);
4792 pseudo_replaced_reg
[nregno
] = def_reg
;
4797 FOR_EACH_BB_FN (bb
, cfun
)
4799 bitmap_clear (bb_local
+ bb
->index
);
4800 bitmap_clear (bb_transp_live
+ bb
->index
);
4801 bitmap_clear (bb_moveable_reg_sets
+ bb
->index
);
4803 bitmap_clear (&interesting
);
4804 bitmap_clear (&unusable_as_input
);
4806 free (closest_uses
);
4808 free (bb_transp_live
);
4809 free (bb_moveable_reg_sets
);
4811 last_moveable_pseudo
= max_reg_num ();
4813 fix_reg_equiv_init ();
4815 regstat_free_n_sets_and_refs ();
4817 regstat_init_n_sets_and_refs ();
4818 regstat_compute_ri ();
4819 free_dominance_info (CDI_DOMINATORS
);
4822 /* If SET pattern SET is an assignment from a hard register to a pseudo which
4823 is live at CALL_DOM (if non-NULL, otherwise this check is omitted), return
4824 the destination. Otherwise return NULL. */
4827 interesting_dest_for_shprep_1 (rtx set
, basic_block call_dom
)
4829 rtx src
= SET_SRC (set
);
4830 rtx dest
= SET_DEST (set
);
4831 if (!REG_P (src
) || !HARD_REGISTER_P (src
)
4832 || !REG_P (dest
) || HARD_REGISTER_P (dest
)
4833 || (call_dom
&& !bitmap_bit_p (df_get_live_in (call_dom
), REGNO (dest
))))
4838 /* If insn is interesting for parameter range-splitting shring-wrapping
4839 preparation, i.e. it is a single set from a hard register to a pseudo, which
4840 is live at CALL_DOM (if non-NULL, otherwise this check is omitted), or a
4841 parallel statement with only one such statement, return the destination.
4842 Otherwise return NULL. */
4845 interesting_dest_for_shprep (rtx insn
, basic_block call_dom
)
4849 rtx pat
= PATTERN (insn
);
4850 if (GET_CODE (pat
) == SET
)
4851 return interesting_dest_for_shprep_1 (pat
, call_dom
);
4853 if (GET_CODE (pat
) != PARALLEL
)
4856 for (int i
= 0; i
< XVECLEN (pat
, 0); i
++)
4858 rtx sub
= XVECEXP (pat
, 0, i
);
4859 if (GET_CODE (sub
) == USE
|| GET_CODE (sub
) == CLOBBER
)
4861 if (GET_CODE (sub
) != SET
4862 || side_effects_p (sub
))
4864 rtx dest
= interesting_dest_for_shprep_1 (sub
, call_dom
);
4873 /* Split live ranges of pseudos that are loaded from hard registers in the
4874 first BB in a BB that dominates all non-sibling call if such a BB can be
4875 found and is not in a loop. Return true if the function has made any
4879 split_live_ranges_for_shrink_wrap (void)
4881 basic_block bb
, call_dom
= NULL
;
4882 basic_block first
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
4883 rtx insn
, last_interesting_insn
= NULL
;
4884 bitmap_head need_new
, reachable
;
4885 vec
<basic_block
> queue
;
4887 if (!flag_shrink_wrap
)
4890 bitmap_initialize (&need_new
, 0);
4891 bitmap_initialize (&reachable
, 0);
4892 queue
.create (n_basic_blocks_for_fn (cfun
));
4894 FOR_EACH_BB_FN (bb
, cfun
)
4895 FOR_BB_INSNS (bb
, insn
)
4896 if (CALL_P (insn
) && !SIBLING_CALL_P (insn
))
4900 bitmap_clear (&need_new
);
4901 bitmap_clear (&reachable
);
4906 bitmap_set_bit (&need_new
, bb
->index
);
4907 bitmap_set_bit (&reachable
, bb
->index
);
4908 queue
.quick_push (bb
);
4912 if (queue
.is_empty ())
4914 bitmap_clear (&need_new
);
4915 bitmap_clear (&reachable
);
4920 while (!queue
.is_empty ())
4926 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4927 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
4928 && bitmap_set_bit (&reachable
, e
->dest
->index
))
4929 queue
.quick_push (e
->dest
);
4933 FOR_BB_INSNS (first
, insn
)
4935 rtx dest
= interesting_dest_for_shprep (insn
, NULL
);
4939 if (DF_REG_DEF_COUNT (REGNO (dest
)) > 1)
4941 bitmap_clear (&need_new
);
4942 bitmap_clear (&reachable
);
4946 for (df_ref use
= DF_REG_USE_CHAIN (REGNO(dest
));
4948 use
= DF_REF_NEXT_REG (use
))
4950 int ubbi
= DF_REF_BB (use
)->index
;
4951 if (bitmap_bit_p (&reachable
, ubbi
))
4952 bitmap_set_bit (&need_new
, ubbi
);
4954 last_interesting_insn
= insn
;
4957 bitmap_clear (&reachable
);
4958 if (!last_interesting_insn
)
4960 bitmap_clear (&need_new
);
4964 call_dom
= nearest_common_dominator_for_set (CDI_DOMINATORS
, &need_new
);
4965 bitmap_clear (&need_new
);
4966 if (call_dom
== first
)
4969 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
4970 while (bb_loop_depth (call_dom
) > 0)
4971 call_dom
= get_immediate_dominator (CDI_DOMINATORS
, call_dom
);
4972 loop_optimizer_finalize ();
4974 if (call_dom
== first
)
4977 calculate_dominance_info (CDI_POST_DOMINATORS
);
4978 if (dominated_by_p (CDI_POST_DOMINATORS
, first
, call_dom
))
4980 free_dominance_info (CDI_POST_DOMINATORS
);
4983 free_dominance_info (CDI_POST_DOMINATORS
);
4986 fprintf (dump_file
, "Will split live ranges of parameters at BB %i\n",
4990 FOR_BB_INSNS (first
, insn
)
4992 rtx dest
= interesting_dest_for_shprep (insn
, call_dom
);
4996 rtx newreg
= NULL_RTX
;
4998 for (use
= DF_REG_USE_CHAIN (REGNO (dest
)); use
; use
= next
)
5000 rtx uin
= DF_REF_INSN (use
);
5001 next
= DF_REF_NEXT_REG (use
);
5003 basic_block ubb
= BLOCK_FOR_INSN (uin
);
5005 || dominated_by_p (CDI_DOMINATORS
, ubb
, call_dom
))
5008 newreg
= ira_create_new_reg (dest
);
5009 validate_change (uin
, DF_REF_REAL_LOC (use
), newreg
, true);
5015 rtx new_move
= gen_move_insn (newreg
, dest
);
5016 emit_insn_after (new_move
, bb_note (call_dom
));
5019 fprintf (dump_file
, "Split live-range of register ");
5020 print_rtl_single (dump_file
, dest
);
5025 if (insn
== last_interesting_insn
)
5028 apply_change_group ();
5032 /* Perform the second half of the transformation started in
5033 find_moveable_pseudos. We look for instances where the newly introduced
5034 pseudo remains unallocated, and remove it by moving the definition to
5035 just before its use, replacing the move instruction generated by
5036 find_moveable_pseudos. */
5038 move_unallocated_pseudos (void)
5041 for (i
= first_moveable_pseudo
; i
< last_moveable_pseudo
; i
++)
5042 if (reg_renumber
[i
] < 0)
5044 int idx
= i
- first_moveable_pseudo
;
5045 rtx other_reg
= pseudo_replaced_reg
[idx
];
5046 rtx def_insn
= DF_REF_INSN (DF_REG_DEF_CHAIN (i
));
5047 /* The use must follow all definitions of OTHER_REG, so we can
5048 insert the new definition immediately after any of them. */
5049 df_ref other_def
= DF_REG_DEF_CHAIN (REGNO (other_reg
));
5050 rtx move_insn
= DF_REF_INSN (other_def
);
5051 rtx newinsn
= emit_insn_after (PATTERN (def_insn
), move_insn
);
5056 fprintf (dump_file
, "moving def of %d (insn %d now) ",
5057 REGNO (other_reg
), INSN_UID (def_insn
));
5059 delete_insn (move_insn
);
5060 while ((other_def
= DF_REG_DEF_CHAIN (REGNO (other_reg
))))
5061 delete_insn (DF_REF_INSN (other_def
));
5062 delete_insn (def_insn
);
5064 set
= single_set (newinsn
);
5065 success
= validate_change (newinsn
, &SET_DEST (set
), other_reg
, 0);
5066 gcc_assert (success
);
5068 fprintf (dump_file
, " %d) rather than keep unallocated replacement %d\n",
5069 INSN_UID (newinsn
), i
);
5070 SET_REG_N_REFS (i
, 0);
5074 /* If the backend knows where to allocate pseudos for hard
5075 register initial values, register these allocations now. */
5077 allocate_initial_values (void)
5079 if (targetm
.allocate_initial_value
)
5084 for (i
= 0; HARD_REGISTER_NUM_P (i
); i
++)
5086 if (! initial_value_entry (i
, &hreg
, &preg
))
5089 x
= targetm
.allocate_initial_value (hreg
);
5090 regno
= REGNO (preg
);
5091 if (x
&& REG_N_SETS (regno
) <= 1)
5094 reg_equiv_memory_loc (regno
) = x
;
5100 gcc_assert (REG_P (x
));
5101 new_regno
= REGNO (x
);
5102 reg_renumber
[regno
] = new_regno
;
5103 /* Poke the regno right into regno_reg_rtx so that even
5104 fixed regs are accepted. */
5105 SET_REGNO (preg
, new_regno
);
5106 /* Update global register liveness information. */
5107 FOR_EACH_BB_FN (bb
, cfun
)
5109 if (REGNO_REG_SET_P (df_get_live_in (bb
), regno
))
5110 SET_REGNO_REG_SET (df_get_live_in (bb
), new_regno
);
5111 if (REGNO_REG_SET_P (df_get_live_out (bb
), regno
))
5112 SET_REGNO_REG_SET (df_get_live_out (bb
), new_regno
);
5118 gcc_checking_assert (! initial_value_entry (FIRST_PSEUDO_REGISTER
,
5124 /* True when we use LRA instead of reload pass for the current
5128 /* True if we have allocno conflicts. It is false for non-optimized
5129 mode or when the conflict table is too big. */
5130 bool ira_conflicts_p
;
5132 /* Saved between IRA and reload. */
5133 static int saved_flag_ira_share_spill_slots
;
5135 /* This is the main entry of IRA. */
5140 int ira_max_point_before_emit
;
5142 bool saved_flag_caller_saves
= flag_caller_saves
;
5143 enum ira_region saved_flag_ira_region
= flag_ira_region
;
5145 ira_conflicts_p
= optimize
> 0;
5147 ira_use_lra_p
= targetm
.lra_p ();
5148 /* If there are too many pseudos and/or basic blocks (e.g. 10K
5149 pseudos and 10K blocks or 100K pseudos and 1K blocks), we will
5150 use simplified and faster algorithms in LRA. */
5153 && max_reg_num () >= (1 << 26) / last_basic_block_for_fn (cfun
));
5156 /* It permits to skip live range splitting in LRA. */
5157 flag_caller_saves
= false;
5158 /* There is no sense to do regional allocation when we use
5160 flag_ira_region
= IRA_REGION_ONE
;
5161 ira_conflicts_p
= false;
5164 #ifndef IRA_NO_OBSTACK
5165 gcc_obstack_init (&ira_obstack
);
5167 bitmap_obstack_initialize (&ira_bitmap_obstack
);
5169 /* LRA uses its own infrastructure to handle caller save registers. */
5170 if (flag_caller_saves
&& !ira_use_lra_p
)
5171 init_caller_save ();
5173 if (flag_ira_verbose
< 10)
5175 internal_flag_ira_verbose
= flag_ira_verbose
;
5180 internal_flag_ira_verbose
= flag_ira_verbose
- 10;
5181 ira_dump_file
= stderr
;
5184 setup_prohibited_mode_move_regs ();
5185 decrease_live_ranges_number ();
5186 df_note_add_problem ();
5188 /* DF_LIVE can't be used in the register allocator, too many other
5189 parts of the compiler depend on using the "classic" liveness
5190 interpretation of the DF_LR problem. See PR38711.
5191 Remove the problem, so that we don't spend time updating it in
5192 any of the df_analyze() calls during IRA/LRA. */
5194 df_remove_problem (df_live
);
5195 gcc_checking_assert (df_live
== NULL
);
5197 #ifdef ENABLE_CHECKING
5198 df
->changeable_flags
|= DF_VERIFY_SCHEDULED
;
5203 if (ira_conflicts_p
)
5205 calculate_dominance_info (CDI_DOMINATORS
);
5207 if (split_live_ranges_for_shrink_wrap ())
5210 free_dominance_info (CDI_DOMINATORS
);
5213 df_clear_flags (DF_NO_INSN_RESCAN
);
5215 regstat_init_n_sets_and_refs ();
5216 regstat_compute_ri ();
5218 /* If we are not optimizing, then this is the only place before
5219 register allocation where dataflow is done. And that is needed
5220 to generate these warnings. */
5222 generate_setjmp_warnings ();
5224 /* Determine if the current function is a leaf before running IRA
5225 since this can impact optimizations done by the prologue and
5226 epilogue thus changing register elimination offsets. */
5227 crtl
->is_leaf
= leaf_function_p ();
5229 if (resize_reg_info () && flag_ira_loop_pressure
)
5230 ira_set_pseudo_classes (true, ira_dump_file
);
5232 rebuild_p
= update_equiv_regs ();
5234 setup_reg_equiv_init ();
5236 if (optimize
&& rebuild_p
)
5238 timevar_push (TV_JUMP
);
5239 rebuild_jump_labels (get_insns ());
5240 if (purge_all_dead_edges ())
5241 delete_unreachable_blocks ();
5242 timevar_pop (TV_JUMP
);
5245 allocated_reg_info_size
= max_reg_num ();
5247 if (delete_trivially_dead_insns (get_insns (), max_reg_num ()))
5250 /* It is not worth to do such improvement when we use a simple
5251 allocation because of -O0 usage or because the function is too
5253 if (ira_conflicts_p
)
5254 find_moveable_pseudos ();
5256 max_regno_before_ira
= max_reg_num ();
5257 ira_setup_eliminable_regset ();
5259 ira_overall_cost
= ira_reg_cost
= ira_mem_cost
= 0;
5260 ira_load_cost
= ira_store_cost
= ira_shuffle_cost
= 0;
5261 ira_move_loops_num
= ira_additional_jumps_num
= 0;
5263 ira_assert (current_loops
== NULL
);
5264 if (flag_ira_region
== IRA_REGION_ALL
|| flag_ira_region
== IRA_REGION_MIXED
)
5265 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
| LOOPS_HAVE_RECORDED_EXITS
);
5267 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
5268 fprintf (ira_dump_file
, "Building IRA IR\n");
5269 loops_p
= ira_build ();
5271 ira_assert (ira_conflicts_p
|| !loops_p
);
5273 saved_flag_ira_share_spill_slots
= flag_ira_share_spill_slots
;
5274 if (too_high_register_pressure_p () || cfun
->calls_setjmp
)
5275 /* It is just wasting compiler's time to pack spilled pseudos into
5276 stack slots in this case -- prohibit it. We also do this if
5277 there is setjmp call because a variable not modified between
5278 setjmp and longjmp the compiler is required to preserve its
5279 value and sharing slots does not guarantee it. */
5280 flag_ira_share_spill_slots
= FALSE
;
5284 ira_max_point_before_emit
= ira_max_point
;
5286 ira_initiate_emit_data ();
5290 max_regno
= max_reg_num ();
5291 if (ira_conflicts_p
)
5295 if (! ira_use_lra_p
)
5296 ira_initiate_assign ();
5305 ira_allocno_iterator ai
;
5307 FOR_EACH_ALLOCNO (a
, ai
)
5308 ALLOCNO_REGNO (a
) = REGNO (ALLOCNO_EMIT_DATA (a
)->reg
);
5312 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
5313 fprintf (ira_dump_file
, "Flattening IR\n");
5314 ira_flattening (max_regno_before_ira
, ira_max_point_before_emit
);
5316 /* New insns were generated: add notes and recalculate live
5320 /* ??? Rebuild the loop tree, but why? Does the loop tree
5321 change if new insns were generated? Can that be handled
5322 by updating the loop tree incrementally? */
5323 loop_optimizer_finalize ();
5324 free_dominance_info (CDI_DOMINATORS
);
5325 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
5326 | LOOPS_HAVE_RECORDED_EXITS
);
5328 if (! ira_use_lra_p
)
5330 setup_allocno_assignment_flags ();
5331 ira_initiate_assign ();
5332 ira_reassign_conflict_allocnos (max_regno
);
5337 ira_finish_emit_data ();
5339 setup_reg_renumber ();
5341 calculate_allocation_cost ();
5343 #ifdef ENABLE_IRA_CHECKING
5344 if (ira_conflicts_p
)
5345 check_allocation ();
5348 if (max_regno
!= max_regno_before_ira
)
5350 regstat_free_n_sets_and_refs ();
5352 regstat_init_n_sets_and_refs ();
5353 regstat_compute_ri ();
5356 overall_cost_before
= ira_overall_cost
;
5357 if (! ira_conflicts_p
)
5361 fix_reg_equiv_init ();
5363 #ifdef ENABLE_IRA_CHECKING
5364 print_redundant_copies ();
5367 ira_spilled_reg_stack_slots_num
= 0;
5368 ira_spilled_reg_stack_slots
5369 = ((struct ira_spilled_reg_stack_slot
*)
5370 ira_allocate (max_regno
5371 * sizeof (struct ira_spilled_reg_stack_slot
)));
5372 memset (ira_spilled_reg_stack_slots
, 0,
5373 max_regno
* sizeof (struct ira_spilled_reg_stack_slot
));
5375 allocate_initial_values ();
5377 /* See comment for find_moveable_pseudos call. */
5378 if (ira_conflicts_p
)
5379 move_unallocated_pseudos ();
5381 /* Restore original values. */
5384 flag_caller_saves
= saved_flag_caller_saves
;
5385 flag_ira_region
= saved_flag_ira_region
;
5395 if (flag_ira_verbose
< 10)
5396 ira_dump_file
= dump_file
;
5398 timevar_push (TV_RELOAD
);
5401 if (current_loops
!= NULL
)
5403 loop_optimizer_finalize ();
5404 free_dominance_info (CDI_DOMINATORS
);
5406 FOR_ALL_BB_FN (bb
, cfun
)
5407 bb
->loop_father
= NULL
;
5408 current_loops
= NULL
;
5410 if (ira_conflicts_p
)
5411 ira_free (ira_spilled_reg_stack_slots
);
5415 lra (ira_dump_file
);
5416 /* ???!!! Move it before lra () when we use ira_reg_equiv in
5418 vec_free (reg_equivs
);
5424 df_set_flags (DF_NO_INSN_RESCAN
);
5425 build_insn_chain ();
5427 need_dce
= reload (get_insns (), ira_conflicts_p
);
5431 timevar_pop (TV_RELOAD
);
5433 timevar_push (TV_IRA
);
5435 if (ira_conflicts_p
&& ! ira_use_lra_p
)
5437 ira_free (ira_spilled_reg_stack_slots
);
5438 ira_finish_assign ();
5441 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
5442 && overall_cost_before
!= ira_overall_cost
)
5443 fprintf (ira_dump_file
, "+++Overall after reload %d\n", ira_overall_cost
);
5445 flag_ira_share_spill_slots
= saved_flag_ira_share_spill_slots
;
5447 if (! ira_use_lra_p
)
5450 if (current_loops
!= NULL
)
5452 loop_optimizer_finalize ();
5453 free_dominance_info (CDI_DOMINATORS
);
5455 FOR_ALL_BB_FN (bb
, cfun
)
5456 bb
->loop_father
= NULL
;
5457 current_loops
= NULL
;
5460 regstat_free_n_sets_and_refs ();
5464 cleanup_cfg (CLEANUP_EXPENSIVE
);
5466 finish_reg_equiv ();
5468 bitmap_obstack_release (&ira_bitmap_obstack
);
5469 #ifndef IRA_NO_OBSTACK
5470 obstack_free (&ira_obstack
, NULL
);
5473 /* The code after the reload has changed so much that at this point
5474 we might as well just rescan everything. Note that
5475 df_rescan_all_insns is not going to help here because it does not
5476 touch the artificial uses and defs. */
5477 df_finish_pass (true);
5478 df_scan_alloc (NULL
);
5483 df_live_add_problem ();
5484 df_live_set_all_dirty ();
5490 if (need_dce
&& optimize
)
5493 /* Diagnose uses of the hard frame pointer when it is used as a global
5494 register. Often we can get away with letting the user appropriate
5495 the frame pointer, but we should let them know when code generation
5496 makes that impossible. */
5497 if (global_regs
[HARD_FRAME_POINTER_REGNUM
] && frame_pointer_needed
)
5499 tree decl
= global_regs_decl
[HARD_FRAME_POINTER_REGNUM
];
5500 error_at (DECL_SOURCE_LOCATION (current_function_decl
),
5501 "frame pointer required, but reserved");
5502 inform (DECL_SOURCE_LOCATION (decl
), "for %qD", decl
);
5505 timevar_pop (TV_IRA
);
5508 /* Run the integrated register allocator. */
5512 const pass_data pass_data_ira
=
5514 RTL_PASS
, /* type */
5516 OPTGROUP_NONE
, /* optinfo_flags */
5517 true, /* has_execute */
5519 0, /* properties_required */
5520 0, /* properties_provided */
5521 0, /* properties_destroyed */
5522 0, /* todo_flags_start */
5523 TODO_do_not_ggc_collect
, /* todo_flags_finish */
5526 class pass_ira
: public rtl_opt_pass
5529 pass_ira (gcc::context
*ctxt
)
5530 : rtl_opt_pass (pass_data_ira
, ctxt
)
5533 /* opt_pass methods: */
5534 virtual unsigned int execute (function
*)
5540 }; // class pass_ira
5545 make_pass_ira (gcc::context
*ctxt
)
5547 return new pass_ira (ctxt
);
5552 const pass_data pass_data_reload
=
5554 RTL_PASS
, /* type */
5555 "reload", /* name */
5556 OPTGROUP_NONE
, /* optinfo_flags */
5557 true, /* has_execute */
5558 TV_RELOAD
, /* tv_id */
5559 0, /* properties_required */
5560 0, /* properties_provided */
5561 0, /* properties_destroyed */
5562 0, /* todo_flags_start */
5563 0, /* todo_flags_finish */
5566 class pass_reload
: public rtl_opt_pass
5569 pass_reload (gcc::context
*ctxt
)
5570 : rtl_opt_pass (pass_data_reload
, ctxt
)
5573 /* opt_pass methods: */
5574 virtual unsigned int execute (function
*)
5580 }; // class pass_reload
5585 make_pass_reload (gcc::context
*ctxt
)
5587 return new pass_reload (ctxt
);