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
, *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
, *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
, *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
, *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
;
334 life_analysis (NULL
, PROP_DEATH_NOTES
);
336 *values
= VEC_alloc (histogram_value
, 0);
338 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
339 rtl_values_to_profile (insn
, values
);
340 static_values
= *values
;
342 for (i
= 0; i
< VEC_length (histogram_value
, *values
); i
++)
344 histogram_value hist
= VEC_index (histogram_value
, *values
, i
);
348 case HIST_TYPE_INTERVAL
:
351 "Interval counter for insn %d, range %d -- %d.\n",
352 INSN_UID ((rtx
)hist
->hvalue
.rtl
.insn
),
353 hist
->hdata
.intvl
.int_start
,
354 (hist
->hdata
.intvl
.int_start
355 + hist
->hdata
.intvl
.steps
- 1));
356 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
362 "Pow2 counter for insn %d.\n",
363 INSN_UID ((rtx
)hist
->hvalue
.rtl
.insn
));
365 = GET_MODE_BITSIZE (hist
->hvalue
.rtl
.mode
)
366 + (hist
->hdata
.pow2
.may_be_other
? 1 : 0);
369 case HIST_TYPE_SINGLE_VALUE
:
372 "Single value counter for insn %d.\n",
373 INSN_UID ((rtx
)hist
->hvalue
.rtl
.insn
));
374 hist
->n_counters
= 3;
377 case HIST_TYPE_CONST_DELTA
:
380 "Constant delta counter for insn %d.\n",
381 INSN_UID ((rtx
)hist
->hvalue
.rtl
.insn
));
382 hist
->n_counters
= 4;
389 allocate_reg_info (max_reg_num (), FALSE
, FALSE
);
392 /* Main entry point. Finds REG_VALUE_PROFILE notes from profiler and uses
393 them to identify and exploit properties of values that are hard to analyze
396 We do following transformations:
402 where b is almost always a constant N is transformed to
415 where b is almost always a power of 2 and the division is unsigned
416 TODO -- handle signed case as well
418 if ((b & (b - 1)) == 0)
423 Note that when b = 0, no error will occur and x = a; this is correct,
424 as result of such operation is undefined.
430 where a is almost always less then b and the division is unsigned
431 TODO -- handle signed case as well
441 where a is almost always less then 2 * b and the division is unsigned
442 TODO -- handle signed case as well
450 It would be possible to continue analogically for K * b for other small
451 K's, but it is probably not useful.
455 Read or write of mem[address], where the value of address changes usually
456 by a constant C != 0 between the following accesses to the computation; with
457 -fspeculative-prefetching we then add a prefetch of address + C before
458 the insn. This handles prefetching of several interesting cases in addition
459 to a simple prefetching for addresses that are induction variables, e. g.
460 linked lists allocated sequentially (even in case they are processed
463 TODO -- we should also check whether there is not (usually) a small
464 difference with the adjacent memory references, so that we do
465 not issue overlapping prefetches. Also we should employ some
466 heuristics to eliminate cases where prefetching evidently spoils
468 -- it should somehow cooperate with the loop optimizer prefetching
472 There are other useful cases that could be handled by a similar mechanism,
475 for (i = 0; i < n; i++)
478 transform to (for constant N):
481 for (i = 0; i < N; i++)
484 for (i = 0; i < n; i++)
486 making unroller happy. Since this may grow the code significantly,
487 we would have to be very careful here. */
490 rtl_value_profile_transformations (void)
495 for (insn
= get_insns (); insn
; insn
= next
)
497 next
= NEXT_INSN (insn
);
502 /* Scan for insn carrying a histogram. */
503 if (!find_reg_note (insn
, REG_VALUE_PROFILE
, 0))
506 /* Ignore cold areas -- we are growing a code. */
507 if (!maybe_hot_bb_p (BLOCK_FOR_INSN (insn
)))
512 fprintf (dump_file
, "Trying transformations on insn %d\n",
514 print_rtl_single (dump_file
, insn
);
517 /* Transformations: */
518 if (flag_value_profile_transformations
519 && (rtl_mod_subtract_transform (insn
)
520 || rtl_divmod_fixed_value_transform (insn
)
521 || rtl_mod_pow2_value_transform (insn
)))
524 if (flag_speculative_prefetching
525 && speculative_prefetching_transform (insn
))
532 commit_edge_insertions ();
533 allocate_reg_info (max_reg_num (), FALSE
, FALSE
);
539 /* Generate code for transformation 1 (with MODE and OPERATION, operands OP1
540 and OP2, whose value is expected to be VALUE, result TARGET and
541 probability of taking the optimal path PROB). */
543 rtl_divmod_fixed_value (enum machine_mode mode
, enum rtx_code operation
,
544 rtx target
, rtx op1
, rtx op2
, gcov_type value
,
548 rtx neq_label
= gen_label_rtx ();
549 rtx end_label
= gen_label_rtx ();
556 tmp
= gen_reg_rtx (mode
);
557 emit_move_insn (tmp
, copy_rtx (op2
));
562 do_compare_rtx_and_jump (tmp
, GEN_INT (value
), NE
, 0, mode
, NULL_RTX
,
563 NULL_RTX
, neq_label
);
565 /* Add branch probability to jump we just created. */
566 jump
= get_last_insn ();
567 REG_NOTES (jump
) = gen_rtx_EXPR_LIST (REG_BR_PROB
,
568 GEN_INT (REG_BR_PROB_BASE
- prob
),
571 tmp1
= simplify_gen_binary (operation
, mode
,
572 copy_rtx (op1
), GEN_INT (value
));
573 tmp1
= force_operand (tmp1
, target
);
575 emit_move_insn (copy_rtx (target
), copy_rtx (tmp1
));
577 emit_jump_insn (gen_jump (end_label
));
580 emit_label (neq_label
);
581 tmp1
= simplify_gen_binary (operation
, mode
,
582 copy_rtx (op1
), copy_rtx (tmp
));
583 tmp1
= force_operand (tmp1
, target
);
585 emit_move_insn (copy_rtx (target
), copy_rtx (tmp1
));
587 emit_label (end_label
);
589 sequence
= get_insns ();
591 rebuild_jump_labels (sequence
);
595 /* Do transform 1) on INSN if applicable. */
597 rtl_divmod_fixed_value_transform (rtx insn
)
599 rtx set
, set_src
, set_dest
, op1
, op2
, value
, histogram
;
601 enum machine_mode mode
;
602 gcov_type val
, count
, all
;
606 set
= single_set (insn
);
610 set_src
= SET_SRC (set
);
611 set_dest
= SET_DEST (set
);
612 code
= GET_CODE (set_src
);
613 mode
= GET_MODE (set_dest
);
615 if (code
!= DIV
&& code
!= MOD
&& code
!= UDIV
&& code
!= UMOD
)
617 op1
= XEXP (set_src
, false);
618 op2
= XEXP (set_src
, 1);
620 for (histogram
= REG_NOTES (insn
);
622 histogram
= XEXP (histogram
, 1))
623 if (REG_NOTE_KIND (histogram
) == REG_VALUE_PROFILE
624 && XEXP (XEXP (histogram
, 0), 0) == GEN_INT (HIST_TYPE_SINGLE_VALUE
))
630 histogram
= XEXP (XEXP (histogram
, 0), 1);
631 value
= XEXP (histogram
, 0);
632 histogram
= XEXP (histogram
, 1);
633 val
= INTVAL (XEXP (histogram
, 0));
634 histogram
= XEXP (histogram
, 1);
635 count
= INTVAL (XEXP (histogram
, 0));
636 histogram
= XEXP (histogram
, 1);
637 all
= INTVAL (XEXP (histogram
, 0));
639 /* We require that count be at least half of all; this means
640 that for the transformation to fire the value must be constant
641 at least 50% of time (and 75% gives the guarantee of usage). */
642 if (!rtx_equal_p (op2
, value
) || 2 * count
< all
)
646 fprintf (dump_file
, "Div/mod by constant transformation on insn %d\n",
649 /* Compute probability of taking the optimal path. */
650 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
652 e
= split_block (BLOCK_FOR_INSN (insn
), PREV_INSN (insn
));
655 insert_insn_on_edge (
656 rtl_divmod_fixed_value (mode
, code
, set_dest
,
657 op1
, op2
, val
, prob
), e
);
662 /* Generate code for transformation 2 (with MODE and OPERATION, operands OP1
663 and OP2, result TARGET and probability of taking the optimal path PROB). */
665 rtl_mod_pow2 (enum machine_mode mode
, enum rtx_code operation
, rtx target
,
666 rtx op1
, rtx op2
, int prob
)
668 rtx tmp
, tmp1
, tmp2
, tmp3
, jump
;
669 rtx neq_label
= gen_label_rtx ();
670 rtx end_label
= gen_label_rtx ();
677 tmp
= gen_reg_rtx (mode
);
678 emit_move_insn (tmp
, copy_rtx (op2
));
683 tmp1
= expand_simple_binop (mode
, PLUS
, tmp
, constm1_rtx
, NULL_RTX
,
685 tmp2
= expand_simple_binop (mode
, AND
, tmp
, tmp1
, NULL_RTX
,
687 do_compare_rtx_and_jump (tmp2
, const0_rtx
, NE
, 0, mode
, NULL_RTX
,
688 NULL_RTX
, neq_label
);
690 /* Add branch probability to jump we just created. */
691 jump
= get_last_insn ();
692 REG_NOTES (jump
) = gen_rtx_EXPR_LIST (REG_BR_PROB
,
693 GEN_INT (REG_BR_PROB_BASE
- prob
),
696 tmp3
= expand_simple_binop (mode
, AND
, op1
, tmp1
, target
,
699 emit_move_insn (copy_rtx (target
), tmp3
);
700 emit_jump_insn (gen_jump (end_label
));
703 emit_label (neq_label
);
704 tmp1
= simplify_gen_binary (operation
, mode
, copy_rtx (op1
), copy_rtx (tmp
));
705 tmp1
= force_operand (tmp1
, target
);
707 emit_move_insn (target
, tmp1
);
709 emit_label (end_label
);
711 sequence
= get_insns ();
713 rebuild_jump_labels (sequence
);
717 /* Do transform 2) on INSN if applicable. */
719 rtl_mod_pow2_value_transform (rtx insn
)
721 rtx set
, set_src
, set_dest
, op1
, op2
, value
, histogram
;
723 enum machine_mode mode
;
724 gcov_type wrong_values
, count
;
728 set
= single_set (insn
);
732 set_src
= SET_SRC (set
);
733 set_dest
= SET_DEST (set
);
734 code
= GET_CODE (set_src
);
735 mode
= GET_MODE (set_dest
);
739 op1
= XEXP (set_src
, 0);
740 op2
= XEXP (set_src
, 1);
742 for (histogram
= REG_NOTES (insn
);
744 histogram
= XEXP (histogram
, 1))
745 if (REG_NOTE_KIND (histogram
) == REG_VALUE_PROFILE
746 && XEXP (XEXP (histogram
, 0), 0) == GEN_INT (HIST_TYPE_POW2
))
752 histogram
= XEXP (XEXP (histogram
, 0), 1);
753 value
= XEXP (histogram
, 0);
754 histogram
= XEXP (histogram
, 1);
755 wrong_values
=INTVAL (XEXP (histogram
, 0));
756 histogram
= XEXP (histogram
, 1);
759 for (i
= 0; i
< GET_MODE_BITSIZE (mode
); i
++)
761 count
+= INTVAL (XEXP (histogram
, 0));
762 histogram
= XEXP (histogram
, 1);
765 if (!rtx_equal_p (op2
, value
))
768 /* We require that we hit a power of two at least half of all evaluations. */
769 if (count
< wrong_values
)
773 fprintf (dump_file
, "Mod power of 2 transformation on insn %d\n",
776 /* Compute probability of taking the optimal path. */
777 all
= count
+ wrong_values
;
778 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
780 e
= split_block (BLOCK_FOR_INSN (insn
), PREV_INSN (insn
));
783 insert_insn_on_edge (
784 rtl_mod_pow2 (mode
, code
, set_dest
, op1
, op2
, prob
), e
);
789 /* Generate code for transformations 3 and 4 (with MODE and OPERATION,
790 operands OP1 and OP2, result TARGET, at most SUB subtractions, and
791 probability of taking the optimal path(s) PROB1 and PROB2). */
793 rtl_mod_subtract (enum machine_mode mode
, enum rtx_code operation
,
794 rtx target
, rtx op1
, rtx op2
, int sub
, int prob1
, int prob2
)
797 rtx end_label
= gen_label_rtx ();
805 tmp
= gen_reg_rtx (mode
);
806 emit_move_insn (tmp
, copy_rtx (op2
));
811 emit_move_insn (target
, copy_rtx (op1
));
812 do_compare_rtx_and_jump (target
, tmp
, LTU
, 0, mode
, NULL_RTX
,
813 NULL_RTX
, end_label
);
815 /* Add branch probability to jump we just created. */
816 jump
= get_last_insn ();
817 REG_NOTES (jump
) = gen_rtx_EXPR_LIST (REG_BR_PROB
,
818 GEN_INT (prob1
), REG_NOTES (jump
));
820 for (i
= 0; i
< sub
; i
++)
822 tmp1
= expand_simple_binop (mode
, MINUS
, target
, tmp
, target
,
825 emit_move_insn (target
, tmp1
);
826 do_compare_rtx_and_jump (target
, tmp
, LTU
, 0, mode
, NULL_RTX
,
827 NULL_RTX
, end_label
);
829 /* Add branch probability to jump we just created. */
830 jump
= get_last_insn ();
831 REG_NOTES (jump
) = gen_rtx_EXPR_LIST (REG_BR_PROB
,
832 GEN_INT (prob2
), REG_NOTES (jump
));
835 tmp1
= simplify_gen_binary (operation
, mode
, copy_rtx (target
), copy_rtx (tmp
));
836 tmp1
= force_operand (tmp1
, target
);
838 emit_move_insn (target
, tmp1
);
840 emit_label (end_label
);
842 sequence
= get_insns ();
844 rebuild_jump_labels (sequence
);
848 /* Do transforms 3) and 4) on INSN if applicable. */
850 rtl_mod_subtract_transform (rtx insn
)
852 rtx set
, set_src
, set_dest
, op1
, op2
, histogram
;
854 enum machine_mode mode
;
855 gcov_type wrong_values
, counts
[2], count
, all
;
859 set
= single_set (insn
);
863 set_src
= SET_SRC (set
);
864 set_dest
= SET_DEST (set
);
865 code
= GET_CODE (set_src
);
866 mode
= GET_MODE (set_dest
);
870 op1
= XEXP (set_src
, 0);
871 op2
= XEXP (set_src
, 1);
873 for (histogram
= REG_NOTES (insn
);
875 histogram
= XEXP (histogram
, 1))
876 if (REG_NOTE_KIND (histogram
) == REG_VALUE_PROFILE
877 && XEXP (XEXP (histogram
, 0), 0) == GEN_INT (HIST_TYPE_INTERVAL
))
883 histogram
= XEXP (XEXP (histogram
, 0), 1);
884 histogram
= XEXP (histogram
, 1);
887 for (i
= 0; i
< 2; i
++)
889 counts
[i
] = INTVAL (XEXP (histogram
, 0));
891 histogram
= XEXP (histogram
, 1);
893 wrong_values
= INTVAL (XEXP (histogram
, 0));
894 histogram
= XEXP (histogram
, 1);
895 wrong_values
+= INTVAL (XEXP (histogram
, 0));
898 /* We require that we use just subtractions in at least 50% of all
901 for (i
= 0; i
< 2; i
++)
904 if (count
* 2 >= all
)
912 fprintf (dump_file
, "Mod subtract transformation on insn %d\n",
915 /* Compute probability of taking the optimal path(s). */
916 prob1
= (counts
[0] * REG_BR_PROB_BASE
+ all
/ 2) / all
;
917 prob2
= (counts
[1] * REG_BR_PROB_BASE
+ all
/ 2) / all
;
919 e
= split_block (BLOCK_FOR_INSN (insn
), PREV_INSN (insn
));
922 insert_insn_on_edge (
923 rtl_mod_subtract (mode
, code
, set_dest
,
924 op1
, op2
, i
, prob1
, prob2
), e
);
930 /* Generate code for transformation 5 for mem with ADDRESS and a constant
931 step DELTA. WRITE is true if the reference is a store to mem. */
934 gen_speculative_prefetch (rtx address
, gcov_type delta
, int write
)
939 /* TODO: we do the prefetching for just one iteration ahead, which
940 often is not enough. */
942 if (offsettable_address_p (0, VOIDmode
, address
))
943 tmp
= plus_constant (copy_rtx (address
), delta
);
946 tmp
= simplify_gen_binary (PLUS
, Pmode
,
947 copy_rtx (address
), GEN_INT (delta
));
948 tmp
= force_operand (tmp
, NULL
);
950 if (! (*insn_data
[(int)CODE_FOR_prefetch
].operand
[0].predicate
)
951 (tmp
, insn_data
[(int)CODE_FOR_prefetch
].operand
[0].mode
))
952 tmp
= force_reg (Pmode
, tmp
);
953 emit_insn (gen_prefetch (tmp
, GEN_INT (write
), GEN_INT (3)));
954 sequence
= get_insns ();
960 /* Do transform 5) on INSN if applicable. */
963 speculative_prefetching_transform (rtx insn
)
965 rtx histogram
, value
;
966 gcov_type val
, count
, all
;
971 if (!maybe_hot_bb_p (BLOCK_FOR_INSN (insn
)))
974 if (!find_mem_reference (insn
, &mem
, &write
))
977 address
= XEXP (mem
, 0);
978 if (side_effects_p (address
))
981 if (CONSTANT_P (address
))
984 for (histogram
= REG_NOTES (insn
);
986 histogram
= XEXP (histogram
, 1))
987 if (REG_NOTE_KIND (histogram
) == REG_VALUE_PROFILE
988 && XEXP (XEXP (histogram
, 0), 0) == GEN_INT (HIST_TYPE_CONST_DELTA
))
994 histogram
= XEXP (XEXP (histogram
, 0), 1);
995 value
= XEXP (histogram
, 0);
996 histogram
= XEXP (histogram
, 1);
997 /* Skip last value referenced. */
998 histogram
= XEXP (histogram
, 1);
999 val
= INTVAL (XEXP (histogram
, 0));
1000 histogram
= XEXP (histogram
, 1);
1001 count
= INTVAL (XEXP (histogram
, 0));
1002 histogram
= XEXP (histogram
, 1);
1003 all
= INTVAL (XEXP (histogram
, 0));
1005 /* With that few executions we do not really have a reason to optimize the
1006 statement, and more importantly, the data about differences of addresses
1007 are spoiled by the first item that had no previous value to compare
1012 /* We require that count be at least half of all; this means
1013 that for the transformation to fire the value must be constant
1014 at least 50% of time (and 75% gives the guarantee of usage). */
1015 if (!rtx_equal_p (address
, value
) || 2 * count
< all
)
1018 /* If the difference is too small, it does not make too much sense to
1019 prefetch, as the memory is probably already in cache. */
1020 if (val
>= NOPREFETCH_RANGE_MIN
&& val
<= NOPREFETCH_RANGE_MAX
)
1024 fprintf (dump_file
, "Speculative prefetching for insn %d\n",
1027 e
= split_block (BLOCK_FOR_INSN (insn
), PREV_INSN (insn
));
1029 insert_insn_on_edge (gen_speculative_prefetch (address
, val
, write
), e
);
1033 #endif /* HAVE_prefetch */
1035 /* Tree based transformations. */
1037 tree_value_profile_transformations (void)
1040 block_stmt_iterator bsi
;
1041 bool changed
= false;
1045 /* Ignore cold areas -- we are enlarging the code. */
1046 if (!maybe_hot_bb_p (bb
))
1049 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1051 tree stmt
= bsi_stmt (bsi
);
1052 stmt_ann_t ann
= get_stmt_ann (stmt
);
1053 histogram_value th
= ann
->histograms
;
1059 fprintf (dump_file
, "Trying transformations on insn ");
1060 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1063 /* Transformations: */
1064 /* The order of things in this conditional controls which
1065 transformation is used when more than one is applicable. */
1066 /* It is expected that any code added by the transformations
1067 will be added before the current statement, and that the
1068 current statement remain valid (although possibly
1069 modified) upon return. */
1070 if (flag_value_profile_transformations
1071 && (tree_mod_subtract_transform (stmt
)
1072 || tree_divmod_fixed_value_transform (stmt
)
1073 || tree_mod_pow2_value_transform (stmt
)))
1076 /* Original statement may no longer be in the same block. */
1077 bb
= bb_for_stmt (stmt
);
1080 /* Free extra storage from compute_value_histograms. */
1083 free (th
->hvalue
.tree
.counters
);
1084 th
= th
->hvalue
.tree
.next
;
1086 ann
->histograms
= 0;
1098 /* Generate code for transformation 1 (with OPERATION, operands OP1
1099 and OP2, whose value is expected to be VALUE, parent modify-expr STMT and
1100 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
1101 within roundoff error). This generates the result into a temp and returns
1102 the temp; it does not replace or alter the original STMT. */
1104 tree_divmod_fixed_value (tree stmt
, tree operation
,
1105 tree op1
, tree op2
, tree value
, int prob
, gcov_type count
,
1108 tree stmt1
, stmt2
, stmt3
;
1109 tree tmp1
, tmp2
, tmpv
;
1110 tree label_decl1
= create_artificial_label ();
1111 tree label_decl2
= create_artificial_label ();
1112 tree label_decl3
= create_artificial_label ();
1113 tree label1
, label2
, label3
;
1114 tree bb1end
, bb2end
, bb3end
;
1115 basic_block bb
, bb2
, bb3
, bb4
;
1116 tree optype
= TREE_TYPE (operation
);
1117 edge e12
, e13
, e23
, e24
, e34
;
1118 block_stmt_iterator bsi
;
1120 bb
= bb_for_stmt (stmt
);
1121 bsi
= bsi_for_stmt (stmt
);
1123 tmpv
= create_tmp_var (optype
, "PROF");
1124 tmp1
= create_tmp_var (optype
, "PROF");
1125 stmt1
= build2 (MODIFY_EXPR
, optype
, tmpv
, fold_convert (optype
, value
));
1126 stmt2
= build2 (MODIFY_EXPR
, optype
, tmp1
, op2
);
1127 stmt3
= build3 (COND_EXPR
, void_type_node
,
1128 build2 (NE_EXPR
, boolean_type_node
, tmp1
, tmpv
),
1129 build1 (GOTO_EXPR
, void_type_node
, label_decl2
),
1130 build1 (GOTO_EXPR
, void_type_node
, label_decl1
));
1131 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1132 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
1133 bsi_insert_before (&bsi
, stmt3
, BSI_SAME_STMT
);
1136 tmp2
= create_tmp_var (optype
, "PROF");
1137 label1
= build1 (LABEL_EXPR
, void_type_node
, label_decl1
);
1138 stmt1
= build2 (MODIFY_EXPR
, optype
, tmp2
,
1139 build2 (TREE_CODE (operation
), optype
, op1
, tmpv
));
1140 bsi_insert_before (&bsi
, label1
, BSI_SAME_STMT
);
1141 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1144 label2
= build1 (LABEL_EXPR
, void_type_node
, label_decl2
);
1145 stmt1
= build2 (MODIFY_EXPR
, optype
, tmp2
,
1146 build2 (TREE_CODE (operation
), optype
, op1
, op2
));
1147 bsi_insert_before (&bsi
, label2
, BSI_SAME_STMT
);
1148 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1151 label3
= build1 (LABEL_EXPR
, void_type_node
, label_decl3
);
1152 bsi_insert_before (&bsi
, label3
, BSI_SAME_STMT
);
1155 /* Edge e23 connects bb2 to bb3, etc. */
1156 e12
= split_block (bb
, bb1end
);
1159 e23
= split_block (bb2
, bb2end
);
1161 bb3
->count
= all
- count
;
1162 e34
= split_block (bb3
, bb3end
);
1166 e12
->flags
&= ~EDGE_FALLTHRU
;
1167 e12
->flags
|= EDGE_FALSE_VALUE
;
1168 e12
->probability
= prob
;
1171 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
1172 e13
->probability
= REG_BR_PROB_BASE
- prob
;
1173 e13
->count
= all
- count
;
1177 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
1178 e24
->probability
= REG_BR_PROB_BASE
;
1181 e34
->probability
= REG_BR_PROB_BASE
;
1182 e34
->count
= all
- count
;
1187 /* Do transform 1) on INSN if applicable. */
1189 tree_divmod_fixed_value_transform (tree stmt
)
1191 stmt_ann_t ann
= get_stmt_ann (stmt
);
1192 histogram_value histogram
;
1193 enum tree_code code
;
1194 gcov_type val
, count
, all
;
1195 tree modify
, op
, op1
, op2
, result
, value
, tree_val
;
1199 if (TREE_CODE (stmt
) == RETURN_EXPR
1200 && TREE_OPERAND (stmt
, 0)
1201 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == MODIFY_EXPR
)
1202 modify
= TREE_OPERAND (stmt
, 0);
1203 if (TREE_CODE (modify
) != MODIFY_EXPR
)
1205 op
= TREE_OPERAND (modify
, 1);
1206 if (!INTEGRAL_TYPE_P (TREE_TYPE (op
)))
1208 code
= TREE_CODE (op
);
1210 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
1213 op1
= TREE_OPERAND (op
, 0);
1214 op2
= TREE_OPERAND (op
, 1);
1215 if (!ann
->histograms
)
1218 for (histogram
= ann
->histograms
; histogram
; histogram
= histogram
->hvalue
.tree
.next
)
1219 if (histogram
->type
== HIST_TYPE_SINGLE_VALUE
)
1225 value
= histogram
->hvalue
.tree
.value
;
1226 val
= histogram
->hvalue
.tree
.counters
[0];
1227 count
= histogram
->hvalue
.tree
.counters
[1];
1228 all
= histogram
->hvalue
.tree
.counters
[2];
1230 /* We require that count is at least half of all; this means
1231 that for the transformation to fire the value must be constant
1232 at least 50% of time (and 75% gives the guarantee of usage). */
1233 if (simple_cst_equal (op2
, value
) != 1 || 2 * count
< all
)
1238 fprintf (dump_file
, "Div/mod by constant transformation on insn ");
1239 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1242 /* Compute probability of taking the optimal path. */
1243 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1245 tree_val
= build_int_cst_wide (get_gcov_type (),
1246 val
& 0xffffffffull
, val
>> 32);
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 /* Check for a special case where the divisor is power(s) of 2.
1668 This is more aggressive than the RTL version, under the
1669 assumption that later phases will reduce / or % by power of 2
1670 to something clever most of the time. Signed or unsigned. */
1671 if (TREE_CODE (op2
) != INTEGER_CST
)
1673 hist
= ggc_alloc (sizeof (*hist
));
1674 hist
->hvalue
.tree
.value
= op2
;
1675 hist
->hvalue
.tree
.stmt
= stmt
;
1676 hist
->type
= HIST_TYPE_POW2
;
1677 hist
->hdata
.pow2
.may_be_other
= 1;
1678 VEC_safe_push (histogram_value
, *values
, hist
);
1681 /* Check for the case where the divisor is the same value most
1683 if (TREE_CODE (op2
) != INTEGER_CST
)
1685 hist
= ggc_alloc (sizeof (*hist
));
1686 hist
->hvalue
.tree
.value
= op2
;
1687 hist
->hvalue
.tree
.stmt
= stmt
;
1688 hist
->type
= HIST_TYPE_SINGLE_VALUE
;
1689 VEC_safe_push (histogram_value
, *values
, hist
);
1692 /* For mod, check whether it is not often a noop (or replaceable by
1693 a few subtractions). */
1694 if (TREE_CODE (op
) == TRUNC_MOD_EXPR
&& TYPE_UNSIGNED (TREE_TYPE (op
)))
1696 hist
= ggc_alloc (sizeof (*hist
));
1697 hist
->hvalue
.tree
.stmt
= stmt
;
1698 hist
->hvalue
.tree
.value
= op2
;
1699 hist
->type
= HIST_TYPE_INTERVAL
;
1700 hist
->hdata
.intvl
.int_start
= 0;
1701 hist
->hdata
.intvl
.steps
= 2;
1702 VEC_safe_push (histogram_value
, *values
, hist
);
1711 /* Find values inside INSN for that we want to measure histograms and adds
1712 them to list VALUES (increasing the record of its length in N_VALUES). */
1714 tree_values_to_profile (tree stmt
, histogram_values
*values
)
1716 if (flag_value_profile_transformations
)
1717 tree_divmod_values_to_profile (stmt
, values
);
1721 tree_find_values_to_profile (histogram_values
*values
)
1724 block_stmt_iterator bsi
;
1728 *values
= VEC_alloc (histogram_value
, 0);
1730 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1732 tree stmt
= bsi_stmt (bsi
);
1733 tree_values_to_profile (stmt
, values
);
1735 static_values
= *values
;
1737 for (i
= 0; i
< VEC_length (histogram_value
, *values
); i
++)
1739 histogram_value hist
= VEC_index (histogram_value
, *values
, i
);
1743 case HIST_TYPE_INTERVAL
:
1746 fprintf (dump_file
, "Interval counter for tree ");
1747 print_generic_expr (dump_file
, hist
->hvalue
.tree
.stmt
,
1749 fprintf (dump_file
, ", range %d -- %d.\n",
1750 hist
->hdata
.intvl
.int_start
,
1751 (hist
->hdata
.intvl
.int_start
1752 + hist
->hdata
.intvl
.steps
- 1));
1754 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1757 case HIST_TYPE_POW2
:
1760 fprintf (dump_file
, "Pow2 counter for insn ");
1761 print_generic_expr (dump_file
, hist
->hvalue
.tree
.stmt
, TDF_SLIM
);
1762 fprintf (dump_file
, ".\n");
1764 stmt
= hist
->hvalue
.tree
.stmt
;
1766 = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (stmt
)))
1767 + (hist
->hdata
.pow2
.may_be_other
? 1 : 0);
1770 case HIST_TYPE_SINGLE_VALUE
:
1773 fprintf (dump_file
, "Single value counter for insn ");
1774 print_generic_expr (dump_file
, hist
->hvalue
.tree
.stmt
, TDF_SLIM
);
1775 fprintf (dump_file
, ".\n");
1777 hist
->n_counters
= 3;
1780 case HIST_TYPE_CONST_DELTA
:
1783 fprintf (dump_file
, "Constant delta counter for insn ");
1784 print_generic_expr (dump_file
, hist
->hvalue
.tree
.stmt
, TDF_SLIM
);
1785 fprintf (dump_file
, ".\n");
1787 hist
->n_counters
= 4;
1796 static struct value_prof_hooks tree_value_prof_hooks
= {
1797 tree_find_values_to_profile
,
1798 tree_value_profile_transformations
1802 tree_register_value_prof_hooks (void)
1804 value_prof_hooks
= &tree_value_prof_hooks
;
1805 gcc_assert (ir_type ());
1808 /* IR-independent entry points. */
1810 find_values_to_profile (histogram_values
*values
)
1812 (value_prof_hooks
->find_values_to_profile
) (values
);
1816 value_profile_transformations (void)
1818 bool retval
= (value_prof_hooks
->value_profile_transformations
) ();
1819 VEC_free (histogram_value
, static_values
);