1 /* Integrated Register Allocator (IRA) entry point. 2 Copyright (C) 2006-2013 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, calulates 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. 196 197 We also use a modification of Chaitin-Briggs algorithm which 198 works for intersected register classes of allocnos. To 199 figure out trivial colorability of allocnos, the mentioned 200 above tree of hard register sets is used. To get an idea how 201 the algorithm works in i386 example, let us consider an 202 allocno to which any general hard register can be assigned. 203 If the allocno conflicts with eight allocnos to which only 204 EAX register can be assigned, given allocno is still 205 trivially colorable because all conflicting allocnos might be 206 assigned only to EAX and all other general hard registers are 207 still free. 208 209 To get an idea of the used trivial colorability criterion, it 210 is also useful to read article "Graph-Coloring Register 211 Allocation for Irregular Architectures" by Michael D. Smith 212 and Glen Holloway. Major difference between the article 213 approach and approach used in IRA is that Smith's approach 214 takes register classes only from machine description and IRA 215 calculate register classes from intermediate code too 216 (e.g. an explicit usage of hard registers in RTL code for 217 parameter passing can result in creation of additional 218 register classes which contain or exclude the hard 219 registers). That makes IRA approach useful for improving 220 coloring even for architectures with regular register files 221 and in fact some benchmarking shows the improvement for 222 regular class architectures is even bigger than for irregular 223 ones. Another difference is that Smith's approach chooses 224 intersection of classes of all insn operands in which a given 225 pseudo occurs. IRA can use bigger classes if it is still 226 more profitable than memory usage. 227 228 * Popping the allocnos from the stack and assigning them hard 229 registers. If IRA can not assign a hard register to an 230 allocno and the allocno is coalesced, IRA undoes the 231 coalescing and puts the uncoalesced allocnos onto the stack in 232 the hope that some such allocnos will get a hard register 233 separately. If IRA fails to assign hard register or memory 234 is more profitable for it, IRA spills the allocno. IRA 235 assigns the allocno the hard-register with minimal full 236 allocation cost which reflects the cost of usage of the 237 hard-register for the allocno and cost of usage of the 238 hard-register for allocnos conflicting with given allocno. 239 240 * Chaitin-Briggs coloring assigns as many pseudos as possible 241 to hard registers. After coloringh we try to improve 242 allocation with cost point of view. We improve the 243 allocation by spilling some allocnos and assigning the freed 244 hard registers to other allocnos if it decreases the overall 245 allocation cost. 246 247 * After allono assigning in the region, IRA modifies the hard 248 register and memory costs for the corresponding allocnos in 249 the subregions to reflect the cost of possible loads, stores, 250 or moves on the border of the region and its subregions. 251 When default regional allocation algorithm is used 252 (-fira-algorithm=mixed), IRA just propagates the assignment 253 for allocnos if the register pressure in the region for the 254 corresponding pressure class is less than number of available 255 hard registers for given pressure class. 256 257 o Spill/restore code moving. When IRA performs an allocation 258 by traversing regions in top-down order, it does not know what 259 happens below in the region tree. Therefore, sometimes IRA 260 misses opportunities to perform a better allocation. A simple 261 optimization tries to improve allocation in a region having 262 subregions and containing in another region. If the 263 corresponding allocnos in the subregion are spilled, it spills 264 the region allocno if it is profitable. The optimization 265 implements a simple iterative algorithm performing profitable 266 transformations while they are still possible. It is fast in 267 practice, so there is no real need for a better time complexity 268 algorithm. 269 270 o Code change. After coloring, two allocnos representing the 271 same pseudo-register outside and inside a region respectively 272 may be assigned to different locations (hard-registers or 273 memory). In this case IRA creates and uses a new 274 pseudo-register inside the region and adds code to move allocno 275 values on the region's borders. This is done during top-down 276 traversal of the regions (file ira-emit.c). In some 277 complicated cases IRA can create a new allocno to move allocno 278 values (e.g. when a swap of values stored in two hard-registers 279 is needed). At this stage, the new allocno is marked as 280 spilled. IRA still creates the pseudo-register and the moves 281 on the region borders even when both allocnos were assigned to 282 the same hard-register. If the reload pass spills a 283 pseudo-register for some reason, the effect will be smaller 284 because another allocno will still be in the hard-register. In 285 most cases, this is better then spilling both allocnos. If 286 reload does not change the allocation for the two 287 pseudo-registers, the trivial move will be removed by 288 post-reload optimizations. IRA does not generate moves for 289 allocnos assigned to the same hard register when the default 290 regional allocation algorithm is used and the register pressure 291 in the region for the corresponding pressure class is less than 292 number of available hard registers for given pressure class. 293 IRA also does some optimizations to remove redundant stores and 294 to reduce code duplication on the region borders. 295 296 o Flattening internal representation. After changing code, IRA 297 transforms its internal representation for several regions into 298 one region representation (file ira-build.c). This process is 299 called IR flattening. Such process is more complicated than IR 300 rebuilding would be, but is much faster. 301 302 o After IR flattening, IRA tries to assign hard registers to all 303 spilled allocnos. This is impelemented by a simple and fast 304 priority coloring algorithm (see function 305 ira_reassign_conflict_allocnos::ira-color.c). Here new allocnos 306 created during the code change pass can be assigned to hard 307 registers. 308 309 o At the end IRA calls the reload pass. The reload pass 310 communicates with IRA through several functions in file 311 ira-color.c to improve its decisions in 312 313 * sharing stack slots for the spilled pseudos based on IRA info 314 about pseudo-register conflicts. 315 316 * reassigning hard-registers to all spilled pseudos at the end 317 of each reload iteration. 318 319 * choosing a better hard-register to spill based on IRA info 320 about pseudo-register live ranges and the register pressure 321 in places where the pseudo-register lives. 322 323 IRA uses a lot of data representing the target processors. These 324 data are initilized in file ira.c. 325 326 If function has no loops (or the loops are ignored when 327 -fira-algorithm=CB is used), we have classic Chaitin-Briggs 328 coloring (only instead of separate pass of coalescing, we use hard 329 register preferencing). In such case, IRA works much faster 330 because many things are not made (like IR flattening, the 331 spill/restore optimization, and the code change). 332 333 Literature is worth to read for better understanding the code: 334 335 o Preston Briggs, Keith D. Cooper, Linda Torczon. Improvements to 336 Graph Coloring Register Allocation. 337 338 o David Callahan, Brian Koblenz. Register allocation via 339 hierarchical graph coloring. 340 341 o Keith Cooper, Anshuman Dasgupta, Jason Eckhardt. Revisiting Graph 342 Coloring Register Allocation: A Study of the Chaitin-Briggs and 343 Callahan-Koblenz Algorithms. 344 345 o Guei-Yuan Lueh, Thomas Gross, and Ali-Reza Adl-Tabatabai. Global 346 Register Allocation Based on Graph Fusion. 347 348 o Michael D. Smith and Glenn Holloway. Graph-Coloring Register 349 Allocation for Irregular Architectures 350 351 o Vladimir Makarov. The Integrated Register Allocator for GCC. 352 353 o Vladimir Makarov. The top-down register allocator for irregular 354 register file architectures. 355 356 */ 357 358 359 #include "config.h" 360 #include "system.h" 361 #include "coretypes.h" 362 #include "tm.h" 363 #include "regs.h" 364 #include "rtl.h" 365 #include "tm_p.h" 366 #include "target.h" 367 #include "flags.h" 368 #include "obstack.h" 369 #include "bitmap.h" 370 #include "hard-reg-set.h" 371 #include "basic-block.h" 372 #include "df.h" 373 #include "expr.h" 374 #include "recog.h" 375 #include "params.h" 376 #include "tree-pass.h" 377 #include "output.h" 378 #include "except.h" 379 #include "reload.h" 380 #include "diagnostic-core.h" 381 #include "function.h" 382 #include "ggc.h" 383 #include "ira-int.h" 384 #include "lra.h" 385 #include "dce.h" 386 #include "dbgcnt.h" 387 388 struct target_ira default_target_ira; 389 struct target_ira_int default_target_ira_int; 390 #if SWITCHABLE_TARGET 391 struct target_ira *this_target_ira = &default_target_ira; 392 struct target_ira_int *this_target_ira_int = &default_target_ira_int; 393 #endif 394 395 /* A modified value of flag `-fira-verbose' used internally. */ 396 int internal_flag_ira_verbose; 397 398 /* Dump file of the allocator if it is not NULL. */ 399 FILE *ira_dump_file; 400 401 /* The number of elements in the following array. */ 402 int ira_spilled_reg_stack_slots_num; 403 404 /* The following array contains info about spilled pseudo-registers 405 stack slots used in current function so far. */ 406 struct ira_spilled_reg_stack_slot *ira_spilled_reg_stack_slots; 407 408 /* Correspondingly overall cost of the allocation, overall cost before 409 reload, cost of the allocnos assigned to hard-registers, cost of 410 the allocnos assigned to memory, cost of loads, stores and register 411 move insns generated for pseudo-register live range splitting (see 412 ira-emit.c). */ 413 int ira_overall_cost, overall_cost_before; 414 int ira_reg_cost, ira_mem_cost; 415 int ira_load_cost, ira_store_cost, ira_shuffle_cost; 416 int ira_move_loops_num, ira_additional_jumps_num; 417 418 /* All registers that can be eliminated. */ 419 420 HARD_REG_SET eliminable_regset; 421 422 /* Value of max_reg_num () before IRA work start. This value helps 423 us to recognize a situation when new pseudos were created during 424 IRA work. */ 425 static int max_regno_before_ira; 426 427 /* Temporary hard reg set used for a different calculation. */ 428 static HARD_REG_SET temp_hard_regset; 429 430 #define last_mode_for_init_move_cost \ 431 (this_target_ira_int->x_last_mode_for_init_move_cost) 432 433 434 /* The function sets up the map IRA_REG_MODE_HARD_REGSET. */ 435 static void 436 setup_reg_mode_hard_regset (void) 437 { 438 int i, m, hard_regno; 439 440 for (m = 0; m < NUM_MACHINE_MODES; m++) 441 for (hard_regno = 0; hard_regno < FIRST_PSEUDO_REGISTER; hard_regno++) 442 { 443 CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset[hard_regno][m]); 444 for (i = hard_regno_nregs[hard_regno][m] - 1; i >= 0; i--) 445 if (hard_regno + i < FIRST_PSEUDO_REGISTER) 446 SET_HARD_REG_BIT (ira_reg_mode_hard_regset[hard_regno][m], 447 hard_regno + i); 448 } 449 } 450 451 452 #define no_unit_alloc_regs \ 453 (this_target_ira_int->x_no_unit_alloc_regs) 454 455 /* The function sets up the three arrays declared above. */ 456 static void 457 setup_class_hard_regs (void) 458 { 459 int cl, i, hard_regno, n; 460 HARD_REG_SET processed_hard_reg_set; 461 462 ira_assert (SHRT_MAX >= FIRST_PSEUDO_REGISTER); 463 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--) 464 { 465 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]); 466 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs); 467 CLEAR_HARD_REG_SET (processed_hard_reg_set); 468 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 469 { 470 ira_non_ordered_class_hard_regs[cl][i] = -1; 471 ira_class_hard_reg_index[cl][i] = -1; 472 } 473 for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++) 474 { 475 #ifdef REG_ALLOC_ORDER 476 hard_regno = reg_alloc_order[i]; 477 #else 478 hard_regno = i; 479 #endif 480 if (TEST_HARD_REG_BIT (processed_hard_reg_set, hard_regno)) 481 continue; 482 SET_HARD_REG_BIT (processed_hard_reg_set, hard_regno); 483 if (! TEST_HARD_REG_BIT (temp_hard_regset, hard_regno)) 484 ira_class_hard_reg_index[cl][hard_regno] = -1; 485 else 486 { 487 ira_class_hard_reg_index[cl][hard_regno] = n; 488 ira_class_hard_regs[cl][n++] = hard_regno; 489 } 490 } 491 ira_class_hard_regs_num[cl] = n; 492 for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++) 493 if (TEST_HARD_REG_BIT (temp_hard_regset, i)) 494 ira_non_ordered_class_hard_regs[cl][n++] = i; 495 ira_assert (ira_class_hard_regs_num[cl] == n); 496 } 497 } 498 499 /* Set up global variables defining info about hard registers for the 500 allocation. These depend on USE_HARD_FRAME_P whose TRUE value means 501 that we can use the hard frame pointer for the allocation. */ 502 static void 503 setup_alloc_regs (bool use_hard_frame_p) 504 { 505 #ifdef ADJUST_REG_ALLOC_ORDER 506 ADJUST_REG_ALLOC_ORDER; 507 #endif 508 COPY_HARD_REG_SET (no_unit_alloc_regs, fixed_reg_set); 509 if (! use_hard_frame_p) 510 SET_HARD_REG_BIT (no_unit_alloc_regs, HARD_FRAME_POINTER_REGNUM); 511 setup_class_hard_regs (); 512 } 513 514 515 516 #define alloc_reg_class_subclasses \ 517 (this_target_ira_int->x_alloc_reg_class_subclasses) 518 519 /* Initialize the table of subclasses of each reg class. */ 520 static void 521 setup_reg_subclasses (void) 522 { 523 int i, j; 524 HARD_REG_SET temp_hard_regset2; 525 526 for (i = 0; i < N_REG_CLASSES; i++) 527 for (j = 0; j < N_REG_CLASSES; j++) 528 alloc_reg_class_subclasses[i][j] = LIM_REG_CLASSES; 529 530 for (i = 0; i < N_REG_CLASSES; i++) 531 { 532 if (i == (int) NO_REGS) 533 continue; 534 535 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]); 536 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs); 537 if (hard_reg_set_empty_p (temp_hard_regset)) 538 continue; 539 for (j = 0; j < N_REG_CLASSES; j++) 540 if (i != j) 541 { 542 enum reg_class *p; 543 544 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[j]); 545 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs); 546 if (! hard_reg_set_subset_p (temp_hard_regset, 547 temp_hard_regset2)) 548 continue; 549 p = &alloc_reg_class_subclasses[j][0]; 550 while (*p != LIM_REG_CLASSES) p++; 551 *p = (enum reg_class) i; 552 } 553 } 554 } 555 556 557 558 /* Set up IRA_MEMORY_MOVE_COST and IRA_MAX_MEMORY_MOVE_COST. */ 559 static void 560 setup_class_subset_and_memory_move_costs (void) 561 { 562 int cl, cl2, mode, cost; 563 HARD_REG_SET temp_hard_regset2; 564 565 for (mode = 0; mode < MAX_MACHINE_MODE; mode++) 566 ira_memory_move_cost[mode][NO_REGS][0] 567 = ira_memory_move_cost[mode][NO_REGS][1] = SHRT_MAX; 568 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--) 569 { 570 if (cl != (int) NO_REGS) 571 for (mode = 0; mode < MAX_MACHINE_MODE; mode++) 572 { 573 ira_max_memory_move_cost[mode][cl][0] 574 = ira_memory_move_cost[mode][cl][0] 575 = memory_move_cost ((enum machine_mode) mode, 576 (reg_class_t) cl, false); 577 ira_max_memory_move_cost[mode][cl][1] 578 = ira_memory_move_cost[mode][cl][1] 579 = memory_move_cost ((enum machine_mode) mode, 580 (reg_class_t) cl, true); 581 /* Costs for NO_REGS are used in cost calculation on the 582 1st pass when the preferred register classes are not 583 known yet. In this case we take the best scenario. */ 584 if (ira_memory_move_cost[mode][NO_REGS][0] 585 > ira_memory_move_cost[mode][cl][0]) 586 ira_max_memory_move_cost[mode][NO_REGS][0] 587 = ira_memory_move_cost[mode][NO_REGS][0] 588 = ira_memory_move_cost[mode][cl][0]; 589 if (ira_memory_move_cost[mode][NO_REGS][1] 590 > ira_memory_move_cost[mode][cl][1]) 591 ira_max_memory_move_cost[mode][NO_REGS][1] 592 = ira_memory_move_cost[mode][NO_REGS][1] 593 = ira_memory_move_cost[mode][cl][1]; 594 } 595 } 596 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--) 597 for (cl2 = (int) N_REG_CLASSES - 1; cl2 >= 0; cl2--) 598 { 599 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]); 600 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs); 601 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]); 602 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs); 603 ira_class_subset_p[cl][cl2] 604 = hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2); 605 if (! hard_reg_set_empty_p (temp_hard_regset2) 606 && hard_reg_set_subset_p (reg_class_contents[cl2], 607 reg_class_contents[cl])) 608 for (mode = 0; mode < MAX_MACHINE_MODE; mode++) 609 { 610 cost = ira_memory_move_cost[mode][cl2][0]; 611 if (cost > ira_max_memory_move_cost[mode][cl][0]) 612 ira_max_memory_move_cost[mode][cl][0] = cost; 613 cost = ira_memory_move_cost[mode][cl2][1]; 614 if (cost > ira_max_memory_move_cost[mode][cl][1]) 615 ira_max_memory_move_cost[mode][cl][1] = cost; 616 } 617 } 618 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--) 619 for (mode = 0; mode < MAX_MACHINE_MODE; mode++) 620 { 621 ira_memory_move_cost[mode][cl][0] 622 = ira_max_memory_move_cost[mode][cl][0]; 623 ira_memory_move_cost[mode][cl][1] 624 = ira_max_memory_move_cost[mode][cl][1]; 625 } 626 setup_reg_subclasses (); 627 } 628 629 630 631 /* Define the following macro if allocation through malloc if 632 preferable. */ 633 #define IRA_NO_OBSTACK 634 635 #ifndef IRA_NO_OBSTACK 636 /* Obstack used for storing all dynamic data (except bitmaps) of the 637 IRA. */ 638 static struct obstack ira_obstack; 639 #endif 640 641 /* Obstack used for storing all bitmaps of the IRA. */ 642 static struct bitmap_obstack ira_bitmap_obstack; 643 644 /* Allocate memory of size LEN for IRA data. */ 645 void * 646 ira_allocate (size_t len) 647 { 648 void *res; 649 650 #ifndef IRA_NO_OBSTACK 651 res = obstack_alloc (&ira_obstack, len); 652 #else 653 res = xmalloc (len); 654 #endif 655 return res; 656 } 657 658 /* Free memory ADDR allocated for IRA data. */ 659 void 660 ira_free (void *addr ATTRIBUTE_UNUSED) 661 { 662 #ifndef IRA_NO_OBSTACK 663 /* do nothing */ 664 #else 665 free (addr); 666 #endif 667 } 668 669 670 /* Allocate and returns bitmap for IRA. */ 671 bitmap 672 ira_allocate_bitmap (void) 673 { 674 return BITMAP_ALLOC (&ira_bitmap_obstack); 675 } 676 677 /* Free bitmap B allocated for IRA. */ 678 void 679 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED) 680 { 681 /* do nothing */ 682 } 683 684 685 686 /* Output information about allocation of all allocnos (except for 687 caps) into file F. */ 688 void 689 ira_print_disposition (FILE *f) 690 { 691 int i, n, max_regno; 692 ira_allocno_t a; 693 basic_block bb; 694 695 fprintf (f, "Disposition:"); 696 max_regno = max_reg_num (); 697 for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 698 for (a = ira_regno_allocno_map[i]; 699 a != NULL; 700 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a)) 701 { 702 if (n % 4 == 0) 703 fprintf (f, "\n"); 704 n++; 705 fprintf (f, " %4d:r%-4d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a)); 706 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL) 707 fprintf (f, "b%-3d", bb->index); 708 else 709 fprintf (f, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num); 710 if (ALLOCNO_HARD_REGNO (a) >= 0) 711 fprintf (f, " %3d", ALLOCNO_HARD_REGNO (a)); 712 else 713 fprintf (f, " mem"); 714 } 715 fprintf (f, "\n"); 716 } 717 718 /* Outputs information about allocation of all allocnos into 719 stderr. */ 720 void 721 ira_debug_disposition (void) 722 { 723 ira_print_disposition (stderr); 724 } 725 726 727 728 /* Set up ira_stack_reg_pressure_class which is the biggest pressure 729 register class containing stack registers or NO_REGS if there are 730 no stack registers. To find this class, we iterate through all 731 register pressure classes and choose the first register pressure 732 class containing all the stack registers and having the biggest 733 size. */ 734 static void 735 setup_stack_reg_pressure_class (void) 736 { 737 ira_stack_reg_pressure_class = NO_REGS; 738 #ifdef STACK_REGS 739 { 740 int i, best, size; 741 enum reg_class cl; 742 HARD_REG_SET temp_hard_regset2; 743 744 CLEAR_HARD_REG_SET (temp_hard_regset); 745 for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++) 746 SET_HARD_REG_BIT (temp_hard_regset, i); 747 best = 0; 748 for (i = 0; i < ira_pressure_classes_num; i++) 749 { 750 cl = ira_pressure_classes[i]; 751 COPY_HARD_REG_SET (temp_hard_regset2, temp_hard_regset); 752 AND_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]); 753 size = hard_reg_set_size (temp_hard_regset2); 754 if (best < size) 755 { 756 best = size; 757 ira_stack_reg_pressure_class = cl; 758 } 759 } 760 } 761 #endif 762 } 763 764 /* Find pressure classes which are register classes for which we 765 calculate register pressure in IRA, register pressure sensitive 766 insn scheduling, and register pressure sensitive loop invariant 767 motion. 768 769 To make register pressure calculation easy, we always use 770 non-intersected register pressure classes. A move of hard 771 registers from one register pressure class is not more expensive 772 than load and store of the hard registers. Most likely an allocno 773 class will be a subset of a register pressure class and in many 774 cases a register pressure class. That makes usage of register 775 pressure classes a good approximation to find a high register 776 pressure. */ 777 static void 778 setup_pressure_classes (void) 779 { 780 int cost, i, n, curr; 781 int cl, cl2; 782 enum reg_class pressure_classes[N_REG_CLASSES]; 783 int m; 784 HARD_REG_SET temp_hard_regset2; 785 bool insert_p; 786 787 n = 0; 788 for (cl = 0; cl < N_REG_CLASSES; cl++) 789 { 790 if (ira_class_hard_regs_num[cl] == 0) 791 continue; 792 if (ira_class_hard_regs_num[cl] != 1 793 /* A register class without subclasses may contain a few 794 hard registers and movement between them is costly 795 (e.g. SPARC FPCC registers). We still should consider it 796 as a candidate for a pressure class. */ 797 && alloc_reg_class_subclasses[cl][0] < cl) 798 { 799 /* Check that the moves between any hard registers of the 800 current class are not more expensive for a legal mode 801 than load/store of the hard registers of the current 802 class. Such class is a potential candidate to be a 803 register pressure class. */ 804 for (m = 0; m < NUM_MACHINE_MODES; m++) 805 { 806 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]); 807 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs); 808 AND_COMPL_HARD_REG_SET (temp_hard_regset, 809 ira_prohibited_class_mode_regs[cl][m]); 810 if (hard_reg_set_empty_p (temp_hard_regset)) 811 continue; 812 ira_init_register_move_cost_if_necessary ((enum machine_mode) m); 813 cost = ira_register_move_cost[m][cl][cl]; 814 if (cost <= ira_max_memory_move_cost[m][cl][1] 815 || cost <= ira_max_memory_move_cost[m][cl][0]) 816 break; 817 } 818 if (m >= NUM_MACHINE_MODES) 819 continue; 820 } 821 curr = 0; 822 insert_p = true; 823 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]); 824 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs); 825 /* Remove so far added pressure classes which are subset of the 826 current candidate class. Prefer GENERAL_REGS as a pressure 827 register class to another class containing the same 828 allocatable hard registers. We do this because machine 829 dependent cost hooks might give wrong costs for the latter 830 class but always give the right cost for the former class 831 (GENERAL_REGS). */ 832 for (i = 0; i < n; i++) 833 { 834 cl2 = pressure_classes[i]; 835 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]); 836 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs); 837 if (hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2) 838 && (! hard_reg_set_equal_p (temp_hard_regset, temp_hard_regset2) 839 || cl2 == (int) GENERAL_REGS)) 840 { 841 pressure_classes[curr++] = (enum reg_class) cl2; 842 insert_p = false; 843 continue; 844 } 845 if (hard_reg_set_subset_p (temp_hard_regset2, temp_hard_regset) 846 && (! hard_reg_set_equal_p (temp_hard_regset2, temp_hard_regset) 847 || cl == (int) GENERAL_REGS)) 848 continue; 849 if (hard_reg_set_equal_p (temp_hard_regset2, temp_hard_regset)) 850 insert_p = false; 851 pressure_classes[curr++] = (enum reg_class) cl2; 852 } 853 /* If the current candidate is a subset of a so far added 854 pressure class, don't add it to the list of the pressure 855 classes. */ 856 if (insert_p) 857 pressure_classes[curr++] = (enum reg_class) cl; 858 n = curr; 859 } 860 #ifdef ENABLE_IRA_CHECKING 861 { 862 HARD_REG_SET ignore_hard_regs; 863 864 /* Check pressure classes correctness: here we check that hard 865 registers from all register pressure classes contains all hard 866 registers available for the allocation. */ 867 CLEAR_HARD_REG_SET (temp_hard_regset); 868 CLEAR_HARD_REG_SET (temp_hard_regset2); 869 COPY_HARD_REG_SET (ignore_hard_regs, no_unit_alloc_regs); 870 for (cl = 0; cl < LIM_REG_CLASSES; cl++) 871 { 872 /* For some targets (like MIPS with MD_REGS), there are some 873 classes with hard registers available for allocation but 874 not able to hold value of any mode. */ 875 for (m = 0; m < NUM_MACHINE_MODES; m++) 876 if (contains_reg_of_mode[cl][m]) 877 break; 878 if (m >= NUM_MACHINE_MODES) 879 { 880 IOR_HARD_REG_SET (ignore_hard_regs, reg_class_contents[cl]); 881 continue; 882 } 883 for (i = 0; i < n; i++) 884 if ((int) pressure_classes[i] == cl) 885 break; 886 IOR_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]); 887 if (i < n) 888 IOR_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]); 889 } 890 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 891 /* Some targets (like SPARC with ICC reg) have alocatable regs 892 for which no reg class is defined. */ 893 if (REGNO_REG_CLASS (i) == NO_REGS) 894 SET_HARD_REG_BIT (ignore_hard_regs, i); 895 AND_COMPL_HARD_REG_SET (temp_hard_regset, ignore_hard_regs); 896 AND_COMPL_HARD_REG_SET (temp_hard_regset2, ignore_hard_regs); 897 ira_assert (hard_reg_set_subset_p (temp_hard_regset2, temp_hard_regset)); 898 } 899 #endif 900 ira_pressure_classes_num = 0; 901 for (i = 0; i < n; i++) 902 { 903 cl = (int) pressure_classes[i]; 904 ira_reg_pressure_class_p[cl] = true; 905 ira_pressure_classes[ira_pressure_classes_num++] = (enum reg_class) cl; 906 } 907 setup_stack_reg_pressure_class (); 908 } 909 910 /* Set up IRA_UNIFORM_CLASS_P. Uniform class is a register class 911 whose register move cost between any registers of the class is the 912 same as for all its subclasses. We use the data to speed up the 913 2nd pass of calculations of allocno costs. */ 914 static void 915 setup_uniform_class_p (void) 916 { 917 int i, cl, cl2, m; 918 919 for (cl = 0; cl < N_REG_CLASSES; cl++) 920 { 921 ira_uniform_class_p[cl] = false; 922 if (ira_class_hard_regs_num[cl] == 0) 923 continue; 924 /* We can not use alloc_reg_class_subclasses here because move 925 cost hooks does not take into account that some registers are 926 unavailable for the subtarget. E.g. for i686, INT_SSE_REGS 927 is element of alloc_reg_class_subclasses for GENERAL_REGS 928 because SSE regs are unavailable. */ 929 for (i = 0; (cl2 = reg_class_subclasses[cl][i]) != LIM_REG_CLASSES; i++) 930 { 931 if (ira_class_hard_regs_num[cl2] == 0) 932 continue; 933 for (m = 0; m < NUM_MACHINE_MODES; m++) 934 if (contains_reg_of_mode[cl][m] && contains_reg_of_mode[cl2][m]) 935 { 936 ira_init_register_move_cost_if_necessary ((enum machine_mode) m); 937 if (ira_register_move_cost[m][cl][cl] 938 != ira_register_move_cost[m][cl2][cl2]) 939 break; 940 } 941 if (m < NUM_MACHINE_MODES) 942 break; 943 } 944 if (cl2 == LIM_REG_CLASSES) 945 ira_uniform_class_p[cl] = true; 946 } 947 } 948 949 /* Set up IRA_ALLOCNO_CLASSES, IRA_ALLOCNO_CLASSES_NUM, 950 IRA_IMPORTANT_CLASSES, and IRA_IMPORTANT_CLASSES_NUM. 951 952 Target may have many subtargets and not all target hard regiters can 953 be used for allocation, e.g. x86 port in 32-bit mode can not use 954 hard registers introduced in x86-64 like r8-r15). Some classes 955 might have the same allocatable hard registers, e.g. INDEX_REGS 956 and GENERAL_REGS in x86 port in 32-bit mode. To decrease different 957 calculations efforts we introduce allocno classes which contain 958 unique non-empty sets of allocatable hard-registers. 959 960 Pseudo class cost calculation in ira-costs.c is very expensive. 961 Therefore we are trying to decrease number of classes involved in 962 such calculation. Register classes used in the cost calculation 963 are called important classes. They are allocno classes and other 964 non-empty classes whose allocatable hard register sets are inside 965 of an allocno class hard register set. From the first sight, it 966 looks like that they are just allocno classes. It is not true. In 967 example of x86-port in 32-bit mode, allocno classes will contain 968 GENERAL_REGS but not LEGACY_REGS (because allocatable hard 969 registers are the same for the both classes). The important 970 classes will contain GENERAL_REGS and LEGACY_REGS. It is done 971 because a machine description insn constraint may refers for 972 LEGACY_REGS and code in ira-costs.c is mostly base on investigation 973 of the insn constraints. */ 974 static void 975 setup_allocno_and_important_classes (void) 976 { 977 int i, j, n, cl; 978 bool set_p; 979 HARD_REG_SET temp_hard_regset2; 980 static enum reg_class classes[LIM_REG_CLASSES + 1]; 981 982 n = 0; 983 /* Collect classes which contain unique sets of allocatable hard 984 registers. Prefer GENERAL_REGS to other classes containing the 985 same set of hard registers. */ 986 for (i = 0; i < LIM_REG_CLASSES; i++) 987 { 988 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]); 989 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs); 990 for (j = 0; j < n; j++) 991 { 992 cl = classes[j]; 993 COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]); 994 AND_COMPL_HARD_REG_SET (temp_hard_regset2, 995 no_unit_alloc_regs); 996 if (hard_reg_set_equal_p (temp_hard_regset, 997 temp_hard_regset2)) 998 break; 999 } 1000 if (j >= n) 1001 classes[n++] = (enum reg_class) i; 1002 else if (i == GENERAL_REGS) 1003 /* Prefer general regs. For i386 example, it means that 1004 we prefer GENERAL_REGS over INDEX_REGS or LEGACY_REGS 1005 (all of them consists of the same available hard 1006 registers). */ 1007 classes[j] = (enum reg_class) i; 1008 } 1009 classes[n] = LIM_REG_CLASSES; 1010 1011 /* Set up classes which can be used for allocnos as classes 1012 conatining non-empty unique sets of allocatable hard 1013 registers. */ 1014 ira_allocno_classes_num = 0; 1015 for (i = 0; (cl = classes[i]) != LIM_REG_CLASSES; i++) 1016 if (ira_class_hard_regs_num[cl] > 0) 1017 ira_allocno_classes[ira_allocno_classes_num++] = (enum reg_class) cl; 1018 ira_important_classes_num = 0; 1019 /* Add non-allocno classes containing to non-empty set of 1020 allocatable hard regs. */ 1021 for (cl = 0; cl < N_REG_CLASSES; cl++) 1022 if (ira_class_hard_regs_num[cl] > 0) 1023 { 1024 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]); 1025 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs); 1026 set_p = false; 1027 for (j = 0; j < ira_allocno_classes_num; j++) 1028 { 1029 COPY_HARD_REG_SET (temp_hard_regset2, 1030 reg_class_contents[ira_allocno_classes[j]]); 1031 AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs); 1032 if ((enum reg_class) cl == ira_allocno_classes[j]) 1033 break; 1034 else if (hard_reg_set_subset_p (temp_hard_regset, 1035 temp_hard_regset2)) 1036 set_p = true; 1037 } 1038 if (set_p && j >= ira_allocno_classes_num) 1039 ira_important_classes[ira_important_classes_num++] 1040 = (enum reg_class) cl; 1041 } 1042 /* Now add allocno classes to the important classes. */ 1043 for (j = 0; j < ira_allocno_classes_num; j++) 1044 ira_important_classes[ira_important_classes_num++] 1045 = ira_allocno_classes[j]; 1046 for (cl = 0; cl < N_REG_CLASSES; cl++) 1047 { 1048 ira_reg_allocno_class_p[cl] = false; 1049 ira_reg_pressure_class_p[cl] = false; 1050 } 1051 for (j = 0; j < ira_allocno_classes_num; j++) 1052 ira_reg_allocno_class_p[ira_allocno_classes[j]] = true; 1053 setup_pressure_classes (); 1054 setup_uniform_class_p (); 1055 } 1056 1057 /* Setup translation in CLASS_TRANSLATE of all classes into a class 1058 given by array CLASSES of length CLASSES_NUM. The function is used 1059 make translation any reg class to an allocno class or to an 1060 pressure class. This translation is necessary for some 1061 calculations when we can use only allocno or pressure classes and 1062 such translation represents an approximate representation of all 1063 classes. 1064 1065 The translation in case when allocatable hard register set of a 1066 given class is subset of allocatable hard register set of a class 1067 in CLASSES is pretty simple. We use smallest classes from CLASSES 1068 containing a given class. If allocatable hard register set of a 1069 given class is not a subset of any corresponding set of a class 1070 from CLASSES, we use the cheapest (with load/store point of view) 1071 class from CLASSES whose set intersects with given class set */ 1072 static void 1073 setup_class_translate_array (enum reg_class *class_translate, 1074 int classes_num, enum reg_class *classes) 1075 { 1076 int cl, mode; 1077 enum reg_class aclass, best_class, *cl_ptr; 1078 int i, cost, min_cost, best_cost; 1079 1080 for (cl = 0; cl < N_REG_CLASSES; cl++) 1081 class_translate[cl] = NO_REGS; 1082 1083 for (i = 0; i < classes_num; i++) 1084 { 1085 aclass = classes[i]; 1086 for (cl_ptr = &alloc_reg_class_subclasses[aclass][0]; 1087 (cl = *cl_ptr) != LIM_REG_CLASSES; 1088 cl_ptr++) 1089 if (class_translate[cl] == NO_REGS) 1090 class_translate[cl] = aclass; 1091 class_translate[aclass] = aclass; 1092 } 1093 /* For classes which are not fully covered by one of given classes 1094 (in other words covered by more one given class), use the 1095 cheapest class. */ 1096 for (cl = 0; cl < N_REG_CLASSES; cl++) 1097 { 1098 if (cl == NO_REGS || class_translate[cl] != NO_REGS) 1099 continue; 1100 best_class = NO_REGS; 1101 best_cost = INT_MAX; 1102 for (i = 0; i < classes_num; i++) 1103 { 1104 aclass = classes[i]; 1105 COPY_HARD_REG_SET (temp_hard_regset, 1106 reg_class_contents[aclass]); 1107 AND_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]); 1108 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs); 1109 if (! hard_reg_set_empty_p (temp_hard_regset)) 1110 { 1111 min_cost = INT_MAX; 1112 for (mode = 0; mode < MAX_MACHINE_MODE; mode++) 1113 { 1114 cost = (ira_memory_move_cost[mode][cl][0] 1115 + ira_memory_move_cost[mode][cl][1]); 1116 if (min_cost > cost) 1117 min_cost = cost; 1118 } 1119 if (best_class == NO_REGS || best_cost > min_cost) 1120 { 1121 best_class = aclass; 1122 best_cost = min_cost; 1123 } 1124 } 1125 } 1126 class_translate[cl] = best_class; 1127 } 1128 } 1129 1130 /* Set up array IRA_ALLOCNO_CLASS_TRANSLATE and 1131 IRA_PRESSURE_CLASS_TRANSLATE. */ 1132 static void 1133 setup_class_translate (void) 1134 { 1135 setup_class_translate_array (ira_allocno_class_translate, 1136 ira_allocno_classes_num, ira_allocno_classes); 1137 setup_class_translate_array (ira_pressure_class_translate, 1138 ira_pressure_classes_num, ira_pressure_classes); 1139 } 1140 1141 /* Order numbers of allocno classes in original target allocno class 1142 array, -1 for non-allocno classes. */ 1143 static int allocno_class_order[N_REG_CLASSES]; 1144 1145 /* The function used to sort the important classes. */ 1146 static int 1147 comp_reg_classes_func (const void *v1p, const void *v2p) 1148 { 1149 enum reg_class cl1 = *(const enum reg_class *) v1p; 1150 enum reg_class cl2 = *(const enum reg_class *) v2p; 1151 enum reg_class tcl1, tcl2; 1152 int diff; 1153 1154 tcl1 = ira_allocno_class_translate[cl1]; 1155 tcl2 = ira_allocno_class_translate[cl2]; 1156 if (tcl1 != NO_REGS && tcl2 != NO_REGS 1157 && (diff = allocno_class_order[tcl1] - allocno_class_order[tcl2]) != 0) 1158 return diff; 1159 return (int) cl1 - (int) cl2; 1160 } 1161 1162 /* For correct work of function setup_reg_class_relation we need to 1163 reorder important classes according to the order of their allocno 1164 classes. It places important classes containing the same 1165 allocatable hard register set adjacent to each other and allocno 1166 class with the allocatable hard register set right after the other 1167 important classes with the same set. 1168 1169 In example from comments of function 1170 setup_allocno_and_important_classes, it places LEGACY_REGS and 1171 GENERAL_REGS close to each other and GENERAL_REGS is after 1172 LEGACY_REGS. */ 1173 static void 1174 reorder_important_classes (void) 1175 { 1176 int i; 1177 1178 for (i = 0; i < N_REG_CLASSES; i++) 1179 allocno_class_order[i] = -1; 1180 for (i = 0; i < ira_allocno_classes_num; i++) 1181 allocno_class_order[ira_allocno_classes[i]] = i; 1182 qsort (ira_important_classes, ira_important_classes_num, 1183 sizeof (enum reg_class), comp_reg_classes_func); 1184 for (i = 0; i < ira_important_classes_num; i++) 1185 ira_important_class_nums[ira_important_classes[i]] = i; 1186 } 1187 1188 /* Set up IRA_REG_CLASS_SUBUNION, IRA_REG_CLASS_SUPERUNION, 1189 IRA_REG_CLASS_SUPER_CLASSES, IRA_REG_CLASSES_INTERSECT, and 1190 IRA_REG_CLASSES_INTERSECT_P. For the meaning of the relations, 1191 please see corresponding comments in ira-int.h. */ 1192 static void 1193 setup_reg_class_relations (void) 1194 { 1195 int i, cl1, cl2, cl3; 1196 HARD_REG_SET intersection_set, union_set, temp_set2; 1197 bool important_class_p[N_REG_CLASSES]; 1198 1199 memset (important_class_p, 0, sizeof (important_class_p)); 1200 for (i = 0; i < ira_important_classes_num; i++) 1201 important_class_p[ira_important_classes[i]] = true; 1202 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++) 1203 { 1204 ira_reg_class_super_classes[cl1][0] = LIM_REG_CLASSES; 1205 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++) 1206 { 1207 ira_reg_classes_intersect_p[cl1][cl2] = false; 1208 ira_reg_class_intersect[cl1][cl2] = NO_REGS; 1209 ira_reg_class_subset[cl1][cl2] = NO_REGS; 1210 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl1]); 1211 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs); 1212 COPY_HARD_REG_SET (temp_set2, reg_class_contents[cl2]); 1213 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs); 1214 if (hard_reg_set_empty_p (temp_hard_regset) 1215 && hard_reg_set_empty_p (temp_set2)) 1216 { 1217 /* The both classes have no allocatable hard registers 1218 -- take all class hard registers into account and use 1219 reg_class_subunion and reg_class_superunion. */ 1220 for (i = 0;; i++) 1221 { 1222 cl3 = reg_class_subclasses[cl1][i]; 1223 if (cl3 == LIM_REG_CLASSES) 1224 break; 1225 if (reg_class_subset_p (ira_reg_class_intersect[cl1][cl2], 1226 (enum reg_class) cl3)) 1227 ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3; 1228 } 1229 ira_reg_class_subunion[cl1][cl2] = reg_class_subunion[cl1][cl2]; 1230 ira_reg_class_superunion[cl1][cl2] = reg_class_superunion[cl1][cl2]; 1231 continue; 1232 } 1233 ira_reg_classes_intersect_p[cl1][cl2] 1234 = hard_reg_set_intersect_p (temp_hard_regset, temp_set2); 1235 if (important_class_p[cl1] && important_class_p[cl2] 1236 && hard_reg_set_subset_p (temp_hard_regset, temp_set2)) 1237 { 1238 /* CL1 and CL2 are important classes and CL1 allocatable 1239 hard register set is inside of CL2 allocatable hard 1240 registers -- make CL1 a superset of CL2. */ 1241 enum reg_class *p; 1242 1243 p = &ira_reg_class_super_classes[cl1][0]; 1244 while (*p != LIM_REG_CLASSES) 1245 p++; 1246 *p++ = (enum reg_class) cl2; 1247 *p = LIM_REG_CLASSES; 1248 } 1249 ira_reg_class_subunion[cl1][cl2] = NO_REGS; 1250 ira_reg_class_superunion[cl1][cl2] = NO_REGS; 1251 COPY_HARD_REG_SET (intersection_set, reg_class_contents[cl1]); 1252 AND_HARD_REG_SET (intersection_set, reg_class_contents[cl2]); 1253 AND_COMPL_HARD_REG_SET (intersection_set, no_unit_alloc_regs); 1254 COPY_HARD_REG_SET (union_set, reg_class_contents[cl1]); 1255 IOR_HARD_REG_SET (union_set, reg_class_contents[cl2]); 1256 AND_COMPL_HARD_REG_SET (union_set, no_unit_alloc_regs); 1257 for (cl3 = 0; cl3 < N_REG_CLASSES; cl3++) 1258 { 1259 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl3]); 1260 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs); 1261 if (hard_reg_set_subset_p (temp_hard_regset, intersection_set)) 1262 { 1263 /* CL3 allocatable hard register set is inside of 1264 intersection of allocatable hard register sets 1265 of CL1 and CL2. */ 1266 if (important_class_p[cl3]) 1267 { 1268 COPY_HARD_REG_SET 1269 (temp_set2, 1270 reg_class_contents 1271 [(int) ira_reg_class_intersect[cl1][cl2]]); 1272 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs); 1273 if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2) 1274 /* If the allocatable hard register sets are 1275 the same, prefer GENERAL_REGS or the 1276 smallest class for debugging 1277 purposes. */ 1278 || (hard_reg_set_equal_p (temp_hard_regset, temp_set2) 1279 && (cl3 == GENERAL_REGS 1280 || ((ira_reg_class_intersect[cl1][cl2] 1281 != GENERAL_REGS) 1282 && hard_reg_set_subset_p 1283 (reg_class_contents[cl3], 1284 reg_class_contents 1285 [(int) 1286 ira_reg_class_intersect[cl1][cl2]]))))) 1287 ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3; 1288 } 1289 COPY_HARD_REG_SET 1290 (temp_set2, 1291 reg_class_contents[(int) ira_reg_class_subset[cl1][cl2]]); 1292 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs); 1293 if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2) 1294 /* Ignore unavailable hard registers and prefer 1295 smallest class for debugging purposes. */ 1296 || (hard_reg_set_equal_p (temp_hard_regset, temp_set2) 1297 && hard_reg_set_subset_p 1298 (reg_class_contents[cl3], 1299 reg_class_contents 1300 [(int) ira_reg_class_subset[cl1][cl2]]))) 1301 ira_reg_class_subset[cl1][cl2] = (enum reg_class) cl3; 1302 } 1303 if (important_class_p[cl3] 1304 && hard_reg_set_subset_p (temp_hard_regset, union_set)) 1305 { 1306 /* CL3 allocatbale hard register set is inside of 1307 union of allocatable hard register sets of CL1 1308 and CL2. */ 1309 COPY_HARD_REG_SET 1310 (temp_set2, 1311 reg_class_contents[(int) ira_reg_class_subunion[cl1][cl2]]); 1312 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs); 1313 if (ira_reg_class_subunion[cl1][cl2] == NO_REGS 1314 || (hard_reg_set_subset_p (temp_set2, temp_hard_regset) 1315 1316 && (! hard_reg_set_equal_p (temp_set2, 1317 temp_hard_regset) 1318 || cl3 == GENERAL_REGS 1319 /* If the allocatable hard register sets are the 1320 same, prefer GENERAL_REGS or the smallest 1321 class for debugging purposes. */ 1322 || (ira_reg_class_subunion[cl1][cl2] != GENERAL_REGS 1323 && hard_reg_set_subset_p 1324 (reg_class_contents[cl3], 1325 reg_class_contents 1326 [(int) ira_reg_class_subunion[cl1][cl2]]))))) 1327 ira_reg_class_subunion[cl1][cl2] = (enum reg_class) cl3; 1328 } 1329 if (hard_reg_set_subset_p (union_set, temp_hard_regset)) 1330 { 1331 /* CL3 allocatable hard register set contains union 1332 of allocatable hard register sets of CL1 and 1333 CL2. */ 1334 COPY_HARD_REG_SET 1335 (temp_set2, 1336 reg_class_contents[(int) ira_reg_class_superunion[cl1][cl2]]); 1337 AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs); 1338 if (ira_reg_class_superunion[cl1][cl2] == NO_REGS 1339 || (hard_reg_set_subset_p (temp_hard_regset, temp_set2) 1340 1341 && (! hard_reg_set_equal_p (temp_set2, 1342 temp_hard_regset) 1343 || cl3 == GENERAL_REGS 1344 /* If the allocatable hard register sets are the 1345 same, prefer GENERAL_REGS or the smallest 1346 class for debugging purposes. */ 1347 || (ira_reg_class_superunion[cl1][cl2] != GENERAL_REGS 1348 && hard_reg_set_subset_p 1349 (reg_class_contents[cl3], 1350 reg_class_contents 1351 [(int) ira_reg_class_superunion[cl1][cl2]]))))) 1352 ira_reg_class_superunion[cl1][cl2] = (enum reg_class) cl3; 1353 } 1354 } 1355 } 1356 } 1357 } 1358 1359 /* Output all unifrom and important classes into file F. */ 1360 static void 1361 print_unform_and_important_classes (FILE *f) 1362 { 1363 static const char *const reg_class_names[] = REG_CLASS_NAMES; 1364 int i, cl; 1365 1366 fprintf (f, "Uniform classes:\n"); 1367 for (cl = 0; cl < N_REG_CLASSES; cl++) 1368 if (ira_uniform_class_p[cl]) 1369 fprintf (f, " %s", reg_class_names[cl]); 1370 fprintf (f, "\nImportant classes:\n"); 1371 for (i = 0; i < ira_important_classes_num; i++) 1372 fprintf (f, " %s", reg_class_names[ira_important_classes[i]]); 1373 fprintf (f, "\n"); 1374 } 1375 1376 /* Output all possible allocno or pressure classes and their 1377 translation map into file F. */ 1378 static void 1379 print_translated_classes (FILE *f, bool pressure_p) 1380 { 1381 int classes_num = (pressure_p 1382 ? ira_pressure_classes_num : ira_allocno_classes_num); 1383 enum reg_class *classes = (pressure_p 1384 ? ira_pressure_classes : ira_allocno_classes); 1385 enum reg_class *class_translate = (pressure_p 1386 ? ira_pressure_class_translate 1387 : ira_allocno_class_translate); 1388 static const char *const reg_class_names[] = REG_CLASS_NAMES; 1389 int i; 1390 1391 fprintf (f, "%s classes:\n", pressure_p ? "Pressure" : "Allocno"); 1392 for (i = 0; i < classes_num; i++) 1393 fprintf (f, " %s", reg_class_names[classes[i]]); 1394 fprintf (f, "\nClass translation:\n"); 1395 for (i = 0; i < N_REG_CLASSES; i++) 1396 fprintf (f, " %s -> %s\n", reg_class_names[i], 1397 reg_class_names[class_translate[i]]); 1398 } 1399 1400 /* Output all possible allocno and translation classes and the 1401 translation maps into stderr. */ 1402 void 1403 ira_debug_allocno_classes (void) 1404 { 1405 print_unform_and_important_classes (stderr); 1406 print_translated_classes (stderr, false); 1407 print_translated_classes (stderr, true); 1408 } 1409 1410 /* Set up different arrays concerning class subsets, allocno and 1411 important classes. */ 1412 static void 1413 find_reg_classes (void) 1414 { 1415 setup_allocno_and_important_classes (); 1416 setup_class_translate (); 1417 reorder_important_classes (); 1418 setup_reg_class_relations (); 1419 } 1420 1421 1422 1423 /* Set up the array above. */ 1424 static void 1425 setup_hard_regno_aclass (void) 1426 { 1427 int i; 1428 1429 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1430 { 1431 #if 1 1432 ira_hard_regno_allocno_class[i] 1433 = (TEST_HARD_REG_BIT (no_unit_alloc_regs, i) 1434 ? NO_REGS 1435 : ira_allocno_class_translate[REGNO_REG_CLASS (i)]); 1436 #else 1437 int j; 1438 enum reg_class cl; 1439 ira_hard_regno_allocno_class[i] = NO_REGS; 1440 for (j = 0; j < ira_allocno_classes_num; j++) 1441 { 1442 cl = ira_allocno_classes[j]; 1443 if (ira_class_hard_reg_index[cl][i] >= 0) 1444 { 1445 ira_hard_regno_allocno_class[i] = cl; 1446 break; 1447 } 1448 } 1449 #endif 1450 } 1451 } 1452 1453 1454 1455 /* Form IRA_REG_CLASS_MAX_NREGS and IRA_REG_CLASS_MIN_NREGS maps. */ 1456 static void 1457 setup_reg_class_nregs (void) 1458 { 1459 int i, cl, cl2, m; 1460 1461 for (m = 0; m < MAX_MACHINE_MODE; m++) 1462 { 1463 for (cl = 0; cl < N_REG_CLASSES; cl++) 1464 ira_reg_class_max_nregs[cl][m] 1465 = ira_reg_class_min_nregs[cl][m] 1466 = targetm.class_max_nregs ((reg_class_t) cl, (enum machine_mode) m); 1467 for (cl = 0; cl < N_REG_CLASSES; cl++) 1468 for (i = 0; 1469 (cl2 = alloc_reg_class_subclasses[cl][i]) != LIM_REG_CLASSES; 1470 i++) 1471 if (ira_reg_class_min_nregs[cl2][m] 1472 < ira_reg_class_min_nregs[cl][m]) 1473 ira_reg_class_min_nregs[cl][m] = ira_reg_class_min_nregs[cl2][m]; 1474 } 1475 } 1476 1477 1478 1479 /* Set up IRA_PROHIBITED_CLASS_MODE_REGS and IRA_CLASS_SINGLETON. 1480 This function is called once IRA_CLASS_HARD_REGS has been initialized. */ 1481 static void 1482 setup_prohibited_class_mode_regs (void) 1483 { 1484 int j, k, hard_regno, cl, last_hard_regno, count; 1485 1486 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--) 1487 { 1488 COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]); 1489 AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs); 1490 for (j = 0; j < NUM_MACHINE_MODES; j++) 1491 { 1492 count = 0; 1493 last_hard_regno = -1; 1494 CLEAR_HARD_REG_SET (ira_prohibited_class_mode_regs[cl][j]); 1495 for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--) 1496 { 1497 hard_regno = ira_class_hard_regs[cl][k]; 1498 if (! HARD_REGNO_MODE_OK (hard_regno, (enum machine_mode) j)) 1499 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j], 1500 hard_regno); 1501 else if (in_hard_reg_set_p (temp_hard_regset, 1502 (enum machine_mode) j, hard_regno)) 1503 { 1504 last_hard_regno = hard_regno; 1505 count++; 1506 } 1507 } 1508 ira_class_singleton[cl][j] = (count == 1 ? last_hard_regno : -1); 1509 } 1510 } 1511 } 1512 1513 /* Clarify IRA_PROHIBITED_CLASS_MODE_REGS by excluding hard registers 1514 spanning from one register pressure class to another one. It is 1515 called after defining the pressure classes. */ 1516 static void 1517 clarify_prohibited_class_mode_regs (void) 1518 { 1519 int j, k, hard_regno, cl, pclass, nregs; 1520 1521 for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--) 1522 for (j = 0; j < NUM_MACHINE_MODES; j++) 1523 { 1524 CLEAR_HARD_REG_SET (ira_useful_class_mode_regs[cl][j]); 1525 for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--) 1526 { 1527 hard_regno = ira_class_hard_regs[cl][k]; 1528 if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j], hard_regno)) 1529 continue; 1530 nregs = hard_regno_nregs[hard_regno][j]; 1531 if (hard_regno + nregs > FIRST_PSEUDO_REGISTER) 1532 { 1533 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j], 1534 hard_regno); 1535 continue; 1536 } 1537 pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)]; 1538 for (nregs-- ;nregs >= 0; nregs--) 1539 if (((enum reg_class) pclass 1540 != ira_pressure_class_translate[REGNO_REG_CLASS 1541 (hard_regno + nregs)])) 1542 { 1543 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j], 1544 hard_regno); 1545 break; 1546 } 1547 if (!TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j], 1548 hard_regno)) 1549 add_to_hard_reg_set (&ira_useful_class_mode_regs[cl][j], 1550 (enum machine_mode) j, hard_regno); 1551 } 1552 } 1553 } 1554 1555 /* Allocate and initialize IRA_REGISTER_MOVE_COST, IRA_MAY_MOVE_IN_COST 1556 and IRA_MAY_MOVE_OUT_COST for MODE. */ 1557 void 1558 ira_init_register_move_cost (enum machine_mode mode) 1559 { 1560 static unsigned short last_move_cost[N_REG_CLASSES][N_REG_CLASSES]; 1561 bool all_match = true; 1562 unsigned int cl1, cl2; 1563 1564 ira_assert (ira_register_move_cost[mode] == NULL 1565 && ira_may_move_in_cost[mode] == NULL 1566 && ira_may_move_out_cost[mode] == NULL); 1567 ira_assert (have_regs_of_mode[mode]); 1568 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++) 1569 if (contains_reg_of_mode[cl1][mode]) 1570 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++) 1571 { 1572 int cost; 1573 if (!contains_reg_of_mode[cl2][mode]) 1574 cost = 65535; 1575 else 1576 { 1577 cost = register_move_cost (mode, (enum reg_class) cl1, 1578 (enum reg_class) cl2); 1579 ira_assert (cost < 65535); 1580 } 1581 all_match &= (last_move_cost[cl1][cl2] == cost); 1582 last_move_cost[cl1][cl2] = cost; 1583 } 1584 if (all_match && last_mode_for_init_move_cost != -1) 1585 { 1586 ira_register_move_cost[mode] 1587 = ira_register_move_cost[last_mode_for_init_move_cost]; 1588 ira_may_move_in_cost[mode] 1589 = ira_may_move_in_cost[last_mode_for_init_move_cost]; 1590 ira_may_move_out_cost[mode] 1591 = ira_may_move_out_cost[last_mode_for_init_move_cost]; 1592 return; 1593 } 1594 last_mode_for_init_move_cost = mode; 1595 ira_register_move_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES); 1596 ira_may_move_in_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES); 1597 ira_may_move_out_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES); 1598 for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++) 1599 if (contains_reg_of_mode[cl1][mode]) 1600 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++) 1601 { 1602 int cost; 1603 enum reg_class *p1, *p2; 1604 1605 if (last_move_cost[cl1][cl2] == 65535) 1606 { 1607 ira_register_move_cost[mode][cl1][cl2] = 65535; 1608 ira_may_move_in_cost[mode][cl1][cl2] = 65535; 1609 ira_may_move_out_cost[mode][cl1][cl2] = 65535; 1610 } 1611 else 1612 { 1613 cost = last_move_cost[cl1][cl2]; 1614 1615 for (p2 = ®_class_subclasses[cl2][0]; 1616 *p2 != LIM_REG_CLASSES; p2++) 1617 if (ira_class_hard_regs_num[*p2] > 0 1618 && (ira_reg_class_max_nregs[*p2][mode] 1619 <= ira_class_hard_regs_num[*p2])) 1620 cost = MAX (cost, ira_register_move_cost[mode][cl1][*p2]); 1621 1622 for (p1 = ®_class_subclasses[cl1][0]; 1623 *p1 != LIM_REG_CLASSES; p1++) 1624 if (ira_class_hard_regs_num[*p1] > 0 1625 && (ira_reg_class_max_nregs[*p1][mode] 1626 <= ira_class_hard_regs_num[*p1])) 1627 cost = MAX (cost, ira_register_move_cost[mode][*p1][cl2]); 1628 1629 ira_assert (cost <= 65535); 1630 ira_register_move_cost[mode][cl1][cl2] = cost; 1631 1632 if (ira_class_subset_p[cl1][cl2]) 1633 ira_may_move_in_cost[mode][cl1][cl2] = 0; 1634 else 1635 ira_may_move_in_cost[mode][cl1][cl2] = cost; 1636 1637 if (ira_class_subset_p[cl2][cl1]) 1638 ira_may_move_out_cost[mode][cl1][cl2] = 0; 1639 else 1640 ira_may_move_out_cost[mode][cl1][cl2] = cost; 1641 } 1642 } 1643 else 1644 for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++) 1645 { 1646 ira_register_move_cost[mode][cl1][cl2] = 65535; 1647 ira_may_move_in_cost[mode][cl1][cl2] = 65535; 1648 ira_may_move_out_cost[mode][cl1][cl2] = 65535; 1649 } 1650 } 1651 1652 1653 /* This is called once during compiler work. It sets up 1654 different arrays whose values don't depend on the compiled 1655 function. */ 1656 void 1657 ira_init_once (void) 1658 { 1659 ira_init_costs_once (); 1660 lra_init_once (); 1661 } 1662 1663 /* Free ira_max_register_move_cost, ira_may_move_in_cost and 1664 ira_may_move_out_cost for each mode. */ 1665 static void 1666 free_register_move_costs (void) 1667 { 1668 int mode, i; 1669 1670 /* Reset move_cost and friends, making sure we only free shared 1671 table entries once. */ 1672 for (mode = 0; mode < MAX_MACHINE_MODE; mode++) 1673 if (ira_register_move_cost[mode]) 1674 { 1675 for (i = 0; 1676 i < mode && (ira_register_move_cost[i] 1677 != ira_register_move_cost[mode]); 1678 i++) 1679 ; 1680 if (i == mode) 1681 { 1682 free (ira_register_move_cost[mode]); 1683 free (ira_may_move_in_cost[mode]); 1684 free (ira_may_move_out_cost[mode]); 1685 } 1686 } 1687 memset (ira_register_move_cost, 0, sizeof ira_register_move_cost); 1688 memset (ira_may_move_in_cost, 0, sizeof ira_may_move_in_cost); 1689 memset (ira_may_move_out_cost, 0, sizeof ira_may_move_out_cost); 1690 last_mode_for_init_move_cost = -1; 1691 } 1692 1693 /* This is called every time when register related information is 1694 changed. */ 1695 void 1696 ira_init (void) 1697 { 1698 free_register_move_costs (); 1699 setup_reg_mode_hard_regset (); 1700 setup_alloc_regs (flag_omit_frame_pointer != 0); 1701 setup_class_subset_and_memory_move_costs (); 1702 setup_reg_class_nregs (); 1703 setup_prohibited_class_mode_regs (); 1704 find_reg_classes (); 1705 clarify_prohibited_class_mode_regs (); 1706 setup_hard_regno_aclass (); 1707 ira_init_costs (); 1708 lra_init (); 1709 } 1710 1711 /* Function called once at the end of compiler work. */ 1712 void 1713 ira_finish_once (void) 1714 { 1715 ira_finish_costs_once (); 1716 free_register_move_costs (); 1717 lra_finish_once (); 1718 } 1719 1720 1721 #define ira_prohibited_mode_move_regs_initialized_p \ 1722 (this_target_ira_int->x_ira_prohibited_mode_move_regs_initialized_p) 1723 1724 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS. */ 1725 static void 1726 setup_prohibited_mode_move_regs (void) 1727 { 1728 int i, j; 1729 rtx test_reg1, test_reg2, move_pat, move_insn; 1730 1731 if (ira_prohibited_mode_move_regs_initialized_p) 1732 return; 1733 ira_prohibited_mode_move_regs_initialized_p = true; 1734 test_reg1 = gen_rtx_REG (VOIDmode, 0); 1735 test_reg2 = gen_rtx_REG (VOIDmode, 0); 1736 move_pat = gen_rtx_SET (VOIDmode, test_reg1, test_reg2); 1737 move_insn = gen_rtx_INSN (VOIDmode, 0, 0, 0, 0, move_pat, 0, -1, 0); 1738 for (i = 0; i < NUM_MACHINE_MODES; i++) 1739 { 1740 SET_HARD_REG_SET (ira_prohibited_mode_move_regs[i]); 1741 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++) 1742 { 1743 if (! HARD_REGNO_MODE_OK (j, (enum machine_mode) i)) 1744 continue; 1745 SET_REGNO_RAW (test_reg1, j); 1746 PUT_MODE (test_reg1, (enum machine_mode) i); 1747 SET_REGNO_RAW (test_reg2, j); 1748 PUT_MODE (test_reg2, (enum machine_mode) i); 1749 INSN_CODE (move_insn) = -1; 1750 recog_memoized (move_insn); 1751 if (INSN_CODE (move_insn) < 0) 1752 continue; 1753 extract_insn (move_insn); 1754 if (! constrain_operands (1)) 1755 continue; 1756 CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs[i], j); 1757 } 1758 } 1759 } 1760 1761 1762 1763 /* Return nonzero if REGNO is a particularly bad choice for reloading X. */ 1764 static bool 1765 ira_bad_reload_regno_1 (int regno, rtx x) 1766 { 1767 int x_regno, n, i; 1768 ira_allocno_t a; 1769 enum reg_class pref; 1770 1771 /* We only deal with pseudo regs. */ 1772 if (! x || GET_CODE (x) != REG) 1773 return false; 1774 1775 x_regno = REGNO (x); 1776 if (x_regno < FIRST_PSEUDO_REGISTER) 1777 return false; 1778 1779 /* If the pseudo prefers REGNO explicitly, then do not consider 1780 REGNO a bad spill choice. */ 1781 pref = reg_preferred_class (x_regno); 1782 if (reg_class_size[pref] == 1) 1783 return !TEST_HARD_REG_BIT (reg_class_contents[pref], regno); 1784 1785 /* If the pseudo conflicts with REGNO, then we consider REGNO a 1786 poor choice for a reload regno. */ 1787 a = ira_regno_allocno_map[x_regno]; 1788 n = ALLOCNO_NUM_OBJECTS (a); 1789 for (i = 0; i < n; i++) 1790 { 1791 ira_object_t obj = ALLOCNO_OBJECT (a, i); 1792 if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), regno)) 1793 return true; 1794 } 1795 return false; 1796 } 1797 1798 /* Return nonzero if REGNO is a particularly bad choice for reloading 1799 IN or OUT. */ 1800 bool 1801 ira_bad_reload_regno (int regno, rtx in, rtx out) 1802 { 1803 return (ira_bad_reload_regno_1 (regno, in) 1804 || ira_bad_reload_regno_1 (regno, out)); 1805 } 1806 1807 /* Return TRUE if *LOC contains an asm. */ 1808 static int 1809 insn_contains_asm_1 (rtx *loc, void *data ATTRIBUTE_UNUSED) 1810 { 1811 if ( !*loc) 1812 return FALSE; 1813 if (GET_CODE (*loc) == ASM_OPERANDS) 1814 return TRUE; 1815 return FALSE; 1816 } 1817 1818 1819 /* Return TRUE if INSN contains an ASM. */ 1820 static bool 1821 insn_contains_asm (rtx insn) 1822 { 1823 return for_each_rtx (&insn, insn_contains_asm_1, NULL); 1824 } 1825 1826 /* Add register clobbers from asm statements. */ 1827 static void 1828 compute_regs_asm_clobbered (void) 1829 { 1830 basic_block bb; 1831 1832 FOR_EACH_BB (bb) 1833 { 1834 rtx insn; 1835 FOR_BB_INSNS_REVERSE (bb, insn) 1836 { 1837 df_ref *def_rec; 1838 1839 if (insn_contains_asm (insn)) 1840 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++) 1841 { 1842 df_ref def = *def_rec; 1843 unsigned int dregno = DF_REF_REGNO (def); 1844 if (HARD_REGISTER_NUM_P (dregno)) 1845 add_to_hard_reg_set (&crtl->asm_clobbers, 1846 GET_MODE (DF_REF_REAL_REG (def)), 1847 dregno); 1848 } 1849 } 1850 } 1851 } 1852 1853 1854 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and REGS_EVER_LIVE. 1855 If the function is called from IRA (not from the insn scheduler or 1856 RTL loop invariant motion), FROM_IRA_P is true. */ 1857 void 1858 ira_setup_eliminable_regset (bool from_ira_p) 1859 { 1860 #ifdef ELIMINABLE_REGS 1861 int i; 1862 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS; 1863 #endif 1864 /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore 1865 sp for alloca. So we can't eliminate the frame pointer in that 1866 case. At some point, we should improve this by emitting the 1867 sp-adjusting insns for this case. */ 1868 frame_pointer_needed 1869 = (! flag_omit_frame_pointer 1870 || (cfun->calls_alloca && EXIT_IGNORE_STACK) 1871 /* We need the frame pointer to catch stack overflow exceptions 1872 if the stack pointer is moving. */ 1873 || (flag_stack_check && STACK_CHECK_MOVING_SP) 1874 || crtl->accesses_prior_frames 1875 || crtl->stack_realign_needed 1876 || targetm.frame_pointer_required ()); 1877 1878 if (from_ira_p && ira_use_lra_p) 1879 /* It can change FRAME_POINTER_NEEDED. We call it only from IRA 1880 because it is expensive. */ 1881 lra_init_elimination (); 1882 1883 if (frame_pointer_needed) 1884 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true); 1885 1886 COPY_HARD_REG_SET (ira_no_alloc_regs, no_unit_alloc_regs); 1887 CLEAR_HARD_REG_SET (eliminable_regset); 1888 1889 compute_regs_asm_clobbered (); 1890 1891 /* Build the regset of all eliminable registers and show we can't 1892 use those that we already know won't be eliminated. */ 1893 #ifdef ELIMINABLE_REGS 1894 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++) 1895 { 1896 bool cannot_elim 1897 = (! targetm.can_eliminate (eliminables[i].from, eliminables[i].to) 1898 || (eliminables[i].to == STACK_POINTER_REGNUM && frame_pointer_needed)); 1899 1900 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, eliminables[i].from)) 1901 { 1902 SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from); 1903 1904 if (cannot_elim) 1905 SET_HARD_REG_BIT (ira_no_alloc_regs, eliminables[i].from); 1906 } 1907 else if (cannot_elim) 1908 error ("%s cannot be used in asm here", 1909 reg_names[eliminables[i].from]); 1910 else 1911 df_set_regs_ever_live (eliminables[i].from, true); 1912 } 1913 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER 1914 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM)) 1915 { 1916 SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM); 1917 if (frame_pointer_needed) 1918 SET_HARD_REG_BIT (ira_no_alloc_regs, HARD_FRAME_POINTER_REGNUM); 1919 } 1920 else if (frame_pointer_needed) 1921 error ("%s cannot be used in asm here", 1922 reg_names[HARD_FRAME_POINTER_REGNUM]); 1923 else 1924 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true); 1925 #endif 1926 1927 #else 1928 if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM)) 1929 { 1930 SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM); 1931 if (frame_pointer_needed) 1932 SET_HARD_REG_BIT (ira_no_alloc_regs, FRAME_POINTER_REGNUM); 1933 } 1934 else if (frame_pointer_needed) 1935 error ("%s cannot be used in asm here", reg_names[FRAME_POINTER_REGNUM]); 1936 else 1937 df_set_regs_ever_live (FRAME_POINTER_REGNUM, true); 1938 #endif 1939 } 1940 1941 1942 1943 /* Vector of substitutions of register numbers, 1944 used to map pseudo regs into hardware regs. 1945 This is set up as a result of register allocation. 1946 Element N is the hard reg assigned to pseudo reg N, 1947 or is -1 if no hard reg was assigned. 1948 If N is a hard reg number, element N is N. */ 1949 short *reg_renumber; 1950 1951 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from 1952 the allocation found by IRA. */ 1953 static void 1954 setup_reg_renumber (void) 1955 { 1956 int regno, hard_regno; 1957 ira_allocno_t a; 1958 ira_allocno_iterator ai; 1959 1960 caller_save_needed = 0; 1961 FOR_EACH_ALLOCNO (a, ai) 1962 { 1963 if (ira_use_lra_p && ALLOCNO_CAP_MEMBER (a) != NULL) 1964 continue; 1965 /* There are no caps at this point. */ 1966 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL); 1967 if (! ALLOCNO_ASSIGNED_P (a)) 1968 /* It can happen if A is not referenced but partially anticipated 1969 somewhere in a region. */ 1970 ALLOCNO_ASSIGNED_P (a) = true; 1971 ira_free_allocno_updated_costs (a); 1972 hard_regno = ALLOCNO_HARD_REGNO (a); 1973 regno = ALLOCNO_REGNO (a); 1974 reg_renumber[regno] = (hard_regno < 0 ? -1 : hard_regno); 1975 if (hard_regno >= 0) 1976 { 1977 int i, nwords; 1978 enum reg_class pclass; 1979 ira_object_t obj; 1980 1981 pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)]; 1982 nwords = ALLOCNO_NUM_OBJECTS (a); 1983 for (i = 0; i < nwords; i++) 1984 { 1985 obj = ALLOCNO_OBJECT (a, i); 1986 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), 1987 reg_class_contents[pclass]); 1988 } 1989 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0 1990 && ira_hard_reg_set_intersection_p (hard_regno, ALLOCNO_MODE (a), 1991 call_used_reg_set)) 1992 { 1993 ira_assert (!optimize || flag_caller_saves 1994 || (ALLOCNO_CALLS_CROSSED_NUM (a) 1995 == ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a)) 1996 || regno >= ira_reg_equiv_len 1997 || ira_equiv_no_lvalue_p (regno)); 1998 caller_save_needed = 1; 1999 } 2000 } 2001 } 2002 } 2003 2004 /* Set up allocno assignment flags for further allocation 2005 improvements. */ 2006 static void 2007 setup_allocno_assignment_flags (void) 2008 { 2009 int hard_regno; 2010 ira_allocno_t a; 2011 ira_allocno_iterator ai; 2012 2013 FOR_EACH_ALLOCNO (a, ai) 2014 { 2015 if (! ALLOCNO_ASSIGNED_P (a)) 2016 /* It can happen if A is not referenced but partially anticipated 2017 somewhere in a region. */ 2018 ira_free_allocno_updated_costs (a); 2019 hard_regno = ALLOCNO_HARD_REGNO (a); 2020 /* Don't assign hard registers to allocnos which are destination 2021 of removed store at the end of loop. It has no sense to keep 2022 the same value in different hard registers. It is also 2023 impossible to assign hard registers correctly to such 2024 allocnos because the cost info and info about intersected 2025 calls are incorrect for them. */ 2026 ALLOCNO_ASSIGNED_P (a) = (hard_regno >= 0 2027 || ALLOCNO_EMIT_DATA (a)->mem_optimized_dest_p 2028 || (ALLOCNO_MEMORY_COST (a) 2029 - ALLOCNO_CLASS_COST (a)) < 0); 2030 ira_assert 2031 (hard_regno < 0 2032 || ira_hard_reg_in_set_p (hard_regno, ALLOCNO_MODE (a), 2033 reg_class_contents[ALLOCNO_CLASS (a)])); 2034 } 2035 } 2036 2037 /* Evaluate overall allocation cost and the costs for using hard 2038 registers and memory for allocnos. */ 2039 static void 2040 calculate_allocation_cost (void) 2041 { 2042 int hard_regno, cost; 2043 ira_allocno_t a; 2044 ira_allocno_iterator ai; 2045 2046 ira_overall_cost = ira_reg_cost = ira_mem_cost = 0; 2047 FOR_EACH_ALLOCNO (a, ai) 2048 { 2049 hard_regno = ALLOCNO_HARD_REGNO (a); 2050 ira_assert (hard_regno < 0 2051 || (ira_hard_reg_in_set_p 2052 (hard_regno, ALLOCNO_MODE (a), 2053 reg_class_contents[ALLOCNO_CLASS (a)]))); 2054 if (hard_regno < 0) 2055 { 2056 cost = ALLOCNO_MEMORY_COST (a); 2057 ira_mem_cost += cost; 2058 } 2059 else if (ALLOCNO_HARD_REG_COSTS (a) != NULL) 2060 { 2061 cost = (ALLOCNO_HARD_REG_COSTS (a) 2062 [ira_class_hard_reg_index 2063 [ALLOCNO_CLASS (a)][hard_regno]]); 2064 ira_reg_cost += cost; 2065 } 2066 else 2067 { 2068 cost = ALLOCNO_CLASS_COST (a); 2069 ira_reg_cost += cost; 2070 } 2071 ira_overall_cost += cost; 2072 } 2073 2074 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL) 2075 { 2076 fprintf (ira_dump_file, 2077 "+++Costs: overall %d, reg %d, mem %d, ld %d, st %d, move %d\n", 2078 ira_overall_cost, ira_reg_cost, ira_mem_cost, 2079 ira_load_cost, ira_store_cost, ira_shuffle_cost); 2080 fprintf (ira_dump_file, "+++ move loops %d, new jumps %d\n", 2081 ira_move_loops_num, ira_additional_jumps_num); 2082 } 2083 2084 } 2085 2086 #ifdef ENABLE_IRA_CHECKING 2087 /* Check the correctness of the allocation. We do need this because 2088 of complicated code to transform more one region internal 2089 representation into one region representation. */ 2090 static void 2091 check_allocation (void) 2092 { 2093 ira_allocno_t a; 2094 int hard_regno, nregs, conflict_nregs; 2095 ira_allocno_iterator ai; 2096 2097 FOR_EACH_ALLOCNO (a, ai) 2098 { 2099 int n = ALLOCNO_NUM_OBJECTS (a); 2100 int i; 2101 2102 if (ALLOCNO_CAP_MEMBER (a) != NULL 2103 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0) 2104 continue; 2105 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)]; 2106 if (nregs == 1) 2107 /* We allocated a single hard register. */ 2108 n = 1; 2109 else if (n > 1) 2110 /* We allocated multiple hard registers, and we will test 2111 conflicts in a granularity of single hard regs. */ 2112 nregs = 1; 2113 2114 for (i = 0; i < n; i++) 2115 { 2116 ira_object_t obj = ALLOCNO_OBJECT (a, i); 2117 ira_object_t conflict_obj; 2118 ira_object_conflict_iterator oci; 2119 int this_regno = hard_regno; 2120 if (n > 1) 2121 { 2122 if (REG_WORDS_BIG_ENDIAN) 2123 this_regno += n - i - 1; 2124 else 2125 this_regno += i; 2126 } 2127 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci) 2128 { 2129 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj); 2130 int conflict_hard_regno = ALLOCNO_HARD_REGNO (conflict_a); 2131 if (conflict_hard_regno < 0) 2132 continue; 2133 2134 conflict_nregs 2135 = (hard_regno_nregs 2136 [conflict_hard_regno][ALLOCNO_MODE (conflict_a)]); 2137 2138 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1 2139 && conflict_nregs == ALLOCNO_NUM_OBJECTS (conflict_a)) 2140 { 2141 if (REG_WORDS_BIG_ENDIAN) 2142 conflict_hard_regno += (ALLOCNO_NUM_OBJECTS (conflict_a) 2143 - OBJECT_SUBWORD (conflict_obj) - 1); 2144 else 2145 conflict_hard_regno += OBJECT_SUBWORD (conflict_obj); 2146 conflict_nregs = 1; 2147 } 2148 2149 if ((conflict_hard_regno <= this_regno 2150 && this_regno < conflict_hard_regno + conflict_nregs) 2151 || (this_regno <= conflict_hard_regno 2152 && conflict_hard_regno < this_regno + nregs)) 2153 { 2154 fprintf (stderr, "bad allocation for %d and %d\n", 2155 ALLOCNO_REGNO (a), ALLOCNO_REGNO (conflict_a)); 2156 gcc_unreachable (); 2157 } 2158 } 2159 } 2160 } 2161 } 2162 #endif 2163 2164 /* Allocate REG_EQUIV_INIT. Set up it from IRA_REG_EQUIV which should 2165 be already calculated. */ 2166 static void 2167 setup_reg_equiv_init (void) 2168 { 2169 int i; 2170 int max_regno = max_reg_num (); 2171 2172 for (i = 0; i < max_regno; i++) 2173 reg_equiv_init (i) = ira_reg_equiv[i].init_insns; 2174 } 2175 2176 /* Update equiv regno from movement of FROM_REGNO to TO_REGNO. INSNS 2177 are insns which were generated for such movement. It is assumed 2178 that FROM_REGNO and TO_REGNO always have the same value at the 2179 point of any move containing such registers. This function is used 2180 to update equiv info for register shuffles on the region borders 2181 and for caller save/restore insns. */ 2182 void 2183 ira_update_equiv_info_by_shuffle_insn (int to_regno, int from_regno, rtx insns) 2184 { 2185 rtx insn, x, note; 2186 2187 if (! ira_reg_equiv[from_regno].defined_p 2188 && (! ira_reg_equiv[to_regno].defined_p 2189 || ((x = ira_reg_equiv[to_regno].memory) != NULL_RTX 2190 && ! MEM_READONLY_P (x)))) 2191 return; 2192 insn = insns; 2193 if (NEXT_INSN (insn) != NULL_RTX) 2194 { 2195 if (! ira_reg_equiv[to_regno].defined_p) 2196 { 2197 ira_assert (ira_reg_equiv[to_regno].init_insns == NULL_RTX); 2198 return; 2199 } 2200 ira_reg_equiv[to_regno].defined_p = false; 2201 ira_reg_equiv[to_regno].memory 2202 = ira_reg_equiv[to_regno].constant 2203 = ira_reg_equiv[to_regno].invariant 2204 = ira_reg_equiv[to_regno].init_insns = NULL_RTX; 2205 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 2206 fprintf (ira_dump_file, 2207 " Invalidating equiv info for reg %d\n", to_regno); 2208 return; 2209 } 2210 /* It is possible that FROM_REGNO still has no equivalence because 2211 in shuffles to_regno<-from_regno and from_regno<-to_regno the 2nd 2212 insn was not processed yet. */ 2213 if (ira_reg_equiv[from_regno].defined_p) 2214 { 2215 ira_reg_equiv[to_regno].defined_p = true; 2216 if ((x = ira_reg_equiv[from_regno].memory) != NULL_RTX) 2217 { 2218 ira_assert (ira_reg_equiv[from_regno].invariant == NULL_RTX 2219 && ira_reg_equiv[from_regno].constant == NULL_RTX); 2220 ira_assert (ira_reg_equiv[to_regno].memory == NULL_RTX 2221 || rtx_equal_p (ira_reg_equiv[to_regno].memory, x)); 2222 ira_reg_equiv[to_regno].memory = x; 2223 if (! MEM_READONLY_P (x)) 2224 /* We don't add the insn to insn init list because memory 2225 equivalence is just to say what memory is better to use 2226 when the pseudo is spilled. */ 2227 return; 2228 } 2229 else if ((x = ira_reg_equiv[from_regno].constant) != NULL_RTX) 2230 { 2231 ira_assert (ira_reg_equiv[from_regno].invariant == NULL_RTX); 2232 ira_assert (ira_reg_equiv[to_regno].constant == NULL_RTX 2233 || rtx_equal_p (ira_reg_equiv[to_regno].constant, x)); 2234 ira_reg_equiv[to_regno].constant = x; 2235 } 2236 else 2237 { 2238 x = ira_reg_equiv[from_regno].invariant; 2239 ira_assert (x != NULL_RTX); 2240 ira_assert (ira_reg_equiv[to_regno].invariant == NULL_RTX 2241 || rtx_equal_p (ira_reg_equiv[to_regno].invariant, x)); 2242 ira_reg_equiv[to_regno].invariant = x; 2243 } 2244 if (find_reg_note (insn, REG_EQUIV, x) == NULL_RTX) 2245 { 2246 note = set_unique_reg_note (insn, REG_EQUIV, x); 2247 gcc_assert (note != NULL_RTX); 2248 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 2249 { 2250 fprintf (ira_dump_file, 2251 " Adding equiv note to insn %u for reg %d ", 2252 INSN_UID (insn), to_regno); 2253 dump_value_slim (ira_dump_file, x, 1); 2254 fprintf (ira_dump_file, "\n"); 2255 } 2256 } 2257 } 2258 ira_reg_equiv[to_regno].init_insns 2259 = gen_rtx_INSN_LIST (VOIDmode, insn, 2260 ira_reg_equiv[to_regno].init_insns); 2261 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL) 2262 fprintf (ira_dump_file, 2263 " Adding equiv init move insn %u to reg %d\n", 2264 INSN_UID (insn), to_regno); 2265 } 2266 2267 /* Fix values of array REG_EQUIV_INIT after live range splitting done 2268 by IRA. */ 2269 static void 2270 fix_reg_equiv_init (void) 2271 { 2272 int max_regno = max_reg_num (); 2273 int i, new_regno, max; 2274 rtx x, prev, next, insn, set; 2275 2276 if (max_regno_before_ira < max_regno) 2277 { 2278 max = vec_safe_length (reg_equivs); 2279 grow_reg_equivs (); 2280 for (i = FIRST_PSEUDO_REGISTER; i < max; i++) 2281 for (prev = NULL_RTX, x = reg_equiv_init (i); 2282 x != NULL_RTX; 2283 x = next) 2284 { 2285 next = XEXP (x, 1); 2286 insn = XEXP (x, 0); 2287 set = single_set (insn); 2288 ira_assert (set != NULL_RTX 2289 && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set)))); 2290 if (REG_P (SET_DEST (set)) 2291 && ((int) REGNO (SET_DEST (set)) == i 2292 || (int) ORIGINAL_REGNO (SET_DEST (set)) == i)) 2293 new_regno = REGNO (SET_DEST (set)); 2294 else if (REG_P (SET_SRC (set)) 2295 && ((int) REGNO (SET_SRC (set)) == i 2296 || (int) ORIGINAL_REGNO (SET_SRC (set)) == i)) 2297 new_regno = REGNO (SET_SRC (set)); 2298 else 2299 gcc_unreachable (); 2300 if (new_regno == i) 2301 prev = x; 2302 else 2303 { 2304 /* Remove the wrong list element. */ 2305 if (prev == NULL_RTX) 2306 reg_equiv_init (i) = next; 2307 else 2308 XEXP (prev, 1) = next; 2309 XEXP (x, 1) = reg_equiv_init (new_regno); 2310 reg_equiv_init (new_regno) = x; 2311 } 2312 } 2313 } 2314 } 2315 2316 #ifdef ENABLE_IRA_CHECKING 2317 /* Print redundant memory-memory copies. */ 2318 static void 2319 print_redundant_copies (void) 2320 { 2321 int hard_regno; 2322 ira_allocno_t a; 2323 ira_copy_t cp, next_cp; 2324 ira_allocno_iterator ai; 2325 2326 FOR_EACH_ALLOCNO (a, ai) 2327 { 2328 if (ALLOCNO_CAP_MEMBER (a) != NULL) 2329 /* It is a cap. */ 2330 continue; 2331 hard_regno = ALLOCNO_HARD_REGNO (a); 2332 if (hard_regno >= 0) 2333 continue; 2334 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp) 2335 if (cp->first == a) 2336 next_cp = cp->next_first_allocno_copy; 2337 else 2338 { 2339 next_cp = cp->next_second_allocno_copy; 2340 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL 2341 && cp->insn != NULL_RTX 2342 && ALLOCNO_HARD_REGNO (cp->first) == hard_regno) 2343 fprintf (ira_dump_file, 2344 " Redundant move from %d(freq %d):%d\n", 2345 INSN_UID (cp->insn), cp->freq, hard_regno); 2346 } 2347 } 2348 } 2349 #endif 2350 2351 /* Setup preferred and alternative classes for new pseudo-registers 2352 created by IRA starting with START. */ 2353 static void 2354 setup_preferred_alternate_classes_for_new_pseudos (int start) 2355 { 2356 int i, old_regno; 2357 int max_regno = max_reg_num (); 2358 2359 for (i = start; i < max_regno; i++) 2360 { 2361 old_regno = ORIGINAL_REGNO (regno_reg_rtx[i]); 2362 ira_assert (i != old_regno); 2363 setup_reg_classes (i, reg_preferred_class (old_regno), 2364 reg_alternate_class (old_regno), 2365 reg_allocno_class (old_regno)); 2366 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL) 2367 fprintf (ira_dump_file, 2368 " New r%d: setting preferred %s, alternative %s\n", 2369 i, reg_class_names[reg_preferred_class (old_regno)], 2370 reg_class_names[reg_alternate_class (old_regno)]); 2371 } 2372 } 2373 2374 2375 /* The number of entries allocated in teg_info. */ 2376 static int allocated_reg_info_size; 2377 2378 /* Regional allocation can create new pseudo-registers. This function 2379 expands some arrays for pseudo-registers. */ 2380 static void 2381 expand_reg_info (void) 2382 { 2383 int i; 2384 int size = max_reg_num (); 2385 2386 resize_reg_info (); 2387 for (i = allocated_reg_info_size; i < size; i++) 2388 setup_reg_classes (i, GENERAL_REGS, ALL_REGS, GENERAL_REGS); 2389 setup_preferred_alternate_classes_for_new_pseudos (allocated_reg_info_size); 2390 allocated_reg_info_size = size; 2391 } 2392 2393 /* Return TRUE if there is too high register pressure in the function. 2394 It is used to decide when stack slot sharing is worth to do. */ 2395 static bool 2396 too_high_register_pressure_p (void) 2397 { 2398 int i; 2399 enum reg_class pclass; 2400 2401 for (i = 0; i < ira_pressure_classes_num; i++) 2402 { 2403 pclass = ira_pressure_classes[i]; 2404 if (ira_loop_tree_root->reg_pressure[pclass] > 10000) 2405 return true; 2406 } 2407 return false; 2408 } 2409 2410 2411 2412 /* Indicate that hard register number FROM was eliminated and replaced with 2413 an offset from hard register number TO. The status of hard registers live 2414 at the start of a basic block is updated by replacing a use of FROM with 2415 a use of TO. */ 2416 2417 void 2418 mark_elimination (int from, int to) 2419 { 2420 basic_block bb; 2421 bitmap r; 2422 2423 FOR_EACH_BB (bb) 2424 { 2425 r = DF_LR_IN (bb); 2426 if (bitmap_bit_p (r, from)) 2427 { 2428 bitmap_clear_bit (r, from); 2429 bitmap_set_bit (r, to); 2430 } 2431 if (! df_live) 2432 continue; 2433 r = DF_LIVE_IN (bb); 2434 if (bitmap_bit_p (r, from)) 2435 { 2436 bitmap_clear_bit (r, from); 2437 bitmap_set_bit (r, to); 2438 } 2439 } 2440 } 2441 2442 2443 2444 /* The length of the following array. */ 2445 int ira_reg_equiv_len; 2446 2447 /* Info about equiv. info for each register. */ 2448 struct ira_reg_equiv *ira_reg_equiv; 2449 2450 /* Expand ira_reg_equiv if necessary. */ 2451 void 2452 ira_expand_reg_equiv (void) 2453 { 2454 int old = ira_reg_equiv_len; 2455 2456 if (ira_reg_equiv_len > max_reg_num ()) 2457 return; 2458 ira_reg_equiv_len = max_reg_num () * 3 / 2 + 1; 2459 ira_reg_equiv 2460 = (struct ira_reg_equiv *) xrealloc (ira_reg_equiv, 2461 ira_reg_equiv_len 2462 * sizeof (struct ira_reg_equiv)); 2463 gcc_assert (old < ira_reg_equiv_len); 2464 memset (ira_reg_equiv + old, 0, 2465 sizeof (struct ira_reg_equiv) * (ira_reg_equiv_len - old)); 2466 } 2467 2468 static void 2469 init_reg_equiv (void) 2470 { 2471 ira_reg_equiv_len = 0; 2472 ira_reg_equiv = NULL; 2473 ira_expand_reg_equiv (); 2474 } 2475 2476 static void 2477 finish_reg_equiv (void) 2478 { 2479 free (ira_reg_equiv); 2480 } 2481 2482 2483 2484 struct equivalence 2485 { 2486 /* Set when a REG_EQUIV note is found or created. Use to 2487 keep track of what memory accesses might be created later, 2488 e.g. by reload. */ 2489 rtx replacement; 2490 rtx *src_p; 2491 /* The list of each instruction which initializes this register. */ 2492 rtx init_insns; 2493 /* Loop depth is used to recognize equivalences which appear 2494 to be present within the same loop (or in an inner loop). */ 2495 int loop_depth; 2496 /* Nonzero if this had a preexisting REG_EQUIV note. */ 2497 int is_arg_equivalence; 2498 /* Set when an attempt should be made to replace a register 2499 with the associated src_p entry. */ 2500 char replace; 2501 }; 2502 2503 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence 2504 structure for that register. */ 2505 static struct equivalence *reg_equiv; 2506 2507 /* Used for communication between the following two functions: contains 2508 a MEM that we wish to ensure remains unchanged. */ 2509 static rtx equiv_mem; 2510 2511 /* Set nonzero if EQUIV_MEM is modified. */ 2512 static int equiv_mem_modified; 2513 2514 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified. 2515 Called via note_stores. */ 2516 static void 2517 validate_equiv_mem_from_store (rtx dest, const_rtx set ATTRIBUTE_UNUSED, 2518 void *data ATTRIBUTE_UNUSED) 2519 { 2520 if ((REG_P (dest) 2521 && reg_overlap_mentioned_p (dest, equiv_mem)) 2522 || (MEM_P (dest) 2523 && anti_dependence (equiv_mem, dest))) 2524 equiv_mem_modified = 1; 2525 } 2526 2527 /* Verify that no store between START and the death of REG invalidates 2528 MEMREF. MEMREF is invalidated by modifying a register used in MEMREF, 2529 by storing into an overlapping memory location, or with a non-const 2530 CALL_INSN. 2531 2532 Return 1 if MEMREF remains valid. */ 2533 static int 2534 validate_equiv_mem (rtx start, rtx reg, rtx memref) 2535 { 2536 rtx insn; 2537 rtx note; 2538 2539 equiv_mem = memref; 2540 equiv_mem_modified = 0; 2541 2542 /* If the memory reference has side effects or is volatile, it isn't a 2543 valid equivalence. */ 2544 if (side_effects_p (memref)) 2545 return 0; 2546 2547 for (insn = start; insn && ! equiv_mem_modified; insn = NEXT_INSN (insn)) 2548 { 2549 if (! INSN_P (insn)) 2550 continue; 2551 2552 if (find_reg_note (insn, REG_DEAD, reg)) 2553 return 1; 2554 2555 /* This used to ignore readonly memory and const/pure calls. The problem 2556 is the equivalent form may reference a pseudo which gets assigned a 2557 call clobbered hard reg. When we later replace REG with its 2558 equivalent form, the value in the call-clobbered reg has been 2559 changed and all hell breaks loose. */ 2560 if (CALL_P (insn)) 2561 return 0; 2562 2563 note_stores (PATTERN (insn), validate_equiv_mem_from_store, NULL); 2564 2565 /* If a register mentioned in MEMREF is modified via an 2566 auto-increment, we lose the equivalence. Do the same if one 2567 dies; although we could extend the life, it doesn't seem worth 2568 the trouble. */ 2569 2570 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 2571 if ((REG_NOTE_KIND (note) == REG_INC 2572 || REG_NOTE_KIND (note) == REG_DEAD) 2573 && REG_P (XEXP (note, 0)) 2574 && reg_overlap_mentioned_p (XEXP (note, 0), memref)) 2575 return 0; 2576 } 2577 2578 return 0; 2579 } 2580 2581 /* Returns zero if X is known to be invariant. */ 2582 static int 2583 equiv_init_varies_p (rtx x) 2584 { 2585 RTX_CODE code = GET_CODE (x); 2586 int i; 2587 const char *fmt; 2588 2589 switch (code) 2590 { 2591 case MEM: 2592 return !MEM_READONLY_P (x) || equiv_init_varies_p (XEXP (x, 0)); 2593 2594 case CONST: 2595 CASE_CONST_ANY: 2596 case SYMBOL_REF: 2597 case LABEL_REF: 2598 return 0; 2599 2600 case REG: 2601 return reg_equiv[REGNO (x)].replace == 0 && rtx_varies_p (x, 0); 2602 2603 case ASM_OPERANDS: 2604 if (MEM_VOLATILE_P (x)) 2605 return 1; 2606 2607 /* Fall through. */ 2608 2609 default: 2610 break; 2611 } 2612 2613 fmt = GET_RTX_FORMAT (code); 2614 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 2615 if (fmt[i] == 'e') 2616 { 2617 if (equiv_init_varies_p (XEXP (x, i))) 2618 return 1; 2619 } 2620 else if (fmt[i] == 'E') 2621 { 2622 int j; 2623 for (j = 0; j < XVECLEN (x, i); j++) 2624 if (equiv_init_varies_p (XVECEXP (x, i, j))) 2625 return 1; 2626 } 2627 2628 return 0; 2629 } 2630 2631 /* Returns nonzero if X (used to initialize register REGNO) is movable. 2632 X is only movable if the registers it uses have equivalent initializations 2633 which appear to be within the same loop (or in an inner loop) and movable 2634 or if they are not candidates for local_alloc and don't vary. */ 2635 static int 2636 equiv_init_movable_p (rtx x, int regno) 2637 { 2638 int i, j; 2639 const char *fmt; 2640 enum rtx_code code = GET_CODE (x); 2641 2642 switch (code) 2643 { 2644 case SET: 2645 return equiv_init_movable_p (SET_SRC (x), regno); 2646 2647 case CC0: 2648 case CLOBBER: 2649 return 0; 2650 2651 case PRE_INC: 2652 case PRE_DEC: 2653 case POST_INC: 2654 case POST_DEC: 2655 case PRE_MODIFY: 2656 case POST_MODIFY: 2657 return 0; 2658 2659 case REG: 2660 return ((reg_equiv[REGNO (x)].loop_depth >= reg_equiv[regno].loop_depth 2661 && reg_equiv[REGNO (x)].replace) 2662 || (REG_BASIC_BLOCK (REGNO (x)) < NUM_FIXED_BLOCKS 2663 && ! rtx_varies_p (x, 0))); 2664 2665 case UNSPEC_VOLATILE: 2666 return 0; 2667 2668 case ASM_OPERANDS: 2669 if (MEM_VOLATILE_P (x)) 2670 return 0; 2671 2672 /* Fall through. */ 2673 2674 default: 2675 break; 2676 } 2677 2678 fmt = GET_RTX_FORMAT (code); 2679 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 2680 switch (fmt[i]) 2681 { 2682 case 'e': 2683 if (! equiv_init_movable_p (XEXP (x, i), regno)) 2684 return 0; 2685 break; 2686 case 'E': 2687 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 2688 if (! equiv_init_movable_p (XVECEXP (x, i, j), regno)) 2689 return 0; 2690 break; 2691 } 2692 2693 return 1; 2694 } 2695 2696 /* TRUE if X uses any registers for which reg_equiv[REGNO].replace is 2697 true. */ 2698 static int 2699 contains_replace_regs (rtx x) 2700 { 2701 int i, j; 2702 const char *fmt; 2703 enum rtx_code code = GET_CODE (x); 2704 2705 switch (code) 2706 { 2707 case CONST: 2708 case LABEL_REF: 2709 case SYMBOL_REF: 2710 CASE_CONST_ANY: 2711 case PC: 2712 case CC0: 2713 case HIGH: 2714 return 0; 2715 2716 case REG: 2717 return reg_equiv[REGNO (x)].replace; 2718 2719 default: 2720 break; 2721 } 2722 2723 fmt = GET_RTX_FORMAT (code); 2724 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 2725 switch (fmt[i]) 2726 { 2727 case 'e': 2728 if (contains_replace_regs (XEXP (x, i))) 2729 return 1; 2730 break; 2731 case 'E': 2732 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 2733 if (contains_replace_regs (XVECEXP (x, i, j))) 2734 return 1; 2735 break; 2736 } 2737 2738 return 0; 2739 } 2740 2741 /* TRUE if X references a memory location that would be affected by a store 2742 to MEMREF. */ 2743 static int 2744 memref_referenced_p (rtx memref, rtx x) 2745 { 2746 int i, j; 2747 const char *fmt; 2748 enum rtx_code code = GET_CODE (x); 2749 2750 switch (code) 2751 { 2752 case CONST: 2753 case LABEL_REF: 2754 case SYMBOL_REF: 2755 CASE_CONST_ANY: 2756 case PC: 2757 case CC0: 2758 case HIGH: 2759 case LO_SUM: 2760 return 0; 2761 2762 case REG: 2763 return (reg_equiv[REGNO (x)].replacement 2764 && memref_referenced_p (memref, 2765 reg_equiv[REGNO (x)].replacement)); 2766 2767 case MEM: 2768 if (true_dependence (memref, VOIDmode, x)) 2769 return 1; 2770 break; 2771 2772 case SET: 2773 /* If we are setting a MEM, it doesn't count (its address does), but any 2774 other SET_DEST that has a MEM in it is referencing the MEM. */ 2775 if (MEM_P (SET_DEST (x))) 2776 { 2777 if (memref_referenced_p (memref, XEXP (SET_DEST (x), 0))) 2778 return 1; 2779 } 2780 else if (memref_referenced_p (memref, SET_DEST (x))) 2781 return 1; 2782 2783 return memref_referenced_p (memref, SET_SRC (x)); 2784 2785 default: 2786 break; 2787 } 2788 2789 fmt = GET_RTX_FORMAT (code); 2790 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 2791 switch (fmt[i]) 2792 { 2793 case 'e': 2794 if (memref_referenced_p (memref, XEXP (x, i))) 2795 return 1; 2796 break; 2797 case 'E': 2798 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 2799 if (memref_referenced_p (memref, XVECEXP (x, i, j))) 2800 return 1; 2801 break; 2802 } 2803 2804 return 0; 2805 } 2806 2807 /* TRUE if some insn in the range (START, END] references a memory location 2808 that would be affected by a store to MEMREF. */ 2809 static int 2810 memref_used_between_p (rtx memref, rtx start, rtx end) 2811 { 2812 rtx insn; 2813 2814 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end); 2815 insn = NEXT_INSN (insn)) 2816 { 2817 if (!NONDEBUG_INSN_P (insn)) 2818 continue; 2819 2820 if (memref_referenced_p (memref, PATTERN (insn))) 2821 return 1; 2822 2823 /* Nonconst functions may access memory. */ 2824 if (CALL_P (insn) && (! RTL_CONST_CALL_P (insn))) 2825 return 1; 2826 } 2827 2828 return 0; 2829 } 2830 2831 /* Mark REG as having no known equivalence. 2832 Some instructions might have been processed before and furnished 2833 with REG_EQUIV notes for this register; these notes will have to be 2834 removed. 2835 STORE is the piece of RTL that does the non-constant / conflicting 2836 assignment - a SET, CLOBBER or REG_INC note. It is currently not used, 2837 but needs to be there because this function is called from note_stores. */ 2838 static void 2839 no_equiv (rtx reg, const_rtx store ATTRIBUTE_UNUSED, 2840 void *data ATTRIBUTE_UNUSED) 2841 { 2842 int regno; 2843 rtx list; 2844 2845 if (!REG_P (reg)) 2846 return; 2847 regno = REGNO (reg); 2848 list = reg_equiv[regno].init_insns; 2849 if (list == const0_rtx) 2850 return; 2851 reg_equiv[regno].init_insns = const0_rtx; 2852 reg_equiv[regno].replacement = NULL_RTX; 2853 /* This doesn't matter for equivalences made for argument registers, we 2854 should keep their initialization insns. */ 2855 if (reg_equiv[regno].is_arg_equivalence) 2856 return; 2857 ira_reg_equiv[regno].defined_p = false; 2858 ira_reg_equiv[regno].init_insns = NULL_RTX; 2859 for (; list; list = XEXP (list, 1)) 2860 { 2861 rtx insn = XEXP (list, 0); 2862 remove_note (insn, find_reg_note (insn, REG_EQUIV, NULL_RTX)); 2863 } 2864 } 2865 2866 /* Check whether the SUBREG is a paradoxical subreg and set the result 2867 in PDX_SUBREGS. */ 2868 2869 static int 2870 set_paradoxical_subreg (rtx *subreg, void *pdx_subregs) 2871 { 2872 rtx reg; 2873 2874 if ((*subreg) == NULL_RTX) 2875 return 1; 2876 if (GET_CODE (*subreg) != SUBREG) 2877 return 0; 2878 reg = SUBREG_REG (*subreg); 2879 if (!REG_P (reg)) 2880 return 0; 2881 2882 if (paradoxical_subreg_p (*subreg)) 2883 ((bool *)pdx_subregs)[REGNO (reg)] = true; 2884 2885 return 0; 2886 } 2887 2888 /* In DEBUG_INSN location adjust REGs from CLEARED_REGS bitmap to the 2889 equivalent replacement. */ 2890 2891 static rtx 2892 adjust_cleared_regs (rtx loc, const_rtx old_rtx ATTRIBUTE_UNUSED, void *data) 2893 { 2894 if (REG_P (loc)) 2895 { 2896 bitmap cleared_regs = (bitmap) data; 2897 if (bitmap_bit_p (cleared_regs, REGNO (loc))) 2898 return simplify_replace_fn_rtx (*reg_equiv[REGNO (loc)].src_p, 2899 NULL_RTX, adjust_cleared_regs, data); 2900 } 2901 return NULL_RTX; 2902 } 2903 2904 /* Nonzero if we recorded an equivalence for a LABEL_REF. */ 2905 static int recorded_label_ref; 2906 2907 /* Find registers that are equivalent to a single value throughout the 2908 compilation (either because they can be referenced in memory or are 2909 set once from a single constant). Lower their priority for a 2910 register. 2911 2912 If such a register is only referenced once, try substituting its 2913 value into the using insn. If it succeeds, we can eliminate the 2914 register completely. 2915 2916 Initialize init_insns in ira_reg_equiv array. 2917 2918 Return non-zero if jump label rebuilding should be done. */ 2919 static int 2920 update_equiv_regs (void) 2921 { 2922 rtx insn; 2923 basic_block bb; 2924 int loop_depth; 2925 bitmap cleared_regs; 2926 bool *pdx_subregs; 2927 2928 /* We need to keep track of whether or not we recorded a LABEL_REF so 2929 that we know if the jump optimizer needs to be rerun. */ 2930 recorded_label_ref = 0; 2931 2932 /* Use pdx_subregs to show whether a reg is used in a paradoxical 2933 subreg. */ 2934 pdx_subregs = XCNEWVEC (bool, max_regno); 2935 2936 reg_equiv = XCNEWVEC (struct equivalence, max_regno); 2937 grow_reg_equivs (); 2938 2939 init_alias_analysis (); 2940 2941 /* Scan insns and set pdx_subregs[regno] if the reg is used in a 2942 paradoxical subreg. Don't set such reg sequivalent to a mem, 2943 because lra will not substitute such equiv memory in order to 2944 prevent access beyond allocated memory for paradoxical memory subreg. */ 2945 FOR_EACH_BB (bb) 2946 FOR_BB_INSNS (bb, insn) 2947 if (NONDEBUG_INSN_P (insn)) 2948 for_each_rtx (&insn, set_paradoxical_subreg, (void *) pdx_subregs); 2949 2950 /* Scan the insns and find which registers have equivalences. Do this 2951 in a separate scan of the insns because (due to -fcse-follow-jumps) 2952 a register can be set below its use. */ 2953 FOR_EACH_BB (bb) 2954 { 2955 loop_depth = bb_loop_depth (bb); 2956 2957 for (insn = BB_HEAD (bb); 2958 insn != NEXT_INSN (BB_END (bb)); 2959 insn = NEXT_INSN (insn)) 2960 { 2961 rtx note; 2962 rtx set; 2963 rtx dest, src; 2964 int regno; 2965 2966 if (! INSN_P (insn)) 2967 continue; 2968 2969 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 2970 if (REG_NOTE_KIND (note) == REG_INC) 2971 no_equiv (XEXP (note, 0), note, NULL); 2972 2973 set = single_set (insn); 2974 2975 /* If this insn contains more (or less) than a single SET, 2976 only mark all destinations as having no known equivalence. */ 2977 if (set == 0) 2978 { 2979 note_stores (PATTERN (insn), no_equiv, NULL); 2980 continue; 2981 } 2982 else if (GET_CODE (PATTERN (insn)) == PARALLEL) 2983 { 2984 int i; 2985 2986 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--) 2987 { 2988 rtx part = XVECEXP (PATTERN (insn), 0, i); 2989 if (part != set) 2990 note_stores (part, no_equiv, NULL); 2991 } 2992 } 2993 2994 dest = SET_DEST (set); 2995 src = SET_SRC (set); 2996 2997 /* See if this is setting up the equivalence between an argument 2998 register and its stack slot. */ 2999 note = find_reg_note (insn, REG_EQUIV, NULL_RTX); 3000 if (note) 3001 { 3002 gcc_assert (REG_P (dest)); 3003 regno = REGNO (dest); 3004 3005 /* Note that we don't want to clear init_insns in 3006 ira_reg_equiv even if there are multiple sets of this 3007 register. */ 3008 reg_equiv[regno].is_arg_equivalence = 1; 3009 3010 /* Record for reload that this is an equivalencing insn. */ 3011 if (rtx_equal_p (src, XEXP (note, 0))) 3012 ira_reg_equiv[regno].init_insns 3013 = gen_rtx_INSN_LIST (VOIDmode, insn, 3014 ira_reg_equiv[regno].init_insns); 3015 3016 /* Continue normally in case this is a candidate for 3017 replacements. */ 3018 } 3019 3020 if (!optimize) 3021 continue; 3022 3023 /* We only handle the case of a pseudo register being set 3024 once, or always to the same value. */ 3025 /* ??? The mn10200 port breaks if we add equivalences for 3026 values that need an ADDRESS_REGS register and set them equivalent 3027 to a MEM of a pseudo. The actual problem is in the over-conservative 3028 handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in 3029 calculate_needs, but we traditionally work around this problem 3030 here by rejecting equivalences when the destination is in a register 3031 that's likely spilled. This is fragile, of course, since the 3032 preferred class of a pseudo depends on all instructions that set 3033 or use it. */ 3034 3035 if (!REG_P (dest) 3036 || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER 3037 || reg_equiv[regno].init_insns == const0_rtx 3038 || (targetm.class_likely_spilled_p (reg_preferred_class (regno)) 3039 && MEM_P (src) && ! reg_equiv[regno].is_arg_equivalence)) 3040 { 3041 /* This might be setting a SUBREG of a pseudo, a pseudo that is 3042 also set somewhere else to a constant. */ 3043 note_stores (set, no_equiv, NULL); 3044 continue; 3045 } 3046 3047 /* Don't set reg (if pdx_subregs[regno] == true) equivalent to a mem. */ 3048 if (MEM_P (src) && pdx_subregs[regno]) 3049 { 3050 note_stores (set, no_equiv, NULL); 3051 continue; 3052 } 3053 3054 note = find_reg_note (insn, REG_EQUAL, NULL_RTX); 3055 3056 /* cse sometimes generates function invariants, but doesn't put a 3057 REG_EQUAL note on the insn. Since this note would be redundant, 3058 there's no point creating it earlier than here. */ 3059 if (! note && ! rtx_varies_p (src, 0)) 3060 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src)); 3061 3062 /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST 3063 since it represents a function call */ 3064 if (note && GET_CODE (XEXP (note, 0)) == EXPR_LIST) 3065 note = NULL_RTX; 3066 3067 if (DF_REG_DEF_COUNT (regno) != 1 3068 && (! note 3069 || rtx_varies_p (XEXP (note, 0), 0) 3070 || (reg_equiv[regno].replacement 3071 && ! rtx_equal_p (XEXP (note, 0), 3072 reg_equiv[regno].replacement)))) 3073 { 3074 no_equiv (dest, set, NULL); 3075 continue; 3076 } 3077 /* Record this insn as initializing this register. */ 3078 reg_equiv[regno].init_insns 3079 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv[regno].init_insns); 3080 3081 /* If this register is known to be equal to a constant, record that 3082 it is always equivalent to the constant. */ 3083 if (DF_REG_DEF_COUNT (regno) == 1 3084 && note && ! rtx_varies_p (XEXP (note, 0), 0)) 3085 { 3086 rtx note_value = XEXP (note, 0); 3087 remove_note (insn, note); 3088 set_unique_reg_note (insn, REG_EQUIV, note_value); 3089 } 3090 3091 /* If this insn introduces a "constant" register, decrease the priority 3092 of that register. Record this insn if the register is only used once 3093 more and the equivalence value is the same as our source. 3094 3095 The latter condition is checked for two reasons: First, it is an 3096 indication that it may be more efficient to actually emit the insn 3097 as written (if no registers are available, reload will substitute 3098 the equivalence). Secondly, it avoids problems with any registers 3099 dying in this insn whose death notes would be missed. 3100 3101 If we don't have a REG_EQUIV note, see if this insn is loading 3102 a register used only in one basic block from a MEM. If so, and the 3103 MEM remains unchanged for the life of the register, add a REG_EQUIV 3104 note. */ 3105 3106 note = find_reg_note (insn, REG_EQUIV, NULL_RTX); 3107 3108 if (note == 0 && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS 3109 && MEM_P (SET_SRC (set)) 3110 && validate_equiv_mem (insn, dest, SET_SRC (set))) 3111 note = set_unique_reg_note (insn, REG_EQUIV, copy_rtx (SET_SRC (set))); 3112 3113 if (note) 3114 { 3115 int regno = REGNO (dest); 3116 rtx x = XEXP (note, 0); 3117 3118 /* If we haven't done so, record for reload that this is an 3119 equivalencing insn. */ 3120 if (!reg_equiv[regno].is_arg_equivalence) 3121 ira_reg_equiv[regno].init_insns 3122 = gen_rtx_INSN_LIST (VOIDmode, insn, 3123 ira_reg_equiv[regno].init_insns); 3124 3125 /* Record whether or not we created a REG_EQUIV note for a LABEL_REF. 3126 We might end up substituting the LABEL_REF for uses of the 3127 pseudo here or later. That kind of transformation may turn an 3128 indirect jump into a direct jump, in which case we must rerun the 3129 jump optimizer to ensure that the JUMP_LABEL fields are valid. */ 3130 if (GET_CODE (x) == LABEL_REF 3131 || (GET_CODE (x) == CONST 3132 && GET_CODE (XEXP (x, 0)) == PLUS 3133 && (GET_CODE (XEXP (XEXP (x, 0), 0)) == LABEL_REF))) 3134 recorded_label_ref = 1; 3135 3136 reg_equiv[regno].replacement = x; 3137 reg_equiv[regno].src_p = &SET_SRC (set); 3138 reg_equiv[regno].loop_depth = loop_depth; 3139 3140 /* Don't mess with things live during setjmp. */ 3141 if (REG_LIVE_LENGTH (regno) >= 0 && optimize) 3142 { 3143 /* Note that the statement below does not affect the priority 3144 in local-alloc! */ 3145 REG_LIVE_LENGTH (regno) *= 2; 3146 3147 /* If the register is referenced exactly twice, meaning it is 3148 set once and used once, indicate that the reference may be 3149 replaced by the equivalence we computed above. Do this 3150 even if the register is only used in one block so that 3151 dependencies can be handled where the last register is 3152 used in a different block (i.e. HIGH / LO_SUM sequences) 3153 and to reduce the number of registers alive across 3154 calls. */ 3155 3156 if (REG_N_REFS (regno) == 2 3157 && (rtx_equal_p (x, src) 3158 || ! equiv_init_varies_p (src)) 3159 && NONJUMP_INSN_P (insn) 3160 && equiv_init_movable_p (PATTERN (insn), regno)) 3161 reg_equiv[regno].replace = 1; 3162 } 3163 } 3164 } 3165 } 3166 3167 if (!optimize) 3168 goto out; 3169 3170 /* A second pass, to gather additional equivalences with memory. This needs 3171 to be done after we know which registers we are going to replace. */ 3172 3173 for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 3174 { 3175 rtx set, src, dest; 3176 unsigned regno; 3177 3178 if (! INSN_P (insn)) 3179 continue; 3180 3181 set = single_set (insn); 3182 if (! set) 3183 continue; 3184 3185 dest = SET_DEST (set); 3186 src = SET_SRC (set); 3187 3188 /* If this sets a MEM to the contents of a REG that is only used 3189 in a single basic block, see if the register is always equivalent 3190 to that memory location and if moving the store from INSN to the 3191 insn that set REG is safe. If so, put a REG_EQUIV note on the 3192 initializing insn. 3193 3194 Don't add a REG_EQUIV note if the insn already has one. The existing 3195 REG_EQUIV is likely more useful than the one we are adding. 3196 3197 If one of the regs in the address has reg_equiv[REGNO].replace set, 3198 then we can't add this REG_EQUIV note. The reg_equiv[REGNO].replace 3199 optimization may move the set of this register immediately before 3200 insn, which puts it after reg_equiv[REGNO].init_insns, and hence 3201 the mention in the REG_EQUIV note would be to an uninitialized 3202 pseudo. */ 3203 3204 if (MEM_P (dest) && REG_P (src) 3205 && (regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER 3206 && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS 3207 && DF_REG_DEF_COUNT (regno) == 1 3208 && reg_equiv[regno].init_insns != 0 3209 && reg_equiv[regno].init_insns != const0_rtx 3210 && ! find_reg_note (XEXP (reg_equiv[regno].init_insns, 0), 3211 REG_EQUIV, NULL_RTX) 3212 && ! contains_replace_regs (XEXP (dest, 0)) 3213 && ! pdx_subregs[regno]) 3214 { 3215 rtx init_insn = XEXP (reg_equiv[regno].init_insns, 0); 3216 if (validate_equiv_mem (init_insn, src, dest) 3217 && ! memref_used_between_p (dest, init_insn, insn) 3218 /* Attaching a REG_EQUIV note will fail if INIT_INSN has 3219 multiple sets. */ 3220 && set_unique_reg_note (init_insn, REG_EQUIV, copy_rtx (dest))) 3221 { 3222 /* This insn makes the equivalence, not the one initializing 3223 the register. */ 3224 ira_reg_equiv[regno].init_insns 3225 = gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX); 3226 df_notes_rescan (init_insn); 3227 } 3228 } 3229 } 3230 3231 cleared_regs = BITMAP_ALLOC (NULL); 3232 /* Now scan all regs killed in an insn to see if any of them are 3233 registers only used that once. If so, see if we can replace the 3234 reference with the equivalent form. If we can, delete the 3235 initializing reference and this register will go away. If we 3236 can't replace the reference, and the initializing reference is 3237 within the same loop (or in an inner loop), then move the register 3238 initialization just before the use, so that they are in the same 3239 basic block. */ 3240 FOR_EACH_BB_REVERSE (bb) 3241 { 3242 loop_depth = bb_loop_depth (bb); 3243 for (insn = BB_END (bb); 3244 insn != PREV_INSN (BB_HEAD (bb)); 3245 insn = PREV_INSN (insn)) 3246 { 3247 rtx link; 3248 3249 if (! INSN_P (insn)) 3250 continue; 3251 3252 /* Don't substitute into a non-local goto, this confuses CFG. */ 3253 if (JUMP_P (insn) 3254 && find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX)) 3255 continue; 3256 3257 for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 3258 { 3259 if (REG_NOTE_KIND (link) == REG_DEAD 3260 /* Make sure this insn still refers to the register. */ 3261 && reg_mentioned_p (XEXP (link, 0), PATTERN (insn))) 3262 { 3263 int regno = REGNO (XEXP (link, 0)); 3264 rtx equiv_insn; 3265 3266 if (! reg_equiv[regno].replace 3267 || reg_equiv[regno].loop_depth < loop_depth 3268 /* There is no sense to move insns if we did 3269 register pressure-sensitive scheduling was 3270 done because it will not improve allocation 3271 but worsen insn schedule with a big 3272 probability. */ 3273 || (flag_sched_pressure && flag_schedule_insns)) 3274 continue; 3275 3276 /* reg_equiv[REGNO].replace gets set only when 3277 REG_N_REFS[REGNO] is 2, i.e. the register is set 3278 once and used once. (If it were only set, but 3279 not used, flow would have deleted the setting 3280 insns.) Hence there can only be one insn in 3281 reg_equiv[REGNO].init_insns. */ 3282 gcc_assert (reg_equiv[regno].init_insns 3283 && !XEXP (reg_equiv[regno].init_insns, 1)); 3284 equiv_insn = XEXP (reg_equiv[regno].init_insns, 0); 3285 3286 /* We may not move instructions that can throw, since 3287 that changes basic block boundaries and we are not 3288 prepared to adjust the CFG to match. */ 3289 if (can_throw_internal (equiv_insn)) 3290 continue; 3291 3292 if (asm_noperands (PATTERN (equiv_insn)) < 0 3293 && validate_replace_rtx (regno_reg_rtx[regno], 3294 *(reg_equiv[regno].src_p), insn)) 3295 { 3296 rtx equiv_link; 3297 rtx last_link; 3298 rtx note; 3299 3300 /* Find the last note. */ 3301 for (last_link = link; XEXP (last_link, 1); 3302 last_link = XEXP (last_link, 1)) 3303 ; 3304 3305 /* Append the REG_DEAD notes from equiv_insn. */ 3306 equiv_link = REG_NOTES (equiv_insn); 3307 while (equiv_link) 3308 { 3309 note = equiv_link; 3310 equiv_link = XEXP (equiv_link, 1); 3311 if (REG_NOTE_KIND (note) == REG_DEAD) 3312 { 3313 remove_note (equiv_insn, note); 3314 XEXP (last_link, 1) = note; 3315 XEXP (note, 1) = NULL_RTX; 3316 last_link = note; 3317 } 3318 } 3319 3320 remove_death (regno, insn); 3321 SET_REG_N_REFS (regno, 0); 3322 REG_FREQ (regno) = 0; 3323 delete_insn (equiv_insn); 3324 3325 reg_equiv[regno].init_insns 3326 = XEXP (reg_equiv[regno].init_insns, 1); 3327 3328 ira_reg_equiv[regno].init_insns = NULL_RTX; 3329 bitmap_set_bit (cleared_regs, regno); 3330 } 3331 /* Move the initialization of the register to just before 3332 INSN. Update the flow information. */ 3333 else if (prev_nondebug_insn (insn) != equiv_insn) 3334 { 3335 rtx new_insn; 3336 3337 new_insn = emit_insn_before (PATTERN (equiv_insn), insn); 3338 REG_NOTES (new_insn) = REG_NOTES (equiv_insn); 3339 REG_NOTES (equiv_insn) = 0; 3340 /* Rescan it to process the notes. */ 3341 df_insn_rescan (new_insn); 3342 3343 /* Make sure this insn is recognized before 3344 reload begins, otherwise 3345 eliminate_regs_in_insn will die. */ 3346 INSN_CODE (new_insn) = INSN_CODE (equiv_insn); 3347 3348 delete_insn (equiv_insn); 3349 3350 XEXP (reg_equiv[regno].init_insns, 0) = new_insn; 3351 3352 REG_BASIC_BLOCK (regno) = bb->index; 3353 REG_N_CALLS_CROSSED (regno) = 0; 3354 REG_FREQ_CALLS_CROSSED (regno) = 0; 3355 REG_N_THROWING_CALLS_CROSSED (regno) = 0; 3356 REG_LIVE_LENGTH (regno) = 2; 3357 3358 if (insn == BB_HEAD (bb)) 3359 BB_HEAD (bb) = PREV_INSN (insn); 3360 3361 ira_reg_equiv[regno].init_insns 3362 = gen_rtx_INSN_LIST (VOIDmode, new_insn, NULL_RTX); 3363 bitmap_set_bit (cleared_regs, regno); 3364 } 3365 } 3366 } 3367 } 3368 } 3369 3370 if (!bitmap_empty_p (cleared_regs)) 3371 { 3372 FOR_EACH_BB (bb) 3373 { 3374 bitmap_and_compl_into (DF_LR_IN (bb), cleared_regs); 3375 bitmap_and_compl_into (DF_LR_OUT (bb), cleared_regs); 3376 if (! df_live) 3377 continue; 3378 bitmap_and_compl_into (DF_LIVE_IN (bb), cleared_regs); 3379 bitmap_and_compl_into (DF_LIVE_OUT (bb), cleared_regs); 3380 } 3381 3382 /* Last pass - adjust debug insns referencing cleared regs. */ 3383 if (MAY_HAVE_DEBUG_INSNS) 3384 for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 3385 if (DEBUG_INSN_P (insn)) 3386 { 3387 rtx old_loc = INSN_VAR_LOCATION_LOC (insn); 3388 INSN_VAR_LOCATION_LOC (insn) 3389 = simplify_replace_fn_rtx (old_loc, NULL_RTX, 3390 adjust_cleared_regs, 3391 (void *) cleared_regs); 3392 if (old_loc != INSN_VAR_LOCATION_LOC (insn)) 3393 df_insn_rescan (insn); 3394 } 3395 } 3396 3397 BITMAP_FREE (cleared_regs); 3398 3399 out: 3400 /* Clean up. */ 3401 3402 end_alias_analysis (); 3403 free (reg_equiv); 3404 free (pdx_subregs); 3405 return recorded_label_ref; 3406 } 3407 3408 3409 3410 /* Set up fields memory, constant, and invariant from init_insns in 3411 the structures of array ira_reg_equiv. */ 3412 static void 3413 setup_reg_equiv (void) 3414 { 3415 int i; 3416 rtx elem, insn, set, x; 3417 3418 for (i = FIRST_PSEUDO_REGISTER; i < ira_reg_equiv_len; i++) 3419 for (elem = ira_reg_equiv[i].init_insns; elem; elem = XEXP (elem, 1)) 3420 { 3421 insn = XEXP (elem, 0); 3422 set = single_set (insn); 3423 3424 /* Init insns can set up equivalence when the reg is a destination or 3425 a source (in this case the destination is memory). */ 3426 if (set != 0 && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set)))) 3427 { 3428 if ((x = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != NULL) 3429 x = XEXP (x, 0); 3430 else if (REG_P (SET_DEST (set)) 3431 && REGNO (SET_DEST (set)) == (unsigned int) i) 3432 x = SET_SRC (set); 3433 else 3434 { 3435 gcc_assert (REG_P (SET_SRC (set)) 3436 && REGNO (SET_SRC (set)) == (unsigned int) i); 3437 x = SET_DEST (set); 3438 } 3439 if (! function_invariant_p (x) 3440 || ! flag_pic 3441 /* A function invariant is often CONSTANT_P but may 3442 include a register. We promise to only pass 3443 CONSTANT_P objects to LEGITIMATE_PIC_OPERAND_P. */ 3444 || (CONSTANT_P (x) && LEGITIMATE_PIC_OPERAND_P (x))) 3445 { 3446 /* It can happen that a REG_EQUIV note contains a MEM 3447 that is not a legitimate memory operand. As later 3448 stages of reload assume that all addresses found in 3449 the lra_regno_equiv_* arrays were originally 3450 legitimate, we ignore such REG_EQUIV notes. */ 3451 if (memory_operand (x, VOIDmode)) 3452 { 3453 ira_reg_equiv[i].defined_p = true; 3454 ira_reg_equiv[i].memory = x; 3455 continue; 3456 } 3457 else if (function_invariant_p (x)) 3458 { 3459 enum machine_mode mode; 3460 3461 mode = GET_MODE (SET_DEST (set)); 3462 if (GET_CODE (x) == PLUS 3463 || x == frame_pointer_rtx || x == arg_pointer_rtx) 3464 /* This is PLUS of frame pointer and a constant, 3465 or fp, or argp. */ 3466 ira_reg_equiv[i].invariant = x; 3467 else if (targetm.legitimate_constant_p (mode, x)) 3468 ira_reg_equiv[i].constant = x; 3469 else 3470 { 3471 ira_reg_equiv[i].memory = force_const_mem (mode, x); 3472 if (ira_reg_equiv[i].memory == NULL_RTX) 3473 { 3474 ira_reg_equiv[i].defined_p = false; 3475 ira_reg_equiv[i].init_insns = NULL_RTX; 3476 break; 3477 } 3478 } 3479 ira_reg_equiv[i].defined_p = true; 3480 continue; 3481 } 3482 } 3483 } 3484 ira_reg_equiv[i].defined_p = false; 3485 ira_reg_equiv[i].init_insns = NULL_RTX; 3486 break; 3487 } 3488 } 3489 3490 3491 3492 /* Print chain C to FILE. */ 3493 static void 3494 print_insn_chain (FILE *file, struct insn_chain *c) 3495 { 3496 fprintf (file, "insn=%d, ", INSN_UID(c->insn)); 3497 bitmap_print (file, &c->live_throughout, "live_throughout: ", ", "); 3498 bitmap_print (file, &c->dead_or_set, "dead_or_set: ", "\n"); 3499 } 3500 3501 3502 /* Print all reload_insn_chains to FILE. */ 3503 static void 3504 print_insn_chains (FILE *file) 3505 { 3506 struct insn_chain *c; 3507 for (c = reload_insn_chain; c ; c = c->next) 3508 print_insn_chain (file, c); 3509 } 3510 3511 /* Return true if pseudo REGNO should be added to set live_throughout 3512 or dead_or_set of the insn chains for reload consideration. */ 3513 static bool 3514 pseudo_for_reload_consideration_p (int regno) 3515 { 3516 /* Consider spilled pseudos too for IRA because they still have a 3517 chance to get hard-registers in the reload when IRA is used. */ 3518 return (reg_renumber[regno] >= 0 || ira_conflicts_p); 3519 } 3520 3521 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using 3522 REG to the number of nregs, and INIT_VALUE to get the 3523 initialization. ALLOCNUM need not be the regno of REG. */ 3524 static void 3525 init_live_subregs (bool init_value, sbitmap *live_subregs, 3526 bitmap live_subregs_used, int allocnum, rtx reg) 3527 { 3528 unsigned int regno = REGNO (SUBREG_REG (reg)); 3529 int size = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno])); 3530 3531 gcc_assert (size > 0); 3532 3533 /* Been there, done that. */ 3534 if (bitmap_bit_p (live_subregs_used, allocnum)) 3535 return; 3536 3537 /* Create a new one. */ 3538 if (live_subregs[allocnum] == NULL) 3539 live_subregs[allocnum] = sbitmap_alloc (size); 3540 3541 /* If the entire reg was live before blasting into subregs, we need 3542 to init all of the subregs to ones else init to 0. */ 3543 if (init_value) 3544 bitmap_ones (live_subregs[allocnum]); 3545 else 3546 bitmap_clear (live_subregs[allocnum]); 3547 3548 bitmap_set_bit (live_subregs_used, allocnum); 3549 } 3550 3551 /* Walk the insns of the current function and build reload_insn_chain, 3552 and record register life information. */ 3553 static void 3554 build_insn_chain (void) 3555 { 3556 unsigned int i; 3557 struct insn_chain **p = &reload_insn_chain; 3558 basic_block bb; 3559 struct insn_chain *c = NULL; 3560 struct insn_chain *next = NULL; 3561 bitmap live_relevant_regs = BITMAP_ALLOC (NULL); 3562 bitmap elim_regset = BITMAP_ALLOC (NULL); 3563 /* live_subregs is a vector used to keep accurate information about 3564 which hardregs are live in multiword pseudos. live_subregs and 3565 live_subregs_used are indexed by pseudo number. The live_subreg 3566 entry for a particular pseudo is only used if the corresponding 3567 element is non zero in live_subregs_used. The sbitmap size of 3568 live_subreg[allocno] is number of bytes that the pseudo can 3569 occupy. */ 3570 sbitmap *live_subregs = XCNEWVEC (sbitmap, max_regno); 3571 bitmap live_subregs_used = BITMAP_ALLOC (NULL); 3572 3573 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 3574 if (TEST_HARD_REG_BIT (eliminable_regset, i)) 3575 bitmap_set_bit (elim_regset, i); 3576 FOR_EACH_BB_REVERSE (bb) 3577 { 3578 bitmap_iterator bi; 3579 rtx insn; 3580 3581 CLEAR_REG_SET (live_relevant_regs); 3582 bitmap_clear (live_subregs_used); 3583 3584 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb), 0, i, bi) 3585 { 3586 if (i >= FIRST_PSEUDO_REGISTER) 3587 break; 3588 bitmap_set_bit (live_relevant_regs, i); 3589 } 3590 3591 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb), 3592 FIRST_PSEUDO_REGISTER, i, bi) 3593 { 3594 if (pseudo_for_reload_consideration_p (i)) 3595 bitmap_set_bit (live_relevant_regs, i); 3596 } 3597 3598 FOR_BB_INSNS_REVERSE (bb, insn) 3599 { 3600 if (!NOTE_P (insn) && !BARRIER_P (insn)) 3601 { 3602 unsigned int uid = INSN_UID (insn); 3603 df_ref *def_rec; 3604 df_ref *use_rec; 3605 3606 c = new_insn_chain (); 3607 c->next = next; 3608 next = c; 3609 *p = c; 3610 p = &c->prev; 3611 3612 c->insn = insn; 3613 c->block = bb->index; 3614 3615 if (NONDEBUG_INSN_P (insn)) 3616 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) 3617 { 3618 df_ref def = *def_rec; 3619 unsigned int regno = DF_REF_REGNO (def); 3620 3621 /* Ignore may clobbers because these are generated 3622 from calls. However, every other kind of def is 3623 added to dead_or_set. */ 3624 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER)) 3625 { 3626 if (regno < FIRST_PSEUDO_REGISTER) 3627 { 3628 if (!fixed_regs[regno]) 3629 bitmap_set_bit (&c->dead_or_set, regno); 3630 } 3631 else if (pseudo_for_reload_consideration_p (regno)) 3632 bitmap_set_bit (&c->dead_or_set, regno); 3633 } 3634 3635 if ((regno < FIRST_PSEUDO_REGISTER 3636 || reg_renumber[regno] >= 0 3637 || ira_conflicts_p) 3638 && (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL))) 3639 { 3640 rtx reg = DF_REF_REG (def); 3641 3642 /* We can model subregs, but not if they are 3643 wrapped in ZERO_EXTRACTS. */ 3644 if (GET_CODE (reg) == SUBREG 3645 && !DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT)) 3646 { 3647 unsigned int start = SUBREG_BYTE (reg); 3648 unsigned int last = start 3649 + GET_MODE_SIZE (GET_MODE (reg)); 3650 3651 init_live_subregs 3652 (bitmap_bit_p (live_relevant_regs, regno), 3653 live_subregs, live_subregs_used, regno, reg); 3654 3655 if (!DF_REF_FLAGS_IS_SET 3656 (def, DF_REF_STRICT_LOW_PART)) 3657 { 3658 /* Expand the range to cover entire words. 3659 Bytes added here are "don't care". */ 3660 start 3661 = start / UNITS_PER_WORD * UNITS_PER_WORD; 3662 last = ((last + UNITS_PER_WORD - 1) 3663 / UNITS_PER_WORD * UNITS_PER_WORD); 3664 } 3665 3666 /* Ignore the paradoxical bits. */ 3667 if (last > SBITMAP_SIZE (live_subregs[regno])) 3668 last = SBITMAP_SIZE (live_subregs[regno]); 3669 3670 while (start < last) 3671 { 3672 bitmap_clear_bit (live_subregs[regno], start); 3673 start++; 3674 } 3675 3676 if (bitmap_empty_p (live_subregs[regno])) 3677 { 3678 bitmap_clear_bit (live_subregs_used, regno); 3679 bitmap_clear_bit (live_relevant_regs, regno); 3680 } 3681 else 3682 /* Set live_relevant_regs here because 3683 that bit has to be true to get us to 3684 look at the live_subregs fields. */ 3685 bitmap_set_bit (live_relevant_regs, regno); 3686 } 3687 else 3688 { 3689 /* DF_REF_PARTIAL is generated for 3690 subregs, STRICT_LOW_PART, and 3691 ZERO_EXTRACT. We handle the subreg 3692 case above so here we have to keep from 3693 modeling the def as a killing def. */ 3694 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL)) 3695 { 3696 bitmap_clear_bit (live_subregs_used, regno); 3697 bitmap_clear_bit (live_relevant_regs, regno); 3698 } 3699 } 3700 } 3701 } 3702 3703 bitmap_and_compl_into (live_relevant_regs, elim_regset); 3704 bitmap_copy (&c->live_throughout, live_relevant_regs); 3705 3706 if (NONDEBUG_INSN_P (insn)) 3707 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) 3708 { 3709 df_ref use = *use_rec; 3710 unsigned int regno = DF_REF_REGNO (use); 3711 rtx reg = DF_REF_REG (use); 3712 3713 /* DF_REF_READ_WRITE on a use means that this use 3714 is fabricated from a def that is a partial set 3715 to a multiword reg. Here, we only model the 3716 subreg case that is not wrapped in ZERO_EXTRACT 3717 precisely so we do not need to look at the 3718 fabricated use. */ 3719 if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE) 3720 && !DF_REF_FLAGS_IS_SET (use, DF_REF_ZERO_EXTRACT) 3721 && DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG)) 3722 continue; 3723 3724 /* Add the last use of each var to dead_or_set. */ 3725 if (!bitmap_bit_p (live_relevant_regs, regno)) 3726 { 3727 if (regno < FIRST_PSEUDO_REGISTER) 3728 { 3729 if (!fixed_regs[regno]) 3730 bitmap_set_bit (&c->dead_or_set, regno); 3731 } 3732 else if (pseudo_for_reload_consideration_p (regno)) 3733 bitmap_set_bit (&c->dead_or_set, regno); 3734 } 3735 3736 if (regno < FIRST_PSEUDO_REGISTER 3737 || pseudo_for_reload_consideration_p (regno)) 3738 { 3739 if (GET_CODE (reg) == SUBREG 3740 && !DF_REF_FLAGS_IS_SET (use, 3741 DF_REF_SIGN_EXTRACT 3742 | DF_REF_ZERO_EXTRACT)) 3743 { 3744 unsigned int start = SUBREG_BYTE (reg); 3745 unsigned int last = start 3746 + GET_MODE_SIZE (GET_MODE (reg)); 3747 3748 init_live_subregs 3749 (bitmap_bit_p (live_relevant_regs, regno), 3750 live_subregs, live_subregs_used, regno, reg); 3751 3752 /* Ignore the paradoxical bits. */ 3753 if (last > SBITMAP_SIZE (live_subregs[regno])) 3754 last = SBITMAP_SIZE (live_subregs[regno]); 3755 3756 while (start < last) 3757 { 3758 bitmap_set_bit (live_subregs[regno], start); 3759 start++; 3760 } 3761 } 3762 else 3763 /* Resetting the live_subregs_used is 3764 effectively saying do not use the subregs 3765 because we are reading the whole 3766 pseudo. */ 3767 bitmap_clear_bit (live_subregs_used, regno); 3768 bitmap_set_bit (live_relevant_regs, regno); 3769 } 3770 } 3771 } 3772 } 3773 3774 /* FIXME!! The following code is a disaster. Reload needs to see the 3775 labels and jump tables that are just hanging out in between 3776 the basic blocks. See pr33676. */ 3777 insn = BB_HEAD (bb); 3778 3779 /* Skip over the barriers and cruft. */ 3780 while (insn && (BARRIER_P (insn) || NOTE_P (insn) 3781 || BLOCK_FOR_INSN (insn) == bb)) 3782 insn = PREV_INSN (insn); 3783 3784 /* While we add anything except barriers and notes, the focus is 3785 to get the labels and jump tables into the 3786 reload_insn_chain. */ 3787 while (insn) 3788 { 3789 if (!NOTE_P (insn) && !BARRIER_P (insn)) 3790 { 3791 if (BLOCK_FOR_INSN (insn)) 3792 break; 3793 3794 c = new_insn_chain (); 3795 c->next = next; 3796 next = c; 3797 *p = c; 3798 p = &c->prev; 3799 3800 /* The block makes no sense here, but it is what the old 3801 code did. */ 3802 c->block = bb->index; 3803 c->insn = insn; 3804 bitmap_copy (&c->live_throughout, live_relevant_regs); 3805 } 3806 insn = PREV_INSN (insn); 3807 } 3808 } 3809 3810 reload_insn_chain = c; 3811 *p = NULL; 3812 3813 for (i = 0; i < (unsigned int) max_regno; i++) 3814 if (live_subregs[i] != NULL) 3815 sbitmap_free (live_subregs[i]); 3816 free (live_subregs); 3817 BITMAP_FREE (live_subregs_used); 3818 BITMAP_FREE (live_relevant_regs); 3819 BITMAP_FREE (elim_regset); 3820 3821 if (dump_file) 3822 print_insn_chains (dump_file); 3823 } 3824 3825 /* Examine the rtx found in *LOC, which is read or written to as determined 3826 by TYPE. Return false if we find a reason why an insn containing this 3827 rtx should not be moved (such as accesses to non-constant memory), true 3828 otherwise. */ 3829 static bool 3830 rtx_moveable_p (rtx *loc, enum op_type type) 3831 { 3832 const char *fmt; 3833 rtx x = *loc; 3834 enum rtx_code code = GET_CODE (x); 3835 int i, j; 3836 3837 code = GET_CODE (x); 3838 switch (code) 3839 { 3840 case CONST: 3841 CASE_CONST_ANY: 3842 case SYMBOL_REF: 3843 case LABEL_REF: 3844 return true; 3845 3846 case PC: 3847 return type == OP_IN; 3848 3849 case CC0: 3850 return false; 3851 3852 case REG: 3853 if (x == frame_pointer_rtx) 3854 return true; 3855 if (HARD_REGISTER_P (x)) 3856 return false; 3857 3858 return true; 3859 3860 case MEM: 3861 if (type == OP_IN && MEM_READONLY_P (x)) 3862 return rtx_moveable_p (&XEXP (x, 0), OP_IN); 3863 return false; 3864 3865 case SET: 3866 return (rtx_moveable_p (&SET_SRC (x), OP_IN) 3867 && rtx_moveable_p (&SET_DEST (x), OP_OUT)); 3868 3869 case STRICT_LOW_PART: 3870 return rtx_moveable_p (&XEXP (x, 0), OP_OUT); 3871 3872 case ZERO_EXTRACT: 3873 case SIGN_EXTRACT: 3874 return (rtx_moveable_p (&XEXP (x, 0), type) 3875 && rtx_moveable_p (&XEXP (x, 1), OP_IN) 3876 && rtx_moveable_p (&XEXP (x, 2), OP_IN)); 3877 3878 case CLOBBER: 3879 return rtx_moveable_p (&SET_DEST (x), OP_OUT); 3880 3881 case UNSPEC_VOLATILE: 3882 /* It is a bad idea to consider insns with with such rtl 3883 as moveable ones. The insn scheduler also considers them as barrier 3884 for a reason. */ 3885 return false; 3886 3887 default: 3888 break; 3889 } 3890 3891 fmt = GET_RTX_FORMAT (code); 3892 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 3893 { 3894 if (fmt[i] == 'e') 3895 { 3896 if (!rtx_moveable_p (&XEXP (x, i), type)) 3897 return false; 3898 } 3899 else if (fmt[i] == 'E') 3900 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 3901 { 3902 if (!rtx_moveable_p (&XVECEXP (x, i, j), type)) 3903 return false; 3904 } 3905 } 3906 return true; 3907 } 3908 3909 /* A wrapper around dominated_by_p, which uses the information in UID_LUID 3910 to give dominance relationships between two insns I1 and I2. */ 3911 static bool 3912 insn_dominated_by_p (rtx i1, rtx i2, int *uid_luid) 3913 { 3914 basic_block bb1 = BLOCK_FOR_INSN (i1); 3915 basic_block bb2 = BLOCK_FOR_INSN (i2); 3916 3917 if (bb1 == bb2) 3918 return uid_luid[INSN_UID (i2)] < uid_luid[INSN_UID (i1)]; 3919 return dominated_by_p (CDI_DOMINATORS, bb1, bb2); 3920 } 3921 3922 /* Record the range of register numbers added by find_moveable_pseudos. */ 3923 int first_moveable_pseudo, last_moveable_pseudo; 3924 3925 /* These two vectors hold data for every register added by 3926 find_movable_pseudos, with index 0 holding data for the 3927 first_moveable_pseudo. */ 3928 /* The original home register. */ 3929 static vec<rtx> pseudo_replaced_reg; 3930 3931 /* Look for instances where we have an instruction that is known to increase 3932 register pressure, and whose result is not used immediately. If it is 3933 possible to move the instruction downwards to just before its first use, 3934 split its lifetime into two ranges. We create a new pseudo to compute the 3935 value, and emit a move instruction just before the first use. If, after 3936 register allocation, the new pseudo remains unallocated, the function 3937 move_unallocated_pseudos then deletes the move instruction and places 3938 the computation just before the first use. 3939 3940 Such a move is safe and profitable if all the input registers remain live 3941 and unchanged between the original computation and its first use. In such 3942 a situation, the computation is known to increase register pressure, and 3943 moving it is known to at least not worsen it. 3944 3945 We restrict moves to only those cases where a register remains unallocated, 3946 in order to avoid interfering too much with the instruction schedule. As 3947 an exception, we may move insns which only modify their input register 3948 (typically induction variables), as this increases the freedom for our 3949 intended transformation, and does not limit the second instruction 3950 scheduler pass. */ 3951 3952 static void 3953 find_moveable_pseudos (void) 3954 { 3955 unsigned i; 3956 int max_regs = max_reg_num (); 3957 int max_uid = get_max_uid (); 3958 basic_block bb; 3959 int *uid_luid = XNEWVEC (int, max_uid); 3960 rtx *closest_uses = XNEWVEC (rtx, max_regs); 3961 /* A set of registers which are live but not modified throughout a block. */ 3962 bitmap_head *bb_transp_live = XNEWVEC (bitmap_head, last_basic_block); 3963 /* A set of registers which only exist in a given basic block. */ 3964 bitmap_head *bb_local = XNEWVEC (bitmap_head, last_basic_block); 3965 /* A set of registers which are set once, in an instruction that can be 3966 moved freely downwards, but are otherwise transparent to a block. */ 3967 bitmap_head *bb_moveable_reg_sets = XNEWVEC (bitmap_head, last_basic_block); 3968 bitmap_head live, used, set, interesting, unusable_as_input; 3969 bitmap_iterator bi; 3970 bitmap_initialize (&interesting, 0); 3971 3972 first_moveable_pseudo = max_regs; 3973 pseudo_replaced_reg.release (); 3974 pseudo_replaced_reg.safe_grow_cleared (max_regs); 3975 3976 df_analyze (); 3977 calculate_dominance_info (CDI_DOMINATORS); 3978 3979 i = 0; 3980 bitmap_initialize (&live, 0); 3981 bitmap_initialize (&used, 0); 3982 bitmap_initialize (&set, 0); 3983 bitmap_initialize (&unusable_as_input, 0); 3984 FOR_EACH_BB (bb) 3985 { 3986 rtx insn; 3987 bitmap transp = bb_transp_live + bb->index; 3988 bitmap moveable = bb_moveable_reg_sets + bb->index; 3989 bitmap local = bb_local + bb->index; 3990 3991 bitmap_initialize (local, 0); 3992 bitmap_initialize (transp, 0); 3993 bitmap_initialize (moveable, 0); 3994 bitmap_copy (&live, df_get_live_out (bb)); 3995 bitmap_and_into (&live, df_get_live_in (bb)); 3996 bitmap_copy (transp, &live); 3997 bitmap_clear (moveable); 3998 bitmap_clear (&live); 3999 bitmap_clear (&used); 4000 bitmap_clear (&set); 4001 FOR_BB_INSNS (bb, insn) 4002 if (NONDEBUG_INSN_P (insn)) 4003 { 4004 df_ref *u_rec, *d_rec; 4005 4006 uid_luid[INSN_UID (insn)] = i++; 4007 4008 u_rec = DF_INSN_USES (insn); 4009 d_rec = DF_INSN_DEFS (insn); 4010 if (d_rec[0] != NULL && d_rec[1] == NULL 4011 && u_rec[0] != NULL && u_rec[1] == NULL 4012 && DF_REF_REGNO (*u_rec) == DF_REF_REGNO (*d_rec) 4013 && !bitmap_bit_p (&set, DF_REF_REGNO (*u_rec)) 4014 && rtx_moveable_p (&PATTERN (insn), OP_IN)) 4015 { 4016 unsigned regno = DF_REF_REGNO (*u_rec); 4017 bitmap_set_bit (moveable, regno); 4018 bitmap_set_bit (&set, regno); 4019 bitmap_set_bit (&used, regno); 4020 bitmap_clear_bit (transp, regno); 4021 continue; 4022 } 4023 while (*u_rec) 4024 { 4025 unsigned regno = DF_REF_REGNO (*u_rec); 4026 bitmap_set_bit (&used, regno); 4027 if (bitmap_clear_bit (moveable, regno)) 4028 bitmap_clear_bit (transp, regno); 4029 u_rec++; 4030 } 4031 4032 while (*d_rec) 4033 { 4034 unsigned regno = DF_REF_REGNO (*d_rec); 4035 bitmap_set_bit (&set, regno); 4036 bitmap_clear_bit (transp, regno); 4037 bitmap_clear_bit (moveable, regno); 4038 d_rec++; 4039 } 4040 } 4041 } 4042 4043 bitmap_clear (&live); 4044 bitmap_clear (&used); 4045 bitmap_clear (&set); 4046 4047 FOR_EACH_BB (bb) 4048 { 4049 bitmap local = bb_local + bb->index; 4050 rtx insn; 4051 4052 FOR_BB_INSNS (bb, insn) 4053 if (NONDEBUG_INSN_P (insn)) 4054 { 4055 rtx def_insn, closest_use, note; 4056 df_ref *def_rec, def, use; 4057 unsigned regno; 4058 bool all_dominated, all_local; 4059 enum machine_mode mode; 4060 4061 def_rec = DF_INSN_DEFS (insn); 4062 /* There must be exactly one def in this insn. */ 4063 def = *def_rec; 4064 if (!def || def_rec[1] || !single_set (insn)) 4065 continue; 4066 /* This must be the only definition of the reg. We also limit 4067 which modes we deal with so that we can assume we can generate 4068 move instructions. */ 4069 regno = DF_REF_REGNO (def); 4070 mode = GET_MODE (DF_REF_REG (def)); 4071 if (DF_REG_DEF_COUNT (regno) != 1 4072 || !DF_REF_INSN_INFO (def) 4073 || HARD_REGISTER_NUM_P (regno) 4074 || DF_REG_EQ_USE_COUNT (regno) > 0 4075 || (!INTEGRAL_MODE_P (mode) && !FLOAT_MODE_P (mode))) 4076 continue; 4077 def_insn = DF_REF_INSN (def); 4078 4079 for (note = REG_NOTES (def_insn); note; note = XEXP (note, 1)) 4080 if (REG_NOTE_KIND (note) == REG_EQUIV && MEM_P (XEXP (note, 0))) 4081 break; 4082 4083 if (note) 4084 { 4085 if (dump_file) 4086 fprintf (dump_file, "Ignoring reg %d, has equiv memory\n", 4087 regno); 4088 bitmap_set_bit (&unusable_as_input, regno); 4089 continue; 4090 } 4091 4092 use = DF_REG_USE_CHAIN (regno); 4093 all_dominated = true; 4094 all_local = true; 4095 closest_use = NULL_RTX; 4096 for (; use; use = DF_REF_NEXT_REG (use)) 4097 { 4098 rtx insn; 4099 if (!DF_REF_INSN_INFO (use)) 4100 { 4101 all_dominated = false; 4102 all_local = false; 4103 break; 4104 } 4105 insn = DF_REF_INSN (use); 4106 if (DEBUG_INSN_P (insn)) 4107 continue; 4108 if (BLOCK_FOR_INSN (insn) != BLOCK_FOR_INSN (def_insn)) 4109 all_local = false; 4110 if (!insn_dominated_by_p (insn, def_insn, uid_luid)) 4111 all_dominated = false; 4112 if (closest_use != insn && closest_use != const0_rtx) 4113 { 4114 if (closest_use == NULL_RTX) 4115 closest_use = insn; 4116 else if (insn_dominated_by_p (closest_use, insn, uid_luid)) 4117 closest_use = insn; 4118 else if (!insn_dominated_by_p (insn, closest_use, uid_luid)) 4119 closest_use = const0_rtx; 4120 } 4121 } 4122 if (!all_dominated) 4123 { 4124 if (dump_file) 4125 fprintf (dump_file, "Reg %d not all uses dominated by set\n", 4126 regno); 4127 continue; 4128 } 4129 if (all_local) 4130 bitmap_set_bit (local, regno); 4131 if (closest_use == const0_rtx || closest_use == NULL 4132 || next_nonnote_nondebug_insn (def_insn) == closest_use) 4133 { 4134 if (dump_file) 4135 fprintf (dump_file, "Reg %d uninteresting%s\n", regno, 4136 closest_use == const0_rtx || closest_use == NULL 4137 ? " (no unique first use)" : ""); 4138 continue; 4139 } 4140 #ifdef HAVE_cc0 4141 if (reg_referenced_p (cc0_rtx, PATTERN (closest_use))) 4142 { 4143 if (dump_file) 4144 fprintf (dump_file, "Reg %d: closest user uses cc0\n", 4145 regno); 4146 continue; 4147 } 4148 #endif 4149 bitmap_set_bit (&interesting, regno); 4150 closest_uses[regno] = closest_use; 4151 4152 if (dump_file && (all_local || all_dominated)) 4153 { 4154 fprintf (dump_file, "Reg %u:", regno); 4155 if (all_local) 4156 fprintf (dump_file, " local to bb %d", bb->index); 4157 if (all_dominated) 4158 fprintf (dump_file, " def dominates all uses"); 4159 if (closest_use != const0_rtx) 4160 fprintf (dump_file, " has unique first use"); 4161 fputs ("\n", dump_file); 4162 } 4163 } 4164 } 4165 4166 EXECUTE_IF_SET_IN_BITMAP (&interesting, 0, i, bi) 4167 { 4168 df_ref def = DF_REG_DEF_CHAIN (i); 4169 rtx def_insn = DF_REF_INSN (def); 4170 basic_block def_block = BLOCK_FOR_INSN (def_insn); 4171 bitmap def_bb_local = bb_local + def_block->index; 4172 bitmap def_bb_moveable = bb_moveable_reg_sets + def_block->index; 4173 bitmap def_bb_transp = bb_transp_live + def_block->index; 4174 bool local_to_bb_p = bitmap_bit_p (def_bb_local, i); 4175 rtx use_insn = closest_uses[i]; 4176 df_ref *def_insn_use_rec = DF_INSN_USES (def_insn); 4177 bool all_ok = true; 4178 bool all_transp = true; 4179 4180 if (!REG_P (DF_REF_REG (def))) 4181 continue; 4182 4183 if (!local_to_bb_p) 4184 { 4185 if (dump_file) 4186 fprintf (dump_file, "Reg %u not local to one basic block\n", 4187 i); 4188 continue; 4189 } 4190 if (reg_equiv_init (i) != NULL_RTX) 4191 { 4192 if (dump_file) 4193 fprintf (dump_file, "Ignoring reg %u with equiv init insn\n", 4194 i); 4195 continue; 4196 } 4197 if (!rtx_moveable_p (&PATTERN (def_insn), OP_IN)) 4198 { 4199 if (dump_file) 4200 fprintf (dump_file, "Found def insn %d for %d to be not moveable\n", 4201 INSN_UID (def_insn), i); 4202 continue; 4203 } 4204 if (dump_file) 4205 fprintf (dump_file, "Examining insn %d, def for %d\n", 4206 INSN_UID (def_insn), i); 4207 while (*def_insn_use_rec != NULL) 4208 { 4209 df_ref use = *def_insn_use_rec; 4210 unsigned regno = DF_REF_REGNO (use); 4211 if (bitmap_bit_p (&unusable_as_input, regno)) 4212 { 4213 all_ok = false; 4214 if (dump_file) 4215 fprintf (dump_file, " found unusable input reg %u.\n", regno); 4216 break; 4217 } 4218 if (!bitmap_bit_p (def_bb_transp, regno)) 4219 { 4220 if (bitmap_bit_p (def_bb_moveable, regno) 4221 && !control_flow_insn_p (use_insn) 4222 #ifdef HAVE_cc0 4223 && !sets_cc0_p (use_insn) 4224 #endif 4225 ) 4226 { 4227 if (modified_between_p (DF_REF_REG (use), def_insn, use_insn)) 4228 { 4229 rtx x = NEXT_INSN (def_insn); 4230 while (!modified_in_p (DF_REF_REG (use), x)) 4231 { 4232 gcc_assert (x != use_insn); 4233 x = NEXT_INSN (x); 4234 } 4235 if (dump_file) 4236 fprintf (dump_file, " input reg %u modified but insn %d moveable\n", 4237 regno, INSN_UID (x)); 4238 emit_insn_after (PATTERN (x), use_insn); 4239 set_insn_deleted (x); 4240 } 4241 else 4242 { 4243 if (dump_file) 4244 fprintf (dump_file, " input reg %u modified between def and use\n", 4245 regno); 4246 all_transp = false; 4247 } 4248 } 4249 else 4250 all_transp = false; 4251 } 4252 4253 def_insn_use_rec++; 4254 } 4255 if (!all_ok) 4256 continue; 4257 if (!dbg_cnt (ira_move)) 4258 break; 4259 if (dump_file) 4260 fprintf (dump_file, " all ok%s\n", all_transp ? " and transp" : ""); 4261 4262 if (all_transp) 4263 { 4264 rtx def_reg = DF_REF_REG (def); 4265 rtx newreg = ira_create_new_reg (def_reg); 4266 if (validate_change (def_insn, DF_REF_LOC (def), newreg, 0)) 4267 { 4268 unsigned nregno = REGNO (newreg); 4269 emit_insn_before (gen_move_insn (def_reg, newreg), use_insn); 4270 nregno -= max_regs; 4271 pseudo_replaced_reg[nregno] = def_reg; 4272 } 4273 } 4274 } 4275 4276 FOR_EACH_BB (bb) 4277 { 4278 bitmap_clear (bb_local + bb->index); 4279 bitmap_clear (bb_transp_live + bb->index); 4280 bitmap_clear (bb_moveable_reg_sets + bb->index); 4281 } 4282 bitmap_clear (&interesting); 4283 bitmap_clear (&unusable_as_input); 4284 free (uid_luid); 4285 free (closest_uses); 4286 free (bb_local); 4287 free (bb_transp_live); 4288 free (bb_moveable_reg_sets); 4289 4290 last_moveable_pseudo = max_reg_num (); 4291 4292 fix_reg_equiv_init (); 4293 expand_reg_info (); 4294 regstat_free_n_sets_and_refs (); 4295 regstat_free_ri (); 4296 regstat_init_n_sets_and_refs (); 4297 regstat_compute_ri (); 4298 free_dominance_info (CDI_DOMINATORS); 4299 } 4300 4301 /* Perform the second half of the transformation started in 4302 find_moveable_pseudos. We look for instances where the newly introduced 4303 pseudo remains unallocated, and remove it by moving the definition to 4304 just before its use, replacing the move instruction generated by 4305 find_moveable_pseudos. */ 4306 static void 4307 move_unallocated_pseudos (void) 4308 { 4309 int i; 4310 for (i = first_moveable_pseudo; i < last_moveable_pseudo; i++) 4311 if (reg_renumber[i] < 0) 4312 { 4313 int idx = i - first_moveable_pseudo; 4314 rtx other_reg = pseudo_replaced_reg[idx]; 4315 rtx def_insn = DF_REF_INSN (DF_REG_DEF_CHAIN (i)); 4316 /* The use must follow all definitions of OTHER_REG, so we can 4317 insert the new definition immediately after any of them. */ 4318 df_ref other_def = DF_REG_DEF_CHAIN (REGNO (other_reg)); 4319 rtx move_insn = DF_REF_INSN (other_def); 4320 rtx newinsn = emit_insn_after (PATTERN (def_insn), move_insn); 4321 rtx set; 4322 int success; 4323 4324 if (dump_file) 4325 fprintf (dump_file, "moving def of %d (insn %d now) ", 4326 REGNO (other_reg), INSN_UID (def_insn)); 4327 4328 delete_insn (move_insn); 4329 while ((other_def = DF_REG_DEF_CHAIN (REGNO (other_reg)))) 4330 delete_insn (DF_REF_INSN (other_def)); 4331 delete_insn (def_insn); 4332 4333 set = single_set (newinsn); 4334 success = validate_change (newinsn, &SET_DEST (set), other_reg, 0); 4335 gcc_assert (success); 4336 if (dump_file) 4337 fprintf (dump_file, " %d) rather than keep unallocated replacement %d\n", 4338 INSN_UID (newinsn), i); 4339 SET_REG_N_REFS (i, 0); 4340 } 4341 } 4342 4343 /* If the backend knows where to allocate pseudos for hard 4344 register initial values, register these allocations now. */ 4345 static void 4346 allocate_initial_values (void) 4347 { 4348 if (targetm.allocate_initial_value) 4349 { 4350 rtx hreg, preg, x; 4351 int i, regno; 4352 4353 for (i = 0; HARD_REGISTER_NUM_P (i); i++) 4354 { 4355 if (! initial_value_entry (i, &hreg, &preg)) 4356 break; 4357 4358 x = targetm.allocate_initial_value (hreg); 4359 regno = REGNO (preg); 4360 if (x && REG_N_SETS (regno) <= 1) 4361 { 4362 if (MEM_P (x)) 4363 reg_equiv_memory_loc (regno) = x; 4364 else 4365 { 4366 basic_block bb; 4367 int new_regno; 4368 4369 gcc_assert (REG_P (x)); 4370 new_regno = REGNO (x); 4371 reg_renumber[regno] = new_regno; 4372 /* Poke the regno right into regno_reg_rtx so that even 4373 fixed regs are accepted. */ 4374 SET_REGNO (preg, new_regno); 4375 /* Update global register liveness information. */ 4376 FOR_EACH_BB (bb) 4377 { 4378 if (REGNO_REG_SET_P(df_get_live_in (bb), regno)) 4379 SET_REGNO_REG_SET (df_get_live_in (bb), new_regno); 4380 if (REGNO_REG_SET_P(df_get_live_out (bb), regno)) 4381 SET_REGNO_REG_SET (df_get_live_out (bb), new_regno); 4382 } 4383 } 4384 } 4385 } 4386 4387 gcc_checking_assert (! initial_value_entry (FIRST_PSEUDO_REGISTER, 4388 &hreg, &preg)); 4389 } 4390 } 4391 4392 4393 /* True when we use LRA instead of reload pass for the current 4394 function. */ 4395 bool ira_use_lra_p; 4396 4397 /* True if we have allocno conflicts. It is false for non-optimized 4398 mode or when the conflict table is too big. */ 4399 bool ira_conflicts_p; 4400 4401 /* Saved between IRA and reload. */ 4402 static int saved_flag_ira_share_spill_slots; 4403 4404 /* This is the main entry of IRA. */ 4405 static void 4406 ira (FILE *f) 4407 { 4408 bool loops_p; 4409 int ira_max_point_before_emit; 4410 int rebuild_p; 4411 bool saved_flag_caller_saves = flag_caller_saves; 4412 enum ira_region saved_flag_ira_region = flag_ira_region; 4413 4414 ira_conflicts_p = optimize > 0; 4415 4416 ira_use_lra_p = targetm.lra_p (); 4417 /* If there are too many pseudos and/or basic blocks (e.g. 10K 4418 pseudos and 10K blocks or 100K pseudos and 1K blocks), we will 4419 use simplified and faster algorithms in LRA. */ 4420 lra_simple_p 4421 = (ira_use_lra_p && max_reg_num () >= (1 << 26) / last_basic_block); 4422 if (lra_simple_p) 4423 { 4424 /* It permits to skip live range splitting in LRA. */ 4425 flag_caller_saves = false; 4426 /* There is no sense to do regional allocation when we use 4427 simplified LRA. */ 4428 flag_ira_region = IRA_REGION_ONE; 4429 ira_conflicts_p = false; 4430 } 4431 4432 #ifndef IRA_NO_OBSTACK 4433 gcc_obstack_init (&ira_obstack); 4434 #endif 4435 bitmap_obstack_initialize (&ira_bitmap_obstack); 4436 4437 if (flag_caller_saves) 4438 init_caller_save (); 4439 4440 if (flag_ira_verbose < 10) 4441 { 4442 internal_flag_ira_verbose = flag_ira_verbose; 4443 ira_dump_file = f; 4444 } 4445 else 4446 { 4447 internal_flag_ira_verbose = flag_ira_verbose - 10; 4448 ira_dump_file = stderr; 4449 } 4450 4451 setup_prohibited_mode_move_regs (); 4452 4453 df_note_add_problem (); 4454 4455 /* DF_LIVE can't be used in the register allocator, too many other 4456 parts of the compiler depend on using the "classic" liveness 4457 interpretation of the DF_LR problem. See PR38711. 4458 Remove the problem, so that we don't spend time updating it in 4459 any of the df_analyze() calls during IRA/LRA. */ 4460 if (optimize > 1) 4461 df_remove_problem (df_live); 4462 gcc_checking_assert (df_live == NULL); 4463 4464 #ifdef ENABLE_CHECKING 4465 df->changeable_flags |= DF_VERIFY_SCHEDULED; 4466 #endif 4467 df_analyze (); 4468 df_clear_flags (DF_NO_INSN_RESCAN); 4469 regstat_init_n_sets_and_refs (); 4470 regstat_compute_ri (); 4471 4472 /* If we are not optimizing, then this is the only place before 4473 register allocation where dataflow is done. And that is needed 4474 to generate these warnings. */ 4475 if (warn_clobbered) 4476 generate_setjmp_warnings (); 4477 4478 /* Determine if the current function is a leaf before running IRA 4479 since this can impact optimizations done by the prologue and 4480 epilogue thus changing register elimination offsets. */ 4481 crtl->is_leaf = leaf_function_p (); 4482 4483 if (resize_reg_info () && flag_ira_loop_pressure) 4484 ira_set_pseudo_classes (true, ira_dump_file); 4485 4486 init_reg_equiv (); 4487 rebuild_p = update_equiv_regs (); 4488 setup_reg_equiv (); 4489 setup_reg_equiv_init (); 4490 4491 if (optimize && rebuild_p) 4492 { 4493 timevar_push (TV_JUMP); 4494 rebuild_jump_labels (get_insns ()); 4495 if (purge_all_dead_edges ()) 4496 delete_unreachable_blocks (); 4497 timevar_pop (TV_JUMP); 4498 } 4499 4500 allocated_reg_info_size = max_reg_num (); 4501 4502 if (delete_trivially_dead_insns (get_insns (), max_reg_num ())) 4503 df_analyze (); 4504 4505 /* It is not worth to do such improvement when we use a simple 4506 allocation because of -O0 usage or because the function is too 4507 big. */ 4508 if (ira_conflicts_p) 4509 find_moveable_pseudos (); 4510 4511 max_regno_before_ira = max_reg_num (); 4512 ira_setup_eliminable_regset (true); 4513 4514 ira_overall_cost = ira_reg_cost = ira_mem_cost = 0; 4515 ira_load_cost = ira_store_cost = ira_shuffle_cost = 0; 4516 ira_move_loops_num = ira_additional_jumps_num = 0; 4517 4518 ira_assert (current_loops == NULL); 4519 if (flag_ira_region == IRA_REGION_ALL || flag_ira_region == IRA_REGION_MIXED) 4520 loop_optimizer_init (AVOID_CFG_MODIFICATIONS | LOOPS_HAVE_RECORDED_EXITS); 4521 4522 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL) 4523 fprintf (ira_dump_file, "Building IRA IR\n"); 4524 loops_p = ira_build (); 4525 4526 ira_assert (ira_conflicts_p || !loops_p); 4527 4528 saved_flag_ira_share_spill_slots = flag_ira_share_spill_slots; 4529 if (too_high_register_pressure_p () || cfun->calls_setjmp) 4530 /* It is just wasting compiler's time to pack spilled pseudos into 4531 stack slots in this case -- prohibit it. We also do this if 4532 there is setjmp call because a variable not modified between 4533 setjmp and longjmp the compiler is required to preserve its 4534 value and sharing slots does not guarantee it. */ 4535 flag_ira_share_spill_slots = FALSE; 4536 4537 ira_color (); 4538 4539 ira_max_point_before_emit = ira_max_point; 4540 4541 ira_initiate_emit_data (); 4542 4543 ira_emit (loops_p); 4544 4545 max_regno = max_reg_num (); 4546 if (ira_conflicts_p) 4547 { 4548 if (! loops_p) 4549 { 4550 if (! ira_use_lra_p) 4551 ira_initiate_assign (); 4552 } 4553 else 4554 { 4555 expand_reg_info (); 4556 4557 if (ira_use_lra_p) 4558 { 4559 ira_allocno_t a; 4560 ira_allocno_iterator ai; 4561 4562 FOR_EACH_ALLOCNO (a, ai) 4563 ALLOCNO_REGNO (a) = REGNO (ALLOCNO_EMIT_DATA (a)->reg); 4564 } 4565 else 4566 { 4567 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL) 4568 fprintf (ira_dump_file, "Flattening IR\n"); 4569 ira_flattening (max_regno_before_ira, ira_max_point_before_emit); 4570 } 4571 /* New insns were generated: add notes and recalculate live 4572 info. */ 4573 df_analyze (); 4574 4575 /* ??? Rebuild the loop tree, but why? Does the loop tree 4576 change if new insns were generated? Can that be handled 4577 by updating the loop tree incrementally? */ 4578 loop_optimizer_finalize (); 4579 free_dominance_info (CDI_DOMINATORS); 4580 loop_optimizer_init (AVOID_CFG_MODIFICATIONS 4581 | LOOPS_HAVE_RECORDED_EXITS); 4582 4583 if (! ira_use_lra_p) 4584 { 4585 setup_allocno_assignment_flags (); 4586 ira_initiate_assign (); 4587 ira_reassign_conflict_allocnos (max_regno); 4588 } 4589 } 4590 } 4591 4592 ira_finish_emit_data (); 4593 4594 setup_reg_renumber (); 4595 4596 calculate_allocation_cost (); 4597 4598 #ifdef ENABLE_IRA_CHECKING 4599 if (ira_conflicts_p) 4600 check_allocation (); 4601 #endif 4602 4603 if (max_regno != max_regno_before_ira) 4604 { 4605 regstat_free_n_sets_and_refs (); 4606 regstat_free_ri (); 4607 regstat_init_n_sets_and_refs (); 4608 regstat_compute_ri (); 4609 } 4610 4611 overall_cost_before = ira_overall_cost; 4612 if (! ira_conflicts_p) 4613 grow_reg_equivs (); 4614 else 4615 { 4616 fix_reg_equiv_init (); 4617 4618 #ifdef ENABLE_IRA_CHECKING 4619 print_redundant_copies (); 4620 #endif 4621 4622 ira_spilled_reg_stack_slots_num = 0; 4623 ira_spilled_reg_stack_slots 4624 = ((struct ira_spilled_reg_stack_slot *) 4625 ira_allocate (max_regno 4626 * sizeof (struct ira_spilled_reg_stack_slot))); 4627 memset (ira_spilled_reg_stack_slots, 0, 4628 max_regno * sizeof (struct ira_spilled_reg_stack_slot)); 4629 } 4630 allocate_initial_values (); 4631 4632 /* See comment for find_moveable_pseudos call. */ 4633 if (ira_conflicts_p) 4634 move_unallocated_pseudos (); 4635 4636 /* Restore original values. */ 4637 if (lra_simple_p) 4638 { 4639 flag_caller_saves = saved_flag_caller_saves; 4640 flag_ira_region = saved_flag_ira_region; 4641 } 4642 } 4643 4644 static void 4645 do_reload (void) 4646 { 4647 basic_block bb; 4648 bool need_dce; 4649 4650 if (flag_ira_verbose < 10) 4651 ira_dump_file = dump_file; 4652 4653 timevar_push (TV_RELOAD); 4654 if (ira_use_lra_p) 4655 { 4656 if (current_loops != NULL) 4657 { 4658 loop_optimizer_finalize (); 4659 free_dominance_info (CDI_DOMINATORS); 4660 } 4661 FOR_ALL_BB (bb) 4662 bb->loop_father = NULL; 4663 current_loops = NULL; 4664 4665 if (ira_conflicts_p) 4666 ira_free (ira_spilled_reg_stack_slots); 4667 4668 ira_destroy (); 4669 4670 lra (ira_dump_file); 4671 /* ???!!! Move it before lra () when we use ira_reg_equiv in 4672 LRA. */ 4673 vec_free (reg_equivs); 4674 reg_equivs = NULL; 4675 need_dce = false; 4676 } 4677 else 4678 { 4679 df_set_flags (DF_NO_INSN_RESCAN); 4680 build_insn_chain (); 4681 4682 need_dce = reload (get_insns (), ira_conflicts_p); 4683 4684 } 4685 4686 timevar_pop (TV_RELOAD); 4687 4688 timevar_push (TV_IRA); 4689 4690 if (ira_conflicts_p && ! ira_use_lra_p) 4691 { 4692 ira_free (ira_spilled_reg_stack_slots); 4693 ira_finish_assign (); 4694 } 4695 4696 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL 4697 && overall_cost_before != ira_overall_cost) 4698 fprintf (ira_dump_file, "+++Overall after reload %d\n", ira_overall_cost); 4699 4700 flag_ira_share_spill_slots = saved_flag_ira_share_spill_slots; 4701 4702 if (! ira_use_lra_p) 4703 { 4704 ira_destroy (); 4705 if (current_loops != NULL) 4706 { 4707 loop_optimizer_finalize (); 4708 free_dominance_info (CDI_DOMINATORS); 4709 } 4710 FOR_ALL_BB (bb) 4711 bb->loop_father = NULL; 4712 current_loops = NULL; 4713 4714 regstat_free_ri (); 4715 regstat_free_n_sets_and_refs (); 4716 } 4717 4718 if (optimize) 4719 cleanup_cfg (CLEANUP_EXPENSIVE); 4720 4721 finish_reg_equiv (); 4722 4723 bitmap_obstack_release (&ira_bitmap_obstack); 4724 #ifndef IRA_NO_OBSTACK 4725 obstack_free (&ira_obstack, NULL); 4726 #endif 4727 4728 /* The code after the reload has changed so much that at this point 4729 we might as well just rescan everything. Note that 4730 df_rescan_all_insns is not going to help here because it does not 4731 touch the artificial uses and defs. */ 4732 df_finish_pass (true); 4733 df_scan_alloc (NULL); 4734 df_scan_blocks (); 4735 4736 if (optimize > 1) 4737 { 4738 df_live_add_problem (); 4739 df_live_set_all_dirty (); 4740 } 4741 4742 if (optimize) 4743 df_analyze (); 4744 4745 if (need_dce && optimize) 4746 run_fast_dce (); 4747 4748 /* Diagnose uses of the hard frame pointer when it is used as a global 4749 register. Often we can get away with letting the user appropriate 4750 the frame pointer, but we should let them know when code generation 4751 makes that impossible. */ 4752 if (global_regs[HARD_FRAME_POINTER_REGNUM] && frame_pointer_needed) 4753 { 4754 tree decl = global_regs_decl[HARD_FRAME_POINTER_REGNUM]; 4755 error_at (DECL_SOURCE_LOCATION (current_function_decl), 4756 "frame pointer required, but reserved"); 4757 inform (DECL_SOURCE_LOCATION (decl), "for %qD", decl); 4758 } 4759 4760 timevar_pop (TV_IRA); 4761 } 4762 4763 /* Run the integrated register allocator. */ 4764 static unsigned int 4765 rest_of_handle_ira (void) 4766 { 4767 ira (dump_file); 4768 return 0; 4769 } 4770 4771 struct rtl_opt_pass pass_ira = 4772 { 4773 { 4774 RTL_PASS, 4775 "ira", /* name */ 4776 OPTGROUP_NONE, /* optinfo_flags */ 4777 NULL, /* gate */ 4778 rest_of_handle_ira, /* execute */ 4779 NULL, /* sub */ 4780 NULL, /* next */ 4781 0, /* static_pass_number */ 4782 TV_IRA, /* tv_id */ 4783 0, /* properties_required */ 4784 0, /* properties_provided */ 4785 0, /* properties_destroyed */ 4786 0, /* todo_flags_start */ 4787 0, /* todo_flags_finish */ 4788 } 4789 }; 4790 4791 static unsigned int 4792 rest_of_handle_reload (void) 4793 { 4794 do_reload (); 4795 return 0; 4796 } 4797 4798 struct rtl_opt_pass pass_reload = 4799 { 4800 { 4801 RTL_PASS, 4802 "reload", /* name */ 4803 OPTGROUP_NONE, /* optinfo_flags */ 4804 NULL, /* gate */ 4805 rest_of_handle_reload, /* execute */ 4806 NULL, /* sub */ 4807 NULL, /* next */ 4808 0, /* static_pass_number */ 4809 TV_RELOAD, /* tv_id */ 4810 0, /* properties_required */ 4811 0, /* properties_provided */ 4812 0, /* properties_destroyed */ 4813 0, /* todo_flags_start */ 4814 TODO_ggc_collect /* todo_flags_finish */ 4815 } 4816 }; 4817