1 /* Discovery of auto-inc and auto-dec instructions. 2 Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc. 3 Contributed by Kenneth Zadeck <zadeck@naturalbridge.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 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "tm.h" 25 #include "tree.h" 26 #include "rtl.h" 27 #include "tm_p.h" 28 #include "hard-reg-set.h" 29 #include "basic-block.h" 30 #include "insn-config.h" 31 #include "regs.h" 32 #include "flags.h" 33 #include "output.h" 34 #include "function.h" 35 #include "except.h" 36 #include "diagnostic-core.h" 37 #include "recog.h" 38 #include "expr.h" 39 #include "timevar.h" 40 #include "tree-pass.h" 41 #include "df.h" 42 #include "dbgcnt.h" 43 #include "target.h" 44 45 /* This pass was originally removed from flow.c. However there is 46 almost nothing that remains of that code. 47 48 There are (4) basic forms that are matched: 49 50 (1) FORM_PRE_ADD 51 a <- b + c 52 ... 53 *a 54 55 becomes 56 57 a <- b 58 ... 59 *(a += c) pre 60 61 62 (2) FORM_PRE_INC 63 a += c 64 ... 65 *a 66 67 becomes 68 69 *(a += c) pre 70 71 72 (3) FORM_POST_ADD 73 *a 74 ... 75 b <- a + c 76 77 (For this case to be true, b must not be assigned or used between 78 the *a and the assignment to b. B must also be a Pmode reg.) 79 80 becomes 81 82 b <- a 83 ... 84 *(b += c) post 85 86 87 (4) FORM_POST_INC 88 *a 89 ... 90 a <- a + c 91 92 becomes 93 94 *(a += c) post 95 96 There are three types of values of c. 97 98 1) c is a constant equal to the width of the value being accessed by 99 the pointer. This is useful for machines that have 100 HAVE_PRE_INCREMENT, HAVE_POST_INCREMENT, HAVE_PRE_DECREMENT or 101 HAVE_POST_DECREMENT defined. 102 103 2) c is a constant not equal to the width of the value being accessed 104 by the pointer. This is useful for machines that have 105 HAVE_PRE_MODIFY_DISP, HAVE_POST_MODIFY_DISP defined. 106 107 3) c is a register. This is useful for machines that have 108 HAVE_PRE_MODIFY_REG, HAVE_POST_MODIFY_REG 109 110 The is one special case: if a already had an offset equal to it +- 111 its width and that offset is equal to -c when the increment was 112 before the ref or +c if the increment was after the ref, then if we 113 can do the combination but switch the pre/post bit. */ 114 115 #ifdef AUTO_INC_DEC 116 117 enum form 118 { 119 FORM_PRE_ADD, 120 FORM_PRE_INC, 121 FORM_POST_ADD, 122 FORM_POST_INC, 123 FORM_last 124 }; 125 126 /* The states of the second operands of mem refs and inc insns. If no 127 second operand of the mem_ref was found, it is assumed to just be 128 ZERO. SIZE is the size of the mode accessed in the memref. The 129 ANY is used for constants that are not +-size or 0. REG is used if 130 the forms are reg1 + reg2. */ 131 132 enum inc_state 133 { 134 INC_ZERO, /* == 0 */ 135 INC_NEG_SIZE, /* == +size */ 136 INC_POS_SIZE, /* == -size */ 137 INC_NEG_ANY, /* == some -constant */ 138 INC_POS_ANY, /* == some +constant */ 139 INC_REG, /* == some register */ 140 INC_last 141 }; 142 143 /* The eight forms that pre/post inc/dec can take. */ 144 enum gen_form 145 { 146 NOTHING, 147 SIMPLE_PRE_INC, /* ++size */ 148 SIMPLE_POST_INC, /* size++ */ 149 SIMPLE_PRE_DEC, /* --size */ 150 SIMPLE_POST_DEC, /* size-- */ 151 DISP_PRE, /* ++con */ 152 DISP_POST, /* con++ */ 153 REG_PRE, /* ++reg */ 154 REG_POST /* reg++ */ 155 }; 156 157 /* Tmp mem rtx for use in cost modeling. */ 158 static rtx mem_tmp; 159 160 static enum inc_state 161 set_inc_state (HOST_WIDE_INT val, int size) 162 { 163 if (val == 0) 164 return INC_ZERO; 165 if (val < 0) 166 return (val == -size) ? INC_NEG_SIZE : INC_NEG_ANY; 167 else 168 return (val == size) ? INC_POS_SIZE : INC_POS_ANY; 169 } 170 171 /* The DECISION_TABLE that describes what form, if any, the increment 172 or decrement will take. It is a three dimensional table. The first 173 index is the type of constant or register found as the second 174 operand of the inc insn. The second index is the type of constant 175 or register found as the second operand of the memory reference (if 176 no second operand exists, 0 is used). The third index is the form 177 and location (relative to the mem reference) of inc insn. */ 178 179 static bool initialized = false; 180 static enum gen_form decision_table[INC_last][INC_last][FORM_last]; 181 182 static void 183 init_decision_table (void) 184 { 185 enum gen_form value; 186 187 if (HAVE_PRE_INCREMENT || HAVE_PRE_MODIFY_DISP) 188 { 189 /* Prefer the simple form if both are available. */ 190 value = (HAVE_PRE_INCREMENT) ? SIMPLE_PRE_INC : DISP_PRE; 191 192 decision_table[INC_POS_SIZE][INC_ZERO][FORM_PRE_ADD] = value; 193 decision_table[INC_POS_SIZE][INC_ZERO][FORM_PRE_INC] = value; 194 195 decision_table[INC_POS_SIZE][INC_POS_SIZE][FORM_POST_ADD] = value; 196 decision_table[INC_POS_SIZE][INC_POS_SIZE][FORM_POST_INC] = value; 197 } 198 199 if (HAVE_POST_INCREMENT || HAVE_POST_MODIFY_DISP) 200 { 201 /* Prefer the simple form if both are available. */ 202 value = (HAVE_POST_INCREMENT) ? SIMPLE_POST_INC : DISP_POST; 203 204 decision_table[INC_POS_SIZE][INC_ZERO][FORM_POST_ADD] = value; 205 decision_table[INC_POS_SIZE][INC_ZERO][FORM_POST_INC] = value; 206 207 decision_table[INC_POS_SIZE][INC_NEG_SIZE][FORM_PRE_ADD] = value; 208 decision_table[INC_POS_SIZE][INC_NEG_SIZE][FORM_PRE_INC] = value; 209 } 210 211 if (HAVE_PRE_DECREMENT || HAVE_PRE_MODIFY_DISP) 212 { 213 /* Prefer the simple form if both are available. */ 214 value = (HAVE_PRE_DECREMENT) ? SIMPLE_PRE_DEC : DISP_PRE; 215 216 decision_table[INC_NEG_SIZE][INC_ZERO][FORM_PRE_ADD] = value; 217 decision_table[INC_NEG_SIZE][INC_ZERO][FORM_PRE_INC] = value; 218 219 decision_table[INC_NEG_SIZE][INC_NEG_SIZE][FORM_POST_ADD] = value; 220 decision_table[INC_NEG_SIZE][INC_NEG_SIZE][FORM_POST_INC] = value; 221 } 222 223 if (HAVE_POST_DECREMENT || HAVE_POST_MODIFY_DISP) 224 { 225 /* Prefer the simple form if both are available. */ 226 value = (HAVE_POST_DECREMENT) ? SIMPLE_POST_DEC : DISP_POST; 227 228 decision_table[INC_NEG_SIZE][INC_ZERO][FORM_POST_ADD] = value; 229 decision_table[INC_NEG_SIZE][INC_ZERO][FORM_POST_INC] = value; 230 231 decision_table[INC_NEG_SIZE][INC_POS_SIZE][FORM_PRE_ADD] = value; 232 decision_table[INC_NEG_SIZE][INC_POS_SIZE][FORM_PRE_INC] = value; 233 } 234 235 if (HAVE_PRE_MODIFY_DISP) 236 { 237 decision_table[INC_POS_ANY][INC_ZERO][FORM_PRE_ADD] = DISP_PRE; 238 decision_table[INC_POS_ANY][INC_ZERO][FORM_PRE_INC] = DISP_PRE; 239 240 decision_table[INC_POS_ANY][INC_POS_ANY][FORM_POST_ADD] = DISP_PRE; 241 decision_table[INC_POS_ANY][INC_POS_ANY][FORM_POST_INC] = DISP_PRE; 242 243 decision_table[INC_NEG_ANY][INC_ZERO][FORM_PRE_ADD] = DISP_PRE; 244 decision_table[INC_NEG_ANY][INC_ZERO][FORM_PRE_INC] = DISP_PRE; 245 246 decision_table[INC_NEG_ANY][INC_NEG_ANY][FORM_POST_ADD] = DISP_PRE; 247 decision_table[INC_NEG_ANY][INC_NEG_ANY][FORM_POST_INC] = DISP_PRE; 248 } 249 250 if (HAVE_POST_MODIFY_DISP) 251 { 252 decision_table[INC_POS_ANY][INC_ZERO][FORM_POST_ADD] = DISP_POST; 253 decision_table[INC_POS_ANY][INC_ZERO][FORM_POST_INC] = DISP_POST; 254 255 decision_table[INC_POS_ANY][INC_NEG_ANY][FORM_PRE_ADD] = DISP_POST; 256 decision_table[INC_POS_ANY][INC_NEG_ANY][FORM_PRE_INC] = DISP_POST; 257 258 decision_table[INC_NEG_ANY][INC_ZERO][FORM_POST_ADD] = DISP_POST; 259 decision_table[INC_NEG_ANY][INC_ZERO][FORM_POST_INC] = DISP_POST; 260 261 decision_table[INC_NEG_ANY][INC_POS_ANY][FORM_PRE_ADD] = DISP_POST; 262 decision_table[INC_NEG_ANY][INC_POS_ANY][FORM_PRE_INC] = DISP_POST; 263 } 264 265 /* This is much simpler than the other cases because we do not look 266 for the reg1-reg2 case. Note that we do not have a INC_POS_REG 267 and INC_NEG_REG states. Most of the use of such states would be 268 on a target that had an R1 - R2 update address form. 269 270 There is the remote possibility that you could also catch a = a + 271 b; *(a - b) as a postdecrement of (a + b). However, it is 272 unclear if *(a - b) would ever be generated on a machine that did 273 not have that kind of addressing mode. The IA-64 and RS6000 will 274 not do this, and I cannot speak for any other. If any 275 architecture does have an a-b update for, these cases should be 276 added. */ 277 if (HAVE_PRE_MODIFY_REG) 278 { 279 decision_table[INC_REG][INC_ZERO][FORM_PRE_ADD] = REG_PRE; 280 decision_table[INC_REG][INC_ZERO][FORM_PRE_INC] = REG_PRE; 281 282 decision_table[INC_REG][INC_REG][FORM_POST_ADD] = REG_PRE; 283 decision_table[INC_REG][INC_REG][FORM_POST_INC] = REG_PRE; 284 } 285 286 if (HAVE_POST_MODIFY_REG) 287 { 288 decision_table[INC_REG][INC_ZERO][FORM_POST_ADD] = REG_POST; 289 decision_table[INC_REG][INC_ZERO][FORM_POST_INC] = REG_POST; 290 } 291 292 initialized = true; 293 } 294 295 /* Parsed fields of an inc insn of the form "reg_res = reg0+reg1" or 296 "reg_res = reg0+c". */ 297 298 static struct inc_insn 299 { 300 rtx insn; /* The insn being parsed. */ 301 rtx pat; /* The pattern of the insn. */ 302 bool reg1_is_const; /* True if reg1 is const, false if reg1 is a reg. */ 303 enum form form; 304 rtx reg_res; 305 rtx reg0; 306 rtx reg1; 307 enum inc_state reg1_state;/* The form of the const if reg1 is a const. */ 308 HOST_WIDE_INT reg1_val;/* Value if reg1 is const. */ 309 } inc_insn; 310 311 312 /* Dump the parsed inc insn to FILE. */ 313 314 static void 315 dump_inc_insn (FILE *file) 316 { 317 const char *f = ((inc_insn.form == FORM_PRE_ADD) 318 || (inc_insn.form == FORM_PRE_INC)) ? "pre" : "post"; 319 320 dump_insn_slim (file, inc_insn.insn); 321 322 switch (inc_insn.form) 323 { 324 case FORM_PRE_ADD: 325 case FORM_POST_ADD: 326 if (inc_insn.reg1_is_const) 327 fprintf (file, "found %s add(%d) r[%d]=r[%d]+%d\n", 328 f, INSN_UID (inc_insn.insn), 329 REGNO (inc_insn.reg_res), 330 REGNO (inc_insn.reg0), (int) inc_insn.reg1_val); 331 else 332 fprintf (file, "found %s add(%d) r[%d]=r[%d]+r[%d]\n", 333 f, INSN_UID (inc_insn.insn), 334 REGNO (inc_insn.reg_res), 335 REGNO (inc_insn.reg0), REGNO (inc_insn.reg1)); 336 break; 337 338 case FORM_PRE_INC: 339 case FORM_POST_INC: 340 if (inc_insn.reg1_is_const) 341 fprintf (file, "found %s inc(%d) r[%d]+=%d\n", 342 f, INSN_UID (inc_insn.insn), 343 REGNO (inc_insn.reg_res), (int) inc_insn.reg1_val); 344 else 345 fprintf (file, "found %s inc(%d) r[%d]+=r[%d]\n", 346 f, INSN_UID (inc_insn.insn), 347 REGNO (inc_insn.reg_res), REGNO (inc_insn.reg1)); 348 break; 349 350 default: 351 break; 352 } 353 } 354 355 356 /* Parsed fields of a mem ref of the form "*(reg0+reg1)" or "*(reg0+c)". */ 357 358 static struct mem_insn 359 { 360 rtx insn; /* The insn being parsed. */ 361 rtx pat; /* The pattern of the insn. */ 362 rtx *mem_loc; /* The address of the field that holds the mem */ 363 /* that is to be replaced. */ 364 bool reg1_is_const; /* True if reg1 is const, false if reg1 is a reg. */ 365 rtx reg0; 366 rtx reg1; /* This is either a reg or a const depending on 367 reg1_is_const. */ 368 enum inc_state reg1_state;/* The form of the const if reg1 is a const. */ 369 HOST_WIDE_INT reg1_val;/* Value if reg1 is const. */ 370 } mem_insn; 371 372 373 /* Dump the parsed mem insn to FILE. */ 374 375 static void 376 dump_mem_insn (FILE *file) 377 { 378 dump_insn_slim (file, mem_insn.insn); 379 380 if (mem_insn.reg1_is_const) 381 fprintf (file, "found mem(%d) *(r[%d]+%d)\n", 382 INSN_UID (mem_insn.insn), 383 REGNO (mem_insn.reg0), (int) mem_insn.reg1_val); 384 else 385 fprintf (file, "found mem(%d) *(r[%d]+r[%d])\n", 386 INSN_UID (mem_insn.insn), 387 REGNO (mem_insn.reg0), REGNO (mem_insn.reg1)); 388 } 389 390 391 /* The following three arrays contain pointers to instructions. They 392 are indexed by REGNO. At any point in the basic block where we are 393 looking these three arrays contain, respectively, the next insn 394 that uses REGNO, the next inc or add insn that uses REGNO and the 395 next insn that sets REGNO. 396 397 The arrays are not cleared when we move from block to block so 398 whenever an insn is retrieved from these arrays, it's block number 399 must be compared with the current block. 400 */ 401 402 static rtx *reg_next_use = NULL; 403 static rtx *reg_next_inc_use = NULL; 404 static rtx *reg_next_def = NULL; 405 406 407 /* Move dead note that match PATTERN to TO_INSN from FROM_INSN. We do 408 not really care about moving any other notes from the inc or add 409 insn. Moving the REG_EQUAL and REG_EQUIV is clearly wrong and it 410 does not appear that there are any other kinds of relevant notes. */ 411 412 static void 413 move_dead_notes (rtx to_insn, rtx from_insn, rtx pattern) 414 { 415 rtx note; 416 rtx next_note; 417 rtx prev_note = NULL; 418 419 for (note = REG_NOTES (from_insn); note; note = next_note) 420 { 421 next_note = XEXP (note, 1); 422 423 if ((REG_NOTE_KIND (note) == REG_DEAD) 424 && pattern == XEXP (note, 0)) 425 { 426 XEXP (note, 1) = REG_NOTES (to_insn); 427 REG_NOTES (to_insn) = note; 428 if (prev_note) 429 XEXP (prev_note, 1) = next_note; 430 else 431 REG_NOTES (from_insn) = next_note; 432 } 433 else prev_note = note; 434 } 435 } 436 437 438 /* Create a mov insn DEST_REG <- SRC_REG and insert it before 439 NEXT_INSN. */ 440 441 static rtx 442 insert_move_insn_before (rtx next_insn, rtx dest_reg, rtx src_reg) 443 { 444 rtx insns; 445 446 start_sequence (); 447 emit_move_insn (dest_reg, src_reg); 448 insns = get_insns (); 449 end_sequence (); 450 emit_insn_before (insns, next_insn); 451 return insns; 452 } 453 454 455 /* Change mem_insn.mem_loc so that uses NEW_ADDR which has an 456 increment of INC_REG. To have reached this point, the change is a 457 legitimate one from a dataflow point of view. The only questions 458 are is this a valid change to the instruction and is this a 459 profitable change to the instruction. */ 460 461 static bool 462 attempt_change (rtx new_addr, rtx inc_reg) 463 { 464 /* There are four cases: For the two cases that involve an add 465 instruction, we are going to have to delete the add and insert a 466 mov. We are going to assume that the mov is free. This is 467 fairly early in the backend and there are a lot of opportunities 468 for removing that move later. In particular, there is the case 469 where the move may be dead, this is what dead code elimination 470 passes are for. The two cases where we have an inc insn will be 471 handled mov free. */ 472 473 basic_block bb = BLOCK_FOR_INSN (mem_insn.insn); 474 rtx mov_insn = NULL; 475 int regno; 476 rtx mem = *mem_insn.mem_loc; 477 enum machine_mode mode = GET_MODE (mem); 478 rtx new_mem; 479 int old_cost = 0; 480 int new_cost = 0; 481 bool speed = optimize_bb_for_speed_p (bb); 482 483 PUT_MODE (mem_tmp, mode); 484 XEXP (mem_tmp, 0) = new_addr; 485 486 old_cost = (set_src_cost (mem, speed) 487 + set_rtx_cost (PATTERN (inc_insn.insn), speed)); 488 new_cost = set_src_cost (mem_tmp, speed); 489 490 /* The first item of business is to see if this is profitable. */ 491 if (old_cost < new_cost) 492 { 493 if (dump_file) 494 fprintf (dump_file, "cost failure old=%d new=%d\n", old_cost, new_cost); 495 return false; 496 } 497 498 /* Jump thru a lot of hoops to keep the attributes up to date. We 499 do not want to call one of the change address variants that take 500 an offset even though we know the offset in many cases. These 501 assume you are changing where the address is pointing by the 502 offset. */ 503 new_mem = replace_equiv_address_nv (mem, new_addr); 504 if (! validate_change (mem_insn.insn, mem_insn.mem_loc, new_mem, 0)) 505 { 506 if (dump_file) 507 fprintf (dump_file, "validation failure\n"); 508 return false; 509 } 510 511 /* From here to the end of the function we are committed to the 512 change, i.e. nothing fails. Generate any necessary movs, move 513 any regnotes, and fix up the reg_next_{use,inc_use,def}. */ 514 switch (inc_insn.form) 515 { 516 case FORM_PRE_ADD: 517 /* Replace the addition with a move. Do it at the location of 518 the addition since the operand of the addition may change 519 before the memory reference. */ 520 mov_insn = insert_move_insn_before (inc_insn.insn, 521 inc_insn.reg_res, inc_insn.reg0); 522 move_dead_notes (mov_insn, inc_insn.insn, inc_insn.reg0); 523 524 regno = REGNO (inc_insn.reg_res); 525 reg_next_def[regno] = mov_insn; 526 reg_next_use[regno] = NULL; 527 regno = REGNO (inc_insn.reg0); 528 reg_next_use[regno] = mov_insn; 529 df_recompute_luids (bb); 530 break; 531 532 case FORM_POST_INC: 533 regno = REGNO (inc_insn.reg_res); 534 if (reg_next_use[regno] == reg_next_inc_use[regno]) 535 reg_next_inc_use[regno] = NULL; 536 537 /* Fallthru. */ 538 case FORM_PRE_INC: 539 regno = REGNO (inc_insn.reg_res); 540 reg_next_def[regno] = mem_insn.insn; 541 reg_next_use[regno] = NULL; 542 543 break; 544 545 case FORM_POST_ADD: 546 mov_insn = insert_move_insn_before (mem_insn.insn, 547 inc_insn.reg_res, inc_insn.reg0); 548 move_dead_notes (mov_insn, inc_insn.insn, inc_insn.reg0); 549 550 /* Do not move anything to the mov insn because the instruction 551 pointer for the main iteration has not yet hit that. It is 552 still pointing to the mem insn. */ 553 regno = REGNO (inc_insn.reg_res); 554 reg_next_def[regno] = mem_insn.insn; 555 reg_next_use[regno] = NULL; 556 557 regno = REGNO (inc_insn.reg0); 558 reg_next_use[regno] = mem_insn.insn; 559 if ((reg_next_use[regno] == reg_next_inc_use[regno]) 560 || (reg_next_inc_use[regno] == inc_insn.insn)) 561 reg_next_inc_use[regno] = NULL; 562 df_recompute_luids (bb); 563 break; 564 565 case FORM_last: 566 default: 567 gcc_unreachable (); 568 } 569 570 if (!inc_insn.reg1_is_const) 571 { 572 regno = REGNO (inc_insn.reg1); 573 reg_next_use[regno] = mem_insn.insn; 574 if ((reg_next_use[regno] == reg_next_inc_use[regno]) 575 || (reg_next_inc_use[regno] == inc_insn.insn)) 576 reg_next_inc_use[regno] = NULL; 577 } 578 579 delete_insn (inc_insn.insn); 580 581 if (dump_file && mov_insn) 582 { 583 fprintf (dump_file, "inserting mov "); 584 dump_insn_slim (dump_file, mov_insn); 585 } 586 587 /* Record that this insn has an implicit side effect. */ 588 add_reg_note (mem_insn.insn, REG_INC, inc_reg); 589 590 if (dump_file) 591 { 592 fprintf (dump_file, "****success "); 593 dump_insn_slim (dump_file, mem_insn.insn); 594 } 595 596 return true; 597 } 598 599 600 /* Try to combine the instruction in INC_INSN with the instruction in 601 MEM_INSN. First the form is determined using the DECISION_TABLE 602 and the results of parsing the INC_INSN and the MEM_INSN. 603 Assuming the form is ok, a prototype new address is built which is 604 passed to ATTEMPT_CHANGE for final processing. */ 605 606 static bool 607 try_merge (void) 608 { 609 enum gen_form gen_form; 610 rtx mem = *mem_insn.mem_loc; 611 rtx inc_reg = inc_insn.form == FORM_POST_ADD ? 612 inc_insn.reg_res : mem_insn.reg0; 613 614 /* The width of the mem being accessed. */ 615 int size = GET_MODE_SIZE (GET_MODE (mem)); 616 rtx last_insn = NULL; 617 enum machine_mode reg_mode = GET_MODE (inc_reg); 618 619 switch (inc_insn.form) 620 { 621 case FORM_PRE_ADD: 622 case FORM_PRE_INC: 623 last_insn = mem_insn.insn; 624 break; 625 case FORM_POST_INC: 626 case FORM_POST_ADD: 627 last_insn = inc_insn.insn; 628 break; 629 case FORM_last: 630 default: 631 gcc_unreachable (); 632 } 633 634 /* Cannot handle auto inc of the stack. */ 635 if (inc_reg == stack_pointer_rtx) 636 { 637 if (dump_file) 638 fprintf (dump_file, "cannot inc stack %d failure\n", REGNO (inc_reg)); 639 return false; 640 } 641 642 /* Look to see if the inc register is dead after the memory 643 reference. If it is, do not do the combination. */ 644 if (find_regno_note (last_insn, REG_DEAD, REGNO (inc_reg))) 645 { 646 if (dump_file) 647 fprintf (dump_file, "dead failure %d\n", REGNO (inc_reg)); 648 return false; 649 } 650 651 mem_insn.reg1_state = (mem_insn.reg1_is_const) 652 ? set_inc_state (mem_insn.reg1_val, size) : INC_REG; 653 inc_insn.reg1_state = (inc_insn.reg1_is_const) 654 ? set_inc_state (inc_insn.reg1_val, size) : INC_REG; 655 656 /* Now get the form that we are generating. */ 657 gen_form = decision_table 658 [inc_insn.reg1_state][mem_insn.reg1_state][inc_insn.form]; 659 660 if (dbg_cnt (auto_inc_dec) == false) 661 return false; 662 663 switch (gen_form) 664 { 665 default: 666 case NOTHING: 667 return false; 668 669 case SIMPLE_PRE_INC: /* ++size */ 670 if (dump_file) 671 fprintf (dump_file, "trying SIMPLE_PRE_INC\n"); 672 return attempt_change (gen_rtx_PRE_INC (reg_mode, inc_reg), inc_reg); 673 break; 674 675 case SIMPLE_POST_INC: /* size++ */ 676 if (dump_file) 677 fprintf (dump_file, "trying SIMPLE_POST_INC\n"); 678 return attempt_change (gen_rtx_POST_INC (reg_mode, inc_reg), inc_reg); 679 break; 680 681 case SIMPLE_PRE_DEC: /* --size */ 682 if (dump_file) 683 fprintf (dump_file, "trying SIMPLE_PRE_DEC\n"); 684 return attempt_change (gen_rtx_PRE_DEC (reg_mode, inc_reg), inc_reg); 685 break; 686 687 case SIMPLE_POST_DEC: /* size-- */ 688 if (dump_file) 689 fprintf (dump_file, "trying SIMPLE_POST_DEC\n"); 690 return attempt_change (gen_rtx_POST_DEC (reg_mode, inc_reg), inc_reg); 691 break; 692 693 case DISP_PRE: /* ++con */ 694 if (dump_file) 695 fprintf (dump_file, "trying DISP_PRE\n"); 696 return attempt_change (gen_rtx_PRE_MODIFY (reg_mode, 697 inc_reg, 698 gen_rtx_PLUS (reg_mode, 699 inc_reg, 700 inc_insn.reg1)), 701 inc_reg); 702 break; 703 704 case DISP_POST: /* con++ */ 705 if (dump_file) 706 fprintf (dump_file, "trying POST_DISP\n"); 707 return attempt_change (gen_rtx_POST_MODIFY (reg_mode, 708 inc_reg, 709 gen_rtx_PLUS (reg_mode, 710 inc_reg, 711 inc_insn.reg1)), 712 inc_reg); 713 break; 714 715 case REG_PRE: /* ++reg */ 716 if (dump_file) 717 fprintf (dump_file, "trying PRE_REG\n"); 718 return attempt_change (gen_rtx_PRE_MODIFY (reg_mode, 719 inc_reg, 720 gen_rtx_PLUS (reg_mode, 721 inc_reg, 722 inc_insn.reg1)), 723 inc_reg); 724 break; 725 726 case REG_POST: /* reg++ */ 727 if (dump_file) 728 fprintf (dump_file, "trying POST_REG\n"); 729 return attempt_change (gen_rtx_POST_MODIFY (reg_mode, 730 inc_reg, 731 gen_rtx_PLUS (reg_mode, 732 inc_reg, 733 inc_insn.reg1)), 734 inc_reg); 735 break; 736 } 737 } 738 739 /* Return the next insn that uses (if reg_next_use is passed in 740 NEXT_ARRAY) or defines (if reg_next_def is passed in NEXT_ARRAY) 741 REGNO in BB. */ 742 743 static rtx 744 get_next_ref (int regno, basic_block bb, rtx *next_array) 745 { 746 rtx insn = next_array[regno]; 747 748 /* Lazy about cleaning out the next_arrays. */ 749 if (insn && BLOCK_FOR_INSN (insn) != bb) 750 { 751 next_array[regno] = NULL; 752 insn = NULL; 753 } 754 755 return insn; 756 } 757 758 759 /* Reverse the operands in a mem insn. */ 760 761 static void 762 reverse_mem (void) 763 { 764 rtx tmp = mem_insn.reg1; 765 mem_insn.reg1 = mem_insn.reg0; 766 mem_insn.reg0 = tmp; 767 } 768 769 770 /* Reverse the operands in a inc insn. */ 771 772 static void 773 reverse_inc (void) 774 { 775 rtx tmp = inc_insn.reg1; 776 inc_insn.reg1 = inc_insn.reg0; 777 inc_insn.reg0 = tmp; 778 } 779 780 781 /* Return true if INSN is of a form "a = b op c" where a and b are 782 regs. op is + if c is a reg and +|- if c is a const. Fill in 783 INC_INSN with what is found. 784 785 This function is called in two contexts, if BEFORE_MEM is true, 786 this is called for each insn in the basic block. If BEFORE_MEM is 787 false, it is called for the instruction in the block that uses the 788 index register for some memory reference that is currently being 789 processed. */ 790 791 static bool 792 parse_add_or_inc (rtx insn, bool before_mem) 793 { 794 rtx pat = single_set (insn); 795 if (!pat) 796 return false; 797 798 /* Result must be single reg. */ 799 if (!REG_P (SET_DEST (pat))) 800 return false; 801 802 if ((GET_CODE (SET_SRC (pat)) != PLUS) 803 && (GET_CODE (SET_SRC (pat)) != MINUS)) 804 return false; 805 806 if (!REG_P (XEXP (SET_SRC (pat), 0))) 807 return false; 808 809 inc_insn.insn = insn; 810 inc_insn.pat = pat; 811 inc_insn.reg_res = SET_DEST (pat); 812 inc_insn.reg0 = XEXP (SET_SRC (pat), 0); 813 if (rtx_equal_p (inc_insn.reg_res, inc_insn.reg0)) 814 inc_insn.form = before_mem ? FORM_PRE_INC : FORM_POST_INC; 815 else 816 inc_insn.form = before_mem ? FORM_PRE_ADD : FORM_POST_ADD; 817 818 if (CONST_INT_P (XEXP (SET_SRC (pat), 1))) 819 { 820 /* Process a = b + c where c is a const. */ 821 inc_insn.reg1_is_const = true; 822 if (GET_CODE (SET_SRC (pat)) == PLUS) 823 { 824 inc_insn.reg1 = XEXP (SET_SRC (pat), 1); 825 inc_insn.reg1_val = INTVAL (inc_insn.reg1); 826 } 827 else 828 { 829 inc_insn.reg1_val = -INTVAL (XEXP (SET_SRC (pat), 1)); 830 inc_insn.reg1 = GEN_INT (inc_insn.reg1_val); 831 } 832 return true; 833 } 834 else if ((HAVE_PRE_MODIFY_REG || HAVE_POST_MODIFY_REG) 835 && (REG_P (XEXP (SET_SRC (pat), 1))) 836 && GET_CODE (SET_SRC (pat)) == PLUS) 837 { 838 /* Process a = b + c where c is a reg. */ 839 inc_insn.reg1 = XEXP (SET_SRC (pat), 1); 840 inc_insn.reg1_is_const = false; 841 842 if (inc_insn.form == FORM_PRE_INC 843 || inc_insn.form == FORM_POST_INC) 844 return true; 845 else if (rtx_equal_p (inc_insn.reg_res, inc_insn.reg1)) 846 { 847 /* Reverse the two operands and turn *_ADD into *_INC since 848 a = c + a. */ 849 reverse_inc (); 850 inc_insn.form = before_mem ? FORM_PRE_INC : FORM_POST_INC; 851 return true; 852 } 853 else 854 return true; 855 } 856 857 return false; 858 } 859 860 861 /* A recursive function that checks all of the mem uses in 862 ADDRESS_OF_X to see if any single one of them is compatible with 863 what has been found in inc_insn. 864 865 -1 is returned for success. 0 is returned if nothing was found and 866 1 is returned for failure. */ 867 868 static int 869 find_address (rtx *address_of_x) 870 { 871 rtx x = *address_of_x; 872 enum rtx_code code = GET_CODE (x); 873 const char *const fmt = GET_RTX_FORMAT (code); 874 int i; 875 int value = 0; 876 int tem; 877 878 if (code == MEM && rtx_equal_p (XEXP (x, 0), inc_insn.reg_res)) 879 { 880 /* Match with *reg0. */ 881 mem_insn.mem_loc = address_of_x; 882 mem_insn.reg0 = inc_insn.reg_res; 883 mem_insn.reg1_is_const = true; 884 mem_insn.reg1_val = 0; 885 mem_insn.reg1 = GEN_INT (0); 886 return -1; 887 } 888 if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS 889 && rtx_equal_p (XEXP (XEXP (x, 0), 0), inc_insn.reg_res)) 890 { 891 rtx b = XEXP (XEXP (x, 0), 1); 892 mem_insn.mem_loc = address_of_x; 893 mem_insn.reg0 = inc_insn.reg_res; 894 mem_insn.reg1 = b; 895 mem_insn.reg1_is_const = inc_insn.reg1_is_const; 896 if (CONST_INT_P (b)) 897 { 898 /* Match with *(reg0 + reg1) where reg1 is a const. */ 899 HOST_WIDE_INT val = INTVAL (b); 900 if (inc_insn.reg1_is_const 901 && (inc_insn.reg1_val == val || inc_insn.reg1_val == -val)) 902 { 903 mem_insn.reg1_val = val; 904 return -1; 905 } 906 } 907 else if (!inc_insn.reg1_is_const 908 && rtx_equal_p (inc_insn.reg1, b)) 909 /* Match with *(reg0 + reg1). */ 910 return -1; 911 } 912 913 if (code == SIGN_EXTRACT || code == ZERO_EXTRACT) 914 { 915 /* If REG occurs inside a MEM used in a bit-field reference, 916 that is unacceptable. */ 917 if (find_address (&XEXP (x, 0))) 918 return 1; 919 } 920 921 if (x == inc_insn.reg_res) 922 return 1; 923 924 /* Time for some deep diving. */ 925 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 926 { 927 if (fmt[i] == 'e') 928 { 929 tem = find_address (&XEXP (x, i)); 930 /* If this is the first use, let it go so the rest of the 931 insn can be checked. */ 932 if (value == 0) 933 value = tem; 934 else if (tem != 0) 935 /* More than one match was found. */ 936 return 1; 937 } 938 else if (fmt[i] == 'E') 939 { 940 int j; 941 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 942 { 943 tem = find_address (&XVECEXP (x, i, j)); 944 /* If this is the first use, let it go so the rest of 945 the insn can be checked. */ 946 if (value == 0) 947 value = tem; 948 else if (tem != 0) 949 /* More than one match was found. */ 950 return 1; 951 } 952 } 953 } 954 return value; 955 } 956 957 /* Once a suitable mem reference has been found and the MEM_INSN 958 structure has been filled in, FIND_INC is called to see if there is 959 a suitable add or inc insn that follows the mem reference and 960 determine if it is suitable to merge. 961 962 In the case where the MEM_INSN has two registers in the reference, 963 this function may be called recursively. The first time looking 964 for an add of the first register, and if that fails, looking for an 965 add of the second register. The FIRST_TRY parameter is used to 966 only allow the parameters to be reversed once. */ 967 968 static bool 969 find_inc (bool first_try) 970 { 971 rtx insn; 972 basic_block bb = BLOCK_FOR_INSN (mem_insn.insn); 973 rtx other_insn; 974 df_ref *def_rec; 975 976 /* Make sure this reg appears only once in this insn. */ 977 if (count_occurrences (PATTERN (mem_insn.insn), mem_insn.reg0, 1) != 1) 978 { 979 if (dump_file) 980 fprintf (dump_file, "mem count failure\n"); 981 return false; 982 } 983 984 if (dump_file) 985 dump_mem_insn (dump_file); 986 987 /* Find the next use that is an inc. */ 988 insn = get_next_ref (REGNO (mem_insn.reg0), 989 BLOCK_FOR_INSN (mem_insn.insn), 990 reg_next_inc_use); 991 if (!insn) 992 return false; 993 994 /* Even though we know the next use is an add or inc because it came 995 from the reg_next_inc_use, we must still reparse. */ 996 if (!parse_add_or_inc (insn, false)) 997 { 998 /* Next use was not an add. Look for one extra case. It could be 999 that we have: 1000 1001 *(a + b) 1002 ...= a; 1003 ...= b + a 1004 1005 if we reverse the operands in the mem ref we would 1006 find this. Only try it once though. */ 1007 if (first_try && !mem_insn.reg1_is_const) 1008 { 1009 reverse_mem (); 1010 return find_inc (false); 1011 } 1012 else 1013 return false; 1014 } 1015 1016 /* Need to assure that none of the operands of the inc instruction are 1017 assigned to by the mem insn. */ 1018 for (def_rec = DF_INSN_DEFS (mem_insn.insn); *def_rec; def_rec++) 1019 { 1020 df_ref def = *def_rec; 1021 unsigned int regno = DF_REF_REGNO (def); 1022 if ((regno == REGNO (inc_insn.reg0)) 1023 || (regno == REGNO (inc_insn.reg_res))) 1024 { 1025 if (dump_file) 1026 fprintf (dump_file, "inc conflicts with store failure.\n"); 1027 return false; 1028 } 1029 if (!inc_insn.reg1_is_const && (regno == REGNO (inc_insn.reg1))) 1030 { 1031 if (dump_file) 1032 fprintf (dump_file, "inc conflicts with store failure.\n"); 1033 return false; 1034 } 1035 } 1036 1037 if (dump_file) 1038 dump_inc_insn (dump_file); 1039 1040 if (inc_insn.form == FORM_POST_ADD) 1041 { 1042 /* Make sure that there is no insn that assigns to inc_insn.res 1043 between the mem_insn and the inc_insn. */ 1044 rtx other_insn = get_next_ref (REGNO (inc_insn.reg_res), 1045 BLOCK_FOR_INSN (mem_insn.insn), 1046 reg_next_def); 1047 if (other_insn != inc_insn.insn) 1048 { 1049 if (dump_file) 1050 fprintf (dump_file, 1051 "result of add is assigned to between mem and inc insns.\n"); 1052 return false; 1053 } 1054 1055 other_insn = get_next_ref (REGNO (inc_insn.reg_res), 1056 BLOCK_FOR_INSN (mem_insn.insn), 1057 reg_next_use); 1058 if (other_insn 1059 && (other_insn != inc_insn.insn) 1060 && (DF_INSN_LUID (inc_insn.insn) > DF_INSN_LUID (other_insn))) 1061 { 1062 if (dump_file) 1063 fprintf (dump_file, 1064 "result of add is used between mem and inc insns.\n"); 1065 return false; 1066 } 1067 1068 /* For the post_add to work, the result_reg of the inc must not be 1069 used in the mem insn since this will become the new index 1070 register. */ 1071 if (reg_overlap_mentioned_p (inc_insn.reg_res, PATTERN (mem_insn.insn))) 1072 { 1073 if (dump_file) 1074 fprintf (dump_file, "base reg replacement failure.\n"); 1075 return false; 1076 } 1077 } 1078 1079 if (mem_insn.reg1_is_const) 1080 { 1081 if (mem_insn.reg1_val == 0) 1082 { 1083 if (!inc_insn.reg1_is_const) 1084 { 1085 /* The mem looks like *r0 and the rhs of the add has two 1086 registers. */ 1087 int luid = DF_INSN_LUID (inc_insn.insn); 1088 if (inc_insn.form == FORM_POST_ADD) 1089 { 1090 /* The trick is that we are not going to increment r0, 1091 we are going to increment the result of the add insn. 1092 For this trick to be correct, the result reg of 1093 the inc must be a valid addressing reg. */ 1094 addr_space_t as = MEM_ADDR_SPACE (*mem_insn.mem_loc); 1095 if (GET_MODE (inc_insn.reg_res) 1096 != targetm.addr_space.address_mode (as)) 1097 { 1098 if (dump_file) 1099 fprintf (dump_file, "base reg mode failure.\n"); 1100 return false; 1101 } 1102 1103 /* We also need to make sure that the next use of 1104 inc result is after the inc. */ 1105 other_insn 1106 = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_use); 1107 if (other_insn && luid > DF_INSN_LUID (other_insn)) 1108 return false; 1109 1110 if (!rtx_equal_p (mem_insn.reg0, inc_insn.reg0)) 1111 reverse_inc (); 1112 } 1113 1114 other_insn 1115 = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_def); 1116 if (other_insn && luid > DF_INSN_LUID (other_insn)) 1117 return false; 1118 } 1119 } 1120 /* Both the inc/add and the mem have a constant. Need to check 1121 that the constants are ok. */ 1122 else if ((mem_insn.reg1_val != inc_insn.reg1_val) 1123 && (mem_insn.reg1_val != -inc_insn.reg1_val)) 1124 return false; 1125 } 1126 else 1127 { 1128 /* The mem insn is of the form *(a + b) where a and b are both 1129 regs. It may be that in order to match the add or inc we 1130 need to treat it as if it was *(b + a). It may also be that 1131 the add is of the form a + c where c does not match b and 1132 then we just abandon this. */ 1133 1134 int luid = DF_INSN_LUID (inc_insn.insn); 1135 rtx other_insn; 1136 1137 /* Make sure this reg appears only once in this insn. */ 1138 if (count_occurrences (PATTERN (mem_insn.insn), mem_insn.reg1, 1) != 1) 1139 return false; 1140 1141 if (inc_insn.form == FORM_POST_ADD) 1142 { 1143 /* For this trick to be correct, the result reg of the inc 1144 must be a valid addressing reg. */ 1145 addr_space_t as = MEM_ADDR_SPACE (*mem_insn.mem_loc); 1146 if (GET_MODE (inc_insn.reg_res) 1147 != targetm.addr_space.address_mode (as)) 1148 { 1149 if (dump_file) 1150 fprintf (dump_file, "base reg mode failure.\n"); 1151 return false; 1152 } 1153 1154 if (rtx_equal_p (mem_insn.reg0, inc_insn.reg0)) 1155 { 1156 if (!rtx_equal_p (mem_insn.reg1, inc_insn.reg1)) 1157 { 1158 /* See comment above on find_inc (false) call. */ 1159 if (first_try) 1160 { 1161 reverse_mem (); 1162 return find_inc (false); 1163 } 1164 else 1165 return false; 1166 } 1167 1168 /* Need to check that there are no assignments to b 1169 before the add insn. */ 1170 other_insn 1171 = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_def); 1172 if (other_insn && luid > DF_INSN_LUID (other_insn)) 1173 return false; 1174 /* All ok for the next step. */ 1175 } 1176 else 1177 { 1178 /* We know that mem_insn.reg0 must equal inc_insn.reg1 1179 or else we would not have found the inc insn. */ 1180 reverse_mem (); 1181 if (!rtx_equal_p (mem_insn.reg0, inc_insn.reg0)) 1182 { 1183 /* See comment above on find_inc (false) call. */ 1184 if (first_try) 1185 return find_inc (false); 1186 else 1187 return false; 1188 } 1189 /* To have gotten here know that. 1190 *(b + a) 1191 1192 ... = (b + a) 1193 1194 We also know that the lhs of the inc is not b or a. We 1195 need to make sure that there are no assignments to b 1196 between the mem ref and the inc. */ 1197 1198 other_insn 1199 = get_next_ref (REGNO (inc_insn.reg0), bb, reg_next_def); 1200 if (other_insn && luid > DF_INSN_LUID (other_insn)) 1201 return false; 1202 } 1203 1204 /* Need to check that the next use of the add result is later than 1205 add insn since this will be the reg incremented. */ 1206 other_insn 1207 = get_next_ref (REGNO (inc_insn.reg_res), bb, reg_next_use); 1208 if (other_insn && luid > DF_INSN_LUID (other_insn)) 1209 return false; 1210 } 1211 else /* FORM_POST_INC. There is less to check here because we 1212 know that operands must line up. */ 1213 { 1214 if (!rtx_equal_p (mem_insn.reg1, inc_insn.reg1)) 1215 /* See comment above on find_inc (false) call. */ 1216 { 1217 if (first_try) 1218 { 1219 reverse_mem (); 1220 return find_inc (false); 1221 } 1222 else 1223 return false; 1224 } 1225 1226 /* To have gotten here know that. 1227 *(a + b) 1228 1229 ... = (a + b) 1230 1231 We also know that the lhs of the inc is not b. We need to make 1232 sure that there are no assignments to b between the mem ref and 1233 the inc. */ 1234 other_insn 1235 = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_def); 1236 if (other_insn && luid > DF_INSN_LUID (other_insn)) 1237 return false; 1238 } 1239 } 1240 1241 if (inc_insn.form == FORM_POST_INC) 1242 { 1243 other_insn 1244 = get_next_ref (REGNO (inc_insn.reg0), bb, reg_next_use); 1245 /* When we found inc_insn, we were looking for the 1246 next add or inc, not the next insn that used the 1247 reg. Because we are going to increment the reg 1248 in this form, we need to make sure that there 1249 were no intervening uses of reg. */ 1250 if (inc_insn.insn != other_insn) 1251 return false; 1252 } 1253 1254 return try_merge (); 1255 } 1256 1257 1258 /* A recursive function that walks ADDRESS_OF_X to find all of the mem 1259 uses in pat that could be used as an auto inc or dec. It then 1260 calls FIND_INC for each one. */ 1261 1262 static bool 1263 find_mem (rtx *address_of_x) 1264 { 1265 rtx x = *address_of_x; 1266 enum rtx_code code = GET_CODE (x); 1267 const char *const fmt = GET_RTX_FORMAT (code); 1268 int i; 1269 1270 if (code == MEM && REG_P (XEXP (x, 0))) 1271 { 1272 /* Match with *reg0. */ 1273 mem_insn.mem_loc = address_of_x; 1274 mem_insn.reg0 = XEXP (x, 0); 1275 mem_insn.reg1_is_const = true; 1276 mem_insn.reg1_val = 0; 1277 mem_insn.reg1 = GEN_INT (0); 1278 if (find_inc (true)) 1279 return true; 1280 } 1281 if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS 1282 && REG_P (XEXP (XEXP (x, 0), 0))) 1283 { 1284 rtx reg1 = XEXP (XEXP (x, 0), 1); 1285 mem_insn.mem_loc = address_of_x; 1286 mem_insn.reg0 = XEXP (XEXP (x, 0), 0); 1287 mem_insn.reg1 = reg1; 1288 if (CONST_INT_P (reg1)) 1289 { 1290 mem_insn.reg1_is_const = true; 1291 /* Match with *(reg0 + c) where c is a const. */ 1292 mem_insn.reg1_val = INTVAL (reg1); 1293 if (find_inc (true)) 1294 return true; 1295 } 1296 else if (REG_P (reg1)) 1297 { 1298 /* Match with *(reg0 + reg1). */ 1299 mem_insn.reg1_is_const = false; 1300 if (find_inc (true)) 1301 return true; 1302 } 1303 } 1304 1305 if (code == SIGN_EXTRACT || code == ZERO_EXTRACT) 1306 { 1307 /* If REG occurs inside a MEM used in a bit-field reference, 1308 that is unacceptable. */ 1309 return false; 1310 } 1311 1312 /* Time for some deep diving. */ 1313 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1314 { 1315 if (fmt[i] == 'e') 1316 { 1317 if (find_mem (&XEXP (x, i))) 1318 return true; 1319 } 1320 else if (fmt[i] == 'E') 1321 { 1322 int j; 1323 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 1324 if (find_mem (&XVECEXP (x, i, j))) 1325 return true; 1326 } 1327 } 1328 return false; 1329 } 1330 1331 1332 /* Try to combine all incs and decs by constant values with memory 1333 references in BB. */ 1334 1335 static void 1336 merge_in_block (int max_reg, basic_block bb) 1337 { 1338 rtx insn; 1339 rtx curr; 1340 int success_in_block = 0; 1341 1342 if (dump_file) 1343 fprintf (dump_file, "\n\nstarting bb %d\n", bb->index); 1344 1345 FOR_BB_INSNS_REVERSE_SAFE (bb, insn, curr) 1346 { 1347 unsigned int uid = INSN_UID (insn); 1348 bool insn_is_add_or_inc = true; 1349 1350 if (!NONDEBUG_INSN_P (insn)) 1351 continue; 1352 1353 /* This continue is deliberate. We do not want the uses of the 1354 jump put into reg_next_use because it is not considered safe to 1355 combine a preincrement with a jump. */ 1356 if (JUMP_P (insn)) 1357 continue; 1358 1359 if (dump_file) 1360 dump_insn_slim (dump_file, insn); 1361 1362 /* Does this instruction increment or decrement a register? */ 1363 if (parse_add_or_inc (insn, true)) 1364 { 1365 int regno = REGNO (inc_insn.reg_res); 1366 /* Cannot handle case where there are three separate regs 1367 before a mem ref. Too many moves would be needed to be 1368 profitable. */ 1369 if ((inc_insn.form == FORM_PRE_INC) || inc_insn.reg1_is_const) 1370 { 1371 mem_insn.insn = get_next_ref (regno, bb, reg_next_use); 1372 if (mem_insn.insn) 1373 { 1374 bool ok = true; 1375 if (!inc_insn.reg1_is_const) 1376 { 1377 /* We are only here if we are going to try a 1378 HAVE_*_MODIFY_REG type transformation. c is a 1379 reg and we must sure that the path from the 1380 inc_insn to the mem_insn.insn is both def and use 1381 clear of c because the inc insn is going to move 1382 into the mem_insn.insn. */ 1383 int luid = DF_INSN_LUID (mem_insn.insn); 1384 rtx other_insn 1385 = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_use); 1386 1387 if (other_insn && luid > DF_INSN_LUID (other_insn)) 1388 ok = false; 1389 1390 other_insn 1391 = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_def); 1392 1393 if (other_insn && luid > DF_INSN_LUID (other_insn)) 1394 ok = false; 1395 } 1396 1397 if (dump_file) 1398 dump_inc_insn (dump_file); 1399 1400 if (ok && find_address (&PATTERN (mem_insn.insn)) == -1) 1401 { 1402 if (dump_file) 1403 dump_mem_insn (dump_file); 1404 if (try_merge ()) 1405 { 1406 success_in_block++; 1407 insn_is_add_or_inc = false; 1408 } 1409 } 1410 } 1411 } 1412 } 1413 else 1414 { 1415 insn_is_add_or_inc = false; 1416 mem_insn.insn = insn; 1417 if (find_mem (&PATTERN (insn))) 1418 success_in_block++; 1419 } 1420 1421 /* If the inc insn was merged with a mem, the inc insn is gone 1422 and there is noting to update. */ 1423 if (DF_INSN_UID_GET (uid)) 1424 { 1425 df_ref *def_rec; 1426 df_ref *use_rec; 1427 /* Need to update next use. */ 1428 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) 1429 { 1430 df_ref def = *def_rec; 1431 reg_next_use[DF_REF_REGNO (def)] = NULL; 1432 reg_next_inc_use[DF_REF_REGNO (def)] = NULL; 1433 reg_next_def[DF_REF_REGNO (def)] = insn; 1434 } 1435 1436 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) 1437 { 1438 df_ref use = *use_rec; 1439 reg_next_use[DF_REF_REGNO (use)] = insn; 1440 if (insn_is_add_or_inc) 1441 reg_next_inc_use[DF_REF_REGNO (use)] = insn; 1442 else 1443 reg_next_inc_use[DF_REF_REGNO (use)] = NULL; 1444 } 1445 } 1446 else if (dump_file) 1447 fprintf (dump_file, "skipping update of deleted insn %d\n", uid); 1448 } 1449 1450 /* If we were successful, try again. There may have been several 1451 opportunities that were interleaved. This is rare but 1452 gcc.c-torture/compile/pr17273.c actually exhibits this. */ 1453 if (success_in_block) 1454 { 1455 /* In this case, we must clear these vectors since the trick of 1456 testing if the stale insn in the block will not work. */ 1457 memset (reg_next_use, 0, max_reg * sizeof(rtx)); 1458 memset (reg_next_inc_use, 0, max_reg * sizeof(rtx)); 1459 memset (reg_next_def, 0, max_reg * sizeof(rtx)); 1460 df_recompute_luids (bb); 1461 merge_in_block (max_reg, bb); 1462 } 1463 } 1464 1465 #endif 1466 1467 static unsigned int 1468 rest_of_handle_auto_inc_dec (void) 1469 { 1470 #ifdef AUTO_INC_DEC 1471 basic_block bb; 1472 int max_reg = max_reg_num (); 1473 1474 if (!initialized) 1475 init_decision_table (); 1476 1477 mem_tmp = gen_rtx_MEM (Pmode, NULL_RTX); 1478 1479 df_note_add_problem (); 1480 df_analyze (); 1481 1482 reg_next_use = XCNEWVEC (rtx, max_reg); 1483 reg_next_inc_use = XCNEWVEC (rtx, max_reg); 1484 reg_next_def = XCNEWVEC (rtx, max_reg); 1485 FOR_EACH_BB (bb) 1486 merge_in_block (max_reg, bb); 1487 1488 free (reg_next_use); 1489 free (reg_next_inc_use); 1490 free (reg_next_def); 1491 1492 mem_tmp = NULL; 1493 #endif 1494 return 0; 1495 } 1496 1497 1498 /* Discover auto-inc auto-dec instructions. */ 1499 1500 static bool 1501 gate_auto_inc_dec (void) 1502 { 1503 #ifdef AUTO_INC_DEC 1504 return (optimize > 0 && flag_auto_inc_dec); 1505 #else 1506 return false; 1507 #endif 1508 } 1509 1510 1511 struct rtl_opt_pass pass_inc_dec = 1512 { 1513 { 1514 RTL_PASS, 1515 "auto_inc_dec", /* name */ 1516 gate_auto_inc_dec, /* gate */ 1517 rest_of_handle_auto_inc_dec, /* execute */ 1518 NULL, /* sub */ 1519 NULL, /* next */ 1520 0, /* static_pass_number */ 1521 TV_AUTO_INC_DEC, /* tv_id */ 1522 0, /* properties_required */ 1523 0, /* properties_provided */ 1524 0, /* properties_destroyed */ 1525 0, /* todo_flags_start */ 1526 TODO_df_finish, /* todo_flags_finish */ 1527 } 1528 }; 1529