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