1 /* Integrated Register Allocator (IRA) entry point.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011, 2012
3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* The integrated register allocator (IRA) is a
23 regional register allocator performing graph coloring on a top-down
24 traversal of nested regions. Graph coloring in a region is based
25 on Chaitin-Briggs algorithm. It is called integrated because
26 register coalescing, register live range splitting, and choosing a
27 better hard register are done on-the-fly during coloring. Register
28 coalescing and choosing a cheaper hard register is done by hard
29 register preferencing during hard register assigning. The live
30 range splitting is a byproduct of the regional register allocation.
32 Major IRA notions are:
34 o *Region* is a part of CFG where graph coloring based on
35 Chaitin-Briggs algorithm is done. IRA can work on any set of
36 nested CFG regions forming a tree. Currently the regions are
37 the entire function for the root region and natural loops for
38 the other regions. Therefore data structure representing a
39 region is called loop_tree_node.
41 o *Allocno class* is a register class used for allocation of
42 given allocno. It means that only hard register of given
43 register class can be assigned to given allocno. In reality,
44 even smaller subset of (*profitable*) hard registers can be
45 assigned. In rare cases, the subset can be even smaller
46 because our modification of Chaitin-Briggs algorithm requires
47 that sets of hard registers can be assigned to allocnos forms a
48 forest, i.e. the sets can be ordered in a way where any
49 previous set is not intersected with given set or is a superset
52 o *Pressure class* is a register class belonging to a set of
53 register classes containing all of the hard-registers available
54 for register allocation. The set of all pressure classes for a
55 target is defined in the corresponding machine-description file
56 according some criteria. Register pressure is calculated only
57 for pressure classes and it affects some IRA decisions as
58 forming allocation regions.
60 o *Allocno* represents the live range of a pseudo-register in a
61 region. Besides the obvious attributes like the corresponding
62 pseudo-register number, allocno class, conflicting allocnos and
63 conflicting hard-registers, there are a few allocno attributes
64 which are important for understanding the allocation algorithm:
66 - *Live ranges*. This is a list of ranges of *program points*
67 where the allocno lives. Program points represent places
68 where a pseudo can be born or become dead (there are
69 approximately two times more program points than the insns)
70 and they are represented by integers starting with 0. The
71 live ranges are used to find conflicts between allocnos.
72 They also play very important role for the transformation of
73 the IRA internal representation of several regions into a one
74 region representation. The later is used during the reload
75 pass work because each allocno represents all of the
76 corresponding pseudo-registers.
78 - *Hard-register costs*. This is a vector of size equal to the
79 number of available hard-registers of the allocno class. The
80 cost of a callee-clobbered hard-register for an allocno is
81 increased by the cost of save/restore code around the calls
82 through the given allocno's life. If the allocno is a move
83 instruction operand and another operand is a hard-register of
84 the allocno class, the cost of the hard-register is decreased
87 When an allocno is assigned, the hard-register with minimal
88 full cost is used. Initially, a hard-register's full cost is
89 the corresponding value from the hard-register's cost vector.
90 If the allocno is connected by a *copy* (see below) to
91 another allocno which has just received a hard-register, the
92 cost of the hard-register is decreased. Before choosing a
93 hard-register for an allocno, the allocno's current costs of
94 the hard-registers are modified by the conflict hard-register
95 costs of all of the conflicting allocnos which are not
98 - *Conflict hard-register costs*. This is a vector of the same
99 size as the hard-register costs vector. To permit an
100 unassigned allocno to get a better hard-register, IRA uses
101 this vector to calculate the final full cost of the
102 available hard-registers. Conflict hard-register costs of an
103 unassigned allocno are also changed with a change of the
104 hard-register cost of the allocno when a copy involving the
105 allocno is processed as described above. This is done to
106 show other unassigned allocnos that a given allocno prefers
107 some hard-registers in order to remove the move instruction
108 corresponding to the copy.
110 o *Cap*. If a pseudo-register does not live in a region but
111 lives in a nested region, IRA creates a special allocno called
112 a cap in the outer region. A region cap is also created for a
115 o *Copy*. Allocnos can be connected by copies. Copies are used
116 to modify hard-register costs for allocnos during coloring.
117 Such modifications reflects a preference to use the same
118 hard-register for the allocnos connected by copies. Usually
119 copies are created for move insns (in this case it results in
120 register coalescing). But IRA also creates copies for operands
121 of an insn which should be assigned to the same hard-register
122 due to constraints in the machine description (it usually
123 results in removing a move generated in reload to satisfy
124 the constraints) and copies referring to the allocno which is
125 the output operand of an instruction and the allocno which is
126 an input operand dying in the instruction (creation of such
127 copies results in less register shuffling). IRA *does not*
128 create copies between the same register allocnos from different
129 regions because we use another technique for propagating
130 hard-register preference on the borders of regions.
132 Allocnos (including caps) for the upper region in the region tree
133 *accumulate* information important for coloring from allocnos with
134 the same pseudo-register from nested regions. This includes
135 hard-register and memory costs, conflicts with hard-registers,
136 allocno conflicts, allocno copies and more. *Thus, attributes for
137 allocnos in a region have the same values as if the region had no
138 subregions*. It means that attributes for allocnos in the
139 outermost region corresponding to the function have the same values
140 as though the allocation used only one region which is the entire
141 function. It also means that we can look at IRA work as if the
142 first IRA did allocation for all function then it improved the
143 allocation for loops then their subloops and so on.
145 IRA major passes are:
147 o Building IRA internal representation which consists of the
150 * First, IRA builds regions and creates allocnos (file
151 ira-build.c) and initializes most of their attributes.
153 * Then IRA finds an allocno class for each allocno and
154 calculates its initial (non-accumulated) cost of memory and
155 each hard-register of its allocno class (file ira-cost.c).
157 * IRA creates live ranges of each allocno, calulates register
158 pressure for each pressure class in each region, sets up
159 conflict hard registers for each allocno and info about calls
160 the allocno lives through (file ira-lives.c).
162 * IRA removes low register pressure loops from the regions
163 mostly to speed IRA up (file ira-build.c).
165 * IRA propagates accumulated allocno info from lower region
166 allocnos to corresponding upper region allocnos (file
169 * IRA creates all caps (file ira-build.c).
171 * Having live-ranges of allocnos and their classes, IRA creates
172 conflicting allocnos for each allocno. Conflicting allocnos
173 are stored as a bit vector or array of pointers to the
174 conflicting allocnos whatever is more profitable (file
175 ira-conflicts.c). At this point IRA creates allocno copies.
177 o Coloring. Now IRA has all necessary info to start graph coloring
178 process. It is done in each region on top-down traverse of the
179 region tree (file ira-color.c). There are following subpasses:
181 * Finding profitable hard registers of corresponding allocno
182 class for each allocno. For example, only callee-saved hard
183 registers are frequently profitable for allocnos living
184 through colors. If the profitable hard register set of
185 allocno does not form a tree based on subset relation, we use
186 some approximation to form the tree. This approximation is
187 used to figure out trivial colorability of allocnos. The
188 approximation is a pretty rare case.
190 * Putting allocnos onto the coloring stack. IRA uses Briggs
191 optimistic coloring which is a major improvement over
192 Chaitin's coloring. Therefore IRA does not spill allocnos at
193 this point. There is some freedom in the order of putting
194 allocnos on the stack which can affect the final result of
195 the allocation. IRA uses some heuristics to improve the
198 We also use a modification of Chaitin-Briggs algorithm which
199 works for intersected register classes of allocnos. To
200 figure out trivial colorability of allocnos, the mentioned
201 above tree of hard register sets is used. To get an idea how
202 the algorithm works in i386 example, let us consider an
203 allocno to which any general hard register can be assigned.
204 If the allocno conflicts with eight allocnos to which only
205 EAX register can be assigned, given allocno is still
206 trivially colorable because all conflicting allocnos might be
207 assigned only to EAX and all other general hard registers are
210 To get an idea of the used trivial colorability criterion, it
211 is also useful to read article "Graph-Coloring Register
212 Allocation for Irregular Architectures" by Michael D. Smith
213 and Glen Holloway. Major difference between the article
214 approach and approach used in IRA is that Smith's approach
215 takes register classes only from machine description and IRA
216 calculate register classes from intermediate code too
217 (e.g. an explicit usage of hard registers in RTL code for
218 parameter passing can result in creation of additional
219 register classes which contain or exclude the hard
220 registers). That makes IRA approach useful for improving
221 coloring even for architectures with regular register files
222 and in fact some benchmarking shows the improvement for
223 regular class architectures is even bigger than for irregular
224 ones. Another difference is that Smith's approach chooses
225 intersection of classes of all insn operands in which a given
226 pseudo occurs. IRA can use bigger classes if it is still
227 more profitable than memory usage.
229 * Popping the allocnos from the stack and assigning them hard
230 registers. If IRA can not assign a hard register to an
231 allocno and the allocno is coalesced, IRA undoes the
232 coalescing and puts the uncoalesced allocnos onto the stack in
233 the hope that some such allocnos will get a hard register
234 separately. If IRA fails to assign hard register or memory
235 is more profitable for it, IRA spills the allocno. IRA
236 assigns the allocno the hard-register with minimal full
237 allocation cost which reflects the cost of usage of the
238 hard-register for the allocno and cost of usage of the
239 hard-register for allocnos conflicting with given allocno.
241 * Chaitin-Briggs coloring assigns as many pseudos as possible
242 to hard registers. After coloringh we try to improve
243 allocation with cost point of view. We improve the
244 allocation by spilling some allocnos and assigning the freed
245 hard registers to other allocnos if it decreases the overall
248 * After allono assigning in the region, IRA modifies the hard
249 register and memory costs for the corresponding allocnos in
250 the subregions to reflect the cost of possible loads, stores,
251 or moves on the border of the region and its subregions.
252 When default regional allocation algorithm is used
253 (-fira-algorithm=mixed), IRA just propagates the assignment
254 for allocnos if the register pressure in the region for the
255 corresponding pressure class is less than number of available
256 hard registers for given pressure class.
258 o Spill/restore code moving. When IRA performs an allocation
259 by traversing regions in top-down order, it does not know what
260 happens below in the region tree. Therefore, sometimes IRA
261 misses opportunities to perform a better allocation. A simple
262 optimization tries to improve allocation in a region having
263 subregions and containing in another region. If the
264 corresponding allocnos in the subregion are spilled, it spills
265 the region allocno if it is profitable. The optimization
266 implements a simple iterative algorithm performing profitable
267 transformations while they are still possible. It is fast in
268 practice, so there is no real need for a better time complexity
271 o Code change. After coloring, two allocnos representing the
272 same pseudo-register outside and inside a region respectively
273 may be assigned to different locations (hard-registers or
274 memory). In this case IRA creates and uses a new
275 pseudo-register inside the region and adds code to move allocno
276 values on the region's borders. This is done during top-down
277 traversal of the regions (file ira-emit.c). In some
278 complicated cases IRA can create a new allocno to move allocno
279 values (e.g. when a swap of values stored in two hard-registers
280 is needed). At this stage, the new allocno is marked as
281 spilled. IRA still creates the pseudo-register and the moves
282 on the region borders even when both allocnos were assigned to
283 the same hard-register. If the reload pass spills a
284 pseudo-register for some reason, the effect will be smaller
285 because another allocno will still be in the hard-register. In
286 most cases, this is better then spilling both allocnos. If
287 reload does not change the allocation for the two
288 pseudo-registers, the trivial move will be removed by
289 post-reload optimizations. IRA does not generate moves for
290 allocnos assigned to the same hard register when the default
291 regional allocation algorithm is used and the register pressure
292 in the region for the corresponding pressure class is less than
293 number of available hard registers for given pressure class.
294 IRA also does some optimizations to remove redundant stores and
295 to reduce code duplication on the region borders.
297 o Flattening internal representation. After changing code, IRA
298 transforms its internal representation for several regions into
299 one region representation (file ira-build.c). This process is
300 called IR flattening. Such process is more complicated than IR
301 rebuilding would be, but is much faster.
303 o After IR flattening, IRA tries to assign hard registers to all
304 spilled allocnos. This is impelemented by a simple and fast
305 priority coloring algorithm (see function
306 ira_reassign_conflict_allocnos::ira-color.c). Here new allocnos
307 created during the code change pass can be assigned to hard
310 o At the end IRA calls the reload pass. The reload pass
311 communicates with IRA through several functions in file
312 ira-color.c to improve its decisions in
314 * sharing stack slots for the spilled pseudos based on IRA info
315 about pseudo-register conflicts.
317 * reassigning hard-registers to all spilled pseudos at the end
318 of each reload iteration.
320 * choosing a better hard-register to spill based on IRA info
321 about pseudo-register live ranges and the register pressure
322 in places where the pseudo-register lives.
324 IRA uses a lot of data representing the target processors. These
325 data are initilized in file ira.c.
327 If function has no loops (or the loops are ignored when
328 -fira-algorithm=CB is used), we have classic Chaitin-Briggs
329 coloring (only instead of separate pass of coalescing, we use hard
330 register preferencing). In such case, IRA works much faster
331 because many things are not made (like IR flattening, the
332 spill/restore optimization, and the code change).
334 Literature is worth to read for better understanding the code:
336 o Preston Briggs, Keith D. Cooper, Linda Torczon. Improvements to
337 Graph Coloring Register Allocation.
339 o David Callahan, Brian Koblenz. Register allocation via
340 hierarchical graph coloring.
342 o Keith Cooper, Anshuman Dasgupta, Jason Eckhardt. Revisiting Graph
343 Coloring Register Allocation: A Study of the Chaitin-Briggs and
344 Callahan-Koblenz Algorithms.
346 o Guei-Yuan Lueh, Thomas Gross, and Ali-Reza Adl-Tabatabai. Global
347 Register Allocation Based on Graph Fusion.
349 o Michael D. Smith and Glenn Holloway. Graph-Coloring Register
350 Allocation for Irregular Architectures
352 o Vladimir Makarov. The Integrated Register Allocator for GCC.
354 o Vladimir Makarov. The top-down register allocator for irregular
355 register file architectures.
362 #include "coretypes.h"
371 #include "hard-reg-set.h"
372 #include "basic-block.h"
378 #include "tree-pass.h"
382 #include "diagnostic-core.h"
383 #include "integrate.h"
389 struct target_ira default_target_ira
;
390 struct target_ira_int default_target_ira_int
;
391 #if SWITCHABLE_TARGET
392 struct target_ira
*this_target_ira
= &default_target_ira
;
393 struct target_ira_int
*this_target_ira_int
= &default_target_ira_int
;
396 /* A modified value of flag `-fira-verbose' used internally. */
397 int internal_flag_ira_verbose
;
399 /* Dump file of the allocator if it is not NULL. */
402 /* The number of elements in the following array. */
403 int ira_spilled_reg_stack_slots_num
;
405 /* The following array contains info about spilled pseudo-registers
406 stack slots used in current function so far. */
407 struct ira_spilled_reg_stack_slot
*ira_spilled_reg_stack_slots
;
409 /* Correspondingly overall cost of the allocation, overall cost before
410 reload, cost of the allocnos assigned to hard-registers, cost of
411 the allocnos assigned to memory, cost of loads, stores and register
412 move insns generated for pseudo-register live range splitting (see
414 int ira_overall_cost
, overall_cost_before
;
415 int ira_reg_cost
, ira_mem_cost
;
416 int ira_load_cost
, ira_store_cost
, ira_shuffle_cost
;
417 int ira_move_loops_num
, ira_additional_jumps_num
;
419 /* All registers that can be eliminated. */
421 HARD_REG_SET eliminable_regset
;
423 /* Temporary hard reg set used for a different calculation. */
424 static HARD_REG_SET temp_hard_regset
;
428 /* The function sets up the map IRA_REG_MODE_HARD_REGSET. */
430 setup_reg_mode_hard_regset (void)
432 int i
, m
, hard_regno
;
434 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
435 for (hard_regno
= 0; hard_regno
< FIRST_PSEUDO_REGISTER
; hard_regno
++)
437 CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset
[hard_regno
][m
]);
438 for (i
= hard_regno_nregs
[hard_regno
][m
] - 1; i
>= 0; i
--)
439 if (hard_regno
+ i
< FIRST_PSEUDO_REGISTER
)
440 SET_HARD_REG_BIT (ira_reg_mode_hard_regset
[hard_regno
][m
],
446 #define no_unit_alloc_regs \
447 (this_target_ira_int->x_no_unit_alloc_regs)
449 /* The function sets up the three arrays declared above. */
451 setup_class_hard_regs (void)
453 int cl
, i
, hard_regno
, n
;
454 HARD_REG_SET processed_hard_reg_set
;
456 ira_assert (SHRT_MAX
>= FIRST_PSEUDO_REGISTER
);
457 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
459 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
460 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
461 CLEAR_HARD_REG_SET (processed_hard_reg_set
);
462 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
464 ira_non_ordered_class_hard_regs
[cl
][i
] = -1;
465 ira_class_hard_reg_index
[cl
][i
] = -1;
467 for (n
= 0, i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
469 #ifdef REG_ALLOC_ORDER
470 hard_regno
= reg_alloc_order
[i
];
474 if (TEST_HARD_REG_BIT (processed_hard_reg_set
, hard_regno
))
476 SET_HARD_REG_BIT (processed_hard_reg_set
, hard_regno
);
477 if (! TEST_HARD_REG_BIT (temp_hard_regset
, hard_regno
))
478 ira_class_hard_reg_index
[cl
][hard_regno
] = -1;
481 ira_class_hard_reg_index
[cl
][hard_regno
] = n
;
482 ira_class_hard_regs
[cl
][n
++] = hard_regno
;
485 ira_class_hard_regs_num
[cl
] = n
;
486 for (n
= 0, i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
487 if (TEST_HARD_REG_BIT (temp_hard_regset
, i
))
488 ira_non_ordered_class_hard_regs
[cl
][n
++] = i
;
489 ira_assert (ira_class_hard_regs_num
[cl
] == n
);
493 /* Set up IRA_AVAILABLE_CLASS_REGS. */
495 setup_available_class_regs (void)
499 memset (ira_available_class_regs
, 0, sizeof (ira_available_class_regs
));
500 for (i
= 0; i
< N_REG_CLASSES
; i
++)
502 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[i
]);
503 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
504 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
505 if (TEST_HARD_REG_BIT (temp_hard_regset
, j
))
506 ira_available_class_regs
[i
]++;
510 /* Set up global variables defining info about hard registers for the
511 allocation. These depend on USE_HARD_FRAME_P whose TRUE value means
512 that we can use the hard frame pointer for the allocation. */
514 setup_alloc_regs (bool use_hard_frame_p
)
516 #ifdef ADJUST_REG_ALLOC_ORDER
517 ADJUST_REG_ALLOC_ORDER
;
519 COPY_HARD_REG_SET (no_unit_alloc_regs
, fixed_reg_set
);
520 if (! use_hard_frame_p
)
521 SET_HARD_REG_BIT (no_unit_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
522 setup_class_hard_regs ();
523 setup_available_class_regs ();
528 #define alloc_reg_class_subclasses \
529 (this_target_ira_int->x_alloc_reg_class_subclasses)
531 /* Initialize the table of subclasses of each reg class. */
533 setup_reg_subclasses (void)
536 HARD_REG_SET temp_hard_regset2
;
538 for (i
= 0; i
< N_REG_CLASSES
; i
++)
539 for (j
= 0; j
< N_REG_CLASSES
; j
++)
540 alloc_reg_class_subclasses
[i
][j
] = LIM_REG_CLASSES
;
542 for (i
= 0; i
< N_REG_CLASSES
; i
++)
544 if (i
== (int) NO_REGS
)
547 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[i
]);
548 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
549 if (hard_reg_set_empty_p (temp_hard_regset
))
551 for (j
= 0; j
< N_REG_CLASSES
; j
++)
556 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[j
]);
557 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
558 if (! hard_reg_set_subset_p (temp_hard_regset
,
561 p
= &alloc_reg_class_subclasses
[j
][0];
562 while (*p
!= LIM_REG_CLASSES
) p
++;
563 *p
= (enum reg_class
) i
;
570 /* Set up IRA_MEMORY_MOVE_COST and IRA_MAX_MEMORY_MOVE_COST. */
572 setup_class_subset_and_memory_move_costs (void)
574 int cl
, cl2
, mode
, cost
;
575 HARD_REG_SET temp_hard_regset2
;
577 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
578 ira_memory_move_cost
[mode
][NO_REGS
][0]
579 = ira_memory_move_cost
[mode
][NO_REGS
][1] = SHRT_MAX
;
580 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
582 if (cl
!= (int) NO_REGS
)
583 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
585 ira_max_memory_move_cost
[mode
][cl
][0]
586 = ira_memory_move_cost
[mode
][cl
][0]
587 = memory_move_cost ((enum machine_mode
) mode
,
588 (reg_class_t
) cl
, false);
589 ira_max_memory_move_cost
[mode
][cl
][1]
590 = ira_memory_move_cost
[mode
][cl
][1]
591 = memory_move_cost ((enum machine_mode
) mode
,
592 (reg_class_t
) cl
, true);
593 /* Costs for NO_REGS are used in cost calculation on the
594 1st pass when the preferred register classes are not
595 known yet. In this case we take the best scenario. */
596 if (ira_memory_move_cost
[mode
][NO_REGS
][0]
597 > ira_memory_move_cost
[mode
][cl
][0])
598 ira_max_memory_move_cost
[mode
][NO_REGS
][0]
599 = ira_memory_move_cost
[mode
][NO_REGS
][0]
600 = ira_memory_move_cost
[mode
][cl
][0];
601 if (ira_memory_move_cost
[mode
][NO_REGS
][1]
602 > ira_memory_move_cost
[mode
][cl
][1])
603 ira_max_memory_move_cost
[mode
][NO_REGS
][1]
604 = ira_memory_move_cost
[mode
][NO_REGS
][1]
605 = ira_memory_move_cost
[mode
][cl
][1];
608 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
609 for (cl2
= (int) N_REG_CLASSES
- 1; cl2
>= 0; cl2
--)
611 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
612 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
613 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl2
]);
614 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
615 ira_class_subset_p
[cl
][cl2
]
616 = hard_reg_set_subset_p (temp_hard_regset
, temp_hard_regset2
);
617 if (! hard_reg_set_empty_p (temp_hard_regset2
)
618 && hard_reg_set_subset_p (reg_class_contents
[cl2
],
619 reg_class_contents
[cl
]))
620 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
622 cost
= ira_memory_move_cost
[mode
][cl2
][0];
623 if (cost
> ira_max_memory_move_cost
[mode
][cl
][0])
624 ira_max_memory_move_cost
[mode
][cl
][0] = cost
;
625 cost
= ira_memory_move_cost
[mode
][cl2
][1];
626 if (cost
> ira_max_memory_move_cost
[mode
][cl
][1])
627 ira_max_memory_move_cost
[mode
][cl
][1] = cost
;
630 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
631 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
633 ira_memory_move_cost
[mode
][cl
][0]
634 = ira_max_memory_move_cost
[mode
][cl
][0];
635 ira_memory_move_cost
[mode
][cl
][1]
636 = ira_max_memory_move_cost
[mode
][cl
][1];
638 setup_reg_subclasses ();
643 /* Define the following macro if allocation through malloc if
645 #define IRA_NO_OBSTACK
647 #ifndef IRA_NO_OBSTACK
648 /* Obstack used for storing all dynamic data (except bitmaps) of the
650 static struct obstack ira_obstack
;
653 /* Obstack used for storing all bitmaps of the IRA. */
654 static struct bitmap_obstack ira_bitmap_obstack
;
656 /* Allocate memory of size LEN for IRA data. */
658 ira_allocate (size_t len
)
662 #ifndef IRA_NO_OBSTACK
663 res
= obstack_alloc (&ira_obstack
, len
);
670 /* Free memory ADDR allocated for IRA data. */
672 ira_free (void *addr ATTRIBUTE_UNUSED
)
674 #ifndef IRA_NO_OBSTACK
682 /* Allocate and returns bitmap for IRA. */
684 ira_allocate_bitmap (void)
686 return BITMAP_ALLOC (&ira_bitmap_obstack
);
689 /* Free bitmap B allocated for IRA. */
691 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED
)
698 /* Output information about allocation of all allocnos (except for
699 caps) into file F. */
701 ira_print_disposition (FILE *f
)
707 fprintf (f
, "Disposition:");
708 max_regno
= max_reg_num ();
709 for (n
= 0, i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
710 for (a
= ira_regno_allocno_map
[i
];
712 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
717 fprintf (f
, " %4d:r%-4d", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
718 if ((bb
= ALLOCNO_LOOP_TREE_NODE (a
)->bb
) != NULL
)
719 fprintf (f
, "b%-3d", bb
->index
);
721 fprintf (f
, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a
)->loop_num
);
722 if (ALLOCNO_HARD_REGNO (a
) >= 0)
723 fprintf (f
, " %3d", ALLOCNO_HARD_REGNO (a
));
730 /* Outputs information about allocation of all allocnos into
733 ira_debug_disposition (void)
735 ira_print_disposition (stderr
);
740 /* Set up ira_stack_reg_pressure_class which is the biggest pressure
741 register class containing stack registers or NO_REGS if there are
742 no stack registers. To find this class, we iterate through all
743 register pressure classes and choose the first register pressure
744 class containing all the stack registers and having the biggest
747 setup_stack_reg_pressure_class (void)
749 ira_stack_reg_pressure_class
= NO_REGS
;
754 HARD_REG_SET temp_hard_regset2
;
756 CLEAR_HARD_REG_SET (temp_hard_regset
);
757 for (i
= FIRST_STACK_REG
; i
<= LAST_STACK_REG
; i
++)
758 SET_HARD_REG_BIT (temp_hard_regset
, i
);
760 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
762 cl
= ira_pressure_classes
[i
];
763 COPY_HARD_REG_SET (temp_hard_regset2
, temp_hard_regset
);
764 AND_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl
]);
765 size
= hard_reg_set_size (temp_hard_regset2
);
769 ira_stack_reg_pressure_class
= cl
;
776 /* Find pressure classes which are register classes for which we
777 calculate register pressure in IRA, register pressure sensitive
778 insn scheduling, and register pressure sensitive loop invariant
781 To make register pressure calculation easy, we always use
782 non-intersected register pressure classes. A move of hard
783 registers from one register pressure class is not more expensive
784 than load and store of the hard registers. Most likely an allocno
785 class will be a subset of a register pressure class and in many
786 cases a register pressure class. That makes usage of register
787 pressure classes a good approximation to find a high register
790 setup_pressure_classes (void)
792 int cost
, i
, n
, curr
;
794 enum reg_class pressure_classes
[N_REG_CLASSES
];
796 HARD_REG_SET temp_hard_regset2
;
800 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
802 if (ira_available_class_regs
[cl
] == 0)
804 if (ira_available_class_regs
[cl
] != 1
805 /* A register class without subclasses may contain a few
806 hard registers and movement between them is costly
807 (e.g. SPARC FPCC registers). We still should consider it
808 as a candidate for a pressure class. */
809 && alloc_reg_class_subclasses
[cl
][0] != LIM_REG_CLASSES
)
811 /* Check that the moves between any hard registers of the
812 current class are not more expensive for a legal mode
813 than load/store of the hard registers of the current
814 class. Such class is a potential candidate to be a
815 register pressure class. */
816 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
818 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
819 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
820 AND_COMPL_HARD_REG_SET (temp_hard_regset
,
821 ira_prohibited_class_mode_regs
[cl
][m
]);
822 if (hard_reg_set_empty_p (temp_hard_regset
))
824 ira_init_register_move_cost_if_necessary ((enum machine_mode
) m
);
825 cost
= ira_register_move_cost
[m
][cl
][cl
];
826 if (cost
<= ira_max_memory_move_cost
[m
][cl
][1]
827 || cost
<= ira_max_memory_move_cost
[m
][cl
][0])
830 if (m
>= NUM_MACHINE_MODES
)
835 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
836 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
837 /* Remove so far added pressure classes which are subset of the
838 current candidate class. Prefer GENERAL_REGS as a pressure
839 register class to another class containing the same
840 allocatable hard registers. We do this because machine
841 dependent cost hooks might give wrong costs for the latter
842 class but always give the right cost for the former class
844 for (i
= 0; i
< n
; i
++)
846 cl2
= pressure_classes
[i
];
847 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl2
]);
848 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
849 if (hard_reg_set_subset_p (temp_hard_regset
, temp_hard_regset2
)
850 && (! hard_reg_set_equal_p (temp_hard_regset
, temp_hard_regset2
)
851 || cl2
== (int) GENERAL_REGS
))
853 pressure_classes
[curr
++] = (enum reg_class
) cl2
;
857 if (hard_reg_set_subset_p (temp_hard_regset2
, temp_hard_regset
)
858 && (! hard_reg_set_equal_p (temp_hard_regset2
, temp_hard_regset
)
859 || cl
== (int) GENERAL_REGS
))
861 if (hard_reg_set_equal_p (temp_hard_regset2
, temp_hard_regset
))
863 pressure_classes
[curr
++] = (enum reg_class
) cl2
;
865 /* If the current candidate is a subset of a so far added
866 pressure class, don't add it to the list of the pressure
869 pressure_classes
[curr
++] = (enum reg_class
) cl
;
872 #ifdef ENABLE_IRA_CHECKING
874 HARD_REG_SET ignore_hard_regs
;
876 /* Check pressure classes correctness: here we check that hard
877 registers from all register pressure classes contains all hard
878 registers available for the allocation. */
879 CLEAR_HARD_REG_SET (temp_hard_regset
);
880 CLEAR_HARD_REG_SET (temp_hard_regset2
);
881 COPY_HARD_REG_SET (ignore_hard_regs
, no_unit_alloc_regs
);
882 for (cl
= 0; cl
< LIM_REG_CLASSES
; cl
++)
884 /* For some targets (like MIPS with MD_REGS), there are some
885 classes with hard registers available for allocation but
886 not able to hold value of any mode. */
887 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
888 if (contains_reg_of_mode
[cl
][m
])
890 if (m
>= NUM_MACHINE_MODES
)
892 IOR_HARD_REG_SET (ignore_hard_regs
, reg_class_contents
[cl
]);
895 for (i
= 0; i
< n
; i
++)
896 if ((int) pressure_classes
[i
] == cl
)
898 IOR_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl
]);
900 IOR_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
902 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
903 /* Some targets (like SPARC with ICC reg) have alocatable regs
904 for which no reg class is defined. */
905 if (REGNO_REG_CLASS (i
) == NO_REGS
)
906 SET_HARD_REG_BIT (ignore_hard_regs
, i
);
907 AND_COMPL_HARD_REG_SET (temp_hard_regset
, ignore_hard_regs
);
908 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, ignore_hard_regs
);
909 ira_assert (hard_reg_set_subset_p (temp_hard_regset2
, temp_hard_regset
));
912 ira_pressure_classes_num
= 0;
913 for (i
= 0; i
< n
; i
++)
915 cl
= (int) pressure_classes
[i
];
916 ira_reg_pressure_class_p
[cl
] = true;
917 ira_pressure_classes
[ira_pressure_classes_num
++] = (enum reg_class
) cl
;
919 setup_stack_reg_pressure_class ();
922 /* Set up IRA_ALLOCNO_CLASSES, IRA_ALLOCNO_CLASSES_NUM,
923 IRA_IMPORTANT_CLASSES, and IRA_IMPORTANT_CLASSES_NUM.
925 Target may have many subtargets and not all target hard regiters can
926 be used for allocation, e.g. x86 port in 32-bit mode can not use
927 hard registers introduced in x86-64 like r8-r15). Some classes
928 might have the same allocatable hard registers, e.g. INDEX_REGS
929 and GENERAL_REGS in x86 port in 32-bit mode. To decrease different
930 calculations efforts we introduce allocno classes which contain
931 unique non-empty sets of allocatable hard-registers.
933 Pseudo class cost calculation in ira-costs.c is very expensive.
934 Therefore we are trying to decrease number of classes involved in
935 such calculation. Register classes used in the cost calculation
936 are called important classes. They are allocno classes and other
937 non-empty classes whose allocatable hard register sets are inside
938 of an allocno class hard register set. From the first sight, it
939 looks like that they are just allocno classes. It is not true. In
940 example of x86-port in 32-bit mode, allocno classes will contain
941 GENERAL_REGS but not LEGACY_REGS (because allocatable hard
942 registers are the same for the both classes). The important
943 classes will contain GENERAL_REGS and LEGACY_REGS. It is done
944 because a machine description insn constraint may refers for
945 LEGACY_REGS and code in ira-costs.c is mostly base on investigation
946 of the insn constraints. */
948 setup_allocno_and_important_classes (void)
952 HARD_REG_SET temp_hard_regset2
;
953 static enum reg_class classes
[LIM_REG_CLASSES
+ 1];
956 /* Collect classes which contain unique sets of allocatable hard
957 registers. Prefer GENERAL_REGS to other classes containing the
958 same set of hard registers. */
959 for (i
= 0; i
< LIM_REG_CLASSES
; i
++)
961 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[i
]);
962 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
963 for (j
= 0; j
< n
; j
++)
966 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl
]);
967 AND_COMPL_HARD_REG_SET (temp_hard_regset2
,
969 if (hard_reg_set_equal_p (temp_hard_regset
,
974 classes
[n
++] = (enum reg_class
) i
;
975 else if (i
== GENERAL_REGS
)
976 /* Prefer general regs. For i386 example, it means that
977 we prefer GENERAL_REGS over INDEX_REGS or LEGACY_REGS
978 (all of them consists of the same available hard
980 classes
[j
] = (enum reg_class
) i
;
982 classes
[n
] = LIM_REG_CLASSES
;
984 /* Set up classes which can be used for allocnos as classes
985 conatining non-empty unique sets of allocatable hard
987 ira_allocno_classes_num
= 0;
988 for (i
= 0; (cl
= classes
[i
]) != LIM_REG_CLASSES
; i
++)
990 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
991 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
992 if (hard_reg_set_empty_p (temp_hard_regset
))
994 ira_allocno_classes
[ira_allocno_classes_num
++] = (enum reg_class
) cl
;
996 ira_important_classes_num
= 0;
997 /* Add non-allocno classes containing to non-empty set of
998 allocatable hard regs. */
999 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1001 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
1002 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1003 if (! hard_reg_set_empty_p (temp_hard_regset
))
1006 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1008 COPY_HARD_REG_SET (temp_hard_regset2
,
1009 reg_class_contents
[ira_allocno_classes
[j
]]);
1010 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
1011 if ((enum reg_class
) cl
== ira_allocno_classes
[j
])
1013 else if (hard_reg_set_subset_p (temp_hard_regset
,
1017 if (set_p
&& j
>= ira_allocno_classes_num
)
1018 ira_important_classes
[ira_important_classes_num
++]
1019 = (enum reg_class
) cl
;
1022 /* Now add allocno classes to the important classes. */
1023 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1024 ira_important_classes
[ira_important_classes_num
++]
1025 = ira_allocno_classes
[j
];
1026 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1028 ira_reg_allocno_class_p
[cl
] = false;
1029 ira_reg_pressure_class_p
[cl
] = false;
1031 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1032 ira_reg_allocno_class_p
[ira_allocno_classes
[j
]] = true;
1033 setup_pressure_classes ();
1036 /* Setup translation in CLASS_TRANSLATE of all classes into a class
1037 given by array CLASSES of length CLASSES_NUM. The function is used
1038 make translation any reg class to an allocno class or to an
1039 pressure class. This translation is necessary for some
1040 calculations when we can use only allocno or pressure classes and
1041 such translation represents an approximate representation of all
1044 The translation in case when allocatable hard register set of a
1045 given class is subset of allocatable hard register set of a class
1046 in CLASSES is pretty simple. We use smallest classes from CLASSES
1047 containing a given class. If allocatable hard register set of a
1048 given class is not a subset of any corresponding set of a class
1049 from CLASSES, we use the cheapest (with load/store point of view)
1050 class from CLASSES whose set intersects with given class set */
1052 setup_class_translate_array (enum reg_class
*class_translate
,
1053 int classes_num
, enum reg_class
*classes
)
1056 enum reg_class aclass
, best_class
, *cl_ptr
;
1057 int i
, cost
, min_cost
, best_cost
;
1059 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1060 class_translate
[cl
] = NO_REGS
;
1062 for (i
= 0; i
< classes_num
; i
++)
1064 aclass
= classes
[i
];
1065 for (cl_ptr
= &alloc_reg_class_subclasses
[aclass
][0];
1066 (cl
= *cl_ptr
) != LIM_REG_CLASSES
;
1068 if (class_translate
[cl
] == NO_REGS
)
1069 class_translate
[cl
] = aclass
;
1070 class_translate
[aclass
] = aclass
;
1072 /* For classes which are not fully covered by one of given classes
1073 (in other words covered by more one given class), use the
1075 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1077 if (cl
== NO_REGS
|| class_translate
[cl
] != NO_REGS
)
1079 best_class
= NO_REGS
;
1080 best_cost
= INT_MAX
;
1081 for (i
= 0; i
< classes_num
; i
++)
1083 aclass
= classes
[i
];
1084 COPY_HARD_REG_SET (temp_hard_regset
,
1085 reg_class_contents
[aclass
]);
1086 AND_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
1087 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1088 if (! hard_reg_set_empty_p (temp_hard_regset
))
1091 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
1093 cost
= (ira_memory_move_cost
[mode
][cl
][0]
1094 + ira_memory_move_cost
[mode
][cl
][1]);
1095 if (min_cost
> cost
)
1098 if (best_class
== NO_REGS
|| best_cost
> min_cost
)
1100 best_class
= aclass
;
1101 best_cost
= min_cost
;
1105 class_translate
[cl
] = best_class
;
1109 /* Set up array IRA_ALLOCNO_CLASS_TRANSLATE and
1110 IRA_PRESSURE_CLASS_TRANSLATE. */
1112 setup_class_translate (void)
1114 setup_class_translate_array (ira_allocno_class_translate
,
1115 ira_allocno_classes_num
, ira_allocno_classes
);
1116 setup_class_translate_array (ira_pressure_class_translate
,
1117 ira_pressure_classes_num
, ira_pressure_classes
);
1120 /* Order numbers of allocno classes in original target allocno class
1121 array, -1 for non-allocno classes. */
1122 static int allocno_class_order
[N_REG_CLASSES
];
1124 /* The function used to sort the important classes. */
1126 comp_reg_classes_func (const void *v1p
, const void *v2p
)
1128 enum reg_class cl1
= *(const enum reg_class
*) v1p
;
1129 enum reg_class cl2
= *(const enum reg_class
*) v2p
;
1130 enum reg_class tcl1
, tcl2
;
1133 tcl1
= ira_allocno_class_translate
[cl1
];
1134 tcl2
= ira_allocno_class_translate
[cl2
];
1135 if (tcl1
!= NO_REGS
&& tcl2
!= NO_REGS
1136 && (diff
= allocno_class_order
[tcl1
] - allocno_class_order
[tcl2
]) != 0)
1138 return (int) cl1
- (int) cl2
;
1141 /* For correct work of function setup_reg_class_relation we need to
1142 reorder important classes according to the order of their allocno
1143 classes. It places important classes containing the same
1144 allocatable hard register set adjacent to each other and allocno
1145 class with the allocatable hard register set right after the other
1146 important classes with the same set.
1148 In example from comments of function
1149 setup_allocno_and_important_classes, it places LEGACY_REGS and
1150 GENERAL_REGS close to each other and GENERAL_REGS is after
1153 reorder_important_classes (void)
1157 for (i
= 0; i
< N_REG_CLASSES
; i
++)
1158 allocno_class_order
[i
] = -1;
1159 for (i
= 0; i
< ira_allocno_classes_num
; i
++)
1160 allocno_class_order
[ira_allocno_classes
[i
]] = i
;
1161 qsort (ira_important_classes
, ira_important_classes_num
,
1162 sizeof (enum reg_class
), comp_reg_classes_func
);
1163 for (i
= 0; i
< ira_important_classes_num
; i
++)
1164 ira_important_class_nums
[ira_important_classes
[i
]] = i
;
1167 /* Set up IRA_REG_CLASS_SUBUNION, IRA_REG_CLASS_SUPERUNION,
1168 IRA_REG_CLASS_SUPER_CLASSES, IRA_REG_CLASSES_INTERSECT, and
1169 IRA_REG_CLASSES_INTERSECT_P. For the meaning of the relations,
1170 please see corresponding comments in ira-int.h. */
1172 setup_reg_class_relations (void)
1174 int i
, cl1
, cl2
, cl3
;
1175 HARD_REG_SET intersection_set
, union_set
, temp_set2
;
1176 bool important_class_p
[N_REG_CLASSES
];
1178 memset (important_class_p
, 0, sizeof (important_class_p
));
1179 for (i
= 0; i
< ira_important_classes_num
; i
++)
1180 important_class_p
[ira_important_classes
[i
]] = true;
1181 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1183 ira_reg_class_super_classes
[cl1
][0] = LIM_REG_CLASSES
;
1184 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1186 ira_reg_classes_intersect_p
[cl1
][cl2
] = false;
1187 ira_reg_class_intersect
[cl1
][cl2
] = NO_REGS
;
1188 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl1
]);
1189 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1190 COPY_HARD_REG_SET (temp_set2
, reg_class_contents
[cl2
]);
1191 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1192 if (hard_reg_set_empty_p (temp_hard_regset
)
1193 && hard_reg_set_empty_p (temp_set2
))
1195 /* The both classes have no allocatable hard registers
1196 -- take all class hard registers into account and use
1197 reg_class_subunion and reg_class_superunion. */
1200 cl3
= reg_class_subclasses
[cl1
][i
];
1201 if (cl3
== LIM_REG_CLASSES
)
1203 if (reg_class_subset_p (ira_reg_class_intersect
[cl1
][cl2
],
1204 (enum reg_class
) cl3
))
1205 ira_reg_class_intersect
[cl1
][cl2
] = (enum reg_class
) cl3
;
1207 ira_reg_class_subunion
[cl1
][cl2
] = reg_class_subunion
[cl1
][cl2
];
1208 ira_reg_class_superunion
[cl1
][cl2
] = reg_class_superunion
[cl1
][cl2
];
1211 ira_reg_classes_intersect_p
[cl1
][cl2
]
1212 = hard_reg_set_intersect_p (temp_hard_regset
, temp_set2
);
1213 if (important_class_p
[cl1
] && important_class_p
[cl2
]
1214 && hard_reg_set_subset_p (temp_hard_regset
, temp_set2
))
1216 /* CL1 and CL2 are important classes and CL1 allocatable
1217 hard register set is inside of CL2 allocatable hard
1218 registers -- make CL1 a superset of CL2. */
1221 p
= &ira_reg_class_super_classes
[cl1
][0];
1222 while (*p
!= LIM_REG_CLASSES
)
1224 *p
++ = (enum reg_class
) cl2
;
1225 *p
= LIM_REG_CLASSES
;
1227 ira_reg_class_subunion
[cl1
][cl2
] = NO_REGS
;
1228 ira_reg_class_superunion
[cl1
][cl2
] = NO_REGS
;
1229 COPY_HARD_REG_SET (intersection_set
, reg_class_contents
[cl1
]);
1230 AND_HARD_REG_SET (intersection_set
, reg_class_contents
[cl2
]);
1231 AND_COMPL_HARD_REG_SET (intersection_set
, no_unit_alloc_regs
);
1232 COPY_HARD_REG_SET (union_set
, reg_class_contents
[cl1
]);
1233 IOR_HARD_REG_SET (union_set
, reg_class_contents
[cl2
]);
1234 AND_COMPL_HARD_REG_SET (union_set
, no_unit_alloc_regs
);
1235 for (i
= 0; i
< ira_important_classes_num
; i
++)
1237 cl3
= ira_important_classes
[i
];
1238 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl3
]);
1239 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1240 if (hard_reg_set_subset_p (temp_hard_regset
, intersection_set
))
1242 /* CL3 allocatable hard register set is inside of
1243 intersection of allocatable hard register sets
1247 reg_class_contents
[(int)
1248 ira_reg_class_intersect
[cl1
][cl2
]]);
1249 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1250 if (! hard_reg_set_subset_p (temp_hard_regset
, temp_set2
)
1251 /* If the allocatable hard register sets are the
1252 same, prefer GENERAL_REGS or the smallest
1253 class for debugging purposes. */
1254 || (hard_reg_set_equal_p (temp_hard_regset
, temp_set2
)
1255 && (cl3
== GENERAL_REGS
1256 || (ira_reg_class_intersect
[cl1
][cl2
] != GENERAL_REGS
1257 && hard_reg_set_subset_p
1258 (reg_class_contents
[cl3
],
1260 [(int) ira_reg_class_intersect
[cl1
][cl2
]])))))
1261 ira_reg_class_intersect
[cl1
][cl2
] = (enum reg_class
) cl3
;
1263 if (hard_reg_set_subset_p (temp_hard_regset
, union_set
))
1265 /* CL3 allocatbale hard register set is inside of
1266 union of allocatable hard register sets of CL1
1270 reg_class_contents
[(int) ira_reg_class_subunion
[cl1
][cl2
]]);
1271 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1272 if (ira_reg_class_subunion
[cl1
][cl2
] == NO_REGS
1273 || (hard_reg_set_subset_p (temp_set2
, temp_hard_regset
)
1275 && (! hard_reg_set_equal_p (temp_set2
,
1277 || cl3
== GENERAL_REGS
1278 /* If the allocatable hard register sets are the
1279 same, prefer GENERAL_REGS or the smallest
1280 class for debugging purposes. */
1281 || (ira_reg_class_subunion
[cl1
][cl2
] != GENERAL_REGS
1282 && hard_reg_set_subset_p
1283 (reg_class_contents
[cl3
],
1285 [(int) ira_reg_class_subunion
[cl1
][cl2
]])))))
1286 ira_reg_class_subunion
[cl1
][cl2
] = (enum reg_class
) cl3
;
1288 if (hard_reg_set_subset_p (union_set
, temp_hard_regset
))
1290 /* CL3 allocatable hard register set contains union
1291 of allocatable hard register sets of CL1 and
1295 reg_class_contents
[(int) ira_reg_class_superunion
[cl1
][cl2
]]);
1296 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1297 if (ira_reg_class_superunion
[cl1
][cl2
] == NO_REGS
1298 || (hard_reg_set_subset_p (temp_hard_regset
, temp_set2
)
1300 && (! hard_reg_set_equal_p (temp_set2
,
1302 || cl3
== GENERAL_REGS
1303 /* If the allocatable hard register sets are the
1304 same, prefer GENERAL_REGS or the smallest
1305 class for debugging purposes. */
1306 || (ira_reg_class_superunion
[cl1
][cl2
] != GENERAL_REGS
1307 && hard_reg_set_subset_p
1308 (reg_class_contents
[cl3
],
1310 [(int) ira_reg_class_superunion
[cl1
][cl2
]])))))
1311 ira_reg_class_superunion
[cl1
][cl2
] = (enum reg_class
) cl3
;
1318 /* Output all possible allocno classes and the translation map into
1321 print_classes (FILE *f
, bool pressure_p
)
1323 int classes_num
= (pressure_p
1324 ? ira_pressure_classes_num
: ira_allocno_classes_num
);
1325 enum reg_class
*classes
= (pressure_p
1326 ? ira_pressure_classes
: ira_allocno_classes
);
1327 enum reg_class
*class_translate
= (pressure_p
1328 ? ira_pressure_class_translate
1329 : ira_allocno_class_translate
);
1330 static const char *const reg_class_names
[] = REG_CLASS_NAMES
;
1333 fprintf (f
, "%s classes:\n", pressure_p
? "Pressure" : "Allocno");
1334 for (i
= 0; i
< classes_num
; i
++)
1335 fprintf (f
, " %s", reg_class_names
[classes
[i
]]);
1336 fprintf (f
, "\nClass translation:\n");
1337 for (i
= 0; i
< N_REG_CLASSES
; i
++)
1338 fprintf (f
, " %s -> %s\n", reg_class_names
[i
],
1339 reg_class_names
[class_translate
[i
]]);
1342 /* Output all possible allocno and translation classes and the
1343 translation maps into stderr. */
1345 ira_debug_allocno_classes (void)
1347 print_classes (stderr
, false);
1348 print_classes (stderr
, true);
1351 /* Set up different arrays concerning class subsets, allocno and
1352 important classes. */
1354 find_reg_classes (void)
1356 setup_allocno_and_important_classes ();
1357 setup_class_translate ();
1358 reorder_important_classes ();
1359 setup_reg_class_relations ();
1364 /* Set up the array above. */
1366 setup_hard_regno_aclass (void)
1370 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1373 ira_hard_regno_allocno_class
[i
]
1374 = (TEST_HARD_REG_BIT (no_unit_alloc_regs
, i
)
1376 : ira_allocno_class_translate
[REGNO_REG_CLASS (i
)]);
1380 ira_hard_regno_allocno_class
[i
] = NO_REGS
;
1381 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1383 cl
= ira_allocno_classes
[j
];
1384 if (ira_class_hard_reg_index
[cl
][i
] >= 0)
1386 ira_hard_regno_allocno_class
[i
] = cl
;
1396 /* Form IRA_REG_CLASS_MAX_NREGS and IRA_REG_CLASS_MIN_NREGS maps. */
1398 setup_reg_class_nregs (void)
1402 for (m
= 0; m
< MAX_MACHINE_MODE
; m
++)
1404 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1405 ira_reg_class_max_nregs
[cl
][m
]
1406 = ira_reg_class_min_nregs
[cl
][m
]
1407 = targetm
.class_max_nregs ((reg_class_t
) cl
, (enum machine_mode
) m
);
1408 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1410 (cl2
= alloc_reg_class_subclasses
[cl
][i
]) != LIM_REG_CLASSES
;
1412 if (ira_reg_class_min_nregs
[cl2
][m
]
1413 < ira_reg_class_min_nregs
[cl
][m
])
1414 ira_reg_class_min_nregs
[cl
][m
] = ira_reg_class_min_nregs
[cl2
][m
];
1420 /* Set up IRA_PROHIBITED_CLASS_MODE_REGS. */
1422 setup_prohibited_class_mode_regs (void)
1424 int j
, k
, hard_regno
, cl
;
1426 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
1428 for (j
= 0; j
< NUM_MACHINE_MODES
; j
++)
1430 CLEAR_HARD_REG_SET (ira_prohibited_class_mode_regs
[cl
][j
]);
1431 for (k
= ira_class_hard_regs_num
[cl
] - 1; k
>= 0; k
--)
1433 hard_regno
= ira_class_hard_regs
[cl
][k
];
1434 if (! HARD_REGNO_MODE_OK (hard_regno
, (enum machine_mode
) j
))
1435 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1442 /* Clarify IRA_PROHIBITED_CLASS_MODE_REGS by excluding hard registers
1443 spanning from one register pressure class to another one. It is
1444 called after defining the pressure classes. */
1446 clarify_prohibited_class_mode_regs (void)
1448 int j
, k
, hard_regno
, cl
, pclass
, nregs
;
1450 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
1451 for (j
= 0; j
< NUM_MACHINE_MODES
; j
++)
1452 for (k
= ira_class_hard_regs_num
[cl
] - 1; k
>= 0; k
--)
1454 hard_regno
= ira_class_hard_regs
[cl
][k
];
1455 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
], hard_regno
))
1457 nregs
= hard_regno_nregs
[hard_regno
][j
];
1458 if (hard_regno
+ nregs
> FIRST_PSEUDO_REGISTER
)
1460 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1464 pclass
= ira_pressure_class_translate
[REGNO_REG_CLASS (hard_regno
)];
1465 for (nregs
-- ;nregs
>= 0; nregs
--)
1466 if (((enum reg_class
) pclass
1467 != ira_pressure_class_translate
[REGNO_REG_CLASS
1468 (hard_regno
+ nregs
)]))
1470 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1479 /* Allocate and initialize IRA_REGISTER_MOVE_COST,
1480 IRA_MAX_REGISTER_MOVE_COST, IRA_MAY_MOVE_IN_COST,
1481 IRA_MAY_MOVE_OUT_COST, IRA_MAX_MAY_MOVE_IN_COST, and
1482 IRA_MAX_MAY_MOVE_OUT_COST for MODE if it is not done yet. */
1484 ira_init_register_move_cost (enum machine_mode mode
)
1488 ira_assert (ira_register_move_cost
[mode
] == NULL
1489 && ira_max_register_move_cost
[mode
] == NULL
1490 && ira_may_move_in_cost
[mode
] == NULL
1491 && ira_may_move_out_cost
[mode
] == NULL
1492 && ira_max_may_move_in_cost
[mode
] == NULL
1493 && ira_max_may_move_out_cost
[mode
] == NULL
);
1494 if (move_cost
[mode
] == NULL
)
1495 init_move_cost (mode
);
1496 ira_register_move_cost
[mode
] = move_cost
[mode
];
1497 /* Don't use ira_allocate because the tables exist out of scope of a
1499 ira_max_register_move_cost
[mode
]
1500 = (move_table
*) xmalloc (sizeof (move_table
) * N_REG_CLASSES
);
1501 memcpy (ira_max_register_move_cost
[mode
], ira_register_move_cost
[mode
],
1502 sizeof (move_table
) * N_REG_CLASSES
);
1503 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1505 /* Some subclasses are to small to have enough registers to hold
1506 a value of MODE. Just ignore them. */
1507 if (ira_reg_class_max_nregs
[cl1
][mode
] > ira_available_class_regs
[cl1
])
1509 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl1
]);
1510 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1511 if (hard_reg_set_empty_p (temp_hard_regset
))
1513 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1514 if (hard_reg_set_subset_p (reg_class_contents
[cl1
],
1515 reg_class_contents
[cl2
]))
1516 for (cl3
= 0; cl3
< N_REG_CLASSES
; cl3
++)
1518 if (ira_max_register_move_cost
[mode
][cl2
][cl3
]
1519 < ira_register_move_cost
[mode
][cl1
][cl3
])
1520 ira_max_register_move_cost
[mode
][cl2
][cl3
]
1521 = ira_register_move_cost
[mode
][cl1
][cl3
];
1522 if (ira_max_register_move_cost
[mode
][cl3
][cl2
]
1523 < ira_register_move_cost
[mode
][cl3
][cl1
])
1524 ira_max_register_move_cost
[mode
][cl3
][cl2
]
1525 = ira_register_move_cost
[mode
][cl3
][cl1
];
1528 ira_may_move_in_cost
[mode
]
1529 = (move_table
*) xmalloc (sizeof (move_table
) * N_REG_CLASSES
);
1530 memcpy (ira_may_move_in_cost
[mode
], may_move_in_cost
[mode
],
1531 sizeof (move_table
) * N_REG_CLASSES
);
1532 ira_may_move_out_cost
[mode
]
1533 = (move_table
*) xmalloc (sizeof (move_table
) * N_REG_CLASSES
);
1534 memcpy (ira_may_move_out_cost
[mode
], may_move_out_cost
[mode
],
1535 sizeof (move_table
) * N_REG_CLASSES
);
1536 ira_max_may_move_in_cost
[mode
]
1537 = (move_table
*) xmalloc (sizeof (move_table
) * N_REG_CLASSES
);
1538 memcpy (ira_max_may_move_in_cost
[mode
], ira_max_register_move_cost
[mode
],
1539 sizeof (move_table
) * N_REG_CLASSES
);
1540 ira_max_may_move_out_cost
[mode
]
1541 = (move_table
*) xmalloc (sizeof (move_table
) * N_REG_CLASSES
);
1542 memcpy (ira_max_may_move_out_cost
[mode
], ira_max_register_move_cost
[mode
],
1543 sizeof (move_table
) * N_REG_CLASSES
);
1544 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1546 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1548 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl2
]);
1549 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1550 if (hard_reg_set_empty_p (temp_hard_regset
))
1552 if (ira_class_subset_p
[cl1
][cl2
])
1553 ira_may_move_in_cost
[mode
][cl1
][cl2
] = 0;
1554 if (ira_class_subset_p
[cl2
][cl1
])
1555 ira_may_move_out_cost
[mode
][cl1
][cl2
] = 0;
1556 if (ira_class_subset_p
[cl1
][cl2
])
1557 ira_max_may_move_in_cost
[mode
][cl1
][cl2
] = 0;
1558 if (ira_class_subset_p
[cl2
][cl1
])
1559 ira_max_may_move_out_cost
[mode
][cl1
][cl2
] = 0;
1560 ira_register_move_cost
[mode
][cl1
][cl2
]
1561 = ira_max_register_move_cost
[mode
][cl1
][cl2
];
1562 ira_may_move_in_cost
[mode
][cl1
][cl2
]
1563 = ira_max_may_move_in_cost
[mode
][cl1
][cl2
];
1564 ira_may_move_out_cost
[mode
][cl1
][cl2
]
1565 = ira_max_may_move_out_cost
[mode
][cl1
][cl2
];
1572 /* This is called once during compiler work. It sets up
1573 different arrays whose values don't depend on the compiled
1576 ira_init_once (void)
1580 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
1582 ira_register_move_cost
[mode
] = NULL
;
1583 ira_max_register_move_cost
[mode
] = NULL
;
1584 ira_may_move_in_cost
[mode
] = NULL
;
1585 ira_may_move_out_cost
[mode
] = NULL
;
1586 ira_max_may_move_in_cost
[mode
] = NULL
;
1587 ira_max_may_move_out_cost
[mode
] = NULL
;
1589 ira_init_costs_once ();
1592 /* Free ira_max_register_move_cost, ira_may_move_in_cost,
1593 ira_may_move_out_cost, ira_max_may_move_in_cost, and
1594 ira_max_may_move_out_cost for each mode. */
1596 free_register_move_costs (void)
1600 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
1602 free (ira_max_register_move_cost
[mode
]);
1603 free (ira_may_move_in_cost
[mode
]);
1604 free (ira_may_move_out_cost
[mode
]);
1605 free (ira_max_may_move_in_cost
[mode
]);
1606 free (ira_max_may_move_out_cost
[mode
]);
1607 ira_register_move_cost
[mode
] = NULL
;
1608 ira_max_register_move_cost
[mode
] = NULL
;
1609 ira_may_move_in_cost
[mode
] = NULL
;
1610 ira_may_move_out_cost
[mode
] = NULL
;
1611 ira_max_may_move_in_cost
[mode
] = NULL
;
1612 ira_max_may_move_out_cost
[mode
] = NULL
;
1616 /* This is called every time when register related information is
1621 free_register_move_costs ();
1622 setup_reg_mode_hard_regset ();
1623 setup_alloc_regs (flag_omit_frame_pointer
!= 0);
1624 setup_class_subset_and_memory_move_costs ();
1625 setup_reg_class_nregs ();
1626 setup_prohibited_class_mode_regs ();
1627 find_reg_classes ();
1628 clarify_prohibited_class_mode_regs ();
1629 setup_hard_regno_aclass ();
1633 /* Function called once at the end of compiler work. */
1635 ira_finish_once (void)
1637 ira_finish_costs_once ();
1638 free_register_move_costs ();
1642 #define ira_prohibited_mode_move_regs_initialized_p \
1643 (this_target_ira_int->x_ira_prohibited_mode_move_regs_initialized_p)
1645 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS. */
1647 setup_prohibited_mode_move_regs (void)
1650 rtx test_reg1
, test_reg2
, move_pat
, move_insn
;
1652 if (ira_prohibited_mode_move_regs_initialized_p
)
1654 ira_prohibited_mode_move_regs_initialized_p
= true;
1655 test_reg1
= gen_rtx_REG (VOIDmode
, 0);
1656 test_reg2
= gen_rtx_REG (VOIDmode
, 0);
1657 move_pat
= gen_rtx_SET (VOIDmode
, test_reg1
, test_reg2
);
1658 move_insn
= gen_rtx_INSN (VOIDmode
, 0, 0, 0, 0, move_pat
, 0, -1, 0);
1659 for (i
= 0; i
< NUM_MACHINE_MODES
; i
++)
1661 SET_HARD_REG_SET (ira_prohibited_mode_move_regs
[i
]);
1662 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1664 if (! HARD_REGNO_MODE_OK (j
, (enum machine_mode
) i
))
1666 SET_REGNO_RAW (test_reg1
, j
);
1667 PUT_MODE (test_reg1
, (enum machine_mode
) i
);
1668 SET_REGNO_RAW (test_reg2
, j
);
1669 PUT_MODE (test_reg2
, (enum machine_mode
) i
);
1670 INSN_CODE (move_insn
) = -1;
1671 recog_memoized (move_insn
);
1672 if (INSN_CODE (move_insn
) < 0)
1674 extract_insn (move_insn
);
1675 if (! constrain_operands (1))
1677 CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs
[i
], j
);
1684 /* Return nonzero if REGNO is a particularly bad choice for reloading X. */
1686 ira_bad_reload_regno_1 (int regno
, rtx x
)
1690 enum reg_class pref
;
1692 /* We only deal with pseudo regs. */
1693 if (! x
|| GET_CODE (x
) != REG
)
1696 x_regno
= REGNO (x
);
1697 if (x_regno
< FIRST_PSEUDO_REGISTER
)
1700 /* If the pseudo prefers REGNO explicitly, then do not consider
1701 REGNO a bad spill choice. */
1702 pref
= reg_preferred_class (x_regno
);
1703 if (reg_class_size
[pref
] == 1)
1704 return !TEST_HARD_REG_BIT (reg_class_contents
[pref
], regno
);
1706 /* If the pseudo conflicts with REGNO, then we consider REGNO a
1707 poor choice for a reload regno. */
1708 a
= ira_regno_allocno_map
[x_regno
];
1709 n
= ALLOCNO_NUM_OBJECTS (a
);
1710 for (i
= 0; i
< n
; i
++)
1712 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
1713 if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), regno
))
1719 /* Return nonzero if REGNO is a particularly bad choice for reloading
1722 ira_bad_reload_regno (int regno
, rtx in
, rtx out
)
1724 return (ira_bad_reload_regno_1 (regno
, in
)
1725 || ira_bad_reload_regno_1 (regno
, out
));
1728 /* Return TRUE if *LOC contains an asm. */
1730 insn_contains_asm_1 (rtx
*loc
, void *data ATTRIBUTE_UNUSED
)
1734 if (GET_CODE (*loc
) == ASM_OPERANDS
)
1740 /* Return TRUE if INSN contains an ASM. */
1742 insn_contains_asm (rtx insn
)
1744 return for_each_rtx (&insn
, insn_contains_asm_1
, NULL
);
1747 /* Add register clobbers from asm statements. */
1749 compute_regs_asm_clobbered (void)
1756 FOR_BB_INSNS_REVERSE (bb
, insn
)
1760 if (insn_contains_asm (insn
))
1761 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
1763 df_ref def
= *def_rec
;
1764 unsigned int dregno
= DF_REF_REGNO (def
);
1765 if (HARD_REGISTER_NUM_P (dregno
))
1766 add_to_hard_reg_set (&crtl
->asm_clobbers
,
1767 GET_MODE (DF_REF_REAL_REG (def
)),
1775 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and REGS_EVER_LIVE. */
1777 ira_setup_eliminable_regset (void)
1779 #ifdef ELIMINABLE_REGS
1781 static const struct {const int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
1783 /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
1784 sp for alloca. So we can't eliminate the frame pointer in that
1785 case. At some point, we should improve this by emitting the
1786 sp-adjusting insns for this case. */
1788 = (! flag_omit_frame_pointer
1789 || (cfun
->calls_alloca
&& EXIT_IGNORE_STACK
)
1790 /* We need the frame pointer to catch stack overflow exceptions
1791 if the stack pointer is moving. */
1792 || (flag_stack_check
&& STACK_CHECK_MOVING_SP
)
1793 || crtl
->accesses_prior_frames
1794 || crtl
->stack_realign_needed
1795 || targetm
.frame_pointer_required ());
1797 frame_pointer_needed
= need_fp
;
1799 COPY_HARD_REG_SET (ira_no_alloc_regs
, no_unit_alloc_regs
);
1800 CLEAR_HARD_REG_SET (eliminable_regset
);
1802 compute_regs_asm_clobbered ();
1804 /* Build the regset of all eliminable registers and show we can't
1805 use those that we already know won't be eliminated. */
1806 #ifdef ELIMINABLE_REGS
1807 for (i
= 0; i
< (int) ARRAY_SIZE (eliminables
); i
++)
1810 = (! targetm
.can_eliminate (eliminables
[i
].from
, eliminables
[i
].to
)
1811 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& need_fp
));
1813 if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
, eliminables
[i
].from
))
1815 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
1818 SET_HARD_REG_BIT (ira_no_alloc_regs
, eliminables
[i
].from
);
1820 else if (cannot_elim
)
1821 error ("%s cannot be used in asm here",
1822 reg_names
[eliminables
[i
].from
]);
1824 df_set_regs_ever_live (eliminables
[i
].from
, true);
1826 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
1827 if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
, HARD_FRAME_POINTER_REGNUM
))
1829 SET_HARD_REG_BIT (eliminable_regset
, HARD_FRAME_POINTER_REGNUM
);
1831 SET_HARD_REG_BIT (ira_no_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
1834 error ("%s cannot be used in asm here",
1835 reg_names
[HARD_FRAME_POINTER_REGNUM
]);
1837 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM
, true);
1841 if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
, HARD_FRAME_POINTER_REGNUM
))
1843 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
1845 SET_HARD_REG_BIT (ira_no_alloc_regs
, FRAME_POINTER_REGNUM
);
1848 error ("%s cannot be used in asm here", reg_names
[FRAME_POINTER_REGNUM
]);
1850 df_set_regs_ever_live (FRAME_POINTER_REGNUM
, true);
1856 /* The length of the following two arrays. */
1857 int ira_reg_equiv_len
;
1859 /* The element value is TRUE if the corresponding regno value is
1861 bool *ira_reg_equiv_invariant_p
;
1863 /* The element value is equiv constant of given pseudo-register or
1865 rtx
*ira_reg_equiv_const
;
1867 /* Set up the two arrays declared above. */
1869 find_reg_equiv_invariant_const (void)
1873 rtx list
, insn
, note
, constant
, x
;
1875 for (i
= FIRST_PSEUDO_REGISTER
; i
< VEC_length (reg_equivs_t
, reg_equivs
); i
++)
1877 constant
= NULL_RTX
;
1878 invariant_p
= false;
1879 for (list
= reg_equiv_init (i
); list
!= NULL_RTX
; list
= XEXP (list
, 1))
1881 insn
= XEXP (list
, 0);
1882 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
1884 if (note
== NULL_RTX
)
1889 if (! CONSTANT_P (x
)
1890 || ! flag_pic
|| LEGITIMATE_PIC_OPERAND_P (x
))
1892 /* It can happen that a REG_EQUIV note contains a MEM
1893 that is not a legitimate memory operand. As later
1894 stages of the reload assume that all addresses found
1895 in the reg_equiv_* arrays were originally legitimate,
1896 we ignore such REG_EQUIV notes. */
1897 if (memory_operand (x
, VOIDmode
))
1898 invariant_p
= MEM_READONLY_P (x
);
1899 else if (function_invariant_p (x
))
1901 if (GET_CODE (x
) == PLUS
1902 || x
== frame_pointer_rtx
|| x
== arg_pointer_rtx
)
1909 ira_reg_equiv_invariant_p
[i
] = invariant_p
;
1910 ira_reg_equiv_const
[i
] = constant
;
1916 /* Vector of substitutions of register numbers,
1917 used to map pseudo regs into hardware regs.
1918 This is set up as a result of register allocation.
1919 Element N is the hard reg assigned to pseudo reg N,
1920 or is -1 if no hard reg was assigned.
1921 If N is a hard reg number, element N is N. */
1922 short *reg_renumber
;
1924 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
1925 the allocation found by IRA. */
1927 setup_reg_renumber (void)
1929 int regno
, hard_regno
;
1931 ira_allocno_iterator ai
;
1933 caller_save_needed
= 0;
1934 FOR_EACH_ALLOCNO (a
, ai
)
1936 /* There are no caps at this point. */
1937 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
1938 if (! ALLOCNO_ASSIGNED_P (a
))
1939 /* It can happen if A is not referenced but partially anticipated
1940 somewhere in a region. */
1941 ALLOCNO_ASSIGNED_P (a
) = true;
1942 ira_free_allocno_updated_costs (a
);
1943 hard_regno
= ALLOCNO_HARD_REGNO (a
);
1944 regno
= ALLOCNO_REGNO (a
);
1945 reg_renumber
[regno
] = (hard_regno
< 0 ? -1 : hard_regno
);
1946 if (hard_regno
>= 0)
1949 enum reg_class pclass
;
1952 pclass
= ira_pressure_class_translate
[REGNO_REG_CLASS (hard_regno
)];
1953 nwords
= ALLOCNO_NUM_OBJECTS (a
);
1954 for (i
= 0; i
< nwords
; i
++)
1956 obj
= ALLOCNO_OBJECT (a
, i
);
1957 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
1958 reg_class_contents
[pclass
]);
1960 if (ALLOCNO_CALLS_CROSSED_NUM (a
) != 0
1961 && ira_hard_reg_set_intersection_p (hard_regno
, ALLOCNO_MODE (a
),
1964 ira_assert (!optimize
|| flag_caller_saves
1965 || (ALLOCNO_CALLS_CROSSED_NUM (a
)
1966 == ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
))
1967 || regno
>= ira_reg_equiv_len
1968 || ira_reg_equiv_const
[regno
]
1969 || ira_reg_equiv_invariant_p
[regno
]);
1970 caller_save_needed
= 1;
1976 /* Set up allocno assignment flags for further allocation
1979 setup_allocno_assignment_flags (void)
1983 ira_allocno_iterator ai
;
1985 FOR_EACH_ALLOCNO (a
, ai
)
1987 if (! ALLOCNO_ASSIGNED_P (a
))
1988 /* It can happen if A is not referenced but partially anticipated
1989 somewhere in a region. */
1990 ira_free_allocno_updated_costs (a
);
1991 hard_regno
= ALLOCNO_HARD_REGNO (a
);
1992 /* Don't assign hard registers to allocnos which are destination
1993 of removed store at the end of loop. It has no sense to keep
1994 the same value in different hard registers. It is also
1995 impossible to assign hard registers correctly to such
1996 allocnos because the cost info and info about intersected
1997 calls are incorrect for them. */
1998 ALLOCNO_ASSIGNED_P (a
) = (hard_regno
>= 0
1999 || ALLOCNO_EMIT_DATA (a
)->mem_optimized_dest_p
2000 || (ALLOCNO_MEMORY_COST (a
)
2001 - ALLOCNO_CLASS_COST (a
)) < 0);
2004 || ira_hard_reg_in_set_p (hard_regno
, ALLOCNO_MODE (a
),
2005 reg_class_contents
[ALLOCNO_CLASS (a
)]));
2009 /* Evaluate overall allocation cost and the costs for using hard
2010 registers and memory for allocnos. */
2012 calculate_allocation_cost (void)
2014 int hard_regno
, cost
;
2016 ira_allocno_iterator ai
;
2018 ira_overall_cost
= ira_reg_cost
= ira_mem_cost
= 0;
2019 FOR_EACH_ALLOCNO (a
, ai
)
2021 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2022 ira_assert (hard_regno
< 0
2023 || (ira_hard_reg_in_set_p
2024 (hard_regno
, ALLOCNO_MODE (a
),
2025 reg_class_contents
[ALLOCNO_CLASS (a
)])));
2028 cost
= ALLOCNO_MEMORY_COST (a
);
2029 ira_mem_cost
+= cost
;
2031 else if (ALLOCNO_HARD_REG_COSTS (a
) != NULL
)
2033 cost
= (ALLOCNO_HARD_REG_COSTS (a
)
2034 [ira_class_hard_reg_index
2035 [ALLOCNO_CLASS (a
)][hard_regno
]]);
2036 ira_reg_cost
+= cost
;
2040 cost
= ALLOCNO_CLASS_COST (a
);
2041 ira_reg_cost
+= cost
;
2043 ira_overall_cost
+= cost
;
2046 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
2048 fprintf (ira_dump_file
,
2049 "+++Costs: overall %d, reg %d, mem %d, ld %d, st %d, move %d\n",
2050 ira_overall_cost
, ira_reg_cost
, ira_mem_cost
,
2051 ira_load_cost
, ira_store_cost
, ira_shuffle_cost
);
2052 fprintf (ira_dump_file
, "+++ move loops %d, new jumps %d\n",
2053 ira_move_loops_num
, ira_additional_jumps_num
);
2058 #ifdef ENABLE_IRA_CHECKING
2059 /* Check the correctness of the allocation. We do need this because
2060 of complicated code to transform more one region internal
2061 representation into one region representation. */
2063 check_allocation (void)
2066 int hard_regno
, nregs
, conflict_nregs
;
2067 ira_allocno_iterator ai
;
2069 FOR_EACH_ALLOCNO (a
, ai
)
2071 int n
= ALLOCNO_NUM_OBJECTS (a
);
2074 if (ALLOCNO_CAP_MEMBER (a
) != NULL
2075 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0)
2077 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (a
)];
2079 /* We allocated a single hard register. */
2082 /* We allocated multiple hard registers, and we will test
2083 conflicts in a granularity of single hard regs. */
2086 for (i
= 0; i
< n
; i
++)
2088 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2089 ira_object_t conflict_obj
;
2090 ira_object_conflict_iterator oci
;
2091 int this_regno
= hard_regno
;
2094 if (REG_WORDS_BIG_ENDIAN
)
2095 this_regno
+= n
- i
- 1;
2099 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2101 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2102 int conflict_hard_regno
= ALLOCNO_HARD_REGNO (conflict_a
);
2103 if (conflict_hard_regno
< 0)
2108 [conflict_hard_regno
][ALLOCNO_MODE (conflict_a
)]);
2110 if (ALLOCNO_NUM_OBJECTS (conflict_a
) > 1
2111 && conflict_nregs
== ALLOCNO_NUM_OBJECTS (conflict_a
))
2113 if (REG_WORDS_BIG_ENDIAN
)
2114 conflict_hard_regno
+= (ALLOCNO_NUM_OBJECTS (conflict_a
)
2115 - OBJECT_SUBWORD (conflict_obj
) - 1);
2117 conflict_hard_regno
+= OBJECT_SUBWORD (conflict_obj
);
2121 if ((conflict_hard_regno
<= this_regno
2122 && this_regno
< conflict_hard_regno
+ conflict_nregs
)
2123 || (this_regno
<= conflict_hard_regno
2124 && conflict_hard_regno
< this_regno
+ nregs
))
2126 fprintf (stderr
, "bad allocation for %d and %d\n",
2127 ALLOCNO_REGNO (a
), ALLOCNO_REGNO (conflict_a
));
2136 /* Fix values of array REG_EQUIV_INIT after live range splitting done
2139 fix_reg_equiv_init (void)
2141 unsigned int max_regno
= max_reg_num ();
2142 int i
, new_regno
, max
;
2143 rtx x
, prev
, next
, insn
, set
;
2145 if (VEC_length (reg_equivs_t
, reg_equivs
) < max_regno
)
2147 max
= VEC_length (reg_equivs_t
, reg_equivs
);
2149 for (i
= FIRST_PSEUDO_REGISTER
; i
< max
; i
++)
2150 for (prev
= NULL_RTX
, x
= reg_equiv_init (i
);
2156 set
= single_set (insn
);
2157 ira_assert (set
!= NULL_RTX
2158 && (REG_P (SET_DEST (set
)) || REG_P (SET_SRC (set
))));
2159 if (REG_P (SET_DEST (set
))
2160 && ((int) REGNO (SET_DEST (set
)) == i
2161 || (int) ORIGINAL_REGNO (SET_DEST (set
)) == i
))
2162 new_regno
= REGNO (SET_DEST (set
));
2163 else if (REG_P (SET_SRC (set
))
2164 && ((int) REGNO (SET_SRC (set
)) == i
2165 || (int) ORIGINAL_REGNO (SET_SRC (set
)) == i
))
2166 new_regno
= REGNO (SET_SRC (set
));
2173 if (prev
== NULL_RTX
)
2174 reg_equiv_init (i
) = next
;
2176 XEXP (prev
, 1) = next
;
2177 XEXP (x
, 1) = reg_equiv_init (new_regno
);
2178 reg_equiv_init (new_regno
) = x
;
2184 #ifdef ENABLE_IRA_CHECKING
2185 /* Print redundant memory-memory copies. */
2187 print_redundant_copies (void)
2191 ira_copy_t cp
, next_cp
;
2192 ira_allocno_iterator ai
;
2194 FOR_EACH_ALLOCNO (a
, ai
)
2196 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2199 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2200 if (hard_regno
>= 0)
2202 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2204 next_cp
= cp
->next_first_allocno_copy
;
2207 next_cp
= cp
->next_second_allocno_copy
;
2208 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
2209 && cp
->insn
!= NULL_RTX
2210 && ALLOCNO_HARD_REGNO (cp
->first
) == hard_regno
)
2211 fprintf (ira_dump_file
,
2212 " Redundant move from %d(freq %d):%d\n",
2213 INSN_UID (cp
->insn
), cp
->freq
, hard_regno
);
2219 /* Setup preferred and alternative classes for new pseudo-registers
2220 created by IRA starting with START. */
2222 setup_preferred_alternate_classes_for_new_pseudos (int start
)
2225 int max_regno
= max_reg_num ();
2227 for (i
= start
; i
< max_regno
; i
++)
2229 old_regno
= ORIGINAL_REGNO (regno_reg_rtx
[i
]);
2230 ira_assert (i
!= old_regno
);
2231 setup_reg_classes (i
, reg_preferred_class (old_regno
),
2232 reg_alternate_class (old_regno
),
2233 reg_allocno_class (old_regno
));
2234 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
2235 fprintf (ira_dump_file
,
2236 " New r%d: setting preferred %s, alternative %s\n",
2237 i
, reg_class_names
[reg_preferred_class (old_regno
)],
2238 reg_class_names
[reg_alternate_class (old_regno
)]);
2243 /* The number of entries allocated in teg_info. */
2244 static int allocated_reg_info_size
;
2246 /* Regional allocation can create new pseudo-registers. This function
2247 expands some arrays for pseudo-registers. */
2249 expand_reg_info (void)
2252 int size
= max_reg_num ();
2255 for (i
= allocated_reg_info_size
; i
< size
; i
++)
2256 setup_reg_classes (i
, GENERAL_REGS
, ALL_REGS
, GENERAL_REGS
);
2257 setup_preferred_alternate_classes_for_new_pseudos (allocated_reg_info_size
);
2258 allocated_reg_info_size
= size
;
2261 /* Return TRUE if there is too high register pressure in the function.
2262 It is used to decide when stack slot sharing is worth to do. */
2264 too_high_register_pressure_p (void)
2267 enum reg_class pclass
;
2269 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2271 pclass
= ira_pressure_classes
[i
];
2272 if (ira_loop_tree_root
->reg_pressure
[pclass
] > 10000)
2280 /* Indicate that hard register number FROM was eliminated and replaced with
2281 an offset from hard register number TO. The status of hard registers live
2282 at the start of a basic block is updated by replacing a use of FROM with
2286 mark_elimination (int from
, int to
)
2292 /* We don't use LIVE info in IRA. */
2293 bitmap r
= DF_LR_IN (bb
);
2295 if (REGNO_REG_SET_P (r
, from
))
2297 CLEAR_REGNO_REG_SET (r
, from
);
2298 SET_REGNO_REG_SET (r
, to
);
2307 /* Set when a REG_EQUIV note is found or created. Use to
2308 keep track of what memory accesses might be created later,
2312 /* The list of each instruction which initializes this register. */
2314 /* Loop depth is used to recognize equivalences which appear
2315 to be present within the same loop (or in an inner loop). */
2317 /* Nonzero if this had a preexisting REG_EQUIV note. */
2318 int is_arg_equivalence
;
2319 /* Set when an attempt should be made to replace a register
2320 with the associated src_p entry. */
2324 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
2325 structure for that register. */
2326 static struct equivalence
*reg_equiv
;
2328 /* Used for communication between the following two functions: contains
2329 a MEM that we wish to ensure remains unchanged. */
2330 static rtx equiv_mem
;
2332 /* Set nonzero if EQUIV_MEM is modified. */
2333 static int equiv_mem_modified
;
2335 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
2336 Called via note_stores. */
2338 validate_equiv_mem_from_store (rtx dest
, const_rtx set ATTRIBUTE_UNUSED
,
2339 void *data ATTRIBUTE_UNUSED
)
2342 && reg_overlap_mentioned_p (dest
, equiv_mem
))
2344 && true_dependence (dest
, VOIDmode
, equiv_mem
)))
2345 equiv_mem_modified
= 1;
2348 /* Verify that no store between START and the death of REG invalidates
2349 MEMREF. MEMREF is invalidated by modifying a register used in MEMREF,
2350 by storing into an overlapping memory location, or with a non-const
2353 Return 1 if MEMREF remains valid. */
2355 validate_equiv_mem (rtx start
, rtx reg
, rtx memref
)
2361 equiv_mem_modified
= 0;
2363 /* If the memory reference has side effects or is volatile, it isn't a
2364 valid equivalence. */
2365 if (side_effects_p (memref
))
2368 for (insn
= start
; insn
&& ! equiv_mem_modified
; insn
= NEXT_INSN (insn
))
2370 if (! INSN_P (insn
))
2373 if (find_reg_note (insn
, REG_DEAD
, reg
))
2376 /* This used to ignore readonly memory and const/pure calls. The problem
2377 is the equivalent form may reference a pseudo which gets assigned a
2378 call clobbered hard reg. When we later replace REG with its
2379 equivalent form, the value in the call-clobbered reg has been
2380 changed and all hell breaks loose. */
2384 note_stores (PATTERN (insn
), validate_equiv_mem_from_store
, NULL
);
2386 /* If a register mentioned in MEMREF is modified via an
2387 auto-increment, we lose the equivalence. Do the same if one
2388 dies; although we could extend the life, it doesn't seem worth
2391 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
2392 if ((REG_NOTE_KIND (note
) == REG_INC
2393 || REG_NOTE_KIND (note
) == REG_DEAD
)
2394 && REG_P (XEXP (note
, 0))
2395 && reg_overlap_mentioned_p (XEXP (note
, 0), memref
))
2402 /* Returns zero if X is known to be invariant. */
2404 equiv_init_varies_p (rtx x
)
2406 RTX_CODE code
= GET_CODE (x
);
2413 return !MEM_READONLY_P (x
) || equiv_init_varies_p (XEXP (x
, 0));
2425 return reg_equiv
[REGNO (x
)].replace
== 0 && rtx_varies_p (x
, 0);
2428 if (MEM_VOLATILE_P (x
))
2437 fmt
= GET_RTX_FORMAT (code
);
2438 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2441 if (equiv_init_varies_p (XEXP (x
, i
)))
2444 else if (fmt
[i
] == 'E')
2447 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2448 if (equiv_init_varies_p (XVECEXP (x
, i
, j
)))
2455 /* Returns nonzero if X (used to initialize register REGNO) is movable.
2456 X is only movable if the registers it uses have equivalent initializations
2457 which appear to be within the same loop (or in an inner loop) and movable
2458 or if they are not candidates for local_alloc and don't vary. */
2460 equiv_init_movable_p (rtx x
, int regno
)
2464 enum rtx_code code
= GET_CODE (x
);
2469 return equiv_init_movable_p (SET_SRC (x
), regno
);
2484 return ((reg_equiv
[REGNO (x
)].loop_depth
>= reg_equiv
[regno
].loop_depth
2485 && reg_equiv
[REGNO (x
)].replace
)
2486 || (REG_BASIC_BLOCK (REGNO (x
)) < NUM_FIXED_BLOCKS
2487 && ! rtx_varies_p (x
, 0)));
2489 case UNSPEC_VOLATILE
:
2493 if (MEM_VOLATILE_P (x
))
2502 fmt
= GET_RTX_FORMAT (code
);
2503 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2507 if (! equiv_init_movable_p (XEXP (x
, i
), regno
))
2511 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2512 if (! equiv_init_movable_p (XVECEXP (x
, i
, j
), regno
))
2520 /* TRUE if X uses any registers for which reg_equiv[REGNO].replace is
2523 contains_replace_regs (rtx x
)
2527 enum rtx_code code
= GET_CODE (x
);
2544 return reg_equiv
[REGNO (x
)].replace
;
2550 fmt
= GET_RTX_FORMAT (code
);
2551 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2555 if (contains_replace_regs (XEXP (x
, i
)))
2559 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2560 if (contains_replace_regs (XVECEXP (x
, i
, j
)))
2568 /* TRUE if X references a memory location that would be affected by a store
2571 memref_referenced_p (rtx memref
, rtx x
)
2575 enum rtx_code code
= GET_CODE (x
);
2593 return (reg_equiv
[REGNO (x
)].replacement
2594 && memref_referenced_p (memref
,
2595 reg_equiv
[REGNO (x
)].replacement
));
2598 if (true_dependence (memref
, VOIDmode
, x
))
2603 /* If we are setting a MEM, it doesn't count (its address does), but any
2604 other SET_DEST that has a MEM in it is referencing the MEM. */
2605 if (MEM_P (SET_DEST (x
)))
2607 if (memref_referenced_p (memref
, XEXP (SET_DEST (x
), 0)))
2610 else if (memref_referenced_p (memref
, SET_DEST (x
)))
2613 return memref_referenced_p (memref
, SET_SRC (x
));
2619 fmt
= GET_RTX_FORMAT (code
);
2620 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2624 if (memref_referenced_p (memref
, XEXP (x
, i
)))
2628 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2629 if (memref_referenced_p (memref
, XVECEXP (x
, i
, j
)))
2637 /* TRUE if some insn in the range (START, END] references a memory location
2638 that would be affected by a store to MEMREF. */
2640 memref_used_between_p (rtx memref
, rtx start
, rtx end
)
2644 for (insn
= NEXT_INSN (start
); insn
!= NEXT_INSN (end
);
2645 insn
= NEXT_INSN (insn
))
2647 if (!NONDEBUG_INSN_P (insn
))
2650 if (memref_referenced_p (memref
, PATTERN (insn
)))
2653 /* Nonconst functions may access memory. */
2654 if (CALL_P (insn
) && (! RTL_CONST_CALL_P (insn
)))
2661 /* Mark REG as having no known equivalence.
2662 Some instructions might have been processed before and furnished
2663 with REG_EQUIV notes for this register; these notes will have to be
2665 STORE is the piece of RTL that does the non-constant / conflicting
2666 assignment - a SET, CLOBBER or REG_INC note. It is currently not used,
2667 but needs to be there because this function is called from note_stores. */
2669 no_equiv (rtx reg
, const_rtx store ATTRIBUTE_UNUSED
,
2670 void *data ATTRIBUTE_UNUSED
)
2677 regno
= REGNO (reg
);
2678 list
= reg_equiv
[regno
].init_insns
;
2679 if (list
== const0_rtx
)
2681 reg_equiv
[regno
].init_insns
= const0_rtx
;
2682 reg_equiv
[regno
].replacement
= NULL_RTX
;
2683 /* This doesn't matter for equivalences made for argument registers, we
2684 should keep their initialization insns. */
2685 if (reg_equiv
[regno
].is_arg_equivalence
)
2687 reg_equiv_init (regno
) = NULL_RTX
;
2688 for (; list
; list
= XEXP (list
, 1))
2690 rtx insn
= XEXP (list
, 0);
2691 remove_note (insn
, find_reg_note (insn
, REG_EQUIV
, NULL_RTX
));
2695 /* In DEBUG_INSN location adjust REGs from CLEARED_REGS bitmap to the
2696 equivalent replacement. */
2699 adjust_cleared_regs (rtx loc
, const_rtx old_rtx ATTRIBUTE_UNUSED
, void *data
)
2703 bitmap cleared_regs
= (bitmap
) data
;
2704 if (bitmap_bit_p (cleared_regs
, REGNO (loc
)))
2705 return simplify_replace_fn_rtx (*reg_equiv
[REGNO (loc
)].src_p
,
2706 NULL_RTX
, adjust_cleared_regs
, data
);
2711 /* Nonzero if we recorded an equivalence for a LABEL_REF. */
2712 static int recorded_label_ref
;
2714 /* Find registers that are equivalent to a single value throughout the
2715 compilation (either because they can be referenced in memory or are
2716 set once from a single constant). Lower their priority for a
2719 If such a register is only referenced once, try substituting its
2720 value into the using insn. If it succeeds, we can eliminate the
2721 register completely.
2723 Initialize the REG_EQUIV_INIT array of initializing insns.
2725 Return non-zero if jump label rebuilding should be done. */
2727 update_equiv_regs (void)
2732 bitmap cleared_regs
;
2734 /* We need to keep track of whether or not we recorded a LABEL_REF so
2735 that we know if the jump optimizer needs to be rerun. */
2736 recorded_label_ref
= 0;
2738 reg_equiv
= XCNEWVEC (struct equivalence
, max_regno
);
2741 init_alias_analysis ();
2743 /* Scan the insns and find which registers have equivalences. Do this
2744 in a separate scan of the insns because (due to -fcse-follow-jumps)
2745 a register can be set below its use. */
2748 loop_depth
= bb
->loop_depth
;
2750 for (insn
= BB_HEAD (bb
);
2751 insn
!= NEXT_INSN (BB_END (bb
));
2752 insn
= NEXT_INSN (insn
))
2759 if (! INSN_P (insn
))
2762 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
2763 if (REG_NOTE_KIND (note
) == REG_INC
)
2764 no_equiv (XEXP (note
, 0), note
, NULL
);
2766 set
= single_set (insn
);
2768 /* If this insn contains more (or less) than a single SET,
2769 only mark all destinations as having no known equivalence. */
2772 note_stores (PATTERN (insn
), no_equiv
, NULL
);
2775 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2779 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
2781 rtx part
= XVECEXP (PATTERN (insn
), 0, i
);
2783 note_stores (part
, no_equiv
, NULL
);
2787 dest
= SET_DEST (set
);
2788 src
= SET_SRC (set
);
2790 /* See if this is setting up the equivalence between an argument
2791 register and its stack slot. */
2792 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
2795 gcc_assert (REG_P (dest
));
2796 regno
= REGNO (dest
);
2798 /* Note that we don't want to clear reg_equiv_init even if there
2799 are multiple sets of this register. */
2800 reg_equiv
[regno
].is_arg_equivalence
= 1;
2802 /* Record for reload that this is an equivalencing insn. */
2803 if (rtx_equal_p (src
, XEXP (note
, 0)))
2804 reg_equiv_init (regno
)
2805 = gen_rtx_INSN_LIST (VOIDmode
, insn
, reg_equiv_init (regno
));
2807 /* Continue normally in case this is a candidate for
2814 /* We only handle the case of a pseudo register being set
2815 once, or always to the same value. */
2816 /* ??? The mn10200 port breaks if we add equivalences for
2817 values that need an ADDRESS_REGS register and set them equivalent
2818 to a MEM of a pseudo. The actual problem is in the over-conservative
2819 handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
2820 calculate_needs, but we traditionally work around this problem
2821 here by rejecting equivalences when the destination is in a register
2822 that's likely spilled. This is fragile, of course, since the
2823 preferred class of a pseudo depends on all instructions that set
2827 || (regno
= REGNO (dest
)) < FIRST_PSEUDO_REGISTER
2828 || reg_equiv
[regno
].init_insns
== const0_rtx
2829 || (targetm
.class_likely_spilled_p (reg_preferred_class (regno
))
2830 && MEM_P (src
) && ! reg_equiv
[regno
].is_arg_equivalence
))
2832 /* This might be setting a SUBREG of a pseudo, a pseudo that is
2833 also set somewhere else to a constant. */
2834 note_stores (set
, no_equiv
, NULL
);
2838 note
= find_reg_note (insn
, REG_EQUAL
, NULL_RTX
);
2840 /* cse sometimes generates function invariants, but doesn't put a
2841 REG_EQUAL note on the insn. Since this note would be redundant,
2842 there's no point creating it earlier than here. */
2843 if (! note
&& ! rtx_varies_p (src
, 0))
2844 note
= set_unique_reg_note (insn
, REG_EQUAL
, copy_rtx (src
));
2846 /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
2847 since it represents a function call */
2848 if (note
&& GET_CODE (XEXP (note
, 0)) == EXPR_LIST
)
2851 if (DF_REG_DEF_COUNT (regno
) != 1
2853 || rtx_varies_p (XEXP (note
, 0), 0)
2854 || (reg_equiv
[regno
].replacement
2855 && ! rtx_equal_p (XEXP (note
, 0),
2856 reg_equiv
[regno
].replacement
))))
2858 no_equiv (dest
, set
, NULL
);
2861 /* Record this insn as initializing this register. */
2862 reg_equiv
[regno
].init_insns
2863 = gen_rtx_INSN_LIST (VOIDmode
, insn
, reg_equiv
[regno
].init_insns
);
2865 /* If this register is known to be equal to a constant, record that
2866 it is always equivalent to the constant. */
2867 if (DF_REG_DEF_COUNT (regno
) == 1
2868 && note
&& ! rtx_varies_p (XEXP (note
, 0), 0))
2870 rtx note_value
= XEXP (note
, 0);
2871 remove_note (insn
, note
);
2872 set_unique_reg_note (insn
, REG_EQUIV
, note_value
);
2875 /* If this insn introduces a "constant" register, decrease the priority
2876 of that register. Record this insn if the register is only used once
2877 more and the equivalence value is the same as our source.
2879 The latter condition is checked for two reasons: First, it is an
2880 indication that it may be more efficient to actually emit the insn
2881 as written (if no registers are available, reload will substitute
2882 the equivalence). Secondly, it avoids problems with any registers
2883 dying in this insn whose death notes would be missed.
2885 If we don't have a REG_EQUIV note, see if this insn is loading
2886 a register used only in one basic block from a MEM. If so, and the
2887 MEM remains unchanged for the life of the register, add a REG_EQUIV
2890 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
2892 if (note
== 0 && REG_BASIC_BLOCK (regno
) >= NUM_FIXED_BLOCKS
2893 && MEM_P (SET_SRC (set
))
2894 && validate_equiv_mem (insn
, dest
, SET_SRC (set
)))
2895 note
= set_unique_reg_note (insn
, REG_EQUIV
, copy_rtx (SET_SRC (set
)));
2899 int regno
= REGNO (dest
);
2900 rtx x
= XEXP (note
, 0);
2902 /* If we haven't done so, record for reload that this is an
2903 equivalencing insn. */
2904 if (!reg_equiv
[regno
].is_arg_equivalence
)
2905 reg_equiv_init (regno
)
2906 = gen_rtx_INSN_LIST (VOIDmode
, insn
, reg_equiv_init (regno
));
2908 /* Record whether or not we created a REG_EQUIV note for a LABEL_REF.
2909 We might end up substituting the LABEL_REF for uses of the
2910 pseudo here or later. That kind of transformation may turn an
2911 indirect jump into a direct jump, in which case we must rerun the
2912 jump optimizer to ensure that the JUMP_LABEL fields are valid. */
2913 if (GET_CODE (x
) == LABEL_REF
2914 || (GET_CODE (x
) == CONST
2915 && GET_CODE (XEXP (x
, 0)) == PLUS
2916 && (GET_CODE (XEXP (XEXP (x
, 0), 0)) == LABEL_REF
)))
2917 recorded_label_ref
= 1;
2919 reg_equiv
[regno
].replacement
= x
;
2920 reg_equiv
[regno
].src_p
= &SET_SRC (set
);
2921 reg_equiv
[regno
].loop_depth
= loop_depth
;
2923 /* Don't mess with things live during setjmp. */
2924 if (REG_LIVE_LENGTH (regno
) >= 0 && optimize
)
2926 /* Note that the statement below does not affect the priority
2928 REG_LIVE_LENGTH (regno
) *= 2;
2930 /* If the register is referenced exactly twice, meaning it is
2931 set once and used once, indicate that the reference may be
2932 replaced by the equivalence we computed above. Do this
2933 even if the register is only used in one block so that
2934 dependencies can be handled where the last register is
2935 used in a different block (i.e. HIGH / LO_SUM sequences)
2936 and to reduce the number of registers alive across
2939 if (REG_N_REFS (regno
) == 2
2940 && (rtx_equal_p (x
, src
)
2941 || ! equiv_init_varies_p (src
))
2942 && NONJUMP_INSN_P (insn
)
2943 && equiv_init_movable_p (PATTERN (insn
), regno
))
2944 reg_equiv
[regno
].replace
= 1;
2953 /* A second pass, to gather additional equivalences with memory. This needs
2954 to be done after we know which registers we are going to replace. */
2956 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
2961 if (! INSN_P (insn
))
2964 set
= single_set (insn
);
2968 dest
= SET_DEST (set
);
2969 src
= SET_SRC (set
);
2971 /* If this sets a MEM to the contents of a REG that is only used
2972 in a single basic block, see if the register is always equivalent
2973 to that memory location and if moving the store from INSN to the
2974 insn that set REG is safe. If so, put a REG_EQUIV note on the
2977 Don't add a REG_EQUIV note if the insn already has one. The existing
2978 REG_EQUIV is likely more useful than the one we are adding.
2980 If one of the regs in the address has reg_equiv[REGNO].replace set,
2981 then we can't add this REG_EQUIV note. The reg_equiv[REGNO].replace
2982 optimization may move the set of this register immediately before
2983 insn, which puts it after reg_equiv[REGNO].init_insns, and hence
2984 the mention in the REG_EQUIV note would be to an uninitialized
2987 if (MEM_P (dest
) && REG_P (src
)
2988 && (regno
= REGNO (src
)) >= FIRST_PSEUDO_REGISTER
2989 && REG_BASIC_BLOCK (regno
) >= NUM_FIXED_BLOCKS
2990 && DF_REG_DEF_COUNT (regno
) == 1
2991 && reg_equiv
[regno
].init_insns
!= 0
2992 && reg_equiv
[regno
].init_insns
!= const0_rtx
2993 && ! find_reg_note (XEXP (reg_equiv
[regno
].init_insns
, 0),
2994 REG_EQUIV
, NULL_RTX
)
2995 && ! contains_replace_regs (XEXP (dest
, 0)))
2997 rtx init_insn
= XEXP (reg_equiv
[regno
].init_insns
, 0);
2998 if (validate_equiv_mem (init_insn
, src
, dest
)
2999 && ! memref_used_between_p (dest
, init_insn
, insn
)
3000 /* Attaching a REG_EQUIV note will fail if INIT_INSN has
3002 && set_unique_reg_note (init_insn
, REG_EQUIV
, copy_rtx (dest
)))
3004 /* This insn makes the equivalence, not the one initializing
3006 reg_equiv_init (regno
)
3007 = gen_rtx_INSN_LIST (VOIDmode
, insn
, NULL_RTX
);
3008 df_notes_rescan (init_insn
);
3013 cleared_regs
= BITMAP_ALLOC (NULL
);
3014 /* Now scan all regs killed in an insn to see if any of them are
3015 registers only used that once. If so, see if we can replace the
3016 reference with the equivalent form. If we can, delete the
3017 initializing reference and this register will go away. If we
3018 can't replace the reference, and the initializing reference is
3019 within the same loop (or in an inner loop), then move the register
3020 initialization just before the use, so that they are in the same
3022 FOR_EACH_BB_REVERSE (bb
)
3024 loop_depth
= bb
->loop_depth
;
3025 for (insn
= BB_END (bb
);
3026 insn
!= PREV_INSN (BB_HEAD (bb
));
3027 insn
= PREV_INSN (insn
))
3031 if (! INSN_P (insn
))
3034 /* Don't substitute into a non-local goto, this confuses CFG. */
3036 && find_reg_note (insn
, REG_NON_LOCAL_GOTO
, NULL_RTX
))
3039 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
3041 if (REG_NOTE_KIND (link
) == REG_DEAD
3042 /* Make sure this insn still refers to the register. */
3043 && reg_mentioned_p (XEXP (link
, 0), PATTERN (insn
)))
3045 int regno
= REGNO (XEXP (link
, 0));
3048 if (! reg_equiv
[regno
].replace
3049 || reg_equiv
[regno
].loop_depth
< loop_depth
3050 /* There is no sense to move insns if we did
3051 register pressure-sensitive scheduling was
3052 done because it will not improve allocation
3053 but worsen insn schedule with a big
3055 || (flag_sched_pressure
&& flag_schedule_insns
))
3058 /* reg_equiv[REGNO].replace gets set only when
3059 REG_N_REFS[REGNO] is 2, i.e. the register is set
3060 once and used once. (If it were only set, but not used,
3061 flow would have deleted the setting insns.) Hence
3062 there can only be one insn in reg_equiv[REGNO].init_insns. */
3063 gcc_assert (reg_equiv
[regno
].init_insns
3064 && !XEXP (reg_equiv
[regno
].init_insns
, 1));
3065 equiv_insn
= XEXP (reg_equiv
[regno
].init_insns
, 0);
3067 /* We may not move instructions that can throw, since
3068 that changes basic block boundaries and we are not
3069 prepared to adjust the CFG to match. */
3070 if (can_throw_internal (equiv_insn
))
3073 if (asm_noperands (PATTERN (equiv_insn
)) < 0
3074 && validate_replace_rtx (regno_reg_rtx
[regno
],
3075 *(reg_equiv
[regno
].src_p
), insn
))
3081 /* Find the last note. */
3082 for (last_link
= link
; XEXP (last_link
, 1);
3083 last_link
= XEXP (last_link
, 1))
3086 /* Append the REG_DEAD notes from equiv_insn. */
3087 equiv_link
= REG_NOTES (equiv_insn
);
3091 equiv_link
= XEXP (equiv_link
, 1);
3092 if (REG_NOTE_KIND (note
) == REG_DEAD
)
3094 remove_note (equiv_insn
, note
);
3095 XEXP (last_link
, 1) = note
;
3096 XEXP (note
, 1) = NULL_RTX
;
3101 remove_death (regno
, insn
);
3102 SET_REG_N_REFS (regno
, 0);
3103 REG_FREQ (regno
) = 0;
3104 delete_insn (equiv_insn
);
3106 reg_equiv
[regno
].init_insns
3107 = XEXP (reg_equiv
[regno
].init_insns
, 1);
3109 reg_equiv_init (regno
) = NULL_RTX
;
3110 bitmap_set_bit (cleared_regs
, regno
);
3112 /* Move the initialization of the register to just before
3113 INSN. Update the flow information. */
3114 else if (prev_nondebug_insn (insn
) != equiv_insn
)
3118 new_insn
= emit_insn_before (PATTERN (equiv_insn
), insn
);
3119 REG_NOTES (new_insn
) = REG_NOTES (equiv_insn
);
3120 REG_NOTES (equiv_insn
) = 0;
3121 /* Rescan it to process the notes. */
3122 df_insn_rescan (new_insn
);
3124 /* Make sure this insn is recognized before
3125 reload begins, otherwise
3126 eliminate_regs_in_insn will die. */
3127 INSN_CODE (new_insn
) = INSN_CODE (equiv_insn
);
3129 delete_insn (equiv_insn
);
3131 XEXP (reg_equiv
[regno
].init_insns
, 0) = new_insn
;
3133 REG_BASIC_BLOCK (regno
) = bb
->index
;
3134 REG_N_CALLS_CROSSED (regno
) = 0;
3135 REG_FREQ_CALLS_CROSSED (regno
) = 0;
3136 REG_N_THROWING_CALLS_CROSSED (regno
) = 0;
3137 REG_LIVE_LENGTH (regno
) = 2;
3139 if (insn
== BB_HEAD (bb
))
3140 BB_HEAD (bb
) = PREV_INSN (insn
);
3142 reg_equiv_init (regno
)
3143 = gen_rtx_INSN_LIST (VOIDmode
, new_insn
, NULL_RTX
);
3144 bitmap_set_bit (cleared_regs
, regno
);
3151 if (!bitmap_empty_p (cleared_regs
))
3155 bitmap_and_compl_into (DF_LIVE_IN (bb
), cleared_regs
);
3156 bitmap_and_compl_into (DF_LIVE_OUT (bb
), cleared_regs
);
3157 bitmap_and_compl_into (DF_LR_IN (bb
), cleared_regs
);
3158 bitmap_and_compl_into (DF_LR_OUT (bb
), cleared_regs
);
3161 /* Last pass - adjust debug insns referencing cleared regs. */
3162 if (MAY_HAVE_DEBUG_INSNS
)
3163 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
3164 if (DEBUG_INSN_P (insn
))
3166 rtx old_loc
= INSN_VAR_LOCATION_LOC (insn
);
3167 INSN_VAR_LOCATION_LOC (insn
)
3168 = simplify_replace_fn_rtx (old_loc
, NULL_RTX
,
3169 adjust_cleared_regs
,
3170 (void *) cleared_regs
);
3171 if (old_loc
!= INSN_VAR_LOCATION_LOC (insn
))
3172 df_insn_rescan (insn
);
3176 BITMAP_FREE (cleared_regs
);
3181 end_alias_analysis ();
3183 return recorded_label_ref
;
3188 /* Print chain C to FILE. */
3190 print_insn_chain (FILE *file
, struct insn_chain
*c
)
3192 fprintf (file
, "insn=%d, ", INSN_UID(c
->insn
));
3193 bitmap_print (file
, &c
->live_throughout
, "live_throughout: ", ", ");
3194 bitmap_print (file
, &c
->dead_or_set
, "dead_or_set: ", "\n");
3198 /* Print all reload_insn_chains to FILE. */
3200 print_insn_chains (FILE *file
)
3202 struct insn_chain
*c
;
3203 for (c
= reload_insn_chain
; c
; c
= c
->next
)
3204 print_insn_chain (file
, c
);
3207 /* Return true if pseudo REGNO should be added to set live_throughout
3208 or dead_or_set of the insn chains for reload consideration. */
3210 pseudo_for_reload_consideration_p (int regno
)
3212 /* Consider spilled pseudos too for IRA because they still have a
3213 chance to get hard-registers in the reload when IRA is used. */
3214 return (reg_renumber
[regno
] >= 0 || ira_conflicts_p
);
3217 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
3218 REG to the number of nregs, and INIT_VALUE to get the
3219 initialization. ALLOCNUM need not be the regno of REG. */
3221 init_live_subregs (bool init_value
, sbitmap
*live_subregs
,
3222 int *live_subregs_used
, int allocnum
, rtx reg
)
3224 unsigned int regno
= REGNO (SUBREG_REG (reg
));
3225 int size
= GET_MODE_SIZE (GET_MODE (regno_reg_rtx
[regno
]));
3227 gcc_assert (size
> 0);
3229 /* Been there, done that. */
3230 if (live_subregs_used
[allocnum
])
3233 /* Create a new one with zeros. */
3234 if (live_subregs
[allocnum
] == NULL
)
3235 live_subregs
[allocnum
] = sbitmap_alloc (size
);
3237 /* If the entire reg was live before blasting into subregs, we need
3238 to init all of the subregs to ones else init to 0. */
3240 sbitmap_ones (live_subregs
[allocnum
]);
3242 sbitmap_zero (live_subregs
[allocnum
]);
3244 /* Set the number of bits that we really want. */
3245 live_subregs_used
[allocnum
] = size
;
3248 /* Walk the insns of the current function and build reload_insn_chain,
3249 and record register life information. */
3251 build_insn_chain (void)
3254 struct insn_chain
**p
= &reload_insn_chain
;
3256 struct insn_chain
*c
= NULL
;
3257 struct insn_chain
*next
= NULL
;
3258 bitmap live_relevant_regs
= BITMAP_ALLOC (NULL
);
3259 bitmap elim_regset
= BITMAP_ALLOC (NULL
);
3260 /* live_subregs is a vector used to keep accurate information about
3261 which hardregs are live in multiword pseudos. live_subregs and
3262 live_subregs_used are indexed by pseudo number. The live_subreg
3263 entry for a particular pseudo is only used if the corresponding
3264 element is non zero in live_subregs_used. The value in
3265 live_subregs_used is number of bytes that the pseudo can
3267 sbitmap
*live_subregs
= XCNEWVEC (sbitmap
, max_regno
);
3268 int *live_subregs_used
= XNEWVEC (int, max_regno
);
3270 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
3271 if (TEST_HARD_REG_BIT (eliminable_regset
, i
))
3272 bitmap_set_bit (elim_regset
, i
);
3273 FOR_EACH_BB_REVERSE (bb
)
3278 CLEAR_REG_SET (live_relevant_regs
);
3279 memset (live_subregs_used
, 0, max_regno
* sizeof (int));
3281 EXECUTE_IF_SET_IN_BITMAP (DF_LR_OUT (bb
), 0, i
, bi
)
3283 if (i
>= FIRST_PSEUDO_REGISTER
)
3285 bitmap_set_bit (live_relevant_regs
, i
);
3288 EXECUTE_IF_SET_IN_BITMAP (DF_LR_OUT (bb
),
3289 FIRST_PSEUDO_REGISTER
, i
, bi
)
3291 if (pseudo_for_reload_consideration_p (i
))
3292 bitmap_set_bit (live_relevant_regs
, i
);
3295 FOR_BB_INSNS_REVERSE (bb
, insn
)
3297 if (!NOTE_P (insn
) && !BARRIER_P (insn
))
3299 unsigned int uid
= INSN_UID (insn
);
3303 c
= new_insn_chain ();
3310 c
->block
= bb
->index
;
3313 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
3315 df_ref def
= *def_rec
;
3316 unsigned int regno
= DF_REF_REGNO (def
);
3318 /* Ignore may clobbers because these are generated
3319 from calls. However, every other kind of def is
3320 added to dead_or_set. */
3321 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
3323 if (regno
< FIRST_PSEUDO_REGISTER
)
3325 if (!fixed_regs
[regno
])
3326 bitmap_set_bit (&c
->dead_or_set
, regno
);
3328 else if (pseudo_for_reload_consideration_p (regno
))
3329 bitmap_set_bit (&c
->dead_or_set
, regno
);
3332 if ((regno
< FIRST_PSEUDO_REGISTER
3333 || reg_renumber
[regno
] >= 0
3335 && (!DF_REF_FLAGS_IS_SET (def
, DF_REF_CONDITIONAL
)))
3337 rtx reg
= DF_REF_REG (def
);
3339 /* We can model subregs, but not if they are
3340 wrapped in ZERO_EXTRACTS. */
3341 if (GET_CODE (reg
) == SUBREG
3342 && !DF_REF_FLAGS_IS_SET (def
, DF_REF_ZERO_EXTRACT
))
3344 unsigned int start
= SUBREG_BYTE (reg
);
3345 unsigned int last
= start
3346 + GET_MODE_SIZE (GET_MODE (reg
));
3349 (bitmap_bit_p (live_relevant_regs
, regno
),
3350 live_subregs
, live_subregs_used
, regno
, reg
);
3352 if (!DF_REF_FLAGS_IS_SET
3353 (def
, DF_REF_STRICT_LOW_PART
))
3355 /* Expand the range to cover entire words.
3356 Bytes added here are "don't care". */
3358 = start
/ UNITS_PER_WORD
* UNITS_PER_WORD
;
3359 last
= ((last
+ UNITS_PER_WORD
- 1)
3360 / UNITS_PER_WORD
* UNITS_PER_WORD
);
3363 /* Ignore the paradoxical bits. */
3364 if ((int)last
> live_subregs_used
[regno
])
3365 last
= live_subregs_used
[regno
];
3367 while (start
< last
)
3369 RESET_BIT (live_subregs
[regno
], start
);
3373 if (sbitmap_empty_p (live_subregs
[regno
]))
3375 live_subregs_used
[regno
] = 0;
3376 bitmap_clear_bit (live_relevant_regs
, regno
);
3379 /* Set live_relevant_regs here because
3380 that bit has to be true to get us to
3381 look at the live_subregs fields. */
3382 bitmap_set_bit (live_relevant_regs
, regno
);
3386 /* DF_REF_PARTIAL is generated for
3387 subregs, STRICT_LOW_PART, and
3388 ZERO_EXTRACT. We handle the subreg
3389 case above so here we have to keep from
3390 modeling the def as a killing def. */
3391 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
))
3393 bitmap_clear_bit (live_relevant_regs
, regno
);
3394 live_subregs_used
[regno
] = 0;
3400 bitmap_and_compl_into (live_relevant_regs
, elim_regset
);
3401 bitmap_copy (&c
->live_throughout
, live_relevant_regs
);
3404 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
3406 df_ref use
= *use_rec
;
3407 unsigned int regno
= DF_REF_REGNO (use
);
3408 rtx reg
= DF_REF_REG (use
);
3410 /* DF_REF_READ_WRITE on a use means that this use
3411 is fabricated from a def that is a partial set
3412 to a multiword reg. Here, we only model the
3413 subreg case that is not wrapped in ZERO_EXTRACT
3414 precisely so we do not need to look at the
3416 if (DF_REF_FLAGS_IS_SET (use
, DF_REF_READ_WRITE
)
3417 && !DF_REF_FLAGS_IS_SET (use
, DF_REF_ZERO_EXTRACT
)
3418 && DF_REF_FLAGS_IS_SET (use
, DF_REF_SUBREG
))
3421 /* Add the last use of each var to dead_or_set. */
3422 if (!bitmap_bit_p (live_relevant_regs
, regno
))
3424 if (regno
< FIRST_PSEUDO_REGISTER
)
3426 if (!fixed_regs
[regno
])
3427 bitmap_set_bit (&c
->dead_or_set
, regno
);
3429 else if (pseudo_for_reload_consideration_p (regno
))
3430 bitmap_set_bit (&c
->dead_or_set
, regno
);
3433 if (regno
< FIRST_PSEUDO_REGISTER
3434 || pseudo_for_reload_consideration_p (regno
))
3436 if (GET_CODE (reg
) == SUBREG
3437 && !DF_REF_FLAGS_IS_SET (use
,
3439 | DF_REF_ZERO_EXTRACT
))
3441 unsigned int start
= SUBREG_BYTE (reg
);
3442 unsigned int last
= start
3443 + GET_MODE_SIZE (GET_MODE (reg
));
3446 (bitmap_bit_p (live_relevant_regs
, regno
),
3447 live_subregs
, live_subregs_used
, regno
, reg
);
3449 /* Ignore the paradoxical bits. */
3450 if ((int)last
> live_subregs_used
[regno
])
3451 last
= live_subregs_used
[regno
];
3453 while (start
< last
)
3455 SET_BIT (live_subregs
[regno
], start
);
3460 /* Resetting the live_subregs_used is
3461 effectively saying do not use the subregs
3462 because we are reading the whole
3464 live_subregs_used
[regno
] = 0;
3465 bitmap_set_bit (live_relevant_regs
, regno
);
3471 /* FIXME!! The following code is a disaster. Reload needs to see the
3472 labels and jump tables that are just hanging out in between
3473 the basic blocks. See pr33676. */
3474 insn
= BB_HEAD (bb
);
3476 /* Skip over the barriers and cruft. */
3477 while (insn
&& (BARRIER_P (insn
) || NOTE_P (insn
)
3478 || BLOCK_FOR_INSN (insn
) == bb
))
3479 insn
= PREV_INSN (insn
);
3481 /* While we add anything except barriers and notes, the focus is
3482 to get the labels and jump tables into the
3483 reload_insn_chain. */
3486 if (!NOTE_P (insn
) && !BARRIER_P (insn
))
3488 if (BLOCK_FOR_INSN (insn
))
3491 c
= new_insn_chain ();
3497 /* The block makes no sense here, but it is what the old
3499 c
->block
= bb
->index
;
3501 bitmap_copy (&c
->live_throughout
, live_relevant_regs
);
3503 insn
= PREV_INSN (insn
);
3507 for (i
= 0; i
< (unsigned int) max_regno
; i
++)
3508 free (live_subregs
[i
]);
3510 reload_insn_chain
= c
;
3513 free (live_subregs
);
3514 free (live_subregs_used
);
3515 BITMAP_FREE (live_relevant_regs
);
3516 BITMAP_FREE (elim_regset
);
3519 print_insn_chains (dump_file
);
3522 /* Examine the rtx found in *LOC, which is read or written to as determined
3523 by TYPE. Return false if we find a reason why an insn containing this
3524 rtx should not be moved (such as accesses to non-constant memory), true
3527 rtx_moveable_p (rtx
*loc
, enum op_type type
)
3531 enum rtx_code code
= GET_CODE (x
);
3534 code
= GET_CODE (x
);
3547 return type
== OP_IN
;
3553 if (x
== frame_pointer_rtx
)
3555 if (HARD_REGISTER_P (x
))
3561 if (type
== OP_IN
&& MEM_READONLY_P (x
))
3562 return rtx_moveable_p (&XEXP (x
, 0), OP_IN
);
3566 return (rtx_moveable_p (&SET_SRC (x
), OP_IN
)
3567 && rtx_moveable_p (&SET_DEST (x
), OP_OUT
));
3569 case STRICT_LOW_PART
:
3570 return rtx_moveable_p (&XEXP (x
, 0), OP_OUT
);
3574 return (rtx_moveable_p (&XEXP (x
, 0), type
)
3575 && rtx_moveable_p (&XEXP (x
, 1), OP_IN
)
3576 && rtx_moveable_p (&XEXP (x
, 2), OP_IN
));
3579 return rtx_moveable_p (&SET_DEST (x
), OP_OUT
);
3585 fmt
= GET_RTX_FORMAT (code
);
3586 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3590 if (!rtx_moveable_p (&XEXP (x
, i
), type
))
3593 else if (fmt
[i
] == 'E')
3594 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
3596 if (!rtx_moveable_p (&XVECEXP (x
, i
, j
), type
))
3603 /* A wrapper around dominated_by_p, which uses the information in UID_LUID
3604 to give dominance relationships between two insns I1 and I2. */
3606 insn_dominated_by_p (rtx i1
, rtx i2
, int *uid_luid
)
3608 basic_block bb1
= BLOCK_FOR_INSN (i1
);
3609 basic_block bb2
= BLOCK_FOR_INSN (i2
);
3612 return uid_luid
[INSN_UID (i2
)] < uid_luid
[INSN_UID (i1
)];
3613 return dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
);
3616 /* Record the range of register numbers added by find_moveable_pseudos. */
3617 int first_moveable_pseudo
, last_moveable_pseudo
;
3619 /* These two vectors hold data for every register added by
3620 find_movable_pseudos, with index 0 holding data for the
3621 first_moveable_pseudo. */
3622 /* The original home register. */
3623 static VEC (rtx
, heap
) *pseudo_replaced_reg
;
3625 /* Look for instances where we have an instruction that is known to increase
3626 register pressure, and whose result is not used immediately. If it is
3627 possible to move the instruction downwards to just before its first use,
3628 split its lifetime into two ranges. We create a new pseudo to compute the
3629 value, and emit a move instruction just before the first use. If, after
3630 register allocation, the new pseudo remains unallocated, the function
3631 move_unallocated_pseudos then deletes the move instruction and places
3632 the computation just before the first use.
3634 Such a move is safe and profitable if all the input registers remain live
3635 and unchanged between the original computation and its first use. In such
3636 a situation, the computation is known to increase register pressure, and
3637 moving it is known to at least not worsen it.
3639 We restrict moves to only those cases where a register remains unallocated,
3640 in order to avoid interfering too much with the instruction schedule. As
3641 an exception, we may move insns which only modify their input register
3642 (typically induction variables), as this increases the freedom for our
3643 intended transformation, and does not limit the second instruction
3647 find_moveable_pseudos (void)
3650 int max_regs
= max_reg_num ();
3651 int max_uid
= get_max_uid ();
3653 int *uid_luid
= XNEWVEC (int, max_uid
);
3654 rtx
*closest_uses
= XNEWVEC (rtx
, max_regs
);
3655 /* A set of registers which are live but not modified throughout a block. */
3656 bitmap_head
*bb_transp_live
= XNEWVEC (bitmap_head
, last_basic_block
);
3657 /* A set of registers which only exist in a given basic block. */
3658 bitmap_head
*bb_local
= XNEWVEC (bitmap_head
, last_basic_block
);
3659 /* A set of registers which are set once, in an instruction that can be
3660 moved freely downwards, but are otherwise transparent to a block. */
3661 bitmap_head
*bb_moveable_reg_sets
= XNEWVEC (bitmap_head
, last_basic_block
);
3662 bitmap_head live
, used
, set
, interesting
, unusable_as_input
;
3664 bitmap_initialize (&interesting
, 0);
3666 first_moveable_pseudo
= max_regs
;
3667 VEC_free (rtx
, heap
, pseudo_replaced_reg
);
3668 VEC_safe_grow (rtx
, heap
, pseudo_replaced_reg
, max_regs
);
3671 calculate_dominance_info (CDI_DOMINATORS
);
3674 bitmap_initialize (&live
, 0);
3675 bitmap_initialize (&used
, 0);
3676 bitmap_initialize (&set
, 0);
3677 bitmap_initialize (&unusable_as_input
, 0);
3681 bitmap transp
= bb_transp_live
+ bb
->index
;
3682 bitmap moveable
= bb_moveable_reg_sets
+ bb
->index
;
3683 bitmap local
= bb_local
+ bb
->index
;
3685 bitmap_initialize (local
, 0);
3686 bitmap_initialize (transp
, 0);
3687 bitmap_initialize (moveable
, 0);
3688 bitmap_copy (&live
, df_get_live_out (bb
));
3689 bitmap_and_into (&live
, df_get_live_in (bb
));
3690 bitmap_copy (transp
, &live
);
3691 bitmap_clear (moveable
);
3692 bitmap_clear (&live
);
3693 bitmap_clear (&used
);
3694 bitmap_clear (&set
);
3695 FOR_BB_INSNS (bb
, insn
)
3696 if (NONDEBUG_INSN_P (insn
))
3698 df_ref
*u_rec
, *d_rec
;
3700 uid_luid
[INSN_UID (insn
)] = i
++;
3702 u_rec
= DF_INSN_USES (insn
);
3703 d_rec
= DF_INSN_DEFS (insn
);
3704 if (d_rec
[0] != NULL
&& d_rec
[1] == NULL
3705 && u_rec
[0] != NULL
&& u_rec
[1] == NULL
3706 && DF_REF_REGNO (*u_rec
) == DF_REF_REGNO (*d_rec
)
3707 && !bitmap_bit_p (&set
, DF_REF_REGNO (*u_rec
))
3708 && rtx_moveable_p (&PATTERN (insn
), OP_IN
))
3710 unsigned regno
= DF_REF_REGNO (*u_rec
);
3711 bitmap_set_bit (moveable
, regno
);
3712 bitmap_set_bit (&set
, regno
);
3713 bitmap_set_bit (&used
, regno
);
3714 bitmap_clear_bit (transp
, regno
);
3719 unsigned regno
= DF_REF_REGNO (*u_rec
);
3720 bitmap_set_bit (&used
, regno
);
3721 if (bitmap_clear_bit (moveable
, regno
))
3722 bitmap_clear_bit (transp
, regno
);
3728 unsigned regno
= DF_REF_REGNO (*d_rec
);
3729 bitmap_set_bit (&set
, regno
);
3730 bitmap_clear_bit (transp
, regno
);
3731 bitmap_clear_bit (moveable
, regno
);
3737 bitmap_clear (&live
);
3738 bitmap_clear (&used
);
3739 bitmap_clear (&set
);
3743 bitmap local
= bb_local
+ bb
->index
;
3746 FOR_BB_INSNS (bb
, insn
)
3747 if (NONDEBUG_INSN_P (insn
))
3749 rtx def_insn
, closest_use
, note
;
3750 df_ref
*def_rec
, def
, use
;
3752 bool all_dominated
, all_local
;
3753 enum machine_mode mode
;
3755 def_rec
= DF_INSN_DEFS (insn
);
3756 /* There must be exactly one def in this insn. */
3758 if (!def
|| def_rec
[1] || !single_set (insn
))
3760 /* This must be the only definition of the reg. We also limit
3761 which modes we deal with so that we can assume we can generate
3762 move instructions. */
3763 regno
= DF_REF_REGNO (def
);
3764 mode
= GET_MODE (DF_REF_REG (def
));
3765 if (DF_REG_DEF_COUNT (regno
) != 1
3766 || !DF_REF_INSN_INFO (def
)
3767 || HARD_REGISTER_NUM_P (regno
)
3768 || DF_REG_EQ_USE_COUNT (regno
) > 0
3769 || (!INTEGRAL_MODE_P (mode
) && !FLOAT_MODE_P (mode
)))
3771 def_insn
= DF_REF_INSN (def
);
3773 for (note
= REG_NOTES (def_insn
); note
; note
= XEXP (note
, 1))
3774 if (REG_NOTE_KIND (note
) == REG_EQUIV
&& MEM_P (XEXP (note
, 0)))
3780 fprintf (dump_file
, "Ignoring reg %d, has equiv memory\n",
3782 bitmap_set_bit (&unusable_as_input
, regno
);
3786 use
= DF_REG_USE_CHAIN (regno
);
3787 all_dominated
= true;
3789 closest_use
= NULL_RTX
;
3790 for (; use
; use
= DF_REF_NEXT_REG (use
))
3793 if (!DF_REF_INSN_INFO (use
))
3795 all_dominated
= false;
3799 insn
= DF_REF_INSN (use
);
3800 if (DEBUG_INSN_P (insn
))
3802 if (BLOCK_FOR_INSN (insn
) != BLOCK_FOR_INSN (def_insn
))
3804 if (!insn_dominated_by_p (insn
, def_insn
, uid_luid
))
3805 all_dominated
= false;
3806 if (closest_use
!= insn
&& closest_use
!= const0_rtx
)
3808 if (closest_use
== NULL_RTX
)
3810 else if (insn_dominated_by_p (closest_use
, insn
, uid_luid
))
3812 else if (!insn_dominated_by_p (insn
, closest_use
, uid_luid
))
3813 closest_use
= const0_rtx
;
3819 fprintf (dump_file
, "Reg %d not all uses dominated by set\n",
3824 bitmap_set_bit (local
, regno
);
3825 if (closest_use
== const0_rtx
|| closest_use
== NULL
3826 || next_nonnote_nondebug_insn (def_insn
) == closest_use
)
3829 fprintf (dump_file
, "Reg %d uninteresting%s\n", regno
,
3830 closest_use
== const0_rtx
|| closest_use
== NULL
3831 ? " (no unique first use)" : "");
3835 if (reg_referenced_p (cc0_rtx
, PATTERN (closest_use
)))
3838 fprintf (dump_file
, "Reg %d: closest user uses cc0\n",
3843 bitmap_set_bit (&interesting
, regno
);
3844 closest_uses
[regno
] = closest_use
;
3846 if (dump_file
&& (all_local
|| all_dominated
))
3848 fprintf (dump_file
, "Reg %u:", regno
);
3850 fprintf (dump_file
, " local to bb %d", bb
->index
);
3852 fprintf (dump_file
, " def dominates all uses");
3853 if (closest_use
!= const0_rtx
)
3854 fprintf (dump_file
, " has unique first use");
3855 fputs ("\n", dump_file
);
3860 EXECUTE_IF_SET_IN_BITMAP (&interesting
, 0, i
, bi
)
3862 df_ref def
= DF_REG_DEF_CHAIN (i
);
3863 rtx def_insn
= DF_REF_INSN (def
);
3864 basic_block def_block
= BLOCK_FOR_INSN (def_insn
);
3865 bitmap def_bb_local
= bb_local
+ def_block
->index
;
3866 bitmap def_bb_moveable
= bb_moveable_reg_sets
+ def_block
->index
;
3867 bitmap def_bb_transp
= bb_transp_live
+ def_block
->index
;
3868 bool local_to_bb_p
= bitmap_bit_p (def_bb_local
, i
);
3869 rtx use_insn
= closest_uses
[i
];
3870 df_ref
*def_insn_use_rec
= DF_INSN_USES (def_insn
);
3872 bool all_transp
= true;
3874 if (!REG_P (DF_REF_REG (def
)))
3880 fprintf (dump_file
, "Reg %u not local to one basic block\n",
3884 if (reg_equiv_init (i
) != NULL_RTX
)
3887 fprintf (dump_file
, "Ignoring reg %u with equiv init insn\n",
3891 if (!rtx_moveable_p (&PATTERN (def_insn
), OP_IN
))
3894 fprintf (dump_file
, "Found def insn %d for %d to be not moveable\n",
3895 INSN_UID (def_insn
), i
);
3899 fprintf (dump_file
, "Examining insn %d, def for %d\n",
3900 INSN_UID (def_insn
), i
);
3901 while (*def_insn_use_rec
!= NULL
)
3903 df_ref use
= *def_insn_use_rec
;
3904 unsigned regno
= DF_REF_REGNO (use
);
3905 if (bitmap_bit_p (&unusable_as_input
, regno
))
3909 fprintf (dump_file
, " found unusable input reg %u.\n", regno
);
3912 if (!bitmap_bit_p (def_bb_transp
, regno
))
3914 if (bitmap_bit_p (def_bb_moveable
, regno
)
3915 && !control_flow_insn_p (use_insn
)
3917 && !sets_cc0_p (use_insn
)
3921 if (modified_between_p (DF_REF_REG (use
), def_insn
, use_insn
))
3923 rtx x
= NEXT_INSN (def_insn
);
3924 while (!modified_in_p (DF_REF_REG (use
), x
))
3926 gcc_assert (x
!= use_insn
);
3930 fprintf (dump_file
, " input reg %u modified but insn %d moveable\n",
3931 regno
, INSN_UID (x
));
3932 emit_insn_after (PATTERN (x
), use_insn
);
3933 set_insn_deleted (x
);
3938 fprintf (dump_file
, " input reg %u modified between def and use\n",
3951 if (!dbg_cnt (ira_move
))
3954 fprintf (dump_file
, " all ok%s\n", all_transp
? " and transp" : "");
3958 rtx def_reg
= DF_REF_REG (def
);
3959 rtx newreg
= ira_create_new_reg (def_reg
);
3960 if (validate_change (def_insn
, DF_REF_LOC (def
), newreg
, 0))
3962 unsigned nregno
= REGNO (newreg
);
3963 emit_insn_before (gen_move_insn (def_reg
, newreg
), use_insn
);
3965 VEC_replace (rtx
, pseudo_replaced_reg
, nregno
, def_reg
);
3972 bitmap_clear (bb_local
+ bb
->index
);
3973 bitmap_clear (bb_transp_live
+ bb
->index
);
3974 bitmap_clear (bb_moveable_reg_sets
+ bb
->index
);
3976 bitmap_clear (&interesting
);
3977 bitmap_clear (&unusable_as_input
);
3979 free (closest_uses
);
3981 free (bb_transp_live
);
3982 free (bb_moveable_reg_sets
);
3984 last_moveable_pseudo
= max_reg_num ();
3986 fix_reg_equiv_init ();
3988 regstat_free_n_sets_and_refs ();
3990 regstat_init_n_sets_and_refs ();
3991 regstat_compute_ri ();
3992 free_dominance_info (CDI_DOMINATORS
);
3995 /* Perform the second half of the transformation started in
3996 find_moveable_pseudos. We look for instances where the newly introduced
3997 pseudo remains unallocated, and remove it by moving the definition to
3998 just before its use, replacing the move instruction generated by
3999 find_moveable_pseudos. */
4001 move_unallocated_pseudos (void)
4004 for (i
= first_moveable_pseudo
; i
< last_moveable_pseudo
; i
++)
4005 if (reg_renumber
[i
] < 0)
4007 int idx
= i
- first_moveable_pseudo
;
4008 rtx other_reg
= VEC_index (rtx
, pseudo_replaced_reg
, idx
);
4009 rtx def_insn
= DF_REF_INSN (DF_REG_DEF_CHAIN (i
));
4010 /* The use must follow all definitions of OTHER_REG, so we can
4011 insert the new definition immediately after any of them. */
4012 df_ref other_def
= DF_REG_DEF_CHAIN (REGNO (other_reg
));
4013 rtx move_insn
= DF_REF_INSN (other_def
);
4014 rtx newinsn
= emit_insn_after (PATTERN (def_insn
), move_insn
);
4019 fprintf (dump_file
, "moving def of %d (insn %d now) ",
4020 REGNO (other_reg
), INSN_UID (def_insn
));
4022 delete_insn (move_insn
);
4023 while ((other_def
= DF_REG_DEF_CHAIN (REGNO (other_reg
))))
4024 delete_insn (DF_REF_INSN (other_def
));
4025 delete_insn (def_insn
);
4027 set
= single_set (newinsn
);
4028 success
= validate_change (newinsn
, &SET_DEST (set
), other_reg
, 0);
4029 gcc_assert (success
);
4031 fprintf (dump_file
, " %d) rather than keep unallocated replacement %d\n",
4032 INSN_UID (newinsn
), i
);
4033 SET_REG_N_REFS (i
, 0);
4038 /* All natural loops. */
4039 struct loops ira_loops
;
4041 /* True if we have allocno conflicts. It is false for non-optimized
4042 mode or when the conflict table is too big. */
4043 bool ira_conflicts_p
;
4045 /* Saved between IRA and reload. */
4046 static int saved_flag_ira_share_spill_slots
;
4048 /* This is the main entry of IRA. */
4053 int max_regno_before_ira
, ira_max_point_before_emit
;
4056 if (flag_caller_saves
)
4057 init_caller_save ();
4059 if (flag_ira_verbose
< 10)
4061 internal_flag_ira_verbose
= flag_ira_verbose
;
4066 internal_flag_ira_verbose
= flag_ira_verbose
- 10;
4067 ira_dump_file
= stderr
;
4070 ira_conflicts_p
= optimize
> 0;
4071 setup_prohibited_mode_move_regs ();
4073 df_note_add_problem ();
4077 df_live_add_problem ();
4078 df_live_set_all_dirty ();
4080 #ifdef ENABLE_CHECKING
4081 df
->changeable_flags
|= DF_VERIFY_SCHEDULED
;
4084 df_clear_flags (DF_NO_INSN_RESCAN
);
4085 regstat_init_n_sets_and_refs ();
4086 regstat_compute_ri ();
4088 /* If we are not optimizing, then this is the only place before
4089 register allocation where dataflow is done. And that is needed
4090 to generate these warnings. */
4092 generate_setjmp_warnings ();
4094 /* Determine if the current function is a leaf before running IRA
4095 since this can impact optimizations done by the prologue and
4096 epilogue thus changing register elimination offsets. */
4097 current_function_is_leaf
= leaf_function_p ();
4099 if (resize_reg_info () && flag_ira_loop_pressure
)
4100 ira_set_pseudo_classes (ira_dump_file
);
4102 rebuild_p
= update_equiv_regs ();
4104 #ifndef IRA_NO_OBSTACK
4105 gcc_obstack_init (&ira_obstack
);
4107 bitmap_obstack_initialize (&ira_bitmap_obstack
);
4110 max_regno
= max_reg_num ();
4111 ira_reg_equiv_len
= max_regno
;
4112 ira_reg_equiv_invariant_p
4113 = (bool *) ira_allocate (max_regno
* sizeof (bool));
4114 memset (ira_reg_equiv_invariant_p
, 0, max_regno
* sizeof (bool));
4115 ira_reg_equiv_const
= (rtx
*) ira_allocate (max_regno
* sizeof (rtx
));
4116 memset (ira_reg_equiv_const
, 0, max_regno
* sizeof (rtx
));
4117 find_reg_equiv_invariant_const ();
4120 timevar_push (TV_JUMP
);
4121 rebuild_jump_labels (get_insns ());
4122 if (purge_all_dead_edges ())
4123 delete_unreachable_blocks ();
4124 timevar_pop (TV_JUMP
);
4128 allocated_reg_info_size
= max_reg_num ();
4130 /* It is not worth to do such improvement when we use a simple
4131 allocation because of -O0 usage or because the function is too
4133 if (ira_conflicts_p
)
4134 find_moveable_pseudos ();
4136 max_regno_before_ira
= max_reg_num ();
4137 ira_setup_eliminable_regset ();
4139 ira_overall_cost
= ira_reg_cost
= ira_mem_cost
= 0;
4140 ira_load_cost
= ira_store_cost
= ira_shuffle_cost
= 0;
4141 ira_move_loops_num
= ira_additional_jumps_num
= 0;
4143 ira_assert (current_loops
== NULL
);
4144 if (flag_ira_region
== IRA_REGION_ALL
|| flag_ira_region
== IRA_REGION_MIXED
)
4146 flow_loops_find (&ira_loops
);
4147 record_loop_exits ();
4148 current_loops
= &ira_loops
;
4151 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
4152 fprintf (ira_dump_file
, "Building IRA IR\n");
4153 loops_p
= ira_build ();
4155 ira_assert (ira_conflicts_p
|| !loops_p
);
4157 saved_flag_ira_share_spill_slots
= flag_ira_share_spill_slots
;
4158 if (too_high_register_pressure_p () || cfun
->calls_setjmp
)
4159 /* It is just wasting compiler's time to pack spilled pseudos into
4160 stack slots in this case -- prohibit it. We also do this if
4161 there is setjmp call because a variable not modified between
4162 setjmp and longjmp the compiler is required to preserve its
4163 value and sharing slots does not guarantee it. */
4164 flag_ira_share_spill_slots
= FALSE
;
4168 ira_max_point_before_emit
= ira_max_point
;
4170 ira_initiate_emit_data ();
4174 if (ira_conflicts_p
)
4176 max_regno
= max_reg_num ();
4179 ira_initiate_assign ();
4184 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
4185 fprintf (ira_dump_file
, "Flattening IR\n");
4186 ira_flattening (max_regno_before_ira
, ira_max_point_before_emit
);
4187 /* New insns were generated: add notes and recalculate live
4191 flow_loops_find (&ira_loops
);
4192 record_loop_exits ();
4193 current_loops
= &ira_loops
;
4195 setup_allocno_assignment_flags ();
4196 ira_initiate_assign ();
4197 ira_reassign_conflict_allocnos (max_regno
);
4201 ira_finish_emit_data ();
4203 setup_reg_renumber ();
4205 calculate_allocation_cost ();
4207 #ifdef ENABLE_IRA_CHECKING
4208 if (ira_conflicts_p
)
4209 check_allocation ();
4212 if (delete_trivially_dead_insns (get_insns (), max_reg_num ()))
4215 if (max_regno
!= max_regno_before_ira
)
4217 regstat_free_n_sets_and_refs ();
4219 regstat_init_n_sets_and_refs ();
4220 regstat_compute_ri ();
4223 overall_cost_before
= ira_overall_cost
;
4224 if (! ira_conflicts_p
)
4228 fix_reg_equiv_init ();
4230 #ifdef ENABLE_IRA_CHECKING
4231 print_redundant_copies ();
4234 ira_spilled_reg_stack_slots_num
= 0;
4235 ira_spilled_reg_stack_slots
4236 = ((struct ira_spilled_reg_stack_slot
*)
4237 ira_allocate (max_regno
4238 * sizeof (struct ira_spilled_reg_stack_slot
)));
4239 memset (ira_spilled_reg_stack_slots
, 0,
4240 max_regno
* sizeof (struct ira_spilled_reg_stack_slot
));
4242 allocate_initial_values (reg_equivs
);
4244 /* See comment for find_moveable_pseudos call. */
4245 if (ira_conflicts_p
)
4246 move_unallocated_pseudos ();
4255 if (flag_ira_verbose
< 10)
4256 ira_dump_file
= dump_file
;
4258 df_set_flags (DF_NO_INSN_RESCAN
);
4259 build_insn_chain ();
4261 need_dce
= reload (get_insns (), ira_conflicts_p
);
4263 timevar_push (TV_IRA
);
4265 if (ira_conflicts_p
)
4267 ira_free (ira_spilled_reg_stack_slots
);
4269 ira_finish_assign ();
4271 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
4272 && overall_cost_before
!= ira_overall_cost
)
4273 fprintf (ira_dump_file
, "+++Overall after reload %d\n", ira_overall_cost
);
4276 flag_ira_share_spill_slots
= saved_flag_ira_share_spill_slots
;
4278 if (current_loops
!= NULL
)
4280 flow_loops_free (&ira_loops
);
4281 free_dominance_info (CDI_DOMINATORS
);
4284 bb
->loop_father
= NULL
;
4285 current_loops
= NULL
;
4288 regstat_free_n_sets_and_refs ();
4292 cleanup_cfg (CLEANUP_EXPENSIVE
);
4294 ira_free (ira_reg_equiv_invariant_p
);
4295 ira_free (ira_reg_equiv_const
);
4298 bitmap_obstack_release (&ira_bitmap_obstack
);
4299 #ifndef IRA_NO_OBSTACK
4300 obstack_free (&ira_obstack
, NULL
);
4303 /* The code after the reload has changed so much that at this point
4304 we might as well just rescan everything. Note that
4305 df_rescan_all_insns is not going to help here because it does not
4306 touch the artificial uses and defs. */
4307 df_finish_pass (true);
4309 df_live_add_problem ();
4310 df_scan_alloc (NULL
);
4316 if (need_dce
&& optimize
)
4319 timevar_pop (TV_IRA
);
4322 /* Run the integrated register allocator. */
4324 rest_of_handle_ira (void)
4330 struct rtl_opt_pass pass_ira
=
4336 rest_of_handle_ira
, /* execute */
4339 0, /* static_pass_number */
4341 0, /* properties_required */
4342 0, /* properties_provided */
4343 0, /* properties_destroyed */
4344 0, /* todo_flags_start */
4345 0, /* todo_flags_finish */
4350 rest_of_handle_reload (void)
4356 struct rtl_opt_pass pass_reload
=
4360 "reload", /* name */
4362 rest_of_handle_reload
, /* execute */
4365 0, /* static_pass_number */
4366 TV_RELOAD
, /* tv_id */
4367 0, /* properties_required */
4368 0, /* properties_provided */
4369 0, /* properties_destroyed */
4370 0, /* todo_flags_start */
4371 TODO_ggc_collect
/* todo_flags_finish */