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