2015-05-22 Pascal Obry <obry@adacore.com>
[official-gcc.git] / gcc / ira.c
blob47b57252bb6a73cc722b2423fa5cdffd7b9cbcd7
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 "tm.h"
370 #include "regs.h"
371 #include "hash-set.h"
372 #include "machmode.h"
373 #include "vec.h"
374 #include "double-int.h"
375 #include "input.h"
376 #include "alias.h"
377 #include "symtab.h"
378 #include "wide-int.h"
379 #include "inchash.h"
380 #include "tree.h"
381 #include "rtl.h"
382 #include "tm_p.h"
383 #include "target.h"
384 #include "flags.h"
385 #include "obstack.h"
386 #include "bitmap.h"
387 #include "hard-reg-set.h"
388 #include "predict.h"
389 #include "function.h"
390 #include "dominance.h"
391 #include "cfg.h"
392 #include "cfgrtl.h"
393 #include "cfgbuild.h"
394 #include "cfgcleanup.h"
395 #include "basic-block.h"
396 #include "df.h"
397 #include "hashtab.h"
398 #include "statistics.h"
399 #include "real.h"
400 #include "fixed-value.h"
401 #include "insn-config.h"
402 #include "expmed.h"
403 #include "dojump.h"
404 #include "explow.h"
405 #include "calls.h"
406 #include "emit-rtl.h"
407 #include "varasm.h"
408 #include "stmt.h"
409 #include "expr.h"
410 #include "recog.h"
411 #include "params.h"
412 #include "tree-pass.h"
413 #include "output.h"
414 #include "except.h"
415 #include "reload.h"
416 #include "diagnostic-core.h"
417 #include "ggc.h"
418 #include "ira-int.h"
419 #include "lra.h"
420 #include "dce.h"
421 #include "dbgcnt.h"
422 #include "rtl-iter.h"
423 #include "shrink-wrap.h"
425 struct target_ira default_target_ira;
426 struct target_ira_int default_target_ira_int;
427 #if SWITCHABLE_TARGET
428 struct target_ira *this_target_ira = &default_target_ira;
429 struct target_ira_int *this_target_ira_int = &default_target_ira_int;
430 #endif
432 /* A modified value of flag `-fira-verbose' used internally. */
433 int internal_flag_ira_verbose;
435 /* Dump file of the allocator if it is not NULL. */
436 FILE *ira_dump_file;
438 /* The number of elements in the following array. */
439 int ira_spilled_reg_stack_slots_num;
441 /* The following array contains info about spilled pseudo-registers
442 stack slots used in current function so far. */
443 struct ira_spilled_reg_stack_slot *ira_spilled_reg_stack_slots;
445 /* Correspondingly overall cost of the allocation, overall cost before
446 reload, cost of the allocnos assigned to hard-registers, cost of
447 the allocnos assigned to memory, cost of loads, stores and register
448 move insns generated for pseudo-register live range splitting (see
449 ira-emit.c). */
450 int64_t ira_overall_cost, overall_cost_before;
451 int64_t ira_reg_cost, ira_mem_cost;
452 int64_t ira_load_cost, ira_store_cost, ira_shuffle_cost;
453 int ira_move_loops_num, ira_additional_jumps_num;
455 /* All registers that can be eliminated. */
457 HARD_REG_SET eliminable_regset;
459 /* Value of max_reg_num () before IRA work start. This value helps
460 us to recognize a situation when new pseudos were created during
461 IRA work. */
462 static int max_regno_before_ira;
464 /* Temporary hard reg set used for a different calculation. */
465 static HARD_REG_SET temp_hard_regset;
467 #define last_mode_for_init_move_cost \
468 (this_target_ira_int->x_last_mode_for_init_move_cost)
471 /* The function sets up the map IRA_REG_MODE_HARD_REGSET. */
472 static void
473 setup_reg_mode_hard_regset (void)
475 int i, m, hard_regno;
477 for (m = 0; m < NUM_MACHINE_MODES; m++)
478 for (hard_regno = 0; hard_regno < FIRST_PSEUDO_REGISTER; hard_regno++)
480 CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset[hard_regno][m]);
481 for (i = hard_regno_nregs[hard_regno][m] - 1; i >= 0; i--)
482 if (hard_regno + i < FIRST_PSEUDO_REGISTER)
483 SET_HARD_REG_BIT (ira_reg_mode_hard_regset[hard_regno][m],
484 hard_regno + i);
489 #define no_unit_alloc_regs \
490 (this_target_ira_int->x_no_unit_alloc_regs)
492 /* The function sets up the three arrays declared above. */
493 static void
494 setup_class_hard_regs (void)
496 int cl, i, hard_regno, n;
497 HARD_REG_SET processed_hard_reg_set;
499 ira_assert (SHRT_MAX >= FIRST_PSEUDO_REGISTER);
500 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
502 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
503 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
504 CLEAR_HARD_REG_SET (processed_hard_reg_set);
505 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
507 ira_non_ordered_class_hard_regs[cl][i] = -1;
508 ira_class_hard_reg_index[cl][i] = -1;
510 for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
512 #ifdef REG_ALLOC_ORDER
513 hard_regno = reg_alloc_order[i];
514 #else
515 hard_regno = i;
516 #endif
517 if (TEST_HARD_REG_BIT (processed_hard_reg_set, hard_regno))
518 continue;
519 SET_HARD_REG_BIT (processed_hard_reg_set, hard_regno);
520 if (! TEST_HARD_REG_BIT (temp_hard_regset, hard_regno))
521 ira_class_hard_reg_index[cl][hard_regno] = -1;
522 else
524 ira_class_hard_reg_index[cl][hard_regno] = n;
525 ira_class_hard_regs[cl][n++] = hard_regno;
528 ira_class_hard_regs_num[cl] = n;
529 for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
530 if (TEST_HARD_REG_BIT (temp_hard_regset, i))
531 ira_non_ordered_class_hard_regs[cl][n++] = i;
532 ira_assert (ira_class_hard_regs_num[cl] == n);
536 /* Set up global variables defining info about hard registers for the
537 allocation. These depend on USE_HARD_FRAME_P whose TRUE value means
538 that we can use the hard frame pointer for the allocation. */
539 static void
540 setup_alloc_regs (bool use_hard_frame_p)
542 #ifdef ADJUST_REG_ALLOC_ORDER
543 ADJUST_REG_ALLOC_ORDER;
544 #endif
545 COPY_HARD_REG_SET (no_unit_alloc_regs, fixed_reg_set);
546 if (! use_hard_frame_p)
547 SET_HARD_REG_BIT (no_unit_alloc_regs, HARD_FRAME_POINTER_REGNUM);
548 setup_class_hard_regs ();
553 #define alloc_reg_class_subclasses \
554 (this_target_ira_int->x_alloc_reg_class_subclasses)
556 /* Initialize the table of subclasses of each reg class. */
557 static void
558 setup_reg_subclasses (void)
560 int i, j;
561 HARD_REG_SET temp_hard_regset2;
563 for (i = 0; i < N_REG_CLASSES; i++)
564 for (j = 0; j < N_REG_CLASSES; j++)
565 alloc_reg_class_subclasses[i][j] = LIM_REG_CLASSES;
567 for (i = 0; i < N_REG_CLASSES; i++)
569 if (i == (int) NO_REGS)
570 continue;
572 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
573 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
574 if (hard_reg_set_empty_p (temp_hard_regset))
575 continue;
576 for (j = 0; j < N_REG_CLASSES; j++)
577 if (i != j)
579 enum reg_class *p;
581 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[j]);
582 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
583 if (! hard_reg_set_subset_p (temp_hard_regset,
584 temp_hard_regset2))
585 continue;
586 p = &alloc_reg_class_subclasses[j][0];
587 while (*p != LIM_REG_CLASSES) p++;
588 *p = (enum reg_class) i;
595 /* Set up IRA_MEMORY_MOVE_COST and IRA_MAX_MEMORY_MOVE_COST. */
596 static void
597 setup_class_subset_and_memory_move_costs (void)
599 int cl, cl2, mode, cost;
600 HARD_REG_SET temp_hard_regset2;
602 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
603 ira_memory_move_cost[mode][NO_REGS][0]
604 = ira_memory_move_cost[mode][NO_REGS][1] = SHRT_MAX;
605 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
607 if (cl != (int) NO_REGS)
608 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
610 ira_max_memory_move_cost[mode][cl][0]
611 = ira_memory_move_cost[mode][cl][0]
612 = memory_move_cost ((machine_mode) mode,
613 (reg_class_t) cl, false);
614 ira_max_memory_move_cost[mode][cl][1]
615 = ira_memory_move_cost[mode][cl][1]
616 = memory_move_cost ((machine_mode) mode,
617 (reg_class_t) cl, true);
618 /* Costs for NO_REGS are used in cost calculation on the
619 1st pass when the preferred register classes are not
620 known yet. In this case we take the best scenario. */
621 if (ira_memory_move_cost[mode][NO_REGS][0]
622 > ira_memory_move_cost[mode][cl][0])
623 ira_max_memory_move_cost[mode][NO_REGS][0]
624 = ira_memory_move_cost[mode][NO_REGS][0]
625 = ira_memory_move_cost[mode][cl][0];
626 if (ira_memory_move_cost[mode][NO_REGS][1]
627 > ira_memory_move_cost[mode][cl][1])
628 ira_max_memory_move_cost[mode][NO_REGS][1]
629 = ira_memory_move_cost[mode][NO_REGS][1]
630 = ira_memory_move_cost[mode][cl][1];
633 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
634 for (cl2 = (int) N_REG_CLASSES - 1; cl2 >= 0; cl2--)
636 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
637 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
638 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]);
639 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
640 ira_class_subset_p[cl][cl2]
641 = hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2);
642 if (! hard_reg_set_empty_p (temp_hard_regset2)
643 && hard_reg_set_subset_p (reg_class_contents[cl2],
644 reg_class_contents[cl]))
645 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
647 cost = ira_memory_move_cost[mode][cl2][0];
648 if (cost > ira_max_memory_move_cost[mode][cl][0])
649 ira_max_memory_move_cost[mode][cl][0] = cost;
650 cost = ira_memory_move_cost[mode][cl2][1];
651 if (cost > ira_max_memory_move_cost[mode][cl][1])
652 ira_max_memory_move_cost[mode][cl][1] = cost;
655 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
656 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
658 ira_memory_move_cost[mode][cl][0]
659 = ira_max_memory_move_cost[mode][cl][0];
660 ira_memory_move_cost[mode][cl][1]
661 = ira_max_memory_move_cost[mode][cl][1];
663 setup_reg_subclasses ();
668 /* Define the following macro if allocation through malloc if
669 preferable. */
670 #define IRA_NO_OBSTACK
672 #ifndef IRA_NO_OBSTACK
673 /* Obstack used for storing all dynamic data (except bitmaps) of the
674 IRA. */
675 static struct obstack ira_obstack;
676 #endif
678 /* Obstack used for storing all bitmaps of the IRA. */
679 static struct bitmap_obstack ira_bitmap_obstack;
681 /* Allocate memory of size LEN for IRA data. */
682 void *
683 ira_allocate (size_t len)
685 void *res;
687 #ifndef IRA_NO_OBSTACK
688 res = obstack_alloc (&ira_obstack, len);
689 #else
690 res = xmalloc (len);
691 #endif
692 return res;
695 /* Free memory ADDR allocated for IRA data. */
696 void
697 ira_free (void *addr ATTRIBUTE_UNUSED)
699 #ifndef IRA_NO_OBSTACK
700 /* do nothing */
701 #else
702 free (addr);
703 #endif
707 /* Allocate and returns bitmap for IRA. */
708 bitmap
709 ira_allocate_bitmap (void)
711 return BITMAP_ALLOC (&ira_bitmap_obstack);
714 /* Free bitmap B allocated for IRA. */
715 void
716 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED)
718 /* do nothing */
723 /* Output information about allocation of all allocnos (except for
724 caps) into file F. */
725 void
726 ira_print_disposition (FILE *f)
728 int i, n, max_regno;
729 ira_allocno_t a;
730 basic_block bb;
732 fprintf (f, "Disposition:");
733 max_regno = max_reg_num ();
734 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
735 for (a = ira_regno_allocno_map[i];
736 a != NULL;
737 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
739 if (n % 4 == 0)
740 fprintf (f, "\n");
741 n++;
742 fprintf (f, " %4d:r%-4d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
743 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
744 fprintf (f, "b%-3d", bb->index);
745 else
746 fprintf (f, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
747 if (ALLOCNO_HARD_REGNO (a) >= 0)
748 fprintf (f, " %3d", ALLOCNO_HARD_REGNO (a));
749 else
750 fprintf (f, " mem");
752 fprintf (f, "\n");
755 /* Outputs information about allocation of all allocnos into
756 stderr. */
757 void
758 ira_debug_disposition (void)
760 ira_print_disposition (stderr);
765 /* Set up ira_stack_reg_pressure_class which is the biggest pressure
766 register class containing stack registers or NO_REGS if there are
767 no stack registers. To find this class, we iterate through all
768 register pressure classes and choose the first register pressure
769 class containing all the stack registers and having the biggest
770 size. */
771 static void
772 setup_stack_reg_pressure_class (void)
774 ira_stack_reg_pressure_class = NO_REGS;
775 #ifdef STACK_REGS
777 int i, best, size;
778 enum reg_class cl;
779 HARD_REG_SET temp_hard_regset2;
781 CLEAR_HARD_REG_SET (temp_hard_regset);
782 for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
783 SET_HARD_REG_BIT (temp_hard_regset, i);
784 best = 0;
785 for (i = 0; i < ira_pressure_classes_num; i++)
787 cl = ira_pressure_classes[i];
788 COPY_HARD_REG_SET (temp_hard_regset2, temp_hard_regset);
789 AND_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
790 size = hard_reg_set_size (temp_hard_regset2);
791 if (best < size)
793 best = size;
794 ira_stack_reg_pressure_class = cl;
798 #endif
801 /* Find pressure classes which are register classes for which we
802 calculate register pressure in IRA, register pressure sensitive
803 insn scheduling, and register pressure sensitive loop invariant
804 motion.
806 To make register pressure calculation easy, we always use
807 non-intersected register pressure classes. A move of hard
808 registers from one register pressure class is not more expensive
809 than load and store of the hard registers. Most likely an allocno
810 class will be a subset of a register pressure class and in many
811 cases a register pressure class. That makes usage of register
812 pressure classes a good approximation to find a high register
813 pressure. */
814 static void
815 setup_pressure_classes (void)
817 int cost, i, n, curr;
818 int cl, cl2;
819 enum reg_class pressure_classes[N_REG_CLASSES];
820 int m;
821 HARD_REG_SET temp_hard_regset2;
822 bool insert_p;
824 n = 0;
825 for (cl = 0; cl < N_REG_CLASSES; cl++)
827 if (ira_class_hard_regs_num[cl] == 0)
828 continue;
829 if (ira_class_hard_regs_num[cl] != 1
830 /* A register class without subclasses may contain a few
831 hard registers and movement between them is costly
832 (e.g. SPARC FPCC registers). We still should consider it
833 as a candidate for a pressure class. */
834 && alloc_reg_class_subclasses[cl][0] < cl)
836 /* Check that the moves between any hard registers of the
837 current class are not more expensive for a legal mode
838 than load/store of the hard registers of the current
839 class. Such class is a potential candidate to be a
840 register pressure class. */
841 for (m = 0; m < NUM_MACHINE_MODES; m++)
843 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
844 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
845 AND_COMPL_HARD_REG_SET (temp_hard_regset,
846 ira_prohibited_class_mode_regs[cl][m]);
847 if (hard_reg_set_empty_p (temp_hard_regset))
848 continue;
849 ira_init_register_move_cost_if_necessary ((machine_mode) m);
850 cost = ira_register_move_cost[m][cl][cl];
851 if (cost <= ira_max_memory_move_cost[m][cl][1]
852 || cost <= ira_max_memory_move_cost[m][cl][0])
853 break;
855 if (m >= NUM_MACHINE_MODES)
856 continue;
858 curr = 0;
859 insert_p = true;
860 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
861 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
862 /* Remove so far added pressure classes which are subset of the
863 current candidate class. Prefer GENERAL_REGS as a pressure
864 register class to another class containing the same
865 allocatable hard registers. We do this because machine
866 dependent cost hooks might give wrong costs for the latter
867 class but always give the right cost for the former class
868 (GENERAL_REGS). */
869 for (i = 0; i < n; i++)
871 cl2 = pressure_classes[i];
872 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]);
873 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
874 if (hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2)
875 && (! hard_reg_set_equal_p (temp_hard_regset, temp_hard_regset2)
876 || cl2 == (int) GENERAL_REGS))
878 pressure_classes[curr++] = (enum reg_class) cl2;
879 insert_p = false;
880 continue;
882 if (hard_reg_set_subset_p (temp_hard_regset2, temp_hard_regset)
883 && (! hard_reg_set_equal_p (temp_hard_regset2, temp_hard_regset)
884 || cl == (int) GENERAL_REGS))
885 continue;
886 if (hard_reg_set_equal_p (temp_hard_regset2, temp_hard_regset))
887 insert_p = false;
888 pressure_classes[curr++] = (enum reg_class) cl2;
890 /* If the current candidate is a subset of a so far added
891 pressure class, don't add it to the list of the pressure
892 classes. */
893 if (insert_p)
894 pressure_classes[curr++] = (enum reg_class) cl;
895 n = curr;
897 #ifdef ENABLE_IRA_CHECKING
899 HARD_REG_SET ignore_hard_regs;
901 /* Check pressure classes correctness: here we check that hard
902 registers from all register pressure classes contains all hard
903 registers available for the allocation. */
904 CLEAR_HARD_REG_SET (temp_hard_regset);
905 CLEAR_HARD_REG_SET (temp_hard_regset2);
906 COPY_HARD_REG_SET (ignore_hard_regs, no_unit_alloc_regs);
907 for (cl = 0; cl < LIM_REG_CLASSES; cl++)
909 /* For some targets (like MIPS with MD_REGS), there are some
910 classes with hard registers available for allocation but
911 not able to hold value of any mode. */
912 for (m = 0; m < NUM_MACHINE_MODES; m++)
913 if (contains_reg_of_mode[cl][m])
914 break;
915 if (m >= NUM_MACHINE_MODES)
917 IOR_HARD_REG_SET (ignore_hard_regs, reg_class_contents[cl]);
918 continue;
920 for (i = 0; i < n; i++)
921 if ((int) pressure_classes[i] == cl)
922 break;
923 IOR_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
924 if (i < n)
925 IOR_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
927 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
928 /* Some targets (like SPARC with ICC reg) have allocatable regs
929 for which no reg class is defined. */
930 if (REGNO_REG_CLASS (i) == NO_REGS)
931 SET_HARD_REG_BIT (ignore_hard_regs, i);
932 AND_COMPL_HARD_REG_SET (temp_hard_regset, ignore_hard_regs);
933 AND_COMPL_HARD_REG_SET (temp_hard_regset2, ignore_hard_regs);
934 ira_assert (hard_reg_set_subset_p (temp_hard_regset2, temp_hard_regset));
936 #endif
937 ira_pressure_classes_num = 0;
938 for (i = 0; i < n; i++)
940 cl = (int) pressure_classes[i];
941 ira_reg_pressure_class_p[cl] = true;
942 ira_pressure_classes[ira_pressure_classes_num++] = (enum reg_class) cl;
944 setup_stack_reg_pressure_class ();
947 /* Set up IRA_UNIFORM_CLASS_P. Uniform class is a register class
948 whose register move cost between any registers of the class is the
949 same as for all its subclasses. We use the data to speed up the
950 2nd pass of calculations of allocno costs. */
951 static void
952 setup_uniform_class_p (void)
954 int i, cl, cl2, m;
956 for (cl = 0; cl < N_REG_CLASSES; cl++)
958 ira_uniform_class_p[cl] = false;
959 if (ira_class_hard_regs_num[cl] == 0)
960 continue;
961 /* We can not use alloc_reg_class_subclasses here because move
962 cost hooks does not take into account that some registers are
963 unavailable for the subtarget. E.g. for i686, INT_SSE_REGS
964 is element of alloc_reg_class_subclasses for GENERAL_REGS
965 because SSE regs are unavailable. */
966 for (i = 0; (cl2 = reg_class_subclasses[cl][i]) != LIM_REG_CLASSES; i++)
968 if (ira_class_hard_regs_num[cl2] == 0)
969 continue;
970 for (m = 0; m < NUM_MACHINE_MODES; m++)
971 if (contains_reg_of_mode[cl][m] && contains_reg_of_mode[cl2][m])
973 ira_init_register_move_cost_if_necessary ((machine_mode) m);
974 if (ira_register_move_cost[m][cl][cl]
975 != ira_register_move_cost[m][cl2][cl2])
976 break;
978 if (m < NUM_MACHINE_MODES)
979 break;
981 if (cl2 == LIM_REG_CLASSES)
982 ira_uniform_class_p[cl] = true;
986 /* Set up IRA_ALLOCNO_CLASSES, IRA_ALLOCNO_CLASSES_NUM,
987 IRA_IMPORTANT_CLASSES, and IRA_IMPORTANT_CLASSES_NUM.
989 Target may have many subtargets and not all target hard registers can
990 be used for allocation, e.g. x86 port in 32-bit mode can not use
991 hard registers introduced in x86-64 like r8-r15). Some classes
992 might have the same allocatable hard registers, e.g. INDEX_REGS
993 and GENERAL_REGS in x86 port in 32-bit mode. To decrease different
994 calculations efforts we introduce allocno classes which contain
995 unique non-empty sets of allocatable hard-registers.
997 Pseudo class cost calculation in ira-costs.c is very expensive.
998 Therefore we are trying to decrease number of classes involved in
999 such calculation. Register classes used in the cost calculation
1000 are called important classes. They are allocno classes and other
1001 non-empty classes whose allocatable hard register sets are inside
1002 of an allocno class hard register set. From the first sight, it
1003 looks like that they are just allocno classes. It is not true. In
1004 example of x86-port in 32-bit mode, allocno classes will contain
1005 GENERAL_REGS but not LEGACY_REGS (because allocatable hard
1006 registers are the same for the both classes). The important
1007 classes will contain GENERAL_REGS and LEGACY_REGS. It is done
1008 because a machine description insn constraint may refers for
1009 LEGACY_REGS and code in ira-costs.c is mostly base on investigation
1010 of the insn constraints. */
1011 static void
1012 setup_allocno_and_important_classes (void)
1014 int i, j, n, cl;
1015 bool set_p;
1016 HARD_REG_SET temp_hard_regset2;
1017 static enum reg_class classes[LIM_REG_CLASSES + 1];
1019 n = 0;
1020 /* Collect classes which contain unique sets of allocatable hard
1021 registers. Prefer GENERAL_REGS to other classes containing the
1022 same set of hard registers. */
1023 for (i = 0; i < LIM_REG_CLASSES; i++)
1025 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
1026 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1027 for (j = 0; j < n; j++)
1029 cl = classes[j];
1030 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
1031 AND_COMPL_HARD_REG_SET (temp_hard_regset2,
1032 no_unit_alloc_regs);
1033 if (hard_reg_set_equal_p (temp_hard_regset,
1034 temp_hard_regset2))
1035 break;
1037 if (j >= n)
1038 classes[n++] = (enum reg_class) i;
1039 else if (i == GENERAL_REGS)
1040 /* Prefer general regs. For i386 example, it means that
1041 we prefer GENERAL_REGS over INDEX_REGS or LEGACY_REGS
1042 (all of them consists of the same available hard
1043 registers). */
1044 classes[j] = (enum reg_class) i;
1046 classes[n] = LIM_REG_CLASSES;
1048 /* Set up classes which can be used for allocnos as classes
1049 containing non-empty unique sets of allocatable hard
1050 registers. */
1051 ira_allocno_classes_num = 0;
1052 for (i = 0; (cl = classes[i]) != LIM_REG_CLASSES; i++)
1053 if (ira_class_hard_regs_num[cl] > 0)
1054 ira_allocno_classes[ira_allocno_classes_num++] = (enum reg_class) cl;
1055 ira_important_classes_num = 0;
1056 /* Add non-allocno classes containing to non-empty set of
1057 allocatable hard regs. */
1058 for (cl = 0; cl < N_REG_CLASSES; cl++)
1059 if (ira_class_hard_regs_num[cl] > 0)
1061 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
1062 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1063 set_p = false;
1064 for (j = 0; j < ira_allocno_classes_num; j++)
1066 COPY_HARD_REG_SET (temp_hard_regset2,
1067 reg_class_contents[ira_allocno_classes[j]]);
1068 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
1069 if ((enum reg_class) cl == ira_allocno_classes[j])
1070 break;
1071 else if (hard_reg_set_subset_p (temp_hard_regset,
1072 temp_hard_regset2))
1073 set_p = true;
1075 if (set_p && j >= ira_allocno_classes_num)
1076 ira_important_classes[ira_important_classes_num++]
1077 = (enum reg_class) cl;
1079 /* Now add allocno classes to the important classes. */
1080 for (j = 0; j < ira_allocno_classes_num; j++)
1081 ira_important_classes[ira_important_classes_num++]
1082 = ira_allocno_classes[j];
1083 for (cl = 0; cl < N_REG_CLASSES; cl++)
1085 ira_reg_allocno_class_p[cl] = false;
1086 ira_reg_pressure_class_p[cl] = false;
1088 for (j = 0; j < ira_allocno_classes_num; j++)
1089 ira_reg_allocno_class_p[ira_allocno_classes[j]] = true;
1090 setup_pressure_classes ();
1091 setup_uniform_class_p ();
1094 /* Setup translation in CLASS_TRANSLATE of all classes into a class
1095 given by array CLASSES of length CLASSES_NUM. The function is used
1096 make translation any reg class to an allocno class or to an
1097 pressure class. This translation is necessary for some
1098 calculations when we can use only allocno or pressure classes and
1099 such translation represents an approximate representation of all
1100 classes.
1102 The translation in case when allocatable hard register set of a
1103 given class is subset of allocatable hard register set of a class
1104 in CLASSES is pretty simple. We use smallest classes from CLASSES
1105 containing a given class. If allocatable hard register set of a
1106 given class is not a subset of any corresponding set of a class
1107 from CLASSES, we use the cheapest (with load/store point of view)
1108 class from CLASSES whose set intersects with given class set. */
1109 static void
1110 setup_class_translate_array (enum reg_class *class_translate,
1111 int classes_num, enum reg_class *classes)
1113 int cl, mode;
1114 enum reg_class aclass, best_class, *cl_ptr;
1115 int i, cost, min_cost, best_cost;
1117 for (cl = 0; cl < N_REG_CLASSES; cl++)
1118 class_translate[cl] = NO_REGS;
1120 for (i = 0; i < classes_num; i++)
1122 aclass = classes[i];
1123 for (cl_ptr = &alloc_reg_class_subclasses[aclass][0];
1124 (cl = *cl_ptr) != LIM_REG_CLASSES;
1125 cl_ptr++)
1126 if (class_translate[cl] == NO_REGS)
1127 class_translate[cl] = aclass;
1128 class_translate[aclass] = aclass;
1130 /* For classes which are not fully covered by one of given classes
1131 (in other words covered by more one given class), use the
1132 cheapest class. */
1133 for (cl = 0; cl < N_REG_CLASSES; cl++)
1135 if (cl == NO_REGS || class_translate[cl] != NO_REGS)
1136 continue;
1137 best_class = NO_REGS;
1138 best_cost = INT_MAX;
1139 for (i = 0; i < classes_num; i++)
1141 aclass = classes[i];
1142 COPY_HARD_REG_SET (temp_hard_regset,
1143 reg_class_contents[aclass]);
1144 AND_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
1145 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1146 if (! hard_reg_set_empty_p (temp_hard_regset))
1148 min_cost = INT_MAX;
1149 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1151 cost = (ira_memory_move_cost[mode][aclass][0]
1152 + ira_memory_move_cost[mode][aclass][1]);
1153 if (min_cost > cost)
1154 min_cost = cost;
1156 if (best_class == NO_REGS || best_cost > min_cost)
1158 best_class = aclass;
1159 best_cost = min_cost;
1163 class_translate[cl] = best_class;
1167 /* Set up array IRA_ALLOCNO_CLASS_TRANSLATE and
1168 IRA_PRESSURE_CLASS_TRANSLATE. */
1169 static void
1170 setup_class_translate (void)
1172 setup_class_translate_array (ira_allocno_class_translate,
1173 ira_allocno_classes_num, ira_allocno_classes);
1174 setup_class_translate_array (ira_pressure_class_translate,
1175 ira_pressure_classes_num, ira_pressure_classes);
1178 /* Order numbers of allocno classes in original target allocno class
1179 array, -1 for non-allocno classes. */
1180 static int allocno_class_order[N_REG_CLASSES];
1182 /* The function used to sort the important classes. */
1183 static int
1184 comp_reg_classes_func (const void *v1p, const void *v2p)
1186 enum reg_class cl1 = *(const enum reg_class *) v1p;
1187 enum reg_class cl2 = *(const enum reg_class *) v2p;
1188 enum reg_class tcl1, tcl2;
1189 int diff;
1191 tcl1 = ira_allocno_class_translate[cl1];
1192 tcl2 = ira_allocno_class_translate[cl2];
1193 if (tcl1 != NO_REGS && tcl2 != NO_REGS
1194 && (diff = allocno_class_order[tcl1] - allocno_class_order[tcl2]) != 0)
1195 return diff;
1196 return (int) cl1 - (int) cl2;
1199 /* For correct work of function setup_reg_class_relation we need to
1200 reorder important classes according to the order of their allocno
1201 classes. It places important classes containing the same
1202 allocatable hard register set adjacent to each other and allocno
1203 class with the allocatable hard register set right after the other
1204 important classes with the same set.
1206 In example from comments of function
1207 setup_allocno_and_important_classes, it places LEGACY_REGS and
1208 GENERAL_REGS close to each other and GENERAL_REGS is after
1209 LEGACY_REGS. */
1210 static void
1211 reorder_important_classes (void)
1213 int i;
1215 for (i = 0; i < N_REG_CLASSES; i++)
1216 allocno_class_order[i] = -1;
1217 for (i = 0; i < ira_allocno_classes_num; i++)
1218 allocno_class_order[ira_allocno_classes[i]] = i;
1219 qsort (ira_important_classes, ira_important_classes_num,
1220 sizeof (enum reg_class), comp_reg_classes_func);
1221 for (i = 0; i < ira_important_classes_num; i++)
1222 ira_important_class_nums[ira_important_classes[i]] = i;
1225 /* Set up IRA_REG_CLASS_SUBUNION, IRA_REG_CLASS_SUPERUNION,
1226 IRA_REG_CLASS_SUPER_CLASSES, IRA_REG_CLASSES_INTERSECT, and
1227 IRA_REG_CLASSES_INTERSECT_P. For the meaning of the relations,
1228 please see corresponding comments in ira-int.h. */
1229 static void
1230 setup_reg_class_relations (void)
1232 int i, cl1, cl2, cl3;
1233 HARD_REG_SET intersection_set, union_set, temp_set2;
1234 bool important_class_p[N_REG_CLASSES];
1236 memset (important_class_p, 0, sizeof (important_class_p));
1237 for (i = 0; i < ira_important_classes_num; i++)
1238 important_class_p[ira_important_classes[i]] = true;
1239 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1241 ira_reg_class_super_classes[cl1][0] = LIM_REG_CLASSES;
1242 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1244 ira_reg_classes_intersect_p[cl1][cl2] = false;
1245 ira_reg_class_intersect[cl1][cl2] = NO_REGS;
1246 ira_reg_class_subset[cl1][cl2] = NO_REGS;
1247 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl1]);
1248 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1249 COPY_HARD_REG_SET (temp_set2, reg_class_contents[cl2]);
1250 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1251 if (hard_reg_set_empty_p (temp_hard_regset)
1252 && hard_reg_set_empty_p (temp_set2))
1254 /* The both classes have no allocatable hard registers
1255 -- take all class hard registers into account and use
1256 reg_class_subunion and reg_class_superunion. */
1257 for (i = 0;; i++)
1259 cl3 = reg_class_subclasses[cl1][i];
1260 if (cl3 == LIM_REG_CLASSES)
1261 break;
1262 if (reg_class_subset_p (ira_reg_class_intersect[cl1][cl2],
1263 (enum reg_class) cl3))
1264 ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
1266 ira_reg_class_subunion[cl1][cl2] = reg_class_subunion[cl1][cl2];
1267 ira_reg_class_superunion[cl1][cl2] = reg_class_superunion[cl1][cl2];
1268 continue;
1270 ira_reg_classes_intersect_p[cl1][cl2]
1271 = hard_reg_set_intersect_p (temp_hard_regset, temp_set2);
1272 if (important_class_p[cl1] && important_class_p[cl2]
1273 && hard_reg_set_subset_p (temp_hard_regset, temp_set2))
1275 /* CL1 and CL2 are important classes and CL1 allocatable
1276 hard register set is inside of CL2 allocatable hard
1277 registers -- make CL1 a superset of CL2. */
1278 enum reg_class *p;
1280 p = &ira_reg_class_super_classes[cl1][0];
1281 while (*p != LIM_REG_CLASSES)
1282 p++;
1283 *p++ = (enum reg_class) cl2;
1284 *p = LIM_REG_CLASSES;
1286 ira_reg_class_subunion[cl1][cl2] = NO_REGS;
1287 ira_reg_class_superunion[cl1][cl2] = NO_REGS;
1288 COPY_HARD_REG_SET (intersection_set, reg_class_contents[cl1]);
1289 AND_HARD_REG_SET (intersection_set, reg_class_contents[cl2]);
1290 AND_COMPL_HARD_REG_SET (intersection_set, no_unit_alloc_regs);
1291 COPY_HARD_REG_SET (union_set, reg_class_contents[cl1]);
1292 IOR_HARD_REG_SET (union_set, reg_class_contents[cl2]);
1293 AND_COMPL_HARD_REG_SET (union_set, no_unit_alloc_regs);
1294 for (cl3 = 0; cl3 < N_REG_CLASSES; cl3++)
1296 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl3]);
1297 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1298 if (hard_reg_set_subset_p (temp_hard_regset, intersection_set))
1300 /* CL3 allocatable hard register set is inside of
1301 intersection of allocatable hard register sets
1302 of CL1 and CL2. */
1303 if (important_class_p[cl3])
1305 COPY_HARD_REG_SET
1306 (temp_set2,
1307 reg_class_contents
1308 [(int) ira_reg_class_intersect[cl1][cl2]]);
1309 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1310 if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1311 /* If the allocatable hard register sets are
1312 the same, prefer GENERAL_REGS or the
1313 smallest class for debugging
1314 purposes. */
1315 || (hard_reg_set_equal_p (temp_hard_regset, temp_set2)
1316 && (cl3 == GENERAL_REGS
1317 || ((ira_reg_class_intersect[cl1][cl2]
1318 != GENERAL_REGS)
1319 && hard_reg_set_subset_p
1320 (reg_class_contents[cl3],
1321 reg_class_contents
1322 [(int)
1323 ira_reg_class_intersect[cl1][cl2]])))))
1324 ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
1326 COPY_HARD_REG_SET
1327 (temp_set2,
1328 reg_class_contents[(int) ira_reg_class_subset[cl1][cl2]]);
1329 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1330 if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1331 /* Ignore unavailable hard registers and prefer
1332 smallest class for debugging purposes. */
1333 || (hard_reg_set_equal_p (temp_hard_regset, temp_set2)
1334 && hard_reg_set_subset_p
1335 (reg_class_contents[cl3],
1336 reg_class_contents
1337 [(int) ira_reg_class_subset[cl1][cl2]])))
1338 ira_reg_class_subset[cl1][cl2] = (enum reg_class) cl3;
1340 if (important_class_p[cl3]
1341 && hard_reg_set_subset_p (temp_hard_regset, union_set))
1343 /* CL3 allocatable hard register set is inside of
1344 union of allocatable hard register sets of CL1
1345 and CL2. */
1346 COPY_HARD_REG_SET
1347 (temp_set2,
1348 reg_class_contents[(int) ira_reg_class_subunion[cl1][cl2]]);
1349 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1350 if (ira_reg_class_subunion[cl1][cl2] == NO_REGS
1351 || (hard_reg_set_subset_p (temp_set2, temp_hard_regset)
1353 && (! hard_reg_set_equal_p (temp_set2,
1354 temp_hard_regset)
1355 || cl3 == GENERAL_REGS
1356 /* If the allocatable hard register sets are the
1357 same, prefer GENERAL_REGS or the smallest
1358 class for debugging purposes. */
1359 || (ira_reg_class_subunion[cl1][cl2] != GENERAL_REGS
1360 && hard_reg_set_subset_p
1361 (reg_class_contents[cl3],
1362 reg_class_contents
1363 [(int) ira_reg_class_subunion[cl1][cl2]])))))
1364 ira_reg_class_subunion[cl1][cl2] = (enum reg_class) cl3;
1366 if (hard_reg_set_subset_p (union_set, temp_hard_regset))
1368 /* CL3 allocatable hard register set contains union
1369 of allocatable hard register sets of CL1 and
1370 CL2. */
1371 COPY_HARD_REG_SET
1372 (temp_set2,
1373 reg_class_contents[(int) ira_reg_class_superunion[cl1][cl2]]);
1374 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1375 if (ira_reg_class_superunion[cl1][cl2] == NO_REGS
1376 || (hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1378 && (! hard_reg_set_equal_p (temp_set2,
1379 temp_hard_regset)
1380 || cl3 == GENERAL_REGS
1381 /* If the allocatable hard register sets are the
1382 same, prefer GENERAL_REGS or the smallest
1383 class for debugging purposes. */
1384 || (ira_reg_class_superunion[cl1][cl2] != GENERAL_REGS
1385 && hard_reg_set_subset_p
1386 (reg_class_contents[cl3],
1387 reg_class_contents
1388 [(int) ira_reg_class_superunion[cl1][cl2]])))))
1389 ira_reg_class_superunion[cl1][cl2] = (enum reg_class) cl3;
1396 /* Output all uniform and important classes into file F. */
1397 static void
1398 print_unform_and_important_classes (FILE *f)
1400 static const char *const reg_class_names[] = REG_CLASS_NAMES;
1401 int i, cl;
1403 fprintf (f, "Uniform classes:\n");
1404 for (cl = 0; cl < N_REG_CLASSES; cl++)
1405 if (ira_uniform_class_p[cl])
1406 fprintf (f, " %s", reg_class_names[cl]);
1407 fprintf (f, "\nImportant classes:\n");
1408 for (i = 0; i < ira_important_classes_num; i++)
1409 fprintf (f, " %s", reg_class_names[ira_important_classes[i]]);
1410 fprintf (f, "\n");
1413 /* Output all possible allocno or pressure classes and their
1414 translation map into file F. */
1415 static void
1416 print_translated_classes (FILE *f, bool pressure_p)
1418 int classes_num = (pressure_p
1419 ? ira_pressure_classes_num : ira_allocno_classes_num);
1420 enum reg_class *classes = (pressure_p
1421 ? ira_pressure_classes : ira_allocno_classes);
1422 enum reg_class *class_translate = (pressure_p
1423 ? ira_pressure_class_translate
1424 : ira_allocno_class_translate);
1425 static const char *const reg_class_names[] = REG_CLASS_NAMES;
1426 int i;
1428 fprintf (f, "%s classes:\n", pressure_p ? "Pressure" : "Allocno");
1429 for (i = 0; i < classes_num; i++)
1430 fprintf (f, " %s", reg_class_names[classes[i]]);
1431 fprintf (f, "\nClass translation:\n");
1432 for (i = 0; i < N_REG_CLASSES; i++)
1433 fprintf (f, " %s -> %s\n", reg_class_names[i],
1434 reg_class_names[class_translate[i]]);
1437 /* Output all possible allocno and translation classes and the
1438 translation maps into stderr. */
1439 void
1440 ira_debug_allocno_classes (void)
1442 print_unform_and_important_classes (stderr);
1443 print_translated_classes (stderr, false);
1444 print_translated_classes (stderr, true);
1447 /* Set up different arrays concerning class subsets, allocno and
1448 important classes. */
1449 static void
1450 find_reg_classes (void)
1452 setup_allocno_and_important_classes ();
1453 setup_class_translate ();
1454 reorder_important_classes ();
1455 setup_reg_class_relations ();
1460 /* Set up the array above. */
1461 static void
1462 setup_hard_regno_aclass (void)
1464 int i;
1466 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1468 #if 1
1469 ira_hard_regno_allocno_class[i]
1470 = (TEST_HARD_REG_BIT (no_unit_alloc_regs, i)
1471 ? NO_REGS
1472 : ira_allocno_class_translate[REGNO_REG_CLASS (i)]);
1473 #else
1474 int j;
1475 enum reg_class cl;
1476 ira_hard_regno_allocno_class[i] = NO_REGS;
1477 for (j = 0; j < ira_allocno_classes_num; j++)
1479 cl = ira_allocno_classes[j];
1480 if (ira_class_hard_reg_index[cl][i] >= 0)
1482 ira_hard_regno_allocno_class[i] = cl;
1483 break;
1486 #endif
1492 /* Form IRA_REG_CLASS_MAX_NREGS and IRA_REG_CLASS_MIN_NREGS maps. */
1493 static void
1494 setup_reg_class_nregs (void)
1496 int i, cl, cl2, m;
1498 for (m = 0; m < MAX_MACHINE_MODE; m++)
1500 for (cl = 0; cl < N_REG_CLASSES; cl++)
1501 ira_reg_class_max_nregs[cl][m]
1502 = ira_reg_class_min_nregs[cl][m]
1503 = targetm.class_max_nregs ((reg_class_t) cl, (machine_mode) m);
1504 for (cl = 0; cl < N_REG_CLASSES; cl++)
1505 for (i = 0;
1506 (cl2 = alloc_reg_class_subclasses[cl][i]) != LIM_REG_CLASSES;
1507 i++)
1508 if (ira_reg_class_min_nregs[cl2][m]
1509 < ira_reg_class_min_nregs[cl][m])
1510 ira_reg_class_min_nregs[cl][m] = ira_reg_class_min_nregs[cl2][m];
1516 /* Set up IRA_PROHIBITED_CLASS_MODE_REGS and IRA_CLASS_SINGLETON.
1517 This function is called once IRA_CLASS_HARD_REGS has been initialized. */
1518 static void
1519 setup_prohibited_class_mode_regs (void)
1521 int j, k, hard_regno, cl, last_hard_regno, count;
1523 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
1525 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
1526 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1527 for (j = 0; j < NUM_MACHINE_MODES; j++)
1529 count = 0;
1530 last_hard_regno = -1;
1531 CLEAR_HARD_REG_SET (ira_prohibited_class_mode_regs[cl][j]);
1532 for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1534 hard_regno = ira_class_hard_regs[cl][k];
1535 if (! HARD_REGNO_MODE_OK (hard_regno, (machine_mode) j))
1536 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1537 hard_regno);
1538 else if (in_hard_reg_set_p (temp_hard_regset,
1539 (machine_mode) j, hard_regno))
1541 last_hard_regno = hard_regno;
1542 count++;
1545 ira_class_singleton[cl][j] = (count == 1 ? last_hard_regno : -1);
1550 /* Clarify IRA_PROHIBITED_CLASS_MODE_REGS by excluding hard registers
1551 spanning from one register pressure class to another one. It is
1552 called after defining the pressure classes. */
1553 static void
1554 clarify_prohibited_class_mode_regs (void)
1556 int j, k, hard_regno, cl, pclass, nregs;
1558 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
1559 for (j = 0; j < NUM_MACHINE_MODES; j++)
1561 CLEAR_HARD_REG_SET (ira_useful_class_mode_regs[cl][j]);
1562 for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1564 hard_regno = ira_class_hard_regs[cl][k];
1565 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j], hard_regno))
1566 continue;
1567 nregs = hard_regno_nregs[hard_regno][j];
1568 if (hard_regno + nregs > FIRST_PSEUDO_REGISTER)
1570 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1571 hard_regno);
1572 continue;
1574 pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)];
1575 for (nregs-- ;nregs >= 0; nregs--)
1576 if (((enum reg_class) pclass
1577 != ira_pressure_class_translate[REGNO_REG_CLASS
1578 (hard_regno + nregs)]))
1580 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1581 hard_regno);
1582 break;
1584 if (!TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1585 hard_regno))
1586 add_to_hard_reg_set (&ira_useful_class_mode_regs[cl][j],
1587 (machine_mode) j, hard_regno);
1592 /* Allocate and initialize IRA_REGISTER_MOVE_COST, IRA_MAY_MOVE_IN_COST
1593 and IRA_MAY_MOVE_OUT_COST for MODE. */
1594 void
1595 ira_init_register_move_cost (machine_mode mode)
1597 static unsigned short last_move_cost[N_REG_CLASSES][N_REG_CLASSES];
1598 bool all_match = true;
1599 unsigned int cl1, cl2;
1601 ira_assert (ira_register_move_cost[mode] == NULL
1602 && ira_may_move_in_cost[mode] == NULL
1603 && ira_may_move_out_cost[mode] == NULL);
1604 ira_assert (have_regs_of_mode[mode]);
1605 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1606 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1608 int cost;
1609 if (!contains_reg_of_mode[cl1][mode]
1610 || !contains_reg_of_mode[cl2][mode])
1612 if ((ira_reg_class_max_nregs[cl1][mode]
1613 > ira_class_hard_regs_num[cl1])
1614 || (ira_reg_class_max_nregs[cl2][mode]
1615 > ira_class_hard_regs_num[cl2]))
1616 cost = 65535;
1617 else
1618 cost = (ira_memory_move_cost[mode][cl1][0]
1619 + ira_memory_move_cost[mode][cl2][1]) * 2;
1621 else
1623 cost = register_move_cost (mode, (enum reg_class) cl1,
1624 (enum reg_class) cl2);
1625 ira_assert (cost < 65535);
1627 all_match &= (last_move_cost[cl1][cl2] == cost);
1628 last_move_cost[cl1][cl2] = cost;
1630 if (all_match && last_mode_for_init_move_cost != -1)
1632 ira_register_move_cost[mode]
1633 = ira_register_move_cost[last_mode_for_init_move_cost];
1634 ira_may_move_in_cost[mode]
1635 = ira_may_move_in_cost[last_mode_for_init_move_cost];
1636 ira_may_move_out_cost[mode]
1637 = ira_may_move_out_cost[last_mode_for_init_move_cost];
1638 return;
1640 last_mode_for_init_move_cost = mode;
1641 ira_register_move_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1642 ira_may_move_in_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1643 ira_may_move_out_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1644 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1645 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1647 int cost;
1648 enum reg_class *p1, *p2;
1650 if (last_move_cost[cl1][cl2] == 65535)
1652 ira_register_move_cost[mode][cl1][cl2] = 65535;
1653 ira_may_move_in_cost[mode][cl1][cl2] = 65535;
1654 ira_may_move_out_cost[mode][cl1][cl2] = 65535;
1656 else
1658 cost = last_move_cost[cl1][cl2];
1660 for (p2 = &reg_class_subclasses[cl2][0];
1661 *p2 != LIM_REG_CLASSES; p2++)
1662 if (ira_class_hard_regs_num[*p2] > 0
1663 && (ira_reg_class_max_nregs[*p2][mode]
1664 <= ira_class_hard_regs_num[*p2]))
1665 cost = MAX (cost, ira_register_move_cost[mode][cl1][*p2]);
1667 for (p1 = &reg_class_subclasses[cl1][0];
1668 *p1 != LIM_REG_CLASSES; p1++)
1669 if (ira_class_hard_regs_num[*p1] > 0
1670 && (ira_reg_class_max_nregs[*p1][mode]
1671 <= ira_class_hard_regs_num[*p1]))
1672 cost = MAX (cost, ira_register_move_cost[mode][*p1][cl2]);
1674 ira_assert (cost <= 65535);
1675 ira_register_move_cost[mode][cl1][cl2] = cost;
1677 if (ira_class_subset_p[cl1][cl2])
1678 ira_may_move_in_cost[mode][cl1][cl2] = 0;
1679 else
1680 ira_may_move_in_cost[mode][cl1][cl2] = cost;
1682 if (ira_class_subset_p[cl2][cl1])
1683 ira_may_move_out_cost[mode][cl1][cl2] = 0;
1684 else
1685 ira_may_move_out_cost[mode][cl1][cl2] = cost;
1692 /* This is called once during compiler work. It sets up
1693 different arrays whose values don't depend on the compiled
1694 function. */
1695 void
1696 ira_init_once (void)
1698 ira_init_costs_once ();
1699 lra_init_once ();
1702 /* Free ira_max_register_move_cost, ira_may_move_in_cost and
1703 ira_may_move_out_cost for each mode. */
1704 void
1705 target_ira_int::free_register_move_costs (void)
1707 int mode, i;
1709 /* Reset move_cost and friends, making sure we only free shared
1710 table entries once. */
1711 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1712 if (x_ira_register_move_cost[mode])
1714 for (i = 0;
1715 i < mode && (x_ira_register_move_cost[i]
1716 != x_ira_register_move_cost[mode]);
1717 i++)
1719 if (i == mode)
1721 free (x_ira_register_move_cost[mode]);
1722 free (x_ira_may_move_in_cost[mode]);
1723 free (x_ira_may_move_out_cost[mode]);
1726 memset (x_ira_register_move_cost, 0, sizeof x_ira_register_move_cost);
1727 memset (x_ira_may_move_in_cost, 0, sizeof x_ira_may_move_in_cost);
1728 memset (x_ira_may_move_out_cost, 0, sizeof x_ira_may_move_out_cost);
1729 last_mode_for_init_move_cost = -1;
1732 target_ira_int::~target_ira_int ()
1734 free_ira_costs ();
1735 free_register_move_costs ();
1738 /* This is called every time when register related information is
1739 changed. */
1740 void
1741 ira_init (void)
1743 this_target_ira_int->free_register_move_costs ();
1744 setup_reg_mode_hard_regset ();
1745 setup_alloc_regs (flag_omit_frame_pointer != 0);
1746 setup_class_subset_and_memory_move_costs ();
1747 setup_reg_class_nregs ();
1748 setup_prohibited_class_mode_regs ();
1749 find_reg_classes ();
1750 clarify_prohibited_class_mode_regs ();
1751 setup_hard_regno_aclass ();
1752 ira_init_costs ();
1756 #define ira_prohibited_mode_move_regs_initialized_p \
1757 (this_target_ira_int->x_ira_prohibited_mode_move_regs_initialized_p)
1759 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS. */
1760 static void
1761 setup_prohibited_mode_move_regs (void)
1763 int i, j;
1764 rtx test_reg1, test_reg2, move_pat;
1765 rtx_insn *move_insn;
1767 if (ira_prohibited_mode_move_regs_initialized_p)
1768 return;
1769 ira_prohibited_mode_move_regs_initialized_p = true;
1770 test_reg1 = gen_rtx_REG (word_mode, FIRST_PSEUDO_REGISTER);
1771 test_reg2 = gen_rtx_REG (word_mode, FIRST_PSEUDO_REGISTER);
1772 move_pat = gen_rtx_SET (test_reg1, test_reg2);
1773 move_insn = gen_rtx_INSN (VOIDmode, 0, 0, 0, move_pat, 0, -1, 0);
1774 for (i = 0; i < NUM_MACHINE_MODES; i++)
1776 SET_HARD_REG_SET (ira_prohibited_mode_move_regs[i]);
1777 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1779 if (! HARD_REGNO_MODE_OK (j, (machine_mode) i))
1780 continue;
1781 set_mode_and_regno (test_reg1, (machine_mode) i, j);
1782 set_mode_and_regno (test_reg2, (machine_mode) i, j);
1783 INSN_CODE (move_insn) = -1;
1784 recog_memoized (move_insn);
1785 if (INSN_CODE (move_insn) < 0)
1786 continue;
1787 extract_insn (move_insn);
1788 /* We don't know whether the move will be in code that is optimized
1789 for size or speed, so consider all enabled alternatives. */
1790 if (! constrain_operands (1, get_enabled_alternatives (move_insn)))
1791 continue;
1792 CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs[i], j);
1799 /* Setup possible alternatives in ALTS for INSN. */
1800 void
1801 ira_setup_alts (rtx_insn *insn, HARD_REG_SET &alts)
1803 /* MAP nalt * nop -> start of constraints for given operand and
1804 alternative. */
1805 static vec<const char *> insn_constraints;
1806 int nop, nalt;
1807 bool curr_swapped;
1808 const char *p;
1809 int commutative = -1;
1811 extract_insn (insn);
1812 alternative_mask preferred = get_preferred_alternatives (insn);
1813 CLEAR_HARD_REG_SET (alts);
1814 insn_constraints.release ();
1815 insn_constraints.safe_grow_cleared (recog_data.n_operands
1816 * recog_data.n_alternatives + 1);
1817 /* Check that the hard reg set is enough for holding all
1818 alternatives. It is hard to imagine the situation when the
1819 assertion is wrong. */
1820 ira_assert (recog_data.n_alternatives
1821 <= (int) MAX (sizeof (HARD_REG_ELT_TYPE) * CHAR_BIT,
1822 FIRST_PSEUDO_REGISTER));
1823 for (curr_swapped = false;; curr_swapped = true)
1825 /* Calculate some data common for all alternatives to speed up the
1826 function. */
1827 for (nop = 0; nop < recog_data.n_operands; nop++)
1829 for (nalt = 0, p = recog_data.constraints[nop];
1830 nalt < recog_data.n_alternatives;
1831 nalt++)
1833 insn_constraints[nop * recog_data.n_alternatives + nalt] = p;
1834 while (*p && *p != ',')
1835 p++;
1836 if (*p)
1837 p++;
1840 for (nalt = 0; nalt < recog_data.n_alternatives; nalt++)
1842 if (!TEST_BIT (preferred, nalt)
1843 || TEST_HARD_REG_BIT (alts, nalt))
1844 continue;
1846 for (nop = 0; nop < recog_data.n_operands; nop++)
1848 int c, len;
1850 rtx op = recog_data.operand[nop];
1851 p = insn_constraints[nop * recog_data.n_alternatives + nalt];
1852 if (*p == 0 || *p == ',')
1853 continue;
1856 switch (c = *p, len = CONSTRAINT_LEN (c, p), c)
1858 case '#':
1859 case ',':
1860 c = '\0';
1861 case '\0':
1862 len = 0;
1863 break;
1865 case '%':
1866 /* We only support one commutative marker, the
1867 first one. We already set commutative
1868 above. */
1869 if (commutative < 0)
1870 commutative = nop;
1871 break;
1873 case '0': case '1': case '2': case '3': case '4':
1874 case '5': case '6': case '7': case '8': case '9':
1875 goto op_success;
1876 break;
1878 case 'g':
1879 goto op_success;
1880 break;
1882 default:
1884 enum constraint_num cn = lookup_constraint (p);
1885 switch (get_constraint_type (cn))
1887 case CT_REGISTER:
1888 if (reg_class_for_constraint (cn) != NO_REGS)
1889 goto op_success;
1890 break;
1892 case CT_CONST_INT:
1893 if (CONST_INT_P (op)
1894 && (insn_const_int_ok_for_constraint
1895 (INTVAL (op), cn)))
1896 goto op_success;
1897 break;
1899 case CT_ADDRESS:
1900 case CT_MEMORY:
1901 goto op_success;
1903 case CT_FIXED_FORM:
1904 if (constraint_satisfied_p (op, cn))
1905 goto op_success;
1906 break;
1908 break;
1911 while (p += len, c);
1912 break;
1913 op_success:
1916 if (nop >= recog_data.n_operands)
1917 SET_HARD_REG_BIT (alts, nalt);
1919 if (commutative < 0)
1920 break;
1921 if (curr_swapped)
1922 break;
1923 std::swap (recog_data.operand[commutative],
1924 recog_data.operand[commutative + 1]);
1928 /* Return the number of the output non-early clobber operand which
1929 should be the same in any case as operand with number OP_NUM (or
1930 negative value if there is no such operand). The function takes
1931 only really possible alternatives into consideration. */
1933 ira_get_dup_out_num (int op_num, HARD_REG_SET &alts)
1935 int curr_alt, c, original, dup;
1936 bool ignore_p, use_commut_op_p;
1937 const char *str;
1939 if (op_num < 0 || recog_data.n_alternatives == 0)
1940 return -1;
1941 /* We should find duplications only for input operands. */
1942 if (recog_data.operand_type[op_num] != OP_IN)
1943 return -1;
1944 str = recog_data.constraints[op_num];
1945 use_commut_op_p = false;
1946 for (;;)
1948 rtx op = recog_data.operand[op_num];
1950 for (curr_alt = 0, ignore_p = !TEST_HARD_REG_BIT (alts, curr_alt),
1951 original = -1;;)
1953 c = *str;
1954 if (c == '\0')
1955 break;
1956 if (c == '#')
1957 ignore_p = true;
1958 else if (c == ',')
1960 curr_alt++;
1961 ignore_p = !TEST_HARD_REG_BIT (alts, curr_alt);
1963 else if (! ignore_p)
1964 switch (c)
1966 case 'g':
1967 goto fail;
1968 default:
1970 enum constraint_num cn = lookup_constraint (str);
1971 enum reg_class cl = reg_class_for_constraint (cn);
1972 if (cl != NO_REGS
1973 && !targetm.class_likely_spilled_p (cl))
1974 goto fail;
1975 if (constraint_satisfied_p (op, cn))
1976 goto fail;
1977 break;
1980 case '0': case '1': case '2': case '3': case '4':
1981 case '5': case '6': case '7': case '8': case '9':
1982 if (original != -1 && original != c)
1983 goto fail;
1984 original = c;
1985 break;
1987 str += CONSTRAINT_LEN (c, str);
1989 if (original == -1)
1990 goto fail;
1991 dup = -1;
1992 for (ignore_p = false, str = recog_data.constraints[original - '0'];
1993 *str != 0;
1994 str++)
1995 if (ignore_p)
1997 if (*str == ',')
1998 ignore_p = false;
2000 else if (*str == '#')
2001 ignore_p = true;
2002 else if (! ignore_p)
2004 if (*str == '=')
2005 dup = original - '0';
2006 /* It is better ignore an alternative with early clobber. */
2007 else if (*str == '&')
2008 goto fail;
2010 if (dup >= 0)
2011 return dup;
2012 fail:
2013 if (use_commut_op_p)
2014 break;
2015 use_commut_op_p = true;
2016 if (recog_data.constraints[op_num][0] == '%')
2017 str = recog_data.constraints[op_num + 1];
2018 else if (op_num > 0 && recog_data.constraints[op_num - 1][0] == '%')
2019 str = recog_data.constraints[op_num - 1];
2020 else
2021 break;
2023 return -1;
2028 /* Search forward to see if the source register of a copy insn dies
2029 before either it or the destination register is modified, but don't
2030 scan past the end of the basic block. If so, we can replace the
2031 source with the destination and let the source die in the copy
2032 insn.
2034 This will reduce the number of registers live in that range and may
2035 enable the destination and the source coalescing, thus often saving
2036 one register in addition to a register-register copy. */
2038 static void
2039 decrease_live_ranges_number (void)
2041 basic_block bb;
2042 rtx_insn *insn;
2043 rtx set, src, dest, dest_death, note;
2044 rtx_insn *p, *q;
2045 int sregno, dregno;
2047 if (! flag_expensive_optimizations)
2048 return;
2050 if (ira_dump_file)
2051 fprintf (ira_dump_file, "Starting decreasing number of live ranges...\n");
2053 FOR_EACH_BB_FN (bb, cfun)
2054 FOR_BB_INSNS (bb, insn)
2056 set = single_set (insn);
2057 if (! set)
2058 continue;
2059 src = SET_SRC (set);
2060 dest = SET_DEST (set);
2061 if (! REG_P (src) || ! REG_P (dest)
2062 || find_reg_note (insn, REG_DEAD, src))
2063 continue;
2064 sregno = REGNO (src);
2065 dregno = REGNO (dest);
2067 /* We don't want to mess with hard regs if register classes
2068 are small. */
2069 if (sregno == dregno
2070 || (targetm.small_register_classes_for_mode_p (GET_MODE (src))
2071 && (sregno < FIRST_PSEUDO_REGISTER
2072 || dregno < FIRST_PSEUDO_REGISTER))
2073 /* We don't see all updates to SP if they are in an
2074 auto-inc memory reference, so we must disallow this
2075 optimization on them. */
2076 || sregno == STACK_POINTER_REGNUM
2077 || dregno == STACK_POINTER_REGNUM)
2078 continue;
2080 dest_death = NULL_RTX;
2082 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
2084 if (! INSN_P (p))
2085 continue;
2086 if (BLOCK_FOR_INSN (p) != bb)
2087 break;
2089 if (reg_set_p (src, p) || reg_set_p (dest, p)
2090 /* If SRC is an asm-declared register, it must not be
2091 replaced in any asm. Unfortunately, the REG_EXPR
2092 tree for the asm variable may be absent in the SRC
2093 rtx, so we can't check the actual register
2094 declaration easily (the asm operand will have it,
2095 though). To avoid complicating the test for a rare
2096 case, we just don't perform register replacement
2097 for a hard reg mentioned in an asm. */
2098 || (sregno < FIRST_PSEUDO_REGISTER
2099 && asm_noperands (PATTERN (p)) >= 0
2100 && reg_overlap_mentioned_p (src, PATTERN (p)))
2101 /* Don't change hard registers used by a call. */
2102 || (CALL_P (p) && sregno < FIRST_PSEUDO_REGISTER
2103 && find_reg_fusage (p, USE, src))
2104 /* Don't change a USE of a register. */
2105 || (GET_CODE (PATTERN (p)) == USE
2106 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
2107 break;
2109 /* See if all of SRC dies in P. This test is slightly
2110 more conservative than it needs to be. */
2111 if ((note = find_regno_note (p, REG_DEAD, sregno))
2112 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
2114 int failed = 0;
2116 /* We can do the optimization. Scan forward from INSN
2117 again, replacing regs as we go. Set FAILED if a
2118 replacement can't be done. In that case, we can't
2119 move the death note for SRC. This should be
2120 rare. */
2122 /* Set to stop at next insn. */
2123 for (q = next_real_insn (insn);
2124 q != next_real_insn (p);
2125 q = next_real_insn (q))
2127 if (reg_overlap_mentioned_p (src, PATTERN (q)))
2129 /* If SRC is a hard register, we might miss
2130 some overlapping registers with
2131 validate_replace_rtx, so we would have to
2132 undo it. We can't if DEST is present in
2133 the insn, so fail in that combination of
2134 cases. */
2135 if (sregno < FIRST_PSEUDO_REGISTER
2136 && reg_mentioned_p (dest, PATTERN (q)))
2137 failed = 1;
2139 /* Attempt to replace all uses. */
2140 else if (!validate_replace_rtx (src, dest, q))
2141 failed = 1;
2143 /* If this succeeded, but some part of the
2144 register is still present, undo the
2145 replacement. */
2146 else if (sregno < FIRST_PSEUDO_REGISTER
2147 && reg_overlap_mentioned_p (src, PATTERN (q)))
2149 validate_replace_rtx (dest, src, q);
2150 failed = 1;
2154 /* If DEST dies here, remove the death note and
2155 save it for later. Make sure ALL of DEST dies
2156 here; again, this is overly conservative. */
2157 if (! dest_death
2158 && (dest_death = find_regno_note (q, REG_DEAD, dregno)))
2160 if (GET_MODE (XEXP (dest_death, 0)) == GET_MODE (dest))
2161 remove_note (q, dest_death);
2162 else
2164 failed = 1;
2165 dest_death = 0;
2170 if (! failed)
2172 /* Move death note of SRC from P to INSN. */
2173 remove_note (p, note);
2174 XEXP (note, 1) = REG_NOTES (insn);
2175 REG_NOTES (insn) = note;
2178 /* DEST is also dead if INSN has a REG_UNUSED note for
2179 DEST. */
2180 if (! dest_death
2181 && (dest_death
2182 = find_regno_note (insn, REG_UNUSED, dregno)))
2184 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
2185 remove_note (insn, dest_death);
2188 /* Put death note of DEST on P if we saw it die. */
2189 if (dest_death)
2191 XEXP (dest_death, 1) = REG_NOTES (p);
2192 REG_NOTES (p) = dest_death;
2194 break;
2197 /* If SRC is a hard register which is set or killed in
2198 some other way, we can't do this optimization. */
2199 else if (sregno < FIRST_PSEUDO_REGISTER && dead_or_set_p (p, src))
2200 break;
2207 /* Return nonzero if REGNO is a particularly bad choice for reloading X. */
2208 static bool
2209 ira_bad_reload_regno_1 (int regno, rtx x)
2211 int x_regno, n, i;
2212 ira_allocno_t a;
2213 enum reg_class pref;
2215 /* We only deal with pseudo regs. */
2216 if (! x || GET_CODE (x) != REG)
2217 return false;
2219 x_regno = REGNO (x);
2220 if (x_regno < FIRST_PSEUDO_REGISTER)
2221 return false;
2223 /* If the pseudo prefers REGNO explicitly, then do not consider
2224 REGNO a bad spill choice. */
2225 pref = reg_preferred_class (x_regno);
2226 if (reg_class_size[pref] == 1)
2227 return !TEST_HARD_REG_BIT (reg_class_contents[pref], regno);
2229 /* If the pseudo conflicts with REGNO, then we consider REGNO a
2230 poor choice for a reload regno. */
2231 a = ira_regno_allocno_map[x_regno];
2232 n = ALLOCNO_NUM_OBJECTS (a);
2233 for (i = 0; i < n; i++)
2235 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2236 if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), regno))
2237 return true;
2239 return false;
2242 /* Return nonzero if REGNO is a particularly bad choice for reloading
2243 IN or OUT. */
2244 bool
2245 ira_bad_reload_regno (int regno, rtx in, rtx out)
2247 return (ira_bad_reload_regno_1 (regno, in)
2248 || ira_bad_reload_regno_1 (regno, out));
2251 /* Add register clobbers from asm statements. */
2252 static void
2253 compute_regs_asm_clobbered (void)
2255 basic_block bb;
2257 FOR_EACH_BB_FN (bb, cfun)
2259 rtx_insn *insn;
2260 FOR_BB_INSNS_REVERSE (bb, insn)
2262 df_ref def;
2264 if (NONDEBUG_INSN_P (insn) && extract_asm_operands (PATTERN (insn)))
2265 FOR_EACH_INSN_DEF (def, insn)
2267 unsigned int dregno = DF_REF_REGNO (def);
2268 if (HARD_REGISTER_NUM_P (dregno))
2269 add_to_hard_reg_set (&crtl->asm_clobbers,
2270 GET_MODE (DF_REF_REAL_REG (def)),
2271 dregno);
2278 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and
2279 REGS_EVER_LIVE. */
2280 void
2281 ira_setup_eliminable_regset (void)
2283 #ifdef ELIMINABLE_REGS
2284 int i;
2285 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
2286 #endif
2287 /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
2288 sp for alloca. So we can't eliminate the frame pointer in that
2289 case. At some point, we should improve this by emitting the
2290 sp-adjusting insns for this case. */
2291 frame_pointer_needed
2292 = (! flag_omit_frame_pointer
2293 || (cfun->calls_alloca && EXIT_IGNORE_STACK)
2294 /* We need the frame pointer to catch stack overflow exceptions
2295 if the stack pointer is moving. */
2296 || (flag_stack_check && STACK_CHECK_MOVING_SP)
2297 || crtl->accesses_prior_frames
2298 || (SUPPORTS_STACK_ALIGNMENT && crtl->stack_realign_needed)
2299 /* We need a frame pointer for all Cilk Plus functions that use
2300 Cilk keywords. */
2301 || (flag_cilkplus && cfun->is_cilk_function)
2302 || targetm.frame_pointer_required ());
2304 /* The chance that FRAME_POINTER_NEEDED is changed from inspecting
2305 RTL is very small. So if we use frame pointer for RA and RTL
2306 actually prevents this, we will spill pseudos assigned to the
2307 frame pointer in LRA. */
2309 if (frame_pointer_needed)
2310 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
2312 COPY_HARD_REG_SET (ira_no_alloc_regs, no_unit_alloc_regs);
2313 CLEAR_HARD_REG_SET (eliminable_regset);
2315 compute_regs_asm_clobbered ();
2317 /* Build the regset of all eliminable registers and show we can't
2318 use those that we already know won't be eliminated. */
2319 #ifdef ELIMINABLE_REGS
2320 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
2322 bool cannot_elim
2323 = (! targetm.can_eliminate (eliminables[i].from, eliminables[i].to)
2324 || (eliminables[i].to == STACK_POINTER_REGNUM && frame_pointer_needed));
2326 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, eliminables[i].from))
2328 SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
2330 if (cannot_elim)
2331 SET_HARD_REG_BIT (ira_no_alloc_regs, eliminables[i].from);
2333 else if (cannot_elim)
2334 error ("%s cannot be used in asm here",
2335 reg_names[eliminables[i].from]);
2336 else
2337 df_set_regs_ever_live (eliminables[i].from, true);
2339 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
2341 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM))
2343 SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
2344 if (frame_pointer_needed)
2345 SET_HARD_REG_BIT (ira_no_alloc_regs, HARD_FRAME_POINTER_REGNUM);
2347 else if (frame_pointer_needed)
2348 error ("%s cannot be used in asm here",
2349 reg_names[HARD_FRAME_POINTER_REGNUM]);
2350 else
2351 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
2354 #else
2355 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM))
2357 SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
2358 if (frame_pointer_needed)
2359 SET_HARD_REG_BIT (ira_no_alloc_regs, FRAME_POINTER_REGNUM);
2361 else if (frame_pointer_needed)
2362 error ("%s cannot be used in asm here", reg_names[FRAME_POINTER_REGNUM]);
2363 else
2364 df_set_regs_ever_live (FRAME_POINTER_REGNUM, true);
2365 #endif
2370 /* Vector of substitutions of register numbers,
2371 used to map pseudo regs into hardware regs.
2372 This is set up as a result of register allocation.
2373 Element N is the hard reg assigned to pseudo reg N,
2374 or is -1 if no hard reg was assigned.
2375 If N is a hard reg number, element N is N. */
2376 short *reg_renumber;
2378 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
2379 the allocation found by IRA. */
2380 static void
2381 setup_reg_renumber (void)
2383 int regno, hard_regno;
2384 ira_allocno_t a;
2385 ira_allocno_iterator ai;
2387 caller_save_needed = 0;
2388 FOR_EACH_ALLOCNO (a, ai)
2390 if (ira_use_lra_p && ALLOCNO_CAP_MEMBER (a) != NULL)
2391 continue;
2392 /* There are no caps at this point. */
2393 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2394 if (! ALLOCNO_ASSIGNED_P (a))
2395 /* It can happen if A is not referenced but partially anticipated
2396 somewhere in a region. */
2397 ALLOCNO_ASSIGNED_P (a) = true;
2398 ira_free_allocno_updated_costs (a);
2399 hard_regno = ALLOCNO_HARD_REGNO (a);
2400 regno = ALLOCNO_REGNO (a);
2401 reg_renumber[regno] = (hard_regno < 0 ? -1 : hard_regno);
2402 if (hard_regno >= 0)
2404 int i, nwords;
2405 enum reg_class pclass;
2406 ira_object_t obj;
2408 pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)];
2409 nwords = ALLOCNO_NUM_OBJECTS (a);
2410 for (i = 0; i < nwords; i++)
2412 obj = ALLOCNO_OBJECT (a, i);
2413 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
2414 reg_class_contents[pclass]);
2416 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
2417 && ira_hard_reg_set_intersection_p (hard_regno, ALLOCNO_MODE (a),
2418 call_used_reg_set))
2420 ira_assert (!optimize || flag_caller_saves
2421 || (ALLOCNO_CALLS_CROSSED_NUM (a)
2422 == ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a))
2423 || regno >= ira_reg_equiv_len
2424 || ira_equiv_no_lvalue_p (regno));
2425 caller_save_needed = 1;
2431 /* Set up allocno assignment flags for further allocation
2432 improvements. */
2433 static void
2434 setup_allocno_assignment_flags (void)
2436 int hard_regno;
2437 ira_allocno_t a;
2438 ira_allocno_iterator ai;
2440 FOR_EACH_ALLOCNO (a, ai)
2442 if (! ALLOCNO_ASSIGNED_P (a))
2443 /* It can happen if A is not referenced but partially anticipated
2444 somewhere in a region. */
2445 ira_free_allocno_updated_costs (a);
2446 hard_regno = ALLOCNO_HARD_REGNO (a);
2447 /* Don't assign hard registers to allocnos which are destination
2448 of removed store at the end of loop. It has no sense to keep
2449 the same value in different hard registers. It is also
2450 impossible to assign hard registers correctly to such
2451 allocnos because the cost info and info about intersected
2452 calls are incorrect for them. */
2453 ALLOCNO_ASSIGNED_P (a) = (hard_regno >= 0
2454 || ALLOCNO_EMIT_DATA (a)->mem_optimized_dest_p
2455 || (ALLOCNO_MEMORY_COST (a)
2456 - ALLOCNO_CLASS_COST (a)) < 0);
2457 ira_assert
2458 (hard_regno < 0
2459 || ira_hard_reg_in_set_p (hard_regno, ALLOCNO_MODE (a),
2460 reg_class_contents[ALLOCNO_CLASS (a)]));
2464 /* Evaluate overall allocation cost and the costs for using hard
2465 registers and memory for allocnos. */
2466 static void
2467 calculate_allocation_cost (void)
2469 int hard_regno, cost;
2470 ira_allocno_t a;
2471 ira_allocno_iterator ai;
2473 ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
2474 FOR_EACH_ALLOCNO (a, ai)
2476 hard_regno = ALLOCNO_HARD_REGNO (a);
2477 ira_assert (hard_regno < 0
2478 || (ira_hard_reg_in_set_p
2479 (hard_regno, ALLOCNO_MODE (a),
2480 reg_class_contents[ALLOCNO_CLASS (a)])));
2481 if (hard_regno < 0)
2483 cost = ALLOCNO_MEMORY_COST (a);
2484 ira_mem_cost += cost;
2486 else if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
2488 cost = (ALLOCNO_HARD_REG_COSTS (a)
2489 [ira_class_hard_reg_index
2490 [ALLOCNO_CLASS (a)][hard_regno]]);
2491 ira_reg_cost += cost;
2493 else
2495 cost = ALLOCNO_CLASS_COST (a);
2496 ira_reg_cost += cost;
2498 ira_overall_cost += cost;
2501 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2503 fprintf (ira_dump_file,
2504 "+++Costs: overall %" PRId64
2505 ", reg %" PRId64
2506 ", mem %" PRId64
2507 ", ld %" PRId64
2508 ", st %" PRId64
2509 ", move %" PRId64,
2510 ira_overall_cost, ira_reg_cost, ira_mem_cost,
2511 ira_load_cost, ira_store_cost, ira_shuffle_cost);
2512 fprintf (ira_dump_file, "\n+++ move loops %d, new jumps %d\n",
2513 ira_move_loops_num, ira_additional_jumps_num);
2518 #ifdef ENABLE_IRA_CHECKING
2519 /* Check the correctness of the allocation. We do need this because
2520 of complicated code to transform more one region internal
2521 representation into one region representation. */
2522 static void
2523 check_allocation (void)
2525 ira_allocno_t a;
2526 int hard_regno, nregs, conflict_nregs;
2527 ira_allocno_iterator ai;
2529 FOR_EACH_ALLOCNO (a, ai)
2531 int n = ALLOCNO_NUM_OBJECTS (a);
2532 int i;
2534 if (ALLOCNO_CAP_MEMBER (a) != NULL
2535 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
2536 continue;
2537 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
2538 if (nregs == 1)
2539 /* We allocated a single hard register. */
2540 n = 1;
2541 else if (n > 1)
2542 /* We allocated multiple hard registers, and we will test
2543 conflicts in a granularity of single hard regs. */
2544 nregs = 1;
2546 for (i = 0; i < n; i++)
2548 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2549 ira_object_t conflict_obj;
2550 ira_object_conflict_iterator oci;
2551 int this_regno = hard_regno;
2552 if (n > 1)
2554 if (REG_WORDS_BIG_ENDIAN)
2555 this_regno += n - i - 1;
2556 else
2557 this_regno += i;
2559 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2561 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2562 int conflict_hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
2563 if (conflict_hard_regno < 0)
2564 continue;
2566 conflict_nregs
2567 = (hard_regno_nregs
2568 [conflict_hard_regno][ALLOCNO_MODE (conflict_a)]);
2570 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1
2571 && conflict_nregs == ALLOCNO_NUM_OBJECTS (conflict_a))
2573 if (REG_WORDS_BIG_ENDIAN)
2574 conflict_hard_regno += (ALLOCNO_NUM_OBJECTS (conflict_a)
2575 - OBJECT_SUBWORD (conflict_obj) - 1);
2576 else
2577 conflict_hard_regno += OBJECT_SUBWORD (conflict_obj);
2578 conflict_nregs = 1;
2581 if ((conflict_hard_regno <= this_regno
2582 && this_regno < conflict_hard_regno + conflict_nregs)
2583 || (this_regno <= conflict_hard_regno
2584 && conflict_hard_regno < this_regno + nregs))
2586 fprintf (stderr, "bad allocation for %d and %d\n",
2587 ALLOCNO_REGNO (a), ALLOCNO_REGNO (conflict_a));
2588 gcc_unreachable ();
2594 #endif
2596 /* Allocate REG_EQUIV_INIT. Set up it from IRA_REG_EQUIV which should
2597 be already calculated. */
2598 static void
2599 setup_reg_equiv_init (void)
2601 int i;
2602 int max_regno = max_reg_num ();
2604 for (i = 0; i < max_regno; i++)
2605 reg_equiv_init (i) = ira_reg_equiv[i].init_insns;
2608 /* Update equiv regno from movement of FROM_REGNO to TO_REGNO. INSNS
2609 are insns which were generated for such movement. It is assumed
2610 that FROM_REGNO and TO_REGNO always have the same value at the
2611 point of any move containing such registers. This function is used
2612 to update equiv info for register shuffles on the region borders
2613 and for caller save/restore insns. */
2614 void
2615 ira_update_equiv_info_by_shuffle_insn (int to_regno, int from_regno, rtx_insn *insns)
2617 rtx_insn *insn;
2618 rtx x, note;
2620 if (! ira_reg_equiv[from_regno].defined_p
2621 && (! ira_reg_equiv[to_regno].defined_p
2622 || ((x = ira_reg_equiv[to_regno].memory) != NULL_RTX
2623 && ! MEM_READONLY_P (x))))
2624 return;
2625 insn = insns;
2626 if (NEXT_INSN (insn) != NULL_RTX)
2628 if (! ira_reg_equiv[to_regno].defined_p)
2630 ira_assert (ira_reg_equiv[to_regno].init_insns == NULL_RTX);
2631 return;
2633 ira_reg_equiv[to_regno].defined_p = false;
2634 ira_reg_equiv[to_regno].memory
2635 = ira_reg_equiv[to_regno].constant
2636 = ira_reg_equiv[to_regno].invariant
2637 = ira_reg_equiv[to_regno].init_insns = NULL;
2638 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2639 fprintf (ira_dump_file,
2640 " Invalidating equiv info for reg %d\n", to_regno);
2641 return;
2643 /* It is possible that FROM_REGNO still has no equivalence because
2644 in shuffles to_regno<-from_regno and from_regno<-to_regno the 2nd
2645 insn was not processed yet. */
2646 if (ira_reg_equiv[from_regno].defined_p)
2648 ira_reg_equiv[to_regno].defined_p = true;
2649 if ((x = ira_reg_equiv[from_regno].memory) != NULL_RTX)
2651 ira_assert (ira_reg_equiv[from_regno].invariant == NULL_RTX
2652 && ira_reg_equiv[from_regno].constant == NULL_RTX);
2653 ira_assert (ira_reg_equiv[to_regno].memory == NULL_RTX
2654 || rtx_equal_p (ira_reg_equiv[to_regno].memory, x));
2655 ira_reg_equiv[to_regno].memory = x;
2656 if (! MEM_READONLY_P (x))
2657 /* We don't add the insn to insn init list because memory
2658 equivalence is just to say what memory is better to use
2659 when the pseudo is spilled. */
2660 return;
2662 else if ((x = ira_reg_equiv[from_regno].constant) != NULL_RTX)
2664 ira_assert (ira_reg_equiv[from_regno].invariant == NULL_RTX);
2665 ira_assert (ira_reg_equiv[to_regno].constant == NULL_RTX
2666 || rtx_equal_p (ira_reg_equiv[to_regno].constant, x));
2667 ira_reg_equiv[to_regno].constant = x;
2669 else
2671 x = ira_reg_equiv[from_regno].invariant;
2672 ira_assert (x != NULL_RTX);
2673 ira_assert (ira_reg_equiv[to_regno].invariant == NULL_RTX
2674 || rtx_equal_p (ira_reg_equiv[to_regno].invariant, x));
2675 ira_reg_equiv[to_regno].invariant = x;
2677 if (find_reg_note (insn, REG_EQUIV, x) == NULL_RTX)
2679 note = set_unique_reg_note (insn, REG_EQUIV, x);
2680 gcc_assert (note != NULL_RTX);
2681 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2683 fprintf (ira_dump_file,
2684 " Adding equiv note to insn %u for reg %d ",
2685 INSN_UID (insn), to_regno);
2686 dump_value_slim (ira_dump_file, x, 1);
2687 fprintf (ira_dump_file, "\n");
2691 ira_reg_equiv[to_regno].init_insns
2692 = gen_rtx_INSN_LIST (VOIDmode, insn,
2693 ira_reg_equiv[to_regno].init_insns);
2694 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2695 fprintf (ira_dump_file,
2696 " Adding equiv init move insn %u to reg %d\n",
2697 INSN_UID (insn), to_regno);
2700 /* Fix values of array REG_EQUIV_INIT after live range splitting done
2701 by IRA. */
2702 static void
2703 fix_reg_equiv_init (void)
2705 int max_regno = max_reg_num ();
2706 int i, new_regno, max;
2707 rtx set;
2708 rtx_insn_list *x, *next, *prev;
2709 rtx_insn *insn;
2711 if (max_regno_before_ira < max_regno)
2713 max = vec_safe_length (reg_equivs);
2714 grow_reg_equivs ();
2715 for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
2716 for (prev = NULL, x = reg_equiv_init (i);
2717 x != NULL_RTX;
2718 x = next)
2720 next = x->next ();
2721 insn = x->insn ();
2722 set = single_set (insn);
2723 ira_assert (set != NULL_RTX
2724 && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))));
2725 if (REG_P (SET_DEST (set))
2726 && ((int) REGNO (SET_DEST (set)) == i
2727 || (int) ORIGINAL_REGNO (SET_DEST (set)) == i))
2728 new_regno = REGNO (SET_DEST (set));
2729 else if (REG_P (SET_SRC (set))
2730 && ((int) REGNO (SET_SRC (set)) == i
2731 || (int) ORIGINAL_REGNO (SET_SRC (set)) == i))
2732 new_regno = REGNO (SET_SRC (set));
2733 else
2734 gcc_unreachable ();
2735 if (new_regno == i)
2736 prev = x;
2737 else
2739 /* Remove the wrong list element. */
2740 if (prev == NULL_RTX)
2741 reg_equiv_init (i) = next;
2742 else
2743 XEXP (prev, 1) = next;
2744 XEXP (x, 1) = reg_equiv_init (new_regno);
2745 reg_equiv_init (new_regno) = x;
2751 #ifdef ENABLE_IRA_CHECKING
2752 /* Print redundant memory-memory copies. */
2753 static void
2754 print_redundant_copies (void)
2756 int hard_regno;
2757 ira_allocno_t a;
2758 ira_copy_t cp, next_cp;
2759 ira_allocno_iterator ai;
2761 FOR_EACH_ALLOCNO (a, ai)
2763 if (ALLOCNO_CAP_MEMBER (a) != NULL)
2764 /* It is a cap. */
2765 continue;
2766 hard_regno = ALLOCNO_HARD_REGNO (a);
2767 if (hard_regno >= 0)
2768 continue;
2769 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2770 if (cp->first == a)
2771 next_cp = cp->next_first_allocno_copy;
2772 else
2774 next_cp = cp->next_second_allocno_copy;
2775 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL
2776 && cp->insn != NULL_RTX
2777 && ALLOCNO_HARD_REGNO (cp->first) == hard_regno)
2778 fprintf (ira_dump_file,
2779 " Redundant move from %d(freq %d):%d\n",
2780 INSN_UID (cp->insn), cp->freq, hard_regno);
2784 #endif
2786 /* Setup preferred and alternative classes for new pseudo-registers
2787 created by IRA starting with START. */
2788 static void
2789 setup_preferred_alternate_classes_for_new_pseudos (int start)
2791 int i, old_regno;
2792 int max_regno = max_reg_num ();
2794 for (i = start; i < max_regno; i++)
2796 old_regno = ORIGINAL_REGNO (regno_reg_rtx[i]);
2797 ira_assert (i != old_regno);
2798 setup_reg_classes (i, reg_preferred_class (old_regno),
2799 reg_alternate_class (old_regno),
2800 reg_allocno_class (old_regno));
2801 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2802 fprintf (ira_dump_file,
2803 " New r%d: setting preferred %s, alternative %s\n",
2804 i, reg_class_names[reg_preferred_class (old_regno)],
2805 reg_class_names[reg_alternate_class (old_regno)]);
2810 /* The number of entries allocated in reg_info. */
2811 static int allocated_reg_info_size;
2813 /* Regional allocation can create new pseudo-registers. This function
2814 expands some arrays for pseudo-registers. */
2815 static void
2816 expand_reg_info (void)
2818 int i;
2819 int size = max_reg_num ();
2821 resize_reg_info ();
2822 for (i = allocated_reg_info_size; i < size; i++)
2823 setup_reg_classes (i, GENERAL_REGS, ALL_REGS, GENERAL_REGS);
2824 setup_preferred_alternate_classes_for_new_pseudos (allocated_reg_info_size);
2825 allocated_reg_info_size = size;
2828 /* Return TRUE if there is too high register pressure in the function.
2829 It is used to decide when stack slot sharing is worth to do. */
2830 static bool
2831 too_high_register_pressure_p (void)
2833 int i;
2834 enum reg_class pclass;
2836 for (i = 0; i < ira_pressure_classes_num; i++)
2838 pclass = ira_pressure_classes[i];
2839 if (ira_loop_tree_root->reg_pressure[pclass] > 10000)
2840 return true;
2842 return false;
2847 /* Indicate that hard register number FROM was eliminated and replaced with
2848 an offset from hard register number TO. The status of hard registers live
2849 at the start of a basic block is updated by replacing a use of FROM with
2850 a use of TO. */
2852 void
2853 mark_elimination (int from, int to)
2855 basic_block bb;
2856 bitmap r;
2858 FOR_EACH_BB_FN (bb, cfun)
2860 r = DF_LR_IN (bb);
2861 if (bitmap_bit_p (r, from))
2863 bitmap_clear_bit (r, from);
2864 bitmap_set_bit (r, to);
2866 if (! df_live)
2867 continue;
2868 r = DF_LIVE_IN (bb);
2869 if (bitmap_bit_p (r, from))
2871 bitmap_clear_bit (r, from);
2872 bitmap_set_bit (r, to);
2879 /* The length of the following array. */
2880 int ira_reg_equiv_len;
2882 /* Info about equiv. info for each register. */
2883 struct ira_reg_equiv_s *ira_reg_equiv;
2885 /* Expand ira_reg_equiv if necessary. */
2886 void
2887 ira_expand_reg_equiv (void)
2889 int old = ira_reg_equiv_len;
2891 if (ira_reg_equiv_len > max_reg_num ())
2892 return;
2893 ira_reg_equiv_len = max_reg_num () * 3 / 2 + 1;
2894 ira_reg_equiv
2895 = (struct ira_reg_equiv_s *) xrealloc (ira_reg_equiv,
2896 ira_reg_equiv_len
2897 * sizeof (struct ira_reg_equiv_s));
2898 gcc_assert (old < ira_reg_equiv_len);
2899 memset (ira_reg_equiv + old, 0,
2900 sizeof (struct ira_reg_equiv_s) * (ira_reg_equiv_len - old));
2903 static void
2904 init_reg_equiv (void)
2906 ira_reg_equiv_len = 0;
2907 ira_reg_equiv = NULL;
2908 ira_expand_reg_equiv ();
2911 static void
2912 finish_reg_equiv (void)
2914 free (ira_reg_equiv);
2919 struct equivalence
2921 /* Set when a REG_EQUIV note is found or created. Use to
2922 keep track of what memory accesses might be created later,
2923 e.g. by reload. */
2924 rtx replacement;
2925 rtx *src_p;
2927 /* The list of each instruction which initializes this register.
2929 NULL indicates we know nothing about this register's equivalence
2930 properties.
2932 An INSN_LIST with a NULL insn indicates this pseudo is already
2933 known to not have a valid equivalence. */
2934 rtx_insn_list *init_insns;
2936 /* Loop depth is used to recognize equivalences which appear
2937 to be present within the same loop (or in an inner loop). */
2938 short loop_depth;
2939 /* Nonzero if this had a preexisting REG_EQUIV note. */
2940 unsigned char is_arg_equivalence : 1;
2941 /* Set when an attempt should be made to replace a register
2942 with the associated src_p entry. */
2943 unsigned char replace : 1;
2944 /* Set if this register has no known equivalence. */
2945 unsigned char no_equiv : 1;
2948 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
2949 structure for that register. */
2950 static struct equivalence *reg_equiv;
2952 /* Used for communication between the following two functions: contains
2953 a MEM that we wish to ensure remains unchanged. */
2954 static rtx equiv_mem;
2956 /* Set nonzero if EQUIV_MEM is modified. */
2957 static int equiv_mem_modified;
2959 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
2960 Called via note_stores. */
2961 static void
2962 validate_equiv_mem_from_store (rtx dest, const_rtx set ATTRIBUTE_UNUSED,
2963 void *data ATTRIBUTE_UNUSED)
2965 if ((REG_P (dest)
2966 && reg_overlap_mentioned_p (dest, equiv_mem))
2967 || (MEM_P (dest)
2968 && anti_dependence (equiv_mem, dest)))
2969 equiv_mem_modified = 1;
2972 /* Verify that no store between START and the death of REG invalidates
2973 MEMREF. MEMREF is invalidated by modifying a register used in MEMREF,
2974 by storing into an overlapping memory location, or with a non-const
2975 CALL_INSN.
2977 Return 1 if MEMREF remains valid. */
2978 static int
2979 validate_equiv_mem (rtx_insn *start, rtx reg, rtx memref)
2981 rtx_insn *insn;
2982 rtx note;
2984 equiv_mem = memref;
2985 equiv_mem_modified = 0;
2987 /* If the memory reference has side effects or is volatile, it isn't a
2988 valid equivalence. */
2989 if (side_effects_p (memref))
2990 return 0;
2992 for (insn = start; insn && ! equiv_mem_modified; insn = NEXT_INSN (insn))
2994 if (! INSN_P (insn))
2995 continue;
2997 if (find_reg_note (insn, REG_DEAD, reg))
2998 return 1;
3000 /* This used to ignore readonly memory and const/pure calls. The problem
3001 is the equivalent form may reference a pseudo which gets assigned a
3002 call clobbered hard reg. When we later replace REG with its
3003 equivalent form, the value in the call-clobbered reg has been
3004 changed and all hell breaks loose. */
3005 if (CALL_P (insn))
3006 return 0;
3008 note_stores (PATTERN (insn), validate_equiv_mem_from_store, NULL);
3010 /* If a register mentioned in MEMREF is modified via an
3011 auto-increment, we lose the equivalence. Do the same if one
3012 dies; although we could extend the life, it doesn't seem worth
3013 the trouble. */
3015 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
3016 if ((REG_NOTE_KIND (note) == REG_INC
3017 || REG_NOTE_KIND (note) == REG_DEAD)
3018 && REG_P (XEXP (note, 0))
3019 && reg_overlap_mentioned_p (XEXP (note, 0), memref))
3020 return 0;
3023 return 0;
3026 /* Returns zero if X is known to be invariant. */
3027 static int
3028 equiv_init_varies_p (rtx x)
3030 RTX_CODE code = GET_CODE (x);
3031 int i;
3032 const char *fmt;
3034 switch (code)
3036 case MEM:
3037 return !MEM_READONLY_P (x) || equiv_init_varies_p (XEXP (x, 0));
3039 case CONST:
3040 CASE_CONST_ANY:
3041 case SYMBOL_REF:
3042 case LABEL_REF:
3043 return 0;
3045 case REG:
3046 return reg_equiv[REGNO (x)].replace == 0 && rtx_varies_p (x, 0);
3048 case ASM_OPERANDS:
3049 if (MEM_VOLATILE_P (x))
3050 return 1;
3052 /* Fall through. */
3054 default:
3055 break;
3058 fmt = GET_RTX_FORMAT (code);
3059 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3060 if (fmt[i] == 'e')
3062 if (equiv_init_varies_p (XEXP (x, i)))
3063 return 1;
3065 else if (fmt[i] == 'E')
3067 int j;
3068 for (j = 0; j < XVECLEN (x, i); j++)
3069 if (equiv_init_varies_p (XVECEXP (x, i, j)))
3070 return 1;
3073 return 0;
3076 /* Returns nonzero if X (used to initialize register REGNO) is movable.
3077 X is only movable if the registers it uses have equivalent initializations
3078 which appear to be within the same loop (or in an inner loop) and movable
3079 or if they are not candidates for local_alloc and don't vary. */
3080 static int
3081 equiv_init_movable_p (rtx x, int regno)
3083 int i, j;
3084 const char *fmt;
3085 enum rtx_code code = GET_CODE (x);
3087 switch (code)
3089 case SET:
3090 return equiv_init_movable_p (SET_SRC (x), regno);
3092 case CC0:
3093 case CLOBBER:
3094 return 0;
3096 case PRE_INC:
3097 case PRE_DEC:
3098 case POST_INC:
3099 case POST_DEC:
3100 case PRE_MODIFY:
3101 case POST_MODIFY:
3102 return 0;
3104 case REG:
3105 return ((reg_equiv[REGNO (x)].loop_depth >= reg_equiv[regno].loop_depth
3106 && reg_equiv[REGNO (x)].replace)
3107 || (REG_BASIC_BLOCK (REGNO (x)) < NUM_FIXED_BLOCKS
3108 && ! rtx_varies_p (x, 0)));
3110 case UNSPEC_VOLATILE:
3111 return 0;
3113 case ASM_OPERANDS:
3114 if (MEM_VOLATILE_P (x))
3115 return 0;
3117 /* Fall through. */
3119 default:
3120 break;
3123 fmt = GET_RTX_FORMAT (code);
3124 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3125 switch (fmt[i])
3127 case 'e':
3128 if (! equiv_init_movable_p (XEXP (x, i), regno))
3129 return 0;
3130 break;
3131 case 'E':
3132 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3133 if (! equiv_init_movable_p (XVECEXP (x, i, j), regno))
3134 return 0;
3135 break;
3138 return 1;
3141 /* TRUE if X uses any registers for which reg_equiv[REGNO].replace is
3142 true. */
3143 static int
3144 contains_replace_regs (rtx x)
3146 int i, j;
3147 const char *fmt;
3148 enum rtx_code code = GET_CODE (x);
3150 switch (code)
3152 case CONST:
3153 case LABEL_REF:
3154 case SYMBOL_REF:
3155 CASE_CONST_ANY:
3156 case PC:
3157 case CC0:
3158 case HIGH:
3159 return 0;
3161 case REG:
3162 return reg_equiv[REGNO (x)].replace;
3164 default:
3165 break;
3168 fmt = GET_RTX_FORMAT (code);
3169 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3170 switch (fmt[i])
3172 case 'e':
3173 if (contains_replace_regs (XEXP (x, i)))
3174 return 1;
3175 break;
3176 case 'E':
3177 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3178 if (contains_replace_regs (XVECEXP (x, i, j)))
3179 return 1;
3180 break;
3183 return 0;
3186 /* TRUE if X references a memory location that would be affected by a store
3187 to MEMREF. */
3188 static int
3189 memref_referenced_p (rtx memref, rtx x)
3191 int i, j;
3192 const char *fmt;
3193 enum rtx_code code = GET_CODE (x);
3195 switch (code)
3197 case CONST:
3198 case LABEL_REF:
3199 case SYMBOL_REF:
3200 CASE_CONST_ANY:
3201 case PC:
3202 case CC0:
3203 case HIGH:
3204 case LO_SUM:
3205 return 0;
3207 case REG:
3208 return (reg_equiv[REGNO (x)].replacement
3209 && memref_referenced_p (memref,
3210 reg_equiv[REGNO (x)].replacement));
3212 case MEM:
3213 if (true_dependence (memref, VOIDmode, x))
3214 return 1;
3215 break;
3217 case SET:
3218 /* If we are setting a MEM, it doesn't count (its address does), but any
3219 other SET_DEST that has a MEM in it is referencing the MEM. */
3220 if (MEM_P (SET_DEST (x)))
3222 if (memref_referenced_p (memref, XEXP (SET_DEST (x), 0)))
3223 return 1;
3225 else if (memref_referenced_p (memref, SET_DEST (x)))
3226 return 1;
3228 return memref_referenced_p (memref, SET_SRC (x));
3230 default:
3231 break;
3234 fmt = GET_RTX_FORMAT (code);
3235 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3236 switch (fmt[i])
3238 case 'e':
3239 if (memref_referenced_p (memref, XEXP (x, i)))
3240 return 1;
3241 break;
3242 case 'E':
3243 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3244 if (memref_referenced_p (memref, XVECEXP (x, i, j)))
3245 return 1;
3246 break;
3249 return 0;
3252 /* TRUE if some insn in the range (START, END] references a memory location
3253 that would be affected by a store to MEMREF. */
3254 static int
3255 memref_used_between_p (rtx memref, rtx_insn *start, rtx_insn *end)
3257 rtx_insn *insn;
3259 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
3260 insn = NEXT_INSN (insn))
3262 if (!NONDEBUG_INSN_P (insn))
3263 continue;
3265 if (memref_referenced_p (memref, PATTERN (insn)))
3266 return 1;
3268 /* Nonconst functions may access memory. */
3269 if (CALL_P (insn) && (! RTL_CONST_CALL_P (insn)))
3270 return 1;
3273 return 0;
3276 /* Mark REG as having no known equivalence.
3277 Some instructions might have been processed before and furnished
3278 with REG_EQUIV notes for this register; these notes will have to be
3279 removed.
3280 STORE is the piece of RTL that does the non-constant / conflicting
3281 assignment - a SET, CLOBBER or REG_INC note. It is currently not used,
3282 but needs to be there because this function is called from note_stores. */
3283 static void
3284 no_equiv (rtx reg, const_rtx store ATTRIBUTE_UNUSED,
3285 void *data ATTRIBUTE_UNUSED)
3287 int regno;
3288 rtx_insn_list *list;
3290 if (!REG_P (reg))
3291 return;
3292 regno = REGNO (reg);
3293 reg_equiv[regno].no_equiv = 1;
3294 list = reg_equiv[regno].init_insns;
3295 if (list && list->insn () == NULL)
3296 return;
3297 reg_equiv[regno].init_insns = gen_rtx_INSN_LIST (VOIDmode, NULL_RTX, NULL);
3298 reg_equiv[regno].replacement = NULL_RTX;
3299 /* This doesn't matter for equivalences made for argument registers, we
3300 should keep their initialization insns. */
3301 if (reg_equiv[regno].is_arg_equivalence)
3302 return;
3303 ira_reg_equiv[regno].defined_p = false;
3304 ira_reg_equiv[regno].init_insns = NULL;
3305 for (; list; list = list->next ())
3307 rtx_insn *insn = list->insn ();
3308 remove_note (insn, find_reg_note (insn, REG_EQUIV, NULL_RTX));
3312 /* Check whether the SUBREG is a paradoxical subreg and set the result
3313 in PDX_SUBREGS. */
3315 static void
3316 set_paradoxical_subreg (rtx_insn *insn, bool *pdx_subregs)
3318 subrtx_iterator::array_type array;
3319 FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
3321 const_rtx subreg = *iter;
3322 if (GET_CODE (subreg) == SUBREG)
3324 const_rtx reg = SUBREG_REG (subreg);
3325 if (REG_P (reg) && paradoxical_subreg_p (subreg))
3326 pdx_subregs[REGNO (reg)] = true;
3331 /* In DEBUG_INSN location adjust REGs from CLEARED_REGS bitmap to the
3332 equivalent replacement. */
3334 static rtx
3335 adjust_cleared_regs (rtx loc, const_rtx old_rtx ATTRIBUTE_UNUSED, void *data)
3337 if (REG_P (loc))
3339 bitmap cleared_regs = (bitmap) data;
3340 if (bitmap_bit_p (cleared_regs, REGNO (loc)))
3341 return simplify_replace_fn_rtx (copy_rtx (*reg_equiv[REGNO (loc)].src_p),
3342 NULL_RTX, adjust_cleared_regs, data);
3344 return NULL_RTX;
3347 /* Nonzero if we recorded an equivalence for a LABEL_REF. */
3348 static int recorded_label_ref;
3350 /* Find registers that are equivalent to a single value throughout the
3351 compilation (either because they can be referenced in memory or are
3352 set once from a single constant). Lower their priority for a
3353 register.
3355 If such a register is only referenced once, try substituting its
3356 value into the using insn. If it succeeds, we can eliminate the
3357 register completely.
3359 Initialize init_insns in ira_reg_equiv array.
3361 Return non-zero if jump label rebuilding should be done. */
3362 static int
3363 update_equiv_regs (void)
3365 rtx_insn *insn;
3366 basic_block bb;
3367 int loop_depth;
3368 bitmap cleared_regs;
3369 bool *pdx_subregs;
3371 /* We need to keep track of whether or not we recorded a LABEL_REF so
3372 that we know if the jump optimizer needs to be rerun. */
3373 recorded_label_ref = 0;
3375 /* Use pdx_subregs to show whether a reg is used in a paradoxical
3376 subreg. */
3377 pdx_subregs = XCNEWVEC (bool, max_regno);
3379 reg_equiv = XCNEWVEC (struct equivalence, max_regno);
3380 grow_reg_equivs ();
3382 init_alias_analysis ();
3384 /* Scan insns and set pdx_subregs[regno] if the reg is used in a
3385 paradoxical subreg. Don't set such reg equivalent to a mem,
3386 because lra will not substitute such equiv memory in order to
3387 prevent access beyond allocated memory for paradoxical memory subreg. */
3388 FOR_EACH_BB_FN (bb, cfun)
3389 FOR_BB_INSNS (bb, insn)
3390 if (NONDEBUG_INSN_P (insn))
3391 set_paradoxical_subreg (insn, pdx_subregs);
3393 /* Scan the insns and find which registers have equivalences. Do this
3394 in a separate scan of the insns because (due to -fcse-follow-jumps)
3395 a register can be set below its use. */
3396 FOR_EACH_BB_FN (bb, cfun)
3398 loop_depth = bb_loop_depth (bb);
3400 for (insn = BB_HEAD (bb);
3401 insn != NEXT_INSN (BB_END (bb));
3402 insn = NEXT_INSN (insn))
3404 rtx note;
3405 rtx set;
3406 rtx dest, src;
3407 int regno;
3409 if (! INSN_P (insn))
3410 continue;
3412 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
3413 if (REG_NOTE_KIND (note) == REG_INC)
3414 no_equiv (XEXP (note, 0), note, NULL);
3416 set = single_set (insn);
3418 /* If this insn contains more (or less) than a single SET,
3419 only mark all destinations as having no known equivalence. */
3420 if (set == NULL_RTX)
3422 note_stores (PATTERN (insn), no_equiv, NULL);
3423 continue;
3425 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3427 int i;
3429 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
3431 rtx part = XVECEXP (PATTERN (insn), 0, i);
3432 if (part != set)
3433 note_stores (part, no_equiv, NULL);
3437 dest = SET_DEST (set);
3438 src = SET_SRC (set);
3440 /* See if this is setting up the equivalence between an argument
3441 register and its stack slot. */
3442 note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
3443 if (note)
3445 gcc_assert (REG_P (dest));
3446 regno = REGNO (dest);
3448 /* Note that we don't want to clear init_insns in
3449 ira_reg_equiv even if there are multiple sets of this
3450 register. */
3451 reg_equiv[regno].is_arg_equivalence = 1;
3453 /* The insn result can have equivalence memory although
3454 the equivalence is not set up by the insn. We add
3455 this insn to init insns as it is a flag for now that
3456 regno has an equivalence. We will remove the insn
3457 from init insn list later. */
3458 if (rtx_equal_p (src, XEXP (note, 0)) || MEM_P (XEXP (note, 0)))
3459 ira_reg_equiv[regno].init_insns
3460 = gen_rtx_INSN_LIST (VOIDmode, insn,
3461 ira_reg_equiv[regno].init_insns);
3463 /* Continue normally in case this is a candidate for
3464 replacements. */
3467 if (!optimize)
3468 continue;
3470 /* We only handle the case of a pseudo register being set
3471 once, or always to the same value. */
3472 /* ??? The mn10200 port breaks if we add equivalences for
3473 values that need an ADDRESS_REGS register and set them equivalent
3474 to a MEM of a pseudo. The actual problem is in the over-conservative
3475 handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
3476 calculate_needs, but we traditionally work around this problem
3477 here by rejecting equivalences when the destination is in a register
3478 that's likely spilled. This is fragile, of course, since the
3479 preferred class of a pseudo depends on all instructions that set
3480 or use it. */
3482 if (!REG_P (dest)
3483 || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER
3484 || (reg_equiv[regno].init_insns
3485 && reg_equiv[regno].init_insns->insn () == NULL)
3486 || (targetm.class_likely_spilled_p (reg_preferred_class (regno))
3487 && MEM_P (src) && ! reg_equiv[regno].is_arg_equivalence))
3489 /* This might be setting a SUBREG of a pseudo, a pseudo that is
3490 also set somewhere else to a constant. */
3491 note_stores (set, no_equiv, NULL);
3492 continue;
3495 /* Don't set reg (if pdx_subregs[regno] == true) equivalent to a mem. */
3496 if (MEM_P (src) && pdx_subregs[regno])
3498 note_stores (set, no_equiv, NULL);
3499 continue;
3502 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
3504 /* cse sometimes generates function invariants, but doesn't put a
3505 REG_EQUAL note on the insn. Since this note would be redundant,
3506 there's no point creating it earlier than here. */
3507 if (! note && ! rtx_varies_p (src, 0))
3508 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
3510 /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
3511 since it represents a function call. */
3512 if (note && GET_CODE (XEXP (note, 0)) == EXPR_LIST)
3513 note = NULL_RTX;
3515 if (DF_REG_DEF_COUNT (regno) != 1)
3517 bool equal_p = true;
3518 rtx_insn_list *list;
3520 /* If we have already processed this pseudo and determined it
3521 can not have an equivalence, then honor that decision. */
3522 if (reg_equiv[regno].no_equiv)
3523 continue;
3525 if (! note
3526 || rtx_varies_p (XEXP (note, 0), 0)
3527 || (reg_equiv[regno].replacement
3528 && ! rtx_equal_p (XEXP (note, 0),
3529 reg_equiv[regno].replacement)))
3531 no_equiv (dest, set, NULL);
3532 continue;
3535 list = reg_equiv[regno].init_insns;
3536 for (; list; list = list->next ())
3538 rtx note_tmp;
3539 rtx_insn *insn_tmp;
3541 insn_tmp = list->insn ();
3542 note_tmp = find_reg_note (insn_tmp, REG_EQUAL, NULL_RTX);
3543 gcc_assert (note_tmp);
3544 if (! rtx_equal_p (XEXP (note, 0), XEXP (note_tmp, 0)))
3546 equal_p = false;
3547 break;
3551 if (! equal_p)
3553 no_equiv (dest, set, NULL);
3554 continue;
3558 /* Record this insn as initializing this register. */
3559 reg_equiv[regno].init_insns
3560 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv[regno].init_insns);
3562 /* If this register is known to be equal to a constant, record that
3563 it is always equivalent to the constant. */
3564 if (DF_REG_DEF_COUNT (regno) == 1
3565 && note && ! rtx_varies_p (XEXP (note, 0), 0))
3567 rtx note_value = XEXP (note, 0);
3568 remove_note (insn, note);
3569 set_unique_reg_note (insn, REG_EQUIV, note_value);
3572 /* If this insn introduces a "constant" register, decrease the priority
3573 of that register. Record this insn if the register is only used once
3574 more and the equivalence value is the same as our source.
3576 The latter condition is checked for two reasons: First, it is an
3577 indication that it may be more efficient to actually emit the insn
3578 as written (if no registers are available, reload will substitute
3579 the equivalence). Secondly, it avoids problems with any registers
3580 dying in this insn whose death notes would be missed.
3582 If we don't have a REG_EQUIV note, see if this insn is loading
3583 a register used only in one basic block from a MEM. If so, and the
3584 MEM remains unchanged for the life of the register, add a REG_EQUIV
3585 note. */
3586 note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
3588 if (note == NULL_RTX && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
3589 && MEM_P (SET_SRC (set))
3590 && validate_equiv_mem (insn, dest, SET_SRC (set)))
3591 note = set_unique_reg_note (insn, REG_EQUIV, copy_rtx (SET_SRC (set)));
3593 if (note)
3595 int regno = REGNO (dest);
3596 rtx x = XEXP (note, 0);
3598 /* If we haven't done so, record for reload that this is an
3599 equivalencing insn. */
3600 if (!reg_equiv[regno].is_arg_equivalence)
3601 ira_reg_equiv[regno].init_insns
3602 = gen_rtx_INSN_LIST (VOIDmode, insn,
3603 ira_reg_equiv[regno].init_insns);
3605 /* Record whether or not we created a REG_EQUIV note for a LABEL_REF.
3606 We might end up substituting the LABEL_REF for uses of the
3607 pseudo here or later. That kind of transformation may turn an
3608 indirect jump into a direct jump, in which case we must rerun the
3609 jump optimizer to ensure that the JUMP_LABEL fields are valid. */
3610 if (GET_CODE (x) == LABEL_REF
3611 || (GET_CODE (x) == CONST
3612 && GET_CODE (XEXP (x, 0)) == PLUS
3613 && (GET_CODE (XEXP (XEXP (x, 0), 0)) == LABEL_REF)))
3614 recorded_label_ref = 1;
3616 reg_equiv[regno].replacement = x;
3617 reg_equiv[regno].src_p = &SET_SRC (set);
3618 reg_equiv[regno].loop_depth = (short) loop_depth;
3620 /* Don't mess with things live during setjmp. */
3621 if (REG_LIVE_LENGTH (regno) >= 0 && optimize)
3623 /* Note that the statement below does not affect the priority
3624 in local-alloc! */
3625 REG_LIVE_LENGTH (regno) *= 2;
3627 /* If the register is referenced exactly twice, meaning it is
3628 set once and used once, indicate that the reference may be
3629 replaced by the equivalence we computed above. Do this
3630 even if the register is only used in one block so that
3631 dependencies can be handled where the last register is
3632 used in a different block (i.e. HIGH / LO_SUM sequences)
3633 and to reduce the number of registers alive across
3634 calls. */
3636 if (REG_N_REFS (regno) == 2
3637 && (rtx_equal_p (x, src)
3638 || ! equiv_init_varies_p (src))
3639 && NONJUMP_INSN_P (insn)
3640 && equiv_init_movable_p (PATTERN (insn), regno))
3641 reg_equiv[regno].replace = 1;
3647 if (!optimize)
3648 goto out;
3650 /* A second pass, to gather additional equivalences with memory. This needs
3651 to be done after we know which registers we are going to replace. */
3653 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
3655 rtx set, src, dest;
3656 unsigned regno;
3658 if (! INSN_P (insn))
3659 continue;
3661 set = single_set (insn);
3662 if (! set)
3663 continue;
3665 dest = SET_DEST (set);
3666 src = SET_SRC (set);
3668 /* If this sets a MEM to the contents of a REG that is only used
3669 in a single basic block, see if the register is always equivalent
3670 to that memory location and if moving the store from INSN to the
3671 insn that set REG is safe. If so, put a REG_EQUIV note on the
3672 initializing insn.
3674 Don't add a REG_EQUIV note if the insn already has one. The existing
3675 REG_EQUIV is likely more useful than the one we are adding.
3677 If one of the regs in the address has reg_equiv[REGNO].replace set,
3678 then we can't add this REG_EQUIV note. The reg_equiv[REGNO].replace
3679 optimization may move the set of this register immediately before
3680 insn, which puts it after reg_equiv[REGNO].init_insns, and hence
3681 the mention in the REG_EQUIV note would be to an uninitialized
3682 pseudo. */
3684 if (MEM_P (dest) && REG_P (src)
3685 && (regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
3686 && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
3687 && DF_REG_DEF_COUNT (regno) == 1
3688 && reg_equiv[regno].init_insns != NULL
3689 && reg_equiv[regno].init_insns->insn () != NULL
3690 && ! find_reg_note (XEXP (reg_equiv[regno].init_insns, 0),
3691 REG_EQUIV, NULL_RTX)
3692 && ! contains_replace_regs (XEXP (dest, 0))
3693 && ! pdx_subregs[regno])
3695 rtx_insn *init_insn =
3696 as_a <rtx_insn *> (XEXP (reg_equiv[regno].init_insns, 0));
3697 if (validate_equiv_mem (init_insn, src, dest)
3698 && ! memref_used_between_p (dest, init_insn, insn)
3699 /* Attaching a REG_EQUIV note will fail if INIT_INSN has
3700 multiple sets. */
3701 && set_unique_reg_note (init_insn, REG_EQUIV, copy_rtx (dest)))
3703 /* This insn makes the equivalence, not the one initializing
3704 the register. */
3705 ira_reg_equiv[regno].init_insns
3706 = gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
3707 df_notes_rescan (init_insn);
3712 cleared_regs = BITMAP_ALLOC (NULL);
3713 /* Now scan all regs killed in an insn to see if any of them are
3714 registers only used that once. If so, see if we can replace the
3715 reference with the equivalent form. If we can, delete the
3716 initializing reference and this register will go away. If we
3717 can't replace the reference, and the initializing reference is
3718 within the same loop (or in an inner loop), then move the register
3719 initialization just before the use, so that they are in the same
3720 basic block. */
3721 FOR_EACH_BB_REVERSE_FN (bb, cfun)
3723 loop_depth = bb_loop_depth (bb);
3724 for (insn = BB_END (bb);
3725 insn != PREV_INSN (BB_HEAD (bb));
3726 insn = PREV_INSN (insn))
3728 rtx link;
3730 if (! INSN_P (insn))
3731 continue;
3733 /* Don't substitute into a non-local goto, this confuses CFG. */
3734 if (JUMP_P (insn)
3735 && find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
3736 continue;
3738 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3740 if (REG_NOTE_KIND (link) == REG_DEAD
3741 /* Make sure this insn still refers to the register. */
3742 && reg_mentioned_p (XEXP (link, 0), PATTERN (insn)))
3744 int regno = REGNO (XEXP (link, 0));
3745 rtx equiv_insn;
3747 if (! reg_equiv[regno].replace
3748 || reg_equiv[regno].loop_depth < (short) loop_depth
3749 /* There is no sense to move insns if live range
3750 shrinkage or register pressure-sensitive
3751 scheduling were done because it will not
3752 improve allocation but worsen insn schedule
3753 with a big probability. */
3754 || flag_live_range_shrinkage
3755 || (flag_sched_pressure && flag_schedule_insns))
3756 continue;
3758 /* reg_equiv[REGNO].replace gets set only when
3759 REG_N_REFS[REGNO] is 2, i.e. the register is set
3760 once and used once. (If it were only set, but
3761 not used, flow would have deleted the setting
3762 insns.) Hence there can only be one insn in
3763 reg_equiv[REGNO].init_insns. */
3764 gcc_assert (reg_equiv[regno].init_insns
3765 && !XEXP (reg_equiv[regno].init_insns, 1));
3766 equiv_insn = XEXP (reg_equiv[regno].init_insns, 0);
3768 /* We may not move instructions that can throw, since
3769 that changes basic block boundaries and we are not
3770 prepared to adjust the CFG to match. */
3771 if (can_throw_internal (equiv_insn))
3772 continue;
3774 if (asm_noperands (PATTERN (equiv_insn)) < 0
3775 && validate_replace_rtx (regno_reg_rtx[regno],
3776 *(reg_equiv[regno].src_p), insn))
3778 rtx equiv_link;
3779 rtx last_link;
3780 rtx note;
3782 /* Find the last note. */
3783 for (last_link = link; XEXP (last_link, 1);
3784 last_link = XEXP (last_link, 1))
3787 /* Append the REG_DEAD notes from equiv_insn. */
3788 equiv_link = REG_NOTES (equiv_insn);
3789 while (equiv_link)
3791 note = equiv_link;
3792 equiv_link = XEXP (equiv_link, 1);
3793 if (REG_NOTE_KIND (note) == REG_DEAD)
3795 remove_note (equiv_insn, note);
3796 XEXP (last_link, 1) = note;
3797 XEXP (note, 1) = NULL_RTX;
3798 last_link = note;
3802 remove_death (regno, insn);
3803 SET_REG_N_REFS (regno, 0);
3804 REG_FREQ (regno) = 0;
3805 delete_insn (equiv_insn);
3807 reg_equiv[regno].init_insns
3808 = reg_equiv[regno].init_insns->next ();
3810 ira_reg_equiv[regno].init_insns = NULL;
3811 bitmap_set_bit (cleared_regs, regno);
3813 /* Move the initialization of the register to just before
3814 INSN. Update the flow information. */
3815 else if (prev_nondebug_insn (insn) != equiv_insn)
3817 rtx_insn *new_insn;
3819 new_insn = emit_insn_before (PATTERN (equiv_insn), insn);
3820 REG_NOTES (new_insn) = REG_NOTES (equiv_insn);
3821 REG_NOTES (equiv_insn) = 0;
3822 /* Rescan it to process the notes. */
3823 df_insn_rescan (new_insn);
3825 /* Make sure this insn is recognized before
3826 reload begins, otherwise
3827 eliminate_regs_in_insn will die. */
3828 INSN_CODE (new_insn) = INSN_CODE (equiv_insn);
3830 delete_insn (equiv_insn);
3832 XEXP (reg_equiv[regno].init_insns, 0) = new_insn;
3834 REG_BASIC_BLOCK (regno) = bb->index;
3835 REG_N_CALLS_CROSSED (regno) = 0;
3836 REG_FREQ_CALLS_CROSSED (regno) = 0;
3837 REG_N_THROWING_CALLS_CROSSED (regno) = 0;
3838 REG_LIVE_LENGTH (regno) = 2;
3840 if (insn == BB_HEAD (bb))
3841 BB_HEAD (bb) = PREV_INSN (insn);
3843 ira_reg_equiv[regno].init_insns
3844 = gen_rtx_INSN_LIST (VOIDmode, new_insn, NULL_RTX);
3845 bitmap_set_bit (cleared_regs, regno);
3852 if (!bitmap_empty_p (cleared_regs))
3854 FOR_EACH_BB_FN (bb, cfun)
3856 bitmap_and_compl_into (DF_LR_IN (bb), cleared_regs);
3857 bitmap_and_compl_into (DF_LR_OUT (bb), cleared_regs);
3858 if (! df_live)
3859 continue;
3860 bitmap_and_compl_into (DF_LIVE_IN (bb), cleared_regs);
3861 bitmap_and_compl_into (DF_LIVE_OUT (bb), cleared_regs);
3864 /* Last pass - adjust debug insns referencing cleared regs. */
3865 if (MAY_HAVE_DEBUG_INSNS)
3866 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
3867 if (DEBUG_INSN_P (insn))
3869 rtx old_loc = INSN_VAR_LOCATION_LOC (insn);
3870 INSN_VAR_LOCATION_LOC (insn)
3871 = simplify_replace_fn_rtx (old_loc, NULL_RTX,
3872 adjust_cleared_regs,
3873 (void *) cleared_regs);
3874 if (old_loc != INSN_VAR_LOCATION_LOC (insn))
3875 df_insn_rescan (insn);
3879 BITMAP_FREE (cleared_regs);
3881 out:
3882 /* Clean up. */
3884 end_alias_analysis ();
3885 free (reg_equiv);
3886 free (pdx_subregs);
3887 return recorded_label_ref;
3892 /* Set up fields memory, constant, and invariant from init_insns in
3893 the structures of array ira_reg_equiv. */
3894 static void
3895 setup_reg_equiv (void)
3897 int i;
3898 rtx_insn_list *elem, *prev_elem, *next_elem;
3899 rtx_insn *insn;
3900 rtx set, x;
3902 for (i = FIRST_PSEUDO_REGISTER; i < ira_reg_equiv_len; i++)
3903 for (prev_elem = NULL, elem = ira_reg_equiv[i].init_insns;
3904 elem;
3905 prev_elem = elem, elem = next_elem)
3907 next_elem = elem->next ();
3908 insn = elem->insn ();
3909 set = single_set (insn);
3911 /* Init insns can set up equivalence when the reg is a destination or
3912 a source (in this case the destination is memory). */
3913 if (set != 0 && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))))
3915 if ((x = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != NULL)
3917 x = XEXP (x, 0);
3918 if (REG_P (SET_DEST (set))
3919 && REGNO (SET_DEST (set)) == (unsigned int) i
3920 && ! rtx_equal_p (SET_SRC (set), x) && MEM_P (x))
3922 /* This insn reporting the equivalence but
3923 actually not setting it. Remove it from the
3924 list. */
3925 if (prev_elem == NULL)
3926 ira_reg_equiv[i].init_insns = next_elem;
3927 else
3928 XEXP (prev_elem, 1) = next_elem;
3929 elem = prev_elem;
3932 else if (REG_P (SET_DEST (set))
3933 && REGNO (SET_DEST (set)) == (unsigned int) i)
3934 x = SET_SRC (set);
3935 else
3937 gcc_assert (REG_P (SET_SRC (set))
3938 && REGNO (SET_SRC (set)) == (unsigned int) i);
3939 x = SET_DEST (set);
3941 if (! function_invariant_p (x)
3942 || ! flag_pic
3943 /* A function invariant is often CONSTANT_P but may
3944 include a register. We promise to only pass
3945 CONSTANT_P objects to LEGITIMATE_PIC_OPERAND_P. */
3946 || (CONSTANT_P (x) && LEGITIMATE_PIC_OPERAND_P (x)))
3948 /* It can happen that a REG_EQUIV note contains a MEM
3949 that is not a legitimate memory operand. As later
3950 stages of reload assume that all addresses found in
3951 the lra_regno_equiv_* arrays were originally
3952 legitimate, we ignore such REG_EQUIV notes. */
3953 if (memory_operand (x, VOIDmode))
3955 ira_reg_equiv[i].defined_p = true;
3956 ira_reg_equiv[i].memory = x;
3957 continue;
3959 else if (function_invariant_p (x))
3961 machine_mode mode;
3963 mode = GET_MODE (SET_DEST (set));
3964 if (GET_CODE (x) == PLUS
3965 || x == frame_pointer_rtx || x == arg_pointer_rtx)
3966 /* This is PLUS of frame pointer and a constant,
3967 or fp, or argp. */
3968 ira_reg_equiv[i].invariant = x;
3969 else if (targetm.legitimate_constant_p (mode, x))
3970 ira_reg_equiv[i].constant = x;
3971 else
3973 ira_reg_equiv[i].memory = force_const_mem (mode, x);
3974 if (ira_reg_equiv[i].memory == NULL_RTX)
3976 ira_reg_equiv[i].defined_p = false;
3977 ira_reg_equiv[i].init_insns = NULL;
3978 break;
3981 ira_reg_equiv[i].defined_p = true;
3982 continue;
3986 ira_reg_equiv[i].defined_p = false;
3987 ira_reg_equiv[i].init_insns = NULL;
3988 break;
3994 /* Print chain C to FILE. */
3995 static void
3996 print_insn_chain (FILE *file, struct insn_chain *c)
3998 fprintf (file, "insn=%d, ", INSN_UID (c->insn));
3999 bitmap_print (file, &c->live_throughout, "live_throughout: ", ", ");
4000 bitmap_print (file, &c->dead_or_set, "dead_or_set: ", "\n");
4004 /* Print all reload_insn_chains to FILE. */
4005 static void
4006 print_insn_chains (FILE *file)
4008 struct insn_chain *c;
4009 for (c = reload_insn_chain; c ; c = c->next)
4010 print_insn_chain (file, c);
4013 /* Return true if pseudo REGNO should be added to set live_throughout
4014 or dead_or_set of the insn chains for reload consideration. */
4015 static bool
4016 pseudo_for_reload_consideration_p (int regno)
4018 /* Consider spilled pseudos too for IRA because they still have a
4019 chance to get hard-registers in the reload when IRA is used. */
4020 return (reg_renumber[regno] >= 0 || ira_conflicts_p);
4023 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
4024 REG to the number of nregs, and INIT_VALUE to get the
4025 initialization. ALLOCNUM need not be the regno of REG. */
4026 static void
4027 init_live_subregs (bool init_value, sbitmap *live_subregs,
4028 bitmap live_subregs_used, int allocnum, rtx reg)
4030 unsigned int regno = REGNO (SUBREG_REG (reg));
4031 int size = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno]));
4033 gcc_assert (size > 0);
4035 /* Been there, done that. */
4036 if (bitmap_bit_p (live_subregs_used, allocnum))
4037 return;
4039 /* Create a new one. */
4040 if (live_subregs[allocnum] == NULL)
4041 live_subregs[allocnum] = sbitmap_alloc (size);
4043 /* If the entire reg was live before blasting into subregs, we need
4044 to init all of the subregs to ones else init to 0. */
4045 if (init_value)
4046 bitmap_ones (live_subregs[allocnum]);
4047 else
4048 bitmap_clear (live_subregs[allocnum]);
4050 bitmap_set_bit (live_subregs_used, allocnum);
4053 /* Walk the insns of the current function and build reload_insn_chain,
4054 and record register life information. */
4055 static void
4056 build_insn_chain (void)
4058 unsigned int i;
4059 struct insn_chain **p = &reload_insn_chain;
4060 basic_block bb;
4061 struct insn_chain *c = NULL;
4062 struct insn_chain *next = NULL;
4063 bitmap live_relevant_regs = BITMAP_ALLOC (NULL);
4064 bitmap elim_regset = BITMAP_ALLOC (NULL);
4065 /* live_subregs is a vector used to keep accurate information about
4066 which hardregs are live in multiword pseudos. live_subregs and
4067 live_subregs_used are indexed by pseudo number. The live_subreg
4068 entry for a particular pseudo is only used if the corresponding
4069 element is non zero in live_subregs_used. The sbitmap size of
4070 live_subreg[allocno] is number of bytes that the pseudo can
4071 occupy. */
4072 sbitmap *live_subregs = XCNEWVEC (sbitmap, max_regno);
4073 bitmap live_subregs_used = BITMAP_ALLOC (NULL);
4075 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4076 if (TEST_HARD_REG_BIT (eliminable_regset, i))
4077 bitmap_set_bit (elim_regset, i);
4078 FOR_EACH_BB_REVERSE_FN (bb, cfun)
4080 bitmap_iterator bi;
4081 rtx_insn *insn;
4083 CLEAR_REG_SET (live_relevant_regs);
4084 bitmap_clear (live_subregs_used);
4086 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb), 0, i, bi)
4088 if (i >= FIRST_PSEUDO_REGISTER)
4089 break;
4090 bitmap_set_bit (live_relevant_regs, i);
4093 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb),
4094 FIRST_PSEUDO_REGISTER, i, bi)
4096 if (pseudo_for_reload_consideration_p (i))
4097 bitmap_set_bit (live_relevant_regs, i);
4100 FOR_BB_INSNS_REVERSE (bb, insn)
4102 if (!NOTE_P (insn) && !BARRIER_P (insn))
4104 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4105 df_ref def, use;
4107 c = new_insn_chain ();
4108 c->next = next;
4109 next = c;
4110 *p = c;
4111 p = &c->prev;
4113 c->insn = insn;
4114 c->block = bb->index;
4116 if (NONDEBUG_INSN_P (insn))
4117 FOR_EACH_INSN_INFO_DEF (def, insn_info)
4119 unsigned int regno = DF_REF_REGNO (def);
4121 /* Ignore may clobbers because these are generated
4122 from calls. However, every other kind of def is
4123 added to dead_or_set. */
4124 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
4126 if (regno < FIRST_PSEUDO_REGISTER)
4128 if (!fixed_regs[regno])
4129 bitmap_set_bit (&c->dead_or_set, regno);
4131 else if (pseudo_for_reload_consideration_p (regno))
4132 bitmap_set_bit (&c->dead_or_set, regno);
4135 if ((regno < FIRST_PSEUDO_REGISTER
4136 || reg_renumber[regno] >= 0
4137 || ira_conflicts_p)
4138 && (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)))
4140 rtx reg = DF_REF_REG (def);
4142 /* We can model subregs, but not if they are
4143 wrapped in ZERO_EXTRACTS. */
4144 if (GET_CODE (reg) == SUBREG
4145 && !DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT))
4147 unsigned int start = SUBREG_BYTE (reg);
4148 unsigned int last = start
4149 + GET_MODE_SIZE (GET_MODE (reg));
4151 init_live_subregs
4152 (bitmap_bit_p (live_relevant_regs, regno),
4153 live_subregs, live_subregs_used, regno, reg);
4155 if (!DF_REF_FLAGS_IS_SET
4156 (def, DF_REF_STRICT_LOW_PART))
4158 /* Expand the range to cover entire words.
4159 Bytes added here are "don't care". */
4160 start
4161 = start / UNITS_PER_WORD * UNITS_PER_WORD;
4162 last = ((last + UNITS_PER_WORD - 1)
4163 / UNITS_PER_WORD * UNITS_PER_WORD);
4166 /* Ignore the paradoxical bits. */
4167 if (last > SBITMAP_SIZE (live_subregs[regno]))
4168 last = SBITMAP_SIZE (live_subregs[regno]);
4170 while (start < last)
4172 bitmap_clear_bit (live_subregs[regno], start);
4173 start++;
4176 if (bitmap_empty_p (live_subregs[regno]))
4178 bitmap_clear_bit (live_subregs_used, regno);
4179 bitmap_clear_bit (live_relevant_regs, regno);
4181 else
4182 /* Set live_relevant_regs here because
4183 that bit has to be true to get us to
4184 look at the live_subregs fields. */
4185 bitmap_set_bit (live_relevant_regs, regno);
4187 else
4189 /* DF_REF_PARTIAL is generated for
4190 subregs, STRICT_LOW_PART, and
4191 ZERO_EXTRACT. We handle the subreg
4192 case above so here we have to keep from
4193 modeling the def as a killing def. */
4194 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL))
4196 bitmap_clear_bit (live_subregs_used, regno);
4197 bitmap_clear_bit (live_relevant_regs, regno);
4203 bitmap_and_compl_into (live_relevant_regs, elim_regset);
4204 bitmap_copy (&c->live_throughout, live_relevant_regs);
4206 if (NONDEBUG_INSN_P (insn))
4207 FOR_EACH_INSN_INFO_USE (use, insn_info)
4209 unsigned int regno = DF_REF_REGNO (use);
4210 rtx reg = DF_REF_REG (use);
4212 /* DF_REF_READ_WRITE on a use means that this use
4213 is fabricated from a def that is a partial set
4214 to a multiword reg. Here, we only model the
4215 subreg case that is not wrapped in ZERO_EXTRACT
4216 precisely so we do not need to look at the
4217 fabricated use. */
4218 if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE)
4219 && !DF_REF_FLAGS_IS_SET (use, DF_REF_ZERO_EXTRACT)
4220 && DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG))
4221 continue;
4223 /* Add the last use of each var to dead_or_set. */
4224 if (!bitmap_bit_p (live_relevant_regs, regno))
4226 if (regno < FIRST_PSEUDO_REGISTER)
4228 if (!fixed_regs[regno])
4229 bitmap_set_bit (&c->dead_or_set, regno);
4231 else if (pseudo_for_reload_consideration_p (regno))
4232 bitmap_set_bit (&c->dead_or_set, regno);
4235 if (regno < FIRST_PSEUDO_REGISTER
4236 || pseudo_for_reload_consideration_p (regno))
4238 if (GET_CODE (reg) == SUBREG
4239 && !DF_REF_FLAGS_IS_SET (use,
4240 DF_REF_SIGN_EXTRACT
4241 | DF_REF_ZERO_EXTRACT))
4243 unsigned int start = SUBREG_BYTE (reg);
4244 unsigned int last = start
4245 + GET_MODE_SIZE (GET_MODE (reg));
4247 init_live_subregs
4248 (bitmap_bit_p (live_relevant_regs, regno),
4249 live_subregs, live_subregs_used, regno, reg);
4251 /* Ignore the paradoxical bits. */
4252 if (last > SBITMAP_SIZE (live_subregs[regno]))
4253 last = SBITMAP_SIZE (live_subregs[regno]);
4255 while (start < last)
4257 bitmap_set_bit (live_subregs[regno], start);
4258 start++;
4261 else
4262 /* Resetting the live_subregs_used is
4263 effectively saying do not use the subregs
4264 because we are reading the whole
4265 pseudo. */
4266 bitmap_clear_bit (live_subregs_used, regno);
4267 bitmap_set_bit (live_relevant_regs, regno);
4273 /* FIXME!! The following code is a disaster. Reload needs to see the
4274 labels and jump tables that are just hanging out in between
4275 the basic blocks. See pr33676. */
4276 insn = BB_HEAD (bb);
4278 /* Skip over the barriers and cruft. */
4279 while (insn && (BARRIER_P (insn) || NOTE_P (insn)
4280 || BLOCK_FOR_INSN (insn) == bb))
4281 insn = PREV_INSN (insn);
4283 /* While we add anything except barriers and notes, the focus is
4284 to get the labels and jump tables into the
4285 reload_insn_chain. */
4286 while (insn)
4288 if (!NOTE_P (insn) && !BARRIER_P (insn))
4290 if (BLOCK_FOR_INSN (insn))
4291 break;
4293 c = new_insn_chain ();
4294 c->next = next;
4295 next = c;
4296 *p = c;
4297 p = &c->prev;
4299 /* The block makes no sense here, but it is what the old
4300 code did. */
4301 c->block = bb->index;
4302 c->insn = insn;
4303 bitmap_copy (&c->live_throughout, live_relevant_regs);
4305 insn = PREV_INSN (insn);
4309 reload_insn_chain = c;
4310 *p = NULL;
4312 for (i = 0; i < (unsigned int) max_regno; i++)
4313 if (live_subregs[i] != NULL)
4314 sbitmap_free (live_subregs[i]);
4315 free (live_subregs);
4316 BITMAP_FREE (live_subregs_used);
4317 BITMAP_FREE (live_relevant_regs);
4318 BITMAP_FREE (elim_regset);
4320 if (dump_file)
4321 print_insn_chains (dump_file);
4324 /* Examine the rtx found in *LOC, which is read or written to as determined
4325 by TYPE. Return false if we find a reason why an insn containing this
4326 rtx should not be moved (such as accesses to non-constant memory), true
4327 otherwise. */
4328 static bool
4329 rtx_moveable_p (rtx *loc, enum op_type type)
4331 const char *fmt;
4332 rtx x = *loc;
4333 enum rtx_code code = GET_CODE (x);
4334 int i, j;
4336 code = GET_CODE (x);
4337 switch (code)
4339 case CONST:
4340 CASE_CONST_ANY:
4341 case SYMBOL_REF:
4342 case LABEL_REF:
4343 return true;
4345 case PC:
4346 return type == OP_IN;
4348 case CC0:
4349 return false;
4351 case REG:
4352 if (x == frame_pointer_rtx)
4353 return true;
4354 if (HARD_REGISTER_P (x))
4355 return false;
4357 return true;
4359 case MEM:
4360 if (type == OP_IN && MEM_READONLY_P (x))
4361 return rtx_moveable_p (&XEXP (x, 0), OP_IN);
4362 return false;
4364 case SET:
4365 return (rtx_moveable_p (&SET_SRC (x), OP_IN)
4366 && rtx_moveable_p (&SET_DEST (x), OP_OUT));
4368 case STRICT_LOW_PART:
4369 return rtx_moveable_p (&XEXP (x, 0), OP_OUT);
4371 case ZERO_EXTRACT:
4372 case SIGN_EXTRACT:
4373 return (rtx_moveable_p (&XEXP (x, 0), type)
4374 && rtx_moveable_p (&XEXP (x, 1), OP_IN)
4375 && rtx_moveable_p (&XEXP (x, 2), OP_IN));
4377 case CLOBBER:
4378 return rtx_moveable_p (&SET_DEST (x), OP_OUT);
4380 case UNSPEC_VOLATILE:
4381 /* It is a bad idea to consider insns with with such rtl
4382 as moveable ones. The insn scheduler also considers them as barrier
4383 for a reason. */
4384 return false;
4386 default:
4387 break;
4390 fmt = GET_RTX_FORMAT (code);
4391 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4393 if (fmt[i] == 'e')
4395 if (!rtx_moveable_p (&XEXP (x, i), type))
4396 return false;
4398 else if (fmt[i] == 'E')
4399 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4401 if (!rtx_moveable_p (&XVECEXP (x, i, j), type))
4402 return false;
4405 return true;
4408 /* A wrapper around dominated_by_p, which uses the information in UID_LUID
4409 to give dominance relationships between two insns I1 and I2. */
4410 static bool
4411 insn_dominated_by_p (rtx i1, rtx i2, int *uid_luid)
4413 basic_block bb1 = BLOCK_FOR_INSN (i1);
4414 basic_block bb2 = BLOCK_FOR_INSN (i2);
4416 if (bb1 == bb2)
4417 return uid_luid[INSN_UID (i2)] < uid_luid[INSN_UID (i1)];
4418 return dominated_by_p (CDI_DOMINATORS, bb1, bb2);
4421 /* Record the range of register numbers added by find_moveable_pseudos. */
4422 int first_moveable_pseudo, last_moveable_pseudo;
4424 /* These two vectors hold data for every register added by
4425 find_movable_pseudos, with index 0 holding data for the
4426 first_moveable_pseudo. */
4427 /* The original home register. */
4428 static vec<rtx> pseudo_replaced_reg;
4430 /* Look for instances where we have an instruction that is known to increase
4431 register pressure, and whose result is not used immediately. If it is
4432 possible to move the instruction downwards to just before its first use,
4433 split its lifetime into two ranges. We create a new pseudo to compute the
4434 value, and emit a move instruction just before the first use. If, after
4435 register allocation, the new pseudo remains unallocated, the function
4436 move_unallocated_pseudos then deletes the move instruction and places
4437 the computation just before the first use.
4439 Such a move is safe and profitable if all the input registers remain live
4440 and unchanged between the original computation and its first use. In such
4441 a situation, the computation is known to increase register pressure, and
4442 moving it is known to at least not worsen it.
4444 We restrict moves to only those cases where a register remains unallocated,
4445 in order to avoid interfering too much with the instruction schedule. As
4446 an exception, we may move insns which only modify their input register
4447 (typically induction variables), as this increases the freedom for our
4448 intended transformation, and does not limit the second instruction
4449 scheduler pass. */
4451 static void
4452 find_moveable_pseudos (void)
4454 unsigned i;
4455 int max_regs = max_reg_num ();
4456 int max_uid = get_max_uid ();
4457 basic_block bb;
4458 int *uid_luid = XNEWVEC (int, max_uid);
4459 rtx_insn **closest_uses = XNEWVEC (rtx_insn *, max_regs);
4460 /* A set of registers which are live but not modified throughout a block. */
4461 bitmap_head *bb_transp_live = XNEWVEC (bitmap_head,
4462 last_basic_block_for_fn (cfun));
4463 /* A set of registers which only exist in a given basic block. */
4464 bitmap_head *bb_local = XNEWVEC (bitmap_head,
4465 last_basic_block_for_fn (cfun));
4466 /* A set of registers which are set once, in an instruction that can be
4467 moved freely downwards, but are otherwise transparent to a block. */
4468 bitmap_head *bb_moveable_reg_sets = XNEWVEC (bitmap_head,
4469 last_basic_block_for_fn (cfun));
4470 bitmap_head live, used, set, interesting, unusable_as_input;
4471 bitmap_iterator bi;
4472 bitmap_initialize (&interesting, 0);
4474 first_moveable_pseudo = max_regs;
4475 pseudo_replaced_reg.release ();
4476 pseudo_replaced_reg.safe_grow_cleared (max_regs);
4478 df_analyze ();
4479 calculate_dominance_info (CDI_DOMINATORS);
4481 i = 0;
4482 bitmap_initialize (&live, 0);
4483 bitmap_initialize (&used, 0);
4484 bitmap_initialize (&set, 0);
4485 bitmap_initialize (&unusable_as_input, 0);
4486 FOR_EACH_BB_FN (bb, cfun)
4488 rtx_insn *insn;
4489 bitmap transp = bb_transp_live + bb->index;
4490 bitmap moveable = bb_moveable_reg_sets + bb->index;
4491 bitmap local = bb_local + bb->index;
4493 bitmap_initialize (local, 0);
4494 bitmap_initialize (transp, 0);
4495 bitmap_initialize (moveable, 0);
4496 bitmap_copy (&live, df_get_live_out (bb));
4497 bitmap_and_into (&live, df_get_live_in (bb));
4498 bitmap_copy (transp, &live);
4499 bitmap_clear (moveable);
4500 bitmap_clear (&live);
4501 bitmap_clear (&used);
4502 bitmap_clear (&set);
4503 FOR_BB_INSNS (bb, insn)
4504 if (NONDEBUG_INSN_P (insn))
4506 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4507 df_ref def, use;
4509 uid_luid[INSN_UID (insn)] = i++;
4511 def = df_single_def (insn_info);
4512 use = df_single_use (insn_info);
4513 if (use
4514 && def
4515 && DF_REF_REGNO (use) == DF_REF_REGNO (def)
4516 && !bitmap_bit_p (&set, DF_REF_REGNO (use))
4517 && rtx_moveable_p (&PATTERN (insn), OP_IN))
4519 unsigned regno = DF_REF_REGNO (use);
4520 bitmap_set_bit (moveable, regno);
4521 bitmap_set_bit (&set, regno);
4522 bitmap_set_bit (&used, regno);
4523 bitmap_clear_bit (transp, regno);
4524 continue;
4526 FOR_EACH_INSN_INFO_USE (use, insn_info)
4528 unsigned regno = DF_REF_REGNO (use);
4529 bitmap_set_bit (&used, regno);
4530 if (bitmap_clear_bit (moveable, regno))
4531 bitmap_clear_bit (transp, regno);
4534 FOR_EACH_INSN_INFO_DEF (def, insn_info)
4536 unsigned regno = DF_REF_REGNO (def);
4537 bitmap_set_bit (&set, regno);
4538 bitmap_clear_bit (transp, regno);
4539 bitmap_clear_bit (moveable, regno);
4544 bitmap_clear (&live);
4545 bitmap_clear (&used);
4546 bitmap_clear (&set);
4548 FOR_EACH_BB_FN (bb, cfun)
4550 bitmap local = bb_local + bb->index;
4551 rtx_insn *insn;
4553 FOR_BB_INSNS (bb, insn)
4554 if (NONDEBUG_INSN_P (insn))
4556 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4557 rtx_insn *def_insn;
4558 rtx closest_use, note;
4559 df_ref def, use;
4560 unsigned regno;
4561 bool all_dominated, all_local;
4562 machine_mode mode;
4564 def = df_single_def (insn_info);
4565 /* There must be exactly one def in this insn. */
4566 if (!def || !single_set (insn))
4567 continue;
4568 /* This must be the only definition of the reg. We also limit
4569 which modes we deal with so that we can assume we can generate
4570 move instructions. */
4571 regno = DF_REF_REGNO (def);
4572 mode = GET_MODE (DF_REF_REG (def));
4573 if (DF_REG_DEF_COUNT (regno) != 1
4574 || !DF_REF_INSN_INFO (def)
4575 || HARD_REGISTER_NUM_P (regno)
4576 || DF_REG_EQ_USE_COUNT (regno) > 0
4577 || (!INTEGRAL_MODE_P (mode) && !FLOAT_MODE_P (mode)))
4578 continue;
4579 def_insn = DF_REF_INSN (def);
4581 for (note = REG_NOTES (def_insn); note; note = XEXP (note, 1))
4582 if (REG_NOTE_KIND (note) == REG_EQUIV && MEM_P (XEXP (note, 0)))
4583 break;
4585 if (note)
4587 if (dump_file)
4588 fprintf (dump_file, "Ignoring reg %d, has equiv memory\n",
4589 regno);
4590 bitmap_set_bit (&unusable_as_input, regno);
4591 continue;
4594 use = DF_REG_USE_CHAIN (regno);
4595 all_dominated = true;
4596 all_local = true;
4597 closest_use = NULL_RTX;
4598 for (; use; use = DF_REF_NEXT_REG (use))
4600 rtx_insn *insn;
4601 if (!DF_REF_INSN_INFO (use))
4603 all_dominated = false;
4604 all_local = false;
4605 break;
4607 insn = DF_REF_INSN (use);
4608 if (DEBUG_INSN_P (insn))
4609 continue;
4610 if (BLOCK_FOR_INSN (insn) != BLOCK_FOR_INSN (def_insn))
4611 all_local = false;
4612 if (!insn_dominated_by_p (insn, def_insn, uid_luid))
4613 all_dominated = false;
4614 if (closest_use != insn && closest_use != const0_rtx)
4616 if (closest_use == NULL_RTX)
4617 closest_use = insn;
4618 else if (insn_dominated_by_p (closest_use, insn, uid_luid))
4619 closest_use = insn;
4620 else if (!insn_dominated_by_p (insn, closest_use, uid_luid))
4621 closest_use = const0_rtx;
4624 if (!all_dominated)
4626 if (dump_file)
4627 fprintf (dump_file, "Reg %d not all uses dominated by set\n",
4628 regno);
4629 continue;
4631 if (all_local)
4632 bitmap_set_bit (local, regno);
4633 if (closest_use == const0_rtx || closest_use == NULL
4634 || next_nonnote_nondebug_insn (def_insn) == closest_use)
4636 if (dump_file)
4637 fprintf (dump_file, "Reg %d uninteresting%s\n", regno,
4638 closest_use == const0_rtx || closest_use == NULL
4639 ? " (no unique first use)" : "");
4640 continue;
4642 if (HAVE_cc0 && reg_referenced_p (cc0_rtx, PATTERN (closest_use)))
4644 if (dump_file)
4645 fprintf (dump_file, "Reg %d: closest user uses cc0\n",
4646 regno);
4647 continue;
4650 bitmap_set_bit (&interesting, regno);
4651 /* If we get here, we know closest_use is a non-NULL insn
4652 (as opposed to const_0_rtx). */
4653 closest_uses[regno] = as_a <rtx_insn *> (closest_use);
4655 if (dump_file && (all_local || all_dominated))
4657 fprintf (dump_file, "Reg %u:", regno);
4658 if (all_local)
4659 fprintf (dump_file, " local to bb %d", bb->index);
4660 if (all_dominated)
4661 fprintf (dump_file, " def dominates all uses");
4662 if (closest_use != const0_rtx)
4663 fprintf (dump_file, " has unique first use");
4664 fputs ("\n", dump_file);
4669 EXECUTE_IF_SET_IN_BITMAP (&interesting, 0, i, bi)
4671 df_ref def = DF_REG_DEF_CHAIN (i);
4672 rtx_insn *def_insn = DF_REF_INSN (def);
4673 basic_block def_block = BLOCK_FOR_INSN (def_insn);
4674 bitmap def_bb_local = bb_local + def_block->index;
4675 bitmap def_bb_moveable = bb_moveable_reg_sets + def_block->index;
4676 bitmap def_bb_transp = bb_transp_live + def_block->index;
4677 bool local_to_bb_p = bitmap_bit_p (def_bb_local, i);
4678 rtx_insn *use_insn = closest_uses[i];
4679 df_ref use;
4680 bool all_ok = true;
4681 bool all_transp = true;
4683 if (!REG_P (DF_REF_REG (def)))
4684 continue;
4686 if (!local_to_bb_p)
4688 if (dump_file)
4689 fprintf (dump_file, "Reg %u not local to one basic block\n",
4691 continue;
4693 if (reg_equiv_init (i) != NULL_RTX)
4695 if (dump_file)
4696 fprintf (dump_file, "Ignoring reg %u with equiv init insn\n",
4698 continue;
4700 if (!rtx_moveable_p (&PATTERN (def_insn), OP_IN))
4702 if (dump_file)
4703 fprintf (dump_file, "Found def insn %d for %d to be not moveable\n",
4704 INSN_UID (def_insn), i);
4705 continue;
4707 if (dump_file)
4708 fprintf (dump_file, "Examining insn %d, def for %d\n",
4709 INSN_UID (def_insn), i);
4710 FOR_EACH_INSN_USE (use, def_insn)
4712 unsigned regno = DF_REF_REGNO (use);
4713 if (bitmap_bit_p (&unusable_as_input, regno))
4715 all_ok = false;
4716 if (dump_file)
4717 fprintf (dump_file, " found unusable input reg %u.\n", regno);
4718 break;
4720 if (!bitmap_bit_p (def_bb_transp, regno))
4722 if (bitmap_bit_p (def_bb_moveable, regno)
4723 && !control_flow_insn_p (use_insn)
4724 && (!HAVE_cc0 || !sets_cc0_p (use_insn)))
4726 if (modified_between_p (DF_REF_REG (use), def_insn, use_insn))
4728 rtx_insn *x = NEXT_INSN (def_insn);
4729 while (!modified_in_p (DF_REF_REG (use), x))
4731 gcc_assert (x != use_insn);
4732 x = NEXT_INSN (x);
4734 if (dump_file)
4735 fprintf (dump_file, " input reg %u modified but insn %d moveable\n",
4736 regno, INSN_UID (x));
4737 emit_insn_after (PATTERN (x), use_insn);
4738 set_insn_deleted (x);
4740 else
4742 if (dump_file)
4743 fprintf (dump_file, " input reg %u modified between def and use\n",
4744 regno);
4745 all_transp = false;
4748 else
4749 all_transp = false;
4752 if (!all_ok)
4753 continue;
4754 if (!dbg_cnt (ira_move))
4755 break;
4756 if (dump_file)
4757 fprintf (dump_file, " all ok%s\n", all_transp ? " and transp" : "");
4759 if (all_transp)
4761 rtx def_reg = DF_REF_REG (def);
4762 rtx newreg = ira_create_new_reg (def_reg);
4763 if (validate_change (def_insn, DF_REF_REAL_LOC (def), newreg, 0))
4765 unsigned nregno = REGNO (newreg);
4766 emit_insn_before (gen_move_insn (def_reg, newreg), use_insn);
4767 nregno -= max_regs;
4768 pseudo_replaced_reg[nregno] = def_reg;
4773 FOR_EACH_BB_FN (bb, cfun)
4775 bitmap_clear (bb_local + bb->index);
4776 bitmap_clear (bb_transp_live + bb->index);
4777 bitmap_clear (bb_moveable_reg_sets + bb->index);
4779 bitmap_clear (&interesting);
4780 bitmap_clear (&unusable_as_input);
4781 free (uid_luid);
4782 free (closest_uses);
4783 free (bb_local);
4784 free (bb_transp_live);
4785 free (bb_moveable_reg_sets);
4787 last_moveable_pseudo = max_reg_num ();
4789 fix_reg_equiv_init ();
4790 expand_reg_info ();
4791 regstat_free_n_sets_and_refs ();
4792 regstat_free_ri ();
4793 regstat_init_n_sets_and_refs ();
4794 regstat_compute_ri ();
4795 free_dominance_info (CDI_DOMINATORS);
4798 /* If SET pattern SET is an assignment from a hard register to a pseudo which
4799 is live at CALL_DOM (if non-NULL, otherwise this check is omitted), return
4800 the destination. Otherwise return NULL. */
4802 static rtx
4803 interesting_dest_for_shprep_1 (rtx set, basic_block call_dom)
4805 rtx src = SET_SRC (set);
4806 rtx dest = SET_DEST (set);
4807 if (!REG_P (src) || !HARD_REGISTER_P (src)
4808 || !REG_P (dest) || HARD_REGISTER_P (dest)
4809 || (call_dom && !bitmap_bit_p (df_get_live_in (call_dom), REGNO (dest))))
4810 return NULL;
4811 return dest;
4814 /* If insn is interesting for parameter range-splitting shrink-wrapping
4815 preparation, i.e. it is a single set from a hard register to a pseudo, which
4816 is live at CALL_DOM (if non-NULL, otherwise this check is omitted), or a
4817 parallel statement with only one such statement, return the destination.
4818 Otherwise return NULL. */
4820 static rtx
4821 interesting_dest_for_shprep (rtx_insn *insn, basic_block call_dom)
4823 if (!INSN_P (insn))
4824 return NULL;
4825 rtx pat = PATTERN (insn);
4826 if (GET_CODE (pat) == SET)
4827 return interesting_dest_for_shprep_1 (pat, call_dom);
4829 if (GET_CODE (pat) != PARALLEL)
4830 return NULL;
4831 rtx ret = NULL;
4832 for (int i = 0; i < XVECLEN (pat, 0); i++)
4834 rtx sub = XVECEXP (pat, 0, i);
4835 if (GET_CODE (sub) == USE || GET_CODE (sub) == CLOBBER)
4836 continue;
4837 if (GET_CODE (sub) != SET
4838 || side_effects_p (sub))
4839 return NULL;
4840 rtx dest = interesting_dest_for_shprep_1 (sub, call_dom);
4841 if (dest && ret)
4842 return NULL;
4843 if (dest)
4844 ret = dest;
4846 return ret;
4849 /* Split live ranges of pseudos that are loaded from hard registers in the
4850 first BB in a BB that dominates all non-sibling call if such a BB can be
4851 found and is not in a loop. Return true if the function has made any
4852 changes. */
4854 static bool
4855 split_live_ranges_for_shrink_wrap (void)
4857 basic_block bb, call_dom = NULL;
4858 basic_block first = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
4859 rtx_insn *insn, *last_interesting_insn = NULL;
4860 bitmap_head need_new, reachable;
4861 vec<basic_block> queue;
4863 if (!SHRINK_WRAPPING_ENABLED)
4864 return false;
4866 bitmap_initialize (&need_new, 0);
4867 bitmap_initialize (&reachable, 0);
4868 queue.create (n_basic_blocks_for_fn (cfun));
4870 FOR_EACH_BB_FN (bb, cfun)
4871 FOR_BB_INSNS (bb, insn)
4872 if (CALL_P (insn) && !SIBLING_CALL_P (insn))
4874 if (bb == first)
4876 bitmap_clear (&need_new);
4877 bitmap_clear (&reachable);
4878 queue.release ();
4879 return false;
4882 bitmap_set_bit (&need_new, bb->index);
4883 bitmap_set_bit (&reachable, bb->index);
4884 queue.quick_push (bb);
4885 break;
4888 if (queue.is_empty ())
4890 bitmap_clear (&need_new);
4891 bitmap_clear (&reachable);
4892 queue.release ();
4893 return false;
4896 while (!queue.is_empty ())
4898 edge e;
4899 edge_iterator ei;
4901 bb = queue.pop ();
4902 FOR_EACH_EDGE (e, ei, bb->succs)
4903 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
4904 && bitmap_set_bit (&reachable, e->dest->index))
4905 queue.quick_push (e->dest);
4907 queue.release ();
4909 FOR_BB_INSNS (first, insn)
4911 rtx dest = interesting_dest_for_shprep (insn, NULL);
4912 if (!dest)
4913 continue;
4915 if (DF_REG_DEF_COUNT (REGNO (dest)) > 1)
4917 bitmap_clear (&need_new);
4918 bitmap_clear (&reachable);
4919 return false;
4922 for (df_ref use = DF_REG_USE_CHAIN (REGNO(dest));
4923 use;
4924 use = DF_REF_NEXT_REG (use))
4926 int ubbi = DF_REF_BB (use)->index;
4927 if (bitmap_bit_p (&reachable, ubbi))
4928 bitmap_set_bit (&need_new, ubbi);
4930 last_interesting_insn = insn;
4933 bitmap_clear (&reachable);
4934 if (!last_interesting_insn)
4936 bitmap_clear (&need_new);
4937 return false;
4940 call_dom = nearest_common_dominator_for_set (CDI_DOMINATORS, &need_new);
4941 bitmap_clear (&need_new);
4942 if (call_dom == first)
4943 return false;
4945 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
4946 while (bb_loop_depth (call_dom) > 0)
4947 call_dom = get_immediate_dominator (CDI_DOMINATORS, call_dom);
4948 loop_optimizer_finalize ();
4950 if (call_dom == first)
4951 return false;
4953 calculate_dominance_info (CDI_POST_DOMINATORS);
4954 if (dominated_by_p (CDI_POST_DOMINATORS, first, call_dom))
4956 free_dominance_info (CDI_POST_DOMINATORS);
4957 return false;
4959 free_dominance_info (CDI_POST_DOMINATORS);
4961 if (dump_file)
4962 fprintf (dump_file, "Will split live ranges of parameters at BB %i\n",
4963 call_dom->index);
4965 bool ret = false;
4966 FOR_BB_INSNS (first, insn)
4968 rtx dest = interesting_dest_for_shprep (insn, call_dom);
4969 if (!dest || dest == pic_offset_table_rtx)
4970 continue;
4972 rtx newreg = NULL_RTX;
4973 df_ref use, next;
4974 for (use = DF_REG_USE_CHAIN (REGNO (dest)); use; use = next)
4976 rtx_insn *uin = DF_REF_INSN (use);
4977 next = DF_REF_NEXT_REG (use);
4979 basic_block ubb = BLOCK_FOR_INSN (uin);
4980 if (ubb == call_dom
4981 || dominated_by_p (CDI_DOMINATORS, ubb, call_dom))
4983 if (!newreg)
4984 newreg = ira_create_new_reg (dest);
4985 validate_change (uin, DF_REF_REAL_LOC (use), newreg, true);
4989 if (newreg)
4991 rtx_insn *new_move = gen_move_insn (newreg, dest);
4992 emit_insn_after (new_move, bb_note (call_dom));
4993 if (dump_file)
4995 fprintf (dump_file, "Split live-range of register ");
4996 print_rtl_single (dump_file, dest);
4998 ret = true;
5001 if (insn == last_interesting_insn)
5002 break;
5004 apply_change_group ();
5005 return ret;
5008 /* Perform the second half of the transformation started in
5009 find_moveable_pseudos. We look for instances where the newly introduced
5010 pseudo remains unallocated, and remove it by moving the definition to
5011 just before its use, replacing the move instruction generated by
5012 find_moveable_pseudos. */
5013 static void
5014 move_unallocated_pseudos (void)
5016 int i;
5017 for (i = first_moveable_pseudo; i < last_moveable_pseudo; i++)
5018 if (reg_renumber[i] < 0)
5020 int idx = i - first_moveable_pseudo;
5021 rtx other_reg = pseudo_replaced_reg[idx];
5022 rtx_insn *def_insn = DF_REF_INSN (DF_REG_DEF_CHAIN (i));
5023 /* The use must follow all definitions of OTHER_REG, so we can
5024 insert the new definition immediately after any of them. */
5025 df_ref other_def = DF_REG_DEF_CHAIN (REGNO (other_reg));
5026 rtx_insn *move_insn = DF_REF_INSN (other_def);
5027 rtx_insn *newinsn = emit_insn_after (PATTERN (def_insn), move_insn);
5028 rtx set;
5029 int success;
5031 if (dump_file)
5032 fprintf (dump_file, "moving def of %d (insn %d now) ",
5033 REGNO (other_reg), INSN_UID (def_insn));
5035 delete_insn (move_insn);
5036 while ((other_def = DF_REG_DEF_CHAIN (REGNO (other_reg))))
5037 delete_insn (DF_REF_INSN (other_def));
5038 delete_insn (def_insn);
5040 set = single_set (newinsn);
5041 success = validate_change (newinsn, &SET_DEST (set), other_reg, 0);
5042 gcc_assert (success);
5043 if (dump_file)
5044 fprintf (dump_file, " %d) rather than keep unallocated replacement %d\n",
5045 INSN_UID (newinsn), i);
5046 SET_REG_N_REFS (i, 0);
5050 /* If the backend knows where to allocate pseudos for hard
5051 register initial values, register these allocations now. */
5052 static void
5053 allocate_initial_values (void)
5055 if (targetm.allocate_initial_value)
5057 rtx hreg, preg, x;
5058 int i, regno;
5060 for (i = 0; HARD_REGISTER_NUM_P (i); i++)
5062 if (! initial_value_entry (i, &hreg, &preg))
5063 break;
5065 x = targetm.allocate_initial_value (hreg);
5066 regno = REGNO (preg);
5067 if (x && REG_N_SETS (regno) <= 1)
5069 if (MEM_P (x))
5070 reg_equiv_memory_loc (regno) = x;
5071 else
5073 basic_block bb;
5074 int new_regno;
5076 gcc_assert (REG_P (x));
5077 new_regno = REGNO (x);
5078 reg_renumber[regno] = new_regno;
5079 /* Poke the regno right into regno_reg_rtx so that even
5080 fixed regs are accepted. */
5081 SET_REGNO (preg, new_regno);
5082 /* Update global register liveness information. */
5083 FOR_EACH_BB_FN (bb, cfun)
5085 if (REGNO_REG_SET_P (df_get_live_in (bb), regno))
5086 SET_REGNO_REG_SET (df_get_live_in (bb), new_regno);
5087 if (REGNO_REG_SET_P (df_get_live_out (bb), regno))
5088 SET_REGNO_REG_SET (df_get_live_out (bb), new_regno);
5094 gcc_checking_assert (! initial_value_entry (FIRST_PSEUDO_REGISTER,
5095 &hreg, &preg));
5100 /* True when we use LRA instead of reload pass for the current
5101 function. */
5102 bool ira_use_lra_p;
5104 /* True if we have allocno conflicts. It is false for non-optimized
5105 mode or when the conflict table is too big. */
5106 bool ira_conflicts_p;
5108 /* Saved between IRA and reload. */
5109 static int saved_flag_ira_share_spill_slots;
5111 /* This is the main entry of IRA. */
5112 static void
5113 ira (FILE *f)
5115 bool loops_p;
5116 int ira_max_point_before_emit;
5117 int rebuild_p;
5118 bool saved_flag_caller_saves = flag_caller_saves;
5119 enum ira_region saved_flag_ira_region = flag_ira_region;
5121 /* Perform target specific PIC register initialization. */
5122 targetm.init_pic_reg ();
5124 ira_conflicts_p = optimize > 0;
5126 ira_use_lra_p = targetm.lra_p ();
5127 /* If there are too many pseudos and/or basic blocks (e.g. 10K
5128 pseudos and 10K blocks or 100K pseudos and 1K blocks), we will
5129 use simplified and faster algorithms in LRA. */
5130 lra_simple_p
5131 = (ira_use_lra_p
5132 && max_reg_num () >= (1 << 26) / last_basic_block_for_fn (cfun));
5133 if (lra_simple_p)
5135 /* It permits to skip live range splitting in LRA. */
5136 flag_caller_saves = false;
5137 /* There is no sense to do regional allocation when we use
5138 simplified LRA. */
5139 flag_ira_region = IRA_REGION_ONE;
5140 ira_conflicts_p = false;
5143 #ifndef IRA_NO_OBSTACK
5144 gcc_obstack_init (&ira_obstack);
5145 #endif
5146 bitmap_obstack_initialize (&ira_bitmap_obstack);
5148 /* LRA uses its own infrastructure to handle caller save registers. */
5149 if (flag_caller_saves && !ira_use_lra_p)
5150 init_caller_save ();
5152 if (flag_ira_verbose < 10)
5154 internal_flag_ira_verbose = flag_ira_verbose;
5155 ira_dump_file = f;
5157 else
5159 internal_flag_ira_verbose = flag_ira_verbose - 10;
5160 ira_dump_file = stderr;
5163 setup_prohibited_mode_move_regs ();
5164 decrease_live_ranges_number ();
5165 df_note_add_problem ();
5167 /* DF_LIVE can't be used in the register allocator, too many other
5168 parts of the compiler depend on using the "classic" liveness
5169 interpretation of the DF_LR problem. See PR38711.
5170 Remove the problem, so that we don't spend time updating it in
5171 any of the df_analyze() calls during IRA/LRA. */
5172 if (optimize > 1)
5173 df_remove_problem (df_live);
5174 gcc_checking_assert (df_live == NULL);
5176 #ifdef ENABLE_CHECKING
5177 df->changeable_flags |= DF_VERIFY_SCHEDULED;
5178 #endif
5179 df_analyze ();
5181 init_reg_equiv ();
5182 if (ira_conflicts_p)
5184 calculate_dominance_info (CDI_DOMINATORS);
5186 if (split_live_ranges_for_shrink_wrap ())
5187 df_analyze ();
5189 free_dominance_info (CDI_DOMINATORS);
5192 df_clear_flags (DF_NO_INSN_RESCAN);
5194 regstat_init_n_sets_and_refs ();
5195 regstat_compute_ri ();
5197 /* If we are not optimizing, then this is the only place before
5198 register allocation where dataflow is done. And that is needed
5199 to generate these warnings. */
5200 if (warn_clobbered)
5201 generate_setjmp_warnings ();
5203 /* Determine if the current function is a leaf before running IRA
5204 since this can impact optimizations done by the prologue and
5205 epilogue thus changing register elimination offsets. */
5206 crtl->is_leaf = leaf_function_p ();
5208 if (resize_reg_info () && flag_ira_loop_pressure)
5209 ira_set_pseudo_classes (true, ira_dump_file);
5211 rebuild_p = update_equiv_regs ();
5212 setup_reg_equiv ();
5213 setup_reg_equiv_init ();
5215 if (optimize && rebuild_p)
5217 timevar_push (TV_JUMP);
5218 rebuild_jump_labels (get_insns ());
5219 if (purge_all_dead_edges ())
5220 delete_unreachable_blocks ();
5221 timevar_pop (TV_JUMP);
5224 allocated_reg_info_size = max_reg_num ();
5226 if (delete_trivially_dead_insns (get_insns (), max_reg_num ()))
5227 df_analyze ();
5229 /* It is not worth to do such improvement when we use a simple
5230 allocation because of -O0 usage or because the function is too
5231 big. */
5232 if (ira_conflicts_p)
5233 find_moveable_pseudos ();
5235 max_regno_before_ira = max_reg_num ();
5236 ira_setup_eliminable_regset ();
5238 ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
5239 ira_load_cost = ira_store_cost = ira_shuffle_cost = 0;
5240 ira_move_loops_num = ira_additional_jumps_num = 0;
5242 ira_assert (current_loops == NULL);
5243 if (flag_ira_region == IRA_REGION_ALL || flag_ira_region == IRA_REGION_MIXED)
5244 loop_optimizer_init (AVOID_CFG_MODIFICATIONS | LOOPS_HAVE_RECORDED_EXITS);
5246 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
5247 fprintf (ira_dump_file, "Building IRA IR\n");
5248 loops_p = ira_build ();
5250 ira_assert (ira_conflicts_p || !loops_p);
5252 saved_flag_ira_share_spill_slots = flag_ira_share_spill_slots;
5253 if (too_high_register_pressure_p () || cfun->calls_setjmp)
5254 /* It is just wasting compiler's time to pack spilled pseudos into
5255 stack slots in this case -- prohibit it. We also do this if
5256 there is setjmp call because a variable not modified between
5257 setjmp and longjmp the compiler is required to preserve its
5258 value and sharing slots does not guarantee it. */
5259 flag_ira_share_spill_slots = FALSE;
5261 ira_color ();
5263 ira_max_point_before_emit = ira_max_point;
5265 ira_initiate_emit_data ();
5267 ira_emit (loops_p);
5269 max_regno = max_reg_num ();
5270 if (ira_conflicts_p)
5272 if (! loops_p)
5274 if (! ira_use_lra_p)
5275 ira_initiate_assign ();
5277 else
5279 expand_reg_info ();
5281 if (ira_use_lra_p)
5283 ira_allocno_t a;
5284 ira_allocno_iterator ai;
5286 FOR_EACH_ALLOCNO (a, ai)
5288 int old_regno = ALLOCNO_REGNO (a);
5289 int new_regno = REGNO (ALLOCNO_EMIT_DATA (a)->reg);
5291 ALLOCNO_REGNO (a) = new_regno;
5293 if (old_regno != new_regno)
5294 setup_reg_classes (new_regno, reg_preferred_class (old_regno),
5295 reg_alternate_class (old_regno),
5296 reg_allocno_class (old_regno));
5300 else
5302 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
5303 fprintf (ira_dump_file, "Flattening IR\n");
5304 ira_flattening (max_regno_before_ira, ira_max_point_before_emit);
5306 /* New insns were generated: add notes and recalculate live
5307 info. */
5308 df_analyze ();
5310 /* ??? Rebuild the loop tree, but why? Does the loop tree
5311 change if new insns were generated? Can that be handled
5312 by updating the loop tree incrementally? */
5313 loop_optimizer_finalize ();
5314 free_dominance_info (CDI_DOMINATORS);
5315 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
5316 | LOOPS_HAVE_RECORDED_EXITS);
5318 if (! ira_use_lra_p)
5320 setup_allocno_assignment_flags ();
5321 ira_initiate_assign ();
5322 ira_reassign_conflict_allocnos (max_regno);
5327 ira_finish_emit_data ();
5329 setup_reg_renumber ();
5331 calculate_allocation_cost ();
5333 #ifdef ENABLE_IRA_CHECKING
5334 if (ira_conflicts_p)
5335 check_allocation ();
5336 #endif
5338 if (max_regno != max_regno_before_ira)
5340 regstat_free_n_sets_and_refs ();
5341 regstat_free_ri ();
5342 regstat_init_n_sets_and_refs ();
5343 regstat_compute_ri ();
5346 overall_cost_before = ira_overall_cost;
5347 if (! ira_conflicts_p)
5348 grow_reg_equivs ();
5349 else
5351 fix_reg_equiv_init ();
5353 #ifdef ENABLE_IRA_CHECKING
5354 print_redundant_copies ();
5355 #endif
5356 if (! ira_use_lra_p)
5358 ira_spilled_reg_stack_slots_num = 0;
5359 ira_spilled_reg_stack_slots
5360 = ((struct ira_spilled_reg_stack_slot *)
5361 ira_allocate (max_regno
5362 * sizeof (struct ira_spilled_reg_stack_slot)));
5363 memset (ira_spilled_reg_stack_slots, 0,
5364 max_regno * sizeof (struct ira_spilled_reg_stack_slot));
5367 allocate_initial_values ();
5369 /* See comment for find_moveable_pseudos call. */
5370 if (ira_conflicts_p)
5371 move_unallocated_pseudos ();
5373 /* Restore original values. */
5374 if (lra_simple_p)
5376 flag_caller_saves = saved_flag_caller_saves;
5377 flag_ira_region = saved_flag_ira_region;
5381 static void
5382 do_reload (void)
5384 basic_block bb;
5385 bool need_dce;
5386 unsigned pic_offset_table_regno = INVALID_REGNUM;
5388 if (flag_ira_verbose < 10)
5389 ira_dump_file = dump_file;
5391 /* If pic_offset_table_rtx is a pseudo register, then keep it so
5392 after reload to avoid possible wrong usages of hard reg assigned
5393 to it. */
5394 if (pic_offset_table_rtx
5395 && REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER)
5396 pic_offset_table_regno = REGNO (pic_offset_table_rtx);
5398 timevar_push (TV_RELOAD);
5399 if (ira_use_lra_p)
5401 if (current_loops != NULL)
5403 loop_optimizer_finalize ();
5404 free_dominance_info (CDI_DOMINATORS);
5406 FOR_ALL_BB_FN (bb, cfun)
5407 bb->loop_father = NULL;
5408 current_loops = NULL;
5410 ira_destroy ();
5412 lra (ira_dump_file);
5413 /* ???!!! Move it before lra () when we use ira_reg_equiv in
5414 LRA. */
5415 vec_free (reg_equivs);
5416 reg_equivs = NULL;
5417 need_dce = false;
5419 else
5421 df_set_flags (DF_NO_INSN_RESCAN);
5422 build_insn_chain ();
5424 need_dce = reload (get_insns (), ira_conflicts_p);
5428 timevar_pop (TV_RELOAD);
5430 timevar_push (TV_IRA);
5432 if (ira_conflicts_p && ! ira_use_lra_p)
5434 ira_free (ira_spilled_reg_stack_slots);
5435 ira_finish_assign ();
5438 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL
5439 && overall_cost_before != ira_overall_cost)
5440 fprintf (ira_dump_file, "+++Overall after reload %" PRId64 "\n",
5441 ira_overall_cost);
5443 flag_ira_share_spill_slots = saved_flag_ira_share_spill_slots;
5445 if (! ira_use_lra_p)
5447 ira_destroy ();
5448 if (current_loops != NULL)
5450 loop_optimizer_finalize ();
5451 free_dominance_info (CDI_DOMINATORS);
5453 FOR_ALL_BB_FN (bb, cfun)
5454 bb->loop_father = NULL;
5455 current_loops = NULL;
5457 regstat_free_ri ();
5458 regstat_free_n_sets_and_refs ();
5461 if (optimize)
5462 cleanup_cfg (CLEANUP_EXPENSIVE);
5464 finish_reg_equiv ();
5466 bitmap_obstack_release (&ira_bitmap_obstack);
5467 #ifndef IRA_NO_OBSTACK
5468 obstack_free (&ira_obstack, NULL);
5469 #endif
5471 /* The code after the reload has changed so much that at this point
5472 we might as well just rescan everything. Note that
5473 df_rescan_all_insns is not going to help here because it does not
5474 touch the artificial uses and defs. */
5475 df_finish_pass (true);
5476 df_scan_alloc (NULL);
5477 df_scan_blocks ();
5479 if (optimize > 1)
5481 df_live_add_problem ();
5482 df_live_set_all_dirty ();
5485 if (optimize)
5486 df_analyze ();
5488 if (need_dce && optimize)
5489 run_fast_dce ();
5491 /* Diagnose uses of the hard frame pointer when it is used as a global
5492 register. Often we can get away with letting the user appropriate
5493 the frame pointer, but we should let them know when code generation
5494 makes that impossible. */
5495 if (global_regs[HARD_FRAME_POINTER_REGNUM] && frame_pointer_needed)
5497 tree decl = global_regs_decl[HARD_FRAME_POINTER_REGNUM];
5498 error_at (DECL_SOURCE_LOCATION (current_function_decl),
5499 "frame pointer required, but reserved");
5500 inform (DECL_SOURCE_LOCATION (decl), "for %qD", decl);
5503 if (pic_offset_table_regno != INVALID_REGNUM)
5504 pic_offset_table_rtx = gen_rtx_REG (Pmode, pic_offset_table_regno);
5506 timevar_pop (TV_IRA);
5509 /* Run the integrated register allocator. */
5511 namespace {
5513 const pass_data pass_data_ira =
5515 RTL_PASS, /* type */
5516 "ira", /* name */
5517 OPTGROUP_NONE, /* optinfo_flags */
5518 TV_IRA, /* tv_id */
5519 0, /* properties_required */
5520 0, /* properties_provided */
5521 0, /* properties_destroyed */
5522 0, /* todo_flags_start */
5523 TODO_do_not_ggc_collect, /* todo_flags_finish */
5526 class pass_ira : public rtl_opt_pass
5528 public:
5529 pass_ira (gcc::context *ctxt)
5530 : rtl_opt_pass (pass_data_ira, ctxt)
5533 /* opt_pass methods: */
5534 virtual bool gate (function *)
5536 return !targetm.no_register_allocation;
5538 virtual unsigned int execute (function *)
5540 ira (dump_file);
5541 return 0;
5544 }; // class pass_ira
5546 } // anon namespace
5548 rtl_opt_pass *
5549 make_pass_ira (gcc::context *ctxt)
5551 return new pass_ira (ctxt);
5554 namespace {
5556 const pass_data pass_data_reload =
5558 RTL_PASS, /* type */
5559 "reload", /* name */
5560 OPTGROUP_NONE, /* optinfo_flags */
5561 TV_RELOAD, /* tv_id */
5562 0, /* properties_required */
5563 0, /* properties_provided */
5564 0, /* properties_destroyed */
5565 0, /* todo_flags_start */
5566 0, /* todo_flags_finish */
5569 class pass_reload : public rtl_opt_pass
5571 public:
5572 pass_reload (gcc::context *ctxt)
5573 : rtl_opt_pass (pass_data_reload, ctxt)
5576 /* opt_pass methods: */
5577 virtual bool gate (function *)
5579 return !targetm.no_register_allocation;
5581 virtual unsigned int execute (function *)
5583 do_reload ();
5584 return 0;
5587 }; // class pass_reload
5589 } // anon namespace
5591 rtl_opt_pass *
5592 make_pass_reload (gcc::context *ctxt)
5594 return new pass_reload (ctxt);