1 /* LRA (local register allocator) driver and LRA utilities. 2 Copyright (C) 2010-2013 Free Software Foundation, Inc. 3 Contributed by Vladimir Makarov <vmakarov@redhat.com>. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 3, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 22 /* The Local Register Allocator (LRA) is a replacement of former 23 reload pass. It is focused to simplify code solving the reload 24 pass tasks, to make the code maintenance easier, and to implement new 25 perspective optimizations. 26 27 The major LRA design solutions are: 28 o division small manageable, separated sub-tasks 29 o reflection of all transformations and decisions in RTL as more 30 as possible 31 o insn constraints as a primary source of the info (minimizing 32 number of target-depended macros/hooks) 33 34 In brief LRA works by iterative insn process with the final goal is 35 to satisfy all insn and address constraints: 36 o New reload insns (in brief reloads) and reload pseudos might be 37 generated; 38 o Some pseudos might be spilled to assign hard registers to 39 new reload pseudos; 40 o Changing spilled pseudos to stack memory or their equivalences; 41 o Allocation stack memory changes the address displacement and 42 new iteration is needed. 43 44 Here is block diagram of LRA passes: 45 46 --------------------- 47 | Undo inheritance | --------------- --------------- 48 | for spilled pseudos)| | Memory-memory | | New (and old) | 49 | and splits (for |<----| move coalesce |<-----| pseudos | 50 | pseudos got the | --------------- | assignment | 51 Start | same hard regs) | --------------- 52 | --------------------- ^ 53 V | ---------------- | 54 ----------- V | Update virtual | | 55 | Remove |----> ------------>| register | | 56 | scratches | ^ | displacements | | 57 ----------- | ---------------- | 58 | | | 59 | V New | 60 ---------------- No ------------ pseudos ------------------- 61 | Spilled pseudo | change |Constraints:| or insns | Inheritance/split | 62 | to memory |<-------| RTL |--------->| transformations | 63 | substitution | | transfor- | | in EBB scope | 64 ---------------- | mations | ------------------- 65 | ------------ 66 V 67 ------------------------- 68 | Hard regs substitution, | 69 | devirtalization, and |------> Finish 70 | restoring scratches got | 71 | memory | 72 ------------------------- 73 74 To speed up the process: 75 o We process only insns affected by changes on previous 76 iterations; 77 o We don't use DFA-infrastructure because it results in much slower 78 compiler speed than a special IR described below does; 79 o We use a special insn representation for quick access to insn 80 info which is always *synchronized* with the current RTL; 81 o Insn IR is minimized by memory. It is divided on three parts: 82 o one specific for each insn in RTL (only operand locations); 83 o one common for all insns in RTL with the same insn code 84 (different operand attributes from machine descriptions); 85 o one oriented for maintenance of live info (list of pseudos). 86 o Pseudo data: 87 o all insns where the pseudo is referenced; 88 o live info (conflicting hard regs, live ranges, # of 89 references etc); 90 o data used for assigning (preferred hard regs, costs etc). 91 92 This file contains LRA driver, LRA utility functions and data, and 93 code for dealing with scratches. */ 94 95 #include "config.h" 96 #include "system.h" 97 #include "coretypes.h" 98 #include "tm.h" 99 #include "hard-reg-set.h" 100 #include "rtl.h" 101 #include "tm_p.h" 102 #include "regs.h" 103 #include "insn-config.h" 104 #include "insn-codes.h" 105 #include "recog.h" 106 #include "output.h" 107 #include "addresses.h" 108 #include "flags.h" 109 #include "function.h" 110 #include "expr.h" 111 #include "basic-block.h" 112 #include "except.h" 113 #include "tree-pass.h" 114 #include "timevar.h" 115 #include "target.h" 116 #include "vec.h" 117 #include "ira.h" 118 #include "lra-int.h" 119 #include "df.h" 120 121 /* Hard registers currently not available for allocation. It can 122 changed after some hard registers become not eliminable. */ 123 HARD_REG_SET lra_no_alloc_regs; 124 125 static int get_new_reg_value (void); 126 static void expand_reg_info (void); 127 static void invalidate_insn_recog_data (int); 128 static int get_insn_freq (rtx); 129 static void invalidate_insn_data_regno_info (lra_insn_recog_data_t, rtx, int); 130 131 /* Expand all regno related info needed for LRA. */ 132 static void 133 expand_reg_data (void) 134 { 135 resize_reg_info (); 136 expand_reg_info (); 137 ira_expand_reg_equiv (); 138 } 139 140 /* Create and return a new reg of ORIGINAL mode. If ORIGINAL is NULL 141 or of VOIDmode, use MD_MODE for the new reg. Initialize its 142 register class to RCLASS. Print message about assigning class 143 RCLASS containing new register name TITLE unless it is NULL. Use 144 attributes of ORIGINAL if it is a register. The created register 145 will have unique held value. */ 146 rtx 147 lra_create_new_reg_with_unique_value (enum machine_mode md_mode, rtx original, 148 enum reg_class rclass, const char *title) 149 { 150 enum machine_mode mode; 151 rtx new_reg; 152 153 if (original == NULL_RTX || (mode = GET_MODE (original)) == VOIDmode) 154 mode = md_mode; 155 lra_assert (mode != VOIDmode); 156 new_reg = gen_reg_rtx (mode); 157 if (original == NULL_RTX || ! REG_P (original)) 158 { 159 if (lra_dump_file != NULL) 160 fprintf (lra_dump_file, " Creating newreg=%i", REGNO (new_reg)); 161 } 162 else 163 { 164 if (ORIGINAL_REGNO (original) >= FIRST_PSEUDO_REGISTER) 165 ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original); 166 REG_USERVAR_P (new_reg) = REG_USERVAR_P (original); 167 REG_POINTER (new_reg) = REG_POINTER (original); 168 REG_ATTRS (new_reg) = REG_ATTRS (original); 169 if (lra_dump_file != NULL) 170 fprintf (lra_dump_file, " Creating newreg=%i from oldreg=%i", 171 REGNO (new_reg), REGNO (original)); 172 } 173 if (lra_dump_file != NULL) 174 { 175 if (title != NULL) 176 fprintf (lra_dump_file, ", assigning class %s to%s%s r%d", 177 reg_class_names[rclass], *title == '\0' ? "" : " ", 178 title, REGNO (new_reg)); 179 fprintf (lra_dump_file, "\n"); 180 } 181 expand_reg_data (); 182 setup_reg_classes (REGNO (new_reg), rclass, NO_REGS, rclass); 183 return new_reg; 184 } 185 186 /* Analogous to the previous function but also inherits value of 187 ORIGINAL. */ 188 rtx 189 lra_create_new_reg (enum machine_mode md_mode, rtx original, 190 enum reg_class rclass, const char *title) 191 { 192 rtx new_reg; 193 194 new_reg 195 = lra_create_new_reg_with_unique_value (md_mode, original, rclass, title); 196 if (original != NULL_RTX && REG_P (original)) 197 lra_reg_info[REGNO (new_reg)].val = lra_reg_info[REGNO (original)].val; 198 return new_reg; 199 } 200 201 /* Set up for REGNO unique hold value. */ 202 void 203 lra_set_regno_unique_value (int regno) 204 { 205 lra_reg_info[regno].val = get_new_reg_value (); 206 } 207 208 /* Invalidate INSN related info used by LRA. */ 209 void 210 lra_invalidate_insn_data (rtx insn) 211 { 212 lra_invalidate_insn_regno_info (insn); 213 invalidate_insn_recog_data (INSN_UID (insn)); 214 } 215 216 /* Mark INSN deleted and invalidate the insn related info used by 217 LRA. */ 218 void 219 lra_set_insn_deleted (rtx insn) 220 { 221 lra_invalidate_insn_data (insn); 222 SET_INSN_DELETED (insn); 223 } 224 225 /* Delete an unneeded INSN and any previous insns who sole purpose is 226 loading data that is dead in INSN. */ 227 void 228 lra_delete_dead_insn (rtx insn) 229 { 230 rtx prev = prev_real_insn (insn); 231 rtx prev_dest; 232 233 /* If the previous insn sets a register that dies in our insn, 234 delete it too. */ 235 if (prev && GET_CODE (PATTERN (prev)) == SET 236 && (prev_dest = SET_DEST (PATTERN (prev)), REG_P (prev_dest)) 237 && reg_mentioned_p (prev_dest, PATTERN (insn)) 238 && find_regno_note (insn, REG_DEAD, REGNO (prev_dest)) 239 && ! side_effects_p (SET_SRC (PATTERN (prev)))) 240 lra_delete_dead_insn (prev); 241 242 lra_set_insn_deleted (insn); 243 } 244 245 /* Target checks operands through operand predicates to recognize an 246 insn. We should have a special precaution to generate add insns 247 which are frequent results of elimination. 248 249 Emit insns for x = y + z. X can be used to store intermediate 250 values and should be not in Y and Z when we use X to store an 251 intermediate value. Y + Z should form [base] [+ index[ * scale]] [ 252 + disp] where base and index are registers, disp and scale are 253 constants. Y should contain base if it is present, Z should 254 contain disp if any. index[*scale] can be part of Y or Z. */ 255 void 256 lra_emit_add (rtx x, rtx y, rtx z) 257 { 258 int old; 259 rtx insn, last; 260 rtx a1, a2, base, index, disp, scale, index_scale; 261 bool ok_p; 262 263 insn = gen_add3_insn (x, y, z); 264 old = max_reg_num (); 265 if (insn != NULL_RTX) 266 emit_insn (insn); 267 else 268 { 269 disp = a2 = NULL_RTX; 270 if (GET_CODE (y) == PLUS) 271 { 272 a1 = XEXP (y, 0); 273 a2 = XEXP (y, 1); 274 disp = z; 275 } 276 else 277 { 278 a1 = y; 279 if (CONSTANT_P (z)) 280 disp = z; 281 else 282 a2 = z; 283 } 284 index_scale = scale = NULL_RTX; 285 if (GET_CODE (a1) == MULT) 286 { 287 index_scale = a1; 288 index = XEXP (a1, 0); 289 scale = XEXP (a1, 1); 290 base = a2; 291 } 292 else if (a2 != NULL_RTX && GET_CODE (a2) == MULT) 293 { 294 index_scale = a2; 295 index = XEXP (a2, 0); 296 scale = XEXP (a2, 1); 297 base = a1; 298 } 299 else 300 { 301 base = a1; 302 index = a2; 303 } 304 if (! REG_P (base) 305 || (index != NULL_RTX && ! REG_P (index)) 306 || (disp != NULL_RTX && ! CONSTANT_P (disp)) 307 || (scale != NULL_RTX && ! CONSTANT_P (scale))) 308 { 309 /* Its is not an address generation. Probably we have no 3 op 310 add. Last chance is to use 2-op add insn. */ 311 lra_assert (x != y && x != z); 312 emit_move_insn (x, z); 313 insn = gen_add2_insn (x, y); 314 emit_insn (insn); 315 } 316 else 317 { 318 if (index_scale == NULL_RTX) 319 index_scale = index; 320 if (disp == NULL_RTX) 321 { 322 /* Generate x = index_scale; x = x + base. */ 323 lra_assert (index_scale != NULL_RTX && base != NULL_RTX); 324 emit_move_insn (x, index_scale); 325 insn = gen_add2_insn (x, base); 326 emit_insn (insn); 327 } 328 else if (scale == NULL_RTX) 329 { 330 /* Try x = base + disp. */ 331 lra_assert (base != NULL_RTX); 332 last = get_last_insn (); 333 insn = emit_move_insn (x, gen_rtx_PLUS (GET_MODE (base), 334 base, disp)); 335 if (recog_memoized (insn) < 0) 336 { 337 delete_insns_since (last); 338 /* Generate x = disp; x = x + base. */ 339 emit_move_insn (x, disp); 340 insn = gen_add2_insn (x, base); 341 emit_insn (insn); 342 } 343 /* Generate x = x + index. */ 344 if (index != NULL_RTX) 345 { 346 insn = gen_add2_insn (x, index); 347 emit_insn (insn); 348 } 349 } 350 else 351 { 352 /* Try x = index_scale; x = x + disp; x = x + base. */ 353 last = get_last_insn (); 354 insn = emit_move_insn (x, index_scale); 355 ok_p = false; 356 if (recog_memoized (insn) >= 0) 357 { 358 insn = gen_add2_insn (x, disp); 359 if (insn != NULL_RTX) 360 { 361 emit_insn (insn); 362 insn = gen_add2_insn (x, disp); 363 if (insn != NULL_RTX) 364 { 365 emit_insn (insn); 366 ok_p = true; 367 } 368 } 369 } 370 if (! ok_p) 371 { 372 delete_insns_since (last); 373 /* Generate x = disp; x = x + base; x = x + index_scale. */ 374 emit_move_insn (x, disp); 375 insn = gen_add2_insn (x, base); 376 emit_insn (insn); 377 insn = gen_add2_insn (x, index_scale); 378 emit_insn (insn); 379 } 380 } 381 } 382 } 383 /* Functions emit_... can create pseudos -- so expand the pseudo 384 data. */ 385 if (old != max_reg_num ()) 386 expand_reg_data (); 387 } 388 389 /* The number of emitted reload insns so far. */ 390 int lra_curr_reload_num; 391 392 /* Emit x := y, processing special case when y = u + v or y = u + v * 393 scale + w through emit_add (Y can be an address which is base + 394 index reg * scale + displacement in general case). X may be used 395 as intermediate result therefore it should be not in Y. */ 396 void 397 lra_emit_move (rtx x, rtx y) 398 { 399 int old; 400 401 if (GET_CODE (y) != PLUS) 402 { 403 if (rtx_equal_p (x, y)) 404 return; 405 old = max_reg_num (); 406 emit_move_insn (x, y); 407 if (REG_P (x)) 408 lra_reg_info[ORIGINAL_REGNO (x)].last_reload = ++lra_curr_reload_num; 409 /* Function emit_move can create pseudos -- so expand the pseudo 410 data. */ 411 if (old != max_reg_num ()) 412 expand_reg_data (); 413 return; 414 } 415 lra_emit_add (x, XEXP (y, 0), XEXP (y, 1)); 416 } 417 418 /* Update insn operands which are duplication of operands whose 419 numbers are in array of NOPS (with end marker -1). The insn is 420 represented by its LRA internal representation ID. */ 421 void 422 lra_update_dups (lra_insn_recog_data_t id, signed char *nops) 423 { 424 int i, j, nop; 425 struct lra_static_insn_data *static_id = id->insn_static_data; 426 427 for (i = 0; i < static_id->n_dups; i++) 428 for (j = 0; (nop = nops[j]) >= 0; j++) 429 if (static_id->dup_num[i] == nop) 430 *id->dup_loc[i] = *id->operand_loc[nop]; 431 } 432 433 434 435 /* This page contains code dealing with info about registers in the 436 insns. */ 437 438 /* Pools for insn reg info. */ 439 static alloc_pool insn_reg_pool; 440 441 /* Initiate pool for insn reg info. */ 442 static void 443 init_insn_regs (void) 444 { 445 insn_reg_pool 446 = create_alloc_pool ("insn regs", sizeof (struct lra_insn_reg), 100); 447 } 448 449 /* Create LRA insn related info about a reference to REGNO in INSN with 450 TYPE (in/out/inout), biggest reference mode MODE, flag that it is 451 reference through subreg (SUBREG_P), flag that is early clobbered 452 in the insn (EARLY_CLOBBER), and reference to the next insn reg 453 info (NEXT). */ 454 static struct lra_insn_reg * 455 new_insn_reg (rtx insn, int regno, enum op_type type, enum machine_mode mode, 456 bool subreg_p, bool early_clobber, struct lra_insn_reg *next) 457 { 458 struct lra_insn_reg *ir; 459 460 ir = (struct lra_insn_reg *) pool_alloc (insn_reg_pool); 461 ir->type = type; 462 ir->biggest_mode = mode; 463 if (GET_MODE_SIZE (mode) > GET_MODE_SIZE (lra_reg_info[regno].biggest_mode) 464 && NONDEBUG_INSN_P (insn)) 465 lra_reg_info[regno].biggest_mode = mode; 466 ir->subreg_p = subreg_p; 467 ir->early_clobber = early_clobber; 468 ir->regno = regno; 469 ir->next = next; 470 return ir; 471 } 472 473 /* Free insn reg info IR. */ 474 static void 475 free_insn_reg (struct lra_insn_reg *ir) 476 { 477 pool_free (insn_reg_pool, ir); 478 } 479 480 /* Free insn reg info list IR. */ 481 static void 482 free_insn_regs (struct lra_insn_reg *ir) 483 { 484 struct lra_insn_reg *next_ir; 485 486 for (; ir != NULL; ir = next_ir) 487 { 488 next_ir = ir->next; 489 free_insn_reg (ir); 490 } 491 } 492 493 /* Finish pool for insn reg info. */ 494 static void 495 finish_insn_regs (void) 496 { 497 free_alloc_pool (insn_reg_pool); 498 } 499 500 501 502 /* This page contains code dealing LRA insn info (or in other words 503 LRA internal insn representation). */ 504 505 struct target_lra_int default_target_lra_int; 506 #if SWITCHABLE_TARGET 507 struct target_lra_int *this_target_lra_int = &default_target_lra_int; 508 #endif 509 510 /* Map INSN_CODE -> the static insn data. This info is valid during 511 all translation unit. */ 512 struct lra_static_insn_data *insn_code_data[LAST_INSN_CODE]; 513 514 /* Debug insns are represented as a special insn with one input 515 operand which is RTL expression in var_location. */ 516 517 /* The following data are used as static insn operand data for all 518 debug insns. If structure lra_operand_data is changed, the 519 initializer should be changed too. */ 520 static struct lra_operand_data debug_operand_data = 521 { 522 NULL, /* alternative */ 523 VOIDmode, /* We are not interesting in the operand mode. */ 524 OP_IN, 525 0, 0, 0, 0 526 }; 527 528 /* The following data are used as static insn data for all debug 529 insns. If structure lra_static_insn_data is changed, the 530 initializer should be changed too. */ 531 static struct lra_static_insn_data debug_insn_static_data = 532 { 533 &debug_operand_data, 534 0, /* Duplication operands #. */ 535 -1, /* Commutative operand #. */ 536 1, /* Operands #. There is only one operand which is debug RTL 537 expression. */ 538 0, /* Duplications #. */ 539 0, /* Alternatives #. We are not interesting in alternatives 540 because we does not proceed debug_insns for reloads. */ 541 NULL, /* Hard registers referenced in machine description. */ 542 NULL /* Descriptions of operands in alternatives. */ 543 }; 544 545 /* Called once per compiler work to initialize some LRA data related 546 to insns. */ 547 static void 548 init_insn_code_data_once (void) 549 { 550 memset (insn_code_data, 0, sizeof (insn_code_data)); 551 memset (op_alt_data, 0, sizeof (op_alt_data)); 552 } 553 554 /* Called once per compiler work to finalize some LRA data related to 555 insns. */ 556 static void 557 finish_insn_code_data_once (void) 558 { 559 int i; 560 561 for (i = 0; i < LAST_INSN_CODE; i++) 562 { 563 if (insn_code_data[i] != NULL) 564 free (insn_code_data[i]); 565 if (op_alt_data[i] != NULL) 566 free (op_alt_data[i]); 567 } 568 } 569 570 /* Initialize LRA info about operands in insn alternatives. */ 571 static void 572 init_op_alt_data (void) 573 { 574 int i; 575 576 for (i = 0; i < LAST_INSN_CODE; i++) 577 if (op_alt_data[i] != NULL) 578 { 579 free (op_alt_data[i]); 580 op_alt_data[i] = NULL; 581 } 582 } 583 584 /* Return static insn data, allocate and setup if necessary. Although 585 dup_num is static data (it depends only on icode), to set it up we 586 need to extract insn first. So recog_data should be valid for 587 normal insn (ICODE >= 0) before the call. */ 588 static struct lra_static_insn_data * 589 get_static_insn_data (int icode, int nop, int ndup, int nalt) 590 { 591 struct lra_static_insn_data *data; 592 size_t n_bytes; 593 594 lra_assert (icode < LAST_INSN_CODE); 595 if (icode >= 0 && (data = insn_code_data[icode]) != NULL) 596 return data; 597 lra_assert (nop >= 0 && ndup >= 0 && nalt >= 0); 598 n_bytes = sizeof (struct lra_static_insn_data) 599 + sizeof (struct lra_operand_data) * nop 600 + sizeof (int) * ndup; 601 data = XNEWVAR (struct lra_static_insn_data, n_bytes); 602 data->n_operands = nop; 603 data->n_dups = ndup; 604 data->n_alternatives = nalt; 605 data->operand = ((struct lra_operand_data *) 606 ((char *) data + sizeof (struct lra_static_insn_data))); 607 data->dup_num = ((int *) ((char *) data->operand 608 + sizeof (struct lra_operand_data) * nop)); 609 if (icode >= 0) 610 { 611 int i; 612 613 insn_code_data[icode] = data; 614 for (i = 0; i < nop; i++) 615 { 616 data->operand[i].constraint 617 = insn_data[icode].operand[i].constraint; 618 data->operand[i].mode = insn_data[icode].operand[i].mode; 619 data->operand[i].strict_low = insn_data[icode].operand[i].strict_low; 620 data->operand[i].is_operator 621 = insn_data[icode].operand[i].is_operator; 622 data->operand[i].type 623 = (data->operand[i].constraint[0] == '=' ? OP_OUT 624 : data->operand[i].constraint[0] == '+' ? OP_INOUT 625 : OP_IN); 626 data->operand[i].is_address = false; 627 } 628 for (i = 0; i < ndup; i++) 629 data->dup_num[i] = recog_data.dup_num[i]; 630 } 631 return data; 632 } 633 634 /* The current length of the following array. */ 635 int lra_insn_recog_data_len; 636 637 /* Map INSN_UID -> the insn recog data (NULL if unknown). */ 638 lra_insn_recog_data_t *lra_insn_recog_data; 639 640 /* Initialize LRA data about insns. */ 641 static void 642 init_insn_recog_data (void) 643 { 644 lra_insn_recog_data_len = 0; 645 lra_insn_recog_data = NULL; 646 init_insn_regs (); 647 } 648 649 /* Expand, if necessary, LRA data about insns. */ 650 static void 651 check_and_expand_insn_recog_data (int index) 652 { 653 int i, old; 654 655 if (lra_insn_recog_data_len > index) 656 return; 657 old = lra_insn_recog_data_len; 658 lra_insn_recog_data_len = index * 3 / 2 + 1; 659 lra_insn_recog_data = XRESIZEVEC (lra_insn_recog_data_t, 660 lra_insn_recog_data, 661 lra_insn_recog_data_len); 662 for (i = old; i < lra_insn_recog_data_len; i++) 663 lra_insn_recog_data[i] = NULL; 664 } 665 666 /* Finish LRA DATA about insn. */ 667 static void 668 free_insn_recog_data (lra_insn_recog_data_t data) 669 { 670 if (data->operand_loc != NULL) 671 free (data->operand_loc); 672 if (data->dup_loc != NULL) 673 free (data->dup_loc); 674 if (data->arg_hard_regs != NULL) 675 free (data->arg_hard_regs); 676 if (HAVE_ATTR_enabled && data->alternative_enabled_p != NULL) 677 free (data->alternative_enabled_p); 678 if (data->icode < 0 && NONDEBUG_INSN_P (data->insn)) 679 { 680 if (data->insn_static_data->operand_alternative != NULL) 681 free (data->insn_static_data->operand_alternative); 682 free_insn_regs (data->insn_static_data->hard_regs); 683 free (data->insn_static_data); 684 } 685 free_insn_regs (data->regs); 686 data->regs = NULL; 687 free (data); 688 } 689 690 /* Finish LRA data about all insns. */ 691 static void 692 finish_insn_recog_data (void) 693 { 694 int i; 695 lra_insn_recog_data_t data; 696 697 for (i = 0; i < lra_insn_recog_data_len; i++) 698 if ((data = lra_insn_recog_data[i]) != NULL) 699 free_insn_recog_data (data); 700 finish_insn_regs (); 701 free (lra_insn_recog_data); 702 } 703 704 /* Setup info about operands in alternatives of LRA DATA of insn. */ 705 static void 706 setup_operand_alternative (lra_insn_recog_data_t data) 707 { 708 int i, nop, nalt; 709 int icode = data->icode; 710 struct lra_static_insn_data *static_data = data->insn_static_data; 711 712 if (icode >= 0 713 && (static_data->operand_alternative = op_alt_data[icode]) != NULL) 714 return; 715 static_data->commutative = -1; 716 nop = static_data->n_operands; 717 if (nop == 0) 718 { 719 static_data->operand_alternative = NULL; 720 return; 721 } 722 nalt = static_data->n_alternatives; 723 static_data->operand_alternative = XNEWVEC (struct operand_alternative, 724 nalt * nop); 725 memset (static_data->operand_alternative, 0, 726 nalt * nop * sizeof (struct operand_alternative)); 727 if (icode >= 0) 728 op_alt_data[icode] = static_data->operand_alternative; 729 for (i = 0; i < nop; i++) 730 { 731 int j; 732 struct operand_alternative *op_alt_start, *op_alt; 733 const char *p = static_data->operand[i].constraint; 734 735 static_data->operand[i].early_clobber = 0; 736 op_alt_start = &static_data->operand_alternative[i]; 737 738 for (j = 0; j < nalt; j++) 739 { 740 op_alt = op_alt_start + j * nop; 741 op_alt->cl = NO_REGS; 742 op_alt->constraint = p; 743 op_alt->matches = -1; 744 op_alt->matched = -1; 745 746 if (*p == '\0' || *p == ',') 747 { 748 op_alt->anything_ok = 1; 749 continue; 750 } 751 752 for (;;) 753 { 754 char c = *p; 755 if (c == '#') 756 do 757 c = *++p; 758 while (c != ',' && c != '\0'); 759 if (c == ',' || c == '\0') 760 { 761 p++; 762 break; 763 } 764 765 switch (c) 766 { 767 case '=': case '+': case '*': 768 case 'E': case 'F': case 'G': case 'H': 769 case 's': case 'i': case 'n': 770 case 'I': case 'J': case 'K': case 'L': 771 case 'M': case 'N': case 'O': case 'P': 772 /* These don't say anything we care about. */ 773 break; 774 775 case '%': 776 /* We currently only support one commutative pair of 777 operands. */ 778 if (static_data->commutative < 0) 779 static_data->commutative = i; 780 else 781 lra_assert (data->icode < 0); /* Asm */ 782 783 /* The last operand should not be marked 784 commutative. */ 785 lra_assert (i != nop - 1); 786 break; 787 788 case '?': 789 op_alt->reject += LRA_LOSER_COST_FACTOR; 790 break; 791 case '!': 792 op_alt->reject += LRA_MAX_REJECT; 793 break; 794 case '&': 795 op_alt->earlyclobber = 1; 796 static_data->operand[i].early_clobber = 1; 797 break; 798 799 case '0': case '1': case '2': case '3': case '4': 800 case '5': case '6': case '7': case '8': case '9': 801 { 802 char *end; 803 op_alt->matches = strtoul (p, &end, 10); 804 static_data->operand_alternative 805 [j * nop + op_alt->matches].matched = i; 806 p = end; 807 } 808 continue; 809 810 case TARGET_MEM_CONSTRAINT: 811 op_alt->memory_ok = 1; 812 break; 813 case '<': 814 op_alt->decmem_ok = 1; 815 break; 816 case '>': 817 op_alt->incmem_ok = 1; 818 break; 819 case 'V': 820 op_alt->nonoffmem_ok = 1; 821 break; 822 case 'o': 823 op_alt->offmem_ok = 1; 824 break; 825 case 'X': 826 op_alt->anything_ok = 1; 827 break; 828 829 case 'p': 830 static_data->operand[i].is_address = true; 831 op_alt->is_address = 1; 832 op_alt->cl = (reg_class_subunion[(int) op_alt->cl] 833 [(int) base_reg_class (VOIDmode, 834 ADDR_SPACE_GENERIC, 835 ADDRESS, SCRATCH)]); 836 break; 837 838 case 'g': 839 case 'r': 840 op_alt->cl = 841 reg_class_subunion[(int) op_alt->cl][(int) GENERAL_REGS]; 842 break; 843 844 default: 845 if (EXTRA_MEMORY_CONSTRAINT (c, p)) 846 { 847 op_alt->memory_ok = 1; 848 break; 849 } 850 if (EXTRA_ADDRESS_CONSTRAINT (c, p)) 851 { 852 static_data->operand[i].is_address = true; 853 op_alt->is_address = 1; 854 op_alt->cl 855 = (reg_class_subunion 856 [(int) op_alt->cl] 857 [(int) base_reg_class (VOIDmode, ADDR_SPACE_GENERIC, 858 ADDRESS, SCRATCH)]); 859 break; 860 } 861 862 op_alt->cl 863 = (reg_class_subunion 864 [(int) op_alt->cl] 865 [(int) 866 REG_CLASS_FROM_CONSTRAINT ((unsigned char) c, p)]); 867 break; 868 } 869 p += CONSTRAINT_LEN (c, p); 870 } 871 } 872 } 873 } 874 875 /* Recursively process X and collect info about registers, which are 876 not the insn operands, in X with TYPE (in/out/inout) and flag that 877 it is early clobbered in the insn (EARLY_CLOBBER) and add the info 878 to LIST. X is a part of insn given by DATA. Return the result 879 list. */ 880 static struct lra_insn_reg * 881 collect_non_operand_hard_regs (rtx *x, lra_insn_recog_data_t data, 882 struct lra_insn_reg *list, 883 enum op_type type, bool early_clobber) 884 { 885 int i, j, regno, last; 886 bool subreg_p; 887 enum machine_mode mode; 888 struct lra_insn_reg *curr; 889 rtx op = *x; 890 enum rtx_code code = GET_CODE (op); 891 const char *fmt = GET_RTX_FORMAT (code); 892 893 for (i = 0; i < data->insn_static_data->n_operands; i++) 894 if (x == data->operand_loc[i]) 895 /* It is an operand loc. Stop here. */ 896 return list; 897 for (i = 0; i < data->insn_static_data->n_dups; i++) 898 if (x == data->dup_loc[i]) 899 /* It is a dup loc. Stop here. */ 900 return list; 901 mode = GET_MODE (op); 902 subreg_p = false; 903 if (code == SUBREG) 904 { 905 op = SUBREG_REG (op); 906 code = GET_CODE (op); 907 if (GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (op))) 908 { 909 mode = GET_MODE (op); 910 if (GET_MODE_SIZE (mode) > REGMODE_NATURAL_SIZE (mode)) 911 subreg_p = true; 912 } 913 } 914 if (REG_P (op)) 915 { 916 if ((regno = REGNO (op)) >= FIRST_PSEUDO_REGISTER) 917 return list; 918 for (last = regno + hard_regno_nregs[regno][mode]; 919 regno < last; 920 regno++) 921 if (! TEST_HARD_REG_BIT (lra_no_alloc_regs, regno) 922 || TEST_HARD_REG_BIT (eliminable_regset, regno)) 923 { 924 for (curr = list; curr != NULL; curr = curr->next) 925 if (curr->regno == regno && curr->subreg_p == subreg_p 926 && curr->biggest_mode == mode) 927 { 928 if (curr->type != type) 929 curr->type = OP_INOUT; 930 if (curr->early_clobber != early_clobber) 931 curr->early_clobber = true; 932 break; 933 } 934 if (curr == NULL) 935 { 936 /* This is a new hard regno or the info can not be 937 integrated into the found structure. */ 938 #ifdef STACK_REGS 939 early_clobber 940 = (early_clobber 941 /* This clobber is to inform popping floating 942 point stack only. */ 943 && ! (FIRST_STACK_REG <= regno 944 && regno <= LAST_STACK_REG)); 945 #endif 946 list = new_insn_reg (data->insn, regno, type, mode, subreg_p, 947 early_clobber, list); 948 } 949 } 950 return list; 951 } 952 switch (code) 953 { 954 case SET: 955 list = collect_non_operand_hard_regs (&SET_DEST (op), data, 956 list, OP_OUT, false); 957 list = collect_non_operand_hard_regs (&SET_SRC (op), data, 958 list, OP_IN, false); 959 break; 960 case CLOBBER: 961 /* We treat clobber of non-operand hard registers as early 962 clobber (the behavior is expected from asm). */ 963 list = collect_non_operand_hard_regs (&XEXP (op, 0), data, 964 list, OP_OUT, true); 965 break; 966 case PRE_INC: case PRE_DEC: case POST_INC: case POST_DEC: 967 list = collect_non_operand_hard_regs (&XEXP (op, 0), data, 968 list, OP_INOUT, false); 969 break; 970 case PRE_MODIFY: case POST_MODIFY: 971 list = collect_non_operand_hard_regs (&XEXP (op, 0), data, 972 list, OP_INOUT, false); 973 list = collect_non_operand_hard_regs (&XEXP (op, 1), data, 974 list, OP_IN, false); 975 break; 976 default: 977 fmt = GET_RTX_FORMAT (code); 978 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 979 { 980 if (fmt[i] == 'e') 981 list = collect_non_operand_hard_regs (&XEXP (op, i), data, 982 list, OP_IN, false); 983 else if (fmt[i] == 'E') 984 for (j = XVECLEN (op, i) - 1; j >= 0; j--) 985 list = collect_non_operand_hard_regs (&XVECEXP (op, i, j), data, 986 list, OP_IN, false); 987 } 988 } 989 return list; 990 } 991 992 /* Set up and return info about INSN. Set up the info if it is not set up 993 yet. */ 994 lra_insn_recog_data_t 995 lra_set_insn_recog_data (rtx insn) 996 { 997 lra_insn_recog_data_t data; 998 int i, n, icode; 999 rtx **locs; 1000 unsigned int uid = INSN_UID (insn); 1001 struct lra_static_insn_data *insn_static_data; 1002 1003 check_and_expand_insn_recog_data (uid); 1004 if (DEBUG_INSN_P (insn)) 1005 icode = -1; 1006 else 1007 { 1008 icode = INSN_CODE (insn); 1009 if (icode < 0) 1010 /* It might be a new simple insn which is not recognized yet. */ 1011 INSN_CODE (insn) = icode = recog_memoized (insn); 1012 } 1013 data = XNEW (struct lra_insn_recog_data); 1014 lra_insn_recog_data[uid] = data; 1015 data->insn = insn; 1016 data->used_insn_alternative = -1; 1017 data->icode = icode; 1018 data->regs = NULL; 1019 if (DEBUG_INSN_P (insn)) 1020 { 1021 data->insn_static_data = &debug_insn_static_data; 1022 data->dup_loc = NULL; 1023 data->arg_hard_regs = NULL; 1024 data->alternative_enabled_p = NULL; 1025 data->operand_loc = XNEWVEC (rtx *, 1); 1026 data->operand_loc[0] = &INSN_VAR_LOCATION_LOC (insn); 1027 return data; 1028 } 1029 if (icode < 0) 1030 { 1031 int nop; 1032 enum machine_mode operand_mode[MAX_RECOG_OPERANDS]; 1033 const char *constraints[MAX_RECOG_OPERANDS]; 1034 1035 nop = asm_noperands (PATTERN (insn)); 1036 data->operand_loc = data->dup_loc = NULL; 1037 if (nop < 0) 1038 /* Its is a special insn like USE or CLOBBER. */ 1039 data->insn_static_data = insn_static_data 1040 = get_static_insn_data (-1, 0, 0, 1); 1041 else 1042 { 1043 /* expand_asm_operands makes sure there aren't too many 1044 operands. */ 1045 lra_assert (nop <= MAX_RECOG_OPERANDS); 1046 if (nop != 0) 1047 data->operand_loc = XNEWVEC (rtx *, nop); 1048 /* Now get the operand values and constraints out of the 1049 insn. */ 1050 decode_asm_operands (PATTERN (insn), NULL, 1051 data->operand_loc, 1052 constraints, operand_mode, NULL); 1053 n = 1; 1054 if (nop > 0) 1055 { 1056 const char *p = recog_data.constraints[0]; 1057 1058 for (p = constraints[0]; *p; p++) 1059 n += *p == ','; 1060 } 1061 data->insn_static_data = insn_static_data 1062 = get_static_insn_data (-1, nop, 0, n); 1063 for (i = 0; i < nop; i++) 1064 { 1065 insn_static_data->operand[i].mode = operand_mode[i]; 1066 insn_static_data->operand[i].constraint = constraints[i]; 1067 insn_static_data->operand[i].strict_low = false; 1068 insn_static_data->operand[i].is_operator = false; 1069 insn_static_data->operand[i].is_address = false; 1070 } 1071 } 1072 for (i = 0; i < insn_static_data->n_operands; i++) 1073 insn_static_data->operand[i].type 1074 = (insn_static_data->operand[i].constraint[0] == '=' ? OP_OUT 1075 : insn_static_data->operand[i].constraint[0] == '+' ? OP_INOUT 1076 : OP_IN); 1077 data->alternative_enabled_p = NULL; 1078 } 1079 else 1080 { 1081 insn_extract (insn); 1082 data->insn_static_data = insn_static_data 1083 = get_static_insn_data (icode, insn_data[icode].n_operands, 1084 insn_data[icode].n_dups, 1085 insn_data[icode].n_alternatives); 1086 n = insn_static_data->n_operands; 1087 if (n == 0) 1088 locs = NULL; 1089 else 1090 { 1091 locs = XNEWVEC (rtx *, n); 1092 memcpy (locs, recog_data.operand_loc, n * sizeof (rtx *)); 1093 } 1094 data->operand_loc = locs; 1095 n = insn_static_data->n_dups; 1096 if (n == 0) 1097 locs = NULL; 1098 else 1099 { 1100 locs = XNEWVEC (rtx *, n); 1101 memcpy (locs, recog_data.dup_loc, n * sizeof (rtx *)); 1102 } 1103 data->dup_loc = locs; 1104 if (HAVE_ATTR_enabled) 1105 { 1106 bool *bp; 1107 1108 n = insn_static_data->n_alternatives; 1109 lra_assert (n >= 0); 1110 data->alternative_enabled_p = bp = XNEWVEC (bool, n); 1111 /* Cache the insn because we don't want to call extract_insn 1112 from get_attr_enabled as extract_insn modifies 1113 which_alternative. The attribute enabled should not depend 1114 on insn operands, operand modes, operand types, and operand 1115 constraints. It should depend on the architecture. If it 1116 is not true, we should rewrite this file code to use 1117 extract_insn instead of less expensive insn_extract. */ 1118 recog_data.insn = insn; 1119 for (i = 0; i < n; i++) 1120 { 1121 which_alternative = i; 1122 bp[i] = get_attr_enabled (insn); 1123 } 1124 } 1125 } 1126 if (GET_CODE (PATTERN (insn)) == CLOBBER || GET_CODE (PATTERN (insn)) == USE) 1127 insn_static_data->hard_regs = NULL; 1128 else 1129 insn_static_data->hard_regs 1130 = collect_non_operand_hard_regs (&PATTERN (insn), data, 1131 NULL, OP_IN, false); 1132 setup_operand_alternative (data); 1133 data->arg_hard_regs = NULL; 1134 if (CALL_P (insn)) 1135 { 1136 rtx link; 1137 int n_hard_regs, regno, arg_hard_regs[FIRST_PSEUDO_REGISTER]; 1138 1139 n_hard_regs = 0; 1140 /* Finding implicit hard register usage. We believe it will be 1141 not changed whatever transformations are used. Call insns 1142 are such example. */ 1143 for (link = CALL_INSN_FUNCTION_USAGE (insn); 1144 link != NULL_RTX; 1145 link = XEXP (link, 1)) 1146 if (GET_CODE (XEXP (link, 0)) == USE 1147 && REG_P (XEXP (XEXP (link, 0), 0))) 1148 { 1149 regno = REGNO (XEXP (XEXP (link, 0), 0)); 1150 lra_assert (regno < FIRST_PSEUDO_REGISTER); 1151 /* It is an argument register. */ 1152 for (i = (hard_regno_nregs 1153 [regno][GET_MODE (XEXP (XEXP (link, 0), 0))]) - 1; 1154 i >= 0; 1155 i--) 1156 arg_hard_regs[n_hard_regs++] = regno + i; 1157 } 1158 if (n_hard_regs != 0) 1159 { 1160 arg_hard_regs[n_hard_regs++] = -1; 1161 data->arg_hard_regs = XNEWVEC (int, n_hard_regs); 1162 memcpy (data->arg_hard_regs, arg_hard_regs, 1163 sizeof (int) * n_hard_regs); 1164 } 1165 } 1166 /* Some output operand can be recognized only from the context not 1167 from the constraints which are empty in this case. Call insn may 1168 contain a hard register in set destination with empty constraint 1169 and extract_insn treats them as an input. */ 1170 for (i = 0; i < insn_static_data->n_operands; i++) 1171 { 1172 int j; 1173 rtx pat, set; 1174 struct lra_operand_data *operand = &insn_static_data->operand[i]; 1175 1176 /* ??? Should we treat 'X' the same way. It looks to me that 1177 'X' means anything and empty constraint means we do not 1178 care. */ 1179 if (operand->type != OP_IN || *operand->constraint != '\0' 1180 || operand->is_operator) 1181 continue; 1182 pat = PATTERN (insn); 1183 if (GET_CODE (pat) == SET) 1184 { 1185 if (data->operand_loc[i] != &SET_DEST (pat)) 1186 continue; 1187 } 1188 else if (GET_CODE (pat) == PARALLEL) 1189 { 1190 for (j = XVECLEN (pat, 0) - 1; j >= 0; j--) 1191 { 1192 set = XVECEXP (PATTERN (insn), 0, j); 1193 if (GET_CODE (set) == SET 1194 && &SET_DEST (set) == data->operand_loc[i]) 1195 break; 1196 } 1197 if (j < 0) 1198 continue; 1199 } 1200 else 1201 continue; 1202 operand->type = OP_OUT; 1203 } 1204 return data; 1205 } 1206 1207 /* Return info about insn give by UID. The info should be already set 1208 up. */ 1209 static lra_insn_recog_data_t 1210 get_insn_recog_data_by_uid (int uid) 1211 { 1212 lra_insn_recog_data_t data; 1213 1214 data = lra_insn_recog_data[uid]; 1215 lra_assert (data != NULL); 1216 return data; 1217 } 1218 1219 /* Invalidate all info about insn given by its UID. */ 1220 static void 1221 invalidate_insn_recog_data (int uid) 1222 { 1223 lra_insn_recog_data_t data; 1224 1225 data = lra_insn_recog_data[uid]; 1226 lra_assert (data != NULL); 1227 free_insn_recog_data (data); 1228 lra_insn_recog_data[uid] = NULL; 1229 } 1230 1231 /* Update all the insn info about INSN. It is usually called when 1232 something in the insn was changed. Return the updated info. */ 1233 lra_insn_recog_data_t 1234 lra_update_insn_recog_data (rtx insn) 1235 { 1236 lra_insn_recog_data_t data; 1237 int n; 1238 unsigned int uid = INSN_UID (insn); 1239 struct lra_static_insn_data *insn_static_data; 1240 1241 check_and_expand_insn_recog_data (uid); 1242 if ((data = lra_insn_recog_data[uid]) != NULL 1243 && data->icode != INSN_CODE (insn)) 1244 { 1245 invalidate_insn_data_regno_info (data, insn, get_insn_freq (insn)); 1246 invalidate_insn_recog_data (uid); 1247 data = NULL; 1248 } 1249 if (data == NULL) 1250 return lra_get_insn_recog_data (insn); 1251 insn_static_data = data->insn_static_data; 1252 data->used_insn_alternative = -1; 1253 if (DEBUG_INSN_P (insn)) 1254 return data; 1255 if (data->icode < 0) 1256 { 1257 int nop; 1258 enum machine_mode operand_mode[MAX_RECOG_OPERANDS]; 1259 const char *constraints[MAX_RECOG_OPERANDS]; 1260 1261 nop = asm_noperands (PATTERN (insn)); 1262 if (nop >= 0) 1263 { 1264 lra_assert (nop == data->insn_static_data->n_operands); 1265 /* Now get the operand values and constraints out of the 1266 insn. */ 1267 decode_asm_operands (PATTERN (insn), NULL, 1268 data->operand_loc, 1269 constraints, operand_mode, NULL); 1270 #ifdef ENABLE_CHECKING 1271 { 1272 int i; 1273 1274 for (i = 0; i < nop; i++) 1275 lra_assert 1276 (insn_static_data->operand[i].mode == operand_mode[i] 1277 && insn_static_data->operand[i].constraint == constraints[i] 1278 && ! insn_static_data->operand[i].is_operator); 1279 } 1280 #endif 1281 } 1282 #ifdef ENABLE_CHECKING 1283 { 1284 int i; 1285 1286 for (i = 0; i < insn_static_data->n_operands; i++) 1287 lra_assert 1288 (insn_static_data->operand[i].type 1289 == (insn_static_data->operand[i].constraint[0] == '=' ? OP_OUT 1290 : insn_static_data->operand[i].constraint[0] == '+' ? OP_INOUT 1291 : OP_IN)); 1292 } 1293 #endif 1294 } 1295 else 1296 { 1297 insn_extract (insn); 1298 n = insn_static_data->n_operands; 1299 if (n != 0) 1300 memcpy (data->operand_loc, recog_data.operand_loc, n * sizeof (rtx *)); 1301 n = insn_static_data->n_dups; 1302 if (n != 0) 1303 memcpy (data->dup_loc, recog_data.dup_loc, n * sizeof (rtx *)); 1304 #if HAVE_ATTR_enabled 1305 #ifdef ENABLE_CHECKING 1306 { 1307 int i; 1308 bool *bp; 1309 1310 n = insn_static_data->n_alternatives; 1311 bp = data->alternative_enabled_p; 1312 lra_assert (n >= 0 && bp != NULL); 1313 /* Cache the insn to prevent extract_insn call from 1314 get_attr_enabled. */ 1315 recog_data.insn = insn; 1316 for (i = 0; i < n; i++) 1317 { 1318 which_alternative = i; 1319 lra_assert (bp[i] == get_attr_enabled (insn)); 1320 } 1321 } 1322 #endif 1323 #endif 1324 } 1325 return data; 1326 } 1327 1328 /* Set up that INSN is using alternative ALT now. */ 1329 void 1330 lra_set_used_insn_alternative (rtx insn, int alt) 1331 { 1332 lra_insn_recog_data_t data; 1333 1334 data = lra_get_insn_recog_data (insn); 1335 data->used_insn_alternative = alt; 1336 } 1337 1338 /* Set up that insn with UID is using alternative ALT now. The insn 1339 info should be already set up. */ 1340 void 1341 lra_set_used_insn_alternative_by_uid (int uid, int alt) 1342 { 1343 lra_insn_recog_data_t data; 1344 1345 check_and_expand_insn_recog_data (uid); 1346 data = lra_insn_recog_data[uid]; 1347 lra_assert (data != NULL); 1348 data->used_insn_alternative = alt; 1349 } 1350 1351 1352 1353 /* This page contains code dealing with common register info and 1354 pseudo copies. */ 1355 1356 /* The size of the following array. */ 1357 static int reg_info_size; 1358 /* Common info about each register. */ 1359 struct lra_reg *lra_reg_info; 1360 1361 /* Last register value. */ 1362 static int last_reg_value; 1363 1364 /* Return new register value. */ 1365 static int 1366 get_new_reg_value (void) 1367 { 1368 return ++last_reg_value; 1369 } 1370 1371 /* Pools for copies. */ 1372 static alloc_pool copy_pool; 1373 1374 /* Vec referring to pseudo copies. */ 1375 static vec<lra_copy_t> copy_vec; 1376 1377 /* Initialize I-th element of lra_reg_info. */ 1378 static inline void 1379 initialize_lra_reg_info_element (int i) 1380 { 1381 bitmap_initialize (&lra_reg_info[i].insn_bitmap, ®_obstack); 1382 #ifdef STACK_REGS 1383 lra_reg_info[i].no_stack_p = false; 1384 #endif 1385 CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs); 1386 lra_reg_info[i].preferred_hard_regno1 = -1; 1387 lra_reg_info[i].preferred_hard_regno2 = -1; 1388 lra_reg_info[i].preferred_hard_regno_profit1 = 0; 1389 lra_reg_info[i].preferred_hard_regno_profit2 = 0; 1390 lra_reg_info[i].biggest_mode = VOIDmode; 1391 lra_reg_info[i].live_ranges = NULL; 1392 lra_reg_info[i].nrefs = lra_reg_info[i].freq = 0; 1393 lra_reg_info[i].last_reload = 0; 1394 lra_reg_info[i].restore_regno = -1; 1395 lra_reg_info[i].val = get_new_reg_value (); 1396 lra_reg_info[i].copies = NULL; 1397 } 1398 1399 /* Initialize common reg info and copies. */ 1400 static void 1401 init_reg_info (void) 1402 { 1403 int i; 1404 1405 last_reg_value = 0; 1406 reg_info_size = max_reg_num () * 3 / 2 + 1; 1407 lra_reg_info = XNEWVEC (struct lra_reg, reg_info_size); 1408 for (i = 0; i < reg_info_size; i++) 1409 initialize_lra_reg_info_element (i); 1410 copy_pool 1411 = create_alloc_pool ("lra copies", sizeof (struct lra_copy), 100); 1412 copy_vec.create (100); 1413 } 1414 1415 1416 /* Finish common reg info and copies. */ 1417 static void 1418 finish_reg_info (void) 1419 { 1420 int i; 1421 1422 for (i = 0; i < reg_info_size; i++) 1423 bitmap_clear (&lra_reg_info[i].insn_bitmap); 1424 free (lra_reg_info); 1425 reg_info_size = 0; 1426 free_alloc_pool (copy_pool); 1427 copy_vec.release (); 1428 } 1429 1430 /* Expand common reg info if it is necessary. */ 1431 static void 1432 expand_reg_info (void) 1433 { 1434 int i, old = reg_info_size; 1435 1436 if (reg_info_size > max_reg_num ()) 1437 return; 1438 reg_info_size = max_reg_num () * 3 / 2 + 1; 1439 lra_reg_info = XRESIZEVEC (struct lra_reg, lra_reg_info, reg_info_size); 1440 for (i = old; i < reg_info_size; i++) 1441 initialize_lra_reg_info_element (i); 1442 } 1443 1444 /* Free all copies. */ 1445 void 1446 lra_free_copies (void) 1447 { 1448 lra_copy_t cp; 1449 1450 while (copy_vec.length () != 0) 1451 { 1452 cp = copy_vec.pop (); 1453 lra_reg_info[cp->regno1].copies = lra_reg_info[cp->regno2].copies = NULL; 1454 pool_free (copy_pool, cp); 1455 } 1456 } 1457 1458 /* Create copy of two pseudos REGNO1 and REGNO2. The copy execution 1459 frequency is FREQ. */ 1460 void 1461 lra_create_copy (int regno1, int regno2, int freq) 1462 { 1463 bool regno1_dest_p; 1464 lra_copy_t cp; 1465 1466 lra_assert (regno1 != regno2); 1467 regno1_dest_p = true; 1468 if (regno1 > regno2) 1469 { 1470 int temp = regno2; 1471 1472 regno1_dest_p = false; 1473 regno2 = regno1; 1474 regno1 = temp; 1475 } 1476 cp = (lra_copy_t) pool_alloc (copy_pool); 1477 copy_vec.safe_push (cp); 1478 cp->regno1_dest_p = regno1_dest_p; 1479 cp->freq = freq; 1480 cp->regno1 = regno1; 1481 cp->regno2 = regno2; 1482 cp->regno1_next = lra_reg_info[regno1].copies; 1483 lra_reg_info[regno1].copies = cp; 1484 cp->regno2_next = lra_reg_info[regno2].copies; 1485 lra_reg_info[regno2].copies = cp; 1486 if (lra_dump_file != NULL) 1487 fprintf (lra_dump_file, " Creating copy r%d%sr%d@%d\n", 1488 regno1, regno1_dest_p ? "<-" : "->", regno2, freq); 1489 } 1490 1491 /* Return N-th (0, 1, ...) copy. If there is no copy, return 1492 NULL. */ 1493 lra_copy_t 1494 lra_get_copy (int n) 1495 { 1496 if (n >= (int) copy_vec.length ()) 1497 return NULL; 1498 return copy_vec[n]; 1499 } 1500 1501 1502 1503 /* This page contains code dealing with info about registers in 1504 insns. */ 1505 1506 /* Process X of insn UID recursively and add info (operand type is 1507 given by TYPE, flag of that it is early clobber is EARLY_CLOBBER) 1508 about registers in X to the insn DATA. */ 1509 static void 1510 add_regs_to_insn_regno_info (lra_insn_recog_data_t data, rtx x, int uid, 1511 enum op_type type, bool early_clobber) 1512 { 1513 int i, j, regno; 1514 bool subreg_p; 1515 enum machine_mode mode; 1516 const char *fmt; 1517 enum rtx_code code; 1518 struct lra_insn_reg *curr; 1519 1520 code = GET_CODE (x); 1521 mode = GET_MODE (x); 1522 subreg_p = false; 1523 if (GET_CODE (x) == SUBREG) 1524 { 1525 x = SUBREG_REG (x); 1526 code = GET_CODE (x); 1527 if (GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (x))) 1528 { 1529 mode = GET_MODE (x); 1530 if (GET_MODE_SIZE (mode) > REGMODE_NATURAL_SIZE (mode)) 1531 subreg_p = true; 1532 } 1533 } 1534 if (REG_P (x)) 1535 { 1536 regno = REGNO (x); 1537 if (regno < FIRST_PSEUDO_REGISTER 1538 && TEST_HARD_REG_BIT (lra_no_alloc_regs, regno) 1539 && ! TEST_HARD_REG_BIT (eliminable_regset, regno)) 1540 return; 1541 expand_reg_info (); 1542 if (bitmap_set_bit (&lra_reg_info[regno].insn_bitmap, uid)) 1543 { 1544 data->regs = new_insn_reg (data->insn, regno, type, mode, subreg_p, 1545 early_clobber, data->regs); 1546 return; 1547 } 1548 else 1549 { 1550 for (curr = data->regs; curr != NULL; curr = curr->next) 1551 if (curr->regno == regno) 1552 { 1553 if (curr->subreg_p != subreg_p || curr->biggest_mode != mode) 1554 /* The info can not be integrated into the found 1555 structure. */ 1556 data->regs = new_insn_reg (data->insn, regno, type, mode, 1557 subreg_p, early_clobber, 1558 data->regs); 1559 else 1560 { 1561 if (curr->type != type) 1562 curr->type = OP_INOUT; 1563 if (curr->early_clobber != early_clobber) 1564 curr->early_clobber = true; 1565 } 1566 return; 1567 } 1568 gcc_unreachable (); 1569 } 1570 } 1571 1572 switch (code) 1573 { 1574 case SET: 1575 add_regs_to_insn_regno_info (data, SET_DEST (x), uid, OP_OUT, false); 1576 add_regs_to_insn_regno_info (data, SET_SRC (x), uid, OP_IN, false); 1577 break; 1578 case CLOBBER: 1579 /* We treat clobber of non-operand hard registers as early 1580 clobber (the behavior is expected from asm). */ 1581 add_regs_to_insn_regno_info (data, XEXP (x, 0), uid, OP_OUT, true); 1582 break; 1583 case PRE_INC: case PRE_DEC: case POST_INC: case POST_DEC: 1584 add_regs_to_insn_regno_info (data, XEXP (x, 0), uid, OP_INOUT, false); 1585 break; 1586 case PRE_MODIFY: case POST_MODIFY: 1587 add_regs_to_insn_regno_info (data, XEXP (x, 0), uid, OP_INOUT, false); 1588 add_regs_to_insn_regno_info (data, XEXP (x, 1), uid, OP_IN, false); 1589 break; 1590 default: 1591 if ((code != PARALLEL && code != EXPR_LIST) || type != OP_OUT) 1592 /* Some targets place small structures in registers for return 1593 values of functions, and those registers are wrapped in 1594 PARALLEL that we may see as the destination of a SET. Here 1595 is an example: 1596 1597 (call_insn 13 12 14 2 (set (parallel:BLK [ 1598 (expr_list:REG_DEP_TRUE (reg:DI 0 ax) 1599 (const_int 0 [0])) 1600 (expr_list:REG_DEP_TRUE (reg:DI 1 dx) 1601 (const_int 8 [0x8])) 1602 ]) 1603 (call (mem:QI (symbol_ref:DI (... */ 1604 type = OP_IN; 1605 fmt = GET_RTX_FORMAT (code); 1606 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1607 { 1608 if (fmt[i] == 'e') 1609 add_regs_to_insn_regno_info (data, XEXP (x, i), uid, type, false); 1610 else if (fmt[i] == 'E') 1611 { 1612 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 1613 add_regs_to_insn_regno_info (data, XVECEXP (x, i, j), uid, 1614 type, false); 1615 } 1616 } 1617 } 1618 } 1619 1620 /* Return execution frequency of INSN. */ 1621 static int 1622 get_insn_freq (rtx insn) 1623 { 1624 basic_block bb; 1625 1626 if ((bb = BLOCK_FOR_INSN (insn)) != NULL) 1627 return REG_FREQ_FROM_BB (bb); 1628 else 1629 { 1630 lra_assert (lra_insn_recog_data[INSN_UID (insn)] 1631 ->insn_static_data->n_operands == 0); 1632 /* We don't care about such insn, e.g. it might be jump with 1633 addr_vec. */ 1634 return 1; 1635 } 1636 } 1637 1638 /* Invalidate all reg info of INSN with DATA and execution frequency 1639 FREQ. Update common info about the invalidated registers. */ 1640 static void 1641 invalidate_insn_data_regno_info (lra_insn_recog_data_t data, rtx insn, 1642 int freq) 1643 { 1644 int uid; 1645 bool debug_p; 1646 unsigned int i; 1647 struct lra_insn_reg *ir, *next_ir; 1648 1649 uid = INSN_UID (insn); 1650 debug_p = DEBUG_INSN_P (insn); 1651 for (ir = data->regs; ir != NULL; ir = next_ir) 1652 { 1653 i = ir->regno; 1654 next_ir = ir->next; 1655 free_insn_reg (ir); 1656 bitmap_clear_bit (&lra_reg_info[i].insn_bitmap, uid); 1657 if (i >= FIRST_PSEUDO_REGISTER && ! debug_p) 1658 { 1659 lra_reg_info[i].nrefs--; 1660 lra_reg_info[i].freq -= freq; 1661 lra_assert (lra_reg_info[i].nrefs >= 0 && lra_reg_info[i].freq >= 0); 1662 } 1663 } 1664 data->regs = NULL; 1665 } 1666 1667 /* Invalidate all reg info of INSN. Update common info about the 1668 invalidated registers. */ 1669 void 1670 lra_invalidate_insn_regno_info (rtx insn) 1671 { 1672 invalidate_insn_data_regno_info (lra_get_insn_recog_data (insn), insn, 1673 get_insn_freq (insn)); 1674 } 1675 1676 /* Update common reg info from reg info of insn given by its DATA and 1677 execution frequency FREQ. */ 1678 static void 1679 setup_insn_reg_info (lra_insn_recog_data_t data, int freq) 1680 { 1681 unsigned int i; 1682 struct lra_insn_reg *ir; 1683 1684 for (ir = data->regs; ir != NULL; ir = ir->next) 1685 if ((i = ir->regno) >= FIRST_PSEUDO_REGISTER) 1686 { 1687 lra_reg_info[i].nrefs++; 1688 lra_reg_info[i].freq += freq; 1689 } 1690 } 1691 1692 /* Set up insn reg info of INSN. Update common reg info from reg info 1693 of INSN. */ 1694 void 1695 lra_update_insn_regno_info (rtx insn) 1696 { 1697 int i, uid, freq; 1698 lra_insn_recog_data_t data; 1699 struct lra_static_insn_data *static_data; 1700 enum rtx_code code; 1701 1702 if (! INSN_P (insn)) 1703 return; 1704 data = lra_get_insn_recog_data (insn); 1705 static_data = data->insn_static_data; 1706 freq = get_insn_freq (insn); 1707 invalidate_insn_data_regno_info (data, insn, freq); 1708 uid = INSN_UID (insn); 1709 for (i = static_data->n_operands - 1; i >= 0; i--) 1710 add_regs_to_insn_regno_info (data, *data->operand_loc[i], uid, 1711 static_data->operand[i].type, 1712 static_data->operand[i].early_clobber); 1713 if ((code = GET_CODE (PATTERN (insn))) == CLOBBER || code == USE) 1714 add_regs_to_insn_regno_info (data, XEXP (PATTERN (insn), 0), uid, 1715 code == USE ? OP_IN : OP_OUT, false); 1716 if (NONDEBUG_INSN_P (insn)) 1717 setup_insn_reg_info (data, freq); 1718 } 1719 1720 /* Return reg info of insn given by it UID. */ 1721 struct lra_insn_reg * 1722 lra_get_insn_regs (int uid) 1723 { 1724 lra_insn_recog_data_t data; 1725 1726 data = get_insn_recog_data_by_uid (uid); 1727 return data->regs; 1728 } 1729 1730 1731 1732 /* This page contains code dealing with stack of the insns which 1733 should be processed by the next constraint pass. */ 1734 1735 /* Bitmap used to put an insn on the stack only in one exemplar. */ 1736 static sbitmap lra_constraint_insn_stack_bitmap; 1737 1738 /* The stack itself. */ 1739 vec<rtx> lra_constraint_insn_stack; 1740 1741 /* Put INSN on the stack. If ALWAYS_UPDATE is true, always update the reg 1742 info for INSN, otherwise only update it if INSN is not already on the 1743 stack. */ 1744 static inline void 1745 lra_push_insn_1 (rtx insn, bool always_update) 1746 { 1747 unsigned int uid = INSN_UID (insn); 1748 if (always_update) 1749 lra_update_insn_regno_info (insn); 1750 if (uid >= SBITMAP_SIZE (lra_constraint_insn_stack_bitmap)) 1751 lra_constraint_insn_stack_bitmap = 1752 sbitmap_resize (lra_constraint_insn_stack_bitmap, 3 * uid / 2, 0); 1753 if (bitmap_bit_p (lra_constraint_insn_stack_bitmap, uid)) 1754 return; 1755 bitmap_set_bit (lra_constraint_insn_stack_bitmap, uid); 1756 if (! always_update) 1757 lra_update_insn_regno_info (insn); 1758 lra_constraint_insn_stack.safe_push (insn); 1759 } 1760 1761 /* Put INSN on the stack. */ 1762 void 1763 lra_push_insn (rtx insn) 1764 { 1765 lra_push_insn_1 (insn, false); 1766 } 1767 1768 /* Put INSN on the stack and update its reg info. */ 1769 void 1770 lra_push_insn_and_update_insn_regno_info (rtx insn) 1771 { 1772 lra_push_insn_1 (insn, true); 1773 } 1774 1775 /* Put insn with UID on the stack. */ 1776 void 1777 lra_push_insn_by_uid (unsigned int uid) 1778 { 1779 lra_push_insn (lra_insn_recog_data[uid]->insn); 1780 } 1781 1782 /* Take the last-inserted insns off the stack and return it. */ 1783 rtx 1784 lra_pop_insn (void) 1785 { 1786 rtx insn = lra_constraint_insn_stack.pop (); 1787 bitmap_clear_bit (lra_constraint_insn_stack_bitmap, INSN_UID (insn)); 1788 return insn; 1789 } 1790 1791 /* Return the current size of the insn stack. */ 1792 unsigned int 1793 lra_insn_stack_length (void) 1794 { 1795 return lra_constraint_insn_stack.length (); 1796 } 1797 1798 /* Push insns FROM to TO (excluding it) going in reverse order. */ 1799 static void 1800 push_insns (rtx from, rtx to) 1801 { 1802 rtx insn; 1803 1804 if (from == NULL_RTX) 1805 return; 1806 for (insn = from; insn != to; insn = PREV_INSN (insn)) 1807 if (INSN_P (insn)) 1808 lra_push_insn (insn); 1809 } 1810 1811 /* Emit insns BEFORE before INSN and insns AFTER after INSN. Put the 1812 insns onto the stack. Print about emitting the insns with 1813 TITLE. */ 1814 void 1815 lra_process_new_insns (rtx insn, rtx before, rtx after, const char *title) 1816 { 1817 rtx last; 1818 1819 if (lra_dump_file != NULL && (before != NULL_RTX || after != NULL_RTX)) 1820 { 1821 dump_insn_slim (lra_dump_file, insn); 1822 if (before != NULL_RTX) 1823 { 1824 fprintf (lra_dump_file," %s before:\n", title); 1825 dump_rtl_slim (lra_dump_file, before, NULL_RTX, -1, 0); 1826 } 1827 if (after != NULL_RTX) 1828 { 1829 fprintf (lra_dump_file, " %s after:\n", title); 1830 dump_rtl_slim (lra_dump_file, after, NULL_RTX, -1, 0); 1831 } 1832 fprintf (lra_dump_file, "\n"); 1833 } 1834 if (before != NULL_RTX) 1835 { 1836 emit_insn_before (before, insn); 1837 push_insns (PREV_INSN (insn), PREV_INSN (before)); 1838 } 1839 if (after != NULL_RTX) 1840 { 1841 for (last = after; NEXT_INSN (last) != NULL_RTX; last = NEXT_INSN (last)) 1842 ; 1843 emit_insn_after (after, insn); 1844 push_insns (last, insn); 1845 } 1846 } 1847 1848 1849 1850 /* This page contains code dealing with scratches (changing them onto 1851 pseudos and restoring them from the pseudos). 1852 1853 We change scratches into pseudos at the beginning of LRA to 1854 simplify dealing with them (conflicts, hard register assignments). 1855 1856 If the pseudo denoting scratch was spilled it means that we do need 1857 a hard register for it. Such pseudos are transformed back to 1858 scratches at the end of LRA. */ 1859 1860 /* Description of location of a former scratch operand. */ 1861 struct sloc 1862 { 1863 rtx insn; /* Insn where the scratch was. */ 1864 int nop; /* Number of the operand which was a scratch. */ 1865 }; 1866 1867 typedef struct sloc *sloc_t; 1868 1869 /* Locations of the former scratches. */ 1870 static vec<sloc_t> scratches; 1871 1872 /* Bitmap of scratch regnos. */ 1873 static bitmap_head scratch_bitmap; 1874 1875 /* Bitmap of scratch operands. */ 1876 static bitmap_head scratch_operand_bitmap; 1877 1878 /* Return true if pseudo REGNO is made of SCRATCH. */ 1879 bool 1880 lra_former_scratch_p (int regno) 1881 { 1882 return bitmap_bit_p (&scratch_bitmap, regno); 1883 } 1884 1885 /* Return true if the operand NOP of INSN is a former scratch. */ 1886 bool 1887 lra_former_scratch_operand_p (rtx insn, int nop) 1888 { 1889 return bitmap_bit_p (&scratch_operand_bitmap, 1890 INSN_UID (insn) * MAX_RECOG_OPERANDS + nop) != 0; 1891 } 1892 1893 /* Change scratches onto pseudos and save their location. */ 1894 static void 1895 remove_scratches (void) 1896 { 1897 int i; 1898 bool insn_changed_p; 1899 basic_block bb; 1900 rtx insn, reg; 1901 sloc_t loc; 1902 lra_insn_recog_data_t id; 1903 struct lra_static_insn_data *static_id; 1904 1905 scratches.create (get_max_uid ()); 1906 bitmap_initialize (&scratch_bitmap, ®_obstack); 1907 bitmap_initialize (&scratch_operand_bitmap, ®_obstack); 1908 FOR_EACH_BB (bb) 1909 FOR_BB_INSNS (bb, insn) 1910 if (INSN_P (insn)) 1911 { 1912 id = lra_get_insn_recog_data (insn); 1913 static_id = id->insn_static_data; 1914 insn_changed_p = false; 1915 for (i = 0; i < static_id->n_operands; i++) 1916 if (GET_CODE (*id->operand_loc[i]) == SCRATCH 1917 && GET_MODE (*id->operand_loc[i]) != VOIDmode) 1918 { 1919 insn_changed_p = true; 1920 *id->operand_loc[i] = reg 1921 = lra_create_new_reg (static_id->operand[i].mode, 1922 *id->operand_loc[i], ALL_REGS, NULL); 1923 add_reg_note (insn, REG_UNUSED, reg); 1924 lra_update_dup (id, i); 1925 loc = XNEW (struct sloc); 1926 loc->insn = insn; 1927 loc->nop = i; 1928 scratches.safe_push (loc); 1929 bitmap_set_bit (&scratch_bitmap, REGNO (*id->operand_loc[i])); 1930 bitmap_set_bit (&scratch_operand_bitmap, 1931 INSN_UID (insn) * MAX_RECOG_OPERANDS + i); 1932 if (lra_dump_file != NULL) 1933 fprintf (lra_dump_file, 1934 "Removing SCRATCH in insn #%u (nop %d)\n", 1935 INSN_UID (insn), i); 1936 } 1937 if (insn_changed_p) 1938 /* Because we might use DF right after caller-saves sub-pass 1939 we need to keep DF info up to date. */ 1940 df_insn_rescan (insn); 1941 } 1942 } 1943 1944 /* Changes pseudos created by function remove_scratches onto scratches. */ 1945 static void 1946 restore_scratches (void) 1947 { 1948 int regno; 1949 unsigned i; 1950 sloc_t loc; 1951 rtx last = NULL_RTX; 1952 lra_insn_recog_data_t id = NULL; 1953 1954 for (i = 0; scratches.iterate (i, &loc); i++) 1955 { 1956 if (last != loc->insn) 1957 { 1958 last = loc->insn; 1959 id = lra_get_insn_recog_data (last); 1960 } 1961 if (REG_P (*id->operand_loc[loc->nop]) 1962 && ((regno = REGNO (*id->operand_loc[loc->nop])) 1963 >= FIRST_PSEUDO_REGISTER) 1964 && lra_get_regno_hard_regno (regno) < 0) 1965 { 1966 /* It should be only case when scratch register with chosen 1967 constraint 'X' did not get memory or hard register. */ 1968 lra_assert (lra_former_scratch_p (regno)); 1969 *id->operand_loc[loc->nop] 1970 = gen_rtx_SCRATCH (GET_MODE (*id->operand_loc[loc->nop])); 1971 lra_update_dup (id, loc->nop); 1972 if (lra_dump_file != NULL) 1973 fprintf (lra_dump_file, "Restoring SCRATCH in insn #%u(nop %d)\n", 1974 INSN_UID (loc->insn), loc->nop); 1975 } 1976 } 1977 for (i = 0; scratches.iterate (i, &loc); i++) 1978 free (loc); 1979 scratches.release (); 1980 bitmap_clear (&scratch_bitmap); 1981 bitmap_clear (&scratch_operand_bitmap); 1982 } 1983 1984 1985 1986 #ifdef ENABLE_CHECKING 1987 1988 /* Function checks RTL for correctness. If FINAL_P is true, it is 1989 done at the end of LRA and the check is more rigorous. */ 1990 static void 1991 check_rtl (bool final_p) 1992 { 1993 int i; 1994 basic_block bb; 1995 rtx insn; 1996 lra_insn_recog_data_t id; 1997 1998 lra_assert (! final_p || reload_completed); 1999 FOR_EACH_BB (bb) 2000 FOR_BB_INSNS (bb, insn) 2001 if (NONDEBUG_INSN_P (insn) 2002 && GET_CODE (PATTERN (insn)) != USE 2003 && GET_CODE (PATTERN (insn)) != CLOBBER 2004 && GET_CODE (PATTERN (insn)) != ADDR_VEC 2005 && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC 2006 && GET_CODE (PATTERN (insn)) != ASM_INPUT) 2007 { 2008 if (final_p) 2009 { 2010 extract_insn (insn); 2011 lra_assert (constrain_operands (1)); 2012 continue; 2013 } 2014 if (insn_invalid_p (insn, false)) 2015 fatal_insn_not_found (insn); 2016 if (asm_noperands (PATTERN (insn)) >= 0) 2017 continue; 2018 id = lra_get_insn_recog_data (insn); 2019 /* The code is based on assumption that all addresses in 2020 regular instruction are legitimate before LRA. The code in 2021 lra-constraints.c is based on assumption that there is no 2022 subreg of memory as an insn operand. */ 2023 for (i = 0; i < id->insn_static_data->n_operands; i++) 2024 { 2025 rtx op = *id->operand_loc[i]; 2026 2027 if (MEM_P (op) 2028 && (GET_MODE (op) != BLKmode 2029 || GET_CODE (XEXP (op, 0)) != SCRATCH) 2030 && ! memory_address_p (GET_MODE (op), XEXP (op, 0)) 2031 /* Some ports don't recognize the following addresses 2032 as legitimate. Although they are legitimate if 2033 they satisfies the constraints and will be checked 2034 by insn constraints which we ignore here. */ 2035 && GET_CODE (XEXP (op, 0)) != UNSPEC 2036 && GET_RTX_CLASS (GET_CODE (XEXP (op, 0))) != RTX_AUTOINC) 2037 fatal_insn_not_found (insn); 2038 } 2039 } 2040 } 2041 #endif /* #ifdef ENABLE_CHECKING */ 2042 2043 /* Determine if the current function has an exception receiver block 2044 that reaches the exit block via non-exceptional edges */ 2045 static bool 2046 has_nonexceptional_receiver (void) 2047 { 2048 edge e; 2049 edge_iterator ei; 2050 basic_block *tos, *worklist, bb; 2051 2052 /* If we're not optimizing, then just err on the safe side. */ 2053 if (!optimize) 2054 return true; 2055 2056 /* First determine which blocks can reach exit via normal paths. */ 2057 tos = worklist = XNEWVEC (basic_block, n_basic_blocks + 1); 2058 2059 FOR_EACH_BB (bb) 2060 bb->flags &= ~BB_REACHABLE; 2061 2062 /* Place the exit block on our worklist. */ 2063 EXIT_BLOCK_PTR->flags |= BB_REACHABLE; 2064 *tos++ = EXIT_BLOCK_PTR; 2065 2066 /* Iterate: find everything reachable from what we've already seen. */ 2067 while (tos != worklist) 2068 { 2069 bb = *--tos; 2070 2071 FOR_EACH_EDGE (e, ei, bb->preds) 2072 if (e->flags & EDGE_ABNORMAL) 2073 { 2074 free (worklist); 2075 return true; 2076 } 2077 else 2078 { 2079 basic_block src = e->src; 2080 2081 if (!(src->flags & BB_REACHABLE)) 2082 { 2083 src->flags |= BB_REACHABLE; 2084 *tos++ = src; 2085 } 2086 } 2087 } 2088 free (worklist); 2089 /* No exceptional block reached exit unexceptionally. */ 2090 return false; 2091 } 2092 2093 #ifdef AUTO_INC_DEC 2094 2095 /* Process recursively X of INSN and add REG_INC notes if necessary. */ 2096 static void 2097 add_auto_inc_notes (rtx insn, rtx x) 2098 { 2099 enum rtx_code code = GET_CODE (x); 2100 const char *fmt; 2101 int i, j; 2102 2103 if (code == MEM && auto_inc_p (XEXP (x, 0))) 2104 { 2105 add_reg_note (insn, REG_INC, XEXP (XEXP (x, 0), 0)); 2106 return; 2107 } 2108 2109 /* Scan all X sub-expressions. */ 2110 fmt = GET_RTX_FORMAT (code); 2111 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 2112 { 2113 if (fmt[i] == 'e') 2114 add_auto_inc_notes (insn, XEXP (x, i)); 2115 else if (fmt[i] == 'E') 2116 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 2117 add_auto_inc_notes (insn, XVECEXP (x, i, j)); 2118 } 2119 } 2120 2121 #endif 2122 2123 /* Remove all REG_DEAD and REG_UNUSED notes and regenerate REG_INC. 2124 We change pseudos by hard registers without notification of DF and 2125 that can make the notes obsolete. DF-infrastructure does not deal 2126 with REG_INC notes -- so we should regenerate them here. */ 2127 static void 2128 update_inc_notes (void) 2129 { 2130 rtx *pnote; 2131 basic_block bb; 2132 rtx insn; 2133 2134 FOR_EACH_BB (bb) 2135 FOR_BB_INSNS (bb, insn) 2136 if (NONDEBUG_INSN_P (insn)) 2137 { 2138 pnote = ®_NOTES (insn); 2139 while (*pnote != 0) 2140 { 2141 if (REG_NOTE_KIND (*pnote) == REG_INC) 2142 *pnote = XEXP (*pnote, 1); 2143 else 2144 pnote = &XEXP (*pnote, 1); 2145 } 2146 #ifdef AUTO_INC_DEC 2147 add_auto_inc_notes (insn, PATTERN (insn)); 2148 #endif 2149 } 2150 } 2151 2152 /* Set to 1 while in lra. */ 2153 int lra_in_progress; 2154 2155 /* Start of pseudo regnos before the LRA. */ 2156 int lra_new_regno_start; 2157 2158 /* Start of reload pseudo regnos before the new spill pass. */ 2159 int lra_constraint_new_regno_start; 2160 2161 /* Inheritance pseudo regnos before the new spill pass. */ 2162 bitmap_head lra_inheritance_pseudos; 2163 2164 /* Split regnos before the new spill pass. */ 2165 bitmap_head lra_split_regs; 2166 2167 /* Reload pseudo regnos before the new assign pass which still can be 2168 spilled after the assinment pass. */ 2169 bitmap_head lra_optional_reload_pseudos; 2170 2171 /* First UID of insns generated before a new spill pass. */ 2172 int lra_constraint_new_insn_uid_start; 2173 2174 /* File used for output of LRA debug information. */ 2175 FILE *lra_dump_file; 2176 2177 /* True if we should try spill into registers of different classes 2178 instead of memory. */ 2179 bool lra_reg_spill_p; 2180 2181 /* Set up value LRA_REG_SPILL_P. */ 2182 static void 2183 setup_reg_spill_flag (void) 2184 { 2185 int cl, mode; 2186 2187 if (targetm.spill_class != NULL) 2188 for (cl = 0; cl < (int) LIM_REG_CLASSES; cl++) 2189 for (mode = 0; mode < MAX_MACHINE_MODE; mode++) 2190 if (targetm.spill_class ((enum reg_class) cl, 2191 (enum machine_mode) mode) != NO_REGS) 2192 { 2193 lra_reg_spill_p = true; 2194 return; 2195 } 2196 lra_reg_spill_p = false; 2197 } 2198 2199 /* True if the current function is too big to use regular algorithms 2200 in LRA. In other words, we should use simpler and faster algorithms 2201 in LRA. It also means we should not worry about generation code 2202 for caller saves. The value is set up in IRA. */ 2203 bool lra_simple_p; 2204 2205 /* Major LRA entry function. F is a file should be used to dump LRA 2206 debug info. */ 2207 void 2208 lra (FILE *f) 2209 { 2210 int i; 2211 bool live_p, scratch_p, inserted_p; 2212 2213 lra_dump_file = f; 2214 2215 timevar_push (TV_LRA); 2216 2217 COPY_HARD_REG_SET (lra_no_alloc_regs, ira_no_alloc_regs); 2218 2219 init_reg_info (); 2220 expand_reg_info (); 2221 2222 init_insn_recog_data (); 2223 2224 #ifdef ENABLE_CHECKING 2225 check_rtl (false); 2226 #endif 2227 2228 lra_live_range_iter = lra_coalesce_iter = 0; 2229 lra_constraint_iter = lra_constraint_iter_after_spill = 0; 2230 lra_inheritance_iter = lra_undo_inheritance_iter = 0; 2231 2232 setup_reg_spill_flag (); 2233 2234 /* We can not set up reload_in_progress because it prevents new 2235 pseudo creation. */ 2236 lra_in_progress = 1; 2237 2238 /* Function remove_scratches can creates new pseudos for clobbers -- 2239 so set up lra_constraint_new_regno_start before its call to 2240 permit changing reg classes for pseudos created by this 2241 simplification. */ 2242 lra_constraint_new_regno_start = lra_new_regno_start = max_reg_num (); 2243 remove_scratches (); 2244 scratch_p = lra_constraint_new_regno_start != max_reg_num (); 2245 2246 /* A function that has a non-local label that can reach the exit 2247 block via non-exceptional paths must save all call-saved 2248 registers. */ 2249 if (cfun->has_nonlocal_label && has_nonexceptional_receiver ()) 2250 crtl->saves_all_registers = 1; 2251 2252 if (crtl->saves_all_registers) 2253 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 2254 if (! call_used_regs[i] && ! fixed_regs[i] && ! LOCAL_REGNO (i)) 2255 df_set_regs_ever_live (i, true); 2256 2257 /* We don't DF from now and avoid its using because it is to 2258 expensive when a lot of RTL changes are made. */ 2259 df_set_flags (DF_NO_INSN_RESCAN); 2260 lra_constraint_insn_stack.create (get_max_uid ()); 2261 lra_constraint_insn_stack_bitmap = sbitmap_alloc (get_max_uid ()); 2262 bitmap_clear (lra_constraint_insn_stack_bitmap); 2263 lra_live_ranges_init (); 2264 lra_constraints_init (); 2265 lra_curr_reload_num = 0; 2266 push_insns (get_last_insn (), NULL_RTX); 2267 /* It is needed for the 1st coalescing. */ 2268 lra_constraint_new_insn_uid_start = get_max_uid (); 2269 bitmap_initialize (&lra_inheritance_pseudos, ®_obstack); 2270 bitmap_initialize (&lra_split_regs, ®_obstack); 2271 bitmap_initialize (&lra_optional_reload_pseudos, ®_obstack); 2272 live_p = false; 2273 for (;;) 2274 { 2275 for (;;) 2276 { 2277 /* We should try to assign hard registers to scratches even 2278 if there were no RTL transformations in 2279 lra_constraints. */ 2280 if (! lra_constraints (lra_constraint_iter == 0) 2281 && (lra_constraint_iter > 1 2282 || (! scratch_p && ! caller_save_needed))) 2283 break; 2284 /* Constraint transformations may result in that eliminable 2285 hard regs become uneliminable and pseudos which use them 2286 should be spilled. It is better to do it before pseudo 2287 assignments. 2288 2289 For example, rs6000 can make 2290 RS6000_PIC_OFFSET_TABLE_REGNUM uneliminable if we started 2291 to use a constant pool. */ 2292 lra_eliminate (false); 2293 /* Do inheritance only for regular algorithms. */ 2294 if (! lra_simple_p) 2295 lra_inheritance (); 2296 if (live_p) 2297 lra_clear_live_ranges (); 2298 /* We need live ranges for lra_assign -- so build them. */ 2299 lra_create_live_ranges (true); 2300 live_p = true; 2301 /* If we don't spill non-reload and non-inheritance pseudos, 2302 there is no sense to run memory-memory move coalescing. 2303 If inheritance pseudos were spilled, the memory-memory 2304 moves involving them will be removed by pass undoing 2305 inheritance. */ 2306 if (lra_simple_p) 2307 lra_assign (); 2308 else 2309 { 2310 bool spill_p = !lra_assign (); 2311 2312 if (lra_undo_inheritance ()) 2313 live_p = false; 2314 if (spill_p) 2315 { 2316 if (! live_p) 2317 { 2318 lra_create_live_ranges (true); 2319 live_p = true; 2320 } 2321 if (lra_coalesce ()) 2322 live_p = false; 2323 } 2324 if (! live_p) 2325 lra_clear_live_ranges (); 2326 } 2327 } 2328 bitmap_clear (&lra_optional_reload_pseudos); 2329 bitmap_clear (&lra_inheritance_pseudos); 2330 bitmap_clear (&lra_split_regs); 2331 if (! lra_need_for_spills_p ()) 2332 break; 2333 if (! live_p) 2334 { 2335 /* We need full live info for spilling pseudos into 2336 registers instead of memory. */ 2337 lra_create_live_ranges (lra_reg_spill_p); 2338 live_p = true; 2339 } 2340 lra_spill (); 2341 /* Assignment of stack slots changes elimination offsets for 2342 some eliminations. So update the offsets here. */ 2343 lra_eliminate (false); 2344 lra_constraint_new_regno_start = max_reg_num (); 2345 lra_constraint_new_insn_uid_start = get_max_uid (); 2346 lra_constraint_iter_after_spill = 0; 2347 } 2348 restore_scratches (); 2349 lra_eliminate (true); 2350 lra_final_code_change (); 2351 lra_in_progress = 0; 2352 if (live_p) 2353 lra_clear_live_ranges (); 2354 lra_live_ranges_finish (); 2355 lra_constraints_finish (); 2356 finish_reg_info (); 2357 sbitmap_free (lra_constraint_insn_stack_bitmap); 2358 lra_constraint_insn_stack.release (); 2359 finish_insn_recog_data (); 2360 regstat_free_n_sets_and_refs (); 2361 regstat_free_ri (); 2362 reload_completed = 1; 2363 update_inc_notes (); 2364 2365 inserted_p = fixup_abnormal_edges (); 2366 2367 /* We've possibly turned single trapping insn into multiple ones. */ 2368 if (cfun->can_throw_non_call_exceptions) 2369 { 2370 sbitmap blocks; 2371 blocks = sbitmap_alloc (last_basic_block); 2372 bitmap_ones (blocks); 2373 find_many_sub_basic_blocks (blocks); 2374 sbitmap_free (blocks); 2375 } 2376 2377 if (inserted_p) 2378 commit_edge_insertions (); 2379 2380 /* Replacing pseudos with their memory equivalents might have 2381 created shared rtx. Subsequent passes would get confused 2382 by this, so unshare everything here. */ 2383 unshare_all_rtl_again (get_insns ()); 2384 2385 #ifdef ENABLE_CHECKING 2386 check_rtl (true); 2387 #endif 2388 2389 timevar_pop (TV_LRA); 2390 } 2391 2392 /* Called once per compiler to initialize LRA data once. */ 2393 void 2394 lra_init_once (void) 2395 { 2396 init_insn_code_data_once (); 2397 } 2398 2399 /* Initialize LRA whenever register-related information is changed. */ 2400 void 2401 lra_init (void) 2402 { 2403 init_op_alt_data (); 2404 } 2405 2406 /* Called once per compiler to finish LRA data which are initialize 2407 once. */ 2408 void 2409 lra_finish_once (void) 2410 { 2411 finish_insn_code_data_once (); 2412 } 2413