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