OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [rtl-factoring.c] - Blame information for rev 816

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.