1 /* Integrated Register Allocator (IRA) entry point.
2 Copyright (C) 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* The integrated register allocator (IRA) is a
23 regional register allocator performing graph coloring on a top-down
24 traversal of nested regions. Graph coloring in a region is based
25 on Chaitin-Briggs algorithm. It is called integrated because
26 register coalescing, register live range splitting, and choosing a
27 better hard register are done on-the-fly during coloring. Register
28 coalescing and choosing a cheaper hard register is done by hard
29 register preferencing during hard register assigning. The live
30 range splitting is a byproduct of the regional register allocation.
32 Major IRA notions are:
34 o *Region* is a part of CFG where graph coloring based on
35 Chaitin-Briggs algorithm is done. IRA can work on any set of
36 nested CFG regions forming a tree. Currently the regions are
37 the entire function for the root region and natural loops for
38 the other regions. Therefore data structure representing a
39 region is called loop_tree_node.
41 o *Cover class* is a register class belonging to a set of
42 non-intersecting register classes containing all of the
43 hard-registers available for register allocation. The set of
44 all cover classes for a target is defined in the corresponding
45 machine-description file according some criteria. Such notion
46 is needed because Chaitin-Briggs algorithm works on
47 non-intersected register classes.
49 o *Allocno* represents the live range of a pseudo-register in a
50 region. Besides the obvious attributes like the corresponding
51 pseudo-register number, cover class, conflicting allocnos and
52 conflicting hard-registers, there are a few allocno attributes
53 which are important for understanding the allocation algorithm:
55 - *Live ranges*. This is a list of ranges of *program
56 points* where the allocno lives. Program points represent
57 places where a pseudo can be born or become dead (there are
58 approximately two times more program points than the insns)
59 and they are represented by integers starting with 0. The
60 live ranges are used to find conflicts between allocnos of
61 different cover classes. They also play very important role
62 for the transformation of the IRA internal representation of
63 several regions into a one region representation. The later is
64 used during the reload pass work because each allocno
65 represents all of the corresponding pseudo-registers.
67 - *Hard-register costs*. This is a vector of size equal to the
68 number of available hard-registers of the allocno's cover
69 class. The cost of a callee-clobbered hard-register for an
70 allocno is increased by the cost of save/restore code around
71 the calls through the given allocno's life. If the allocno
72 is a move instruction operand and another operand is a
73 hard-register of the allocno's cover class, the cost of the
74 hard-register is decreased by the move cost.
76 When an allocno is assigned, the hard-register with minimal
77 full cost is used. Initially, a hard-register's full cost is
78 the corresponding value from the hard-register's cost vector.
79 If the allocno is connected by a *copy* (see below) to
80 another allocno which has just received a hard-register, the
81 cost of the hard-register is decreased. Before choosing a
82 hard-register for an allocno, the allocno's current costs of
83 the hard-registers are modified by the conflict hard-register
84 costs of all of the conflicting allocnos which are not
87 - *Conflict hard-register costs*. This is a vector of the same
88 size as the hard-register costs vector. To permit an
89 unassigned allocno to get a better hard-register, IRA uses
90 this vector to calculate the final full cost of the
91 available hard-registers. Conflict hard-register costs of an
92 unassigned allocno are also changed with a change of the
93 hard-register cost of the allocno when a copy involving the
94 allocno is processed as described above. This is done to
95 show other unassigned allocnos that a given allocno prefers
96 some hard-registers in order to remove the move instruction
97 corresponding to the copy.
99 o *Cap*. If a pseudo-register does not live in a region but
100 lives in a nested region, IRA creates a special allocno called
101 a cap in the outer region. A region cap is also created for a
104 o *Copy*. Allocnos can be connected by copies. Copies are used
105 to modify hard-register costs for allocnos during coloring.
106 Such modifications reflects a preference to use the same
107 hard-register for the allocnos connected by copies. Usually
108 copies are created for move insns (in this case it results in
109 register coalescing). But IRA also creates copies for operands
110 of an insn which should be assigned to the same hard-register
111 due to constraints in the machine description (it usually
112 results in removing a move generated in reload to satisfy
113 the constraints) and copies referring to the allocno which is
114 the output operand of an instruction and the allocno which is
115 an input operand dying in the instruction (creation of such
116 copies results in less register shuffling). IRA *does not*
117 create copies between the same register allocnos from different
118 regions because we use another technique for propagating
119 hard-register preference on the borders of regions.
121 Allocnos (including caps) for the upper region in the region tree
122 *accumulate* information important for coloring from allocnos with
123 the same pseudo-register from nested regions. This includes
124 hard-register and memory costs, conflicts with hard-registers,
125 allocno conflicts, allocno copies and more. *Thus, attributes for
126 allocnos in a region have the same values as if the region had no
127 subregions*. It means that attributes for allocnos in the
128 outermost region corresponding to the function have the same values
129 as though the allocation used only one region which is the entire
130 function. It also means that we can look at IRA work as if the
131 first IRA did allocation for all function then it improved the
132 allocation for loops then their subloops and so on.
134 IRA major passes are:
136 o Building IRA internal representation which consists of the
139 * First, IRA builds regions and creates allocnos (file
140 ira-build.c) and initializes most of their attributes.
142 * Then IRA finds a cover class for each allocno and calculates
143 its initial (non-accumulated) cost of memory and each
144 hard-register of its cover class (file ira-cost.c).
146 * IRA creates live ranges of each allocno, calulates register
147 pressure for each cover class in each region, sets up
148 conflict hard registers for each allocno and info about calls
149 the allocno lives through (file ira-lives.c).
151 * IRA removes low register pressure loops from the regions
152 mostly to speed IRA up (file ira-build.c).
154 * IRA propagates accumulated allocno info from lower region
155 allocnos to corresponding upper region allocnos (file
158 * IRA creates all caps (file ira-build.c).
160 * Having live-ranges of allocnos and their cover classes, IRA
161 creates conflicting allocnos of the same cover class for each
162 allocno. Conflicting allocnos are stored as a bit vector or
163 array of pointers to the conflicting allocnos whatever is
164 more profitable (file ira-conflicts.c). At this point IRA
165 creates allocno copies.
167 o Coloring. Now IRA has all necessary info to start graph coloring
168 process. It is done in each region on top-down traverse of the
169 region tree (file ira-color.c). There are following subpasses:
171 * Optional aggressive coalescing of allocnos in the region.
173 * Putting allocnos onto the coloring stack. IRA uses Briggs
174 optimistic coloring which is a major improvement over
175 Chaitin's coloring. Therefore IRA does not spill allocnos at
176 this point. There is some freedom in the order of putting
177 allocnos on the stack which can affect the final result of
178 the allocation. IRA uses some heuristics to improve the order.
180 * Popping the allocnos from the stack and assigning them hard
181 registers. If IRA can not assign a hard register to an
182 allocno and the allocno is coalesced, IRA undoes the
183 coalescing and puts the uncoalesced allocnos onto the stack in
184 the hope that some such allocnos will get a hard register
185 separately. If IRA fails to assign hard register or memory
186 is more profitable for it, IRA spills the allocno. IRA
187 assigns the allocno the hard-register with minimal full
188 allocation cost which reflects the cost of usage of the
189 hard-register for the allocno and cost of usage of the
190 hard-register for allocnos conflicting with given allocno.
192 * After allono assigning in the region, IRA modifies the hard
193 register and memory costs for the corresponding allocnos in
194 the subregions to reflect the cost of possible loads, stores,
195 or moves on the border of the region and its subregions.
196 When default regional allocation algorithm is used
197 (-fira-algorithm=mixed), IRA just propagates the assignment
198 for allocnos if the register pressure in the region for the
199 corresponding cover class is less than number of available
200 hard registers for given cover class.
202 o Spill/restore code moving. When IRA performs an allocation
203 by traversing regions in top-down order, it does not know what
204 happens below in the region tree. Therefore, sometimes IRA
205 misses opportunities to perform a better allocation. A simple
206 optimization tries to improve allocation in a region having
207 subregions and containing in another region. If the
208 corresponding allocnos in the subregion are spilled, it spills
209 the region allocno if it is profitable. The optimization
210 implements a simple iterative algorithm performing profitable
211 transformations while they are still possible. It is fast in
212 practice, so there is no real need for a better time complexity
215 o Code change. After coloring, two allocnos representing the same
216 pseudo-register outside and inside a region respectively may be
217 assigned to different locations (hard-registers or memory). In
218 this case IRA creates and uses a new pseudo-register inside the
219 region and adds code to move allocno values on the region's
220 borders. This is done during top-down traversal of the regions
221 (file ira-emit.c). In some complicated cases IRA can create a
222 new allocno to move allocno values (e.g. when a swap of values
223 stored in two hard-registers is needed). At this stage, the
224 new allocno is marked as spilled. IRA still creates the
225 pseudo-register and the moves on the region borders even when
226 both allocnos were assigned to the same hard-register. If the
227 reload pass spills a pseudo-register for some reason, the
228 effect will be smaller because another allocno will still be in
229 the hard-register. In most cases, this is better then spilling
230 both allocnos. If reload does not change the allocation
231 for the two pseudo-registers, the trivial move will be removed
232 by post-reload optimizations. IRA does not generate moves for
233 allocnos assigned to the same hard register when the default
234 regional allocation algorithm is used and the register pressure
235 in the region for the corresponding allocno cover class is less
236 than number of available hard registers for given cover class.
237 IRA also does some optimizations to remove redundant stores and
238 to reduce code duplication on the region borders.
240 o Flattening internal representation. After changing code, IRA
241 transforms its internal representation for several regions into
242 one region representation (file ira-build.c). This process is
243 called IR flattening. Such process is more complicated than IR
244 rebuilding would be, but is much faster.
246 o After IR flattening, IRA tries to assign hard registers to all
247 spilled allocnos. This is impelemented by a simple and fast
248 priority coloring algorithm (see function
249 ira_reassign_conflict_allocnos::ira-color.c). Here new allocnos
250 created during the code change pass can be assigned to hard
253 o At the end IRA calls the reload pass. The reload pass
254 communicates with IRA through several functions in file
255 ira-color.c to improve its decisions in
257 * sharing stack slots for the spilled pseudos based on IRA info
258 about pseudo-register conflicts.
260 * reassigning hard-registers to all spilled pseudos at the end
261 of each reload iteration.
263 * choosing a better hard-register to spill based on IRA info
264 about pseudo-register live ranges and the register pressure
265 in places where the pseudo-register lives.
267 IRA uses a lot of data representing the target processors. These
268 data are initilized in file ira.c.
270 If function has no loops (or the loops are ignored when
271 -fira-algorithm=CB is used), we have classic Chaitin-Briggs
272 coloring (only instead of separate pass of coalescing, we use hard
273 register preferencing). In such case, IRA works much faster
274 because many things are not made (like IR flattening, the
275 spill/restore optimization, and the code change).
277 Literature is worth to read for better understanding the code:
279 o Preston Briggs, Keith D. Cooper, Linda Torczon. Improvements to
280 Graph Coloring Register Allocation.
282 o David Callahan, Brian Koblenz. Register allocation via
283 hierarchical graph coloring.
285 o Keith Cooper, Anshuman Dasgupta, Jason Eckhardt. Revisiting Graph
286 Coloring Register Allocation: A Study of the Chaitin-Briggs and
287 Callahan-Koblenz Algorithms.
289 o Guei-Yuan Lueh, Thomas Gross, and Ali-Reza Adl-Tabatabai. Global
290 Register Allocation Based on Graph Fusion.
292 o Vladimir Makarov. The Integrated Register Allocator for GCC.
294 o Vladimir Makarov. The top-down register allocator for irregular
295 register file architectures.
302 #include "coretypes.h"
311 #include "hard-reg-set.h"
312 #include "basic-block.h"
317 #include "tree-pass.h"
322 #include "integrate.h"
328 /* A modified value of flag `-fira-verbose' used internally. */
329 int internal_flag_ira_verbose
;
331 /* Dump file of the allocator if it is not NULL. */
334 /* Pools for allocnos, copies, allocno live ranges. */
335 alloc_pool allocno_pool
, copy_pool
, allocno_live_range_pool
;
337 /* The number of elements in the following array. */
338 int ira_spilled_reg_stack_slots_num
;
340 /* The following array contains info about spilled pseudo-registers
341 stack slots used in current function so far. */
342 struct ira_spilled_reg_stack_slot
*ira_spilled_reg_stack_slots
;
344 /* Correspondingly overall cost of the allocation, cost of the
345 allocnos assigned to hard-registers, cost of the allocnos assigned
346 to memory, cost of loads, stores and register move insns generated
347 for pseudo-register live range splitting (see ira-emit.c). */
348 int ira_overall_cost
;
349 int ira_reg_cost
, ira_mem_cost
;
350 int ira_load_cost
, ira_store_cost
, ira_shuffle_cost
;
351 int ira_move_loops_num
, ira_additional_jumps_num
;
353 /* All registers that can be eliminated. */
355 HARD_REG_SET eliminable_regset
;
357 /* Map: hard regs X modes -> set of hard registers for storing value
358 of given mode starting with given hard register. */
359 HARD_REG_SET ira_reg_mode_hard_regset
[FIRST_PSEUDO_REGISTER
][NUM_MACHINE_MODES
];
361 /* The following two variables are array analogs of the macros
362 MEMORY_MOVE_COST and REGISTER_MOVE_COST. */
363 short int ira_memory_move_cost
[MAX_MACHINE_MODE
][N_REG_CLASSES
][2];
364 move_table
*ira_register_move_cost
[MAX_MACHINE_MODE
];
366 /* Similar to may_move_in_cost but it is calculated in IRA instead of
367 regclass. Another difference is that we take only available hard
368 registers into account to figure out that one register class is a
369 subset of the another one. */
370 move_table
*ira_may_move_in_cost
[MAX_MACHINE_MODE
];
372 /* Similar to may_move_out_cost but it is calculated in IRA instead of
373 regclass. Another difference is that we take only available hard
374 registers into account to figure out that one register class is a
375 subset of the another one. */
376 move_table
*ira_may_move_out_cost
[MAX_MACHINE_MODE
];
378 /* Register class subset relation: TRUE if the first class is a subset
379 of the second one considering only hard registers available for the
381 int ira_class_subset_p
[N_REG_CLASSES
][N_REG_CLASSES
];
383 /* Temporary hard reg set used for a different calculation. */
384 static HARD_REG_SET temp_hard_regset
;
388 /* The function sets up the map IRA_REG_MODE_HARD_REGSET. */
390 setup_reg_mode_hard_regset (void)
392 int i
, m
, hard_regno
;
394 for (m
= 0; m
< NUM_MACHINE_MODES
; m
++)
395 for (hard_regno
= 0; hard_regno
< FIRST_PSEUDO_REGISTER
; hard_regno
++)
397 CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset
[hard_regno
][m
]);
398 for (i
= hard_regno_nregs
[hard_regno
][m
] - 1; i
>= 0; i
--)
399 if (hard_regno
+ i
< FIRST_PSEUDO_REGISTER
)
400 SET_HARD_REG_BIT (ira_reg_mode_hard_regset
[hard_regno
][m
],
407 /* Hard registers that can not be used for the register allocator for
408 all functions of the current compilation unit. */
409 static HARD_REG_SET no_unit_alloc_regs
;
411 /* Array of the number of hard registers of given class which are
412 available for allocation. The order is defined by the
414 short ira_class_hard_regs
[N_REG_CLASSES
][FIRST_PSEUDO_REGISTER
];
416 /* The number of elements of the above array for given register
418 int ira_class_hard_regs_num
[N_REG_CLASSES
];
420 /* Index (in ira_class_hard_regs) for given register class and hard
421 register (in general case a hard register can belong to several
422 register classes). The index is negative for hard registers
423 unavailable for the allocation. */
424 short ira_class_hard_reg_index
[N_REG_CLASSES
][FIRST_PSEUDO_REGISTER
];
426 /* The function sets up the three arrays declared above. */
428 setup_class_hard_regs (void)
430 int cl
, i
, hard_regno
, n
;
431 HARD_REG_SET processed_hard_reg_set
;
433 ira_assert (SHRT_MAX
>= FIRST_PSEUDO_REGISTER
);
434 /* We could call ORDER_REGS_FOR_LOCAL_ALLOC here (it is usually
435 putting hard callee-used hard registers first). But our
436 heuristics work better. */
437 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
439 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
440 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
441 CLEAR_HARD_REG_SET (processed_hard_reg_set
);
442 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
443 ira_class_hard_reg_index
[cl
][0] = -1;
444 for (n
= 0, i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
446 #ifdef REG_ALLOC_ORDER
447 hard_regno
= reg_alloc_order
[i
];
451 if (TEST_HARD_REG_BIT (processed_hard_reg_set
, hard_regno
))
453 SET_HARD_REG_BIT (processed_hard_reg_set
, hard_regno
);
454 if (! TEST_HARD_REG_BIT (temp_hard_regset
, hard_regno
))
455 ira_class_hard_reg_index
[cl
][hard_regno
] = -1;
458 ira_class_hard_reg_index
[cl
][hard_regno
] = n
;
459 ira_class_hard_regs
[cl
][n
++] = hard_regno
;
462 ira_class_hard_regs_num
[cl
] = n
;
466 /* Number of given class hard registers available for the register
467 allocation for given classes. */
468 int ira_available_class_regs
[N_REG_CLASSES
];
470 /* Set up IRA_AVAILABLE_CLASS_REGS. */
472 setup_available_class_regs (void)
476 memset (ira_available_class_regs
, 0, sizeof (ira_available_class_regs
));
477 for (i
= 0; i
< N_REG_CLASSES
; i
++)
479 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[i
]);
480 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
481 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
482 if (TEST_HARD_REG_BIT (temp_hard_regset
, j
))
483 ira_available_class_regs
[i
]++;
487 /* Set up global variables defining info about hard registers for the
488 allocation. These depend on USE_HARD_FRAME_P whose TRUE value means
489 that we can use the hard frame pointer for the allocation. */
491 setup_alloc_regs (bool use_hard_frame_p
)
493 COPY_HARD_REG_SET (no_unit_alloc_regs
, fixed_reg_set
);
494 if (! use_hard_frame_p
)
495 SET_HARD_REG_BIT (no_unit_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
496 setup_class_hard_regs ();
497 setup_available_class_regs ();
502 /* Set up IRA_MEMORY_MOVE_COST, IRA_REGISTER_MOVE_COST. */
504 setup_class_subset_and_memory_move_costs (void)
507 HARD_REG_SET temp_hard_regset2
;
509 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
510 ira_memory_move_cost
[mode
][NO_REGS
][0]
511 = ira_memory_move_cost
[mode
][NO_REGS
][1] = SHRT_MAX
;
512 for (cl
= (int) N_REG_CLASSES
- 1; cl
>= 0; cl
--)
514 if (cl
!= (int) NO_REGS
)
515 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
517 ira_memory_move_cost
[mode
][cl
][0] =
518 MEMORY_MOVE_COST ((enum machine_mode
) mode
,
519 (enum reg_class
) cl
, 0);
520 ira_memory_move_cost
[mode
][cl
][1] =
521 MEMORY_MOVE_COST ((enum machine_mode
) mode
,
522 (enum reg_class
) cl
, 1);
523 /* Costs for NO_REGS are used in cost calculation on the
524 1st pass when the preferred register classes are not
525 known yet. In this case we take the best scenario. */
526 if (ira_memory_move_cost
[mode
][NO_REGS
][0]
527 > ira_memory_move_cost
[mode
][cl
][0])
528 ira_memory_move_cost
[mode
][NO_REGS
][0]
529 = ira_memory_move_cost
[mode
][cl
][0];
530 if (ira_memory_move_cost
[mode
][NO_REGS
][1]
531 > ira_memory_move_cost
[mode
][cl
][1])
532 ira_memory_move_cost
[mode
][NO_REGS
][1]
533 = ira_memory_move_cost
[mode
][cl
][1];
535 for (cl2
= (int) N_REG_CLASSES
- 1; cl2
>= 0; cl2
--)
537 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
538 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
539 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[cl2
]);
540 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
541 ira_class_subset_p
[cl
][cl2
]
542 = hard_reg_set_subset_p (temp_hard_regset
, temp_hard_regset2
);
549 /* Define the following macro if allocation through malloc if
551 #define IRA_NO_OBSTACK
553 #ifndef IRA_NO_OBSTACK
554 /* Obstack used for storing all dynamic data (except bitmaps) of the
556 static struct obstack ira_obstack
;
559 /* Obstack used for storing all bitmaps of the IRA. */
560 static struct bitmap_obstack ira_bitmap_obstack
;
562 /* Allocate memory of size LEN for IRA data. */
564 ira_allocate (size_t len
)
568 #ifndef IRA_NO_OBSTACK
569 res
= obstack_alloc (&ira_obstack
, len
);
576 /* Reallocate memory PTR of size LEN for IRA data. */
578 ira_reallocate (void *ptr
, size_t len
)
582 #ifndef IRA_NO_OBSTACK
583 res
= obstack_alloc (&ira_obstack
, len
);
585 res
= xrealloc (ptr
, len
);
590 /* Free memory ADDR allocated for IRA data. */
592 ira_free (void *addr ATTRIBUTE_UNUSED
)
594 #ifndef IRA_NO_OBSTACK
602 /* Allocate and returns bitmap for IRA. */
604 ira_allocate_bitmap (void)
606 return BITMAP_ALLOC (&ira_bitmap_obstack
);
609 /* Free bitmap B allocated for IRA. */
611 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED
)
618 /* Output information about allocation of all allocnos (except for
619 caps) into file F. */
621 ira_print_disposition (FILE *f
)
627 fprintf (f
, "Disposition:");
628 max_regno
= max_reg_num ();
629 for (n
= 0, i
= FIRST_PSEUDO_REGISTER
; i
< max_regno
; i
++)
630 for (a
= ira_regno_allocno_map
[i
];
632 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
637 fprintf (f
, " %4d:r%-4d", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
638 if ((bb
= ALLOCNO_LOOP_TREE_NODE (a
)->bb
) != NULL
)
639 fprintf (f
, "b%-3d", bb
->index
);
641 fprintf (f
, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a
)->loop
->num
);
642 if (ALLOCNO_HARD_REGNO (a
) >= 0)
643 fprintf (f
, " %3d", ALLOCNO_HARD_REGNO (a
));
650 /* Outputs information about allocation of all allocnos into
653 ira_debug_disposition (void)
655 ira_print_disposition (stderr
);
660 /* For each reg class, table listing all the classes contained in it
661 (excluding the class itself. Non-allocatable registers are
662 excluded from the consideration). */
663 static enum reg_class alloc_reg_class_subclasses
[N_REG_CLASSES
][N_REG_CLASSES
];
665 /* Initialize the table of subclasses of each reg class. */
667 setup_reg_subclasses (void)
670 HARD_REG_SET temp_hard_regset2
;
672 for (i
= 0; i
< N_REG_CLASSES
; i
++)
673 for (j
= 0; j
< N_REG_CLASSES
; j
++)
674 alloc_reg_class_subclasses
[i
][j
] = LIM_REG_CLASSES
;
676 for (i
= 0; i
< N_REG_CLASSES
; i
++)
678 if (i
== (int) NO_REGS
)
681 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[i
]);
682 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
683 if (hard_reg_set_empty_p (temp_hard_regset
))
685 for (j
= 0; j
< N_REG_CLASSES
; j
++)
690 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[j
]);
691 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
692 if (! hard_reg_set_subset_p (temp_hard_regset
,
695 p
= &alloc_reg_class_subclasses
[j
][0];
696 while (*p
!= LIM_REG_CLASSES
) p
++;
697 *p
= (enum reg_class
) i
;
704 /* Number of cover classes. Cover classes is non-intersected register
705 classes containing all hard-registers available for the
707 int ira_reg_class_cover_size
;
709 /* The array containing cover classes (see also comments for macro
710 IRA_COVER_CLASSES). Only first IRA_REG_CLASS_COVER_SIZE elements are
712 enum reg_class ira_reg_class_cover
[N_REG_CLASSES
];
714 /* The number of elements in the subsequent array. */
715 int ira_important_classes_num
;
717 /* The array containing non-empty classes (including non-empty cover
718 classes) which are subclasses of cover classes. Such classes is
719 important for calculation of the hard register usage costs. */
720 enum reg_class ira_important_classes
[N_REG_CLASSES
];
722 /* The array containing indexes of important classes in the previous
723 array. The array elements are defined only for important
725 int ira_important_class_nums
[N_REG_CLASSES
];
727 /* Set the four global variables defined above. */
729 setup_cover_and_important_classes (void)
733 const enum reg_class
*cover_classes
;
734 HARD_REG_SET temp_hard_regset2
;
735 static enum reg_class classes
[LIM_REG_CLASSES
+ 1];
737 if (targetm
.ira_cover_classes
== NULL
)
738 cover_classes
= NULL
;
740 cover_classes
= targetm
.ira_cover_classes ();
741 if (cover_classes
== NULL
)
742 ira_assert (flag_ira_algorithm
== IRA_ALGORITHM_PRIORITY
);
745 for (i
= 0; (cl
= cover_classes
[i
]) != LIM_REG_CLASSES
; i
++)
746 classes
[i
] = (enum reg_class
) cl
;
747 classes
[i
] = LIM_REG_CLASSES
;
750 if (flag_ira_algorithm
== IRA_ALGORITHM_PRIORITY
)
753 for (i
= 0; i
<= LIM_REG_CLASSES
; i
++)
757 #ifdef CONSTRAINT_NUM_DEFINED_P
758 for (j
= 0; j
< CONSTRAINT__LIMIT
; j
++)
759 if ((int) REG_CLASS_FOR_CONSTRAINT ((enum constraint_num
) j
) == i
)
761 if (j
< CONSTRAINT__LIMIT
)
763 classes
[n
++] = (enum reg_class
) i
;
767 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[i
]);
768 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
769 for (j
= 0; j
< LIM_REG_CLASSES
; j
++)
773 COPY_HARD_REG_SET (temp_hard_regset2
, reg_class_contents
[j
]);
774 AND_COMPL_HARD_REG_SET (temp_hard_regset2
,
776 if (hard_reg_set_equal_p (temp_hard_regset
,
781 classes
[n
++] = (enum reg_class
) i
;
783 classes
[n
] = LIM_REG_CLASSES
;
786 ira_reg_class_cover_size
= 0;
787 for (i
= 0; (cl
= classes
[i
]) != LIM_REG_CLASSES
; i
++)
789 for (j
= 0; j
< i
; j
++)
790 if (flag_ira_algorithm
!= IRA_ALGORITHM_PRIORITY
791 && reg_classes_intersect_p ((enum reg_class
) cl
, classes
[j
]))
793 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
794 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
795 if (! hard_reg_set_empty_p (temp_hard_regset
))
796 ira_reg_class_cover
[ira_reg_class_cover_size
++] = (enum reg_class
) cl
;
798 ira_important_classes_num
= 0;
799 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
801 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
802 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
803 if (! hard_reg_set_empty_p (temp_hard_regset
))
805 set_p
= eq_p
= false;
806 for (j
= 0; j
< ira_reg_class_cover_size
; j
++)
808 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
809 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
810 COPY_HARD_REG_SET (temp_hard_regset2
,
811 reg_class_contents
[ira_reg_class_cover
[j
]]);
812 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
813 if ((enum reg_class
) cl
== ira_reg_class_cover
[j
])
819 else if (hard_reg_set_equal_p (temp_hard_regset
,
822 else if (hard_reg_set_subset_p (temp_hard_regset
,
828 ira_important_class_nums
[cl
] = ira_important_classes_num
;
829 ira_important_classes
[ira_important_classes_num
++] =
836 /* Map of all register classes to corresponding cover class containing
837 the given class. If given class is not a subset of a cover class,
838 we translate it into the cheapest cover class. */
839 enum reg_class ira_class_translate
[N_REG_CLASSES
];
841 /* Set up array IRA_CLASS_TRANSLATE. */
843 setup_class_translate (void)
846 enum reg_class cover_class
, best_class
, *cl_ptr
;
847 int i
, cost
, min_cost
, best_cost
;
849 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
850 ira_class_translate
[cl
] = NO_REGS
;
852 if (flag_ira_algorithm
== IRA_ALGORITHM_PRIORITY
)
853 for (cl
= 0; cl
< LIM_REG_CLASSES
; cl
++)
855 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
856 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
857 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
859 HARD_REG_SET temp_hard_regset2
;
861 cover_class
= ira_reg_class_cover
[i
];
862 COPY_HARD_REG_SET (temp_hard_regset2
,
863 reg_class_contents
[cover_class
]);
864 AND_COMPL_HARD_REG_SET (temp_hard_regset2
, no_unit_alloc_regs
);
865 if (hard_reg_set_equal_p (temp_hard_regset
, temp_hard_regset2
))
866 ira_class_translate
[cl
] = cover_class
;
869 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
871 cover_class
= ira_reg_class_cover
[i
];
872 if (flag_ira_algorithm
!= IRA_ALGORITHM_PRIORITY
)
873 for (cl_ptr
= &alloc_reg_class_subclasses
[cover_class
][0];
874 (cl
= *cl_ptr
) != LIM_REG_CLASSES
;
877 if (ira_class_translate
[cl
] == NO_REGS
)
878 ira_class_translate
[cl
] = cover_class
;
879 #ifdef ENABLE_IRA_CHECKING
882 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
883 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
884 if (! hard_reg_set_empty_p (temp_hard_regset
))
889 ira_class_translate
[cover_class
] = cover_class
;
891 /* For classes which are not fully covered by a cover class (in
892 other words covered by more one cover class), use the cheapest
894 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
896 if (cl
== NO_REGS
|| ira_class_translate
[cl
] != NO_REGS
)
898 best_class
= NO_REGS
;
900 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
902 cover_class
= ira_reg_class_cover
[i
];
903 COPY_HARD_REG_SET (temp_hard_regset
,
904 reg_class_contents
[cover_class
]);
905 AND_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl
]);
906 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
907 if (! hard_reg_set_empty_p (temp_hard_regset
))
910 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
912 cost
= (ira_memory_move_cost
[mode
][cl
][0]
913 + ira_memory_move_cost
[mode
][cl
][1]);
917 if (best_class
== NO_REGS
|| best_cost
> min_cost
)
919 best_class
= cover_class
;
920 best_cost
= min_cost
;
924 ira_class_translate
[cl
] = best_class
;
928 /* The biggest important reg_class inside of intersection of the two
929 reg_classes (that is calculated taking only hard registers
930 available for allocation into account). If the both reg_classes
931 contain no hard registers available for allocation, the value is
932 calculated by taking all hard-registers including fixed ones into
934 enum reg_class ira_reg_class_intersect
[N_REG_CLASSES
][N_REG_CLASSES
];
936 /* True if the two classes (that is calculated taking only hard
937 registers available for allocation into account) are
939 bool ira_reg_classes_intersect_p
[N_REG_CLASSES
][N_REG_CLASSES
];
941 /* Important classes with end marker LIM_REG_CLASSES which are
942 supersets with given important class (the first index). That
943 includes given class itself. This is calculated taking only hard
944 registers available for allocation into account. */
945 enum reg_class ira_reg_class_super_classes
[N_REG_CLASSES
][N_REG_CLASSES
];
947 /* The biggest important reg_class inside of union of the two
948 reg_classes (that is calculated taking only hard registers
949 available for allocation into account). If the both reg_classes
950 contain no hard registers available for allocation, the value is
951 calculated by taking all hard-registers including fixed ones into
952 account. In other words, the value is the corresponding
953 reg_class_subunion value. */
954 enum reg_class ira_reg_class_union
[N_REG_CLASSES
][N_REG_CLASSES
];
956 /* Set up the above reg class relations. */
958 setup_reg_class_relations (void)
960 int i
, cl1
, cl2
, cl3
;
961 HARD_REG_SET intersection_set
, union_set
, temp_set2
;
962 bool important_class_p
[N_REG_CLASSES
];
964 memset (important_class_p
, 0, sizeof (important_class_p
));
965 for (i
= 0; i
< ira_important_classes_num
; i
++)
966 important_class_p
[ira_important_classes
[i
]] = true;
967 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
969 ira_reg_class_super_classes
[cl1
][0] = LIM_REG_CLASSES
;
970 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
972 ira_reg_classes_intersect_p
[cl1
][cl2
] = false;
973 ira_reg_class_intersect
[cl1
][cl2
] = NO_REGS
;
974 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl1
]);
975 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
976 COPY_HARD_REG_SET (temp_set2
, reg_class_contents
[cl2
]);
977 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
978 if (hard_reg_set_empty_p (temp_hard_regset
)
979 && hard_reg_set_empty_p (temp_set2
))
983 cl3
= reg_class_subclasses
[cl1
][i
];
984 if (cl3
== LIM_REG_CLASSES
)
986 if (reg_class_subset_p (ira_reg_class_intersect
[cl1
][cl2
],
987 (enum reg_class
) cl3
))
988 ira_reg_class_intersect
[cl1
][cl2
] = (enum reg_class
) cl3
;
990 ira_reg_class_union
[cl1
][cl2
] = reg_class_subunion
[cl1
][cl2
];
993 ira_reg_classes_intersect_p
[cl1
][cl2
]
994 = hard_reg_set_intersect_p (temp_hard_regset
, temp_set2
);
995 if (important_class_p
[cl1
] && important_class_p
[cl2
]
996 && hard_reg_set_subset_p (temp_hard_regset
, temp_set2
))
1000 p
= &ira_reg_class_super_classes
[cl1
][0];
1001 while (*p
!= LIM_REG_CLASSES
)
1003 *p
++ = (enum reg_class
) cl2
;
1004 *p
= LIM_REG_CLASSES
;
1006 ira_reg_class_union
[cl1
][cl2
] = NO_REGS
;
1007 COPY_HARD_REG_SET (intersection_set
, reg_class_contents
[cl1
]);
1008 AND_HARD_REG_SET (intersection_set
, reg_class_contents
[cl2
]);
1009 AND_COMPL_HARD_REG_SET (intersection_set
, no_unit_alloc_regs
);
1010 COPY_HARD_REG_SET (union_set
, reg_class_contents
[cl1
]);
1011 IOR_HARD_REG_SET (union_set
, reg_class_contents
[cl2
]);
1012 AND_COMPL_HARD_REG_SET (union_set
, no_unit_alloc_regs
);
1013 for (i
= 0; i
< ira_important_classes_num
; i
++)
1015 cl3
= ira_important_classes
[i
];
1016 COPY_HARD_REG_SET (temp_hard_regset
, reg_class_contents
[cl3
]);
1017 AND_COMPL_HARD_REG_SET (temp_hard_regset
, no_unit_alloc_regs
);
1018 if (hard_reg_set_subset_p (temp_hard_regset
, intersection_set
))
1022 reg_class_contents
[(int)
1023 ira_reg_class_intersect
[cl1
][cl2
]]);
1024 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1025 if (! hard_reg_set_subset_p (temp_hard_regset
, temp_set2
)
1026 /* Ignore unavailable hard registers and prefer
1027 smallest class for debugging purposes. */
1028 || (hard_reg_set_equal_p (temp_hard_regset
, temp_set2
)
1029 && hard_reg_set_subset_p
1030 (reg_class_contents
[cl3
],
1032 [(int) ira_reg_class_intersect
[cl1
][cl2
]])))
1033 ira_reg_class_intersect
[cl1
][cl2
] = (enum reg_class
) cl3
;
1035 if (hard_reg_set_subset_p (temp_hard_regset
, union_set
))
1039 reg_class_contents
[(int) ira_reg_class_union
[cl1
][cl2
]]);
1040 AND_COMPL_HARD_REG_SET (temp_set2
, no_unit_alloc_regs
);
1041 if (ira_reg_class_union
[cl1
][cl2
] == NO_REGS
1042 || (hard_reg_set_subset_p (temp_set2
, temp_hard_regset
)
1044 && (! hard_reg_set_equal_p (temp_set2
,
1046 /* Ignore unavailable hard registers and
1047 prefer smallest class for debugging
1049 || hard_reg_set_subset_p
1050 (reg_class_contents
[cl3
],
1052 [(int) ira_reg_class_union
[cl1
][cl2
]]))))
1053 ira_reg_class_union
[cl1
][cl2
] = (enum reg_class
) cl3
;
1060 /* Output all cover classes and the translation map into file F. */
1062 print_class_cover (FILE *f
)
1064 static const char *const reg_class_names
[] = REG_CLASS_NAMES
;
1067 fprintf (f
, "Class cover:\n");
1068 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1069 fprintf (f
, " %s", reg_class_names
[ira_reg_class_cover
[i
]]);
1070 fprintf (f
, "\nClass translation:\n");
1071 for (i
= 0; i
< N_REG_CLASSES
; i
++)
1072 fprintf (f
, " %s -> %s\n", reg_class_names
[i
],
1073 reg_class_names
[ira_class_translate
[i
]]);
1076 /* Output all cover classes and the translation map into
1079 ira_debug_class_cover (void)
1081 print_class_cover (stderr
);
1084 /* Set up different arrays concerning class subsets, cover and
1085 important classes. */
1087 find_reg_class_closure (void)
1089 setup_reg_subclasses ();
1090 setup_cover_and_important_classes ();
1091 setup_class_translate ();
1092 setup_reg_class_relations ();
1097 /* Map: hard register number -> cover class it belongs to. If the
1098 corresponding class is NO_REGS, the hard register is not available
1100 enum reg_class ira_hard_regno_cover_class
[FIRST_PSEUDO_REGISTER
];
1102 /* Set up the array above. */
1104 setup_hard_regno_cover_class (void)
1109 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1111 ira_hard_regno_cover_class
[i
] = NO_REGS
;
1112 for (j
= 0; j
< ira_reg_class_cover_size
; j
++)
1114 cl
= ira_reg_class_cover
[j
];
1115 if (ira_class_hard_reg_index
[cl
][i
] >= 0)
1117 ira_hard_regno_cover_class
[i
] = cl
;
1127 /* Map: register class x machine mode -> number of hard registers of
1128 given class needed to store value of given mode. If the number is
1129 different, the size will be negative. */
1130 int ira_reg_class_nregs
[N_REG_CLASSES
][MAX_MACHINE_MODE
];
1132 /* Maximal value of the previous array elements. */
1135 /* Form IRA_REG_CLASS_NREGS map. */
1137 setup_reg_class_nregs (void)
1142 for (cl
= 0; cl
< N_REG_CLASSES
; cl
++)
1143 for (m
= 0; m
< MAX_MACHINE_MODE
; m
++)
1145 ira_reg_class_nregs
[cl
][m
] = CLASS_MAX_NREGS ((enum reg_class
) cl
,
1146 (enum machine_mode
) m
);
1147 if (ira_max_nregs
< ira_reg_class_nregs
[cl
][m
])
1148 ira_max_nregs
= ira_reg_class_nregs
[cl
][m
];
1154 /* Array whose values are hard regset of hard registers available for
1155 the allocation of given register class whose HARD_REGNO_MODE_OK
1156 values for given mode are zero. */
1157 HARD_REG_SET prohibited_class_mode_regs
[N_REG_CLASSES
][NUM_MACHINE_MODES
];
1159 /* Set up PROHIBITED_CLASS_MODE_REGS. */
1161 setup_prohibited_class_mode_regs (void)
1163 int i
, j
, k
, hard_regno
;
1166 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1168 cl
= ira_reg_class_cover
[i
];
1169 for (j
= 0; j
< NUM_MACHINE_MODES
; j
++)
1171 CLEAR_HARD_REG_SET (prohibited_class_mode_regs
[cl
][j
]);
1172 for (k
= ira_class_hard_regs_num
[cl
] - 1; k
>= 0; k
--)
1174 hard_regno
= ira_class_hard_regs
[cl
][k
];
1175 if (! HARD_REGNO_MODE_OK (hard_regno
, (enum machine_mode
) j
))
1176 SET_HARD_REG_BIT (prohibited_class_mode_regs
[cl
][j
],
1185 /* Allocate and initialize IRA_REGISTER_MOVE_COST,
1186 IRA_MAY_MOVE_IN_COST, and IRA_MAY_MOVE_OUT_COST for MODE if it is
1189 ira_init_register_move_cost (enum machine_mode mode
)
1193 ira_assert (ira_register_move_cost
[mode
] == NULL
1194 && ira_may_move_in_cost
[mode
] == NULL
1195 && ira_may_move_out_cost
[mode
] == NULL
);
1196 if (move_cost
[mode
] == NULL
)
1197 init_move_cost (mode
);
1198 ira_register_move_cost
[mode
] = move_cost
[mode
];
1199 /* Don't use ira_allocate because the tables exist out of scope of a
1201 ira_may_move_in_cost
[mode
]
1202 = (move_table
*) xmalloc (sizeof (move_table
) * N_REG_CLASSES
);
1203 memcpy (ira_may_move_in_cost
[mode
], may_move_in_cost
[mode
],
1204 sizeof (move_table
) * N_REG_CLASSES
);
1205 ira_may_move_out_cost
[mode
]
1206 = (move_table
*) xmalloc (sizeof (move_table
) * N_REG_CLASSES
);
1207 memcpy (ira_may_move_out_cost
[mode
], may_move_out_cost
[mode
],
1208 sizeof (move_table
) * N_REG_CLASSES
);
1209 for (cl1
= 0; cl1
< N_REG_CLASSES
; cl1
++)
1211 for (cl2
= 0; cl2
< N_REG_CLASSES
; cl2
++)
1213 if (ira_class_subset_p
[cl1
][cl2
])
1214 ira_may_move_in_cost
[mode
][cl1
][cl2
] = 0;
1215 if (ira_class_subset_p
[cl2
][cl1
])
1216 ira_may_move_out_cost
[mode
][cl1
][cl2
] = 0;
1223 /* This is called once during compiler work. It sets up
1224 different arrays whose values don't depend on the compiled
1227 ira_init_once (void)
1231 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
1233 ira_register_move_cost
[mode
] = NULL
;
1234 ira_may_move_in_cost
[mode
] = NULL
;
1235 ira_may_move_out_cost
[mode
] = NULL
;
1237 ira_init_costs_once ();
1240 /* Free ira_register_move_cost, ira_may_move_in_cost, and
1241 ira_may_move_out_cost for each mode. */
1243 free_register_move_costs (void)
1247 for (mode
= 0; mode
< MAX_MACHINE_MODE
; mode
++)
1249 if (ira_may_move_in_cost
[mode
] != NULL
)
1250 free (ira_may_move_in_cost
[mode
]);
1251 if (ira_may_move_out_cost
[mode
] != NULL
)
1252 free (ira_may_move_out_cost
[mode
]);
1253 ira_register_move_cost
[mode
] = NULL
;
1254 ira_may_move_in_cost
[mode
] = NULL
;
1255 ira_may_move_out_cost
[mode
] = NULL
;
1259 /* This is called every time when register related information is
1264 free_register_move_costs ();
1265 setup_reg_mode_hard_regset ();
1266 setup_alloc_regs (flag_omit_frame_pointer
!= 0);
1267 setup_class_subset_and_memory_move_costs ();
1268 find_reg_class_closure ();
1269 setup_hard_regno_cover_class ();
1270 setup_reg_class_nregs ();
1271 setup_prohibited_class_mode_regs ();
1275 /* Function called once at the end of compiler work. */
1277 ira_finish_once (void)
1279 ira_finish_costs_once ();
1280 free_register_move_costs ();
1285 /* Array whose values are hard regset of hard registers for which
1286 move of the hard register in given mode into itself is
1288 HARD_REG_SET ira_prohibited_mode_move_regs
[NUM_MACHINE_MODES
];
1290 /* Flag of that the above array has been initialized. */
1291 static bool ira_prohibited_mode_move_regs_initialized_p
= false;
1293 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS. */
1295 setup_prohibited_mode_move_regs (void)
1298 rtx test_reg1
, test_reg2
, move_pat
, move_insn
;
1300 if (ira_prohibited_mode_move_regs_initialized_p
)
1302 ira_prohibited_mode_move_regs_initialized_p
= true;
1303 test_reg1
= gen_rtx_REG (VOIDmode
, 0);
1304 test_reg2
= gen_rtx_REG (VOIDmode
, 0);
1305 move_pat
= gen_rtx_SET (VOIDmode
, test_reg1
, test_reg2
);
1306 move_insn
= gen_rtx_INSN (VOIDmode
, 0, 0, 0, 0, 0, move_pat
, -1, 0);
1307 for (i
= 0; i
< NUM_MACHINE_MODES
; i
++)
1309 SET_HARD_REG_SET (ira_prohibited_mode_move_regs
[i
]);
1310 for (j
= 0; j
< FIRST_PSEUDO_REGISTER
; j
++)
1312 if (! HARD_REGNO_MODE_OK (j
, (enum machine_mode
) i
))
1314 SET_REGNO (test_reg1
, j
);
1315 PUT_MODE (test_reg1
, (enum machine_mode
) i
);
1316 SET_REGNO (test_reg2
, j
);
1317 PUT_MODE (test_reg2
, (enum machine_mode
) i
);
1318 INSN_CODE (move_insn
) = -1;
1319 recog_memoized (move_insn
);
1320 if (INSN_CODE (move_insn
) < 0)
1322 extract_insn (move_insn
);
1323 if (! constrain_operands (1))
1325 CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs
[i
], j
);
1332 /* Function specific hard registers that can not be used for the
1333 register allocation. */
1334 HARD_REG_SET ira_no_alloc_regs
;
1336 /* Return TRUE if *LOC contains an asm. */
1338 insn_contains_asm_1 (rtx
*loc
, void *data ATTRIBUTE_UNUSED
)
1342 if (GET_CODE (*loc
) == ASM_OPERANDS
)
1348 /* Return TRUE if INSN contains an ASM. */
1350 insn_contains_asm (rtx insn
)
1352 return for_each_rtx (&insn
, insn_contains_asm_1
, NULL
);
1355 /* Set up regs_asm_clobbered. */
1357 compute_regs_asm_clobbered (char *regs_asm_clobbered
)
1361 memset (regs_asm_clobbered
, 0, sizeof (char) * FIRST_PSEUDO_REGISTER
);
1366 FOR_BB_INSNS_REVERSE (bb
, insn
)
1370 if (insn_contains_asm (insn
))
1371 for (def_rec
= DF_INSN_DEFS (insn
); *def_rec
; def_rec
++)
1373 df_ref def
= *def_rec
;
1374 unsigned int dregno
= DF_REF_REGNO (def
);
1375 if (dregno
< FIRST_PSEUDO_REGISTER
)
1378 enum machine_mode mode
= GET_MODE (DF_REF_REAL_REG (def
));
1379 unsigned int end
= dregno
1380 + hard_regno_nregs
[dregno
][mode
] - 1;
1382 for (i
= dregno
; i
<= end
; ++i
)
1383 regs_asm_clobbered
[i
] = 1;
1391 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and REGS_EVER_LIVE. */
1393 setup_eliminable_regset (void)
1395 /* Like regs_ever_live, but 1 if a reg is set or clobbered from an
1396 asm. Unlike regs_ever_live, elements of this array corresponding
1397 to eliminable regs (like the frame pointer) are set if an asm
1399 char *regs_asm_clobbered
1400 = (char *) alloca (FIRST_PSEUDO_REGISTER
* sizeof (char));
1401 #ifdef ELIMINABLE_REGS
1403 static const struct {const int from
, to
; } eliminables
[] = ELIMINABLE_REGS
;
1405 /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
1406 sp for alloca. So we can't eliminate the frame pointer in that
1407 case. At some point, we should improve this by emitting the
1408 sp-adjusting insns for this case. */
1410 = (! flag_omit_frame_pointer
1411 || (cfun
->calls_alloca
&& EXIT_IGNORE_STACK
)
1412 || crtl
->accesses_prior_frames
1413 || crtl
->stack_realign_needed
1414 || targetm
.frame_pointer_required ());
1416 frame_pointer_needed
= need_fp
;
1418 COPY_HARD_REG_SET (ira_no_alloc_regs
, no_unit_alloc_regs
);
1419 CLEAR_HARD_REG_SET (eliminable_regset
);
1421 compute_regs_asm_clobbered (regs_asm_clobbered
);
1422 /* Build the regset of all eliminable registers and show we can't
1423 use those that we already know won't be eliminated. */
1424 #ifdef ELIMINABLE_REGS
1425 for (i
= 0; i
< (int) ARRAY_SIZE (eliminables
); i
++)
1428 = (! CAN_ELIMINATE (eliminables
[i
].from
, eliminables
[i
].to
)
1429 || (eliminables
[i
].to
== STACK_POINTER_REGNUM
&& need_fp
));
1431 if (! regs_asm_clobbered
[eliminables
[i
].from
])
1433 SET_HARD_REG_BIT (eliminable_regset
, eliminables
[i
].from
);
1436 SET_HARD_REG_BIT (ira_no_alloc_regs
, eliminables
[i
].from
);
1438 else if (cannot_elim
)
1439 error ("%s cannot be used in asm here",
1440 reg_names
[eliminables
[i
].from
]);
1442 df_set_regs_ever_live (eliminables
[i
].from
, true);
1444 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
1445 if (! regs_asm_clobbered
[HARD_FRAME_POINTER_REGNUM
])
1447 SET_HARD_REG_BIT (eliminable_regset
, HARD_FRAME_POINTER_REGNUM
);
1449 SET_HARD_REG_BIT (ira_no_alloc_regs
, HARD_FRAME_POINTER_REGNUM
);
1452 error ("%s cannot be used in asm here",
1453 reg_names
[HARD_FRAME_POINTER_REGNUM
]);
1455 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM
, true);
1459 if (! regs_asm_clobbered
[FRAME_POINTER_REGNUM
])
1461 SET_HARD_REG_BIT (eliminable_regset
, FRAME_POINTER_REGNUM
);
1463 SET_HARD_REG_BIT (ira_no_alloc_regs
, FRAME_POINTER_REGNUM
);
1466 error ("%s cannot be used in asm here", reg_names
[FRAME_POINTER_REGNUM
]);
1468 df_set_regs_ever_live (FRAME_POINTER_REGNUM
, true);
1474 /* The length of the following two arrays. */
1475 int ira_reg_equiv_len
;
1477 /* The element value is TRUE if the corresponding regno value is
1479 bool *ira_reg_equiv_invariant_p
;
1481 /* The element value is equiv constant of given pseudo-register or
1483 rtx
*ira_reg_equiv_const
;
1485 /* Set up the two arrays declared above. */
1487 find_reg_equiv_invariant_const (void)
1491 rtx list
, insn
, note
, constant
, x
;
1493 for (i
= FIRST_PSEUDO_REGISTER
; i
< reg_equiv_init_size
; i
++)
1495 constant
= NULL_RTX
;
1496 invariant_p
= false;
1497 for (list
= reg_equiv_init
[i
]; list
!= NULL_RTX
; list
= XEXP (list
, 1))
1499 insn
= XEXP (list
, 0);
1500 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
1502 if (note
== NULL_RTX
)
1507 if (! function_invariant_p (x
)
1509 /* A function invariant is often CONSTANT_P but may
1510 include a register. We promise to only pass CONSTANT_P
1511 objects to LEGITIMATE_PIC_OPERAND_P. */
1512 || (CONSTANT_P (x
) && LEGITIMATE_PIC_OPERAND_P (x
)))
1514 /* It can happen that a REG_EQUIV note contains a MEM
1515 that is not a legitimate memory operand. As later
1516 stages of the reload assume that all addresses found
1517 in the reg_equiv_* arrays were originally legitimate,
1518 we ignore such REG_EQUIV notes. */
1519 if (memory_operand (x
, VOIDmode
))
1520 invariant_p
= MEM_READONLY_P (x
);
1521 else if (function_invariant_p (x
))
1523 if (GET_CODE (x
) == PLUS
1524 || x
== frame_pointer_rtx
|| x
== arg_pointer_rtx
)
1531 ira_reg_equiv_invariant_p
[i
] = invariant_p
;
1532 ira_reg_equiv_const
[i
] = constant
;
1538 /* Vector of substitutions of register numbers,
1539 used to map pseudo regs into hardware regs.
1540 This is set up as a result of register allocation.
1541 Element N is the hard reg assigned to pseudo reg N,
1542 or is -1 if no hard reg was assigned.
1543 If N is a hard reg number, element N is N. */
1544 short *reg_renumber
;
1546 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
1547 the allocation found by IRA. */
1549 setup_reg_renumber (void)
1551 int regno
, hard_regno
;
1553 ira_allocno_iterator ai
;
1555 caller_save_needed
= 0;
1556 FOR_EACH_ALLOCNO (a
, ai
)
1558 /* There are no caps at this point. */
1559 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
1560 if (! ALLOCNO_ASSIGNED_P (a
))
1561 /* It can happen if A is not referenced but partially anticipated
1562 somewhere in a region. */
1563 ALLOCNO_ASSIGNED_P (a
) = true;
1564 ira_free_allocno_updated_costs (a
);
1565 hard_regno
= ALLOCNO_HARD_REGNO (a
);
1566 regno
= (int) REGNO (ALLOCNO_REG (a
));
1567 reg_renumber
[regno
] = (hard_regno
< 0 ? -1 : hard_regno
);
1568 if (hard_regno
>= 0 && ALLOCNO_CALLS_CROSSED_NUM (a
) != 0
1569 && ! ira_hard_reg_not_in_set_p (hard_regno
, ALLOCNO_MODE (a
),
1572 ira_assert (!optimize
|| flag_caller_saves
1573 || regno
>= ira_reg_equiv_len
1574 || ira_reg_equiv_const
[regno
]
1575 || ira_reg_equiv_invariant_p
[regno
]);
1576 caller_save_needed
= 1;
1581 /* Set up allocno assignment flags for further allocation
1584 setup_allocno_assignment_flags (void)
1588 ira_allocno_iterator ai
;
1590 FOR_EACH_ALLOCNO (a
, ai
)
1592 if (! ALLOCNO_ASSIGNED_P (a
))
1593 /* It can happen if A is not referenced but partially anticipated
1594 somewhere in a region. */
1595 ira_free_allocno_updated_costs (a
);
1596 hard_regno
= ALLOCNO_HARD_REGNO (a
);
1597 /* Don't assign hard registers to allocnos which are destination
1598 of removed store at the end of loop. It has no sense to keep
1599 the same value in different hard registers. It is also
1600 impossible to assign hard registers correctly to such
1601 allocnos because the cost info and info about intersected
1602 calls are incorrect for them. */
1603 ALLOCNO_ASSIGNED_P (a
) = (hard_regno
>= 0
1604 || ALLOCNO_MEM_OPTIMIZED_DEST_P (a
)
1605 || (ALLOCNO_MEMORY_COST (a
)
1606 - ALLOCNO_COVER_CLASS_COST (a
)) < 0);
1607 ira_assert (hard_regno
< 0
1608 || ! ira_hard_reg_not_in_set_p (hard_regno
, ALLOCNO_MODE (a
),
1610 [ALLOCNO_COVER_CLASS (a
)]));
1614 /* Evaluate overall allocation cost and the costs for using hard
1615 registers and memory for allocnos. */
1617 calculate_allocation_cost (void)
1619 int hard_regno
, cost
;
1621 ira_allocno_iterator ai
;
1623 ira_overall_cost
= ira_reg_cost
= ira_mem_cost
= 0;
1624 FOR_EACH_ALLOCNO (a
, ai
)
1626 hard_regno
= ALLOCNO_HARD_REGNO (a
);
1627 ira_assert (hard_regno
< 0
1628 || ! ira_hard_reg_not_in_set_p
1629 (hard_regno
, ALLOCNO_MODE (a
),
1630 reg_class_contents
[ALLOCNO_COVER_CLASS (a
)]));
1633 cost
= ALLOCNO_MEMORY_COST (a
);
1634 ira_mem_cost
+= cost
;
1636 else if (ALLOCNO_HARD_REG_COSTS (a
) != NULL
)
1638 cost
= (ALLOCNO_HARD_REG_COSTS (a
)
1639 [ira_class_hard_reg_index
1640 [ALLOCNO_COVER_CLASS (a
)][hard_regno
]]);
1641 ira_reg_cost
+= cost
;
1645 cost
= ALLOCNO_COVER_CLASS_COST (a
);
1646 ira_reg_cost
+= cost
;
1648 ira_overall_cost
+= cost
;
1651 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
1653 fprintf (ira_dump_file
,
1654 "+++Costs: overall %d, reg %d, mem %d, ld %d, st %d, move %d\n",
1655 ira_overall_cost
, ira_reg_cost
, ira_mem_cost
,
1656 ira_load_cost
, ira_store_cost
, ira_shuffle_cost
);
1657 fprintf (ira_dump_file
, "+++ move loops %d, new jumps %d\n",
1658 ira_move_loops_num
, ira_additional_jumps_num
);
1663 #ifdef ENABLE_IRA_CHECKING
1664 /* Check the correctness of the allocation. We do need this because
1665 of complicated code to transform more one region internal
1666 representation into one region representation. */
1668 check_allocation (void)
1670 ira_allocno_t a
, conflict_a
;
1671 int hard_regno
, conflict_hard_regno
, nregs
, conflict_nregs
;
1672 ira_allocno_conflict_iterator aci
;
1673 ira_allocno_iterator ai
;
1675 FOR_EACH_ALLOCNO (a
, ai
)
1677 if (ALLOCNO_CAP_MEMBER (a
) != NULL
1678 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0)
1680 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (a
)];
1681 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_a
, aci
)
1682 if ((conflict_hard_regno
= ALLOCNO_HARD_REGNO (conflict_a
)) >= 0)
1686 [conflict_hard_regno
][ALLOCNO_MODE (conflict_a
)]);
1687 if ((conflict_hard_regno
<= hard_regno
1688 && hard_regno
< conflict_hard_regno
+ conflict_nregs
)
1689 || (hard_regno
<= conflict_hard_regno
1690 && conflict_hard_regno
< hard_regno
+ nregs
))
1692 fprintf (stderr
, "bad allocation for %d and %d\n",
1693 ALLOCNO_REGNO (a
), ALLOCNO_REGNO (conflict_a
));
1701 /* Fix values of array REG_EQUIV_INIT after live range splitting done
1704 fix_reg_equiv_init (void)
1706 int max_regno
= max_reg_num ();
1708 rtx x
, prev
, next
, insn
, set
;
1710 if (reg_equiv_init_size
< max_regno
)
1713 = (rtx
*) ggc_realloc (reg_equiv_init
, max_regno
* sizeof (rtx
));
1714 while (reg_equiv_init_size
< max_regno
)
1715 reg_equiv_init
[reg_equiv_init_size
++] = NULL_RTX
;
1716 for (i
= FIRST_PSEUDO_REGISTER
; i
< reg_equiv_init_size
; i
++)
1717 for (prev
= NULL_RTX
, x
= reg_equiv_init
[i
]; x
!= NULL_RTX
; x
= next
)
1721 set
= single_set (insn
);
1722 ira_assert (set
!= NULL_RTX
1723 && (REG_P (SET_DEST (set
)) || REG_P (SET_SRC (set
))));
1724 if (REG_P (SET_DEST (set
))
1725 && ((int) REGNO (SET_DEST (set
)) == i
1726 || (int) ORIGINAL_REGNO (SET_DEST (set
)) == i
))
1727 new_regno
= REGNO (SET_DEST (set
));
1728 else if (REG_P (SET_SRC (set
))
1729 && ((int) REGNO (SET_SRC (set
)) == i
1730 || (int) ORIGINAL_REGNO (SET_SRC (set
)) == i
))
1731 new_regno
= REGNO (SET_SRC (set
));
1738 if (prev
== NULL_RTX
)
1739 reg_equiv_init
[i
] = next
;
1741 XEXP (prev
, 1) = next
;
1742 XEXP (x
, 1) = reg_equiv_init
[new_regno
];
1743 reg_equiv_init
[new_regno
] = x
;
1749 #ifdef ENABLE_IRA_CHECKING
1750 /* Print redundant memory-memory copies. */
1752 print_redundant_copies (void)
1756 ira_copy_t cp
, next_cp
;
1757 ira_allocno_iterator ai
;
1759 FOR_EACH_ALLOCNO (a
, ai
)
1761 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
1764 hard_regno
= ALLOCNO_HARD_REGNO (a
);
1765 if (hard_regno
>= 0)
1767 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
1769 next_cp
= cp
->next_first_allocno_copy
;
1772 next_cp
= cp
->next_second_allocno_copy
;
1773 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
1774 && cp
->insn
!= NULL_RTX
1775 && ALLOCNO_HARD_REGNO (cp
->first
) == hard_regno
)
1776 fprintf (ira_dump_file
,
1777 " Redundant move from %d(freq %d):%d\n",
1778 INSN_UID (cp
->insn
), cp
->freq
, hard_regno
);
1784 /* Setup preferred and alternative classes for new pseudo-registers
1785 created by IRA starting with START. */
1787 setup_preferred_alternate_classes_for_new_pseudos (int start
)
1790 int max_regno
= max_reg_num ();
1792 for (i
= start
; i
< max_regno
; i
++)
1794 old_regno
= ORIGINAL_REGNO (regno_reg_rtx
[i
]);
1795 ira_assert (i
!= old_regno
);
1796 setup_reg_classes (i
, reg_preferred_class (old_regno
),
1797 reg_alternate_class (old_regno
));
1798 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1799 fprintf (ira_dump_file
,
1800 " New r%d: setting preferred %s, alternative %s\n",
1801 i
, reg_class_names
[reg_preferred_class (old_regno
)],
1802 reg_class_names
[reg_alternate_class (old_regno
)]);
1808 /* Regional allocation can create new pseudo-registers. This function
1809 expands some arrays for pseudo-registers. */
1811 expand_reg_info (int old_size
)
1814 int size
= max_reg_num ();
1817 for (i
= old_size
; i
< size
; i
++)
1819 reg_renumber
[i
] = -1;
1820 setup_reg_classes (i
, GENERAL_REGS
, ALL_REGS
);
1824 /* Return TRUE if there is too high register pressure in the function.
1825 It is used to decide when stack slot sharing is worth to do. */
1827 too_high_register_pressure_p (void)
1830 enum reg_class cover_class
;
1832 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1834 cover_class
= ira_reg_class_cover
[i
];
1835 if (ira_loop_tree_root
->reg_pressure
[cover_class
] > 10000)
1843 /* Indicate that hard register number FROM was eliminated and replaced with
1844 an offset from hard register number TO. The status of hard registers live
1845 at the start of a basic block is updated by replacing a use of FROM with
1849 mark_elimination (int from
, int to
)
1855 /* We don't use LIVE info in IRA. */
1856 regset r
= DF_LR_IN (bb
);
1858 if (REGNO_REG_SET_P (r
, from
))
1860 CLEAR_REGNO_REG_SET (r
, from
);
1861 SET_REGNO_REG_SET (r
, to
);
1870 /* Set when a REG_EQUIV note is found or created. Use to
1871 keep track of what memory accesses might be created later,
1875 /* The list of each instruction which initializes this register. */
1877 /* Loop depth is used to recognize equivalences which appear
1878 to be present within the same loop (or in an inner loop). */
1880 /* Nonzero if this had a preexisting REG_EQUIV note. */
1881 int is_arg_equivalence
;
1882 /* Set when an attempt should be made to replace a register
1883 with the associated src_p entry. */
1887 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
1888 structure for that register. */
1889 static struct equivalence
*reg_equiv
;
1891 /* Used for communication between the following two functions: contains
1892 a MEM that we wish to ensure remains unchanged. */
1893 static rtx equiv_mem
;
1895 /* Set nonzero if EQUIV_MEM is modified. */
1896 static int equiv_mem_modified
;
1898 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
1899 Called via note_stores. */
1901 validate_equiv_mem_from_store (rtx dest
, const_rtx set ATTRIBUTE_UNUSED
,
1902 void *data ATTRIBUTE_UNUSED
)
1905 && reg_overlap_mentioned_p (dest
, equiv_mem
))
1907 && true_dependence (dest
, VOIDmode
, equiv_mem
, rtx_varies_p
)))
1908 equiv_mem_modified
= 1;
1911 /* Verify that no store between START and the death of REG invalidates
1912 MEMREF. MEMREF is invalidated by modifying a register used in MEMREF,
1913 by storing into an overlapping memory location, or with a non-const
1916 Return 1 if MEMREF remains valid. */
1918 validate_equiv_mem (rtx start
, rtx reg
, rtx memref
)
1924 equiv_mem_modified
= 0;
1926 /* If the memory reference has side effects or is volatile, it isn't a
1927 valid equivalence. */
1928 if (side_effects_p (memref
))
1931 for (insn
= start
; insn
&& ! equiv_mem_modified
; insn
= NEXT_INSN (insn
))
1933 if (! INSN_P (insn
))
1936 if (find_reg_note (insn
, REG_DEAD
, reg
))
1939 if (CALL_P (insn
) && ! MEM_READONLY_P (memref
)
1940 && ! RTL_CONST_OR_PURE_CALL_P (insn
))
1943 note_stores (PATTERN (insn
), validate_equiv_mem_from_store
, NULL
);
1945 /* If a register mentioned in MEMREF is modified via an
1946 auto-increment, we lose the equivalence. Do the same if one
1947 dies; although we could extend the life, it doesn't seem worth
1950 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1951 if ((REG_NOTE_KIND (note
) == REG_INC
1952 || REG_NOTE_KIND (note
) == REG_DEAD
)
1953 && REG_P (XEXP (note
, 0))
1954 && reg_overlap_mentioned_p (XEXP (note
, 0), memref
))
1961 /* Returns zero if X is known to be invariant. */
1963 equiv_init_varies_p (rtx x
)
1965 RTX_CODE code
= GET_CODE (x
);
1972 return !MEM_READONLY_P (x
) || equiv_init_varies_p (XEXP (x
, 0));
1984 return reg_equiv
[REGNO (x
)].replace
== 0 && rtx_varies_p (x
, 0);
1987 if (MEM_VOLATILE_P (x
))
1996 fmt
= GET_RTX_FORMAT (code
);
1997 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2000 if (equiv_init_varies_p (XEXP (x
, i
)))
2003 else if (fmt
[i
] == 'E')
2006 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
2007 if (equiv_init_varies_p (XVECEXP (x
, i
, j
)))
2014 /* Returns nonzero if X (used to initialize register REGNO) is movable.
2015 X is only movable if the registers it uses have equivalent initializations
2016 which appear to be within the same loop (or in an inner loop) and movable
2017 or if they are not candidates for local_alloc and don't vary. */
2019 equiv_init_movable_p (rtx x
, int regno
)
2023 enum rtx_code code
= GET_CODE (x
);
2028 return equiv_init_movable_p (SET_SRC (x
), regno
);
2043 return (reg_equiv
[REGNO (x
)].loop_depth
>= reg_equiv
[regno
].loop_depth
2044 && reg_equiv
[REGNO (x
)].replace
)
2045 || (REG_BASIC_BLOCK (REGNO (x
)) < NUM_FIXED_BLOCKS
&& ! rtx_varies_p (x
, 0));
2047 case UNSPEC_VOLATILE
:
2051 if (MEM_VOLATILE_P (x
))
2060 fmt
= GET_RTX_FORMAT (code
);
2061 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2065 if (! equiv_init_movable_p (XEXP (x
, i
), regno
))
2069 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2070 if (! equiv_init_movable_p (XVECEXP (x
, i
, j
), regno
))
2078 /* TRUE if X uses any registers for which reg_equiv[REGNO].replace is true. */
2080 contains_replace_regs (rtx x
)
2084 enum rtx_code code
= GET_CODE (x
);
2101 return reg_equiv
[REGNO (x
)].replace
;
2107 fmt
= GET_RTX_FORMAT (code
);
2108 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2112 if (contains_replace_regs (XEXP (x
, i
)))
2116 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2117 if (contains_replace_regs (XVECEXP (x
, i
, j
)))
2125 /* TRUE if X references a memory location that would be affected by a store
2128 memref_referenced_p (rtx memref
, rtx x
)
2132 enum rtx_code code
= GET_CODE (x
);
2150 return (reg_equiv
[REGNO (x
)].replacement
2151 && memref_referenced_p (memref
,
2152 reg_equiv
[REGNO (x
)].replacement
));
2155 if (true_dependence (memref
, VOIDmode
, x
, rtx_varies_p
))
2160 /* If we are setting a MEM, it doesn't count (its address does), but any
2161 other SET_DEST that has a MEM in it is referencing the MEM. */
2162 if (MEM_P (SET_DEST (x
)))
2164 if (memref_referenced_p (memref
, XEXP (SET_DEST (x
), 0)))
2167 else if (memref_referenced_p (memref
, SET_DEST (x
)))
2170 return memref_referenced_p (memref
, SET_SRC (x
));
2176 fmt
= GET_RTX_FORMAT (code
);
2177 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
2181 if (memref_referenced_p (memref
, XEXP (x
, i
)))
2185 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
2186 if (memref_referenced_p (memref
, XVECEXP (x
, i
, j
)))
2194 /* TRUE if some insn in the range (START, END] references a memory location
2195 that would be affected by a store to MEMREF. */
2197 memref_used_between_p (rtx memref
, rtx start
, rtx end
)
2201 for (insn
= NEXT_INSN (start
); insn
!= NEXT_INSN (end
);
2202 insn
= NEXT_INSN (insn
))
2207 if (memref_referenced_p (memref
, PATTERN (insn
)))
2210 /* Nonconst functions may access memory. */
2211 if (CALL_P (insn
) && (! RTL_CONST_CALL_P (insn
)))
2218 /* Mark REG as having no known equivalence.
2219 Some instructions might have been processed before and furnished
2220 with REG_EQUIV notes for this register; these notes will have to be
2222 STORE is the piece of RTL that does the non-constant / conflicting
2223 assignment - a SET, CLOBBER or REG_INC note. It is currently not used,
2224 but needs to be there because this function is called from note_stores. */
2226 no_equiv (rtx reg
, const_rtx store ATTRIBUTE_UNUSED
, void *data ATTRIBUTE_UNUSED
)
2233 regno
= REGNO (reg
);
2234 list
= reg_equiv
[regno
].init_insns
;
2235 if (list
== const0_rtx
)
2237 reg_equiv
[regno
].init_insns
= const0_rtx
;
2238 reg_equiv
[regno
].replacement
= NULL_RTX
;
2239 /* This doesn't matter for equivalences made for argument registers, we
2240 should keep their initialization insns. */
2241 if (reg_equiv
[regno
].is_arg_equivalence
)
2243 reg_equiv_init
[regno
] = NULL_RTX
;
2244 for (; list
; list
= XEXP (list
, 1))
2246 rtx insn
= XEXP (list
, 0);
2247 remove_note (insn
, find_reg_note (insn
, REG_EQUIV
, NULL_RTX
));
2251 /* Nonzero if we recorded an equivalence for a LABEL_REF. */
2252 static int recorded_label_ref
;
2254 /* Find registers that are equivalent to a single value throughout the
2255 compilation (either because they can be referenced in memory or are set once
2256 from a single constant). Lower their priority for a register.
2258 If such a register is only referenced once, try substituting its value
2259 into the using insn. If it succeeds, we can eliminate the register
2262 Initialize the REG_EQUIV_INIT array of initializing insns.
2264 Return non-zero if jump label rebuilding should be done. */
2266 update_equiv_regs (void)
2271 bitmap cleared_regs
;
2273 /* We need to keep track of whether or not we recorded a LABEL_REF so
2274 that we know if the jump optimizer needs to be rerun. */
2275 recorded_label_ref
= 0;
2277 reg_equiv
= XCNEWVEC (struct equivalence
, max_regno
);
2278 reg_equiv_init
= GGC_CNEWVEC (rtx
, max_regno
);
2279 reg_equiv_init_size
= max_regno
;
2281 init_alias_analysis ();
2283 /* Scan the insns and find which registers have equivalences. Do this
2284 in a separate scan of the insns because (due to -fcse-follow-jumps)
2285 a register can be set below its use. */
2288 loop_depth
= bb
->loop_depth
;
2290 for (insn
= BB_HEAD (bb
);
2291 insn
!= NEXT_INSN (BB_END (bb
));
2292 insn
= NEXT_INSN (insn
))
2299 if (! INSN_P (insn
))
2302 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
2303 if (REG_NOTE_KIND (note
) == REG_INC
)
2304 no_equiv (XEXP (note
, 0), note
, NULL
);
2306 set
= single_set (insn
);
2308 /* If this insn contains more (or less) than a single SET,
2309 only mark all destinations as having no known equivalence. */
2312 note_stores (PATTERN (insn
), no_equiv
, NULL
);
2315 else if (GET_CODE (PATTERN (insn
)) == PARALLEL
)
2319 for (i
= XVECLEN (PATTERN (insn
), 0) - 1; i
>= 0; i
--)
2321 rtx part
= XVECEXP (PATTERN (insn
), 0, i
);
2323 note_stores (part
, no_equiv
, NULL
);
2327 dest
= SET_DEST (set
);
2328 src
= SET_SRC (set
);
2330 /* See if this is setting up the equivalence between an argument
2331 register and its stack slot. */
2332 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
2335 gcc_assert (REG_P (dest
));
2336 regno
= REGNO (dest
);
2338 /* Note that we don't want to clear reg_equiv_init even if there
2339 are multiple sets of this register. */
2340 reg_equiv
[regno
].is_arg_equivalence
= 1;
2342 /* Record for reload that this is an equivalencing insn. */
2343 if (rtx_equal_p (src
, XEXP (note
, 0)))
2344 reg_equiv_init
[regno
]
2345 = gen_rtx_INSN_LIST (VOIDmode
, insn
, reg_equiv_init
[regno
]);
2347 /* Continue normally in case this is a candidate for
2354 /* We only handle the case of a pseudo register being set
2355 once, or always to the same value. */
2356 /* ??? The mn10200 port breaks if we add equivalences for
2357 values that need an ADDRESS_REGS register and set them equivalent
2358 to a MEM of a pseudo. The actual problem is in the over-conservative
2359 handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
2360 calculate_needs, but we traditionally work around this problem
2361 here by rejecting equivalences when the destination is in a register
2362 that's likely spilled. This is fragile, of course, since the
2363 preferred class of a pseudo depends on all instructions that set
2367 || (regno
= REGNO (dest
)) < FIRST_PSEUDO_REGISTER
2368 || reg_equiv
[regno
].init_insns
== const0_rtx
2369 || (CLASS_LIKELY_SPILLED_P (reg_preferred_class (regno
))
2370 && MEM_P (src
) && ! reg_equiv
[regno
].is_arg_equivalence
))
2372 /* This might be setting a SUBREG of a pseudo, a pseudo that is
2373 also set somewhere else to a constant. */
2374 note_stores (set
, no_equiv
, NULL
);
2378 note
= find_reg_note (insn
, REG_EQUAL
, NULL_RTX
);
2380 /* cse sometimes generates function invariants, but doesn't put a
2381 REG_EQUAL note on the insn. Since this note would be redundant,
2382 there's no point creating it earlier than here. */
2383 if (! note
&& ! rtx_varies_p (src
, 0))
2384 note
= set_unique_reg_note (insn
, REG_EQUAL
, copy_rtx (src
));
2386 /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
2387 since it represents a function call */
2388 if (note
&& GET_CODE (XEXP (note
, 0)) == EXPR_LIST
)
2391 if (DF_REG_DEF_COUNT (regno
) != 1
2393 || rtx_varies_p (XEXP (note
, 0), 0)
2394 || (reg_equiv
[regno
].replacement
2395 && ! rtx_equal_p (XEXP (note
, 0),
2396 reg_equiv
[regno
].replacement
))))
2398 no_equiv (dest
, set
, NULL
);
2401 /* Record this insn as initializing this register. */
2402 reg_equiv
[regno
].init_insns
2403 = gen_rtx_INSN_LIST (VOIDmode
, insn
, reg_equiv
[regno
].init_insns
);
2405 /* If this register is known to be equal to a constant, record that
2406 it is always equivalent to the constant. */
2407 if (DF_REG_DEF_COUNT (regno
) == 1
2408 && note
&& ! rtx_varies_p (XEXP (note
, 0), 0))
2410 rtx note_value
= XEXP (note
, 0);
2411 remove_note (insn
, note
);
2412 set_unique_reg_note (insn
, REG_EQUIV
, note_value
);
2415 /* If this insn introduces a "constant" register, decrease the priority
2416 of that register. Record this insn if the register is only used once
2417 more and the equivalence value is the same as our source.
2419 The latter condition is checked for two reasons: First, it is an
2420 indication that it may be more efficient to actually emit the insn
2421 as written (if no registers are available, reload will substitute
2422 the equivalence). Secondly, it avoids problems with any registers
2423 dying in this insn whose death notes would be missed.
2425 If we don't have a REG_EQUIV note, see if this insn is loading
2426 a register used only in one basic block from a MEM. If so, and the
2427 MEM remains unchanged for the life of the register, add a REG_EQUIV
2430 note
= find_reg_note (insn
, REG_EQUIV
, NULL_RTX
);
2432 if (note
== 0 && REG_BASIC_BLOCK (regno
) >= NUM_FIXED_BLOCKS
2433 && MEM_P (SET_SRC (set
))
2434 && validate_equiv_mem (insn
, dest
, SET_SRC (set
)))
2435 note
= set_unique_reg_note (insn
, REG_EQUIV
, copy_rtx (SET_SRC (set
)));
2439 int regno
= REGNO (dest
);
2440 rtx x
= XEXP (note
, 0);
2442 /* If we haven't done so, record for reload that this is an
2443 equivalencing insn. */
2444 if (!reg_equiv
[regno
].is_arg_equivalence
)
2445 reg_equiv_init
[regno
]
2446 = gen_rtx_INSN_LIST (VOIDmode
, insn
, reg_equiv_init
[regno
]);
2448 /* Record whether or not we created a REG_EQUIV note for a LABEL_REF.
2449 We might end up substituting the LABEL_REF for uses of the
2450 pseudo here or later. That kind of transformation may turn an
2451 indirect jump into a direct jump, in which case we must rerun the
2452 jump optimizer to ensure that the JUMP_LABEL fields are valid. */
2453 if (GET_CODE (x
) == LABEL_REF
2454 || (GET_CODE (x
) == CONST
2455 && GET_CODE (XEXP (x
, 0)) == PLUS
2456 && (GET_CODE (XEXP (XEXP (x
, 0), 0)) == LABEL_REF
)))
2457 recorded_label_ref
= 1;
2459 reg_equiv
[regno
].replacement
= x
;
2460 reg_equiv
[regno
].src_p
= &SET_SRC (set
);
2461 reg_equiv
[regno
].loop_depth
= loop_depth
;
2463 /* Don't mess with things live during setjmp. */
2464 if (REG_LIVE_LENGTH (regno
) >= 0 && optimize
)
2466 /* Note that the statement below does not affect the priority
2468 REG_LIVE_LENGTH (regno
) *= 2;
2470 /* If the register is referenced exactly twice, meaning it is
2471 set once and used once, indicate that the reference may be
2472 replaced by the equivalence we computed above. Do this
2473 even if the register is only used in one block so that
2474 dependencies can be handled where the last register is
2475 used in a different block (i.e. HIGH / LO_SUM sequences)
2476 and to reduce the number of registers alive across
2479 if (REG_N_REFS (regno
) == 2
2480 && (rtx_equal_p (x
, src
)
2481 || ! equiv_init_varies_p (src
))
2482 && NONJUMP_INSN_P (insn
)
2483 && equiv_init_movable_p (PATTERN (insn
), regno
))
2484 reg_equiv
[regno
].replace
= 1;
2493 /* A second pass, to gather additional equivalences with memory. This needs
2494 to be done after we know which registers we are going to replace. */
2496 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
2501 if (! INSN_P (insn
))
2504 set
= single_set (insn
);
2508 dest
= SET_DEST (set
);
2509 src
= SET_SRC (set
);
2511 /* If this sets a MEM to the contents of a REG that is only used
2512 in a single basic block, see if the register is always equivalent
2513 to that memory location and if moving the store from INSN to the
2514 insn that set REG is safe. If so, put a REG_EQUIV note on the
2517 Don't add a REG_EQUIV note if the insn already has one. The existing
2518 REG_EQUIV is likely more useful than the one we are adding.
2520 If one of the regs in the address has reg_equiv[REGNO].replace set,
2521 then we can't add this REG_EQUIV note. The reg_equiv[REGNO].replace
2522 optimization may move the set of this register immediately before
2523 insn, which puts it after reg_equiv[REGNO].init_insns, and hence
2524 the mention in the REG_EQUIV note would be to an uninitialized
2527 if (MEM_P (dest
) && REG_P (src
)
2528 && (regno
= REGNO (src
)) >= FIRST_PSEUDO_REGISTER
2529 && REG_BASIC_BLOCK (regno
) >= NUM_FIXED_BLOCKS
2530 && DF_REG_DEF_COUNT (regno
) == 1
2531 && reg_equiv
[regno
].init_insns
!= 0
2532 && reg_equiv
[regno
].init_insns
!= const0_rtx
2533 && ! find_reg_note (XEXP (reg_equiv
[regno
].init_insns
, 0),
2534 REG_EQUIV
, NULL_RTX
)
2535 && ! contains_replace_regs (XEXP (dest
, 0)))
2537 rtx init_insn
= XEXP (reg_equiv
[regno
].init_insns
, 0);
2538 if (validate_equiv_mem (init_insn
, src
, dest
)
2539 && ! memref_used_between_p (dest
, init_insn
, insn
)
2540 /* Attaching a REG_EQUIV note will fail if INIT_INSN has
2542 && set_unique_reg_note (init_insn
, REG_EQUIV
, copy_rtx (dest
)))
2544 /* This insn makes the equivalence, not the one initializing
2546 reg_equiv_init
[regno
]
2547 = gen_rtx_INSN_LIST (VOIDmode
, insn
, NULL_RTX
);
2548 df_notes_rescan (init_insn
);
2553 cleared_regs
= BITMAP_ALLOC (NULL
);
2554 /* Now scan all regs killed in an insn to see if any of them are
2555 registers only used that once. If so, see if we can replace the
2556 reference with the equivalent form. If we can, delete the
2557 initializing reference and this register will go away. If we
2558 can't replace the reference, and the initializing reference is
2559 within the same loop (or in an inner loop), then move the register
2560 initialization just before the use, so that they are in the same
2562 FOR_EACH_BB_REVERSE (bb
)
2564 loop_depth
= bb
->loop_depth
;
2565 for (insn
= BB_END (bb
);
2566 insn
!= PREV_INSN (BB_HEAD (bb
));
2567 insn
= PREV_INSN (insn
))
2571 if (! INSN_P (insn
))
2574 /* Don't substitute into a non-local goto, this confuses CFG. */
2576 && find_reg_note (insn
, REG_NON_LOCAL_GOTO
, NULL_RTX
))
2579 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2581 if (REG_NOTE_KIND (link
) == REG_DEAD
2582 /* Make sure this insn still refers to the register. */
2583 && reg_mentioned_p (XEXP (link
, 0), PATTERN (insn
)))
2585 int regno
= REGNO (XEXP (link
, 0));
2588 if (! reg_equiv
[regno
].replace
2589 || reg_equiv
[regno
].loop_depth
< loop_depth
)
2592 /* reg_equiv[REGNO].replace gets set only when
2593 REG_N_REFS[REGNO] is 2, i.e. the register is set
2594 once and used once. (If it were only set, but not used,
2595 flow would have deleted the setting insns.) Hence
2596 there can only be one insn in reg_equiv[REGNO].init_insns. */
2597 gcc_assert (reg_equiv
[regno
].init_insns
2598 && !XEXP (reg_equiv
[regno
].init_insns
, 1));
2599 equiv_insn
= XEXP (reg_equiv
[regno
].init_insns
, 0);
2601 /* We may not move instructions that can throw, since
2602 that changes basic block boundaries and we are not
2603 prepared to adjust the CFG to match. */
2604 if (can_throw_internal (equiv_insn
))
2607 if (asm_noperands (PATTERN (equiv_insn
)) < 0
2608 && validate_replace_rtx (regno_reg_rtx
[regno
],
2609 *(reg_equiv
[regno
].src_p
), insn
))
2615 /* Find the last note. */
2616 for (last_link
= link
; XEXP (last_link
, 1);
2617 last_link
= XEXP (last_link
, 1))
2620 /* Append the REG_DEAD notes from equiv_insn. */
2621 equiv_link
= REG_NOTES (equiv_insn
);
2625 equiv_link
= XEXP (equiv_link
, 1);
2626 if (REG_NOTE_KIND (note
) == REG_DEAD
)
2628 remove_note (equiv_insn
, note
);
2629 XEXP (last_link
, 1) = note
;
2630 XEXP (note
, 1) = NULL_RTX
;
2635 remove_death (regno
, insn
);
2636 SET_REG_N_REFS (regno
, 0);
2637 REG_FREQ (regno
) = 0;
2638 delete_insn (equiv_insn
);
2640 reg_equiv
[regno
].init_insns
2641 = XEXP (reg_equiv
[regno
].init_insns
, 1);
2643 reg_equiv_init
[regno
] = NULL_RTX
;
2644 bitmap_set_bit (cleared_regs
, regno
);
2646 /* Move the initialization of the register to just before
2647 INSN. Update the flow information. */
2648 else if (PREV_INSN (insn
) != equiv_insn
)
2652 new_insn
= emit_insn_before (PATTERN (equiv_insn
), insn
);
2653 REG_NOTES (new_insn
) = REG_NOTES (equiv_insn
);
2654 REG_NOTES (equiv_insn
) = 0;
2655 /* Rescan it to process the notes. */
2656 df_insn_rescan (new_insn
);
2658 /* Make sure this insn is recognized before
2659 reload begins, otherwise
2660 eliminate_regs_in_insn will die. */
2661 INSN_CODE (new_insn
) = INSN_CODE (equiv_insn
);
2663 delete_insn (equiv_insn
);
2665 XEXP (reg_equiv
[regno
].init_insns
, 0) = new_insn
;
2667 REG_BASIC_BLOCK (regno
) = bb
->index
;
2668 REG_N_CALLS_CROSSED (regno
) = 0;
2669 REG_FREQ_CALLS_CROSSED (regno
) = 0;
2670 REG_N_THROWING_CALLS_CROSSED (regno
) = 0;
2671 REG_LIVE_LENGTH (regno
) = 2;
2673 if (insn
== BB_HEAD (bb
))
2674 BB_HEAD (bb
) = PREV_INSN (insn
);
2676 reg_equiv_init
[regno
]
2677 = gen_rtx_INSN_LIST (VOIDmode
, new_insn
, NULL_RTX
);
2678 bitmap_set_bit (cleared_regs
, regno
);
2685 if (!bitmap_empty_p (cleared_regs
))
2688 bitmap_and_compl_into (DF_LIVE_IN (bb
), cleared_regs
);
2689 bitmap_and_compl_into (DF_LIVE_OUT (bb
), cleared_regs
);
2690 bitmap_and_compl_into (DF_LR_IN (bb
), cleared_regs
);
2691 bitmap_and_compl_into (DF_LR_OUT (bb
), cleared_regs
);
2694 BITMAP_FREE (cleared_regs
);
2699 end_alias_analysis ();
2701 return recorded_label_ref
;
2706 /* Print chain C to FILE. */
2708 print_insn_chain (FILE *file
, struct insn_chain
*c
)
2710 fprintf (file
, "insn=%d, ", INSN_UID(c
->insn
));
2711 bitmap_print (file
, &c
->live_throughout
, "live_throughout: ", ", ");
2712 bitmap_print (file
, &c
->dead_or_set
, "dead_or_set: ", "\n");
2716 /* Print all reload_insn_chains to FILE. */
2718 print_insn_chains (FILE *file
)
2720 struct insn_chain
*c
;
2721 for (c
= reload_insn_chain
; c
; c
= c
->next
)
2722 print_insn_chain (file
, c
);
2725 /* Return true if pseudo REGNO should be added to set live_throughout
2726 or dead_or_set of the insn chains for reload consideration. */
2728 pseudo_for_reload_consideration_p (int regno
)
2730 /* Consider spilled pseudos too for IRA because they still have a
2731 chance to get hard-registers in the reload when IRA is used. */
2732 return (reg_renumber
[regno
] >= 0
2733 || (ira_conflicts_p
&& flag_ira_share_spill_slots
));
2736 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
2737 REG to the number of nregs, and INIT_VALUE to get the
2738 initialization. ALLOCNUM need not be the regno of REG. */
2740 init_live_subregs (bool init_value
, sbitmap
*live_subregs
,
2741 int *live_subregs_used
, int allocnum
, rtx reg
)
2743 unsigned int regno
= REGNO (SUBREG_REG (reg
));
2744 int size
= GET_MODE_SIZE (GET_MODE (regno_reg_rtx
[regno
]));
2746 gcc_assert (size
> 0);
2748 /* Been there, done that. */
2749 if (live_subregs_used
[allocnum
])
2752 /* Create a new one with zeros. */
2753 if (live_subregs
[allocnum
] == NULL
)
2754 live_subregs
[allocnum
] = sbitmap_alloc (size
);
2756 /* If the entire reg was live before blasting into subregs, we need
2757 to init all of the subregs to ones else init to 0. */
2759 sbitmap_ones (live_subregs
[allocnum
]);
2761 sbitmap_zero (live_subregs
[allocnum
]);
2763 /* Set the number of bits that we really want. */
2764 live_subregs_used
[allocnum
] = size
;
2767 /* Walk the insns of the current function and build reload_insn_chain,
2768 and record register life information. */
2770 build_insn_chain (void)
2773 struct insn_chain
**p
= &reload_insn_chain
;
2775 struct insn_chain
*c
= NULL
;
2776 struct insn_chain
*next
= NULL
;
2777 bitmap live_relevant_regs
= BITMAP_ALLOC (NULL
);
2778 bitmap elim_regset
= BITMAP_ALLOC (NULL
);
2779 /* live_subregs is a vector used to keep accurate information about
2780 which hardregs are live in multiword pseudos. live_subregs and
2781 live_subregs_used are indexed by pseudo number. The live_subreg
2782 entry for a particular pseudo is only used if the corresponding
2783 element is non zero in live_subregs_used. The value in
2784 live_subregs_used is number of bytes that the pseudo can
2786 sbitmap
*live_subregs
= XCNEWVEC (sbitmap
, max_regno
);
2787 int *live_subregs_used
= XNEWVEC (int, max_regno
);
2789 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2790 if (TEST_HARD_REG_BIT (eliminable_regset
, i
))
2791 bitmap_set_bit (elim_regset
, i
);
2792 FOR_EACH_BB_REVERSE (bb
)
2797 CLEAR_REG_SET (live_relevant_regs
);
2798 memset (live_subregs_used
, 0, max_regno
* sizeof (int));
2800 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb
), 0, i
, bi
)
2802 if (i
>= FIRST_PSEUDO_REGISTER
)
2804 bitmap_set_bit (live_relevant_regs
, i
);
2807 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb
),
2808 FIRST_PSEUDO_REGISTER
, i
, bi
)
2810 if (pseudo_for_reload_consideration_p (i
))
2811 bitmap_set_bit (live_relevant_regs
, i
);
2814 FOR_BB_INSNS_REVERSE (bb
, insn
)
2816 if (!NOTE_P (insn
) && !BARRIER_P (insn
))
2818 unsigned int uid
= INSN_UID (insn
);
2822 c
= new_insn_chain ();
2829 c
->block
= bb
->index
;
2832 for (def_rec
= DF_INSN_UID_DEFS (uid
); *def_rec
; def_rec
++)
2834 df_ref def
= *def_rec
;
2835 unsigned int regno
= DF_REF_REGNO (def
);
2837 /* Ignore may clobbers because these are generated
2838 from calls. However, every other kind of def is
2839 added to dead_or_set. */
2840 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_MAY_CLOBBER
))
2842 if (regno
< FIRST_PSEUDO_REGISTER
)
2844 if (!fixed_regs
[regno
])
2845 bitmap_set_bit (&c
->dead_or_set
, regno
);
2847 else if (pseudo_for_reload_consideration_p (regno
))
2848 bitmap_set_bit (&c
->dead_or_set
, regno
);
2851 if ((regno
< FIRST_PSEUDO_REGISTER
2852 || reg_renumber
[regno
] >= 0
2854 && (!DF_REF_FLAGS_IS_SET (def
, DF_REF_CONDITIONAL
)))
2856 rtx reg
= DF_REF_REG (def
);
2858 /* We can model subregs, but not if they are
2859 wrapped in ZERO_EXTRACTS. */
2860 if (GET_CODE (reg
) == SUBREG
2861 && !DF_REF_FLAGS_IS_SET (def
, DF_REF_ZERO_EXTRACT
))
2863 unsigned int start
= SUBREG_BYTE (reg
);
2864 unsigned int last
= start
2865 + GET_MODE_SIZE (GET_MODE (reg
));
2868 (bitmap_bit_p (live_relevant_regs
, regno
),
2869 live_subregs
, live_subregs_used
, regno
, reg
);
2871 if (!DF_REF_FLAGS_IS_SET
2872 (def
, DF_REF_STRICT_LOW_PART
))
2874 /* Expand the range to cover entire words.
2875 Bytes added here are "don't care". */
2877 = start
/ UNITS_PER_WORD
* UNITS_PER_WORD
;
2878 last
= ((last
+ UNITS_PER_WORD
- 1)
2879 / UNITS_PER_WORD
* UNITS_PER_WORD
);
2882 /* Ignore the paradoxical bits. */
2883 if ((int)last
> live_subregs_used
[regno
])
2884 last
= live_subregs_used
[regno
];
2886 while (start
< last
)
2888 RESET_BIT (live_subregs
[regno
], start
);
2892 if (sbitmap_empty_p (live_subregs
[regno
]))
2894 live_subregs_used
[regno
] = 0;
2895 bitmap_clear_bit (live_relevant_regs
, regno
);
2898 /* Set live_relevant_regs here because
2899 that bit has to be true to get us to
2900 look at the live_subregs fields. */
2901 bitmap_set_bit (live_relevant_regs
, regno
);
2905 /* DF_REF_PARTIAL is generated for
2906 subregs, STRICT_LOW_PART, and
2907 ZERO_EXTRACT. We handle the subreg
2908 case above so here we have to keep from
2909 modeling the def as a killing def. */
2910 if (!DF_REF_FLAGS_IS_SET (def
, DF_REF_PARTIAL
))
2912 bitmap_clear_bit (live_relevant_regs
, regno
);
2913 live_subregs_used
[regno
] = 0;
2919 bitmap_and_compl_into (live_relevant_regs
, elim_regset
);
2920 bitmap_copy (&c
->live_throughout
, live_relevant_regs
);
2923 for (use_rec
= DF_INSN_UID_USES (uid
); *use_rec
; use_rec
++)
2925 df_ref use
= *use_rec
;
2926 unsigned int regno
= DF_REF_REGNO (use
);
2927 rtx reg
= DF_REF_REG (use
);
2929 /* DF_REF_READ_WRITE on a use means that this use
2930 is fabricated from a def that is a partial set
2931 to a multiword reg. Here, we only model the
2932 subreg case that is not wrapped in ZERO_EXTRACT
2933 precisely so we do not need to look at the
2935 if (DF_REF_FLAGS_IS_SET (use
, DF_REF_READ_WRITE
)
2936 && !DF_REF_FLAGS_IS_SET (use
, DF_REF_ZERO_EXTRACT
)
2937 && DF_REF_FLAGS_IS_SET (use
, DF_REF_SUBREG
))
2940 /* Add the last use of each var to dead_or_set. */
2941 if (!bitmap_bit_p (live_relevant_regs
, regno
))
2943 if (regno
< FIRST_PSEUDO_REGISTER
)
2945 if (!fixed_regs
[regno
])
2946 bitmap_set_bit (&c
->dead_or_set
, regno
);
2948 else if (pseudo_for_reload_consideration_p (regno
))
2949 bitmap_set_bit (&c
->dead_or_set
, regno
);
2952 if (regno
< FIRST_PSEUDO_REGISTER
2953 || pseudo_for_reload_consideration_p (regno
))
2955 if (GET_CODE (reg
) == SUBREG
2956 && !DF_REF_FLAGS_IS_SET (use
,
2958 | DF_REF_ZERO_EXTRACT
))
2960 unsigned int start
= SUBREG_BYTE (reg
);
2961 unsigned int last
= start
2962 + GET_MODE_SIZE (GET_MODE (reg
));
2965 (bitmap_bit_p (live_relevant_regs
, regno
),
2966 live_subregs
, live_subregs_used
, regno
, reg
);
2968 /* Ignore the paradoxical bits. */
2969 if ((int)last
> live_subregs_used
[regno
])
2970 last
= live_subregs_used
[regno
];
2972 while (start
< last
)
2974 SET_BIT (live_subregs
[regno
], start
);
2979 /* Resetting the live_subregs_used is
2980 effectively saying do not use the subregs
2981 because we are reading the whole
2983 live_subregs_used
[regno
] = 0;
2984 bitmap_set_bit (live_relevant_regs
, regno
);
2990 /* FIXME!! The following code is a disaster. Reload needs to see the
2991 labels and jump tables that are just hanging out in between
2992 the basic blocks. See pr33676. */
2993 insn
= BB_HEAD (bb
);
2995 /* Skip over the barriers and cruft. */
2996 while (insn
&& (BARRIER_P (insn
) || NOTE_P (insn
)
2997 || BLOCK_FOR_INSN (insn
) == bb
))
2998 insn
= PREV_INSN (insn
);
3000 /* While we add anything except barriers and notes, the focus is
3001 to get the labels and jump tables into the
3002 reload_insn_chain. */
3005 if (!NOTE_P (insn
) && !BARRIER_P (insn
))
3007 if (BLOCK_FOR_INSN (insn
))
3010 c
= new_insn_chain ();
3016 /* The block makes no sense here, but it is what the old
3018 c
->block
= bb
->index
;
3020 bitmap_copy (&c
->live_throughout
, live_relevant_regs
);
3022 insn
= PREV_INSN (insn
);
3026 for (i
= 0; i
< (unsigned int) max_regno
; i
++)
3027 if (live_subregs
[i
])
3028 free (live_subregs
[i
]);
3030 reload_insn_chain
= c
;
3033 free (live_subregs
);
3034 free (live_subregs_used
);
3035 BITMAP_FREE (live_relevant_regs
);
3036 BITMAP_FREE (elim_regset
);
3039 print_insn_chains (dump_file
);
3044 /* All natural loops. */
3045 struct loops ira_loops
;
3047 /* True if we have allocno conflicts. It is false for non-optimized
3048 mode or when the conflict table is too big. */
3049 bool ira_conflicts_p
;
3051 /* This is the main entry of IRA. */
3055 int overall_cost_before
, allocated_reg_info_size
;
3057 int max_regno_before_ira
, ira_max_point_before_emit
;
3059 int saved_flag_ira_share_spill_slots
;
3062 timevar_push (TV_IRA
);
3064 if (flag_ira_verbose
< 10)
3066 internal_flag_ira_verbose
= flag_ira_verbose
;
3071 internal_flag_ira_verbose
= flag_ira_verbose
- 10;
3072 ira_dump_file
= stderr
;
3075 ira_conflicts_p
= optimize
> 0;
3076 setup_prohibited_mode_move_regs ();
3078 df_note_add_problem ();
3082 df_live_add_problem ();
3083 df_live_set_all_dirty ();
3085 #ifdef ENABLE_CHECKING
3086 df
->changeable_flags
|= DF_VERIFY_SCHEDULED
;
3089 df_clear_flags (DF_NO_INSN_RESCAN
);
3090 regstat_init_n_sets_and_refs ();
3091 regstat_compute_ri ();
3093 /* If we are not optimizing, then this is the only place before
3094 register allocation where dataflow is done. And that is needed
3095 to generate these warnings. */
3097 generate_setjmp_warnings ();
3099 /* Determine if the current function is a leaf before running IRA
3100 since this can impact optimizations done by the prologue and
3101 epilogue thus changing register elimination offsets. */
3102 current_function_is_leaf
= leaf_function_p ();
3104 rebuild_p
= update_equiv_regs ();
3106 #ifndef IRA_NO_OBSTACK
3107 gcc_obstack_init (&ira_obstack
);
3109 bitmap_obstack_initialize (&ira_bitmap_obstack
);
3112 max_regno
= max_reg_num ();
3113 ira_reg_equiv_len
= max_regno
;
3114 ira_reg_equiv_invariant_p
3115 = (bool *) ira_allocate (max_regno
* sizeof (bool));
3116 memset (ira_reg_equiv_invariant_p
, 0, max_regno
* sizeof (bool));
3117 ira_reg_equiv_const
= (rtx
*) ira_allocate (max_regno
* sizeof (rtx
));
3118 memset (ira_reg_equiv_const
, 0, max_regno
* sizeof (rtx
));
3119 find_reg_equiv_invariant_const ();
3122 timevar_push (TV_JUMP
);
3123 rebuild_jump_labels (get_insns ());
3124 purge_all_dead_edges ();
3125 timevar_pop (TV_JUMP
);
3129 max_regno_before_ira
= allocated_reg_info_size
= max_reg_num ();
3130 allocate_reg_info ();
3131 setup_eliminable_regset ();
3133 ira_overall_cost
= ira_reg_cost
= ira_mem_cost
= 0;
3134 ira_load_cost
= ira_store_cost
= ira_shuffle_cost
= 0;
3135 ira_move_loops_num
= ira_additional_jumps_num
= 0;
3137 ira_assert (current_loops
== NULL
);
3138 flow_loops_find (&ira_loops
);
3139 current_loops
= &ira_loops
;
3141 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
3142 fprintf (ira_dump_file
, "Building IRA IR\n");
3143 loops_p
= ira_build (optimize
3144 && (flag_ira_region
== IRA_REGION_ALL
3145 || flag_ira_region
== IRA_REGION_MIXED
));
3147 ira_assert (ira_conflicts_p
|| !loops_p
);
3149 saved_flag_ira_share_spill_slots
= flag_ira_share_spill_slots
;
3150 if (too_high_register_pressure_p ())
3151 /* It is just wasting compiler's time to pack spilled pseudos into
3152 stack slots in this case -- prohibit it. */
3153 flag_ira_share_spill_slots
= FALSE
;
3157 ira_max_point_before_emit
= ira_max_point
;
3161 if (ira_conflicts_p
)
3163 max_regno
= max_reg_num ();
3166 ira_initiate_assign ();
3169 expand_reg_info (allocated_reg_info_size
);
3170 setup_preferred_alternate_classes_for_new_pseudos
3171 (allocated_reg_info_size
);
3172 allocated_reg_info_size
= max_regno
;
3174 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
3175 fprintf (ira_dump_file
, "Flattening IR\n");
3176 ira_flattening (max_regno_before_ira
, ira_max_point_before_emit
);
3177 /* New insns were generated: add notes and recalculate live
3181 flow_loops_find (&ira_loops
);
3182 current_loops
= &ira_loops
;
3184 setup_allocno_assignment_flags ();
3185 ira_initiate_assign ();
3186 ira_reassign_conflict_allocnos (max_regno
);
3190 setup_reg_renumber ();
3192 calculate_allocation_cost ();
3194 #ifdef ENABLE_IRA_CHECKING
3195 if (ira_conflicts_p
)
3196 check_allocation ();
3199 delete_trivially_dead_insns (get_insns (), max_reg_num ());
3200 max_regno
= max_reg_num ();
3202 /* And the reg_equiv_memory_loc array. */
3203 VEC_safe_grow (rtx
, gc
, reg_equiv_memory_loc_vec
, max_regno
);
3204 memset (VEC_address (rtx
, reg_equiv_memory_loc_vec
), 0,
3205 sizeof (rtx
) * max_regno
);
3206 reg_equiv_memory_loc
= VEC_address (rtx
, reg_equiv_memory_loc_vec
);
3208 if (max_regno
!= max_regno_before_ira
)
3210 regstat_free_n_sets_and_refs ();
3212 regstat_init_n_sets_and_refs ();
3213 regstat_compute_ri ();
3216 allocate_initial_values (reg_equiv_memory_loc
);
3218 overall_cost_before
= ira_overall_cost
;
3219 if (ira_conflicts_p
)
3221 fix_reg_equiv_init ();
3223 #ifdef ENABLE_IRA_CHECKING
3224 print_redundant_copies ();
3227 ira_spilled_reg_stack_slots_num
= 0;
3228 ira_spilled_reg_stack_slots
3229 = ((struct ira_spilled_reg_stack_slot
*)
3230 ira_allocate (max_regno
3231 * sizeof (struct ira_spilled_reg_stack_slot
)));
3232 memset (ira_spilled_reg_stack_slots
, 0,
3233 max_regno
* sizeof (struct ira_spilled_reg_stack_slot
));
3236 timevar_pop (TV_IRA
);
3238 timevar_push (TV_RELOAD
);
3239 df_set_flags (DF_NO_INSN_RESCAN
);
3240 build_insn_chain ();
3242 reload_completed
= !reload (get_insns (), ira_conflicts_p
);
3244 timevar_pop (TV_RELOAD
);
3246 timevar_push (TV_IRA
);
3248 if (ira_conflicts_p
)
3250 ira_free (ira_spilled_reg_stack_slots
);
3252 ira_finish_assign ();
3255 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
3256 && overall_cost_before
!= ira_overall_cost
)
3257 fprintf (ira_dump_file
, "+++Overall after reload %d\n", ira_overall_cost
);
3260 flag_ira_share_spill_slots
= saved_flag_ira_share_spill_slots
;
3262 flow_loops_free (&ira_loops
);
3263 free_dominance_info (CDI_DOMINATORS
);
3265 bb
->loop_father
= NULL
;
3266 current_loops
= NULL
;
3269 regstat_free_n_sets_and_refs ();
3273 cleanup_cfg (CLEANUP_EXPENSIVE
);
3275 ira_free (ira_reg_equiv_invariant_p
);
3276 ira_free (ira_reg_equiv_const
);
3279 bitmap_obstack_release (&ira_bitmap_obstack
);
3280 #ifndef IRA_NO_OBSTACK
3281 obstack_free (&ira_obstack
, NULL
);
3284 /* The code after the reload has changed so much that at this point
3285 we might as well just rescan everything. Not that
3286 df_rescan_all_insns is not going to help here because it does not
3287 touch the artificial uses and defs. */
3288 df_finish_pass (true);
3290 df_live_add_problem ();
3291 df_scan_alloc (NULL
);
3297 timevar_pop (TV_IRA
);
3308 /* Run the integrated register allocator. */
3310 rest_of_handle_ira (void)
3316 struct rtl_opt_pass pass_ira
=
3321 gate_ira
, /* gate */
3322 rest_of_handle_ira
, /* execute */
3325 0, /* static_pass_number */
3326 TV_NONE
, /* tv_id */
3327 0, /* properties_required */
3328 0, /* properties_provided */
3329 0, /* properties_destroyed */
3330 0, /* todo_flags_start */
3332 TODO_ggc_collect
/* todo_flags_finish */