1/* Transformations based on profile information for values.
2 Copyright (C) 2003-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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
107static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator *);
108static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator *);
109static bool gimple_mod_subtract_transform (gimple_stmt_iterator *);
110static bool gimple_stringops_transform (gimple_stmt_iterator *);
111static bool gimple_ic_transform (gimple_stmt_iterator *);
112
113/* Allocate histogram value. */
114
115histogram_value
116gimple_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
128static hashval_t
129histogram_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
136static int
137histogram_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
144static void
145set_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
167histogram_value
168gimple_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
178void
179gimple_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
189void
190gimple_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
212histogram_value
213gimple_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
226static void
227dump_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
343void
344stream_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
380void
381stream_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
442void
443dump_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
452void
453gimple_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
462void
463gimple_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
480void
481gimple_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
496static 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
501static int
502visit_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
520DEBUG_FUNCTION void
521verify_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
557static int
558free_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
566void
567free_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
582static bool
583check_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.ipa ().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
623bool
624gimple_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 return changed;
677}
678
679/* Generate code for transformation 1 (with parent gimple assignment
680 STMT and probability of taking the optimal path PROB, which is
681 equivalent to COUNT/ALL within roundoff error). This generates the
682 result into a temp and returns the temp; it does not replace or
683 alter the original STMT. */
684
685static tree
686gimple_divmod_fixed_value (gassign *stmt, tree value, profile_probability prob,
687 gcov_type count, gcov_type all)
688{
689 gassign *stmt1, *stmt2;
690 gcond *stmt3;
691 tree tmp0, tmp1, tmp2;
692 gimple *bb1end, *bb2end, *bb3end;
693 basic_block bb, bb2, bb3, bb4;
694 tree optype, op1, op2;
695 edge e12, e13, e23, e24, e34;
696 gimple_stmt_iterator gsi;
697
698 gcc_assert (is_gimple_assign (stmt)
699 && (gimple_assign_rhs_code (stmt) == TRUNC_DIV_EXPR
700 || gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR));
701
702 optype = TREE_TYPE (gimple_assign_lhs (stmt));
703 op1 = gimple_assign_rhs1 (stmt);
704 op2 = gimple_assign_rhs2 (stmt);
705
706 bb = gimple_bb (stmt);
707 gsi = gsi_for_stmt (stmt);
708
709 tmp0 = make_temp_ssa_name (optype, NULL, "PROF");
710 tmp1 = make_temp_ssa_name (optype, NULL, "PROF");
711 stmt1 = gimple_build_assign (tmp0, fold_convert (optype, value));
712 stmt2 = gimple_build_assign (tmp1, op2);
713 stmt3 = gimple_build_cond (NE_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
714 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
715 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
716 gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
717 bb1end = stmt3;
718
719 tmp2 = create_tmp_reg (optype, "PROF");
720 stmt1 = gimple_build_assign (tmp2, gimple_assign_rhs_code (stmt), op1, tmp0);
721 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
722 bb2end = stmt1;
723
724 stmt1 = gimple_build_assign (tmp2, gimple_assign_rhs_code (stmt), op1, op2);
725 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
726 bb3end = stmt1;
727
728 /* Fix CFG. */
729 /* Edge e23 connects bb2 to bb3, etc. */
730 e12 = split_block (bb, bb1end);
731 bb2 = e12->dest;
732 bb2->count = profile_count::from_gcov_type (count);
733 e23 = split_block (bb2, bb2end);
734 bb3 = e23->dest;
735 bb3->count = profile_count::from_gcov_type (all - count);
736 e34 = split_block (bb3, bb3end);
737 bb4 = e34->dest;
738 bb4->count = profile_count::from_gcov_type (all);
739
740 e12->flags &= ~EDGE_FALLTHRU;
741 e12->flags |= EDGE_FALSE_VALUE;
742 e12->probability = prob;
743
744 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
745 e13->probability = prob.invert ();
746
747 remove_edge (e23);
748
749 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
750 e24->probability = profile_probability::always ();
751
752 e34->probability = profile_probability::always ();
753
754 return tmp2;
755}
756
757/* Do transform 1) on INSN if applicable. */
758
759static bool
760gimple_divmod_fixed_value_transform (gimple_stmt_iterator *si)
761{
762 histogram_value histogram;
763 enum tree_code code;
764 gcov_type val, count, all;
765 tree result, value, tree_val;
766 profile_probability prob;
767 gassign *stmt;
768
769 stmt = dyn_cast <gassign *> (gsi_stmt (*si));
770 if (!stmt)
771 return false;
772
773 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt))))
774 return false;
775
776 code = gimple_assign_rhs_code (stmt);
777
778 if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR)
779 return false;
780
781 histogram = gimple_histogram_value_of_type (cfun, stmt,
782 HIST_TYPE_SINGLE_VALUE);
783 if (!histogram)
784 return false;
785
786 value = histogram->hvalue.value;
787 val = histogram->hvalue.counters[0];
788 count = histogram->hvalue.counters[1];
789 all = histogram->hvalue.counters[2];
790 gimple_remove_histogram_value (cfun, stmt, histogram);
791
792 /* We require that count is at least half of all; this means
793 that for the transformation to fire the value must be constant
794 at least 50% of time (and 75% gives the guarantee of usage). */
795 if (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1
796 || 2 * count < all
797 || optimize_bb_for_size_p (gimple_bb (stmt)))
798 return false;
799
800 if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count))
801 return false;
802
803 /* Compute probability of taking the optimal path. */
804 if (all > 0)
805 prob = profile_probability::probability_in_gcov_type (count, all);
806 else
807 prob = profile_probability::never ();
808
809 if (sizeof (gcov_type) == sizeof (HOST_WIDE_INT))
810 tree_val = build_int_cst (get_gcov_type (), val);
811 else
812 {
813 HOST_WIDE_INT a[2];
814 a[0] = (unsigned HOST_WIDE_INT) val;
815 a[1] = val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1;
816
817 tree_val = wide_int_to_tree (get_gcov_type (), wide_int::from_array (a, 2,
818 TYPE_PRECISION (get_gcov_type ()), false));
819 }
820 result = gimple_divmod_fixed_value (stmt, tree_val, prob, count, all);
821
822 if (dump_file)
823 {
824 fprintf (dump_file, "Div/mod by constant ");
825 print_generic_expr (dump_file, value, TDF_SLIM);
826 fprintf (dump_file, "=");
827 print_generic_expr (dump_file, tree_val, TDF_SLIM);
828 fprintf (dump_file, " transformation on insn ");
829 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
830 }
831
832 gimple_assign_set_rhs_from_tree (si, result);
833 update_stmt (gsi_stmt (*si));
834
835 return true;
836}
837
838/* Generate code for transformation 2 (with parent gimple assign STMT and
839 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
840 within roundoff error). This generates the result into a temp and returns
841 the temp; it does not replace or alter the original STMT. */
842
843static tree
844gimple_mod_pow2 (gassign *stmt, profile_probability prob, gcov_type count, gcov_type all)
845{
846 gassign *stmt1, *stmt2, *stmt3;
847 gcond *stmt4;
848 tree tmp2, tmp3;
849 gimple *bb1end, *bb2end, *bb3end;
850 basic_block bb, bb2, bb3, bb4;
851 tree optype, op1, op2;
852 edge e12, e13, e23, e24, e34;
853 gimple_stmt_iterator gsi;
854 tree result;
855
856 gcc_assert (is_gimple_assign (stmt)
857 && gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR);
858
859 optype = TREE_TYPE (gimple_assign_lhs (stmt));
860 op1 = gimple_assign_rhs1 (stmt);
861 op2 = gimple_assign_rhs2 (stmt);
862
863 bb = gimple_bb (stmt);
864 gsi = gsi_for_stmt (stmt);
865
866 result = create_tmp_reg (optype, "PROF");
867 tmp2 = make_temp_ssa_name (optype, NULL, "PROF");
868 tmp3 = make_temp_ssa_name (optype, NULL, "PROF");
869 stmt2 = gimple_build_assign (tmp2, PLUS_EXPR, op2,
870 build_int_cst (optype, -1));
871 stmt3 = gimple_build_assign (tmp3, BIT_AND_EXPR, tmp2, op2);
872 stmt4 = gimple_build_cond (NE_EXPR, tmp3, build_int_cst (optype, 0),
873 NULL_TREE, NULL_TREE);
874 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
875 gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
876 gsi_insert_before (&gsi, stmt4, GSI_SAME_STMT);
877 bb1end = stmt4;
878
879 /* tmp2 == op2-1 inherited from previous block. */
880 stmt1 = gimple_build_assign (result, BIT_AND_EXPR, op1, tmp2);
881 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
882 bb2end = stmt1;
883
884 stmt1 = gimple_build_assign (result, gimple_assign_rhs_code (stmt),
885 op1, op2);
886 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
887 bb3end = stmt1;
888
889 /* Fix CFG. */
890 /* Edge e23 connects bb2 to bb3, etc. */
891 e12 = split_block (bb, bb1end);
892 bb2 = e12->dest;
893 bb2->count = profile_count::from_gcov_type (count);
894 e23 = split_block (bb2, bb2end);
895 bb3 = e23->dest;
896 bb3->count = profile_count::from_gcov_type (all - count);
897 e34 = split_block (bb3, bb3end);
898 bb4 = e34->dest;
899 bb4->count = profile_count::from_gcov_type (all);
900
901 e12->flags &= ~EDGE_FALLTHRU;
902 e12->flags |= EDGE_FALSE_VALUE;
903 e12->probability = prob;
904
905 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
906 e13->probability = prob.invert ();
907
908 remove_edge (e23);
909
910 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
911 e24->probability = profile_probability::always ();
912
913 e34->probability = profile_probability::always ();
914
915 return result;
916}
917
918/* Do transform 2) on INSN if applicable. */
919
920static bool
921gimple_mod_pow2_value_transform (gimple_stmt_iterator *si)
922{
923 histogram_value histogram;
924 enum tree_code code;
925 gcov_type count, wrong_values, all;
926 tree lhs_type, result, value;
927 profile_probability prob;
928 gassign *stmt;
929
930 stmt = dyn_cast <gassign *> (gsi_stmt (*si));
931 if (!stmt)
932 return false;
933
934 lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
935 if (!INTEGRAL_TYPE_P (lhs_type))
936 return false;
937
938 code = gimple_assign_rhs_code (stmt);
939
940 if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type))
941 return false;
942
943 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_POW2);
944 if (!histogram)
945 return false;
946
947 value = histogram->hvalue.value;
948 wrong_values = histogram->hvalue.counters[0];
949 count = histogram->hvalue.counters[1];
950
951 gimple_remove_histogram_value (cfun, stmt, histogram);
952
953 /* We require that we hit a power of 2 at least half of all evaluations. */
954 if (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1
955 || count < wrong_values
956 || optimize_bb_for_size_p (gimple_bb (stmt)))
957 return false;
958
959 if (dump_file)
960 {
961 fprintf (dump_file, "Mod power of 2 transformation on insn ");
962 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
963 }
964
965 /* Compute probability of taking the optimal path. */
966 all = count + wrong_values;
967
968 if (check_counter (stmt, "pow2", &count, &all, gimple_bb (stmt)->count))
969 return false;
970
971 if (all > 0)
972 prob = profile_probability::probability_in_gcov_type (count, all);
973 else
974 prob = profile_probability::never ();
975
976 result = gimple_mod_pow2 (stmt, prob, count, all);
977
978 gimple_assign_set_rhs_from_tree (si, result);
979 update_stmt (gsi_stmt (*si));
980
981 return true;
982}
983
984/* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
985 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
986 supported and this is built into this interface. The probabilities of taking
987 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
988 COUNT2/ALL respectively within roundoff error). This generates the
989 result into a temp and returns the temp; it does not replace or alter
990 the original STMT. */
991/* FIXME: Generalize the interface to handle NCOUNTS > 1. */
992
993static tree
994gimple_mod_subtract (gassign *stmt, profile_probability prob1,
995 profile_probability prob2, int ncounts,
996 gcov_type count1, gcov_type count2, gcov_type all)
997{
998 gassign *stmt1;
999 gimple *stmt2;
1000 gcond *stmt3;
1001 tree tmp1;
1002 gimple *bb1end, *bb2end = NULL, *bb3end;
1003 basic_block bb, bb2, bb3, bb4;
1004 tree optype, op1, op2;
1005 edge e12, e23 = 0, e24, e34, e14;
1006 gimple_stmt_iterator gsi;
1007 tree result;
1008
1009 gcc_assert (is_gimple_assign (stmt)
1010 && gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR);
1011
1012 optype = TREE_TYPE (gimple_assign_lhs (stmt));
1013 op1 = gimple_assign_rhs1 (stmt);
1014 op2 = gimple_assign_rhs2 (stmt);
1015
1016 bb = gimple_bb (stmt);
1017 gsi = gsi_for_stmt (stmt);
1018
1019 result = create_tmp_reg (optype, "PROF");
1020 tmp1 = make_temp_ssa_name (optype, NULL, "PROF");
1021 stmt1 = gimple_build_assign (result, op1);
1022 stmt2 = gimple_build_assign (tmp1, op2);
1023 stmt3 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE);
1024 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
1025 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
1026 gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
1027 bb1end = stmt3;
1028
1029 if (ncounts) /* Assumed to be 0 or 1 */
1030 {
1031 stmt1 = gimple_build_assign (result, MINUS_EXPR, result, tmp1);
1032 stmt2 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE);
1033 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
1034 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
1035 bb2end = stmt2;
1036 }
1037
1038 /* Fallback case. */
1039 stmt1 = gimple_build_assign (result, gimple_assign_rhs_code (stmt),
1040 result, tmp1);
1041 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
1042 bb3end = stmt1;
1043
1044 /* Fix CFG. */
1045 /* Edge e23 connects bb2 to bb3, etc. */
1046 /* However block 3 is optional; if it is not there, references
1047 to 3 really refer to block 2. */
1048 e12 = split_block (bb, bb1end);
1049 bb2 = e12->dest;
1050 bb2->count = profile_count::from_gcov_type (all - count1);
1051
1052 if (ncounts) /* Assumed to be 0 or 1. */
1053 {
1054 e23 = split_block (bb2, bb2end);
1055 bb3 = e23->dest;
1056 bb3->count = profile_count::from_gcov_type (all - count1 - count2);
1057 }
1058
1059 e34 = split_block (ncounts ? bb3 : bb2, bb3end);
1060 bb4 = e34->dest;
1061 bb4->count = profile_count::from_gcov_type (all);
1062
1063 e12->flags &= ~EDGE_FALLTHRU;
1064 e12->flags |= EDGE_FALSE_VALUE;
1065 e12->probability = prob1.invert ();
1066
1067 e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE);
1068 e14->probability = prob1;
1069
1070 if (ncounts) /* Assumed to be 0 or 1. */
1071 {
1072 e23->flags &= ~EDGE_FALLTHRU;
1073 e23->flags |= EDGE_FALSE_VALUE;
1074 e23->probability = prob2.invert ();
1075
1076 e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE);
1077 e24->probability = prob2;
1078 }
1079
1080 e34->probability = profile_probability::always ();
1081
1082 return result;
1083}
1084
1085/* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1086
1087static bool
1088gimple_mod_subtract_transform (gimple_stmt_iterator *si)
1089{
1090 histogram_value histogram;
1091 enum tree_code code;
1092 gcov_type count, wrong_values, all;
1093 tree lhs_type, result;
1094 profile_probability prob1, prob2;
1095 unsigned int i, steps;
1096 gcov_type count1, count2;
1097 gassign *stmt;
1098 stmt = dyn_cast <gassign *> (gsi_stmt (*si));
1099 if (!stmt)
1100 return false;
1101
1102 lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
1103 if (!INTEGRAL_TYPE_P (lhs_type))
1104 return false;
1105
1106 code = gimple_assign_rhs_code (stmt);
1107
1108 if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type))
1109 return false;
1110
1111 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INTERVAL);
1112 if (!histogram)
1113 return false;
1114
1115 all = 0;
1116 wrong_values = 0;
1117 for (i = 0; i < histogram->hdata.intvl.steps; i++)
1118 all += histogram->hvalue.counters[i];
1119
1120 wrong_values += histogram->hvalue.counters[i];
1121 wrong_values += histogram->hvalue.counters[i+1];
1122 steps = histogram->hdata.intvl.steps;
1123 all += wrong_values;
1124 count1 = histogram->hvalue.counters[0];
1125 count2 = histogram->hvalue.counters[1];
1126
1127 /* Compute probability of taking the optimal path. */
1128 if (check_counter (stmt, "interval", &count1, &all, gimple_bb (stmt)->count))
1129 {
1130 gimple_remove_histogram_value (cfun, stmt, histogram);
1131 return false;
1132 }
1133
1134 if (flag_profile_correction && count1 + count2 > all)
1135 all = count1 + count2;
1136
1137 gcc_assert (count1 + count2 <= all);
1138
1139 /* We require that we use just subtractions in at least 50% of all
1140 evaluations. */
1141 count = 0;
1142 for (i = 0; i < histogram->hdata.intvl.steps; i++)
1143 {
1144 count += histogram->hvalue.counters[i];
1145 if (count * 2 >= all)
1146 break;
1147 }
1148 if (i == steps
1149 || optimize_bb_for_size_p (gimple_bb (stmt)))
1150 return false;
1151
1152 gimple_remove_histogram_value (cfun, stmt, histogram);
1153 if (dump_file)
1154 {
1155 fprintf (dump_file, "Mod subtract transformation on insn ");
1156 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1157 }
1158
1159 /* Compute probability of taking the optimal path(s). */
1160 if (all > 0)
1161 {
1162 prob1 = profile_probability::probability_in_gcov_type (count1, all);
1163 prob2 = profile_probability::probability_in_gcov_type (count2, all);
1164 }
1165 else
1166 {
1167 prob1 = prob2 = profile_probability::never ();
1168 }
1169
1170 /* In practice, "steps" is always 2. This interface reflects this,
1171 and will need to be changed if "steps" can change. */
1172 result = gimple_mod_subtract (stmt, prob1, prob2, i, count1, count2, all);
1173
1174 gimple_assign_set_rhs_from_tree (si, result);
1175 update_stmt (gsi_stmt (*si));
1176
1177 return true;
1178}
1179
1180typedef int_hash <unsigned int, 0, UINT_MAX> profile_id_hash;
1181
1182static hash_map<profile_id_hash, cgraph_node *> *cgraph_node_map = 0;
1183
1184/* Returns true if node graph is initialized. This
1185 is used to test if profile_id has been created
1186 for cgraph_nodes. */
1187
1188bool
1189coverage_node_map_initialized_p (void)
1190{
1191 return cgraph_node_map != 0;
1192}
1193
1194/* Initialize map from PROFILE_ID to CGRAPH_NODE.
1195 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1196 that the PROFILE_IDs was already assigned. */
1197
1198void
1199init_node_map (bool local)
1200{
1201 struct cgraph_node *n;
1202 cgraph_node_map = new hash_map<profile_id_hash, cgraph_node *>;
1203
1204 FOR_EACH_DEFINED_FUNCTION (n)
1205 if (n->has_gimple_body_p ())
1206 {
1207 cgraph_node **val;
1208 if (local)
1209 {
1210 n->profile_id = coverage_compute_profile_id (n);
1211 while ((val = cgraph_node_map->get (n->profile_id))
1212 || !n->profile_id)
1213 {
1214 if (dump_file)
1215 fprintf (dump_file, "Local profile-id %i conflict"
1216 " with nodes %s %s\n",
1217 n->profile_id,
1218 n->dump_name (),
1219 (*val)->dump_name ());
1220 n->profile_id = (n->profile_id + 1) & 0x7fffffff;
1221 }
1222 }
1223 else if (!n->profile_id)
1224 {
1225 if (dump_file)
1226 fprintf (dump_file,
1227 "Node %s has no profile-id"
1228 " (profile feedback missing?)\n",
1229 n->dump_name ());
1230 continue;
1231 }
1232 else if ((val = cgraph_node_map->get (n->profile_id)))
1233 {
1234 if (dump_file)
1235 fprintf (dump_file,
1236 "Node %s has IP profile-id %i conflict. "
1237 "Giving up.\n",
1238 n->dump_name (), n->profile_id);
1239 *val = NULL;
1240 continue;
1241 }
1242 cgraph_node_map->put (n->profile_id, n);
1243 }
1244}
1245
1246/* Delete the CGRAPH_NODE_MAP. */
1247
1248void
1249del_node_map (void)
1250{
1251 delete cgraph_node_map;
1252}
1253
1254/* Return cgraph node for function with pid */
1255
1256struct cgraph_node*
1257find_func_by_profile_id (int profile_id)
1258{
1259 cgraph_node **val = cgraph_node_map->get (profile_id);
1260 if (val)
1261 return *val;
1262 else
1263 return NULL;
1264}
1265
1266/* Perform sanity check on the indirect call target. Due to race conditions,
1267 false function target may be attributed to an indirect call site. If the
1268 call expression type mismatches with the target function's type, expand_call
1269 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1270 Returns true if TARGET is considered ok for call CALL_STMT. */
1271
1272bool
1273check_ic_target (gcall *call_stmt, struct cgraph_node *target)
1274{
1275 location_t locus;
1276 if (gimple_check_call_matching_types (call_stmt, target->decl, true))
1277 return true;
1278
1279 locus = gimple_location (call_stmt);
1280 if (dump_enabled_p ())
1281 dump_printf_loc (MSG_MISSED_OPTIMIZATION, locus,
1282 "Skipping target %s with mismatching types for icall\n",
1283 target->name ());
1284 return false;
1285}
1286
1287/* Do transformation
1288
1289 if (actual_callee_address == address_of_most_common_function/method)
1290 do direct call
1291 else
1292 old call
1293 */
1294
1295gcall *
1296gimple_ic (gcall *icall_stmt, struct cgraph_node *direct_call,
1297 profile_probability prob)
1298{
1299 gcall *dcall_stmt;
1300 gassign *load_stmt;
1301 gcond *cond_stmt;
1302 gcall *iretbnd_stmt = NULL;
1303 tree tmp0, tmp1, tmp;
1304 basic_block cond_bb, dcall_bb, icall_bb, join_bb = NULL;
1305 tree optype = build_pointer_type (void_type_node);
1306 edge e_cd, e_ci, e_di, e_dj = NULL, e_ij;
1307 gimple_stmt_iterator gsi;
1308 int lp_nr, dflags;
1309 edge e_eh, e;
1310 edge_iterator ei;
1311 gimple_stmt_iterator psi;
1312
1313 cond_bb = gimple_bb (icall_stmt);
1314 gsi = gsi_for_stmt (icall_stmt);
1315
1316 if (gimple_call_with_bounds_p (icall_stmt) && gimple_call_lhs (icall_stmt))
1317 iretbnd_stmt = chkp_retbnd_call_by_val (gimple_call_lhs (icall_stmt));
1318
1319 tmp0 = make_temp_ssa_name (optype, NULL, "PROF");
1320 tmp1 = make_temp_ssa_name (optype, NULL, "PROF");
1321 tmp = unshare_expr (gimple_call_fn (icall_stmt));
1322 load_stmt = gimple_build_assign (tmp0, tmp);
1323 gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
1324
1325 tmp = fold_convert (optype, build_addr (direct_call->decl));
1326 load_stmt = gimple_build_assign (tmp1, tmp);
1327 gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
1328
1329 cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
1330 gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1331
1332 if (TREE_CODE (gimple_vdef (icall_stmt)) == SSA_NAME)
1333 {
1334 unlink_stmt_vdef (icall_stmt);
1335 release_ssa_name (gimple_vdef (icall_stmt));
1336 }
1337 gimple_set_vdef (icall_stmt, NULL_TREE);
1338 gimple_set_vuse (icall_stmt, NULL_TREE);
1339 update_stmt (icall_stmt);
1340 dcall_stmt = as_a <gcall *> (gimple_copy (icall_stmt));
1341 gimple_call_set_fndecl (dcall_stmt, direct_call->decl);
1342 dflags = flags_from_decl_or_type (direct_call->decl);
1343 if ((dflags & ECF_NORETURN) != 0
1344 && should_remove_lhs_p (gimple_call_lhs (dcall_stmt)))
1345 gimple_call_set_lhs (dcall_stmt, NULL_TREE);
1346 gsi_insert_before (&gsi, dcall_stmt, GSI_SAME_STMT);
1347
1348 /* Fix CFG. */
1349 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1350 e_cd = split_block (cond_bb, cond_stmt);
1351 dcall_bb = e_cd->dest;
1352 dcall_bb->count = cond_bb->count.apply_probability (prob);
1353
1354 e_di = split_block (dcall_bb, dcall_stmt);
1355 icall_bb = e_di->dest;
1356 icall_bb->count = cond_bb->count - dcall_bb->count;
1357
1358 /* Do not disturb existing EH edges from the indirect call. */
1359 if (!stmt_ends_bb_p (icall_stmt))
1360 e_ij = split_block (icall_bb, icall_stmt);
1361 else
1362 {
1363 e_ij = find_fallthru_edge (icall_bb->succs);
1364 /* The indirect call might be noreturn. */
1365 if (e_ij != NULL)
1366 {
1367 e_ij->probability = profile_probability::always ();
1368 e_ij = single_pred_edge (split_edge (e_ij));
1369 }
1370 }
1371 if (e_ij != NULL)
1372 {
1373 join_bb = e_ij->dest;
1374 join_bb->count = cond_bb->count;
1375 }
1376
1377 e_cd->flags = (e_cd->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE;
1378 e_cd->probability = prob;
1379
1380 e_ci = make_edge (cond_bb, icall_bb, EDGE_FALSE_VALUE);
1381 e_ci->probability = prob.invert ();
1382
1383 remove_edge (e_di);
1384
1385 if (e_ij != NULL)
1386 {
1387 if ((dflags & ECF_NORETURN) == 0)
1388 {
1389 e_dj = make_edge (dcall_bb, join_bb, EDGE_FALLTHRU);
1390 e_dj->probability = profile_probability::always ();
1391 }
1392 e_ij->probability = profile_probability::always ();
1393 }
1394
1395 /* Insert PHI node for the call result if necessary. */
1396 if (gimple_call_lhs (icall_stmt)
1397 && TREE_CODE (gimple_call_lhs (icall_stmt)) == SSA_NAME
1398 && (dflags & ECF_NORETURN) == 0)
1399 {
1400 tree result = gimple_call_lhs (icall_stmt);
1401 gphi *phi = create_phi_node (result, join_bb);
1402 gimple_call_set_lhs (icall_stmt,
1403 duplicate_ssa_name (result, icall_stmt));
1404 add_phi_arg (phi, gimple_call_lhs (icall_stmt), e_ij, UNKNOWN_LOCATION);
1405 gimple_call_set_lhs (dcall_stmt,
1406 duplicate_ssa_name (result, dcall_stmt));
1407 add_phi_arg (phi, gimple_call_lhs (dcall_stmt), e_dj, UNKNOWN_LOCATION);
1408
1409 /* If indirect call has following BUILT_IN_CHKP_BNDRET
1410 call then we need to make it's copy for the direct
1411 call. */
1412 if (iretbnd_stmt)
1413 {
1414 if (gimple_call_lhs (iretbnd_stmt))
1415 {
1416 gimple *copy;
1417
1418 if (TREE_CODE (gimple_vdef (iretbnd_stmt)) == SSA_NAME)
1419 {
1420 unlink_stmt_vdef (iretbnd_stmt);
1421 release_ssa_name (gimple_vdef (iretbnd_stmt));
1422 }
1423 gimple_set_vdef (iretbnd_stmt, NULL_TREE);
1424 gimple_set_vuse (iretbnd_stmt, NULL_TREE);
1425 update_stmt (iretbnd_stmt);
1426
1427 result = gimple_call_lhs (iretbnd_stmt);
1428 phi = create_phi_node (result, join_bb);
1429
1430 copy = gimple_copy (iretbnd_stmt);
1431 gimple_call_set_arg (copy, 0,
1432 gimple_call_lhs (dcall_stmt));
1433 gimple_call_set_lhs (copy, duplicate_ssa_name (result, copy));
1434 gsi_insert_on_edge (e_dj, copy);
1435 add_phi_arg (phi, gimple_call_lhs (copy),
1436 e_dj, UNKNOWN_LOCATION);
1437
1438 gimple_call_set_arg (iretbnd_stmt, 0,
1439 gimple_call_lhs (icall_stmt));
1440 gimple_call_set_lhs (iretbnd_stmt,
1441 duplicate_ssa_name (result, iretbnd_stmt));
1442 psi = gsi_for_stmt (iretbnd_stmt);
1443 gsi_remove (&psi, false);
1444 gsi_insert_on_edge (e_ij, iretbnd_stmt);
1445 add_phi_arg (phi, gimple_call_lhs (iretbnd_stmt),
1446 e_ij, UNKNOWN_LOCATION);
1447
1448 gsi_commit_one_edge_insert (e_dj, NULL);
1449 gsi_commit_one_edge_insert (e_ij, NULL);
1450 }
1451 else
1452 {
1453 psi = gsi_for_stmt (iretbnd_stmt);
1454 gsi_remove (&psi, true);
1455 }
1456 }
1457 }
1458
1459 /* Build an EH edge for the direct call if necessary. */
1460 lp_nr = lookup_stmt_eh_lp (icall_stmt);
1461 if (lp_nr > 0 && stmt_could_throw_p (dcall_stmt))
1462 {
1463 add_stmt_to_eh_lp (dcall_stmt, lp_nr);
1464 }
1465
1466 FOR_EACH_EDGE (e_eh, ei, icall_bb->succs)
1467 if (e_eh->flags & (EDGE_EH | EDGE_ABNORMAL))
1468 {
1469 e = make_edge (dcall_bb, e_eh->dest, e_eh->flags);
1470 e->probability = e_eh->probability;
1471 for (gphi_iterator psi = gsi_start_phis (e_eh->dest);
1472 !gsi_end_p (psi); gsi_next (&psi))
1473 {
1474 gphi *phi = psi.phi ();
1475 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, e),
1476 PHI_ARG_DEF_FROM_EDGE (phi, e_eh));
1477 }
1478 }
1479 if (!stmt_could_throw_p (dcall_stmt))
1480 gimple_purge_dead_eh_edges (dcall_bb);
1481 return dcall_stmt;
1482}
1483
1484/*
1485 For every checked indirect/virtual call determine if most common pid of
1486 function/class method has probability more than 50%. If yes modify code of
1487 this call to:
1488 */
1489
1490static bool
1491gimple_ic_transform (gimple_stmt_iterator *gsi)
1492{
1493 gcall *stmt;
1494 histogram_value histogram;
1495 gcov_type val, count, all, bb_all;
1496 struct cgraph_node *direct_call;
1497
1498 stmt = dyn_cast <gcall *> (gsi_stmt (*gsi));
1499 if (!stmt)
1500 return false;
1501
1502 if (gimple_call_fndecl (stmt) != NULL_TREE)
1503 return false;
1504
1505 if (gimple_call_internal_p (stmt))
1506 return false;
1507
1508 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INDIR_CALL);
1509 if (!histogram)
1510 return false;
1511
1512 val = histogram->hvalue.counters [0];
1513 count = histogram->hvalue.counters [1];
1514 all = histogram->hvalue.counters [2];
1515
1516 bb_all = gimple_bb (stmt)->count.ipa ().to_gcov_type ();
1517 /* The order of CHECK_COUNTER calls is important -
1518 since check_counter can correct the third parameter
1519 and we want to make count <= all <= bb_all. */
1520 if (check_counter (stmt, "ic", &all, &bb_all, gimple_bb (stmt)->count)
1521 || check_counter (stmt, "ic", &count, &all,
1522 profile_count::from_gcov_type (all)))
1523 {
1524 gimple_remove_histogram_value (cfun, stmt, histogram);
1525 return false;
1526 }
1527
1528 if (4 * count <= 3 * all)
1529 return false;
1530
1531 direct_call = find_func_by_profile_id ((int)val);
1532
1533 if (direct_call == NULL)
1534 {
1535 if (val)
1536 {
1537 if (dump_file)
1538 {
1539 fprintf (dump_file, "Indirect call -> direct call from other module");
1540 print_generic_expr (dump_file, gimple_call_fn (stmt), TDF_SLIM);
1541 fprintf (dump_file, "=> %i (will resolve only with LTO)\n", (int)val);
1542 }
1543 }
1544 return false;
1545 }
1546
1547 if (!check_ic_target (stmt, direct_call))
1548 {
1549 if (dump_file)
1550 {
1551 fprintf (dump_file, "Indirect call -> direct call ");
1552 print_generic_expr (dump_file, gimple_call_fn (stmt), TDF_SLIM);
1553 fprintf (dump_file, "=> ");
1554 print_generic_expr (dump_file, direct_call->decl, TDF_SLIM);
1555 fprintf (dump_file, " transformation skipped because of type mismatch");
1556 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1557 }
1558 gimple_remove_histogram_value (cfun, stmt, histogram);
1559 return false;
1560 }
1561
1562 if (dump_file)
1563 {
1564 fprintf (dump_file, "Indirect call -> direct call ");
1565 print_generic_expr (dump_file, gimple_call_fn (stmt), TDF_SLIM);
1566 fprintf (dump_file, "=> ");
1567 print_generic_expr (dump_file, direct_call->decl, TDF_SLIM);
1568 fprintf (dump_file, " transformation on insn postponned to ipa-profile");
1569 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1570 fprintf (dump_file, "hist->count %" PRId64
1571 " hist->all %" PRId64"\n", count, all);
1572 }
1573
1574 return true;
1575}
1576
1577/* Return true if the stringop CALL shall be profiled. SIZE_ARG be
1578 set to the argument index for the size of the string operation. */
1579
1580static bool
1581interesting_stringop_to_profile_p (gcall *call, int *size_arg)
1582{
1583 enum built_in_function fcode;
1584
1585 fcode = DECL_FUNCTION_CODE (gimple_call_fndecl (call));
1586 if (fcode != BUILT_IN_MEMCPY && fcode != BUILT_IN_MEMPCPY
1587 && fcode != BUILT_IN_MEMSET && fcode != BUILT_IN_BZERO)
1588 return false;
1589
1590 switch (fcode)
1591 {
1592 case BUILT_IN_MEMCPY:
1593 case BUILT_IN_MEMPCPY:
1594 *size_arg = 2;
1595 return validate_gimple_arglist (call, POINTER_TYPE, POINTER_TYPE,
1596 INTEGER_TYPE, VOID_TYPE);
1597 case BUILT_IN_MEMSET:
1598 *size_arg = 2;
1599 return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE,
1600 INTEGER_TYPE, VOID_TYPE);
1601 case BUILT_IN_BZERO:
1602 *size_arg = 1;
1603 return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE,
1604 VOID_TYPE);
1605 default:
1606 gcc_unreachable ();
1607 }
1608}
1609
1610/* Convert stringop (..., vcall_size)
1611 into
1612 if (vcall_size == icall_size)
1613 stringop (..., icall_size);
1614 else
1615 stringop (..., vcall_size);
1616 assuming we'll propagate a true constant into ICALL_SIZE later. */
1617
1618static void
1619gimple_stringop_fixed_value (gcall *vcall_stmt, tree icall_size, profile_probability prob,
1620 gcov_type count, gcov_type all)
1621{
1622 gassign *tmp_stmt;
1623 gcond *cond_stmt;
1624 gcall *icall_stmt;
1625 tree tmp0, tmp1, vcall_size, optype;
1626 basic_block cond_bb, icall_bb, vcall_bb, join_bb;
1627 edge e_ci, e_cv, e_iv, e_ij, e_vj;
1628 gimple_stmt_iterator gsi;
1629 int size_arg;
1630
1631 if (!interesting_stringop_to_profile_p (vcall_stmt, &size_arg))
1632 gcc_unreachable ();
1633
1634 cond_bb = gimple_bb (vcall_stmt);
1635 gsi = gsi_for_stmt (vcall_stmt);
1636
1637 vcall_size = gimple_call_arg (vcall_stmt, size_arg);
1638 optype = TREE_TYPE (vcall_size);
1639
1640 tmp0 = make_temp_ssa_name (optype, NULL, "PROF");
1641 tmp1 = make_temp_ssa_name (optype, NULL, "PROF");
1642 tmp_stmt = gimple_build_assign (tmp0, fold_convert (optype, icall_size));
1643 gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT);
1644
1645 tmp_stmt = gimple_build_assign (tmp1, vcall_size);
1646 gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT);
1647
1648 cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
1649 gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1650
1651 if (TREE_CODE (gimple_vdef (vcall_stmt)) == SSA_NAME)
1652 {
1653 unlink_stmt_vdef (vcall_stmt);
1654 release_ssa_name (gimple_vdef (vcall_stmt));
1655 }
1656 gimple_set_vdef (vcall_stmt, NULL);
1657 gimple_set_vuse (vcall_stmt, NULL);
1658 update_stmt (vcall_stmt);
1659 icall_stmt = as_a <gcall *> (gimple_copy (vcall_stmt));
1660 gimple_call_set_arg (icall_stmt, size_arg,
1661 fold_convert (optype, icall_size));
1662 gsi_insert_before (&gsi, icall_stmt, GSI_SAME_STMT);
1663
1664 /* Fix CFG. */
1665 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1666 e_ci = split_block (cond_bb, cond_stmt);
1667 icall_bb = e_ci->dest;
1668 icall_bb->count = profile_count::from_gcov_type (count);
1669
1670 e_iv = split_block (icall_bb, icall_stmt);
1671 vcall_bb = e_iv->dest;
1672 vcall_bb->count = profile_count::from_gcov_type (all - count);
1673
1674 e_vj = split_block (vcall_bb, vcall_stmt);
1675 join_bb = e_vj->dest;
1676 join_bb->count = profile_count::from_gcov_type (all);
1677
1678 e_ci->flags = (e_ci->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE;
1679 e_ci->probability = prob;
1680
1681 e_cv = make_edge (cond_bb, vcall_bb, EDGE_FALSE_VALUE);
1682 e_cv->probability = prob.invert ();
1683
1684 remove_edge (e_iv);
1685
1686 e_ij = make_edge (icall_bb, join_bb, EDGE_FALLTHRU);
1687 e_ij->probability = profile_probability::always ();
1688
1689 e_vj->probability = profile_probability::always ();
1690
1691 /* Insert PHI node for the call result if necessary. */
1692 if (gimple_call_lhs (vcall_stmt)
1693 && TREE_CODE (gimple_call_lhs (vcall_stmt)) == SSA_NAME)
1694 {
1695 tree result = gimple_call_lhs (vcall_stmt);
1696 gphi *phi = create_phi_node (result, join_bb);
1697 gimple_call_set_lhs (vcall_stmt,
1698 duplicate_ssa_name (result, vcall_stmt));
1699 add_phi_arg (phi, gimple_call_lhs (vcall_stmt), e_vj, UNKNOWN_LOCATION);
1700 gimple_call_set_lhs (icall_stmt,
1701 duplicate_ssa_name (result, icall_stmt));
1702 add_phi_arg (phi, gimple_call_lhs (icall_stmt), e_ij, UNKNOWN_LOCATION);
1703 }
1704
1705 /* Because these are all string op builtins, they're all nothrow. */
1706 gcc_assert (!stmt_could_throw_p (vcall_stmt));
1707 gcc_assert (!stmt_could_throw_p (icall_stmt));
1708}
1709
1710/* Find values inside STMT for that we want to measure histograms for
1711 division/modulo optimization. */
1712
1713static bool
1714gimple_stringops_transform (gimple_stmt_iterator *gsi)
1715{
1716 gcall *stmt;
1717 tree blck_size;
1718 enum built_in_function fcode;
1719 histogram_value histogram;
1720 gcov_type count, all, val;
1721 tree dest, src;
1722 unsigned int dest_align, src_align;
1723 profile_probability prob;
1724 tree tree_val;
1725 int size_arg;
1726
1727 stmt = dyn_cast <gcall *> (gsi_stmt (*gsi));
1728 if (!stmt)
1729 return false;
1730
1731 if (!gimple_call_builtin_p (gsi_stmt (*gsi), BUILT_IN_NORMAL))
1732 return false;
1733
1734 if (!interesting_stringop_to_profile_p (stmt, &size_arg))
1735 return false;
1736
1737 blck_size = gimple_call_arg (stmt, size_arg);
1738 if (TREE_CODE (blck_size) == INTEGER_CST)
1739 return false;
1740
1741 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE);
1742 if (!histogram)
1743 return false;
1744
1745 val = histogram->hvalue.counters[0];
1746 count = histogram->hvalue.counters[1];
1747 all = histogram->hvalue.counters[2];
1748 gimple_remove_histogram_value (cfun, stmt, histogram);
1749
1750 /* We require that count is at least half of all; this means
1751 that for the transformation to fire the value must be constant
1752 at least 80% of time. */
1753 if ((6 * count / 5) < all || optimize_bb_for_size_p (gimple_bb (stmt)))
1754 return false;
1755 if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count))
1756 return false;
1757 if (all > 0)
1758 prob = profile_probability::probability_in_gcov_type (count, all);
1759 else
1760 prob = profile_probability::never ();
1761
1762 dest = gimple_call_arg (stmt, 0);
1763 dest_align = get_pointer_alignment (dest);
1764 fcode = DECL_FUNCTION_CODE (gimple_call_fndecl (stmt));
1765 switch (fcode)
1766 {
1767 case BUILT_IN_MEMCPY:
1768 case BUILT_IN_MEMPCPY:
1769 src = gimple_call_arg (stmt, 1);
1770 src_align = get_pointer_alignment (src);
1771 if (!can_move_by_pieces (val, MIN (dest_align, src_align)))
1772 return false;
1773 break;
1774 case BUILT_IN_MEMSET:
1775 if (!can_store_by_pieces (val, builtin_memset_read_str,
1776 gimple_call_arg (stmt, 1),
1777 dest_align, true))
1778 return false;
1779 break;
1780 case BUILT_IN_BZERO:
1781 if (!can_store_by_pieces (val, builtin_memset_read_str,
1782 integer_zero_node,
1783 dest_align, true))
1784 return false;
1785 break;
1786 default:
1787 gcc_unreachable ();
1788 }
1789
1790 if (sizeof (gcov_type) == sizeof (HOST_WIDE_INT))
1791 tree_val = build_int_cst (get_gcov_type (), val);
1792 else
1793 {
1794 HOST_WIDE_INT a[2];
1795 a[0] = (unsigned HOST_WIDE_INT) val;
1796 a[1] = val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1;
1797
1798 tree_val = wide_int_to_tree (get_gcov_type (), wide_int::from_array (a, 2,
1799 TYPE_PRECISION (get_gcov_type ()), false));
1800 }
1801
1802 if (dump_file)
1803 {
1804 fprintf (dump_file, "Single value %i stringop transformation on ",
1805 (int)val);
1806 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1807 }
1808
1809 gimple_stringop_fixed_value (stmt, tree_val, prob, count, all);
1810
1811 return true;
1812}
1813
1814void
1815stringop_block_profile (gimple *stmt, unsigned int *expected_align,
1816 HOST_WIDE_INT *expected_size)
1817{
1818 histogram_value histogram;
1819 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_AVERAGE);
1820
1821 if (!histogram)
1822 *expected_size = -1;
1823 else if (!histogram->hvalue.counters[1])
1824 {
1825 *expected_size = -1;
1826 gimple_remove_histogram_value (cfun, stmt, histogram);
1827 }
1828 else
1829 {
1830 gcov_type size;
1831 size = ((histogram->hvalue.counters[0]
1832 + histogram->hvalue.counters[1] / 2)
1833 / histogram->hvalue.counters[1]);
1834 /* Even if we can hold bigger value in SIZE, INT_MAX
1835 is safe "infinity" for code generation strategies. */
1836 if (size > INT_MAX)
1837 size = INT_MAX;
1838 *expected_size = size;
1839 gimple_remove_histogram_value (cfun, stmt, histogram);
1840 }
1841
1842 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_IOR);
1843
1844 if (!histogram)
1845 *expected_align = 0;
1846 else if (!histogram->hvalue.counters[0])
1847 {
1848 gimple_remove_histogram_value (cfun, stmt, histogram);
1849 *expected_align = 0;
1850 }
1851 else
1852 {
1853 gcov_type count;
1854 unsigned int alignment;
1855
1856 count = histogram->hvalue.counters[0];
1857 alignment = 1;
1858 while (!(count & alignment)
1859 && (alignment <= UINT_MAX / 2 / BITS_PER_UNIT))
1860 alignment <<= 1;
1861 *expected_align = alignment * BITS_PER_UNIT;
1862 gimple_remove_histogram_value (cfun, stmt, histogram);
1863 }
1864}
1865
1866
1867/* Find values inside STMT for that we want to measure histograms for
1868 division/modulo optimization. */
1869
1870static void
1871gimple_divmod_values_to_profile (gimple *stmt, histogram_values *values)
1872{
1873 tree lhs, divisor, op0, type;
1874 histogram_value hist;
1875
1876 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1877 return;
1878
1879 lhs = gimple_assign_lhs (stmt);
1880 type = TREE_TYPE (lhs);
1881 if (!INTEGRAL_TYPE_P (type))
1882 return;
1883
1884 switch (gimple_assign_rhs_code (stmt))
1885 {
1886 case TRUNC_DIV_EXPR:
1887 case TRUNC_MOD_EXPR:
1888 divisor = gimple_assign_rhs2 (stmt);
1889 op0 = gimple_assign_rhs1 (stmt);
1890
1891 values->reserve (3);
1892
1893 if (TREE_CODE (divisor) == SSA_NAME)
1894 /* Check for the case where the divisor is the same value most
1895 of the time. */
1896 values->quick_push (gimple_alloc_histogram_value (cfun,
1897 HIST_TYPE_SINGLE_VALUE,
1898 stmt, divisor));
1899
1900 /* For mod, check whether it is not often a noop (or replaceable by
1901 a few subtractions). */
1902 if (gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR
1903 && TYPE_UNSIGNED (type)
1904 && TREE_CODE (divisor) == SSA_NAME)
1905 {
1906 tree val;
1907 /* Check for a special case where the divisor is power of 2. */
1908 values->quick_push (gimple_alloc_histogram_value (cfun,
1909 HIST_TYPE_POW2,
1910 stmt, divisor));
1911
1912 val = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
1913 hist = gimple_alloc_histogram_value (cfun, HIST_TYPE_INTERVAL,
1914 stmt, val);
1915 hist->hdata.intvl.int_start = 0;
1916 hist->hdata.intvl.steps = 2;
1917 values->quick_push (hist);
1918 }
1919 return;
1920
1921 default:
1922 return;
1923 }
1924}
1925
1926/* Find calls inside STMT for that we want to measure histograms for
1927 indirect/virtual call optimization. */
1928
1929static void
1930gimple_indirect_call_to_profile (gimple *stmt, histogram_values *values)
1931{
1932 tree callee;
1933
1934 if (gimple_code (stmt) != GIMPLE_CALL
1935 || gimple_call_internal_p (stmt)
1936 || gimple_call_fndecl (stmt) != NULL_TREE)
1937 return;
1938
1939 callee = gimple_call_fn (stmt);
1940
1941 values->reserve (3);
1942
1943 values->quick_push (gimple_alloc_histogram_value (
1944 cfun,
1945 PARAM_VALUE (PARAM_INDIR_CALL_TOPN_PROFILE) ?
1946 HIST_TYPE_INDIR_CALL_TOPN :
1947 HIST_TYPE_INDIR_CALL,
1948 stmt, callee));
1949
1950 return;
1951}
1952
1953/* Find values inside STMT for that we want to measure histograms for
1954 string operations. */
1955
1956static void
1957gimple_stringops_values_to_profile (gimple *gs, histogram_values *values)
1958{
1959 gcall *stmt;
1960 tree blck_size;
1961 tree dest;
1962 int size_arg;
1963
1964 stmt = dyn_cast <gcall *> (gs);
1965 if (!stmt)
1966 return;
1967
1968 if (!gimple_call_builtin_p (gs, BUILT_IN_NORMAL))
1969 return;
1970
1971 if (!interesting_stringop_to_profile_p (stmt, &size_arg))
1972 return;
1973
1974 dest = gimple_call_arg (stmt, 0);
1975 blck_size = gimple_call_arg (stmt, size_arg);
1976
1977 if (TREE_CODE (blck_size) != INTEGER_CST)
1978 {
1979 values->safe_push (gimple_alloc_histogram_value (cfun,
1980 HIST_TYPE_SINGLE_VALUE,
1981 stmt, blck_size));
1982 values->safe_push (gimple_alloc_histogram_value (cfun, HIST_TYPE_AVERAGE,
1983 stmt, blck_size));
1984 }
1985
1986 if (TREE_CODE (blck_size) != INTEGER_CST)
1987 values->safe_push (gimple_alloc_histogram_value (cfun, HIST_TYPE_IOR,
1988 stmt, dest));
1989}
1990
1991/* Find values inside STMT for that we want to measure histograms and adds
1992 them to list VALUES. */
1993
1994static void
1995gimple_values_to_profile (gimple *stmt, histogram_values *values)
1996{
1997 gimple_divmod_values_to_profile (stmt, values);
1998 gimple_stringops_values_to_profile (stmt, values);
1999 gimple_indirect_call_to_profile (stmt, values);
2000}
2001
2002void
2003gimple_find_values_to_profile (histogram_values *values)
2004{
2005 basic_block bb;
2006 gimple_stmt_iterator gsi;
2007 unsigned i;
2008 histogram_value hist = NULL;
2009 values->create (0);
2010
2011 FOR_EACH_BB_FN (bb, cfun)
2012 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2013 gimple_values_to_profile (gsi_stmt (gsi), values);
2014
2015 values->safe_push (gimple_alloc_histogram_value (cfun, HIST_TYPE_TIME_PROFILE, 0, 0));
2016
2017 FOR_EACH_VEC_ELT (*values, i, hist)
2018 {
2019 switch (hist->type)
2020 {
2021 case HIST_TYPE_INTERVAL:
2022 hist->n_counters = hist->hdata.intvl.steps + 2;
2023 break;
2024
2025 case HIST_TYPE_POW2:
2026 hist->n_counters = 2;
2027 break;
2028
2029 case HIST_TYPE_SINGLE_VALUE:
2030 hist->n_counters = 3;
2031 break;
2032
2033 case HIST_TYPE_INDIR_CALL:
2034 hist->n_counters = 3;
2035 break;
2036
2037 case HIST_TYPE_TIME_PROFILE:
2038 hist->n_counters = 1;
2039 break;
2040
2041 case HIST_TYPE_AVERAGE:
2042 hist->n_counters = 2;
2043 break;
2044
2045 case HIST_TYPE_IOR:
2046 hist->n_counters = 1;
2047 break;
2048
2049 case HIST_TYPE_INDIR_CALL_TOPN:
2050 hist->n_counters = GCOV_ICALL_TOPN_NCOUNTS;
2051 break;
2052
2053 default:
2054 gcc_unreachable ();
2055 }
2056 if (dump_file)
2057 {
2058 fprintf (dump_file, "Stmt ");
2059 print_gimple_stmt (dump_file, hist->hvalue.stmt, 0, TDF_SLIM);
2060 dump_histogram_value (dump_file, hist);
2061 }
2062 }
2063}
2064