1 /* RTL dead store elimination. 2 Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010 3 Free Software Foundation, Inc. 4 5 Contributed by Richard Sandiford <rsandifor@codesourcery.com> 6 and Kenneth Zadeck <zadeck@naturalbridge.com> 7 8 This file is part of GCC. 9 10 GCC is free software; you can redistribute it and/or modify it under 11 the terms of the GNU General Public License as published by the Free 12 Software Foundation; either version 3, or (at your option) any later 13 version. 14 15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 16 WARRANTY; without even the implied warranty of MERCHANTABILITY or 17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 18 for more details. 19 20 You should have received a copy of the GNU General Public License 21 along with GCC; see the file COPYING3. If not see 22 <http://www.gnu.org/licenses/>. */ 23 24 #undef BASELINE 25 26 #include "config.h" 27 #include "system.h" 28 #include "coretypes.h" 29 #include "hashtab.h" 30 #include "tm.h" 31 #include "rtl.h" 32 #include "tree.h" 33 #include "tm_p.h" 34 #include "regs.h" 35 #include "hard-reg-set.h" 36 #include "flags.h" 37 #include "df.h" 38 #include "cselib.h" 39 #include "timevar.h" 40 #include "tree-pass.h" 41 #include "alloc-pool.h" 42 #include "alias.h" 43 #include "insn-config.h" 44 #include "expr.h" 45 #include "recog.h" 46 #include "dse.h" 47 #include "optabs.h" 48 #include "dbgcnt.h" 49 #include "target.h" 50 51 /* This file contains three techniques for performing Dead Store 52 Elimination (dse). 53 54 * The first technique performs dse locally on any base address. It 55 is based on the cselib which is a local value numbering technique. 56 This technique is local to a basic block but deals with a fairly 57 general addresses. 58 59 * The second technique performs dse globally but is restricted to 60 base addresses that are either constant or are relative to the 61 frame_pointer. 62 63 * The third technique, (which is only done after register allocation) 64 processes the spill spill slots. This differs from the second 65 technique because it takes advantage of the fact that spilling is 66 completely free from the effects of aliasing. 67 68 Logically, dse is a backwards dataflow problem. A store can be 69 deleted if it if cannot be reached in the backward direction by any 70 use of the value being stored. However, the local technique uses a 71 forwards scan of the basic block because cselib requires that the 72 block be processed in that order. 73 74 The pass is logically broken into 7 steps: 75 76 0) Initialization. 77 78 1) The local algorithm, as well as scanning the insns for the two 79 global algorithms. 80 81 2) Analysis to see if the global algs are necessary. In the case 82 of stores base on a constant address, there must be at least two 83 stores to that address, to make it possible to delete some of the 84 stores. In the case of stores off of the frame or spill related 85 stores, only one store to an address is necessary because those 86 stores die at the end of the function. 87 88 3) Set up the global dataflow equations based on processing the 89 info parsed in the first step. 90 91 4) Solve the dataflow equations. 92 93 5) Delete the insns that the global analysis has indicated are 94 unnecessary. 95 96 6) Delete insns that store the same value as preceeding store 97 where the earlier store couldn't be eliminated. 98 99 7) Cleanup. 100 101 This step uses cselib and canon_rtx to build the largest expression 102 possible for each address. This pass is a forwards pass through 103 each basic block. From the point of view of the global technique, 104 the first pass could examine a block in either direction. The 105 forwards ordering is to accommodate cselib. 106 107 We a simplifying assumption: addresses fall into four broad 108 categories: 109 110 1) base has rtx_varies_p == false, offset is constant. 111 2) base has rtx_varies_p == false, offset variable. 112 3) base has rtx_varies_p == true, offset constant. 113 4) base has rtx_varies_p == true, offset variable. 114 115 The local passes are able to process all 4 kinds of addresses. The 116 global pass only handles (1). 117 118 The global problem is formulated as follows: 119 120 A store, S1, to address A, where A is not relative to the stack 121 frame, can be eliminated if all paths from S1 to the end of the 122 of the function contain another store to A before a read to A. 123 124 If the address A is relative to the stack frame, a store S2 to A 125 can be eliminated if there are no paths from S1 that reach the 126 end of the function that read A before another store to A. In 127 this case S2 can be deleted if there are paths to from S2 to the 128 end of the function that have no reads or writes to A. This 129 second case allows stores to the stack frame to be deleted that 130 would otherwise die when the function returns. This cannot be 131 done if stores_off_frame_dead_at_return is not true. See the doc 132 for that variable for when this variable is false. 133 134 The global problem is formulated as a backwards set union 135 dataflow problem where the stores are the gens and reads are the 136 kills. Set union problems are rare and require some special 137 handling given our representation of bitmaps. A straightforward 138 implementation of requires a lot of bitmaps filled with 1s. 139 These are expensive and cumbersome in our bitmap formulation so 140 care has been taken to avoid large vectors filled with 1s. See 141 the comments in bb_info and in the dataflow confluence functions 142 for details. 143 144 There are two places for further enhancements to this algorithm: 145 146 1) The original dse which was embedded in a pass called flow also 147 did local address forwarding. For example in 148 149 A <- r100 150 ... <- A 151 152 flow would replace the right hand side of the second insn with a 153 reference to r100. Most of the information is available to add this 154 to this pass. It has not done it because it is a lot of work in 155 the case that either r100 is assigned to between the first and 156 second insn and/or the second insn is a load of part of the value 157 stored by the first insn. 158 159 insn 5 in gcc.c-torture/compile/990203-1.c simple case. 160 insn 15 in gcc.c-torture/execute/20001017-2.c simple case. 161 insn 25 in gcc.c-torture/execute/20001026-1.c simple case. 162 insn 44 in gcc.c-torture/execute/20010910-1.c simple case. 163 164 2) The cleaning up of spill code is quite profitable. It currently 165 depends on reading tea leaves and chicken entrails left by reload. 166 This pass depends on reload creating a singleton alias set for each 167 spill slot and telling the next dse pass which of these alias sets 168 are the singletons. Rather than analyze the addresses of the 169 spills, dse's spill processing just does analysis of the loads and 170 stores that use those alias sets. There are three cases where this 171 falls short: 172 173 a) Reload sometimes creates the slot for one mode of access, and 174 then inserts loads and/or stores for a smaller mode. In this 175 case, the current code just punts on the slot. The proper thing 176 to do is to back out and use one bit vector position for each 177 byte of the entity associated with the slot. This depends on 178 KNOWING that reload always generates the accesses for each of the 179 bytes in some canonical (read that easy to understand several 180 passes after reload happens) way. 181 182 b) Reload sometimes decides that spill slot it allocated was not 183 large enough for the mode and goes back and allocates more slots 184 with the same mode and alias set. The backout in this case is a 185 little more graceful than (a). In this case the slot is unmarked 186 as being a spill slot and if final address comes out to be based 187 off the frame pointer, the global algorithm handles this slot. 188 189 c) For any pass that may prespill, there is currently no 190 mechanism to tell the dse pass that the slot being used has the 191 special properties that reload uses. It may be that all that is 192 required is to have those passes make the same calls that reload 193 does, assuming that the alias sets can be manipulated in the same 194 way. */ 195 196 /* There are limits to the size of constant offsets we model for the 197 global problem. There are certainly test cases, that exceed this 198 limit, however, it is unlikely that there are important programs 199 that really have constant offsets this size. */ 200 #define MAX_OFFSET (64 * 1024) 201 202 203 static bitmap scratch = NULL; 204 struct insn_info; 205 206 /* This structure holds information about a candidate store. */ 207 struct store_info 208 { 209 210 /* False means this is a clobber. */ 211 bool is_set; 212 213 /* False if a single HOST_WIDE_INT bitmap is used for positions_needed. */ 214 bool is_large; 215 216 /* The id of the mem group of the base address. If rtx_varies_p is 217 true, this is -1. Otherwise, it is the index into the group 218 table. */ 219 int group_id; 220 221 /* This is the cselib value. */ 222 cselib_val *cse_base; 223 224 /* This canonized mem. */ 225 rtx mem; 226 227 /* Canonized MEM address for use by canon_true_dependence. */ 228 rtx mem_addr; 229 230 /* If this is non-zero, it is the alias set of a spill location. */ 231 alias_set_type alias_set; 232 233 /* The offset of the first and byte before the last byte associated 234 with the operation. */ 235 HOST_WIDE_INT begin, end; 236 237 union 238 { 239 /* A bitmask as wide as the number of bytes in the word that 240 contains a 1 if the byte may be needed. The store is unused if 241 all of the bits are 0. This is used if IS_LARGE is false. */ 242 unsigned HOST_WIDE_INT small_bitmask; 243 244 struct 245 { 246 /* A bitmap with one bit per byte. Cleared bit means the position 247 is needed. Used if IS_LARGE is false. */ 248 bitmap bmap; 249 250 /* Number of set bits (i.e. unneeded bytes) in BITMAP. If it is 251 equal to END - BEGIN, the whole store is unused. */ 252 int count; 253 } large; 254 } positions_needed; 255 256 /* The next store info for this insn. */ 257 struct store_info *next; 258 259 /* The right hand side of the store. This is used if there is a 260 subsequent reload of the mems address somewhere later in the 261 basic block. */ 262 rtx rhs; 263 264 /* If rhs is or holds a constant, this contains that constant, 265 otherwise NULL. */ 266 rtx const_rhs; 267 268 /* Set if this store stores the same constant value as REDUNDANT_REASON 269 insn stored. These aren't eliminated early, because doing that 270 might prevent the earlier larger store to be eliminated. */ 271 struct insn_info *redundant_reason; 272 }; 273 274 /* Return a bitmask with the first N low bits set. */ 275 276 static unsigned HOST_WIDE_INT 277 lowpart_bitmask (int n) 278 { 279 unsigned HOST_WIDE_INT mask = ~(unsigned HOST_WIDE_INT) 0; 280 return mask >> (HOST_BITS_PER_WIDE_INT - n); 281 } 282 283 typedef struct store_info *store_info_t; 284 static alloc_pool cse_store_info_pool; 285 static alloc_pool rtx_store_info_pool; 286 287 /* This structure holds information about a load. These are only 288 built for rtx bases. */ 289 struct read_info 290 { 291 /* The id of the mem group of the base address. */ 292 int group_id; 293 294 /* If this is non-zero, it is the alias set of a spill location. */ 295 alias_set_type alias_set; 296 297 /* The offset of the first and byte after the last byte associated 298 with the operation. If begin == end == 0, the read did not have 299 a constant offset. */ 300 int begin, end; 301 302 /* The mem being read. */ 303 rtx mem; 304 305 /* The next read_info for this insn. */ 306 struct read_info *next; 307 }; 308 typedef struct read_info *read_info_t; 309 static alloc_pool read_info_pool; 310 311 312 /* One of these records is created for each insn. */ 313 314 struct insn_info 315 { 316 /* Set true if the insn contains a store but the insn itself cannot 317 be deleted. This is set if the insn is a parallel and there is 318 more than one non dead output or if the insn is in some way 319 volatile. */ 320 bool cannot_delete; 321 322 /* This field is only used by the global algorithm. It is set true 323 if the insn contains any read of mem except for a (1). This is 324 also set if the insn is a call or has a clobber mem. If the insn 325 contains a wild read, the use_rec will be null. */ 326 bool wild_read; 327 328 /* This field is only used for the processing of const functions. 329 These functions cannot read memory, but they can read the stack 330 because that is where they may get their parms. We need to be 331 this conservative because, like the store motion pass, we don't 332 consider CALL_INSN_FUNCTION_USAGE when processing call insns. 333 Moreover, we need to distinguish two cases: 334 1. Before reload (register elimination), the stores related to 335 outgoing arguments are stack pointer based and thus deemed 336 of non-constant base in this pass. This requires special 337 handling but also means that the frame pointer based stores 338 need not be killed upon encountering a const function call. 339 2. After reload, the stores related to outgoing arguments can be 340 either stack pointer or hard frame pointer based. This means 341 that we have no other choice than also killing all the frame 342 pointer based stores upon encountering a const function call. 343 This field is set after reload for const function calls. Having 344 this set is less severe than a wild read, it just means that all 345 the frame related stores are killed rather than all the stores. */ 346 bool frame_read; 347 348 /* This field is only used for the processing of const functions. 349 It is set if the insn may contain a stack pointer based store. */ 350 bool stack_pointer_based; 351 352 /* This is true if any of the sets within the store contains a 353 cselib base. Such stores can only be deleted by the local 354 algorithm. */ 355 bool contains_cselib_groups; 356 357 /* The insn. */ 358 rtx insn; 359 360 /* The list of mem sets or mem clobbers that are contained in this 361 insn. If the insn is deletable, it contains only one mem set. 362 But it could also contain clobbers. Insns that contain more than 363 one mem set are not deletable, but each of those mems are here in 364 order to provide info to delete other insns. */ 365 store_info_t store_rec; 366 367 /* The linked list of mem uses in this insn. Only the reads from 368 rtx bases are listed here. The reads to cselib bases are 369 completely processed during the first scan and so are never 370 created. */ 371 read_info_t read_rec; 372 373 /* The prev insn in the basic block. */ 374 struct insn_info * prev_insn; 375 376 /* The linked list of insns that are in consideration for removal in 377 the forwards pass thru the basic block. This pointer may be 378 trash as it is not cleared when a wild read occurs. The only 379 time it is guaranteed to be correct is when the traversal starts 380 at active_local_stores. */ 381 struct insn_info * next_local_store; 382 }; 383 384 typedef struct insn_info *insn_info_t; 385 static alloc_pool insn_info_pool; 386 387 /* The linked list of stores that are under consideration in this 388 basic block. */ 389 static insn_info_t active_local_stores; 390 391 struct bb_info 392 { 393 394 /* Pointer to the insn info for the last insn in the block. These 395 are linked so this is how all of the insns are reached. During 396 scanning this is the current insn being scanned. */ 397 insn_info_t last_insn; 398 399 /* The info for the global dataflow problem. */ 400 401 402 /* This is set if the transfer function should and in the wild_read 403 bitmap before applying the kill and gen sets. That vector knocks 404 out most of the bits in the bitmap and thus speeds up the 405 operations. */ 406 bool apply_wild_read; 407 408 /* The following 4 bitvectors hold information about which positions 409 of which stores are live or dead. They are indexed by 410 get_bitmap_index. */ 411 412 /* The set of store positions that exist in this block before a wild read. */ 413 bitmap gen; 414 415 /* The set of load positions that exist in this block above the 416 same position of a store. */ 417 bitmap kill; 418 419 /* The set of stores that reach the top of the block without being 420 killed by a read. 421 422 Do not represent the in if it is all ones. Note that this is 423 what the bitvector should logically be initialized to for a set 424 intersection problem. However, like the kill set, this is too 425 expensive. So initially, the in set will only be created for the 426 exit block and any block that contains a wild read. */ 427 bitmap in; 428 429 /* The set of stores that reach the bottom of the block from it's 430 successors. 431 432 Do not represent the in if it is all ones. Note that this is 433 what the bitvector should logically be initialized to for a set 434 intersection problem. However, like the kill and in set, this is 435 too expensive. So what is done is that the confluence operator 436 just initializes the vector from one of the out sets of the 437 successors of the block. */ 438 bitmap out; 439 440 /* The following bitvector is indexed by the reg number. It 441 contains the set of regs that are live at the current instruction 442 being processed. While it contains info for all of the 443 registers, only the pseudos are actually examined. It is used to 444 assure that shift sequences that are inserted do not accidently 445 clobber live hard regs. */ 446 bitmap regs_live; 447 }; 448 449 typedef struct bb_info *bb_info_t; 450 static alloc_pool bb_info_pool; 451 452 /* Table to hold all bb_infos. */ 453 static bb_info_t *bb_table; 454 455 /* There is a group_info for each rtx base that is used to reference 456 memory. There are also not many of the rtx bases because they are 457 very limited in scope. */ 458 459 struct group_info 460 { 461 /* The actual base of the address. */ 462 rtx rtx_base; 463 464 /* The sequential id of the base. This allows us to have a 465 canonical ordering of these that is not based on addresses. */ 466 int id; 467 468 /* True if there are any positions that are to be processed 469 globally. */ 470 bool process_globally; 471 472 /* True if the base of this group is either the frame_pointer or 473 hard_frame_pointer. */ 474 bool frame_related; 475 476 /* A mem wrapped around the base pointer for the group in order to 477 do read dependency. */ 478 rtx base_mem; 479 480 /* Canonized version of base_mem's address. */ 481 rtx canon_base_addr; 482 483 /* These two sets of two bitmaps are used to keep track of how many 484 stores are actually referencing that position from this base. We 485 only do this for rtx bases as this will be used to assign 486 positions in the bitmaps for the global problem. Bit N is set in 487 store1 on the first store for offset N. Bit N is set in store2 488 for the second store to offset N. This is all we need since we 489 only care about offsets that have two or more stores for them. 490 491 The "_n" suffix is for offsets less than 0 and the "_p" suffix is 492 for 0 and greater offsets. 493 494 There is one special case here, for stores into the stack frame, 495 we will or store1 into store2 before deciding which stores look 496 at globally. This is because stores to the stack frame that have 497 no other reads before the end of the function can also be 498 deleted. */ 499 bitmap store1_n, store1_p, store2_n, store2_p; 500 501 /* The positions in this bitmap have the same assignments as the in, 502 out, gen and kill bitmaps. This bitmap is all zeros except for 503 the positions that are occupied by stores for this group. */ 504 bitmap group_kill; 505 506 /* The offset_map is used to map the offsets from this base into 507 positions in the global bitmaps. It is only created after all of 508 the all of stores have been scanned and we know which ones we 509 care about. */ 510 int *offset_map_n, *offset_map_p; 511 int offset_map_size_n, offset_map_size_p; 512 }; 513 typedef struct group_info *group_info_t; 514 typedef const struct group_info *const_group_info_t; 515 static alloc_pool rtx_group_info_pool; 516 517 /* Tables of group_info structures, hashed by base value. */ 518 static htab_t rtx_group_table; 519 520 /* Index into the rtx_group_vec. */ 521 static int rtx_group_next_id; 522 523 DEF_VEC_P(group_info_t); 524 DEF_VEC_ALLOC_P(group_info_t,heap); 525 526 static VEC(group_info_t,heap) *rtx_group_vec; 527 528 529 /* This structure holds the set of changes that are being deferred 530 when removing read operation. See replace_read. */ 531 struct deferred_change 532 { 533 534 /* The mem that is being replaced. */ 535 rtx *loc; 536 537 /* The reg it is being replaced with. */ 538 rtx reg; 539 540 struct deferred_change *next; 541 }; 542 543 typedef struct deferred_change *deferred_change_t; 544 static alloc_pool deferred_change_pool; 545 546 static deferred_change_t deferred_change_list = NULL; 547 548 /* This are used to hold the alias sets of spill variables. Since 549 these are never aliased and there may be a lot of them, it makes 550 sense to treat them specially. This bitvector is only allocated in 551 calls from dse_record_singleton_alias_set which currently is only 552 made during reload1. So when dse is called before reload this 553 mechanism does nothing. */ 554 555 static bitmap clear_alias_sets = NULL; 556 557 /* The set of clear_alias_sets that have been disqualified because 558 there are loads or stores using a different mode than the alias set 559 was registered with. */ 560 static bitmap disqualified_clear_alias_sets = NULL; 561 562 /* The group that holds all of the clear_alias_sets. */ 563 static group_info_t clear_alias_group; 564 565 /* The modes of the clear_alias_sets. */ 566 static htab_t clear_alias_mode_table; 567 568 /* Hash table element to look up the mode for an alias set. */ 569 struct clear_alias_mode_holder 570 { 571 alias_set_type alias_set; 572 enum machine_mode mode; 573 }; 574 575 static alloc_pool clear_alias_mode_pool; 576 577 /* This is true except if cfun->stdarg -- i.e. we cannot do 578 this for vararg functions because they play games with the frame. */ 579 static bool stores_off_frame_dead_at_return; 580 581 /* Counter for stats. */ 582 static int globally_deleted; 583 static int locally_deleted; 584 static int spill_deleted; 585 586 static bitmap all_blocks; 587 588 /* The number of bits used in the global bitmaps. */ 589 static unsigned int current_position; 590 591 592 static bool gate_dse (void); 593 static bool gate_dse1 (void); 594 static bool gate_dse2 (void); 595 596 597 /*---------------------------------------------------------------------------- 598 Zeroth step. 599 600 Initialization. 601 ----------------------------------------------------------------------------*/ 602 603 /* Hashtable callbacks for maintaining the "bases" field of 604 store_group_info, given that the addresses are function invariants. */ 605 606 static int 607 clear_alias_mode_eq (const void *p1, const void *p2) 608 { 609 const struct clear_alias_mode_holder * h1 610 = (const struct clear_alias_mode_holder *) p1; 611 const struct clear_alias_mode_holder * h2 612 = (const struct clear_alias_mode_holder *) p2; 613 return h1->alias_set == h2->alias_set; 614 } 615 616 617 static hashval_t 618 clear_alias_mode_hash (const void *p) 619 { 620 const struct clear_alias_mode_holder *holder 621 = (const struct clear_alias_mode_holder *) p; 622 return holder->alias_set; 623 } 624 625 626 /* Find the entry associated with ALIAS_SET. */ 627 628 static struct clear_alias_mode_holder * 629 clear_alias_set_lookup (alias_set_type alias_set) 630 { 631 struct clear_alias_mode_holder tmp_holder; 632 void **slot; 633 634 tmp_holder.alias_set = alias_set; 635 slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, NO_INSERT); 636 gcc_assert (*slot); 637 638 return (struct clear_alias_mode_holder *) *slot; 639 } 640 641 642 /* Hashtable callbacks for maintaining the "bases" field of 643 store_group_info, given that the addresses are function invariants. */ 644 645 static int 646 invariant_group_base_eq (const void *p1, const void *p2) 647 { 648 const_group_info_t gi1 = (const_group_info_t) p1; 649 const_group_info_t gi2 = (const_group_info_t) p2; 650 return rtx_equal_p (gi1->rtx_base, gi2->rtx_base); 651 } 652 653 654 static hashval_t 655 invariant_group_base_hash (const void *p) 656 { 657 const_group_info_t gi = (const_group_info_t) p; 658 int do_not_record; 659 return hash_rtx (gi->rtx_base, Pmode, &do_not_record, NULL, false); 660 } 661 662 663 /* Get the GROUP for BASE. Add a new group if it is not there. */ 664 665 static group_info_t 666 get_group_info (rtx base) 667 { 668 struct group_info tmp_gi; 669 group_info_t gi; 670 void **slot; 671 672 if (base) 673 { 674 /* Find the store_base_info structure for BASE, creating a new one 675 if necessary. */ 676 tmp_gi.rtx_base = base; 677 slot = htab_find_slot (rtx_group_table, &tmp_gi, INSERT); 678 gi = (group_info_t) *slot; 679 } 680 else 681 { 682 if (!clear_alias_group) 683 { 684 clear_alias_group = gi = 685 (group_info_t) pool_alloc (rtx_group_info_pool); 686 memset (gi, 0, sizeof (struct group_info)); 687 gi->id = rtx_group_next_id++; 688 gi->store1_n = BITMAP_ALLOC (NULL); 689 gi->store1_p = BITMAP_ALLOC (NULL); 690 gi->store2_n = BITMAP_ALLOC (NULL); 691 gi->store2_p = BITMAP_ALLOC (NULL); 692 gi->group_kill = BITMAP_ALLOC (NULL); 693 gi->process_globally = false; 694 gi->offset_map_size_n = 0; 695 gi->offset_map_size_p = 0; 696 gi->offset_map_n = NULL; 697 gi->offset_map_p = NULL; 698 VEC_safe_push (group_info_t, heap, rtx_group_vec, gi); 699 } 700 return clear_alias_group; 701 } 702 703 if (gi == NULL) 704 { 705 *slot = gi = (group_info_t) pool_alloc (rtx_group_info_pool); 706 gi->rtx_base = base; 707 gi->id = rtx_group_next_id++; 708 gi->base_mem = gen_rtx_MEM (QImode, base); 709 gi->canon_base_addr = canon_rtx (base); 710 gi->store1_n = BITMAP_ALLOC (NULL); 711 gi->store1_p = BITMAP_ALLOC (NULL); 712 gi->store2_n = BITMAP_ALLOC (NULL); 713 gi->store2_p = BITMAP_ALLOC (NULL); 714 gi->group_kill = BITMAP_ALLOC (NULL); 715 gi->process_globally = false; 716 gi->frame_related = 717 (base == frame_pointer_rtx) || (base == hard_frame_pointer_rtx); 718 gi->offset_map_size_n = 0; 719 gi->offset_map_size_p = 0; 720 gi->offset_map_n = NULL; 721 gi->offset_map_p = NULL; 722 VEC_safe_push (group_info_t, heap, rtx_group_vec, gi); 723 } 724 725 return gi; 726 } 727 728 729 /* Initialization of data structures. */ 730 731 static void 732 dse_step0 (void) 733 { 734 locally_deleted = 0; 735 globally_deleted = 0; 736 spill_deleted = 0; 737 738 scratch = BITMAP_ALLOC (NULL); 739 740 rtx_store_info_pool 741 = create_alloc_pool ("rtx_store_info_pool", 742 sizeof (struct store_info), 100); 743 read_info_pool 744 = create_alloc_pool ("read_info_pool", 745 sizeof (struct read_info), 100); 746 insn_info_pool 747 = create_alloc_pool ("insn_info_pool", 748 sizeof (struct insn_info), 100); 749 bb_info_pool 750 = create_alloc_pool ("bb_info_pool", 751 sizeof (struct bb_info), 100); 752 rtx_group_info_pool 753 = create_alloc_pool ("rtx_group_info_pool", 754 sizeof (struct group_info), 100); 755 deferred_change_pool 756 = create_alloc_pool ("deferred_change_pool", 757 sizeof (struct deferred_change), 10); 758 759 rtx_group_table = htab_create (11, invariant_group_base_hash, 760 invariant_group_base_eq, NULL); 761 762 bb_table = XCNEWVEC (bb_info_t, last_basic_block); 763 rtx_group_next_id = 0; 764 765 stores_off_frame_dead_at_return = !cfun->stdarg; 766 767 init_alias_analysis (); 768 769 if (clear_alias_sets) 770 clear_alias_group = get_group_info (NULL); 771 else 772 clear_alias_group = NULL; 773 } 774 775 776 777 /*---------------------------------------------------------------------------- 778 First step. 779 780 Scan all of the insns. Any random ordering of the blocks is fine. 781 Each block is scanned in forward order to accommodate cselib which 782 is used to remove stores with non-constant bases. 783 ----------------------------------------------------------------------------*/ 784 785 /* Delete all of the store_info recs from INSN_INFO. */ 786 787 static void 788 free_store_info (insn_info_t insn_info) 789 { 790 store_info_t store_info = insn_info->store_rec; 791 while (store_info) 792 { 793 store_info_t next = store_info->next; 794 if (store_info->is_large) 795 BITMAP_FREE (store_info->positions_needed.large.bmap); 796 if (store_info->cse_base) 797 pool_free (cse_store_info_pool, store_info); 798 else 799 pool_free (rtx_store_info_pool, store_info); 800 store_info = next; 801 } 802 803 insn_info->cannot_delete = true; 804 insn_info->contains_cselib_groups = false; 805 insn_info->store_rec = NULL; 806 } 807 808 809 struct insn_size { 810 int size; 811 rtx insn; 812 }; 813 814 815 /* Add an insn to do the add inside a x if it is a 816 PRE/POST-INC/DEC/MODIFY. D is an structure containing the insn and 817 the size of the mode of the MEM that this is inside of. */ 818 819 static int 820 replace_inc_dec (rtx *r, void *d) 821 { 822 rtx x = *r; 823 struct insn_size *data = (struct insn_size *)d; 824 switch (GET_CODE (x)) 825 { 826 case PRE_INC: 827 case POST_INC: 828 { 829 rtx r1 = XEXP (x, 0); 830 rtx c = gen_int_mode (data->size, GET_MODE (r1)); 831 emit_insn_before (gen_rtx_SET (VOIDmode, r1, 832 gen_rtx_PLUS (GET_MODE (r1), r1, c)), 833 data->insn); 834 return -1; 835 } 836 837 case PRE_DEC: 838 case POST_DEC: 839 { 840 rtx r1 = XEXP (x, 0); 841 rtx c = gen_int_mode (-data->size, GET_MODE (r1)); 842 emit_insn_before (gen_rtx_SET (VOIDmode, r1, 843 gen_rtx_PLUS (GET_MODE (r1), r1, c)), 844 data->insn); 845 return -1; 846 } 847 848 case PRE_MODIFY: 849 case POST_MODIFY: 850 { 851 /* We can reuse the add because we are about to delete the 852 insn that contained it. */ 853 rtx add = XEXP (x, 0); 854 rtx r1 = XEXP (add, 0); 855 emit_insn_before (gen_rtx_SET (VOIDmode, r1, add), data->insn); 856 return -1; 857 } 858 859 default: 860 return 0; 861 } 862 } 863 864 865 /* If X is a MEM, check the address to see if it is PRE/POST-INC/DEC/MODIFY 866 and generate an add to replace that. */ 867 868 static int 869 replace_inc_dec_mem (rtx *r, void *d) 870 { 871 rtx x = *r; 872 if (x != NULL_RTX && MEM_P (x)) 873 { 874 struct insn_size data; 875 876 data.size = GET_MODE_SIZE (GET_MODE (x)); 877 data.insn = (rtx) d; 878 879 for_each_rtx (&XEXP (x, 0), replace_inc_dec, &data); 880 881 return -1; 882 } 883 return 0; 884 } 885 886 /* Before we delete INSN, make sure that the auto inc/dec, if it is 887 there, is split into a separate insn. */ 888 889 static void 890 check_for_inc_dec (rtx insn) 891 { 892 rtx note = find_reg_note (insn, REG_INC, NULL_RTX); 893 if (note) 894 for_each_rtx (&insn, replace_inc_dec_mem, insn); 895 } 896 897 898 /* Delete the insn and free all of the fields inside INSN_INFO. */ 899 900 static void 901 delete_dead_store_insn (insn_info_t insn_info) 902 { 903 read_info_t read_info; 904 905 if (!dbg_cnt (dse)) 906 return; 907 908 check_for_inc_dec (insn_info->insn); 909 if (dump_file) 910 { 911 fprintf (dump_file, "Locally deleting insn %d ", 912 INSN_UID (insn_info->insn)); 913 if (insn_info->store_rec->alias_set) 914 fprintf (dump_file, "alias set %d\n", 915 (int) insn_info->store_rec->alias_set); 916 else 917 fprintf (dump_file, "\n"); 918 } 919 920 free_store_info (insn_info); 921 read_info = insn_info->read_rec; 922 923 while (read_info) 924 { 925 read_info_t next = read_info->next; 926 pool_free (read_info_pool, read_info); 927 read_info = next; 928 } 929 insn_info->read_rec = NULL; 930 931 delete_insn (insn_info->insn); 932 locally_deleted++; 933 insn_info->insn = NULL; 934 935 insn_info->wild_read = false; 936 } 937 938 939 /* Set the store* bitmaps offset_map_size* fields in GROUP based on 940 OFFSET and WIDTH. */ 941 942 static void 943 set_usage_bits (group_info_t group, HOST_WIDE_INT offset, HOST_WIDE_INT width) 944 { 945 HOST_WIDE_INT i; 946 947 if (offset > -MAX_OFFSET && offset + width < MAX_OFFSET) 948 for (i=offset; i<offset+width; i++) 949 { 950 bitmap store1; 951 bitmap store2; 952 int ai; 953 if (i < 0) 954 { 955 store1 = group->store1_n; 956 store2 = group->store2_n; 957 ai = -i; 958 } 959 else 960 { 961 store1 = group->store1_p; 962 store2 = group->store2_p; 963 ai = i; 964 } 965 966 if (bitmap_bit_p (store1, ai)) 967 bitmap_set_bit (store2, ai); 968 else 969 { 970 bitmap_set_bit (store1, ai); 971 if (i < 0) 972 { 973 if (group->offset_map_size_n < ai) 974 group->offset_map_size_n = ai; 975 } 976 else 977 { 978 if (group->offset_map_size_p < ai) 979 group->offset_map_size_p = ai; 980 } 981 } 982 } 983 } 984 985 986 /* Set the BB_INFO so that the last insn is marked as a wild read. */ 987 988 static void 989 add_wild_read (bb_info_t bb_info) 990 { 991 insn_info_t insn_info = bb_info->last_insn; 992 read_info_t *ptr = &insn_info->read_rec; 993 994 while (*ptr) 995 { 996 read_info_t next = (*ptr)->next; 997 if ((*ptr)->alias_set == 0) 998 { 999 pool_free (read_info_pool, *ptr); 1000 *ptr = next; 1001 } 1002 else 1003 ptr = &(*ptr)->next; 1004 } 1005 insn_info->wild_read = true; 1006 active_local_stores = NULL; 1007 } 1008 1009 1010 /* Return true if X is a constant or one of the registers that behave 1011 as a constant over the life of a function. This is equivalent to 1012 !rtx_varies_p for memory addresses. */ 1013 1014 static bool 1015 const_or_frame_p (rtx x) 1016 { 1017 switch (GET_CODE (x)) 1018 { 1019 case CONST: 1020 case CONST_INT: 1021 case CONST_DOUBLE: 1022 case CONST_VECTOR: 1023 case SYMBOL_REF: 1024 case LABEL_REF: 1025 return true; 1026 1027 case REG: 1028 /* Note that we have to test for the actual rtx used for the frame 1029 and arg pointers and not just the register number in case we have 1030 eliminated the frame and/or arg pointer and are using it 1031 for pseudos. */ 1032 if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx 1033 /* The arg pointer varies if it is not a fixed register. */ 1034 || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]) 1035 || x == pic_offset_table_rtx) 1036 return true; 1037 return false; 1038 1039 default: 1040 return false; 1041 } 1042 } 1043 1044 /* Take all reasonable action to put the address of MEM into the form 1045 that we can do analysis on. 1046 1047 The gold standard is to get the address into the form: address + 1048 OFFSET where address is something that rtx_varies_p considers a 1049 constant. When we can get the address in this form, we can do 1050 global analysis on it. Note that for constant bases, address is 1051 not actually returned, only the group_id. The address can be 1052 obtained from that. 1053 1054 If that fails, we try cselib to get a value we can at least use 1055 locally. If that fails we return false. 1056 1057 The GROUP_ID is set to -1 for cselib bases and the index of the 1058 group for non_varying bases. 1059 1060 FOR_READ is true if this is a mem read and false if not. */ 1061 1062 static bool 1063 canon_address (rtx mem, 1064 alias_set_type *alias_set_out, 1065 int *group_id, 1066 HOST_WIDE_INT *offset, 1067 cselib_val **base) 1068 { 1069 enum machine_mode address_mode 1070 = targetm.addr_space.address_mode (MEM_ADDR_SPACE (mem)); 1071 rtx mem_address = XEXP (mem, 0); 1072 rtx expanded_address, address; 1073 int expanded; 1074 1075 /* Make sure that cselib is has initialized all of the operands of 1076 the address before asking it to do the subst. */ 1077 1078 if (clear_alias_sets) 1079 { 1080 /* If this is a spill, do not do any further processing. */ 1081 alias_set_type alias_set = MEM_ALIAS_SET (mem); 1082 if (dump_file) 1083 fprintf (dump_file, "found alias set %d\n", (int) alias_set); 1084 if (bitmap_bit_p (clear_alias_sets, alias_set)) 1085 { 1086 struct clear_alias_mode_holder *entry 1087 = clear_alias_set_lookup (alias_set); 1088 1089 /* If the modes do not match, we cannot process this set. */ 1090 if (entry->mode != GET_MODE (mem)) 1091 { 1092 if (dump_file) 1093 fprintf (dump_file, 1094 "disqualifying alias set %d, (%s) != (%s)\n", 1095 (int) alias_set, GET_MODE_NAME (entry->mode), 1096 GET_MODE_NAME (GET_MODE (mem))); 1097 1098 bitmap_set_bit (disqualified_clear_alias_sets, alias_set); 1099 return false; 1100 } 1101 1102 *alias_set_out = alias_set; 1103 *group_id = clear_alias_group->id; 1104 return true; 1105 } 1106 } 1107 1108 *alias_set_out = 0; 1109 1110 cselib_lookup (mem_address, address_mode, 1); 1111 1112 if (dump_file) 1113 { 1114 fprintf (dump_file, " mem: "); 1115 print_inline_rtx (dump_file, mem_address, 0); 1116 fprintf (dump_file, "\n"); 1117 } 1118 1119 /* First see if just canon_rtx (mem_address) is const or frame, 1120 if not, try cselib_expand_value_rtx and call canon_rtx on that. */ 1121 address = NULL_RTX; 1122 for (expanded = 0; expanded < 2; expanded++) 1123 { 1124 if (expanded) 1125 { 1126 /* Use cselib to replace all of the reg references with the full 1127 expression. This will take care of the case where we have 1128 1129 r_x = base + offset; 1130 val = *r_x; 1131 1132 by making it into 1133 1134 val = *(base + offset); */ 1135 1136 expanded_address = cselib_expand_value_rtx (mem_address, 1137 scratch, 5); 1138 1139 /* If this fails, just go with the address from first 1140 iteration. */ 1141 if (!expanded_address) 1142 break; 1143 } 1144 else 1145 expanded_address = mem_address; 1146 1147 /* Split the address into canonical BASE + OFFSET terms. */ 1148 address = canon_rtx (expanded_address); 1149 1150 *offset = 0; 1151 1152 if (dump_file) 1153 { 1154 if (expanded) 1155 { 1156 fprintf (dump_file, "\n after cselib_expand address: "); 1157 print_inline_rtx (dump_file, expanded_address, 0); 1158 fprintf (dump_file, "\n"); 1159 } 1160 1161 fprintf (dump_file, "\n after canon_rtx address: "); 1162 print_inline_rtx (dump_file, address, 0); 1163 fprintf (dump_file, "\n"); 1164 } 1165 1166 if (GET_CODE (address) == CONST) 1167 address = XEXP (address, 0); 1168 1169 if (GET_CODE (address) == PLUS 1170 && CONST_INT_P (XEXP (address, 1))) 1171 { 1172 *offset = INTVAL (XEXP (address, 1)); 1173 address = XEXP (address, 0); 1174 } 1175 1176 if (ADDR_SPACE_GENERIC_P (MEM_ADDR_SPACE (mem)) 1177 && const_or_frame_p (address)) 1178 { 1179 group_info_t group = get_group_info (address); 1180 1181 if (dump_file) 1182 fprintf (dump_file, " gid=%d offset=%d \n", 1183 group->id, (int)*offset); 1184 *base = NULL; 1185 *group_id = group->id; 1186 return true; 1187 } 1188 } 1189 1190 *base = cselib_lookup (address, address_mode, true); 1191 *group_id = -1; 1192 1193 if (*base == NULL) 1194 { 1195 if (dump_file) 1196 fprintf (dump_file, " no cselib val - should be a wild read.\n"); 1197 return false; 1198 } 1199 if (dump_file) 1200 fprintf (dump_file, " varying cselib base=%u:%u offset = %d\n", 1201 (*base)->uid, (*base)->hash, (int)*offset); 1202 return true; 1203 } 1204 1205 1206 /* Clear the rhs field from the active_local_stores array. */ 1207 1208 static void 1209 clear_rhs_from_active_local_stores (void) 1210 { 1211 insn_info_t ptr = active_local_stores; 1212 1213 while (ptr) 1214 { 1215 store_info_t store_info = ptr->store_rec; 1216 /* Skip the clobbers. */ 1217 while (!store_info->is_set) 1218 store_info = store_info->next; 1219 1220 store_info->rhs = NULL; 1221 store_info->const_rhs = NULL; 1222 1223 ptr = ptr->next_local_store; 1224 } 1225 } 1226 1227 1228 /* Mark byte POS bytes from the beginning of store S_INFO as unneeded. */ 1229 1230 static inline void 1231 set_position_unneeded (store_info_t s_info, int pos) 1232 { 1233 if (__builtin_expect (s_info->is_large, false)) 1234 { 1235 if (!bitmap_bit_p (s_info->positions_needed.large.bmap, pos)) 1236 { 1237 s_info->positions_needed.large.count++; 1238 bitmap_set_bit (s_info->positions_needed.large.bmap, pos); 1239 } 1240 } 1241 else 1242 s_info->positions_needed.small_bitmask 1243 &= ~(((unsigned HOST_WIDE_INT) 1) << pos); 1244 } 1245 1246 /* Mark the whole store S_INFO as unneeded. */ 1247 1248 static inline void 1249 set_all_positions_unneeded (store_info_t s_info) 1250 { 1251 if (__builtin_expect (s_info->is_large, false)) 1252 { 1253 int pos, end = s_info->end - s_info->begin; 1254 for (pos = 0; pos < end; pos++) 1255 bitmap_set_bit (s_info->positions_needed.large.bmap, pos); 1256 s_info->positions_needed.large.count = end; 1257 } 1258 else 1259 s_info->positions_needed.small_bitmask = (unsigned HOST_WIDE_INT) 0; 1260 } 1261 1262 /* Return TRUE if any bytes from S_INFO store are needed. */ 1263 1264 static inline bool 1265 any_positions_needed_p (store_info_t s_info) 1266 { 1267 if (__builtin_expect (s_info->is_large, false)) 1268 return (s_info->positions_needed.large.count 1269 < s_info->end - s_info->begin); 1270 else 1271 return (s_info->positions_needed.small_bitmask 1272 != (unsigned HOST_WIDE_INT) 0); 1273 } 1274 1275 /* Return TRUE if all bytes START through START+WIDTH-1 from S_INFO 1276 store are needed. */ 1277 1278 static inline bool 1279 all_positions_needed_p (store_info_t s_info, int start, int width) 1280 { 1281 if (__builtin_expect (s_info->is_large, false)) 1282 { 1283 int end = start + width; 1284 while (start < end) 1285 if (bitmap_bit_p (s_info->positions_needed.large.bmap, start++)) 1286 return false; 1287 return true; 1288 } 1289 else 1290 { 1291 unsigned HOST_WIDE_INT mask = lowpart_bitmask (width) << start; 1292 return (s_info->positions_needed.small_bitmask & mask) == mask; 1293 } 1294 } 1295 1296 1297 static rtx get_stored_val (store_info_t, enum machine_mode, HOST_WIDE_INT, 1298 HOST_WIDE_INT, basic_block, bool); 1299 1300 1301 /* BODY is an instruction pattern that belongs to INSN. Return 1 if 1302 there is a candidate store, after adding it to the appropriate 1303 local store group if so. */ 1304 1305 static int 1306 record_store (rtx body, bb_info_t bb_info) 1307 { 1308 rtx mem, rhs, const_rhs, mem_addr; 1309 HOST_WIDE_INT offset = 0; 1310 HOST_WIDE_INT width = 0; 1311 alias_set_type spill_alias_set; 1312 insn_info_t insn_info = bb_info->last_insn; 1313 store_info_t store_info = NULL; 1314 int group_id; 1315 cselib_val *base = NULL; 1316 insn_info_t ptr, last, redundant_reason; 1317 bool store_is_unused; 1318 1319 if (GET_CODE (body) != SET && GET_CODE (body) != CLOBBER) 1320 return 0; 1321 1322 mem = SET_DEST (body); 1323 1324 /* If this is not used, then this cannot be used to keep the insn 1325 from being deleted. On the other hand, it does provide something 1326 that can be used to prove that another store is dead. */ 1327 store_is_unused 1328 = (find_reg_note (insn_info->insn, REG_UNUSED, mem) != NULL); 1329 1330 /* Check whether that value is a suitable memory location. */ 1331 if (!MEM_P (mem)) 1332 { 1333 /* If the set or clobber is unused, then it does not effect our 1334 ability to get rid of the entire insn. */ 1335 if (!store_is_unused) 1336 insn_info->cannot_delete = true; 1337 return 0; 1338 } 1339 1340 /* At this point we know mem is a mem. */ 1341 if (GET_MODE (mem) == BLKmode) 1342 { 1343 if (GET_CODE (XEXP (mem, 0)) == SCRATCH) 1344 { 1345 if (dump_file) 1346 fprintf (dump_file, " adding wild read for (clobber (mem:BLK (scratch))\n"); 1347 add_wild_read (bb_info); 1348 insn_info->cannot_delete = true; 1349 return 0; 1350 } 1351 /* Handle (set (mem:BLK (addr) [... S36 ...]) (const_int 0)) 1352 as memset (addr, 0, 36); */ 1353 else if (!MEM_SIZE (mem) 1354 || !CONST_INT_P (MEM_SIZE (mem)) 1355 || GET_CODE (body) != SET 1356 || INTVAL (MEM_SIZE (mem)) <= 0 1357 || INTVAL (MEM_SIZE (mem)) > MAX_OFFSET 1358 || !CONST_INT_P (SET_SRC (body))) 1359 { 1360 if (!store_is_unused) 1361 { 1362 /* If the set or clobber is unused, then it does not effect our 1363 ability to get rid of the entire insn. */ 1364 insn_info->cannot_delete = true; 1365 clear_rhs_from_active_local_stores (); 1366 } 1367 return 0; 1368 } 1369 } 1370 1371 /* We can still process a volatile mem, we just cannot delete it. */ 1372 if (MEM_VOLATILE_P (mem)) 1373 insn_info->cannot_delete = true; 1374 1375 if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base)) 1376 { 1377 clear_rhs_from_active_local_stores (); 1378 return 0; 1379 } 1380 1381 if (GET_MODE (mem) == BLKmode) 1382 width = INTVAL (MEM_SIZE (mem)); 1383 else 1384 { 1385 width = GET_MODE_SIZE (GET_MODE (mem)); 1386 gcc_assert ((unsigned) width <= HOST_BITS_PER_WIDE_INT); 1387 } 1388 1389 if (spill_alias_set) 1390 { 1391 bitmap store1 = clear_alias_group->store1_p; 1392 bitmap store2 = clear_alias_group->store2_p; 1393 1394 gcc_assert (GET_MODE (mem) != BLKmode); 1395 1396 if (bitmap_bit_p (store1, spill_alias_set)) 1397 bitmap_set_bit (store2, spill_alias_set); 1398 else 1399 bitmap_set_bit (store1, spill_alias_set); 1400 1401 if (clear_alias_group->offset_map_size_p < spill_alias_set) 1402 clear_alias_group->offset_map_size_p = spill_alias_set; 1403 1404 store_info = (store_info_t) pool_alloc (rtx_store_info_pool); 1405 1406 if (dump_file) 1407 fprintf (dump_file, " processing spill store %d(%s)\n", 1408 (int) spill_alias_set, GET_MODE_NAME (GET_MODE (mem))); 1409 } 1410 else if (group_id >= 0) 1411 { 1412 /* In the restrictive case where the base is a constant or the 1413 frame pointer we can do global analysis. */ 1414 1415 group_info_t group 1416 = VEC_index (group_info_t, rtx_group_vec, group_id); 1417 1418 store_info = (store_info_t) pool_alloc (rtx_store_info_pool); 1419 set_usage_bits (group, offset, width); 1420 1421 if (dump_file) 1422 fprintf (dump_file, " processing const base store gid=%d[%d..%d)\n", 1423 group_id, (int)offset, (int)(offset+width)); 1424 } 1425 else 1426 { 1427 rtx base_term = find_base_term (XEXP (mem, 0)); 1428 if (!base_term 1429 || (GET_CODE (base_term) == ADDRESS 1430 && GET_MODE (base_term) == Pmode 1431 && XEXP (base_term, 0) == stack_pointer_rtx)) 1432 insn_info->stack_pointer_based = true; 1433 insn_info->contains_cselib_groups = true; 1434 1435 store_info = (store_info_t) pool_alloc (cse_store_info_pool); 1436 group_id = -1; 1437 1438 if (dump_file) 1439 fprintf (dump_file, " processing cselib store [%d..%d)\n", 1440 (int)offset, (int)(offset+width)); 1441 } 1442 1443 const_rhs = rhs = NULL_RTX; 1444 if (GET_CODE (body) == SET 1445 /* No place to keep the value after ra. */ 1446 && !reload_completed 1447 && (REG_P (SET_SRC (body)) 1448 || GET_CODE (SET_SRC (body)) == SUBREG 1449 || CONSTANT_P (SET_SRC (body))) 1450 && !MEM_VOLATILE_P (mem) 1451 /* Sometimes the store and reload is used for truncation and 1452 rounding. */ 1453 && !(FLOAT_MODE_P (GET_MODE (mem)) && (flag_float_store))) 1454 { 1455 rhs = SET_SRC (body); 1456 if (CONSTANT_P (rhs)) 1457 const_rhs = rhs; 1458 else if (body == PATTERN (insn_info->insn)) 1459 { 1460 rtx tem = find_reg_note (insn_info->insn, REG_EQUAL, NULL_RTX); 1461 if (tem && CONSTANT_P (XEXP (tem, 0))) 1462 const_rhs = XEXP (tem, 0); 1463 } 1464 if (const_rhs == NULL_RTX && REG_P (rhs)) 1465 { 1466 rtx tem = cselib_expand_value_rtx (rhs, scratch, 5); 1467 1468 if (tem && CONSTANT_P (tem)) 1469 const_rhs = tem; 1470 } 1471 } 1472 1473 /* Check to see if this stores causes some other stores to be 1474 dead. */ 1475 ptr = active_local_stores; 1476 last = NULL; 1477 redundant_reason = NULL; 1478 mem = canon_rtx (mem); 1479 /* For alias_set != 0 canon_true_dependence should be never called. */ 1480 if (spill_alias_set) 1481 mem_addr = NULL_RTX; 1482 else 1483 { 1484 if (group_id < 0) 1485 mem_addr = base->val_rtx; 1486 else 1487 { 1488 group_info_t group 1489 = VEC_index (group_info_t, rtx_group_vec, group_id); 1490 mem_addr = group->canon_base_addr; 1491 } 1492 if (offset) 1493 mem_addr = plus_constant (mem_addr, offset); 1494 } 1495 1496 while (ptr) 1497 { 1498 insn_info_t next = ptr->next_local_store; 1499 store_info_t s_info = ptr->store_rec; 1500 bool del = true; 1501 1502 /* Skip the clobbers. We delete the active insn if this insn 1503 shadows the set. To have been put on the active list, it 1504 has exactly on set. */ 1505 while (!s_info->is_set) 1506 s_info = s_info->next; 1507 1508 if (s_info->alias_set != spill_alias_set) 1509 del = false; 1510 else if (s_info->alias_set) 1511 { 1512 struct clear_alias_mode_holder *entry 1513 = clear_alias_set_lookup (s_info->alias_set); 1514 /* Generally, spills cannot be processed if and of the 1515 references to the slot have a different mode. But if 1516 we are in the same block and mode is exactly the same 1517 between this store and one before in the same block, 1518 we can still delete it. */ 1519 if ((GET_MODE (mem) == GET_MODE (s_info->mem)) 1520 && (GET_MODE (mem) == entry->mode)) 1521 { 1522 del = true; 1523 set_all_positions_unneeded (s_info); 1524 } 1525 if (dump_file) 1526 fprintf (dump_file, " trying spill store in insn=%d alias_set=%d\n", 1527 INSN_UID (ptr->insn), (int) s_info->alias_set); 1528 } 1529 else if ((s_info->group_id == group_id) 1530 && (s_info->cse_base == base)) 1531 { 1532 HOST_WIDE_INT i; 1533 if (dump_file) 1534 fprintf (dump_file, " trying store in insn=%d gid=%d[%d..%d)\n", 1535 INSN_UID (ptr->insn), s_info->group_id, 1536 (int)s_info->begin, (int)s_info->end); 1537 1538 /* Even if PTR won't be eliminated as unneeded, if both 1539 PTR and this insn store the same constant value, we might 1540 eliminate this insn instead. */ 1541 if (s_info->const_rhs 1542 && const_rhs 1543 && offset >= s_info->begin 1544 && offset + width <= s_info->end 1545 && all_positions_needed_p (s_info, offset - s_info->begin, 1546 width)) 1547 { 1548 if (GET_MODE (mem) == BLKmode) 1549 { 1550 if (GET_MODE (s_info->mem) == BLKmode 1551 && s_info->const_rhs == const_rhs) 1552 redundant_reason = ptr; 1553 } 1554 else if (s_info->const_rhs == const0_rtx 1555 && const_rhs == const0_rtx) 1556 redundant_reason = ptr; 1557 else 1558 { 1559 rtx val; 1560 start_sequence (); 1561 val = get_stored_val (s_info, GET_MODE (mem), 1562 offset, offset + width, 1563 BLOCK_FOR_INSN (insn_info->insn), 1564 true); 1565 if (get_insns () != NULL) 1566 val = NULL_RTX; 1567 end_sequence (); 1568 if (val && rtx_equal_p (val, const_rhs)) 1569 redundant_reason = ptr; 1570 } 1571 } 1572 1573 for (i = MAX (offset, s_info->begin); 1574 i < offset + width && i < s_info->end; 1575 i++) 1576 set_position_unneeded (s_info, i - s_info->begin); 1577 } 1578 else if (s_info->rhs) 1579 /* Need to see if it is possible for this store to overwrite 1580 the value of store_info. If it is, set the rhs to NULL to 1581 keep it from being used to remove a load. */ 1582 { 1583 if (canon_true_dependence (s_info->mem, 1584 GET_MODE (s_info->mem), 1585 s_info->mem_addr, 1586 mem, mem_addr, rtx_varies_p)) 1587 { 1588 s_info->rhs = NULL; 1589 s_info->const_rhs = NULL; 1590 } 1591 } 1592 1593 /* An insn can be deleted if every position of every one of 1594 its s_infos is zero. */ 1595 if (any_positions_needed_p (s_info)) 1596 del = false; 1597 1598 if (del) 1599 { 1600 insn_info_t insn_to_delete = ptr; 1601 1602 if (last) 1603 last->next_local_store = ptr->next_local_store; 1604 else 1605 active_local_stores = ptr->next_local_store; 1606 1607 if (!insn_to_delete->cannot_delete) 1608 delete_dead_store_insn (insn_to_delete); 1609 } 1610 else 1611 last = ptr; 1612 1613 ptr = next; 1614 } 1615 1616 /* Finish filling in the store_info. */ 1617 store_info->next = insn_info->store_rec; 1618 insn_info->store_rec = store_info; 1619 store_info->mem = mem; 1620 store_info->alias_set = spill_alias_set; 1621 store_info->mem_addr = mem_addr; 1622 store_info->cse_base = base; 1623 if (width > HOST_BITS_PER_WIDE_INT) 1624 { 1625 store_info->is_large = true; 1626 store_info->positions_needed.large.count = 0; 1627 store_info->positions_needed.large.bmap = BITMAP_ALLOC (NULL); 1628 } 1629 else 1630 { 1631 store_info->is_large = false; 1632 store_info->positions_needed.small_bitmask = lowpart_bitmask (width); 1633 } 1634 store_info->group_id = group_id; 1635 store_info->begin = offset; 1636 store_info->end = offset + width; 1637 store_info->is_set = GET_CODE (body) == SET; 1638 store_info->rhs = rhs; 1639 store_info->const_rhs = const_rhs; 1640 store_info->redundant_reason = redundant_reason; 1641 1642 /* If this is a clobber, we return 0. We will only be able to 1643 delete this insn if there is only one store USED store, but we 1644 can use the clobber to delete other stores earlier. */ 1645 return store_info->is_set ? 1 : 0; 1646 } 1647 1648 1649 static void 1650 dump_insn_info (const char * start, insn_info_t insn_info) 1651 { 1652 fprintf (dump_file, "%s insn=%d %s\n", start, 1653 INSN_UID (insn_info->insn), 1654 insn_info->store_rec ? "has store" : "naked"); 1655 } 1656 1657 1658 /* If the modes are different and the value's source and target do not 1659 line up, we need to extract the value from lower part of the rhs of 1660 the store, shift it, and then put it into a form that can be shoved 1661 into the read_insn. This function generates a right SHIFT of a 1662 value that is at least ACCESS_SIZE bytes wide of READ_MODE. The 1663 shift sequence is returned or NULL if we failed to find a 1664 shift. */ 1665 1666 static rtx 1667 find_shift_sequence (int access_size, 1668 store_info_t store_info, 1669 enum machine_mode read_mode, 1670 int shift, bool speed, bool require_cst) 1671 { 1672 enum machine_mode store_mode = GET_MODE (store_info->mem); 1673 enum machine_mode new_mode; 1674 rtx read_reg = NULL; 1675 1676 /* Some machines like the x86 have shift insns for each size of 1677 operand. Other machines like the ppc or the ia-64 may only have 1678 shift insns that shift values within 32 or 64 bit registers. 1679 This loop tries to find the smallest shift insn that will right 1680 justify the value we want to read but is available in one insn on 1681 the machine. */ 1682 1683 for (new_mode = smallest_mode_for_size (access_size * BITS_PER_UNIT, 1684 MODE_INT); 1685 GET_MODE_BITSIZE (new_mode) <= BITS_PER_WORD; 1686 new_mode = GET_MODE_WIDER_MODE (new_mode)) 1687 { 1688 rtx target, new_reg, shift_seq, insn, new_lhs; 1689 int cost; 1690 1691 /* If a constant was stored into memory, try to simplify it here, 1692 otherwise the cost of the shift might preclude this optimization 1693 e.g. at -Os, even when no actual shift will be needed. */ 1694 if (store_info->const_rhs) 1695 { 1696 unsigned int byte = subreg_lowpart_offset (new_mode, store_mode); 1697 rtx ret = simplify_subreg (new_mode, store_info->const_rhs, 1698 store_mode, byte); 1699 if (ret && CONSTANT_P (ret)) 1700 { 1701 ret = simplify_const_binary_operation (LSHIFTRT, new_mode, 1702 ret, GEN_INT (shift)); 1703 if (ret && CONSTANT_P (ret)) 1704 { 1705 byte = subreg_lowpart_offset (read_mode, new_mode); 1706 ret = simplify_subreg (read_mode, ret, new_mode, byte); 1707 if (ret && CONSTANT_P (ret) 1708 && rtx_cost (ret, SET, speed) <= COSTS_N_INSNS (1)) 1709 return ret; 1710 } 1711 } 1712 } 1713 1714 if (require_cst) 1715 return NULL_RTX; 1716 1717 /* Try a wider mode if truncating the store mode to NEW_MODE 1718 requires a real instruction. */ 1719 if (GET_MODE_BITSIZE (new_mode) < GET_MODE_BITSIZE (store_mode) 1720 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (new_mode), 1721 GET_MODE_BITSIZE (store_mode))) 1722 continue; 1723 1724 /* Also try a wider mode if the necessary punning is either not 1725 desirable or not possible. */ 1726 if (!CONSTANT_P (store_info->rhs) 1727 && !MODES_TIEABLE_P (new_mode, store_mode)) 1728 continue; 1729 1730 new_reg = gen_reg_rtx (new_mode); 1731 1732 start_sequence (); 1733 1734 /* In theory we could also check for an ashr. Ian Taylor knows 1735 of one dsp where the cost of these two was not the same. But 1736 this really is a rare case anyway. */ 1737 target = expand_binop (new_mode, lshr_optab, new_reg, 1738 GEN_INT (shift), new_reg, 1, OPTAB_DIRECT); 1739 1740 shift_seq = get_insns (); 1741 end_sequence (); 1742 1743 if (target != new_reg || shift_seq == NULL) 1744 continue; 1745 1746 cost = 0; 1747 for (insn = shift_seq; insn != NULL_RTX; insn = NEXT_INSN (insn)) 1748 if (INSN_P (insn)) 1749 cost += insn_rtx_cost (PATTERN (insn), speed); 1750 1751 /* The computation up to here is essentially independent 1752 of the arguments and could be precomputed. It may 1753 not be worth doing so. We could precompute if 1754 worthwhile or at least cache the results. The result 1755 technically depends on both SHIFT and ACCESS_SIZE, 1756 but in practice the answer will depend only on ACCESS_SIZE. */ 1757 1758 if (cost > COSTS_N_INSNS (1)) 1759 continue; 1760 1761 new_lhs = extract_low_bits (new_mode, store_mode, 1762 copy_rtx (store_info->rhs)); 1763 if (new_lhs == NULL_RTX) 1764 continue; 1765 1766 /* We found an acceptable shift. Generate a move to 1767 take the value from the store and put it into the 1768 shift pseudo, then shift it, then generate another 1769 move to put in into the target of the read. */ 1770 emit_move_insn (new_reg, new_lhs); 1771 emit_insn (shift_seq); 1772 read_reg = extract_low_bits (read_mode, new_mode, new_reg); 1773 break; 1774 } 1775 1776 return read_reg; 1777 } 1778 1779 1780 /* Call back for note_stores to find the hard regs set or clobbered by 1781 insn. Data is a bitmap of the hardregs set so far. */ 1782 1783 static void 1784 look_for_hardregs (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data) 1785 { 1786 bitmap regs_set = (bitmap) data; 1787 1788 if (REG_P (x) 1789 && REGNO (x) < FIRST_PSEUDO_REGISTER) 1790 { 1791 int regno = REGNO (x); 1792 int n = hard_regno_nregs[regno][GET_MODE (x)]; 1793 while (--n >= 0) 1794 bitmap_set_bit (regs_set, regno + n); 1795 } 1796 } 1797 1798 /* Helper function for replace_read and record_store. 1799 Attempt to return a value stored in STORE_INFO, from READ_BEGIN 1800 to one before READ_END bytes read in READ_MODE. Return NULL 1801 if not successful. If REQUIRE_CST is true, return always constant. */ 1802 1803 static rtx 1804 get_stored_val (store_info_t store_info, enum machine_mode read_mode, 1805 HOST_WIDE_INT read_begin, HOST_WIDE_INT read_end, 1806 basic_block bb, bool require_cst) 1807 { 1808 enum machine_mode store_mode = GET_MODE (store_info->mem); 1809 int shift; 1810 int access_size; /* In bytes. */ 1811 rtx read_reg; 1812 1813 /* To get here the read is within the boundaries of the write so 1814 shift will never be negative. Start out with the shift being in 1815 bytes. */ 1816 if (store_mode == BLKmode) 1817 shift = 0; 1818 else if (BYTES_BIG_ENDIAN) 1819 shift = store_info->end - read_end; 1820 else 1821 shift = read_begin - store_info->begin; 1822 1823 access_size = shift + GET_MODE_SIZE (read_mode); 1824 1825 /* From now on it is bits. */ 1826 shift *= BITS_PER_UNIT; 1827 1828 if (shift) 1829 read_reg = find_shift_sequence (access_size, store_info, read_mode, shift, 1830 optimize_bb_for_speed_p (bb), 1831 require_cst); 1832 else if (store_mode == BLKmode) 1833 { 1834 /* The store is a memset (addr, const_val, const_size). */ 1835 gcc_assert (CONST_INT_P (store_info->rhs)); 1836 store_mode = int_mode_for_mode (read_mode); 1837 if (store_mode == BLKmode) 1838 read_reg = NULL_RTX; 1839 else if (store_info->rhs == const0_rtx) 1840 read_reg = extract_low_bits (read_mode, store_mode, const0_rtx); 1841 else if (GET_MODE_BITSIZE (store_mode) > HOST_BITS_PER_WIDE_INT 1842 || BITS_PER_UNIT >= HOST_BITS_PER_WIDE_INT) 1843 read_reg = NULL_RTX; 1844 else 1845 { 1846 unsigned HOST_WIDE_INT c 1847 = INTVAL (store_info->rhs) 1848 & (((HOST_WIDE_INT) 1 << BITS_PER_UNIT) - 1); 1849 int shift = BITS_PER_UNIT; 1850 while (shift < HOST_BITS_PER_WIDE_INT) 1851 { 1852 c |= (c << shift); 1853 shift <<= 1; 1854 } 1855 read_reg = GEN_INT (trunc_int_for_mode (c, store_mode)); 1856 read_reg = extract_low_bits (read_mode, store_mode, read_reg); 1857 } 1858 } 1859 else if (store_info->const_rhs 1860 && (require_cst 1861 || GET_MODE_CLASS (read_mode) != GET_MODE_CLASS (store_mode))) 1862 read_reg = extract_low_bits (read_mode, store_mode, 1863 copy_rtx (store_info->const_rhs)); 1864 else 1865 read_reg = extract_low_bits (read_mode, store_mode, 1866 copy_rtx (store_info->rhs)); 1867 if (require_cst && read_reg && !CONSTANT_P (read_reg)) 1868 read_reg = NULL_RTX; 1869 return read_reg; 1870 } 1871 1872 /* Take a sequence of: 1873 A <- r1 1874 ... 1875 ... <- A 1876 1877 and change it into 1878 r2 <- r1 1879 A <- r1 1880 ... 1881 ... <- r2 1882 1883 or 1884 1885 r3 <- extract (r1) 1886 r3 <- r3 >> shift 1887 r2 <- extract (r3) 1888 ... <- r2 1889 1890 or 1891 1892 r2 <- extract (r1) 1893 ... <- r2 1894 1895 Depending on the alignment and the mode of the store and 1896 subsequent load. 1897 1898 1899 The STORE_INFO and STORE_INSN are for the store and READ_INFO 1900 and READ_INSN are for the read. Return true if the replacement 1901 went ok. */ 1902 1903 static bool 1904 replace_read (store_info_t store_info, insn_info_t store_insn, 1905 read_info_t read_info, insn_info_t read_insn, rtx *loc, 1906 bitmap regs_live) 1907 { 1908 enum machine_mode store_mode = GET_MODE (store_info->mem); 1909 enum machine_mode read_mode = GET_MODE (read_info->mem); 1910 rtx insns, this_insn, read_reg; 1911 basic_block bb; 1912 1913 if (!dbg_cnt (dse)) 1914 return false; 1915 1916 /* Create a sequence of instructions to set up the read register. 1917 This sequence goes immediately before the store and its result 1918 is read by the load. 1919 1920 We need to keep this in perspective. We are replacing a read 1921 with a sequence of insns, but the read will almost certainly be 1922 in cache, so it is not going to be an expensive one. Thus, we 1923 are not willing to do a multi insn shift or worse a subroutine 1924 call to get rid of the read. */ 1925 if (dump_file) 1926 fprintf (dump_file, "trying to replace %smode load in insn %d" 1927 " from %smode store in insn %d\n", 1928 GET_MODE_NAME (read_mode), INSN_UID (read_insn->insn), 1929 GET_MODE_NAME (store_mode), INSN_UID (store_insn->insn)); 1930 start_sequence (); 1931 bb = BLOCK_FOR_INSN (read_insn->insn); 1932 read_reg = get_stored_val (store_info, 1933 read_mode, read_info->begin, read_info->end, 1934 bb, false); 1935 if (read_reg == NULL_RTX) 1936 { 1937 end_sequence (); 1938 if (dump_file) 1939 fprintf (dump_file, " -- could not extract bits of stored value\n"); 1940 return false; 1941 } 1942 /* Force the value into a new register so that it won't be clobbered 1943 between the store and the load. */ 1944 read_reg = copy_to_mode_reg (read_mode, read_reg); 1945 insns = get_insns (); 1946 end_sequence (); 1947 1948 if (insns != NULL_RTX) 1949 { 1950 /* Now we have to scan the set of new instructions to see if the 1951 sequence contains and sets of hardregs that happened to be 1952 live at this point. For instance, this can happen if one of 1953 the insns sets the CC and the CC happened to be live at that 1954 point. This does occasionally happen, see PR 37922. */ 1955 bitmap regs_set = BITMAP_ALLOC (NULL); 1956 1957 for (this_insn = insns; this_insn != NULL_RTX; this_insn = NEXT_INSN (this_insn)) 1958 note_stores (PATTERN (this_insn), look_for_hardregs, regs_set); 1959 1960 bitmap_and_into (regs_set, regs_live); 1961 if (!bitmap_empty_p (regs_set)) 1962 { 1963 if (dump_file) 1964 { 1965 fprintf (dump_file, 1966 "abandoning replacement because sequence clobbers live hardregs:"); 1967 df_print_regset (dump_file, regs_set); 1968 } 1969 1970 BITMAP_FREE (regs_set); 1971 return false; 1972 } 1973 BITMAP_FREE (regs_set); 1974 } 1975 1976 if (validate_change (read_insn->insn, loc, read_reg, 0)) 1977 { 1978 deferred_change_t deferred_change = 1979 (deferred_change_t) pool_alloc (deferred_change_pool); 1980 1981 /* Insert this right before the store insn where it will be safe 1982 from later insns that might change it before the read. */ 1983 emit_insn_before (insns, store_insn->insn); 1984 1985 /* And now for the kludge part: cselib croaks if you just 1986 return at this point. There are two reasons for this: 1987 1988 1) Cselib has an idea of how many pseudos there are and 1989 that does not include the new ones we just added. 1990 1991 2) Cselib does not know about the move insn we added 1992 above the store_info, and there is no way to tell it 1993 about it, because it has "moved on". 1994 1995 Problem (1) is fixable with a certain amount of engineering. 1996 Problem (2) is requires starting the bb from scratch. This 1997 could be expensive. 1998 1999 So we are just going to have to lie. The move/extraction 2000 insns are not really an issue, cselib did not see them. But 2001 the use of the new pseudo read_insn is a real problem because 2002 cselib has not scanned this insn. The way that we solve this 2003 problem is that we are just going to put the mem back for now 2004 and when we are finished with the block, we undo this. We 2005 keep a table of mems to get rid of. At the end of the basic 2006 block we can put them back. */ 2007 2008 *loc = read_info->mem; 2009 deferred_change->next = deferred_change_list; 2010 deferred_change_list = deferred_change; 2011 deferred_change->loc = loc; 2012 deferred_change->reg = read_reg; 2013 2014 /* Get rid of the read_info, from the point of view of the 2015 rest of dse, play like this read never happened. */ 2016 read_insn->read_rec = read_info->next; 2017 pool_free (read_info_pool, read_info); 2018 if (dump_file) 2019 { 2020 fprintf (dump_file, " -- replaced the loaded MEM with "); 2021 print_simple_rtl (dump_file, read_reg); 2022 fprintf (dump_file, "\n"); 2023 } 2024 return true; 2025 } 2026 else 2027 { 2028 if (dump_file) 2029 { 2030 fprintf (dump_file, " -- replacing the loaded MEM with "); 2031 print_simple_rtl (dump_file, read_reg); 2032 fprintf (dump_file, " led to an invalid instruction\n"); 2033 } 2034 return false; 2035 } 2036 } 2037 2038 /* A for_each_rtx callback in which DATA is the bb_info. Check to see 2039 if LOC is a mem and if it is look at the address and kill any 2040 appropriate stores that may be active. */ 2041 2042 static int 2043 check_mem_read_rtx (rtx *loc, void *data) 2044 { 2045 rtx mem = *loc, mem_addr; 2046 bb_info_t bb_info; 2047 insn_info_t insn_info; 2048 HOST_WIDE_INT offset = 0; 2049 HOST_WIDE_INT width = 0; 2050 alias_set_type spill_alias_set = 0; 2051 cselib_val *base = NULL; 2052 int group_id; 2053 read_info_t read_info; 2054 2055 if (!mem || !MEM_P (mem)) 2056 return 0; 2057 2058 bb_info = (bb_info_t) data; 2059 insn_info = bb_info->last_insn; 2060 2061 if ((MEM_ALIAS_SET (mem) == ALIAS_SET_MEMORY_BARRIER) 2062 || (MEM_VOLATILE_P (mem))) 2063 { 2064 if (dump_file) 2065 fprintf (dump_file, " adding wild read, volatile or barrier.\n"); 2066 add_wild_read (bb_info); 2067 insn_info->cannot_delete = true; 2068 return 0; 2069 } 2070 2071 /* If it is reading readonly mem, then there can be no conflict with 2072 another write. */ 2073 if (MEM_READONLY_P (mem)) 2074 return 0; 2075 2076 if (!canon_address (mem, &spill_alias_set, &group_id, &offset, &base)) 2077 { 2078 if (dump_file) 2079 fprintf (dump_file, " adding wild read, canon_address failure.\n"); 2080 add_wild_read (bb_info); 2081 return 0; 2082 } 2083 2084 if (GET_MODE (mem) == BLKmode) 2085 width = -1; 2086 else 2087 width = GET_MODE_SIZE (GET_MODE (mem)); 2088 2089 read_info = (read_info_t) pool_alloc (read_info_pool); 2090 read_info->group_id = group_id; 2091 read_info->mem = mem; 2092 read_info->alias_set = spill_alias_set; 2093 read_info->begin = offset; 2094 read_info->end = offset + width; 2095 read_info->next = insn_info->read_rec; 2096 insn_info->read_rec = read_info; 2097 /* For alias_set != 0 canon_true_dependence should be never called. */ 2098 if (spill_alias_set) 2099 mem_addr = NULL_RTX; 2100 else 2101 { 2102 if (group_id < 0) 2103 mem_addr = base->val_rtx; 2104 else 2105 { 2106 group_info_t group 2107 = VEC_index (group_info_t, rtx_group_vec, group_id); 2108 mem_addr = group->canon_base_addr; 2109 } 2110 if (offset) 2111 mem_addr = plus_constant (mem_addr, offset); 2112 } 2113 2114 /* We ignore the clobbers in store_info. The is mildly aggressive, 2115 but there really should not be a clobber followed by a read. */ 2116 2117 if (spill_alias_set) 2118 { 2119 insn_info_t i_ptr = active_local_stores; 2120 insn_info_t last = NULL; 2121 2122 if (dump_file) 2123 fprintf (dump_file, " processing spill load %d\n", 2124 (int) spill_alias_set); 2125 2126 while (i_ptr) 2127 { 2128 store_info_t store_info = i_ptr->store_rec; 2129 2130 /* Skip the clobbers. */ 2131 while (!store_info->is_set) 2132 store_info = store_info->next; 2133 2134 if (store_info->alias_set == spill_alias_set) 2135 { 2136 if (dump_file) 2137 dump_insn_info ("removing from active", i_ptr); 2138 2139 if (last) 2140 last->next_local_store = i_ptr->next_local_store; 2141 else 2142 active_local_stores = i_ptr->next_local_store; 2143 } 2144 else 2145 last = i_ptr; 2146 i_ptr = i_ptr->next_local_store; 2147 } 2148 } 2149 else if (group_id >= 0) 2150 { 2151 /* This is the restricted case where the base is a constant or 2152 the frame pointer and offset is a constant. */ 2153 insn_info_t i_ptr = active_local_stores; 2154 insn_info_t last = NULL; 2155 2156 if (dump_file) 2157 { 2158 if (width == -1) 2159 fprintf (dump_file, " processing const load gid=%d[BLK]\n", 2160 group_id); 2161 else 2162 fprintf (dump_file, " processing const load gid=%d[%d..%d)\n", 2163 group_id, (int)offset, (int)(offset+width)); 2164 } 2165 2166 while (i_ptr) 2167 { 2168 bool remove = false; 2169 store_info_t store_info = i_ptr->store_rec; 2170 2171 /* Skip the clobbers. */ 2172 while (!store_info->is_set) 2173 store_info = store_info->next; 2174 2175 /* There are three cases here. */ 2176 if (store_info->group_id < 0) 2177 /* We have a cselib store followed by a read from a 2178 const base. */ 2179 remove 2180 = canon_true_dependence (store_info->mem, 2181 GET_MODE (store_info->mem), 2182 store_info->mem_addr, 2183 mem, mem_addr, rtx_varies_p); 2184 2185 else if (group_id == store_info->group_id) 2186 { 2187 /* This is a block mode load. We may get lucky and 2188 canon_true_dependence may save the day. */ 2189 if (width == -1) 2190 remove 2191 = canon_true_dependence (store_info->mem, 2192 GET_MODE (store_info->mem), 2193 store_info->mem_addr, 2194 mem, mem_addr, rtx_varies_p); 2195 2196 /* If this read is just reading back something that we just 2197 stored, rewrite the read. */ 2198 else 2199 { 2200 if (store_info->rhs 2201 && offset >= store_info->begin 2202 && offset + width <= store_info->end 2203 && all_positions_needed_p (store_info, 2204 offset - store_info->begin, 2205 width) 2206 && replace_read (store_info, i_ptr, read_info, 2207 insn_info, loc, bb_info->regs_live)) 2208 return 0; 2209 2210 /* The bases are the same, just see if the offsets 2211 overlap. */ 2212 if ((offset < store_info->end) 2213 && (offset + width > store_info->begin)) 2214 remove = true; 2215 } 2216 } 2217 2218 /* else 2219 The else case that is missing here is that the 2220 bases are constant but different. There is nothing 2221 to do here because there is no overlap. */ 2222 2223 if (remove) 2224 { 2225 if (dump_file) 2226 dump_insn_info ("removing from active", i_ptr); 2227 2228 if (last) 2229 last->next_local_store = i_ptr->next_local_store; 2230 else 2231 active_local_stores = i_ptr->next_local_store; 2232 } 2233 else 2234 last = i_ptr; 2235 i_ptr = i_ptr->next_local_store; 2236 } 2237 } 2238 else 2239 { 2240 insn_info_t i_ptr = active_local_stores; 2241 insn_info_t last = NULL; 2242 if (dump_file) 2243 { 2244 fprintf (dump_file, " processing cselib load mem:"); 2245 print_inline_rtx (dump_file, mem, 0); 2246 fprintf (dump_file, "\n"); 2247 } 2248 2249 while (i_ptr) 2250 { 2251 bool remove = false; 2252 store_info_t store_info = i_ptr->store_rec; 2253 2254 if (dump_file) 2255 fprintf (dump_file, " processing cselib load against insn %d\n", 2256 INSN_UID (i_ptr->insn)); 2257 2258 /* Skip the clobbers. */ 2259 while (!store_info->is_set) 2260 store_info = store_info->next; 2261 2262 /* If this read is just reading back something that we just 2263 stored, rewrite the read. */ 2264 if (store_info->rhs 2265 && store_info->group_id == -1 2266 && store_info->cse_base == base 2267 && width != -1 2268 && offset >= store_info->begin 2269 && offset + width <= store_info->end 2270 && all_positions_needed_p (store_info, 2271 offset - store_info->begin, width) 2272 && replace_read (store_info, i_ptr, read_info, insn_info, loc, 2273 bb_info->regs_live)) 2274 return 0; 2275 2276 if (!store_info->alias_set) 2277 remove = canon_true_dependence (store_info->mem, 2278 GET_MODE (store_info->mem), 2279 store_info->mem_addr, 2280 mem, mem_addr, rtx_varies_p); 2281 2282 if (remove) 2283 { 2284 if (dump_file) 2285 dump_insn_info ("removing from active", i_ptr); 2286 2287 if (last) 2288 last->next_local_store = i_ptr->next_local_store; 2289 else 2290 active_local_stores = i_ptr->next_local_store; 2291 } 2292 else 2293 last = i_ptr; 2294 i_ptr = i_ptr->next_local_store; 2295 } 2296 } 2297 return 0; 2298 } 2299 2300 /* A for_each_rtx callback in which DATA points the INSN_INFO for 2301 as check_mem_read_rtx. Nullify the pointer if i_m_r_m_r returns 2302 true for any part of *LOC. */ 2303 2304 static void 2305 check_mem_read_use (rtx *loc, void *data) 2306 { 2307 for_each_rtx (loc, check_mem_read_rtx, data); 2308 } 2309 2310 2311 /* Get arguments passed to CALL_INSN. Return TRUE if successful. 2312 So far it only handles arguments passed in registers. */ 2313 2314 static bool 2315 get_call_args (rtx call_insn, tree fn, rtx *args, int nargs) 2316 { 2317 CUMULATIVE_ARGS args_so_far; 2318 tree arg; 2319 int idx; 2320 2321 INIT_CUMULATIVE_ARGS (args_so_far, TREE_TYPE (fn), NULL_RTX, 0, 3); 2322 2323 arg = TYPE_ARG_TYPES (TREE_TYPE (fn)); 2324 for (idx = 0; 2325 arg != void_list_node && idx < nargs; 2326 arg = TREE_CHAIN (arg), idx++) 2327 { 2328 enum machine_mode mode = TYPE_MODE (TREE_VALUE (arg)); 2329 rtx reg = FUNCTION_ARG (args_so_far, mode, NULL_TREE, 1), link, tmp; 2330 if (!reg || !REG_P (reg) || GET_MODE (reg) != mode 2331 || GET_MODE_CLASS (mode) != MODE_INT) 2332 return false; 2333 2334 for (link = CALL_INSN_FUNCTION_USAGE (call_insn); 2335 link; 2336 link = XEXP (link, 1)) 2337 if (GET_CODE (XEXP (link, 0)) == USE) 2338 { 2339 args[idx] = XEXP (XEXP (link, 0), 0); 2340 if (REG_P (args[idx]) 2341 && REGNO (args[idx]) == REGNO (reg) 2342 && (GET_MODE (args[idx]) == mode 2343 || (GET_MODE_CLASS (GET_MODE (args[idx])) == MODE_INT 2344 && (GET_MODE_SIZE (GET_MODE (args[idx])) 2345 <= UNITS_PER_WORD) 2346 && (GET_MODE_SIZE (GET_MODE (args[idx])) 2347 > GET_MODE_SIZE (mode))))) 2348 break; 2349 } 2350 if (!link) 2351 return false; 2352 2353 tmp = cselib_expand_value_rtx (args[idx], scratch, 5); 2354 if (GET_MODE (args[idx]) != mode) 2355 { 2356 if (!tmp || !CONST_INT_P (tmp)) 2357 return false; 2358 tmp = GEN_INT (trunc_int_for_mode (INTVAL (tmp), mode)); 2359 } 2360 if (tmp) 2361 args[idx] = tmp; 2362 2363 FUNCTION_ARG_ADVANCE (args_so_far, mode, NULL_TREE, 1); 2364 } 2365 if (arg != void_list_node || idx != nargs) 2366 return false; 2367 return true; 2368 } 2369 2370 2371 /* Apply record_store to all candidate stores in INSN. Mark INSN 2372 if some part of it is not a candidate store and assigns to a 2373 non-register target. */ 2374 2375 static void 2376 scan_insn (bb_info_t bb_info, rtx insn) 2377 { 2378 rtx body; 2379 insn_info_t insn_info = (insn_info_t) pool_alloc (insn_info_pool); 2380 int mems_found = 0; 2381 memset (insn_info, 0, sizeof (struct insn_info)); 2382 2383 if (dump_file) 2384 fprintf (dump_file, "\n**scanning insn=%d\n", 2385 INSN_UID (insn)); 2386 2387 insn_info->prev_insn = bb_info->last_insn; 2388 insn_info->insn = insn; 2389 bb_info->last_insn = insn_info; 2390 2391 if (DEBUG_INSN_P (insn)) 2392 { 2393 insn_info->cannot_delete = true; 2394 return; 2395 } 2396 2397 /* Cselib clears the table for this case, so we have to essentially 2398 do the same. */ 2399 if (NONJUMP_INSN_P (insn) 2400 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS 2401 && MEM_VOLATILE_P (PATTERN (insn))) 2402 { 2403 add_wild_read (bb_info); 2404 insn_info->cannot_delete = true; 2405 return; 2406 } 2407 2408 /* Look at all of the uses in the insn. */ 2409 note_uses (&PATTERN (insn), check_mem_read_use, bb_info); 2410 2411 if (CALL_P (insn)) 2412 { 2413 bool const_call; 2414 tree memset_call = NULL_TREE; 2415 2416 insn_info->cannot_delete = true; 2417 2418 /* Const functions cannot do anything bad i.e. read memory, 2419 however, they can read their parameters which may have 2420 been pushed onto the stack. 2421 memset and bzero don't read memory either. */ 2422 const_call = RTL_CONST_CALL_P (insn); 2423 if (!const_call) 2424 { 2425 rtx call = PATTERN (insn); 2426 if (GET_CODE (call) == PARALLEL) 2427 call = XVECEXP (call, 0, 0); 2428 if (GET_CODE (call) == SET) 2429 call = SET_SRC (call); 2430 if (GET_CODE (call) == CALL 2431 && MEM_P (XEXP (call, 0)) 2432 && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF) 2433 { 2434 rtx symbol = XEXP (XEXP (call, 0), 0); 2435 if (SYMBOL_REF_DECL (symbol) 2436 && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL) 2437 { 2438 if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol)) 2439 == BUILT_IN_NORMAL 2440 && (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol)) 2441 == BUILT_IN_MEMSET)) 2442 || SYMBOL_REF_DECL (symbol) == block_clear_fn) 2443 memset_call = SYMBOL_REF_DECL (symbol); 2444 } 2445 } 2446 } 2447 if (const_call || memset_call) 2448 { 2449 insn_info_t i_ptr = active_local_stores; 2450 insn_info_t last = NULL; 2451 2452 if (dump_file) 2453 fprintf (dump_file, "%s call %d\n", 2454 const_call ? "const" : "memset", INSN_UID (insn)); 2455 2456 /* See the head comment of the frame_read field. */ 2457 if (reload_completed) 2458 insn_info->frame_read = true; 2459 2460 /* Loop over the active stores and remove those which are 2461 killed by the const function call. */ 2462 while (i_ptr) 2463 { 2464 bool remove_store = false; 2465 2466 /* The stack pointer based stores are always killed. */ 2467 if (i_ptr->stack_pointer_based) 2468 remove_store = true; 2469 2470 /* If the frame is read, the frame related stores are killed. */ 2471 else if (insn_info->frame_read) 2472 { 2473 store_info_t store_info = i_ptr->store_rec; 2474 2475 /* Skip the clobbers. */ 2476 while (!store_info->is_set) 2477 store_info = store_info->next; 2478 2479 if (store_info->group_id >= 0 2480 && VEC_index (group_info_t, rtx_group_vec, 2481 store_info->group_id)->frame_related) 2482 remove_store = true; 2483 } 2484 2485 if (remove_store) 2486 { 2487 if (dump_file) 2488 dump_insn_info ("removing from active", i_ptr); 2489 2490 if (last) 2491 last->next_local_store = i_ptr->next_local_store; 2492 else 2493 active_local_stores = i_ptr->next_local_store; 2494 } 2495 else 2496 last = i_ptr; 2497 2498 i_ptr = i_ptr->next_local_store; 2499 } 2500 2501 if (memset_call) 2502 { 2503 rtx args[3]; 2504 if (get_call_args (insn, memset_call, args, 3) 2505 && CONST_INT_P (args[1]) 2506 && CONST_INT_P (args[2]) 2507 && INTVAL (args[2]) > 0) 2508 { 2509 rtx mem = gen_rtx_MEM (BLKmode, args[0]); 2510 set_mem_size (mem, args[2]); 2511 body = gen_rtx_SET (VOIDmode, mem, args[1]); 2512 mems_found += record_store (body, bb_info); 2513 if (dump_file) 2514 fprintf (dump_file, "handling memset as BLKmode store\n"); 2515 if (mems_found == 1) 2516 { 2517 insn_info->next_local_store = active_local_stores; 2518 active_local_stores = insn_info; 2519 } 2520 } 2521 } 2522 } 2523 2524 else 2525 /* Every other call, including pure functions, may read memory. */ 2526 add_wild_read (bb_info); 2527 2528 return; 2529 } 2530 2531 /* Assuming that there are sets in these insns, we cannot delete 2532 them. */ 2533 if ((GET_CODE (PATTERN (insn)) == CLOBBER) 2534 || volatile_refs_p (PATTERN (insn)) 2535 || insn_could_throw_p (insn) 2536 || (RTX_FRAME_RELATED_P (insn)) 2537 || find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX)) 2538 insn_info->cannot_delete = true; 2539 2540 body = PATTERN (insn); 2541 if (GET_CODE (body) == PARALLEL) 2542 { 2543 int i; 2544 for (i = 0; i < XVECLEN (body, 0); i++) 2545 mems_found += record_store (XVECEXP (body, 0, i), bb_info); 2546 } 2547 else 2548 mems_found += record_store (body, bb_info); 2549 2550 if (dump_file) 2551 fprintf (dump_file, "mems_found = %d, cannot_delete = %s\n", 2552 mems_found, insn_info->cannot_delete ? "true" : "false"); 2553 2554 /* If we found some sets of mems, add it into the active_local_stores so 2555 that it can be locally deleted if found dead or used for 2556 replace_read and redundant constant store elimination. Otherwise mark 2557 it as cannot delete. This simplifies the processing later. */ 2558 if (mems_found == 1) 2559 { 2560 insn_info->next_local_store = active_local_stores; 2561 active_local_stores = insn_info; 2562 } 2563 else 2564 insn_info->cannot_delete = true; 2565 } 2566 2567 2568 /* Remove BASE from the set of active_local_stores. This is a 2569 callback from cselib that is used to get rid of the stores in 2570 active_local_stores. */ 2571 2572 static void 2573 remove_useless_values (cselib_val *base) 2574 { 2575 insn_info_t insn_info = active_local_stores; 2576 insn_info_t last = NULL; 2577 2578 while (insn_info) 2579 { 2580 store_info_t store_info = insn_info->store_rec; 2581 bool del = false; 2582 2583 /* If ANY of the store_infos match the cselib group that is 2584 being deleted, then the insn can not be deleted. */ 2585 while (store_info) 2586 { 2587 if ((store_info->group_id == -1) 2588 && (store_info->cse_base == base)) 2589 { 2590 del = true; 2591 break; 2592 } 2593 store_info = store_info->next; 2594 } 2595 2596 if (del) 2597 { 2598 if (last) 2599 last->next_local_store = insn_info->next_local_store; 2600 else 2601 active_local_stores = insn_info->next_local_store; 2602 free_store_info (insn_info); 2603 } 2604 else 2605 last = insn_info; 2606 2607 insn_info = insn_info->next_local_store; 2608 } 2609 } 2610 2611 2612 /* Do all of step 1. */ 2613 2614 static void 2615 dse_step1 (void) 2616 { 2617 basic_block bb; 2618 bitmap regs_live = BITMAP_ALLOC (NULL); 2619 2620 cselib_init (0); 2621 all_blocks = BITMAP_ALLOC (NULL); 2622 bitmap_set_bit (all_blocks, ENTRY_BLOCK); 2623 bitmap_set_bit (all_blocks, EXIT_BLOCK); 2624 2625 FOR_ALL_BB (bb) 2626 { 2627 insn_info_t ptr; 2628 bb_info_t bb_info = (bb_info_t) pool_alloc (bb_info_pool); 2629 2630 memset (bb_info, 0, sizeof (struct bb_info)); 2631 bitmap_set_bit (all_blocks, bb->index); 2632 bb_info->regs_live = regs_live; 2633 2634 bitmap_copy (regs_live, DF_LR_IN (bb)); 2635 df_simulate_initialize_forwards (bb, regs_live); 2636 2637 bb_table[bb->index] = bb_info; 2638 cselib_discard_hook = remove_useless_values; 2639 2640 if (bb->index >= NUM_FIXED_BLOCKS) 2641 { 2642 rtx insn; 2643 2644 cse_store_info_pool 2645 = create_alloc_pool ("cse_store_info_pool", 2646 sizeof (struct store_info), 100); 2647 active_local_stores = NULL; 2648 cselib_clear_table (); 2649 2650 /* Scan the insns. */ 2651 FOR_BB_INSNS (bb, insn) 2652 { 2653 if (INSN_P (insn)) 2654 scan_insn (bb_info, insn); 2655 cselib_process_insn (insn); 2656 if (INSN_P (insn)) 2657 df_simulate_one_insn_forwards (bb, insn, regs_live); 2658 } 2659 2660 /* This is something of a hack, because the global algorithm 2661 is supposed to take care of the case where stores go dead 2662 at the end of the function. However, the global 2663 algorithm must take a more conservative view of block 2664 mode reads than the local alg does. So to get the case 2665 where you have a store to the frame followed by a non 2666 overlapping block more read, we look at the active local 2667 stores at the end of the function and delete all of the 2668 frame and spill based ones. */ 2669 if (stores_off_frame_dead_at_return 2670 && (EDGE_COUNT (bb->succs) == 0 2671 || (single_succ_p (bb) 2672 && single_succ (bb) == EXIT_BLOCK_PTR 2673 && ! crtl->calls_eh_return))) 2674 { 2675 insn_info_t i_ptr = active_local_stores; 2676 while (i_ptr) 2677 { 2678 store_info_t store_info = i_ptr->store_rec; 2679 2680 /* Skip the clobbers. */ 2681 while (!store_info->is_set) 2682 store_info = store_info->next; 2683 if (store_info->alias_set && !i_ptr->cannot_delete) 2684 delete_dead_store_insn (i_ptr); 2685 else 2686 if (store_info->group_id >= 0) 2687 { 2688 group_info_t group 2689 = VEC_index (group_info_t, rtx_group_vec, store_info->group_id); 2690 if (group->frame_related && !i_ptr->cannot_delete) 2691 delete_dead_store_insn (i_ptr); 2692 } 2693 2694 i_ptr = i_ptr->next_local_store; 2695 } 2696 } 2697 2698 /* Get rid of the loads that were discovered in 2699 replace_read. Cselib is finished with this block. */ 2700 while (deferred_change_list) 2701 { 2702 deferred_change_t next = deferred_change_list->next; 2703 2704 /* There is no reason to validate this change. That was 2705 done earlier. */ 2706 *deferred_change_list->loc = deferred_change_list->reg; 2707 pool_free (deferred_change_pool, deferred_change_list); 2708 deferred_change_list = next; 2709 } 2710 2711 /* Get rid of all of the cselib based store_infos in this 2712 block and mark the containing insns as not being 2713 deletable. */ 2714 ptr = bb_info->last_insn; 2715 while (ptr) 2716 { 2717 if (ptr->contains_cselib_groups) 2718 { 2719 store_info_t s_info = ptr->store_rec; 2720 while (s_info && !s_info->is_set) 2721 s_info = s_info->next; 2722 if (s_info 2723 && s_info->redundant_reason 2724 && s_info->redundant_reason->insn 2725 && !ptr->cannot_delete) 2726 { 2727 if (dump_file) 2728 fprintf (dump_file, "Locally deleting insn %d " 2729 "because insn %d stores the " 2730 "same value and couldn't be " 2731 "eliminated\n", 2732 INSN_UID (ptr->insn), 2733 INSN_UID (s_info->redundant_reason->insn)); 2734 delete_dead_store_insn (ptr); 2735 } 2736 if (s_info) 2737 s_info->redundant_reason = NULL; 2738 free_store_info (ptr); 2739 } 2740 else 2741 { 2742 store_info_t s_info; 2743 2744 /* Free at least positions_needed bitmaps. */ 2745 for (s_info = ptr->store_rec; s_info; s_info = s_info->next) 2746 if (s_info->is_large) 2747 { 2748 BITMAP_FREE (s_info->positions_needed.large.bmap); 2749 s_info->is_large = false; 2750 } 2751 } 2752 ptr = ptr->prev_insn; 2753 } 2754 2755 free_alloc_pool (cse_store_info_pool); 2756 } 2757 bb_info->regs_live = NULL; 2758 } 2759 2760 BITMAP_FREE (regs_live); 2761 cselib_finish (); 2762 htab_empty (rtx_group_table); 2763 } 2764 2765 2766 /*---------------------------------------------------------------------------- 2767 Second step. 2768 2769 Assign each byte position in the stores that we are going to 2770 analyze globally to a position in the bitmaps. Returns true if 2771 there are any bit positions assigned. 2772 ----------------------------------------------------------------------------*/ 2773 2774 static void 2775 dse_step2_init (void) 2776 { 2777 unsigned int i; 2778 group_info_t group; 2779 2780 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++) 2781 { 2782 /* For all non stack related bases, we only consider a store to 2783 be deletable if there are two or more stores for that 2784 position. This is because it takes one store to make the 2785 other store redundant. However, for the stores that are 2786 stack related, we consider them if there is only one store 2787 for the position. We do this because the stack related 2788 stores can be deleted if their is no read between them and 2789 the end of the function. 2790 2791 To make this work in the current framework, we take the stack 2792 related bases add all of the bits from store1 into store2. 2793 This has the effect of making the eligible even if there is 2794 only one store. */ 2795 2796 if (stores_off_frame_dead_at_return && group->frame_related) 2797 { 2798 bitmap_ior_into (group->store2_n, group->store1_n); 2799 bitmap_ior_into (group->store2_p, group->store1_p); 2800 if (dump_file) 2801 fprintf (dump_file, "group %d is frame related ", i); 2802 } 2803 2804 group->offset_map_size_n++; 2805 group->offset_map_n = XNEWVEC (int, group->offset_map_size_n); 2806 group->offset_map_size_p++; 2807 group->offset_map_p = XNEWVEC (int, group->offset_map_size_p); 2808 group->process_globally = false; 2809 if (dump_file) 2810 { 2811 fprintf (dump_file, "group %d(%d+%d): ", i, 2812 (int)bitmap_count_bits (group->store2_n), 2813 (int)bitmap_count_bits (group->store2_p)); 2814 bitmap_print (dump_file, group->store2_n, "n ", " "); 2815 bitmap_print (dump_file, group->store2_p, "p ", "\n"); 2816 } 2817 } 2818 } 2819 2820 2821 /* Init the offset tables for the normal case. */ 2822 2823 static bool 2824 dse_step2_nospill (void) 2825 { 2826 unsigned int i; 2827 group_info_t group; 2828 /* Position 0 is unused because 0 is used in the maps to mean 2829 unused. */ 2830 current_position = 1; 2831 2832 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++) 2833 { 2834 bitmap_iterator bi; 2835 unsigned int j; 2836 2837 if (group == clear_alias_group) 2838 continue; 2839 2840 memset (group->offset_map_n, 0, sizeof(int) * group->offset_map_size_n); 2841 memset (group->offset_map_p, 0, sizeof(int) * group->offset_map_size_p); 2842 bitmap_clear (group->group_kill); 2843 2844 EXECUTE_IF_SET_IN_BITMAP (group->store2_n, 0, j, bi) 2845 { 2846 bitmap_set_bit (group->group_kill, current_position); 2847 group->offset_map_n[j] = current_position++; 2848 group->process_globally = true; 2849 } 2850 EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi) 2851 { 2852 bitmap_set_bit (group->group_kill, current_position); 2853 group->offset_map_p[j] = current_position++; 2854 group->process_globally = true; 2855 } 2856 } 2857 return current_position != 1; 2858 } 2859 2860 2861 /* Init the offset tables for the spill case. */ 2862 2863 static bool 2864 dse_step2_spill (void) 2865 { 2866 unsigned int j; 2867 group_info_t group = clear_alias_group; 2868 bitmap_iterator bi; 2869 2870 /* Position 0 is unused because 0 is used in the maps to mean 2871 unused. */ 2872 current_position = 1; 2873 2874 if (dump_file) 2875 { 2876 bitmap_print (dump_file, clear_alias_sets, 2877 "clear alias sets ", "\n"); 2878 bitmap_print (dump_file, disqualified_clear_alias_sets, 2879 "disqualified clear alias sets ", "\n"); 2880 } 2881 2882 memset (group->offset_map_n, 0, sizeof(int) * group->offset_map_size_n); 2883 memset (group->offset_map_p, 0, sizeof(int) * group->offset_map_size_p); 2884 bitmap_clear (group->group_kill); 2885 2886 /* Remove the disqualified positions from the store2_p set. */ 2887 bitmap_and_compl_into (group->store2_p, disqualified_clear_alias_sets); 2888 2889 /* We do not need to process the store2_n set because 2890 alias_sets are always positive. */ 2891 EXECUTE_IF_SET_IN_BITMAP (group->store2_p, 0, j, bi) 2892 { 2893 bitmap_set_bit (group->group_kill, current_position); 2894 group->offset_map_p[j] = current_position++; 2895 group->process_globally = true; 2896 } 2897 2898 return current_position != 1; 2899 } 2900 2901 2902 2903 /*---------------------------------------------------------------------------- 2904 Third step. 2905 2906 Build the bit vectors for the transfer functions. 2907 ----------------------------------------------------------------------------*/ 2908 2909 2910 /* Note that this is NOT a general purpose function. Any mem that has 2911 an alias set registered here expected to be COMPLETELY unaliased: 2912 i.e it's addresses are not and need not be examined. 2913 2914 It is known that all references to this address will have this 2915 alias set and there are NO other references to this address in the 2916 function. 2917 2918 Currently the only place that is known to be clean enough to use 2919 this interface is the code that assigns the spill locations. 2920 2921 All of the mems that have alias_sets registered are subjected to a 2922 very powerful form of dse where function calls, volatile reads and 2923 writes, and reads from random location are not taken into account. 2924 2925 It is also assumed that these locations go dead when the function 2926 returns. This assumption could be relaxed if there were found to 2927 be places that this assumption was not correct. 2928 2929 The MODE is passed in and saved. The mode of each load or store to 2930 a mem with ALIAS_SET is checked against MEM. If the size of that 2931 load or store is different from MODE, processing is halted on this 2932 alias set. For the vast majority of aliases sets, all of the loads 2933 and stores will use the same mode. But vectors are treated 2934 differently: the alias set is established for the entire vector, 2935 but reload will insert loads and stores for individual elements and 2936 we do not necessarily have the information to track those separate 2937 elements. So when we see a mode mismatch, we just bail. */ 2938 2939 2940 void 2941 dse_record_singleton_alias_set (alias_set_type alias_set, 2942 enum machine_mode mode) 2943 { 2944 struct clear_alias_mode_holder tmp_holder; 2945 struct clear_alias_mode_holder *entry; 2946 void **slot; 2947 2948 /* If we are not going to run dse, we need to return now or there 2949 will be problems with allocating the bitmaps. */ 2950 if ((!gate_dse()) || !alias_set) 2951 return; 2952 2953 if (!clear_alias_sets) 2954 { 2955 clear_alias_sets = BITMAP_ALLOC (NULL); 2956 disqualified_clear_alias_sets = BITMAP_ALLOC (NULL); 2957 clear_alias_mode_table = htab_create (11, clear_alias_mode_hash, 2958 clear_alias_mode_eq, NULL); 2959 clear_alias_mode_pool = create_alloc_pool ("clear_alias_mode_pool", 2960 sizeof (struct clear_alias_mode_holder), 100); 2961 } 2962 2963 bitmap_set_bit (clear_alias_sets, alias_set); 2964 2965 tmp_holder.alias_set = alias_set; 2966 2967 slot = htab_find_slot (clear_alias_mode_table, &tmp_holder, INSERT); 2968 gcc_assert (*slot == NULL); 2969 2970 *slot = entry = 2971 (struct clear_alias_mode_holder *) pool_alloc (clear_alias_mode_pool); 2972 entry->alias_set = alias_set; 2973 entry->mode = mode; 2974 } 2975 2976 2977 /* Remove ALIAS_SET from the sets of stack slots being considered. */ 2978 2979 void 2980 dse_invalidate_singleton_alias_set (alias_set_type alias_set) 2981 { 2982 if ((!gate_dse()) || !alias_set) 2983 return; 2984 2985 bitmap_clear_bit (clear_alias_sets, alias_set); 2986 } 2987 2988 2989 /* Look up the bitmap index for OFFSET in GROUP_INFO. If it is not 2990 there, return 0. */ 2991 2992 static int 2993 get_bitmap_index (group_info_t group_info, HOST_WIDE_INT offset) 2994 { 2995 if (offset < 0) 2996 { 2997 HOST_WIDE_INT offset_p = -offset; 2998 if (offset_p >= group_info->offset_map_size_n) 2999 return 0; 3000 return group_info->offset_map_n[offset_p]; 3001 } 3002 else 3003 { 3004 if (offset >= group_info->offset_map_size_p) 3005 return 0; 3006 return group_info->offset_map_p[offset]; 3007 } 3008 } 3009 3010 3011 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL 3012 may be NULL. */ 3013 3014 static void 3015 scan_stores_nospill (store_info_t store_info, bitmap gen, bitmap kill) 3016 { 3017 while (store_info) 3018 { 3019 HOST_WIDE_INT i; 3020 group_info_t group_info 3021 = VEC_index (group_info_t, rtx_group_vec, store_info->group_id); 3022 if (group_info->process_globally) 3023 for (i = store_info->begin; i < store_info->end; i++) 3024 { 3025 int index = get_bitmap_index (group_info, i); 3026 if (index != 0) 3027 { 3028 bitmap_set_bit (gen, index); 3029 if (kill) 3030 bitmap_clear_bit (kill, index); 3031 } 3032 } 3033 store_info = store_info->next; 3034 } 3035 } 3036 3037 3038 /* Process the STORE_INFOs into the bitmaps into GEN and KILL. KILL 3039 may be NULL. */ 3040 3041 static void 3042 scan_stores_spill (store_info_t store_info, bitmap gen, bitmap kill) 3043 { 3044 while (store_info) 3045 { 3046 if (store_info->alias_set) 3047 { 3048 int index = get_bitmap_index (clear_alias_group, 3049 store_info->alias_set); 3050 if (index != 0) 3051 { 3052 bitmap_set_bit (gen, index); 3053 if (kill) 3054 bitmap_clear_bit (kill, index); 3055 } 3056 } 3057 store_info = store_info->next; 3058 } 3059 } 3060 3061 3062 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL 3063 may be NULL. */ 3064 3065 static void 3066 scan_reads_nospill (insn_info_t insn_info, bitmap gen, bitmap kill) 3067 { 3068 read_info_t read_info = insn_info->read_rec; 3069 int i; 3070 group_info_t group; 3071 3072 /* If this insn reads the frame, kill all the frame related stores. */ 3073 if (insn_info->frame_read) 3074 { 3075 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++) 3076 if (group->process_globally && group->frame_related) 3077 { 3078 if (kill) 3079 bitmap_ior_into (kill, group->group_kill); 3080 bitmap_and_compl_into (gen, group->group_kill); 3081 } 3082 } 3083 3084 while (read_info) 3085 { 3086 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++) 3087 { 3088 if (group->process_globally) 3089 { 3090 if (i == read_info->group_id) 3091 { 3092 if (read_info->begin > read_info->end) 3093 { 3094 /* Begin > end for block mode reads. */ 3095 if (kill) 3096 bitmap_ior_into (kill, group->group_kill); 3097 bitmap_and_compl_into (gen, group->group_kill); 3098 } 3099 else 3100 { 3101 /* The groups are the same, just process the 3102 offsets. */ 3103 HOST_WIDE_INT j; 3104 for (j = read_info->begin; j < read_info->end; j++) 3105 { 3106 int index = get_bitmap_index (group, j); 3107 if (index != 0) 3108 { 3109 if (kill) 3110 bitmap_set_bit (kill, index); 3111 bitmap_clear_bit (gen, index); 3112 } 3113 } 3114 } 3115 } 3116 else 3117 { 3118 /* The groups are different, if the alias sets 3119 conflict, clear the entire group. We only need 3120 to apply this test if the read_info is a cselib 3121 read. Anything with a constant base cannot alias 3122 something else with a different constant 3123 base. */ 3124 if ((read_info->group_id < 0) 3125 && canon_true_dependence (group->base_mem, 3126 QImode, 3127 group->canon_base_addr, 3128 read_info->mem, NULL_RTX, 3129 rtx_varies_p)) 3130 { 3131 if (kill) 3132 bitmap_ior_into (kill, group->group_kill); 3133 bitmap_and_compl_into (gen, group->group_kill); 3134 } 3135 } 3136 } 3137 } 3138 3139 read_info = read_info->next; 3140 } 3141 } 3142 3143 /* Process the READ_INFOs into the bitmaps into GEN and KILL. KILL 3144 may be NULL. */ 3145 3146 static void 3147 scan_reads_spill (read_info_t read_info, bitmap gen, bitmap kill) 3148 { 3149 while (read_info) 3150 { 3151 if (read_info->alias_set) 3152 { 3153 int index = get_bitmap_index (clear_alias_group, 3154 read_info->alias_set); 3155 if (index != 0) 3156 { 3157 if (kill) 3158 bitmap_set_bit (kill, index); 3159 bitmap_clear_bit (gen, index); 3160 } 3161 } 3162 3163 read_info = read_info->next; 3164 } 3165 } 3166 3167 3168 /* Return the insn in BB_INFO before the first wild read or if there 3169 are no wild reads in the block, return the last insn. */ 3170 3171 static insn_info_t 3172 find_insn_before_first_wild_read (bb_info_t bb_info) 3173 { 3174 insn_info_t insn_info = bb_info->last_insn; 3175 insn_info_t last_wild_read = NULL; 3176 3177 while (insn_info) 3178 { 3179 if (insn_info->wild_read) 3180 { 3181 last_wild_read = insn_info->prev_insn; 3182 /* Block starts with wild read. */ 3183 if (!last_wild_read) 3184 return NULL; 3185 } 3186 3187 insn_info = insn_info->prev_insn; 3188 } 3189 3190 if (last_wild_read) 3191 return last_wild_read; 3192 else 3193 return bb_info->last_insn; 3194 } 3195 3196 3197 /* Scan the insns in BB_INFO starting at PTR and going to the top of 3198 the block in order to build the gen and kill sets for the block. 3199 We start at ptr which may be the last insn in the block or may be 3200 the first insn with a wild read. In the latter case we are able to 3201 skip the rest of the block because it just does not matter: 3202 anything that happens is hidden by the wild read. */ 3203 3204 static void 3205 dse_step3_scan (bool for_spills, basic_block bb) 3206 { 3207 bb_info_t bb_info = bb_table[bb->index]; 3208 insn_info_t insn_info; 3209 3210 if (for_spills) 3211 /* There are no wild reads in the spill case. */ 3212 insn_info = bb_info->last_insn; 3213 else 3214 insn_info = find_insn_before_first_wild_read (bb_info); 3215 3216 /* In the spill case or in the no_spill case if there is no wild 3217 read in the block, we will need a kill set. */ 3218 if (insn_info == bb_info->last_insn) 3219 { 3220 if (bb_info->kill) 3221 bitmap_clear (bb_info->kill); 3222 else 3223 bb_info->kill = BITMAP_ALLOC (NULL); 3224 } 3225 else 3226 if (bb_info->kill) 3227 BITMAP_FREE (bb_info->kill); 3228 3229 while (insn_info) 3230 { 3231 /* There may have been code deleted by the dce pass run before 3232 this phase. */ 3233 if (insn_info->insn && INSN_P (insn_info->insn)) 3234 { 3235 /* Process the read(s) last. */ 3236 if (for_spills) 3237 { 3238 scan_stores_spill (insn_info->store_rec, bb_info->gen, bb_info->kill); 3239 scan_reads_spill (insn_info->read_rec, bb_info->gen, bb_info->kill); 3240 } 3241 else 3242 { 3243 scan_stores_nospill (insn_info->store_rec, bb_info->gen, bb_info->kill); 3244 scan_reads_nospill (insn_info, bb_info->gen, bb_info->kill); 3245 } 3246 } 3247 3248 insn_info = insn_info->prev_insn; 3249 } 3250 } 3251 3252 3253 /* Set the gen set of the exit block, and also any block with no 3254 successors that does not have a wild read. */ 3255 3256 static void 3257 dse_step3_exit_block_scan (bb_info_t bb_info) 3258 { 3259 /* The gen set is all 0's for the exit block except for the 3260 frame_pointer_group. */ 3261 3262 if (stores_off_frame_dead_at_return) 3263 { 3264 unsigned int i; 3265 group_info_t group; 3266 3267 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++) 3268 { 3269 if (group->process_globally && group->frame_related) 3270 bitmap_ior_into (bb_info->gen, group->group_kill); 3271 } 3272 } 3273 } 3274 3275 3276 /* Find all of the blocks that are not backwards reachable from the 3277 exit block or any block with no successors (BB). These are the 3278 infinite loops or infinite self loops. These blocks will still 3279 have their bits set in UNREACHABLE_BLOCKS. */ 3280 3281 static void 3282 mark_reachable_blocks (sbitmap unreachable_blocks, basic_block bb) 3283 { 3284 edge e; 3285 edge_iterator ei; 3286 3287 if (TEST_BIT (unreachable_blocks, bb->index)) 3288 { 3289 RESET_BIT (unreachable_blocks, bb->index); 3290 FOR_EACH_EDGE (e, ei, bb->preds) 3291 { 3292 mark_reachable_blocks (unreachable_blocks, e->src); 3293 } 3294 } 3295 } 3296 3297 /* Build the transfer functions for the function. */ 3298 3299 static void 3300 dse_step3 (bool for_spills) 3301 { 3302 basic_block bb; 3303 sbitmap unreachable_blocks = sbitmap_alloc (last_basic_block); 3304 sbitmap_iterator sbi; 3305 bitmap all_ones = NULL; 3306 unsigned int i; 3307 3308 sbitmap_ones (unreachable_blocks); 3309 3310 FOR_ALL_BB (bb) 3311 { 3312 bb_info_t bb_info = bb_table[bb->index]; 3313 if (bb_info->gen) 3314 bitmap_clear (bb_info->gen); 3315 else 3316 bb_info->gen = BITMAP_ALLOC (NULL); 3317 3318 if (bb->index == ENTRY_BLOCK) 3319 ; 3320 else if (bb->index == EXIT_BLOCK) 3321 dse_step3_exit_block_scan (bb_info); 3322 else 3323 dse_step3_scan (for_spills, bb); 3324 if (EDGE_COUNT (bb->succs) == 0) 3325 mark_reachable_blocks (unreachable_blocks, bb); 3326 3327 /* If this is the second time dataflow is run, delete the old 3328 sets. */ 3329 if (bb_info->in) 3330 BITMAP_FREE (bb_info->in); 3331 if (bb_info->out) 3332 BITMAP_FREE (bb_info->out); 3333 } 3334 3335 /* For any block in an infinite loop, we must initialize the out set 3336 to all ones. This could be expensive, but almost never occurs in 3337 practice. However, it is common in regression tests. */ 3338 EXECUTE_IF_SET_IN_SBITMAP (unreachable_blocks, 0, i, sbi) 3339 { 3340 if (bitmap_bit_p (all_blocks, i)) 3341 { 3342 bb_info_t bb_info = bb_table[i]; 3343 if (!all_ones) 3344 { 3345 unsigned int j; 3346 group_info_t group; 3347 3348 all_ones = BITMAP_ALLOC (NULL); 3349 for (j = 0; VEC_iterate (group_info_t, rtx_group_vec, j, group); j++) 3350 bitmap_ior_into (all_ones, group->group_kill); 3351 } 3352 if (!bb_info->out) 3353 { 3354 bb_info->out = BITMAP_ALLOC (NULL); 3355 bitmap_copy (bb_info->out, all_ones); 3356 } 3357 } 3358 } 3359 3360 if (all_ones) 3361 BITMAP_FREE (all_ones); 3362 sbitmap_free (unreachable_blocks); 3363 } 3364 3365 3366 3367 /*---------------------------------------------------------------------------- 3368 Fourth step. 3369 3370 Solve the bitvector equations. 3371 ----------------------------------------------------------------------------*/ 3372 3373 3374 /* Confluence function for blocks with no successors. Create an out 3375 set from the gen set of the exit block. This block logically has 3376 the exit block as a successor. */ 3377 3378 3379 3380 static void 3381 dse_confluence_0 (basic_block bb) 3382 { 3383 bb_info_t bb_info = bb_table[bb->index]; 3384 3385 if (bb->index == EXIT_BLOCK) 3386 return; 3387 3388 if (!bb_info->out) 3389 { 3390 bb_info->out = BITMAP_ALLOC (NULL); 3391 bitmap_copy (bb_info->out, bb_table[EXIT_BLOCK]->gen); 3392 } 3393 } 3394 3395 /* Propagate the information from the in set of the dest of E to the 3396 out set of the src of E. If the various in or out sets are not 3397 there, that means they are all ones. */ 3398 3399 static void 3400 dse_confluence_n (edge e) 3401 { 3402 bb_info_t src_info = bb_table[e->src->index]; 3403 bb_info_t dest_info = bb_table[e->dest->index]; 3404 3405 if (dest_info->in) 3406 { 3407 if (src_info->out) 3408 bitmap_and_into (src_info->out, dest_info->in); 3409 else 3410 { 3411 src_info->out = BITMAP_ALLOC (NULL); 3412 bitmap_copy (src_info->out, dest_info->in); 3413 } 3414 } 3415 } 3416 3417 3418 /* Propagate the info from the out to the in set of BB_INDEX's basic 3419 block. There are three cases: 3420 3421 1) The block has no kill set. In this case the kill set is all 3422 ones. It does not matter what the out set of the block is, none of 3423 the info can reach the top. The only thing that reaches the top is 3424 the gen set and we just copy the set. 3425 3426 2) There is a kill set but no out set and bb has successors. In 3427 this case we just return. Eventually an out set will be created and 3428 it is better to wait than to create a set of ones. 3429 3430 3) There is both a kill and out set. We apply the obvious transfer 3431 function. 3432 */ 3433 3434 static bool 3435 dse_transfer_function (int bb_index) 3436 { 3437 bb_info_t bb_info = bb_table[bb_index]; 3438 3439 if (bb_info->kill) 3440 { 3441 if (bb_info->out) 3442 { 3443 /* Case 3 above. */ 3444 if (bb_info->in) 3445 return bitmap_ior_and_compl (bb_info->in, bb_info->gen, 3446 bb_info->out, bb_info->kill); 3447 else 3448 { 3449 bb_info->in = BITMAP_ALLOC (NULL); 3450 bitmap_ior_and_compl (bb_info->in, bb_info->gen, 3451 bb_info->out, bb_info->kill); 3452 return true; 3453 } 3454 } 3455 else 3456 /* Case 2 above. */ 3457 return false; 3458 } 3459 else 3460 { 3461 /* Case 1 above. If there is already an in set, nothing 3462 happens. */ 3463 if (bb_info->in) 3464 return false; 3465 else 3466 { 3467 bb_info->in = BITMAP_ALLOC (NULL); 3468 bitmap_copy (bb_info->in, bb_info->gen); 3469 return true; 3470 } 3471 } 3472 } 3473 3474 /* Solve the dataflow equations. */ 3475 3476 static void 3477 dse_step4 (void) 3478 { 3479 df_simple_dataflow (DF_BACKWARD, NULL, dse_confluence_0, 3480 dse_confluence_n, dse_transfer_function, 3481 all_blocks, df_get_postorder (DF_BACKWARD), 3482 df_get_n_blocks (DF_BACKWARD)); 3483 if (dump_file) 3484 { 3485 basic_block bb; 3486 3487 fprintf (dump_file, "\n\n*** Global dataflow info after analysis.\n"); 3488 FOR_ALL_BB (bb) 3489 { 3490 bb_info_t bb_info = bb_table[bb->index]; 3491 3492 df_print_bb_index (bb, dump_file); 3493 if (bb_info->in) 3494 bitmap_print (dump_file, bb_info->in, " in: ", "\n"); 3495 else 3496 fprintf (dump_file, " in: *MISSING*\n"); 3497 if (bb_info->gen) 3498 bitmap_print (dump_file, bb_info->gen, " gen: ", "\n"); 3499 else 3500 fprintf (dump_file, " gen: *MISSING*\n"); 3501 if (bb_info->kill) 3502 bitmap_print (dump_file, bb_info->kill, " kill: ", "\n"); 3503 else 3504 fprintf (dump_file, " kill: *MISSING*\n"); 3505 if (bb_info->out) 3506 bitmap_print (dump_file, bb_info->out, " out: ", "\n"); 3507 else 3508 fprintf (dump_file, " out: *MISSING*\n\n"); 3509 } 3510 } 3511 } 3512 3513 3514 3515 /*---------------------------------------------------------------------------- 3516 Fifth step. 3517 3518 Delete the stores that can only be deleted using the global information. 3519 ----------------------------------------------------------------------------*/ 3520 3521 3522 static void 3523 dse_step5_nospill (void) 3524 { 3525 basic_block bb; 3526 FOR_EACH_BB (bb) 3527 { 3528 bb_info_t bb_info = bb_table[bb->index]; 3529 insn_info_t insn_info = bb_info->last_insn; 3530 bitmap v = bb_info->out; 3531 3532 while (insn_info) 3533 { 3534 bool deleted = false; 3535 if (dump_file && insn_info->insn) 3536 { 3537 fprintf (dump_file, "starting to process insn %d\n", 3538 INSN_UID (insn_info->insn)); 3539 bitmap_print (dump_file, v, " v: ", "\n"); 3540 } 3541 3542 /* There may have been code deleted by the dce pass run before 3543 this phase. */ 3544 if (insn_info->insn 3545 && INSN_P (insn_info->insn) 3546 && (!insn_info->cannot_delete) 3547 && (!bitmap_empty_p (v))) 3548 { 3549 store_info_t store_info = insn_info->store_rec; 3550 3551 /* Try to delete the current insn. */ 3552 deleted = true; 3553 3554 /* Skip the clobbers. */ 3555 while (!store_info->is_set) 3556 store_info = store_info->next; 3557 3558 if (store_info->alias_set) 3559 deleted = false; 3560 else 3561 { 3562 HOST_WIDE_INT i; 3563 group_info_t group_info 3564 = VEC_index (group_info_t, rtx_group_vec, store_info->group_id); 3565 3566 for (i = store_info->begin; i < store_info->end; i++) 3567 { 3568 int index = get_bitmap_index (group_info, i); 3569 3570 if (dump_file) 3571 fprintf (dump_file, "i = %d, index = %d\n", (int)i, index); 3572 if (index == 0 || !bitmap_bit_p (v, index)) 3573 { 3574 if (dump_file) 3575 fprintf (dump_file, "failing at i = %d\n", (int)i); 3576 deleted = false; 3577 break; 3578 } 3579 } 3580 } 3581 if (deleted) 3582 { 3583 if (dbg_cnt (dse)) 3584 { 3585 check_for_inc_dec (insn_info->insn); 3586 delete_insn (insn_info->insn); 3587 insn_info->insn = NULL; 3588 globally_deleted++; 3589 } 3590 } 3591 } 3592 /* We do want to process the local info if the insn was 3593 deleted. For instance, if the insn did a wild read, we 3594 no longer need to trash the info. */ 3595 if (insn_info->insn 3596 && INSN_P (insn_info->insn) 3597 && (!deleted)) 3598 { 3599 scan_stores_nospill (insn_info->store_rec, v, NULL); 3600 if (insn_info->wild_read) 3601 { 3602 if (dump_file) 3603 fprintf (dump_file, "wild read\n"); 3604 bitmap_clear (v); 3605 } 3606 else if (insn_info->read_rec) 3607 { 3608 if (dump_file) 3609 fprintf (dump_file, "regular read\n"); 3610 scan_reads_nospill (insn_info, v, NULL); 3611 } 3612 } 3613 3614 insn_info = insn_info->prev_insn; 3615 } 3616 } 3617 } 3618 3619 3620 static void 3621 dse_step5_spill (void) 3622 { 3623 basic_block bb; 3624 FOR_EACH_BB (bb) 3625 { 3626 bb_info_t bb_info = bb_table[bb->index]; 3627 insn_info_t insn_info = bb_info->last_insn; 3628 bitmap v = bb_info->out; 3629 3630 while (insn_info) 3631 { 3632 bool deleted = false; 3633 /* There may have been code deleted by the dce pass run before 3634 this phase. */ 3635 if (insn_info->insn 3636 && INSN_P (insn_info->insn) 3637 && (!insn_info->cannot_delete) 3638 && (!bitmap_empty_p (v))) 3639 { 3640 /* Try to delete the current insn. */ 3641 store_info_t store_info = insn_info->store_rec; 3642 deleted = true; 3643 3644 while (store_info) 3645 { 3646 if (store_info->alias_set) 3647 { 3648 int index = get_bitmap_index (clear_alias_group, 3649 store_info->alias_set); 3650 if (index == 0 || !bitmap_bit_p (v, index)) 3651 { 3652 deleted = false; 3653 break; 3654 } 3655 } 3656 else 3657 deleted = false; 3658 store_info = store_info->next; 3659 } 3660 if (deleted && dbg_cnt (dse)) 3661 { 3662 if (dump_file) 3663 fprintf (dump_file, "Spill deleting insn %d\n", 3664 INSN_UID (insn_info->insn)); 3665 check_for_inc_dec (insn_info->insn); 3666 delete_insn (insn_info->insn); 3667 spill_deleted++; 3668 insn_info->insn = NULL; 3669 } 3670 } 3671 3672 if (insn_info->insn 3673 && INSN_P (insn_info->insn) 3674 && (!deleted)) 3675 { 3676 scan_stores_spill (insn_info->store_rec, v, NULL); 3677 scan_reads_spill (insn_info->read_rec, v, NULL); 3678 } 3679 3680 insn_info = insn_info->prev_insn; 3681 } 3682 } 3683 } 3684 3685 3686 3687 /*---------------------------------------------------------------------------- 3688 Sixth step. 3689 3690 Delete stores made redundant by earlier stores (which store the same 3691 value) that couldn't be eliminated. 3692 ----------------------------------------------------------------------------*/ 3693 3694 static void 3695 dse_step6 (void) 3696 { 3697 basic_block bb; 3698 3699 FOR_ALL_BB (bb) 3700 { 3701 bb_info_t bb_info = bb_table[bb->index]; 3702 insn_info_t insn_info = bb_info->last_insn; 3703 3704 while (insn_info) 3705 { 3706 /* There may have been code deleted by the dce pass run before 3707 this phase. */ 3708 if (insn_info->insn 3709 && INSN_P (insn_info->insn) 3710 && !insn_info->cannot_delete) 3711 { 3712 store_info_t s_info = insn_info->store_rec; 3713 3714 while (s_info && !s_info->is_set) 3715 s_info = s_info->next; 3716 if (s_info 3717 && s_info->redundant_reason 3718 && s_info->redundant_reason->insn 3719 && INSN_P (s_info->redundant_reason->insn)) 3720 { 3721 rtx rinsn = s_info->redundant_reason->insn; 3722 if (dump_file) 3723 fprintf (dump_file, "Locally deleting insn %d " 3724 "because insn %d stores the " 3725 "same value and couldn't be " 3726 "eliminated\n", 3727 INSN_UID (insn_info->insn), 3728 INSN_UID (rinsn)); 3729 delete_dead_store_insn (insn_info); 3730 } 3731 } 3732 insn_info = insn_info->prev_insn; 3733 } 3734 } 3735 } 3736 3737 /*---------------------------------------------------------------------------- 3738 Seventh step. 3739 3740 Destroy everything left standing. 3741 ----------------------------------------------------------------------------*/ 3742 3743 static void 3744 dse_step7 (bool global_done) 3745 { 3746 unsigned int i; 3747 group_info_t group; 3748 basic_block bb; 3749 3750 for (i = 0; VEC_iterate (group_info_t, rtx_group_vec, i, group); i++) 3751 { 3752 free (group->offset_map_n); 3753 free (group->offset_map_p); 3754 BITMAP_FREE (group->store1_n); 3755 BITMAP_FREE (group->store1_p); 3756 BITMAP_FREE (group->store2_n); 3757 BITMAP_FREE (group->store2_p); 3758 BITMAP_FREE (group->group_kill); 3759 } 3760 3761 if (global_done) 3762 FOR_ALL_BB (bb) 3763 { 3764 bb_info_t bb_info = bb_table[bb->index]; 3765 BITMAP_FREE (bb_info->gen); 3766 if (bb_info->kill) 3767 BITMAP_FREE (bb_info->kill); 3768 if (bb_info->in) 3769 BITMAP_FREE (bb_info->in); 3770 if (bb_info->out) 3771 BITMAP_FREE (bb_info->out); 3772 } 3773 3774 if (clear_alias_sets) 3775 { 3776 BITMAP_FREE (clear_alias_sets); 3777 BITMAP_FREE (disqualified_clear_alias_sets); 3778 free_alloc_pool (clear_alias_mode_pool); 3779 htab_delete (clear_alias_mode_table); 3780 } 3781 3782 end_alias_analysis (); 3783 free (bb_table); 3784 htab_delete (rtx_group_table); 3785 VEC_free (group_info_t, heap, rtx_group_vec); 3786 BITMAP_FREE (all_blocks); 3787 BITMAP_FREE (scratch); 3788 3789 free_alloc_pool (rtx_store_info_pool); 3790 free_alloc_pool (read_info_pool); 3791 free_alloc_pool (insn_info_pool); 3792 free_alloc_pool (bb_info_pool); 3793 free_alloc_pool (rtx_group_info_pool); 3794 free_alloc_pool (deferred_change_pool); 3795 } 3796 3797 3798 /* ------------------------------------------------------------------------- 3799 DSE 3800 ------------------------------------------------------------------------- */ 3801 3802 /* Callback for running pass_rtl_dse. */ 3803 3804 static unsigned int 3805 rest_of_handle_dse (void) 3806 { 3807 bool did_global = false; 3808 3809 df_set_flags (DF_DEFER_INSN_RESCAN); 3810 3811 /* Need the notes since we must track live hardregs in the forwards 3812 direction. */ 3813 df_note_add_problem (); 3814 df_analyze (); 3815 3816 dse_step0 (); 3817 dse_step1 (); 3818 dse_step2_init (); 3819 if (dse_step2_nospill ()) 3820 { 3821 df_set_flags (DF_LR_RUN_DCE); 3822 df_analyze (); 3823 did_global = true; 3824 if (dump_file) 3825 fprintf (dump_file, "doing global processing\n"); 3826 dse_step3 (false); 3827 dse_step4 (); 3828 dse_step5_nospill (); 3829 } 3830 3831 /* For the instance of dse that runs after reload, we make a special 3832 pass to process the spills. These are special in that they are 3833 totally transparent, i.e, there is no aliasing issues that need 3834 to be considered. This means that the wild reads that kill 3835 everything else do not apply here. */ 3836 if (clear_alias_sets && dse_step2_spill ()) 3837 { 3838 if (!did_global) 3839 { 3840 df_set_flags (DF_LR_RUN_DCE); 3841 df_analyze (); 3842 } 3843 did_global = true; 3844 if (dump_file) 3845 fprintf (dump_file, "doing global spill processing\n"); 3846 dse_step3 (true); 3847 dse_step4 (); 3848 dse_step5_spill (); 3849 } 3850 3851 dse_step6 (); 3852 dse_step7 (did_global); 3853 3854 if (dump_file) 3855 fprintf (dump_file, "dse: local deletions = %d, global deletions = %d, spill deletions = %d\n", 3856 locally_deleted, globally_deleted, spill_deleted); 3857 return 0; 3858 } 3859 3860 static bool 3861 gate_dse (void) 3862 { 3863 return gate_dse1 () || gate_dse2 (); 3864 } 3865 3866 static bool 3867 gate_dse1 (void) 3868 { 3869 return optimize > 0 && flag_dse 3870 && dbg_cnt (dse1); 3871 } 3872 3873 static bool 3874 gate_dse2 (void) 3875 { 3876 return optimize > 0 && flag_dse 3877 && dbg_cnt (dse2); 3878 } 3879 3880 struct rtl_opt_pass pass_rtl_dse1 = 3881 { 3882 { 3883 RTL_PASS, 3884 "dse1", /* name */ 3885 gate_dse1, /* gate */ 3886 rest_of_handle_dse, /* execute */ 3887 NULL, /* sub */ 3888 NULL, /* next */ 3889 0, /* static_pass_number */ 3890 TV_DSE1, /* tv_id */ 3891 0, /* properties_required */ 3892 0, /* properties_provided */ 3893 0, /* properties_destroyed */ 3894 0, /* todo_flags_start */ 3895 TODO_dump_func | 3896 TODO_df_finish | TODO_verify_rtl_sharing | 3897 TODO_ggc_collect /* todo_flags_finish */ 3898 } 3899 }; 3900 3901 struct rtl_opt_pass pass_rtl_dse2 = 3902 { 3903 { 3904 RTL_PASS, 3905 "dse2", /* name */ 3906 gate_dse2, /* gate */ 3907 rest_of_handle_dse, /* execute */ 3908 NULL, /* sub */ 3909 NULL, /* next */ 3910 0, /* static_pass_number */ 3911 TV_DSE2, /* tv_id */ 3912 0, /* properties_required */ 3913 0, /* properties_provided */ 3914 0, /* properties_destroyed */ 3915 0, /* todo_flags_start */ 3916 TODO_dump_func | 3917 TODO_df_finish | TODO_verify_rtl_sharing | 3918 TODO_ggc_collect /* todo_flags_finish */ 3919 } 3920 }; 3921