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