1 /* Integrated Register Allocator (IRA) entry point.
2 Copyright (C) 2006-2016 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, calculates register
157 pressure for each pressure class in each region, sets up
158 conflict hard registers for each allocno and info about calls
159 the allocno lives through (file ira-lives.c).
161 * IRA removes low register pressure loops from the regions
162 mostly to speed IRA up (file ira-build.c).
164 * IRA propagates accumulated allocno info from lower region
165 allocnos to corresponding upper region allocnos (file
168 * IRA creates all caps (file ira-build.c).
170 * Having live-ranges of allocnos and their classes, IRA creates
171 conflicting allocnos for each allocno. Conflicting allocnos
172 are stored as a bit vector or array of pointers to the
173 conflicting allocnos whatever is more profitable (file
174 ira-conflicts.c). At this point IRA creates allocno copies.
176 o Coloring. Now IRA has all necessary info to start graph coloring
177 process. It is done in each region on top-down traverse of the
178 region tree (file ira-color.c). There are following subpasses:
180 * Finding profitable hard registers of corresponding allocno
181 class for each allocno. For example, only callee-saved hard
182 registers are frequently profitable for allocnos living
183 through colors. If the profitable hard register set of
184 allocno does not form a tree based on subset relation, we use
185 some approximation to form the tree. This approximation is
186 used to figure out trivial colorability of allocnos. The
187 approximation is a pretty rare case.
189 * Putting allocnos onto the coloring stack. IRA uses Briggs
190 optimistic coloring which is a major improvement over
191 Chaitin's coloring. Therefore IRA does not spill allocnos at
192 this point. There is some freedom in the order of putting
193 allocnos on the stack which can affect the final result of
194 the allocation. IRA uses some heuristics to improve the
195 order. The major one is to form *threads* from colorable
196 allocnos and push them on the stack by threads. Thread is a
197 set of non-conflicting colorable allocnos connected by
198 copies. The thread contains allocnos from the colorable
199 bucket or colorable allocnos already pushed onto the coloring
200 stack. Pushing thread allocnos one after another onto the
201 stack increases chances of removing copies when the allocnos
202 get the same hard reg.
204 We also use a modification of Chaitin-Briggs algorithm which
205 works for intersected register classes of allocnos. To
206 figure out trivial colorability of allocnos, the mentioned
207 above tree of hard register sets is used. To get an idea how
208 the algorithm works in i386 example, let us consider an
209 allocno to which any general hard register can be assigned.
210 If the allocno conflicts with eight allocnos to which only
211 EAX register can be assigned, given allocno is still
212 trivially colorable because all conflicting allocnos might be
213 assigned only to EAX and all other general hard registers are
216 To get an idea of the used trivial colorability criterion, it
217 is also useful to read article "Graph-Coloring Register
218 Allocation for Irregular Architectures" by Michael D. Smith
219 and Glen Holloway. Major difference between the article
220 approach and approach used in IRA is that Smith's approach
221 takes register classes only from machine description and IRA
222 calculate register classes from intermediate code too
223 (e.g. an explicit usage of hard registers in RTL code for
224 parameter passing can result in creation of additional
225 register classes which contain or exclude the hard
226 registers). That makes IRA approach useful for improving
227 coloring even for architectures with regular register files
228 and in fact some benchmarking shows the improvement for
229 regular class architectures is even bigger than for irregular
230 ones. Another difference is that Smith's approach chooses
231 intersection of classes of all insn operands in which a given
232 pseudo occurs. IRA can use bigger classes if it is still
233 more profitable than memory usage.
235 * Popping the allocnos from the stack and assigning them hard
236 registers. If IRA can not assign a hard register to an
237 allocno and the allocno is coalesced, IRA undoes the
238 coalescing and puts the uncoalesced allocnos onto the stack in
239 the hope that some such allocnos will get a hard register
240 separately. If IRA fails to assign hard register or memory
241 is more profitable for it, IRA spills the allocno. IRA
242 assigns the allocno the hard-register with minimal full
243 allocation cost which reflects the cost of usage of the
244 hard-register for the allocno and cost of usage of the
245 hard-register for allocnos conflicting with given allocno.
247 * Chaitin-Briggs coloring assigns as many pseudos as possible
248 to hard registers. After coloring we try to improve
249 allocation with cost point of view. We improve the
250 allocation by spilling some allocnos and assigning the freed
251 hard registers to other allocnos if it decreases the overall
254 * After allocno assigning in the region, IRA modifies the hard
255 register and memory costs for the corresponding allocnos in
256 the subregions to reflect the cost of possible loads, stores,
257 or moves on the border of the region and its subregions.
258 When default regional allocation algorithm is used
259 (-fira-algorithm=mixed), IRA just propagates the assignment
260 for allocnos if the register pressure in the region for the
261 corresponding pressure class is less than number of available
262 hard registers for given pressure class.
264 o Spill/restore code moving. When IRA performs an allocation
265 by traversing regions in top-down order, it does not know what
266 happens below in the region tree. Therefore, sometimes IRA
267 misses opportunities to perform a better allocation. A simple
268 optimization tries to improve allocation in a region having
269 subregions and containing in another region. If the
270 corresponding allocnos in the subregion are spilled, it spills
271 the region allocno if it is profitable. The optimization
272 implements a simple iterative algorithm performing profitable
273 transformations while they are still possible. It is fast in
274 practice, so there is no real need for a better time complexity
277 o Code change. After coloring, two allocnos representing the
278 same pseudo-register outside and inside a region respectively
279 may be assigned to different locations (hard-registers or
280 memory). In this case IRA creates and uses a new
281 pseudo-register inside the region and adds code to move allocno
282 values on the region's borders. This is done during top-down
283 traversal of the regions (file ira-emit.c). In some
284 complicated cases IRA can create a new allocno to move allocno
285 values (e.g. when a swap of values stored in two hard-registers
286 is needed). At this stage, the new allocno is marked as
287 spilled. IRA still creates the pseudo-register and the moves
288 on the region borders even when both allocnos were assigned to
289 the same hard-register. If the reload pass spills a
290 pseudo-register for some reason, the effect will be smaller
291 because another allocno will still be in the hard-register. In
292 most cases, this is better then spilling both allocnos. If
293 reload does not change the allocation for the two
294 pseudo-registers, the trivial move will be removed by
295 post-reload optimizations. IRA does not generate moves for
296 allocnos assigned to the same hard register when the default
297 regional allocation algorithm is used and the register pressure
298 in the region for the corresponding pressure class is less than
299 number of available hard registers for given pressure class.
300 IRA also does some optimizations to remove redundant stores and
301 to reduce code duplication on the region borders.
303 o Flattening internal representation. After changing code, IRA
304 transforms its internal representation for several regions into
305 one region representation (file ira-build.c). This process is
306 called IR flattening. Such process is more complicated than IR
307 rebuilding would be, but is much faster.
309 o After IR flattening, IRA tries to assign hard registers to all
310 spilled allocnos. This is implemented by a simple and fast
311 priority coloring algorithm (see function
312 ira_reassign_conflict_allocnos::ira-color.c). Here new allocnos
313 created during the code change pass can be assigned to hard
316 o At the end IRA calls the reload pass. The reload pass
317 communicates with IRA through several functions in file
318 ira-color.c to improve its decisions in
320 * sharing stack slots for the spilled pseudos based on IRA info
321 about pseudo-register conflicts.
323 * reassigning hard-registers to all spilled pseudos at the end
324 of each reload iteration.
326 * choosing a better hard-register to spill based on IRA info
327 about pseudo-register live ranges and the register pressure
328 in places where the pseudo-register lives.
330 IRA uses a lot of data representing the target processors. These
331 data are initialized in file ira.c.
333 If function has no loops (or the loops are ignored when
334 -fira-algorithm=CB is used), we have classic Chaitin-Briggs
335 coloring (only instead of separate pass of coalescing, we use hard
336 register preferencing). In such case, IRA works much faster
337 because many things are not made (like IR flattening, the
338 spill/restore optimization, and the code change).
340 Literature is worth to read for better understanding the code:
342 o Preston Briggs, Keith D. Cooper, Linda Torczon. Improvements to
343 Graph Coloring Register Allocation.
345 o David Callahan, Brian Koblenz. Register allocation via
346 hierarchical graph coloring.
348 o Keith Cooper, Anshuman Dasgupta, Jason Eckhardt. Revisiting Graph
349 Coloring Register Allocation: A Study of the Chaitin-Briggs and
350 Callahan-Koblenz Algorithms.
352 o Guei-Yuan Lueh, Thomas Gross, and Ali-Reza Adl-Tabatabai. Global
353 Register Allocation Based on Graph Fusion.
355 o Michael D. Smith and Glenn Holloway. Graph-Coloring Register
356 Allocation for Irregular Architectures
358 o Vladimir Makarov. The Integrated Register Allocator for GCC.
360 o Vladimir Makarov. The top-down register allocator for irregular
361 register file architectures.
368 #include "coretypes.h"
374 #include "memmodel.h"
376 #include "insn-config.h"
380 #include "diagnostic-core.h"
382 #include "cfgbuild.h"
383 #include "cfgcleanup.h"
385 #include "tree-pass.h"
392 #include "rtl-iter.h"
393 #include "shrink-wrap.h"
394 #include "print-rtl.h"
396 struct target_ira default_target_ira
;
397 struct target_ira_int default_target_ira_int
;
398 #if SWITCHABLE_TARGET
399 struct target_ira
*this_target_ira
= &default_target_ira
;
400 struct target_ira_int
*this_target_ira_int
= &default_target_ira_int
;
403 /* A modified value of flag `-fira-verbose' used internally. */
404 int internal_flag_ira_verbose
;
406 /* Dump file of the allocator if it is not NULL. */
409 /* The number of elements in the following array. */
410 int ira_spilled_reg_stack_slots_num
;
412 /* The following array contains info about spilled pseudo-registers
413 stack slots used in current function so far. */
414 struct ira_spilled_reg_stack_slot
*ira_spilled_reg_stack_slots
;
416 /* Correspondingly overall cost of the allocation, overall cost before
417 reload, cost of the allocnos assigned to hard-registers, cost of
418 the allocnos assigned to memory, cost of loads, stores and register
419 move insns generated for pseudo-register live range splitting (see
421 int64_t ira_overall_cost
, overall_cost_before
;
422 int64_t ira_reg_cost
, ira_mem_cost
;
423 int64_t ira_load_cost
, ira_store_cost
, ira_shuffle_cost
;
424 int ira_move_loops_num
, ira_additional_jumps_num
;
426 /* All registers that can be eliminated. */
428 HARD_REG_SET eliminable_regset
;
430 /* Value of max_reg_num () before IRA work start. This value helps
431 us to recognize a situation when new pseudos were created during
433 static int max_regno_before_ira
;
435 /* Temporary hard reg set used for a different calculation. */
436 static HARD_REG_SET temp_hard_regset
;
438 #define last_mode_for_init_move_cost \
439 (this_target_ira_int->x_last_mode_for_init_move_cost)
442 /* The function sets up the map IRA_REG_MODE_HARD_REGSET. */
444 setup_reg_mode_hard_regset (void)
446 int i
, m
, hard_regno
;
448 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
449 for (hard_regno
= 0; hard_regno
< FIRST_PSEUDO_REGISTER
; hard_regno
++)
451 CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset
[hard_regno
][m
]);
452 for (i
= hard_regno_nregs
[hard_regno
][m
] - 1; i
>= 0; i
--)
453 if (hard_regno
+ i
< FIRST_PSEUDO_REGISTER
)
454 SET_HARD_REG_BIT (ira_reg_mode_hard_regset
[hard_regno
][m
],
460 #define no_unit_alloc_regs \
461 (this_target_ira_int->x_no_unit_alloc_regs)
463 /* The function sets up the three arrays declared above. */
465 setup_class_hard_regs (void)
467 int cl
, i
, hard_regno
, n
;
468 HARD_REG_SET processed_hard_reg_set
;
470 ira_assert (SHRT_MAX
>= FIRST_PSEUDO_REGISTER
);
471 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
473 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
474 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
475 CLEAR_HARD_REG_SET (processed_hard_reg_set
);
476 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
478 ira_non_ordered_class_hard_regs
[cl
][i
] = -1;
479 ira_class_hard_reg_index
[cl
][i
] = -1;
481 for (n
= 0, i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
483 #ifdef REG_ALLOC_ORDER
484 hard_regno
= reg_alloc_order
[i
];
488 if (TEST_HARD_REG_BIT (processed_hard_reg_set
, hard_regno
))
490 SET_HARD_REG_BIT (processed_hard_reg_set
, hard_regno
);
491 if (! TEST_HARD_REG_BIT (temp_hard_regset
, hard_regno
))
492 ira_class_hard_reg_index
[cl
][hard_regno
] = -1;
495 ira_class_hard_reg_index
[cl
][hard_regno
] = n
;
496 ira_class_hard_regs
[cl
][n
++] = hard_regno
;
499 ira_class_hard_regs_num
[cl
] = n
;
500 for (n
= 0, i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
501 if (TEST_HARD_REG_BIT (temp_hard_regset
, i
))
502 ira_non_ordered_class_hard_regs
[cl
][n
++] = i
;
503 ira_assert (ira_class_hard_regs_num
[cl
] == n
);
507 /* Set up global variables defining info about hard registers for the
508 allocation. These depend on USE_HARD_FRAME_P whose TRUE value means
509 that we can use the hard frame pointer for the allocation. */
511 setup_alloc_regs (bool use_hard_frame_p
)
513 #ifdef ADJUST_REG_ALLOC_ORDER
514 ADJUST_REG_ALLOC_ORDER
;
516 COPY_HARD_REG_SET (no_unit_alloc_regs
, fixed_nonglobal_reg_set
);
517 if (! use_hard_frame_p
)
518 SET_HARD_REG_BIT (no_unit_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
519 setup_class_hard_regs ();
524 #define alloc_reg_class_subclasses \
525 (this_target_ira_int->x_alloc_reg_class_subclasses)
527 /* Initialize the table of subclasses of each reg class. */
529 setup_reg_subclasses (void)
532 HARD_REG_SET temp_hard_regset2
;
534 for (i
= 0; i
< N_REG_CLASSES
; i
++)
535 for (j
= 0; j
< N_REG_CLASSES
; j
++)
536 alloc_reg_class_subclasses
[i
][j
] = LIM_REG_CLASSES
;
538 for (i
= 0; i
< N_REG_CLASSES
; i
++)
540 if (i
== (int) NO_REGS
)
543 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[i
]);
544 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
545 if (hard_reg_set_empty_p (temp_hard_regset
))
547 for (j
= 0; j
< N_REG_CLASSES
; j
++)
552 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[j
]);
553 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
554 if (! hard_reg_set_subset_p (temp_hard_regset
,
557 p
= &alloc_reg_class_subclasses
[j
][0];
558 while (*p
!= LIM_REG_CLASSES
) p
++;
559 *p
= (enum reg_class
) i
;
566 /* Set up IRA_MEMORY_MOVE_COST and IRA_MAX_MEMORY_MOVE_COST. */
568 setup_class_subset_and_memory_move_costs (void)
570 int cl
, cl2
, mode
, cost
;
571 HARD_REG_SET temp_hard_regset2
;
573 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
574 ira_memory_move_cost
[mode
][NO_REGS
][0]
575 = ira_memory_move_cost
[mode
][NO_REGS
][1] = SHRT_MAX
;
576 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
578 if (cl
!= (int) NO_REGS
)
579 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
581 ira_max_memory_move_cost
[mode
][cl
][0]
582 = ira_memory_move_cost
[mode
][cl
][0]
583 = memory_move_cost ((machine_mode
) mode
,
584 (reg_class_t
) cl
, false);
585 ira_max_memory_move_cost
[mode
][cl
][1]
586 = ira_memory_move_cost
[mode
][cl
][1]
587 = memory_move_cost ((machine_mode
) mode
,
588 (reg_class_t
) cl
, true);
589 /* Costs for NO_REGS are used in cost calculation on the
590 1st pass when the preferred register classes are not
591 known yet. In this case we take the best scenario. */
592 if (ira_memory_move_cost
[mode
][NO_REGS
][0]
593 > ira_memory_move_cost
[mode
][cl
][0])
594 ira_max_memory_move_cost
[mode
][NO_REGS
][0]
595 = ira_memory_move_cost
[mode
][NO_REGS
][0]
596 = ira_memory_move_cost
[mode
][cl
][0];
597 if (ira_memory_move_cost
[mode
][NO_REGS
][1]
598 > ira_memory_move_cost
[mode
][cl
][1])
599 ira_max_memory_move_cost
[mode
][NO_REGS
][1]
600 = ira_memory_move_cost
[mode
][NO_REGS
][1]
601 = ira_memory_move_cost
[mode
][cl
][1];
604 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
605 for (cl2
= (int) N_REG_CLASSES
- 1; cl2
>= 0; cl2
--)
607 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
608 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
609 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl2
]);
610 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
611 ira_class_subset_p
[cl
][cl2
]
612 = hard_reg_set_subset_p (temp_hard_regset
, temp_hard_regset2
);
613 if (! hard_reg_set_empty_p (temp_hard_regset2
)
614 && hard_reg_set_subset_p (reg_class_contents
[cl2
],
615 reg_class_contents
[cl
]))
616 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
618 cost
= ira_memory_move_cost
[mode
][cl2
][0];
619 if (cost
> ira_max_memory_move_cost
[mode
][cl
][0])
620 ira_max_memory_move_cost
[mode
][cl
][0] = cost
;
621 cost
= ira_memory_move_cost
[mode
][cl2
][1];
622 if (cost
> ira_max_memory_move_cost
[mode
][cl
][1])
623 ira_max_memory_move_cost
[mode
][cl
][1] = cost
;
626 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
627 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
629 ira_memory_move_cost
[mode
][cl
][0]
630 = ira_max_memory_move_cost
[mode
][cl
][0];
631 ira_memory_move_cost
[mode
][cl
][1]
632 = ira_max_memory_move_cost
[mode
][cl
][1];
634 setup_reg_subclasses ();
639 /* Define the following macro if allocation through malloc if
641 #define IRA_NO_OBSTACK
643 #ifndef IRA_NO_OBSTACK
644 /* Obstack used for storing all dynamic data (except bitmaps) of the
646 static struct obstack ira_obstack
;
649 /* Obstack used for storing all bitmaps of the IRA. */
650 static struct bitmap_obstack ira_bitmap_obstack
;
652 /* Allocate memory of size LEN for IRA data. */
654 ira_allocate (size_t len
)
658 #ifndef IRA_NO_OBSTACK
659 res
= obstack_alloc (&ira_obstack
, len
);
666 /* Free memory ADDR allocated for IRA data. */
668 ira_free (void *addr ATTRIBUTE_UNUSED
)
670 #ifndef IRA_NO_OBSTACK
678 /* Allocate and returns bitmap for IRA. */
680 ira_allocate_bitmap (void)
682 return BITMAP_ALLOC (&ira_bitmap_obstack
);
685 /* Free bitmap B allocated for IRA. */
687 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED
)
694 /* Output information about allocation of all allocnos (except for
695 caps) into file F. */
697 ira_print_disposition (FILE *f
)
703 fprintf (f
, "Disposition:");
704 max_regno
= max_reg_num ();
705 for (n
= 0, i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
706 for (a
= ira_regno_allocno_map
[i
];
708 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
713 fprintf (f
, " %4d:r%-4d", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
714 if ((bb
= ALLOCNO_LOOP_TREE_NODE (a
)->bb
) != NULL
)
715 fprintf (f
, "b%-3d", bb
->index
);
717 fprintf (f
, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a
)->loop_num
);
718 if (ALLOCNO_HARD_REGNO (a
) >= 0)
719 fprintf (f
, " %3d", ALLOCNO_HARD_REGNO (a
));
726 /* Outputs information about allocation of all allocnos into
729 ira_debug_disposition (void)
731 ira_print_disposition (stderr
);
736 /* Set up ira_stack_reg_pressure_class which is the biggest pressure
737 register class containing stack registers or NO_REGS if there are
738 no stack registers. To find this class, we iterate through all
739 register pressure classes and choose the first register pressure
740 class containing all the stack registers and having the biggest
743 setup_stack_reg_pressure_class (void)
745 ira_stack_reg_pressure_class
= NO_REGS
;
750 HARD_REG_SET temp_hard_regset2
;
752 CLEAR_HARD_REG_SET (temp_hard_regset
);
753 for (i
= FIRST_STACK_REG
; i
<= LAST_STACK_REG
; i
++)
754 SET_HARD_REG_BIT (temp_hard_regset
, i
);
756 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
758 cl
= ira_pressure_classes
[i
];
759 COPY_HARD_REG_SET (temp_hard_regset2
, temp_hard_regset
);
760 AND_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl
]);
761 size
= hard_reg_set_size (temp_hard_regset2
);
765 ira_stack_reg_pressure_class
= cl
;
772 /* Find pressure classes which are register classes for which we
773 calculate register pressure in IRA, register pressure sensitive
774 insn scheduling, and register pressure sensitive loop invariant
777 To make register pressure calculation easy, we always use
778 non-intersected register pressure classes. A move of hard
779 registers from one register pressure class is not more expensive
780 than load and store of the hard registers. Most likely an allocno
781 class will be a subset of a register pressure class and in many
782 cases a register pressure class. That makes usage of register
783 pressure classes a good approximation to find a high register
786 setup_pressure_classes (void)
788 int cost
, i
, n
, curr
;
790 enum reg_class pressure_classes
[N_REG_CLASSES
];
792 HARD_REG_SET temp_hard_regset2
;
795 if (targetm
.compute_pressure_classes
)
796 n
= targetm
.compute_pressure_classes (pressure_classes
);
800 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
802 if (ira_class_hard_regs_num
[cl
] == 0)
804 if (ira_class_hard_regs_num
[cl
] != 1
805 /* A register class without subclasses may contain a few
806 hard registers and movement between them is costly
807 (e.g. SPARC FPCC registers). We still should consider it
808 as a candidate for a pressure class. */
809 && alloc_reg_class_subclasses
[cl
][0] < cl
)
811 /* Check that the moves between any hard registers of the
812 current class are not more expensive for a legal mode
813 than load/store of the hard registers of the current
814 class. Such class is a potential candidate to be a
815 register pressure class. */
816 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
818 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
819 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
820 AND_COMPL_HARD_REG_SET (temp_hard_regset
,
821 ira_prohibited_class_mode_regs
[cl
][m
]);
822 if (hard_reg_set_empty_p (temp_hard_regset
))
824 ira_init_register_move_cost_if_necessary ((machine_mode
) m
);
825 cost
= ira_register_move_cost
[m
][cl
][cl
];
826 if (cost
<= ira_max_memory_move_cost
[m
][cl
][1]
827 || cost
<= ira_max_memory_move_cost
[m
][cl
][0])
830 if (m
>= NUM_MACHINE_MODES
)
835 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
836 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
837 /* Remove so far added pressure classes which are subset of the
838 current candidate class. Prefer GENERAL_REGS as a pressure
839 register class to another class containing the same
840 allocatable hard registers. We do this because machine
841 dependent cost hooks might give wrong costs for the latter
842 class but always give the right cost for the former class
844 for (i
= 0; i
< n
; i
++)
846 cl2
= pressure_classes
[i
];
847 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl2
]);
848 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
849 if (hard_reg_set_subset_p (temp_hard_regset
, temp_hard_regset2
)
850 && (! hard_reg_set_equal_p (temp_hard_regset
,
852 || cl2
== (int) GENERAL_REGS
))
854 pressure_classes
[curr
++] = (enum reg_class
) cl2
;
858 if (hard_reg_set_subset_p (temp_hard_regset2
, temp_hard_regset
)
859 && (! hard_reg_set_equal_p (temp_hard_regset2
,
861 || cl
== (int) GENERAL_REGS
))
863 if (hard_reg_set_equal_p (temp_hard_regset2
, temp_hard_regset
))
865 pressure_classes
[curr
++] = (enum reg_class
) cl2
;
867 /* If the current candidate is a subset of a so far added
868 pressure class, don't add it to the list of the pressure
871 pressure_classes
[curr
++] = (enum reg_class
) cl
;
875 #ifdef ENABLE_IRA_CHECKING
877 HARD_REG_SET ignore_hard_regs
;
879 /* Check pressure classes correctness: here we check that hard
880 registers from all register pressure classes contains all hard
881 registers available for the allocation. */
882 CLEAR_HARD_REG_SET (temp_hard_regset
);
883 CLEAR_HARD_REG_SET (temp_hard_regset2
);
884 COPY_HARD_REG_SET (ignore_hard_regs
, no_unit_alloc_regs
);
885 for (cl
= 0; cl
< LIM_REG_CLASSES
; cl
++)
887 /* For some targets (like MIPS with MD_REGS), there are some
888 classes with hard registers available for allocation but
889 not able to hold value of any mode. */
890 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
891 if (contains_reg_of_mode
[cl
][m
])
893 if (m
>= NUM_MACHINE_MODES
)
895 IOR_HARD_REG_SET (ignore_hard_regs
, reg_class_contents
[cl
]);
898 for (i
= 0; i
< n
; i
++)
899 if ((int) pressure_classes
[i
] == cl
)
901 IOR_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl
]);
903 IOR_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
905 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
906 /* Some targets (like SPARC with ICC reg) have allocatable regs
907 for which no reg class is defined. */
908 if (REGNO_REG_CLASS (i
) == NO_REGS
)
909 SET_HARD_REG_BIT (ignore_hard_regs
, i
);
910 AND_COMPL_HARD_REG_SET (temp_hard_regset
, ignore_hard_regs
);
911 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, ignore_hard_regs
);
912 ira_assert (hard_reg_set_subset_p (temp_hard_regset2
, temp_hard_regset
));
915 ira_pressure_classes_num
= 0;
916 for (i
= 0; i
< n
; i
++)
918 cl
= (int) pressure_classes
[i
];
919 ira_reg_pressure_class_p
[cl
] = true;
920 ira_pressure_classes
[ira_pressure_classes_num
++] = (enum reg_class
) cl
;
922 setup_stack_reg_pressure_class ();
925 /* Set up IRA_UNIFORM_CLASS_P. Uniform class is a register class
926 whose register move cost between any registers of the class is the
927 same as for all its subclasses. We use the data to speed up the
928 2nd pass of calculations of allocno costs. */
930 setup_uniform_class_p (void)
934 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
936 ira_uniform_class_p
[cl
] = false;
937 if (ira_class_hard_regs_num
[cl
] == 0)
939 /* We can not use alloc_reg_class_subclasses here because move
940 cost hooks does not take into account that some registers are
941 unavailable for the subtarget. E.g. for i686, INT_SSE_REGS
942 is element of alloc_reg_class_subclasses for GENERAL_REGS
943 because SSE regs are unavailable. */
944 for (i
= 0; (cl2
= reg_class_subclasses
[cl
][i
]) != LIM_REG_CLASSES
; i
++)
946 if (ira_class_hard_regs_num
[cl2
] == 0)
948 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
949 if (contains_reg_of_mode
[cl
][m
] && contains_reg_of_mode
[cl2
][m
])
951 ira_init_register_move_cost_if_necessary ((machine_mode
) m
);
952 if (ira_register_move_cost
[m
][cl
][cl
]
953 != ira_register_move_cost
[m
][cl2
][cl2
])
956 if (m
< NUM_MACHINE_MODES
)
959 if (cl2
== LIM_REG_CLASSES
)
960 ira_uniform_class_p
[cl
] = true;
964 /* Set up IRA_ALLOCNO_CLASSES, IRA_ALLOCNO_CLASSES_NUM,
965 IRA_IMPORTANT_CLASSES, and IRA_IMPORTANT_CLASSES_NUM.
967 Target may have many subtargets and not all target hard registers can
968 be used for allocation, e.g. x86 port in 32-bit mode can not use
969 hard registers introduced in x86-64 like r8-r15). Some classes
970 might have the same allocatable hard registers, e.g. INDEX_REGS
971 and GENERAL_REGS in x86 port in 32-bit mode. To decrease different
972 calculations efforts we introduce allocno classes which contain
973 unique non-empty sets of allocatable hard-registers.
975 Pseudo class cost calculation in ira-costs.c is very expensive.
976 Therefore we are trying to decrease number of classes involved in
977 such calculation. Register classes used in the cost calculation
978 are called important classes. They are allocno classes and other
979 non-empty classes whose allocatable hard register sets are inside
980 of an allocno class hard register set. From the first sight, it
981 looks like that they are just allocno classes. It is not true. In
982 example of x86-port in 32-bit mode, allocno classes will contain
983 GENERAL_REGS but not LEGACY_REGS (because allocatable hard
984 registers are the same for the both classes). The important
985 classes will contain GENERAL_REGS and LEGACY_REGS. It is done
986 because a machine description insn constraint may refers for
987 LEGACY_REGS and code in ira-costs.c is mostly base on investigation
988 of the insn constraints. */
990 setup_allocno_and_important_classes (void)
994 HARD_REG_SET temp_hard_regset2
;
995 static enum reg_class classes
[LIM_REG_CLASSES
+ 1];
998 /* Collect classes which contain unique sets of allocatable hard
999 registers. Prefer GENERAL_REGS to other classes containing the
1000 same set of hard registers. */
1001 for (i
= 0; i
< LIM_REG_CLASSES
; i
++)
1003 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[i
]);
1004 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1005 for (j
= 0; j
< n
; j
++)
1008 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl
]);
1009 AND_COMPL_HARD_REG_SET (temp_hard_regset2
,
1010 no_unit_alloc_regs
);
1011 if (hard_reg_set_equal_p (temp_hard_regset
,
1015 if (j
>= n
|| targetm
.additional_allocno_class_p (i
))
1016 classes
[n
++] = (enum reg_class
) i
;
1017 else if (i
== GENERAL_REGS
)
1018 /* Prefer general regs. For i386 example, it means that
1019 we prefer GENERAL_REGS over INDEX_REGS or LEGACY_REGS
1020 (all of them consists of the same available hard
1022 classes
[j
] = (enum reg_class
) i
;
1024 classes
[n
] = LIM_REG_CLASSES
;
1026 /* Set up classes which can be used for allocnos as classes
1027 containing non-empty unique sets of allocatable hard
1029 ira_allocno_classes_num
= 0;
1030 for (i
= 0; (cl
= classes
[i
]) != LIM_REG_CLASSES
; i
++)
1031 if (ira_class_hard_regs_num
[cl
] > 0)
1032 ira_allocno_classes
[ira_allocno_classes_num
++] = (enum reg_class
) cl
;
1033 ira_important_classes_num
= 0;
1034 /* Add non-allocno classes containing to non-empty set of
1035 allocatable hard regs. */
1036 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1037 if (ira_class_hard_regs_num
[cl
] > 0)
1039 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
1040 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1042 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1044 COPY_HARD_REG_SET (temp_hard_regset2
,
1045 reg_class_contents
[ira_allocno_classes
[j
]]);
1046 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
1047 if ((enum reg_class
) cl
== ira_allocno_classes
[j
])
1049 else if (hard_reg_set_subset_p (temp_hard_regset
,
1053 if (set_p
&& j
>= ira_allocno_classes_num
)
1054 ira_important_classes
[ira_important_classes_num
++]
1055 = (enum reg_class
) cl
;
1057 /* Now add allocno classes to the important classes. */
1058 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1059 ira_important_classes
[ira_important_classes_num
++]
1060 = ira_allocno_classes
[j
];
1061 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1063 ira_reg_allocno_class_p
[cl
] = false;
1064 ira_reg_pressure_class_p
[cl
] = false;
1066 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1067 ira_reg_allocno_class_p
[ira_allocno_classes
[j
]] = true;
1068 setup_pressure_classes ();
1069 setup_uniform_class_p ();
1072 /* Setup translation in CLASS_TRANSLATE of all classes into a class
1073 given by array CLASSES of length CLASSES_NUM. The function is used
1074 make translation any reg class to an allocno class or to an
1075 pressure class. This translation is necessary for some
1076 calculations when we can use only allocno or pressure classes and
1077 such translation represents an approximate representation of all
1080 The translation in case when allocatable hard register set of a
1081 given class is subset of allocatable hard register set of a class
1082 in CLASSES is pretty simple. We use smallest classes from CLASSES
1083 containing a given class. If allocatable hard register set of a
1084 given class is not a subset of any corresponding set of a class
1085 from CLASSES, we use the cheapest (with load/store point of view)
1086 class from CLASSES whose set intersects with given class set. */
1088 setup_class_translate_array (enum reg_class
*class_translate
,
1089 int classes_num
, enum reg_class
*classes
)
1092 enum reg_class aclass
, best_class
, *cl_ptr
;
1093 int i
, cost
, min_cost
, best_cost
;
1095 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1096 class_translate
[cl
] = NO_REGS
;
1098 for (i
= 0; i
< classes_num
; i
++)
1100 aclass
= classes
[i
];
1101 for (cl_ptr
= &alloc_reg_class_subclasses
[aclass
][0];
1102 (cl
= *cl_ptr
) != LIM_REG_CLASSES
;
1104 if (class_translate
[cl
] == NO_REGS
)
1105 class_translate
[cl
] = aclass
;
1106 class_translate
[aclass
] = aclass
;
1108 /* For classes which are not fully covered by one of given classes
1109 (in other words covered by more one given class), use the
1111 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1113 if (cl
== NO_REGS
|| class_translate
[cl
] != NO_REGS
)
1115 best_class
= NO_REGS
;
1116 best_cost
= INT_MAX
;
1117 for (i
= 0; i
< classes_num
; i
++)
1119 aclass
= classes
[i
];
1120 COPY_HARD_REG_SET (temp_hard_regset
,
1121 reg_class_contents
[aclass
]);
1122 AND_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
1123 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1124 if (! hard_reg_set_empty_p (temp_hard_regset
))
1127 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
1129 cost
= (ira_memory_move_cost
[mode
][aclass
][0]
1130 + ira_memory_move_cost
[mode
][aclass
][1]);
1131 if (min_cost
> cost
)
1134 if (best_class
== NO_REGS
|| best_cost
> min_cost
)
1136 best_class
= aclass
;
1137 best_cost
= min_cost
;
1141 class_translate
[cl
] = best_class
;
1145 /* Set up array IRA_ALLOCNO_CLASS_TRANSLATE and
1146 IRA_PRESSURE_CLASS_TRANSLATE. */
1148 setup_class_translate (void)
1150 setup_class_translate_array (ira_allocno_class_translate
,
1151 ira_allocno_classes_num
, ira_allocno_classes
);
1152 setup_class_translate_array (ira_pressure_class_translate
,
1153 ira_pressure_classes_num
, ira_pressure_classes
);
1156 /* Order numbers of allocno classes in original target allocno class
1157 array, -1 for non-allocno classes. */
1158 static int allocno_class_order
[N_REG_CLASSES
];
1160 /* The function used to sort the important classes. */
1162 comp_reg_classes_func (const void *v1p
, const void *v2p
)
1164 enum reg_class cl1
= *(const enum reg_class
*) v1p
;
1165 enum reg_class cl2
= *(const enum reg_class
*) v2p
;
1166 enum reg_class tcl1
, tcl2
;
1169 tcl1
= ira_allocno_class_translate
[cl1
];
1170 tcl2
= ira_allocno_class_translate
[cl2
];
1171 if (tcl1
!= NO_REGS
&& tcl2
!= NO_REGS
1172 && (diff
= allocno_class_order
[tcl1
] - allocno_class_order
[tcl2
]) != 0)
1174 return (int) cl1
- (int) cl2
;
1177 /* For correct work of function setup_reg_class_relation we need to
1178 reorder important classes according to the order of their allocno
1179 classes. It places important classes containing the same
1180 allocatable hard register set adjacent to each other and allocno
1181 class with the allocatable hard register set right after the other
1182 important classes with the same set.
1184 In example from comments of function
1185 setup_allocno_and_important_classes, it places LEGACY_REGS and
1186 GENERAL_REGS close to each other and GENERAL_REGS is after
1189 reorder_important_classes (void)
1193 for (i
= 0; i
< N_REG_CLASSES
; i
++)
1194 allocno_class_order
[i
] = -1;
1195 for (i
= 0; i
< ira_allocno_classes_num
; i
++)
1196 allocno_class_order
[ira_allocno_classes
[i
]] = i
;
1197 qsort (ira_important_classes
, ira_important_classes_num
,
1198 sizeof (enum reg_class
), comp_reg_classes_func
);
1199 for (i
= 0; i
< ira_important_classes_num
; i
++)
1200 ira_important_class_nums
[ira_important_classes
[i
]] = i
;
1203 /* Set up IRA_REG_CLASS_SUBUNION, IRA_REG_CLASS_SUPERUNION,
1204 IRA_REG_CLASS_SUPER_CLASSES, IRA_REG_CLASSES_INTERSECT, and
1205 IRA_REG_CLASSES_INTERSECT_P. For the meaning of the relations,
1206 please see corresponding comments in ira-int.h. */
1208 setup_reg_class_relations (void)
1210 int i
, cl1
, cl2
, cl3
;
1211 HARD_REG_SET intersection_set
, union_set
, temp_set2
;
1212 bool important_class_p
[N_REG_CLASSES
];
1214 memset (important_class_p
, 0, sizeof (important_class_p
));
1215 for (i
= 0; i
< ira_important_classes_num
; i
++)
1216 important_class_p
[ira_important_classes
[i
]] = true;
1217 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1219 ira_reg_class_super_classes
[cl1
][0] = LIM_REG_CLASSES
;
1220 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1222 ira_reg_classes_intersect_p
[cl1
][cl2
] = false;
1223 ira_reg_class_intersect
[cl1
][cl2
] = NO_REGS
;
1224 ira_reg_class_subset
[cl1
][cl2
] = NO_REGS
;
1225 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl1
]);
1226 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1227 COPY_HARD_REG_SET (temp_set2
, reg_class_contents
[cl2
]);
1228 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1229 if (hard_reg_set_empty_p (temp_hard_regset
)
1230 && hard_reg_set_empty_p (temp_set2
))
1232 /* The both classes have no allocatable hard registers
1233 -- take all class hard registers into account and use
1234 reg_class_subunion and reg_class_superunion. */
1237 cl3
= reg_class_subclasses
[cl1
][i
];
1238 if (cl3
== LIM_REG_CLASSES
)
1240 if (reg_class_subset_p (ira_reg_class_intersect
[cl1
][cl2
],
1241 (enum reg_class
) cl3
))
1242 ira_reg_class_intersect
[cl1
][cl2
] = (enum reg_class
) cl3
;
1244 ira_reg_class_subunion
[cl1
][cl2
] = reg_class_subunion
[cl1
][cl2
];
1245 ira_reg_class_superunion
[cl1
][cl2
] = reg_class_superunion
[cl1
][cl2
];
1248 ira_reg_classes_intersect_p
[cl1
][cl2
]
1249 = hard_reg_set_intersect_p (temp_hard_regset
, temp_set2
);
1250 if (important_class_p
[cl1
] && important_class_p
[cl2
]
1251 && hard_reg_set_subset_p (temp_hard_regset
, temp_set2
))
1253 /* CL1 and CL2 are important classes and CL1 allocatable
1254 hard register set is inside of CL2 allocatable hard
1255 registers -- make CL1 a superset of CL2. */
1258 p
= &ira_reg_class_super_classes
[cl1
][0];
1259 while (*p
!= LIM_REG_CLASSES
)
1261 *p
++ = (enum reg_class
) cl2
;
1262 *p
= LIM_REG_CLASSES
;
1264 ira_reg_class_subunion
[cl1
][cl2
] = NO_REGS
;
1265 ira_reg_class_superunion
[cl1
][cl2
] = NO_REGS
;
1266 COPY_HARD_REG_SET (intersection_set
, reg_class_contents
[cl1
]);
1267 AND_HARD_REG_SET (intersection_set
, reg_class_contents
[cl2
]);
1268 AND_COMPL_HARD_REG_SET (intersection_set
, no_unit_alloc_regs
);
1269 COPY_HARD_REG_SET (union_set
, reg_class_contents
[cl1
]);
1270 IOR_HARD_REG_SET (union_set
, reg_class_contents
[cl2
]);
1271 AND_COMPL_HARD_REG_SET (union_set
, no_unit_alloc_regs
);
1272 for (cl3
= 0; cl3
< N_REG_CLASSES
; cl3
++)
1274 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl3
]);
1275 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1276 if (hard_reg_set_subset_p (temp_hard_regset
, intersection_set
))
1278 /* CL3 allocatable hard register set is inside of
1279 intersection of allocatable hard register sets
1281 if (important_class_p
[cl3
])
1286 [(int) ira_reg_class_intersect
[cl1
][cl2
]]);
1287 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1288 if (! hard_reg_set_subset_p (temp_hard_regset
, temp_set2
)
1289 /* If the allocatable hard register sets are
1290 the same, prefer GENERAL_REGS or the
1291 smallest class for debugging
1293 || (hard_reg_set_equal_p (temp_hard_regset
, temp_set2
)
1294 && (cl3
== GENERAL_REGS
1295 || ((ira_reg_class_intersect
[cl1
][cl2
]
1297 && hard_reg_set_subset_p
1298 (reg_class_contents
[cl3
],
1301 ira_reg_class_intersect
[cl1
][cl2
]])))))
1302 ira_reg_class_intersect
[cl1
][cl2
] = (enum reg_class
) cl3
;
1306 reg_class_contents
[(int) ira_reg_class_subset
[cl1
][cl2
]]);
1307 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1308 if (! hard_reg_set_subset_p (temp_hard_regset
, temp_set2
)
1309 /* Ignore unavailable hard registers and prefer
1310 smallest class for debugging purposes. */
1311 || (hard_reg_set_equal_p (temp_hard_regset
, temp_set2
)
1312 && hard_reg_set_subset_p
1313 (reg_class_contents
[cl3
],
1315 [(int) ira_reg_class_subset
[cl1
][cl2
]])))
1316 ira_reg_class_subset
[cl1
][cl2
] = (enum reg_class
) cl3
;
1318 if (important_class_p
[cl3
]
1319 && hard_reg_set_subset_p (temp_hard_regset
, union_set
))
1321 /* CL3 allocatable hard register set is inside of
1322 union of allocatable hard register sets of CL1
1326 reg_class_contents
[(int) ira_reg_class_subunion
[cl1
][cl2
]]);
1327 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1328 if (ira_reg_class_subunion
[cl1
][cl2
] == NO_REGS
1329 || (hard_reg_set_subset_p (temp_set2
, temp_hard_regset
)
1331 && (! hard_reg_set_equal_p (temp_set2
,
1333 || cl3
== GENERAL_REGS
1334 /* If the allocatable hard register sets are the
1335 same, prefer GENERAL_REGS or the smallest
1336 class for debugging purposes. */
1337 || (ira_reg_class_subunion
[cl1
][cl2
] != GENERAL_REGS
1338 && hard_reg_set_subset_p
1339 (reg_class_contents
[cl3
],
1341 [(int) ira_reg_class_subunion
[cl1
][cl2
]])))))
1342 ira_reg_class_subunion
[cl1
][cl2
] = (enum reg_class
) cl3
;
1344 if (hard_reg_set_subset_p (union_set
, temp_hard_regset
))
1346 /* CL3 allocatable hard register set contains union
1347 of allocatable hard register sets of CL1 and
1351 reg_class_contents
[(int) ira_reg_class_superunion
[cl1
][cl2
]]);
1352 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1353 if (ira_reg_class_superunion
[cl1
][cl2
] == NO_REGS
1354 || (hard_reg_set_subset_p (temp_hard_regset
, temp_set2
)
1356 && (! hard_reg_set_equal_p (temp_set2
,
1358 || cl3
== GENERAL_REGS
1359 /* If the allocatable hard register sets are the
1360 same, prefer GENERAL_REGS or the smallest
1361 class for debugging purposes. */
1362 || (ira_reg_class_superunion
[cl1
][cl2
] != GENERAL_REGS
1363 && hard_reg_set_subset_p
1364 (reg_class_contents
[cl3
],
1366 [(int) ira_reg_class_superunion
[cl1
][cl2
]])))))
1367 ira_reg_class_superunion
[cl1
][cl2
] = (enum reg_class
) cl3
;
1374 /* Output all uniform and important classes into file F. */
1376 print_uniform_and_important_classes (FILE *f
)
1380 fprintf (f
, "Uniform classes:\n");
1381 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1382 if (ira_uniform_class_p
[cl
])
1383 fprintf (f
, " %s", reg_class_names
[cl
]);
1384 fprintf (f
, "\nImportant classes:\n");
1385 for (i
= 0; i
< ira_important_classes_num
; i
++)
1386 fprintf (f
, " %s", reg_class_names
[ira_important_classes
[i
]]);
1390 /* Output all possible allocno or pressure classes and their
1391 translation map into file F. */
1393 print_translated_classes (FILE *f
, bool pressure_p
)
1395 int classes_num
= (pressure_p
1396 ? ira_pressure_classes_num
: ira_allocno_classes_num
);
1397 enum reg_class
*classes
= (pressure_p
1398 ? ira_pressure_classes
: ira_allocno_classes
);
1399 enum reg_class
*class_translate
= (pressure_p
1400 ? ira_pressure_class_translate
1401 : ira_allocno_class_translate
);
1404 fprintf (f
, "%s classes:\n", pressure_p
? "Pressure" : "Allocno");
1405 for (i
= 0; i
< classes_num
; i
++)
1406 fprintf (f
, " %s", reg_class_names
[classes
[i
]]);
1407 fprintf (f
, "\nClass translation:\n");
1408 for (i
= 0; i
< N_REG_CLASSES
; i
++)
1409 fprintf (f
, " %s -> %s\n", reg_class_names
[i
],
1410 reg_class_names
[class_translate
[i
]]);
1413 /* Output all possible allocno and translation classes and the
1414 translation maps into stderr. */
1416 ira_debug_allocno_classes (void)
1418 print_uniform_and_important_classes (stderr
);
1419 print_translated_classes (stderr
, false);
1420 print_translated_classes (stderr
, true);
1423 /* Set up different arrays concerning class subsets, allocno and
1424 important classes. */
1426 find_reg_classes (void)
1428 setup_allocno_and_important_classes ();
1429 setup_class_translate ();
1430 reorder_important_classes ();
1431 setup_reg_class_relations ();
1436 /* Set up the array above. */
1438 setup_hard_regno_aclass (void)
1442 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1445 ira_hard_regno_allocno_class
[i
]
1446 = (TEST_HARD_REG_BIT (no_unit_alloc_regs
, i
)
1448 : ira_allocno_class_translate
[REGNO_REG_CLASS (i
)]);
1452 ira_hard_regno_allocno_class
[i
] = NO_REGS
;
1453 for (j
= 0; j
< ira_allocno_classes_num
; j
++)
1455 cl
= ira_allocno_classes
[j
];
1456 if (ira_class_hard_reg_index
[cl
][i
] >= 0)
1458 ira_hard_regno_allocno_class
[i
] = cl
;
1468 /* Form IRA_REG_CLASS_MAX_NREGS and IRA_REG_CLASS_MIN_NREGS maps. */
1470 setup_reg_class_nregs (void)
1474 for (m
= 0; m
< MAX_MACHINE_MODE
; m
++)
1476 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1477 ira_reg_class_max_nregs
[cl
][m
]
1478 = ira_reg_class_min_nregs
[cl
][m
]
1479 = targetm
.class_max_nregs ((reg_class_t
) cl
, (machine_mode
) m
);
1480 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1482 (cl2
= alloc_reg_class_subclasses
[cl
][i
]) != LIM_REG_CLASSES
;
1484 if (ira_reg_class_min_nregs
[cl2
][m
]
1485 < ira_reg_class_min_nregs
[cl
][m
])
1486 ira_reg_class_min_nregs
[cl
][m
] = ira_reg_class_min_nregs
[cl2
][m
];
1492 /* Set up IRA_PROHIBITED_CLASS_MODE_REGS and IRA_CLASS_SINGLETON.
1493 This function is called once IRA_CLASS_HARD_REGS has been initialized. */
1495 setup_prohibited_class_mode_regs (void)
1497 int j
, k
, hard_regno
, cl
, last_hard_regno
, count
;
1499 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
1501 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
1502 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1503 for (j
= 0; j
< NUM_MACHINE_MODES
; j
++)
1506 last_hard_regno
= -1;
1507 CLEAR_HARD_REG_SET (ira_prohibited_class_mode_regs
[cl
][j
]);
1508 for (k
= ira_class_hard_regs_num
[cl
] - 1; k
>= 0; k
--)
1510 hard_regno
= ira_class_hard_regs
[cl
][k
];
1511 if (! HARD_REGNO_MODE_OK (hard_regno
, (machine_mode
) j
))
1512 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1514 else if (in_hard_reg_set_p (temp_hard_regset
,
1515 (machine_mode
) j
, hard_regno
))
1517 last_hard_regno
= hard_regno
;
1521 ira_class_singleton
[cl
][j
] = (count
== 1 ? last_hard_regno
: -1);
1526 /* Clarify IRA_PROHIBITED_CLASS_MODE_REGS by excluding hard registers
1527 spanning from one register pressure class to another one. It is
1528 called after defining the pressure classes. */
1530 clarify_prohibited_class_mode_regs (void)
1532 int j
, k
, hard_regno
, cl
, pclass
, nregs
;
1534 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
1535 for (j
= 0; j
< NUM_MACHINE_MODES
; j
++)
1537 CLEAR_HARD_REG_SET (ira_useful_class_mode_regs
[cl
][j
]);
1538 for (k
= ira_class_hard_regs_num
[cl
] - 1; k
>= 0; k
--)
1540 hard_regno
= ira_class_hard_regs
[cl
][k
];
1541 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
], hard_regno
))
1543 nregs
= hard_regno_nregs
[hard_regno
][j
];
1544 if (hard_regno
+ nregs
> FIRST_PSEUDO_REGISTER
)
1546 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1550 pclass
= ira_pressure_class_translate
[REGNO_REG_CLASS (hard_regno
)];
1551 for (nregs
-- ;nregs
>= 0; nregs
--)
1552 if (((enum reg_class
) pclass
1553 != ira_pressure_class_translate
[REGNO_REG_CLASS
1554 (hard_regno
+ nregs
)]))
1556 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1560 if (!TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
[cl
][j
],
1562 add_to_hard_reg_set (&ira_useful_class_mode_regs
[cl
][j
],
1563 (machine_mode
) j
, hard_regno
);
1568 /* Allocate and initialize IRA_REGISTER_MOVE_COST, IRA_MAY_MOVE_IN_COST
1569 and IRA_MAY_MOVE_OUT_COST for MODE. */
1571 ira_init_register_move_cost (machine_mode mode
)
1573 static unsigned short last_move_cost
[N_REG_CLASSES
][N_REG_CLASSES
];
1574 bool all_match
= true;
1575 unsigned int cl1
, cl2
;
1577 ira_assert (ira_register_move_cost
[mode
] == NULL
1578 && ira_may_move_in_cost
[mode
] == NULL
1579 && ira_may_move_out_cost
[mode
] == NULL
);
1580 ira_assert (have_regs_of_mode
[mode
]);
1581 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1582 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1585 if (!contains_reg_of_mode
[cl1
][mode
]
1586 || !contains_reg_of_mode
[cl2
][mode
])
1588 if ((ira_reg_class_max_nregs
[cl1
][mode
]
1589 > ira_class_hard_regs_num
[cl1
])
1590 || (ira_reg_class_max_nregs
[cl2
][mode
]
1591 > ira_class_hard_regs_num
[cl2
]))
1594 cost
= (ira_memory_move_cost
[mode
][cl1
][0]
1595 + ira_memory_move_cost
[mode
][cl2
][1]) * 2;
1599 cost
= register_move_cost (mode
, (enum reg_class
) cl1
,
1600 (enum reg_class
) cl2
);
1601 ira_assert (cost
< 65535);
1603 all_match
&= (last_move_cost
[cl1
][cl2
] == cost
);
1604 last_move_cost
[cl1
][cl2
] = cost
;
1606 if (all_match
&& last_mode_for_init_move_cost
!= -1)
1608 ira_register_move_cost
[mode
]
1609 = ira_register_move_cost
[last_mode_for_init_move_cost
];
1610 ira_may_move_in_cost
[mode
]
1611 = ira_may_move_in_cost
[last_mode_for_init_move_cost
];
1612 ira_may_move_out_cost
[mode
]
1613 = ira_may_move_out_cost
[last_mode_for_init_move_cost
];
1616 last_mode_for_init_move_cost
= mode
;
1617 ira_register_move_cost
[mode
] = XNEWVEC (move_table
, N_REG_CLASSES
);
1618 ira_may_move_in_cost
[mode
] = XNEWVEC (move_table
, N_REG_CLASSES
);
1619 ira_may_move_out_cost
[mode
] = XNEWVEC (move_table
, N_REG_CLASSES
);
1620 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1621 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1624 enum reg_class
*p1
, *p2
;
1626 if (last_move_cost
[cl1
][cl2
] == 65535)
1628 ira_register_move_cost
[mode
][cl1
][cl2
] = 65535;
1629 ira_may_move_in_cost
[mode
][cl1
][cl2
] = 65535;
1630 ira_may_move_out_cost
[mode
][cl1
][cl2
] = 65535;
1634 cost
= last_move_cost
[cl1
][cl2
];
1636 for (p2
= ®_class_subclasses
[cl2
][0];
1637 *p2
!= LIM_REG_CLASSES
; p2
++)
1638 if (ira_class_hard_regs_num
[*p2
] > 0
1639 && (ira_reg_class_max_nregs
[*p2
][mode
]
1640 <= ira_class_hard_regs_num
[*p2
]))
1641 cost
= MAX (cost
, ira_register_move_cost
[mode
][cl1
][*p2
]);
1643 for (p1
= ®_class_subclasses
[cl1
][0];
1644 *p1
!= LIM_REG_CLASSES
; p1
++)
1645 if (ira_class_hard_regs_num
[*p1
] > 0
1646 && (ira_reg_class_max_nregs
[*p1
][mode
]
1647 <= ira_class_hard_regs_num
[*p1
]))
1648 cost
= MAX (cost
, ira_register_move_cost
[mode
][*p1
][cl2
]);
1650 ira_assert (cost
<= 65535);
1651 ira_register_move_cost
[mode
][cl1
][cl2
] = cost
;
1653 if (ira_class_subset_p
[cl1
][cl2
])
1654 ira_may_move_in_cost
[mode
][cl1
][cl2
] = 0;
1656 ira_may_move_in_cost
[mode
][cl1
][cl2
] = cost
;
1658 if (ira_class_subset_p
[cl2
][cl1
])
1659 ira_may_move_out_cost
[mode
][cl1
][cl2
] = 0;
1661 ira_may_move_out_cost
[mode
][cl1
][cl2
] = cost
;
1668 /* This is called once during compiler work. It sets up
1669 different arrays whose values don't depend on the compiled
1672 ira_init_once (void)
1674 ira_init_costs_once ();
1677 ira_use_lra_p
= targetm
.lra_p ();
1680 /* Free ira_max_register_move_cost, ira_may_move_in_cost and
1681 ira_may_move_out_cost for each mode. */
1683 target_ira_int::free_register_move_costs (void)
1687 /* Reset move_cost and friends, making sure we only free shared
1688 table entries once. */
1689 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
1690 if (x_ira_register_move_cost
[mode
])
1693 i
< mode
&& (x_ira_register_move_cost
[i
]
1694 != x_ira_register_move_cost
[mode
]);
1699 free (x_ira_register_move_cost
[mode
]);
1700 free (x_ira_may_move_in_cost
[mode
]);
1701 free (x_ira_may_move_out_cost
[mode
]);
1704 memset (x_ira_register_move_cost
, 0, sizeof x_ira_register_move_cost
);
1705 memset (x_ira_may_move_in_cost
, 0, sizeof x_ira_may_move_in_cost
);
1706 memset (x_ira_may_move_out_cost
, 0, sizeof x_ira_may_move_out_cost
);
1707 last_mode_for_init_move_cost
= -1;
1710 target_ira_int::~target_ira_int ()
1713 free_register_move_costs ();
1716 /* This is called every time when register related information is
1721 this_target_ira_int
->free_register_move_costs ();
1722 setup_reg_mode_hard_regset ();
1723 setup_alloc_regs (flag_omit_frame_pointer
!= 0);
1724 setup_class_subset_and_memory_move_costs ();
1725 setup_reg_class_nregs ();
1726 setup_prohibited_class_mode_regs ();
1727 find_reg_classes ();
1728 clarify_prohibited_class_mode_regs ();
1729 setup_hard_regno_aclass ();
1734 #define ira_prohibited_mode_move_regs_initialized_p \
1735 (this_target_ira_int->x_ira_prohibited_mode_move_regs_initialized_p)
1737 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS. */
1739 setup_prohibited_mode_move_regs (void)
1742 rtx test_reg1
, test_reg2
, move_pat
;
1743 rtx_insn
*move_insn
;
1745 if (ira_prohibited_mode_move_regs_initialized_p
)
1747 ira_prohibited_mode_move_regs_initialized_p
= true;
1748 test_reg1
= gen_rtx_REG (word_mode
, LAST_VIRTUAL_REGISTER
+ 1);
1749 test_reg2
= gen_rtx_REG (word_mode
, LAST_VIRTUAL_REGISTER
+ 2);
1750 move_pat
= gen_rtx_SET (test_reg1
, test_reg2
);
1751 move_insn
= gen_rtx_INSN (VOIDmode
, 0, 0, 0, move_pat
, 0, -1, 0);
1752 for (i
= 0; i
< NUM_MACHINE_MODES
; i
++)
1754 SET_HARD_REG_SET (ira_prohibited_mode_move_regs
[i
]);
1755 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1757 if (! HARD_REGNO_MODE_OK (j
, (machine_mode
) i
))
1759 set_mode_and_regno (test_reg1
, (machine_mode
) i
, j
);
1760 set_mode_and_regno (test_reg2
, (machine_mode
) i
, j
);
1761 INSN_CODE (move_insn
) = -1;
1762 recog_memoized (move_insn
);
1763 if (INSN_CODE (move_insn
) < 0)
1765 extract_insn (move_insn
);
1766 /* We don't know whether the move will be in code that is optimized
1767 for size or speed, so consider all enabled alternatives. */
1768 if (! constrain_operands (1, get_enabled_alternatives (move_insn
)))
1770 CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs
[i
], j
);
1777 /* Setup possible alternatives in ALTS for INSN. */
1779 ira_setup_alts (rtx_insn
*insn
, HARD_REG_SET
&alts
)
1781 /* MAP nalt * nop -> start of constraints for given operand and
1783 static vec
<const char *> insn_constraints
;
1787 int commutative
= -1;
1789 extract_insn (insn
);
1790 alternative_mask preferred
= get_preferred_alternatives (insn
);
1791 CLEAR_HARD_REG_SET (alts
);
1792 insn_constraints
.release ();
1793 insn_constraints
.safe_grow_cleared (recog_data
.n_operands
1794 * recog_data
.n_alternatives
+ 1);
1795 /* Check that the hard reg set is enough for holding all
1796 alternatives. It is hard to imagine the situation when the
1797 assertion is wrong. */
1798 ira_assert (recog_data
.n_alternatives
1799 <= (int) MAX (sizeof (HARD_REG_ELT_TYPE
) * CHAR_BIT
,
1800 FIRST_PSEUDO_REGISTER
));
1801 for (curr_swapped
= false;; curr_swapped
= true)
1803 /* Calculate some data common for all alternatives to speed up the
1805 for (nop
= 0; nop
< recog_data
.n_operands
; nop
++)
1807 for (nalt
= 0, p
= recog_data
.constraints
[nop
];
1808 nalt
< recog_data
.n_alternatives
;
1811 insn_constraints
[nop
* recog_data
.n_alternatives
+ nalt
] = p
;
1812 while (*p
&& *p
!= ',')
1814 /* We only support one commutative marker, the first
1815 one. We already set commutative above. */
1816 if (*p
== '%' && commutative
< 0)
1824 for (nalt
= 0; nalt
< recog_data
.n_alternatives
; nalt
++)
1826 if (!TEST_BIT (preferred
, nalt
)
1827 || TEST_HARD_REG_BIT (alts
, nalt
))
1830 for (nop
= 0; nop
< recog_data
.n_operands
; nop
++)
1834 rtx op
= recog_data
.operand
[nop
];
1835 p
= insn_constraints
[nop
* recog_data
.n_alternatives
+ nalt
];
1836 if (*p
== 0 || *p
== ',')
1840 switch (c
= *p
, len
= CONSTRAINT_LEN (c
, p
), c
)
1851 /* The commutative modifier is handled above. */
1854 case '0': case '1': case '2': case '3': case '4':
1855 case '5': case '6': case '7': case '8': case '9':
1865 enum constraint_num cn
= lookup_constraint (p
);
1866 switch (get_constraint_type (cn
))
1869 if (reg_class_for_constraint (cn
) != NO_REGS
)
1874 if (CONST_INT_P (op
)
1875 && (insn_const_int_ok_for_constraint
1882 case CT_SPECIAL_MEMORY
:
1886 if (constraint_satisfied_p (op
, cn
))
1893 while (p
+= len
, c
);
1898 if (nop
>= recog_data
.n_operands
)
1899 SET_HARD_REG_BIT (alts
, nalt
);
1901 if (commutative
< 0)
1903 /* Swap forth and back to avoid changing recog_data. */
1904 std::swap (recog_data
.operand
[commutative
],
1905 recog_data
.operand
[commutative
+ 1]);
1911 /* Return the number of the output non-early clobber operand which
1912 should be the same in any case as operand with number OP_NUM (or
1913 negative value if there is no such operand). The function takes
1914 only really possible alternatives into consideration. */
1916 ira_get_dup_out_num (int op_num
, HARD_REG_SET
&alts
)
1918 int curr_alt
, c
, original
, dup
;
1919 bool ignore_p
, use_commut_op_p
;
1922 if (op_num
< 0 || recog_data
.n_alternatives
== 0)
1924 /* We should find duplications only for input operands. */
1925 if (recog_data
.operand_type
[op_num
] != OP_IN
)
1927 str
= recog_data
.constraints
[op_num
];
1928 use_commut_op_p
= false;
1931 rtx op
= recog_data
.operand
[op_num
];
1933 for (curr_alt
= 0, ignore_p
= !TEST_HARD_REG_BIT (alts
, curr_alt
),
1944 ignore_p
= !TEST_HARD_REG_BIT (alts
, curr_alt
);
1946 else if (! ignore_p
)
1953 enum constraint_num cn
= lookup_constraint (str
);
1954 enum reg_class cl
= reg_class_for_constraint (cn
);
1956 && !targetm
.class_likely_spilled_p (cl
))
1958 if (constraint_satisfied_p (op
, cn
))
1963 case '0': case '1': case '2': case '3': case '4':
1964 case '5': case '6': case '7': case '8': case '9':
1965 if (original
!= -1 && original
!= c
)
1970 str
+= CONSTRAINT_LEN (c
, str
);
1975 for (ignore_p
= false, str
= recog_data
.constraints
[original
- '0'];
1983 else if (*str
== '#')
1985 else if (! ignore_p
)
1988 dup
= original
- '0';
1989 /* It is better ignore an alternative with early clobber. */
1990 else if (*str
== '&')
1996 if (use_commut_op_p
)
1998 use_commut_op_p
= true;
1999 if (recog_data
.constraints
[op_num
][0] == '%')
2000 str
= recog_data
.constraints
[op_num
+ 1];
2001 else if (op_num
> 0 && recog_data
.constraints
[op_num
- 1][0] == '%')
2002 str
= recog_data
.constraints
[op_num
- 1];
2011 /* Search forward to see if the source register of a copy insn dies
2012 before either it or the destination register is modified, but don't
2013 scan past the end of the basic block. If so, we can replace the
2014 source with the destination and let the source die in the copy
2017 This will reduce the number of registers live in that range and may
2018 enable the destination and the source coalescing, thus often saving
2019 one register in addition to a register-register copy. */
2022 decrease_live_ranges_number (void)
2026 rtx set
, src
, dest
, dest_death
, note
;
2030 if (! flag_expensive_optimizations
)
2034 fprintf (ira_dump_file
, "Starting decreasing number of live ranges...\n");
2036 FOR_EACH_BB_FN (bb
, cfun
)
2037 FOR_BB_INSNS (bb
, insn
)
2039 set
= single_set (insn
);
2042 src
= SET_SRC (set
);
2043 dest
= SET_DEST (set
);
2044 if (! REG_P (src
) || ! REG_P (dest
)
2045 || find_reg_note (insn
, REG_DEAD
, src
))
2047 sregno
= REGNO (src
);
2048 dregno
= REGNO (dest
);
2050 /* We don't want to mess with hard regs if register classes
2052 if (sregno
== dregno
2053 || (targetm
.small_register_classes_for_mode_p (GET_MODE (src
))
2054 && (sregno
< FIRST_PSEUDO_REGISTER
2055 || dregno
< FIRST_PSEUDO_REGISTER
))
2056 /* We don't see all updates to SP if they are in an
2057 auto-inc memory reference, so we must disallow this
2058 optimization on them. */
2059 || sregno
== STACK_POINTER_REGNUM
2060 || dregno
== STACK_POINTER_REGNUM
)
2063 dest_death
= NULL_RTX
;
2065 for (p
= NEXT_INSN (insn
); p
; p
= NEXT_INSN (p
))
2069 if (BLOCK_FOR_INSN (p
) != bb
)
2072 if (reg_set_p (src
, p
) || reg_set_p (dest
, p
)
2073 /* If SRC is an asm-declared register, it must not be
2074 replaced in any asm. Unfortunately, the REG_EXPR
2075 tree for the asm variable may be absent in the SRC
2076 rtx, so we can't check the actual register
2077 declaration easily (the asm operand will have it,
2078 though). To avoid complicating the test for a rare
2079 case, we just don't perform register replacement
2080 for a hard reg mentioned in an asm. */
2081 || (sregno
< FIRST_PSEUDO_REGISTER
2082 && asm_noperands (PATTERN (p
)) >= 0
2083 && reg_overlap_mentioned_p (src
, PATTERN (p
)))
2084 /* Don't change hard registers used by a call. */
2085 || (CALL_P (p
) && sregno
< FIRST_PSEUDO_REGISTER
2086 && find_reg_fusage (p
, USE
, src
))
2087 /* Don't change a USE of a register. */
2088 || (GET_CODE (PATTERN (p
)) == USE
2089 && reg_overlap_mentioned_p (src
, XEXP (PATTERN (p
), 0))))
2092 /* See if all of SRC dies in P. This test is slightly
2093 more conservative than it needs to be. */
2094 if ((note
= find_regno_note (p
, REG_DEAD
, sregno
))
2095 && GET_MODE (XEXP (note
, 0)) == GET_MODE (src
))
2099 /* We can do the optimization. Scan forward from INSN
2100 again, replacing regs as we go. Set FAILED if a
2101 replacement can't be done. In that case, we can't
2102 move the death note for SRC. This should be
2105 /* Set to stop at next insn. */
2106 for (q
= next_real_insn (insn
);
2107 q
!= next_real_insn (p
);
2108 q
= next_real_insn (q
))
2110 if (reg_overlap_mentioned_p (src
, PATTERN (q
)))
2112 /* If SRC is a hard register, we might miss
2113 some overlapping registers with
2114 validate_replace_rtx, so we would have to
2115 undo it. We can't if DEST is present in
2116 the insn, so fail in that combination of
2118 if (sregno
< FIRST_PSEUDO_REGISTER
2119 && reg_mentioned_p (dest
, PATTERN (q
)))
2122 /* Attempt to replace all uses. */
2123 else if (!validate_replace_rtx (src
, dest
, q
))
2126 /* If this succeeded, but some part of the
2127 register is still present, undo the
2129 else if (sregno
< FIRST_PSEUDO_REGISTER
2130 && reg_overlap_mentioned_p (src
, PATTERN (q
)))
2132 validate_replace_rtx (dest
, src
, q
);
2137 /* If DEST dies here, remove the death note and
2138 save it for later. Make sure ALL of DEST dies
2139 here; again, this is overly conservative. */
2141 && (dest_death
= find_regno_note (q
, REG_DEAD
, dregno
)))
2143 if (GET_MODE (XEXP (dest_death
, 0)) == GET_MODE (dest
))
2144 remove_note (q
, dest_death
);
2155 /* Move death note of SRC from P to INSN. */
2156 remove_note (p
, note
);
2157 XEXP (note
, 1) = REG_NOTES (insn
);
2158 REG_NOTES (insn
) = note
;
2161 /* DEST is also dead if INSN has a REG_UNUSED note for
2165 = find_regno_note (insn
, REG_UNUSED
, dregno
)))
2167 PUT_REG_NOTE_KIND (dest_death
, REG_DEAD
);
2168 remove_note (insn
, dest_death
);
2171 /* Put death note of DEST on P if we saw it die. */
2174 XEXP (dest_death
, 1) = REG_NOTES (p
);
2175 REG_NOTES (p
) = dest_death
;
2180 /* If SRC is a hard register which is set or killed in
2181 some other way, we can't do this optimization. */
2182 else if (sregno
< FIRST_PSEUDO_REGISTER
&& dead_or_set_p (p
, src
))
2190 /* Return nonzero if REGNO is a particularly bad choice for reloading X. */
2192 ira_bad_reload_regno_1 (int regno
, rtx x
)
2196 enum reg_class pref
;
2198 /* We only deal with pseudo regs. */
2199 if (! x
|| GET_CODE (x
) != REG
)
2202 x_regno
= REGNO (x
);
2203 if (x_regno
< FIRST_PSEUDO_REGISTER
)
2206 /* If the pseudo prefers REGNO explicitly, then do not consider
2207 REGNO a bad spill choice. */
2208 pref
= reg_preferred_class (x_regno
);
2209 if (reg_class_size
[pref
] == 1)
2210 return !TEST_HARD_REG_BIT (reg_class_contents
[pref
], regno
);
2212 /* If the pseudo conflicts with REGNO, then we consider REGNO a
2213 poor choice for a reload regno. */
2214 a
= ira_regno_allocno_map
[x_regno
];
2215 n
= ALLOCNO_NUM_OBJECTS (a
);
2216 for (i
= 0; i
< n
; i
++)
2218 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2219 if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), regno
))
2225 /* Return nonzero if REGNO is a particularly bad choice for reloading
2228 ira_bad_reload_regno (int regno
, rtx in
, rtx out
)
2230 return (ira_bad_reload_regno_1 (regno
, in
)
2231 || ira_bad_reload_regno_1 (regno
, out
));
2234 /* Add register clobbers from asm statements. */
2236 compute_regs_asm_clobbered (void)
2240 FOR_EACH_BB_FN (bb
, cfun
)
2243 FOR_BB_INSNS_REVERSE (bb
, insn
)
2247 if (NONDEBUG_INSN_P (insn
) && asm_noperands (PATTERN (insn
)) >= 0)
2248 FOR_EACH_INSN_DEF (def
, insn
)
2250 unsigned int dregno
= DF_REF_REGNO (def
);
2251 if (HARD_REGISTER_NUM_P (dregno
))
2252 add_to_hard_reg_set (&crtl
->asm_clobbers
,
2253 GET_MODE (DF_REF_REAL_REG (def
)),
2261 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and
2264 ira_setup_eliminable_regset (void)
2267 static const struct {const int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
2269 /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
2270 sp for alloca. So we can't eliminate the frame pointer in that
2271 case. At some point, we should improve this by emitting the
2272 sp-adjusting insns for this case. */
2273 frame_pointer_needed
2274 = (! flag_omit_frame_pointer
2275 || (cfun
->calls_alloca
&& EXIT_IGNORE_STACK
)
2276 /* We need the frame pointer to catch stack overflow exceptions if
2277 the stack pointer is moving (as for the alloca case just above). */
2278 || (STACK_CHECK_MOVING_SP
2281 && cfun
->can_throw_non_call_exceptions
)
2282 || crtl
->accesses_prior_frames
2283 || (SUPPORTS_STACK_ALIGNMENT
&& crtl
->stack_realign_needed
)
2284 /* We need a frame pointer for all Cilk Plus functions that use
2286 || (flag_cilkplus
&& cfun
->is_cilk_function
)
2287 || targetm
.frame_pointer_required ());
2289 /* The chance that FRAME_POINTER_NEEDED is changed from inspecting
2290 RTL is very small. So if we use frame pointer for RA and RTL
2291 actually prevents this, we will spill pseudos assigned to the
2292 frame pointer in LRA. */
2294 if (frame_pointer_needed
)
2295 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM
, true);
2297 COPY_HARD_REG_SET (ira_no_alloc_regs
, no_unit_alloc_regs
);
2298 CLEAR_HARD_REG_SET (eliminable_regset
);
2300 compute_regs_asm_clobbered ();
2302 /* Build the regset of all eliminable registers and show we can't
2303 use those that we already know won't be eliminated. */
2304 for (i
= 0; i
< (int) ARRAY_SIZE (eliminables
); i
++)
2307 = (! targetm
.can_eliminate (eliminables
[i
].from
, eliminables
[i
].to
)
2308 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& frame_pointer_needed
));
2310 if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
, eliminables
[i
].from
))
2312 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
2315 SET_HARD_REG_BIT (ira_no_alloc_regs
, eliminables
[i
].from
);
2317 else if (cannot_elim
)
2318 error ("%s cannot be used in asm here",
2319 reg_names
[eliminables
[i
].from
]);
2321 df_set_regs_ever_live (eliminables
[i
].from
, true);
2323 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
)
2325 if (!TEST_HARD_REG_BIT (crtl
->asm_clobbers
, HARD_FRAME_POINTER_REGNUM
))
2327 SET_HARD_REG_BIT (eliminable_regset
, HARD_FRAME_POINTER_REGNUM
);
2328 if (frame_pointer_needed
)
2329 SET_HARD_REG_BIT (ira_no_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
2331 else if (frame_pointer_needed
)
2332 error ("%s cannot be used in asm here",
2333 reg_names
[HARD_FRAME_POINTER_REGNUM
]);
2335 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM
, true);
2341 /* Vector of substitutions of register numbers,
2342 used to map pseudo regs into hardware regs.
2343 This is set up as a result of register allocation.
2344 Element N is the hard reg assigned to pseudo reg N,
2345 or is -1 if no hard reg was assigned.
2346 If N is a hard reg number, element N is N. */
2347 short *reg_renumber
;
2349 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
2350 the allocation found by IRA. */
2352 setup_reg_renumber (void)
2354 int regno
, hard_regno
;
2356 ira_allocno_iterator ai
;
2358 caller_save_needed
= 0;
2359 FOR_EACH_ALLOCNO (a
, ai
)
2361 if (ira_use_lra_p
&& ALLOCNO_CAP_MEMBER (a
) != NULL
)
2363 /* There are no caps at this point. */
2364 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
2365 if (! ALLOCNO_ASSIGNED_P (a
))
2366 /* It can happen if A is not referenced but partially anticipated
2367 somewhere in a region. */
2368 ALLOCNO_ASSIGNED_P (a
) = true;
2369 ira_free_allocno_updated_costs (a
);
2370 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2371 regno
= ALLOCNO_REGNO (a
);
2372 reg_renumber
[regno
] = (hard_regno
< 0 ? -1 : hard_regno
);
2373 if (hard_regno
>= 0)
2376 enum reg_class pclass
;
2379 pclass
= ira_pressure_class_translate
[REGNO_REG_CLASS (hard_regno
)];
2380 nwords
= ALLOCNO_NUM_OBJECTS (a
);
2381 for (i
= 0; i
< nwords
; i
++)
2383 obj
= ALLOCNO_OBJECT (a
, i
);
2384 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
2385 reg_class_contents
[pclass
]);
2387 if (ALLOCNO_CALLS_CROSSED_NUM (a
) != 0
2388 && ira_hard_reg_set_intersection_p (hard_regno
, ALLOCNO_MODE (a
),
2391 ira_assert (!optimize
|| flag_caller_saves
2392 || (ALLOCNO_CALLS_CROSSED_NUM (a
)
2393 == ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
))
2394 || regno
>= ira_reg_equiv_len
2395 || ira_equiv_no_lvalue_p (regno
));
2396 caller_save_needed
= 1;
2402 /* Set up allocno assignment flags for further allocation
2405 setup_allocno_assignment_flags (void)
2409 ira_allocno_iterator ai
;
2411 FOR_EACH_ALLOCNO (a
, ai
)
2413 if (! ALLOCNO_ASSIGNED_P (a
))
2414 /* It can happen if A is not referenced but partially anticipated
2415 somewhere in a region. */
2416 ira_free_allocno_updated_costs (a
);
2417 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2418 /* Don't assign hard registers to allocnos which are destination
2419 of removed store at the end of loop. It has no sense to keep
2420 the same value in different hard registers. It is also
2421 impossible to assign hard registers correctly to such
2422 allocnos because the cost info and info about intersected
2423 calls are incorrect for them. */
2424 ALLOCNO_ASSIGNED_P (a
) = (hard_regno
>= 0
2425 || ALLOCNO_EMIT_DATA (a
)->mem_optimized_dest_p
2426 || (ALLOCNO_MEMORY_COST (a
)
2427 - ALLOCNO_CLASS_COST (a
)) < 0);
2430 || ira_hard_reg_in_set_p (hard_regno
, ALLOCNO_MODE (a
),
2431 reg_class_contents
[ALLOCNO_CLASS (a
)]));
2435 /* Evaluate overall allocation cost and the costs for using hard
2436 registers and memory for allocnos. */
2438 calculate_allocation_cost (void)
2440 int hard_regno
, cost
;
2442 ira_allocno_iterator ai
;
2444 ira_overall_cost
= ira_reg_cost
= ira_mem_cost
= 0;
2445 FOR_EACH_ALLOCNO (a
, ai
)
2447 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2448 ira_assert (hard_regno
< 0
2449 || (ira_hard_reg_in_set_p
2450 (hard_regno
, ALLOCNO_MODE (a
),
2451 reg_class_contents
[ALLOCNO_CLASS (a
)])));
2454 cost
= ALLOCNO_MEMORY_COST (a
);
2455 ira_mem_cost
+= cost
;
2457 else if (ALLOCNO_HARD_REG_COSTS (a
) != NULL
)
2459 cost
= (ALLOCNO_HARD_REG_COSTS (a
)
2460 [ira_class_hard_reg_index
2461 [ALLOCNO_CLASS (a
)][hard_regno
]]);
2462 ira_reg_cost
+= cost
;
2466 cost
= ALLOCNO_CLASS_COST (a
);
2467 ira_reg_cost
+= cost
;
2469 ira_overall_cost
+= cost
;
2472 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
2474 fprintf (ira_dump_file
,
2475 "+++Costs: overall %" PRId64
2481 ira_overall_cost
, ira_reg_cost
, ira_mem_cost
,
2482 ira_load_cost
, ira_store_cost
, ira_shuffle_cost
);
2483 fprintf (ira_dump_file
, "\n+++ move loops %d, new jumps %d\n",
2484 ira_move_loops_num
, ira_additional_jumps_num
);
2489 #ifdef ENABLE_IRA_CHECKING
2490 /* Check the correctness of the allocation. We do need this because
2491 of complicated code to transform more one region internal
2492 representation into one region representation. */
2494 check_allocation (void)
2497 int hard_regno
, nregs
, conflict_nregs
;
2498 ira_allocno_iterator ai
;
2500 FOR_EACH_ALLOCNO (a
, ai
)
2502 int n
= ALLOCNO_NUM_OBJECTS (a
);
2505 if (ALLOCNO_CAP_MEMBER (a
) != NULL
2506 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0)
2508 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (a
)];
2510 /* We allocated a single hard register. */
2513 /* We allocated multiple hard registers, and we will test
2514 conflicts in a granularity of single hard regs. */
2517 for (i
= 0; i
< n
; i
++)
2519 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2520 ira_object_t conflict_obj
;
2521 ira_object_conflict_iterator oci
;
2522 int this_regno
= hard_regno
;
2525 if (REG_WORDS_BIG_ENDIAN
)
2526 this_regno
+= n
- i
- 1;
2530 FOR_EACH_OBJECT_CONFLICT (obj
, conflict_obj
, oci
)
2532 ira_allocno_t conflict_a
= OBJECT_ALLOCNO (conflict_obj
);
2533 int conflict_hard_regno
= ALLOCNO_HARD_REGNO (conflict_a
);
2534 if (conflict_hard_regno
< 0)
2539 [conflict_hard_regno
][ALLOCNO_MODE (conflict_a
)]);
2541 if (ALLOCNO_NUM_OBJECTS (conflict_a
) > 1
2542 && conflict_nregs
== ALLOCNO_NUM_OBJECTS (conflict_a
))
2544 if (REG_WORDS_BIG_ENDIAN
)
2545 conflict_hard_regno
+= (ALLOCNO_NUM_OBJECTS (conflict_a
)
2546 - OBJECT_SUBWORD (conflict_obj
) - 1);
2548 conflict_hard_regno
+= OBJECT_SUBWORD (conflict_obj
);
2552 if ((conflict_hard_regno
<= this_regno
2553 && this_regno
< conflict_hard_regno
+ conflict_nregs
)
2554 || (this_regno
<= conflict_hard_regno
2555 && conflict_hard_regno
< this_regno
+ nregs
))
2557 fprintf (stderr
, "bad allocation for %d and %d\n",
2558 ALLOCNO_REGNO (a
), ALLOCNO_REGNO (conflict_a
));
2567 /* Allocate REG_EQUIV_INIT. Set up it from IRA_REG_EQUIV which should
2568 be already calculated. */
2570 setup_reg_equiv_init (void)
2573 int max_regno
= max_reg_num ();
2575 for (i
= 0; i
< max_regno
; i
++)
2576 reg_equiv_init (i
) = ira_reg_equiv
[i
].init_insns
;
2579 /* Update equiv regno from movement of FROM_REGNO to TO_REGNO. INSNS
2580 are insns which were generated for such movement. It is assumed
2581 that FROM_REGNO and TO_REGNO always have the same value at the
2582 point of any move containing such registers. This function is used
2583 to update equiv info for register shuffles on the region borders
2584 and for caller save/restore insns. */
2586 ira_update_equiv_info_by_shuffle_insn (int to_regno
, int from_regno
, rtx_insn
*insns
)
2591 if (! ira_reg_equiv
[from_regno
].defined_p
2592 && (! ira_reg_equiv
[to_regno
].defined_p
2593 || ((x
= ira_reg_equiv
[to_regno
].memory
) != NULL_RTX
2594 && ! MEM_READONLY_P (x
))))
2597 if (NEXT_INSN (insn
) != NULL_RTX
)
2599 if (! ira_reg_equiv
[to_regno
].defined_p
)
2601 ira_assert (ira_reg_equiv
[to_regno
].init_insns
== NULL_RTX
);
2604 ira_reg_equiv
[to_regno
].defined_p
= false;
2605 ira_reg_equiv
[to_regno
].memory
2606 = ira_reg_equiv
[to_regno
].constant
2607 = ira_reg_equiv
[to_regno
].invariant
2608 = ira_reg_equiv
[to_regno
].init_insns
= NULL
;
2609 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2610 fprintf (ira_dump_file
,
2611 " Invalidating equiv info for reg %d\n", to_regno
);
2614 /* It is possible that FROM_REGNO still has no equivalence because
2615 in shuffles to_regno<-from_regno and from_regno<-to_regno the 2nd
2616 insn was not processed yet. */
2617 if (ira_reg_equiv
[from_regno
].defined_p
)
2619 ira_reg_equiv
[to_regno
].defined_p
= true;
2620 if ((x
= ira_reg_equiv
[from_regno
].memory
) != NULL_RTX
)
2622 ira_assert (ira_reg_equiv
[from_regno
].invariant
== NULL_RTX
2623 && ira_reg_equiv
[from_regno
].constant
== NULL_RTX
);
2624 ira_assert (ira_reg_equiv
[to_regno
].memory
== NULL_RTX
2625 || rtx_equal_p (ira_reg_equiv
[to_regno
].memory
, x
));
2626 ira_reg_equiv
[to_regno
].memory
= x
;
2627 if (! MEM_READONLY_P (x
))
2628 /* We don't add the insn to insn init list because memory
2629 equivalence is just to say what memory is better to use
2630 when the pseudo is spilled. */
2633 else if ((x
= ira_reg_equiv
[from_regno
].constant
) != NULL_RTX
)
2635 ira_assert (ira_reg_equiv
[from_regno
].invariant
== NULL_RTX
);
2636 ira_assert (ira_reg_equiv
[to_regno
].constant
== NULL_RTX
2637 || rtx_equal_p (ira_reg_equiv
[to_regno
].constant
, x
));
2638 ira_reg_equiv
[to_regno
].constant
= x
;
2642 x
= ira_reg_equiv
[from_regno
].invariant
;
2643 ira_assert (x
!= NULL_RTX
);
2644 ira_assert (ira_reg_equiv
[to_regno
].invariant
== NULL_RTX
2645 || rtx_equal_p (ira_reg_equiv
[to_regno
].invariant
, x
));
2646 ira_reg_equiv
[to_regno
].invariant
= x
;
2648 if (find_reg_note (insn
, REG_EQUIV
, x
) == NULL_RTX
)
2650 note
= set_unique_reg_note (insn
, REG_EQUIV
, copy_rtx (x
));
2651 gcc_assert (note
!= NULL_RTX
);
2652 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2654 fprintf (ira_dump_file
,
2655 " Adding equiv note to insn %u for reg %d ",
2656 INSN_UID (insn
), to_regno
);
2657 dump_value_slim (ira_dump_file
, x
, 1);
2658 fprintf (ira_dump_file
, "\n");
2662 ira_reg_equiv
[to_regno
].init_insns
2663 = gen_rtx_INSN_LIST (VOIDmode
, insn
,
2664 ira_reg_equiv
[to_regno
].init_insns
);
2665 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2666 fprintf (ira_dump_file
,
2667 " Adding equiv init move insn %u to reg %d\n",
2668 INSN_UID (insn
), to_regno
);
2671 /* Fix values of array REG_EQUIV_INIT after live range splitting done
2674 fix_reg_equiv_init (void)
2676 int max_regno
= max_reg_num ();
2677 int i
, new_regno
, max
;
2679 rtx_insn_list
*x
, *next
, *prev
;
2682 if (max_regno_before_ira
< max_regno
)
2684 max
= vec_safe_length (reg_equivs
);
2686 for (i
= FIRST_PSEUDO_REGISTER
; i
< max
; i
++)
2687 for (prev
= NULL
, x
= reg_equiv_init (i
);
2693 set
= single_set (insn
);
2694 ira_assert (set
!= NULL_RTX
2695 && (REG_P (SET_DEST (set
)) || REG_P (SET_SRC (set
))));
2696 if (REG_P (SET_DEST (set
))
2697 && ((int) REGNO (SET_DEST (set
)) == i
2698 || (int) ORIGINAL_REGNO (SET_DEST (set
)) == i
))
2699 new_regno
= REGNO (SET_DEST (set
));
2700 else if (REG_P (SET_SRC (set
))
2701 && ((int) REGNO (SET_SRC (set
)) == i
2702 || (int) ORIGINAL_REGNO (SET_SRC (set
)) == i
))
2703 new_regno
= REGNO (SET_SRC (set
));
2710 /* Remove the wrong list element. */
2711 if (prev
== NULL_RTX
)
2712 reg_equiv_init (i
) = next
;
2714 XEXP (prev
, 1) = next
;
2715 XEXP (x
, 1) = reg_equiv_init (new_regno
);
2716 reg_equiv_init (new_regno
) = x
;
2722 #ifdef ENABLE_IRA_CHECKING
2723 /* Print redundant memory-memory copies. */
2725 print_redundant_copies (void)
2729 ira_copy_t cp
, next_cp
;
2730 ira_allocno_iterator ai
;
2732 FOR_EACH_ALLOCNO (a
, ai
)
2734 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2737 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2738 if (hard_regno
>= 0)
2740 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2742 next_cp
= cp
->next_first_allocno_copy
;
2745 next_cp
= cp
->next_second_allocno_copy
;
2746 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
2747 && cp
->insn
!= NULL_RTX
2748 && ALLOCNO_HARD_REGNO (cp
->first
) == hard_regno
)
2749 fprintf (ira_dump_file
,
2750 " Redundant move from %d(freq %d):%d\n",
2751 INSN_UID (cp
->insn
), cp
->freq
, hard_regno
);
2757 /* Setup preferred and alternative classes for new pseudo-registers
2758 created by IRA starting with START. */
2760 setup_preferred_alternate_classes_for_new_pseudos (int start
)
2763 int max_regno
= max_reg_num ();
2765 for (i
= start
; i
< max_regno
; i
++)
2767 old_regno
= ORIGINAL_REGNO (regno_reg_rtx
[i
]);
2768 ira_assert (i
!= old_regno
);
2769 setup_reg_classes (i
, reg_preferred_class (old_regno
),
2770 reg_alternate_class (old_regno
),
2771 reg_allocno_class (old_regno
));
2772 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
2773 fprintf (ira_dump_file
,
2774 " New r%d: setting preferred %s, alternative %s\n",
2775 i
, reg_class_names
[reg_preferred_class (old_regno
)],
2776 reg_class_names
[reg_alternate_class (old_regno
)]);
2781 /* The number of entries allocated in reg_info. */
2782 static int allocated_reg_info_size
;
2784 /* Regional allocation can create new pseudo-registers. This function
2785 expands some arrays for pseudo-registers. */
2787 expand_reg_info (void)
2790 int size
= max_reg_num ();
2793 for (i
= allocated_reg_info_size
; i
< size
; i
++)
2794 setup_reg_classes (i
, GENERAL_REGS
, ALL_REGS
, GENERAL_REGS
);
2795 setup_preferred_alternate_classes_for_new_pseudos (allocated_reg_info_size
);
2796 allocated_reg_info_size
= size
;
2799 /* Return TRUE if there is too high register pressure in the function.
2800 It is used to decide when stack slot sharing is worth to do. */
2802 too_high_register_pressure_p (void)
2805 enum reg_class pclass
;
2807 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2809 pclass
= ira_pressure_classes
[i
];
2810 if (ira_loop_tree_root
->reg_pressure
[pclass
] > 10000)
2818 /* Indicate that hard register number FROM was eliminated and replaced with
2819 an offset from hard register number TO. The status of hard registers live
2820 at the start of a basic block is updated by replacing a use of FROM with
2824 mark_elimination (int from
, int to
)
2829 FOR_EACH_BB_FN (bb
, cfun
)
2832 if (bitmap_bit_p (r
, from
))
2834 bitmap_clear_bit (r
, from
);
2835 bitmap_set_bit (r
, to
);
2839 r
= DF_LIVE_IN (bb
);
2840 if (bitmap_bit_p (r
, from
))
2842 bitmap_clear_bit (r
, from
);
2843 bitmap_set_bit (r
, to
);
2850 /* The length of the following array. */
2851 int ira_reg_equiv_len
;
2853 /* Info about equiv. info for each register. */
2854 struct ira_reg_equiv_s
*ira_reg_equiv
;
2856 /* Expand ira_reg_equiv if necessary. */
2858 ira_expand_reg_equiv (void)
2860 int old
= ira_reg_equiv_len
;
2862 if (ira_reg_equiv_len
> max_reg_num ())
2864 ira_reg_equiv_len
= max_reg_num () * 3 / 2 + 1;
2866 = (struct ira_reg_equiv_s
*) xrealloc (ira_reg_equiv
,
2868 * sizeof (struct ira_reg_equiv_s
));
2869 gcc_assert (old
< ira_reg_equiv_len
);
2870 memset (ira_reg_equiv
+ old
, 0,
2871 sizeof (struct ira_reg_equiv_s
) * (ira_reg_equiv_len
- old
));
2875 init_reg_equiv (void)
2877 ira_reg_equiv_len
= 0;
2878 ira_reg_equiv
= NULL
;
2879 ira_expand_reg_equiv ();
2883 finish_reg_equiv (void)
2885 free (ira_reg_equiv
);
2892 /* Set when a REG_EQUIV note is found or created. Use to
2893 keep track of what memory accesses might be created later,
2898 /* The list of each instruction which initializes this register.
2900 NULL indicates we know nothing about this register's equivalence
2903 An INSN_LIST with a NULL insn indicates this pseudo is already
2904 known to not have a valid equivalence. */
2905 rtx_insn_list
*init_insns
;
2907 /* Loop depth is used to recognize equivalences which appear
2908 to be present within the same loop (or in an inner loop). */
2910 /* Nonzero if this had a preexisting REG_EQUIV note. */
2911 unsigned char is_arg_equivalence
: 1;
2912 /* Set when an attempt should be made to replace a register
2913 with the associated src_p entry. */
2914 unsigned char replace
: 1;
2915 /* Set if this register has no known equivalence. */
2916 unsigned char no_equiv
: 1;
2917 /* Set if this register is mentioned in a paradoxical subreg. */
2918 unsigned char pdx_subregs
: 1;
2921 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
2922 structure for that register. */
2923 static struct equivalence
*reg_equiv
;
2925 /* Used for communication between the following two functions. */
2926 struct equiv_mem_data
2928 /* A MEM that we wish to ensure remains unchanged. */
2931 /* Set true if EQUIV_MEM is modified. */
2932 bool equiv_mem_modified
;
2935 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
2936 Called via note_stores. */
2938 validate_equiv_mem_from_store (rtx dest
, const_rtx set ATTRIBUTE_UNUSED
,
2941 struct equiv_mem_data
*info
= (struct equiv_mem_data
*) data
;
2944 && reg_overlap_mentioned_p (dest
, info
->equiv_mem
))
2946 && anti_dependence (info
->equiv_mem
, dest
)))
2947 info
->equiv_mem_modified
= true;
2950 enum valid_equiv
{ valid_none
, valid_combine
, valid_reload
};
2952 /* Verify that no store between START and the death of REG invalidates
2953 MEMREF. MEMREF is invalidated by modifying a register used in MEMREF,
2954 by storing into an overlapping memory location, or with a non-const
2957 Return VALID_RELOAD if MEMREF remains valid for both reload and
2958 combine_and_move insns, VALID_COMBINE if only valid for
2959 combine_and_move_insns, and VALID_NONE otherwise. */
2960 static enum valid_equiv
2961 validate_equiv_mem (rtx_insn
*start
, rtx reg
, rtx memref
)
2965 struct equiv_mem_data info
= { memref
, false };
2966 enum valid_equiv ret
= valid_reload
;
2968 /* If the memory reference has side effects or is volatile, it isn't a
2969 valid equivalence. */
2970 if (side_effects_p (memref
))
2973 for (insn
= start
; insn
; insn
= NEXT_INSN (insn
))
2978 if (find_reg_note (insn
, REG_DEAD
, reg
))
2983 /* We can combine a reg def from one insn into a reg use in
2984 another over a call if the memory is readonly or the call
2985 const/pure. However, we can't set reg_equiv notes up for
2986 reload over any call. The problem is the equivalent form
2987 may reference a pseudo which gets assigned a call
2988 clobbered hard reg. When we later replace REG with its
2989 equivalent form, the value in the call-clobbered reg has
2990 been changed and all hell breaks loose. */
2991 ret
= valid_combine
;
2992 if (!MEM_READONLY_P (memref
)
2993 && !RTL_CONST_OR_PURE_CALL_P (insn
))
2997 note_stores (PATTERN (insn
), validate_equiv_mem_from_store
, &info
);
2998 if (info
.equiv_mem_modified
)
3001 /* If a register mentioned in MEMREF is modified via an
3002 auto-increment, we lose the equivalence. Do the same if one
3003 dies; although we could extend the life, it doesn't seem worth
3006 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
3007 if ((REG_NOTE_KIND (note
) == REG_INC
3008 || REG_NOTE_KIND (note
) == REG_DEAD
)
3009 && REG_P (XEXP (note
, 0))
3010 && reg_overlap_mentioned_p (XEXP (note
, 0), memref
))
3017 /* Returns zero if X is known to be invariant. */
3019 equiv_init_varies_p (rtx x
)
3021 RTX_CODE code
= GET_CODE (x
);
3028 return !MEM_READONLY_P (x
) || equiv_init_varies_p (XEXP (x
, 0));
3037 return reg_equiv
[REGNO (x
)].replace
== 0 && rtx_varies_p (x
, 0);
3040 if (MEM_VOLATILE_P (x
))
3049 fmt
= GET_RTX_FORMAT (code
);
3050 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3053 if (equiv_init_varies_p (XEXP (x
, i
)))
3056 else if (fmt
[i
] == 'E')
3059 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
3060 if (equiv_init_varies_p (XVECEXP (x
, i
, j
)))
3067 /* Returns nonzero if X (used to initialize register REGNO) is movable.
3068 X is only movable if the registers it uses have equivalent initializations
3069 which appear to be within the same loop (or in an inner loop) and movable
3070 or if they are not candidates for local_alloc and don't vary. */
3072 equiv_init_movable_p (rtx x
, int regno
)
3076 enum rtx_code code
= GET_CODE (x
);
3081 return equiv_init_movable_p (SET_SRC (x
), regno
);
3096 return ((reg_equiv
[REGNO (x
)].loop_depth
>= reg_equiv
[regno
].loop_depth
3097 && reg_equiv
[REGNO (x
)].replace
)
3098 || (REG_BASIC_BLOCK (REGNO (x
)) < NUM_FIXED_BLOCKS
3099 && ! rtx_varies_p (x
, 0)));
3101 case UNSPEC_VOLATILE
:
3105 if (MEM_VOLATILE_P (x
))
3114 fmt
= GET_RTX_FORMAT (code
);
3115 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3119 if (! equiv_init_movable_p (XEXP (x
, i
), regno
))
3123 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
3124 if (! equiv_init_movable_p (XVECEXP (x
, i
, j
), regno
))
3132 /* TRUE if X references a memory location that would be affected by a store
3135 memref_referenced_p (rtx memref
, rtx x
)
3139 enum rtx_code code
= GET_CODE (x
);
3154 return (reg_equiv
[REGNO (x
)].replacement
3155 && memref_referenced_p (memref
,
3156 reg_equiv
[REGNO (x
)].replacement
));
3159 if (true_dependence (memref
, VOIDmode
, x
))
3164 /* If we are setting a MEM, it doesn't count (its address does), but any
3165 other SET_DEST that has a MEM in it is referencing the MEM. */
3166 if (MEM_P (SET_DEST (x
)))
3168 if (memref_referenced_p (memref
, XEXP (SET_DEST (x
), 0)))
3171 else if (memref_referenced_p (memref
, SET_DEST (x
)))
3174 return memref_referenced_p (memref
, SET_SRC (x
));
3180 fmt
= GET_RTX_FORMAT (code
);
3181 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
3185 if (memref_referenced_p (memref
, XEXP (x
, i
)))
3189 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
3190 if (memref_referenced_p (memref
, XVECEXP (x
, i
, j
)))
3198 /* TRUE if some insn in the range (START, END] references a memory location
3199 that would be affected by a store to MEMREF.
3201 Callers should not call this routine if START is after END in the
3205 memref_used_between_p (rtx memref
, rtx_insn
*start
, rtx_insn
*end
)
3209 for (insn
= NEXT_INSN (start
);
3210 insn
&& insn
!= NEXT_INSN (end
);
3211 insn
= NEXT_INSN (insn
))
3213 if (!NONDEBUG_INSN_P (insn
))
3216 if (memref_referenced_p (memref
, PATTERN (insn
)))
3219 /* Nonconst functions may access memory. */
3220 if (CALL_P (insn
) && (! RTL_CONST_CALL_P (insn
)))
3224 gcc_assert (insn
== NEXT_INSN (end
));
3228 /* Mark REG as having no known equivalence.
3229 Some instructions might have been processed before and furnished
3230 with REG_EQUIV notes for this register; these notes will have to be
3232 STORE is the piece of RTL that does the non-constant / conflicting
3233 assignment - a SET, CLOBBER or REG_INC note. It is currently not used,
3234 but needs to be there because this function is called from note_stores. */
3236 no_equiv (rtx reg
, const_rtx store ATTRIBUTE_UNUSED
,
3237 void *data ATTRIBUTE_UNUSED
)
3240 rtx_insn_list
*list
;
3244 regno
= REGNO (reg
);
3245 reg_equiv
[regno
].no_equiv
= 1;
3246 list
= reg_equiv
[regno
].init_insns
;
3247 if (list
&& list
->insn () == NULL
)
3249 reg_equiv
[regno
].init_insns
= gen_rtx_INSN_LIST (VOIDmode
, NULL_RTX
, NULL
);
3250 reg_equiv
[regno
].replacement
= NULL_RTX
;
3251 /* This doesn't matter for equivalences made for argument registers, we
3252 should keep their initialization insns. */
3253 if (reg_equiv
[regno
].is_arg_equivalence
)
3255 ira_reg_equiv
[regno
].defined_p
= false;
3256 ira_reg_equiv
[regno
].init_insns
= NULL
;
3257 for (; list
; list
= list
->next ())
3259 rtx_insn
*insn
= list
->insn ();
3260 remove_note (insn
, find_reg_note (insn
, REG_EQUIV
, NULL_RTX
));
3264 /* Check whether the SUBREG is a paradoxical subreg and set the result
3268 set_paradoxical_subreg (rtx_insn
*insn
)
3270 subrtx_iterator::array_type array
;
3271 FOR_EACH_SUBRTX (iter
, array
, PATTERN (insn
), NONCONST
)
3273 const_rtx subreg
= *iter
;
3274 if (GET_CODE (subreg
) == SUBREG
)
3276 const_rtx reg
= SUBREG_REG (subreg
);
3277 if (REG_P (reg
) && paradoxical_subreg_p (subreg
))
3278 reg_equiv
[REGNO (reg
)].pdx_subregs
= true;
3283 /* In DEBUG_INSN location adjust REGs from CLEARED_REGS bitmap to the
3284 equivalent replacement. */
3287 adjust_cleared_regs (rtx loc
, const_rtx old_rtx ATTRIBUTE_UNUSED
, void *data
)
3291 bitmap cleared_regs
= (bitmap
) data
;
3292 if (bitmap_bit_p (cleared_regs
, REGNO (loc
)))
3293 return simplify_replace_fn_rtx (copy_rtx (*reg_equiv
[REGNO (loc
)].src_p
),
3294 NULL_RTX
, adjust_cleared_regs
, data
);
3299 /* Find registers that are equivalent to a single value throughout the
3300 compilation (either because they can be referenced in memory or are
3301 set once from a single constant). Lower their priority for a
3304 If such a register is only referenced once, try substituting its
3305 value into the using insn. If it succeeds, we can eliminate the
3306 register completely.
3308 Initialize init_insns in ira_reg_equiv array. */
3310 update_equiv_regs (void)
3315 /* Scan insns and set pdx_subregs if the reg is used in a
3316 paradoxical subreg. Don't set such reg equivalent to a mem,
3317 because lra will not substitute such equiv memory in order to
3318 prevent access beyond allocated memory for paradoxical memory subreg. */
3319 FOR_EACH_BB_FN (bb
, cfun
)
3320 FOR_BB_INSNS (bb
, insn
)
3321 if (NONDEBUG_INSN_P (insn
))
3322 set_paradoxical_subreg (insn
);
3324 /* Scan the insns and find which registers have equivalences. Do this
3325 in a separate scan of the insns because (due to -fcse-follow-jumps)
3326 a register can be set below its use. */
3327 bitmap setjmp_crosses
= regstat_get_setjmp_crosses ();
3328 FOR_EACH_BB_FN (bb
, cfun
)
3330 int loop_depth
= bb_loop_depth (bb
);
3332 for (insn
= BB_HEAD (bb
);
3333 insn
!= NEXT_INSN (BB_END (bb
));
3334 insn
= NEXT_INSN (insn
))
3341 if (! INSN_P (insn
))
3344 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
3345 if (REG_NOTE_KIND (note
) == REG_INC
)
3346 no_equiv (XEXP (note
, 0), note
, NULL
);
3348 set
= single_set (insn
);
3350 /* If this insn contains more (or less) than a single SET,
3351 only mark all destinations as having no known equivalence. */
3353 || side_effects_p (SET_SRC (set
)))
3355 note_stores (PATTERN (insn
), no_equiv
, NULL
);
3358 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
3362 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
3364 rtx part
= XVECEXP (PATTERN (insn
), 0, i
);
3366 note_stores (part
, no_equiv
, NULL
);
3370 dest
= SET_DEST (set
);
3371 src
= SET_SRC (set
);
3373 /* See if this is setting up the equivalence between an argument
3374 register and its stack slot. */
3375 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
3378 gcc_assert (REG_P (dest
));
3379 regno
= REGNO (dest
);
3381 /* Note that we don't want to clear init_insns in
3382 ira_reg_equiv even if there are multiple sets of this
3384 reg_equiv
[regno
].is_arg_equivalence
= 1;
3386 /* The insn result can have equivalence memory although
3387 the equivalence is not set up by the insn. We add
3388 this insn to init insns as it is a flag for now that
3389 regno has an equivalence. We will remove the insn
3390 from init insn list later. */
3391 if (rtx_equal_p (src
, XEXP (note
, 0)) || MEM_P (XEXP (note
, 0)))
3392 ira_reg_equiv
[regno
].init_insns
3393 = gen_rtx_INSN_LIST (VOIDmode
, insn
,
3394 ira_reg_equiv
[regno
].init_insns
);
3396 /* Continue normally in case this is a candidate for
3403 /* We only handle the case of a pseudo register being set
3404 once, or always to the same value. */
3405 /* ??? The mn10200 port breaks if we add equivalences for
3406 values that need an ADDRESS_REGS register and set them equivalent
3407 to a MEM of a pseudo. The actual problem is in the over-conservative
3408 handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
3409 calculate_needs, but we traditionally work around this problem
3410 here by rejecting equivalences when the destination is in a register
3411 that's likely spilled. This is fragile, of course, since the
3412 preferred class of a pseudo depends on all instructions that set
3416 || (regno
= REGNO (dest
)) < FIRST_PSEUDO_REGISTER
3417 || (reg_equiv
[regno
].init_insns
3418 && reg_equiv
[regno
].init_insns
->insn () == NULL
)
3419 || (targetm
.class_likely_spilled_p (reg_preferred_class (regno
))
3420 && MEM_P (src
) && ! reg_equiv
[regno
].is_arg_equivalence
))
3422 /* This might be setting a SUBREG of a pseudo, a pseudo that is
3423 also set somewhere else to a constant. */
3424 note_stores (set
, no_equiv
, NULL
);
3428 /* Don't set reg mentioned in a paradoxical subreg
3429 equivalent to a mem. */
3430 if (MEM_P (src
) && reg_equiv
[regno
].pdx_subregs
)
3432 note_stores (set
, no_equiv
, NULL
);
3436 note
= find_reg_note (insn
, REG_EQUAL
, NULL_RTX
);
3438 /* cse sometimes generates function invariants, but doesn't put a
3439 REG_EQUAL note on the insn. Since this note would be redundant,
3440 there's no point creating it earlier than here. */
3441 if (! note
&& ! rtx_varies_p (src
, 0))
3442 note
= set_unique_reg_note (insn
, REG_EQUAL
, copy_rtx (src
));
3444 /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
3445 since it represents a function call. */
3446 if (note
&& GET_CODE (XEXP (note
, 0)) == EXPR_LIST
)
3449 if (DF_REG_DEF_COUNT (regno
) != 1)
3451 bool equal_p
= true;
3452 rtx_insn_list
*list
;
3454 /* If we have already processed this pseudo and determined it
3455 can not have an equivalence, then honor that decision. */
3456 if (reg_equiv
[regno
].no_equiv
)
3460 || rtx_varies_p (XEXP (note
, 0), 0)
3461 || (reg_equiv
[regno
].replacement
3462 && ! rtx_equal_p (XEXP (note
, 0),
3463 reg_equiv
[regno
].replacement
)))
3465 no_equiv (dest
, set
, NULL
);
3469 list
= reg_equiv
[regno
].init_insns
;
3470 for (; list
; list
= list
->next ())
3475 insn_tmp
= list
->insn ();
3476 note_tmp
= find_reg_note (insn_tmp
, REG_EQUAL
, NULL_RTX
);
3477 gcc_assert (note_tmp
);
3478 if (! rtx_equal_p (XEXP (note
, 0), XEXP (note_tmp
, 0)))
3487 no_equiv (dest
, set
, NULL
);
3492 /* Record this insn as initializing this register. */
3493 reg_equiv
[regno
].init_insns
3494 = gen_rtx_INSN_LIST (VOIDmode
, insn
, reg_equiv
[regno
].init_insns
);
3496 /* If this register is known to be equal to a constant, record that
3497 it is always equivalent to the constant. */
3498 if (DF_REG_DEF_COUNT (regno
) == 1
3499 && note
&& ! rtx_varies_p (XEXP (note
, 0), 0))
3501 rtx note_value
= XEXP (note
, 0);
3502 remove_note (insn
, note
);
3503 set_unique_reg_note (insn
, REG_EQUIV
, note_value
);
3506 /* If this insn introduces a "constant" register, decrease the priority
3507 of that register. Record this insn if the register is only used once
3508 more and the equivalence value is the same as our source.
3510 The latter condition is checked for two reasons: First, it is an
3511 indication that it may be more efficient to actually emit the insn
3512 as written (if no registers are available, reload will substitute
3513 the equivalence). Secondly, it avoids problems with any registers
3514 dying in this insn whose death notes would be missed.
3516 If we don't have a REG_EQUIV note, see if this insn is loading
3517 a register used only in one basic block from a MEM. If so, and the
3518 MEM remains unchanged for the life of the register, add a REG_EQUIV
3520 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
3522 rtx replacement
= NULL_RTX
;
3524 replacement
= XEXP (note
, 0);
3525 else if (REG_BASIC_BLOCK (regno
) >= NUM_FIXED_BLOCKS
3526 && MEM_P (SET_SRC (set
)))
3528 enum valid_equiv validity
;
3529 validity
= validate_equiv_mem (insn
, dest
, SET_SRC (set
));
3530 if (validity
!= valid_none
)
3532 replacement
= copy_rtx (SET_SRC (set
));
3533 if (validity
== valid_reload
)
3534 note
= set_unique_reg_note (insn
, REG_EQUIV
, replacement
);
3538 /* If we haven't done so, record for reload that this is an
3539 equivalencing insn. */
3540 if (note
&& !reg_equiv
[regno
].is_arg_equivalence
)
3541 ira_reg_equiv
[regno
].init_insns
3542 = gen_rtx_INSN_LIST (VOIDmode
, insn
,
3543 ira_reg_equiv
[regno
].init_insns
);
3547 reg_equiv
[regno
].replacement
= replacement
;
3548 reg_equiv
[regno
].src_p
= &SET_SRC (set
);
3549 reg_equiv
[regno
].loop_depth
= (short) loop_depth
;
3551 /* Don't mess with things live during setjmp. */
3552 if (optimize
&& !bitmap_bit_p (setjmp_crosses
, regno
))
3554 /* If the register is referenced exactly twice, meaning it is
3555 set once and used once, indicate that the reference may be
3556 replaced by the equivalence we computed above. Do this
3557 even if the register is only used in one block so that
3558 dependencies can be handled where the last register is
3559 used in a different block (i.e. HIGH / LO_SUM sequences)
3560 and to reduce the number of registers alive across
3563 if (REG_N_REFS (regno
) == 2
3564 && (rtx_equal_p (replacement
, src
)
3565 || ! equiv_init_varies_p (src
))
3566 && NONJUMP_INSN_P (insn
)
3567 && equiv_init_movable_p (PATTERN (insn
), regno
))
3568 reg_equiv
[regno
].replace
= 1;
3575 /* For insns that set a MEM to the contents of a REG that is only used
3576 in a single basic block, see if the register is always equivalent
3577 to that memory location and if moving the store from INSN to the
3578 insn that sets REG is safe. If so, put a REG_EQUIV note on the
3579 initializing insn. */
3581 add_store_equivs (void)
3583 bitmap_head seen_insns
;
3585 bitmap_initialize (&seen_insns
, NULL
);
3586 for (rtx_insn
*insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
3590 rtx_insn
*init_insn
;
3592 bitmap_set_bit (&seen_insns
, INSN_UID (insn
));
3594 if (! INSN_P (insn
))
3597 set
= single_set (insn
);
3601 dest
= SET_DEST (set
);
3602 src
= SET_SRC (set
);
3604 /* Don't add a REG_EQUIV note if the insn already has one. The existing
3605 REG_EQUIV is likely more useful than the one we are adding. */
3606 if (MEM_P (dest
) && REG_P (src
)
3607 && (regno
= REGNO (src
)) >= FIRST_PSEUDO_REGISTER
3608 && REG_BASIC_BLOCK (regno
) >= NUM_FIXED_BLOCKS
3609 && DF_REG_DEF_COUNT (regno
) == 1
3610 && ! reg_equiv
[regno
].pdx_subregs
3611 && reg_equiv
[regno
].init_insns
!= NULL
3612 && (init_insn
= reg_equiv
[regno
].init_insns
->insn ()) != 0
3613 && bitmap_bit_p (&seen_insns
, INSN_UID (init_insn
))
3614 && ! find_reg_note (init_insn
, REG_EQUIV
, NULL_RTX
)
3615 && validate_equiv_mem (init_insn
, src
, dest
) == valid_reload
3616 && ! memref_used_between_p (dest
, init_insn
, insn
)
3617 /* Attaching a REG_EQUIV note will fail if INIT_INSN has
3619 && set_unique_reg_note (init_insn
, REG_EQUIV
, copy_rtx (dest
)))
3621 /* This insn makes the equivalence, not the one initializing
3623 ira_reg_equiv
[regno
].init_insns
3624 = gen_rtx_INSN_LIST (VOIDmode
, insn
, NULL_RTX
);
3625 df_notes_rescan (init_insn
);
3628 "Adding REG_EQUIV to insn %d for source of insn %d\n",
3629 INSN_UID (init_insn
),
3633 bitmap_clear (&seen_insns
);
3636 /* Scan all regs killed in an insn to see if any of them are registers
3637 only used that once. If so, see if we can replace the reference
3638 with the equivalent form. If we can, delete the initializing
3639 reference and this register will go away. If we can't replace the
3640 reference, and the initializing reference is within the same loop
3641 (or in an inner loop), then move the register initialization just
3642 before the use, so that they are in the same basic block. */
3644 combine_and_move_insns (void)
3646 bitmap cleared_regs
= BITMAP_ALLOC (NULL
);
3647 int max
= max_reg_num ();
3649 for (int regno
= FIRST_PSEUDO_REGISTER
; regno
< max
; regno
++)
3651 if (!reg_equiv
[regno
].replace
)
3654 rtx_insn
*use_insn
= 0;
3655 for (df_ref use
= DF_REG_USE_CHAIN (regno
);
3657 use
= DF_REF_NEXT_REG (use
))
3658 if (DF_REF_INSN_INFO (use
))
3660 if (DEBUG_INSN_P (DF_REF_INSN (use
)))
3662 gcc_assert (!use_insn
);
3663 use_insn
= DF_REF_INSN (use
);
3665 gcc_assert (use_insn
);
3667 /* Don't substitute into jumps. indirect_jump_optimize does
3668 this for anything we are prepared to handle. */
3669 if (JUMP_P (use_insn
))
3672 /* Also don't substitute into a conditional trap insn -- it can become
3673 an unconditional trap, and that is a flow control insn. */
3674 if (GET_CODE (PATTERN (use_insn
)) == TRAP_IF
)
3677 df_ref def
= DF_REG_DEF_CHAIN (regno
);
3678 gcc_assert (DF_REG_DEF_COUNT (regno
) == 1 && DF_REF_INSN_INFO (def
));
3679 rtx_insn
*def_insn
= DF_REF_INSN (def
);
3681 /* We may not move instructions that can throw, since that
3682 changes basic block boundaries and we are not prepared to
3683 adjust the CFG to match. */
3684 if (can_throw_internal (def_insn
))
3687 basic_block use_bb
= BLOCK_FOR_INSN (use_insn
);
3688 basic_block def_bb
= BLOCK_FOR_INSN (def_insn
);
3689 if (bb_loop_depth (use_bb
) > bb_loop_depth (def_bb
))
3692 if (asm_noperands (PATTERN (def_insn
)) < 0
3693 && validate_replace_rtx (regno_reg_rtx
[regno
],
3694 *reg_equiv
[regno
].src_p
, use_insn
))
3697 /* Append the REG_DEAD notes from def_insn. */
3698 for (rtx
*p
= ®_NOTES (def_insn
); (link
= *p
) != 0; )
3700 if (REG_NOTE_KIND (XEXP (link
, 0)) == REG_DEAD
)
3702 *p
= XEXP (link
, 1);
3703 XEXP (link
, 1) = REG_NOTES (use_insn
);
3704 REG_NOTES (use_insn
) = link
;
3707 p
= &XEXP (link
, 1);
3710 remove_death (regno
, use_insn
);
3711 SET_REG_N_REFS (regno
, 0);
3712 REG_FREQ (regno
) = 0;
3713 delete_insn (def_insn
);
3715 reg_equiv
[regno
].init_insns
= NULL
;
3716 ira_reg_equiv
[regno
].init_insns
= NULL
;
3717 bitmap_set_bit (cleared_regs
, regno
);
3720 /* Move the initialization of the register to just before
3721 USE_INSN. Update the flow information. */
3722 else if (prev_nondebug_insn (use_insn
) != def_insn
)
3726 new_insn
= emit_insn_before (PATTERN (def_insn
), use_insn
);
3727 REG_NOTES (new_insn
) = REG_NOTES (def_insn
);
3728 REG_NOTES (def_insn
) = 0;
3729 /* Rescan it to process the notes. */
3730 df_insn_rescan (new_insn
);
3732 /* Make sure this insn is recognized before reload begins,
3733 otherwise eliminate_regs_in_insn will die. */
3734 INSN_CODE (new_insn
) = INSN_CODE (def_insn
);
3736 delete_insn (def_insn
);
3738 XEXP (reg_equiv
[regno
].init_insns
, 0) = new_insn
;
3740 REG_BASIC_BLOCK (regno
) = use_bb
->index
;
3741 REG_N_CALLS_CROSSED (regno
) = 0;
3743 if (use_insn
== BB_HEAD (use_bb
))
3744 BB_HEAD (use_bb
) = new_insn
;
3746 /* We know regno dies in use_insn, but inside a loop
3747 REG_DEAD notes might be missing when def_insn was in
3748 another basic block. However, when we move def_insn into
3749 this bb we'll definitely get a REG_DEAD note and reload
3750 will see the death. It's possible that update_equiv_regs
3751 set up an equivalence referencing regno for a reg set by
3752 use_insn, when regno was seen as non-local. Now that
3753 regno is local to this block, and dies, such an
3754 equivalence is invalid. */
3755 if (find_reg_note (use_insn
, REG_EQUIV
, regno_reg_rtx
[regno
]))
3757 rtx set
= single_set (use_insn
);
3758 if (set
&& REG_P (SET_DEST (set
)))
3759 no_equiv (SET_DEST (set
), set
, NULL
);
3762 ira_reg_equiv
[regno
].init_insns
3763 = gen_rtx_INSN_LIST (VOIDmode
, new_insn
, NULL_RTX
);
3764 bitmap_set_bit (cleared_regs
, regno
);
3768 if (!bitmap_empty_p (cleared_regs
))
3772 FOR_EACH_BB_FN (bb
, cfun
)
3774 bitmap_and_compl_into (DF_LR_IN (bb
), cleared_regs
);
3775 bitmap_and_compl_into (DF_LR_OUT (bb
), cleared_regs
);
3778 bitmap_and_compl_into (DF_LIVE_IN (bb
), cleared_regs
);
3779 bitmap_and_compl_into (DF_LIVE_OUT (bb
), cleared_regs
);
3782 /* Last pass - adjust debug insns referencing cleared regs. */
3783 if (MAY_HAVE_DEBUG_INSNS
)
3784 for (rtx_insn
*insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
3785 if (DEBUG_INSN_P (insn
))
3787 rtx old_loc
= INSN_VAR_LOCATION_LOC (insn
);
3788 INSN_VAR_LOCATION_LOC (insn
)
3789 = simplify_replace_fn_rtx (old_loc
, NULL_RTX
,
3790 adjust_cleared_regs
,
3791 (void *) cleared_regs
);
3792 if (old_loc
!= INSN_VAR_LOCATION_LOC (insn
))
3793 df_insn_rescan (insn
);
3797 BITMAP_FREE (cleared_regs
);
3800 /* A pass over indirect jumps, converting simple cases to direct jumps.
3801 Combine does this optimization too, but only within a basic block. */
3803 indirect_jump_optimize (void)
3806 bool rebuild_p
= false;
3808 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
3810 rtx_insn
*insn
= BB_END (bb
);
3812 || find_reg_note (insn
, REG_NON_LOCAL_GOTO
, NULL_RTX
))
3815 rtx x
= pc_set (insn
);
3816 if (!x
|| !REG_P (SET_SRC (x
)))
3819 int regno
= REGNO (SET_SRC (x
));
3820 if (DF_REG_DEF_COUNT (regno
) == 1)
3822 df_ref def
= DF_REG_DEF_CHAIN (regno
);
3823 if (!DF_REF_IS_ARTIFICIAL (def
))
3825 rtx_insn
*def_insn
= DF_REF_INSN (def
);
3827 rtx set
= single_set (def_insn
);
3828 if (set
&& GET_CODE (SET_SRC (set
)) == LABEL_REF
)
3829 lab
= SET_SRC (set
);
3832 rtx eqnote
= find_reg_note (def_insn
, REG_EQUAL
, NULL_RTX
);
3833 if (eqnote
&& GET_CODE (XEXP (eqnote
, 0)) == LABEL_REF
)
3834 lab
= XEXP (eqnote
, 0);
3836 if (lab
&& validate_replace_rtx (SET_SRC (x
), lab
, insn
))
3844 timevar_push (TV_JUMP
);
3845 rebuild_jump_labels (get_insns ());
3846 if (purge_all_dead_edges ())
3847 delete_unreachable_blocks ();
3848 timevar_pop (TV_JUMP
);
3852 /* Set up fields memory, constant, and invariant from init_insns in
3853 the structures of array ira_reg_equiv. */
3855 setup_reg_equiv (void)
3858 rtx_insn_list
*elem
, *prev_elem
, *next_elem
;
3862 for (i
= FIRST_PSEUDO_REGISTER
; i
< ira_reg_equiv_len
; i
++)
3863 for (prev_elem
= NULL
, elem
= ira_reg_equiv
[i
].init_insns
;
3865 prev_elem
= elem
, elem
= next_elem
)
3867 next_elem
= elem
->next ();
3868 insn
= elem
->insn ();
3869 set
= single_set (insn
);
3871 /* Init insns can set up equivalence when the reg is a destination or
3872 a source (in this case the destination is memory). */
3873 if (set
!= 0 && (REG_P (SET_DEST (set
)) || REG_P (SET_SRC (set
))))
3875 if ((x
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
)) != NULL
)
3878 if (REG_P (SET_DEST (set
))
3879 && REGNO (SET_DEST (set
)) == (unsigned int) i
3880 && ! rtx_equal_p (SET_SRC (set
), x
) && MEM_P (x
))
3882 /* This insn reporting the equivalence but
3883 actually not setting it. Remove it from the
3885 if (prev_elem
== NULL
)
3886 ira_reg_equiv
[i
].init_insns
= next_elem
;
3888 XEXP (prev_elem
, 1) = next_elem
;
3892 else if (REG_P (SET_DEST (set
))
3893 && REGNO (SET_DEST (set
)) == (unsigned int) i
)
3897 gcc_assert (REG_P (SET_SRC (set
))
3898 && REGNO (SET_SRC (set
)) == (unsigned int) i
);
3901 if (! function_invariant_p (x
)
3903 /* A function invariant is often CONSTANT_P but may
3904 include a register. We promise to only pass
3905 CONSTANT_P objects to LEGITIMATE_PIC_OPERAND_P. */
3906 || (CONSTANT_P (x
) && LEGITIMATE_PIC_OPERAND_P (x
)))
3908 /* It can happen that a REG_EQUIV note contains a MEM
3909 that is not a legitimate memory operand. As later
3910 stages of reload assume that all addresses found in
3911 the lra_regno_equiv_* arrays were originally
3912 legitimate, we ignore such REG_EQUIV notes. */
3913 if (memory_operand (x
, VOIDmode
))
3915 ira_reg_equiv
[i
].defined_p
= true;
3916 ira_reg_equiv
[i
].memory
= x
;
3919 else if (function_invariant_p (x
))
3923 mode
= GET_MODE (SET_DEST (set
));
3924 if (GET_CODE (x
) == PLUS
3925 || x
== frame_pointer_rtx
|| x
== arg_pointer_rtx
)
3926 /* This is PLUS of frame pointer and a constant,
3928 ira_reg_equiv
[i
].invariant
= x
;
3929 else if (targetm
.legitimate_constant_p (mode
, x
))
3930 ira_reg_equiv
[i
].constant
= x
;
3933 ira_reg_equiv
[i
].memory
= force_const_mem (mode
, x
);
3934 if (ira_reg_equiv
[i
].memory
== NULL_RTX
)
3936 ira_reg_equiv
[i
].defined_p
= false;
3937 ira_reg_equiv
[i
].init_insns
= NULL
;
3941 ira_reg_equiv
[i
].defined_p
= true;
3946 ira_reg_equiv
[i
].defined_p
= false;
3947 ira_reg_equiv
[i
].init_insns
= NULL
;
3954 /* Print chain C to FILE. */
3956 print_insn_chain (FILE *file
, struct insn_chain
*c
)
3958 fprintf (file
, "insn=%d, ", INSN_UID (c
->insn
));
3959 bitmap_print (file
, &c
->live_throughout
, "live_throughout: ", ", ");
3960 bitmap_print (file
, &c
->dead_or_set
, "dead_or_set: ", "\n");
3964 /* Print all reload_insn_chains to FILE. */
3966 print_insn_chains (FILE *file
)
3968 struct insn_chain
*c
;
3969 for (c
= reload_insn_chain
; c
; c
= c
->next
)
3970 print_insn_chain (file
, c
);
3973 /* Return true if pseudo REGNO should be added to set live_throughout
3974 or dead_or_set of the insn chains for reload consideration. */
3976 pseudo_for_reload_consideration_p (int regno
)
3978 /* Consider spilled pseudos too for IRA because they still have a
3979 chance to get hard-registers in the reload when IRA is used. */
3980 return (reg_renumber
[regno
] >= 0 || ira_conflicts_p
);
3983 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
3984 REG to the number of nregs, and INIT_VALUE to get the
3985 initialization. ALLOCNUM need not be the regno of REG. */
3987 init_live_subregs (bool init_value
, sbitmap
*live_subregs
,
3988 bitmap live_subregs_used
, int allocnum
, rtx reg
)
3990 unsigned int regno
= REGNO (SUBREG_REG (reg
));
3991 int size
= GET_MODE_SIZE (GET_MODE (regno_reg_rtx
[regno
]));
3993 gcc_assert (size
> 0);
3995 /* Been there, done that. */
3996 if (bitmap_bit_p (live_subregs_used
, allocnum
))
3999 /* Create a new one. */
4000 if (live_subregs
[allocnum
] == NULL
)
4001 live_subregs
[allocnum
] = sbitmap_alloc (size
);
4003 /* If the entire reg was live before blasting into subregs, we need
4004 to init all of the subregs to ones else init to 0. */
4006 bitmap_ones (live_subregs
[allocnum
]);
4008 bitmap_clear (live_subregs
[allocnum
]);
4010 bitmap_set_bit (live_subregs_used
, allocnum
);
4013 /* Walk the insns of the current function and build reload_insn_chain,
4014 and record register life information. */
4016 build_insn_chain (void)
4019 struct insn_chain
**p
= &reload_insn_chain
;
4021 struct insn_chain
*c
= NULL
;
4022 struct insn_chain
*next
= NULL
;
4023 bitmap live_relevant_regs
= BITMAP_ALLOC (NULL
);
4024 bitmap elim_regset
= BITMAP_ALLOC (NULL
);
4025 /* live_subregs is a vector used to keep accurate information about
4026 which hardregs are live in multiword pseudos. live_subregs and
4027 live_subregs_used are indexed by pseudo number. The live_subreg
4028 entry for a particular pseudo is only used if the corresponding
4029 element is non zero in live_subregs_used. The sbitmap size of
4030 live_subreg[allocno] is number of bytes that the pseudo can
4032 sbitmap
*live_subregs
= XCNEWVEC (sbitmap
, max_regno
);
4033 bitmap live_subregs_used
= BITMAP_ALLOC (NULL
);
4035 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
4036 if (TEST_HARD_REG_BIT (eliminable_regset
, i
))
4037 bitmap_set_bit (elim_regset
, i
);
4038 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
4043 CLEAR_REG_SET (live_relevant_regs
);
4044 bitmap_clear (live_subregs_used
);
4046 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb
), 0, i
, bi
)
4048 if (i
>= FIRST_PSEUDO_REGISTER
)
4050 bitmap_set_bit (live_relevant_regs
, i
);
4053 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb
),
4054 FIRST_PSEUDO_REGISTER
, i
, bi
)
4056 if (pseudo_for_reload_consideration_p (i
))
4057 bitmap_set_bit (live_relevant_regs
, i
);
4060 FOR_BB_INSNS_REVERSE (bb
, insn
)
4062 if (!NOTE_P (insn
) && !BARRIER_P (insn
))
4064 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
4067 c
= new_insn_chain ();
4074 c
->block
= bb
->index
;
4076 if (NONDEBUG_INSN_P (insn
))
4077 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
4079 unsigned int regno
= DF_REF_REGNO (def
);
4081 /* Ignore may clobbers because these are generated
4082 from calls. However, every other kind of def is
4083 added to dead_or_set. */
4084 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
4086 if (regno
< FIRST_PSEUDO_REGISTER
)
4088 if (!fixed_regs
[regno
])
4089 bitmap_set_bit (&c
->dead_or_set
, regno
);
4091 else if (pseudo_for_reload_consideration_p (regno
))
4092 bitmap_set_bit (&c
->dead_or_set
, regno
);
4095 if ((regno
< FIRST_PSEUDO_REGISTER
4096 || reg_renumber
[regno
] >= 0
4098 && (!DF_REF_FLAGS_IS_SET (def
, DF_REF_CONDITIONAL
)))
4100 rtx reg
= DF_REF_REG (def
);
4102 /* We can model subregs, but not if they are
4103 wrapped in ZERO_EXTRACTS. */
4104 if (GET_CODE (reg
) == SUBREG
4105 && !DF_REF_FLAGS_IS_SET (def
, DF_REF_ZERO_EXTRACT
))
4107 unsigned int start
= SUBREG_BYTE (reg
);
4108 unsigned int last
= start
4109 + GET_MODE_SIZE (GET_MODE (reg
));
4112 (bitmap_bit_p (live_relevant_regs
, regno
),
4113 live_subregs
, live_subregs_used
, regno
, reg
);
4115 if (!DF_REF_FLAGS_IS_SET
4116 (def
, DF_REF_STRICT_LOW_PART
))
4118 /* Expand the range to cover entire words.
4119 Bytes added here are "don't care". */
4121 = start
/ UNITS_PER_WORD
* UNITS_PER_WORD
;
4122 last
= ((last
+ UNITS_PER_WORD
- 1)
4123 / UNITS_PER_WORD
* UNITS_PER_WORD
);
4126 /* Ignore the paradoxical bits. */
4127 if (last
> SBITMAP_SIZE (live_subregs
[regno
]))
4128 last
= SBITMAP_SIZE (live_subregs
[regno
]);
4130 while (start
< last
)
4132 bitmap_clear_bit (live_subregs
[regno
], start
);
4136 if (bitmap_empty_p (live_subregs
[regno
]))
4138 bitmap_clear_bit (live_subregs_used
, regno
);
4139 bitmap_clear_bit (live_relevant_regs
, regno
);
4142 /* Set live_relevant_regs here because
4143 that bit has to be true to get us to
4144 look at the live_subregs fields. */
4145 bitmap_set_bit (live_relevant_regs
, regno
);
4149 /* DF_REF_PARTIAL is generated for
4150 subregs, STRICT_LOW_PART, and
4151 ZERO_EXTRACT. We handle the subreg
4152 case above so here we have to keep from
4153 modeling the def as a killing def. */
4154 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
))
4156 bitmap_clear_bit (live_subregs_used
, regno
);
4157 bitmap_clear_bit (live_relevant_regs
, regno
);
4163 bitmap_and_compl_into (live_relevant_regs
, elim_regset
);
4164 bitmap_copy (&c
->live_throughout
, live_relevant_regs
);
4166 if (NONDEBUG_INSN_P (insn
))
4167 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
4169 unsigned int regno
= DF_REF_REGNO (use
);
4170 rtx reg
= DF_REF_REG (use
);
4172 /* DF_REF_READ_WRITE on a use means that this use
4173 is fabricated from a def that is a partial set
4174 to a multiword reg. Here, we only model the
4175 subreg case that is not wrapped in ZERO_EXTRACT
4176 precisely so we do not need to look at the
4178 if (DF_REF_FLAGS_IS_SET (use
, DF_REF_READ_WRITE
)
4179 && !DF_REF_FLAGS_IS_SET (use
, DF_REF_ZERO_EXTRACT
)
4180 && DF_REF_FLAGS_IS_SET (use
, DF_REF_SUBREG
))
4183 /* Add the last use of each var to dead_or_set. */
4184 if (!bitmap_bit_p (live_relevant_regs
, regno
))
4186 if (regno
< FIRST_PSEUDO_REGISTER
)
4188 if (!fixed_regs
[regno
])
4189 bitmap_set_bit (&c
->dead_or_set
, regno
);
4191 else if (pseudo_for_reload_consideration_p (regno
))
4192 bitmap_set_bit (&c
->dead_or_set
, regno
);
4195 if (regno
< FIRST_PSEUDO_REGISTER
4196 || pseudo_for_reload_consideration_p (regno
))
4198 if (GET_CODE (reg
) == SUBREG
4199 && !DF_REF_FLAGS_IS_SET (use
,
4201 | DF_REF_ZERO_EXTRACT
))
4203 unsigned int start
= SUBREG_BYTE (reg
);
4204 unsigned int last
= start
4205 + GET_MODE_SIZE (GET_MODE (reg
));
4208 (bitmap_bit_p (live_relevant_regs
, regno
),
4209 live_subregs
, live_subregs_used
, regno
, reg
);
4211 /* Ignore the paradoxical bits. */
4212 if (last
> SBITMAP_SIZE (live_subregs
[regno
]))
4213 last
= SBITMAP_SIZE (live_subregs
[regno
]);
4215 while (start
< last
)
4217 bitmap_set_bit (live_subregs
[regno
], start
);
4222 /* Resetting the live_subregs_used is
4223 effectively saying do not use the subregs
4224 because we are reading the whole
4226 bitmap_clear_bit (live_subregs_used
, regno
);
4227 bitmap_set_bit (live_relevant_regs
, regno
);
4233 /* FIXME!! The following code is a disaster. Reload needs to see the
4234 labels and jump tables that are just hanging out in between
4235 the basic blocks. See pr33676. */
4236 insn
= BB_HEAD (bb
);
4238 /* Skip over the barriers and cruft. */
4239 while (insn
&& (BARRIER_P (insn
) || NOTE_P (insn
)
4240 || BLOCK_FOR_INSN (insn
) == bb
))
4241 insn
= PREV_INSN (insn
);
4243 /* While we add anything except barriers and notes, the focus is
4244 to get the labels and jump tables into the
4245 reload_insn_chain. */
4248 if (!NOTE_P (insn
) && !BARRIER_P (insn
))
4250 if (BLOCK_FOR_INSN (insn
))
4253 c
= new_insn_chain ();
4259 /* The block makes no sense here, but it is what the old
4261 c
->block
= bb
->index
;
4263 bitmap_copy (&c
->live_throughout
, live_relevant_regs
);
4265 insn
= PREV_INSN (insn
);
4269 reload_insn_chain
= c
;
4272 for (i
= 0; i
< (unsigned int) max_regno
; i
++)
4273 if (live_subregs
[i
] != NULL
)
4274 sbitmap_free (live_subregs
[i
]);
4275 free (live_subregs
);
4276 BITMAP_FREE (live_subregs_used
);
4277 BITMAP_FREE (live_relevant_regs
);
4278 BITMAP_FREE (elim_regset
);
4281 print_insn_chains (dump_file
);
4284 /* Examine the rtx found in *LOC, which is read or written to as determined
4285 by TYPE. Return false if we find a reason why an insn containing this
4286 rtx should not be moved (such as accesses to non-constant memory), true
4289 rtx_moveable_p (rtx
*loc
, enum op_type type
)
4293 enum rtx_code code
= GET_CODE (x
);
4296 code
= GET_CODE (x
);
4306 return type
== OP_IN
;
4312 if (x
== frame_pointer_rtx
)
4314 if (HARD_REGISTER_P (x
))
4320 if (type
== OP_IN
&& MEM_READONLY_P (x
))
4321 return rtx_moveable_p (&XEXP (x
, 0), OP_IN
);
4325 return (rtx_moveable_p (&SET_SRC (x
), OP_IN
)
4326 && rtx_moveable_p (&SET_DEST (x
), OP_OUT
));
4328 case STRICT_LOW_PART
:
4329 return rtx_moveable_p (&XEXP (x
, 0), OP_OUT
);
4333 return (rtx_moveable_p (&XEXP (x
, 0), type
)
4334 && rtx_moveable_p (&XEXP (x
, 1), OP_IN
)
4335 && rtx_moveable_p (&XEXP (x
, 2), OP_IN
));
4338 return rtx_moveable_p (&SET_DEST (x
), OP_OUT
);
4340 case UNSPEC_VOLATILE
:
4341 /* It is a bad idea to consider insns with such rtl
4342 as moveable ones. The insn scheduler also considers them as barrier
4350 fmt
= GET_RTX_FORMAT (code
);
4351 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
4355 if (!rtx_moveable_p (&XEXP (x
, i
), type
))
4358 else if (fmt
[i
] == 'E')
4359 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
4361 if (!rtx_moveable_p (&XVECEXP (x
, i
, j
), type
))
4368 /* A wrapper around dominated_by_p, which uses the information in UID_LUID
4369 to give dominance relationships between two insns I1 and I2. */
4371 insn_dominated_by_p (rtx i1
, rtx i2
, int *uid_luid
)
4373 basic_block bb1
= BLOCK_FOR_INSN (i1
);
4374 basic_block bb2
= BLOCK_FOR_INSN (i2
);
4377 return uid_luid
[INSN_UID (i2
)] < uid_luid
[INSN_UID (i1
)];
4378 return dominated_by_p (CDI_DOMINATORS
, bb1
, bb2
);
4381 /* Record the range of register numbers added by find_moveable_pseudos. */
4382 int first_moveable_pseudo
, last_moveable_pseudo
;
4384 /* These two vectors hold data for every register added by
4385 find_movable_pseudos, with index 0 holding data for the
4386 first_moveable_pseudo. */
4387 /* The original home register. */
4388 static vec
<rtx
> pseudo_replaced_reg
;
4390 /* Look for instances where we have an instruction that is known to increase
4391 register pressure, and whose result is not used immediately. If it is
4392 possible to move the instruction downwards to just before its first use,
4393 split its lifetime into two ranges. We create a new pseudo to compute the
4394 value, and emit a move instruction just before the first use. If, after
4395 register allocation, the new pseudo remains unallocated, the function
4396 move_unallocated_pseudos then deletes the move instruction and places
4397 the computation just before the first use.
4399 Such a move is safe and profitable if all the input registers remain live
4400 and unchanged between the original computation and its first use. In such
4401 a situation, the computation is known to increase register pressure, and
4402 moving it is known to at least not worsen it.
4404 We restrict moves to only those cases where a register remains unallocated,
4405 in order to avoid interfering too much with the instruction schedule. As
4406 an exception, we may move insns which only modify their input register
4407 (typically induction variables), as this increases the freedom for our
4408 intended transformation, and does not limit the second instruction
4412 find_moveable_pseudos (void)
4415 int max_regs
= max_reg_num ();
4416 int max_uid
= get_max_uid ();
4418 int *uid_luid
= XNEWVEC (int, max_uid
);
4419 rtx_insn
**closest_uses
= XNEWVEC (rtx_insn
*, max_regs
);
4420 /* A set of registers which are live but not modified throughout a block. */
4421 bitmap_head
*bb_transp_live
= XNEWVEC (bitmap_head
,
4422 last_basic_block_for_fn (cfun
));
4423 /* A set of registers which only exist in a given basic block. */
4424 bitmap_head
*bb_local
= XNEWVEC (bitmap_head
,
4425 last_basic_block_for_fn (cfun
));
4426 /* A set of registers which are set once, in an instruction that can be
4427 moved freely downwards, but are otherwise transparent to a block. */
4428 bitmap_head
*bb_moveable_reg_sets
= XNEWVEC (bitmap_head
,
4429 last_basic_block_for_fn (cfun
));
4430 bitmap_head live
, used
, set
, interesting
, unusable_as_input
;
4432 bitmap_initialize (&interesting
, 0);
4434 first_moveable_pseudo
= max_regs
;
4435 pseudo_replaced_reg
.release ();
4436 pseudo_replaced_reg
.safe_grow_cleared (max_regs
);
4439 calculate_dominance_info (CDI_DOMINATORS
);
4442 bitmap_initialize (&live
, 0);
4443 bitmap_initialize (&used
, 0);
4444 bitmap_initialize (&set
, 0);
4445 bitmap_initialize (&unusable_as_input
, 0);
4446 FOR_EACH_BB_FN (bb
, cfun
)
4449 bitmap transp
= bb_transp_live
+ bb
->index
;
4450 bitmap moveable
= bb_moveable_reg_sets
+ bb
->index
;
4451 bitmap local
= bb_local
+ bb
->index
;
4453 bitmap_initialize (local
, 0);
4454 bitmap_initialize (transp
, 0);
4455 bitmap_initialize (moveable
, 0);
4456 bitmap_copy (&live
, df_get_live_out (bb
));
4457 bitmap_and_into (&live
, df_get_live_in (bb
));
4458 bitmap_copy (transp
, &live
);
4459 bitmap_clear (moveable
);
4460 bitmap_clear (&live
);
4461 bitmap_clear (&used
);
4462 bitmap_clear (&set
);
4463 FOR_BB_INSNS (bb
, insn
)
4464 if (NONDEBUG_INSN_P (insn
))
4466 df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
4469 uid_luid
[INSN_UID (insn
)] = i
++;
4471 def
= df_single_def (insn_info
);
4472 use
= df_single_use (insn_info
);
4475 && DF_REF_REGNO (use
) == DF_REF_REGNO (def
)
4476 && !bitmap_bit_p (&set
, DF_REF_REGNO (use
))
4477 && rtx_moveable_p (&PATTERN (insn
), OP_IN
))
4479 unsigned regno
= DF_REF_REGNO (use
);
4480 bitmap_set_bit (moveable
, regno
);
4481 bitmap_set_bit (&set
, regno
);
4482 bitmap_set_bit (&used
, regno
);
4483 bitmap_clear_bit (transp
, regno
);
4486 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
4488 unsigned regno
= DF_REF_REGNO (use
);
4489 bitmap_set_bit (&used
, regno
);
4490 if (bitmap_clear_bit (moveable
, regno
))
4491 bitmap_clear_bit (transp
, regno
);
4494 FOR_EACH_INSN_INFO_DEF (def
, insn_info
)
4496 unsigned regno
= DF_REF_REGNO (def
);
4497 bitmap_set_bit (&set
, regno
);
4498 bitmap_clear_bit (transp
, regno
);
4499 bitmap_clear_bit (moveable
, regno
);
4504 bitmap_clear (&live
);
4505 bitmap_clear (&used
);
4506 bitmap_clear (&set
);
4508 FOR_EACH_BB_FN (bb
, cfun
)
4510 bitmap local
= bb_local
+ bb
->index
;
4513 FOR_BB_INSNS (bb
, insn
)
4514 if (NONDEBUG_INSN_P (insn
))
4516 df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
4518 rtx closest_use
, note
;
4521 bool all_dominated
, all_local
;
4524 def
= df_single_def (insn_info
);
4525 /* There must be exactly one def in this insn. */
4526 if (!def
|| !single_set (insn
))
4528 /* This must be the only definition of the reg. We also limit
4529 which modes we deal with so that we can assume we can generate
4530 move instructions. */
4531 regno
= DF_REF_REGNO (def
);
4532 mode
= GET_MODE (DF_REF_REG (def
));
4533 if (DF_REG_DEF_COUNT (regno
) != 1
4534 || !DF_REF_INSN_INFO (def
)
4535 || HARD_REGISTER_NUM_P (regno
)
4536 || DF_REG_EQ_USE_COUNT (regno
) > 0
4537 || (!INTEGRAL_MODE_P (mode
) && !FLOAT_MODE_P (mode
)))
4539 def_insn
= DF_REF_INSN (def
);
4541 for (note
= REG_NOTES (def_insn
); note
; note
= XEXP (note
, 1))
4542 if (REG_NOTE_KIND (note
) == REG_EQUIV
&& MEM_P (XEXP (note
, 0)))
4548 fprintf (dump_file
, "Ignoring reg %d, has equiv memory\n",
4550 bitmap_set_bit (&unusable_as_input
, regno
);
4554 use
= DF_REG_USE_CHAIN (regno
);
4555 all_dominated
= true;
4557 closest_use
= NULL_RTX
;
4558 for (; use
; use
= DF_REF_NEXT_REG (use
))
4561 if (!DF_REF_INSN_INFO (use
))
4563 all_dominated
= false;
4567 insn
= DF_REF_INSN (use
);
4568 if (DEBUG_INSN_P (insn
))
4570 if (BLOCK_FOR_INSN (insn
) != BLOCK_FOR_INSN (def_insn
))
4572 if (!insn_dominated_by_p (insn
, def_insn
, uid_luid
))
4573 all_dominated
= false;
4574 if (closest_use
!= insn
&& closest_use
!= const0_rtx
)
4576 if (closest_use
== NULL_RTX
)
4578 else if (insn_dominated_by_p (closest_use
, insn
, uid_luid
))
4580 else if (!insn_dominated_by_p (insn
, closest_use
, uid_luid
))
4581 closest_use
= const0_rtx
;
4587 fprintf (dump_file
, "Reg %d not all uses dominated by set\n",
4592 bitmap_set_bit (local
, regno
);
4593 if (closest_use
== const0_rtx
|| closest_use
== NULL
4594 || next_nonnote_nondebug_insn (def_insn
) == closest_use
)
4597 fprintf (dump_file
, "Reg %d uninteresting%s\n", regno
,
4598 closest_use
== const0_rtx
|| closest_use
== NULL
4599 ? " (no unique first use)" : "");
4602 if (HAVE_cc0
&& reg_referenced_p (cc0_rtx
, PATTERN (closest_use
)))
4605 fprintf (dump_file
, "Reg %d: closest user uses cc0\n",
4610 bitmap_set_bit (&interesting
, regno
);
4611 /* If we get here, we know closest_use is a non-NULL insn
4612 (as opposed to const_0_rtx). */
4613 closest_uses
[regno
] = as_a
<rtx_insn
*> (closest_use
);
4615 if (dump_file
&& (all_local
|| all_dominated
))
4617 fprintf (dump_file
, "Reg %u:", regno
);
4619 fprintf (dump_file
, " local to bb %d", bb
->index
);
4621 fprintf (dump_file
, " def dominates all uses");
4622 if (closest_use
!= const0_rtx
)
4623 fprintf (dump_file
, " has unique first use");
4624 fputs ("\n", dump_file
);
4629 EXECUTE_IF_SET_IN_BITMAP (&interesting
, 0, i
, bi
)
4631 df_ref def
= DF_REG_DEF_CHAIN (i
);
4632 rtx_insn
*def_insn
= DF_REF_INSN (def
);
4633 basic_block def_block
= BLOCK_FOR_INSN (def_insn
);
4634 bitmap def_bb_local
= bb_local
+ def_block
->index
;
4635 bitmap def_bb_moveable
= bb_moveable_reg_sets
+ def_block
->index
;
4636 bitmap def_bb_transp
= bb_transp_live
+ def_block
->index
;
4637 bool local_to_bb_p
= bitmap_bit_p (def_bb_local
, i
);
4638 rtx_insn
*use_insn
= closest_uses
[i
];
4641 bool all_transp
= true;
4643 if (!REG_P (DF_REF_REG (def
)))
4649 fprintf (dump_file
, "Reg %u not local to one basic block\n",
4653 if (reg_equiv_init (i
) != NULL_RTX
)
4656 fprintf (dump_file
, "Ignoring reg %u with equiv init insn\n",
4660 if (!rtx_moveable_p (&PATTERN (def_insn
), OP_IN
))
4663 fprintf (dump_file
, "Found def insn %d for %d to be not moveable\n",
4664 INSN_UID (def_insn
), i
);
4668 fprintf (dump_file
, "Examining insn %d, def for %d\n",
4669 INSN_UID (def_insn
), i
);
4670 FOR_EACH_INSN_USE (use
, def_insn
)
4672 unsigned regno
= DF_REF_REGNO (use
);
4673 if (bitmap_bit_p (&unusable_as_input
, regno
))
4677 fprintf (dump_file
, " found unusable input reg %u.\n", regno
);
4680 if (!bitmap_bit_p (def_bb_transp
, regno
))
4682 if (bitmap_bit_p (def_bb_moveable
, regno
)
4683 && !control_flow_insn_p (use_insn
)
4684 && (!HAVE_cc0
|| !sets_cc0_p (use_insn
)))
4686 if (modified_between_p (DF_REF_REG (use
), def_insn
, use_insn
))
4688 rtx_insn
*x
= NEXT_INSN (def_insn
);
4689 while (!modified_in_p (DF_REF_REG (use
), x
))
4691 gcc_assert (x
!= use_insn
);
4695 fprintf (dump_file
, " input reg %u modified but insn %d moveable\n",
4696 regno
, INSN_UID (x
));
4697 emit_insn_after (PATTERN (x
), use_insn
);
4698 set_insn_deleted (x
);
4703 fprintf (dump_file
, " input reg %u modified between def and use\n",
4714 if (!dbg_cnt (ira_move
))
4717 fprintf (dump_file
, " all ok%s\n", all_transp
? " and transp" : "");
4721 rtx def_reg
= DF_REF_REG (def
);
4722 rtx newreg
= ira_create_new_reg (def_reg
);
4723 if (validate_change (def_insn
, DF_REF_REAL_LOC (def
), newreg
, 0))
4725 unsigned nregno
= REGNO (newreg
);
4726 emit_insn_before (gen_move_insn (def_reg
, newreg
), use_insn
);
4728 pseudo_replaced_reg
[nregno
] = def_reg
;
4733 FOR_EACH_BB_FN (bb
, cfun
)
4735 bitmap_clear (bb_local
+ bb
->index
);
4736 bitmap_clear (bb_transp_live
+ bb
->index
);
4737 bitmap_clear (bb_moveable_reg_sets
+ bb
->index
);
4739 bitmap_clear (&interesting
);
4740 bitmap_clear (&unusable_as_input
);
4742 free (closest_uses
);
4744 free (bb_transp_live
);
4745 free (bb_moveable_reg_sets
);
4747 last_moveable_pseudo
= max_reg_num ();
4749 fix_reg_equiv_init ();
4751 regstat_free_n_sets_and_refs ();
4753 regstat_init_n_sets_and_refs ();
4754 regstat_compute_ri ();
4755 free_dominance_info (CDI_DOMINATORS
);
4758 /* If SET pattern SET is an assignment from a hard register to a pseudo which
4759 is live at CALL_DOM (if non-NULL, otherwise this check is omitted), return
4760 the destination. Otherwise return NULL. */
4763 interesting_dest_for_shprep_1 (rtx set
, basic_block call_dom
)
4765 rtx src
= SET_SRC (set
);
4766 rtx dest
= SET_DEST (set
);
4767 if (!REG_P (src
) || !HARD_REGISTER_P (src
)
4768 || !REG_P (dest
) || HARD_REGISTER_P (dest
)
4769 || (call_dom
&& !bitmap_bit_p (df_get_live_in (call_dom
), REGNO (dest
))))
4774 /* If insn is interesting for parameter range-splitting shrink-wrapping
4775 preparation, i.e. it is a single set from a hard register to a pseudo, which
4776 is live at CALL_DOM (if non-NULL, otherwise this check is omitted), or a
4777 parallel statement with only one such statement, return the destination.
4778 Otherwise return NULL. */
4781 interesting_dest_for_shprep (rtx_insn
*insn
, basic_block call_dom
)
4785 rtx pat
= PATTERN (insn
);
4786 if (GET_CODE (pat
) == SET
)
4787 return interesting_dest_for_shprep_1 (pat
, call_dom
);
4789 if (GET_CODE (pat
) != PARALLEL
)
4792 for (int i
= 0; i
< XVECLEN (pat
, 0); i
++)
4794 rtx sub
= XVECEXP (pat
, 0, i
);
4795 if (GET_CODE (sub
) == USE
|| GET_CODE (sub
) == CLOBBER
)
4797 if (GET_CODE (sub
) != SET
4798 || side_effects_p (sub
))
4800 rtx dest
= interesting_dest_for_shprep_1 (sub
, call_dom
);
4809 /* Split live ranges of pseudos that are loaded from hard registers in the
4810 first BB in a BB that dominates all non-sibling call if such a BB can be
4811 found and is not in a loop. Return true if the function has made any
4815 split_live_ranges_for_shrink_wrap (void)
4817 basic_block bb
, call_dom
= NULL
;
4818 basic_block first
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
4819 rtx_insn
*insn
, *last_interesting_insn
= NULL
;
4820 bitmap_head need_new
, reachable
;
4821 vec
<basic_block
> queue
;
4823 if (!SHRINK_WRAPPING_ENABLED
)
4826 bitmap_initialize (&need_new
, 0);
4827 bitmap_initialize (&reachable
, 0);
4828 queue
.create (n_basic_blocks_for_fn (cfun
));
4830 FOR_EACH_BB_FN (bb
, cfun
)
4831 FOR_BB_INSNS (bb
, insn
)
4832 if (CALL_P (insn
) && !SIBLING_CALL_P (insn
))
4836 bitmap_clear (&need_new
);
4837 bitmap_clear (&reachable
);
4842 bitmap_set_bit (&need_new
, bb
->index
);
4843 bitmap_set_bit (&reachable
, bb
->index
);
4844 queue
.quick_push (bb
);
4848 if (queue
.is_empty ())
4850 bitmap_clear (&need_new
);
4851 bitmap_clear (&reachable
);
4856 while (!queue
.is_empty ())
4862 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4863 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
4864 && bitmap_set_bit (&reachable
, e
->dest
->index
))
4865 queue
.quick_push (e
->dest
);
4869 FOR_BB_INSNS (first
, insn
)
4871 rtx dest
= interesting_dest_for_shprep (insn
, NULL
);
4875 if (DF_REG_DEF_COUNT (REGNO (dest
)) > 1)
4877 bitmap_clear (&need_new
);
4878 bitmap_clear (&reachable
);
4882 for (df_ref use
= DF_REG_USE_CHAIN (REGNO(dest
));
4884 use
= DF_REF_NEXT_REG (use
))
4886 int ubbi
= DF_REF_BB (use
)->index
;
4887 if (bitmap_bit_p (&reachable
, ubbi
))
4888 bitmap_set_bit (&need_new
, ubbi
);
4890 last_interesting_insn
= insn
;
4893 bitmap_clear (&reachable
);
4894 if (!last_interesting_insn
)
4896 bitmap_clear (&need_new
);
4900 call_dom
= nearest_common_dominator_for_set (CDI_DOMINATORS
, &need_new
);
4901 bitmap_clear (&need_new
);
4902 if (call_dom
== first
)
4905 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
4906 while (bb_loop_depth (call_dom
) > 0)
4907 call_dom
= get_immediate_dominator (CDI_DOMINATORS
, call_dom
);
4908 loop_optimizer_finalize ();
4910 if (call_dom
== first
)
4913 calculate_dominance_info (CDI_POST_DOMINATORS
);
4914 if (dominated_by_p (CDI_POST_DOMINATORS
, first
, call_dom
))
4916 free_dominance_info (CDI_POST_DOMINATORS
);
4919 free_dominance_info (CDI_POST_DOMINATORS
);
4922 fprintf (dump_file
, "Will split live ranges of parameters at BB %i\n",
4926 FOR_BB_INSNS (first
, insn
)
4928 rtx dest
= interesting_dest_for_shprep (insn
, call_dom
);
4929 if (!dest
|| dest
== pic_offset_table_rtx
)
4932 rtx newreg
= NULL_RTX
;
4934 for (use
= DF_REG_USE_CHAIN (REGNO (dest
)); use
; use
= next
)
4936 rtx_insn
*uin
= DF_REF_INSN (use
);
4937 next
= DF_REF_NEXT_REG (use
);
4939 basic_block ubb
= BLOCK_FOR_INSN (uin
);
4941 || dominated_by_p (CDI_DOMINATORS
, ubb
, call_dom
))
4944 newreg
= ira_create_new_reg (dest
);
4945 validate_change (uin
, DF_REF_REAL_LOC (use
), newreg
, true);
4951 rtx_insn
*new_move
= gen_move_insn (newreg
, dest
);
4952 emit_insn_after (new_move
, bb_note (call_dom
));
4955 fprintf (dump_file
, "Split live-range of register ");
4956 print_rtl_single (dump_file
, dest
);
4961 if (insn
== last_interesting_insn
)
4964 apply_change_group ();
4968 /* Perform the second half of the transformation started in
4969 find_moveable_pseudos. We look for instances where the newly introduced
4970 pseudo remains unallocated, and remove it by moving the definition to
4971 just before its use, replacing the move instruction generated by
4972 find_moveable_pseudos. */
4974 move_unallocated_pseudos (void)
4977 for (i
= first_moveable_pseudo
; i
< last_moveable_pseudo
; i
++)
4978 if (reg_renumber
[i
] < 0)
4980 int idx
= i
- first_moveable_pseudo
;
4981 rtx other_reg
= pseudo_replaced_reg
[idx
];
4982 rtx_insn
*def_insn
= DF_REF_INSN (DF_REG_DEF_CHAIN (i
));
4983 /* The use must follow all definitions of OTHER_REG, so we can
4984 insert the new definition immediately after any of them. */
4985 df_ref other_def
= DF_REG_DEF_CHAIN (REGNO (other_reg
));
4986 rtx_insn
*move_insn
= DF_REF_INSN (other_def
);
4987 rtx_insn
*newinsn
= emit_insn_after (PATTERN (def_insn
), move_insn
);
4992 fprintf (dump_file
, "moving def of %d (insn %d now) ",
4993 REGNO (other_reg
), INSN_UID (def_insn
));
4995 delete_insn (move_insn
);
4996 while ((other_def
= DF_REG_DEF_CHAIN (REGNO (other_reg
))))
4997 delete_insn (DF_REF_INSN (other_def
));
4998 delete_insn (def_insn
);
5000 set
= single_set (newinsn
);
5001 success
= validate_change (newinsn
, &SET_DEST (set
), other_reg
, 0);
5002 gcc_assert (success
);
5004 fprintf (dump_file
, " %d) rather than keep unallocated replacement %d\n",
5005 INSN_UID (newinsn
), i
);
5006 SET_REG_N_REFS (i
, 0);
5010 /* If the backend knows where to allocate pseudos for hard
5011 register initial values, register these allocations now. */
5013 allocate_initial_values (void)
5015 if (targetm
.allocate_initial_value
)
5020 for (i
= 0; HARD_REGISTER_NUM_P (i
); i
++)
5022 if (! initial_value_entry (i
, &hreg
, &preg
))
5025 x
= targetm
.allocate_initial_value (hreg
);
5026 regno
= REGNO (preg
);
5027 if (x
&& REG_N_SETS (regno
) <= 1)
5030 reg_equiv_memory_loc (regno
) = x
;
5036 gcc_assert (REG_P (x
));
5037 new_regno
= REGNO (x
);
5038 reg_renumber
[regno
] = new_regno
;
5039 /* Poke the regno right into regno_reg_rtx so that even
5040 fixed regs are accepted. */
5041 SET_REGNO (preg
, new_regno
);
5042 /* Update global register liveness information. */
5043 FOR_EACH_BB_FN (bb
, cfun
)
5045 if (REGNO_REG_SET_P (df_get_live_in (bb
), regno
))
5046 SET_REGNO_REG_SET (df_get_live_in (bb
), new_regno
);
5047 if (REGNO_REG_SET_P (df_get_live_out (bb
), regno
))
5048 SET_REGNO_REG_SET (df_get_live_out (bb
), new_regno
);
5054 gcc_checking_assert (! initial_value_entry (FIRST_PSEUDO_REGISTER
,
5060 /* True when we use LRA instead of reload pass for the current
5064 /* True if we have allocno conflicts. It is false for non-optimized
5065 mode or when the conflict table is too big. */
5066 bool ira_conflicts_p
;
5068 /* Saved between IRA and reload. */
5069 static int saved_flag_ira_share_spill_slots
;
5071 /* This is the main entry of IRA. */
5076 int ira_max_point_before_emit
;
5077 bool saved_flag_caller_saves
= flag_caller_saves
;
5078 enum ira_region saved_flag_ira_region
= flag_ira_region
;
5082 /* Perform target specific PIC register initialization. */
5083 targetm
.init_pic_reg ();
5085 ira_conflicts_p
= optimize
> 0;
5087 /* If there are too many pseudos and/or basic blocks (e.g. 10K
5088 pseudos and 10K blocks or 100K pseudos and 1K blocks), we will
5089 use simplified and faster algorithms in LRA. */
5092 && max_reg_num () >= (1 << 26) / last_basic_block_for_fn (cfun
));
5095 /* It permits to skip live range splitting in LRA. */
5096 flag_caller_saves
= false;
5097 /* There is no sense to do regional allocation when we use
5099 flag_ira_region
= IRA_REGION_ONE
;
5100 ira_conflicts_p
= false;
5103 #ifndef IRA_NO_OBSTACK
5104 gcc_obstack_init (&ira_obstack
);
5106 bitmap_obstack_initialize (&ira_bitmap_obstack
);
5108 /* LRA uses its own infrastructure to handle caller save registers. */
5109 if (flag_caller_saves
&& !ira_use_lra_p
)
5110 init_caller_save ();
5112 if (flag_ira_verbose
< 10)
5114 internal_flag_ira_verbose
= flag_ira_verbose
;
5119 internal_flag_ira_verbose
= flag_ira_verbose
- 10;
5120 ira_dump_file
= stderr
;
5123 setup_prohibited_mode_move_regs ();
5124 decrease_live_ranges_number ();
5125 df_note_add_problem ();
5127 /* DF_LIVE can't be used in the register allocator, too many other
5128 parts of the compiler depend on using the "classic" liveness
5129 interpretation of the DF_LR problem. See PR38711.
5130 Remove the problem, so that we don't spend time updating it in
5131 any of the df_analyze() calls during IRA/LRA. */
5133 df_remove_problem (df_live
);
5134 gcc_checking_assert (df_live
== NULL
);
5137 df
->changeable_flags
|= DF_VERIFY_SCHEDULED
;
5142 if (ira_conflicts_p
)
5144 calculate_dominance_info (CDI_DOMINATORS
);
5146 if (split_live_ranges_for_shrink_wrap ())
5149 free_dominance_info (CDI_DOMINATORS
);
5152 df_clear_flags (DF_NO_INSN_RESCAN
);
5154 indirect_jump_optimize ();
5155 if (delete_trivially_dead_insns (get_insns (), max_reg_num ()))
5158 regstat_init_n_sets_and_refs ();
5159 regstat_compute_ri ();
5161 /* If we are not optimizing, then this is the only place before
5162 register allocation where dataflow is done. And that is needed
5163 to generate these warnings. */
5165 generate_setjmp_warnings ();
5167 /* Determine if the current function is a leaf before running IRA
5168 since this can impact optimizations done by the prologue and
5169 epilogue thus changing register elimination offsets. */
5170 crtl
->is_leaf
= leaf_function_p ();
5172 if (resize_reg_info () && flag_ira_loop_pressure
)
5173 ira_set_pseudo_classes (true, ira_dump_file
);
5175 init_alias_analysis ();
5176 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
5177 reg_equiv
= XCNEWVEC (struct equivalence
, max_reg_num ());
5178 update_equiv_regs ();
5180 /* Don't move insns if live range shrinkage or register
5181 pressure-sensitive scheduling were done because it will not
5182 improve allocation but likely worsen insn scheduling. */
5184 && !flag_live_range_shrinkage
5185 && !(flag_sched_pressure
&& flag_schedule_insns
))
5186 combine_and_move_insns ();
5188 /* Gather additional equivalences with memory. */
5190 add_store_equivs ();
5192 loop_optimizer_finalize ();
5193 free_dominance_info (CDI_DOMINATORS
);
5194 end_alias_analysis ();
5199 setup_reg_equiv_init ();
5201 allocated_reg_info_size
= max_reg_num ();
5203 /* It is not worth to do such improvement when we use a simple
5204 allocation because of -O0 usage or because the function is too
5206 if (ira_conflicts_p
)
5207 find_moveable_pseudos ();
5209 max_regno_before_ira
= max_reg_num ();
5210 ira_setup_eliminable_regset ();
5212 ira_overall_cost
= ira_reg_cost
= ira_mem_cost
= 0;
5213 ira_load_cost
= ira_store_cost
= ira_shuffle_cost
= 0;
5214 ira_move_loops_num
= ira_additional_jumps_num
= 0;
5216 ira_assert (current_loops
== NULL
);
5217 if (flag_ira_region
== IRA_REGION_ALL
|| flag_ira_region
== IRA_REGION_MIXED
)
5218 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
| LOOPS_HAVE_RECORDED_EXITS
);
5220 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
5221 fprintf (ira_dump_file
, "Building IRA IR\n");
5222 loops_p
= ira_build ();
5224 ira_assert (ira_conflicts_p
|| !loops_p
);
5226 saved_flag_ira_share_spill_slots
= flag_ira_share_spill_slots
;
5227 if (too_high_register_pressure_p () || cfun
->calls_setjmp
)
5228 /* It is just wasting compiler's time to pack spilled pseudos into
5229 stack slots in this case -- prohibit it. We also do this if
5230 there is setjmp call because a variable not modified between
5231 setjmp and longjmp the compiler is required to preserve its
5232 value and sharing slots does not guarantee it. */
5233 flag_ira_share_spill_slots
= FALSE
;
5237 ira_max_point_before_emit
= ira_max_point
;
5239 ira_initiate_emit_data ();
5243 max_regno
= max_reg_num ();
5244 if (ira_conflicts_p
)
5248 if (! ira_use_lra_p
)
5249 ira_initiate_assign ();
5258 ira_allocno_iterator ai
;
5260 FOR_EACH_ALLOCNO (a
, ai
)
5262 int old_regno
= ALLOCNO_REGNO (a
);
5263 int new_regno
= REGNO (ALLOCNO_EMIT_DATA (a
)->reg
);
5265 ALLOCNO_REGNO (a
) = new_regno
;
5267 if (old_regno
!= new_regno
)
5268 setup_reg_classes (new_regno
, reg_preferred_class (old_regno
),
5269 reg_alternate_class (old_regno
),
5270 reg_allocno_class (old_regno
));
5276 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
5277 fprintf (ira_dump_file
, "Flattening IR\n");
5278 ira_flattening (max_regno_before_ira
, ira_max_point_before_emit
);
5280 /* New insns were generated: add notes and recalculate live
5284 /* ??? Rebuild the loop tree, but why? Does the loop tree
5285 change if new insns were generated? Can that be handled
5286 by updating the loop tree incrementally? */
5287 loop_optimizer_finalize ();
5288 free_dominance_info (CDI_DOMINATORS
);
5289 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
5290 | LOOPS_HAVE_RECORDED_EXITS
);
5292 if (! ira_use_lra_p
)
5294 setup_allocno_assignment_flags ();
5295 ira_initiate_assign ();
5296 ira_reassign_conflict_allocnos (max_regno
);
5301 ira_finish_emit_data ();
5303 setup_reg_renumber ();
5305 calculate_allocation_cost ();
5307 #ifdef ENABLE_IRA_CHECKING
5308 if (ira_conflicts_p
)
5309 check_allocation ();
5312 if (max_regno
!= max_regno_before_ira
)
5314 regstat_free_n_sets_and_refs ();
5316 regstat_init_n_sets_and_refs ();
5317 regstat_compute_ri ();
5320 overall_cost_before
= ira_overall_cost
;
5321 if (! ira_conflicts_p
)
5325 fix_reg_equiv_init ();
5327 #ifdef ENABLE_IRA_CHECKING
5328 print_redundant_copies ();
5330 if (! ira_use_lra_p
)
5332 ira_spilled_reg_stack_slots_num
= 0;
5333 ira_spilled_reg_stack_slots
5334 = ((struct ira_spilled_reg_stack_slot
*)
5335 ira_allocate (max_regno
5336 * sizeof (struct ira_spilled_reg_stack_slot
)));
5337 memset (ira_spilled_reg_stack_slots
, 0,
5338 max_regno
* sizeof (struct ira_spilled_reg_stack_slot
));
5341 allocate_initial_values ();
5343 /* See comment for find_moveable_pseudos call. */
5344 if (ira_conflicts_p
)
5345 move_unallocated_pseudos ();
5347 /* Restore original values. */
5350 flag_caller_saves
= saved_flag_caller_saves
;
5351 flag_ira_region
= saved_flag_ira_region
;
5360 unsigned pic_offset_table_regno
= INVALID_REGNUM
;
5362 if (flag_ira_verbose
< 10)
5363 ira_dump_file
= dump_file
;
5365 /* If pic_offset_table_rtx is a pseudo register, then keep it so
5366 after reload to avoid possible wrong usages of hard reg assigned
5368 if (pic_offset_table_rtx
5369 && REGNO (pic_offset_table_rtx
) >= FIRST_PSEUDO_REGISTER
)
5370 pic_offset_table_regno
= REGNO (pic_offset_table_rtx
);
5372 timevar_push (TV_RELOAD
);
5375 if (current_loops
!= NULL
)
5377 loop_optimizer_finalize ();
5378 free_dominance_info (CDI_DOMINATORS
);
5380 FOR_ALL_BB_FN (bb
, cfun
)
5381 bb
->loop_father
= NULL
;
5382 current_loops
= NULL
;
5386 lra (ira_dump_file
);
5387 /* ???!!! Move it before lra () when we use ira_reg_equiv in
5389 vec_free (reg_equivs
);
5395 df_set_flags (DF_NO_INSN_RESCAN
);
5396 build_insn_chain ();
5398 need_dce
= reload (get_insns (), ira_conflicts_p
);
5401 timevar_pop (TV_RELOAD
);
5403 timevar_push (TV_IRA
);
5405 if (ira_conflicts_p
&& ! ira_use_lra_p
)
5407 ira_free (ira_spilled_reg_stack_slots
);
5408 ira_finish_assign ();
5411 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
5412 && overall_cost_before
!= ira_overall_cost
)
5413 fprintf (ira_dump_file
, "+++Overall after reload %" PRId64
"\n",
5416 flag_ira_share_spill_slots
= saved_flag_ira_share_spill_slots
;
5418 if (! ira_use_lra_p
)
5421 if (current_loops
!= NULL
)
5423 loop_optimizer_finalize ();
5424 free_dominance_info (CDI_DOMINATORS
);
5426 FOR_ALL_BB_FN (bb
, cfun
)
5427 bb
->loop_father
= NULL
;
5428 current_loops
= NULL
;
5431 regstat_free_n_sets_and_refs ();
5435 cleanup_cfg (CLEANUP_EXPENSIVE
);
5437 finish_reg_equiv ();
5439 bitmap_obstack_release (&ira_bitmap_obstack
);
5440 #ifndef IRA_NO_OBSTACK
5441 obstack_free (&ira_obstack
, NULL
);
5444 /* The code after the reload has changed so much that at this point
5445 we might as well just rescan everything. Note that
5446 df_rescan_all_insns is not going to help here because it does not
5447 touch the artificial uses and defs. */
5448 df_finish_pass (true);
5449 df_scan_alloc (NULL
);
5454 df_live_add_problem ();
5455 df_live_set_all_dirty ();
5461 if (need_dce
&& optimize
)
5464 /* Diagnose uses of the hard frame pointer when it is used as a global
5465 register. Often we can get away with letting the user appropriate
5466 the frame pointer, but we should let them know when code generation
5467 makes that impossible. */
5468 if (global_regs
[HARD_FRAME_POINTER_REGNUM
] && frame_pointer_needed
)
5470 tree decl
= global_regs_decl
[HARD_FRAME_POINTER_REGNUM
];
5471 error_at (DECL_SOURCE_LOCATION (current_function_decl
),
5472 "frame pointer required, but reserved");
5473 inform (DECL_SOURCE_LOCATION (decl
), "for %qD", decl
);
5476 /* If we are doing generic stack checking, give a warning if this
5477 function's frame size is larger than we expect. */
5478 if (flag_stack_check
== GENERIC_STACK_CHECK
)
5480 HOST_WIDE_INT size
= get_frame_size () + STACK_CHECK_FIXED_FRAME_SIZE
;
5482 for (int i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
5483 if (df_regs_ever_live_p (i
) && !fixed_regs
[i
] && call_used_regs
[i
])
5484 size
+= UNITS_PER_WORD
;
5486 if (size
> STACK_CHECK_MAX_FRAME_SIZE
)
5487 warning (0, "frame size too large for reliable stack checking");
5490 if (pic_offset_table_regno
!= INVALID_REGNUM
)
5491 pic_offset_table_rtx
= gen_rtx_REG (Pmode
, pic_offset_table_regno
);
5493 timevar_pop (TV_IRA
);
5496 /* Run the integrated register allocator. */
5500 const pass_data pass_data_ira
=
5502 RTL_PASS
, /* type */
5504 OPTGROUP_NONE
, /* optinfo_flags */
5506 0, /* properties_required */
5507 0, /* properties_provided */
5508 0, /* properties_destroyed */
5509 0, /* todo_flags_start */
5510 TODO_do_not_ggc_collect
, /* todo_flags_finish */
5513 class pass_ira
: public rtl_opt_pass
5516 pass_ira (gcc::context
*ctxt
)
5517 : rtl_opt_pass (pass_data_ira
, ctxt
)
5520 /* opt_pass methods: */
5521 virtual bool gate (function
*)
5523 return !targetm
.no_register_allocation
;
5525 virtual unsigned int execute (function
*)
5531 }; // class pass_ira
5536 make_pass_ira (gcc::context
*ctxt
)
5538 return new pass_ira (ctxt
);
5543 const pass_data pass_data_reload
=
5545 RTL_PASS
, /* type */
5546 "reload", /* name */
5547 OPTGROUP_NONE
, /* optinfo_flags */
5548 TV_RELOAD
, /* tv_id */
5549 0, /* properties_required */
5550 0, /* properties_provided */
5551 0, /* properties_destroyed */
5552 0, /* todo_flags_start */
5553 0, /* todo_flags_finish */
5556 class pass_reload
: public rtl_opt_pass
5559 pass_reload (gcc::context
*ctxt
)
5560 : rtl_opt_pass (pass_data_reload
, ctxt
)
5563 /* opt_pass methods: */
5564 virtual bool gate (function
*)
5566 return !targetm
.no_register_allocation
;
5568 virtual unsigned int execute (function
*)
5574 }; // class pass_reload
5579 make_pass_reload (gcc::context
*ctxt
)
5581 return new pass_reload (ctxt
);