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