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