1 /* Transformations based on profile information for values.
2 Copyright (C) 2003, 2004, 2005 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
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 COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 #include "coretypes.h"
27 #include "hard-reg-set.h"
28 #include "basic-block.h"
29 #include "value-prof.h"
32 #include "insn-config.h"
37 #include "tree-flow.h"
38 #include "tree-flow-inline.h"
39 #include "diagnostic.h"
44 static struct value_prof_hooks
*value_prof_hooks
;
46 /* This is the vector of histograms. Created in find_values_to_profile.
47 During profile generation, freed by instrument_values.
48 During profile use, freed by value_profile_transformations. */
50 static histogram_values static_values
= NULL
;
52 /* In this file value profile based optimizations are placed. Currently the
53 following optimizations are implemented (for more detailed descriptions
54 see comments at value_profile_transformations):
56 1) Division/modulo specialization. Provided that we can determine that the
57 operands of the division have some special properties, we may use it to
58 produce more effective code.
59 2) Speculative prefetching. If we are able to determine that the difference
60 between addresses accessed by a memory reference is usually constant, we
61 may add the prefetch instructions.
63 Every such optimization should add its requirements for profiled values to
64 insn_values_to_profile function. This function is called from branch_prob
65 in profile.c and the requested values are instrumented by it in the first
66 compilation with -fprofile-arcs. The optimization may then read the
67 gathered data in the second compilation with -fbranch-probabilities.
69 There are currently two versions, RTL-based and tree-based. Over time
70 the RTL-based version may go away.
72 In the RTL-based version, the measured data is appended as REG_VALUE_PROFILE
73 note to the instrumented insn. The argument to the note consists of an
74 EXPR_LIST where its members have the following meaning (from the first to
77 -- type of information gathered (HIST_TYPE*)
78 -- the expression that is profiled
79 -- list of counters starting from the first one.
81 In the tree-based version, the measured data is pointed to from the histograms
82 field of the statement annotation of the instrumented insns. It is
83 kept as a linked list of struct histogram_value_t's, which contain the
84 same information as above. */
86 /* For speculative prefetching, the range in that we do not prefetch (because
87 we assume that it will be in cache anyway). The asymmetry between min and
88 max range is trying to reflect the fact that the sequential prefetching
89 of the data is commonly done directly by hardware. Nevertheless, these
90 values are just a guess and should of course be target-specific.
92 FIXME: There is no tree form of speculative prefetching as yet.
94 FIXME: A better approach to instrumentation in the profile-generation
95 pass is to generate calls to magic library functions (to be added to
96 libgcc) rather than inline code. This approach will probably be
97 necessary to get tree-based speculative prefetching working in a useful
98 fashion, as inline code bloats things so much the rest of the compiler has
99 serious problems dealing with it (judging from the rtl behavior). */
101 #ifndef NOPREFETCH_RANGE_MIN
102 #define NOPREFETCH_RANGE_MIN (-16)
104 #ifndef NOPREFETCH_RANGE_MAX
105 #define NOPREFETCH_RANGE_MAX 32
108 static void rtl_divmod_values_to_profile (rtx
, histogram_values
*);
110 static bool insn_prefetch_values_to_profile (rtx
, histogram_values
*);
111 static int find_mem_reference_1 (rtx
*, void *);
112 static void find_mem_reference_2 (rtx
, rtx
, void *);
113 static bool find_mem_reference (rtx
, rtx
*, int *);
116 static void rtl_values_to_profile (rtx
, histogram_values
*);
117 static rtx
rtl_divmod_fixed_value (enum machine_mode
, enum rtx_code
, rtx
, rtx
,
118 rtx
, gcov_type
, int);
119 static rtx
rtl_mod_pow2 (enum machine_mode
, enum rtx_code
, rtx
, rtx
, rtx
, int);
120 static rtx
rtl_mod_subtract (enum machine_mode
, enum rtx_code
, rtx
, rtx
, rtx
,
123 static rtx
gen_speculative_prefetch (rtx
, gcov_type
, int);
125 static bool rtl_divmod_fixed_value_transform (rtx
);
126 static bool rtl_mod_pow2_value_transform (rtx
);
127 static bool rtl_mod_subtract_transform (rtx
);
129 static bool speculative_prefetching_transform (rtx
);
131 static void tree_divmod_values_to_profile (tree
, histogram_values
*);
132 static void tree_values_to_profile (tree
, histogram_values
*);
133 static tree
tree_divmod_fixed_value (tree
, tree
, tree
, tree
,
134 tree
, int, gcov_type
, gcov_type
);
135 static tree
tree_mod_pow2 (tree
, tree
, tree
, tree
, int, gcov_type
, gcov_type
);
136 static tree
tree_mod_subtract (tree
, tree
, tree
, tree
, int, int, int,
137 gcov_type
, gcov_type
, gcov_type
);
138 static bool tree_divmod_fixed_value_transform (tree
);
139 static bool tree_mod_pow2_value_transform (tree
);
140 static bool tree_mod_subtract_transform (tree
);
143 /* Find values inside INSN for that we want to measure histograms for
144 division/modulo optimization and stores them to VALUES. */
146 rtl_divmod_values_to_profile (rtx insn
, histogram_values
*values
)
148 rtx set
, set_src
, op1
, op2
;
149 enum machine_mode mode
;
150 histogram_value hist
;
155 set
= single_set (insn
);
159 mode
= GET_MODE (SET_DEST (set
));
160 if (!INTEGRAL_MODE_P (mode
))
163 set_src
= SET_SRC (set
);
164 switch (GET_CODE (set_src
))
170 op1
= XEXP (set_src
, 0);
171 op2
= XEXP (set_src
, 1);
172 if (side_effects_p (op2
))
175 /* Check for a special case where the divisor is power of 2. */
176 if ((GET_CODE (set_src
) == UMOD
) && !CONSTANT_P (op2
))
178 hist
= ggc_alloc (sizeof (*hist
));
179 hist
->hvalue
.rtl
.value
= op2
;
180 hist
->hvalue
.rtl
.seq
= NULL_RTX
;
181 hist
->hvalue
.rtl
.mode
= mode
;
182 hist
->hvalue
.rtl
.insn
= insn
;
183 hist
->type
= HIST_TYPE_POW2
;
184 hist
->hdata
.pow2
.may_be_other
= 1;
185 VEC_safe_push (histogram_value
, heap
, *values
, hist
);
188 /* Check whether the divisor is not in fact a constant. */
189 if (!CONSTANT_P (op2
))
191 hist
= ggc_alloc (sizeof (*hist
));
192 hist
->hvalue
.rtl
.value
= op2
;
193 hist
->hvalue
.rtl
.mode
= mode
;
194 hist
->hvalue
.rtl
.seq
= NULL_RTX
;
195 hist
->hvalue
.rtl
.insn
= insn
;
196 hist
->type
= HIST_TYPE_SINGLE_VALUE
;
197 VEC_safe_push (histogram_value
, heap
, *values
, hist
);
200 /* For mod, check whether it is not often a noop (or replaceable by
201 a few subtractions). */
202 if (GET_CODE (set_src
) == UMOD
&& !side_effects_p (op1
))
206 hist
= ggc_alloc (sizeof (*hist
));
208 tmp
= simplify_gen_binary (DIV
, mode
, copy_rtx (op1
), copy_rtx (op2
));
209 hist
->hvalue
.rtl
.value
= force_operand (tmp
, NULL_RTX
);
210 hist
->hvalue
.rtl
.seq
= get_insns ();
212 hist
->hvalue
.rtl
.mode
= mode
;
213 hist
->hvalue
.rtl
.insn
= insn
;
214 hist
->type
= HIST_TYPE_INTERVAL
;
215 hist
->hdata
.intvl
.int_start
= 0;
216 hist
->hdata
.intvl
.steps
= 2;
217 VEC_safe_push (histogram_value
, heap
, *values
, hist
);
228 /* Called from find_mem_reference through for_each_rtx, finds a memory
229 reference. I.e. if *EXPR is a MEM, the reference to this MEM is stored
230 to *RET and the traversing of the expression is interrupted by returning 1.
231 Otherwise 0 is returned. */
234 find_mem_reference_1 (rtx
*expr
, void *ret
)
238 if (GET_CODE (*expr
) == MEM
)
246 /* Called form find_mem_reference through note_stores to find out whether
247 the memory reference MEM is a store. I.e. if EXPR == MEM, the variable
248 FMR2_WRITE is set to true. */
250 static int fmr2_write
;
252 find_mem_reference_2 (rtx expr
, rtx pat ATTRIBUTE_UNUSED
, void *mem
)
258 /* Find a memory reference inside INSN, return it in MEM. Set WRITE to true
259 if it is a write of the mem. Return false if no memory reference is found,
263 find_mem_reference (rtx insn
, rtx
*mem
, int *write
)
266 for_each_rtx (&PATTERN (insn
), find_mem_reference_1
, mem
);
272 note_stores (PATTERN (insn
), find_mem_reference_2
, *mem
);
277 /* Find values inside INSN for that we want to measure histograms for
278 a speculative prefetching. Add them to the list VALUES.
279 Returns true if such we found any such value, false otherwise. */
282 insn_prefetch_values_to_profile (rtx insn
, histogram_values
* values
)
286 histogram_value hist
;
288 /* It only makes sense to look for memory references in ordinary insns. */
289 if (GET_CODE (insn
) != INSN
)
292 if (!find_mem_reference (insn
, &mem
, &write
))
295 address
= XEXP (mem
, 0);
296 if (side_effects_p (address
))
299 if (CONSTANT_P (address
))
302 hist
= ggc_alloc (sizeof (*hist
));
303 hist
->hvalue
.rtl
.value
= address
;
304 hist
->hvalue
.rtl
.mode
= GET_MODE (address
);
305 hist
->hvalue
.rtl
.seq
= NULL_RTX
;
306 hist
->hvalue
.rtl
.insn
= insn
;
307 hist
->type
= HIST_TYPE_CONST_DELTA
;
308 VEC_safe_push (histogram_value
, heap
, *values
, hist
);
313 /* Find values inside INSN for that we want to measure histograms and adds
314 them to list VALUES (increasing the record of its length in N_VALUES). */
316 rtl_values_to_profile (rtx insn
, histogram_values
*values
)
318 if (flag_value_profile_transformations
)
319 rtl_divmod_values_to_profile (insn
, values
);
322 if (flag_speculative_prefetching
)
323 insn_prefetch_values_to_profile (insn
, values
);
327 /* Find list of values for that we want to measure histograms. */
329 rtl_find_values_to_profile (histogram_values
*values
)
332 unsigned i
, libcall_level
;
333 histogram_value hist
;
335 life_analysis (NULL
, PROP_DEATH_NOTES
);
339 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
340 rtl_values_to_profile (insn
, values
);
341 static_values
= *values
;
343 for (i
= 0; VEC_iterate (histogram_value
, *values
, i
, hist
); i
++)
347 case HIST_TYPE_INTERVAL
:
350 "Interval counter for insn %d, range %d -- %d.\n",
351 INSN_UID ((rtx
)hist
->hvalue
.rtl
.insn
),
352 hist
->hdata
.intvl
.int_start
,
353 (hist
->hdata
.intvl
.int_start
354 + hist
->hdata
.intvl
.steps
- 1));
355 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
361 "Pow2 counter for insn %d.\n",
362 INSN_UID ((rtx
)hist
->hvalue
.rtl
.insn
));
364 = GET_MODE_BITSIZE (hist
->hvalue
.rtl
.mode
)
365 + (hist
->hdata
.pow2
.may_be_other
? 1 : 0);
368 case HIST_TYPE_SINGLE_VALUE
:
371 "Single value counter for insn %d.\n",
372 INSN_UID ((rtx
)hist
->hvalue
.rtl
.insn
));
373 hist
->n_counters
= 3;
376 case HIST_TYPE_CONST_DELTA
:
379 "Constant delta counter for insn %d.\n",
380 INSN_UID ((rtx
)hist
->hvalue
.rtl
.insn
));
381 hist
->n_counters
= 4;
388 allocate_reg_info (max_reg_num (), FALSE
, FALSE
);
391 /* Main entry point. Finds REG_VALUE_PROFILE notes from profiler and uses
392 them to identify and exploit properties of values that are hard to analyze
395 We do following transformations:
401 where b is almost always a constant N is transformed to
414 where b is almost always a power of 2 and the division is unsigned
415 TODO -- handle signed case as well
417 if ((b & (b - 1)) == 0)
422 Note that when b = 0, no error will occur and x = a; this is correct,
423 as result of such operation is undefined.
429 where a is almost always less then b and the division is unsigned
430 TODO -- handle signed case as well
440 where a is almost always less then 2 * b and the division is unsigned
441 TODO -- handle signed case as well
449 It would be possible to continue analogically for K * b for other small
450 K's, but it is probably not useful.
454 Read or write of mem[address], where the value of address changes usually
455 by a constant C != 0 between the following accesses to the computation; with
456 -fspeculative-prefetching we then add a prefetch of address + C before
457 the insn. This handles prefetching of several interesting cases in addition
458 to a simple prefetching for addresses that are induction variables, e. g.
459 linked lists allocated sequentially (even in case they are processed
462 TODO -- we should also check whether there is not (usually) a small
463 difference with the adjacent memory references, so that we do
464 not issue overlapping prefetches. Also we should employ some
465 heuristics to eliminate cases where prefetching evidently spoils
467 -- it should somehow cooperate with the loop optimizer prefetching
471 There are other useful cases that could be handled by a similar mechanism,
474 for (i = 0; i < n; i++)
477 transform to (for constant N):
480 for (i = 0; i < N; i++)
483 for (i = 0; i < n; i++)
485 making unroller happy. Since this may grow the code significantly,
486 we would have to be very careful here. */
489 rtl_value_profile_transformations (void)
494 for (insn
= get_insns (); insn
; insn
= next
)
496 next
= NEXT_INSN (insn
);
501 /* Scan for insn carrying a histogram. */
502 if (!find_reg_note (insn
, REG_VALUE_PROFILE
, 0))
505 /* Ignore cold areas -- we are growing a code. */
506 if (!maybe_hot_bb_p (BLOCK_FOR_INSN (insn
)))
511 fprintf (dump_file
, "Trying transformations on insn %d\n",
513 print_rtl_single (dump_file
, insn
);
516 /* Transformations: */
517 if (flag_value_profile_transformations
518 && (rtl_mod_subtract_transform (insn
)
519 || rtl_divmod_fixed_value_transform (insn
)
520 || rtl_mod_pow2_value_transform (insn
)))
523 if (flag_speculative_prefetching
524 && speculative_prefetching_transform (insn
))
531 commit_edge_insertions ();
532 allocate_reg_info (max_reg_num (), FALSE
, FALSE
);
538 /* Generate code for transformation 1 (with MODE and OPERATION, operands OP1
539 and OP2, whose value is expected to be VALUE, result TARGET and
540 probability of taking the optimal path PROB). */
542 rtl_divmod_fixed_value (enum machine_mode mode
, enum rtx_code operation
,
543 rtx target
, rtx op1
, rtx op2
, gcov_type value
,
547 rtx neq_label
= gen_label_rtx ();
548 rtx end_label
= gen_label_rtx ();
555 tmp
= gen_reg_rtx (mode
);
556 emit_move_insn (tmp
, copy_rtx (op2
));
561 do_compare_rtx_and_jump (tmp
, GEN_INT (value
), NE
, 0, mode
, NULL_RTX
,
562 NULL_RTX
, neq_label
);
564 /* Add branch probability to jump we just created. */
565 jump
= get_last_insn ();
566 REG_NOTES (jump
) = gen_rtx_EXPR_LIST (REG_BR_PROB
,
567 GEN_INT (REG_BR_PROB_BASE
- prob
),
570 tmp1
= simplify_gen_binary (operation
, mode
,
571 copy_rtx (op1
), GEN_INT (value
));
572 tmp1
= force_operand (tmp1
, target
);
574 emit_move_insn (copy_rtx (target
), copy_rtx (tmp1
));
576 emit_jump_insn (gen_jump (end_label
));
579 emit_label (neq_label
);
580 tmp1
= simplify_gen_binary (operation
, mode
,
581 copy_rtx (op1
), copy_rtx (tmp
));
582 tmp1
= force_operand (tmp1
, target
);
584 emit_move_insn (copy_rtx (target
), copy_rtx (tmp1
));
586 emit_label (end_label
);
588 sequence
= get_insns ();
590 rebuild_jump_labels (sequence
);
594 /* Do transform 1) on INSN if applicable. */
596 rtl_divmod_fixed_value_transform (rtx insn
)
598 rtx set
, set_src
, set_dest
, op1
, op2
, value
, histogram
;
600 enum machine_mode mode
;
601 gcov_type val
, count
, all
;
605 set
= single_set (insn
);
609 set_src
= SET_SRC (set
);
610 set_dest
= SET_DEST (set
);
611 code
= GET_CODE (set_src
);
612 mode
= GET_MODE (set_dest
);
614 if (code
!= DIV
&& code
!= MOD
&& code
!= UDIV
&& code
!= UMOD
)
616 op1
= XEXP (set_src
, false);
617 op2
= XEXP (set_src
, 1);
619 for (histogram
= REG_NOTES (insn
);
621 histogram
= XEXP (histogram
, 1))
622 if (REG_NOTE_KIND (histogram
) == REG_VALUE_PROFILE
623 && XEXP (XEXP (histogram
, 0), 0) == GEN_INT (HIST_TYPE_SINGLE_VALUE
))
629 histogram
= XEXP (XEXP (histogram
, 0), 1);
630 value
= XEXP (histogram
, 0);
631 histogram
= XEXP (histogram
, 1);
632 val
= INTVAL (XEXP (histogram
, 0));
633 histogram
= XEXP (histogram
, 1);
634 count
= INTVAL (XEXP (histogram
, 0));
635 histogram
= XEXP (histogram
, 1);
636 all
= INTVAL (XEXP (histogram
, 0));
638 /* We require that count be at least half of all; this means
639 that for the transformation to fire the value must be constant
640 at least 50% of time (and 75% gives the guarantee of usage). */
641 if (!rtx_equal_p (op2
, value
) || 2 * count
< all
)
645 fprintf (dump_file
, "Div/mod by constant transformation on insn %d\n",
648 /* Compute probability of taking the optimal path. */
649 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
651 e
= split_block (BLOCK_FOR_INSN (insn
), PREV_INSN (insn
));
654 insert_insn_on_edge (
655 rtl_divmod_fixed_value (mode
, code
, set_dest
,
656 op1
, op2
, val
, prob
), e
);
661 /* Generate code for transformation 2 (with MODE and OPERATION, operands OP1
662 and OP2, result TARGET and probability of taking the optimal path PROB). */
664 rtl_mod_pow2 (enum machine_mode mode
, enum rtx_code operation
, rtx target
,
665 rtx op1
, rtx op2
, int prob
)
667 rtx tmp
, tmp1
, tmp2
, tmp3
, jump
;
668 rtx neq_label
= gen_label_rtx ();
669 rtx end_label
= gen_label_rtx ();
676 tmp
= gen_reg_rtx (mode
);
677 emit_move_insn (tmp
, copy_rtx (op2
));
682 tmp1
= expand_simple_binop (mode
, PLUS
, tmp
, constm1_rtx
, NULL_RTX
,
684 tmp2
= expand_simple_binop (mode
, AND
, tmp
, tmp1
, NULL_RTX
,
686 do_compare_rtx_and_jump (tmp2
, const0_rtx
, NE
, 0, mode
, NULL_RTX
,
687 NULL_RTX
, neq_label
);
689 /* Add branch probability to jump we just created. */
690 jump
= get_last_insn ();
691 REG_NOTES (jump
) = gen_rtx_EXPR_LIST (REG_BR_PROB
,
692 GEN_INT (REG_BR_PROB_BASE
- prob
),
695 tmp3
= expand_simple_binop (mode
, AND
, op1
, tmp1
, target
,
698 emit_move_insn (copy_rtx (target
), tmp3
);
699 emit_jump_insn (gen_jump (end_label
));
702 emit_label (neq_label
);
703 tmp1
= simplify_gen_binary (operation
, mode
, copy_rtx (op1
), copy_rtx (tmp
));
704 tmp1
= force_operand (tmp1
, target
);
706 emit_move_insn (target
, tmp1
);
708 emit_label (end_label
);
710 sequence
= get_insns ();
712 rebuild_jump_labels (sequence
);
716 /* Do transform 2) on INSN if applicable. */
718 rtl_mod_pow2_value_transform (rtx insn
)
720 rtx set
, set_src
, set_dest
, op1
, op2
, value
, histogram
;
722 enum machine_mode mode
;
723 gcov_type wrong_values
, count
;
727 set
= single_set (insn
);
731 set_src
= SET_SRC (set
);
732 set_dest
= SET_DEST (set
);
733 code
= GET_CODE (set_src
);
734 mode
= GET_MODE (set_dest
);
738 op1
= XEXP (set_src
, 0);
739 op2
= XEXP (set_src
, 1);
741 for (histogram
= REG_NOTES (insn
);
743 histogram
= XEXP (histogram
, 1))
744 if (REG_NOTE_KIND (histogram
) == REG_VALUE_PROFILE
745 && XEXP (XEXP (histogram
, 0), 0) == GEN_INT (HIST_TYPE_POW2
))
751 histogram
= XEXP (XEXP (histogram
, 0), 1);
752 value
= XEXP (histogram
, 0);
753 histogram
= XEXP (histogram
, 1);
754 wrong_values
=INTVAL (XEXP (histogram
, 0));
755 histogram
= XEXP (histogram
, 1);
758 for (i
= 0; i
< GET_MODE_BITSIZE (mode
); i
++)
760 count
+= INTVAL (XEXP (histogram
, 0));
761 histogram
= XEXP (histogram
, 1);
764 if (!rtx_equal_p (op2
, value
))
767 /* We require that we hit a power of two at least half of all evaluations. */
768 if (count
< wrong_values
)
772 fprintf (dump_file
, "Mod power of 2 transformation on insn %d\n",
775 /* Compute probability of taking the optimal path. */
776 all
= count
+ wrong_values
;
777 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
779 e
= split_block (BLOCK_FOR_INSN (insn
), PREV_INSN (insn
));
782 insert_insn_on_edge (
783 rtl_mod_pow2 (mode
, code
, set_dest
, op1
, op2
, prob
), e
);
788 /* Generate code for transformations 3 and 4 (with MODE and OPERATION,
789 operands OP1 and OP2, result TARGET, at most SUB subtractions, and
790 probability of taking the optimal path(s) PROB1 and PROB2). */
792 rtl_mod_subtract (enum machine_mode mode
, enum rtx_code operation
,
793 rtx target
, rtx op1
, rtx op2
, int sub
, int prob1
, int prob2
)
796 rtx end_label
= gen_label_rtx ();
804 tmp
= gen_reg_rtx (mode
);
805 emit_move_insn (tmp
, copy_rtx (op2
));
810 emit_move_insn (target
, copy_rtx (op1
));
811 do_compare_rtx_and_jump (target
, tmp
, LTU
, 0, mode
, NULL_RTX
,
812 NULL_RTX
, end_label
);
814 /* Add branch probability to jump we just created. */
815 jump
= get_last_insn ();
816 REG_NOTES (jump
) = gen_rtx_EXPR_LIST (REG_BR_PROB
,
817 GEN_INT (prob1
), REG_NOTES (jump
));
819 for (i
= 0; i
< sub
; i
++)
821 tmp1
= expand_simple_binop (mode
, MINUS
, target
, tmp
, target
,
824 emit_move_insn (target
, tmp1
);
825 do_compare_rtx_and_jump (target
, tmp
, LTU
, 0, mode
, NULL_RTX
,
826 NULL_RTX
, end_label
);
828 /* Add branch probability to jump we just created. */
829 jump
= get_last_insn ();
830 REG_NOTES (jump
) = gen_rtx_EXPR_LIST (REG_BR_PROB
,
831 GEN_INT (prob2
), REG_NOTES (jump
));
834 tmp1
= simplify_gen_binary (operation
, mode
, copy_rtx (target
), copy_rtx (tmp
));
835 tmp1
= force_operand (tmp1
, target
);
837 emit_move_insn (target
, tmp1
);
839 emit_label (end_label
);
841 sequence
= get_insns ();
843 rebuild_jump_labels (sequence
);
847 /* Do transforms 3) and 4) on INSN if applicable. */
849 rtl_mod_subtract_transform (rtx insn
)
851 rtx set
, set_src
, set_dest
, op1
, op2
, histogram
;
853 enum machine_mode mode
;
854 gcov_type wrong_values
, counts
[2], count
, all
;
858 set
= single_set (insn
);
862 set_src
= SET_SRC (set
);
863 set_dest
= SET_DEST (set
);
864 code
= GET_CODE (set_src
);
865 mode
= GET_MODE (set_dest
);
869 op1
= XEXP (set_src
, 0);
870 op2
= XEXP (set_src
, 1);
872 for (histogram
= REG_NOTES (insn
);
874 histogram
= XEXP (histogram
, 1))
875 if (REG_NOTE_KIND (histogram
) == REG_VALUE_PROFILE
876 && XEXP (XEXP (histogram
, 0), 0) == GEN_INT (HIST_TYPE_INTERVAL
))
882 histogram
= XEXP (XEXP (histogram
, 0), 1);
883 histogram
= XEXP (histogram
, 1);
886 for (i
= 0; i
< 2; i
++)
888 counts
[i
] = INTVAL (XEXP (histogram
, 0));
890 histogram
= XEXP (histogram
, 1);
892 wrong_values
= INTVAL (XEXP (histogram
, 0));
893 histogram
= XEXP (histogram
, 1);
894 wrong_values
+= INTVAL (XEXP (histogram
, 0));
897 /* We require that we use just subtractions in at least 50% of all
900 for (i
= 0; i
< 2; i
++)
903 if (count
* 2 >= all
)
911 fprintf (dump_file
, "Mod subtract transformation on insn %d\n",
914 /* Compute probability of taking the optimal path(s). */
915 prob1
= (counts
[0] * REG_BR_PROB_BASE
+ all
/ 2) / all
;
916 prob2
= (counts
[1] * REG_BR_PROB_BASE
+ all
/ 2) / all
;
918 e
= split_block (BLOCK_FOR_INSN (insn
), PREV_INSN (insn
));
921 insert_insn_on_edge (
922 rtl_mod_subtract (mode
, code
, set_dest
,
923 op1
, op2
, i
, prob1
, prob2
), e
);
929 /* Generate code for transformation 5 for mem with ADDRESS and a constant
930 step DELTA. WRITE is true if the reference is a store to mem. */
933 gen_speculative_prefetch (rtx address
, gcov_type delta
, int write
)
938 /* TODO: we do the prefetching for just one iteration ahead, which
939 often is not enough. */
941 if (offsettable_address_p (0, VOIDmode
, address
))
942 tmp
= plus_constant (copy_rtx (address
), delta
);
945 tmp
= simplify_gen_binary (PLUS
, Pmode
,
946 copy_rtx (address
), GEN_INT (delta
));
947 tmp
= force_operand (tmp
, NULL
);
949 if (! (*insn_data
[(int)CODE_FOR_prefetch
].operand
[0].predicate
)
950 (tmp
, insn_data
[(int)CODE_FOR_prefetch
].operand
[0].mode
))
951 tmp
= force_reg (Pmode
, tmp
);
952 emit_insn (gen_prefetch (tmp
, GEN_INT (write
), GEN_INT (3)));
953 sequence
= get_insns ();
959 /* Do transform 5) on INSN if applicable. */
962 speculative_prefetching_transform (rtx insn
)
964 rtx histogram
, value
;
965 gcov_type val
, count
, all
;
970 if (!maybe_hot_bb_p (BLOCK_FOR_INSN (insn
)))
973 if (!find_mem_reference (insn
, &mem
, &write
))
976 address
= XEXP (mem
, 0);
977 if (side_effects_p (address
))
980 if (CONSTANT_P (address
))
983 for (histogram
= REG_NOTES (insn
);
985 histogram
= XEXP (histogram
, 1))
986 if (REG_NOTE_KIND (histogram
) == REG_VALUE_PROFILE
987 && XEXP (XEXP (histogram
, 0), 0) == GEN_INT (HIST_TYPE_CONST_DELTA
))
993 histogram
= XEXP (XEXP (histogram
, 0), 1);
994 value
= XEXP (histogram
, 0);
995 histogram
= XEXP (histogram
, 1);
996 /* Skip last value referenced. */
997 histogram
= XEXP (histogram
, 1);
998 val
= INTVAL (XEXP (histogram
, 0));
999 histogram
= XEXP (histogram
, 1);
1000 count
= INTVAL (XEXP (histogram
, 0));
1001 histogram
= XEXP (histogram
, 1);
1002 all
= INTVAL (XEXP (histogram
, 0));
1004 /* With that few executions we do not really have a reason to optimize the
1005 statement, and more importantly, the data about differences of addresses
1006 are spoiled by the first item that had no previous value to compare
1011 /* We require that count be at least half of all; this means
1012 that for the transformation to fire the value must be constant
1013 at least 50% of time (and 75% gives the guarantee of usage). */
1014 if (!rtx_equal_p (address
, value
) || 2 * count
< all
)
1017 /* If the difference is too small, it does not make too much sense to
1018 prefetch, as the memory is probably already in cache. */
1019 if (val
>= NOPREFETCH_RANGE_MIN
&& val
<= NOPREFETCH_RANGE_MAX
)
1023 fprintf (dump_file
, "Speculative prefetching for insn %d\n",
1026 e
= split_block (BLOCK_FOR_INSN (insn
), PREV_INSN (insn
));
1028 insert_insn_on_edge (gen_speculative_prefetch (address
, val
, write
), e
);
1032 #endif /* HAVE_prefetch */
1034 /* Tree based transformations. */
1036 tree_value_profile_transformations (void)
1039 block_stmt_iterator bsi
;
1040 bool changed
= false;
1044 /* Ignore cold areas -- we are enlarging the code. */
1045 if (!maybe_hot_bb_p (bb
))
1048 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1050 tree stmt
= bsi_stmt (bsi
);
1051 stmt_ann_t ann
= get_stmt_ann (stmt
);
1052 histogram_value th
= ann
->histograms
;
1058 fprintf (dump_file
, "Trying transformations on insn ");
1059 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1062 /* Transformations: */
1063 /* The order of things in this conditional controls which
1064 transformation is used when more than one is applicable. */
1065 /* It is expected that any code added by the transformations
1066 will be added before the current statement, and that the
1067 current statement remain valid (although possibly
1068 modified) upon return. */
1069 if (flag_value_profile_transformations
1070 && (tree_mod_subtract_transform (stmt
)
1071 || tree_divmod_fixed_value_transform (stmt
)
1072 || tree_mod_pow2_value_transform (stmt
)))
1075 /* Original statement may no longer be in the same block. */
1076 bb
= bb_for_stmt (stmt
);
1079 /* Free extra storage from compute_value_histograms. */
1082 free (th
->hvalue
.tree
.counters
);
1083 th
= th
->hvalue
.tree
.next
;
1085 ann
->histograms
= 0;
1097 /* Generate code for transformation 1 (with OPERATION, operands OP1
1098 and OP2, whose value is expected to be VALUE, parent modify-expr STMT and
1099 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
1100 within roundoff error). This generates the result into a temp and returns
1101 the temp; it does not replace or alter the original STMT. */
1103 tree_divmod_fixed_value (tree stmt
, tree operation
,
1104 tree op1
, tree op2
, tree value
, int prob
, gcov_type count
,
1107 tree stmt1
, stmt2
, stmt3
;
1108 tree tmp1
, tmp2
, tmpv
;
1109 tree label_decl1
= create_artificial_label ();
1110 tree label_decl2
= create_artificial_label ();
1111 tree label_decl3
= create_artificial_label ();
1112 tree label1
, label2
, label3
;
1113 tree bb1end
, bb2end
, bb3end
;
1114 basic_block bb
, bb2
, bb3
, bb4
;
1115 tree optype
= TREE_TYPE (operation
);
1116 edge e12
, e13
, e23
, e24
, e34
;
1117 block_stmt_iterator bsi
;
1119 bb
= bb_for_stmt (stmt
);
1120 bsi
= bsi_for_stmt (stmt
);
1122 tmpv
= create_tmp_var (optype
, "PROF");
1123 tmp1
= create_tmp_var (optype
, "PROF");
1124 stmt1
= build2 (MODIFY_EXPR
, optype
, tmpv
, fold_convert (optype
, value
));
1125 stmt2
= build2 (MODIFY_EXPR
, optype
, tmp1
, op2
);
1126 stmt3
= build3 (COND_EXPR
, void_type_node
,
1127 build2 (NE_EXPR
, boolean_type_node
, tmp1
, tmpv
),
1128 build1 (GOTO_EXPR
, void_type_node
, label_decl2
),
1129 build1 (GOTO_EXPR
, void_type_node
, label_decl1
));
1130 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1131 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
1132 bsi_insert_before (&bsi
, stmt3
, BSI_SAME_STMT
);
1135 tmp2
= create_tmp_var (optype
, "PROF");
1136 label1
= build1 (LABEL_EXPR
, void_type_node
, label_decl1
);
1137 stmt1
= build2 (MODIFY_EXPR
, optype
, tmp2
,
1138 build2 (TREE_CODE (operation
), optype
, op1
, tmpv
));
1139 bsi_insert_before (&bsi
, label1
, BSI_SAME_STMT
);
1140 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1143 label2
= build1 (LABEL_EXPR
, void_type_node
, label_decl2
);
1144 stmt1
= build2 (MODIFY_EXPR
, optype
, tmp2
,
1145 build2 (TREE_CODE (operation
), optype
, op1
, op2
));
1146 bsi_insert_before (&bsi
, label2
, BSI_SAME_STMT
);
1147 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1150 label3
= build1 (LABEL_EXPR
, void_type_node
, label_decl3
);
1151 bsi_insert_before (&bsi
, label3
, BSI_SAME_STMT
);
1154 /* Edge e23 connects bb2 to bb3, etc. */
1155 e12
= split_block (bb
, bb1end
);
1158 e23
= split_block (bb2
, bb2end
);
1160 bb3
->count
= all
- count
;
1161 e34
= split_block (bb3
, bb3end
);
1165 e12
->flags
&= ~EDGE_FALLTHRU
;
1166 e12
->flags
|= EDGE_FALSE_VALUE
;
1167 e12
->probability
= prob
;
1170 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
1171 e13
->probability
= REG_BR_PROB_BASE
- prob
;
1172 e13
->count
= all
- count
;
1176 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
1177 e24
->probability
= REG_BR_PROB_BASE
;
1180 e34
->probability
= REG_BR_PROB_BASE
;
1181 e34
->count
= all
- count
;
1186 /* Do transform 1) on INSN if applicable. */
1188 tree_divmod_fixed_value_transform (tree stmt
)
1190 stmt_ann_t ann
= get_stmt_ann (stmt
);
1191 histogram_value histogram
;
1192 enum tree_code code
;
1193 gcov_type val
, count
, all
;
1194 tree modify
, op
, op1
, op2
, result
, value
, tree_val
;
1198 if (TREE_CODE (stmt
) == RETURN_EXPR
1199 && TREE_OPERAND (stmt
, 0)
1200 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == MODIFY_EXPR
)
1201 modify
= TREE_OPERAND (stmt
, 0);
1202 if (TREE_CODE (modify
) != MODIFY_EXPR
)
1204 op
= TREE_OPERAND (modify
, 1);
1205 if (!INTEGRAL_TYPE_P (TREE_TYPE (op
)))
1207 code
= TREE_CODE (op
);
1209 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
1212 op1
= TREE_OPERAND (op
, 0);
1213 op2
= TREE_OPERAND (op
, 1);
1214 if (!ann
->histograms
)
1217 for (histogram
= ann
->histograms
; histogram
; histogram
= histogram
->hvalue
.tree
.next
)
1218 if (histogram
->type
== HIST_TYPE_SINGLE_VALUE
)
1224 value
= histogram
->hvalue
.tree
.value
;
1225 val
= histogram
->hvalue
.tree
.counters
[0];
1226 count
= histogram
->hvalue
.tree
.counters
[1];
1227 all
= histogram
->hvalue
.tree
.counters
[2];
1229 /* We require that count is at least half of all; this means
1230 that for the transformation to fire the value must be constant
1231 at least 50% of time (and 75% gives the guarantee of usage). */
1232 if (simple_cst_equal (op2
, value
) != 1 || 2 * count
< all
)
1237 fprintf (dump_file
, "Div/mod by constant transformation on insn ");
1238 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1241 /* Compute probability of taking the optimal path. */
1242 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1244 tree_val
= build_int_cst_wide (get_gcov_type (),
1245 (unsigned HOST_WIDE_INT
) val
,
1246 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
1247 result
= tree_divmod_fixed_value (stmt
, op
, op1
, op2
, tree_val
, prob
, count
, all
);
1249 TREE_OPERAND (modify
, 1) = result
;
1254 /* Generate code for transformation 2 (with OPERATION, operands OP1
1255 and OP2, parent modify-expr STMT and probability of taking the optimal
1256 path PROB, which is equivalent to COUNT/ALL within roundoff error).
1257 This generates the result into a temp and returns
1258 the temp; it does not replace or alter the original STMT. */
1260 tree_mod_pow2 (tree stmt
, tree operation
, tree op1
, tree op2
, int prob
,
1261 gcov_type count
, gcov_type all
)
1263 tree stmt1
, stmt2
, stmt3
, stmt4
;
1264 tree tmp1
, tmp2
, tmp3
;
1265 tree label_decl1
= create_artificial_label ();
1266 tree label_decl2
= create_artificial_label ();
1267 tree label_decl3
= create_artificial_label ();
1268 tree label1
, label2
, label3
;
1269 tree bb1end
, bb2end
, bb3end
;
1270 basic_block bb
, bb2
, bb3
, bb4
;
1271 tree optype
= TREE_TYPE (operation
);
1272 edge e12
, e13
, e23
, e24
, e34
;
1273 block_stmt_iterator bsi
;
1274 tree result
= create_tmp_var (optype
, "PROF");
1276 bb
= bb_for_stmt (stmt
);
1277 bsi
= bsi_for_stmt (stmt
);
1279 tmp1
= create_tmp_var (optype
, "PROF");
1280 tmp2
= create_tmp_var (optype
, "PROF");
1281 tmp3
= create_tmp_var (optype
, "PROF");
1282 stmt1
= build2 (MODIFY_EXPR
, optype
, tmp1
, fold_convert (optype
, op2
));
1283 stmt2
= build2 (MODIFY_EXPR
, optype
, tmp2
,
1284 build2 (PLUS_EXPR
, optype
, op2
, integer_minus_one_node
));
1285 stmt3
= build2 (MODIFY_EXPR
, optype
, tmp3
,
1286 build2 (BIT_AND_EXPR
, optype
, tmp2
, tmp1
));
1287 stmt4
= build3 (COND_EXPR
, void_type_node
,
1288 build2 (NE_EXPR
, boolean_type_node
, tmp3
, integer_zero_node
),
1289 build1 (GOTO_EXPR
, void_type_node
, label_decl2
),
1290 build1 (GOTO_EXPR
, void_type_node
, label_decl1
));
1291 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1292 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
1293 bsi_insert_before (&bsi
, stmt3
, BSI_SAME_STMT
);
1294 bsi_insert_before (&bsi
, stmt4
, BSI_SAME_STMT
);
1297 /* tmp2 == op2-1 inherited from previous block */
1298 label1
= build1 (LABEL_EXPR
, void_type_node
, label_decl1
);
1299 stmt1
= build2 (MODIFY_EXPR
, optype
, result
,
1300 build2 (BIT_AND_EXPR
, optype
, op1
, tmp2
));
1301 bsi_insert_before (&bsi
, label1
, BSI_SAME_STMT
);
1302 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1305 label2
= build1 (LABEL_EXPR
, void_type_node
, label_decl2
);
1306 stmt1
= build2 (MODIFY_EXPR
, optype
, result
,
1307 build2 (TREE_CODE (operation
), optype
, op1
, op2
));
1308 bsi_insert_before (&bsi
, label2
, BSI_SAME_STMT
);
1309 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1312 label3
= build1 (LABEL_EXPR
, void_type_node
, label_decl3
);
1313 bsi_insert_before (&bsi
, label3
, BSI_SAME_STMT
);
1316 /* Edge e23 connects bb2 to bb3, etc. */
1317 e12
= split_block (bb
, bb1end
);
1320 e23
= split_block (bb2
, bb2end
);
1322 bb3
->count
= all
- count
;
1323 e34
= split_block (bb3
, bb3end
);
1327 e12
->flags
&= ~EDGE_FALLTHRU
;
1328 e12
->flags
|= EDGE_FALSE_VALUE
;
1329 e12
->probability
= prob
;
1332 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
1333 e13
->probability
= REG_BR_PROB_BASE
- prob
;
1334 e13
->count
= all
- count
;
1338 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
1339 e24
->probability
= REG_BR_PROB_BASE
;
1342 e34
->probability
= REG_BR_PROB_BASE
;
1343 e34
->count
= all
- count
;
1348 /* Do transform 2) on INSN if applicable. */
1350 tree_mod_pow2_value_transform (tree stmt
)
1352 stmt_ann_t ann
= get_stmt_ann (stmt
);
1353 histogram_value histogram
;
1354 enum tree_code code
;
1355 gcov_type count
, wrong_values
, all
;
1356 tree modify
, op
, op1
, op2
, result
, value
;
1361 if (TREE_CODE (stmt
) == RETURN_EXPR
1362 && TREE_OPERAND (stmt
, 0)
1363 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == MODIFY_EXPR
)
1364 modify
= TREE_OPERAND (stmt
, 0);
1365 if (TREE_CODE (modify
) != MODIFY_EXPR
)
1367 op
= TREE_OPERAND (modify
, 1);
1368 if (!INTEGRAL_TYPE_P (TREE_TYPE (op
)))
1370 code
= TREE_CODE (op
);
1372 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (TREE_TYPE (op
)))
1375 op1
= TREE_OPERAND (op
, 0);
1376 op2
= TREE_OPERAND (op
, 1);
1377 if (!ann
->histograms
)
1380 for (histogram
= ann
->histograms
; histogram
; histogram
= histogram
->hvalue
.tree
.next
)
1381 if (histogram
->type
== HIST_TYPE_POW2
)
1387 value
= histogram
->hvalue
.tree
.value
;
1388 wrong_values
= histogram
->hvalue
.tree
.counters
[0];
1390 for (i
= 1; i
<= TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (stmt
))); i
++)
1391 count
+= histogram
->hvalue
.tree
.counters
[i
];
1393 /* We require that we hit a power of 2 at least half of all evaluations. */
1394 if (simple_cst_equal (op2
, value
) != 1 || count
< wrong_values
)
1399 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
1400 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1403 /* Compute probability of taking the optimal path. */
1404 all
= count
+ wrong_values
;
1405 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1407 result
= tree_mod_pow2 (stmt
, op
, op1
, op2
, prob
, count
, all
);
1409 TREE_OPERAND (modify
, 1) = result
;
1414 /* Generate code for transformations 3 and 4 (with OPERATION, operands OP1
1415 and OP2, parent modify-expr STMT, and NCOUNTS the number of cases to
1416 support. Currently only NCOUNTS==0 or 1 is supported and this is
1417 built into this interface. The probabilities of taking the optimal
1418 paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
1419 COUNT2/ALL respectively within roundoff error). This generates the
1420 result into a temp and returns the temp; it does not replace or alter
1421 the original STMT. */
1422 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
1425 tree_mod_subtract (tree stmt
, tree operation
, tree op1
, tree op2
,
1426 int prob1
, int prob2
, int ncounts
,
1427 gcov_type count1
, gcov_type count2
, gcov_type all
)
1429 tree stmt1
, stmt2
, stmt3
;
1431 tree label_decl1
= create_artificial_label ();
1432 tree label_decl2
= create_artificial_label ();
1433 tree label_decl3
= create_artificial_label ();
1434 tree label1
, label2
, label3
;
1435 tree bb1end
, bb2end
= NULL_TREE
, bb3end
;
1436 basic_block bb
, bb2
, bb3
, bb4
;
1437 tree optype
= TREE_TYPE (operation
);
1438 edge e12
, e23
= 0, e24
, e34
, e14
;
1439 block_stmt_iterator bsi
;
1440 tree result
= create_tmp_var (optype
, "PROF");
1442 bb
= bb_for_stmt (stmt
);
1443 bsi
= bsi_for_stmt (stmt
);
1445 tmp1
= create_tmp_var (optype
, "PROF");
1446 stmt1
= build2 (MODIFY_EXPR
, optype
, result
, op1
);
1447 stmt2
= build2 (MODIFY_EXPR
, optype
, tmp1
, op2
);
1448 stmt3
= build3 (COND_EXPR
, void_type_node
,
1449 build2 (LT_EXPR
, boolean_type_node
, result
, tmp1
),
1450 build1 (GOTO_EXPR
, void_type_node
, label_decl3
),
1451 build1 (GOTO_EXPR
, void_type_node
,
1452 ncounts
? label_decl1
: label_decl2
));
1453 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1454 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
1455 bsi_insert_before (&bsi
, stmt3
, BSI_SAME_STMT
);
1458 if (ncounts
) /* Assumed to be 0 or 1 */
1460 label1
= build1 (LABEL_EXPR
, void_type_node
, label_decl1
);
1461 stmt1
= build2 (MODIFY_EXPR
, optype
, result
,
1462 build2 (MINUS_EXPR
, optype
, result
, tmp1
));
1463 stmt2
= build3 (COND_EXPR
, void_type_node
,
1464 build2 (LT_EXPR
, boolean_type_node
, result
, tmp1
),
1465 build1 (GOTO_EXPR
, void_type_node
, label_decl3
),
1466 build1 (GOTO_EXPR
, void_type_node
, label_decl2
));
1467 bsi_insert_before (&bsi
, label1
, BSI_SAME_STMT
);
1468 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1469 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
1473 /* Fallback case. */
1474 label2
= build1 (LABEL_EXPR
, void_type_node
, label_decl2
);
1475 stmt1
= build2 (MODIFY_EXPR
, optype
, result
,
1476 build2 (TREE_CODE (operation
), optype
, result
, tmp1
));
1477 bsi_insert_before (&bsi
, label2
, BSI_SAME_STMT
);
1478 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1481 label3
= build1 (LABEL_EXPR
, void_type_node
, label_decl3
);
1482 bsi_insert_before (&bsi
, label3
, BSI_SAME_STMT
);
1485 /* Edge e23 connects bb2 to bb3, etc. */
1486 /* However block 3 is optional; if it is not there, references
1487 to 3 really refer to block 2. */
1488 e12
= split_block (bb
, bb1end
);
1490 bb2
->count
= all
- count1
;
1492 if (ncounts
) /* Assumed to be 0 or 1. */
1494 e23
= split_block (bb2
, bb2end
);
1496 bb3
->count
= all
- count1
- count2
;
1499 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1503 e12
->flags
&= ~EDGE_FALLTHRU
;
1504 e12
->flags
|= EDGE_FALSE_VALUE
;
1505 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
1506 e12
->count
= count1
;
1508 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1509 e14
->probability
= prob1
;
1510 e14
->count
= all
- count1
;
1512 if (ncounts
) /* Assumed to be 0 or 1. */
1514 e23
->flags
&= ~EDGE_FALLTHRU
;
1515 e23
->flags
|= EDGE_FALSE_VALUE
;
1516 e23
->count
= all
- count1
- count2
;
1517 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
1519 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1520 e24
->probability
= prob2
;
1521 e24
->count
= count2
;
1524 e34
->probability
= REG_BR_PROB_BASE
;
1525 e34
->count
= all
- count1
- count2
;
1530 /* Do transforms 3) and 4) on INSN if applicable. */
1532 tree_mod_subtract_transform (tree stmt
)
1534 stmt_ann_t ann
= get_stmt_ann (stmt
);
1535 histogram_value histogram
;
1536 enum tree_code code
;
1537 gcov_type count
, wrong_values
, all
;
1538 tree modify
, op
, op1
, op2
, result
, value
;
1543 if (TREE_CODE (stmt
) == RETURN_EXPR
1544 && TREE_OPERAND (stmt
, 0)
1545 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == MODIFY_EXPR
)
1546 modify
= TREE_OPERAND (stmt
, 0);
1547 if (TREE_CODE (modify
) != MODIFY_EXPR
)
1549 op
= TREE_OPERAND (modify
, 1);
1550 if (!INTEGRAL_TYPE_P (TREE_TYPE (op
)))
1552 code
= TREE_CODE (op
);
1554 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (TREE_TYPE (op
)))
1557 op1
= TREE_OPERAND (op
, 0);
1558 op2
= TREE_OPERAND (op
, 1);
1559 if (!ann
->histograms
)
1562 for (histogram
= ann
->histograms
; histogram
; histogram
= histogram
->hvalue
.tree
.next
)
1563 if (histogram
->type
== HIST_TYPE_INTERVAL
)
1569 value
= histogram
->hvalue
.tree
.value
;
1572 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1573 all
+= histogram
->hvalue
.tree
.counters
[i
];
1575 wrong_values
+= histogram
->hvalue
.tree
.counters
[i
];
1576 wrong_values
+= histogram
->hvalue
.tree
.counters
[i
+1];
1577 all
+= wrong_values
;
1580 if (simple_cst_equal (op2
, value
) != 1)
1583 /* We require that we use just subtractions in at least 50% of all
1586 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1588 count
+= histogram
->hvalue
.tree
.counters
[i
];
1589 if (count
* 2 >= all
)
1592 if (i
== histogram
->hdata
.intvl
.steps
)
1597 fprintf (dump_file
, "Mod subtract transformation on insn ");
1598 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1601 /* Compute probability of taking the optimal path(s). */
1602 prob1
= (histogram
->hvalue
.tree
.counters
[0] * REG_BR_PROB_BASE
+ all
/ 2) / all
;
1603 prob2
= (histogram
->hvalue
.tree
.counters
[1] * REG_BR_PROB_BASE
+ all
/ 2) / all
;
1605 /* In practice, "steps" is always 2. This interface reflects this,
1606 and will need to be changed if "steps" can change. */
1607 result
= tree_mod_subtract (stmt
, op
, op1
, op2
, prob1
, prob2
, i
,
1608 histogram
->hvalue
.tree
.counters
[0],
1609 histogram
->hvalue
.tree
.counters
[1], all
);
1611 TREE_OPERAND (modify
, 1) = result
;
1616 /* Connection to the outside world. */
1617 /* Struct for IR-dependent hooks. */
1618 struct value_prof_hooks
{
1619 /* Find list of values for which we want to measure histograms. */
1620 void (*find_values_to_profile
) (histogram_values
*);
1622 /* Identify and exploit properties of values that are hard to analyze
1623 statically. See value-prof.c for more detail. */
1624 bool (*value_profile_transformations
) (void);
1627 /* Hooks for RTL-based versions (the only ones that currently work). */
1628 static struct value_prof_hooks rtl_value_prof_hooks
=
1630 rtl_find_values_to_profile
,
1631 rtl_value_profile_transformations
1635 rtl_register_value_prof_hooks (void)
1637 value_prof_hooks
= &rtl_value_prof_hooks
;
1638 gcc_assert (!ir_type ());
1641 /* Find values inside INSN for that we want to measure histograms for
1642 division/modulo optimization. */
1644 tree_divmod_values_to_profile (tree stmt
, histogram_values
*values
)
1647 histogram_value hist
;
1650 if (TREE_CODE (stmt
) == RETURN_EXPR
1651 && TREE_OPERAND (stmt
, 0)
1652 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == MODIFY_EXPR
)
1653 op
= TREE_OPERAND (stmt
, 0);
1655 if (TREE_CODE (op
) != MODIFY_EXPR
)
1657 if (!INTEGRAL_TYPE_P (TREE_TYPE (op
)))
1659 op
= TREE_OPERAND (op
, 1);
1660 switch (TREE_CODE (op
))
1662 case TRUNC_DIV_EXPR
:
1663 case TRUNC_MOD_EXPR
:
1664 op1
= TREE_OPERAND (op
, 0);
1665 op2
= TREE_OPERAND (op
, 1);
1667 VEC_reserve (histogram_value
, heap
, *values
, 3);
1669 /* Check for a special case where the divisor is power(s) of 2.
1670 This is more aggressive than the RTL version, under the
1671 assumption that later phases will reduce / or % by power of 2
1672 to something clever most of the time. Signed or unsigned. */
1673 if (TREE_CODE (op2
) != INTEGER_CST
)
1675 hist
= ggc_alloc (sizeof (*hist
));
1676 hist
->hvalue
.tree
.value
= op2
;
1677 hist
->hvalue
.tree
.stmt
= stmt
;
1678 hist
->type
= HIST_TYPE_POW2
;
1679 hist
->hdata
.pow2
.may_be_other
= 1;
1680 VEC_quick_push (histogram_value
, *values
, hist
);
1683 /* Check for the case where the divisor is the same value most
1685 if (TREE_CODE (op2
) != INTEGER_CST
)
1687 hist
= ggc_alloc (sizeof (*hist
));
1688 hist
->hvalue
.tree
.value
= op2
;
1689 hist
->hvalue
.tree
.stmt
= stmt
;
1690 hist
->type
= HIST_TYPE_SINGLE_VALUE
;
1691 VEC_quick_push (histogram_value
, *values
, hist
);
1694 /* For mod, check whether it is not often a noop (or replaceable by
1695 a few subtractions). */
1696 if (TREE_CODE (op
) == TRUNC_MOD_EXPR
&& TYPE_UNSIGNED (TREE_TYPE (op
)))
1698 hist
= ggc_alloc (sizeof (*hist
));
1699 hist
->hvalue
.tree
.stmt
= stmt
;
1700 hist
->hvalue
.tree
.value
= op2
;
1701 hist
->type
= HIST_TYPE_INTERVAL
;
1702 hist
->hdata
.intvl
.int_start
= 0;
1703 hist
->hdata
.intvl
.steps
= 2;
1704 VEC_quick_push (histogram_value
, *values
, hist
);
1713 /* Find values inside INSN for that we want to measure histograms and adds
1714 them to list VALUES (increasing the record of its length in N_VALUES). */
1716 tree_values_to_profile (tree stmt
, histogram_values
*values
)
1718 if (flag_value_profile_transformations
)
1719 tree_divmod_values_to_profile (stmt
, values
);
1723 tree_find_values_to_profile (histogram_values
*values
)
1726 block_stmt_iterator bsi
;
1729 histogram_value hist
;
1733 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1735 tree stmt
= bsi_stmt (bsi
);
1736 tree_values_to_profile (stmt
, values
);
1738 static_values
= *values
;
1740 for (i
= 0; VEC_iterate (histogram_value
, *values
, i
, hist
); i
++)
1744 case HIST_TYPE_INTERVAL
:
1747 fprintf (dump_file
, "Interval counter for tree ");
1748 print_generic_expr (dump_file
, hist
->hvalue
.tree
.stmt
,
1750 fprintf (dump_file
, ", range %d -- %d.\n",
1751 hist
->hdata
.intvl
.int_start
,
1752 (hist
->hdata
.intvl
.int_start
1753 + hist
->hdata
.intvl
.steps
- 1));
1755 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1758 case HIST_TYPE_POW2
:
1761 fprintf (dump_file
, "Pow2 counter for insn ");
1762 print_generic_expr (dump_file
, hist
->hvalue
.tree
.stmt
, TDF_SLIM
);
1763 fprintf (dump_file
, ".\n");
1765 stmt
= hist
->hvalue
.tree
.stmt
;
1767 = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (stmt
)))
1768 + (hist
->hdata
.pow2
.may_be_other
? 1 : 0);
1771 case HIST_TYPE_SINGLE_VALUE
:
1774 fprintf (dump_file
, "Single value counter for insn ");
1775 print_generic_expr (dump_file
, hist
->hvalue
.tree
.stmt
, TDF_SLIM
);
1776 fprintf (dump_file
, ".\n");
1778 hist
->n_counters
= 3;
1781 case HIST_TYPE_CONST_DELTA
:
1784 fprintf (dump_file
, "Constant delta counter for insn ");
1785 print_generic_expr (dump_file
, hist
->hvalue
.tree
.stmt
, TDF_SLIM
);
1786 fprintf (dump_file
, ".\n");
1788 hist
->n_counters
= 4;
1797 static struct value_prof_hooks tree_value_prof_hooks
= {
1798 tree_find_values_to_profile
,
1799 tree_value_profile_transformations
1803 tree_register_value_prof_hooks (void)
1805 value_prof_hooks
= &tree_value_prof_hooks
;
1806 gcc_assert (ir_type ());
1809 /* IR-independent entry points. */
1811 find_values_to_profile (histogram_values
*values
)
1813 (value_prof_hooks
->find_values_to_profile
) (values
);
1817 value_profile_transformations (void)
1819 bool retval
= (value_prof_hooks
->value_profile_transformations
) ();
1820 VEC_free (histogram_value
, heap
, static_values
);