gcc/rtl-factoring.c

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