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, 51 Franklin Street, Fifth Floor, 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 #include "tree-pass.h"
47 static struct value_prof_hooks
*value_prof_hooks
;
49 /* In this file value profile based optimizations are placed. Currently the
50 following optimizations are implemented (for more detailed descriptions
51 see comments at value_profile_transformations):
53 1) Division/modulo specialization. Provided that we can determine that the
54 operands of the division have some special properties, we may use it to
55 produce more effective code.
56 2) Speculative prefetching. If we are able to determine that the difference
57 between addresses accessed by a memory reference is usually constant, we
58 may add the prefetch instructions.
59 FIXME: This transformation was removed together with RTL based value
62 Every such optimization should add its requirements for profiled values to
63 insn_values_to_profile function. This function is called from branch_prob
64 in profile.c and the requested values are instrumented by it in the first
65 compilation with -fprofile-arcs. The optimization may then read the
66 gathered data in the second compilation with -fbranch-probabilities.
68 The measured data is pointed to from the histograms
69 field of the statement annotation of the instrumented insns. It is
70 kept as a linked list of struct histogram_value_t's, which contain the
71 same information as above. */
74 static tree
tree_divmod_fixed_value (tree
, tree
, tree
, tree
,
75 tree
, int, gcov_type
, gcov_type
);
76 static tree
tree_mod_pow2 (tree
, tree
, tree
, tree
, int, gcov_type
, gcov_type
);
77 static tree
tree_mod_subtract (tree
, tree
, tree
, tree
, int, int, int,
78 gcov_type
, gcov_type
, gcov_type
);
79 static bool tree_divmod_fixed_value_transform (tree
);
80 static bool tree_mod_pow2_value_transform (tree
);
81 static bool tree_mod_subtract_transform (tree
);
83 /* The overall number of invocations of the counter should match execution count
84 of basic block. Report it as error rather than internal error as it might
85 mean that user has misused the profile somehow. */
87 check_counter (tree stmt
, const char * name
, gcov_type all
, gcov_type bb_count
)
92 locus
= (stmt
!= NULL
&& EXPR_HAS_LOCATION (stmt
)
94 : &DECL_SOURCE_LOCATION (current_function_decl
));
95 error ("%HCorrupted value profile: %s profiler overall count (%d) does not match BB count (%d)",
96 locus
, name
, (int)all
, (int)bb_count
);
102 /* Tree based transformations. */
104 tree_value_profile_transformations (void)
107 block_stmt_iterator bsi
;
108 bool changed
= false;
112 /* Ignore cold areas -- we are enlarging the code. */
113 if (!maybe_hot_bb_p (bb
))
116 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
118 tree stmt
= bsi_stmt (bsi
);
119 stmt_ann_t ann
= get_stmt_ann (stmt
);
120 histogram_value th
= ann
->histograms
;
126 fprintf (dump_file
, "Trying transformations on insn ");
127 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
130 /* Transformations: */
131 /* The order of things in this conditional controls which
132 transformation is used when more than one is applicable. */
133 /* It is expected that any code added by the transformations
134 will be added before the current statement, and that the
135 current statement remain valid (although possibly
136 modified) upon return. */
137 if (flag_value_profile_transformations
138 && (tree_mod_subtract_transform (stmt
)
139 || tree_divmod_fixed_value_transform (stmt
)
140 || tree_mod_pow2_value_transform (stmt
)))
143 /* Original statement may no longer be in the same block. */
144 if (bb
!= bb_for_stmt (stmt
))
146 bb
= bb_for_stmt (stmt
);
147 bsi
= bsi_for_stmt (stmt
);
151 /* Free extra storage from compute_value_histograms. */
154 free (th
->hvalue
.counters
);
155 th
= th
->hvalue
.next
;
169 /* Generate code for transformation 1 (with OPERATION, operands OP1
170 and OP2, whose value is expected to be VALUE, parent modify-expr STMT and
171 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
172 within roundoff error). This generates the result into a temp and returns
173 the temp; it does not replace or alter the original STMT. */
175 tree_divmod_fixed_value (tree stmt
, tree operation
,
176 tree op1
, tree op2
, tree value
, int prob
, gcov_type count
,
179 tree stmt1
, stmt2
, stmt3
;
180 tree tmp1
, tmp2
, tmpv
;
181 tree label_decl1
= create_artificial_label ();
182 tree label_decl2
= create_artificial_label ();
183 tree label_decl3
= create_artificial_label ();
184 tree label1
, label2
, label3
;
185 tree bb1end
, bb2end
, bb3end
;
186 basic_block bb
, bb2
, bb3
, bb4
;
187 tree optype
= TREE_TYPE (operation
);
188 edge e12
, e13
, e23
, e24
, e34
;
189 block_stmt_iterator bsi
;
191 bb
= bb_for_stmt (stmt
);
192 bsi
= bsi_for_stmt (stmt
);
194 tmpv
= create_tmp_var (optype
, "PROF");
195 tmp1
= create_tmp_var (optype
, "PROF");
196 stmt1
= build2 (GIMPLE_MODIFY_STMT
, optype
, tmpv
,
197 fold_convert (optype
, value
));
198 stmt2
= build2 (GIMPLE_MODIFY_STMT
, optype
, tmp1
, op2
);
199 stmt3
= build3 (COND_EXPR
, void_type_node
,
200 build2 (NE_EXPR
, boolean_type_node
, tmp1
, tmpv
),
201 build1 (GOTO_EXPR
, void_type_node
, label_decl2
),
202 build1 (GOTO_EXPR
, void_type_node
, label_decl1
));
203 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
204 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
205 bsi_insert_before (&bsi
, stmt3
, BSI_SAME_STMT
);
208 tmp2
= create_tmp_var (optype
, "PROF");
209 label1
= build1 (LABEL_EXPR
, void_type_node
, label_decl1
);
210 stmt1
= build2 (GIMPLE_MODIFY_STMT
, optype
, tmp2
,
211 build2 (TREE_CODE (operation
), optype
, op1
, tmpv
));
212 bsi_insert_before (&bsi
, label1
, BSI_SAME_STMT
);
213 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
216 label2
= build1 (LABEL_EXPR
, void_type_node
, label_decl2
);
217 stmt1
= build2 (GIMPLE_MODIFY_STMT
, optype
, tmp2
,
218 build2 (TREE_CODE (operation
), optype
, op1
, op2
));
219 bsi_insert_before (&bsi
, label2
, BSI_SAME_STMT
);
220 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
223 label3
= build1 (LABEL_EXPR
, void_type_node
, label_decl3
);
224 bsi_insert_before (&bsi
, label3
, BSI_SAME_STMT
);
227 /* Edge e23 connects bb2 to bb3, etc. */
228 e12
= split_block (bb
, bb1end
);
231 e23
= split_block (bb2
, bb2end
);
233 bb3
->count
= all
- count
;
234 e34
= split_block (bb3
, bb3end
);
238 e12
->flags
&= ~EDGE_FALLTHRU
;
239 e12
->flags
|= EDGE_FALSE_VALUE
;
240 e12
->probability
= prob
;
243 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
244 e13
->probability
= REG_BR_PROB_BASE
- prob
;
245 e13
->count
= all
- count
;
249 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
250 e24
->probability
= REG_BR_PROB_BASE
;
253 e34
->probability
= REG_BR_PROB_BASE
;
254 e34
->count
= all
- count
;
259 /* Do transform 1) on INSN if applicable. */
261 tree_divmod_fixed_value_transform (tree stmt
)
263 stmt_ann_t ann
= get_stmt_ann (stmt
);
264 histogram_value histogram
;
266 gcov_type val
, count
, all
;
267 tree modify
, op
, op1
, op2
, result
, value
, tree_val
;
271 if (TREE_CODE (stmt
) == RETURN_EXPR
272 && TREE_OPERAND (stmt
, 0)
273 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == GIMPLE_MODIFY_STMT
)
274 modify
= TREE_OPERAND (stmt
, 0);
275 if (TREE_CODE (modify
) != GIMPLE_MODIFY_STMT
)
277 op
= GIMPLE_STMT_OPERAND (modify
, 1);
278 if (!INTEGRAL_TYPE_P (TREE_TYPE (op
)))
280 code
= TREE_CODE (op
);
282 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
285 op1
= TREE_OPERAND (op
, 0);
286 op2
= TREE_OPERAND (op
, 1);
287 if (!ann
->histograms
)
290 for (histogram
= ann
->histograms
; histogram
; histogram
= histogram
->hvalue
.next
)
291 if (histogram
->type
== HIST_TYPE_SINGLE_VALUE
)
297 value
= histogram
->hvalue
.value
;
298 val
= histogram
->hvalue
.counters
[0];
299 count
= histogram
->hvalue
.counters
[1];
300 all
= histogram
->hvalue
.counters
[2];
302 /* We require that count is at least half of all; this means
303 that for the transformation to fire the value must be constant
304 at least 50% of time (and 75% gives the guarantee of usage). */
305 if (simple_cst_equal (op2
, value
) != 1 || 2 * count
< all
)
308 if (check_counter (stmt
, "value", all
, bb_for_stmt (stmt
)->count
))
311 /* Compute probability of taking the optimal path. */
312 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
314 tree_val
= build_int_cst_wide (get_gcov_type (),
315 (unsigned HOST_WIDE_INT
) val
,
316 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
317 result
= tree_divmod_fixed_value (stmt
, op
, op1
, op2
, tree_val
, prob
, count
, all
);
321 fprintf (dump_file
, "Div/mod by constant ");
322 print_generic_expr (dump_file
, value
, TDF_SLIM
);
323 fprintf (dump_file
, "=");
324 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
325 fprintf (dump_file
, " transformation on insn ");
326 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
329 GIMPLE_STMT_OPERAND (modify
, 1) = result
;
334 /* Generate code for transformation 2 (with OPERATION, operands OP1
335 and OP2, parent modify-expr STMT and probability of taking the optimal
336 path PROB, which is equivalent to COUNT/ALL within roundoff error).
337 This generates the result into a temp and returns
338 the temp; it does not replace or alter the original STMT. */
340 tree_mod_pow2 (tree stmt
, tree operation
, tree op1
, tree op2
, int prob
,
341 gcov_type count
, gcov_type all
)
343 tree stmt1
, stmt2
, stmt3
, stmt4
;
345 tree label_decl1
= create_artificial_label ();
346 tree label_decl2
= create_artificial_label ();
347 tree label_decl3
= create_artificial_label ();
348 tree label1
, label2
, label3
;
349 tree bb1end
, bb2end
, bb3end
;
350 basic_block bb
, bb2
, bb3
, bb4
;
351 tree optype
= TREE_TYPE (operation
);
352 edge e12
, e13
, e23
, e24
, e34
;
353 block_stmt_iterator bsi
;
354 tree result
= create_tmp_var (optype
, "PROF");
356 bb
= bb_for_stmt (stmt
);
357 bsi
= bsi_for_stmt (stmt
);
359 tmp2
= create_tmp_var (optype
, "PROF");
360 tmp3
= create_tmp_var (optype
, "PROF");
361 stmt2
= build2 (GIMPLE_MODIFY_STMT
, optype
, tmp2
,
362 build2 (PLUS_EXPR
, optype
, op2
, build_int_cst (optype
, -1)));
363 stmt3
= build2 (GIMPLE_MODIFY_STMT
, optype
, tmp3
,
364 build2 (BIT_AND_EXPR
, optype
, tmp2
, op2
));
365 stmt4
= build3 (COND_EXPR
, void_type_node
,
366 build2 (NE_EXPR
, boolean_type_node
,
367 tmp3
, build_int_cst (optype
, 0)),
368 build1 (GOTO_EXPR
, void_type_node
, label_decl2
),
369 build1 (GOTO_EXPR
, void_type_node
, label_decl1
));
370 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
371 bsi_insert_before (&bsi
, stmt3
, BSI_SAME_STMT
);
372 bsi_insert_before (&bsi
, stmt4
, BSI_SAME_STMT
);
375 /* tmp2 == op2-1 inherited from previous block */
376 label1
= build1 (LABEL_EXPR
, void_type_node
, label_decl1
);
377 stmt1
= build2 (GIMPLE_MODIFY_STMT
, optype
, result
,
378 build2 (BIT_AND_EXPR
, optype
, op1
, tmp2
));
379 bsi_insert_before (&bsi
, label1
, BSI_SAME_STMT
);
380 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
383 label2
= build1 (LABEL_EXPR
, void_type_node
, label_decl2
);
384 stmt1
= build2 (GIMPLE_MODIFY_STMT
, optype
, result
,
385 build2 (TREE_CODE (operation
), optype
, op1
, op2
));
386 bsi_insert_before (&bsi
, label2
, BSI_SAME_STMT
);
387 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
390 label3
= build1 (LABEL_EXPR
, void_type_node
, label_decl3
);
391 bsi_insert_before (&bsi
, label3
, BSI_SAME_STMT
);
394 /* Edge e23 connects bb2 to bb3, etc. */
395 e12
= split_block (bb
, bb1end
);
398 e23
= split_block (bb2
, bb2end
);
400 bb3
->count
= all
- count
;
401 e34
= split_block (bb3
, bb3end
);
405 e12
->flags
&= ~EDGE_FALLTHRU
;
406 e12
->flags
|= EDGE_FALSE_VALUE
;
407 e12
->probability
= prob
;
410 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
411 e13
->probability
= REG_BR_PROB_BASE
- prob
;
412 e13
->count
= all
- count
;
416 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
417 e24
->probability
= REG_BR_PROB_BASE
;
420 e34
->probability
= REG_BR_PROB_BASE
;
421 e34
->count
= all
- count
;
426 /* Do transform 2) on INSN if applicable. */
428 tree_mod_pow2_value_transform (tree stmt
)
430 stmt_ann_t ann
= get_stmt_ann (stmt
);
431 histogram_value histogram
;
433 gcov_type count
, wrong_values
, all
;
434 tree modify
, op
, op1
, op2
, result
, value
;
438 if (TREE_CODE (stmt
) == RETURN_EXPR
439 && TREE_OPERAND (stmt
, 0)
440 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == GIMPLE_MODIFY_STMT
)
441 modify
= TREE_OPERAND (stmt
, 0);
442 if (TREE_CODE (modify
) != GIMPLE_MODIFY_STMT
)
444 op
= GIMPLE_STMT_OPERAND (modify
, 1);
445 if (!INTEGRAL_TYPE_P (TREE_TYPE (op
)))
447 code
= TREE_CODE (op
);
449 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (TREE_TYPE (op
)))
452 op1
= TREE_OPERAND (op
, 0);
453 op2
= TREE_OPERAND (op
, 1);
454 if (!ann
->histograms
)
457 for (histogram
= ann
->histograms
; histogram
; histogram
= histogram
->hvalue
.next
)
458 if (histogram
->type
== HIST_TYPE_POW2
)
464 value
= histogram
->hvalue
.value
;
465 wrong_values
= histogram
->hvalue
.counters
[0];
466 count
= histogram
->hvalue
.counters
[1];
468 /* We require that we hit a power of 2 at least half of all evaluations. */
469 if (simple_cst_equal (op2
, value
) != 1 || count
< wrong_values
)
474 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
475 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
478 /* Compute probability of taking the optimal path. */
479 all
= count
+ wrong_values
;
480 if (check_counter (stmt
, "pow2", all
, bb_for_stmt (stmt
)->count
))
483 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
485 result
= tree_mod_pow2 (stmt
, op
, op1
, op2
, prob
, count
, all
);
487 GIMPLE_STMT_OPERAND (modify
, 1) = result
;
492 /* Generate code for transformations 3 and 4 (with OPERATION, operands OP1
493 and OP2, parent modify-expr STMT, and NCOUNTS the number of cases to
494 support. Currently only NCOUNTS==0 or 1 is supported and this is
495 built into this interface. The probabilities of taking the optimal
496 paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
497 COUNT2/ALL respectively within roundoff error). This generates the
498 result into a temp and returns the temp; it does not replace or alter
499 the original STMT. */
500 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
503 tree_mod_subtract (tree stmt
, tree operation
, tree op1
, tree op2
,
504 int prob1
, int prob2
, int ncounts
,
505 gcov_type count1
, gcov_type count2
, gcov_type all
)
507 tree stmt1
, stmt2
, stmt3
;
509 tree label_decl1
= create_artificial_label ();
510 tree label_decl2
= create_artificial_label ();
511 tree label_decl3
= create_artificial_label ();
512 tree label1
, label2
, label3
;
513 tree bb1end
, bb2end
= NULL_TREE
, bb3end
;
514 basic_block bb
, bb2
, bb3
, bb4
;
515 tree optype
= TREE_TYPE (operation
);
516 edge e12
, e23
= 0, e24
, e34
, e14
;
517 block_stmt_iterator bsi
;
518 tree result
= create_tmp_var (optype
, "PROF");
520 bb
= bb_for_stmt (stmt
);
521 bsi
= bsi_for_stmt (stmt
);
523 tmp1
= create_tmp_var (optype
, "PROF");
524 stmt1
= build2 (GIMPLE_MODIFY_STMT
, optype
, result
, op1
);
525 stmt2
= build2 (GIMPLE_MODIFY_STMT
, optype
, tmp1
, op2
);
526 stmt3
= build3 (COND_EXPR
, void_type_node
,
527 build2 (LT_EXPR
, boolean_type_node
, result
, tmp1
),
528 build1 (GOTO_EXPR
, void_type_node
, label_decl3
),
529 build1 (GOTO_EXPR
, void_type_node
,
530 ncounts
? label_decl1
: label_decl2
));
531 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
532 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
533 bsi_insert_before (&bsi
, stmt3
, BSI_SAME_STMT
);
536 if (ncounts
) /* Assumed to be 0 or 1 */
538 label1
= build1 (LABEL_EXPR
, void_type_node
, label_decl1
);
539 stmt1
= build2 (GIMPLE_MODIFY_STMT
, optype
, result
,
540 build2 (MINUS_EXPR
, optype
, result
, tmp1
));
541 stmt2
= build3 (COND_EXPR
, void_type_node
,
542 build2 (LT_EXPR
, boolean_type_node
, result
, tmp1
),
543 build1 (GOTO_EXPR
, void_type_node
, label_decl3
),
544 build1 (GOTO_EXPR
, void_type_node
, label_decl2
));
545 bsi_insert_before (&bsi
, label1
, BSI_SAME_STMT
);
546 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
547 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
552 label2
= build1 (LABEL_EXPR
, void_type_node
, label_decl2
);
553 stmt1
= build2 (GIMPLE_MODIFY_STMT
, optype
, result
,
554 build2 (TREE_CODE (operation
), optype
, result
, tmp1
));
555 bsi_insert_before (&bsi
, label2
, BSI_SAME_STMT
);
556 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
559 label3
= build1 (LABEL_EXPR
, void_type_node
, label_decl3
);
560 bsi_insert_before (&bsi
, label3
, BSI_SAME_STMT
);
563 /* Edge e23 connects bb2 to bb3, etc. */
564 /* However block 3 is optional; if it is not there, references
565 to 3 really refer to block 2. */
566 e12
= split_block (bb
, bb1end
);
568 bb2
->count
= all
- count1
;
570 if (ncounts
) /* Assumed to be 0 or 1. */
572 e23
= split_block (bb2
, bb2end
);
574 bb3
->count
= all
- count1
- count2
;
577 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
581 e12
->flags
&= ~EDGE_FALLTHRU
;
582 e12
->flags
|= EDGE_FALSE_VALUE
;
583 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
584 e12
->count
= all
- count1
;
586 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
587 e14
->probability
= prob1
;
590 if (ncounts
) /* Assumed to be 0 or 1. */
592 e23
->flags
&= ~EDGE_FALLTHRU
;
593 e23
->flags
|= EDGE_FALSE_VALUE
;
594 e23
->count
= all
- count1
- count2
;
595 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
597 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
598 e24
->probability
= prob2
;
602 e34
->probability
= REG_BR_PROB_BASE
;
603 e34
->count
= all
- count1
- count2
;
608 /* Do transforms 3) and 4) on INSN if applicable. */
610 tree_mod_subtract_transform (tree stmt
)
612 stmt_ann_t ann
= get_stmt_ann (stmt
);
613 histogram_value histogram
;
615 gcov_type count
, wrong_values
, all
;
616 tree modify
, op
, op1
, op2
, result
, value
;
621 if (TREE_CODE (stmt
) == RETURN_EXPR
622 && TREE_OPERAND (stmt
, 0)
623 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == GIMPLE_MODIFY_STMT
)
624 modify
= TREE_OPERAND (stmt
, 0);
625 if (TREE_CODE (modify
) != GIMPLE_MODIFY_STMT
)
627 op
= GIMPLE_STMT_OPERAND (modify
, 1);
628 if (!INTEGRAL_TYPE_P (TREE_TYPE (op
)))
630 code
= TREE_CODE (op
);
632 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (TREE_TYPE (op
)))
635 op1
= TREE_OPERAND (op
, 0);
636 op2
= TREE_OPERAND (op
, 1);
637 if (!ann
->histograms
)
640 for (histogram
= ann
->histograms
; histogram
; histogram
= histogram
->hvalue
.next
)
641 if (histogram
->type
== HIST_TYPE_INTERVAL
)
647 value
= histogram
->hvalue
.value
;
650 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
651 all
+= histogram
->hvalue
.counters
[i
];
653 wrong_values
+= histogram
->hvalue
.counters
[i
];
654 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
657 /* Compute probability of taking the optimal path. */
658 if (check_counter (stmt
, "interval", all
, bb_for_stmt (stmt
)->count
))
661 /* We require that we use just subtractions in at least 50% of all
664 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
666 count
+= histogram
->hvalue
.counters
[i
];
667 if (count
* 2 >= all
)
670 if (i
== histogram
->hdata
.intvl
.steps
)
675 fprintf (dump_file
, "Mod subtract transformation on insn ");
676 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
679 /* Compute probability of taking the optimal path(s). */
680 prob1
= (histogram
->hvalue
.counters
[0] * REG_BR_PROB_BASE
+ all
/ 2) / all
;
681 prob2
= (histogram
->hvalue
.counters
[1] * REG_BR_PROB_BASE
+ all
/ 2) / all
;
683 /* In practice, "steps" is always 2. This interface reflects this,
684 and will need to be changed if "steps" can change. */
685 result
= tree_mod_subtract (stmt
, op
, op1
, op2
, prob1
, prob2
, i
,
686 histogram
->hvalue
.counters
[0],
687 histogram
->hvalue
.counters
[1], all
);
689 GIMPLE_STMT_OPERAND (modify
, 1) = result
;
694 struct value_prof_hooks
{
695 /* Find list of values for which we want to measure histograms. */
696 void (*find_values_to_profile
) (histogram_values
*);
698 /* Identify and exploit properties of values that are hard to analyze
699 statically. See value-prof.c for more detail. */
700 bool (*value_profile_transformations
) (void);
703 /* Find values inside STMT for that we want to measure histograms for
704 division/modulo optimization. */
706 tree_divmod_values_to_profile (tree stmt
, histogram_values
*values
)
708 tree assign
, lhs
, rhs
, divisor
, op0
, type
;
709 histogram_value hist
;
711 if (TREE_CODE (stmt
) == RETURN_EXPR
)
712 assign
= TREE_OPERAND (stmt
, 0);
717 || TREE_CODE (assign
) != GIMPLE_MODIFY_STMT
)
719 lhs
= GIMPLE_STMT_OPERAND (assign
, 0);
720 type
= TREE_TYPE (lhs
);
721 if (!INTEGRAL_TYPE_P (type
))
724 rhs
= GIMPLE_STMT_OPERAND (assign
, 1);
725 switch (TREE_CODE (rhs
))
729 divisor
= TREE_OPERAND (rhs
, 1);
730 op0
= TREE_OPERAND (rhs
, 0);
732 VEC_reserve (histogram_value
, heap
, *values
, 3);
734 if (is_gimple_reg (divisor
))
736 /* Check for the case where the divisor is the same value most
738 hist
= ggc_alloc (sizeof (*hist
));
739 hist
->hvalue
.value
= divisor
;
740 hist
->hvalue
.stmt
= stmt
;
741 hist
->type
= HIST_TYPE_SINGLE_VALUE
;
742 VEC_quick_push (histogram_value
, *values
, hist
);
745 /* For mod, check whether it is not often a noop (or replaceable by
746 a few subtractions). */
747 if (TREE_CODE (rhs
) == TRUNC_MOD_EXPR
748 && TYPE_UNSIGNED (type
))
750 /* Check for a special case where the divisor is power of 2. */
751 hist
= ggc_alloc (sizeof (*hist
));
752 hist
->hvalue
.value
= divisor
;
753 hist
->hvalue
.stmt
= stmt
;
754 hist
->type
= HIST_TYPE_POW2
;
755 VEC_quick_push (histogram_value
, *values
, hist
);
757 hist
= ggc_alloc (sizeof (*hist
));
758 hist
->hvalue
.stmt
= stmt
;
760 = build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
761 hist
->type
= HIST_TYPE_INTERVAL
;
762 hist
->hdata
.intvl
.int_start
= 0;
763 hist
->hdata
.intvl
.steps
= 2;
764 VEC_quick_push (histogram_value
, *values
, hist
);
773 /* Find values inside STMT for that we want to measure histograms and adds
774 them to list VALUES. */
777 tree_values_to_profile (tree stmt
, histogram_values
*values
)
779 if (flag_value_profile_transformations
)
780 tree_divmod_values_to_profile (stmt
, values
);
784 tree_find_values_to_profile (histogram_values
*values
)
787 block_stmt_iterator bsi
;
789 histogram_value hist
;
793 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
794 tree_values_to_profile (bsi_stmt (bsi
), values
);
796 for (i
= 0; VEC_iterate (histogram_value
, *values
, i
, hist
); i
++)
800 case HIST_TYPE_INTERVAL
:
803 fprintf (dump_file
, "Interval counter for tree ");
804 print_generic_expr (dump_file
, hist
->hvalue
.stmt
,
806 fprintf (dump_file
, ", range %d -- %d.\n",
807 hist
->hdata
.intvl
.int_start
,
808 (hist
->hdata
.intvl
.int_start
809 + hist
->hdata
.intvl
.steps
- 1));
811 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
817 fprintf (dump_file
, "Pow2 counter for tree ");
818 print_generic_expr (dump_file
, hist
->hvalue
.stmt
, TDF_SLIM
);
819 fprintf (dump_file
, ".\n");
821 hist
->n_counters
= 2;
824 case HIST_TYPE_SINGLE_VALUE
:
827 fprintf (dump_file
, "Single value counter for tree ");
828 print_generic_expr (dump_file
, hist
->hvalue
.stmt
, TDF_SLIM
);
829 fprintf (dump_file
, ".\n");
831 hist
->n_counters
= 3;
834 case HIST_TYPE_CONST_DELTA
:
837 fprintf (dump_file
, "Constant delta counter for tree ");
838 print_generic_expr (dump_file
, hist
->hvalue
.stmt
, TDF_SLIM
);
839 fprintf (dump_file
, ".\n");
841 hist
->n_counters
= 4;
850 static struct value_prof_hooks tree_value_prof_hooks
= {
851 tree_find_values_to_profile
,
852 tree_value_profile_transformations
856 tree_register_value_prof_hooks (void)
858 gcc_assert (current_ir_type () == IR_GIMPLE
);
859 value_prof_hooks
= &tree_value_prof_hooks
;
862 /* IR-independent entry points. */
864 find_values_to_profile (histogram_values
*values
)
866 (value_prof_hooks
->find_values_to_profile
) (values
);
870 value_profile_transformations (void)
872 return (value_prof_hooks
->value_profile_transformations
) ();