1 /* Transformations based on profile information for values.
2 Copyright (C) 2003-2020 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 3, 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 COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
19
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "rtl.h"
25 #include "tree.h"
26 #include "gimple.h"
27 #include "cfghooks.h"
28 #include "ssa.h"
29 #include "cgraph.h"
30 #include "coverage.h"
31 #include "data-streamer.h"
32 #include "diagnostic.h"
33 #include "fold-const.h"
34 #include "tree-nested.h"
35 #include "calls.h"
36 #include "expr.h"
37 #include "value-prof.h"
38 #include "tree-eh.h"
39 #include "gimplify.h"
40 #include "gimple-iterator.h"
41 #include "tree-cfg.h"
42 #include "gimple-pretty-print.h"
43 #include "dumpfile.h"
44 #include "builtins.h"
45
46 /* In this file value profile based optimizations are placed. Currently the
47 following optimizations are implemented (for more detailed descriptions
48 see comments at value_profile_transformations):
49
50 1) Division/modulo specialization. Provided that we can determine that the
51 operands of the division have some special properties, we may use it to
52 produce more effective code.
53
54 2) Indirect/virtual call specialization. If we can determine most
55 common function callee in indirect/virtual call. We can use this
56 information to improve code effectiveness (especially info for
57 the inliner).
58
59 3) 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.
62 FIXME: This transformation was removed together with RTL based value
63 profiling.
64
65
66 Value profiling internals
67 ==========================
68
69 Every value profiling transformation starts with defining what values
70 to profile. There are different histogram types (see HIST_TYPE_* in
71 value-prof.h) and each transformation can request one or more histogram
72 types per GIMPLE statement. The function gimple_find_values_to_profile()
73 collects the values to profile in a vec, and adds the number of counters
74 required for the different histogram types.
75
76 For a -fprofile-generate run, the statements for which values should be
77 recorded, are instrumented in instrument_values(). The instrumentation
78 is done by helper functions that can be found in tree-profile.c, where
79 new types of histograms can be added if necessary.
80
81 After a -fprofile-use, the value profiling data is read back in by
82 compute_value_histograms() that translates the collected data to
83 histograms and attaches them to the profiled statements via
84 gimple_add_histogram_value(). Histograms are stored in a hash table
85 that is attached to every intrumented function, see VALUE_HISTOGRAMS
86 in function.h.
87
88 The value-profile transformations driver is the function
89 gimple_value_profile_transformations(). It traverses all statements in
90 the to-be-transformed function, and looks for statements with one or
91 more histograms attached to it. If a statement has histograms, the
92 transformation functions are called on the statement.
93
94 Limitations / FIXME / TODO:
95 * Only one histogram of each type can be associated with a statement.
96 * Some value profile transformations are done in builtins.c (?!)
97 * Updating of histograms needs some TLC.
98 * The value profiling code could be used to record analysis results
99 from non-profiling (e.g. VRP).
100 * Adding new profilers should be simplified, starting with a cleanup
101 of what-happens-where and with making gimple_find_values_to_profile
102 and gimple_value_profile_transformations table-driven, perhaps...
103 */
104
105 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator *);
106 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator *);
107 static bool gimple_mod_subtract_transform (gimple_stmt_iterator *);
108 static bool gimple_stringops_transform (gimple_stmt_iterator *);
109 static void dump_ic_profile (gimple_stmt_iterator *gsi);
110
111 /* Allocate histogram value. */
112
113 histogram_value
gimple_alloc_histogram_value(struct function * fun ATTRIBUTE_UNUSED,enum hist_type type,gimple * stmt,tree value)114 gimple_alloc_histogram_value (struct function *fun ATTRIBUTE_UNUSED,
115 enum hist_type type, gimple *stmt, tree value)
116 {
117 histogram_value hist = (histogram_value) xcalloc (1, sizeof (*hist));
118 hist->hvalue.value = value;
119 hist->hvalue.stmt = stmt;
120 hist->type = type;
121 return hist;
122 }
123
124 /* Hash value for histogram. */
125
126 static hashval_t
histogram_hash(const void * x)127 histogram_hash (const void *x)
128 {
129 return htab_hash_pointer (((const_histogram_value)x)->hvalue.stmt);
130 }
131
132 /* Return nonzero if statement for histogram_value X is Y. */
133
134 static int
histogram_eq(const void * x,const void * y)135 histogram_eq (const void *x, const void *y)
136 {
137 return ((const_histogram_value) x)->hvalue.stmt == (const gimple *) y;
138 }
139
140 /* Set histogram for STMT. */
141
142 static void
set_histogram_value(struct function * fun,gimple * stmt,histogram_value hist)143 set_histogram_value (struct function *fun, gimple *stmt, histogram_value hist)
144 {
145 void **loc;
146 if (!hist && !VALUE_HISTOGRAMS (fun))
147 return;
148 if (!VALUE_HISTOGRAMS (fun))
149 VALUE_HISTOGRAMS (fun) = htab_create (1, histogram_hash,
150 histogram_eq, NULL);
151 loc = htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun), stmt,
152 htab_hash_pointer (stmt),
153 hist ? INSERT : NO_INSERT);
154 if (!hist)
155 {
156 if (loc)
157 htab_clear_slot (VALUE_HISTOGRAMS (fun), loc);
158 return;
159 }
160 *loc = hist;
161 }
162
163 /* Get histogram list for STMT. */
164
165 histogram_value
gimple_histogram_value(struct function * fun,gimple * stmt)166 gimple_histogram_value (struct function *fun, gimple *stmt)
167 {
168 if (!VALUE_HISTOGRAMS (fun))
169 return NULL;
170 return (histogram_value) htab_find_with_hash (VALUE_HISTOGRAMS (fun), stmt,
171 htab_hash_pointer (stmt));
172 }
173
174 /* Add histogram for STMT. */
175
176 void
gimple_add_histogram_value(struct function * fun,gimple * stmt,histogram_value hist)177 gimple_add_histogram_value (struct function *fun, gimple *stmt,
178 histogram_value hist)
179 {
180 hist->hvalue.next = gimple_histogram_value (fun, stmt);
181 set_histogram_value (fun, stmt, hist);
182 hist->fun = fun;
183 }
184
185 /* Remove histogram HIST from STMT's histogram list. */
186
187 void
gimple_remove_histogram_value(struct function * fun,gimple * stmt,histogram_value hist)188 gimple_remove_histogram_value (struct function *fun, gimple *stmt,
189 histogram_value hist)
190 {
191 histogram_value hist2 = gimple_histogram_value (fun, stmt);
192 if (hist == hist2)
193 {
194 set_histogram_value (fun, stmt, hist->hvalue.next);
195 }
196 else
197 {
198 while (hist2->hvalue.next != hist)
199 hist2 = hist2->hvalue.next;
200 hist2->hvalue.next = hist->hvalue.next;
201 }
202 free (hist->hvalue.counters);
203 if (flag_checking)
204 memset (hist, 0xab, sizeof (*hist));
205 free (hist);
206 }
207
208 /* Lookup histogram of type TYPE in the STMT. */
209
210 histogram_value
gimple_histogram_value_of_type(struct function * fun,gimple * stmt,enum hist_type type)211 gimple_histogram_value_of_type (struct function *fun, gimple *stmt,
212 enum hist_type type)
213 {
214 histogram_value hist;
215 for (hist = gimple_histogram_value (fun, stmt); hist;
216 hist = hist->hvalue.next)
217 if (hist->type == type)
218 return hist;
219 return NULL;
220 }
221
222 /* Dump information about HIST to DUMP_FILE. */
223
224 static void
dump_histogram_value(FILE * dump_file,histogram_value hist)225 dump_histogram_value (FILE *dump_file, histogram_value hist)
226 {
227 switch (hist->type)
228 {
229 case HIST_TYPE_INTERVAL:
230 if (hist->hvalue.counters)
231 {
232 fprintf (dump_file, "Interval counter range [%d,%d]: [",
233 hist->hdata.intvl.int_start,
234 (hist->hdata.intvl.int_start
235 + hist->hdata.intvl.steps - 1));
236
237 unsigned int i;
238 for (i = 0; i < hist->hdata.intvl.steps; i++)
239 {
240 fprintf (dump_file, "%d:%" PRId64,
241 hist->hdata.intvl.int_start + i,
242 (int64_t) hist->hvalue.counters[i]);
243 if (i != hist->hdata.intvl.steps - 1)
244 fprintf (dump_file, ", ");
245 }
246 fprintf (dump_file, "] outside range: %" PRId64 ".\n",
247 (int64_t) hist->hvalue.counters[i]);
248 }
249 break;
250
251 case HIST_TYPE_POW2:
252 if (hist->hvalue.counters)
253 fprintf (dump_file, "Pow2 counter pow2:%" PRId64
254 " nonpow2:%" PRId64 ".\n",
255 (int64_t) hist->hvalue.counters[1],
256 (int64_t) hist->hvalue.counters[0]);
257 break;
258
259 case HIST_TYPE_TOPN_VALUES:
260 case HIST_TYPE_INDIR_CALL:
261 if (hist->hvalue.counters)
262 {
263 fprintf (dump_file,
264 (hist->type == HIST_TYPE_TOPN_VALUES
265 ? "Top N value counter" : "Indirect call counter"));
266 if (hist->hvalue.counters)
267 {
268 fprintf (dump_file, " all: %" PRId64 "%s, values: ",
269 (int64_t) abs_hwi (hist->hvalue.counters[0]),
270 hist->hvalue.counters[0] < 0
271 ? " (values missing)": "");
272 for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++)
273 {
274 fprintf (dump_file, "[%" PRId64 ":%" PRId64 "]",
275 (int64_t) hist->hvalue.counters[2 * i + 1],
276 (int64_t) hist->hvalue.counters[2 * i + 2]);
277 if (i != GCOV_TOPN_VALUES - 1)
278 fprintf (dump_file, ", ");
279 }
280 fprintf (dump_file, ".\n");
281 }
282 }
283 break;
284
285 case HIST_TYPE_AVERAGE:
286 if (hist->hvalue.counters)
287 fprintf (dump_file, "Average value sum:%" PRId64
288 " times:%" PRId64 ".\n",
289 (int64_t) hist->hvalue.counters[0],
290 (int64_t) hist->hvalue.counters[1]);
291 break;
292
293 case HIST_TYPE_IOR:
294 if (hist->hvalue.counters)
295 fprintf (dump_file, "IOR value ior:%" PRId64 ".\n",
296 (int64_t) hist->hvalue.counters[0]);
297 break;
298
299 case HIST_TYPE_TIME_PROFILE:
300 if (hist->hvalue.counters)
301 fprintf (dump_file, "Time profile time:%" PRId64 ".\n",
302 (int64_t) hist->hvalue.counters[0]);
303 break;
304 default:
305 gcc_unreachable ();
306 }
307 }
308
309 /* Dump information about HIST to DUMP_FILE. */
310
311 void
stream_out_histogram_value(struct output_block * ob,histogram_value hist)312 stream_out_histogram_value (struct output_block *ob, histogram_value hist)
313 {
314 struct bitpack_d bp;
315 unsigned int i;
316
317 bp = bitpack_create (ob->main_stream);
318 bp_pack_enum (&bp, hist_type, HIST_TYPE_MAX, hist->type);
319 bp_pack_value (&bp, hist->hvalue.next != NULL, 1);
320 streamer_write_bitpack (&bp);
321 switch (hist->type)
322 {
323 case HIST_TYPE_INTERVAL:
324 streamer_write_hwi (ob, hist->hdata.intvl.int_start);
325 streamer_write_uhwi (ob, hist->hdata.intvl.steps);
326 break;
327 default:
328 break;
329 }
330 for (i = 0; i < hist->n_counters; i++)
331 {
332 /* When user uses an unsigned type with a big value, constant converted
333 to gcov_type (a signed type) can be negative. */
334 gcov_type value = hist->hvalue.counters[i];
335 if (hist->type == HIST_TYPE_TOPN_VALUES
336 || hist->type == HIST_TYPE_IOR)
337 /* Note that the IOR counter tracks pointer values and these can have
338 sign bit set. */
339 ;
340 else
341 gcc_assert (value >= 0);
342
343 streamer_write_gcov_count (ob, value);
344 }
345 if (hist->hvalue.next)
346 stream_out_histogram_value (ob, hist->hvalue.next);
347 }
348
349 /* Dump information about HIST to DUMP_FILE. */
350
351 void
stream_in_histogram_value(class lto_input_block * ib,gimple * stmt)352 stream_in_histogram_value (class lto_input_block *ib, gimple *stmt)
353 {
354 enum hist_type type;
355 unsigned int ncounters = 0;
356 struct bitpack_d bp;
357 unsigned int i;
358 histogram_value new_val;
359 bool next;
360 histogram_value *next_p = NULL;
361
362 do
363 {
364 bp = streamer_read_bitpack (ib);
365 type = bp_unpack_enum (&bp, hist_type, HIST_TYPE_MAX);
366 next = bp_unpack_value (&bp, 1);
367 new_val = gimple_alloc_histogram_value (cfun, type, stmt);
368 switch (type)
369 {
370 case HIST_TYPE_INTERVAL:
371 new_val->hdata.intvl.int_start = streamer_read_hwi (ib);
372 new_val->hdata.intvl.steps = streamer_read_uhwi (ib);
373 ncounters = new_val->hdata.intvl.steps + 2;
374 break;
375
376 case HIST_TYPE_POW2:
377 case HIST_TYPE_AVERAGE:
378 ncounters = 2;
379 break;
380
381 case HIST_TYPE_TOPN_VALUES:
382 case HIST_TYPE_INDIR_CALL:
383 ncounters = GCOV_TOPN_VALUES_COUNTERS;
384 break;
385
386 case HIST_TYPE_IOR:
387 case HIST_TYPE_TIME_PROFILE:
388 ncounters = 1;
389 break;
390
391 default:
392 gcc_unreachable ();
393 }
394 new_val->hvalue.counters = XNEWVAR (gcov_type,
395 sizeof (*new_val->hvalue.counters)
396 * ncounters);
397 new_val->n_counters = ncounters;
398 for (i = 0; i < ncounters; i++)
399 new_val->hvalue.counters[i] = streamer_read_gcov_count (ib);
400 if (!next_p)
401 gimple_add_histogram_value (cfun, stmt, new_val);
402 else
403 *next_p = new_val;
404 next_p = &new_val->hvalue.next;
405 }
406 while (next);
407 }
408
409 /* Dump all histograms attached to STMT to DUMP_FILE. */
410
411 void
dump_histograms_for_stmt(struct function * fun,FILE * dump_file,gimple * stmt)412 dump_histograms_for_stmt (struct function *fun, FILE *dump_file, gimple *stmt)
413 {
414 histogram_value hist;
415 for (hist = gimple_histogram_value (fun, stmt); hist; hist = hist->hvalue.next)
416 dump_histogram_value (dump_file, hist);
417 }
418
419 /* Remove all histograms associated with STMT. */
420
421 void
gimple_remove_stmt_histograms(struct function * fun,gimple * stmt)422 gimple_remove_stmt_histograms (struct function *fun, gimple *stmt)
423 {
424 histogram_value val;
425 while ((val = gimple_histogram_value (fun, stmt)) != NULL)
426 gimple_remove_histogram_value (fun, stmt, val);
427 }
428
429 /* Duplicate all histograms associates with OSTMT to STMT. */
430
431 void
gimple_duplicate_stmt_histograms(struct function * fun,gimple * stmt,struct function * ofun,gimple * ostmt)432 gimple_duplicate_stmt_histograms (struct function *fun, gimple *stmt,
433 struct function *ofun, gimple *ostmt)
434 {
435 histogram_value val;
436 for (val = gimple_histogram_value (ofun, ostmt); val != NULL; val = val->hvalue.next)
437 {
438 histogram_value new_val = gimple_alloc_histogram_value (fun, val->type);
439 memcpy (new_val, val, sizeof (*val));
440 new_val->hvalue.stmt = stmt;
441 new_val->hvalue.counters = XNEWVAR (gcov_type, sizeof (*new_val->hvalue.counters) * new_val->n_counters);
442 memcpy (new_val->hvalue.counters, val->hvalue.counters, sizeof (*new_val->hvalue.counters) * new_val->n_counters);
443 gimple_add_histogram_value (fun, stmt, new_val);
444 }
445 }
446
447 /* Move all histograms associated with OSTMT to STMT. */
448
449 void
gimple_move_stmt_histograms(struct function * fun,gimple * stmt,gimple * ostmt)450 gimple_move_stmt_histograms (struct function *fun, gimple *stmt, gimple *ostmt)
451 {
452 histogram_value val = gimple_histogram_value (fun, ostmt);
453 if (val)
454 {
455 /* The following three statements can't be reordered,
456 because histogram hashtab relies on stmt field value
457 for finding the exact slot. */
458 set_histogram_value (fun, ostmt, NULL);
459 for (; val != NULL; val = val->hvalue.next)
460 val->hvalue.stmt = stmt;
461 set_histogram_value (fun, stmt, val);
462 }
463 }
464
465 static bool error_found = false;
466
467 /* Helper function for verify_histograms. For each histogram reachable via htab
468 walk verify that it was reached via statement walk. */
469
470 static int
visit_hist(void ** slot,void * data)471 visit_hist (void **slot, void *data)
472 {
473 hash_set<histogram_value> *visited = (hash_set<histogram_value> *) data;
474 histogram_value hist = *(histogram_value *) slot;
475
476 if (!visited->contains (hist)
477 && hist->type != HIST_TYPE_TIME_PROFILE)
478 {
479 error ("dead histogram");
480 dump_histogram_value (stderr, hist);
481 debug_gimple_stmt (hist->hvalue.stmt);
482 error_found = true;
483 }
484 return 1;
485 }
486
487 /* Verify sanity of the histograms. */
488
489 DEBUG_FUNCTION void
verify_histograms(void)490 verify_histograms (void)
491 {
492 basic_block bb;
493 gimple_stmt_iterator gsi;
494 histogram_value hist;
495
496 error_found = false;
497 hash_set<histogram_value> visited_hists;
498 FOR_EACH_BB_FN (bb, cfun)
499 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
500 {
501 gimple *stmt = gsi_stmt (gsi);
502
503 for (hist = gimple_histogram_value (cfun, stmt); hist;
504 hist = hist->hvalue.next)
505 {
506 if (hist->hvalue.stmt != stmt)
507 {
508 error ("histogram value statement does not correspond to "
509 "the statement it is associated with");
510 debug_gimple_stmt (stmt);
511 dump_histogram_value (stderr, hist);
512 error_found = true;
513 }
514 visited_hists.add (hist);
515 }
516 }
517 if (VALUE_HISTOGRAMS (cfun))
518 htab_traverse (VALUE_HISTOGRAMS (cfun), visit_hist, &visited_hists);
519 if (error_found)
520 internal_error ("%qs failed", __func__);
521 }
522
523 /* Helper function for verify_histograms. For each histogram reachable via htab
524 walk verify that it was reached via statement walk. */
525
526 static int
free_hist(void ** slot,void * data ATTRIBUTE_UNUSED)527 free_hist (void **slot, void *data ATTRIBUTE_UNUSED)
528 {
529 histogram_value hist = *(histogram_value *) slot;
530 free (hist->hvalue.counters);
531 free (hist);
532 return 1;
533 }
534
535 void
free_histograms(struct function * fn)536 free_histograms (struct function *fn)
537 {
538 if (VALUE_HISTOGRAMS (fn))
539 {
540 htab_traverse (VALUE_HISTOGRAMS (fn), free_hist, NULL);
541 htab_delete (VALUE_HISTOGRAMS (fn));
542 VALUE_HISTOGRAMS (fn) = NULL;
543 }
544 }
545
546 /* The overall number of invocations of the counter should match
547 execution count of basic block. Report it as error rather than
548 internal error as it might mean that user has misused the profile
549 somehow. */
550
551 static bool
check_counter(gimple * stmt,const char * name,gcov_type * count,gcov_type * all,profile_count bb_count_d)552 check_counter (gimple *stmt, const char * name,
553 gcov_type *count, gcov_type *all, profile_count bb_count_d)
554 {
555 gcov_type bb_count = bb_count_d.ipa ().to_gcov_type ();
556 if (*all != bb_count || *count > *all)
557 {
558 dump_user_location_t locus;
559 locus = ((stmt != NULL)
560 ? dump_user_location_t (stmt)
561 : dump_user_location_t::from_function_decl
562 (current_function_decl));
563 if (flag_profile_correction)
564 {
565 if (dump_enabled_p ())
566 dump_printf_loc (MSG_MISSED_OPTIMIZATION, locus,
567 "correcting inconsistent value profile: %s "
568 "profiler overall count (%d) does not match BB "
569 "count (%d)\n", name, (int)*all, (int)bb_count);
570 *all = bb_count;
571 if (*count > *all)
572 *count = *all;
573 return false;
574 }
575 else
576 {
577 error_at (locus.get_location_t (), "corrupted value profile: %s "
578 "profile counter (%d out of %d) inconsistent with "
579 "basic-block count (%d)",
580 name,
581 (int) *count,
582 (int) *all,
583 (int) bb_count);
584 return true;
585 }
586 }
587
588 return false;
589 }
590
591 /* GIMPLE based transformations. */
592
593 bool
gimple_value_profile_transformations(void)594 gimple_value_profile_transformations (void)
595 {
596 basic_block bb;
597 gimple_stmt_iterator gsi;
598 bool changed = false;
599
600 FOR_EACH_BB_FN (bb, cfun)
601 {
602 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
603 {
604 gimple *stmt = gsi_stmt (gsi);
605 histogram_value th = gimple_histogram_value (cfun, stmt);
606 if (!th)
607 continue;
608
609 if (dump_file)
610 {
611 fprintf (dump_file, "Trying transformations on stmt ");
612 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
613 dump_histograms_for_stmt (cfun, dump_file, stmt);
614 }
615
616 /* Transformations: */
617 /* The order of things in this conditional controls which
618 transformation is used when more than one is applicable. */
619 /* It is expected that any code added by the transformations
620 will be added before the current statement, and that the
621 current statement remain valid (although possibly
622 modified) upon return. */
623 if (gimple_mod_subtract_transform (&gsi)
624 || gimple_divmod_fixed_value_transform (&gsi)
625 || gimple_mod_pow2_value_transform (&gsi)
626 || gimple_stringops_transform (&gsi))
627 {
628 stmt = gsi_stmt (gsi);
629 changed = true;
630 /* Original statement may no longer be in the same block. */
631 if (bb != gimple_bb (stmt))
632 {
633 bb = gimple_bb (stmt);
634 gsi = gsi_for_stmt (stmt);
635 }
636 }
637
638 /* The function never thansforms a GIMPLE statement. */
639 if (dump_enabled_p ())
640 dump_ic_profile (&gsi);
641 }
642 }
643
644 return changed;
645 }
646
647 /* Generate code for transformation 1 (with parent gimple assignment
648 STMT and probability of taking the optimal path PROB, which is
649 equivalent to COUNT/ALL within roundoff error). This generates the
650 result into a temp and returns the temp; it does not replace or
651 alter the original STMT. */
652
653 static tree
gimple_divmod_fixed_value(gassign * stmt,tree value,profile_probability prob,gcov_type count,gcov_type all)654 gimple_divmod_fixed_value (gassign *stmt, tree value, profile_probability prob,
655 gcov_type count, gcov_type all)
656 {
657 gassign *stmt1, *stmt2;
658 gcond *stmt3;
659 tree tmp0, tmp1, tmp2;
660 gimple *bb1end, *bb2end, *bb3end;
661 basic_block bb, bb2, bb3, bb4;
662 tree optype, op1, op2;
663 edge e12, e13, e23, e24, e34;
664 gimple_stmt_iterator gsi;
665
666 gcc_assert (is_gimple_assign (stmt)
667 && (gimple_assign_rhs_code (stmt) == TRUNC_DIV_EXPR
668 || gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR));
669
670 optype = TREE_TYPE (gimple_assign_lhs (stmt));
671 op1 = gimple_assign_rhs1 (stmt);
672 op2 = gimple_assign_rhs2 (stmt);
673
674 bb = gimple_bb (stmt);
675 gsi = gsi_for_stmt (stmt);
676
677 tmp0 = make_temp_ssa_name (optype, NULL, "PROF");
678 tmp1 = make_temp_ssa_name (optype, NULL, "PROF");
679 stmt1 = gimple_build_assign (tmp0, fold_convert (optype, value));
680 stmt2 = gimple_build_assign (tmp1, op2);
681 stmt3 = gimple_build_cond (NE_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
682 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
683 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
684 gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
685 bb1end = stmt3;
686
687 tmp2 = create_tmp_reg (optype, "PROF");
688 stmt1 = gimple_build_assign (tmp2, gimple_assign_rhs_code (stmt), op1, tmp0);
689 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
690 bb2end = stmt1;
691
692 stmt1 = gimple_build_assign (tmp2, gimple_assign_rhs_code (stmt), op1, op2);
693 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
694 bb3end = stmt1;
695
696 /* Fix CFG. */
697 /* Edge e23 connects bb2 to bb3, etc. */
698 e12 = split_block (bb, bb1end);
699 bb2 = e12->dest;
700 bb2->count = profile_count::from_gcov_type (count);
701 e23 = split_block (bb2, bb2end);
702 bb3 = e23->dest;
703 bb3->count = profile_count::from_gcov_type (all - count);
704 e34 = split_block (bb3, bb3end);
705 bb4 = e34->dest;
706 bb4->count = profile_count::from_gcov_type (all);
707
708 e12->flags &= ~EDGE_FALLTHRU;
709 e12->flags |= EDGE_FALSE_VALUE;
710 e12->probability = prob;
711
712 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
713 e13->probability = prob.invert ();
714
715 remove_edge (e23);
716
717 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
718 e24->probability = profile_probability::always ();
719
720 e34->probability = profile_probability::always ();
721
722 return tmp2;
723 }
724
725 /* Return the n-th value count of TOPN_VALUE histogram. If
726 there's a value, return true and set VALUE and COUNT
727 arguments.
728
729 Counters have the following meaning.
730
731 abs (counters[0]) is the number of executions
732 for i in 0 ... TOPN-1
733 counters[2 * i + 1] is target
734 abs (counters[2 * i + 2]) is corresponding hitrate counter.
735
736 Value of counters[0] negative when counter became
737 full during merging and some values are lost. */
738
739 bool
get_nth_most_common_value(gimple * stmt,const char * counter_type,histogram_value hist,gcov_type * value,gcov_type * count,gcov_type * all,unsigned n)740 get_nth_most_common_value (gimple *stmt, const char *counter_type,
741 histogram_value hist, gcov_type *value,
742 gcov_type *count, gcov_type *all, unsigned n)
743 {
744 gcc_assert (n < GCOV_TOPN_VALUES);
745
746 *count = 0;
747 *value = 0;
748
749 gcov_type read_all = abs_hwi (hist->hvalue.counters[0]);
750
751 gcov_type v = hist->hvalue.counters[2 * n + 1];
752 gcov_type c = hist->hvalue.counters[2 * n + 2];
753
754 if (hist->hvalue.counters[0] < 0
755 && (flag_profile_reproducible == PROFILE_REPRODUCIBILITY_PARALLEL_RUNS
756 || (flag_profile_reproducible
757 == PROFILE_REPRODUCIBILITY_MULTITHREADED)))
758 return false;
759
760 /* Indirect calls can't be verified. */
761 if (stmt
762 && check_counter (stmt, counter_type, &c, &read_all,
763 gimple_bb (stmt)->count))
764 return false;
765
766 *all = read_all;
767
768 *value = v;
769 *count = c;
770 return true;
771 }
772
773 /* Do transform 1) on INSN if applicable. */
774
775 static bool
gimple_divmod_fixed_value_transform(gimple_stmt_iterator * si)776 gimple_divmod_fixed_value_transform (gimple_stmt_iterator *si)
777 {
778 histogram_value histogram;
779 enum tree_code code;
780 gcov_type val, count, all;
781 tree result, value, tree_val;
782 profile_probability prob;
783 gassign *stmt;
784
785 stmt = dyn_cast <gassign *> (gsi_stmt (*si));
786 if (!stmt)
787 return false;
788
789 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt))))
790 return false;
791
792 code = gimple_assign_rhs_code (stmt);
793
794 if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR)
795 return false;
796
797 histogram = gimple_histogram_value_of_type (cfun, stmt,
798 HIST_TYPE_TOPN_VALUES);
799 if (!histogram)
800 return false;
801
802 if (!get_nth_most_common_value (stmt, "divmod", histogram, &val, &count,
803 &all))
804 return false;
805
806 value = histogram->hvalue.value;
807 gimple_remove_histogram_value (cfun, stmt, histogram);
808
809 /* We require that count is at least half of all. */
810 if (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1
811 || 2 * count < all
812 || optimize_bb_for_size_p (gimple_bb (stmt)))
813 return false;
814
815 /* Compute probability of taking the optimal path. */
816 if (all > 0)
817 prob = profile_probability::probability_in_gcov_type (count, all);
818 else
819 prob = profile_probability::never ();
820
821 if (sizeof (gcov_type) == sizeof (HOST_WIDE_INT))
822 tree_val = build_int_cst (get_gcov_type (), val);
823 else
824 {
825 HOST_WIDE_INT a[2];
826 a[0] = (unsigned HOST_WIDE_INT) val;
827 a[1] = val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1;
828
829 tree_val = wide_int_to_tree (get_gcov_type (), wide_int::from_array (a, 2,
830 TYPE_PRECISION (get_gcov_type ()), false));
831 }
832 result = gimple_divmod_fixed_value (stmt, tree_val, prob, count, all);
833
834 if (dump_enabled_p ())
835 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, stmt,
836 "Transformation done: div/mod by constant %T\n", tree_val);
837
838 gimple_assign_set_rhs_from_tree (si, result);
839 update_stmt (gsi_stmt (*si));
840
841 return true;
842 }
843
844 /* Generate code for transformation 2 (with parent gimple assign STMT and
845 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
846 within roundoff error). This generates the result into a temp and returns
847 the temp; it does not replace or alter the original STMT. */
848
849 static tree
gimple_mod_pow2(gassign * stmt,profile_probability prob,gcov_type count,gcov_type all)850 gimple_mod_pow2 (gassign *stmt, profile_probability prob, gcov_type count, gcov_type all)
851 {
852 gassign *stmt1, *stmt2, *stmt3;
853 gcond *stmt4;
854 tree tmp2, tmp3;
855 gimple *bb1end, *bb2end, *bb3end;
856 basic_block bb, bb2, bb3, bb4;
857 tree optype, op1, op2;
858 edge e12, e13, e23, e24, e34;
859 gimple_stmt_iterator gsi;
860 tree result;
861
862 gcc_assert (is_gimple_assign (stmt)
863 && gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR);
864
865 optype = TREE_TYPE (gimple_assign_lhs (stmt));
866 op1 = gimple_assign_rhs1 (stmt);
867 op2 = gimple_assign_rhs2 (stmt);
868
869 bb = gimple_bb (stmt);
870 gsi = gsi_for_stmt (stmt);
871
872 result = create_tmp_reg (optype, "PROF");
873 tmp2 = make_temp_ssa_name (optype, NULL, "PROF");
874 tmp3 = make_temp_ssa_name (optype, NULL, "PROF");
875 stmt2 = gimple_build_assign (tmp2, PLUS_EXPR, op2,
876 build_int_cst (optype, -1));
877 stmt3 = gimple_build_assign (tmp3, BIT_AND_EXPR, tmp2, op2);
878 stmt4 = gimple_build_cond (NE_EXPR, tmp3, build_int_cst (optype, 0),
879 NULL_TREE, NULL_TREE);
880 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
881 gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
882 gsi_insert_before (&gsi, stmt4, GSI_SAME_STMT);
883 bb1end = stmt4;
884
885 /* tmp2 == op2-1 inherited from previous block. */
886 stmt1 = gimple_build_assign (result, BIT_AND_EXPR, op1, tmp2);
887 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
888 bb2end = stmt1;
889
890 stmt1 = gimple_build_assign (result, gimple_assign_rhs_code (stmt),
891 op1, op2);
892 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
893 bb3end = stmt1;
894
895 /* Fix CFG. */
896 /* Edge e23 connects bb2 to bb3, etc. */
897 e12 = split_block (bb, bb1end);
898 bb2 = e12->dest;
899 bb2->count = profile_count::from_gcov_type (count);
900 e23 = split_block (bb2, bb2end);
901 bb3 = e23->dest;
902 bb3->count = profile_count::from_gcov_type (all - count);
903 e34 = split_block (bb3, bb3end);
904 bb4 = e34->dest;
905 bb4->count = profile_count::from_gcov_type (all);
906
907 e12->flags &= ~EDGE_FALLTHRU;
908 e12->flags |= EDGE_FALSE_VALUE;
909 e12->probability = prob;
910
911 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
912 e13->probability = prob.invert ();
913
914 remove_edge (e23);
915
916 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
917 e24->probability = profile_probability::always ();
918
919 e34->probability = profile_probability::always ();
920
921 return result;
922 }
923
924 /* Do transform 2) on INSN if applicable. */
925
926 static bool
gimple_mod_pow2_value_transform(gimple_stmt_iterator * si)927 gimple_mod_pow2_value_transform (gimple_stmt_iterator *si)
928 {
929 histogram_value histogram;
930 enum tree_code code;
931 gcov_type count, wrong_values, all;
932 tree lhs_type, result, value;
933 profile_probability prob;
934 gassign *stmt;
935
936 stmt = dyn_cast <gassign *> (gsi_stmt (*si));
937 if (!stmt)
938 return false;
939
940 lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
941 if (!INTEGRAL_TYPE_P (lhs_type))
942 return false;
943
944 code = gimple_assign_rhs_code (stmt);
945
946 if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type))
947 return false;
948
949 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_POW2);
950 if (!histogram)
951 return false;
952
953 value = histogram->hvalue.value;
954 wrong_values = histogram->hvalue.counters[0];
955 count = histogram->hvalue.counters[1];
956
957 gimple_remove_histogram_value (cfun, stmt, histogram);
958
959 /* We require that we hit a power of 2 at least half of all evaluations. */
960 if (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1
961 || count < wrong_values
962 || optimize_bb_for_size_p (gimple_bb (stmt)))
963 return false;
964
965 /* Compute probability of taking the optimal path. */
966 all = count + wrong_values;
967
968 if (check_counter (stmt, "pow2", &count, &all, gimple_bb (stmt)->count))
969 return false;
970
971 if (dump_enabled_p ())
972 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, stmt,
973 "Transformation done: mod power of 2\n");
974
975 if (all > 0)
976 prob = profile_probability::probability_in_gcov_type (count, all);
977 else
978 prob = profile_probability::never ();
979
980 result = gimple_mod_pow2 (stmt, prob, count, all);
981
982 gimple_assign_set_rhs_from_tree (si, result);
983 update_stmt (gsi_stmt (*si));
984
985 return true;
986 }
987
988 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
989 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
990 supported and this is built into this interface. The probabilities of taking
991 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
992 COUNT2/ALL respectively within roundoff error). This generates the
993 result into a temp and returns the temp; it does not replace or alter
994 the original STMT. */
995 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
996
997 static tree
gimple_mod_subtract(gassign * stmt,profile_probability prob1,profile_probability prob2,int ncounts,gcov_type count1,gcov_type count2,gcov_type all)998 gimple_mod_subtract (gassign *stmt, profile_probability prob1,
999 profile_probability prob2, int ncounts,
1000 gcov_type count1, gcov_type count2, gcov_type all)
1001 {
1002 gassign *stmt1;
1003 gimple *stmt2;
1004 gcond *stmt3;
1005 tree tmp1;
1006 gimple *bb1end, *bb2end = NULL, *bb3end;
1007 basic_block bb, bb2, bb3, bb4;
1008 tree optype, op1, op2;
1009 edge e12, e23 = 0, e24, e34, e14;
1010 gimple_stmt_iterator gsi;
1011 tree result;
1012
1013 gcc_assert (is_gimple_assign (stmt)
1014 && gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR);
1015
1016 optype = TREE_TYPE (gimple_assign_lhs (stmt));
1017 op1 = gimple_assign_rhs1 (stmt);
1018 op2 = gimple_assign_rhs2 (stmt);
1019
1020 bb = gimple_bb (stmt);
1021 gsi = gsi_for_stmt (stmt);
1022
1023 result = create_tmp_reg (optype, "PROF");
1024 tmp1 = make_temp_ssa_name (optype, NULL, "PROF");
1025 stmt1 = gimple_build_assign (result, op1);
1026 stmt2 = gimple_build_assign (tmp1, op2);
1027 stmt3 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE);
1028 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
1029 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
1030 gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
1031 bb1end = stmt3;
1032
1033 if (ncounts) /* Assumed to be 0 or 1 */
1034 {
1035 stmt1 = gimple_build_assign (result, MINUS_EXPR, result, tmp1);
1036 stmt2 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE);
1037 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
1038 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
1039 bb2end = stmt2;
1040 }
1041
1042 /* Fallback case. */
1043 stmt1 = gimple_build_assign (result, gimple_assign_rhs_code (stmt),
1044 result, tmp1);
1045 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
1046 bb3end = stmt1;
1047
1048 /* Fix CFG. */
1049 /* Edge e23 connects bb2 to bb3, etc. */
1050 /* However block 3 is optional; if it is not there, references
1051 to 3 really refer to block 2. */
1052 e12 = split_block (bb, bb1end);
1053 bb2 = e12->dest;
1054 bb2->count = profile_count::from_gcov_type (all - count1);
1055
1056 if (ncounts) /* Assumed to be 0 or 1. */
1057 {
1058 e23 = split_block (bb2, bb2end);
1059 bb3 = e23->dest;
1060 bb3->count = profile_count::from_gcov_type (all - count1 - count2);
1061 }
1062
1063 e34 = split_block (ncounts ? bb3 : bb2, bb3end);
1064 bb4 = e34->dest;
1065 bb4->count = profile_count::from_gcov_type (all);
1066
1067 e12->flags &= ~EDGE_FALLTHRU;
1068 e12->flags |= EDGE_FALSE_VALUE;
1069 e12->probability = prob1.invert ();
1070
1071 e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE);
1072 e14->probability = prob1;
1073
1074 if (ncounts) /* Assumed to be 0 or 1. */
1075 {
1076 e23->flags &= ~EDGE_FALLTHRU;
1077 e23->flags |= EDGE_FALSE_VALUE;
1078 e23->probability = prob2.invert ();
1079
1080 e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE);
1081 e24->probability = prob2;
1082 }
1083
1084 e34->probability = profile_probability::always ();
1085
1086 return result;
1087 }
1088
1089 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1090
1091 static bool
gimple_mod_subtract_transform(gimple_stmt_iterator * si)1092 gimple_mod_subtract_transform (gimple_stmt_iterator *si)
1093 {
1094 histogram_value histogram;
1095 enum tree_code code;
1096 gcov_type count, wrong_values, all;
1097 tree lhs_type, result;
1098 profile_probability prob1, prob2;
1099 unsigned int i, steps;
1100 gcov_type count1, count2;
1101 gassign *stmt;
1102 stmt = dyn_cast <gassign *> (gsi_stmt (*si));
1103 if (!stmt)
1104 return false;
1105
1106 lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
1107 if (!INTEGRAL_TYPE_P (lhs_type))
1108 return false;
1109
1110 code = gimple_assign_rhs_code (stmt);
1111
1112 if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type))
1113 return false;
1114
1115 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INTERVAL);
1116 if (!histogram)
1117 return false;
1118
1119 all = 0;
1120 wrong_values = 0;
1121 for (i = 0; i < histogram->hdata.intvl.steps; i++)
1122 all += histogram->hvalue.counters[i];
1123
1124 wrong_values += histogram->hvalue.counters[i];
1125 wrong_values += histogram->hvalue.counters[i+1];
1126 steps = histogram->hdata.intvl.steps;
1127 all += wrong_values;
1128 count1 = histogram->hvalue.counters[0];
1129 count2 = histogram->hvalue.counters[1];
1130
1131 if (check_counter (stmt, "interval", &count1, &all, gimple_bb (stmt)->count))
1132 {
1133 gimple_remove_histogram_value (cfun, stmt, histogram);
1134 return false;
1135 }
1136
1137 if (flag_profile_correction && count1 + count2 > all)
1138 all = count1 + count2;
1139
1140 gcc_assert (count1 + count2 <= all);
1141
1142 /* We require that we use just subtractions in at least 50% of all
1143 evaluations. */
1144 count = 0;
1145 for (i = 0; i < histogram->hdata.intvl.steps; i++)
1146 {
1147 count += histogram->hvalue.counters[i];
1148 if (count * 2 >= all)
1149 break;
1150 }
1151 if (i == steps
1152 || optimize_bb_for_size_p (gimple_bb (stmt)))
1153 return false;
1154
1155 gimple_remove_histogram_value (cfun, stmt, histogram);
1156 if (dump_enabled_p ())
1157 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, stmt,
1158 "Transformation done: mod subtract\n");
1159
1160 /* Compute probability of taking the optimal path(s). */
1161 if (all > 0)
1162 {
1163 prob1 = profile_probability::probability_in_gcov_type (count1, all);
1164 prob2 = profile_probability::probability_in_gcov_type (count2, all);
1165 }
1166 else
1167 {
1168 prob1 = prob2 = profile_probability::never ();
1169 }
1170
1171 /* In practice, "steps" is always 2. This interface reflects this,
1172 and will need to be changed if "steps" can change. */
1173 result = gimple_mod_subtract (stmt, prob1, prob2, i, count1, count2, all);
1174
1175 gimple_assign_set_rhs_from_tree (si, result);
1176 update_stmt (gsi_stmt (*si));
1177
1178 return true;
1179 }
1180
1181 typedef int_hash <unsigned int, 0, UINT_MAX> profile_id_hash;
1182
1183 static hash_map<profile_id_hash, cgraph_node *> *cgraph_node_map = 0;
1184
1185 /* Returns true if node graph is initialized. This
1186 is used to test if profile_id has been created
1187 for cgraph_nodes. */
1188
1189 bool
coverage_node_map_initialized_p(void)1190 coverage_node_map_initialized_p (void)
1191 {
1192 return cgraph_node_map != 0;
1193 }
1194
1195 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1196 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1197 that the PROFILE_IDs was already assigned. */
1198
1199 void
init_node_map(bool local)1200 init_node_map (bool local)
1201 {
1202 struct cgraph_node *n;
1203 cgraph_node_map = new hash_map<profile_id_hash, cgraph_node *>;
1204
1205 FOR_EACH_DEFINED_FUNCTION (n)
1206 if (n->has_gimple_body_p () || n->thunk.thunk_p)
1207 {
1208 cgraph_node **val;
1209 dump_user_location_t loc
1210 = dump_user_location_t::from_function_decl (n->decl);
1211 if (local)
1212 {
1213 n->profile_id = coverage_compute_profile_id (n);
1214 while ((val = cgraph_node_map->get (n->profile_id))
1215 || !n->profile_id)
1216 {
1217 if (dump_enabled_p ())
1218 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
1219 "Local profile-id %i conflict"
1220 " with nodes %s %s\n",
1221 n->profile_id,
1222 n->dump_name (),
1223 (*val)->dump_name ());
1224 n->profile_id = (n->profile_id + 1) & 0x7fffffff;
1225 }
1226 }
1227 else if (!n->profile_id)
1228 {
1229 if (dump_enabled_p ())
1230 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
1231 "Node %s has no profile-id"
1232 " (profile feedback missing?)\n",
1233 n->dump_name ());
1234 continue;
1235 }
1236 else if ((val = cgraph_node_map->get (n->profile_id)))
1237 {
1238 if (dump_enabled_p ())
1239 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
1240 "Node %s has IP profile-id %i conflict. "
1241 "Giving up.\n",
1242 n->dump_name (), n->profile_id);
1243 *val = NULL;
1244 continue;
1245 }
1246 cgraph_node_map->put (n->profile_id, n);
1247 }
1248 }
1249
1250 /* Delete the CGRAPH_NODE_MAP. */
1251
1252 void
del_node_map(void)1253 del_node_map (void)
1254 {
1255 delete cgraph_node_map;
1256 }
1257
1258 /* Return cgraph node for function with pid */
1259
1260 struct cgraph_node*
find_func_by_profile_id(int profile_id)1261 find_func_by_profile_id (int profile_id)
1262 {
1263 cgraph_node **val = cgraph_node_map->get (profile_id);
1264 if (val)
1265 return *val;
1266 else
1267 return NULL;
1268 }
1269
1270 /* Do transformation
1271
1272 if (actual_callee_address == address_of_most_common_function/method)
1273 do direct call
1274 else
1275 old call
1276 */
1277
1278 gcall *
gimple_ic(gcall * icall_stmt,struct cgraph_node * direct_call,profile_probability prob)1279 gimple_ic (gcall *icall_stmt, struct cgraph_node *direct_call,
1280 profile_probability prob)
1281 {
1282 gcall *dcall_stmt;
1283 gassign *load_stmt;
1284 gcond *cond_stmt;
1285 tree tmp0, tmp1, tmp;
1286 basic_block cond_bb, dcall_bb, icall_bb, join_bb = NULL;
1287 edge e_cd, e_ci, e_di, e_dj = NULL, e_ij;
1288 gimple_stmt_iterator gsi;
1289 int lp_nr, dflags;
1290 edge e_eh, e;
1291 edge_iterator ei;
1292
1293 cond_bb = gimple_bb (icall_stmt);
1294 gsi = gsi_for_stmt (icall_stmt);
1295
1296 tmp0 = make_temp_ssa_name (ptr_type_node, NULL, "PROF");
1297 tmp1 = make_temp_ssa_name (ptr_type_node, NULL, "PROF");
1298 tmp = unshare_expr (gimple_call_fn (icall_stmt));
1299 load_stmt = gimple_build_assign (tmp0, tmp);
1300 gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
1301
1302 tmp = fold_convert (ptr_type_node, build_addr (direct_call->decl));
1303 load_stmt = gimple_build_assign (tmp1, tmp);
1304 gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
1305
1306 cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
1307 gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1308
1309 if (TREE_CODE (gimple_vdef (icall_stmt)) == SSA_NAME)
1310 {
1311 unlink_stmt_vdef (icall_stmt);
1312 release_ssa_name (gimple_vdef (icall_stmt));
1313 }
1314 gimple_set_vdef (icall_stmt, NULL_TREE);
1315 gimple_set_vuse (icall_stmt, NULL_TREE);
1316 update_stmt (icall_stmt);
1317 dcall_stmt = as_a <gcall *> (gimple_copy (icall_stmt));
1318 gimple_call_set_fndecl (dcall_stmt, direct_call->decl);
1319 dflags = flags_from_decl_or_type (direct_call->decl);
1320 if ((dflags & ECF_NORETURN) != 0
1321 && should_remove_lhs_p (gimple_call_lhs (dcall_stmt)))
1322 gimple_call_set_lhs (dcall_stmt, NULL_TREE);
1323 gsi_insert_before (&gsi, dcall_stmt, GSI_SAME_STMT);
1324
1325 /* Fix CFG. */
1326 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1327 e_cd = split_block (cond_bb, cond_stmt);
1328 dcall_bb = e_cd->dest;
1329 dcall_bb->count = cond_bb->count.apply_probability (prob);
1330
1331 e_di = split_block (dcall_bb, dcall_stmt);
1332 icall_bb = e_di->dest;
1333 icall_bb->count = cond_bb->count - dcall_bb->count;
1334
1335 /* Do not disturb existing EH edges from the indirect call. */
1336 if (!stmt_ends_bb_p (icall_stmt))
1337 e_ij = split_block (icall_bb, icall_stmt);
1338 else
1339 {
1340 e_ij = find_fallthru_edge (icall_bb->succs);
1341 /* The indirect call might be noreturn. */
1342 if (e_ij != NULL)
1343 {
1344 e_ij->probability = profile_probability::always ();
1345 e_ij = single_pred_edge (split_edge (e_ij));
1346 }
1347 }
1348 if (e_ij != NULL)
1349 {
1350 join_bb = e_ij->dest;
1351 join_bb->count = cond_bb->count;
1352 }
1353
1354 e_cd->flags = (e_cd->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE;
1355 e_cd->probability = prob;
1356
1357 e_ci = make_edge (cond_bb, icall_bb, EDGE_FALSE_VALUE);
1358 e_ci->probability = prob.invert ();
1359
1360 remove_edge (e_di);
1361
1362 if (e_ij != NULL)
1363 {
1364 if ((dflags & ECF_NORETURN) == 0)
1365 {
1366 e_dj = make_edge (dcall_bb, join_bb, EDGE_FALLTHRU);
1367 e_dj->probability = profile_probability::always ();
1368 }
1369 e_ij->probability = profile_probability::always ();
1370 }
1371
1372 /* Insert PHI node for the call result if necessary. */
1373 if (gimple_call_lhs (icall_stmt)
1374 && TREE_CODE (gimple_call_lhs (icall_stmt)) == SSA_NAME
1375 && (dflags & ECF_NORETURN) == 0)
1376 {
1377 tree result = gimple_call_lhs (icall_stmt);
1378 gphi *phi = create_phi_node (result, join_bb);
1379 gimple_call_set_lhs (icall_stmt,
1380 duplicate_ssa_name (result, icall_stmt));
1381 add_phi_arg (phi, gimple_call_lhs (icall_stmt), e_ij, UNKNOWN_LOCATION);
1382 gimple_call_set_lhs (dcall_stmt,
1383 duplicate_ssa_name (result, dcall_stmt));
1384 add_phi_arg (phi, gimple_call_lhs (dcall_stmt), e_dj, UNKNOWN_LOCATION);
1385 }
1386
1387 /* Build an EH edge for the direct call if necessary. */
1388 lp_nr = lookup_stmt_eh_lp (icall_stmt);
1389 if (lp_nr > 0 && stmt_could_throw_p (cfun, dcall_stmt))
1390 {
1391 add_stmt_to_eh_lp (dcall_stmt, lp_nr);
1392 }
1393
1394 FOR_EACH_EDGE (e_eh, ei, icall_bb->succs)
1395 if (e_eh->flags & (EDGE_EH | EDGE_ABNORMAL))
1396 {
1397 e = make_edge (dcall_bb, e_eh->dest, e_eh->flags);
1398 e->probability = e_eh->probability;
1399 for (gphi_iterator psi = gsi_start_phis (e_eh->dest);
1400 !gsi_end_p (psi); gsi_next (&psi))
1401 {
1402 gphi *phi = psi.phi ();
1403 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, e),
1404 PHI_ARG_DEF_FROM_EDGE (phi, e_eh));
1405 }
1406 }
1407 if (!stmt_could_throw_p (cfun, dcall_stmt))
1408 gimple_purge_dead_eh_edges (dcall_bb);
1409 return dcall_stmt;
1410 }
1411
1412 /* Dump info about indirect call profile. */
1413
1414 static void
dump_ic_profile(gimple_stmt_iterator * gsi)1415 dump_ic_profile (gimple_stmt_iterator *gsi)
1416 {
1417 gcall *stmt;
1418 histogram_value histogram;
1419 gcov_type val, count, all;
1420 struct cgraph_node *direct_call;
1421
1422 stmt = dyn_cast <gcall *> (gsi_stmt (*gsi));
1423 if (!stmt)
1424 return;
1425
1426 if (gimple_call_fndecl (stmt) != NULL_TREE)
1427 return;
1428
1429 if (gimple_call_internal_p (stmt))
1430 return;
1431
1432 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INDIR_CALL);
1433 if (!histogram)
1434 return;
1435
1436 count = 0;
1437 all = histogram->hvalue.counters[0];
1438
1439 for (unsigned j = 0; j < GCOV_TOPN_VALUES; j++)
1440 {
1441 if (!get_nth_most_common_value (NULL, "indirect call", histogram, &val,
1442 &count, &all, j))
1443 return;
1444 if (!count)
1445 continue;
1446
1447 direct_call = find_func_by_profile_id ((int) val);
1448
1449 if (direct_call == NULL)
1450 dump_printf_loc (
1451 MSG_MISSED_OPTIMIZATION, stmt,
1452 "Indirect call -> direct call from other "
1453 "module %T=> %i (will resolve by ipa-profile only with LTO)\n",
1454 gimple_call_fn (stmt), (int) val);
1455 else
1456 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, stmt,
1457 "Indirect call -> direct call "
1458 "%T => %T (will resolve by ipa-profile)\n",
1459 gimple_call_fn (stmt), direct_call->decl);
1460 dump_printf_loc (MSG_NOTE, stmt,
1461 "hist->count %" PRId64 " hist->all %" PRId64 "\n",
1462 count, all);
1463 }
1464 }
1465
1466 /* Return true if the stringop CALL shall be profiled. SIZE_ARG be
1467 set to the argument index for the size of the string operation. */
1468
1469 static bool
interesting_stringop_to_profile_p(gcall * call,int * size_arg)1470 interesting_stringop_to_profile_p (gcall *call, int *size_arg)
1471 {
1472 enum built_in_function fcode;
1473
1474 fcode = DECL_FUNCTION_CODE (gimple_call_fndecl (call));
1475 switch (fcode)
1476 {
1477 case BUILT_IN_MEMCPY:
1478 case BUILT_IN_MEMPCPY:
1479 case BUILT_IN_MEMMOVE:
1480 *size_arg = 2;
1481 return validate_gimple_arglist (call, POINTER_TYPE, POINTER_TYPE,
1482 INTEGER_TYPE, VOID_TYPE);
1483 case BUILT_IN_MEMSET:
1484 *size_arg = 2;
1485 return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE,
1486 INTEGER_TYPE, VOID_TYPE);
1487 case BUILT_IN_BZERO:
1488 *size_arg = 1;
1489 return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE,
1490 VOID_TYPE);
1491 default:
1492 return false;
1493 }
1494 }
1495
1496 /* Convert stringop (..., vcall_size)
1497 into
1498 if (vcall_size == icall_size)
1499 stringop (..., icall_size);
1500 else
1501 stringop (..., vcall_size);
1502 assuming we'll propagate a true constant into ICALL_SIZE later. */
1503
1504 static void
gimple_stringop_fixed_value(gcall * vcall_stmt,tree icall_size,profile_probability prob,gcov_type count,gcov_type all)1505 gimple_stringop_fixed_value (gcall *vcall_stmt, tree icall_size, profile_probability prob,
1506 gcov_type count, gcov_type all)
1507 {
1508 gassign *tmp_stmt;
1509 gcond *cond_stmt;
1510 gcall *icall_stmt;
1511 tree tmp0, tmp1, vcall_size, optype;
1512 basic_block cond_bb, icall_bb, vcall_bb, join_bb;
1513 edge e_ci, e_cv, e_iv, e_ij, e_vj;
1514 gimple_stmt_iterator gsi;
1515 int size_arg;
1516
1517 if (!interesting_stringop_to_profile_p (vcall_stmt, &size_arg))
1518 gcc_unreachable ();
1519
1520 cond_bb = gimple_bb (vcall_stmt);
1521 gsi = gsi_for_stmt (vcall_stmt);
1522
1523 vcall_size = gimple_call_arg (vcall_stmt, size_arg);
1524 optype = TREE_TYPE (vcall_size);
1525
1526 tmp0 = make_temp_ssa_name (optype, NULL, "PROF");
1527 tmp1 = make_temp_ssa_name (optype, NULL, "PROF");
1528 tmp_stmt = gimple_build_assign (tmp0, fold_convert (optype, icall_size));
1529 gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT);
1530
1531 tmp_stmt = gimple_build_assign (tmp1, vcall_size);
1532 gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT);
1533
1534 cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
1535 gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1536
1537 if (TREE_CODE (gimple_vdef (vcall_stmt)) == SSA_NAME)
1538 {
1539 unlink_stmt_vdef (vcall_stmt);
1540 release_ssa_name (gimple_vdef (vcall_stmt));
1541 }
1542 gimple_set_vdef (vcall_stmt, NULL);
1543 gimple_set_vuse (vcall_stmt, NULL);
1544 update_stmt (vcall_stmt);
1545 icall_stmt = as_a <gcall *> (gimple_copy (vcall_stmt));
1546 gimple_call_set_arg (icall_stmt, size_arg,
1547 fold_convert (optype, icall_size));
1548 gsi_insert_before (&gsi, icall_stmt, GSI_SAME_STMT);
1549
1550 /* Fix CFG. */
1551 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1552 e_ci = split_block (cond_bb, cond_stmt);
1553 icall_bb = e_ci->dest;
1554 icall_bb->count = profile_count::from_gcov_type (count);
1555
1556 e_iv = split_block (icall_bb, icall_stmt);
1557 vcall_bb = e_iv->dest;
1558 vcall_bb->count = profile_count::from_gcov_type (all - count);
1559
1560 e_vj = split_block (vcall_bb, vcall_stmt);
1561 join_bb = e_vj->dest;
1562 join_bb->count = profile_count::from_gcov_type (all);
1563
1564 e_ci->flags = (e_ci->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE;
1565 e_ci->probability = prob;
1566
1567 e_cv = make_edge (cond_bb, vcall_bb, EDGE_FALSE_VALUE);
1568 e_cv->probability = prob.invert ();
1569
1570 remove_edge (e_iv);
1571
1572 e_ij = make_edge (icall_bb, join_bb, EDGE_FALLTHRU);
1573 e_ij->probability = profile_probability::always ();
1574
1575 e_vj->probability = profile_probability::always ();
1576
1577 /* Insert PHI node for the call result if necessary. */
1578 if (gimple_call_lhs (vcall_stmt)
1579 && TREE_CODE (gimple_call_lhs (vcall_stmt)) == SSA_NAME)
1580 {
1581 tree result = gimple_call_lhs (vcall_stmt);
1582 gphi *phi = create_phi_node (result, join_bb);
1583 gimple_call_set_lhs (vcall_stmt,
1584 duplicate_ssa_name (result, vcall_stmt));
1585 add_phi_arg (phi, gimple_call_lhs (vcall_stmt), e_vj, UNKNOWN_LOCATION);
1586 gimple_call_set_lhs (icall_stmt,
1587 duplicate_ssa_name (result, icall_stmt));
1588 add_phi_arg (phi, gimple_call_lhs (icall_stmt), e_ij, UNKNOWN_LOCATION);
1589 }
1590
1591 /* Because these are all string op builtins, they're all nothrow. */
1592 gcc_assert (!stmt_could_throw_p (cfun, vcall_stmt));
1593 gcc_assert (!stmt_could_throw_p (cfun, icall_stmt));
1594 }
1595
1596 /* Find values inside STMT for that we want to measure histograms for
1597 division/modulo optimization. */
1598
1599 static bool
gimple_stringops_transform(gimple_stmt_iterator * gsi)1600 gimple_stringops_transform (gimple_stmt_iterator *gsi)
1601 {
1602 gcall *stmt;
1603 tree blck_size;
1604 enum built_in_function fcode;
1605 histogram_value histogram;
1606 gcov_type count, all, val;
1607 tree dest, src;
1608 unsigned int dest_align, src_align;
1609 profile_probability prob;
1610 tree tree_val;
1611 int size_arg;
1612
1613 stmt = dyn_cast <gcall *> (gsi_stmt (*gsi));
1614 if (!stmt)
1615 return false;
1616
1617 if (!gimple_call_builtin_p (gsi_stmt (*gsi), BUILT_IN_NORMAL))
1618 return false;
1619
1620 if (!interesting_stringop_to_profile_p (stmt, &size_arg))
1621 return false;
1622
1623 blck_size = gimple_call_arg (stmt, size_arg);
1624 if (TREE_CODE (blck_size) == INTEGER_CST)
1625 return false;
1626
1627 histogram = gimple_histogram_value_of_type (cfun, stmt,
1628 HIST_TYPE_TOPN_VALUES);
1629 if (!histogram)
1630 return false;
1631
1632 if (!get_nth_most_common_value (stmt, "stringops", histogram, &val, &count,
1633 &all))
1634 return false;
1635
1636 gimple_remove_histogram_value (cfun, stmt, histogram);
1637
1638 /* We require that count is at least half of all. */
1639 if (2 * count < all || optimize_bb_for_size_p (gimple_bb (stmt)))
1640 return false;
1641 if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count))
1642 return false;
1643 if (all > 0)
1644 prob = profile_probability::probability_in_gcov_type (count, all);
1645 else
1646 prob = profile_probability::never ();
1647
1648 dest = gimple_call_arg (stmt, 0);
1649 dest_align = get_pointer_alignment (dest);
1650 fcode = DECL_FUNCTION_CODE (gimple_call_fndecl (stmt));
1651 switch (fcode)
1652 {
1653 case BUILT_IN_MEMCPY:
1654 case BUILT_IN_MEMPCPY:
1655 case BUILT_IN_MEMMOVE:
1656 src = gimple_call_arg (stmt, 1);
1657 src_align = get_pointer_alignment (src);
1658 if (!can_move_by_pieces (val, MIN (dest_align, src_align)))
1659 return false;
1660 break;
1661 case BUILT_IN_MEMSET:
1662 if (!can_store_by_pieces (val, builtin_memset_read_str,
1663 gimple_call_arg (stmt, 1),
1664 dest_align, true))
1665 return false;
1666 break;
1667 case BUILT_IN_BZERO:
1668 if (!can_store_by_pieces (val, builtin_memset_read_str,
1669 integer_zero_node,
1670 dest_align, true))
1671 return false;
1672 break;
1673 default:
1674 gcc_unreachable ();
1675 }
1676
1677 if (sizeof (gcov_type) == sizeof (HOST_WIDE_INT))
1678 tree_val = build_int_cst (get_gcov_type (), val);
1679 else
1680 {
1681 HOST_WIDE_INT a[2];
1682 a[0] = (unsigned HOST_WIDE_INT) val;
1683 a[1] = val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1;
1684
1685 tree_val = wide_int_to_tree (get_gcov_type (), wide_int::from_array (a, 2,
1686 TYPE_PRECISION (get_gcov_type ()), false));
1687 }
1688
1689 if (dump_enabled_p ())
1690 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, stmt,
1691 "Transformation done: single value %i stringop for %s\n",
1692 (int)val, built_in_names[(int)fcode]);
1693
1694 gimple_stringop_fixed_value (stmt, tree_val, prob, count, all);
1695
1696 return true;
1697 }
1698
1699 void
stringop_block_profile(gimple * stmt,unsigned int * expected_align,HOST_WIDE_INT * expected_size)1700 stringop_block_profile (gimple *stmt, unsigned int *expected_align,
1701 HOST_WIDE_INT *expected_size)
1702 {
1703 histogram_value histogram;
1704 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_AVERAGE);
1705
1706 if (!histogram)
1707 *expected_size = -1;
1708 else if (!histogram->hvalue.counters[1])
1709 {
1710 *expected_size = -1;
1711 gimple_remove_histogram_value (cfun, stmt, histogram);
1712 }
1713 else
1714 {
1715 gcov_type size;
1716 size = ((histogram->hvalue.counters[0]
1717 + histogram->hvalue.counters[1] / 2)
1718 / histogram->hvalue.counters[1]);
1719 /* Even if we can hold bigger value in SIZE, INT_MAX
1720 is safe "infinity" for code generation strategies. */
1721 if (size > INT_MAX)
1722 size = INT_MAX;
1723 *expected_size = size;
1724 gimple_remove_histogram_value (cfun, stmt, histogram);
1725 }
1726
1727 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_IOR);
1728
1729 if (!histogram)
1730 *expected_align = 0;
1731 else if (!histogram->hvalue.counters[0])
1732 {
1733 gimple_remove_histogram_value (cfun, stmt, histogram);
1734 *expected_align = 0;
1735 }
1736 else
1737 {
1738 gcov_type count;
1739 unsigned int alignment;
1740
1741 count = histogram->hvalue.counters[0];
1742 alignment = 1;
1743 while (!(count & alignment)
1744 && (alignment <= UINT_MAX / 2 / BITS_PER_UNIT))
1745 alignment <<= 1;
1746 *expected_align = alignment * BITS_PER_UNIT;
1747 gimple_remove_histogram_value (cfun, stmt, histogram);
1748 }
1749 }
1750
1751
1752 /* Find values inside STMT for that we want to measure histograms for
1753 division/modulo optimization. */
1754
1755 static void
gimple_divmod_values_to_profile(gimple * stmt,histogram_values * values)1756 gimple_divmod_values_to_profile (gimple *stmt, histogram_values *values)
1757 {
1758 tree lhs, divisor, op0, type;
1759 histogram_value hist;
1760
1761 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1762 return;
1763
1764 lhs = gimple_assign_lhs (stmt);
1765 type = TREE_TYPE (lhs);
1766 if (!INTEGRAL_TYPE_P (type))
1767 return;
1768
1769 switch (gimple_assign_rhs_code (stmt))
1770 {
1771 case TRUNC_DIV_EXPR:
1772 case TRUNC_MOD_EXPR:
1773 divisor = gimple_assign_rhs2 (stmt);
1774 op0 = gimple_assign_rhs1 (stmt);
1775
1776 if (TREE_CODE (divisor) == SSA_NAME)
1777 /* Check for the case where the divisor is the same value most
1778 of the time. */
1779 values->safe_push (gimple_alloc_histogram_value (cfun,
1780 HIST_TYPE_TOPN_VALUES,
1781 stmt, divisor));
1782
1783 /* For mod, check whether it is not often a noop (or replaceable by
1784 a few subtractions). */
1785 if (gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR
1786 && TYPE_UNSIGNED (type)
1787 && TREE_CODE (divisor) == SSA_NAME)
1788 {
1789 tree val;
1790 /* Check for a special case where the divisor is power of 2. */
1791 values->safe_push (gimple_alloc_histogram_value (cfun,
1792 HIST_TYPE_POW2,
1793 stmt, divisor));
1794 val = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
1795 hist = gimple_alloc_histogram_value (cfun, HIST_TYPE_INTERVAL,
1796 stmt, val);
1797 hist->hdata.intvl.int_start = 0;
1798 hist->hdata.intvl.steps = 2;
1799 values->safe_push (hist);
1800 }
1801 return;
1802
1803 default:
1804 return;
1805 }
1806 }
1807
1808 /* Find calls inside STMT for that we want to measure histograms for
1809 indirect/virtual call optimization. */
1810
1811 static void
gimple_indirect_call_to_profile(gimple * stmt,histogram_values * values)1812 gimple_indirect_call_to_profile (gimple *stmt, histogram_values *values)
1813 {
1814 tree callee;
1815
1816 if (gimple_code (stmt) != GIMPLE_CALL
1817 || gimple_call_internal_p (stmt)
1818 || gimple_call_fndecl (stmt) != NULL_TREE)
1819 return;
1820
1821 callee = gimple_call_fn (stmt);
1822 histogram_value v = gimple_alloc_histogram_value (cfun, HIST_TYPE_INDIR_CALL,
1823 stmt, callee);
1824 values->safe_push (v);
1825
1826 return;
1827 }
1828
1829 /* Find values inside STMT for that we want to measure histograms for
1830 string operations. */
1831
1832 static void
gimple_stringops_values_to_profile(gimple * gs,histogram_values * values)1833 gimple_stringops_values_to_profile (gimple *gs, histogram_values *values)
1834 {
1835 gcall *stmt;
1836 tree blck_size;
1837 tree dest;
1838 int size_arg;
1839
1840 stmt = dyn_cast <gcall *> (gs);
1841 if (!stmt)
1842 return;
1843
1844 if (!gimple_call_builtin_p (gs, BUILT_IN_NORMAL))
1845 return;
1846
1847 if (!interesting_stringop_to_profile_p (stmt, &size_arg))
1848 return;
1849
1850 dest = gimple_call_arg (stmt, 0);
1851 blck_size = gimple_call_arg (stmt, size_arg);
1852
1853 if (TREE_CODE (blck_size) != INTEGER_CST)
1854 {
1855 values->safe_push (gimple_alloc_histogram_value (cfun,
1856 HIST_TYPE_TOPN_VALUES,
1857 stmt, blck_size));
1858 values->safe_push (gimple_alloc_histogram_value (cfun, HIST_TYPE_AVERAGE,
1859 stmt, blck_size));
1860 }
1861
1862 if (TREE_CODE (blck_size) != INTEGER_CST)
1863 values->safe_push (gimple_alloc_histogram_value (cfun, HIST_TYPE_IOR,
1864 stmt, dest));
1865 }
1866
1867 /* Find values inside STMT for that we want to measure histograms and adds
1868 them to list VALUES. */
1869
1870 static void
gimple_values_to_profile(gimple * stmt,histogram_values * values)1871 gimple_values_to_profile (gimple *stmt, histogram_values *values)
1872 {
1873 gimple_divmod_values_to_profile (stmt, values);
1874 gimple_stringops_values_to_profile (stmt, values);
1875 gimple_indirect_call_to_profile (stmt, values);
1876 }
1877
1878 void
gimple_find_values_to_profile(histogram_values * values)1879 gimple_find_values_to_profile (histogram_values *values)
1880 {
1881 basic_block bb;
1882 gimple_stmt_iterator gsi;
1883 unsigned i;
1884 histogram_value hist = NULL;
1885 values->create (0);
1886
1887 FOR_EACH_BB_FN (bb, cfun)
1888 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1889 gimple_values_to_profile (gsi_stmt (gsi), values);
1890
1891 values->safe_push (gimple_alloc_histogram_value (cfun,
1892 HIST_TYPE_TIME_PROFILE));
1893
1894 FOR_EACH_VEC_ELT (*values, i, hist)
1895 {
1896 switch (hist->type)
1897 {
1898 case HIST_TYPE_INTERVAL:
1899 hist->n_counters = hist->hdata.intvl.steps + 2;
1900 break;
1901
1902 case HIST_TYPE_POW2:
1903 hist->n_counters = 2;
1904 break;
1905
1906 case HIST_TYPE_TOPN_VALUES:
1907 case HIST_TYPE_INDIR_CALL:
1908 hist->n_counters = GCOV_TOPN_VALUES_COUNTERS;
1909 break;
1910
1911 case HIST_TYPE_TIME_PROFILE:
1912 hist->n_counters = 1;
1913 break;
1914
1915 case HIST_TYPE_AVERAGE:
1916 hist->n_counters = 2;
1917 break;
1918
1919 case HIST_TYPE_IOR:
1920 hist->n_counters = 1;
1921 break;
1922
1923 default:
1924 gcc_unreachable ();
1925 }
1926 if (dump_file && hist->hvalue.stmt != NULL)
1927 {
1928 fprintf (dump_file, "Stmt ");
1929 print_gimple_stmt (dump_file, hist->hvalue.stmt, 0, TDF_SLIM);
1930 dump_histogram_value (dump_file, hist);
1931 }
1932 }
1933 }
1934