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 #if defined STACK_REGS || defined HAVE_cc0
 448   basic_block bb;
 449   bitmap_head dont_collect;
 450
 451   /* Extra initialization step to ensure that no stack registers (if present)
 452      or cc0 code (if present) are live across abnormal edges.
 453      Set a flag in DONT_COLLECT for an insn if a stack register is live
 454      after the insn or the insn is cc0 setter or user.  */
 455   bitmap_initialize (&dont_collect, NULL);
 456
 457 #ifdef STACK_REGS
 458   FOR_EACH_BB (bb)
 459   {
 460     regset_head live;
 461     rtx insn;
 462     rtx prev;
 463
 464     /* Initialize liveness propagation.  */
 465     INIT_REG_SET (&live);
 466     bitmap_copy (&live, DF_LR_OUT (bb));
 467     df_simulate_artificial_refs_at_end (bb, &live);
 468
 469     /* Propagate liveness info and mark insns where a stack reg is live.  */
 470     insn = BB_END (bb);
 471     for (insn = BB_END (bb); ; insn = prev)
 472       {
 473         prev = PREV_INSN (insn);
 474         if (INSN_P (insn))
 475           {
 476             int reg;
 477             for (reg = FIRST_STACK_REG; reg <= LAST_STACK_REG; reg++)
 478               {
 479                 if (REGNO_REG_SET_P (&live, reg))
 480                   {
 481                     bitmap_set_bit (&dont_collect, INSN_UID (insn));
 482                     break;
 483                   }
 484               }
 485
 486           }
 487         if (insn == BB_HEAD (bb))
 488           break;
 489         df_simulate_one_insn (bb, insn, &live);
 490         insn = prev;
 491       }
 492
 493     /* Free unused data.  */
 494     CLEAR_REG_SET (&live);
 495   }
 496 #endif
 497
 498 #ifdef HAVE_cc0
 499   /* Mark CC0 setters and users as ineligible for collection into sequences.
 500      This is an over-conservative fix, since it is OK to include
 501      a cc0_setter, but only if we also include the corresponding cc0_user,
 502      and vice versa.  */
 503   FOR_EACH_BB (bb)
 504   {
 505     rtx insn;
 506     rtx next_tail;
 507
 508     next_tail = NEXT_INSN (BB_END (bb));
 509
 510     for (insn = BB_HEAD (bb); insn != next_tail; insn = NEXT_INSN (insn))
 511       {
 512         if (INSN_P (insn) && reg_mentioned_p (cc0_rtx, PATTERN (insn)))
 513           bitmap_set_bit (&dont_collect, INSN_UID (insn));
 514       }
 515   }
 516 #endif
 517
 518 #endif /* defined STACK_REGS || defined HAVE_cc0 */
 519
 520   /* Initialize PATTERN_SEQS to empty.  */
 521   pattern_seqs = 0;
 522
 523   /* Try to match every abstractable insn with every other insn in the same
 524      HASH_BUCKET.  */
 525
 526   FOR_EACH_HTAB_ELEMENT (hash_buckets, hash_bucket, p_hash_bucket, hti0)
 527     if (htab_elements (hash_bucket->seq_candidates) > 1)
 528       FOR_EACH_HTAB_ELEMENT (hash_bucket->seq_candidates, e0, p_hash_elem, hti1)
 529         FOR_EACH_HTAB_ELEMENT (hash_bucket->seq_candidates, e1, p_hash_elem,
 530                                hti2)
 531           if (e0 != e1
 532 #if defined STACK_REGS || defined HAVE_cc0
 533               && !bitmap_bit_p (&dont_collect, INSN_UID (e0->insn))
 534               && !bitmap_bit_p (&dont_collect, INSN_UID (e1->insn))
 535 #endif
 536              )
 537             match_seqs (e0, e1);
 538 #if defined STACK_REGS || defined HAVE_cc0
 539   /* Free unused data.  */
 540   bitmap_clear (&dont_collect);
 541 #endif
 542 }
 543
 544 /* Transforms a regset to a HARD_REG_SET. Every hard register in REGS is added
 545    to hregs. Additionally, the hard counterpart of every renumbered pseudo
 546    register is also added.  */
 547
 548 static void
 549 renumbered_reg_set_to_hard_reg_set (HARD_REG_SET * hregs, regset regs)
 550 {
 551   int r;
 552
 553   REG_SET_TO_HARD_REG_SET (*hregs, regs);
 554   for (r = FIRST_PSEUDO_REGISTER; r < max_regno; r++)
 555     if (REGNO_REG_SET_P (regs, r) && reg_renumber[r] >= 0)
 556       SET_HARD_REG_BIT (*hregs, reg_renumber[r]);
 557 }
 558
 559 /* Clears the bits in REGS for all registers, which are live in the sequence
 560    give by its last INSN and its LENGTH.  */
 561
 562 static void
 563 clear_regs_live_in_seq (HARD_REG_SET * regs, rtx insn, int length)
 564 {
 565   basic_block bb;
 566   regset_head live;
 567   HARD_REG_SET hlive;
 568   rtx x;
 569   int i;
 570
 571   /* Initialize liveness propagation.  */
 572   bb = BLOCK_FOR_INSN (insn);
 573   INIT_REG_SET (&live);
 574   bitmap_copy (&live, DF_LR_OUT (bb));
 575   df_simulate_artificial_refs_at_end (bb, &live);
 576
 577   /* Propagate until INSN if found.  */
 578   for (x = BB_END (bb); x != insn; x = PREV_INSN (x))
 579     df_simulate_one_insn (bb, x, &live);
 580
 581   /* Clear registers live after INSN.  */
 582   renumbered_reg_set_to_hard_reg_set (&hlive, &live);
 583   AND_COMPL_HARD_REG_SET (*regs, hlive);
 584
 585   /* Clear registers live in and before the sequence.  */
 586   for (i = 0; i < length;)
 587     {
 588       rtx prev = PREV_INSN (x);
 589       df_simulate_one_insn (bb, x, &live);
 590
 591       if (INSN_P (x))
 592         {
 593           renumbered_reg_set_to_hard_reg_set (&hlive, &live);
 594           AND_COMPL_HARD_REG_SET (*regs, hlive);
 595           i++;
 596         }
 597
 598       x = prev;
 599     }
 600
 601   /* Free unused data.  */
 602   CLEAR_REG_SET (&live);
 603 }
 604
 605 /* Computes the gain of turning PSEQ into a pseudo-function and its matching
 606    sequences into pseudo-calls. Also computes and caches the number of insns to
 607    abstract from  the matching sequences.  */
 608
 609 static void
 610 recompute_gain_for_pattern_seq (pattern_seq pseq)
 611 {
 612   matching_seq mseq;
 613   rtx x;
 614   int i;
 615   int hascall;
 616   HARD_REG_SET linkregs;
 617
 618   /* Initialize data.  */
 619   SET_HARD_REG_SET (linkregs);
 620   pseq->link_reg = NULL_RTX;
 621   pseq->abstracted_length = 0;
 622
 623   pseq->gain = -(seq_call_cost - seq_jump_cost + seq_return_cost);
 624
 625   /* Determine ABSTRACTED_LENGTH and COST for matching sequences of PSEQ.
 626      ABSTRACTED_LENGTH may be less than MATCHING_LENGTH if sequences in the
 627      same block overlap. */
 628
 629   for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
 630     {
 631       /* Determine ABSTRACTED_LENGTH.  */
 632       if (mseq->next_matching_seq)
 633         mseq->abstracted_length = (int)(mseq->next_matching_seq->idx -
 634                                         mseq->idx);
 635       else
 636         mseq->abstracted_length = mseq->matching_length;
 637
 638       if (mseq->abstracted_length > mseq->matching_length)
 639         mseq->abstracted_length = mseq->matching_length;
 640
 641       /* Compute the cost of sequence.  */
 642       RECOMPUTE_COST (mseq);
 643
 644       /* If COST is big enough registers live in this matching sequence
 645          should not be used as a link register. Also set ABSTRACTED_LENGTH
 646          of PSEQ.  */
 647       if (mseq->cost > seq_call_cost)
 648         {
 649           clear_regs_live_in_seq (&linkregs, mseq->insn,
 650                                   mseq->abstracted_length);
 651           if (mseq->abstracted_length > pseq->abstracted_length)
 652             pseq->abstracted_length = mseq->abstracted_length;
 653         }
 654     }
 655
 656   /* Modify ABSTRACTED_LENGTH of PSEQ if pattern sequence overlaps with one
 657      of the matching sequences.  */
 658   for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
 659     {
 660       x = pseq->insn;
 661       for (i = 0; (i < pseq->abstracted_length) && (x != mseq->insn); i++)
 662         x = prev_insn_in_block (x);
 663       pseq->abstracted_length = i;
 664     }
 665
 666   /* Compute the cost of pattern sequence.  */
 667   RECOMPUTE_COST (pseq);
 668
 669   /* No gain if COST is too small.  */
 670   if (pseq->cost <= seq_call_cost)
 671   {
 672     pseq->gain = -1;
 673     return;
 674   }
 675
 676   /* Ensure that no matching sequence is longer than the pattern sequence.  */
 677   for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
 678     {
 679       if (mseq->abstracted_length > pseq->abstracted_length)
 680         {
 681           mseq->abstracted_length = pseq->abstracted_length;
 682           RECOMPUTE_COST (mseq);
 683         }
 684       /* Once the length is stabilizing the gain can be calculated.  */
 685       if (mseq->cost > seq_call_cost)
 686         pseq->gain += mseq->cost - seq_call_cost;
 687     }
 688
 689   /* No need to do further work if there is no gain.  */
 690   if (pseq->gain <= 0)
 691     return;
 692
 693   /* Should not use registers live in the pattern sequence as link register.
 694    */
 695   clear_regs_live_in_seq (&linkregs, pseq->insn, pseq->abstracted_length);
 696
 697   /* Determine whether pattern sequence contains a call_insn.  */
 698   hascall = 0;
 699   x = pseq->insn;
 700   for (i = 0; i < pseq->abstracted_length; i++)
 701     {
 702       if (CALL_P (x))
 703         {
 704           hascall = 1;
 705           break;
 706         }
 707       x = prev_insn_in_block (x);
 708     }
 709
 710   /* Should not use a register as a link register if - it is a fixed
 711      register, or - the sequence contains a call insn and the register is a
 712      call used register, or - the register needs to be saved if used in a
 713      function but was not used before (since saving it can invalidate already
 714      computed frame pointer offsets), or - the register cannot be used as a
 715      base register.  */
 716
 717   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 718     if (fixed_regs[i]
 719 #ifdef REGNO_OK_FOR_INDIRECT_JUMP_P
 720         || (!REGNO_OK_FOR_INDIRECT_JUMP_P (i, Pmode))
 721 #else
 722         || (!ok_for_base_p_1 (i, Pmode, MEM, SCRATCH))
 723         || (!reg_class_subset_p (REGNO_REG_CLASS (i),
 724                                  base_reg_class (VOIDmode, MEM, SCRATCH)))
 725 #endif
 726         || (hascall && call_used_regs[i])
 727         || (!call_used_regs[i] && !df_regs_ever_live_p (i)))
 728       CLEAR_HARD_REG_BIT (linkregs, i);
 729
 730   /* Find an appropriate register to be used as the link register.  */
 731   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 732     if (TEST_HARD_REG_BIT (linkregs, i))
 733       {
 734         pseq->link_reg = gen_rtx_REG (Pmode, i);
 735         break;
 736       }
 737
 738   /* Abstraction is not possible if no link register is available, so set
 739      gain to 0.  */
 740   if (!pseq->link_reg)
 741     pseq->gain = 0;
 742 }
 743
 744 /* Deallocates memory occupied by PSEQ and its matching seqs.  */
 745
 746 static void
 747 free_pattern_seq (pattern_seq pseq)
 748 {
 749   while (pseq->matching_seqs)
 750     {
 751       matching_seq mseq = pseq->matching_seqs;
 752       pseq->matching_seqs = mseq->next_matching_seq;
 753       free (mseq);
 754     }
 755   free (pseq);
 756 }
 757
 758
 759 /* Computes the gain for pattern sequences. Pattern sequences producing no gain
 760    are deleted. The pattern sequence with the biggest gain is moved to the first
 761    place of PATTERN_SEQS.  */
 762
 763 static void
 764 recompute_gain (void)
 765 {
 766   pattern_seq *pseq;
 767   int maxgain;
 768
 769   maxgain = 0;
 770   for (pseq = &pattern_seqs; *pseq;)
 771     {
 772       if ((*pseq)->gain <= 0)
 773         recompute_gain_for_pattern_seq (*pseq);
 774
 775       if ((*pseq)->gain > 0)
 776         {
 777           if ((*pseq)->gain > maxgain)
 778             {
 779               pattern_seq temp = *pseq;
 780               (*pseq) = temp->next_pattern_seq;
 781               temp->next_pattern_seq = pattern_seqs;
 782               pattern_seqs = temp;
 783               maxgain = pattern_seqs->gain;
 784             }
 785           else
 786             {
 787               pseq = &(*pseq)->next_pattern_seq;
 788             }
 789         }
 790       else
 791         {
 792           pattern_seq temp = *pseq;
 793           *pseq = temp->next_pattern_seq;
 794           free_pattern_seq (temp);
 795         }
 796     }
 797 }
 798
 799 /* Updated those pattern sequences and matching sequences, which overlap with
 800    the sequence given by INSN and LEN. Deletes sequences shrinking below a
 801    limit.  */
 802
 803 static void
 804 erase_from_pattern_seqs (rtx insn, int len)
 805 {
 806   pattern_seq *pseq;
 807   matching_seq *mseq;
 808   rtx x;
 809   int plen, mlen;
 810   int pcost, mcost;
 811
 812   while (len > 0)
 813     {
 814       for (pseq = &pattern_seqs; *pseq;)
 815         {
 816           plen = 0;
 817           pcost = 0;
 818           for (x = (*pseq)->insn; x && (x != insn);
 819                x = prev_insn_in_block (x))
 820             {
 821               plen++;
 822               pcost += compute_rtx_cost (x);
 823             }
 824
 825           if (pcost <= seq_call_cost)
 826             {
 827               pattern_seq temp = *pseq;
 828               *pseq = temp->next_pattern_seq;
 829               free_pattern_seq (temp);
 830             }
 831           else
 832             {
 833               for (mseq = &(*pseq)->matching_seqs; *mseq;)
 834                 {
 835                   mlen = 0;
 836                   mcost = 0;
 837                   for (x = (*mseq)->insn;
 838                        x && (x != insn) && (mlen < plen)
 839                        && (mlen < (*mseq)->matching_length);
 840                        x = prev_insn_in_block (x))
 841                     {
 842                       mlen++;
 843                       mcost += compute_rtx_cost (x);
 844                     }
 845
 846                   if (mcost <= seq_call_cost)
 847                     {
 848                       matching_seq temp = *mseq;
 849                       *mseq = temp->next_matching_seq;
 850                       free (temp);
 851                       /* Set to 0 to force gain recomputation.  */
 852                       (*pseq)->gain = 0;
 853                     }
 854                   else
 855                     {
 856                       if (mlen < (*mseq)->matching_length)
 857                         {
 858                           (*mseq)->cost = mcost;
 859                           (*mseq)->matching_length = mlen;
 860                           /* Set to 0 to force gain recomputation.  */
 861                           (*pseq)->gain = 0;
 862                         }
 863                       mseq = &(*mseq)->next_matching_seq;
 864                     }
 865                 }
 866
 867               pseq = &(*pseq)->next_pattern_seq;
 868             }
 869         }
 870
 871       len--;
 872       insn = prev_insn_in_block (insn);
 873     }
 874 }
 875
 876 /* Updates those pattern sequences and matching sequences, which overlap with
 877    the pattern sequence with the biggest gain and its matching sequences.  */
 878
 879 static void
 880 update_pattern_seqs (void)
 881 {
 882   pattern_seq bestpseq;
 883   matching_seq mseq;
 884
 885   bestpseq = pattern_seqs;
 886   pattern_seqs = bestpseq->next_pattern_seq;
 887
 888   for (mseq = bestpseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
 889     if (mseq->cost > seq_call_cost)
 890       erase_from_pattern_seqs (mseq->insn, mseq->abstracted_length);
 891   erase_from_pattern_seqs (bestpseq->insn, bestpseq->abstracted_length);
 892
 893   bestpseq->next_pattern_seq = pattern_seqs;
 894   pattern_seqs = bestpseq;
 895 }
 896
 897 /* Groups together those matching sequences of the best pattern sequence, which
 898    have the same ABSTRACTED_LENGTH and puts these groups in ascending order.
 899    SEQ_BLOCKS contains the result.  */
 900
 901 static void
 902 determine_seq_blocks (void)
 903 {
 904   seq_block sb;
 905   matching_seq *mseq;
 906   matching_seq m;
 907
 908   /* Initialize SEQ_BLOCKS to empty.  */
 909   seq_blocks = 0;
 910
 911   /* Process all matching sequences.  */
 912   for (mseq = &pattern_seqs->matching_seqs; *mseq;)
 913     {
 914       /* Deal only with matching sequences being long enough. */
 915       if ((*mseq)->cost <= seq_call_cost)
 916         {
 917           mseq = &(*mseq)->next_matching_seq;
 918           continue;
 919         }
 920
 921       /* Ensure that SB contains a seq_block with the appropriate length.
 922          Insert a new seq_block if necessary.  */
 923       if (!seq_blocks || ((*mseq)->abstracted_length < seq_blocks->length))
 924         {
 925           sb = (seq_block) xmalloc (sizeof (struct seq_block_def));
 926           sb->length = (*mseq)->abstracted_length;
 927           sb->label = NULL_RTX;
 928           sb->matching_seqs = 0;
 929           sb->next_seq_block = seq_blocks;
 930           seq_blocks = sb;
 931         }
 932       else
 933         {
 934           for (sb = seq_blocks; sb; sb = sb->next_seq_block)
 935             {
 936               if ((*mseq)->abstracted_length == sb->length)
 937                 break;
 938               if (!sb->next_seq_block
 939                   || ((*mseq)->abstracted_length <
 940                       sb->next_seq_block->length))
 941                 {
 942                   seq_block temp =
 943                     (seq_block) xmalloc (sizeof (struct seq_block_def));
 944                   temp->length = (*mseq)->abstracted_length;
 945                   temp->label = NULL_RTX;
 946                   temp->matching_seqs = 0;
 947                   temp->next_seq_block = sb->next_seq_block;
 948                   sb->next_seq_block = temp;
 949                 }
 950             }
 951         }
 952
 953       /* Remove the matching sequence from the linked list of the pattern
 954          sequence and link it to SB.  */
 955       m = *mseq;
 956       *mseq = m->next_matching_seq;
 957       m->next_matching_seq = sb->matching_seqs;
 958       sb->matching_seqs = m;
 959     }
 960 }
 961
 962 /* Builds a symbol_ref for LABEL.  */
 963
 964 static rtx
 965 gen_symbol_ref_rtx_for_label (const_rtx label)
 966 {
 967   char name[20];
 968   rtx sym;
 969
 970   ASM_GENERATE_INTERNAL_LABEL (name, "L", CODE_LABEL_NUMBER (label));
 971   sym = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (name));
 972   SYMBOL_REF_FLAGS (sym) = SYMBOL_FLAG_LOCAL;
 973   return sym;
 974 }
 975
 976 /* Splits basic block at the requested insn and rebuilds dataflow.  */
 977
 978 static basic_block
 979 split_block_and_df_analyze (basic_block bb, rtx insn)
 980 {
 981   basic_block next;
 982   next = split_block (bb, insn)->dest;
 983   df_analyze ();
 984   return next;
 985 }
 986
 987 /* Ensures that INSN is the last insn in its block and returns the block label
 988    of the next block.  */
 989
 990 static rtx
 991 block_label_after (rtx insn)
 992 {
 993   basic_block bb = BLOCK_FOR_INSN (insn);
 994   if ((insn == BB_END (bb)) && (bb->next_bb != EXIT_BLOCK_PTR))
 995     return block_label (bb->next_bb);
 996   else
 997     return block_label (split_block_and_df_analyze (bb, insn));
 998 }
 999
1000 /* Ensures that the last insns of the best pattern and its matching sequences
1001    are the last insns in their block. Additionally, extends the live set at the
1002    end of the pattern sequence with the live sets at the end of the matching
1003    sequences.  */
1004
1005 static void
1006 split_blocks_after_seqs (void)
1007 {
1008   seq_block sb;
1009   matching_seq mseq;
1010
1011   block_label_after (pattern_seqs->insn);
1012   for (sb = seq_blocks; sb; sb = sb->next_seq_block)
1013     {
1014       for (mseq = sb->matching_seqs; mseq; mseq = mseq->next_matching_seq)
1015         {
1016           block_label_after (mseq->insn);
1017           IOR_REG_SET (df_get_live_out (BLOCK_FOR_INSN (pattern_seqs->insn)),
1018                        df_get_live_out (BLOCK_FOR_INSN (mseq->insn)));
1019         }
1020     }
1021 }
1022
1023 /* Splits the best pattern sequence according to SEQ_BLOCKS. Emits pseudo-call
1024    and -return insns before and after the sequence.  */
1025
1026 static void
1027 split_pattern_seq (void)
1028 {
1029   rtx insn;
1030   basic_block bb;
1031   rtx retlabel, retjmp, saveinsn;
1032   int i;
1033   seq_block sb;
1034
1035   insn = pattern_seqs->insn;
1036   bb = BLOCK_FOR_INSN (insn);
1037
1038   /* Get the label after the sequence. This will be the return address. The
1039      label will be referenced using a symbol_ref so protect it from
1040      deleting.  */
1041   retlabel = block_label_after (insn);
1042   LABEL_PRESERVE_P (retlabel) = 1;
1043
1044   /* Emit an indirect jump via the link register after the sequence acting
1045      as the return insn.  Also emit a barrier and update the basic block.  */
1046   if (!find_reg_note (BB_END (bb), REG_NORETURN, NULL))
1047     retjmp = emit_jump_insn_after (gen_indirect_jump (pattern_seqs->link_reg),
1048                                    BB_END (bb));
1049   emit_barrier_after (BB_END (bb));
1050
1051   /* Replace all outgoing edges with a new one to the block of RETLABEL.  */
1052   while (EDGE_COUNT (bb->succs) != 0)
1053     remove_edge (EDGE_SUCC (bb, 0));
1054   make_edge (bb, BLOCK_FOR_INSN (retlabel), EDGE_ABNORMAL);
1055
1056   /* Split the sequence according to SEQ_BLOCKS and cache the label of the
1057      resulting basic blocks.  */
1058   i = 0;
1059   for (sb = seq_blocks; sb; sb = sb->next_seq_block)
1060     {
1061       for (; i < sb->length; i++)
1062         insn = prev_insn_in_block (insn);
1063
1064       sb->label = block_label (split_block_and_df_analyze (bb, insn));
1065     }
1066
1067   /* Emit an insn saving the return address to the link register before the
1068      sequence.  */
1069   saveinsn = emit_insn_after (gen_move_insn (pattern_seqs->link_reg,
1070                               gen_symbol_ref_rtx_for_label
1071                               (retlabel)), BB_END (bb));
1072   /* Update liveness info.  */
1073   SET_REGNO_REG_SET (df_get_live_out (bb),
1074                      REGNO (pattern_seqs->link_reg));
1075 }
1076
1077 /* Deletes the insns of the matching sequences of the best pattern sequence and
1078    replaces them with pseudo-calls to the pattern sequence.  */
1079
1080 static void
1081 erase_matching_seqs (void)
1082 {
1083   seq_block sb;
1084   matching_seq mseq;
1085   rtx insn;
1086   basic_block bb;
1087   rtx retlabel, saveinsn, callinsn;
1088   int i;
1089
1090   for (sb = seq_blocks; sb; sb = sb->next_seq_block)
1091     {
1092       for (mseq = sb->matching_seqs; mseq; mseq = mseq->next_matching_seq)
1093         {
1094           insn = mseq->insn;
1095           bb = BLOCK_FOR_INSN (insn);
1096
1097           /* Get the label after the sequence. This will be the return
1098              address. The label will be referenced using a symbol_ref so
1099              protect it from deleting.  */
1100           retlabel = block_label_after (insn);
1101           LABEL_PRESERVE_P (retlabel) = 1;
1102
1103           /* Delete the insns of the sequence.  */
1104           for (i = 0; i < sb->length; i++)
1105             insn = prev_insn_in_block (insn);
1106           delete_basic_block (split_block_and_df_analyze (bb, insn));
1107
1108           /* Emit an insn saving the return address to the link register
1109              before the deleted sequence.  */
1110           saveinsn = emit_insn_after (gen_move_insn (pattern_seqs->link_reg,
1111                                       gen_symbol_ref_rtx_for_label
1112                                       (retlabel)),
1113                                       BB_END (bb));
1114           BLOCK_FOR_INSN (saveinsn) = bb;
1115
1116           /* Emit a jump to the appropriate part of the pattern sequence
1117              after the save insn. Also update the basic block.  */
1118           callinsn = emit_jump_insn_after (gen_jump (sb->label), saveinsn);
1119           JUMP_LABEL (callinsn) = sb->label;
1120           LABEL_NUSES (sb->label)++;
1121           BLOCK_FOR_INSN (callinsn) = bb;
1122           BB_END (bb) = callinsn;
1123
1124           /* Maintain control flow and liveness information.  */
1125           SET_REGNO_REG_SET (df_get_live_out (bb),
1126                              REGNO (pattern_seqs->link_reg));
1127           emit_barrier_after (BB_END (bb));
1128           make_single_succ_edge (bb, BLOCK_FOR_INSN (sb->label), 0);
1129           IOR_REG_SET (df_get_live_out (bb),
1130                        df_get_live_in (BLOCK_FOR_INSN (sb->label)));
1131
1132           make_edge (BLOCK_FOR_INSN (seq_blocks->label),
1133                      BLOCK_FOR_INSN (retlabel), EDGE_ABNORMAL);
1134         }
1135     }
1136 }
1137
1138 /* Deallocates SEQ_BLOCKS and all the matching sequences.  */
1139
1140 static void
1141 free_seq_blocks (void)
1142 {
1143   while (seq_blocks)
1144     {
1145       seq_block sb = seq_blocks;
1146       while (sb->matching_seqs)
1147         {
1148           matching_seq mseq = sb->matching_seqs;
1149           sb->matching_seqs = mseq->next_matching_seq;
1150           free (mseq);
1151         }
1152       seq_blocks = sb->next_seq_block;
1153       free (sb);
1154     }
1155 }
1156
1157 /* Transforms the best pattern sequence into a pseudo-function and its matching
1158    sequences to pseudo-calls. Afterwards the best pattern sequence is removed
1159    from PATTERN_SEQS.  */
1160
1161 static void
1162 abstract_best_seq (void)
1163 {
1164   pattern_seq bestpseq;
1165
1166   /* Do the abstraction.  */
1167   determine_seq_blocks ();
1168   split_blocks_after_seqs ();
1169   split_pattern_seq ();
1170   erase_matching_seqs ();
1171   free_seq_blocks ();
1172
1173   /* Record the usage of the link register.  */
1174   df_set_regs_ever_live (REGNO (pattern_seqs->link_reg), true);
1175
1176   /* Remove the best pattern sequence.  */
1177   bestpseq = pattern_seqs;
1178   pattern_seqs = bestpseq->next_pattern_seq;
1179   free_pattern_seq (bestpseq);
1180 }
1181
1182 /* Prints info on the pattern sequences to the dump file.  */
1183
1184 static void
1185 dump_pattern_seqs (void)
1186 {
1187   pattern_seq pseq;
1188   matching_seq mseq;
1189
1190   if (!dump_file)
1191     return;
1192
1193   fprintf (dump_file, ";; Pattern sequences\n");
1194   for (pseq = pattern_seqs; pseq; pseq = pseq->next_pattern_seq)
1195     {
1196       fprintf (dump_file, "Pattern sequence at insn %d matches sequences at",
1197                INSN_UID (pseq->insn));
1198       for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
1199         {
1200           fprintf (dump_file, " insn %d (length %d)", INSN_UID (mseq->insn),
1201                    mseq->matching_length);
1202           if (mseq->next_matching_seq)
1203             fprintf (dump_file, ",");
1204         }
1205       fprintf (dump_file, ".\n");
1206     }
1207   fprintf (dump_file, "\n");
1208 }
1209
1210 /* Prints info on the best pattern sequence transformed in the ITER-th
1211    iteration to the dump file.  */
1212
1213 static void
1214 dump_best_pattern_seq (int iter)
1215 {
1216   matching_seq mseq;
1217
1218   if (!dump_file)
1219     return;
1220
1221   fprintf (dump_file, ";; Iteration %d\n", iter);
1222   fprintf (dump_file,
1223            "Best pattern sequence with %d gain is at insn %d (length %d).\n",
1224            pattern_seqs->gain, INSN_UID (pattern_seqs->insn),
1225            pattern_seqs->abstracted_length);
1226   fprintf (dump_file, "Matching sequences are at");
1227   for (mseq = pattern_seqs->matching_seqs; mseq;
1228        mseq = mseq->next_matching_seq)
1229     {
1230       fprintf (dump_file, " insn %d (length %d)", INSN_UID (mseq->insn),
1231                mseq->abstracted_length);
1232       if (mseq->next_matching_seq)
1233         fprintf (dump_file, ",");
1234     }
1235   fprintf (dump_file, ".\n");
1236   fprintf (dump_file, "Using reg %d as link register.\n\n",
1237            REGNO (pattern_seqs->link_reg));
1238 }
1239
1240 /* Htab hash function for hash_bucket_def structure.  */
1241
1242 static unsigned int
1243 htab_hash_bucket (const void *p)
1244 {
1245   const_p_hash_bucket bucket = (const_p_hash_bucket) p;
1246   return bucket->hash;
1247 }
1248
1249 /* Htab equal function for hash_bucket_def structure.  */
1250
1251 static int
1252 htab_eq_bucket (const void *p0, const void *p1)
1253 {
1254   return htab_hash_bucket (p0) == htab_hash_bucket (p1);
1255 }
1256
1257 /* Htab delete function for hash_bucket_def structure.  */
1258
1259 static void
1260 htab_del_bucket (void *p)
1261 {
1262   p_hash_bucket bucket = (p_hash_bucket) p;
1263
1264   if (bucket->seq_candidates)
1265     htab_delete (bucket->seq_candidates);
1266
1267   free (bucket);
1268 }
1269
1270 /* Htab hash function for hash_bucket_def structure.  */
1271
1272 static unsigned int
1273 htab_hash_elem (const void *p)
1274 {
1275   const_p_hash_elem elem = (const_p_hash_elem) p;
1276   return htab_hash_pointer (elem->insn);
1277 }
1278
1279 /* Htab equal function for hash_bucket_def structure.  */
1280
1281 static int
1282 htab_eq_elem (const void *p0, const void *p1)
1283 {
1284   return htab_hash_elem (p0) == htab_hash_elem (p1);
1285 }
1286
1287 /* Htab delete function for hash_bucket_def structure.  */
1288
1289 static void
1290 htab_del_elem (void *p)
1291 {
1292   p_hash_elem elem = (p_hash_elem) p;
1293   free (elem);
1294 }
1295
1296 /* Creates a hash value for each sequence candidate and saves them
1297    in HASH_BUCKET.  */
1298
1299 static void
1300 fill_hash_bucket (void)
1301 {
1302   basic_block bb;
1303   rtx insn;
1304   void **slot;
1305   p_hash_bucket bucket;
1306   struct hash_bucket_def tmp_bucket;
1307   p_hash_elem elem;
1308   unsigned long insn_idx;
1309
1310   insn_idx = 0;
1311   FOR_EACH_BB (bb)
1312     {
1313       FOR_BB_INSNS_REVERSE (bb, insn)
1314         {
1315           if (!ABSTRACTABLE_INSN_P (insn))
1316             continue;
1317
1318           /* Compute hash value for INSN.  */
1319           tmp_bucket.hash = compute_hash (insn);
1320
1321           /* Select the hash group.  */
1322           bucket = htab_find (hash_buckets, &tmp_bucket);
1323
1324           if (!bucket)
1325             {
1326               /* Create a new hash group.  */
1327               bucket = (p_hash_bucket) xcalloc (1,
1328                                         sizeof (struct hash_bucket_def));
1329               bucket->hash = tmp_bucket.hash;
1330               bucket->seq_candidates = NULL;
1331
1332               slot = htab_find_slot (hash_buckets, &tmp_bucket, INSERT);
1333               *slot = bucket;
1334             }
1335
1336           /* Create new list for storing sequence candidates.  */
1337           if (!bucket->seq_candidates)
1338               bucket->seq_candidates = htab_create (HASH_INIT,
1339                                                     htab_hash_elem,
1340                                                     htab_eq_elem,
1341                                                     htab_del_elem);
1342
1343           elem = (p_hash_elem) xcalloc (1, sizeof (struct hash_elem_def));
1344           elem->insn = insn;
1345           elem->idx = insn_idx;
1346           elem->length = get_attr_length (insn);
1347
1348           /* Insert INSN into BUCKET hash bucket.  */
1349           slot = htab_find_slot (bucket->seq_candidates, elem, INSERT);
1350           *slot = elem;
1351
1352           insn_idx++;
1353         }
1354     }
1355 }
1356
1357 /* Computes the cost of calling sequence and the cost of return.  */
1358
1359 static void
1360 compute_init_costs (void)
1361 {
1362   rtx rtx_jump, rtx_store, rtx_return, reg, label;
1363   basic_block bb;
1364
1365   FOR_EACH_BB (bb)
1366     if (BB_HEAD (bb))
1367       break;
1368
1369   label = block_label (bb);
1370   reg = gen_rtx_REG (Pmode, 0);
1371
1372   /* Pattern for indirect jump.  */
1373   rtx_jump = gen_indirect_jump (reg);
1374
1375   /* Pattern for storing address.  */
1376   rtx_store = gen_rtx_SET (VOIDmode, reg, gen_symbol_ref_rtx_for_label (label));
1377
1378   /* Pattern for return insn.  */
1379   rtx_return = gen_jump (label);
1380
1381   /* The cost of jump.  */
1382   seq_jump_cost = compute_rtx_cost (make_jump_insn_raw (rtx_jump));
1383
1384   /* The cost of calling sequence.  */
1385   seq_call_cost = seq_jump_cost + compute_rtx_cost (make_insn_raw (rtx_store));
1386
1387   /* The cost of return.  */
1388   seq_return_cost = compute_rtx_cost (make_jump_insn_raw (rtx_return));
1389
1390   /* Simple heuristic for minimal sequence cost.  */
1391   seq_call_cost   = (int)(seq_call_cost * (double)SEQ_CALL_COST_MULTIPLIER);
1392 }
1393
1394 /* Finds equivalent insn sequences in the current function and retains only one
1395    instance of them which is turned into a pseudo-function. The additional
1396    copies are erased and replaced by pseudo-calls to the retained sequence.  */
1397
1398 static void
1399 rtl_seqabstr (void)
1400 {
1401   int iter;
1402   df_set_flags (DF_LR_RUN_DCE);
1403   df_analyze ();
1404
1405   /* Create a hash list for COLLECT_PATTERN_SEQS.  */
1406   hash_buckets = htab_create (HASH_INIT, htab_hash_bucket , htab_eq_bucket ,
1407                               htab_del_bucket);
1408   fill_hash_bucket ();
1409
1410   /* Compute the common cost of abstraction.  */
1411   compute_init_costs ();
1412
1413   /* Build an initial set of pattern sequences from the current function.  */
1414   collect_pattern_seqs ();
1415   dump_pattern_seqs ();
1416
1417   /* Iterate until there are no sequences to abstract.  */
1418   for (iter = 1;; iter++)
1419     {
1420       /* Recompute gain for sequences if necessary and select sequence with
1421          biggest gain.  */
1422       recompute_gain ();
1423       if (!pattern_seqs)
1424         break;
1425       dump_best_pattern_seq (iter);
1426       /* Update the cached info of the other sequences and force gain
1427          recomputation where needed.  */
1428       update_pattern_seqs ();
1429       /* Turn best sequences into pseudo-functions and -calls.  */
1430       abstract_best_seq ();
1431     }
1432
1433   /* Cleanup hash tables.  */
1434   htab_delete (hash_buckets);
1435 }
1436
1437 /* The gate function for TREE_OPT_PASS.  */
1438
1439 static bool
1440 gate_rtl_seqabstr (void)
1441 {
1442   return flag_rtl_seqabstr;
1443 }
1444
1445 /* The entry point of the sequence abstraction algorithm.  */
1446
1447 static unsigned int
1448 rest_of_rtl_seqabstr (void)
1449 {
1450   /* Abstract out common insn sequences. */
1451   rtl_seqabstr ();
1452   return 0;
1453 }
1454
1455 struct rtl_opt_pass pass_rtl_seqabstr =
1456 {
1457  {
1458   RTL_PASS,
1459   "seqabstr",                           /* name */
1460   gate_rtl_seqabstr,                    /* gate */
1461   rest_of_rtl_seqabstr,                 /* execute */
1462   NULL,                                 /* sub */
1463   NULL,                                 /* next */
1464   0,                                    /* static_pass_number */
1465   TV_SEQABSTR,                          /* tv_id */
1466   0,                                    /* properties_required */
1467   0,                                    /* properties_provided */
1468   0,                                    /* properties_destroyed */
1469   0,                                    /* todo_flags_start */
1470   TODO_df_finish | TODO_verify_rtl_sharing |
1471   TODO_dump_func |
1472   TODO_ggc_collect                      /* todo_flags_finish */
1473  }
1474 };