|
0
|
1 /* Transformations based on profile information for values.
|
|
|
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Free Software
|
|
|
3 Foundation, Inc.
|
|
|
4
|
|
|
5 This file is part of GCC.
|
|
|
6
|
|
|
7 GCC is free software; you can redistribute it and/or modify it under
|
|
|
8 the terms of the GNU General Public License as published by the Free
|
|
|
9 Software Foundation; either version 3, or (at your option) any later
|
|
|
10 version.
|
|
|
11
|
|
|
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
|
|
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
15 for more details.
|
|
|
16
|
|
|
17 You should have received a copy of the GNU General Public License
|
|
|
18 along with GCC; see the file COPYING3. If not see
|
|
|
19 <http://www.gnu.org/licenses/>. */
|
|
|
20
|
|
|
21 #include "config.h"
|
|
|
22 #include "system.h"
|
|
|
23 #include "coretypes.h"
|
|
|
24 #include "tm.h"
|
|
|
25 #include "rtl.h"
|
|
|
26 #include "expr.h"
|
|
|
27 #include "hard-reg-set.h"
|
|
|
28 #include "basic-block.h"
|
|
|
29 #include "value-prof.h"
|
|
|
30 #include "output.h"
|
|
|
31 #include "flags.h"
|
|
|
32 #include "insn-config.h"
|
|
|
33 #include "recog.h"
|
|
|
34 #include "optabs.h"
|
|
|
35 #include "regs.h"
|
|
|
36 #include "ggc.h"
|
|
|
37 #include "tree-flow.h"
|
|
|
38 #include "tree-flow-inline.h"
|
|
|
39 #include "diagnostic.h"
|
|
|
40 #include "coverage.h"
|
|
|
41 #include "tree.h"
|
|
|
42 #include "gcov-io.h"
|
|
|
43 #include "cgraph.h"
|
|
|
44 #include "timevar.h"
|
|
|
45 #include "tree-pass.h"
|
|
|
46 #include "toplev.h"
|
|
|
47 #include "pointer-set.h"
|
|
|
48
|
|
|
49 static struct value_prof_hooks *value_prof_hooks;
|
|
|
50
|
|
|
51 /* In this file value profile based optimizations are placed. Currently the
|
|
|
52 following optimizations are implemented (for more detailed descriptions
|
|
|
53 see comments at value_profile_transformations):
|
|
|
54
|
|
|
55 1) Division/modulo specialization. Provided that we can determine that the
|
|
|
56 operands of the division have some special properties, we may use it to
|
|
|
57 produce more effective code.
|
|
|
58 2) Speculative prefetching. If we are able to determine that the difference
|
|
|
59 between addresses accessed by a memory reference is usually constant, we
|
|
|
60 may add the prefetch instructions.
|
|
|
61 FIXME: This transformation was removed together with RTL based value
|
|
|
62 profiling.
|
|
|
63
|
|
|
64 3) Indirect/virtual call specialization. If we can determine most
|
|
|
65 common function callee in indirect/virtual call. We can use this
|
|
|
66 information to improve code effectiveness (especially info for
|
|
|
67 inliner).
|
|
|
68
|
|
|
69 Every such optimization should add its requirements for profiled values to
|
|
|
70 insn_values_to_profile function. This function is called from branch_prob
|
|
|
71 in profile.c and the requested values are instrumented by it in the first
|
|
|
72 compilation with -fprofile-arcs. The optimization may then read the
|
|
|
73 gathered data in the second compilation with -fbranch-probabilities.
|
|
|
74
|
|
|
75 The measured data is pointed to from the histograms
|
|
|
76 field of the statement annotation of the instrumented insns. It is
|
|
|
77 kept as a linked list of struct histogram_value_t's, which contain the
|
|
|
78 same information as above. */
|
|
|
79
|
|
|
80
|
|
|
81 static tree gimple_divmod_fixed_value (gimple, tree, int, gcov_type, gcov_type);
|
|
|
82 static tree gimple_mod_pow2 (gimple, int, gcov_type, gcov_type);
|
|
|
83 static tree gimple_mod_subtract (gimple, int, int, int, gcov_type, gcov_type,
|
|
|
84 gcov_type);
|
|
|
85 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator *);
|
|
|
86 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator *);
|
|
|
87 static bool gimple_mod_subtract_transform (gimple_stmt_iterator *);
|
|
|
88 static bool gimple_stringops_transform (gimple_stmt_iterator *);
|
|
|
89 static bool gimple_ic_transform (gimple);
|
|
|
90
|
|
|
91 /* Allocate histogram value. */
|
|
|
92
|
|
|
93 static histogram_value
|
|
|
94 gimple_alloc_histogram_value (struct function *fun ATTRIBUTE_UNUSED,
|
|
|
95 enum hist_type type, gimple stmt, tree value)
|
|
|
96 {
|
|
|
97 histogram_value hist = (histogram_value) xcalloc (1, sizeof (*hist));
|
|
|
98 hist->hvalue.value = value;
|
|
|
99 hist->hvalue.stmt = stmt;
|
|
|
100 hist->type = type;
|
|
|
101 return hist;
|
|
|
102 }
|
|
|
103
|
|
|
104 /* Hash value for histogram. */
|
|
|
105
|
|
|
106 static hashval_t
|
|
|
107 histogram_hash (const void *x)
|
|
|
108 {
|
|
|
109 return htab_hash_pointer (((const_histogram_value)x)->hvalue.stmt);
|
|
|
110 }
|
|
|
111
|
|
|
112 /* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y. */
|
|
|
113
|
|
|
114 static int
|
|
|
115 histogram_eq (const void *x, const void *y)
|
|
|
116 {
|
|
|
117 return ((const_histogram_value) x)->hvalue.stmt == (const_gimple) y;
|
|
|
118 }
|
|
|
119
|
|
|
120 /* Set histogram for STMT. */
|
|
|
121
|
|
|
122 static void
|
|
|
123 set_histogram_value (struct function *fun, gimple stmt, histogram_value hist)
|
|
|
124 {
|
|
|
125 void **loc;
|
|
|
126 if (!hist && !VALUE_HISTOGRAMS (fun))
|
|
|
127 return;
|
|
|
128 if (!VALUE_HISTOGRAMS (fun))
|
|
|
129 VALUE_HISTOGRAMS (fun) = htab_create (1, histogram_hash,
|
|
|
130 histogram_eq, NULL);
|
|
|
131 loc = htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun), stmt,
|
|
|
132 htab_hash_pointer (stmt),
|
|
|
133 hist ? INSERT : NO_INSERT);
|
|
|
134 if (!hist)
|
|
|
135 {
|
|
|
136 if (loc)
|
|
|
137 htab_clear_slot (VALUE_HISTOGRAMS (fun), loc);
|
|
|
138 return;
|
|
|
139 }
|
|
|
140 *loc = hist;
|
|
|
141 }
|
|
|
142
|
|
|
143 /* Get histogram list for STMT. */
|
|
|
144
|
|
|
145 histogram_value
|
|
|
146 gimple_histogram_value (struct function *fun, gimple stmt)
|
|
|
147 {
|
|
|
148 if (!VALUE_HISTOGRAMS (fun))
|
|
|
149 return NULL;
|
|
|
150 return (histogram_value) htab_find_with_hash (VALUE_HISTOGRAMS (fun), stmt,
|
|
|
151 htab_hash_pointer (stmt));
|
|
|
152 }
|
|
|
153
|
|
|
154 /* Add histogram for STMT. */
|
|
|
155
|
|
|
156 void
|
|
|
157 gimple_add_histogram_value (struct function *fun, gimple stmt,
|
|
|
158 histogram_value hist)
|
|
|
159 {
|
|
|
160 hist->hvalue.next = gimple_histogram_value (fun, stmt);
|
|
|
161 set_histogram_value (fun, stmt, hist);
|
|
|
162 }
|
|
|
163
|
|
|
164
|
|
|
165 /* Remove histogram HIST from STMT's histogram list. */
|
|
|
166
|
|
|
167 void
|
|
|
168 gimple_remove_histogram_value (struct function *fun, gimple stmt,
|
|
|
169 histogram_value hist)
|
|
|
170 {
|
|
|
171 histogram_value hist2 = gimple_histogram_value (fun, stmt);
|
|
|
172 if (hist == hist2)
|
|
|
173 {
|
|
|
174 set_histogram_value (fun, stmt, hist->hvalue.next);
|
|
|
175 }
|
|
|
176 else
|
|
|
177 {
|
|
|
178 while (hist2->hvalue.next != hist)
|
|
|
179 hist2 = hist2->hvalue.next;
|
|
|
180 hist2->hvalue.next = hist->hvalue.next;
|
|
|
181 }
|
|
|
182 free (hist->hvalue.counters);
|
|
|
183 #ifdef ENABLE_CHECKING
|
|
|
184 memset (hist, 0xab, sizeof (*hist));
|
|
|
185 #endif
|
|
|
186 free (hist);
|
|
|
187 }
|
|
|
188
|
|
|
189
|
|
|
190 /* Lookup histogram of type TYPE in the STMT. */
|
|
|
191
|
|
|
192 histogram_value
|
|
|
193 gimple_histogram_value_of_type (struct function *fun, gimple stmt,
|
|
|
194 enum hist_type type)
|
|
|
195 {
|
|
|
196 histogram_value hist;
|
|
|
197 for (hist = gimple_histogram_value (fun, stmt); hist;
|
|
|
198 hist = hist->hvalue.next)
|
|
|
199 if (hist->type == type)
|
|
|
200 return hist;
|
|
|
201 return NULL;
|
|
|
202 }
|
|
|
203
|
|
|
204 /* Dump information about HIST to DUMP_FILE. */
|
|
|
205
|
|
|
206 static void
|
|
|
207 dump_histogram_value (FILE *dump_file, histogram_value hist)
|
|
|
208 {
|
|
|
209 switch (hist->type)
|
|
|
210 {
|
|
|
211 case HIST_TYPE_INTERVAL:
|
|
|
212 fprintf (dump_file, "Interval counter range %d -- %d",
|
|
|
213 hist->hdata.intvl.int_start,
|
|
|
214 (hist->hdata.intvl.int_start
|
|
|
215 + hist->hdata.intvl.steps - 1));
|
|
|
216 if (hist->hvalue.counters)
|
|
|
217 {
|
|
|
218 unsigned int i;
|
|
|
219 fprintf(dump_file, " [");
|
|
|
220 for (i = 0; i < hist->hdata.intvl.steps; i++)
|
|
|
221 fprintf (dump_file, " %d:"HOST_WIDEST_INT_PRINT_DEC,
|
|
|
222 hist->hdata.intvl.int_start + i,
|
|
|
223 (HOST_WIDEST_INT) hist->hvalue.counters[i]);
|
|
|
224 fprintf (dump_file, " ] outside range:"HOST_WIDEST_INT_PRINT_DEC,
|
|
|
225 (HOST_WIDEST_INT) hist->hvalue.counters[i]);
|
|
|
226 }
|
|
|
227 fprintf (dump_file, ".\n");
|
|
|
228 break;
|
|
|
229
|
|
|
230 case HIST_TYPE_POW2:
|
|
|
231 fprintf (dump_file, "Pow2 counter ");
|
|
|
232 if (hist->hvalue.counters)
|
|
|
233 {
|
|
|
234 fprintf (dump_file, "pow2:"HOST_WIDEST_INT_PRINT_DEC
|
|
|
235 " nonpow2:"HOST_WIDEST_INT_PRINT_DEC,
|
|
|
236 (HOST_WIDEST_INT) hist->hvalue.counters[0],
|
|
|
237 (HOST_WIDEST_INT) hist->hvalue.counters[1]);
|
|
|
238 }
|
|
|
239 fprintf (dump_file, ".\n");
|
|
|
240 break;
|
|
|
241
|
|
|
242 case HIST_TYPE_SINGLE_VALUE:
|
|
|
243 fprintf (dump_file, "Single value ");
|
|
|
244 if (hist->hvalue.counters)
|
|
|
245 {
|
|
|
246 fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC
|
|
|
247 " match:"HOST_WIDEST_INT_PRINT_DEC
|
|
|
248 " wrong:"HOST_WIDEST_INT_PRINT_DEC,
|
|
|
249 (HOST_WIDEST_INT) hist->hvalue.counters[0],
|
|
|
250 (HOST_WIDEST_INT) hist->hvalue.counters[1],
|
|
|
251 (HOST_WIDEST_INT) hist->hvalue.counters[2]);
|
|
|
252 }
|
|
|
253 fprintf (dump_file, ".\n");
|
|
|
254 break;
|
|
|
255
|
|
|
256 case HIST_TYPE_AVERAGE:
|
|
|
257 fprintf (dump_file, "Average value ");
|
|
|
258 if (hist->hvalue.counters)
|
|
|
259 {
|
|
|
260 fprintf (dump_file, "sum:"HOST_WIDEST_INT_PRINT_DEC
|
|
|
261 " times:"HOST_WIDEST_INT_PRINT_DEC,
|
|
|
262 (HOST_WIDEST_INT) hist->hvalue.counters[0],
|
|
|
263 (HOST_WIDEST_INT) hist->hvalue.counters[1]);
|
|
|
264 }
|
|
|
265 fprintf (dump_file, ".\n");
|
|
|
266 break;
|
|
|
267
|
|
|
268 case HIST_TYPE_IOR:
|
|
|
269 fprintf (dump_file, "IOR value ");
|
|
|
270 if (hist->hvalue.counters)
|
|
|
271 {
|
|
|
272 fprintf (dump_file, "ior:"HOST_WIDEST_INT_PRINT_DEC,
|
|
|
273 (HOST_WIDEST_INT) hist->hvalue.counters[0]);
|
|
|
274 }
|
|
|
275 fprintf (dump_file, ".\n");
|
|
|
276 break;
|
|
|
277
|
|
|
278 case HIST_TYPE_CONST_DELTA:
|
|
|
279 fprintf (dump_file, "Constant delta ");
|
|
|
280 if (hist->hvalue.counters)
|
|
|
281 {
|
|
|
282 fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC
|
|
|
283 " match:"HOST_WIDEST_INT_PRINT_DEC
|
|
|
284 " wrong:"HOST_WIDEST_INT_PRINT_DEC,
|
|
|
285 (HOST_WIDEST_INT) hist->hvalue.counters[0],
|
|
|
286 (HOST_WIDEST_INT) hist->hvalue.counters[1],
|
|
|
287 (HOST_WIDEST_INT) hist->hvalue.counters[2]);
|
|
|
288 }
|
|
|
289 fprintf (dump_file, ".\n");
|
|
|
290 break;
|
|
|
291 case HIST_TYPE_INDIR_CALL:
|
|
|
292 fprintf (dump_file, "Indirect call ");
|
|
|
293 if (hist->hvalue.counters)
|
|
|
294 {
|
|
|
295 fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC
|
|
|
296 " match:"HOST_WIDEST_INT_PRINT_DEC
|
|
|
297 " all:"HOST_WIDEST_INT_PRINT_DEC,
|
|
|
298 (HOST_WIDEST_INT) hist->hvalue.counters[0],
|
|
|
299 (HOST_WIDEST_INT) hist->hvalue.counters[1],
|
|
|
300 (HOST_WIDEST_INT) hist->hvalue.counters[2]);
|
|
|
301 }
|
|
|
302 fprintf (dump_file, ".\n");
|
|
|
303 break;
|
|
|
304 }
|
|
|
305 }
|
|
|
306
|
|
|
307 /* Dump all histograms attached to STMT to DUMP_FILE. */
|
|
|
308
|
|
|
309 void
|
|
|
310 dump_histograms_for_stmt (struct function *fun, FILE *dump_file, gimple stmt)
|
|
|
311 {
|
|
|
312 histogram_value hist;
|
|
|
313 for (hist = gimple_histogram_value (fun, stmt); hist; hist = hist->hvalue.next)
|
|
|
314 dump_histogram_value (dump_file, hist);
|
|
|
315 }
|
|
|
316
|
|
|
317 /* Remove all histograms associated with STMT. */
|
|
|
318
|
|
|
319 void
|
|
|
320 gimple_remove_stmt_histograms (struct function *fun, gimple stmt)
|
|
|
321 {
|
|
|
322 histogram_value val;
|
|
|
323 while ((val = gimple_histogram_value (fun, stmt)) != NULL)
|
|
|
324 gimple_remove_histogram_value (fun, stmt, val);
|
|
|
325 }
|
|
|
326
|
|
|
327 /* Duplicate all histograms associates with OSTMT to STMT. */
|
|
|
328
|
|
|
329 void
|
|
|
330 gimple_duplicate_stmt_histograms (struct function *fun, gimple stmt,
|
|
|
331 struct function *ofun, gimple ostmt)
|
|
|
332 {
|
|
|
333 histogram_value val;
|
|
|
334 for (val = gimple_histogram_value (ofun, ostmt); val != NULL; val = val->hvalue.next)
|
|
|
335 {
|
|
|
336 histogram_value new_val = gimple_alloc_histogram_value (fun, val->type, NULL, NULL);
|
|
|
337 memcpy (new_val, val, sizeof (*val));
|
|
|
338 new_val->hvalue.stmt = stmt;
|
|
|
339 new_val->hvalue.counters = XNEWVAR (gcov_type, sizeof (*new_val->hvalue.counters) * new_val->n_counters);
|
|
|
340 memcpy (new_val->hvalue.counters, val->hvalue.counters, sizeof (*new_val->hvalue.counters) * new_val->n_counters);
|
|
|
341 gimple_add_histogram_value (fun, stmt, new_val);
|
|
|
342 }
|
|
|
343 }
|
|
|
344
|
|
|
345
|
|
|
346 /* Move all histograms associated with OSTMT to STMT. */
|
|
|
347
|
|
|
348 void
|
|
|
349 gimple_move_stmt_histograms (struct function *fun, gimple stmt, gimple ostmt)
|
|
|
350 {
|
|
|
351 histogram_value val = gimple_histogram_value (fun, ostmt);
|
|
|
352 if (val)
|
|
|
353 {
|
|
|
354 /* The following three statements can't be reordered,
|
|
|
355 because histogram hashtab relies on stmt field value
|
|
|
356 for finding the exact slot. */
|
|
|
357 set_histogram_value (fun, ostmt, NULL);
|
|
|
358 for (; val != NULL; val = val->hvalue.next)
|
|
|
359 val->hvalue.stmt = stmt;
|
|
|
360 set_histogram_value (fun, stmt, val);
|
|
|
361 }
|
|
|
362 }
|
|
|
363
|
|
|
364 static bool error_found = false;
|
|
|
365
|
|
|
366 /* Helper function for verify_histograms. For each histogram reachable via htab
|
|
|
367 walk verify that it was reached via statement walk. */
|
|
|
368
|
|
|
369 static int
|
|
|
370 visit_hist (void **slot, void *data)
|
|
|
371 {
|
|
|
372 struct pointer_set_t *visited = (struct pointer_set_t *) data;
|
|
|
373 histogram_value hist = *(histogram_value *) slot;
|
|
|
374 if (!pointer_set_contains (visited, hist))
|
|
|
375 {
|
|
|
376 error ("Dead histogram");
|
|
|
377 dump_histogram_value (stderr, hist);
|
|
|
378 debug_gimple_stmt (hist->hvalue.stmt);
|
|
|
379 error_found = true;
|
|
|
380 }
|
|
|
381 return 1;
|
|
|
382 }
|
|
|
383
|
|
|
384
|
|
|
385 /* Verify sanity of the histograms. */
|
|
|
386
|
|
|
387 void
|
|
|
388 verify_histograms (void)
|
|
|
389 {
|
|
|
390 basic_block bb;
|
|
|
391 gimple_stmt_iterator gsi;
|
|
|
392 histogram_value hist;
|
|
|
393 struct pointer_set_t *visited_hists;
|
|
|
394
|
|
|
395 error_found = false;
|
|
|
396 visited_hists = pointer_set_create ();
|
|
|
397 FOR_EACH_BB (bb)
|
|
|
398 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
399 {
|
|
|
400 gimple stmt = gsi_stmt (gsi);
|
|
|
401
|
|
|
402 for (hist = gimple_histogram_value (cfun, stmt); hist;
|
|
|
403 hist = hist->hvalue.next)
|
|
|
404 {
|
|
|
405 if (hist->hvalue.stmt != stmt)
|
|
|
406 {
|
|
|
407 error ("Histogram value statement does not correspond to "
|
|
|
408 "the statement it is associated with");
|
|
|
409 debug_gimple_stmt (stmt);
|
|
|
410 dump_histogram_value (stderr, hist);
|
|
|
411 error_found = true;
|
|
|
412 }
|
|
|
413 pointer_set_insert (visited_hists, hist);
|
|
|
414 }
|
|
|
415 }
|
|
|
416 if (VALUE_HISTOGRAMS (cfun))
|
|
|
417 htab_traverse (VALUE_HISTOGRAMS (cfun), visit_hist, visited_hists);
|
|
|
418 pointer_set_destroy (visited_hists);
|
|
|
419 if (error_found)
|
|
|
420 internal_error ("verify_histograms failed");
|
|
|
421 }
|
|
|
422
|
|
|
423 /* Helper function for verify_histograms. For each histogram reachable via htab
|
|
|
424 walk verify that it was reached via statement walk. */
|
|
|
425
|
|
|
426 static int
|
|
|
427 free_hist (void **slot, void *data ATTRIBUTE_UNUSED)
|
|
|
428 {
|
|
|
429 histogram_value hist = *(histogram_value *) slot;
|
|
|
430 free (hist->hvalue.counters);
|
|
|
431 #ifdef ENABLE_CHECKING
|
|
|
432 memset (hist, 0xab, sizeof (*hist));
|
|
|
433 #endif
|
|
|
434 free (hist);
|
|
|
435 return 1;
|
|
|
436 }
|
|
|
437
|
|
|
438 void
|
|
|
439 free_histograms (void)
|
|
|
440 {
|
|
|
441 if (VALUE_HISTOGRAMS (cfun))
|
|
|
442 {
|
|
|
443 htab_traverse (VALUE_HISTOGRAMS (cfun), free_hist, NULL);
|
|
|
444 htab_delete (VALUE_HISTOGRAMS (cfun));
|
|
|
445 VALUE_HISTOGRAMS (cfun) = NULL;
|
|
|
446 }
|
|
|
447 }
|
|
|
448
|
|
|
449
|
|
|
450 /* The overall number of invocations of the counter should match
|
|
|
451 execution count of basic block. Report it as error rather than
|
|
|
452 internal error as it might mean that user has misused the profile
|
|
|
453 somehow. */
|
|
|
454
|
|
|
455 static bool
|
|
|
456 check_counter (gimple stmt, const char * name,
|
|
|
457 gcov_type *count, gcov_type *all, gcov_type bb_count)
|
|
|
458 {
|
|
|
459 if (*all != bb_count || *count > *all)
|
|
|
460 {
|
|
|
461 location_t locus;
|
|
|
462 locus = (stmt != NULL)
|
|
|
463 ? gimple_location (stmt)
|
|
|
464 : DECL_SOURCE_LOCATION (current_function_decl);
|
|
|
465 if (flag_profile_correction)
|
|
|
466 {
|
|
|
467 inform (locus, "Correcting inconsistent value profile: "
|
|
|
468 "%s profiler overall count (%d) does not match BB count "
|
|
|
469 "(%d)", name, (int)*all, (int)bb_count);
|
|
|
470 *all = bb_count;
|
|
|
471 if (*count > *all)
|
|
|
472 *count = *all;
|
|
|
473 return false;
|
|
|
474 }
|
|
|
475 else
|
|
|
476 {
|
|
|
477 error ("%HCorrupted value profile: %s profiler overall count (%d) "
|
|
|
478 "does not match BB count (%d)", &locus, name, (int)*all,
|
|
|
479 (int)bb_count);
|
|
|
480 return true;
|
|
|
481 }
|
|
|
482 }
|
|
|
483
|
|
|
484 return false;
|
|
|
485 }
|
|
|
486
|
|
|
487
|
|
|
488 /* GIMPLE based transformations. */
|
|
|
489
|
|
|
490 static bool
|
|
|
491 gimple_value_profile_transformations (void)
|
|
|
492 {
|
|
|
493 basic_block bb;
|
|
|
494 gimple_stmt_iterator gsi;
|
|
|
495 bool changed = false;
|
|
|
496
|
|
|
497 FOR_EACH_BB (bb)
|
|
|
498 {
|
|
|
499 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
500 {
|
|
|
501 gimple stmt = gsi_stmt (gsi);
|
|
|
502 histogram_value th = gimple_histogram_value (cfun, stmt);
|
|
|
503 if (!th)
|
|
|
504 continue;
|
|
|
505
|
|
|
506 if (dump_file)
|
|
|
507 {
|
|
|
508 fprintf (dump_file, "Trying transformations on stmt ");
|
|
|
509 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
|
|
510 dump_histograms_for_stmt (cfun, dump_file, stmt);
|
|
|
511 }
|
|
|
512
|
|
|
513 /* Transformations: */
|
|
|
514 /* The order of things in this conditional controls which
|
|
|
515 transformation is used when more than one is applicable. */
|
|
|
516 /* It is expected that any code added by the transformations
|
|
|
517 will be added before the current statement, and that the
|
|
|
518 current statement remain valid (although possibly
|
|
|
519 modified) upon return. */
|
|
|
520 if (flag_value_profile_transformations
|
|
|
521 && (gimple_mod_subtract_transform (&gsi)
|
|
|
522 || gimple_divmod_fixed_value_transform (&gsi)
|
|
|
523 || gimple_mod_pow2_value_transform (&gsi)
|
|
|
524 || gimple_stringops_transform (&gsi)
|
|
|
525 || gimple_ic_transform (stmt)))
|
|
|
526 {
|
|
|
527 stmt = gsi_stmt (gsi);
|
|
|
528 changed = true;
|
|
|
529 /* Original statement may no longer be in the same block. */
|
|
|
530 if (bb != gimple_bb (stmt))
|
|
|
531 {
|
|
|
532 bb = gimple_bb (stmt);
|
|
|
533 gsi = gsi_for_stmt (stmt);
|
|
|
534 }
|
|
|
535 }
|
|
|
536 }
|
|
|
537 }
|
|
|
538
|
|
|
539 if (changed)
|
|
|
540 {
|
|
|
541 counts_to_freqs ();
|
|
|
542 }
|
|
|
543
|
|
|
544 return changed;
|
|
|
545 }
|
|
|
546
|
|
|
547
|
|
|
548 /* Generate code for transformation 1 (with parent gimple assignment
|
|
|
549 STMT and probability of taking the optimal path PROB, which is
|
|
|
550 equivalent to COUNT/ALL within roundoff error). This generates the
|
|
|
551 result into a temp and returns the temp; it does not replace or
|
|
|
552 alter the original STMT. */
|
|
|
553
|
|
|
554 static tree
|
|
|
555 gimple_divmod_fixed_value (gimple stmt, tree value, int prob, gcov_type count,
|
|
|
556 gcov_type all)
|
|
|
557 {
|
|
|
558 gimple stmt1, stmt2, stmt3;
|
|
|
559 tree tmp1, tmp2, tmpv;
|
|
|
560 gimple bb1end, bb2end, bb3end;
|
|
|
561 basic_block bb, bb2, bb3, bb4;
|
|
|
562 tree optype, op1, op2;
|
|
|
563 edge e12, e13, e23, e24, e34;
|
|
|
564 gimple_stmt_iterator gsi;
|
|
|
565
|
|
|
566 gcc_assert (is_gimple_assign (stmt)
|
|
|
567 && (gimple_assign_rhs_code (stmt) == TRUNC_DIV_EXPR
|
|
|
568 || gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR));
|
|
|
569
|
|
|
570 optype = TREE_TYPE (gimple_assign_lhs (stmt));
|
|
|
571 op1 = gimple_assign_rhs1 (stmt);
|
|
|
572 op2 = gimple_assign_rhs2 (stmt);
|
|
|
573
|
|
|
574 bb = gimple_bb (stmt);
|
|
|
575 gsi = gsi_for_stmt (stmt);
|
|
|
576
|
|
|
577 tmpv = create_tmp_var (optype, "PROF");
|
|
|
578 tmp1 = create_tmp_var (optype, "PROF");
|
|
|
579 stmt1 = gimple_build_assign (tmpv, fold_convert (optype, value));
|
|
|
580 stmt2 = gimple_build_assign (tmp1, op2);
|
|
|
581 stmt3 = gimple_build_cond (NE_EXPR, tmp1, tmpv, NULL_TREE, NULL_TREE);
|
|
|
582 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
|
|
|
583 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
|
|
|
584 gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
|
|
|
585 bb1end = stmt3;
|
|
|
586
|
|
|
587 tmp2 = create_tmp_var (optype, "PROF");
|
|
|
588 stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), tmp2,
|
|
|
589 op1, tmpv);
|
|
|
590 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
|
|
|
591 bb2end = stmt1;
|
|
|
592
|
|
|
593 stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), tmp2,
|
|
|
594 op1, op2);
|
|
|
595 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
|
|
|
596 bb3end = stmt1;
|
|
|
597
|
|
|
598 /* Fix CFG. */
|
|
|
599 /* Edge e23 connects bb2 to bb3, etc. */
|
|
|
600 e12 = split_block (bb, bb1end);
|
|
|
601 bb2 = e12->dest;
|
|
|
602 bb2->count = count;
|
|
|
603 e23 = split_block (bb2, bb2end);
|
|
|
604 bb3 = e23->dest;
|
|
|
605 bb3->count = all - count;
|
|
|
606 e34 = split_block (bb3, bb3end);
|
|
|
607 bb4 = e34->dest;
|
|
|
608 bb4->count = all;
|
|
|
609
|
|
|
610 e12->flags &= ~EDGE_FALLTHRU;
|
|
|
611 e12->flags |= EDGE_FALSE_VALUE;
|
|
|
612 e12->probability = prob;
|
|
|
613 e12->count = count;
|
|
|
614
|
|
|
615 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
|
|
|
616 e13->probability = REG_BR_PROB_BASE - prob;
|
|
|
617 e13->count = all - count;
|
|
|
618
|
|
|
619 remove_edge (e23);
|
|
|
620
|
|
|
621 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
|
|
|
622 e24->probability = REG_BR_PROB_BASE;
|
|
|
623 e24->count = count;
|
|
|
624
|
|
|
625 e34->probability = REG_BR_PROB_BASE;
|
|
|
626 e34->count = all - count;
|
|
|
627
|
|
|
628 return tmp2;
|
|
|
629 }
|
|
|
630
|
|
|
631
|
|
|
632 /* Do transform 1) on INSN if applicable. */
|
|
|
633
|
|
|
634 static bool
|
|
|
635 gimple_divmod_fixed_value_transform (gimple_stmt_iterator *si)
|
|
|
636 {
|
|
|
637 histogram_value histogram;
|
|
|
638 enum tree_code code;
|
|
|
639 gcov_type val, count, all;
|
|
|
640 tree result, value, tree_val;
|
|
|
641 gcov_type prob;
|
|
|
642 gimple stmt;
|
|
|
643
|
|
|
644 stmt = gsi_stmt (*si);
|
|
|
645 if (gimple_code (stmt) != GIMPLE_ASSIGN)
|
|
|
646 return false;
|
|
|
647
|
|
|
648 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt))))
|
|
|
649 return false;
|
|
|
650
|
|
|
651 code = gimple_assign_rhs_code (stmt);
|
|
|
652
|
|
|
653 if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR)
|
|
|
654 return false;
|
|
|
655
|
|
|
656 histogram = gimple_histogram_value_of_type (cfun, stmt,
|
|
|
657 HIST_TYPE_SINGLE_VALUE);
|
|
|
658 if (!histogram)
|
|
|
659 return false;
|
|
|
660
|
|
|
661 value = histogram->hvalue.value;
|
|
|
662 val = histogram->hvalue.counters[0];
|
|
|
663 count = histogram->hvalue.counters[1];
|
|
|
664 all = histogram->hvalue.counters[2];
|
|
|
665 gimple_remove_histogram_value (cfun, stmt, histogram);
|
|
|
666
|
|
|
667 /* We require that count is at least half of all; this means
|
|
|
668 that for the transformation to fire the value must be constant
|
|
|
669 at least 50% of time (and 75% gives the guarantee of usage). */
|
|
|
670 if (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1
|
|
|
671 || 2 * count < all
|
|
|
672 || optimize_bb_for_size_p (gimple_bb (stmt)))
|
|
|
673 return false;
|
|
|
674
|
|
|
675 if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count))
|
|
|
676 return false;
|
|
|
677
|
|
|
678 /* Compute probability of taking the optimal path. */
|
|
|
679 if (all > 0)
|
|
|
680 prob = (count * REG_BR_PROB_BASE + all / 2) / all;
|
|
|
681 else
|
|
|
682 prob = 0;
|
|
|
683
|
|
|
684 tree_val = build_int_cst_wide (get_gcov_type (),
|
|
|
685 (unsigned HOST_WIDE_INT) val,
|
|
|
686 val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
|
|
|
687 result = gimple_divmod_fixed_value (stmt, tree_val, prob, count, all);
|
|
|
688
|
|
|
689 if (dump_file)
|
|
|
690 {
|
|
|
691 fprintf (dump_file, "Div/mod by constant ");
|
|
|
692 print_generic_expr (dump_file, value, TDF_SLIM);
|
|
|
693 fprintf (dump_file, "=");
|
|
|
694 print_generic_expr (dump_file, tree_val, TDF_SLIM);
|
|
|
695 fprintf (dump_file, " transformation on insn ");
|
|
|
696 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
|
|
697 }
|
|
|
698
|
|
|
699 gimple_assign_set_rhs_from_tree (si, result);
|
|
|
700
|
|
|
701 return true;
|
|
|
702 }
|
|
|
703
|
|
|
704 /* Generate code for transformation 2 (with parent gimple assign STMT and
|
|
|
705 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
|
|
|
706 within roundoff error). This generates the result into a temp and returns
|
|
|
707 the temp; it does not replace or alter the original STMT. */
|
|
|
708 static tree
|
|
|
709 gimple_mod_pow2 (gimple stmt, int prob, gcov_type count, gcov_type all)
|
|
|
710 {
|
|
|
711 gimple stmt1, stmt2, stmt3, stmt4;
|
|
|
712 tree tmp2, tmp3;
|
|
|
713 gimple bb1end, bb2end, bb3end;
|
|
|
714 basic_block bb, bb2, bb3, bb4;
|
|
|
715 tree optype, op1, op2;
|
|
|
716 edge e12, e13, e23, e24, e34;
|
|
|
717 gimple_stmt_iterator gsi;
|
|
|
718 tree result;
|
|
|
719
|
|
|
720 gcc_assert (is_gimple_assign (stmt)
|
|
|
721 && gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR);
|
|
|
722
|
|
|
723 optype = TREE_TYPE (gimple_assign_lhs (stmt));
|
|
|
724 op1 = gimple_assign_rhs1 (stmt);
|
|
|
725 op2 = gimple_assign_rhs2 (stmt);
|
|
|
726
|
|
|
727 bb = gimple_bb (stmt);
|
|
|
728 gsi = gsi_for_stmt (stmt);
|
|
|
729
|
|
|
730 result = create_tmp_var (optype, "PROF");
|
|
|
731 tmp2 = create_tmp_var (optype, "PROF");
|
|
|
732 tmp3 = create_tmp_var (optype, "PROF");
|
|
|
733 stmt2 = gimple_build_assign_with_ops (PLUS_EXPR, tmp2, op2,
|
|
|
734 build_int_cst (optype, -1));
|
|
|
735 stmt3 = gimple_build_assign_with_ops (BIT_AND_EXPR, tmp3, tmp2, op2);
|
|
|
736 stmt4 = gimple_build_cond (NE_EXPR, tmp3, build_int_cst (optype, 0),
|
|
|
737 NULL_TREE, NULL_TREE);
|
|
|
738 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
|
|
|
739 gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
|
|
|
740 gsi_insert_before (&gsi, stmt4, GSI_SAME_STMT);
|
|
|
741 bb1end = stmt4;
|
|
|
742
|
|
|
743 /* tmp2 == op2-1 inherited from previous block. */
|
|
|
744 stmt1 = gimple_build_assign_with_ops (BIT_AND_EXPR, result, op1, tmp2);
|
|
|
745 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
|
|
|
746 bb2end = stmt1;
|
|
|
747
|
|
|
748 stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), result,
|
|
|
749 op1, op2);
|
|
|
750 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
|
|
|
751 bb3end = stmt1;
|
|
|
752
|
|
|
753 /* Fix CFG. */
|
|
|
754 /* Edge e23 connects bb2 to bb3, etc. */
|
|
|
755 e12 = split_block (bb, bb1end);
|
|
|
756 bb2 = e12->dest;
|
|
|
757 bb2->count = count;
|
|
|
758 e23 = split_block (bb2, bb2end);
|
|
|
759 bb3 = e23->dest;
|
|
|
760 bb3->count = all - count;
|
|
|
761 e34 = split_block (bb3, bb3end);
|
|
|
762 bb4 = e34->dest;
|
|
|
763 bb4->count = all;
|
|
|
764
|
|
|
765 e12->flags &= ~EDGE_FALLTHRU;
|
|
|
766 e12->flags |= EDGE_FALSE_VALUE;
|
|
|
767 e12->probability = prob;
|
|
|
768 e12->count = count;
|
|
|
769
|
|
|
770 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
|
|
|
771 e13->probability = REG_BR_PROB_BASE - prob;
|
|
|
772 e13->count = all - count;
|
|
|
773
|
|
|
774 remove_edge (e23);
|
|
|
775
|
|
|
776 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
|
|
|
777 e24->probability = REG_BR_PROB_BASE;
|
|
|
778 e24->count = count;
|
|
|
779
|
|
|
780 e34->probability = REG_BR_PROB_BASE;
|
|
|
781 e34->count = all - count;
|
|
|
782
|
|
|
783 return result;
|
|
|
784 }
|
|
|
785
|
|
|
786 /* Do transform 2) on INSN if applicable. */
|
|
|
787 static bool
|
|
|
788 gimple_mod_pow2_value_transform (gimple_stmt_iterator *si)
|
|
|
789 {
|
|
|
790 histogram_value histogram;
|
|
|
791 enum tree_code code;
|
|
|
792 gcov_type count, wrong_values, all;
|
|
|
793 tree lhs_type, result, value;
|
|
|
794 gcov_type prob;
|
|
|
795 gimple stmt;
|
|
|
796
|
|
|
797 stmt = gsi_stmt (*si);
|
|
|
798 if (gimple_code (stmt) != GIMPLE_ASSIGN)
|
|
|
799 return false;
|
|
|
800
|
|
|
801 lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
|
|
|
802 if (!INTEGRAL_TYPE_P (lhs_type))
|
|
|
803 return false;
|
|
|
804
|
|
|
805 code = gimple_assign_rhs_code (stmt);
|
|
|
806
|
|
|
807 if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type))
|
|
|
808 return false;
|
|
|
809
|
|
|
810 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_POW2);
|
|
|
811 if (!histogram)
|
|
|
812 return false;
|
|
|
813
|
|
|
814 value = histogram->hvalue.value;
|
|
|
815 wrong_values = histogram->hvalue.counters[0];
|
|
|
816 count = histogram->hvalue.counters[1];
|
|
|
817
|
|
|
818 gimple_remove_histogram_value (cfun, stmt, histogram);
|
|
|
819
|
|
|
820 /* We require that we hit a power of 2 at least half of all evaluations. */
|
|
|
821 if (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1
|
|
|
822 || count < wrong_values
|
|
|
823 || optimize_bb_for_size_p (gimple_bb (stmt)))
|
|
|
824 return false;
|
|
|
825
|
|
|
826 if (dump_file)
|
|
|
827 {
|
|
|
828 fprintf (dump_file, "Mod power of 2 transformation on insn ");
|
|
|
829 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
|
|
830 }
|
|
|
831
|
|
|
832 /* Compute probability of taking the optimal path. */
|
|
|
833 all = count + wrong_values;
|
|
|
834
|
|
|
835 if (check_counter (stmt, "pow2", &count, &all, gimple_bb (stmt)->count))
|
|
|
836 return false;
|
|
|
837
|
|
|
838 if (all > 0)
|
|
|
839 prob = (count * REG_BR_PROB_BASE + all / 2) / all;
|
|
|
840 else
|
|
|
841 prob = 0;
|
|
|
842
|
|
|
843 result = gimple_mod_pow2 (stmt, prob, count, all);
|
|
|
844
|
|
|
845 gimple_assign_set_rhs_from_tree (si, result);
|
|
|
846
|
|
|
847 return true;
|
|
|
848 }
|
|
|
849
|
|
|
850 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
|
|
|
851 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
|
|
|
852 supported and this is built into this interface. The probabilities of taking
|
|
|
853 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
|
|
|
854 COUNT2/ALL respectively within roundoff error). This generates the
|
|
|
855 result into a temp and returns the temp; it does not replace or alter
|
|
|
856 the original STMT. */
|
|
|
857 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
|
|
|
858
|
|
|
859 static tree
|
|
|
860 gimple_mod_subtract (gimple stmt, int prob1, int prob2, int ncounts,
|
|
|
861 gcov_type count1, gcov_type count2, gcov_type all)
|
|
|
862 {
|
|
|
863 gimple stmt1, stmt2, stmt3;
|
|
|
864 tree tmp1;
|
|
|
865 gimple bb1end, bb2end = NULL, bb3end;
|
|
|
866 basic_block bb, bb2, bb3, bb4;
|
|
|
867 tree optype, op1, op2;
|
|
|
868 edge e12, e23 = 0, e24, e34, e14;
|
|
|
869 gimple_stmt_iterator gsi;
|
|
|
870 tree result;
|
|
|
871
|
|
|
872 gcc_assert (is_gimple_assign (stmt)
|
|
|
873 && gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR);
|
|
|
874
|
|
|
875 optype = TREE_TYPE (gimple_assign_lhs (stmt));
|
|
|
876 op1 = gimple_assign_rhs1 (stmt);
|
|
|
877 op2 = gimple_assign_rhs2 (stmt);
|
|
|
878
|
|
|
879 bb = gimple_bb (stmt);
|
|
|
880 gsi = gsi_for_stmt (stmt);
|
|
|
881
|
|
|
882 result = create_tmp_var (optype, "PROF");
|
|
|
883 tmp1 = create_tmp_var (optype, "PROF");
|
|
|
884 stmt1 = gimple_build_assign (result, op1);
|
|
|
885 stmt2 = gimple_build_assign (tmp1, op2);
|
|
|
886 stmt3 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE);
|
|
|
887 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
|
|
|
888 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
|
|
|
889 gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
|
|
|
890 bb1end = stmt3;
|
|
|
891
|
|
|
892 if (ncounts) /* Assumed to be 0 or 1 */
|
|
|
893 {
|
|
|
894 stmt1 = gimple_build_assign_with_ops (MINUS_EXPR, result, result, tmp1);
|
|
|
895 stmt2 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE);
|
|
|
896 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
|
|
|
897 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
|
|
|
898 bb2end = stmt2;
|
|
|
899 }
|
|
|
900
|
|
|
901 /* Fallback case. */
|
|
|
902 stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), result,
|
|
|
903 result, tmp1);
|
|
|
904 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
|
|
|
905 bb3end = stmt1;
|
|
|
906
|
|
|
907 /* Fix CFG. */
|
|
|
908 /* Edge e23 connects bb2 to bb3, etc. */
|
|
|
909 /* However block 3 is optional; if it is not there, references
|
|
|
910 to 3 really refer to block 2. */
|
|
|
911 e12 = split_block (bb, bb1end);
|
|
|
912 bb2 = e12->dest;
|
|
|
913 bb2->count = all - count1;
|
|
|
914
|
|
|
915 if (ncounts) /* Assumed to be 0 or 1. */
|
|
|
916 {
|
|
|
917 e23 = split_block (bb2, bb2end);
|
|
|
918 bb3 = e23->dest;
|
|
|
919 bb3->count = all - count1 - count2;
|
|
|
920 }
|
|
|
921
|
|
|
922 e34 = split_block (ncounts ? bb3 : bb2, bb3end);
|
|
|
923 bb4 = e34->dest;
|
|
|
924 bb4->count = all;
|
|
|
925
|
|
|
926 e12->flags &= ~EDGE_FALLTHRU;
|
|
|
927 e12->flags |= EDGE_FALSE_VALUE;
|
|
|
928 e12->probability = REG_BR_PROB_BASE - prob1;
|
|
|
929 e12->count = all - count1;
|
|
|
930
|
|
|
931 e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE);
|
|
|
932 e14->probability = prob1;
|
|
|
933 e14->count = count1;
|
|
|
934
|
|
|
935 if (ncounts) /* Assumed to be 0 or 1. */
|
|
|
936 {
|
|
|
937 e23->flags &= ~EDGE_FALLTHRU;
|
|
|
938 e23->flags |= EDGE_FALSE_VALUE;
|
|
|
939 e23->count = all - count1 - count2;
|
|
|
940 e23->probability = REG_BR_PROB_BASE - prob2;
|
|
|
941
|
|
|
942 e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE);
|
|
|
943 e24->probability = prob2;
|
|
|
944 e24->count = count2;
|
|
|
945 }
|
|
|
946
|
|
|
947 e34->probability = REG_BR_PROB_BASE;
|
|
|
948 e34->count = all - count1 - count2;
|
|
|
949
|
|
|
950 return result;
|
|
|
951 }
|
|
|
952
|
|
|
953
|
|
|
954 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
|
|
|
955
|
|
|
956 static bool
|
|
|
957 gimple_mod_subtract_transform (gimple_stmt_iterator *si)
|
|
|
958 {
|
|
|
959 histogram_value histogram;
|
|
|
960 enum tree_code code;
|
|
|
961 gcov_type count, wrong_values, all;
|
|
|
962 tree lhs_type, result, value;
|
|
|
963 gcov_type prob1, prob2;
|
|
|
964 unsigned int i, steps;
|
|
|
965 gcov_type count1, count2;
|
|
|
966 gimple stmt;
|
|
|
967
|
|
|
968 stmt = gsi_stmt (*si);
|
|
|
969 if (gimple_code (stmt) != GIMPLE_ASSIGN)
|
|
|
970 return false;
|
|
|
971
|
|
|
972 lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
|
|
|
973 if (!INTEGRAL_TYPE_P (lhs_type))
|
|
|
974 return false;
|
|
|
975
|
|
|
976 code = gimple_assign_rhs_code (stmt);
|
|
|
977
|
|
|
978 if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type))
|
|
|
979 return false;
|
|
|
980
|
|
|
981 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INTERVAL);
|
|
|
982 if (!histogram)
|
|
|
983 return false;
|
|
|
984
|
|
|
985 value = histogram->hvalue.value;
|
|
|
986 all = 0;
|
|
|
987 wrong_values = 0;
|
|
|
988 for (i = 0; i < histogram->hdata.intvl.steps; i++)
|
|
|
989 all += histogram->hvalue.counters[i];
|
|
|
990
|
|
|
991 wrong_values += histogram->hvalue.counters[i];
|
|
|
992 wrong_values += histogram->hvalue.counters[i+1];
|
|
|
993 steps = histogram->hdata.intvl.steps;
|
|
|
994 all += wrong_values;
|
|
|
995 count1 = histogram->hvalue.counters[0];
|
|
|
996 count2 = histogram->hvalue.counters[1];
|
|
|
997
|
|
|
998 /* Compute probability of taking the optimal path. */
|
|
|
999 if (check_counter (stmt, "interval", &count1, &all, gimple_bb (stmt)->count))
|
|
|
1000 {
|
|
|
1001 gimple_remove_histogram_value (cfun, stmt, histogram);
|
|
|
1002 return false;
|
|
|
1003 }
|
|
|
1004
|
|
|
1005 if (flag_profile_correction && count1 + count2 > all)
|
|
|
1006 all = count1 + count2;
|
|
|
1007
|
|
|
1008 gcc_assert (count1 + count2 <= all);
|
|
|
1009
|
|
|
1010 /* We require that we use just subtractions in at least 50% of all
|
|
|
1011 evaluations. */
|
|
|
1012 count = 0;
|
|
|
1013 for (i = 0; i < histogram->hdata.intvl.steps; i++)
|
|
|
1014 {
|
|
|
1015 count += histogram->hvalue.counters[i];
|
|
|
1016 if (count * 2 >= all)
|
|
|
1017 break;
|
|
|
1018 }
|
|
|
1019 if (i == steps
|
|
|
1020 || optimize_bb_for_size_p (gimple_bb (stmt)))
|
|
|
1021 return false;
|
|
|
1022
|
|
|
1023 gimple_remove_histogram_value (cfun, stmt, histogram);
|
|
|
1024 if (dump_file)
|
|
|
1025 {
|
|
|
1026 fprintf (dump_file, "Mod subtract transformation on insn ");
|
|
|
1027 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
|
|
1028 }
|
|
|
1029
|
|
|
1030 /* Compute probability of taking the optimal path(s). */
|
|
|
1031 if (all > 0)
|
|
|
1032 {
|
|
|
1033 prob1 = (count1 * REG_BR_PROB_BASE + all / 2) / all;
|
|
|
1034 prob2 = (count2 * REG_BR_PROB_BASE + all / 2) / all;
|
|
|
1035 }
|
|
|
1036 else
|
|
|
1037 {
|
|
|
1038 prob1 = prob2 = 0;
|
|
|
1039 }
|
|
|
1040
|
|
|
1041 /* In practice, "steps" is always 2. This interface reflects this,
|
|
|
1042 and will need to be changed if "steps" can change. */
|
|
|
1043 result = gimple_mod_subtract (stmt, prob1, prob2, i, count1, count2, all);
|
|
|
1044
|
|
|
1045 gimple_assign_set_rhs_from_tree (si, result);
|
|
|
1046
|
|
|
1047 return true;
|
|
|
1048 }
|
|
|
1049
|
|
|
1050 static struct cgraph_node** pid_map = NULL;
|
|
|
1051
|
|
|
1052 /* Initialize map of pids (pid -> cgraph node) */
|
|
|
1053
|
|
|
1054 static void
|
|
|
1055 init_pid_map (void)
|
|
|
1056 {
|
|
|
1057 struct cgraph_node *n;
|
|
|
1058
|
|
|
1059 if (pid_map != NULL)
|
|
|
1060 return;
|
|
|
1061
|
|
|
1062 pid_map
|
|
|
1063 = (struct cgraph_node**) xmalloc (sizeof (struct cgraph_node*) * cgraph_max_pid);
|
|
|
1064
|
|
|
1065 for (n = cgraph_nodes; n; n = n->next)
|
|
|
1066 {
|
|
|
1067 if (n->pid != -1)
|
|
|
1068 pid_map [n->pid] = n;
|
|
|
1069 }
|
|
|
1070 }
|
|
|
1071
|
|
|
1072 /* Return cgraph node for function with pid */
|
|
|
1073
|
|
|
1074 static inline struct cgraph_node*
|
|
|
1075 find_func_by_pid (int pid)
|
|
|
1076 {
|
|
|
1077 init_pid_map ();
|
|
|
1078
|
|
|
1079 return pid_map [pid];
|
|
|
1080 }
|
|
|
1081
|
|
|
1082 /* Do transformation
|
|
|
1083
|
|
|
1084 if (actual_callee_address == address_of_most_common_function/method)
|
|
|
1085 do direct call
|
|
|
1086 else
|
|
|
1087 old call
|
|
|
1088 */
|
|
|
1089
|
|
|
1090 static gimple
|
|
|
1091 gimple_ic (gimple stmt, gimple call, struct cgraph_node *direct_call,
|
|
|
1092 int prob, gcov_type count, gcov_type all)
|
|
|
1093 {
|
|
|
1094 gimple stmt1, stmt2, stmt3;
|
|
|
1095 tree tmp1, tmpv, tmp;
|
|
|
1096 gimple bb1end, bb2end, bb3end;
|
|
|
1097 basic_block bb, bb2, bb3, bb4;
|
|
|
1098 tree optype = build_pointer_type (void_type_node);
|
|
|
1099 edge e12, e13, e23, e24, e34;
|
|
|
1100 gimple_stmt_iterator gsi;
|
|
|
1101 int region;
|
|
|
1102
|
|
|
1103 bb = gimple_bb (stmt);
|
|
|
1104 gsi = gsi_for_stmt (stmt);
|
|
|
1105
|
|
|
1106 tmpv = create_tmp_var (optype, "PROF");
|
|
|
1107 tmp1 = create_tmp_var (optype, "PROF");
|
|
|
1108 stmt1 = gimple_build_assign (tmpv, unshare_expr (gimple_call_fn (call)));
|
|
|
1109
|
|
|
1110 tmp = fold_convert (optype, build_addr (direct_call->decl,
|
|
|
1111 current_function_decl));
|
|
|
1112 stmt2 = gimple_build_assign (tmp1, tmp);
|
|
|
1113 stmt3 = gimple_build_cond (NE_EXPR, tmp1, tmpv, NULL_TREE, NULL_TREE);
|
|
|
1114 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
|
|
|
1115 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
|
|
|
1116 gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
|
|
|
1117 bb1end = stmt3;
|
|
|
1118
|
|
|
1119 stmt1 = gimple_copy (stmt);
|
|
|
1120 gimple_call_set_fndecl (stmt1, direct_call->decl);
|
|
|
1121 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
|
|
|
1122 bb2end = stmt1;
|
|
|
1123 bb3end = stmt;
|
|
|
1124
|
|
|
1125 /* Fix CFG. */
|
|
|
1126 /* Edge e23 connects bb2 to bb3, etc. */
|
|
|
1127 e12 = split_block (bb, bb1end);
|
|
|
1128 bb2 = e12->dest;
|
|
|
1129 bb2->count = count;
|
|
|
1130 e23 = split_block (bb2, bb2end);
|
|
|
1131 bb3 = e23->dest;
|
|
|
1132 bb3->count = all - count;
|
|
|
1133 e34 = split_block (bb3, bb3end);
|
|
|
1134 bb4 = e34->dest;
|
|
|
1135 bb4->count = all;
|
|
|
1136
|
|
|
1137 e12->flags &= ~EDGE_FALLTHRU;
|
|
|
1138 e12->flags |= EDGE_FALSE_VALUE;
|
|
|
1139 e12->probability = prob;
|
|
|
1140 e12->count = count;
|
|
|
1141
|
|
|
1142 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
|
|
|
1143 e13->probability = REG_BR_PROB_BASE - prob;
|
|
|
1144 e13->count = all - count;
|
|
|
1145
|
|
|
1146 remove_edge (e23);
|
|
|
1147
|
|
|
1148 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
|
|
|
1149 e24->probability = REG_BR_PROB_BASE;
|
|
|
1150 e24->count = count;
|
|
|
1151 e34->probability = REG_BR_PROB_BASE;
|
|
|
1152 e34->count = all - count;
|
|
|
1153
|
|
|
1154 /* Fix eh edges */
|
|
|
1155 region = lookup_stmt_eh_region (stmt);
|
|
|
1156 if (region >= 0 && stmt_could_throw_p (stmt1))
|
|
|
1157 {
|
|
|
1158 add_stmt_to_eh_region (stmt1, region);
|
|
|
1159 make_eh_edges (stmt1);
|
|
|
1160 }
|
|
|
1161
|
|
|
1162 if (region >= 0 && stmt_could_throw_p (stmt))
|
|
|
1163 {
|
|
|
1164 gimple_purge_dead_eh_edges (bb4);
|
|
|
1165 make_eh_edges (stmt);
|
|
|
1166 }
|
|
|
1167
|
|
|
1168 return stmt1;
|
|
|
1169 }
|
|
|
1170
|
|
|
1171 /*
|
|
|
1172 For every checked indirect/virtual call determine if most common pid of
|
|
|
1173 function/class method has probability more than 50%. If yes modify code of
|
|
|
1174 this call to:
|
|
|
1175 */
|
|
|
1176
|
|
|
1177 static bool
|
|
|
1178 gimple_ic_transform (gimple stmt)
|
|
|
1179 {
|
|
|
1180 histogram_value histogram;
|
|
|
1181 gcov_type val, count, all, bb_all;
|
|
|
1182 gcov_type prob;
|
|
|
1183 tree callee;
|
|
|
1184 gimple modify;
|
|
|
1185 struct cgraph_node *direct_call;
|
|
|
1186
|
|
|
1187 if (gimple_code (stmt) != GIMPLE_CALL)
|
|
|
1188 return false;
|
|
|
1189
|
|
|
1190 callee = gimple_call_fn (stmt);
|
|
|
1191
|
|
|
1192 if (TREE_CODE (callee) == FUNCTION_DECL)
|
|
|
1193 return false;
|
|
|
1194
|
|
|
1195 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INDIR_CALL);
|
|
|
1196 if (!histogram)
|
|
|
1197 return false;
|
|
|
1198
|
|
|
1199 val = histogram->hvalue.counters [0];
|
|
|
1200 count = histogram->hvalue.counters [1];
|
|
|
1201 all = histogram->hvalue.counters [2];
|
|
|
1202 gimple_remove_histogram_value (cfun, stmt, histogram);
|
|
|
1203
|
|
|
1204 if (4 * count <= 3 * all)
|
|
|
1205 return false;
|
|
|
1206
|
|
|
1207 bb_all = gimple_bb (stmt)->count;
|
|
|
1208 /* The order of CHECK_COUNTER calls is important -
|
|
|
1209 since check_counter can correct the third parameter
|
|
|
1210 and we want to make count <= all <= bb_all. */
|
|
|
1211 if ( check_counter (stmt, "ic", &all, &bb_all, bb_all)
|
|
|
1212 || check_counter (stmt, "ic", &count, &all, all))
|
|
|
1213 return false;
|
|
|
1214
|
|
|
1215 if (all > 0)
|
|
|
1216 prob = (count * REG_BR_PROB_BASE + all / 2) / all;
|
|
|
1217 else
|
|
|
1218 prob = 0;
|
|
|
1219 direct_call = find_func_by_pid ((int)val);
|
|
|
1220
|
|
|
1221 if (direct_call == NULL)
|
|
|
1222 return false;
|
|
|
1223
|
|
|
1224 modify = gimple_ic (stmt, stmt, direct_call, prob, count, all);
|
|
|
1225
|
|
|
1226 if (dump_file)
|
|
|
1227 {
|
|
|
1228 fprintf (dump_file, "Indirect call -> direct call ");
|
|
|
1229 print_generic_expr (dump_file, gimple_call_fn (stmt), TDF_SLIM);
|
|
|
1230 fprintf (dump_file, "=> ");
|
|
|
1231 print_generic_expr (dump_file, direct_call->decl, TDF_SLIM);
|
|
|
1232 fprintf (dump_file, " transformation on insn ");
|
|
|
1233 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
|
|
1234 fprintf (dump_file, " to ");
|
|
|
1235 print_gimple_stmt (dump_file, modify, 0, TDF_SLIM);
|
|
|
1236 fprintf (dump_file, "hist->count "HOST_WIDEST_INT_PRINT_DEC
|
|
|
1237 " hist->all "HOST_WIDEST_INT_PRINT_DEC"\n", count, all);
|
|
|
1238 }
|
|
|
1239
|
|
|
1240 return true;
|
|
|
1241 }
|
|
|
1242
|
|
|
1243 /* Return true if the stringop CALL with FNDECL shall be profiled. */
|
|
|
1244 static bool
|
|
|
1245 interesting_stringop_to_profile_p (tree fndecl, gimple call)
|
|
|
1246 {
|
|
|
1247 enum built_in_function fcode = DECL_FUNCTION_CODE (fndecl);
|
|
|
1248
|
|
|
1249 if (fcode != BUILT_IN_MEMCPY && fcode != BUILT_IN_MEMPCPY
|
|
|
1250 && fcode != BUILT_IN_MEMSET && fcode != BUILT_IN_BZERO)
|
|
|
1251 return false;
|
|
|
1252
|
|
|
1253 switch (fcode)
|
|
|
1254 {
|
|
|
1255 case BUILT_IN_MEMCPY:
|
|
|
1256 case BUILT_IN_MEMPCPY:
|
|
|
1257 return validate_gimple_arglist (call, POINTER_TYPE, POINTER_TYPE,
|
|
|
1258 INTEGER_TYPE, VOID_TYPE);
|
|
|
1259 case BUILT_IN_MEMSET:
|
|
|
1260 return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE,
|
|
|
1261 INTEGER_TYPE, VOID_TYPE);
|
|
|
1262 case BUILT_IN_BZERO:
|
|
|
1263 return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE,
|
|
|
1264 VOID_TYPE);
|
|
|
1265 default:
|
|
|
1266 gcc_unreachable ();
|
|
|
1267 }
|
|
|
1268 }
|
|
|
1269
|
|
|
1270 /* Convert stringop (..., size)
|
|
|
1271 into
|
|
|
1272 if (size == VALUE)
|
|
|
1273 stringop (...., VALUE);
|
|
|
1274 else
|
|
|
1275 stringop (...., size);
|
|
|
1276 assuming constant propagation of VALUE will happen later.
|
|
|
1277 */
|
|
|
1278 static void
|
|
|
1279 gimple_stringop_fixed_value (gimple stmt, tree value, int prob, gcov_type count,
|
|
|
1280 gcov_type all)
|
|
|
1281 {
|
|
|
1282 gimple stmt1, stmt2, stmt3;
|
|
|
1283 tree tmp1, tmpv;
|
|
|
1284 gimple bb1end, bb2end;
|
|
|
1285 basic_block bb, bb2, bb3, bb4;
|
|
|
1286 edge e12, e13, e23, e24, e34;
|
|
|
1287 gimple_stmt_iterator gsi;
|
|
|
1288 tree blck_size = gimple_call_arg (stmt, 2);
|
|
|
1289 tree optype = TREE_TYPE (blck_size);
|
|
|
1290 int region;
|
|
|
1291
|
|
|
1292 bb = gimple_bb (stmt);
|
|
|
1293 gsi = gsi_for_stmt (stmt);
|
|
|
1294
|
|
|
1295 if (gsi_end_p (gsi))
|
|
|
1296 {
|
|
|
1297 edge_iterator ei;
|
|
|
1298 for (ei = ei_start (bb->succs); (e34 = ei_safe_edge (ei)); )
|
|
|
1299 if (!(e34->flags & EDGE_ABNORMAL))
|
|
|
1300 break;
|
|
|
1301 }
|
|
|
1302 else
|
|
|
1303 {
|
|
|
1304 e34 = split_block (bb, stmt);
|
|
|
1305 gsi = gsi_for_stmt (stmt);
|
|
|
1306 }
|
|
|
1307 bb4 = e34->dest;
|
|
|
1308
|
|
|
1309 tmpv = create_tmp_var (optype, "PROF");
|
|
|
1310 tmp1 = create_tmp_var (optype, "PROF");
|
|
|
1311 stmt1 = gimple_build_assign (tmpv, fold_convert (optype, value));
|
|
|
1312 stmt2 = gimple_build_assign (tmp1, blck_size);
|
|
|
1313 stmt3 = gimple_build_cond (NE_EXPR, tmp1, tmpv, NULL_TREE, NULL_TREE);
|
|
|
1314 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
|
|
|
1315 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
|
|
|
1316 gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
|
|
|
1317 bb1end = stmt3;
|
|
|
1318
|
|
|
1319 stmt1 = gimple_copy (stmt);
|
|
|
1320 gimple_call_set_arg (stmt1, 2, value);
|
|
|
1321 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
|
|
|
1322 region = lookup_stmt_eh_region (stmt);
|
|
|
1323 if (region >= 0)
|
|
|
1324 add_stmt_to_eh_region (stmt1, region);
|
|
|
1325 bb2end = stmt1;
|
|
|
1326
|
|
|
1327 /* Fix CFG. */
|
|
|
1328 /* Edge e23 connects bb2 to bb3, etc. */
|
|
|
1329 e12 = split_block (bb, bb1end);
|
|
|
1330 bb2 = e12->dest;
|
|
|
1331 bb2->count = count;
|
|
|
1332 e23 = split_block (bb2, bb2end);
|
|
|
1333 bb3 = e23->dest;
|
|
|
1334 bb3->count = all - count;
|
|
|
1335
|
|
|
1336 e12->flags &= ~EDGE_FALLTHRU;
|
|
|
1337 e12->flags |= EDGE_FALSE_VALUE;
|
|
|
1338 e12->probability = prob;
|
|
|
1339 e12->count = count;
|
|
|
1340
|
|
|
1341 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
|
|
|
1342 e13->probability = REG_BR_PROB_BASE - prob;
|
|
|
1343 e13->count = all - count;
|
|
|
1344
|
|
|
1345 remove_edge (e23);
|
|
|
1346
|
|
|
1347 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
|
|
|
1348 e24->probability = REG_BR_PROB_BASE;
|
|
|
1349 e24->count = count;
|
|
|
1350
|
|
|
1351 e34->probability = REG_BR_PROB_BASE;
|
|
|
1352 e34->count = all - count;
|
|
|
1353 }
|
|
|
1354
|
|
|
1355 /* Find values inside STMT for that we want to measure histograms for
|
|
|
1356 division/modulo optimization. */
|
|
|
1357 static bool
|
|
|
1358 gimple_stringops_transform (gimple_stmt_iterator *gsi)
|
|
|
1359 {
|
|
|
1360 gimple stmt = gsi_stmt (*gsi);
|
|
|
1361 tree fndecl;
|
|
|
1362 tree blck_size;
|
|
|
1363 enum built_in_function fcode;
|
|
|
1364 histogram_value histogram;
|
|
|
1365 gcov_type count, all, val;
|
|
|
1366 tree value;
|
|
|
1367 tree dest, src;
|
|
|
1368 unsigned int dest_align, src_align;
|
|
|
1369 gcov_type prob;
|
|
|
1370 tree tree_val;
|
|
|
1371
|
|
|
1372 if (gimple_code (stmt) != GIMPLE_CALL)
|
|
|
1373 return false;
|
|
|
1374 fndecl = gimple_call_fndecl (stmt);
|
|
|
1375 if (!fndecl)
|
|
|
1376 return false;
|
|
|
1377 fcode = DECL_FUNCTION_CODE (fndecl);
|
|
|
1378 if (!interesting_stringop_to_profile_p (fndecl, stmt))
|
|
|
1379 return false;
|
|
|
1380
|
|
|
1381 if (fcode == BUILT_IN_BZERO)
|
|
|
1382 blck_size = gimple_call_arg (stmt, 1);
|
|
|
1383 else
|
|
|
1384 blck_size = gimple_call_arg (stmt, 2);
|
|
|
1385 if (TREE_CODE (blck_size) == INTEGER_CST)
|
|
|
1386 return false;
|
|
|
1387
|
|
|
1388 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE);
|
|
|
1389 if (!histogram)
|
|
|
1390 return false;
|
|
|
1391 value = histogram->hvalue.value;
|
|
|
1392 val = histogram->hvalue.counters[0];
|
|
|
1393 count = histogram->hvalue.counters[1];
|
|
|
1394 all = histogram->hvalue.counters[2];
|
|
|
1395 gimple_remove_histogram_value (cfun, stmt, histogram);
|
|
|
1396 /* We require that count is at least half of all; this means
|
|
|
1397 that for the transformation to fire the value must be constant
|
|
|
1398 at least 80% of time. */
|
|
|
1399 if ((6 * count / 5) < all || optimize_bb_for_size_p (gimple_bb (stmt)))
|
|
|
1400 return false;
|
|
|
1401 if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count))
|
|
|
1402 return false;
|
|
|
1403 if (all > 0)
|
|
|
1404 prob = (count * REG_BR_PROB_BASE + all / 2) / all;
|
|
|
1405 else
|
|
|
1406 prob = 0;
|
|
|
1407 dest = gimple_call_arg (stmt, 0);
|
|
|
1408 dest_align = get_pointer_alignment (dest, BIGGEST_ALIGNMENT);
|
|
|
1409 switch (fcode)
|
|
|
1410 {
|
|
|
1411 case BUILT_IN_MEMCPY:
|
|
|
1412 case BUILT_IN_MEMPCPY:
|
|
|
1413 src = gimple_call_arg (stmt, 1);
|
|
|
1414 src_align = get_pointer_alignment (src, BIGGEST_ALIGNMENT);
|
|
|
1415 if (!can_move_by_pieces (val, MIN (dest_align, src_align)))
|
|
|
1416 return false;
|
|
|
1417 break;
|
|
|
1418 case BUILT_IN_MEMSET:
|
|
|
1419 if (!can_store_by_pieces (val, builtin_memset_read_str,
|
|
|
1420 gimple_call_arg (stmt, 1),
|
|
|
1421 dest_align, true))
|
|
|
1422 return false;
|
|
|
1423 break;
|
|
|
1424 case BUILT_IN_BZERO:
|
|
|
1425 if (!can_store_by_pieces (val, builtin_memset_read_str,
|
|
|
1426 integer_zero_node,
|
|
|
1427 dest_align, true))
|
|
|
1428 return false;
|
|
|
1429 break;
|
|
|
1430 default:
|
|
|
1431 gcc_unreachable ();
|
|
|
1432 }
|
|
|
1433 tree_val = build_int_cst_wide (get_gcov_type (),
|
|
|
1434 (unsigned HOST_WIDE_INT) val,
|
|
|
1435 val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
|
|
|
1436 if (dump_file)
|
|
|
1437 {
|
|
|
1438 fprintf (dump_file, "Single value %i stringop transformation on ",
|
|
|
1439 (int)val);
|
|
|
1440 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
|
|
1441 }
|
|
|
1442 gimple_stringop_fixed_value (stmt, tree_val, prob, count, all);
|
|
|
1443
|
|
|
1444 return true;
|
|
|
1445 }
|
|
|
1446
|
|
|
1447 void
|
|
|
1448 stringop_block_profile (gimple stmt, unsigned int *expected_align,
|
|
|
1449 HOST_WIDE_INT *expected_size)
|
|
|
1450 {
|
|
|
1451 histogram_value histogram;
|
|
|
1452 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_AVERAGE);
|
|
|
1453 if (!histogram)
|
|
|
1454 *expected_size = -1;
|
|
|
1455 else if (!histogram->hvalue.counters[1])
|
|
|
1456 {
|
|
|
1457 *expected_size = -1;
|
|
|
1458 gimple_remove_histogram_value (cfun, stmt, histogram);
|
|
|
1459 }
|
|
|
1460 else
|
|
|
1461 {
|
|
|
1462 gcov_type size;
|
|
|
1463 size = ((histogram->hvalue.counters[0]
|
|
|
1464 + histogram->hvalue.counters[1] / 2)
|
|
|
1465 / histogram->hvalue.counters[1]);
|
|
|
1466 /* Even if we can hold bigger value in SIZE, INT_MAX
|
|
|
1467 is safe "infinity" for code generation strategies. */
|
|
|
1468 if (size > INT_MAX)
|
|
|
1469 size = INT_MAX;
|
|
|
1470 *expected_size = size;
|
|
|
1471 gimple_remove_histogram_value (cfun, stmt, histogram);
|
|
|
1472 }
|
|
|
1473 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_IOR);
|
|
|
1474 if (!histogram)
|
|
|
1475 *expected_align = 0;
|
|
|
1476 else if (!histogram->hvalue.counters[0])
|
|
|
1477 {
|
|
|
1478 gimple_remove_histogram_value (cfun, stmt, histogram);
|
|
|
1479 *expected_align = 0;
|
|
|
1480 }
|
|
|
1481 else
|
|
|
1482 {
|
|
|
1483 gcov_type count;
|
|
|
1484 int alignment;
|
|
|
1485
|
|
|
1486 count = histogram->hvalue.counters[0];
|
|
|
1487 alignment = 1;
|
|
|
1488 while (!(count & alignment)
|
|
|
1489 && (alignment * 2 * BITS_PER_UNIT))
|
|
|
1490 alignment <<= 1;
|
|
|
1491 *expected_align = alignment * BITS_PER_UNIT;
|
|
|
1492 gimple_remove_histogram_value (cfun, stmt, histogram);
|
|
|
1493 }
|
|
|
1494 }
|
|
|
1495
|
|
|
1496 struct value_prof_hooks {
|
|
|
1497 /* Find list of values for which we want to measure histograms. */
|
|
|
1498 void (*find_values_to_profile) (histogram_values *);
|
|
|
1499
|
|
|
1500 /* Identify and exploit properties of values that are hard to analyze
|
|
|
1501 statically. See value-prof.c for more detail. */
|
|
|
1502 bool (*value_profile_transformations) (void);
|
|
|
1503 };
|
|
|
1504
|
|
|
1505 /* Find values inside STMT for that we want to measure histograms for
|
|
|
1506 division/modulo optimization. */
|
|
|
1507 static void
|
|
|
1508 gimple_divmod_values_to_profile (gimple stmt, histogram_values *values)
|
|
|
1509 {
|
|
|
1510 tree lhs, divisor, op0, type;
|
|
|
1511 histogram_value hist;
|
|
|
1512
|
|
|
1513 if (gimple_code (stmt) != GIMPLE_ASSIGN)
|
|
|
1514 return;
|
|
|
1515
|
|
|
1516 lhs = gimple_assign_lhs (stmt);
|
|
|
1517 type = TREE_TYPE (lhs);
|
|
|
1518 if (!INTEGRAL_TYPE_P (type))
|
|
|
1519 return;
|
|
|
1520
|
|
|
1521 switch (gimple_assign_rhs_code (stmt))
|
|
|
1522 {
|
|
|
1523 case TRUNC_DIV_EXPR:
|
|
|
1524 case TRUNC_MOD_EXPR:
|
|
|
1525 divisor = gimple_assign_rhs2 (stmt);
|
|
|
1526 op0 = gimple_assign_rhs1 (stmt);
|
|
|
1527
|
|
|
1528 VEC_reserve (histogram_value, heap, *values, 3);
|
|
|
1529
|
|
|
1530 if (is_gimple_reg (divisor))
|
|
|
1531 /* Check for the case where the divisor is the same value most
|
|
|
1532 of the time. */
|
|
|
1533 VEC_quick_push (histogram_value, *values,
|
|
|
1534 gimple_alloc_histogram_value (cfun,
|
|
|
1535 HIST_TYPE_SINGLE_VALUE,
|
|
|
1536 stmt, divisor));
|
|
|
1537
|
|
|
1538 /* For mod, check whether it is not often a noop (or replaceable by
|
|
|
1539 a few subtractions). */
|
|
|
1540 if (gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR
|
|
|
1541 && TYPE_UNSIGNED (type))
|
|
|
1542 {
|
|
|
1543 tree val;
|
|
|
1544 /* Check for a special case where the divisor is power of 2. */
|
|
|
1545 VEC_quick_push (histogram_value, *values,
|
|
|
1546 gimple_alloc_histogram_value (cfun, HIST_TYPE_POW2,
|
|
|
1547 stmt, divisor));
|
|
|
1548
|
|
|
1549 val = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
|
|
|
1550 hist = gimple_alloc_histogram_value (cfun, HIST_TYPE_INTERVAL,
|
|
|
1551 stmt, val);
|
|
|
1552 hist->hdata.intvl.int_start = 0;
|
|
|
1553 hist->hdata.intvl.steps = 2;
|
|
|
1554 VEC_quick_push (histogram_value, *values, hist);
|
|
|
1555 }
|
|
|
1556 return;
|
|
|
1557
|
|
|
1558 default:
|
|
|
1559 return;
|
|
|
1560 }
|
|
|
1561 }
|
|
|
1562
|
|
|
1563 /* Find calls inside STMT for that we want to measure histograms for
|
|
|
1564 indirect/virtual call optimization. */
|
|
|
1565
|
|
|
1566 static void
|
|
|
1567 gimple_indirect_call_to_profile (gimple stmt, histogram_values *values)
|
|
|
1568 {
|
|
|
1569 tree callee;
|
|
|
1570
|
|
|
1571 if (gimple_code (stmt) != GIMPLE_CALL
|
|
|
1572 || gimple_call_fndecl (stmt) != NULL_TREE)
|
|
|
1573 return;
|
|
|
1574
|
|
|
1575 callee = gimple_call_fn (stmt);
|
|
|
1576
|
|
|
1577 VEC_reserve (histogram_value, heap, *values, 3);
|
|
|
1578
|
|
|
1579 VEC_quick_push (histogram_value, *values,
|
|
|
1580 gimple_alloc_histogram_value (cfun, HIST_TYPE_INDIR_CALL,
|
|
|
1581 stmt, callee));
|
|
|
1582
|
|
|
1583 return;
|
|
|
1584 }
|
|
|
1585
|
|
|
1586 /* Find values inside STMT for that we want to measure histograms for
|
|
|
1587 string operations. */
|
|
|
1588 static void
|
|
|
1589 gimple_stringops_values_to_profile (gimple stmt, histogram_values *values)
|
|
|
1590 {
|
|
|
1591 tree fndecl;
|
|
|
1592 tree blck_size;
|
|
|
1593 tree dest;
|
|
|
1594 enum built_in_function fcode;
|
|
|
1595
|
|
|
1596 if (gimple_code (stmt) != GIMPLE_CALL)
|
|
|
1597 return;
|
|
|
1598 fndecl = gimple_call_fndecl (stmt);
|
|
|
1599 if (!fndecl)
|
|
|
1600 return;
|
|
|
1601 fcode = DECL_FUNCTION_CODE (fndecl);
|
|
|
1602
|
|
|
1603 if (!interesting_stringop_to_profile_p (fndecl, stmt))
|
|
|
1604 return;
|
|
|
1605
|
|
|
1606 dest = gimple_call_arg (stmt, 0);
|
|
|
1607 if (fcode == BUILT_IN_BZERO)
|
|
|
1608 blck_size = gimple_call_arg (stmt, 1);
|
|
|
1609 else
|
|
|
1610 blck_size = gimple_call_arg (stmt, 2);
|
|
|
1611
|
|
|
1612 if (TREE_CODE (blck_size) != INTEGER_CST)
|
|
|
1613 {
|
|
|
1614 VEC_safe_push (histogram_value, heap, *values,
|
|
|
1615 gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE,
|
|
|
1616 stmt, blck_size));
|
|
|
1617 VEC_safe_push (histogram_value, heap, *values,
|
|
|
1618 gimple_alloc_histogram_value (cfun, HIST_TYPE_AVERAGE,
|
|
|
1619 stmt, blck_size));
|
|
|
1620 }
|
|
|
1621 if (TREE_CODE (blck_size) != INTEGER_CST)
|
|
|
1622 VEC_safe_push (histogram_value, heap, *values,
|
|
|
1623 gimple_alloc_histogram_value (cfun, HIST_TYPE_IOR,
|
|
|
1624 stmt, dest));
|
|
|
1625 }
|
|
|
1626
|
|
|
1627 /* Find values inside STMT for that we want to measure histograms and adds
|
|
|
1628 them to list VALUES. */
|
|
|
1629
|
|
|
1630 static void
|
|
|
1631 gimple_values_to_profile (gimple stmt, histogram_values *values)
|
|
|
1632 {
|
|
|
1633 if (flag_value_profile_transformations)
|
|
|
1634 {
|
|
|
1635 gimple_divmod_values_to_profile (stmt, values);
|
|
|
1636 gimple_stringops_values_to_profile (stmt, values);
|
|
|
1637 gimple_indirect_call_to_profile (stmt, values);
|
|
|
1638 }
|
|
|
1639 }
|
|
|
1640
|
|
|
1641 static void
|
|
|
1642 gimple_find_values_to_profile (histogram_values *values)
|
|
|
1643 {
|
|
|
1644 basic_block bb;
|
|
|
1645 gimple_stmt_iterator gsi;
|
|
|
1646 unsigned i;
|
|
|
1647 histogram_value hist = NULL;
|
|
|
1648
|
|
|
1649 *values = NULL;
|
|
|
1650 FOR_EACH_BB (bb)
|
|
|
1651 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
1652 gimple_values_to_profile (gsi_stmt (gsi), values);
|
|
|
1653
|
|
|
1654 for (i = 0; VEC_iterate (histogram_value, *values, i, hist); i++)
|
|
|
1655 {
|
|
|
1656 switch (hist->type)
|
|
|
1657 {
|
|
|
1658 case HIST_TYPE_INTERVAL:
|
|
|
1659 hist->n_counters = hist->hdata.intvl.steps + 2;
|
|
|
1660 break;
|
|
|
1661
|
|
|
1662 case HIST_TYPE_POW2:
|
|
|
1663 hist->n_counters = 2;
|
|
|
1664 break;
|
|
|
1665
|
|
|
1666 case HIST_TYPE_SINGLE_VALUE:
|
|
|
1667 hist->n_counters = 3;
|
|
|
1668 break;
|
|
|
1669
|
|
|
1670 case HIST_TYPE_CONST_DELTA:
|
|
|
1671 hist->n_counters = 4;
|
|
|
1672 break;
|
|
|
1673
|
|
|
1674 case HIST_TYPE_INDIR_CALL:
|
|
|
1675 hist->n_counters = 3;
|
|
|
1676 break;
|
|
|
1677
|
|
|
1678 case HIST_TYPE_AVERAGE:
|
|
|
1679 hist->n_counters = 2;
|
|
|
1680 break;
|
|
|
1681
|
|
|
1682 case HIST_TYPE_IOR:
|
|
|
1683 hist->n_counters = 1;
|
|
|
1684 break;
|
|
|
1685
|
|
|
1686 default:
|
|
|
1687 gcc_unreachable ();
|
|
|
1688 }
|
|
|
1689 if (dump_file)
|
|
|
1690 {
|
|
|
1691 fprintf (dump_file, "Stmt ");
|
|
|
1692 print_gimple_stmt (dump_file, hist->hvalue.stmt, 0, TDF_SLIM);
|
|
|
1693 dump_histogram_value (dump_file, hist);
|
|
|
1694 }
|
|
|
1695 }
|
|
|
1696 }
|
|
|
1697
|
|
|
1698 static struct value_prof_hooks gimple_value_prof_hooks = {
|
|
|
1699 gimple_find_values_to_profile,
|
|
|
1700 gimple_value_profile_transformations
|
|
|
1701 };
|
|
|
1702
|
|
|
1703 void
|
|
|
1704 gimple_register_value_prof_hooks (void)
|
|
|
1705 {
|
|
|
1706 gcc_assert (current_ir_type () == IR_GIMPLE);
|
|
|
1707 value_prof_hooks = &gimple_value_prof_hooks;
|
|
|
1708 }
|
|
|
1709
|
|
|
1710 /* IR-independent entry points. */
|
|
|
1711 void
|
|
|
1712 find_values_to_profile (histogram_values *values)
|
|
|
1713 {
|
|
|
1714 (value_prof_hooks->find_values_to_profile) (values);
|
|
|
1715 }
|
|
|
1716
|
|
|
1717 bool
|
|
|
1718 value_profile_transformations (void)
|
|
|
1719 {
|
|
|
1720 return (value_prof_hooks->value_profile_transformations) ();
|
|
|
1721 }
|
|
|
1722
|
