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
 972   if (! bb->pred)
 973     return false;
 974
 975   for (pred = bb->pred; pred != NULL; pred = pred->pred_next)
 976     {
 977       if ((pred->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (pred))
 978         return false;
 979
 980       if (JUMP_TABLE_DATA_P (BB_END (pred->src)))
 981         return false;
 982     }
 983   return true;
 984 }
 985
 986
 987 /* Search for the occurrences of expression in BB.  */
 988
 989 static struct occr*
 990 get_bb_avail_insn (basic_block bb, struct occr *occr)
 991 {
 992   for (; occr != NULL; occr = occr->next)
 993     if (BLOCK_FOR_INSN (occr->insn) == bb)
 994       return occr;
 995   return NULL;
 996 }
 997
 998
 999 /* This handles the case where several stores feed a partially redundant
1000    load. It checks if the redundancy elimination is possible and if it's
1001    worth it.
1002
1003    Redundancy elimination is possible if,
1004    1) None of the operands of an insn have been modified since the start
1005       of the current basic block.
1006    2) In any predecessor of the current basic block, the same expression
1007       is generated.
1008
1009    See the function body for the heuristics that determine if eliminating
1010    a redundancy is also worth doing, assuming it is possible.  */
1011
1012 static void
1013 eliminate_partially_redundant_load (basic_block bb, rtx insn,
1014                                     struct expr *expr)
1015 {
1016   edge pred;
1017   rtx avail_insn = NULL_RTX;
1018   rtx avail_reg;
1019   rtx dest, pat;
1020   struct occr *a_occr;
1021   struct unoccr *occr, *avail_occrs = NULL;
1022   struct unoccr *unoccr, *unavail_occrs = NULL, *rollback_unoccr = NULL;
1023   int npred_ok = 0;
1024   gcov_type ok_count = 0; /* Redundant load execution count.  */
1025   gcov_type critical_count = 0; /* Execution count of critical edges.  */
1026
1027   /* The execution count of the loads to be added to make the
1028      load fully redundant.  */
1029   gcov_type not_ok_count = 0;
1030   basic_block pred_bb;
1031
1032   pat = PATTERN (insn);
1033   dest = SET_DEST (pat);
1034
1035   /* Check that the loaded register is not used, set, or killed from the
1036      beginning of the block.  */
1037   if (reg_set_or_used_since_bb_start (dest, bb, insn))
1038     return;
1039
1040   /* Check potential for replacing load with copy for predecessors.  */
1041   for (pred = bb->pred; pred; pred = pred->pred_next)
1042     {
1043       rtx next_pred_bb_end;
1044
1045       avail_insn = NULL_RTX;
1046       pred_bb = pred->src;
1047       next_pred_bb_end = NEXT_INSN (BB_END (pred_bb));
1048       for (a_occr = get_bb_avail_insn (pred_bb, expr->avail_occr); a_occr;
1049            a_occr = get_bb_avail_insn (pred_bb, a_occr->next))
1050         {
1051           /* Check if the loaded register is not used.  */
1052           avail_insn = a_occr->insn;
1053           if (! (avail_reg = get_avail_load_store_reg (avail_insn)))
1054             abort ();
1055           /* Make sure we can generate a move from register avail_reg to
1056              dest.  */
1057           extract_insn (gen_move_insn (copy_rtx (dest),
1058                                        copy_rtx (avail_reg)));
1059           if (! constrain_operands (1)
1060               || reg_killed_on_edge (avail_reg, pred)
1061               || reg_used_on_edge (dest, pred))
1062             {
1063               avail_insn = NULL;
1064               continue;
1065             }
1066           if (! reg_set_between_after_reload_p (avail_reg, avail_insn,
1067                                                 next_pred_bb_end))
1068             /* AVAIL_INSN remains non-null.  */
1069             break;
1070           else
1071             avail_insn = NULL;
1072         }
1073
1074       if (EDGE_CRITICAL_P (pred))
1075         critical_count += pred->count;
1076
1077       if (avail_insn != NULL_RTX)
1078         {
1079           npred_ok++;
1080           ok_count += pred->count;
1081           occr = (struct unoccr *) obstack_alloc (&unoccr_obstack,
1082                                                   sizeof (struct occr));
1083           occr->insn = avail_insn;
1084           occr->pred = pred;
1085           occr->next = avail_occrs;
1086           avail_occrs = occr;
1087           if (! rollback_unoccr)
1088             rollback_unoccr = occr;
1089         }
1090       else
1091         {
1092           not_ok_count += pred->count;
1093           unoccr = (struct unoccr *) obstack_alloc (&unoccr_obstack,
1094                                                     sizeof (struct unoccr));
1095           unoccr->insn = NULL_RTX;
1096           unoccr->pred = pred;
1097           unoccr->next = unavail_occrs;
1098           unavail_occrs = unoccr;
1099           if (! rollback_unoccr)
1100             rollback_unoccr = unoccr;
1101         }
1102     }
1103
1104   if (/* No load can be replaced by copy.  */
1105       npred_ok == 0
1106       /* Prevent exploding the code.  */
1107       || (optimize_size && npred_ok > 1))
1108     goto cleanup;
1109
1110   /* Check if it's worth applying the partial redundancy elimination.  */
1111   if (ok_count < GCSE_AFTER_RELOAD_PARTIAL_FRACTION * not_ok_count)
1112     goto cleanup;
1113   if (ok_count < GCSE_AFTER_RELOAD_CRITICAL_FRACTION * critical_count)
1114     goto cleanup;
1115
1116   /* Generate moves to the loaded register from where
1117      the memory is available.  */
1118   for (occr = avail_occrs; occr; occr = occr->next)
1119     {
1120       avail_insn = occr->insn;
1121       pred = occr->pred;
1122       /* Set avail_reg to be the register having the value of the
1123          memory.  */
1124       avail_reg = get_avail_load_store_reg (avail_insn);
1125       if (! avail_reg)
1126         abort ();
1127
1128       insert_insn_on_edge (gen_move_insn (copy_rtx (dest),
1129                                           copy_rtx (avail_reg)),
1130                            pred);
1131       stats.moves_inserted++;
1132
1133       if (dump_file)
1134         fprintf (dump_file,
1135                  "generating move from %d to %d on edge from %d to %d\n",
1136                  REGNO (avail_reg),
1137                  REGNO (dest),
1138                  pred->src->index,
1139                  pred->dest->index);
1140     }
1141
1142   /* Regenerate loads where the memory is unavailable.  */
1143   for (unoccr = unavail_occrs; unoccr; unoccr = unoccr->next)
1144     {
1145       pred = unoccr->pred;
1146       insert_insn_on_edge (copy_insn (PATTERN (insn)), pred);
1147       stats.copies_inserted++;
1148
1149       if (dump_file)
1150         {
1151           fprintf (dump_file,
1152                    "generating on edge from %d to %d a copy of load: ",
1153                    pred->src->index,
1154                    pred->dest->index);
1155           print_rtl (dump_file, PATTERN (insn));
1156           fprintf (dump_file, "\n");
1157         }
1158     }
1159
1160   /* Delete the insn if it is not available in this block and mark it
1161      for deletion if it is available. If insn is available it may help
1162      discover additional redundancies, so mark it for later deletion.  */
1163   for (a_occr = get_bb_avail_insn (bb, expr->avail_occr);
1164        a_occr && (a_occr->insn != insn);
1165        a_occr = get_bb_avail_insn (bb, a_occr->next));
1166
1167   if (!a_occr)
1168     delete_insn (insn);
1169   else
1170     a_occr->deleted_p = 1;
1171
1172 cleanup:
1173   if (rollback_unoccr)
1174     obstack_free (&unoccr_obstack, rollback_unoccr);
1175 }
1176
1177 /* Performing the redundancy elimination as described before.  */
1178
1179 static void
1180 eliminate_partially_redundant_loads (void)
1181 {
1182   rtx insn;
1183   basic_block bb;
1184
1185   /* Note we start at block 1.  */
1186
1187   if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
1188     return;
1189
1190   FOR_BB_BETWEEN (bb,
1191                   ENTRY_BLOCK_PTR->next_bb->next_bb,
1192                   EXIT_BLOCK_PTR,
1193                   next_bb)
1194     {
1195       /* Don't try anything on basic blocks with strange predecessors.  */
1196       if (! bb_has_well_behaved_predecessors (bb))
1197         continue;
1198
1199       /* Do not try anything on cold basic blocks.  */
1200       if (probably_cold_bb_p (bb))
1201         continue;
1202
1203       /* Reset the table of things changed since the start of the current
1204          basic block.  */
1205       reset_opr_set_tables ();
1206
1207       /* Look at all insns in the current basic block and see if there are
1208          any loads in it that we can record.  */
1209       FOR_BB_INSNS (bb, insn)
1210         {
1211           /* Is it a load - of the form (set (reg) (mem))?  */
1212           if (NONJUMP_INSN_P (insn)
1213               && GET_CODE (PATTERN (insn)) == SET
1214               && REG_P (SET_DEST (PATTERN (insn)))
1215               && MEM_P (SET_SRC (PATTERN (insn))))
1216             {
1217               rtx pat = PATTERN (insn);
1218               rtx src = SET_SRC (pat);
1219               struct expr *expr;
1220
1221               if (!MEM_VOLATILE_P (src)
1222                   && GET_MODE (src) != BLKmode
1223                   && general_operand (src, GET_MODE (src))
1224                   /* Are the operands unchanged since the start of the
1225                      block?  */
1226                   && oprs_unchanged_p (src, insn, false)
1227                   && !(flag_non_call_exceptions && may_trap_p (src))
1228                   && !side_effects_p (src)
1229                   /* Is the expression recorded?  */
1230                   && (expr = lookup_expr_in_table (src)) != NULL)
1231                 {
1232                   /* We now have a load (insn) and an available memory at
1233                      its BB start (expr). Try to remove the loads if it is
1234                      redundant.  */
1235                   eliminate_partially_redundant_load (bb, insn, expr);
1236                 }
1237             }
1238
1239           /* Keep track of everything modified by this insn, so that we
1240              know what has been modified since the start of the current
1241              basic block.  */
1242           if (INSN_P (insn))
1243             record_opr_changes (insn);
1244         }
1245     }
1246
1247   commit_edge_insertions ();
1248 }
1249
1250 /* Go over the expression hash table and delete insns that were
1251    marked for later deletion.  */
1252
1253 /* This helper is called via htab_traverse.  */
1254 static int
1255 delete_redundant_insns_1 (void **slot, void *data ATTRIBUTE_UNUSED)
1256 {
1257   struct expr *expr = (struct expr *) *slot;
1258   struct occr *occr;
1259
1260   for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
1261     {
1262       if (occr->deleted_p)
1263         {
1264           delete_insn (occr->insn);
1265           stats.insns_deleted++;
1266
1267           if (dump_file)
1268             {
1269               fprintf (dump_file, "deleting insn:\n");
1270               print_rtl_single (dump_file, occr->insn);
1271               fprintf (dump_file, "\n");
1272             }
1273         }
1274     }
1275
1276   return 1;
1277 }
1278
1279 static void
1280 delete_redundant_insns (void)
1281 {
1282   htab_traverse (expr_table, delete_redundant_insns_1, NULL);
1283   if (dump_file)
1284     fprintf (dump_file, "\n");
1285 }
1286
1287 /* Main entry point of the GCSE after reload - clean some redundant loads
1288    due to spilling.  */
1289
1290 void
1291 gcse_after_reload_main (rtx f ATTRIBUTE_UNUSED)
1292 {
1293   memset (&stats, 0, sizeof (stats));
1294
1295   /* Allocate ememory for this pass.
1296      Also computes and initializes the insns' CUIDs.  */
1297   alloc_mem ();
1298
1299   /* We need alias analysis.  */
1300   init_alias_analysis ();
1301
1302   compute_hash_table ();
1303
1304   if (dump_file)
1305     dump_hash_table (dump_file);
1306
1307   if (htab_elements (expr_table) > 0)
1308     {
1309       eliminate_partially_redundant_loads ();
1310       delete_redundant_insns ();
1311
1312       if (dump_file)
1313         {
1314           fprintf (dump_file, "GCSE AFTER RELOAD stats:\n");
1315           fprintf (dump_file, "copies inserted: %d\n", stats.copies_inserted);
1316           fprintf (dump_file, "moves inserted:  %d\n", stats.moves_inserted);
1317           fprintf (dump_file, "insns deleted:   %d\n", stats.insns_deleted);
1318           fprintf (dump_file, "\n\n");
1319         }
1320     }
1321
1322   /* We are finished with alias.  */
1323   end_alias_analysis ();
1324
1325   free_mem ();
1326 }
1327