gcc/rtl-factoring.c

   1 /* RTL factoring (sequence abstraction).
   2    Copyright (C) 2004, 2005, 2006, 2007, 2008 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; x = PREV_INSN (x))
 555     df_simulate_one_insn_backwards (bb, x, &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, x, &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 /* Splits basic block at the requested insn and rebuilds dataflow.  */
 953
 954 static basic_block
 955 split_block_and_df_analyze (basic_block bb, rtx insn)
 956 {
 957   basic_block next;
 958   next = split_block (bb, insn)->dest;
 959   df_analyze ();
 960   return next;
 961 }
 962
 963 /* Ensures that INSN is the last insn in its block and returns the block label
 964    of the next block.  */
 965
 966 static rtx
 967 block_label_after (rtx insn)
 968 {
 969   basic_block bb = BLOCK_FOR_INSN (insn);
 970   if ((insn == BB_END (bb)) && (bb->next_bb != EXIT_BLOCK_PTR))
 971     return block_label (bb->next_bb);
 972   else
 973     return block_label (split_block_and_df_analyze (bb, insn));
 974 }
 975
 976 /* Ensures that the last insns of the best pattern and its matching sequences
 977    are the last insns in their block. Additionally, extends the live set at the
 978    end of the pattern sequence with the live sets at the end of the matching
 979    sequences.  */
 980
 981 static void
 982 split_blocks_after_seqs (void)
 983 {
 984   seq_block sb;
 985   matching_seq mseq;
 986
 987   block_label_after (pattern_seqs->insn);
 988   for (sb = seq_blocks; sb; sb = sb->next_seq_block)
 989     {
 990       for (mseq = sb->matching_seqs; mseq; mseq = mseq->next_matching_seq)
 991         {
 992           block_label_after (mseq->insn);
 993           IOR_REG_SET (df_get_live_out (BLOCK_FOR_INSN (pattern_seqs->insn)),
 994                        df_get_live_out (BLOCK_FOR_INSN (mseq->insn)));
 995         }
 996     }
 997 }
 998
 999 /* Splits the best pattern sequence according to SEQ_BLOCKS. Emits pseudo-call
1000    and -return insns before and after the sequence.  */
1001
1002 static void
1003 split_pattern_seq (void)
1004 {
1005   rtx insn;
1006   basic_block bb;
1007   rtx retlabel, retjmp, saveinsn;
1008   int i;
1009   seq_block sb;
1010
1011   insn = pattern_seqs->insn;
1012   bb = BLOCK_FOR_INSN (insn);
1013
1014   /* Get the label after the sequence. This will be the return address. The
1015      label will be referenced using a symbol_ref so protect it from
1016      deleting.  */
1017   retlabel = block_label_after (insn);
1018   LABEL_PRESERVE_P (retlabel) = 1;
1019
1020   /* Emit an indirect jump via the link register after the sequence acting
1021      as the return insn.  Also emit a barrier and update the basic block.  */
1022   if (!find_reg_note (BB_END (bb), REG_NORETURN, NULL))
1023     retjmp = emit_jump_insn_after (gen_indirect_jump (pattern_seqs->link_reg),
1024                                    BB_END (bb));
1025   emit_barrier_after (BB_END (bb));
1026
1027   /* Replace all outgoing edges with a new one to the block of RETLABEL.  */
1028   while (EDGE_COUNT (bb->succs) != 0)
1029     remove_edge (EDGE_SUCC (bb, 0));
1030   make_edge (bb, BLOCK_FOR_INSN (retlabel), EDGE_ABNORMAL);
1031
1032   /* Split the sequence according to SEQ_BLOCKS and cache the label of the
1033      resulting basic blocks.  */
1034   i = 0;
1035   for (sb = seq_blocks; sb; sb = sb->next_seq_block)
1036     {
1037       for (; i < sb->length; i++)
1038         insn = prev_insn_in_block (insn);
1039
1040       sb->label = block_label (split_block_and_df_analyze (bb, insn));
1041     }
1042
1043   /* Emit an insn saving the return address to the link register before the
1044      sequence.  */
1045   saveinsn = emit_insn_after (gen_move_insn (pattern_seqs->link_reg,
1046                               gen_symbol_ref_rtx_for_label
1047                               (retlabel)), BB_END (bb));
1048   /* Update liveness info.  */
1049   SET_REGNO_REG_SET (df_get_live_out (bb),
1050                      REGNO (pattern_seqs->link_reg));
1051 }
1052
1053 /* Deletes the insns of the matching sequences of the best pattern sequence and
1054    replaces them with pseudo-calls to the pattern sequence.  */
1055
1056 static void
1057 erase_matching_seqs (void)
1058 {
1059   seq_block sb;
1060   matching_seq mseq;
1061   rtx insn;
1062   basic_block bb;
1063   rtx retlabel, saveinsn, callinsn;
1064   int i;
1065
1066   for (sb = seq_blocks; sb; sb = sb->next_seq_block)
1067     {
1068       for (mseq = sb->matching_seqs; mseq; mseq = mseq->next_matching_seq)
1069         {
1070           insn = mseq->insn;
1071           bb = BLOCK_FOR_INSN (insn);
1072
1073           /* Get the label after the sequence. This will be the return
1074              address. The label will be referenced using a symbol_ref so
1075              protect it from deleting.  */
1076           retlabel = block_label_after (insn);
1077           LABEL_PRESERVE_P (retlabel) = 1;
1078
1079           /* Delete the insns of the sequence.  */
1080           for (i = 0; i < sb->length; i++)
1081             insn = prev_insn_in_block (insn);
1082           delete_basic_block (split_block_and_df_analyze (bb, insn));
1083
1084           /* Emit an insn saving the return address to the link register
1085              before the deleted sequence.  */
1086           saveinsn = emit_insn_after (gen_move_insn (pattern_seqs->link_reg,
1087                                       gen_symbol_ref_rtx_for_label
1088                                       (retlabel)),
1089                                       BB_END (bb));
1090           BLOCK_FOR_INSN (saveinsn) = bb;
1091
1092           /* Emit a jump to the appropriate part of the pattern sequence
1093              after the save insn. Also update the basic block.  */
1094           callinsn = emit_jump_insn_after (gen_jump (sb->label), saveinsn);
1095           JUMP_LABEL (callinsn) = sb->label;
1096           LABEL_NUSES (sb->label)++;
1097           BLOCK_FOR_INSN (callinsn) = bb;
1098           BB_END (bb) = callinsn;
1099
1100           /* Maintain control flow and liveness information.  */
1101           SET_REGNO_REG_SET (df_get_live_out (bb),
1102                              REGNO (pattern_seqs->link_reg));
1103           emit_barrier_after (BB_END (bb));
1104           make_single_succ_edge (bb, BLOCK_FOR_INSN (sb->label), 0);
1105           IOR_REG_SET (df_get_live_out (bb),
1106                        df_get_live_in (BLOCK_FOR_INSN (sb->label)));
1107
1108           make_edge (BLOCK_FOR_INSN (seq_blocks->label),
1109                      BLOCK_FOR_INSN (retlabel), EDGE_ABNORMAL);
1110         }
1111     }
1112 }
1113
1114 /* Deallocates SEQ_BLOCKS and all the matching sequences.  */
1115
1116 static void
1117 free_seq_blocks (void)
1118 {
1119   while (seq_blocks)
1120     {
1121       seq_block sb = seq_blocks;
1122       while (sb->matching_seqs)
1123         {
1124           matching_seq mseq = sb->matching_seqs;
1125           sb->matching_seqs = mseq->next_matching_seq;
1126           free (mseq);
1127         }
1128       seq_blocks = sb->next_seq_block;
1129       free (sb);
1130     }
1131 }
1132
1133 /* Transforms the best pattern sequence into a pseudo-function and its matching
1134    sequences to pseudo-calls. Afterwards the best pattern sequence is removed
1135    from PATTERN_SEQS.  */
1136
1137 static void
1138 abstract_best_seq (void)
1139 {
1140   pattern_seq bestpseq;
1141
1142   /* Do the abstraction.  */
1143   determine_seq_blocks ();
1144   split_blocks_after_seqs ();
1145   split_pattern_seq ();
1146   erase_matching_seqs ();
1147   free_seq_blocks ();
1148
1149   /* Record the usage of the link register.  */
1150   df_set_regs_ever_live (REGNO (pattern_seqs->link_reg), true);
1151
1152   /* Remove the best pattern sequence.  */
1153   bestpseq = pattern_seqs;
1154   pattern_seqs = bestpseq->next_pattern_seq;
1155   free_pattern_seq (bestpseq);
1156 }
1157
1158 /* Prints info on the pattern sequences to the dump file.  */
1159
1160 static void
1161 dump_pattern_seqs (void)
1162 {
1163   pattern_seq pseq;
1164   matching_seq mseq;
1165
1166   if (!dump_file)
1167     return;
1168
1169   fprintf (dump_file, ";; Pattern sequences\n");
1170   for (pseq = pattern_seqs; pseq; pseq = pseq->next_pattern_seq)
1171     {
1172       fprintf (dump_file, "Pattern sequence at insn %d matches sequences at",
1173                INSN_UID (pseq->insn));
1174       for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
1175         {
1176           fprintf (dump_file, " insn %d (length %d)", INSN_UID (mseq->insn),
1177                    mseq->matching_length);
1178           if (mseq->next_matching_seq)
1179             fprintf (dump_file, ",");
1180         }
1181       fprintf (dump_file, ".\n");
1182     }
1183   fprintf (dump_file, "\n");
1184 }
1185
1186 /* Prints info on the best pattern sequence transformed in the ITER-th
1187    iteration to the dump file.  */
1188
1189 static void
1190 dump_best_pattern_seq (int iter)
1191 {
1192   matching_seq mseq;
1193
1194   if (!dump_file)
1195     return;
1196
1197   fprintf (dump_file, ";; Iteration %d\n", iter);
1198   fprintf (dump_file,
1199            "Best pattern sequence with %d gain is at insn %d (length %d).\n",
1200            pattern_seqs->gain, INSN_UID (pattern_seqs->insn),
1201            pattern_seqs->abstracted_length);
1202   fprintf (dump_file, "Matching sequences are at");
1203   for (mseq = pattern_seqs->matching_seqs; mseq;
1204        mseq = mseq->next_matching_seq)
1205     {
1206       fprintf (dump_file, " insn %d (length %d)", INSN_UID (mseq->insn),
1207                mseq->abstracted_length);
1208       if (mseq->next_matching_seq)
1209         fprintf (dump_file, ",");
1210     }
1211   fprintf (dump_file, ".\n");
1212   fprintf (dump_file, "Using reg %d as link register.\n\n",
1213            REGNO (pattern_seqs->link_reg));
1214 }
1215
1216 /* Htab hash function for hash_bucket_def structure.  */
1217
1218 static unsigned int
1219 htab_hash_bucket (const void *p)
1220 {
1221   const_p_hash_bucket bucket = (const_p_hash_bucket) p;
1222   return bucket->hash;
1223 }
1224
1225 /* Htab equal function for hash_bucket_def structure.  */
1226
1227 static int
1228 htab_eq_bucket (const void *p0, const void *p1)
1229 {
1230   return htab_hash_bucket (p0) == htab_hash_bucket (p1);
1231 }
1232
1233 /* Htab delete function for hash_bucket_def structure.  */
1234
1235 static void
1236 htab_del_bucket (void *p)
1237 {
1238   p_hash_bucket bucket = (p_hash_bucket) p;
1239
1240   if (bucket->seq_candidates)
1241     htab_delete (bucket->seq_candidates);
1242
1243   free (bucket);
1244 }
1245
1246 /* Htab hash function for hash_bucket_def structure.  */
1247
1248 static unsigned int
1249 htab_hash_elem (const void *p)
1250 {
1251   const_p_hash_elem elem = (const_p_hash_elem) p;
1252   return htab_hash_pointer (elem->insn);
1253 }
1254
1255 /* Htab equal function for hash_bucket_def structure.  */
1256
1257 static int
1258 htab_eq_elem (const void *p0, const void *p1)
1259 {
1260   return htab_hash_elem (p0) == htab_hash_elem (p1);
1261 }
1262
1263 /* Htab delete function for hash_bucket_def structure.  */
1264
1265 static void
1266 htab_del_elem (void *p)
1267 {
1268   p_hash_elem elem = (p_hash_elem) p;
1269   free (elem);
1270 }
1271
1272 /* Creates a hash value for each sequence candidate and saves them
1273    in HASH_BUCKET.  */
1274
1275 static void
1276 fill_hash_bucket (void)
1277 {
1278   basic_block bb;
1279   rtx insn;
1280   void **slot;
1281   p_hash_bucket bucket;
1282   struct hash_bucket_def tmp_bucket;
1283   p_hash_elem elem;
1284   unsigned long insn_idx;
1285
1286   insn_idx = 0;
1287   FOR_EACH_BB (bb)
1288     {
1289       FOR_BB_INSNS_REVERSE (bb, insn)
1290         {
1291           if (!ABSTRACTABLE_INSN_P (insn))
1292             continue;
1293
1294           /* Compute hash value for INSN.  */
1295           tmp_bucket.hash = compute_hash (insn);
1296
1297           /* Select the hash group.  */
1298           bucket = htab_find (hash_buckets, &tmp_bucket);
1299
1300           if (!bucket)
1301             {
1302               /* Create a new hash group.  */
1303               bucket = (p_hash_bucket) xcalloc (1,
1304                                         sizeof (struct hash_bucket_def));
1305               bucket->hash = tmp_bucket.hash;
1306               bucket->seq_candidates = NULL;
1307
1308               slot = htab_find_slot (hash_buckets, &tmp_bucket, INSERT);
1309               *slot = bucket;
1310             }
1311
1312           /* Create new list for storing sequence candidates.  */
1313           if (!bucket->seq_candidates)
1314               bucket->seq_candidates = htab_create (HASH_INIT,
1315                                                     htab_hash_elem,
1316                                                     htab_eq_elem,
1317                                                     htab_del_elem);
1318
1319           elem = (p_hash_elem) xcalloc (1, sizeof (struct hash_elem_def));
1320           elem->insn = insn;
1321           elem->idx = insn_idx;
1322           elem->length = get_attr_length (insn);
1323
1324           /* Insert INSN into BUCKET hash bucket.  */
1325           slot = htab_find_slot (bucket->seq_candidates, elem, INSERT);
1326           *slot = elem;
1327
1328           insn_idx++;
1329         }
1330     }
1331 }
1332
1333 /* Computes the cost of calling sequence and the cost of return.  */
1334
1335 static void
1336 compute_init_costs (void)
1337 {
1338   rtx rtx_jump, rtx_store, rtx_return, reg, label;
1339   basic_block bb;
1340
1341   FOR_EACH_BB (bb)
1342     if (BB_HEAD (bb))
1343       break;
1344
1345   label = block_label (bb);
1346   reg = gen_rtx_REG (Pmode, 0);
1347
1348   /* Pattern for indirect jump.  */
1349   rtx_jump = gen_indirect_jump (reg);
1350
1351   /* Pattern for storing address.  */
1352   rtx_store = gen_rtx_SET (VOIDmode, reg, gen_symbol_ref_rtx_for_label (label));
1353
1354   /* Pattern for return insn.  */
1355   rtx_return = gen_jump (label);
1356
1357   /* The cost of jump.  */
1358   seq_jump_cost = compute_rtx_cost (make_jump_insn_raw (rtx_jump));
1359
1360   /* The cost of calling sequence.  */
1361   seq_call_cost = seq_jump_cost + compute_rtx_cost (make_insn_raw (rtx_store));
1362
1363   /* The cost of return.  */
1364   seq_return_cost = compute_rtx_cost (make_jump_insn_raw (rtx_return));
1365
1366   /* Simple heuristic for minimal sequence cost.  */
1367   seq_call_cost   = (int)(seq_call_cost * (double)SEQ_CALL_COST_MULTIPLIER);
1368 }
1369
1370 /* Finds equivalent insn sequences in the current function and retains only one
1371    instance of them which is turned into a pseudo-function. The additional
1372    copies are erased and replaced by pseudo-calls to the retained sequence.  */
1373
1374 static void
1375 rtl_seqabstr (void)
1376 {
1377   int iter;
1378   df_set_flags (DF_LR_RUN_DCE);
1379   df_analyze ();
1380
1381   /* Create a hash list for COLLECT_PATTERN_SEQS.  */
1382   hash_buckets = htab_create (HASH_INIT, htab_hash_bucket , htab_eq_bucket ,
1383                               htab_del_bucket);
1384   fill_hash_bucket ();
1385
1386   /* Compute the common cost of abstraction.  */
1387   compute_init_costs ();
1388
1389   /* Build an initial set of pattern sequences from the current function.  */
1390   collect_pattern_seqs ();
1391   dump_pattern_seqs ();
1392
1393   /* Iterate until there are no sequences to abstract.  */
1394   for (iter = 1;; iter++)
1395     {
1396       /* Recompute gain for sequences if necessary and select sequence with
1397          biggest gain.  */
1398       recompute_gain ();
1399       if (!pattern_seqs)
1400         break;
1401       dump_best_pattern_seq (iter);
1402       /* Update the cached info of the other sequences and force gain
1403          recomputation where needed.  */
1404       update_pattern_seqs ();
1405       /* Turn best sequences into pseudo-functions and -calls.  */
1406       abstract_best_seq ();
1407     }
1408
1409   /* Cleanup hash tables.  */
1410   htab_delete (hash_buckets);
1411 }
1412
1413 /* The gate function for TREE_OPT_PASS.  */
1414
1415 static bool
1416 gate_rtl_seqabstr (void)
1417 {
1418   return flag_rtl_seqabstr;
1419 }
1420
1421 /* The entry point of the sequence abstraction algorithm.  */
1422
1423 static unsigned int
1424 rest_of_rtl_seqabstr (void)
1425 {
1426   /* Abstract out common insn sequences. */
1427   rtl_seqabstr ();
1428   return 0;
1429 }
1430
1431 struct rtl_opt_pass pass_rtl_seqabstr =
1432 {
1433  {
1434   RTL_PASS,
1435   "seqabstr",                           /* name */
1436   gate_rtl_seqabstr,                    /* gate */
1437   rest_of_rtl_seqabstr,                 /* execute */
1438   NULL,                                 /* sub */
1439   NULL,                                 /* next */
1440   0,                                    /* static_pass_number */
1441   TV_SEQABSTR,                          /* tv_id */
1442   0,                                    /* properties_required */
1443   0,                                    /* properties_provided */
1444   0,                                    /* properties_destroyed */
1445   0,                                    /* todo_flags_start */
1446   TODO_df_finish | TODO_verify_rtl_sharing |
1447   TODO_dump_func |
1448   TODO_ggc_collect                      /* todo_flags_finish */
1449  }
1450 };