1 /* Integrated Register Allocator (IRA) entry point.
2 Copyright (C) 2006-2013 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* The integrated register allocator (IRA) is a
22 regional register allocator performing graph coloring on a top-down
23 traversal of nested regions. Graph coloring in a region is based
24 on Chaitin-Briggs algorithm. It is called integrated because
25 register coalescing, register live range splitting, and choosing a
26 better hard register are done on-the-fly during coloring. Register
27 coalescing and choosing a cheaper hard register is done by hard
28 register preferencing during hard register assigning. The live
29 range splitting is a byproduct of the regional register allocation.
31 Major IRA notions are:
33 o *Region* is a part of CFG where graph coloring based on
34 Chaitin-Briggs algorithm is done. IRA can work on any set of
35 nested CFG regions forming a tree. Currently the regions are
36 the entire function for the root region and natural loops for
37 the other regions. Therefore data structure representing a
38 region is called loop_tree_node.
40 o *Allocno class* is a register class used for allocation of
41 given allocno. It means that only hard register of given
42 register class can be assigned to given allocno. In reality,
43 even smaller subset of (*profitable*) hard registers can be
44 assigned. In rare cases, the subset can be even smaller
45 because our modification of Chaitin-Briggs algorithm requires
46 that sets of hard registers can be assigned to allocnos forms a
47 forest, i.e. the sets can be ordered in a way where any
48 previous set is not intersected with given set or is a superset
51 o *Pressure class* is a register class belonging to a set of
52 register classes containing all of the hard-registers available
53 for register allocation. The set of all pressure classes for a
54 target is defined in the corresponding machine-description file
55 according some criteria. Register pressure is calculated only
56 for pressure classes and it affects some IRA decisions as
57 forming allocation regions.
59 o *Allocno* represents the live range of a pseudo-register in a
60 region. Besides the obvious attributes like the corresponding
61 pseudo-register number, allocno class, conflicting allocnos and
62 conflicting hard-registers, there are a few allocno attributes
63 which are important for understanding the allocation algorithm:
65 - *Live ranges*. This is a list of ranges of *program points*
66 where the allocno lives. Program points represent places
67 where a pseudo can be born or become dead (there are
68 approximately two times more program points than the insns)
69 and they are represented by integers starting with 0. The
70 live ranges are used to find conflicts between allocnos.
71 They also play very important role for the transformation of
72 the IRA internal representation of several regions into a one
73 region representation. The later is used during the reload
74 pass work because each allocno represents all of the
75 corresponding pseudo-registers.
77 - *Hard-register costs*. This is a vector of size equal to the
78 number of available hard-registers of the allocno class. The
79 cost of a callee-clobbered hard-register for an allocno is
80 increased by the cost of save/restore code around the calls
81 through the given allocno's life. If the allocno is a move
82 instruction operand and another operand is a hard-register of
83 the allocno class, the cost of the hard-register is decreased
86 When an allocno is assigned, the hard-register with minimal
87 full cost is used. Initially, a hard-register's full cost is
88 the corresponding value from the hard-register's cost vector.
89 If the allocno is connected by a *copy* (see below) to
90 another allocno which has just received a hard-register, the
91 cost of the hard-register is decreased. Before choosing a
92 hard-register for an allocno, the allocno's current costs of
93 the hard-registers are modified by the conflict hard-register
94 costs of all of the conflicting allocnos which are not
97 - *Conflict hard-register costs*. This is a vector of the same
98 size as the hard-register costs vector. To permit an
99 unassigned allocno to get a better hard-register, IRA uses
100 this vector to calculate the final full cost of the
101 available hard-registers. Conflict hard-register costs of an
102 unassigned allocno are also changed with a change of the
103 hard-register cost of the allocno when a copy involving the
104 allocno is processed as described above. This is done to
105 show other unassigned allocnos that a given allocno prefers
106 some hard-registers in order to remove the move instruction
107 corresponding to the copy.
109 o *Cap*. If a pseudo-register does not live in a region but
110 lives in a nested region, IRA creates a special allocno called
111 a cap in the outer region. A region cap is also created for a
114 o *Copy*. Allocnos can be connected by copies. Copies are used
115 to modify hard-register costs for allocnos during coloring.
116 Such modifications reflects a preference to use the same
117 hard-register for the allocnos connected by copies. Usually
118 copies are created for move insns (in this case it results in
119 register coalescing). But IRA also creates copies for operands
120 of an insn which should be assigned to the same hard-register
121 due to constraints in the machine description (it usually
122 results in removing a move generated in reload to satisfy
123 the constraints) and copies referring to the allocno which is
124 the output operand of an instruction and the allocno which is
125 an input operand dying in the instruction (creation of such
126 copies results in less register shuffling). IRA *does not*
127 create copies between the same register allocnos from different
128 regions because we use another technique for propagating
129 hard-register preference on the borders of regions.
131 Allocnos (including caps) for the upper region in the region tree
132 *accumulate* information important for coloring from allocnos with
133 the same pseudo-register from nested regions. This includes
134 hard-register and memory costs, conflicts with hard-registers,
135 allocno conflicts, allocno copies and more. *Thus, attributes for
136 allocnos in a region have the same values as if the region had no
137 subregions*. It means that attributes for allocnos in the
138 outermost region corresponding to the function have the same values
139 as though the allocation used only one region which is the entire
140 function. It also means that we can look at IRA work as if the
141 first IRA did allocation for all function then it improved the
142 allocation for loops then their subloops and so on.
144 IRA major passes are:
146 o Building IRA internal representation which consists of the
149 * First, IRA builds regions and creates allocnos (file
150 ira-build.c) and initializes most of their attributes.
152 * Then IRA finds an allocno class for each allocno and
153 calculates its initial (non-accumulated) cost of memory and
154 each hard-register of its allocno class (file ira-cost.c).
156 * IRA creates live ranges of each allocno, calulates register
157 pressure for each pressure class in each region, sets up
158 conflict hard registers for each allocno and info about calls
159 the allocno lives through (file ira-lives.c).
161 * IRA removes low register pressure loops from the regions
162 mostly to speed IRA up (file ira-build.c).
164 * IRA propagates accumulated allocno info from lower region
165 allocnos to corresponding upper region allocnos (file
168 * IRA creates all caps (file ira-build.c).
170 * Having live-ranges of allocnos and their classes, IRA creates
171 conflicting allocnos for each allocno. Conflicting allocnos
172 are stored as a bit vector or array of pointers to the
173 conflicting allocnos whatever is more profitable (file
174 ira-conflicts.c). At this point IRA creates allocno copies.
176 o Coloring. Now IRA has all necessary info to start graph coloring
177 process. It is done in each region on top-down traverse of the
178 region tree (file ira-color.c). There are following subpasses:
180 * Finding profitable hard registers of corresponding allocno
181 class for each allocno. For example, only callee-saved hard
182 registers are frequently profitable for allocnos living
183 through colors. If the profitable hard register set of
184 allocno does not form a tree based on subset relation, we use
185 some approximation to form the tree. This approximation is
186 used to figure out trivial colorability of allocnos. The
187 approximation is a pretty rare case.
189 * Putting allocnos onto the coloring stack. IRA uses Briggs
190 optimistic coloring which is a major improvement over
191 Chaitin's coloring. Therefore IRA does not spill allocnos at
192 this point. There is some freedom in the order of putting
193 allocnos on the stack which can affect the final result of
194 the allocation. IRA uses some heuristics to improve the
197 We also use a modification of Chaitin-Briggs algorithm which
198 works for intersected register classes of allocnos. To
199 figure out trivial colorability of allocnos, the mentioned
200 above tree of hard register sets is used. To get an idea how
201 the algorithm works in i386 example, let us consider an
202 allocno to which any general hard register can be assigned.
203 If the allocno conflicts with eight allocnos to which only
204 EAX register can be assigned, given allocno is still
205 trivially colorable because all conflicting allocnos might be
206 assigned only to EAX and all other general hard registers are
209 To get an idea of the used trivial colorability criterion, it
210 is also useful to read article "Graph-Coloring Register
211 Allocation for Irregular Architectures" by Michael D. Smith
212 and Glen Holloway. Major difference between the article
213 approach and approach used in IRA is that Smith's approach
214 takes register classes only from machine description and IRA
215 calculate register classes from intermediate code too
216 (e.g. an explicit usage of hard registers in RTL code for
217 parameter passing can result in creation of additional
218 register classes which contain or exclude the hard
219 registers). That makes IRA approach useful for improving
220 coloring even for architectures with regular register files
221 and in fact some benchmarking shows the improvement for
222 regular class architectures is even bigger than for irregular
223 ones. Another difference is that Smith's approach chooses
224 intersection of classes of all insn operands in which a given
225 pseudo occurs. IRA can use bigger classes if it is still
226 more profitable than memory usage.
228 * Popping the allocnos from the stack and assigning them hard
229 registers. If IRA can not assign a hard register to an
230 allocno and the allocno is coalesced, IRA undoes the
231 coalescing and puts the uncoalesced allocnos onto the stack in
232 the hope that some such allocnos will get a hard register
233 separately. If IRA fails to assign hard register or memory
234 is more profitable for it, IRA spills the allocno. IRA
235 assigns the allocno the hard-register with minimal full
236 allocation cost which reflects the cost of usage of the
237 hard-register for the allocno and cost of usage of the
238 hard-register for allocnos conflicting with given allocno.
240 * Chaitin-Briggs coloring assigns as many pseudos as possible
241 to hard registers. After coloringh we try to improve
242 allocation with cost point of view. We improve the
243 allocation by spilling some allocnos and assigning the freed
244 hard registers to other allocnos if it decreases the overall
247 * After allono assigning in the region, IRA modifies the hard
248 register and memory costs for the corresponding allocnos in
249 the subregions to reflect the cost of possible loads, stores,
250 or moves on the border of the region and its subregions.
251 When default regional allocation algorithm is used
252 (-fira-algorithm=mixed), IRA just propagates the assignment
253 for allocnos if the register pressure in the region for the
254 corresponding pressure class is less than number of available
255 hard registers for given pressure class.
257 o Spill/restore code moving. When IRA performs an allocation
258 by traversing regions in top-down order, it does not know what
259 happens below in the region tree. Therefore, sometimes IRA
260 misses opportunities to perform a better allocation. A simple
261 optimization tries to improve allocation in a region having
262 subregions and containing in another region. If the
263 corresponding allocnos in the subregion are spilled, it spills
264 the region allocno if it is profitable. The optimization
265 implements a simple iterative algorithm performing profitable
266 transformations while they are still possible. It is fast in
267 practice, so there is no real need for a better time complexity
270 o Code change. After coloring, two allocnos representing the
271 same pseudo-register outside and inside a region respectively
272 may be assigned to different locations (hard-registers or
273 memory). In this case IRA creates and uses a new
274 pseudo-register inside the region and adds code to move allocno
275 values on the region's borders. This is done during top-down
276 traversal of the regions (file ira-emit.c). In some
277 complicated cases IRA can create a new allocno to move allocno
278 values (e.g. when a swap of values stored in two hard-registers
279 is needed). At this stage, the new allocno is marked as
280 spilled. IRA still creates the pseudo-register and the moves
281 on the region borders even when both allocnos were assigned to
282 the same hard-register. If the reload pass spills a
283 pseudo-register for some reason, the effect will be smaller
284 because another allocno will still be in the hard-register. In
285 most cases, this is better then spilling both allocnos. If
286 reload does not change the allocation for the two
287 pseudo-registers, the trivial move will be removed by
288 post-reload optimizations. IRA does not generate moves for
289 allocnos assigned to the same hard register when the default
290 regional allocation algorithm is used and the register pressure
291 in the region for the corresponding pressure class is less than
292 number of available hard registers for given pressure class.
293 IRA also does some optimizations to remove redundant stores and
294 to reduce code duplication on the region borders.
296 o Flattening internal representation. After changing code, IRA
297 transforms its internal representation for several regions into
298 one region representation (file ira-build.c). This process is
299 called IR flattening. Such process is more complicated than IR
300 rebuilding would be, but is much faster.
302 o After IR flattening, IRA tries to assign hard registers to all
303 spilled allocnos. This is impelemented by a simple and fast
304 priority coloring algorithm (see function
305 ira_reassign_conflict_allocnos::ira-color.c). Here new allocnos
306 created during the code change pass can be assigned to hard
309 o At the end IRA calls the reload pass. The reload pass
310 communicates with IRA through several functions in file
311 ira-color.c to improve its decisions in
313 * sharing stack slots for the spilled pseudos based on IRA info
314 about pseudo-register conflicts.
316 * reassigning hard-registers to all spilled pseudos at the end
317 of each reload iteration.
319 * choosing a better hard-register to spill based on IRA info
320 about pseudo-register live ranges and the register pressure
321 in places where the pseudo-register lives.
323 IRA uses a lot of data representing the target processors. These
324 data are initilized in file ira.c.
326 If function has no loops (or the loops are ignored when
327 -fira-algorithm=CB is used), we have classic Chaitin-Briggs
328 coloring (only instead of separate pass of coalescing, we use hard
329 register preferencing). In such case, IRA works much faster
330 because many things are not made (like IR flattening, the
331 spill/restore optimization, and the code change).
333 Literature is worth to read for better understanding the code:
335 o Preston Briggs, Keith D. Cooper, Linda Torczon. Improvements to
336 Graph Coloring Register Allocation.
338 o David Callahan, Brian Koblenz. Register allocation via
339 hierarchical graph coloring.
341 o Keith Cooper, Anshuman Dasgupta, Jason Eckhardt. Revisiting Graph
342 Coloring Register Allocation: A Study of the Chaitin-Briggs and
343 Callahan-Koblenz Algorithms.
345 o Guei-Yuan Lueh, Thomas Gross, and Ali-Reza Adl-Tabatabai. Global
346 Register Allocation Based on Graph Fusion.
348 o Michael D. Smith and Glenn Holloway. Graph-Coloring Register
349 Allocation for Irregular Architectures
351 o Vladimir Makarov. The Integrated Register Allocator for GCC.
353 o Vladimir Makarov. The top-down register allocator for irregular
354 register file architectures.
361 #include "coretypes.h"
371 #include "hard-reg-set.h"
372 #include "basic-block.h"
377 #include "tree-pass.h"
381 #include "diagnostic-core.h"
382 #include "function.h"
389 struct target_ira default_target_ira
;
390 struct target_ira_int default_target_ira_int
;
391 #if SWITCHABLE_TARGET
392 struct target_ira
*this_target_ira
= &default_target_ira
;
393 struct target_ira_int
*this_target_ira_int
= &default_target_ira_int
;
396 /* A modified value of flag `-fira-verbose' used internally. */
397 int internal_flag_ira_verbose
;
399 /* Dump file of the allocator if it is not NULL. */
402 /* The number of elements in the following array. */
403 int ira_spilled_reg_stack_slots_num
;
405 /* The following array contains info about spilled pseudo-registers
406 stack slots used in current function so far. */
407 struct ira_spilled_reg_stack_slot
*ira_spilled_reg_stack_slots
;
409 /* Correspondingly overall cost of the allocation, overall cost before
410 reload, cost of the allocnos assigned to hard-registers, cost of
411 the allocnos assigned to memory, cost of loads, stores and register
412 move insns generated for pseudo-register live range splitting (see
414 int ira_overall_cost
, overall_cost_before
;
415 int ira_reg_cost
, ira_mem_cost
;
416 int ira_load_cost
, ira_store_cost
, ira_shuffle_cost
;
417 int ira_move_loops_num
, ira_additional_jumps_num
;
419 /* All registers that can be eliminated. */
421 HARD_REG_SET eliminable_regset
;
423 /* Value of max_reg_num () before IRA work start. This value helps
424 us to recognize a situation when new pseudos were created during
426 static int max_regno_before_ira
;
428 /* Temporary hard reg set used for a different calculation. */
429 static HARD_REG_SET temp_hard_regset
;
431 #define last_mode_for_init_move_cost \
432 (this_target_ira_int->x_last_mode_for_init_move_cost)
435 /* The function sets up the map IRA_REG_MODE_HARD_REGSET. */
437 setup_reg_mode_hard_regset (void)
439 int i
, m
, hard_regno
;
441 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
442 for (hard_regno
= 0; hard_regno
< FIRST_PSEUDO_REGISTER
; hard_regno
++)
444 CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset
[hard_regno
][m
]);
445 for (i
= hard_regno_nregs
[hard_regno
][m
] - 1; i
>= 0; i
--)
446 if (hard_regno
+ i
< FIRST_PSEUDO_REGISTER
)
447 SET_HARD_REG_BIT (ira_reg_mode_hard_regset
[hard_regno
][m
],
453 #define no_unit_alloc_regs \
454 (this_target_ira_int->x_no_unit_alloc_regs)
456 /* The function sets up the three arrays declared above. */
458 setup_class_hard_regs (void)
460 int cl
, i
, hard_regno
, n
;
461 HARD_REG_SET processed_hard_reg_set
;
463 ira_assert (SHRT_MAX
>= FIRST_PSEUDO_REGISTER
);
464 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
466 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
467 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
468 CLEAR_HARD_REG_SET (processed_hard_reg_set
);
469 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
471 ira_non_ordered_class_hard_regs
[cl
][i
] = -1;
472 ira_class_hard_reg_index
[cl
][i
] = -1;
474 for (n
= 0, i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
476 #ifdef REG_ALLOC_ORDER
477 hard_regno
= reg_alloc_order
[i
];
481 if (TEST_HARD_REG_BIT (processed_hard_reg_set
, hard_regno
))
483 SET_HARD_REG_BIT (processed_hard_reg_set
, hard_regno
);
484 if (! TEST_HARD_REG_BIT (temp_hard_regset
, hard_regno
))
485 ira_class_hard_reg_index
[cl
][hard_regno
] = -1;
488 ira_class_hard_reg_index
[cl
][hard_regno
] = n
;
489 ira_class_hard_regs
[cl
][n
++] = hard_regno
;
492 ira_class_hard_regs_num
[cl
] = n
;
493 for (n
= 0, i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
494 if (TEST_HARD_REG_BIT (temp_hard_regset
, i
))
495 ira_non_ordered_class_hard_regs
[cl
][n
++] = i
;
496 ira_assert (ira_class_hard_regs_num
[cl
] == n
);
500 /* Set up global variables defining info about hard registers for the
501 allocation. These depend on USE_HARD_FRAME_P whose TRUE value means
502 that we can use the hard frame pointer for the allocation. */
504 setup_alloc_regs (bool use_hard_frame_p
)
506 #ifdef ADJUST_REG_ALLOC_ORDER
507 ADJUST_REG_ALLOC_ORDER
;
509 COPY_HARD_REG_SET (no_unit_alloc_regs
, fixed_reg_set
);
510 if (! use_hard_frame_p
)
511 SET_HARD_REG_BIT (no_unit_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
512 setup_class_hard_regs ();
517 #define alloc_reg_class_subclasses \
518 (this_target_ira_int->x_alloc_reg_class_subclasses)
520 /* Initialize the table of subclasses of each reg class. */
522 setup_reg_subclasses (void)
525 HARD_REG_SET temp_hard_regset2
;
527 for (i
= 0; i
< N_REG_CLASSES
; i
++)
528 for (j
= 0; j
< N_REG_CLASSES
; j
++)
529 alloc_reg_class_subclasses
[i
][j
] = LIM_REG_CLASSES
;
531 for (i
= 0; i
< N_REG_CLASSES
; i
++)
533 if (i
== (int) NO_REGS
)
536 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[i
]);
537 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
538 if (hard_reg_set_empty_p (temp_hard_regset
))
540 for (j
= 0; j
< N_REG_CLASSES
; j
++)
545 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[j
]);
546 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
547 if (! hard_reg_set_subset_p (temp_hard_regset
,
550 p
= &alloc_reg_class_subclasses
[j
][0];
551 while (*p
!= LIM_REG_CLASSES
) p
++;
552 *p
= (enum reg_class
) i
;
559 /* Set up IRA_MEMORY_MOVE_COST and IRA_MAX_MEMORY_MOVE_COST. */
561 setup_class_subset_and_memory_move_costs (void)
563 int cl
, cl2
, mode
, cost
;
564 HARD_REG_SET temp_hard_regset2
;
566 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
567 ira_memory_move_cost
[mode
][NO_REGS
][0]
568 = ira_memory_move_cost
[mode
][NO_REGS
][1] = SHRT_MAX
;
569 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
571 if (cl
!= (int) NO_REGS
)
572 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
574 ira_max_memory_move_cost
[mode
][cl
][0]
575 = ira_memory_move_cost
[mode
][cl
][0]
576 = memory_move_cost ((enum machine_mode
) mode
,
577 (reg_class_t
) cl
, false);
578 ira_max_memory_move_cost
[mode
][cl
][1]
579 = ira_memory_move_cost
[mode
][cl
][1]
580 = memory_move_cost ((enum machine_mode
) mode
,
581 (reg_class_t
) cl
, true);
582 /* Costs for NO_REGS are used in cost calculation on the
583 1st pass when the preferred register classes are not
584 known yet. In this case we take the best scenario. */
585 if (ira_memory_move_cost
[mode
][NO_REGS
][0]
586 > ira_memory_move_cost
[mode
][cl
][0])
587 ira_max_memory_move_cost
[mode
][NO_REGS
][0]
588 = ira_memory_move_cost
[mode
][NO_REGS
][0]
589 = ira_memory_move_cost
[mode
][cl
][0];
590 if (ira_memory_move_cost
[mode
][NO_REGS
][1]
591 > ira_memory_move_cost
[mode
][cl
][1])
592 ira_max_memory_move_cost
[mode
][NO_REGS
][1]
593 = ira_memory_move_cost
[mode
][NO_REGS
][1]
594 = ira_memory_move_cost
[mode
][cl
][1];
597 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
598 for (cl2
= (int) N_REG_CLASSES
- 1; cl2
>= 0; cl2
--)
600 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
601 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
602 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl2
]);
603 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
604 ira_class_subset_p
[cl
][cl2
]
605 = hard_reg_set_subset_p (temp_hard_regset
, temp_hard_regset2
);
606 if (! hard_reg_set_empty_p (temp_hard_regset2
)
607 && hard_reg_set_subset_p (reg_class_contents
[cl2
],
608 reg_class_contents
[cl
]))
609 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
611 cost
= ira_memory_move_cost
[mode
][cl2
][0];
612 if (cost
> ira_max_memory_move_cost
[mode
][cl
][0])
613 ira_max_memory_move_cost
[mode
][cl
][0] = cost
;
614 cost
= ira_memory_move_cost
[mode
][cl2
][1];
615 if (cost
> ira_max_memory_move_cost
[mode
][cl
][1])
616 ira_max_memory_move_cost
[mode
][cl
][1] = cost
;
619 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
620 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
622 ira_memory_move_cost
[mode
][cl
][0]
623 = ira_max_memory_move_cost
[mode
][cl
][0];
624 ira_memory_move_cost
[mode
][cl
][1]
625 = ira_max_memory_move_cost
[mode
][cl
][1];
627 setup_reg_subclasses ();
632 /* Define the following macro if allocation through malloc if
634 #define IRA_NO_OBSTACK
636 #ifndef IRA_NO_OBSTACK
637 /* Obstack used for storing all dynamic data (except bitmaps) of the
639 static struct obstack ira_obstack
;
642 /* Obstack used for storing all bitmaps of the IRA. */
643 static struct bitmap_obstack ira_bitmap_obstack
;
645 /* Allocate memory of size LEN for IRA data. */
647 ira_allocate (size_t len
)
651 #ifndef IRA_NO_OBSTACK
652 res
= obstack_alloc (&ira_obstack
, len
);
659 /* Free memory ADDR allocated for IRA data. */
661 ira_free (void *addr ATTRIBUTE_UNUSED
)
663 #ifndef IRA_NO_OBSTACK
671 /* Allocate and returns bitmap for IRA. */
673 ira_allocate_bitmap (void)
675 return BITMAP_ALLOC (&ira_bitmap_obstack
);
678 /* Free bitmap B allocated for IRA. */
680 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED
)
687 /* Output information about allocation of all allocnos (except for
688 caps) into file F. */
690 ira_print_disposition (FILE *f
)
696 fprintf (f
, "Disposition:");
697 max_regno
= max_reg_num ();
698 for (n
= 0, i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
699 for (a
= ira_regno_allocno_map
[i
];
701 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
706 fprintf (f
, " %4d:r%-4d", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
707 if ((bb
= ALLOCNO_LOOP_TREE_NODE (a
)->bb
) != NULL
)
708 fprintf (f
, "b%-3d", bb
->index
);
710 fprintf (f
, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a
)->loop_num
);
711 if (ALLOCNO_HARD_REGNO (a
) >= 0)
712 fprintf (f
, " %3d", ALLOCNO_HARD_REGNO (a
));
719 /* Outputs information about allocation of all allocnos into
722 ira_debug_disposition (void)
724 ira_print_disposition (stderr
);
729 /* Set up ira_stack_reg_pressure_class which is the biggest pressure
730 register class containing stack registers or NO_REGS if there are
731 no stack registers. To find this class, we iterate through all
732 register pressure classes and choose the first register pressure
733 class containing all the stack registers and having the biggest
736 setup_stack_reg_pressure_class (void)
738 ira_stack_reg_pressure_class
= NO_REGS
;
743 HARD_REG_SET temp_hard_regset2
;
745 CLEAR_HARD_REG_SET (temp_hard_regset
);
746 for (i
= FIRST_STACK_REG
; i
<= LAST_STACK_REG
; i
++)
747 SET_HARD_REG_BIT (temp_hard_regset
, i
);
749 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
751 cl
= ira_pressure_classes
[i
];
752 COPY_HARD_REG_SET (temp_hard_regset2
, temp_hard_regset
);
753 AND_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl
]);
754 size
= hard_reg_set_size (temp_hard_regset2
);
758 ira_stack_reg_pressure_class
= cl
;
765 /* Find pressure classes which are register classes for which we
766 calculate register pressure in IRA, register pressure sensitive
767 insn scheduling, and register pressure sensitive loop invariant
770 To make register pressure calculation easy, we always use
771 non-intersected register pressure classes. A move of hard
772 registers from one register pressure class is not more expensive
773 than load and store of the hard registers. Most likely an allocno
774 class will be a subset of a register pressure class and in many
775 cases a register pressure class. That makes usage of register
776 pressure classes a good approximation to find a high register
779 setup_pressure_classes (void)
781 int cost
, i
, n
, curr
;
783 enum reg_class pressure_classes
[N_REG_CLASSES
];
785 HARD_REG_SET temp_hard_regset2
;
789 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
791 if (ira_class_hard_regs_num
[cl
] == 0)
793 if (ira_class_hard_regs_num
[cl
] != 1
794 /* A register class without subclasses may contain a few
795 hard registers and movement between them is costly
796 (e.g. SPARC FPCC registers). We still should consider it
797 as a candidate for a pressure class. */
798 && alloc_reg_class_subclasses
[cl
][0] < cl
)
800 /* Check that the moves between any hard registers of the
801 current class are not more expensive for a legal mode
802 than load/store of the hard registers of the current
803 class. Such class is a potential candidate to be a
804 register pressure class. */
805 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
807 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
808 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
809 AND_COMPL_HARD_REG_SET (temp_hard_regset
,
810 ira_prohibited_class_mode_regs
[cl
][m
]);
811 if (hard_reg_set_empty_p (temp_hard_regset
))
813 ira_init_register_move_cost_if_necessary ((enum machine_mode
) m
);
814 cost
= ira_register_move_cost
[m
][cl
][cl
];
815 if (cost
<= ira_max_memory_move_cost
[m
][cl
][1]
816 || cost
<= ira_max_memory_move_cost
[m
][cl
][0])
819 if (m
>= NUM_MACHINE_MODES
)
824 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
825 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
826 /* Remove so far added pressure classes which are subset of the
827 current candidate class. Prefer GENERAL_REGS as a pressure
828 register class to another class containing the same
829 allocatable hard registers. We do this because machine
830 dependent cost hooks might give wrong costs for the latter
831 class but always give the right cost for the former class
833 for (i
= 0; i
< n
; i
++)
835 cl2
= pressure_classes
[i
];
836 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl2
]);
837 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
838 if (hard_reg_set_subset_p (temp_hard_regset
, temp_hard_regset2
)
839 && (! hard_reg_set_equal_p (temp_hard_regset
, temp_hard_regset2
)
840 || cl2
== (int) GENERAL_REGS
))
842 pressure_classes
[curr
++] = (enum reg_class
) cl2
;
846 if (hard_reg_set_subset_p (temp_hard_regset2
, temp_hard_regset
)
847 && (! hard_reg_set_equal_p (temp_hard_regset2
, temp_hard_regset
)
848 || cl
== (int) GENERAL_REGS
))
850 if (hard_reg_set_equal_p (temp_hard_regset2
, temp_hard_regset
))
852 pressure_classes
[curr
++] = (enum reg_class
) cl2
;
854 /* If the current candidate is a subset of a so far added
855 pressure class, don't add it to the list of the pressure
858 pressure_classes
[curr
++] = (enum reg_class
) cl
;
861 #ifdef ENABLE_IRA_CHECKING
863 HARD_REG_SET ignore_hard_regs
;
865 /* Check pressure classes correctness: here we check that hard
866 registers from all register pressure classes contains all hard
867 registers available for the allocation. */
868 CLEAR_HARD_REG_SET (temp_hard_regset
);
869 CLEAR_HARD_REG_SET (temp_hard_regset2
);
870 COPY_HARD_REG_SET (ignore_hard_regs
, no_unit_alloc_regs
);
871 for (cl
= 0; cl
< LIM_REG_CLASSES
; cl
++)
873 /* For some targets (like MIPS with MD_REGS), there are some
874 classes with hard registers available for allocation but
875 not able to hold value of any mode. */
876 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
877 if (contains_reg_of_mode
[cl
][m
])
879 if (m
>= NUM_MACHINE_MODES
)
881 IOR_HARD_REG_SET (ignore_hard_regs
, reg_class_contents
[cl
]);
884 for (i
= 0; i
< n
; i
++)
885 if ((int) pressure_classes
[i
] == cl
)
887 IOR_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl
]);
889 IOR_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
891 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
892 /* Some targets (like SPARC with ICC reg) have alocatable regs
893 for which no reg class is defined. */
894 if (REGNO_REG_CLASS (i
) == NO_REGS
)
895 SET_HARD_REG_BIT (ignore_hard_regs
, i
);
896 AND_COMPL_HARD_REG_SET (temp_hard_regset
, ignore_hard_regs
);
897 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, ignore_hard_regs
);
898 ira_assert (hard_reg_set_subset_p (temp_hard_regset2
, temp_hard_regset
));
901 ira_pressure_classes_num
= 0;
902 for (i
= 0; i
< n
; i
++)
904 cl
= (int) pressure_classes
[i
];
905 ira_reg_pressure_class_p
[cl
] = true;
906 ira_pressure_classes
[ira_pressure_classes_num
++] = (enum reg_class
) cl
;
908 setup_stack_reg_pressure_class ();
911 /* Set up IRA_UNIFORM_CLASS_P. Uniform class is a register class
912 whose register move cost between any registers of the class is the
913 same as for all its subclasses. We use the data to speed up the
914 2nd pass of calculations of allocno costs. */
916 setup_uniform_class_p (void)
920 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
922 ira_uniform_class_p
[cl
] = false;
923 if (ira_class_hard_regs_num
[cl
] == 0)
925 /* We can not use alloc_reg_class_subclasses here because move
926 cost hooks does not take into account that some registers are
927 unavailable for the subtarget. E.g. for i686, INT_SSE_REGS
928 is element of alloc_reg_class_subclasses for GENERAL_REGS
929 because SSE regs are unavailable. */
930 for (i
= 0; (cl2
= reg_class_subclasses
[cl
][i
]) != LIM_REG_CLASSES
; i
++)
932 if (ira_class_hard_regs_num
[cl2
] == 0)
934 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
935 if (contains_reg_of_mode
[cl
][m
] && contains_reg_of_mode
[cl2
][m
])
937 ira_init_register_move_cost_if_necessary ((enum machine_mode
) m
);
938 if (ira_register_move_cost
[m
][cl
][cl
]
939 != ira_register_move_cost
[m
][cl2
][cl2
])
942 if (m
< NUM_MACHINE_MODES
)
945 if (cl2
== LIM_REG_CLASSES
)
946 ira_uniform_class_p
[cl
] = true;
950 /* Set up IRA_ALLOCNO_CLASSES, IRA_ALLOCNO_CLASSES_NUM,
951 IRA_IMPORTANT_CLASSES, and IRA_IMPORTANT_CLASSES_NUM.
953 Target may have many subtargets and not all target hard regiters can
954 be used for allocation, e.g. x86 port in 32-bit mode can not use
955 hard registers introduced in x86-64 like r8-r15). Some classes
956 might have the same allocatable hard registers, e.g. INDEX_REGS
957 and GENERAL_REGS in x86 port in 32-bit mode. To decrease different
958 calculations efforts we introduce allocno classes which contain
959 unique non-empty sets of allocatable hard-registers.
961 Pseudo class cost calculation in ira-costs.c is very expensive.
962 Therefore we are trying to decrease number of classes involved in
963 such calculation. Register classes used in the cost calculation
964 are called important classes. They are allocno classes and other
965 non-empty classes whose allocatable hard register sets are inside
966 of an allocno class hard register set. From the first sight, it
967 looks like that they are just allocno classes. It is not true. In
968 example of x86-port in 32-bit mode, allocno classes will contain
969 GENERAL_REGS but not LEGACY_REGS (because allocatable hard
970 registers are the same for the both classes). The important
971 classes will contain GENERAL_REGS and LEGACY_REGS. It is done
972 because a machine description insn constraint may refers for
973 LEGACY_REGS and code in ira-costs.c is mostly base on investigation
974 of the insn constraints. */
976 setup_allocno_and_important_classes (void)
980 HARD_REG_SET temp_hard_regset2
;
981 static enum reg_class classes
[LIM_REG_CLASSES
+ 1];
984 /* Collect classes which contain unique sets of allocatable hard
985 registers. Prefer GENERAL_REGS to other classes containing the
986 same set of hard registers. */
987 for (i
= 0; i
< LIM_REG_CLASSES
; i
++)
989 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[i
]);
990 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
991 for (j
= 0; j
< n
; j
++)
994 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl
]);
995 AND_COMPL_HARD_REG_SET (temp_hard_regset2
,
997 if (hard_reg_set_equal_p (temp_hard_regset
,
1002 classes
[n
++] = (enum reg_class
) i
;
1003 else if (i
== GENERAL_REGS
)
1004 /* Prefer general regs. For i386 example, it means that
1005 we prefer GENERAL_REGS over INDEX_REGS or LEGACY_REGS
1006 (all of them consists of the same available hard
1008 classes
[j
] = (enum reg_class
) i
;
1010 classes
[n
] = LIM_REG_CLASSES
;
1012 /* Set up classes which can be used for allocnos as classes
1013 conatining non-empty unique sets of allocatable hard
1015 ira_allocno_classes_num
= 0;
1016 for (i
= 0; (cl
= classes
[i
]) != LIM_REG_CLASSES
; i
++)
1017 if (ira_class_hard_regs_num
[cl
] > 0)
1018 ira_allocno_classes
[ira_allocno_classes_num
++] = (enum reg_class
) cl
;
1019 ira_important_classes_num
= 0;
1020 /* Add non-allocno classes containing to non-empty set of
1021 allocatable hard regs. */
1022 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1023 if (ira_class_hard_regs_num
[cl
] > 0)
1025 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
1026 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1028 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1030 COPY_HARD_REG_SET (temp_hard_regset2
,
1031 reg_class_contents
[ira_allocno_classes
[j
]]);
1032 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
1033 if ((enum reg_class
) cl
== ira_allocno_classes
[j
])
1035 else if (hard_reg_set_subset_p (temp_hard_regset
,
1039 if (set_p
&& j
>= ira_allocno_classes_num
)
1040 ira_important_classes
[ira_important_classes_num
++]
1041 = (enum reg_class
) cl
;
1043 /* Now add allocno classes to the important classes. */
1044 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1045 ira_important_classes
[ira_important_classes_num
++]
1046 = ira_allocno_classes
[j
];
1047 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1049 ira_reg_allocno_class_p
[cl
] = false;
1050 ira_reg_pressure_class_p
[cl
] = false;
1052 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1053 ira_reg_allocno_class_p
[ira_allocno_classes
[j
]] = true;
1054 setup_pressure_classes ();
1055 setup_uniform_class_p ();
1058 /* Setup translation in CLASS_TRANSLATE of all classes into a class
1059 given by array CLASSES of length CLASSES_NUM. The function is used
1060 make translation any reg class to an allocno class or to an
1061 pressure class. This translation is necessary for some
1062 calculations when we can use only allocno or pressure classes and
1063 such translation represents an approximate representation of all
1066 The translation in case when allocatable hard register set of a
1067 given class is subset of allocatable hard register set of a class
1068 in CLASSES is pretty simple. We use smallest classes from CLASSES
1069 containing a given class. If allocatable hard register set of a
1070 given class is not a subset of any corresponding set of a class
1071 from CLASSES, we use the cheapest (with load/store point of view)
1072 class from CLASSES whose set intersects with given class set */
1074 setup_class_translate_array (enum reg_class
*class_translate
,
1075 int classes_num
, enum reg_class
*classes
)
1078 enum reg_class aclass
, best_class
, *cl_ptr
;
1079 int i
, cost
, min_cost
, best_cost
;
1081 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1082 class_translate
[cl
] = NO_REGS
;
1084 for (i
= 0; i
< classes_num
; i
++)
1086 aclass
= classes
[i
];
1087 for (cl_ptr
= &alloc_reg_class_subclasses
[aclass
][0];
1088 (cl
= *cl_ptr
) != LIM_REG_CLASSES
;
1090 if (class_translate
[cl
] == NO_REGS
)
1091 class_translate
[cl
] = aclass
;
1092 class_translate
[aclass
] = aclass
;
1094 /* For classes which are not fully covered by one of given classes
1095 (in other words covered by more one given class), use the
1097 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1099 if (cl
== NO_REGS
|| class_translate
[cl
] != NO_REGS
)
1101 best_class
= NO_REGS
;
1102 best_cost
= INT_MAX
;
1103 for (i
= 0; i
< classes_num
; i
++)
1105 aclass
= classes
[i
];
1106 COPY_HARD_REG_SET (temp_hard_regset
,
1107 reg_class_contents
[aclass
]);
1108 AND_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
1109 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1110 if (! hard_reg_set_empty_p (temp_hard_regset
))
1113 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
1115 cost
= (ira_memory_move_cost
[mode
][aclass
][0]
1116 + ira_memory_move_cost
[mode
][aclass
][1]);
1117 if (min_cost
> cost
)
1120 if (best_class
== NO_REGS
|| best_cost
> min_cost
)
1122 best_class
= aclass
;
1123 best_cost
= min_cost
;
1127 class_translate
[cl
] = best_class
;
1131 /* Set up array IRA_ALLOCNO_CLASS_TRANSLATE and
1132 IRA_PRESSURE_CLASS_TRANSLATE. */
1134 setup_class_translate (void)
1136 setup_class_translate_array (ira_allocno_class_translate
,
1137 ira_allocno_classes_num
, ira_allocno_classes
);
1138 setup_class_translate_array (ira_pressure_class_translate
,
1139 ira_pressure_classes_num
, ira_pressure_classes
);
1142 /* Order numbers of allocno classes in original target allocno class
1143 array, -1 for non-allocno classes. */
1144 static int allocno_class_order
[N_REG_CLASSES
];
1146 /* The function used to sort the important classes. */
1148 comp_reg_classes_func (const void *v1p
, const void *v2p
)
1150 enum reg_class cl1
= *(const enum reg_class
*) v1p
;
1151 enum reg_class cl2
= *(const enum reg_class
*) v2p
;
1152 enum reg_class tcl1
, tcl2
;
1155 tcl1
= ira_allocno_class_translate
[cl1
];
1156 tcl2
= ira_allocno_class_translate
[cl2
];
1157 if (tcl1
!= NO_REGS
&& tcl2
!= NO_REGS
1158 && (diff
= allocno_class_order
[tcl1
] - allocno_class_order
[tcl2
]) != 0)
1160 return (int) cl1
- (int) cl2
;
1163 /* For correct work of function setup_reg_class_relation we need to
1164 reorder important classes according to the order of their allocno
1165 classes. It places important classes containing the same
1166 allocatable hard register set adjacent to each other and allocno
1167 class with the allocatable hard register set right after the other
1168 important classes with the same set.
1170 In example from comments of function
1171 setup_allocno_and_important_classes, it places LEGACY_REGS and
1172 GENERAL_REGS close to each other and GENERAL_REGS is after
1175 reorder_important_classes (void)
1179 for (i
= 0; i
< N_REG_CLASSES
; i
++)
1180 allocno_class_order
[i
] = -1;
1181 for (i
= 0; i
< ira_allocno_classes_num
; i
++)
1182 allocno_class_order
[ira_allocno_classes
[i
]] = i
;
1183 qsort (ira_important_classes
, ira_important_classes_num
,
1184 sizeof (enum reg_class
), comp_reg_classes_func
);
1185 for (i
= 0; i
< ira_important_classes_num
; i
++)
1186 ira_important_class_nums
[ira_important_classes
[i
]] = i
;
1189 /* Set up IRA_REG_CLASS_SUBUNION, IRA_REG_CLASS_SUPERUNION,
1190 IRA_REG_CLASS_SUPER_CLASSES, IRA_REG_CLASSES_INTERSECT, and
1191 IRA_REG_CLASSES_INTERSECT_P. For the meaning of the relations,
1192 please see corresponding comments in ira-int.h. */
1194 setup_reg_class_relations (void)
1196 int i
, cl1
, cl2
, cl3
;
1197 HARD_REG_SET intersection_set
, union_set
, temp_set2
;
1198 bool important_class_p
[N_REG_CLASSES
];
1200 memset (important_class_p
, 0, sizeof (important_class_p
));
1201 for (i
= 0; i
< ira_important_classes_num
; i
++)
1202 important_class_p
[ira_important_classes
[i
]] = true;
1203 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1205 ira_reg_class_super_classes
[cl1
][0] = LIM_REG_CLASSES
;
1206 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1208 ira_reg_classes_intersect_p
[cl1
][cl2
] = false;
1209 ira_reg_class_intersect
[cl1
][cl2
] = NO_REGS
;
1210 ira_reg_class_subset
[cl1
][cl2
] = NO_REGS
;
1211 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl1
]);
1212 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1213 COPY_HARD_REG_SET (temp_set2
, reg_class_contents
[cl2
]);
1214 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1215 if (hard_reg_set_empty_p (temp_hard_regset
)
1216 && hard_reg_set_empty_p (temp_set2
))
1218 /* The both classes have no allocatable hard registers
1219 -- take all class hard registers into account and use
1220 reg_class_subunion and reg_class_superunion. */
1223 cl3
= reg_class_subclasses
[cl1
][i
];
1224 if (cl3
== LIM_REG_CLASSES
)
1226 if (reg_class_subset_p (ira_reg_class_intersect
[cl1
][cl2
],
1227 (enum reg_class
) cl3
))
1228 ira_reg_class_intersect
[cl1
][cl2
] = (enum reg_class
) cl3
;
1230 ira_reg_class_subunion
[cl1
][cl2
] = reg_class_subunion
[cl1
][cl2
];
1231 ira_reg_class_superunion
[cl1
][cl2
] = reg_class_superunion
[cl1
][cl2
];
1234 ira_reg_classes_intersect_p
[cl1
][cl2
]
1235 = hard_reg_set_intersect_p (temp_hard_regset
, temp_set2
);
1236 if (important_class_p
[cl1
] && important_class_p
[cl2
]
1237 && hard_reg_set_subset_p (temp_hard_regset
, temp_set2
))
1239 /* CL1 and CL2 are important classes and CL1 allocatable
1240 hard register set is inside of CL2 allocatable hard
1241 registers -- make CL1 a superset of CL2. */
1244 p
= &ira_reg_class_super_classes
[cl1
][0];
1245 while (*p
!= LIM_REG_CLASSES
)
1247 *p
++ = (enum reg_class
) cl2
;
1248 *p
= LIM_REG_CLASSES
;
1250 ira_reg_class_subunion
[cl1
][cl2
] = NO_REGS
;
1251 ira_reg_class_superunion
[cl1
][cl2
] = NO_REGS
;
1252 COPY_HARD_REG_SET (intersection_set
, reg_class_contents
[cl1
]);
1253 AND_HARD_REG_SET (intersection_set
, reg_class_contents
[cl2
]);
1254 AND_COMPL_HARD_REG_SET (intersection_set
, no_unit_alloc_regs
);
1255 COPY_HARD_REG_SET (union_set
, reg_class_contents
[cl1
]);
1256 IOR_HARD_REG_SET (union_set
, reg_class_contents
[cl2
]);
1257 AND_COMPL_HARD_REG_SET (union_set
, no_unit_alloc_regs
);
1258 for (cl3
= 0; cl3
< N_REG_CLASSES
; cl3
++)
1260 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl3
]);
1261 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1262 if (hard_reg_set_subset_p (temp_hard_regset
, intersection_set
))
1264 /* CL3 allocatable hard register set is inside of
1265 intersection of allocatable hard register sets
1267 if (important_class_p
[cl3
])
1272 [(int) ira_reg_class_intersect
[cl1
][cl2
]]);
1273 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1274 if (! hard_reg_set_subset_p (temp_hard_regset
, temp_set2
)
1275 /* If the allocatable hard register sets are
1276 the same, prefer GENERAL_REGS or the
1277 smallest class for debugging
1279 || (hard_reg_set_equal_p (temp_hard_regset
, temp_set2
)
1280 && (cl3
== GENERAL_REGS
1281 || ((ira_reg_class_intersect
[cl1
][cl2
]
1283 && hard_reg_set_subset_p
1284 (reg_class_contents
[cl3
],
1287 ira_reg_class_intersect
[cl1
][cl2
]])))))
1288 ira_reg_class_intersect
[cl1
][cl2
] = (enum reg_class
) cl3
;
1292 reg_class_contents
[(int) ira_reg_class_subset
[cl1
][cl2
]]);
1293 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1294 if (! hard_reg_set_subset_p (temp_hard_regset
, temp_set2
)
1295 /* Ignore unavailable hard registers and prefer
1296 smallest class for debugging purposes. */
1297 || (hard_reg_set_equal_p (temp_hard_regset
, temp_set2
)
1298 && hard_reg_set_subset_p
1299 (reg_class_contents
[cl3
],
1301 [(int) ira_reg_class_subset
[cl1
][cl2
]])))
1302 ira_reg_class_subset
[cl1
][cl2
] = (enum reg_class
) cl3
;
1304 if (important_class_p
[cl3
]
1305 && hard_reg_set_subset_p (temp_hard_regset
, union_set
))
1307 /* CL3 allocatbale hard register set is inside of
1308 union of allocatable hard register sets of CL1
1312 reg_class_contents
[(int) ira_reg_class_subunion
[cl1
][cl2
]]);
1313 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1314 if (ira_reg_class_subunion
[cl1
][cl2
] == NO_REGS
1315 || (hard_reg_set_subset_p (temp_set2
, temp_hard_regset
)
1317 && (! hard_reg_set_equal_p (temp_set2
,
1319 || cl3
== GENERAL_REGS
1320 /* If the allocatable hard register sets are the
1321 same, prefer GENERAL_REGS or the smallest
1322 class for debugging purposes. */
1323 || (ira_reg_class_subunion
[cl1
][cl2
] != GENERAL_REGS
1324 && hard_reg_set_subset_p
1325 (reg_class_contents
[cl3
],
1327 [(int) ira_reg_class_subunion
[cl1
][cl2
]])))))
1328 ira_reg_class_subunion
[cl1
][cl2
] = (enum reg_class
) cl3
;
1330 if (hard_reg_set_subset_p (union_set
, temp_hard_regset
))
1332 /* CL3 allocatable hard register set contains union
1333 of allocatable hard register sets of CL1 and
1337 reg_class_contents
[(int) ira_reg_class_superunion
[cl1
][cl2
]]);
1338 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1339 if (ira_reg_class_superunion
[cl1
][cl2
] == NO_REGS
1340 || (hard_reg_set_subset_p (temp_hard_regset
, temp_set2
)
1342 && (! hard_reg_set_equal_p (temp_set2
,
1344 || cl3
== GENERAL_REGS
1345 /* If the allocatable hard register sets are the
1346 same, prefer GENERAL_REGS or the smallest
1347 class for debugging purposes. */
1348 || (ira_reg_class_superunion
[cl1
][cl2
] != GENERAL_REGS
1349 && hard_reg_set_subset_p
1350 (reg_class_contents
[cl3
],
1352 [(int) ira_reg_class_superunion
[cl1
][cl2
]])))))
1353 ira_reg_class_superunion
[cl1
][cl2
] = (enum reg_class
) cl3
;
1360 /* Output all unifrom and important classes into file F. */
1362 print_unform_and_important_classes (FILE *f
)
1364 static const char *const reg_class_names
[] = REG_CLASS_NAMES
;
1367 fprintf (f
, "Uniform classes:\n");
1368 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1369 if (ira_uniform_class_p
[cl
])
1370 fprintf (f
, " %s", reg_class_names
[cl
]);
1371 fprintf (f
, "\nImportant classes:\n");
1372 for (i
= 0; i
< ira_important_classes_num
; i
++)
1373 fprintf (f
, " %s", reg_class_names
[ira_important_classes
[i
]]);
1377 /* Output all possible allocno or pressure classes and their
1378 translation map into file F. */
1380 print_translated_classes (FILE *f
, bool pressure_p
)
1382 int classes_num
= (pressure_p
1383 ? ira_pressure_classes_num
: ira_allocno_classes_num
);
1384 enum reg_class
*classes
= (pressure_p
1385 ? ira_pressure_classes
: ira_allocno_classes
);
1386 enum reg_class
*class_translate
= (pressure_p
1387 ? ira_pressure_class_translate
1388 : ira_allocno_class_translate
);
1389 static const char *const reg_class_names
[] = REG_CLASS_NAMES
;
1392 fprintf (f
, "%s classes:\n", pressure_p
? "Pressure" : "Allocno");
1393 for (i
= 0; i
< classes_num
; i
++)
1394 fprintf (f
, " %s", reg_class_names
[classes
[i
]]);
1395 fprintf (f
, "\nClass translation:\n");
1396 for (i
= 0; i
< N_REG_CLASSES
; i
++)
1397 fprintf (f
, " %s -> %s\n", reg_class_names
[i
],
1398 reg_class_names
[class_translate
[i
]]);
1401 /* Output all possible allocno and translation classes and the
1402 translation maps into stderr. */
1404 ira_debug_allocno_classes (void)
1406 print_unform_and_important_classes (stderr
);
1407 print_translated_classes (stderr
, false);
1408 print_translated_classes (stderr
, true);
1411 /* Set up different arrays concerning class subsets, allocno and
1412 important classes. */
1414 find_reg_classes (void)
1416 setup_allocno_and_important_classes ();
1417 setup_class_translate ();
1418 reorder_important_classes ();
1419 setup_reg_class_relations ();
1424 /* Set up the array above. */
1426 setup_hard_regno_aclass (void)
1430 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1433 ira_hard_regno_allocno_class
[i
]
1434 = (TEST_HARD_REG_BIT (no_unit_alloc_regs
, i
)
1436 : ira_allocno_class_translate
[REGNO_REG_CLASS (i
)]);
1440 ira_hard_regno_allocno_class
[i
] = NO_REGS
;
1441 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1443 cl
= ira_allocno_classes
[j
];
1444 if (ira_class_hard_reg_index
[cl
][i
] >= 0)
1446 ira_hard_regno_allocno_class
[i
] = cl
;
1456 /* Form IRA_REG_CLASS_MAX_NREGS and IRA_REG_CLASS_MIN_NREGS maps. */
1458 setup_reg_class_nregs (void)
1462 for (m
= 0; m
< MAX_MACHINE_MODE
; m
++)
1464 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1465 ira_reg_class_max_nregs
[cl
][m
]
1466 = ira_reg_class_min_nregs
[cl
][m
]
1467 = targetm
.class_max_nregs ((reg_class_t
) cl
, (enum machine_mode
) m
);
1468 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1470 (cl2
= alloc_reg_class_subclasses
[cl
][i
]) != LIM_REG_CLASSES
;
1472 if (ira_reg_class_min_nregs
[cl2
][m
]
1473 < ira_reg_class_min_nregs
[cl
][m
])
1474 ira_reg_class_min_nregs
[cl
][m
] = ira_reg_class_min_nregs
[cl2
][m
];
1480 /* Set up IRA_PROHIBITED_CLASS_MODE_REGS and IRA_CLASS_SINGLETON.
1481 This function is called once IRA_CLASS_HARD_REGS has been initialized. */
1483 setup_prohibited_class_mode_regs (void)
1485 int j
, k
, hard_regno
, cl
, last_hard_regno
, count
;
1487 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
1489 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
1490 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1491 for (j
= 0; j
< NUM_MACHINE_MODES
; j
++)
1494 last_hard_regno
= -1;
1495 CLEAR_HARD_REG_SET (ira_prohibited_class_mode_regs
[cl
][j
]);
1496 for (k
= ira_class_hard_regs_num
[cl
] - 1; k
>= 0; k
--)
1498 hard_regno
= ira_class_hard_regs
[cl
][k
];
1499 if (! HARD_REGNO_MODE_OK (hard_regno
, (enum machine_mode
) j
))
1500 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1502 else if (in_hard_reg_set_p (temp_hard_regset
,
1503 (enum machine_mode
) j
, hard_regno
))
1505 last_hard_regno
= hard_regno
;
1509 ira_class_singleton
[cl
][j
] = (count
== 1 ? last_hard_regno
: -1);
1514 /* Clarify IRA_PROHIBITED_CLASS_MODE_REGS by excluding hard registers
1515 spanning from one register pressure class to another one. It is
1516 called after defining the pressure classes. */
1518 clarify_prohibited_class_mode_regs (void)
1520 int j
, k
, hard_regno
, cl
, pclass
, nregs
;
1522 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
1523 for (j
= 0; j
< NUM_MACHINE_MODES
; j
++)
1525 CLEAR_HARD_REG_SET (ira_useful_class_mode_regs
[cl
][j
]);
1526 for (k
= ira_class_hard_regs_num
[cl
] - 1; k
>= 0; k
--)
1528 hard_regno
= ira_class_hard_regs
[cl
][k
];
1529 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
], hard_regno
))
1531 nregs
= hard_regno_nregs
[hard_regno
][j
];
1532 if (hard_regno
+ nregs
> FIRST_PSEUDO_REGISTER
)
1534 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1538 pclass
= ira_pressure_class_translate
[REGNO_REG_CLASS (hard_regno
)];
1539 for (nregs
-- ;nregs
>= 0; nregs
--)
1540 if (((enum reg_class
) pclass
1541 != ira_pressure_class_translate
[REGNO_REG_CLASS
1542 (hard_regno
+ nregs
)]))
1544 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1548 if (!TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1550 add_to_hard_reg_set (&ira_useful_class_mode_regs
[cl
][j
],
1551 (enum machine_mode
) j
, hard_regno
);
1556 /* Allocate and initialize IRA_REGISTER_MOVE_COST, IRA_MAY_MOVE_IN_COST
1557 and IRA_MAY_MOVE_OUT_COST for MODE. */
1559 ira_init_register_move_cost (enum machine_mode mode
)
1561 static unsigned short last_move_cost
[N_REG_CLASSES
][N_REG_CLASSES
];
1562 bool all_match
= true;
1563 unsigned int cl1
, cl2
;
1565 ira_assert (ira_register_move_cost
[mode
] == NULL
1566 && ira_may_move_in_cost
[mode
] == NULL
1567 && ira_may_move_out_cost
[mode
] == NULL
);
1568 ira_assert (have_regs_of_mode
[mode
]);
1569 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1570 if (contains_reg_of_mode
[cl1
][mode
])
1571 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1574 if (!contains_reg_of_mode
[cl2
][mode
])
1578 cost
= register_move_cost (mode
, (enum reg_class
) cl1
,
1579 (enum reg_class
) cl2
);
1580 ira_assert (cost
< 65535);
1582 all_match
&= (last_move_cost
[cl1
][cl2
] == cost
);
1583 last_move_cost
[cl1
][cl2
] = cost
;
1585 if (all_match
&& last_mode_for_init_move_cost
!= -1)
1587 ira_register_move_cost
[mode
]
1588 = ira_register_move_cost
[last_mode_for_init_move_cost
];
1589 ira_may_move_in_cost
[mode
]
1590 = ira_may_move_in_cost
[last_mode_for_init_move_cost
];
1591 ira_may_move_out_cost
[mode
]
1592 = ira_may_move_out_cost
[last_mode_for_init_move_cost
];
1595 last_mode_for_init_move_cost
= mode
;
1596 ira_register_move_cost
[mode
] = XNEWVEC (move_table
, N_REG_CLASSES
);
1597 ira_may_move_in_cost
[mode
] = XNEWVEC (move_table
, N_REG_CLASSES
);
1598 ira_may_move_out_cost
[mode
] = XNEWVEC (move_table
, N_REG_CLASSES
);
1599 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1600 if (contains_reg_of_mode
[cl1
][mode
])
1601 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1604 enum reg_class
*p1
, *p2
;
1606 if (last_move_cost
[cl1
][cl2
] == 65535)
1608 ira_register_move_cost
[mode
][cl1
][cl2
] = 65535;
1609 ira_may_move_in_cost
[mode
][cl1
][cl2
] = 65535;
1610 ira_may_move_out_cost
[mode
][cl1
][cl2
] = 65535;
1614 cost
= last_move_cost
[cl1
][cl2
];
1616 for (p2
= ®_class_subclasses
[cl2
][0];
1617 *p2
!= LIM_REG_CLASSES
; p2
++)
1618 if (ira_class_hard_regs_num
[*p2
] > 0
1619 && (ira_reg_class_max_nregs
[*p2
][mode
]
1620 <= ira_class_hard_regs_num
[*p2
]))
1621 cost
= MAX (cost
, ira_register_move_cost
[mode
][cl1
][*p2
]);
1623 for (p1
= ®_class_subclasses
[cl1
][0];
1624 *p1
!= LIM_REG_CLASSES
; p1
++)
1625 if (ira_class_hard_regs_num
[*p1
] > 0
1626 && (ira_reg_class_max_nregs
[*p1
][mode
]
1627 <= ira_class_hard_regs_num
[*p1
]))
1628 cost
= MAX (cost
, ira_register_move_cost
[mode
][*p1
][cl2
]);
1630 ira_assert (cost
<= 65535);
1631 ira_register_move_cost
[mode
][cl1
][cl2
] = cost
;
1633 if (ira_class_subset_p
[cl1
][cl2
])
1634 ira_may_move_in_cost
[mode
][cl1
][cl2
] = 0;
1636 ira_may_move_in_cost
[mode
][cl1
][cl2
] = cost
;
1638 if (ira_class_subset_p
[cl2
][cl1
])
1639 ira_may_move_out_cost
[mode
][cl1
][cl2
] = 0;
1641 ira_may_move_out_cost
[mode
][cl1
][cl2
] = cost
;
1645 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1647 ira_register_move_cost
[mode
][cl1
][cl2
] = 65535;
1648 ira_may_move_in_cost
[mode
][cl1
][cl2
] = 65535;
1649 ira_may_move_out_cost
[mode
][cl1
][cl2
] = 65535;
1654 /* This is called once during compiler work. It sets up
1655 different arrays whose values don't depend on the compiled
1658 ira_init_once (void)
1660 ira_init_costs_once ();
1664 /* Free ira_max_register_move_cost, ira_may_move_in_cost and
1665 ira_may_move_out_cost for each mode. */
1667 free_register_move_costs (void)
1671 /* Reset move_cost and friends, making sure we only free shared
1672 table entries once. */
1673 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
1674 if (ira_register_move_cost
[mode
])
1677 i
< mode
&& (ira_register_move_cost
[i
]
1678 != ira_register_move_cost
[mode
]);
1683 free (ira_register_move_cost
[mode
]);
1684 free (ira_may_move_in_cost
[mode
]);
1685 free (ira_may_move_out_cost
[mode
]);
1688 memset (ira_register_move_cost
, 0, sizeof ira_register_move_cost
);
1689 memset (ira_may_move_in_cost
, 0, sizeof ira_may_move_in_cost
);
1690 memset (ira_may_move_out_cost
, 0, sizeof ira_may_move_out_cost
);
1691 last_mode_for_init_move_cost
= -1;
1694 /* This is called every time when register related information is
1699 free_register_move_costs ();
1700 setup_reg_mode_hard_regset ();
1701 setup_alloc_regs (flag_omit_frame_pointer
!= 0);
1702 setup_class_subset_and_memory_move_costs ();
1703 setup_reg_class_nregs ();
1704 setup_prohibited_class_mode_regs ();
1705 find_reg_classes ();
1706 clarify_prohibited_class_mode_regs ();
1707 setup_hard_regno_aclass ();
1712 /* Function called once at the end of compiler work. */
1714 ira_finish_once (void)
1716 ira_finish_costs_once ();
1717 free_register_move_costs ();
1722 #define ira_prohibited_mode_move_regs_initialized_p \
1723 (this_target_ira_int->x_ira_prohibited_mode_move_regs_initialized_p)
1725 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS. */
1727 setup_prohibited_mode_move_regs (void)
1730 rtx test_reg1
, test_reg2
, move_pat
, move_insn
;
1732 if (ira_prohibited_mode_move_regs_initialized_p
)
1734 ira_prohibited_mode_move_regs_initialized_p
= true;
1735 test_reg1
= gen_rtx_REG (VOIDmode
, 0);
1736 test_reg2
= gen_rtx_REG (VOIDmode
, 0);
1737 move_pat
= gen_rtx_SET (VOIDmode
, test_reg1
, test_reg2
);
1738 move_insn
= gen_rtx_INSN (VOIDmode
, 0, 0, 0, 0, move_pat
, 0, -1, 0);
1739 for (i
= 0; i
< NUM_MACHINE_MODES
; i
++)
1741 SET_HARD_REG_SET (ira_prohibited_mode_move_regs
[i
]);
1742 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1744 if (! HARD_REGNO_MODE_OK (j
, (enum machine_mode
) i
))
1746 SET_REGNO_RAW (test_reg1
, j
);
1747 PUT_MODE (test_reg1
, (enum machine_mode
) i
);
1748 SET_REGNO_RAW (test_reg2
, j
);
1749 PUT_MODE (test_reg2
, (enum machine_mode
) i
);
1750 INSN_CODE (move_insn
) = -1;
1751 recog_memoized (move_insn
);
1752 if (INSN_CODE (move_insn
) < 0)
1754 extract_insn (move_insn
);
1755 if (! constrain_operands (1))
1757 CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs
[i
], j
);
1764 /* Return TRUE if the operand constraint STR is commutative. */
1766 commutative_constraint_p (const char *str
)
1771 for (ignore_p
= false, curr_alt
= 0;;)
1776 str
+= CONSTRAINT_LEN (c
, str
);
1777 if (c
== '#' || !recog_data
.alternative_enabled_p
[curr_alt
])
1784 else if (! ignore_p
)
1786 /* Usually `%' is the first constraint character but the
1787 documentation does not require this. */
1795 /* Setup possible alternatives in ALTS for INSN. */
1797 ira_setup_alts (rtx insn
, HARD_REG_SET
&alts
)
1799 /* MAP nalt * nop -> start of constraints for given operand and
1801 static vec
<const char *> insn_constraints
;
1806 int commutative
= -1;
1808 extract_insn (insn
);
1809 CLEAR_HARD_REG_SET (alts
);
1810 insn_constraints
.release ();
1811 insn_constraints
.safe_grow_cleared (recog_data
.n_operands
1812 * recog_data
.n_alternatives
+ 1);
1813 /* Check that the hard reg set is enough for holding all
1814 alternatives. It is hard to imagine the situation when the
1815 assertion is wrong. */
1816 ira_assert (recog_data
.n_alternatives
1817 <= (int) MAX (sizeof (HARD_REG_ELT_TYPE
) * CHAR_BIT
,
1818 FIRST_PSEUDO_REGISTER
));
1819 for (curr_swapped
= false;; curr_swapped
= true)
1821 /* Calculate some data common for all alternatives to speed up the
1823 for (nop
= 0; nop
< recog_data
.n_operands
; nop
++)
1825 for (nalt
= 0, p
= recog_data
.constraints
[nop
];
1826 nalt
< recog_data
.n_alternatives
;
1829 insn_constraints
[nop
* recog_data
.n_alternatives
+ nalt
] = p
;
1830 while (*p
&& *p
!= ',')
1836 for (nalt
= 0; nalt
< recog_data
.n_alternatives
; nalt
++)
1838 if (! recog_data
.alternative_enabled_p
[nalt
] || TEST_HARD_REG_BIT (alts
, nalt
))
1841 for (nop
= 0; nop
< recog_data
.n_operands
; nop
++)
1845 op
= recog_data
.operand
[nop
];
1846 p
= insn_constraints
[nop
* recog_data
.n_alternatives
+ nalt
];
1847 if (*p
== 0 || *p
== ',')
1851 switch (c
= *p
, len
= CONSTRAINT_LEN (c
, p
), c
)
1860 case '?': case '!': case '*': case '=': case '+':
1864 /* We only support one commutative marker, the
1865 first one. We already set commutative
1867 if (commutative
< 0)
1874 case '0': case '1': case '2': case '3': case '4':
1875 case '5': case '6': case '7': case '8': case '9':
1882 case TARGET_MEM_CONSTRAINT
:
1888 && (GET_CODE (XEXP (op
, 0)) == PRE_DEC
1889 || GET_CODE (XEXP (op
, 0)) == POST_DEC
))
1895 && (GET_CODE (XEXP (op
, 0)) == PRE_INC
1896 || GET_CODE (XEXP (op
, 0)) == POST_INC
))
1902 if (CONST_DOUBLE_AS_FLOAT_P (op
)
1903 || (GET_CODE (op
) == CONST_VECTOR
1904 && GET_MODE_CLASS (GET_MODE (op
)) == MODE_VECTOR_FLOAT
))
1910 if (CONST_DOUBLE_AS_FLOAT_P (op
)
1911 && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (op
, c
, p
))
1916 if (CONST_SCALAR_INT_P (op
))
1919 if (CONSTANT_P (op
))
1924 if (CONST_SCALAR_INT_P (op
))
1936 if (CONST_INT_P (op
)
1937 && CONST_OK_FOR_CONSTRAINT_P (INTVAL (op
), c
, p
))
1942 if (MEM_P (op
) && ! offsettable_memref_p (op
))
1954 cl
= (c
== 'r' ? GENERAL_REGS
: REG_CLASS_FROM_CONSTRAINT (c
, p
));
1957 #ifdef EXTRA_CONSTRAINT_STR
1958 else if (EXTRA_CONSTRAINT_STR (op
, c
, p
))
1960 else if (EXTRA_MEMORY_CONSTRAINT (c
, p
))
1962 else if (EXTRA_ADDRESS_CONSTRAINT (c
, p
))
1968 while (p
+= len
, c
);
1973 if (nop
>= recog_data
.n_operands
)
1974 SET_HARD_REG_BIT (alts
, nalt
);
1976 if (commutative
< 0)
1980 op
= recog_data
.operand
[commutative
];
1981 recog_data
.operand
[commutative
] = recog_data
.operand
[commutative
+ 1];
1982 recog_data
.operand
[commutative
+ 1] = op
;
1987 /* Return the number of the output non-early clobber operand which
1988 should be the same in any case as operand with number OP_NUM (or
1989 negative value if there is no such operand). The function takes
1990 only really possible alternatives into consideration. */
1992 ira_get_dup_out_num (int op_num
, HARD_REG_SET
&alts
)
1994 int curr_alt
, c
, original
, dup
;
1995 bool ignore_p
, use_commut_op_p
;
1997 #ifdef EXTRA_CONSTRAINT_STR
2001 if (op_num
< 0 || recog_data
.n_alternatives
== 0)
2003 use_commut_op_p
= false;
2004 str
= recog_data
.constraints
[op_num
];
2007 #ifdef EXTRA_CONSTRAINT_STR
2008 op
= recog_data
.operand
[op_num
];
2011 for (ignore_p
= false, original
= -1, curr_alt
= 0;;)
2016 if (c
== '#' || !TEST_HARD_REG_BIT (alts
, curr_alt
))
2023 else if (! ignore_p
)
2026 /* We should find duplications only for input operands. */
2035 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
2036 case 'h': case 'j': case 'k': case 'l':
2037 case 'q': case 't': case 'u':
2038 case 'v': case 'w': case 'x': case 'y': case 'z':
2039 case 'A': case 'B': case 'C': case 'D':
2040 case 'Q': case 'R': case 'S': case 'T': case 'U':
2041 case 'W': case 'Y': case 'Z':
2046 ? GENERAL_REGS
: REG_CLASS_FROM_CONSTRAINT (c
, str
));
2049 if (! targetm
.class_likely_spilled_p (cl
))
2052 #ifdef EXTRA_CONSTRAINT_STR
2053 else if (EXTRA_CONSTRAINT_STR (op
, c
, str
))
2059 case '0': case '1': case '2': case '3': case '4':
2060 case '5': case '6': case '7': case '8': case '9':
2061 if (original
!= -1 && original
!= c
)
2066 str
+= CONSTRAINT_LEN (c
, str
);
2071 for (ignore_p
= false, str
= recog_data
.constraints
[original
- '0'];
2079 else if (*str
== '#')
2081 else if (! ignore_p
)
2084 dup
= original
- '0';
2085 /* It is better ignore an alternative with early clobber. */
2086 else if (*str
== '&')
2092 if (use_commut_op_p
)
2094 use_commut_op_p
= true;
2095 if (commutative_constraint_p (recog_data
.constraints
[op_num
]))
2096 str
= recog_data
.constraints
[op_num
+ 1];
2097 else if (op_num
> 0 && commutative_constraint_p (recog_data
.constraints
2099 str
= recog_data
.constraints
[op_num
- 1];
2108 /* Search forward to see if the source register of a copy insn dies
2109 before either it or the destination register is modified, but don't
2110 scan past the end of the basic block. If so, we can replace the
2111 source with the destination and let the source die in the copy
2114 This will reduce the number of registers live in that range and may
2115 enable the destination and the source coalescing, thus often saving
2116 one register in addition to a register-register copy. */
2119 decrease_live_ranges_number (void)
2122 rtx insn
, set
, src
, dest
, dest_death
, p
, q
, note
;
2125 if (! flag_expensive_optimizations
)
2129 fprintf (ira_dump_file
, "Starting decreasing number of live ranges...\n");
2132 FOR_BB_INSNS (bb
, insn
)
2134 set
= single_set (insn
);
2137 src
= SET_SRC (set
);
2138 dest
= SET_DEST (set
);
2139 if (! REG_P (src
) || ! REG_P (dest
)
2140 || find_reg_note (insn
, REG_DEAD
, src
))
2142 sregno
= REGNO (src
);
2143 dregno
= REGNO (dest
);
2145 /* We don't want to mess with hard regs if register classes
2147 if (sregno
== dregno
2148 || (targetm
.small_register_classes_for_mode_p (GET_MODE (src
))
2149 && (sregno
< FIRST_PSEUDO_REGISTER
2150 || dregno
< FIRST_PSEUDO_REGISTER
))
2151 /* We don't see all updates to SP if they are in an
2152 auto-inc memory reference, so we must disallow this
2153 optimization on them. */
2154 || sregno
== STACK_POINTER_REGNUM
2155 || dregno
== STACK_POINTER_REGNUM
)
2158 dest_death
= NULL_RTX
;
2160 for (p
= NEXT_INSN (insn
); p
; p
= NEXT_INSN (p
))
2164 if (BLOCK_FOR_INSN (p
) != bb
)
2167 if (reg_set_p (src
, p
) || reg_set_p (dest
, p
)
2168 /* If SRC is an asm-declared register, it must not be
2169 replaced in any asm. Unfortunately, the REG_EXPR
2170 tree for the asm variable may be absent in the SRC
2171 rtx, so we can't check the actual register
2172 declaration easily (the asm operand will have it,
2173 though). To avoid complicating the test for a rare
2174 case, we just don't perform register replacement
2175 for a hard reg mentioned in an asm. */
2176 || (sregno
< FIRST_PSEUDO_REGISTER
2177 && asm_noperands (PATTERN (p
)) >= 0
2178 && reg_overlap_mentioned_p (src
, PATTERN (p
)))
2179 /* Don't change hard registers used by a call. */
2180 || (CALL_P (p
) && sregno
< FIRST_PSEUDO_REGISTER
2181 && find_reg_fusage (p
, USE
, src
))
2182 /* Don't change a USE of a register. */
2183 || (GET_CODE (PATTERN (p
)) == USE
2184 && reg_overlap_mentioned_p (src
, XEXP (PATTERN (p
), 0))))
2187 /* See if all of SRC dies in P. This test is slightly
2188 more conservative than it needs to be. */
2189 if ((note
= find_regno_note (p
, REG_DEAD
, sregno
))
2190 && GET_MODE (XEXP (note
, 0)) == GET_MODE (src
))
2194 /* We can do the optimization. Scan forward from INSN
2195 again, replacing regs as we go. Set FAILED if a
2196 replacement can't be done. In that case, we can't
2197 move the death note for SRC. This should be
2200 /* Set to stop at next insn. */
2201 for (q
= next_real_insn (insn
);
2202 q
!= next_real_insn (p
);
2203 q
= next_real_insn (q
))
2205 if (reg_overlap_mentioned_p (src
, PATTERN (q
)))
2207 /* If SRC is a hard register, we might miss
2208 some overlapping registers with
2209 validate_replace_rtx, so we would have to
2210 undo it. We can't if DEST is present in
2211 the insn, so fail in that combination of
2213 if (sregno
< FIRST_PSEUDO_REGISTER
2214 && reg_mentioned_p (dest
, PATTERN (q
)))
2217 /* Attempt to replace all uses. */
2218 else if (!validate_replace_rtx (src
, dest
, q
))
2221 /* If this succeeded, but some part of the
2222 register is still present, undo the
2224 else if (sregno
< FIRST_PSEUDO_REGISTER
2225 && reg_overlap_mentioned_p (src
, PATTERN (q
)))
2227 validate_replace_rtx (dest
, src
, q
);
2232 /* If DEST dies here, remove the death note and
2233 save it for later. Make sure ALL of DEST dies
2234 here; again, this is overly conservative. */
2236 && (dest_death
= find_regno_note (q
, REG_DEAD
, dregno
)))
2238 if (GET_MODE (XEXP (dest_death
, 0)) == GET_MODE (dest
))
2239 remove_note (q
, dest_death
);
2250 /* Move death note of SRC from P to INSN. */
2251 remove_note (p
, note
);
2252 XEXP (note
, 1) = REG_NOTES (insn
);
2253 REG_NOTES (insn
) = note
;
2256 /* DEST is also dead if INSN has a REG_UNUSED note for
2260 = find_regno_note (insn
, REG_UNUSED
, dregno
)))
2262 PUT_REG_NOTE_KIND (dest_death
, REG_DEAD
);
2263 remove_note (insn
, dest_death
);
2266 /* Put death note of DEST on P if we saw it die. */
2269 XEXP (dest_death
, 1) = REG_NOTES (p
);
2270 REG_NOTES (p
) = dest_death
;
2275 /* If SRC is a hard register which is set or killed in
2276 some other way, we can't do this optimization. */
2277 else if (sregno
< FIRST_PSEUDO_REGISTER
&& dead_or_set_p (p
, src
))
2285 /* Return nonzero if REGNO is a particularly bad choice for reloading X. */
2287 ira_bad_reload_regno_1 (int regno
, rtx x
)
2291 enum reg_class pref
;
2293 /* We only deal with pseudo regs. */
2294 if (! x
|| GET_CODE (x
) != REG
)
2297 x_regno
= REGNO (x
);
2298 if (x_regno
< FIRST_PSEUDO_REGISTER
)
2301 /* If the pseudo prefers REGNO explicitly, then do not consider
2302 REGNO a bad spill choice. */
2303 pref
= reg_preferred_class (x_regno
);
2304 if (reg_class_size
[pref
] == 1)
2305 return !TEST_HARD_REG_BIT (reg_class_contents
[pref
], regno
);
2307 /* If the pseudo conflicts with REGNO, then we consider REGNO a
2308 poor choice for a reload regno. */
2309 a
= ira_regno_allocno_map
[x_regno
];
2310 n
= ALLOCNO_NUM_OBJECTS (a
);
2311 for (i
= 0; i
< n
; i
++)
2313 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2314 if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), regno
))
2320 /* Return nonzero if REGNO is a particularly bad choice for reloading
2323 ira_bad_reload_regno (int regno
, rtx in
, rtx out
)
2325 return (ira_bad_reload_regno_1 (regno
, in
)
2326 || ira_bad_reload_regno_1 (regno
, out
));
2329 /* Return TRUE if *LOC contains an asm. */
2331 insn_contains_asm_1 (rtx
*loc
, void *data ATTRIBUTE_UNUSED
)
2335 if (GET_CODE (*loc
) == ASM_OPERANDS
)
2341 /* Return TRUE if INSN contains an ASM. */
2343 insn_contains_asm (rtx insn
)
2345 return for_each_rtx (&insn
, insn_contains_asm_1
, NULL
);
2348 /* Add register clobbers from asm statements. */
2350 compute_regs_asm_clobbered (void)
2357 FOR_BB_INSNS_REVERSE (bb
, insn
)
2361 if (insn_contains_asm (insn
))
2362 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
2364 df_ref def
= *def_rec
;
2365 unsigned int dregno
= DF_REF_REGNO (def
);
2366 if (HARD_REGISTER_NUM_P (dregno
))
2367 add_to_hard_reg_set (&crtl
->asm_clobbers
,
2368 GET_MODE (DF_REF_REAL_REG (def
)),
2376 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and REGS_EVER_LIVE.
2377 If the function is called from IRA (not from the insn scheduler or
2378 RTL loop invariant motion), FROM_IRA_P is true. */
2380 ira_setup_eliminable_regset (bool from_ira_p
)
2382 #ifdef ELIMINABLE_REGS
2384 static const struct {const int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
2386 /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
2387 sp for alloca. So we can't eliminate the frame pointer in that
2388 case. At some point, we should improve this by emitting the
2389 sp-adjusting insns for this case. */
2390 frame_pointer_needed
2391 = (! flag_omit_frame_pointer
2392 || (cfun
->calls_alloca
&& EXIT_IGNORE_STACK
)
2393 /* We need the frame pointer to catch stack overflow exceptions
2394 if the stack pointer is moving. */
2395 || (flag_stack_check
&& STACK_CHECK_MOVING_SP
)
2396 || crtl
->accesses_prior_frames
2397 || crtl
->stack_realign_needed
2398 /* We need a frame pointer for all Cilk Plus functions that use
2400 || (flag_enable_cilkplus
&& cfun
->is_cilk_function
)
2401 || targetm
.frame_pointer_required ());
2403 if (from_ira_p
&& ira_use_lra_p
)
2404 /* It can change FRAME_POINTER_NEEDED. We call it only from IRA
2405 because it is expensive. */
2406 lra_init_elimination ();
2408 if (frame_pointer_needed
)
2409 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM
, true);
2411 COPY_HARD_REG_SET (ira_no_alloc_regs
, no_unit_alloc_regs
);
2412 CLEAR_HARD_REG_SET (eliminable_regset
);
2414 compute_regs_asm_clobbered ();
2416 /* Build the regset of all eliminable registers and show we can't
2417 use those that we already know won't be eliminated. */
2418 #ifdef ELIMINABLE_REGS
2419 for (i
= 0; i
< (int) ARRAY_SIZE (eliminables
); i
++)
2422 = (! targetm
.can_eliminate (eliminables
[i
].from
, eliminables
[i
].to
)
2423 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& frame_pointer_needed
));
2425 if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
, eliminables
[i
].from
))
2427 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
2430 SET_HARD_REG_BIT (ira_no_alloc_regs
, eliminables
[i
].from
);
2432 else if (cannot_elim
)
2433 error ("%s cannot be used in asm here",
2434 reg_names
[eliminables
[i
].from
]);
2436 df_set_regs_ever_live (eliminables
[i
].from
, true);
2438 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
2439 if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
, HARD_FRAME_POINTER_REGNUM
))
2441 SET_HARD_REG_BIT (eliminable_regset
, HARD_FRAME_POINTER_REGNUM
);
2442 if (frame_pointer_needed
)
2443 SET_HARD_REG_BIT (ira_no_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
2445 else if (frame_pointer_needed
)
2446 error ("%s cannot be used in asm here",
2447 reg_names
[HARD_FRAME_POINTER_REGNUM
]);
2449 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM
, true);
2453 if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
, HARD_FRAME_POINTER_REGNUM
))
2455 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
2456 if (frame_pointer_needed
)
2457 SET_HARD_REG_BIT (ira_no_alloc_regs
, FRAME_POINTER_REGNUM
);
2459 else if (frame_pointer_needed
)
2460 error ("%s cannot be used in asm here", reg_names
[FRAME_POINTER_REGNUM
]);
2462 df_set_regs_ever_live (FRAME_POINTER_REGNUM
, true);
2468 /* Vector of substitutions of register numbers,
2469 used to map pseudo regs into hardware regs.
2470 This is set up as a result of register allocation.
2471 Element N is the hard reg assigned to pseudo reg N,
2472 or is -1 if no hard reg was assigned.
2473 If N is a hard reg number, element N is N. */
2474 short *reg_renumber
;
2476 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
2477 the allocation found by IRA. */
2479 setup_reg_renumber (void)
2481 int regno
, hard_regno
;
2483 ira_allocno_iterator ai
;
2485 caller_save_needed
= 0;
2486 FOR_EACH_ALLOCNO (a
, ai
)
2488 if (ira_use_lra_p
&& ALLOCNO_CAP_MEMBER (a
) != NULL
)
2490 /* There are no caps at this point. */
2491 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
2492 if (! ALLOCNO_ASSIGNED_P (a
))
2493 /* It can happen if A is not referenced but partially anticipated
2494 somewhere in a region. */
2495 ALLOCNO_ASSIGNED_P (a
) = true;
2496 ira_free_allocno_updated_costs (a
);
2497 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2498 regno
= ALLOCNO_REGNO (a
);
2499 reg_renumber
[regno
] = (hard_regno
< 0 ? -1 : hard_regno
);
2500 if (hard_regno
>= 0)
2503 enum reg_class pclass
;
2506 pclass
= ira_pressure_class_translate
[REGNO_REG_CLASS (hard_regno
)];
2507 nwords
= ALLOCNO_NUM_OBJECTS (a
);
2508 for (i
= 0; i
< nwords
; i
++)
2510 obj
= ALLOCNO_OBJECT (a
, i
);
2511 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
2512 reg_class_contents
[pclass
]);
2514 if (ALLOCNO_CALLS_CROSSED_NUM (a
) != 0
2515 && ira_hard_reg_set_intersection_p (hard_regno
, ALLOCNO_MODE (a
),
2518 ira_assert (!optimize
|| flag_caller_saves
2519 || (ALLOCNO_CALLS_CROSSED_NUM (a
)
2520 == ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
))
2521 || regno
>= ira_reg_equiv_len
2522 || ira_equiv_no_lvalue_p (regno
));
2523 caller_save_needed
= 1;
2529 /* Set up allocno assignment flags for further allocation
2532 setup_allocno_assignment_flags (void)
2536 ira_allocno_iterator ai
;
2538 FOR_EACH_ALLOCNO (a
, ai
)
2540 if (! ALLOCNO_ASSIGNED_P (a
))
2541 /* It can happen if A is not referenced but partially anticipated
2542 somewhere in a region. */
2543 ira_free_allocno_updated_costs (a
);
2544 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2545 /* Don't assign hard registers to allocnos which are destination
2546 of removed store at the end of loop. It has no sense to keep
2547 the same value in different hard registers. It is also
2548 impossible to assign hard registers correctly to such
2549 allocnos because the cost info and info about intersected
2550 calls are incorrect for them. */
2551 ALLOCNO_ASSIGNED_P (a
) = (hard_regno
>= 0
2552 || ALLOCNO_EMIT_DATA (a
)->mem_optimized_dest_p
2553 || (ALLOCNO_MEMORY_COST (a
)
2554 - ALLOCNO_CLASS_COST (a
)) < 0);
2557 || ira_hard_reg_in_set_p (hard_regno
, ALLOCNO_MODE (a
),
2558 reg_class_contents
[ALLOCNO_CLASS (a
)]));
2562 /* Evaluate overall allocation cost and the costs for using hard
2563 registers and memory for allocnos. */
2565 calculate_allocation_cost (void)
2567 int hard_regno
, cost
;
2569 ira_allocno_iterator ai
;
2571 ira_overall_cost
= ira_reg_cost
= ira_mem_cost
= 0;
2572 FOR_EACH_ALLOCNO (a
, ai
)
2574 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2575 ira_assert (hard_regno
< 0
2576 || (ira_hard_reg_in_set_p
2577 (hard_regno
, ALLOCNO_MODE (a
),
2578 reg_class_contents
[ALLOCNO_CLASS (a
)])));
2581 cost
= ALLOCNO_MEMORY_COST (a
);
2582 ira_mem_cost
+= cost
;
2584 else if (ALLOCNO_HARD_REG_COSTS (a
) != NULL
)
2586 cost
= (ALLOCNO_HARD_REG_COSTS (a
)
2587 [ira_class_hard_reg_index
2588 [ALLOCNO_CLASS (a
)][hard_regno
]]);
2589 ira_reg_cost
+= cost
;
2593 cost
= ALLOCNO_CLASS_COST (a
);
2594 ira_reg_cost
+= cost
;
2596 ira_overall_cost
+= cost
;
2599 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
2601 fprintf (ira_dump_file
,
2602 "+++Costs: overall %d, reg %d, mem %d, ld %d, st %d, move %d\n",
2603 ira_overall_cost
, ira_reg_cost
, ira_mem_cost
,
2604 ira_load_cost
, ira_store_cost
, ira_shuffle_cost
);
2605 fprintf (ira_dump_file
, "+++ move loops %d, new jumps %d\n",
2606 ira_move_loops_num
, ira_additional_jumps_num
);
2611 #ifdef ENABLE_IRA_CHECKING
2612 /* Check the correctness of the allocation. We do need this because
2613 of complicated code to transform more one region internal
2614 representation into one region representation. */
2616 check_allocation (void)
2619 int hard_regno
, nregs
, conflict_nregs
;
2620 ira_allocno_iterator ai
;
2622 FOR_EACH_ALLOCNO (a
, ai
)
2624 int n
= ALLOCNO_NUM_OBJECTS (a
);
2627 if (ALLOCNO_CAP_MEMBER (a
) != NULL
2628 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0)
2630 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (a
)];
2632 /* We allocated a single hard register. */
2635 /* We allocated multiple hard registers, and we will test
2636 conflicts in a granularity of single hard regs. */
2639 for (i
= 0; i
< n
; i
++)
2641 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2642 ira_object_t conflict_obj
;
2643 ira_object_conflict_iterator oci
;
2644 int this_regno
= hard_regno
;
2647 if (REG_WORDS_BIG_ENDIAN
)
2648 this_regno
+= n
- i
- 1;
2652 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2654 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2655 int conflict_hard_regno
= ALLOCNO_HARD_REGNO (conflict_a
);
2656 if (conflict_hard_regno
< 0)
2661 [conflict_hard_regno
][ALLOCNO_MODE (conflict_a
)]);
2663 if (ALLOCNO_NUM_OBJECTS (conflict_a
) > 1
2664 && conflict_nregs
== ALLOCNO_NUM_OBJECTS (conflict_a
))
2666 if (REG_WORDS_BIG_ENDIAN
)
2667 conflict_hard_regno
+= (ALLOCNO_NUM_OBJECTS (conflict_a
)
2668 - OBJECT_SUBWORD (conflict_obj
) - 1);
2670 conflict_hard_regno
+= OBJECT_SUBWORD (conflict_obj
);
2674 if ((conflict_hard_regno
<= this_regno
2675 && this_regno
< conflict_hard_regno
+ conflict_nregs
)
2676 || (this_regno
<= conflict_hard_regno
2677 && conflict_hard_regno
< this_regno
+ nregs
))
2679 fprintf (stderr
, "bad allocation for %d and %d\n",
2680 ALLOCNO_REGNO (a
), ALLOCNO_REGNO (conflict_a
));
2689 /* Allocate REG_EQUIV_INIT. Set up it from IRA_REG_EQUIV which should
2690 be already calculated. */
2692 setup_reg_equiv_init (void)
2695 int max_regno
= max_reg_num ();
2697 for (i
= 0; i
< max_regno
; i
++)
2698 reg_equiv_init (i
) = ira_reg_equiv
[i
].init_insns
;
2701 /* Update equiv regno from movement of FROM_REGNO to TO_REGNO. INSNS
2702 are insns which were generated for such movement. It is assumed
2703 that FROM_REGNO and TO_REGNO always have the same value at the
2704 point of any move containing such registers. This function is used
2705 to update equiv info for register shuffles on the region borders
2706 and for caller save/restore insns. */
2708 ira_update_equiv_info_by_shuffle_insn (int to_regno
, int from_regno
, rtx insns
)
2712 if (! ira_reg_equiv
[from_regno
].defined_p
2713 && (! ira_reg_equiv
[to_regno
].defined_p
2714 || ((x
= ira_reg_equiv
[to_regno
].memory
) != NULL_RTX
2715 && ! MEM_READONLY_P (x
))))
2718 if (NEXT_INSN (insn
) != NULL_RTX
)
2720 if (! ira_reg_equiv
[to_regno
].defined_p
)
2722 ira_assert (ira_reg_equiv
[to_regno
].init_insns
== NULL_RTX
);
2725 ira_reg_equiv
[to_regno
].defined_p
= false;
2726 ira_reg_equiv
[to_regno
].memory
2727 = ira_reg_equiv
[to_regno
].constant
2728 = ira_reg_equiv
[to_regno
].invariant
2729 = ira_reg_equiv
[to_regno
].init_insns
= NULL_RTX
;
2730 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2731 fprintf (ira_dump_file
,
2732 " Invalidating equiv info for reg %d\n", to_regno
);
2735 /* It is possible that FROM_REGNO still has no equivalence because
2736 in shuffles to_regno<-from_regno and from_regno<-to_regno the 2nd
2737 insn was not processed yet. */
2738 if (ira_reg_equiv
[from_regno
].defined_p
)
2740 ira_reg_equiv
[to_regno
].defined_p
= true;
2741 if ((x
= ira_reg_equiv
[from_regno
].memory
) != NULL_RTX
)
2743 ira_assert (ira_reg_equiv
[from_regno
].invariant
== NULL_RTX
2744 && ira_reg_equiv
[from_regno
].constant
== NULL_RTX
);
2745 ira_assert (ira_reg_equiv
[to_regno
].memory
== NULL_RTX
2746 || rtx_equal_p (ira_reg_equiv
[to_regno
].memory
, x
));
2747 ira_reg_equiv
[to_regno
].memory
= x
;
2748 if (! MEM_READONLY_P (x
))
2749 /* We don't add the insn to insn init list because memory
2750 equivalence is just to say what memory is better to use
2751 when the pseudo is spilled. */
2754 else if ((x
= ira_reg_equiv
[from_regno
].constant
) != NULL_RTX
)
2756 ira_assert (ira_reg_equiv
[from_regno
].invariant
== NULL_RTX
);
2757 ira_assert (ira_reg_equiv
[to_regno
].constant
== NULL_RTX
2758 || rtx_equal_p (ira_reg_equiv
[to_regno
].constant
, x
));
2759 ira_reg_equiv
[to_regno
].constant
= x
;
2763 x
= ira_reg_equiv
[from_regno
].invariant
;
2764 ira_assert (x
!= NULL_RTX
);
2765 ira_assert (ira_reg_equiv
[to_regno
].invariant
== NULL_RTX
2766 || rtx_equal_p (ira_reg_equiv
[to_regno
].invariant
, x
));
2767 ira_reg_equiv
[to_regno
].invariant
= x
;
2769 if (find_reg_note (insn
, REG_EQUIV
, x
) == NULL_RTX
)
2771 note
= set_unique_reg_note (insn
, REG_EQUIV
, x
);
2772 gcc_assert (note
!= NULL_RTX
);
2773 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2775 fprintf (ira_dump_file
,
2776 " Adding equiv note to insn %u for reg %d ",
2777 INSN_UID (insn
), to_regno
);
2778 dump_value_slim (ira_dump_file
, x
, 1);
2779 fprintf (ira_dump_file
, "\n");
2783 ira_reg_equiv
[to_regno
].init_insns
2784 = gen_rtx_INSN_LIST (VOIDmode
, insn
,
2785 ira_reg_equiv
[to_regno
].init_insns
);
2786 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2787 fprintf (ira_dump_file
,
2788 " Adding equiv init move insn %u to reg %d\n",
2789 INSN_UID (insn
), to_regno
);
2792 /* Fix values of array REG_EQUIV_INIT after live range splitting done
2795 fix_reg_equiv_init (void)
2797 int max_regno
= max_reg_num ();
2798 int i
, new_regno
, max
;
2799 rtx x
, prev
, next
, insn
, set
;
2801 if (max_regno_before_ira
< max_regno
)
2803 max
= vec_safe_length (reg_equivs
);
2805 for (i
= FIRST_PSEUDO_REGISTER
; i
< max
; i
++)
2806 for (prev
= NULL_RTX
, x
= reg_equiv_init (i
);
2812 set
= single_set (insn
);
2813 ira_assert (set
!= NULL_RTX
2814 && (REG_P (SET_DEST (set
)) || REG_P (SET_SRC (set
))));
2815 if (REG_P (SET_DEST (set
))
2816 && ((int) REGNO (SET_DEST (set
)) == i
2817 || (int) ORIGINAL_REGNO (SET_DEST (set
)) == i
))
2818 new_regno
= REGNO (SET_DEST (set
));
2819 else if (REG_P (SET_SRC (set
))
2820 && ((int) REGNO (SET_SRC (set
)) == i
2821 || (int) ORIGINAL_REGNO (SET_SRC (set
)) == i
))
2822 new_regno
= REGNO (SET_SRC (set
));
2829 /* Remove the wrong list element. */
2830 if (prev
== NULL_RTX
)
2831 reg_equiv_init (i
) = next
;
2833 XEXP (prev
, 1) = next
;
2834 XEXP (x
, 1) = reg_equiv_init (new_regno
);
2835 reg_equiv_init (new_regno
) = x
;
2841 #ifdef ENABLE_IRA_CHECKING
2842 /* Print redundant memory-memory copies. */
2844 print_redundant_copies (void)
2848 ira_copy_t cp
, next_cp
;
2849 ira_allocno_iterator ai
;
2851 FOR_EACH_ALLOCNO (a
, ai
)
2853 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2856 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2857 if (hard_regno
>= 0)
2859 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2861 next_cp
= cp
->next_first_allocno_copy
;
2864 next_cp
= cp
->next_second_allocno_copy
;
2865 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
2866 && cp
->insn
!= NULL_RTX
2867 && ALLOCNO_HARD_REGNO (cp
->first
) == hard_regno
)
2868 fprintf (ira_dump_file
,
2869 " Redundant move from %d(freq %d):%d\n",
2870 INSN_UID (cp
->insn
), cp
->freq
, hard_regno
);
2876 /* Setup preferred and alternative classes for new pseudo-registers
2877 created by IRA starting with START. */
2879 setup_preferred_alternate_classes_for_new_pseudos (int start
)
2882 int max_regno
= max_reg_num ();
2884 for (i
= start
; i
< max_regno
; i
++)
2886 old_regno
= ORIGINAL_REGNO (regno_reg_rtx
[i
]);
2887 ira_assert (i
!= old_regno
);
2888 setup_reg_classes (i
, reg_preferred_class (old_regno
),
2889 reg_alternate_class (old_regno
),
2890 reg_allocno_class (old_regno
));
2891 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
2892 fprintf (ira_dump_file
,
2893 " New r%d: setting preferred %s, alternative %s\n",
2894 i
, reg_class_names
[reg_preferred_class (old_regno
)],
2895 reg_class_names
[reg_alternate_class (old_regno
)]);
2900 /* The number of entries allocated in teg_info. */
2901 static int allocated_reg_info_size
;
2903 /* Regional allocation can create new pseudo-registers. This function
2904 expands some arrays for pseudo-registers. */
2906 expand_reg_info (void)
2909 int size
= max_reg_num ();
2912 for (i
= allocated_reg_info_size
; i
< size
; i
++)
2913 setup_reg_classes (i
, GENERAL_REGS
, ALL_REGS
, GENERAL_REGS
);
2914 setup_preferred_alternate_classes_for_new_pseudos (allocated_reg_info_size
);
2915 allocated_reg_info_size
= size
;
2918 /* Return TRUE if there is too high register pressure in the function.
2919 It is used to decide when stack slot sharing is worth to do. */
2921 too_high_register_pressure_p (void)
2924 enum reg_class pclass
;
2926 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2928 pclass
= ira_pressure_classes
[i
];
2929 if (ira_loop_tree_root
->reg_pressure
[pclass
] > 10000)
2937 /* Indicate that hard register number FROM was eliminated and replaced with
2938 an offset from hard register number TO. The status of hard registers live
2939 at the start of a basic block is updated by replacing a use of FROM with
2943 mark_elimination (int from
, int to
)
2951 if (bitmap_bit_p (r
, from
))
2953 bitmap_clear_bit (r
, from
);
2954 bitmap_set_bit (r
, to
);
2958 r
= DF_LIVE_IN (bb
);
2959 if (bitmap_bit_p (r
, from
))
2961 bitmap_clear_bit (r
, from
);
2962 bitmap_set_bit (r
, to
);
2969 /* The length of the following array. */
2970 int ira_reg_equiv_len
;
2972 /* Info about equiv. info for each register. */
2973 struct ira_reg_equiv
*ira_reg_equiv
;
2975 /* Expand ira_reg_equiv if necessary. */
2977 ira_expand_reg_equiv (void)
2979 int old
= ira_reg_equiv_len
;
2981 if (ira_reg_equiv_len
> max_reg_num ())
2983 ira_reg_equiv_len
= max_reg_num () * 3 / 2 + 1;
2985 = (struct ira_reg_equiv
*) xrealloc (ira_reg_equiv
,
2987 * sizeof (struct ira_reg_equiv
));
2988 gcc_assert (old
< ira_reg_equiv_len
);
2989 memset (ira_reg_equiv
+ old
, 0,
2990 sizeof (struct ira_reg_equiv
) * (ira_reg_equiv_len
- old
));
2994 init_reg_equiv (void)
2996 ira_reg_equiv_len
= 0;
2997 ira_reg_equiv
= NULL
;
2998 ira_expand_reg_equiv ();
3002 finish_reg_equiv (void)
3004 free (ira_reg_equiv
);
3011 /* Set when a REG_EQUIV note is found or created. Use to
3012 keep track of what memory accesses might be created later,
3016 /* The list of each instruction which initializes this register. */
3018 /* Loop depth is used to recognize equivalences which appear
3019 to be present within the same loop (or in an inner loop). */
3021 /* Nonzero if this had a preexisting REG_EQUIV note. */
3022 int is_arg_equivalence
;
3023 /* Set when an attempt should be made to replace a register
3024 with the associated src_p entry. */
3028 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
3029 structure for that register. */
3030 static struct equivalence
*reg_equiv
;
3032 /* Used for communication between the following two functions: contains
3033 a MEM that we wish to ensure remains unchanged. */
3034 static rtx equiv_mem
;
3036 /* Set nonzero if EQUIV_MEM is modified. */
3037 static int equiv_mem_modified
;
3039 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
3040 Called via note_stores. */
3042 validate_equiv_mem_from_store (rtx dest
, const_rtx set ATTRIBUTE_UNUSED
,
3043 void *data ATTRIBUTE_UNUSED
)
3046 && reg_overlap_mentioned_p (dest
, equiv_mem
))
3048 && anti_dependence (equiv_mem
, dest
)))
3049 equiv_mem_modified
= 1;
3052 /* Verify that no store between START and the death of REG invalidates
3053 MEMREF. MEMREF is invalidated by modifying a register used in MEMREF,
3054 by storing into an overlapping memory location, or with a non-const
3057 Return 1 if MEMREF remains valid. */
3059 validate_equiv_mem (rtx start
, rtx reg
, rtx memref
)
3065 equiv_mem_modified
= 0;
3067 /* If the memory reference has side effects or is volatile, it isn't a
3068 valid equivalence. */
3069 if (side_effects_p (memref
))
3072 for (insn
= start
; insn
&& ! equiv_mem_modified
; insn
= NEXT_INSN (insn
))
3074 if (! INSN_P (insn
))
3077 if (find_reg_note (insn
, REG_DEAD
, reg
))
3080 /* This used to ignore readonly memory and const/pure calls. The problem
3081 is the equivalent form may reference a pseudo which gets assigned a
3082 call clobbered hard reg. When we later replace REG with its
3083 equivalent form, the value in the call-clobbered reg has been
3084 changed and all hell breaks loose. */
3088 note_stores (PATTERN (insn
), validate_equiv_mem_from_store
, NULL
);
3090 /* If a register mentioned in MEMREF is modified via an
3091 auto-increment, we lose the equivalence. Do the same if one
3092 dies; although we could extend the life, it doesn't seem worth
3095 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
3096 if ((REG_NOTE_KIND (note
) == REG_INC
3097 || REG_NOTE_KIND (note
) == REG_DEAD
)
3098 && REG_P (XEXP (note
, 0))
3099 && reg_overlap_mentioned_p (XEXP (note
, 0), memref
))
3106 /* Returns zero if X is known to be invariant. */
3108 equiv_init_varies_p (rtx x
)
3110 RTX_CODE code
= GET_CODE (x
);
3117 return !MEM_READONLY_P (x
) || equiv_init_varies_p (XEXP (x
, 0));
3126 return reg_equiv
[REGNO (x
)].replace
== 0 && rtx_varies_p (x
, 0);
3129 if (MEM_VOLATILE_P (x
))
3138 fmt
= GET_RTX_FORMAT (code
);
3139 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3142 if (equiv_init_varies_p (XEXP (x
, i
)))
3145 else if (fmt
[i
] == 'E')
3148 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
3149 if (equiv_init_varies_p (XVECEXP (x
, i
, j
)))
3156 /* Returns nonzero if X (used to initialize register REGNO) is movable.
3157 X is only movable if the registers it uses have equivalent initializations
3158 which appear to be within the same loop (or in an inner loop) and movable
3159 or if they are not candidates for local_alloc and don't vary. */
3161 equiv_init_movable_p (rtx x
, int regno
)
3165 enum rtx_code code
= GET_CODE (x
);
3170 return equiv_init_movable_p (SET_SRC (x
), regno
);
3185 return ((reg_equiv
[REGNO (x
)].loop_depth
>= reg_equiv
[regno
].loop_depth
3186 && reg_equiv
[REGNO (x
)].replace
)
3187 || (REG_BASIC_BLOCK (REGNO (x
)) < NUM_FIXED_BLOCKS
3188 && ! rtx_varies_p (x
, 0)));
3190 case UNSPEC_VOLATILE
:
3194 if (MEM_VOLATILE_P (x
))
3203 fmt
= GET_RTX_FORMAT (code
);
3204 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3208 if (! equiv_init_movable_p (XEXP (x
, i
), regno
))
3212 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
3213 if (! equiv_init_movable_p (XVECEXP (x
, i
, j
), regno
))
3221 /* TRUE if X uses any registers for which reg_equiv[REGNO].replace is
3224 contains_replace_regs (rtx x
)
3228 enum rtx_code code
= GET_CODE (x
);
3242 return reg_equiv
[REGNO (x
)].replace
;
3248 fmt
= GET_RTX_FORMAT (code
);
3249 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3253 if (contains_replace_regs (XEXP (x
, i
)))
3257 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
3258 if (contains_replace_regs (XVECEXP (x
, i
, j
)))
3266 /* TRUE if X references a memory location that would be affected by a store
3269 memref_referenced_p (rtx memref
, rtx x
)
3273 enum rtx_code code
= GET_CODE (x
);
3288 return (reg_equiv
[REGNO (x
)].replacement
3289 && memref_referenced_p (memref
,
3290 reg_equiv
[REGNO (x
)].replacement
));
3293 if (true_dependence (memref
, VOIDmode
, x
))
3298 /* If we are setting a MEM, it doesn't count (its address does), but any
3299 other SET_DEST that has a MEM in it is referencing the MEM. */
3300 if (MEM_P (SET_DEST (x
)))
3302 if (memref_referenced_p (memref
, XEXP (SET_DEST (x
), 0)))
3305 else if (memref_referenced_p (memref
, SET_DEST (x
)))
3308 return memref_referenced_p (memref
, SET_SRC (x
));
3314 fmt
= GET_RTX_FORMAT (code
);
3315 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3319 if (memref_referenced_p (memref
, XEXP (x
, i
)))
3323 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
3324 if (memref_referenced_p (memref
, XVECEXP (x
, i
, j
)))
3332 /* TRUE if some insn in the range (START, END] references a memory location
3333 that would be affected by a store to MEMREF. */
3335 memref_used_between_p (rtx memref
, rtx start
, rtx end
)
3339 for (insn
= NEXT_INSN (start
); insn
!= NEXT_INSN (end
);
3340 insn
= NEXT_INSN (insn
))
3342 if (!NONDEBUG_INSN_P (insn
))
3345 if (memref_referenced_p (memref
, PATTERN (insn
)))
3348 /* Nonconst functions may access memory. */
3349 if (CALL_P (insn
) && (! RTL_CONST_CALL_P (insn
)))
3356 /* Mark REG as having no known equivalence.
3357 Some instructions might have been processed before and furnished
3358 with REG_EQUIV notes for this register; these notes will have to be
3360 STORE is the piece of RTL that does the non-constant / conflicting
3361 assignment - a SET, CLOBBER or REG_INC note. It is currently not used,
3362 but needs to be there because this function is called from note_stores. */
3364 no_equiv (rtx reg
, const_rtx store ATTRIBUTE_UNUSED
,
3365 void *data ATTRIBUTE_UNUSED
)
3372 regno
= REGNO (reg
);
3373 list
= reg_equiv
[regno
].init_insns
;
3374 if (list
== const0_rtx
)
3376 reg_equiv
[regno
].init_insns
= const0_rtx
;
3377 reg_equiv
[regno
].replacement
= NULL_RTX
;
3378 /* This doesn't matter for equivalences made for argument registers, we
3379 should keep their initialization insns. */
3380 if (reg_equiv
[regno
].is_arg_equivalence
)
3382 ira_reg_equiv
[regno
].defined_p
= false;
3383 ira_reg_equiv
[regno
].init_insns
= NULL_RTX
;
3384 for (; list
; list
= XEXP (list
, 1))
3386 rtx insn
= XEXP (list
, 0);
3387 remove_note (insn
, find_reg_note (insn
, REG_EQUIV
, NULL_RTX
));
3391 /* Check whether the SUBREG is a paradoxical subreg and set the result
3395 set_paradoxical_subreg (rtx
*subreg
, void *pdx_subregs
)
3399 if ((*subreg
) == NULL_RTX
)
3401 if (GET_CODE (*subreg
) != SUBREG
)
3403 reg
= SUBREG_REG (*subreg
);
3407 if (paradoxical_subreg_p (*subreg
))
3408 ((bool *)pdx_subregs
)[REGNO (reg
)] = true;
3413 /* In DEBUG_INSN location adjust REGs from CLEARED_REGS bitmap to the
3414 equivalent replacement. */
3417 adjust_cleared_regs (rtx loc
, const_rtx old_rtx ATTRIBUTE_UNUSED
, void *data
)
3421 bitmap cleared_regs
= (bitmap
) data
;
3422 if (bitmap_bit_p (cleared_regs
, REGNO (loc
)))
3423 return simplify_replace_fn_rtx (*reg_equiv
[REGNO (loc
)].src_p
,
3424 NULL_RTX
, adjust_cleared_regs
, data
);
3429 /* Nonzero if we recorded an equivalence for a LABEL_REF. */
3430 static int recorded_label_ref
;
3432 /* Find registers that are equivalent to a single value throughout the
3433 compilation (either because they can be referenced in memory or are
3434 set once from a single constant). Lower their priority for a
3437 If such a register is only referenced once, try substituting its
3438 value into the using insn. If it succeeds, we can eliminate the
3439 register completely.
3441 Initialize init_insns in ira_reg_equiv array.
3443 Return non-zero if jump label rebuilding should be done. */
3445 update_equiv_regs (void)
3450 bitmap cleared_regs
;
3453 /* We need to keep track of whether or not we recorded a LABEL_REF so
3454 that we know if the jump optimizer needs to be rerun. */
3455 recorded_label_ref
= 0;
3457 /* Use pdx_subregs to show whether a reg is used in a paradoxical
3459 pdx_subregs
= XCNEWVEC (bool, max_regno
);
3461 reg_equiv
= XCNEWVEC (struct equivalence
, max_regno
);
3464 init_alias_analysis ();
3466 /* Scan insns and set pdx_subregs[regno] if the reg is used in a
3467 paradoxical subreg. Don't set such reg sequivalent to a mem,
3468 because lra will not substitute such equiv memory in order to
3469 prevent access beyond allocated memory for paradoxical memory subreg. */
3471 FOR_BB_INSNS (bb
, insn
)
3472 if (NONDEBUG_INSN_P (insn
))
3473 for_each_rtx (&insn
, set_paradoxical_subreg
, (void *) pdx_subregs
);
3475 /* Scan the insns and find which registers have equivalences. Do this
3476 in a separate scan of the insns because (due to -fcse-follow-jumps)
3477 a register can be set below its use. */
3480 loop_depth
= bb_loop_depth (bb
);
3482 for (insn
= BB_HEAD (bb
);
3483 insn
!= NEXT_INSN (BB_END (bb
));
3484 insn
= NEXT_INSN (insn
))
3491 if (! INSN_P (insn
))
3494 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
3495 if (REG_NOTE_KIND (note
) == REG_INC
)
3496 no_equiv (XEXP (note
, 0), note
, NULL
);
3498 set
= single_set (insn
);
3500 /* If this insn contains more (or less) than a single SET,
3501 only mark all destinations as having no known equivalence. */
3504 note_stores (PATTERN (insn
), no_equiv
, NULL
);
3507 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
3511 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
3513 rtx part
= XVECEXP (PATTERN (insn
), 0, i
);
3515 note_stores (part
, no_equiv
, NULL
);
3519 dest
= SET_DEST (set
);
3520 src
= SET_SRC (set
);
3522 /* See if this is setting up the equivalence between an argument
3523 register and its stack slot. */
3524 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
3527 gcc_assert (REG_P (dest
));
3528 regno
= REGNO (dest
);
3530 /* Note that we don't want to clear init_insns in
3531 ira_reg_equiv even if there are multiple sets of this
3533 reg_equiv
[regno
].is_arg_equivalence
= 1;
3535 /* The insn result can have equivalence memory although
3536 the equivalence is not set up by the insn. We add
3537 this insn to init insns as it is a flag for now that
3538 regno has an equivalence. We will remove the insn
3539 from init insn list later. */
3540 if (rtx_equal_p (src
, XEXP (note
, 0)) || MEM_P (XEXP (note
, 0)))
3541 ira_reg_equiv
[regno
].init_insns
3542 = gen_rtx_INSN_LIST (VOIDmode
, insn
,
3543 ira_reg_equiv
[regno
].init_insns
);
3545 /* Continue normally in case this is a candidate for
3552 /* We only handle the case of a pseudo register being set
3553 once, or always to the same value. */
3554 /* ??? The mn10200 port breaks if we add equivalences for
3555 values that need an ADDRESS_REGS register and set them equivalent
3556 to a MEM of a pseudo. The actual problem is in the over-conservative
3557 handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
3558 calculate_needs, but we traditionally work around this problem
3559 here by rejecting equivalences when the destination is in a register
3560 that's likely spilled. This is fragile, of course, since the
3561 preferred class of a pseudo depends on all instructions that set
3565 || (regno
= REGNO (dest
)) < FIRST_PSEUDO_REGISTER
3566 || reg_equiv
[regno
].init_insns
== const0_rtx
3567 || (targetm
.class_likely_spilled_p (reg_preferred_class (regno
))
3568 && MEM_P (src
) && ! reg_equiv
[regno
].is_arg_equivalence
))
3570 /* This might be setting a SUBREG of a pseudo, a pseudo that is
3571 also set somewhere else to a constant. */
3572 note_stores (set
, no_equiv
, NULL
);
3576 /* Don't set reg (if pdx_subregs[regno] == true) equivalent to a mem. */
3577 if (MEM_P (src
) && pdx_subregs
[regno
])
3579 note_stores (set
, no_equiv
, NULL
);
3583 note
= find_reg_note (insn
, REG_EQUAL
, NULL_RTX
);
3585 /* cse sometimes generates function invariants, but doesn't put a
3586 REG_EQUAL note on the insn. Since this note would be redundant,
3587 there's no point creating it earlier than here. */
3588 if (! note
&& ! rtx_varies_p (src
, 0))
3589 note
= set_unique_reg_note (insn
, REG_EQUAL
, copy_rtx (src
));
3591 /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
3592 since it represents a function call */
3593 if (note
&& GET_CODE (XEXP (note
, 0)) == EXPR_LIST
)
3596 if (DF_REG_DEF_COUNT (regno
) != 1
3598 || rtx_varies_p (XEXP (note
, 0), 0)
3599 || (reg_equiv
[regno
].replacement
3600 && ! rtx_equal_p (XEXP (note
, 0),
3601 reg_equiv
[regno
].replacement
))))
3603 no_equiv (dest
, set
, NULL
);
3606 /* Record this insn as initializing this register. */
3607 reg_equiv
[regno
].init_insns
3608 = gen_rtx_INSN_LIST (VOIDmode
, insn
, reg_equiv
[regno
].init_insns
);
3610 /* If this register is known to be equal to a constant, record that
3611 it is always equivalent to the constant. */
3612 if (DF_REG_DEF_COUNT (regno
) == 1
3613 && note
&& ! rtx_varies_p (XEXP (note
, 0), 0))
3615 rtx note_value
= XEXP (note
, 0);
3616 remove_note (insn
, note
);
3617 set_unique_reg_note (insn
, REG_EQUIV
, note_value
);
3620 /* If this insn introduces a "constant" register, decrease the priority
3621 of that register. Record this insn if the register is only used once
3622 more and the equivalence value is the same as our source.
3624 The latter condition is checked for two reasons: First, it is an
3625 indication that it may be more efficient to actually emit the insn
3626 as written (if no registers are available, reload will substitute
3627 the equivalence). Secondly, it avoids problems with any registers
3628 dying in this insn whose death notes would be missed.
3630 If we don't have a REG_EQUIV note, see if this insn is loading
3631 a register used only in one basic block from a MEM. If so, and the
3632 MEM remains unchanged for the life of the register, add a REG_EQUIV
3635 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
3637 if (note
== 0 && REG_BASIC_BLOCK (regno
) >= NUM_FIXED_BLOCKS
3638 && MEM_P (SET_SRC (set
))
3639 && validate_equiv_mem (insn
, dest
, SET_SRC (set
)))
3640 note
= set_unique_reg_note (insn
, REG_EQUIV
, copy_rtx (SET_SRC (set
)));
3644 int regno
= REGNO (dest
);
3645 rtx x
= XEXP (note
, 0);
3647 /* If we haven't done so, record for reload that this is an
3648 equivalencing insn. */
3649 if (!reg_equiv
[regno
].is_arg_equivalence
)
3650 ira_reg_equiv
[regno
].init_insns
3651 = gen_rtx_INSN_LIST (VOIDmode
, insn
,
3652 ira_reg_equiv
[regno
].init_insns
);
3654 /* Record whether or not we created a REG_EQUIV note for a LABEL_REF.
3655 We might end up substituting the LABEL_REF for uses of the
3656 pseudo here or later. That kind of transformation may turn an
3657 indirect jump into a direct jump, in which case we must rerun the
3658 jump optimizer to ensure that the JUMP_LABEL fields are valid. */
3659 if (GET_CODE (x
) == LABEL_REF
3660 || (GET_CODE (x
) == CONST
3661 && GET_CODE (XEXP (x
, 0)) == PLUS
3662 && (GET_CODE (XEXP (XEXP (x
, 0), 0)) == LABEL_REF
)))
3663 recorded_label_ref
= 1;
3665 reg_equiv
[regno
].replacement
= x
;
3666 reg_equiv
[regno
].src_p
= &SET_SRC (set
);
3667 reg_equiv
[regno
].loop_depth
= loop_depth
;
3669 /* Don't mess with things live during setjmp. */
3670 if (REG_LIVE_LENGTH (regno
) >= 0 && optimize
)
3672 /* Note that the statement below does not affect the priority
3674 REG_LIVE_LENGTH (regno
) *= 2;
3676 /* If the register is referenced exactly twice, meaning it is
3677 set once and used once, indicate that the reference may be
3678 replaced by the equivalence we computed above. Do this
3679 even if the register is only used in one block so that
3680 dependencies can be handled where the last register is
3681 used in a different block (i.e. HIGH / LO_SUM sequences)
3682 and to reduce the number of registers alive across
3685 if (REG_N_REFS (regno
) == 2
3686 && (rtx_equal_p (x
, src
)
3687 || ! equiv_init_varies_p (src
))
3688 && NONJUMP_INSN_P (insn
)
3689 && equiv_init_movable_p (PATTERN (insn
), regno
))
3690 reg_equiv
[regno
].replace
= 1;
3699 /* A second pass, to gather additional equivalences with memory. This needs
3700 to be done after we know which registers we are going to replace. */
3702 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
3707 if (! INSN_P (insn
))
3710 set
= single_set (insn
);
3714 dest
= SET_DEST (set
);
3715 src
= SET_SRC (set
);
3717 /* If this sets a MEM to the contents of a REG that is only used
3718 in a single basic block, see if the register is always equivalent
3719 to that memory location and if moving the store from INSN to the
3720 insn that set REG is safe. If so, put a REG_EQUIV note on the
3723 Don't add a REG_EQUIV note if the insn already has one. The existing
3724 REG_EQUIV is likely more useful than the one we are adding.
3726 If one of the regs in the address has reg_equiv[REGNO].replace set,
3727 then we can't add this REG_EQUIV note. The reg_equiv[REGNO].replace
3728 optimization may move the set of this register immediately before
3729 insn, which puts it after reg_equiv[REGNO].init_insns, and hence
3730 the mention in the REG_EQUIV note would be to an uninitialized
3733 if (MEM_P (dest
) && REG_P (src
)
3734 && (regno
= REGNO (src
)) >= FIRST_PSEUDO_REGISTER
3735 && REG_BASIC_BLOCK (regno
) >= NUM_FIXED_BLOCKS
3736 && DF_REG_DEF_COUNT (regno
) == 1
3737 && reg_equiv
[regno
].init_insns
!= 0
3738 && reg_equiv
[regno
].init_insns
!= const0_rtx
3739 && ! find_reg_note (XEXP (reg_equiv
[regno
].init_insns
, 0),
3740 REG_EQUIV
, NULL_RTX
)
3741 && ! contains_replace_regs (XEXP (dest
, 0))
3742 && ! pdx_subregs
[regno
])
3744 rtx init_insn
= XEXP (reg_equiv
[regno
].init_insns
, 0);
3745 if (validate_equiv_mem (init_insn
, src
, dest
)
3746 && ! memref_used_between_p (dest
, init_insn
, insn
)
3747 /* Attaching a REG_EQUIV note will fail if INIT_INSN has
3749 && set_unique_reg_note (init_insn
, REG_EQUIV
, copy_rtx (dest
)))
3751 /* This insn makes the equivalence, not the one initializing
3753 ira_reg_equiv
[regno
].init_insns
3754 = gen_rtx_INSN_LIST (VOIDmode
, insn
, NULL_RTX
);
3755 df_notes_rescan (init_insn
);
3760 cleared_regs
= BITMAP_ALLOC (NULL
);
3761 /* Now scan all regs killed in an insn to see if any of them are
3762 registers only used that once. If so, see if we can replace the
3763 reference with the equivalent form. If we can, delete the
3764 initializing reference and this register will go away. If we
3765 can't replace the reference, and the initializing reference is
3766 within the same loop (or in an inner loop), then move the register
3767 initialization just before the use, so that they are in the same
3769 FOR_EACH_BB_REVERSE (bb
)
3771 loop_depth
= bb_loop_depth (bb
);
3772 for (insn
= BB_END (bb
);
3773 insn
!= PREV_INSN (BB_HEAD (bb
));
3774 insn
= PREV_INSN (insn
))
3778 if (! INSN_P (insn
))
3781 /* Don't substitute into a non-local goto, this confuses CFG. */
3783 && find_reg_note (insn
, REG_NON_LOCAL_GOTO
, NULL_RTX
))
3786 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
3788 if (REG_NOTE_KIND (link
) == REG_DEAD
3789 /* Make sure this insn still refers to the register. */
3790 && reg_mentioned_p (XEXP (link
, 0), PATTERN (insn
)))
3792 int regno
= REGNO (XEXP (link
, 0));
3795 if (! reg_equiv
[regno
].replace
3796 || reg_equiv
[regno
].loop_depth
< loop_depth
3797 /* There is no sense to move insns if live range
3798 shrinkage or register pressure-sensitive
3799 scheduling were done because it will not
3800 improve allocation but worsen insn schedule
3801 with a big probability. */
3802 || flag_live_range_shrinkage
3803 || (flag_sched_pressure
&& flag_schedule_insns
))
3806 /* reg_equiv[REGNO].replace gets set only when
3807 REG_N_REFS[REGNO] is 2, i.e. the register is set
3808 once and used once. (If it were only set, but
3809 not used, flow would have deleted the setting
3810 insns.) Hence there can only be one insn in
3811 reg_equiv[REGNO].init_insns. */
3812 gcc_assert (reg_equiv
[regno
].init_insns
3813 && !XEXP (reg_equiv
[regno
].init_insns
, 1));
3814 equiv_insn
= XEXP (reg_equiv
[regno
].init_insns
, 0);
3816 /* We may not move instructions that can throw, since
3817 that changes basic block boundaries and we are not
3818 prepared to adjust the CFG to match. */
3819 if (can_throw_internal (equiv_insn
))
3822 if (asm_noperands (PATTERN (equiv_insn
)) < 0
3823 && validate_replace_rtx (regno_reg_rtx
[regno
],
3824 *(reg_equiv
[regno
].src_p
), insn
))
3830 /* Find the last note. */
3831 for (last_link
= link
; XEXP (last_link
, 1);
3832 last_link
= XEXP (last_link
, 1))
3835 /* Append the REG_DEAD notes from equiv_insn. */
3836 equiv_link
= REG_NOTES (equiv_insn
);
3840 equiv_link
= XEXP (equiv_link
, 1);
3841 if (REG_NOTE_KIND (note
) == REG_DEAD
)
3843 remove_note (equiv_insn
, note
);
3844 XEXP (last_link
, 1) = note
;
3845 XEXP (note
, 1) = NULL_RTX
;
3850 remove_death (regno
, insn
);
3851 SET_REG_N_REFS (regno
, 0);
3852 REG_FREQ (regno
) = 0;
3853 delete_insn (equiv_insn
);
3855 reg_equiv
[regno
].init_insns
3856 = XEXP (reg_equiv
[regno
].init_insns
, 1);
3858 ira_reg_equiv
[regno
].init_insns
= NULL_RTX
;
3859 bitmap_set_bit (cleared_regs
, regno
);
3861 /* Move the initialization of the register to just before
3862 INSN. Update the flow information. */
3863 else if (prev_nondebug_insn (insn
) != equiv_insn
)
3867 new_insn
= emit_insn_before (PATTERN (equiv_insn
), insn
);
3868 REG_NOTES (new_insn
) = REG_NOTES (equiv_insn
);
3869 REG_NOTES (equiv_insn
) = 0;
3870 /* Rescan it to process the notes. */
3871 df_insn_rescan (new_insn
);
3873 /* Make sure this insn is recognized before
3874 reload begins, otherwise
3875 eliminate_regs_in_insn will die. */
3876 INSN_CODE (new_insn
) = INSN_CODE (equiv_insn
);
3878 delete_insn (equiv_insn
);
3880 XEXP (reg_equiv
[regno
].init_insns
, 0) = new_insn
;
3882 REG_BASIC_BLOCK (regno
) = bb
->index
;
3883 REG_N_CALLS_CROSSED (regno
) = 0;
3884 REG_FREQ_CALLS_CROSSED (regno
) = 0;
3885 REG_N_THROWING_CALLS_CROSSED (regno
) = 0;
3886 REG_LIVE_LENGTH (regno
) = 2;
3888 if (insn
== BB_HEAD (bb
))
3889 BB_HEAD (bb
) = PREV_INSN (insn
);
3891 ira_reg_equiv
[regno
].init_insns
3892 = gen_rtx_INSN_LIST (VOIDmode
, new_insn
, NULL_RTX
);
3893 bitmap_set_bit (cleared_regs
, regno
);
3900 if (!bitmap_empty_p (cleared_regs
))
3904 bitmap_and_compl_into (DF_LR_IN (bb
), cleared_regs
);
3905 bitmap_and_compl_into (DF_LR_OUT (bb
), cleared_regs
);
3908 bitmap_and_compl_into (DF_LIVE_IN (bb
), cleared_regs
);
3909 bitmap_and_compl_into (DF_LIVE_OUT (bb
), cleared_regs
);
3912 /* Last pass - adjust debug insns referencing cleared regs. */
3913 if (MAY_HAVE_DEBUG_INSNS
)
3914 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
3915 if (DEBUG_INSN_P (insn
))
3917 rtx old_loc
= INSN_VAR_LOCATION_LOC (insn
);
3918 INSN_VAR_LOCATION_LOC (insn
)
3919 = simplify_replace_fn_rtx (old_loc
, NULL_RTX
,
3920 adjust_cleared_regs
,
3921 (void *) cleared_regs
);
3922 if (old_loc
!= INSN_VAR_LOCATION_LOC (insn
))
3923 df_insn_rescan (insn
);
3927 BITMAP_FREE (cleared_regs
);
3932 end_alias_analysis ();
3935 return recorded_label_ref
;
3940 /* Set up fields memory, constant, and invariant from init_insns in
3941 the structures of array ira_reg_equiv. */
3943 setup_reg_equiv (void)
3946 rtx elem
, prev_elem
, next_elem
, insn
, set
, x
;
3948 for (i
= FIRST_PSEUDO_REGISTER
; i
< ira_reg_equiv_len
; i
++)
3949 for (prev_elem
= NULL
, elem
= ira_reg_equiv
[i
].init_insns
;
3951 prev_elem
= elem
, elem
= next_elem
)
3953 next_elem
= XEXP (elem
, 1);
3954 insn
= XEXP (elem
, 0);
3955 set
= single_set (insn
);
3957 /* Init insns can set up equivalence when the reg is a destination or
3958 a source (in this case the destination is memory). */
3959 if (set
!= 0 && (REG_P (SET_DEST (set
)) || REG_P (SET_SRC (set
))))
3961 if ((x
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
)) != NULL
)
3964 if (REG_P (SET_DEST (set
))
3965 && REGNO (SET_DEST (set
)) == (unsigned int) i
3966 && ! rtx_equal_p (SET_SRC (set
), x
) && MEM_P (x
))
3968 /* This insn reporting the equivalence but
3969 actually not setting it. Remove it from the
3971 if (prev_elem
== NULL
)
3972 ira_reg_equiv
[i
].init_insns
= next_elem
;
3974 XEXP (prev_elem
, 1) = next_elem
;
3978 else if (REG_P (SET_DEST (set
))
3979 && REGNO (SET_DEST (set
)) == (unsigned int) i
)
3983 gcc_assert (REG_P (SET_SRC (set
))
3984 && REGNO (SET_SRC (set
)) == (unsigned int) i
);
3987 if (! function_invariant_p (x
)
3989 /* A function invariant is often CONSTANT_P but may
3990 include a register. We promise to only pass
3991 CONSTANT_P objects to LEGITIMATE_PIC_OPERAND_P. */
3992 || (CONSTANT_P (x
) && LEGITIMATE_PIC_OPERAND_P (x
)))
3994 /* It can happen that a REG_EQUIV note contains a MEM
3995 that is not a legitimate memory operand. As later
3996 stages of reload assume that all addresses found in
3997 the lra_regno_equiv_* arrays were originally
3998 legitimate, we ignore such REG_EQUIV notes. */
3999 if (memory_operand (x
, VOIDmode
))
4001 ira_reg_equiv
[i
].defined_p
= true;
4002 ira_reg_equiv
[i
].memory
= x
;
4005 else if (function_invariant_p (x
))
4007 enum machine_mode mode
;
4009 mode
= GET_MODE (SET_DEST (set
));
4010 if (GET_CODE (x
) == PLUS
4011 || x
== frame_pointer_rtx
|| x
== arg_pointer_rtx
)
4012 /* This is PLUS of frame pointer and a constant,
4014 ira_reg_equiv
[i
].invariant
= x
;
4015 else if (targetm
.legitimate_constant_p (mode
, x
))
4016 ira_reg_equiv
[i
].constant
= x
;
4019 ira_reg_equiv
[i
].memory
= force_const_mem (mode
, x
);
4020 if (ira_reg_equiv
[i
].memory
== NULL_RTX
)
4022 ira_reg_equiv
[i
].defined_p
= false;
4023 ira_reg_equiv
[i
].init_insns
= NULL_RTX
;
4027 ira_reg_equiv
[i
].defined_p
= true;
4032 ira_reg_equiv
[i
].defined_p
= false;
4033 ira_reg_equiv
[i
].init_insns
= NULL_RTX
;
4040 /* Print chain C to FILE. */
4042 print_insn_chain (FILE *file
, struct insn_chain
*c
)
4044 fprintf (file
, "insn=%d, ", INSN_UID (c
->insn
));
4045 bitmap_print (file
, &c
->live_throughout
, "live_throughout: ", ", ");
4046 bitmap_print (file
, &c
->dead_or_set
, "dead_or_set: ", "\n");
4050 /* Print all reload_insn_chains to FILE. */
4052 print_insn_chains (FILE *file
)
4054 struct insn_chain
*c
;
4055 for (c
= reload_insn_chain
; c
; c
= c
->next
)
4056 print_insn_chain (file
, c
);
4059 /* Return true if pseudo REGNO should be added to set live_throughout
4060 or dead_or_set of the insn chains for reload consideration. */
4062 pseudo_for_reload_consideration_p (int regno
)
4064 /* Consider spilled pseudos too for IRA because they still have a
4065 chance to get hard-registers in the reload when IRA is used. */
4066 return (reg_renumber
[regno
] >= 0 || ira_conflicts_p
);
4069 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
4070 REG to the number of nregs, and INIT_VALUE to get the
4071 initialization. ALLOCNUM need not be the regno of REG. */
4073 init_live_subregs (bool init_value
, sbitmap
*live_subregs
,
4074 bitmap live_subregs_used
, int allocnum
, rtx reg
)
4076 unsigned int regno
= REGNO (SUBREG_REG (reg
));
4077 int size
= GET_MODE_SIZE (GET_MODE (regno_reg_rtx
[regno
]));
4079 gcc_assert (size
> 0);
4081 /* Been there, done that. */
4082 if (bitmap_bit_p (live_subregs_used
, allocnum
))
4085 /* Create a new one. */
4086 if (live_subregs
[allocnum
] == NULL
)
4087 live_subregs
[allocnum
] = sbitmap_alloc (size
);
4089 /* If the entire reg was live before blasting into subregs, we need
4090 to init all of the subregs to ones else init to 0. */
4092 bitmap_ones (live_subregs
[allocnum
]);
4094 bitmap_clear (live_subregs
[allocnum
]);
4096 bitmap_set_bit (live_subregs_used
, allocnum
);
4099 /* Walk the insns of the current function and build reload_insn_chain,
4100 and record register life information. */
4102 build_insn_chain (void)
4105 struct insn_chain
**p
= &reload_insn_chain
;
4107 struct insn_chain
*c
= NULL
;
4108 struct insn_chain
*next
= NULL
;
4109 bitmap live_relevant_regs
= BITMAP_ALLOC (NULL
);
4110 bitmap elim_regset
= BITMAP_ALLOC (NULL
);
4111 /* live_subregs is a vector used to keep accurate information about
4112 which hardregs are live in multiword pseudos. live_subregs and
4113 live_subregs_used are indexed by pseudo number. The live_subreg
4114 entry for a particular pseudo is only used if the corresponding
4115 element is non zero in live_subregs_used. The sbitmap size of
4116 live_subreg[allocno] is number of bytes that the pseudo can
4118 sbitmap
*live_subregs
= XCNEWVEC (sbitmap
, max_regno
);
4119 bitmap live_subregs_used
= BITMAP_ALLOC (NULL
);
4121 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
4122 if (TEST_HARD_REG_BIT (eliminable_regset
, i
))
4123 bitmap_set_bit (elim_regset
, i
);
4124 FOR_EACH_BB_REVERSE (bb
)
4129 CLEAR_REG_SET (live_relevant_regs
);
4130 bitmap_clear (live_subregs_used
);
4132 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb
), 0, i
, bi
)
4134 if (i
>= FIRST_PSEUDO_REGISTER
)
4136 bitmap_set_bit (live_relevant_regs
, i
);
4139 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb
),
4140 FIRST_PSEUDO_REGISTER
, i
, bi
)
4142 if (pseudo_for_reload_consideration_p (i
))
4143 bitmap_set_bit (live_relevant_regs
, i
);
4146 FOR_BB_INSNS_REVERSE (bb
, insn
)
4148 if (!NOTE_P (insn
) && !BARRIER_P (insn
))
4150 unsigned int uid
= INSN_UID (insn
);
4154 c
= new_insn_chain ();
4161 c
->block
= bb
->index
;
4163 if (NONDEBUG_INSN_P (insn
))
4164 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
4166 df_ref def
= *def_rec
;
4167 unsigned int regno
= DF_REF_REGNO (def
);
4169 /* Ignore may clobbers because these are generated
4170 from calls. However, every other kind of def is
4171 added to dead_or_set. */
4172 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
4174 if (regno
< FIRST_PSEUDO_REGISTER
)
4176 if (!fixed_regs
[regno
])
4177 bitmap_set_bit (&c
->dead_or_set
, regno
);
4179 else if (pseudo_for_reload_consideration_p (regno
))
4180 bitmap_set_bit (&c
->dead_or_set
, regno
);
4183 if ((regno
< FIRST_PSEUDO_REGISTER
4184 || reg_renumber
[regno
] >= 0
4186 && (!DF_REF_FLAGS_IS_SET (def
, DF_REF_CONDITIONAL
)))
4188 rtx reg
= DF_REF_REG (def
);
4190 /* We can model subregs, but not if they are
4191 wrapped in ZERO_EXTRACTS. */
4192 if (GET_CODE (reg
) == SUBREG
4193 && !DF_REF_FLAGS_IS_SET (def
, DF_REF_ZERO_EXTRACT
))
4195 unsigned int start
= SUBREG_BYTE (reg
);
4196 unsigned int last
= start
4197 + GET_MODE_SIZE (GET_MODE (reg
));
4200 (bitmap_bit_p (live_relevant_regs
, regno
),
4201 live_subregs
, live_subregs_used
, regno
, reg
);
4203 if (!DF_REF_FLAGS_IS_SET
4204 (def
, DF_REF_STRICT_LOW_PART
))
4206 /* Expand the range to cover entire words.
4207 Bytes added here are "don't care". */
4209 = start
/ UNITS_PER_WORD
* UNITS_PER_WORD
;
4210 last
= ((last
+ UNITS_PER_WORD
- 1)
4211 / UNITS_PER_WORD
* UNITS_PER_WORD
);
4214 /* Ignore the paradoxical bits. */
4215 if (last
> SBITMAP_SIZE (live_subregs
[regno
]))
4216 last
= SBITMAP_SIZE (live_subregs
[regno
]);
4218 while (start
< last
)
4220 bitmap_clear_bit (live_subregs
[regno
], start
);
4224 if (bitmap_empty_p (live_subregs
[regno
]))
4226 bitmap_clear_bit (live_subregs_used
, regno
);
4227 bitmap_clear_bit (live_relevant_regs
, regno
);
4230 /* Set live_relevant_regs here because
4231 that bit has to be true to get us to
4232 look at the live_subregs fields. */
4233 bitmap_set_bit (live_relevant_regs
, regno
);
4237 /* DF_REF_PARTIAL is generated for
4238 subregs, STRICT_LOW_PART, and
4239 ZERO_EXTRACT. We handle the subreg
4240 case above so here we have to keep from
4241 modeling the def as a killing def. */
4242 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
))
4244 bitmap_clear_bit (live_subregs_used
, regno
);
4245 bitmap_clear_bit (live_relevant_regs
, regno
);
4251 bitmap_and_compl_into (live_relevant_regs
, elim_regset
);
4252 bitmap_copy (&c
->live_throughout
, live_relevant_regs
);
4254 if (NONDEBUG_INSN_P (insn
))
4255 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
4257 df_ref use
= *use_rec
;
4258 unsigned int regno
= DF_REF_REGNO (use
);
4259 rtx reg
= DF_REF_REG (use
);
4261 /* DF_REF_READ_WRITE on a use means that this use
4262 is fabricated from a def that is a partial set
4263 to a multiword reg. Here, we only model the
4264 subreg case that is not wrapped in ZERO_EXTRACT
4265 precisely so we do not need to look at the
4267 if (DF_REF_FLAGS_IS_SET (use
, DF_REF_READ_WRITE
)
4268 && !DF_REF_FLAGS_IS_SET (use
, DF_REF_ZERO_EXTRACT
)
4269 && DF_REF_FLAGS_IS_SET (use
, DF_REF_SUBREG
))
4272 /* Add the last use of each var to dead_or_set. */
4273 if (!bitmap_bit_p (live_relevant_regs
, regno
))
4275 if (regno
< FIRST_PSEUDO_REGISTER
)
4277 if (!fixed_regs
[regno
])
4278 bitmap_set_bit (&c
->dead_or_set
, regno
);
4280 else if (pseudo_for_reload_consideration_p (regno
))
4281 bitmap_set_bit (&c
->dead_or_set
, regno
);
4284 if (regno
< FIRST_PSEUDO_REGISTER
4285 || pseudo_for_reload_consideration_p (regno
))
4287 if (GET_CODE (reg
) == SUBREG
4288 && !DF_REF_FLAGS_IS_SET (use
,
4290 | DF_REF_ZERO_EXTRACT
))
4292 unsigned int start
= SUBREG_BYTE (reg
);
4293 unsigned int last
= start
4294 + GET_MODE_SIZE (GET_MODE (reg
));
4297 (bitmap_bit_p (live_relevant_regs
, regno
),
4298 live_subregs
, live_subregs_used
, regno
, reg
);
4300 /* Ignore the paradoxical bits. */
4301 if (last
> SBITMAP_SIZE (live_subregs
[regno
]))
4302 last
= SBITMAP_SIZE (live_subregs
[regno
]);
4304 while (start
< last
)
4306 bitmap_set_bit (live_subregs
[regno
], start
);
4311 /* Resetting the live_subregs_used is
4312 effectively saying do not use the subregs
4313 because we are reading the whole
4315 bitmap_clear_bit (live_subregs_used
, regno
);
4316 bitmap_set_bit (live_relevant_regs
, regno
);
4322 /* FIXME!! The following code is a disaster. Reload needs to see the
4323 labels and jump tables that are just hanging out in between
4324 the basic blocks. See pr33676. */
4325 insn
= BB_HEAD (bb
);
4327 /* Skip over the barriers and cruft. */
4328 while (insn
&& (BARRIER_P (insn
) || NOTE_P (insn
)
4329 || BLOCK_FOR_INSN (insn
) == bb
))
4330 insn
= PREV_INSN (insn
);
4332 /* While we add anything except barriers and notes, the focus is
4333 to get the labels and jump tables into the
4334 reload_insn_chain. */
4337 if (!NOTE_P (insn
) && !BARRIER_P (insn
))
4339 if (BLOCK_FOR_INSN (insn
))
4342 c
= new_insn_chain ();
4348 /* The block makes no sense here, but it is what the old
4350 c
->block
= bb
->index
;
4352 bitmap_copy (&c
->live_throughout
, live_relevant_regs
);
4354 insn
= PREV_INSN (insn
);
4358 reload_insn_chain
= c
;
4361 for (i
= 0; i
< (unsigned int) max_regno
; i
++)
4362 if (live_subregs
[i
] != NULL
)
4363 sbitmap_free (live_subregs
[i
]);
4364 free (live_subregs
);
4365 BITMAP_FREE (live_subregs_used
);
4366 BITMAP_FREE (live_relevant_regs
);
4367 BITMAP_FREE (elim_regset
);
4370 print_insn_chains (dump_file
);
4373 /* Examine the rtx found in *LOC, which is read or written to as determined
4374 by TYPE. Return false if we find a reason why an insn containing this
4375 rtx should not be moved (such as accesses to non-constant memory), true
4378 rtx_moveable_p (rtx
*loc
, enum op_type type
)
4382 enum rtx_code code
= GET_CODE (x
);
4385 code
= GET_CODE (x
);
4395 return type
== OP_IN
;
4401 if (x
== frame_pointer_rtx
)
4403 if (HARD_REGISTER_P (x
))
4409 if (type
== OP_IN
&& MEM_READONLY_P (x
))
4410 return rtx_moveable_p (&XEXP (x
, 0), OP_IN
);
4414 return (rtx_moveable_p (&SET_SRC (x
), OP_IN
)
4415 && rtx_moveable_p (&SET_DEST (x
), OP_OUT
));
4417 case STRICT_LOW_PART
:
4418 return rtx_moveable_p (&XEXP (x
, 0), OP_OUT
);
4422 return (rtx_moveable_p (&XEXP (x
, 0), type
)
4423 && rtx_moveable_p (&XEXP (x
, 1), OP_IN
)
4424 && rtx_moveable_p (&XEXP (x
, 2), OP_IN
));
4427 return rtx_moveable_p (&SET_DEST (x
), OP_OUT
);
4433 fmt
= GET_RTX_FORMAT (code
);
4434 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4438 if (!rtx_moveable_p (&XEXP (x
, i
), type
))
4441 else if (fmt
[i
] == 'E')
4442 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
4444 if (!rtx_moveable_p (&XVECEXP (x
, i
, j
), type
))
4451 /* A wrapper around dominated_by_p, which uses the information in UID_LUID
4452 to give dominance relationships between two insns I1 and I2. */
4454 insn_dominated_by_p (rtx i1
, rtx i2
, int *uid_luid
)
4456 basic_block bb1
= BLOCK_FOR_INSN (i1
);
4457 basic_block bb2
= BLOCK_FOR_INSN (i2
);
4460 return uid_luid
[INSN_UID (i2
)] < uid_luid
[INSN_UID (i1
)];
4461 return dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
);
4464 /* Record the range of register numbers added by find_moveable_pseudos. */
4465 int first_moveable_pseudo
, last_moveable_pseudo
;
4467 /* These two vectors hold data for every register added by
4468 find_movable_pseudos, with index 0 holding data for the
4469 first_moveable_pseudo. */
4470 /* The original home register. */
4471 static vec
<rtx
> pseudo_replaced_reg
;
4473 /* Look for instances where we have an instruction that is known to increase
4474 register pressure, and whose result is not used immediately. If it is
4475 possible to move the instruction downwards to just before its first use,
4476 split its lifetime into two ranges. We create a new pseudo to compute the
4477 value, and emit a move instruction just before the first use. If, after
4478 register allocation, the new pseudo remains unallocated, the function
4479 move_unallocated_pseudos then deletes the move instruction and places
4480 the computation just before the first use.
4482 Such a move is safe and profitable if all the input registers remain live
4483 and unchanged between the original computation and its first use. In such
4484 a situation, the computation is known to increase register pressure, and
4485 moving it is known to at least not worsen it.
4487 We restrict moves to only those cases where a register remains unallocated,
4488 in order to avoid interfering too much with the instruction schedule. As
4489 an exception, we may move insns which only modify their input register
4490 (typically induction variables), as this increases the freedom for our
4491 intended transformation, and does not limit the second instruction
4495 find_moveable_pseudos (void)
4498 int max_regs
= max_reg_num ();
4499 int max_uid
= get_max_uid ();
4501 int *uid_luid
= XNEWVEC (int, max_uid
);
4502 rtx
*closest_uses
= XNEWVEC (rtx
, max_regs
);
4503 /* A set of registers which are live but not modified throughout a block. */
4504 bitmap_head
*bb_transp_live
= XNEWVEC (bitmap_head
, last_basic_block
);
4505 /* A set of registers which only exist in a given basic block. */
4506 bitmap_head
*bb_local
= XNEWVEC (bitmap_head
, last_basic_block
);
4507 /* A set of registers which are set once, in an instruction that can be
4508 moved freely downwards, but are otherwise transparent to a block. */
4509 bitmap_head
*bb_moveable_reg_sets
= XNEWVEC (bitmap_head
, last_basic_block
);
4510 bitmap_head live
, used
, set
, interesting
, unusable_as_input
;
4512 bitmap_initialize (&interesting
, 0);
4514 first_moveable_pseudo
= max_regs
;
4515 pseudo_replaced_reg
.release ();
4516 pseudo_replaced_reg
.safe_grow_cleared (max_regs
);
4519 calculate_dominance_info (CDI_DOMINATORS
);
4522 bitmap_initialize (&live
, 0);
4523 bitmap_initialize (&used
, 0);
4524 bitmap_initialize (&set
, 0);
4525 bitmap_initialize (&unusable_as_input
, 0);
4529 bitmap transp
= bb_transp_live
+ bb
->index
;
4530 bitmap moveable
= bb_moveable_reg_sets
+ bb
->index
;
4531 bitmap local
= bb_local
+ bb
->index
;
4533 bitmap_initialize (local
, 0);
4534 bitmap_initialize (transp
, 0);
4535 bitmap_initialize (moveable
, 0);
4536 bitmap_copy (&live
, df_get_live_out (bb
));
4537 bitmap_and_into (&live
, df_get_live_in (bb
));
4538 bitmap_copy (transp
, &live
);
4539 bitmap_clear (moveable
);
4540 bitmap_clear (&live
);
4541 bitmap_clear (&used
);
4542 bitmap_clear (&set
);
4543 FOR_BB_INSNS (bb
, insn
)
4544 if (NONDEBUG_INSN_P (insn
))
4546 df_ref
*u_rec
, *d_rec
;
4548 uid_luid
[INSN_UID (insn
)] = i
++;
4550 u_rec
= DF_INSN_USES (insn
);
4551 d_rec
= DF_INSN_DEFS (insn
);
4552 if (d_rec
[0] != NULL
&& d_rec
[1] == NULL
4553 && u_rec
[0] != NULL
&& u_rec
[1] == NULL
4554 && DF_REF_REGNO (*u_rec
) == DF_REF_REGNO (*d_rec
)
4555 && !bitmap_bit_p (&set
, DF_REF_REGNO (*u_rec
))
4556 && rtx_moveable_p (&PATTERN (insn
), OP_IN
))
4558 unsigned regno
= DF_REF_REGNO (*u_rec
);
4559 bitmap_set_bit (moveable
, regno
);
4560 bitmap_set_bit (&set
, regno
);
4561 bitmap_set_bit (&used
, regno
);
4562 bitmap_clear_bit (transp
, regno
);
4567 unsigned regno
= DF_REF_REGNO (*u_rec
);
4568 bitmap_set_bit (&used
, regno
);
4569 if (bitmap_clear_bit (moveable
, regno
))
4570 bitmap_clear_bit (transp
, regno
);
4576 unsigned regno
= DF_REF_REGNO (*d_rec
);
4577 bitmap_set_bit (&set
, regno
);
4578 bitmap_clear_bit (transp
, regno
);
4579 bitmap_clear_bit (moveable
, regno
);
4585 bitmap_clear (&live
);
4586 bitmap_clear (&used
);
4587 bitmap_clear (&set
);
4591 bitmap local
= bb_local
+ bb
->index
;
4594 FOR_BB_INSNS (bb
, insn
)
4595 if (NONDEBUG_INSN_P (insn
))
4597 rtx def_insn
, closest_use
, note
;
4598 df_ref
*def_rec
, def
, use
;
4600 bool all_dominated
, all_local
;
4601 enum machine_mode mode
;
4603 def_rec
= DF_INSN_DEFS (insn
);
4604 /* There must be exactly one def in this insn. */
4606 if (!def
|| def_rec
[1] || !single_set (insn
))
4608 /* This must be the only definition of the reg. We also limit
4609 which modes we deal with so that we can assume we can generate
4610 move instructions. */
4611 regno
= DF_REF_REGNO (def
);
4612 mode
= GET_MODE (DF_REF_REG (def
));
4613 if (DF_REG_DEF_COUNT (regno
) != 1
4614 || !DF_REF_INSN_INFO (def
)
4615 || HARD_REGISTER_NUM_P (regno
)
4616 || DF_REG_EQ_USE_COUNT (regno
) > 0
4617 || (!INTEGRAL_MODE_P (mode
) && !FLOAT_MODE_P (mode
)))
4619 def_insn
= DF_REF_INSN (def
);
4621 for (note
= REG_NOTES (def_insn
); note
; note
= XEXP (note
, 1))
4622 if (REG_NOTE_KIND (note
) == REG_EQUIV
&& MEM_P (XEXP (note
, 0)))
4628 fprintf (dump_file
, "Ignoring reg %d, has equiv memory\n",
4630 bitmap_set_bit (&unusable_as_input
, regno
);
4634 use
= DF_REG_USE_CHAIN (regno
);
4635 all_dominated
= true;
4637 closest_use
= NULL_RTX
;
4638 for (; use
; use
= DF_REF_NEXT_REG (use
))
4641 if (!DF_REF_INSN_INFO (use
))
4643 all_dominated
= false;
4647 insn
= DF_REF_INSN (use
);
4648 if (DEBUG_INSN_P (insn
))
4650 if (BLOCK_FOR_INSN (insn
) != BLOCK_FOR_INSN (def_insn
))
4652 if (!insn_dominated_by_p (insn
, def_insn
, uid_luid
))
4653 all_dominated
= false;
4654 if (closest_use
!= insn
&& closest_use
!= const0_rtx
)
4656 if (closest_use
== NULL_RTX
)
4658 else if (insn_dominated_by_p (closest_use
, insn
, uid_luid
))
4660 else if (!insn_dominated_by_p (insn
, closest_use
, uid_luid
))
4661 closest_use
= const0_rtx
;
4667 fprintf (dump_file
, "Reg %d not all uses dominated by set\n",
4672 bitmap_set_bit (local
, regno
);
4673 if (closest_use
== const0_rtx
|| closest_use
== NULL
4674 || next_nonnote_nondebug_insn (def_insn
) == closest_use
)
4677 fprintf (dump_file
, "Reg %d uninteresting%s\n", regno
,
4678 closest_use
== const0_rtx
|| closest_use
== NULL
4679 ? " (no unique first use)" : "");
4683 if (reg_referenced_p (cc0_rtx
, PATTERN (closest_use
)))
4686 fprintf (dump_file
, "Reg %d: closest user uses cc0\n",
4691 bitmap_set_bit (&interesting
, regno
);
4692 closest_uses
[regno
] = closest_use
;
4694 if (dump_file
&& (all_local
|| all_dominated
))
4696 fprintf (dump_file
, "Reg %u:", regno
);
4698 fprintf (dump_file
, " local to bb %d", bb
->index
);
4700 fprintf (dump_file
, " def dominates all uses");
4701 if (closest_use
!= const0_rtx
)
4702 fprintf (dump_file
, " has unique first use");
4703 fputs ("\n", dump_file
);
4708 EXECUTE_IF_SET_IN_BITMAP (&interesting
, 0, i
, bi
)
4710 df_ref def
= DF_REG_DEF_CHAIN (i
);
4711 rtx def_insn
= DF_REF_INSN (def
);
4712 basic_block def_block
= BLOCK_FOR_INSN (def_insn
);
4713 bitmap def_bb_local
= bb_local
+ def_block
->index
;
4714 bitmap def_bb_moveable
= bb_moveable_reg_sets
+ def_block
->index
;
4715 bitmap def_bb_transp
= bb_transp_live
+ def_block
->index
;
4716 bool local_to_bb_p
= bitmap_bit_p (def_bb_local
, i
);
4717 rtx use_insn
= closest_uses
[i
];
4718 df_ref
*def_insn_use_rec
= DF_INSN_USES (def_insn
);
4720 bool all_transp
= true;
4722 if (!REG_P (DF_REF_REG (def
)))
4728 fprintf (dump_file
, "Reg %u not local to one basic block\n",
4732 if (reg_equiv_init (i
) != NULL_RTX
)
4735 fprintf (dump_file
, "Ignoring reg %u with equiv init insn\n",
4739 if (!rtx_moveable_p (&PATTERN (def_insn
), OP_IN
))
4742 fprintf (dump_file
, "Found def insn %d for %d to be not moveable\n",
4743 INSN_UID (def_insn
), i
);
4747 fprintf (dump_file
, "Examining insn %d, def for %d\n",
4748 INSN_UID (def_insn
), i
);
4749 while (*def_insn_use_rec
!= NULL
)
4751 df_ref use
= *def_insn_use_rec
;
4752 unsigned regno
= DF_REF_REGNO (use
);
4753 if (bitmap_bit_p (&unusable_as_input
, regno
))
4757 fprintf (dump_file
, " found unusable input reg %u.\n", regno
);
4760 if (!bitmap_bit_p (def_bb_transp
, regno
))
4762 if (bitmap_bit_p (def_bb_moveable
, regno
)
4763 && !control_flow_insn_p (use_insn
)
4765 && !sets_cc0_p (use_insn
)
4769 if (modified_between_p (DF_REF_REG (use
), def_insn
, use_insn
))
4771 rtx x
= NEXT_INSN (def_insn
);
4772 while (!modified_in_p (DF_REF_REG (use
), x
))
4774 gcc_assert (x
!= use_insn
);
4778 fprintf (dump_file
, " input reg %u modified but insn %d moveable\n",
4779 regno
, INSN_UID (x
));
4780 emit_insn_after (PATTERN (x
), use_insn
);
4781 set_insn_deleted (x
);
4786 fprintf (dump_file
, " input reg %u modified between def and use\n",
4799 if (!dbg_cnt (ira_move
))
4802 fprintf (dump_file
, " all ok%s\n", all_transp
? " and transp" : "");
4806 rtx def_reg
= DF_REF_REG (def
);
4807 rtx newreg
= ira_create_new_reg (def_reg
);
4808 if (validate_change (def_insn
, DF_REF_LOC (def
), newreg
, 0))
4810 unsigned nregno
= REGNO (newreg
);
4811 emit_insn_before (gen_move_insn (def_reg
, newreg
), use_insn
);
4813 pseudo_replaced_reg
[nregno
] = def_reg
;
4820 bitmap_clear (bb_local
+ bb
->index
);
4821 bitmap_clear (bb_transp_live
+ bb
->index
);
4822 bitmap_clear (bb_moveable_reg_sets
+ bb
->index
);
4824 bitmap_clear (&interesting
);
4825 bitmap_clear (&unusable_as_input
);
4827 free (closest_uses
);
4829 free (bb_transp_live
);
4830 free (bb_moveable_reg_sets
);
4832 last_moveable_pseudo
= max_reg_num ();
4834 fix_reg_equiv_init ();
4836 regstat_free_n_sets_and_refs ();
4838 regstat_init_n_sets_and_refs ();
4839 regstat_compute_ri ();
4840 free_dominance_info (CDI_DOMINATORS
);
4843 /* Perform the second half of the transformation started in
4844 find_moveable_pseudos. We look for instances where the newly introduced
4845 pseudo remains unallocated, and remove it by moving the definition to
4846 just before its use, replacing the move instruction generated by
4847 find_moveable_pseudos. */
4849 move_unallocated_pseudos (void)
4852 for (i
= first_moveable_pseudo
; i
< last_moveable_pseudo
; i
++)
4853 if (reg_renumber
[i
] < 0)
4855 int idx
= i
- first_moveable_pseudo
;
4856 rtx other_reg
= pseudo_replaced_reg
[idx
];
4857 rtx def_insn
= DF_REF_INSN (DF_REG_DEF_CHAIN (i
));
4858 /* The use must follow all definitions of OTHER_REG, so we can
4859 insert the new definition immediately after any of them. */
4860 df_ref other_def
= DF_REG_DEF_CHAIN (REGNO (other_reg
));
4861 rtx move_insn
= DF_REF_INSN (other_def
);
4862 rtx newinsn
= emit_insn_after (PATTERN (def_insn
), move_insn
);
4867 fprintf (dump_file
, "moving def of %d (insn %d now) ",
4868 REGNO (other_reg
), INSN_UID (def_insn
));
4870 delete_insn (move_insn
);
4871 while ((other_def
= DF_REG_DEF_CHAIN (REGNO (other_reg
))))
4872 delete_insn (DF_REF_INSN (other_def
));
4873 delete_insn (def_insn
);
4875 set
= single_set (newinsn
);
4876 success
= validate_change (newinsn
, &SET_DEST (set
), other_reg
, 0);
4877 gcc_assert (success
);
4879 fprintf (dump_file
, " %d) rather than keep unallocated replacement %d\n",
4880 INSN_UID (newinsn
), i
);
4881 SET_REG_N_REFS (i
, 0);
4885 /* If the backend knows where to allocate pseudos for hard
4886 register initial values, register these allocations now. */
4888 allocate_initial_values (void)
4890 if (targetm
.allocate_initial_value
)
4895 for (i
= 0; HARD_REGISTER_NUM_P (i
); i
++)
4897 if (! initial_value_entry (i
, &hreg
, &preg
))
4900 x
= targetm
.allocate_initial_value (hreg
);
4901 regno
= REGNO (preg
);
4902 if (x
&& REG_N_SETS (regno
) <= 1)
4905 reg_equiv_memory_loc (regno
) = x
;
4911 gcc_assert (REG_P (x
));
4912 new_regno
= REGNO (x
);
4913 reg_renumber
[regno
] = new_regno
;
4914 /* Poke the regno right into regno_reg_rtx so that even
4915 fixed regs are accepted. */
4916 SET_REGNO (preg
, new_regno
);
4917 /* Update global register liveness information. */
4920 if (REGNO_REG_SET_P (df_get_live_in (bb
), regno
))
4921 SET_REGNO_REG_SET (df_get_live_in (bb
), new_regno
);
4922 if (REGNO_REG_SET_P (df_get_live_out (bb
), regno
))
4923 SET_REGNO_REG_SET (df_get_live_out (bb
), new_regno
);
4929 gcc_checking_assert (! initial_value_entry (FIRST_PSEUDO_REGISTER
,
4935 /* True when we use LRA instead of reload pass for the current
4939 /* True if we have allocno conflicts. It is false for non-optimized
4940 mode or when the conflict table is too big. */
4941 bool ira_conflicts_p
;
4943 /* Saved between IRA and reload. */
4944 static int saved_flag_ira_share_spill_slots
;
4946 /* This is the main entry of IRA. */
4951 int ira_max_point_before_emit
;
4953 bool saved_flag_caller_saves
= flag_caller_saves
;
4954 enum ira_region saved_flag_ira_region
= flag_ira_region
;
4956 ira_conflicts_p
= optimize
> 0;
4958 ira_use_lra_p
= targetm
.lra_p ();
4959 /* If there are too many pseudos and/or basic blocks (e.g. 10K
4960 pseudos and 10K blocks or 100K pseudos and 1K blocks), we will
4961 use simplified and faster algorithms in LRA. */
4963 = (ira_use_lra_p
&& max_reg_num () >= (1 << 26) / last_basic_block
);
4966 /* It permits to skip live range splitting in LRA. */
4967 flag_caller_saves
= false;
4968 /* There is no sense to do regional allocation when we use
4970 flag_ira_region
= IRA_REGION_ONE
;
4971 ira_conflicts_p
= false;
4974 #ifndef IRA_NO_OBSTACK
4975 gcc_obstack_init (&ira_obstack
);
4977 bitmap_obstack_initialize (&ira_bitmap_obstack
);
4979 if (flag_caller_saves
)
4980 init_caller_save ();
4982 if (flag_ira_verbose
< 10)
4984 internal_flag_ira_verbose
= flag_ira_verbose
;
4989 internal_flag_ira_verbose
= flag_ira_verbose
- 10;
4990 ira_dump_file
= stderr
;
4993 setup_prohibited_mode_move_regs ();
4994 decrease_live_ranges_number ();
4995 df_note_add_problem ();
4997 /* DF_LIVE can't be used in the register allocator, too many other
4998 parts of the compiler depend on using the "classic" liveness
4999 interpretation of the DF_LR problem. See PR38711.
5000 Remove the problem, so that we don't spend time updating it in
5001 any of the df_analyze() calls during IRA/LRA. */
5003 df_remove_problem (df_live
);
5004 gcc_checking_assert (df_live
== NULL
);
5006 #ifdef ENABLE_CHECKING
5007 df
->changeable_flags
|= DF_VERIFY_SCHEDULED
;
5011 df_clear_flags (DF_NO_INSN_RESCAN
);
5012 regstat_init_n_sets_and_refs ();
5013 regstat_compute_ri ();
5015 /* If we are not optimizing, then this is the only place before
5016 register allocation where dataflow is done. And that is needed
5017 to generate these warnings. */
5019 generate_setjmp_warnings ();
5021 /* Determine if the current function is a leaf before running IRA
5022 since this can impact optimizations done by the prologue and
5023 epilogue thus changing register elimination offsets. */
5024 crtl
->is_leaf
= leaf_function_p ();
5026 if (resize_reg_info () && flag_ira_loop_pressure
)
5027 ira_set_pseudo_classes (true, ira_dump_file
);
5030 rebuild_p
= update_equiv_regs ();
5032 setup_reg_equiv_init ();
5034 if (optimize
&& rebuild_p
)
5036 timevar_push (TV_JUMP
);
5037 rebuild_jump_labels (get_insns ());
5038 if (purge_all_dead_edges ())
5039 delete_unreachable_blocks ();
5040 timevar_pop (TV_JUMP
);
5043 allocated_reg_info_size
= max_reg_num ();
5045 if (delete_trivially_dead_insns (get_insns (), max_reg_num ()))
5048 /* It is not worth to do such improvement when we use a simple
5049 allocation because of -O0 usage or because the function is too
5051 if (ira_conflicts_p
)
5052 find_moveable_pseudos ();
5054 max_regno_before_ira
= max_reg_num ();
5055 ira_setup_eliminable_regset (true);
5057 ira_overall_cost
= ira_reg_cost
= ira_mem_cost
= 0;
5058 ira_load_cost
= ira_store_cost
= ira_shuffle_cost
= 0;
5059 ira_move_loops_num
= ira_additional_jumps_num
= 0;
5061 ira_assert (current_loops
== NULL
);
5062 if (flag_ira_region
== IRA_REGION_ALL
|| flag_ira_region
== IRA_REGION_MIXED
)
5063 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
| LOOPS_HAVE_RECORDED_EXITS
);
5065 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
5066 fprintf (ira_dump_file
, "Building IRA IR\n");
5067 loops_p
= ira_build ();
5069 ira_assert (ira_conflicts_p
|| !loops_p
);
5071 saved_flag_ira_share_spill_slots
= flag_ira_share_spill_slots
;
5072 if (too_high_register_pressure_p () || cfun
->calls_setjmp
)
5073 /* It is just wasting compiler's time to pack spilled pseudos into
5074 stack slots in this case -- prohibit it. We also do this if
5075 there is setjmp call because a variable not modified between
5076 setjmp and longjmp the compiler is required to preserve its
5077 value and sharing slots does not guarantee it. */
5078 flag_ira_share_spill_slots
= FALSE
;
5082 ira_max_point_before_emit
= ira_max_point
;
5084 ira_initiate_emit_data ();
5088 max_regno
= max_reg_num ();
5089 if (ira_conflicts_p
)
5093 if (! ira_use_lra_p
)
5094 ira_initiate_assign ();
5103 ira_allocno_iterator ai
;
5105 FOR_EACH_ALLOCNO (a
, ai
)
5106 ALLOCNO_REGNO (a
) = REGNO (ALLOCNO_EMIT_DATA (a
)->reg
);
5110 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
5111 fprintf (ira_dump_file
, "Flattening IR\n");
5112 ira_flattening (max_regno_before_ira
, ira_max_point_before_emit
);
5114 /* New insns were generated: add notes and recalculate live
5118 /* ??? Rebuild the loop tree, but why? Does the loop tree
5119 change if new insns were generated? Can that be handled
5120 by updating the loop tree incrementally? */
5121 loop_optimizer_finalize ();
5122 free_dominance_info (CDI_DOMINATORS
);
5123 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
5124 | LOOPS_HAVE_RECORDED_EXITS
);
5126 if (! ira_use_lra_p
)
5128 setup_allocno_assignment_flags ();
5129 ira_initiate_assign ();
5130 ira_reassign_conflict_allocnos (max_regno
);
5135 ira_finish_emit_data ();
5137 setup_reg_renumber ();
5139 calculate_allocation_cost ();
5141 #ifdef ENABLE_IRA_CHECKING
5142 if (ira_conflicts_p
)
5143 check_allocation ();
5146 if (max_regno
!= max_regno_before_ira
)
5148 regstat_free_n_sets_and_refs ();
5150 regstat_init_n_sets_and_refs ();
5151 regstat_compute_ri ();
5154 overall_cost_before
= ira_overall_cost
;
5155 if (! ira_conflicts_p
)
5159 fix_reg_equiv_init ();
5161 #ifdef ENABLE_IRA_CHECKING
5162 print_redundant_copies ();
5165 ira_spilled_reg_stack_slots_num
= 0;
5166 ira_spilled_reg_stack_slots
5167 = ((struct ira_spilled_reg_stack_slot
*)
5168 ira_allocate (max_regno
5169 * sizeof (struct ira_spilled_reg_stack_slot
)));
5170 memset (ira_spilled_reg_stack_slots
, 0,
5171 max_regno
* sizeof (struct ira_spilled_reg_stack_slot
));
5173 allocate_initial_values ();
5175 /* See comment for find_moveable_pseudos call. */
5176 if (ira_conflicts_p
)
5177 move_unallocated_pseudos ();
5179 /* Restore original values. */
5182 flag_caller_saves
= saved_flag_caller_saves
;
5183 flag_ira_region
= saved_flag_ira_region
;
5193 if (flag_ira_verbose
< 10)
5194 ira_dump_file
= dump_file
;
5196 timevar_push (TV_RELOAD
);
5199 if (current_loops
!= NULL
)
5201 loop_optimizer_finalize ();
5202 free_dominance_info (CDI_DOMINATORS
);
5205 bb
->loop_father
= NULL
;
5206 current_loops
= NULL
;
5208 if (ira_conflicts_p
)
5209 ira_free (ira_spilled_reg_stack_slots
);
5213 lra (ira_dump_file
);
5214 /* ???!!! Move it before lra () when we use ira_reg_equiv in
5216 vec_free (reg_equivs
);
5222 df_set_flags (DF_NO_INSN_RESCAN
);
5223 build_insn_chain ();
5225 need_dce
= reload (get_insns (), ira_conflicts_p
);
5229 timevar_pop (TV_RELOAD
);
5231 timevar_push (TV_IRA
);
5233 if (ira_conflicts_p
&& ! ira_use_lra_p
)
5235 ira_free (ira_spilled_reg_stack_slots
);
5236 ira_finish_assign ();
5239 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
5240 && overall_cost_before
!= ira_overall_cost
)
5241 fprintf (ira_dump_file
, "+++Overall after reload %d\n", ira_overall_cost
);
5243 flag_ira_share_spill_slots
= saved_flag_ira_share_spill_slots
;
5245 if (! ira_use_lra_p
)
5248 if (current_loops
!= NULL
)
5250 loop_optimizer_finalize ();
5251 free_dominance_info (CDI_DOMINATORS
);
5254 bb
->loop_father
= NULL
;
5255 current_loops
= NULL
;
5258 regstat_free_n_sets_and_refs ();
5262 cleanup_cfg (CLEANUP_EXPENSIVE
);
5264 finish_reg_equiv ();
5266 bitmap_obstack_release (&ira_bitmap_obstack
);
5267 #ifndef IRA_NO_OBSTACK
5268 obstack_free (&ira_obstack
, NULL
);
5271 /* The code after the reload has changed so much that at this point
5272 we might as well just rescan everything. Note that
5273 df_rescan_all_insns is not going to help here because it does not
5274 touch the artificial uses and defs. */
5275 df_finish_pass (true);
5276 df_scan_alloc (NULL
);
5281 df_live_add_problem ();
5282 df_live_set_all_dirty ();
5288 if (need_dce
&& optimize
)
5291 timevar_pop (TV_IRA
);
5294 /* Run the integrated register allocator. */
5296 rest_of_handle_ira (void)
5304 const pass_data pass_data_ira
=
5306 RTL_PASS
, /* type */
5308 OPTGROUP_NONE
, /* optinfo_flags */
5309 false, /* has_gate */
5310 true, /* has_execute */
5312 0, /* properties_required */
5313 0, /* properties_provided */
5314 0, /* properties_destroyed */
5315 0, /* todo_flags_start */
5316 TODO_do_not_ggc_collect
, /* todo_flags_finish */
5319 class pass_ira
: public rtl_opt_pass
5322 pass_ira (gcc::context
*ctxt
)
5323 : rtl_opt_pass (pass_data_ira
, ctxt
)
5326 /* opt_pass methods: */
5327 unsigned int execute () { return rest_of_handle_ira (); }
5329 }; // class pass_ira
5334 make_pass_ira (gcc::context
*ctxt
)
5336 return new pass_ira (ctxt
);
5340 rest_of_handle_reload (void)
5348 const pass_data pass_data_reload
=
5350 RTL_PASS
, /* type */
5351 "reload", /* name */
5352 OPTGROUP_NONE
, /* optinfo_flags */
5353 false, /* has_gate */
5354 true, /* has_execute */
5355 TV_RELOAD
, /* tv_id */
5356 0, /* properties_required */
5357 0, /* properties_provided */
5358 0, /* properties_destroyed */
5359 0, /* todo_flags_start */
5360 0, /* todo_flags_finish */
5363 class pass_reload
: public rtl_opt_pass
5366 pass_reload (gcc::context
*ctxt
)
5367 : rtl_opt_pass (pass_data_reload
, ctxt
)
5370 /* opt_pass methods: */
5371 unsigned int execute () { return rest_of_handle_reload (); }
5373 }; // class pass_reload
5378 make_pass_reload (gcc::context
*ctxt
)
5380 return new pass_reload (ctxt
);