1 /* Transformations based on profile information for values.
2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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
9 version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
15
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
19 02110-1301, USA. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "expr.h"
27 #include "hard-reg-set.h"
28 #include "basic-block.h"
29 #include "value-prof.h"
30 #include "output.h"
31 #include "flags.h"
32 #include "insn-config.h"
33 #include "recog.h"
34 #include "optabs.h"
35 #include "regs.h"
36 #include "ggc.h"
37 #include "tree-flow.h"
38 #include "tree-flow-inline.h"
39 #include "diagnostic.h"
40 #include "coverage.h"
41 #include "tree.h"
42 #include "gcov-io.h"
43 #include "timevar.h"
44 #include "tree-pass.h"
45 #include "toplev.h"
46
47 static struct value_prof_hooks *value_prof_hooks;
48
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):
52
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
60 profiling.
61
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.
67
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. */
72
73
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);
82
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. */
86 static bool
check_counter(tree stmt,const char * name,gcov_type all,gcov_type bb_count)87 check_counter (tree stmt, const char * name, gcov_type all, gcov_type bb_count)
88 {
89 if (all != bb_count)
90 {
91 location_t * locus;
92 locus = (stmt != NULL && EXPR_HAS_LOCATION (stmt)
93 ? EXPR_LOCUS (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);
97 return true;
98 }
99 return false;
100 }
101
102 /* Tree based transformations. */
103 static bool
tree_value_profile_transformations(void)104 tree_value_profile_transformations (void)
105 {
106 basic_block bb;
107 block_stmt_iterator bsi;
108 bool changed = false;
109
110 FOR_EACH_BB (bb)
111 {
112 /* Ignore cold areas -- we are enlarging the code. */
113 if (!maybe_hot_bb_p (bb))
114 continue;
115
116 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
117 {
118 tree stmt = bsi_stmt (bsi);
119 stmt_ann_t ann = get_stmt_ann (stmt);
120 histogram_value th = ann->histograms;
121 if (!th)
122 continue;
123
124 if (dump_file)
125 {
126 fprintf (dump_file, "Trying transformations on insn ");
127 print_generic_stmt (dump_file, stmt, TDF_SLIM);
128 }
129
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)))
141 {
142 changed = true;
143 /* Original statement may no longer be in the same block. */
144 if (bb != bb_for_stmt (stmt))
145 {
146 bb = bb_for_stmt (stmt);
147 bsi = bsi_for_stmt (stmt);
148 }
149 }
150
151 /* Free extra storage from compute_value_histograms. */
152 while (th)
153 {
154 free (th->hvalue.counters);
155 th = th->hvalue.next;
156 }
157 ann->histograms = 0;
158 }
159 }
160
161 if (changed)
162 {
163 counts_to_freqs ();
164 }
165
166 return changed;
167 }
168
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. */
174 static tree
tree_divmod_fixed_value(tree stmt,tree operation,tree op1,tree op2,tree value,int prob,gcov_type count,gcov_type all)175 tree_divmod_fixed_value (tree stmt, tree operation,
176 tree op1, tree op2, tree value, int prob, gcov_type count,
177 gcov_type all)
178 {
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;
190
191 bb = bb_for_stmt (stmt);
192 bsi = bsi_for_stmt (stmt);
193
194 tmpv = create_tmp_var (optype, "PROF");
195 tmp1 = create_tmp_var (optype, "PROF");
196 stmt1 = build2 (MODIFY_EXPR, optype, tmpv, fold_convert (optype, value));
197 stmt2 = build2 (MODIFY_EXPR, optype, tmp1, op2);
198 stmt3 = build3 (COND_EXPR, void_type_node,
199 build2 (NE_EXPR, boolean_type_node, tmp1, tmpv),
200 build1 (GOTO_EXPR, void_type_node, label_decl2),
201 build1 (GOTO_EXPR, void_type_node, label_decl1));
202 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
203 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
204 bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
205 bb1end = stmt3;
206
207 tmp2 = create_tmp_var (optype, "PROF");
208 label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
209 stmt1 = build2 (MODIFY_EXPR, optype, tmp2,
210 build2 (TREE_CODE (operation), optype, op1, tmpv));
211 bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
212 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
213 bb2end = stmt1;
214
215 label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
216 stmt1 = build2 (MODIFY_EXPR, optype, tmp2,
217 build2 (TREE_CODE (operation), optype, op1, op2));
218 bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
219 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
220 bb3end = stmt1;
221
222 label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
223 bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
224
225 /* Fix CFG. */
226 /* Edge e23 connects bb2 to bb3, etc. */
227 e12 = split_block (bb, bb1end);
228 bb2 = e12->dest;
229 bb2->count = count;
230 e23 = split_block (bb2, bb2end);
231 bb3 = e23->dest;
232 bb3->count = all - count;
233 e34 = split_block (bb3, bb3end);
234 bb4 = e34->dest;
235 bb4->count = all;
236
237 e12->flags &= ~EDGE_FALLTHRU;
238 e12->flags |= EDGE_FALSE_VALUE;
239 e12->probability = prob;
240 e12->count = count;
241
242 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
243 e13->probability = REG_BR_PROB_BASE - prob;
244 e13->count = all - count;
245
246 remove_edge (e23);
247
248 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
249 e24->probability = REG_BR_PROB_BASE;
250 e24->count = count;
251
252 e34->probability = REG_BR_PROB_BASE;
253 e34->count = all - count;
254
255 return tmp2;
256 }
257
258 /* Do transform 1) on INSN if applicable. */
259 static bool
tree_divmod_fixed_value_transform(tree stmt)260 tree_divmod_fixed_value_transform (tree stmt)
261 {
262 stmt_ann_t ann = get_stmt_ann (stmt);
263 histogram_value histogram;
264 enum tree_code code;
265 gcov_type val, count, all;
266 tree modify, op, op1, op2, result, value, tree_val;
267 int prob;
268
269 modify = stmt;
270 if (TREE_CODE (stmt) == RETURN_EXPR
271 && TREE_OPERAND (stmt, 0)
272 && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
273 modify = TREE_OPERAND (stmt, 0);
274 if (TREE_CODE (modify) != MODIFY_EXPR)
275 return false;
276 op = TREE_OPERAND (modify, 1);
277 if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
278 return false;
279 code = TREE_CODE (op);
280
281 if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR)
282 return false;
283
284 op1 = TREE_OPERAND (op, 0);
285 op2 = TREE_OPERAND (op, 1);
286 if (!ann->histograms)
287 return false;
288
289 for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next)
290 if (histogram->type == HIST_TYPE_SINGLE_VALUE)
291 break;
292
293 if (!histogram)
294 return false;
295
296 value = histogram->hvalue.value;
297 val = histogram->hvalue.counters[0];
298 count = histogram->hvalue.counters[1];
299 all = histogram->hvalue.counters[2];
300
301 /* We require that count is at least half of all; this means
302 that for the transformation to fire the value must be constant
303 at least 50% of time (and 75% gives the guarantee of usage). */
304 if (simple_cst_equal (op2, value) != 1 || 2 * count < all)
305 return false;
306
307 if (check_counter (stmt, "value", all, bb_for_stmt (stmt)->count))
308 return false;
309
310 /* Compute probability of taking the optimal path. */
311 prob = (count * REG_BR_PROB_BASE + all / 2) / all;
312
313 tree_val = build_int_cst_wide (get_gcov_type (),
314 (unsigned HOST_WIDE_INT) val,
315 val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
316 result = tree_divmod_fixed_value (stmt, op, op1, op2, tree_val, prob, count, all);
317
318 if (dump_file)
319 {
320 fprintf (dump_file, "Div/mod by constant ");
321 print_generic_expr (dump_file, value, TDF_SLIM);
322 fprintf (dump_file, "=");
323 print_generic_expr (dump_file, tree_val, TDF_SLIM);
324 fprintf (dump_file, " transformation on insn ");
325 print_generic_stmt (dump_file, stmt, TDF_SLIM);
326 }
327
328 TREE_OPERAND (modify, 1) = result;
329
330 return true;
331 }
332
333 /* Generate code for transformation 2 (with OPERATION, operands OP1
334 and OP2, parent modify-expr STMT and probability of taking the optimal
335 path PROB, which is equivalent to COUNT/ALL within roundoff error).
336 This generates the result into a temp and returns
337 the temp; it does not replace or alter the original STMT. */
338 static tree
tree_mod_pow2(tree stmt,tree operation,tree op1,tree op2,int prob,gcov_type count,gcov_type all)339 tree_mod_pow2 (tree stmt, tree operation, tree op1, tree op2, int prob,
340 gcov_type count, gcov_type all)
341 {
342 tree stmt1, stmt2, stmt3, stmt4;
343 tree tmp2, tmp3;
344 tree label_decl1 = create_artificial_label ();
345 tree label_decl2 = create_artificial_label ();
346 tree label_decl3 = create_artificial_label ();
347 tree label1, label2, label3;
348 tree bb1end, bb2end, bb3end;
349 basic_block bb, bb2, bb3, bb4;
350 tree optype = TREE_TYPE (operation);
351 edge e12, e13, e23, e24, e34;
352 block_stmt_iterator bsi;
353 tree result = create_tmp_var (optype, "PROF");
354
355 bb = bb_for_stmt (stmt);
356 bsi = bsi_for_stmt (stmt);
357
358 tmp2 = create_tmp_var (optype, "PROF");
359 tmp3 = create_tmp_var (optype, "PROF");
360 stmt2 = build2 (MODIFY_EXPR, optype, tmp2,
361 build2 (PLUS_EXPR, optype, op2, build_int_cst (optype, -1)));
362 stmt3 = build2 (MODIFY_EXPR, optype, tmp3,
363 build2 (BIT_AND_EXPR, optype, tmp2, op2));
364 stmt4 = build3 (COND_EXPR, void_type_node,
365 build2 (NE_EXPR, boolean_type_node,
366 tmp3, build_int_cst (optype, 0)),
367 build1 (GOTO_EXPR, void_type_node, label_decl2),
368 build1 (GOTO_EXPR, void_type_node, label_decl1));
369 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
370 bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
371 bsi_insert_before (&bsi, stmt4, BSI_SAME_STMT);
372 bb1end = stmt4;
373
374 /* tmp2 == op2-1 inherited from previous block */
375 label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
376 stmt1 = build2 (MODIFY_EXPR, optype, result,
377 build2 (BIT_AND_EXPR, optype, op1, tmp2));
378 bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
379 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
380 bb2end = stmt1;
381
382 label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
383 stmt1 = build2 (MODIFY_EXPR, optype, result,
384 build2 (TREE_CODE (operation), optype, op1, op2));
385 bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
386 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
387 bb3end = stmt1;
388
389 label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
390 bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
391
392 /* Fix CFG. */
393 /* Edge e23 connects bb2 to bb3, etc. */
394 e12 = split_block (bb, bb1end);
395 bb2 = e12->dest;
396 bb2->count = count;
397 e23 = split_block (bb2, bb2end);
398 bb3 = e23->dest;
399 bb3->count = all - count;
400 e34 = split_block (bb3, bb3end);
401 bb4 = e34->dest;
402 bb4->count = all;
403
404 e12->flags &= ~EDGE_FALLTHRU;
405 e12->flags |= EDGE_FALSE_VALUE;
406 e12->probability = prob;
407 e12->count = count;
408
409 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
410 e13->probability = REG_BR_PROB_BASE - prob;
411 e13->count = all - count;
412
413 remove_edge (e23);
414
415 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
416 e24->probability = REG_BR_PROB_BASE;
417 e24->count = count;
418
419 e34->probability = REG_BR_PROB_BASE;
420 e34->count = all - count;
421
422 return result;
423 }
424
425 /* Do transform 2) on INSN if applicable. */
426 static bool
tree_mod_pow2_value_transform(tree stmt)427 tree_mod_pow2_value_transform (tree stmt)
428 {
429 stmt_ann_t ann = get_stmt_ann (stmt);
430 histogram_value histogram;
431 enum tree_code code;
432 gcov_type count, wrong_values, all;
433 tree modify, op, op1, op2, result, value;
434 int prob;
435
436 modify = stmt;
437 if (TREE_CODE (stmt) == RETURN_EXPR
438 && TREE_OPERAND (stmt, 0)
439 && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
440 modify = TREE_OPERAND (stmt, 0);
441 if (TREE_CODE (modify) != MODIFY_EXPR)
442 return false;
443 op = TREE_OPERAND (modify, 1);
444 if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
445 return false;
446 code = TREE_CODE (op);
447
448 if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op)))
449 return false;
450
451 op1 = TREE_OPERAND (op, 0);
452 op2 = TREE_OPERAND (op, 1);
453 if (!ann->histograms)
454 return false;
455
456 for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next)
457 if (histogram->type == HIST_TYPE_POW2)
458 break;
459
460 if (!histogram)
461 return false;
462
463 value = histogram->hvalue.value;
464 wrong_values = histogram->hvalue.counters[0];
465 count = histogram->hvalue.counters[1];
466
467 /* We require that we hit a power of 2 at least half of all evaluations. */
468 if (simple_cst_equal (op2, value) != 1 || count < wrong_values)
469 return false;
470
471 if (dump_file)
472 {
473 fprintf (dump_file, "Mod power of 2 transformation on insn ");
474 print_generic_stmt (dump_file, stmt, TDF_SLIM);
475 }
476
477 /* Compute probability of taking the optimal path. */
478 all = count + wrong_values;
479 if (check_counter (stmt, "pow2", all, bb_for_stmt (stmt)->count))
480 return false;
481
482 prob = (count * REG_BR_PROB_BASE + all / 2) / all;
483
484 result = tree_mod_pow2 (stmt, op, op1, op2, prob, count, all);
485
486 TREE_OPERAND (modify, 1) = result;
487
488 return true;
489 }
490
491 /* Generate code for transformations 3 and 4 (with OPERATION, operands OP1
492 and OP2, parent modify-expr STMT, and NCOUNTS the number of cases to
493 support. Currently only NCOUNTS==0 or 1 is supported and this is
494 built into this interface. The probabilities of taking the optimal
495 paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
496 COUNT2/ALL respectively within roundoff error). This generates the
497 result into a temp and returns the temp; it does not replace or alter
498 the original STMT. */
499 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
500
501 static tree
tree_mod_subtract(tree stmt,tree operation,tree op1,tree op2,int prob1,int prob2,int ncounts,gcov_type count1,gcov_type count2,gcov_type all)502 tree_mod_subtract (tree stmt, tree operation, tree op1, tree op2,
503 int prob1, int prob2, int ncounts,
504 gcov_type count1, gcov_type count2, gcov_type all)
505 {
506 tree stmt1, stmt2, stmt3;
507 tree tmp1;
508 tree label_decl1 = create_artificial_label ();
509 tree label_decl2 = create_artificial_label ();
510 tree label_decl3 = create_artificial_label ();
511 tree label1, label2, label3;
512 tree bb1end, bb2end = NULL_TREE, bb3end;
513 basic_block bb, bb2, bb3, bb4;
514 tree optype = TREE_TYPE (operation);
515 edge e12, e23 = 0, e24, e34, e14;
516 block_stmt_iterator bsi;
517 tree result = create_tmp_var (optype, "PROF");
518
519 bb = bb_for_stmt (stmt);
520 bsi = bsi_for_stmt (stmt);
521
522 tmp1 = create_tmp_var (optype, "PROF");
523 stmt1 = build2 (MODIFY_EXPR, optype, result, op1);
524 stmt2 = build2 (MODIFY_EXPR, optype, tmp1, op2);
525 stmt3 = build3 (COND_EXPR, void_type_node,
526 build2 (LT_EXPR, boolean_type_node, result, tmp1),
527 build1 (GOTO_EXPR, void_type_node, label_decl3),
528 build1 (GOTO_EXPR, void_type_node,
529 ncounts ? label_decl1 : label_decl2));
530 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
531 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
532 bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
533 bb1end = stmt3;
534
535 if (ncounts) /* Assumed to be 0 or 1 */
536 {
537 label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
538 stmt1 = build2 (MODIFY_EXPR, optype, result,
539 build2 (MINUS_EXPR, optype, result, tmp1));
540 stmt2 = build3 (COND_EXPR, void_type_node,
541 build2 (LT_EXPR, boolean_type_node, result, tmp1),
542 build1 (GOTO_EXPR, void_type_node, label_decl3),
543 build1 (GOTO_EXPR, void_type_node, label_decl2));
544 bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
545 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
546 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
547 bb2end = stmt2;
548 }
549
550 /* Fallback case. */
551 label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
552 stmt1 = build2 (MODIFY_EXPR, optype, result,
553 build2 (TREE_CODE (operation), optype, result, tmp1));
554 bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
555 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
556 bb3end = stmt1;
557
558 label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
559 bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
560
561 /* Fix CFG. */
562 /* Edge e23 connects bb2 to bb3, etc. */
563 /* However block 3 is optional; if it is not there, references
564 to 3 really refer to block 2. */
565 e12 = split_block (bb, bb1end);
566 bb2 = e12->dest;
567 bb2->count = all - count1;
568
569 if (ncounts) /* Assumed to be 0 or 1. */
570 {
571 e23 = split_block (bb2, bb2end);
572 bb3 = e23->dest;
573 bb3->count = all - count1 - count2;
574 }
575
576 e34 = split_block (ncounts ? bb3 : bb2, bb3end);
577 bb4 = e34->dest;
578 bb4->count = all;
579
580 e12->flags &= ~EDGE_FALLTHRU;
581 e12->flags |= EDGE_FALSE_VALUE;
582 e12->probability = REG_BR_PROB_BASE - prob1;
583 e12->count = all - count1;
584
585 e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE);
586 e14->probability = prob1;
587 e14->count = count1;
588
589 if (ncounts) /* Assumed to be 0 or 1. */
590 {
591 e23->flags &= ~EDGE_FALLTHRU;
592 e23->flags |= EDGE_FALSE_VALUE;
593 e23->count = all - count1 - count2;
594 e23->probability = REG_BR_PROB_BASE - prob2;
595
596 e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE);
597 e24->probability = prob2;
598 e24->count = count2;
599 }
600
601 e34->probability = REG_BR_PROB_BASE;
602 e34->count = all - count1 - count2;
603
604 return result;
605 }
606
607 /* Do transforms 3) and 4) on INSN if applicable. */
608 static bool
tree_mod_subtract_transform(tree stmt)609 tree_mod_subtract_transform (tree stmt)
610 {
611 stmt_ann_t ann = get_stmt_ann (stmt);
612 histogram_value histogram;
613 enum tree_code code;
614 gcov_type count, wrong_values, all;
615 tree modify, op, op1, op2, result, value;
616 int prob1, prob2;
617 unsigned int i;
618
619 modify = stmt;
620 if (TREE_CODE (stmt) == RETURN_EXPR
621 && TREE_OPERAND (stmt, 0)
622 && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
623 modify = TREE_OPERAND (stmt, 0);
624 if (TREE_CODE (modify) != MODIFY_EXPR)
625 return false;
626 op = TREE_OPERAND (modify, 1);
627 if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
628 return false;
629 code = TREE_CODE (op);
630
631 if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op)))
632 return false;
633
634 op1 = TREE_OPERAND (op, 0);
635 op2 = TREE_OPERAND (op, 1);
636 if (!ann->histograms)
637 return false;
638
639 for (histogram = ann->histograms; histogram; histogram = histogram->hvalue.next)
640 if (histogram->type == HIST_TYPE_INTERVAL)
641 break;
642
643 if (!histogram)
644 return false;
645
646 value = histogram->hvalue.value;
647 all = 0;
648 wrong_values = 0;
649 for (i = 0; i < histogram->hdata.intvl.steps; i++)
650 all += histogram->hvalue.counters[i];
651
652 wrong_values += histogram->hvalue.counters[i];
653 wrong_values += histogram->hvalue.counters[i+1];
654 all += wrong_values;
655
656 /* Compute probability of taking the optimal path. */
657 if (check_counter (stmt, "interval", all, bb_for_stmt (stmt)->count))
658 return false;
659
660 /* We require that we use just subtractions in at least 50% of all
661 evaluations. */
662 count = 0;
663 for (i = 0; i < histogram->hdata.intvl.steps; i++)
664 {
665 count += histogram->hvalue.counters[i];
666 if (count * 2 >= all)
667 break;
668 }
669 if (i == histogram->hdata.intvl.steps)
670 return false;
671
672 if (dump_file)
673 {
674 fprintf (dump_file, "Mod subtract transformation on insn ");
675 print_generic_stmt (dump_file, stmt, TDF_SLIM);
676 }
677
678 /* Compute probability of taking the optimal path(s). */
679 prob1 = (histogram->hvalue.counters[0] * REG_BR_PROB_BASE + all / 2) / all;
680 prob2 = (histogram->hvalue.counters[1] * REG_BR_PROB_BASE + all / 2) / all;
681
682 /* In practice, "steps" is always 2. This interface reflects this,
683 and will need to be changed if "steps" can change. */
684 result = tree_mod_subtract (stmt, op, op1, op2, prob1, prob2, i,
685 histogram->hvalue.counters[0],
686 histogram->hvalue.counters[1], all);
687
688 TREE_OPERAND (modify, 1) = result;
689
690 return true;
691 }
692
693 struct value_prof_hooks {
694 /* Find list of values for which we want to measure histograms. */
695 void (*find_values_to_profile) (histogram_values *);
696
697 /* Identify and exploit properties of values that are hard to analyze
698 statically. See value-prof.c for more detail. */
699 bool (*value_profile_transformations) (void);
700 };
701
702 /* Find values inside STMT for that we want to measure histograms for
703 division/modulo optimization. */
704 static void
tree_divmod_values_to_profile(tree stmt,histogram_values * values)705 tree_divmod_values_to_profile (tree stmt, histogram_values *values)
706 {
707 tree assign, lhs, rhs, divisor, op0, type;
708 histogram_value hist;
709
710 if (TREE_CODE (stmt) == RETURN_EXPR)
711 assign = TREE_OPERAND (stmt, 0);
712 else
713 assign = stmt;
714
715 if (!assign
716 || TREE_CODE (assign) != MODIFY_EXPR)
717 return;
718 lhs = TREE_OPERAND (assign, 0);
719 type = TREE_TYPE (lhs);
720 if (!INTEGRAL_TYPE_P (type))
721 return;
722
723 rhs = TREE_OPERAND (assign, 1);
724 switch (TREE_CODE (rhs))
725 {
726 case TRUNC_DIV_EXPR:
727 case TRUNC_MOD_EXPR:
728 divisor = TREE_OPERAND (rhs, 1);
729 op0 = TREE_OPERAND (rhs, 0);
730
731 VEC_reserve (histogram_value, heap, *values, 3);
732
733 if (is_gimple_reg (divisor))
734 {
735 /* Check for the case where the divisor is the same value most
736 of the time. */
737 hist = ggc_alloc (sizeof (*hist));
738 hist->hvalue.value = divisor;
739 hist->hvalue.stmt = stmt;
740 hist->type = HIST_TYPE_SINGLE_VALUE;
741 VEC_quick_push (histogram_value, *values, hist);
742 }
743
744 /* For mod, check whether it is not often a noop (or replaceable by
745 a few subtractions). */
746 if (TREE_CODE (rhs) == TRUNC_MOD_EXPR
747 && TYPE_UNSIGNED (type))
748 {
749 /* Check for a special case where the divisor is power of 2. */
750 hist = ggc_alloc (sizeof (*hist));
751 hist->hvalue.value = divisor;
752 hist->hvalue.stmt = stmt;
753 hist->type = HIST_TYPE_POW2;
754 VEC_quick_push (histogram_value, *values, hist);
755
756 hist = ggc_alloc (sizeof (*hist));
757 hist->hvalue.stmt = stmt;
758 hist->hvalue.value
759 = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
760 hist->type = HIST_TYPE_INTERVAL;
761 hist->hdata.intvl.int_start = 0;
762 hist->hdata.intvl.steps = 2;
763 VEC_quick_push (histogram_value, *values, hist);
764 }
765 return;
766
767 default:
768 return;
769 }
770 }
771
772 /* Find values inside STMT for that we want to measure histograms and adds
773 them to list VALUES. */
774
775 static void
tree_values_to_profile(tree stmt,histogram_values * values)776 tree_values_to_profile (tree stmt, histogram_values *values)
777 {
778 if (flag_value_profile_transformations)
779 tree_divmod_values_to_profile (stmt, values);
780 }
781
782 static void
tree_find_values_to_profile(histogram_values * values)783 tree_find_values_to_profile (histogram_values *values)
784 {
785 basic_block bb;
786 block_stmt_iterator bsi;
787 unsigned i;
788 histogram_value hist;
789
790 *values = NULL;
791 FOR_EACH_BB (bb)
792 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
793 tree_values_to_profile (bsi_stmt (bsi), values);
794
795 for (i = 0; VEC_iterate (histogram_value, *values, i, hist); i++)
796 {
797 switch (hist->type)
798 {
799 case HIST_TYPE_INTERVAL:
800 if (dump_file)
801 {
802 fprintf (dump_file, "Interval counter for tree ");
803 print_generic_expr (dump_file, hist->hvalue.stmt,
804 TDF_SLIM);
805 fprintf (dump_file, ", range %d -- %d.\n",
806 hist->hdata.intvl.int_start,
807 (hist->hdata.intvl.int_start
808 + hist->hdata.intvl.steps - 1));
809 }
810 hist->n_counters = hist->hdata.intvl.steps + 2;
811 break;
812
813 case HIST_TYPE_POW2:
814 if (dump_file)
815 {
816 fprintf (dump_file, "Pow2 counter for tree ");
817 print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
818 fprintf (dump_file, ".\n");
819 }
820 hist->n_counters = 2;
821 break;
822
823 case HIST_TYPE_SINGLE_VALUE:
824 if (dump_file)
825 {
826 fprintf (dump_file, "Single value counter for tree ");
827 print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
828 fprintf (dump_file, ".\n");
829 }
830 hist->n_counters = 3;
831 break;
832
833 case HIST_TYPE_CONST_DELTA:
834 if (dump_file)
835 {
836 fprintf (dump_file, "Constant delta counter for tree ");
837 print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
838 fprintf (dump_file, ".\n");
839 }
840 hist->n_counters = 4;
841 break;
842
843 default:
844 gcc_unreachable ();
845 }
846 }
847 }
848
849 static struct value_prof_hooks tree_value_prof_hooks = {
850 tree_find_values_to_profile,
851 tree_value_profile_transformations
852 };
853
854 void
tree_register_value_prof_hooks(void)855 tree_register_value_prof_hooks (void)
856 {
857 value_prof_hooks = &tree_value_prof_hooks;
858 gcc_assert (ir_type ());
859 }
860
861 /* IR-independent entry points. */
862 void
find_values_to_profile(histogram_values * values)863 find_values_to_profile (histogram_values *values)
864 {
865 (value_prof_hooks->find_values_to_profile) (values);
866 }
867
868 bool
value_profile_transformations(void)869 value_profile_transformations (void)
870 {
871 return (value_prof_hooks->value_profile_transformations) ();
872 }
873
874
875