PR rtl-optimization/86620
[official-gcc.git] / gcc / ira.c
blobb70e2c60b745e875188a2bd2cf8a3f4701ff63a5
1 /* Integrated Register Allocator (IRA) entry point.
2 Copyright (C) 2006-2018 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
10 version.
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
15 for more details.
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
49 of given set.
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
84 by the move cost.
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
95 assigned yet.
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
112 subregion cap.
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
147 following subpasses:
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
166 ira-build.c).
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
214 still free.
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
252 allocation cost.
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
275 algorithm.
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
314 registers.
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.
366 #include "config.h"
367 #include "system.h"
368 #include "coretypes.h"
369 #include "backend.h"
370 #include "target.h"
371 #include "rtl.h"
372 #include "tree.h"
373 #include "df.h"
374 #include "memmodel.h"
375 #include "tm_p.h"
376 #include "insn-config.h"
377 #include "regs.h"
378 #include "ira.h"
379 #include "ira-int.h"
380 #include "diagnostic-core.h"
381 #include "cfgrtl.h"
382 #include "cfgbuild.h"
383 #include "cfgcleanup.h"
384 #include "expr.h"
385 #include "tree-pass.h"
386 #include "output.h"
387 #include "reload.h"
388 #include "cfgloop.h"
389 #include "lra.h"
390 #include "dce.h"
391 #include "dbgcnt.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;
401 #endif
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. */
407 FILE *ira_dump_file;
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
420 ira-emit.c). */
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
432 IRA work. */
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. */
443 static void
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, (machine_mode) m) - 1;
453 i >= 0; i--)
454 if (hard_regno + i < FIRST_PSEUDO_REGISTER)
455 SET_HARD_REG_BIT (ira_reg_mode_hard_regset[hard_regno][m],
456 hard_regno + i);
461 #define no_unit_alloc_regs \
462 (this_target_ira_int->x_no_unit_alloc_regs)
464 /* The function sets up the three arrays declared above. */
465 static void
466 setup_class_hard_regs (void)
468 int cl, i, hard_regno, n;
469 HARD_REG_SET processed_hard_reg_set;
471 ira_assert (SHRT_MAX >= FIRST_PSEUDO_REGISTER);
472 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
474 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
475 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
476 CLEAR_HARD_REG_SET (processed_hard_reg_set);
477 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
479 ira_non_ordered_class_hard_regs[cl][i] = -1;
480 ira_class_hard_reg_index[cl][i] = -1;
482 for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
484 #ifdef REG_ALLOC_ORDER
485 hard_regno = reg_alloc_order[i];
486 #else
487 hard_regno = i;
488 #endif
489 if (TEST_HARD_REG_BIT (processed_hard_reg_set, hard_regno))
490 continue;
491 SET_HARD_REG_BIT (processed_hard_reg_set, hard_regno);
492 if (! TEST_HARD_REG_BIT (temp_hard_regset, hard_regno))
493 ira_class_hard_reg_index[cl][hard_regno] = -1;
494 else
496 ira_class_hard_reg_index[cl][hard_regno] = n;
497 ira_class_hard_regs[cl][n++] = hard_regno;
500 ira_class_hard_regs_num[cl] = n;
501 for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
502 if (TEST_HARD_REG_BIT (temp_hard_regset, i))
503 ira_non_ordered_class_hard_regs[cl][n++] = i;
504 ira_assert (ira_class_hard_regs_num[cl] == n);
508 /* Set up global variables defining info about hard registers for the
509 allocation. These depend on USE_HARD_FRAME_P whose TRUE value means
510 that we can use the hard frame pointer for the allocation. */
511 static void
512 setup_alloc_regs (bool use_hard_frame_p)
514 #ifdef ADJUST_REG_ALLOC_ORDER
515 ADJUST_REG_ALLOC_ORDER;
516 #endif
517 COPY_HARD_REG_SET (no_unit_alloc_regs, fixed_nonglobal_reg_set);
518 if (! use_hard_frame_p)
519 SET_HARD_REG_BIT (no_unit_alloc_regs, HARD_FRAME_POINTER_REGNUM);
520 setup_class_hard_regs ();
525 #define alloc_reg_class_subclasses \
526 (this_target_ira_int->x_alloc_reg_class_subclasses)
528 /* Initialize the table of subclasses of each reg class. */
529 static void
530 setup_reg_subclasses (void)
532 int i, j;
533 HARD_REG_SET temp_hard_regset2;
535 for (i = 0; i < N_REG_CLASSES; i++)
536 for (j = 0; j < N_REG_CLASSES; j++)
537 alloc_reg_class_subclasses[i][j] = LIM_REG_CLASSES;
539 for (i = 0; i < N_REG_CLASSES; i++)
541 if (i == (int) NO_REGS)
542 continue;
544 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
545 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
546 if (hard_reg_set_empty_p (temp_hard_regset))
547 continue;
548 for (j = 0; j < N_REG_CLASSES; j++)
549 if (i != j)
551 enum reg_class *p;
553 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[j]);
554 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
555 if (! hard_reg_set_subset_p (temp_hard_regset,
556 temp_hard_regset2))
557 continue;
558 p = &alloc_reg_class_subclasses[j][0];
559 while (*p != LIM_REG_CLASSES) p++;
560 *p = (enum reg_class) i;
567 /* Set up IRA_MEMORY_MOVE_COST and IRA_MAX_MEMORY_MOVE_COST. */
568 static void
569 setup_class_subset_and_memory_move_costs (void)
571 int cl, cl2, mode, cost;
572 HARD_REG_SET temp_hard_regset2;
574 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
575 ira_memory_move_cost[mode][NO_REGS][0]
576 = ira_memory_move_cost[mode][NO_REGS][1] = SHRT_MAX;
577 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
579 if (cl != (int) NO_REGS)
580 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
582 ira_max_memory_move_cost[mode][cl][0]
583 = ira_memory_move_cost[mode][cl][0]
584 = memory_move_cost ((machine_mode) mode,
585 (reg_class_t) cl, false);
586 ira_max_memory_move_cost[mode][cl][1]
587 = ira_memory_move_cost[mode][cl][1]
588 = memory_move_cost ((machine_mode) mode,
589 (reg_class_t) cl, true);
590 /* Costs for NO_REGS are used in cost calculation on the
591 1st pass when the preferred register classes are not
592 known yet. In this case we take the best scenario. */
593 if (ira_memory_move_cost[mode][NO_REGS][0]
594 > ira_memory_move_cost[mode][cl][0])
595 ira_max_memory_move_cost[mode][NO_REGS][0]
596 = ira_memory_move_cost[mode][NO_REGS][0]
597 = ira_memory_move_cost[mode][cl][0];
598 if (ira_memory_move_cost[mode][NO_REGS][1]
599 > ira_memory_move_cost[mode][cl][1])
600 ira_max_memory_move_cost[mode][NO_REGS][1]
601 = ira_memory_move_cost[mode][NO_REGS][1]
602 = ira_memory_move_cost[mode][cl][1];
605 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
606 for (cl2 = (int) N_REG_CLASSES - 1; cl2 >= 0; cl2--)
608 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
609 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
610 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]);
611 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
612 ira_class_subset_p[cl][cl2]
613 = hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2);
614 if (! hard_reg_set_empty_p (temp_hard_regset2)
615 && hard_reg_set_subset_p (reg_class_contents[cl2],
616 reg_class_contents[cl]))
617 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
619 cost = ira_memory_move_cost[mode][cl2][0];
620 if (cost > ira_max_memory_move_cost[mode][cl][0])
621 ira_max_memory_move_cost[mode][cl][0] = cost;
622 cost = ira_memory_move_cost[mode][cl2][1];
623 if (cost > ira_max_memory_move_cost[mode][cl][1])
624 ira_max_memory_move_cost[mode][cl][1] = cost;
627 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
628 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
630 ira_memory_move_cost[mode][cl][0]
631 = ira_max_memory_move_cost[mode][cl][0];
632 ira_memory_move_cost[mode][cl][1]
633 = ira_max_memory_move_cost[mode][cl][1];
635 setup_reg_subclasses ();
640 /* Define the following macro if allocation through malloc if
641 preferable. */
642 #define IRA_NO_OBSTACK
644 #ifndef IRA_NO_OBSTACK
645 /* Obstack used for storing all dynamic data (except bitmaps) of the
646 IRA. */
647 static struct obstack ira_obstack;
648 #endif
650 /* Obstack used for storing all bitmaps of the IRA. */
651 static struct bitmap_obstack ira_bitmap_obstack;
653 /* Allocate memory of size LEN for IRA data. */
654 void *
655 ira_allocate (size_t len)
657 void *res;
659 #ifndef IRA_NO_OBSTACK
660 res = obstack_alloc (&ira_obstack, len);
661 #else
662 res = xmalloc (len);
663 #endif
664 return res;
667 /* Free memory ADDR allocated for IRA data. */
668 void
669 ira_free (void *addr ATTRIBUTE_UNUSED)
671 #ifndef IRA_NO_OBSTACK
672 /* do nothing */
673 #else
674 free (addr);
675 #endif
679 /* Allocate and returns bitmap for IRA. */
680 bitmap
681 ira_allocate_bitmap (void)
683 return BITMAP_ALLOC (&ira_bitmap_obstack);
686 /* Free bitmap B allocated for IRA. */
687 void
688 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED)
690 /* do nothing */
695 /* Output information about allocation of all allocnos (except for
696 caps) into file F. */
697 void
698 ira_print_disposition (FILE *f)
700 int i, n, max_regno;
701 ira_allocno_t a;
702 basic_block bb;
704 fprintf (f, "Disposition:");
705 max_regno = max_reg_num ();
706 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
707 for (a = ira_regno_allocno_map[i];
708 a != NULL;
709 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
711 if (n % 4 == 0)
712 fprintf (f, "\n");
713 n++;
714 fprintf (f, " %4d:r%-4d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
715 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
716 fprintf (f, "b%-3d", bb->index);
717 else
718 fprintf (f, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
719 if (ALLOCNO_HARD_REGNO (a) >= 0)
720 fprintf (f, " %3d", ALLOCNO_HARD_REGNO (a));
721 else
722 fprintf (f, " mem");
724 fprintf (f, "\n");
727 /* Outputs information about allocation of all allocnos into
728 stderr. */
729 void
730 ira_debug_disposition (void)
732 ira_print_disposition (stderr);
737 /* Set up ira_stack_reg_pressure_class which is the biggest pressure
738 register class containing stack registers or NO_REGS if there are
739 no stack registers. To find this class, we iterate through all
740 register pressure classes and choose the first register pressure
741 class containing all the stack registers and having the biggest
742 size. */
743 static void
744 setup_stack_reg_pressure_class (void)
746 ira_stack_reg_pressure_class = NO_REGS;
747 #ifdef STACK_REGS
749 int i, best, size;
750 enum reg_class cl;
751 HARD_REG_SET temp_hard_regset2;
753 CLEAR_HARD_REG_SET (temp_hard_regset);
754 for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
755 SET_HARD_REG_BIT (temp_hard_regset, i);
756 best = 0;
757 for (i = 0; i < ira_pressure_classes_num; i++)
759 cl = ira_pressure_classes[i];
760 COPY_HARD_REG_SET (temp_hard_regset2, temp_hard_regset);
761 AND_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
762 size = hard_reg_set_size (temp_hard_regset2);
763 if (best < size)
765 best = size;
766 ira_stack_reg_pressure_class = cl;
770 #endif
773 /* Find pressure classes which are register classes for which we
774 calculate register pressure in IRA, register pressure sensitive
775 insn scheduling, and register pressure sensitive loop invariant
776 motion.
778 To make register pressure calculation easy, we always use
779 non-intersected register pressure classes. A move of hard
780 registers from one register pressure class is not more expensive
781 than load and store of the hard registers. Most likely an allocno
782 class will be a subset of a register pressure class and in many
783 cases a register pressure class. That makes usage of register
784 pressure classes a good approximation to find a high register
785 pressure. */
786 static void
787 setup_pressure_classes (void)
789 int cost, i, n, curr;
790 int cl, cl2;
791 enum reg_class pressure_classes[N_REG_CLASSES];
792 int m;
793 HARD_REG_SET temp_hard_regset2;
794 bool insert_p;
796 if (targetm.compute_pressure_classes)
797 n = targetm.compute_pressure_classes (pressure_classes);
798 else
800 n = 0;
801 for (cl = 0; cl < N_REG_CLASSES; cl++)
803 if (ira_class_hard_regs_num[cl] == 0)
804 continue;
805 if (ira_class_hard_regs_num[cl] != 1
806 /* A register class without subclasses may contain a few
807 hard registers and movement between them is costly
808 (e.g. SPARC FPCC registers). We still should consider it
809 as a candidate for a pressure class. */
810 && alloc_reg_class_subclasses[cl][0] < cl)
812 /* Check that the moves between any hard registers of the
813 current class are not more expensive for a legal mode
814 than load/store of the hard registers of the current
815 class. Such class is a potential candidate to be a
816 register pressure class. */
817 for (m = 0; m < NUM_MACHINE_MODES; m++)
819 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
820 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
821 AND_COMPL_HARD_REG_SET (temp_hard_regset,
822 ira_prohibited_class_mode_regs[cl][m]);
823 if (hard_reg_set_empty_p (temp_hard_regset))
824 continue;
825 ira_init_register_move_cost_if_necessary ((machine_mode) m);
826 cost = ira_register_move_cost[m][cl][cl];
827 if (cost <= ira_max_memory_move_cost[m][cl][1]
828 || cost <= ira_max_memory_move_cost[m][cl][0])
829 break;
831 if (m >= NUM_MACHINE_MODES)
832 continue;
834 curr = 0;
835 insert_p = true;
836 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
837 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
838 /* Remove so far added pressure classes which are subset of the
839 current candidate class. Prefer GENERAL_REGS as a pressure
840 register class to another class containing the same
841 allocatable hard registers. We do this because machine
842 dependent cost hooks might give wrong costs for the latter
843 class but always give the right cost for the former class
844 (GENERAL_REGS). */
845 for (i = 0; i < n; i++)
847 cl2 = pressure_classes[i];
848 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]);
849 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
850 if (hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2)
851 && (! hard_reg_set_equal_p (temp_hard_regset,
852 temp_hard_regset2)
853 || cl2 == (int) GENERAL_REGS))
855 pressure_classes[curr++] = (enum reg_class) cl2;
856 insert_p = false;
857 continue;
859 if (hard_reg_set_subset_p (temp_hard_regset2, temp_hard_regset)
860 && (! hard_reg_set_equal_p (temp_hard_regset2,
861 temp_hard_regset)
862 || cl == (int) GENERAL_REGS))
863 continue;
864 if (hard_reg_set_equal_p (temp_hard_regset2, temp_hard_regset))
865 insert_p = false;
866 pressure_classes[curr++] = (enum reg_class) cl2;
868 /* If the current candidate is a subset of a so far added
869 pressure class, don't add it to the list of the pressure
870 classes. */
871 if (insert_p)
872 pressure_classes[curr++] = (enum reg_class) cl;
873 n = curr;
876 #ifdef ENABLE_IRA_CHECKING
878 HARD_REG_SET ignore_hard_regs;
880 /* Check pressure classes correctness: here we check that hard
881 registers from all register pressure classes contains all hard
882 registers available for the allocation. */
883 CLEAR_HARD_REG_SET (temp_hard_regset);
884 CLEAR_HARD_REG_SET (temp_hard_regset2);
885 COPY_HARD_REG_SET (ignore_hard_regs, no_unit_alloc_regs);
886 for (cl = 0; cl < LIM_REG_CLASSES; cl++)
888 /* For some targets (like MIPS with MD_REGS), there are some
889 classes with hard registers available for allocation but
890 not able to hold value of any mode. */
891 for (m = 0; m < NUM_MACHINE_MODES; m++)
892 if (contains_reg_of_mode[cl][m])
893 break;
894 if (m >= NUM_MACHINE_MODES)
896 IOR_HARD_REG_SET (ignore_hard_regs, reg_class_contents[cl]);
897 continue;
899 for (i = 0; i < n; i++)
900 if ((int) pressure_classes[i] == cl)
901 break;
902 IOR_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
903 if (i < n)
904 IOR_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
906 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
907 /* Some targets (like SPARC with ICC reg) have allocatable regs
908 for which no reg class is defined. */
909 if (REGNO_REG_CLASS (i) == NO_REGS)
910 SET_HARD_REG_BIT (ignore_hard_regs, i);
911 AND_COMPL_HARD_REG_SET (temp_hard_regset, ignore_hard_regs);
912 AND_COMPL_HARD_REG_SET (temp_hard_regset2, ignore_hard_regs);
913 ira_assert (hard_reg_set_subset_p (temp_hard_regset2, temp_hard_regset));
915 #endif
916 ira_pressure_classes_num = 0;
917 for (i = 0; i < n; i++)
919 cl = (int) pressure_classes[i];
920 ira_reg_pressure_class_p[cl] = true;
921 ira_pressure_classes[ira_pressure_classes_num++] = (enum reg_class) cl;
923 setup_stack_reg_pressure_class ();
926 /* Set up IRA_UNIFORM_CLASS_P. Uniform class is a register class
927 whose register move cost between any registers of the class is the
928 same as for all its subclasses. We use the data to speed up the
929 2nd pass of calculations of allocno costs. */
930 static void
931 setup_uniform_class_p (void)
933 int i, cl, cl2, m;
935 for (cl = 0; cl < N_REG_CLASSES; cl++)
937 ira_uniform_class_p[cl] = false;
938 if (ira_class_hard_regs_num[cl] == 0)
939 continue;
940 /* We can not use alloc_reg_class_subclasses here because move
941 cost hooks does not take into account that some registers are
942 unavailable for the subtarget. E.g. for i686, INT_SSE_REGS
943 is element of alloc_reg_class_subclasses for GENERAL_REGS
944 because SSE regs are unavailable. */
945 for (i = 0; (cl2 = reg_class_subclasses[cl][i]) != LIM_REG_CLASSES; i++)
947 if (ira_class_hard_regs_num[cl2] == 0)
948 continue;
949 for (m = 0; m < NUM_MACHINE_MODES; m++)
950 if (contains_reg_of_mode[cl][m] && contains_reg_of_mode[cl2][m])
952 ira_init_register_move_cost_if_necessary ((machine_mode) m);
953 if (ira_register_move_cost[m][cl][cl]
954 != ira_register_move_cost[m][cl2][cl2])
955 break;
957 if (m < NUM_MACHINE_MODES)
958 break;
960 if (cl2 == LIM_REG_CLASSES)
961 ira_uniform_class_p[cl] = true;
965 /* Set up IRA_ALLOCNO_CLASSES, IRA_ALLOCNO_CLASSES_NUM,
966 IRA_IMPORTANT_CLASSES, and IRA_IMPORTANT_CLASSES_NUM.
968 Target may have many subtargets and not all target hard registers can
969 be used for allocation, e.g. x86 port in 32-bit mode can not use
970 hard registers introduced in x86-64 like r8-r15). Some classes
971 might have the same allocatable hard registers, e.g. INDEX_REGS
972 and GENERAL_REGS in x86 port in 32-bit mode. To decrease different
973 calculations efforts we introduce allocno classes which contain
974 unique non-empty sets of allocatable hard-registers.
976 Pseudo class cost calculation in ira-costs.c is very expensive.
977 Therefore we are trying to decrease number of classes involved in
978 such calculation. Register classes used in the cost calculation
979 are called important classes. They are allocno classes and other
980 non-empty classes whose allocatable hard register sets are inside
981 of an allocno class hard register set. From the first sight, it
982 looks like that they are just allocno classes. It is not true. In
983 example of x86-port in 32-bit mode, allocno classes will contain
984 GENERAL_REGS but not LEGACY_REGS (because allocatable hard
985 registers are the same for the both classes). The important
986 classes will contain GENERAL_REGS and LEGACY_REGS. It is done
987 because a machine description insn constraint may refers for
988 LEGACY_REGS and code in ira-costs.c is mostly base on investigation
989 of the insn constraints. */
990 static void
991 setup_allocno_and_important_classes (void)
993 int i, j, n, cl;
994 bool set_p;
995 HARD_REG_SET temp_hard_regset2;
996 static enum reg_class classes[LIM_REG_CLASSES + 1];
998 n = 0;
999 /* Collect classes which contain unique sets of allocatable hard
1000 registers. Prefer GENERAL_REGS to other classes containing the
1001 same set of hard registers. */
1002 for (i = 0; i < LIM_REG_CLASSES; i++)
1004 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
1005 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1006 for (j = 0; j < n; j++)
1008 cl = classes[j];
1009 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
1010 AND_COMPL_HARD_REG_SET (temp_hard_regset2,
1011 no_unit_alloc_regs);
1012 if (hard_reg_set_equal_p (temp_hard_regset,
1013 temp_hard_regset2))
1014 break;
1016 if (j >= n || targetm.additional_allocno_class_p (i))
1017 classes[n++] = (enum reg_class) i;
1018 else if (i == GENERAL_REGS)
1019 /* Prefer general regs. For i386 example, it means that
1020 we prefer GENERAL_REGS over INDEX_REGS or LEGACY_REGS
1021 (all of them consists of the same available hard
1022 registers). */
1023 classes[j] = (enum reg_class) i;
1025 classes[n] = LIM_REG_CLASSES;
1027 /* Set up classes which can be used for allocnos as classes
1028 containing non-empty unique sets of allocatable hard
1029 registers. */
1030 ira_allocno_classes_num = 0;
1031 for (i = 0; (cl = classes[i]) != LIM_REG_CLASSES; i++)
1032 if (ira_class_hard_regs_num[cl] > 0)
1033 ira_allocno_classes[ira_allocno_classes_num++] = (enum reg_class) cl;
1034 ira_important_classes_num = 0;
1035 /* Add non-allocno classes containing to non-empty set of
1036 allocatable hard regs. */
1037 for (cl = 0; cl < N_REG_CLASSES; cl++)
1038 if (ira_class_hard_regs_num[cl] > 0)
1040 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
1041 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1042 set_p = false;
1043 for (j = 0; j < ira_allocno_classes_num; j++)
1045 COPY_HARD_REG_SET (temp_hard_regset2,
1046 reg_class_contents[ira_allocno_classes[j]]);
1047 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
1048 if ((enum reg_class) cl == ira_allocno_classes[j])
1049 break;
1050 else if (hard_reg_set_subset_p (temp_hard_regset,
1051 temp_hard_regset2))
1052 set_p = true;
1054 if (set_p && j >= ira_allocno_classes_num)
1055 ira_important_classes[ira_important_classes_num++]
1056 = (enum reg_class) cl;
1058 /* Now add allocno classes to the important classes. */
1059 for (j = 0; j < ira_allocno_classes_num; j++)
1060 ira_important_classes[ira_important_classes_num++]
1061 = ira_allocno_classes[j];
1062 for (cl = 0; cl < N_REG_CLASSES; cl++)
1064 ira_reg_allocno_class_p[cl] = false;
1065 ira_reg_pressure_class_p[cl] = false;
1067 for (j = 0; j < ira_allocno_classes_num; j++)
1068 ira_reg_allocno_class_p[ira_allocno_classes[j]] = true;
1069 setup_pressure_classes ();
1070 setup_uniform_class_p ();
1073 /* Setup translation in CLASS_TRANSLATE of all classes into a class
1074 given by array CLASSES of length CLASSES_NUM. The function is used
1075 make translation any reg class to an allocno class or to an
1076 pressure class. This translation is necessary for some
1077 calculations when we can use only allocno or pressure classes and
1078 such translation represents an approximate representation of all
1079 classes.
1081 The translation in case when allocatable hard register set of a
1082 given class is subset of allocatable hard register set of a class
1083 in CLASSES is pretty simple. We use smallest classes from CLASSES
1084 containing a given class. If allocatable hard register set of a
1085 given class is not a subset of any corresponding set of a class
1086 from CLASSES, we use the cheapest (with load/store point of view)
1087 class from CLASSES whose set intersects with given class set. */
1088 static void
1089 setup_class_translate_array (enum reg_class *class_translate,
1090 int classes_num, enum reg_class *classes)
1092 int cl, mode;
1093 enum reg_class aclass, best_class, *cl_ptr;
1094 int i, cost, min_cost, best_cost;
1096 for (cl = 0; cl < N_REG_CLASSES; cl++)
1097 class_translate[cl] = NO_REGS;
1099 for (i = 0; i < classes_num; i++)
1101 aclass = classes[i];
1102 for (cl_ptr = &alloc_reg_class_subclasses[aclass][0];
1103 (cl = *cl_ptr) != LIM_REG_CLASSES;
1104 cl_ptr++)
1105 if (class_translate[cl] == NO_REGS)
1106 class_translate[cl] = aclass;
1107 class_translate[aclass] = aclass;
1109 /* For classes which are not fully covered by one of given classes
1110 (in other words covered by more one given class), use the
1111 cheapest class. */
1112 for (cl = 0; cl < N_REG_CLASSES; cl++)
1114 if (cl == NO_REGS || class_translate[cl] != NO_REGS)
1115 continue;
1116 best_class = NO_REGS;
1117 best_cost = INT_MAX;
1118 for (i = 0; i < classes_num; i++)
1120 aclass = classes[i];
1121 COPY_HARD_REG_SET (temp_hard_regset,
1122 reg_class_contents[aclass]);
1123 AND_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
1124 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1125 if (! hard_reg_set_empty_p (temp_hard_regset))
1127 min_cost = INT_MAX;
1128 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1130 cost = (ira_memory_move_cost[mode][aclass][0]
1131 + ira_memory_move_cost[mode][aclass][1]);
1132 if (min_cost > cost)
1133 min_cost = cost;
1135 if (best_class == NO_REGS || best_cost > min_cost)
1137 best_class = aclass;
1138 best_cost = min_cost;
1142 class_translate[cl] = best_class;
1146 /* Set up array IRA_ALLOCNO_CLASS_TRANSLATE and
1147 IRA_PRESSURE_CLASS_TRANSLATE. */
1148 static void
1149 setup_class_translate (void)
1151 setup_class_translate_array (ira_allocno_class_translate,
1152 ira_allocno_classes_num, ira_allocno_classes);
1153 setup_class_translate_array (ira_pressure_class_translate,
1154 ira_pressure_classes_num, ira_pressure_classes);
1157 /* Order numbers of allocno classes in original target allocno class
1158 array, -1 for non-allocno classes. */
1159 static int allocno_class_order[N_REG_CLASSES];
1161 /* The function used to sort the important classes. */
1162 static int
1163 comp_reg_classes_func (const void *v1p, const void *v2p)
1165 enum reg_class cl1 = *(const enum reg_class *) v1p;
1166 enum reg_class cl2 = *(const enum reg_class *) v2p;
1167 enum reg_class tcl1, tcl2;
1168 int diff;
1170 tcl1 = ira_allocno_class_translate[cl1];
1171 tcl2 = ira_allocno_class_translate[cl2];
1172 if (tcl1 != NO_REGS && tcl2 != NO_REGS
1173 && (diff = allocno_class_order[tcl1] - allocno_class_order[tcl2]) != 0)
1174 return diff;
1175 return (int) cl1 - (int) cl2;
1178 /* For correct work of function setup_reg_class_relation we need to
1179 reorder important classes according to the order of their allocno
1180 classes. It places important classes containing the same
1181 allocatable hard register set adjacent to each other and allocno
1182 class with the allocatable hard register set right after the other
1183 important classes with the same set.
1185 In example from comments of function
1186 setup_allocno_and_important_classes, it places LEGACY_REGS and
1187 GENERAL_REGS close to each other and GENERAL_REGS is after
1188 LEGACY_REGS. */
1189 static void
1190 reorder_important_classes (void)
1192 int i;
1194 for (i = 0; i < N_REG_CLASSES; i++)
1195 allocno_class_order[i] = -1;
1196 for (i = 0; i < ira_allocno_classes_num; i++)
1197 allocno_class_order[ira_allocno_classes[i]] = i;
1198 qsort (ira_important_classes, ira_important_classes_num,
1199 sizeof (enum reg_class), comp_reg_classes_func);
1200 for (i = 0; i < ira_important_classes_num; i++)
1201 ira_important_class_nums[ira_important_classes[i]] = i;
1204 /* Set up IRA_REG_CLASS_SUBUNION, IRA_REG_CLASS_SUPERUNION,
1205 IRA_REG_CLASS_SUPER_CLASSES, IRA_REG_CLASSES_INTERSECT, and
1206 IRA_REG_CLASSES_INTERSECT_P. For the meaning of the relations,
1207 please see corresponding comments in ira-int.h. */
1208 static void
1209 setup_reg_class_relations (void)
1211 int i, cl1, cl2, cl3;
1212 HARD_REG_SET intersection_set, union_set, temp_set2;
1213 bool important_class_p[N_REG_CLASSES];
1215 memset (important_class_p, 0, sizeof (important_class_p));
1216 for (i = 0; i < ira_important_classes_num; i++)
1217 important_class_p[ira_important_classes[i]] = true;
1218 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1220 ira_reg_class_super_classes[cl1][0] = LIM_REG_CLASSES;
1221 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1223 ira_reg_classes_intersect_p[cl1][cl2] = false;
1224 ira_reg_class_intersect[cl1][cl2] = NO_REGS;
1225 ira_reg_class_subset[cl1][cl2] = NO_REGS;
1226 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl1]);
1227 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1228 COPY_HARD_REG_SET (temp_set2, reg_class_contents[cl2]);
1229 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1230 if (hard_reg_set_empty_p (temp_hard_regset)
1231 && hard_reg_set_empty_p (temp_set2))
1233 /* The both classes have no allocatable hard registers
1234 -- take all class hard registers into account and use
1235 reg_class_subunion and reg_class_superunion. */
1236 for (i = 0;; i++)
1238 cl3 = reg_class_subclasses[cl1][i];
1239 if (cl3 == LIM_REG_CLASSES)
1240 break;
1241 if (reg_class_subset_p (ira_reg_class_intersect[cl1][cl2],
1242 (enum reg_class) cl3))
1243 ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
1245 ira_reg_class_subunion[cl1][cl2] = reg_class_subunion[cl1][cl2];
1246 ira_reg_class_superunion[cl1][cl2] = reg_class_superunion[cl1][cl2];
1247 continue;
1249 ira_reg_classes_intersect_p[cl1][cl2]
1250 = hard_reg_set_intersect_p (temp_hard_regset, temp_set2);
1251 if (important_class_p[cl1] && important_class_p[cl2]
1252 && hard_reg_set_subset_p (temp_hard_regset, temp_set2))
1254 /* CL1 and CL2 are important classes and CL1 allocatable
1255 hard register set is inside of CL2 allocatable hard
1256 registers -- make CL1 a superset of CL2. */
1257 enum reg_class *p;
1259 p = &ira_reg_class_super_classes[cl1][0];
1260 while (*p != LIM_REG_CLASSES)
1261 p++;
1262 *p++ = (enum reg_class) cl2;
1263 *p = LIM_REG_CLASSES;
1265 ira_reg_class_subunion[cl1][cl2] = NO_REGS;
1266 ira_reg_class_superunion[cl1][cl2] = NO_REGS;
1267 COPY_HARD_REG_SET (intersection_set, reg_class_contents[cl1]);
1268 AND_HARD_REG_SET (intersection_set, reg_class_contents[cl2]);
1269 AND_COMPL_HARD_REG_SET (intersection_set, no_unit_alloc_regs);
1270 COPY_HARD_REG_SET (union_set, reg_class_contents[cl1]);
1271 IOR_HARD_REG_SET (union_set, reg_class_contents[cl2]);
1272 AND_COMPL_HARD_REG_SET (union_set, no_unit_alloc_regs);
1273 for (cl3 = 0; cl3 < N_REG_CLASSES; cl3++)
1275 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl3]);
1276 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1277 if (hard_reg_set_subset_p (temp_hard_regset, intersection_set))
1279 /* CL3 allocatable hard register set is inside of
1280 intersection of allocatable hard register sets
1281 of CL1 and CL2. */
1282 if (important_class_p[cl3])
1284 COPY_HARD_REG_SET
1285 (temp_set2,
1286 reg_class_contents
1287 [(int) ira_reg_class_intersect[cl1][cl2]]);
1288 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1289 if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1290 /* If the allocatable hard register sets are
1291 the same, prefer GENERAL_REGS or the
1292 smallest class for debugging
1293 purposes. */
1294 || (hard_reg_set_equal_p (temp_hard_regset, temp_set2)
1295 && (cl3 == GENERAL_REGS
1296 || ((ira_reg_class_intersect[cl1][cl2]
1297 != GENERAL_REGS)
1298 && hard_reg_set_subset_p
1299 (reg_class_contents[cl3],
1300 reg_class_contents
1301 [(int)
1302 ira_reg_class_intersect[cl1][cl2]])))))
1303 ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
1305 COPY_HARD_REG_SET
1306 (temp_set2,
1307 reg_class_contents[(int) ira_reg_class_subset[cl1][cl2]]);
1308 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1309 if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1310 /* Ignore unavailable hard registers and prefer
1311 smallest class for debugging purposes. */
1312 || (hard_reg_set_equal_p (temp_hard_regset, temp_set2)
1313 && hard_reg_set_subset_p
1314 (reg_class_contents[cl3],
1315 reg_class_contents
1316 [(int) ira_reg_class_subset[cl1][cl2]])))
1317 ira_reg_class_subset[cl1][cl2] = (enum reg_class) cl3;
1319 if (important_class_p[cl3]
1320 && hard_reg_set_subset_p (temp_hard_regset, union_set))
1322 /* CL3 allocatable hard register set is inside of
1323 union of allocatable hard register sets of CL1
1324 and CL2. */
1325 COPY_HARD_REG_SET
1326 (temp_set2,
1327 reg_class_contents[(int) ira_reg_class_subunion[cl1][cl2]]);
1328 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1329 if (ira_reg_class_subunion[cl1][cl2] == NO_REGS
1330 || (hard_reg_set_subset_p (temp_set2, temp_hard_regset)
1332 && (! hard_reg_set_equal_p (temp_set2,
1333 temp_hard_regset)
1334 || cl3 == GENERAL_REGS
1335 /* If the allocatable hard register sets are the
1336 same, prefer GENERAL_REGS or the smallest
1337 class for debugging purposes. */
1338 || (ira_reg_class_subunion[cl1][cl2] != GENERAL_REGS
1339 && hard_reg_set_subset_p
1340 (reg_class_contents[cl3],
1341 reg_class_contents
1342 [(int) ira_reg_class_subunion[cl1][cl2]])))))
1343 ira_reg_class_subunion[cl1][cl2] = (enum reg_class) cl3;
1345 if (hard_reg_set_subset_p (union_set, temp_hard_regset))
1347 /* CL3 allocatable hard register set contains union
1348 of allocatable hard register sets of CL1 and
1349 CL2. */
1350 COPY_HARD_REG_SET
1351 (temp_set2,
1352 reg_class_contents[(int) ira_reg_class_superunion[cl1][cl2]]);
1353 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1354 if (ira_reg_class_superunion[cl1][cl2] == NO_REGS
1355 || (hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1357 && (! hard_reg_set_equal_p (temp_set2,
1358 temp_hard_regset)
1359 || cl3 == GENERAL_REGS
1360 /* If the allocatable hard register sets are the
1361 same, prefer GENERAL_REGS or the smallest
1362 class for debugging purposes. */
1363 || (ira_reg_class_superunion[cl1][cl2] != GENERAL_REGS
1364 && hard_reg_set_subset_p
1365 (reg_class_contents[cl3],
1366 reg_class_contents
1367 [(int) ira_reg_class_superunion[cl1][cl2]])))))
1368 ira_reg_class_superunion[cl1][cl2] = (enum reg_class) cl3;
1375 /* Output all uniform and important classes into file F. */
1376 static void
1377 print_uniform_and_important_classes (FILE *f)
1379 int i, cl;
1381 fprintf (f, "Uniform classes:\n");
1382 for (cl = 0; cl < N_REG_CLASSES; cl++)
1383 if (ira_uniform_class_p[cl])
1384 fprintf (f, " %s", reg_class_names[cl]);
1385 fprintf (f, "\nImportant classes:\n");
1386 for (i = 0; i < ira_important_classes_num; i++)
1387 fprintf (f, " %s", reg_class_names[ira_important_classes[i]]);
1388 fprintf (f, "\n");
1391 /* Output all possible allocno or pressure classes and their
1392 translation map into file F. */
1393 static void
1394 print_translated_classes (FILE *f, bool pressure_p)
1396 int classes_num = (pressure_p
1397 ? ira_pressure_classes_num : ira_allocno_classes_num);
1398 enum reg_class *classes = (pressure_p
1399 ? ira_pressure_classes : ira_allocno_classes);
1400 enum reg_class *class_translate = (pressure_p
1401 ? ira_pressure_class_translate
1402 : ira_allocno_class_translate);
1403 int i;
1405 fprintf (f, "%s classes:\n", pressure_p ? "Pressure" : "Allocno");
1406 for (i = 0; i < classes_num; i++)
1407 fprintf (f, " %s", reg_class_names[classes[i]]);
1408 fprintf (f, "\nClass translation:\n");
1409 for (i = 0; i < N_REG_CLASSES; i++)
1410 fprintf (f, " %s -> %s\n", reg_class_names[i],
1411 reg_class_names[class_translate[i]]);
1414 /* Output all possible allocno and translation classes and the
1415 translation maps into stderr. */
1416 void
1417 ira_debug_allocno_classes (void)
1419 print_uniform_and_important_classes (stderr);
1420 print_translated_classes (stderr, false);
1421 print_translated_classes (stderr, true);
1424 /* Set up different arrays concerning class subsets, allocno and
1425 important classes. */
1426 static void
1427 find_reg_classes (void)
1429 setup_allocno_and_important_classes ();
1430 setup_class_translate ();
1431 reorder_important_classes ();
1432 setup_reg_class_relations ();
1437 /* Set up the array above. */
1438 static void
1439 setup_hard_regno_aclass (void)
1441 int i;
1443 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1445 #if 1
1446 ira_hard_regno_allocno_class[i]
1447 = (TEST_HARD_REG_BIT (no_unit_alloc_regs, i)
1448 ? NO_REGS
1449 : ira_allocno_class_translate[REGNO_REG_CLASS (i)]);
1450 #else
1451 int j;
1452 enum reg_class cl;
1453 ira_hard_regno_allocno_class[i] = NO_REGS;
1454 for (j = 0; j < ira_allocno_classes_num; j++)
1456 cl = ira_allocno_classes[j];
1457 if (ira_class_hard_reg_index[cl][i] >= 0)
1459 ira_hard_regno_allocno_class[i] = cl;
1460 break;
1463 #endif
1469 /* Form IRA_REG_CLASS_MAX_NREGS and IRA_REG_CLASS_MIN_NREGS maps. */
1470 static void
1471 setup_reg_class_nregs (void)
1473 int i, cl, cl2, m;
1475 for (m = 0; m < MAX_MACHINE_MODE; m++)
1477 for (cl = 0; cl < N_REG_CLASSES; cl++)
1478 ira_reg_class_max_nregs[cl][m]
1479 = ira_reg_class_min_nregs[cl][m]
1480 = targetm.class_max_nregs ((reg_class_t) cl, (machine_mode) m);
1481 for (cl = 0; cl < N_REG_CLASSES; cl++)
1482 for (i = 0;
1483 (cl2 = alloc_reg_class_subclasses[cl][i]) != LIM_REG_CLASSES;
1484 i++)
1485 if (ira_reg_class_min_nregs[cl2][m]
1486 < ira_reg_class_min_nregs[cl][m])
1487 ira_reg_class_min_nregs[cl][m] = ira_reg_class_min_nregs[cl2][m];
1493 /* Set up IRA_PROHIBITED_CLASS_MODE_REGS and IRA_CLASS_SINGLETON.
1494 This function is called once IRA_CLASS_HARD_REGS has been initialized. */
1495 static void
1496 setup_prohibited_class_mode_regs (void)
1498 int j, k, hard_regno, cl, last_hard_regno, count;
1500 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
1502 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
1503 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1504 for (j = 0; j < NUM_MACHINE_MODES; j++)
1506 count = 0;
1507 last_hard_regno = -1;
1508 CLEAR_HARD_REG_SET (ira_prohibited_class_mode_regs[cl][j]);
1509 for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1511 hard_regno = ira_class_hard_regs[cl][k];
1512 if (!targetm.hard_regno_mode_ok (hard_regno, (machine_mode) j))
1513 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1514 hard_regno);
1515 else if (in_hard_reg_set_p (temp_hard_regset,
1516 (machine_mode) j, hard_regno))
1518 last_hard_regno = hard_regno;
1519 count++;
1522 ira_class_singleton[cl][j] = (count == 1 ? last_hard_regno : -1);
1527 /* Clarify IRA_PROHIBITED_CLASS_MODE_REGS by excluding hard registers
1528 spanning from one register pressure class to another one. It is
1529 called after defining the pressure classes. */
1530 static void
1531 clarify_prohibited_class_mode_regs (void)
1533 int j, k, hard_regno, cl, pclass, nregs;
1535 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
1536 for (j = 0; j < NUM_MACHINE_MODES; j++)
1538 CLEAR_HARD_REG_SET (ira_useful_class_mode_regs[cl][j]);
1539 for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1541 hard_regno = ira_class_hard_regs[cl][k];
1542 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j], hard_regno))
1543 continue;
1544 nregs = hard_regno_nregs (hard_regno, (machine_mode) j);
1545 if (hard_regno + nregs > FIRST_PSEUDO_REGISTER)
1547 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1548 hard_regno);
1549 continue;
1551 pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)];
1552 for (nregs-- ;nregs >= 0; nregs--)
1553 if (((enum reg_class) pclass
1554 != ira_pressure_class_translate[REGNO_REG_CLASS
1555 (hard_regno + nregs)]))
1557 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1558 hard_regno);
1559 break;
1561 if (!TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1562 hard_regno))
1563 add_to_hard_reg_set (&ira_useful_class_mode_regs[cl][j],
1564 (machine_mode) j, hard_regno);
1569 /* Allocate and initialize IRA_REGISTER_MOVE_COST, IRA_MAY_MOVE_IN_COST
1570 and IRA_MAY_MOVE_OUT_COST for MODE. */
1571 void
1572 ira_init_register_move_cost (machine_mode mode)
1574 static unsigned short last_move_cost[N_REG_CLASSES][N_REG_CLASSES];
1575 bool all_match = true;
1576 unsigned int cl1, cl2;
1578 ira_assert (ira_register_move_cost[mode] == NULL
1579 && ira_may_move_in_cost[mode] == NULL
1580 && ira_may_move_out_cost[mode] == NULL);
1581 ira_assert (have_regs_of_mode[mode]);
1582 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1583 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1585 int cost;
1586 if (!contains_reg_of_mode[cl1][mode]
1587 || !contains_reg_of_mode[cl2][mode])
1589 if ((ira_reg_class_max_nregs[cl1][mode]
1590 > ira_class_hard_regs_num[cl1])
1591 || (ira_reg_class_max_nregs[cl2][mode]
1592 > ira_class_hard_regs_num[cl2]))
1593 cost = 65535;
1594 else
1595 cost = (ira_memory_move_cost[mode][cl1][0]
1596 + ira_memory_move_cost[mode][cl2][1]) * 2;
1598 else
1600 cost = register_move_cost (mode, (enum reg_class) cl1,
1601 (enum reg_class) cl2);
1602 ira_assert (cost < 65535);
1604 all_match &= (last_move_cost[cl1][cl2] == cost);
1605 last_move_cost[cl1][cl2] = cost;
1607 if (all_match && last_mode_for_init_move_cost != -1)
1609 ira_register_move_cost[mode]
1610 = ira_register_move_cost[last_mode_for_init_move_cost];
1611 ira_may_move_in_cost[mode]
1612 = ira_may_move_in_cost[last_mode_for_init_move_cost];
1613 ira_may_move_out_cost[mode]
1614 = ira_may_move_out_cost[last_mode_for_init_move_cost];
1615 return;
1617 last_mode_for_init_move_cost = mode;
1618 ira_register_move_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1619 ira_may_move_in_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1620 ira_may_move_out_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1621 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1622 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1624 int cost;
1625 enum reg_class *p1, *p2;
1627 if (last_move_cost[cl1][cl2] == 65535)
1629 ira_register_move_cost[mode][cl1][cl2] = 65535;
1630 ira_may_move_in_cost[mode][cl1][cl2] = 65535;
1631 ira_may_move_out_cost[mode][cl1][cl2] = 65535;
1633 else
1635 cost = last_move_cost[cl1][cl2];
1637 for (p2 = &reg_class_subclasses[cl2][0];
1638 *p2 != LIM_REG_CLASSES; p2++)
1639 if (ira_class_hard_regs_num[*p2] > 0
1640 && (ira_reg_class_max_nregs[*p2][mode]
1641 <= ira_class_hard_regs_num[*p2]))
1642 cost = MAX (cost, ira_register_move_cost[mode][cl1][*p2]);
1644 for (p1 = &reg_class_subclasses[cl1][0];
1645 *p1 != LIM_REG_CLASSES; p1++)
1646 if (ira_class_hard_regs_num[*p1] > 0
1647 && (ira_reg_class_max_nregs[*p1][mode]
1648 <= ira_class_hard_regs_num[*p1]))
1649 cost = MAX (cost, ira_register_move_cost[mode][*p1][cl2]);
1651 ira_assert (cost <= 65535);
1652 ira_register_move_cost[mode][cl1][cl2] = cost;
1654 if (ira_class_subset_p[cl1][cl2])
1655 ira_may_move_in_cost[mode][cl1][cl2] = 0;
1656 else
1657 ira_may_move_in_cost[mode][cl1][cl2] = cost;
1659 if (ira_class_subset_p[cl2][cl1])
1660 ira_may_move_out_cost[mode][cl1][cl2] = 0;
1661 else
1662 ira_may_move_out_cost[mode][cl1][cl2] = cost;
1669 /* This is called once during compiler work. It sets up
1670 different arrays whose values don't depend on the compiled
1671 function. */
1672 void
1673 ira_init_once (void)
1675 ira_init_costs_once ();
1676 lra_init_once ();
1678 ira_use_lra_p = targetm.lra_p ();
1681 /* Free ira_max_register_move_cost, ira_may_move_in_cost and
1682 ira_may_move_out_cost for each mode. */
1683 void
1684 target_ira_int::free_register_move_costs (void)
1686 int mode, i;
1688 /* Reset move_cost and friends, making sure we only free shared
1689 table entries once. */
1690 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1691 if (x_ira_register_move_cost[mode])
1693 for (i = 0;
1694 i < mode && (x_ira_register_move_cost[i]
1695 != x_ira_register_move_cost[mode]);
1696 i++)
1698 if (i == mode)
1700 free (x_ira_register_move_cost[mode]);
1701 free (x_ira_may_move_in_cost[mode]);
1702 free (x_ira_may_move_out_cost[mode]);
1705 memset (x_ira_register_move_cost, 0, sizeof x_ira_register_move_cost);
1706 memset (x_ira_may_move_in_cost, 0, sizeof x_ira_may_move_in_cost);
1707 memset (x_ira_may_move_out_cost, 0, sizeof x_ira_may_move_out_cost);
1708 last_mode_for_init_move_cost = -1;
1711 target_ira_int::~target_ira_int ()
1713 free_ira_costs ();
1714 free_register_move_costs ();
1717 /* This is called every time when register related information is
1718 changed. */
1719 void
1720 ira_init (void)
1722 this_target_ira_int->free_register_move_costs ();
1723 setup_reg_mode_hard_regset ();
1724 setup_alloc_regs (flag_omit_frame_pointer != 0);
1725 setup_class_subset_and_memory_move_costs ();
1726 setup_reg_class_nregs ();
1727 setup_prohibited_class_mode_regs ();
1728 find_reg_classes ();
1729 clarify_prohibited_class_mode_regs ();
1730 setup_hard_regno_aclass ();
1731 ira_init_costs ();
1735 #define ira_prohibited_mode_move_regs_initialized_p \
1736 (this_target_ira_int->x_ira_prohibited_mode_move_regs_initialized_p)
1738 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS. */
1739 static void
1740 setup_prohibited_mode_move_regs (void)
1742 int i, j;
1743 rtx test_reg1, test_reg2, move_pat;
1744 rtx_insn *move_insn;
1746 if (ira_prohibited_mode_move_regs_initialized_p)
1747 return;
1748 ira_prohibited_mode_move_regs_initialized_p = true;
1749 test_reg1 = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
1750 test_reg2 = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 2);
1751 move_pat = gen_rtx_SET (test_reg1, test_reg2);
1752 move_insn = gen_rtx_INSN (VOIDmode, 0, 0, 0, move_pat, 0, -1, 0);
1753 for (i = 0; i < NUM_MACHINE_MODES; i++)
1755 SET_HARD_REG_SET (ira_prohibited_mode_move_regs[i]);
1756 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1758 if (!targetm.hard_regno_mode_ok (j, (machine_mode) i))
1759 continue;
1760 set_mode_and_regno (test_reg1, (machine_mode) i, j);
1761 set_mode_and_regno (test_reg2, (machine_mode) i, j);
1762 INSN_CODE (move_insn) = -1;
1763 recog_memoized (move_insn);
1764 if (INSN_CODE (move_insn) < 0)
1765 continue;
1766 extract_insn (move_insn);
1767 /* We don't know whether the move will be in code that is optimized
1768 for size or speed, so consider all enabled alternatives. */
1769 if (! constrain_operands (1, get_enabled_alternatives (move_insn)))
1770 continue;
1771 CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs[i], j);
1778 /* Setup possible alternatives in ALTS for INSN. */
1779 void
1780 ira_setup_alts (rtx_insn *insn, HARD_REG_SET &alts)
1782 /* MAP nalt * nop -> start of constraints for given operand and
1783 alternative. */
1784 static vec<const char *> insn_constraints;
1785 int nop, nalt;
1786 bool curr_swapped;
1787 const char *p;
1788 int commutative = -1;
1790 extract_insn (insn);
1791 alternative_mask preferred = get_preferred_alternatives (insn);
1792 CLEAR_HARD_REG_SET (alts);
1793 insn_constraints.release ();
1794 insn_constraints.safe_grow_cleared (recog_data.n_operands
1795 * recog_data.n_alternatives + 1);
1796 /* Check that the hard reg set is enough for holding all
1797 alternatives. It is hard to imagine the situation when the
1798 assertion is wrong. */
1799 ira_assert (recog_data.n_alternatives
1800 <= (int) MAX (sizeof (HARD_REG_ELT_TYPE) * CHAR_BIT,
1801 FIRST_PSEUDO_REGISTER));
1802 for (curr_swapped = false;; curr_swapped = true)
1804 /* Calculate some data common for all alternatives to speed up the
1805 function. */
1806 for (nop = 0; nop < recog_data.n_operands; nop++)
1808 for (nalt = 0, p = recog_data.constraints[nop];
1809 nalt < recog_data.n_alternatives;
1810 nalt++)
1812 insn_constraints[nop * recog_data.n_alternatives + nalt] = p;
1813 while (*p && *p != ',')
1815 /* We only support one commutative marker, the first
1816 one. We already set commutative above. */
1817 if (*p == '%' && commutative < 0)
1818 commutative = nop;
1819 p++;
1821 if (*p)
1822 p++;
1825 for (nalt = 0; nalt < recog_data.n_alternatives; nalt++)
1827 if (!TEST_BIT (preferred, nalt)
1828 || TEST_HARD_REG_BIT (alts, nalt))
1829 continue;
1831 for (nop = 0; nop < recog_data.n_operands; nop++)
1833 int c, len;
1835 rtx op = recog_data.operand[nop];
1836 p = insn_constraints[nop * recog_data.n_alternatives + nalt];
1837 if (*p == 0 || *p == ',')
1838 continue;
1841 switch (c = *p, len = CONSTRAINT_LEN (c, p), c)
1843 case '#':
1844 case ',':
1845 c = '\0';
1846 /* FALLTHRU */
1847 case '\0':
1848 len = 0;
1849 break;
1851 case '%':
1852 /* The commutative modifier is handled above. */
1853 break;
1855 case '0': case '1': case '2': case '3': case '4':
1856 case '5': case '6': case '7': case '8': case '9':
1857 goto op_success;
1858 break;
1860 case 'g':
1861 goto op_success;
1862 break;
1864 default:
1866 enum constraint_num cn = lookup_constraint (p);
1867 switch (get_constraint_type (cn))
1869 case CT_REGISTER:
1870 if (reg_class_for_constraint (cn) != NO_REGS)
1871 goto op_success;
1872 break;
1874 case CT_CONST_INT:
1875 if (CONST_INT_P (op)
1876 && (insn_const_int_ok_for_constraint
1877 (INTVAL (op), cn)))
1878 goto op_success;
1879 break;
1881 case CT_ADDRESS:
1882 case CT_MEMORY:
1883 case CT_SPECIAL_MEMORY:
1884 goto op_success;
1886 case CT_FIXED_FORM:
1887 if (constraint_satisfied_p (op, cn))
1888 goto op_success;
1889 break;
1891 break;
1894 while (p += len, c);
1895 break;
1896 op_success:
1899 if (nop >= recog_data.n_operands)
1900 SET_HARD_REG_BIT (alts, nalt);
1902 if (commutative < 0)
1903 break;
1904 /* Swap forth and back to avoid changing recog_data. */
1905 std::swap (recog_data.operand[commutative],
1906 recog_data.operand[commutative + 1]);
1907 if (curr_swapped)
1908 break;
1912 /* Return the number of the output non-early clobber operand which
1913 should be the same in any case as operand with number OP_NUM (or
1914 negative value if there is no such operand). The function takes
1915 only really possible alternatives into consideration. */
1917 ira_get_dup_out_num (int op_num, HARD_REG_SET &alts)
1919 int curr_alt, c, original, dup;
1920 bool ignore_p, use_commut_op_p;
1921 const char *str;
1923 if (op_num < 0 || recog_data.n_alternatives == 0)
1924 return -1;
1925 /* We should find duplications only for input operands. */
1926 if (recog_data.operand_type[op_num] != OP_IN)
1927 return -1;
1928 str = recog_data.constraints[op_num];
1929 use_commut_op_p = false;
1930 for (;;)
1932 rtx op = recog_data.operand[op_num];
1934 for (curr_alt = 0, ignore_p = !TEST_HARD_REG_BIT (alts, curr_alt),
1935 original = -1;;)
1937 c = *str;
1938 if (c == '\0')
1939 break;
1940 if (c == '#')
1941 ignore_p = true;
1942 else if (c == ',')
1944 curr_alt++;
1945 ignore_p = !TEST_HARD_REG_BIT (alts, curr_alt);
1947 else if (! ignore_p)
1948 switch (c)
1950 case 'g':
1951 goto fail;
1952 default:
1954 enum constraint_num cn = lookup_constraint (str);
1955 enum reg_class cl = reg_class_for_constraint (cn);
1956 if (cl != NO_REGS
1957 && !targetm.class_likely_spilled_p (cl))
1958 goto fail;
1959 if (constraint_satisfied_p (op, cn))
1960 goto fail;
1961 break;
1964 case '0': case '1': case '2': case '3': case '4':
1965 case '5': case '6': case '7': case '8': case '9':
1966 if (original != -1 && original != c)
1967 goto fail;
1968 original = c;
1969 break;
1971 str += CONSTRAINT_LEN (c, str);
1973 if (original == -1)
1974 goto fail;
1975 dup = -1;
1976 for (ignore_p = false, str = recog_data.constraints[original - '0'];
1977 *str != 0;
1978 str++)
1979 if (ignore_p)
1981 if (*str == ',')
1982 ignore_p = false;
1984 else if (*str == '#')
1985 ignore_p = true;
1986 else if (! ignore_p)
1988 if (*str == '=')
1989 dup = original - '0';
1990 /* It is better ignore an alternative with early clobber. */
1991 else if (*str == '&')
1992 goto fail;
1994 if (dup >= 0)
1995 return dup;
1996 fail:
1997 if (use_commut_op_p)
1998 break;
1999 use_commut_op_p = true;
2000 if (recog_data.constraints[op_num][0] == '%')
2001 str = recog_data.constraints[op_num + 1];
2002 else if (op_num > 0 && recog_data.constraints[op_num - 1][0] == '%')
2003 str = recog_data.constraints[op_num - 1];
2004 else
2005 break;
2007 return -1;
2012 /* Search forward to see if the source register of a copy insn dies
2013 before either it or the destination register is modified, but don't
2014 scan past the end of the basic block. If so, we can replace the
2015 source with the destination and let the source die in the copy
2016 insn.
2018 This will reduce the number of registers live in that range and may
2019 enable the destination and the source coalescing, thus often saving
2020 one register in addition to a register-register copy. */
2022 static void
2023 decrease_live_ranges_number (void)
2025 basic_block bb;
2026 rtx_insn *insn;
2027 rtx set, src, dest, dest_death, note;
2028 rtx_insn *p, *q;
2029 int sregno, dregno;
2031 if (! flag_expensive_optimizations)
2032 return;
2034 if (ira_dump_file)
2035 fprintf (ira_dump_file, "Starting decreasing number of live ranges...\n");
2037 FOR_EACH_BB_FN (bb, cfun)
2038 FOR_BB_INSNS (bb, insn)
2040 set = single_set (insn);
2041 if (! set)
2042 continue;
2043 src = SET_SRC (set);
2044 dest = SET_DEST (set);
2045 if (! REG_P (src) || ! REG_P (dest)
2046 || find_reg_note (insn, REG_DEAD, src))
2047 continue;
2048 sregno = REGNO (src);
2049 dregno = REGNO (dest);
2051 /* We don't want to mess with hard regs if register classes
2052 are small. */
2053 if (sregno == dregno
2054 || (targetm.small_register_classes_for_mode_p (GET_MODE (src))
2055 && (sregno < FIRST_PSEUDO_REGISTER
2056 || dregno < FIRST_PSEUDO_REGISTER))
2057 /* We don't see all updates to SP if they are in an
2058 auto-inc memory reference, so we must disallow this
2059 optimization on them. */
2060 || sregno == STACK_POINTER_REGNUM
2061 || dregno == STACK_POINTER_REGNUM)
2062 continue;
2064 dest_death = NULL_RTX;
2066 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
2068 if (! INSN_P (p))
2069 continue;
2070 if (BLOCK_FOR_INSN (p) != bb)
2071 break;
2073 if (reg_set_p (src, p) || reg_set_p (dest, p)
2074 /* If SRC is an asm-declared register, it must not be
2075 replaced in any asm. Unfortunately, the REG_EXPR
2076 tree for the asm variable may be absent in the SRC
2077 rtx, so we can't check the actual register
2078 declaration easily (the asm operand will have it,
2079 though). To avoid complicating the test for a rare
2080 case, we just don't perform register replacement
2081 for a hard reg mentioned in an asm. */
2082 || (sregno < FIRST_PSEUDO_REGISTER
2083 && asm_noperands (PATTERN (p)) >= 0
2084 && reg_overlap_mentioned_p (src, PATTERN (p)))
2085 /* Don't change hard registers used by a call. */
2086 || (CALL_P (p) && sregno < FIRST_PSEUDO_REGISTER
2087 && find_reg_fusage (p, USE, src))
2088 /* Don't change a USE of a register. */
2089 || (GET_CODE (PATTERN (p)) == USE
2090 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
2091 break;
2093 /* See if all of SRC dies in P. This test is slightly
2094 more conservative than it needs to be. */
2095 if ((note = find_regno_note (p, REG_DEAD, sregno))
2096 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
2098 int failed = 0;
2100 /* We can do the optimization. Scan forward from INSN
2101 again, replacing regs as we go. Set FAILED if a
2102 replacement can't be done. In that case, we can't
2103 move the death note for SRC. This should be
2104 rare. */
2106 /* Set to stop at next insn. */
2107 for (q = next_real_insn (insn);
2108 q != next_real_insn (p);
2109 q = next_real_insn (q))
2111 if (reg_overlap_mentioned_p (src, PATTERN (q)))
2113 /* If SRC is a hard register, we might miss
2114 some overlapping registers with
2115 validate_replace_rtx, so we would have to
2116 undo it. We can't if DEST is present in
2117 the insn, so fail in that combination of
2118 cases. */
2119 if (sregno < FIRST_PSEUDO_REGISTER
2120 && reg_mentioned_p (dest, PATTERN (q)))
2121 failed = 1;
2123 /* Attempt to replace all uses. */
2124 else if (!validate_replace_rtx (src, dest, q))
2125 failed = 1;
2127 /* If this succeeded, but some part of the
2128 register is still present, undo the
2129 replacement. */
2130 else if (sregno < FIRST_PSEUDO_REGISTER
2131 && reg_overlap_mentioned_p (src, PATTERN (q)))
2133 validate_replace_rtx (dest, src, q);
2134 failed = 1;
2138 /* If DEST dies here, remove the death note and
2139 save it for later. Make sure ALL of DEST dies
2140 here; again, this is overly conservative. */
2141 if (! dest_death
2142 && (dest_death = find_regno_note (q, REG_DEAD, dregno)))
2144 if (GET_MODE (XEXP (dest_death, 0)) == GET_MODE (dest))
2145 remove_note (q, dest_death);
2146 else
2148 failed = 1;
2149 dest_death = 0;
2154 if (! failed)
2156 /* Move death note of SRC from P to INSN. */
2157 remove_note (p, note);
2158 XEXP (note, 1) = REG_NOTES (insn);
2159 REG_NOTES (insn) = note;
2162 /* DEST is also dead if INSN has a REG_UNUSED note for
2163 DEST. */
2164 if (! dest_death
2165 && (dest_death
2166 = find_regno_note (insn, REG_UNUSED, dregno)))
2168 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
2169 remove_note (insn, dest_death);
2172 /* Put death note of DEST on P if we saw it die. */
2173 if (dest_death)
2175 XEXP (dest_death, 1) = REG_NOTES (p);
2176 REG_NOTES (p) = dest_death;
2178 break;
2181 /* If SRC is a hard register which is set or killed in
2182 some other way, we can't do this optimization. */
2183 else if (sregno < FIRST_PSEUDO_REGISTER && dead_or_set_p (p, src))
2184 break;
2191 /* Return nonzero if REGNO is a particularly bad choice for reloading X. */
2192 static bool
2193 ira_bad_reload_regno_1 (int regno, rtx x)
2195 int x_regno, n, i;
2196 ira_allocno_t a;
2197 enum reg_class pref;
2199 /* We only deal with pseudo regs. */
2200 if (! x || GET_CODE (x) != REG)
2201 return false;
2203 x_regno = REGNO (x);
2204 if (x_regno < FIRST_PSEUDO_REGISTER)
2205 return false;
2207 /* If the pseudo prefers REGNO explicitly, then do not consider
2208 REGNO a bad spill choice. */
2209 pref = reg_preferred_class (x_regno);
2210 if (reg_class_size[pref] == 1)
2211 return !TEST_HARD_REG_BIT (reg_class_contents[pref], regno);
2213 /* If the pseudo conflicts with REGNO, then we consider REGNO a
2214 poor choice for a reload regno. */
2215 a = ira_regno_allocno_map[x_regno];
2216 n = ALLOCNO_NUM_OBJECTS (a);
2217 for (i = 0; i < n; i++)
2219 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2220 if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), regno))
2221 return true;
2223 return false;
2226 /* Return nonzero if REGNO is a particularly bad choice for reloading
2227 IN or OUT. */
2228 bool
2229 ira_bad_reload_regno (int regno, rtx in, rtx out)
2231 return (ira_bad_reload_regno_1 (regno, in)
2232 || ira_bad_reload_regno_1 (regno, out));
2235 /* Add register clobbers from asm statements. */
2236 static void
2237 compute_regs_asm_clobbered (void)
2239 basic_block bb;
2241 FOR_EACH_BB_FN (bb, cfun)
2243 rtx_insn *insn;
2244 FOR_BB_INSNS_REVERSE (bb, insn)
2246 df_ref def;
2248 if (NONDEBUG_INSN_P (insn) && asm_noperands (PATTERN (insn)) >= 0)
2249 FOR_EACH_INSN_DEF (def, insn)
2251 unsigned int dregno = DF_REF_REGNO (def);
2252 if (HARD_REGISTER_NUM_P (dregno))
2253 add_to_hard_reg_set (&crtl->asm_clobbers,
2254 GET_MODE (DF_REF_REAL_REG (def)),
2255 dregno);
2262 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and
2263 REGS_EVER_LIVE. */
2264 void
2265 ira_setup_eliminable_regset (void)
2267 int i;
2268 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
2270 /* Setup is_leaf as frame_pointer_required may use it. This function
2271 is called by sched_init before ira if scheduling is enabled. */
2272 crtl->is_leaf = leaf_function_p ();
2274 /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
2275 sp for alloca. So we can't eliminate the frame pointer in that
2276 case. At some point, we should improve this by emitting the
2277 sp-adjusting insns for this case. */
2278 frame_pointer_needed
2279 = (! flag_omit_frame_pointer
2280 || (cfun->calls_alloca && EXIT_IGNORE_STACK)
2281 /* We need the frame pointer to catch stack overflow exceptions if
2282 the stack pointer is moving (as for the alloca case just above). */
2283 || (STACK_CHECK_MOVING_SP
2284 && flag_stack_check
2285 && flag_exceptions
2286 && cfun->can_throw_non_call_exceptions)
2287 || crtl->accesses_prior_frames
2288 || (SUPPORTS_STACK_ALIGNMENT && crtl->stack_realign_needed)
2289 || targetm.frame_pointer_required ());
2291 /* The chance that FRAME_POINTER_NEEDED is changed from inspecting
2292 RTL is very small. So if we use frame pointer for RA and RTL
2293 actually prevents this, we will spill pseudos assigned to the
2294 frame pointer in LRA. */
2296 if (frame_pointer_needed)
2297 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
2299 COPY_HARD_REG_SET (ira_no_alloc_regs, no_unit_alloc_regs);
2300 CLEAR_HARD_REG_SET (eliminable_regset);
2302 compute_regs_asm_clobbered ();
2304 /* Build the regset of all eliminable registers and show we can't
2305 use those that we already know won't be eliminated. */
2306 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
2308 bool cannot_elim
2309 = (! targetm.can_eliminate (eliminables[i].from, eliminables[i].to)
2310 || (eliminables[i].to == STACK_POINTER_REGNUM && frame_pointer_needed));
2312 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, eliminables[i].from))
2314 SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
2316 if (cannot_elim)
2317 SET_HARD_REG_BIT (ira_no_alloc_regs, eliminables[i].from);
2319 else if (cannot_elim)
2320 error ("%s cannot be used in asm here",
2321 reg_names[eliminables[i].from]);
2322 else
2323 df_set_regs_ever_live (eliminables[i].from, true);
2325 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
2327 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM))
2329 SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
2330 if (frame_pointer_needed)
2331 SET_HARD_REG_BIT (ira_no_alloc_regs, HARD_FRAME_POINTER_REGNUM);
2333 else if (frame_pointer_needed)
2334 error ("%s cannot be used in asm here",
2335 reg_names[HARD_FRAME_POINTER_REGNUM]);
2336 else
2337 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
2343 /* Vector of substitutions of register numbers,
2344 used to map pseudo regs into hardware regs.
2345 This is set up as a result of register allocation.
2346 Element N is the hard reg assigned to pseudo reg N,
2347 or is -1 if no hard reg was assigned.
2348 If N is a hard reg number, element N is N. */
2349 short *reg_renumber;
2351 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
2352 the allocation found by IRA. */
2353 static void
2354 setup_reg_renumber (void)
2356 int regno, hard_regno;
2357 ira_allocno_t a;
2358 ira_allocno_iterator ai;
2360 caller_save_needed = 0;
2361 FOR_EACH_ALLOCNO (a, ai)
2363 if (ira_use_lra_p && ALLOCNO_CAP_MEMBER (a) != NULL)
2364 continue;
2365 /* There are no caps at this point. */
2366 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2367 if (! ALLOCNO_ASSIGNED_P (a))
2368 /* It can happen if A is not referenced but partially anticipated
2369 somewhere in a region. */
2370 ALLOCNO_ASSIGNED_P (a) = true;
2371 ira_free_allocno_updated_costs (a);
2372 hard_regno = ALLOCNO_HARD_REGNO (a);
2373 regno = ALLOCNO_REGNO (a);
2374 reg_renumber[regno] = (hard_regno < 0 ? -1 : hard_regno);
2375 if (hard_regno >= 0)
2377 int i, nwords;
2378 enum reg_class pclass;
2379 ira_object_t obj;
2381 pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)];
2382 nwords = ALLOCNO_NUM_OBJECTS (a);
2383 for (i = 0; i < nwords; i++)
2385 obj = ALLOCNO_OBJECT (a, i);
2386 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
2387 reg_class_contents[pclass]);
2389 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
2390 && ira_hard_reg_set_intersection_p (hard_regno, ALLOCNO_MODE (a),
2391 call_used_reg_set))
2393 ira_assert (!optimize || flag_caller_saves
2394 || (ALLOCNO_CALLS_CROSSED_NUM (a)
2395 == ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a))
2396 || regno >= ira_reg_equiv_len
2397 || ira_equiv_no_lvalue_p (regno));
2398 caller_save_needed = 1;
2404 /* Set up allocno assignment flags for further allocation
2405 improvements. */
2406 static void
2407 setup_allocno_assignment_flags (void)
2409 int hard_regno;
2410 ira_allocno_t a;
2411 ira_allocno_iterator ai;
2413 FOR_EACH_ALLOCNO (a, ai)
2415 if (! ALLOCNO_ASSIGNED_P (a))
2416 /* It can happen if A is not referenced but partially anticipated
2417 somewhere in a region. */
2418 ira_free_allocno_updated_costs (a);
2419 hard_regno = ALLOCNO_HARD_REGNO (a);
2420 /* Don't assign hard registers to allocnos which are destination
2421 of removed store at the end of loop. It has no sense to keep
2422 the same value in different hard registers. It is also
2423 impossible to assign hard registers correctly to such
2424 allocnos because the cost info and info about intersected
2425 calls are incorrect for them. */
2426 ALLOCNO_ASSIGNED_P (a) = (hard_regno >= 0
2427 || ALLOCNO_EMIT_DATA (a)->mem_optimized_dest_p
2428 || (ALLOCNO_MEMORY_COST (a)
2429 - ALLOCNO_CLASS_COST (a)) < 0);
2430 ira_assert
2431 (hard_regno < 0
2432 || ira_hard_reg_in_set_p (hard_regno, ALLOCNO_MODE (a),
2433 reg_class_contents[ALLOCNO_CLASS (a)]));
2437 /* Evaluate overall allocation cost and the costs for using hard
2438 registers and memory for allocnos. */
2439 static void
2440 calculate_allocation_cost (void)
2442 int hard_regno, cost;
2443 ira_allocno_t a;
2444 ira_allocno_iterator ai;
2446 ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
2447 FOR_EACH_ALLOCNO (a, ai)
2449 hard_regno = ALLOCNO_HARD_REGNO (a);
2450 ira_assert (hard_regno < 0
2451 || (ira_hard_reg_in_set_p
2452 (hard_regno, ALLOCNO_MODE (a),
2453 reg_class_contents[ALLOCNO_CLASS (a)])));
2454 if (hard_regno < 0)
2456 cost = ALLOCNO_MEMORY_COST (a);
2457 ira_mem_cost += cost;
2459 else if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
2461 cost = (ALLOCNO_HARD_REG_COSTS (a)
2462 [ira_class_hard_reg_index
2463 [ALLOCNO_CLASS (a)][hard_regno]]);
2464 ira_reg_cost += cost;
2466 else
2468 cost = ALLOCNO_CLASS_COST (a);
2469 ira_reg_cost += cost;
2471 ira_overall_cost += cost;
2474 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2476 fprintf (ira_dump_file,
2477 "+++Costs: overall %" PRId64
2478 ", reg %" PRId64
2479 ", mem %" PRId64
2480 ", ld %" PRId64
2481 ", st %" PRId64
2482 ", move %" PRId64,
2483 ira_overall_cost, ira_reg_cost, ira_mem_cost,
2484 ira_load_cost, ira_store_cost, ira_shuffle_cost);
2485 fprintf (ira_dump_file, "\n+++ move loops %d, new jumps %d\n",
2486 ira_move_loops_num, ira_additional_jumps_num);
2491 #ifdef ENABLE_IRA_CHECKING
2492 /* Check the correctness of the allocation. We do need this because
2493 of complicated code to transform more one region internal
2494 representation into one region representation. */
2495 static void
2496 check_allocation (void)
2498 ira_allocno_t a;
2499 int hard_regno, nregs, conflict_nregs;
2500 ira_allocno_iterator ai;
2502 FOR_EACH_ALLOCNO (a, ai)
2504 int n = ALLOCNO_NUM_OBJECTS (a);
2505 int i;
2507 if (ALLOCNO_CAP_MEMBER (a) != NULL
2508 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
2509 continue;
2510 nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (a));
2511 if (nregs == 1)
2512 /* We allocated a single hard register. */
2513 n = 1;
2514 else if (n > 1)
2515 /* We allocated multiple hard registers, and we will test
2516 conflicts in a granularity of single hard regs. */
2517 nregs = 1;
2519 for (i = 0; i < n; i++)
2521 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2522 ira_object_t conflict_obj;
2523 ira_object_conflict_iterator oci;
2524 int this_regno = hard_regno;
2525 if (n > 1)
2527 if (REG_WORDS_BIG_ENDIAN)
2528 this_regno += n - i - 1;
2529 else
2530 this_regno += i;
2532 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2534 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2535 int conflict_hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
2536 if (conflict_hard_regno < 0)
2537 continue;
2539 conflict_nregs = hard_regno_nregs (conflict_hard_regno,
2540 ALLOCNO_MODE (conflict_a));
2542 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1
2543 && conflict_nregs == ALLOCNO_NUM_OBJECTS (conflict_a))
2545 if (REG_WORDS_BIG_ENDIAN)
2546 conflict_hard_regno += (ALLOCNO_NUM_OBJECTS (conflict_a)
2547 - OBJECT_SUBWORD (conflict_obj) - 1);
2548 else
2549 conflict_hard_regno += OBJECT_SUBWORD (conflict_obj);
2550 conflict_nregs = 1;
2553 if ((conflict_hard_regno <= this_regno
2554 && this_regno < conflict_hard_regno + conflict_nregs)
2555 || (this_regno <= conflict_hard_regno
2556 && conflict_hard_regno < this_regno + nregs))
2558 fprintf (stderr, "bad allocation for %d and %d\n",
2559 ALLOCNO_REGNO (a), ALLOCNO_REGNO (conflict_a));
2560 gcc_unreachable ();
2566 #endif
2568 /* Allocate REG_EQUIV_INIT. Set up it from IRA_REG_EQUIV which should
2569 be already calculated. */
2570 static void
2571 setup_reg_equiv_init (void)
2573 int i;
2574 int max_regno = max_reg_num ();
2576 for (i = 0; i < max_regno; i++)
2577 reg_equiv_init (i) = ira_reg_equiv[i].init_insns;
2580 /* Update equiv regno from movement of FROM_REGNO to TO_REGNO. INSNS
2581 are insns which were generated for such movement. It is assumed
2582 that FROM_REGNO and TO_REGNO always have the same value at the
2583 point of any move containing such registers. This function is used
2584 to update equiv info for register shuffles on the region borders
2585 and for caller save/restore insns. */
2586 void
2587 ira_update_equiv_info_by_shuffle_insn (int to_regno, int from_regno, rtx_insn *insns)
2589 rtx_insn *insn;
2590 rtx x, note;
2592 if (! ira_reg_equiv[from_regno].defined_p
2593 && (! ira_reg_equiv[to_regno].defined_p
2594 || ((x = ira_reg_equiv[to_regno].memory) != NULL_RTX
2595 && ! MEM_READONLY_P (x))))
2596 return;
2597 insn = insns;
2598 if (NEXT_INSN (insn) != NULL_RTX)
2600 if (! ira_reg_equiv[to_regno].defined_p)
2602 ira_assert (ira_reg_equiv[to_regno].init_insns == NULL_RTX);
2603 return;
2605 ira_reg_equiv[to_regno].defined_p = false;
2606 ira_reg_equiv[to_regno].memory
2607 = ira_reg_equiv[to_regno].constant
2608 = ira_reg_equiv[to_regno].invariant
2609 = ira_reg_equiv[to_regno].init_insns = NULL;
2610 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2611 fprintf (ira_dump_file,
2612 " Invalidating equiv info for reg %d\n", to_regno);
2613 return;
2615 /* It is possible that FROM_REGNO still has no equivalence because
2616 in shuffles to_regno<-from_regno and from_regno<-to_regno the 2nd
2617 insn was not processed yet. */
2618 if (ira_reg_equiv[from_regno].defined_p)
2620 ira_reg_equiv[to_regno].defined_p = true;
2621 if ((x = ira_reg_equiv[from_regno].memory) != NULL_RTX)
2623 ira_assert (ira_reg_equiv[from_regno].invariant == NULL_RTX
2624 && ira_reg_equiv[from_regno].constant == NULL_RTX);
2625 ira_assert (ira_reg_equiv[to_regno].memory == NULL_RTX
2626 || rtx_equal_p (ira_reg_equiv[to_regno].memory, x));
2627 ira_reg_equiv[to_regno].memory = x;
2628 if (! MEM_READONLY_P (x))
2629 /* We don't add the insn to insn init list because memory
2630 equivalence is just to say what memory is better to use
2631 when the pseudo is spilled. */
2632 return;
2634 else if ((x = ira_reg_equiv[from_regno].constant) != NULL_RTX)
2636 ira_assert (ira_reg_equiv[from_regno].invariant == NULL_RTX);
2637 ira_assert (ira_reg_equiv[to_regno].constant == NULL_RTX
2638 || rtx_equal_p (ira_reg_equiv[to_regno].constant, x));
2639 ira_reg_equiv[to_regno].constant = x;
2641 else
2643 x = ira_reg_equiv[from_regno].invariant;
2644 ira_assert (x != NULL_RTX);
2645 ira_assert (ira_reg_equiv[to_regno].invariant == NULL_RTX
2646 || rtx_equal_p (ira_reg_equiv[to_regno].invariant, x));
2647 ira_reg_equiv[to_regno].invariant = x;
2649 if (find_reg_note (insn, REG_EQUIV, x) == NULL_RTX)
2651 note = set_unique_reg_note (insn, REG_EQUIV, copy_rtx (x));
2652 gcc_assert (note != NULL_RTX);
2653 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2655 fprintf (ira_dump_file,
2656 " Adding equiv note to insn %u for reg %d ",
2657 INSN_UID (insn), to_regno);
2658 dump_value_slim (ira_dump_file, x, 1);
2659 fprintf (ira_dump_file, "\n");
2663 ira_reg_equiv[to_regno].init_insns
2664 = gen_rtx_INSN_LIST (VOIDmode, insn,
2665 ira_reg_equiv[to_regno].init_insns);
2666 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2667 fprintf (ira_dump_file,
2668 " Adding equiv init move insn %u to reg %d\n",
2669 INSN_UID (insn), to_regno);
2672 /* Fix values of array REG_EQUIV_INIT after live range splitting done
2673 by IRA. */
2674 static void
2675 fix_reg_equiv_init (void)
2677 int max_regno = max_reg_num ();
2678 int i, new_regno, max;
2679 rtx set;
2680 rtx_insn_list *x, *next, *prev;
2681 rtx_insn *insn;
2683 if (max_regno_before_ira < max_regno)
2685 max = vec_safe_length (reg_equivs);
2686 grow_reg_equivs ();
2687 for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
2688 for (prev = NULL, x = reg_equiv_init (i);
2689 x != NULL_RTX;
2690 x = next)
2692 next = x->next ();
2693 insn = x->insn ();
2694 set = single_set (insn);
2695 ira_assert (set != NULL_RTX
2696 && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))));
2697 if (REG_P (SET_DEST (set))
2698 && ((int) REGNO (SET_DEST (set)) == i
2699 || (int) ORIGINAL_REGNO (SET_DEST (set)) == i))
2700 new_regno = REGNO (SET_DEST (set));
2701 else if (REG_P (SET_SRC (set))
2702 && ((int) REGNO (SET_SRC (set)) == i
2703 || (int) ORIGINAL_REGNO (SET_SRC (set)) == i))
2704 new_regno = REGNO (SET_SRC (set));
2705 else
2706 gcc_unreachable ();
2707 if (new_regno == i)
2708 prev = x;
2709 else
2711 /* Remove the wrong list element. */
2712 if (prev == NULL_RTX)
2713 reg_equiv_init (i) = next;
2714 else
2715 XEXP (prev, 1) = next;
2716 XEXP (x, 1) = reg_equiv_init (new_regno);
2717 reg_equiv_init (new_regno) = x;
2723 #ifdef ENABLE_IRA_CHECKING
2724 /* Print redundant memory-memory copies. */
2725 static void
2726 print_redundant_copies (void)
2728 int hard_regno;
2729 ira_allocno_t a;
2730 ira_copy_t cp, next_cp;
2731 ira_allocno_iterator ai;
2733 FOR_EACH_ALLOCNO (a, ai)
2735 if (ALLOCNO_CAP_MEMBER (a) != NULL)
2736 /* It is a cap. */
2737 continue;
2738 hard_regno = ALLOCNO_HARD_REGNO (a);
2739 if (hard_regno >= 0)
2740 continue;
2741 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2742 if (cp->first == a)
2743 next_cp = cp->next_first_allocno_copy;
2744 else
2746 next_cp = cp->next_second_allocno_copy;
2747 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL
2748 && cp->insn != NULL_RTX
2749 && ALLOCNO_HARD_REGNO (cp->first) == hard_regno)
2750 fprintf (ira_dump_file,
2751 " Redundant move from %d(freq %d):%d\n",
2752 INSN_UID (cp->insn), cp->freq, hard_regno);
2756 #endif
2758 /* Setup preferred and alternative classes for new pseudo-registers
2759 created by IRA starting with START. */
2760 static void
2761 setup_preferred_alternate_classes_for_new_pseudos (int start)
2763 int i, old_regno;
2764 int max_regno = max_reg_num ();
2766 for (i = start; i < max_regno; i++)
2768 old_regno = ORIGINAL_REGNO (regno_reg_rtx[i]);
2769 ira_assert (i != old_regno);
2770 setup_reg_classes (i, reg_preferred_class (old_regno),
2771 reg_alternate_class (old_regno),
2772 reg_allocno_class (old_regno));
2773 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2774 fprintf (ira_dump_file,
2775 " New r%d: setting preferred %s, alternative %s\n",
2776 i, reg_class_names[reg_preferred_class (old_regno)],
2777 reg_class_names[reg_alternate_class (old_regno)]);
2782 /* The number of entries allocated in reg_info. */
2783 static int allocated_reg_info_size;
2785 /* Regional allocation can create new pseudo-registers. This function
2786 expands some arrays for pseudo-registers. */
2787 static void
2788 expand_reg_info (void)
2790 int i;
2791 int size = max_reg_num ();
2793 resize_reg_info ();
2794 for (i = allocated_reg_info_size; i < size; i++)
2795 setup_reg_classes (i, GENERAL_REGS, ALL_REGS, GENERAL_REGS);
2796 setup_preferred_alternate_classes_for_new_pseudos (allocated_reg_info_size);
2797 allocated_reg_info_size = size;
2800 /* Return TRUE if there is too high register pressure in the function.
2801 It is used to decide when stack slot sharing is worth to do. */
2802 static bool
2803 too_high_register_pressure_p (void)
2805 int i;
2806 enum reg_class pclass;
2808 for (i = 0; i < ira_pressure_classes_num; i++)
2810 pclass = ira_pressure_classes[i];
2811 if (ira_loop_tree_root->reg_pressure[pclass] > 10000)
2812 return true;
2814 return false;
2819 /* Indicate that hard register number FROM was eliminated and replaced with
2820 an offset from hard register number TO. The status of hard registers live
2821 at the start of a basic block is updated by replacing a use of FROM with
2822 a use of TO. */
2824 void
2825 mark_elimination (int from, int to)
2827 basic_block bb;
2828 bitmap r;
2830 FOR_EACH_BB_FN (bb, cfun)
2832 r = DF_LR_IN (bb);
2833 if (bitmap_bit_p (r, from))
2835 bitmap_clear_bit (r, from);
2836 bitmap_set_bit (r, to);
2838 if (! df_live)
2839 continue;
2840 r = DF_LIVE_IN (bb);
2841 if (bitmap_bit_p (r, from))
2843 bitmap_clear_bit (r, from);
2844 bitmap_set_bit (r, to);
2851 /* The length of the following array. */
2852 int ira_reg_equiv_len;
2854 /* Info about equiv. info for each register. */
2855 struct ira_reg_equiv_s *ira_reg_equiv;
2857 /* Expand ira_reg_equiv if necessary. */
2858 void
2859 ira_expand_reg_equiv (void)
2861 int old = ira_reg_equiv_len;
2863 if (ira_reg_equiv_len > max_reg_num ())
2864 return;
2865 ira_reg_equiv_len = max_reg_num () * 3 / 2 + 1;
2866 ira_reg_equiv
2867 = (struct ira_reg_equiv_s *) xrealloc (ira_reg_equiv,
2868 ira_reg_equiv_len
2869 * sizeof (struct ira_reg_equiv_s));
2870 gcc_assert (old < ira_reg_equiv_len);
2871 memset (ira_reg_equiv + old, 0,
2872 sizeof (struct ira_reg_equiv_s) * (ira_reg_equiv_len - old));
2875 static void
2876 init_reg_equiv (void)
2878 ira_reg_equiv_len = 0;
2879 ira_reg_equiv = NULL;
2880 ira_expand_reg_equiv ();
2883 static void
2884 finish_reg_equiv (void)
2886 free (ira_reg_equiv);
2891 struct equivalence
2893 /* Set when a REG_EQUIV note is found or created. Use to
2894 keep track of what memory accesses might be created later,
2895 e.g. by reload. */
2896 rtx replacement;
2897 rtx *src_p;
2899 /* The list of each instruction which initializes this register.
2901 NULL indicates we know nothing about this register's equivalence
2902 properties.
2904 An INSN_LIST with a NULL insn indicates this pseudo is already
2905 known to not have a valid equivalence. */
2906 rtx_insn_list *init_insns;
2908 /* Loop depth is used to recognize equivalences which appear
2909 to be present within the same loop (or in an inner loop). */
2910 short loop_depth;
2911 /* Nonzero if this had a preexisting REG_EQUIV note. */
2912 unsigned char is_arg_equivalence : 1;
2913 /* Set when an attempt should be made to replace a register
2914 with the associated src_p entry. */
2915 unsigned char replace : 1;
2916 /* Set if this register has no known equivalence. */
2917 unsigned char no_equiv : 1;
2918 /* Set if this register is mentioned in a paradoxical subreg. */
2919 unsigned char pdx_subregs : 1;
2922 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
2923 structure for that register. */
2924 static struct equivalence *reg_equiv;
2926 /* Used for communication between the following two functions. */
2927 struct equiv_mem_data
2929 /* A MEM that we wish to ensure remains unchanged. */
2930 rtx equiv_mem;
2932 /* Set true if EQUIV_MEM is modified. */
2933 bool equiv_mem_modified;
2936 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
2937 Called via note_stores. */
2938 static void
2939 validate_equiv_mem_from_store (rtx dest, const_rtx set ATTRIBUTE_UNUSED,
2940 void *data)
2942 struct equiv_mem_data *info = (struct equiv_mem_data *) data;
2944 if ((REG_P (dest)
2945 && reg_overlap_mentioned_p (dest, info->equiv_mem))
2946 || (MEM_P (dest)
2947 && anti_dependence (info->equiv_mem, dest)))
2948 info->equiv_mem_modified = true;
2951 enum valid_equiv { valid_none, valid_combine, valid_reload };
2953 /* Verify that no store between START and the death of REG invalidates
2954 MEMREF. MEMREF is invalidated by modifying a register used in MEMREF,
2955 by storing into an overlapping memory location, or with a non-const
2956 CALL_INSN.
2958 Return VALID_RELOAD if MEMREF remains valid for both reload and
2959 combine_and_move insns, VALID_COMBINE if only valid for
2960 combine_and_move_insns, and VALID_NONE otherwise. */
2961 static enum valid_equiv
2962 validate_equiv_mem (rtx_insn *start, rtx reg, rtx memref)
2964 rtx_insn *insn;
2965 rtx note;
2966 struct equiv_mem_data info = { memref, false };
2967 enum valid_equiv ret = valid_reload;
2969 /* If the memory reference has side effects or is volatile, it isn't a
2970 valid equivalence. */
2971 if (side_effects_p (memref))
2972 return valid_none;
2974 for (insn = start; insn; insn = NEXT_INSN (insn))
2976 if (!INSN_P (insn))
2977 continue;
2979 if (find_reg_note (insn, REG_DEAD, reg))
2980 return ret;
2982 if (CALL_P (insn))
2984 /* We can combine a reg def from one insn into a reg use in
2985 another over a call if the memory is readonly or the call
2986 const/pure. However, we can't set reg_equiv notes up for
2987 reload over any call. The problem is the equivalent form
2988 may reference a pseudo which gets assigned a call
2989 clobbered hard reg. When we later replace REG with its
2990 equivalent form, the value in the call-clobbered reg has
2991 been changed and all hell breaks loose. */
2992 ret = valid_combine;
2993 if (!MEM_READONLY_P (memref)
2994 && !RTL_CONST_OR_PURE_CALL_P (insn))
2995 return valid_none;
2998 note_stores (PATTERN (insn), validate_equiv_mem_from_store, &info);
2999 if (info.equiv_mem_modified)
3000 return valid_none;
3002 /* If a register mentioned in MEMREF is modified via an
3003 auto-increment, we lose the equivalence. Do the same if one
3004 dies; although we could extend the life, it doesn't seem worth
3005 the trouble. */
3007 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
3008 if ((REG_NOTE_KIND (note) == REG_INC
3009 || REG_NOTE_KIND (note) == REG_DEAD)
3010 && REG_P (XEXP (note, 0))
3011 && reg_overlap_mentioned_p (XEXP (note, 0), memref))
3012 return valid_none;
3015 return valid_none;
3018 /* Returns zero if X is known to be invariant. */
3019 static int
3020 equiv_init_varies_p (rtx x)
3022 RTX_CODE code = GET_CODE (x);
3023 int i;
3024 const char *fmt;
3026 switch (code)
3028 case MEM:
3029 return !MEM_READONLY_P (x) || equiv_init_varies_p (XEXP (x, 0));
3031 case CONST:
3032 CASE_CONST_ANY:
3033 case SYMBOL_REF:
3034 case LABEL_REF:
3035 return 0;
3037 case REG:
3038 return reg_equiv[REGNO (x)].replace == 0 && rtx_varies_p (x, 0);
3040 case ASM_OPERANDS:
3041 if (MEM_VOLATILE_P (x))
3042 return 1;
3044 /* Fall through. */
3046 default:
3047 break;
3050 fmt = GET_RTX_FORMAT (code);
3051 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3052 if (fmt[i] == 'e')
3054 if (equiv_init_varies_p (XEXP (x, i)))
3055 return 1;
3057 else if (fmt[i] == 'E')
3059 int j;
3060 for (j = 0; j < XVECLEN (x, i); j++)
3061 if (equiv_init_varies_p (XVECEXP (x, i, j)))
3062 return 1;
3065 return 0;
3068 /* Returns nonzero if X (used to initialize register REGNO) is movable.
3069 X is only movable if the registers it uses have equivalent initializations
3070 which appear to be within the same loop (or in an inner loop) and movable
3071 or if they are not candidates for local_alloc and don't vary. */
3072 static int
3073 equiv_init_movable_p (rtx x, int regno)
3075 int i, j;
3076 const char *fmt;
3077 enum rtx_code code = GET_CODE (x);
3079 switch (code)
3081 case SET:
3082 return equiv_init_movable_p (SET_SRC (x), regno);
3084 case CC0:
3085 case CLOBBER:
3086 return 0;
3088 case PRE_INC:
3089 case PRE_DEC:
3090 case POST_INC:
3091 case POST_DEC:
3092 case PRE_MODIFY:
3093 case POST_MODIFY:
3094 return 0;
3096 case REG:
3097 return ((reg_equiv[REGNO (x)].loop_depth >= reg_equiv[regno].loop_depth
3098 && reg_equiv[REGNO (x)].replace)
3099 || (REG_BASIC_BLOCK (REGNO (x)) < NUM_FIXED_BLOCKS
3100 && ! rtx_varies_p (x, 0)));
3102 case UNSPEC_VOLATILE:
3103 return 0;
3105 case ASM_OPERANDS:
3106 if (MEM_VOLATILE_P (x))
3107 return 0;
3109 /* Fall through. */
3111 default:
3112 break;
3115 fmt = GET_RTX_FORMAT (code);
3116 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3117 switch (fmt[i])
3119 case 'e':
3120 if (! equiv_init_movable_p (XEXP (x, i), regno))
3121 return 0;
3122 break;
3123 case 'E':
3124 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3125 if (! equiv_init_movable_p (XVECEXP (x, i, j), regno))
3126 return 0;
3127 break;
3130 return 1;
3133 /* TRUE if X references a memory location that would be affected by a store
3134 to MEMREF. */
3135 static int
3136 memref_referenced_p (rtx memref, rtx x)
3138 int i, j;
3139 const char *fmt;
3140 enum rtx_code code = GET_CODE (x);
3142 switch (code)
3144 case CONST:
3145 case LABEL_REF:
3146 case SYMBOL_REF:
3147 CASE_CONST_ANY:
3148 case PC:
3149 case CC0:
3150 case HIGH:
3151 case LO_SUM:
3152 return 0;
3154 case REG:
3155 return (reg_equiv[REGNO (x)].replacement
3156 && memref_referenced_p (memref,
3157 reg_equiv[REGNO (x)].replacement));
3159 case MEM:
3160 if (true_dependence (memref, VOIDmode, x))
3161 return 1;
3162 break;
3164 case SET:
3165 /* If we are setting a MEM, it doesn't count (its address does), but any
3166 other SET_DEST that has a MEM in it is referencing the MEM. */
3167 if (MEM_P (SET_DEST (x)))
3169 if (memref_referenced_p (memref, XEXP (SET_DEST (x), 0)))
3170 return 1;
3172 else if (memref_referenced_p (memref, SET_DEST (x)))
3173 return 1;
3175 return memref_referenced_p (memref, SET_SRC (x));
3177 default:
3178 break;
3181 fmt = GET_RTX_FORMAT (code);
3182 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3183 switch (fmt[i])
3185 case 'e':
3186 if (memref_referenced_p (memref, XEXP (x, i)))
3187 return 1;
3188 break;
3189 case 'E':
3190 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3191 if (memref_referenced_p (memref, XVECEXP (x, i, j)))
3192 return 1;
3193 break;
3196 return 0;
3199 /* TRUE if some insn in the range (START, END] references a memory location
3200 that would be affected by a store to MEMREF.
3202 Callers should not call this routine if START is after END in the
3203 RTL chain. */
3205 static int
3206 memref_used_between_p (rtx memref, rtx_insn *start, rtx_insn *end)
3208 rtx_insn *insn;
3210 for (insn = NEXT_INSN (start);
3211 insn && insn != NEXT_INSN (end);
3212 insn = NEXT_INSN (insn))
3214 if (!NONDEBUG_INSN_P (insn))
3215 continue;
3217 if (memref_referenced_p (memref, PATTERN (insn)))
3218 return 1;
3220 /* Nonconst functions may access memory. */
3221 if (CALL_P (insn) && (! RTL_CONST_CALL_P (insn)))
3222 return 1;
3225 gcc_assert (insn == NEXT_INSN (end));
3226 return 0;
3229 /* Mark REG as having no known equivalence.
3230 Some instructions might have been processed before and furnished
3231 with REG_EQUIV notes for this register; these notes will have to be
3232 removed.
3233 STORE is the piece of RTL that does the non-constant / conflicting
3234 assignment - a SET, CLOBBER or REG_INC note. It is currently not used,
3235 but needs to be there because this function is called from note_stores. */
3236 static void
3237 no_equiv (rtx reg, const_rtx store ATTRIBUTE_UNUSED,
3238 void *data ATTRIBUTE_UNUSED)
3240 int regno;
3241 rtx_insn_list *list;
3243 if (!REG_P (reg))
3244 return;
3245 regno = REGNO (reg);
3246 reg_equiv[regno].no_equiv = 1;
3247 list = reg_equiv[regno].init_insns;
3248 if (list && list->insn () == NULL)
3249 return;
3250 reg_equiv[regno].init_insns = gen_rtx_INSN_LIST (VOIDmode, NULL_RTX, NULL);
3251 reg_equiv[regno].replacement = NULL_RTX;
3252 /* This doesn't matter for equivalences made for argument registers, we
3253 should keep their initialization insns. */
3254 if (reg_equiv[regno].is_arg_equivalence)
3255 return;
3256 ira_reg_equiv[regno].defined_p = false;
3257 ira_reg_equiv[regno].init_insns = NULL;
3258 for (; list; list = list->next ())
3260 rtx_insn *insn = list->insn ();
3261 remove_note (insn, find_reg_note (insn, REG_EQUIV, NULL_RTX));
3265 /* Check whether the SUBREG is a paradoxical subreg and set the result
3266 in PDX_SUBREGS. */
3268 static void
3269 set_paradoxical_subreg (rtx_insn *insn)
3271 subrtx_iterator::array_type array;
3272 FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
3274 const_rtx subreg = *iter;
3275 if (GET_CODE (subreg) == SUBREG)
3277 const_rtx reg = SUBREG_REG (subreg);
3278 if (REG_P (reg) && paradoxical_subreg_p (subreg))
3279 reg_equiv[REGNO (reg)].pdx_subregs = true;
3284 /* In DEBUG_INSN location adjust REGs from CLEARED_REGS bitmap to the
3285 equivalent replacement. */
3287 static rtx
3288 adjust_cleared_regs (rtx loc, const_rtx old_rtx ATTRIBUTE_UNUSED, void *data)
3290 if (REG_P (loc))
3292 bitmap cleared_regs = (bitmap) data;
3293 if (bitmap_bit_p (cleared_regs, REGNO (loc)))
3294 return simplify_replace_fn_rtx (copy_rtx (*reg_equiv[REGNO (loc)].src_p),
3295 NULL_RTX, adjust_cleared_regs, data);
3297 return NULL_RTX;
3300 /* Given register REGNO is set only once, return true if the defining
3301 insn dominates all uses. */
3303 static bool
3304 def_dominates_uses (int regno)
3306 df_ref def = DF_REG_DEF_CHAIN (regno);
3308 struct df_insn_info *def_info = DF_REF_INSN_INFO (def);
3309 /* If this is an artificial def (eh handler regs, hard frame pointer
3310 for non-local goto, regs defined on function entry) then def_info
3311 is NULL and the reg is always live before any use. We might
3312 reasonably return true in that case, but since the only call
3313 of this function is currently here in ira.c when we are looking
3314 at a defining insn we can't have an artificial def as that would
3315 bump DF_REG_DEF_COUNT. */
3316 gcc_assert (DF_REG_DEF_COUNT (regno) == 1 && def_info != NULL);
3318 rtx_insn *def_insn = DF_REF_INSN (def);
3319 basic_block def_bb = BLOCK_FOR_INSN (def_insn);
3321 for (df_ref use = DF_REG_USE_CHAIN (regno);
3322 use;
3323 use = DF_REF_NEXT_REG (use))
3325 struct df_insn_info *use_info = DF_REF_INSN_INFO (use);
3326 /* Only check real uses, not artificial ones. */
3327 if (use_info)
3329 rtx_insn *use_insn = DF_REF_INSN (use);
3330 if (!DEBUG_INSN_P (use_insn))
3332 basic_block use_bb = BLOCK_FOR_INSN (use_insn);
3333 if (use_bb != def_bb
3334 ? !dominated_by_p (CDI_DOMINATORS, use_bb, def_bb)
3335 : DF_INSN_INFO_LUID (use_info) < DF_INSN_INFO_LUID (def_info))
3336 return false;
3340 return true;
3343 /* Find registers that are equivalent to a single value throughout the
3344 compilation (either because they can be referenced in memory or are
3345 set once from a single constant). Lower their priority for a
3346 register.
3348 If such a register is only referenced once, try substituting its
3349 value into the using insn. If it succeeds, we can eliminate the
3350 register completely.
3352 Initialize init_insns in ira_reg_equiv array. */
3353 static void
3354 update_equiv_regs (void)
3356 rtx_insn *insn;
3357 basic_block bb;
3359 /* Scan insns and set pdx_subregs if the reg is used in a
3360 paradoxical subreg. Don't set such reg equivalent to a mem,
3361 because lra will not substitute such equiv memory in order to
3362 prevent access beyond allocated memory for paradoxical memory subreg. */
3363 FOR_EACH_BB_FN (bb, cfun)
3364 FOR_BB_INSNS (bb, insn)
3365 if (NONDEBUG_INSN_P (insn))
3366 set_paradoxical_subreg (insn);
3368 /* Scan the insns and find which registers have equivalences. Do this
3369 in a separate scan of the insns because (due to -fcse-follow-jumps)
3370 a register can be set below its use. */
3371 bitmap setjmp_crosses = regstat_get_setjmp_crosses ();
3372 FOR_EACH_BB_FN (bb, cfun)
3374 int loop_depth = bb_loop_depth (bb);
3376 for (insn = BB_HEAD (bb);
3377 insn != NEXT_INSN (BB_END (bb));
3378 insn = NEXT_INSN (insn))
3380 rtx note;
3381 rtx set;
3382 rtx dest, src;
3383 int regno;
3385 if (! INSN_P (insn))
3386 continue;
3388 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
3389 if (REG_NOTE_KIND (note) == REG_INC)
3390 no_equiv (XEXP (note, 0), note, NULL);
3392 set = single_set (insn);
3394 /* If this insn contains more (or less) than a single SET,
3395 only mark all destinations as having no known equivalence. */
3396 if (set == NULL_RTX
3397 || side_effects_p (SET_SRC (set)))
3399 note_stores (PATTERN (insn), no_equiv, NULL);
3400 continue;
3402 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3404 int i;
3406 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
3408 rtx part = XVECEXP (PATTERN (insn), 0, i);
3409 if (part != set)
3410 note_stores (part, no_equiv, NULL);
3414 dest = SET_DEST (set);
3415 src = SET_SRC (set);
3417 /* See if this is setting up the equivalence between an argument
3418 register and its stack slot. */
3419 note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
3420 if (note)
3422 gcc_assert (REG_P (dest));
3423 regno = REGNO (dest);
3425 /* Note that we don't want to clear init_insns in
3426 ira_reg_equiv even if there are multiple sets of this
3427 register. */
3428 reg_equiv[regno].is_arg_equivalence = 1;
3430 /* The insn result can have equivalence memory although
3431 the equivalence is not set up by the insn. We add
3432 this insn to init insns as it is a flag for now that
3433 regno has an equivalence. We will remove the insn
3434 from init insn list later. */
3435 if (rtx_equal_p (src, XEXP (note, 0)) || MEM_P (XEXP (note, 0)))
3436 ira_reg_equiv[regno].init_insns
3437 = gen_rtx_INSN_LIST (VOIDmode, insn,
3438 ira_reg_equiv[regno].init_insns);
3440 /* Continue normally in case this is a candidate for
3441 replacements. */
3444 if (!optimize)
3445 continue;
3447 /* We only handle the case of a pseudo register being set
3448 once, or always to the same value. */
3449 /* ??? The mn10200 port breaks if we add equivalences for
3450 values that need an ADDRESS_REGS register and set them equivalent
3451 to a MEM of a pseudo. The actual problem is in the over-conservative
3452 handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
3453 calculate_needs, but we traditionally work around this problem
3454 here by rejecting equivalences when the destination is in a register
3455 that's likely spilled. This is fragile, of course, since the
3456 preferred class of a pseudo depends on all instructions that set
3457 or use it. */
3459 if (!REG_P (dest)
3460 || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER
3461 || (reg_equiv[regno].init_insns
3462 && reg_equiv[regno].init_insns->insn () == NULL)
3463 || (targetm.class_likely_spilled_p (reg_preferred_class (regno))
3464 && MEM_P (src) && ! reg_equiv[regno].is_arg_equivalence))
3466 /* This might be setting a SUBREG of a pseudo, a pseudo that is
3467 also set somewhere else to a constant. */
3468 note_stores (set, no_equiv, NULL);
3469 continue;
3472 /* Don't set reg mentioned in a paradoxical subreg
3473 equivalent to a mem. */
3474 if (MEM_P (src) && reg_equiv[regno].pdx_subregs)
3476 note_stores (set, no_equiv, NULL);
3477 continue;
3480 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
3482 /* cse sometimes generates function invariants, but doesn't put a
3483 REG_EQUAL note on the insn. Since this note would be redundant,
3484 there's no point creating it earlier than here. */
3485 if (! note && ! rtx_varies_p (src, 0))
3486 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
3488 /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
3489 since it represents a function call. */
3490 if (note && GET_CODE (XEXP (note, 0)) == EXPR_LIST)
3491 note = NULL_RTX;
3493 if (DF_REG_DEF_COUNT (regno) != 1)
3495 bool equal_p = true;
3496 rtx_insn_list *list;
3498 /* If we have already processed this pseudo and determined it
3499 can not have an equivalence, then honor that decision. */
3500 if (reg_equiv[regno].no_equiv)
3501 continue;
3503 if (! note
3504 || rtx_varies_p (XEXP (note, 0), 0)
3505 || (reg_equiv[regno].replacement
3506 && ! rtx_equal_p (XEXP (note, 0),
3507 reg_equiv[regno].replacement)))
3509 no_equiv (dest, set, NULL);
3510 continue;
3513 list = reg_equiv[regno].init_insns;
3514 for (; list; list = list->next ())
3516 rtx note_tmp;
3517 rtx_insn *insn_tmp;
3519 insn_tmp = list->insn ();
3520 note_tmp = find_reg_note (insn_tmp, REG_EQUAL, NULL_RTX);
3521 gcc_assert (note_tmp);
3522 if (! rtx_equal_p (XEXP (note, 0), XEXP (note_tmp, 0)))
3524 equal_p = false;
3525 break;
3529 if (! equal_p)
3531 no_equiv (dest, set, NULL);
3532 continue;
3536 /* Record this insn as initializing this register. */
3537 reg_equiv[regno].init_insns
3538 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv[regno].init_insns);
3540 /* If this register is known to be equal to a constant, record that
3541 it is always equivalent to the constant.
3542 Note that it is possible to have a register use before
3543 the def in loops (see gcc.c-torture/execute/pr79286.c)
3544 where the reg is undefined on first use. If the def insn
3545 won't trap we can use it as an equivalence, effectively
3546 choosing the "undefined" value for the reg to be the
3547 same as the value set by the def. */
3548 if (DF_REG_DEF_COUNT (regno) == 1
3549 && note
3550 && !rtx_varies_p (XEXP (note, 0), 0)
3551 && (!may_trap_or_fault_p (XEXP (note, 0))
3552 || def_dominates_uses (regno)))
3554 rtx note_value = XEXP (note, 0);
3555 remove_note (insn, note);
3556 set_unique_reg_note (insn, REG_EQUIV, note_value);
3559 /* If this insn introduces a "constant" register, decrease the priority
3560 of that register. Record this insn if the register is only used once
3561 more and the equivalence value is the same as our source.
3563 The latter condition is checked for two reasons: First, it is an
3564 indication that it may be more efficient to actually emit the insn
3565 as written (if no registers are available, reload will substitute
3566 the equivalence). Secondly, it avoids problems with any registers
3567 dying in this insn whose death notes would be missed.
3569 If we don't have a REG_EQUIV note, see if this insn is loading
3570 a register used only in one basic block from a MEM. If so, and the
3571 MEM remains unchanged for the life of the register, add a REG_EQUIV
3572 note. */
3573 note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
3575 rtx replacement = NULL_RTX;
3576 if (note)
3577 replacement = XEXP (note, 0);
3578 else if (REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
3579 && MEM_P (SET_SRC (set)))
3581 enum valid_equiv validity;
3582 validity = validate_equiv_mem (insn, dest, SET_SRC (set));
3583 if (validity != valid_none)
3585 replacement = copy_rtx (SET_SRC (set));
3586 if (validity == valid_reload)
3587 note = set_unique_reg_note (insn, REG_EQUIV, replacement);
3591 /* If we haven't done so, record for reload that this is an
3592 equivalencing insn. */
3593 if (note && !reg_equiv[regno].is_arg_equivalence)
3594 ira_reg_equiv[regno].init_insns
3595 = gen_rtx_INSN_LIST (VOIDmode, insn,
3596 ira_reg_equiv[regno].init_insns);
3598 if (replacement)
3600 reg_equiv[regno].replacement = replacement;
3601 reg_equiv[regno].src_p = &SET_SRC (set);
3602 reg_equiv[regno].loop_depth = (short) loop_depth;
3604 /* Don't mess with things live during setjmp. */
3605 if (optimize && !bitmap_bit_p (setjmp_crosses, regno))
3607 /* If the register is referenced exactly twice, meaning it is
3608 set once and used once, indicate that the reference may be
3609 replaced by the equivalence we computed above. Do this
3610 even if the register is only used in one block so that
3611 dependencies can be handled where the last register is
3612 used in a different block (i.e. HIGH / LO_SUM sequences)
3613 and to reduce the number of registers alive across
3614 calls. */
3616 if (REG_N_REFS (regno) == 2
3617 && (rtx_equal_p (replacement, src)
3618 || ! equiv_init_varies_p (src))
3619 && NONJUMP_INSN_P (insn)
3620 && equiv_init_movable_p (PATTERN (insn), regno))
3621 reg_equiv[regno].replace = 1;
3628 /* For insns that set a MEM to the contents of a REG that is only used
3629 in a single basic block, see if the register is always equivalent
3630 to that memory location and if moving the store from INSN to the
3631 insn that sets REG is safe. If so, put a REG_EQUIV note on the
3632 initializing insn. */
3633 static void
3634 add_store_equivs (void)
3636 auto_bitmap seen_insns;
3638 for (rtx_insn *insn = get_insns (); insn; insn = NEXT_INSN (insn))
3640 rtx set, src, dest;
3641 unsigned regno;
3642 rtx_insn *init_insn;
3644 bitmap_set_bit (seen_insns, INSN_UID (insn));
3646 if (! INSN_P (insn))
3647 continue;
3649 set = single_set (insn);
3650 if (! set)
3651 continue;
3653 dest = SET_DEST (set);
3654 src = SET_SRC (set);
3656 /* Don't add a REG_EQUIV note if the insn already has one. The existing
3657 REG_EQUIV is likely more useful than the one we are adding. */
3658 if (MEM_P (dest) && REG_P (src)
3659 && (regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
3660 && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
3661 && DF_REG_DEF_COUNT (regno) == 1
3662 && ! reg_equiv[regno].pdx_subregs
3663 && reg_equiv[regno].init_insns != NULL
3664 && (init_insn = reg_equiv[regno].init_insns->insn ()) != 0
3665 && bitmap_bit_p (seen_insns, INSN_UID (init_insn))
3666 && ! find_reg_note (init_insn, REG_EQUIV, NULL_RTX)
3667 && validate_equiv_mem (init_insn, src, dest) == valid_reload
3668 && ! memref_used_between_p (dest, init_insn, insn)
3669 /* Attaching a REG_EQUIV note will fail if INIT_INSN has
3670 multiple sets. */
3671 && set_unique_reg_note (init_insn, REG_EQUIV, copy_rtx (dest)))
3673 /* This insn makes the equivalence, not the one initializing
3674 the register. */
3675 ira_reg_equiv[regno].init_insns
3676 = gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
3677 df_notes_rescan (init_insn);
3678 if (dump_file)
3679 fprintf (dump_file,
3680 "Adding REG_EQUIV to insn %d for source of insn %d\n",
3681 INSN_UID (init_insn),
3682 INSN_UID (insn));
3687 /* Scan all regs killed in an insn to see if any of them are registers
3688 only used that once. If so, see if we can replace the reference
3689 with the equivalent form. If we can, delete the initializing
3690 reference and this register will go away. If we can't replace the
3691 reference, and the initializing reference is within the same loop
3692 (or in an inner loop), then move the register initialization just
3693 before the use, so that they are in the same basic block. */
3694 static void
3695 combine_and_move_insns (void)
3697 auto_bitmap cleared_regs;
3698 int max = max_reg_num ();
3700 for (int regno = FIRST_PSEUDO_REGISTER; regno < max; regno++)
3702 if (!reg_equiv[regno].replace)
3703 continue;
3705 rtx_insn *use_insn = 0;
3706 for (df_ref use = DF_REG_USE_CHAIN (regno);
3707 use;
3708 use = DF_REF_NEXT_REG (use))
3709 if (DF_REF_INSN_INFO (use))
3711 if (DEBUG_INSN_P (DF_REF_INSN (use)))
3712 continue;
3713 gcc_assert (!use_insn);
3714 use_insn = DF_REF_INSN (use);
3716 gcc_assert (use_insn);
3718 /* Don't substitute into jumps. indirect_jump_optimize does
3719 this for anything we are prepared to handle. */
3720 if (JUMP_P (use_insn))
3721 continue;
3723 /* Also don't substitute into a conditional trap insn -- it can become
3724 an unconditional trap, and that is a flow control insn. */
3725 if (GET_CODE (PATTERN (use_insn)) == TRAP_IF)
3726 continue;
3728 df_ref def = DF_REG_DEF_CHAIN (regno);
3729 gcc_assert (DF_REG_DEF_COUNT (regno) == 1 && DF_REF_INSN_INFO (def));
3730 rtx_insn *def_insn = DF_REF_INSN (def);
3732 /* We may not move instructions that can throw, since that
3733 changes basic block boundaries and we are not prepared to
3734 adjust the CFG to match. */
3735 if (can_throw_internal (def_insn))
3736 continue;
3738 basic_block use_bb = BLOCK_FOR_INSN (use_insn);
3739 basic_block def_bb = BLOCK_FOR_INSN (def_insn);
3740 if (bb_loop_depth (use_bb) > bb_loop_depth (def_bb))
3741 continue;
3743 if (asm_noperands (PATTERN (def_insn)) < 0
3744 && validate_replace_rtx (regno_reg_rtx[regno],
3745 *reg_equiv[regno].src_p, use_insn))
3747 rtx link;
3748 /* Append the REG_DEAD notes from def_insn. */
3749 for (rtx *p = &REG_NOTES (def_insn); (link = *p) != 0; )
3751 if (REG_NOTE_KIND (XEXP (link, 0)) == REG_DEAD)
3753 *p = XEXP (link, 1);
3754 XEXP (link, 1) = REG_NOTES (use_insn);
3755 REG_NOTES (use_insn) = link;
3757 else
3758 p = &XEXP (link, 1);
3761 remove_death (regno, use_insn);
3762 SET_REG_N_REFS (regno, 0);
3763 REG_FREQ (regno) = 0;
3764 df_ref use;
3765 FOR_EACH_INSN_USE (use, def_insn)
3767 unsigned int use_regno = DF_REF_REGNO (use);
3768 if (!HARD_REGISTER_NUM_P (use_regno))
3769 reg_equiv[use_regno].replace = 0;
3772 delete_insn (def_insn);
3774 reg_equiv[regno].init_insns = NULL;
3775 ira_reg_equiv[regno].init_insns = NULL;
3776 bitmap_set_bit (cleared_regs, regno);
3779 /* Move the initialization of the register to just before
3780 USE_INSN. Update the flow information. */
3781 else if (prev_nondebug_insn (use_insn) != def_insn)
3783 rtx_insn *new_insn;
3785 new_insn = emit_insn_before (PATTERN (def_insn), use_insn);
3786 REG_NOTES (new_insn) = REG_NOTES (def_insn);
3787 REG_NOTES (def_insn) = 0;
3788 /* Rescan it to process the notes. */
3789 df_insn_rescan (new_insn);
3791 /* Make sure this insn is recognized before reload begins,
3792 otherwise eliminate_regs_in_insn will die. */
3793 INSN_CODE (new_insn) = INSN_CODE (def_insn);
3795 delete_insn (def_insn);
3797 XEXP (reg_equiv[regno].init_insns, 0) = new_insn;
3799 REG_BASIC_BLOCK (regno) = use_bb->index;
3800 REG_N_CALLS_CROSSED (regno) = 0;
3802 if (use_insn == BB_HEAD (use_bb))
3803 BB_HEAD (use_bb) = new_insn;
3805 /* We know regno dies in use_insn, but inside a loop
3806 REG_DEAD notes might be missing when def_insn was in
3807 another basic block. However, when we move def_insn into
3808 this bb we'll definitely get a REG_DEAD note and reload
3809 will see the death. It's possible that update_equiv_regs
3810 set up an equivalence referencing regno for a reg set by
3811 use_insn, when regno was seen as non-local. Now that
3812 regno is local to this block, and dies, such an
3813 equivalence is invalid. */
3814 if (find_reg_note (use_insn, REG_EQUIV, regno_reg_rtx[regno]))
3816 rtx set = single_set (use_insn);
3817 if (set && REG_P (SET_DEST (set)))
3818 no_equiv (SET_DEST (set), set, NULL);
3821 ira_reg_equiv[regno].init_insns
3822 = gen_rtx_INSN_LIST (VOIDmode, new_insn, NULL_RTX);
3823 bitmap_set_bit (cleared_regs, regno);
3827 if (!bitmap_empty_p (cleared_regs))
3829 basic_block bb;
3831 FOR_EACH_BB_FN (bb, cfun)
3833 bitmap_and_compl_into (DF_LR_IN (bb), cleared_regs);
3834 bitmap_and_compl_into (DF_LR_OUT (bb), cleared_regs);
3835 if (!df_live)
3836 continue;
3837 bitmap_and_compl_into (DF_LIVE_IN (bb), cleared_regs);
3838 bitmap_and_compl_into (DF_LIVE_OUT (bb), cleared_regs);
3841 /* Last pass - adjust debug insns referencing cleared regs. */
3842 if (MAY_HAVE_DEBUG_BIND_INSNS)
3843 for (rtx_insn *insn = get_insns (); insn; insn = NEXT_INSN (insn))
3844 if (DEBUG_BIND_INSN_P (insn))
3846 rtx old_loc = INSN_VAR_LOCATION_LOC (insn);
3847 INSN_VAR_LOCATION_LOC (insn)
3848 = simplify_replace_fn_rtx (old_loc, NULL_RTX,
3849 adjust_cleared_regs,
3850 (void *) cleared_regs);
3851 if (old_loc != INSN_VAR_LOCATION_LOC (insn))
3852 df_insn_rescan (insn);
3857 /* A pass over indirect jumps, converting simple cases to direct jumps.
3858 Combine does this optimization too, but only within a basic block. */
3859 static void
3860 indirect_jump_optimize (void)
3862 basic_block bb;
3863 bool rebuild_p = false;
3865 FOR_EACH_BB_REVERSE_FN (bb, cfun)
3867 rtx_insn *insn = BB_END (bb);
3868 if (!JUMP_P (insn)
3869 || find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
3870 continue;
3872 rtx x = pc_set (insn);
3873 if (!x || !REG_P (SET_SRC (x)))
3874 continue;
3876 int regno = REGNO (SET_SRC (x));
3877 if (DF_REG_DEF_COUNT (regno) == 1)
3879 df_ref def = DF_REG_DEF_CHAIN (regno);
3880 if (!DF_REF_IS_ARTIFICIAL (def))
3882 rtx_insn *def_insn = DF_REF_INSN (def);
3883 rtx lab = NULL_RTX;
3884 rtx set = single_set (def_insn);
3885 if (set && GET_CODE (SET_SRC (set)) == LABEL_REF)
3886 lab = SET_SRC (set);
3887 else
3889 rtx eqnote = find_reg_note (def_insn, REG_EQUAL, NULL_RTX);
3890 if (eqnote && GET_CODE (XEXP (eqnote, 0)) == LABEL_REF)
3891 lab = XEXP (eqnote, 0);
3893 if (lab && validate_replace_rtx (SET_SRC (x), lab, insn))
3894 rebuild_p = true;
3899 if (rebuild_p)
3901 timevar_push (TV_JUMP);
3902 rebuild_jump_labels (get_insns ());
3903 if (purge_all_dead_edges ())
3904 delete_unreachable_blocks ();
3905 timevar_pop (TV_JUMP);
3909 /* Set up fields memory, constant, and invariant from init_insns in
3910 the structures of array ira_reg_equiv. */
3911 static void
3912 setup_reg_equiv (void)
3914 int i;
3915 rtx_insn_list *elem, *prev_elem, *next_elem;
3916 rtx_insn *insn;
3917 rtx set, x;
3919 for (i = FIRST_PSEUDO_REGISTER; i < ira_reg_equiv_len; i++)
3920 for (prev_elem = NULL, elem = ira_reg_equiv[i].init_insns;
3921 elem;
3922 prev_elem = elem, elem = next_elem)
3924 next_elem = elem->next ();
3925 insn = elem->insn ();
3926 set = single_set (insn);
3928 /* Init insns can set up equivalence when the reg is a destination or
3929 a source (in this case the destination is memory). */
3930 if (set != 0 && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))))
3932 if ((x = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != NULL)
3934 x = XEXP (x, 0);
3935 if (REG_P (SET_DEST (set))
3936 && REGNO (SET_DEST (set)) == (unsigned int) i
3937 && ! rtx_equal_p (SET_SRC (set), x) && MEM_P (x))
3939 /* This insn reporting the equivalence but
3940 actually not setting it. Remove it from the
3941 list. */
3942 if (prev_elem == NULL)
3943 ira_reg_equiv[i].init_insns = next_elem;
3944 else
3945 XEXP (prev_elem, 1) = next_elem;
3946 elem = prev_elem;
3949 else if (REG_P (SET_DEST (set))
3950 && REGNO (SET_DEST (set)) == (unsigned int) i)
3951 x = SET_SRC (set);
3952 else
3954 gcc_assert (REG_P (SET_SRC (set))
3955 && REGNO (SET_SRC (set)) == (unsigned int) i);
3956 x = SET_DEST (set);
3958 if (! function_invariant_p (x)
3959 || ! flag_pic
3960 /* A function invariant is often CONSTANT_P but may
3961 include a register. We promise to only pass
3962 CONSTANT_P objects to LEGITIMATE_PIC_OPERAND_P. */
3963 || (CONSTANT_P (x) && LEGITIMATE_PIC_OPERAND_P (x)))
3965 /* It can happen that a REG_EQUIV note contains a MEM
3966 that is not a legitimate memory operand. As later
3967 stages of reload assume that all addresses found in
3968 the lra_regno_equiv_* arrays were originally
3969 legitimate, we ignore such REG_EQUIV notes. */
3970 if (memory_operand (x, VOIDmode))
3972 ira_reg_equiv[i].defined_p = true;
3973 ira_reg_equiv[i].memory = x;
3974 continue;
3976 else if (function_invariant_p (x))
3978 machine_mode mode;
3980 mode = GET_MODE (SET_DEST (set));
3981 if (GET_CODE (x) == PLUS
3982 || x == frame_pointer_rtx || x == arg_pointer_rtx)
3983 /* This is PLUS of frame pointer and a constant,
3984 or fp, or argp. */
3985 ira_reg_equiv[i].invariant = x;
3986 else if (targetm.legitimate_constant_p (mode, x))
3987 ira_reg_equiv[i].constant = x;
3988 else
3990 ira_reg_equiv[i].memory = force_const_mem (mode, x);
3991 if (ira_reg_equiv[i].memory == NULL_RTX)
3993 ira_reg_equiv[i].defined_p = false;
3994 ira_reg_equiv[i].init_insns = NULL;
3995 break;
3998 ira_reg_equiv[i].defined_p = true;
3999 continue;
4003 ira_reg_equiv[i].defined_p = false;
4004 ira_reg_equiv[i].init_insns = NULL;
4005 break;
4011 /* Print chain C to FILE. */
4012 static void
4013 print_insn_chain (FILE *file, struct insn_chain *c)
4015 fprintf (file, "insn=%d, ", INSN_UID (c->insn));
4016 bitmap_print (file, &c->live_throughout, "live_throughout: ", ", ");
4017 bitmap_print (file, &c->dead_or_set, "dead_or_set: ", "\n");
4021 /* Print all reload_insn_chains to FILE. */
4022 static void
4023 print_insn_chains (FILE *file)
4025 struct insn_chain *c;
4026 for (c = reload_insn_chain; c ; c = c->next)
4027 print_insn_chain (file, c);
4030 /* Return true if pseudo REGNO should be added to set live_throughout
4031 or dead_or_set of the insn chains for reload consideration. */
4032 static bool
4033 pseudo_for_reload_consideration_p (int regno)
4035 /* Consider spilled pseudos too for IRA because they still have a
4036 chance to get hard-registers in the reload when IRA is used. */
4037 return (reg_renumber[regno] >= 0 || ira_conflicts_p);
4040 /* Return true if we can track the individual bytes of subreg X.
4041 When returning true, set *OUTER_SIZE to the number of bytes in
4042 X itself, *INNER_SIZE to the number of bytes in the inner register
4043 and *START to the offset of the first byte. */
4044 static bool
4045 get_subreg_tracking_sizes (rtx x, HOST_WIDE_INT *outer_size,
4046 HOST_WIDE_INT *inner_size, HOST_WIDE_INT *start)
4048 rtx reg = regno_reg_rtx[REGNO (SUBREG_REG (x))];
4049 return (GET_MODE_SIZE (GET_MODE (x)).is_constant (outer_size)
4050 && GET_MODE_SIZE (GET_MODE (reg)).is_constant (inner_size)
4051 && SUBREG_BYTE (x).is_constant (start));
4054 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] for
4055 a register with SIZE bytes, making the register live if INIT_VALUE. */
4056 static void
4057 init_live_subregs (bool init_value, sbitmap *live_subregs,
4058 bitmap live_subregs_used, int allocnum, int size)
4060 gcc_assert (size > 0);
4062 /* Been there, done that. */
4063 if (bitmap_bit_p (live_subregs_used, allocnum))
4064 return;
4066 /* Create a new one. */
4067 if (live_subregs[allocnum] == NULL)
4068 live_subregs[allocnum] = sbitmap_alloc (size);
4070 /* If the entire reg was live before blasting into subregs, we need
4071 to init all of the subregs to ones else init to 0. */
4072 if (init_value)
4073 bitmap_ones (live_subregs[allocnum]);
4074 else
4075 bitmap_clear (live_subregs[allocnum]);
4077 bitmap_set_bit (live_subregs_used, allocnum);
4080 /* Walk the insns of the current function and build reload_insn_chain,
4081 and record register life information. */
4082 static void
4083 build_insn_chain (void)
4085 unsigned int i;
4086 struct insn_chain **p = &reload_insn_chain;
4087 basic_block bb;
4088 struct insn_chain *c = NULL;
4089 struct insn_chain *next = NULL;
4090 auto_bitmap live_relevant_regs;
4091 auto_bitmap elim_regset;
4092 /* live_subregs is a vector used to keep accurate information about
4093 which hardregs are live in multiword pseudos. live_subregs and
4094 live_subregs_used are indexed by pseudo number. The live_subreg
4095 entry for a particular pseudo is only used if the corresponding
4096 element is non zero in live_subregs_used. The sbitmap size of
4097 live_subreg[allocno] is number of bytes that the pseudo can
4098 occupy. */
4099 sbitmap *live_subregs = XCNEWVEC (sbitmap, max_regno);
4100 auto_bitmap live_subregs_used;
4102 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4103 if (TEST_HARD_REG_BIT (eliminable_regset, i))
4104 bitmap_set_bit (elim_regset, i);
4105 FOR_EACH_BB_REVERSE_FN (bb, cfun)
4107 bitmap_iterator bi;
4108 rtx_insn *insn;
4110 CLEAR_REG_SET (live_relevant_regs);
4111 bitmap_clear (live_subregs_used);
4113 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb), 0, i, bi)
4115 if (i >= FIRST_PSEUDO_REGISTER)
4116 break;
4117 bitmap_set_bit (live_relevant_regs, i);
4120 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb),
4121 FIRST_PSEUDO_REGISTER, i, bi)
4123 if (pseudo_for_reload_consideration_p (i))
4124 bitmap_set_bit (live_relevant_regs, i);
4127 FOR_BB_INSNS_REVERSE (bb, insn)
4129 if (!NOTE_P (insn) && !BARRIER_P (insn))
4131 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4132 df_ref def, use;
4134 c = new_insn_chain ();
4135 c->next = next;
4136 next = c;
4137 *p = c;
4138 p = &c->prev;
4140 c->insn = insn;
4141 c->block = bb->index;
4143 if (NONDEBUG_INSN_P (insn))
4144 FOR_EACH_INSN_INFO_DEF (def, insn_info)
4146 unsigned int regno = DF_REF_REGNO (def);
4148 /* Ignore may clobbers because these are generated
4149 from calls. However, every other kind of def is
4150 added to dead_or_set. */
4151 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
4153 if (regno < FIRST_PSEUDO_REGISTER)
4155 if (!fixed_regs[regno])
4156 bitmap_set_bit (&c->dead_or_set, regno);
4158 else if (pseudo_for_reload_consideration_p (regno))
4159 bitmap_set_bit (&c->dead_or_set, regno);
4162 if ((regno < FIRST_PSEUDO_REGISTER
4163 || reg_renumber[regno] >= 0
4164 || ira_conflicts_p)
4165 && (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)))
4167 rtx reg = DF_REF_REG (def);
4168 HOST_WIDE_INT outer_size, inner_size, start;
4170 /* We can usually track the liveness of individual
4171 bytes within a subreg. The only exceptions are
4172 subregs wrapped in ZERO_EXTRACTs and subregs whose
4173 size is not known; in those cases we need to be
4174 conservative and treat the definition as a partial
4175 definition of the full register rather than a full
4176 definition of a specific part of the register. */
4177 if (GET_CODE (reg) == SUBREG
4178 && !DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT)
4179 && get_subreg_tracking_sizes (reg, &outer_size,
4180 &inner_size, &start))
4182 HOST_WIDE_INT last = start + outer_size;
4184 init_live_subregs
4185 (bitmap_bit_p (live_relevant_regs, regno),
4186 live_subregs, live_subregs_used, regno,
4187 inner_size);
4189 if (!DF_REF_FLAGS_IS_SET
4190 (def, DF_REF_STRICT_LOW_PART))
4192 /* Expand the range to cover entire words.
4193 Bytes added here are "don't care". */
4194 start
4195 = start / UNITS_PER_WORD * UNITS_PER_WORD;
4196 last = ((last + UNITS_PER_WORD - 1)
4197 / UNITS_PER_WORD * UNITS_PER_WORD);
4200 /* Ignore the paradoxical bits. */
4201 if (last > SBITMAP_SIZE (live_subregs[regno]))
4202 last = SBITMAP_SIZE (live_subregs[regno]);
4204 while (start < last)
4206 bitmap_clear_bit (live_subregs[regno], start);
4207 start++;
4210 if (bitmap_empty_p (live_subregs[regno]))
4212 bitmap_clear_bit (live_subregs_used, regno);
4213 bitmap_clear_bit (live_relevant_regs, regno);
4215 else
4216 /* Set live_relevant_regs here because
4217 that bit has to be true to get us to
4218 look at the live_subregs fields. */
4219 bitmap_set_bit (live_relevant_regs, regno);
4221 else
4223 /* DF_REF_PARTIAL is generated for
4224 subregs, STRICT_LOW_PART, and
4225 ZERO_EXTRACT. We handle the subreg
4226 case above so here we have to keep from
4227 modeling the def as a killing def. */
4228 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL))
4230 bitmap_clear_bit (live_subregs_used, regno);
4231 bitmap_clear_bit (live_relevant_regs, regno);
4237 bitmap_and_compl_into (live_relevant_regs, elim_regset);
4238 bitmap_copy (&c->live_throughout, live_relevant_regs);
4240 if (NONDEBUG_INSN_P (insn))
4241 FOR_EACH_INSN_INFO_USE (use, insn_info)
4243 unsigned int regno = DF_REF_REGNO (use);
4244 rtx reg = DF_REF_REG (use);
4246 /* DF_REF_READ_WRITE on a use means that this use
4247 is fabricated from a def that is a partial set
4248 to a multiword reg. Here, we only model the
4249 subreg case that is not wrapped in ZERO_EXTRACT
4250 precisely so we do not need to look at the
4251 fabricated use. */
4252 if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE)
4253 && !DF_REF_FLAGS_IS_SET (use, DF_REF_ZERO_EXTRACT)
4254 && DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG))
4255 continue;
4257 /* Add the last use of each var to dead_or_set. */
4258 if (!bitmap_bit_p (live_relevant_regs, regno))
4260 if (regno < FIRST_PSEUDO_REGISTER)
4262 if (!fixed_regs[regno])
4263 bitmap_set_bit (&c->dead_or_set, regno);
4265 else if (pseudo_for_reload_consideration_p (regno))
4266 bitmap_set_bit (&c->dead_or_set, regno);
4269 if (regno < FIRST_PSEUDO_REGISTER
4270 || pseudo_for_reload_consideration_p (regno))
4272 HOST_WIDE_INT outer_size, inner_size, start;
4273 if (GET_CODE (reg) == SUBREG
4274 && !DF_REF_FLAGS_IS_SET (use,
4275 DF_REF_SIGN_EXTRACT
4276 | DF_REF_ZERO_EXTRACT)
4277 && get_subreg_tracking_sizes (reg, &outer_size,
4278 &inner_size, &start))
4280 HOST_WIDE_INT last = start + outer_size;
4282 init_live_subregs
4283 (bitmap_bit_p (live_relevant_regs, regno),
4284 live_subregs, live_subregs_used, regno,
4285 inner_size);
4287 /* Ignore the paradoxical bits. */
4288 if (last > SBITMAP_SIZE (live_subregs[regno]))
4289 last = SBITMAP_SIZE (live_subregs[regno]);
4291 while (start < last)
4293 bitmap_set_bit (live_subregs[regno], start);
4294 start++;
4297 else
4298 /* Resetting the live_subregs_used is
4299 effectively saying do not use the subregs
4300 because we are reading the whole
4301 pseudo. */
4302 bitmap_clear_bit (live_subregs_used, regno);
4303 bitmap_set_bit (live_relevant_regs, regno);
4309 /* FIXME!! The following code is a disaster. Reload needs to see the
4310 labels and jump tables that are just hanging out in between
4311 the basic blocks. See pr33676. */
4312 insn = BB_HEAD (bb);
4314 /* Skip over the barriers and cruft. */
4315 while (insn && (BARRIER_P (insn) || NOTE_P (insn)
4316 || BLOCK_FOR_INSN (insn) == bb))
4317 insn = PREV_INSN (insn);
4319 /* While we add anything except barriers and notes, the focus is
4320 to get the labels and jump tables into the
4321 reload_insn_chain. */
4322 while (insn)
4324 if (!NOTE_P (insn) && !BARRIER_P (insn))
4326 if (BLOCK_FOR_INSN (insn))
4327 break;
4329 c = new_insn_chain ();
4330 c->next = next;
4331 next = c;
4332 *p = c;
4333 p = &c->prev;
4335 /* The block makes no sense here, but it is what the old
4336 code did. */
4337 c->block = bb->index;
4338 c->insn = insn;
4339 bitmap_copy (&c->live_throughout, live_relevant_regs);
4341 insn = PREV_INSN (insn);
4345 reload_insn_chain = c;
4346 *p = NULL;
4348 for (i = 0; i < (unsigned int) max_regno; i++)
4349 if (live_subregs[i] != NULL)
4350 sbitmap_free (live_subregs[i]);
4351 free (live_subregs);
4353 if (dump_file)
4354 print_insn_chains (dump_file);
4357 /* Examine the rtx found in *LOC, which is read or written to as determined
4358 by TYPE. Return false if we find a reason why an insn containing this
4359 rtx should not be moved (such as accesses to non-constant memory), true
4360 otherwise. */
4361 static bool
4362 rtx_moveable_p (rtx *loc, enum op_type type)
4364 const char *fmt;
4365 rtx x = *loc;
4366 enum rtx_code code = GET_CODE (x);
4367 int i, j;
4369 code = GET_CODE (x);
4370 switch (code)
4372 case CONST:
4373 CASE_CONST_ANY:
4374 case SYMBOL_REF:
4375 case LABEL_REF:
4376 return true;
4378 case PC:
4379 return type == OP_IN;
4381 case CC0:
4382 return false;
4384 case REG:
4385 if (x == frame_pointer_rtx)
4386 return true;
4387 if (HARD_REGISTER_P (x))
4388 return false;
4390 return true;
4392 case MEM:
4393 if (type == OP_IN && MEM_READONLY_P (x))
4394 return rtx_moveable_p (&XEXP (x, 0), OP_IN);
4395 return false;
4397 case SET:
4398 return (rtx_moveable_p (&SET_SRC (x), OP_IN)
4399 && rtx_moveable_p (&SET_DEST (x), OP_OUT));
4401 case STRICT_LOW_PART:
4402 return rtx_moveable_p (&XEXP (x, 0), OP_OUT);
4404 case ZERO_EXTRACT:
4405 case SIGN_EXTRACT:
4406 return (rtx_moveable_p (&XEXP (x, 0), type)
4407 && rtx_moveable_p (&XEXP (x, 1), OP_IN)
4408 && rtx_moveable_p (&XEXP (x, 2), OP_IN));
4410 case CLOBBER:
4411 return rtx_moveable_p (&SET_DEST (x), OP_OUT);
4413 case UNSPEC_VOLATILE:
4414 /* It is a bad idea to consider insns with such rtl
4415 as moveable ones. The insn scheduler also considers them as barrier
4416 for a reason. */
4417 return false;
4419 case ASM_OPERANDS:
4420 /* The same is true for volatile asm: it has unknown side effects, it
4421 cannot be moved at will. */
4422 if (MEM_VOLATILE_P (x))
4423 return false;
4425 default:
4426 break;
4429 fmt = GET_RTX_FORMAT (code);
4430 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4432 if (fmt[i] == 'e')
4434 if (!rtx_moveable_p (&XEXP (x, i), type))
4435 return false;
4437 else if (fmt[i] == 'E')
4438 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4440 if (!rtx_moveable_p (&XVECEXP (x, i, j), type))
4441 return false;
4444 return true;
4447 /* A wrapper around dominated_by_p, which uses the information in UID_LUID
4448 to give dominance relationships between two insns I1 and I2. */
4449 static bool
4450 insn_dominated_by_p (rtx i1, rtx i2, int *uid_luid)
4452 basic_block bb1 = BLOCK_FOR_INSN (i1);
4453 basic_block bb2 = BLOCK_FOR_INSN (i2);
4455 if (bb1 == bb2)
4456 return uid_luid[INSN_UID (i2)] < uid_luid[INSN_UID (i1)];
4457 return dominated_by_p (CDI_DOMINATORS, bb1, bb2);
4460 /* Record the range of register numbers added by find_moveable_pseudos. */
4461 int first_moveable_pseudo, last_moveable_pseudo;
4463 /* These two vectors hold data for every register added by
4464 find_movable_pseudos, with index 0 holding data for the
4465 first_moveable_pseudo. */
4466 /* The original home register. */
4467 static vec<rtx> pseudo_replaced_reg;
4469 /* Look for instances where we have an instruction that is known to increase
4470 register pressure, and whose result is not used immediately. If it is
4471 possible to move the instruction downwards to just before its first use,
4472 split its lifetime into two ranges. We create a new pseudo to compute the
4473 value, and emit a move instruction just before the first use. If, after
4474 register allocation, the new pseudo remains unallocated, the function
4475 move_unallocated_pseudos then deletes the move instruction and places
4476 the computation just before the first use.
4478 Such a move is safe and profitable if all the input registers remain live
4479 and unchanged between the original computation and its first use. In such
4480 a situation, the computation is known to increase register pressure, and
4481 moving it is known to at least not worsen it.
4483 We restrict moves to only those cases where a register remains unallocated,
4484 in order to avoid interfering too much with the instruction schedule. As
4485 an exception, we may move insns which only modify their input register
4486 (typically induction variables), as this increases the freedom for our
4487 intended transformation, and does not limit the second instruction
4488 scheduler pass. */
4490 static void
4491 find_moveable_pseudos (void)
4493 unsigned i;
4494 int max_regs = max_reg_num ();
4495 int max_uid = get_max_uid ();
4496 basic_block bb;
4497 int *uid_luid = XNEWVEC (int, max_uid);
4498 rtx_insn **closest_uses = XNEWVEC (rtx_insn *, max_regs);
4499 /* A set of registers which are live but not modified throughout a block. */
4500 bitmap_head *bb_transp_live = XNEWVEC (bitmap_head,
4501 last_basic_block_for_fn (cfun));
4502 /* A set of registers which only exist in a given basic block. */
4503 bitmap_head *bb_local = XNEWVEC (bitmap_head,
4504 last_basic_block_for_fn (cfun));
4505 /* A set of registers which are set once, in an instruction that can be
4506 moved freely downwards, but are otherwise transparent to a block. */
4507 bitmap_head *bb_moveable_reg_sets = XNEWVEC (bitmap_head,
4508 last_basic_block_for_fn (cfun));
4509 auto_bitmap live, used, set, interesting, unusable_as_input;
4510 bitmap_iterator bi;
4512 first_moveable_pseudo = max_regs;
4513 pseudo_replaced_reg.release ();
4514 pseudo_replaced_reg.safe_grow_cleared (max_regs);
4516 df_analyze ();
4517 calculate_dominance_info (CDI_DOMINATORS);
4519 i = 0;
4520 FOR_EACH_BB_FN (bb, cfun)
4522 rtx_insn *insn;
4523 bitmap transp = bb_transp_live + bb->index;
4524 bitmap moveable = bb_moveable_reg_sets + bb->index;
4525 bitmap local = bb_local + bb->index;
4527 bitmap_initialize (local, 0);
4528 bitmap_initialize (transp, 0);
4529 bitmap_initialize (moveable, 0);
4530 bitmap_copy (live, df_get_live_out (bb));
4531 bitmap_and_into (live, df_get_live_in (bb));
4532 bitmap_copy (transp, live);
4533 bitmap_clear (moveable);
4534 bitmap_clear (live);
4535 bitmap_clear (used);
4536 bitmap_clear (set);
4537 FOR_BB_INSNS (bb, insn)
4538 if (NONDEBUG_INSN_P (insn))
4540 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4541 df_ref def, use;
4543 uid_luid[INSN_UID (insn)] = i++;
4545 def = df_single_def (insn_info);
4546 use = df_single_use (insn_info);
4547 if (use
4548 && def
4549 && DF_REF_REGNO (use) == DF_REF_REGNO (def)
4550 && !bitmap_bit_p (set, DF_REF_REGNO (use))
4551 && rtx_moveable_p (&PATTERN (insn), OP_IN))
4553 unsigned regno = DF_REF_REGNO (use);
4554 bitmap_set_bit (moveable, regno);
4555 bitmap_set_bit (set, regno);
4556 bitmap_set_bit (used, regno);
4557 bitmap_clear_bit (transp, regno);
4558 continue;
4560 FOR_EACH_INSN_INFO_USE (use, insn_info)
4562 unsigned regno = DF_REF_REGNO (use);
4563 bitmap_set_bit (used, regno);
4564 if (bitmap_clear_bit (moveable, regno))
4565 bitmap_clear_bit (transp, regno);
4568 FOR_EACH_INSN_INFO_DEF (def, insn_info)
4570 unsigned regno = DF_REF_REGNO (def);
4571 bitmap_set_bit (set, regno);
4572 bitmap_clear_bit (transp, regno);
4573 bitmap_clear_bit (moveable, regno);
4578 FOR_EACH_BB_FN (bb, cfun)
4580 bitmap local = bb_local + bb->index;
4581 rtx_insn *insn;
4583 FOR_BB_INSNS (bb, insn)
4584 if (NONDEBUG_INSN_P (insn))
4586 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4587 rtx_insn *def_insn;
4588 rtx closest_use, note;
4589 df_ref def, use;
4590 unsigned regno;
4591 bool all_dominated, all_local;
4592 machine_mode mode;
4594 def = df_single_def (insn_info);
4595 /* There must be exactly one def in this insn. */
4596 if (!def || !single_set (insn))
4597 continue;
4598 /* This must be the only definition of the reg. We also limit
4599 which modes we deal with so that we can assume we can generate
4600 move instructions. */
4601 regno = DF_REF_REGNO (def);
4602 mode = GET_MODE (DF_REF_REG (def));
4603 if (DF_REG_DEF_COUNT (regno) != 1
4604 || !DF_REF_INSN_INFO (def)
4605 || HARD_REGISTER_NUM_P (regno)
4606 || DF_REG_EQ_USE_COUNT (regno) > 0
4607 || (!INTEGRAL_MODE_P (mode) && !FLOAT_MODE_P (mode)))
4608 continue;
4609 def_insn = DF_REF_INSN (def);
4611 for (note = REG_NOTES (def_insn); note; note = XEXP (note, 1))
4612 if (REG_NOTE_KIND (note) == REG_EQUIV && MEM_P (XEXP (note, 0)))
4613 break;
4615 if (note)
4617 if (dump_file)
4618 fprintf (dump_file, "Ignoring reg %d, has equiv memory\n",
4619 regno);
4620 bitmap_set_bit (unusable_as_input, regno);
4621 continue;
4624 use = DF_REG_USE_CHAIN (regno);
4625 all_dominated = true;
4626 all_local = true;
4627 closest_use = NULL_RTX;
4628 for (; use; use = DF_REF_NEXT_REG (use))
4630 rtx_insn *insn;
4631 if (!DF_REF_INSN_INFO (use))
4633 all_dominated = false;
4634 all_local = false;
4635 break;
4637 insn = DF_REF_INSN (use);
4638 if (DEBUG_INSN_P (insn))
4639 continue;
4640 if (BLOCK_FOR_INSN (insn) != BLOCK_FOR_INSN (def_insn))
4641 all_local = false;
4642 if (!insn_dominated_by_p (insn, def_insn, uid_luid))
4643 all_dominated = false;
4644 if (closest_use != insn && closest_use != const0_rtx)
4646 if (closest_use == NULL_RTX)
4647 closest_use = insn;
4648 else if (insn_dominated_by_p (closest_use, insn, uid_luid))
4649 closest_use = insn;
4650 else if (!insn_dominated_by_p (insn, closest_use, uid_luid))
4651 closest_use = const0_rtx;
4654 if (!all_dominated)
4656 if (dump_file)
4657 fprintf (dump_file, "Reg %d not all uses dominated by set\n",
4658 regno);
4659 continue;
4661 if (all_local)
4662 bitmap_set_bit (local, regno);
4663 if (closest_use == const0_rtx || closest_use == NULL
4664 || next_nonnote_nondebug_insn (def_insn) == closest_use)
4666 if (dump_file)
4667 fprintf (dump_file, "Reg %d uninteresting%s\n", regno,
4668 closest_use == const0_rtx || closest_use == NULL
4669 ? " (no unique first use)" : "");
4670 continue;
4672 if (HAVE_cc0 && reg_referenced_p (cc0_rtx, PATTERN (closest_use)))
4674 if (dump_file)
4675 fprintf (dump_file, "Reg %d: closest user uses cc0\n",
4676 regno);
4677 continue;
4680 bitmap_set_bit (interesting, regno);
4681 /* If we get here, we know closest_use is a non-NULL insn
4682 (as opposed to const_0_rtx). */
4683 closest_uses[regno] = as_a <rtx_insn *> (closest_use);
4685 if (dump_file && (all_local || all_dominated))
4687 fprintf (dump_file, "Reg %u:", regno);
4688 if (all_local)
4689 fprintf (dump_file, " local to bb %d", bb->index);
4690 if (all_dominated)
4691 fprintf (dump_file, " def dominates all uses");
4692 if (closest_use != const0_rtx)
4693 fprintf (dump_file, " has unique first use");
4694 fputs ("\n", dump_file);
4699 EXECUTE_IF_SET_IN_BITMAP (interesting, 0, i, bi)
4701 df_ref def = DF_REG_DEF_CHAIN (i);
4702 rtx_insn *def_insn = DF_REF_INSN (def);
4703 basic_block def_block = BLOCK_FOR_INSN (def_insn);
4704 bitmap def_bb_local = bb_local + def_block->index;
4705 bitmap def_bb_moveable = bb_moveable_reg_sets + def_block->index;
4706 bitmap def_bb_transp = bb_transp_live + def_block->index;
4707 bool local_to_bb_p = bitmap_bit_p (def_bb_local, i);
4708 rtx_insn *use_insn = closest_uses[i];
4709 df_ref use;
4710 bool all_ok = true;
4711 bool all_transp = true;
4713 if (!REG_P (DF_REF_REG (def)))
4714 continue;
4716 if (!local_to_bb_p)
4718 if (dump_file)
4719 fprintf (dump_file, "Reg %u not local to one basic block\n",
4721 continue;
4723 if (reg_equiv_init (i) != NULL_RTX)
4725 if (dump_file)
4726 fprintf (dump_file, "Ignoring reg %u with equiv init insn\n",
4728 continue;
4730 if (!rtx_moveable_p (&PATTERN (def_insn), OP_IN))
4732 if (dump_file)
4733 fprintf (dump_file, "Found def insn %d for %d to be not moveable\n",
4734 INSN_UID (def_insn), i);
4735 continue;
4737 if (dump_file)
4738 fprintf (dump_file, "Examining insn %d, def for %d\n",
4739 INSN_UID (def_insn), i);
4740 FOR_EACH_INSN_USE (use, def_insn)
4742 unsigned regno = DF_REF_REGNO (use);
4743 if (bitmap_bit_p (unusable_as_input, regno))
4745 all_ok = false;
4746 if (dump_file)
4747 fprintf (dump_file, " found unusable input reg %u.\n", regno);
4748 break;
4750 if (!bitmap_bit_p (def_bb_transp, regno))
4752 if (bitmap_bit_p (def_bb_moveable, regno)
4753 && !control_flow_insn_p (use_insn)
4754 && (!HAVE_cc0 || !sets_cc0_p (use_insn)))
4756 if (modified_between_p (DF_REF_REG (use), def_insn, use_insn))
4758 rtx_insn *x = NEXT_INSN (def_insn);
4759 while (!modified_in_p (DF_REF_REG (use), x))
4761 gcc_assert (x != use_insn);
4762 x = NEXT_INSN (x);
4764 if (dump_file)
4765 fprintf (dump_file, " input reg %u modified but insn %d moveable\n",
4766 regno, INSN_UID (x));
4767 emit_insn_after (PATTERN (x), use_insn);
4768 set_insn_deleted (x);
4770 else
4772 if (dump_file)
4773 fprintf (dump_file, " input reg %u modified between def and use\n",
4774 regno);
4775 all_transp = false;
4778 else
4779 all_transp = false;
4782 if (!all_ok)
4783 continue;
4784 if (!dbg_cnt (ira_move))
4785 break;
4786 if (dump_file)
4787 fprintf (dump_file, " all ok%s\n", all_transp ? " and transp" : "");
4789 if (all_transp)
4791 rtx def_reg = DF_REF_REG (def);
4792 rtx newreg = ira_create_new_reg (def_reg);
4793 if (validate_change (def_insn, DF_REF_REAL_LOC (def), newreg, 0))
4795 unsigned nregno = REGNO (newreg);
4796 emit_insn_before (gen_move_insn (def_reg, newreg), use_insn);
4797 nregno -= max_regs;
4798 pseudo_replaced_reg[nregno] = def_reg;
4803 FOR_EACH_BB_FN (bb, cfun)
4805 bitmap_clear (bb_local + bb->index);
4806 bitmap_clear (bb_transp_live + bb->index);
4807 bitmap_clear (bb_moveable_reg_sets + bb->index);
4809 free (uid_luid);
4810 free (closest_uses);
4811 free (bb_local);
4812 free (bb_transp_live);
4813 free (bb_moveable_reg_sets);
4815 last_moveable_pseudo = max_reg_num ();
4817 fix_reg_equiv_init ();
4818 expand_reg_info ();
4819 regstat_free_n_sets_and_refs ();
4820 regstat_free_ri ();
4821 regstat_init_n_sets_and_refs ();
4822 regstat_compute_ri ();
4823 free_dominance_info (CDI_DOMINATORS);
4826 /* If SET pattern SET is an assignment from a hard register to a pseudo which
4827 is live at CALL_DOM (if non-NULL, otherwise this check is omitted), return
4828 the destination. Otherwise return NULL. */
4830 static rtx
4831 interesting_dest_for_shprep_1 (rtx set, basic_block call_dom)
4833 rtx src = SET_SRC (set);
4834 rtx dest = SET_DEST (set);
4835 if (!REG_P (src) || !HARD_REGISTER_P (src)
4836 || !REG_P (dest) || HARD_REGISTER_P (dest)
4837 || (call_dom && !bitmap_bit_p (df_get_live_in (call_dom), REGNO (dest))))
4838 return NULL;
4839 return dest;
4842 /* If insn is interesting for parameter range-splitting shrink-wrapping
4843 preparation, i.e. it is a single set from a hard register to a pseudo, which
4844 is live at CALL_DOM (if non-NULL, otherwise this check is omitted), or a
4845 parallel statement with only one such statement, return the destination.
4846 Otherwise return NULL. */
4848 static rtx
4849 interesting_dest_for_shprep (rtx_insn *insn, basic_block call_dom)
4851 if (!INSN_P (insn))
4852 return NULL;
4853 rtx pat = PATTERN (insn);
4854 if (GET_CODE (pat) == SET)
4855 return interesting_dest_for_shprep_1 (pat, call_dom);
4857 if (GET_CODE (pat) != PARALLEL)
4858 return NULL;
4859 rtx ret = NULL;
4860 for (int i = 0; i < XVECLEN (pat, 0); i++)
4862 rtx sub = XVECEXP (pat, 0, i);
4863 if (GET_CODE (sub) == USE || GET_CODE (sub) == CLOBBER)
4864 continue;
4865 if (GET_CODE (sub) != SET
4866 || side_effects_p (sub))
4867 return NULL;
4868 rtx dest = interesting_dest_for_shprep_1 (sub, call_dom);
4869 if (dest && ret)
4870 return NULL;
4871 if (dest)
4872 ret = dest;
4874 return ret;
4877 /* Split live ranges of pseudos that are loaded from hard registers in the
4878 first BB in a BB that dominates all non-sibling call if such a BB can be
4879 found and is not in a loop. Return true if the function has made any
4880 changes. */
4882 static bool
4883 split_live_ranges_for_shrink_wrap (void)
4885 basic_block bb, call_dom = NULL;
4886 basic_block first = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
4887 rtx_insn *insn, *last_interesting_insn = NULL;
4888 auto_bitmap need_new, reachable;
4889 vec<basic_block> queue;
4891 if (!SHRINK_WRAPPING_ENABLED)
4892 return false;
4894 queue.create (n_basic_blocks_for_fn (cfun));
4896 FOR_EACH_BB_FN (bb, cfun)
4897 FOR_BB_INSNS (bb, insn)
4898 if (CALL_P (insn) && !SIBLING_CALL_P (insn))
4900 if (bb == first)
4902 queue.release ();
4903 return false;
4906 bitmap_set_bit (need_new, bb->index);
4907 bitmap_set_bit (reachable, bb->index);
4908 queue.quick_push (bb);
4909 break;
4912 if (queue.is_empty ())
4914 queue.release ();
4915 return false;
4918 while (!queue.is_empty ())
4920 edge e;
4921 edge_iterator ei;
4923 bb = queue.pop ();
4924 FOR_EACH_EDGE (e, ei, bb->succs)
4925 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
4926 && bitmap_set_bit (reachable, e->dest->index))
4927 queue.quick_push (e->dest);
4929 queue.release ();
4931 FOR_BB_INSNS (first, insn)
4933 rtx dest = interesting_dest_for_shprep (insn, NULL);
4934 if (!dest)
4935 continue;
4937 if (DF_REG_DEF_COUNT (REGNO (dest)) > 1)
4938 return false;
4940 for (df_ref use = DF_REG_USE_CHAIN (REGNO(dest));
4941 use;
4942 use = DF_REF_NEXT_REG (use))
4944 int ubbi = DF_REF_BB (use)->index;
4945 if (bitmap_bit_p (reachable, ubbi))
4946 bitmap_set_bit (need_new, ubbi);
4948 last_interesting_insn = insn;
4951 if (!last_interesting_insn)
4952 return false;
4954 call_dom = nearest_common_dominator_for_set (CDI_DOMINATORS, need_new);
4955 if (call_dom == first)
4956 return false;
4958 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
4959 while (bb_loop_depth (call_dom) > 0)
4960 call_dom = get_immediate_dominator (CDI_DOMINATORS, call_dom);
4961 loop_optimizer_finalize ();
4963 if (call_dom == first)
4964 return false;
4966 calculate_dominance_info (CDI_POST_DOMINATORS);
4967 if (dominated_by_p (CDI_POST_DOMINATORS, first, call_dom))
4969 free_dominance_info (CDI_POST_DOMINATORS);
4970 return false;
4972 free_dominance_info (CDI_POST_DOMINATORS);
4974 if (dump_file)
4975 fprintf (dump_file, "Will split live ranges of parameters at BB %i\n",
4976 call_dom->index);
4978 bool ret = false;
4979 FOR_BB_INSNS (first, insn)
4981 rtx dest = interesting_dest_for_shprep (insn, call_dom);
4982 if (!dest || dest == pic_offset_table_rtx)
4983 continue;
4985 bool need_newreg = false;
4986 df_ref use, next;
4987 for (use = DF_REG_USE_CHAIN (REGNO (dest)); use; use = next)
4989 rtx_insn *uin = DF_REF_INSN (use);
4990 next = DF_REF_NEXT_REG (use);
4992 if (DEBUG_INSN_P (uin))
4993 continue;
4995 basic_block ubb = BLOCK_FOR_INSN (uin);
4996 if (ubb == call_dom
4997 || dominated_by_p (CDI_DOMINATORS, ubb, call_dom))
4999 need_newreg = true;
5000 break;
5004 if (need_newreg)
5006 rtx newreg = ira_create_new_reg (dest);
5008 for (use = DF_REG_USE_CHAIN (REGNO (dest)); use; use = next)
5010 rtx_insn *uin = DF_REF_INSN (use);
5011 next = DF_REF_NEXT_REG (use);
5013 basic_block ubb = BLOCK_FOR_INSN (uin);
5014 if (ubb == call_dom
5015 || dominated_by_p (CDI_DOMINATORS, ubb, call_dom))
5016 validate_change (uin, DF_REF_REAL_LOC (use), newreg, true);
5019 rtx_insn *new_move = gen_move_insn (newreg, dest);
5020 emit_insn_after (new_move, bb_note (call_dom));
5021 if (dump_file)
5023 fprintf (dump_file, "Split live-range of register ");
5024 print_rtl_single (dump_file, dest);
5026 ret = true;
5029 if (insn == last_interesting_insn)
5030 break;
5032 apply_change_group ();
5033 return ret;
5036 /* Perform the second half of the transformation started in
5037 find_moveable_pseudos. We look for instances where the newly introduced
5038 pseudo remains unallocated, and remove it by moving the definition to
5039 just before its use, replacing the move instruction generated by
5040 find_moveable_pseudos. */
5041 static void
5042 move_unallocated_pseudos (void)
5044 int i;
5045 for (i = first_moveable_pseudo; i < last_moveable_pseudo; i++)
5046 if (reg_renumber[i] < 0)
5048 int idx = i - first_moveable_pseudo;
5049 rtx other_reg = pseudo_replaced_reg[idx];
5050 rtx_insn *def_insn = DF_REF_INSN (DF_REG_DEF_CHAIN (i));
5051 /* The use must follow all definitions of OTHER_REG, so we can
5052 insert the new definition immediately after any of them. */
5053 df_ref other_def = DF_REG_DEF_CHAIN (REGNO (other_reg));
5054 rtx_insn *move_insn = DF_REF_INSN (other_def);
5055 rtx_insn *newinsn = emit_insn_after (PATTERN (def_insn), move_insn);
5056 rtx set;
5057 int success;
5059 if (dump_file)
5060 fprintf (dump_file, "moving def of %d (insn %d now) ",
5061 REGNO (other_reg), INSN_UID (def_insn));
5063 delete_insn (move_insn);
5064 while ((other_def = DF_REG_DEF_CHAIN (REGNO (other_reg))))
5065 delete_insn (DF_REF_INSN (other_def));
5066 delete_insn (def_insn);
5068 set = single_set (newinsn);
5069 success = validate_change (newinsn, &SET_DEST (set), other_reg, 0);
5070 gcc_assert (success);
5071 if (dump_file)
5072 fprintf (dump_file, " %d) rather than keep unallocated replacement %d\n",
5073 INSN_UID (newinsn), i);
5074 SET_REG_N_REFS (i, 0);
5078 /* If the backend knows where to allocate pseudos for hard
5079 register initial values, register these allocations now. */
5080 static void
5081 allocate_initial_values (void)
5083 if (targetm.allocate_initial_value)
5085 rtx hreg, preg, x;
5086 int i, regno;
5088 for (i = 0; HARD_REGISTER_NUM_P (i); i++)
5090 if (! initial_value_entry (i, &hreg, &preg))
5091 break;
5093 x = targetm.allocate_initial_value (hreg);
5094 regno = REGNO (preg);
5095 if (x && REG_N_SETS (regno) <= 1)
5097 if (MEM_P (x))
5098 reg_equiv_memory_loc (regno) = x;
5099 else
5101 basic_block bb;
5102 int new_regno;
5104 gcc_assert (REG_P (x));
5105 new_regno = REGNO (x);
5106 reg_renumber[regno] = new_regno;
5107 /* Poke the regno right into regno_reg_rtx so that even
5108 fixed regs are accepted. */
5109 SET_REGNO (preg, new_regno);
5110 /* Update global register liveness information. */
5111 FOR_EACH_BB_FN (bb, cfun)
5113 if (REGNO_REG_SET_P (df_get_live_in (bb), regno))
5114 SET_REGNO_REG_SET (df_get_live_in (bb), new_regno);
5115 if (REGNO_REG_SET_P (df_get_live_out (bb), regno))
5116 SET_REGNO_REG_SET (df_get_live_out (bb), new_regno);
5122 gcc_checking_assert (! initial_value_entry (FIRST_PSEUDO_REGISTER,
5123 &hreg, &preg));
5128 /* True when we use LRA instead of reload pass for the current
5129 function. */
5130 bool ira_use_lra_p;
5132 /* True if we have allocno conflicts. It is false for non-optimized
5133 mode or when the conflict table is too big. */
5134 bool ira_conflicts_p;
5136 /* Saved between IRA and reload. */
5137 static int saved_flag_ira_share_spill_slots;
5139 /* This is the main entry of IRA. */
5140 static void
5141 ira (FILE *f)
5143 bool loops_p;
5144 int ira_max_point_before_emit;
5145 bool saved_flag_caller_saves = flag_caller_saves;
5146 enum ira_region saved_flag_ira_region = flag_ira_region;
5148 clear_bb_flags ();
5150 /* Determine if the current function is a leaf before running IRA
5151 since this can impact optimizations done by the prologue and
5152 epilogue thus changing register elimination offsets.
5153 Other target callbacks may use crtl->is_leaf too, including
5154 SHRINK_WRAPPING_ENABLED, so initialize as early as possible. */
5155 crtl->is_leaf = leaf_function_p ();
5157 /* Perform target specific PIC register initialization. */
5158 targetm.init_pic_reg ();
5160 ira_conflicts_p = optimize > 0;
5162 /* If there are too many pseudos and/or basic blocks (e.g. 10K
5163 pseudos and 10K blocks or 100K pseudos and 1K blocks), we will
5164 use simplified and faster algorithms in LRA. */
5165 lra_simple_p
5166 = (ira_use_lra_p
5167 && max_reg_num () >= (1 << 26) / last_basic_block_for_fn (cfun));
5168 if (lra_simple_p)
5170 /* It permits to skip live range splitting in LRA. */
5171 flag_caller_saves = false;
5172 /* There is no sense to do regional allocation when we use
5173 simplified LRA. */
5174 flag_ira_region = IRA_REGION_ONE;
5175 ira_conflicts_p = false;
5178 #ifndef IRA_NO_OBSTACK
5179 gcc_obstack_init (&ira_obstack);
5180 #endif
5181 bitmap_obstack_initialize (&ira_bitmap_obstack);
5183 /* LRA uses its own infrastructure to handle caller save registers. */
5184 if (flag_caller_saves && !ira_use_lra_p)
5185 init_caller_save ();
5187 if (flag_ira_verbose < 10)
5189 internal_flag_ira_verbose = flag_ira_verbose;
5190 ira_dump_file = f;
5192 else
5194 internal_flag_ira_verbose = flag_ira_verbose - 10;
5195 ira_dump_file = stderr;
5198 setup_prohibited_mode_move_regs ();
5199 decrease_live_ranges_number ();
5200 df_note_add_problem ();
5202 /* DF_LIVE can't be used in the register allocator, too many other
5203 parts of the compiler depend on using the "classic" liveness
5204 interpretation of the DF_LR problem. See PR38711.
5205 Remove the problem, so that we don't spend time updating it in
5206 any of the df_analyze() calls during IRA/LRA. */
5207 if (optimize > 1)
5208 df_remove_problem (df_live);
5209 gcc_checking_assert (df_live == NULL);
5211 if (flag_checking)
5212 df->changeable_flags |= DF_VERIFY_SCHEDULED;
5214 df_analyze ();
5216 init_reg_equiv ();
5217 if (ira_conflicts_p)
5219 calculate_dominance_info (CDI_DOMINATORS);
5221 if (split_live_ranges_for_shrink_wrap ())
5222 df_analyze ();
5224 free_dominance_info (CDI_DOMINATORS);
5227 df_clear_flags (DF_NO_INSN_RESCAN);
5229 indirect_jump_optimize ();
5230 if (delete_trivially_dead_insns (get_insns (), max_reg_num ()))
5231 df_analyze ();
5233 regstat_init_n_sets_and_refs ();
5234 regstat_compute_ri ();
5236 /* If we are not optimizing, then this is the only place before
5237 register allocation where dataflow is done. And that is needed
5238 to generate these warnings. */
5239 if (warn_clobbered)
5240 generate_setjmp_warnings ();
5242 if (resize_reg_info () && flag_ira_loop_pressure)
5243 ira_set_pseudo_classes (true, ira_dump_file);
5245 init_alias_analysis ();
5246 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
5247 reg_equiv = XCNEWVEC (struct equivalence, max_reg_num ());
5248 update_equiv_regs ();
5250 /* Don't move insns if live range shrinkage or register
5251 pressure-sensitive scheduling were done because it will not
5252 improve allocation but likely worsen insn scheduling. */
5253 if (optimize
5254 && !flag_live_range_shrinkage
5255 && !(flag_sched_pressure && flag_schedule_insns))
5256 combine_and_move_insns ();
5258 /* Gather additional equivalences with memory. */
5259 if (optimize)
5260 add_store_equivs ();
5262 loop_optimizer_finalize ();
5263 free_dominance_info (CDI_DOMINATORS);
5264 end_alias_analysis ();
5265 free (reg_equiv);
5267 setup_reg_equiv ();
5268 grow_reg_equivs ();
5269 setup_reg_equiv_init ();
5271 allocated_reg_info_size = max_reg_num ();
5273 /* It is not worth to do such improvement when we use a simple
5274 allocation because of -O0 usage or because the function is too
5275 big. */
5276 if (ira_conflicts_p)
5277 find_moveable_pseudos ();
5279 max_regno_before_ira = max_reg_num ();
5280 ira_setup_eliminable_regset ();
5282 ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
5283 ira_load_cost = ira_store_cost = ira_shuffle_cost = 0;
5284 ira_move_loops_num = ira_additional_jumps_num = 0;
5286 ira_assert (current_loops == NULL);
5287 if (flag_ira_region == IRA_REGION_ALL || flag_ira_region == IRA_REGION_MIXED)
5288 loop_optimizer_init (AVOID_CFG_MODIFICATIONS | LOOPS_HAVE_RECORDED_EXITS);
5290 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
5291 fprintf (ira_dump_file, "Building IRA IR\n");
5292 loops_p = ira_build ();
5294 ira_assert (ira_conflicts_p || !loops_p);
5296 saved_flag_ira_share_spill_slots = flag_ira_share_spill_slots;
5297 if (too_high_register_pressure_p () || cfun->calls_setjmp)
5298 /* It is just wasting compiler's time to pack spilled pseudos into
5299 stack slots in this case -- prohibit it. We also do this if
5300 there is setjmp call because a variable not modified between
5301 setjmp and longjmp the compiler is required to preserve its
5302 value and sharing slots does not guarantee it. */
5303 flag_ira_share_spill_slots = FALSE;
5305 ira_color ();
5307 ira_max_point_before_emit = ira_max_point;
5309 ira_initiate_emit_data ();
5311 ira_emit (loops_p);
5313 max_regno = max_reg_num ();
5314 if (ira_conflicts_p)
5316 if (! loops_p)
5318 if (! ira_use_lra_p)
5319 ira_initiate_assign ();
5321 else
5323 expand_reg_info ();
5325 if (ira_use_lra_p)
5327 ira_allocno_t a;
5328 ira_allocno_iterator ai;
5330 FOR_EACH_ALLOCNO (a, ai)
5332 int old_regno = ALLOCNO_REGNO (a);
5333 int new_regno = REGNO (ALLOCNO_EMIT_DATA (a)->reg);
5335 ALLOCNO_REGNO (a) = new_regno;
5337 if (old_regno != new_regno)
5338 setup_reg_classes (new_regno, reg_preferred_class (old_regno),
5339 reg_alternate_class (old_regno),
5340 reg_allocno_class (old_regno));
5343 else
5345 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
5346 fprintf (ira_dump_file, "Flattening IR\n");
5347 ira_flattening (max_regno_before_ira, ira_max_point_before_emit);
5349 /* New insns were generated: add notes and recalculate live
5350 info. */
5351 df_analyze ();
5353 /* ??? Rebuild the loop tree, but why? Does the loop tree
5354 change if new insns were generated? Can that be handled
5355 by updating the loop tree incrementally? */
5356 loop_optimizer_finalize ();
5357 free_dominance_info (CDI_DOMINATORS);
5358 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
5359 | LOOPS_HAVE_RECORDED_EXITS);
5361 if (! ira_use_lra_p)
5363 setup_allocno_assignment_flags ();
5364 ira_initiate_assign ();
5365 ira_reassign_conflict_allocnos (max_regno);
5370 ira_finish_emit_data ();
5372 setup_reg_renumber ();
5374 calculate_allocation_cost ();
5376 #ifdef ENABLE_IRA_CHECKING
5377 if (ira_conflicts_p && ! ira_use_lra_p)
5378 /* Opposite to reload pass, LRA does not use any conflict info
5379 from IRA. We don't rebuild conflict info for LRA (through
5380 ira_flattening call) and can not use the check here. We could
5381 rebuild this info for LRA in the check mode but there is a risk
5382 that code generated with the check and without it will be a bit
5383 different. Calling ira_flattening in any mode would be a
5384 wasting CPU time. So do not check the allocation for LRA. */
5385 check_allocation ();
5386 #endif
5388 if (max_regno != max_regno_before_ira)
5390 regstat_free_n_sets_and_refs ();
5391 regstat_free_ri ();
5392 regstat_init_n_sets_and_refs ();
5393 regstat_compute_ri ();
5396 overall_cost_before = ira_overall_cost;
5397 if (! ira_conflicts_p)
5398 grow_reg_equivs ();
5399 else
5401 fix_reg_equiv_init ();
5403 #ifdef ENABLE_IRA_CHECKING
5404 print_redundant_copies ();
5405 #endif
5406 if (! ira_use_lra_p)
5408 ira_spilled_reg_stack_slots_num = 0;
5409 ira_spilled_reg_stack_slots
5410 = ((struct ira_spilled_reg_stack_slot *)
5411 ira_allocate (max_regno
5412 * sizeof (struct ira_spilled_reg_stack_slot)));
5413 memset (ira_spilled_reg_stack_slots, 0,
5414 max_regno * sizeof (struct ira_spilled_reg_stack_slot));
5417 allocate_initial_values ();
5419 /* See comment for find_moveable_pseudos call. */
5420 if (ira_conflicts_p)
5421 move_unallocated_pseudos ();
5423 /* Restore original values. */
5424 if (lra_simple_p)
5426 flag_caller_saves = saved_flag_caller_saves;
5427 flag_ira_region = saved_flag_ira_region;
5431 static void
5432 do_reload (void)
5434 basic_block bb;
5435 bool need_dce;
5436 unsigned pic_offset_table_regno = INVALID_REGNUM;
5438 if (flag_ira_verbose < 10)
5439 ira_dump_file = dump_file;
5441 /* If pic_offset_table_rtx is a pseudo register, then keep it so
5442 after reload to avoid possible wrong usages of hard reg assigned
5443 to it. */
5444 if (pic_offset_table_rtx
5445 && REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER)
5446 pic_offset_table_regno = REGNO (pic_offset_table_rtx);
5448 timevar_push (TV_RELOAD);
5449 if (ira_use_lra_p)
5451 if (current_loops != NULL)
5453 loop_optimizer_finalize ();
5454 free_dominance_info (CDI_DOMINATORS);
5456 FOR_ALL_BB_FN (bb, cfun)
5457 bb->loop_father = NULL;
5458 current_loops = NULL;
5460 ira_destroy ();
5462 lra (ira_dump_file);
5463 /* ???!!! Move it before lra () when we use ira_reg_equiv in
5464 LRA. */
5465 vec_free (reg_equivs);
5466 reg_equivs = NULL;
5467 need_dce = false;
5469 else
5471 df_set_flags (DF_NO_INSN_RESCAN);
5472 build_insn_chain ();
5474 need_dce = reload (get_insns (), ira_conflicts_p);
5477 timevar_pop (TV_RELOAD);
5479 timevar_push (TV_IRA);
5481 if (ira_conflicts_p && ! ira_use_lra_p)
5483 ira_free (ira_spilled_reg_stack_slots);
5484 ira_finish_assign ();
5487 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL
5488 && overall_cost_before != ira_overall_cost)
5489 fprintf (ira_dump_file, "+++Overall after reload %" PRId64 "\n",
5490 ira_overall_cost);
5492 flag_ira_share_spill_slots = saved_flag_ira_share_spill_slots;
5494 if (! ira_use_lra_p)
5496 ira_destroy ();
5497 if (current_loops != NULL)
5499 loop_optimizer_finalize ();
5500 free_dominance_info (CDI_DOMINATORS);
5502 FOR_ALL_BB_FN (bb, cfun)
5503 bb->loop_father = NULL;
5504 current_loops = NULL;
5506 regstat_free_ri ();
5507 regstat_free_n_sets_and_refs ();
5510 if (optimize)
5511 cleanup_cfg (CLEANUP_EXPENSIVE);
5513 finish_reg_equiv ();
5515 bitmap_obstack_release (&ira_bitmap_obstack);
5516 #ifndef IRA_NO_OBSTACK
5517 obstack_free (&ira_obstack, NULL);
5518 #endif
5520 /* The code after the reload has changed so much that at this point
5521 we might as well just rescan everything. Note that
5522 df_rescan_all_insns is not going to help here because it does not
5523 touch the artificial uses and defs. */
5524 df_finish_pass (true);
5525 df_scan_alloc (NULL);
5526 df_scan_blocks ();
5528 if (optimize > 1)
5530 df_live_add_problem ();
5531 df_live_set_all_dirty ();
5534 if (optimize)
5535 df_analyze ();
5537 if (need_dce && optimize)
5538 run_fast_dce ();
5540 /* Diagnose uses of the hard frame pointer when it is used as a global
5541 register. Often we can get away with letting the user appropriate
5542 the frame pointer, but we should let them know when code generation
5543 makes that impossible. */
5544 if (global_regs[HARD_FRAME_POINTER_REGNUM] && frame_pointer_needed)
5546 tree decl = global_regs_decl[HARD_FRAME_POINTER_REGNUM];
5547 error_at (DECL_SOURCE_LOCATION (current_function_decl),
5548 "frame pointer required, but reserved");
5549 inform (DECL_SOURCE_LOCATION (decl), "for %qD", decl);
5552 /* If we are doing generic stack checking, give a warning if this
5553 function's frame size is larger than we expect. */
5554 if (flag_stack_check == GENERIC_STACK_CHECK)
5556 poly_int64 size = get_frame_size () + STACK_CHECK_FIXED_FRAME_SIZE;
5558 for (int i = 0; i < FIRST_PSEUDO_REGISTER; i++)
5559 if (df_regs_ever_live_p (i) && !fixed_regs[i] && call_used_regs[i])
5560 size += UNITS_PER_WORD;
5562 if (constant_lower_bound (size) > STACK_CHECK_MAX_FRAME_SIZE)
5563 warning (0, "frame size too large for reliable stack checking");
5566 if (pic_offset_table_regno != INVALID_REGNUM)
5567 pic_offset_table_rtx = gen_rtx_REG (Pmode, pic_offset_table_regno);
5569 timevar_pop (TV_IRA);
5572 /* Run the integrated register allocator. */
5574 namespace {
5576 const pass_data pass_data_ira =
5578 RTL_PASS, /* type */
5579 "ira", /* name */
5580 OPTGROUP_NONE, /* optinfo_flags */
5581 TV_IRA, /* tv_id */
5582 0, /* properties_required */
5583 0, /* properties_provided */
5584 0, /* properties_destroyed */
5585 0, /* todo_flags_start */
5586 TODO_do_not_ggc_collect, /* todo_flags_finish */
5589 class pass_ira : public rtl_opt_pass
5591 public:
5592 pass_ira (gcc::context *ctxt)
5593 : rtl_opt_pass (pass_data_ira, ctxt)
5596 /* opt_pass methods: */
5597 virtual bool gate (function *)
5599 return !targetm.no_register_allocation;
5601 virtual unsigned int execute (function *)
5603 ira (dump_file);
5604 return 0;
5607 }; // class pass_ira
5609 } // anon namespace
5611 rtl_opt_pass *
5612 make_pass_ira (gcc::context *ctxt)
5614 return new pass_ira (ctxt);
5617 namespace {
5619 const pass_data pass_data_reload =
5621 RTL_PASS, /* type */
5622 "reload", /* name */
5623 OPTGROUP_NONE, /* optinfo_flags */
5624 TV_RELOAD, /* tv_id */
5625 0, /* properties_required */
5626 0, /* properties_provided */
5627 0, /* properties_destroyed */
5628 0, /* todo_flags_start */
5629 0, /* todo_flags_finish */
5632 class pass_reload : public rtl_opt_pass
5634 public:
5635 pass_reload (gcc::context *ctxt)
5636 : rtl_opt_pass (pass_data_reload, ctxt)
5639 /* opt_pass methods: */
5640 virtual bool gate (function *)
5642 return !targetm.no_register_allocation;
5644 virtual unsigned int execute (function *)
5646 do_reload ();
5647 return 0;
5650 }; // class pass_reload
5652 } // anon namespace
5654 rtl_opt_pass *
5655 make_pass_reload (gcc::context *ctxt)
5657 return new pass_reload (ctxt);