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