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
 716       for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
 717         if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
 718           record_last_reg_set_info (insn, regno);
 719
 720       if (! CONST_OR_PURE_CALL_P (insn))
 721         record_last_mem_set_info (insn);
 722     }
 723 }
 724 \f
 725
 726 /* Scan the pattern of INSN and add an entry to the hash TABLE.
 727    After reload we are interested in loads/stores only.  */
 728
 729 static void
 730 hash_scan_set (rtx insn)
 731 {
 732   rtx pat = PATTERN (insn);
 733   rtx src = SET_SRC (pat);
 734   rtx dest = SET_DEST (pat);
 735
 736   /* We are only interested in loads and stores.  */
 737   if (! MEM_P (src) && ! MEM_P (dest))
 738     return;
 739
 740   /* Don't mess with jumps and nops.  */
 741   if (JUMP_P (insn) || set_noop_p (pat))
 742     return;
 743
 744 #ifdef ENABLE_CHEKCING
 745   /* We shouldn't have any EH_REGION notes post reload.  */
 746   if (find_reg_note (insn, REG_EH_REGION, NULL_RTX))
 747     abort ();
 748 #endif
 749
 750   if (REG_P (dest))
 751     {
 752       if (/* Don't CSE something if we can't do a reg/reg copy.  */
 753           can_copy_p (GET_MODE (dest))
 754           /* Is SET_SRC something we want to gcse?  */
 755           && general_operand (src, GET_MODE (src))
 756           /* An expression is not available if its operands are
 757              subsequently modified, including this insn.  */
 758           && oprs_unchanged_p (src, insn, true))
 759         {
 760           insert_expr_in_table (src, insn);
 761         }
 762     }
 763   else if (REG_P (src))
 764     {
 765       /* Only record sets of pseudo-regs in the hash table.  */
 766       if (/* Don't CSE something if we can't do a reg/reg copy.  */
 767           can_copy_p (GET_MODE (src))
 768           /* Is SET_DEST something we want to gcse?  */
 769           && general_operand (dest, GET_MODE (dest))
 770           && ! (flag_float_store && FLOAT_MODE_P (GET_MODE (dest)))
 771           /* Check if the memory expression is killed after insn.  */
 772           && ! load_killed_in_block_p (INSN_CUID (insn) + 1, dest, true)
 773           && oprs_unchanged_p (XEXP (dest, 0), insn, true))
 774         {
 775           insert_expr_in_table (dest, insn);
 776         }
 777     }
 778 }
 779 \f
 780
 781 /* Create hash table of memory expressions available at end of basic
 782    blocks.  Basically you should think of this hash table as the
 783    representation of AVAIL_OUT.  This is the set of expressions that
 784    is generated in a basic block and not killed before the end of the
 785    same basic block.  Notice that this is really a local computation.  */
 786
 787 static void
 788 compute_hash_table (void)
 789 {
 790   basic_block bb;
 791
 792   FOR_EACH_BB (bb)
 793     {
 794       rtx insn;
 795
 796       /* First pass over the instructions records information used to
 797          determine when registers and memory are last set.
 798          Since we compute a "local" AVAIL_OUT, reset the tables that
 799          help us keep track of what has been modified since the start
 800          of the block.  */
 801       reset_opr_set_tables ();
 802       FOR_BB_INSNS (bb, insn)
 803         {
 804           if (INSN_P (insn))
 805             record_opr_changes (insn);
 806         }
 807
 808       /* The next pass actually builds the hash table.  */
 809       FOR_BB_INSNS (bb, insn)
 810         if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == SET)
 811           hash_scan_set (insn);
 812     }
 813 }
 814 \f
 815
 816 /* Check if register REG is killed in any insn waiting to be inserted on
 817    edge E.  This function is required to check that our data flow analysis
 818    is still valid prior to commit_edge_insertions.  */
 819
 820 static bool
 821 reg_killed_on_edge (rtx reg, edge e)
 822 {
 823   rtx insn;
 824
 825   for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
 826     if (INSN_P (insn) && reg_set_p (reg, insn))
 827       return true;
 828
 829   return false;
 830 }
 831
 832 /* Similar to above - check if register REG is used in any insn waiting
 833    to be inserted on edge E.
 834    Assumes no such insn can be a CALL_INSN; if so call reg_used_between_p
 835    with PREV(insn),NEXT(insn) instead of calling reg_overlap_mentioned_p.  */
 836
 837 static bool
 838 reg_used_on_edge (rtx reg, edge e)
 839 {
 840   rtx insn;
 841
 842   for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
 843     if (INSN_P (insn) && reg_overlap_mentioned_p (reg, PATTERN (insn)))
 844       return true;
 845
 846   return false;
 847 }
 848 \f
 849
 850 /* Return the insn that sets register REG or clobbers it in between
 851    FROM_INSN and TO_INSN (exclusive of those two).
 852    Just like reg_set_between but for hard registers and not pseudos.  */
 853
 854 static rtx
 855 reg_set_between_after_reload_p (rtx reg, rtx from_insn, rtx to_insn)
 856 {
 857   rtx insn;
 858
 859 #ifdef ENABLE_CHECKING
 860   /* We are called after register allocation.  */
 861   if (!REG_P (reg) || REGNO (reg) >= FIRST_PSEUDO_REGISTER)
 862     abort ();
 863 #endif
 864
 865   if (from_insn == to_insn)
 866     return NULL_RTX;
 867
 868   for (insn = NEXT_INSN (from_insn);
 869        insn != to_insn;
 870        insn = NEXT_INSN (insn))
 871     if (INSN_P (insn))
 872       {
 873         if (set_of (reg, insn) != NULL_RTX)
 874           return insn;
 875         if ((CALL_P (insn)
 876               && call_used_regs[REGNO (reg)])
 877             || find_reg_fusage (insn, CLOBBER, reg))
 878           return insn;
 879
 880         if (FIND_REG_INC_NOTE (insn, reg))
 881           return insn;
 882       }
 883
 884   return NULL_RTX;
 885 }
 886
 887 /* Return the insn that uses register REG in between FROM_INSN and TO_INSN
 888    (exclusive of those two). Similar to reg_used_between but for hard
 889    registers and not pseudos.  */
 890
 891 static rtx
 892 reg_used_between_after_reload_p (rtx reg, rtx from_insn, rtx to_insn)
 893 {
 894   rtx insn;
 895
 896 #ifdef ENABLE_CHECKING
 897   /* We are called after register allocation.  */
 898   if (!REG_P (reg) || REGNO (reg) >= FIRST_PSEUDO_REGISTER)
 899     abort ();
 900 #endif
 901
 902   if (from_insn == to_insn)
 903     return NULL_RTX;
 904
 905   for (insn = NEXT_INSN (from_insn);
 906        insn != to_insn;
 907        insn = NEXT_INSN (insn))
 908     if (INSN_P (insn))
 909       {
 910         if (reg_overlap_mentioned_p (reg, PATTERN (insn))
 911             || (CALL_P (insn)
 912                 && call_used_regs[REGNO (reg)])
 913             || find_reg_fusage (insn, USE, reg)
 914             || find_reg_fusage (insn, CLOBBER, reg))
 915           return insn;
 916
 917         if (FIND_REG_INC_NOTE (insn, reg))
 918           return insn;
 919       }
 920
 921   return NULL_RTX;
 922 }
 923
 924 /* Return true if REG is used, set, or killed between the beginning of
 925    basic block BB and UP_TO_INSN.  Caches the result in reg_avail_info.  */
 926
 927 static bool
 928 reg_set_or_used_since_bb_start (rtx reg, basic_block bb, rtx up_to_insn)
 929 {
 930   rtx insn, start = PREV_INSN (BB_HEAD (bb));
 931
 932   if (reg_avail_info[REGNO (reg)] != 0)
 933     return true;
 934
 935   insn = reg_used_between_after_reload_p (reg, start, up_to_insn);
 936   if (! insn)
 937     insn = reg_set_between_after_reload_p (reg, start, up_to_insn);
 938
 939   if (insn)
 940     reg_avail_info[REGNO (reg)] = INSN_CUID (insn);
 941
 942   return insn != NULL_RTX;
 943 }
 944
 945 /* Return the loaded/stored register of a load/store instruction.  */
 946
 947 static rtx
 948 get_avail_load_store_reg (rtx insn)
 949 {
 950   if (REG_P (SET_DEST (PATTERN (insn))))  /* A load.  */
 951     return SET_DEST(PATTERN(insn));
 952   if (REG_P (SET_SRC (PATTERN (insn))))  /* A store.  */
 953     return SET_SRC (PATTERN (insn));
 954   abort ();
 955 }
 956
 957 /* Return nonzero if the predecessors of BB are "well behaved".  */
 958
 959 static bool
 960 bb_has_well_behaved_predecessors (basic_block bb)
 961 {
 962   edge pred;
 963   edge_iterator ei;
 964
 965   if (EDGE_COUNT (bb->preds) == 0)
 966     return false;
 967
 968   FOR_EACH_EDGE (pred, ei, bb->preds)
 969     {
 970       if ((pred->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (pred))
 971         return false;
 972
 973       if (JUMP_TABLE_DATA_P (BB_END (pred->src)))
 974         return false;
 975     }
 976   return true;
 977 }
 978
 979
 980 /* Search for the occurrences of expression in BB.  */
 981
 982 static struct occr*
 983 get_bb_avail_insn (basic_block bb, struct occr *occr)
 984 {
 985   for (; occr != NULL; occr = occr->next)
 986     if (BLOCK_FOR_INSN (occr->insn) == bb)
 987       return occr;
 988   return NULL;
 989 }
 990
 991
 992 /* This handles the case where several stores feed a partially redundant
 993    load. It checks if the redundancy elimination is possible and if it's
 994    worth it.
 995
 996    Redundancy elimination is possible if,
 997    1) None of the operands of an insn have been modified since the start
 998       of the current basic block.
 999    2) In any predecessor of the current basic block, the same expression
1000       is generated.
1001
1002    See the function body for the heuristics that determine if eliminating
1003    a redundancy is also worth doing, assuming it is possible.  */
1004
1005 static void
1006 eliminate_partially_redundant_load (basic_block bb, rtx insn,
1007                                     struct expr *expr)
1008 {
1009   edge pred;
1010   rtx avail_insn = NULL_RTX;
1011   rtx avail_reg;
1012   rtx dest, pat;
1013   struct occr *a_occr;
1014   struct unoccr *occr, *avail_occrs = NULL;
1015   struct unoccr *unoccr, *unavail_occrs = NULL, *rollback_unoccr = NULL;
1016   int npred_ok = 0;
1017   gcov_type ok_count = 0; /* Redundant load execution count.  */
1018   gcov_type critical_count = 0; /* Execution count of critical edges.  */
1019   edge_iterator ei;
1020
1021   /* The execution count of the loads to be added to make the
1022      load fully redundant.  */
1023   gcov_type not_ok_count = 0;
1024   basic_block pred_bb;
1025
1026   pat = PATTERN (insn);
1027   dest = SET_DEST (pat);
1028
1029   /* Check that the loaded register is not used, set, or killed from the
1030      beginning of the block.  */
1031   if (reg_set_or_used_since_bb_start (dest, bb, insn))
1032     return;
1033
1034   /* Check potential for replacing load with copy for predecessors.  */
1035   FOR_EACH_EDGE (pred, ei, bb->preds)
1036     {
1037       rtx next_pred_bb_end;
1038
1039       avail_insn = NULL_RTX;
1040       pred_bb = pred->src;
1041       next_pred_bb_end = NEXT_INSN (BB_END (pred_bb));
1042       for (a_occr = get_bb_avail_insn (pred_bb, expr->avail_occr); a_occr;
1043            a_occr = get_bb_avail_insn (pred_bb, a_occr->next))
1044         {
1045           /* Check if the loaded register is not used.  */
1046           avail_insn = a_occr->insn;
1047           if (! (avail_reg = get_avail_load_store_reg (avail_insn)))
1048             abort ();
1049           /* Make sure we can generate a move from register avail_reg to
1050              dest.  */
1051           extract_insn (gen_move_insn (copy_rtx (dest),
1052                                        copy_rtx (avail_reg)));
1053           if (! constrain_operands (1)
1054               || reg_killed_on_edge (avail_reg, pred)
1055               || reg_used_on_edge (dest, pred))
1056             {
1057               avail_insn = NULL;
1058               continue;
1059             }
1060           if (! reg_set_between_after_reload_p (avail_reg, avail_insn,
1061                                                 next_pred_bb_end))
1062             /* AVAIL_INSN remains non-null.  */
1063             break;
1064           else
1065             avail_insn = NULL;
1066         }
1067
1068       if (EDGE_CRITICAL_P (pred))
1069         critical_count += pred->count;
1070
1071       if (avail_insn != NULL_RTX)
1072         {
1073           npred_ok++;
1074           ok_count += pred->count;
1075           occr = (struct unoccr *) obstack_alloc (&unoccr_obstack,
1076                                                   sizeof (struct occr));
1077           occr->insn = avail_insn;
1078           occr->pred = pred;
1079           occr->next = avail_occrs;
1080           avail_occrs = occr;
1081           if (! rollback_unoccr)
1082             rollback_unoccr = occr;
1083         }
1084       else
1085         {
1086           not_ok_count += pred->count;
1087           unoccr = (struct unoccr *) obstack_alloc (&unoccr_obstack,
1088                                                     sizeof (struct unoccr));
1089           unoccr->insn = NULL_RTX;
1090           unoccr->pred = pred;
1091           unoccr->next = unavail_occrs;
1092           unavail_occrs = unoccr;
1093           if (! rollback_unoccr)
1094             rollback_unoccr = unoccr;
1095         }
1096     }
1097
1098   if (/* No load can be replaced by copy.  */
1099       npred_ok == 0
1100       /* Prevent exploding the code.  */
1101       || (optimize_size && npred_ok > 1))
1102     goto cleanup;
1103
1104   /* Check if it's worth applying the partial redundancy elimination.  */
1105   if (ok_count < GCSE_AFTER_RELOAD_PARTIAL_FRACTION * not_ok_count)
1106     goto cleanup;
1107   if (ok_count < GCSE_AFTER_RELOAD_CRITICAL_FRACTION * critical_count)
1108     goto cleanup;
1109
1110   /* Generate moves to the loaded register from where
1111      the memory is available.  */
1112   for (occr = avail_occrs; occr; occr = occr->next)
1113     {
1114       avail_insn = occr->insn;
1115       pred = occr->pred;
1116       /* Set avail_reg to be the register having the value of the
1117          memory.  */
1118       avail_reg = get_avail_load_store_reg (avail_insn);
1119       if (! avail_reg)
1120         abort ();
1121
1122       insert_insn_on_edge (gen_move_insn (copy_rtx (dest),
1123                                           copy_rtx (avail_reg)),
1124                            pred);
1125       stats.moves_inserted++;
1126
1127       if (dump_file)
1128         fprintf (dump_file,
1129                  "generating move from %d to %d on edge from %d to %d\n",
1130                  REGNO (avail_reg),
1131                  REGNO (dest),
1132                  pred->src->index,
1133                  pred->dest->index);
1134     }
1135
1136   /* Regenerate loads where the memory is unavailable.  */
1137   for (unoccr = unavail_occrs; unoccr; unoccr = unoccr->next)
1138     {
1139       pred = unoccr->pred;
1140       insert_insn_on_edge (copy_insn (PATTERN (insn)), pred);
1141       stats.copies_inserted++;
1142
1143       if (dump_file)
1144         {
1145           fprintf (dump_file,
1146                    "generating on edge from %d to %d a copy of load: ",
1147                    pred->src->index,
1148                    pred->dest->index);
1149           print_rtl (dump_file, PATTERN (insn));
1150           fprintf (dump_file, "\n");
1151         }
1152     }
1153
1154   /* Delete the insn if it is not available in this block and mark it
1155      for deletion if it is available. If insn is available it may help
1156      discover additional redundancies, so mark it for later deletion.  */
1157   for (a_occr = get_bb_avail_insn (bb, expr->avail_occr);
1158        a_occr && (a_occr->insn != insn);
1159        a_occr = get_bb_avail_insn (bb, a_occr->next));
1160
1161   if (!a_occr)
1162     delete_insn (insn);
1163   else
1164     a_occr->deleted_p = 1;
1165
1166 cleanup:
1167   if (rollback_unoccr)
1168     obstack_free (&unoccr_obstack, rollback_unoccr);
1169 }
1170
1171 /* Performing the redundancy elimination as described before.  */
1172
1173 static void
1174 eliminate_partially_redundant_loads (void)
1175 {
1176   rtx insn;
1177   basic_block bb;
1178
1179   /* Note we start at block 1.  */
1180
1181   if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
1182     return;
1183
1184   FOR_BB_BETWEEN (bb,
1185                   ENTRY_BLOCK_PTR->next_bb->next_bb,
1186                   EXIT_BLOCK_PTR,
1187                   next_bb)
1188     {
1189       /* Don't try anything on basic blocks with strange predecessors.  */
1190       if (! bb_has_well_behaved_predecessors (bb))
1191         continue;
1192
1193       /* Do not try anything on cold basic blocks.  */
1194       if (probably_cold_bb_p (bb))
1195         continue;
1196
1197       /* Reset the table of things changed since the start of the current
1198          basic block.  */
1199       reset_opr_set_tables ();
1200
1201       /* Look at all insns in the current basic block and see if there are
1202          any loads in it that we can record.  */
1203       FOR_BB_INSNS (bb, insn)
1204         {
1205           /* Is it a load - of the form (set (reg) (mem))?  */
1206           if (NONJUMP_INSN_P (insn)
1207               && GET_CODE (PATTERN (insn)) == SET
1208               && REG_P (SET_DEST (PATTERN (insn)))
1209               && MEM_P (SET_SRC (PATTERN (insn))))
1210             {
1211               rtx pat = PATTERN (insn);
1212               rtx src = SET_SRC (pat);
1213               struct expr *expr;
1214
1215               if (!MEM_VOLATILE_P (src)
1216                   && GET_MODE (src) != BLKmode
1217                   && general_operand (src, GET_MODE (src))
1218                   /* Are the operands unchanged since the start of the
1219                      block?  */
1220                   && oprs_unchanged_p (src, insn, false)
1221                   && !(flag_non_call_exceptions && may_trap_p (src))
1222                   && !side_effects_p (src)
1223                   /* Is the expression recorded?  */
1224                   && (expr = lookup_expr_in_table (src)) != NULL)
1225                 {
1226                   /* We now have a load (insn) and an available memory at
1227                      its BB start (expr). Try to remove the loads if it is
1228                      redundant.  */
1229                   eliminate_partially_redundant_load (bb, insn, expr);
1230                 }
1231             }
1232
1233           /* Keep track of everything modified by this insn, so that we
1234              know what has been modified since the start of the current
1235              basic block.  */
1236           if (INSN_P (insn))
1237             record_opr_changes (insn);
1238         }
1239     }
1240
1241   commit_edge_insertions ();
1242 }
1243
1244 /* Go over the expression hash table and delete insns that were
1245    marked for later deletion.  */
1246
1247 /* This helper is called via htab_traverse.  */
1248 static int
1249 delete_redundant_insns_1 (void **slot, void *data ATTRIBUTE_UNUSED)
1250 {
1251   struct expr *expr = (struct expr *) *slot;
1252   struct occr *occr;
1253
1254   for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
1255     {
1256       if (occr->deleted_p)
1257         {
1258           delete_insn (occr->insn);
1259           stats.insns_deleted++;
1260
1261           if (dump_file)
1262             {
1263               fprintf (dump_file, "deleting insn:\n");
1264               print_rtl_single (dump_file, occr->insn);
1265               fprintf (dump_file, "\n");
1266             }
1267         }
1268     }
1269
1270   return 1;
1271 }
1272
1273 static void
1274 delete_redundant_insns (void)
1275 {
1276   htab_traverse (expr_table, delete_redundant_insns_1, NULL);
1277   if (dump_file)
1278     fprintf (dump_file, "\n");
1279 }
1280
1281 /* Main entry point of the GCSE after reload - clean some redundant loads
1282    due to spilling.  */
1283
1284 void
1285 gcse_after_reload_main (rtx f ATTRIBUTE_UNUSED)
1286 {
1287   memset (&stats, 0, sizeof (stats));
1288
1289   /* Allocate ememory for this pass.
1290      Also computes and initializes the insns' CUIDs.  */
1291   alloc_mem ();
1292
1293   /* We need alias analysis.  */
1294   init_alias_analysis ();
1295
1296   compute_hash_table ();
1297
1298   if (dump_file)
1299     dump_hash_table (dump_file);
1300
1301   if (htab_elements (expr_table) > 0)
1302     {
1303       eliminate_partially_redundant_loads ();
1304       delete_redundant_insns ();
1305
1306       if (dump_file)
1307         {
1308           fprintf (dump_file, "GCSE AFTER RELOAD stats:\n");
1309           fprintf (dump_file, "copies inserted: %d\n", stats.copies_inserted);
1310           fprintf (dump_file, "moves inserted:  %d\n", stats.moves_inserted);
1311           fprintf (dump_file, "insns deleted:   %d\n", stats.insns_deleted);
1312           fprintf (dump_file, "\n\n");
1313         }
1314     }
1315
1316   /* We are finished with alias.  */
1317   end_alias_analysis ();
1318
1319   free_mem ();
1320 }
1321