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