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