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