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