[AArch64][14/14] Reuse target_option_current_node when passing pragma string to targe...
[official-gcc.git] / gcc / ira.c
blob23ed1dbcd3992aa6fe4588744ced4b635780b360
1 /* Integrated Register Allocator (IRA) entry point.
2 Copyright (C) 2006-2015 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* The integrated register allocator (IRA) is a
22 regional register allocator performing graph coloring on a top-down
23 traversal of nested regions. Graph coloring in a region is based
24 on Chaitin-Briggs algorithm. It is called integrated because
25 register coalescing, register live range splitting, and choosing a
26 better hard register are done on-the-fly during coloring. Register
27 coalescing and choosing a cheaper hard register is done by hard
28 register preferencing during hard register assigning. The live
29 range splitting is a byproduct of the regional register allocation.
31 Major IRA notions are:
33 o *Region* is a part of CFG where graph coloring based on
34 Chaitin-Briggs algorithm is done. IRA can work on any set of
35 nested CFG regions forming a tree. Currently the regions are
36 the entire function for the root region and natural loops for
37 the other regions. Therefore data structure representing a
38 region is called loop_tree_node.
40 o *Allocno class* is a register class used for allocation of
41 given allocno. It means that only hard register of given
42 register class can be assigned to given allocno. In reality,
43 even smaller subset of (*profitable*) hard registers can be
44 assigned. In rare cases, the subset can be even smaller
45 because our modification of Chaitin-Briggs algorithm requires
46 that sets of hard registers can be assigned to allocnos forms a
47 forest, i.e. the sets can be ordered in a way where any
48 previous set is not intersected with given set or is a superset
49 of given set.
51 o *Pressure class* is a register class belonging to a set of
52 register classes containing all of the hard-registers available
53 for register allocation. The set of all pressure classes for a
54 target is defined in the corresponding machine-description file
55 according some criteria. Register pressure is calculated only
56 for pressure classes and it affects some IRA decisions as
57 forming allocation regions.
59 o *Allocno* represents the live range of a pseudo-register in a
60 region. Besides the obvious attributes like the corresponding
61 pseudo-register number, allocno class, conflicting allocnos and
62 conflicting hard-registers, there are a few allocno attributes
63 which are important for understanding the allocation algorithm:
65 - *Live ranges*. This is a list of ranges of *program points*
66 where the allocno lives. Program points represent places
67 where a pseudo can be born or become dead (there are
68 approximately two times more program points than the insns)
69 and they are represented by integers starting with 0. The
70 live ranges are used to find conflicts between allocnos.
71 They also play very important role for the transformation of
72 the IRA internal representation of several regions into a one
73 region representation. The later is used during the reload
74 pass work because each allocno represents all of the
75 corresponding pseudo-registers.
77 - *Hard-register costs*. This is a vector of size equal to the
78 number of available hard-registers of the allocno class. The
79 cost of a callee-clobbered hard-register for an allocno is
80 increased by the cost of save/restore code around the calls
81 through the given allocno's life. If the allocno is a move
82 instruction operand and another operand is a hard-register of
83 the allocno class, the cost of the hard-register is decreased
84 by the move cost.
86 When an allocno is assigned, the hard-register with minimal
87 full cost is used. Initially, a hard-register's full cost is
88 the corresponding value from the hard-register's cost vector.
89 If the allocno is connected by a *copy* (see below) to
90 another allocno which has just received a hard-register, the
91 cost of the hard-register is decreased. Before choosing a
92 hard-register for an allocno, the allocno's current costs of
93 the hard-registers are modified by the conflict hard-register
94 costs of all of the conflicting allocnos which are not
95 assigned yet.
97 - *Conflict hard-register costs*. This is a vector of the same
98 size as the hard-register costs vector. To permit an
99 unassigned allocno to get a better hard-register, IRA uses
100 this vector to calculate the final full cost of the
101 available hard-registers. Conflict hard-register costs of an
102 unassigned allocno are also changed with a change of the
103 hard-register cost of the allocno when a copy involving the
104 allocno is processed as described above. This is done to
105 show other unassigned allocnos that a given allocno prefers
106 some hard-registers in order to remove the move instruction
107 corresponding to the copy.
109 o *Cap*. If a pseudo-register does not live in a region but
110 lives in a nested region, IRA creates a special allocno called
111 a cap in the outer region. A region cap is also created for a
112 subregion cap.
114 o *Copy*. Allocnos can be connected by copies. Copies are used
115 to modify hard-register costs for allocnos during coloring.
116 Such modifications reflects a preference to use the same
117 hard-register for the allocnos connected by copies. Usually
118 copies are created for move insns (in this case it results in
119 register coalescing). But IRA also creates copies for operands
120 of an insn which should be assigned to the same hard-register
121 due to constraints in the machine description (it usually
122 results in removing a move generated in reload to satisfy
123 the constraints) and copies referring to the allocno which is
124 the output operand of an instruction and the allocno which is
125 an input operand dying in the instruction (creation of such
126 copies results in less register shuffling). IRA *does not*
127 create copies between the same register allocnos from different
128 regions because we use another technique for propagating
129 hard-register preference on the borders of regions.
131 Allocnos (including caps) for the upper region in the region tree
132 *accumulate* information important for coloring from allocnos with
133 the same pseudo-register from nested regions. This includes
134 hard-register and memory costs, conflicts with hard-registers,
135 allocno conflicts, allocno copies and more. *Thus, attributes for
136 allocnos in a region have the same values as if the region had no
137 subregions*. It means that attributes for allocnos in the
138 outermost region corresponding to the function have the same values
139 as though the allocation used only one region which is the entire
140 function. It also means that we can look at IRA work as if the
141 first IRA did allocation for all function then it improved the
142 allocation for loops then their subloops and so on.
144 IRA major passes are:
146 o Building IRA internal representation which consists of the
147 following subpasses:
149 * First, IRA builds regions and creates allocnos (file
150 ira-build.c) and initializes most of their attributes.
152 * Then IRA finds an allocno class for each allocno and
153 calculates its initial (non-accumulated) cost of memory and
154 each hard-register of its allocno class (file ira-cost.c).
156 * IRA creates live ranges of each allocno, calculates register
157 pressure for each pressure class in each region, sets up
158 conflict hard registers for each allocno and info about calls
159 the allocno lives through (file ira-lives.c).
161 * IRA removes low register pressure loops from the regions
162 mostly to speed IRA up (file ira-build.c).
164 * IRA propagates accumulated allocno info from lower region
165 allocnos to corresponding upper region allocnos (file
166 ira-build.c).
168 * IRA creates all caps (file ira-build.c).
170 * Having live-ranges of allocnos and their classes, IRA creates
171 conflicting allocnos for each allocno. Conflicting allocnos
172 are stored as a bit vector or array of pointers to the
173 conflicting allocnos whatever is more profitable (file
174 ira-conflicts.c). At this point IRA creates allocno copies.
176 o Coloring. Now IRA has all necessary info to start graph coloring
177 process. It is done in each region on top-down traverse of the
178 region tree (file ira-color.c). There are following subpasses:
180 * Finding profitable hard registers of corresponding allocno
181 class for each allocno. For example, only callee-saved hard
182 registers are frequently profitable for allocnos living
183 through colors. If the profitable hard register set of
184 allocno does not form a tree based on subset relation, we use
185 some approximation to form the tree. This approximation is
186 used to figure out trivial colorability of allocnos. The
187 approximation is a pretty rare case.
189 * Putting allocnos onto the coloring stack. IRA uses Briggs
190 optimistic coloring which is a major improvement over
191 Chaitin's coloring. Therefore IRA does not spill allocnos at
192 this point. There is some freedom in the order of putting
193 allocnos on the stack which can affect the final result of
194 the allocation. IRA uses some heuristics to improve the
195 order. The major one is to form *threads* from colorable
196 allocnos and push them on the stack by threads. Thread is a
197 set of non-conflicting colorable allocnos connected by
198 copies. The thread contains allocnos from the colorable
199 bucket or colorable allocnos already pushed onto the coloring
200 stack. Pushing thread allocnos one after another onto the
201 stack increases chances of removing copies when the allocnos
202 get the same hard reg.
204 We also use a modification of Chaitin-Briggs algorithm which
205 works for intersected register classes of allocnos. To
206 figure out trivial colorability of allocnos, the mentioned
207 above tree of hard register sets is used. To get an idea how
208 the algorithm works in i386 example, let us consider an
209 allocno to which any general hard register can be assigned.
210 If the allocno conflicts with eight allocnos to which only
211 EAX register can be assigned, given allocno is still
212 trivially colorable because all conflicting allocnos might be
213 assigned only to EAX and all other general hard registers are
214 still free.
216 To get an idea of the used trivial colorability criterion, it
217 is also useful to read article "Graph-Coloring Register
218 Allocation for Irregular Architectures" by Michael D. Smith
219 and Glen Holloway. Major difference between the article
220 approach and approach used in IRA is that Smith's approach
221 takes register classes only from machine description and IRA
222 calculate register classes from intermediate code too
223 (e.g. an explicit usage of hard registers in RTL code for
224 parameter passing can result in creation of additional
225 register classes which contain or exclude the hard
226 registers). That makes IRA approach useful for improving
227 coloring even for architectures with regular register files
228 and in fact some benchmarking shows the improvement for
229 regular class architectures is even bigger than for irregular
230 ones. Another difference is that Smith's approach chooses
231 intersection of classes of all insn operands in which a given
232 pseudo occurs. IRA can use bigger classes if it is still
233 more profitable than memory usage.
235 * Popping the allocnos from the stack and assigning them hard
236 registers. If IRA can not assign a hard register to an
237 allocno and the allocno is coalesced, IRA undoes the
238 coalescing and puts the uncoalesced allocnos onto the stack in
239 the hope that some such allocnos will get a hard register
240 separately. If IRA fails to assign hard register or memory
241 is more profitable for it, IRA spills the allocno. IRA
242 assigns the allocno the hard-register with minimal full
243 allocation cost which reflects the cost of usage of the
244 hard-register for the allocno and cost of usage of the
245 hard-register for allocnos conflicting with given allocno.
247 * Chaitin-Briggs coloring assigns as many pseudos as possible
248 to hard registers. After coloring we try to improve
249 allocation with cost point of view. We improve the
250 allocation by spilling some allocnos and assigning the freed
251 hard registers to other allocnos if it decreases the overall
252 allocation cost.
254 * After allocno assigning in the region, IRA modifies the hard
255 register and memory costs for the corresponding allocnos in
256 the subregions to reflect the cost of possible loads, stores,
257 or moves on the border of the region and its subregions.
258 When default regional allocation algorithm is used
259 (-fira-algorithm=mixed), IRA just propagates the assignment
260 for allocnos if the register pressure in the region for the
261 corresponding pressure class is less than number of available
262 hard registers for given pressure class.
264 o Spill/restore code moving. When IRA performs an allocation
265 by traversing regions in top-down order, it does not know what
266 happens below in the region tree. Therefore, sometimes IRA
267 misses opportunities to perform a better allocation. A simple
268 optimization tries to improve allocation in a region having
269 subregions and containing in another region. If the
270 corresponding allocnos in the subregion are spilled, it spills
271 the region allocno if it is profitable. The optimization
272 implements a simple iterative algorithm performing profitable
273 transformations while they are still possible. It is fast in
274 practice, so there is no real need for a better time complexity
275 algorithm.
277 o Code change. After coloring, two allocnos representing the
278 same pseudo-register outside and inside a region respectively
279 may be assigned to different locations (hard-registers or
280 memory). In this case IRA creates and uses a new
281 pseudo-register inside the region and adds code to move allocno
282 values on the region's borders. This is done during top-down
283 traversal of the regions (file ira-emit.c). In some
284 complicated cases IRA can create a new allocno to move allocno
285 values (e.g. when a swap of values stored in two hard-registers
286 is needed). At this stage, the new allocno is marked as
287 spilled. IRA still creates the pseudo-register and the moves
288 on the region borders even when both allocnos were assigned to
289 the same hard-register. If the reload pass spills a
290 pseudo-register for some reason, the effect will be smaller
291 because another allocno will still be in the hard-register. In
292 most cases, this is better then spilling both allocnos. If
293 reload does not change the allocation for the two
294 pseudo-registers, the trivial move will be removed by
295 post-reload optimizations. IRA does not generate moves for
296 allocnos assigned to the same hard register when the default
297 regional allocation algorithm is used and the register pressure
298 in the region for the corresponding pressure class is less than
299 number of available hard registers for given pressure class.
300 IRA also does some optimizations to remove redundant stores and
301 to reduce code duplication on the region borders.
303 o Flattening internal representation. After changing code, IRA
304 transforms its internal representation for several regions into
305 one region representation (file ira-build.c). This process is
306 called IR flattening. Such process is more complicated than IR
307 rebuilding would be, but is much faster.
309 o After IR flattening, IRA tries to assign hard registers to all
310 spilled allocnos. This is implemented by a simple and fast
311 priority coloring algorithm (see function
312 ira_reassign_conflict_allocnos::ira-color.c). Here new allocnos
313 created during the code change pass can be assigned to hard
314 registers.
316 o At the end IRA calls the reload pass. The reload pass
317 communicates with IRA through several functions in file
318 ira-color.c to improve its decisions in
320 * sharing stack slots for the spilled pseudos based on IRA info
321 about pseudo-register conflicts.
323 * reassigning hard-registers to all spilled pseudos at the end
324 of each reload iteration.
326 * choosing a better hard-register to spill based on IRA info
327 about pseudo-register live ranges and the register pressure
328 in places where the pseudo-register lives.
330 IRA uses a lot of data representing the target processors. These
331 data are initialized in file ira.c.
333 If function has no loops (or the loops are ignored when
334 -fira-algorithm=CB is used), we have classic Chaitin-Briggs
335 coloring (only instead of separate pass of coalescing, we use hard
336 register preferencing). In such case, IRA works much faster
337 because many things are not made (like IR flattening, the
338 spill/restore optimization, and the code change).
340 Literature is worth to read for better understanding the code:
342 o Preston Briggs, Keith D. Cooper, Linda Torczon. Improvements to
343 Graph Coloring Register Allocation.
345 o David Callahan, Brian Koblenz. Register allocation via
346 hierarchical graph coloring.
348 o Keith Cooper, Anshuman Dasgupta, Jason Eckhardt. Revisiting Graph
349 Coloring Register Allocation: A Study of the Chaitin-Briggs and
350 Callahan-Koblenz Algorithms.
352 o Guei-Yuan Lueh, Thomas Gross, and Ali-Reza Adl-Tabatabai. Global
353 Register Allocation Based on Graph Fusion.
355 o Michael D. Smith and Glenn Holloway. Graph-Coloring Register
356 Allocation for Irregular Architectures
358 o Vladimir Makarov. The Integrated Register Allocator for GCC.
360 o Vladimir Makarov. The top-down register allocator for irregular
361 register file architectures.
366 #include "config.h"
367 #include "system.h"
368 #include "coretypes.h"
369 #include "backend.h"
370 #include "tree.h"
371 #include "rtl.h"
372 #include "df.h"
373 #include "regs.h"
374 #include "alias.h"
375 #include "tm_p.h"
376 #include "target.h"
377 #include "flags.h"
378 #include "cfgrtl.h"
379 #include "cfgbuild.h"
380 #include "cfgcleanup.h"
381 #include "insn-config.h"
382 #include "expmed.h"
383 #include "dojump.h"
384 #include "explow.h"
385 #include "calls.h"
386 #include "emit-rtl.h"
387 #include "varasm.h"
388 #include "stmt.h"
389 #include "expr.h"
390 #include "recog.h"
391 #include "params.h"
392 #include "tree-pass.h"
393 #include "output.h"
394 #include "except.h"
395 #include "reload.h"
396 #include "diagnostic-core.h"
397 #include "cfgloop.h"
398 #include "ira.h"
399 #include "alloc-pool.h"
400 #include "ira-int.h"
401 #include "lra.h"
402 #include "dce.h"
403 #include "dbgcnt.h"
404 #include "rtl-iter.h"
405 #include "shrink-wrap.h"
407 struct target_ira default_target_ira;
408 struct target_ira_int default_target_ira_int;
409 #if SWITCHABLE_TARGET
410 struct target_ira *this_target_ira = &default_target_ira;
411 struct target_ira_int *this_target_ira_int = &default_target_ira_int;
412 #endif
414 /* A modified value of flag `-fira-verbose' used internally. */
415 int internal_flag_ira_verbose;
417 /* Dump file of the allocator if it is not NULL. */
418 FILE *ira_dump_file;
420 /* The number of elements in the following array. */
421 int ira_spilled_reg_stack_slots_num;
423 /* The following array contains info about spilled pseudo-registers
424 stack slots used in current function so far. */
425 struct ira_spilled_reg_stack_slot *ira_spilled_reg_stack_slots;
427 /* Correspondingly overall cost of the allocation, overall cost before
428 reload, cost of the allocnos assigned to hard-registers, cost of
429 the allocnos assigned to memory, cost of loads, stores and register
430 move insns generated for pseudo-register live range splitting (see
431 ira-emit.c). */
432 int64_t ira_overall_cost, overall_cost_before;
433 int64_t ira_reg_cost, ira_mem_cost;
434 int64_t ira_load_cost, ira_store_cost, ira_shuffle_cost;
435 int ira_move_loops_num, ira_additional_jumps_num;
437 /* All registers that can be eliminated. */
439 HARD_REG_SET eliminable_regset;
441 /* Value of max_reg_num () before IRA work start. This value helps
442 us to recognize a situation when new pseudos were created during
443 IRA work. */
444 static int max_regno_before_ira;
446 /* Temporary hard reg set used for a different calculation. */
447 static HARD_REG_SET temp_hard_regset;
449 #define last_mode_for_init_move_cost \
450 (this_target_ira_int->x_last_mode_for_init_move_cost)
453 /* The function sets up the map IRA_REG_MODE_HARD_REGSET. */
454 static void
455 setup_reg_mode_hard_regset (void)
457 int i, m, hard_regno;
459 for (m = 0; m < NUM_MACHINE_MODES; m++)
460 for (hard_regno = 0; hard_regno < FIRST_PSEUDO_REGISTER; hard_regno++)
462 CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset[hard_regno][m]);
463 for (i = hard_regno_nregs[hard_regno][m] - 1; i >= 0; i--)
464 if (hard_regno + i < FIRST_PSEUDO_REGISTER)
465 SET_HARD_REG_BIT (ira_reg_mode_hard_regset[hard_regno][m],
466 hard_regno + i);
471 #define no_unit_alloc_regs \
472 (this_target_ira_int->x_no_unit_alloc_regs)
474 /* The function sets up the three arrays declared above. */
475 static void
476 setup_class_hard_regs (void)
478 int cl, i, hard_regno, n;
479 HARD_REG_SET processed_hard_reg_set;
481 ira_assert (SHRT_MAX >= FIRST_PSEUDO_REGISTER);
482 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
484 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
485 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
486 CLEAR_HARD_REG_SET (processed_hard_reg_set);
487 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
489 ira_non_ordered_class_hard_regs[cl][i] = -1;
490 ira_class_hard_reg_index[cl][i] = -1;
492 for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
494 #ifdef REG_ALLOC_ORDER
495 hard_regno = reg_alloc_order[i];
496 #else
497 hard_regno = i;
498 #endif
499 if (TEST_HARD_REG_BIT (processed_hard_reg_set, hard_regno))
500 continue;
501 SET_HARD_REG_BIT (processed_hard_reg_set, hard_regno);
502 if (! TEST_HARD_REG_BIT (temp_hard_regset, hard_regno))
503 ira_class_hard_reg_index[cl][hard_regno] = -1;
504 else
506 ira_class_hard_reg_index[cl][hard_regno] = n;
507 ira_class_hard_regs[cl][n++] = hard_regno;
510 ira_class_hard_regs_num[cl] = n;
511 for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
512 if (TEST_HARD_REG_BIT (temp_hard_regset, i))
513 ira_non_ordered_class_hard_regs[cl][n++] = i;
514 ira_assert (ira_class_hard_regs_num[cl] == n);
518 /* Set up global variables defining info about hard registers for the
519 allocation. These depend on USE_HARD_FRAME_P whose TRUE value means
520 that we can use the hard frame pointer for the allocation. */
521 static void
522 setup_alloc_regs (bool use_hard_frame_p)
524 #ifdef ADJUST_REG_ALLOC_ORDER
525 ADJUST_REG_ALLOC_ORDER;
526 #endif
527 COPY_HARD_REG_SET (no_unit_alloc_regs, fixed_reg_set);
528 if (! use_hard_frame_p)
529 SET_HARD_REG_BIT (no_unit_alloc_regs, HARD_FRAME_POINTER_REGNUM);
530 setup_class_hard_regs ();
535 #define alloc_reg_class_subclasses \
536 (this_target_ira_int->x_alloc_reg_class_subclasses)
538 /* Initialize the table of subclasses of each reg class. */
539 static void
540 setup_reg_subclasses (void)
542 int i, j;
543 HARD_REG_SET temp_hard_regset2;
545 for (i = 0; i < N_REG_CLASSES; i++)
546 for (j = 0; j < N_REG_CLASSES; j++)
547 alloc_reg_class_subclasses[i][j] = LIM_REG_CLASSES;
549 for (i = 0; i < N_REG_CLASSES; i++)
551 if (i == (int) NO_REGS)
552 continue;
554 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
555 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
556 if (hard_reg_set_empty_p (temp_hard_regset))
557 continue;
558 for (j = 0; j < N_REG_CLASSES; j++)
559 if (i != j)
561 enum reg_class *p;
563 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[j]);
564 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
565 if (! hard_reg_set_subset_p (temp_hard_regset,
566 temp_hard_regset2))
567 continue;
568 p = &alloc_reg_class_subclasses[j][0];
569 while (*p != LIM_REG_CLASSES) p++;
570 *p = (enum reg_class) i;
577 /* Set up IRA_MEMORY_MOVE_COST and IRA_MAX_MEMORY_MOVE_COST. */
578 static void
579 setup_class_subset_and_memory_move_costs (void)
581 int cl, cl2, mode, cost;
582 HARD_REG_SET temp_hard_regset2;
584 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
585 ira_memory_move_cost[mode][NO_REGS][0]
586 = ira_memory_move_cost[mode][NO_REGS][1] = SHRT_MAX;
587 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
589 if (cl != (int) NO_REGS)
590 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
592 ira_max_memory_move_cost[mode][cl][0]
593 = ira_memory_move_cost[mode][cl][0]
594 = memory_move_cost ((machine_mode) mode,
595 (reg_class_t) cl, false);
596 ira_max_memory_move_cost[mode][cl][1]
597 = ira_memory_move_cost[mode][cl][1]
598 = memory_move_cost ((machine_mode) mode,
599 (reg_class_t) cl, true);
600 /* Costs for NO_REGS are used in cost calculation on the
601 1st pass when the preferred register classes are not
602 known yet. In this case we take the best scenario. */
603 if (ira_memory_move_cost[mode][NO_REGS][0]
604 > ira_memory_move_cost[mode][cl][0])
605 ira_max_memory_move_cost[mode][NO_REGS][0]
606 = ira_memory_move_cost[mode][NO_REGS][0]
607 = ira_memory_move_cost[mode][cl][0];
608 if (ira_memory_move_cost[mode][NO_REGS][1]
609 > ira_memory_move_cost[mode][cl][1])
610 ira_max_memory_move_cost[mode][NO_REGS][1]
611 = ira_memory_move_cost[mode][NO_REGS][1]
612 = ira_memory_move_cost[mode][cl][1];
615 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
616 for (cl2 = (int) N_REG_CLASSES - 1; cl2 >= 0; cl2--)
618 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
619 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
620 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]);
621 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
622 ira_class_subset_p[cl][cl2]
623 = hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2);
624 if (! hard_reg_set_empty_p (temp_hard_regset2)
625 && hard_reg_set_subset_p (reg_class_contents[cl2],
626 reg_class_contents[cl]))
627 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
629 cost = ira_memory_move_cost[mode][cl2][0];
630 if (cost > ira_max_memory_move_cost[mode][cl][0])
631 ira_max_memory_move_cost[mode][cl][0] = cost;
632 cost = ira_memory_move_cost[mode][cl2][1];
633 if (cost > ira_max_memory_move_cost[mode][cl][1])
634 ira_max_memory_move_cost[mode][cl][1] = cost;
637 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
638 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
640 ira_memory_move_cost[mode][cl][0]
641 = ira_max_memory_move_cost[mode][cl][0];
642 ira_memory_move_cost[mode][cl][1]
643 = ira_max_memory_move_cost[mode][cl][1];
645 setup_reg_subclasses ();
650 /* Define the following macro if allocation through malloc if
651 preferable. */
652 #define IRA_NO_OBSTACK
654 #ifndef IRA_NO_OBSTACK
655 /* Obstack used for storing all dynamic data (except bitmaps) of the
656 IRA. */
657 static struct obstack ira_obstack;
658 #endif
660 /* Obstack used for storing all bitmaps of the IRA. */
661 static struct bitmap_obstack ira_bitmap_obstack;
663 /* Allocate memory of size LEN for IRA data. */
664 void *
665 ira_allocate (size_t len)
667 void *res;
669 #ifndef IRA_NO_OBSTACK
670 res = obstack_alloc (&ira_obstack, len);
671 #else
672 res = xmalloc (len);
673 #endif
674 return res;
677 /* Free memory ADDR allocated for IRA data. */
678 void
679 ira_free (void *addr ATTRIBUTE_UNUSED)
681 #ifndef IRA_NO_OBSTACK
682 /* do nothing */
683 #else
684 free (addr);
685 #endif
689 /* Allocate and returns bitmap for IRA. */
690 bitmap
691 ira_allocate_bitmap (void)
693 return BITMAP_ALLOC (&ira_bitmap_obstack);
696 /* Free bitmap B allocated for IRA. */
697 void
698 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED)
700 /* do nothing */
705 /* Output information about allocation of all allocnos (except for
706 caps) into file F. */
707 void
708 ira_print_disposition (FILE *f)
710 int i, n, max_regno;
711 ira_allocno_t a;
712 basic_block bb;
714 fprintf (f, "Disposition:");
715 max_regno = max_reg_num ();
716 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
717 for (a = ira_regno_allocno_map[i];
718 a != NULL;
719 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
721 if (n % 4 == 0)
722 fprintf (f, "\n");
723 n++;
724 fprintf (f, " %4d:r%-4d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
725 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
726 fprintf (f, "b%-3d", bb->index);
727 else
728 fprintf (f, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
729 if (ALLOCNO_HARD_REGNO (a) >= 0)
730 fprintf (f, " %3d", ALLOCNO_HARD_REGNO (a));
731 else
732 fprintf (f, " mem");
734 fprintf (f, "\n");
737 /* Outputs information about allocation of all allocnos into
738 stderr. */
739 void
740 ira_debug_disposition (void)
742 ira_print_disposition (stderr);
747 /* Set up ira_stack_reg_pressure_class which is the biggest pressure
748 register class containing stack registers or NO_REGS if there are
749 no stack registers. To find this class, we iterate through all
750 register pressure classes and choose the first register pressure
751 class containing all the stack registers and having the biggest
752 size. */
753 static void
754 setup_stack_reg_pressure_class (void)
756 ira_stack_reg_pressure_class = NO_REGS;
757 #ifdef STACK_REGS
759 int i, best, size;
760 enum reg_class cl;
761 HARD_REG_SET temp_hard_regset2;
763 CLEAR_HARD_REG_SET (temp_hard_regset);
764 for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
765 SET_HARD_REG_BIT (temp_hard_regset, i);
766 best = 0;
767 for (i = 0; i < ira_pressure_classes_num; i++)
769 cl = ira_pressure_classes[i];
770 COPY_HARD_REG_SET (temp_hard_regset2, temp_hard_regset);
771 AND_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
772 size = hard_reg_set_size (temp_hard_regset2);
773 if (best < size)
775 best = size;
776 ira_stack_reg_pressure_class = cl;
780 #endif
783 /* Find pressure classes which are register classes for which we
784 calculate register pressure in IRA, register pressure sensitive
785 insn scheduling, and register pressure sensitive loop invariant
786 motion.
788 To make register pressure calculation easy, we always use
789 non-intersected register pressure classes. A move of hard
790 registers from one register pressure class is not more expensive
791 than load and store of the hard registers. Most likely an allocno
792 class will be a subset of a register pressure class and in many
793 cases a register pressure class. That makes usage of register
794 pressure classes a good approximation to find a high register
795 pressure. */
796 static void
797 setup_pressure_classes (void)
799 int cost, i, n, curr;
800 int cl, cl2;
801 enum reg_class pressure_classes[N_REG_CLASSES];
802 int m;
803 HARD_REG_SET temp_hard_regset2;
804 bool insert_p;
806 n = 0;
807 for (cl = 0; cl < N_REG_CLASSES; cl++)
809 if (ira_class_hard_regs_num[cl] == 0)
810 continue;
811 if (ira_class_hard_regs_num[cl] != 1
812 /* A register class without subclasses may contain a few
813 hard registers and movement between them is costly
814 (e.g. SPARC FPCC registers). We still should consider it
815 as a candidate for a pressure class. */
816 && alloc_reg_class_subclasses[cl][0] < cl)
818 /* Check that the moves between any hard registers of the
819 current class are not more expensive for a legal mode
820 than load/store of the hard registers of the current
821 class. Such class is a potential candidate to be a
822 register pressure class. */
823 for (m = 0; m < NUM_MACHINE_MODES; m++)
825 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
826 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
827 AND_COMPL_HARD_REG_SET (temp_hard_regset,
828 ira_prohibited_class_mode_regs[cl][m]);
829 if (hard_reg_set_empty_p (temp_hard_regset))
830 continue;
831 ira_init_register_move_cost_if_necessary ((machine_mode) m);
832 cost = ira_register_move_cost[m][cl][cl];
833 if (cost <= ira_max_memory_move_cost[m][cl][1]
834 || cost <= ira_max_memory_move_cost[m][cl][0])
835 break;
837 if (m >= NUM_MACHINE_MODES)
838 continue;
840 curr = 0;
841 insert_p = true;
842 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
843 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
844 /* Remove so far added pressure classes which are subset of the
845 current candidate class. Prefer GENERAL_REGS as a pressure
846 register class to another class containing the same
847 allocatable hard registers. We do this because machine
848 dependent cost hooks might give wrong costs for the latter
849 class but always give the right cost for the former class
850 (GENERAL_REGS). */
851 for (i = 0; i < n; i++)
853 cl2 = pressure_classes[i];
854 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]);
855 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
856 if (hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2)
857 && (! hard_reg_set_equal_p (temp_hard_regset, temp_hard_regset2)
858 || cl2 == (int) GENERAL_REGS))
860 pressure_classes[curr++] = (enum reg_class) cl2;
861 insert_p = false;
862 continue;
864 if (hard_reg_set_subset_p (temp_hard_regset2, temp_hard_regset)
865 && (! hard_reg_set_equal_p (temp_hard_regset2, temp_hard_regset)
866 || cl == (int) GENERAL_REGS))
867 continue;
868 if (hard_reg_set_equal_p (temp_hard_regset2, temp_hard_regset))
869 insert_p = false;
870 pressure_classes[curr++] = (enum reg_class) cl2;
872 /* If the current candidate is a subset of a so far added
873 pressure class, don't add it to the list of the pressure
874 classes. */
875 if (insert_p)
876 pressure_classes[curr++] = (enum reg_class) cl;
877 n = curr;
879 #ifdef ENABLE_IRA_CHECKING
881 HARD_REG_SET ignore_hard_regs;
883 /* Check pressure classes correctness: here we check that hard
884 registers from all register pressure classes contains all hard
885 registers available for the allocation. */
886 CLEAR_HARD_REG_SET (temp_hard_regset);
887 CLEAR_HARD_REG_SET (temp_hard_regset2);
888 COPY_HARD_REG_SET (ignore_hard_regs, no_unit_alloc_regs);
889 for (cl = 0; cl < LIM_REG_CLASSES; cl++)
891 /* For some targets (like MIPS with MD_REGS), there are some
892 classes with hard registers available for allocation but
893 not able to hold value of any mode. */
894 for (m = 0; m < NUM_MACHINE_MODES; m++)
895 if (contains_reg_of_mode[cl][m])
896 break;
897 if (m >= NUM_MACHINE_MODES)
899 IOR_HARD_REG_SET (ignore_hard_regs, reg_class_contents[cl]);
900 continue;
902 for (i = 0; i < n; i++)
903 if ((int) pressure_classes[i] == cl)
904 break;
905 IOR_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
906 if (i < n)
907 IOR_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
909 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
910 /* Some targets (like SPARC with ICC reg) have allocatable regs
911 for which no reg class is defined. */
912 if (REGNO_REG_CLASS (i) == NO_REGS)
913 SET_HARD_REG_BIT (ignore_hard_regs, i);
914 AND_COMPL_HARD_REG_SET (temp_hard_regset, ignore_hard_regs);
915 AND_COMPL_HARD_REG_SET (temp_hard_regset2, ignore_hard_regs);
916 ira_assert (hard_reg_set_subset_p (temp_hard_regset2, temp_hard_regset));
918 #endif
919 ira_pressure_classes_num = 0;
920 for (i = 0; i < n; i++)
922 cl = (int) pressure_classes[i];
923 ira_reg_pressure_class_p[cl] = true;
924 ira_pressure_classes[ira_pressure_classes_num++] = (enum reg_class) cl;
926 setup_stack_reg_pressure_class ();
929 /* Set up IRA_UNIFORM_CLASS_P. Uniform class is a register class
930 whose register move cost between any registers of the class is the
931 same as for all its subclasses. We use the data to speed up the
932 2nd pass of calculations of allocno costs. */
933 static void
934 setup_uniform_class_p (void)
936 int i, cl, cl2, m;
938 for (cl = 0; cl < N_REG_CLASSES; cl++)
940 ira_uniform_class_p[cl] = false;
941 if (ira_class_hard_regs_num[cl] == 0)
942 continue;
943 /* We can not use alloc_reg_class_subclasses here because move
944 cost hooks does not take into account that some registers are
945 unavailable for the subtarget. E.g. for i686, INT_SSE_REGS
946 is element of alloc_reg_class_subclasses for GENERAL_REGS
947 because SSE regs are unavailable. */
948 for (i = 0; (cl2 = reg_class_subclasses[cl][i]) != LIM_REG_CLASSES; i++)
950 if (ira_class_hard_regs_num[cl2] == 0)
951 continue;
952 for (m = 0; m < NUM_MACHINE_MODES; m++)
953 if (contains_reg_of_mode[cl][m] && contains_reg_of_mode[cl2][m])
955 ira_init_register_move_cost_if_necessary ((machine_mode) m);
956 if (ira_register_move_cost[m][cl][cl]
957 != ira_register_move_cost[m][cl2][cl2])
958 break;
960 if (m < NUM_MACHINE_MODES)
961 break;
963 if (cl2 == LIM_REG_CLASSES)
964 ira_uniform_class_p[cl] = true;
968 /* Set up IRA_ALLOCNO_CLASSES, IRA_ALLOCNO_CLASSES_NUM,
969 IRA_IMPORTANT_CLASSES, and IRA_IMPORTANT_CLASSES_NUM.
971 Target may have many subtargets and not all target hard registers can
972 be used for allocation, e.g. x86 port in 32-bit mode can not use
973 hard registers introduced in x86-64 like r8-r15). Some classes
974 might have the same allocatable hard registers, e.g. INDEX_REGS
975 and GENERAL_REGS in x86 port in 32-bit mode. To decrease different
976 calculations efforts we introduce allocno classes which contain
977 unique non-empty sets of allocatable hard-registers.
979 Pseudo class cost calculation in ira-costs.c is very expensive.
980 Therefore we are trying to decrease number of classes involved in
981 such calculation. Register classes used in the cost calculation
982 are called important classes. They are allocno classes and other
983 non-empty classes whose allocatable hard register sets are inside
984 of an allocno class hard register set. From the first sight, it
985 looks like that they are just allocno classes. It is not true. In
986 example of x86-port in 32-bit mode, allocno classes will contain
987 GENERAL_REGS but not LEGACY_REGS (because allocatable hard
988 registers are the same for the both classes). The important
989 classes will contain GENERAL_REGS and LEGACY_REGS. It is done
990 because a machine description insn constraint may refers for
991 LEGACY_REGS and code in ira-costs.c is mostly base on investigation
992 of the insn constraints. */
993 static void
994 setup_allocno_and_important_classes (void)
996 int i, j, n, cl;
997 bool set_p;
998 HARD_REG_SET temp_hard_regset2;
999 static enum reg_class classes[LIM_REG_CLASSES + 1];
1001 n = 0;
1002 /* Collect classes which contain unique sets of allocatable hard
1003 registers. Prefer GENERAL_REGS to other classes containing the
1004 same set of hard registers. */
1005 for (i = 0; i < LIM_REG_CLASSES; i++)
1007 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
1008 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1009 for (j = 0; j < n; j++)
1011 cl = classes[j];
1012 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
1013 AND_COMPL_HARD_REG_SET (temp_hard_regset2,
1014 no_unit_alloc_regs);
1015 if (hard_reg_set_equal_p (temp_hard_regset,
1016 temp_hard_regset2))
1017 break;
1019 if (j >= n)
1020 classes[n++] = (enum reg_class) i;
1021 else if (i == GENERAL_REGS)
1022 /* Prefer general regs. For i386 example, it means that
1023 we prefer GENERAL_REGS over INDEX_REGS or LEGACY_REGS
1024 (all of them consists of the same available hard
1025 registers). */
1026 classes[j] = (enum reg_class) i;
1028 classes[n] = LIM_REG_CLASSES;
1030 /* Set up classes which can be used for allocnos as classes
1031 containing non-empty unique sets of allocatable hard
1032 registers. */
1033 ira_allocno_classes_num = 0;
1034 for (i = 0; (cl = classes[i]) != LIM_REG_CLASSES; i++)
1035 if (ira_class_hard_regs_num[cl] > 0)
1036 ira_allocno_classes[ira_allocno_classes_num++] = (enum reg_class) cl;
1037 ira_important_classes_num = 0;
1038 /* Add non-allocno classes containing to non-empty set of
1039 allocatable hard regs. */
1040 for (cl = 0; cl < N_REG_CLASSES; cl++)
1041 if (ira_class_hard_regs_num[cl] > 0)
1043 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
1044 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1045 set_p = false;
1046 for (j = 0; j < ira_allocno_classes_num; j++)
1048 COPY_HARD_REG_SET (temp_hard_regset2,
1049 reg_class_contents[ira_allocno_classes[j]]);
1050 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
1051 if ((enum reg_class) cl == ira_allocno_classes[j])
1052 break;
1053 else if (hard_reg_set_subset_p (temp_hard_regset,
1054 temp_hard_regset2))
1055 set_p = true;
1057 if (set_p && j >= ira_allocno_classes_num)
1058 ira_important_classes[ira_important_classes_num++]
1059 = (enum reg_class) cl;
1061 /* Now add allocno classes to the important classes. */
1062 for (j = 0; j < ira_allocno_classes_num; j++)
1063 ira_important_classes[ira_important_classes_num++]
1064 = ira_allocno_classes[j];
1065 for (cl = 0; cl < N_REG_CLASSES; cl++)
1067 ira_reg_allocno_class_p[cl] = false;
1068 ira_reg_pressure_class_p[cl] = false;
1070 for (j = 0; j < ira_allocno_classes_num; j++)
1071 ira_reg_allocno_class_p[ira_allocno_classes[j]] = true;
1072 setup_pressure_classes ();
1073 setup_uniform_class_p ();
1076 /* Setup translation in CLASS_TRANSLATE of all classes into a class
1077 given by array CLASSES of length CLASSES_NUM. The function is used
1078 make translation any reg class to an allocno class or to an
1079 pressure class. This translation is necessary for some
1080 calculations when we can use only allocno or pressure classes and
1081 such translation represents an approximate representation of all
1082 classes.
1084 The translation in case when allocatable hard register set of a
1085 given class is subset of allocatable hard register set of a class
1086 in CLASSES is pretty simple. We use smallest classes from CLASSES
1087 containing a given class. If allocatable hard register set of a
1088 given class is not a subset of any corresponding set of a class
1089 from CLASSES, we use the cheapest (with load/store point of view)
1090 class from CLASSES whose set intersects with given class set. */
1091 static void
1092 setup_class_translate_array (enum reg_class *class_translate,
1093 int classes_num, enum reg_class *classes)
1095 int cl, mode;
1096 enum reg_class aclass, best_class, *cl_ptr;
1097 int i, cost, min_cost, best_cost;
1099 for (cl = 0; cl < N_REG_CLASSES; cl++)
1100 class_translate[cl] = NO_REGS;
1102 for (i = 0; i < classes_num; i++)
1104 aclass = classes[i];
1105 for (cl_ptr = &alloc_reg_class_subclasses[aclass][0];
1106 (cl = *cl_ptr) != LIM_REG_CLASSES;
1107 cl_ptr++)
1108 if (class_translate[cl] == NO_REGS)
1109 class_translate[cl] = aclass;
1110 class_translate[aclass] = aclass;
1112 /* For classes which are not fully covered by one of given classes
1113 (in other words covered by more one given class), use the
1114 cheapest class. */
1115 for (cl = 0; cl < N_REG_CLASSES; cl++)
1117 if (cl == NO_REGS || class_translate[cl] != NO_REGS)
1118 continue;
1119 best_class = NO_REGS;
1120 best_cost = INT_MAX;
1121 for (i = 0; i < classes_num; i++)
1123 aclass = classes[i];
1124 COPY_HARD_REG_SET (temp_hard_regset,
1125 reg_class_contents[aclass]);
1126 AND_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
1127 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1128 if (! hard_reg_set_empty_p (temp_hard_regset))
1130 min_cost = INT_MAX;
1131 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1133 cost = (ira_memory_move_cost[mode][aclass][0]
1134 + ira_memory_move_cost[mode][aclass][1]);
1135 if (min_cost > cost)
1136 min_cost = cost;
1138 if (best_class == NO_REGS || best_cost > min_cost)
1140 best_class = aclass;
1141 best_cost = min_cost;
1145 class_translate[cl] = best_class;
1149 /* Set up array IRA_ALLOCNO_CLASS_TRANSLATE and
1150 IRA_PRESSURE_CLASS_TRANSLATE. */
1151 static void
1152 setup_class_translate (void)
1154 setup_class_translate_array (ira_allocno_class_translate,
1155 ira_allocno_classes_num, ira_allocno_classes);
1156 setup_class_translate_array (ira_pressure_class_translate,
1157 ira_pressure_classes_num, ira_pressure_classes);
1160 /* Order numbers of allocno classes in original target allocno class
1161 array, -1 for non-allocno classes. */
1162 static int allocno_class_order[N_REG_CLASSES];
1164 /* The function used to sort the important classes. */
1165 static int
1166 comp_reg_classes_func (const void *v1p, const void *v2p)
1168 enum reg_class cl1 = *(const enum reg_class *) v1p;
1169 enum reg_class cl2 = *(const enum reg_class *) v2p;
1170 enum reg_class tcl1, tcl2;
1171 int diff;
1173 tcl1 = ira_allocno_class_translate[cl1];
1174 tcl2 = ira_allocno_class_translate[cl2];
1175 if (tcl1 != NO_REGS && tcl2 != NO_REGS
1176 && (diff = allocno_class_order[tcl1] - allocno_class_order[tcl2]) != 0)
1177 return diff;
1178 return (int) cl1 - (int) cl2;
1181 /* For correct work of function setup_reg_class_relation we need to
1182 reorder important classes according to the order of their allocno
1183 classes. It places important classes containing the same
1184 allocatable hard register set adjacent to each other and allocno
1185 class with the allocatable hard register set right after the other
1186 important classes with the same set.
1188 In example from comments of function
1189 setup_allocno_and_important_classes, it places LEGACY_REGS and
1190 GENERAL_REGS close to each other and GENERAL_REGS is after
1191 LEGACY_REGS. */
1192 static void
1193 reorder_important_classes (void)
1195 int i;
1197 for (i = 0; i < N_REG_CLASSES; i++)
1198 allocno_class_order[i] = -1;
1199 for (i = 0; i < ira_allocno_classes_num; i++)
1200 allocno_class_order[ira_allocno_classes[i]] = i;
1201 qsort (ira_important_classes, ira_important_classes_num,
1202 sizeof (enum reg_class), comp_reg_classes_func);
1203 for (i = 0; i < ira_important_classes_num; i++)
1204 ira_important_class_nums[ira_important_classes[i]] = i;
1207 /* Set up IRA_REG_CLASS_SUBUNION, IRA_REG_CLASS_SUPERUNION,
1208 IRA_REG_CLASS_SUPER_CLASSES, IRA_REG_CLASSES_INTERSECT, and
1209 IRA_REG_CLASSES_INTERSECT_P. For the meaning of the relations,
1210 please see corresponding comments in ira-int.h. */
1211 static void
1212 setup_reg_class_relations (void)
1214 int i, cl1, cl2, cl3;
1215 HARD_REG_SET intersection_set, union_set, temp_set2;
1216 bool important_class_p[N_REG_CLASSES];
1218 memset (important_class_p, 0, sizeof (important_class_p));
1219 for (i = 0; i < ira_important_classes_num; i++)
1220 important_class_p[ira_important_classes[i]] = true;
1221 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1223 ira_reg_class_super_classes[cl1][0] = LIM_REG_CLASSES;
1224 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1226 ira_reg_classes_intersect_p[cl1][cl2] = false;
1227 ira_reg_class_intersect[cl1][cl2] = NO_REGS;
1228 ira_reg_class_subset[cl1][cl2] = NO_REGS;
1229 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl1]);
1230 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1231 COPY_HARD_REG_SET (temp_set2, reg_class_contents[cl2]);
1232 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1233 if (hard_reg_set_empty_p (temp_hard_regset)
1234 && hard_reg_set_empty_p (temp_set2))
1236 /* The both classes have no allocatable hard registers
1237 -- take all class hard registers into account and use
1238 reg_class_subunion and reg_class_superunion. */
1239 for (i = 0;; i++)
1241 cl3 = reg_class_subclasses[cl1][i];
1242 if (cl3 == LIM_REG_CLASSES)
1243 break;
1244 if (reg_class_subset_p (ira_reg_class_intersect[cl1][cl2],
1245 (enum reg_class) cl3))
1246 ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
1248 ira_reg_class_subunion[cl1][cl2] = reg_class_subunion[cl1][cl2];
1249 ira_reg_class_superunion[cl1][cl2] = reg_class_superunion[cl1][cl2];
1250 continue;
1252 ira_reg_classes_intersect_p[cl1][cl2]
1253 = hard_reg_set_intersect_p (temp_hard_regset, temp_set2);
1254 if (important_class_p[cl1] && important_class_p[cl2]
1255 && hard_reg_set_subset_p (temp_hard_regset, temp_set2))
1257 /* CL1 and CL2 are important classes and CL1 allocatable
1258 hard register set is inside of CL2 allocatable hard
1259 registers -- make CL1 a superset of CL2. */
1260 enum reg_class *p;
1262 p = &ira_reg_class_super_classes[cl1][0];
1263 while (*p != LIM_REG_CLASSES)
1264 p++;
1265 *p++ = (enum reg_class) cl2;
1266 *p = LIM_REG_CLASSES;
1268 ira_reg_class_subunion[cl1][cl2] = NO_REGS;
1269 ira_reg_class_superunion[cl1][cl2] = NO_REGS;
1270 COPY_HARD_REG_SET (intersection_set, reg_class_contents[cl1]);
1271 AND_HARD_REG_SET (intersection_set, reg_class_contents[cl2]);
1272 AND_COMPL_HARD_REG_SET (intersection_set, no_unit_alloc_regs);
1273 COPY_HARD_REG_SET (union_set, reg_class_contents[cl1]);
1274 IOR_HARD_REG_SET (union_set, reg_class_contents[cl2]);
1275 AND_COMPL_HARD_REG_SET (union_set, no_unit_alloc_regs);
1276 for (cl3 = 0; cl3 < N_REG_CLASSES; cl3++)
1278 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl3]);
1279 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1280 if (hard_reg_set_subset_p (temp_hard_regset, intersection_set))
1282 /* CL3 allocatable hard register set is inside of
1283 intersection of allocatable hard register sets
1284 of CL1 and CL2. */
1285 if (important_class_p[cl3])
1287 COPY_HARD_REG_SET
1288 (temp_set2,
1289 reg_class_contents
1290 [(int) ira_reg_class_intersect[cl1][cl2]]);
1291 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1292 if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1293 /* If the allocatable hard register sets are
1294 the same, prefer GENERAL_REGS or the
1295 smallest class for debugging
1296 purposes. */
1297 || (hard_reg_set_equal_p (temp_hard_regset, temp_set2)
1298 && (cl3 == GENERAL_REGS
1299 || ((ira_reg_class_intersect[cl1][cl2]
1300 != GENERAL_REGS)
1301 && hard_reg_set_subset_p
1302 (reg_class_contents[cl3],
1303 reg_class_contents
1304 [(int)
1305 ira_reg_class_intersect[cl1][cl2]])))))
1306 ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
1308 COPY_HARD_REG_SET
1309 (temp_set2,
1310 reg_class_contents[(int) ira_reg_class_subset[cl1][cl2]]);
1311 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1312 if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1313 /* Ignore unavailable hard registers and prefer
1314 smallest class for debugging purposes. */
1315 || (hard_reg_set_equal_p (temp_hard_regset, temp_set2)
1316 && hard_reg_set_subset_p
1317 (reg_class_contents[cl3],
1318 reg_class_contents
1319 [(int) ira_reg_class_subset[cl1][cl2]])))
1320 ira_reg_class_subset[cl1][cl2] = (enum reg_class) cl3;
1322 if (important_class_p[cl3]
1323 && hard_reg_set_subset_p (temp_hard_regset, union_set))
1325 /* CL3 allocatable hard register set is inside of
1326 union of allocatable hard register sets of CL1
1327 and CL2. */
1328 COPY_HARD_REG_SET
1329 (temp_set2,
1330 reg_class_contents[(int) ira_reg_class_subunion[cl1][cl2]]);
1331 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1332 if (ira_reg_class_subunion[cl1][cl2] == NO_REGS
1333 || (hard_reg_set_subset_p (temp_set2, temp_hard_regset)
1335 && (! hard_reg_set_equal_p (temp_set2,
1336 temp_hard_regset)
1337 || cl3 == GENERAL_REGS
1338 /* If the allocatable hard register sets are the
1339 same, prefer GENERAL_REGS or the smallest
1340 class for debugging purposes. */
1341 || (ira_reg_class_subunion[cl1][cl2] != GENERAL_REGS
1342 && hard_reg_set_subset_p
1343 (reg_class_contents[cl3],
1344 reg_class_contents
1345 [(int) ira_reg_class_subunion[cl1][cl2]])))))
1346 ira_reg_class_subunion[cl1][cl2] = (enum reg_class) cl3;
1348 if (hard_reg_set_subset_p (union_set, temp_hard_regset))
1350 /* CL3 allocatable hard register set contains union
1351 of allocatable hard register sets of CL1 and
1352 CL2. */
1353 COPY_HARD_REG_SET
1354 (temp_set2,
1355 reg_class_contents[(int) ira_reg_class_superunion[cl1][cl2]]);
1356 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1357 if (ira_reg_class_superunion[cl1][cl2] == NO_REGS
1358 || (hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1360 && (! hard_reg_set_equal_p (temp_set2,
1361 temp_hard_regset)
1362 || cl3 == GENERAL_REGS
1363 /* If the allocatable hard register sets are the
1364 same, prefer GENERAL_REGS or the smallest
1365 class for debugging purposes. */
1366 || (ira_reg_class_superunion[cl1][cl2] != GENERAL_REGS
1367 && hard_reg_set_subset_p
1368 (reg_class_contents[cl3],
1369 reg_class_contents
1370 [(int) ira_reg_class_superunion[cl1][cl2]])))))
1371 ira_reg_class_superunion[cl1][cl2] = (enum reg_class) cl3;
1378 /* Output all uniform and important classes into file F. */
1379 static void
1380 print_unform_and_important_classes (FILE *f)
1382 static const char *const reg_class_names[] = REG_CLASS_NAMES;
1383 int i, cl;
1385 fprintf (f, "Uniform classes:\n");
1386 for (cl = 0; cl < N_REG_CLASSES; cl++)
1387 if (ira_uniform_class_p[cl])
1388 fprintf (f, " %s", reg_class_names[cl]);
1389 fprintf (f, "\nImportant classes:\n");
1390 for (i = 0; i < ira_important_classes_num; i++)
1391 fprintf (f, " %s", reg_class_names[ira_important_classes[i]]);
1392 fprintf (f, "\n");
1395 /* Output all possible allocno or pressure classes and their
1396 translation map into file F. */
1397 static void
1398 print_translated_classes (FILE *f, bool pressure_p)
1400 int classes_num = (pressure_p
1401 ? ira_pressure_classes_num : ira_allocno_classes_num);
1402 enum reg_class *classes = (pressure_p
1403 ? ira_pressure_classes : ira_allocno_classes);
1404 enum reg_class *class_translate = (pressure_p
1405 ? ira_pressure_class_translate
1406 : ira_allocno_class_translate);
1407 static const char *const reg_class_names[] = REG_CLASS_NAMES;
1408 int i;
1410 fprintf (f, "%s classes:\n", pressure_p ? "Pressure" : "Allocno");
1411 for (i = 0; i < classes_num; i++)
1412 fprintf (f, " %s", reg_class_names[classes[i]]);
1413 fprintf (f, "\nClass translation:\n");
1414 for (i = 0; i < N_REG_CLASSES; i++)
1415 fprintf (f, " %s -> %s\n", reg_class_names[i],
1416 reg_class_names[class_translate[i]]);
1419 /* Output all possible allocno and translation classes and the
1420 translation maps into stderr. */
1421 void
1422 ira_debug_allocno_classes (void)
1424 print_unform_and_important_classes (stderr);
1425 print_translated_classes (stderr, false);
1426 print_translated_classes (stderr, true);
1429 /* Set up different arrays concerning class subsets, allocno and
1430 important classes. */
1431 static void
1432 find_reg_classes (void)
1434 setup_allocno_and_important_classes ();
1435 setup_class_translate ();
1436 reorder_important_classes ();
1437 setup_reg_class_relations ();
1442 /* Set up the array above. */
1443 static void
1444 setup_hard_regno_aclass (void)
1446 int i;
1448 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1450 #if 1
1451 ira_hard_regno_allocno_class[i]
1452 = (TEST_HARD_REG_BIT (no_unit_alloc_regs, i)
1453 ? NO_REGS
1454 : ira_allocno_class_translate[REGNO_REG_CLASS (i)]);
1455 #else
1456 int j;
1457 enum reg_class cl;
1458 ira_hard_regno_allocno_class[i] = NO_REGS;
1459 for (j = 0; j < ira_allocno_classes_num; j++)
1461 cl = ira_allocno_classes[j];
1462 if (ira_class_hard_reg_index[cl][i] >= 0)
1464 ira_hard_regno_allocno_class[i] = cl;
1465 break;
1468 #endif
1474 /* Form IRA_REG_CLASS_MAX_NREGS and IRA_REG_CLASS_MIN_NREGS maps. */
1475 static void
1476 setup_reg_class_nregs (void)
1478 int i, cl, cl2, m;
1480 for (m = 0; m < MAX_MACHINE_MODE; m++)
1482 for (cl = 0; cl < N_REG_CLASSES; cl++)
1483 ira_reg_class_max_nregs[cl][m]
1484 = ira_reg_class_min_nregs[cl][m]
1485 = targetm.class_max_nregs ((reg_class_t) cl, (machine_mode) m);
1486 for (cl = 0; cl < N_REG_CLASSES; cl++)
1487 for (i = 0;
1488 (cl2 = alloc_reg_class_subclasses[cl][i]) != LIM_REG_CLASSES;
1489 i++)
1490 if (ira_reg_class_min_nregs[cl2][m]
1491 < ira_reg_class_min_nregs[cl][m])
1492 ira_reg_class_min_nregs[cl][m] = ira_reg_class_min_nregs[cl2][m];
1498 /* Set up IRA_PROHIBITED_CLASS_MODE_REGS and IRA_CLASS_SINGLETON.
1499 This function is called once IRA_CLASS_HARD_REGS has been initialized. */
1500 static void
1501 setup_prohibited_class_mode_regs (void)
1503 int j, k, hard_regno, cl, last_hard_regno, count;
1505 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
1507 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
1508 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1509 for (j = 0; j < NUM_MACHINE_MODES; j++)
1511 count = 0;
1512 last_hard_regno = -1;
1513 CLEAR_HARD_REG_SET (ira_prohibited_class_mode_regs[cl][j]);
1514 for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1516 hard_regno = ira_class_hard_regs[cl][k];
1517 if (! HARD_REGNO_MODE_OK (hard_regno, (machine_mode) j))
1518 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1519 hard_regno);
1520 else if (in_hard_reg_set_p (temp_hard_regset,
1521 (machine_mode) j, hard_regno))
1523 last_hard_regno = hard_regno;
1524 count++;
1527 ira_class_singleton[cl][j] = (count == 1 ? last_hard_regno : -1);
1532 /* Clarify IRA_PROHIBITED_CLASS_MODE_REGS by excluding hard registers
1533 spanning from one register pressure class to another one. It is
1534 called after defining the pressure classes. */
1535 static void
1536 clarify_prohibited_class_mode_regs (void)
1538 int j, k, hard_regno, cl, pclass, nregs;
1540 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
1541 for (j = 0; j < NUM_MACHINE_MODES; j++)
1543 CLEAR_HARD_REG_SET (ira_useful_class_mode_regs[cl][j]);
1544 for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1546 hard_regno = ira_class_hard_regs[cl][k];
1547 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j], hard_regno))
1548 continue;
1549 nregs = hard_regno_nregs[hard_regno][j];
1550 if (hard_regno + nregs > FIRST_PSEUDO_REGISTER)
1552 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1553 hard_regno);
1554 continue;
1556 pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)];
1557 for (nregs-- ;nregs >= 0; nregs--)
1558 if (((enum reg_class) pclass
1559 != ira_pressure_class_translate[REGNO_REG_CLASS
1560 (hard_regno + nregs)]))
1562 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1563 hard_regno);
1564 break;
1566 if (!TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1567 hard_regno))
1568 add_to_hard_reg_set (&ira_useful_class_mode_regs[cl][j],
1569 (machine_mode) j, hard_regno);
1574 /* Allocate and initialize IRA_REGISTER_MOVE_COST, IRA_MAY_MOVE_IN_COST
1575 and IRA_MAY_MOVE_OUT_COST for MODE. */
1576 void
1577 ira_init_register_move_cost (machine_mode mode)
1579 static unsigned short last_move_cost[N_REG_CLASSES][N_REG_CLASSES];
1580 bool all_match = true;
1581 unsigned int cl1, cl2;
1583 ira_assert (ira_register_move_cost[mode] == NULL
1584 && ira_may_move_in_cost[mode] == NULL
1585 && ira_may_move_out_cost[mode] == NULL);
1586 ira_assert (have_regs_of_mode[mode]);
1587 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1588 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1590 int cost;
1591 if (!contains_reg_of_mode[cl1][mode]
1592 || !contains_reg_of_mode[cl2][mode])
1594 if ((ira_reg_class_max_nregs[cl1][mode]
1595 > ira_class_hard_regs_num[cl1])
1596 || (ira_reg_class_max_nregs[cl2][mode]
1597 > ira_class_hard_regs_num[cl2]))
1598 cost = 65535;
1599 else
1600 cost = (ira_memory_move_cost[mode][cl1][0]
1601 + ira_memory_move_cost[mode][cl2][1]) * 2;
1603 else
1605 cost = register_move_cost (mode, (enum reg_class) cl1,
1606 (enum reg_class) cl2);
1607 ira_assert (cost < 65535);
1609 all_match &= (last_move_cost[cl1][cl2] == cost);
1610 last_move_cost[cl1][cl2] = cost;
1612 if (all_match && last_mode_for_init_move_cost != -1)
1614 ira_register_move_cost[mode]
1615 = ira_register_move_cost[last_mode_for_init_move_cost];
1616 ira_may_move_in_cost[mode]
1617 = ira_may_move_in_cost[last_mode_for_init_move_cost];
1618 ira_may_move_out_cost[mode]
1619 = ira_may_move_out_cost[last_mode_for_init_move_cost];
1620 return;
1622 last_mode_for_init_move_cost = mode;
1623 ira_register_move_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1624 ira_may_move_in_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1625 ira_may_move_out_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1626 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1627 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1629 int cost;
1630 enum reg_class *p1, *p2;
1632 if (last_move_cost[cl1][cl2] == 65535)
1634 ira_register_move_cost[mode][cl1][cl2] = 65535;
1635 ira_may_move_in_cost[mode][cl1][cl2] = 65535;
1636 ira_may_move_out_cost[mode][cl1][cl2] = 65535;
1638 else
1640 cost = last_move_cost[cl1][cl2];
1642 for (p2 = &reg_class_subclasses[cl2][0];
1643 *p2 != LIM_REG_CLASSES; p2++)
1644 if (ira_class_hard_regs_num[*p2] > 0
1645 && (ira_reg_class_max_nregs[*p2][mode]
1646 <= ira_class_hard_regs_num[*p2]))
1647 cost = MAX (cost, ira_register_move_cost[mode][cl1][*p2]);
1649 for (p1 = &reg_class_subclasses[cl1][0];
1650 *p1 != LIM_REG_CLASSES; p1++)
1651 if (ira_class_hard_regs_num[*p1] > 0
1652 && (ira_reg_class_max_nregs[*p1][mode]
1653 <= ira_class_hard_regs_num[*p1]))
1654 cost = MAX (cost, ira_register_move_cost[mode][*p1][cl2]);
1656 ira_assert (cost <= 65535);
1657 ira_register_move_cost[mode][cl1][cl2] = cost;
1659 if (ira_class_subset_p[cl1][cl2])
1660 ira_may_move_in_cost[mode][cl1][cl2] = 0;
1661 else
1662 ira_may_move_in_cost[mode][cl1][cl2] = cost;
1664 if (ira_class_subset_p[cl2][cl1])
1665 ira_may_move_out_cost[mode][cl1][cl2] = 0;
1666 else
1667 ira_may_move_out_cost[mode][cl1][cl2] = cost;
1674 /* This is called once during compiler work. It sets up
1675 different arrays whose values don't depend on the compiled
1676 function. */
1677 void
1678 ira_init_once (void)
1680 ira_init_costs_once ();
1681 lra_init_once ();
1684 /* Free ira_max_register_move_cost, ira_may_move_in_cost and
1685 ira_may_move_out_cost for each mode. */
1686 void
1687 target_ira_int::free_register_move_costs (void)
1689 int mode, i;
1691 /* Reset move_cost and friends, making sure we only free shared
1692 table entries once. */
1693 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1694 if (x_ira_register_move_cost[mode])
1696 for (i = 0;
1697 i < mode && (x_ira_register_move_cost[i]
1698 != x_ira_register_move_cost[mode]);
1699 i++)
1701 if (i == mode)
1703 free (x_ira_register_move_cost[mode]);
1704 free (x_ira_may_move_in_cost[mode]);
1705 free (x_ira_may_move_out_cost[mode]);
1708 memset (x_ira_register_move_cost, 0, sizeof x_ira_register_move_cost);
1709 memset (x_ira_may_move_in_cost, 0, sizeof x_ira_may_move_in_cost);
1710 memset (x_ira_may_move_out_cost, 0, sizeof x_ira_may_move_out_cost);
1711 last_mode_for_init_move_cost = -1;
1714 target_ira_int::~target_ira_int ()
1716 free_ira_costs ();
1717 free_register_move_costs ();
1720 /* This is called every time when register related information is
1721 changed. */
1722 void
1723 ira_init (void)
1725 this_target_ira_int->free_register_move_costs ();
1726 setup_reg_mode_hard_regset ();
1727 setup_alloc_regs (flag_omit_frame_pointer != 0);
1728 setup_class_subset_and_memory_move_costs ();
1729 setup_reg_class_nregs ();
1730 setup_prohibited_class_mode_regs ();
1731 find_reg_classes ();
1732 clarify_prohibited_class_mode_regs ();
1733 setup_hard_regno_aclass ();
1734 ira_init_costs ();
1738 #define ira_prohibited_mode_move_regs_initialized_p \
1739 (this_target_ira_int->x_ira_prohibited_mode_move_regs_initialized_p)
1741 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS. */
1742 static void
1743 setup_prohibited_mode_move_regs (void)
1745 int i, j;
1746 rtx test_reg1, test_reg2, move_pat;
1747 rtx_insn *move_insn;
1749 if (ira_prohibited_mode_move_regs_initialized_p)
1750 return;
1751 ira_prohibited_mode_move_regs_initialized_p = true;
1752 test_reg1 = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
1753 test_reg2 = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 2);
1754 move_pat = gen_rtx_SET (test_reg1, test_reg2);
1755 move_insn = gen_rtx_INSN (VOIDmode, 0, 0, 0, move_pat, 0, -1, 0);
1756 for (i = 0; i < NUM_MACHINE_MODES; i++)
1758 SET_HARD_REG_SET (ira_prohibited_mode_move_regs[i]);
1759 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1761 if (! HARD_REGNO_MODE_OK (j, (machine_mode) i))
1762 continue;
1763 set_mode_and_regno (test_reg1, (machine_mode) i, j);
1764 set_mode_and_regno (test_reg2, (machine_mode) i, j);
1765 INSN_CODE (move_insn) = -1;
1766 recog_memoized (move_insn);
1767 if (INSN_CODE (move_insn) < 0)
1768 continue;
1769 extract_insn (move_insn);
1770 /* We don't know whether the move will be in code that is optimized
1771 for size or speed, so consider all enabled alternatives. */
1772 if (! constrain_operands (1, get_enabled_alternatives (move_insn)))
1773 continue;
1774 CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs[i], j);
1781 /* Setup possible alternatives in ALTS for INSN. */
1782 void
1783 ira_setup_alts (rtx_insn *insn, HARD_REG_SET &alts)
1785 /* MAP nalt * nop -> start of constraints for given operand and
1786 alternative. */
1787 static vec<const char *> insn_constraints;
1788 int nop, nalt;
1789 bool curr_swapped;
1790 const char *p;
1791 int commutative = -1;
1793 extract_insn (insn);
1794 alternative_mask preferred = get_preferred_alternatives (insn);
1795 CLEAR_HARD_REG_SET (alts);
1796 insn_constraints.release ();
1797 insn_constraints.safe_grow_cleared (recog_data.n_operands
1798 * recog_data.n_alternatives + 1);
1799 /* Check that the hard reg set is enough for holding all
1800 alternatives. It is hard to imagine the situation when the
1801 assertion is wrong. */
1802 ira_assert (recog_data.n_alternatives
1803 <= (int) MAX (sizeof (HARD_REG_ELT_TYPE) * CHAR_BIT,
1804 FIRST_PSEUDO_REGISTER));
1805 for (curr_swapped = false;; curr_swapped = true)
1807 /* Calculate some data common for all alternatives to speed up the
1808 function. */
1809 for (nop = 0; nop < recog_data.n_operands; nop++)
1811 for (nalt = 0, p = recog_data.constraints[nop];
1812 nalt < recog_data.n_alternatives;
1813 nalt++)
1815 insn_constraints[nop * recog_data.n_alternatives + nalt] = p;
1816 while (*p && *p != ',')
1817 p++;
1818 if (*p)
1819 p++;
1822 for (nalt = 0; nalt < recog_data.n_alternatives; nalt++)
1824 if (!TEST_BIT (preferred, nalt)
1825 || TEST_HARD_REG_BIT (alts, nalt))
1826 continue;
1828 for (nop = 0; nop < recog_data.n_operands; nop++)
1830 int c, len;
1832 rtx op = recog_data.operand[nop];
1833 p = insn_constraints[nop * recog_data.n_alternatives + nalt];
1834 if (*p == 0 || *p == ',')
1835 continue;
1838 switch (c = *p, len = CONSTRAINT_LEN (c, p), c)
1840 case '#':
1841 case ',':
1842 c = '\0';
1843 case '\0':
1844 len = 0;
1845 break;
1847 case '%':
1848 /* We only support one commutative marker, the
1849 first one. We already set commutative
1850 above. */
1851 if (commutative < 0)
1852 commutative = nop;
1853 break;
1855 case '0': case '1': case '2': case '3': case '4':
1856 case '5': case '6': case '7': case '8': case '9':
1857 goto op_success;
1858 break;
1860 case 'g':
1861 goto op_success;
1862 break;
1864 default:
1866 enum constraint_num cn = lookup_constraint (p);
1867 switch (get_constraint_type (cn))
1869 case CT_REGISTER:
1870 if (reg_class_for_constraint (cn) != NO_REGS)
1871 goto op_success;
1872 break;
1874 case CT_CONST_INT:
1875 if (CONST_INT_P (op)
1876 && (insn_const_int_ok_for_constraint
1877 (INTVAL (op), cn)))
1878 goto op_success;
1879 break;
1881 case CT_ADDRESS:
1882 case CT_MEMORY:
1883 goto op_success;
1885 case CT_FIXED_FORM:
1886 if (constraint_satisfied_p (op, cn))
1887 goto op_success;
1888 break;
1890 break;
1893 while (p += len, c);
1894 break;
1895 op_success:
1898 if (nop >= recog_data.n_operands)
1899 SET_HARD_REG_BIT (alts, nalt);
1901 if (commutative < 0)
1902 break;
1903 if (curr_swapped)
1904 break;
1905 std::swap (recog_data.operand[commutative],
1906 recog_data.operand[commutative + 1]);
1910 /* Return the number of the output non-early clobber operand which
1911 should be the same in any case as operand with number OP_NUM (or
1912 negative value if there is no such operand). The function takes
1913 only really possible alternatives into consideration. */
1915 ira_get_dup_out_num (int op_num, HARD_REG_SET &alts)
1917 int curr_alt, c, original, dup;
1918 bool ignore_p, use_commut_op_p;
1919 const char *str;
1921 if (op_num < 0 || recog_data.n_alternatives == 0)
1922 return -1;
1923 /* We should find duplications only for input operands. */
1924 if (recog_data.operand_type[op_num] != OP_IN)
1925 return -1;
1926 str = recog_data.constraints[op_num];
1927 use_commut_op_p = false;
1928 for (;;)
1930 rtx op = recog_data.operand[op_num];
1932 for (curr_alt = 0, ignore_p = !TEST_HARD_REG_BIT (alts, curr_alt),
1933 original = -1;;)
1935 c = *str;
1936 if (c == '\0')
1937 break;
1938 if (c == '#')
1939 ignore_p = true;
1940 else if (c == ',')
1942 curr_alt++;
1943 ignore_p = !TEST_HARD_REG_BIT (alts, curr_alt);
1945 else if (! ignore_p)
1946 switch (c)
1948 case 'g':
1949 goto fail;
1950 default:
1952 enum constraint_num cn = lookup_constraint (str);
1953 enum reg_class cl = reg_class_for_constraint (cn);
1954 if (cl != NO_REGS
1955 && !targetm.class_likely_spilled_p (cl))
1956 goto fail;
1957 if (constraint_satisfied_p (op, cn))
1958 goto fail;
1959 break;
1962 case '0': case '1': case '2': case '3': case '4':
1963 case '5': case '6': case '7': case '8': case '9':
1964 if (original != -1 && original != c)
1965 goto fail;
1966 original = c;
1967 break;
1969 str += CONSTRAINT_LEN (c, str);
1971 if (original == -1)
1972 goto fail;
1973 dup = -1;
1974 for (ignore_p = false, str = recog_data.constraints[original - '0'];
1975 *str != 0;
1976 str++)
1977 if (ignore_p)
1979 if (*str == ',')
1980 ignore_p = false;
1982 else if (*str == '#')
1983 ignore_p = true;
1984 else if (! ignore_p)
1986 if (*str == '=')
1987 dup = original - '0';
1988 /* It is better ignore an alternative with early clobber. */
1989 else if (*str == '&')
1990 goto fail;
1992 if (dup >= 0)
1993 return dup;
1994 fail:
1995 if (use_commut_op_p)
1996 break;
1997 use_commut_op_p = true;
1998 if (recog_data.constraints[op_num][0] == '%')
1999 str = recog_data.constraints[op_num + 1];
2000 else if (op_num > 0 && recog_data.constraints[op_num - 1][0] == '%')
2001 str = recog_data.constraints[op_num - 1];
2002 else
2003 break;
2005 return -1;
2010 /* Search forward to see if the source register of a copy insn dies
2011 before either it or the destination register is modified, but don't
2012 scan past the end of the basic block. If so, we can replace the
2013 source with the destination and let the source die in the copy
2014 insn.
2016 This will reduce the number of registers live in that range and may
2017 enable the destination and the source coalescing, thus often saving
2018 one register in addition to a register-register copy. */
2020 static void
2021 decrease_live_ranges_number (void)
2023 basic_block bb;
2024 rtx_insn *insn;
2025 rtx set, src, dest, dest_death, note;
2026 rtx_insn *p, *q;
2027 int sregno, dregno;
2029 if (! flag_expensive_optimizations)
2030 return;
2032 if (ira_dump_file)
2033 fprintf (ira_dump_file, "Starting decreasing number of live ranges...\n");
2035 FOR_EACH_BB_FN (bb, cfun)
2036 FOR_BB_INSNS (bb, insn)
2038 set = single_set (insn);
2039 if (! set)
2040 continue;
2041 src = SET_SRC (set);
2042 dest = SET_DEST (set);
2043 if (! REG_P (src) || ! REG_P (dest)
2044 || find_reg_note (insn, REG_DEAD, src))
2045 continue;
2046 sregno = REGNO (src);
2047 dregno = REGNO (dest);
2049 /* We don't want to mess with hard regs if register classes
2050 are small. */
2051 if (sregno == dregno
2052 || (targetm.small_register_classes_for_mode_p (GET_MODE (src))
2053 && (sregno < FIRST_PSEUDO_REGISTER
2054 || dregno < FIRST_PSEUDO_REGISTER))
2055 /* We don't see all updates to SP if they are in an
2056 auto-inc memory reference, so we must disallow this
2057 optimization on them. */
2058 || sregno == STACK_POINTER_REGNUM
2059 || dregno == STACK_POINTER_REGNUM)
2060 continue;
2062 dest_death = NULL_RTX;
2064 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
2066 if (! INSN_P (p))
2067 continue;
2068 if (BLOCK_FOR_INSN (p) != bb)
2069 break;
2071 if (reg_set_p (src, p) || reg_set_p (dest, p)
2072 /* If SRC is an asm-declared register, it must not be
2073 replaced in any asm. Unfortunately, the REG_EXPR
2074 tree for the asm variable may be absent in the SRC
2075 rtx, so we can't check the actual register
2076 declaration easily (the asm operand will have it,
2077 though). To avoid complicating the test for a rare
2078 case, we just don't perform register replacement
2079 for a hard reg mentioned in an asm. */
2080 || (sregno < FIRST_PSEUDO_REGISTER
2081 && asm_noperands (PATTERN (p)) >= 0
2082 && reg_overlap_mentioned_p (src, PATTERN (p)))
2083 /* Don't change hard registers used by a call. */
2084 || (CALL_P (p) && sregno < FIRST_PSEUDO_REGISTER
2085 && find_reg_fusage (p, USE, src))
2086 /* Don't change a USE of a register. */
2087 || (GET_CODE (PATTERN (p)) == USE
2088 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
2089 break;
2091 /* See if all of SRC dies in P. This test is slightly
2092 more conservative than it needs to be. */
2093 if ((note = find_regno_note (p, REG_DEAD, sregno))
2094 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
2096 int failed = 0;
2098 /* We can do the optimization. Scan forward from INSN
2099 again, replacing regs as we go. Set FAILED if a
2100 replacement can't be done. In that case, we can't
2101 move the death note for SRC. This should be
2102 rare. */
2104 /* Set to stop at next insn. */
2105 for (q = next_real_insn (insn);
2106 q != next_real_insn (p);
2107 q = next_real_insn (q))
2109 if (reg_overlap_mentioned_p (src, PATTERN (q)))
2111 /* If SRC is a hard register, we might miss
2112 some overlapping registers with
2113 validate_replace_rtx, so we would have to
2114 undo it. We can't if DEST is present in
2115 the insn, so fail in that combination of
2116 cases. */
2117 if (sregno < FIRST_PSEUDO_REGISTER
2118 && reg_mentioned_p (dest, PATTERN (q)))
2119 failed = 1;
2121 /* Attempt to replace all uses. */
2122 else if (!validate_replace_rtx (src, dest, q))
2123 failed = 1;
2125 /* If this succeeded, but some part of the
2126 register is still present, undo the
2127 replacement. */
2128 else if (sregno < FIRST_PSEUDO_REGISTER
2129 && reg_overlap_mentioned_p (src, PATTERN (q)))
2131 validate_replace_rtx (dest, src, q);
2132 failed = 1;
2136 /* If DEST dies here, remove the death note and
2137 save it for later. Make sure ALL of DEST dies
2138 here; again, this is overly conservative. */
2139 if (! dest_death
2140 && (dest_death = find_regno_note (q, REG_DEAD, dregno)))
2142 if (GET_MODE (XEXP (dest_death, 0)) == GET_MODE (dest))
2143 remove_note (q, dest_death);
2144 else
2146 failed = 1;
2147 dest_death = 0;
2152 if (! failed)
2154 /* Move death note of SRC from P to INSN. */
2155 remove_note (p, note);
2156 XEXP (note, 1) = REG_NOTES (insn);
2157 REG_NOTES (insn) = note;
2160 /* DEST is also dead if INSN has a REG_UNUSED note for
2161 DEST. */
2162 if (! dest_death
2163 && (dest_death
2164 = find_regno_note (insn, REG_UNUSED, dregno)))
2166 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
2167 remove_note (insn, dest_death);
2170 /* Put death note of DEST on P if we saw it die. */
2171 if (dest_death)
2173 XEXP (dest_death, 1) = REG_NOTES (p);
2174 REG_NOTES (p) = dest_death;
2176 break;
2179 /* If SRC is a hard register which is set or killed in
2180 some other way, we can't do this optimization. */
2181 else if (sregno < FIRST_PSEUDO_REGISTER && dead_or_set_p (p, src))
2182 break;
2189 /* Return nonzero if REGNO is a particularly bad choice for reloading X. */
2190 static bool
2191 ira_bad_reload_regno_1 (int regno, rtx x)
2193 int x_regno, n, i;
2194 ira_allocno_t a;
2195 enum reg_class pref;
2197 /* We only deal with pseudo regs. */
2198 if (! x || GET_CODE (x) != REG)
2199 return false;
2201 x_regno = REGNO (x);
2202 if (x_regno < FIRST_PSEUDO_REGISTER)
2203 return false;
2205 /* If the pseudo prefers REGNO explicitly, then do not consider
2206 REGNO a bad spill choice. */
2207 pref = reg_preferred_class (x_regno);
2208 if (reg_class_size[pref] == 1)
2209 return !TEST_HARD_REG_BIT (reg_class_contents[pref], regno);
2211 /* If the pseudo conflicts with REGNO, then we consider REGNO a
2212 poor choice for a reload regno. */
2213 a = ira_regno_allocno_map[x_regno];
2214 n = ALLOCNO_NUM_OBJECTS (a);
2215 for (i = 0; i < n; i++)
2217 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2218 if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), regno))
2219 return true;
2221 return false;
2224 /* Return nonzero if REGNO is a particularly bad choice for reloading
2225 IN or OUT. */
2226 bool
2227 ira_bad_reload_regno (int regno, rtx in, rtx out)
2229 return (ira_bad_reload_regno_1 (regno, in)
2230 || ira_bad_reload_regno_1 (regno, out));
2233 /* Add register clobbers from asm statements. */
2234 static void
2235 compute_regs_asm_clobbered (void)
2237 basic_block bb;
2239 FOR_EACH_BB_FN (bb, cfun)
2241 rtx_insn *insn;
2242 FOR_BB_INSNS_REVERSE (bb, insn)
2244 df_ref def;
2246 if (NONDEBUG_INSN_P (insn) && extract_asm_operands (PATTERN (insn)))
2247 FOR_EACH_INSN_DEF (def, insn)
2249 unsigned int dregno = DF_REF_REGNO (def);
2250 if (HARD_REGISTER_NUM_P (dregno))
2251 add_to_hard_reg_set (&crtl->asm_clobbers,
2252 GET_MODE (DF_REF_REAL_REG (def)),
2253 dregno);
2260 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and
2261 REGS_EVER_LIVE. */
2262 void
2263 ira_setup_eliminable_regset (void)
2265 #ifdef ELIMINABLE_REGS
2266 int i;
2267 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
2268 #endif
2269 /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
2270 sp for alloca. So we can't eliminate the frame pointer in that
2271 case. At some point, we should improve this by emitting the
2272 sp-adjusting insns for this case. */
2273 frame_pointer_needed
2274 = (! flag_omit_frame_pointer
2275 || (cfun->calls_alloca && EXIT_IGNORE_STACK)
2276 /* We need the frame pointer to catch stack overflow exceptions
2277 if the stack pointer is moving. */
2278 || (flag_stack_check && STACK_CHECK_MOVING_SP)
2279 || crtl->accesses_prior_frames
2280 || (SUPPORTS_STACK_ALIGNMENT && crtl->stack_realign_needed)
2281 /* We need a frame pointer for all Cilk Plus functions that use
2282 Cilk keywords. */
2283 || (flag_cilkplus && cfun->is_cilk_function)
2284 || targetm.frame_pointer_required ());
2286 /* The chance that FRAME_POINTER_NEEDED is changed from inspecting
2287 RTL is very small. So if we use frame pointer for RA and RTL
2288 actually prevents this, we will spill pseudos assigned to the
2289 frame pointer in LRA. */
2291 if (frame_pointer_needed)
2292 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
2294 COPY_HARD_REG_SET (ira_no_alloc_regs, no_unit_alloc_regs);
2295 CLEAR_HARD_REG_SET (eliminable_regset);
2297 compute_regs_asm_clobbered ();
2299 /* Build the regset of all eliminable registers and show we can't
2300 use those that we already know won't be eliminated. */
2301 #ifdef ELIMINABLE_REGS
2302 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
2304 bool cannot_elim
2305 = (! targetm.can_eliminate (eliminables[i].from, eliminables[i].to)
2306 || (eliminables[i].to == STACK_POINTER_REGNUM && frame_pointer_needed));
2308 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, eliminables[i].from))
2310 SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
2312 if (cannot_elim)
2313 SET_HARD_REG_BIT (ira_no_alloc_regs, eliminables[i].from);
2315 else if (cannot_elim)
2316 error ("%s cannot be used in asm here",
2317 reg_names[eliminables[i].from]);
2318 else
2319 df_set_regs_ever_live (eliminables[i].from, true);
2321 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
2323 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM))
2325 SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
2326 if (frame_pointer_needed)
2327 SET_HARD_REG_BIT (ira_no_alloc_regs, HARD_FRAME_POINTER_REGNUM);
2329 else if (frame_pointer_needed)
2330 error ("%s cannot be used in asm here",
2331 reg_names[HARD_FRAME_POINTER_REGNUM]);
2332 else
2333 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
2336 #else
2337 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM))
2339 SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
2340 if (frame_pointer_needed)
2341 SET_HARD_REG_BIT (ira_no_alloc_regs, FRAME_POINTER_REGNUM);
2343 else if (frame_pointer_needed)
2344 error ("%s cannot be used in asm here", reg_names[FRAME_POINTER_REGNUM]);
2345 else
2346 df_set_regs_ever_live (FRAME_POINTER_REGNUM, true);
2347 #endif
2352 /* Vector of substitutions of register numbers,
2353 used to map pseudo regs into hardware regs.
2354 This is set up as a result of register allocation.
2355 Element N is the hard reg assigned to pseudo reg N,
2356 or is -1 if no hard reg was assigned.
2357 If N is a hard reg number, element N is N. */
2358 short *reg_renumber;
2360 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
2361 the allocation found by IRA. */
2362 static void
2363 setup_reg_renumber (void)
2365 int regno, hard_regno;
2366 ira_allocno_t a;
2367 ira_allocno_iterator ai;
2369 caller_save_needed = 0;
2370 FOR_EACH_ALLOCNO (a, ai)
2372 if (ira_use_lra_p && ALLOCNO_CAP_MEMBER (a) != NULL)
2373 continue;
2374 /* There are no caps at this point. */
2375 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2376 if (! ALLOCNO_ASSIGNED_P (a))
2377 /* It can happen if A is not referenced but partially anticipated
2378 somewhere in a region. */
2379 ALLOCNO_ASSIGNED_P (a) = true;
2380 ira_free_allocno_updated_costs (a);
2381 hard_regno = ALLOCNO_HARD_REGNO (a);
2382 regno = ALLOCNO_REGNO (a);
2383 reg_renumber[regno] = (hard_regno < 0 ? -1 : hard_regno);
2384 if (hard_regno >= 0)
2386 int i, nwords;
2387 enum reg_class pclass;
2388 ira_object_t obj;
2390 pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)];
2391 nwords = ALLOCNO_NUM_OBJECTS (a);
2392 for (i = 0; i < nwords; i++)
2394 obj = ALLOCNO_OBJECT (a, i);
2395 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
2396 reg_class_contents[pclass]);
2398 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
2399 && ira_hard_reg_set_intersection_p (hard_regno, ALLOCNO_MODE (a),
2400 call_used_reg_set))
2402 ira_assert (!optimize || flag_caller_saves
2403 || (ALLOCNO_CALLS_CROSSED_NUM (a)
2404 == ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a))
2405 || regno >= ira_reg_equiv_len
2406 || ira_equiv_no_lvalue_p (regno));
2407 caller_save_needed = 1;
2413 /* Set up allocno assignment flags for further allocation
2414 improvements. */
2415 static void
2416 setup_allocno_assignment_flags (void)
2418 int hard_regno;
2419 ira_allocno_t a;
2420 ira_allocno_iterator ai;
2422 FOR_EACH_ALLOCNO (a, ai)
2424 if (! ALLOCNO_ASSIGNED_P (a))
2425 /* It can happen if A is not referenced but partially anticipated
2426 somewhere in a region. */
2427 ira_free_allocno_updated_costs (a);
2428 hard_regno = ALLOCNO_HARD_REGNO (a);
2429 /* Don't assign hard registers to allocnos which are destination
2430 of removed store at the end of loop. It has no sense to keep
2431 the same value in different hard registers. It is also
2432 impossible to assign hard registers correctly to such
2433 allocnos because the cost info and info about intersected
2434 calls are incorrect for them. */
2435 ALLOCNO_ASSIGNED_P (a) = (hard_regno >= 0
2436 || ALLOCNO_EMIT_DATA (a)->mem_optimized_dest_p
2437 || (ALLOCNO_MEMORY_COST (a)
2438 - ALLOCNO_CLASS_COST (a)) < 0);
2439 ira_assert
2440 (hard_regno < 0
2441 || ira_hard_reg_in_set_p (hard_regno, ALLOCNO_MODE (a),
2442 reg_class_contents[ALLOCNO_CLASS (a)]));
2446 /* Evaluate overall allocation cost and the costs for using hard
2447 registers and memory for allocnos. */
2448 static void
2449 calculate_allocation_cost (void)
2451 int hard_regno, cost;
2452 ira_allocno_t a;
2453 ira_allocno_iterator ai;
2455 ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
2456 FOR_EACH_ALLOCNO (a, ai)
2458 hard_regno = ALLOCNO_HARD_REGNO (a);
2459 ira_assert (hard_regno < 0
2460 || (ira_hard_reg_in_set_p
2461 (hard_regno, ALLOCNO_MODE (a),
2462 reg_class_contents[ALLOCNO_CLASS (a)])));
2463 if (hard_regno < 0)
2465 cost = ALLOCNO_MEMORY_COST (a);
2466 ira_mem_cost += cost;
2468 else if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
2470 cost = (ALLOCNO_HARD_REG_COSTS (a)
2471 [ira_class_hard_reg_index
2472 [ALLOCNO_CLASS (a)][hard_regno]]);
2473 ira_reg_cost += cost;
2475 else
2477 cost = ALLOCNO_CLASS_COST (a);
2478 ira_reg_cost += cost;
2480 ira_overall_cost += cost;
2483 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2485 fprintf (ira_dump_file,
2486 "+++Costs: overall %" PRId64
2487 ", reg %" PRId64
2488 ", mem %" PRId64
2489 ", ld %" PRId64
2490 ", st %" PRId64
2491 ", move %" PRId64,
2492 ira_overall_cost, ira_reg_cost, ira_mem_cost,
2493 ira_load_cost, ira_store_cost, ira_shuffle_cost);
2494 fprintf (ira_dump_file, "\n+++ move loops %d, new jumps %d\n",
2495 ira_move_loops_num, ira_additional_jumps_num);
2500 #ifdef ENABLE_IRA_CHECKING
2501 /* Check the correctness of the allocation. We do need this because
2502 of complicated code to transform more one region internal
2503 representation into one region representation. */
2504 static void
2505 check_allocation (void)
2507 ira_allocno_t a;
2508 int hard_regno, nregs, conflict_nregs;
2509 ira_allocno_iterator ai;
2511 FOR_EACH_ALLOCNO (a, ai)
2513 int n = ALLOCNO_NUM_OBJECTS (a);
2514 int i;
2516 if (ALLOCNO_CAP_MEMBER (a) != NULL
2517 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
2518 continue;
2519 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
2520 if (nregs == 1)
2521 /* We allocated a single hard register. */
2522 n = 1;
2523 else if (n > 1)
2524 /* We allocated multiple hard registers, and we will test
2525 conflicts in a granularity of single hard regs. */
2526 nregs = 1;
2528 for (i = 0; i < n; i++)
2530 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2531 ira_object_t conflict_obj;
2532 ira_object_conflict_iterator oci;
2533 int this_regno = hard_regno;
2534 if (n > 1)
2536 if (REG_WORDS_BIG_ENDIAN)
2537 this_regno += n - i - 1;
2538 else
2539 this_regno += i;
2541 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2543 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2544 int conflict_hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
2545 if (conflict_hard_regno < 0)
2546 continue;
2548 conflict_nregs
2549 = (hard_regno_nregs
2550 [conflict_hard_regno][ALLOCNO_MODE (conflict_a)]);
2552 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1
2553 && conflict_nregs == ALLOCNO_NUM_OBJECTS (conflict_a))
2555 if (REG_WORDS_BIG_ENDIAN)
2556 conflict_hard_regno += (ALLOCNO_NUM_OBJECTS (conflict_a)
2557 - OBJECT_SUBWORD (conflict_obj) - 1);
2558 else
2559 conflict_hard_regno += OBJECT_SUBWORD (conflict_obj);
2560 conflict_nregs = 1;
2563 if ((conflict_hard_regno <= this_regno
2564 && this_regno < conflict_hard_regno + conflict_nregs)
2565 || (this_regno <= conflict_hard_regno
2566 && conflict_hard_regno < this_regno + nregs))
2568 fprintf (stderr, "bad allocation for %d and %d\n",
2569 ALLOCNO_REGNO (a), ALLOCNO_REGNO (conflict_a));
2570 gcc_unreachable ();
2576 #endif
2578 /* Allocate REG_EQUIV_INIT. Set up it from IRA_REG_EQUIV which should
2579 be already calculated. */
2580 static void
2581 setup_reg_equiv_init (void)
2583 int i;
2584 int max_regno = max_reg_num ();
2586 for (i = 0; i < max_regno; i++)
2587 reg_equiv_init (i) = ira_reg_equiv[i].init_insns;
2590 /* Update equiv regno from movement of FROM_REGNO to TO_REGNO. INSNS
2591 are insns which were generated for such movement. It is assumed
2592 that FROM_REGNO and TO_REGNO always have the same value at the
2593 point of any move containing such registers. This function is used
2594 to update equiv info for register shuffles on the region borders
2595 and for caller save/restore insns. */
2596 void
2597 ira_update_equiv_info_by_shuffle_insn (int to_regno, int from_regno, rtx_insn *insns)
2599 rtx_insn *insn;
2600 rtx x, note;
2602 if (! ira_reg_equiv[from_regno].defined_p
2603 && (! ira_reg_equiv[to_regno].defined_p
2604 || ((x = ira_reg_equiv[to_regno].memory) != NULL_RTX
2605 && ! MEM_READONLY_P (x))))
2606 return;
2607 insn = insns;
2608 if (NEXT_INSN (insn) != NULL_RTX)
2610 if (! ira_reg_equiv[to_regno].defined_p)
2612 ira_assert (ira_reg_equiv[to_regno].init_insns == NULL_RTX);
2613 return;
2615 ira_reg_equiv[to_regno].defined_p = false;
2616 ira_reg_equiv[to_regno].memory
2617 = ira_reg_equiv[to_regno].constant
2618 = ira_reg_equiv[to_regno].invariant
2619 = ira_reg_equiv[to_regno].init_insns = NULL;
2620 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2621 fprintf (ira_dump_file,
2622 " Invalidating equiv info for reg %d\n", to_regno);
2623 return;
2625 /* It is possible that FROM_REGNO still has no equivalence because
2626 in shuffles to_regno<-from_regno and from_regno<-to_regno the 2nd
2627 insn was not processed yet. */
2628 if (ira_reg_equiv[from_regno].defined_p)
2630 ira_reg_equiv[to_regno].defined_p = true;
2631 if ((x = ira_reg_equiv[from_regno].memory) != NULL_RTX)
2633 ira_assert (ira_reg_equiv[from_regno].invariant == NULL_RTX
2634 && ira_reg_equiv[from_regno].constant == NULL_RTX);
2635 ira_assert (ira_reg_equiv[to_regno].memory == NULL_RTX
2636 || rtx_equal_p (ira_reg_equiv[to_regno].memory, x));
2637 ira_reg_equiv[to_regno].memory = x;
2638 if (! MEM_READONLY_P (x))
2639 /* We don't add the insn to insn init list because memory
2640 equivalence is just to say what memory is better to use
2641 when the pseudo is spilled. */
2642 return;
2644 else if ((x = ira_reg_equiv[from_regno].constant) != NULL_RTX)
2646 ira_assert (ira_reg_equiv[from_regno].invariant == NULL_RTX);
2647 ira_assert (ira_reg_equiv[to_regno].constant == NULL_RTX
2648 || rtx_equal_p (ira_reg_equiv[to_regno].constant, x));
2649 ira_reg_equiv[to_regno].constant = x;
2651 else
2653 x = ira_reg_equiv[from_regno].invariant;
2654 ira_assert (x != NULL_RTX);
2655 ira_assert (ira_reg_equiv[to_regno].invariant == NULL_RTX
2656 || rtx_equal_p (ira_reg_equiv[to_regno].invariant, x));
2657 ira_reg_equiv[to_regno].invariant = x;
2659 if (find_reg_note (insn, REG_EQUIV, x) == NULL_RTX)
2661 note = set_unique_reg_note (insn, REG_EQUIV, x);
2662 gcc_assert (note != NULL_RTX);
2663 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2665 fprintf (ira_dump_file,
2666 " Adding equiv note to insn %u for reg %d ",
2667 INSN_UID (insn), to_regno);
2668 dump_value_slim (ira_dump_file, x, 1);
2669 fprintf (ira_dump_file, "\n");
2673 ira_reg_equiv[to_regno].init_insns
2674 = gen_rtx_INSN_LIST (VOIDmode, insn,
2675 ira_reg_equiv[to_regno].init_insns);
2676 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2677 fprintf (ira_dump_file,
2678 " Adding equiv init move insn %u to reg %d\n",
2679 INSN_UID (insn), to_regno);
2682 /* Fix values of array REG_EQUIV_INIT after live range splitting done
2683 by IRA. */
2684 static void
2685 fix_reg_equiv_init (void)
2687 int max_regno = max_reg_num ();
2688 int i, new_regno, max;
2689 rtx set;
2690 rtx_insn_list *x, *next, *prev;
2691 rtx_insn *insn;
2693 if (max_regno_before_ira < max_regno)
2695 max = vec_safe_length (reg_equivs);
2696 grow_reg_equivs ();
2697 for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
2698 for (prev = NULL, x = reg_equiv_init (i);
2699 x != NULL_RTX;
2700 x = next)
2702 next = x->next ();
2703 insn = x->insn ();
2704 set = single_set (insn);
2705 ira_assert (set != NULL_RTX
2706 && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))));
2707 if (REG_P (SET_DEST (set))
2708 && ((int) REGNO (SET_DEST (set)) == i
2709 || (int) ORIGINAL_REGNO (SET_DEST (set)) == i))
2710 new_regno = REGNO (SET_DEST (set));
2711 else if (REG_P (SET_SRC (set))
2712 && ((int) REGNO (SET_SRC (set)) == i
2713 || (int) ORIGINAL_REGNO (SET_SRC (set)) == i))
2714 new_regno = REGNO (SET_SRC (set));
2715 else
2716 gcc_unreachable ();
2717 if (new_regno == i)
2718 prev = x;
2719 else
2721 /* Remove the wrong list element. */
2722 if (prev == NULL_RTX)
2723 reg_equiv_init (i) = next;
2724 else
2725 XEXP (prev, 1) = next;
2726 XEXP (x, 1) = reg_equiv_init (new_regno);
2727 reg_equiv_init (new_regno) = x;
2733 #ifdef ENABLE_IRA_CHECKING
2734 /* Print redundant memory-memory copies. */
2735 static void
2736 print_redundant_copies (void)
2738 int hard_regno;
2739 ira_allocno_t a;
2740 ira_copy_t cp, next_cp;
2741 ira_allocno_iterator ai;
2743 FOR_EACH_ALLOCNO (a, ai)
2745 if (ALLOCNO_CAP_MEMBER (a) != NULL)
2746 /* It is a cap. */
2747 continue;
2748 hard_regno = ALLOCNO_HARD_REGNO (a);
2749 if (hard_regno >= 0)
2750 continue;
2751 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2752 if (cp->first == a)
2753 next_cp = cp->next_first_allocno_copy;
2754 else
2756 next_cp = cp->next_second_allocno_copy;
2757 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL
2758 && cp->insn != NULL_RTX
2759 && ALLOCNO_HARD_REGNO (cp->first) == hard_regno)
2760 fprintf (ira_dump_file,
2761 " Redundant move from %d(freq %d):%d\n",
2762 INSN_UID (cp->insn), cp->freq, hard_regno);
2766 #endif
2768 /* Setup preferred and alternative classes for new pseudo-registers
2769 created by IRA starting with START. */
2770 static void
2771 setup_preferred_alternate_classes_for_new_pseudos (int start)
2773 int i, old_regno;
2774 int max_regno = max_reg_num ();
2776 for (i = start; i < max_regno; i++)
2778 old_regno = ORIGINAL_REGNO (regno_reg_rtx[i]);
2779 ira_assert (i != old_regno);
2780 setup_reg_classes (i, reg_preferred_class (old_regno),
2781 reg_alternate_class (old_regno),
2782 reg_allocno_class (old_regno));
2783 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2784 fprintf (ira_dump_file,
2785 " New r%d: setting preferred %s, alternative %s\n",
2786 i, reg_class_names[reg_preferred_class (old_regno)],
2787 reg_class_names[reg_alternate_class (old_regno)]);
2792 /* The number of entries allocated in reg_info. */
2793 static int allocated_reg_info_size;
2795 /* Regional allocation can create new pseudo-registers. This function
2796 expands some arrays for pseudo-registers. */
2797 static void
2798 expand_reg_info (void)
2800 int i;
2801 int size = max_reg_num ();
2803 resize_reg_info ();
2804 for (i = allocated_reg_info_size; i < size; i++)
2805 setup_reg_classes (i, GENERAL_REGS, ALL_REGS, GENERAL_REGS);
2806 setup_preferred_alternate_classes_for_new_pseudos (allocated_reg_info_size);
2807 allocated_reg_info_size = size;
2810 /* Return TRUE if there is too high register pressure in the function.
2811 It is used to decide when stack slot sharing is worth to do. */
2812 static bool
2813 too_high_register_pressure_p (void)
2815 int i;
2816 enum reg_class pclass;
2818 for (i = 0; i < ira_pressure_classes_num; i++)
2820 pclass = ira_pressure_classes[i];
2821 if (ira_loop_tree_root->reg_pressure[pclass] > 10000)
2822 return true;
2824 return false;
2829 /* Indicate that hard register number FROM was eliminated and replaced with
2830 an offset from hard register number TO. The status of hard registers live
2831 at the start of a basic block is updated by replacing a use of FROM with
2832 a use of TO. */
2834 void
2835 mark_elimination (int from, int to)
2837 basic_block bb;
2838 bitmap r;
2840 FOR_EACH_BB_FN (bb, cfun)
2842 r = DF_LR_IN (bb);
2843 if (bitmap_bit_p (r, from))
2845 bitmap_clear_bit (r, from);
2846 bitmap_set_bit (r, to);
2848 if (! df_live)
2849 continue;
2850 r = DF_LIVE_IN (bb);
2851 if (bitmap_bit_p (r, from))
2853 bitmap_clear_bit (r, from);
2854 bitmap_set_bit (r, to);
2861 /* The length of the following array. */
2862 int ira_reg_equiv_len;
2864 /* Info about equiv. info for each register. */
2865 struct ira_reg_equiv_s *ira_reg_equiv;
2867 /* Expand ira_reg_equiv if necessary. */
2868 void
2869 ira_expand_reg_equiv (void)
2871 int old = ira_reg_equiv_len;
2873 if (ira_reg_equiv_len > max_reg_num ())
2874 return;
2875 ira_reg_equiv_len = max_reg_num () * 3 / 2 + 1;
2876 ira_reg_equiv
2877 = (struct ira_reg_equiv_s *) xrealloc (ira_reg_equiv,
2878 ira_reg_equiv_len
2879 * sizeof (struct ira_reg_equiv_s));
2880 gcc_assert (old < ira_reg_equiv_len);
2881 memset (ira_reg_equiv + old, 0,
2882 sizeof (struct ira_reg_equiv_s) * (ira_reg_equiv_len - old));
2885 static void
2886 init_reg_equiv (void)
2888 ira_reg_equiv_len = 0;
2889 ira_reg_equiv = NULL;
2890 ira_expand_reg_equiv ();
2893 static void
2894 finish_reg_equiv (void)
2896 free (ira_reg_equiv);
2901 struct equivalence
2903 /* Set when a REG_EQUIV note is found or created. Use to
2904 keep track of what memory accesses might be created later,
2905 e.g. by reload. */
2906 rtx replacement;
2907 rtx *src_p;
2909 /* The list of each instruction which initializes this register.
2911 NULL indicates we know nothing about this register's equivalence
2912 properties.
2914 An INSN_LIST with a NULL insn indicates this pseudo is already
2915 known to not have a valid equivalence. */
2916 rtx_insn_list *init_insns;
2918 /* Loop depth is used to recognize equivalences which appear
2919 to be present within the same loop (or in an inner loop). */
2920 short loop_depth;
2921 /* Nonzero if this had a preexisting REG_EQUIV note. */
2922 unsigned char is_arg_equivalence : 1;
2923 /* Set when an attempt should be made to replace a register
2924 with the associated src_p entry. */
2925 unsigned char replace : 1;
2926 /* Set if this register has no known equivalence. */
2927 unsigned char no_equiv : 1;
2930 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
2931 structure for that register. */
2932 static struct equivalence *reg_equiv;
2934 /* Used for communication between the following two functions: contains
2935 a MEM that we wish to ensure remains unchanged. */
2936 static rtx equiv_mem;
2938 /* Set nonzero if EQUIV_MEM is modified. */
2939 static int equiv_mem_modified;
2941 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
2942 Called via note_stores. */
2943 static void
2944 validate_equiv_mem_from_store (rtx dest, const_rtx set ATTRIBUTE_UNUSED,
2945 void *data ATTRIBUTE_UNUSED)
2947 if ((REG_P (dest)
2948 && reg_overlap_mentioned_p (dest, equiv_mem))
2949 || (MEM_P (dest)
2950 && anti_dependence (equiv_mem, dest)))
2951 equiv_mem_modified = 1;
2954 /* Verify that no store between START and the death of REG invalidates
2955 MEMREF. MEMREF is invalidated by modifying a register used in MEMREF,
2956 by storing into an overlapping memory location, or with a non-const
2957 CALL_INSN.
2959 Return 1 if MEMREF remains valid. */
2960 static int
2961 validate_equiv_mem (rtx_insn *start, rtx reg, rtx memref)
2963 rtx_insn *insn;
2964 rtx note;
2966 equiv_mem = memref;
2967 equiv_mem_modified = 0;
2969 /* If the memory reference has side effects or is volatile, it isn't a
2970 valid equivalence. */
2971 if (side_effects_p (memref))
2972 return 0;
2974 for (insn = start; insn && ! equiv_mem_modified; insn = NEXT_INSN (insn))
2976 if (! INSN_P (insn))
2977 continue;
2979 if (find_reg_note (insn, REG_DEAD, reg))
2980 return 1;
2982 /* This used to ignore readonly memory and const/pure calls. The problem
2983 is the equivalent form may reference a pseudo which gets assigned a
2984 call clobbered hard reg. When we later replace REG with its
2985 equivalent form, the value in the call-clobbered reg has been
2986 changed and all hell breaks loose. */
2987 if (CALL_P (insn))
2988 return 0;
2990 note_stores (PATTERN (insn), validate_equiv_mem_from_store, NULL);
2992 /* If a register mentioned in MEMREF is modified via an
2993 auto-increment, we lose the equivalence. Do the same if one
2994 dies; although we could extend the life, it doesn't seem worth
2995 the trouble. */
2997 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2998 if ((REG_NOTE_KIND (note) == REG_INC
2999 || REG_NOTE_KIND (note) == REG_DEAD)
3000 && REG_P (XEXP (note, 0))
3001 && reg_overlap_mentioned_p (XEXP (note, 0), memref))
3002 return 0;
3005 return 0;
3008 /* Returns zero if X is known to be invariant. */
3009 static int
3010 equiv_init_varies_p (rtx x)
3012 RTX_CODE code = GET_CODE (x);
3013 int i;
3014 const char *fmt;
3016 switch (code)
3018 case MEM:
3019 return !MEM_READONLY_P (x) || equiv_init_varies_p (XEXP (x, 0));
3021 case CONST:
3022 CASE_CONST_ANY:
3023 case SYMBOL_REF:
3024 case LABEL_REF:
3025 return 0;
3027 case REG:
3028 return reg_equiv[REGNO (x)].replace == 0 && rtx_varies_p (x, 0);
3030 case ASM_OPERANDS:
3031 if (MEM_VOLATILE_P (x))
3032 return 1;
3034 /* Fall through. */
3036 default:
3037 break;
3040 fmt = GET_RTX_FORMAT (code);
3041 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3042 if (fmt[i] == 'e')
3044 if (equiv_init_varies_p (XEXP (x, i)))
3045 return 1;
3047 else if (fmt[i] == 'E')
3049 int j;
3050 for (j = 0; j < XVECLEN (x, i); j++)
3051 if (equiv_init_varies_p (XVECEXP (x, i, j)))
3052 return 1;
3055 return 0;
3058 /* Returns nonzero if X (used to initialize register REGNO) is movable.
3059 X is only movable if the registers it uses have equivalent initializations
3060 which appear to be within the same loop (or in an inner loop) and movable
3061 or if they are not candidates for local_alloc and don't vary. */
3062 static int
3063 equiv_init_movable_p (rtx x, int regno)
3065 int i, j;
3066 const char *fmt;
3067 enum rtx_code code = GET_CODE (x);
3069 switch (code)
3071 case SET:
3072 return equiv_init_movable_p (SET_SRC (x), regno);
3074 case CC0:
3075 case CLOBBER:
3076 return 0;
3078 case PRE_INC:
3079 case PRE_DEC:
3080 case POST_INC:
3081 case POST_DEC:
3082 case PRE_MODIFY:
3083 case POST_MODIFY:
3084 return 0;
3086 case REG:
3087 return ((reg_equiv[REGNO (x)].loop_depth >= reg_equiv[regno].loop_depth
3088 && reg_equiv[REGNO (x)].replace)
3089 || (REG_BASIC_BLOCK (REGNO (x)) < NUM_FIXED_BLOCKS
3090 && ! rtx_varies_p (x, 0)));
3092 case UNSPEC_VOLATILE:
3093 return 0;
3095 case ASM_OPERANDS:
3096 if (MEM_VOLATILE_P (x))
3097 return 0;
3099 /* Fall through. */
3101 default:
3102 break;
3105 fmt = GET_RTX_FORMAT (code);
3106 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3107 switch (fmt[i])
3109 case 'e':
3110 if (! equiv_init_movable_p (XEXP (x, i), regno))
3111 return 0;
3112 break;
3113 case 'E':
3114 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3115 if (! equiv_init_movable_p (XVECEXP (x, i, j), regno))
3116 return 0;
3117 break;
3120 return 1;
3123 /* TRUE if X uses any registers for which reg_equiv[REGNO].replace is
3124 true. */
3125 static int
3126 contains_replace_regs (rtx x)
3128 int i, j;
3129 const char *fmt;
3130 enum rtx_code code = GET_CODE (x);
3132 switch (code)
3134 case CONST:
3135 case LABEL_REF:
3136 case SYMBOL_REF:
3137 CASE_CONST_ANY:
3138 case PC:
3139 case CC0:
3140 case HIGH:
3141 return 0;
3143 case REG:
3144 return reg_equiv[REGNO (x)].replace;
3146 default:
3147 break;
3150 fmt = GET_RTX_FORMAT (code);
3151 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3152 switch (fmt[i])
3154 case 'e':
3155 if (contains_replace_regs (XEXP (x, i)))
3156 return 1;
3157 break;
3158 case 'E':
3159 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3160 if (contains_replace_regs (XVECEXP (x, i, j)))
3161 return 1;
3162 break;
3165 return 0;
3168 /* TRUE if X references a memory location that would be affected by a store
3169 to MEMREF. */
3170 static int
3171 memref_referenced_p (rtx memref, rtx x)
3173 int i, j;
3174 const char *fmt;
3175 enum rtx_code code = GET_CODE (x);
3177 switch (code)
3179 case CONST:
3180 case LABEL_REF:
3181 case SYMBOL_REF:
3182 CASE_CONST_ANY:
3183 case PC:
3184 case CC0:
3185 case HIGH:
3186 case LO_SUM:
3187 return 0;
3189 case REG:
3190 return (reg_equiv[REGNO (x)].replacement
3191 && memref_referenced_p (memref,
3192 reg_equiv[REGNO (x)].replacement));
3194 case MEM:
3195 if (true_dependence (memref, VOIDmode, x))
3196 return 1;
3197 break;
3199 case SET:
3200 /* If we are setting a MEM, it doesn't count (its address does), but any
3201 other SET_DEST that has a MEM in it is referencing the MEM. */
3202 if (MEM_P (SET_DEST (x)))
3204 if (memref_referenced_p (memref, XEXP (SET_DEST (x), 0)))
3205 return 1;
3207 else if (memref_referenced_p (memref, SET_DEST (x)))
3208 return 1;
3210 return memref_referenced_p (memref, SET_SRC (x));
3212 default:
3213 break;
3216 fmt = GET_RTX_FORMAT (code);
3217 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3218 switch (fmt[i])
3220 case 'e':
3221 if (memref_referenced_p (memref, XEXP (x, i)))
3222 return 1;
3223 break;
3224 case 'E':
3225 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3226 if (memref_referenced_p (memref, XVECEXP (x, i, j)))
3227 return 1;
3228 break;
3231 return 0;
3234 /* TRUE if some insn in the range (START, END] references a memory location
3235 that would be affected by a store to MEMREF. */
3236 static int
3237 memref_used_between_p (rtx memref, rtx_insn *start, rtx_insn *end)
3239 rtx_insn *insn;
3241 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
3242 insn = NEXT_INSN (insn))
3244 if (!NONDEBUG_INSN_P (insn))
3245 continue;
3247 if (memref_referenced_p (memref, PATTERN (insn)))
3248 return 1;
3250 /* Nonconst functions may access memory. */
3251 if (CALL_P (insn) && (! RTL_CONST_CALL_P (insn)))
3252 return 1;
3255 return 0;
3258 /* Mark REG as having no known equivalence.
3259 Some instructions might have been processed before and furnished
3260 with REG_EQUIV notes for this register; these notes will have to be
3261 removed.
3262 STORE is the piece of RTL that does the non-constant / conflicting
3263 assignment - a SET, CLOBBER or REG_INC note. It is currently not used,
3264 but needs to be there because this function is called from note_stores. */
3265 static void
3266 no_equiv (rtx reg, const_rtx store ATTRIBUTE_UNUSED,
3267 void *data ATTRIBUTE_UNUSED)
3269 int regno;
3270 rtx_insn_list *list;
3272 if (!REG_P (reg))
3273 return;
3274 regno = REGNO (reg);
3275 reg_equiv[regno].no_equiv = 1;
3276 list = reg_equiv[regno].init_insns;
3277 if (list && list->insn () == NULL)
3278 return;
3279 reg_equiv[regno].init_insns = gen_rtx_INSN_LIST (VOIDmode, NULL_RTX, NULL);
3280 reg_equiv[regno].replacement = NULL_RTX;
3281 /* This doesn't matter for equivalences made for argument registers, we
3282 should keep their initialization insns. */
3283 if (reg_equiv[regno].is_arg_equivalence)
3284 return;
3285 ira_reg_equiv[regno].defined_p = false;
3286 ira_reg_equiv[regno].init_insns = NULL;
3287 for (; list; list = list->next ())
3289 rtx_insn *insn = list->insn ();
3290 remove_note (insn, find_reg_note (insn, REG_EQUIV, NULL_RTX));
3294 /* Check whether the SUBREG is a paradoxical subreg and set the result
3295 in PDX_SUBREGS. */
3297 static void
3298 set_paradoxical_subreg (rtx_insn *insn, bool *pdx_subregs)
3300 subrtx_iterator::array_type array;
3301 FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
3303 const_rtx subreg = *iter;
3304 if (GET_CODE (subreg) == SUBREG)
3306 const_rtx reg = SUBREG_REG (subreg);
3307 if (REG_P (reg) && paradoxical_subreg_p (subreg))
3308 pdx_subregs[REGNO (reg)] = true;
3313 /* In DEBUG_INSN location adjust REGs from CLEARED_REGS bitmap to the
3314 equivalent replacement. */
3316 static rtx
3317 adjust_cleared_regs (rtx loc, const_rtx old_rtx ATTRIBUTE_UNUSED, void *data)
3319 if (REG_P (loc))
3321 bitmap cleared_regs = (bitmap) data;
3322 if (bitmap_bit_p (cleared_regs, REGNO (loc)))
3323 return simplify_replace_fn_rtx (copy_rtx (*reg_equiv[REGNO (loc)].src_p),
3324 NULL_RTX, adjust_cleared_regs, data);
3326 return NULL_RTX;
3329 /* Nonzero if we recorded an equivalence for a LABEL_REF. */
3330 static int recorded_label_ref;
3332 /* Find registers that are equivalent to a single value throughout the
3333 compilation (either because they can be referenced in memory or are
3334 set once from a single constant). Lower their priority for a
3335 register.
3337 If such a register is only referenced once, try substituting its
3338 value into the using insn. If it succeeds, we can eliminate the
3339 register completely.
3341 Initialize init_insns in ira_reg_equiv array.
3343 Return non-zero if jump label rebuilding should be done. */
3344 static int
3345 update_equiv_regs (void)
3347 rtx_insn *insn;
3348 basic_block bb;
3349 int loop_depth;
3350 bitmap cleared_regs;
3351 bool *pdx_subregs;
3353 /* We need to keep track of whether or not we recorded a LABEL_REF so
3354 that we know if the jump optimizer needs to be rerun. */
3355 recorded_label_ref = 0;
3357 /* Use pdx_subregs to show whether a reg is used in a paradoxical
3358 subreg. */
3359 pdx_subregs = XCNEWVEC (bool, max_regno);
3361 reg_equiv = XCNEWVEC (struct equivalence, max_regno);
3362 grow_reg_equivs ();
3364 init_alias_analysis ();
3366 /* Scan insns and set pdx_subregs[regno] if the reg is used in a
3367 paradoxical subreg. Don't set such reg equivalent to a mem,
3368 because lra will not substitute such equiv memory in order to
3369 prevent access beyond allocated memory for paradoxical memory subreg. */
3370 FOR_EACH_BB_FN (bb, cfun)
3371 FOR_BB_INSNS (bb, insn)
3372 if (NONDEBUG_INSN_P (insn))
3373 set_paradoxical_subreg (insn, pdx_subregs);
3375 /* Scan the insns and find which registers have equivalences. Do this
3376 in a separate scan of the insns because (due to -fcse-follow-jumps)
3377 a register can be set below its use. */
3378 FOR_EACH_BB_FN (bb, cfun)
3380 loop_depth = bb_loop_depth (bb);
3382 for (insn = BB_HEAD (bb);
3383 insn != NEXT_INSN (BB_END (bb));
3384 insn = NEXT_INSN (insn))
3386 rtx note;
3387 rtx set;
3388 rtx dest, src;
3389 int regno;
3391 if (! INSN_P (insn))
3392 continue;
3394 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
3395 if (REG_NOTE_KIND (note) == REG_INC)
3396 no_equiv (XEXP (note, 0), note, NULL);
3398 set = single_set (insn);
3400 /* If this insn contains more (or less) than a single SET,
3401 only mark all destinations as having no known equivalence. */
3402 if (set == NULL_RTX)
3404 note_stores (PATTERN (insn), no_equiv, NULL);
3405 continue;
3407 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3409 int i;
3411 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
3413 rtx part = XVECEXP (PATTERN (insn), 0, i);
3414 if (part != set)
3415 note_stores (part, no_equiv, NULL);
3419 dest = SET_DEST (set);
3420 src = SET_SRC (set);
3422 /* See if this is setting up the equivalence between an argument
3423 register and its stack slot. */
3424 note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
3425 if (note)
3427 gcc_assert (REG_P (dest));
3428 regno = REGNO (dest);
3430 /* Note that we don't want to clear init_insns in
3431 ira_reg_equiv even if there are multiple sets of this
3432 register. */
3433 reg_equiv[regno].is_arg_equivalence = 1;
3435 /* The insn result can have equivalence memory although
3436 the equivalence is not set up by the insn. We add
3437 this insn to init insns as it is a flag for now that
3438 regno has an equivalence. We will remove the insn
3439 from init insn list later. */
3440 if (rtx_equal_p (src, XEXP (note, 0)) || MEM_P (XEXP (note, 0)))
3441 ira_reg_equiv[regno].init_insns
3442 = gen_rtx_INSN_LIST (VOIDmode, insn,
3443 ira_reg_equiv[regno].init_insns);
3445 /* Continue normally in case this is a candidate for
3446 replacements. */
3449 if (!optimize)
3450 continue;
3452 /* We only handle the case of a pseudo register being set
3453 once, or always to the same value. */
3454 /* ??? The mn10200 port breaks if we add equivalences for
3455 values that need an ADDRESS_REGS register and set them equivalent
3456 to a MEM of a pseudo. The actual problem is in the over-conservative
3457 handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
3458 calculate_needs, but we traditionally work around this problem
3459 here by rejecting equivalences when the destination is in a register
3460 that's likely spilled. This is fragile, of course, since the
3461 preferred class of a pseudo depends on all instructions that set
3462 or use it. */
3464 if (!REG_P (dest)
3465 || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER
3466 || (reg_equiv[regno].init_insns
3467 && reg_equiv[regno].init_insns->insn () == NULL)
3468 || (targetm.class_likely_spilled_p (reg_preferred_class (regno))
3469 && MEM_P (src) && ! reg_equiv[regno].is_arg_equivalence))
3471 /* This might be setting a SUBREG of a pseudo, a pseudo that is
3472 also set somewhere else to a constant. */
3473 note_stores (set, no_equiv, NULL);
3474 continue;
3477 /* Don't set reg (if pdx_subregs[regno] == true) equivalent to a mem. */
3478 if (MEM_P (src) && pdx_subregs[regno])
3480 note_stores (set, no_equiv, NULL);
3481 continue;
3484 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
3486 /* cse sometimes generates function invariants, but doesn't put a
3487 REG_EQUAL note on the insn. Since this note would be redundant,
3488 there's no point creating it earlier than here. */
3489 if (! note && ! rtx_varies_p (src, 0))
3490 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
3492 /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
3493 since it represents a function call. */
3494 if (note && GET_CODE (XEXP (note, 0)) == EXPR_LIST)
3495 note = NULL_RTX;
3497 if (DF_REG_DEF_COUNT (regno) != 1)
3499 bool equal_p = true;
3500 rtx_insn_list *list;
3502 /* If we have already processed this pseudo and determined it
3503 can not have an equivalence, then honor that decision. */
3504 if (reg_equiv[regno].no_equiv)
3505 continue;
3507 if (! note
3508 || rtx_varies_p (XEXP (note, 0), 0)
3509 || (reg_equiv[regno].replacement
3510 && ! rtx_equal_p (XEXP (note, 0),
3511 reg_equiv[regno].replacement)))
3513 no_equiv (dest, set, NULL);
3514 continue;
3517 list = reg_equiv[regno].init_insns;
3518 for (; list; list = list->next ())
3520 rtx note_tmp;
3521 rtx_insn *insn_tmp;
3523 insn_tmp = list->insn ();
3524 note_tmp = find_reg_note (insn_tmp, REG_EQUAL, NULL_RTX);
3525 gcc_assert (note_tmp);
3526 if (! rtx_equal_p (XEXP (note, 0), XEXP (note_tmp, 0)))
3528 equal_p = false;
3529 break;
3533 if (! equal_p)
3535 no_equiv (dest, set, NULL);
3536 continue;
3540 /* Record this insn as initializing this register. */
3541 reg_equiv[regno].init_insns
3542 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv[regno].init_insns);
3544 /* If this register is known to be equal to a constant, record that
3545 it is always equivalent to the constant. */
3546 if (DF_REG_DEF_COUNT (regno) == 1
3547 && note && ! rtx_varies_p (XEXP (note, 0), 0))
3549 rtx note_value = XEXP (note, 0);
3550 remove_note (insn, note);
3551 set_unique_reg_note (insn, REG_EQUIV, note_value);
3554 /* If this insn introduces a "constant" register, decrease the priority
3555 of that register. Record this insn if the register is only used once
3556 more and the equivalence value is the same as our source.
3558 The latter condition is checked for two reasons: First, it is an
3559 indication that it may be more efficient to actually emit the insn
3560 as written (if no registers are available, reload will substitute
3561 the equivalence). Secondly, it avoids problems with any registers
3562 dying in this insn whose death notes would be missed.
3564 If we don't have a REG_EQUIV note, see if this insn is loading
3565 a register used only in one basic block from a MEM. If so, and the
3566 MEM remains unchanged for the life of the register, add a REG_EQUIV
3567 note. */
3568 note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
3570 if (note == NULL_RTX && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
3571 && MEM_P (SET_SRC (set))
3572 && validate_equiv_mem (insn, dest, SET_SRC (set)))
3573 note = set_unique_reg_note (insn, REG_EQUIV, copy_rtx (SET_SRC (set)));
3575 if (note)
3577 int regno = REGNO (dest);
3578 rtx x = XEXP (note, 0);
3580 /* If we haven't done so, record for reload that this is an
3581 equivalencing insn. */
3582 if (!reg_equiv[regno].is_arg_equivalence)
3583 ira_reg_equiv[regno].init_insns
3584 = gen_rtx_INSN_LIST (VOIDmode, insn,
3585 ira_reg_equiv[regno].init_insns);
3587 /* Record whether or not we created a REG_EQUIV note for a LABEL_REF.
3588 We might end up substituting the LABEL_REF for uses of the
3589 pseudo here or later. That kind of transformation may turn an
3590 indirect jump into a direct jump, in which case we must rerun the
3591 jump optimizer to ensure that the JUMP_LABEL fields are valid. */
3592 if (GET_CODE (x) == LABEL_REF
3593 || (GET_CODE (x) == CONST
3594 && GET_CODE (XEXP (x, 0)) == PLUS
3595 && (GET_CODE (XEXP (XEXP (x, 0), 0)) == LABEL_REF)))
3596 recorded_label_ref = 1;
3598 reg_equiv[regno].replacement = x;
3599 reg_equiv[regno].src_p = &SET_SRC (set);
3600 reg_equiv[regno].loop_depth = (short) loop_depth;
3602 /* Don't mess with things live during setjmp. */
3603 if (REG_LIVE_LENGTH (regno) >= 0 && optimize)
3605 /* Note that the statement below does not affect the priority
3606 in local-alloc! */
3607 REG_LIVE_LENGTH (regno) *= 2;
3609 /* If the register is referenced exactly twice, meaning it is
3610 set once and used once, indicate that the reference may be
3611 replaced by the equivalence we computed above. Do this
3612 even if the register is only used in one block so that
3613 dependencies can be handled where the last register is
3614 used in a different block (i.e. HIGH / LO_SUM sequences)
3615 and to reduce the number of registers alive across
3616 calls. */
3618 if (REG_N_REFS (regno) == 2
3619 && (rtx_equal_p (x, src)
3620 || ! equiv_init_varies_p (src))
3621 && NONJUMP_INSN_P (insn)
3622 && equiv_init_movable_p (PATTERN (insn), regno))
3623 reg_equiv[regno].replace = 1;
3629 if (!optimize)
3630 goto out;
3632 /* A second pass, to gather additional equivalences with memory. This needs
3633 to be done after we know which registers we are going to replace. */
3635 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
3637 rtx set, src, dest;
3638 unsigned regno;
3640 if (! INSN_P (insn))
3641 continue;
3643 set = single_set (insn);
3644 if (! set)
3645 continue;
3647 dest = SET_DEST (set);
3648 src = SET_SRC (set);
3650 /* If this sets a MEM to the contents of a REG that is only used
3651 in a single basic block, see if the register is always equivalent
3652 to that memory location and if moving the store from INSN to the
3653 insn that set REG is safe. If so, put a REG_EQUIV note on the
3654 initializing insn.
3656 Don't add a REG_EQUIV note if the insn already has one. The existing
3657 REG_EQUIV is likely more useful than the one we are adding.
3659 If one of the regs in the address has reg_equiv[REGNO].replace set,
3660 then we can't add this REG_EQUIV note. The reg_equiv[REGNO].replace
3661 optimization may move the set of this register immediately before
3662 insn, which puts it after reg_equiv[REGNO].init_insns, and hence
3663 the mention in the REG_EQUIV note would be to an uninitialized
3664 pseudo. */
3666 if (MEM_P (dest) && REG_P (src)
3667 && (regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
3668 && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
3669 && DF_REG_DEF_COUNT (regno) == 1
3670 && reg_equiv[regno].init_insns != NULL
3671 && reg_equiv[regno].init_insns->insn () != NULL
3672 && ! find_reg_note (XEXP (reg_equiv[regno].init_insns, 0),
3673 REG_EQUIV, NULL_RTX)
3674 && ! contains_replace_regs (XEXP (dest, 0))
3675 && ! pdx_subregs[regno])
3677 rtx_insn *init_insn =
3678 as_a <rtx_insn *> (XEXP (reg_equiv[regno].init_insns, 0));
3679 if (validate_equiv_mem (init_insn, src, dest)
3680 && ! memref_used_between_p (dest, init_insn, insn)
3681 /* Attaching a REG_EQUIV note will fail if INIT_INSN has
3682 multiple sets. */
3683 && set_unique_reg_note (init_insn, REG_EQUIV, copy_rtx (dest)))
3685 /* This insn makes the equivalence, not the one initializing
3686 the register. */
3687 ira_reg_equiv[regno].init_insns
3688 = gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
3689 df_notes_rescan (init_insn);
3694 cleared_regs = BITMAP_ALLOC (NULL);
3695 /* Now scan all regs killed in an insn to see if any of them are
3696 registers only used that once. If so, see if we can replace the
3697 reference with the equivalent form. If we can, delete the
3698 initializing reference and this register will go away. If we
3699 can't replace the reference, and the initializing reference is
3700 within the same loop (or in an inner loop), then move the register
3701 initialization just before the use, so that they are in the same
3702 basic block. */
3703 FOR_EACH_BB_REVERSE_FN (bb, cfun)
3705 loop_depth = bb_loop_depth (bb);
3706 for (insn = BB_END (bb);
3707 insn != PREV_INSN (BB_HEAD (bb));
3708 insn = PREV_INSN (insn))
3710 rtx link;
3712 if (! INSN_P (insn))
3713 continue;
3715 /* Don't substitute into a non-local goto, this confuses CFG. */
3716 if (JUMP_P (insn)
3717 && find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
3718 continue;
3720 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3722 if (REG_NOTE_KIND (link) == REG_DEAD
3723 /* Make sure this insn still refers to the register. */
3724 && reg_mentioned_p (XEXP (link, 0), PATTERN (insn)))
3726 int regno = REGNO (XEXP (link, 0));
3727 rtx equiv_insn;
3729 if (! reg_equiv[regno].replace
3730 || reg_equiv[regno].loop_depth < (short) loop_depth
3731 /* There is no sense to move insns if live range
3732 shrinkage or register pressure-sensitive
3733 scheduling were done because it will not
3734 improve allocation but worsen insn schedule
3735 with a big probability. */
3736 || flag_live_range_shrinkage
3737 || (flag_sched_pressure && flag_schedule_insns))
3738 continue;
3740 /* reg_equiv[REGNO].replace gets set only when
3741 REG_N_REFS[REGNO] is 2, i.e. the register is set
3742 once and used once. (If it were only set, but
3743 not used, flow would have deleted the setting
3744 insns.) Hence there can only be one insn in
3745 reg_equiv[REGNO].init_insns. */
3746 gcc_assert (reg_equiv[regno].init_insns
3747 && !XEXP (reg_equiv[regno].init_insns, 1));
3748 equiv_insn = XEXP (reg_equiv[regno].init_insns, 0);
3750 /* We may not move instructions that can throw, since
3751 that changes basic block boundaries and we are not
3752 prepared to adjust the CFG to match. */
3753 if (can_throw_internal (equiv_insn))
3754 continue;
3756 if (asm_noperands (PATTERN (equiv_insn)) < 0
3757 && validate_replace_rtx (regno_reg_rtx[regno],
3758 *(reg_equiv[regno].src_p), insn))
3760 rtx equiv_link;
3761 rtx last_link;
3762 rtx note;
3764 /* Find the last note. */
3765 for (last_link = link; XEXP (last_link, 1);
3766 last_link = XEXP (last_link, 1))
3769 /* Append the REG_DEAD notes from equiv_insn. */
3770 equiv_link = REG_NOTES (equiv_insn);
3771 while (equiv_link)
3773 note = equiv_link;
3774 equiv_link = XEXP (equiv_link, 1);
3775 if (REG_NOTE_KIND (note) == REG_DEAD)
3777 remove_note (equiv_insn, note);
3778 XEXP (last_link, 1) = note;
3779 XEXP (note, 1) = NULL_RTX;
3780 last_link = note;
3784 remove_death (regno, insn);
3785 SET_REG_N_REFS (regno, 0);
3786 REG_FREQ (regno) = 0;
3787 delete_insn (equiv_insn);
3789 reg_equiv[regno].init_insns
3790 = reg_equiv[regno].init_insns->next ();
3792 ira_reg_equiv[regno].init_insns = NULL;
3793 bitmap_set_bit (cleared_regs, regno);
3795 /* Move the initialization of the register to just before
3796 INSN. Update the flow information. */
3797 else if (prev_nondebug_insn (insn) != equiv_insn)
3799 rtx_insn *new_insn;
3801 new_insn = emit_insn_before (PATTERN (equiv_insn), insn);
3802 REG_NOTES (new_insn) = REG_NOTES (equiv_insn);
3803 REG_NOTES (equiv_insn) = 0;
3804 /* Rescan it to process the notes. */
3805 df_insn_rescan (new_insn);
3807 /* Make sure this insn is recognized before
3808 reload begins, otherwise
3809 eliminate_regs_in_insn will die. */
3810 INSN_CODE (new_insn) = INSN_CODE (equiv_insn);
3812 delete_insn (equiv_insn);
3814 XEXP (reg_equiv[regno].init_insns, 0) = new_insn;
3816 REG_BASIC_BLOCK (regno) = bb->index;
3817 REG_N_CALLS_CROSSED (regno) = 0;
3818 REG_FREQ_CALLS_CROSSED (regno) = 0;
3819 REG_N_THROWING_CALLS_CROSSED (regno) = 0;
3820 REG_LIVE_LENGTH (regno) = 2;
3822 if (insn == BB_HEAD (bb))
3823 BB_HEAD (bb) = PREV_INSN (insn);
3825 ira_reg_equiv[regno].init_insns
3826 = gen_rtx_INSN_LIST (VOIDmode, new_insn, NULL_RTX);
3827 bitmap_set_bit (cleared_regs, regno);
3834 if (!bitmap_empty_p (cleared_regs))
3836 FOR_EACH_BB_FN (bb, cfun)
3838 bitmap_and_compl_into (DF_LR_IN (bb), cleared_regs);
3839 bitmap_and_compl_into (DF_LR_OUT (bb), cleared_regs);
3840 if (! df_live)
3841 continue;
3842 bitmap_and_compl_into (DF_LIVE_IN (bb), cleared_regs);
3843 bitmap_and_compl_into (DF_LIVE_OUT (bb), cleared_regs);
3846 /* Last pass - adjust debug insns referencing cleared regs. */
3847 if (MAY_HAVE_DEBUG_INSNS)
3848 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
3849 if (DEBUG_INSN_P (insn))
3851 rtx old_loc = INSN_VAR_LOCATION_LOC (insn);
3852 INSN_VAR_LOCATION_LOC (insn)
3853 = simplify_replace_fn_rtx (old_loc, NULL_RTX,
3854 adjust_cleared_regs,
3855 (void *) cleared_regs);
3856 if (old_loc != INSN_VAR_LOCATION_LOC (insn))
3857 df_insn_rescan (insn);
3861 BITMAP_FREE (cleared_regs);
3863 out:
3864 /* Clean up. */
3866 end_alias_analysis ();
3867 free (reg_equiv);
3868 free (pdx_subregs);
3869 return recorded_label_ref;
3874 /* Set up fields memory, constant, and invariant from init_insns in
3875 the structures of array ira_reg_equiv. */
3876 static void
3877 setup_reg_equiv (void)
3879 int i;
3880 rtx_insn_list *elem, *prev_elem, *next_elem;
3881 rtx_insn *insn;
3882 rtx set, x;
3884 for (i = FIRST_PSEUDO_REGISTER; i < ira_reg_equiv_len; i++)
3885 for (prev_elem = NULL, elem = ira_reg_equiv[i].init_insns;
3886 elem;
3887 prev_elem = elem, elem = next_elem)
3889 next_elem = elem->next ();
3890 insn = elem->insn ();
3891 set = single_set (insn);
3893 /* Init insns can set up equivalence when the reg is a destination or
3894 a source (in this case the destination is memory). */
3895 if (set != 0 && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))))
3897 if ((x = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != NULL)
3899 x = XEXP (x, 0);
3900 if (REG_P (SET_DEST (set))
3901 && REGNO (SET_DEST (set)) == (unsigned int) i
3902 && ! rtx_equal_p (SET_SRC (set), x) && MEM_P (x))
3904 /* This insn reporting the equivalence but
3905 actually not setting it. Remove it from the
3906 list. */
3907 if (prev_elem == NULL)
3908 ira_reg_equiv[i].init_insns = next_elem;
3909 else
3910 XEXP (prev_elem, 1) = next_elem;
3911 elem = prev_elem;
3914 else if (REG_P (SET_DEST (set))
3915 && REGNO (SET_DEST (set)) == (unsigned int) i)
3916 x = SET_SRC (set);
3917 else
3919 gcc_assert (REG_P (SET_SRC (set))
3920 && REGNO (SET_SRC (set)) == (unsigned int) i);
3921 x = SET_DEST (set);
3923 if (! function_invariant_p (x)
3924 || ! flag_pic
3925 /* A function invariant is often CONSTANT_P but may
3926 include a register. We promise to only pass
3927 CONSTANT_P objects to LEGITIMATE_PIC_OPERAND_P. */
3928 || (CONSTANT_P (x) && LEGITIMATE_PIC_OPERAND_P (x)))
3930 /* It can happen that a REG_EQUIV note contains a MEM
3931 that is not a legitimate memory operand. As later
3932 stages of reload assume that all addresses found in
3933 the lra_regno_equiv_* arrays were originally
3934 legitimate, we ignore such REG_EQUIV notes. */
3935 if (memory_operand (x, VOIDmode))
3937 ira_reg_equiv[i].defined_p = true;
3938 ira_reg_equiv[i].memory = x;
3939 continue;
3941 else if (function_invariant_p (x))
3943 machine_mode mode;
3945 mode = GET_MODE (SET_DEST (set));
3946 if (GET_CODE (x) == PLUS
3947 || x == frame_pointer_rtx || x == arg_pointer_rtx)
3948 /* This is PLUS of frame pointer and a constant,
3949 or fp, or argp. */
3950 ira_reg_equiv[i].invariant = x;
3951 else if (targetm.legitimate_constant_p (mode, x))
3952 ira_reg_equiv[i].constant = x;
3953 else
3955 ira_reg_equiv[i].memory = force_const_mem (mode, x);
3956 if (ira_reg_equiv[i].memory == NULL_RTX)
3958 ira_reg_equiv[i].defined_p = false;
3959 ira_reg_equiv[i].init_insns = NULL;
3960 break;
3963 ira_reg_equiv[i].defined_p = true;
3964 continue;
3968 ira_reg_equiv[i].defined_p = false;
3969 ira_reg_equiv[i].init_insns = NULL;
3970 break;
3976 /* Print chain C to FILE. */
3977 static void
3978 print_insn_chain (FILE *file, struct insn_chain *c)
3980 fprintf (file, "insn=%d, ", INSN_UID (c->insn));
3981 bitmap_print (file, &c->live_throughout, "live_throughout: ", ", ");
3982 bitmap_print (file, &c->dead_or_set, "dead_or_set: ", "\n");
3986 /* Print all reload_insn_chains to FILE. */
3987 static void
3988 print_insn_chains (FILE *file)
3990 struct insn_chain *c;
3991 for (c = reload_insn_chain; c ; c = c->next)
3992 print_insn_chain (file, c);
3995 /* Return true if pseudo REGNO should be added to set live_throughout
3996 or dead_or_set of the insn chains for reload consideration. */
3997 static bool
3998 pseudo_for_reload_consideration_p (int regno)
4000 /* Consider spilled pseudos too for IRA because they still have a
4001 chance to get hard-registers in the reload when IRA is used. */
4002 return (reg_renumber[regno] >= 0 || ira_conflicts_p);
4005 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
4006 REG to the number of nregs, and INIT_VALUE to get the
4007 initialization. ALLOCNUM need not be the regno of REG. */
4008 static void
4009 init_live_subregs (bool init_value, sbitmap *live_subregs,
4010 bitmap live_subregs_used, int allocnum, rtx reg)
4012 unsigned int regno = REGNO (SUBREG_REG (reg));
4013 int size = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno]));
4015 gcc_assert (size > 0);
4017 /* Been there, done that. */
4018 if (bitmap_bit_p (live_subregs_used, allocnum))
4019 return;
4021 /* Create a new one. */
4022 if (live_subregs[allocnum] == NULL)
4023 live_subregs[allocnum] = sbitmap_alloc (size);
4025 /* If the entire reg was live before blasting into subregs, we need
4026 to init all of the subregs to ones else init to 0. */
4027 if (init_value)
4028 bitmap_ones (live_subregs[allocnum]);
4029 else
4030 bitmap_clear (live_subregs[allocnum]);
4032 bitmap_set_bit (live_subregs_used, allocnum);
4035 /* Walk the insns of the current function and build reload_insn_chain,
4036 and record register life information. */
4037 static void
4038 build_insn_chain (void)
4040 unsigned int i;
4041 struct insn_chain **p = &reload_insn_chain;
4042 basic_block bb;
4043 struct insn_chain *c = NULL;
4044 struct insn_chain *next = NULL;
4045 bitmap live_relevant_regs = BITMAP_ALLOC (NULL);
4046 bitmap elim_regset = BITMAP_ALLOC (NULL);
4047 /* live_subregs is a vector used to keep accurate information about
4048 which hardregs are live in multiword pseudos. live_subregs and
4049 live_subregs_used are indexed by pseudo number. The live_subreg
4050 entry for a particular pseudo is only used if the corresponding
4051 element is non zero in live_subregs_used. The sbitmap size of
4052 live_subreg[allocno] is number of bytes that the pseudo can
4053 occupy. */
4054 sbitmap *live_subregs = XCNEWVEC (sbitmap, max_regno);
4055 bitmap live_subregs_used = BITMAP_ALLOC (NULL);
4057 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4058 if (TEST_HARD_REG_BIT (eliminable_regset, i))
4059 bitmap_set_bit (elim_regset, i);
4060 FOR_EACH_BB_REVERSE_FN (bb, cfun)
4062 bitmap_iterator bi;
4063 rtx_insn *insn;
4065 CLEAR_REG_SET (live_relevant_regs);
4066 bitmap_clear (live_subregs_used);
4068 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb), 0, i, bi)
4070 if (i >= FIRST_PSEUDO_REGISTER)
4071 break;
4072 bitmap_set_bit (live_relevant_regs, i);
4075 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb),
4076 FIRST_PSEUDO_REGISTER, i, bi)
4078 if (pseudo_for_reload_consideration_p (i))
4079 bitmap_set_bit (live_relevant_regs, i);
4082 FOR_BB_INSNS_REVERSE (bb, insn)
4084 if (!NOTE_P (insn) && !BARRIER_P (insn))
4086 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4087 df_ref def, use;
4089 c = new_insn_chain ();
4090 c->next = next;
4091 next = c;
4092 *p = c;
4093 p = &c->prev;
4095 c->insn = insn;
4096 c->block = bb->index;
4098 if (NONDEBUG_INSN_P (insn))
4099 FOR_EACH_INSN_INFO_DEF (def, insn_info)
4101 unsigned int regno = DF_REF_REGNO (def);
4103 /* Ignore may clobbers because these are generated
4104 from calls. However, every other kind of def is
4105 added to dead_or_set. */
4106 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
4108 if (regno < FIRST_PSEUDO_REGISTER)
4110 if (!fixed_regs[regno])
4111 bitmap_set_bit (&c->dead_or_set, regno);
4113 else if (pseudo_for_reload_consideration_p (regno))
4114 bitmap_set_bit (&c->dead_or_set, regno);
4117 if ((regno < FIRST_PSEUDO_REGISTER
4118 || reg_renumber[regno] >= 0
4119 || ira_conflicts_p)
4120 && (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)))
4122 rtx reg = DF_REF_REG (def);
4124 /* We can model subregs, but not if they are
4125 wrapped in ZERO_EXTRACTS. */
4126 if (GET_CODE (reg) == SUBREG
4127 && !DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT))
4129 unsigned int start = SUBREG_BYTE (reg);
4130 unsigned int last = start
4131 + GET_MODE_SIZE (GET_MODE (reg));
4133 init_live_subregs
4134 (bitmap_bit_p (live_relevant_regs, regno),
4135 live_subregs, live_subregs_used, regno, reg);
4137 if (!DF_REF_FLAGS_IS_SET
4138 (def, DF_REF_STRICT_LOW_PART))
4140 /* Expand the range to cover entire words.
4141 Bytes added here are "don't care". */
4142 start
4143 = start / UNITS_PER_WORD * UNITS_PER_WORD;
4144 last = ((last + UNITS_PER_WORD - 1)
4145 / UNITS_PER_WORD * UNITS_PER_WORD);
4148 /* Ignore the paradoxical bits. */
4149 if (last > SBITMAP_SIZE (live_subregs[regno]))
4150 last = SBITMAP_SIZE (live_subregs[regno]);
4152 while (start < last)
4154 bitmap_clear_bit (live_subregs[regno], start);
4155 start++;
4158 if (bitmap_empty_p (live_subregs[regno]))
4160 bitmap_clear_bit (live_subregs_used, regno);
4161 bitmap_clear_bit (live_relevant_regs, regno);
4163 else
4164 /* Set live_relevant_regs here because
4165 that bit has to be true to get us to
4166 look at the live_subregs fields. */
4167 bitmap_set_bit (live_relevant_regs, regno);
4169 else
4171 /* DF_REF_PARTIAL is generated for
4172 subregs, STRICT_LOW_PART, and
4173 ZERO_EXTRACT. We handle the subreg
4174 case above so here we have to keep from
4175 modeling the def as a killing def. */
4176 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL))
4178 bitmap_clear_bit (live_subregs_used, regno);
4179 bitmap_clear_bit (live_relevant_regs, regno);
4185 bitmap_and_compl_into (live_relevant_regs, elim_regset);
4186 bitmap_copy (&c->live_throughout, live_relevant_regs);
4188 if (NONDEBUG_INSN_P (insn))
4189 FOR_EACH_INSN_INFO_USE (use, insn_info)
4191 unsigned int regno = DF_REF_REGNO (use);
4192 rtx reg = DF_REF_REG (use);
4194 /* DF_REF_READ_WRITE on a use means that this use
4195 is fabricated from a def that is a partial set
4196 to a multiword reg. Here, we only model the
4197 subreg case that is not wrapped in ZERO_EXTRACT
4198 precisely so we do not need to look at the
4199 fabricated use. */
4200 if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE)
4201 && !DF_REF_FLAGS_IS_SET (use, DF_REF_ZERO_EXTRACT)
4202 && DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG))
4203 continue;
4205 /* Add the last use of each var to dead_or_set. */
4206 if (!bitmap_bit_p (live_relevant_regs, regno))
4208 if (regno < FIRST_PSEUDO_REGISTER)
4210 if (!fixed_regs[regno])
4211 bitmap_set_bit (&c->dead_or_set, regno);
4213 else if (pseudo_for_reload_consideration_p (regno))
4214 bitmap_set_bit (&c->dead_or_set, regno);
4217 if (regno < FIRST_PSEUDO_REGISTER
4218 || pseudo_for_reload_consideration_p (regno))
4220 if (GET_CODE (reg) == SUBREG
4221 && !DF_REF_FLAGS_IS_SET (use,
4222 DF_REF_SIGN_EXTRACT
4223 | DF_REF_ZERO_EXTRACT))
4225 unsigned int start = SUBREG_BYTE (reg);
4226 unsigned int last = start
4227 + GET_MODE_SIZE (GET_MODE (reg));
4229 init_live_subregs
4230 (bitmap_bit_p (live_relevant_regs, regno),
4231 live_subregs, live_subregs_used, regno, reg);
4233 /* Ignore the paradoxical bits. */
4234 if (last > SBITMAP_SIZE (live_subregs[regno]))
4235 last = SBITMAP_SIZE (live_subregs[regno]);
4237 while (start < last)
4239 bitmap_set_bit (live_subregs[regno], start);
4240 start++;
4243 else
4244 /* Resetting the live_subregs_used is
4245 effectively saying do not use the subregs
4246 because we are reading the whole
4247 pseudo. */
4248 bitmap_clear_bit (live_subregs_used, regno);
4249 bitmap_set_bit (live_relevant_regs, regno);
4255 /* FIXME!! The following code is a disaster. Reload needs to see the
4256 labels and jump tables that are just hanging out in between
4257 the basic blocks. See pr33676. */
4258 insn = BB_HEAD (bb);
4260 /* Skip over the barriers and cruft. */
4261 while (insn && (BARRIER_P (insn) || NOTE_P (insn)
4262 || BLOCK_FOR_INSN (insn) == bb))
4263 insn = PREV_INSN (insn);
4265 /* While we add anything except barriers and notes, the focus is
4266 to get the labels and jump tables into the
4267 reload_insn_chain. */
4268 while (insn)
4270 if (!NOTE_P (insn) && !BARRIER_P (insn))
4272 if (BLOCK_FOR_INSN (insn))
4273 break;
4275 c = new_insn_chain ();
4276 c->next = next;
4277 next = c;
4278 *p = c;
4279 p = &c->prev;
4281 /* The block makes no sense here, but it is what the old
4282 code did. */
4283 c->block = bb->index;
4284 c->insn = insn;
4285 bitmap_copy (&c->live_throughout, live_relevant_regs);
4287 insn = PREV_INSN (insn);
4291 reload_insn_chain = c;
4292 *p = NULL;
4294 for (i = 0; i < (unsigned int) max_regno; i++)
4295 if (live_subregs[i] != NULL)
4296 sbitmap_free (live_subregs[i]);
4297 free (live_subregs);
4298 BITMAP_FREE (live_subregs_used);
4299 BITMAP_FREE (live_relevant_regs);
4300 BITMAP_FREE (elim_regset);
4302 if (dump_file)
4303 print_insn_chains (dump_file);
4306 /* Examine the rtx found in *LOC, which is read or written to as determined
4307 by TYPE. Return false if we find a reason why an insn containing this
4308 rtx should not be moved (such as accesses to non-constant memory), true
4309 otherwise. */
4310 static bool
4311 rtx_moveable_p (rtx *loc, enum op_type type)
4313 const char *fmt;
4314 rtx x = *loc;
4315 enum rtx_code code = GET_CODE (x);
4316 int i, j;
4318 code = GET_CODE (x);
4319 switch (code)
4321 case CONST:
4322 CASE_CONST_ANY:
4323 case SYMBOL_REF:
4324 case LABEL_REF:
4325 return true;
4327 case PC:
4328 return type == OP_IN;
4330 case CC0:
4331 return false;
4333 case REG:
4334 if (x == frame_pointer_rtx)
4335 return true;
4336 if (HARD_REGISTER_P (x))
4337 return false;
4339 return true;
4341 case MEM:
4342 if (type == OP_IN && MEM_READONLY_P (x))
4343 return rtx_moveable_p (&XEXP (x, 0), OP_IN);
4344 return false;
4346 case SET:
4347 return (rtx_moveable_p (&SET_SRC (x), OP_IN)
4348 && rtx_moveable_p (&SET_DEST (x), OP_OUT));
4350 case STRICT_LOW_PART:
4351 return rtx_moveable_p (&XEXP (x, 0), OP_OUT);
4353 case ZERO_EXTRACT:
4354 case SIGN_EXTRACT:
4355 return (rtx_moveable_p (&XEXP (x, 0), type)
4356 && rtx_moveable_p (&XEXP (x, 1), OP_IN)
4357 && rtx_moveable_p (&XEXP (x, 2), OP_IN));
4359 case CLOBBER:
4360 return rtx_moveable_p (&SET_DEST (x), OP_OUT);
4362 case UNSPEC_VOLATILE:
4363 /* It is a bad idea to consider insns with such rtl
4364 as moveable ones. The insn scheduler also considers them as barrier
4365 for a reason. */
4366 return false;
4368 default:
4369 break;
4372 fmt = GET_RTX_FORMAT (code);
4373 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4375 if (fmt[i] == 'e')
4377 if (!rtx_moveable_p (&XEXP (x, i), type))
4378 return false;
4380 else if (fmt[i] == 'E')
4381 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4383 if (!rtx_moveable_p (&XVECEXP (x, i, j), type))
4384 return false;
4387 return true;
4390 /* A wrapper around dominated_by_p, which uses the information in UID_LUID
4391 to give dominance relationships between two insns I1 and I2. */
4392 static bool
4393 insn_dominated_by_p (rtx i1, rtx i2, int *uid_luid)
4395 basic_block bb1 = BLOCK_FOR_INSN (i1);
4396 basic_block bb2 = BLOCK_FOR_INSN (i2);
4398 if (bb1 == bb2)
4399 return uid_luid[INSN_UID (i2)] < uid_luid[INSN_UID (i1)];
4400 return dominated_by_p (CDI_DOMINATORS, bb1, bb2);
4403 /* Record the range of register numbers added by find_moveable_pseudos. */
4404 int first_moveable_pseudo, last_moveable_pseudo;
4406 /* These two vectors hold data for every register added by
4407 find_movable_pseudos, with index 0 holding data for the
4408 first_moveable_pseudo. */
4409 /* The original home register. */
4410 static vec<rtx> pseudo_replaced_reg;
4412 /* Look for instances where we have an instruction that is known to increase
4413 register pressure, and whose result is not used immediately. If it is
4414 possible to move the instruction downwards to just before its first use,
4415 split its lifetime into two ranges. We create a new pseudo to compute the
4416 value, and emit a move instruction just before the first use. If, after
4417 register allocation, the new pseudo remains unallocated, the function
4418 move_unallocated_pseudos then deletes the move instruction and places
4419 the computation just before the first use.
4421 Such a move is safe and profitable if all the input registers remain live
4422 and unchanged between the original computation and its first use. In such
4423 a situation, the computation is known to increase register pressure, and
4424 moving it is known to at least not worsen it.
4426 We restrict moves to only those cases where a register remains unallocated,
4427 in order to avoid interfering too much with the instruction schedule. As
4428 an exception, we may move insns which only modify their input register
4429 (typically induction variables), as this increases the freedom for our
4430 intended transformation, and does not limit the second instruction
4431 scheduler pass. */
4433 static void
4434 find_moveable_pseudos (void)
4436 unsigned i;
4437 int max_regs = max_reg_num ();
4438 int max_uid = get_max_uid ();
4439 basic_block bb;
4440 int *uid_luid = XNEWVEC (int, max_uid);
4441 rtx_insn **closest_uses = XNEWVEC (rtx_insn *, max_regs);
4442 /* A set of registers which are live but not modified throughout a block. */
4443 bitmap_head *bb_transp_live = XNEWVEC (bitmap_head,
4444 last_basic_block_for_fn (cfun));
4445 /* A set of registers which only exist in a given basic block. */
4446 bitmap_head *bb_local = XNEWVEC (bitmap_head,
4447 last_basic_block_for_fn (cfun));
4448 /* A set of registers which are set once, in an instruction that can be
4449 moved freely downwards, but are otherwise transparent to a block. */
4450 bitmap_head *bb_moveable_reg_sets = XNEWVEC (bitmap_head,
4451 last_basic_block_for_fn (cfun));
4452 bitmap_head live, used, set, interesting, unusable_as_input;
4453 bitmap_iterator bi;
4454 bitmap_initialize (&interesting, 0);
4456 first_moveable_pseudo = max_regs;
4457 pseudo_replaced_reg.release ();
4458 pseudo_replaced_reg.safe_grow_cleared (max_regs);
4460 df_analyze ();
4461 calculate_dominance_info (CDI_DOMINATORS);
4463 i = 0;
4464 bitmap_initialize (&live, 0);
4465 bitmap_initialize (&used, 0);
4466 bitmap_initialize (&set, 0);
4467 bitmap_initialize (&unusable_as_input, 0);
4468 FOR_EACH_BB_FN (bb, cfun)
4470 rtx_insn *insn;
4471 bitmap transp = bb_transp_live + bb->index;
4472 bitmap moveable = bb_moveable_reg_sets + bb->index;
4473 bitmap local = bb_local + bb->index;
4475 bitmap_initialize (local, 0);
4476 bitmap_initialize (transp, 0);
4477 bitmap_initialize (moveable, 0);
4478 bitmap_copy (&live, df_get_live_out (bb));
4479 bitmap_and_into (&live, df_get_live_in (bb));
4480 bitmap_copy (transp, &live);
4481 bitmap_clear (moveable);
4482 bitmap_clear (&live);
4483 bitmap_clear (&used);
4484 bitmap_clear (&set);
4485 FOR_BB_INSNS (bb, insn)
4486 if (NONDEBUG_INSN_P (insn))
4488 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4489 df_ref def, use;
4491 uid_luid[INSN_UID (insn)] = i++;
4493 def = df_single_def (insn_info);
4494 use = df_single_use (insn_info);
4495 if (use
4496 && def
4497 && DF_REF_REGNO (use) == DF_REF_REGNO (def)
4498 && !bitmap_bit_p (&set, DF_REF_REGNO (use))
4499 && rtx_moveable_p (&PATTERN (insn), OP_IN))
4501 unsigned regno = DF_REF_REGNO (use);
4502 bitmap_set_bit (moveable, regno);
4503 bitmap_set_bit (&set, regno);
4504 bitmap_set_bit (&used, regno);
4505 bitmap_clear_bit (transp, regno);
4506 continue;
4508 FOR_EACH_INSN_INFO_USE (use, insn_info)
4510 unsigned regno = DF_REF_REGNO (use);
4511 bitmap_set_bit (&used, regno);
4512 if (bitmap_clear_bit (moveable, regno))
4513 bitmap_clear_bit (transp, regno);
4516 FOR_EACH_INSN_INFO_DEF (def, insn_info)
4518 unsigned regno = DF_REF_REGNO (def);
4519 bitmap_set_bit (&set, regno);
4520 bitmap_clear_bit (transp, regno);
4521 bitmap_clear_bit (moveable, regno);
4526 bitmap_clear (&live);
4527 bitmap_clear (&used);
4528 bitmap_clear (&set);
4530 FOR_EACH_BB_FN (bb, cfun)
4532 bitmap local = bb_local + bb->index;
4533 rtx_insn *insn;
4535 FOR_BB_INSNS (bb, insn)
4536 if (NONDEBUG_INSN_P (insn))
4538 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4539 rtx_insn *def_insn;
4540 rtx closest_use, note;
4541 df_ref def, use;
4542 unsigned regno;
4543 bool all_dominated, all_local;
4544 machine_mode mode;
4546 def = df_single_def (insn_info);
4547 /* There must be exactly one def in this insn. */
4548 if (!def || !single_set (insn))
4549 continue;
4550 /* This must be the only definition of the reg. We also limit
4551 which modes we deal with so that we can assume we can generate
4552 move instructions. */
4553 regno = DF_REF_REGNO (def);
4554 mode = GET_MODE (DF_REF_REG (def));
4555 if (DF_REG_DEF_COUNT (regno) != 1
4556 || !DF_REF_INSN_INFO (def)
4557 || HARD_REGISTER_NUM_P (regno)
4558 || DF_REG_EQ_USE_COUNT (regno) > 0
4559 || (!INTEGRAL_MODE_P (mode) && !FLOAT_MODE_P (mode)))
4560 continue;
4561 def_insn = DF_REF_INSN (def);
4563 for (note = REG_NOTES (def_insn); note; note = XEXP (note, 1))
4564 if (REG_NOTE_KIND (note) == REG_EQUIV && MEM_P (XEXP (note, 0)))
4565 break;
4567 if (note)
4569 if (dump_file)
4570 fprintf (dump_file, "Ignoring reg %d, has equiv memory\n",
4571 regno);
4572 bitmap_set_bit (&unusable_as_input, regno);
4573 continue;
4576 use = DF_REG_USE_CHAIN (regno);
4577 all_dominated = true;
4578 all_local = true;
4579 closest_use = NULL_RTX;
4580 for (; use; use = DF_REF_NEXT_REG (use))
4582 rtx_insn *insn;
4583 if (!DF_REF_INSN_INFO (use))
4585 all_dominated = false;
4586 all_local = false;
4587 break;
4589 insn = DF_REF_INSN (use);
4590 if (DEBUG_INSN_P (insn))
4591 continue;
4592 if (BLOCK_FOR_INSN (insn) != BLOCK_FOR_INSN (def_insn))
4593 all_local = false;
4594 if (!insn_dominated_by_p (insn, def_insn, uid_luid))
4595 all_dominated = false;
4596 if (closest_use != insn && closest_use != const0_rtx)
4598 if (closest_use == NULL_RTX)
4599 closest_use = insn;
4600 else if (insn_dominated_by_p (closest_use, insn, uid_luid))
4601 closest_use = insn;
4602 else if (!insn_dominated_by_p (insn, closest_use, uid_luid))
4603 closest_use = const0_rtx;
4606 if (!all_dominated)
4608 if (dump_file)
4609 fprintf (dump_file, "Reg %d not all uses dominated by set\n",
4610 regno);
4611 continue;
4613 if (all_local)
4614 bitmap_set_bit (local, regno);
4615 if (closest_use == const0_rtx || closest_use == NULL
4616 || next_nonnote_nondebug_insn (def_insn) == closest_use)
4618 if (dump_file)
4619 fprintf (dump_file, "Reg %d uninteresting%s\n", regno,
4620 closest_use == const0_rtx || closest_use == NULL
4621 ? " (no unique first use)" : "");
4622 continue;
4624 if (HAVE_cc0 && reg_referenced_p (cc0_rtx, PATTERN (closest_use)))
4626 if (dump_file)
4627 fprintf (dump_file, "Reg %d: closest user uses cc0\n",
4628 regno);
4629 continue;
4632 bitmap_set_bit (&interesting, regno);
4633 /* If we get here, we know closest_use is a non-NULL insn
4634 (as opposed to const_0_rtx). */
4635 closest_uses[regno] = as_a <rtx_insn *> (closest_use);
4637 if (dump_file && (all_local || all_dominated))
4639 fprintf (dump_file, "Reg %u:", regno);
4640 if (all_local)
4641 fprintf (dump_file, " local to bb %d", bb->index);
4642 if (all_dominated)
4643 fprintf (dump_file, " def dominates all uses");
4644 if (closest_use != const0_rtx)
4645 fprintf (dump_file, " has unique first use");
4646 fputs ("\n", dump_file);
4651 EXECUTE_IF_SET_IN_BITMAP (&interesting, 0, i, bi)
4653 df_ref def = DF_REG_DEF_CHAIN (i);
4654 rtx_insn *def_insn = DF_REF_INSN (def);
4655 basic_block def_block = BLOCK_FOR_INSN (def_insn);
4656 bitmap def_bb_local = bb_local + def_block->index;
4657 bitmap def_bb_moveable = bb_moveable_reg_sets + def_block->index;
4658 bitmap def_bb_transp = bb_transp_live + def_block->index;
4659 bool local_to_bb_p = bitmap_bit_p (def_bb_local, i);
4660 rtx_insn *use_insn = closest_uses[i];
4661 df_ref use;
4662 bool all_ok = true;
4663 bool all_transp = true;
4665 if (!REG_P (DF_REF_REG (def)))
4666 continue;
4668 if (!local_to_bb_p)
4670 if (dump_file)
4671 fprintf (dump_file, "Reg %u not local to one basic block\n",
4673 continue;
4675 if (reg_equiv_init (i) != NULL_RTX)
4677 if (dump_file)
4678 fprintf (dump_file, "Ignoring reg %u with equiv init insn\n",
4680 continue;
4682 if (!rtx_moveable_p (&PATTERN (def_insn), OP_IN))
4684 if (dump_file)
4685 fprintf (dump_file, "Found def insn %d for %d to be not moveable\n",
4686 INSN_UID (def_insn), i);
4687 continue;
4689 if (dump_file)
4690 fprintf (dump_file, "Examining insn %d, def for %d\n",
4691 INSN_UID (def_insn), i);
4692 FOR_EACH_INSN_USE (use, def_insn)
4694 unsigned regno = DF_REF_REGNO (use);
4695 if (bitmap_bit_p (&unusable_as_input, regno))
4697 all_ok = false;
4698 if (dump_file)
4699 fprintf (dump_file, " found unusable input reg %u.\n", regno);
4700 break;
4702 if (!bitmap_bit_p (def_bb_transp, regno))
4704 if (bitmap_bit_p (def_bb_moveable, regno)
4705 && !control_flow_insn_p (use_insn)
4706 && (!HAVE_cc0 || !sets_cc0_p (use_insn)))
4708 if (modified_between_p (DF_REF_REG (use), def_insn, use_insn))
4710 rtx_insn *x = NEXT_INSN (def_insn);
4711 while (!modified_in_p (DF_REF_REG (use), x))
4713 gcc_assert (x != use_insn);
4714 x = NEXT_INSN (x);
4716 if (dump_file)
4717 fprintf (dump_file, " input reg %u modified but insn %d moveable\n",
4718 regno, INSN_UID (x));
4719 emit_insn_after (PATTERN (x), use_insn);
4720 set_insn_deleted (x);
4722 else
4724 if (dump_file)
4725 fprintf (dump_file, " input reg %u modified between def and use\n",
4726 regno);
4727 all_transp = false;
4730 else
4731 all_transp = false;
4734 if (!all_ok)
4735 continue;
4736 if (!dbg_cnt (ira_move))
4737 break;
4738 if (dump_file)
4739 fprintf (dump_file, " all ok%s\n", all_transp ? " and transp" : "");
4741 if (all_transp)
4743 rtx def_reg = DF_REF_REG (def);
4744 rtx newreg = ira_create_new_reg (def_reg);
4745 if (validate_change (def_insn, DF_REF_REAL_LOC (def), newreg, 0))
4747 unsigned nregno = REGNO (newreg);
4748 emit_insn_before (gen_move_insn (def_reg, newreg), use_insn);
4749 nregno -= max_regs;
4750 pseudo_replaced_reg[nregno] = def_reg;
4755 FOR_EACH_BB_FN (bb, cfun)
4757 bitmap_clear (bb_local + bb->index);
4758 bitmap_clear (bb_transp_live + bb->index);
4759 bitmap_clear (bb_moveable_reg_sets + bb->index);
4761 bitmap_clear (&interesting);
4762 bitmap_clear (&unusable_as_input);
4763 free (uid_luid);
4764 free (closest_uses);
4765 free (bb_local);
4766 free (bb_transp_live);
4767 free (bb_moveable_reg_sets);
4769 last_moveable_pseudo = max_reg_num ();
4771 fix_reg_equiv_init ();
4772 expand_reg_info ();
4773 regstat_free_n_sets_and_refs ();
4774 regstat_free_ri ();
4775 regstat_init_n_sets_and_refs ();
4776 regstat_compute_ri ();
4777 free_dominance_info (CDI_DOMINATORS);
4780 /* If SET pattern SET is an assignment from a hard register to a pseudo which
4781 is live at CALL_DOM (if non-NULL, otherwise this check is omitted), return
4782 the destination. Otherwise return NULL. */
4784 static rtx
4785 interesting_dest_for_shprep_1 (rtx set, basic_block call_dom)
4787 rtx src = SET_SRC (set);
4788 rtx dest = SET_DEST (set);
4789 if (!REG_P (src) || !HARD_REGISTER_P (src)
4790 || !REG_P (dest) || HARD_REGISTER_P (dest)
4791 || (call_dom && !bitmap_bit_p (df_get_live_in (call_dom), REGNO (dest))))
4792 return NULL;
4793 return dest;
4796 /* If insn is interesting for parameter range-splitting shrink-wrapping
4797 preparation, i.e. it is a single set from a hard register to a pseudo, which
4798 is live at CALL_DOM (if non-NULL, otherwise this check is omitted), or a
4799 parallel statement with only one such statement, return the destination.
4800 Otherwise return NULL. */
4802 static rtx
4803 interesting_dest_for_shprep (rtx_insn *insn, basic_block call_dom)
4805 if (!INSN_P (insn))
4806 return NULL;
4807 rtx pat = PATTERN (insn);
4808 if (GET_CODE (pat) == SET)
4809 return interesting_dest_for_shprep_1 (pat, call_dom);
4811 if (GET_CODE (pat) != PARALLEL)
4812 return NULL;
4813 rtx ret = NULL;
4814 for (int i = 0; i < XVECLEN (pat, 0); i++)
4816 rtx sub = XVECEXP (pat, 0, i);
4817 if (GET_CODE (sub) == USE || GET_CODE (sub) == CLOBBER)
4818 continue;
4819 if (GET_CODE (sub) != SET
4820 || side_effects_p (sub))
4821 return NULL;
4822 rtx dest = interesting_dest_for_shprep_1 (sub, call_dom);
4823 if (dest && ret)
4824 return NULL;
4825 if (dest)
4826 ret = dest;
4828 return ret;
4831 /* Split live ranges of pseudos that are loaded from hard registers in the
4832 first BB in a BB that dominates all non-sibling call if such a BB can be
4833 found and is not in a loop. Return true if the function has made any
4834 changes. */
4836 static bool
4837 split_live_ranges_for_shrink_wrap (void)
4839 basic_block bb, call_dom = NULL;
4840 basic_block first = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
4841 rtx_insn *insn, *last_interesting_insn = NULL;
4842 bitmap_head need_new, reachable;
4843 vec<basic_block> queue;
4845 if (!SHRINK_WRAPPING_ENABLED)
4846 return false;
4848 bitmap_initialize (&need_new, 0);
4849 bitmap_initialize (&reachable, 0);
4850 queue.create (n_basic_blocks_for_fn (cfun));
4852 FOR_EACH_BB_FN (bb, cfun)
4853 FOR_BB_INSNS (bb, insn)
4854 if (CALL_P (insn) && !SIBLING_CALL_P (insn))
4856 if (bb == first)
4858 bitmap_clear (&need_new);
4859 bitmap_clear (&reachable);
4860 queue.release ();
4861 return false;
4864 bitmap_set_bit (&need_new, bb->index);
4865 bitmap_set_bit (&reachable, bb->index);
4866 queue.quick_push (bb);
4867 break;
4870 if (queue.is_empty ())
4872 bitmap_clear (&need_new);
4873 bitmap_clear (&reachable);
4874 queue.release ();
4875 return false;
4878 while (!queue.is_empty ())
4880 edge e;
4881 edge_iterator ei;
4883 bb = queue.pop ();
4884 FOR_EACH_EDGE (e, ei, bb->succs)
4885 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
4886 && bitmap_set_bit (&reachable, e->dest->index))
4887 queue.quick_push (e->dest);
4889 queue.release ();
4891 FOR_BB_INSNS (first, insn)
4893 rtx dest = interesting_dest_for_shprep (insn, NULL);
4894 if (!dest)
4895 continue;
4897 if (DF_REG_DEF_COUNT (REGNO (dest)) > 1)
4899 bitmap_clear (&need_new);
4900 bitmap_clear (&reachable);
4901 return false;
4904 for (df_ref use = DF_REG_USE_CHAIN (REGNO(dest));
4905 use;
4906 use = DF_REF_NEXT_REG (use))
4908 int ubbi = DF_REF_BB (use)->index;
4909 if (bitmap_bit_p (&reachable, ubbi))
4910 bitmap_set_bit (&need_new, ubbi);
4912 last_interesting_insn = insn;
4915 bitmap_clear (&reachable);
4916 if (!last_interesting_insn)
4918 bitmap_clear (&need_new);
4919 return false;
4922 call_dom = nearest_common_dominator_for_set (CDI_DOMINATORS, &need_new);
4923 bitmap_clear (&need_new);
4924 if (call_dom == first)
4925 return false;
4927 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
4928 while (bb_loop_depth (call_dom) > 0)
4929 call_dom = get_immediate_dominator (CDI_DOMINATORS, call_dom);
4930 loop_optimizer_finalize ();
4932 if (call_dom == first)
4933 return false;
4935 calculate_dominance_info (CDI_POST_DOMINATORS);
4936 if (dominated_by_p (CDI_POST_DOMINATORS, first, call_dom))
4938 free_dominance_info (CDI_POST_DOMINATORS);
4939 return false;
4941 free_dominance_info (CDI_POST_DOMINATORS);
4943 if (dump_file)
4944 fprintf (dump_file, "Will split live ranges of parameters at BB %i\n",
4945 call_dom->index);
4947 bool ret = false;
4948 FOR_BB_INSNS (first, insn)
4950 rtx dest = interesting_dest_for_shprep (insn, call_dom);
4951 if (!dest || dest == pic_offset_table_rtx)
4952 continue;
4954 rtx newreg = NULL_RTX;
4955 df_ref use, next;
4956 for (use = DF_REG_USE_CHAIN (REGNO (dest)); use; use = next)
4958 rtx_insn *uin = DF_REF_INSN (use);
4959 next = DF_REF_NEXT_REG (use);
4961 basic_block ubb = BLOCK_FOR_INSN (uin);
4962 if (ubb == call_dom
4963 || dominated_by_p (CDI_DOMINATORS, ubb, call_dom))
4965 if (!newreg)
4966 newreg = ira_create_new_reg (dest);
4967 validate_change (uin, DF_REF_REAL_LOC (use), newreg, true);
4971 if (newreg)
4973 rtx_insn *new_move = gen_move_insn (newreg, dest);
4974 emit_insn_after (new_move, bb_note (call_dom));
4975 if (dump_file)
4977 fprintf (dump_file, "Split live-range of register ");
4978 print_rtl_single (dump_file, dest);
4980 ret = true;
4983 if (insn == last_interesting_insn)
4984 break;
4986 apply_change_group ();
4987 return ret;
4990 /* Perform the second half of the transformation started in
4991 find_moveable_pseudos. We look for instances where the newly introduced
4992 pseudo remains unallocated, and remove it by moving the definition to
4993 just before its use, replacing the move instruction generated by
4994 find_moveable_pseudos. */
4995 static void
4996 move_unallocated_pseudos (void)
4998 int i;
4999 for (i = first_moveable_pseudo; i < last_moveable_pseudo; i++)
5000 if (reg_renumber[i] < 0)
5002 int idx = i - first_moveable_pseudo;
5003 rtx other_reg = pseudo_replaced_reg[idx];
5004 rtx_insn *def_insn = DF_REF_INSN (DF_REG_DEF_CHAIN (i));
5005 /* The use must follow all definitions of OTHER_REG, so we can
5006 insert the new definition immediately after any of them. */
5007 df_ref other_def = DF_REG_DEF_CHAIN (REGNO (other_reg));
5008 rtx_insn *move_insn = DF_REF_INSN (other_def);
5009 rtx_insn *newinsn = emit_insn_after (PATTERN (def_insn), move_insn);
5010 rtx set;
5011 int success;
5013 if (dump_file)
5014 fprintf (dump_file, "moving def of %d (insn %d now) ",
5015 REGNO (other_reg), INSN_UID (def_insn));
5017 delete_insn (move_insn);
5018 while ((other_def = DF_REG_DEF_CHAIN (REGNO (other_reg))))
5019 delete_insn (DF_REF_INSN (other_def));
5020 delete_insn (def_insn);
5022 set = single_set (newinsn);
5023 success = validate_change (newinsn, &SET_DEST (set), other_reg, 0);
5024 gcc_assert (success);
5025 if (dump_file)
5026 fprintf (dump_file, " %d) rather than keep unallocated replacement %d\n",
5027 INSN_UID (newinsn), i);
5028 SET_REG_N_REFS (i, 0);
5032 /* If the backend knows where to allocate pseudos for hard
5033 register initial values, register these allocations now. */
5034 static void
5035 allocate_initial_values (void)
5037 if (targetm.allocate_initial_value)
5039 rtx hreg, preg, x;
5040 int i, regno;
5042 for (i = 0; HARD_REGISTER_NUM_P (i); i++)
5044 if (! initial_value_entry (i, &hreg, &preg))
5045 break;
5047 x = targetm.allocate_initial_value (hreg);
5048 regno = REGNO (preg);
5049 if (x && REG_N_SETS (regno) <= 1)
5051 if (MEM_P (x))
5052 reg_equiv_memory_loc (regno) = x;
5053 else
5055 basic_block bb;
5056 int new_regno;
5058 gcc_assert (REG_P (x));
5059 new_regno = REGNO (x);
5060 reg_renumber[regno] = new_regno;
5061 /* Poke the regno right into regno_reg_rtx so that even
5062 fixed regs are accepted. */
5063 SET_REGNO (preg, new_regno);
5064 /* Update global register liveness information. */
5065 FOR_EACH_BB_FN (bb, cfun)
5067 if (REGNO_REG_SET_P (df_get_live_in (bb), regno))
5068 SET_REGNO_REG_SET (df_get_live_in (bb), new_regno);
5069 if (REGNO_REG_SET_P (df_get_live_out (bb), regno))
5070 SET_REGNO_REG_SET (df_get_live_out (bb), new_regno);
5076 gcc_checking_assert (! initial_value_entry (FIRST_PSEUDO_REGISTER,
5077 &hreg, &preg));
5082 /* True when we use LRA instead of reload pass for the current
5083 function. */
5084 bool ira_use_lra_p;
5086 /* True if we have allocno conflicts. It is false for non-optimized
5087 mode or when the conflict table is too big. */
5088 bool ira_conflicts_p;
5090 /* Saved between IRA and reload. */
5091 static int saved_flag_ira_share_spill_slots;
5093 /* This is the main entry of IRA. */
5094 static void
5095 ira (FILE *f)
5097 bool loops_p;
5098 int ira_max_point_before_emit;
5099 int rebuild_p;
5100 bool saved_flag_caller_saves = flag_caller_saves;
5101 enum ira_region saved_flag_ira_region = flag_ira_region;
5103 /* Perform target specific PIC register initialization. */
5104 targetm.init_pic_reg ();
5106 ira_conflicts_p = optimize > 0;
5108 ira_use_lra_p = targetm.lra_p ();
5109 /* If there are too many pseudos and/or basic blocks (e.g. 10K
5110 pseudos and 10K blocks or 100K pseudos and 1K blocks), we will
5111 use simplified and faster algorithms in LRA. */
5112 lra_simple_p
5113 = (ira_use_lra_p
5114 && max_reg_num () >= (1 << 26) / last_basic_block_for_fn (cfun));
5115 if (lra_simple_p)
5117 /* It permits to skip live range splitting in LRA. */
5118 flag_caller_saves = false;
5119 /* There is no sense to do regional allocation when we use
5120 simplified LRA. */
5121 flag_ira_region = IRA_REGION_ONE;
5122 ira_conflicts_p = false;
5125 #ifndef IRA_NO_OBSTACK
5126 gcc_obstack_init (&ira_obstack);
5127 #endif
5128 bitmap_obstack_initialize (&ira_bitmap_obstack);
5130 /* LRA uses its own infrastructure to handle caller save registers. */
5131 if (flag_caller_saves && !ira_use_lra_p)
5132 init_caller_save ();
5134 if (flag_ira_verbose < 10)
5136 internal_flag_ira_verbose = flag_ira_verbose;
5137 ira_dump_file = f;
5139 else
5141 internal_flag_ira_verbose = flag_ira_verbose - 10;
5142 ira_dump_file = stderr;
5145 setup_prohibited_mode_move_regs ();
5146 decrease_live_ranges_number ();
5147 df_note_add_problem ();
5149 /* DF_LIVE can't be used in the register allocator, too many other
5150 parts of the compiler depend on using the "classic" liveness
5151 interpretation of the DF_LR problem. See PR38711.
5152 Remove the problem, so that we don't spend time updating it in
5153 any of the df_analyze() calls during IRA/LRA. */
5154 if (optimize > 1)
5155 df_remove_problem (df_live);
5156 gcc_checking_assert (df_live == NULL);
5158 #ifdef ENABLE_CHECKING
5159 df->changeable_flags |= DF_VERIFY_SCHEDULED;
5160 #endif
5161 df_analyze ();
5163 init_reg_equiv ();
5164 if (ira_conflicts_p)
5166 calculate_dominance_info (CDI_DOMINATORS);
5168 if (split_live_ranges_for_shrink_wrap ())
5169 df_analyze ();
5171 free_dominance_info (CDI_DOMINATORS);
5174 df_clear_flags (DF_NO_INSN_RESCAN);
5176 regstat_init_n_sets_and_refs ();
5177 regstat_compute_ri ();
5179 /* If we are not optimizing, then this is the only place before
5180 register allocation where dataflow is done. And that is needed
5181 to generate these warnings. */
5182 if (warn_clobbered)
5183 generate_setjmp_warnings ();
5185 /* Determine if the current function is a leaf before running IRA
5186 since this can impact optimizations done by the prologue and
5187 epilogue thus changing register elimination offsets. */
5188 crtl->is_leaf = leaf_function_p ();
5190 if (resize_reg_info () && flag_ira_loop_pressure)
5191 ira_set_pseudo_classes (true, ira_dump_file);
5193 rebuild_p = update_equiv_regs ();
5194 setup_reg_equiv ();
5195 setup_reg_equiv_init ();
5197 if (optimize && rebuild_p)
5199 timevar_push (TV_JUMP);
5200 rebuild_jump_labels (get_insns ());
5201 if (purge_all_dead_edges ())
5202 delete_unreachable_blocks ();
5203 timevar_pop (TV_JUMP);
5206 allocated_reg_info_size = max_reg_num ();
5208 if (delete_trivially_dead_insns (get_insns (), max_reg_num ()))
5209 df_analyze ();
5211 /* It is not worth to do such improvement when we use a simple
5212 allocation because of -O0 usage or because the function is too
5213 big. */
5214 if (ira_conflicts_p)
5215 find_moveable_pseudos ();
5217 max_regno_before_ira = max_reg_num ();
5218 ira_setup_eliminable_regset ();
5220 ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
5221 ira_load_cost = ira_store_cost = ira_shuffle_cost = 0;
5222 ira_move_loops_num = ira_additional_jumps_num = 0;
5224 ira_assert (current_loops == NULL);
5225 if (flag_ira_region == IRA_REGION_ALL || flag_ira_region == IRA_REGION_MIXED)
5226 loop_optimizer_init (AVOID_CFG_MODIFICATIONS | LOOPS_HAVE_RECORDED_EXITS);
5228 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
5229 fprintf (ira_dump_file, "Building IRA IR\n");
5230 loops_p = ira_build ();
5232 ira_assert (ira_conflicts_p || !loops_p);
5234 saved_flag_ira_share_spill_slots = flag_ira_share_spill_slots;
5235 if (too_high_register_pressure_p () || cfun->calls_setjmp)
5236 /* It is just wasting compiler's time to pack spilled pseudos into
5237 stack slots in this case -- prohibit it. We also do this if
5238 there is setjmp call because a variable not modified between
5239 setjmp and longjmp the compiler is required to preserve its
5240 value and sharing slots does not guarantee it. */
5241 flag_ira_share_spill_slots = FALSE;
5243 ira_color ();
5245 ira_max_point_before_emit = ira_max_point;
5247 ira_initiate_emit_data ();
5249 ira_emit (loops_p);
5251 max_regno = max_reg_num ();
5252 if (ira_conflicts_p)
5254 if (! loops_p)
5256 if (! ira_use_lra_p)
5257 ira_initiate_assign ();
5259 else
5261 expand_reg_info ();
5263 if (ira_use_lra_p)
5265 ira_allocno_t a;
5266 ira_allocno_iterator ai;
5268 FOR_EACH_ALLOCNO (a, ai)
5270 int old_regno = ALLOCNO_REGNO (a);
5271 int new_regno = REGNO (ALLOCNO_EMIT_DATA (a)->reg);
5273 ALLOCNO_REGNO (a) = new_regno;
5275 if (old_regno != new_regno)
5276 setup_reg_classes (new_regno, reg_preferred_class (old_regno),
5277 reg_alternate_class (old_regno),
5278 reg_allocno_class (old_regno));
5282 else
5284 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
5285 fprintf (ira_dump_file, "Flattening IR\n");
5286 ira_flattening (max_regno_before_ira, ira_max_point_before_emit);
5288 /* New insns were generated: add notes and recalculate live
5289 info. */
5290 df_analyze ();
5292 /* ??? Rebuild the loop tree, but why? Does the loop tree
5293 change if new insns were generated? Can that be handled
5294 by updating the loop tree incrementally? */
5295 loop_optimizer_finalize ();
5296 free_dominance_info (CDI_DOMINATORS);
5297 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
5298 | LOOPS_HAVE_RECORDED_EXITS);
5300 if (! ira_use_lra_p)
5302 setup_allocno_assignment_flags ();
5303 ira_initiate_assign ();
5304 ira_reassign_conflict_allocnos (max_regno);
5309 ira_finish_emit_data ();
5311 setup_reg_renumber ();
5313 calculate_allocation_cost ();
5315 #ifdef ENABLE_IRA_CHECKING
5316 if (ira_conflicts_p)
5317 check_allocation ();
5318 #endif
5320 if (max_regno != max_regno_before_ira)
5322 regstat_free_n_sets_and_refs ();
5323 regstat_free_ri ();
5324 regstat_init_n_sets_and_refs ();
5325 regstat_compute_ri ();
5328 overall_cost_before = ira_overall_cost;
5329 if (! ira_conflicts_p)
5330 grow_reg_equivs ();
5331 else
5333 fix_reg_equiv_init ();
5335 #ifdef ENABLE_IRA_CHECKING
5336 print_redundant_copies ();
5337 #endif
5338 if (! ira_use_lra_p)
5340 ira_spilled_reg_stack_slots_num = 0;
5341 ira_spilled_reg_stack_slots
5342 = ((struct ira_spilled_reg_stack_slot *)
5343 ira_allocate (max_regno
5344 * sizeof (struct ira_spilled_reg_stack_slot)));
5345 memset (ira_spilled_reg_stack_slots, 0,
5346 max_regno * sizeof (struct ira_spilled_reg_stack_slot));
5349 allocate_initial_values ();
5351 /* See comment for find_moveable_pseudos call. */
5352 if (ira_conflicts_p)
5353 move_unallocated_pseudos ();
5355 /* Restore original values. */
5356 if (lra_simple_p)
5358 flag_caller_saves = saved_flag_caller_saves;
5359 flag_ira_region = saved_flag_ira_region;
5363 static void
5364 do_reload (void)
5366 basic_block bb;
5367 bool need_dce;
5368 unsigned pic_offset_table_regno = INVALID_REGNUM;
5370 if (flag_ira_verbose < 10)
5371 ira_dump_file = dump_file;
5373 /* If pic_offset_table_rtx is a pseudo register, then keep it so
5374 after reload to avoid possible wrong usages of hard reg assigned
5375 to it. */
5376 if (pic_offset_table_rtx
5377 && REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER)
5378 pic_offset_table_regno = REGNO (pic_offset_table_rtx);
5380 timevar_push (TV_RELOAD);
5381 if (ira_use_lra_p)
5383 if (current_loops != NULL)
5385 loop_optimizer_finalize ();
5386 free_dominance_info (CDI_DOMINATORS);
5388 FOR_ALL_BB_FN (bb, cfun)
5389 bb->loop_father = NULL;
5390 current_loops = NULL;
5392 ira_destroy ();
5394 lra (ira_dump_file);
5395 /* ???!!! Move it before lra () when we use ira_reg_equiv in
5396 LRA. */
5397 vec_free (reg_equivs);
5398 reg_equivs = NULL;
5399 need_dce = false;
5401 else
5403 df_set_flags (DF_NO_INSN_RESCAN);
5404 build_insn_chain ();
5406 need_dce = reload (get_insns (), ira_conflicts_p);
5410 timevar_pop (TV_RELOAD);
5412 timevar_push (TV_IRA);
5414 if (ira_conflicts_p && ! ira_use_lra_p)
5416 ira_free (ira_spilled_reg_stack_slots);
5417 ira_finish_assign ();
5420 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL
5421 && overall_cost_before != ira_overall_cost)
5422 fprintf (ira_dump_file, "+++Overall after reload %" PRId64 "\n",
5423 ira_overall_cost);
5425 flag_ira_share_spill_slots = saved_flag_ira_share_spill_slots;
5427 if (! ira_use_lra_p)
5429 ira_destroy ();
5430 if (current_loops != NULL)
5432 loop_optimizer_finalize ();
5433 free_dominance_info (CDI_DOMINATORS);
5435 FOR_ALL_BB_FN (bb, cfun)
5436 bb->loop_father = NULL;
5437 current_loops = NULL;
5439 regstat_free_ri ();
5440 regstat_free_n_sets_and_refs ();
5443 if (optimize)
5444 cleanup_cfg (CLEANUP_EXPENSIVE);
5446 finish_reg_equiv ();
5448 bitmap_obstack_release (&ira_bitmap_obstack);
5449 #ifndef IRA_NO_OBSTACK
5450 obstack_free (&ira_obstack, NULL);
5451 #endif
5453 /* The code after the reload has changed so much that at this point
5454 we might as well just rescan everything. Note that
5455 df_rescan_all_insns is not going to help here because it does not
5456 touch the artificial uses and defs. */
5457 df_finish_pass (true);
5458 df_scan_alloc (NULL);
5459 df_scan_blocks ();
5461 if (optimize > 1)
5463 df_live_add_problem ();
5464 df_live_set_all_dirty ();
5467 if (optimize)
5468 df_analyze ();
5470 if (need_dce && optimize)
5471 run_fast_dce ();
5473 /* Diagnose uses of the hard frame pointer when it is used as a global
5474 register. Often we can get away with letting the user appropriate
5475 the frame pointer, but we should let them know when code generation
5476 makes that impossible. */
5477 if (global_regs[HARD_FRAME_POINTER_REGNUM] && frame_pointer_needed)
5479 tree decl = global_regs_decl[HARD_FRAME_POINTER_REGNUM];
5480 error_at (DECL_SOURCE_LOCATION (current_function_decl),
5481 "frame pointer required, but reserved");
5482 inform (DECL_SOURCE_LOCATION (decl), "for %qD", decl);
5485 if (pic_offset_table_regno != INVALID_REGNUM)
5486 pic_offset_table_rtx = gen_rtx_REG (Pmode, pic_offset_table_regno);
5488 timevar_pop (TV_IRA);
5491 /* Run the integrated register allocator. */
5493 namespace {
5495 const pass_data pass_data_ira =
5497 RTL_PASS, /* type */
5498 "ira", /* name */
5499 OPTGROUP_NONE, /* optinfo_flags */
5500 TV_IRA, /* tv_id */
5501 0, /* properties_required */
5502 0, /* properties_provided */
5503 0, /* properties_destroyed */
5504 0, /* todo_flags_start */
5505 TODO_do_not_ggc_collect, /* todo_flags_finish */
5508 class pass_ira : public rtl_opt_pass
5510 public:
5511 pass_ira (gcc::context *ctxt)
5512 : rtl_opt_pass (pass_data_ira, ctxt)
5515 /* opt_pass methods: */
5516 virtual bool gate (function *)
5518 return !targetm.no_register_allocation;
5520 virtual unsigned int execute (function *)
5522 ira (dump_file);
5523 return 0;
5526 }; // class pass_ira
5528 } // anon namespace
5530 rtl_opt_pass *
5531 make_pass_ira (gcc::context *ctxt)
5533 return new pass_ira (ctxt);
5536 namespace {
5538 const pass_data pass_data_reload =
5540 RTL_PASS, /* type */
5541 "reload", /* name */
5542 OPTGROUP_NONE, /* optinfo_flags */
5543 TV_RELOAD, /* tv_id */
5544 0, /* properties_required */
5545 0, /* properties_provided */
5546 0, /* properties_destroyed */
5547 0, /* todo_flags_start */
5548 0, /* todo_flags_finish */
5551 class pass_reload : public rtl_opt_pass
5553 public:
5554 pass_reload (gcc::context *ctxt)
5555 : rtl_opt_pass (pass_data_reload, ctxt)
5558 /* opt_pass methods: */
5559 virtual bool gate (function *)
5561 return !targetm.no_register_allocation;
5563 virtual unsigned int execute (function *)
5565 do_reload ();
5566 return 0;
5569 }; // class pass_reload
5571 } // anon namespace
5573 rtl_opt_pass *
5574 make_pass_reload (gcc::context *ctxt)
5576 return new pass_reload (ctxt);