Fix bootstrap/PR63632
[official-gcc.git] / gcc / ira.c
blob235a21171df9a4f61b17d595d50c6c81714a76fe
1 /* Integrated Register Allocator (IRA) entry point.
2 Copyright (C) 2006-2014 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 "tm.h"
370 #include "regs.h"
371 #include "tree.h"
372 #include "rtl.h"
373 #include "tm_p.h"
374 #include "target.h"
375 #include "flags.h"
376 #include "obstack.h"
377 #include "bitmap.h"
378 #include "hard-reg-set.h"
379 #include "basic-block.h"
380 #include "df.h"
381 #include "expr.h"
382 #include "recog.h"
383 #include "params.h"
384 #include "tree-pass.h"
385 #include "output.h"
386 #include "except.h"
387 #include "reload.h"
388 #include "diagnostic-core.h"
389 #include "hashtab.h"
390 #include "hash-set.h"
391 #include "vec.h"
392 #include "machmode.h"
393 #include "input.h"
394 #include "function.h"
395 #include "ggc.h"
396 #include "ira-int.h"
397 #include "lra.h"
398 #include "dce.h"
399 #include "dbgcnt.h"
400 #include "rtl-iter.h"
401 #include "shrink-wrap.h"
403 struct target_ira default_target_ira;
404 struct target_ira_int default_target_ira_int;
405 #if SWITCHABLE_TARGET
406 struct target_ira *this_target_ira = &default_target_ira;
407 struct target_ira_int *this_target_ira_int = &default_target_ira_int;
408 #endif
410 /* A modified value of flag `-fira-verbose' used internally. */
411 int internal_flag_ira_verbose;
413 /* Dump file of the allocator if it is not NULL. */
414 FILE *ira_dump_file;
416 /* The number of elements in the following array. */
417 int ira_spilled_reg_stack_slots_num;
419 /* The following array contains info about spilled pseudo-registers
420 stack slots used in current function so far. */
421 struct ira_spilled_reg_stack_slot *ira_spilled_reg_stack_slots;
423 /* Correspondingly overall cost of the allocation, overall cost before
424 reload, cost of the allocnos assigned to hard-registers, cost of
425 the allocnos assigned to memory, cost of loads, stores and register
426 move insns generated for pseudo-register live range splitting (see
427 ira-emit.c). */
428 int ira_overall_cost, overall_cost_before;
429 int ira_reg_cost, ira_mem_cost;
430 int ira_load_cost, ira_store_cost, ira_shuffle_cost;
431 int ira_move_loops_num, ira_additional_jumps_num;
433 /* All registers that can be eliminated. */
435 HARD_REG_SET eliminable_regset;
437 /* Value of max_reg_num () before IRA work start. This value helps
438 us to recognize a situation when new pseudos were created during
439 IRA work. */
440 static int max_regno_before_ira;
442 /* Temporary hard reg set used for a different calculation. */
443 static HARD_REG_SET temp_hard_regset;
445 #define last_mode_for_init_move_cost \
446 (this_target_ira_int->x_last_mode_for_init_move_cost)
449 /* The function sets up the map IRA_REG_MODE_HARD_REGSET. */
450 static void
451 setup_reg_mode_hard_regset (void)
453 int i, m, hard_regno;
455 for (m = 0; m < NUM_MACHINE_MODES; m++)
456 for (hard_regno = 0; hard_regno < FIRST_PSEUDO_REGISTER; hard_regno++)
458 CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset[hard_regno][m]);
459 for (i = hard_regno_nregs[hard_regno][m] - 1; i >= 0; i--)
460 if (hard_regno + i < FIRST_PSEUDO_REGISTER)
461 SET_HARD_REG_BIT (ira_reg_mode_hard_regset[hard_regno][m],
462 hard_regno + i);
467 #define no_unit_alloc_regs \
468 (this_target_ira_int->x_no_unit_alloc_regs)
470 /* The function sets up the three arrays declared above. */
471 static void
472 setup_class_hard_regs (void)
474 int cl, i, hard_regno, n;
475 HARD_REG_SET processed_hard_reg_set;
477 ira_assert (SHRT_MAX >= FIRST_PSEUDO_REGISTER);
478 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
480 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
481 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
482 CLEAR_HARD_REG_SET (processed_hard_reg_set);
483 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
485 ira_non_ordered_class_hard_regs[cl][i] = -1;
486 ira_class_hard_reg_index[cl][i] = -1;
488 for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
490 #ifdef REG_ALLOC_ORDER
491 hard_regno = reg_alloc_order[i];
492 #else
493 hard_regno = i;
494 #endif
495 if (TEST_HARD_REG_BIT (processed_hard_reg_set, hard_regno))
496 continue;
497 SET_HARD_REG_BIT (processed_hard_reg_set, hard_regno);
498 if (! TEST_HARD_REG_BIT (temp_hard_regset, hard_regno))
499 ira_class_hard_reg_index[cl][hard_regno] = -1;
500 else
502 ira_class_hard_reg_index[cl][hard_regno] = n;
503 ira_class_hard_regs[cl][n++] = hard_regno;
506 ira_class_hard_regs_num[cl] = n;
507 for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
508 if (TEST_HARD_REG_BIT (temp_hard_regset, i))
509 ira_non_ordered_class_hard_regs[cl][n++] = i;
510 ira_assert (ira_class_hard_regs_num[cl] == n);
514 /* Set up global variables defining info about hard registers for the
515 allocation. These depend on USE_HARD_FRAME_P whose TRUE value means
516 that we can use the hard frame pointer for the allocation. */
517 static void
518 setup_alloc_regs (bool use_hard_frame_p)
520 #ifdef ADJUST_REG_ALLOC_ORDER
521 ADJUST_REG_ALLOC_ORDER;
522 #endif
523 COPY_HARD_REG_SET (no_unit_alloc_regs, fixed_reg_set);
524 if (! use_hard_frame_p)
525 SET_HARD_REG_BIT (no_unit_alloc_regs, HARD_FRAME_POINTER_REGNUM);
526 setup_class_hard_regs ();
531 #define alloc_reg_class_subclasses \
532 (this_target_ira_int->x_alloc_reg_class_subclasses)
534 /* Initialize the table of subclasses of each reg class. */
535 static void
536 setup_reg_subclasses (void)
538 int i, j;
539 HARD_REG_SET temp_hard_regset2;
541 for (i = 0; i < N_REG_CLASSES; i++)
542 for (j = 0; j < N_REG_CLASSES; j++)
543 alloc_reg_class_subclasses[i][j] = LIM_REG_CLASSES;
545 for (i = 0; i < N_REG_CLASSES; i++)
547 if (i == (int) NO_REGS)
548 continue;
550 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
551 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
552 if (hard_reg_set_empty_p (temp_hard_regset))
553 continue;
554 for (j = 0; j < N_REG_CLASSES; j++)
555 if (i != j)
557 enum reg_class *p;
559 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[j]);
560 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
561 if (! hard_reg_set_subset_p (temp_hard_regset,
562 temp_hard_regset2))
563 continue;
564 p = &alloc_reg_class_subclasses[j][0];
565 while (*p != LIM_REG_CLASSES) p++;
566 *p = (enum reg_class) i;
573 /* Set up IRA_MEMORY_MOVE_COST and IRA_MAX_MEMORY_MOVE_COST. */
574 static void
575 setup_class_subset_and_memory_move_costs (void)
577 int cl, cl2, mode, cost;
578 HARD_REG_SET temp_hard_regset2;
580 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
581 ira_memory_move_cost[mode][NO_REGS][0]
582 = ira_memory_move_cost[mode][NO_REGS][1] = SHRT_MAX;
583 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
585 if (cl != (int) NO_REGS)
586 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
588 ira_max_memory_move_cost[mode][cl][0]
589 = ira_memory_move_cost[mode][cl][0]
590 = memory_move_cost ((enum machine_mode) mode,
591 (reg_class_t) cl, false);
592 ira_max_memory_move_cost[mode][cl][1]
593 = ira_memory_move_cost[mode][cl][1]
594 = memory_move_cost ((enum machine_mode) mode,
595 (reg_class_t) cl, true);
596 /* Costs for NO_REGS are used in cost calculation on the
597 1st pass when the preferred register classes are not
598 known yet. In this case we take the best scenario. */
599 if (ira_memory_move_cost[mode][NO_REGS][0]
600 > ira_memory_move_cost[mode][cl][0])
601 ira_max_memory_move_cost[mode][NO_REGS][0]
602 = ira_memory_move_cost[mode][NO_REGS][0]
603 = ira_memory_move_cost[mode][cl][0];
604 if (ira_memory_move_cost[mode][NO_REGS][1]
605 > ira_memory_move_cost[mode][cl][1])
606 ira_max_memory_move_cost[mode][NO_REGS][1]
607 = ira_memory_move_cost[mode][NO_REGS][1]
608 = ira_memory_move_cost[mode][cl][1];
611 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
612 for (cl2 = (int) N_REG_CLASSES - 1; cl2 >= 0; cl2--)
614 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
615 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
616 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]);
617 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
618 ira_class_subset_p[cl][cl2]
619 = hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2);
620 if (! hard_reg_set_empty_p (temp_hard_regset2)
621 && hard_reg_set_subset_p (reg_class_contents[cl2],
622 reg_class_contents[cl]))
623 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
625 cost = ira_memory_move_cost[mode][cl2][0];
626 if (cost > ira_max_memory_move_cost[mode][cl][0])
627 ira_max_memory_move_cost[mode][cl][0] = cost;
628 cost = ira_memory_move_cost[mode][cl2][1];
629 if (cost > ira_max_memory_move_cost[mode][cl][1])
630 ira_max_memory_move_cost[mode][cl][1] = cost;
633 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
634 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
636 ira_memory_move_cost[mode][cl][0]
637 = ira_max_memory_move_cost[mode][cl][0];
638 ira_memory_move_cost[mode][cl][1]
639 = ira_max_memory_move_cost[mode][cl][1];
641 setup_reg_subclasses ();
646 /* Define the following macro if allocation through malloc if
647 preferable. */
648 #define IRA_NO_OBSTACK
650 #ifndef IRA_NO_OBSTACK
651 /* Obstack used for storing all dynamic data (except bitmaps) of the
652 IRA. */
653 static struct obstack ira_obstack;
654 #endif
656 /* Obstack used for storing all bitmaps of the IRA. */
657 static struct bitmap_obstack ira_bitmap_obstack;
659 /* Allocate memory of size LEN for IRA data. */
660 void *
661 ira_allocate (size_t len)
663 void *res;
665 #ifndef IRA_NO_OBSTACK
666 res = obstack_alloc (&ira_obstack, len);
667 #else
668 res = xmalloc (len);
669 #endif
670 return res;
673 /* Free memory ADDR allocated for IRA data. */
674 void
675 ira_free (void *addr ATTRIBUTE_UNUSED)
677 #ifndef IRA_NO_OBSTACK
678 /* do nothing */
679 #else
680 free (addr);
681 #endif
685 /* Allocate and returns bitmap for IRA. */
686 bitmap
687 ira_allocate_bitmap (void)
689 return BITMAP_ALLOC (&ira_bitmap_obstack);
692 /* Free bitmap B allocated for IRA. */
693 void
694 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED)
696 /* do nothing */
701 /* Output information about allocation of all allocnos (except for
702 caps) into file F. */
703 void
704 ira_print_disposition (FILE *f)
706 int i, n, max_regno;
707 ira_allocno_t a;
708 basic_block bb;
710 fprintf (f, "Disposition:");
711 max_regno = max_reg_num ();
712 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
713 for (a = ira_regno_allocno_map[i];
714 a != NULL;
715 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
717 if (n % 4 == 0)
718 fprintf (f, "\n");
719 n++;
720 fprintf (f, " %4d:r%-4d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
721 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
722 fprintf (f, "b%-3d", bb->index);
723 else
724 fprintf (f, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
725 if (ALLOCNO_HARD_REGNO (a) >= 0)
726 fprintf (f, " %3d", ALLOCNO_HARD_REGNO (a));
727 else
728 fprintf (f, " mem");
730 fprintf (f, "\n");
733 /* Outputs information about allocation of all allocnos into
734 stderr. */
735 void
736 ira_debug_disposition (void)
738 ira_print_disposition (stderr);
743 /* Set up ira_stack_reg_pressure_class which is the biggest pressure
744 register class containing stack registers or NO_REGS if there are
745 no stack registers. To find this class, we iterate through all
746 register pressure classes and choose the first register pressure
747 class containing all the stack registers and having the biggest
748 size. */
749 static void
750 setup_stack_reg_pressure_class (void)
752 ira_stack_reg_pressure_class = NO_REGS;
753 #ifdef STACK_REGS
755 int i, best, size;
756 enum reg_class cl;
757 HARD_REG_SET temp_hard_regset2;
759 CLEAR_HARD_REG_SET (temp_hard_regset);
760 for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
761 SET_HARD_REG_BIT (temp_hard_regset, i);
762 best = 0;
763 for (i = 0; i < ira_pressure_classes_num; i++)
765 cl = ira_pressure_classes[i];
766 COPY_HARD_REG_SET (temp_hard_regset2, temp_hard_regset);
767 AND_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
768 size = hard_reg_set_size (temp_hard_regset2);
769 if (best < size)
771 best = size;
772 ira_stack_reg_pressure_class = cl;
776 #endif
779 /* Find pressure classes which are register classes for which we
780 calculate register pressure in IRA, register pressure sensitive
781 insn scheduling, and register pressure sensitive loop invariant
782 motion.
784 To make register pressure calculation easy, we always use
785 non-intersected register pressure classes. A move of hard
786 registers from one register pressure class is not more expensive
787 than load and store of the hard registers. Most likely an allocno
788 class will be a subset of a register pressure class and in many
789 cases a register pressure class. That makes usage of register
790 pressure classes a good approximation to find a high register
791 pressure. */
792 static void
793 setup_pressure_classes (void)
795 int cost, i, n, curr;
796 int cl, cl2;
797 enum reg_class pressure_classes[N_REG_CLASSES];
798 int m;
799 HARD_REG_SET temp_hard_regset2;
800 bool insert_p;
802 n = 0;
803 for (cl = 0; cl < N_REG_CLASSES; cl++)
805 if (ira_class_hard_regs_num[cl] == 0)
806 continue;
807 if (ira_class_hard_regs_num[cl] != 1
808 /* A register class without subclasses may contain a few
809 hard registers and movement between them is costly
810 (e.g. SPARC FPCC registers). We still should consider it
811 as a candidate for a pressure class. */
812 && alloc_reg_class_subclasses[cl][0] < cl)
814 /* Check that the moves between any hard registers of the
815 current class are not more expensive for a legal mode
816 than load/store of the hard registers of the current
817 class. Such class is a potential candidate to be a
818 register pressure class. */
819 for (m = 0; m < NUM_MACHINE_MODES; m++)
821 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
822 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
823 AND_COMPL_HARD_REG_SET (temp_hard_regset,
824 ira_prohibited_class_mode_regs[cl][m]);
825 if (hard_reg_set_empty_p (temp_hard_regset))
826 continue;
827 ira_init_register_move_cost_if_necessary ((enum machine_mode) m);
828 cost = ira_register_move_cost[m][cl][cl];
829 if (cost <= ira_max_memory_move_cost[m][cl][1]
830 || cost <= ira_max_memory_move_cost[m][cl][0])
831 break;
833 if (m >= NUM_MACHINE_MODES)
834 continue;
836 curr = 0;
837 insert_p = true;
838 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
839 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
840 /* Remove so far added pressure classes which are subset of the
841 current candidate class. Prefer GENERAL_REGS as a pressure
842 register class to another class containing the same
843 allocatable hard registers. We do this because machine
844 dependent cost hooks might give wrong costs for the latter
845 class but always give the right cost for the former class
846 (GENERAL_REGS). */
847 for (i = 0; i < n; i++)
849 cl2 = pressure_classes[i];
850 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]);
851 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
852 if (hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2)
853 && (! hard_reg_set_equal_p (temp_hard_regset, temp_hard_regset2)
854 || cl2 == (int) GENERAL_REGS))
856 pressure_classes[curr++] = (enum reg_class) cl2;
857 insert_p = false;
858 continue;
860 if (hard_reg_set_subset_p (temp_hard_regset2, temp_hard_regset)
861 && (! hard_reg_set_equal_p (temp_hard_regset2, 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;
875 #ifdef ENABLE_IRA_CHECKING
877 HARD_REG_SET ignore_hard_regs;
879 /* Check pressure classes correctness: here we check that hard
880 registers from all register pressure classes contains all hard
881 registers available for the allocation. */
882 CLEAR_HARD_REG_SET (temp_hard_regset);
883 CLEAR_HARD_REG_SET (temp_hard_regset2);
884 COPY_HARD_REG_SET (ignore_hard_regs, no_unit_alloc_regs);
885 for (cl = 0; cl < LIM_REG_CLASSES; cl++)
887 /* For some targets (like MIPS with MD_REGS), there are some
888 classes with hard registers available for allocation but
889 not able to hold value of any mode. */
890 for (m = 0; m < NUM_MACHINE_MODES; m++)
891 if (contains_reg_of_mode[cl][m])
892 break;
893 if (m >= NUM_MACHINE_MODES)
895 IOR_HARD_REG_SET (ignore_hard_regs, reg_class_contents[cl]);
896 continue;
898 for (i = 0; i < n; i++)
899 if ((int) pressure_classes[i] == cl)
900 break;
901 IOR_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
902 if (i < n)
903 IOR_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
905 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
906 /* Some targets (like SPARC with ICC reg) have allocatable regs
907 for which no reg class is defined. */
908 if (REGNO_REG_CLASS (i) == NO_REGS)
909 SET_HARD_REG_BIT (ignore_hard_regs, i);
910 AND_COMPL_HARD_REG_SET (temp_hard_regset, ignore_hard_regs);
911 AND_COMPL_HARD_REG_SET (temp_hard_regset2, ignore_hard_regs);
912 ira_assert (hard_reg_set_subset_p (temp_hard_regset2, temp_hard_regset));
914 #endif
915 ira_pressure_classes_num = 0;
916 for (i = 0; i < n; i++)
918 cl = (int) pressure_classes[i];
919 ira_reg_pressure_class_p[cl] = true;
920 ira_pressure_classes[ira_pressure_classes_num++] = (enum reg_class) cl;
922 setup_stack_reg_pressure_class ();
925 /* Set up IRA_UNIFORM_CLASS_P. Uniform class is a register class
926 whose register move cost between any registers of the class is the
927 same as for all its subclasses. We use the data to speed up the
928 2nd pass of calculations of allocno costs. */
929 static void
930 setup_uniform_class_p (void)
932 int i, cl, cl2, m;
934 for (cl = 0; cl < N_REG_CLASSES; cl++)
936 ira_uniform_class_p[cl] = false;
937 if (ira_class_hard_regs_num[cl] == 0)
938 continue;
939 /* We can not use alloc_reg_class_subclasses here because move
940 cost hooks does not take into account that some registers are
941 unavailable for the subtarget. E.g. for i686, INT_SSE_REGS
942 is element of alloc_reg_class_subclasses for GENERAL_REGS
943 because SSE regs are unavailable. */
944 for (i = 0; (cl2 = reg_class_subclasses[cl][i]) != LIM_REG_CLASSES; i++)
946 if (ira_class_hard_regs_num[cl2] == 0)
947 continue;
948 for (m = 0; m < NUM_MACHINE_MODES; m++)
949 if (contains_reg_of_mode[cl][m] && contains_reg_of_mode[cl2][m])
951 ira_init_register_move_cost_if_necessary ((enum machine_mode) m);
952 if (ira_register_move_cost[m][cl][cl]
953 != ira_register_move_cost[m][cl2][cl2])
954 break;
956 if (m < NUM_MACHINE_MODES)
957 break;
959 if (cl2 == LIM_REG_CLASSES)
960 ira_uniform_class_p[cl] = true;
964 /* Set up IRA_ALLOCNO_CLASSES, IRA_ALLOCNO_CLASSES_NUM,
965 IRA_IMPORTANT_CLASSES, and IRA_IMPORTANT_CLASSES_NUM.
967 Target may have many subtargets and not all target hard registers can
968 be used for allocation, e.g. x86 port in 32-bit mode can not use
969 hard registers introduced in x86-64 like r8-r15). Some classes
970 might have the same allocatable hard registers, e.g. INDEX_REGS
971 and GENERAL_REGS in x86 port in 32-bit mode. To decrease different
972 calculations efforts we introduce allocno classes which contain
973 unique non-empty sets of allocatable hard-registers.
975 Pseudo class cost calculation in ira-costs.c is very expensive.
976 Therefore we are trying to decrease number of classes involved in
977 such calculation. Register classes used in the cost calculation
978 are called important classes. They are allocno classes and other
979 non-empty classes whose allocatable hard register sets are inside
980 of an allocno class hard register set. From the first sight, it
981 looks like that they are just allocno classes. It is not true. In
982 example of x86-port in 32-bit mode, allocno classes will contain
983 GENERAL_REGS but not LEGACY_REGS (because allocatable hard
984 registers are the same for the both classes). The important
985 classes will contain GENERAL_REGS and LEGACY_REGS. It is done
986 because a machine description insn constraint may refers for
987 LEGACY_REGS and code in ira-costs.c is mostly base on investigation
988 of the insn constraints. */
989 static void
990 setup_allocno_and_important_classes (void)
992 int i, j, n, cl;
993 bool set_p;
994 HARD_REG_SET temp_hard_regset2;
995 static enum reg_class classes[LIM_REG_CLASSES + 1];
997 n = 0;
998 /* Collect classes which contain unique sets of allocatable hard
999 registers. Prefer GENERAL_REGS to other classes containing the
1000 same set of hard registers. */
1001 for (i = 0; i < LIM_REG_CLASSES; i++)
1003 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
1004 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1005 for (j = 0; j < n; j++)
1007 cl = classes[j];
1008 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
1009 AND_COMPL_HARD_REG_SET (temp_hard_regset2,
1010 no_unit_alloc_regs);
1011 if (hard_reg_set_equal_p (temp_hard_regset,
1012 temp_hard_regset2))
1013 break;
1015 if (j >= n)
1016 classes[n++] = (enum reg_class) i;
1017 else if (i == GENERAL_REGS)
1018 /* Prefer general regs. For i386 example, it means that
1019 we prefer GENERAL_REGS over INDEX_REGS or LEGACY_REGS
1020 (all of them consists of the same available hard
1021 registers). */
1022 classes[j] = (enum reg_class) i;
1024 classes[n] = LIM_REG_CLASSES;
1026 /* Set up classes which can be used for allocnos as classes
1027 containing non-empty unique sets of allocatable hard
1028 registers. */
1029 ira_allocno_classes_num = 0;
1030 for (i = 0; (cl = classes[i]) != LIM_REG_CLASSES; i++)
1031 if (ira_class_hard_regs_num[cl] > 0)
1032 ira_allocno_classes[ira_allocno_classes_num++] = (enum reg_class) cl;
1033 ira_important_classes_num = 0;
1034 /* Add non-allocno classes containing to non-empty set of
1035 allocatable hard regs. */
1036 for (cl = 0; cl < N_REG_CLASSES; cl++)
1037 if (ira_class_hard_regs_num[cl] > 0)
1039 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
1040 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1041 set_p = false;
1042 for (j = 0; j < ira_allocno_classes_num; j++)
1044 COPY_HARD_REG_SET (temp_hard_regset2,
1045 reg_class_contents[ira_allocno_classes[j]]);
1046 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
1047 if ((enum reg_class) cl == ira_allocno_classes[j])
1048 break;
1049 else if (hard_reg_set_subset_p (temp_hard_regset,
1050 temp_hard_regset2))
1051 set_p = true;
1053 if (set_p && j >= ira_allocno_classes_num)
1054 ira_important_classes[ira_important_classes_num++]
1055 = (enum reg_class) cl;
1057 /* Now add allocno classes to the important classes. */
1058 for (j = 0; j < ira_allocno_classes_num; j++)
1059 ira_important_classes[ira_important_classes_num++]
1060 = ira_allocno_classes[j];
1061 for (cl = 0; cl < N_REG_CLASSES; cl++)
1063 ira_reg_allocno_class_p[cl] = false;
1064 ira_reg_pressure_class_p[cl] = false;
1066 for (j = 0; j < ira_allocno_classes_num; j++)
1067 ira_reg_allocno_class_p[ira_allocno_classes[j]] = true;
1068 setup_pressure_classes ();
1069 setup_uniform_class_p ();
1072 /* Setup translation in CLASS_TRANSLATE of all classes into a class
1073 given by array CLASSES of length CLASSES_NUM. The function is used
1074 make translation any reg class to an allocno class or to an
1075 pressure class. This translation is necessary for some
1076 calculations when we can use only allocno or pressure classes and
1077 such translation represents an approximate representation of all
1078 classes.
1080 The translation in case when allocatable hard register set of a
1081 given class is subset of allocatable hard register set of a class
1082 in CLASSES is pretty simple. We use smallest classes from CLASSES
1083 containing a given class. If allocatable hard register set of a
1084 given class is not a subset of any corresponding set of a class
1085 from CLASSES, we use the cheapest (with load/store point of view)
1086 class from CLASSES whose set intersects with given class set. */
1087 static void
1088 setup_class_translate_array (enum reg_class *class_translate,
1089 int classes_num, enum reg_class *classes)
1091 int cl, mode;
1092 enum reg_class aclass, best_class, *cl_ptr;
1093 int i, cost, min_cost, best_cost;
1095 for (cl = 0; cl < N_REG_CLASSES; cl++)
1096 class_translate[cl] = NO_REGS;
1098 for (i = 0; i < classes_num; i++)
1100 aclass = classes[i];
1101 for (cl_ptr = &alloc_reg_class_subclasses[aclass][0];
1102 (cl = *cl_ptr) != LIM_REG_CLASSES;
1103 cl_ptr++)
1104 if (class_translate[cl] == NO_REGS)
1105 class_translate[cl] = aclass;
1106 class_translate[aclass] = aclass;
1108 /* For classes which are not fully covered by one of given classes
1109 (in other words covered by more one given class), use the
1110 cheapest class. */
1111 for (cl = 0; cl < N_REG_CLASSES; cl++)
1113 if (cl == NO_REGS || class_translate[cl] != NO_REGS)
1114 continue;
1115 best_class = NO_REGS;
1116 best_cost = INT_MAX;
1117 for (i = 0; i < classes_num; i++)
1119 aclass = classes[i];
1120 COPY_HARD_REG_SET (temp_hard_regset,
1121 reg_class_contents[aclass]);
1122 AND_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
1123 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1124 if (! hard_reg_set_empty_p (temp_hard_regset))
1126 min_cost = INT_MAX;
1127 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1129 cost = (ira_memory_move_cost[mode][aclass][0]
1130 + ira_memory_move_cost[mode][aclass][1]);
1131 if (min_cost > cost)
1132 min_cost = cost;
1134 if (best_class == NO_REGS || best_cost > min_cost)
1136 best_class = aclass;
1137 best_cost = min_cost;
1141 class_translate[cl] = best_class;
1145 /* Set up array IRA_ALLOCNO_CLASS_TRANSLATE and
1146 IRA_PRESSURE_CLASS_TRANSLATE. */
1147 static void
1148 setup_class_translate (void)
1150 setup_class_translate_array (ira_allocno_class_translate,
1151 ira_allocno_classes_num, ira_allocno_classes);
1152 setup_class_translate_array (ira_pressure_class_translate,
1153 ira_pressure_classes_num, ira_pressure_classes);
1156 /* Order numbers of allocno classes in original target allocno class
1157 array, -1 for non-allocno classes. */
1158 static int allocno_class_order[N_REG_CLASSES];
1160 /* The function used to sort the important classes. */
1161 static int
1162 comp_reg_classes_func (const void *v1p, const void *v2p)
1164 enum reg_class cl1 = *(const enum reg_class *) v1p;
1165 enum reg_class cl2 = *(const enum reg_class *) v2p;
1166 enum reg_class tcl1, tcl2;
1167 int diff;
1169 tcl1 = ira_allocno_class_translate[cl1];
1170 tcl2 = ira_allocno_class_translate[cl2];
1171 if (tcl1 != NO_REGS && tcl2 != NO_REGS
1172 && (diff = allocno_class_order[tcl1] - allocno_class_order[tcl2]) != 0)
1173 return diff;
1174 return (int) cl1 - (int) cl2;
1177 /* For correct work of function setup_reg_class_relation we need to
1178 reorder important classes according to the order of their allocno
1179 classes. It places important classes containing the same
1180 allocatable hard register set adjacent to each other and allocno
1181 class with the allocatable hard register set right after the other
1182 important classes with the same set.
1184 In example from comments of function
1185 setup_allocno_and_important_classes, it places LEGACY_REGS and
1186 GENERAL_REGS close to each other and GENERAL_REGS is after
1187 LEGACY_REGS. */
1188 static void
1189 reorder_important_classes (void)
1191 int i;
1193 for (i = 0; i < N_REG_CLASSES; i++)
1194 allocno_class_order[i] = -1;
1195 for (i = 0; i < ira_allocno_classes_num; i++)
1196 allocno_class_order[ira_allocno_classes[i]] = i;
1197 qsort (ira_important_classes, ira_important_classes_num,
1198 sizeof (enum reg_class), comp_reg_classes_func);
1199 for (i = 0; i < ira_important_classes_num; i++)
1200 ira_important_class_nums[ira_important_classes[i]] = i;
1203 /* Set up IRA_REG_CLASS_SUBUNION, IRA_REG_CLASS_SUPERUNION,
1204 IRA_REG_CLASS_SUPER_CLASSES, IRA_REG_CLASSES_INTERSECT, and
1205 IRA_REG_CLASSES_INTERSECT_P. For the meaning of the relations,
1206 please see corresponding comments in ira-int.h. */
1207 static void
1208 setup_reg_class_relations (void)
1210 int i, cl1, cl2, cl3;
1211 HARD_REG_SET intersection_set, union_set, temp_set2;
1212 bool important_class_p[N_REG_CLASSES];
1214 memset (important_class_p, 0, sizeof (important_class_p));
1215 for (i = 0; i < ira_important_classes_num; i++)
1216 important_class_p[ira_important_classes[i]] = true;
1217 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1219 ira_reg_class_super_classes[cl1][0] = LIM_REG_CLASSES;
1220 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1222 ira_reg_classes_intersect_p[cl1][cl2] = false;
1223 ira_reg_class_intersect[cl1][cl2] = NO_REGS;
1224 ira_reg_class_subset[cl1][cl2] = NO_REGS;
1225 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl1]);
1226 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1227 COPY_HARD_REG_SET (temp_set2, reg_class_contents[cl2]);
1228 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1229 if (hard_reg_set_empty_p (temp_hard_regset)
1230 && hard_reg_set_empty_p (temp_set2))
1232 /* The both classes have no allocatable hard registers
1233 -- take all class hard registers into account and use
1234 reg_class_subunion and reg_class_superunion. */
1235 for (i = 0;; i++)
1237 cl3 = reg_class_subclasses[cl1][i];
1238 if (cl3 == LIM_REG_CLASSES)
1239 break;
1240 if (reg_class_subset_p (ira_reg_class_intersect[cl1][cl2],
1241 (enum reg_class) cl3))
1242 ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
1244 ira_reg_class_subunion[cl1][cl2] = reg_class_subunion[cl1][cl2];
1245 ira_reg_class_superunion[cl1][cl2] = reg_class_superunion[cl1][cl2];
1246 continue;
1248 ira_reg_classes_intersect_p[cl1][cl2]
1249 = hard_reg_set_intersect_p (temp_hard_regset, temp_set2);
1250 if (important_class_p[cl1] && important_class_p[cl2]
1251 && hard_reg_set_subset_p (temp_hard_regset, temp_set2))
1253 /* CL1 and CL2 are important classes and CL1 allocatable
1254 hard register set is inside of CL2 allocatable hard
1255 registers -- make CL1 a superset of CL2. */
1256 enum reg_class *p;
1258 p = &ira_reg_class_super_classes[cl1][0];
1259 while (*p != LIM_REG_CLASSES)
1260 p++;
1261 *p++ = (enum reg_class) cl2;
1262 *p = LIM_REG_CLASSES;
1264 ira_reg_class_subunion[cl1][cl2] = NO_REGS;
1265 ira_reg_class_superunion[cl1][cl2] = NO_REGS;
1266 COPY_HARD_REG_SET (intersection_set, reg_class_contents[cl1]);
1267 AND_HARD_REG_SET (intersection_set, reg_class_contents[cl2]);
1268 AND_COMPL_HARD_REG_SET (intersection_set, no_unit_alloc_regs);
1269 COPY_HARD_REG_SET (union_set, reg_class_contents[cl1]);
1270 IOR_HARD_REG_SET (union_set, reg_class_contents[cl2]);
1271 AND_COMPL_HARD_REG_SET (union_set, no_unit_alloc_regs);
1272 for (cl3 = 0; cl3 < N_REG_CLASSES; cl3++)
1274 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl3]);
1275 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1276 if (hard_reg_set_subset_p (temp_hard_regset, intersection_set))
1278 /* CL3 allocatable hard register set is inside of
1279 intersection of allocatable hard register sets
1280 of CL1 and CL2. */
1281 if (important_class_p[cl3])
1283 COPY_HARD_REG_SET
1284 (temp_set2,
1285 reg_class_contents
1286 [(int) ira_reg_class_intersect[cl1][cl2]]);
1287 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1288 if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1289 /* If the allocatable hard register sets are
1290 the same, prefer GENERAL_REGS or the
1291 smallest class for debugging
1292 purposes. */
1293 || (hard_reg_set_equal_p (temp_hard_regset, temp_set2)
1294 && (cl3 == GENERAL_REGS
1295 || ((ira_reg_class_intersect[cl1][cl2]
1296 != GENERAL_REGS)
1297 && hard_reg_set_subset_p
1298 (reg_class_contents[cl3],
1299 reg_class_contents
1300 [(int)
1301 ira_reg_class_intersect[cl1][cl2]])))))
1302 ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
1304 COPY_HARD_REG_SET
1305 (temp_set2,
1306 reg_class_contents[(int) ira_reg_class_subset[cl1][cl2]]);
1307 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1308 if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1309 /* Ignore unavailable hard registers and prefer
1310 smallest class for debugging purposes. */
1311 || (hard_reg_set_equal_p (temp_hard_regset, temp_set2)
1312 && hard_reg_set_subset_p
1313 (reg_class_contents[cl3],
1314 reg_class_contents
1315 [(int) ira_reg_class_subset[cl1][cl2]])))
1316 ira_reg_class_subset[cl1][cl2] = (enum reg_class) cl3;
1318 if (important_class_p[cl3]
1319 && hard_reg_set_subset_p (temp_hard_regset, union_set))
1321 /* CL3 allocatable hard register set is inside of
1322 union of allocatable hard register sets of CL1
1323 and CL2. */
1324 COPY_HARD_REG_SET
1325 (temp_set2,
1326 reg_class_contents[(int) ira_reg_class_subunion[cl1][cl2]]);
1327 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1328 if (ira_reg_class_subunion[cl1][cl2] == NO_REGS
1329 || (hard_reg_set_subset_p (temp_set2, temp_hard_regset)
1331 && (! hard_reg_set_equal_p (temp_set2,
1332 temp_hard_regset)
1333 || cl3 == GENERAL_REGS
1334 /* If the allocatable hard register sets are the
1335 same, prefer GENERAL_REGS or the smallest
1336 class for debugging purposes. */
1337 || (ira_reg_class_subunion[cl1][cl2] != GENERAL_REGS
1338 && hard_reg_set_subset_p
1339 (reg_class_contents[cl3],
1340 reg_class_contents
1341 [(int) ira_reg_class_subunion[cl1][cl2]])))))
1342 ira_reg_class_subunion[cl1][cl2] = (enum reg_class) cl3;
1344 if (hard_reg_set_subset_p (union_set, temp_hard_regset))
1346 /* CL3 allocatable hard register set contains union
1347 of allocatable hard register sets of CL1 and
1348 CL2. */
1349 COPY_HARD_REG_SET
1350 (temp_set2,
1351 reg_class_contents[(int) ira_reg_class_superunion[cl1][cl2]]);
1352 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1353 if (ira_reg_class_superunion[cl1][cl2] == NO_REGS
1354 || (hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1356 && (! hard_reg_set_equal_p (temp_set2,
1357 temp_hard_regset)
1358 || cl3 == GENERAL_REGS
1359 /* If the allocatable hard register sets are the
1360 same, prefer GENERAL_REGS or the smallest
1361 class for debugging purposes. */
1362 || (ira_reg_class_superunion[cl1][cl2] != GENERAL_REGS
1363 && hard_reg_set_subset_p
1364 (reg_class_contents[cl3],
1365 reg_class_contents
1366 [(int) ira_reg_class_superunion[cl1][cl2]])))))
1367 ira_reg_class_superunion[cl1][cl2] = (enum reg_class) cl3;
1374 /* Output all uniform and important classes into file F. */
1375 static void
1376 print_unform_and_important_classes (FILE *f)
1378 static const char *const reg_class_names[] = REG_CLASS_NAMES;
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 static const char *const reg_class_names[] = REG_CLASS_NAMES;
1404 int i;
1406 fprintf (f, "%s classes:\n", pressure_p ? "Pressure" : "Allocno");
1407 for (i = 0; i < classes_num; i++)
1408 fprintf (f, " %s", reg_class_names[classes[i]]);
1409 fprintf (f, "\nClass translation:\n");
1410 for (i = 0; i < N_REG_CLASSES; i++)
1411 fprintf (f, " %s -> %s\n", reg_class_names[i],
1412 reg_class_names[class_translate[i]]);
1415 /* Output all possible allocno and translation classes and the
1416 translation maps into stderr. */
1417 void
1418 ira_debug_allocno_classes (void)
1420 print_unform_and_important_classes (stderr);
1421 print_translated_classes (stderr, false);
1422 print_translated_classes (stderr, true);
1425 /* Set up different arrays concerning class subsets, allocno and
1426 important classes. */
1427 static void
1428 find_reg_classes (void)
1430 setup_allocno_and_important_classes ();
1431 setup_class_translate ();
1432 reorder_important_classes ();
1433 setup_reg_class_relations ();
1438 /* Set up the array above. */
1439 static void
1440 setup_hard_regno_aclass (void)
1442 int i;
1444 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1446 #if 1
1447 ira_hard_regno_allocno_class[i]
1448 = (TEST_HARD_REG_BIT (no_unit_alloc_regs, i)
1449 ? NO_REGS
1450 : ira_allocno_class_translate[REGNO_REG_CLASS (i)]);
1451 #else
1452 int j;
1453 enum reg_class cl;
1454 ira_hard_regno_allocno_class[i] = NO_REGS;
1455 for (j = 0; j < ira_allocno_classes_num; j++)
1457 cl = ira_allocno_classes[j];
1458 if (ira_class_hard_reg_index[cl][i] >= 0)
1460 ira_hard_regno_allocno_class[i] = cl;
1461 break;
1464 #endif
1470 /* Form IRA_REG_CLASS_MAX_NREGS and IRA_REG_CLASS_MIN_NREGS maps. */
1471 static void
1472 setup_reg_class_nregs (void)
1474 int i, cl, cl2, m;
1476 for (m = 0; m < MAX_MACHINE_MODE; m++)
1478 for (cl = 0; cl < N_REG_CLASSES; cl++)
1479 ira_reg_class_max_nregs[cl][m]
1480 = ira_reg_class_min_nregs[cl][m]
1481 = targetm.class_max_nregs ((reg_class_t) cl, (enum machine_mode) m);
1482 for (cl = 0; cl < N_REG_CLASSES; cl++)
1483 for (i = 0;
1484 (cl2 = alloc_reg_class_subclasses[cl][i]) != LIM_REG_CLASSES;
1485 i++)
1486 if (ira_reg_class_min_nregs[cl2][m]
1487 < ira_reg_class_min_nregs[cl][m])
1488 ira_reg_class_min_nregs[cl][m] = ira_reg_class_min_nregs[cl2][m];
1494 /* Set up IRA_PROHIBITED_CLASS_MODE_REGS and IRA_CLASS_SINGLETON.
1495 This function is called once IRA_CLASS_HARD_REGS has been initialized. */
1496 static void
1497 setup_prohibited_class_mode_regs (void)
1499 int j, k, hard_regno, cl, last_hard_regno, count;
1501 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
1503 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
1504 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1505 for (j = 0; j < NUM_MACHINE_MODES; j++)
1507 count = 0;
1508 last_hard_regno = -1;
1509 CLEAR_HARD_REG_SET (ira_prohibited_class_mode_regs[cl][j]);
1510 for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1512 hard_regno = ira_class_hard_regs[cl][k];
1513 if (! HARD_REGNO_MODE_OK (hard_regno, (enum machine_mode) j))
1514 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1515 hard_regno);
1516 else if (in_hard_reg_set_p (temp_hard_regset,
1517 (enum machine_mode) j, hard_regno))
1519 last_hard_regno = hard_regno;
1520 count++;
1523 ira_class_singleton[cl][j] = (count == 1 ? last_hard_regno : -1);
1528 /* Clarify IRA_PROHIBITED_CLASS_MODE_REGS by excluding hard registers
1529 spanning from one register pressure class to another one. It is
1530 called after defining the pressure classes. */
1531 static void
1532 clarify_prohibited_class_mode_regs (void)
1534 int j, k, hard_regno, cl, pclass, nregs;
1536 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
1537 for (j = 0; j < NUM_MACHINE_MODES; j++)
1539 CLEAR_HARD_REG_SET (ira_useful_class_mode_regs[cl][j]);
1540 for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1542 hard_regno = ira_class_hard_regs[cl][k];
1543 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j], hard_regno))
1544 continue;
1545 nregs = hard_regno_nregs[hard_regno][j];
1546 if (hard_regno + nregs > FIRST_PSEUDO_REGISTER)
1548 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1549 hard_regno);
1550 continue;
1552 pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)];
1553 for (nregs-- ;nregs >= 0; nregs--)
1554 if (((enum reg_class) pclass
1555 != ira_pressure_class_translate[REGNO_REG_CLASS
1556 (hard_regno + nregs)]))
1558 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1559 hard_regno);
1560 break;
1562 if (!TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1563 hard_regno))
1564 add_to_hard_reg_set (&ira_useful_class_mode_regs[cl][j],
1565 (enum machine_mode) j, hard_regno);
1570 /* Allocate and initialize IRA_REGISTER_MOVE_COST, IRA_MAY_MOVE_IN_COST
1571 and IRA_MAY_MOVE_OUT_COST for MODE. */
1572 void
1573 ira_init_register_move_cost (enum machine_mode mode)
1575 static unsigned short last_move_cost[N_REG_CLASSES][N_REG_CLASSES];
1576 bool all_match = true;
1577 unsigned int cl1, cl2;
1579 ira_assert (ira_register_move_cost[mode] == NULL
1580 && ira_may_move_in_cost[mode] == NULL
1581 && ira_may_move_out_cost[mode] == NULL);
1582 ira_assert (have_regs_of_mode[mode]);
1583 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1584 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1586 int cost;
1587 if (!contains_reg_of_mode[cl1][mode]
1588 || !contains_reg_of_mode[cl2][mode])
1590 if ((ira_reg_class_max_nregs[cl1][mode]
1591 > ira_class_hard_regs_num[cl1])
1592 || (ira_reg_class_max_nregs[cl2][mode]
1593 > ira_class_hard_regs_num[cl2]))
1594 cost = 65535;
1595 else
1596 cost = (ira_memory_move_cost[mode][cl1][0]
1597 + ira_memory_move_cost[mode][cl2][1]) * 2;
1599 else
1601 cost = register_move_cost (mode, (enum reg_class) cl1,
1602 (enum reg_class) cl2);
1603 ira_assert (cost < 65535);
1605 all_match &= (last_move_cost[cl1][cl2] == cost);
1606 last_move_cost[cl1][cl2] = cost;
1608 if (all_match && last_mode_for_init_move_cost != -1)
1610 ira_register_move_cost[mode]
1611 = ira_register_move_cost[last_mode_for_init_move_cost];
1612 ira_may_move_in_cost[mode]
1613 = ira_may_move_in_cost[last_mode_for_init_move_cost];
1614 ira_may_move_out_cost[mode]
1615 = ira_may_move_out_cost[last_mode_for_init_move_cost];
1616 return;
1618 last_mode_for_init_move_cost = mode;
1619 ira_register_move_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1620 ira_may_move_in_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1621 ira_may_move_out_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1622 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1623 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1625 int cost;
1626 enum reg_class *p1, *p2;
1628 if (last_move_cost[cl1][cl2] == 65535)
1630 ira_register_move_cost[mode][cl1][cl2] = 65535;
1631 ira_may_move_in_cost[mode][cl1][cl2] = 65535;
1632 ira_may_move_out_cost[mode][cl1][cl2] = 65535;
1634 else
1636 cost = last_move_cost[cl1][cl2];
1638 for (p2 = &reg_class_subclasses[cl2][0];
1639 *p2 != LIM_REG_CLASSES; p2++)
1640 if (ira_class_hard_regs_num[*p2] > 0
1641 && (ira_reg_class_max_nregs[*p2][mode]
1642 <= ira_class_hard_regs_num[*p2]))
1643 cost = MAX (cost, ira_register_move_cost[mode][cl1][*p2]);
1645 for (p1 = &reg_class_subclasses[cl1][0];
1646 *p1 != LIM_REG_CLASSES; p1++)
1647 if (ira_class_hard_regs_num[*p1] > 0
1648 && (ira_reg_class_max_nregs[*p1][mode]
1649 <= ira_class_hard_regs_num[*p1]))
1650 cost = MAX (cost, ira_register_move_cost[mode][*p1][cl2]);
1652 ira_assert (cost <= 65535);
1653 ira_register_move_cost[mode][cl1][cl2] = cost;
1655 if (ira_class_subset_p[cl1][cl2])
1656 ira_may_move_in_cost[mode][cl1][cl2] = 0;
1657 else
1658 ira_may_move_in_cost[mode][cl1][cl2] = cost;
1660 if (ira_class_subset_p[cl2][cl1])
1661 ira_may_move_out_cost[mode][cl1][cl2] = 0;
1662 else
1663 ira_may_move_out_cost[mode][cl1][cl2] = cost;
1670 /* This is called once during compiler work. It sets up
1671 different arrays whose values don't depend on the compiled
1672 function. */
1673 void
1674 ira_init_once (void)
1676 ira_init_costs_once ();
1677 lra_init_once ();
1680 /* Free ira_max_register_move_cost, ira_may_move_in_cost and
1681 ira_may_move_out_cost for each mode. */
1682 void
1683 target_ira_int::free_register_move_costs (void)
1685 int mode, i;
1687 /* Reset move_cost and friends, making sure we only free shared
1688 table entries once. */
1689 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1690 if (x_ira_register_move_cost[mode])
1692 for (i = 0;
1693 i < mode && (x_ira_register_move_cost[i]
1694 != x_ira_register_move_cost[mode]);
1695 i++)
1697 if (i == mode)
1699 free (x_ira_register_move_cost[mode]);
1700 free (x_ira_may_move_in_cost[mode]);
1701 free (x_ira_may_move_out_cost[mode]);
1704 memset (x_ira_register_move_cost, 0, sizeof x_ira_register_move_cost);
1705 memset (x_ira_may_move_in_cost, 0, sizeof x_ira_may_move_in_cost);
1706 memset (x_ira_may_move_out_cost, 0, sizeof x_ira_may_move_out_cost);
1707 last_mode_for_init_move_cost = -1;
1710 target_ira_int::~target_ira_int ()
1712 free_ira_costs ();
1713 free_register_move_costs ();
1716 /* This is called every time when register related information is
1717 changed. */
1718 void
1719 ira_init (void)
1721 this_target_ira_int->free_register_move_costs ();
1722 setup_reg_mode_hard_regset ();
1723 setup_alloc_regs (flag_omit_frame_pointer != 0);
1724 setup_class_subset_and_memory_move_costs ();
1725 setup_reg_class_nregs ();
1726 setup_prohibited_class_mode_regs ();
1727 find_reg_classes ();
1728 clarify_prohibited_class_mode_regs ();
1729 setup_hard_regno_aclass ();
1730 ira_init_costs ();
1734 #define ira_prohibited_mode_move_regs_initialized_p \
1735 (this_target_ira_int->x_ira_prohibited_mode_move_regs_initialized_p)
1737 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS. */
1738 static void
1739 setup_prohibited_mode_move_regs (void)
1741 int i, j;
1742 rtx test_reg1, test_reg2, move_pat;
1743 rtx_insn *move_insn;
1745 if (ira_prohibited_mode_move_regs_initialized_p)
1746 return;
1747 ira_prohibited_mode_move_regs_initialized_p = true;
1748 test_reg1 = gen_rtx_REG (VOIDmode, 0);
1749 test_reg2 = gen_rtx_REG (VOIDmode, 0);
1750 move_pat = gen_rtx_SET (VOIDmode, test_reg1, test_reg2);
1751 move_insn = gen_rtx_INSN (VOIDmode, 0, 0, 0, move_pat, 0, -1, 0);
1752 for (i = 0; i < NUM_MACHINE_MODES; i++)
1754 SET_HARD_REG_SET (ira_prohibited_mode_move_regs[i]);
1755 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1757 if (! HARD_REGNO_MODE_OK (j, (enum machine_mode) i))
1758 continue;
1759 SET_REGNO_RAW (test_reg1, j);
1760 PUT_MODE (test_reg1, (enum machine_mode) i);
1761 SET_REGNO_RAW (test_reg2, j);
1762 PUT_MODE (test_reg2, (enum machine_mode) i);
1763 INSN_CODE (move_insn) = -1;
1764 recog_memoized (move_insn);
1765 if (INSN_CODE (move_insn) < 0)
1766 continue;
1767 extract_insn (move_insn);
1768 /* We don't know whether the move will be in code that is optimized
1769 for size or speed, so consider all enabled alternatives. */
1770 if (! constrain_operands (1, get_enabled_alternatives (move_insn)))
1771 continue;
1772 CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs[i], j);
1779 /* Setup possible alternatives in ALTS for INSN. */
1780 void
1781 ira_setup_alts (rtx_insn *insn, HARD_REG_SET &alts)
1783 /* MAP nalt * nop -> start of constraints for given operand and
1784 alternative. */
1785 static vec<const char *> insn_constraints;
1786 int nop, nalt;
1787 bool curr_swapped;
1788 const char *p;
1789 rtx op;
1790 int commutative = -1;
1792 extract_insn (insn);
1793 alternative_mask preferred = get_preferred_alternatives (insn);
1794 CLEAR_HARD_REG_SET (alts);
1795 insn_constraints.release ();
1796 insn_constraints.safe_grow_cleared (recog_data.n_operands
1797 * recog_data.n_alternatives + 1);
1798 /* Check that the hard reg set is enough for holding all
1799 alternatives. It is hard to imagine the situation when the
1800 assertion is wrong. */
1801 ira_assert (recog_data.n_alternatives
1802 <= (int) MAX (sizeof (HARD_REG_ELT_TYPE) * CHAR_BIT,
1803 FIRST_PSEUDO_REGISTER));
1804 for (curr_swapped = false;; curr_swapped = true)
1806 /* Calculate some data common for all alternatives to speed up the
1807 function. */
1808 for (nop = 0; nop < recog_data.n_operands; nop++)
1810 for (nalt = 0, p = recog_data.constraints[nop];
1811 nalt < recog_data.n_alternatives;
1812 nalt++)
1814 insn_constraints[nop * recog_data.n_alternatives + nalt] = p;
1815 while (*p && *p != ',')
1816 p++;
1817 if (*p)
1818 p++;
1821 for (nalt = 0; nalt < recog_data.n_alternatives; nalt++)
1823 if (!TEST_BIT (preferred, nalt)
1824 || TEST_HARD_REG_BIT (alts, nalt))
1825 continue;
1827 for (nop = 0; nop < recog_data.n_operands; nop++)
1829 int c, len;
1831 op = recog_data.operand[nop];
1832 p = insn_constraints[nop * recog_data.n_alternatives + nalt];
1833 if (*p == 0 || *p == ',')
1834 continue;
1837 switch (c = *p, len = CONSTRAINT_LEN (c, p), c)
1839 case '#':
1840 case ',':
1841 c = '\0';
1842 case '\0':
1843 len = 0;
1844 break;
1846 case '%':
1847 /* We only support one commutative marker, the
1848 first one. We already set commutative
1849 above. */
1850 if (commutative < 0)
1851 commutative = nop;
1852 break;
1854 case '0': case '1': case '2': case '3': case '4':
1855 case '5': case '6': case '7': case '8': case '9':
1856 goto op_success;
1857 break;
1859 case 'g':
1860 goto op_success;
1861 break;
1863 default:
1865 enum constraint_num cn = lookup_constraint (p);
1866 switch (get_constraint_type (cn))
1868 case CT_REGISTER:
1869 if (reg_class_for_constraint (cn) != NO_REGS)
1870 goto op_success;
1871 break;
1873 case CT_CONST_INT:
1874 if (CONST_INT_P (op)
1875 && (insn_const_int_ok_for_constraint
1876 (INTVAL (op), cn)))
1877 goto op_success;
1878 break;
1880 case CT_ADDRESS:
1881 case CT_MEMORY:
1882 goto op_success;
1884 case CT_FIXED_FORM:
1885 if (constraint_satisfied_p (op, cn))
1886 goto op_success;
1887 break;
1889 break;
1892 while (p += len, c);
1893 break;
1894 op_success:
1897 if (nop >= recog_data.n_operands)
1898 SET_HARD_REG_BIT (alts, nalt);
1900 if (commutative < 0)
1901 break;
1902 if (curr_swapped)
1903 break;
1904 op = recog_data.operand[commutative];
1905 recog_data.operand[commutative] = recog_data.operand[commutative + 1];
1906 recog_data.operand[commutative + 1] = op;
1911 /* Return the number of the output non-early clobber operand which
1912 should be the same in any case as operand with number OP_NUM (or
1913 negative value if there is no such operand). The function takes
1914 only really possible alternatives into consideration. */
1916 ira_get_dup_out_num (int op_num, HARD_REG_SET &alts)
1918 int curr_alt, c, original, dup;
1919 bool ignore_p, use_commut_op_p;
1920 const char *str;
1922 if (op_num < 0 || recog_data.n_alternatives == 0)
1923 return -1;
1924 /* We should find duplications only for input operands. */
1925 if (recog_data.operand_type[op_num] != OP_IN)
1926 return -1;
1927 str = recog_data.constraints[op_num];
1928 use_commut_op_p = false;
1929 for (;;)
1931 rtx op = recog_data.operand[op_num];
1933 for (curr_alt = 0, ignore_p = !TEST_HARD_REG_BIT (alts, curr_alt),
1934 original = -1;;)
1936 c = *str;
1937 if (c == '\0')
1938 break;
1939 if (c == '#')
1940 ignore_p = true;
1941 else if (c == ',')
1943 curr_alt++;
1944 ignore_p = !TEST_HARD_REG_BIT (alts, curr_alt);
1946 else if (! ignore_p)
1947 switch (c)
1949 case 'g':
1950 goto fail;
1951 default:
1953 enum constraint_num cn = lookup_constraint (str);
1954 enum reg_class cl = reg_class_for_constraint (cn);
1955 if (cl != NO_REGS
1956 && !targetm.class_likely_spilled_p (cl))
1957 goto fail;
1958 if (constraint_satisfied_p (op, cn))
1959 goto fail;
1960 break;
1963 case '0': case '1': case '2': case '3': case '4':
1964 case '5': case '6': case '7': case '8': case '9':
1965 if (original != -1 && original != c)
1966 goto fail;
1967 original = c;
1968 break;
1970 str += CONSTRAINT_LEN (c, str);
1972 if (original == -1)
1973 goto fail;
1974 dup = -1;
1975 for (ignore_p = false, str = recog_data.constraints[original - '0'];
1976 *str != 0;
1977 str++)
1978 if (ignore_p)
1980 if (*str == ',')
1981 ignore_p = false;
1983 else if (*str == '#')
1984 ignore_p = true;
1985 else if (! ignore_p)
1987 if (*str == '=')
1988 dup = original - '0';
1989 /* It is better ignore an alternative with early clobber. */
1990 else if (*str == '&')
1991 goto fail;
1993 if (dup >= 0)
1994 return dup;
1995 fail:
1996 if (use_commut_op_p)
1997 break;
1998 use_commut_op_p = true;
1999 if (recog_data.constraints[op_num][0] == '%')
2000 str = recog_data.constraints[op_num + 1];
2001 else if (op_num > 0 && recog_data.constraints[op_num - 1][0] == '%')
2002 str = recog_data.constraints[op_num - 1];
2003 else
2004 break;
2006 return -1;
2011 /* Search forward to see if the source register of a copy insn dies
2012 before either it or the destination register is modified, but don't
2013 scan past the end of the basic block. If so, we can replace the
2014 source with the destination and let the source die in the copy
2015 insn.
2017 This will reduce the number of registers live in that range and may
2018 enable the destination and the source coalescing, thus often saving
2019 one register in addition to a register-register copy. */
2021 static void
2022 decrease_live_ranges_number (void)
2024 basic_block bb;
2025 rtx_insn *insn;
2026 rtx set, src, dest, dest_death, q, note;
2027 rtx_insn *p;
2028 int sregno, dregno;
2030 if (! flag_expensive_optimizations)
2031 return;
2033 if (ira_dump_file)
2034 fprintf (ira_dump_file, "Starting decreasing number of live ranges...\n");
2036 FOR_EACH_BB_FN (bb, cfun)
2037 FOR_BB_INSNS (bb, insn)
2039 set = single_set (insn);
2040 if (! set)
2041 continue;
2042 src = SET_SRC (set);
2043 dest = SET_DEST (set);
2044 if (! REG_P (src) || ! REG_P (dest)
2045 || find_reg_note (insn, REG_DEAD, src))
2046 continue;
2047 sregno = REGNO (src);
2048 dregno = REGNO (dest);
2050 /* We don't want to mess with hard regs if register classes
2051 are small. */
2052 if (sregno == dregno
2053 || (targetm.small_register_classes_for_mode_p (GET_MODE (src))
2054 && (sregno < FIRST_PSEUDO_REGISTER
2055 || dregno < FIRST_PSEUDO_REGISTER))
2056 /* We don't see all updates to SP if they are in an
2057 auto-inc memory reference, so we must disallow this
2058 optimization on them. */
2059 || sregno == STACK_POINTER_REGNUM
2060 || dregno == STACK_POINTER_REGNUM)
2061 continue;
2063 dest_death = NULL_RTX;
2065 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
2067 if (! INSN_P (p))
2068 continue;
2069 if (BLOCK_FOR_INSN (p) != bb)
2070 break;
2072 if (reg_set_p (src, p) || reg_set_p (dest, p)
2073 /* If SRC is an asm-declared register, it must not be
2074 replaced in any asm. Unfortunately, the REG_EXPR
2075 tree for the asm variable may be absent in the SRC
2076 rtx, so we can't check the actual register
2077 declaration easily (the asm operand will have it,
2078 though). To avoid complicating the test for a rare
2079 case, we just don't perform register replacement
2080 for a hard reg mentioned in an asm. */
2081 || (sregno < FIRST_PSEUDO_REGISTER
2082 && asm_noperands (PATTERN (p)) >= 0
2083 && reg_overlap_mentioned_p (src, PATTERN (p)))
2084 /* Don't change hard registers used by a call. */
2085 || (CALL_P (p) && sregno < FIRST_PSEUDO_REGISTER
2086 && find_reg_fusage (p, USE, src))
2087 /* Don't change a USE of a register. */
2088 || (GET_CODE (PATTERN (p)) == USE
2089 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
2090 break;
2092 /* See if all of SRC dies in P. This test is slightly
2093 more conservative than it needs to be. */
2094 if ((note = find_regno_note (p, REG_DEAD, sregno))
2095 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
2097 int failed = 0;
2099 /* We can do the optimization. Scan forward from INSN
2100 again, replacing regs as we go. Set FAILED if a
2101 replacement can't be done. In that case, we can't
2102 move the death note for SRC. This should be
2103 rare. */
2105 /* Set to stop at next insn. */
2106 for (q = next_real_insn (insn);
2107 q != next_real_insn (p);
2108 q = next_real_insn (q))
2110 if (reg_overlap_mentioned_p (src, PATTERN (q)))
2112 /* If SRC is a hard register, we might miss
2113 some overlapping registers with
2114 validate_replace_rtx, so we would have to
2115 undo it. We can't if DEST is present in
2116 the insn, so fail in that combination of
2117 cases. */
2118 if (sregno < FIRST_PSEUDO_REGISTER
2119 && reg_mentioned_p (dest, PATTERN (q)))
2120 failed = 1;
2122 /* Attempt to replace all uses. */
2123 else if (!validate_replace_rtx (src, dest, q))
2124 failed = 1;
2126 /* If this succeeded, but some part of the
2127 register is still present, undo the
2128 replacement. */
2129 else if (sregno < FIRST_PSEUDO_REGISTER
2130 && reg_overlap_mentioned_p (src, PATTERN (q)))
2132 validate_replace_rtx (dest, src, q);
2133 failed = 1;
2137 /* If DEST dies here, remove the death note and
2138 save it for later. Make sure ALL of DEST dies
2139 here; again, this is overly conservative. */
2140 if (! dest_death
2141 && (dest_death = find_regno_note (q, REG_DEAD, dregno)))
2143 if (GET_MODE (XEXP (dest_death, 0)) == GET_MODE (dest))
2144 remove_note (q, dest_death);
2145 else
2147 failed = 1;
2148 dest_death = 0;
2153 if (! failed)
2155 /* Move death note of SRC from P to INSN. */
2156 remove_note (p, note);
2157 XEXP (note, 1) = REG_NOTES (insn);
2158 REG_NOTES (insn) = note;
2161 /* DEST is also dead if INSN has a REG_UNUSED note for
2162 DEST. */
2163 if (! dest_death
2164 && (dest_death
2165 = find_regno_note (insn, REG_UNUSED, dregno)))
2167 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
2168 remove_note (insn, dest_death);
2171 /* Put death note of DEST on P if we saw it die. */
2172 if (dest_death)
2174 XEXP (dest_death, 1) = REG_NOTES (p);
2175 REG_NOTES (p) = dest_death;
2177 break;
2180 /* If SRC is a hard register which is set or killed in
2181 some other way, we can't do this optimization. */
2182 else if (sregno < FIRST_PSEUDO_REGISTER && dead_or_set_p (p, src))
2183 break;
2190 /* Return nonzero if REGNO is a particularly bad choice for reloading X. */
2191 static bool
2192 ira_bad_reload_regno_1 (int regno, rtx x)
2194 int x_regno, n, i;
2195 ira_allocno_t a;
2196 enum reg_class pref;
2198 /* We only deal with pseudo regs. */
2199 if (! x || GET_CODE (x) != REG)
2200 return false;
2202 x_regno = REGNO (x);
2203 if (x_regno < FIRST_PSEUDO_REGISTER)
2204 return false;
2206 /* If the pseudo prefers REGNO explicitly, then do not consider
2207 REGNO a bad spill choice. */
2208 pref = reg_preferred_class (x_regno);
2209 if (reg_class_size[pref] == 1)
2210 return !TEST_HARD_REG_BIT (reg_class_contents[pref], regno);
2212 /* If the pseudo conflicts with REGNO, then we consider REGNO a
2213 poor choice for a reload regno. */
2214 a = ira_regno_allocno_map[x_regno];
2215 n = ALLOCNO_NUM_OBJECTS (a);
2216 for (i = 0; i < n; i++)
2218 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2219 if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), regno))
2220 return true;
2222 return false;
2225 /* Return nonzero if REGNO is a particularly bad choice for reloading
2226 IN or OUT. */
2227 bool
2228 ira_bad_reload_regno (int regno, rtx in, rtx out)
2230 return (ira_bad_reload_regno_1 (regno, in)
2231 || ira_bad_reload_regno_1 (regno, out));
2234 /* Add register clobbers from asm statements. */
2235 static void
2236 compute_regs_asm_clobbered (void)
2238 basic_block bb;
2240 FOR_EACH_BB_FN (bb, cfun)
2242 rtx_insn *insn;
2243 FOR_BB_INSNS_REVERSE (bb, insn)
2245 df_ref def;
2247 if (NONDEBUG_INSN_P (insn) && extract_asm_operands (PATTERN (insn)))
2248 FOR_EACH_INSN_DEF (def, insn)
2250 unsigned int dregno = DF_REF_REGNO (def);
2251 if (HARD_REGISTER_NUM_P (dregno))
2252 add_to_hard_reg_set (&crtl->asm_clobbers,
2253 GET_MODE (DF_REF_REAL_REG (def)),
2254 dregno);
2261 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and
2262 REGS_EVER_LIVE. */
2263 void
2264 ira_setup_eliminable_regset (void)
2266 #ifdef ELIMINABLE_REGS
2267 int i;
2268 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
2269 #endif
2270 /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
2271 sp for alloca. So we can't eliminate the frame pointer in that
2272 case. At some point, we should improve this by emitting the
2273 sp-adjusting insns for this case. */
2274 frame_pointer_needed
2275 = (! flag_omit_frame_pointer
2276 || (cfun->calls_alloca && EXIT_IGNORE_STACK)
2277 /* We need the frame pointer to catch stack overflow exceptions
2278 if the stack pointer is moving. */
2279 || (flag_stack_check && STACK_CHECK_MOVING_SP)
2280 || crtl->accesses_prior_frames
2281 || (SUPPORTS_STACK_ALIGNMENT && crtl->stack_realign_needed)
2282 /* We need a frame pointer for all Cilk Plus functions that use
2283 Cilk keywords. */
2284 || (flag_cilkplus && cfun->is_cilk_function)
2285 || targetm.frame_pointer_required ());
2287 /* The chance that FRAME_POINTER_NEEDED is changed from inspecting
2288 RTL is very small. So if we use frame pointer for RA and RTL
2289 actually prevents this, we will spill pseudos assigned to the
2290 frame pointer in LRA. */
2292 if (frame_pointer_needed)
2293 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
2295 COPY_HARD_REG_SET (ira_no_alloc_regs, no_unit_alloc_regs);
2296 CLEAR_HARD_REG_SET (eliminable_regset);
2298 compute_regs_asm_clobbered ();
2300 /* Build the regset of all eliminable registers and show we can't
2301 use those that we already know won't be eliminated. */
2302 #ifdef ELIMINABLE_REGS
2303 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
2305 bool cannot_elim
2306 = (! targetm.can_eliminate (eliminables[i].from, eliminables[i].to)
2307 || (eliminables[i].to == STACK_POINTER_REGNUM && frame_pointer_needed));
2309 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, eliminables[i].from))
2311 SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
2313 if (cannot_elim)
2314 SET_HARD_REG_BIT (ira_no_alloc_regs, eliminables[i].from);
2316 else if (cannot_elim)
2317 error ("%s cannot be used in asm here",
2318 reg_names[eliminables[i].from]);
2319 else
2320 df_set_regs_ever_live (eliminables[i].from, true);
2322 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
2323 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM))
2325 SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
2326 if (frame_pointer_needed)
2327 SET_HARD_REG_BIT (ira_no_alloc_regs, HARD_FRAME_POINTER_REGNUM);
2329 else if (frame_pointer_needed)
2330 error ("%s cannot be used in asm here",
2331 reg_names[HARD_FRAME_POINTER_REGNUM]);
2332 else
2333 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
2334 #endif
2336 #else
2337 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM))
2339 SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
2340 if (frame_pointer_needed)
2341 SET_HARD_REG_BIT (ira_no_alloc_regs, FRAME_POINTER_REGNUM);
2343 else if (frame_pointer_needed)
2344 error ("%s cannot be used in asm here", reg_names[FRAME_POINTER_REGNUM]);
2345 else
2346 df_set_regs_ever_live (FRAME_POINTER_REGNUM, true);
2347 #endif
2352 /* Vector of substitutions of register numbers,
2353 used to map pseudo regs into hardware regs.
2354 This is set up as a result of register allocation.
2355 Element N is the hard reg assigned to pseudo reg N,
2356 or is -1 if no hard reg was assigned.
2357 If N is a hard reg number, element N is N. */
2358 short *reg_renumber;
2360 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
2361 the allocation found by IRA. */
2362 static void
2363 setup_reg_renumber (void)
2365 int regno, hard_regno;
2366 ira_allocno_t a;
2367 ira_allocno_iterator ai;
2369 caller_save_needed = 0;
2370 FOR_EACH_ALLOCNO (a, ai)
2372 if (ira_use_lra_p && ALLOCNO_CAP_MEMBER (a) != NULL)
2373 continue;
2374 /* There are no caps at this point. */
2375 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2376 if (! ALLOCNO_ASSIGNED_P (a))
2377 /* It can happen if A is not referenced but partially anticipated
2378 somewhere in a region. */
2379 ALLOCNO_ASSIGNED_P (a) = true;
2380 ira_free_allocno_updated_costs (a);
2381 hard_regno = ALLOCNO_HARD_REGNO (a);
2382 regno = ALLOCNO_REGNO (a);
2383 reg_renumber[regno] = (hard_regno < 0 ? -1 : hard_regno);
2384 if (hard_regno >= 0)
2386 int i, nwords;
2387 enum reg_class pclass;
2388 ira_object_t obj;
2390 pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)];
2391 nwords = ALLOCNO_NUM_OBJECTS (a);
2392 for (i = 0; i < nwords; i++)
2394 obj = ALLOCNO_OBJECT (a, i);
2395 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
2396 reg_class_contents[pclass]);
2398 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
2399 && ira_hard_reg_set_intersection_p (hard_regno, ALLOCNO_MODE (a),
2400 call_used_reg_set))
2402 ira_assert (!optimize || flag_caller_saves
2403 || (ALLOCNO_CALLS_CROSSED_NUM (a)
2404 == ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a))
2405 || regno >= ira_reg_equiv_len
2406 || ira_equiv_no_lvalue_p (regno));
2407 caller_save_needed = 1;
2413 /* Set up allocno assignment flags for further allocation
2414 improvements. */
2415 static void
2416 setup_allocno_assignment_flags (void)
2418 int hard_regno;
2419 ira_allocno_t a;
2420 ira_allocno_iterator ai;
2422 FOR_EACH_ALLOCNO (a, ai)
2424 if (! ALLOCNO_ASSIGNED_P (a))
2425 /* It can happen if A is not referenced but partially anticipated
2426 somewhere in a region. */
2427 ira_free_allocno_updated_costs (a);
2428 hard_regno = ALLOCNO_HARD_REGNO (a);
2429 /* Don't assign hard registers to allocnos which are destination
2430 of removed store at the end of loop. It has no sense to keep
2431 the same value in different hard registers. It is also
2432 impossible to assign hard registers correctly to such
2433 allocnos because the cost info and info about intersected
2434 calls are incorrect for them. */
2435 ALLOCNO_ASSIGNED_P (a) = (hard_regno >= 0
2436 || ALLOCNO_EMIT_DATA (a)->mem_optimized_dest_p
2437 || (ALLOCNO_MEMORY_COST (a)
2438 - ALLOCNO_CLASS_COST (a)) < 0);
2439 ira_assert
2440 (hard_regno < 0
2441 || ira_hard_reg_in_set_p (hard_regno, ALLOCNO_MODE (a),
2442 reg_class_contents[ALLOCNO_CLASS (a)]));
2446 /* Evaluate overall allocation cost and the costs for using hard
2447 registers and memory for allocnos. */
2448 static void
2449 calculate_allocation_cost (void)
2451 int hard_regno, cost;
2452 ira_allocno_t a;
2453 ira_allocno_iterator ai;
2455 ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
2456 FOR_EACH_ALLOCNO (a, ai)
2458 hard_regno = ALLOCNO_HARD_REGNO (a);
2459 ira_assert (hard_regno < 0
2460 || (ira_hard_reg_in_set_p
2461 (hard_regno, ALLOCNO_MODE (a),
2462 reg_class_contents[ALLOCNO_CLASS (a)])));
2463 if (hard_regno < 0)
2465 cost = ALLOCNO_MEMORY_COST (a);
2466 ira_mem_cost += cost;
2468 else if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
2470 cost = (ALLOCNO_HARD_REG_COSTS (a)
2471 [ira_class_hard_reg_index
2472 [ALLOCNO_CLASS (a)][hard_regno]]);
2473 ira_reg_cost += cost;
2475 else
2477 cost = ALLOCNO_CLASS_COST (a);
2478 ira_reg_cost += cost;
2480 ira_overall_cost += cost;
2483 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2485 fprintf (ira_dump_file,
2486 "+++Costs: overall %d, reg %d, mem %d, ld %d, st %d, move %d\n",
2487 ira_overall_cost, ira_reg_cost, ira_mem_cost,
2488 ira_load_cost, ira_store_cost, ira_shuffle_cost);
2489 fprintf (ira_dump_file, "+++ move loops %d, new jumps %d\n",
2490 ira_move_loops_num, ira_additional_jumps_num);
2495 #ifdef ENABLE_IRA_CHECKING
2496 /* Check the correctness of the allocation. We do need this because
2497 of complicated code to transform more one region internal
2498 representation into one region representation. */
2499 static void
2500 check_allocation (void)
2502 ira_allocno_t a;
2503 int hard_regno, nregs, conflict_nregs;
2504 ira_allocno_iterator ai;
2506 FOR_EACH_ALLOCNO (a, ai)
2508 int n = ALLOCNO_NUM_OBJECTS (a);
2509 int i;
2511 if (ALLOCNO_CAP_MEMBER (a) != NULL
2512 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
2513 continue;
2514 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
2515 if (nregs == 1)
2516 /* We allocated a single hard register. */
2517 n = 1;
2518 else if (n > 1)
2519 /* We allocated multiple hard registers, and we will test
2520 conflicts in a granularity of single hard regs. */
2521 nregs = 1;
2523 for (i = 0; i < n; i++)
2525 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2526 ira_object_t conflict_obj;
2527 ira_object_conflict_iterator oci;
2528 int this_regno = hard_regno;
2529 if (n > 1)
2531 if (REG_WORDS_BIG_ENDIAN)
2532 this_regno += n - i - 1;
2533 else
2534 this_regno += i;
2536 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2538 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2539 int conflict_hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
2540 if (conflict_hard_regno < 0)
2541 continue;
2543 conflict_nregs
2544 = (hard_regno_nregs
2545 [conflict_hard_regno][ALLOCNO_MODE (conflict_a)]);
2547 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1
2548 && conflict_nregs == ALLOCNO_NUM_OBJECTS (conflict_a))
2550 if (REG_WORDS_BIG_ENDIAN)
2551 conflict_hard_regno += (ALLOCNO_NUM_OBJECTS (conflict_a)
2552 - OBJECT_SUBWORD (conflict_obj) - 1);
2553 else
2554 conflict_hard_regno += OBJECT_SUBWORD (conflict_obj);
2555 conflict_nregs = 1;
2558 if ((conflict_hard_regno <= this_regno
2559 && this_regno < conflict_hard_regno + conflict_nregs)
2560 || (this_regno <= conflict_hard_regno
2561 && conflict_hard_regno < this_regno + nregs))
2563 fprintf (stderr, "bad allocation for %d and %d\n",
2564 ALLOCNO_REGNO (a), ALLOCNO_REGNO (conflict_a));
2565 gcc_unreachable ();
2571 #endif
2573 /* Allocate REG_EQUIV_INIT. Set up it from IRA_REG_EQUIV which should
2574 be already calculated. */
2575 static void
2576 setup_reg_equiv_init (void)
2578 int i;
2579 int max_regno = max_reg_num ();
2581 for (i = 0; i < max_regno; i++)
2582 reg_equiv_init (i) = ira_reg_equiv[i].init_insns;
2585 /* Update equiv regno from movement of FROM_REGNO to TO_REGNO. INSNS
2586 are insns which were generated for such movement. It is assumed
2587 that FROM_REGNO and TO_REGNO always have the same value at the
2588 point of any move containing such registers. This function is used
2589 to update equiv info for register shuffles on the region borders
2590 and for caller save/restore insns. */
2591 void
2592 ira_update_equiv_info_by_shuffle_insn (int to_regno, int from_regno, rtx_insn *insns)
2594 rtx_insn *insn;
2595 rtx x, note;
2597 if (! ira_reg_equiv[from_regno].defined_p
2598 && (! ira_reg_equiv[to_regno].defined_p
2599 || ((x = ira_reg_equiv[to_regno].memory) != NULL_RTX
2600 && ! MEM_READONLY_P (x))))
2601 return;
2602 insn = insns;
2603 if (NEXT_INSN (insn) != NULL_RTX)
2605 if (! ira_reg_equiv[to_regno].defined_p)
2607 ira_assert (ira_reg_equiv[to_regno].init_insns == NULL_RTX);
2608 return;
2610 ira_reg_equiv[to_regno].defined_p = false;
2611 ira_reg_equiv[to_regno].memory
2612 = ira_reg_equiv[to_regno].constant
2613 = ira_reg_equiv[to_regno].invariant
2614 = ira_reg_equiv[to_regno].init_insns = NULL;
2615 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2616 fprintf (ira_dump_file,
2617 " Invalidating equiv info for reg %d\n", to_regno);
2618 return;
2620 /* It is possible that FROM_REGNO still has no equivalence because
2621 in shuffles to_regno<-from_regno and from_regno<-to_regno the 2nd
2622 insn was not processed yet. */
2623 if (ira_reg_equiv[from_regno].defined_p)
2625 ira_reg_equiv[to_regno].defined_p = true;
2626 if ((x = ira_reg_equiv[from_regno].memory) != NULL_RTX)
2628 ira_assert (ira_reg_equiv[from_regno].invariant == NULL_RTX
2629 && ira_reg_equiv[from_regno].constant == NULL_RTX);
2630 ira_assert (ira_reg_equiv[to_regno].memory == NULL_RTX
2631 || rtx_equal_p (ira_reg_equiv[to_regno].memory, x));
2632 ira_reg_equiv[to_regno].memory = x;
2633 if (! MEM_READONLY_P (x))
2634 /* We don't add the insn to insn init list because memory
2635 equivalence is just to say what memory is better to use
2636 when the pseudo is spilled. */
2637 return;
2639 else if ((x = ira_reg_equiv[from_regno].constant) != NULL_RTX)
2641 ira_assert (ira_reg_equiv[from_regno].invariant == NULL_RTX);
2642 ira_assert (ira_reg_equiv[to_regno].constant == NULL_RTX
2643 || rtx_equal_p (ira_reg_equiv[to_regno].constant, x));
2644 ira_reg_equiv[to_regno].constant = x;
2646 else
2648 x = ira_reg_equiv[from_regno].invariant;
2649 ira_assert (x != NULL_RTX);
2650 ira_assert (ira_reg_equiv[to_regno].invariant == NULL_RTX
2651 || rtx_equal_p (ira_reg_equiv[to_regno].invariant, x));
2652 ira_reg_equiv[to_regno].invariant = x;
2654 if (find_reg_note (insn, REG_EQUIV, x) == NULL_RTX)
2656 note = set_unique_reg_note (insn, REG_EQUIV, x);
2657 gcc_assert (note != NULL_RTX);
2658 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2660 fprintf (ira_dump_file,
2661 " Adding equiv note to insn %u for reg %d ",
2662 INSN_UID (insn), to_regno);
2663 dump_value_slim (ira_dump_file, x, 1);
2664 fprintf (ira_dump_file, "\n");
2668 ira_reg_equiv[to_regno].init_insns
2669 = gen_rtx_INSN_LIST (VOIDmode, insn,
2670 ira_reg_equiv[to_regno].init_insns);
2671 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2672 fprintf (ira_dump_file,
2673 " Adding equiv init move insn %u to reg %d\n",
2674 INSN_UID (insn), to_regno);
2677 /* Fix values of array REG_EQUIV_INIT after live range splitting done
2678 by IRA. */
2679 static void
2680 fix_reg_equiv_init (void)
2682 int max_regno = max_reg_num ();
2683 int i, new_regno, max;
2684 rtx x, prev, next, insn, set;
2686 if (max_regno_before_ira < max_regno)
2688 max = vec_safe_length (reg_equivs);
2689 grow_reg_equivs ();
2690 for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
2691 for (prev = NULL_RTX, x = reg_equiv_init (i);
2692 x != NULL_RTX;
2693 x = next)
2695 next = XEXP (x, 1);
2696 insn = XEXP (x, 0);
2697 set = single_set (as_a <rtx_insn *> (insn));
2698 ira_assert (set != NULL_RTX
2699 && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))));
2700 if (REG_P (SET_DEST (set))
2701 && ((int) REGNO (SET_DEST (set)) == i
2702 || (int) ORIGINAL_REGNO (SET_DEST (set)) == i))
2703 new_regno = REGNO (SET_DEST (set));
2704 else if (REG_P (SET_SRC (set))
2705 && ((int) REGNO (SET_SRC (set)) == i
2706 || (int) ORIGINAL_REGNO (SET_SRC (set)) == i))
2707 new_regno = REGNO (SET_SRC (set));
2708 else
2709 gcc_unreachable ();
2710 if (new_regno == i)
2711 prev = x;
2712 else
2714 /* Remove the wrong list element. */
2715 if (prev == NULL_RTX)
2716 reg_equiv_init (i) = next;
2717 else
2718 XEXP (prev, 1) = next;
2719 XEXP (x, 1) = reg_equiv_init (new_regno);
2720 reg_equiv_init (new_regno) = x;
2726 #ifdef ENABLE_IRA_CHECKING
2727 /* Print redundant memory-memory copies. */
2728 static void
2729 print_redundant_copies (void)
2731 int hard_regno;
2732 ira_allocno_t a;
2733 ira_copy_t cp, next_cp;
2734 ira_allocno_iterator ai;
2736 FOR_EACH_ALLOCNO (a, ai)
2738 if (ALLOCNO_CAP_MEMBER (a) != NULL)
2739 /* It is a cap. */
2740 continue;
2741 hard_regno = ALLOCNO_HARD_REGNO (a);
2742 if (hard_regno >= 0)
2743 continue;
2744 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2745 if (cp->first == a)
2746 next_cp = cp->next_first_allocno_copy;
2747 else
2749 next_cp = cp->next_second_allocno_copy;
2750 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL
2751 && cp->insn != NULL_RTX
2752 && ALLOCNO_HARD_REGNO (cp->first) == hard_regno)
2753 fprintf (ira_dump_file,
2754 " Redundant move from %d(freq %d):%d\n",
2755 INSN_UID (cp->insn), cp->freq, hard_regno);
2759 #endif
2761 /* Setup preferred and alternative classes for new pseudo-registers
2762 created by IRA starting with START. */
2763 static void
2764 setup_preferred_alternate_classes_for_new_pseudos (int start)
2766 int i, old_regno;
2767 int max_regno = max_reg_num ();
2769 for (i = start; i < max_regno; i++)
2771 old_regno = ORIGINAL_REGNO (regno_reg_rtx[i]);
2772 ira_assert (i != old_regno);
2773 setup_reg_classes (i, reg_preferred_class (old_regno),
2774 reg_alternate_class (old_regno),
2775 reg_allocno_class (old_regno));
2776 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2777 fprintf (ira_dump_file,
2778 " New r%d: setting preferred %s, alternative %s\n",
2779 i, reg_class_names[reg_preferred_class (old_regno)],
2780 reg_class_names[reg_alternate_class (old_regno)]);
2785 /* The number of entries allocated in reg_info. */
2786 static int allocated_reg_info_size;
2788 /* Regional allocation can create new pseudo-registers. This function
2789 expands some arrays for pseudo-registers. */
2790 static void
2791 expand_reg_info (void)
2793 int i;
2794 int size = max_reg_num ();
2796 resize_reg_info ();
2797 for (i = allocated_reg_info_size; i < size; i++)
2798 setup_reg_classes (i, GENERAL_REGS, ALL_REGS, GENERAL_REGS);
2799 setup_preferred_alternate_classes_for_new_pseudos (allocated_reg_info_size);
2800 allocated_reg_info_size = size;
2803 /* Return TRUE if there is too high register pressure in the function.
2804 It is used to decide when stack slot sharing is worth to do. */
2805 static bool
2806 too_high_register_pressure_p (void)
2808 int i;
2809 enum reg_class pclass;
2811 for (i = 0; i < ira_pressure_classes_num; i++)
2813 pclass = ira_pressure_classes[i];
2814 if (ira_loop_tree_root->reg_pressure[pclass] > 10000)
2815 return true;
2817 return false;
2822 /* Indicate that hard register number FROM was eliminated and replaced with
2823 an offset from hard register number TO. The status of hard registers live
2824 at the start of a basic block is updated by replacing a use of FROM with
2825 a use of TO. */
2827 void
2828 mark_elimination (int from, int to)
2830 basic_block bb;
2831 bitmap r;
2833 FOR_EACH_BB_FN (bb, cfun)
2835 r = DF_LR_IN (bb);
2836 if (bitmap_bit_p (r, from))
2838 bitmap_clear_bit (r, from);
2839 bitmap_set_bit (r, to);
2841 if (! df_live)
2842 continue;
2843 r = DF_LIVE_IN (bb);
2844 if (bitmap_bit_p (r, from))
2846 bitmap_clear_bit (r, from);
2847 bitmap_set_bit (r, to);
2854 /* The length of the following array. */
2855 int ira_reg_equiv_len;
2857 /* Info about equiv. info for each register. */
2858 struct ira_reg_equiv_s *ira_reg_equiv;
2860 /* Expand ira_reg_equiv if necessary. */
2861 void
2862 ira_expand_reg_equiv (void)
2864 int old = ira_reg_equiv_len;
2866 if (ira_reg_equiv_len > max_reg_num ())
2867 return;
2868 ira_reg_equiv_len = max_reg_num () * 3 / 2 + 1;
2869 ira_reg_equiv
2870 = (struct ira_reg_equiv_s *) xrealloc (ira_reg_equiv,
2871 ira_reg_equiv_len
2872 * sizeof (struct ira_reg_equiv_s));
2873 gcc_assert (old < ira_reg_equiv_len);
2874 memset (ira_reg_equiv + old, 0,
2875 sizeof (struct ira_reg_equiv_s) * (ira_reg_equiv_len - old));
2878 static void
2879 init_reg_equiv (void)
2881 ira_reg_equiv_len = 0;
2882 ira_reg_equiv = NULL;
2883 ira_expand_reg_equiv ();
2886 static void
2887 finish_reg_equiv (void)
2889 free (ira_reg_equiv);
2894 struct equivalence
2896 /* Set when a REG_EQUIV note is found or created. Use to
2897 keep track of what memory accesses might be created later,
2898 e.g. by reload. */
2899 rtx replacement;
2900 rtx *src_p;
2902 /* The list of each instruction which initializes this register.
2904 NULL indicates we know nothing about this register's equivalence
2905 properties.
2907 An INSN_LIST with a NULL insn indicates this pseudo is already
2908 known to not have a valid equivalence. */
2909 rtx_insn_list *init_insns;
2911 /* Loop depth is used to recognize equivalences which appear
2912 to be present within the same loop (or in an inner loop). */
2913 short loop_depth;
2914 /* Nonzero if this had a preexisting REG_EQUIV note. */
2915 unsigned char is_arg_equivalence : 1;
2916 /* Set when an attempt should be made to replace a register
2917 with the associated src_p entry. */
2918 unsigned char replace : 1;
2919 /* Set if this register has no known equivalence. */
2920 unsigned char no_equiv : 1;
2923 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
2924 structure for that register. */
2925 static struct equivalence *reg_equiv;
2927 /* Used for communication between the following two functions: contains
2928 a MEM that we wish to ensure remains unchanged. */
2929 static rtx equiv_mem;
2931 /* Set nonzero if EQUIV_MEM is modified. */
2932 static int equiv_mem_modified;
2934 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
2935 Called via note_stores. */
2936 static void
2937 validate_equiv_mem_from_store (rtx dest, const_rtx set ATTRIBUTE_UNUSED,
2938 void *data ATTRIBUTE_UNUSED)
2940 if ((REG_P (dest)
2941 && reg_overlap_mentioned_p (dest, equiv_mem))
2942 || (MEM_P (dest)
2943 && anti_dependence (equiv_mem, dest)))
2944 equiv_mem_modified = 1;
2947 /* Verify that no store between START and the death of REG invalidates
2948 MEMREF. MEMREF is invalidated by modifying a register used in MEMREF,
2949 by storing into an overlapping memory location, or with a non-const
2950 CALL_INSN.
2952 Return 1 if MEMREF remains valid. */
2953 static int
2954 validate_equiv_mem (rtx_insn *start, rtx reg, rtx memref)
2956 rtx_insn *insn;
2957 rtx note;
2959 equiv_mem = memref;
2960 equiv_mem_modified = 0;
2962 /* If the memory reference has side effects or is volatile, it isn't a
2963 valid equivalence. */
2964 if (side_effects_p (memref))
2965 return 0;
2967 for (insn = start; insn && ! equiv_mem_modified; insn = NEXT_INSN (insn))
2969 if (! INSN_P (insn))
2970 continue;
2972 if (find_reg_note (insn, REG_DEAD, reg))
2973 return 1;
2975 /* This used to ignore readonly memory and const/pure calls. The problem
2976 is the equivalent form may reference a pseudo which gets assigned a
2977 call clobbered hard reg. When we later replace REG with its
2978 equivalent form, the value in the call-clobbered reg has been
2979 changed and all hell breaks loose. */
2980 if (CALL_P (insn))
2981 return 0;
2983 note_stores (PATTERN (insn), validate_equiv_mem_from_store, NULL);
2985 /* If a register mentioned in MEMREF is modified via an
2986 auto-increment, we lose the equivalence. Do the same if one
2987 dies; although we could extend the life, it doesn't seem worth
2988 the trouble. */
2990 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2991 if ((REG_NOTE_KIND (note) == REG_INC
2992 || REG_NOTE_KIND (note) == REG_DEAD)
2993 && REG_P (XEXP (note, 0))
2994 && reg_overlap_mentioned_p (XEXP (note, 0), memref))
2995 return 0;
2998 return 0;
3001 /* Returns zero if X is known to be invariant. */
3002 static int
3003 equiv_init_varies_p (rtx x)
3005 RTX_CODE code = GET_CODE (x);
3006 int i;
3007 const char *fmt;
3009 switch (code)
3011 case MEM:
3012 return !MEM_READONLY_P (x) || equiv_init_varies_p (XEXP (x, 0));
3014 case CONST:
3015 CASE_CONST_ANY:
3016 case SYMBOL_REF:
3017 case LABEL_REF:
3018 return 0;
3020 case REG:
3021 return reg_equiv[REGNO (x)].replace == 0 && rtx_varies_p (x, 0);
3023 case ASM_OPERANDS:
3024 if (MEM_VOLATILE_P (x))
3025 return 1;
3027 /* Fall through. */
3029 default:
3030 break;
3033 fmt = GET_RTX_FORMAT (code);
3034 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3035 if (fmt[i] == 'e')
3037 if (equiv_init_varies_p (XEXP (x, i)))
3038 return 1;
3040 else if (fmt[i] == 'E')
3042 int j;
3043 for (j = 0; j < XVECLEN (x, i); j++)
3044 if (equiv_init_varies_p (XVECEXP (x, i, j)))
3045 return 1;
3048 return 0;
3051 /* Returns nonzero if X (used to initialize register REGNO) is movable.
3052 X is only movable if the registers it uses have equivalent initializations
3053 which appear to be within the same loop (or in an inner loop) and movable
3054 or if they are not candidates for local_alloc and don't vary. */
3055 static int
3056 equiv_init_movable_p (rtx x, int regno)
3058 int i, j;
3059 const char *fmt;
3060 enum rtx_code code = GET_CODE (x);
3062 switch (code)
3064 case SET:
3065 return equiv_init_movable_p (SET_SRC (x), regno);
3067 case CC0:
3068 case CLOBBER:
3069 return 0;
3071 case PRE_INC:
3072 case PRE_DEC:
3073 case POST_INC:
3074 case POST_DEC:
3075 case PRE_MODIFY:
3076 case POST_MODIFY:
3077 return 0;
3079 case REG:
3080 return ((reg_equiv[REGNO (x)].loop_depth >= reg_equiv[regno].loop_depth
3081 && reg_equiv[REGNO (x)].replace)
3082 || (REG_BASIC_BLOCK (REGNO (x)) < NUM_FIXED_BLOCKS
3083 && ! rtx_varies_p (x, 0)));
3085 case UNSPEC_VOLATILE:
3086 return 0;
3088 case ASM_OPERANDS:
3089 if (MEM_VOLATILE_P (x))
3090 return 0;
3092 /* Fall through. */
3094 default:
3095 break;
3098 fmt = GET_RTX_FORMAT (code);
3099 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3100 switch (fmt[i])
3102 case 'e':
3103 if (! equiv_init_movable_p (XEXP (x, i), regno))
3104 return 0;
3105 break;
3106 case 'E':
3107 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3108 if (! equiv_init_movable_p (XVECEXP (x, i, j), regno))
3109 return 0;
3110 break;
3113 return 1;
3116 /* TRUE if X uses any registers for which reg_equiv[REGNO].replace is
3117 true. */
3118 static int
3119 contains_replace_regs (rtx x)
3121 int i, j;
3122 const char *fmt;
3123 enum rtx_code code = GET_CODE (x);
3125 switch (code)
3127 case CONST:
3128 case LABEL_REF:
3129 case SYMBOL_REF:
3130 CASE_CONST_ANY:
3131 case PC:
3132 case CC0:
3133 case HIGH:
3134 return 0;
3136 case REG:
3137 return reg_equiv[REGNO (x)].replace;
3139 default:
3140 break;
3143 fmt = GET_RTX_FORMAT (code);
3144 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3145 switch (fmt[i])
3147 case 'e':
3148 if (contains_replace_regs (XEXP (x, i)))
3149 return 1;
3150 break;
3151 case 'E':
3152 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3153 if (contains_replace_regs (XVECEXP (x, i, j)))
3154 return 1;
3155 break;
3158 return 0;
3161 /* TRUE if X references a memory location that would be affected by a store
3162 to MEMREF. */
3163 static int
3164 memref_referenced_p (rtx memref, rtx x)
3166 int i, j;
3167 const char *fmt;
3168 enum rtx_code code = GET_CODE (x);
3170 switch (code)
3172 case CONST:
3173 case LABEL_REF:
3174 case SYMBOL_REF:
3175 CASE_CONST_ANY:
3176 case PC:
3177 case CC0:
3178 case HIGH:
3179 case LO_SUM:
3180 return 0;
3182 case REG:
3183 return (reg_equiv[REGNO (x)].replacement
3184 && memref_referenced_p (memref,
3185 reg_equiv[REGNO (x)].replacement));
3187 case MEM:
3188 if (true_dependence (memref, VOIDmode, x))
3189 return 1;
3190 break;
3192 case SET:
3193 /* If we are setting a MEM, it doesn't count (its address does), but any
3194 other SET_DEST that has a MEM in it is referencing the MEM. */
3195 if (MEM_P (SET_DEST (x)))
3197 if (memref_referenced_p (memref, XEXP (SET_DEST (x), 0)))
3198 return 1;
3200 else if (memref_referenced_p (memref, SET_DEST (x)))
3201 return 1;
3203 return memref_referenced_p (memref, SET_SRC (x));
3205 default:
3206 break;
3209 fmt = GET_RTX_FORMAT (code);
3210 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3211 switch (fmt[i])
3213 case 'e':
3214 if (memref_referenced_p (memref, XEXP (x, i)))
3215 return 1;
3216 break;
3217 case 'E':
3218 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3219 if (memref_referenced_p (memref, XVECEXP (x, i, j)))
3220 return 1;
3221 break;
3224 return 0;
3227 /* TRUE if some insn in the range (START, END] references a memory location
3228 that would be affected by a store to MEMREF. */
3229 static int
3230 memref_used_between_p (rtx memref, rtx_insn *start, rtx_insn *end)
3232 rtx_insn *insn;
3234 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
3235 insn = NEXT_INSN (insn))
3237 if (!NONDEBUG_INSN_P (insn))
3238 continue;
3240 if (memref_referenced_p (memref, PATTERN (insn)))
3241 return 1;
3243 /* Nonconst functions may access memory. */
3244 if (CALL_P (insn) && (! RTL_CONST_CALL_P (insn)))
3245 return 1;
3248 return 0;
3251 /* Mark REG as having no known equivalence.
3252 Some instructions might have been processed before and furnished
3253 with REG_EQUIV notes for this register; these notes will have to be
3254 removed.
3255 STORE is the piece of RTL that does the non-constant / conflicting
3256 assignment - a SET, CLOBBER or REG_INC note. It is currently not used,
3257 but needs to be there because this function is called from note_stores. */
3258 static void
3259 no_equiv (rtx reg, const_rtx store ATTRIBUTE_UNUSED,
3260 void *data ATTRIBUTE_UNUSED)
3262 int regno;
3263 rtx_insn_list *list;
3265 if (!REG_P (reg))
3266 return;
3267 regno = REGNO (reg);
3268 reg_equiv[regno].no_equiv = 1;
3269 list = reg_equiv[regno].init_insns;
3270 if (list && list->insn () == NULL)
3271 return;
3272 reg_equiv[regno].init_insns = gen_rtx_INSN_LIST (VOIDmode, NULL_RTX, NULL);
3273 reg_equiv[regno].replacement = NULL_RTX;
3274 /* This doesn't matter for equivalences made for argument registers, we
3275 should keep their initialization insns. */
3276 if (reg_equiv[regno].is_arg_equivalence)
3277 return;
3278 ira_reg_equiv[regno].defined_p = false;
3279 ira_reg_equiv[regno].init_insns = NULL;
3280 for (; list; list = list->next ())
3282 rtx_insn *insn = list->insn ();
3283 remove_note (insn, find_reg_note (insn, REG_EQUIV, NULL_RTX));
3287 /* Check whether the SUBREG is a paradoxical subreg and set the result
3288 in PDX_SUBREGS. */
3290 static void
3291 set_paradoxical_subreg (rtx_insn *insn, bool *pdx_subregs)
3293 subrtx_iterator::array_type array;
3294 FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
3296 const_rtx subreg = *iter;
3297 if (GET_CODE (subreg) == SUBREG)
3299 const_rtx reg = SUBREG_REG (subreg);
3300 if (REG_P (reg) && paradoxical_subreg_p (subreg))
3301 pdx_subregs[REGNO (reg)] = true;
3306 /* In DEBUG_INSN location adjust REGs from CLEARED_REGS bitmap to the
3307 equivalent replacement. */
3309 static rtx
3310 adjust_cleared_regs (rtx loc, const_rtx old_rtx ATTRIBUTE_UNUSED, void *data)
3312 if (REG_P (loc))
3314 bitmap cleared_regs = (bitmap) data;
3315 if (bitmap_bit_p (cleared_regs, REGNO (loc)))
3316 return simplify_replace_fn_rtx (copy_rtx (*reg_equiv[REGNO (loc)].src_p),
3317 NULL_RTX, adjust_cleared_regs, data);
3319 return NULL_RTX;
3322 /* Nonzero if we recorded an equivalence for a LABEL_REF. */
3323 static int recorded_label_ref;
3325 /* Find registers that are equivalent to a single value throughout the
3326 compilation (either because they can be referenced in memory or are
3327 set once from a single constant). Lower their priority for a
3328 register.
3330 If such a register is only referenced once, try substituting its
3331 value into the using insn. If it succeeds, we can eliminate the
3332 register completely.
3334 Initialize init_insns in ira_reg_equiv array.
3336 Return non-zero if jump label rebuilding should be done. */
3337 static int
3338 update_equiv_regs (void)
3340 rtx_insn *insn;
3341 basic_block bb;
3342 int loop_depth;
3343 bitmap cleared_regs;
3344 bool *pdx_subregs;
3346 /* We need to keep track of whether or not we recorded a LABEL_REF so
3347 that we know if the jump optimizer needs to be rerun. */
3348 recorded_label_ref = 0;
3350 /* Use pdx_subregs to show whether a reg is used in a paradoxical
3351 subreg. */
3352 pdx_subregs = XCNEWVEC (bool, max_regno);
3354 reg_equiv = XCNEWVEC (struct equivalence, max_regno);
3355 grow_reg_equivs ();
3357 init_alias_analysis ();
3359 /* Scan insns and set pdx_subregs[regno] 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, pdx_subregs);
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 FOR_EACH_BB_FN (bb, cfun)
3373 loop_depth = bb_loop_depth (bb);
3375 for (insn = BB_HEAD (bb);
3376 insn != NEXT_INSN (BB_END (bb));
3377 insn = NEXT_INSN (insn))
3379 rtx note;
3380 rtx set;
3381 rtx dest, src;
3382 int regno;
3384 if (! INSN_P (insn))
3385 continue;
3387 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
3388 if (REG_NOTE_KIND (note) == REG_INC)
3389 no_equiv (XEXP (note, 0), note, NULL);
3391 set = single_set (insn);
3393 /* If this insn contains more (or less) than a single SET,
3394 only mark all destinations as having no known equivalence. */
3395 if (set == NULL_RTX)
3397 note_stores (PATTERN (insn), no_equiv, NULL);
3398 continue;
3400 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3402 int i;
3404 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
3406 rtx part = XVECEXP (PATTERN (insn), 0, i);
3407 if (part != set)
3408 note_stores (part, no_equiv, NULL);
3412 dest = SET_DEST (set);
3413 src = SET_SRC (set);
3415 /* See if this is setting up the equivalence between an argument
3416 register and its stack slot. */
3417 note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
3418 if (note)
3420 gcc_assert (REG_P (dest));
3421 regno = REGNO (dest);
3423 /* Note that we don't want to clear init_insns in
3424 ira_reg_equiv even if there are multiple sets of this
3425 register. */
3426 reg_equiv[regno].is_arg_equivalence = 1;
3428 /* The insn result can have equivalence memory although
3429 the equivalence is not set up by the insn. We add
3430 this insn to init insns as it is a flag for now that
3431 regno has an equivalence. We will remove the insn
3432 from init insn list later. */
3433 if (rtx_equal_p (src, XEXP (note, 0)) || MEM_P (XEXP (note, 0)))
3434 ira_reg_equiv[regno].init_insns
3435 = gen_rtx_INSN_LIST (VOIDmode, insn,
3436 ira_reg_equiv[regno].init_insns);
3438 /* Continue normally in case this is a candidate for
3439 replacements. */
3442 if (!optimize)
3443 continue;
3445 /* We only handle the case of a pseudo register being set
3446 once, or always to the same value. */
3447 /* ??? The mn10200 port breaks if we add equivalences for
3448 values that need an ADDRESS_REGS register and set them equivalent
3449 to a MEM of a pseudo. The actual problem is in the over-conservative
3450 handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
3451 calculate_needs, but we traditionally work around this problem
3452 here by rejecting equivalences when the destination is in a register
3453 that's likely spilled. This is fragile, of course, since the
3454 preferred class of a pseudo depends on all instructions that set
3455 or use it. */
3457 if (!REG_P (dest)
3458 || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER
3459 || (reg_equiv[regno].init_insns
3460 && reg_equiv[regno].init_insns->insn () == NULL)
3461 || (targetm.class_likely_spilled_p (reg_preferred_class (regno))
3462 && MEM_P (src) && ! reg_equiv[regno].is_arg_equivalence))
3464 /* This might be setting a SUBREG of a pseudo, a pseudo that is
3465 also set somewhere else to a constant. */
3466 note_stores (set, no_equiv, NULL);
3467 continue;
3470 /* Don't set reg (if pdx_subregs[regno] == true) equivalent to a mem. */
3471 if (MEM_P (src) && pdx_subregs[regno])
3473 note_stores (set, no_equiv, NULL);
3474 continue;
3477 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
3479 /* cse sometimes generates function invariants, but doesn't put a
3480 REG_EQUAL note on the insn. Since this note would be redundant,
3481 there's no point creating it earlier than here. */
3482 if (! note && ! rtx_varies_p (src, 0))
3483 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
3485 /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
3486 since it represents a function call. */
3487 if (note && GET_CODE (XEXP (note, 0)) == EXPR_LIST)
3488 note = NULL_RTX;
3490 if (DF_REG_DEF_COUNT (regno) != 1)
3492 bool equal_p = true;
3493 rtx_insn_list *list;
3495 /* If we have already processed this pseudo and determined it
3496 can not have an equivalence, then honor that decision. */
3497 if (reg_equiv[regno].no_equiv)
3498 continue;
3500 if (! note
3501 || rtx_varies_p (XEXP (note, 0), 0)
3502 || (reg_equiv[regno].replacement
3503 && ! rtx_equal_p (XEXP (note, 0),
3504 reg_equiv[regno].replacement)))
3506 no_equiv (dest, set, NULL);
3507 continue;
3510 list = reg_equiv[regno].init_insns;
3511 for (; list; list = list->next ())
3513 rtx note_tmp;
3514 rtx_insn *insn_tmp;
3516 insn_tmp = list->insn ();
3517 note_tmp = find_reg_note (insn_tmp, REG_EQUAL, NULL_RTX);
3518 gcc_assert (note_tmp);
3519 if (! rtx_equal_p (XEXP (note, 0), XEXP (note_tmp, 0)))
3521 equal_p = false;
3522 break;
3526 if (! equal_p)
3528 no_equiv (dest, set, NULL);
3529 continue;
3533 /* Record this insn as initializing this register. */
3534 reg_equiv[regno].init_insns
3535 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv[regno].init_insns);
3537 /* If this register is known to be equal to a constant, record that
3538 it is always equivalent to the constant. */
3539 if (DF_REG_DEF_COUNT (regno) == 1
3540 && note && ! rtx_varies_p (XEXP (note, 0), 0))
3542 rtx note_value = XEXP (note, 0);
3543 remove_note (insn, note);
3544 set_unique_reg_note (insn, REG_EQUIV, note_value);
3547 /* If this insn introduces a "constant" register, decrease the priority
3548 of that register. Record this insn if the register is only used once
3549 more and the equivalence value is the same as our source.
3551 The latter condition is checked for two reasons: First, it is an
3552 indication that it may be more efficient to actually emit the insn
3553 as written (if no registers are available, reload will substitute
3554 the equivalence). Secondly, it avoids problems with any registers
3555 dying in this insn whose death notes would be missed.
3557 If we don't have a REG_EQUIV note, see if this insn is loading
3558 a register used only in one basic block from a MEM. If so, and the
3559 MEM remains unchanged for the life of the register, add a REG_EQUIV
3560 note. */
3561 note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
3563 if (note == NULL_RTX && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
3564 && MEM_P (SET_SRC (set))
3565 && validate_equiv_mem (insn, dest, SET_SRC (set)))
3566 note = set_unique_reg_note (insn, REG_EQUIV, copy_rtx (SET_SRC (set)));
3568 if (note)
3570 int regno = REGNO (dest);
3571 rtx x = XEXP (note, 0);
3573 /* If we haven't done so, record for reload that this is an
3574 equivalencing insn. */
3575 if (!reg_equiv[regno].is_arg_equivalence)
3576 ira_reg_equiv[regno].init_insns
3577 = gen_rtx_INSN_LIST (VOIDmode, insn,
3578 ira_reg_equiv[regno].init_insns);
3580 /* Record whether or not we created a REG_EQUIV note for a LABEL_REF.
3581 We might end up substituting the LABEL_REF for uses of the
3582 pseudo here or later. That kind of transformation may turn an
3583 indirect jump into a direct jump, in which case we must rerun the
3584 jump optimizer to ensure that the JUMP_LABEL fields are valid. */
3585 if (GET_CODE (x) == LABEL_REF
3586 || (GET_CODE (x) == CONST
3587 && GET_CODE (XEXP (x, 0)) == PLUS
3588 && (GET_CODE (XEXP (XEXP (x, 0), 0)) == LABEL_REF)))
3589 recorded_label_ref = 1;
3591 reg_equiv[regno].replacement = x;
3592 reg_equiv[regno].src_p = &SET_SRC (set);
3593 reg_equiv[regno].loop_depth = (short) loop_depth;
3595 /* Don't mess with things live during setjmp. */
3596 if (REG_LIVE_LENGTH (regno) >= 0 && optimize)
3598 /* Note that the statement below does not affect the priority
3599 in local-alloc! */
3600 REG_LIVE_LENGTH (regno) *= 2;
3602 /* If the register is referenced exactly twice, meaning it is
3603 set once and used once, indicate that the reference may be
3604 replaced by the equivalence we computed above. Do this
3605 even if the register is only used in one block so that
3606 dependencies can be handled where the last register is
3607 used in a different block (i.e. HIGH / LO_SUM sequences)
3608 and to reduce the number of registers alive across
3609 calls. */
3611 if (REG_N_REFS (regno) == 2
3612 && (rtx_equal_p (x, src)
3613 || ! equiv_init_varies_p (src))
3614 && NONJUMP_INSN_P (insn)
3615 && equiv_init_movable_p (PATTERN (insn), regno))
3616 reg_equiv[regno].replace = 1;
3622 if (!optimize)
3623 goto out;
3625 /* A second pass, to gather additional equivalences with memory. This needs
3626 to be done after we know which registers we are going to replace. */
3628 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
3630 rtx set, src, dest;
3631 unsigned regno;
3633 if (! INSN_P (insn))
3634 continue;
3636 set = single_set (insn);
3637 if (! set)
3638 continue;
3640 dest = SET_DEST (set);
3641 src = SET_SRC (set);
3643 /* If this sets a MEM to the contents of a REG that is only used
3644 in a single basic block, see if the register is always equivalent
3645 to that memory location and if moving the store from INSN to the
3646 insn that set REG is safe. If so, put a REG_EQUIV note on the
3647 initializing insn.
3649 Don't add a REG_EQUIV note if the insn already has one. The existing
3650 REG_EQUIV is likely more useful than the one we are adding.
3652 If one of the regs in the address has reg_equiv[REGNO].replace set,
3653 then we can't add this REG_EQUIV note. The reg_equiv[REGNO].replace
3654 optimization may move the set of this register immediately before
3655 insn, which puts it after reg_equiv[REGNO].init_insns, and hence
3656 the mention in the REG_EQUIV note would be to an uninitialized
3657 pseudo. */
3659 if (MEM_P (dest) && REG_P (src)
3660 && (regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
3661 && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
3662 && DF_REG_DEF_COUNT (regno) == 1
3663 && reg_equiv[regno].init_insns != NULL
3664 && reg_equiv[regno].init_insns->insn () != NULL
3665 && ! find_reg_note (XEXP (reg_equiv[regno].init_insns, 0),
3666 REG_EQUIV, NULL_RTX)
3667 && ! contains_replace_regs (XEXP (dest, 0))
3668 && ! pdx_subregs[regno])
3670 rtx_insn *init_insn =
3671 as_a <rtx_insn *> (XEXP (reg_equiv[regno].init_insns, 0));
3672 if (validate_equiv_mem (init_insn, src, dest)
3673 && ! memref_used_between_p (dest, init_insn, insn)
3674 /* Attaching a REG_EQUIV note will fail if INIT_INSN has
3675 multiple sets. */
3676 && set_unique_reg_note (init_insn, REG_EQUIV, copy_rtx (dest)))
3678 /* This insn makes the equivalence, not the one initializing
3679 the register. */
3680 ira_reg_equiv[regno].init_insns
3681 = gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
3682 df_notes_rescan (init_insn);
3687 cleared_regs = BITMAP_ALLOC (NULL);
3688 /* Now scan all regs killed in an insn to see if any of them are
3689 registers only used that once. If so, see if we can replace the
3690 reference with the equivalent form. If we can, delete the
3691 initializing reference and this register will go away. If we
3692 can't replace the reference, and the initializing reference is
3693 within the same loop (or in an inner loop), then move the register
3694 initialization just before the use, so that they are in the same
3695 basic block. */
3696 FOR_EACH_BB_REVERSE_FN (bb, cfun)
3698 loop_depth = bb_loop_depth (bb);
3699 for (insn = BB_END (bb);
3700 insn != PREV_INSN (BB_HEAD (bb));
3701 insn = PREV_INSN (insn))
3703 rtx link;
3705 if (! INSN_P (insn))
3706 continue;
3708 /* Don't substitute into a non-local goto, this confuses CFG. */
3709 if (JUMP_P (insn)
3710 && find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
3711 continue;
3713 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3715 if (REG_NOTE_KIND (link) == REG_DEAD
3716 /* Make sure this insn still refers to the register. */
3717 && reg_mentioned_p (XEXP (link, 0), PATTERN (insn)))
3719 int regno = REGNO (XEXP (link, 0));
3720 rtx equiv_insn;
3722 if (! reg_equiv[regno].replace
3723 || reg_equiv[regno].loop_depth < (short) loop_depth
3724 /* There is no sense to move insns if live range
3725 shrinkage or register pressure-sensitive
3726 scheduling were done because it will not
3727 improve allocation but worsen insn schedule
3728 with a big probability. */
3729 || flag_live_range_shrinkage
3730 || (flag_sched_pressure && flag_schedule_insns))
3731 continue;
3733 /* reg_equiv[REGNO].replace gets set only when
3734 REG_N_REFS[REGNO] is 2, i.e. the register is set
3735 once and used once. (If it were only set, but
3736 not used, flow would have deleted the setting
3737 insns.) Hence there can only be one insn in
3738 reg_equiv[REGNO].init_insns. */
3739 gcc_assert (reg_equiv[regno].init_insns
3740 && !XEXP (reg_equiv[regno].init_insns, 1));
3741 equiv_insn = XEXP (reg_equiv[regno].init_insns, 0);
3743 /* We may not move instructions that can throw, since
3744 that changes basic block boundaries and we are not
3745 prepared to adjust the CFG to match. */
3746 if (can_throw_internal (equiv_insn))
3747 continue;
3749 if (asm_noperands (PATTERN (equiv_insn)) < 0
3750 && validate_replace_rtx (regno_reg_rtx[regno],
3751 *(reg_equiv[regno].src_p), insn))
3753 rtx equiv_link;
3754 rtx last_link;
3755 rtx note;
3757 /* Find the last note. */
3758 for (last_link = link; XEXP (last_link, 1);
3759 last_link = XEXP (last_link, 1))
3762 /* Append the REG_DEAD notes from equiv_insn. */
3763 equiv_link = REG_NOTES (equiv_insn);
3764 while (equiv_link)
3766 note = equiv_link;
3767 equiv_link = XEXP (equiv_link, 1);
3768 if (REG_NOTE_KIND (note) == REG_DEAD)
3770 remove_note (equiv_insn, note);
3771 XEXP (last_link, 1) = note;
3772 XEXP (note, 1) = NULL_RTX;
3773 last_link = note;
3777 remove_death (regno, insn);
3778 SET_REG_N_REFS (regno, 0);
3779 REG_FREQ (regno) = 0;
3780 delete_insn (equiv_insn);
3782 reg_equiv[regno].init_insns
3783 = reg_equiv[regno].init_insns->next ();
3785 ira_reg_equiv[regno].init_insns = NULL;
3786 bitmap_set_bit (cleared_regs, regno);
3788 /* Move the initialization of the register to just before
3789 INSN. Update the flow information. */
3790 else if (prev_nondebug_insn (insn) != equiv_insn)
3792 rtx_insn *new_insn;
3794 new_insn = emit_insn_before (PATTERN (equiv_insn), insn);
3795 REG_NOTES (new_insn) = REG_NOTES (equiv_insn);
3796 REG_NOTES (equiv_insn) = 0;
3797 /* Rescan it to process the notes. */
3798 df_insn_rescan (new_insn);
3800 /* Make sure this insn is recognized before
3801 reload begins, otherwise
3802 eliminate_regs_in_insn will die. */
3803 INSN_CODE (new_insn) = INSN_CODE (equiv_insn);
3805 delete_insn (equiv_insn);
3807 XEXP (reg_equiv[regno].init_insns, 0) = new_insn;
3809 REG_BASIC_BLOCK (regno) = bb->index;
3810 REG_N_CALLS_CROSSED (regno) = 0;
3811 REG_FREQ_CALLS_CROSSED (regno) = 0;
3812 REG_N_THROWING_CALLS_CROSSED (regno) = 0;
3813 REG_LIVE_LENGTH (regno) = 2;
3815 if (insn == BB_HEAD (bb))
3816 BB_HEAD (bb) = PREV_INSN (insn);
3818 ira_reg_equiv[regno].init_insns
3819 = gen_rtx_INSN_LIST (VOIDmode, new_insn, NULL_RTX);
3820 bitmap_set_bit (cleared_regs, regno);
3827 if (!bitmap_empty_p (cleared_regs))
3829 FOR_EACH_BB_FN (bb, cfun)
3831 bitmap_and_compl_into (DF_LR_IN (bb), cleared_regs);
3832 bitmap_and_compl_into (DF_LR_OUT (bb), cleared_regs);
3833 if (! df_live)
3834 continue;
3835 bitmap_and_compl_into (DF_LIVE_IN (bb), cleared_regs);
3836 bitmap_and_compl_into (DF_LIVE_OUT (bb), cleared_regs);
3839 /* Last pass - adjust debug insns referencing cleared regs. */
3840 if (MAY_HAVE_DEBUG_INSNS)
3841 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
3842 if (DEBUG_INSN_P (insn))
3844 rtx old_loc = INSN_VAR_LOCATION_LOC (insn);
3845 INSN_VAR_LOCATION_LOC (insn)
3846 = simplify_replace_fn_rtx (old_loc, NULL_RTX,
3847 adjust_cleared_regs,
3848 (void *) cleared_regs);
3849 if (old_loc != INSN_VAR_LOCATION_LOC (insn))
3850 df_insn_rescan (insn);
3854 BITMAP_FREE (cleared_regs);
3856 out:
3857 /* Clean up. */
3859 end_alias_analysis ();
3860 free (reg_equiv);
3861 free (pdx_subregs);
3862 return recorded_label_ref;
3867 /* Set up fields memory, constant, and invariant from init_insns in
3868 the structures of array ira_reg_equiv. */
3869 static void
3870 setup_reg_equiv (void)
3872 int i;
3873 rtx_insn_list *elem, *prev_elem, *next_elem;
3874 rtx_insn *insn;
3875 rtx set, x;
3877 for (i = FIRST_PSEUDO_REGISTER; i < ira_reg_equiv_len; i++)
3878 for (prev_elem = NULL, elem = ira_reg_equiv[i].init_insns;
3879 elem;
3880 prev_elem = elem, elem = next_elem)
3882 next_elem = elem->next ();
3883 insn = elem->insn ();
3884 set = single_set (insn);
3886 /* Init insns can set up equivalence when the reg is a destination or
3887 a source (in this case the destination is memory). */
3888 if (set != 0 && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))))
3890 if ((x = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != NULL)
3892 x = XEXP (x, 0);
3893 if (REG_P (SET_DEST (set))
3894 && REGNO (SET_DEST (set)) == (unsigned int) i
3895 && ! rtx_equal_p (SET_SRC (set), x) && MEM_P (x))
3897 /* This insn reporting the equivalence but
3898 actually not setting it. Remove it from the
3899 list. */
3900 if (prev_elem == NULL)
3901 ira_reg_equiv[i].init_insns = next_elem;
3902 else
3903 XEXP (prev_elem, 1) = next_elem;
3904 elem = prev_elem;
3907 else if (REG_P (SET_DEST (set))
3908 && REGNO (SET_DEST (set)) == (unsigned int) i)
3909 x = SET_SRC (set);
3910 else
3912 gcc_assert (REG_P (SET_SRC (set))
3913 && REGNO (SET_SRC (set)) == (unsigned int) i);
3914 x = SET_DEST (set);
3916 if (! function_invariant_p (x)
3917 || ! flag_pic
3918 /* A function invariant is often CONSTANT_P but may
3919 include a register. We promise to only pass
3920 CONSTANT_P objects to LEGITIMATE_PIC_OPERAND_P. */
3921 || (CONSTANT_P (x) && LEGITIMATE_PIC_OPERAND_P (x)))
3923 /* It can happen that a REG_EQUIV note contains a MEM
3924 that is not a legitimate memory operand. As later
3925 stages of reload assume that all addresses found in
3926 the lra_regno_equiv_* arrays were originally
3927 legitimate, we ignore such REG_EQUIV notes. */
3928 if (memory_operand (x, VOIDmode))
3930 ira_reg_equiv[i].defined_p = true;
3931 ira_reg_equiv[i].memory = x;
3932 continue;
3934 else if (function_invariant_p (x))
3936 enum machine_mode mode;
3938 mode = GET_MODE (SET_DEST (set));
3939 if (GET_CODE (x) == PLUS
3940 || x == frame_pointer_rtx || x == arg_pointer_rtx)
3941 /* This is PLUS of frame pointer and a constant,
3942 or fp, or argp. */
3943 ira_reg_equiv[i].invariant = x;
3944 else if (targetm.legitimate_constant_p (mode, x))
3945 ira_reg_equiv[i].constant = x;
3946 else
3948 ira_reg_equiv[i].memory = force_const_mem (mode, x);
3949 if (ira_reg_equiv[i].memory == NULL_RTX)
3951 ira_reg_equiv[i].defined_p = false;
3952 ira_reg_equiv[i].init_insns = NULL;
3953 break;
3956 ira_reg_equiv[i].defined_p = true;
3957 continue;
3961 ira_reg_equiv[i].defined_p = false;
3962 ira_reg_equiv[i].init_insns = NULL;
3963 break;
3969 /* Print chain C to FILE. */
3970 static void
3971 print_insn_chain (FILE *file, struct insn_chain *c)
3973 fprintf (file, "insn=%d, ", INSN_UID (c->insn));
3974 bitmap_print (file, &c->live_throughout, "live_throughout: ", ", ");
3975 bitmap_print (file, &c->dead_or_set, "dead_or_set: ", "\n");
3979 /* Print all reload_insn_chains to FILE. */
3980 static void
3981 print_insn_chains (FILE *file)
3983 struct insn_chain *c;
3984 for (c = reload_insn_chain; c ; c = c->next)
3985 print_insn_chain (file, c);
3988 /* Return true if pseudo REGNO should be added to set live_throughout
3989 or dead_or_set of the insn chains for reload consideration. */
3990 static bool
3991 pseudo_for_reload_consideration_p (int regno)
3993 /* Consider spilled pseudos too for IRA because they still have a
3994 chance to get hard-registers in the reload when IRA is used. */
3995 return (reg_renumber[regno] >= 0 || ira_conflicts_p);
3998 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
3999 REG to the number of nregs, and INIT_VALUE to get the
4000 initialization. ALLOCNUM need not be the regno of REG. */
4001 static void
4002 init_live_subregs (bool init_value, sbitmap *live_subregs,
4003 bitmap live_subregs_used, int allocnum, rtx reg)
4005 unsigned int regno = REGNO (SUBREG_REG (reg));
4006 int size = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno]));
4008 gcc_assert (size > 0);
4010 /* Been there, done that. */
4011 if (bitmap_bit_p (live_subregs_used, allocnum))
4012 return;
4014 /* Create a new one. */
4015 if (live_subregs[allocnum] == NULL)
4016 live_subregs[allocnum] = sbitmap_alloc (size);
4018 /* If the entire reg was live before blasting into subregs, we need
4019 to init all of the subregs to ones else init to 0. */
4020 if (init_value)
4021 bitmap_ones (live_subregs[allocnum]);
4022 else
4023 bitmap_clear (live_subregs[allocnum]);
4025 bitmap_set_bit (live_subregs_used, allocnum);
4028 /* Walk the insns of the current function and build reload_insn_chain,
4029 and record register life information. */
4030 static void
4031 build_insn_chain (void)
4033 unsigned int i;
4034 struct insn_chain **p = &reload_insn_chain;
4035 basic_block bb;
4036 struct insn_chain *c = NULL;
4037 struct insn_chain *next = NULL;
4038 bitmap live_relevant_regs = BITMAP_ALLOC (NULL);
4039 bitmap elim_regset = BITMAP_ALLOC (NULL);
4040 /* live_subregs is a vector used to keep accurate information about
4041 which hardregs are live in multiword pseudos. live_subregs and
4042 live_subregs_used are indexed by pseudo number. The live_subreg
4043 entry for a particular pseudo is only used if the corresponding
4044 element is non zero in live_subregs_used. The sbitmap size of
4045 live_subreg[allocno] is number of bytes that the pseudo can
4046 occupy. */
4047 sbitmap *live_subregs = XCNEWVEC (sbitmap, max_regno);
4048 bitmap live_subregs_used = BITMAP_ALLOC (NULL);
4050 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4051 if (TEST_HARD_REG_BIT (eliminable_regset, i))
4052 bitmap_set_bit (elim_regset, i);
4053 FOR_EACH_BB_REVERSE_FN (bb, cfun)
4055 bitmap_iterator bi;
4056 rtx_insn *insn;
4058 CLEAR_REG_SET (live_relevant_regs);
4059 bitmap_clear (live_subregs_used);
4061 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb), 0, i, bi)
4063 if (i >= FIRST_PSEUDO_REGISTER)
4064 break;
4065 bitmap_set_bit (live_relevant_regs, i);
4068 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb),
4069 FIRST_PSEUDO_REGISTER, i, bi)
4071 if (pseudo_for_reload_consideration_p (i))
4072 bitmap_set_bit (live_relevant_regs, i);
4075 FOR_BB_INSNS_REVERSE (bb, insn)
4077 if (!NOTE_P (insn) && !BARRIER_P (insn))
4079 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4080 df_ref def, use;
4082 c = new_insn_chain ();
4083 c->next = next;
4084 next = c;
4085 *p = c;
4086 p = &c->prev;
4088 c->insn = insn;
4089 c->block = bb->index;
4091 if (NONDEBUG_INSN_P (insn))
4092 FOR_EACH_INSN_INFO_DEF (def, insn_info)
4094 unsigned int regno = DF_REF_REGNO (def);
4096 /* Ignore may clobbers because these are generated
4097 from calls. However, every other kind of def is
4098 added to dead_or_set. */
4099 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
4101 if (regno < FIRST_PSEUDO_REGISTER)
4103 if (!fixed_regs[regno])
4104 bitmap_set_bit (&c->dead_or_set, regno);
4106 else if (pseudo_for_reload_consideration_p (regno))
4107 bitmap_set_bit (&c->dead_or_set, regno);
4110 if ((regno < FIRST_PSEUDO_REGISTER
4111 || reg_renumber[regno] >= 0
4112 || ira_conflicts_p)
4113 && (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)))
4115 rtx reg = DF_REF_REG (def);
4117 /* We can model subregs, but not if they are
4118 wrapped in ZERO_EXTRACTS. */
4119 if (GET_CODE (reg) == SUBREG
4120 && !DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT))
4122 unsigned int start = SUBREG_BYTE (reg);
4123 unsigned int last = start
4124 + GET_MODE_SIZE (GET_MODE (reg));
4126 init_live_subregs
4127 (bitmap_bit_p (live_relevant_regs, regno),
4128 live_subregs, live_subregs_used, regno, reg);
4130 if (!DF_REF_FLAGS_IS_SET
4131 (def, DF_REF_STRICT_LOW_PART))
4133 /* Expand the range to cover entire words.
4134 Bytes added here are "don't care". */
4135 start
4136 = start / UNITS_PER_WORD * UNITS_PER_WORD;
4137 last = ((last + UNITS_PER_WORD - 1)
4138 / UNITS_PER_WORD * UNITS_PER_WORD);
4141 /* Ignore the paradoxical bits. */
4142 if (last > SBITMAP_SIZE (live_subregs[regno]))
4143 last = SBITMAP_SIZE (live_subregs[regno]);
4145 while (start < last)
4147 bitmap_clear_bit (live_subregs[regno], start);
4148 start++;
4151 if (bitmap_empty_p (live_subregs[regno]))
4153 bitmap_clear_bit (live_subregs_used, regno);
4154 bitmap_clear_bit (live_relevant_regs, regno);
4156 else
4157 /* Set live_relevant_regs here because
4158 that bit has to be true to get us to
4159 look at the live_subregs fields. */
4160 bitmap_set_bit (live_relevant_regs, regno);
4162 else
4164 /* DF_REF_PARTIAL is generated for
4165 subregs, STRICT_LOW_PART, and
4166 ZERO_EXTRACT. We handle the subreg
4167 case above so here we have to keep from
4168 modeling the def as a killing def. */
4169 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL))
4171 bitmap_clear_bit (live_subregs_used, regno);
4172 bitmap_clear_bit (live_relevant_regs, regno);
4178 bitmap_and_compl_into (live_relevant_regs, elim_regset);
4179 bitmap_copy (&c->live_throughout, live_relevant_regs);
4181 if (NONDEBUG_INSN_P (insn))
4182 FOR_EACH_INSN_INFO_USE (use, insn_info)
4184 unsigned int regno = DF_REF_REGNO (use);
4185 rtx reg = DF_REF_REG (use);
4187 /* DF_REF_READ_WRITE on a use means that this use
4188 is fabricated from a def that is a partial set
4189 to a multiword reg. Here, we only model the
4190 subreg case that is not wrapped in ZERO_EXTRACT
4191 precisely so we do not need to look at the
4192 fabricated use. */
4193 if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE)
4194 && !DF_REF_FLAGS_IS_SET (use, DF_REF_ZERO_EXTRACT)
4195 && DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG))
4196 continue;
4198 /* Add the last use of each var to dead_or_set. */
4199 if (!bitmap_bit_p (live_relevant_regs, regno))
4201 if (regno < FIRST_PSEUDO_REGISTER)
4203 if (!fixed_regs[regno])
4204 bitmap_set_bit (&c->dead_or_set, regno);
4206 else if (pseudo_for_reload_consideration_p (regno))
4207 bitmap_set_bit (&c->dead_or_set, regno);
4210 if (regno < FIRST_PSEUDO_REGISTER
4211 || pseudo_for_reload_consideration_p (regno))
4213 if (GET_CODE (reg) == SUBREG
4214 && !DF_REF_FLAGS_IS_SET (use,
4215 DF_REF_SIGN_EXTRACT
4216 | DF_REF_ZERO_EXTRACT))
4218 unsigned int start = SUBREG_BYTE (reg);
4219 unsigned int last = start
4220 + GET_MODE_SIZE (GET_MODE (reg));
4222 init_live_subregs
4223 (bitmap_bit_p (live_relevant_regs, regno),
4224 live_subregs, live_subregs_used, regno, reg);
4226 /* Ignore the paradoxical bits. */
4227 if (last > SBITMAP_SIZE (live_subregs[regno]))
4228 last = SBITMAP_SIZE (live_subregs[regno]);
4230 while (start < last)
4232 bitmap_set_bit (live_subregs[regno], start);
4233 start++;
4236 else
4237 /* Resetting the live_subregs_used is
4238 effectively saying do not use the subregs
4239 because we are reading the whole
4240 pseudo. */
4241 bitmap_clear_bit (live_subregs_used, regno);
4242 bitmap_set_bit (live_relevant_regs, regno);
4248 /* FIXME!! The following code is a disaster. Reload needs to see the
4249 labels and jump tables that are just hanging out in between
4250 the basic blocks. See pr33676. */
4251 insn = BB_HEAD (bb);
4253 /* Skip over the barriers and cruft. */
4254 while (insn && (BARRIER_P (insn) || NOTE_P (insn)
4255 || BLOCK_FOR_INSN (insn) == bb))
4256 insn = PREV_INSN (insn);
4258 /* While we add anything except barriers and notes, the focus is
4259 to get the labels and jump tables into the
4260 reload_insn_chain. */
4261 while (insn)
4263 if (!NOTE_P (insn) && !BARRIER_P (insn))
4265 if (BLOCK_FOR_INSN (insn))
4266 break;
4268 c = new_insn_chain ();
4269 c->next = next;
4270 next = c;
4271 *p = c;
4272 p = &c->prev;
4274 /* The block makes no sense here, but it is what the old
4275 code did. */
4276 c->block = bb->index;
4277 c->insn = insn;
4278 bitmap_copy (&c->live_throughout, live_relevant_regs);
4280 insn = PREV_INSN (insn);
4284 reload_insn_chain = c;
4285 *p = NULL;
4287 for (i = 0; i < (unsigned int) max_regno; i++)
4288 if (live_subregs[i] != NULL)
4289 sbitmap_free (live_subregs[i]);
4290 free (live_subregs);
4291 BITMAP_FREE (live_subregs_used);
4292 BITMAP_FREE (live_relevant_regs);
4293 BITMAP_FREE (elim_regset);
4295 if (dump_file)
4296 print_insn_chains (dump_file);
4299 /* Examine the rtx found in *LOC, which is read or written to as determined
4300 by TYPE. Return false if we find a reason why an insn containing this
4301 rtx should not be moved (such as accesses to non-constant memory), true
4302 otherwise. */
4303 static bool
4304 rtx_moveable_p (rtx *loc, enum op_type type)
4306 const char *fmt;
4307 rtx x = *loc;
4308 enum rtx_code code = GET_CODE (x);
4309 int i, j;
4311 code = GET_CODE (x);
4312 switch (code)
4314 case CONST:
4315 CASE_CONST_ANY:
4316 case SYMBOL_REF:
4317 case LABEL_REF:
4318 return true;
4320 case PC:
4321 return type == OP_IN;
4323 case CC0:
4324 return false;
4326 case REG:
4327 if (x == frame_pointer_rtx)
4328 return true;
4329 if (HARD_REGISTER_P (x))
4330 return false;
4332 return true;
4334 case MEM:
4335 if (type == OP_IN && MEM_READONLY_P (x))
4336 return rtx_moveable_p (&XEXP (x, 0), OP_IN);
4337 return false;
4339 case SET:
4340 return (rtx_moveable_p (&SET_SRC (x), OP_IN)
4341 && rtx_moveable_p (&SET_DEST (x), OP_OUT));
4343 case STRICT_LOW_PART:
4344 return rtx_moveable_p (&XEXP (x, 0), OP_OUT);
4346 case ZERO_EXTRACT:
4347 case SIGN_EXTRACT:
4348 return (rtx_moveable_p (&XEXP (x, 0), type)
4349 && rtx_moveable_p (&XEXP (x, 1), OP_IN)
4350 && rtx_moveable_p (&XEXP (x, 2), OP_IN));
4352 case CLOBBER:
4353 return rtx_moveable_p (&SET_DEST (x), OP_OUT);
4355 default:
4356 break;
4359 fmt = GET_RTX_FORMAT (code);
4360 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4362 if (fmt[i] == 'e')
4364 if (!rtx_moveable_p (&XEXP (x, i), type))
4365 return false;
4367 else if (fmt[i] == 'E')
4368 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4370 if (!rtx_moveable_p (&XVECEXP (x, i, j), type))
4371 return false;
4374 return true;
4377 /* A wrapper around dominated_by_p, which uses the information in UID_LUID
4378 to give dominance relationships between two insns I1 and I2. */
4379 static bool
4380 insn_dominated_by_p (rtx i1, rtx i2, int *uid_luid)
4382 basic_block bb1 = BLOCK_FOR_INSN (i1);
4383 basic_block bb2 = BLOCK_FOR_INSN (i2);
4385 if (bb1 == bb2)
4386 return uid_luid[INSN_UID (i2)] < uid_luid[INSN_UID (i1)];
4387 return dominated_by_p (CDI_DOMINATORS, bb1, bb2);
4390 /* Record the range of register numbers added by find_moveable_pseudos. */
4391 int first_moveable_pseudo, last_moveable_pseudo;
4393 /* These two vectors hold data for every register added by
4394 find_movable_pseudos, with index 0 holding data for the
4395 first_moveable_pseudo. */
4396 /* The original home register. */
4397 static vec<rtx> pseudo_replaced_reg;
4399 /* Look for instances where we have an instruction that is known to increase
4400 register pressure, and whose result is not used immediately. If it is
4401 possible to move the instruction downwards to just before its first use,
4402 split its lifetime into two ranges. We create a new pseudo to compute the
4403 value, and emit a move instruction just before the first use. If, after
4404 register allocation, the new pseudo remains unallocated, the function
4405 move_unallocated_pseudos then deletes the move instruction and places
4406 the computation just before the first use.
4408 Such a move is safe and profitable if all the input registers remain live
4409 and unchanged between the original computation and its first use. In such
4410 a situation, the computation is known to increase register pressure, and
4411 moving it is known to at least not worsen it.
4413 We restrict moves to only those cases where a register remains unallocated,
4414 in order to avoid interfering too much with the instruction schedule. As
4415 an exception, we may move insns which only modify their input register
4416 (typically induction variables), as this increases the freedom for our
4417 intended transformation, and does not limit the second instruction
4418 scheduler pass. */
4420 static void
4421 find_moveable_pseudos (void)
4423 unsigned i;
4424 int max_regs = max_reg_num ();
4425 int max_uid = get_max_uid ();
4426 basic_block bb;
4427 int *uid_luid = XNEWVEC (int, max_uid);
4428 rtx_insn **closest_uses = XNEWVEC (rtx_insn *, max_regs);
4429 /* A set of registers which are live but not modified throughout a block. */
4430 bitmap_head *bb_transp_live = XNEWVEC (bitmap_head,
4431 last_basic_block_for_fn (cfun));
4432 /* A set of registers which only exist in a given basic block. */
4433 bitmap_head *bb_local = XNEWVEC (bitmap_head,
4434 last_basic_block_for_fn (cfun));
4435 /* A set of registers which are set once, in an instruction that can be
4436 moved freely downwards, but are otherwise transparent to a block. */
4437 bitmap_head *bb_moveable_reg_sets = XNEWVEC (bitmap_head,
4438 last_basic_block_for_fn (cfun));
4439 bitmap_head live, used, set, interesting, unusable_as_input;
4440 bitmap_iterator bi;
4441 bitmap_initialize (&interesting, 0);
4443 first_moveable_pseudo = max_regs;
4444 pseudo_replaced_reg.release ();
4445 pseudo_replaced_reg.safe_grow_cleared (max_regs);
4447 df_analyze ();
4448 calculate_dominance_info (CDI_DOMINATORS);
4450 i = 0;
4451 bitmap_initialize (&live, 0);
4452 bitmap_initialize (&used, 0);
4453 bitmap_initialize (&set, 0);
4454 bitmap_initialize (&unusable_as_input, 0);
4455 FOR_EACH_BB_FN (bb, cfun)
4457 rtx_insn *insn;
4458 bitmap transp = bb_transp_live + bb->index;
4459 bitmap moveable = bb_moveable_reg_sets + bb->index;
4460 bitmap local = bb_local + bb->index;
4462 bitmap_initialize (local, 0);
4463 bitmap_initialize (transp, 0);
4464 bitmap_initialize (moveable, 0);
4465 bitmap_copy (&live, df_get_live_out (bb));
4466 bitmap_and_into (&live, df_get_live_in (bb));
4467 bitmap_copy (transp, &live);
4468 bitmap_clear (moveable);
4469 bitmap_clear (&live);
4470 bitmap_clear (&used);
4471 bitmap_clear (&set);
4472 FOR_BB_INSNS (bb, insn)
4473 if (NONDEBUG_INSN_P (insn))
4475 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4476 df_ref def, use;
4478 uid_luid[INSN_UID (insn)] = i++;
4480 def = df_single_def (insn_info);
4481 use = df_single_use (insn_info);
4482 if (use
4483 && def
4484 && DF_REF_REGNO (use) == DF_REF_REGNO (def)
4485 && !bitmap_bit_p (&set, DF_REF_REGNO (use))
4486 && rtx_moveable_p (&PATTERN (insn), OP_IN))
4488 unsigned regno = DF_REF_REGNO (use);
4489 bitmap_set_bit (moveable, regno);
4490 bitmap_set_bit (&set, regno);
4491 bitmap_set_bit (&used, regno);
4492 bitmap_clear_bit (transp, regno);
4493 continue;
4495 FOR_EACH_INSN_INFO_USE (use, insn_info)
4497 unsigned regno = DF_REF_REGNO (use);
4498 bitmap_set_bit (&used, regno);
4499 if (bitmap_clear_bit (moveable, regno))
4500 bitmap_clear_bit (transp, regno);
4503 FOR_EACH_INSN_INFO_DEF (def, insn_info)
4505 unsigned regno = DF_REF_REGNO (def);
4506 bitmap_set_bit (&set, regno);
4507 bitmap_clear_bit (transp, regno);
4508 bitmap_clear_bit (moveable, regno);
4513 bitmap_clear (&live);
4514 bitmap_clear (&used);
4515 bitmap_clear (&set);
4517 FOR_EACH_BB_FN (bb, cfun)
4519 bitmap local = bb_local + bb->index;
4520 rtx_insn *insn;
4522 FOR_BB_INSNS (bb, insn)
4523 if (NONDEBUG_INSN_P (insn))
4525 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4526 rtx_insn *def_insn;
4527 rtx closest_use, note;
4528 df_ref def, use;
4529 unsigned regno;
4530 bool all_dominated, all_local;
4531 enum machine_mode mode;
4533 def = df_single_def (insn_info);
4534 /* There must be exactly one def in this insn. */
4535 if (!def || !single_set (insn))
4536 continue;
4537 /* This must be the only definition of the reg. We also limit
4538 which modes we deal with so that we can assume we can generate
4539 move instructions. */
4540 regno = DF_REF_REGNO (def);
4541 mode = GET_MODE (DF_REF_REG (def));
4542 if (DF_REG_DEF_COUNT (regno) != 1
4543 || !DF_REF_INSN_INFO (def)
4544 || HARD_REGISTER_NUM_P (regno)
4545 || DF_REG_EQ_USE_COUNT (regno) > 0
4546 || (!INTEGRAL_MODE_P (mode) && !FLOAT_MODE_P (mode)))
4547 continue;
4548 def_insn = DF_REF_INSN (def);
4550 for (note = REG_NOTES (def_insn); note; note = XEXP (note, 1))
4551 if (REG_NOTE_KIND (note) == REG_EQUIV && MEM_P (XEXP (note, 0)))
4552 break;
4554 if (note)
4556 if (dump_file)
4557 fprintf (dump_file, "Ignoring reg %d, has equiv memory\n",
4558 regno);
4559 bitmap_set_bit (&unusable_as_input, regno);
4560 continue;
4563 use = DF_REG_USE_CHAIN (regno);
4564 all_dominated = true;
4565 all_local = true;
4566 closest_use = NULL_RTX;
4567 for (; use; use = DF_REF_NEXT_REG (use))
4569 rtx_insn *insn;
4570 if (!DF_REF_INSN_INFO (use))
4572 all_dominated = false;
4573 all_local = false;
4574 break;
4576 insn = DF_REF_INSN (use);
4577 if (DEBUG_INSN_P (insn))
4578 continue;
4579 if (BLOCK_FOR_INSN (insn) != BLOCK_FOR_INSN (def_insn))
4580 all_local = false;
4581 if (!insn_dominated_by_p (insn, def_insn, uid_luid))
4582 all_dominated = false;
4583 if (closest_use != insn && closest_use != const0_rtx)
4585 if (closest_use == NULL_RTX)
4586 closest_use = insn;
4587 else if (insn_dominated_by_p (closest_use, insn, uid_luid))
4588 closest_use = insn;
4589 else if (!insn_dominated_by_p (insn, closest_use, uid_luid))
4590 closest_use = const0_rtx;
4593 if (!all_dominated)
4595 if (dump_file)
4596 fprintf (dump_file, "Reg %d not all uses dominated by set\n",
4597 regno);
4598 continue;
4600 if (all_local)
4601 bitmap_set_bit (local, regno);
4602 if (closest_use == const0_rtx || closest_use == NULL
4603 || next_nonnote_nondebug_insn (def_insn) == closest_use)
4605 if (dump_file)
4606 fprintf (dump_file, "Reg %d uninteresting%s\n", regno,
4607 closest_use == const0_rtx || closest_use == NULL
4608 ? " (no unique first use)" : "");
4609 continue;
4611 #ifdef HAVE_cc0
4612 if (reg_referenced_p (cc0_rtx, PATTERN (closest_use)))
4614 if (dump_file)
4615 fprintf (dump_file, "Reg %d: closest user uses cc0\n",
4616 regno);
4617 continue;
4619 #endif
4620 bitmap_set_bit (&interesting, regno);
4621 /* If we get here, we know closest_use is a non-NULL insn
4622 (as opposed to const_0_rtx). */
4623 closest_uses[regno] = as_a <rtx_insn *> (closest_use);
4625 if (dump_file && (all_local || all_dominated))
4627 fprintf (dump_file, "Reg %u:", regno);
4628 if (all_local)
4629 fprintf (dump_file, " local to bb %d", bb->index);
4630 if (all_dominated)
4631 fprintf (dump_file, " def dominates all uses");
4632 if (closest_use != const0_rtx)
4633 fprintf (dump_file, " has unique first use");
4634 fputs ("\n", dump_file);
4639 EXECUTE_IF_SET_IN_BITMAP (&interesting, 0, i, bi)
4641 df_ref def = DF_REG_DEF_CHAIN (i);
4642 rtx_insn *def_insn = DF_REF_INSN (def);
4643 basic_block def_block = BLOCK_FOR_INSN (def_insn);
4644 bitmap def_bb_local = bb_local + def_block->index;
4645 bitmap def_bb_moveable = bb_moveable_reg_sets + def_block->index;
4646 bitmap def_bb_transp = bb_transp_live + def_block->index;
4647 bool local_to_bb_p = bitmap_bit_p (def_bb_local, i);
4648 rtx_insn *use_insn = closest_uses[i];
4649 df_ref use;
4650 bool all_ok = true;
4651 bool all_transp = true;
4653 if (!REG_P (DF_REF_REG (def)))
4654 continue;
4656 if (!local_to_bb_p)
4658 if (dump_file)
4659 fprintf (dump_file, "Reg %u not local to one basic block\n",
4661 continue;
4663 if (reg_equiv_init (i) != NULL_RTX)
4665 if (dump_file)
4666 fprintf (dump_file, "Ignoring reg %u with equiv init insn\n",
4668 continue;
4670 if (!rtx_moveable_p (&PATTERN (def_insn), OP_IN))
4672 if (dump_file)
4673 fprintf (dump_file, "Found def insn %d for %d to be not moveable\n",
4674 INSN_UID (def_insn), i);
4675 continue;
4677 if (dump_file)
4678 fprintf (dump_file, "Examining insn %d, def for %d\n",
4679 INSN_UID (def_insn), i);
4680 FOR_EACH_INSN_USE (use, def_insn)
4682 unsigned regno = DF_REF_REGNO (use);
4683 if (bitmap_bit_p (&unusable_as_input, regno))
4685 all_ok = false;
4686 if (dump_file)
4687 fprintf (dump_file, " found unusable input reg %u.\n", regno);
4688 break;
4690 if (!bitmap_bit_p (def_bb_transp, regno))
4692 if (bitmap_bit_p (def_bb_moveable, regno)
4693 && !control_flow_insn_p (use_insn)
4694 #ifdef HAVE_cc0
4695 && !sets_cc0_p (use_insn)
4696 #endif
4699 if (modified_between_p (DF_REF_REG (use), def_insn, use_insn))
4701 rtx_insn *x = NEXT_INSN (def_insn);
4702 while (!modified_in_p (DF_REF_REG (use), x))
4704 gcc_assert (x != use_insn);
4705 x = NEXT_INSN (x);
4707 if (dump_file)
4708 fprintf (dump_file, " input reg %u modified but insn %d moveable\n",
4709 regno, INSN_UID (x));
4710 emit_insn_after (PATTERN (x), use_insn);
4711 set_insn_deleted (x);
4713 else
4715 if (dump_file)
4716 fprintf (dump_file, " input reg %u modified between def and use\n",
4717 regno);
4718 all_transp = false;
4721 else
4722 all_transp = false;
4725 if (!all_ok)
4726 continue;
4727 if (!dbg_cnt (ira_move))
4728 break;
4729 if (dump_file)
4730 fprintf (dump_file, " all ok%s\n", all_transp ? " and transp" : "");
4732 if (all_transp)
4734 rtx def_reg = DF_REF_REG (def);
4735 rtx newreg = ira_create_new_reg (def_reg);
4736 if (validate_change (def_insn, DF_REF_REAL_LOC (def), newreg, 0))
4738 unsigned nregno = REGNO (newreg);
4739 emit_insn_before (gen_move_insn (def_reg, newreg), use_insn);
4740 nregno -= max_regs;
4741 pseudo_replaced_reg[nregno] = def_reg;
4746 FOR_EACH_BB_FN (bb, cfun)
4748 bitmap_clear (bb_local + bb->index);
4749 bitmap_clear (bb_transp_live + bb->index);
4750 bitmap_clear (bb_moveable_reg_sets + bb->index);
4752 bitmap_clear (&interesting);
4753 bitmap_clear (&unusable_as_input);
4754 free (uid_luid);
4755 free (closest_uses);
4756 free (bb_local);
4757 free (bb_transp_live);
4758 free (bb_moveable_reg_sets);
4760 last_moveable_pseudo = max_reg_num ();
4762 fix_reg_equiv_init ();
4763 expand_reg_info ();
4764 regstat_free_n_sets_and_refs ();
4765 regstat_free_ri ();
4766 regstat_init_n_sets_and_refs ();
4767 regstat_compute_ri ();
4768 free_dominance_info (CDI_DOMINATORS);
4771 /* If SET pattern SET is an assignment from a hard register to a pseudo which
4772 is live at CALL_DOM (if non-NULL, otherwise this check is omitted), return
4773 the destination. Otherwise return NULL. */
4775 static rtx
4776 interesting_dest_for_shprep_1 (rtx set, basic_block call_dom)
4778 rtx src = SET_SRC (set);
4779 rtx dest = SET_DEST (set);
4780 if (!REG_P (src) || !HARD_REGISTER_P (src)
4781 || !REG_P (dest) || HARD_REGISTER_P (dest)
4782 || (call_dom && !bitmap_bit_p (df_get_live_in (call_dom), REGNO (dest))))
4783 return NULL;
4784 return dest;
4787 /* If insn is interesting for parameter range-splitting shrink-wrapping
4788 preparation, i.e. it is a single set from a hard register to a pseudo, which
4789 is live at CALL_DOM (if non-NULL, otherwise this check is omitted), or a
4790 parallel statement with only one such statement, return the destination.
4791 Otherwise return NULL. */
4793 static rtx
4794 interesting_dest_for_shprep (rtx_insn *insn, basic_block call_dom)
4796 if (!INSN_P (insn))
4797 return NULL;
4798 rtx pat = PATTERN (insn);
4799 if (GET_CODE (pat) == SET)
4800 return interesting_dest_for_shprep_1 (pat, call_dom);
4802 if (GET_CODE (pat) != PARALLEL)
4803 return NULL;
4804 rtx ret = NULL;
4805 for (int i = 0; i < XVECLEN (pat, 0); i++)
4807 rtx sub = XVECEXP (pat, 0, i);
4808 if (GET_CODE (sub) == USE || GET_CODE (sub) == CLOBBER)
4809 continue;
4810 if (GET_CODE (sub) != SET
4811 || side_effects_p (sub))
4812 return NULL;
4813 rtx dest = interesting_dest_for_shprep_1 (sub, call_dom);
4814 if (dest && ret)
4815 return NULL;
4816 if (dest)
4817 ret = dest;
4819 return ret;
4822 /* Split live ranges of pseudos that are loaded from hard registers in the
4823 first BB in a BB that dominates all non-sibling call if such a BB can be
4824 found and is not in a loop. Return true if the function has made any
4825 changes. */
4827 static bool
4828 split_live_ranges_for_shrink_wrap (void)
4830 basic_block bb, call_dom = NULL;
4831 basic_block first = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
4832 rtx_insn *insn, *last_interesting_insn = NULL;
4833 bitmap_head need_new, reachable;
4834 vec<basic_block> queue;
4836 if (!SHRINK_WRAPPING_ENABLED)
4837 return false;
4839 bitmap_initialize (&need_new, 0);
4840 bitmap_initialize (&reachable, 0);
4841 queue.create (n_basic_blocks_for_fn (cfun));
4843 FOR_EACH_BB_FN (bb, cfun)
4844 FOR_BB_INSNS (bb, insn)
4845 if (CALL_P (insn) && !SIBLING_CALL_P (insn))
4847 if (bb == first)
4849 bitmap_clear (&need_new);
4850 bitmap_clear (&reachable);
4851 queue.release ();
4852 return false;
4855 bitmap_set_bit (&need_new, bb->index);
4856 bitmap_set_bit (&reachable, bb->index);
4857 queue.quick_push (bb);
4858 break;
4861 if (queue.is_empty ())
4863 bitmap_clear (&need_new);
4864 bitmap_clear (&reachable);
4865 queue.release ();
4866 return false;
4869 while (!queue.is_empty ())
4871 edge e;
4872 edge_iterator ei;
4874 bb = queue.pop ();
4875 FOR_EACH_EDGE (e, ei, bb->succs)
4876 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
4877 && bitmap_set_bit (&reachable, e->dest->index))
4878 queue.quick_push (e->dest);
4880 queue.release ();
4882 FOR_BB_INSNS (first, insn)
4884 rtx dest = interesting_dest_for_shprep (insn, NULL);
4885 if (!dest)
4886 continue;
4888 if (DF_REG_DEF_COUNT (REGNO (dest)) > 1)
4890 bitmap_clear (&need_new);
4891 bitmap_clear (&reachable);
4892 return false;
4895 for (df_ref use = DF_REG_USE_CHAIN (REGNO(dest));
4896 use;
4897 use = DF_REF_NEXT_REG (use))
4899 int ubbi = DF_REF_BB (use)->index;
4900 if (bitmap_bit_p (&reachable, ubbi))
4901 bitmap_set_bit (&need_new, ubbi);
4903 last_interesting_insn = insn;
4906 bitmap_clear (&reachable);
4907 if (!last_interesting_insn)
4909 bitmap_clear (&need_new);
4910 return false;
4913 call_dom = nearest_common_dominator_for_set (CDI_DOMINATORS, &need_new);
4914 bitmap_clear (&need_new);
4915 if (call_dom == first)
4916 return false;
4918 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
4919 while (bb_loop_depth (call_dom) > 0)
4920 call_dom = get_immediate_dominator (CDI_DOMINATORS, call_dom);
4921 loop_optimizer_finalize ();
4923 if (call_dom == first)
4924 return false;
4926 calculate_dominance_info (CDI_POST_DOMINATORS);
4927 if (dominated_by_p (CDI_POST_DOMINATORS, first, call_dom))
4929 free_dominance_info (CDI_POST_DOMINATORS);
4930 return false;
4932 free_dominance_info (CDI_POST_DOMINATORS);
4934 if (dump_file)
4935 fprintf (dump_file, "Will split live ranges of parameters at BB %i\n",
4936 call_dom->index);
4938 bool ret = false;
4939 FOR_BB_INSNS (first, insn)
4941 rtx dest = interesting_dest_for_shprep (insn, call_dom);
4942 if (!dest || dest == pic_offset_table_rtx)
4943 continue;
4945 rtx newreg = NULL_RTX;
4946 df_ref use, next;
4947 for (use = DF_REG_USE_CHAIN (REGNO (dest)); use; use = next)
4949 rtx_insn *uin = DF_REF_INSN (use);
4950 next = DF_REF_NEXT_REG (use);
4952 basic_block ubb = BLOCK_FOR_INSN (uin);
4953 if (ubb == call_dom
4954 || dominated_by_p (CDI_DOMINATORS, ubb, call_dom))
4956 if (!newreg)
4957 newreg = ira_create_new_reg (dest);
4958 validate_change (uin, DF_REF_REAL_LOC (use), newreg, true);
4962 if (newreg)
4964 rtx new_move = gen_move_insn (newreg, dest);
4965 emit_insn_after (new_move, bb_note (call_dom));
4966 if (dump_file)
4968 fprintf (dump_file, "Split live-range of register ");
4969 print_rtl_single (dump_file, dest);
4971 ret = true;
4974 if (insn == last_interesting_insn)
4975 break;
4977 apply_change_group ();
4978 return ret;
4981 /* Perform the second half of the transformation started in
4982 find_moveable_pseudos. We look for instances where the newly introduced
4983 pseudo remains unallocated, and remove it by moving the definition to
4984 just before its use, replacing the move instruction generated by
4985 find_moveable_pseudos. */
4986 static void
4987 move_unallocated_pseudos (void)
4989 int i;
4990 for (i = first_moveable_pseudo; i < last_moveable_pseudo; i++)
4991 if (reg_renumber[i] < 0)
4993 int idx = i - first_moveable_pseudo;
4994 rtx other_reg = pseudo_replaced_reg[idx];
4995 rtx_insn *def_insn = DF_REF_INSN (DF_REG_DEF_CHAIN (i));
4996 /* The use must follow all definitions of OTHER_REG, so we can
4997 insert the new definition immediately after any of them. */
4998 df_ref other_def = DF_REG_DEF_CHAIN (REGNO (other_reg));
4999 rtx_insn *move_insn = DF_REF_INSN (other_def);
5000 rtx_insn *newinsn = emit_insn_after (PATTERN (def_insn), move_insn);
5001 rtx set;
5002 int success;
5004 if (dump_file)
5005 fprintf (dump_file, "moving def of %d (insn %d now) ",
5006 REGNO (other_reg), INSN_UID (def_insn));
5008 delete_insn (move_insn);
5009 while ((other_def = DF_REG_DEF_CHAIN (REGNO (other_reg))))
5010 delete_insn (DF_REF_INSN (other_def));
5011 delete_insn (def_insn);
5013 set = single_set (newinsn);
5014 success = validate_change (newinsn, &SET_DEST (set), other_reg, 0);
5015 gcc_assert (success);
5016 if (dump_file)
5017 fprintf (dump_file, " %d) rather than keep unallocated replacement %d\n",
5018 INSN_UID (newinsn), i);
5019 SET_REG_N_REFS (i, 0);
5023 /* If the backend knows where to allocate pseudos for hard
5024 register initial values, register these allocations now. */
5025 static void
5026 allocate_initial_values (void)
5028 if (targetm.allocate_initial_value)
5030 rtx hreg, preg, x;
5031 int i, regno;
5033 for (i = 0; HARD_REGISTER_NUM_P (i); i++)
5035 if (! initial_value_entry (i, &hreg, &preg))
5036 break;
5038 x = targetm.allocate_initial_value (hreg);
5039 regno = REGNO (preg);
5040 if (x && REG_N_SETS (regno) <= 1)
5042 if (MEM_P (x))
5043 reg_equiv_memory_loc (regno) = x;
5044 else
5046 basic_block bb;
5047 int new_regno;
5049 gcc_assert (REG_P (x));
5050 new_regno = REGNO (x);
5051 reg_renumber[regno] = new_regno;
5052 /* Poke the regno right into regno_reg_rtx so that even
5053 fixed regs are accepted. */
5054 SET_REGNO (preg, new_regno);
5055 /* Update global register liveness information. */
5056 FOR_EACH_BB_FN (bb, cfun)
5058 if (REGNO_REG_SET_P (df_get_live_in (bb), regno))
5059 SET_REGNO_REG_SET (df_get_live_in (bb), new_regno);
5060 if (REGNO_REG_SET_P (df_get_live_out (bb), regno))
5061 SET_REGNO_REG_SET (df_get_live_out (bb), new_regno);
5067 gcc_checking_assert (! initial_value_entry (FIRST_PSEUDO_REGISTER,
5068 &hreg, &preg));
5073 /* True when we use LRA instead of reload pass for the current
5074 function. */
5075 bool ira_use_lra_p;
5077 /* True if we have allocno conflicts. It is false for non-optimized
5078 mode or when the conflict table is too big. */
5079 bool ira_conflicts_p;
5081 /* Saved between IRA and reload. */
5082 static int saved_flag_ira_share_spill_slots;
5084 /* This is the main entry of IRA. */
5085 static void
5086 ira (FILE *f)
5088 bool loops_p;
5089 int ira_max_point_before_emit;
5090 int rebuild_p;
5091 bool saved_flag_caller_saves = flag_caller_saves;
5092 enum ira_region saved_flag_ira_region = flag_ira_region;
5094 /* Perform target specific PIC register initialization. */
5095 targetm.init_pic_reg ();
5097 ira_conflicts_p = optimize > 0;
5099 ira_use_lra_p = targetm.lra_p ();
5100 /* If there are too many pseudos and/or basic blocks (e.g. 10K
5101 pseudos and 10K blocks or 100K pseudos and 1K blocks), we will
5102 use simplified and faster algorithms in LRA. */
5103 lra_simple_p
5104 = (ira_use_lra_p
5105 && max_reg_num () >= (1 << 26) / last_basic_block_for_fn (cfun));
5106 if (lra_simple_p)
5108 /* It permits to skip live range splitting in LRA. */
5109 flag_caller_saves = false;
5110 /* There is no sense to do regional allocation when we use
5111 simplified LRA. */
5112 flag_ira_region = IRA_REGION_ONE;
5113 ira_conflicts_p = false;
5116 #ifndef IRA_NO_OBSTACK
5117 gcc_obstack_init (&ira_obstack);
5118 #endif
5119 bitmap_obstack_initialize (&ira_bitmap_obstack);
5121 /* LRA uses its own infrastructure to handle caller save registers. */
5122 if (flag_caller_saves && !ira_use_lra_p)
5123 init_caller_save ();
5125 if (flag_ira_verbose < 10)
5127 internal_flag_ira_verbose = flag_ira_verbose;
5128 ira_dump_file = f;
5130 else
5132 internal_flag_ira_verbose = flag_ira_verbose - 10;
5133 ira_dump_file = stderr;
5136 setup_prohibited_mode_move_regs ();
5137 decrease_live_ranges_number ();
5138 df_note_add_problem ();
5140 /* DF_LIVE can't be used in the register allocator, too many other
5141 parts of the compiler depend on using the "classic" liveness
5142 interpretation of the DF_LR problem. See PR38711.
5143 Remove the problem, so that we don't spend time updating it in
5144 any of the df_analyze() calls during IRA/LRA. */
5145 if (optimize > 1)
5146 df_remove_problem (df_live);
5147 gcc_checking_assert (df_live == NULL);
5149 #ifdef ENABLE_CHECKING
5150 df->changeable_flags |= DF_VERIFY_SCHEDULED;
5151 #endif
5152 df_analyze ();
5154 init_reg_equiv ();
5155 if (ira_conflicts_p)
5157 calculate_dominance_info (CDI_DOMINATORS);
5159 if (split_live_ranges_for_shrink_wrap ())
5160 df_analyze ();
5162 free_dominance_info (CDI_DOMINATORS);
5165 df_clear_flags (DF_NO_INSN_RESCAN);
5167 regstat_init_n_sets_and_refs ();
5168 regstat_compute_ri ();
5170 /* If we are not optimizing, then this is the only place before
5171 register allocation where dataflow is done. And that is needed
5172 to generate these warnings. */
5173 if (warn_clobbered)
5174 generate_setjmp_warnings ();
5176 /* Determine if the current function is a leaf before running IRA
5177 since this can impact optimizations done by the prologue and
5178 epilogue thus changing register elimination offsets. */
5179 crtl->is_leaf = leaf_function_p ();
5181 if (resize_reg_info () && flag_ira_loop_pressure)
5182 ira_set_pseudo_classes (true, ira_dump_file);
5184 rebuild_p = update_equiv_regs ();
5185 setup_reg_equiv ();
5186 setup_reg_equiv_init ();
5188 if (optimize && rebuild_p)
5190 timevar_push (TV_JUMP);
5191 rebuild_jump_labels (get_insns ());
5192 if (purge_all_dead_edges ())
5193 delete_unreachable_blocks ();
5194 timevar_pop (TV_JUMP);
5197 allocated_reg_info_size = max_reg_num ();
5199 if (delete_trivially_dead_insns (get_insns (), max_reg_num ()))
5200 df_analyze ();
5202 /* It is not worth to do such improvement when we use a simple
5203 allocation because of -O0 usage or because the function is too
5204 big. */
5205 if (ira_conflicts_p)
5206 find_moveable_pseudos ();
5208 max_regno_before_ira = max_reg_num ();
5209 ira_setup_eliminable_regset ();
5211 ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
5212 ira_load_cost = ira_store_cost = ira_shuffle_cost = 0;
5213 ira_move_loops_num = ira_additional_jumps_num = 0;
5215 ira_assert (current_loops == NULL);
5216 if (flag_ira_region == IRA_REGION_ALL || flag_ira_region == IRA_REGION_MIXED)
5217 loop_optimizer_init (AVOID_CFG_MODIFICATIONS | LOOPS_HAVE_RECORDED_EXITS);
5219 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
5220 fprintf (ira_dump_file, "Building IRA IR\n");
5221 loops_p = ira_build ();
5223 ira_assert (ira_conflicts_p || !loops_p);
5225 saved_flag_ira_share_spill_slots = flag_ira_share_spill_slots;
5226 if (too_high_register_pressure_p () || cfun->calls_setjmp)
5227 /* It is just wasting compiler's time to pack spilled pseudos into
5228 stack slots in this case -- prohibit it. We also do this if
5229 there is setjmp call because a variable not modified between
5230 setjmp and longjmp the compiler is required to preserve its
5231 value and sharing slots does not guarantee it. */
5232 flag_ira_share_spill_slots = FALSE;
5234 ira_color ();
5236 ira_max_point_before_emit = ira_max_point;
5238 ira_initiate_emit_data ();
5240 ira_emit (loops_p);
5242 max_regno = max_reg_num ();
5243 if (ira_conflicts_p)
5245 if (! loops_p)
5247 if (! ira_use_lra_p)
5248 ira_initiate_assign ();
5250 else
5252 expand_reg_info ();
5254 if (ira_use_lra_p)
5256 ira_allocno_t a;
5257 ira_allocno_iterator ai;
5259 FOR_EACH_ALLOCNO (a, ai)
5260 ALLOCNO_REGNO (a) = REGNO (ALLOCNO_EMIT_DATA (a)->reg);
5262 else
5264 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
5265 fprintf (ira_dump_file, "Flattening IR\n");
5266 ira_flattening (max_regno_before_ira, ira_max_point_before_emit);
5268 /* New insns were generated: add notes and recalculate live
5269 info. */
5270 df_analyze ();
5272 /* ??? Rebuild the loop tree, but why? Does the loop tree
5273 change if new insns were generated? Can that be handled
5274 by updating the loop tree incrementally? */
5275 loop_optimizer_finalize ();
5276 free_dominance_info (CDI_DOMINATORS);
5277 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
5278 | LOOPS_HAVE_RECORDED_EXITS);
5280 if (! ira_use_lra_p)
5282 setup_allocno_assignment_flags ();
5283 ira_initiate_assign ();
5284 ira_reassign_conflict_allocnos (max_regno);
5289 ira_finish_emit_data ();
5291 setup_reg_renumber ();
5293 calculate_allocation_cost ();
5295 #ifdef ENABLE_IRA_CHECKING
5296 if (ira_conflicts_p)
5297 check_allocation ();
5298 #endif
5300 if (max_regno != max_regno_before_ira)
5302 regstat_free_n_sets_and_refs ();
5303 regstat_free_ri ();
5304 regstat_init_n_sets_and_refs ();
5305 regstat_compute_ri ();
5308 overall_cost_before = ira_overall_cost;
5309 if (! ira_conflicts_p)
5310 grow_reg_equivs ();
5311 else
5313 fix_reg_equiv_init ();
5315 #ifdef ENABLE_IRA_CHECKING
5316 print_redundant_copies ();
5317 #endif
5318 if (! ira_use_lra_p)
5320 ira_spilled_reg_stack_slots_num = 0;
5321 ira_spilled_reg_stack_slots
5322 = ((struct ira_spilled_reg_stack_slot *)
5323 ira_allocate (max_regno
5324 * sizeof (struct ira_spilled_reg_stack_slot)));
5325 memset (ira_spilled_reg_stack_slots, 0,
5326 max_regno * sizeof (struct ira_spilled_reg_stack_slot));
5329 allocate_initial_values ();
5331 /* See comment for find_moveable_pseudos call. */
5332 if (ira_conflicts_p)
5333 move_unallocated_pseudos ();
5335 /* Restore original values. */
5336 if (lra_simple_p)
5338 flag_caller_saves = saved_flag_caller_saves;
5339 flag_ira_region = saved_flag_ira_region;
5343 static void
5344 do_reload (void)
5346 basic_block bb;
5347 bool need_dce;
5348 unsigned pic_offset_table_regno = INVALID_REGNUM;
5350 if (flag_ira_verbose < 10)
5351 ira_dump_file = dump_file;
5353 /* If pic_offset_table_rtx is a pseudo register, then keep it so
5354 after reload to avoid possible wrong usages of hard reg assigned
5355 to it. */
5356 if (pic_offset_table_rtx
5357 && REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER)
5358 pic_offset_table_regno = REGNO (pic_offset_table_rtx);
5360 timevar_push (TV_RELOAD);
5361 if (ira_use_lra_p)
5363 if (current_loops != NULL)
5365 loop_optimizer_finalize ();
5366 free_dominance_info (CDI_DOMINATORS);
5368 FOR_ALL_BB_FN (bb, cfun)
5369 bb->loop_father = NULL;
5370 current_loops = NULL;
5372 ira_destroy ();
5374 lra (ira_dump_file);
5375 /* ???!!! Move it before lra () when we use ira_reg_equiv in
5376 LRA. */
5377 vec_free (reg_equivs);
5378 reg_equivs = NULL;
5379 need_dce = false;
5381 else
5383 df_set_flags (DF_NO_INSN_RESCAN);
5384 build_insn_chain ();
5386 need_dce = reload (get_insns (), ira_conflicts_p);
5390 timevar_pop (TV_RELOAD);
5392 timevar_push (TV_IRA);
5394 if (ira_conflicts_p && ! ira_use_lra_p)
5396 ira_free (ira_spilled_reg_stack_slots);
5397 ira_finish_assign ();
5400 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL
5401 && overall_cost_before != ira_overall_cost)
5402 fprintf (ira_dump_file, "+++Overall after reload %d\n", ira_overall_cost);
5404 flag_ira_share_spill_slots = saved_flag_ira_share_spill_slots;
5406 if (! ira_use_lra_p)
5408 ira_destroy ();
5409 if (current_loops != NULL)
5411 loop_optimizer_finalize ();
5412 free_dominance_info (CDI_DOMINATORS);
5414 FOR_ALL_BB_FN (bb, cfun)
5415 bb->loop_father = NULL;
5416 current_loops = NULL;
5418 regstat_free_ri ();
5419 regstat_free_n_sets_and_refs ();
5422 if (optimize)
5423 cleanup_cfg (CLEANUP_EXPENSIVE);
5425 finish_reg_equiv ();
5427 bitmap_obstack_release (&ira_bitmap_obstack);
5428 #ifndef IRA_NO_OBSTACK
5429 obstack_free (&ira_obstack, NULL);
5430 #endif
5432 /* The code after the reload has changed so much that at this point
5433 we might as well just rescan everything. Note that
5434 df_rescan_all_insns is not going to help here because it does not
5435 touch the artificial uses and defs. */
5436 df_finish_pass (true);
5437 df_scan_alloc (NULL);
5438 df_scan_blocks ();
5440 if (optimize > 1)
5442 df_live_add_problem ();
5443 df_live_set_all_dirty ();
5446 if (optimize)
5447 df_analyze ();
5449 if (need_dce && optimize)
5450 run_fast_dce ();
5452 /* Diagnose uses of the hard frame pointer when it is used as a global
5453 register. Often we can get away with letting the user appropriate
5454 the frame pointer, but we should let them know when code generation
5455 makes that impossible. */
5456 if (global_regs[HARD_FRAME_POINTER_REGNUM] && frame_pointer_needed)
5458 tree decl = global_regs_decl[HARD_FRAME_POINTER_REGNUM];
5459 error_at (DECL_SOURCE_LOCATION (current_function_decl),
5460 "frame pointer required, but reserved");
5461 inform (DECL_SOURCE_LOCATION (decl), "for %qD", decl);
5464 if (pic_offset_table_regno != INVALID_REGNUM)
5465 pic_offset_table_rtx = gen_rtx_REG (Pmode, pic_offset_table_regno);
5467 timevar_pop (TV_IRA);
5470 /* Run the integrated register allocator. */
5472 namespace {
5474 const pass_data pass_data_ira =
5476 RTL_PASS, /* type */
5477 "ira", /* name */
5478 OPTGROUP_NONE, /* optinfo_flags */
5479 TV_IRA, /* tv_id */
5480 0, /* properties_required */
5481 0, /* properties_provided */
5482 0, /* properties_destroyed */
5483 0, /* todo_flags_start */
5484 TODO_do_not_ggc_collect, /* todo_flags_finish */
5487 class pass_ira : public rtl_opt_pass
5489 public:
5490 pass_ira (gcc::context *ctxt)
5491 : rtl_opt_pass (pass_data_ira, ctxt)
5494 /* opt_pass methods: */
5495 virtual unsigned int execute (function *)
5497 ira (dump_file);
5498 return 0;
5501 }; // class pass_ira
5503 } // anon namespace
5505 rtl_opt_pass *
5506 make_pass_ira (gcc::context *ctxt)
5508 return new pass_ira (ctxt);
5511 namespace {
5513 const pass_data pass_data_reload =
5515 RTL_PASS, /* type */
5516 "reload", /* name */
5517 OPTGROUP_NONE, /* optinfo_flags */
5518 TV_RELOAD, /* tv_id */
5519 0, /* properties_required */
5520 0, /* properties_provided */
5521 0, /* properties_destroyed */
5522 0, /* todo_flags_start */
5523 0, /* todo_flags_finish */
5526 class pass_reload : public rtl_opt_pass
5528 public:
5529 pass_reload (gcc::context *ctxt)
5530 : rtl_opt_pass (pass_data_reload, ctxt)
5533 /* opt_pass methods: */
5534 virtual unsigned int execute (function *)
5536 do_reload ();
5537 return 0;
5540 }; // class pass_reload
5542 } // anon namespace
5544 rtl_opt_pass *
5545 make_pass_reload (gcc::context *ctxt)
5547 return new pass_reload (ctxt);