gcc/rtl-factoring.c

   1 /* RTL factoring (sequence abstraction).
   2    Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "rtl.h"
  26 #include "obstack.h"
  27 #include "basic-block.h"
  28 #include "resource.h"
  29 #include "flags.h"
  30 #include "ggc.h"
  31 #include "regs.h"
  32 #include "params.h"
  33 #include "expr.h"
  34 #include "tm_p.h"
  35 #include "tree-pass.h"
  36 #include "tree-flow.h"
  37 #include "timevar.h"
  38 #include "output.h"
  39 #include "df.h"
  40 #include "addresses.h"
  41
  42 /* Sequence abstraction:
  43
  44    It is a size optimization method. The main idea of this technique is to
  45    find identical sequences of code, which can be turned into procedures and
  46    then replace all occurrences with calls to the newly created subroutine.
  47    It is kind of an opposite of function inlining.
  48
  49    There are four major parts of this file:
  50
  51    sequence fingerprint
  52      In order to avoid the comparison of every insn with every other, hash
  53      value will be designed for every insn by COMPUTE_HASH.
  54      These hash values are used for grouping the sequence candidates. So
  55      we only need to compare every insn with every other in same hash group.
  56
  57      FILL_HASH_BUCKET creates all hash values and stores into HASH_BUCKETS.
  58      The result is used by COLLECT_PATTERN_SEQS.
  59
  60    code matching
  61      In code matching the algorithm compares every two possible sequence
  62      candidates which last insns are in the same hash group. If these
  63      sequences are identical they will be stored and do further searches for
  64      finding more sequences which are identical with the first one.
  65
  66      COLLECT_PATTERN_SEQS does the code matching and stores the results into
  67      PATTERN_SEQS.
  68
  69    gain computation
  70      This part computes the gain of abstraction which could be archived when
  71      turning the pattern sequence into a pseudo-function and its matching
  72      sequences into pseudo-calls. After it the most effective sequences will
  73      be marked for abstraction.
  74
  75      RECOMPUTE_GAIN does the gain computation. The sequences with the maximum
  76      gain is on the top of PATTERN_SEQS.
  77
  78    abstract code
  79      This part turns the pattern sequence into a pseudo-function and its
  80      matching sequences into pseudo-calls.
  81
  82      ABSTRACT_BEST_SEQ does the code merging.
  83
  84
  85    C code example:
  86
  87    // Original source            // After sequence abstraction
  88    {                             {
  89                                    void *jump_label;
  90      ...                           ...
  91                                    jump_label = &&exit_0;
  92                                  entry_0:
  93      I0;                           I0;
  94      I1;                           I1;
  95      I2;                           I2;
  96      I3;                           I3;
  97                                    goto *jump_label;
  98                                  exit_0:
  99      ...                           ...
 100                                    jump_label = &&exit_1;
 101                                  goto entry_0;
 102      I0;
 103      I1;
 104      I2;
 105      I3;
 106                                  exit_1:
 107      ...                           ...
 108                                    jump_label = &&exit_2;
 109                                    goto entry_0;
 110      I0;
 111      I1;
 112      I2;
 113      I3;
 114                                  exit_2:
 115      ...                           ...
 116                                    jump_label = &&exit_3;
 117                                    goto entry_0;
 118      I0;
 119      I1;
 120      I2;
 121      I3;
 122                                 exit_3:
 123      ...                           ...
 124    }                             }
 125
 126
 127    TODO:
 128    - Use REG_ALLOC_ORDER when choosing link register.
 129    - Handle JUMP_INSNs. Also handle volatile function calls (handle them
 130      similar to unconditional jumps.)
 131    - Test command line option -fpic.
 132 */
 133
 134 /* Predicate yielding nonzero iff X is an abstractable insn.  Non-jump insns are
 135    abstractable.  */
 136 #define ABSTRACTABLE_INSN_P(X) (INSN_P (X) && !JUMP_P (X))
 137
 138 /* First parameter of the htab_create function call.  */
 139 #define HASH_INIT 1023
 140
 141 /* Multiplier for cost of sequence call to avoid abstracting short
 142    sequences.  */
 143 #ifndef SEQ_CALL_COST_MULTIPLIER
 144 #define SEQ_CALL_COST_MULTIPLIER 2
 145 #endif
 146
 147 /* Recomputes the cost of MSEQ pattern/matching sequence.  */
 148 #define RECOMPUTE_COST(SEQ)                                 \
 149 {                                                           \
 150   int l;                                                    \
 151   rtx x = SEQ->insn;                                        \
 152   SEQ->cost = 0;                                            \
 153   for (l = 0; l < SEQ->abstracted_length; l++)              \
 154     {                                                       \
 155       SEQ->cost += compute_rtx_cost (x);                    \
 156       x = prev_insn_in_block (x);                           \
 157     }                                                       \
 158 }
 159
 160 /* A sequence matching a pattern sequence.  */
 161 typedef struct matching_seq_def
 162 {
 163   /* The last insn in the matching sequence.  */
 164   rtx insn;
 165
 166   /* Index of INSN instruction.  */
 167   unsigned long idx;
 168
 169   /* The number of insns matching in this sequence and the pattern sequence.
 170    */
 171   int matching_length;
 172
 173   /* The number of insns selected to abstract from this sequence. Less than
 174      or equal to MATCHING_LENGTH.  */
 175   int abstracted_length;
 176
 177   /* The cost of the sequence.  */
 178   int cost;
 179
 180   /* The next sequence in the chain matching the same pattern.  */
 181   struct matching_seq_def *next_matching_seq;
 182 } *matching_seq;
 183
 184
 185 /* A pattern instruction sequence.  */
 186 typedef struct pattern_seq_def
 187 {
 188   /* The last insn in the pattern sequence.  */
 189   rtx insn;
 190
 191   /* Index of INSN instruction.  */
 192   unsigned long idx;
 193
 194   /* The gain of transforming the pattern sequence into a pseudo-function and
 195      the matching sequences into pseudo-calls.  */
 196   int gain;
 197
 198   /* The maximum of the ABSTRACTED_LENGTH of the matching sequences.  */
 199   int abstracted_length;
 200
 201   /* The cost of the sequence.  */
 202   int cost;
 203
 204   /* The register used to hold the return address during the pseudo-call.  */
 205   rtx link_reg;
 206
 207   /* The sequences matching this pattern.  */
 208   matching_seq matching_seqs;
 209
 210   /* The next pattern sequence in the chain.  */
 211   struct pattern_seq_def *next_pattern_seq;
 212 } *pattern_seq;
 213
 214
 215 /* A block of a pattern sequence.  */
 216 typedef struct seq_block_def
 217 {
 218   /* The number of insns in the block.  */
 219   int length;
 220
 221   /* The code_label of the block.  */
 222   rtx label;
 223
 224   /* The sequences entering the pattern sequence at LABEL.  */
 225   matching_seq matching_seqs;
 226
 227   /* The next block in the chain. The blocks are sorted by LENGTH in
 228      ascending order.  */
 229   struct seq_block_def *next_seq_block;
 230 } *seq_block;
 231
 232 /* Contains same sequence candidates for further searching.  */
 233 typedef struct hash_bucket_def
 234 {
 235   /* The hash value of the group.  */
 236   unsigned int hash;
 237
 238   /* List of sequence candidates.  */
 239   htab_t seq_candidates;
 240 } *p_hash_bucket;
 241 typedef const struct hash_bucket_def *const_p_hash_bucket;
 242
 243 /* Contains the last insn of the sequence, and its index value.  */
 244 typedef struct hash_elem_def
 245 {
 246   /* Unique index; ordered by FILL_HASH_BUCKET.  */
 247   unsigned long idx;
 248
 249   /* The last insn in the sequence.  */
 250   rtx insn;
 251
 252   /* The cached length of the insn.  */
 253   int length;
 254 } *p_hash_elem;
 255 typedef const struct hash_elem_def *const_p_hash_elem;
 256
 257 /* The list of same sequence candidates.  */
 258 static htab_t hash_buckets;
 259
 260 /* The pattern sequences collected from the current functions.  */
 261 static pattern_seq pattern_seqs;
 262
 263 /* The blocks of the current pattern sequence.  */
 264 static seq_block seq_blocks;
 265
 266 /* Cost of calling sequence.  */
 267 static int seq_call_cost;
 268
 269 /* Cost of jump.  */
 270 static int seq_jump_cost;
 271
 272 /* Cost of returning.  */
 273 static int seq_return_cost;
 274
 275 /* Returns the first insn preceding INSN for which INSN_P is true and belongs to
 276    the same basic block. Returns NULL_RTX if no such insn can be found.  */
 277
 278 static rtx
 279 prev_insn_in_block (rtx insn)
 280 {
 281   basic_block bb = BLOCK_FOR_INSN (insn);
 282
 283   if (!bb)
 284     return NULL_RTX;
 285
 286   while (insn != BB_HEAD (bb))
 287     {
 288       insn = PREV_INSN (insn);
 289       if (INSN_P (insn))
 290         return insn;
 291     }
 292   return NULL_RTX;
 293 }
 294
 295 /* Returns the hash value of INSN.  */
 296
 297 static unsigned int
 298 compute_hash (rtx insn)
 299 {
 300   unsigned int hash = 0;
 301   rtx prev;
 302
 303   hash = INSN_CODE (insn) * 100;
 304
 305   prev = prev_insn_in_block (insn);
 306   if (prev)
 307     hash += INSN_CODE (prev);
 308
 309   return hash;
 310 }
 311
 312 /* Compute the cost of INSN rtx for abstraction.  */
 313
 314 static int
 315 compute_rtx_cost (rtx insn)
 316 {
 317   struct hash_bucket_def tmp_bucket;
 318   p_hash_bucket bucket;
 319   struct hash_elem_def tmp_elem;
 320   p_hash_elem elem = NULL;
 321   int cost = -1;
 322
 323   /* Compute hash value for INSN.  */
 324   tmp_bucket.hash = compute_hash (insn);
 325
 326   /* Select the hash group.  */
 327   bucket = htab_find (hash_buckets, &tmp_bucket);
 328
 329   if (bucket)
 330   {
 331     tmp_elem.insn = insn;
 332
 333     /* Select the insn.  */
 334     elem = htab_find (bucket->seq_candidates, &tmp_elem);
 335
 336     /* If INSN is parsed the cost will be the cached length.  */
 337     if (elem)
 338       cost = elem->length;
 339   }
 340
 341   /* If we can't parse the INSN cost will be the instruction length.  */
 342   if (cost == -1)
 343   {
 344     cost = get_attr_length (insn);
 345
 346     /* Cache the length.  */
 347     if (elem)
 348       elem->length = cost;
 349   }
 350
 351   /* If we can't get an accurate estimate for a complex instruction,
 352      assume that it has the same cost as a single fast instruction.  */
 353   return cost != 0 ? cost : COSTS_N_INSNS (1);
 354 }
 355
 356 /* Determines the number of common insns in the sequences ending in INSN1 and
 357    INSN2. Returns with LEN number of common insns and COST cost of sequence.
 358 */
 359
 360 static void
 361 matching_length (rtx insn1, rtx insn2, int* len, int* cost)
 362 {
 363   rtx x1;
 364   rtx x2;
 365
 366   x1 = insn1;
 367   x2 = insn2;
 368   *len = 0;
 369   *cost = 0;
 370   while (x1 && x2 && (x1 != insn2) && (x2 != insn1)
 371          && rtx_equal_p (PATTERN (x1), PATTERN (x2)))
 372     {
 373       (*len)++;
 374       (*cost) += compute_rtx_cost (x1);
 375       x1 = prev_insn_in_block (x1);
 376       x2 = prev_insn_in_block (x2);
 377     }
 378 }
 379
 380 /* Adds E0 as a pattern sequence to PATTERN_SEQS with E1 as a matching
 381    sequence.  */
 382
 383 static void
 384 match_seqs (p_hash_elem e0, p_hash_elem e1)
 385 {
 386   int len;
 387   int cost;
 388   matching_seq mseq, p_prev, p_next;
 389
 390   /* Determines the cost of the sequence and return without doing anything
 391      if it is too small to produce any gain.  */
 392   matching_length (e0->insn, e1->insn, &len, &cost);
 393   if (cost <= seq_call_cost)
 394     return;
 395
 396   /* Prepend a new PATTERN_SEQ to PATTERN_SEQS if the last pattern sequence
 397      does not end in E0->INSN. This assumes that once the E0->INSN changes
 398      the old value will never appear again.  */
 399   if (!pattern_seqs || pattern_seqs->insn != e0->insn)
 400     {
 401       pattern_seq pseq =
 402         (pattern_seq) xmalloc (sizeof (struct pattern_seq_def));
 403       pseq->insn = e0->insn;
 404       pseq->idx = e0->idx;
 405       pseq->gain = 0;                 /* Set to zero to force recomputing.  */
 406       pseq->abstracted_length = 0;
 407       pseq->cost = 0;
 408       pseq->link_reg = NULL_RTX;
 409       pseq->matching_seqs = NULL;
 410       pseq->next_pattern_seq = pattern_seqs;
 411       pattern_seqs = pseq;
 412     }
 413
 414   /* Find the position of E1 in the matching sequences list.  */
 415   p_prev = NULL;
 416   p_next = pattern_seqs->matching_seqs;
 417   while (p_next && p_next->idx < e1->idx)
 418     {
 419       p_prev = p_next;
 420       p_next = p_next->next_matching_seq;
 421     }
 422
 423   /* Add a new E1 matching sequence to the pattern sequence. We know that
 424      it ends in E0->INSN.  */
 425   mseq = (matching_seq) xmalloc (sizeof (struct matching_seq_def));
 426   mseq->insn = e1->insn;
 427   mseq->idx = e1->idx;
 428   mseq->matching_length = len;
 429   mseq->abstracted_length = 0;
 430   mseq->cost = cost;
 431
 432   if (p_prev == NULL)
 433     pattern_seqs->matching_seqs = mseq;
 434   else
 435     p_prev->next_matching_seq = mseq;
 436   mseq->next_matching_seq = p_next;
 437 }
 438
 439 /* Collects all pattern sequences and their matching sequences and puts them
 440    into PATTERN_SEQS.  */
 441
 442 static void
 443 collect_pattern_seqs (void)
 444 {
 445   htab_iterator hti0, hti1, hti2;
 446   p_hash_bucket hash_bucket;
 447   p_hash_elem e0, e1;
 448 #ifdef STACK_REGS
 449   basic_block bb;
 450   bitmap_head stack_reg_live;
 451
 452   /* Extra initialization step to ensure that no stack registers (if present)
 453      are live across abnormal edges. Set a flag in STACK_REG_LIVE for an insn
 454      if a stack register is live after the insn.  */
 455   bitmap_initialize (&stack_reg_live, NULL);
 456
 457   FOR_EACH_BB (bb)
 458   {
 459     regset_head live;
 460     rtx insn;
 461     rtx prev;
 462
 463     /* Initialize liveness propagation.  */
 464     INIT_REG_SET (&live);
 465     bitmap_copy (&live, DF_LR_OUT (bb));
 466     df_simulate_artificial_refs_at_end (bb, &live);
 467
 468     /* Propagate liveness info and mark insns where a stack reg is live.  */
 469     insn = BB_END (bb);
 470     for (insn = BB_END (bb); ; insn = prev)
 471       {
 472         prev = PREV_INSN (insn);
 473         if (INSN_P (insn))
 474           {
 475             int reg;
 476             for (reg = FIRST_STACK_REG; reg <= LAST_STACK_REG; reg++)
 477               {
 478                 if (REGNO_REG_SET_P (&live, reg))
 479                   {
 480                     bitmap_set_bit (&stack_reg_live, INSN_UID (insn));
 481                     break;
 482                   }
 483               }
 484
 485           }
 486         if (insn == BB_HEAD (bb))
 487           break;
 488         df_simulate_one_insn_backwards (bb, insn, &live);
 489         insn = prev;
 490       }
 491
 492     /* Free unused data.  */
 493     CLEAR_REG_SET (&live);
 494   }
 495 #endif
 496
 497   /* Initialize PATTERN_SEQS to empty.  */
 498   pattern_seqs = 0;
 499
 500   /* Try to match every abstractable insn with every other insn in the same
 501      HASH_BUCKET.  */
 502
 503   FOR_EACH_HTAB_ELEMENT (hash_buckets, hash_bucket, p_hash_bucket, hti0)
 504     if (htab_elements (hash_bucket->seq_candidates) > 1)
 505       FOR_EACH_HTAB_ELEMENT (hash_bucket->seq_candidates, e0, p_hash_elem, hti1)
 506         FOR_EACH_HTAB_ELEMENT (hash_bucket->seq_candidates, e1, p_hash_elem,
 507                                hti2)
 508           if (e0 != e1
 509 #ifdef STACK_REGS
 510               && !bitmap_bit_p (&stack_reg_live, INSN_UID (e0->insn))
 511               && !bitmap_bit_p (&stack_reg_live, INSN_UID (e1->insn))
 512 #endif
 513              )
 514             match_seqs (e0, e1);
 515 #ifdef STACK_REGS
 516   /* Free unused data.  */
 517   bitmap_clear (&stack_reg_live);
 518 #endif
 519 }
 520
 521 /* Transforms a regset to a HARD_REG_SET. Every hard register in REGS is added
 522    to hregs. Additionally, the hard counterpart of every renumbered pseudo
 523    register is also added.  */
 524
 525 static void
 526 renumbered_reg_set_to_hard_reg_set (HARD_REG_SET * hregs, regset regs)
 527 {
 528   int r;
 529
 530   REG_SET_TO_HARD_REG_SET (*hregs, regs);
 531   for (r = FIRST_PSEUDO_REGISTER; r < max_regno; r++)
 532     if (REGNO_REG_SET_P (regs, r) && reg_renumber[r] >= 0)
 533       SET_HARD_REG_BIT (*hregs, reg_renumber[r]);
 534 }
 535
 536 /* Clears the bits in REGS for all registers, which are live in the sequence
 537    give by its last INSN and its LENGTH.  */
 538
 539 static void
 540 clear_regs_live_in_seq (HARD_REG_SET * regs, rtx insn, int length)
 541 {
 542   basic_block bb;
 543   regset_head live;
 544   HARD_REG_SET hlive;
 545   rtx x;
 546   int i;
 547
 548   /* Initialize liveness propagation.  */
 549   bb = BLOCK_FOR_INSN (insn);
 550   INIT_REG_SET (&live);
 551   bitmap_copy (&live, DF_LR_OUT (bb));
 552   df_simulate_artificial_refs_at_end (bb, &live);
 553
 554   /* Propagate until INSN if found.  */
 555   for (x = BB_END (bb); x != insn;)
 556     df_simulate_one_insn_backwards (bb, insn, &live);
 557
 558   /* Clear registers live after INSN.  */
 559   renumbered_reg_set_to_hard_reg_set (&hlive, &live);
 560   AND_COMPL_HARD_REG_SET (*regs, hlive);
 561
 562   /* Clear registers live in and before the sequence.  */
 563   for (i = 0; i < length;)
 564     {
 565       rtx prev = PREV_INSN (x);
 566       df_simulate_one_insn_backwards (bb, insn, &live);
 567
 568       if (INSN_P (x))
 569         {
 570           renumbered_reg_set_to_hard_reg_set (&hlive, &live);
 571           AND_COMPL_HARD_REG_SET (*regs, hlive);
 572           i++;
 573         }
 574
 575       x = prev;
 576     }
 577
 578   /* Free unused data.  */
 579   CLEAR_REG_SET (&live);
 580 }
 581
 582 /* Computes the gain of turning PSEQ into a pseudo-function and its matching
 583    sequences into pseudo-calls. Also computes and caches the number of insns to
 584    abstract from  the matching sequences.  */
 585
 586 static void
 587 recompute_gain_for_pattern_seq (pattern_seq pseq)
 588 {
 589   matching_seq mseq;
 590   rtx x;
 591   int i;
 592   int hascall;
 593   HARD_REG_SET linkregs;
 594
 595   /* Initialize data.  */
 596   SET_HARD_REG_SET (linkregs);
 597   pseq->link_reg = NULL_RTX;
 598   pseq->abstracted_length = 0;
 599
 600   pseq->gain = -(seq_call_cost - seq_jump_cost + seq_return_cost);
 601
 602   /* Determine ABSTRACTED_LENGTH and COST for matching sequences of PSEQ.
 603      ABSTRACTED_LENGTH may be less than MATCHING_LENGTH if sequences in the
 604      same block overlap. */
 605
 606   for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
 607     {
 608       /* Determine ABSTRACTED_LENGTH.  */
 609       if (mseq->next_matching_seq)
 610         mseq->abstracted_length = (int)(mseq->next_matching_seq->idx -
 611                                         mseq->idx);
 612       else
 613         mseq->abstracted_length = mseq->matching_length;
 614
 615       if (mseq->abstracted_length > mseq->matching_length)
 616         mseq->abstracted_length = mseq->matching_length;
 617
 618       /* Compute the cost of sequence.  */
 619       RECOMPUTE_COST (mseq);
 620
 621       /* If COST is big enough registers live in this matching sequence
 622          should not be used as a link register. Also set ABSTRACTED_LENGTH
 623          of PSEQ.  */
 624       if (mseq->cost > seq_call_cost)
 625         {
 626           clear_regs_live_in_seq (&linkregs, mseq->insn,
 627                                   mseq->abstracted_length);
 628           if (mseq->abstracted_length > pseq->abstracted_length)
 629             pseq->abstracted_length = mseq->abstracted_length;
 630         }
 631     }
 632
 633   /* Modify ABSTRACTED_LENGTH of PSEQ if pattern sequence overlaps with one
 634      of the matching sequences.  */
 635   for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
 636     {
 637       x = pseq->insn;
 638       for (i = 0; (i < pseq->abstracted_length) && (x != mseq->insn); i++)
 639         x = prev_insn_in_block (x);
 640       pseq->abstracted_length = i;
 641     }
 642
 643   /* Compute the cost of pattern sequence.  */
 644   RECOMPUTE_COST (pseq);
 645
 646   /* No gain if COST is too small.  */
 647   if (pseq->cost <= seq_call_cost)
 648   {
 649     pseq->gain = -1;
 650     return;
 651   }
 652
 653   /* Ensure that no matching sequence is longer than the pattern sequence.  */
 654   for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
 655     {
 656       if (mseq->abstracted_length > pseq->abstracted_length)
 657         {
 658           mseq->abstracted_length = pseq->abstracted_length;
 659           RECOMPUTE_COST (mseq);
 660         }
 661       /* Once the length is stabilizing the gain can be calculated.  */
 662       if (mseq->cost > seq_call_cost)
 663         pseq->gain += mseq->cost - seq_call_cost;
 664     }
 665
 666   /* No need to do further work if there is no gain.  */
 667   if (pseq->gain <= 0)
 668     return;
 669
 670   /* Should not use registers live in the pattern sequence as link register.
 671    */
 672   clear_regs_live_in_seq (&linkregs, pseq->insn, pseq->abstracted_length);
 673
 674   /* Determine whether pattern sequence contains a call_insn.  */
 675   hascall = 0;
 676   x = pseq->insn;
 677   for (i = 0; i < pseq->abstracted_length; i++)
 678     {
 679       if (CALL_P (x))
 680         {
 681           hascall = 1;
 682           break;
 683         }
 684       x = prev_insn_in_block (x);
 685     }
 686
 687   /* Should not use a register as a link register if - it is a fixed
 688      register, or - the sequence contains a call insn and the register is a
 689      call used register, or - the register needs to be saved if used in a
 690      function but was not used before (since saving it can invalidate already
 691      computed frame pointer offsets), or - the register cannot be used as a
 692      base register.  */
 693
 694   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 695     if (fixed_regs[i]
 696 #ifdef REGNO_OK_FOR_INDIRECT_JUMP_P
 697         || (!REGNO_OK_FOR_INDIRECT_JUMP_P (i, Pmode))
 698 #else
 699         || (!ok_for_base_p_1 (i, Pmode, MEM, SCRATCH))
 700         || (!reg_class_subset_p (REGNO_REG_CLASS (i),
 701                                  base_reg_class (VOIDmode, MEM, SCRATCH)))
 702 #endif
 703         || (hascall && call_used_regs[i])
 704         || (!call_used_regs[i] && !df_regs_ever_live_p (i)))
 705       CLEAR_HARD_REG_BIT (linkregs, i);
 706
 707   /* Find an appropriate register to be used as the link register.  */
 708   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 709     if (TEST_HARD_REG_BIT (linkregs, i))
 710       {
 711         pseq->link_reg = gen_rtx_REG (Pmode, i);
 712         break;
 713       }
 714
 715   /* Abstraction is not possible if no link register is available, so set
 716      gain to 0.  */
 717   if (!pseq->link_reg)
 718     pseq->gain = 0;
 719 }
 720
 721 /* Deallocates memory occupied by PSEQ and its matching seqs.  */
 722
 723 static void
 724 free_pattern_seq (pattern_seq pseq)
 725 {
 726   while (pseq->matching_seqs)
 727     {
 728       matching_seq mseq = pseq->matching_seqs;
 729       pseq->matching_seqs = mseq->next_matching_seq;
 730       free (mseq);
 731     }
 732   free (pseq);
 733 }
 734
 735
 736 /* Computes the gain for pattern sequences. Pattern sequences producing no gain
 737    are deleted. The pattern sequence with the biggest gain is moved to the first
 738    place of PATTERN_SEQS.  */
 739
 740 static void
 741 recompute_gain (void)
 742 {
 743   pattern_seq *pseq;
 744   int maxgain;
 745
 746   maxgain = 0;
 747   for (pseq = &pattern_seqs; *pseq;)
 748     {
 749       if ((*pseq)->gain <= 0)
 750         recompute_gain_for_pattern_seq (*pseq);
 751
 752       if ((*pseq)->gain > 0)
 753         {
 754           if ((*pseq)->gain > maxgain)
 755             {
 756               pattern_seq temp = *pseq;
 757               (*pseq) = temp->next_pattern_seq;
 758               temp->next_pattern_seq = pattern_seqs;
 759               pattern_seqs = temp;
 760               maxgain = pattern_seqs->gain;
 761             }
 762           else
 763             {
 764               pseq = &(*pseq)->next_pattern_seq;
 765             }
 766         }
 767       else
 768         {
 769           pattern_seq temp = *pseq;
 770           *pseq = temp->next_pattern_seq;
 771           free_pattern_seq (temp);
 772         }
 773     }
 774 }
 775
 776 /* Updated those pattern sequences and matching sequences, which overlap with
 777    the sequence given by INSN and LEN. Deletes sequences shrinking below a
 778    limit.  */
 779
 780 static void
 781 erase_from_pattern_seqs (rtx insn, int len)
 782 {
 783   pattern_seq *pseq;
 784   matching_seq *mseq;
 785   rtx x;
 786   int plen, mlen;
 787   int pcost, mcost;
 788
 789   while (len > 0)
 790     {
 791       for (pseq = &pattern_seqs; *pseq;)
 792         {
 793           plen = 0;
 794           pcost = 0;
 795           for (x = (*pseq)->insn; x && (x != insn);
 796                x = prev_insn_in_block (x))
 797             {
 798               plen++;
 799               pcost += compute_rtx_cost (x);
 800             }
 801
 802           if (pcost <= seq_call_cost)
 803             {
 804               pattern_seq temp = *pseq;
 805               *pseq = temp->next_pattern_seq;
 806               free_pattern_seq (temp);
 807             }
 808           else
 809             {
 810               for (mseq = &(*pseq)->matching_seqs; *mseq;)
 811                 {
 812                   mlen = 0;
 813                   mcost = 0;
 814                   for (x = (*mseq)->insn;
 815                        x && (x != insn) && (mlen < plen)
 816                        && (mlen < (*mseq)->matching_length);
 817                        x = prev_insn_in_block (x))
 818                     {
 819                       mlen++;
 820                       mcost += compute_rtx_cost (x);
 821                     }
 822
 823                   if (mcost <= seq_call_cost)
 824                     {
 825                       matching_seq temp = *mseq;
 826                       *mseq = temp->next_matching_seq;
 827                       free (temp);
 828                       /* Set to 0 to force gain recomputation.  */
 829                       (*pseq)->gain = 0;
 830                     }
 831                   else
 832                     {
 833                       if (mlen < (*mseq)->matching_length)
 834                         {
 835                           (*mseq)->cost = mcost;
 836                           (*mseq)->matching_length = mlen;
 837                           /* Set to 0 to force gain recomputation.  */
 838                           (*pseq)->gain = 0;
 839                         }
 840                       mseq = &(*mseq)->next_matching_seq;
 841                     }
 842                 }
 843
 844               pseq = &(*pseq)->next_pattern_seq;
 845             }
 846         }
 847
 848       len--;
 849       insn = prev_insn_in_block (insn);
 850     }
 851 }
 852
 853 /* Updates those pattern sequences and matching sequences, which overlap with
 854    the pattern sequence with the biggest gain and its matching sequences.  */
 855
 856 static void
 857 update_pattern_seqs (void)
 858 {
 859   pattern_seq bestpseq;
 860   matching_seq mseq;
 861
 862   bestpseq = pattern_seqs;
 863   pattern_seqs = bestpseq->next_pattern_seq;
 864
 865   for (mseq = bestpseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
 866     if (mseq->cost > seq_call_cost)
 867       erase_from_pattern_seqs (mseq->insn, mseq->abstracted_length);
 868   erase_from_pattern_seqs (bestpseq->insn, bestpseq->abstracted_length);
 869
 870   bestpseq->next_pattern_seq = pattern_seqs;
 871   pattern_seqs = bestpseq;
 872 }
 873
 874 /* Groups together those matching sequences of the best pattern sequence, which
 875    have the same ABSTRACTED_LENGTH and puts these groups in ascending order.
 876    SEQ_BLOCKS contains the result.  */
 877
 878 static void
 879 determine_seq_blocks (void)
 880 {
 881   seq_block sb;
 882   matching_seq *mseq;
 883   matching_seq m;
 884
 885   /* Initialize SEQ_BLOCKS to empty.  */
 886   seq_blocks = 0;
 887
 888   /* Process all matching sequences.  */
 889   for (mseq = &pattern_seqs->matching_seqs; *mseq;)
 890     {
 891       /* Deal only with matching sequences being long enough. */
 892       if ((*mseq)->cost <= seq_call_cost)
 893         {
 894           mseq = &(*mseq)->next_matching_seq;
 895           continue;
 896         }
 897
 898       /* Ensure that SB contains a seq_block with the appropriate length.
 899          Insert a new seq_block if necessary.  */
 900       if (!seq_blocks || ((*mseq)->abstracted_length < seq_blocks->length))
 901         {
 902           sb = (seq_block) xmalloc (sizeof (struct seq_block_def));
 903           sb->length = (*mseq)->abstracted_length;
 904           sb->label = NULL_RTX;
 905           sb->matching_seqs = 0;
 906           sb->next_seq_block = seq_blocks;
 907           seq_blocks = sb;
 908         }
 909       else
 910         {
 911           for (sb = seq_blocks; sb; sb = sb->next_seq_block)
 912             {
 913               if ((*mseq)->abstracted_length == sb->length)
 914                 break;
 915               if (!sb->next_seq_block
 916                   || ((*mseq)->abstracted_length <
 917                       sb->next_seq_block->length))
 918                 {
 919                   seq_block temp =
 920                     (seq_block) xmalloc (sizeof (struct seq_block_def));
 921                   temp->length = (*mseq)->abstracted_length;
 922                   temp->label = NULL_RTX;
 923                   temp->matching_seqs = 0;
 924                   temp->next_seq_block = sb->next_seq_block;
 925                   sb->next_seq_block = temp;
 926                 }
 927             }
 928         }
 929
 930       /* Remove the matching sequence from the linked list of the pattern
 931          sequence and link it to SB.  */
 932       m = *mseq;
 933       *mseq = m->next_matching_seq;
 934       m->next_matching_seq = sb->matching_seqs;
 935       sb->matching_seqs = m;
 936     }
 937 }
 938
 939 /* Builds a symbol_ref for LABEL.  */
 940
 941 static rtx
 942 gen_symbol_ref_rtx_for_label (rtx label)
 943 {
 944   char name[20];
 945   rtx sym;
 946
 947   ASM_GENERATE_INTERNAL_LABEL (name, "L", CODE_LABEL_NUMBER (label));
 948   sym = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (name));
 949   SYMBOL_REF_FLAGS (sym) = SYMBOL_FLAG_LOCAL;
 950   return sym;
 951 }
 952
 953 /* Ensures that INSN is the last insn in its block and returns the block label
 954    of the next block.  */
 955
 956 static rtx
 957 block_label_after (rtx insn)
 958 {
 959   basic_block bb = BLOCK_FOR_INSN (insn);
 960   if ((insn == BB_END (bb)) && (bb->next_bb != EXIT_BLOCK_PTR))
 961     return block_label (bb->next_bb);
 962   else
 963     return block_label (split_block (bb, insn)->dest);
 964 }
 965
 966 /* Ensures that the last insns of the best pattern and its matching sequences
 967    are the last insns in their block. Additionally, extends the live set at the
 968    end of the pattern sequence with the live sets at the end of the matching
 969    sequences.  */
 970
 971 static void
 972 split_blocks_after_seqs (void)
 973 {
 974   seq_block sb;
 975   matching_seq mseq;
 976
 977   block_label_after (pattern_seqs->insn);
 978   for (sb = seq_blocks; sb; sb = sb->next_seq_block)
 979     {
 980       for (mseq = sb->matching_seqs; mseq; mseq = mseq->next_matching_seq)
 981         {
 982           block_label_after (mseq->insn);
 983           IOR_REG_SET (df_get_live_out (BLOCK_FOR_INSN (pattern_seqs->insn)),
 984                        df_get_live_out (BLOCK_FOR_INSN (mseq->insn)));
 985         }
 986     }
 987 }
 988
 989 /* Splits the best pattern sequence according to SEQ_BLOCKS. Emits pseudo-call
 990    and -return insns before and after the sequence.  */
 991
 992 static void
 993 split_pattern_seq (void)
 994 {
 995   rtx insn;
 996   basic_block bb;
 997   rtx retlabel, retjmp, saveinsn;
 998   int i;
 999   seq_block sb;
1000
1001   insn = pattern_seqs->insn;
1002   bb = BLOCK_FOR_INSN (insn);
1003
1004   /* Get the label after the sequence. This will be the return address. The
1005      label will be referenced using a symbol_ref so protect it from
1006      deleting.  */
1007   retlabel = block_label_after (insn);
1008   LABEL_PRESERVE_P (retlabel) = 1;
1009
1010   /* Emit an indirect jump via the link register after the sequence acting
1011      as the return insn.  Also emit a barrier and update the basic block.  */
1012   retjmp = emit_jump_insn_after (gen_indirect_jump (pattern_seqs->link_reg),
1013                                  BB_END (bb));
1014   emit_barrier_after (BB_END (bb));
1015
1016   /* Replace all outgoing edges with a new one to the block of RETLABEL.  */
1017   while (EDGE_COUNT (bb->succs) != 0)
1018     remove_edge (EDGE_SUCC (bb, 0));
1019   make_edge (bb, BLOCK_FOR_INSN (retlabel), EDGE_ABNORMAL);
1020
1021   /* Split the sequence according to SEQ_BLOCKS and cache the label of the
1022      resulting basic blocks.  */
1023   i = 0;
1024   for (sb = seq_blocks; sb; sb = sb->next_seq_block)
1025     {
1026       for (; i < sb->length; i++)
1027         insn = prev_insn_in_block (insn);
1028
1029       sb->label = block_label (split_block (bb, insn)->dest);
1030     }
1031
1032   /* Emit an insn saving the return address to the link register before the
1033      sequence.  */
1034   saveinsn = emit_insn_after (gen_move_insn (pattern_seqs->link_reg,
1035                               gen_symbol_ref_rtx_for_label
1036                               (retlabel)), BB_END (bb));
1037   /* Update liveness info.  */
1038   SET_REGNO_REG_SET (df_get_live_out (bb),
1039                      REGNO (pattern_seqs->link_reg));
1040 }
1041
1042 /* Deletes the insns of the matching sequences of the best pattern sequence and
1043    replaces them with pseudo-calls to the pattern sequence.  */
1044
1045 static void
1046 erase_matching_seqs (void)
1047 {
1048   seq_block sb;
1049   matching_seq mseq;
1050   rtx insn;
1051   basic_block bb;
1052   rtx retlabel, saveinsn, callinsn;
1053   int i;
1054
1055   for (sb = seq_blocks; sb; sb = sb->next_seq_block)
1056     {
1057       for (mseq = sb->matching_seqs; mseq; mseq = mseq->next_matching_seq)
1058         {
1059           insn = mseq->insn;
1060           bb = BLOCK_FOR_INSN (insn);
1061
1062           /* Get the label after the sequence. This will be the return
1063              address. The label will be referenced using a symbol_ref so
1064              protect it from deleting.  */
1065           retlabel = block_label_after (insn);
1066           LABEL_PRESERVE_P (retlabel) = 1;
1067
1068           /* Delete the insns of the sequence.  */
1069           for (i = 0; i < sb->length; i++)
1070             insn = prev_insn_in_block (insn);
1071           delete_basic_block (split_block (bb, insn)->dest);
1072
1073           /* Emit an insn saving the return address to the link register
1074              before the deleted sequence.  */
1075           saveinsn = emit_insn_after (gen_move_insn (pattern_seqs->link_reg,
1076                                       gen_symbol_ref_rtx_for_label
1077                                       (retlabel)),
1078                                       BB_END (bb));
1079           BLOCK_FOR_INSN (saveinsn) = bb;
1080
1081           /* Emit a jump to the appropriate part of the pattern sequence
1082              after the save insn. Also update the basic block.  */
1083           callinsn = emit_jump_insn_after (gen_jump (sb->label), saveinsn);
1084           JUMP_LABEL (callinsn) = sb->label;
1085           LABEL_NUSES (sb->label)++;
1086           BLOCK_FOR_INSN (callinsn) = bb;
1087           BB_END (bb) = callinsn;
1088
1089           /* Maintain control flow and liveness information.  */
1090           SET_REGNO_REG_SET (df_get_live_out (bb),
1091                              REGNO (pattern_seqs->link_reg));
1092           emit_barrier_after (BB_END (bb));
1093           make_single_succ_edge (bb, BLOCK_FOR_INSN (sb->label), 0);
1094           IOR_REG_SET (df_get_live_out (bb),
1095                        df_get_live_in (BLOCK_FOR_INSN (sb->label)));
1096
1097           make_edge (BLOCK_FOR_INSN (seq_blocks->label),
1098                      BLOCK_FOR_INSN (retlabel), EDGE_ABNORMAL);
1099         }
1100     }
1101 }
1102
1103 /* Deallocates SEQ_BLOCKS and all the matching sequences.  */
1104
1105 static void
1106 free_seq_blocks (void)
1107 {
1108   while (seq_blocks)
1109     {
1110       seq_block sb = seq_blocks;
1111       while (sb->matching_seqs)
1112         {
1113           matching_seq mseq = sb->matching_seqs;
1114           sb->matching_seqs = mseq->next_matching_seq;
1115           free (mseq);
1116         }
1117       seq_blocks = sb->next_seq_block;
1118       free (sb);
1119     }
1120 }
1121
1122 /* Transforms the best pattern sequence into a pseudo-function and its matching
1123    sequences to pseudo-calls. Afterwards the best pattern sequence is removed
1124    from PATTERN_SEQS.  */
1125
1126 static void
1127 abstract_best_seq (void)
1128 {
1129   pattern_seq bestpseq;
1130
1131   /* Do the abstraction.  */
1132   determine_seq_blocks ();
1133   split_blocks_after_seqs ();
1134   split_pattern_seq ();
1135   erase_matching_seqs ();
1136   free_seq_blocks ();
1137
1138   /* Record the usage of the link register.  */
1139   df_set_regs_ever_live (REGNO (pattern_seqs->link_reg), true);
1140
1141   /* Remove the best pattern sequence.  */
1142   bestpseq = pattern_seqs;
1143   pattern_seqs = bestpseq->next_pattern_seq;
1144   free_pattern_seq (bestpseq);
1145 }
1146
1147 /* Prints info on the pattern sequences to the dump file.  */
1148
1149 static void
1150 dump_pattern_seqs (void)
1151 {
1152   pattern_seq pseq;
1153   matching_seq mseq;
1154
1155   if (!dump_file)
1156     return;
1157
1158   fprintf (dump_file, ";; Pattern sequences\n");
1159   for (pseq = pattern_seqs; pseq; pseq = pseq->next_pattern_seq)
1160     {
1161       fprintf (dump_file, "Pattern sequence at insn %d matches sequences at",
1162                INSN_UID (pseq->insn));
1163       for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
1164         {
1165           fprintf (dump_file, " insn %d (length %d)", INSN_UID (mseq->insn),
1166                    mseq->matching_length);
1167           if (mseq->next_matching_seq)
1168             fprintf (dump_file, ",");
1169         }
1170       fprintf (dump_file, ".\n");
1171     }
1172   fprintf (dump_file, "\n");
1173 }
1174
1175 /* Prints info on the best pattern sequence transformed in the ITER-th
1176    iteration to the dump file.  */
1177
1178 static void
1179 dump_best_pattern_seq (int iter)
1180 {
1181   matching_seq mseq;
1182
1183   if (!dump_file)
1184     return;
1185
1186   fprintf (dump_file, ";; Iteration %d\n", iter);
1187   fprintf (dump_file,
1188            "Best pattern sequence with %d gain is at insn %d (length %d).\n",
1189            pattern_seqs->gain, INSN_UID (pattern_seqs->insn),
1190            pattern_seqs->abstracted_length);
1191   fprintf (dump_file, "Matching sequences are at");
1192   for (mseq = pattern_seqs->matching_seqs; mseq;
1193        mseq = mseq->next_matching_seq)
1194     {
1195       fprintf (dump_file, " insn %d (length %d)", INSN_UID (mseq->insn),
1196                mseq->abstracted_length);
1197       if (mseq->next_matching_seq)
1198         fprintf (dump_file, ",");
1199     }
1200   fprintf (dump_file, ".\n");
1201   fprintf (dump_file, "Using reg %d as link register.\n\n",
1202            REGNO (pattern_seqs->link_reg));
1203 }
1204
1205 /* Htab hash function for hash_bucket_def structure.  */
1206
1207 static unsigned int
1208 htab_hash_bucket (const void *p)
1209 {
1210   const_p_hash_bucket bucket = (const_p_hash_bucket) p;
1211   return bucket->hash;
1212 }
1213
1214 /* Htab equal function for hash_bucket_def structure.  */
1215
1216 static int
1217 htab_eq_bucket (const void *p0, const void *p1)
1218 {
1219   return htab_hash_bucket (p0) == htab_hash_bucket (p1);
1220 }
1221
1222 /* Htab delete function for hash_bucket_def structure.  */
1223
1224 static void
1225 htab_del_bucket (void *p)
1226 {
1227   p_hash_bucket bucket = (p_hash_bucket) p;
1228
1229   if (bucket->seq_candidates)
1230     htab_delete (bucket->seq_candidates);
1231
1232   free (bucket);
1233 }
1234
1235 /* Htab hash function for hash_bucket_def structure.  */
1236
1237 static unsigned int
1238 htab_hash_elem (const void *p)
1239 {
1240   const_p_hash_elem elem = (const_p_hash_elem) p;
1241   return htab_hash_pointer (elem->insn);
1242 }
1243
1244 /* Htab equal function for hash_bucket_def structure.  */
1245
1246 static int
1247 htab_eq_elem (const void *p0, const void *p1)
1248 {
1249   return htab_hash_elem (p0) == htab_hash_elem (p1);
1250 }
1251
1252 /* Htab delete function for hash_bucket_def structure.  */
1253
1254 static void
1255 htab_del_elem (void *p)
1256 {
1257   p_hash_elem elem = (p_hash_elem) p;
1258   free (elem);
1259 }
1260
1261 /* Creates a hash value for each sequence candidate and saves them
1262    in HASH_BUCKET.  */
1263
1264 static void
1265 fill_hash_bucket (void)
1266 {
1267   basic_block bb;
1268   rtx insn;
1269   void **slot;
1270   p_hash_bucket bucket;
1271   struct hash_bucket_def tmp_bucket;
1272   p_hash_elem elem;
1273   unsigned long insn_idx;
1274
1275   insn_idx = 0;
1276   FOR_EACH_BB (bb)
1277     {
1278       FOR_BB_INSNS_REVERSE (bb, insn)
1279         {
1280           if (!ABSTRACTABLE_INSN_P (insn))
1281             continue;
1282
1283           /* Compute hash value for INSN.  */
1284           tmp_bucket.hash = compute_hash (insn);
1285
1286           /* Select the hash group.  */
1287           bucket = htab_find (hash_buckets, &tmp_bucket);
1288
1289           if (!bucket)
1290             {
1291               /* Create a new hash group.  */
1292               bucket = (p_hash_bucket) xcalloc (1,
1293                                         sizeof (struct hash_bucket_def));
1294               bucket->hash = tmp_bucket.hash;
1295               bucket->seq_candidates = NULL;
1296
1297               slot = htab_find_slot (hash_buckets, &tmp_bucket, INSERT);
1298               *slot = bucket;
1299             }
1300
1301           /* Create new list for storing sequence candidates.  */
1302           if (!bucket->seq_candidates)
1303               bucket->seq_candidates = htab_create (HASH_INIT,
1304                                                     htab_hash_elem,
1305                                                     htab_eq_elem,
1306                                                     htab_del_elem);
1307
1308           elem = (p_hash_elem) xcalloc (1, sizeof (struct hash_elem_def));
1309           elem->insn = insn;
1310           elem->idx = insn_idx;
1311           elem->length = get_attr_length (insn);
1312
1313           /* Insert INSN into BUCKET hash bucket.  */
1314           slot = htab_find_slot (bucket->seq_candidates, elem, INSERT);
1315           *slot = elem;
1316
1317           insn_idx++;
1318         }
1319     }
1320 }
1321
1322 /* Computes the cost of calling sequence and the cost of return.  */
1323
1324 static void
1325 compute_init_costs (void)
1326 {
1327   rtx rtx_jump, rtx_store, rtx_return, reg, label;
1328   basic_block bb;
1329
1330   FOR_EACH_BB (bb)
1331     if (BB_HEAD (bb))
1332       break;
1333
1334   label = block_label (bb);
1335   reg = gen_rtx_REG (Pmode, 0);
1336
1337   /* Pattern for indirect jump.  */
1338   rtx_jump = gen_indirect_jump (reg);
1339
1340   /* Pattern for storing address.  */
1341   rtx_store = gen_rtx_SET (VOIDmode, reg, gen_symbol_ref_rtx_for_label (label));
1342
1343   /* Pattern for return insn.  */
1344   rtx_return = gen_jump (label);
1345
1346   /* The cost of jump.  */
1347   seq_jump_cost = compute_rtx_cost (make_jump_insn_raw (rtx_jump));
1348
1349   /* The cost of calling sequence.  */
1350   seq_call_cost = seq_jump_cost + compute_rtx_cost (make_insn_raw (rtx_store));
1351
1352   /* The cost of return.  */
1353   seq_return_cost = compute_rtx_cost (make_jump_insn_raw (rtx_return));
1354
1355   /* Simple heuristic for minimal sequence cost.  */
1356   seq_call_cost   = (int)(seq_call_cost * (double)SEQ_CALL_COST_MULTIPLIER);
1357 }
1358
1359 /* Finds equivalent insn sequences in the current function and retains only one
1360    instance of them which is turned into a pseudo-function. The additional
1361    copies are erased and replaced by pseudo-calls to the retained sequence.  */
1362
1363 static void
1364 rtl_seqabstr (void)
1365 {
1366   int iter;
1367   df_set_flags (DF_LR_RUN_DCE);
1368   df_analyze ();
1369
1370   /* Create a hash list for COLLECT_PATTERN_SEQS.  */
1371   hash_buckets = htab_create (HASH_INIT, htab_hash_bucket , htab_eq_bucket ,
1372                               htab_del_bucket);
1373   fill_hash_bucket ();
1374
1375   /* Compute the common cost of abstraction.  */
1376   compute_init_costs ();
1377
1378   /* Build an initial set of pattern sequences from the current function.  */
1379   collect_pattern_seqs ();
1380   dump_pattern_seqs ();
1381
1382   /* Iterate until there are no sequences to abstract.  */
1383   for (iter = 1;; iter++)
1384     {
1385       /* Recompute gain for sequences if necessary and select sequence with
1386          biggest gain.  */
1387       recompute_gain ();
1388       if (!pattern_seqs)
1389         break;
1390       dump_best_pattern_seq (iter);
1391       /* Update the cached info of the other sequences and force gain
1392          recomputation where needed.  */
1393       update_pattern_seqs ();
1394       /* Turn best sequences into pseudo-functions and -calls.  */
1395       abstract_best_seq ();
1396     }
1397
1398   /* Cleanup hash tables.  */
1399   htab_delete (hash_buckets);
1400 }
1401
1402 /* The gate function for TREE_OPT_PASS.  */
1403
1404 static bool
1405 gate_rtl_seqabstr (void)
1406 {
1407   return flag_rtl_seqabstr;
1408 }
1409
1410 /* The entry point of the sequence abstraction algorithm.  */
1411
1412 static unsigned int
1413 rest_of_rtl_seqabstr (void)
1414 {
1415   /* Abstract out common insn sequences. */
1416   rtl_seqabstr ();
1417   return 0;
1418 }
1419
1420 struct tree_opt_pass pass_rtl_seqabstr = {
1421   "seqabstr",                           /* name */
1422   gate_rtl_seqabstr,                    /* gate */
1423   rest_of_rtl_seqabstr,                 /* execute */
1424   NULL,                                 /* sub */
1425   NULL,                                 /* next */
1426   0,                                    /* static_pass_number */
1427   TV_SEQABSTR,                          /* tv_id */
1428   0,                                    /* properties_required */
1429   0,                                    /* properties_provided */
1430   0,                                    /* properties_destroyed */
1431   0,                                    /* todo_flags_start */
1432   TODO_df_finish |
1433   TODO_dump_func |
1434   TODO_ggc_collect,                     /* todo_flags_finish */
1435   'Q'                                   /* letter */
1436 };