gcc/postreload-gcse.c

   1 /* Post reload partially redundant load elimination
   2    Copyright (C) 2004
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "toplev.h"
  27
  28 #include "rtl.h"
  29 #include "tree.h"
  30 #include "tm_p.h"
  31 #include "regs.h"
  32 #include "hard-reg-set.h"
  33 #include "flags.h"
  34 #include "real.h"
  35 #include "insn-config.h"
  36 #include "recog.h"
  37 #include "basic-block.h"
  38 #include "output.h"
  39 #include "function.h"
  40 #include "expr.h"
  41 #include "except.h"
  42 #include "intl.h"
  43 #include "obstack.h"
  44 #include "hashtab.h"
  45 #include "params.h"
  46
  47 /* The following code implements gcse after reload, the purpose of this
  48    pass is to cleanup redundant loads generated by reload and other
  49    optimizations that come after gcse. It searches for simple inter-block
  50    redundancies and tries to eliminate them by adding moves and loads
  51    in cold places.
  52
  53    Perform partially redundant load elimination, try to eliminate redundant
  54    loads created by the reload pass.  We try to look for full or partial
  55    redundant loads fed by one or more loads/stores in predecessor BBs,
  56    and try adding loads to make them fully redundant.  We also check if
  57    it's worth adding loads to be able to delete the redundant load.
  58
  59    Algorithm:
  60    1. Build available expressions hash table:
  61        For each load/store instruction, if the loaded/stored memory didn't
  62        change until the end of the basic block add this memory expression to
  63        the hash table.
  64    2. Perform Redundancy elimination:
  65       For each load instruction do the following:
  66          perform partial redundancy elimination, check if it's worth adding
  67          loads to make the load fully redundant.  If so add loads and
  68          register copies and delete the load.
  69    3. Delete instructions made redundant in step 2.
  70
  71    Future enhancement:
  72      If the loaded register is used/defined between load and some store,
  73      look for some other free register between load and all its stores,
  74      and replace the load with a copy from this register to the loaded
  75      register.
  76 */
  77 \f
  78
  79 /* Keep statistics of this pass.  */
  80 static struct
  81 {
  82   int moves_inserted;
  83   int copies_inserted;
  84   int insns_deleted;
  85 } stats;
  86
  87 /* We need to keep a hash table of expressions.  The table entries are of
  88    type 'struct expr', and for each expression there is a single linked
  89    list of occurrences.  */
  90
  91 /* The table itself.  */
  92 static htab_t expr_table;
  93
  94 /* Expression elements in the hash table.  */
  95 struct expr
  96 {
  97   /* The expression (SET_SRC for expressions, PATTERN for assignments).  */
  98   rtx expr;
  99
 100   /* The same hash for this entry.  */
 101   hashval_t hash;
 102
 103   /* List of available occurrence in basic blocks in the function.  */
 104   struct occr *avail_occr;
 105 };
 106
 107 static struct obstack expr_obstack;
 108
 109 /* Occurrence of an expression.
 110    There is at most one occurrence per basic block.  If a pattern appears
 111    more than once, the last appearance is used.  */
 112
 113 struct occr
 114 {
 115   /* Next occurrence of this expression.  */
 116   struct occr *next;
 117   /* The insn that computes the expression.  */
 118   rtx insn;
 119   /* Nonzero if this [anticipatable] occurrence has been deleted.  */
 120   char deleted_p;
 121 };
 122
 123 static struct obstack occr_obstack;
 124
 125 /* The following structure holds the information about the occurrences of
 126    the redundant instructions.  */
 127 struct unoccr
 128 {
 129   struct unoccr *next;
 130   edge pred;
 131   rtx insn;
 132 };
 133
 134 static struct obstack unoccr_obstack;
 135
 136 /* Array where each element is the CUID if the insn that last set the hard
 137    register with the number of the element, since the start of the current
 138    basic block.
 139
 140    This array is used during the building of the hash table (step 1) to
 141    determine if a reg is killed before the end of a basic block.
 142
 143    It is also used when eliminating partial redundancies (step 2) to see
 144    if a reg was modified since the start of a basic block.  */
 145 static int *reg_avail_info;
 146
 147 /* A list of insns that may modify memory within the current basic block.  */
 148 struct modifies_mem
 149 {
 150   rtx insn;
 151   struct modifies_mem *next;
 152 };
 153 static struct modifies_mem *modifies_mem_list;
 154
 155 /* The modifies_mem structs also go on an obstack, only this obstack is
 156    freed each time after completing the analysis or transformations on
 157    a basic block.  So we allocate a dummy modifies_mem_obstack_bottom
 158    object on the obstack to keep track of the bottom of the obstack.  */
 159 static struct obstack modifies_mem_obstack;
 160 static struct modifies_mem  *modifies_mem_obstack_bottom;
 161
 162 /* Mapping of insn UIDs to CUIDs.
 163    CUIDs are like UIDs except they increase monotonically in each basic
 164    block, have no gaps, and only apply to real insns.  */
 165 static int *uid_cuid;
 166 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
 167 \f
 168
 169 /* Helpers for memory allocation/freeing.  */
 170 static void alloc_mem (void);
 171 static void free_mem (void);
 172
 173 /* Support for hash table construction and transformations.  */
 174 static bool oprs_unchanged_p (rtx, rtx, bool);
 175 static void record_last_reg_set_info (rtx, int);
 176 static void record_last_mem_set_info (rtx);
 177 static void record_last_set_info (rtx, rtx, void *);
 178 static void record_opr_changes (rtx);
 179
 180 static void find_mem_conflicts (rtx, rtx, void *);
 181 static int load_killed_in_block_p (int, rtx, bool);
 182 static void reset_opr_set_tables (void);
 183
 184 /* Hash table support.  */
 185 static hashval_t hash_expr (rtx, int *);
 186 static hashval_t hash_expr_for_htab (const void *);
 187 static int expr_equiv_p (const void *, const void *);
 188 static void insert_expr_in_table (rtx, rtx);
 189 static struct expr *lookup_expr_in_table (rtx);
 190 static int dump_hash_table_entry (void **, void *);
 191 static void dump_hash_table (FILE *);
 192
 193 /* Helpers for eliminate_partially_redundant_load.  */
 194 static bool reg_killed_on_edge (rtx, edge);
 195 static bool reg_used_on_edge (rtx, edge);
 196
 197 static rtx reg_set_between_after_reload_p (rtx, rtx, rtx);
 198 static rtx reg_used_between_after_reload_p (rtx, rtx, rtx);
 199 static rtx get_avail_load_store_reg (rtx);
 200
 201 static bool bb_has_well_behaved_predecessors (basic_block);
 202 static struct occr* get_bb_avail_insn (basic_block, struct occr *);
 203 static void hash_scan_set (rtx);
 204 static void compute_hash_table (void);
 205
 206 /* The work horses of this pass.  */
 207 static void eliminate_partially_redundant_load (basic_block,
 208                                                 rtx,
 209                                                 struct expr *);
 210 static void eliminate_partially_redundant_loads (void);
 211 \f
 212
 213 /* Allocate memory for the CUID mapping array and register/memory
 214    tracking tables.  */
 215
 216 static void
 217 alloc_mem (void)
 218 {
 219   int i;
 220   basic_block bb;
 221   rtx insn;
 222
 223   /* Find the largest UID and create a mapping from UIDs to CUIDs.  */
 224   uid_cuid = xcalloc (get_max_uid () + 1, sizeof (int));
 225   i = 0;
 226   FOR_EACH_BB (bb)
 227     FOR_BB_INSNS (bb, insn)
 228       {
 229         if (INSN_P (insn))
 230           uid_cuid[INSN_UID (insn)] = i++;
 231         else
 232           uid_cuid[INSN_UID (insn)] = i;
 233       }
 234
 235   /* Allocate the available expressions hash table.  We don't want to
 236      make the hash table too small, but unnecessarily making it too large
 237      also doesn't help.  The i/4 is a gcse.c relic, and seems like a
 238      reasonable choice.  */
 239   expr_table = htab_create (MAX (i / 4, 13),
 240                             hash_expr_for_htab, expr_equiv_p, NULL);
 241
 242   /* We allocate everything on obstacks because we often can roll back
 243      the whole obstack to some point.  Freeing obstacks is very fast.  */
 244   gcc_obstack_init (&expr_obstack);
 245   gcc_obstack_init (&occr_obstack);
 246   gcc_obstack_init (&unoccr_obstack);
 247   gcc_obstack_init (&modifies_mem_obstack);
 248
 249   /* Working array used to track the last set for each register
 250      in the current block.  */
 251   reg_avail_info = (int *) xmalloc (FIRST_PSEUDO_REGISTER * sizeof (int));
 252
 253   /* Put a dummy modifies_mem object on the modifies_mem_obstack, so we
 254      can roll it back in reset_opr_set_tables.  */
 255   modifies_mem_obstack_bottom =
 256     (struct modifies_mem *) obstack_alloc (&modifies_mem_obstack,
 257                                            sizeof (struct modifies_mem));
 258 }
 259
 260 /* Free memory allocated by alloc_mem.  */
 261
 262 static void
 263 free_mem (void)
 264 {
 265   free (uid_cuid);
 266
 267   htab_delete (expr_table);
 268
 269   obstack_free (&expr_obstack, NULL);
 270   obstack_free (&occr_obstack, NULL);
 271   obstack_free (&unoccr_obstack, NULL);
 272   obstack_free (&modifies_mem_obstack, NULL);
 273
 274   free (reg_avail_info);
 275 }
 276 \f
 277
 278 /* Hash expression X.
 279    DO_NOT_RECORD_P is a boolean indicating if a volatile operand is found
 280    or if the expression contains something we don't want to insert in the
 281    table.  */
 282
 283 static hashval_t
 284 hash_expr (rtx x, int *do_not_record_p)
 285 {
 286   *do_not_record_p = 0;
 287   return hash_rtx (x, GET_MODE (x), do_not_record_p,
 288                    NULL,  /*have_reg_qty=*/false);
 289 }
 290
 291 /* Callback for hashtab.
 292    Return the hash value for expression EXP.  We don't actually hash
 293    here, we just return the cached hash value.  */
 294
 295 static hashval_t
 296 hash_expr_for_htab (const void *expp)
 297 {
 298   struct expr *exp = (struct expr *) expp;
 299   return exp->hash;
 300 }
 301
 302 /* Callbach for hashtab.
 303    Return nonzero if exp1 is equivalent to exp2.  */
 304
 305 static int
 306 expr_equiv_p (const void *exp1p, const void *exp2p)
 307 {
 308   struct expr *exp1 = (struct expr *) exp1p;
 309   struct expr *exp2 = (struct expr *) exp2p;
 310   int equiv_p = exp_equiv_p (exp1->expr, exp2->expr, 0, true);
 311   if (equiv_p
 312       && exp1->hash != exp2->hash)
 313     abort ();
 314   return equiv_p;
 315 }
 316 \f
 317
 318 /* Insert expression X in INSN in the hash TABLE.
 319    If it is already present, record it as the last occurrence in INSN's
 320    basic block.  */
 321
 322 static void
 323 insert_expr_in_table (rtx x, rtx insn)
 324 {
 325   int do_not_record_p;
 326   hashval_t hash;
 327   struct expr *cur_expr, **slot;
 328   struct occr *avail_occr, *last_occr = NULL;
 329
 330   hash = hash_expr (x, &do_not_record_p);
 331
 332   /* Do not insert expression in the table if it contains volatile operands,
 333      or if hash_expr determines the expression is something we don't want
 334      to or can't handle.  */
 335   if (do_not_record_p)
 336     return;
 337
 338   /* We anticipate that redundant expressions are rare, so for convenience
 339      allocate a new hash table element here already and set its fields.
 340      If we don't do this, we need a hack with a static struct expr.  Anyway,
 341      obstack_free is really fast and one more obstack_alloc doesn't hurt if
 342      we're going to see more expressions later on.  */
 343   cur_expr = (struct expr *) obstack_alloc (&expr_obstack,
 344                                             sizeof (struct expr));
 345   cur_expr->expr = x;
 346   cur_expr->hash = hash;
 347   cur_expr->avail_occr = NULL;
 348
 349   slot = (struct expr **) htab_find_slot_with_hash (expr_table, cur_expr,
 350                                                     hash, INSERT);
 351
 352   if (! (*slot))
 353     /* The expression isn't found, so insert it.  */
 354     *slot = cur_expr;
 355   else
 356     {
 357       /* The expression is already in the table, so roll back the
 358          obstack and use the existing table entry.  */
 359       obstack_free (&expr_obstack, cur_expr);
 360       cur_expr = *slot;
 361     }
 362
 363   /* Search for another occurrence in the same basic block.  */
 364   avail_occr = cur_expr->avail_occr;
 365   while (avail_occr && BLOCK_NUM (avail_occr->insn) != BLOCK_NUM (insn))
 366     {
 367       /* If an occurrence isn't found, save a pointer to the end of
 368          the list.  */
 369       last_occr = avail_occr;
 370       avail_occr = avail_occr->next;
 371     }
 372
 373   if (avail_occr)
 374     /* Found another instance of the expression in the same basic block.
 375        Prefer this occurrence to the currently recorded one.  We want
 376        the last one in the block and the block is scanned from start
 377        to end.  */
 378     avail_occr->insn = insn;
 379   else
 380     {
 381       /* First occurrence of this expression in this basic block.  */
 382       avail_occr = (struct occr *) obstack_alloc (&occr_obstack,
 383                                                   sizeof (struct occr));
 384
 385       /* First occurrence of this expression in any block?  */
 386       if (cur_expr->avail_occr == NULL)
 387         cur_expr->avail_occr = avail_occr;
 388       else
 389         last_occr->next = avail_occr;
 390
 391       avail_occr->insn = insn;
 392       avail_occr->next = NULL;
 393       avail_occr->deleted_p = 0;
 394     }
 395 }
 396 \f
 397
 398 /* Lookup pattern PAT in the expression hash table.
 399    The result is a pointer to the table entry, or NULL if not found.  */
 400
 401 static struct expr *
 402 lookup_expr_in_table (rtx pat)
 403 {
 404   int do_not_record_p;
 405   struct expr **slot, *tmp_expr;
 406   hashval_t hash = hash_expr (pat, &do_not_record_p);
 407
 408   if (do_not_record_p)
 409     return NULL;
 410
 411   tmp_expr = (struct expr *) obstack_alloc (&expr_obstack,
 412                                             sizeof (struct expr));
 413   tmp_expr->expr = pat;
 414   tmp_expr->hash = hash;
 415   tmp_expr->avail_occr = NULL;
 416
 417   slot = (struct expr **) htab_find_slot_with_hash (expr_table, tmp_expr,
 418                                                     hash, INSERT);
 419   obstack_free (&expr_obstack, tmp_expr);
 420
 421   if (!slot)
 422     return NULL;
 423   else
 424     return (*slot);
 425 }
 426 \f
 427
 428 /* Dump all expressions and occurrences that are currently in the
 429    expression hash table to FILE.  */
 430
 431 /* This helper is called via htab_traverse.  */
 432 static int
 433 dump_hash_table_entry (void **slot, void *filep)
 434 {
 435   struct expr *expr = (struct expr *) *slot;
 436   FILE *file = (FILE *) filep;
 437   struct occr *occr;
 438
 439   fprintf (file, "expr: ");
 440   print_rtl (file, expr->expr);
 441   fprintf (file,"\nhashcode: %u\n", expr->hash);
 442   fprintf (file,"list of occurences:\n");
 443   occr = expr->avail_occr;
 444   while (occr)
 445     {
 446       rtx insn = occr->insn;
 447       print_rtl_single (file, insn);
 448       fprintf (file, "\n");
 449       occr = occr->next;
 450     }
 451   fprintf (file, "\n");
 452   return 1;
 453 }
 454
 455 static void
 456 dump_hash_table (FILE *file)
 457 {
 458   fprintf (file, "\n\nexpression hash table\n");
 459   fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
 460            (long) htab_size (expr_table),
 461            (long) htab_elements (expr_table),
 462            htab_collisions (expr_table));
 463   if (htab_elements (expr_table) > 0)
 464     {
 465       fprintf (file, "\n\ntable entries:\n");
 466       htab_traverse (expr_table, dump_hash_table_entry, file);
 467     }
 468   fprintf (file, "\n");
 469 }
 470 \f
 471
 472 /* Return nonzero if the operands of expression X are unchanged
 473    1) from the start of INSN's basic block up to but not including INSN
 474       if AFTER_INSN is false, or
 475    2) from INSN to the end of INSN's basic block if AFTER_INSN is true.  */
 476
 477 static bool
 478 oprs_unchanged_p (rtx x, rtx insn, bool after_insn)
 479 {
 480   int i, j;
 481   enum rtx_code code;
 482   const char *fmt;
 483
 484   if (x == 0)
 485     return 1;
 486
 487   code = GET_CODE (x);
 488   switch (code)
 489     {
 490     case REG:
 491 #ifdef ENABLE_CHECKING
 492       /* We are called after register allocation.  */
 493       if (REGNO (x) >= FIRST_PSEUDO_REGISTER)
 494         abort ();
 495 #endif
 496       if (after_insn)
 497         /* If the last CUID setting the insn is less than the CUID of
 498            INSN, then reg X is not changed in or after INSN.  */
 499         return reg_avail_info[REGNO (x)] < INSN_CUID (insn);
 500       else
 501         /* Reg X is not set before INSN in the current basic block if
 502            we have not yet recorded the CUID of an insn that touches
 503            the reg.  */
 504         return reg_avail_info[REGNO (x)] == 0;
 505
 506     case MEM:
 507       if (load_killed_in_block_p (INSN_CUID (insn), x, after_insn))
 508         return 0;
 509       else
 510         return oprs_unchanged_p (XEXP (x, 0), insn, after_insn);
 511
 512     case PC:
 513     case CC0: /*FIXME*/
 514     case CONST:
 515     case CONST_INT:
 516     case CONST_DOUBLE:
 517     case CONST_VECTOR:
 518     case SYMBOL_REF:
 519     case LABEL_REF:
 520     case ADDR_VEC:
 521     case ADDR_DIFF_VEC:
 522       return 1;
 523
 524     case PRE_DEC:
 525     case PRE_INC:
 526     case POST_DEC:
 527     case POST_INC:
 528     case PRE_MODIFY:
 529     case POST_MODIFY:
 530       if (after_insn)
 531         return 0;
 532       break;
 533
 534     default:
 535       break;
 536     }
 537
 538   for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
 539     {
 540       if (fmt[i] == 'e')
 541         {
 542           if (! oprs_unchanged_p (XEXP (x, i), insn, after_insn))
 543             return 0;
 544         }
 545       else if (fmt[i] == 'E')
 546         for (j = 0; j < XVECLEN (x, i); j++)
 547           if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, after_insn))
 548             return 0;
 549     }
 550
 551   return 1;
 552 }
 553 \f
 554
 555 /* Used for communication between find_mem_conflicts and
 556    load_killed_in_block_p.  Nonzero if find_mem_conflicts finds a
 557    conflict between two memory references.
 558    This is a bit of a hack to work around the limitations of note_stores.  */
 559 static int mems_conflict_p;
 560
 561 /* DEST is the output of an instruction.  If it is a memory reference, and
 562    possibly conflicts with the load found in DATA, then set mems_conflict_p
 563    to a nonzero value.  */
 564
 565 static void
 566 find_mem_conflicts (rtx dest, rtx setter ATTRIBUTE_UNUSED,
 567                     void *data)
 568 {
 569   rtx mem_op = (rtx) data;
 570
 571   while (GET_CODE (dest) == SUBREG
 572          || GET_CODE (dest) == ZERO_EXTRACT
 573          || GET_CODE (dest) == SIGN_EXTRACT
 574          || GET_CODE (dest) == STRICT_LOW_PART)
 575     dest = XEXP (dest, 0);
 576
 577   /* If DEST is not a MEM, then it will not conflict with the load.  Note
 578      that function calls are assumed to clobber memory, but are handled
 579      elsewhere.  */
 580   if (! MEM_P (dest))
 581     return;
 582
 583   if (true_dependence (dest, GET_MODE (dest), mem_op,
 584                        rtx_addr_varies_p))
 585     mems_conflict_p = 1;
 586 }
 587 \f
 588
 589 /* Return nonzero if the expression in X (a memory reference) is killed
 590    in the current basic block before (if AFTER_INSN is false) or after
 591    (if AFTER_INSN is true) the insn with the CUID in UID_LIMIT.
 592
 593    This function assumes that the modifies_mem table is flushed when
 594    the hash table construction or redundancy elimination phases start
 595    processing a new basic block.  */
 596
 597 static int
 598 load_killed_in_block_p (int uid_limit, rtx x, bool after_insn)
 599 {
 600   struct modifies_mem *list_entry = modifies_mem_list;
 601
 602   while (list_entry)
 603     {
 604       rtx setter = list_entry->insn;
 605
 606       /* Ignore entries in the list that do not apply.  */
 607       if ((after_insn
 608            && INSN_CUID (setter) < uid_limit)
 609           || (! after_insn
 610               && INSN_CUID (setter) > uid_limit))
 611         {
 612           list_entry = list_entry->next;
 613           continue;
 614         }
 615
 616       /* If SETTER is a call everything is clobbered.  Note that calls
 617          to pure functions are never put on the list, so we need not
 618          worry about them.  */
 619       if (CALL_P (setter))
 620         return 1;
 621
 622       /* SETTER must be an insn of some kind that sets memory.  Call
 623          note_stores to examine each hunk of memory that is modified.
 624          It will set mems_conflict_p to nonzero if there may be a
 625          conflict between X and SETTER.  */
 626       mems_conflict_p = 0;
 627       note_stores (PATTERN (setter), find_mem_conflicts, x);
 628       if (mems_conflict_p)
 629         return 1;
 630
 631       list_entry = list_entry->next;
 632     }
 633   return 0;
 634 }
 635 \f
 636
 637 /* Record register first/last/block set information for REGNO in INSN.  */
 638
 639 static inline void
 640 record_last_reg_set_info (rtx insn, int regno)
 641 {
 642   reg_avail_info[regno] = INSN_CUID (insn);
 643 }
 644
 645
 646 /* Record memory modification information for INSN.  We do not actually care
 647    about the memory location(s) that are set, or even how they are set (consider
 648    a CALL_INSN).  We merely need to record which insns modify memory.  */
 649
 650 static void
 651 record_last_mem_set_info (rtx insn)
 652 {
 653   struct modifies_mem *list_entry;
 654
 655   list_entry = (struct modifies_mem *) obstack_alloc (&modifies_mem_obstack,
 656                                                       sizeof (struct modifies_mem));
 657   list_entry->insn = insn;
 658   list_entry->next = modifies_mem_list;
 659   modifies_mem_list = list_entry;
 660 }
 661
 662 /* Called from compute_hash_table via note_stores to handle one
 663    SET or CLOBBER in an insn.  DATA is really the instruction in which
 664    the SET is taking place.  */
 665
 666 static void
 667 record_last_set_info (rtx dest, rtx setter ATTRIBUTE_UNUSED, void *data)
 668 {
 669   rtx last_set_insn = (rtx) data;
 670
 671   if (GET_CODE (dest) == SUBREG)
 672     dest = SUBREG_REG (dest);
 673
 674   if (REG_P (dest))
 675     record_last_reg_set_info (last_set_insn, REGNO (dest));
 676   else if (MEM_P (dest)
 677            /* Ignore pushes, they clobber nothing.  */
 678            && ! push_operand (dest, GET_MODE (dest)))
 679     record_last_mem_set_info (last_set_insn);
 680 }
 681
 682
 683 /* Reset tables used to keep track of what's still available since the
 684    start of the block.  */
 685
 686 static void
 687 reset_opr_set_tables (void)
 688 {
 689   memset (reg_avail_info, 0, FIRST_PSEUDO_REGISTER * sizeof (int));
 690   obstack_free (&modifies_mem_obstack, modifies_mem_obstack_bottom);
 691   modifies_mem_list = NULL;
 692 }
 693 \f
 694
 695 /* Record things set by INSN.
 696    This data is used by oprs_unchanged_p.  */
 697
 698 static void
 699 record_opr_changes (rtx insn)
 700 {
 701   rtx note;
 702
 703   /* Find all stores and record them.  */
 704   note_stores (PATTERN (insn), record_last_set_info, insn);
 705
 706   /* Also record autoincremented REGs for this insn as changed.  */
 707   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 708     if (REG_NOTE_KIND (note) == REG_INC)
 709       record_last_reg_set_info (insn, REGNO (XEXP (note, 0)));
 710
 711   /* Finally, if this is a call, record all call clobbers.  */
 712   if (CALL_P (insn))
 713     {
 714       unsigned int regno;
 715       bool clobbers_all = false;
 716
 717 #ifdef NON_SAVING_SETJMP
 718       if (NON_SAVING_SETJMP
 719           && find_reg_note (insn, REG_SETJMP, NULL_RTX))
 720         clobbers_all = true;
 721 #endif
 722
 723       for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
 724         if (clobbers_all
 725             || TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
 726           record_last_reg_set_info (insn, regno);
 727
 728       if (! CONST_OR_PURE_CALL_P (insn))
 729         record_last_mem_set_info (insn);
 730     }
 731 }
 732 \f
 733
 734 /* Scan the pattern of INSN and add an entry to the hash TABLE.
 735    After reload we are interested in loads/stores only.  */
 736
 737 static void
 738 hash_scan_set (rtx insn)
 739 {
 740   rtx pat = PATTERN (insn);
 741   rtx src = SET_SRC (pat);
 742   rtx dest = SET_DEST (pat);
 743
 744   /* We are only interested in loads and stores.  */
 745   if (! MEM_P (src) && ! MEM_P (dest))
 746     return;
 747
 748   /* Don't mess with jumps and nops.  */
 749   if (JUMP_P (insn) || set_noop_p (pat))
 750     return;
 751
 752 #ifdef ENABLE_CHEKCING
 753   /* We shouldn't have any EH_REGION notes post reload.  */
 754   if (find_reg_note (insn, REG_EH_REGION, NULL_RTX))
 755     abort ();
 756 #endif
 757
 758   if (REG_P (dest))
 759     {
 760       if (/* Don't CSE something if we can't do a reg/reg copy.  */
 761           can_copy_p (GET_MODE (dest))
 762           /* Is SET_SRC something we want to gcse?  */
 763           && general_operand (src, GET_MODE (src))
 764           /* An expression is not available if its operands are
 765              subsequently modified, including this insn.  */
 766           && oprs_unchanged_p (src, insn, true))
 767         {
 768           insert_expr_in_table (src, insn);
 769         }
 770     }
 771   else if (REG_P (src))
 772     {
 773       /* Only record sets of pseudo-regs in the hash table.  */
 774       if (/* Don't CSE something if we can't do a reg/reg copy.  */
 775           can_copy_p (GET_MODE (src))
 776           /* Is SET_DEST something we want to gcse?  */
 777           && general_operand (dest, GET_MODE (dest))
 778           && ! (flag_float_store && FLOAT_MODE_P (GET_MODE (dest)))
 779           /* Check if the memory expression is killed after insn.  */
 780           && ! load_killed_in_block_p (INSN_CUID (insn) + 1, dest, true)
 781           && oprs_unchanged_p (XEXP (dest, 0), insn, true))
 782         {
 783           insert_expr_in_table (dest, insn);
 784         }
 785     }
 786 }
 787 \f
 788
 789 /* Create hash table of memory expressions available at end of basic
 790    blocks.  Basically you should think of this hash table as the
 791    representation of AVAIL_OUT.  This is the set of expressions that
 792    is generated in a basic block and not killed before the end of the
 793    same basic block.  Notice that this is really a local computation.  */
 794
 795 static void
 796 compute_hash_table (void)
 797 {
 798   basic_block bb;
 799
 800   FOR_EACH_BB (bb)
 801     {
 802       rtx insn;
 803
 804       /* First pass over the instructions records information used to
 805          determine when registers and memory are last set.
 806          Since we compute a "local" AVAIL_OUT, reset the tables that
 807          help us keep track of what has been modified since the start
 808          of the block.  */
 809       reset_opr_set_tables ();
 810       FOR_BB_INSNS (bb, insn)
 811         {
 812           if (INSN_P (insn))
 813             record_opr_changes (insn);
 814         }
 815
 816       /* The next pass actually builds the hash table.  */
 817       FOR_BB_INSNS (bb, insn)
 818         if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == SET)
 819           hash_scan_set (insn);
 820     }
 821 }
 822 \f
 823
 824 /* Check if register REG is killed in any insn waiting to be inserted on
 825    edge E.  This function is required to check that our data flow analysis
 826    is still valid prior to commit_edge_insertions.  */
 827
 828 static bool
 829 reg_killed_on_edge (rtx reg, edge e)
 830 {
 831   rtx insn;
 832
 833   for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
 834     if (INSN_P (insn) && reg_set_p (reg, insn))
 835       return true;
 836
 837   return false;
 838 }
 839
 840 /* Similar to above - check if register REG is used in any insn waiting
 841    to be inserted on edge E.
 842    Assumes no such insn can be a CALL_INSN; if so call reg_used_between_p
 843    with PREV(insn),NEXT(insn) instead of calling reg_overlap_mentioned_p.  */
 844
 845 static bool
 846 reg_used_on_edge (rtx reg, edge e)
 847 {
 848   rtx insn;
 849
 850   for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
 851     if (INSN_P (insn) && reg_overlap_mentioned_p (reg, PATTERN (insn)))
 852       return true;
 853
 854   return false;
 855 }
 856 \f
 857
 858 /* Return the insn that sets register REG or clobbers it in between
 859    FROM_INSN and TO_INSN (exclusive of those two).
 860    Just like reg_set_between but for hard registers and not pseudos.  */
 861
 862 static rtx
 863 reg_set_between_after_reload_p (rtx reg, rtx from_insn, rtx to_insn)
 864 {
 865   rtx insn;
 866
 867 #ifdef ENABLE_CHECKING
 868   /* We are called after register allocation.  */
 869   if (!REG_P (reg) || REGNO (reg) >= FIRST_PSEUDO_REGISTER)
 870     abort ();
 871 #endif
 872
 873   if (from_insn == to_insn)
 874     return NULL_RTX;
 875
 876   for (insn = NEXT_INSN (from_insn);
 877        insn != to_insn;
 878        insn = NEXT_INSN (insn))
 879     if (INSN_P (insn))
 880       {
 881         if (set_of (reg, insn) != NULL_RTX)
 882           return insn;
 883         if ((CALL_P (insn)
 884               && call_used_regs[REGNO (reg)])
 885             || find_reg_fusage (insn, CLOBBER, reg))
 886           return insn;
 887
 888         if (FIND_REG_INC_NOTE (insn, reg))
 889           return insn;
 890       }
 891
 892   return NULL_RTX;
 893 }
 894
 895 /* Return the insn that uses register REG in between FROM_INSN and TO_INSN
 896    (exclusive of those two). Similar to reg_used_between but for hard
 897    registers and not pseudos.  */
 898
 899 static rtx
 900 reg_used_between_after_reload_p (rtx reg, rtx from_insn, rtx to_insn)
 901 {
 902   rtx insn;
 903
 904 #ifdef ENABLE_CHECKING
 905   /* We are called after register allocation.  */
 906   if (!REG_P (reg) || REGNO (reg) >= FIRST_PSEUDO_REGISTER)
 907     abort ();
 908 #endif
 909
 910   if (from_insn == to_insn)
 911     return NULL_RTX;
 912
 913   for (insn = NEXT_INSN (from_insn);
 914        insn != to_insn;
 915        insn = NEXT_INSN (insn))
 916     if (INSN_P (insn))
 917       {
 918         if (reg_overlap_mentioned_p (reg, PATTERN (insn))
 919             || (CALL_P (insn)
 920                 && call_used_regs[REGNO (reg)])
 921             || find_reg_fusage (insn, USE, reg)
 922             || find_reg_fusage (insn, CLOBBER, reg))
 923           return insn;
 924
 925         if (FIND_REG_INC_NOTE (insn, reg))
 926           return insn;
 927       }
 928
 929   return NULL_RTX;
 930 }
 931
 932 /* Return true if REG is used, set, or killed between the beginning of
 933    basic block BB and UP_TO_INSN.  Caches the result in reg_avail_info.  */
 934
 935 static bool
 936 reg_set_or_used_since_bb_start (rtx reg, basic_block bb, rtx up_to_insn)
 937 {
 938   rtx insn, start = PREV_INSN (BB_HEAD (bb));
 939
 940   if (reg_avail_info[REGNO (reg)] != 0)
 941     return true;
 942
 943   insn = reg_used_between_after_reload_p (reg, start, up_to_insn);
 944   if (! insn)
 945     insn = reg_set_between_after_reload_p (reg, start, up_to_insn);
 946
 947   if (insn)
 948     reg_avail_info[REGNO (reg)] = INSN_CUID (insn);
 949
 950   return insn != NULL_RTX;
 951 }
 952
 953 /* Return the loaded/stored register of a load/store instruction.  */
 954
 955 static rtx
 956 get_avail_load_store_reg (rtx insn)
 957 {
 958   if (REG_P (SET_DEST (PATTERN (insn))))  /* A load.  */
 959     return SET_DEST(PATTERN(insn));
 960   if (REG_P (SET_SRC (PATTERN (insn))))  /* A store.  */
 961     return SET_SRC (PATTERN (insn));
 962   abort ();
 963 }
 964
 965 /* Return nonzero if the predecessors of BB are "well behaved".  */
 966
 967 static bool
 968 bb_has_well_behaved_predecessors (basic_block bb)
 969 {
 970   edge pred;
 971   edge_iterator ei;
 972
 973   if (EDGE_COUNT (bb->preds) == 0)
 974     return false;
 975
 976   FOR_EACH_EDGE (pred, ei, bb->preds)
 977     {
 978       if ((pred->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (pred))
 979         return false;
 980
 981       if (JUMP_TABLE_DATA_P (BB_END (pred->src)))
 982         return false;
 983     }
 984   return true;
 985 }
 986
 987
 988 /* Search for the occurrences of expression in BB.  */
 989
 990 static struct occr*
 991 get_bb_avail_insn (basic_block bb, struct occr *occr)
 992 {
 993   for (; occr != NULL; occr = occr->next)
 994     if (BLOCK_FOR_INSN (occr->insn) == bb)
 995       return occr;
 996   return NULL;
 997 }
 998
 999
1000 /* This handles the case where several stores feed a partially redundant
1001    load. It checks if the redundancy elimination is possible and if it's
1002    worth it.
1003
1004    Redundancy elimination is possible if,
1005    1) None of the operands of an insn have been modified since the start
1006       of the current basic block.
1007    2) In any predecessor of the current basic block, the same expression
1008       is generated.
1009
1010    See the function body for the heuristics that determine if eliminating
1011    a redundancy is also worth doing, assuming it is possible.  */
1012
1013 static void
1014 eliminate_partially_redundant_load (basic_block bb, rtx insn,
1015                                     struct expr *expr)
1016 {
1017   edge pred;
1018   rtx avail_insn = NULL_RTX;
1019   rtx avail_reg;
1020   rtx dest, pat;
1021   struct occr *a_occr;
1022   struct unoccr *occr, *avail_occrs = NULL;
1023   struct unoccr *unoccr, *unavail_occrs = NULL, *rollback_unoccr = NULL;
1024   int npred_ok = 0;
1025   gcov_type ok_count = 0; /* Redundant load execution count.  */
1026   gcov_type critical_count = 0; /* Execution count of critical edges.  */
1027   edge_iterator ei;
1028
1029   /* The execution count of the loads to be added to make the
1030      load fully redundant.  */
1031   gcov_type not_ok_count = 0;
1032   basic_block pred_bb;
1033
1034   pat = PATTERN (insn);
1035   dest = SET_DEST (pat);
1036
1037   /* Check that the loaded register is not used, set, or killed from the
1038      beginning of the block.  */
1039   if (reg_set_or_used_since_bb_start (dest, bb, insn))
1040     return;
1041
1042   /* Check potential for replacing load with copy for predecessors.  */
1043   FOR_EACH_EDGE (pred, ei, bb->preds)
1044     {
1045       rtx next_pred_bb_end;
1046
1047       avail_insn = NULL_RTX;
1048       pred_bb = pred->src;
1049       next_pred_bb_end = NEXT_INSN (BB_END (pred_bb));
1050       for (a_occr = get_bb_avail_insn (pred_bb, expr->avail_occr); a_occr;
1051            a_occr = get_bb_avail_insn (pred_bb, a_occr->next))
1052         {
1053           /* Check if the loaded register is not used.  */
1054           avail_insn = a_occr->insn;
1055           if (! (avail_reg = get_avail_load_store_reg (avail_insn)))
1056             abort ();
1057           /* Make sure we can generate a move from register avail_reg to
1058              dest.  */
1059           extract_insn (gen_move_insn (copy_rtx (dest),
1060                                        copy_rtx (avail_reg)));
1061           if (! constrain_operands (1)
1062               || reg_killed_on_edge (avail_reg, pred)
1063               || reg_used_on_edge (dest, pred))
1064             {
1065               avail_insn = NULL;
1066               continue;
1067             }
1068           if (! reg_set_between_after_reload_p (avail_reg, avail_insn,
1069                                                 next_pred_bb_end))
1070             /* AVAIL_INSN remains non-null.  */
1071             break;
1072           else
1073             avail_insn = NULL;
1074         }
1075
1076       if (EDGE_CRITICAL_P (pred))
1077         critical_count += pred->count;
1078
1079       if (avail_insn != NULL_RTX)
1080         {
1081           npred_ok++;
1082           ok_count += pred->count;
1083           occr = (struct unoccr *) obstack_alloc (&unoccr_obstack,
1084                                                   sizeof (struct occr));
1085           occr->insn = avail_insn;
1086           occr->pred = pred;
1087           occr->next = avail_occrs;
1088           avail_occrs = occr;
1089           if (! rollback_unoccr)
1090             rollback_unoccr = occr;
1091         }
1092       else
1093         {
1094           not_ok_count += pred->count;
1095           unoccr = (struct unoccr *) obstack_alloc (&unoccr_obstack,
1096                                                     sizeof (struct unoccr));
1097           unoccr->insn = NULL_RTX;
1098           unoccr->pred = pred;
1099           unoccr->next = unavail_occrs;
1100           unavail_occrs = unoccr;
1101           if (! rollback_unoccr)
1102             rollback_unoccr = unoccr;
1103         }
1104     }
1105
1106   if (/* No load can be replaced by copy.  */
1107       npred_ok == 0
1108       /* Prevent exploding the code.  */
1109       || (optimize_size && npred_ok > 1))
1110     goto cleanup;
1111
1112   /* Check if it's worth applying the partial redundancy elimination.  */
1113   if (ok_count < GCSE_AFTER_RELOAD_PARTIAL_FRACTION * not_ok_count)
1114     goto cleanup;
1115   if (ok_count < GCSE_AFTER_RELOAD_CRITICAL_FRACTION * critical_count)
1116     goto cleanup;
1117
1118   /* Generate moves to the loaded register from where
1119      the memory is available.  */
1120   for (occr = avail_occrs; occr; occr = occr->next)
1121     {
1122       avail_insn = occr->insn;
1123       pred = occr->pred;
1124       /* Set avail_reg to be the register having the value of the
1125          memory.  */
1126       avail_reg = get_avail_load_store_reg (avail_insn);
1127       if (! avail_reg)
1128         abort ();
1129
1130       insert_insn_on_edge (gen_move_insn (copy_rtx (dest),
1131                                           copy_rtx (avail_reg)),
1132                            pred);
1133       stats.moves_inserted++;
1134
1135       if (dump_file)
1136         fprintf (dump_file,
1137                  "generating move from %d to %d on edge from %d to %d\n",
1138                  REGNO (avail_reg),
1139                  REGNO (dest),
1140                  pred->src->index,
1141                  pred->dest->index);
1142     }
1143
1144   /* Regenerate loads where the memory is unavailable.  */
1145   for (unoccr = unavail_occrs; unoccr; unoccr = unoccr->next)
1146     {
1147       pred = unoccr->pred;
1148       insert_insn_on_edge (copy_insn (PATTERN (insn)), pred);
1149       stats.copies_inserted++;
1150
1151       if (dump_file)
1152         {
1153           fprintf (dump_file,
1154                    "generating on edge from %d to %d a copy of load: ",
1155                    pred->src->index,
1156                    pred->dest->index);
1157           print_rtl (dump_file, PATTERN (insn));
1158           fprintf (dump_file, "\n");
1159         }
1160     }
1161
1162   /* Delete the insn if it is not available in this block and mark it
1163      for deletion if it is available. If insn is available it may help
1164      discover additional redundancies, so mark it for later deletion.  */
1165   for (a_occr = get_bb_avail_insn (bb, expr->avail_occr);
1166        a_occr && (a_occr->insn != insn);
1167        a_occr = get_bb_avail_insn (bb, a_occr->next));
1168
1169   if (!a_occr)
1170     delete_insn (insn);
1171   else
1172     a_occr->deleted_p = 1;
1173
1174 cleanup:
1175   if (rollback_unoccr)
1176     obstack_free (&unoccr_obstack, rollback_unoccr);
1177 }
1178
1179 /* Performing the redundancy elimination as described before.  */
1180
1181 static void
1182 eliminate_partially_redundant_loads (void)
1183 {
1184   rtx insn;
1185   basic_block bb;
1186
1187   /* Note we start at block 1.  */
1188
1189   if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
1190     return;
1191
1192   FOR_BB_BETWEEN (bb,
1193                   ENTRY_BLOCK_PTR->next_bb->next_bb,
1194                   EXIT_BLOCK_PTR,
1195                   next_bb)
1196     {
1197       /* Don't try anything on basic blocks with strange predecessors.  */
1198       if (! bb_has_well_behaved_predecessors (bb))
1199         continue;
1200
1201       /* Do not try anything on cold basic blocks.  */
1202       if (probably_cold_bb_p (bb))
1203         continue;
1204
1205       /* Reset the table of things changed since the start of the current
1206          basic block.  */
1207       reset_opr_set_tables ();
1208
1209       /* Look at all insns in the current basic block and see if there are
1210          any loads in it that we can record.  */
1211       FOR_BB_INSNS (bb, insn)
1212         {
1213           /* Is it a load - of the form (set (reg) (mem))?  */
1214           if (NONJUMP_INSN_P (insn)
1215               && GET_CODE (PATTERN (insn)) == SET
1216               && REG_P (SET_DEST (PATTERN (insn)))
1217               && MEM_P (SET_SRC (PATTERN (insn))))
1218             {
1219               rtx pat = PATTERN (insn);
1220               rtx src = SET_SRC (pat);
1221               struct expr *expr;
1222
1223               if (!MEM_VOLATILE_P (src)
1224                   && GET_MODE (src) != BLKmode
1225                   && general_operand (src, GET_MODE (src))
1226                   /* Are the operands unchanged since the start of the
1227                      block?  */
1228                   && oprs_unchanged_p (src, insn, false)
1229                   && !(flag_non_call_exceptions && may_trap_p (src))
1230                   && !side_effects_p (src)
1231                   /* Is the expression recorded?  */
1232                   && (expr = lookup_expr_in_table (src)) != NULL)
1233                 {
1234                   /* We now have a load (insn) and an available memory at
1235                      its BB start (expr). Try to remove the loads if it is
1236                      redundant.  */
1237                   eliminate_partially_redundant_load (bb, insn, expr);
1238                 }
1239             }
1240
1241           /* Keep track of everything modified by this insn, so that we
1242              know what has been modified since the start of the current
1243              basic block.  */
1244           if (INSN_P (insn))
1245             record_opr_changes (insn);
1246         }
1247     }
1248
1249   commit_edge_insertions ();
1250 }
1251
1252 /* Go over the expression hash table and delete insns that were
1253    marked for later deletion.  */
1254
1255 /* This helper is called via htab_traverse.  */
1256 static int
1257 delete_redundant_insns_1 (void **slot, void *data ATTRIBUTE_UNUSED)
1258 {
1259   struct expr *expr = (struct expr *) *slot;
1260   struct occr *occr;
1261
1262   for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
1263     {
1264       if (occr->deleted_p)
1265         {
1266           delete_insn (occr->insn);
1267           stats.insns_deleted++;
1268
1269           if (dump_file)
1270             {
1271               fprintf (dump_file, "deleting insn:\n");
1272               print_rtl_single (dump_file, occr->insn);
1273               fprintf (dump_file, "\n");
1274             }
1275         }
1276     }
1277
1278   return 1;
1279 }
1280
1281 static void
1282 delete_redundant_insns (void)
1283 {
1284   htab_traverse (expr_table, delete_redundant_insns_1, NULL);
1285   if (dump_file)
1286     fprintf (dump_file, "\n");
1287 }
1288
1289 /* Main entry point of the GCSE after reload - clean some redundant loads
1290    due to spilling.  */
1291
1292 void
1293 gcse_after_reload_main (rtx f ATTRIBUTE_UNUSED)
1294 {
1295   memset (&stats, 0, sizeof (stats));
1296
1297   /* Allocate ememory for this pass.
1298      Also computes and initializes the insns' CUIDs.  */
1299   alloc_mem ();
1300
1301   /* We need alias analysis.  */
1302   init_alias_analysis ();
1303
1304   compute_hash_table ();
1305
1306   if (dump_file)
1307     dump_hash_table (dump_file);
1308
1309   if (htab_elements (expr_table) > 0)
1310     {
1311       eliminate_partially_redundant_loads ();
1312       delete_redundant_insns ();
1313
1314       if (dump_file)
1315         {
1316           fprintf (dump_file, "GCSE AFTER RELOAD stats:\n");
1317           fprintf (dump_file, "copies inserted: %d\n", stats.copies_inserted);
1318           fprintf (dump_file, "moves inserted:  %d\n", stats.moves_inserted);
1319           fprintf (dump_file, "insns deleted:   %d\n", stats.insns_deleted);
1320           fprintf (dump_file, "\n\n");
1321         }
1322     }
1323
1324   /* We are finished with alias.  */
1325   end_alias_analysis ();
1326
1327   free_mem ();
1328 }
1329