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