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