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