* gcc.dg/atomic/c11-atomic-exec-5.c (dg-additional-options): Use
[official-gcc.git] / gcc / ira.c
blob1dd21871865951832b2448873d9ee055986f233c
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, calulates register
157 pressure for each pressure class in each region, sets up
158 conflict hard registers for each allocno and info about calls
159 the allocno lives through (file ira-lives.c).
161 * IRA removes low register pressure loops from the regions
162 mostly to speed IRA up (file ira-build.c).
164 * IRA propagates accumulated allocno info from lower region
165 allocnos to corresponding upper region allocnos (file
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 coloringh 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 allono 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 impelemented 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 initilized 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 "function.h"
390 #include "ggc.h"
391 #include "ira-int.h"
392 #include "lra.h"
393 #include "dce.h"
394 #include "dbgcnt.h"
396 struct target_ira default_target_ira;
397 struct target_ira_int default_target_ira_int;
398 #if SWITCHABLE_TARGET
399 struct target_ira *this_target_ira = &default_target_ira;
400 struct target_ira_int *this_target_ira_int = &default_target_ira_int;
401 #endif
403 /* A modified value of flag `-fira-verbose' used internally. */
404 int internal_flag_ira_verbose;
406 /* Dump file of the allocator if it is not NULL. */
407 FILE *ira_dump_file;
409 /* The number of elements in the following array. */
410 int ira_spilled_reg_stack_slots_num;
412 /* The following array contains info about spilled pseudo-registers
413 stack slots used in current function so far. */
414 struct ira_spilled_reg_stack_slot *ira_spilled_reg_stack_slots;
416 /* Correspondingly overall cost of the allocation, overall cost before
417 reload, cost of the allocnos assigned to hard-registers, cost of
418 the allocnos assigned to memory, cost of loads, stores and register
419 move insns generated for pseudo-register live range splitting (see
420 ira-emit.c). */
421 int ira_overall_cost, overall_cost_before;
422 int ira_reg_cost, ira_mem_cost;
423 int ira_load_cost, ira_store_cost, ira_shuffle_cost;
424 int ira_move_loops_num, ira_additional_jumps_num;
426 /* All registers that can be eliminated. */
428 HARD_REG_SET eliminable_regset;
430 /* Value of max_reg_num () before IRA work start. This value helps
431 us to recognize a situation when new pseudos were created during
432 IRA work. */
433 static int max_regno_before_ira;
435 /* Temporary hard reg set used for a different calculation. */
436 static HARD_REG_SET temp_hard_regset;
438 #define last_mode_for_init_move_cost \
439 (this_target_ira_int->x_last_mode_for_init_move_cost)
442 /* The function sets up the map IRA_REG_MODE_HARD_REGSET. */
443 static void
444 setup_reg_mode_hard_regset (void)
446 int i, m, hard_regno;
448 for (m = 0; m < NUM_MACHINE_MODES; m++)
449 for (hard_regno = 0; hard_regno < FIRST_PSEUDO_REGISTER; hard_regno++)
451 CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset[hard_regno][m]);
452 for (i = hard_regno_nregs[hard_regno][m] - 1; i >= 0; i--)
453 if (hard_regno + i < FIRST_PSEUDO_REGISTER)
454 SET_HARD_REG_BIT (ira_reg_mode_hard_regset[hard_regno][m],
455 hard_regno + i);
460 #define no_unit_alloc_regs \
461 (this_target_ira_int->x_no_unit_alloc_regs)
463 /* The function sets up the three arrays declared above. */
464 static void
465 setup_class_hard_regs (void)
467 int cl, i, hard_regno, n;
468 HARD_REG_SET processed_hard_reg_set;
470 ira_assert (SHRT_MAX >= FIRST_PSEUDO_REGISTER);
471 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
473 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
474 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
475 CLEAR_HARD_REG_SET (processed_hard_reg_set);
476 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
478 ira_non_ordered_class_hard_regs[cl][i] = -1;
479 ira_class_hard_reg_index[cl][i] = -1;
481 for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
483 #ifdef REG_ALLOC_ORDER
484 hard_regno = reg_alloc_order[i];
485 #else
486 hard_regno = i;
487 #endif
488 if (TEST_HARD_REG_BIT (processed_hard_reg_set, hard_regno))
489 continue;
490 SET_HARD_REG_BIT (processed_hard_reg_set, hard_regno);
491 if (! TEST_HARD_REG_BIT (temp_hard_regset, hard_regno))
492 ira_class_hard_reg_index[cl][hard_regno] = -1;
493 else
495 ira_class_hard_reg_index[cl][hard_regno] = n;
496 ira_class_hard_regs[cl][n++] = hard_regno;
499 ira_class_hard_regs_num[cl] = n;
500 for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
501 if (TEST_HARD_REG_BIT (temp_hard_regset, i))
502 ira_non_ordered_class_hard_regs[cl][n++] = i;
503 ira_assert (ira_class_hard_regs_num[cl] == n);
507 /* Set up global variables defining info about hard registers for the
508 allocation. These depend on USE_HARD_FRAME_P whose TRUE value means
509 that we can use the hard frame pointer for the allocation. */
510 static void
511 setup_alloc_regs (bool use_hard_frame_p)
513 #ifdef ADJUST_REG_ALLOC_ORDER
514 ADJUST_REG_ALLOC_ORDER;
515 #endif
516 COPY_HARD_REG_SET (no_unit_alloc_regs, fixed_reg_set);
517 if (! use_hard_frame_p)
518 SET_HARD_REG_BIT (no_unit_alloc_regs, HARD_FRAME_POINTER_REGNUM);
519 setup_class_hard_regs ();
524 #define alloc_reg_class_subclasses \
525 (this_target_ira_int->x_alloc_reg_class_subclasses)
527 /* Initialize the table of subclasses of each reg class. */
528 static void
529 setup_reg_subclasses (void)
531 int i, j;
532 HARD_REG_SET temp_hard_regset2;
534 for (i = 0; i < N_REG_CLASSES; i++)
535 for (j = 0; j < N_REG_CLASSES; j++)
536 alloc_reg_class_subclasses[i][j] = LIM_REG_CLASSES;
538 for (i = 0; i < N_REG_CLASSES; i++)
540 if (i == (int) NO_REGS)
541 continue;
543 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
544 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
545 if (hard_reg_set_empty_p (temp_hard_regset))
546 continue;
547 for (j = 0; j < N_REG_CLASSES; j++)
548 if (i != j)
550 enum reg_class *p;
552 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[j]);
553 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
554 if (! hard_reg_set_subset_p (temp_hard_regset,
555 temp_hard_regset2))
556 continue;
557 p = &alloc_reg_class_subclasses[j][0];
558 while (*p != LIM_REG_CLASSES) p++;
559 *p = (enum reg_class) i;
566 /* Set up IRA_MEMORY_MOVE_COST and IRA_MAX_MEMORY_MOVE_COST. */
567 static void
568 setup_class_subset_and_memory_move_costs (void)
570 int cl, cl2, mode, cost;
571 HARD_REG_SET temp_hard_regset2;
573 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
574 ira_memory_move_cost[mode][NO_REGS][0]
575 = ira_memory_move_cost[mode][NO_REGS][1] = SHRT_MAX;
576 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
578 if (cl != (int) NO_REGS)
579 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
581 ira_max_memory_move_cost[mode][cl][0]
582 = ira_memory_move_cost[mode][cl][0]
583 = memory_move_cost ((enum machine_mode) mode,
584 (reg_class_t) cl, false);
585 ira_max_memory_move_cost[mode][cl][1]
586 = ira_memory_move_cost[mode][cl][1]
587 = memory_move_cost ((enum machine_mode) mode,
588 (reg_class_t) cl, true);
589 /* Costs for NO_REGS are used in cost calculation on the
590 1st pass when the preferred register classes are not
591 known yet. In this case we take the best scenario. */
592 if (ira_memory_move_cost[mode][NO_REGS][0]
593 > ira_memory_move_cost[mode][cl][0])
594 ira_max_memory_move_cost[mode][NO_REGS][0]
595 = ira_memory_move_cost[mode][NO_REGS][0]
596 = ira_memory_move_cost[mode][cl][0];
597 if (ira_memory_move_cost[mode][NO_REGS][1]
598 > ira_memory_move_cost[mode][cl][1])
599 ira_max_memory_move_cost[mode][NO_REGS][1]
600 = ira_memory_move_cost[mode][NO_REGS][1]
601 = ira_memory_move_cost[mode][cl][1];
604 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
605 for (cl2 = (int) N_REG_CLASSES - 1; cl2 >= 0; cl2--)
607 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
608 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
609 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]);
610 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
611 ira_class_subset_p[cl][cl2]
612 = hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2);
613 if (! hard_reg_set_empty_p (temp_hard_regset2)
614 && hard_reg_set_subset_p (reg_class_contents[cl2],
615 reg_class_contents[cl]))
616 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
618 cost = ira_memory_move_cost[mode][cl2][0];
619 if (cost > ira_max_memory_move_cost[mode][cl][0])
620 ira_max_memory_move_cost[mode][cl][0] = cost;
621 cost = ira_memory_move_cost[mode][cl2][1];
622 if (cost > ira_max_memory_move_cost[mode][cl][1])
623 ira_max_memory_move_cost[mode][cl][1] = cost;
626 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
627 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
629 ira_memory_move_cost[mode][cl][0]
630 = ira_max_memory_move_cost[mode][cl][0];
631 ira_memory_move_cost[mode][cl][1]
632 = ira_max_memory_move_cost[mode][cl][1];
634 setup_reg_subclasses ();
639 /* Define the following macro if allocation through malloc if
640 preferable. */
641 #define IRA_NO_OBSTACK
643 #ifndef IRA_NO_OBSTACK
644 /* Obstack used for storing all dynamic data (except bitmaps) of the
645 IRA. */
646 static struct obstack ira_obstack;
647 #endif
649 /* Obstack used for storing all bitmaps of the IRA. */
650 static struct bitmap_obstack ira_bitmap_obstack;
652 /* Allocate memory of size LEN for IRA data. */
653 void *
654 ira_allocate (size_t len)
656 void *res;
658 #ifndef IRA_NO_OBSTACK
659 res = obstack_alloc (&ira_obstack, len);
660 #else
661 res = xmalloc (len);
662 #endif
663 return res;
666 /* Free memory ADDR allocated for IRA data. */
667 void
668 ira_free (void *addr ATTRIBUTE_UNUSED)
670 #ifndef IRA_NO_OBSTACK
671 /* do nothing */
672 #else
673 free (addr);
674 #endif
678 /* Allocate and returns bitmap for IRA. */
679 bitmap
680 ira_allocate_bitmap (void)
682 return BITMAP_ALLOC (&ira_bitmap_obstack);
685 /* Free bitmap B allocated for IRA. */
686 void
687 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED)
689 /* do nothing */
694 /* Output information about allocation of all allocnos (except for
695 caps) into file F. */
696 void
697 ira_print_disposition (FILE *f)
699 int i, n, max_regno;
700 ira_allocno_t a;
701 basic_block bb;
703 fprintf (f, "Disposition:");
704 max_regno = max_reg_num ();
705 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
706 for (a = ira_regno_allocno_map[i];
707 a != NULL;
708 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
710 if (n % 4 == 0)
711 fprintf (f, "\n");
712 n++;
713 fprintf (f, " %4d:r%-4d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
714 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
715 fprintf (f, "b%-3d", bb->index);
716 else
717 fprintf (f, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
718 if (ALLOCNO_HARD_REGNO (a) >= 0)
719 fprintf (f, " %3d", ALLOCNO_HARD_REGNO (a));
720 else
721 fprintf (f, " mem");
723 fprintf (f, "\n");
726 /* Outputs information about allocation of all allocnos into
727 stderr. */
728 void
729 ira_debug_disposition (void)
731 ira_print_disposition (stderr);
736 /* Set up ira_stack_reg_pressure_class which is the biggest pressure
737 register class containing stack registers or NO_REGS if there are
738 no stack registers. To find this class, we iterate through all
739 register pressure classes and choose the first register pressure
740 class containing all the stack registers and having the biggest
741 size. */
742 static void
743 setup_stack_reg_pressure_class (void)
745 ira_stack_reg_pressure_class = NO_REGS;
746 #ifdef STACK_REGS
748 int i, best, size;
749 enum reg_class cl;
750 HARD_REG_SET temp_hard_regset2;
752 CLEAR_HARD_REG_SET (temp_hard_regset);
753 for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
754 SET_HARD_REG_BIT (temp_hard_regset, i);
755 best = 0;
756 for (i = 0; i < ira_pressure_classes_num; i++)
758 cl = ira_pressure_classes[i];
759 COPY_HARD_REG_SET (temp_hard_regset2, temp_hard_regset);
760 AND_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
761 size = hard_reg_set_size (temp_hard_regset2);
762 if (best < size)
764 best = size;
765 ira_stack_reg_pressure_class = cl;
769 #endif
772 /* Find pressure classes which are register classes for which we
773 calculate register pressure in IRA, register pressure sensitive
774 insn scheduling, and register pressure sensitive loop invariant
775 motion.
777 To make register pressure calculation easy, we always use
778 non-intersected register pressure classes. A move of hard
779 registers from one register pressure class is not more expensive
780 than load and store of the hard registers. Most likely an allocno
781 class will be a subset of a register pressure class and in many
782 cases a register pressure class. That makes usage of register
783 pressure classes a good approximation to find a high register
784 pressure. */
785 static void
786 setup_pressure_classes (void)
788 int cost, i, n, curr;
789 int cl, cl2;
790 enum reg_class pressure_classes[N_REG_CLASSES];
791 int m;
792 HARD_REG_SET temp_hard_regset2;
793 bool insert_p;
795 n = 0;
796 for (cl = 0; cl < N_REG_CLASSES; cl++)
798 if (ira_class_hard_regs_num[cl] == 0)
799 continue;
800 if (ira_class_hard_regs_num[cl] != 1
801 /* A register class without subclasses may contain a few
802 hard registers and movement between them is costly
803 (e.g. SPARC FPCC registers). We still should consider it
804 as a candidate for a pressure class. */
805 && alloc_reg_class_subclasses[cl][0] < cl)
807 /* Check that the moves between any hard registers of the
808 current class are not more expensive for a legal mode
809 than load/store of the hard registers of the current
810 class. Such class is a potential candidate to be a
811 register pressure class. */
812 for (m = 0; m < NUM_MACHINE_MODES; m++)
814 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
815 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
816 AND_COMPL_HARD_REG_SET (temp_hard_regset,
817 ira_prohibited_class_mode_regs[cl][m]);
818 if (hard_reg_set_empty_p (temp_hard_regset))
819 continue;
820 ira_init_register_move_cost_if_necessary ((enum machine_mode) m);
821 cost = ira_register_move_cost[m][cl][cl];
822 if (cost <= ira_max_memory_move_cost[m][cl][1]
823 || cost <= ira_max_memory_move_cost[m][cl][0])
824 break;
826 if (m >= NUM_MACHINE_MODES)
827 continue;
829 curr = 0;
830 insert_p = true;
831 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
832 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
833 /* Remove so far added pressure classes which are subset of the
834 current candidate class. Prefer GENERAL_REGS as a pressure
835 register class to another class containing the same
836 allocatable hard registers. We do this because machine
837 dependent cost hooks might give wrong costs for the latter
838 class but always give the right cost for the former class
839 (GENERAL_REGS). */
840 for (i = 0; i < n; i++)
842 cl2 = pressure_classes[i];
843 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]);
844 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
845 if (hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2)
846 && (! hard_reg_set_equal_p (temp_hard_regset, temp_hard_regset2)
847 || cl2 == (int) GENERAL_REGS))
849 pressure_classes[curr++] = (enum reg_class) cl2;
850 insert_p = false;
851 continue;
853 if (hard_reg_set_subset_p (temp_hard_regset2, temp_hard_regset)
854 && (! hard_reg_set_equal_p (temp_hard_regset2, temp_hard_regset)
855 || cl == (int) GENERAL_REGS))
856 continue;
857 if (hard_reg_set_equal_p (temp_hard_regset2, temp_hard_regset))
858 insert_p = false;
859 pressure_classes[curr++] = (enum reg_class) cl2;
861 /* If the current candidate is a subset of a so far added
862 pressure class, don't add it to the list of the pressure
863 classes. */
864 if (insert_p)
865 pressure_classes[curr++] = (enum reg_class) cl;
866 n = curr;
868 #ifdef ENABLE_IRA_CHECKING
870 HARD_REG_SET ignore_hard_regs;
872 /* Check pressure classes correctness: here we check that hard
873 registers from all register pressure classes contains all hard
874 registers available for the allocation. */
875 CLEAR_HARD_REG_SET (temp_hard_regset);
876 CLEAR_HARD_REG_SET (temp_hard_regset2);
877 COPY_HARD_REG_SET (ignore_hard_regs, no_unit_alloc_regs);
878 for (cl = 0; cl < LIM_REG_CLASSES; cl++)
880 /* For some targets (like MIPS with MD_REGS), there are some
881 classes with hard registers available for allocation but
882 not able to hold value of any mode. */
883 for (m = 0; m < NUM_MACHINE_MODES; m++)
884 if (contains_reg_of_mode[cl][m])
885 break;
886 if (m >= NUM_MACHINE_MODES)
888 IOR_HARD_REG_SET (ignore_hard_regs, reg_class_contents[cl]);
889 continue;
891 for (i = 0; i < n; i++)
892 if ((int) pressure_classes[i] == cl)
893 break;
894 IOR_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
895 if (i < n)
896 IOR_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
898 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
899 /* Some targets (like SPARC with ICC reg) have alocatable regs
900 for which no reg class is defined. */
901 if (REGNO_REG_CLASS (i) == NO_REGS)
902 SET_HARD_REG_BIT (ignore_hard_regs, i);
903 AND_COMPL_HARD_REG_SET (temp_hard_regset, ignore_hard_regs);
904 AND_COMPL_HARD_REG_SET (temp_hard_regset2, ignore_hard_regs);
905 ira_assert (hard_reg_set_subset_p (temp_hard_regset2, temp_hard_regset));
907 #endif
908 ira_pressure_classes_num = 0;
909 for (i = 0; i < n; i++)
911 cl = (int) pressure_classes[i];
912 ira_reg_pressure_class_p[cl] = true;
913 ira_pressure_classes[ira_pressure_classes_num++] = (enum reg_class) cl;
915 setup_stack_reg_pressure_class ();
918 /* Set up IRA_UNIFORM_CLASS_P. Uniform class is a register class
919 whose register move cost between any registers of the class is the
920 same as for all its subclasses. We use the data to speed up the
921 2nd pass of calculations of allocno costs. */
922 static void
923 setup_uniform_class_p (void)
925 int i, cl, cl2, m;
927 for (cl = 0; cl < N_REG_CLASSES; cl++)
929 ira_uniform_class_p[cl] = false;
930 if (ira_class_hard_regs_num[cl] == 0)
931 continue;
932 /* We can not use alloc_reg_class_subclasses here because move
933 cost hooks does not take into account that some registers are
934 unavailable for the subtarget. E.g. for i686, INT_SSE_REGS
935 is element of alloc_reg_class_subclasses for GENERAL_REGS
936 because SSE regs are unavailable. */
937 for (i = 0; (cl2 = reg_class_subclasses[cl][i]) != LIM_REG_CLASSES; i++)
939 if (ira_class_hard_regs_num[cl2] == 0)
940 continue;
941 for (m = 0; m < NUM_MACHINE_MODES; m++)
942 if (contains_reg_of_mode[cl][m] && contains_reg_of_mode[cl2][m])
944 ira_init_register_move_cost_if_necessary ((enum machine_mode) m);
945 if (ira_register_move_cost[m][cl][cl]
946 != ira_register_move_cost[m][cl2][cl2])
947 break;
949 if (m < NUM_MACHINE_MODES)
950 break;
952 if (cl2 == LIM_REG_CLASSES)
953 ira_uniform_class_p[cl] = true;
957 /* Set up IRA_ALLOCNO_CLASSES, IRA_ALLOCNO_CLASSES_NUM,
958 IRA_IMPORTANT_CLASSES, and IRA_IMPORTANT_CLASSES_NUM.
960 Target may have many subtargets and not all target hard regiters can
961 be used for allocation, e.g. x86 port in 32-bit mode can not use
962 hard registers introduced in x86-64 like r8-r15). Some classes
963 might have the same allocatable hard registers, e.g. INDEX_REGS
964 and GENERAL_REGS in x86 port in 32-bit mode. To decrease different
965 calculations efforts we introduce allocno classes which contain
966 unique non-empty sets of allocatable hard-registers.
968 Pseudo class cost calculation in ira-costs.c is very expensive.
969 Therefore we are trying to decrease number of classes involved in
970 such calculation. Register classes used in the cost calculation
971 are called important classes. They are allocno classes and other
972 non-empty classes whose allocatable hard register sets are inside
973 of an allocno class hard register set. From the first sight, it
974 looks like that they are just allocno classes. It is not true. In
975 example of x86-port in 32-bit mode, allocno classes will contain
976 GENERAL_REGS but not LEGACY_REGS (because allocatable hard
977 registers are the same for the both classes). The important
978 classes will contain GENERAL_REGS and LEGACY_REGS. It is done
979 because a machine description insn constraint may refers for
980 LEGACY_REGS and code in ira-costs.c is mostly base on investigation
981 of the insn constraints. */
982 static void
983 setup_allocno_and_important_classes (void)
985 int i, j, n, cl;
986 bool set_p;
987 HARD_REG_SET temp_hard_regset2;
988 static enum reg_class classes[LIM_REG_CLASSES + 1];
990 n = 0;
991 /* Collect classes which contain unique sets of allocatable hard
992 registers. Prefer GENERAL_REGS to other classes containing the
993 same set of hard registers. */
994 for (i = 0; i < LIM_REG_CLASSES; i++)
996 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
997 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
998 for (j = 0; j < n; j++)
1000 cl = classes[j];
1001 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
1002 AND_COMPL_HARD_REG_SET (temp_hard_regset2,
1003 no_unit_alloc_regs);
1004 if (hard_reg_set_equal_p (temp_hard_regset,
1005 temp_hard_regset2))
1006 break;
1008 if (j >= n)
1009 classes[n++] = (enum reg_class) i;
1010 else if (i == GENERAL_REGS)
1011 /* Prefer general regs. For i386 example, it means that
1012 we prefer GENERAL_REGS over INDEX_REGS or LEGACY_REGS
1013 (all of them consists of the same available hard
1014 registers). */
1015 classes[j] = (enum reg_class) i;
1017 classes[n] = LIM_REG_CLASSES;
1019 /* Set up classes which can be used for allocnos as classes
1020 conatining non-empty unique sets of allocatable hard
1021 registers. */
1022 ira_allocno_classes_num = 0;
1023 for (i = 0; (cl = classes[i]) != LIM_REG_CLASSES; i++)
1024 if (ira_class_hard_regs_num[cl] > 0)
1025 ira_allocno_classes[ira_allocno_classes_num++] = (enum reg_class) cl;
1026 ira_important_classes_num = 0;
1027 /* Add non-allocno classes containing to non-empty set of
1028 allocatable hard regs. */
1029 for (cl = 0; cl < N_REG_CLASSES; cl++)
1030 if (ira_class_hard_regs_num[cl] > 0)
1032 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
1033 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1034 set_p = false;
1035 for (j = 0; j < ira_allocno_classes_num; j++)
1037 COPY_HARD_REG_SET (temp_hard_regset2,
1038 reg_class_contents[ira_allocno_classes[j]]);
1039 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
1040 if ((enum reg_class) cl == ira_allocno_classes[j])
1041 break;
1042 else if (hard_reg_set_subset_p (temp_hard_regset,
1043 temp_hard_regset2))
1044 set_p = true;
1046 if (set_p && j >= ira_allocno_classes_num)
1047 ira_important_classes[ira_important_classes_num++]
1048 = (enum reg_class) cl;
1050 /* Now add allocno classes to the important classes. */
1051 for (j = 0; j < ira_allocno_classes_num; j++)
1052 ira_important_classes[ira_important_classes_num++]
1053 = ira_allocno_classes[j];
1054 for (cl = 0; cl < N_REG_CLASSES; cl++)
1056 ira_reg_allocno_class_p[cl] = false;
1057 ira_reg_pressure_class_p[cl] = false;
1059 for (j = 0; j < ira_allocno_classes_num; j++)
1060 ira_reg_allocno_class_p[ira_allocno_classes[j]] = true;
1061 setup_pressure_classes ();
1062 setup_uniform_class_p ();
1065 /* Setup translation in CLASS_TRANSLATE of all classes into a class
1066 given by array CLASSES of length CLASSES_NUM. The function is used
1067 make translation any reg class to an allocno class or to an
1068 pressure class. This translation is necessary for some
1069 calculations when we can use only allocno or pressure classes and
1070 such translation represents an approximate representation of all
1071 classes.
1073 The translation in case when allocatable hard register set of a
1074 given class is subset of allocatable hard register set of a class
1075 in CLASSES is pretty simple. We use smallest classes from CLASSES
1076 containing a given class. If allocatable hard register set of a
1077 given class is not a subset of any corresponding set of a class
1078 from CLASSES, we use the cheapest (with load/store point of view)
1079 class from CLASSES whose set intersects with given class set */
1080 static void
1081 setup_class_translate_array (enum reg_class *class_translate,
1082 int classes_num, enum reg_class *classes)
1084 int cl, mode;
1085 enum reg_class aclass, best_class, *cl_ptr;
1086 int i, cost, min_cost, best_cost;
1088 for (cl = 0; cl < N_REG_CLASSES; cl++)
1089 class_translate[cl] = NO_REGS;
1091 for (i = 0; i < classes_num; i++)
1093 aclass = classes[i];
1094 for (cl_ptr = &alloc_reg_class_subclasses[aclass][0];
1095 (cl = *cl_ptr) != LIM_REG_CLASSES;
1096 cl_ptr++)
1097 if (class_translate[cl] == NO_REGS)
1098 class_translate[cl] = aclass;
1099 class_translate[aclass] = aclass;
1101 /* For classes which are not fully covered by one of given classes
1102 (in other words covered by more one given class), use the
1103 cheapest class. */
1104 for (cl = 0; cl < N_REG_CLASSES; cl++)
1106 if (cl == NO_REGS || class_translate[cl] != NO_REGS)
1107 continue;
1108 best_class = NO_REGS;
1109 best_cost = INT_MAX;
1110 for (i = 0; i < classes_num; i++)
1112 aclass = classes[i];
1113 COPY_HARD_REG_SET (temp_hard_regset,
1114 reg_class_contents[aclass]);
1115 AND_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
1116 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1117 if (! hard_reg_set_empty_p (temp_hard_regset))
1119 min_cost = INT_MAX;
1120 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1122 cost = (ira_memory_move_cost[mode][aclass][0]
1123 + ira_memory_move_cost[mode][aclass][1]);
1124 if (min_cost > cost)
1125 min_cost = cost;
1127 if (best_class == NO_REGS || best_cost > min_cost)
1129 best_class = aclass;
1130 best_cost = min_cost;
1134 class_translate[cl] = best_class;
1138 /* Set up array IRA_ALLOCNO_CLASS_TRANSLATE and
1139 IRA_PRESSURE_CLASS_TRANSLATE. */
1140 static void
1141 setup_class_translate (void)
1143 setup_class_translate_array (ira_allocno_class_translate,
1144 ira_allocno_classes_num, ira_allocno_classes);
1145 setup_class_translate_array (ira_pressure_class_translate,
1146 ira_pressure_classes_num, ira_pressure_classes);
1149 /* Order numbers of allocno classes in original target allocno class
1150 array, -1 for non-allocno classes. */
1151 static int allocno_class_order[N_REG_CLASSES];
1153 /* The function used to sort the important classes. */
1154 static int
1155 comp_reg_classes_func (const void *v1p, const void *v2p)
1157 enum reg_class cl1 = *(const enum reg_class *) v1p;
1158 enum reg_class cl2 = *(const enum reg_class *) v2p;
1159 enum reg_class tcl1, tcl2;
1160 int diff;
1162 tcl1 = ira_allocno_class_translate[cl1];
1163 tcl2 = ira_allocno_class_translate[cl2];
1164 if (tcl1 != NO_REGS && tcl2 != NO_REGS
1165 && (diff = allocno_class_order[tcl1] - allocno_class_order[tcl2]) != 0)
1166 return diff;
1167 return (int) cl1 - (int) cl2;
1170 /* For correct work of function setup_reg_class_relation we need to
1171 reorder important classes according to the order of their allocno
1172 classes. It places important classes containing the same
1173 allocatable hard register set adjacent to each other and allocno
1174 class with the allocatable hard register set right after the other
1175 important classes with the same set.
1177 In example from comments of function
1178 setup_allocno_and_important_classes, it places LEGACY_REGS and
1179 GENERAL_REGS close to each other and GENERAL_REGS is after
1180 LEGACY_REGS. */
1181 static void
1182 reorder_important_classes (void)
1184 int i;
1186 for (i = 0; i < N_REG_CLASSES; i++)
1187 allocno_class_order[i] = -1;
1188 for (i = 0; i < ira_allocno_classes_num; i++)
1189 allocno_class_order[ira_allocno_classes[i]] = i;
1190 qsort (ira_important_classes, ira_important_classes_num,
1191 sizeof (enum reg_class), comp_reg_classes_func);
1192 for (i = 0; i < ira_important_classes_num; i++)
1193 ira_important_class_nums[ira_important_classes[i]] = i;
1196 /* Set up IRA_REG_CLASS_SUBUNION, IRA_REG_CLASS_SUPERUNION,
1197 IRA_REG_CLASS_SUPER_CLASSES, IRA_REG_CLASSES_INTERSECT, and
1198 IRA_REG_CLASSES_INTERSECT_P. For the meaning of the relations,
1199 please see corresponding comments in ira-int.h. */
1200 static void
1201 setup_reg_class_relations (void)
1203 int i, cl1, cl2, cl3;
1204 HARD_REG_SET intersection_set, union_set, temp_set2;
1205 bool important_class_p[N_REG_CLASSES];
1207 memset (important_class_p, 0, sizeof (important_class_p));
1208 for (i = 0; i < ira_important_classes_num; i++)
1209 important_class_p[ira_important_classes[i]] = true;
1210 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1212 ira_reg_class_super_classes[cl1][0] = LIM_REG_CLASSES;
1213 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1215 ira_reg_classes_intersect_p[cl1][cl2] = false;
1216 ira_reg_class_intersect[cl1][cl2] = NO_REGS;
1217 ira_reg_class_subset[cl1][cl2] = NO_REGS;
1218 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl1]);
1219 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1220 COPY_HARD_REG_SET (temp_set2, reg_class_contents[cl2]);
1221 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1222 if (hard_reg_set_empty_p (temp_hard_regset)
1223 && hard_reg_set_empty_p (temp_set2))
1225 /* The both classes have no allocatable hard registers
1226 -- take all class hard registers into account and use
1227 reg_class_subunion and reg_class_superunion. */
1228 for (i = 0;; i++)
1230 cl3 = reg_class_subclasses[cl1][i];
1231 if (cl3 == LIM_REG_CLASSES)
1232 break;
1233 if (reg_class_subset_p (ira_reg_class_intersect[cl1][cl2],
1234 (enum reg_class) cl3))
1235 ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
1237 ira_reg_class_subunion[cl1][cl2] = reg_class_subunion[cl1][cl2];
1238 ira_reg_class_superunion[cl1][cl2] = reg_class_superunion[cl1][cl2];
1239 continue;
1241 ira_reg_classes_intersect_p[cl1][cl2]
1242 = hard_reg_set_intersect_p (temp_hard_regset, temp_set2);
1243 if (important_class_p[cl1] && important_class_p[cl2]
1244 && hard_reg_set_subset_p (temp_hard_regset, temp_set2))
1246 /* CL1 and CL2 are important classes and CL1 allocatable
1247 hard register set is inside of CL2 allocatable hard
1248 registers -- make CL1 a superset of CL2. */
1249 enum reg_class *p;
1251 p = &ira_reg_class_super_classes[cl1][0];
1252 while (*p != LIM_REG_CLASSES)
1253 p++;
1254 *p++ = (enum reg_class) cl2;
1255 *p = LIM_REG_CLASSES;
1257 ira_reg_class_subunion[cl1][cl2] = NO_REGS;
1258 ira_reg_class_superunion[cl1][cl2] = NO_REGS;
1259 COPY_HARD_REG_SET (intersection_set, reg_class_contents[cl1]);
1260 AND_HARD_REG_SET (intersection_set, reg_class_contents[cl2]);
1261 AND_COMPL_HARD_REG_SET (intersection_set, no_unit_alloc_regs);
1262 COPY_HARD_REG_SET (union_set, reg_class_contents[cl1]);
1263 IOR_HARD_REG_SET (union_set, reg_class_contents[cl2]);
1264 AND_COMPL_HARD_REG_SET (union_set, no_unit_alloc_regs);
1265 for (cl3 = 0; cl3 < N_REG_CLASSES; cl3++)
1267 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl3]);
1268 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1269 if (hard_reg_set_subset_p (temp_hard_regset, intersection_set))
1271 /* CL3 allocatable hard register set is inside of
1272 intersection of allocatable hard register sets
1273 of CL1 and CL2. */
1274 if (important_class_p[cl3])
1276 COPY_HARD_REG_SET
1277 (temp_set2,
1278 reg_class_contents
1279 [(int) ira_reg_class_intersect[cl1][cl2]]);
1280 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1281 if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1282 /* If the allocatable hard register sets are
1283 the same, prefer GENERAL_REGS or the
1284 smallest class for debugging
1285 purposes. */
1286 || (hard_reg_set_equal_p (temp_hard_regset, temp_set2)
1287 && (cl3 == GENERAL_REGS
1288 || ((ira_reg_class_intersect[cl1][cl2]
1289 != GENERAL_REGS)
1290 && hard_reg_set_subset_p
1291 (reg_class_contents[cl3],
1292 reg_class_contents
1293 [(int)
1294 ira_reg_class_intersect[cl1][cl2]])))))
1295 ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
1297 COPY_HARD_REG_SET
1298 (temp_set2,
1299 reg_class_contents[(int) ira_reg_class_subset[cl1][cl2]]);
1300 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1301 if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1302 /* Ignore unavailable hard registers and prefer
1303 smallest class for debugging purposes. */
1304 || (hard_reg_set_equal_p (temp_hard_regset, temp_set2)
1305 && hard_reg_set_subset_p
1306 (reg_class_contents[cl3],
1307 reg_class_contents
1308 [(int) ira_reg_class_subset[cl1][cl2]])))
1309 ira_reg_class_subset[cl1][cl2] = (enum reg_class) cl3;
1311 if (important_class_p[cl3]
1312 && hard_reg_set_subset_p (temp_hard_regset, union_set))
1314 /* CL3 allocatbale hard register set is inside of
1315 union of allocatable hard register sets of CL1
1316 and CL2. */
1317 COPY_HARD_REG_SET
1318 (temp_set2,
1319 reg_class_contents[(int) ira_reg_class_subunion[cl1][cl2]]);
1320 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1321 if (ira_reg_class_subunion[cl1][cl2] == NO_REGS
1322 || (hard_reg_set_subset_p (temp_set2, temp_hard_regset)
1324 && (! hard_reg_set_equal_p (temp_set2,
1325 temp_hard_regset)
1326 || cl3 == GENERAL_REGS
1327 /* If the allocatable hard register sets are the
1328 same, prefer GENERAL_REGS or the smallest
1329 class for debugging purposes. */
1330 || (ira_reg_class_subunion[cl1][cl2] != GENERAL_REGS
1331 && hard_reg_set_subset_p
1332 (reg_class_contents[cl3],
1333 reg_class_contents
1334 [(int) ira_reg_class_subunion[cl1][cl2]])))))
1335 ira_reg_class_subunion[cl1][cl2] = (enum reg_class) cl3;
1337 if (hard_reg_set_subset_p (union_set, temp_hard_regset))
1339 /* CL3 allocatable hard register set contains union
1340 of allocatable hard register sets of CL1 and
1341 CL2. */
1342 COPY_HARD_REG_SET
1343 (temp_set2,
1344 reg_class_contents[(int) ira_reg_class_superunion[cl1][cl2]]);
1345 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1346 if (ira_reg_class_superunion[cl1][cl2] == NO_REGS
1347 || (hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1349 && (! hard_reg_set_equal_p (temp_set2,
1350 temp_hard_regset)
1351 || cl3 == GENERAL_REGS
1352 /* If the allocatable hard register sets are the
1353 same, prefer GENERAL_REGS or the smallest
1354 class for debugging purposes. */
1355 || (ira_reg_class_superunion[cl1][cl2] != GENERAL_REGS
1356 && hard_reg_set_subset_p
1357 (reg_class_contents[cl3],
1358 reg_class_contents
1359 [(int) ira_reg_class_superunion[cl1][cl2]])))))
1360 ira_reg_class_superunion[cl1][cl2] = (enum reg_class) cl3;
1367 /* Output all unifrom and important classes into file F. */
1368 static void
1369 print_unform_and_important_classes (FILE *f)
1371 static const char *const reg_class_names[] = REG_CLASS_NAMES;
1372 int i, cl;
1374 fprintf (f, "Uniform classes:\n");
1375 for (cl = 0; cl < N_REG_CLASSES; cl++)
1376 if (ira_uniform_class_p[cl])
1377 fprintf (f, " %s", reg_class_names[cl]);
1378 fprintf (f, "\nImportant classes:\n");
1379 for (i = 0; i < ira_important_classes_num; i++)
1380 fprintf (f, " %s", reg_class_names[ira_important_classes[i]]);
1381 fprintf (f, "\n");
1384 /* Output all possible allocno or pressure classes and their
1385 translation map into file F. */
1386 static void
1387 print_translated_classes (FILE *f, bool pressure_p)
1389 int classes_num = (pressure_p
1390 ? ira_pressure_classes_num : ira_allocno_classes_num);
1391 enum reg_class *classes = (pressure_p
1392 ? ira_pressure_classes : ira_allocno_classes);
1393 enum reg_class *class_translate = (pressure_p
1394 ? ira_pressure_class_translate
1395 : ira_allocno_class_translate);
1396 static const char *const reg_class_names[] = REG_CLASS_NAMES;
1397 int i;
1399 fprintf (f, "%s classes:\n", pressure_p ? "Pressure" : "Allocno");
1400 for (i = 0; i < classes_num; i++)
1401 fprintf (f, " %s", reg_class_names[classes[i]]);
1402 fprintf (f, "\nClass translation:\n");
1403 for (i = 0; i < N_REG_CLASSES; i++)
1404 fprintf (f, " %s -> %s\n", reg_class_names[i],
1405 reg_class_names[class_translate[i]]);
1408 /* Output all possible allocno and translation classes and the
1409 translation maps into stderr. */
1410 void
1411 ira_debug_allocno_classes (void)
1413 print_unform_and_important_classes (stderr);
1414 print_translated_classes (stderr, false);
1415 print_translated_classes (stderr, true);
1418 /* Set up different arrays concerning class subsets, allocno and
1419 important classes. */
1420 static void
1421 find_reg_classes (void)
1423 setup_allocno_and_important_classes ();
1424 setup_class_translate ();
1425 reorder_important_classes ();
1426 setup_reg_class_relations ();
1431 /* Set up the array above. */
1432 static void
1433 setup_hard_regno_aclass (void)
1435 int i;
1437 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1439 #if 1
1440 ira_hard_regno_allocno_class[i]
1441 = (TEST_HARD_REG_BIT (no_unit_alloc_regs, i)
1442 ? NO_REGS
1443 : ira_allocno_class_translate[REGNO_REG_CLASS (i)]);
1444 #else
1445 int j;
1446 enum reg_class cl;
1447 ira_hard_regno_allocno_class[i] = NO_REGS;
1448 for (j = 0; j < ira_allocno_classes_num; j++)
1450 cl = ira_allocno_classes[j];
1451 if (ira_class_hard_reg_index[cl][i] >= 0)
1453 ira_hard_regno_allocno_class[i] = cl;
1454 break;
1457 #endif
1463 /* Form IRA_REG_CLASS_MAX_NREGS and IRA_REG_CLASS_MIN_NREGS maps. */
1464 static void
1465 setup_reg_class_nregs (void)
1467 int i, cl, cl2, m;
1469 for (m = 0; m < MAX_MACHINE_MODE; m++)
1471 for (cl = 0; cl < N_REG_CLASSES; cl++)
1472 ira_reg_class_max_nregs[cl][m]
1473 = ira_reg_class_min_nregs[cl][m]
1474 = targetm.class_max_nregs ((reg_class_t) cl, (enum machine_mode) m);
1475 for (cl = 0; cl < N_REG_CLASSES; cl++)
1476 for (i = 0;
1477 (cl2 = alloc_reg_class_subclasses[cl][i]) != LIM_REG_CLASSES;
1478 i++)
1479 if (ira_reg_class_min_nregs[cl2][m]
1480 < ira_reg_class_min_nregs[cl][m])
1481 ira_reg_class_min_nregs[cl][m] = ira_reg_class_min_nregs[cl2][m];
1487 /* Set up IRA_PROHIBITED_CLASS_MODE_REGS and IRA_CLASS_SINGLETON.
1488 This function is called once IRA_CLASS_HARD_REGS has been initialized. */
1489 static void
1490 setup_prohibited_class_mode_regs (void)
1492 int j, k, hard_regno, cl, last_hard_regno, count;
1494 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
1496 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
1497 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1498 for (j = 0; j < NUM_MACHINE_MODES; j++)
1500 count = 0;
1501 last_hard_regno = -1;
1502 CLEAR_HARD_REG_SET (ira_prohibited_class_mode_regs[cl][j]);
1503 for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1505 hard_regno = ira_class_hard_regs[cl][k];
1506 if (! HARD_REGNO_MODE_OK (hard_regno, (enum machine_mode) j))
1507 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1508 hard_regno);
1509 else if (in_hard_reg_set_p (temp_hard_regset,
1510 (enum machine_mode) j, hard_regno))
1512 last_hard_regno = hard_regno;
1513 count++;
1516 ira_class_singleton[cl][j] = (count == 1 ? last_hard_regno : -1);
1521 /* Clarify IRA_PROHIBITED_CLASS_MODE_REGS by excluding hard registers
1522 spanning from one register pressure class to another one. It is
1523 called after defining the pressure classes. */
1524 static void
1525 clarify_prohibited_class_mode_regs (void)
1527 int j, k, hard_regno, cl, pclass, nregs;
1529 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
1530 for (j = 0; j < NUM_MACHINE_MODES; j++)
1532 CLEAR_HARD_REG_SET (ira_useful_class_mode_regs[cl][j]);
1533 for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1535 hard_regno = ira_class_hard_regs[cl][k];
1536 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j], hard_regno))
1537 continue;
1538 nregs = hard_regno_nregs[hard_regno][j];
1539 if (hard_regno + nregs > FIRST_PSEUDO_REGISTER)
1541 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1542 hard_regno);
1543 continue;
1545 pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)];
1546 for (nregs-- ;nregs >= 0; nregs--)
1547 if (((enum reg_class) pclass
1548 != ira_pressure_class_translate[REGNO_REG_CLASS
1549 (hard_regno + nregs)]))
1551 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1552 hard_regno);
1553 break;
1555 if (!TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1556 hard_regno))
1557 add_to_hard_reg_set (&ira_useful_class_mode_regs[cl][j],
1558 (enum machine_mode) j, hard_regno);
1563 /* Allocate and initialize IRA_REGISTER_MOVE_COST, IRA_MAY_MOVE_IN_COST
1564 and IRA_MAY_MOVE_OUT_COST for MODE. */
1565 void
1566 ira_init_register_move_cost (enum machine_mode mode)
1568 static unsigned short last_move_cost[N_REG_CLASSES][N_REG_CLASSES];
1569 bool all_match = true;
1570 unsigned int cl1, cl2;
1572 ira_assert (ira_register_move_cost[mode] == NULL
1573 && ira_may_move_in_cost[mode] == NULL
1574 && ira_may_move_out_cost[mode] == NULL);
1575 ira_assert (have_regs_of_mode[mode]);
1576 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1577 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1579 int cost;
1580 if (!contains_reg_of_mode[cl1][mode]
1581 || !contains_reg_of_mode[cl2][mode])
1583 if ((ira_reg_class_max_nregs[cl1][mode]
1584 > ira_class_hard_regs_num[cl1])
1585 || (ira_reg_class_max_nregs[cl2][mode]
1586 > ira_class_hard_regs_num[cl2]))
1587 cost = 65535;
1588 else
1589 cost = (ira_memory_move_cost[mode][cl1][0]
1590 + ira_memory_move_cost[mode][cl2][1]) * 2;
1592 else
1594 cost = register_move_cost (mode, (enum reg_class) cl1,
1595 (enum reg_class) cl2);
1596 ira_assert (cost < 65535);
1598 all_match &= (last_move_cost[cl1][cl2] == cost);
1599 last_move_cost[cl1][cl2] = cost;
1601 if (all_match && last_mode_for_init_move_cost != -1)
1603 ira_register_move_cost[mode]
1604 = ira_register_move_cost[last_mode_for_init_move_cost];
1605 ira_may_move_in_cost[mode]
1606 = ira_may_move_in_cost[last_mode_for_init_move_cost];
1607 ira_may_move_out_cost[mode]
1608 = ira_may_move_out_cost[last_mode_for_init_move_cost];
1609 return;
1611 last_mode_for_init_move_cost = mode;
1612 ira_register_move_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1613 ira_may_move_in_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1614 ira_may_move_out_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1615 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1616 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1618 int cost;
1619 enum reg_class *p1, *p2;
1621 if (last_move_cost[cl1][cl2] == 65535)
1623 ira_register_move_cost[mode][cl1][cl2] = 65535;
1624 ira_may_move_in_cost[mode][cl1][cl2] = 65535;
1625 ira_may_move_out_cost[mode][cl1][cl2] = 65535;
1627 else
1629 cost = last_move_cost[cl1][cl2];
1631 for (p2 = &reg_class_subclasses[cl2][0];
1632 *p2 != LIM_REG_CLASSES; p2++)
1633 if (ira_class_hard_regs_num[*p2] > 0
1634 && (ira_reg_class_max_nregs[*p2][mode]
1635 <= ira_class_hard_regs_num[*p2]))
1636 cost = MAX (cost, ira_register_move_cost[mode][cl1][*p2]);
1638 for (p1 = &reg_class_subclasses[cl1][0];
1639 *p1 != LIM_REG_CLASSES; p1++)
1640 if (ira_class_hard_regs_num[*p1] > 0
1641 && (ira_reg_class_max_nregs[*p1][mode]
1642 <= ira_class_hard_regs_num[*p1]))
1643 cost = MAX (cost, ira_register_move_cost[mode][*p1][cl2]);
1645 ira_assert (cost <= 65535);
1646 ira_register_move_cost[mode][cl1][cl2] = cost;
1648 if (ira_class_subset_p[cl1][cl2])
1649 ira_may_move_in_cost[mode][cl1][cl2] = 0;
1650 else
1651 ira_may_move_in_cost[mode][cl1][cl2] = cost;
1653 if (ira_class_subset_p[cl2][cl1])
1654 ira_may_move_out_cost[mode][cl1][cl2] = 0;
1655 else
1656 ira_may_move_out_cost[mode][cl1][cl2] = cost;
1663 /* This is called once during compiler work. It sets up
1664 different arrays whose values don't depend on the compiled
1665 function. */
1666 void
1667 ira_init_once (void)
1669 ira_init_costs_once ();
1670 lra_init_once ();
1673 /* Free ira_max_register_move_cost, ira_may_move_in_cost and
1674 ira_may_move_out_cost for each mode. */
1675 static void
1676 free_register_move_costs (void)
1678 int mode, i;
1680 /* Reset move_cost and friends, making sure we only free shared
1681 table entries once. */
1682 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1683 if (ira_register_move_cost[mode])
1685 for (i = 0;
1686 i < mode && (ira_register_move_cost[i]
1687 != ira_register_move_cost[mode]);
1688 i++)
1690 if (i == mode)
1692 free (ira_register_move_cost[mode]);
1693 free (ira_may_move_in_cost[mode]);
1694 free (ira_may_move_out_cost[mode]);
1697 memset (ira_register_move_cost, 0, sizeof ira_register_move_cost);
1698 memset (ira_may_move_in_cost, 0, sizeof ira_may_move_in_cost);
1699 memset (ira_may_move_out_cost, 0, sizeof ira_may_move_out_cost);
1700 last_mode_for_init_move_cost = -1;
1703 /* This is called every time when register related information is
1704 changed. */
1705 void
1706 ira_init (void)
1708 free_register_move_costs ();
1709 setup_reg_mode_hard_regset ();
1710 setup_alloc_regs (flag_omit_frame_pointer != 0);
1711 setup_class_subset_and_memory_move_costs ();
1712 setup_reg_class_nregs ();
1713 setup_prohibited_class_mode_regs ();
1714 find_reg_classes ();
1715 clarify_prohibited_class_mode_regs ();
1716 setup_hard_regno_aclass ();
1717 ira_init_costs ();
1720 /* Function called once at the end of compiler work. */
1721 void
1722 ira_finish_once (void)
1724 ira_finish_costs_once ();
1725 free_register_move_costs ();
1726 lra_finish_once ();
1730 #define ira_prohibited_mode_move_regs_initialized_p \
1731 (this_target_ira_int->x_ira_prohibited_mode_move_regs_initialized_p)
1733 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS. */
1734 static void
1735 setup_prohibited_mode_move_regs (void)
1737 int i, j;
1738 rtx test_reg1, test_reg2, move_pat, move_insn;
1740 if (ira_prohibited_mode_move_regs_initialized_p)
1741 return;
1742 ira_prohibited_mode_move_regs_initialized_p = true;
1743 test_reg1 = gen_rtx_REG (VOIDmode, 0);
1744 test_reg2 = gen_rtx_REG (VOIDmode, 0);
1745 move_pat = gen_rtx_SET (VOIDmode, test_reg1, test_reg2);
1746 move_insn = gen_rtx_INSN (VOIDmode, 0, 0, 0, move_pat, 0, -1, 0);
1747 for (i = 0; i < NUM_MACHINE_MODES; i++)
1749 SET_HARD_REG_SET (ira_prohibited_mode_move_regs[i]);
1750 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1752 if (! HARD_REGNO_MODE_OK (j, (enum machine_mode) i))
1753 continue;
1754 SET_REGNO_RAW (test_reg1, j);
1755 PUT_MODE (test_reg1, (enum machine_mode) i);
1756 SET_REGNO_RAW (test_reg2, j);
1757 PUT_MODE (test_reg2, (enum machine_mode) i);
1758 INSN_CODE (move_insn) = -1;
1759 recog_memoized (move_insn);
1760 if (INSN_CODE (move_insn) < 0)
1761 continue;
1762 extract_insn (move_insn);
1763 if (! constrain_operands (1))
1764 continue;
1765 CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs[i], j);
1772 /* Setup possible alternatives in ALTS for INSN. */
1773 void
1774 ira_setup_alts (rtx insn, HARD_REG_SET &alts)
1776 /* MAP nalt * nop -> start of constraints for given operand and
1777 alternative */
1778 static vec<const char *> insn_constraints;
1779 int nop, nalt;
1780 bool curr_swapped;
1781 const char *p;
1782 rtx op;
1783 int commutative = -1;
1785 extract_insn (insn);
1786 CLEAR_HARD_REG_SET (alts);
1787 insn_constraints.release ();
1788 insn_constraints.safe_grow_cleared (recog_data.n_operands
1789 * recog_data.n_alternatives + 1);
1790 /* Check that the hard reg set is enough for holding all
1791 alternatives. It is hard to imagine the situation when the
1792 assertion is wrong. */
1793 ira_assert (recog_data.n_alternatives
1794 <= (int) MAX (sizeof (HARD_REG_ELT_TYPE) * CHAR_BIT,
1795 FIRST_PSEUDO_REGISTER));
1796 for (curr_swapped = false;; curr_swapped = true)
1798 /* Calculate some data common for all alternatives to speed up the
1799 function. */
1800 for (nop = 0; nop < recog_data.n_operands; nop++)
1802 for (nalt = 0, p = recog_data.constraints[nop];
1803 nalt < recog_data.n_alternatives;
1804 nalt++)
1806 insn_constraints[nop * recog_data.n_alternatives + nalt] = p;
1807 while (*p && *p != ',')
1808 p++;
1809 if (*p)
1810 p++;
1813 for (nalt = 0; nalt < recog_data.n_alternatives; nalt++)
1815 if (!TEST_BIT (recog_data.enabled_alternatives, nalt)
1816 || TEST_HARD_REG_BIT (alts, nalt))
1817 continue;
1819 for (nop = 0; nop < recog_data.n_operands; nop++)
1821 int c, len;
1823 op = recog_data.operand[nop];
1824 p = insn_constraints[nop * recog_data.n_alternatives + nalt];
1825 if (*p == 0 || *p == ',')
1826 continue;
1829 switch (c = *p, len = CONSTRAINT_LEN (c, p), c)
1831 case '#':
1832 case ',':
1833 c = '\0';
1834 case '\0':
1835 len = 0;
1836 break;
1838 case '%':
1839 /* We only support one commutative marker, the
1840 first one. We already set commutative
1841 above. */
1842 if (commutative < 0)
1843 commutative = nop;
1844 break;
1846 case '0': case '1': case '2': case '3': case '4':
1847 case '5': case '6': case '7': case '8': case '9':
1848 goto op_success;
1849 break;
1851 case 'g':
1852 goto op_success;
1853 break;
1855 default:
1857 enum constraint_num cn = lookup_constraint (p);
1858 switch (get_constraint_type (cn))
1860 case CT_REGISTER:
1861 if (reg_class_for_constraint (cn) != NO_REGS)
1862 goto op_success;
1863 break;
1865 case CT_CONST_INT:
1866 if (CONST_INT_P (op)
1867 && (insn_const_int_ok_for_constraint
1868 (INTVAL (op), cn)))
1869 goto op_success;
1870 break;
1872 case CT_ADDRESS:
1873 case CT_MEMORY:
1874 goto op_success;
1876 case CT_FIXED_FORM:
1877 if (constraint_satisfied_p (op, cn))
1878 goto op_success;
1879 break;
1881 break;
1884 while (p += len, c);
1885 break;
1886 op_success:
1889 if (nop >= recog_data.n_operands)
1890 SET_HARD_REG_BIT (alts, nalt);
1892 if (commutative < 0)
1893 break;
1894 if (curr_swapped)
1895 break;
1896 op = recog_data.operand[commutative];
1897 recog_data.operand[commutative] = recog_data.operand[commutative + 1];
1898 recog_data.operand[commutative + 1] = op;
1903 /* Return the number of the output non-early clobber operand which
1904 should be the same in any case as operand with number OP_NUM (or
1905 negative value if there is no such operand). The function takes
1906 only really possible alternatives into consideration. */
1908 ira_get_dup_out_num (int op_num, HARD_REG_SET &alts)
1910 int curr_alt, c, original, dup;
1911 bool ignore_p, use_commut_op_p;
1912 const char *str;
1914 if (op_num < 0 || recog_data.n_alternatives == 0)
1915 return -1;
1916 /* We should find duplications only for input operands. */
1917 if (recog_data.operand_type[op_num] != OP_IN)
1918 return -1;
1919 str = recog_data.constraints[op_num];
1920 use_commut_op_p = false;
1921 for (;;)
1923 rtx op = recog_data.operand[op_num];
1925 for (curr_alt = 0, ignore_p = !TEST_HARD_REG_BIT (alts, curr_alt),
1926 original = -1;;)
1928 c = *str;
1929 if (c == '\0')
1930 break;
1931 if (c == '#')
1932 ignore_p = true;
1933 else if (c == ',')
1935 curr_alt++;
1936 ignore_p = !TEST_HARD_REG_BIT (alts, curr_alt);
1938 else if (! ignore_p)
1939 switch (c)
1941 case 'g':
1942 goto fail;
1943 default:
1945 enum constraint_num cn = lookup_constraint (str);
1946 enum reg_class cl = reg_class_for_constraint (cn);
1947 if (cl != NO_REGS
1948 && !targetm.class_likely_spilled_p (cl))
1949 goto fail;
1950 if (constraint_satisfied_p (op, cn))
1951 goto fail;
1952 break;
1955 case '0': case '1': case '2': case '3': case '4':
1956 case '5': case '6': case '7': case '8': case '9':
1957 if (original != -1 && original != c)
1958 goto fail;
1959 original = c;
1960 break;
1962 str += CONSTRAINT_LEN (c, str);
1964 if (original == -1)
1965 goto fail;
1966 dup = -1;
1967 for (ignore_p = false, str = recog_data.constraints[original - '0'];
1968 *str != 0;
1969 str++)
1970 if (ignore_p)
1972 if (*str == ',')
1973 ignore_p = false;
1975 else if (*str == '#')
1976 ignore_p = true;
1977 else if (! ignore_p)
1979 if (*str == '=')
1980 dup = original - '0';
1981 /* It is better ignore an alternative with early clobber. */
1982 else if (*str == '&')
1983 goto fail;
1985 if (dup >= 0)
1986 return dup;
1987 fail:
1988 if (use_commut_op_p)
1989 break;
1990 use_commut_op_p = true;
1991 if (recog_data.constraints[op_num][0] == '%')
1992 str = recog_data.constraints[op_num + 1];
1993 else if (op_num > 0 && recog_data.constraints[op_num - 1][0] == '%')
1994 str = recog_data.constraints[op_num - 1];
1995 else
1996 break;
1998 return -1;
2003 /* Search forward to see if the source register of a copy insn dies
2004 before either it or the destination register is modified, but don't
2005 scan past the end of the basic block. If so, we can replace the
2006 source with the destination and let the source die in the copy
2007 insn.
2009 This will reduce the number of registers live in that range and may
2010 enable the destination and the source coalescing, thus often saving
2011 one register in addition to a register-register copy. */
2013 static void
2014 decrease_live_ranges_number (void)
2016 basic_block bb;
2017 rtx insn, set, src, dest, dest_death, p, q, note;
2018 int sregno, dregno;
2020 if (! flag_expensive_optimizations)
2021 return;
2023 if (ira_dump_file)
2024 fprintf (ira_dump_file, "Starting decreasing number of live ranges...\n");
2026 FOR_EACH_BB_FN (bb, cfun)
2027 FOR_BB_INSNS (bb, insn)
2029 set = single_set (insn);
2030 if (! set)
2031 continue;
2032 src = SET_SRC (set);
2033 dest = SET_DEST (set);
2034 if (! REG_P (src) || ! REG_P (dest)
2035 || find_reg_note (insn, REG_DEAD, src))
2036 continue;
2037 sregno = REGNO (src);
2038 dregno = REGNO (dest);
2040 /* We don't want to mess with hard regs if register classes
2041 are small. */
2042 if (sregno == dregno
2043 || (targetm.small_register_classes_for_mode_p (GET_MODE (src))
2044 && (sregno < FIRST_PSEUDO_REGISTER
2045 || dregno < FIRST_PSEUDO_REGISTER))
2046 /* We don't see all updates to SP if they are in an
2047 auto-inc memory reference, so we must disallow this
2048 optimization on them. */
2049 || sregno == STACK_POINTER_REGNUM
2050 || dregno == STACK_POINTER_REGNUM)
2051 continue;
2053 dest_death = NULL_RTX;
2055 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
2057 if (! INSN_P (p))
2058 continue;
2059 if (BLOCK_FOR_INSN (p) != bb)
2060 break;
2062 if (reg_set_p (src, p) || reg_set_p (dest, p)
2063 /* If SRC is an asm-declared register, it must not be
2064 replaced in any asm. Unfortunately, the REG_EXPR
2065 tree for the asm variable may be absent in the SRC
2066 rtx, so we can't check the actual register
2067 declaration easily (the asm operand will have it,
2068 though). To avoid complicating the test for a rare
2069 case, we just don't perform register replacement
2070 for a hard reg mentioned in an asm. */
2071 || (sregno < FIRST_PSEUDO_REGISTER
2072 && asm_noperands (PATTERN (p)) >= 0
2073 && reg_overlap_mentioned_p (src, PATTERN (p)))
2074 /* Don't change hard registers used by a call. */
2075 || (CALL_P (p) && sregno < FIRST_PSEUDO_REGISTER
2076 && find_reg_fusage (p, USE, src))
2077 /* Don't change a USE of a register. */
2078 || (GET_CODE (PATTERN (p)) == USE
2079 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
2080 break;
2082 /* See if all of SRC dies in P. This test is slightly
2083 more conservative than it needs to be. */
2084 if ((note = find_regno_note (p, REG_DEAD, sregno))
2085 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
2087 int failed = 0;
2089 /* We can do the optimization. Scan forward from INSN
2090 again, replacing regs as we go. Set FAILED if a
2091 replacement can't be done. In that case, we can't
2092 move the death note for SRC. This should be
2093 rare. */
2095 /* Set to stop at next insn. */
2096 for (q = next_real_insn (insn);
2097 q != next_real_insn (p);
2098 q = next_real_insn (q))
2100 if (reg_overlap_mentioned_p (src, PATTERN (q)))
2102 /* If SRC is a hard register, we might miss
2103 some overlapping registers with
2104 validate_replace_rtx, so we would have to
2105 undo it. We can't if DEST is present in
2106 the insn, so fail in that combination of
2107 cases. */
2108 if (sregno < FIRST_PSEUDO_REGISTER
2109 && reg_mentioned_p (dest, PATTERN (q)))
2110 failed = 1;
2112 /* Attempt to replace all uses. */
2113 else if (!validate_replace_rtx (src, dest, q))
2114 failed = 1;
2116 /* If this succeeded, but some part of the
2117 register is still present, undo the
2118 replacement. */
2119 else if (sregno < FIRST_PSEUDO_REGISTER
2120 && reg_overlap_mentioned_p (src, PATTERN (q)))
2122 validate_replace_rtx (dest, src, q);
2123 failed = 1;
2127 /* If DEST dies here, remove the death note and
2128 save it for later. Make sure ALL of DEST dies
2129 here; again, this is overly conservative. */
2130 if (! dest_death
2131 && (dest_death = find_regno_note (q, REG_DEAD, dregno)))
2133 if (GET_MODE (XEXP (dest_death, 0)) == GET_MODE (dest))
2134 remove_note (q, dest_death);
2135 else
2137 failed = 1;
2138 dest_death = 0;
2143 if (! failed)
2145 /* Move death note of SRC from P to INSN. */
2146 remove_note (p, note);
2147 XEXP (note, 1) = REG_NOTES (insn);
2148 REG_NOTES (insn) = note;
2151 /* DEST is also dead if INSN has a REG_UNUSED note for
2152 DEST. */
2153 if (! dest_death
2154 && (dest_death
2155 = find_regno_note (insn, REG_UNUSED, dregno)))
2157 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
2158 remove_note (insn, dest_death);
2161 /* Put death note of DEST on P if we saw it die. */
2162 if (dest_death)
2164 XEXP (dest_death, 1) = REG_NOTES (p);
2165 REG_NOTES (p) = dest_death;
2167 break;
2170 /* If SRC is a hard register which is set or killed in
2171 some other way, we can't do this optimization. */
2172 else if (sregno < FIRST_PSEUDO_REGISTER && dead_or_set_p (p, src))
2173 break;
2180 /* Return nonzero if REGNO is a particularly bad choice for reloading X. */
2181 static bool
2182 ira_bad_reload_regno_1 (int regno, rtx x)
2184 int x_regno, n, i;
2185 ira_allocno_t a;
2186 enum reg_class pref;
2188 /* We only deal with pseudo regs. */
2189 if (! x || GET_CODE (x) != REG)
2190 return false;
2192 x_regno = REGNO (x);
2193 if (x_regno < FIRST_PSEUDO_REGISTER)
2194 return false;
2196 /* If the pseudo prefers REGNO explicitly, then do not consider
2197 REGNO a bad spill choice. */
2198 pref = reg_preferred_class (x_regno);
2199 if (reg_class_size[pref] == 1)
2200 return !TEST_HARD_REG_BIT (reg_class_contents[pref], regno);
2202 /* If the pseudo conflicts with REGNO, then we consider REGNO a
2203 poor choice for a reload regno. */
2204 a = ira_regno_allocno_map[x_regno];
2205 n = ALLOCNO_NUM_OBJECTS (a);
2206 for (i = 0; i < n; i++)
2208 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2209 if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), regno))
2210 return true;
2212 return false;
2215 /* Return nonzero if REGNO is a particularly bad choice for reloading
2216 IN or OUT. */
2217 bool
2218 ira_bad_reload_regno (int regno, rtx in, rtx out)
2220 return (ira_bad_reload_regno_1 (regno, in)
2221 || ira_bad_reload_regno_1 (regno, out));
2224 /* Return TRUE if *LOC contains an asm. */
2225 static int
2226 insn_contains_asm_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
2228 if ( !*loc)
2229 return FALSE;
2230 if (GET_CODE (*loc) == ASM_OPERANDS)
2231 return TRUE;
2232 return FALSE;
2236 /* Return TRUE if INSN contains an ASM. */
2237 static bool
2238 insn_contains_asm (rtx insn)
2240 return for_each_rtx (&insn, insn_contains_asm_1, NULL);
2243 /* Add register clobbers from asm statements. */
2244 static void
2245 compute_regs_asm_clobbered (void)
2247 basic_block bb;
2249 FOR_EACH_BB_FN (bb, cfun)
2251 rtx insn;
2252 FOR_BB_INSNS_REVERSE (bb, insn)
2254 df_ref def;
2256 if (insn_contains_asm (insn))
2257 FOR_EACH_INSN_DEF (def, insn)
2259 unsigned int dregno = DF_REF_REGNO (def);
2260 if (HARD_REGISTER_NUM_P (dregno))
2261 add_to_hard_reg_set (&crtl->asm_clobbers,
2262 GET_MODE (DF_REF_REAL_REG (def)),
2263 dregno);
2270 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and
2271 REGS_EVER_LIVE. */
2272 void
2273 ira_setup_eliminable_regset (void)
2275 #ifdef ELIMINABLE_REGS
2276 int i;
2277 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
2278 #endif
2279 /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
2280 sp for alloca. So we can't eliminate the frame pointer in that
2281 case. At some point, we should improve this by emitting the
2282 sp-adjusting insns for this case. */
2283 frame_pointer_needed
2284 = (! flag_omit_frame_pointer
2285 || (cfun->calls_alloca && EXIT_IGNORE_STACK)
2286 /* We need the frame pointer to catch stack overflow exceptions
2287 if the stack pointer is moving. */
2288 || (flag_stack_check && STACK_CHECK_MOVING_SP)
2289 || crtl->accesses_prior_frames
2290 || (SUPPORTS_STACK_ALIGNMENT && crtl->stack_realign_needed)
2291 /* We need a frame pointer for all Cilk Plus functions that use
2292 Cilk keywords. */
2293 || (flag_cilkplus && cfun->is_cilk_function)
2294 || targetm.frame_pointer_required ());
2296 /* The chance that FRAME_POINTER_NEEDED is changed from inspecting
2297 RTL is very small. So if we use frame pointer for RA and RTL
2298 actually prevents this, we will spill pseudos assigned to the
2299 frame pointer in LRA. */
2301 if (frame_pointer_needed)
2302 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
2304 COPY_HARD_REG_SET (ira_no_alloc_regs, no_unit_alloc_regs);
2305 CLEAR_HARD_REG_SET (eliminable_regset);
2307 compute_regs_asm_clobbered ();
2309 /* Build the regset of all eliminable registers and show we can't
2310 use those that we already know won't be eliminated. */
2311 #ifdef ELIMINABLE_REGS
2312 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
2314 bool cannot_elim
2315 = (! targetm.can_eliminate (eliminables[i].from, eliminables[i].to)
2316 || (eliminables[i].to == STACK_POINTER_REGNUM && frame_pointer_needed));
2318 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, eliminables[i].from))
2320 SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
2322 if (cannot_elim)
2323 SET_HARD_REG_BIT (ira_no_alloc_regs, eliminables[i].from);
2325 else if (cannot_elim)
2326 error ("%s cannot be used in asm here",
2327 reg_names[eliminables[i].from]);
2328 else
2329 df_set_regs_ever_live (eliminables[i].from, true);
2331 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
2332 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM))
2334 SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
2335 if (frame_pointer_needed)
2336 SET_HARD_REG_BIT (ira_no_alloc_regs, HARD_FRAME_POINTER_REGNUM);
2338 else if (frame_pointer_needed)
2339 error ("%s cannot be used in asm here",
2340 reg_names[HARD_FRAME_POINTER_REGNUM]);
2341 else
2342 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
2343 #endif
2345 #else
2346 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM))
2348 SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
2349 if (frame_pointer_needed)
2350 SET_HARD_REG_BIT (ira_no_alloc_regs, FRAME_POINTER_REGNUM);
2352 else if (frame_pointer_needed)
2353 error ("%s cannot be used in asm here", reg_names[FRAME_POINTER_REGNUM]);
2354 else
2355 df_set_regs_ever_live (FRAME_POINTER_REGNUM, true);
2356 #endif
2361 /* Vector of substitutions of register numbers,
2362 used to map pseudo regs into hardware regs.
2363 This is set up as a result of register allocation.
2364 Element N is the hard reg assigned to pseudo reg N,
2365 or is -1 if no hard reg was assigned.
2366 If N is a hard reg number, element N is N. */
2367 short *reg_renumber;
2369 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
2370 the allocation found by IRA. */
2371 static void
2372 setup_reg_renumber (void)
2374 int regno, hard_regno;
2375 ira_allocno_t a;
2376 ira_allocno_iterator ai;
2378 caller_save_needed = 0;
2379 FOR_EACH_ALLOCNO (a, ai)
2381 if (ira_use_lra_p && ALLOCNO_CAP_MEMBER (a) != NULL)
2382 continue;
2383 /* There are no caps at this point. */
2384 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2385 if (! ALLOCNO_ASSIGNED_P (a))
2386 /* It can happen if A is not referenced but partially anticipated
2387 somewhere in a region. */
2388 ALLOCNO_ASSIGNED_P (a) = true;
2389 ira_free_allocno_updated_costs (a);
2390 hard_regno = ALLOCNO_HARD_REGNO (a);
2391 regno = ALLOCNO_REGNO (a);
2392 reg_renumber[regno] = (hard_regno < 0 ? -1 : hard_regno);
2393 if (hard_regno >= 0)
2395 int i, nwords;
2396 enum reg_class pclass;
2397 ira_object_t obj;
2399 pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)];
2400 nwords = ALLOCNO_NUM_OBJECTS (a);
2401 for (i = 0; i < nwords; i++)
2403 obj = ALLOCNO_OBJECT (a, i);
2404 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
2405 reg_class_contents[pclass]);
2407 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
2408 && ira_hard_reg_set_intersection_p (hard_regno, ALLOCNO_MODE (a),
2409 call_used_reg_set))
2411 ira_assert (!optimize || flag_caller_saves
2412 || (ALLOCNO_CALLS_CROSSED_NUM (a)
2413 == ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a))
2414 || regno >= ira_reg_equiv_len
2415 || ira_equiv_no_lvalue_p (regno));
2416 caller_save_needed = 1;
2422 /* Set up allocno assignment flags for further allocation
2423 improvements. */
2424 static void
2425 setup_allocno_assignment_flags (void)
2427 int hard_regno;
2428 ira_allocno_t a;
2429 ira_allocno_iterator ai;
2431 FOR_EACH_ALLOCNO (a, ai)
2433 if (! ALLOCNO_ASSIGNED_P (a))
2434 /* It can happen if A is not referenced but partially anticipated
2435 somewhere in a region. */
2436 ira_free_allocno_updated_costs (a);
2437 hard_regno = ALLOCNO_HARD_REGNO (a);
2438 /* Don't assign hard registers to allocnos which are destination
2439 of removed store at the end of loop. It has no sense to keep
2440 the same value in different hard registers. It is also
2441 impossible to assign hard registers correctly to such
2442 allocnos because the cost info and info about intersected
2443 calls are incorrect for them. */
2444 ALLOCNO_ASSIGNED_P (a) = (hard_regno >= 0
2445 || ALLOCNO_EMIT_DATA (a)->mem_optimized_dest_p
2446 || (ALLOCNO_MEMORY_COST (a)
2447 - ALLOCNO_CLASS_COST (a)) < 0);
2448 ira_assert
2449 (hard_regno < 0
2450 || ira_hard_reg_in_set_p (hard_regno, ALLOCNO_MODE (a),
2451 reg_class_contents[ALLOCNO_CLASS (a)]));
2455 /* Evaluate overall allocation cost and the costs for using hard
2456 registers and memory for allocnos. */
2457 static void
2458 calculate_allocation_cost (void)
2460 int hard_regno, cost;
2461 ira_allocno_t a;
2462 ira_allocno_iterator ai;
2464 ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
2465 FOR_EACH_ALLOCNO (a, ai)
2467 hard_regno = ALLOCNO_HARD_REGNO (a);
2468 ira_assert (hard_regno < 0
2469 || (ira_hard_reg_in_set_p
2470 (hard_regno, ALLOCNO_MODE (a),
2471 reg_class_contents[ALLOCNO_CLASS (a)])));
2472 if (hard_regno < 0)
2474 cost = ALLOCNO_MEMORY_COST (a);
2475 ira_mem_cost += cost;
2477 else if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
2479 cost = (ALLOCNO_HARD_REG_COSTS (a)
2480 [ira_class_hard_reg_index
2481 [ALLOCNO_CLASS (a)][hard_regno]]);
2482 ira_reg_cost += cost;
2484 else
2486 cost = ALLOCNO_CLASS_COST (a);
2487 ira_reg_cost += cost;
2489 ira_overall_cost += cost;
2492 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2494 fprintf (ira_dump_file,
2495 "+++Costs: overall %d, reg %d, mem %d, ld %d, st %d, move %d\n",
2496 ira_overall_cost, ira_reg_cost, ira_mem_cost,
2497 ira_load_cost, ira_store_cost, ira_shuffle_cost);
2498 fprintf (ira_dump_file, "+++ move loops %d, new jumps %d\n",
2499 ira_move_loops_num, ira_additional_jumps_num);
2504 #ifdef ENABLE_IRA_CHECKING
2505 /* Check the correctness of the allocation. We do need this because
2506 of complicated code to transform more one region internal
2507 representation into one region representation. */
2508 static void
2509 check_allocation (void)
2511 ira_allocno_t a;
2512 int hard_regno, nregs, conflict_nregs;
2513 ira_allocno_iterator ai;
2515 FOR_EACH_ALLOCNO (a, ai)
2517 int n = ALLOCNO_NUM_OBJECTS (a);
2518 int i;
2520 if (ALLOCNO_CAP_MEMBER (a) != NULL
2521 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
2522 continue;
2523 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
2524 if (nregs == 1)
2525 /* We allocated a single hard register. */
2526 n = 1;
2527 else if (n > 1)
2528 /* We allocated multiple hard registers, and we will test
2529 conflicts in a granularity of single hard regs. */
2530 nregs = 1;
2532 for (i = 0; i < n; i++)
2534 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2535 ira_object_t conflict_obj;
2536 ira_object_conflict_iterator oci;
2537 int this_regno = hard_regno;
2538 if (n > 1)
2540 if (REG_WORDS_BIG_ENDIAN)
2541 this_regno += n - i - 1;
2542 else
2543 this_regno += i;
2545 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2547 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2548 int conflict_hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
2549 if (conflict_hard_regno < 0)
2550 continue;
2552 conflict_nregs
2553 = (hard_regno_nregs
2554 [conflict_hard_regno][ALLOCNO_MODE (conflict_a)]);
2556 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1
2557 && conflict_nregs == ALLOCNO_NUM_OBJECTS (conflict_a))
2559 if (REG_WORDS_BIG_ENDIAN)
2560 conflict_hard_regno += (ALLOCNO_NUM_OBJECTS (conflict_a)
2561 - OBJECT_SUBWORD (conflict_obj) - 1);
2562 else
2563 conflict_hard_regno += OBJECT_SUBWORD (conflict_obj);
2564 conflict_nregs = 1;
2567 if ((conflict_hard_regno <= this_regno
2568 && this_regno < conflict_hard_regno + conflict_nregs)
2569 || (this_regno <= conflict_hard_regno
2570 && conflict_hard_regno < this_regno + nregs))
2572 fprintf (stderr, "bad allocation for %d and %d\n",
2573 ALLOCNO_REGNO (a), ALLOCNO_REGNO (conflict_a));
2574 gcc_unreachable ();
2580 #endif
2582 /* Allocate REG_EQUIV_INIT. Set up it from IRA_REG_EQUIV which should
2583 be already calculated. */
2584 static void
2585 setup_reg_equiv_init (void)
2587 int i;
2588 int max_regno = max_reg_num ();
2590 for (i = 0; i < max_regno; i++)
2591 reg_equiv_init (i) = ira_reg_equiv[i].init_insns;
2594 /* Update equiv regno from movement of FROM_REGNO to TO_REGNO. INSNS
2595 are insns which were generated for such movement. It is assumed
2596 that FROM_REGNO and TO_REGNO always have the same value at the
2597 point of any move containing such registers. This function is used
2598 to update equiv info for register shuffles on the region borders
2599 and for caller save/restore insns. */
2600 void
2601 ira_update_equiv_info_by_shuffle_insn (int to_regno, int from_regno, rtx insns)
2603 rtx insn, x, note;
2605 if (! ira_reg_equiv[from_regno].defined_p
2606 && (! ira_reg_equiv[to_regno].defined_p
2607 || ((x = ira_reg_equiv[to_regno].memory) != NULL_RTX
2608 && ! MEM_READONLY_P (x))))
2609 return;
2610 insn = insns;
2611 if (NEXT_INSN (insn) != NULL_RTX)
2613 if (! ira_reg_equiv[to_regno].defined_p)
2615 ira_assert (ira_reg_equiv[to_regno].init_insns == NULL_RTX);
2616 return;
2618 ira_reg_equiv[to_regno].defined_p = false;
2619 ira_reg_equiv[to_regno].memory
2620 = ira_reg_equiv[to_regno].constant
2621 = ira_reg_equiv[to_regno].invariant
2622 = ira_reg_equiv[to_regno].init_insns = NULL_RTX;
2623 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2624 fprintf (ira_dump_file,
2625 " Invalidating equiv info for reg %d\n", to_regno);
2626 return;
2628 /* It is possible that FROM_REGNO still has no equivalence because
2629 in shuffles to_regno<-from_regno and from_regno<-to_regno the 2nd
2630 insn was not processed yet. */
2631 if (ira_reg_equiv[from_regno].defined_p)
2633 ira_reg_equiv[to_regno].defined_p = true;
2634 if ((x = ira_reg_equiv[from_regno].memory) != NULL_RTX)
2636 ira_assert (ira_reg_equiv[from_regno].invariant == NULL_RTX
2637 && ira_reg_equiv[from_regno].constant == NULL_RTX);
2638 ira_assert (ira_reg_equiv[to_regno].memory == NULL_RTX
2639 || rtx_equal_p (ira_reg_equiv[to_regno].memory, x));
2640 ira_reg_equiv[to_regno].memory = x;
2641 if (! MEM_READONLY_P (x))
2642 /* We don't add the insn to insn init list because memory
2643 equivalence is just to say what memory is better to use
2644 when the pseudo is spilled. */
2645 return;
2647 else if ((x = ira_reg_equiv[from_regno].constant) != NULL_RTX)
2649 ira_assert (ira_reg_equiv[from_regno].invariant == NULL_RTX);
2650 ira_assert (ira_reg_equiv[to_regno].constant == NULL_RTX
2651 || rtx_equal_p (ira_reg_equiv[to_regno].constant, x));
2652 ira_reg_equiv[to_regno].constant = x;
2654 else
2656 x = ira_reg_equiv[from_regno].invariant;
2657 ira_assert (x != NULL_RTX);
2658 ira_assert (ira_reg_equiv[to_regno].invariant == NULL_RTX
2659 || rtx_equal_p (ira_reg_equiv[to_regno].invariant, x));
2660 ira_reg_equiv[to_regno].invariant = x;
2662 if (find_reg_note (insn, REG_EQUIV, x) == NULL_RTX)
2664 note = set_unique_reg_note (insn, REG_EQUIV, x);
2665 gcc_assert (note != NULL_RTX);
2666 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2668 fprintf (ira_dump_file,
2669 " Adding equiv note to insn %u for reg %d ",
2670 INSN_UID (insn), to_regno);
2671 dump_value_slim (ira_dump_file, x, 1);
2672 fprintf (ira_dump_file, "\n");
2676 ira_reg_equiv[to_regno].init_insns
2677 = gen_rtx_INSN_LIST (VOIDmode, insn,
2678 ira_reg_equiv[to_regno].init_insns);
2679 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2680 fprintf (ira_dump_file,
2681 " Adding equiv init move insn %u to reg %d\n",
2682 INSN_UID (insn), to_regno);
2685 /* Fix values of array REG_EQUIV_INIT after live range splitting done
2686 by IRA. */
2687 static void
2688 fix_reg_equiv_init (void)
2690 int max_regno = max_reg_num ();
2691 int i, new_regno, max;
2692 rtx x, prev, next, insn, set;
2694 if (max_regno_before_ira < max_regno)
2696 max = vec_safe_length (reg_equivs);
2697 grow_reg_equivs ();
2698 for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
2699 for (prev = NULL_RTX, x = reg_equiv_init (i);
2700 x != NULL_RTX;
2701 x = next)
2703 next = XEXP (x, 1);
2704 insn = XEXP (x, 0);
2705 set = single_set (insn);
2706 ira_assert (set != NULL_RTX
2707 && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))));
2708 if (REG_P (SET_DEST (set))
2709 && ((int) REGNO (SET_DEST (set)) == i
2710 || (int) ORIGINAL_REGNO (SET_DEST (set)) == i))
2711 new_regno = REGNO (SET_DEST (set));
2712 else if (REG_P (SET_SRC (set))
2713 && ((int) REGNO (SET_SRC (set)) == i
2714 || (int) ORIGINAL_REGNO (SET_SRC (set)) == i))
2715 new_regno = REGNO (SET_SRC (set));
2716 else
2717 gcc_unreachable ();
2718 if (new_regno == i)
2719 prev = x;
2720 else
2722 /* Remove the wrong list element. */
2723 if (prev == NULL_RTX)
2724 reg_equiv_init (i) = next;
2725 else
2726 XEXP (prev, 1) = next;
2727 XEXP (x, 1) = reg_equiv_init (new_regno);
2728 reg_equiv_init (new_regno) = x;
2734 #ifdef ENABLE_IRA_CHECKING
2735 /* Print redundant memory-memory copies. */
2736 static void
2737 print_redundant_copies (void)
2739 int hard_regno;
2740 ira_allocno_t a;
2741 ira_copy_t cp, next_cp;
2742 ira_allocno_iterator ai;
2744 FOR_EACH_ALLOCNO (a, ai)
2746 if (ALLOCNO_CAP_MEMBER (a) != NULL)
2747 /* It is a cap. */
2748 continue;
2749 hard_regno = ALLOCNO_HARD_REGNO (a);
2750 if (hard_regno >= 0)
2751 continue;
2752 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2753 if (cp->first == a)
2754 next_cp = cp->next_first_allocno_copy;
2755 else
2757 next_cp = cp->next_second_allocno_copy;
2758 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL
2759 && cp->insn != NULL_RTX
2760 && ALLOCNO_HARD_REGNO (cp->first) == hard_regno)
2761 fprintf (ira_dump_file,
2762 " Redundant move from %d(freq %d):%d\n",
2763 INSN_UID (cp->insn), cp->freq, hard_regno);
2767 #endif
2769 /* Setup preferred and alternative classes for new pseudo-registers
2770 created by IRA starting with START. */
2771 static void
2772 setup_preferred_alternate_classes_for_new_pseudos (int start)
2774 int i, old_regno;
2775 int max_regno = max_reg_num ();
2777 for (i = start; i < max_regno; i++)
2779 old_regno = ORIGINAL_REGNO (regno_reg_rtx[i]);
2780 ira_assert (i != old_regno);
2781 setup_reg_classes (i, reg_preferred_class (old_regno),
2782 reg_alternate_class (old_regno),
2783 reg_allocno_class (old_regno));
2784 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2785 fprintf (ira_dump_file,
2786 " New r%d: setting preferred %s, alternative %s\n",
2787 i, reg_class_names[reg_preferred_class (old_regno)],
2788 reg_class_names[reg_alternate_class (old_regno)]);
2793 /* The number of entries allocated in teg_info. */
2794 static int allocated_reg_info_size;
2796 /* Regional allocation can create new pseudo-registers. This function
2797 expands some arrays for pseudo-registers. */
2798 static void
2799 expand_reg_info (void)
2801 int i;
2802 int size = max_reg_num ();
2804 resize_reg_info ();
2805 for (i = allocated_reg_info_size; i < size; i++)
2806 setup_reg_classes (i, GENERAL_REGS, ALL_REGS, GENERAL_REGS);
2807 setup_preferred_alternate_classes_for_new_pseudos (allocated_reg_info_size);
2808 allocated_reg_info_size = size;
2811 /* Return TRUE if there is too high register pressure in the function.
2812 It is used to decide when stack slot sharing is worth to do. */
2813 static bool
2814 too_high_register_pressure_p (void)
2816 int i;
2817 enum reg_class pclass;
2819 for (i = 0; i < ira_pressure_classes_num; i++)
2821 pclass = ira_pressure_classes[i];
2822 if (ira_loop_tree_root->reg_pressure[pclass] > 10000)
2823 return true;
2825 return false;
2830 /* Indicate that hard register number FROM was eliminated and replaced with
2831 an offset from hard register number TO. The status of hard registers live
2832 at the start of a basic block is updated by replacing a use of FROM with
2833 a use of TO. */
2835 void
2836 mark_elimination (int from, int to)
2838 basic_block bb;
2839 bitmap r;
2841 FOR_EACH_BB_FN (bb, cfun)
2843 r = DF_LR_IN (bb);
2844 if (bitmap_bit_p (r, from))
2846 bitmap_clear_bit (r, from);
2847 bitmap_set_bit (r, to);
2849 if (! df_live)
2850 continue;
2851 r = DF_LIVE_IN (bb);
2852 if (bitmap_bit_p (r, from))
2854 bitmap_clear_bit (r, from);
2855 bitmap_set_bit (r, to);
2862 /* The length of the following array. */
2863 int ira_reg_equiv_len;
2865 /* Info about equiv. info for each register. */
2866 struct ira_reg_equiv_s *ira_reg_equiv;
2868 /* Expand ira_reg_equiv if necessary. */
2869 void
2870 ira_expand_reg_equiv (void)
2872 int old = ira_reg_equiv_len;
2874 if (ira_reg_equiv_len > max_reg_num ())
2875 return;
2876 ira_reg_equiv_len = max_reg_num () * 3 / 2 + 1;
2877 ira_reg_equiv
2878 = (struct ira_reg_equiv_s *) xrealloc (ira_reg_equiv,
2879 ira_reg_equiv_len
2880 * sizeof (struct ira_reg_equiv_s));
2881 gcc_assert (old < ira_reg_equiv_len);
2882 memset (ira_reg_equiv + old, 0,
2883 sizeof (struct ira_reg_equiv_s) * (ira_reg_equiv_len - old));
2886 static void
2887 init_reg_equiv (void)
2889 ira_reg_equiv_len = 0;
2890 ira_reg_equiv = NULL;
2891 ira_expand_reg_equiv ();
2894 static void
2895 finish_reg_equiv (void)
2897 free (ira_reg_equiv);
2902 struct equivalence
2904 /* Set when a REG_EQUIV note is found or created. Use to
2905 keep track of what memory accesses might be created later,
2906 e.g. by reload. */
2907 rtx replacement;
2908 rtx *src_p;
2909 /* The list of each instruction which initializes this register. */
2910 rtx 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 int loop_depth;
2914 /* Nonzero if this had a preexisting REG_EQUIV note. */
2915 int is_arg_equivalence;
2916 /* Set when an attempt should be made to replace a register
2917 with the associated src_p entry. */
2918 char replace;
2921 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
2922 structure for that register. */
2923 static struct equivalence *reg_equiv;
2925 /* Used for communication between the following two functions: contains
2926 a MEM that we wish to ensure remains unchanged. */
2927 static rtx equiv_mem;
2929 /* Set nonzero if EQUIV_MEM is modified. */
2930 static int equiv_mem_modified;
2932 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
2933 Called via note_stores. */
2934 static void
2935 validate_equiv_mem_from_store (rtx dest, const_rtx set ATTRIBUTE_UNUSED,
2936 void *data ATTRIBUTE_UNUSED)
2938 if ((REG_P (dest)
2939 && reg_overlap_mentioned_p (dest, equiv_mem))
2940 || (MEM_P (dest)
2941 && anti_dependence (equiv_mem, dest)))
2942 equiv_mem_modified = 1;
2945 /* Verify that no store between START and the death of REG invalidates
2946 MEMREF. MEMREF is invalidated by modifying a register used in MEMREF,
2947 by storing into an overlapping memory location, or with a non-const
2948 CALL_INSN.
2950 Return 1 if MEMREF remains valid. */
2951 static int
2952 validate_equiv_mem (rtx start, rtx reg, rtx memref)
2954 rtx insn;
2955 rtx note;
2957 equiv_mem = memref;
2958 equiv_mem_modified = 0;
2960 /* If the memory reference has side effects or is volatile, it isn't a
2961 valid equivalence. */
2962 if (side_effects_p (memref))
2963 return 0;
2965 for (insn = start; insn && ! equiv_mem_modified; insn = NEXT_INSN (insn))
2967 if (! INSN_P (insn))
2968 continue;
2970 if (find_reg_note (insn, REG_DEAD, reg))
2971 return 1;
2973 /* This used to ignore readonly memory and const/pure calls. The problem
2974 is the equivalent form may reference a pseudo which gets assigned a
2975 call clobbered hard reg. When we later replace REG with its
2976 equivalent form, the value in the call-clobbered reg has been
2977 changed and all hell breaks loose. */
2978 if (CALL_P (insn))
2979 return 0;
2981 note_stores (PATTERN (insn), validate_equiv_mem_from_store, NULL);
2983 /* If a register mentioned in MEMREF is modified via an
2984 auto-increment, we lose the equivalence. Do the same if one
2985 dies; although we could extend the life, it doesn't seem worth
2986 the trouble. */
2988 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2989 if ((REG_NOTE_KIND (note) == REG_INC
2990 || REG_NOTE_KIND (note) == REG_DEAD)
2991 && REG_P (XEXP (note, 0))
2992 && reg_overlap_mentioned_p (XEXP (note, 0), memref))
2993 return 0;
2996 return 0;
2999 /* Returns zero if X is known to be invariant. */
3000 static int
3001 equiv_init_varies_p (rtx x)
3003 RTX_CODE code = GET_CODE (x);
3004 int i;
3005 const char *fmt;
3007 switch (code)
3009 case MEM:
3010 return !MEM_READONLY_P (x) || equiv_init_varies_p (XEXP (x, 0));
3012 case CONST:
3013 CASE_CONST_ANY:
3014 case SYMBOL_REF:
3015 case LABEL_REF:
3016 return 0;
3018 case REG:
3019 return reg_equiv[REGNO (x)].replace == 0 && rtx_varies_p (x, 0);
3021 case ASM_OPERANDS:
3022 if (MEM_VOLATILE_P (x))
3023 return 1;
3025 /* Fall through. */
3027 default:
3028 break;
3031 fmt = GET_RTX_FORMAT (code);
3032 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3033 if (fmt[i] == 'e')
3035 if (equiv_init_varies_p (XEXP (x, i)))
3036 return 1;
3038 else if (fmt[i] == 'E')
3040 int j;
3041 for (j = 0; j < XVECLEN (x, i); j++)
3042 if (equiv_init_varies_p (XVECEXP (x, i, j)))
3043 return 1;
3046 return 0;
3049 /* Returns nonzero if X (used to initialize register REGNO) is movable.
3050 X is only movable if the registers it uses have equivalent initializations
3051 which appear to be within the same loop (or in an inner loop) and movable
3052 or if they are not candidates for local_alloc and don't vary. */
3053 static int
3054 equiv_init_movable_p (rtx x, int regno)
3056 int i, j;
3057 const char *fmt;
3058 enum rtx_code code = GET_CODE (x);
3060 switch (code)
3062 case SET:
3063 return equiv_init_movable_p (SET_SRC (x), regno);
3065 case CC0:
3066 case CLOBBER:
3067 return 0;
3069 case PRE_INC:
3070 case PRE_DEC:
3071 case POST_INC:
3072 case POST_DEC:
3073 case PRE_MODIFY:
3074 case POST_MODIFY:
3075 return 0;
3077 case REG:
3078 return ((reg_equiv[REGNO (x)].loop_depth >= reg_equiv[regno].loop_depth
3079 && reg_equiv[REGNO (x)].replace)
3080 || (REG_BASIC_BLOCK (REGNO (x)) < NUM_FIXED_BLOCKS
3081 && ! rtx_varies_p (x, 0)));
3083 case UNSPEC_VOLATILE:
3084 return 0;
3086 case ASM_OPERANDS:
3087 if (MEM_VOLATILE_P (x))
3088 return 0;
3090 /* Fall through. */
3092 default:
3093 break;
3096 fmt = GET_RTX_FORMAT (code);
3097 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3098 switch (fmt[i])
3100 case 'e':
3101 if (! equiv_init_movable_p (XEXP (x, i), regno))
3102 return 0;
3103 break;
3104 case 'E':
3105 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3106 if (! equiv_init_movable_p (XVECEXP (x, i, j), regno))
3107 return 0;
3108 break;
3111 return 1;
3114 /* TRUE if X uses any registers for which reg_equiv[REGNO].replace is
3115 true. */
3116 static int
3117 contains_replace_regs (rtx x)
3119 int i, j;
3120 const char *fmt;
3121 enum rtx_code code = GET_CODE (x);
3123 switch (code)
3125 case CONST:
3126 case LABEL_REF:
3127 case SYMBOL_REF:
3128 CASE_CONST_ANY:
3129 case PC:
3130 case CC0:
3131 case HIGH:
3132 return 0;
3134 case REG:
3135 return reg_equiv[REGNO (x)].replace;
3137 default:
3138 break;
3141 fmt = GET_RTX_FORMAT (code);
3142 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3143 switch (fmt[i])
3145 case 'e':
3146 if (contains_replace_regs (XEXP (x, i)))
3147 return 1;
3148 break;
3149 case 'E':
3150 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3151 if (contains_replace_regs (XVECEXP (x, i, j)))
3152 return 1;
3153 break;
3156 return 0;
3159 /* TRUE if X references a memory location that would be affected by a store
3160 to MEMREF. */
3161 static int
3162 memref_referenced_p (rtx memref, rtx x)
3164 int i, j;
3165 const char *fmt;
3166 enum rtx_code code = GET_CODE (x);
3168 switch (code)
3170 case CONST:
3171 case LABEL_REF:
3172 case SYMBOL_REF:
3173 CASE_CONST_ANY:
3174 case PC:
3175 case CC0:
3176 case HIGH:
3177 case LO_SUM:
3178 return 0;
3180 case REG:
3181 return (reg_equiv[REGNO (x)].replacement
3182 && memref_referenced_p (memref,
3183 reg_equiv[REGNO (x)].replacement));
3185 case MEM:
3186 if (true_dependence (memref, VOIDmode, x))
3187 return 1;
3188 break;
3190 case SET:
3191 /* If we are setting a MEM, it doesn't count (its address does), but any
3192 other SET_DEST that has a MEM in it is referencing the MEM. */
3193 if (MEM_P (SET_DEST (x)))
3195 if (memref_referenced_p (memref, XEXP (SET_DEST (x), 0)))
3196 return 1;
3198 else if (memref_referenced_p (memref, SET_DEST (x)))
3199 return 1;
3201 return memref_referenced_p (memref, SET_SRC (x));
3203 default:
3204 break;
3207 fmt = GET_RTX_FORMAT (code);
3208 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3209 switch (fmt[i])
3211 case 'e':
3212 if (memref_referenced_p (memref, XEXP (x, i)))
3213 return 1;
3214 break;
3215 case 'E':
3216 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3217 if (memref_referenced_p (memref, XVECEXP (x, i, j)))
3218 return 1;
3219 break;
3222 return 0;
3225 /* TRUE if some insn in the range (START, END] references a memory location
3226 that would be affected by a store to MEMREF. */
3227 static int
3228 memref_used_between_p (rtx memref, rtx start, rtx end)
3230 rtx insn;
3232 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
3233 insn = NEXT_INSN (insn))
3235 if (!NONDEBUG_INSN_P (insn))
3236 continue;
3238 if (memref_referenced_p (memref, PATTERN (insn)))
3239 return 1;
3241 /* Nonconst functions may access memory. */
3242 if (CALL_P (insn) && (! RTL_CONST_CALL_P (insn)))
3243 return 1;
3246 return 0;
3249 /* Mark REG as having no known equivalence.
3250 Some instructions might have been processed before and furnished
3251 with REG_EQUIV notes for this register; these notes will have to be
3252 removed.
3253 STORE is the piece of RTL that does the non-constant / conflicting
3254 assignment - a SET, CLOBBER or REG_INC note. It is currently not used,
3255 but needs to be there because this function is called from note_stores. */
3256 static void
3257 no_equiv (rtx reg, const_rtx store ATTRIBUTE_UNUSED,
3258 void *data ATTRIBUTE_UNUSED)
3260 int regno;
3261 rtx list;
3263 if (!REG_P (reg))
3264 return;
3265 regno = REGNO (reg);
3266 list = reg_equiv[regno].init_insns;
3267 if (list == const0_rtx)
3268 return;
3269 reg_equiv[regno].init_insns = const0_rtx;
3270 reg_equiv[regno].replacement = NULL_RTX;
3271 /* This doesn't matter for equivalences made for argument registers, we
3272 should keep their initialization insns. */
3273 if (reg_equiv[regno].is_arg_equivalence)
3274 return;
3275 ira_reg_equiv[regno].defined_p = false;
3276 ira_reg_equiv[regno].init_insns = NULL_RTX;
3277 for (; list; list = XEXP (list, 1))
3279 rtx insn = XEXP (list, 0);
3280 remove_note (insn, find_reg_note (insn, REG_EQUIV, NULL_RTX));
3284 /* Check whether the SUBREG is a paradoxical subreg and set the result
3285 in PDX_SUBREGS. */
3287 static int
3288 set_paradoxical_subreg (rtx *subreg, void *pdx_subregs)
3290 rtx reg;
3292 if ((*subreg) == NULL_RTX)
3293 return 1;
3294 if (GET_CODE (*subreg) != SUBREG)
3295 return 0;
3296 reg = SUBREG_REG (*subreg);
3297 if (!REG_P (reg))
3298 return 0;
3300 if (paradoxical_subreg_p (*subreg))
3301 ((bool *)pdx_subregs)[REGNO (reg)] = true;
3303 return 0;
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;
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 sequivalent 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 for_each_rtx (&insn, set_paradoxical_subreg, (void *) 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 == 0)
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 == const0_rtx
3460 || (targetm.class_likely_spilled_p (reg_preferred_class (regno))
3461 && MEM_P (src) && ! reg_equiv[regno].is_arg_equivalence))
3463 /* This might be setting a SUBREG of a pseudo, a pseudo that is
3464 also set somewhere else to a constant. */
3465 note_stores (set, no_equiv, NULL);
3466 continue;
3469 /* Don't set reg (if pdx_subregs[regno] == true) equivalent to a mem. */
3470 if (MEM_P (src) && pdx_subregs[regno])
3472 note_stores (set, no_equiv, NULL);
3473 continue;
3476 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
3478 /* cse sometimes generates function invariants, but doesn't put a
3479 REG_EQUAL note on the insn. Since this note would be redundant,
3480 there's no point creating it earlier than here. */
3481 if (! note && ! rtx_varies_p (src, 0))
3482 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
3484 /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
3485 since it represents a function call */
3486 if (note && GET_CODE (XEXP (note, 0)) == EXPR_LIST)
3487 note = NULL_RTX;
3489 if (DF_REG_DEF_COUNT (regno) != 1
3490 && (! note
3491 || rtx_varies_p (XEXP (note, 0), 0)
3492 || (reg_equiv[regno].replacement
3493 && ! rtx_equal_p (XEXP (note, 0),
3494 reg_equiv[regno].replacement))))
3496 no_equiv (dest, set, NULL);
3497 continue;
3499 /* Record this insn as initializing this register. */
3500 reg_equiv[regno].init_insns
3501 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv[regno].init_insns);
3503 /* If this register is known to be equal to a constant, record that
3504 it is always equivalent to the constant. */
3505 if (DF_REG_DEF_COUNT (regno) == 1
3506 && note && ! rtx_varies_p (XEXP (note, 0), 0))
3508 rtx note_value = XEXP (note, 0);
3509 remove_note (insn, note);
3510 set_unique_reg_note (insn, REG_EQUIV, note_value);
3513 /* If this insn introduces a "constant" register, decrease the priority
3514 of that register. Record this insn if the register is only used once
3515 more and the equivalence value is the same as our source.
3517 The latter condition is checked for two reasons: First, it is an
3518 indication that it may be more efficient to actually emit the insn
3519 as written (if no registers are available, reload will substitute
3520 the equivalence). Secondly, it avoids problems with any registers
3521 dying in this insn whose death notes would be missed.
3523 If we don't have a REG_EQUIV note, see if this insn is loading
3524 a register used only in one basic block from a MEM. If so, and the
3525 MEM remains unchanged for the life of the register, add a REG_EQUIV
3526 note. */
3528 note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
3530 if (note == 0 && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
3531 && MEM_P (SET_SRC (set))
3532 && validate_equiv_mem (insn, dest, SET_SRC (set)))
3533 note = set_unique_reg_note (insn, REG_EQUIV, copy_rtx (SET_SRC (set)));
3535 if (note)
3537 int regno = REGNO (dest);
3538 rtx x = XEXP (note, 0);
3540 /* If we haven't done so, record for reload that this is an
3541 equivalencing insn. */
3542 if (!reg_equiv[regno].is_arg_equivalence)
3543 ira_reg_equiv[regno].init_insns
3544 = gen_rtx_INSN_LIST (VOIDmode, insn,
3545 ira_reg_equiv[regno].init_insns);
3547 /* Record whether or not we created a REG_EQUIV note for a LABEL_REF.
3548 We might end up substituting the LABEL_REF for uses of the
3549 pseudo here or later. That kind of transformation may turn an
3550 indirect jump into a direct jump, in which case we must rerun the
3551 jump optimizer to ensure that the JUMP_LABEL fields are valid. */
3552 if (GET_CODE (x) == LABEL_REF
3553 || (GET_CODE (x) == CONST
3554 && GET_CODE (XEXP (x, 0)) == PLUS
3555 && (GET_CODE (XEXP (XEXP (x, 0), 0)) == LABEL_REF)))
3556 recorded_label_ref = 1;
3558 reg_equiv[regno].replacement = x;
3559 reg_equiv[regno].src_p = &SET_SRC (set);
3560 reg_equiv[regno].loop_depth = loop_depth;
3562 /* Don't mess with things live during setjmp. */
3563 if (REG_LIVE_LENGTH (regno) >= 0 && optimize)
3565 /* Note that the statement below does not affect the priority
3566 in local-alloc! */
3567 REG_LIVE_LENGTH (regno) *= 2;
3569 /* If the register is referenced exactly twice, meaning it is
3570 set once and used once, indicate that the reference may be
3571 replaced by the equivalence we computed above. Do this
3572 even if the register is only used in one block so that
3573 dependencies can be handled where the last register is
3574 used in a different block (i.e. HIGH / LO_SUM sequences)
3575 and to reduce the number of registers alive across
3576 calls. */
3578 if (REG_N_REFS (regno) == 2
3579 && (rtx_equal_p (x, src)
3580 || ! equiv_init_varies_p (src))
3581 && NONJUMP_INSN_P (insn)
3582 && equiv_init_movable_p (PATTERN (insn), regno))
3583 reg_equiv[regno].replace = 1;
3589 if (!optimize)
3590 goto out;
3592 /* A second pass, to gather additional equivalences with memory. This needs
3593 to be done after we know which registers we are going to replace. */
3595 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
3597 rtx set, src, dest;
3598 unsigned regno;
3600 if (! INSN_P (insn))
3601 continue;
3603 set = single_set (insn);
3604 if (! set)
3605 continue;
3607 dest = SET_DEST (set);
3608 src = SET_SRC (set);
3610 /* If this sets a MEM to the contents of a REG that is only used
3611 in a single basic block, see if the register is always equivalent
3612 to that memory location and if moving the store from INSN to the
3613 insn that set REG is safe. If so, put a REG_EQUIV note on the
3614 initializing insn.
3616 Don't add a REG_EQUIV note if the insn already has one. The existing
3617 REG_EQUIV is likely more useful than the one we are adding.
3619 If one of the regs in the address has reg_equiv[REGNO].replace set,
3620 then we can't add this REG_EQUIV note. The reg_equiv[REGNO].replace
3621 optimization may move the set of this register immediately before
3622 insn, which puts it after reg_equiv[REGNO].init_insns, and hence
3623 the mention in the REG_EQUIV note would be to an uninitialized
3624 pseudo. */
3626 if (MEM_P (dest) && REG_P (src)
3627 && (regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
3628 && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
3629 && DF_REG_DEF_COUNT (regno) == 1
3630 && reg_equiv[regno].init_insns != 0
3631 && reg_equiv[regno].init_insns != const0_rtx
3632 && ! find_reg_note (XEXP (reg_equiv[regno].init_insns, 0),
3633 REG_EQUIV, NULL_RTX)
3634 && ! contains_replace_regs (XEXP (dest, 0))
3635 && ! pdx_subregs[regno])
3637 rtx init_insn = XEXP (reg_equiv[regno].init_insns, 0);
3638 if (validate_equiv_mem (init_insn, src, dest)
3639 && ! memref_used_between_p (dest, init_insn, insn)
3640 /* Attaching a REG_EQUIV note will fail if INIT_INSN has
3641 multiple sets. */
3642 && set_unique_reg_note (init_insn, REG_EQUIV, copy_rtx (dest)))
3644 /* This insn makes the equivalence, not the one initializing
3645 the register. */
3646 ira_reg_equiv[regno].init_insns
3647 = gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
3648 df_notes_rescan (init_insn);
3653 cleared_regs = BITMAP_ALLOC (NULL);
3654 /* Now scan all regs killed in an insn to see if any of them are
3655 registers only used that once. If so, see if we can replace the
3656 reference with the equivalent form. If we can, delete the
3657 initializing reference and this register will go away. If we
3658 can't replace the reference, and the initializing reference is
3659 within the same loop (or in an inner loop), then move the register
3660 initialization just before the use, so that they are in the same
3661 basic block. */
3662 FOR_EACH_BB_REVERSE_FN (bb, cfun)
3664 loop_depth = bb_loop_depth (bb);
3665 for (insn = BB_END (bb);
3666 insn != PREV_INSN (BB_HEAD (bb));
3667 insn = PREV_INSN (insn))
3669 rtx link;
3671 if (! INSN_P (insn))
3672 continue;
3674 /* Don't substitute into a non-local goto, this confuses CFG. */
3675 if (JUMP_P (insn)
3676 && find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
3677 continue;
3679 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3681 if (REG_NOTE_KIND (link) == REG_DEAD
3682 /* Make sure this insn still refers to the register. */
3683 && reg_mentioned_p (XEXP (link, 0), PATTERN (insn)))
3685 int regno = REGNO (XEXP (link, 0));
3686 rtx equiv_insn;
3688 if (! reg_equiv[regno].replace
3689 || reg_equiv[regno].loop_depth < loop_depth
3690 /* There is no sense to move insns if live range
3691 shrinkage or register pressure-sensitive
3692 scheduling were done because it will not
3693 improve allocation but worsen insn schedule
3694 with a big probability. */
3695 || flag_live_range_shrinkage
3696 || (flag_sched_pressure && flag_schedule_insns))
3697 continue;
3699 /* reg_equiv[REGNO].replace gets set only when
3700 REG_N_REFS[REGNO] is 2, i.e. the register is set
3701 once and used once. (If it were only set, but
3702 not used, flow would have deleted the setting
3703 insns.) Hence there can only be one insn in
3704 reg_equiv[REGNO].init_insns. */
3705 gcc_assert (reg_equiv[regno].init_insns
3706 && !XEXP (reg_equiv[regno].init_insns, 1));
3707 equiv_insn = XEXP (reg_equiv[regno].init_insns, 0);
3709 /* We may not move instructions that can throw, since
3710 that changes basic block boundaries and we are not
3711 prepared to adjust the CFG to match. */
3712 if (can_throw_internal (equiv_insn))
3713 continue;
3715 if (asm_noperands (PATTERN (equiv_insn)) < 0
3716 && validate_replace_rtx (regno_reg_rtx[regno],
3717 *(reg_equiv[regno].src_p), insn))
3719 rtx equiv_link;
3720 rtx last_link;
3721 rtx note;
3723 /* Find the last note. */
3724 for (last_link = link; XEXP (last_link, 1);
3725 last_link = XEXP (last_link, 1))
3728 /* Append the REG_DEAD notes from equiv_insn. */
3729 equiv_link = REG_NOTES (equiv_insn);
3730 while (equiv_link)
3732 note = equiv_link;
3733 equiv_link = XEXP (equiv_link, 1);
3734 if (REG_NOTE_KIND (note) == REG_DEAD)
3736 remove_note (equiv_insn, note);
3737 XEXP (last_link, 1) = note;
3738 XEXP (note, 1) = NULL_RTX;
3739 last_link = note;
3743 remove_death (regno, insn);
3744 SET_REG_N_REFS (regno, 0);
3745 REG_FREQ (regno) = 0;
3746 delete_insn (equiv_insn);
3748 reg_equiv[regno].init_insns
3749 = XEXP (reg_equiv[regno].init_insns, 1);
3751 ira_reg_equiv[regno].init_insns = NULL_RTX;
3752 bitmap_set_bit (cleared_regs, regno);
3754 /* Move the initialization of the register to just before
3755 INSN. Update the flow information. */
3756 else if (prev_nondebug_insn (insn) != equiv_insn)
3758 rtx new_insn;
3760 new_insn = emit_insn_before (PATTERN (equiv_insn), insn);
3761 REG_NOTES (new_insn) = REG_NOTES (equiv_insn);
3762 REG_NOTES (equiv_insn) = 0;
3763 /* Rescan it to process the notes. */
3764 df_insn_rescan (new_insn);
3766 /* Make sure this insn is recognized before
3767 reload begins, otherwise
3768 eliminate_regs_in_insn will die. */
3769 INSN_CODE (new_insn) = INSN_CODE (equiv_insn);
3771 delete_insn (equiv_insn);
3773 XEXP (reg_equiv[regno].init_insns, 0) = new_insn;
3775 REG_BASIC_BLOCK (regno) = bb->index;
3776 REG_N_CALLS_CROSSED (regno) = 0;
3777 REG_FREQ_CALLS_CROSSED (regno) = 0;
3778 REG_N_THROWING_CALLS_CROSSED (regno) = 0;
3779 REG_LIVE_LENGTH (regno) = 2;
3781 if (insn == BB_HEAD (bb))
3782 BB_HEAD (bb) = PREV_INSN (insn);
3784 ira_reg_equiv[regno].init_insns
3785 = gen_rtx_INSN_LIST (VOIDmode, new_insn, NULL_RTX);
3786 bitmap_set_bit (cleared_regs, regno);
3793 if (!bitmap_empty_p (cleared_regs))
3795 FOR_EACH_BB_FN (bb, cfun)
3797 bitmap_and_compl_into (DF_LR_IN (bb), cleared_regs);
3798 bitmap_and_compl_into (DF_LR_OUT (bb), cleared_regs);
3799 if (! df_live)
3800 continue;
3801 bitmap_and_compl_into (DF_LIVE_IN (bb), cleared_regs);
3802 bitmap_and_compl_into (DF_LIVE_OUT (bb), cleared_regs);
3805 /* Last pass - adjust debug insns referencing cleared regs. */
3806 if (MAY_HAVE_DEBUG_INSNS)
3807 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
3808 if (DEBUG_INSN_P (insn))
3810 rtx old_loc = INSN_VAR_LOCATION_LOC (insn);
3811 INSN_VAR_LOCATION_LOC (insn)
3812 = simplify_replace_fn_rtx (old_loc, NULL_RTX,
3813 adjust_cleared_regs,
3814 (void *) cleared_regs);
3815 if (old_loc != INSN_VAR_LOCATION_LOC (insn))
3816 df_insn_rescan (insn);
3820 BITMAP_FREE (cleared_regs);
3822 out:
3823 /* Clean up. */
3825 end_alias_analysis ();
3826 free (reg_equiv);
3827 free (pdx_subregs);
3828 return recorded_label_ref;
3833 /* Set up fields memory, constant, and invariant from init_insns in
3834 the structures of array ira_reg_equiv. */
3835 static void
3836 setup_reg_equiv (void)
3838 int i;
3839 rtx elem, prev_elem, next_elem, insn, set, x;
3841 for (i = FIRST_PSEUDO_REGISTER; i < ira_reg_equiv_len; i++)
3842 for (prev_elem = NULL, elem = ira_reg_equiv[i].init_insns;
3843 elem;
3844 prev_elem = elem, elem = next_elem)
3846 next_elem = XEXP (elem, 1);
3847 insn = XEXP (elem, 0);
3848 set = single_set (insn);
3850 /* Init insns can set up equivalence when the reg is a destination or
3851 a source (in this case the destination is memory). */
3852 if (set != 0 && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))))
3854 if ((x = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != NULL)
3856 x = XEXP (x, 0);
3857 if (REG_P (SET_DEST (set))
3858 && REGNO (SET_DEST (set)) == (unsigned int) i
3859 && ! rtx_equal_p (SET_SRC (set), x) && MEM_P (x))
3861 /* This insn reporting the equivalence but
3862 actually not setting it. Remove it from the
3863 list. */
3864 if (prev_elem == NULL)
3865 ira_reg_equiv[i].init_insns = next_elem;
3866 else
3867 XEXP (prev_elem, 1) = next_elem;
3868 elem = prev_elem;
3871 else if (REG_P (SET_DEST (set))
3872 && REGNO (SET_DEST (set)) == (unsigned int) i)
3873 x = SET_SRC (set);
3874 else
3876 gcc_assert (REG_P (SET_SRC (set))
3877 && REGNO (SET_SRC (set)) == (unsigned int) i);
3878 x = SET_DEST (set);
3880 if (! function_invariant_p (x)
3881 || ! flag_pic
3882 /* A function invariant is often CONSTANT_P but may
3883 include a register. We promise to only pass
3884 CONSTANT_P objects to LEGITIMATE_PIC_OPERAND_P. */
3885 || (CONSTANT_P (x) && LEGITIMATE_PIC_OPERAND_P (x)))
3887 /* It can happen that a REG_EQUIV note contains a MEM
3888 that is not a legitimate memory operand. As later
3889 stages of reload assume that all addresses found in
3890 the lra_regno_equiv_* arrays were originally
3891 legitimate, we ignore such REG_EQUIV notes. */
3892 if (memory_operand (x, VOIDmode))
3894 ira_reg_equiv[i].defined_p = true;
3895 ira_reg_equiv[i].memory = x;
3896 continue;
3898 else if (function_invariant_p (x))
3900 enum machine_mode mode;
3902 mode = GET_MODE (SET_DEST (set));
3903 if (GET_CODE (x) == PLUS
3904 || x == frame_pointer_rtx || x == arg_pointer_rtx)
3905 /* This is PLUS of frame pointer and a constant,
3906 or fp, or argp. */
3907 ira_reg_equiv[i].invariant = x;
3908 else if (targetm.legitimate_constant_p (mode, x))
3909 ira_reg_equiv[i].constant = x;
3910 else
3912 ira_reg_equiv[i].memory = force_const_mem (mode, x);
3913 if (ira_reg_equiv[i].memory == NULL_RTX)
3915 ira_reg_equiv[i].defined_p = false;
3916 ira_reg_equiv[i].init_insns = NULL_RTX;
3917 break;
3920 ira_reg_equiv[i].defined_p = true;
3921 continue;
3925 ira_reg_equiv[i].defined_p = false;
3926 ira_reg_equiv[i].init_insns = NULL_RTX;
3927 break;
3933 /* Print chain C to FILE. */
3934 static void
3935 print_insn_chain (FILE *file, struct insn_chain *c)
3937 fprintf (file, "insn=%d, ", INSN_UID (c->insn));
3938 bitmap_print (file, &c->live_throughout, "live_throughout: ", ", ");
3939 bitmap_print (file, &c->dead_or_set, "dead_or_set: ", "\n");
3943 /* Print all reload_insn_chains to FILE. */
3944 static void
3945 print_insn_chains (FILE *file)
3947 struct insn_chain *c;
3948 for (c = reload_insn_chain; c ; c = c->next)
3949 print_insn_chain (file, c);
3952 /* Return true if pseudo REGNO should be added to set live_throughout
3953 or dead_or_set of the insn chains for reload consideration. */
3954 static bool
3955 pseudo_for_reload_consideration_p (int regno)
3957 /* Consider spilled pseudos too for IRA because they still have a
3958 chance to get hard-registers in the reload when IRA is used. */
3959 return (reg_renumber[regno] >= 0 || ira_conflicts_p);
3962 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
3963 REG to the number of nregs, and INIT_VALUE to get the
3964 initialization. ALLOCNUM need not be the regno of REG. */
3965 static void
3966 init_live_subregs (bool init_value, sbitmap *live_subregs,
3967 bitmap live_subregs_used, int allocnum, rtx reg)
3969 unsigned int regno = REGNO (SUBREG_REG (reg));
3970 int size = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno]));
3972 gcc_assert (size > 0);
3974 /* Been there, done that. */
3975 if (bitmap_bit_p (live_subregs_used, allocnum))
3976 return;
3978 /* Create a new one. */
3979 if (live_subregs[allocnum] == NULL)
3980 live_subregs[allocnum] = sbitmap_alloc (size);
3982 /* If the entire reg was live before blasting into subregs, we need
3983 to init all of the subregs to ones else init to 0. */
3984 if (init_value)
3985 bitmap_ones (live_subregs[allocnum]);
3986 else
3987 bitmap_clear (live_subregs[allocnum]);
3989 bitmap_set_bit (live_subregs_used, allocnum);
3992 /* Walk the insns of the current function and build reload_insn_chain,
3993 and record register life information. */
3994 static void
3995 build_insn_chain (void)
3997 unsigned int i;
3998 struct insn_chain **p = &reload_insn_chain;
3999 basic_block bb;
4000 struct insn_chain *c = NULL;
4001 struct insn_chain *next = NULL;
4002 bitmap live_relevant_regs = BITMAP_ALLOC (NULL);
4003 bitmap elim_regset = BITMAP_ALLOC (NULL);
4004 /* live_subregs is a vector used to keep accurate information about
4005 which hardregs are live in multiword pseudos. live_subregs and
4006 live_subregs_used are indexed by pseudo number. The live_subreg
4007 entry for a particular pseudo is only used if the corresponding
4008 element is non zero in live_subregs_used. The sbitmap size of
4009 live_subreg[allocno] is number of bytes that the pseudo can
4010 occupy. */
4011 sbitmap *live_subregs = XCNEWVEC (sbitmap, max_regno);
4012 bitmap live_subregs_used = BITMAP_ALLOC (NULL);
4014 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4015 if (TEST_HARD_REG_BIT (eliminable_regset, i))
4016 bitmap_set_bit (elim_regset, i);
4017 FOR_EACH_BB_REVERSE_FN (bb, cfun)
4019 bitmap_iterator bi;
4020 rtx insn;
4022 CLEAR_REG_SET (live_relevant_regs);
4023 bitmap_clear (live_subregs_used);
4025 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb), 0, i, bi)
4027 if (i >= FIRST_PSEUDO_REGISTER)
4028 break;
4029 bitmap_set_bit (live_relevant_regs, i);
4032 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb),
4033 FIRST_PSEUDO_REGISTER, i, bi)
4035 if (pseudo_for_reload_consideration_p (i))
4036 bitmap_set_bit (live_relevant_regs, i);
4039 FOR_BB_INSNS_REVERSE (bb, insn)
4041 if (!NOTE_P (insn) && !BARRIER_P (insn))
4043 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4044 df_ref def, use;
4046 c = new_insn_chain ();
4047 c->next = next;
4048 next = c;
4049 *p = c;
4050 p = &c->prev;
4052 c->insn = insn;
4053 c->block = bb->index;
4055 if (NONDEBUG_INSN_P (insn))
4056 FOR_EACH_INSN_INFO_DEF (def, insn_info)
4058 unsigned int regno = DF_REF_REGNO (def);
4060 /* Ignore may clobbers because these are generated
4061 from calls. However, every other kind of def is
4062 added to dead_or_set. */
4063 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
4065 if (regno < FIRST_PSEUDO_REGISTER)
4067 if (!fixed_regs[regno])
4068 bitmap_set_bit (&c->dead_or_set, regno);
4070 else if (pseudo_for_reload_consideration_p (regno))
4071 bitmap_set_bit (&c->dead_or_set, regno);
4074 if ((regno < FIRST_PSEUDO_REGISTER
4075 || reg_renumber[regno] >= 0
4076 || ira_conflicts_p)
4077 && (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)))
4079 rtx reg = DF_REF_REG (def);
4081 /* We can model subregs, but not if they are
4082 wrapped in ZERO_EXTRACTS. */
4083 if (GET_CODE (reg) == SUBREG
4084 && !DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT))
4086 unsigned int start = SUBREG_BYTE (reg);
4087 unsigned int last = start
4088 + GET_MODE_SIZE (GET_MODE (reg));
4090 init_live_subregs
4091 (bitmap_bit_p (live_relevant_regs, regno),
4092 live_subregs, live_subregs_used, regno, reg);
4094 if (!DF_REF_FLAGS_IS_SET
4095 (def, DF_REF_STRICT_LOW_PART))
4097 /* Expand the range to cover entire words.
4098 Bytes added here are "don't care". */
4099 start
4100 = start / UNITS_PER_WORD * UNITS_PER_WORD;
4101 last = ((last + UNITS_PER_WORD - 1)
4102 / UNITS_PER_WORD * UNITS_PER_WORD);
4105 /* Ignore the paradoxical bits. */
4106 if (last > SBITMAP_SIZE (live_subregs[regno]))
4107 last = SBITMAP_SIZE (live_subregs[regno]);
4109 while (start < last)
4111 bitmap_clear_bit (live_subregs[regno], start);
4112 start++;
4115 if (bitmap_empty_p (live_subregs[regno]))
4117 bitmap_clear_bit (live_subregs_used, regno);
4118 bitmap_clear_bit (live_relevant_regs, regno);
4120 else
4121 /* Set live_relevant_regs here because
4122 that bit has to be true to get us to
4123 look at the live_subregs fields. */
4124 bitmap_set_bit (live_relevant_regs, regno);
4126 else
4128 /* DF_REF_PARTIAL is generated for
4129 subregs, STRICT_LOW_PART, and
4130 ZERO_EXTRACT. We handle the subreg
4131 case above so here we have to keep from
4132 modeling the def as a killing def. */
4133 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL))
4135 bitmap_clear_bit (live_subregs_used, regno);
4136 bitmap_clear_bit (live_relevant_regs, regno);
4142 bitmap_and_compl_into (live_relevant_regs, elim_regset);
4143 bitmap_copy (&c->live_throughout, live_relevant_regs);
4145 if (NONDEBUG_INSN_P (insn))
4146 FOR_EACH_INSN_INFO_USE (use, insn_info)
4148 unsigned int regno = DF_REF_REGNO (use);
4149 rtx reg = DF_REF_REG (use);
4151 /* DF_REF_READ_WRITE on a use means that this use
4152 is fabricated from a def that is a partial set
4153 to a multiword reg. Here, we only model the
4154 subreg case that is not wrapped in ZERO_EXTRACT
4155 precisely so we do not need to look at the
4156 fabricated use. */
4157 if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE)
4158 && !DF_REF_FLAGS_IS_SET (use, DF_REF_ZERO_EXTRACT)
4159 && DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG))
4160 continue;
4162 /* Add the last use of each var to dead_or_set. */
4163 if (!bitmap_bit_p (live_relevant_regs, regno))
4165 if (regno < FIRST_PSEUDO_REGISTER)
4167 if (!fixed_regs[regno])
4168 bitmap_set_bit (&c->dead_or_set, regno);
4170 else if (pseudo_for_reload_consideration_p (regno))
4171 bitmap_set_bit (&c->dead_or_set, regno);
4174 if (regno < FIRST_PSEUDO_REGISTER
4175 || pseudo_for_reload_consideration_p (regno))
4177 if (GET_CODE (reg) == SUBREG
4178 && !DF_REF_FLAGS_IS_SET (use,
4179 DF_REF_SIGN_EXTRACT
4180 | DF_REF_ZERO_EXTRACT))
4182 unsigned int start = SUBREG_BYTE (reg);
4183 unsigned int last = start
4184 + GET_MODE_SIZE (GET_MODE (reg));
4186 init_live_subregs
4187 (bitmap_bit_p (live_relevant_regs, regno),
4188 live_subregs, live_subregs_used, regno, reg);
4190 /* Ignore the paradoxical bits. */
4191 if (last > SBITMAP_SIZE (live_subregs[regno]))
4192 last = SBITMAP_SIZE (live_subregs[regno]);
4194 while (start < last)
4196 bitmap_set_bit (live_subregs[regno], start);
4197 start++;
4200 else
4201 /* Resetting the live_subregs_used is
4202 effectively saying do not use the subregs
4203 because we are reading the whole
4204 pseudo. */
4205 bitmap_clear_bit (live_subregs_used, regno);
4206 bitmap_set_bit (live_relevant_regs, regno);
4212 /* FIXME!! The following code is a disaster. Reload needs to see the
4213 labels and jump tables that are just hanging out in between
4214 the basic blocks. See pr33676. */
4215 insn = BB_HEAD (bb);
4217 /* Skip over the barriers and cruft. */
4218 while (insn && (BARRIER_P (insn) || NOTE_P (insn)
4219 || BLOCK_FOR_INSN (insn) == bb))
4220 insn = PREV_INSN (insn);
4222 /* While we add anything except barriers and notes, the focus is
4223 to get the labels and jump tables into the
4224 reload_insn_chain. */
4225 while (insn)
4227 if (!NOTE_P (insn) && !BARRIER_P (insn))
4229 if (BLOCK_FOR_INSN (insn))
4230 break;
4232 c = new_insn_chain ();
4233 c->next = next;
4234 next = c;
4235 *p = c;
4236 p = &c->prev;
4238 /* The block makes no sense here, but it is what the old
4239 code did. */
4240 c->block = bb->index;
4241 c->insn = insn;
4242 bitmap_copy (&c->live_throughout, live_relevant_regs);
4244 insn = PREV_INSN (insn);
4248 reload_insn_chain = c;
4249 *p = NULL;
4251 for (i = 0; i < (unsigned int) max_regno; i++)
4252 if (live_subregs[i] != NULL)
4253 sbitmap_free (live_subregs[i]);
4254 free (live_subregs);
4255 BITMAP_FREE (live_subregs_used);
4256 BITMAP_FREE (live_relevant_regs);
4257 BITMAP_FREE (elim_regset);
4259 if (dump_file)
4260 print_insn_chains (dump_file);
4263 /* Examine the rtx found in *LOC, which is read or written to as determined
4264 by TYPE. Return false if we find a reason why an insn containing this
4265 rtx should not be moved (such as accesses to non-constant memory), true
4266 otherwise. */
4267 static bool
4268 rtx_moveable_p (rtx *loc, enum op_type type)
4270 const char *fmt;
4271 rtx x = *loc;
4272 enum rtx_code code = GET_CODE (x);
4273 int i, j;
4275 code = GET_CODE (x);
4276 switch (code)
4278 case CONST:
4279 CASE_CONST_ANY:
4280 case SYMBOL_REF:
4281 case LABEL_REF:
4282 return true;
4284 case PC:
4285 return type == OP_IN;
4287 case CC0:
4288 return false;
4290 case REG:
4291 if (x == frame_pointer_rtx)
4292 return true;
4293 if (HARD_REGISTER_P (x))
4294 return false;
4296 return true;
4298 case MEM:
4299 if (type == OP_IN && MEM_READONLY_P (x))
4300 return rtx_moveable_p (&XEXP (x, 0), OP_IN);
4301 return false;
4303 case SET:
4304 return (rtx_moveable_p (&SET_SRC (x), OP_IN)
4305 && rtx_moveable_p (&SET_DEST (x), OP_OUT));
4307 case STRICT_LOW_PART:
4308 return rtx_moveable_p (&XEXP (x, 0), OP_OUT);
4310 case ZERO_EXTRACT:
4311 case SIGN_EXTRACT:
4312 return (rtx_moveable_p (&XEXP (x, 0), type)
4313 && rtx_moveable_p (&XEXP (x, 1), OP_IN)
4314 && rtx_moveable_p (&XEXP (x, 2), OP_IN));
4316 case CLOBBER:
4317 return rtx_moveable_p (&SET_DEST (x), OP_OUT);
4319 default:
4320 break;
4323 fmt = GET_RTX_FORMAT (code);
4324 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4326 if (fmt[i] == 'e')
4328 if (!rtx_moveable_p (&XEXP (x, i), type))
4329 return false;
4331 else if (fmt[i] == 'E')
4332 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4334 if (!rtx_moveable_p (&XVECEXP (x, i, j), type))
4335 return false;
4338 return true;
4341 /* A wrapper around dominated_by_p, which uses the information in UID_LUID
4342 to give dominance relationships between two insns I1 and I2. */
4343 static bool
4344 insn_dominated_by_p (rtx i1, rtx i2, int *uid_luid)
4346 basic_block bb1 = BLOCK_FOR_INSN (i1);
4347 basic_block bb2 = BLOCK_FOR_INSN (i2);
4349 if (bb1 == bb2)
4350 return uid_luid[INSN_UID (i2)] < uid_luid[INSN_UID (i1)];
4351 return dominated_by_p (CDI_DOMINATORS, bb1, bb2);
4354 /* Record the range of register numbers added by find_moveable_pseudos. */
4355 int first_moveable_pseudo, last_moveable_pseudo;
4357 /* These two vectors hold data for every register added by
4358 find_movable_pseudos, with index 0 holding data for the
4359 first_moveable_pseudo. */
4360 /* The original home register. */
4361 static vec<rtx> pseudo_replaced_reg;
4363 /* Look for instances where we have an instruction that is known to increase
4364 register pressure, and whose result is not used immediately. If it is
4365 possible to move the instruction downwards to just before its first use,
4366 split its lifetime into two ranges. We create a new pseudo to compute the
4367 value, and emit a move instruction just before the first use. If, after
4368 register allocation, the new pseudo remains unallocated, the function
4369 move_unallocated_pseudos then deletes the move instruction and places
4370 the computation just before the first use.
4372 Such a move is safe and profitable if all the input registers remain live
4373 and unchanged between the original computation and its first use. In such
4374 a situation, the computation is known to increase register pressure, and
4375 moving it is known to at least not worsen it.
4377 We restrict moves to only those cases where a register remains unallocated,
4378 in order to avoid interfering too much with the instruction schedule. As
4379 an exception, we may move insns which only modify their input register
4380 (typically induction variables), as this increases the freedom for our
4381 intended transformation, and does not limit the second instruction
4382 scheduler pass. */
4384 static void
4385 find_moveable_pseudos (void)
4387 unsigned i;
4388 int max_regs = max_reg_num ();
4389 int max_uid = get_max_uid ();
4390 basic_block bb;
4391 int *uid_luid = XNEWVEC (int, max_uid);
4392 rtx *closest_uses = XNEWVEC (rtx, max_regs);
4393 /* A set of registers which are live but not modified throughout a block. */
4394 bitmap_head *bb_transp_live = XNEWVEC (bitmap_head,
4395 last_basic_block_for_fn (cfun));
4396 /* A set of registers which only exist in a given basic block. */
4397 bitmap_head *bb_local = XNEWVEC (bitmap_head,
4398 last_basic_block_for_fn (cfun));
4399 /* A set of registers which are set once, in an instruction that can be
4400 moved freely downwards, but are otherwise transparent to a block. */
4401 bitmap_head *bb_moveable_reg_sets = XNEWVEC (bitmap_head,
4402 last_basic_block_for_fn (cfun));
4403 bitmap_head live, used, set, interesting, unusable_as_input;
4404 bitmap_iterator bi;
4405 bitmap_initialize (&interesting, 0);
4407 first_moveable_pseudo = max_regs;
4408 pseudo_replaced_reg.release ();
4409 pseudo_replaced_reg.safe_grow_cleared (max_regs);
4411 df_analyze ();
4412 calculate_dominance_info (CDI_DOMINATORS);
4414 i = 0;
4415 bitmap_initialize (&live, 0);
4416 bitmap_initialize (&used, 0);
4417 bitmap_initialize (&set, 0);
4418 bitmap_initialize (&unusable_as_input, 0);
4419 FOR_EACH_BB_FN (bb, cfun)
4421 rtx insn;
4422 bitmap transp = bb_transp_live + bb->index;
4423 bitmap moveable = bb_moveable_reg_sets + bb->index;
4424 bitmap local = bb_local + bb->index;
4426 bitmap_initialize (local, 0);
4427 bitmap_initialize (transp, 0);
4428 bitmap_initialize (moveable, 0);
4429 bitmap_copy (&live, df_get_live_out (bb));
4430 bitmap_and_into (&live, df_get_live_in (bb));
4431 bitmap_copy (transp, &live);
4432 bitmap_clear (moveable);
4433 bitmap_clear (&live);
4434 bitmap_clear (&used);
4435 bitmap_clear (&set);
4436 FOR_BB_INSNS (bb, insn)
4437 if (NONDEBUG_INSN_P (insn))
4439 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4440 df_ref def, use;
4442 uid_luid[INSN_UID (insn)] = i++;
4444 def = df_single_def (insn_info);
4445 use = df_single_use (insn_info);
4446 if (use
4447 && def
4448 && DF_REF_REGNO (use) == DF_REF_REGNO (def)
4449 && !bitmap_bit_p (&set, DF_REF_REGNO (use))
4450 && rtx_moveable_p (&PATTERN (insn), OP_IN))
4452 unsigned regno = DF_REF_REGNO (use);
4453 bitmap_set_bit (moveable, regno);
4454 bitmap_set_bit (&set, regno);
4455 bitmap_set_bit (&used, regno);
4456 bitmap_clear_bit (transp, regno);
4457 continue;
4459 FOR_EACH_INSN_INFO_USE (use, insn_info)
4461 unsigned regno = DF_REF_REGNO (use);
4462 bitmap_set_bit (&used, regno);
4463 if (bitmap_clear_bit (moveable, regno))
4464 bitmap_clear_bit (transp, regno);
4467 FOR_EACH_INSN_INFO_DEF (def, insn_info)
4469 unsigned regno = DF_REF_REGNO (def);
4470 bitmap_set_bit (&set, regno);
4471 bitmap_clear_bit (transp, regno);
4472 bitmap_clear_bit (moveable, regno);
4477 bitmap_clear (&live);
4478 bitmap_clear (&used);
4479 bitmap_clear (&set);
4481 FOR_EACH_BB_FN (bb, cfun)
4483 bitmap local = bb_local + bb->index;
4484 rtx insn;
4486 FOR_BB_INSNS (bb, insn)
4487 if (NONDEBUG_INSN_P (insn))
4489 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4490 rtx def_insn, closest_use, note;
4491 df_ref def, use;
4492 unsigned regno;
4493 bool all_dominated, all_local;
4494 enum machine_mode mode;
4496 def = df_single_def (insn_info);
4497 /* There must be exactly one def in this insn. */
4498 if (!def || !single_set (insn))
4499 continue;
4500 /* This must be the only definition of the reg. We also limit
4501 which modes we deal with so that we can assume we can generate
4502 move instructions. */
4503 regno = DF_REF_REGNO (def);
4504 mode = GET_MODE (DF_REF_REG (def));
4505 if (DF_REG_DEF_COUNT (regno) != 1
4506 || !DF_REF_INSN_INFO (def)
4507 || HARD_REGISTER_NUM_P (regno)
4508 || DF_REG_EQ_USE_COUNT (regno) > 0
4509 || (!INTEGRAL_MODE_P (mode) && !FLOAT_MODE_P (mode)))
4510 continue;
4511 def_insn = DF_REF_INSN (def);
4513 for (note = REG_NOTES (def_insn); note; note = XEXP (note, 1))
4514 if (REG_NOTE_KIND (note) == REG_EQUIV && MEM_P (XEXP (note, 0)))
4515 break;
4517 if (note)
4519 if (dump_file)
4520 fprintf (dump_file, "Ignoring reg %d, has equiv memory\n",
4521 regno);
4522 bitmap_set_bit (&unusable_as_input, regno);
4523 continue;
4526 use = DF_REG_USE_CHAIN (regno);
4527 all_dominated = true;
4528 all_local = true;
4529 closest_use = NULL_RTX;
4530 for (; use; use = DF_REF_NEXT_REG (use))
4532 rtx insn;
4533 if (!DF_REF_INSN_INFO (use))
4535 all_dominated = false;
4536 all_local = false;
4537 break;
4539 insn = DF_REF_INSN (use);
4540 if (DEBUG_INSN_P (insn))
4541 continue;
4542 if (BLOCK_FOR_INSN (insn) != BLOCK_FOR_INSN (def_insn))
4543 all_local = false;
4544 if (!insn_dominated_by_p (insn, def_insn, uid_luid))
4545 all_dominated = false;
4546 if (closest_use != insn && closest_use != const0_rtx)
4548 if (closest_use == NULL_RTX)
4549 closest_use = insn;
4550 else if (insn_dominated_by_p (closest_use, insn, uid_luid))
4551 closest_use = insn;
4552 else if (!insn_dominated_by_p (insn, closest_use, uid_luid))
4553 closest_use = const0_rtx;
4556 if (!all_dominated)
4558 if (dump_file)
4559 fprintf (dump_file, "Reg %d not all uses dominated by set\n",
4560 regno);
4561 continue;
4563 if (all_local)
4564 bitmap_set_bit (local, regno);
4565 if (closest_use == const0_rtx || closest_use == NULL
4566 || next_nonnote_nondebug_insn (def_insn) == closest_use)
4568 if (dump_file)
4569 fprintf (dump_file, "Reg %d uninteresting%s\n", regno,
4570 closest_use == const0_rtx || closest_use == NULL
4571 ? " (no unique first use)" : "");
4572 continue;
4574 #ifdef HAVE_cc0
4575 if (reg_referenced_p (cc0_rtx, PATTERN (closest_use)))
4577 if (dump_file)
4578 fprintf (dump_file, "Reg %d: closest user uses cc0\n",
4579 regno);
4580 continue;
4582 #endif
4583 bitmap_set_bit (&interesting, regno);
4584 closest_uses[regno] = closest_use;
4586 if (dump_file && (all_local || all_dominated))
4588 fprintf (dump_file, "Reg %u:", regno);
4589 if (all_local)
4590 fprintf (dump_file, " local to bb %d", bb->index);
4591 if (all_dominated)
4592 fprintf (dump_file, " def dominates all uses");
4593 if (closest_use != const0_rtx)
4594 fprintf (dump_file, " has unique first use");
4595 fputs ("\n", dump_file);
4600 EXECUTE_IF_SET_IN_BITMAP (&interesting, 0, i, bi)
4602 df_ref def = DF_REG_DEF_CHAIN (i);
4603 rtx def_insn = DF_REF_INSN (def);
4604 basic_block def_block = BLOCK_FOR_INSN (def_insn);
4605 bitmap def_bb_local = bb_local + def_block->index;
4606 bitmap def_bb_moveable = bb_moveable_reg_sets + def_block->index;
4607 bitmap def_bb_transp = bb_transp_live + def_block->index;
4608 bool local_to_bb_p = bitmap_bit_p (def_bb_local, i);
4609 rtx use_insn = closest_uses[i];
4610 df_ref use;
4611 bool all_ok = true;
4612 bool all_transp = true;
4614 if (!REG_P (DF_REF_REG (def)))
4615 continue;
4617 if (!local_to_bb_p)
4619 if (dump_file)
4620 fprintf (dump_file, "Reg %u not local to one basic block\n",
4622 continue;
4624 if (reg_equiv_init (i) != NULL_RTX)
4626 if (dump_file)
4627 fprintf (dump_file, "Ignoring reg %u with equiv init insn\n",
4629 continue;
4631 if (!rtx_moveable_p (&PATTERN (def_insn), OP_IN))
4633 if (dump_file)
4634 fprintf (dump_file, "Found def insn %d for %d to be not moveable\n",
4635 INSN_UID (def_insn), i);
4636 continue;
4638 if (dump_file)
4639 fprintf (dump_file, "Examining insn %d, def for %d\n",
4640 INSN_UID (def_insn), i);
4641 FOR_EACH_INSN_USE (use, def_insn)
4643 unsigned regno = DF_REF_REGNO (use);
4644 if (bitmap_bit_p (&unusable_as_input, regno))
4646 all_ok = false;
4647 if (dump_file)
4648 fprintf (dump_file, " found unusable input reg %u.\n", regno);
4649 break;
4651 if (!bitmap_bit_p (def_bb_transp, regno))
4653 if (bitmap_bit_p (def_bb_moveable, regno)
4654 && !control_flow_insn_p (use_insn)
4655 #ifdef HAVE_cc0
4656 && !sets_cc0_p (use_insn)
4657 #endif
4660 if (modified_between_p (DF_REF_REG (use), def_insn, use_insn))
4662 rtx x = NEXT_INSN (def_insn);
4663 while (!modified_in_p (DF_REF_REG (use), x))
4665 gcc_assert (x != use_insn);
4666 x = NEXT_INSN (x);
4668 if (dump_file)
4669 fprintf (dump_file, " input reg %u modified but insn %d moveable\n",
4670 regno, INSN_UID (x));
4671 emit_insn_after (PATTERN (x), use_insn);
4672 set_insn_deleted (x);
4674 else
4676 if (dump_file)
4677 fprintf (dump_file, " input reg %u modified between def and use\n",
4678 regno);
4679 all_transp = false;
4682 else
4683 all_transp = false;
4686 if (!all_ok)
4687 continue;
4688 if (!dbg_cnt (ira_move))
4689 break;
4690 if (dump_file)
4691 fprintf (dump_file, " all ok%s\n", all_transp ? " and transp" : "");
4693 if (all_transp)
4695 rtx def_reg = DF_REF_REG (def);
4696 rtx newreg = ira_create_new_reg (def_reg);
4697 if (validate_change (def_insn, DF_REF_REAL_LOC (def), newreg, 0))
4699 unsigned nregno = REGNO (newreg);
4700 emit_insn_before (gen_move_insn (def_reg, newreg), use_insn);
4701 nregno -= max_regs;
4702 pseudo_replaced_reg[nregno] = def_reg;
4707 FOR_EACH_BB_FN (bb, cfun)
4709 bitmap_clear (bb_local + bb->index);
4710 bitmap_clear (bb_transp_live + bb->index);
4711 bitmap_clear (bb_moveable_reg_sets + bb->index);
4713 bitmap_clear (&interesting);
4714 bitmap_clear (&unusable_as_input);
4715 free (uid_luid);
4716 free (closest_uses);
4717 free (bb_local);
4718 free (bb_transp_live);
4719 free (bb_moveable_reg_sets);
4721 last_moveable_pseudo = max_reg_num ();
4723 fix_reg_equiv_init ();
4724 expand_reg_info ();
4725 regstat_free_n_sets_and_refs ();
4726 regstat_free_ri ();
4727 regstat_init_n_sets_and_refs ();
4728 regstat_compute_ri ();
4729 free_dominance_info (CDI_DOMINATORS);
4732 /* If SET pattern SET is an assignment from a hard register to a pseudo which
4733 is live at CALL_DOM (if non-NULL, otherwise this check is omitted), return
4734 the destination. Otherwise return NULL. */
4736 static rtx
4737 interesting_dest_for_shprep_1 (rtx set, basic_block call_dom)
4739 rtx src = SET_SRC (set);
4740 rtx dest = SET_DEST (set);
4741 if (!REG_P (src) || !HARD_REGISTER_P (src)
4742 || !REG_P (dest) || HARD_REGISTER_P (dest)
4743 || (call_dom && !bitmap_bit_p (df_get_live_in (call_dom), REGNO (dest))))
4744 return NULL;
4745 return dest;
4748 /* If insn is interesting for parameter range-splitting shring-wrapping
4749 preparation, i.e. it is a single set from a hard register to a pseudo, which
4750 is live at CALL_DOM (if non-NULL, otherwise this check is omitted), or a
4751 parallel statement with only one such statement, return the destination.
4752 Otherwise return NULL. */
4754 static rtx
4755 interesting_dest_for_shprep (rtx insn, basic_block call_dom)
4757 if (!INSN_P (insn))
4758 return NULL;
4759 rtx pat = PATTERN (insn);
4760 if (GET_CODE (pat) == SET)
4761 return interesting_dest_for_shprep_1 (pat, call_dom);
4763 if (GET_CODE (pat) != PARALLEL)
4764 return NULL;
4765 rtx ret = NULL;
4766 for (int i = 0; i < XVECLEN (pat, 0); i++)
4768 rtx sub = XVECEXP (pat, 0, i);
4769 if (GET_CODE (sub) == USE || GET_CODE (sub) == CLOBBER)
4770 continue;
4771 if (GET_CODE (sub) != SET
4772 || side_effects_p (sub))
4773 return NULL;
4774 rtx dest = interesting_dest_for_shprep_1 (sub, call_dom);
4775 if (dest && ret)
4776 return NULL;
4777 if (dest)
4778 ret = dest;
4780 return ret;
4783 /* Split live ranges of pseudos that are loaded from hard registers in the
4784 first BB in a BB that dominates all non-sibling call if such a BB can be
4785 found and is not in a loop. Return true if the function has made any
4786 changes. */
4788 static bool
4789 split_live_ranges_for_shrink_wrap (void)
4791 basic_block bb, call_dom = NULL;
4792 basic_block first = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
4793 rtx insn, last_interesting_insn = NULL;
4794 bitmap_head need_new, reachable;
4795 vec<basic_block> queue;
4797 if (!flag_shrink_wrap)
4798 return false;
4800 bitmap_initialize (&need_new, 0);
4801 bitmap_initialize (&reachable, 0);
4802 queue.create (n_basic_blocks_for_fn (cfun));
4804 FOR_EACH_BB_FN (bb, cfun)
4805 FOR_BB_INSNS (bb, insn)
4806 if (CALL_P (insn) && !SIBLING_CALL_P (insn))
4808 if (bb == first)
4810 bitmap_clear (&need_new);
4811 bitmap_clear (&reachable);
4812 queue.release ();
4813 return false;
4816 bitmap_set_bit (&need_new, bb->index);
4817 bitmap_set_bit (&reachable, bb->index);
4818 queue.quick_push (bb);
4819 break;
4822 if (queue.is_empty ())
4824 bitmap_clear (&need_new);
4825 bitmap_clear (&reachable);
4826 queue.release ();
4827 return false;
4830 while (!queue.is_empty ())
4832 edge e;
4833 edge_iterator ei;
4835 bb = queue.pop ();
4836 FOR_EACH_EDGE (e, ei, bb->succs)
4837 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
4838 && bitmap_set_bit (&reachable, e->dest->index))
4839 queue.quick_push (e->dest);
4841 queue.release ();
4843 FOR_BB_INSNS (first, insn)
4845 rtx dest = interesting_dest_for_shprep (insn, NULL);
4846 if (!dest)
4847 continue;
4849 if (DF_REG_DEF_COUNT (REGNO (dest)) > 1)
4851 bitmap_clear (&need_new);
4852 bitmap_clear (&reachable);
4853 return false;
4856 for (df_ref use = DF_REG_USE_CHAIN (REGNO(dest));
4857 use;
4858 use = DF_REF_NEXT_REG (use))
4860 int ubbi = DF_REF_BB (use)->index;
4861 if (bitmap_bit_p (&reachable, ubbi))
4862 bitmap_set_bit (&need_new, ubbi);
4864 last_interesting_insn = insn;
4867 bitmap_clear (&reachable);
4868 if (!last_interesting_insn)
4870 bitmap_clear (&need_new);
4871 return false;
4874 call_dom = nearest_common_dominator_for_set (CDI_DOMINATORS, &need_new);
4875 bitmap_clear (&need_new);
4876 if (call_dom == first)
4877 return false;
4879 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
4880 while (bb_loop_depth (call_dom) > 0)
4881 call_dom = get_immediate_dominator (CDI_DOMINATORS, call_dom);
4882 loop_optimizer_finalize ();
4884 if (call_dom == first)
4885 return false;
4887 calculate_dominance_info (CDI_POST_DOMINATORS);
4888 if (dominated_by_p (CDI_POST_DOMINATORS, first, call_dom))
4890 free_dominance_info (CDI_POST_DOMINATORS);
4891 return false;
4893 free_dominance_info (CDI_POST_DOMINATORS);
4895 if (dump_file)
4896 fprintf (dump_file, "Will split live ranges of parameters at BB %i\n",
4897 call_dom->index);
4899 bool ret = false;
4900 FOR_BB_INSNS (first, insn)
4902 rtx dest = interesting_dest_for_shprep (insn, call_dom);
4903 if (!dest)
4904 continue;
4906 rtx newreg = NULL_RTX;
4907 df_ref use, next;
4908 for (use = DF_REG_USE_CHAIN (REGNO (dest)); use; use = next)
4910 rtx uin = DF_REF_INSN (use);
4911 next = DF_REF_NEXT_REG (use);
4913 basic_block ubb = BLOCK_FOR_INSN (uin);
4914 if (ubb == call_dom
4915 || dominated_by_p (CDI_DOMINATORS, ubb, call_dom))
4917 if (!newreg)
4918 newreg = ira_create_new_reg (dest);
4919 validate_change (uin, DF_REF_REAL_LOC (use), newreg, true);
4923 if (newreg)
4925 rtx new_move = gen_move_insn (newreg, dest);
4926 emit_insn_after (new_move, bb_note (call_dom));
4927 if (dump_file)
4929 fprintf (dump_file, "Split live-range of register ");
4930 print_rtl_single (dump_file, dest);
4932 ret = true;
4935 if (insn == last_interesting_insn)
4936 break;
4938 apply_change_group ();
4939 return ret;
4942 /* Perform the second half of the transformation started in
4943 find_moveable_pseudos. We look for instances where the newly introduced
4944 pseudo remains unallocated, and remove it by moving the definition to
4945 just before its use, replacing the move instruction generated by
4946 find_moveable_pseudos. */
4947 static void
4948 move_unallocated_pseudos (void)
4950 int i;
4951 for (i = first_moveable_pseudo; i < last_moveable_pseudo; i++)
4952 if (reg_renumber[i] < 0)
4954 int idx = i - first_moveable_pseudo;
4955 rtx other_reg = pseudo_replaced_reg[idx];
4956 rtx def_insn = DF_REF_INSN (DF_REG_DEF_CHAIN (i));
4957 /* The use must follow all definitions of OTHER_REG, so we can
4958 insert the new definition immediately after any of them. */
4959 df_ref other_def = DF_REG_DEF_CHAIN (REGNO (other_reg));
4960 rtx move_insn = DF_REF_INSN (other_def);
4961 rtx newinsn = emit_insn_after (PATTERN (def_insn), move_insn);
4962 rtx set;
4963 int success;
4965 if (dump_file)
4966 fprintf (dump_file, "moving def of %d (insn %d now) ",
4967 REGNO (other_reg), INSN_UID (def_insn));
4969 delete_insn (move_insn);
4970 while ((other_def = DF_REG_DEF_CHAIN (REGNO (other_reg))))
4971 delete_insn (DF_REF_INSN (other_def));
4972 delete_insn (def_insn);
4974 set = single_set (newinsn);
4975 success = validate_change (newinsn, &SET_DEST (set), other_reg, 0);
4976 gcc_assert (success);
4977 if (dump_file)
4978 fprintf (dump_file, " %d) rather than keep unallocated replacement %d\n",
4979 INSN_UID (newinsn), i);
4980 SET_REG_N_REFS (i, 0);
4984 /* If the backend knows where to allocate pseudos for hard
4985 register initial values, register these allocations now. */
4986 static void
4987 allocate_initial_values (void)
4989 if (targetm.allocate_initial_value)
4991 rtx hreg, preg, x;
4992 int i, regno;
4994 for (i = 0; HARD_REGISTER_NUM_P (i); i++)
4996 if (! initial_value_entry (i, &hreg, &preg))
4997 break;
4999 x = targetm.allocate_initial_value (hreg);
5000 regno = REGNO (preg);
5001 if (x && REG_N_SETS (regno) <= 1)
5003 if (MEM_P (x))
5004 reg_equiv_memory_loc (regno) = x;
5005 else
5007 basic_block bb;
5008 int new_regno;
5010 gcc_assert (REG_P (x));
5011 new_regno = REGNO (x);
5012 reg_renumber[regno] = new_regno;
5013 /* Poke the regno right into regno_reg_rtx so that even
5014 fixed regs are accepted. */
5015 SET_REGNO (preg, new_regno);
5016 /* Update global register liveness information. */
5017 FOR_EACH_BB_FN (bb, cfun)
5019 if (REGNO_REG_SET_P (df_get_live_in (bb), regno))
5020 SET_REGNO_REG_SET (df_get_live_in (bb), new_regno);
5021 if (REGNO_REG_SET_P (df_get_live_out (bb), regno))
5022 SET_REGNO_REG_SET (df_get_live_out (bb), new_regno);
5028 gcc_checking_assert (! initial_value_entry (FIRST_PSEUDO_REGISTER,
5029 &hreg, &preg));
5034 /* True when we use LRA instead of reload pass for the current
5035 function. */
5036 bool ira_use_lra_p;
5038 /* True if we have allocno conflicts. It is false for non-optimized
5039 mode or when the conflict table is too big. */
5040 bool ira_conflicts_p;
5042 /* Saved between IRA and reload. */
5043 static int saved_flag_ira_share_spill_slots;
5045 /* This is the main entry of IRA. */
5046 static void
5047 ira (FILE *f)
5049 bool loops_p;
5050 int ira_max_point_before_emit;
5051 int rebuild_p;
5052 bool saved_flag_caller_saves = flag_caller_saves;
5053 enum ira_region saved_flag_ira_region = flag_ira_region;
5055 ira_conflicts_p = optimize > 0;
5057 ira_use_lra_p = targetm.lra_p ();
5058 /* If there are too many pseudos and/or basic blocks (e.g. 10K
5059 pseudos and 10K blocks or 100K pseudos and 1K blocks), we will
5060 use simplified and faster algorithms in LRA. */
5061 lra_simple_p
5062 = (ira_use_lra_p
5063 && max_reg_num () >= (1 << 26) / last_basic_block_for_fn (cfun));
5064 if (lra_simple_p)
5066 /* It permits to skip live range splitting in LRA. */
5067 flag_caller_saves = false;
5068 /* There is no sense to do regional allocation when we use
5069 simplified LRA. */
5070 flag_ira_region = IRA_REGION_ONE;
5071 ira_conflicts_p = false;
5074 #ifndef IRA_NO_OBSTACK
5075 gcc_obstack_init (&ira_obstack);
5076 #endif
5077 bitmap_obstack_initialize (&ira_bitmap_obstack);
5079 /* LRA uses its own infrastructure to handle caller save registers. */
5080 if (flag_caller_saves && !ira_use_lra_p)
5081 init_caller_save ();
5083 if (flag_ira_verbose < 10)
5085 internal_flag_ira_verbose = flag_ira_verbose;
5086 ira_dump_file = f;
5088 else
5090 internal_flag_ira_verbose = flag_ira_verbose - 10;
5091 ira_dump_file = stderr;
5094 setup_prohibited_mode_move_regs ();
5095 decrease_live_ranges_number ();
5096 df_note_add_problem ();
5098 /* DF_LIVE can't be used in the register allocator, too many other
5099 parts of the compiler depend on using the "classic" liveness
5100 interpretation of the DF_LR problem. See PR38711.
5101 Remove the problem, so that we don't spend time updating it in
5102 any of the df_analyze() calls during IRA/LRA. */
5103 if (optimize > 1)
5104 df_remove_problem (df_live);
5105 gcc_checking_assert (df_live == NULL);
5107 #ifdef ENABLE_CHECKING
5108 df->changeable_flags |= DF_VERIFY_SCHEDULED;
5109 #endif
5110 df_analyze ();
5112 init_reg_equiv ();
5113 if (ira_conflicts_p)
5115 calculate_dominance_info (CDI_DOMINATORS);
5117 if (split_live_ranges_for_shrink_wrap ())
5118 df_analyze ();
5120 free_dominance_info (CDI_DOMINATORS);
5123 df_clear_flags (DF_NO_INSN_RESCAN);
5125 regstat_init_n_sets_and_refs ();
5126 regstat_compute_ri ();
5128 /* If we are not optimizing, then this is the only place before
5129 register allocation where dataflow is done. And that is needed
5130 to generate these warnings. */
5131 if (warn_clobbered)
5132 generate_setjmp_warnings ();
5134 /* Determine if the current function is a leaf before running IRA
5135 since this can impact optimizations done by the prologue and
5136 epilogue thus changing register elimination offsets. */
5137 crtl->is_leaf = leaf_function_p ();
5139 if (resize_reg_info () && flag_ira_loop_pressure)
5140 ira_set_pseudo_classes (true, ira_dump_file);
5142 rebuild_p = update_equiv_regs ();
5143 setup_reg_equiv ();
5144 setup_reg_equiv_init ();
5146 if (optimize && rebuild_p)
5148 timevar_push (TV_JUMP);
5149 rebuild_jump_labels (get_insns ());
5150 if (purge_all_dead_edges ())
5151 delete_unreachable_blocks ();
5152 timevar_pop (TV_JUMP);
5155 allocated_reg_info_size = max_reg_num ();
5157 if (delete_trivially_dead_insns (get_insns (), max_reg_num ()))
5158 df_analyze ();
5160 /* It is not worth to do such improvement when we use a simple
5161 allocation because of -O0 usage or because the function is too
5162 big. */
5163 if (ira_conflicts_p)
5164 find_moveable_pseudos ();
5166 max_regno_before_ira = max_reg_num ();
5167 ira_setup_eliminable_regset ();
5169 ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
5170 ira_load_cost = ira_store_cost = ira_shuffle_cost = 0;
5171 ira_move_loops_num = ira_additional_jumps_num = 0;
5173 ira_assert (current_loops == NULL);
5174 if (flag_ira_region == IRA_REGION_ALL || flag_ira_region == IRA_REGION_MIXED)
5175 loop_optimizer_init (AVOID_CFG_MODIFICATIONS | LOOPS_HAVE_RECORDED_EXITS);
5177 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
5178 fprintf (ira_dump_file, "Building IRA IR\n");
5179 loops_p = ira_build ();
5181 ira_assert (ira_conflicts_p || !loops_p);
5183 saved_flag_ira_share_spill_slots = flag_ira_share_spill_slots;
5184 if (too_high_register_pressure_p () || cfun->calls_setjmp)
5185 /* It is just wasting compiler's time to pack spilled pseudos into
5186 stack slots in this case -- prohibit it. We also do this if
5187 there is setjmp call because a variable not modified between
5188 setjmp and longjmp the compiler is required to preserve its
5189 value and sharing slots does not guarantee it. */
5190 flag_ira_share_spill_slots = FALSE;
5192 ira_color ();
5194 ira_max_point_before_emit = ira_max_point;
5196 ira_initiate_emit_data ();
5198 ira_emit (loops_p);
5200 max_regno = max_reg_num ();
5201 if (ira_conflicts_p)
5203 if (! loops_p)
5205 if (! ira_use_lra_p)
5206 ira_initiate_assign ();
5208 else
5210 expand_reg_info ();
5212 if (ira_use_lra_p)
5214 ira_allocno_t a;
5215 ira_allocno_iterator ai;
5217 FOR_EACH_ALLOCNO (a, ai)
5218 ALLOCNO_REGNO (a) = REGNO (ALLOCNO_EMIT_DATA (a)->reg);
5220 else
5222 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
5223 fprintf (ira_dump_file, "Flattening IR\n");
5224 ira_flattening (max_regno_before_ira, ira_max_point_before_emit);
5226 /* New insns were generated: add notes and recalculate live
5227 info. */
5228 df_analyze ();
5230 /* ??? Rebuild the loop tree, but why? Does the loop tree
5231 change if new insns were generated? Can that be handled
5232 by updating the loop tree incrementally? */
5233 loop_optimizer_finalize ();
5234 free_dominance_info (CDI_DOMINATORS);
5235 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
5236 | LOOPS_HAVE_RECORDED_EXITS);
5238 if (! ira_use_lra_p)
5240 setup_allocno_assignment_flags ();
5241 ira_initiate_assign ();
5242 ira_reassign_conflict_allocnos (max_regno);
5247 ira_finish_emit_data ();
5249 setup_reg_renumber ();
5251 calculate_allocation_cost ();
5253 #ifdef ENABLE_IRA_CHECKING
5254 if (ira_conflicts_p)
5255 check_allocation ();
5256 #endif
5258 if (max_regno != max_regno_before_ira)
5260 regstat_free_n_sets_and_refs ();
5261 regstat_free_ri ();
5262 regstat_init_n_sets_and_refs ();
5263 regstat_compute_ri ();
5266 overall_cost_before = ira_overall_cost;
5267 if (! ira_conflicts_p)
5268 grow_reg_equivs ();
5269 else
5271 fix_reg_equiv_init ();
5273 #ifdef ENABLE_IRA_CHECKING
5274 print_redundant_copies ();
5275 #endif
5277 ira_spilled_reg_stack_slots_num = 0;
5278 ira_spilled_reg_stack_slots
5279 = ((struct ira_spilled_reg_stack_slot *)
5280 ira_allocate (max_regno
5281 * sizeof (struct ira_spilled_reg_stack_slot)));
5282 memset (ira_spilled_reg_stack_slots, 0,
5283 max_regno * sizeof (struct ira_spilled_reg_stack_slot));
5285 allocate_initial_values ();
5287 /* See comment for find_moveable_pseudos call. */
5288 if (ira_conflicts_p)
5289 move_unallocated_pseudos ();
5291 /* Restore original values. */
5292 if (lra_simple_p)
5294 flag_caller_saves = saved_flag_caller_saves;
5295 flag_ira_region = saved_flag_ira_region;
5299 static void
5300 do_reload (void)
5302 basic_block bb;
5303 bool need_dce;
5305 if (flag_ira_verbose < 10)
5306 ira_dump_file = dump_file;
5308 timevar_push (TV_RELOAD);
5309 if (ira_use_lra_p)
5311 if (current_loops != NULL)
5313 loop_optimizer_finalize ();
5314 free_dominance_info (CDI_DOMINATORS);
5316 FOR_ALL_BB_FN (bb, cfun)
5317 bb->loop_father = NULL;
5318 current_loops = NULL;
5320 if (ira_conflicts_p)
5321 ira_free (ira_spilled_reg_stack_slots);
5323 ira_destroy ();
5325 lra (ira_dump_file);
5326 /* ???!!! Move it before lra () when we use ira_reg_equiv in
5327 LRA. */
5328 vec_free (reg_equivs);
5329 reg_equivs = NULL;
5330 need_dce = false;
5332 else
5334 df_set_flags (DF_NO_INSN_RESCAN);
5335 build_insn_chain ();
5337 need_dce = reload (get_insns (), ira_conflicts_p);
5341 timevar_pop (TV_RELOAD);
5343 timevar_push (TV_IRA);
5345 if (ira_conflicts_p && ! ira_use_lra_p)
5347 ira_free (ira_spilled_reg_stack_slots);
5348 ira_finish_assign ();
5351 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL
5352 && overall_cost_before != ira_overall_cost)
5353 fprintf (ira_dump_file, "+++Overall after reload %d\n", ira_overall_cost);
5355 flag_ira_share_spill_slots = saved_flag_ira_share_spill_slots;
5357 if (! ira_use_lra_p)
5359 ira_destroy ();
5360 if (current_loops != NULL)
5362 loop_optimizer_finalize ();
5363 free_dominance_info (CDI_DOMINATORS);
5365 FOR_ALL_BB_FN (bb, cfun)
5366 bb->loop_father = NULL;
5367 current_loops = NULL;
5369 regstat_free_ri ();
5370 regstat_free_n_sets_and_refs ();
5373 if (optimize)
5374 cleanup_cfg (CLEANUP_EXPENSIVE);
5376 finish_reg_equiv ();
5378 bitmap_obstack_release (&ira_bitmap_obstack);
5379 #ifndef IRA_NO_OBSTACK
5380 obstack_free (&ira_obstack, NULL);
5381 #endif
5383 /* The code after the reload has changed so much that at this point
5384 we might as well just rescan everything. Note that
5385 df_rescan_all_insns is not going to help here because it does not
5386 touch the artificial uses and defs. */
5387 df_finish_pass (true);
5388 df_scan_alloc (NULL);
5389 df_scan_blocks ();
5391 if (optimize > 1)
5393 df_live_add_problem ();
5394 df_live_set_all_dirty ();
5397 if (optimize)
5398 df_analyze ();
5400 if (need_dce && optimize)
5401 run_fast_dce ();
5403 /* Diagnose uses of the hard frame pointer when it is used as a global
5404 register. Often we can get away with letting the user appropriate
5405 the frame pointer, but we should let them know when code generation
5406 makes that impossible. */
5407 if (global_regs[HARD_FRAME_POINTER_REGNUM] && frame_pointer_needed)
5409 tree decl = global_regs_decl[HARD_FRAME_POINTER_REGNUM];
5410 error_at (DECL_SOURCE_LOCATION (current_function_decl),
5411 "frame pointer required, but reserved");
5412 inform (DECL_SOURCE_LOCATION (decl), "for %qD", decl);
5415 timevar_pop (TV_IRA);
5418 /* Run the integrated register allocator. */
5420 namespace {
5422 const pass_data pass_data_ira =
5424 RTL_PASS, /* type */
5425 "ira", /* name */
5426 OPTGROUP_NONE, /* optinfo_flags */
5427 TV_IRA, /* tv_id */
5428 0, /* properties_required */
5429 0, /* properties_provided */
5430 0, /* properties_destroyed */
5431 0, /* todo_flags_start */
5432 TODO_do_not_ggc_collect, /* todo_flags_finish */
5435 class pass_ira : public rtl_opt_pass
5437 public:
5438 pass_ira (gcc::context *ctxt)
5439 : rtl_opt_pass (pass_data_ira, ctxt)
5442 /* opt_pass methods: */
5443 virtual unsigned int execute (function *)
5445 ira (dump_file);
5446 return 0;
5449 }; // class pass_ira
5451 } // anon namespace
5453 rtl_opt_pass *
5454 make_pass_ira (gcc::context *ctxt)
5456 return new pass_ira (ctxt);
5459 namespace {
5461 const pass_data pass_data_reload =
5463 RTL_PASS, /* type */
5464 "reload", /* name */
5465 OPTGROUP_NONE, /* optinfo_flags */
5466 TV_RELOAD, /* tv_id */
5467 0, /* properties_required */
5468 0, /* properties_provided */
5469 0, /* properties_destroyed */
5470 0, /* todo_flags_start */
5471 0, /* todo_flags_finish */
5474 class pass_reload : public rtl_opt_pass
5476 public:
5477 pass_reload (gcc::context *ctxt)
5478 : rtl_opt_pass (pass_data_reload, ctxt)
5481 /* opt_pass methods: */
5482 virtual unsigned int execute (function *)
5484 do_reload ();
5485 return 0;
5488 }; // class pass_reload
5490 } // anon namespace
5492 rtl_opt_pass *
5493 make_pass_reload (gcc::context *ctxt)
5495 return new pass_reload (ctxt);