1 /* RTL factoring (sequence abstraction).
2 Copyright (C) 2004, 2005, 2006, 2007 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
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
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/>. */
22 #include "coretypes.h"
26 #include "basic-block.h"
34 #include "tree-pass.h"
35 #include "tree-flow.h"
38 #include "addresses.h"
40 /* Sequence abstraction:
42 It is a size optimization method. The main idea of this technique is to
43 find identical sequences of code, which can be turned into procedures and
44 then replace all occurrences with calls to the newly created subroutine.
45 It is kind of an opposite of function inlining.
47 There are four major parts of this file:
50 In order to avoid the comparison of every insn with every other, hash
51 value will be designed for every insn by COMPUTE_HASH.
52 These hash values are used for grouping the sequence candidates. So
53 we only need to compare every insn with every other in same hash group.
55 FILL_HASH_BUCKET creates all hash values and stores into HASH_BUCKETS.
56 The result is used by COLLECT_PATTERN_SEQS.
59 In code matching the algorithm compares every two possible sequence
60 candidates which last insns are in the same hash group. If these
61 sequences are identical they will be stored and do further searches for
62 finding more sequences which are identical with the first one.
64 COLLECT_PATTERN_SEQS does the code matching and stores the results into
68 This part computes the gain of abstraction which could be archived when
69 turning the pattern sequence into a pseudo-function and its matching
70 sequences into pseudo-calls. After it the most effective sequences will
71 be marked for abstraction.
73 RECOMPUTE_GAIN does the gain computation. The sequences with the maximum
74 gain is on the top of PATTERN_SEQS.
77 This part turns the pattern sequence into a pseudo-function and its
78 matching sequences into pseudo-calls.
80 ABSTRACT_BEST_SEQ does the code merging.
85 // Original source // After sequence abstraction
89 jump_label = &&exit_0;
98 jump_label = &&exit_1;
106 jump_label = &&exit_2;
114 jump_label = &&exit_3;
126 - Use REG_ALLOC_ORDER when choosing link register.
127 - Handle JUMP_INSNs. Also handle volatile function calls (handle them
128 similar to unconditional jumps.)
129 - Test command line option -fpic.
132 /* Predicate yielding nonzero iff X is an abstractable insn. Non-jump insns are
134 #define ABSTRACTABLE_INSN_P(X) (INSN_P (X) && !JUMP_P (X))
136 /* First parameter of the htab_create function call. */
137 #define HASH_INIT 1023
139 /* Multiplier for cost of sequence call to avoid abstracting short
141 #ifndef SEQ_CALL_COST_MULTIPLIER
142 #define SEQ_CALL_COST_MULTIPLIER 2
145 /* Recomputes the cost of MSEQ pattern/matching sequence. */
146 #define RECOMPUTE_COST(SEQ) \
151 for (l = 0; l < SEQ->abstracted_length; l++) \
153 SEQ->cost += compute_rtx_cost (x); \
154 x = prev_insn_in_block (x); \
158 /* A sequence matching a pattern sequence. */
159 typedef struct matching_seq_def
161 /* The last insn in the matching sequence. */
164 /* Index of INSN instruction. */
167 /* The number of insns matching in this sequence and the pattern sequence.
171 /* The number of insns selected to abstract from this sequence. Less than
172 or equal to MATCHING_LENGTH. */
173 int abstracted_length
;
175 /* The cost of the sequence. */
178 /* The next sequence in the chain matching the same pattern. */
179 struct matching_seq_def
*next_matching_seq
;
183 /* A pattern instruction sequence. */
184 typedef struct pattern_seq_def
186 /* The last insn in the pattern sequence. */
189 /* Index of INSN instruction. */
192 /* The gain of transforming the pattern sequence into a pseudo-function and
193 the matching sequences into pseudo-calls. */
196 /* The maximum of the ABSTRACTED_LENGTH of the matching sequences. */
197 int abstracted_length
;
199 /* The cost of the sequence. */
202 /* The register used to hold the return address during the pseudo-call. */
205 /* The sequences matching this pattern. */
206 matching_seq matching_seqs
;
208 /* The next pattern sequence in the chain. */
209 struct pattern_seq_def
*next_pattern_seq
;
213 /* A block of a pattern sequence. */
214 typedef struct seq_block_def
216 /* The number of insns in the block. */
219 /* The code_label of the block. */
222 /* The sequences entering the pattern sequence at LABEL. */
223 matching_seq matching_seqs
;
225 /* The next block in the chain. The blocks are sorted by LENGTH in
227 struct seq_block_def
*next_seq_block
;
230 /* Contains same sequence candidates for further searching. */
231 typedef struct hash_bucket_def
233 /* The hash value of the group. */
236 /* List of sequence candidates. */
237 htab_t seq_candidates
;
240 /* Contains the last insn of the sequence, and its index value. */
241 typedef struct hash_elem_def
243 /* Unique index; ordered by FILL_HASH_BUCKET. */
246 /* The last insn in the sequence. */
249 /* The cached length of the insn. */
253 /* The list of same sequence candidates. */
254 static htab_t hash_buckets
;
256 /* The pattern sequences collected from the current functions. */
257 static pattern_seq pattern_seqs
;
259 /* The blocks of the current pattern sequence. */
260 static seq_block seq_blocks
;
262 /* Cost of calling sequence. */
263 static int seq_call_cost
;
266 static int seq_jump_cost
;
268 /* Cost of returning. */
269 static int seq_return_cost
;
271 /* Returns the first insn preceding INSN for which INSN_P is true and belongs to
272 the same basic block. Returns NULL_RTX if no such insn can be found. */
275 prev_insn_in_block (rtx insn
)
277 basic_block bb
= BLOCK_FOR_INSN (insn
);
282 while (insn
!= BB_HEAD (bb
))
284 insn
= PREV_INSN (insn
);
291 /* Returns the hash value of INSN. */
294 compute_hash (rtx insn
)
296 unsigned int hash
= 0;
299 hash
= INSN_CODE (insn
) * 100;
301 prev
= prev_insn_in_block (insn
);
303 hash
+= INSN_CODE (prev
);
308 /* Compute the cost of INSN rtx for abstraction. */
311 compute_rtx_cost (rtx insn
)
313 struct hash_bucket_def tmp_bucket
;
314 p_hash_bucket bucket
;
315 struct hash_elem_def tmp_elem
;
316 p_hash_elem elem
= NULL
;
319 /* Compute hash value for INSN. */
320 tmp_bucket
.hash
= compute_hash (insn
);
322 /* Select the hash group. */
323 bucket
= htab_find (hash_buckets
, &tmp_bucket
);
327 tmp_elem
.insn
= insn
;
329 /* Select the insn. */
330 elem
= htab_find (bucket
->seq_candidates
, &tmp_elem
);
332 /* If INSN is parsed the cost will be the cached length. */
337 /* If we can't parse the INSN cost will be the instruction length. */
340 cost
= get_attr_length (insn
);
342 /* Cache the length. */
347 /* If we can't get an accurate estimate for a complex instruction,
348 assume that it has the same cost as a single fast instruction. */
349 return cost
!= 0 ? cost
: COSTS_N_INSNS (1);
352 /* Determines the number of common insns in the sequences ending in INSN1 and
353 INSN2. Returns with LEN number of common insns and COST cost of sequence.
357 matching_length (rtx insn1
, rtx insn2
, int* len
, int* cost
)
366 while (x1
&& x2
&& (x1
!= insn2
) && (x2
!= insn1
)
367 && rtx_equal_p (PATTERN (x1
), PATTERN (x2
)))
370 (*cost
) += compute_rtx_cost (x1
);
371 x1
= prev_insn_in_block (x1
);
372 x2
= prev_insn_in_block (x2
);
376 /* Adds E0 as a pattern sequence to PATTERN_SEQS with E1 as a matching
380 match_seqs (p_hash_elem e0
, p_hash_elem e1
)
384 matching_seq mseq
, p_prev
, p_next
;
386 /* Determines the cost of the sequence and return without doing anything
387 if it is too small to produce any gain. */
388 matching_length (e0
->insn
, e1
->insn
, &len
, &cost
);
389 if (cost
<= seq_call_cost
)
392 /* Prepend a new PATTERN_SEQ to PATTERN_SEQS if the last pattern sequence
393 does not end in E0->INSN. This assumes that once the E0->INSN changes
394 the old value will never appear again. */
395 if (!pattern_seqs
|| pattern_seqs
->insn
!= e0
->insn
)
398 (pattern_seq
) xmalloc (sizeof (struct pattern_seq_def
));
399 pseq
->insn
= e0
->insn
;
401 pseq
->gain
= 0; /* Set to zero to force recomputing. */
402 pseq
->abstracted_length
= 0;
404 pseq
->link_reg
= NULL_RTX
;
405 pseq
->matching_seqs
= NULL
;
406 pseq
->next_pattern_seq
= pattern_seqs
;
410 /* Find the position of E1 in the matching sequences list. */
412 p_next
= pattern_seqs
->matching_seqs
;
413 while (p_next
&& p_next
->idx
< e1
->idx
)
416 p_next
= p_next
->next_matching_seq
;
419 /* Add a new E1 matching sequence to the pattern sequence. We know that
420 it ends in E0->INSN. */
421 mseq
= (matching_seq
) xmalloc (sizeof (struct matching_seq_def
));
422 mseq
->insn
= e1
->insn
;
424 mseq
->matching_length
= len
;
425 mseq
->abstracted_length
= 0;
429 pattern_seqs
->matching_seqs
= mseq
;
431 p_prev
->next_matching_seq
= mseq
;
432 mseq
->next_matching_seq
= p_next
;
435 /* Collects all pattern sequences and their matching sequences and puts them
436 into PATTERN_SEQS. */
439 collect_pattern_seqs (void)
441 htab_iterator hti0
, hti1
, hti2
;
442 p_hash_bucket hash_bucket
;
446 bitmap_head stack_reg_live
;
448 /* Extra initialization step to ensure that no stack registers (if present)
449 are live across abnormal edges. Set a flag in STACK_REG_LIVE for an insn
450 if a stack register is live after the insn. */
451 bitmap_initialize (&stack_reg_live
, NULL
);
456 struct propagate_block_info
*pbi
;
459 /* Initialize liveness propagation. */
460 INIT_REG_SET (&live
);
461 COPY_REG_SET (&live
, bb
->il
.rtl
->global_live_at_end
);
462 pbi
= init_propagate_block_info (bb
, &live
, NULL
, NULL
, 0);
464 /* Propagate liveness info and mark insns where a stack reg is live. */
469 for (reg
= FIRST_STACK_REG
; reg
<= LAST_STACK_REG
; reg
++)
471 if (REGNO_REG_SET_P (&live
, reg
))
473 bitmap_set_bit (&stack_reg_live
, INSN_UID (insn
));
478 if (insn
== BB_HEAD (bb
))
480 insn
= propagate_one_insn (pbi
, insn
);
483 /* Free unused data. */
484 CLEAR_REG_SET (&live
);
485 free_propagate_block_info (pbi
);
489 /* Initialize PATTERN_SEQS to empty. */
492 /* Try to match every abstractable insn with every other insn in the same
495 FOR_EACH_HTAB_ELEMENT (hash_buckets
, hash_bucket
, p_hash_bucket
, hti0
)
496 if (htab_elements (hash_bucket
->seq_candidates
) > 1)
497 FOR_EACH_HTAB_ELEMENT (hash_bucket
->seq_candidates
, e0
, p_hash_elem
, hti1
)
498 FOR_EACH_HTAB_ELEMENT (hash_bucket
->seq_candidates
, e1
, p_hash_elem
,
502 && !bitmap_bit_p (&stack_reg_live
, INSN_UID (e0
->insn
))
503 && !bitmap_bit_p (&stack_reg_live
, INSN_UID (e1
->insn
))
508 /* Free unused data. */
509 bitmap_clear (&stack_reg_live
);
513 /* Transforms a regset to a HARD_REG_SET. Every hard register in REGS is added
514 to hregs. Additionally, the hard counterpart of every renumbered pseudo
515 register is also added. */
518 renumbered_reg_set_to_hard_reg_set (HARD_REG_SET
* hregs
, regset regs
)
522 REG_SET_TO_HARD_REG_SET (*hregs
, regs
);
523 for (r
= FIRST_PSEUDO_REGISTER
; r
< max_regno
; r
++)
524 if (REGNO_REG_SET_P (regs
, r
) && reg_renumber
[r
] >= 0)
525 SET_HARD_REG_BIT (*hregs
, reg_renumber
[r
]);
528 /* Clears the bits in REGS for all registers, which are live in the sequence
529 give by its last INSN and its LENGTH. */
532 clear_regs_live_in_seq (HARD_REG_SET
* regs
, rtx insn
, int length
)
537 struct propagate_block_info
*pbi
;
541 /* Initialize liveness propagation. */
542 bb
= BLOCK_FOR_INSN (insn
);
543 INIT_REG_SET (&live
);
544 COPY_REG_SET (&live
, bb
->il
.rtl
->global_live_at_end
);
545 pbi
= init_propagate_block_info (bb
, &live
, NULL
, NULL
, 0);
547 /* Propagate until INSN if found. */
548 for (x
= BB_END (bb
); x
!= insn
;)
549 x
= propagate_one_insn (pbi
, x
);
551 /* Clear registers live after INSN. */
552 renumbered_reg_set_to_hard_reg_set (&hlive
, &live
);
553 AND_COMPL_HARD_REG_SET (*regs
, hlive
);
555 /* Clear registers live in and before the sequence. */
556 for (i
= 0; i
< length
;)
558 rtx prev
= propagate_one_insn (pbi
, x
);
562 renumbered_reg_set_to_hard_reg_set (&hlive
, &live
);
563 AND_COMPL_HARD_REG_SET (*regs
, hlive
);
570 /* Free unused data. */
571 free_propagate_block_info (pbi
);
572 CLEAR_REG_SET (&live
);
575 /* Computes the gain of turning PSEQ into a pseudo-function and its matching
576 sequences into pseudo-calls. Also computes and caches the number of insns to
577 abstract from the matching sequences. */
580 recompute_gain_for_pattern_seq (pattern_seq pseq
)
586 HARD_REG_SET linkregs
;
588 /* Initialize data. */
589 SET_HARD_REG_SET (linkregs
);
590 pseq
->link_reg
= NULL_RTX
;
591 pseq
->abstracted_length
= 0;
593 pseq
->gain
= -(seq_call_cost
- seq_jump_cost
+ seq_return_cost
);
595 /* Determine ABSTRACTED_LENGTH and COST for matching sequences of PSEQ.
596 ABSTRACTED_LENGTH may be less than MATCHING_LENGTH if sequences in the
597 same block overlap. */
599 for (mseq
= pseq
->matching_seqs
; mseq
; mseq
= mseq
->next_matching_seq
)
601 /* Determine ABSTRACTED_LENGTH. */
602 if (mseq
->next_matching_seq
)
603 mseq
->abstracted_length
= (int)(mseq
->next_matching_seq
->idx
-
606 mseq
->abstracted_length
= mseq
->matching_length
;
608 if (mseq
->abstracted_length
> mseq
->matching_length
)
609 mseq
->abstracted_length
= mseq
->matching_length
;
611 /* Compute the cost of sequence. */
612 RECOMPUTE_COST (mseq
);
614 /* If COST is big enough registers live in this matching sequence
615 should not be used as a link register. Also set ABSTRACTED_LENGTH
617 if (mseq
->cost
> seq_call_cost
)
619 clear_regs_live_in_seq (&linkregs
, mseq
->insn
,
620 mseq
->abstracted_length
);
621 if (mseq
->abstracted_length
> pseq
->abstracted_length
)
622 pseq
->abstracted_length
= mseq
->abstracted_length
;
626 /* Modify ABSTRACTED_LENGTH of PSEQ if pattern sequence overlaps with one
627 of the matching sequences. */
628 for (mseq
= pseq
->matching_seqs
; mseq
; mseq
= mseq
->next_matching_seq
)
631 for (i
= 0; (i
< pseq
->abstracted_length
) && (x
!= mseq
->insn
); i
++)
632 x
= prev_insn_in_block (x
);
633 pseq
->abstracted_length
= i
;
636 /* Compute the cost of pattern sequence. */
637 RECOMPUTE_COST (pseq
);
639 /* No gain if COST is too small. */
640 if (pseq
->cost
<= seq_call_cost
)
646 /* Ensure that no matching sequence is longer than the pattern sequence. */
647 for (mseq
= pseq
->matching_seqs
; mseq
; mseq
= mseq
->next_matching_seq
)
649 if (mseq
->abstracted_length
> pseq
->abstracted_length
)
651 mseq
->abstracted_length
= pseq
->abstracted_length
;
652 RECOMPUTE_COST (mseq
);
654 /* Once the length is stabilizing the gain can be calculated. */
655 if (mseq
->cost
> seq_call_cost
)
656 pseq
->gain
+= mseq
->cost
- seq_call_cost
;
659 /* No need to do further work if there is no gain. */
663 /* Should not use registers live in the pattern sequence as link register.
665 clear_regs_live_in_seq (&linkregs
, pseq
->insn
, pseq
->abstracted_length
);
667 /* Determine whether pattern sequence contains a call_insn. */
670 for (i
= 0; i
< pseq
->abstracted_length
; i
++)
677 x
= prev_insn_in_block (x
);
680 /* Should not use a register as a link register if - it is a fixed
681 register, or - the sequence contains a call insn and the register is a
682 call used register, or - the register needs to be saved if used in a
683 function but was not used before (since saving it can invalidate already
684 computed frame pointer offsets), or - the register cannot be used as a
687 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
689 #ifdef REGNO_OK_FOR_INDIRECT_JUMP_P
690 || (!REGNO_OK_FOR_INDIRECT_JUMP_P (i
, Pmode
))
692 || (!ok_for_base_p_1 (i
, Pmode
, MEM
, SCRATCH
))
693 || (!reg_class_subset_p (REGNO_REG_CLASS (i
),
694 base_reg_class (VOIDmode
, MEM
, SCRATCH
)))
696 || (hascall
&& call_used_regs
[i
])
697 || (!call_used_regs
[i
] && !regs_ever_live
[i
]))
698 CLEAR_HARD_REG_BIT (linkregs
, i
);
700 /* Find an appropriate register to be used as the link register. */
701 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
702 if (TEST_HARD_REG_BIT (linkregs
, i
))
704 pseq
->link_reg
= gen_rtx_REG (Pmode
, i
);
708 /* Abstraction is not possible if no link register is available, so set
714 /* Deallocates memory occupied by PSEQ and its matching seqs. */
717 free_pattern_seq (pattern_seq pseq
)
719 while (pseq
->matching_seqs
)
721 matching_seq mseq
= pseq
->matching_seqs
;
722 pseq
->matching_seqs
= mseq
->next_matching_seq
;
729 /* Computes the gain for pattern sequences. Pattern sequences producing no gain
730 are deleted. The pattern sequence with the biggest gain is moved to the first
731 place of PATTERN_SEQS. */
734 recompute_gain (void)
740 for (pseq
= &pattern_seqs
; *pseq
;)
742 if ((*pseq
)->gain
<= 0)
743 recompute_gain_for_pattern_seq (*pseq
);
745 if ((*pseq
)->gain
> 0)
747 if ((*pseq
)->gain
> maxgain
)
749 pattern_seq temp
= *pseq
;
750 (*pseq
) = temp
->next_pattern_seq
;
751 temp
->next_pattern_seq
= pattern_seqs
;
753 maxgain
= pattern_seqs
->gain
;
757 pseq
= &(*pseq
)->next_pattern_seq
;
762 pattern_seq temp
= *pseq
;
763 *pseq
= temp
->next_pattern_seq
;
764 free_pattern_seq (temp
);
769 /* Updated those pattern sequences and matching sequences, which overlap with
770 the sequence given by INSN and LEN. Deletes sequences shrinking below a
774 erase_from_pattern_seqs (rtx insn
, int len
)
784 for (pseq
= &pattern_seqs
; *pseq
;)
788 for (x
= (*pseq
)->insn
; x
&& (x
!= insn
);
789 x
= prev_insn_in_block (x
))
792 pcost
+= compute_rtx_cost (x
);
795 if (pcost
<= seq_call_cost
)
797 pattern_seq temp
= *pseq
;
798 *pseq
= temp
->next_pattern_seq
;
799 free_pattern_seq (temp
);
803 for (mseq
= &(*pseq
)->matching_seqs
; *mseq
;)
807 for (x
= (*mseq
)->insn
;
808 x
&& (x
!= insn
) && (mlen
< plen
)
809 && (mlen
< (*mseq
)->matching_length
);
810 x
= prev_insn_in_block (x
))
813 mcost
+= compute_rtx_cost (x
);
816 if (mcost
<= seq_call_cost
)
818 matching_seq temp
= *mseq
;
819 *mseq
= temp
->next_matching_seq
;
821 /* Set to 0 to force gain recomputation. */
826 if (mlen
< (*mseq
)->matching_length
)
828 (*mseq
)->cost
= mcost
;
829 (*mseq
)->matching_length
= mlen
;
830 /* Set to 0 to force gain recomputation. */
833 mseq
= &(*mseq
)->next_matching_seq
;
837 pseq
= &(*pseq
)->next_pattern_seq
;
842 insn
= prev_insn_in_block (insn
);
846 /* Updates those pattern sequences and matching sequences, which overlap with
847 the pattern sequence with the biggest gain and its matching sequences. */
850 update_pattern_seqs (void)
852 pattern_seq bestpseq
;
855 bestpseq
= pattern_seqs
;
856 pattern_seqs
= bestpseq
->next_pattern_seq
;
858 for (mseq
= bestpseq
->matching_seqs
; mseq
; mseq
= mseq
->next_matching_seq
)
859 if (mseq
->cost
> seq_call_cost
)
860 erase_from_pattern_seqs (mseq
->insn
, mseq
->abstracted_length
);
861 erase_from_pattern_seqs (bestpseq
->insn
, bestpseq
->abstracted_length
);
863 bestpseq
->next_pattern_seq
= pattern_seqs
;
864 pattern_seqs
= bestpseq
;
867 /* Groups together those matching sequences of the best pattern sequence, which
868 have the same ABSTRACTED_LENGTH and puts these groups in ascending order.
869 SEQ_BLOCKS contains the result. */
872 determine_seq_blocks (void)
878 /* Initialize SEQ_BLOCKS to empty. */
881 /* Process all matching sequences. */
882 for (mseq
= &pattern_seqs
->matching_seqs
; *mseq
;)
884 /* Deal only with matching sequences being long enough. */
885 if ((*mseq
)->cost
<= seq_call_cost
)
887 mseq
= &(*mseq
)->next_matching_seq
;
891 /* Ensure that SB contains a seq_block with the appropriate length.
892 Insert a new seq_block if necessary. */
893 if (!seq_blocks
|| ((*mseq
)->abstracted_length
< seq_blocks
->length
))
895 sb
= (seq_block
) xmalloc (sizeof (struct seq_block_def
));
896 sb
->length
= (*mseq
)->abstracted_length
;
897 sb
->label
= NULL_RTX
;
898 sb
->matching_seqs
= 0;
899 sb
->next_seq_block
= seq_blocks
;
904 for (sb
= seq_blocks
; sb
; sb
= sb
->next_seq_block
)
906 if ((*mseq
)->abstracted_length
== sb
->length
)
908 if (!sb
->next_seq_block
909 || ((*mseq
)->abstracted_length
<
910 sb
->next_seq_block
->length
))
913 (seq_block
) xmalloc (sizeof (struct seq_block_def
));
914 temp
->length
= (*mseq
)->abstracted_length
;
915 temp
->label
= NULL_RTX
;
916 temp
->matching_seqs
= 0;
917 temp
->next_seq_block
= sb
->next_seq_block
;
918 sb
->next_seq_block
= temp
;
923 /* Remove the matching sequence from the linked list of the pattern
924 sequence and link it to SB. */
926 *mseq
= m
->next_matching_seq
;
927 m
->next_matching_seq
= sb
->matching_seqs
;
928 sb
->matching_seqs
= m
;
932 /* Builds a symbol_ref for LABEL. */
935 gen_symbol_ref_rtx_for_label (rtx label
)
940 ASM_GENERATE_INTERNAL_LABEL (name
, "L", CODE_LABEL_NUMBER (label
));
941 sym
= gen_rtx_SYMBOL_REF (Pmode
, ggc_strdup (name
));
942 SYMBOL_REF_FLAGS (sym
) = SYMBOL_FLAG_LOCAL
;
946 /* Ensures that INSN is the last insn in its block and returns the block label
947 of the next block. */
950 block_label_after (rtx insn
)
952 basic_block bb
= BLOCK_FOR_INSN (insn
);
953 if ((insn
== BB_END (bb
)) && (bb
->next_bb
!= EXIT_BLOCK_PTR
))
954 return block_label (bb
->next_bb
);
956 return block_label (split_block (bb
, insn
)->dest
);
959 /* Ensures that the last insns of the best pattern and its matching sequences
960 are the last insns in their block. Additionally, extends the live set at the
961 end of the pattern sequence with the live sets at the end of the matching
965 split_blocks_after_seqs (void)
970 block_label_after (pattern_seqs
->insn
);
971 for (sb
= seq_blocks
; sb
; sb
= sb
->next_seq_block
)
973 for (mseq
= sb
->matching_seqs
; mseq
; mseq
= mseq
->next_matching_seq
)
975 block_label_after (mseq
->insn
);
976 IOR_REG_SET (BLOCK_FOR_INSN (pattern_seqs
->insn
)->
977 il
.rtl
->global_live_at_end
,
978 BLOCK_FOR_INSN (mseq
->insn
)->il
.rtl
->global_live_at_end
);
983 /* Splits the best pattern sequence according to SEQ_BLOCKS. Emits pseudo-call
984 and -return insns before and after the sequence. */
987 split_pattern_seq (void)
991 rtx retlabel
, retjmp
, saveinsn
;
995 insn
= pattern_seqs
->insn
;
996 bb
= BLOCK_FOR_INSN (insn
);
998 /* Get the label after the sequence. This will be the return address. The
999 label will be referenced using a symbol_ref so protect it from
1001 retlabel
= block_label_after (insn
);
1002 LABEL_PRESERVE_P (retlabel
) = 1;
1004 /* Emit an indirect jump via the link register after the sequence acting
1005 as the return insn. Also emit a barrier and update the basic block. */
1006 retjmp
= emit_jump_insn_after (gen_indirect_jump (pattern_seqs
->link_reg
),
1008 emit_barrier_after (BB_END (bb
));
1010 /* Replace all outgoing edges with a new one to the block of RETLABEL. */
1011 while (EDGE_COUNT (bb
->succs
) != 0)
1012 remove_edge (EDGE_SUCC (bb
, 0));
1013 make_edge (bb
, BLOCK_FOR_INSN (retlabel
), EDGE_ABNORMAL
);
1015 /* Split the sequence according to SEQ_BLOCKS and cache the label of the
1016 resulting basic blocks. */
1018 for (sb
= seq_blocks
; sb
; sb
= sb
->next_seq_block
)
1020 for (; i
< sb
->length
; i
++)
1021 insn
= prev_insn_in_block (insn
);
1023 sb
->label
= block_label (split_block (bb
, insn
)->dest
);
1026 /* Emit an insn saving the return address to the link register before the
1028 saveinsn
= emit_insn_after (gen_move_insn (pattern_seqs
->link_reg
,
1029 gen_symbol_ref_rtx_for_label
1030 (retlabel
)), BB_END (bb
));
1031 /* Update liveness info. */
1032 SET_REGNO_REG_SET (bb
->il
.rtl
->global_live_at_end
,
1033 REGNO (pattern_seqs
->link_reg
));
1036 /* Deletes the insns of the matching sequences of the best pattern sequence and
1037 replaces them with pseudo-calls to the pattern sequence. */
1040 erase_matching_seqs (void)
1046 rtx retlabel
, saveinsn
, callinsn
;
1049 for (sb
= seq_blocks
; sb
; sb
= sb
->next_seq_block
)
1051 for (mseq
= sb
->matching_seqs
; mseq
; mseq
= mseq
->next_matching_seq
)
1054 bb
= BLOCK_FOR_INSN (insn
);
1056 /* Get the label after the sequence. This will be the return
1057 address. The label will be referenced using a symbol_ref so
1058 protect it from deleting. */
1059 retlabel
= block_label_after (insn
);
1060 LABEL_PRESERVE_P (retlabel
) = 1;
1062 /* Delete the insns of the sequence. */
1063 for (i
= 0; i
< sb
->length
; i
++)
1064 insn
= prev_insn_in_block (insn
);
1065 delete_basic_block (split_block (bb
, insn
)->dest
);
1067 /* Emit an insn saving the return address to the link register
1068 before the deleted sequence. */
1069 saveinsn
= emit_insn_after (gen_move_insn (pattern_seqs
->link_reg
,
1070 gen_symbol_ref_rtx_for_label
1073 BLOCK_FOR_INSN (saveinsn
) = bb
;
1075 /* Emit a jump to the appropriate part of the pattern sequence
1076 after the save insn. Also update the basic block. */
1077 callinsn
= emit_jump_insn_after (gen_jump (sb
->label
), saveinsn
);
1078 JUMP_LABEL (callinsn
) = sb
->label
;
1079 LABEL_NUSES (sb
->label
)++;
1080 BLOCK_FOR_INSN (callinsn
) = bb
;
1081 BB_END (bb
) = callinsn
;
1083 /* Maintain control flow and liveness information. */
1084 SET_REGNO_REG_SET (bb
->il
.rtl
->global_live_at_end
,
1085 REGNO (pattern_seqs
->link_reg
));
1086 emit_barrier_after (BB_END (bb
));
1087 make_single_succ_edge (bb
, BLOCK_FOR_INSN (sb
->label
), 0);
1088 IOR_REG_SET (bb
->il
.rtl
->global_live_at_end
,
1089 BLOCK_FOR_INSN (sb
->label
)->il
.rtl
->global_live_at_start
);
1091 make_edge (BLOCK_FOR_INSN (seq_blocks
->label
),
1092 BLOCK_FOR_INSN (retlabel
), EDGE_ABNORMAL
);
1097 /* Deallocates SEQ_BLOCKS and all the matching sequences. */
1100 free_seq_blocks (void)
1104 seq_block sb
= seq_blocks
;
1105 while (sb
->matching_seqs
)
1107 matching_seq mseq
= sb
->matching_seqs
;
1108 sb
->matching_seqs
= mseq
->next_matching_seq
;
1111 seq_blocks
= sb
->next_seq_block
;
1116 /* Transforms the best pattern sequence into a pseudo-function and its matching
1117 sequences to pseudo-calls. Afterwards the best pattern sequence is removed
1118 from PATTERN_SEQS. */
1121 abstract_best_seq (void)
1123 pattern_seq bestpseq
;
1125 /* Do the abstraction. */
1126 determine_seq_blocks ();
1127 split_blocks_after_seqs ();
1128 split_pattern_seq ();
1129 erase_matching_seqs ();
1132 /* Record the usage of the link register. */
1133 regs_ever_live
[REGNO (pattern_seqs
->link_reg
)] = 1;
1135 /* Remove the best pattern sequence. */
1136 bestpseq
= pattern_seqs
;
1137 pattern_seqs
= bestpseq
->next_pattern_seq
;
1138 free_pattern_seq (bestpseq
);
1141 /* Prints info on the pattern sequences to the dump file. */
1144 dump_pattern_seqs (void)
1152 fprintf (dump_file
, ";; Pattern sequences\n");
1153 for (pseq
= pattern_seqs
; pseq
; pseq
= pseq
->next_pattern_seq
)
1155 fprintf (dump_file
, "Pattern sequence at insn %d matches sequences at",
1156 INSN_UID (pseq
->insn
));
1157 for (mseq
= pseq
->matching_seqs
; mseq
; mseq
= mseq
->next_matching_seq
)
1159 fprintf (dump_file
, " insn %d (length %d)", INSN_UID (mseq
->insn
),
1160 mseq
->matching_length
);
1161 if (mseq
->next_matching_seq
)
1162 fprintf (dump_file
, ",");
1164 fprintf (dump_file
, ".\n");
1166 fprintf (dump_file
, "\n");
1169 /* Prints info on the best pattern sequence transformed in the ITER-th
1170 iteration to the dump file. */
1173 dump_best_pattern_seq (int iter
)
1180 fprintf (dump_file
, ";; Iteration %d\n", iter
);
1182 "Best pattern sequence with %d gain is at insn %d (length %d).\n",
1183 pattern_seqs
->gain
, INSN_UID (pattern_seqs
->insn
),
1184 pattern_seqs
->abstracted_length
);
1185 fprintf (dump_file
, "Matching sequences are at");
1186 for (mseq
= pattern_seqs
->matching_seqs
; mseq
;
1187 mseq
= mseq
->next_matching_seq
)
1189 fprintf (dump_file
, " insn %d (length %d)", INSN_UID (mseq
->insn
),
1190 mseq
->abstracted_length
);
1191 if (mseq
->next_matching_seq
)
1192 fprintf (dump_file
, ",");
1194 fprintf (dump_file
, ".\n");
1195 fprintf (dump_file
, "Using reg %d as link register.\n\n",
1196 REGNO (pattern_seqs
->link_reg
));
1199 /* Htab hash function for hash_bucket_def structure. */
1202 htab_hash_bucket (const void *p
)
1204 p_hash_bucket bucket
= (p_hash_bucket
) p
;
1205 return bucket
->hash
;
1208 /* Htab equal function for hash_bucket_def structure. */
1211 htab_eq_bucket (const void *p0
, const void *p1
)
1213 return htab_hash_bucket (p0
) == htab_hash_bucket (p1
);
1216 /* Htab delete function for hash_bucket_def structure. */
1219 htab_del_bucket (void *p
)
1221 p_hash_bucket bucket
= (p_hash_bucket
) p
;
1223 if (bucket
->seq_candidates
)
1224 htab_delete (bucket
->seq_candidates
);
1229 /* Htab hash function for hash_bucket_def structure. */
1232 htab_hash_elem (const void *p
)
1234 p_hash_elem elem
= (p_hash_elem
) p
;
1235 return htab_hash_pointer (elem
->insn
);
1238 /* Htab equal function for hash_bucket_def structure. */
1241 htab_eq_elem (const void *p0
, const void *p1
)
1243 return htab_hash_elem (p0
) == htab_hash_elem (p1
);
1246 /* Htab delete function for hash_bucket_def structure. */
1249 htab_del_elem (void *p
)
1251 p_hash_elem elem
= (p_hash_elem
) p
;
1255 /* Creates a hash value for each sequence candidate and saves them
1259 fill_hash_bucket (void)
1264 p_hash_bucket bucket
;
1265 struct hash_bucket_def tmp_bucket
;
1267 unsigned long insn_idx
;
1272 FOR_BB_INSNS_REVERSE (bb
, insn
)
1274 if (!ABSTRACTABLE_INSN_P (insn
))
1277 /* Compute hash value for INSN. */
1278 tmp_bucket
.hash
= compute_hash (insn
);
1280 /* Select the hash group. */
1281 bucket
= htab_find (hash_buckets
, &tmp_bucket
);
1285 /* Create a new hash group. */
1286 bucket
= (p_hash_bucket
) xcalloc (1,
1287 sizeof (struct hash_bucket_def
));
1288 bucket
->hash
= tmp_bucket
.hash
;
1289 bucket
->seq_candidates
= NULL
;
1291 slot
= htab_find_slot (hash_buckets
, &tmp_bucket
, INSERT
);
1295 /* Create new list for storing sequence candidates. */
1296 if (!bucket
->seq_candidates
)
1297 bucket
->seq_candidates
= htab_create (HASH_INIT
,
1302 elem
= (p_hash_elem
) xcalloc (1, sizeof (struct hash_elem_def
));
1304 elem
->idx
= insn_idx
;
1305 elem
->length
= get_attr_length (insn
);
1307 /* Insert INSN into BUCKET hash bucket. */
1308 slot
= htab_find_slot (bucket
->seq_candidates
, elem
, INSERT
);
1316 /* Computes the cost of calling sequence and the cost of return. */
1319 compute_init_costs (void)
1321 rtx rtx_jump
, rtx_store
, rtx_return
, reg
, label
;
1328 label
= block_label (bb
);
1329 reg
= gen_rtx_REG (Pmode
, 0);
1331 /* Pattern for indirect jump. */
1332 rtx_jump
= gen_indirect_jump (reg
);
1334 /* Pattern for storing address. */
1335 rtx_store
= gen_rtx_SET (VOIDmode
, reg
, gen_symbol_ref_rtx_for_label (label
));
1337 /* Pattern for return insn. */
1338 rtx_return
= gen_jump (label
);
1340 /* The cost of jump. */
1341 seq_jump_cost
= compute_rtx_cost (make_jump_insn_raw (rtx_jump
));
1343 /* The cost of calling sequence. */
1344 seq_call_cost
= seq_jump_cost
+ compute_rtx_cost (make_insn_raw (rtx_store
));
1346 /* The cost of return. */
1347 seq_return_cost
= compute_rtx_cost (make_jump_insn_raw (rtx_return
));
1349 /* Simple heuristic for minimal sequence cost. */
1350 seq_call_cost
= (int)(seq_call_cost
* (double)SEQ_CALL_COST_MULTIPLIER
);
1353 /* Finds equivalent insn sequences in the current function and retains only one
1354 instance of them which is turned into a pseudo-function. The additional
1355 copies are erased and replaced by pseudo-calls to the retained sequence. */
1362 /* Create a hash list for COLLECT_PATTERN_SEQS. */
1363 hash_buckets
= htab_create (HASH_INIT
, htab_hash_bucket
, htab_eq_bucket
,
1365 fill_hash_bucket ();
1367 /* Compute the common cost of abstraction. */
1368 compute_init_costs ();
1370 /* Build an initial set of pattern sequences from the current function. */
1371 collect_pattern_seqs ();
1372 dump_pattern_seqs ();
1374 /* Iterate until there are no sequences to abstract. */
1375 for (iter
= 1;; iter
++)
1377 /* Recompute gain for sequences if necessary and select sequence with
1382 dump_best_pattern_seq (iter
);
1383 /* Update the cached info of the other sequences and force gain
1384 recomputation where needed. */
1385 update_pattern_seqs ();
1386 /* Turn best sequences into pseudo-functions and -calls. */
1387 abstract_best_seq ();
1390 /* Cleanup hash tables. */
1391 htab_delete (hash_buckets
);
1396 count_or_remove_death_notes (NULL
, 1);
1398 life_analysis (PROP_DEATH_NOTES
| PROP_SCAN_DEAD_CODE
1399 | PROP_KILL_DEAD_CODE
);
1401 /* Extra cleanup. */
1402 cleanup_cfg (CLEANUP_EXPENSIVE
|
1403 CLEANUP_UPDATE_LIFE
|
1404 (flag_crossjumping
? CLEANUP_CROSSJUMP
: 0));
1408 /* The gate function for TREE_OPT_PASS. */
1411 gate_rtl_seqabstr (void)
1413 return flag_rtl_seqabstr
;
1416 /* The entry point of the sequence abstraction algorithm. */
1419 rest_of_rtl_seqabstr (void)
1421 life_analysis (PROP_DEATH_NOTES
| PROP_SCAN_DEAD_CODE
| PROP_KILL_DEAD_CODE
);
1423 cleanup_cfg (CLEANUP_EXPENSIVE
|
1424 CLEANUP_UPDATE_LIFE
|
1425 (flag_crossjumping
? CLEANUP_CROSSJUMP
: 0));
1427 /* Abstract out common insn sequences. */
1432 struct tree_opt_pass pass_rtl_seqabstr
= {
1433 "seqabstr", /* name */
1434 gate_rtl_seqabstr
, /* gate */
1435 rest_of_rtl_seqabstr
, /* execute */
1438 0, /* static_pass_number */
1439 TV_SEQABSTR
, /* tv_id */
1440 0, /* properties_required */
1441 0, /* properties_provided */
1442 0, /* properties_destroyed */
1443 0, /* todo_flags_start */
1445 TODO_ggc_collect
, /* todo_flags_finish */