Daily bump.
[official-gcc.git] / gcc / rtl-factoring.c
blob77c2197b41d70f6702d63e811d7a330fbd12da25
1 /* RTL factoring (sequence abstraction).
2 Copyright (C) 2004, 2005, 2006, 2007, 2008 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 3, 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 COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "rtl.h"
25 #include "obstack.h"
26 #include "basic-block.h"
27 #include "resource.h"
28 #include "flags.h"
29 #include "ggc.h"
30 #include "regs.h"
31 #include "params.h"
32 #include "expr.h"
33 #include "tm_p.h"
34 #include "tree-pass.h"
35 #include "tree-flow.h"
36 #include "timevar.h"
37 #include "output.h"
38 #include "df.h"
39 #include "addresses.h"
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;
240 typedef const struct hash_bucket_def *const_p_hash_bucket;
242 /* Contains the last insn of the sequence, and its index value. */
243 typedef struct hash_elem_def
245 /* Unique index; ordered by FILL_HASH_BUCKET. */
246 unsigned long idx;
248 /* The last insn in the sequence. */
249 rtx insn;
251 /* The cached length of the insn. */
252 int length;
253 } *p_hash_elem;
254 typedef const struct hash_elem_def *const_p_hash_elem;
256 /* The list of same sequence candidates. */
257 static htab_t hash_buckets;
259 /* The pattern sequences collected from the current functions. */
260 static pattern_seq pattern_seqs;
262 /* The blocks of the current pattern sequence. */
263 static seq_block seq_blocks;
265 /* Cost of calling sequence. */
266 static int seq_call_cost;
268 /* Cost of jump. */
269 static int seq_jump_cost;
271 /* Cost of returning. */
272 static int seq_return_cost;
274 /* Returns the first insn preceding INSN for which INSN_P is true and belongs to
275 the same basic block. Returns NULL_RTX if no such insn can be found. */
277 static rtx
278 prev_insn_in_block (rtx insn)
280 basic_block bb = BLOCK_FOR_INSN (insn);
282 if (!bb)
283 return NULL_RTX;
285 while (insn != BB_HEAD (bb))
287 insn = PREV_INSN (insn);
288 if (INSN_P (insn))
289 return insn;
291 return NULL_RTX;
294 /* Returns the hash value of INSN. */
296 static unsigned int
297 compute_hash (rtx insn)
299 unsigned int hash = 0;
300 rtx prev;
302 hash = INSN_CODE (insn) * 100;
304 prev = prev_insn_in_block (insn);
305 if (prev)
306 hash += INSN_CODE (prev);
308 return hash;
311 /* Compute the cost of INSN rtx for abstraction. */
313 static int
314 compute_rtx_cost (rtx insn)
316 struct hash_bucket_def tmp_bucket;
317 p_hash_bucket bucket;
318 struct hash_elem_def tmp_elem;
319 p_hash_elem elem = NULL;
320 int cost = -1;
322 /* Compute hash value for INSN. */
323 tmp_bucket.hash = compute_hash (insn);
325 /* Select the hash group. */
326 bucket = htab_find (hash_buckets, &tmp_bucket);
328 if (bucket)
330 tmp_elem.insn = insn;
332 /* Select the insn. */
333 elem = htab_find (bucket->seq_candidates, &tmp_elem);
335 /* If INSN is parsed the cost will be the cached length. */
336 if (elem)
337 cost = elem->length;
340 /* If we can't parse the INSN cost will be the instruction length. */
341 if (cost == -1)
343 cost = get_attr_length (insn);
345 /* Cache the length. */
346 if (elem)
347 elem->length = cost;
350 /* If we can't get an accurate estimate for a complex instruction,
351 assume that it has the same cost as a single fast instruction. */
352 return cost != 0 ? cost : COSTS_N_INSNS (1);
355 /* Determines the number of common insns in the sequences ending in INSN1 and
356 INSN2. Returns with LEN number of common insns and COST cost of sequence.
359 static void
360 matching_length (rtx insn1, rtx insn2, int* len, int* cost)
362 rtx x1;
363 rtx x2;
365 x1 = insn1;
366 x2 = insn2;
367 *len = 0;
368 *cost = 0;
369 while (x1 && x2 && (x1 != insn2) && (x2 != insn1)
370 && rtx_equal_p (PATTERN (x1), PATTERN (x2)))
372 (*len)++;
373 (*cost) += compute_rtx_cost (x1);
374 x1 = prev_insn_in_block (x1);
375 x2 = prev_insn_in_block (x2);
379 /* Adds E0 as a pattern sequence to PATTERN_SEQS with E1 as a matching
380 sequence. */
382 static void
383 match_seqs (p_hash_elem e0, p_hash_elem e1)
385 int len;
386 int cost;
387 matching_seq mseq, p_prev, p_next;
389 /* Determines the cost of the sequence and return without doing anything
390 if it is too small to produce any gain. */
391 matching_length (e0->insn, e1->insn, &len, &cost);
392 if (cost <= seq_call_cost)
393 return;
395 /* Prepend a new PATTERN_SEQ to PATTERN_SEQS if the last pattern sequence
396 does not end in E0->INSN. This assumes that once the E0->INSN changes
397 the old value will never appear again. */
398 if (!pattern_seqs || pattern_seqs->insn != e0->insn)
400 pattern_seq pseq =
401 (pattern_seq) xmalloc (sizeof (struct pattern_seq_def));
402 pseq->insn = e0->insn;
403 pseq->idx = e0->idx;
404 pseq->gain = 0; /* Set to zero to force recomputing. */
405 pseq->abstracted_length = 0;
406 pseq->cost = 0;
407 pseq->link_reg = NULL_RTX;
408 pseq->matching_seqs = NULL;
409 pseq->next_pattern_seq = pattern_seqs;
410 pattern_seqs = pseq;
413 /* Find the position of E1 in the matching sequences list. */
414 p_prev = NULL;
415 p_next = pattern_seqs->matching_seqs;
416 while (p_next && p_next->idx < e1->idx)
418 p_prev = p_next;
419 p_next = p_next->next_matching_seq;
422 /* Add a new E1 matching sequence to the pattern sequence. We know that
423 it ends in E0->INSN. */
424 mseq = (matching_seq) xmalloc (sizeof (struct matching_seq_def));
425 mseq->insn = e1->insn;
426 mseq->idx = e1->idx;
427 mseq->matching_length = len;
428 mseq->abstracted_length = 0;
429 mseq->cost = cost;
431 if (p_prev == NULL)
432 pattern_seqs->matching_seqs = mseq;
433 else
434 p_prev->next_matching_seq = mseq;
435 mseq->next_matching_seq = p_next;
438 /* Collects all pattern sequences and their matching sequences and puts them
439 into PATTERN_SEQS. */
441 static void
442 collect_pattern_seqs (void)
444 htab_iterator hti0, hti1, hti2;
445 p_hash_bucket hash_bucket;
446 p_hash_elem e0, e1;
447 #ifdef STACK_REGS
448 basic_block bb;
449 bitmap_head stack_reg_live;
451 /* Extra initialization step to ensure that no stack registers (if present)
452 are live across abnormal edges. Set a flag in STACK_REG_LIVE for an insn
453 if a stack register is live after the insn. */
454 bitmap_initialize (&stack_reg_live, NULL);
456 FOR_EACH_BB (bb)
458 regset_head live;
459 rtx insn;
460 rtx prev;
462 /* Initialize liveness propagation. */
463 INIT_REG_SET (&live);
464 bitmap_copy (&live, DF_LR_OUT (bb));
465 df_simulate_artificial_refs_at_end (bb, &live);
467 /* Propagate liveness info and mark insns where a stack reg is live. */
468 insn = BB_END (bb);
469 for (insn = BB_END (bb); ; insn = prev)
471 prev = PREV_INSN (insn);
472 if (INSN_P (insn))
474 int reg;
475 for (reg = FIRST_STACK_REG; reg <= LAST_STACK_REG; reg++)
477 if (REGNO_REG_SET_P (&live, reg))
479 bitmap_set_bit (&stack_reg_live, INSN_UID (insn));
480 break;
485 if (insn == BB_HEAD (bb))
486 break;
487 df_simulate_one_insn_backwards (bb, insn, &live);
488 insn = prev;
491 /* Free unused data. */
492 CLEAR_REG_SET (&live);
494 #endif
496 /* Initialize PATTERN_SEQS to empty. */
497 pattern_seqs = 0;
499 /* Try to match every abstractable insn with every other insn in the same
500 HASH_BUCKET. */
502 FOR_EACH_HTAB_ELEMENT (hash_buckets, hash_bucket, p_hash_bucket, hti0)
503 if (htab_elements (hash_bucket->seq_candidates) > 1)
504 FOR_EACH_HTAB_ELEMENT (hash_bucket->seq_candidates, e0, p_hash_elem, hti1)
505 FOR_EACH_HTAB_ELEMENT (hash_bucket->seq_candidates, e1, p_hash_elem,
506 hti2)
507 if (e0 != e1
508 #ifdef STACK_REGS
509 && !bitmap_bit_p (&stack_reg_live, INSN_UID (e0->insn))
510 && !bitmap_bit_p (&stack_reg_live, INSN_UID (e1->insn))
511 #endif
513 match_seqs (e0, e1);
514 #ifdef STACK_REGS
515 /* Free unused data. */
516 bitmap_clear (&stack_reg_live);
517 #endif
520 /* Transforms a regset to a HARD_REG_SET. Every hard register in REGS is added
521 to hregs. Additionally, the hard counterpart of every renumbered pseudo
522 register is also added. */
524 static void
525 renumbered_reg_set_to_hard_reg_set (HARD_REG_SET * hregs, regset regs)
527 int r;
529 REG_SET_TO_HARD_REG_SET (*hregs, regs);
530 for (r = FIRST_PSEUDO_REGISTER; r < max_regno; r++)
531 if (REGNO_REG_SET_P (regs, r) && reg_renumber[r] >= 0)
532 SET_HARD_REG_BIT (*hregs, reg_renumber[r]);
535 /* Clears the bits in REGS for all registers, which are live in the sequence
536 give by its last INSN and its LENGTH. */
538 static void
539 clear_regs_live_in_seq (HARD_REG_SET * regs, rtx insn, int length)
541 basic_block bb;
542 regset_head live;
543 HARD_REG_SET hlive;
544 rtx x;
545 int i;
547 /* Initialize liveness propagation. */
548 bb = BLOCK_FOR_INSN (insn);
549 INIT_REG_SET (&live);
550 bitmap_copy (&live, DF_LR_OUT (bb));
551 df_simulate_artificial_refs_at_end (bb, &live);
553 /* Propagate until INSN if found. */
554 for (x = BB_END (bb); x != insn; x = PREV_INSN (x))
555 df_simulate_one_insn_backwards (bb, x, &live);
557 /* Clear registers live after INSN. */
558 renumbered_reg_set_to_hard_reg_set (&hlive, &live);
559 AND_COMPL_HARD_REG_SET (*regs, hlive);
561 /* Clear registers live in and before the sequence. */
562 for (i = 0; i < length;)
564 rtx prev = PREV_INSN (x);
565 df_simulate_one_insn_backwards (bb, x, &live);
567 if (INSN_P (x))
569 renumbered_reg_set_to_hard_reg_set (&hlive, &live);
570 AND_COMPL_HARD_REG_SET (*regs, hlive);
571 i++;
574 x = prev;
577 /* Free unused data. */
578 CLEAR_REG_SET (&live);
581 /* Computes the gain of turning PSEQ into a pseudo-function and its matching
582 sequences into pseudo-calls. Also computes and caches the number of insns to
583 abstract from the matching sequences. */
585 static void
586 recompute_gain_for_pattern_seq (pattern_seq pseq)
588 matching_seq mseq;
589 rtx x;
590 int i;
591 int hascall;
592 HARD_REG_SET linkregs;
594 /* Initialize data. */
595 SET_HARD_REG_SET (linkregs);
596 pseq->link_reg = NULL_RTX;
597 pseq->abstracted_length = 0;
599 pseq->gain = -(seq_call_cost - seq_jump_cost + seq_return_cost);
601 /* Determine ABSTRACTED_LENGTH and COST for matching sequences of PSEQ.
602 ABSTRACTED_LENGTH may be less than MATCHING_LENGTH if sequences in the
603 same block overlap. */
605 for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
607 /* Determine ABSTRACTED_LENGTH. */
608 if (mseq->next_matching_seq)
609 mseq->abstracted_length = (int)(mseq->next_matching_seq->idx -
610 mseq->idx);
611 else
612 mseq->abstracted_length = mseq->matching_length;
614 if (mseq->abstracted_length > mseq->matching_length)
615 mseq->abstracted_length = mseq->matching_length;
617 /* Compute the cost of sequence. */
618 RECOMPUTE_COST (mseq);
620 /* If COST is big enough registers live in this matching sequence
621 should not be used as a link register. Also set ABSTRACTED_LENGTH
622 of PSEQ. */
623 if (mseq->cost > seq_call_cost)
625 clear_regs_live_in_seq (&linkregs, mseq->insn,
626 mseq->abstracted_length);
627 if (mseq->abstracted_length > pseq->abstracted_length)
628 pseq->abstracted_length = mseq->abstracted_length;
632 /* Modify ABSTRACTED_LENGTH of PSEQ if pattern sequence overlaps with one
633 of the matching sequences. */
634 for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
636 x = pseq->insn;
637 for (i = 0; (i < pseq->abstracted_length) && (x != mseq->insn); i++)
638 x = prev_insn_in_block (x);
639 pseq->abstracted_length = i;
642 /* Compute the cost of pattern sequence. */
643 RECOMPUTE_COST (pseq);
645 /* No gain if COST is too small. */
646 if (pseq->cost <= seq_call_cost)
648 pseq->gain = -1;
649 return;
652 /* Ensure that no matching sequence is longer than the pattern sequence. */
653 for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
655 if (mseq->abstracted_length > pseq->abstracted_length)
657 mseq->abstracted_length = pseq->abstracted_length;
658 RECOMPUTE_COST (mseq);
660 /* Once the length is stabilizing the gain can be calculated. */
661 if (mseq->cost > seq_call_cost)
662 pseq->gain += mseq->cost - seq_call_cost;
665 /* No need to do further work if there is no gain. */
666 if (pseq->gain <= 0)
667 return;
669 /* Should not use registers live in the pattern sequence as link register.
671 clear_regs_live_in_seq (&linkregs, pseq->insn, pseq->abstracted_length);
673 /* Determine whether pattern sequence contains a call_insn. */
674 hascall = 0;
675 x = pseq->insn;
676 for (i = 0; i < pseq->abstracted_length; i++)
678 if (CALL_P (x))
680 hascall = 1;
681 break;
683 x = prev_insn_in_block (x);
686 /* Should not use a register as a link register if - it is a fixed
687 register, or - the sequence contains a call insn and the register is a
688 call used register, or - the register needs to be saved if used in a
689 function but was not used before (since saving it can invalidate already
690 computed frame pointer offsets), or - the register cannot be used as a
691 base register. */
693 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
694 if (fixed_regs[i]
695 #ifdef REGNO_OK_FOR_INDIRECT_JUMP_P
696 || (!REGNO_OK_FOR_INDIRECT_JUMP_P (i, Pmode))
697 #else
698 || (!ok_for_base_p_1 (i, Pmode, MEM, SCRATCH))
699 || (!reg_class_subset_p (REGNO_REG_CLASS (i),
700 base_reg_class (VOIDmode, MEM, SCRATCH)))
701 #endif
702 || (hascall && call_used_regs[i])
703 || (!call_used_regs[i] && !df_regs_ever_live_p (i)))
704 CLEAR_HARD_REG_BIT (linkregs, i);
706 /* Find an appropriate register to be used as the link register. */
707 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
708 if (TEST_HARD_REG_BIT (linkregs, i))
710 pseq->link_reg = gen_rtx_REG (Pmode, i);
711 break;
714 /* Abstraction is not possible if no link register is available, so set
715 gain to 0. */
716 if (!pseq->link_reg)
717 pseq->gain = 0;
720 /* Deallocates memory occupied by PSEQ and its matching seqs. */
722 static void
723 free_pattern_seq (pattern_seq pseq)
725 while (pseq->matching_seqs)
727 matching_seq mseq = pseq->matching_seqs;
728 pseq->matching_seqs = mseq->next_matching_seq;
729 free (mseq);
731 free (pseq);
735 /* Computes the gain for pattern sequences. Pattern sequences producing no gain
736 are deleted. The pattern sequence with the biggest gain is moved to the first
737 place of PATTERN_SEQS. */
739 static void
740 recompute_gain (void)
742 pattern_seq *pseq;
743 int maxgain;
745 maxgain = 0;
746 for (pseq = &pattern_seqs; *pseq;)
748 if ((*pseq)->gain <= 0)
749 recompute_gain_for_pattern_seq (*pseq);
751 if ((*pseq)->gain > 0)
753 if ((*pseq)->gain > maxgain)
755 pattern_seq temp = *pseq;
756 (*pseq) = temp->next_pattern_seq;
757 temp->next_pattern_seq = pattern_seqs;
758 pattern_seqs = temp;
759 maxgain = pattern_seqs->gain;
761 else
763 pseq = &(*pseq)->next_pattern_seq;
766 else
768 pattern_seq temp = *pseq;
769 *pseq = temp->next_pattern_seq;
770 free_pattern_seq (temp);
775 /* Updated those pattern sequences and matching sequences, which overlap with
776 the sequence given by INSN and LEN. Deletes sequences shrinking below a
777 limit. */
779 static void
780 erase_from_pattern_seqs (rtx insn, int len)
782 pattern_seq *pseq;
783 matching_seq *mseq;
784 rtx x;
785 int plen, mlen;
786 int pcost, mcost;
788 while (len > 0)
790 for (pseq = &pattern_seqs; *pseq;)
792 plen = 0;
793 pcost = 0;
794 for (x = (*pseq)->insn; x && (x != insn);
795 x = prev_insn_in_block (x))
797 plen++;
798 pcost += compute_rtx_cost (x);
801 if (pcost <= seq_call_cost)
803 pattern_seq temp = *pseq;
804 *pseq = temp->next_pattern_seq;
805 free_pattern_seq (temp);
807 else
809 for (mseq = &(*pseq)->matching_seqs; *mseq;)
811 mlen = 0;
812 mcost = 0;
813 for (x = (*mseq)->insn;
814 x && (x != insn) && (mlen < plen)
815 && (mlen < (*mseq)->matching_length);
816 x = prev_insn_in_block (x))
818 mlen++;
819 mcost += compute_rtx_cost (x);
822 if (mcost <= seq_call_cost)
824 matching_seq temp = *mseq;
825 *mseq = temp->next_matching_seq;
826 free (temp);
827 /* Set to 0 to force gain recomputation. */
828 (*pseq)->gain = 0;
830 else
832 if (mlen < (*mseq)->matching_length)
834 (*mseq)->cost = mcost;
835 (*mseq)->matching_length = mlen;
836 /* Set to 0 to force gain recomputation. */
837 (*pseq)->gain = 0;
839 mseq = &(*mseq)->next_matching_seq;
843 pseq = &(*pseq)->next_pattern_seq;
847 len--;
848 insn = prev_insn_in_block (insn);
852 /* Updates those pattern sequences and matching sequences, which overlap with
853 the pattern sequence with the biggest gain and its matching sequences. */
855 static void
856 update_pattern_seqs (void)
858 pattern_seq bestpseq;
859 matching_seq mseq;
861 bestpseq = pattern_seqs;
862 pattern_seqs = bestpseq->next_pattern_seq;
864 for (mseq = bestpseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
865 if (mseq->cost > seq_call_cost)
866 erase_from_pattern_seqs (mseq->insn, mseq->abstracted_length);
867 erase_from_pattern_seqs (bestpseq->insn, bestpseq->abstracted_length);
869 bestpseq->next_pattern_seq = pattern_seqs;
870 pattern_seqs = bestpseq;
873 /* Groups together those matching sequences of the best pattern sequence, which
874 have the same ABSTRACTED_LENGTH and puts these groups in ascending order.
875 SEQ_BLOCKS contains the result. */
877 static void
878 determine_seq_blocks (void)
880 seq_block sb;
881 matching_seq *mseq;
882 matching_seq m;
884 /* Initialize SEQ_BLOCKS to empty. */
885 seq_blocks = 0;
887 /* Process all matching sequences. */
888 for (mseq = &pattern_seqs->matching_seqs; *mseq;)
890 /* Deal only with matching sequences being long enough. */
891 if ((*mseq)->cost <= seq_call_cost)
893 mseq = &(*mseq)->next_matching_seq;
894 continue;
897 /* Ensure that SB contains a seq_block with the appropriate length.
898 Insert a new seq_block if necessary. */
899 if (!seq_blocks || ((*mseq)->abstracted_length < seq_blocks->length))
901 sb = (seq_block) xmalloc (sizeof (struct seq_block_def));
902 sb->length = (*mseq)->abstracted_length;
903 sb->label = NULL_RTX;
904 sb->matching_seqs = 0;
905 sb->next_seq_block = seq_blocks;
906 seq_blocks = sb;
908 else
910 for (sb = seq_blocks; sb; sb = sb->next_seq_block)
912 if ((*mseq)->abstracted_length == sb->length)
913 break;
914 if (!sb->next_seq_block
915 || ((*mseq)->abstracted_length <
916 sb->next_seq_block->length))
918 seq_block temp =
919 (seq_block) xmalloc (sizeof (struct seq_block_def));
920 temp->length = (*mseq)->abstracted_length;
921 temp->label = NULL_RTX;
922 temp->matching_seqs = 0;
923 temp->next_seq_block = sb->next_seq_block;
924 sb->next_seq_block = temp;
929 /* Remove the matching sequence from the linked list of the pattern
930 sequence and link it to SB. */
931 m = *mseq;
932 *mseq = m->next_matching_seq;
933 m->next_matching_seq = sb->matching_seqs;
934 sb->matching_seqs = m;
938 /* Builds a symbol_ref for LABEL. */
940 static rtx
941 gen_symbol_ref_rtx_for_label (const_rtx label)
943 char name[20];
944 rtx sym;
946 ASM_GENERATE_INTERNAL_LABEL (name, "L", CODE_LABEL_NUMBER (label));
947 sym = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (name));
948 SYMBOL_REF_FLAGS (sym) = SYMBOL_FLAG_LOCAL;
949 return sym;
952 /* Splits basic block at the requested insn and rebuilds dataflow. */
954 static basic_block
955 split_block_and_df_analyze (basic_block bb, rtx insn)
957 basic_block next;
958 next = split_block (bb, insn)->dest;
959 df_analyze ();
960 return next;
963 /* Ensures that INSN is the last insn in its block and returns the block label
964 of the next block. */
966 static rtx
967 block_label_after (rtx insn)
969 basic_block bb = BLOCK_FOR_INSN (insn);
970 if ((insn == BB_END (bb)) && (bb->next_bb != EXIT_BLOCK_PTR))
971 return block_label (bb->next_bb);
972 else
973 return block_label (split_block_and_df_analyze (bb, insn));
976 /* Ensures that the last insns of the best pattern and its matching sequences
977 are the last insns in their block. Additionally, extends the live set at the
978 end of the pattern sequence with the live sets at the end of the matching
979 sequences. */
981 static void
982 split_blocks_after_seqs (void)
984 seq_block sb;
985 matching_seq mseq;
987 block_label_after (pattern_seqs->insn);
988 for (sb = seq_blocks; sb; sb = sb->next_seq_block)
990 for (mseq = sb->matching_seqs; mseq; mseq = mseq->next_matching_seq)
992 block_label_after (mseq->insn);
993 IOR_REG_SET (df_get_live_out (BLOCK_FOR_INSN (pattern_seqs->insn)),
994 df_get_live_out (BLOCK_FOR_INSN (mseq->insn)));
999 /* Splits the best pattern sequence according to SEQ_BLOCKS. Emits pseudo-call
1000 and -return insns before and after the sequence. */
1002 static void
1003 split_pattern_seq (void)
1005 rtx insn;
1006 basic_block bb;
1007 rtx retlabel, retjmp, saveinsn;
1008 int i;
1009 seq_block sb;
1011 insn = pattern_seqs->insn;
1012 bb = BLOCK_FOR_INSN (insn);
1014 /* Get the label after the sequence. This will be the return address. The
1015 label will be referenced using a symbol_ref so protect it from
1016 deleting. */
1017 retlabel = block_label_after (insn);
1018 LABEL_PRESERVE_P (retlabel) = 1;
1020 /* Emit an indirect jump via the link register after the sequence acting
1021 as the return insn. Also emit a barrier and update the basic block. */
1022 if (!find_reg_note (BB_END (bb), REG_NORETURN, NULL))
1023 retjmp = emit_jump_insn_after (gen_indirect_jump (pattern_seqs->link_reg),
1024 BB_END (bb));
1025 emit_barrier_after (BB_END (bb));
1027 /* Replace all outgoing edges with a new one to the block of RETLABEL. */
1028 while (EDGE_COUNT (bb->succs) != 0)
1029 remove_edge (EDGE_SUCC (bb, 0));
1030 make_edge (bb, BLOCK_FOR_INSN (retlabel), EDGE_ABNORMAL);
1032 /* Split the sequence according to SEQ_BLOCKS and cache the label of the
1033 resulting basic blocks. */
1034 i = 0;
1035 for (sb = seq_blocks; sb; sb = sb->next_seq_block)
1037 for (; i < sb->length; i++)
1038 insn = prev_insn_in_block (insn);
1040 sb->label = block_label (split_block_and_df_analyze (bb, insn));
1043 /* Emit an insn saving the return address to the link register before the
1044 sequence. */
1045 saveinsn = emit_insn_after (gen_move_insn (pattern_seqs->link_reg,
1046 gen_symbol_ref_rtx_for_label
1047 (retlabel)), BB_END (bb));
1048 /* Update liveness info. */
1049 SET_REGNO_REG_SET (df_get_live_out (bb),
1050 REGNO (pattern_seqs->link_reg));
1053 /* Deletes the insns of the matching sequences of the best pattern sequence and
1054 replaces them with pseudo-calls to the pattern sequence. */
1056 static void
1057 erase_matching_seqs (void)
1059 seq_block sb;
1060 matching_seq mseq;
1061 rtx insn;
1062 basic_block bb;
1063 rtx retlabel, saveinsn, callinsn;
1064 int i;
1066 for (sb = seq_blocks; sb; sb = sb->next_seq_block)
1068 for (mseq = sb->matching_seqs; mseq; mseq = mseq->next_matching_seq)
1070 insn = mseq->insn;
1071 bb = BLOCK_FOR_INSN (insn);
1073 /* Get the label after the sequence. This will be the return
1074 address. The label will be referenced using a symbol_ref so
1075 protect it from deleting. */
1076 retlabel = block_label_after (insn);
1077 LABEL_PRESERVE_P (retlabel) = 1;
1079 /* Delete the insns of the sequence. */
1080 for (i = 0; i < sb->length; i++)
1081 insn = prev_insn_in_block (insn);
1082 delete_basic_block (split_block_and_df_analyze (bb, insn));
1084 /* Emit an insn saving the return address to the link register
1085 before the deleted sequence. */
1086 saveinsn = emit_insn_after (gen_move_insn (pattern_seqs->link_reg,
1087 gen_symbol_ref_rtx_for_label
1088 (retlabel)),
1089 BB_END (bb));
1090 BLOCK_FOR_INSN (saveinsn) = bb;
1092 /* Emit a jump to the appropriate part of the pattern sequence
1093 after the save insn. Also update the basic block. */
1094 callinsn = emit_jump_insn_after (gen_jump (sb->label), saveinsn);
1095 JUMP_LABEL (callinsn) = sb->label;
1096 LABEL_NUSES (sb->label)++;
1097 BLOCK_FOR_INSN (callinsn) = bb;
1098 BB_END (bb) = callinsn;
1100 /* Maintain control flow and liveness information. */
1101 SET_REGNO_REG_SET (df_get_live_out (bb),
1102 REGNO (pattern_seqs->link_reg));
1103 emit_barrier_after (BB_END (bb));
1104 make_single_succ_edge (bb, BLOCK_FOR_INSN (sb->label), 0);
1105 IOR_REG_SET (df_get_live_out (bb),
1106 df_get_live_in (BLOCK_FOR_INSN (sb->label)));
1108 make_edge (BLOCK_FOR_INSN (seq_blocks->label),
1109 BLOCK_FOR_INSN (retlabel), EDGE_ABNORMAL);
1114 /* Deallocates SEQ_BLOCKS and all the matching sequences. */
1116 static void
1117 free_seq_blocks (void)
1119 while (seq_blocks)
1121 seq_block sb = seq_blocks;
1122 while (sb->matching_seqs)
1124 matching_seq mseq = sb->matching_seqs;
1125 sb->matching_seqs = mseq->next_matching_seq;
1126 free (mseq);
1128 seq_blocks = sb->next_seq_block;
1129 free (sb);
1133 /* Transforms the best pattern sequence into a pseudo-function and its matching
1134 sequences to pseudo-calls. Afterwards the best pattern sequence is removed
1135 from PATTERN_SEQS. */
1137 static void
1138 abstract_best_seq (void)
1140 pattern_seq bestpseq;
1142 /* Do the abstraction. */
1143 determine_seq_blocks ();
1144 split_blocks_after_seqs ();
1145 split_pattern_seq ();
1146 erase_matching_seqs ();
1147 free_seq_blocks ();
1149 /* Record the usage of the link register. */
1150 df_set_regs_ever_live (REGNO (pattern_seqs->link_reg), true);
1152 /* Remove the best pattern sequence. */
1153 bestpseq = pattern_seqs;
1154 pattern_seqs = bestpseq->next_pattern_seq;
1155 free_pattern_seq (bestpseq);
1158 /* Prints info on the pattern sequences to the dump file. */
1160 static void
1161 dump_pattern_seqs (void)
1163 pattern_seq pseq;
1164 matching_seq mseq;
1166 if (!dump_file)
1167 return;
1169 fprintf (dump_file, ";; Pattern sequences\n");
1170 for (pseq = pattern_seqs; pseq; pseq = pseq->next_pattern_seq)
1172 fprintf (dump_file, "Pattern sequence at insn %d matches sequences at",
1173 INSN_UID (pseq->insn));
1174 for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
1176 fprintf (dump_file, " insn %d (length %d)", INSN_UID (mseq->insn),
1177 mseq->matching_length);
1178 if (mseq->next_matching_seq)
1179 fprintf (dump_file, ",");
1181 fprintf (dump_file, ".\n");
1183 fprintf (dump_file, "\n");
1186 /* Prints info on the best pattern sequence transformed in the ITER-th
1187 iteration to the dump file. */
1189 static void
1190 dump_best_pattern_seq (int iter)
1192 matching_seq mseq;
1194 if (!dump_file)
1195 return;
1197 fprintf (dump_file, ";; Iteration %d\n", iter);
1198 fprintf (dump_file,
1199 "Best pattern sequence with %d gain is at insn %d (length %d).\n",
1200 pattern_seqs->gain, INSN_UID (pattern_seqs->insn),
1201 pattern_seqs->abstracted_length);
1202 fprintf (dump_file, "Matching sequences are at");
1203 for (mseq = pattern_seqs->matching_seqs; mseq;
1204 mseq = mseq->next_matching_seq)
1206 fprintf (dump_file, " insn %d (length %d)", INSN_UID (mseq->insn),
1207 mseq->abstracted_length);
1208 if (mseq->next_matching_seq)
1209 fprintf (dump_file, ",");
1211 fprintf (dump_file, ".\n");
1212 fprintf (dump_file, "Using reg %d as link register.\n\n",
1213 REGNO (pattern_seqs->link_reg));
1216 /* Htab hash function for hash_bucket_def structure. */
1218 static unsigned int
1219 htab_hash_bucket (const void *p)
1221 const_p_hash_bucket bucket = (const_p_hash_bucket) p;
1222 return bucket->hash;
1225 /* Htab equal function for hash_bucket_def structure. */
1227 static int
1228 htab_eq_bucket (const void *p0, const void *p1)
1230 return htab_hash_bucket (p0) == htab_hash_bucket (p1);
1233 /* Htab delete function for hash_bucket_def structure. */
1235 static void
1236 htab_del_bucket (void *p)
1238 p_hash_bucket bucket = (p_hash_bucket) p;
1240 if (bucket->seq_candidates)
1241 htab_delete (bucket->seq_candidates);
1243 free (bucket);
1246 /* Htab hash function for hash_bucket_def structure. */
1248 static unsigned int
1249 htab_hash_elem (const void *p)
1251 const_p_hash_elem elem = (const_p_hash_elem) p;
1252 return htab_hash_pointer (elem->insn);
1255 /* Htab equal function for hash_bucket_def structure. */
1257 static int
1258 htab_eq_elem (const void *p0, const void *p1)
1260 return htab_hash_elem (p0) == htab_hash_elem (p1);
1263 /* Htab delete function for hash_bucket_def structure. */
1265 static void
1266 htab_del_elem (void *p)
1268 p_hash_elem elem = (p_hash_elem) p;
1269 free (elem);
1272 /* Creates a hash value for each sequence candidate and saves them
1273 in HASH_BUCKET. */
1275 static void
1276 fill_hash_bucket (void)
1278 basic_block bb;
1279 rtx insn;
1280 void **slot;
1281 p_hash_bucket bucket;
1282 struct hash_bucket_def tmp_bucket;
1283 p_hash_elem elem;
1284 unsigned long insn_idx;
1286 insn_idx = 0;
1287 FOR_EACH_BB (bb)
1289 FOR_BB_INSNS_REVERSE (bb, insn)
1291 if (!ABSTRACTABLE_INSN_P (insn))
1292 continue;
1294 /* Compute hash value for INSN. */
1295 tmp_bucket.hash = compute_hash (insn);
1297 /* Select the hash group. */
1298 bucket = htab_find (hash_buckets, &tmp_bucket);
1300 if (!bucket)
1302 /* Create a new hash group. */
1303 bucket = (p_hash_bucket) xcalloc (1,
1304 sizeof (struct hash_bucket_def));
1305 bucket->hash = tmp_bucket.hash;
1306 bucket->seq_candidates = NULL;
1308 slot = htab_find_slot (hash_buckets, &tmp_bucket, INSERT);
1309 *slot = bucket;
1312 /* Create new list for storing sequence candidates. */
1313 if (!bucket->seq_candidates)
1314 bucket->seq_candidates = htab_create (HASH_INIT,
1315 htab_hash_elem,
1316 htab_eq_elem,
1317 htab_del_elem);
1319 elem = (p_hash_elem) xcalloc (1, sizeof (struct hash_elem_def));
1320 elem->insn = insn;
1321 elem->idx = insn_idx;
1322 elem->length = get_attr_length (insn);
1324 /* Insert INSN into BUCKET hash bucket. */
1325 slot = htab_find_slot (bucket->seq_candidates, elem, INSERT);
1326 *slot = elem;
1328 insn_idx++;
1333 /* Computes the cost of calling sequence and the cost of return. */
1335 static void
1336 compute_init_costs (void)
1338 rtx rtx_jump, rtx_store, rtx_return, reg, label;
1339 basic_block bb;
1341 FOR_EACH_BB (bb)
1342 if (BB_HEAD (bb))
1343 break;
1345 label = block_label (bb);
1346 reg = gen_rtx_REG (Pmode, 0);
1348 /* Pattern for indirect jump. */
1349 rtx_jump = gen_indirect_jump (reg);
1351 /* Pattern for storing address. */
1352 rtx_store = gen_rtx_SET (VOIDmode, reg, gen_symbol_ref_rtx_for_label (label));
1354 /* Pattern for return insn. */
1355 rtx_return = gen_jump (label);
1357 /* The cost of jump. */
1358 seq_jump_cost = compute_rtx_cost (make_jump_insn_raw (rtx_jump));
1360 /* The cost of calling sequence. */
1361 seq_call_cost = seq_jump_cost + compute_rtx_cost (make_insn_raw (rtx_store));
1363 /* The cost of return. */
1364 seq_return_cost = compute_rtx_cost (make_jump_insn_raw (rtx_return));
1366 /* Simple heuristic for minimal sequence cost. */
1367 seq_call_cost = (int)(seq_call_cost * (double)SEQ_CALL_COST_MULTIPLIER);
1370 /* Finds equivalent insn sequences in the current function and retains only one
1371 instance of them which is turned into a pseudo-function. The additional
1372 copies are erased and replaced by pseudo-calls to the retained sequence. */
1374 static void
1375 rtl_seqabstr (void)
1377 int iter;
1378 df_set_flags (DF_LR_RUN_DCE);
1379 df_analyze ();
1381 /* Create a hash list for COLLECT_PATTERN_SEQS. */
1382 hash_buckets = htab_create (HASH_INIT, htab_hash_bucket , htab_eq_bucket ,
1383 htab_del_bucket);
1384 fill_hash_bucket ();
1386 /* Compute the common cost of abstraction. */
1387 compute_init_costs ();
1389 /* Build an initial set of pattern sequences from the current function. */
1390 collect_pattern_seqs ();
1391 dump_pattern_seqs ();
1393 /* Iterate until there are no sequences to abstract. */
1394 for (iter = 1;; iter++)
1396 /* Recompute gain for sequences if necessary and select sequence with
1397 biggest gain. */
1398 recompute_gain ();
1399 if (!pattern_seqs)
1400 break;
1401 dump_best_pattern_seq (iter);
1402 /* Update the cached info of the other sequences and force gain
1403 recomputation where needed. */
1404 update_pattern_seqs ();
1405 /* Turn best sequences into pseudo-functions and -calls. */
1406 abstract_best_seq ();
1409 /* Cleanup hash tables. */
1410 htab_delete (hash_buckets);
1413 /* The gate function for TREE_OPT_PASS. */
1415 static bool
1416 gate_rtl_seqabstr (void)
1418 return flag_rtl_seqabstr;
1421 /* The entry point of the sequence abstraction algorithm. */
1423 static unsigned int
1424 rest_of_rtl_seqabstr (void)
1426 /* Abstract out common insn sequences. */
1427 rtl_seqabstr ();
1428 return 0;
1431 struct rtl_opt_pass pass_rtl_seqabstr =
1434 RTL_PASS,
1435 "seqabstr", /* name */
1436 gate_rtl_seqabstr, /* gate */
1437 rest_of_rtl_seqabstr, /* execute */
1438 NULL, /* sub */
1439 NULL, /* next */
1440 0, /* static_pass_number */
1441 TV_SEQABSTR, /* tv_id */
1442 0, /* properties_required */
1443 0, /* properties_provided */
1444 0, /* properties_destroyed */
1445 0, /* todo_flags_start */
1446 TODO_df_finish | TODO_verify_rtl_sharing |
1447 TODO_dump_func |
1448 TODO_ggc_collect /* todo_flags_finish */