* invoke.texi (mstringop-strategy): Add missing "byte_loop" value.
[official-gcc.git] / gcc / rtl-factoring.c
blob8113306e0e87cabcd7dc8f15a717dc46a66e1ea5
1 /* RTL factoring (sequence abstraction).
2 Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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. */
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"
41 /* Sequence abstraction:
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.
48 There are four major parts of this file:
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.
56 FILL_HASH_BUCKET creates all hash values and stores into HASH_BUCKETS.
57 The result is used by COLLECT_PATTERN_SEQS.
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.
65 COLLECT_PATTERN_SEQS does the code matching and stores the results into
66 PATTERN_SEQS.
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.
74 RECOMPUTE_GAIN does the gain computation. The sequences with the maximum
75 gain is on the top of PATTERN_SEQS.
77 abstract code
78 This part turns the pattern sequence into a pseudo-function and its
79 matching sequences into pseudo-calls.
81 ABSTRACT_BEST_SEQ does the code merging.
84 C code example:
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;
105 exit_1:
106 ... ...
107 jump_label = &&exit_2;
108 goto entry_0;
113 exit_2:
114 ... ...
115 jump_label = &&exit_3;
116 goto entry_0;
121 exit_3:
122 ... ...
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.
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))
137 /* First parameter of the htab_create function call. */
138 #define HASH_INIT 1023
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
146 /* Recomputes the cost of MSEQ pattern/matching sequence. */
147 #define RECOMPUTE_COST(SEQ) \
149 int l; \
150 rtx x = SEQ->insn; \
151 SEQ->cost = 0; \
152 for (l = 0; l < SEQ->abstracted_length; l++) \
154 SEQ->cost += compute_rtx_cost (x); \
155 x = prev_insn_in_block (x); \
159 /* A sequence matching a pattern sequence. */
160 typedef struct matching_seq_def
162 /* The last insn in the matching sequence. */
163 rtx insn;
165 /* Index of INSN instruction. */
166 unsigned long idx;
168 /* The number of insns matching in this sequence and the pattern sequence.
170 int matching_length;
172 /* The number of insns selected to abstract from this sequence. Less than
173 or equal to MATCHING_LENGTH. */
174 int abstracted_length;
176 /* The cost of the sequence. */
177 int cost;
179 /* The next sequence in the chain matching the same pattern. */
180 struct matching_seq_def *next_matching_seq;
181 } *matching_seq;
184 /* A pattern instruction sequence. */
185 typedef struct pattern_seq_def
187 /* The last insn in the pattern sequence. */
188 rtx insn;
190 /* Index of INSN instruction. */
191 unsigned long idx;
193 /* The gain of transforming the pattern sequence into a pseudo-function and
194 the matching sequences into pseudo-calls. */
195 int gain;
197 /* The maximum of the ABSTRACTED_LENGTH of the matching sequences. */
198 int abstracted_length;
200 /* The cost of the sequence. */
201 int cost;
203 /* The register used to hold the return address during the pseudo-call. */
204 rtx link_reg;
206 /* The sequences matching this pattern. */
207 matching_seq matching_seqs;
209 /* The next pattern sequence in the chain. */
210 struct pattern_seq_def *next_pattern_seq;
211 } *pattern_seq;
214 /* A block of a pattern sequence. */
215 typedef struct seq_block_def
217 /* The number of insns in the block. */
218 int length;
220 /* The code_label of the block. */
221 rtx label;
223 /* The sequences entering the pattern sequence at LABEL. */
224 matching_seq matching_seqs;
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;
231 /* Contains same sequence candidates for further searching. */
232 typedef struct hash_bucket_def
234 /* The hash value of the group. */
235 unsigned int hash;
237 /* List of sequence candidates. */
238 htab_t seq_candidates;
239 } *p_hash_bucket;
241 /* Contains the last insn of the sequence, and its index value. */
242 typedef struct hash_elem_def
244 /* Unique index; ordered by FILL_HASH_BUCKET. */
245 unsigned long idx;
247 /* The last insn in the sequence. */
248 rtx insn;
250 /* The cached length of the insn. */
251 int length;
252 } *p_hash_elem;
254 /* The list of same sequence candidates. */
255 static htab_t hash_buckets;
257 /* The pattern sequences collected from the current functions. */
258 static pattern_seq pattern_seqs;
260 /* The blocks of the current pattern sequence. */
261 static seq_block seq_blocks;
263 /* Cost of calling sequence. */
264 static int seq_call_cost;
266 /* Cost of jump. */
267 static int seq_jump_cost;
269 /* Cost of returning. */
270 static int seq_return_cost;
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. */
275 static rtx
276 prev_insn_in_block (rtx insn)
278 basic_block bb = BLOCK_FOR_INSN (insn);
280 if (!bb)
281 return NULL_RTX;
283 while (insn != BB_HEAD (bb))
285 insn = PREV_INSN (insn);
286 if (INSN_P (insn))
287 return insn;
289 return NULL_RTX;
292 /* Returns the hash value of INSN. */
294 static unsigned int
295 compute_hash (rtx insn)
297 unsigned int hash = 0;
298 rtx prev;
300 hash = INSN_CODE (insn) * 100;
302 prev = prev_insn_in_block (insn);
303 if (prev)
304 hash += INSN_CODE (prev);
306 return hash;
309 /* Compute the cost of INSN rtx for abstraction. */
311 static int
312 compute_rtx_cost (rtx insn)
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;
320 /* Compute hash value for INSN. */
321 tmp_bucket.hash = compute_hash (insn);
323 /* Select the hash group. */
324 bucket = htab_find (hash_buckets, &tmp_bucket);
326 if (bucket)
328 tmp_elem.insn = insn;
330 /* Select the insn. */
331 elem = htab_find (bucket->seq_candidates, &tmp_elem);
333 /* If INSN is parsed the cost will be the cached length. */
334 if (elem)
335 cost = elem->length;
338 /* If we can't parse the INSN cost will be the instruction length. */
339 if (cost == -1)
341 cost = get_attr_length (insn);
343 /* Cache the length. */
344 if (elem)
345 elem->length = cost;
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);
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.
357 static void
358 matching_length (rtx insn1, rtx insn2, int* len, int* cost)
360 rtx x1;
361 rtx x2;
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)))
370 (*len)++;
371 (*cost) += compute_rtx_cost (x1);
372 x1 = prev_insn_in_block (x1);
373 x2 = prev_insn_in_block (x2);
377 /* Adds E0 as a pattern sequence to PATTERN_SEQS with E1 as a matching
378 sequence. */
380 static void
381 match_seqs (p_hash_elem e0, p_hash_elem e1)
383 int len;
384 int cost;
385 matching_seq mseq, p_prev, p_next;
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;
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)
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;
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)
416 p_prev = p_next;
417 p_next = p_next->next_matching_seq;
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;
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;
436 /* Collects all pattern sequences and their matching sequences and puts them
437 into PATTERN_SEQS. */
439 static void
440 collect_pattern_seqs (void)
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;
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);
454 FOR_EACH_BB (bb)
456 regset_head live;
457 struct propagate_block_info *pbi;
458 rtx insn;
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);
465 /* Propagate liveness info and mark insns where a stack reg is live. */
466 insn = BB_END (bb);
467 while (1)
469 int reg;
470 for (reg = FIRST_STACK_REG; reg <= LAST_STACK_REG; reg++)
472 if (REGNO_REG_SET_P (&live, reg))
474 bitmap_set_bit (&stack_reg_live, INSN_UID (insn));
475 break;
479 if (insn == BB_HEAD (bb))
480 break;
481 insn = propagate_one_insn (pbi, insn);
484 /* Free unused data. */
485 CLEAR_REG_SET (&live);
486 free_propagate_block_info (pbi);
488 #endif
490 /* Initialize PATTERN_SEQS to empty. */
491 pattern_seqs = 0;
493 /* Try to match every abstractable insn with every other insn in the same
494 HASH_BUCKET. */
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
507 match_seqs (e0, e1);
508 #ifdef STACK_REGS
509 /* Free unused data. */
510 bitmap_clear (&stack_reg_live);
511 #endif
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. */
518 static void
519 renumbered_reg_set_to_hard_reg_set (HARD_REG_SET * hregs, regset regs)
521 int r;
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]);
529 /* Clears the bits in REGS for all registers, which are live in the sequence
530 give by its last INSN and its LENGTH. */
532 static void
533 clear_regs_live_in_seq (HARD_REG_SET * regs, rtx insn, int length)
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;
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);
548 /* Propagate until INSN if found. */
549 for (x = BB_END (bb); x != insn;)
550 x = propagate_one_insn (pbi, x);
552 /* Clear registers live after INSN. */
553 renumbered_reg_set_to_hard_reg_set (&hlive, &live);
554 AND_COMPL_HARD_REG_SET (*regs, hlive);
556 /* Clear registers live in and before the sequence. */
557 for (i = 0; i < length;)
559 rtx prev = propagate_one_insn (pbi, x);
561 if (INSN_P (x))
563 renumbered_reg_set_to_hard_reg_set (&hlive, &live);
564 AND_COMPL_HARD_REG_SET (*regs, hlive);
565 i++;
568 x = prev;
571 /* Free unused data. */
572 free_propagate_block_info (pbi);
573 CLEAR_REG_SET (&live);
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. */
580 static void
581 recompute_gain_for_pattern_seq (pattern_seq pseq)
583 matching_seq mseq;
584 rtx x;
585 int i;
586 int hascall;
587 HARD_REG_SET linkregs;
589 /* Initialize data. */
590 SET_HARD_REG_SET (linkregs);
591 pseq->link_reg = NULL_RTX;
592 pseq->abstracted_length = 0;
594 pseq->gain = -(seq_call_cost - seq_jump_cost + seq_return_cost);
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. */
600 for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
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;
609 if (mseq->abstracted_length > mseq->matching_length)
610 mseq->abstracted_length = mseq->matching_length;
612 /* Compute the cost of sequence. */
613 RECOMPUTE_COST (mseq);
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)
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;
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)
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;
637 /* Compute the cost of pattern sequence. */
638 RECOMPUTE_COST (pseq);
640 /* No gain if COST is too small. */
641 if (pseq->cost <= seq_call_cost)
643 pseq->gain = -1;
644 return;
647 /* Ensure that no matching sequence is longer than the pattern sequence. */
648 for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
650 if (mseq->abstracted_length > pseq->abstracted_length)
652 mseq->abstracted_length = pseq->abstracted_length;
653 RECOMPUTE_COST (mseq);
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;
660 /* No need to do further work if there is no gain. */
661 if (pseq->gain <= 0)
662 return;
664 /* Should not use registers live in the pattern sequence as link register.
666 clear_regs_live_in_seq (&linkregs, pseq->insn, pseq->abstracted_length);
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++)
673 if (CALL_P (x))
675 hascall = 1;
676 break;
678 x = prev_insn_in_block (x);
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. */
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);
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))
705 pseq->link_reg = gen_rtx_REG (Pmode, i);
706 break;
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;
715 /* Deallocates memory occupied by PSEQ and its matching seqs. */
717 static void
718 free_pattern_seq (pattern_seq pseq)
720 while (pseq->matching_seqs)
722 matching_seq mseq = pseq->matching_seqs;
723 pseq->matching_seqs = mseq->next_matching_seq;
724 free (mseq);
726 free (pseq);
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. */
734 static void
735 recompute_gain (void)
737 pattern_seq *pseq;
738 int maxgain;
740 maxgain = 0;
741 for (pseq = &pattern_seqs; *pseq;)
743 if ((*pseq)->gain <= 0)
744 recompute_gain_for_pattern_seq (*pseq);
746 if ((*pseq)->gain > 0)
748 if ((*pseq)->gain > maxgain)
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;
756 else
758 pseq = &(*pseq)->next_pattern_seq;
761 else
763 pattern_seq temp = *pseq;
764 *pseq = temp->next_pattern_seq;
765 free_pattern_seq (temp);
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. */
774 static void
775 erase_from_pattern_seqs (rtx insn, int len)
777 pattern_seq *pseq;
778 matching_seq *mseq;
779 rtx x;
780 int plen, mlen;
781 int pcost, mcost;
783 while (len > 0)
785 for (pseq = &pattern_seqs; *pseq;)
787 plen = 0;
788 pcost = 0;
789 for (x = (*pseq)->insn; x && (x != insn);
790 x = prev_insn_in_block (x))
792 plen++;
793 pcost += compute_rtx_cost (x);
796 if (pcost <= seq_call_cost)
798 pattern_seq temp = *pseq;
799 *pseq = temp->next_pattern_seq;
800 free_pattern_seq (temp);
802 else
804 for (mseq = &(*pseq)->matching_seqs; *mseq;)
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))
813 mlen++;
814 mcost += compute_rtx_cost (x);
817 if (mcost <= seq_call_cost)
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;
825 else
827 if (mlen < (*mseq)->matching_length)
829 (*mseq)->cost = mcost;
830 (*mseq)->matching_length = mlen;
831 /* Set to 0 to force gain recomputation. */
832 (*pseq)->gain = 0;
834 mseq = &(*mseq)->next_matching_seq;
838 pseq = &(*pseq)->next_pattern_seq;
842 len--;
843 insn = prev_insn_in_block (insn);
847 /* Updates those pattern sequences and matching sequences, which overlap with
848 the pattern sequence with the biggest gain and its matching sequences. */
850 static void
851 update_pattern_seqs (void)
853 pattern_seq bestpseq;
854 matching_seq mseq;
856 bestpseq = pattern_seqs;
857 pattern_seqs = bestpseq->next_pattern_seq;
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);
864 bestpseq->next_pattern_seq = pattern_seqs;
865 pattern_seqs = bestpseq;
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. */
872 static void
873 determine_seq_blocks (void)
875 seq_block sb;
876 matching_seq *mseq;
877 matching_seq m;
879 /* Initialize SEQ_BLOCKS to empty. */
880 seq_blocks = 0;
882 /* Process all matching sequences. */
883 for (mseq = &pattern_seqs->matching_seqs; *mseq;)
885 /* Deal only with matching sequences being long enough. */
886 if ((*mseq)->cost <= seq_call_cost)
888 mseq = &(*mseq)->next_matching_seq;
889 continue;
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))
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;
903 else
905 for (sb = seq_blocks; sb; sb = sb->next_seq_block)
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))
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;
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;
933 /* Builds a symbol_ref for LABEL. */
935 static rtx
936 gen_symbol_ref_rtx_for_label (rtx label)
938 char name[20];
939 rtx sym;
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;
947 /* Ensures that INSN is the last insn in its block and returns the block label
948 of the next block. */
950 static rtx
951 block_label_after (rtx insn)
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);
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. */
965 static void
966 split_blocks_after_seqs (void)
968 seq_block sb;
969 matching_seq mseq;
971 block_label_after (pattern_seqs->insn);
972 for (sb = seq_blocks; sb; sb = sb->next_seq_block)
974 for (mseq = sb->matching_seqs; mseq; mseq = mseq->next_matching_seq)
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);
984 /* Splits the best pattern sequence according to SEQ_BLOCKS. Emits pseudo-call
985 and -return insns before and after the sequence. */
987 static void
988 split_pattern_seq (void)
990 rtx insn;
991 basic_block bb;
992 rtx retlabel, retjmp, saveinsn;
993 int i;
994 seq_block sb;
996 insn = pattern_seqs->insn;
997 bb = BLOCK_FOR_INSN (insn);
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;
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));
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);
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)
1021 for (; i < sb->length; i++)
1022 insn = prev_insn_in_block (insn);
1024 sb->label = block_label (split_block (bb, insn)->dest);
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));
1037 /* Deletes the insns of the matching sequences of the best pattern sequence and
1038 replaces them with pseudo-calls to the pattern sequence. */
1040 static void
1041 erase_matching_seqs (void)
1043 seq_block sb;
1044 matching_seq mseq;
1045 rtx insn;
1046 basic_block bb;
1047 rtx retlabel, saveinsn, callinsn;
1048 int i;
1050 for (sb = seq_blocks; sb; sb = sb->next_seq_block)
1052 for (mseq = sb->matching_seqs; mseq; mseq = mseq->next_matching_seq)
1054 insn = mseq->insn;
1055 bb = BLOCK_FOR_INSN (insn);
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;
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);
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;
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;
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);
1092 make_edge (BLOCK_FOR_INSN (seq_blocks->label),
1093 BLOCK_FOR_INSN (retlabel), EDGE_ABNORMAL);
1098 /* Deallocates SEQ_BLOCKS and all the matching sequences. */
1100 static void
1101 free_seq_blocks (void)
1103 while (seq_blocks)
1105 seq_block sb = seq_blocks;
1106 while (sb->matching_seqs)
1108 matching_seq mseq = sb->matching_seqs;
1109 sb->matching_seqs = mseq->next_matching_seq;
1110 free (mseq);
1112 seq_blocks = sb->next_seq_block;
1113 free (sb);
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. */
1121 static void
1122 abstract_best_seq (void)
1124 pattern_seq bestpseq;
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 ();
1133 /* Record the usage of the link register. */
1134 regs_ever_live[REGNO (pattern_seqs->link_reg)] = 1;
1136 /* Remove the best pattern sequence. */
1137 bestpseq = pattern_seqs;
1138 pattern_seqs = bestpseq->next_pattern_seq;
1139 free_pattern_seq (bestpseq);
1142 /* Prints info on the pattern sequences to the dump file. */
1144 static void
1145 dump_pattern_seqs (void)
1147 pattern_seq pseq;
1148 matching_seq mseq;
1150 if (!dump_file)
1151 return;
1153 fprintf (dump_file, ";; Pattern sequences\n");
1154 for (pseq = pattern_seqs; pseq; pseq = pseq->next_pattern_seq)
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)
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, ",");
1165 fprintf (dump_file, ".\n");
1167 fprintf (dump_file, "\n");
1170 /* Prints info on the best pattern sequence transformed in the ITER-th
1171 iteration to the dump file. */
1173 static void
1174 dump_best_pattern_seq (int iter)
1176 matching_seq mseq;
1178 if (!dump_file)
1179 return;
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)
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, ",");
1195 fprintf (dump_file, ".\n");
1196 fprintf (dump_file, "Using reg %d as link register.\n\n",
1197 REGNO (pattern_seqs->link_reg));
1200 /* Htab hash function for hash_bucket_def structure. */
1202 static unsigned int
1203 htab_hash_bucket (const void *p)
1205 p_hash_bucket bucket = (p_hash_bucket) p;
1206 return bucket->hash;
1209 /* Htab equal function for hash_bucket_def structure. */
1211 static int
1212 htab_eq_bucket (const void *p0, const void *p1)
1214 return htab_hash_bucket (p0) == htab_hash_bucket (p1);
1217 /* Htab delete function for hash_bucket_def structure. */
1219 static void
1220 htab_del_bucket (void *p)
1222 p_hash_bucket bucket = (p_hash_bucket) p;
1224 if (bucket->seq_candidates)
1225 htab_delete (bucket->seq_candidates);
1227 free (bucket);
1230 /* Htab hash function for hash_bucket_def structure. */
1232 static unsigned int
1233 htab_hash_elem (const void *p)
1235 p_hash_elem elem = (p_hash_elem) p;
1236 return htab_hash_pointer (elem->insn);
1239 /* Htab equal function for hash_bucket_def structure. */
1241 static int
1242 htab_eq_elem (const void *p0, const void *p1)
1244 return htab_hash_elem (p0) == htab_hash_elem (p1);
1247 /* Htab delete function for hash_bucket_def structure. */
1249 static void
1250 htab_del_elem (void *p)
1252 p_hash_elem elem = (p_hash_elem) p;
1253 free (elem);
1256 /* Creates a hash value for each sequence candidate and saves them
1257 in HASH_BUCKET. */
1259 static void
1260 fill_hash_bucket (void)
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;
1270 insn_idx = 0;
1271 FOR_EACH_BB (bb)
1273 FOR_BB_INSNS_REVERSE (bb, insn)
1275 if (!ABSTRACTABLE_INSN_P (insn))
1276 continue;
1278 /* Compute hash value for INSN. */
1279 tmp_bucket.hash = compute_hash (insn);
1281 /* Select the hash group. */
1282 bucket = htab_find (hash_buckets, &tmp_bucket);
1284 if (!bucket)
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;
1292 slot = htab_find_slot (hash_buckets, &tmp_bucket, INSERT);
1293 *slot = bucket;
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);
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);
1308 /* Insert INSN into BUCKET hash bucket. */
1309 slot = htab_find_slot (bucket->seq_candidates, elem, INSERT);
1310 *slot = elem;
1312 insn_idx++;
1317 /* Computes the cost of calling sequence and the cost of return. */
1319 static void
1320 compute_init_costs (void)
1322 rtx rtx_jump, rtx_store, rtx_return, reg, label;
1323 basic_block bb;
1325 FOR_EACH_BB (bb)
1326 if (BB_HEAD (bb))
1327 break;
1329 label = block_label (bb);
1330 reg = gen_rtx_REG (Pmode, 0);
1332 /* Pattern for indirect jump. */
1333 rtx_jump = gen_indirect_jump (reg);
1335 /* Pattern for storing address. */
1336 rtx_store = gen_rtx_SET (VOIDmode, reg, gen_symbol_ref_rtx_for_label (label));
1338 /* Pattern for return insn. */
1339 rtx_return = gen_jump (label);
1341 /* The cost of jump. */
1342 seq_jump_cost = compute_rtx_cost (make_jump_insn_raw (rtx_jump));
1344 /* The cost of calling sequence. */
1345 seq_call_cost = seq_jump_cost + compute_rtx_cost (make_insn_raw (rtx_store));
1347 /* The cost of return. */
1348 seq_return_cost = compute_rtx_cost (make_jump_insn_raw (rtx_return));
1350 /* Simple heuristic for minimal sequence cost. */
1351 seq_call_cost = (int)(seq_call_cost * (double)SEQ_CALL_COST_MULTIPLIER);
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. */
1358 static void
1359 rtl_seqabstr (void)
1361 int iter;
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 ();
1368 /* Compute the common cost of abstraction. */
1369 compute_init_costs ();
1371 /* Build an initial set of pattern sequences from the current function. */
1372 collect_pattern_seqs ();
1373 dump_pattern_seqs ();
1375 /* Iterate until there are no sequences to abstract. */
1376 for (iter = 1;; iter++)
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 ();
1391 /* Cleanup hash tables. */
1392 htab_delete (hash_buckets);
1394 if (iter > 1)
1396 /* Update notes. */
1397 count_or_remove_death_notes (NULL, 1);
1399 life_analysis (PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
1400 | PROP_KILL_DEAD_CODE);
1402 /* Extra cleanup. */
1403 cleanup_cfg (CLEANUP_EXPENSIVE |
1404 CLEANUP_UPDATE_LIFE |
1405 (flag_crossjumping ? CLEANUP_CROSSJUMP : 0));
1409 /* The gate function for TREE_OPT_PASS. */
1411 static bool
1412 gate_rtl_seqabstr (void)
1414 return flag_rtl_seqabstr;
1417 /* The entry point of the sequence abstraction algorithm. */
1419 static unsigned int
1420 rest_of_rtl_seqabstr (void)
1422 life_analysis (PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE | PROP_KILL_DEAD_CODE);
1424 cleanup_cfg (CLEANUP_EXPENSIVE |
1425 CLEANUP_UPDATE_LIFE |
1426 (flag_crossjumping ? CLEANUP_CROSSJUMP : 0));
1428 /* Abstract out common insn sequences. */
1429 rtl_seqabstr ();
1430 return 0;
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 */