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