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