1 /* Integrated Register Allocator (IRA) entry point.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011
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"
388 struct target_ira default_target_ira;
389 struct target_ira_int default_target_ira_int;
390 #if SWITCHABLE_TARGET
391 struct target_ira *this_target_ira = &default_target_ira;
392 struct target_ira_int *this_target_ira_int = &default_target_ira_int;
395 /* A modified value of flag `-fira-verbose' used internally. */
396 int internal_flag_ira_verbose;
398 /* Dump file of the allocator if it is not NULL. */
401 /* The number of elements in the following array. */
402 int ira_spilled_reg_stack_slots_num;
404 /* The following array contains info about spilled pseudo-registers
405 stack slots used in current function so far. */
406 struct ira_spilled_reg_stack_slot *ira_spilled_reg_stack_slots;
408 /* Correspondingly overall cost of the allocation, cost of the
409 allocnos assigned to hard-registers, cost of the allocnos assigned
410 to memory, cost of loads, stores and register move insns generated
411 for pseudo-register live range splitting (see ira-emit.c). */
412 int ira_overall_cost;
413 int ira_reg_cost, ira_mem_cost;
414 int ira_load_cost, ira_store_cost, ira_shuffle_cost;
415 int ira_move_loops_num, ira_additional_jumps_num;
417 /* All registers that can be eliminated. */
419 HARD_REG_SET eliminable_regset;
421 /* Temporary hard reg set used for a different calculation. */
422 static HARD_REG_SET temp_hard_regset;
426 /* The function sets up the map IRA_REG_MODE_HARD_REGSET. */
428 setup_reg_mode_hard_regset (void)
430 int i, m, hard_regno;
432 for (m = 0; m < NUM_MACHINE_MODES; m++)
433 for (hard_regno = 0; hard_regno < FIRST_PSEUDO_REGISTER; hard_regno++)
435 CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset[hard_regno][m]);
436 for (i = hard_regno_nregs[hard_regno][m] - 1; i >= 0; i--)
437 if (hard_regno + i < FIRST_PSEUDO_REGISTER)
438 SET_HARD_REG_BIT (ira_reg_mode_hard_regset[hard_regno][m],
444 #define no_unit_alloc_regs \
445 (this_target_ira_int->x_no_unit_alloc_regs)
447 /* The function sets up the three arrays declared above. */
449 setup_class_hard_regs (void)
451 int cl, i, hard_regno, n;
452 HARD_REG_SET processed_hard_reg_set;
454 ira_assert (SHRT_MAX >= FIRST_PSEUDO_REGISTER);
455 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
457 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
458 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
459 CLEAR_HARD_REG_SET (processed_hard_reg_set);
460 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
462 ira_non_ordered_class_hard_regs[cl][i] = -1;
463 ira_class_hard_reg_index[cl][i] = -1;
465 for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
467 #ifdef REG_ALLOC_ORDER
468 hard_regno = reg_alloc_order[i];
472 if (TEST_HARD_REG_BIT (processed_hard_reg_set, hard_regno))
474 SET_HARD_REG_BIT (processed_hard_reg_set, hard_regno);
475 if (! TEST_HARD_REG_BIT (temp_hard_regset, hard_regno))
476 ira_class_hard_reg_index[cl][hard_regno] = -1;
479 ira_class_hard_reg_index[cl][hard_regno] = n;
480 ira_class_hard_regs[cl][n++] = hard_regno;
483 ira_class_hard_regs_num[cl] = n;
484 for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
485 if (TEST_HARD_REG_BIT (temp_hard_regset, i))
486 ira_non_ordered_class_hard_regs[cl][n++] = i;
487 ira_assert (ira_class_hard_regs_num[cl] == n);
491 /* Set up IRA_AVAILABLE_CLASS_REGS. */
493 setup_available_class_regs (void)
497 memset (ira_available_class_regs, 0, sizeof (ira_available_class_regs));
498 for (i = 0; i < N_REG_CLASSES; i++)
500 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
501 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
502 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
503 if (TEST_HARD_REG_BIT (temp_hard_regset, j))
504 ira_available_class_regs[i]++;
508 /* Set up global variables defining info about hard registers for the
509 allocation. These depend on USE_HARD_FRAME_P whose TRUE value means
510 that we can use the hard frame pointer for the allocation. */
512 setup_alloc_regs (bool use_hard_frame_p)
514 #ifdef ADJUST_REG_ALLOC_ORDER
515 ADJUST_REG_ALLOC_ORDER;
517 COPY_HARD_REG_SET (no_unit_alloc_regs, fixed_reg_set);
518 if (! use_hard_frame_p)
519 SET_HARD_REG_BIT (no_unit_alloc_regs, HARD_FRAME_POINTER_REGNUM);
520 setup_class_hard_regs ();
521 setup_available_class_regs ();
526 #define alloc_reg_class_subclasses \
527 (this_target_ira_int->x_alloc_reg_class_subclasses)
529 /* Initialize the table of subclasses of each reg class. */
531 setup_reg_subclasses (void)
534 HARD_REG_SET temp_hard_regset2;
536 for (i = 0; i < N_REG_CLASSES; i++)
537 for (j = 0; j < N_REG_CLASSES; j++)
538 alloc_reg_class_subclasses[i][j] = LIM_REG_CLASSES;
540 for (i = 0; i < N_REG_CLASSES; i++)
542 if (i == (int) NO_REGS)
545 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
546 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
547 if (hard_reg_set_empty_p (temp_hard_regset))
549 for (j = 0; j < N_REG_CLASSES; j++)
554 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[j]);
555 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
556 if (! hard_reg_set_subset_p (temp_hard_regset,
559 p = &alloc_reg_class_subclasses[j][0];
560 while (*p != LIM_REG_CLASSES) p++;
561 *p = (enum reg_class) i;
568 /* Set up IRA_MEMORY_MOVE_COST and IRA_MAX_MEMORY_MOVE_COST. */
570 setup_class_subset_and_memory_move_costs (void)
572 int cl, cl2, mode, cost;
573 HARD_REG_SET temp_hard_regset2;
575 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
576 ira_memory_move_cost[mode][NO_REGS][0]
577 = ira_memory_move_cost[mode][NO_REGS][1] = SHRT_MAX;
578 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
580 if (cl != (int) NO_REGS)
581 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
583 ira_max_memory_move_cost[mode][cl][0]
584 = ira_memory_move_cost[mode][cl][0]
585 = memory_move_cost ((enum machine_mode) mode,
586 (reg_class_t) cl, false);
587 ira_max_memory_move_cost[mode][cl][1]
588 = ira_memory_move_cost[mode][cl][1]
589 = memory_move_cost ((enum machine_mode) mode,
590 (reg_class_t) cl, true);
591 /* Costs for NO_REGS are used in cost calculation on the
592 1st pass when the preferred register classes are not
593 known yet. In this case we take the best scenario. */
594 if (ira_memory_move_cost[mode][NO_REGS][0]
595 > ira_memory_move_cost[mode][cl][0])
596 ira_max_memory_move_cost[mode][NO_REGS][0]
597 = ira_memory_move_cost[mode][NO_REGS][0]
598 = ira_memory_move_cost[mode][cl][0];
599 if (ira_memory_move_cost[mode][NO_REGS][1]
600 > ira_memory_move_cost[mode][cl][1])
601 ira_max_memory_move_cost[mode][NO_REGS][1]
602 = ira_memory_move_cost[mode][NO_REGS][1]
603 = ira_memory_move_cost[mode][cl][1];
606 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
607 for (cl2 = (int) N_REG_CLASSES - 1; cl2 >= 0; cl2--)
609 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
610 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
611 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]);
612 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
613 ira_class_subset_p[cl][cl2]
614 = hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2);
615 if (! hard_reg_set_empty_p (temp_hard_regset2)
616 && hard_reg_set_subset_p (reg_class_contents[cl2],
617 reg_class_contents[cl]))
618 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
620 cost = ira_memory_move_cost[mode][cl2][0];
621 if (cost > ira_max_memory_move_cost[mode][cl][0])
622 ira_max_memory_move_cost[mode][cl][0] = cost;
623 cost = ira_memory_move_cost[mode][cl2][1];
624 if (cost > ira_max_memory_move_cost[mode][cl][1])
625 ira_max_memory_move_cost[mode][cl][1] = cost;
628 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
629 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
631 ira_memory_move_cost[mode][cl][0]
632 = ira_max_memory_move_cost[mode][cl][0];
633 ira_memory_move_cost[mode][cl][1]
634 = ira_max_memory_move_cost[mode][cl][1];
636 setup_reg_subclasses ();
641 /* Define the following macro if allocation through malloc if
643 #define IRA_NO_OBSTACK
645 #ifndef IRA_NO_OBSTACK
646 /* Obstack used for storing all dynamic data (except bitmaps) of the
648 static struct obstack ira_obstack;
651 /* Obstack used for storing all bitmaps of the IRA. */
652 static struct bitmap_obstack ira_bitmap_obstack;
654 /* Allocate memory of size LEN for IRA data. */
656 ira_allocate (size_t len)
660 #ifndef IRA_NO_OBSTACK
661 res = obstack_alloc (&ira_obstack, len);
668 /* Free memory ADDR allocated for IRA data. */
670 ira_free (void *addr ATTRIBUTE_UNUSED)
672 #ifndef IRA_NO_OBSTACK
680 /* Allocate and returns bitmap for IRA. */
682 ira_allocate_bitmap (void)
684 return BITMAP_ALLOC (&ira_bitmap_obstack);
687 /* Free bitmap B allocated for IRA. */
689 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED)
696 /* Output information about allocation of all allocnos (except for
697 caps) into file F. */
699 ira_print_disposition (FILE *f)
705 fprintf (f, "Disposition:");
706 max_regno = max_reg_num ();
707 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
708 for (a = ira_regno_allocno_map[i];
710 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
715 fprintf (f, " %4d:r%-4d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
716 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
717 fprintf (f, "b%-3d", bb->index);
719 fprintf (f, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
720 if (ALLOCNO_HARD_REGNO (a) >= 0)
721 fprintf (f, " %3d", ALLOCNO_HARD_REGNO (a));
728 /* Outputs information about allocation of all allocnos into
731 ira_debug_disposition (void)
733 ira_print_disposition (stderr);
738 /* Set up ira_stack_reg_pressure_class which is the biggest pressure
739 register class containing stack registers or NO_REGS if there are
740 no stack registers. To find this class, we iterate through all
741 register pressure classes and choose the first register pressure
742 class containing all the stack registers and having the biggest
745 setup_stack_reg_pressure_class (void)
747 ira_stack_reg_pressure_class = NO_REGS;
752 HARD_REG_SET temp_hard_regset2;
754 CLEAR_HARD_REG_SET (temp_hard_regset);
755 for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
756 SET_HARD_REG_BIT (temp_hard_regset, i);
758 for (i = 0; i < ira_pressure_classes_num; i++)
760 cl = ira_pressure_classes[i];
761 COPY_HARD_REG_SET (temp_hard_regset2, temp_hard_regset);
762 AND_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
763 size = hard_reg_set_size (temp_hard_regset2);
767 ira_stack_reg_pressure_class = cl;
774 /* Find pressure classes which are register classes for which we
775 calculate register pressure in IRA, register pressure sensitive
776 insn scheduling, and register pressure sensitive loop invariant
779 To make register pressure calculation easy, we always use
780 non-intersected register pressure classes. A move of hard
781 registers from one register pressure class is not more expensive
782 than load and store of the hard registers. Most likely an allocno
783 class will be a subset of a register pressure class and in many
784 cases a register pressure class. That makes usage of register
785 pressure classes a good approximation to find a high register
788 setup_pressure_classes (void)
790 int cost, i, n, curr;
792 enum reg_class pressure_classes[N_REG_CLASSES];
794 HARD_REG_SET temp_hard_regset2;
798 for (cl = 0; cl < N_REG_CLASSES; cl++)
800 if (ira_available_class_regs[cl] == 0)
802 if (ira_available_class_regs[cl] != 1)
804 /* Check that the moves between any hard registers of the
805 current class are not more expensive for a legal mode
806 than load/store of the hard registers of the current
807 class. Such class is a potential candidate to be a
808 register pressure class. */
809 for (m = 0; m < NUM_MACHINE_MODES; m++)
811 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
812 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
813 AND_COMPL_HARD_REG_SET (temp_hard_regset,
814 ira_prohibited_class_mode_regs[cl][m]);
815 if (hard_reg_set_empty_p (temp_hard_regset))
817 ira_init_register_move_cost_if_necessary ((enum machine_mode) m);
818 cost = ira_register_move_cost[m][cl][cl];
819 if (cost <= ira_max_memory_move_cost[m][cl][1]
820 || cost <= ira_max_memory_move_cost[m][cl][0])
823 if (m >= NUM_MACHINE_MODES)
828 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
829 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
830 /* Remove so far added pressure classes which are subset of the
831 current candidate class. Prefer GENERAL_REGS as a pressure
832 register class to another class containing the same
833 allocatable hard registers. We do this because machine
834 dependent cost hooks might give wrong costs for the latter
835 class but always give the right cost for the former class
837 for (i = 0; i < n; i++)
839 cl2 = pressure_classes[i];
840 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]);
841 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
842 if (hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2)
843 && (! hard_reg_set_equal_p (temp_hard_regset, temp_hard_regset2)
844 || cl2 == (int) GENERAL_REGS))
846 pressure_classes[curr++] = (enum reg_class) cl2;
850 if (hard_reg_set_subset_p (temp_hard_regset2, temp_hard_regset)
851 && (! hard_reg_set_equal_p (temp_hard_regset2, temp_hard_regset)
852 || cl == (int) GENERAL_REGS))
854 if (hard_reg_set_equal_p (temp_hard_regset2, temp_hard_regset))
856 pressure_classes[curr++] = (enum reg_class) cl2;
858 /* If the current candidate is a subset of a so far added
859 pressure class, don't add it to the list of the pressure
862 pressure_classes[curr++] = (enum reg_class) cl;
865 #ifdef ENABLE_IRA_CHECKING
867 HARD_REG_SET ignore_hard_regs;
869 /* Check pressure classes correctness: here we check that hard
870 registers from all register pressure classes contains all hard
871 registers available for the allocation. */
872 CLEAR_HARD_REG_SET (temp_hard_regset);
873 CLEAR_HARD_REG_SET (temp_hard_regset2);
874 COPY_HARD_REG_SET (ignore_hard_regs, no_unit_alloc_regs);
875 for (cl = 0; cl < LIM_REG_CLASSES; cl++)
877 /* For some targets (like MIPS with MD_REGS), there are some
878 classes with hard registers available for allocation but
879 not able to hold value of any mode. */
880 for (m = 0; m < NUM_MACHINE_MODES; m++)
881 if (contains_reg_of_mode[cl][m])
883 if (m >= NUM_MACHINE_MODES)
885 IOR_HARD_REG_SET (ignore_hard_regs, reg_class_contents[cl]);
888 for (i = 0; i < n; i++)
889 if ((int) pressure_classes[i] == cl)
891 IOR_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
893 IOR_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
895 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
896 /* Some targets (like SPARC with ICC reg) have alocatable regs
897 for which no reg class is defined. */
898 if (REGNO_REG_CLASS (i) == NO_REGS)
899 SET_HARD_REG_BIT (ignore_hard_regs, i);
900 AND_COMPL_HARD_REG_SET (temp_hard_regset, ignore_hard_regs);
901 AND_COMPL_HARD_REG_SET (temp_hard_regset2, ignore_hard_regs);
902 ira_assert (hard_reg_set_subset_p (temp_hard_regset2, temp_hard_regset));
905 ira_pressure_classes_num = 0;
906 for (i = 0; i < n; i++)
908 cl = (int) pressure_classes[i];
909 ira_reg_pressure_class_p[cl] = true;
910 ira_pressure_classes[ira_pressure_classes_num++] = (enum reg_class) cl;
912 setup_stack_reg_pressure_class ();
915 /* Set up IRA_ALLOCNO_CLASSES, IRA_ALLOCNO_CLASSES_NUM,
916 IRA_IMPORTANT_CLASSES, and IRA_IMPORTANT_CLASSES_NUM.
918 Target may have many subtargets and not all target hard regiters can
919 be used for allocation, e.g. x86 port in 32-bit mode can not use
920 hard registers introduced in x86-64 like r8-r15). Some classes
921 might have the same allocatable hard registers, e.g. INDEX_REGS
922 and GENERAL_REGS in x86 port in 32-bit mode. To decrease different
923 calculations efforts we introduce allocno classes which contain
924 unique non-empty sets of allocatable hard-registers.
926 Pseudo class cost calculation in ira-costs.c is very expensive.
927 Therefore we are trying to decrease number of classes involved in
928 such calculation. Register classes used in the cost calculation
929 are called important classes. They are allocno classes and other
930 non-empty classes whose allocatable hard register sets are inside
931 of an allocno class hard register set. From the first sight, it
932 looks like that they are just allocno classes. It is not true. In
933 example of x86-port in 32-bit mode, allocno classes will contain
934 GENERAL_REGS but not LEGACY_REGS (because allocatable hard
935 registers are the same for the both classes). The important
936 classes will contain GENERAL_REGS and LEGACY_REGS. It is done
937 because a machine description insn constraint may refers for
938 LEGACY_REGS and code in ira-costs.c is mostly base on investigation
939 of the insn constraints. */
941 setup_allocno_and_important_classes (void)
945 HARD_REG_SET temp_hard_regset2;
946 static enum reg_class classes[LIM_REG_CLASSES + 1];
949 /* Collect classes which contain unique sets of allocatable hard
950 registers. Prefer GENERAL_REGS to other classes containing the
951 same set of hard registers. */
952 for (i = 0; i < LIM_REG_CLASSES; i++)
954 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
955 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
956 for (j = 0; j < n; j++)
959 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
960 AND_COMPL_HARD_REG_SET (temp_hard_regset2,
962 if (hard_reg_set_equal_p (temp_hard_regset,
967 classes[n++] = (enum reg_class) i;
968 else if (i == GENERAL_REGS)
969 /* Prefer general regs. For i386 example, it means that
970 we prefer GENERAL_REGS over INDEX_REGS or LEGACY_REGS
971 (all of them consists of the same available hard
973 classes[j] = (enum reg_class) i;
975 classes[n] = LIM_REG_CLASSES;
977 /* Set up classes which can be used for allocnos as classes
978 conatining non-empty unique sets of allocatable hard
980 ira_allocno_classes_num = 0;
981 for (i = 0; (cl = classes[i]) != LIM_REG_CLASSES; i++)
983 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
984 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
985 if (hard_reg_set_empty_p (temp_hard_regset))
987 ira_allocno_classes[ira_allocno_classes_num++] = (enum reg_class) cl;
989 ira_important_classes_num = 0;
990 /* Add non-allocno classes containing to non-empty set of
991 allocatable hard regs. */
992 for (cl = 0; cl < N_REG_CLASSES; cl++)
994 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
995 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
996 if (! hard_reg_set_empty_p (temp_hard_regset))
999 for (j = 0; j < ira_allocno_classes_num; j++)
1001 COPY_HARD_REG_SET (temp_hard_regset2,
1002 reg_class_contents[ira_allocno_classes[j]]);
1003 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
1004 if ((enum reg_class) cl == ira_allocno_classes[j])
1006 else if (hard_reg_set_subset_p (temp_hard_regset,
1010 if (set_p && j >= ira_allocno_classes_num)
1011 ira_important_classes[ira_important_classes_num++]
1012 = (enum reg_class) cl;
1015 /* Now add allocno classes to the important classes. */
1016 for (j = 0; j < ira_allocno_classes_num; j++)
1017 ira_important_classes[ira_important_classes_num++]
1018 = ira_allocno_classes[j];
1019 for (cl = 0; cl < N_REG_CLASSES; cl++)
1021 ira_reg_allocno_class_p[cl] = false;
1022 ira_reg_pressure_class_p[cl] = false;
1024 for (j = 0; j < ira_allocno_classes_num; j++)
1025 ira_reg_allocno_class_p[ira_allocno_classes[j]] = true;
1026 setup_pressure_classes ();
1029 /* Setup translation in CLASS_TRANSLATE of all classes into a class
1030 given by array CLASSES of length CLASSES_NUM. The function is used
1031 make translation any reg class to an allocno class or to an
1032 pressure class. This translation is necessary for some
1033 calculations when we can use only allocno or pressure classes and
1034 such translation represents an approximate representation of all
1037 The translation in case when allocatable hard register set of a
1038 given class is subset of allocatable hard register set of a class
1039 in CLASSES is pretty simple. We use smallest classes from CLASSES
1040 containing a given class. If allocatable hard register set of a
1041 given class is not a subset of any corresponding set of a class
1042 from CLASSES, we use the cheapest (with load/store point of view)
1043 class from CLASSES whose set intersects with given class set */
1045 setup_class_translate_array (enum reg_class *class_translate,
1046 int classes_num, enum reg_class *classes)
1049 enum reg_class aclass, best_class, *cl_ptr;
1050 int i, cost, min_cost, best_cost;
1052 for (cl = 0; cl < N_REG_CLASSES; cl++)
1053 class_translate[cl] = NO_REGS;
1055 for (i = 0; i < classes_num; i++)
1057 aclass = classes[i];
1058 for (cl_ptr = &alloc_reg_class_subclasses[aclass][0];
1059 (cl = *cl_ptr) != LIM_REG_CLASSES;
1061 if (class_translate[cl] == NO_REGS)
1062 class_translate[cl] = aclass;
1063 class_translate[aclass] = aclass;
1065 /* For classes which are not fully covered by one of given classes
1066 (in other words covered by more one given class), use the
1068 for (cl = 0; cl < N_REG_CLASSES; cl++)
1070 if (cl == NO_REGS || class_translate[cl] != NO_REGS)
1072 best_class = NO_REGS;
1073 best_cost = INT_MAX;
1074 for (i = 0; i < classes_num; i++)
1076 aclass = classes[i];
1077 COPY_HARD_REG_SET (temp_hard_regset,
1078 reg_class_contents[aclass]);
1079 AND_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
1080 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1081 if (! hard_reg_set_empty_p (temp_hard_regset))
1084 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1086 cost = (ira_memory_move_cost[mode][cl][0]
1087 + ira_memory_move_cost[mode][cl][1]);
1088 if (min_cost > cost)
1091 if (best_class == NO_REGS || best_cost > min_cost)
1093 best_class = aclass;
1094 best_cost = min_cost;
1098 class_translate[cl] = best_class;
1102 /* Set up array IRA_ALLOCNO_CLASS_TRANSLATE and
1103 IRA_PRESSURE_CLASS_TRANSLATE. */
1105 setup_class_translate (void)
1107 setup_class_translate_array (ira_allocno_class_translate,
1108 ira_allocno_classes_num, ira_allocno_classes);
1109 setup_class_translate_array (ira_pressure_class_translate,
1110 ira_pressure_classes_num, ira_pressure_classes);
1113 /* Order numbers of allocno classes in original target allocno class
1114 array, -1 for non-allocno classes. */
1115 static int allocno_class_order[N_REG_CLASSES];
1117 /* The function used to sort the important classes. */
1119 comp_reg_classes_func (const void *v1p, const void *v2p)
1121 enum reg_class cl1 = *(const enum reg_class *) v1p;
1122 enum reg_class cl2 = *(const enum reg_class *) v2p;
1123 enum reg_class tcl1, tcl2;
1126 tcl1 = ira_allocno_class_translate[cl1];
1127 tcl2 = ira_allocno_class_translate[cl2];
1128 if (tcl1 != NO_REGS && tcl2 != NO_REGS
1129 && (diff = allocno_class_order[tcl1] - allocno_class_order[tcl2]) != 0)
1131 return (int) cl1 - (int) cl2;
1134 /* For correct work of function setup_reg_class_relation we need to
1135 reorder important classes according to the order of their allocno
1136 classes. It places important classes containing the same
1137 allocatable hard register set adjacent to each other and allocno
1138 class with the allocatable hard register set right after the other
1139 important classes with the same set.
1141 In example from comments of function
1142 setup_allocno_and_important_classes, it places LEGACY_REGS and
1143 GENERAL_REGS close to each other and GENERAL_REGS is after
1146 reorder_important_classes (void)
1150 for (i = 0; i < N_REG_CLASSES; i++)
1151 allocno_class_order[i] = -1;
1152 for (i = 0; i < ira_allocno_classes_num; i++)
1153 allocno_class_order[ira_allocno_classes[i]] = i;
1154 qsort (ira_important_classes, ira_important_classes_num,
1155 sizeof (enum reg_class), comp_reg_classes_func);
1156 for (i = 0; i < ira_important_classes_num; i++)
1157 ira_important_class_nums[ira_important_classes[i]] = i;
1160 /* Set up IRA_REG_CLASS_SUBUNION, IRA_REG_CLASS_SUPERUNION,
1161 IRA_REG_CLASS_SUPER_CLASSES, IRA_REG_CLASSES_INTERSECT, and
1162 IRA_REG_CLASSES_INTERSECT_P. For the meaning of the relations,
1163 please see corresponding comments in ira-int.h. */
1165 setup_reg_class_relations (void)
1167 int i, cl1, cl2, cl3;
1168 HARD_REG_SET intersection_set, union_set, temp_set2;
1169 bool important_class_p[N_REG_CLASSES];
1171 memset (important_class_p, 0, sizeof (important_class_p));
1172 for (i = 0; i < ira_important_classes_num; i++)
1173 important_class_p[ira_important_classes[i]] = true;
1174 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1176 ira_reg_class_super_classes[cl1][0] = LIM_REG_CLASSES;
1177 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1179 ira_reg_classes_intersect_p[cl1][cl2] = false;
1180 ira_reg_class_intersect[cl1][cl2] = NO_REGS;
1181 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl1]);
1182 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1183 COPY_HARD_REG_SET (temp_set2, reg_class_contents[cl2]);
1184 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1185 if (hard_reg_set_empty_p (temp_hard_regset)
1186 && hard_reg_set_empty_p (temp_set2))
1188 /* The both classes have no allocatable hard registers
1189 -- take all class hard registers into account and use
1190 reg_class_subunion and reg_class_superunion. */
1193 cl3 = reg_class_subclasses[cl1][i];
1194 if (cl3 == LIM_REG_CLASSES)
1196 if (reg_class_subset_p (ira_reg_class_intersect[cl1][cl2],
1197 (enum reg_class) cl3))
1198 ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
1200 ira_reg_class_subunion[cl1][cl2] = reg_class_subunion[cl1][cl2];
1201 ira_reg_class_superunion[cl1][cl2] = reg_class_superunion[cl1][cl2];
1204 ira_reg_classes_intersect_p[cl1][cl2]
1205 = hard_reg_set_intersect_p (temp_hard_regset, temp_set2);
1206 if (important_class_p[cl1] && important_class_p[cl2]
1207 && hard_reg_set_subset_p (temp_hard_regset, temp_set2))
1209 /* CL1 and CL2 are important classes and CL1 allocatable
1210 hard register set is inside of CL2 allocatable hard
1211 registers -- make CL1 a superset of CL2. */
1214 p = &ira_reg_class_super_classes[cl1][0];
1215 while (*p != LIM_REG_CLASSES)
1217 *p++ = (enum reg_class) cl2;
1218 *p = LIM_REG_CLASSES;
1220 ira_reg_class_subunion[cl1][cl2] = NO_REGS;
1221 ira_reg_class_superunion[cl1][cl2] = NO_REGS;
1222 COPY_HARD_REG_SET (intersection_set, reg_class_contents[cl1]);
1223 AND_HARD_REG_SET (intersection_set, reg_class_contents[cl2]);
1224 AND_COMPL_HARD_REG_SET (intersection_set, no_unit_alloc_regs);
1225 COPY_HARD_REG_SET (union_set, reg_class_contents[cl1]);
1226 IOR_HARD_REG_SET (union_set, reg_class_contents[cl2]);
1227 AND_COMPL_HARD_REG_SET (union_set, no_unit_alloc_regs);
1228 for (i = 0; i < ira_important_classes_num; i++)
1230 cl3 = ira_important_classes[i];
1231 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl3]);
1232 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1233 if (hard_reg_set_subset_p (temp_hard_regset, intersection_set))
1235 /* CL3 allocatable hard register set is inside of
1236 intersection of allocatable hard register sets
1240 reg_class_contents[(int)
1241 ira_reg_class_intersect[cl1][cl2]]);
1242 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1243 if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1244 /* If the allocatable hard register sets are the
1245 same, prefer GENERAL_REGS or the smallest
1246 class for debugging purposes. */
1247 || (hard_reg_set_equal_p (temp_hard_regset, temp_set2)
1248 && (cl3 == GENERAL_REGS
1249 || (ira_reg_class_intersect[cl1][cl2] != GENERAL_REGS
1250 && hard_reg_set_subset_p
1251 (reg_class_contents[cl3],
1253 [(int) ira_reg_class_intersect[cl1][cl2]])))))
1254 ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
1256 if (hard_reg_set_subset_p (temp_hard_regset, union_set))
1258 /* CL3 allocatbale hard register set is inside of
1259 union of allocatable hard register sets of CL1
1263 reg_class_contents[(int) ira_reg_class_subunion[cl1][cl2]]);
1264 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1265 if (ira_reg_class_subunion[cl1][cl2] == NO_REGS
1266 || (hard_reg_set_subset_p (temp_set2, temp_hard_regset)
1268 && (! hard_reg_set_equal_p (temp_set2,
1270 || cl3 == GENERAL_REGS
1271 /* If the allocatable hard register sets are the
1272 same, prefer GENERAL_REGS or the smallest
1273 class for debugging purposes. */
1274 || (ira_reg_class_subunion[cl1][cl2] != GENERAL_REGS
1275 && hard_reg_set_subset_p
1276 (reg_class_contents[cl3],
1278 [(int) ira_reg_class_subunion[cl1][cl2]])))))
1279 ira_reg_class_subunion[cl1][cl2] = (enum reg_class) cl3;
1281 if (hard_reg_set_subset_p (union_set, temp_hard_regset))
1283 /* CL3 allocatable hard register set contains union
1284 of allocatable hard register sets of CL1 and
1288 reg_class_contents[(int) ira_reg_class_superunion[cl1][cl2]]);
1289 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1290 if (ira_reg_class_superunion[cl1][cl2] == NO_REGS
1291 || (hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1293 && (! hard_reg_set_equal_p (temp_set2,
1295 || cl3 == GENERAL_REGS
1296 /* If the allocatable hard register sets are the
1297 same, prefer GENERAL_REGS or the smallest
1298 class for debugging purposes. */
1299 || (ira_reg_class_superunion[cl1][cl2] != GENERAL_REGS
1300 && hard_reg_set_subset_p
1301 (reg_class_contents[cl3],
1303 [(int) ira_reg_class_superunion[cl1][cl2]])))))
1304 ira_reg_class_superunion[cl1][cl2] = (enum reg_class) cl3;
1311 /* Output all possible allocno classes and the translation map into
1314 print_classes (FILE *f, bool pressure_p)
1316 int classes_num = (pressure_p
1317 ? ira_pressure_classes_num : ira_allocno_classes_num);
1318 enum reg_class *classes = (pressure_p
1319 ? ira_pressure_classes : ira_allocno_classes);
1320 enum reg_class *class_translate = (pressure_p
1321 ? ira_pressure_class_translate
1322 : ira_allocno_class_translate);
1323 static const char *const reg_class_names[] = REG_CLASS_NAMES;
1326 fprintf (f, "%s classes:\n", pressure_p ? "Pressure" : "Allocno");
1327 for (i = 0; i < classes_num; i++)
1328 fprintf (f, " %s", reg_class_names[classes[i]]);
1329 fprintf (f, "\nClass translation:\n");
1330 for (i = 0; i < N_REG_CLASSES; i++)
1331 fprintf (f, " %s -> %s\n", reg_class_names[i],
1332 reg_class_names[class_translate[i]]);
1335 /* Output all possible allocno and translation classes and the
1336 translation maps into stderr. */
1338 ira_debug_allocno_classes (void)
1340 print_classes (stderr, false);
1341 print_classes (stderr, true);
1344 /* Set up different arrays concerning class subsets, allocno and
1345 important classes. */
1347 find_reg_classes (void)
1349 setup_allocno_and_important_classes ();
1350 setup_class_translate ();
1351 reorder_important_classes ();
1352 setup_reg_class_relations ();
1357 /* Set up the array above. */
1359 setup_hard_regno_aclass (void)
1363 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1366 ira_hard_regno_allocno_class[i]
1367 = (TEST_HARD_REG_BIT (no_unit_alloc_regs, i)
1369 : ira_allocno_class_translate[REGNO_REG_CLASS (i)]);
1373 ira_hard_regno_allocno_class[i] = NO_REGS;
1374 for (j = 0; j < ira_allocno_classes_num; j++)
1376 cl = ira_allocno_classes[j];
1377 if (ira_class_hard_reg_index[cl][i] >= 0)
1379 ira_hard_regno_allocno_class[i] = cl;
1389 /* Form IRA_REG_CLASS_MAX_NREGS and IRA_REG_CLASS_MIN_NREGS maps. */
1391 setup_reg_class_nregs (void)
1395 for (m = 0; m < MAX_MACHINE_MODE; m++)
1397 for (cl = 0; cl < N_REG_CLASSES; cl++)
1398 ira_reg_class_max_nregs[cl][m]
1399 = ira_reg_class_min_nregs[cl][m]
1400 = CLASS_MAX_NREGS ((enum reg_class) cl, (enum machine_mode) m);
1401 for (cl = 0; cl < N_REG_CLASSES; cl++)
1403 (cl2 = alloc_reg_class_subclasses[cl][i]) != LIM_REG_CLASSES;
1405 if (ira_reg_class_min_nregs[cl2][m]
1406 < ira_reg_class_min_nregs[cl][m])
1407 ira_reg_class_min_nregs[cl][m] = ira_reg_class_min_nregs[cl2][m];
1413 /* Set up IRA_PROHIBITED_CLASS_MODE_REGS. */
1415 setup_prohibited_class_mode_regs (void)
1417 int j, k, hard_regno, cl;
1419 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
1421 for (j = 0; j < NUM_MACHINE_MODES; j++)
1423 CLEAR_HARD_REG_SET (ira_prohibited_class_mode_regs[cl][j]);
1424 for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1426 hard_regno = ira_class_hard_regs[cl][k];
1427 if (! HARD_REGNO_MODE_OK (hard_regno, (enum machine_mode) j))
1428 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1435 /* Clarify IRA_PROHIBITED_CLASS_MODE_REGS by excluding hard registers
1436 spanning from one register pressure class to another one. It is
1437 called after defining the pressure classes. */
1439 clarify_prohibited_class_mode_regs (void)
1441 int j, k, hard_regno, cl, pclass, nregs;
1443 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
1444 for (j = 0; j < NUM_MACHINE_MODES; j++)
1445 for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1447 hard_regno = ira_class_hard_regs[cl][k];
1448 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j], hard_regno))
1450 nregs = hard_regno_nregs[hard_regno][j];
1451 if (hard_regno + nregs > FIRST_PSEUDO_REGISTER)
1453 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1457 pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)];
1458 for (nregs-- ;nregs >= 0; nregs--)
1459 if (((enum reg_class) pclass
1460 != ira_pressure_class_translate[REGNO_REG_CLASS
1461 (hard_regno + nregs)]))
1463 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1472 /* Allocate and initialize IRA_REGISTER_MOVE_COST,
1473 IRA_MAX_REGISTER_MOVE_COST, IRA_MAY_MOVE_IN_COST,
1474 IRA_MAY_MOVE_OUT_COST, IRA_MAX_MAY_MOVE_IN_COST, and
1475 IRA_MAX_MAY_MOVE_OUT_COST for MODE if it is not done yet. */
1477 ira_init_register_move_cost (enum machine_mode mode)
1481 ira_assert (ira_register_move_cost[mode] == NULL
1482 && ira_max_register_move_cost[mode] == NULL
1483 && ira_may_move_in_cost[mode] == NULL
1484 && ira_may_move_out_cost[mode] == NULL
1485 && ira_max_may_move_in_cost[mode] == NULL
1486 && ira_max_may_move_out_cost[mode] == NULL);
1487 if (move_cost[mode] == NULL)
1488 init_move_cost (mode);
1489 ira_register_move_cost[mode] = move_cost[mode];
1490 /* Don't use ira_allocate because the tables exist out of scope of a
1492 ira_max_register_move_cost[mode]
1493 = (move_table *) xmalloc (sizeof (move_table) * N_REG_CLASSES);
1494 memcpy (ira_max_register_move_cost[mode], ira_register_move_cost[mode],
1495 sizeof (move_table) * N_REG_CLASSES);
1496 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1498 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl1]);
1499 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1500 if (hard_reg_set_empty_p (temp_hard_regset))
1502 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1503 if (hard_reg_set_subset_p (reg_class_contents[cl1],
1504 reg_class_contents[cl2]))
1505 for (cl3 = 0; cl3 < N_REG_CLASSES; cl3++)
1507 if (ira_max_register_move_cost[mode][cl2][cl3]
1508 < ira_register_move_cost[mode][cl1][cl3])
1509 ira_max_register_move_cost[mode][cl2][cl3]
1510 = ira_register_move_cost[mode][cl1][cl3];
1511 if (ira_max_register_move_cost[mode][cl3][cl2]
1512 < ira_register_move_cost[mode][cl3][cl1])
1513 ira_max_register_move_cost[mode][cl3][cl2]
1514 = ira_register_move_cost[mode][cl3][cl1];
1517 ira_may_move_in_cost[mode]
1518 = (move_table *) xmalloc (sizeof (move_table) * N_REG_CLASSES);
1519 memcpy (ira_may_move_in_cost[mode], may_move_in_cost[mode],
1520 sizeof (move_table) * N_REG_CLASSES);
1521 ira_may_move_out_cost[mode]
1522 = (move_table *) xmalloc (sizeof (move_table) * N_REG_CLASSES);
1523 memcpy (ira_may_move_out_cost[mode], may_move_out_cost[mode],
1524 sizeof (move_table) * N_REG_CLASSES);
1525 ira_max_may_move_in_cost[mode]
1526 = (move_table *) xmalloc (sizeof (move_table) * N_REG_CLASSES);
1527 memcpy (ira_max_may_move_in_cost[mode], ira_max_register_move_cost[mode],
1528 sizeof (move_table) * N_REG_CLASSES);
1529 ira_max_may_move_out_cost[mode]
1530 = (move_table *) xmalloc (sizeof (move_table) * N_REG_CLASSES);
1531 memcpy (ira_max_may_move_out_cost[mode], ira_max_register_move_cost[mode],
1532 sizeof (move_table) * N_REG_CLASSES);
1533 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1535 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1537 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl2]);
1538 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1539 if (hard_reg_set_empty_p (temp_hard_regset))
1541 if (ira_class_subset_p[cl1][cl2])
1542 ira_may_move_in_cost[mode][cl1][cl2] = 0;
1543 if (ira_class_subset_p[cl2][cl1])
1544 ira_may_move_out_cost[mode][cl1][cl2] = 0;
1545 if (ira_class_subset_p[cl1][cl2])
1546 ira_max_may_move_in_cost[mode][cl1][cl2] = 0;
1547 if (ira_class_subset_p[cl2][cl1])
1548 ira_max_may_move_out_cost[mode][cl1][cl2] = 0;
1549 ira_register_move_cost[mode][cl1][cl2]
1550 = ira_max_register_move_cost[mode][cl1][cl2];
1551 ira_may_move_in_cost[mode][cl1][cl2]
1552 = ira_max_may_move_in_cost[mode][cl1][cl2];
1553 ira_may_move_out_cost[mode][cl1][cl2]
1554 = ira_max_may_move_out_cost[mode][cl1][cl2];
1561 /* This is called once during compiler work. It sets up
1562 different arrays whose values don't depend on the compiled
1565 ira_init_once (void)
1569 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1571 ira_register_move_cost[mode] = NULL;
1572 ira_max_register_move_cost[mode] = NULL;
1573 ira_may_move_in_cost[mode] = NULL;
1574 ira_may_move_out_cost[mode] = NULL;
1575 ira_max_may_move_in_cost[mode] = NULL;
1576 ira_max_may_move_out_cost[mode] = NULL;
1578 ira_init_costs_once ();
1581 /* Free ira_max_register_move_cost, ira_may_move_in_cost,
1582 ira_may_move_out_cost, ira_max_may_move_in_cost, and
1583 ira_max_may_move_out_cost for each mode. */
1585 free_register_move_costs (void)
1589 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1591 free (ira_max_register_move_cost[mode]);
1592 free (ira_may_move_in_cost[mode]);
1593 free (ira_may_move_out_cost[mode]);
1594 free (ira_max_may_move_in_cost[mode]);
1595 free (ira_max_may_move_out_cost[mode]);
1596 ira_register_move_cost[mode] = NULL;
1597 ira_max_register_move_cost[mode] = NULL;
1598 ira_may_move_in_cost[mode] = NULL;
1599 ira_may_move_out_cost[mode] = NULL;
1600 ira_max_may_move_in_cost[mode] = NULL;
1601 ira_max_may_move_out_cost[mode] = NULL;
1605 /* This is called every time when register related information is
1610 free_register_move_costs ();
1611 setup_reg_mode_hard_regset ();
1612 setup_alloc_regs (flag_omit_frame_pointer != 0);
1613 setup_class_subset_and_memory_move_costs ();
1614 setup_reg_class_nregs ();
1615 setup_prohibited_class_mode_regs ();
1616 find_reg_classes ();
1617 clarify_prohibited_class_mode_regs ();
1618 setup_hard_regno_aclass ();
1622 /* Function called once at the end of compiler work. */
1624 ira_finish_once (void)
1626 ira_finish_costs_once ();
1627 free_register_move_costs ();
1631 #define ira_prohibited_mode_move_regs_initialized_p \
1632 (this_target_ira_int->x_ira_prohibited_mode_move_regs_initialized_p)
1634 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS. */
1636 setup_prohibited_mode_move_regs (void)
1639 rtx test_reg1, test_reg2, move_pat, move_insn;
1641 if (ira_prohibited_mode_move_regs_initialized_p)
1643 ira_prohibited_mode_move_regs_initialized_p = true;
1644 test_reg1 = gen_rtx_REG (VOIDmode, 0);
1645 test_reg2 = gen_rtx_REG (VOIDmode, 0);
1646 move_pat = gen_rtx_SET (VOIDmode, test_reg1, test_reg2);
1647 move_insn = gen_rtx_INSN (VOIDmode, 0, 0, 0, 0, move_pat, 0, -1, 0);
1648 for (i = 0; i < NUM_MACHINE_MODES; i++)
1650 SET_HARD_REG_SET (ira_prohibited_mode_move_regs[i]);
1651 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1653 if (! HARD_REGNO_MODE_OK (j, (enum machine_mode) i))
1655 SET_REGNO_RAW (test_reg1, j);
1656 PUT_MODE (test_reg1, (enum machine_mode) i);
1657 SET_REGNO_RAW (test_reg2, j);
1658 PUT_MODE (test_reg2, (enum machine_mode) i);
1659 INSN_CODE (move_insn) = -1;
1660 recog_memoized (move_insn);
1661 if (INSN_CODE (move_insn) < 0)
1663 extract_insn (move_insn);
1664 if (! constrain_operands (1))
1666 CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs[i], j);
1673 /* Return nonzero if REGNO is a particularly bad choice for reloading X. */
1675 ira_bad_reload_regno_1 (int regno, rtx x)
1679 enum reg_class pref;
1681 /* We only deal with pseudo regs. */
1682 if (! x || GET_CODE (x) != REG)
1685 x_regno = REGNO (x);
1686 if (x_regno < FIRST_PSEUDO_REGISTER)
1689 /* If the pseudo prefers REGNO explicitly, then do not consider
1690 REGNO a bad spill choice. */
1691 pref = reg_preferred_class (x_regno);
1692 if (reg_class_size[pref] == 1)
1693 return !TEST_HARD_REG_BIT (reg_class_contents[pref], regno);
1695 /* If the pseudo conflicts with REGNO, then we consider REGNO a
1696 poor choice for a reload regno. */
1697 a = ira_regno_allocno_map[x_regno];
1698 n = ALLOCNO_NUM_OBJECTS (a);
1699 for (i = 0; i < n; i++)
1701 ira_object_t obj = ALLOCNO_OBJECT (a, i);
1702 if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), regno))
1708 /* Return nonzero if REGNO is a particularly bad choice for reloading
1711 ira_bad_reload_regno (int regno, rtx in, rtx out)
1713 return (ira_bad_reload_regno_1 (regno, in)
1714 || ira_bad_reload_regno_1 (regno, out));
1717 /* Return TRUE if *LOC contains an asm. */
1719 insn_contains_asm_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
1723 if (GET_CODE (*loc) == ASM_OPERANDS)
1729 /* Return TRUE if INSN contains an ASM. */
1731 insn_contains_asm (rtx insn)
1733 return for_each_rtx (&insn, insn_contains_asm_1, NULL);
1736 /* Add register clobbers from asm statements. */
1738 compute_regs_asm_clobbered (void)
1745 FOR_BB_INSNS_REVERSE (bb, insn)
1749 if (insn_contains_asm (insn))
1750 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
1752 df_ref def = *def_rec;
1753 unsigned int dregno = DF_REF_REGNO (def);
1754 if (HARD_REGISTER_NUM_P (dregno))
1755 add_to_hard_reg_set (&crtl->asm_clobbers,
1756 GET_MODE (DF_REF_REAL_REG (def)),
1764 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and REGS_EVER_LIVE. */
1766 ira_setup_eliminable_regset (void)
1768 #ifdef ELIMINABLE_REGS
1770 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
1772 /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
1773 sp for alloca. So we can't eliminate the frame pointer in that
1774 case. At some point, we should improve this by emitting the
1775 sp-adjusting insns for this case. */
1777 = (! flag_omit_frame_pointer
1778 || (cfun->calls_alloca && EXIT_IGNORE_STACK)
1779 /* We need the frame pointer to catch stack overflow exceptions
1780 if the stack pointer is moving. */
1781 || (flag_stack_check && STACK_CHECK_MOVING_SP)
1782 || crtl->accesses_prior_frames
1783 || crtl->stack_realign_needed
1784 || targetm.frame_pointer_required ());
1786 frame_pointer_needed = need_fp;
1788 COPY_HARD_REG_SET (ira_no_alloc_regs, no_unit_alloc_regs);
1789 CLEAR_HARD_REG_SET (eliminable_regset);
1791 compute_regs_asm_clobbered ();
1793 /* Build the regset of all eliminable registers and show we can't
1794 use those that we already know won't be eliminated. */
1795 #ifdef ELIMINABLE_REGS
1796 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
1799 = (! targetm.can_eliminate (eliminables[i].from, eliminables[i].to)
1800 || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp));
1802 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, eliminables[i].from))
1804 SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
1807 SET_HARD_REG_BIT (ira_no_alloc_regs, eliminables[i].from);
1809 else if (cannot_elim)
1810 error ("%s cannot be used in asm here",
1811 reg_names[eliminables[i].from]);
1813 df_set_regs_ever_live (eliminables[i].from, true);
1815 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
1816 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM))
1818 SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
1820 SET_HARD_REG_BIT (ira_no_alloc_regs, HARD_FRAME_POINTER_REGNUM);
1823 error ("%s cannot be used in asm here",
1824 reg_names[HARD_FRAME_POINTER_REGNUM]);
1826 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
1830 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM))
1832 SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
1834 SET_HARD_REG_BIT (ira_no_alloc_regs, FRAME_POINTER_REGNUM);
1837 error ("%s cannot be used in asm here", reg_names[FRAME_POINTER_REGNUM]);
1839 df_set_regs_ever_live (FRAME_POINTER_REGNUM, true);
1845 /* The length of the following two arrays. */
1846 int ira_reg_equiv_len;
1848 /* The element value is TRUE if the corresponding regno value is
1850 bool *ira_reg_equiv_invariant_p;
1852 /* The element value is equiv constant of given pseudo-register or
1854 rtx *ira_reg_equiv_const;
1856 /* Set up the two arrays declared above. */
1858 find_reg_equiv_invariant_const (void)
1862 rtx list, insn, note, constant, x;
1864 for (i = FIRST_PSEUDO_REGISTER; i < VEC_length (reg_equivs_t, reg_equivs); i++)
1866 constant = NULL_RTX;
1867 invariant_p = false;
1868 for (list = reg_equiv_init (i); list != NULL_RTX; list = XEXP (list, 1))
1870 insn = XEXP (list, 0);
1871 note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
1873 if (note == NULL_RTX)
1878 if (! CONSTANT_P (x)
1879 || ! flag_pic || LEGITIMATE_PIC_OPERAND_P (x))
1881 /* It can happen that a REG_EQUIV note contains a MEM
1882 that is not a legitimate memory operand. As later
1883 stages of the reload assume that all addresses found
1884 in the reg_equiv_* arrays were originally legitimate,
1885 we ignore such REG_EQUIV notes. */
1886 if (memory_operand (x, VOIDmode))
1887 invariant_p = MEM_READONLY_P (x);
1888 else if (function_invariant_p (x))
1890 if (GET_CODE (x) == PLUS
1891 || x == frame_pointer_rtx || x == arg_pointer_rtx)
1898 ira_reg_equiv_invariant_p[i] = invariant_p;
1899 ira_reg_equiv_const[i] = constant;
1905 /* Vector of substitutions of register numbers,
1906 used to map pseudo regs into hardware regs.
1907 This is set up as a result of register allocation.
1908 Element N is the hard reg assigned to pseudo reg N,
1909 or is -1 if no hard reg was assigned.
1910 If N is a hard reg number, element N is N. */
1911 short *reg_renumber;
1913 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
1914 the allocation found by IRA. */
1916 setup_reg_renumber (void)
1918 int regno, hard_regno;
1920 ira_allocno_iterator ai;
1922 caller_save_needed = 0;
1923 FOR_EACH_ALLOCNO (a, ai)
1925 /* There are no caps at this point. */
1926 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
1927 if (! ALLOCNO_ASSIGNED_P (a))
1928 /* It can happen if A is not referenced but partially anticipated
1929 somewhere in a region. */
1930 ALLOCNO_ASSIGNED_P (a) = true;
1931 ira_free_allocno_updated_costs (a);
1932 hard_regno = ALLOCNO_HARD_REGNO (a);
1933 regno = ALLOCNO_REGNO (a);
1934 reg_renumber[regno] = (hard_regno < 0 ? -1 : hard_regno);
1935 if (hard_regno >= 0)
1938 enum reg_class pclass;
1941 pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)];
1942 nwords = ALLOCNO_NUM_OBJECTS (a);
1943 for (i = 0; i < nwords; i++)
1945 obj = ALLOCNO_OBJECT (a, i);
1946 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
1947 reg_class_contents[pclass]);
1949 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
1950 && ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
1953 ira_assert (!optimize || flag_caller_saves
1954 || regno >= ira_reg_equiv_len
1955 || ira_reg_equiv_const[regno]
1956 || ira_reg_equiv_invariant_p[regno]);
1957 caller_save_needed = 1;
1963 /* Set up allocno assignment flags for further allocation
1966 setup_allocno_assignment_flags (void)
1970 ira_allocno_iterator ai;
1972 FOR_EACH_ALLOCNO (a, ai)
1974 if (! ALLOCNO_ASSIGNED_P (a))
1975 /* It can happen if A is not referenced but partially anticipated
1976 somewhere in a region. */
1977 ira_free_allocno_updated_costs (a);
1978 hard_regno = ALLOCNO_HARD_REGNO (a);
1979 /* Don't assign hard registers to allocnos which are destination
1980 of removed store at the end of loop. It has no sense to keep
1981 the same value in different hard registers. It is also
1982 impossible to assign hard registers correctly to such
1983 allocnos because the cost info and info about intersected
1984 calls are incorrect for them. */
1985 ALLOCNO_ASSIGNED_P (a) = (hard_regno >= 0
1986 || ALLOCNO_EMIT_DATA (a)->mem_optimized_dest_p
1987 || (ALLOCNO_MEMORY_COST (a)
1988 - ALLOCNO_CLASS_COST (a)) < 0);
1989 ira_assert (hard_regno < 0
1990 || ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
1992 [ALLOCNO_CLASS (a)]));
1996 /* Evaluate overall allocation cost and the costs for using hard
1997 registers and memory for allocnos. */
1999 calculate_allocation_cost (void)
2001 int hard_regno, cost;
2003 ira_allocno_iterator ai;
2005 ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
2006 FOR_EACH_ALLOCNO (a, ai)
2008 hard_regno = ALLOCNO_HARD_REGNO (a);
2009 ira_assert (hard_regno < 0
2010 || ! ira_hard_reg_not_in_set_p
2011 (hard_regno, ALLOCNO_MODE (a),
2012 reg_class_contents[ALLOCNO_CLASS (a)]));
2015 cost = ALLOCNO_MEMORY_COST (a);
2016 ira_mem_cost += cost;
2018 else if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
2020 cost = (ALLOCNO_HARD_REG_COSTS (a)
2021 [ira_class_hard_reg_index
2022 [ALLOCNO_CLASS (a)][hard_regno]]);
2023 ira_reg_cost += cost;
2027 cost = ALLOCNO_CLASS_COST (a);
2028 ira_reg_cost += cost;
2030 ira_overall_cost += cost;
2033 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2035 fprintf (ira_dump_file,
2036 "+++Costs: overall %d, reg %d, mem %d, ld %d, st %d, move %d\n",
2037 ira_overall_cost, ira_reg_cost, ira_mem_cost,
2038 ira_load_cost, ira_store_cost, ira_shuffle_cost);
2039 fprintf (ira_dump_file, "+++ move loops %d, new jumps %d\n",
2040 ira_move_loops_num, ira_additional_jumps_num);
2045 #ifdef ENABLE_IRA_CHECKING
2046 /* Check the correctness of the allocation. We do need this because
2047 of complicated code to transform more one region internal
2048 representation into one region representation. */
2050 check_allocation (void)
2053 int hard_regno, nregs, conflict_nregs;
2054 ira_allocno_iterator ai;
2056 FOR_EACH_ALLOCNO (a, ai)
2058 int n = ALLOCNO_NUM_OBJECTS (a);
2061 if (ALLOCNO_CAP_MEMBER (a) != NULL
2062 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
2064 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
2066 /* We allocated a single hard register. */
2069 /* We allocated multiple hard registers, and we will test
2070 conflicts in a granularity of single hard regs. */
2073 for (i = 0; i < n; i++)
2075 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2076 ira_object_t conflict_obj;
2077 ira_object_conflict_iterator oci;
2078 int this_regno = hard_regno;
2081 if (WORDS_BIG_ENDIAN)
2082 this_regno += n - i - 1;
2086 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2088 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2089 int conflict_hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
2090 if (conflict_hard_regno < 0)
2095 [conflict_hard_regno][ALLOCNO_MODE (conflict_a)]);
2097 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1
2098 && conflict_nregs == ALLOCNO_NUM_OBJECTS (conflict_a))
2100 if (WORDS_BIG_ENDIAN)
2101 conflict_hard_regno += (ALLOCNO_NUM_OBJECTS (conflict_a)
2102 - OBJECT_SUBWORD (conflict_obj) - 1);
2104 conflict_hard_regno += OBJECT_SUBWORD (conflict_obj);
2108 if ((conflict_hard_regno <= this_regno
2109 && this_regno < conflict_hard_regno + conflict_nregs)
2110 || (this_regno <= conflict_hard_regno
2111 && conflict_hard_regno < this_regno + nregs))
2113 fprintf (stderr, "bad allocation for %d and %d\n",
2114 ALLOCNO_REGNO (a), ALLOCNO_REGNO (conflict_a));
2123 /* Fix values of array REG_EQUIV_INIT after live range splitting done
2126 fix_reg_equiv_init (void)
2128 unsigned int max_regno = max_reg_num ();
2129 int i, new_regno, max;
2130 rtx x, prev, next, insn, set;
2132 if (VEC_length (reg_equivs_t, reg_equivs) < max_regno)
2134 max = VEC_length (reg_equivs_t, reg_equivs);
2136 for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
2137 for (prev = NULL_RTX, x = reg_equiv_init (i);
2143 set = single_set (insn);
2144 ira_assert (set != NULL_RTX
2145 && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))));
2146 if (REG_P (SET_DEST (set))
2147 && ((int) REGNO (SET_DEST (set)) == i
2148 || (int) ORIGINAL_REGNO (SET_DEST (set)) == i))
2149 new_regno = REGNO (SET_DEST (set));
2150 else if (REG_P (SET_SRC (set))
2151 && ((int) REGNO (SET_SRC (set)) == i
2152 || (int) ORIGINAL_REGNO (SET_SRC (set)) == i))
2153 new_regno = REGNO (SET_SRC (set));
2160 if (prev == NULL_RTX)
2161 reg_equiv_init (i) = next;
2163 XEXP (prev, 1) = next;
2164 XEXP (x, 1) = reg_equiv_init (new_regno);
2165 reg_equiv_init (new_regno) = x;
2171 #ifdef ENABLE_IRA_CHECKING
2172 /* Print redundant memory-memory copies. */
2174 print_redundant_copies (void)
2178 ira_copy_t cp, next_cp;
2179 ira_allocno_iterator ai;
2181 FOR_EACH_ALLOCNO (a, ai)
2183 if (ALLOCNO_CAP_MEMBER (a) != NULL)
2186 hard_regno = ALLOCNO_HARD_REGNO (a);
2187 if (hard_regno >= 0)
2189 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2191 next_cp = cp->next_first_allocno_copy;
2194 next_cp = cp->next_second_allocno_copy;
2195 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL
2196 && cp->insn != NULL_RTX
2197 && ALLOCNO_HARD_REGNO (cp->first) == hard_regno)
2198 fprintf (ira_dump_file,
2199 " Redundant move from %d(freq %d):%d\n",
2200 INSN_UID (cp->insn), cp->freq, hard_regno);
2206 /* Setup preferred and alternative classes for new pseudo-registers
2207 created by IRA starting with START. */
2209 setup_preferred_alternate_classes_for_new_pseudos (int start)
2212 int max_regno = max_reg_num ();
2214 for (i = start; i < max_regno; i++)
2216 old_regno = ORIGINAL_REGNO (regno_reg_rtx[i]);
2217 ira_assert (i != old_regno);
2218 setup_reg_classes (i, reg_preferred_class (old_regno),
2219 reg_alternate_class (old_regno),
2220 reg_allocno_class (old_regno));
2221 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2222 fprintf (ira_dump_file,
2223 " New r%d: setting preferred %s, alternative %s\n",
2224 i, reg_class_names[reg_preferred_class (old_regno)],
2225 reg_class_names[reg_alternate_class (old_regno)]);
2231 /* Regional allocation can create new pseudo-registers. This function
2232 expands some arrays for pseudo-registers. */
2234 expand_reg_info (int old_size)
2237 int size = max_reg_num ();
2240 for (i = old_size; i < size; i++)
2241 setup_reg_classes (i, GENERAL_REGS, ALL_REGS, GENERAL_REGS);
2244 /* Return TRUE if there is too high register pressure in the function.
2245 It is used to decide when stack slot sharing is worth to do. */
2247 too_high_register_pressure_p (void)
2250 enum reg_class pclass;
2252 for (i = 0; i < ira_pressure_classes_num; i++)
2254 pclass = ira_pressure_classes[i];
2255 if (ira_loop_tree_root->reg_pressure[pclass] > 10000)
2263 /* Indicate that hard register number FROM was eliminated and replaced with
2264 an offset from hard register number TO. The status of hard registers live
2265 at the start of a basic block is updated by replacing a use of FROM with
2269 mark_elimination (int from, int to)
2275 /* We don't use LIVE info in IRA. */
2276 bitmap r = DF_LR_IN (bb);
2278 if (REGNO_REG_SET_P (r, from))
2280 CLEAR_REGNO_REG_SET (r, from);
2281 SET_REGNO_REG_SET (r, to);
2290 /* Set when a REG_EQUIV note is found or created. Use to
2291 keep track of what memory accesses might be created later,
2295 /* The list of each instruction which initializes this register. */
2297 /* Loop depth is used to recognize equivalences which appear
2298 to be present within the same loop (or in an inner loop). */
2300 /* Nonzero if this had a preexisting REG_EQUIV note. */
2301 int is_arg_equivalence;
2302 /* Set when an attempt should be made to replace a register
2303 with the associated src_p entry. */
2307 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
2308 structure for that register. */
2309 static struct equivalence *reg_equiv;
2311 /* Used for communication between the following two functions: contains
2312 a MEM that we wish to ensure remains unchanged. */
2313 static rtx equiv_mem;
2315 /* Set nonzero if EQUIV_MEM is modified. */
2316 static int equiv_mem_modified;
2318 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
2319 Called via note_stores. */
2321 validate_equiv_mem_from_store (rtx dest, const_rtx set ATTRIBUTE_UNUSED,
2322 void *data ATTRIBUTE_UNUSED)
2325 && reg_overlap_mentioned_p (dest, equiv_mem))
2327 && true_dependence (dest, VOIDmode, equiv_mem, rtx_varies_p)))
2328 equiv_mem_modified = 1;
2331 /* Verify that no store between START and the death of REG invalidates
2332 MEMREF. MEMREF is invalidated by modifying a register used in MEMREF,
2333 by storing into an overlapping memory location, or with a non-const
2336 Return 1 if MEMREF remains valid. */
2338 validate_equiv_mem (rtx start, rtx reg, rtx memref)
2344 equiv_mem_modified = 0;
2346 /* If the memory reference has side effects or is volatile, it isn't a
2347 valid equivalence. */
2348 if (side_effects_p (memref))
2351 for (insn = start; insn && ! equiv_mem_modified; insn = NEXT_INSN (insn))
2353 if (! INSN_P (insn))
2356 if (find_reg_note (insn, REG_DEAD, reg))
2359 /* This used to ignore readonly memory and const/pure calls. The problem
2360 is the equivalent form may reference a pseudo which gets assigned a
2361 call clobbered hard reg. When we later replace REG with its
2362 equivalent form, the value in the call-clobbered reg has been
2363 changed and all hell breaks loose. */
2367 note_stores (PATTERN (insn), validate_equiv_mem_from_store, NULL);
2369 /* If a register mentioned in MEMREF is modified via an
2370 auto-increment, we lose the equivalence. Do the same if one
2371 dies; although we could extend the life, it doesn't seem worth
2374 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2375 if ((REG_NOTE_KIND (note) == REG_INC
2376 || REG_NOTE_KIND (note) == REG_DEAD)
2377 && REG_P (XEXP (note, 0))
2378 && reg_overlap_mentioned_p (XEXP (note, 0), memref))
2385 /* Returns zero if X is known to be invariant. */
2387 equiv_init_varies_p (rtx x)
2389 RTX_CODE code = GET_CODE (x);
2396 return !MEM_READONLY_P (x) || equiv_init_varies_p (XEXP (x, 0));
2408 return reg_equiv[REGNO (x)].replace == 0 && rtx_varies_p (x, 0);
2411 if (MEM_VOLATILE_P (x))
2420 fmt = GET_RTX_FORMAT (code);
2421 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2424 if (equiv_init_varies_p (XEXP (x, i)))
2427 else if (fmt[i] == 'E')
2430 for (j = 0; j < XVECLEN (x, i); j++)
2431 if (equiv_init_varies_p (XVECEXP (x, i, j)))
2438 /* Returns nonzero if X (used to initialize register REGNO) is movable.
2439 X is only movable if the registers it uses have equivalent initializations
2440 which appear to be within the same loop (or in an inner loop) and movable
2441 or if they are not candidates for local_alloc and don't vary. */
2443 equiv_init_movable_p (rtx x, int regno)
2447 enum rtx_code code = GET_CODE (x);
2452 return equiv_init_movable_p (SET_SRC (x), regno);
2467 return ((reg_equiv[REGNO (x)].loop_depth >= reg_equiv[regno].loop_depth
2468 && reg_equiv[REGNO (x)].replace)
2469 || (REG_BASIC_BLOCK (REGNO (x)) < NUM_FIXED_BLOCKS
2470 && ! rtx_varies_p (x, 0)));
2472 case UNSPEC_VOLATILE:
2476 if (MEM_VOLATILE_P (x))
2485 fmt = GET_RTX_FORMAT (code);
2486 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2490 if (! equiv_init_movable_p (XEXP (x, i), regno))
2494 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2495 if (! equiv_init_movable_p (XVECEXP (x, i, j), regno))
2503 /* TRUE if X uses any registers for which reg_equiv[REGNO].replace is
2506 contains_replace_regs (rtx x)
2510 enum rtx_code code = GET_CODE (x);
2527 return reg_equiv[REGNO (x)].replace;
2533 fmt = GET_RTX_FORMAT (code);
2534 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2538 if (contains_replace_regs (XEXP (x, i)))
2542 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2543 if (contains_replace_regs (XVECEXP (x, i, j)))
2551 /* TRUE if X references a memory location that would be affected by a store
2554 memref_referenced_p (rtx memref, rtx x)
2558 enum rtx_code code = GET_CODE (x);
2576 return (reg_equiv[REGNO (x)].replacement
2577 && memref_referenced_p (memref,
2578 reg_equiv[REGNO (x)].replacement));
2581 if (true_dependence (memref, VOIDmode, x, rtx_varies_p))
2586 /* If we are setting a MEM, it doesn't count (its address does), but any
2587 other SET_DEST that has a MEM in it is referencing the MEM. */
2588 if (MEM_P (SET_DEST (x)))
2590 if (memref_referenced_p (memref, XEXP (SET_DEST (x), 0)))
2593 else if (memref_referenced_p (memref, SET_DEST (x)))
2596 return memref_referenced_p (memref, SET_SRC (x));
2602 fmt = GET_RTX_FORMAT (code);
2603 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2607 if (memref_referenced_p (memref, XEXP (x, i)))
2611 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2612 if (memref_referenced_p (memref, XVECEXP (x, i, j)))
2620 /* TRUE if some insn in the range (START, END] references a memory location
2621 that would be affected by a store to MEMREF. */
2623 memref_used_between_p (rtx memref, rtx start, rtx end)
2627 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2628 insn = NEXT_INSN (insn))
2630 if (!NONDEBUG_INSN_P (insn))
2633 if (memref_referenced_p (memref, PATTERN (insn)))
2636 /* Nonconst functions may access memory. */
2637 if (CALL_P (insn) && (! RTL_CONST_CALL_P (insn)))
2644 /* Mark REG as having no known equivalence.
2645 Some instructions might have been processed before and furnished
2646 with REG_EQUIV notes for this register; these notes will have to be
2648 STORE is the piece of RTL that does the non-constant / conflicting
2649 assignment - a SET, CLOBBER or REG_INC note. It is currently not used,
2650 but needs to be there because this function is called from note_stores. */
2652 no_equiv (rtx reg, const_rtx store ATTRIBUTE_UNUSED,
2653 void *data ATTRIBUTE_UNUSED)
2660 regno = REGNO (reg);
2661 list = reg_equiv[regno].init_insns;
2662 if (list == const0_rtx)
2664 reg_equiv[regno].init_insns = const0_rtx;
2665 reg_equiv[regno].replacement = NULL_RTX;
2666 /* This doesn't matter for equivalences made for argument registers, we
2667 should keep their initialization insns. */
2668 if (reg_equiv[regno].is_arg_equivalence)
2670 reg_equiv_init (regno) = NULL_RTX;
2671 for (; list; list = XEXP (list, 1))
2673 rtx insn = XEXP (list, 0);
2674 remove_note (insn, find_reg_note (insn, REG_EQUIV, NULL_RTX));
2678 /* In DEBUG_INSN location adjust REGs from CLEARED_REGS bitmap to the
2679 equivalent replacement. */
2682 adjust_cleared_regs (rtx loc, const_rtx old_rtx ATTRIBUTE_UNUSED, void *data)
2686 bitmap cleared_regs = (bitmap) data;
2687 if (bitmap_bit_p (cleared_regs, REGNO (loc)))
2688 return simplify_replace_fn_rtx (*reg_equiv[REGNO (loc)].src_p,
2689 NULL_RTX, adjust_cleared_regs, data);
2694 /* Nonzero if we recorded an equivalence for a LABEL_REF. */
2695 static int recorded_label_ref;
2697 /* Find registers that are equivalent to a single value throughout the
2698 compilation (either because they can be referenced in memory or are
2699 set once from a single constant). Lower their priority for a
2702 If such a register is only referenced once, try substituting its
2703 value into the using insn. If it succeeds, we can eliminate the
2704 register completely.
2706 Initialize the REG_EQUIV_INIT array of initializing insns.
2708 Return non-zero if jump label rebuilding should be done. */
2710 update_equiv_regs (void)
2715 bitmap cleared_regs;
2717 /* We need to keep track of whether or not we recorded a LABEL_REF so
2718 that we know if the jump optimizer needs to be rerun. */
2719 recorded_label_ref = 0;
2721 reg_equiv = XCNEWVEC (struct equivalence, max_regno);
2724 init_alias_analysis ();
2726 /* Scan the insns and find which registers have equivalences. Do this
2727 in a separate scan of the insns because (due to -fcse-follow-jumps)
2728 a register can be set below its use. */
2731 loop_depth = bb->loop_depth;
2733 for (insn = BB_HEAD (bb);
2734 insn != NEXT_INSN (BB_END (bb));
2735 insn = NEXT_INSN (insn))
2742 if (! INSN_P (insn))
2745 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2746 if (REG_NOTE_KIND (note) == REG_INC)
2747 no_equiv (XEXP (note, 0), note, NULL);
2749 set = single_set (insn);
2751 /* If this insn contains more (or less) than a single SET,
2752 only mark all destinations as having no known equivalence. */
2755 note_stores (PATTERN (insn), no_equiv, NULL);
2758 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2762 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
2764 rtx part = XVECEXP (PATTERN (insn), 0, i);
2766 note_stores (part, no_equiv, NULL);
2770 dest = SET_DEST (set);
2771 src = SET_SRC (set);
2773 /* See if this is setting up the equivalence between an argument
2774 register and its stack slot. */
2775 note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
2778 gcc_assert (REG_P (dest));
2779 regno = REGNO (dest);
2781 /* Note that we don't want to clear reg_equiv_init even if there
2782 are multiple sets of this register. */
2783 reg_equiv[regno].is_arg_equivalence = 1;
2785 /* Record for reload that this is an equivalencing insn. */
2786 if (rtx_equal_p (src, XEXP (note, 0)))
2787 reg_equiv_init (regno)
2788 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init (regno));
2790 /* Continue normally in case this is a candidate for
2797 /* We only handle the case of a pseudo register being set
2798 once, or always to the same value. */
2799 /* ??? The mn10200 port breaks if we add equivalences for
2800 values that need an ADDRESS_REGS register and set them equivalent
2801 to a MEM of a pseudo. The actual problem is in the over-conservative
2802 handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
2803 calculate_needs, but we traditionally work around this problem
2804 here by rejecting equivalences when the destination is in a register
2805 that's likely spilled. This is fragile, of course, since the
2806 preferred class of a pseudo depends on all instructions that set
2810 || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER
2811 || reg_equiv[regno].init_insns == const0_rtx
2812 || (targetm.class_likely_spilled_p (reg_preferred_class (regno))
2813 && MEM_P (src) && ! reg_equiv[regno].is_arg_equivalence))
2815 /* This might be setting a SUBREG of a pseudo, a pseudo that is
2816 also set somewhere else to a constant. */
2817 note_stores (set, no_equiv, NULL);
2821 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
2823 /* cse sometimes generates function invariants, but doesn't put a
2824 REG_EQUAL note on the insn. Since this note would be redundant,
2825 there's no point creating it earlier than here. */
2826 if (! note && ! rtx_varies_p (src, 0))
2827 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
2829 /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
2830 since it represents a function call */
2831 if (note && GET_CODE (XEXP (note, 0)) == EXPR_LIST)
2834 if (DF_REG_DEF_COUNT (regno) != 1
2836 || rtx_varies_p (XEXP (note, 0), 0)
2837 || (reg_equiv[regno].replacement
2838 && ! rtx_equal_p (XEXP (note, 0),
2839 reg_equiv[regno].replacement))))
2841 no_equiv (dest, set, NULL);
2844 /* Record this insn as initializing this register. */
2845 reg_equiv[regno].init_insns
2846 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv[regno].init_insns);
2848 /* If this register is known to be equal to a constant, record that
2849 it is always equivalent to the constant. */
2850 if (DF_REG_DEF_COUNT (regno) == 1
2851 && note && ! rtx_varies_p (XEXP (note, 0), 0))
2853 rtx note_value = XEXP (note, 0);
2854 remove_note (insn, note);
2855 set_unique_reg_note (insn, REG_EQUIV, note_value);
2858 /* If this insn introduces a "constant" register, decrease the priority
2859 of that register. Record this insn if the register is only used once
2860 more and the equivalence value is the same as our source.
2862 The latter condition is checked for two reasons: First, it is an
2863 indication that it may be more efficient to actually emit the insn
2864 as written (if no registers are available, reload will substitute
2865 the equivalence). Secondly, it avoids problems with any registers
2866 dying in this insn whose death notes would be missed.
2868 If we don't have a REG_EQUIV note, see if this insn is loading
2869 a register used only in one basic block from a MEM. If so, and the
2870 MEM remains unchanged for the life of the register, add a REG_EQUIV
2873 note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
2875 if (note == 0 && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
2876 && MEM_P (SET_SRC (set))
2877 && validate_equiv_mem (insn, dest, SET_SRC (set)))
2878 note = set_unique_reg_note (insn, REG_EQUIV, copy_rtx (SET_SRC (set)));
2882 int regno = REGNO (dest);
2883 rtx x = XEXP (note, 0);
2885 /* If we haven't done so, record for reload that this is an
2886 equivalencing insn. */
2887 if (!reg_equiv[regno].is_arg_equivalence)
2888 reg_equiv_init (regno)
2889 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init (regno));
2891 /* Record whether or not we created a REG_EQUIV note for a LABEL_REF.
2892 We might end up substituting the LABEL_REF for uses of the
2893 pseudo here or later. That kind of transformation may turn an
2894 indirect jump into a direct jump, in which case we must rerun the
2895 jump optimizer to ensure that the JUMP_LABEL fields are valid. */
2896 if (GET_CODE (x) == LABEL_REF
2897 || (GET_CODE (x) == CONST
2898 && GET_CODE (XEXP (x, 0)) == PLUS
2899 && (GET_CODE (XEXP (XEXP (x, 0), 0)) == LABEL_REF)))
2900 recorded_label_ref = 1;
2902 reg_equiv[regno].replacement = x;
2903 reg_equiv[regno].src_p = &SET_SRC (set);
2904 reg_equiv[regno].loop_depth = loop_depth;
2906 /* Don't mess with things live during setjmp. */
2907 if (REG_LIVE_LENGTH (regno) >= 0 && optimize)
2909 /* Note that the statement below does not affect the priority
2911 REG_LIVE_LENGTH (regno) *= 2;
2913 /* If the register is referenced exactly twice, meaning it is
2914 set once and used once, indicate that the reference may be
2915 replaced by the equivalence we computed above. Do this
2916 even if the register is only used in one block so that
2917 dependencies can be handled where the last register is
2918 used in a different block (i.e. HIGH / LO_SUM sequences)
2919 and to reduce the number of registers alive across
2922 if (REG_N_REFS (regno) == 2
2923 && (rtx_equal_p (x, src)
2924 || ! equiv_init_varies_p (src))
2925 && NONJUMP_INSN_P (insn)
2926 && equiv_init_movable_p (PATTERN (insn), regno))
2927 reg_equiv[regno].replace = 1;
2936 /* A second pass, to gather additional equivalences with memory. This needs
2937 to be done after we know which registers we are going to replace. */
2939 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2944 if (! INSN_P (insn))
2947 set = single_set (insn);
2951 dest = SET_DEST (set);
2952 src = SET_SRC (set);
2954 /* If this sets a MEM to the contents of a REG that is only used
2955 in a single basic block, see if the register is always equivalent
2956 to that memory location and if moving the store from INSN to the
2957 insn that set REG is safe. If so, put a REG_EQUIV note on the
2960 Don't add a REG_EQUIV note if the insn already has one. The existing
2961 REG_EQUIV is likely more useful than the one we are adding.
2963 If one of the regs in the address has reg_equiv[REGNO].replace set,
2964 then we can't add this REG_EQUIV note. The reg_equiv[REGNO].replace
2965 optimization may move the set of this register immediately before
2966 insn, which puts it after reg_equiv[REGNO].init_insns, and hence
2967 the mention in the REG_EQUIV note would be to an uninitialized
2970 if (MEM_P (dest) && REG_P (src)
2971 && (regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
2972 && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
2973 && DF_REG_DEF_COUNT (regno) == 1
2974 && reg_equiv[regno].init_insns != 0
2975 && reg_equiv[regno].init_insns != const0_rtx
2976 && ! find_reg_note (XEXP (reg_equiv[regno].init_insns, 0),
2977 REG_EQUIV, NULL_RTX)
2978 && ! contains_replace_regs (XEXP (dest, 0)))
2980 rtx init_insn = XEXP (reg_equiv[regno].init_insns, 0);
2981 if (validate_equiv_mem (init_insn, src, dest)
2982 && ! memref_used_between_p (dest, init_insn, insn)
2983 /* Attaching a REG_EQUIV note will fail if INIT_INSN has
2985 && set_unique_reg_note (init_insn, REG_EQUIV, copy_rtx (dest)))
2987 /* This insn makes the equivalence, not the one initializing
2989 reg_equiv_init (regno)
2990 = gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
2991 df_notes_rescan (init_insn);
2996 cleared_regs = BITMAP_ALLOC (NULL);
2997 /* Now scan all regs killed in an insn to see if any of them are
2998 registers only used that once. If so, see if we can replace the
2999 reference with the equivalent form. If we can, delete the
3000 initializing reference and this register will go away. If we
3001 can't replace the reference, and the initializing reference is
3002 within the same loop (or in an inner loop), then move the register
3003 initialization just before the use, so that they are in the same
3005 FOR_EACH_BB_REVERSE (bb)
3007 loop_depth = bb->loop_depth;
3008 for (insn = BB_END (bb);
3009 insn != PREV_INSN (BB_HEAD (bb));
3010 insn = PREV_INSN (insn))
3014 if (! INSN_P (insn))
3017 /* Don't substitute into a non-local goto, this confuses CFG. */
3019 && find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
3022 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3024 if (REG_NOTE_KIND (link) == REG_DEAD
3025 /* Make sure this insn still refers to the register. */
3026 && reg_mentioned_p (XEXP (link, 0), PATTERN (insn)))
3028 int regno = REGNO (XEXP (link, 0));
3031 if (! reg_equiv[regno].replace
3032 || reg_equiv[regno].loop_depth < loop_depth
3033 /* There is no sense to move insns if we did
3034 register pressure-sensitive scheduling was
3035 done because it will not improve allocation
3036 but worsen insn schedule with a big
3038 || (flag_sched_pressure && flag_schedule_insns))
3041 /* reg_equiv[REGNO].replace gets set only when
3042 REG_N_REFS[REGNO] is 2, i.e. the register is set
3043 once and used once. (If it were only set, but not used,
3044 flow would have deleted the setting insns.) Hence
3045 there can only be one insn in reg_equiv[REGNO].init_insns. */
3046 gcc_assert (reg_equiv[regno].init_insns
3047 && !XEXP (reg_equiv[regno].init_insns, 1));
3048 equiv_insn = XEXP (reg_equiv[regno].init_insns, 0);
3050 /* We may not move instructions that can throw, since
3051 that changes basic block boundaries and we are not
3052 prepared to adjust the CFG to match. */
3053 if (can_throw_internal (equiv_insn))
3056 if (asm_noperands (PATTERN (equiv_insn)) < 0
3057 && validate_replace_rtx (regno_reg_rtx[regno],
3058 *(reg_equiv[regno].src_p), insn))
3064 /* Find the last note. */
3065 for (last_link = link; XEXP (last_link, 1);
3066 last_link = XEXP (last_link, 1))
3069 /* Append the REG_DEAD notes from equiv_insn. */
3070 equiv_link = REG_NOTES (equiv_insn);
3074 equiv_link = XEXP (equiv_link, 1);
3075 if (REG_NOTE_KIND (note) == REG_DEAD)
3077 remove_note (equiv_insn, note);
3078 XEXP (last_link, 1) = note;
3079 XEXP (note, 1) = NULL_RTX;
3084 remove_death (regno, insn);
3085 SET_REG_N_REFS (regno, 0);
3086 REG_FREQ (regno) = 0;
3087 delete_insn (equiv_insn);
3089 reg_equiv[regno].init_insns
3090 = XEXP (reg_equiv[regno].init_insns, 1);
3092 reg_equiv_init (regno) = NULL_RTX;
3093 bitmap_set_bit (cleared_regs, regno);
3095 /* Move the initialization of the register to just before
3096 INSN. Update the flow information. */
3097 else if (prev_nondebug_insn (insn) != equiv_insn)
3101 new_insn = emit_insn_before (PATTERN (equiv_insn), insn);
3102 REG_NOTES (new_insn) = REG_NOTES (equiv_insn);
3103 REG_NOTES (equiv_insn) = 0;
3104 /* Rescan it to process the notes. */
3105 df_insn_rescan (new_insn);
3107 /* Make sure this insn is recognized before
3108 reload begins, otherwise
3109 eliminate_regs_in_insn will die. */
3110 INSN_CODE (new_insn) = INSN_CODE (equiv_insn);
3112 delete_insn (equiv_insn);
3114 XEXP (reg_equiv[regno].init_insns, 0) = new_insn;
3116 REG_BASIC_BLOCK (regno) = bb->index;
3117 REG_N_CALLS_CROSSED (regno) = 0;
3118 REG_FREQ_CALLS_CROSSED (regno) = 0;
3119 REG_N_THROWING_CALLS_CROSSED (regno) = 0;
3120 REG_LIVE_LENGTH (regno) = 2;
3122 if (insn == BB_HEAD (bb))
3123 BB_HEAD (bb) = PREV_INSN (insn);
3125 reg_equiv_init (regno)
3126 = gen_rtx_INSN_LIST (VOIDmode, new_insn, NULL_RTX);
3127 bitmap_set_bit (cleared_regs, regno);
3134 if (!bitmap_empty_p (cleared_regs))
3138 bitmap_and_compl_into (DF_LIVE_IN (bb), cleared_regs);
3139 bitmap_and_compl_into (DF_LIVE_OUT (bb), cleared_regs);
3140 bitmap_and_compl_into (DF_LR_IN (bb), cleared_regs);
3141 bitmap_and_compl_into (DF_LR_OUT (bb), cleared_regs);
3144 /* Last pass - adjust debug insns referencing cleared regs. */
3145 if (MAY_HAVE_DEBUG_INSNS)
3146 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
3147 if (DEBUG_INSN_P (insn))
3149 rtx old_loc = INSN_VAR_LOCATION_LOC (insn);
3150 INSN_VAR_LOCATION_LOC (insn)
3151 = simplify_replace_fn_rtx (old_loc, NULL_RTX,
3152 adjust_cleared_regs,
3153 (void *) cleared_regs);
3154 if (old_loc != INSN_VAR_LOCATION_LOC (insn))
3155 df_insn_rescan (insn);
3159 BITMAP_FREE (cleared_regs);
3164 end_alias_analysis ();
3166 return recorded_label_ref;
3171 /* Print chain C to FILE. */
3173 print_insn_chain (FILE *file, struct insn_chain *c)
3175 fprintf (file, "insn=%d, ", INSN_UID(c->insn));
3176 bitmap_print (file, &c->live_throughout, "live_throughout: ", ", ");
3177 bitmap_print (file, &c->dead_or_set, "dead_or_set: ", "\n");
3181 /* Print all reload_insn_chains to FILE. */
3183 print_insn_chains (FILE *file)
3185 struct insn_chain *c;
3186 for (c = reload_insn_chain; c ; c = c->next)
3187 print_insn_chain (file, c);
3190 /* Return true if pseudo REGNO should be added to set live_throughout
3191 or dead_or_set of the insn chains for reload consideration. */
3193 pseudo_for_reload_consideration_p (int regno)
3195 /* Consider spilled pseudos too for IRA because they still have a
3196 chance to get hard-registers in the reload when IRA is used. */
3197 return (reg_renumber[regno] >= 0 || ira_conflicts_p);
3200 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
3201 REG to the number of nregs, and INIT_VALUE to get the
3202 initialization. ALLOCNUM need not be the regno of REG. */
3204 init_live_subregs (bool init_value, sbitmap *live_subregs,
3205 int *live_subregs_used, int allocnum, rtx reg)
3207 unsigned int regno = REGNO (SUBREG_REG (reg));
3208 int size = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno]));
3210 gcc_assert (size > 0);
3212 /* Been there, done that. */
3213 if (live_subregs_used[allocnum])
3216 /* Create a new one with zeros. */
3217 if (live_subregs[allocnum] == NULL)
3218 live_subregs[allocnum] = sbitmap_alloc (size);
3220 /* If the entire reg was live before blasting into subregs, we need
3221 to init all of the subregs to ones else init to 0. */
3223 sbitmap_ones (live_subregs[allocnum]);
3225 sbitmap_zero (live_subregs[allocnum]);
3227 /* Set the number of bits that we really want. */
3228 live_subregs_used[allocnum] = size;
3231 /* Walk the insns of the current function and build reload_insn_chain,
3232 and record register life information. */
3234 build_insn_chain (void)
3237 struct insn_chain **p = &reload_insn_chain;
3239 struct insn_chain *c = NULL;
3240 struct insn_chain *next = NULL;
3241 bitmap live_relevant_regs = BITMAP_ALLOC (NULL);
3242 bitmap elim_regset = BITMAP_ALLOC (NULL);
3243 /* live_subregs is a vector used to keep accurate information about
3244 which hardregs are live in multiword pseudos. live_subregs and
3245 live_subregs_used are indexed by pseudo number. The live_subreg
3246 entry for a particular pseudo is only used if the corresponding
3247 element is non zero in live_subregs_used. The value in
3248 live_subregs_used is number of bytes that the pseudo can
3250 sbitmap *live_subregs = XCNEWVEC (sbitmap, max_regno);
3251 int *live_subregs_used = XNEWVEC (int, max_regno);
3253 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3254 if (TEST_HARD_REG_BIT (eliminable_regset, i))
3255 bitmap_set_bit (elim_regset, i);
3256 FOR_EACH_BB_REVERSE (bb)
3261 CLEAR_REG_SET (live_relevant_regs);
3262 memset (live_subregs_used, 0, max_regno * sizeof (int));
3264 EXECUTE_IF_SET_IN_BITMAP (DF_LR_OUT (bb), 0, i, bi)
3266 if (i >= FIRST_PSEUDO_REGISTER)
3268 bitmap_set_bit (live_relevant_regs, i);
3271 EXECUTE_IF_SET_IN_BITMAP (DF_LR_OUT (bb),
3272 FIRST_PSEUDO_REGISTER, i, bi)
3274 if (pseudo_for_reload_consideration_p (i))
3275 bitmap_set_bit (live_relevant_regs, i);
3278 FOR_BB_INSNS_REVERSE (bb, insn)
3280 if (!NOTE_P (insn) && !BARRIER_P (insn))
3282 unsigned int uid = INSN_UID (insn);
3286 c = new_insn_chain ();
3293 c->block = bb->index;
3296 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3298 df_ref def = *def_rec;
3299 unsigned int regno = DF_REF_REGNO (def);
3301 /* Ignore may clobbers because these are generated
3302 from calls. However, every other kind of def is
3303 added to dead_or_set. */
3304 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
3306 if (regno < FIRST_PSEUDO_REGISTER)
3308 if (!fixed_regs[regno])
3309 bitmap_set_bit (&c->dead_or_set, regno);
3311 else if (pseudo_for_reload_consideration_p (regno))
3312 bitmap_set_bit (&c->dead_or_set, regno);
3315 if ((regno < FIRST_PSEUDO_REGISTER
3316 || reg_renumber[regno] >= 0
3318 && (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)))
3320 rtx reg = DF_REF_REG (def);
3322 /* We can model subregs, but not if they are
3323 wrapped in ZERO_EXTRACTS. */
3324 if (GET_CODE (reg) == SUBREG
3325 && !DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT))
3327 unsigned int start = SUBREG_BYTE (reg);
3328 unsigned int last = start
3329 + GET_MODE_SIZE (GET_MODE (reg));
3332 (bitmap_bit_p (live_relevant_regs, regno),
3333 live_subregs, live_subregs_used, regno, reg);
3335 if (!DF_REF_FLAGS_IS_SET
3336 (def, DF_REF_STRICT_LOW_PART))
3338 /* Expand the range to cover entire words.
3339 Bytes added here are "don't care". */
3341 = start / UNITS_PER_WORD * UNITS_PER_WORD;
3342 last = ((last + UNITS_PER_WORD - 1)
3343 / UNITS_PER_WORD * UNITS_PER_WORD);
3346 /* Ignore the paradoxical bits. */
3347 if ((int)last > live_subregs_used[regno])
3348 last = live_subregs_used[regno];
3350 while (start < last)
3352 RESET_BIT (live_subregs[regno], start);
3356 if (sbitmap_empty_p (live_subregs[regno]))
3358 live_subregs_used[regno] = 0;
3359 bitmap_clear_bit (live_relevant_regs, regno);
3362 /* Set live_relevant_regs here because
3363 that bit has to be true to get us to
3364 look at the live_subregs fields. */
3365 bitmap_set_bit (live_relevant_regs, regno);
3369 /* DF_REF_PARTIAL is generated for
3370 subregs, STRICT_LOW_PART, and
3371 ZERO_EXTRACT. We handle the subreg
3372 case above so here we have to keep from
3373 modeling the def as a killing def. */
3374 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL))
3376 bitmap_clear_bit (live_relevant_regs, regno);
3377 live_subregs_used[regno] = 0;
3383 bitmap_and_compl_into (live_relevant_regs, elim_regset);
3384 bitmap_copy (&c->live_throughout, live_relevant_regs);
3387 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3389 df_ref use = *use_rec;
3390 unsigned int regno = DF_REF_REGNO (use);
3391 rtx reg = DF_REF_REG (use);
3393 /* DF_REF_READ_WRITE on a use means that this use
3394 is fabricated from a def that is a partial set
3395 to a multiword reg. Here, we only model the
3396 subreg case that is not wrapped in ZERO_EXTRACT
3397 precisely so we do not need to look at the
3399 if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE)
3400 && !DF_REF_FLAGS_IS_SET (use, DF_REF_ZERO_EXTRACT)
3401 && DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG))
3404 /* Add the last use of each var to dead_or_set. */
3405 if (!bitmap_bit_p (live_relevant_regs, regno))
3407 if (regno < FIRST_PSEUDO_REGISTER)
3409 if (!fixed_regs[regno])
3410 bitmap_set_bit (&c->dead_or_set, regno);
3412 else if (pseudo_for_reload_consideration_p (regno))
3413 bitmap_set_bit (&c->dead_or_set, regno);
3416 if (regno < FIRST_PSEUDO_REGISTER
3417 || pseudo_for_reload_consideration_p (regno))
3419 if (GET_CODE (reg) == SUBREG
3420 && !DF_REF_FLAGS_IS_SET (use,
3422 | DF_REF_ZERO_EXTRACT))
3424 unsigned int start = SUBREG_BYTE (reg);
3425 unsigned int last = start
3426 + GET_MODE_SIZE (GET_MODE (reg));
3429 (bitmap_bit_p (live_relevant_regs, regno),
3430 live_subregs, live_subregs_used, regno, reg);
3432 /* Ignore the paradoxical bits. */
3433 if ((int)last > live_subregs_used[regno])
3434 last = live_subregs_used[regno];
3436 while (start < last)
3438 SET_BIT (live_subregs[regno], start);
3443 /* Resetting the live_subregs_used is
3444 effectively saying do not use the subregs
3445 because we are reading the whole
3447 live_subregs_used[regno] = 0;
3448 bitmap_set_bit (live_relevant_regs, regno);
3454 /* FIXME!! The following code is a disaster. Reload needs to see the
3455 labels and jump tables that are just hanging out in between
3456 the basic blocks. See pr33676. */
3457 insn = BB_HEAD (bb);
3459 /* Skip over the barriers and cruft. */
3460 while (insn && (BARRIER_P (insn) || NOTE_P (insn)
3461 || BLOCK_FOR_INSN (insn) == bb))
3462 insn = PREV_INSN (insn);
3464 /* While we add anything except barriers and notes, the focus is
3465 to get the labels and jump tables into the
3466 reload_insn_chain. */
3469 if (!NOTE_P (insn) && !BARRIER_P (insn))
3471 if (BLOCK_FOR_INSN (insn))
3474 c = new_insn_chain ();
3480 /* The block makes no sense here, but it is what the old
3482 c->block = bb->index;
3484 bitmap_copy (&c->live_throughout, live_relevant_regs);
3486 insn = PREV_INSN (insn);
3490 for (i = 0; i < (unsigned int) max_regno; i++)
3491 free (live_subregs[i]);
3493 reload_insn_chain = c;
3496 free (live_subregs);
3497 free (live_subregs_used);
3498 BITMAP_FREE (live_relevant_regs);
3499 BITMAP_FREE (elim_regset);
3502 print_insn_chains (dump_file);
3507 /* All natural loops. */
3508 struct loops ira_loops;
3510 /* True if we have allocno conflicts. It is false for non-optimized
3511 mode or when the conflict table is too big. */
3512 bool ira_conflicts_p;
3514 /* This is the main entry of IRA. */
3518 int overall_cost_before, allocated_reg_info_size;
3520 int max_regno_before_ira, ira_max_point_before_emit;
3522 int saved_flag_ira_share_spill_slots;
3525 timevar_push (TV_IRA);
3527 if (flag_caller_saves)
3528 init_caller_save ();
3530 if (flag_ira_verbose < 10)
3532 internal_flag_ira_verbose = flag_ira_verbose;
3537 internal_flag_ira_verbose = flag_ira_verbose - 10;
3538 ira_dump_file = stderr;
3541 ira_conflicts_p = optimize > 0;
3542 setup_prohibited_mode_move_regs ();
3544 df_note_add_problem ();
3548 df_live_add_problem ();
3549 df_live_set_all_dirty ();
3551 #ifdef ENABLE_CHECKING
3552 df->changeable_flags |= DF_VERIFY_SCHEDULED;
3555 df_clear_flags (DF_NO_INSN_RESCAN);
3556 regstat_init_n_sets_and_refs ();
3557 regstat_compute_ri ();
3559 /* If we are not optimizing, then this is the only place before
3560 register allocation where dataflow is done. And that is needed
3561 to generate these warnings. */
3563 generate_setjmp_warnings ();
3565 /* Determine if the current function is a leaf before running IRA
3566 since this can impact optimizations done by the prologue and
3567 epilogue thus changing register elimination offsets. */
3568 current_function_is_leaf = leaf_function_p ();
3570 if (resize_reg_info () && flag_ira_loop_pressure)
3571 ira_set_pseudo_classes (ira_dump_file);
3573 rebuild_p = update_equiv_regs ();
3575 #ifndef IRA_NO_OBSTACK
3576 gcc_obstack_init (&ira_obstack);
3578 bitmap_obstack_initialize (&ira_bitmap_obstack);
3581 max_regno = max_reg_num ();
3582 ira_reg_equiv_len = max_regno;
3583 ira_reg_equiv_invariant_p
3584 = (bool *) ira_allocate (max_regno * sizeof (bool));
3585 memset (ira_reg_equiv_invariant_p, 0, max_regno * sizeof (bool));
3586 ira_reg_equiv_const = (rtx *) ira_allocate (max_regno * sizeof (rtx));
3587 memset (ira_reg_equiv_const, 0, max_regno * sizeof (rtx));
3588 find_reg_equiv_invariant_const ();
3591 timevar_push (TV_JUMP);
3592 rebuild_jump_labels (get_insns ());
3593 if (purge_all_dead_edges ())
3594 delete_unreachable_blocks ();
3595 timevar_pop (TV_JUMP);
3599 max_regno_before_ira = allocated_reg_info_size = max_reg_num ();
3600 ira_setup_eliminable_regset ();
3602 ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
3603 ira_load_cost = ira_store_cost = ira_shuffle_cost = 0;
3604 ira_move_loops_num = ira_additional_jumps_num = 0;
3606 ira_assert (current_loops == NULL);
3607 flow_loops_find (&ira_loops);
3608 record_loop_exits ();
3609 current_loops = &ira_loops;
3611 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3612 fprintf (ira_dump_file, "Building IRA IR\n");
3613 loops_p = ira_build (optimize
3614 && (flag_ira_region == IRA_REGION_ALL
3615 || flag_ira_region == IRA_REGION_MIXED));
3617 ira_assert (ira_conflicts_p || !loops_p);
3619 saved_flag_ira_share_spill_slots = flag_ira_share_spill_slots;
3620 if (too_high_register_pressure_p () || cfun->calls_setjmp)
3621 /* It is just wasting compiler's time to pack spilled pseudos into
3622 stack slots in this case -- prohibit it. We also do this if
3623 there is setjmp call because a variable not modified between
3624 setjmp and longjmp the compiler is required to preserve its
3625 value and sharing slots does not guarantee it. */
3626 flag_ira_share_spill_slots = FALSE;
3630 ira_max_point_before_emit = ira_max_point;
3632 ira_initiate_emit_data ();
3636 if (ira_conflicts_p)
3638 max_regno = max_reg_num ();
3641 ira_initiate_assign ();
3644 expand_reg_info (allocated_reg_info_size);
3645 setup_preferred_alternate_classes_for_new_pseudos
3646 (allocated_reg_info_size);
3647 allocated_reg_info_size = max_regno;
3649 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3650 fprintf (ira_dump_file, "Flattening IR\n");
3651 ira_flattening (max_regno_before_ira, ira_max_point_before_emit);
3652 /* New insns were generated: add notes and recalculate live
3656 flow_loops_find (&ira_loops);
3657 record_loop_exits ();
3658 current_loops = &ira_loops;
3660 setup_allocno_assignment_flags ();
3661 ira_initiate_assign ();
3662 ira_reassign_conflict_allocnos (max_regno);
3666 ira_finish_emit_data ();
3668 setup_reg_renumber ();
3670 calculate_allocation_cost ();
3672 #ifdef ENABLE_IRA_CHECKING
3673 if (ira_conflicts_p)
3674 check_allocation ();
3677 if (delete_trivially_dead_insns (get_insns (), max_reg_num ()))
3680 if (max_regno != max_regno_before_ira)
3682 regstat_free_n_sets_and_refs ();
3684 regstat_init_n_sets_and_refs ();
3685 regstat_compute_ri ();
3688 overall_cost_before = ira_overall_cost;
3689 if (! ira_conflicts_p)
3693 fix_reg_equiv_init ();
3695 #ifdef ENABLE_IRA_CHECKING
3696 print_redundant_copies ();
3699 ira_spilled_reg_stack_slots_num = 0;
3700 ira_spilled_reg_stack_slots
3701 = ((struct ira_spilled_reg_stack_slot *)
3702 ira_allocate (max_regno
3703 * sizeof (struct ira_spilled_reg_stack_slot)));
3704 memset (ira_spilled_reg_stack_slots, 0,
3705 max_regno * sizeof (struct ira_spilled_reg_stack_slot));
3707 allocate_initial_values (reg_equivs);
3709 timevar_pop (TV_IRA);
3711 timevar_push (TV_RELOAD);
3712 df_set_flags (DF_NO_INSN_RESCAN);
3713 build_insn_chain ();
3715 reload_completed = !reload (get_insns (), ira_conflicts_p);
3717 timevar_pop (TV_RELOAD);
3719 timevar_push (TV_IRA);
3721 if (ira_conflicts_p)
3723 ira_free (ira_spilled_reg_stack_slots);
3725 ira_finish_assign ();
3728 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL
3729 && overall_cost_before != ira_overall_cost)
3730 fprintf (ira_dump_file, "+++Overall after reload %d\n", ira_overall_cost);
3733 flag_ira_share_spill_slots = saved_flag_ira_share_spill_slots;
3735 flow_loops_free (&ira_loops);
3736 free_dominance_info (CDI_DOMINATORS);
3738 bb->loop_father = NULL;
3739 current_loops = NULL;
3742 regstat_free_n_sets_and_refs ();
3746 cleanup_cfg (CLEANUP_EXPENSIVE);
3748 ira_free (ira_reg_equiv_invariant_p);
3749 ira_free (ira_reg_equiv_const);
3752 bitmap_obstack_release (&ira_bitmap_obstack);
3753 #ifndef IRA_NO_OBSTACK
3754 obstack_free (&ira_obstack, NULL);
3757 /* The code after the reload has changed so much that at this point
3758 we might as well just rescan everything. Not that
3759 df_rescan_all_insns is not going to help here because it does not
3760 touch the artificial uses and defs. */
3761 df_finish_pass (true);
3763 df_live_add_problem ();
3764 df_scan_alloc (NULL);
3770 timevar_pop (TV_IRA);
3781 /* Run the integrated register allocator. */
3783 rest_of_handle_ira (void)
3789 struct rtl_opt_pass pass_ira =
3794 gate_ira, /* gate */
3795 rest_of_handle_ira, /* execute */
3798 0, /* static_pass_number */
3799 TV_NONE, /* tv_id */
3800 0, /* properties_required */
3801 0, /* properties_provided */
3802 0, /* properties_destroyed */
3803 0, /* todo_flags_start */
3805 TODO_ggc_collect /* todo_flags_finish */