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