gcc/postreload-gcse.c

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