Branch data Line data Source code
1 : : /* Transformations based on profile information for values.
2 : : Copyright (C) 2003-2024 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 : 1243 : gimple_alloc_histogram_value (struct function *fun ATTRIBUTE_UNUSED,
115 : : enum hist_type type, gimple *stmt, tree value)
116 : : {
117 : 1243 : histogram_value hist = (histogram_value) xcalloc (1, sizeof (*hist));
118 : 1243 : hist->hvalue.value = value;
119 : 1243 : hist->hvalue.stmt = stmt;
120 : 1243 : hist->type = type;
121 : 1243 : 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 : 52840 : histogram_eq (const void *x, const void *y)
136 : : {
137 : 52840 : return ((const_histogram_value) x)->hvalue.stmt == (const gimple *) y;
138 : : }
139 : :
140 : : /* Set histogram for STMT. */
141 : :
142 : : static void
143 : 526 : set_histogram_value (struct function *fun, gimple *stmt, histogram_value hist)
144 : : {
145 : 526 : void **loc;
146 : 526 : if (!hist && !VALUE_HISTOGRAMS (fun))
147 : : return;
148 : 526 : if (!VALUE_HISTOGRAMS (fun))
149 : 312 : VALUE_HISTOGRAMS (fun) = htab_create (1, histogram_hash,
150 : : histogram_eq, NULL);
151 : 597 : loc = htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun), stmt,
152 : : htab_hash_pointer (stmt),
153 : : hist ? INSERT : NO_INSERT);
154 : 526 : if (!hist)
155 : : {
156 : 71 : if (loc)
157 : 71 : htab_clear_slot (VALUE_HISTOGRAMS (fun), loc);
158 : 71 : return;
159 : : }
160 : 455 : *loc = hist;
161 : : }
162 : :
163 : : /* Get histogram list for STMT. */
164 : :
165 : : histogram_value
166 : 11401286816 : gimple_histogram_value (struct function *fun, gimple *stmt)
167 : : {
168 : 11401286816 : if (!VALUE_HISTOGRAMS (fun))
169 : : return NULL;
170 : 315320 : return (histogram_value) htab_find_with_hash (VALUE_HISTOGRAMS (fun), stmt,
171 : 315320 : htab_hash_pointer (stmt));
172 : : }
173 : :
174 : : /* Add histogram for STMT. */
175 : :
176 : : void
177 : 439 : gimple_add_histogram_value (struct function *fun, gimple *stmt,
178 : : histogram_value hist)
179 : : {
180 : 439 : hist->hvalue.next = gimple_histogram_value (fun, stmt);
181 : 439 : set_histogram_value (fun, stmt, hist);
182 : 439 : hist->fun = fun;
183 : 439 : }
184 : :
185 : : /* Remove histogram HIST from STMT's histogram list. */
186 : :
187 : : void
188 : 122 : gimple_remove_histogram_value (struct function *fun, gimple *stmt,
189 : : histogram_value hist)
190 : : {
191 : 122 : histogram_value hist2 = gimple_histogram_value (fun, stmt);
192 : 122 : if (hist == hist2)
193 : : {
194 : 87 : set_histogram_value (fun, stmt, hist->hvalue.next);
195 : : }
196 : : else
197 : : {
198 : 53 : while (hist2->hvalue.next != hist)
199 : : hist2 = hist2->hvalue.next;
200 : 35 : hist2->hvalue.next = hist->hvalue.next;
201 : : }
202 : 122 : free (hist->hvalue.counters);
203 : 122 : if (flag_checking)
204 : : memset (hist, 0xab, sizeof (*hist));
205 : 122 : free (hist);
206 : 122 : }
207 : :
208 : : /* Lookup histogram of type TYPE in the STMT. */
209 : :
210 : : histogram_value
211 : 261825 : gimple_histogram_value_of_type (struct function *fun, gimple *stmt,
212 : : enum hist_type type)
213 : : {
214 : 261825 : histogram_value hist;
215 : 261884 : for (hist = gimple_histogram_value (fun, stmt); hist;
216 : 59 : hist = hist->hvalue.next)
217 : 178 : 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 : 256 : dump_histogram_value (FILE *dump_file, histogram_value hist)
226 : : {
227 : 256 : 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 : 109 : case HIST_TYPE_TOPN_VALUES:
260 : 109 : case HIST_TYPE_INDIR_CALL:
261 : 109 : if (hist->hvalue.counters)
262 : : {
263 : 67 : fprintf (dump_file,
264 : : (hist->type == HIST_TYPE_TOPN_VALUES
265 : : ? "Top N value counter" : "Indirect call counter"));
266 : 47 : if (hist->hvalue.counters)
267 : : {
268 : 47 : unsigned count = hist->hvalue.counters[1];
269 : 47 : fprintf (dump_file, " all: %" PRId64 ", %" PRId64 " values: ",
270 : : (int64_t) hist->hvalue.counters[0], (int64_t) count);
271 : 115 : for (unsigned i = 0; i < count; i++)
272 : : {
273 : 68 : fprintf (dump_file, "[%" PRId64 ":%" PRId64 "]",
274 : 68 : (int64_t) hist->hvalue.counters[2 * i + 2],
275 : 68 : (int64_t) hist->hvalue.counters[2 * i + 3]);
276 : 68 : if (i != count - 1)
277 : 25 : fprintf (dump_file, ", ");
278 : : }
279 : 47 : fprintf (dump_file, ".\n");
280 : : }
281 : : }
282 : : break;
283 : :
284 : 59 : case HIST_TYPE_AVERAGE:
285 : 59 : if (hist->hvalue.counters)
286 : 31 : 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 : 59 : case HIST_TYPE_IOR:
293 : 59 : if (hist->hvalue.counters)
294 : 31 : 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 : 256 : }
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 : 1042874 : dump_histograms_for_stmt (struct function *fun, FILE *dump_file, gimple *stmt)
422 : : {
423 : 1042874 : histogram_value hist;
424 : 1042996 : for (hist = gimple_histogram_value (fun, stmt); hist; hist = hist->hvalue.next)
425 : 122 : dump_histogram_value (dump_file, hist);
426 : 1042874 : }
427 : :
428 : : /* Remove all histograms associated with STMT. */
429 : :
430 : : void
431 : 105786467 : gimple_remove_stmt_histograms (struct function *fun, gimple *stmt)
432 : : {
433 : 105786467 : histogram_value val;
434 : 105786486 : while ((val = gimple_histogram_value (fun, stmt)) != NULL)
435 : 19 : gimple_remove_histogram_value (fun, stmt, val);
436 : 105786467 : }
437 : :
438 : : /* Duplicate all histograms associates with OSTMT to STMT. */
439 : :
440 : : void
441 : 88250935 : gimple_duplicate_stmt_histograms (struct function *fun, gimple *stmt,
442 : : struct function *ofun, gimple *ostmt)
443 : : {
444 : 88250935 : histogram_value val;
445 : 88250943 : for (val = gimple_histogram_value (ofun, ostmt); val != NULL; val = val->hvalue.next)
446 : : {
447 : 8 : histogram_value new_val = gimple_alloc_histogram_value (fun, val->type);
448 : 8 : memcpy (new_val, val, sizeof (*val));
449 : 8 : new_val->hvalue.stmt = stmt;
450 : 8 : new_val->hvalue.counters = XNEWVAR (gcov_type, sizeof (*new_val->hvalue.counters) * new_val->n_counters);
451 : 8 : memcpy (new_val->hvalue.counters, val->hvalue.counters, sizeof (*new_val->hvalue.counters) * new_val->n_counters);
452 : 8 : gimple_add_histogram_value (fun, stmt, new_val);
453 : : }
454 : 88250935 : }
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 : 32658 : visit_hist (void **slot, void *data)
481 : : {
482 : 32658 : hash_set<histogram_value> *visited = (hash_set<histogram_value> *) data;
483 : 32658 : histogram_value hist = *(histogram_value *) slot;
484 : :
485 : 32658 : if (!visited->contains (hist)
486 : 32658 : && 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 : 32658 : return 1;
494 : : }
495 : :
496 : : /* Verify sanity of the histograms. */
497 : :
498 : : DEBUG_FUNCTION void
499 : 228023048 : verify_histograms (void)
500 : : {
501 : 228023048 : basic_block bb;
502 : 228023048 : gimple_stmt_iterator gsi;
503 : 228023048 : histogram_value hist;
504 : :
505 : 228023048 : error_found = false;
506 : 228023048 : hash_set<histogram_value> visited_hists;
507 : 2047972795 : FOR_EACH_BB_FN (bb, cfun)
508 : 14844193792 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
509 : : {
510 : 11204294298 : gimple *stmt = gsi_stmt (gsi);
511 : :
512 : 11204299340 : for (hist = gimple_histogram_value (cfun, stmt); hist;
513 : 5042 : hist = hist->hvalue.next)
514 : : {
515 : 5042 : 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 : 5042 : visited_hists.add (hist);
524 : : }
525 : : }
526 : 228023048 : if (VALUE_HISTOGRAMS (cfun))
527 : 30306 : htab_traverse (VALUE_HISTOGRAMS (cfun), visit_hist, &visited_hists);
528 : 228023048 : if (error_found)
529 : 0 : internal_error ("%qs failed", __func__);
530 : 228023048 : }
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 : 300 : free_hist (void **slot, void *data ATTRIBUTE_UNUSED)
537 : : {
538 : 300 : histogram_value hist = *(histogram_value *) slot;
539 : 300 : free (hist->hvalue.counters);
540 : 300 : free (hist);
541 : 300 : return 1;
542 : : }
543 : :
544 : : void
545 : 1416256 : free_histograms (struct function *fn)
546 : : {
547 : 1416256 : if (VALUE_HISTOGRAMS (fn))
548 : : {
549 : 297 : htab_traverse (VALUE_HISTOGRAMS (fn), free_hist, NULL);
550 : 297 : htab_delete (VALUE_HISTOGRAMS (fn));
551 : 297 : VALUE_HISTOGRAMS (fn) = NULL;
552 : : }
553 : 1416256 : }
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 : 41 : check_counter (gimple *stmt, const char * name,
562 : : gcov_type *count, gcov_type *all, profile_count bb_count_d)
563 : : {
564 : 41 : gcov_type bb_count = bb_count_d.ipa ().to_gcov_type ();
565 : 41 : 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 : 327 : gimple_value_profile_transformations (void)
604 : : {
605 : 327 : basic_block bb;
606 : 327 : gimple_stmt_iterator gsi;
607 : 327 : bool changed = false;
608 : :
609 : 1754 : FOR_EACH_BB_FN (bb, cfun)
610 : : {
611 : 5165 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
612 : : {
613 : 2311 : gimple *stmt = gsi_stmt (gsi);
614 : 2311 : histogram_value th = gimple_histogram_value (cfun, stmt);
615 : 2311 : if (!th)
616 : 2241 : continue;
617 : :
618 : 70 : if (dump_file)
619 : : {
620 : 31 : fprintf (dump_file, "Trying transformations on stmt ");
621 : 31 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
622 : 31 : 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 : 70 : if (gimple_mod_subtract_transform (&gsi)
633 : 66 : || gimple_divmod_fixed_value_transform (&gsi)
634 : 62 : || gimple_mod_pow2_value_transform (&gsi)
635 : 132 : || 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 : 70 : if (dump_enabled_p ())
649 : 31 : dump_ic_profile (&gsi);
650 : : }
651 : : }
652 : :
653 : 327 : 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 : 1328 : 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 : 1328 : unsigned counters = hist->hvalue.counters[1];
754 : 1328 : if (n >= counters)
755 : : return false;
756 : :
757 : 84 : *count = 0;
758 : 84 : *value = 0;
759 : :
760 : 84 : gcov_type read_all = abs_hwi (hist->hvalue.counters[0]);
761 : 84 : gcov_type covered = 0;
762 : 252 : for (unsigned i = 0; i < counters; ++i)
763 : 168 : covered += hist->hvalue.counters[2 * i + 3];
764 : :
765 : 84 : gcov_type v = hist->hvalue.counters[2 * n + 2];
766 : 84 : gcov_type c = hist->hvalue.counters[2 * n + 3];
767 : :
768 : 84 : 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 : 84 : 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 : 84 : if (stmt
787 : 105 : && check_counter (stmt, counter_type, &c, &read_all,
788 : 21 : gimple_bb (stmt)->count))
789 : : return false;
790 : :
791 : 84 : *all = read_all;
792 : :
793 : 84 : *value = v;
794 : 84 : *count = c;
795 : 84 : return true;
796 : : }
797 : :
798 : : /* Do transform 1) on INSN if applicable. */
799 : :
800 : : static bool
801 : 66 : gimple_divmod_fixed_value_transform (gimple_stmt_iterator *si)
802 : : {
803 : 66 : histogram_value histogram;
804 : 66 : enum tree_code code;
805 : 66 : gcov_type val, count, all;
806 : 66 : tree result, value, tree_val;
807 : 66 : profile_probability prob;
808 : 66 : gassign *stmt;
809 : :
810 : 68 : 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 : 0 : 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 : 62 : gimple_mod_pow2_value_transform (gimple_stmt_iterator *si)
953 : : {
954 : 62 : histogram_value histogram;
955 : 62 : enum tree_code code;
956 : 62 : gcov_type count, wrong_values, all;
957 : 62 : tree lhs_type, result, value;
958 : 62 : profile_probability prob;
959 : 62 : gassign *stmt;
960 : :
961 : 64 : 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 : 70 : gimple_mod_subtract_transform (gimple_stmt_iterator *si)
1118 : : {
1119 : 70 : histogram_value histogram;
1120 : 70 : enum tree_code code;
1121 : 70 : gcov_type count, wrong_values, all;
1122 : 70 : tree lhs_type, result;
1123 : 70 : profile_probability prob1, prob2;
1124 : 70 : unsigned int i, steps;
1125 : 70 : gcov_type count1, count2;
1126 : 70 : gassign *stmt;
1127 : 76 : 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 : 3379 : coverage_node_map_initialized_p (void)
1220 : : {
1221 : 3379 : 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 : 605 : init_node_map (bool local)
1230 : : {
1231 : 605 : struct cgraph_node *n;
1232 : 605 : cgraph_node_map = new hash_map<profile_id_hash, cgraph_node *>;
1233 : :
1234 : 3216 : FOR_EACH_DEFINED_FUNCTION (n)
1235 : 2611 : if (n->has_gimple_body_p () || n->thunk)
1236 : : {
1237 : 2412 : cgraph_node **val;
1238 : 2412 : dump_user_location_t loc
1239 : 2412 : = dump_user_location_t::from_function_decl (n->decl);
1240 : 2412 : if (local)
1241 : : {
1242 : 2246 : n->profile_id = coverage_compute_profile_id (n);
1243 : 2246 : while ((val = cgraph_node_map->get (n->profile_id))
1244 : 2246 : || !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 : 2366 : cgraph_node_map->put (n->profile_id, n);
1276 : : }
1277 : 605 : }
1278 : :
1279 : : /* Delete the CGRAPH_NODE_MAP. */
1280 : :
1281 : : void
1282 : 605 : del_node_map (void)
1283 : : {
1284 : 1210 : delete cgraph_node_map;
1285 : 605 : }
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 : 11816 : gimple_ic (gcall *icall_stmt, struct cgraph_node *direct_call,
1309 : : profile_probability prob)
1310 : : {
1311 : 11816 : gcall *dcall_stmt;
1312 : 11816 : gassign *load_stmt;
1313 : 11816 : gcond *cond_stmt;
1314 : 11816 : tree tmp0, tmp1, tmp;
1315 : 11816 : basic_block cond_bb, dcall_bb, icall_bb, join_bb = NULL;
1316 : 11816 : edge e_cd, e_ci, e_di, e_dj = NULL, e_ij;
1317 : 11816 : gimple_stmt_iterator gsi;
1318 : 11816 : int lp_nr, dflags;
1319 : 11816 : edge e_eh, e;
1320 : 11816 : edge_iterator ei;
1321 : :
1322 : 11816 : cond_bb = gimple_bb (icall_stmt);
1323 : 11816 : gsi = gsi_for_stmt (icall_stmt);
1324 : :
1325 : 11816 : tmp0 = make_temp_ssa_name (ptr_type_node, NULL, "PROF");
1326 : 11816 : tmp1 = make_temp_ssa_name (ptr_type_node, NULL, "PROF");
1327 : 11816 : tmp = unshare_expr (gimple_call_fn (icall_stmt));
1328 : 11816 : load_stmt = gimple_build_assign (tmp0, tmp);
1329 : 11816 : gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
1330 : :
1331 : 11816 : tmp = fold_convert (ptr_type_node, build_addr (direct_call->decl));
1332 : 11816 : load_stmt = gimple_build_assign (tmp1, tmp);
1333 : 11816 : gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
1334 : :
1335 : 11816 : cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
1336 : 11816 : gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1337 : :
1338 : 23632 : if (TREE_CODE (gimple_vdef (icall_stmt)) == SSA_NAME)
1339 : : {
1340 : 2151 : unlink_stmt_vdef (icall_stmt);
1341 : 4302 : release_ssa_name (gimple_vdef (icall_stmt));
1342 : : }
1343 : 11816 : gimple_set_vdef (icall_stmt, NULL_TREE);
1344 : 11816 : gimple_set_vuse (icall_stmt, NULL_TREE);
1345 : 11816 : update_stmt (icall_stmt);
1346 : 11816 : dcall_stmt = as_a <gcall *> (gimple_copy (icall_stmt));
1347 : 11816 : gimple_call_set_fndecl (dcall_stmt, direct_call->decl);
1348 : 11816 : dflags = flags_from_decl_or_type (direct_call->decl);
1349 : 11816 : if ((dflags & ECF_NORETURN) != 0
1350 : 11816 : && should_remove_lhs_p (gimple_call_lhs (dcall_stmt)))
1351 : 3 : gimple_call_set_lhs (dcall_stmt, NULL_TREE);
1352 : 11816 : 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 : 11816 : e_cd = split_block (cond_bb, cond_stmt);
1357 : 11816 : dcall_bb = e_cd->dest;
1358 : 11816 : dcall_bb->count = cond_bb->count.apply_probability (prob);
1359 : :
1360 : 11816 : e_di = split_block (dcall_bb, dcall_stmt);
1361 : 11816 : icall_bb = e_di->dest;
1362 : 11816 : icall_bb->count = cond_bb->count - dcall_bb->count;
1363 : :
1364 : : /* Do not disturb existing EH edges from the indirect call. */
1365 : 11816 : if (!stmt_ends_bb_p (icall_stmt))
1366 : 7884 : e_ij = split_block (icall_bb, icall_stmt);
1367 : : else
1368 : : {
1369 : 3932 : e_ij = find_fallthru_edge (icall_bb->succs);
1370 : : /* The indirect call might be noreturn. */
1371 : 3932 : if (e_ij != NULL)
1372 : : {
1373 : 3932 : e_ij->probability = profile_probability::always ();
1374 : 3932 : e_ij = single_pred_edge (split_edge (e_ij));
1375 : : }
1376 : : }
1377 : 11816 : if (e_ij != NULL)
1378 : : {
1379 : 11816 : join_bb = e_ij->dest;
1380 : 11816 : join_bb->count = cond_bb->count;
1381 : : }
1382 : :
1383 : 11816 : e_cd->flags = (e_cd->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE;
1384 : 11816 : e_cd->probability = prob;
1385 : :
1386 : 11816 : e_ci = make_edge (cond_bb, icall_bb, EDGE_FALSE_VALUE);
1387 : 11816 : e_ci->probability = prob.invert ();
1388 : :
1389 : 11816 : remove_edge (e_di);
1390 : :
1391 : 11816 : if (e_ij != NULL)
1392 : : {
1393 : 11816 : if ((dflags & ECF_NORETURN) == 0)
1394 : : {
1395 : 11813 : e_dj = make_edge (dcall_bb, join_bb, EDGE_FALLTHRU);
1396 : 11813 : e_dj->probability = profile_probability::always ();
1397 : : }
1398 : 11816 : e_ij->probability = profile_probability::always ();
1399 : : }
1400 : :
1401 : : /* Insert PHI node for the call result if necessary. */
1402 : 11816 : if (gimple_call_lhs (icall_stmt)
1403 : 8744 : && TREE_CODE (gimple_call_lhs (icall_stmt)) == SSA_NAME
1404 : 19826 : && (dflags & ECF_NORETURN) == 0)
1405 : : {
1406 : 8007 : tree result = gimple_call_lhs (icall_stmt);
1407 : 8007 : gphi *phi = create_phi_node (result, join_bb);
1408 : 8007 : gimple_call_set_lhs (icall_stmt,
1409 : : duplicate_ssa_name (result, icall_stmt));
1410 : 8007 : add_phi_arg (phi, gimple_call_lhs (icall_stmt), e_ij, UNKNOWN_LOCATION);
1411 : 8007 : gimple_call_set_lhs (dcall_stmt,
1412 : : duplicate_ssa_name (result, dcall_stmt));
1413 : 8007 : 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 : 11816 : lp_nr = lookup_stmt_eh_lp (icall_stmt);
1418 : 11816 : if (lp_nr > 0 && stmt_could_throw_p (cfun, dcall_stmt))
1419 : : {
1420 : 528 : add_stmt_to_eh_lp (dcall_stmt, lp_nr);
1421 : : }
1422 : :
1423 : 27564 : FOR_EACH_EDGE (e_eh, ei, icall_bb->succs)
1424 : 15748 : if (e_eh->flags & (EDGE_EH | EDGE_ABNORMAL))
1425 : : {
1426 : 3932 : e = make_edge (dcall_bb, e_eh->dest, e_eh->flags);
1427 : 3932 : e->probability = e_eh->probability;
1428 : 3932 : for (gphi_iterator psi = gsi_start_phis (e_eh->dest);
1429 : 7755 : !gsi_end_p (psi); gsi_next (&psi))
1430 : : {
1431 : 3823 : gphi *phi = psi.phi ();
1432 : 3823 : SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, e),
1433 : : PHI_ARG_DEF_FROM_EDGE (phi, e_eh));
1434 : : }
1435 : : }
1436 : 11816 : if (!stmt_could_throw_p (cfun, dcall_stmt))
1437 : 10150 : gimple_purge_dead_eh_edges (dcall_bb);
1438 : 11816 : return dcall_stmt;
1439 : : }
1440 : :
1441 : : /* Dump info about indirect call profile. */
1442 : :
1443 : : static void
1444 : 31 : dump_ic_profile (gimple_stmt_iterator *gsi)
1445 : : {
1446 : 31 : gcall *stmt;
1447 : 31 : histogram_value histogram;
1448 : 31 : gcov_type val, count, all;
1449 : 31 : struct cgraph_node *direct_call;
1450 : :
1451 : 31 : stmt = dyn_cast <gcall *> (gsi_stmt (*gsi));
1452 : 24 : if (!stmt)
1453 : 31 : return;
1454 : :
1455 : 24 : 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 : : 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 : 419 : interesting_stringop_to_profile_p (gcall *call, int *size_arg)
1500 : : {
1501 : 419 : enum built_in_function fcode;
1502 : :
1503 : 419 : fcode = DECL_FUNCTION_CODE (gimple_call_fndecl (call));
1504 : 419 : switch (fcode)
1505 : : {
1506 : 61 : case BUILT_IN_MEMCPY:
1507 : 61 : case BUILT_IN_MEMPCPY:
1508 : 61 : case BUILT_IN_MEMMOVE:
1509 : 61 : *size_arg = 2;
1510 : 61 : return validate_gimple_arglist (call, POINTER_TYPE, POINTER_TYPE,
1511 : 61 : 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 : 62 : gimple_stringops_transform (gimple_stmt_iterator *gsi)
1630 : : {
1631 : 62 : gcall *stmt;
1632 : 62 : tree blck_size;
1633 : 62 : enum built_in_function fcode;
1634 : 62 : histogram_value histogram;
1635 : 62 : gcov_type count, all, val;
1636 : 62 : tree dest, src;
1637 : 62 : unsigned int dest_align, src_align;
1638 : 62 : profile_probability prob;
1639 : 62 : tree tree_val;
1640 : 62 : int size_arg;
1641 : :
1642 : 111 : stmt = dyn_cast <gcall *> (gsi_stmt (*gsi));
1643 : 60 : if (!stmt)
1644 : : return false;
1645 : :
1646 : 60 : if (!gimple_call_builtin_p (gsi_stmt (*gsi), BUILT_IN_NORMAL))
1647 : : return false;
1648 : :
1649 : 20 : if (!interesting_stringop_to_profile_p (stmt, &size_arg))
1650 : : return false;
1651 : :
1652 : 20 : blck_size = gimple_call_arg (stmt, size_arg);
1653 : 20 : if (TREE_CODE (blck_size) == INTEGER_CST)
1654 : : return false;
1655 : :
1656 : 20 : histogram = gimple_histogram_value_of_type (cfun, stmt,
1657 : : HIST_TYPE_TOPN_VALUES);
1658 : 20 : if (!histogram)
1659 : : return false;
1660 : :
1661 : 20 : if (!get_nth_most_common_value (stmt, "stringops", histogram, &val, &count,
1662 : : &all))
1663 : : return false;
1664 : :
1665 : 17 : gimple_remove_histogram_value (cfun, stmt, histogram);
1666 : :
1667 : : /* We require that count is at least half of all. */
1668 : 17 : if (2 * count < all || optimize_bb_for_size_p (gimple_bb (stmt)))
1669 : 2 : return false;
1670 : 15 : if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count))
1671 : : return false;
1672 : 15 : if (all > 0)
1673 : 15 : prob = profile_probability::probability_in_gcov_type (count, all);
1674 : : else
1675 : 0 : prob = profile_probability::never ();
1676 : :
1677 : 15 : dest = gimple_call_arg (stmt, 0);
1678 : 15 : dest_align = get_pointer_alignment (dest);
1679 : 15 : fcode = DECL_FUNCTION_CODE (gimple_call_fndecl (stmt));
1680 : 15 : switch (fcode)
1681 : : {
1682 : 11 : case BUILT_IN_MEMCPY:
1683 : 11 : case BUILT_IN_MEMPCPY:
1684 : 11 : case BUILT_IN_MEMMOVE:
1685 : 11 : src = gimple_call_arg (stmt, 1);
1686 : 11 : src_align = get_pointer_alignment (src);
1687 : 11 : 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 : 130815 : stringop_block_profile (gimple *stmt, unsigned int *expected_align,
1730 : : HOST_WIDE_INT *expected_size)
1731 : : {
1732 : 130815 : histogram_value histogram;
1733 : 130815 : histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_AVERAGE);
1734 : :
1735 : 130815 : if (!histogram)
1736 : 130796 : *expected_size = -1;
1737 : 19 : 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 : 17 : gcov_type size;
1745 : 17 : size = ((histogram->hvalue.counters[0]
1746 : 17 : + 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 : 17 : if (size > INT_MAX)
1751 : : size = INT_MAX;
1752 : 17 : *expected_size = size;
1753 : 17 : gimple_remove_histogram_value (cfun, stmt, histogram);
1754 : : }
1755 : :
1756 : 130815 : histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_IOR);
1757 : :
1758 : 130815 : if (!histogram)
1759 : 130796 : *expected_align = 0;
1760 : 19 : 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 : 109 : while (!(count & alignment)
1773 : 109 : && (alignment <= UINT_MAX / 2 / BITS_PER_UNIT))
1774 : 92 : alignment <<= 1;
1775 : 17 : *expected_align = alignment * BITS_PER_UNIT;
1776 : 17 : gimple_remove_histogram_value (cfun, stmt, histogram);
1777 : : }
1778 : 130815 : }
1779 : :
1780 : :
1781 : : /* Find values inside STMT for that we want to measure histograms for
1782 : : division/modulo optimization. */
1783 : :
1784 : : static void
1785 : 6908 : gimple_divmod_values_to_profile (gimple *stmt, histogram_values *values)
1786 : : {
1787 : 6908 : tree lhs, divisor, op0, type;
1788 : 6908 : histogram_value hist;
1789 : :
1790 : 6908 : if (gimple_code (stmt) != GIMPLE_ASSIGN)
1791 : : return;
1792 : :
1793 : 3108 : lhs = gimple_assign_lhs (stmt);
1794 : 3108 : type = TREE_TYPE (lhs);
1795 : 3108 : if (!INTEGRAL_TYPE_P (type))
1796 : : return;
1797 : :
1798 : 2128 : 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 : 6908 : gimple_indirect_call_to_profile (gimple *stmt, histogram_values *values)
1842 : : {
1843 : 6908 : tree callee;
1844 : :
1845 : 6908 : if (gimple_code (stmt) != GIMPLE_CALL
1846 : 1308 : || gimple_call_internal_p (stmt)
1847 : 8173 : || gimple_call_fndecl (stmt) != NULL_TREE)
1848 : 6825 : return;
1849 : :
1850 : 83 : callee = gimple_call_fn (stmt);
1851 : 83 : histogram_value v = gimple_alloc_histogram_value (cfun, HIST_TYPE_INDIR_CALL,
1852 : 83 : stmt, callee);
1853 : 83 : values->safe_push (v);
1854 : :
1855 : 83 : return;
1856 : : }
1857 : :
1858 : : /* Find values inside STMT for that we want to measure histograms for
1859 : : string operations. */
1860 : :
1861 : : static void
1862 : 6908 : gimple_stringops_values_to_profile (gimple *gs, histogram_values *values)
1863 : : {
1864 : 6908 : gcall *stmt;
1865 : 6908 : tree blck_size;
1866 : 6908 : tree dest;
1867 : 6908 : int size_arg;
1868 : :
1869 : 6908 : stmt = dyn_cast <gcall *> (gs);
1870 : 1308 : if (!stmt)
1871 : 6849 : return;
1872 : :
1873 : 1308 : if (!gimple_call_builtin_p (gs, BUILT_IN_NORMAL))
1874 : : return;
1875 : :
1876 : 388 : if (!interesting_stringop_to_profile_p (stmt, &size_arg))
1877 : : return;
1878 : :
1879 : 59 : dest = gimple_call_arg (stmt, 0);
1880 : 59 : blck_size = gimple_call_arg (stmt, size_arg);
1881 : :
1882 : 59 : if (TREE_CODE (blck_size) != INTEGER_CST)
1883 : : {
1884 : 48 : values->safe_push (gimple_alloc_histogram_value (cfun,
1885 : : HIST_TYPE_TOPN_VALUES,
1886 : : stmt, blck_size));
1887 : 48 : values->safe_push (gimple_alloc_histogram_value (cfun, HIST_TYPE_AVERAGE,
1888 : : stmt, blck_size));
1889 : : }
1890 : :
1891 : 59 : if (TREE_CODE (blck_size) != INTEGER_CST)
1892 : 48 : 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 : 6908 : gimple_values_to_profile (gimple *stmt, histogram_values *values)
1901 : : {
1902 : 6908 : gimple_divmod_values_to_profile (stmt, values);
1903 : 6908 : gimple_stringops_values_to_profile (stmt, values);
1904 : 6908 : gimple_indirect_call_to_profile (stmt, values);
1905 : 6908 : }
1906 : :
1907 : : void
1908 : 927 : gimple_find_values_to_profile (histogram_values *values)
1909 : : {
1910 : 927 : basic_block bb;
1911 : 927 : gimple_stmt_iterator gsi;
1912 : 927 : unsigned i;
1913 : 927 : histogram_value hist = NULL;
1914 : 927 : values->create (0);
1915 : :
1916 : 4928 : FOR_EACH_BB_FN (bb, cfun)
1917 : 14910 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1918 : 6908 : gimple_values_to_profile (gsi_stmt (gsi), values);
1919 : :
1920 : 927 : values->safe_push (gimple_alloc_histogram_value (cfun,
1921 : : HIST_TYPE_TIME_PROFILE));
1922 : :
1923 : 2160 : FOR_EACH_VEC_ELT (*values, i, hist)
1924 : : {
1925 : 1233 : 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 : 172 : case HIST_TYPE_TOPN_VALUES:
1936 : 172 : case HIST_TYPE_INDIR_CALL:
1937 : 172 : hist->n_counters = GCOV_TOPN_MEM_COUNTERS;
1938 : 172 : break;
1939 : :
1940 : 927 : case HIST_TYPE_TIME_PROFILE:
1941 : 927 : hist->n_counters = 1;
1942 : 927 : break;
1943 : :
1944 : 48 : case HIST_TYPE_AVERAGE:
1945 : 48 : hist->n_counters = 2;
1946 : 48 : break;
1947 : :
1948 : 48 : case HIST_TYPE_IOR:
1949 : 48 : hist->n_counters = 1;
1950 : 48 : break;
1951 : :
1952 : 0 : default:
1953 : 0 : gcc_unreachable ();
1954 : : }
1955 : 1233 : if (dump_file && hist->hvalue.stmt != NULL)
1956 : : {
1957 : 134 : fprintf (dump_file, "Stmt ");
1958 : 134 : print_gimple_stmt (dump_file, hist->hvalue.stmt, 0, TDF_SLIM);
1959 : 134 : dump_histogram_value (dump_file, hist);
1960 : : }
1961 : : }
1962 : 927 : }
|
