gcc/rtl-factoring.c

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