1 /* Integrated Register Allocator (IRA) entry point.
2 Copyright (C) 2006-2021 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21 /* The integrated register allocator (IRA) is a
22 regional register allocator performing graph coloring on a top-down
23 traversal of nested regions. Graph coloring in a region is based
24 on Chaitin-Briggs algorithm. It is called integrated because
25 register coalescing, register live range splitting, and choosing a
26 better hard register are done on-the-fly during coloring. Register
27 coalescing and choosing a cheaper hard register is done by hard
28 register preferencing during hard register assigning. The live
29 range splitting is a byproduct of the regional register allocation.
30
31 Major IRA notions are:
32
33 o *Region* is a part of CFG where graph coloring based on
34 Chaitin-Briggs algorithm is done. IRA can work on any set of
35 nested CFG regions forming a tree. Currently the regions are
36 the entire function for the root region and natural loops for
37 the other regions. Therefore data structure representing a
38 region is called loop_tree_node.
39
40 o *Allocno class* is a register class used for allocation of
41 given allocno. It means that only hard register of given
42 register class can be assigned to given allocno. In reality,
43 even smaller subset of (*profitable*) hard registers can be
44 assigned. In rare cases, the subset can be even smaller
45 because our modification of Chaitin-Briggs algorithm requires
46 that sets of hard registers can be assigned to allocnos forms a
47 forest, i.e. the sets can be ordered in a way where any
48 previous set is not intersected with given set or is a superset
49 of given set.
50
51 o *Pressure class* is a register class belonging to a set of
52 register classes containing all of the hard-registers available
53 for register allocation. The set of all pressure classes for a
54 target is defined in the corresponding machine-description file
55 according some criteria. Register pressure is calculated only
56 for pressure classes and it affects some IRA decisions as
57 forming allocation regions.
58
59 o *Allocno* represents the live range of a pseudo-register in a
60 region. Besides the obvious attributes like the corresponding
61 pseudo-register number, allocno class, conflicting allocnos and
62 conflicting hard-registers, there are a few allocno attributes
63 which are important for understanding the allocation algorithm:
64
65 - *Live ranges*. This is a list of ranges of *program points*
66 where the allocno lives. Program points represent places
67 where a pseudo can be born or become dead (there are
68 approximately two times more program points than the insns)
69 and they are represented by integers starting with 0. The
70 live ranges are used to find conflicts between allocnos.
71 They also play very important role for the transformation of
72 the IRA internal representation of several regions into a one
73 region representation. The later is used during the reload
74 pass work because each allocno represents all of the
75 corresponding pseudo-registers.
76
77 - *Hard-register costs*. This is a vector of size equal to the
78 number of available hard-registers of the allocno class. The
79 cost of a callee-clobbered hard-register for an allocno is
80 increased by the cost of save/restore code around the calls
81 through the given allocno's life. If the allocno is a move
82 instruction operand and another operand is a hard-register of
83 the allocno class, the cost of the hard-register is decreased
84 by the move cost.
85
86 When an allocno is assigned, the hard-register with minimal
87 full cost is used. Initially, a hard-register's full cost is
88 the corresponding value from the hard-register's cost vector.
89 If the allocno is connected by a *copy* (see below) to
90 another allocno which has just received a hard-register, the
91 cost of the hard-register is decreased. Before choosing a
92 hard-register for an allocno, the allocno's current costs of
93 the hard-registers are modified by the conflict hard-register
94 costs of all of the conflicting allocnos which are not
95 assigned yet.
96
97 - *Conflict hard-register costs*. This is a vector of the same
98 size as the hard-register costs vector. To permit an
99 unassigned allocno to get a better hard-register, IRA uses
100 this vector to calculate the final full cost of the
101 available hard-registers. Conflict hard-register costs of an
102 unassigned allocno are also changed with a change of the
103 hard-register cost of the allocno when a copy involving the
104 allocno is processed as described above. This is done to
105 show other unassigned allocnos that a given allocno prefers
106 some hard-registers in order to remove the move instruction
107 corresponding to the copy.
108
109 o *Cap*. If a pseudo-register does not live in a region but
110 lives in a nested region, IRA creates a special allocno called
111 a cap in the outer region. A region cap is also created for a
112 subregion cap.
113
114 o *Copy*. Allocnos can be connected by copies. Copies are used
115 to modify hard-register costs for allocnos during coloring.
116 Such modifications reflects a preference to use the same
117 hard-register for the allocnos connected by copies. Usually
118 copies are created for move insns (in this case it results in
119 register coalescing). But IRA also creates copies for operands
120 of an insn which should be assigned to the same hard-register
121 due to constraints in the machine description (it usually
122 results in removing a move generated in reload to satisfy
123 the constraints) and copies referring to the allocno which is
124 the output operand of an instruction and the allocno which is
125 an input operand dying in the instruction (creation of such
126 copies results in less register shuffling). IRA *does not*
127 create copies between the same register allocnos from different
128 regions because we use another technique for propagating
129 hard-register preference on the borders of regions.
130
131 Allocnos (including caps) for the upper region in the region tree
132 *accumulate* information important for coloring from allocnos with
133 the same pseudo-register from nested regions. This includes
134 hard-register and memory costs, conflicts with hard-registers,
135 allocno conflicts, allocno copies and more. *Thus, attributes for
136 allocnos in a region have the same values as if the region had no
137 subregions*. It means that attributes for allocnos in the
138 outermost region corresponding to the function have the same values
139 as though the allocation used only one region which is the entire
140 function. It also means that we can look at IRA work as if the
141 first IRA did allocation for all function then it improved the
142 allocation for loops then their subloops and so on.
143
144 IRA major passes are:
145
146 o Building IRA internal representation which consists of the
147 following subpasses:
148
149 * First, IRA builds regions and creates allocnos (file
150 ira-build.c) and initializes most of their attributes.
151
152 * Then IRA finds an allocno class for each allocno and
153 calculates its initial (non-accumulated) cost of memory and
154 each hard-register of its allocno class (file ira-cost.c).
155
156 * IRA creates live ranges of each allocno, calculates register
157 pressure for each pressure class in each region, sets up
158 conflict hard registers for each allocno and info about calls
159 the allocno lives through (file ira-lives.c).
160
161 * IRA removes low register pressure loops from the regions
162 mostly to speed IRA up (file ira-build.c).
163
164 * IRA propagates accumulated allocno info from lower region
165 allocnos to corresponding upper region allocnos (file
166 ira-build.c).
167
168 * IRA creates all caps (file ira-build.c).
169
170 * Having live-ranges of allocnos and their classes, IRA creates
171 conflicting allocnos for each allocno. Conflicting allocnos
172 are stored as a bit vector or array of pointers to the
173 conflicting allocnos whatever is more profitable (file
174 ira-conflicts.c). At this point IRA creates allocno copies.
175
176 o Coloring. Now IRA has all necessary info to start graph coloring
177 process. It is done in each region on top-down traverse of the
178 region tree (file ira-color.c). There are following subpasses:
179
180 * Finding profitable hard registers of corresponding allocno
181 class for each allocno. For example, only callee-saved hard
182 registers are frequently profitable for allocnos living
183 through colors. If the profitable hard register set of
184 allocno does not form a tree based on subset relation, we use
185 some approximation to form the tree. This approximation is
186 used to figure out trivial colorability of allocnos. The
187 approximation is a pretty rare case.
188
189 * Putting allocnos onto the coloring stack. IRA uses Briggs
190 optimistic coloring which is a major improvement over
191 Chaitin's coloring. Therefore IRA does not spill allocnos at
192 this point. There is some freedom in the order of putting
193 allocnos on the stack which can affect the final result of
194 the allocation. IRA uses some heuristics to improve the
195 order. The major one is to form *threads* from colorable
196 allocnos and push them on the stack by threads. Thread is a
197 set of non-conflicting colorable allocnos connected by
198 copies. The thread contains allocnos from the colorable
199 bucket or colorable allocnos already pushed onto the coloring
200 stack. Pushing thread allocnos one after another onto the
201 stack increases chances of removing copies when the allocnos
202 get the same hard reg.
203
204 We also use a modification of Chaitin-Briggs algorithm which
205 works for intersected register classes of allocnos. To
206 figure out trivial colorability of allocnos, the mentioned
207 above tree of hard register sets is used. To get an idea how
208 the algorithm works in i386 example, let us consider an
209 allocno to which any general hard register can be assigned.
210 If the allocno conflicts with eight allocnos to which only
211 EAX register can be assigned, given allocno is still
212 trivially colorable because all conflicting allocnos might be
213 assigned only to EAX and all other general hard registers are
214 still free.
215
216 To get an idea of the used trivial colorability criterion, it
217 is also useful to read article "Graph-Coloring Register
218 Allocation for Irregular Architectures" by Michael D. Smith
219 and Glen Holloway. Major difference between the article
220 approach and approach used in IRA is that Smith's approach
221 takes register classes only from machine description and IRA
222 calculate register classes from intermediate code too
223 (e.g. an explicit usage of hard registers in RTL code for
224 parameter passing can result in creation of additional
225 register classes which contain or exclude the hard
226 registers). That makes IRA approach useful for improving
227 coloring even for architectures with regular register files
228 and in fact some benchmarking shows the improvement for
229 regular class architectures is even bigger than for irregular
230 ones. Another difference is that Smith's approach chooses
231 intersection of classes of all insn operands in which a given
232 pseudo occurs. IRA can use bigger classes if it is still
233 more profitable than memory usage.
234
235 * Popping the allocnos from the stack and assigning them hard
236 registers. If IRA cannot assign a hard register to an
237 allocno and the allocno is coalesced, IRA undoes the
238 coalescing and puts the uncoalesced allocnos onto the stack in
239 the hope that some such allocnos will get a hard register
240 separately. If IRA fails to assign hard register or memory
241 is more profitable for it, IRA spills the allocno. IRA
242 assigns the allocno the hard-register with minimal full
243 allocation cost which reflects the cost of usage of the
244 hard-register for the allocno and cost of usage of the
245 hard-register for allocnos conflicting with given allocno.
246
247 * Chaitin-Briggs coloring assigns as many pseudos as possible
248 to hard registers. After coloring we try to improve
249 allocation with cost point of view. We improve the
250 allocation by spilling some allocnos and assigning the freed
251 hard registers to other allocnos if it decreases the overall
252 allocation cost.
253
254 * After allocno assigning in the region, IRA modifies the hard
255 register and memory costs for the corresponding allocnos in
256 the subregions to reflect the cost of possible loads, stores,
257 or moves on the border of the region and its subregions.
258 When default regional allocation algorithm is used
259 (-fira-algorithm=mixed), IRA just propagates the assignment
260 for allocnos if the register pressure in the region for the
261 corresponding pressure class is less than number of available
262 hard registers for given pressure class.
263
264 o Spill/restore code moving. When IRA performs an allocation
265 by traversing regions in top-down order, it does not know what
266 happens below in the region tree. Therefore, sometimes IRA
267 misses opportunities to perform a better allocation. A simple
268 optimization tries to improve allocation in a region having
269 subregions and containing in another region. If the
270 corresponding allocnos in the subregion are spilled, it spills
271 the region allocno if it is profitable. The optimization
272 implements a simple iterative algorithm performing profitable
273 transformations while they are still possible. It is fast in
274 practice, so there is no real need for a better time complexity
275 algorithm.
276
277 o Code change. After coloring, two allocnos representing the
278 same pseudo-register outside and inside a region respectively
279 may be assigned to different locations (hard-registers or
280 memory). In this case IRA creates and uses a new
281 pseudo-register inside the region and adds code to move allocno
282 values on the region's borders. This is done during top-down
283 traversal of the regions (file ira-emit.c). In some
284 complicated cases IRA can create a new allocno to move allocno
285 values (e.g. when a swap of values stored in two hard-registers
286 is needed). At this stage, the new allocno is marked as
287 spilled. IRA still creates the pseudo-register and the moves
288 on the region borders even when both allocnos were assigned to
289 the same hard-register. If the reload pass spills a
290 pseudo-register for some reason, the effect will be smaller
291 because another allocno will still be in the hard-register. In
292 most cases, this is better then spilling both allocnos. If
293 reload does not change the allocation for the two
294 pseudo-registers, the trivial move will be removed by
295 post-reload optimizations. IRA does not generate moves for
296 allocnos assigned to the same hard register when the default
297 regional allocation algorithm is used and the register pressure
298 in the region for the corresponding pressure class is less than
299 number of available hard registers for given pressure class.
300 IRA also does some optimizations to remove redundant stores and
301 to reduce code duplication on the region borders.
302
303 o Flattening internal representation. After changing code, IRA
304 transforms its internal representation for several regions into
305 one region representation (file ira-build.c). This process is
306 called IR flattening. Such process is more complicated than IR
307 rebuilding would be, but is much faster.
308
309 o After IR flattening, IRA tries to assign hard registers to all
310 spilled allocnos. This is implemented by a simple and fast
311 priority coloring algorithm (see function
312 ira_reassign_conflict_allocnos::ira-color.c). Here new allocnos
313 created during the code change pass can be assigned to hard
314 registers.
315
316 o At the end IRA calls the reload pass. The reload pass
317 communicates with IRA through several functions in file
318 ira-color.c to improve its decisions in
319
320 * sharing stack slots for the spilled pseudos based on IRA info
321 about pseudo-register conflicts.
322
323 * reassigning hard-registers to all spilled pseudos at the end
324 of each reload iteration.
325
326 * choosing a better hard-register to spill based on IRA info
327 about pseudo-register live ranges and the register pressure
328 in places where the pseudo-register lives.
329
330 IRA uses a lot of data representing the target processors. These
331 data are initialized in file ira.c.
332
333 If function has no loops (or the loops are ignored when
334 -fira-algorithm=CB is used), we have classic Chaitin-Briggs
335 coloring (only instead of separate pass of coalescing, we use hard
336 register preferencing). In such case, IRA works much faster
337 because many things are not made (like IR flattening, the
338 spill/restore optimization, and the code change).
339
340 Literature is worth to read for better understanding the code:
341
342 o Preston Briggs, Keith D. Cooper, Linda Torczon. Improvements to
343 Graph Coloring Register Allocation.
344
345 o David Callahan, Brian Koblenz. Register allocation via
346 hierarchical graph coloring.
347
348 o Keith Cooper, Anshuman Dasgupta, Jason Eckhardt. Revisiting Graph
349 Coloring Register Allocation: A Study of the Chaitin-Briggs and
350 Callahan-Koblenz Algorithms.
351
352 o Guei-Yuan Lueh, Thomas Gross, and Ali-Reza Adl-Tabatabai. Global
353 Register Allocation Based on Graph Fusion.
354
355 o Michael D. Smith and Glenn Holloway. Graph-Coloring Register
356 Allocation for Irregular Architectures
357
358 o Vladimir Makarov. The Integrated Register Allocator for GCC.
359
360 o Vladimir Makarov. The top-down register allocator for irregular
361 register file architectures.
362
363 */
364
365
366 #include "config.h"
367 #include "system.h"
368 #include "coretypes.h"
369 #include "backend.h"
370 #include "target.h"
371 #include "rtl.h"
372 #include "tree.h"
373 #include "df.h"
374 #include "memmodel.h"
375 #include "tm_p.h"
376 #include "insn-config.h"
377 #include "regs.h"
378 #include "ira.h"
379 #include "ira-int.h"
380 #include "diagnostic-core.h"
381 #include "cfgrtl.h"
382 #include "cfgbuild.h"
383 #include "cfgcleanup.h"
384 #include "expr.h"
385 #include "tree-pass.h"
386 #include "output.h"
387 #include "reload.h"
388 #include "cfgloop.h"
389 #include "lra.h"
390 #include "dce.h"
391 #include "dbgcnt.h"
392 #include "rtl-iter.h"
393 #include "shrink-wrap.h"
394 #include "print-rtl.h"
395
396 struct target_ira default_target_ira;
397 class target_ira_int default_target_ira_int;
398 #if SWITCHABLE_TARGET
399 struct target_ira *this_target_ira = &default_target_ira;
400 class target_ira_int *this_target_ira_int = &default_target_ira_int;
401 #endif
402
403 /* A modified value of flag `-fira-verbose' used internally. */
404 int internal_flag_ira_verbose;
405
406 /* Dump file of the allocator if it is not NULL. */
407 FILE *ira_dump_file;
408
409 /* The number of elements in the following array. */
410 int ira_spilled_reg_stack_slots_num;
411
412 /* The following array contains info about spilled pseudo-registers
413 stack slots used in current function so far. */
414 class ira_spilled_reg_stack_slot *ira_spilled_reg_stack_slots;
415
416 /* Correspondingly overall cost of the allocation, overall cost before
417 reload, cost of the allocnos assigned to hard-registers, cost of
418 the allocnos assigned to memory, cost of loads, stores and register
419 move insns generated for pseudo-register live range splitting (see
420 ira-emit.c). */
421 int64_t ira_overall_cost, overall_cost_before;
422 int64_t ira_reg_cost, ira_mem_cost;
423 int64_t ira_load_cost, ira_store_cost, ira_shuffle_cost;
424 int ira_move_loops_num, ira_additional_jumps_num;
425
426 /* All registers that can be eliminated. */
427
428 HARD_REG_SET eliminable_regset;
429
430 /* Value of max_reg_num () before IRA work start. This value helps
431 us to recognize a situation when new pseudos were created during
432 IRA work. */
433 static int max_regno_before_ira;
434
435 /* Temporary hard reg set used for a different calculation. */
436 static HARD_REG_SET temp_hard_regset;
437
438 #define last_mode_for_init_move_cost \
439 (this_target_ira_int->x_last_mode_for_init_move_cost)
440
441
442 /* The function sets up the map IRA_REG_MODE_HARD_REGSET. */
443 static void
setup_reg_mode_hard_regset(void)444 setup_reg_mode_hard_regset (void)
445 {
446 int i, m, hard_regno;
447
448 for (m = 0; m < NUM_MACHINE_MODES; m++)
449 for (hard_regno = 0; hard_regno < FIRST_PSEUDO_REGISTER; hard_regno++)
450 {
451 CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset[hard_regno][m]);
452 for (i = hard_regno_nregs (hard_regno, (machine_mode) m) - 1;
453 i >= 0; i--)
454 if (hard_regno + i < FIRST_PSEUDO_REGISTER)
455 SET_HARD_REG_BIT (ira_reg_mode_hard_regset[hard_regno][m],
456 hard_regno + i);
457 }
458 }
459
460
461 #define no_unit_alloc_regs \
462 (this_target_ira_int->x_no_unit_alloc_regs)
463
464 /* The function sets up the three arrays declared above. */
465 static void
setup_class_hard_regs(void)466 setup_class_hard_regs (void)
467 {
468 int cl, i, hard_regno, n;
469 HARD_REG_SET processed_hard_reg_set;
470
471 ira_assert (SHRT_MAX >= FIRST_PSEUDO_REGISTER);
472 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
473 {
474 temp_hard_regset = reg_class_contents[cl] & ~no_unit_alloc_regs;
475 CLEAR_HARD_REG_SET (processed_hard_reg_set);
476 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
477 {
478 ira_non_ordered_class_hard_regs[cl][i] = -1;
479 ira_class_hard_reg_index[cl][i] = -1;
480 }
481 for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
482 {
483 #ifdef REG_ALLOC_ORDER
484 hard_regno = reg_alloc_order[i];
485 #else
486 hard_regno = i;
487 #endif
488 if (TEST_HARD_REG_BIT (processed_hard_reg_set, hard_regno))
489 continue;
490 SET_HARD_REG_BIT (processed_hard_reg_set, hard_regno);
491 if (! TEST_HARD_REG_BIT (temp_hard_regset, hard_regno))
492 ira_class_hard_reg_index[cl][hard_regno] = -1;
493 else
494 {
495 ira_class_hard_reg_index[cl][hard_regno] = n;
496 ira_class_hard_regs[cl][n++] = hard_regno;
497 }
498 }
499 ira_class_hard_regs_num[cl] = n;
500 for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
501 if (TEST_HARD_REG_BIT (temp_hard_regset, i))
502 ira_non_ordered_class_hard_regs[cl][n++] = i;
503 ira_assert (ira_class_hard_regs_num[cl] == n);
504 }
505 }
506
507 /* Set up global variables defining info about hard registers for the
508 allocation. These depend on USE_HARD_FRAME_P whose TRUE value means
509 that we can use the hard frame pointer for the allocation. */
510 static void
setup_alloc_regs(bool use_hard_frame_p)511 setup_alloc_regs (bool use_hard_frame_p)
512 {
513 #ifdef ADJUST_REG_ALLOC_ORDER
514 ADJUST_REG_ALLOC_ORDER;
515 #endif
516 no_unit_alloc_regs = fixed_nonglobal_reg_set;
517 if (! use_hard_frame_p)
518 add_to_hard_reg_set (&no_unit_alloc_regs, Pmode,
519 HARD_FRAME_POINTER_REGNUM);
520 setup_class_hard_regs ();
521 }
522
523
524
525 #define alloc_reg_class_subclasses \
526 (this_target_ira_int->x_alloc_reg_class_subclasses)
527
528 /* Initialize the table of subclasses of each reg class. */
529 static void
setup_reg_subclasses(void)530 setup_reg_subclasses (void)
531 {
532 int i, j;
533 HARD_REG_SET temp_hard_regset2;
534
535 for (i = 0; i < N_REG_CLASSES; i++)
536 for (j = 0; j < N_REG_CLASSES; j++)
537 alloc_reg_class_subclasses[i][j] = LIM_REG_CLASSES;
538
539 for (i = 0; i < N_REG_CLASSES; i++)
540 {
541 if (i == (int) NO_REGS)
542 continue;
543
544 temp_hard_regset = reg_class_contents[i] & ~no_unit_alloc_regs;
545 if (hard_reg_set_empty_p (temp_hard_regset))
546 continue;
547 for (j = 0; j < N_REG_CLASSES; j++)
548 if (i != j)
549 {
550 enum reg_class *p;
551
552 temp_hard_regset2 = reg_class_contents[j] & ~no_unit_alloc_regs;
553 if (! hard_reg_set_subset_p (temp_hard_regset,
554 temp_hard_regset2))
555 continue;
556 p = &alloc_reg_class_subclasses[j][0];
557 while (*p != LIM_REG_CLASSES) p++;
558 *p = (enum reg_class) i;
559 }
560 }
561 }
562
563
564
565 /* Set up IRA_MEMORY_MOVE_COST and IRA_MAX_MEMORY_MOVE_COST. */
566 static void
setup_class_subset_and_memory_move_costs(void)567 setup_class_subset_and_memory_move_costs (void)
568 {
569 int cl, cl2, mode, cost;
570 HARD_REG_SET temp_hard_regset2;
571
572 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
573 ira_memory_move_cost[mode][NO_REGS][0]
574 = ira_memory_move_cost[mode][NO_REGS][1] = SHRT_MAX;
575 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
576 {
577 if (cl != (int) NO_REGS)
578 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
579 {
580 ira_max_memory_move_cost[mode][cl][0]
581 = ira_memory_move_cost[mode][cl][0]
582 = memory_move_cost ((machine_mode) mode,
583 (reg_class_t) cl, false);
584 ira_max_memory_move_cost[mode][cl][1]
585 = ira_memory_move_cost[mode][cl][1]
586 = memory_move_cost ((machine_mode) mode,
587 (reg_class_t) cl, true);
588 /* Costs for NO_REGS are used in cost calculation on the
589 1st pass when the preferred register classes are not
590 known yet. In this case we take the best scenario. */
591 if (ira_memory_move_cost[mode][NO_REGS][0]
592 > ira_memory_move_cost[mode][cl][0])
593 ira_max_memory_move_cost[mode][NO_REGS][0]
594 = ira_memory_move_cost[mode][NO_REGS][0]
595 = ira_memory_move_cost[mode][cl][0];
596 if (ira_memory_move_cost[mode][NO_REGS][1]
597 > ira_memory_move_cost[mode][cl][1])
598 ira_max_memory_move_cost[mode][NO_REGS][1]
599 = ira_memory_move_cost[mode][NO_REGS][1]
600 = ira_memory_move_cost[mode][cl][1];
601 }
602 }
603 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
604 for (cl2 = (int) N_REG_CLASSES - 1; cl2 >= 0; cl2--)
605 {
606 temp_hard_regset = reg_class_contents[cl] & ~no_unit_alloc_regs;
607 temp_hard_regset2 = reg_class_contents[cl2] & ~no_unit_alloc_regs;
608 ira_class_subset_p[cl][cl2]
609 = hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2);
610 if (! hard_reg_set_empty_p (temp_hard_regset2)
611 && hard_reg_set_subset_p (reg_class_contents[cl2],
612 reg_class_contents[cl]))
613 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
614 {
615 cost = ira_memory_move_cost[mode][cl2][0];
616 if (cost > ira_max_memory_move_cost[mode][cl][0])
617 ira_max_memory_move_cost[mode][cl][0] = cost;
618 cost = ira_memory_move_cost[mode][cl2][1];
619 if (cost > ira_max_memory_move_cost[mode][cl][1])
620 ira_max_memory_move_cost[mode][cl][1] = cost;
621 }
622 }
623 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
624 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
625 {
626 ira_memory_move_cost[mode][cl][0]
627 = ira_max_memory_move_cost[mode][cl][0];
628 ira_memory_move_cost[mode][cl][1]
629 = ira_max_memory_move_cost[mode][cl][1];
630 }
631 setup_reg_subclasses ();
632 }
633
634
635
636 /* Define the following macro if allocation through malloc if
637 preferable. */
638 #define IRA_NO_OBSTACK
639
640 #ifndef IRA_NO_OBSTACK
641 /* Obstack used for storing all dynamic data (except bitmaps) of the
642 IRA. */
643 static struct obstack ira_obstack;
644 #endif
645
646 /* Obstack used for storing all bitmaps of the IRA. */
647 static struct bitmap_obstack ira_bitmap_obstack;
648
649 /* Allocate memory of size LEN for IRA data. */
650 void *
ira_allocate(size_t len)651 ira_allocate (size_t len)
652 {
653 void *res;
654
655 #ifndef IRA_NO_OBSTACK
656 res = obstack_alloc (&ira_obstack, len);
657 #else
658 res = xmalloc (len);
659 #endif
660 return res;
661 }
662
663 /* Free memory ADDR allocated for IRA data. */
664 void
ira_free(void * addr ATTRIBUTE_UNUSED)665 ira_free (void *addr ATTRIBUTE_UNUSED)
666 {
667 #ifndef IRA_NO_OBSTACK
668 /* do nothing */
669 #else
670 free (addr);
671 #endif
672 }
673
674
675 /* Allocate and returns bitmap for IRA. */
676 bitmap
ira_allocate_bitmap(void)677 ira_allocate_bitmap (void)
678 {
679 return BITMAP_ALLOC (&ira_bitmap_obstack);
680 }
681
682 /* Free bitmap B allocated for IRA. */
683 void
ira_free_bitmap(bitmap b ATTRIBUTE_UNUSED)684 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED)
685 {
686 /* do nothing */
687 }
688
689
690
691 /* Output information about allocation of all allocnos (except for
692 caps) into file F. */
693 void
ira_print_disposition(FILE * f)694 ira_print_disposition (FILE *f)
695 {
696 int i, n, max_regno;
697 ira_allocno_t a;
698 basic_block bb;
699
700 fprintf (f, "Disposition:");
701 max_regno = max_reg_num ();
702 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
703 for (a = ira_regno_allocno_map[i];
704 a != NULL;
705 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
706 {
707 if (n % 4 == 0)
708 fprintf (f, "\n");
709 n++;
710 fprintf (f, " %4d:r%-4d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
711 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
712 fprintf (f, "b%-3d", bb->index);
713 else
714 fprintf (f, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
715 if (ALLOCNO_HARD_REGNO (a) >= 0)
716 fprintf (f, " %3d", ALLOCNO_HARD_REGNO (a));
717 else
718 fprintf (f, " mem");
719 }
720 fprintf (f, "\n");
721 }
722
723 /* Outputs information about allocation of all allocnos into
724 stderr. */
725 void
ira_debug_disposition(void)726 ira_debug_disposition (void)
727 {
728 ira_print_disposition (stderr);
729 }
730
731
732
733 /* Set up ira_stack_reg_pressure_class which is the biggest pressure
734 register class containing stack registers or NO_REGS if there are
735 no stack registers. To find this class, we iterate through all
736 register pressure classes and choose the first register pressure
737 class containing all the stack registers and having the biggest
738 size. */
739 static void
setup_stack_reg_pressure_class(void)740 setup_stack_reg_pressure_class (void)
741 {
742 ira_stack_reg_pressure_class = NO_REGS;
743 #ifdef STACK_REGS
744 {
745 int i, best, size;
746 enum reg_class cl;
747 HARD_REG_SET temp_hard_regset2;
748
749 CLEAR_HARD_REG_SET (temp_hard_regset);
750 for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
751 SET_HARD_REG_BIT (temp_hard_regset, i);
752 best = 0;
753 for (i = 0; i < ira_pressure_classes_num; i++)
754 {
755 cl = ira_pressure_classes[i];
756 temp_hard_regset2 = temp_hard_regset & reg_class_contents[cl];
757 size = hard_reg_set_size (temp_hard_regset2);
758 if (best < size)
759 {
760 best = size;
761 ira_stack_reg_pressure_class = cl;
762 }
763 }
764 }
765 #endif
766 }
767
768 /* Find pressure classes which are register classes for which we
769 calculate register pressure in IRA, register pressure sensitive
770 insn scheduling, and register pressure sensitive loop invariant
771 motion.
772
773 To make register pressure calculation easy, we always use
774 non-intersected register pressure classes. A move of hard
775 registers from one register pressure class is not more expensive
776 than load and store of the hard registers. Most likely an allocno
777 class will be a subset of a register pressure class and in many
778 cases a register pressure class. That makes usage of register
779 pressure classes a good approximation to find a high register
780 pressure. */
781 static void
setup_pressure_classes(void)782 setup_pressure_classes (void)
783 {
784 int cost, i, n, curr;
785 int cl, cl2;
786 enum reg_class pressure_classes[N_REG_CLASSES];
787 int m;
788 HARD_REG_SET temp_hard_regset2;
789 bool insert_p;
790
791 if (targetm.compute_pressure_classes)
792 n = targetm.compute_pressure_classes (pressure_classes);
793 else
794 {
795 n = 0;
796 for (cl = 0; cl < N_REG_CLASSES; cl++)
797 {
798 if (ira_class_hard_regs_num[cl] == 0)
799 continue;
800 if (ira_class_hard_regs_num[cl] != 1
801 /* A register class without subclasses may contain a few
802 hard registers and movement between them is costly
803 (e.g. SPARC FPCC registers). We still should consider it
804 as a candidate for a pressure class. */
805 && alloc_reg_class_subclasses[cl][0] < cl)
806 {
807 /* Check that the moves between any hard registers of the
808 current class are not more expensive for a legal mode
809 than load/store of the hard registers of the current
810 class. Such class is a potential candidate to be a
811 register pressure class. */
812 for (m = 0; m < NUM_MACHINE_MODES; m++)
813 {
814 temp_hard_regset
815 = (reg_class_contents[cl]
816 & ~(no_unit_alloc_regs
817 | ira_prohibited_class_mode_regs[cl][m]));
818 if (hard_reg_set_empty_p (temp_hard_regset))
819 continue;
820 ira_init_register_move_cost_if_necessary ((machine_mode) m);
821 cost = ira_register_move_cost[m][cl][cl];
822 if (cost <= ira_max_memory_move_cost[m][cl][1]
823 || cost <= ira_max_memory_move_cost[m][cl][0])
824 break;
825 }
826 if (m >= NUM_MACHINE_MODES)
827 continue;
828 }
829 curr = 0;
830 insert_p = true;
831 temp_hard_regset = reg_class_contents[cl] & ~no_unit_alloc_regs;
832 /* Remove so far added pressure classes which are subset of the
833 current candidate class. Prefer GENERAL_REGS as a pressure
834 register class to another class containing the same
835 allocatable hard registers. We do this because machine
836 dependent cost hooks might give wrong costs for the latter
837 class but always give the right cost for the former class
838 (GENERAL_REGS). */
839 for (i = 0; i < n; i++)
840 {
841 cl2 = pressure_classes[i];
842 temp_hard_regset2 = (reg_class_contents[cl2]
843 & ~no_unit_alloc_regs);
844 if (hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2)
845 && (temp_hard_regset != temp_hard_regset2
846 || cl2 == (int) GENERAL_REGS))
847 {
848 pressure_classes[curr++] = (enum reg_class) cl2;
849 insert_p = false;
850 continue;
851 }
852 if (hard_reg_set_subset_p (temp_hard_regset2, temp_hard_regset)
853 && (temp_hard_regset2 != temp_hard_regset
854 || cl == (int) GENERAL_REGS))
855 continue;
856 if (temp_hard_regset2 == temp_hard_regset)
857 insert_p = false;
858 pressure_classes[curr++] = (enum reg_class) cl2;
859 }
860 /* If the current candidate is a subset of a so far added
861 pressure class, don't add it to the list of the pressure
862 classes. */
863 if (insert_p)
864 pressure_classes[curr++] = (enum reg_class) cl;
865 n = curr;
866 }
867 }
868 #ifdef ENABLE_IRA_CHECKING
869 {
870 HARD_REG_SET ignore_hard_regs;
871
872 /* Check pressure classes correctness: here we check that hard
873 registers from all register pressure classes contains all hard
874 registers available for the allocation. */
875 CLEAR_HARD_REG_SET (temp_hard_regset);
876 CLEAR_HARD_REG_SET (temp_hard_regset2);
877 ignore_hard_regs = no_unit_alloc_regs;
878 for (cl = 0; cl < LIM_REG_CLASSES; cl++)
879 {
880 /* For some targets (like MIPS with MD_REGS), there are some
881 classes with hard registers available for allocation but
882 not able to hold value of any mode. */
883 for (m = 0; m < NUM_MACHINE_MODES; m++)
884 if (contains_reg_of_mode[cl][m])
885 break;
886 if (m >= NUM_MACHINE_MODES)
887 {
888 ignore_hard_regs |= reg_class_contents[cl];
889 continue;
890 }
891 for (i = 0; i < n; i++)
892 if ((int) pressure_classes[i] == cl)
893 break;
894 temp_hard_regset2 |= reg_class_contents[cl];
895 if (i < n)
896 temp_hard_regset |= reg_class_contents[cl];
897 }
898 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
899 /* Some targets (like SPARC with ICC reg) have allocatable regs
900 for which no reg class is defined. */
901 if (REGNO_REG_CLASS (i) == NO_REGS)
902 SET_HARD_REG_BIT (ignore_hard_regs, i);
903 temp_hard_regset &= ~ignore_hard_regs;
904 temp_hard_regset2 &= ~ignore_hard_regs;
905 ira_assert (hard_reg_set_subset_p (temp_hard_regset2, temp_hard_regset));
906 }
907 #endif
908 ira_pressure_classes_num = 0;
909 for (i = 0; i < n; i++)
910 {
911 cl = (int) pressure_classes[i];
912 ira_reg_pressure_class_p[cl] = true;
913 ira_pressure_classes[ira_pressure_classes_num++] = (enum reg_class) cl;
914 }
915 setup_stack_reg_pressure_class ();
916 }
917
918 /* Set up IRA_UNIFORM_CLASS_P. Uniform class is a register class
919 whose register move cost between any registers of the class is the
920 same as for all its subclasses. We use the data to speed up the
921 2nd pass of calculations of allocno costs. */
922 static void
setup_uniform_class_p(void)923 setup_uniform_class_p (void)
924 {
925 int i, cl, cl2, m;
926
927 for (cl = 0; cl < N_REG_CLASSES; cl++)
928 {
929 ira_uniform_class_p[cl] = false;
930 if (ira_class_hard_regs_num[cl] == 0)
931 continue;
932 /* We cannot use alloc_reg_class_subclasses here because move
933 cost hooks does not take into account that some registers are
934 unavailable for the subtarget. E.g. for i686, INT_SSE_REGS
935 is element of alloc_reg_class_subclasses for GENERAL_REGS
936 because SSE regs are unavailable. */
937 for (i = 0; (cl2 = reg_class_subclasses[cl][i]) != LIM_REG_CLASSES; i++)
938 {
939 if (ira_class_hard_regs_num[cl2] == 0)
940 continue;
941 for (m = 0; m < NUM_MACHINE_MODES; m++)
942 if (contains_reg_of_mode[cl][m] && contains_reg_of_mode[cl2][m])
943 {
944 ira_init_register_move_cost_if_necessary ((machine_mode) m);
945 if (ira_register_move_cost[m][cl][cl]
946 != ira_register_move_cost[m][cl2][cl2])
947 break;
948 }
949 if (m < NUM_MACHINE_MODES)
950 break;
951 }
952 if (cl2 == LIM_REG_CLASSES)
953 ira_uniform_class_p[cl] = true;
954 }
955 }
956
957 /* Set up IRA_ALLOCNO_CLASSES, IRA_ALLOCNO_CLASSES_NUM,
958 IRA_IMPORTANT_CLASSES, and IRA_IMPORTANT_CLASSES_NUM.
959
960 Target may have many subtargets and not all target hard registers can
961 be used for allocation, e.g. x86 port in 32-bit mode cannot use
962 hard registers introduced in x86-64 like r8-r15). Some classes
963 might have the same allocatable hard registers, e.g. INDEX_REGS
964 and GENERAL_REGS in x86 port in 32-bit mode. To decrease different
965 calculations efforts we introduce allocno classes which contain
966 unique non-empty sets of allocatable hard-registers.
967
968 Pseudo class cost calculation in ira-costs.c is very expensive.
969 Therefore we are trying to decrease number of classes involved in
970 such calculation. Register classes used in the cost calculation
971 are called important classes. They are allocno classes and other
972 non-empty classes whose allocatable hard register sets are inside
973 of an allocno class hard register set. From the first sight, it
974 looks like that they are just allocno classes. It is not true. In
975 example of x86-port in 32-bit mode, allocno classes will contain
976 GENERAL_REGS but not LEGACY_REGS (because allocatable hard
977 registers are the same for the both classes). The important
978 classes will contain GENERAL_REGS and LEGACY_REGS. It is done
979 because a machine description insn constraint may refers for
980 LEGACY_REGS and code in ira-costs.c is mostly base on investigation
981 of the insn constraints. */
982 static void
setup_allocno_and_important_classes(void)983 setup_allocno_and_important_classes (void)
984 {
985 int i, j, n, cl;
986 bool set_p;
987 HARD_REG_SET temp_hard_regset2;
988 static enum reg_class classes[LIM_REG_CLASSES + 1];
989
990 n = 0;
991 /* Collect classes which contain unique sets of allocatable hard
992 registers. Prefer GENERAL_REGS to other classes containing the
993 same set of hard registers. */
994 for (i = 0; i < LIM_REG_CLASSES; i++)
995 {
996 temp_hard_regset = reg_class_contents[i] & ~no_unit_alloc_regs;
997 for (j = 0; j < n; j++)
998 {
999 cl = classes[j];
1000 temp_hard_regset2 = reg_class_contents[cl] & ~no_unit_alloc_regs;
1001 if (temp_hard_regset == temp_hard_regset2)
1002 break;
1003 }
1004 if (j >= n || targetm.additional_allocno_class_p (i))
1005 classes[n++] = (enum reg_class) i;
1006 else if (i == GENERAL_REGS)
1007 /* Prefer general regs. For i386 example, it means that
1008 we prefer GENERAL_REGS over INDEX_REGS or LEGACY_REGS
1009 (all of them consists of the same available hard
1010 registers). */
1011 classes[j] = (enum reg_class) i;
1012 }
1013 classes[n] = LIM_REG_CLASSES;
1014
1015 /* Set up classes which can be used for allocnos as classes
1016 containing non-empty unique sets of allocatable hard
1017 registers. */
1018 ira_allocno_classes_num = 0;
1019 for (i = 0; (cl = classes[i]) != LIM_REG_CLASSES; i++)
1020 if (ira_class_hard_regs_num[cl] > 0)
1021 ira_allocno_classes[ira_allocno_classes_num++] = (enum reg_class) cl;
1022 ira_important_classes_num = 0;
1023 /* Add non-allocno classes containing to non-empty set of
1024 allocatable hard regs. */
1025 for (cl = 0; cl < N_REG_CLASSES; cl++)
1026 if (ira_class_hard_regs_num[cl] > 0)
1027 {
1028 temp_hard_regset = reg_class_contents[cl] & ~no_unit_alloc_regs;
1029 set_p = false;
1030 for (j = 0; j < ira_allocno_classes_num; j++)
1031 {
1032 temp_hard_regset2 = (reg_class_contents[ira_allocno_classes[j]]
1033 & ~no_unit_alloc_regs);
1034 if ((enum reg_class) cl == ira_allocno_classes[j])
1035 break;
1036 else if (hard_reg_set_subset_p (temp_hard_regset,
1037 temp_hard_regset2))
1038 set_p = true;
1039 }
1040 if (set_p && j >= ira_allocno_classes_num)
1041 ira_important_classes[ira_important_classes_num++]
1042 = (enum reg_class) cl;
1043 }
1044 /* Now add allocno classes to the important classes. */
1045 for (j = 0; j < ira_allocno_classes_num; j++)
1046 ira_important_classes[ira_important_classes_num++]
1047 = ira_allocno_classes[j];
1048 for (cl = 0; cl < N_REG_CLASSES; cl++)
1049 {
1050 ira_reg_allocno_class_p[cl] = false;
1051 ira_reg_pressure_class_p[cl] = false;
1052 }
1053 for (j = 0; j < ira_allocno_classes_num; j++)
1054 ira_reg_allocno_class_p[ira_allocno_classes[j]] = true;
1055 setup_pressure_classes ();
1056 setup_uniform_class_p ();
1057 }
1058
1059 /* Setup translation in CLASS_TRANSLATE of all classes into a class
1060 given by array CLASSES of length CLASSES_NUM. The function is used
1061 make translation any reg class to an allocno class or to an
1062 pressure class. This translation is necessary for some
1063 calculations when we can use only allocno or pressure classes and
1064 such translation represents an approximate representation of all
1065 classes.
1066
1067 The translation in case when allocatable hard register set of a
1068 given class is subset of allocatable hard register set of a class
1069 in CLASSES is pretty simple. We use smallest classes from CLASSES
1070 containing a given class. If allocatable hard register set of a
1071 given class is not a subset of any corresponding set of a class
1072 from CLASSES, we use the cheapest (with load/store point of view)
1073 class from CLASSES whose set intersects with given class set. */
1074 static void
setup_class_translate_array(enum reg_class * class_translate,int classes_num,enum reg_class * classes)1075 setup_class_translate_array (enum reg_class *class_translate,
1076 int classes_num, enum reg_class *classes)
1077 {
1078 int cl, mode;
1079 enum reg_class aclass, best_class, *cl_ptr;
1080 int i, cost, min_cost, best_cost;
1081
1082 for (cl = 0; cl < N_REG_CLASSES; cl++)
1083 class_translate[cl] = NO_REGS;
1084
1085 for (i = 0; i < classes_num; i++)
1086 {
1087 aclass = classes[i];
1088 for (cl_ptr = &alloc_reg_class_subclasses[aclass][0];
1089 (cl = *cl_ptr) != LIM_REG_CLASSES;
1090 cl_ptr++)
1091 if (class_translate[cl] == NO_REGS)
1092 class_translate[cl] = aclass;
1093 class_translate[aclass] = aclass;
1094 }
1095 /* For classes which are not fully covered by one of given classes
1096 (in other words covered by more one given class), use the
1097 cheapest class. */
1098 for (cl = 0; cl < N_REG_CLASSES; cl++)
1099 {
1100 if (cl == NO_REGS || class_translate[cl] != NO_REGS)
1101 continue;
1102 best_class = NO_REGS;
1103 best_cost = INT_MAX;
1104 for (i = 0; i < classes_num; i++)
1105 {
1106 aclass = classes[i];
1107 temp_hard_regset = (reg_class_contents[aclass]
1108 & reg_class_contents[cl]
1109 & ~no_unit_alloc_regs);
1110 if (! hard_reg_set_empty_p (temp_hard_regset))
1111 {
1112 min_cost = INT_MAX;
1113 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1114 {
1115 cost = (ira_memory_move_cost[mode][aclass][0]
1116 + ira_memory_move_cost[mode][aclass][1]);
1117 if (min_cost > cost)
1118 min_cost = cost;
1119 }
1120 if (best_class == NO_REGS || best_cost > min_cost)
1121 {
1122 best_class = aclass;
1123 best_cost = min_cost;
1124 }
1125 }
1126 }
1127 class_translate[cl] = best_class;
1128 }
1129 }
1130
1131 /* Set up array IRA_ALLOCNO_CLASS_TRANSLATE and
1132 IRA_PRESSURE_CLASS_TRANSLATE. */
1133 static void
setup_class_translate(void)1134 setup_class_translate (void)
1135 {
1136 setup_class_translate_array (ira_allocno_class_translate,
1137 ira_allocno_classes_num, ira_allocno_classes);
1138 setup_class_translate_array (ira_pressure_class_translate,
1139 ira_pressure_classes_num, ira_pressure_classes);
1140 }
1141
1142 /* Order numbers of allocno classes in original target allocno class
1143 array, -1 for non-allocno classes. */
1144 static int allocno_class_order[N_REG_CLASSES];
1145
1146 /* The function used to sort the important classes. */
1147 static int
comp_reg_classes_func(const void * v1p,const void * v2p)1148 comp_reg_classes_func (const void *v1p, const void *v2p)
1149 {
1150 enum reg_class cl1 = *(const enum reg_class *) v1p;
1151 enum reg_class cl2 = *(const enum reg_class *) v2p;
1152 enum reg_class tcl1, tcl2;
1153 int diff;
1154
1155 tcl1 = ira_allocno_class_translate[cl1];
1156 tcl2 = ira_allocno_class_translate[cl2];
1157 if (tcl1 != NO_REGS && tcl2 != NO_REGS
1158 && (diff = allocno_class_order[tcl1] - allocno_class_order[tcl2]) != 0)
1159 return diff;
1160 return (int) cl1 - (int) cl2;
1161 }
1162
1163 /* For correct work of function setup_reg_class_relation we need to
1164 reorder important classes according to the order of their allocno
1165 classes. It places important classes containing the same
1166 allocatable hard register set adjacent to each other and allocno
1167 class with the allocatable hard register set right after the other
1168 important classes with the same set.
1169
1170 In example from comments of function
1171 setup_allocno_and_important_classes, it places LEGACY_REGS and
1172 GENERAL_REGS close to each other and GENERAL_REGS is after
1173 LEGACY_REGS. */
1174 static void
reorder_important_classes(void)1175 reorder_important_classes (void)
1176 {
1177 int i;
1178
1179 for (i = 0; i < N_REG_CLASSES; i++)
1180 allocno_class_order[i] = -1;
1181 for (i = 0; i < ira_allocno_classes_num; i++)
1182 allocno_class_order[ira_allocno_classes[i]] = i;
1183 qsort (ira_important_classes, ira_important_classes_num,
1184 sizeof (enum reg_class), comp_reg_classes_func);
1185 for (i = 0; i < ira_important_classes_num; i++)
1186 ira_important_class_nums[ira_important_classes[i]] = i;
1187 }
1188
1189 /* Set up IRA_REG_CLASS_SUBUNION, IRA_REG_CLASS_SUPERUNION,
1190 IRA_REG_CLASS_SUPER_CLASSES, IRA_REG_CLASSES_INTERSECT, and
1191 IRA_REG_CLASSES_INTERSECT_P. For the meaning of the relations,
1192 please see corresponding comments in ira-int.h. */
1193 static void
setup_reg_class_relations(void)1194 setup_reg_class_relations (void)
1195 {
1196 int i, cl1, cl2, cl3;
1197 HARD_REG_SET intersection_set, union_set, temp_set2;
1198 bool important_class_p[N_REG_CLASSES];
1199
1200 memset (important_class_p, 0, sizeof (important_class_p));
1201 for (i = 0; i < ira_important_classes_num; i++)
1202 important_class_p[ira_important_classes[i]] = true;
1203 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1204 {
1205 ira_reg_class_super_classes[cl1][0] = LIM_REG_CLASSES;
1206 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1207 {
1208 ira_reg_classes_intersect_p[cl1][cl2] = false;
1209 ira_reg_class_intersect[cl1][cl2] = NO_REGS;
1210 ira_reg_class_subset[cl1][cl2] = NO_REGS;
1211 temp_hard_regset = reg_class_contents[cl1] & ~no_unit_alloc_regs;
1212 temp_set2 = reg_class_contents[cl2] & ~no_unit_alloc_regs;
1213 if (hard_reg_set_empty_p (temp_hard_regset)
1214 && hard_reg_set_empty_p (temp_set2))
1215 {
1216 /* The both classes have no allocatable hard registers
1217 -- take all class hard registers into account and use
1218 reg_class_subunion and reg_class_superunion. */
1219 for (i = 0;; i++)
1220 {
1221 cl3 = reg_class_subclasses[cl1][i];
1222 if (cl3 == LIM_REG_CLASSES)
1223 break;
1224 if (reg_class_subset_p (ira_reg_class_intersect[cl1][cl2],
1225 (enum reg_class) cl3))
1226 ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
1227 }
1228 ira_reg_class_subunion[cl1][cl2] = reg_class_subunion[cl1][cl2];
1229 ira_reg_class_superunion[cl1][cl2] = reg_class_superunion[cl1][cl2];
1230 continue;
1231 }
1232 ira_reg_classes_intersect_p[cl1][cl2]
1233 = hard_reg_set_intersect_p (temp_hard_regset, temp_set2);
1234 if (important_class_p[cl1] && important_class_p[cl2]
1235 && hard_reg_set_subset_p (temp_hard_regset, temp_set2))
1236 {
1237 /* CL1 and CL2 are important classes and CL1 allocatable
1238 hard register set is inside of CL2 allocatable hard
1239 registers -- make CL1 a superset of CL2. */
1240 enum reg_class *p;
1241
1242 p = &ira_reg_class_super_classes[cl1][0];
1243 while (*p != LIM_REG_CLASSES)
1244 p++;
1245 *p++ = (enum reg_class) cl2;
1246 *p = LIM_REG_CLASSES;
1247 }
1248 ira_reg_class_subunion[cl1][cl2] = NO_REGS;
1249 ira_reg_class_superunion[cl1][cl2] = NO_REGS;
1250 intersection_set = (reg_class_contents[cl1]
1251 & reg_class_contents[cl2]
1252 & ~no_unit_alloc_regs);
1253 union_set = ((reg_class_contents[cl1] | reg_class_contents[cl2])
1254 & ~no_unit_alloc_regs);
1255 for (cl3 = 0; cl3 < N_REG_CLASSES; cl3++)
1256 {
1257 temp_hard_regset = reg_class_contents[cl3] & ~no_unit_alloc_regs;
1258 if (hard_reg_set_subset_p (temp_hard_regset, intersection_set))
1259 {
1260 /* CL3 allocatable hard register set is inside of
1261 intersection of allocatable hard register sets
1262 of CL1 and CL2. */
1263 if (important_class_p[cl3])
1264 {
1265 temp_set2
1266 = (reg_class_contents
1267 [ira_reg_class_intersect[cl1][cl2]]);
1268 temp_set2 &= ~no_unit_alloc_regs;
1269 if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1270 /* If the allocatable hard register sets are
1271 the same, prefer GENERAL_REGS or the
1272 smallest class for debugging
1273 purposes. */
1274 || (temp_hard_regset == temp_set2
1275 && (cl3 == GENERAL_REGS
1276 || ((ira_reg_class_intersect[cl1][cl2]
1277 != GENERAL_REGS)
1278 && hard_reg_set_subset_p
1279 (reg_class_contents[cl3],
1280 reg_class_contents
1281 [(int)
1282 ira_reg_class_intersect[cl1][cl2]])))))
1283 ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
1284 }
1285 temp_set2
1286 = (reg_class_contents[ira_reg_class_subset[cl1][cl2]]
1287 & ~no_unit_alloc_regs);
1288 if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1289 /* Ignore unavailable hard registers and prefer
1290 smallest class for debugging purposes. */
1291 || (temp_hard_regset == temp_set2
1292 && hard_reg_set_subset_p
1293 (reg_class_contents[cl3],
1294 reg_class_contents
1295 [(int) ira_reg_class_subset[cl1][cl2]])))
1296 ira_reg_class_subset[cl1][cl2] = (enum reg_class) cl3;
1297 }
1298 if (important_class_p[cl3]
1299 && hard_reg_set_subset_p (temp_hard_regset, union_set))
1300 {
1301 /* CL3 allocatable hard register set is inside of
1302 union of allocatable hard register sets of CL1
1303 and CL2. */
1304 temp_set2
1305 = (reg_class_contents[ira_reg_class_subunion[cl1][cl2]]
1306 & ~no_unit_alloc_regs);
1307 if (ira_reg_class_subunion[cl1][cl2] == NO_REGS
1308 || (hard_reg_set_subset_p (temp_set2, temp_hard_regset)
1309
1310 && (temp_set2 != temp_hard_regset
1311 || cl3 == GENERAL_REGS
1312 /* If the allocatable hard register sets are the
1313 same, prefer GENERAL_REGS or the smallest
1314 class for debugging purposes. */
1315 || (ira_reg_class_subunion[cl1][cl2] != GENERAL_REGS
1316 && hard_reg_set_subset_p
1317 (reg_class_contents[cl3],
1318 reg_class_contents
1319 [(int) ira_reg_class_subunion[cl1][cl2]])))))
1320 ira_reg_class_subunion[cl1][cl2] = (enum reg_class) cl3;
1321 }
1322 if (hard_reg_set_subset_p (union_set, temp_hard_regset))
1323 {
1324 /* CL3 allocatable hard register set contains union
1325 of allocatable hard register sets of CL1 and
1326 CL2. */
1327 temp_set2
1328 = (reg_class_contents[ira_reg_class_superunion[cl1][cl2]]
1329 & ~no_unit_alloc_regs);
1330 if (ira_reg_class_superunion[cl1][cl2] == NO_REGS
1331 || (hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1332
1333 && (temp_set2 != temp_hard_regset
1334 || cl3 == GENERAL_REGS
1335 /* If the allocatable hard register sets are the
1336 same, prefer GENERAL_REGS or the smallest
1337 class for debugging purposes. */
1338 || (ira_reg_class_superunion[cl1][cl2] != GENERAL_REGS
1339 && hard_reg_set_subset_p
1340 (reg_class_contents[cl3],
1341 reg_class_contents
1342 [(int) ira_reg_class_superunion[cl1][cl2]])))))
1343 ira_reg_class_superunion[cl1][cl2] = (enum reg_class) cl3;
1344 }
1345 }
1346 }
1347 }
1348 }
1349
1350 /* Output all uniform and important classes into file F. */
1351 static void
print_uniform_and_important_classes(FILE * f)1352 print_uniform_and_important_classes (FILE *f)
1353 {
1354 int i, cl;
1355
1356 fprintf (f, "Uniform classes:\n");
1357 for (cl = 0; cl < N_REG_CLASSES; cl++)
1358 if (ira_uniform_class_p[cl])
1359 fprintf (f, " %s", reg_class_names[cl]);
1360 fprintf (f, "\nImportant classes:\n");
1361 for (i = 0; i < ira_important_classes_num; i++)
1362 fprintf (f, " %s", reg_class_names[ira_important_classes[i]]);
1363 fprintf (f, "\n");
1364 }
1365
1366 /* Output all possible allocno or pressure classes and their
1367 translation map into file F. */
1368 static void
print_translated_classes(FILE * f,bool pressure_p)1369 print_translated_classes (FILE *f, bool pressure_p)
1370 {
1371 int classes_num = (pressure_p
1372 ? ira_pressure_classes_num : ira_allocno_classes_num);
1373 enum reg_class *classes = (pressure_p
1374 ? ira_pressure_classes : ira_allocno_classes);
1375 enum reg_class *class_translate = (pressure_p
1376 ? ira_pressure_class_translate
1377 : ira_allocno_class_translate);
1378 int i;
1379
1380 fprintf (f, "%s classes:\n", pressure_p ? "Pressure" : "Allocno");
1381 for (i = 0; i < classes_num; i++)
1382 fprintf (f, " %s", reg_class_names[classes[i]]);
1383 fprintf (f, "\nClass translation:\n");
1384 for (i = 0; i < N_REG_CLASSES; i++)
1385 fprintf (f, " %s -> %s\n", reg_class_names[i],
1386 reg_class_names[class_translate[i]]);
1387 }
1388
1389 /* Output all possible allocno and translation classes and the
1390 translation maps into stderr. */
1391 void
ira_debug_allocno_classes(void)1392 ira_debug_allocno_classes (void)
1393 {
1394 print_uniform_and_important_classes (stderr);
1395 print_translated_classes (stderr, false);
1396 print_translated_classes (stderr, true);
1397 }
1398
1399 /* Set up different arrays concerning class subsets, allocno and
1400 important classes. */
1401 static void
find_reg_classes(void)1402 find_reg_classes (void)
1403 {
1404 setup_allocno_and_important_classes ();
1405 setup_class_translate ();
1406 reorder_important_classes ();
1407 setup_reg_class_relations ();
1408 }
1409
1410
1411
1412 /* Set up the array above. */
1413 static void
setup_hard_regno_aclass(void)1414 setup_hard_regno_aclass (void)
1415 {
1416 int i;
1417
1418 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1419 {
1420 #if 1
1421 ira_hard_regno_allocno_class[i]
1422 = (TEST_HARD_REG_BIT (no_unit_alloc_regs, i)
1423 ? NO_REGS
1424 : ira_allocno_class_translate[REGNO_REG_CLASS (i)]);
1425 #else
1426 int j;
1427 enum reg_class cl;
1428 ira_hard_regno_allocno_class[i] = NO_REGS;
1429 for (j = 0; j < ira_allocno_classes_num; j++)
1430 {
1431 cl = ira_allocno_classes[j];
1432 if (ira_class_hard_reg_index[cl][i] >= 0)
1433 {
1434 ira_hard_regno_allocno_class[i] = cl;
1435 break;
1436 }
1437 }
1438 #endif
1439 }
1440 }
1441
1442
1443
1444 /* Form IRA_REG_CLASS_MAX_NREGS and IRA_REG_CLASS_MIN_NREGS maps. */
1445 static void
setup_reg_class_nregs(void)1446 setup_reg_class_nregs (void)
1447 {
1448 int i, cl, cl2, m;
1449
1450 for (m = 0; m < MAX_MACHINE_MODE; m++)
1451 {
1452 for (cl = 0; cl < N_REG_CLASSES; cl++)
1453 ira_reg_class_max_nregs[cl][m]
1454 = ira_reg_class_min_nregs[cl][m]
1455 = targetm.class_max_nregs ((reg_class_t) cl, (machine_mode) m);
1456 for (cl = 0; cl < N_REG_CLASSES; cl++)
1457 for (i = 0;
1458 (cl2 = alloc_reg_class_subclasses[cl][i]) != LIM_REG_CLASSES;
1459 i++)
1460 if (ira_reg_class_min_nregs[cl2][m]
1461 < ira_reg_class_min_nregs[cl][m])
1462 ira_reg_class_min_nregs[cl][m] = ira_reg_class_min_nregs[cl2][m];
1463 }
1464 }
1465
1466
1467
1468 /* Set up IRA_PROHIBITED_CLASS_MODE_REGS and IRA_CLASS_SINGLETON.
1469 This function is called once IRA_CLASS_HARD_REGS has been initialized. */
1470 static void
setup_prohibited_class_mode_regs(void)1471 setup_prohibited_class_mode_regs (void)
1472 {
1473 int j, k, hard_regno, cl, last_hard_regno, count;
1474
1475 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
1476 {
1477 temp_hard_regset = reg_class_contents[cl] & ~no_unit_alloc_regs;
1478 for (j = 0; j < NUM_MACHINE_MODES; j++)
1479 {
1480 count = 0;
1481 last_hard_regno = -1;
1482 CLEAR_HARD_REG_SET (ira_prohibited_class_mode_regs[cl][j]);
1483 for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1484 {
1485 hard_regno = ira_class_hard_regs[cl][k];
1486 if (!targetm.hard_regno_mode_ok (hard_regno, (machine_mode) j))
1487 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1488 hard_regno);
1489 else if (in_hard_reg_set_p (temp_hard_regset,
1490 (machine_mode) j, hard_regno))
1491 {
1492 last_hard_regno = hard_regno;
1493 count++;
1494 }
1495 }
1496 ira_class_singleton[cl][j] = (count == 1 ? last_hard_regno : -1);
1497 }
1498 }
1499 }
1500
1501 /* Clarify IRA_PROHIBITED_CLASS_MODE_REGS by excluding hard registers
1502 spanning from one register pressure class to another one. It is
1503 called after defining the pressure classes. */
1504 static void
clarify_prohibited_class_mode_regs(void)1505 clarify_prohibited_class_mode_regs (void)
1506 {
1507 int j, k, hard_regno, cl, pclass, nregs;
1508
1509 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
1510 for (j = 0; j < NUM_MACHINE_MODES; j++)
1511 {
1512 CLEAR_HARD_REG_SET (ira_useful_class_mode_regs[cl][j]);
1513 for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1514 {
1515 hard_regno = ira_class_hard_regs[cl][k];
1516 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j], hard_regno))
1517 continue;
1518 nregs = hard_regno_nregs (hard_regno, (machine_mode) j);
1519 if (hard_regno + nregs > FIRST_PSEUDO_REGISTER)
1520 {
1521 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1522 hard_regno);
1523 continue;
1524 }
1525 pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)];
1526 for (nregs-- ;nregs >= 0; nregs--)
1527 if (((enum reg_class) pclass
1528 != ira_pressure_class_translate[REGNO_REG_CLASS
1529 (hard_regno + nregs)]))
1530 {
1531 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1532 hard_regno);
1533 break;
1534 }
1535 if (!TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1536 hard_regno))
1537 add_to_hard_reg_set (&ira_useful_class_mode_regs[cl][j],
1538 (machine_mode) j, hard_regno);
1539 }
1540 }
1541 }
1542
1543 /* Allocate and initialize IRA_REGISTER_MOVE_COST, IRA_MAY_MOVE_IN_COST
1544 and IRA_MAY_MOVE_OUT_COST for MODE. */
1545 void
ira_init_register_move_cost(machine_mode mode)1546 ira_init_register_move_cost (machine_mode mode)
1547 {
1548 static unsigned short last_move_cost[N_REG_CLASSES][N_REG_CLASSES];
1549 bool all_match = true;
1550 unsigned int i, cl1, cl2;
1551 HARD_REG_SET ok_regs;
1552
1553 ira_assert (ira_register_move_cost[mode] == NULL
1554 && ira_may_move_in_cost[mode] == NULL
1555 && ira_may_move_out_cost[mode] == NULL);
1556 CLEAR_HARD_REG_SET (ok_regs);
1557 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1558 if (targetm.hard_regno_mode_ok (i, mode))
1559 SET_HARD_REG_BIT (ok_regs, i);
1560
1561 /* Note that we might be asked about the move costs of modes that
1562 cannot be stored in any hard register, for example if an inline
1563 asm tries to create a register operand with an impossible mode.
1564 We therefore can't assert have_regs_of_mode[mode] here. */
1565 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1566 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1567 {
1568 int cost;
1569 if (!hard_reg_set_intersect_p (ok_regs, reg_class_contents[cl1])
1570 || !hard_reg_set_intersect_p (ok_regs, reg_class_contents[cl2]))
1571 {
1572 if ((ira_reg_class_max_nregs[cl1][mode]
1573 > ira_class_hard_regs_num[cl1])
1574 || (ira_reg_class_max_nregs[cl2][mode]
1575 > ira_class_hard_regs_num[cl2]))
1576 cost = 65535;
1577 else
1578 cost = (ira_memory_move_cost[mode][cl1][0]
1579 + ira_memory_move_cost[mode][cl2][1]) * 2;
1580 }
1581 else
1582 {
1583 cost = register_move_cost (mode, (enum reg_class) cl1,
1584 (enum reg_class) cl2);
1585 ira_assert (cost < 65535);
1586 }
1587 all_match &= (last_move_cost[cl1][cl2] == cost);
1588 last_move_cost[cl1][cl2] = cost;
1589 }
1590 if (all_match && last_mode_for_init_move_cost != -1)
1591 {
1592 ira_register_move_cost[mode]
1593 = ira_register_move_cost[last_mode_for_init_move_cost];
1594 ira_may_move_in_cost[mode]
1595 = ira_may_move_in_cost[last_mode_for_init_move_cost];
1596 ira_may_move_out_cost[mode]
1597 = ira_may_move_out_cost[last_mode_for_init_move_cost];
1598 return;
1599 }
1600 last_mode_for_init_move_cost = mode;
1601 ira_register_move_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1602 ira_may_move_in_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1603 ira_may_move_out_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1604 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1605 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1606 {
1607 int cost;
1608 enum reg_class *p1, *p2;
1609
1610 if (last_move_cost[cl1][cl2] == 65535)
1611 {
1612 ira_register_move_cost[mode][cl1][cl2] = 65535;
1613 ira_may_move_in_cost[mode][cl1][cl2] = 65535;
1614 ira_may_move_out_cost[mode][cl1][cl2] = 65535;
1615 }
1616 else
1617 {
1618 cost = last_move_cost[cl1][cl2];
1619
1620 for (p2 = ®_class_subclasses[cl2][0];
1621 *p2 != LIM_REG_CLASSES; p2++)
1622 if (ira_class_hard_regs_num[*p2] > 0
1623 && (ira_reg_class_max_nregs[*p2][mode]
1624 <= ira_class_hard_regs_num[*p2]))
1625 cost = MAX (cost, ira_register_move_cost[mode][cl1][*p2]);
1626
1627 for (p1 = ®_class_subclasses[cl1][0];
1628 *p1 != LIM_REG_CLASSES; p1++)
1629 if (ira_class_hard_regs_num[*p1] > 0
1630 && (ira_reg_class_max_nregs[*p1][mode]
1631 <= ira_class_hard_regs_num[*p1]))
1632 cost = MAX (cost, ira_register_move_cost[mode][*p1][cl2]);
1633
1634 ira_assert (cost <= 65535);
1635 ira_register_move_cost[mode][cl1][cl2] = cost;
1636
1637 if (ira_class_subset_p[cl1][cl2])
1638 ira_may_move_in_cost[mode][cl1][cl2] = 0;
1639 else
1640 ira_may_move_in_cost[mode][cl1][cl2] = cost;
1641
1642 if (ira_class_subset_p[cl2][cl1])
1643 ira_may_move_out_cost[mode][cl1][cl2] = 0;
1644 else
1645 ira_may_move_out_cost[mode][cl1][cl2] = cost;
1646 }
1647 }
1648 }
1649
1650
1651
1652 /* This is called once during compiler work. It sets up
1653 different arrays whose values don't depend on the compiled
1654 function. */
1655 void
ira_init_once(void)1656 ira_init_once (void)
1657 {
1658 ira_init_costs_once ();
1659 lra_init_once ();
1660
1661 ira_use_lra_p = targetm.lra_p ();
1662 }
1663
1664 /* Free ira_max_register_move_cost, ira_may_move_in_cost and
1665 ira_may_move_out_cost for each mode. */
1666 void
free_register_move_costs(void)1667 target_ira_int::free_register_move_costs (void)
1668 {
1669 int mode, i;
1670
1671 /* Reset move_cost and friends, making sure we only free shared
1672 table entries once. */
1673 for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1674 if (x_ira_register_move_cost[mode])
1675 {
1676 for (i = 0;
1677 i < mode && (x_ira_register_move_cost[i]
1678 != x_ira_register_move_cost[mode]);
1679 i++)
1680 ;
1681 if (i == mode)
1682 {
1683 free (x_ira_register_move_cost[mode]);
1684 free (x_ira_may_move_in_cost[mode]);
1685 free (x_ira_may_move_out_cost[mode]);
1686 }
1687 }
1688 memset (x_ira_register_move_cost, 0, sizeof x_ira_register_move_cost);
1689 memset (x_ira_may_move_in_cost, 0, sizeof x_ira_may_move_in_cost);
1690 memset (x_ira_may_move_out_cost, 0, sizeof x_ira_may_move_out_cost);
1691 last_mode_for_init_move_cost = -1;
1692 }
1693
~target_ira_int()1694 target_ira_int::~target_ira_int ()
1695 {
1696 free_ira_costs ();
1697 free_register_move_costs ();
1698 }
1699
1700 /* This is called every time when register related information is
1701 changed. */
1702 void
ira_init(void)1703 ira_init (void)
1704 {
1705 this_target_ira_int->free_register_move_costs ();
1706 setup_reg_mode_hard_regset ();
1707 setup_alloc_regs (flag_omit_frame_pointer != 0);
1708 setup_class_subset_and_memory_move_costs ();
1709 setup_reg_class_nregs ();
1710 setup_prohibited_class_mode_regs ();
1711 find_reg_classes ();
1712 clarify_prohibited_class_mode_regs ();
1713 setup_hard_regno_aclass ();
1714 ira_init_costs ();
1715 }
1716
1717
1718 #define ira_prohibited_mode_move_regs_initialized_p \
1719 (this_target_ira_int->x_ira_prohibited_mode_move_regs_initialized_p)
1720
1721 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS. */
1722 static void
setup_prohibited_mode_move_regs(void)1723 setup_prohibited_mode_move_regs (void)
1724 {
1725 int i, j;
1726 rtx test_reg1, test_reg2, move_pat;
1727 rtx_insn *move_insn;
1728
1729 if (ira_prohibited_mode_move_regs_initialized_p)
1730 return;
1731 ira_prohibited_mode_move_regs_initialized_p = true;
1732 test_reg1 = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
1733 test_reg2 = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 2);
1734 move_pat = gen_rtx_SET (test_reg1, test_reg2);
1735 move_insn = gen_rtx_INSN (VOIDmode, 0, 0, 0, move_pat, 0, -1, 0);
1736 for (i = 0; i < NUM_MACHINE_MODES; i++)
1737 {
1738 SET_HARD_REG_SET (ira_prohibited_mode_move_regs[i]);
1739 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1740 {
1741 if (!targetm.hard_regno_mode_ok (j, (machine_mode) i))
1742 continue;
1743 set_mode_and_regno (test_reg1, (machine_mode) i, j);
1744 set_mode_and_regno (test_reg2, (machine_mode) i, j);
1745 INSN_CODE (move_insn) = -1;
1746 recog_memoized (move_insn);
1747 if (INSN_CODE (move_insn) < 0)
1748 continue;
1749 extract_insn (move_insn);
1750 /* We don't know whether the move will be in code that is optimized
1751 for size or speed, so consider all enabled alternatives. */
1752 if (! constrain_operands (1, get_enabled_alternatives (move_insn)))
1753 continue;
1754 CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs[i], j);
1755 }
1756 }
1757 }
1758
1759
1760
1761 /* Extract INSN and return the set of alternatives that we should consider.
1762 This excludes any alternatives whose constraints are obviously impossible
1763 to meet (e.g. because the constraint requires a constant and the operand
1764 is nonconstant). It also excludes alternatives that are bound to need
1765 a spill or reload, as long as we have other alternatives that match
1766 exactly. */
1767 alternative_mask
ira_setup_alts(rtx_insn * insn)1768 ira_setup_alts (rtx_insn *insn)
1769 {
1770 int nop, nalt;
1771 bool curr_swapped;
1772 const char *p;
1773 int commutative = -1;
1774
1775 extract_insn (insn);
1776 preprocess_constraints (insn);
1777 alternative_mask preferred = get_preferred_alternatives (insn);
1778 alternative_mask alts = 0;
1779 alternative_mask exact_alts = 0;
1780 /* Check that the hard reg set is enough for holding all
1781 alternatives. It is hard to imagine the situation when the
1782 assertion is wrong. */
1783 ira_assert (recog_data.n_alternatives
1784 <= (int) MAX (sizeof (HARD_REG_ELT_TYPE) * CHAR_BIT,
1785 FIRST_PSEUDO_REGISTER));
1786 for (nop = 0; nop < recog_data.n_operands; nop++)
1787 if (recog_data.constraints[nop][0] == '%')
1788 {
1789 commutative = nop;
1790 break;
1791 }
1792 for (curr_swapped = false;; curr_swapped = true)
1793 {
1794 for (nalt = 0; nalt < recog_data.n_alternatives; nalt++)
1795 {
1796 if (!TEST_BIT (preferred, nalt) || TEST_BIT (exact_alts, nalt))
1797 continue;
1798
1799 const operand_alternative *op_alt
1800 = &recog_op_alt[nalt * recog_data.n_operands];
1801 int this_reject = 0;
1802 for (nop = 0; nop < recog_data.n_operands; nop++)
1803 {
1804 int c, len;
1805
1806 this_reject += op_alt[nop].reject;
1807
1808 rtx op = recog_data.operand[nop];
1809 p = op_alt[nop].constraint;
1810 if (*p == 0 || *p == ',')
1811 continue;
1812
1813 bool win_p = false;
1814 do
1815 switch (c = *p, len = CONSTRAINT_LEN (c, p), c)
1816 {
1817 case '#':
1818 case ',':
1819 c = '\0';
1820 /* FALLTHRU */
1821 case '\0':
1822 len = 0;
1823 break;
1824
1825 case '%':
1826 /* The commutative modifier is handled above. */
1827 break;
1828
1829 case '0': case '1': case '2': case '3': case '4':
1830 case '5': case '6': case '7': case '8': case '9':
1831 {
1832 char *end;
1833 unsigned long dup = strtoul (p, &end, 10);
1834 rtx other = recog_data.operand[dup];
1835 len = end - p;
1836 if (MEM_P (other)
1837 ? rtx_equal_p (other, op)
1838 : REG_P (op) || SUBREG_P (op))
1839 goto op_success;
1840 win_p = true;
1841 }
1842 break;
1843
1844 case 'g':
1845 goto op_success;
1846 break;
1847
1848 default:
1849 {
1850 enum constraint_num cn = lookup_constraint (p);
1851 rtx mem = NULL;
1852 switch (get_constraint_type (cn))
1853 {
1854 case CT_REGISTER:
1855 if (reg_class_for_constraint (cn) != NO_REGS)
1856 {
1857 if (REG_P (op) || SUBREG_P (op))
1858 goto op_success;
1859 win_p = true;
1860 }
1861 break;
1862
1863 case CT_CONST_INT:
1864 if (CONST_INT_P (op)
1865 && (insn_const_int_ok_for_constraint
1866 (INTVAL (op), cn)))
1867 goto op_success;
1868 break;
1869
1870 case CT_ADDRESS:
1871 goto op_success;
1872
1873 case CT_MEMORY:
1874 case CT_RELAXED_MEMORY:
1875 mem = op;
1876 /* Fall through. */
1877 case CT_SPECIAL_MEMORY:
1878 if (!mem)
1879 mem = extract_mem_from_operand (op);
1880 if (MEM_P (mem))
1881 goto op_success;
1882 win_p = true;
1883 break;
1884
1885 case CT_FIXED_FORM:
1886 if (constraint_satisfied_p (op, cn))
1887 goto op_success;
1888 break;
1889 }
1890 break;
1891 }
1892 }
1893 while (p += len, c);
1894 if (!win_p)
1895 break;
1896 /* We can make the alternative match by spilling a register
1897 to memory or loading something into a register. Count a
1898 cost of one reload (the equivalent of the '?' constraint). */
1899 this_reject += 6;
1900 op_success:
1901 ;
1902 }
1903
1904 if (nop >= recog_data.n_operands)
1905 {
1906 alts |= ALTERNATIVE_BIT (nalt);
1907 if (this_reject == 0)
1908 exact_alts |= ALTERNATIVE_BIT (nalt);
1909 }
1910 }
1911 if (commutative < 0)
1912 break;
1913 /* Swap forth and back to avoid changing recog_data. */
1914 std::swap (recog_data.operand[commutative],
1915 recog_data.operand[commutative + 1]);
1916 if (curr_swapped)
1917 break;
1918 }
1919 return exact_alts ? exact_alts : alts;
1920 }
1921
1922 /* Return the number of the output non-early clobber operand which
1923 should be the same in any case as operand with number OP_NUM (or
1924 negative value if there is no such operand). ALTS is the mask
1925 of alternatives that we should consider. */
1926 int
ira_get_dup_out_num(int op_num,alternative_mask alts)1927 ira_get_dup_out_num (int op_num, alternative_mask alts)
1928 {
1929 int curr_alt, c, original;
1930 bool ignore_p, use_commut_op_p;
1931 const char *str;
1932
1933 if (op_num < 0 || recog_data.n_alternatives == 0)
1934 return -1;
1935 /* We should find duplications only for input operands. */
1936 if (recog_data.operand_type[op_num] != OP_IN)
1937 return -1;
1938 str = recog_data.constraints[op_num];
1939 use_commut_op_p = false;
1940 for (;;)
1941 {
1942 rtx op = recog_data.operand[op_num];
1943
1944 for (curr_alt = 0, ignore_p = !TEST_BIT (alts, curr_alt),
1945 original = -1;;)
1946 {
1947 c = *str;
1948 if (c == '\0')
1949 break;
1950 if (c == '#')
1951 ignore_p = true;
1952 else if (c == ',')
1953 {
1954 curr_alt++;
1955 ignore_p = !TEST_BIT (alts, curr_alt);
1956 }
1957 else if (! ignore_p)
1958 switch (c)
1959 {
1960 case 'g':
1961 goto fail;
1962 default:
1963 {
1964 enum constraint_num cn = lookup_constraint (str);
1965 enum reg_class cl = reg_class_for_constraint (cn);
1966 if (cl != NO_REGS
1967 && !targetm.class_likely_spilled_p (cl))
1968 goto fail;
1969 if (constraint_satisfied_p (op, cn))
1970 goto fail;
1971 break;
1972 }
1973
1974 case '0': case '1': case '2': case '3': case '4':
1975 case '5': case '6': case '7': case '8': case '9':
1976 {
1977 char *end;
1978 int n = (int) strtoul (str, &end, 10);
1979 str = end;
1980 if (original != -1 && original != n)
1981 goto fail;
1982 original = n;
1983 continue;
1984 }
1985 }
1986 str += CONSTRAINT_LEN (c, str);
1987 }
1988 if (original == -1)
1989 goto fail;
1990 if (recog_data.operand_type[original] == OP_OUT)
1991 return original;
1992 fail:
1993 if (use_commut_op_p)
1994 break;
1995 use_commut_op_p = true;
1996 if (recog_data.constraints[op_num][0] == '%')
1997 str = recog_data.constraints[op_num + 1];
1998 else if (op_num > 0 && recog_data.constraints[op_num - 1][0] == '%')
1999 str = recog_data.constraints[op_num - 1];
2000 else
2001 break;
2002 }
2003 return -1;
2004 }
2005
2006
2007
2008 /* Search forward to see if the source register of a copy insn dies
2009 before either it or the destination register is modified, but don't
2010 scan past the end of the basic block. If so, we can replace the
2011 source with the destination and let the source die in the copy
2012 insn.
2013
2014 This will reduce the number of registers live in that range and may
2015 enable the destination and the source coalescing, thus often saving
2016 one register in addition to a register-register copy. */
2017
2018 static void
decrease_live_ranges_number(void)2019 decrease_live_ranges_number (void)
2020 {
2021 basic_block bb;
2022 rtx_insn *insn;
2023 rtx set, src, dest, dest_death, note;
2024 rtx_insn *p, *q;
2025 int sregno, dregno;
2026
2027 if (! flag_expensive_optimizations)
2028 return;
2029
2030 if (ira_dump_file)
2031 fprintf (ira_dump_file, "Starting decreasing number of live ranges...\n");
2032
2033 FOR_EACH_BB_FN (bb, cfun)
2034 FOR_BB_INSNS (bb, insn)
2035 {
2036 set = single_set (insn);
2037 if (! set)
2038 continue;
2039 src = SET_SRC (set);
2040 dest = SET_DEST (set);
2041 if (! REG_P (src) || ! REG_P (dest)
2042 || find_reg_note (insn, REG_DEAD, src))
2043 continue;
2044 sregno = REGNO (src);
2045 dregno = REGNO (dest);
2046
2047 /* We don't want to mess with hard regs if register classes
2048 are small. */
2049 if (sregno == dregno
2050 || (targetm.small_register_classes_for_mode_p (GET_MODE (src))
2051 && (sregno < FIRST_PSEUDO_REGISTER
2052 || dregno < FIRST_PSEUDO_REGISTER))
2053 /* We don't see all updates to SP if they are in an
2054 auto-inc memory reference, so we must disallow this
2055 optimization on them. */
2056 || sregno == STACK_POINTER_REGNUM
2057 || dregno == STACK_POINTER_REGNUM)
2058 continue;
2059
2060 dest_death = NULL_RTX;
2061
2062 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
2063 {
2064 if (! INSN_P (p))
2065 continue;
2066 if (BLOCK_FOR_INSN (p) != bb)
2067 break;
2068
2069 if (reg_set_p (src, p) || reg_set_p (dest, p)
2070 /* If SRC is an asm-declared register, it must not be
2071 replaced in any asm. Unfortunately, the REG_EXPR
2072 tree for the asm variable may be absent in the SRC
2073 rtx, so we can't check the actual register
2074 declaration easily (the asm operand will have it,
2075 though). To avoid complicating the test for a rare
2076 case, we just don't perform register replacement
2077 for a hard reg mentioned in an asm. */
2078 || (sregno < FIRST_PSEUDO_REGISTER
2079 && asm_noperands (PATTERN (p)) >= 0
2080 && reg_overlap_mentioned_p (src, PATTERN (p)))
2081 /* Don't change hard registers used by a call. */
2082 || (CALL_P (p) && sregno < FIRST_PSEUDO_REGISTER
2083 && find_reg_fusage (p, USE, src))
2084 /* Don't change a USE of a register. */
2085 || (GET_CODE (PATTERN (p)) == USE
2086 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
2087 break;
2088
2089 /* See if all of SRC dies in P. This test is slightly
2090 more conservative than it needs to be. */
2091 if ((note = find_regno_note (p, REG_DEAD, sregno))
2092 && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
2093 {
2094 int failed = 0;
2095
2096 /* We can do the optimization. Scan forward from INSN
2097 again, replacing regs as we go. Set FAILED if a
2098 replacement can't be done. In that case, we can't
2099 move the death note for SRC. This should be
2100 rare. */
2101
2102 /* Set to stop at next insn. */
2103 for (q = next_real_insn (insn);
2104 q != next_real_insn (p);
2105 q = next_real_insn (q))
2106 {
2107 if (reg_overlap_mentioned_p (src, PATTERN (q)))
2108 {
2109 /* If SRC is a hard register, we might miss
2110 some overlapping registers with
2111 validate_replace_rtx, so we would have to
2112 undo it. We can't if DEST is present in
2113 the insn, so fail in that combination of
2114 cases. */
2115 if (sregno < FIRST_PSEUDO_REGISTER
2116 && reg_mentioned_p (dest, PATTERN (q)))
2117 failed = 1;
2118
2119 /* Attempt to replace all uses. */
2120 else if (!validate_replace_rtx (src, dest, q))
2121 failed = 1;
2122
2123 /* If this succeeded, but some part of the
2124 register is still present, undo the
2125 replacement. */
2126 else if (sregno < FIRST_PSEUDO_REGISTER
2127 && reg_overlap_mentioned_p (src, PATTERN (q)))
2128 {
2129 validate_replace_rtx (dest, src, q);
2130 failed = 1;
2131 }
2132 }
2133
2134 /* If DEST dies here, remove the death note and
2135 save it for later. Make sure ALL of DEST dies
2136 here; again, this is overly conservative. */
2137 if (! dest_death
2138 && (dest_death = find_regno_note (q, REG_DEAD, dregno)))
2139 {
2140 if (GET_MODE (XEXP (dest_death, 0)) == GET_MODE (dest))
2141 remove_note (q, dest_death);
2142 else
2143 {
2144 failed = 1;
2145 dest_death = 0;
2146 }
2147 }
2148 }
2149
2150 if (! failed)
2151 {
2152 /* Move death note of SRC from P to INSN. */
2153 remove_note (p, note);
2154 XEXP (note, 1) = REG_NOTES (insn);
2155 REG_NOTES (insn) = note;
2156 }
2157
2158 /* DEST is also dead if INSN has a REG_UNUSED note for
2159 DEST. */
2160 if (! dest_death
2161 && (dest_death
2162 = find_regno_note (insn, REG_UNUSED, dregno)))
2163 {
2164 PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
2165 remove_note (insn, dest_death);
2166 }
2167
2168 /* Put death note of DEST on P if we saw it die. */
2169 if (dest_death)
2170 {
2171 XEXP (dest_death, 1) = REG_NOTES (p);
2172 REG_NOTES (p) = dest_death;
2173 }
2174 break;
2175 }
2176
2177 /* If SRC is a hard register which is set or killed in
2178 some other way, we can't do this optimization. */
2179 else if (sregno < FIRST_PSEUDO_REGISTER && dead_or_set_p (p, src))
2180 break;
2181 }
2182 }
2183 }
2184
2185
2186
2187 /* Return nonzero if REGNO is a particularly bad choice for reloading X. */
2188 static bool
ira_bad_reload_regno_1(int regno,rtx x)2189 ira_bad_reload_regno_1 (int regno, rtx x)
2190 {
2191 int x_regno, n, i;
2192 ira_allocno_t a;
2193 enum reg_class pref;
2194
2195 /* We only deal with pseudo regs. */
2196 if (! x || GET_CODE (x) != REG)
2197 return false;
2198
2199 x_regno = REGNO (x);
2200 if (x_regno < FIRST_PSEUDO_REGISTER)
2201 return false;
2202
2203 /* If the pseudo prefers REGNO explicitly, then do not consider
2204 REGNO a bad spill choice. */
2205 pref = reg_preferred_class (x_regno);
2206 if (reg_class_size[pref] == 1)
2207 return !TEST_HARD_REG_BIT (reg_class_contents[pref], regno);
2208
2209 /* If the pseudo conflicts with REGNO, then we consider REGNO a
2210 poor choice for a reload regno. */
2211 a = ira_regno_allocno_map[x_regno];
2212 n = ALLOCNO_NUM_OBJECTS (a);
2213 for (i = 0; i < n; i++)
2214 {
2215 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2216 if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), regno))
2217 return true;
2218 }
2219 return false;
2220 }
2221
2222 /* Return nonzero if REGNO is a particularly bad choice for reloading
2223 IN or OUT. */
2224 bool
ira_bad_reload_regno(int regno,rtx in,rtx out)2225 ira_bad_reload_regno (int regno, rtx in, rtx out)
2226 {
2227 return (ira_bad_reload_regno_1 (regno, in)
2228 || ira_bad_reload_regno_1 (regno, out));
2229 }
2230
2231 /* Add register clobbers from asm statements. */
2232 static void
compute_regs_asm_clobbered(void)2233 compute_regs_asm_clobbered (void)
2234 {
2235 basic_block bb;
2236
2237 FOR_EACH_BB_FN (bb, cfun)
2238 {
2239 rtx_insn *insn;
2240 FOR_BB_INSNS_REVERSE (bb, insn)
2241 {
2242 df_ref def;
2243
2244 if (NONDEBUG_INSN_P (insn) && asm_noperands (PATTERN (insn)) >= 0)
2245 FOR_EACH_INSN_DEF (def, insn)
2246 {
2247 unsigned int dregno = DF_REF_REGNO (def);
2248 if (HARD_REGISTER_NUM_P (dregno))
2249 add_to_hard_reg_set (&crtl->asm_clobbers,
2250 GET_MODE (DF_REF_REAL_REG (def)),
2251 dregno);
2252 }
2253 }
2254 }
2255 }
2256
2257
2258 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and
2259 REGS_EVER_LIVE. */
2260 void
ira_setup_eliminable_regset(void)2261 ira_setup_eliminable_regset (void)
2262 {
2263 int i;
2264 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
2265 int fp_reg_count = hard_regno_nregs (HARD_FRAME_POINTER_REGNUM, Pmode);
2266
2267 /* Setup is_leaf as frame_pointer_required may use it. This function
2268 is called by sched_init before ira if scheduling is enabled. */
2269 crtl->is_leaf = leaf_function_p ();
2270
2271 /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
2272 sp for alloca. So we can't eliminate the frame pointer in that
2273 case. At some point, we should improve this by emitting the
2274 sp-adjusting insns for this case. */
2275 frame_pointer_needed
2276 = (! flag_omit_frame_pointer
2277 || (cfun->calls_alloca && EXIT_IGNORE_STACK)
2278 /* We need the frame pointer to catch stack overflow exceptions if
2279 the stack pointer is moving (as for the alloca case just above). */
2280 || (STACK_CHECK_MOVING_SP
2281 && flag_stack_check
2282 && flag_exceptions
2283 && cfun->can_throw_non_call_exceptions)
2284 || crtl->accesses_prior_frames
2285 || (SUPPORTS_STACK_ALIGNMENT && crtl->stack_realign_needed)
2286 || targetm.frame_pointer_required ());
2287
2288 /* The chance that FRAME_POINTER_NEEDED is changed from inspecting
2289 RTL is very small. So if we use frame pointer for RA and RTL
2290 actually prevents this, we will spill pseudos assigned to the
2291 frame pointer in LRA. */
2292
2293 if (frame_pointer_needed)
2294 for (i = 0; i < fp_reg_count; i++)
2295 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM + i, true);
2296
2297 ira_no_alloc_regs = no_unit_alloc_regs;
2298 CLEAR_HARD_REG_SET (eliminable_regset);
2299
2300 compute_regs_asm_clobbered ();
2301
2302 /* Build the regset of all eliminable registers and show we can't
2303 use those that we already know won't be eliminated. */
2304 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
2305 {
2306 bool cannot_elim
2307 = (! targetm.can_eliminate (eliminables[i].from, eliminables[i].to)
2308 || (eliminables[i].to == STACK_POINTER_REGNUM && frame_pointer_needed));
2309
2310 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, eliminables[i].from))
2311 {
2312 SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
2313
2314 if (cannot_elim)
2315 SET_HARD_REG_BIT (ira_no_alloc_regs, eliminables[i].from);
2316 }
2317 else if (cannot_elim)
2318 error ("%s cannot be used in %<asm%> here",
2319 reg_names[eliminables[i].from]);
2320 else
2321 df_set_regs_ever_live (eliminables[i].from, true);
2322 }
2323 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
2324 {
2325 for (i = 0; i < fp_reg_count; i++)
2326 if (global_regs[HARD_FRAME_POINTER_REGNUM + i])
2327 /* Nothing to do: the register is already treated as live
2328 where appropriate, and cannot be eliminated. */
2329 ;
2330 else if (!TEST_HARD_REG_BIT (crtl->asm_clobbers,
2331 HARD_FRAME_POINTER_REGNUM + i))
2332 {
2333 SET_HARD_REG_BIT (eliminable_regset,
2334 HARD_FRAME_POINTER_REGNUM + i);
2335 if (frame_pointer_needed)
2336 SET_HARD_REG_BIT (ira_no_alloc_regs,
2337 HARD_FRAME_POINTER_REGNUM + i);
2338 }
2339 else if (frame_pointer_needed)
2340 error ("%s cannot be used in %<asm%> here",
2341 reg_names[HARD_FRAME_POINTER_REGNUM + i]);
2342 else
2343 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM + i, true);
2344 }
2345 }
2346
2347
2348
2349 /* Vector of substitutions of register numbers,
2350 used to map pseudo regs into hardware regs.
2351 This is set up as a result of register allocation.
2352 Element N is the hard reg assigned to pseudo reg N,
2353 or is -1 if no hard reg was assigned.
2354 If N is a hard reg number, element N is N. */
2355 short *reg_renumber;
2356
2357 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
2358 the allocation found by IRA. */
2359 static void
setup_reg_renumber(void)2360 setup_reg_renumber (void)
2361 {
2362 int regno, hard_regno;
2363 ira_allocno_t a;
2364 ira_allocno_iterator ai;
2365
2366 caller_save_needed = 0;
2367 FOR_EACH_ALLOCNO (a, ai)
2368 {
2369 if (ira_use_lra_p && ALLOCNO_CAP_MEMBER (a) != NULL)
2370 continue;
2371 /* There are no caps at this point. */
2372 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2373 if (! ALLOCNO_ASSIGNED_P (a))
2374 /* It can happen if A is not referenced but partially anticipated
2375 somewhere in a region. */
2376 ALLOCNO_ASSIGNED_P (a) = true;
2377 ira_free_allocno_updated_costs (a);
2378 hard_regno = ALLOCNO_HARD_REGNO (a);
2379 regno = ALLOCNO_REGNO (a);
2380 reg_renumber[regno] = (hard_regno < 0 ? -1 : hard_regno);
2381 if (hard_regno >= 0)
2382 {
2383 int i, nwords;
2384 enum reg_class pclass;
2385 ira_object_t obj;
2386
2387 pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)];
2388 nwords = ALLOCNO_NUM_OBJECTS (a);
2389 for (i = 0; i < nwords; i++)
2390 {
2391 obj = ALLOCNO_OBJECT (a, i);
2392 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj)
2393 |= ~reg_class_contents[pclass];
2394 }
2395 if (ira_need_caller_save_p (a, hard_regno))
2396 {
2397 ira_assert (!optimize || flag_caller_saves
2398 || (ALLOCNO_CALLS_CROSSED_NUM (a)
2399 == ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a))
2400 || regno >= ira_reg_equiv_len
2401 || ira_equiv_no_lvalue_p (regno));
2402 caller_save_needed = 1;
2403 }
2404 }
2405 }
2406 }
2407
2408 /* Set up allocno assignment flags for further allocation
2409 improvements. */
2410 static void
setup_allocno_assignment_flags(void)2411 setup_allocno_assignment_flags (void)
2412 {
2413 int hard_regno;
2414 ira_allocno_t a;
2415 ira_allocno_iterator ai;
2416
2417 FOR_EACH_ALLOCNO (a, ai)
2418 {
2419 if (! ALLOCNO_ASSIGNED_P (a))
2420 /* It can happen if A is not referenced but partially anticipated
2421 somewhere in a region. */
2422 ira_free_allocno_updated_costs (a);
2423 hard_regno = ALLOCNO_HARD_REGNO (a);
2424 /* Don't assign hard registers to allocnos which are destination
2425 of removed store at the end of loop. It has no sense to keep
2426 the same value in different hard registers. It is also
2427 impossible to assign hard registers correctly to such
2428 allocnos because the cost info and info about intersected
2429 calls are incorrect for them. */
2430 ALLOCNO_ASSIGNED_P (a) = (hard_regno >= 0
2431 || ALLOCNO_EMIT_DATA (a)->mem_optimized_dest_p
2432 || (ALLOCNO_MEMORY_COST (a)
2433 - ALLOCNO_CLASS_COST (a)) < 0);
2434 ira_assert
2435 (hard_regno < 0
2436 || ira_hard_reg_in_set_p (hard_regno, ALLOCNO_MODE (a),
2437 reg_class_contents[ALLOCNO_CLASS (a)]));
2438 }
2439 }
2440
2441 /* Evaluate overall allocation cost and the costs for using hard
2442 registers and memory for allocnos. */
2443 static void
calculate_allocation_cost(void)2444 calculate_allocation_cost (void)
2445 {
2446 int hard_regno, cost;
2447 ira_allocno_t a;
2448 ira_allocno_iterator ai;
2449
2450 ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
2451 FOR_EACH_ALLOCNO (a, ai)
2452 {
2453 hard_regno = ALLOCNO_HARD_REGNO (a);
2454 ira_assert (hard_regno < 0
2455 || (ira_hard_reg_in_set_p
2456 (hard_regno, ALLOCNO_MODE (a),
2457 reg_class_contents[ALLOCNO_CLASS (a)])));
2458 if (hard_regno < 0)
2459 {
2460 cost = ALLOCNO_MEMORY_COST (a);
2461 ira_mem_cost += cost;
2462 }
2463 else if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
2464 {
2465 cost = (ALLOCNO_HARD_REG_COSTS (a)
2466 [ira_class_hard_reg_index
2467 [ALLOCNO_CLASS (a)][hard_regno]]);
2468 ira_reg_cost += cost;
2469 }
2470 else
2471 {
2472 cost = ALLOCNO_CLASS_COST (a);
2473 ira_reg_cost += cost;
2474 }
2475 ira_overall_cost += cost;
2476 }
2477
2478 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2479 {
2480 fprintf (ira_dump_file,
2481 "+++Costs: overall %" PRId64
2482 ", reg %" PRId64
2483 ", mem %" PRId64
2484 ", ld %" PRId64
2485 ", st %" PRId64
2486 ", move %" PRId64,
2487 ira_overall_cost, ira_reg_cost, ira_mem_cost,
2488 ira_load_cost, ira_store_cost, ira_shuffle_cost);
2489 fprintf (ira_dump_file, "\n+++ move loops %d, new jumps %d\n",
2490 ira_move_loops_num, ira_additional_jumps_num);
2491 }
2492
2493 }
2494
2495 #ifdef ENABLE_IRA_CHECKING
2496 /* Check the correctness of the allocation. We do need this because
2497 of complicated code to transform more one region internal
2498 representation into one region representation. */
2499 static void
check_allocation(void)2500 check_allocation (void)
2501 {
2502 ira_allocno_t a;
2503 int hard_regno, nregs, conflict_nregs;
2504 ira_allocno_iterator ai;
2505
2506 FOR_EACH_ALLOCNO (a, ai)
2507 {
2508 int n = ALLOCNO_NUM_OBJECTS (a);
2509 int i;
2510
2511 if (ALLOCNO_CAP_MEMBER (a) != NULL
2512 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
2513 continue;
2514 nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (a));
2515 if (nregs == 1)
2516 /* We allocated a single hard register. */
2517 n = 1;
2518 else if (n > 1)
2519 /* We allocated multiple hard registers, and we will test
2520 conflicts in a granularity of single hard regs. */
2521 nregs = 1;
2522
2523 for (i = 0; i < n; i++)
2524 {
2525 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2526 ira_object_t conflict_obj;
2527 ira_object_conflict_iterator oci;
2528 int this_regno = hard_regno;
2529 if (n > 1)
2530 {
2531 if (REG_WORDS_BIG_ENDIAN)
2532 this_regno += n - i - 1;
2533 else
2534 this_regno += i;
2535 }
2536 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2537 {
2538 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2539 int conflict_hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
2540 if (conflict_hard_regno < 0)
2541 continue;
2542
2543 conflict_nregs = hard_regno_nregs (conflict_hard_regno,
2544 ALLOCNO_MODE (conflict_a));
2545
2546 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1
2547 && conflict_nregs == ALLOCNO_NUM_OBJECTS (conflict_a))
2548 {
2549 if (REG_WORDS_BIG_ENDIAN)
2550 conflict_hard_regno += (ALLOCNO_NUM_OBJECTS (conflict_a)
2551 - OBJECT_SUBWORD (conflict_obj) - 1);
2552 else
2553 conflict_hard_regno += OBJECT_SUBWORD (conflict_obj);
2554 conflict_nregs = 1;
2555 }
2556
2557 if ((conflict_hard_regno <= this_regno
2558 && this_regno < conflict_hard_regno + conflict_nregs)
2559 || (this_regno <= conflict_hard_regno
2560 && conflict_hard_regno < this_regno + nregs))
2561 {
2562 fprintf (stderr, "bad allocation for %d and %d\n",
2563 ALLOCNO_REGNO (a), ALLOCNO_REGNO (conflict_a));
2564 gcc_unreachable ();
2565 }
2566 }
2567 }
2568 }
2569 }
2570 #endif
2571
2572 /* Allocate REG_EQUIV_INIT. Set up it from IRA_REG_EQUIV which should
2573 be already calculated. */
2574 static void
setup_reg_equiv_init(void)2575 setup_reg_equiv_init (void)
2576 {
2577 int i;
2578 int max_regno = max_reg_num ();
2579
2580 for (i = 0; i < max_regno; i++)
2581 reg_equiv_init (i) = ira_reg_equiv[i].init_insns;
2582 }
2583
2584 /* Update equiv regno from movement of FROM_REGNO to TO_REGNO. INSNS
2585 are insns which were generated for such movement. It is assumed
2586 that FROM_REGNO and TO_REGNO always have the same value at the
2587 point of any move containing such registers. This function is used
2588 to update equiv info for register shuffles on the region borders
2589 and for caller save/restore insns. */
2590 void
ira_update_equiv_info_by_shuffle_insn(int to_regno,int from_regno,rtx_insn * insns)2591 ira_update_equiv_info_by_shuffle_insn (int to_regno, int from_regno, rtx_insn *insns)
2592 {
2593 rtx_insn *insn;
2594 rtx x, note;
2595
2596 if (! ira_reg_equiv[from_regno].defined_p
2597 && (! ira_reg_equiv[to_regno].defined_p
2598 || ((x = ira_reg_equiv[to_regno].memory) != NULL_RTX
2599 && ! MEM_READONLY_P (x))))
2600 return;
2601 insn = insns;
2602 if (NEXT_INSN (insn) != NULL_RTX)
2603 {
2604 if (! ira_reg_equiv[to_regno].defined_p)
2605 {
2606 ira_assert (ira_reg_equiv[to_regno].init_insns == NULL_RTX);
2607 return;
2608 }
2609 ira_reg_equiv[to_regno].defined_p = false;
2610 ira_reg_equiv[to_regno].memory
2611 = ira_reg_equiv[to_regno].constant
2612 = ira_reg_equiv[to_regno].invariant
2613 = ira_reg_equiv[to_regno].init_insns = NULL;
2614 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2615 fprintf (ira_dump_file,
2616 " Invalidating equiv info for reg %d\n", to_regno);
2617 return;
2618 }
2619 /* It is possible that FROM_REGNO still has no equivalence because
2620 in shuffles to_regno<-from_regno and from_regno<-to_regno the 2nd
2621 insn was not processed yet. */
2622 if (ira_reg_equiv[from_regno].defined_p)
2623 {
2624 ira_reg_equiv[to_regno].defined_p = true;
2625 if ((x = ira_reg_equiv[from_regno].memory) != NULL_RTX)
2626 {
2627 ira_assert (ira_reg_equiv[from_regno].invariant == NULL_RTX
2628 && ira_reg_equiv[from_regno].constant == NULL_RTX);
2629 ira_assert (ira_reg_equiv[to_regno].memory == NULL_RTX
2630 || rtx_equal_p (ira_reg_equiv[to_regno].memory, x));
2631 ira_reg_equiv[to_regno].memory = x;
2632 if (! MEM_READONLY_P (x))
2633 /* We don't add the insn to insn init list because memory
2634 equivalence is just to say what memory is better to use
2635 when the pseudo is spilled. */
2636 return;
2637 }
2638 else if ((x = ira_reg_equiv[from_regno].constant) != NULL_RTX)
2639 {
2640 ira_assert (ira_reg_equiv[from_regno].invariant == NULL_RTX);
2641 ira_assert (ira_reg_equiv[to_regno].constant == NULL_RTX
2642 || rtx_equal_p (ira_reg_equiv[to_regno].constant, x));
2643 ira_reg_equiv[to_regno].constant = x;
2644 }
2645 else
2646 {
2647 x = ira_reg_equiv[from_regno].invariant;
2648 ira_assert (x != NULL_RTX);
2649 ira_assert (ira_reg_equiv[to_regno].invariant == NULL_RTX
2650 || rtx_equal_p (ira_reg_equiv[to_regno].invariant, x));
2651 ira_reg_equiv[to_regno].invariant = x;
2652 }
2653 if (find_reg_note (insn, REG_EQUIV, x) == NULL_RTX)
2654 {
2655 note = set_unique_reg_note (insn, REG_EQUIV, copy_rtx (x));
2656 gcc_assert (note != NULL_RTX);
2657 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2658 {
2659 fprintf (ira_dump_file,
2660 " Adding equiv note to insn %u for reg %d ",
2661 INSN_UID (insn), to_regno);
2662 dump_value_slim (ira_dump_file, x, 1);
2663 fprintf (ira_dump_file, "\n");
2664 }
2665 }
2666 }
2667 ira_reg_equiv[to_regno].init_insns
2668 = gen_rtx_INSN_LIST (VOIDmode, insn,
2669 ira_reg_equiv[to_regno].init_insns);
2670 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2671 fprintf (ira_dump_file,
2672 " Adding equiv init move insn %u to reg %d\n",
2673 INSN_UID (insn), to_regno);
2674 }
2675
2676 /* Fix values of array REG_EQUIV_INIT after live range splitting done
2677 by IRA. */
2678 static void
fix_reg_equiv_init(void)2679 fix_reg_equiv_init (void)
2680 {
2681 int max_regno = max_reg_num ();
2682 int i, new_regno, max;
2683 rtx set;
2684 rtx_insn_list *x, *next, *prev;
2685 rtx_insn *insn;
2686
2687 if (max_regno_before_ira < max_regno)
2688 {
2689 max = vec_safe_length (reg_equivs);
2690 grow_reg_equivs ();
2691 for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
2692 for (prev = NULL, x = reg_equiv_init (i);
2693 x != NULL_RTX;
2694 x = next)
2695 {
2696 next = x->next ();
2697 insn = x->insn ();
2698 set = single_set (insn);
2699 ira_assert (set != NULL_RTX
2700 && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))));
2701 if (REG_P (SET_DEST (set))
2702 && ((int) REGNO (SET_DEST (set)) == i
2703 || (int) ORIGINAL_REGNO (SET_DEST (set)) == i))
2704 new_regno = REGNO (SET_DEST (set));
2705 else if (REG_P (SET_SRC (set))
2706 && ((int) REGNO (SET_SRC (set)) == i
2707 || (int) ORIGINAL_REGNO (SET_SRC (set)) == i))
2708 new_regno = REGNO (SET_SRC (set));
2709 else
2710 gcc_unreachable ();
2711 if (new_regno == i)
2712 prev = x;
2713 else
2714 {
2715 /* Remove the wrong list element. */
2716 if (prev == NULL_RTX)
2717 reg_equiv_init (i) = next;
2718 else
2719 XEXP (prev, 1) = next;
2720 XEXP (x, 1) = reg_equiv_init (new_regno);
2721 reg_equiv_init (new_regno) = x;
2722 }
2723 }
2724 }
2725 }
2726
2727 #ifdef ENABLE_IRA_CHECKING
2728 /* Print redundant memory-memory copies. */
2729 static void
print_redundant_copies(void)2730 print_redundant_copies (void)
2731 {
2732 int hard_regno;
2733 ira_allocno_t a;
2734 ira_copy_t cp, next_cp;
2735 ira_allocno_iterator ai;
2736
2737 FOR_EACH_ALLOCNO (a, ai)
2738 {
2739 if (ALLOCNO_CAP_MEMBER (a) != NULL)
2740 /* It is a cap. */
2741 continue;
2742 hard_regno = ALLOCNO_HARD_REGNO (a);
2743 if (hard_regno >= 0)
2744 continue;
2745 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2746 if (cp->first == a)
2747 next_cp = cp->next_first_allocno_copy;
2748 else
2749 {
2750 next_cp = cp->next_second_allocno_copy;
2751 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL
2752 && cp->insn != NULL_RTX
2753 && ALLOCNO_HARD_REGNO (cp->first) == hard_regno)
2754 fprintf (ira_dump_file,
2755 " Redundant move from %d(freq %d):%d\n",
2756 INSN_UID (cp->insn), cp->freq, hard_regno);
2757 }
2758 }
2759 }
2760 #endif
2761
2762 /* Setup preferred and alternative classes for new pseudo-registers
2763 created by IRA starting with START. */
2764 static void
setup_preferred_alternate_classes_for_new_pseudos(int start)2765 setup_preferred_alternate_classes_for_new_pseudos (int start)
2766 {
2767 int i, old_regno;
2768 int max_regno = max_reg_num ();
2769
2770 for (i = start; i < max_regno; i++)
2771 {
2772 old_regno = ORIGINAL_REGNO (regno_reg_rtx[i]);
2773 ira_assert (i != old_regno);
2774 setup_reg_classes (i, reg_preferred_class (old_regno),
2775 reg_alternate_class (old_regno),
2776 reg_allocno_class (old_regno));
2777 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2778 fprintf (ira_dump_file,
2779 " New r%d: setting preferred %s, alternative %s\n",
2780 i, reg_class_names[reg_preferred_class (old_regno)],
2781 reg_class_names[reg_alternate_class (old_regno)]);
2782 }
2783 }
2784
2785
2786 /* The number of entries allocated in reg_info. */
2787 static int allocated_reg_info_size;
2788
2789 /* Regional allocation can create new pseudo-registers. This function
2790 expands some arrays for pseudo-registers. */
2791 static void
expand_reg_info(void)2792 expand_reg_info (void)
2793 {
2794 int i;
2795 int size = max_reg_num ();
2796
2797 resize_reg_info ();
2798 for (i = allocated_reg_info_size; i < size; i++)
2799 setup_reg_classes (i, GENERAL_REGS, ALL_REGS, GENERAL_REGS);
2800 setup_preferred_alternate_classes_for_new_pseudos (allocated_reg_info_size);
2801 allocated_reg_info_size = size;
2802 }
2803
2804 /* Return TRUE if there is too high register pressure in the function.
2805 It is used to decide when stack slot sharing is worth to do. */
2806 static bool
too_high_register_pressure_p(void)2807 too_high_register_pressure_p (void)
2808 {
2809 int i;
2810 enum reg_class pclass;
2811
2812 for (i = 0; i < ira_pressure_classes_num; i++)
2813 {
2814 pclass = ira_pressure_classes[i];
2815 if (ira_loop_tree_root->reg_pressure[pclass] > 10000)
2816 return true;
2817 }
2818 return false;
2819 }
2820
2821
2822
2823 /* Indicate that hard register number FROM was eliminated and replaced with
2824 an offset from hard register number TO. The status of hard registers live
2825 at the start of a basic block is updated by replacing a use of FROM with
2826 a use of TO. */
2827
2828 void
mark_elimination(int from,int to)2829 mark_elimination (int from, int to)
2830 {
2831 basic_block bb;
2832 bitmap r;
2833
2834 FOR_EACH_BB_FN (bb, cfun)
2835 {
2836 r = DF_LR_IN (bb);
2837 if (bitmap_bit_p (r, from))
2838 {
2839 bitmap_clear_bit (r, from);
2840 bitmap_set_bit (r, to);
2841 }
2842 if (! df_live)
2843 continue;
2844 r = DF_LIVE_IN (bb);
2845 if (bitmap_bit_p (r, from))
2846 {
2847 bitmap_clear_bit (r, from);
2848 bitmap_set_bit (r, to);
2849 }
2850 }
2851 }
2852
2853
2854
2855 /* The length of the following array. */
2856 int ira_reg_equiv_len;
2857
2858 /* Info about equiv. info for each register. */
2859 struct ira_reg_equiv_s *ira_reg_equiv;
2860
2861 /* Expand ira_reg_equiv if necessary. */
2862 void
ira_expand_reg_equiv(void)2863 ira_expand_reg_equiv (void)
2864 {
2865 int old = ira_reg_equiv_len;
2866
2867 if (ira_reg_equiv_len > max_reg_num ())
2868 return;
2869 ira_reg_equiv_len = max_reg_num () * 3 / 2 + 1;
2870 ira_reg_equiv
2871 = (struct ira_reg_equiv_s *) xrealloc (ira_reg_equiv,
2872 ira_reg_equiv_len
2873 * sizeof (struct ira_reg_equiv_s));
2874 gcc_assert (old < ira_reg_equiv_len);
2875 memset (ira_reg_equiv + old, 0,
2876 sizeof (struct ira_reg_equiv_s) * (ira_reg_equiv_len - old));
2877 }
2878
2879 static void
init_reg_equiv(void)2880 init_reg_equiv (void)
2881 {
2882 ira_reg_equiv_len = 0;
2883 ira_reg_equiv = NULL;
2884 ira_expand_reg_equiv ();
2885 }
2886
2887 static void
finish_reg_equiv(void)2888 finish_reg_equiv (void)
2889 {
2890 free (ira_reg_equiv);
2891 }
2892
2893
2894
2895 struct equivalence
2896 {
2897 /* Set when a REG_EQUIV note is found or created. Use to
2898 keep track of what memory accesses might be created later,
2899 e.g. by reload. */
2900 rtx replacement;
2901 rtx *src_p;
2902
2903 /* The list of each instruction which initializes this register.
2904
2905 NULL indicates we know nothing about this register's equivalence
2906 properties.
2907
2908 An INSN_LIST with a NULL insn indicates this pseudo is already
2909 known to not have a valid equivalence. */
2910 rtx_insn_list *init_insns;
2911
2912 /* Loop depth is used to recognize equivalences which appear
2913 to be present within the same loop (or in an inner loop). */
2914 short loop_depth;
2915 /* Nonzero if this had a preexisting REG_EQUIV note. */
2916 unsigned char is_arg_equivalence : 1;
2917 /* Set when an attempt should be made to replace a register
2918 with the associated src_p entry. */
2919 unsigned char replace : 1;
2920 /* Set if this register has no known equivalence. */
2921 unsigned char no_equiv : 1;
2922 /* Set if this register is mentioned in a paradoxical subreg. */
2923 unsigned char pdx_subregs : 1;
2924 };
2925
2926 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
2927 structure for that register. */
2928 static struct equivalence *reg_equiv;
2929
2930 /* Used for communication between the following two functions. */
2931 struct equiv_mem_data
2932 {
2933 /* A MEM that we wish to ensure remains unchanged. */
2934 rtx equiv_mem;
2935
2936 /* Set true if EQUIV_MEM is modified. */
2937 bool equiv_mem_modified;
2938 };
2939
2940 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
2941 Called via note_stores. */
2942 static void
validate_equiv_mem_from_store(rtx dest,const_rtx set ATTRIBUTE_UNUSED,void * data)2943 validate_equiv_mem_from_store (rtx dest, const_rtx set ATTRIBUTE_UNUSED,
2944 void *data)
2945 {
2946 struct equiv_mem_data *info = (struct equiv_mem_data *) data;
2947
2948 if ((REG_P (dest)
2949 && reg_overlap_mentioned_p (dest, info->equiv_mem))
2950 || (MEM_P (dest)
2951 && anti_dependence (info->equiv_mem, dest)))
2952 info->equiv_mem_modified = true;
2953 }
2954
2955 enum valid_equiv { valid_none, valid_combine, valid_reload };
2956
2957 /* Verify that no store between START and the death of REG invalidates
2958 MEMREF. MEMREF is invalidated by modifying a register used in MEMREF,
2959 by storing into an overlapping memory location, or with a non-const
2960 CALL_INSN.
2961
2962 Return VALID_RELOAD if MEMREF remains valid for both reload and
2963 combine_and_move insns, VALID_COMBINE if only valid for
2964 combine_and_move_insns, and VALID_NONE otherwise. */
2965 static enum valid_equiv
validate_equiv_mem(rtx_insn * start,rtx reg,rtx memref)2966 validate_equiv_mem (rtx_insn *start, rtx reg, rtx memref)
2967 {
2968 rtx_insn *insn;
2969 rtx note;
2970 struct equiv_mem_data info = { memref, false };
2971 enum valid_equiv ret = valid_reload;
2972
2973 /* If the memory reference has side effects or is volatile, it isn't a
2974 valid equivalence. */
2975 if (side_effects_p (memref))
2976 return valid_none;
2977
2978 for (insn = start; insn; insn = NEXT_INSN (insn))
2979 {
2980 if (!INSN_P (insn))
2981 continue;
2982
2983 if (find_reg_note (insn, REG_DEAD, reg))
2984 return ret;
2985
2986 if (CALL_P (insn))
2987 {
2988 /* We can combine a reg def from one insn into a reg use in
2989 another over a call if the memory is readonly or the call
2990 const/pure. However, we can't set reg_equiv notes up for
2991 reload over any call. The problem is the equivalent form
2992 may reference a pseudo which gets assigned a call
2993 clobbered hard reg. When we later replace REG with its
2994 equivalent form, the value in the call-clobbered reg has
2995 been changed and all hell breaks loose. */
2996 ret = valid_combine;
2997 if (!MEM_READONLY_P (memref)
2998 && !RTL_CONST_OR_PURE_CALL_P (insn))
2999 return valid_none;
3000 }
3001
3002 note_stores (insn, validate_equiv_mem_from_store, &info);
3003 if (info.equiv_mem_modified)
3004 return valid_none;
3005
3006 /* If a register mentioned in MEMREF is modified via an
3007 auto-increment, we lose the equivalence. Do the same if one
3008 dies; although we could extend the life, it doesn't seem worth
3009 the trouble. */
3010
3011 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
3012 if ((REG_NOTE_KIND (note) == REG_INC
3013 || REG_NOTE_KIND (note) == REG_DEAD)
3014 && REG_P (XEXP (note, 0))
3015 && reg_overlap_mentioned_p (XEXP (note, 0), memref))
3016 return valid_none;
3017 }
3018
3019 return valid_none;
3020 }
3021
3022 /* Returns zero if X is known to be invariant. */
3023 static int
equiv_init_varies_p(rtx x)3024 equiv_init_varies_p (rtx x)
3025 {
3026 RTX_CODE code = GET_CODE (x);
3027 int i;
3028 const char *fmt;
3029
3030 switch (code)
3031 {
3032 case MEM:
3033 return !MEM_READONLY_P (x) || equiv_init_varies_p (XEXP (x, 0));
3034
3035 case CONST:
3036 CASE_CONST_ANY:
3037 case SYMBOL_REF:
3038 case LABEL_REF:
3039 return 0;
3040
3041 case REG:
3042 return reg_equiv[REGNO (x)].replace == 0 && rtx_varies_p (x, 0);
3043
3044 case ASM_OPERANDS:
3045 if (MEM_VOLATILE_P (x))
3046 return 1;
3047
3048 /* Fall through. */
3049
3050 default:
3051 break;
3052 }
3053
3054 fmt = GET_RTX_FORMAT (code);
3055 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3056 if (fmt[i] == 'e')
3057 {
3058 if (equiv_init_varies_p (XEXP (x, i)))
3059 return 1;
3060 }
3061 else if (fmt[i] == 'E')
3062 {
3063 int j;
3064 for (j = 0; j < XVECLEN (x, i); j++)
3065 if (equiv_init_varies_p (XVECEXP (x, i, j)))
3066 return 1;
3067 }
3068
3069 return 0;
3070 }
3071
3072 /* Returns nonzero if X (used to initialize register REGNO) is movable.
3073 X is only movable if the registers it uses have equivalent initializations
3074 which appear to be within the same loop (or in an inner loop) and movable
3075 or if they are not candidates for local_alloc and don't vary. */
3076 static int
equiv_init_movable_p(rtx x,int regno)3077 equiv_init_movable_p (rtx x, int regno)
3078 {
3079 int i, j;
3080 const char *fmt;
3081 enum rtx_code code = GET_CODE (x);
3082
3083 switch (code)
3084 {
3085 case SET:
3086 return equiv_init_movable_p (SET_SRC (x), regno);
3087
3088 case CC0:
3089 case CLOBBER:
3090 return 0;
3091
3092 case PRE_INC:
3093 case PRE_DEC:
3094 case POST_INC:
3095 case POST_DEC:
3096 case PRE_MODIFY:
3097 case POST_MODIFY:
3098 return 0;
3099
3100 case REG:
3101 return ((reg_equiv[REGNO (x)].loop_depth >= reg_equiv[regno].loop_depth
3102 && reg_equiv[REGNO (x)].replace)
3103 || (REG_BASIC_BLOCK (REGNO (x)) < NUM_FIXED_BLOCKS
3104 && ! rtx_varies_p (x, 0)));
3105
3106 case UNSPEC_VOLATILE:
3107 return 0;
3108
3109 case ASM_OPERANDS:
3110 if (MEM_VOLATILE_P (x))
3111 return 0;
3112
3113 /* Fall through. */
3114
3115 default:
3116 break;
3117 }
3118
3119 fmt = GET_RTX_FORMAT (code);
3120 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3121 switch (fmt[i])
3122 {
3123 case 'e':
3124 if (! equiv_init_movable_p (XEXP (x, i), regno))
3125 return 0;
3126 break;
3127 case 'E':
3128 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3129 if (! equiv_init_movable_p (XVECEXP (x, i, j), regno))
3130 return 0;
3131 break;
3132 }
3133
3134 return 1;
3135 }
3136
3137 static bool memref_referenced_p (rtx memref, rtx x, bool read_p);
3138
3139 /* Auxiliary function for memref_referenced_p. Process setting X for
3140 MEMREF store. */
3141 static bool
process_set_for_memref_referenced_p(rtx memref,rtx x)3142 process_set_for_memref_referenced_p (rtx memref, rtx x)
3143 {
3144 /* If we are setting a MEM, it doesn't count (its address does), but any
3145 other SET_DEST that has a MEM in it is referencing the MEM. */
3146 if (MEM_P (x))
3147 {
3148 if (memref_referenced_p (memref, XEXP (x, 0), true))
3149 return true;
3150 }
3151 else if (memref_referenced_p (memref, x, false))
3152 return true;
3153
3154 return false;
3155 }
3156
3157 /* TRUE if X references a memory location (as a read if READ_P) that
3158 would be affected by a store to MEMREF. */
3159 static bool
memref_referenced_p(rtx memref,rtx x,bool read_p)3160 memref_referenced_p (rtx memref, rtx x, bool read_p)
3161 {
3162 int i, j;
3163 const char *fmt;
3164 enum rtx_code code = GET_CODE (x);
3165
3166 switch (code)
3167 {
3168 case CONST:
3169 case LABEL_REF:
3170 case SYMBOL_REF:
3171 CASE_CONST_ANY:
3172 case PC:
3173 case CC0:
3174 case HIGH:
3175 case LO_SUM:
3176 return false;
3177
3178 case REG:
3179 return (reg_equiv[REGNO (x)].replacement
3180 && memref_referenced_p (memref,
3181 reg_equiv[REGNO (x)].replacement, read_p));
3182
3183 case MEM:
3184 /* Memory X might have another effective type than MEMREF. */
3185 if (read_p || true_dependence (memref, VOIDmode, x))
3186 return true;
3187 break;
3188
3189 case SET:
3190 if (process_set_for_memref_referenced_p (memref, SET_DEST (x)))
3191 return true;
3192
3193 return memref_referenced_p (memref, SET_SRC (x), true);
3194
3195 case CLOBBER:
3196 if (process_set_for_memref_referenced_p (memref, XEXP (x, 0)))
3197 return true;
3198
3199 return false;
3200
3201 case PRE_DEC:
3202 case POST_DEC:
3203 case PRE_INC:
3204 case POST_INC:
3205 if (process_set_for_memref_referenced_p (memref, XEXP (x, 0)))
3206 return true;
3207
3208 return memref_referenced_p (memref, XEXP (x, 0), true);
3209
3210 case POST_MODIFY:
3211 case PRE_MODIFY:
3212 /* op0 = op0 + op1 */
3213 if (process_set_for_memref_referenced_p (memref, XEXP (x, 0)))
3214 return true;
3215
3216 if (memref_referenced_p (memref, XEXP (x, 0), true))
3217 return true;
3218
3219 return memref_referenced_p (memref, XEXP (x, 1), true);
3220
3221 default:
3222 break;
3223 }
3224
3225 fmt = GET_RTX_FORMAT (code);
3226 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3227 switch (fmt[i])
3228 {
3229 case 'e':
3230 if (memref_referenced_p (memref, XEXP (x, i), read_p))
3231 return true;
3232 break;
3233 case 'E':
3234 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3235 if (memref_referenced_p (memref, XVECEXP (x, i, j), read_p))
3236 return true;
3237 break;
3238 }
3239
3240 return false;
3241 }
3242
3243 /* TRUE if some insn in the range (START, END] references a memory location
3244 that would be affected by a store to MEMREF.
3245
3246 Callers should not call this routine if START is after END in the
3247 RTL chain. */
3248
3249 static int
memref_used_between_p(rtx memref,rtx_insn * start,rtx_insn * end)3250 memref_used_between_p (rtx memref, rtx_insn *start, rtx_insn *end)
3251 {
3252 rtx_insn *insn;
3253
3254 for (insn = NEXT_INSN (start);
3255 insn && insn != NEXT_INSN (end);
3256 insn = NEXT_INSN (insn))
3257 {
3258 if (!NONDEBUG_INSN_P (insn))
3259 continue;
3260
3261 if (memref_referenced_p (memref, PATTERN (insn), false))
3262 return 1;
3263
3264 /* Nonconst functions may access memory. */
3265 if (CALL_P (insn) && (! RTL_CONST_CALL_P (insn)))
3266 return 1;
3267 }
3268
3269 gcc_assert (insn == NEXT_INSN (end));
3270 return 0;
3271 }
3272
3273 /* Mark REG as having no known equivalence.
3274 Some instructions might have been processed before and furnished
3275 with REG_EQUIV notes for this register; these notes will have to be
3276 removed.
3277 STORE is the piece of RTL that does the non-constant / conflicting
3278 assignment - a SET, CLOBBER or REG_INC note. It is currently not used,
3279 but needs to be there because this function is called from note_stores. */
3280 static void
no_equiv(rtx reg,const_rtx store ATTRIBUTE_UNUSED,void * data ATTRIBUTE_UNUSED)3281 no_equiv (rtx reg, const_rtx store ATTRIBUTE_UNUSED,
3282 void *data ATTRIBUTE_UNUSED)
3283 {
3284 int regno;
3285 rtx_insn_list *list;
3286
3287 if (!REG_P (reg))
3288 return;
3289 regno = REGNO (reg);
3290 reg_equiv[regno].no_equiv = 1;
3291 list = reg_equiv[regno].init_insns;
3292 if (list && list->insn () == NULL)
3293 return;
3294 reg_equiv[regno].init_insns = gen_rtx_INSN_LIST (VOIDmode, NULL_RTX, NULL);
3295 reg_equiv[regno].replacement = NULL_RTX;
3296 /* This doesn't matter for equivalences made for argument registers, we
3297 should keep their initialization insns. */
3298 if (reg_equiv[regno].is_arg_equivalence)
3299 return;
3300 ira_reg_equiv[regno].defined_p = false;
3301 ira_reg_equiv[regno].init_insns = NULL;
3302 for (; list; list = list->next ())
3303 {
3304 rtx_insn *insn = list->insn ();
3305 remove_note (insn, find_reg_note (insn, REG_EQUIV, NULL_RTX));
3306 }
3307 }
3308
3309 /* Check whether the SUBREG is a paradoxical subreg and set the result
3310 in PDX_SUBREGS. */
3311
3312 static void
set_paradoxical_subreg(rtx_insn * insn)3313 set_paradoxical_subreg (rtx_insn *insn)
3314 {
3315 subrtx_iterator::array_type array;
3316 FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
3317 {
3318 const_rtx subreg = *iter;
3319 if (GET_CODE (subreg) == SUBREG)
3320 {
3321 const_rtx reg = SUBREG_REG (subreg);
3322 if (REG_P (reg) && paradoxical_subreg_p (subreg))
3323 reg_equiv[REGNO (reg)].pdx_subregs = true;
3324 }
3325 }
3326 }
3327
3328 /* In DEBUG_INSN location adjust REGs from CLEARED_REGS bitmap to the
3329 equivalent replacement. */
3330
3331 static rtx
adjust_cleared_regs(rtx loc,const_rtx old_rtx ATTRIBUTE_UNUSED,void * data)3332 adjust_cleared_regs (rtx loc, const_rtx old_rtx ATTRIBUTE_UNUSED, void *data)
3333 {
3334 if (REG_P (loc))
3335 {
3336 bitmap cleared_regs = (bitmap) data;
3337 if (bitmap_bit_p (cleared_regs, REGNO (loc)))
3338 return simplify_replace_fn_rtx (copy_rtx (*reg_equiv[REGNO (loc)].src_p),
3339 NULL_RTX, adjust_cleared_regs, data);
3340 }
3341 return NULL_RTX;
3342 }
3343
3344 /* Given register REGNO is set only once, return true if the defining
3345 insn dominates all uses. */
3346
3347 static bool
def_dominates_uses(int regno)3348 def_dominates_uses (int regno)
3349 {
3350 df_ref def = DF_REG_DEF_CHAIN (regno);
3351
3352 struct df_insn_info *def_info = DF_REF_INSN_INFO (def);
3353 /* If this is an artificial def (eh handler regs, hard frame pointer
3354 for non-local goto, regs defined on function entry) then def_info
3355 is NULL and the reg is always live before any use. We might
3356 reasonably return true in that case, but since the only call
3357 of this function is currently here in ira.c when we are looking
3358 at a defining insn we can't have an artificial def as that would
3359 bump DF_REG_DEF_COUNT. */
3360 gcc_assert (DF_REG_DEF_COUNT (regno) == 1 && def_info != NULL);
3361
3362 rtx_insn *def_insn = DF_REF_INSN (def);
3363 basic_block def_bb = BLOCK_FOR_INSN (def_insn);
3364
3365 for (df_ref use = DF_REG_USE_CHAIN (regno);
3366 use;
3367 use = DF_REF_NEXT_REG (use))
3368 {
3369 struct df_insn_info *use_info = DF_REF_INSN_INFO (use);
3370 /* Only check real uses, not artificial ones. */
3371 if (use_info)
3372 {
3373 rtx_insn *use_insn = DF_REF_INSN (use);
3374 if (!DEBUG_INSN_P (use_insn))
3375 {
3376 basic_block use_bb = BLOCK_FOR_INSN (use_insn);
3377 if (use_bb != def_bb
3378 ? !dominated_by_p (CDI_DOMINATORS, use_bb, def_bb)
3379 : DF_INSN_INFO_LUID (use_info) < DF_INSN_INFO_LUID (def_info))
3380 return false;
3381 }
3382 }
3383 }
3384 return true;
3385 }
3386
3387 /* Scan the instructions before update_equiv_regs. Record which registers
3388 are referenced as paradoxical subregs. Also check for cases in which
3389 the current function needs to save a register that one of its call
3390 instructions clobbers.
3391
3392 These things are logically unrelated, but it's more efficient to do
3393 them together. */
3394
3395 static void
update_equiv_regs_prescan(void)3396 update_equiv_regs_prescan (void)
3397 {
3398 basic_block bb;
3399 rtx_insn *insn;
3400 function_abi_aggregator callee_abis;
3401
3402 FOR_EACH_BB_FN (bb, cfun)
3403 FOR_BB_INSNS (bb, insn)
3404 if (NONDEBUG_INSN_P (insn))
3405 {
3406 set_paradoxical_subreg (insn);
3407 if (CALL_P (insn))
3408 callee_abis.note_callee_abi (insn_callee_abi (insn));
3409 }
3410
3411 HARD_REG_SET extra_caller_saves = callee_abis.caller_save_regs (*crtl->abi);
3412 if (!hard_reg_set_empty_p (extra_caller_saves))
3413 for (unsigned int regno = 0; regno < FIRST_PSEUDO_REGISTER; ++regno)
3414 if (TEST_HARD_REG_BIT (extra_caller_saves, regno))
3415 df_set_regs_ever_live (regno, true);
3416 }
3417
3418 /* Find registers that are equivalent to a single value throughout the
3419 compilation (either because they can be referenced in memory or are
3420 set once from a single constant). Lower their priority for a
3421 register.
3422
3423 If such a register is only referenced once, try substituting its
3424 value into the using insn. If it succeeds, we can eliminate the
3425 register completely.
3426
3427 Initialize init_insns in ira_reg_equiv array. */
3428 static void
update_equiv_regs(void)3429 update_equiv_regs (void)
3430 {
3431 rtx_insn *insn;
3432 basic_block bb;
3433
3434 /* Scan the insns and find which registers have equivalences. Do this
3435 in a separate scan of the insns because (due to -fcse-follow-jumps)
3436 a register can be set below its use. */
3437 bitmap setjmp_crosses = regstat_get_setjmp_crosses ();
3438 FOR_EACH_BB_FN (bb, cfun)
3439 {
3440 int loop_depth = bb_loop_depth (bb);
3441
3442 for (insn = BB_HEAD (bb);
3443 insn != NEXT_INSN (BB_END (bb));
3444 insn = NEXT_INSN (insn))
3445 {
3446 rtx note;
3447 rtx set;
3448 rtx dest, src;
3449 int regno;
3450
3451 if (! INSN_P (insn))
3452 continue;
3453
3454 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
3455 if (REG_NOTE_KIND (note) == REG_INC)
3456 no_equiv (XEXP (note, 0), note, NULL);
3457
3458 set = single_set (insn);
3459
3460 /* If this insn contains more (or less) than a single SET,
3461 only mark all destinations as having no known equivalence. */
3462 if (set == NULL_RTX
3463 || side_effects_p (SET_SRC (set)))
3464 {
3465 note_pattern_stores (PATTERN (insn), no_equiv, NULL);
3466 continue;
3467 }
3468 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3469 {
3470 int i;
3471
3472 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
3473 {
3474 rtx part = XVECEXP (PATTERN (insn), 0, i);
3475 if (part != set)
3476 note_pattern_stores (part, no_equiv, NULL);
3477 }
3478 }
3479
3480 dest = SET_DEST (set);
3481 src = SET_SRC (set);
3482
3483 /* See if this is setting up the equivalence between an argument
3484 register and its stack slot. */
3485 note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
3486 if (note)
3487 {
3488 gcc_assert (REG_P (dest));
3489 regno = REGNO (dest);
3490
3491 /* Note that we don't want to clear init_insns in
3492 ira_reg_equiv even if there are multiple sets of this
3493 register. */
3494 reg_equiv[regno].is_arg_equivalence = 1;
3495
3496 /* The insn result can have equivalence memory although
3497 the equivalence is not set up by the insn. We add
3498 this insn to init insns as it is a flag for now that
3499 regno has an equivalence. We will remove the insn
3500 from init insn list later. */
3501 if (rtx_equal_p (src, XEXP (note, 0)) || MEM_P (XEXP (note, 0)))
3502 ira_reg_equiv[regno].init_insns
3503 = gen_rtx_INSN_LIST (VOIDmode, insn,
3504 ira_reg_equiv[regno].init_insns);
3505
3506 /* Continue normally in case this is a candidate for
3507 replacements. */
3508 }
3509
3510 if (!optimize)
3511 continue;
3512
3513 /* We only handle the case of a pseudo register being set
3514 once, or always to the same value. */
3515 /* ??? The mn10200 port breaks if we add equivalences for
3516 values that need an ADDRESS_REGS register and set them equivalent
3517 to a MEM of a pseudo. The actual problem is in the over-conservative
3518 handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
3519 calculate_needs, but we traditionally work around this problem
3520 here by rejecting equivalences when the destination is in a register
3521 that's likely spilled. This is fragile, of course, since the
3522 preferred class of a pseudo depends on all instructions that set
3523 or use it. */
3524
3525 if (!REG_P (dest)
3526 || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER
3527 || (reg_equiv[regno].init_insns
3528 && reg_equiv[regno].init_insns->insn () == NULL)
3529 || (targetm.class_likely_spilled_p (reg_preferred_class (regno))
3530 && MEM_P (src) && ! reg_equiv[regno].is_arg_equivalence))
3531 {
3532 /* This might be setting a SUBREG of a pseudo, a pseudo that is
3533 also set somewhere else to a constant. */
3534 note_pattern_stores (set, no_equiv, NULL);
3535 continue;
3536 }
3537
3538 /* Don't set reg mentioned in a paradoxical subreg
3539 equivalent to a mem. */
3540 if (MEM_P (src) && reg_equiv[regno].pdx_subregs)
3541 {
3542 note_pattern_stores (set, no_equiv, NULL);
3543 continue;
3544 }
3545
3546 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
3547
3548 /* cse sometimes generates function invariants, but doesn't put a
3549 REG_EQUAL note on the insn. Since this note would be redundant,
3550 there's no point creating it earlier than here. */
3551 if (! note && ! rtx_varies_p (src, 0))
3552 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
3553
3554 /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
3555 since it represents a function call. */
3556 if (note && GET_CODE (XEXP (note, 0)) == EXPR_LIST)
3557 note = NULL_RTX;
3558
3559 if (DF_REG_DEF_COUNT (regno) != 1)
3560 {
3561 bool equal_p = true;
3562 rtx_insn_list *list;
3563
3564 /* If we have already processed this pseudo and determined it
3565 cannot have an equivalence, then honor that decision. */
3566 if (reg_equiv[regno].no_equiv)
3567 continue;
3568
3569 if (! note
3570 || rtx_varies_p (XEXP (note, 0), 0)
3571 || (reg_equiv[regno].replacement
3572 && ! rtx_equal_p (XEXP (note, 0),
3573 reg_equiv[regno].replacement)))
3574 {
3575 no_equiv (dest, set, NULL);
3576 continue;
3577 }
3578
3579 list = reg_equiv[regno].init_insns;
3580 for (; list; list = list->next ())
3581 {
3582 rtx note_tmp;
3583 rtx_insn *insn_tmp;
3584
3585 insn_tmp = list->insn ();
3586 note_tmp = find_reg_note (insn_tmp, REG_EQUAL, NULL_RTX);
3587 gcc_assert (note_tmp);
3588 if (! rtx_equal_p (XEXP (note, 0), XEXP (note_tmp, 0)))
3589 {
3590 equal_p = false;
3591 break;
3592 }
3593 }
3594
3595 if (! equal_p)
3596 {
3597 no_equiv (dest, set, NULL);
3598 continue;
3599 }
3600 }
3601
3602 /* Record this insn as initializing this register. */
3603 reg_equiv[regno].init_insns
3604 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv[regno].init_insns);
3605
3606 /* If this register is known to be equal to a constant, record that
3607 it is always equivalent to the constant.
3608 Note that it is possible to have a register use before
3609 the def in loops (see gcc.c-torture/execute/pr79286.c)
3610 where the reg is undefined on first use. If the def insn
3611 won't trap we can use it as an equivalence, effectively
3612 choosing the "undefined" value for the reg to be the
3613 same as the value set by the def. */
3614 if (DF_REG_DEF_COUNT (regno) == 1
3615 && note
3616 && !rtx_varies_p (XEXP (note, 0), 0)
3617 && (!may_trap_or_fault_p (XEXP (note, 0))
3618 || def_dominates_uses (regno)))
3619 {
3620 rtx note_value = XEXP (note, 0);
3621 remove_note (insn, note);
3622 set_unique_reg_note (insn, REG_EQUIV, note_value);
3623 }
3624
3625 /* If this insn introduces a "constant" register, decrease the priority
3626 of that register. Record this insn if the register is only used once
3627 more and the equivalence value is the same as our source.
3628
3629 The latter condition is checked for two reasons: First, it is an
3630 indication that it may be more efficient to actually emit the insn
3631 as written (if no registers are available, reload will substitute
3632 the equivalence). Secondly, it avoids problems with any registers
3633 dying in this insn whose death notes would be missed.
3634
3635 If we don't have a REG_EQUIV note, see if this insn is loading
3636 a register used only in one basic block from a MEM. If so, and the
3637 MEM remains unchanged for the life of the register, add a REG_EQUIV
3638 note. */
3639 note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
3640
3641 rtx replacement = NULL_RTX;
3642 if (note)
3643 replacement = XEXP (note, 0);
3644 else if (REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
3645 && MEM_P (SET_SRC (set)))
3646 {
3647 enum valid_equiv validity;
3648 validity = validate_equiv_mem (insn, dest, SET_SRC (set));
3649 if (validity != valid_none)
3650 {
3651 replacement = copy_rtx (SET_SRC (set));
3652 if (validity == valid_reload)
3653 note = set_unique_reg_note (insn, REG_EQUIV, replacement);
3654 }
3655 }
3656
3657 /* If we haven't done so, record for reload that this is an
3658 equivalencing insn. */
3659 if (note && !reg_equiv[regno].is_arg_equivalence)
3660 ira_reg_equiv[regno].init_insns
3661 = gen_rtx_INSN_LIST (VOIDmode, insn,
3662 ira_reg_equiv[regno].init_insns);
3663
3664 if (replacement)
3665 {
3666 reg_equiv[regno].replacement = replacement;
3667 reg_equiv[regno].src_p = &SET_SRC (set);
3668 reg_equiv[regno].loop_depth = (short) loop_depth;
3669
3670 /* Don't mess with things live during setjmp. */
3671 if (optimize && !bitmap_bit_p (setjmp_crosses, regno))
3672 {
3673 /* If the register is referenced exactly twice, meaning it is
3674 set once and used once, indicate that the reference may be
3675 replaced by the equivalence we computed above. Do this
3676 even if the register is only used in one block so that
3677 dependencies can be handled where the last register is
3678 used in a different block (i.e. HIGH / LO_SUM sequences)
3679 and to reduce the number of registers alive across
3680 calls. */
3681
3682 if (REG_N_REFS (regno) == 2
3683 && (rtx_equal_p (replacement, src)
3684 || ! equiv_init_varies_p (src))
3685 && NONJUMP_INSN_P (insn)
3686 && equiv_init_movable_p (PATTERN (insn), regno))
3687 reg_equiv[regno].replace = 1;
3688 }
3689 }
3690 }
3691 }
3692 }
3693
3694 /* For insns that set a MEM to the contents of a REG that is only used
3695 in a single basic block, see if the register is always equivalent
3696 to that memory location and if moving the store from INSN to the
3697 insn that sets REG is safe. If so, put a REG_EQUIV note on the
3698 initializing insn. */
3699 static void
add_store_equivs(void)3700 add_store_equivs (void)
3701 {
3702 auto_bitmap seen_insns;
3703
3704 for (rtx_insn *insn = get_insns (); insn; insn = NEXT_INSN (insn))
3705 {
3706 rtx set, src, dest;
3707 unsigned regno;
3708 rtx_insn *init_insn;
3709
3710 bitmap_set_bit (seen_insns, INSN_UID (insn));
3711
3712 if (! INSN_P (insn))
3713 continue;
3714
3715 set = single_set (insn);
3716 if (! set)
3717 continue;
3718
3719 dest = SET_DEST (set);
3720 src = SET_SRC (set);
3721
3722 /* Don't add a REG_EQUIV note if the insn already has one. The existing
3723 REG_EQUIV is likely more useful than the one we are adding. */
3724 if (MEM_P (dest) && REG_P (src)
3725 && (regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
3726 && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
3727 && DF_REG_DEF_COUNT (regno) == 1
3728 && ! reg_equiv[regno].pdx_subregs
3729 && reg_equiv[regno].init_insns != NULL
3730 && (init_insn = reg_equiv[regno].init_insns->insn ()) != 0
3731 && bitmap_bit_p (seen_insns, INSN_UID (init_insn))
3732 && ! find_reg_note (init_insn, REG_EQUIV, NULL_RTX)
3733 && validate_equiv_mem (init_insn, src, dest) == valid_reload
3734 && ! memref_used_between_p (dest, init_insn, insn)
3735 /* Attaching a REG_EQUIV note will fail if INIT_INSN has
3736 multiple sets. */
3737 && set_unique_reg_note (init_insn, REG_EQUIV, copy_rtx (dest)))
3738 {
3739 /* This insn makes the equivalence, not the one initializing
3740 the register. */
3741 ira_reg_equiv[regno].init_insns
3742 = gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
3743 df_notes_rescan (init_insn);
3744 if (dump_file)
3745 fprintf (dump_file,
3746 "Adding REG_EQUIV to insn %d for source of insn %d\n",
3747 INSN_UID (init_insn),
3748 INSN_UID (insn));
3749 }
3750 }
3751 }
3752
3753 /* Scan all regs killed in an insn to see if any of them are registers
3754 only used that once. If so, see if we can replace the reference
3755 with the equivalent form. If we can, delete the initializing
3756 reference and this register will go away. If we can't replace the
3757 reference, and the initializing reference is within the same loop
3758 (or in an inner loop), then move the register initialization just
3759 before the use, so that they are in the same basic block. */
3760 static void
combine_and_move_insns(void)3761 combine_and_move_insns (void)
3762 {
3763 auto_bitmap cleared_regs;
3764 int max = max_reg_num ();
3765
3766 for (int regno = FIRST_PSEUDO_REGISTER; regno < max; regno++)
3767 {
3768 if (!reg_equiv[regno].replace)
3769 continue;
3770
3771 rtx_insn *use_insn = 0;
3772 for (df_ref use = DF_REG_USE_CHAIN (regno);
3773 use;
3774 use = DF_REF_NEXT_REG (use))
3775 if (DF_REF_INSN_INFO (use))
3776 {
3777 if (DEBUG_INSN_P (DF_REF_INSN (use)))
3778 continue;
3779 gcc_assert (!use_insn);
3780 use_insn = DF_REF_INSN (use);
3781 }
3782 gcc_assert (use_insn);
3783
3784 /* Don't substitute into jumps. indirect_jump_optimize does
3785 this for anything we are prepared to handle. */
3786 if (JUMP_P (use_insn))
3787 continue;
3788
3789 /* Also don't substitute into a conditional trap insn -- it can become
3790 an unconditional trap, and that is a flow control insn. */
3791 if (GET_CODE (PATTERN (use_insn)) == TRAP_IF)
3792 continue;
3793
3794 df_ref def = DF_REG_DEF_CHAIN (regno);
3795 gcc_assert (DF_REG_DEF_COUNT (regno) == 1 && DF_REF_INSN_INFO (def));
3796 rtx_insn *def_insn = DF_REF_INSN (def);
3797
3798 /* We may not move instructions that can throw, since that
3799 changes basic block boundaries and we are not prepared to
3800 adjust the CFG to match. */
3801 if (can_throw_internal (def_insn))
3802 continue;
3803
3804 /* Instructions with multiple sets can only be moved if DF analysis is
3805 performed for all of the registers set. See PR91052. */
3806 if (multiple_sets (def_insn))
3807 continue;
3808
3809 basic_block use_bb = BLOCK_FOR_INSN (use_insn);
3810 basic_block def_bb = BLOCK_FOR_INSN (def_insn);
3811 if (bb_loop_depth (use_bb) > bb_loop_depth (def_bb))
3812 continue;
3813
3814 if (asm_noperands (PATTERN (def_insn)) < 0
3815 && validate_replace_rtx (regno_reg_rtx[regno],
3816 *reg_equiv[regno].src_p, use_insn))
3817 {
3818 rtx link;
3819 /* Append the REG_DEAD notes from def_insn. */
3820 for (rtx *p = ®_NOTES (def_insn); (link = *p) != 0; )
3821 {
3822 if (REG_NOTE_KIND (XEXP (link, 0)) == REG_DEAD)
3823 {
3824 *p = XEXP (link, 1);
3825 XEXP (link, 1) = REG_NOTES (use_insn);
3826 REG_NOTES (use_insn) = link;
3827 }
3828 else
3829 p = &XEXP (link, 1);
3830 }
3831
3832 remove_death (regno, use_insn);
3833 SET_REG_N_REFS (regno, 0);
3834 REG_FREQ (regno) = 0;
3835 df_ref use;
3836 FOR_EACH_INSN_USE (use, def_insn)
3837 {
3838 unsigned int use_regno = DF_REF_REGNO (use);
3839 if (!HARD_REGISTER_NUM_P (use_regno))
3840 reg_equiv[use_regno].replace = 0;
3841 }
3842
3843 delete_insn (def_insn);
3844
3845 reg_equiv[regno].init_insns = NULL;
3846 ira_reg_equiv[regno].init_insns = NULL;
3847 bitmap_set_bit (cleared_regs, regno);
3848 }
3849
3850 /* Move the initialization of the register to just before
3851 USE_INSN. Update the flow information. */
3852 else if (prev_nondebug_insn (use_insn) != def_insn)
3853 {
3854 rtx_insn *new_insn;
3855
3856 new_insn = emit_insn_before (PATTERN (def_insn), use_insn);
3857 REG_NOTES (new_insn) = REG_NOTES (def_insn);
3858 REG_NOTES (def_insn) = 0;
3859 /* Rescan it to process the notes. */
3860 df_insn_rescan (new_insn);
3861
3862 /* Make sure this insn is recognized before reload begins,
3863 otherwise eliminate_regs_in_insn will die. */
3864 INSN_CODE (new_insn) = INSN_CODE (def_insn);
3865
3866 delete_insn (def_insn);
3867
3868 XEXP (reg_equiv[regno].init_insns, 0) = new_insn;
3869
3870 REG_BASIC_BLOCK (regno) = use_bb->index;
3871 REG_N_CALLS_CROSSED (regno) = 0;
3872
3873 if (use_insn == BB_HEAD (use_bb))
3874 BB_HEAD (use_bb) = new_insn;
3875
3876 /* We know regno dies in use_insn, but inside a loop
3877 REG_DEAD notes might be missing when def_insn was in
3878 another basic block. However, when we move def_insn into
3879 this bb we'll definitely get a REG_DEAD note and reload
3880 will see the death. It's possible that update_equiv_regs
3881 set up an equivalence referencing regno for a reg set by
3882 use_insn, when regno was seen as non-local. Now that
3883 regno is local to this block, and dies, such an
3884 equivalence is invalid. */
3885 if (find_reg_note (use_insn, REG_EQUIV, regno_reg_rtx[regno]))
3886 {
3887 rtx set = single_set (use_insn);
3888 if (set && REG_P (SET_DEST (set)))
3889 no_equiv (SET_DEST (set), set, NULL);
3890 }
3891
3892 ira_reg_equiv[regno].init_insns
3893 = gen_rtx_INSN_LIST (VOIDmode, new_insn, NULL_RTX);
3894 bitmap_set_bit (cleared_regs, regno);
3895 }
3896 }
3897
3898 if (!bitmap_empty_p (cleared_regs))
3899 {
3900 basic_block bb;
3901
3902 FOR_EACH_BB_FN (bb, cfun)
3903 {
3904 bitmap_and_compl_into (DF_LR_IN (bb), cleared_regs);
3905 bitmap_and_compl_into (DF_LR_OUT (bb), cleared_regs);
3906 if (!df_live)
3907 continue;
3908 bitmap_and_compl_into (DF_LIVE_IN (bb), cleared_regs);
3909 bitmap_and_compl_into (DF_LIVE_OUT (bb), cleared_regs);
3910 }
3911
3912 /* Last pass - adjust debug insns referencing cleared regs. */
3913 if (MAY_HAVE_DEBUG_BIND_INSNS)
3914 for (rtx_insn *insn = get_insns (); insn; insn = NEXT_INSN (insn))
3915 if (DEBUG_BIND_INSN_P (insn))
3916 {
3917 rtx old_loc = INSN_VAR_LOCATION_LOC (insn);
3918 INSN_VAR_LOCATION_LOC (insn)
3919 = simplify_replace_fn_rtx (old_loc, NULL_RTX,
3920 adjust_cleared_regs,
3921 (void *) cleared_regs);
3922 if (old_loc != INSN_VAR_LOCATION_LOC (insn))
3923 df_insn_rescan (insn);
3924 }
3925 }
3926 }
3927
3928 /* A pass over indirect jumps, converting simple cases to direct jumps.
3929 Combine does this optimization too, but only within a basic block. */
3930 static void
indirect_jump_optimize(void)3931 indirect_jump_optimize (void)
3932 {
3933 basic_block bb;
3934 bool rebuild_p = false;
3935
3936 FOR_EACH_BB_REVERSE_FN (bb, cfun)
3937 {
3938 rtx_insn *insn = BB_END (bb);
3939 if (!JUMP_P (insn)
3940 || find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
3941 continue;
3942
3943 rtx x = pc_set (insn);
3944 if (!x || !REG_P (SET_SRC (x)))
3945 continue;
3946
3947 int regno = REGNO (SET_SRC (x));
3948 if (DF_REG_DEF_COUNT (regno) == 1)
3949 {
3950 df_ref def = DF_REG_DEF_CHAIN (regno);
3951 if (!DF_REF_IS_ARTIFICIAL (def))
3952 {
3953 rtx_insn *def_insn = DF_REF_INSN (def);
3954 rtx lab = NULL_RTX;
3955 rtx set = single_set (def_insn);
3956 if (set && GET_CODE (SET_SRC (set)) == LABEL_REF)
3957 lab = SET_SRC (set);
3958 else
3959 {
3960 rtx eqnote = find_reg_note (def_insn, REG_EQUAL, NULL_RTX);
3961 if (eqnote && GET_CODE (XEXP (eqnote, 0)) == LABEL_REF)
3962 lab = XEXP (eqnote, 0);
3963 }
3964 if (lab && validate_replace_rtx (SET_SRC (x), lab, insn))
3965 rebuild_p = true;
3966 }
3967 }
3968 }
3969
3970 if (rebuild_p)
3971 {
3972 timevar_push (TV_JUMP);
3973 rebuild_jump_labels (get_insns ());
3974 if (purge_all_dead_edges ())
3975 delete_unreachable_blocks ();
3976 timevar_pop (TV_JUMP);
3977 }
3978 }
3979
3980 /* Set up fields memory, constant, and invariant from init_insns in
3981 the structures of array ira_reg_equiv. */
3982 static void
setup_reg_equiv(void)3983 setup_reg_equiv (void)
3984 {
3985 int i;
3986 rtx_insn_list *elem, *prev_elem, *next_elem;
3987 rtx_insn *insn;
3988 rtx set, x;
3989
3990 for (i = FIRST_PSEUDO_REGISTER; i < ira_reg_equiv_len; i++)
3991 for (prev_elem = NULL, elem = ira_reg_equiv[i].init_insns;
3992 elem;
3993 prev_elem = elem, elem = next_elem)
3994 {
3995 next_elem = elem->next ();
3996 insn = elem->insn ();
3997 set = single_set (insn);
3998
3999 /* Init insns can set up equivalence when the reg is a destination or
4000 a source (in this case the destination is memory). */
4001 if (set != 0 && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))))
4002 {
4003 if ((x = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != NULL)
4004 {
4005 x = XEXP (x, 0);
4006 if (REG_P (SET_DEST (set))
4007 && REGNO (SET_DEST (set)) == (unsigned int) i
4008 && ! rtx_equal_p (SET_SRC (set), x) && MEM_P (x))
4009 {
4010 /* This insn reporting the equivalence but
4011 actually not setting it. Remove it from the
4012 list. */
4013 if (prev_elem == NULL)
4014 ira_reg_equiv[i].init_insns = next_elem;
4015 else
4016 XEXP (prev_elem, 1) = next_elem;
4017 elem = prev_elem;
4018 }
4019 }
4020 else if (REG_P (SET_DEST (set))
4021 && REGNO (SET_DEST (set)) == (unsigned int) i)
4022 x = SET_SRC (set);
4023 else
4024 {
4025 gcc_assert (REG_P (SET_SRC (set))
4026 && REGNO (SET_SRC (set)) == (unsigned int) i);
4027 x = SET_DEST (set);
4028 }
4029 if (! function_invariant_p (x)
4030 || ! flag_pic
4031 /* A function invariant is often CONSTANT_P but may
4032 include a register. We promise to only pass
4033 CONSTANT_P objects to LEGITIMATE_PIC_OPERAND_P. */
4034 || (CONSTANT_P (x) && LEGITIMATE_PIC_OPERAND_P (x)))
4035 {
4036 /* It can happen that a REG_EQUIV note contains a MEM
4037 that is not a legitimate memory operand. As later
4038 stages of reload assume that all addresses found in
4039 the lra_regno_equiv_* arrays were originally
4040 legitimate, we ignore such REG_EQUIV notes. */
4041 if (memory_operand (x, VOIDmode))
4042 {
4043 ira_reg_equiv[i].defined_p = true;
4044 ira_reg_equiv[i].memory = x;
4045 continue;
4046 }
4047 else if (function_invariant_p (x))
4048 {
4049 machine_mode mode;
4050
4051 mode = GET_MODE (SET_DEST (set));
4052 if (GET_CODE (x) == PLUS
4053 || x == frame_pointer_rtx || x == arg_pointer_rtx)
4054 /* This is PLUS of frame pointer and a constant,
4055 or fp, or argp. */
4056 ira_reg_equiv[i].invariant = x;
4057 else if (targetm.legitimate_constant_p (mode, x))
4058 ira_reg_equiv[i].constant = x;
4059 else
4060 {
4061 ira_reg_equiv[i].memory = force_const_mem (mode, x);
4062 if (ira_reg_equiv[i].memory == NULL_RTX)
4063 {
4064 ira_reg_equiv[i].defined_p = false;
4065 ira_reg_equiv[i].init_insns = NULL;
4066 break;
4067 }
4068 }
4069 ira_reg_equiv[i].defined_p = true;
4070 continue;
4071 }
4072 }
4073 }
4074 ira_reg_equiv[i].defined_p = false;
4075 ira_reg_equiv[i].init_insns = NULL;
4076 break;
4077 }
4078 }
4079
4080
4081
4082 /* Print chain C to FILE. */
4083 static void
print_insn_chain(FILE * file,class insn_chain * c)4084 print_insn_chain (FILE *file, class insn_chain *c)
4085 {
4086 fprintf (file, "insn=%d, ", INSN_UID (c->insn));
4087 bitmap_print (file, &c->live_throughout, "live_throughout: ", ", ");
4088 bitmap_print (file, &c->dead_or_set, "dead_or_set: ", "\n");
4089 }
4090
4091
4092 /* Print all reload_insn_chains to FILE. */
4093 static void
print_insn_chains(FILE * file)4094 print_insn_chains (FILE *file)
4095 {
4096 class insn_chain *c;
4097 for (c = reload_insn_chain; c ; c = c->next)
4098 print_insn_chain (file, c);
4099 }
4100
4101 /* Return true if pseudo REGNO should be added to set live_throughout
4102 or dead_or_set of the insn chains for reload consideration. */
4103 static bool
pseudo_for_reload_consideration_p(int regno)4104 pseudo_for_reload_consideration_p (int regno)
4105 {
4106 /* Consider spilled pseudos too for IRA because they still have a
4107 chance to get hard-registers in the reload when IRA is used. */
4108 return (reg_renumber[regno] >= 0 || ira_conflicts_p);
4109 }
4110
4111 /* Return true if we can track the individual bytes of subreg X.
4112 When returning true, set *OUTER_SIZE to the number of bytes in
4113 X itself, *INNER_SIZE to the number of bytes in the inner register
4114 and *START to the offset of the first byte. */
4115 static bool
get_subreg_tracking_sizes(rtx x,HOST_WIDE_INT * outer_size,HOST_WIDE_INT * inner_size,HOST_WIDE_INT * start)4116 get_subreg_tracking_sizes (rtx x, HOST_WIDE_INT *outer_size,
4117 HOST_WIDE_INT *inner_size, HOST_WIDE_INT *start)
4118 {
4119 rtx reg = regno_reg_rtx[REGNO (SUBREG_REG (x))];
4120 return (GET_MODE_SIZE (GET_MODE (x)).is_constant (outer_size)
4121 && GET_MODE_SIZE (GET_MODE (reg)).is_constant (inner_size)
4122 && SUBREG_BYTE (x).is_constant (start));
4123 }
4124
4125 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] for
4126 a register with SIZE bytes, making the register live if INIT_VALUE. */
4127 static void
init_live_subregs(bool init_value,sbitmap * live_subregs,bitmap live_subregs_used,int allocnum,int size)4128 init_live_subregs (bool init_value, sbitmap *live_subregs,
4129 bitmap live_subregs_used, int allocnum, int size)
4130 {
4131 gcc_assert (size > 0);
4132
4133 /* Been there, done that. */
4134 if (bitmap_bit_p (live_subregs_used, allocnum))
4135 return;
4136
4137 /* Create a new one. */
4138 if (live_subregs[allocnum] == NULL)
4139 live_subregs[allocnum] = sbitmap_alloc (size);
4140
4141 /* If the entire reg was live before blasting into subregs, we need
4142 to init all of the subregs to ones else init to 0. */
4143 if (init_value)
4144 bitmap_ones (live_subregs[allocnum]);
4145 else
4146 bitmap_clear (live_subregs[allocnum]);
4147
4148 bitmap_set_bit (live_subregs_used, allocnum);
4149 }
4150
4151 /* Walk the insns of the current function and build reload_insn_chain,
4152 and record register life information. */
4153 static void
build_insn_chain(void)4154 build_insn_chain (void)
4155 {
4156 unsigned int i;
4157 class insn_chain **p = &reload_insn_chain;
4158 basic_block bb;
4159 class insn_chain *c = NULL;
4160 class insn_chain *next = NULL;
4161 auto_bitmap live_relevant_regs;
4162 auto_bitmap elim_regset;
4163 /* live_subregs is a vector used to keep accurate information about
4164 which hardregs are live in multiword pseudos. live_subregs and
4165 live_subregs_used are indexed by pseudo number. The live_subreg
4166 entry for a particular pseudo is only used if the corresponding
4167 element is non zero in live_subregs_used. The sbitmap size of
4168 live_subreg[allocno] is number of bytes that the pseudo can
4169 occupy. */
4170 sbitmap *live_subregs = XCNEWVEC (sbitmap, max_regno);
4171 auto_bitmap live_subregs_used;
4172
4173 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4174 if (TEST_HARD_REG_BIT (eliminable_regset, i))
4175 bitmap_set_bit (elim_regset, i);
4176 FOR_EACH_BB_REVERSE_FN (bb, cfun)
4177 {
4178 bitmap_iterator bi;
4179 rtx_insn *insn;
4180
4181 CLEAR_REG_SET (live_relevant_regs);
4182 bitmap_clear (live_subregs_used);
4183
4184 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb), 0, i, bi)
4185 {
4186 if (i >= FIRST_PSEUDO_REGISTER)
4187 break;
4188 bitmap_set_bit (live_relevant_regs, i);
4189 }
4190
4191 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb),
4192 FIRST_PSEUDO_REGISTER, i, bi)
4193 {
4194 if (pseudo_for_reload_consideration_p (i))
4195 bitmap_set_bit (live_relevant_regs, i);
4196 }
4197
4198 FOR_BB_INSNS_REVERSE (bb, insn)
4199 {
4200 if (!NOTE_P (insn) && !BARRIER_P (insn))
4201 {
4202 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4203 df_ref def, use;
4204
4205 c = new_insn_chain ();
4206 c->next = next;
4207 next = c;
4208 *p = c;
4209 p = &c->prev;
4210
4211 c->insn = insn;
4212 c->block = bb->index;
4213
4214 if (NONDEBUG_INSN_P (insn))
4215 FOR_EACH_INSN_INFO_DEF (def, insn_info)
4216 {
4217 unsigned int regno = DF_REF_REGNO (def);
4218
4219 /* Ignore may clobbers because these are generated
4220 from calls. However, every other kind of def is
4221 added to dead_or_set. */
4222 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
4223 {
4224 if (regno < FIRST_PSEUDO_REGISTER)
4225 {
4226 if (!fixed_regs[regno])
4227 bitmap_set_bit (&c->dead_or_set, regno);
4228 }
4229 else if (pseudo_for_reload_consideration_p (regno))
4230 bitmap_set_bit (&c->dead_or_set, regno);
4231 }
4232
4233 if ((regno < FIRST_PSEUDO_REGISTER
4234 || reg_renumber[regno] >= 0
4235 || ira_conflicts_p)
4236 && (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)))
4237 {
4238 rtx reg = DF_REF_REG (def);
4239 HOST_WIDE_INT outer_size, inner_size, start;
4240
4241 /* We can usually track the liveness of individual
4242 bytes within a subreg. The only exceptions are
4243 subregs wrapped in ZERO_EXTRACTs and subregs whose
4244 size is not known; in those cases we need to be
4245 conservative and treat the definition as a partial
4246 definition of the full register rather than a full
4247 definition of a specific part of the register. */
4248 if (GET_CODE (reg) == SUBREG
4249 && !DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT)
4250 && get_subreg_tracking_sizes (reg, &outer_size,
4251 &inner_size, &start))
4252 {
4253 HOST_WIDE_INT last = start + outer_size;
4254
4255 init_live_subregs
4256 (bitmap_bit_p (live_relevant_regs, regno),
4257 live_subregs, live_subregs_used, regno,
4258 inner_size);
4259
4260 if (!DF_REF_FLAGS_IS_SET
4261 (def, DF_REF_STRICT_LOW_PART))
4262 {
4263 /* Expand the range to cover entire words.
4264 Bytes added here are "don't care". */
4265 start
4266 = start / UNITS_PER_WORD * UNITS_PER_WORD;
4267 last = ((last + UNITS_PER_WORD - 1)
4268 / UNITS_PER_WORD * UNITS_PER_WORD);
4269 }
4270
4271 /* Ignore the paradoxical bits. */
4272 if (last > SBITMAP_SIZE (live_subregs[regno]))
4273 last = SBITMAP_SIZE (live_subregs[regno]);
4274
4275 while (start < last)
4276 {
4277 bitmap_clear_bit (live_subregs[regno], start);
4278 start++;
4279 }
4280
4281 if (bitmap_empty_p (live_subregs[regno]))
4282 {
4283 bitmap_clear_bit (live_subregs_used, regno);
4284 bitmap_clear_bit (live_relevant_regs, regno);
4285 }
4286 else
4287 /* Set live_relevant_regs here because
4288 that bit has to be true to get us to
4289 look at the live_subregs fields. */
4290 bitmap_set_bit (live_relevant_regs, regno);
4291 }
4292 else
4293 {
4294 /* DF_REF_PARTIAL is generated for
4295 subregs, STRICT_LOW_PART, and
4296 ZERO_EXTRACT. We handle the subreg
4297 case above so here we have to keep from
4298 modeling the def as a killing def. */
4299 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL))
4300 {
4301 bitmap_clear_bit (live_subregs_used, regno);
4302 bitmap_clear_bit (live_relevant_regs, regno);
4303 }
4304 }
4305 }
4306 }
4307
4308 bitmap_and_compl_into (live_relevant_regs, elim_regset);
4309 bitmap_copy (&c->live_throughout, live_relevant_regs);
4310
4311 if (NONDEBUG_INSN_P (insn))
4312 FOR_EACH_INSN_INFO_USE (use, insn_info)
4313 {
4314 unsigned int regno = DF_REF_REGNO (use);
4315 rtx reg = DF_REF_REG (use);
4316
4317 /* DF_REF_READ_WRITE on a use means that this use
4318 is fabricated from a def that is a partial set
4319 to a multiword reg. Here, we only model the
4320 subreg case that is not wrapped in ZERO_EXTRACT
4321 precisely so we do not need to look at the
4322 fabricated use. */
4323 if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE)
4324 && !DF_REF_FLAGS_IS_SET (use, DF_REF_ZERO_EXTRACT)
4325 && DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG))
4326 continue;
4327
4328 /* Add the last use of each var to dead_or_set. */
4329 if (!bitmap_bit_p (live_relevant_regs, regno))
4330 {
4331 if (regno < FIRST_PSEUDO_REGISTER)
4332 {
4333 if (!fixed_regs[regno])
4334 bitmap_set_bit (&c->dead_or_set, regno);
4335 }
4336 else if (pseudo_for_reload_consideration_p (regno))
4337 bitmap_set_bit (&c->dead_or_set, regno);
4338 }
4339
4340 if (regno < FIRST_PSEUDO_REGISTER
4341 || pseudo_for_reload_consideration_p (regno))
4342 {
4343 HOST_WIDE_INT outer_size, inner_size, start;
4344 if (GET_CODE (reg) == SUBREG
4345 && !DF_REF_FLAGS_IS_SET (use,
4346 DF_REF_SIGN_EXTRACT
4347 | DF_REF_ZERO_EXTRACT)
4348 && get_subreg_tracking_sizes (reg, &outer_size,
4349 &inner_size, &start))
4350 {
4351 HOST_WIDE_INT last = start + outer_size;
4352
4353 init_live_subregs
4354 (bitmap_bit_p (live_relevant_regs, regno),
4355 live_subregs, live_subregs_used, regno,
4356 inner_size);
4357
4358 /* Ignore the paradoxical bits. */
4359 if (last > SBITMAP_SIZE (live_subregs[regno]))
4360 last = SBITMAP_SIZE (live_subregs[regno]);
4361
4362 while (start < last)
4363 {
4364 bitmap_set_bit (live_subregs[regno], start);
4365 start++;
4366 }
4367 }
4368 else
4369 /* Resetting the live_subregs_used is
4370 effectively saying do not use the subregs
4371 because we are reading the whole
4372 pseudo. */
4373 bitmap_clear_bit (live_subregs_used, regno);
4374 bitmap_set_bit (live_relevant_regs, regno);
4375 }
4376 }
4377 }
4378 }
4379
4380 /* FIXME!! The following code is a disaster. Reload needs to see the
4381 labels and jump tables that are just hanging out in between
4382 the basic blocks. See pr33676. */
4383 insn = BB_HEAD (bb);
4384
4385 /* Skip over the barriers and cruft. */
4386 while (insn && (BARRIER_P (insn) || NOTE_P (insn)
4387 || BLOCK_FOR_INSN (insn) == bb))
4388 insn = PREV_INSN (insn);
4389
4390 /* While we add anything except barriers and notes, the focus is
4391 to get the labels and jump tables into the
4392 reload_insn_chain. */
4393 while (insn)
4394 {
4395 if (!NOTE_P (insn) && !BARRIER_P (insn))
4396 {
4397 if (BLOCK_FOR_INSN (insn))
4398 break;
4399
4400 c = new_insn_chain ();
4401 c->next = next;
4402 next = c;
4403 *p = c;
4404 p = &c->prev;
4405
4406 /* The block makes no sense here, but it is what the old
4407 code did. */
4408 c->block = bb->index;
4409 c->insn = insn;
4410 bitmap_copy (&c->live_throughout, live_relevant_regs);
4411 }
4412 insn = PREV_INSN (insn);
4413 }
4414 }
4415
4416 reload_insn_chain = c;
4417 *p = NULL;
4418
4419 for (i = 0; i < (unsigned int) max_regno; i++)
4420 if (live_subregs[i] != NULL)
4421 sbitmap_free (live_subregs[i]);
4422 free (live_subregs);
4423
4424 if (dump_file)
4425 print_insn_chains (dump_file);
4426 }
4427
4428 /* Examine the rtx found in *LOC, which is read or written to as determined
4429 by TYPE. Return false if we find a reason why an insn containing this
4430 rtx should not be moved (such as accesses to non-constant memory), true
4431 otherwise. */
4432 static bool
rtx_moveable_p(rtx * loc,enum op_type type)4433 rtx_moveable_p (rtx *loc, enum op_type type)
4434 {
4435 const char *fmt;
4436 rtx x = *loc;
4437 int i, j;
4438
4439 enum rtx_code code = GET_CODE (x);
4440 switch (code)
4441 {
4442 case CONST:
4443 CASE_CONST_ANY:
4444 case SYMBOL_REF:
4445 case LABEL_REF:
4446 return true;
4447
4448 case PC:
4449 return type == OP_IN;
4450
4451 case CC0:
4452 return false;
4453
4454 case REG:
4455 if (x == frame_pointer_rtx)
4456 return true;
4457 if (HARD_REGISTER_P (x))
4458 return false;
4459
4460 return true;
4461
4462 case MEM:
4463 if (type == OP_IN && MEM_READONLY_P (x))
4464 return rtx_moveable_p (&XEXP (x, 0), OP_IN);
4465 return false;
4466
4467 case SET:
4468 return (rtx_moveable_p (&SET_SRC (x), OP_IN)
4469 && rtx_moveable_p (&SET_DEST (x), OP_OUT));
4470
4471 case STRICT_LOW_PART:
4472 return rtx_moveable_p (&XEXP (x, 0), OP_OUT);
4473
4474 case ZERO_EXTRACT:
4475 case SIGN_EXTRACT:
4476 return (rtx_moveable_p (&XEXP (x, 0), type)
4477 && rtx_moveable_p (&XEXP (x, 1), OP_IN)
4478 && rtx_moveable_p (&XEXP (x, 2), OP_IN));
4479
4480 case CLOBBER:
4481 return rtx_moveable_p (&SET_DEST (x), OP_OUT);
4482
4483 case UNSPEC_VOLATILE:
4484 /* It is a bad idea to consider insns with such rtl
4485 as moveable ones. The insn scheduler also considers them as barrier
4486 for a reason. */
4487 return false;
4488
4489 case ASM_OPERANDS:
4490 /* The same is true for volatile asm: it has unknown side effects, it
4491 cannot be moved at will. */
4492 if (MEM_VOLATILE_P (x))
4493 return false;
4494
4495 default:
4496 break;
4497 }
4498
4499 fmt = GET_RTX_FORMAT (code);
4500 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4501 {
4502 if (fmt[i] == 'e')
4503 {
4504 if (!rtx_moveable_p (&XEXP (x, i), type))
4505 return false;
4506 }
4507 else if (fmt[i] == 'E')
4508 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4509 {
4510 if (!rtx_moveable_p (&XVECEXP (x, i, j), type))
4511 return false;
4512 }
4513 }
4514 return true;
4515 }
4516
4517 /* A wrapper around dominated_by_p, which uses the information in UID_LUID
4518 to give dominance relationships between two insns I1 and I2. */
4519 static bool
insn_dominated_by_p(rtx i1,rtx i2,int * uid_luid)4520 insn_dominated_by_p (rtx i1, rtx i2, int *uid_luid)
4521 {
4522 basic_block bb1 = BLOCK_FOR_INSN (i1);
4523 basic_block bb2 = BLOCK_FOR_INSN (i2);
4524
4525 if (bb1 == bb2)
4526 return uid_luid[INSN_UID (i2)] < uid_luid[INSN_UID (i1)];
4527 return dominated_by_p (CDI_DOMINATORS, bb1, bb2);
4528 }
4529
4530 /* Record the range of register numbers added by find_moveable_pseudos. */
4531 int first_moveable_pseudo, last_moveable_pseudo;
4532
4533 /* These two vectors hold data for every register added by
4534 find_movable_pseudos, with index 0 holding data for the
4535 first_moveable_pseudo. */
4536 /* The original home register. */
4537 static vec<rtx> pseudo_replaced_reg;
4538
4539 /* Look for instances where we have an instruction that is known to increase
4540 register pressure, and whose result is not used immediately. If it is
4541 possible to move the instruction downwards to just before its first use,
4542 split its lifetime into two ranges. We create a new pseudo to compute the
4543 value, and emit a move instruction just before the first use. If, after
4544 register allocation, the new pseudo remains unallocated, the function
4545 move_unallocated_pseudos then deletes the move instruction and places
4546 the computation just before the first use.
4547
4548 Such a move is safe and profitable if all the input registers remain live
4549 and unchanged between the original computation and its first use. In such
4550 a situation, the computation is known to increase register pressure, and
4551 moving it is known to at least not worsen it.
4552
4553 We restrict moves to only those cases where a register remains unallocated,
4554 in order to avoid interfering too much with the instruction schedule. As
4555 an exception, we may move insns which only modify their input register
4556 (typically induction variables), as this increases the freedom for our
4557 intended transformation, and does not limit the second instruction
4558 scheduler pass. */
4559
4560 static void
find_moveable_pseudos(void)4561 find_moveable_pseudos (void)
4562 {
4563 unsigned i;
4564 int max_regs = max_reg_num ();
4565 int max_uid = get_max_uid ();
4566 basic_block bb;
4567 int *uid_luid = XNEWVEC (int, max_uid);
4568 rtx_insn **closest_uses = XNEWVEC (rtx_insn *, max_regs);
4569 /* A set of registers which are live but not modified throughout a block. */
4570 bitmap_head *bb_transp_live = XNEWVEC (bitmap_head,
4571 last_basic_block_for_fn (cfun));
4572 /* A set of registers which only exist in a given basic block. */
4573 bitmap_head *bb_local = XNEWVEC (bitmap_head,
4574 last_basic_block_for_fn (cfun));
4575 /* A set of registers which are set once, in an instruction that can be
4576 moved freely downwards, but are otherwise transparent to a block. */
4577 bitmap_head *bb_moveable_reg_sets = XNEWVEC (bitmap_head,
4578 last_basic_block_for_fn (cfun));
4579 auto_bitmap live, used, set, interesting, unusable_as_input;
4580 bitmap_iterator bi;
4581
4582 first_moveable_pseudo = max_regs;
4583 pseudo_replaced_reg.release ();
4584 pseudo_replaced_reg.safe_grow_cleared (max_regs, true);
4585
4586 df_analyze ();
4587 calculate_dominance_info (CDI_DOMINATORS);
4588
4589 i = 0;
4590 FOR_EACH_BB_FN (bb, cfun)
4591 {
4592 rtx_insn *insn;
4593 bitmap transp = bb_transp_live + bb->index;
4594 bitmap moveable = bb_moveable_reg_sets + bb->index;
4595 bitmap local = bb_local + bb->index;
4596
4597 bitmap_initialize (local, 0);
4598 bitmap_initialize (transp, 0);
4599 bitmap_initialize (moveable, 0);
4600 bitmap_copy (live, df_get_live_out (bb));
4601 bitmap_and_into (live, df_get_live_in (bb));
4602 bitmap_copy (transp, live);
4603 bitmap_clear (moveable);
4604 bitmap_clear (live);
4605 bitmap_clear (used);
4606 bitmap_clear (set);
4607 FOR_BB_INSNS (bb, insn)
4608 if (NONDEBUG_INSN_P (insn))
4609 {
4610 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4611 df_ref def, use;
4612
4613 uid_luid[INSN_UID (insn)] = i++;
4614
4615 def = df_single_def (insn_info);
4616 use = df_single_use (insn_info);
4617 if (use
4618 && def
4619 && DF_REF_REGNO (use) == DF_REF_REGNO (def)
4620 && !bitmap_bit_p (set, DF_REF_REGNO (use))
4621 && rtx_moveable_p (&PATTERN (insn), OP_IN))
4622 {
4623 unsigned regno = DF_REF_REGNO (use);
4624 bitmap_set_bit (moveable, regno);
4625 bitmap_set_bit (set, regno);
4626 bitmap_set_bit (used, regno);
4627 bitmap_clear_bit (transp, regno);
4628 continue;
4629 }
4630 FOR_EACH_INSN_INFO_USE (use, insn_info)
4631 {
4632 unsigned regno = DF_REF_REGNO (use);
4633 bitmap_set_bit (used, regno);
4634 if (bitmap_clear_bit (moveable, regno))
4635 bitmap_clear_bit (transp, regno);
4636 }
4637
4638 FOR_EACH_INSN_INFO_DEF (def, insn_info)
4639 {
4640 unsigned regno = DF_REF_REGNO (def);
4641 bitmap_set_bit (set, regno);
4642 bitmap_clear_bit (transp, regno);
4643 bitmap_clear_bit (moveable, regno);
4644 }
4645 }
4646 }
4647
4648 FOR_EACH_BB_FN (bb, cfun)
4649 {
4650 bitmap local = bb_local + bb->index;
4651 rtx_insn *insn;
4652
4653 FOR_BB_INSNS (bb, insn)
4654 if (NONDEBUG_INSN_P (insn))
4655 {
4656 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4657 rtx_insn *def_insn;
4658 rtx closest_use, note;
4659 df_ref def, use;
4660 unsigned regno;
4661 bool all_dominated, all_local;
4662 machine_mode mode;
4663
4664 def = df_single_def (insn_info);
4665 /* There must be exactly one def in this insn. */
4666 if (!def || !single_set (insn))
4667 continue;
4668 /* This must be the only definition of the reg. We also limit
4669 which modes we deal with so that we can assume we can generate
4670 move instructions. */
4671 regno = DF_REF_REGNO (def);
4672 mode = GET_MODE (DF_REF_REG (def));
4673 if (DF_REG_DEF_COUNT (regno) != 1
4674 || !DF_REF_INSN_INFO (def)
4675 || HARD_REGISTER_NUM_P (regno)
4676 || DF_REG_EQ_USE_COUNT (regno) > 0
4677 || (!INTEGRAL_MODE_P (mode)
4678 && !FLOAT_MODE_P (mode)
4679 && !OPAQUE_MODE_P (mode)))
4680 continue;
4681 def_insn = DF_REF_INSN (def);
4682
4683 for (note = REG_NOTES (def_insn); note; note = XEXP (note, 1))
4684 if (REG_NOTE_KIND (note) == REG_EQUIV && MEM_P (XEXP (note, 0)))
4685 break;
4686
4687 if (note)
4688 {
4689 if (dump_file)
4690 fprintf (dump_file, "Ignoring reg %d, has equiv memory\n",
4691 regno);
4692 bitmap_set_bit (unusable_as_input, regno);
4693 continue;
4694 }
4695
4696 use = DF_REG_USE_CHAIN (regno);
4697 all_dominated = true;
4698 all_local = true;
4699 closest_use = NULL_RTX;
4700 for (; use; use = DF_REF_NEXT_REG (use))
4701 {
4702 rtx_insn *insn;
4703 if (!DF_REF_INSN_INFO (use))
4704 {
4705 all_dominated = false;
4706 all_local = false;
4707 break;
4708 }
4709 insn = DF_REF_INSN (use);
4710 if (DEBUG_INSN_P (insn))
4711 continue;
4712 if (BLOCK_FOR_INSN (insn) != BLOCK_FOR_INSN (def_insn))
4713 all_local = false;
4714 if (!insn_dominated_by_p (insn, def_insn, uid_luid))
4715 all_dominated = false;
4716 if (closest_use != insn && closest_use != const0_rtx)
4717 {
4718 if (closest_use == NULL_RTX)
4719 closest_use = insn;
4720 else if (insn_dominated_by_p (closest_use, insn, uid_luid))
4721 closest_use = insn;
4722 else if (!insn_dominated_by_p (insn, closest_use, uid_luid))
4723 closest_use = const0_rtx;
4724 }
4725 }
4726 if (!all_dominated)
4727 {
4728 if (dump_file)
4729 fprintf (dump_file, "Reg %d not all uses dominated by set\n",
4730 regno);
4731 continue;
4732 }
4733 if (all_local)
4734 bitmap_set_bit (local, regno);
4735 if (closest_use == const0_rtx || closest_use == NULL
4736 || next_nonnote_nondebug_insn (def_insn) == closest_use)
4737 {
4738 if (dump_file)
4739 fprintf (dump_file, "Reg %d uninteresting%s\n", regno,
4740 closest_use == const0_rtx || closest_use == NULL
4741 ? " (no unique first use)" : "");
4742 continue;
4743 }
4744 if (HAVE_cc0 && reg_referenced_p (cc0_rtx, PATTERN (closest_use)))
4745 {
4746 if (dump_file)
4747 fprintf (dump_file, "Reg %d: closest user uses cc0\n",
4748 regno);
4749 continue;
4750 }
4751
4752 bitmap_set_bit (interesting, regno);
4753 /* If we get here, we know closest_use is a non-NULL insn
4754 (as opposed to const_0_rtx). */
4755 closest_uses[regno] = as_a <rtx_insn *> (closest_use);
4756
4757 if (dump_file && (all_local || all_dominated))
4758 {
4759 fprintf (dump_file, "Reg %u:", regno);
4760 if (all_local)
4761 fprintf (dump_file, " local to bb %d", bb->index);
4762 if (all_dominated)
4763 fprintf (dump_file, " def dominates all uses");
4764 if (closest_use != const0_rtx)
4765 fprintf (dump_file, " has unique first use");
4766 fputs ("\n", dump_file);
4767 }
4768 }
4769 }
4770
4771 EXECUTE_IF_SET_IN_BITMAP (interesting, 0, i, bi)
4772 {
4773 df_ref def = DF_REG_DEF_CHAIN (i);
4774 rtx_insn *def_insn = DF_REF_INSN (def);
4775 basic_block def_block = BLOCK_FOR_INSN (def_insn);
4776 bitmap def_bb_local = bb_local + def_block->index;
4777 bitmap def_bb_moveable = bb_moveable_reg_sets + def_block->index;
4778 bitmap def_bb_transp = bb_transp_live + def_block->index;
4779 bool local_to_bb_p = bitmap_bit_p (def_bb_local, i);
4780 rtx_insn *use_insn = closest_uses[i];
4781 df_ref use;
4782 bool all_ok = true;
4783 bool all_transp = true;
4784
4785 if (!REG_P (DF_REF_REG (def)))
4786 continue;
4787
4788 if (!local_to_bb_p)
4789 {
4790 if (dump_file)
4791 fprintf (dump_file, "Reg %u not local to one basic block\n",
4792 i);
4793 continue;
4794 }
4795 if (reg_equiv_init (i) != NULL_RTX)
4796 {
4797 if (dump_file)
4798 fprintf (dump_file, "Ignoring reg %u with equiv init insn\n",
4799 i);
4800 continue;
4801 }
4802 if (!rtx_moveable_p (&PATTERN (def_insn), OP_IN))
4803 {
4804 if (dump_file)
4805 fprintf (dump_file, "Found def insn %d for %d to be not moveable\n",
4806 INSN_UID (def_insn), i);
4807 continue;
4808 }
4809 if (dump_file)
4810 fprintf (dump_file, "Examining insn %d, def for %d\n",
4811 INSN_UID (def_insn), i);
4812 FOR_EACH_INSN_USE (use, def_insn)
4813 {
4814 unsigned regno = DF_REF_REGNO (use);
4815 if (bitmap_bit_p (unusable_as_input, regno))
4816 {
4817 all_ok = false;
4818 if (dump_file)
4819 fprintf (dump_file, " found unusable input reg %u.\n", regno);
4820 break;
4821 }
4822 if (!bitmap_bit_p (def_bb_transp, regno))
4823 {
4824 if (bitmap_bit_p (def_bb_moveable, regno)
4825 && !control_flow_insn_p (use_insn)
4826 && (!HAVE_cc0 || !sets_cc0_p (use_insn)))
4827 {
4828 if (modified_between_p (DF_REF_REG (use), def_insn, use_insn))
4829 {
4830 rtx_insn *x = NEXT_INSN (def_insn);
4831 while (!modified_in_p (DF_REF_REG (use), x))
4832 {
4833 gcc_assert (x != use_insn);
4834 x = NEXT_INSN (x);
4835 }
4836 if (dump_file)
4837 fprintf (dump_file, " input reg %u modified but insn %d moveable\n",
4838 regno, INSN_UID (x));
4839 emit_insn_after (PATTERN (x), use_insn);
4840 set_insn_deleted (x);
4841 }
4842 else
4843 {
4844 if (dump_file)
4845 fprintf (dump_file, " input reg %u modified between def and use\n",
4846 regno);
4847 all_transp = false;
4848 }
4849 }
4850 else
4851 all_transp = false;
4852 }
4853 }
4854 if (!all_ok)
4855 continue;
4856 if (!dbg_cnt (ira_move))
4857 break;
4858 if (dump_file)
4859 fprintf (dump_file, " all ok%s\n", all_transp ? " and transp" : "");
4860
4861 if (all_transp)
4862 {
4863 rtx def_reg = DF_REF_REG (def);
4864 rtx newreg = ira_create_new_reg (def_reg);
4865 if (validate_change (def_insn, DF_REF_REAL_LOC (def), newreg, 0))
4866 {
4867 unsigned nregno = REGNO (newreg);
4868 emit_insn_before (gen_move_insn (def_reg, newreg), use_insn);
4869 nregno -= max_regs;
4870 pseudo_replaced_reg[nregno] = def_reg;
4871 }
4872 }
4873 }
4874
4875 FOR_EACH_BB_FN (bb, cfun)
4876 {
4877 bitmap_clear (bb_local + bb->index);
4878 bitmap_clear (bb_transp_live + bb->index);
4879 bitmap_clear (bb_moveable_reg_sets + bb->index);
4880 }
4881 free (uid_luid);
4882 free (closest_uses);
4883 free (bb_local);
4884 free (bb_transp_live);
4885 free (bb_moveable_reg_sets);
4886
4887 last_moveable_pseudo = max_reg_num ();
4888
4889 fix_reg_equiv_init ();
4890 expand_reg_info ();
4891 regstat_free_n_sets_and_refs ();
4892 regstat_free_ri ();
4893 regstat_init_n_sets_and_refs ();
4894 regstat_compute_ri ();
4895 free_dominance_info (CDI_DOMINATORS);
4896 }
4897
4898 /* If SET pattern SET is an assignment from a hard register to a pseudo which
4899 is live at CALL_DOM (if non-NULL, otherwise this check is omitted), return
4900 the destination. Otherwise return NULL. */
4901
4902 static rtx
interesting_dest_for_shprep_1(rtx set,basic_block call_dom)4903 interesting_dest_for_shprep_1 (rtx set, basic_block call_dom)
4904 {
4905 rtx src = SET_SRC (set);
4906 rtx dest = SET_DEST (set);
4907 if (!REG_P (src) || !HARD_REGISTER_P (src)
4908 || !REG_P (dest) || HARD_REGISTER_P (dest)
4909 || (call_dom && !bitmap_bit_p (df_get_live_in (call_dom), REGNO (dest))))
4910 return NULL;
4911 return dest;
4912 }
4913
4914 /* If insn is interesting for parameter range-splitting shrink-wrapping
4915 preparation, i.e. it is a single set from a hard register to a pseudo, which
4916 is live at CALL_DOM (if non-NULL, otherwise this check is omitted), or a
4917 parallel statement with only one such statement, return the destination.
4918 Otherwise return NULL. */
4919
4920 static rtx
interesting_dest_for_shprep(rtx_insn * insn,basic_block call_dom)4921 interesting_dest_for_shprep (rtx_insn *insn, basic_block call_dom)
4922 {
4923 if (!INSN_P (insn))
4924 return NULL;
4925 rtx pat = PATTERN (insn);
4926 if (GET_CODE (pat) == SET)
4927 return interesting_dest_for_shprep_1 (pat, call_dom);
4928
4929 if (GET_CODE (pat) != PARALLEL)
4930 return NULL;
4931 rtx ret = NULL;
4932 for (int i = 0; i < XVECLEN (pat, 0); i++)
4933 {
4934 rtx sub = XVECEXP (pat, 0, i);
4935 if (GET_CODE (sub) == USE || GET_CODE (sub) == CLOBBER)
4936 continue;
4937 if (GET_CODE (sub) != SET
4938 || side_effects_p (sub))
4939 return NULL;
4940 rtx dest = interesting_dest_for_shprep_1 (sub, call_dom);
4941 if (dest && ret)
4942 return NULL;
4943 if (dest)
4944 ret = dest;
4945 }
4946 return ret;
4947 }
4948
4949 /* Split live ranges of pseudos that are loaded from hard registers in the
4950 first BB in a BB that dominates all non-sibling call if such a BB can be
4951 found and is not in a loop. Return true if the function has made any
4952 changes. */
4953
4954 static bool
split_live_ranges_for_shrink_wrap(void)4955 split_live_ranges_for_shrink_wrap (void)
4956 {
4957 basic_block bb, call_dom = NULL;
4958 basic_block first = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
4959 rtx_insn *insn, *last_interesting_insn = NULL;
4960 auto_bitmap need_new, reachable;
4961 vec<basic_block> queue;
4962
4963 if (!SHRINK_WRAPPING_ENABLED)
4964 return false;
4965
4966 queue.create (n_basic_blocks_for_fn (cfun));
4967
4968 FOR_EACH_BB_FN (bb, cfun)
4969 FOR_BB_INSNS (bb, insn)
4970 if (CALL_P (insn) && !SIBLING_CALL_P (insn))
4971 {
4972 if (bb == first)
4973 {
4974 queue.release ();
4975 return false;
4976 }
4977
4978 bitmap_set_bit (need_new, bb->index);
4979 bitmap_set_bit (reachable, bb->index);
4980 queue.quick_push (bb);
4981 break;
4982 }
4983
4984 if (queue.is_empty ())
4985 {
4986 queue.release ();
4987 return false;
4988 }
4989
4990 while (!queue.is_empty ())
4991 {
4992 edge e;
4993 edge_iterator ei;
4994
4995 bb = queue.pop ();
4996 FOR_EACH_EDGE (e, ei, bb->succs)
4997 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
4998 && bitmap_set_bit (reachable, e->dest->index))
4999 queue.quick_push (e->dest);
5000 }
5001 queue.release ();
5002
5003 FOR_BB_INSNS (first, insn)
5004 {
5005 rtx dest = interesting_dest_for_shprep (insn, NULL);
5006 if (!dest)
5007 continue;
5008
5009 if (DF_REG_DEF_COUNT (REGNO (dest)) > 1)
5010 return false;
5011
5012 for (df_ref use = DF_REG_USE_CHAIN (REGNO(dest));
5013 use;
5014 use = DF_REF_NEXT_REG (use))
5015 {
5016 int ubbi = DF_REF_BB (use)->index;
5017 if (bitmap_bit_p (reachable, ubbi))
5018 bitmap_set_bit (need_new, ubbi);
5019 }
5020 last_interesting_insn = insn;
5021 }
5022
5023 if (!last_interesting_insn)
5024 return false;
5025
5026 call_dom = nearest_common_dominator_for_set (CDI_DOMINATORS, need_new);
5027 if (call_dom == first)
5028 return false;
5029
5030 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
5031 while (bb_loop_depth (call_dom) > 0)
5032 call_dom = get_immediate_dominator (CDI_DOMINATORS, call_dom);
5033 loop_optimizer_finalize ();
5034
5035 if (call_dom == first)
5036 return false;
5037
5038 calculate_dominance_info (CDI_POST_DOMINATORS);
5039 if (dominated_by_p (CDI_POST_DOMINATORS, first, call_dom))
5040 {
5041 free_dominance_info (CDI_POST_DOMINATORS);
5042 return false;
5043 }
5044 free_dominance_info (CDI_POST_DOMINATORS);
5045
5046 if (dump_file)
5047 fprintf (dump_file, "Will split live ranges of parameters at BB %i\n",
5048 call_dom->index);
5049
5050 bool ret = false;
5051 FOR_BB_INSNS (first, insn)
5052 {
5053 rtx dest = interesting_dest_for_shprep (insn, call_dom);
5054 if (!dest || dest == pic_offset_table_rtx)
5055 continue;
5056
5057 bool need_newreg = false;
5058 df_ref use, next;
5059 for (use = DF_REG_USE_CHAIN (REGNO (dest)); use; use = next)
5060 {
5061 rtx_insn *uin = DF_REF_INSN (use);
5062 next = DF_REF_NEXT_REG (use);
5063
5064 if (DEBUG_INSN_P (uin))
5065 continue;
5066
5067 basic_block ubb = BLOCK_FOR_INSN (uin);
5068 if (ubb == call_dom
5069 || dominated_by_p (CDI_DOMINATORS, ubb, call_dom))
5070 {
5071 need_newreg = true;
5072 break;
5073 }
5074 }
5075
5076 if (need_newreg)
5077 {
5078 rtx newreg = ira_create_new_reg (dest);
5079
5080 for (use = DF_REG_USE_CHAIN (REGNO (dest)); use; use = next)
5081 {
5082 rtx_insn *uin = DF_REF_INSN (use);
5083 next = DF_REF_NEXT_REG (use);
5084
5085 basic_block ubb = BLOCK_FOR_INSN (uin);
5086 if (ubb == call_dom
5087 || dominated_by_p (CDI_DOMINATORS, ubb, call_dom))
5088 validate_change (uin, DF_REF_REAL_LOC (use), newreg, true);
5089 }
5090
5091 rtx_insn *new_move = gen_move_insn (newreg, dest);
5092 emit_insn_after (new_move, bb_note (call_dom));
5093 if (dump_file)
5094 {
5095 fprintf (dump_file, "Split live-range of register ");
5096 print_rtl_single (dump_file, dest);
5097 }
5098 ret = true;
5099 }
5100
5101 if (insn == last_interesting_insn)
5102 break;
5103 }
5104 apply_change_group ();
5105 return ret;
5106 }
5107
5108 /* Perform the second half of the transformation started in
5109 find_moveable_pseudos. We look for instances where the newly introduced
5110 pseudo remains unallocated, and remove it by moving the definition to
5111 just before its use, replacing the move instruction generated by
5112 find_moveable_pseudos. */
5113 static void
move_unallocated_pseudos(void)5114 move_unallocated_pseudos (void)
5115 {
5116 int i;
5117 for (i = first_moveable_pseudo; i < last_moveable_pseudo; i++)
5118 if (reg_renumber[i] < 0)
5119 {
5120 int idx = i - first_moveable_pseudo;
5121 rtx other_reg = pseudo_replaced_reg[idx];
5122 /* The iterating range [first_moveable_pseudo, last_moveable_pseudo)
5123 covers every new pseudo created in find_moveable_pseudos,
5124 regardless of the validation with it is successful or not.
5125 So we need to skip the pseudos which were used in those failed
5126 validations to avoid unexpected DF info and consequent ICE.
5127 We only set pseudo_replaced_reg[] when the validation is successful
5128 in find_moveable_pseudos, it's enough to check it here. */
5129 if (!other_reg)
5130 continue;
5131 rtx_insn *def_insn = DF_REF_INSN (DF_REG_DEF_CHAIN (i));
5132 /* The use must follow all definitions of OTHER_REG, so we can
5133 insert the new definition immediately after any of them. */
5134 df_ref other_def = DF_REG_DEF_CHAIN (REGNO (other_reg));
5135 rtx_insn *move_insn = DF_REF_INSN (other_def);
5136 rtx_insn *newinsn = emit_insn_after (PATTERN (def_insn), move_insn);
5137 rtx set;
5138 int success;
5139
5140 if (dump_file)
5141 fprintf (dump_file, "moving def of %d (insn %d now) ",
5142 REGNO (other_reg), INSN_UID (def_insn));
5143
5144 delete_insn (move_insn);
5145 while ((other_def = DF_REG_DEF_CHAIN (REGNO (other_reg))))
5146 delete_insn (DF_REF_INSN (other_def));
5147 delete_insn (def_insn);
5148
5149 set = single_set (newinsn);
5150 success = validate_change (newinsn, &SET_DEST (set), other_reg, 0);
5151 gcc_assert (success);
5152 if (dump_file)
5153 fprintf (dump_file, " %d) rather than keep unallocated replacement %d\n",
5154 INSN_UID (newinsn), i);
5155 SET_REG_N_REFS (i, 0);
5156 }
5157
5158 first_moveable_pseudo = last_moveable_pseudo = 0;
5159 }
5160
5161
5162
5163 /* Code dealing with scratches (changing them onto
5164 pseudos and restoring them from the pseudos).
5165
5166 We change scratches into pseudos at the beginning of IRA to
5167 simplify dealing with them (conflicts, hard register assignments).
5168
5169 If the pseudo denoting scratch was spilled it means that we do not
5170 need a hard register for it. Such pseudos are transformed back to
5171 scratches at the end of LRA. */
5172
5173 /* Description of location of a former scratch operand. */
5174 struct sloc
5175 {
5176 rtx_insn *insn; /* Insn where the scratch was. */
5177 int nop; /* Number of the operand which was a scratch. */
5178 unsigned regno; /* regno gnerated instead of scratch */
5179 int icode; /* Original icode from which scratch was removed. */
5180 };
5181
5182 typedef struct sloc *sloc_t;
5183
5184 /* Locations of the former scratches. */
5185 static vec<sloc_t> scratches;
5186
5187 /* Bitmap of scratch regnos. */
5188 static bitmap_head scratch_bitmap;
5189
5190 /* Bitmap of scratch operands. */
5191 static bitmap_head scratch_operand_bitmap;
5192
5193 /* Return true if pseudo REGNO is made of SCRATCH. */
5194 bool
ira_former_scratch_p(int regno)5195 ira_former_scratch_p (int regno)
5196 {
5197 return bitmap_bit_p (&scratch_bitmap, regno);
5198 }
5199
5200 /* Return true if the operand NOP of INSN is a former scratch. */
5201 bool
ira_former_scratch_operand_p(rtx_insn * insn,int nop)5202 ira_former_scratch_operand_p (rtx_insn *insn, int nop)
5203 {
5204 return bitmap_bit_p (&scratch_operand_bitmap,
5205 INSN_UID (insn) * MAX_RECOG_OPERANDS + nop) != 0;
5206 }
5207
5208 /* Register operand NOP in INSN as a former scratch. It will be
5209 changed to scratch back, if it is necessary, at the LRA end. */
5210 void
ira_register_new_scratch_op(rtx_insn * insn,int nop,int icode)5211 ira_register_new_scratch_op (rtx_insn *insn, int nop, int icode)
5212 {
5213 rtx op = *recog_data.operand_loc[nop];
5214 sloc_t loc = XNEW (struct sloc);
5215 ira_assert (REG_P (op));
5216 loc->insn = insn;
5217 loc->nop = nop;
5218 loc->regno = REGNO (op);
5219 loc->icode = icode;
5220 scratches.safe_push (loc);
5221 bitmap_set_bit (&scratch_bitmap, REGNO (op));
5222 bitmap_set_bit (&scratch_operand_bitmap,
5223 INSN_UID (insn) * MAX_RECOG_OPERANDS + nop);
5224 add_reg_note (insn, REG_UNUSED, op);
5225 }
5226
5227 /* Return true if string STR contains constraint 'X'. */
5228 static bool
contains_X_constraint_p(const char * str)5229 contains_X_constraint_p (const char *str)
5230 {
5231 int c;
5232
5233 while ((c = *str))
5234 {
5235 str += CONSTRAINT_LEN (c, str);
5236 if (c == 'X') return true;
5237 }
5238 return false;
5239 }
5240
5241 /* Change INSN's scratches into pseudos and save their location.
5242 Return true if we changed any scratch. */
5243 bool
ira_remove_insn_scratches(rtx_insn * insn,bool all_p,FILE * dump_file,rtx (* get_reg)(rtx original))5244 ira_remove_insn_scratches (rtx_insn *insn, bool all_p, FILE *dump_file,
5245 rtx (*get_reg) (rtx original))
5246 {
5247 int i;
5248 bool insn_changed_p;
5249 rtx reg, *loc;
5250
5251 extract_insn (insn);
5252 insn_changed_p = false;
5253 for (i = 0; i < recog_data.n_operands; i++)
5254 {
5255 loc = recog_data.operand_loc[i];
5256 if (GET_CODE (*loc) == SCRATCH && GET_MODE (*loc) != VOIDmode)
5257 {
5258 if (! all_p && contains_X_constraint_p (recog_data.constraints[i]))
5259 continue;
5260 insn_changed_p = true;
5261 *loc = reg = get_reg (*loc);
5262 ira_register_new_scratch_op (insn, i, INSN_CODE (insn));
5263 if (ira_dump_file != NULL)
5264 fprintf (dump_file,
5265 "Removing SCRATCH to p%u in insn #%u (nop %d)\n",
5266 REGNO (reg), INSN_UID (insn), i);
5267 }
5268 }
5269 return insn_changed_p;
5270 }
5271
5272 /* Return new register of the same mode as ORIGINAL. Used in
5273 remove_scratches. */
5274 static rtx
get_scratch_reg(rtx original)5275 get_scratch_reg (rtx original)
5276 {
5277 return gen_reg_rtx (GET_MODE (original));
5278 }
5279
5280 /* Change scratches into pseudos and save their location. Return true
5281 if we changed any scratch. */
5282 static bool
remove_scratches(void)5283 remove_scratches (void)
5284 {
5285 bool change_p = false;
5286 basic_block bb;
5287 rtx_insn *insn;
5288
5289 scratches.create (get_max_uid ());
5290 bitmap_initialize (&scratch_bitmap, ®_obstack);
5291 bitmap_initialize (&scratch_operand_bitmap, ®_obstack);
5292 FOR_EACH_BB_FN (bb, cfun)
5293 FOR_BB_INSNS (bb, insn)
5294 if (INSN_P (insn)
5295 && ira_remove_insn_scratches (insn, false, ira_dump_file, get_scratch_reg))
5296 {
5297 /* Because we might use DF, we need to keep DF info up to date. */
5298 df_insn_rescan (insn);
5299 change_p = true;
5300 }
5301 return change_p;
5302 }
5303
5304 /* Changes pseudos created by function remove_scratches onto scratches. */
5305 void
ira_restore_scratches(FILE * dump_file)5306 ira_restore_scratches (FILE *dump_file)
5307 {
5308 int regno, n;
5309 unsigned i;
5310 rtx *op_loc;
5311 sloc_t loc;
5312
5313 for (i = 0; scratches.iterate (i, &loc); i++)
5314 {
5315 /* Ignore already deleted insns. */
5316 if (NOTE_P (loc->insn)
5317 && NOTE_KIND (loc->insn) == NOTE_INSN_DELETED)
5318 continue;
5319 extract_insn (loc->insn);
5320 if (loc->icode != INSN_CODE (loc->insn))
5321 {
5322 /* The icode doesn't match, which means the insn has been modified
5323 (e.g. register elimination). The scratch cannot be restored. */
5324 continue;
5325 }
5326 op_loc = recog_data.operand_loc[loc->nop];
5327 if (REG_P (*op_loc)
5328 && ((regno = REGNO (*op_loc)) >= FIRST_PSEUDO_REGISTER)
5329 && reg_renumber[regno] < 0)
5330 {
5331 /* It should be only case when scratch register with chosen
5332 constraint 'X' did not get memory or hard register. */
5333 ira_assert (ira_former_scratch_p (regno));
5334 *op_loc = gen_rtx_SCRATCH (GET_MODE (*op_loc));
5335 for (n = 0; n < recog_data.n_dups; n++)
5336 *recog_data.dup_loc[n]
5337 = *recog_data.operand_loc[(int) recog_data.dup_num[n]];
5338 if (dump_file != NULL)
5339 fprintf (dump_file, "Restoring SCRATCH in insn #%u(nop %d)\n",
5340 INSN_UID (loc->insn), loc->nop);
5341 }
5342 }
5343 for (i = 0; scratches.iterate (i, &loc); i++)
5344 free (loc);
5345 scratches.release ();
5346 bitmap_clear (&scratch_bitmap);
5347 bitmap_clear (&scratch_operand_bitmap);
5348 }
5349
5350
5351
5352 /* If the backend knows where to allocate pseudos for hard
5353 register initial values, register these allocations now. */
5354 static void
allocate_initial_values(void)5355 allocate_initial_values (void)
5356 {
5357 if (targetm.allocate_initial_value)
5358 {
5359 rtx hreg, preg, x;
5360 int i, regno;
5361
5362 for (i = 0; HARD_REGISTER_NUM_P (i); i++)
5363 {
5364 if (! initial_value_entry (i, &hreg, &preg))
5365 break;
5366
5367 x = targetm.allocate_initial_value (hreg);
5368 regno = REGNO (preg);
5369 if (x && REG_N_SETS (regno) <= 1)
5370 {
5371 if (MEM_P (x))
5372 reg_equiv_memory_loc (regno) = x;
5373 else
5374 {
5375 basic_block bb;
5376 int new_regno;
5377
5378 gcc_assert (REG_P (x));
5379 new_regno = REGNO (x);
5380 reg_renumber[regno] = new_regno;
5381 /* Poke the regno right into regno_reg_rtx so that even
5382 fixed regs are accepted. */
5383 SET_REGNO (preg, new_regno);
5384 /* Update global register liveness information. */
5385 FOR_EACH_BB_FN (bb, cfun)
5386 {
5387 if (REGNO_REG_SET_P (df_get_live_in (bb), regno))
5388 SET_REGNO_REG_SET (df_get_live_in (bb), new_regno);
5389 if (REGNO_REG_SET_P (df_get_live_out (bb), regno))
5390 SET_REGNO_REG_SET (df_get_live_out (bb), new_regno);
5391 }
5392 }
5393 }
5394 }
5395
5396 gcc_checking_assert (! initial_value_entry (FIRST_PSEUDO_REGISTER,
5397 &hreg, &preg));
5398 }
5399 }
5400
5401
5402
5403
5404 /* True when we use LRA instead of reload pass for the current
5405 function. */
5406 bool ira_use_lra_p;
5407
5408 /* True if we have allocno conflicts. It is false for non-optimized
5409 mode or when the conflict table is too big. */
5410 bool ira_conflicts_p;
5411
5412 /* Saved between IRA and reload. */
5413 static int saved_flag_ira_share_spill_slots;
5414
5415 /* This is the main entry of IRA. */
5416 static void
ira(FILE * f)5417 ira (FILE *f)
5418 {
5419 bool loops_p;
5420 int ira_max_point_before_emit;
5421 bool saved_flag_caller_saves = flag_caller_saves;
5422 enum ira_region saved_flag_ira_region = flag_ira_region;
5423 basic_block bb;
5424 edge_iterator ei;
5425 edge e;
5426 bool output_jump_reload_p = false;
5427
5428 if (ira_use_lra_p)
5429 {
5430 /* First put potential jump output reloads on the output edges
5431 as USE which will be removed at the end of LRA. The major
5432 goal is actually to create BBs for critical edges for LRA and
5433 populate them later by live info. In LRA it will be
5434 difficult to do this. */
5435 FOR_EACH_BB_FN (bb, cfun)
5436 {
5437 rtx_insn *end = BB_END (bb);
5438 if (!JUMP_P (end))
5439 continue;
5440 extract_insn (end);
5441 for (int i = 0; i < recog_data.n_operands; i++)
5442 if (recog_data.operand_type[i] != OP_IN)
5443 {
5444 bool skip_p = false;
5445 FOR_EACH_EDGE (e, ei, bb->succs)
5446 if (EDGE_CRITICAL_P (e)
5447 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
5448 && (e->flags & EDGE_ABNORMAL))
5449 {
5450 skip_p = true;
5451 break;
5452 }
5453 if (skip_p)
5454 break;
5455 output_jump_reload_p = true;
5456 FOR_EACH_EDGE (e, ei, bb->succs)
5457 if (EDGE_CRITICAL_P (e)
5458 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
5459 {
5460 start_sequence ();
5461 /* We need to put some no-op insn here. We can
5462 not put a note as commit_edges insertion will
5463 fail. */
5464 emit_insn (gen_rtx_USE (VOIDmode, const1_rtx));
5465 rtx_insn *insns = get_insns ();
5466 end_sequence ();
5467 insert_insn_on_edge (insns, e);
5468 }
5469 break;
5470 }
5471 }
5472 if (output_jump_reload_p)
5473 commit_edge_insertions ();
5474 }
5475
5476 if (flag_ira_verbose < 10)
5477 {
5478 internal_flag_ira_verbose = flag_ira_verbose;
5479 ira_dump_file = f;
5480 }
5481 else
5482 {
5483 internal_flag_ira_verbose = flag_ira_verbose - 10;
5484 ira_dump_file = stderr;
5485 }
5486
5487 clear_bb_flags ();
5488
5489 /* Determine if the current function is a leaf before running IRA
5490 since this can impact optimizations done by the prologue and
5491 epilogue thus changing register elimination offsets.
5492 Other target callbacks may use crtl->is_leaf too, including
5493 SHRINK_WRAPPING_ENABLED, so initialize as early as possible. */
5494 crtl->is_leaf = leaf_function_p ();
5495
5496 /* Perform target specific PIC register initialization. */
5497 targetm.init_pic_reg ();
5498
5499 ira_conflicts_p = optimize > 0;
5500
5501 /* Determine the number of pseudos actually requiring coloring. */
5502 unsigned int num_used_regs = 0;
5503 for (unsigned int i = FIRST_PSEUDO_REGISTER; i < DF_REG_SIZE (df); i++)
5504 if (DF_REG_DEF_COUNT (i) || DF_REG_USE_COUNT (i))
5505 num_used_regs++;
5506
5507 /* If there are too many pseudos and/or basic blocks (e.g. 10K
5508 pseudos and 10K blocks or 100K pseudos and 1K blocks), we will
5509 use simplified and faster algorithms in LRA. */
5510 lra_simple_p
5511 = ira_use_lra_p
5512 && num_used_regs >= (1U << 26) / last_basic_block_for_fn (cfun);
5513
5514 if (lra_simple_p)
5515 {
5516 /* It permits to skip live range splitting in LRA. */
5517 flag_caller_saves = false;
5518 /* There is no sense to do regional allocation when we use
5519 simplified LRA. */
5520 flag_ira_region = IRA_REGION_ONE;
5521 ira_conflicts_p = false;
5522 }
5523
5524 #ifndef IRA_NO_OBSTACK
5525 gcc_obstack_init (&ira_obstack);
5526 #endif
5527 bitmap_obstack_initialize (&ira_bitmap_obstack);
5528
5529 /* LRA uses its own infrastructure to handle caller save registers. */
5530 if (flag_caller_saves && !ira_use_lra_p)
5531 init_caller_save ();
5532
5533 setup_prohibited_mode_move_regs ();
5534 decrease_live_ranges_number ();
5535 df_note_add_problem ();
5536
5537 /* DF_LIVE can't be used in the register allocator, too many other
5538 parts of the compiler depend on using the "classic" liveness
5539 interpretation of the DF_LR problem. See PR38711.
5540 Remove the problem, so that we don't spend time updating it in
5541 any of the df_analyze() calls during IRA/LRA. */
5542 if (optimize > 1)
5543 df_remove_problem (df_live);
5544 gcc_checking_assert (df_live == NULL);
5545
5546 if (flag_checking)
5547 df->changeable_flags |= DF_VERIFY_SCHEDULED;
5548
5549 df_analyze ();
5550
5551 init_reg_equiv ();
5552 if (ira_conflicts_p)
5553 {
5554 calculate_dominance_info (CDI_DOMINATORS);
5555
5556 if (split_live_ranges_for_shrink_wrap ())
5557 df_analyze ();
5558
5559 free_dominance_info (CDI_DOMINATORS);
5560 }
5561
5562 df_clear_flags (DF_NO_INSN_RESCAN);
5563
5564 indirect_jump_optimize ();
5565 if (delete_trivially_dead_insns (get_insns (), max_reg_num ()))
5566 df_analyze ();
5567
5568 regstat_init_n_sets_and_refs ();
5569 regstat_compute_ri ();
5570
5571 /* If we are not optimizing, then this is the only place before
5572 register allocation where dataflow is done. And that is needed
5573 to generate these warnings. */
5574 if (warn_clobbered)
5575 generate_setjmp_warnings ();
5576
5577 /* update_equiv_regs can use reg classes of pseudos and they are set up in
5578 register pressure sensitive scheduling and loop invariant motion and in
5579 live range shrinking. This info can become obsolete if we add new pseudos
5580 since the last set up. Recalculate it again if the new pseudos were
5581 added. */
5582 if (resize_reg_info () && (flag_sched_pressure || flag_live_range_shrinkage
5583 || flag_ira_loop_pressure))
5584 ira_set_pseudo_classes (true, ira_dump_file);
5585
5586 init_alias_analysis ();
5587 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
5588 reg_equiv = XCNEWVEC (struct equivalence, max_reg_num ());
5589 update_equiv_regs_prescan ();
5590 update_equiv_regs ();
5591
5592 /* Don't move insns if live range shrinkage or register
5593 pressure-sensitive scheduling were done because it will not
5594 improve allocation but likely worsen insn scheduling. */
5595 if (optimize
5596 && !flag_live_range_shrinkage
5597 && !(flag_sched_pressure && flag_schedule_insns))
5598 combine_and_move_insns ();
5599
5600 /* Gather additional equivalences with memory. */
5601 if (optimize)
5602 add_store_equivs ();
5603
5604 loop_optimizer_finalize ();
5605 free_dominance_info (CDI_DOMINATORS);
5606 end_alias_analysis ();
5607 free (reg_equiv);
5608
5609 /* Once max_regno changes, we need to free and re-init/re-compute
5610 some data structures like regstat_n_sets_and_refs and reg_info_p. */
5611 auto regstat_recompute_for_max_regno = []() {
5612 regstat_free_n_sets_and_refs ();
5613 regstat_free_ri ();
5614 regstat_init_n_sets_and_refs ();
5615 regstat_compute_ri ();
5616 };
5617
5618 int max_regno_before_rm = max_reg_num ();
5619 if (ira_use_lra_p && remove_scratches ())
5620 {
5621 ira_expand_reg_equiv ();
5622 /* For now remove_scatches is supposed to create pseudos when it
5623 succeeds, assert this happens all the time. Once it doesn't
5624 hold, we should guard the regstat recompute for the case
5625 max_regno changes. */
5626 gcc_assert (max_regno_before_rm != max_reg_num ());
5627 regstat_recompute_for_max_regno ();
5628 }
5629
5630 setup_reg_equiv ();
5631 grow_reg_equivs ();
5632 setup_reg_equiv_init ();
5633
5634 allocated_reg_info_size = max_reg_num ();
5635
5636 /* It is not worth to do such improvement when we use a simple
5637 allocation because of -O0 usage or because the function is too
5638 big. */
5639 if (ira_conflicts_p)
5640 find_moveable_pseudos ();
5641
5642 max_regno_before_ira = max_reg_num ();
5643 ira_setup_eliminable_regset ();
5644
5645 ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
5646 ira_load_cost = ira_store_cost = ira_shuffle_cost = 0;
5647 ira_move_loops_num = ira_additional_jumps_num = 0;
5648
5649 ira_assert (current_loops == NULL);
5650 if (flag_ira_region == IRA_REGION_ALL || flag_ira_region == IRA_REGION_MIXED)
5651 loop_optimizer_init (AVOID_CFG_MODIFICATIONS | LOOPS_HAVE_RECORDED_EXITS);
5652
5653 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
5654 fprintf (ira_dump_file, "Building IRA IR\n");
5655 loops_p = ira_build ();
5656
5657 ira_assert (ira_conflicts_p || !loops_p);
5658
5659 saved_flag_ira_share_spill_slots = flag_ira_share_spill_slots;
5660 if (too_high_register_pressure_p () || cfun->calls_setjmp)
5661 /* It is just wasting compiler's time to pack spilled pseudos into
5662 stack slots in this case -- prohibit it. We also do this if
5663 there is setjmp call because a variable not modified between
5664 setjmp and longjmp the compiler is required to preserve its
5665 value and sharing slots does not guarantee it. */
5666 flag_ira_share_spill_slots = FALSE;
5667
5668 ira_color ();
5669
5670 ira_max_point_before_emit = ira_max_point;
5671
5672 ira_initiate_emit_data ();
5673
5674 ira_emit (loops_p);
5675
5676 max_regno = max_reg_num ();
5677 if (ira_conflicts_p)
5678 {
5679 if (! loops_p)
5680 {
5681 if (! ira_use_lra_p)
5682 ira_initiate_assign ();
5683 }
5684 else
5685 {
5686 expand_reg_info ();
5687
5688 if (ira_use_lra_p)
5689 {
5690 ira_allocno_t a;
5691 ira_allocno_iterator ai;
5692
5693 FOR_EACH_ALLOCNO (a, ai)
5694 {
5695 int old_regno = ALLOCNO_REGNO (a);
5696 int new_regno = REGNO (ALLOCNO_EMIT_DATA (a)->reg);
5697
5698 ALLOCNO_REGNO (a) = new_regno;
5699
5700 if (old_regno != new_regno)
5701 setup_reg_classes (new_regno, reg_preferred_class (old_regno),
5702 reg_alternate_class (old_regno),
5703 reg_allocno_class (old_regno));
5704 }
5705 }
5706 else
5707 {
5708 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
5709 fprintf (ira_dump_file, "Flattening IR\n");
5710 ira_flattening (max_regno_before_ira, ira_max_point_before_emit);
5711 }
5712 /* New insns were generated: add notes and recalculate live
5713 info. */
5714 df_analyze ();
5715
5716 /* ??? Rebuild the loop tree, but why? Does the loop tree
5717 change if new insns were generated? Can that be handled
5718 by updating the loop tree incrementally? */
5719 loop_optimizer_finalize ();
5720 free_dominance_info (CDI_DOMINATORS);
5721 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
5722 | LOOPS_HAVE_RECORDED_EXITS);
5723
5724 if (! ira_use_lra_p)
5725 {
5726 setup_allocno_assignment_flags ();
5727 ira_initiate_assign ();
5728 ira_reassign_conflict_allocnos (max_regno);
5729 }
5730 }
5731 }
5732
5733 ira_finish_emit_data ();
5734
5735 setup_reg_renumber ();
5736
5737 calculate_allocation_cost ();
5738
5739 #ifdef ENABLE_IRA_CHECKING
5740 if (ira_conflicts_p && ! ira_use_lra_p)
5741 /* Opposite to reload pass, LRA does not use any conflict info
5742 from IRA. We don't rebuild conflict info for LRA (through
5743 ira_flattening call) and cannot use the check here. We could
5744 rebuild this info for LRA in the check mode but there is a risk
5745 that code generated with the check and without it will be a bit
5746 different. Calling ira_flattening in any mode would be a
5747 wasting CPU time. So do not check the allocation for LRA. */
5748 check_allocation ();
5749 #endif
5750
5751 if (max_regno != max_regno_before_ira)
5752 regstat_recompute_for_max_regno ();
5753
5754 overall_cost_before = ira_overall_cost;
5755 if (! ira_conflicts_p)
5756 grow_reg_equivs ();
5757 else
5758 {
5759 fix_reg_equiv_init ();
5760
5761 #ifdef ENABLE_IRA_CHECKING
5762 print_redundant_copies ();
5763 #endif
5764 if (! ira_use_lra_p)
5765 {
5766 ira_spilled_reg_stack_slots_num = 0;
5767 ira_spilled_reg_stack_slots
5768 = ((class ira_spilled_reg_stack_slot *)
5769 ira_allocate (max_regno
5770 * sizeof (class ira_spilled_reg_stack_slot)));
5771 memset ((void *)ira_spilled_reg_stack_slots, 0,
5772 max_regno * sizeof (class ira_spilled_reg_stack_slot));
5773 }
5774 }
5775 allocate_initial_values ();
5776
5777 /* See comment for find_moveable_pseudos call. */
5778 if (ira_conflicts_p)
5779 move_unallocated_pseudos ();
5780
5781 /* Restore original values. */
5782 if (lra_simple_p)
5783 {
5784 flag_caller_saves = saved_flag_caller_saves;
5785 flag_ira_region = saved_flag_ira_region;
5786 }
5787 }
5788
5789 /* Modify asm goto to avoid further trouble with this insn. We can
5790 not replace the insn by USE as in other asm insns as we still
5791 need to keep CFG consistency. */
5792 void
ira_nullify_asm_goto(rtx_insn * insn)5793 ira_nullify_asm_goto (rtx_insn *insn)
5794 {
5795 ira_assert (JUMP_P (insn) && INSN_CODE (insn) < 0);
5796 rtx tmp = extract_asm_operands (PATTERN (insn));
5797 PATTERN (insn) = gen_rtx_ASM_OPERANDS (VOIDmode, ggc_strdup (""), "", 0,
5798 rtvec_alloc (0),
5799 rtvec_alloc (0),
5800 ASM_OPERANDS_LABEL_VEC (tmp),
5801 ASM_OPERANDS_SOURCE_LOCATION(tmp));
5802 }
5803
5804 static void
do_reload(void)5805 do_reload (void)
5806 {
5807 basic_block bb;
5808 bool need_dce;
5809 unsigned pic_offset_table_regno = INVALID_REGNUM;
5810
5811 if (flag_ira_verbose < 10)
5812 ira_dump_file = dump_file;
5813
5814 /* If pic_offset_table_rtx is a pseudo register, then keep it so
5815 after reload to avoid possible wrong usages of hard reg assigned
5816 to it. */
5817 if (pic_offset_table_rtx
5818 && REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER)
5819 pic_offset_table_regno = REGNO (pic_offset_table_rtx);
5820
5821 timevar_push (TV_RELOAD);
5822 if (ira_use_lra_p)
5823 {
5824 if (current_loops != NULL)
5825 {
5826 loop_optimizer_finalize ();
5827 free_dominance_info (CDI_DOMINATORS);
5828 }
5829 FOR_ALL_BB_FN (bb, cfun)
5830 bb->loop_father = NULL;
5831 current_loops = NULL;
5832
5833 ira_destroy ();
5834
5835 lra (ira_dump_file);
5836 /* ???!!! Move it before lra () when we use ira_reg_equiv in
5837 LRA. */
5838 vec_free (reg_equivs);
5839 reg_equivs = NULL;
5840 need_dce = false;
5841 }
5842 else
5843 {
5844 df_set_flags (DF_NO_INSN_RESCAN);
5845 build_insn_chain ();
5846
5847 need_dce = reload (get_insns (), ira_conflicts_p);
5848 }
5849
5850 timevar_pop (TV_RELOAD);
5851
5852 timevar_push (TV_IRA);
5853
5854 if (ira_conflicts_p && ! ira_use_lra_p)
5855 {
5856 ira_free (ira_spilled_reg_stack_slots);
5857 ira_finish_assign ();
5858 }
5859
5860 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL
5861 && overall_cost_before != ira_overall_cost)
5862 fprintf (ira_dump_file, "+++Overall after reload %" PRId64 "\n",
5863 ira_overall_cost);
5864
5865 flag_ira_share_spill_slots = saved_flag_ira_share_spill_slots;
5866
5867 if (! ira_use_lra_p)
5868 {
5869 ira_destroy ();
5870 if (current_loops != NULL)
5871 {
5872 loop_optimizer_finalize ();
5873 free_dominance_info (CDI_DOMINATORS);
5874 }
5875 FOR_ALL_BB_FN (bb, cfun)
5876 bb->loop_father = NULL;
5877 current_loops = NULL;
5878
5879 regstat_free_ri ();
5880 regstat_free_n_sets_and_refs ();
5881 }
5882
5883 if (optimize)
5884 cleanup_cfg (CLEANUP_EXPENSIVE);
5885
5886 finish_reg_equiv ();
5887
5888 bitmap_obstack_release (&ira_bitmap_obstack);
5889 #ifndef IRA_NO_OBSTACK
5890 obstack_free (&ira_obstack, NULL);
5891 #endif
5892
5893 /* The code after the reload has changed so much that at this point
5894 we might as well just rescan everything. Note that
5895 df_rescan_all_insns is not going to help here because it does not
5896 touch the artificial uses and defs. */
5897 df_finish_pass (true);
5898 df_scan_alloc (NULL);
5899 df_scan_blocks ();
5900
5901 if (optimize > 1)
5902 {
5903 df_live_add_problem ();
5904 df_live_set_all_dirty ();
5905 }
5906
5907 if (optimize)
5908 df_analyze ();
5909
5910 if (need_dce && optimize)
5911 run_fast_dce ();
5912
5913 /* Diagnose uses of the hard frame pointer when it is used as a global
5914 register. Often we can get away with letting the user appropriate
5915 the frame pointer, but we should let them know when code generation
5916 makes that impossible. */
5917 if (global_regs[HARD_FRAME_POINTER_REGNUM] && frame_pointer_needed)
5918 {
5919 tree decl = global_regs_decl[HARD_FRAME_POINTER_REGNUM];
5920 error_at (DECL_SOURCE_LOCATION (current_function_decl),
5921 "frame pointer required, but reserved");
5922 inform (DECL_SOURCE_LOCATION (decl), "for %qD", decl);
5923 }
5924
5925 /* If we are doing generic stack checking, give a warning if this
5926 function's frame size is larger than we expect. */
5927 if (flag_stack_check == GENERIC_STACK_CHECK)
5928 {
5929 poly_int64 size = get_frame_size () + STACK_CHECK_FIXED_FRAME_SIZE;
5930
5931 for (int i = 0; i < FIRST_PSEUDO_REGISTER; i++)
5932 if (df_regs_ever_live_p (i)
5933 && !fixed_regs[i]
5934 && !crtl->abi->clobbers_full_reg_p (i))
5935 size += UNITS_PER_WORD;
5936
5937 if (constant_lower_bound (size) > STACK_CHECK_MAX_FRAME_SIZE)
5938 warning (0, "frame size too large for reliable stack checking");
5939 }
5940
5941 if (pic_offset_table_regno != INVALID_REGNUM)
5942 pic_offset_table_rtx = gen_rtx_REG (Pmode, pic_offset_table_regno);
5943
5944 timevar_pop (TV_IRA);
5945 }
5946
5947 /* Run the integrated register allocator. */
5948
5949 namespace {
5950
5951 const pass_data pass_data_ira =
5952 {
5953 RTL_PASS, /* type */
5954 "ira", /* name */
5955 OPTGROUP_NONE, /* optinfo_flags */
5956 TV_IRA, /* tv_id */
5957 0, /* properties_required */
5958 0, /* properties_provided */
5959 0, /* properties_destroyed */
5960 0, /* todo_flags_start */
5961 TODO_do_not_ggc_collect, /* todo_flags_finish */
5962 };
5963
5964 class pass_ira : public rtl_opt_pass
5965 {
5966 public:
pass_ira(gcc::context * ctxt)5967 pass_ira (gcc::context *ctxt)
5968 : rtl_opt_pass (pass_data_ira, ctxt)
5969 {}
5970
5971 /* opt_pass methods: */
gate(function *)5972 virtual bool gate (function *)
5973 {
5974 return !targetm.no_register_allocation;
5975 }
execute(function *)5976 virtual unsigned int execute (function *)
5977 {
5978 ira (dump_file);
5979 return 0;
5980 }
5981
5982 }; // class pass_ira
5983
5984 } // anon namespace
5985
5986 rtl_opt_pass *
make_pass_ira(gcc::context * ctxt)5987 make_pass_ira (gcc::context *ctxt)
5988 {
5989 return new pass_ira (ctxt);
5990 }
5991
5992 namespace {
5993
5994 const pass_data pass_data_reload =
5995 {
5996 RTL_PASS, /* type */
5997 "reload", /* name */
5998 OPTGROUP_NONE, /* optinfo_flags */
5999 TV_RELOAD, /* tv_id */
6000 0, /* properties_required */
6001 0, /* properties_provided */
6002 0, /* properties_destroyed */
6003 0, /* todo_flags_start */
6004 0, /* todo_flags_finish */
6005 };
6006
6007 class pass_reload : public rtl_opt_pass
6008 {
6009 public:
pass_reload(gcc::context * ctxt)6010 pass_reload (gcc::context *ctxt)
6011 : rtl_opt_pass (pass_data_reload, ctxt)
6012 {}
6013
6014 /* opt_pass methods: */
gate(function *)6015 virtual bool gate (function *)
6016 {
6017 return !targetm.no_register_allocation;
6018 }
execute(function *)6019 virtual unsigned int execute (function *)
6020 {
6021 do_reload ();
6022 return 0;
6023 }
6024
6025 }; // class pass_reload
6026
6027 } // anon namespace
6028
6029 rtl_opt_pass *
make_pass_reload(gcc::context * ctxt)6030 make_pass_reload (gcc::context *ctxt)
6031 {
6032 return new pass_reload (ctxt);
6033 }
6034