1 /* Transformations based on profile information for values.
2 Copyright (C) 2003-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
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
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
27 #include "hard-reg-set.h"
28 #include "basic-block.h"
29 #include "value-prof.h"
31 #include "insn-config.h"
37 #include "gimple-ssa.h"
39 #include "tree-phinodes.h"
40 #include "ssa-iterators.h"
41 #include "tree-ssanames.h"
42 #include "diagnostic.h"
43 #include "gimple-pretty-print.h"
49 #include "pointer-set.h"
51 #include "data-streamer.h"
53 /* In this file value profile based optimizations are placed. Currently the
54 following optimizations are implemented (for more detailed descriptions
55 see comments at value_profile_transformations):
57 1) Division/modulo specialization. Provided that we can determine that the
58 operands of the division have some special properties, we may use it to
59 produce more effective code.
61 2) Indirect/virtual call specialization. If we can determine most
62 common function callee in indirect/virtual call. We can use this
63 information to improve code effectiveness (especially info for
66 3) Speculative prefetching. If we are able to determine that the difference
67 between addresses accessed by a memory reference is usually constant, we
68 may add the prefetch instructions.
69 FIXME: This transformation was removed together with RTL based value
73 Value profiling internals
74 ==========================
76 Every value profiling transformation starts with defining what values
77 to profile. There are different histogram types (see HIST_TYPE_* in
78 value-prof.h) and each transformation can request one or more histogram
79 types per GIMPLE statement. The function gimple_find_values_to_profile()
80 collects the values to profile in a vec, and adds the number of counters
81 required for the different histogram types.
83 For a -fprofile-generate run, the statements for which values should be
84 recorded, are instrumented in instrument_values(). The instrumentation
85 is done by helper functions that can be found in tree-profile.c, where
86 new types of histograms can be added if necessary.
88 After a -fprofile-use, the value profiling data is read back in by
89 compute_value_histograms() that translates the collected data to
90 histograms and attaches them to the profiled statements via
91 gimple_add_histogram_value(). Histograms are stored in a hash table
92 that is attached to every intrumented function, see VALUE_HISTOGRAMS
95 The value-profile transformations driver is the function
96 gimple_value_profile_transformations(). It traverses all statements in
97 the to-be-transformed function, and looks for statements with one or
98 more histograms attached to it. If a statement has histograms, the
99 transformation functions are called on the statement.
101 Limitations / FIXME / TODO:
102 * Only one histogram of each type can be associated with a statement.
103 * Currently, HIST_TYPE_CONST_DELTA is not implemented.
104 (This type of histogram was originally used to implement a form of
105 stride profiling based speculative prefetching to improve SPEC2000
106 scores for memory-bound benchmarks, mcf and equake. However, this
107 was an RTL value-profiling transformation, and those have all been
109 * Some value profile transformations are done in builtins.c (?!)
110 * Updating of histograms needs some TLC.
111 * The value profiling code could be used to record analysis results
112 from non-profiling (e.g. VRP).
113 * Adding new profilers should be simplified, starting with a cleanup
114 of what-happens-where andwith making gimple_find_values_to_profile
115 and gimple_value_profile_transformations table-driven, perhaps...
118 static tree
gimple_divmod_fixed_value (gimple
, tree
, int, gcov_type
, gcov_type
);
119 static tree
gimple_mod_pow2 (gimple
, int, gcov_type
, gcov_type
);
120 static tree
gimple_mod_subtract (gimple
, int, int, int, gcov_type
, gcov_type
,
122 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*);
123 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator
*);
124 static bool gimple_mod_subtract_transform (gimple_stmt_iterator
*);
125 static bool gimple_stringops_transform (gimple_stmt_iterator
*);
126 static bool gimple_ic_transform (gimple_stmt_iterator
*);
128 /* Allocate histogram value. */
130 static histogram_value
131 gimple_alloc_histogram_value (struct function
*fun ATTRIBUTE_UNUSED
,
132 enum hist_type type
, gimple stmt
, tree value
)
134 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
135 hist
->hvalue
.value
= value
;
136 hist
->hvalue
.stmt
= stmt
;
141 /* Hash value for histogram. */
144 histogram_hash (const void *x
)
146 return htab_hash_pointer (((const_histogram_value
)x
)->hvalue
.stmt
);
149 /* Return nonzero if statement for histogram_value X is Y. */
152 histogram_eq (const void *x
, const void *y
)
154 return ((const_histogram_value
) x
)->hvalue
.stmt
== (const_gimple
) y
;
157 /* Set histogram for STMT. */
160 set_histogram_value (struct function
*fun
, gimple stmt
, histogram_value hist
)
163 if (!hist
&& !VALUE_HISTOGRAMS (fun
))
165 if (!VALUE_HISTOGRAMS (fun
))
166 VALUE_HISTOGRAMS (fun
) = htab_create (1, histogram_hash
,
168 loc
= htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
169 htab_hash_pointer (stmt
),
170 hist
? INSERT
: NO_INSERT
);
174 htab_clear_slot (VALUE_HISTOGRAMS (fun
), loc
);
180 /* Get histogram list for STMT. */
183 gimple_histogram_value (struct function
*fun
, gimple stmt
)
185 if (!VALUE_HISTOGRAMS (fun
))
187 return (histogram_value
) htab_find_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
188 htab_hash_pointer (stmt
));
191 /* Add histogram for STMT. */
194 gimple_add_histogram_value (struct function
*fun
, gimple stmt
,
195 histogram_value hist
)
197 hist
->hvalue
.next
= gimple_histogram_value (fun
, stmt
);
198 set_histogram_value (fun
, stmt
, hist
);
203 /* Remove histogram HIST from STMT's histogram list. */
206 gimple_remove_histogram_value (struct function
*fun
, gimple stmt
,
207 histogram_value hist
)
209 histogram_value hist2
= gimple_histogram_value (fun
, stmt
);
212 set_histogram_value (fun
, stmt
, hist
->hvalue
.next
);
216 while (hist2
->hvalue
.next
!= hist
)
217 hist2
= hist2
->hvalue
.next
;
218 hist2
->hvalue
.next
= hist
->hvalue
.next
;
220 free (hist
->hvalue
.counters
);
221 #ifdef ENABLE_CHECKING
222 memset (hist
, 0xab, sizeof (*hist
));
228 /* Lookup histogram of type TYPE in the STMT. */
231 gimple_histogram_value_of_type (struct function
*fun
, gimple stmt
,
234 histogram_value hist
;
235 for (hist
= gimple_histogram_value (fun
, stmt
); hist
;
236 hist
= hist
->hvalue
.next
)
237 if (hist
->type
== type
)
242 /* Dump information about HIST to DUMP_FILE. */
245 dump_histogram_value (FILE *dump_file
, histogram_value hist
)
249 case HIST_TYPE_INTERVAL
:
250 fprintf (dump_file
, "Interval counter range %d -- %d",
251 hist
->hdata
.intvl
.int_start
,
252 (hist
->hdata
.intvl
.int_start
253 + hist
->hdata
.intvl
.steps
- 1));
254 if (hist
->hvalue
.counters
)
257 fprintf (dump_file
, " [");
258 for (i
= 0; i
< hist
->hdata
.intvl
.steps
; i
++)
259 fprintf (dump_file
, " %d:"HOST_WIDEST_INT_PRINT_DEC
,
260 hist
->hdata
.intvl
.int_start
+ i
,
261 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[i
]);
262 fprintf (dump_file
, " ] outside range:"HOST_WIDEST_INT_PRINT_DEC
,
263 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[i
]);
265 fprintf (dump_file
, ".\n");
269 fprintf (dump_file
, "Pow2 counter ");
270 if (hist
->hvalue
.counters
)
272 fprintf (dump_file
, "pow2:"HOST_WIDEST_INT_PRINT_DEC
273 " nonpow2:"HOST_WIDEST_INT_PRINT_DEC
,
274 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
275 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1]);
277 fprintf (dump_file
, ".\n");
280 case HIST_TYPE_SINGLE_VALUE
:
281 fprintf (dump_file
, "Single value ");
282 if (hist
->hvalue
.counters
)
284 fprintf (dump_file
, "value:"HOST_WIDEST_INT_PRINT_DEC
285 " match:"HOST_WIDEST_INT_PRINT_DEC
286 " wrong:"HOST_WIDEST_INT_PRINT_DEC
,
287 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
288 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1],
289 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[2]);
291 fprintf (dump_file
, ".\n");
294 case HIST_TYPE_AVERAGE
:
295 fprintf (dump_file
, "Average value ");
296 if (hist
->hvalue
.counters
)
298 fprintf (dump_file
, "sum:"HOST_WIDEST_INT_PRINT_DEC
299 " times:"HOST_WIDEST_INT_PRINT_DEC
,
300 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
301 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1]);
303 fprintf (dump_file
, ".\n");
307 fprintf (dump_file
, "IOR value ");
308 if (hist
->hvalue
.counters
)
310 fprintf (dump_file
, "ior:"HOST_WIDEST_INT_PRINT_DEC
,
311 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0]);
313 fprintf (dump_file
, ".\n");
316 case HIST_TYPE_CONST_DELTA
:
317 fprintf (dump_file
, "Constant delta ");
318 if (hist
->hvalue
.counters
)
320 fprintf (dump_file
, "value:"HOST_WIDEST_INT_PRINT_DEC
321 " match:"HOST_WIDEST_INT_PRINT_DEC
322 " wrong:"HOST_WIDEST_INT_PRINT_DEC
,
323 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
324 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1],
325 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[2]);
327 fprintf (dump_file
, ".\n");
329 case HIST_TYPE_INDIR_CALL
:
330 fprintf (dump_file
, "Indirect call ");
331 if (hist
->hvalue
.counters
)
333 fprintf (dump_file
, "value:"HOST_WIDEST_INT_PRINT_DEC
334 " match:"HOST_WIDEST_INT_PRINT_DEC
335 " all:"HOST_WIDEST_INT_PRINT_DEC
,
336 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
337 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1],
338 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[2]);
340 fprintf (dump_file
, ".\n");
342 case HIST_TYPE_TIME_PROFILE
:
343 fprintf (dump_file
, "Time profile ");
344 if (hist
->hvalue
.counters
)
346 fprintf (dump_file
, "time:"HOST_WIDEST_INT_PRINT_DEC
,
347 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0]);
349 fprintf (dump_file
, ".\n");
356 /* Dump information about HIST to DUMP_FILE. */
359 stream_out_histogram_value (struct output_block
*ob
, histogram_value hist
)
364 bp
= bitpack_create (ob
->main_stream
);
365 bp_pack_enum (&bp
, hist_type
, HIST_TYPE_MAX
, hist
->type
);
366 bp_pack_value (&bp
, hist
->hvalue
.next
!= NULL
, 1);
367 streamer_write_bitpack (&bp
);
370 case HIST_TYPE_INTERVAL
:
371 streamer_write_hwi (ob
, hist
->hdata
.intvl
.int_start
);
372 streamer_write_uhwi (ob
, hist
->hdata
.intvl
.steps
);
377 for (i
= 0; i
< hist
->n_counters
; i
++)
378 streamer_write_gcov_count (ob
, hist
->hvalue
.counters
[i
]);
379 if (hist
->hvalue
.next
)
380 stream_out_histogram_value (ob
, hist
->hvalue
.next
);
382 /* Dump information about HIST to DUMP_FILE. */
385 stream_in_histogram_value (struct lto_input_block
*ib
, gimple stmt
)
388 unsigned int ncounters
= 0;
391 histogram_value new_val
;
393 histogram_value
*next_p
= NULL
;
397 bp
= streamer_read_bitpack (ib
);
398 type
= bp_unpack_enum (&bp
, hist_type
, HIST_TYPE_MAX
);
399 next
= bp_unpack_value (&bp
, 1);
400 new_val
= gimple_alloc_histogram_value (cfun
, type
, stmt
, NULL
);
403 case HIST_TYPE_INTERVAL
:
404 new_val
->hdata
.intvl
.int_start
= streamer_read_hwi (ib
);
405 new_val
->hdata
.intvl
.steps
= streamer_read_uhwi (ib
);
406 ncounters
= new_val
->hdata
.intvl
.steps
+ 2;
410 case HIST_TYPE_AVERAGE
:
414 case HIST_TYPE_SINGLE_VALUE
:
415 case HIST_TYPE_INDIR_CALL
:
419 case HIST_TYPE_CONST_DELTA
:
424 case HIST_TYPE_TIME_PROFILE
:
430 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * ncounters
);
431 new_val
->n_counters
= ncounters
;
432 for (i
= 0; i
< ncounters
; i
++)
433 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
435 gimple_add_histogram_value (cfun
, stmt
, new_val
);
438 next_p
= &new_val
->hvalue
.next
;
443 /* Dump all histograms attached to STMT to DUMP_FILE. */
446 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple stmt
)
448 histogram_value hist
;
449 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
450 dump_histogram_value (dump_file
, hist
);
453 /* Remove all histograms associated with STMT. */
456 gimple_remove_stmt_histograms (struct function
*fun
, gimple stmt
)
459 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
460 gimple_remove_histogram_value (fun
, stmt
, val
);
463 /* Duplicate all histograms associates with OSTMT to STMT. */
466 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple stmt
,
467 struct function
*ofun
, gimple ostmt
)
470 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
472 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
, NULL
, NULL
);
473 memcpy (new_val
, val
, sizeof (*val
));
474 new_val
->hvalue
.stmt
= stmt
;
475 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
476 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
477 gimple_add_histogram_value (fun
, stmt
, new_val
);
482 /* Move all histograms associated with OSTMT to STMT. */
485 gimple_move_stmt_histograms (struct function
*fun
, gimple stmt
, gimple ostmt
)
487 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
490 /* The following three statements can't be reordered,
491 because histogram hashtab relies on stmt field value
492 for finding the exact slot. */
493 set_histogram_value (fun
, ostmt
, NULL
);
494 for (; val
!= NULL
; val
= val
->hvalue
.next
)
495 val
->hvalue
.stmt
= stmt
;
496 set_histogram_value (fun
, stmt
, val
);
500 static bool error_found
= false;
502 /* Helper function for verify_histograms. For each histogram reachable via htab
503 walk verify that it was reached via statement walk. */
506 visit_hist (void **slot
, void *data
)
508 struct pointer_set_t
*visited
= (struct pointer_set_t
*) data
;
509 histogram_value hist
= *(histogram_value
*) slot
;
511 if (!pointer_set_contains (visited
, hist
)
512 && hist
->type
!= HIST_TYPE_TIME_PROFILE
)
514 error ("dead histogram");
515 dump_histogram_value (stderr
, hist
);
516 debug_gimple_stmt (hist
->hvalue
.stmt
);
523 /* Verify sanity of the histograms. */
526 verify_histograms (void)
529 gimple_stmt_iterator gsi
;
530 histogram_value hist
;
531 struct pointer_set_t
*visited_hists
;
534 visited_hists
= pointer_set_create ();
536 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
538 gimple stmt
= gsi_stmt (gsi
);
540 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
541 hist
= hist
->hvalue
.next
)
543 if (hist
->hvalue
.stmt
!= stmt
)
545 error ("Histogram value statement does not correspond to "
546 "the statement it is associated with");
547 debug_gimple_stmt (stmt
);
548 dump_histogram_value (stderr
, hist
);
551 pointer_set_insert (visited_hists
, hist
);
554 if (VALUE_HISTOGRAMS (cfun
))
555 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, visited_hists
);
556 pointer_set_destroy (visited_hists
);
558 internal_error ("verify_histograms failed");
561 /* Helper function for verify_histograms. For each histogram reachable via htab
562 walk verify that it was reached via statement walk. */
565 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
567 histogram_value hist
= *(histogram_value
*) slot
;
568 free (hist
->hvalue
.counters
);
569 #ifdef ENABLE_CHECKING
570 memset (hist
, 0xab, sizeof (*hist
));
577 free_histograms (void)
579 if (VALUE_HISTOGRAMS (cfun
))
581 htab_traverse (VALUE_HISTOGRAMS (cfun
), free_hist
, NULL
);
582 htab_delete (VALUE_HISTOGRAMS (cfun
));
583 VALUE_HISTOGRAMS (cfun
) = NULL
;
588 /* The overall number of invocations of the counter should match
589 execution count of basic block. Report it as error rather than
590 internal error as it might mean that user has misused the profile
594 check_counter (gimple stmt
, const char * name
,
595 gcov_type
*count
, gcov_type
*all
, gcov_type bb_count
)
597 if (*all
!= bb_count
|| *count
> *all
)
600 locus
= (stmt
!= NULL
)
601 ? gimple_location (stmt
)
602 : DECL_SOURCE_LOCATION (current_function_decl
);
603 if (flag_profile_correction
)
605 if (dump_enabled_p ())
606 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
607 "correcting inconsistent value profile: %s "
608 "profiler overall count (%d) does not match BB "
609 "count (%d)\n", name
, (int)*all
, (int)bb_count
);
617 error_at (locus
, "corrupted value profile: %s "
618 "profile counter (%d out of %d) inconsistent with "
619 "basic-block count (%d)",
632 /* GIMPLE based transformations. */
635 gimple_value_profile_transformations (void)
638 gimple_stmt_iterator gsi
;
639 bool changed
= false;
643 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
645 gimple stmt
= gsi_stmt (gsi
);
646 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
652 fprintf (dump_file
, "Trying transformations on stmt ");
653 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
654 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
657 /* Transformations: */
658 /* The order of things in this conditional controls which
659 transformation is used when more than one is applicable. */
660 /* It is expected that any code added by the transformations
661 will be added before the current statement, and that the
662 current statement remain valid (although possibly
663 modified) upon return. */
664 if (gimple_mod_subtract_transform (&gsi
)
665 || gimple_divmod_fixed_value_transform (&gsi
)
666 || gimple_mod_pow2_value_transform (&gsi
)
667 || gimple_stringops_transform (&gsi
)
668 || gimple_ic_transform (&gsi
))
670 stmt
= gsi_stmt (gsi
);
672 /* Original statement may no longer be in the same block. */
673 if (bb
!= gimple_bb (stmt
))
675 bb
= gimple_bb (stmt
);
676 gsi
= gsi_for_stmt (stmt
);
691 /* Generate code for transformation 1 (with parent gimple assignment
692 STMT and probability of taking the optimal path PROB, which is
693 equivalent to COUNT/ALL within roundoff error). This generates the
694 result into a temp and returns the temp; it does not replace or
695 alter the original STMT. */
698 gimple_divmod_fixed_value (gimple stmt
, tree value
, int prob
, gcov_type count
,
701 gimple stmt1
, stmt2
, stmt3
;
702 tree tmp0
, tmp1
, tmp2
;
703 gimple bb1end
, bb2end
, bb3end
;
704 basic_block bb
, bb2
, bb3
, bb4
;
705 tree optype
, op1
, op2
;
706 edge e12
, e13
, e23
, e24
, e34
;
707 gimple_stmt_iterator gsi
;
709 gcc_assert (is_gimple_assign (stmt
)
710 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
711 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
713 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
714 op1
= gimple_assign_rhs1 (stmt
);
715 op2
= gimple_assign_rhs2 (stmt
);
717 bb
= gimple_bb (stmt
);
718 gsi
= gsi_for_stmt (stmt
);
720 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
721 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
722 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
723 stmt2
= gimple_build_assign (tmp1
, op2
);
724 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
725 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
726 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
727 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
730 tmp2
= create_tmp_reg (optype
, "PROF");
731 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
733 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
736 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
738 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
742 /* Edge e23 connects bb2 to bb3, etc. */
743 e12
= split_block (bb
, bb1end
);
746 e23
= split_block (bb2
, bb2end
);
748 bb3
->count
= all
- count
;
749 e34
= split_block (bb3
, bb3end
);
753 e12
->flags
&= ~EDGE_FALLTHRU
;
754 e12
->flags
|= EDGE_FALSE_VALUE
;
755 e12
->probability
= prob
;
758 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
759 e13
->probability
= REG_BR_PROB_BASE
- prob
;
760 e13
->count
= all
- count
;
764 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
765 e24
->probability
= REG_BR_PROB_BASE
;
768 e34
->probability
= REG_BR_PROB_BASE
;
769 e34
->count
= all
- count
;
775 /* Do transform 1) on INSN if applicable. */
778 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
780 histogram_value histogram
;
782 gcov_type val
, count
, all
;
783 tree result
, value
, tree_val
;
787 stmt
= gsi_stmt (*si
);
788 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
791 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
794 code
= gimple_assign_rhs_code (stmt
);
796 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
799 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
800 HIST_TYPE_SINGLE_VALUE
);
804 value
= histogram
->hvalue
.value
;
805 val
= histogram
->hvalue
.counters
[0];
806 count
= histogram
->hvalue
.counters
[1];
807 all
= histogram
->hvalue
.counters
[2];
808 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
810 /* We require that count is at least half of all; this means
811 that for the transformation to fire the value must be constant
812 at least 50% of time (and 75% gives the guarantee of usage). */
813 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
815 || optimize_bb_for_size_p (gimple_bb (stmt
)))
818 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
821 /* Compute probability of taking the optimal path. */
823 prob
= GCOV_COMPUTE_SCALE (count
, all
);
827 tree_val
= build_int_cst_wide (get_gcov_type (),
828 (unsigned HOST_WIDE_INT
) val
,
829 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
830 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
834 fprintf (dump_file
, "Div/mod by constant ");
835 print_generic_expr (dump_file
, value
, TDF_SLIM
);
836 fprintf (dump_file
, "=");
837 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
838 fprintf (dump_file
, " transformation on insn ");
839 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
842 gimple_assign_set_rhs_from_tree (si
, result
);
843 update_stmt (gsi_stmt (*si
));
848 /* Generate code for transformation 2 (with parent gimple assign STMT and
849 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
850 within roundoff error). This generates the result into a temp and returns
851 the temp; it does not replace or alter the original STMT. */
853 gimple_mod_pow2 (gimple stmt
, int prob
, gcov_type count
, gcov_type all
)
855 gimple stmt1
, stmt2
, stmt3
, stmt4
;
857 gimple bb1end
, bb2end
, bb3end
;
858 basic_block bb
, bb2
, bb3
, bb4
;
859 tree optype
, op1
, op2
;
860 edge e12
, e13
, e23
, e24
, e34
;
861 gimple_stmt_iterator gsi
;
864 gcc_assert (is_gimple_assign (stmt
)
865 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
867 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
868 op1
= gimple_assign_rhs1 (stmt
);
869 op2
= gimple_assign_rhs2 (stmt
);
871 bb
= gimple_bb (stmt
);
872 gsi
= gsi_for_stmt (stmt
);
874 result
= create_tmp_reg (optype
, "PROF");
875 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
876 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
877 stmt2
= gimple_build_assign_with_ops (PLUS_EXPR
, tmp2
, op2
,
878 build_int_cst (optype
, -1));
879 stmt3
= gimple_build_assign_with_ops (BIT_AND_EXPR
, tmp3
, tmp2
, op2
);
880 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
881 NULL_TREE
, NULL_TREE
);
882 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
883 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
884 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
887 /* tmp2 == op2-1 inherited from previous block. */
888 stmt1
= gimple_build_assign_with_ops (BIT_AND_EXPR
, result
, op1
, tmp2
);
889 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
892 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
894 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
898 /* Edge e23 connects bb2 to bb3, etc. */
899 e12
= split_block (bb
, bb1end
);
902 e23
= split_block (bb2
, bb2end
);
904 bb3
->count
= all
- count
;
905 e34
= split_block (bb3
, bb3end
);
909 e12
->flags
&= ~EDGE_FALLTHRU
;
910 e12
->flags
|= EDGE_FALSE_VALUE
;
911 e12
->probability
= prob
;
914 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
915 e13
->probability
= REG_BR_PROB_BASE
- prob
;
916 e13
->count
= all
- count
;
920 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
921 e24
->probability
= REG_BR_PROB_BASE
;
924 e34
->probability
= REG_BR_PROB_BASE
;
925 e34
->count
= all
- count
;
930 /* Do transform 2) on INSN if applicable. */
932 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
934 histogram_value histogram
;
936 gcov_type count
, wrong_values
, all
;
937 tree lhs_type
, result
, value
;
941 stmt
= gsi_stmt (*si
);
942 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
945 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
946 if (!INTEGRAL_TYPE_P (lhs_type
))
949 code
= gimple_assign_rhs_code (stmt
);
951 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
954 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
958 value
= histogram
->hvalue
.value
;
959 wrong_values
= histogram
->hvalue
.counters
[0];
960 count
= histogram
->hvalue
.counters
[1];
962 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
964 /* We require that we hit a power of 2 at least half of all evaluations. */
965 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
966 || count
< wrong_values
967 || optimize_bb_for_size_p (gimple_bb (stmt
)))
972 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
973 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
976 /* Compute probability of taking the optimal path. */
977 all
= count
+ wrong_values
;
979 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
983 prob
= GCOV_COMPUTE_SCALE (count
, all
);
987 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
989 gimple_assign_set_rhs_from_tree (si
, result
);
990 update_stmt (gsi_stmt (*si
));
995 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
996 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
997 supported and this is built into this interface. The probabilities of taking
998 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
999 COUNT2/ALL respectively within roundoff error). This generates the
1000 result into a temp and returns the temp; it does not replace or alter
1001 the original STMT. */
1002 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
1005 gimple_mod_subtract (gimple stmt
, int prob1
, int prob2
, int ncounts
,
1006 gcov_type count1
, gcov_type count2
, gcov_type all
)
1008 gimple stmt1
, stmt2
, stmt3
;
1010 gimple bb1end
, bb2end
= NULL
, bb3end
;
1011 basic_block bb
, bb2
, bb3
, bb4
;
1012 tree optype
, op1
, op2
;
1013 edge e12
, e23
= 0, e24
, e34
, e14
;
1014 gimple_stmt_iterator gsi
;
1017 gcc_assert (is_gimple_assign (stmt
)
1018 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1020 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1021 op1
= gimple_assign_rhs1 (stmt
);
1022 op2
= gimple_assign_rhs2 (stmt
);
1024 bb
= gimple_bb (stmt
);
1025 gsi
= gsi_for_stmt (stmt
);
1027 result
= create_tmp_reg (optype
, "PROF");
1028 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1029 stmt1
= gimple_build_assign (result
, op1
);
1030 stmt2
= gimple_build_assign (tmp1
, op2
);
1031 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1032 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1033 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1034 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1037 if (ncounts
) /* Assumed to be 0 or 1 */
1039 stmt1
= gimple_build_assign_with_ops (MINUS_EXPR
, result
, result
, tmp1
);
1040 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1041 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1042 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1046 /* Fallback case. */
1047 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
1049 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1053 /* Edge e23 connects bb2 to bb3, etc. */
1054 /* However block 3 is optional; if it is not there, references
1055 to 3 really refer to block 2. */
1056 e12
= split_block (bb
, bb1end
);
1058 bb2
->count
= all
- count1
;
1060 if (ncounts
) /* Assumed to be 0 or 1. */
1062 e23
= split_block (bb2
, bb2end
);
1064 bb3
->count
= all
- count1
- count2
;
1067 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1071 e12
->flags
&= ~EDGE_FALLTHRU
;
1072 e12
->flags
|= EDGE_FALSE_VALUE
;
1073 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
1074 e12
->count
= all
- count1
;
1076 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1077 e14
->probability
= prob1
;
1078 e14
->count
= count1
;
1080 if (ncounts
) /* Assumed to be 0 or 1. */
1082 e23
->flags
&= ~EDGE_FALLTHRU
;
1083 e23
->flags
|= EDGE_FALSE_VALUE
;
1084 e23
->count
= all
- count1
- count2
;
1085 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
1087 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1088 e24
->probability
= prob2
;
1089 e24
->count
= count2
;
1092 e34
->probability
= REG_BR_PROB_BASE
;
1093 e34
->count
= all
- count1
- count2
;
1099 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1102 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1104 histogram_value histogram
;
1105 enum tree_code code
;
1106 gcov_type count
, wrong_values
, all
;
1107 tree lhs_type
, result
;
1108 gcov_type prob1
, prob2
;
1109 unsigned int i
, steps
;
1110 gcov_type count1
, count2
;
1113 stmt
= gsi_stmt (*si
);
1114 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1117 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1118 if (!INTEGRAL_TYPE_P (lhs_type
))
1121 code
= gimple_assign_rhs_code (stmt
);
1123 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1126 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1132 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1133 all
+= histogram
->hvalue
.counters
[i
];
1135 wrong_values
+= histogram
->hvalue
.counters
[i
];
1136 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1137 steps
= histogram
->hdata
.intvl
.steps
;
1138 all
+= wrong_values
;
1139 count1
= histogram
->hvalue
.counters
[0];
1140 count2
= histogram
->hvalue
.counters
[1];
1142 /* Compute probability of taking the optimal path. */
1143 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1145 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1149 if (flag_profile_correction
&& count1
+ count2
> all
)
1150 all
= count1
+ count2
;
1152 gcc_assert (count1
+ count2
<= all
);
1154 /* We require that we use just subtractions in at least 50% of all
1157 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1159 count
+= histogram
->hvalue
.counters
[i
];
1160 if (count
* 2 >= all
)
1164 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1167 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1170 fprintf (dump_file
, "Mod subtract transformation on insn ");
1171 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1174 /* Compute probability of taking the optimal path(s). */
1177 prob1
= GCOV_COMPUTE_SCALE (count1
, all
);
1178 prob2
= GCOV_COMPUTE_SCALE (count2
, all
);
1185 /* In practice, "steps" is always 2. This interface reflects this,
1186 and will need to be changed if "steps" can change. */
1187 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1189 gimple_assign_set_rhs_from_tree (si
, result
);
1190 update_stmt (gsi_stmt (*si
));
1195 static pointer_map_t
*cgraph_node_map
;
1197 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1198 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1199 that the PROFILE_IDs was already assigned. */
1202 init_node_map (bool local
)
1204 struct cgraph_node
*n
;
1205 cgraph_node_map
= pointer_map_create ();
1207 FOR_EACH_DEFINED_FUNCTION (n
)
1208 if (cgraph_function_with_gimple_body_p (n
)
1209 && !cgraph_only_called_directly_p (n
))
1214 n
->profile_id
= coverage_compute_profile_id (n
);
1215 while ((val
= pointer_map_contains (cgraph_node_map
,
1216 (void *)(size_t)n
->profile_id
))
1220 fprintf (dump_file
, "Local profile-id %i conflict"
1221 " with nodes %s/%i %s/%i\n",
1223 cgraph_node_name (n
),
1225 symtab_node_name (*(symtab_node
**)val
),
1226 (*(symtab_node
**)val
)->order
);
1227 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1230 else if (!n
->profile_id
)
1234 "Node %s/%i has no profile-id"
1235 " (profile feedback missing?)\n",
1236 cgraph_node_name (n
),
1240 else if ((val
= pointer_map_contains (cgraph_node_map
,
1241 (void *)(size_t)n
->profile_id
)))
1245 "Node %s/%i has IP profile-id %i conflict. "
1247 cgraph_node_name (n
),
1253 *pointer_map_insert (cgraph_node_map
,
1254 (void *)(size_t)n
->profile_id
) = (void *)n
;
1258 /* Delete the CGRAPH_NODE_MAP. */
1263 pointer_map_destroy (cgraph_node_map
);
1266 /* Return cgraph node for function with pid */
1269 find_func_by_profile_id (int profile_id
)
1271 void **val
= pointer_map_contains (cgraph_node_map
,
1272 (void *)(size_t)profile_id
);
1274 return (struct cgraph_node
*)*val
;
1279 /* Perform sanity check on the indirect call target. Due to race conditions,
1280 false function target may be attributed to an indirect call site. If the
1281 call expression type mismatches with the target function's type, expand_call
1282 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1283 Returns true if TARGET is considered ok for call CALL_STMT. */
1286 check_ic_target (gimple call_stmt
, struct cgraph_node
*target
)
1289 if (gimple_check_call_matching_types (call_stmt
, target
->decl
, true))
1292 locus
= gimple_location (call_stmt
);
1293 if (dump_enabled_p ())
1294 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
1295 "Skipping target %s with mismatching types for icall\n",
1296 cgraph_node_name (target
));
1300 /* Do transformation
1302 if (actual_callee_address == address_of_most_common_function/method)
1309 gimple_ic (gimple icall_stmt
, struct cgraph_node
*direct_call
,
1310 int prob
, gcov_type count
, gcov_type all
)
1312 gimple dcall_stmt
, load_stmt
, cond_stmt
;
1313 tree tmp0
, tmp1
, tmp
;
1314 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1315 tree optype
= build_pointer_type (void_type_node
);
1316 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1317 gimple_stmt_iterator gsi
;
1321 gimple_stmt_iterator psi
;
1323 cond_bb
= gimple_bb (icall_stmt
);
1324 gsi
= gsi_for_stmt (icall_stmt
);
1326 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1327 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1328 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1329 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1330 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1332 tmp
= fold_convert (optype
, build_addr (direct_call
->decl
,
1333 current_function_decl
));
1334 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1335 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1337 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1338 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1340 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1341 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1342 update_stmt (icall_stmt
);
1343 dcall_stmt
= gimple_copy (icall_stmt
);
1344 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1345 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1346 if ((dflags
& ECF_NORETURN
) != 0)
1347 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1348 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1351 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1352 e_cd
= split_block (cond_bb
, cond_stmt
);
1353 dcall_bb
= e_cd
->dest
;
1354 dcall_bb
->count
= count
;
1356 e_di
= split_block (dcall_bb
, dcall_stmt
);
1357 icall_bb
= e_di
->dest
;
1358 icall_bb
->count
= all
- count
;
1360 /* Do not disturb existing EH edges from the indirect call. */
1361 if (!stmt_ends_bb_p (icall_stmt
))
1362 e_ij
= split_block (icall_bb
, icall_stmt
);
1365 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1366 /* The indirect call might be noreturn. */
1369 e_ij
->probability
= REG_BR_PROB_BASE
;
1370 e_ij
->count
= all
- count
;
1371 e_ij
= single_pred_edge (split_edge (e_ij
));
1376 join_bb
= e_ij
->dest
;
1377 join_bb
->count
= all
;
1380 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1381 e_cd
->probability
= prob
;
1382 e_cd
->count
= count
;
1384 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1385 e_ci
->probability
= REG_BR_PROB_BASE
- prob
;
1386 e_ci
->count
= all
- count
;
1392 if ((dflags
& ECF_NORETURN
) != 0)
1396 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1397 e_dj
->probability
= REG_BR_PROB_BASE
;
1398 e_dj
->count
= count
;
1400 e_ij
->count
= all
- count
;
1402 e_ij
->probability
= REG_BR_PROB_BASE
;
1405 /* Insert PHI node for the call result if necessary. */
1406 if (gimple_call_lhs (icall_stmt
)
1407 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1408 && (dflags
& ECF_NORETURN
) == 0)
1410 tree result
= gimple_call_lhs (icall_stmt
);
1411 gimple phi
= create_phi_node (result
, join_bb
);
1412 gimple_call_set_lhs (icall_stmt
,
1413 duplicate_ssa_name (result
, icall_stmt
));
1414 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1415 gimple_call_set_lhs (dcall_stmt
,
1416 duplicate_ssa_name (result
, dcall_stmt
));
1417 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1420 /* Build an EH edge for the direct call if necessary. */
1421 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1422 if (lp_nr
> 0 && stmt_could_throw_p (dcall_stmt
))
1424 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1427 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1428 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1430 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1431 for (psi
= gsi_start_phis (e_eh
->dest
);
1432 !gsi_end_p (psi
); gsi_next (&psi
))
1434 gimple phi
= gsi_stmt (psi
);
1435 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1436 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1443 For every checked indirect/virtual call determine if most common pid of
1444 function/class method has probability more than 50%. If yes modify code of
1449 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1451 gimple stmt
= gsi_stmt (*gsi
);
1452 histogram_value histogram
;
1453 gcov_type val
, count
, all
, bb_all
;
1454 struct cgraph_node
*direct_call
;
1456 if (gimple_code (stmt
) != GIMPLE_CALL
)
1459 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1462 if (gimple_call_internal_p (stmt
))
1465 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1469 val
= histogram
->hvalue
.counters
[0];
1470 count
= histogram
->hvalue
.counters
[1];
1471 all
= histogram
->hvalue
.counters
[2];
1473 bb_all
= gimple_bb (stmt
)->count
;
1474 /* The order of CHECK_COUNTER calls is important -
1475 since check_counter can correct the third parameter
1476 and we want to make count <= all <= bb_all. */
1477 if ( check_counter (stmt
, "ic", &all
, &bb_all
, bb_all
)
1478 || check_counter (stmt
, "ic", &count
, &all
, all
))
1480 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1484 if (4 * count
<= 3 * all
)
1487 direct_call
= find_func_by_profile_id ((int)val
);
1489 if (direct_call
== NULL
)
1495 fprintf (dump_file
, "Indirect call -> direct call from other module");
1496 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1497 fprintf (dump_file
, "=> %i (will resolve only with LTO)\n", (int)val
);
1503 if (!check_ic_target (stmt
, direct_call
))
1507 fprintf (dump_file
, "Indirect call -> direct call ");
1508 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1509 fprintf (dump_file
, "=> ");
1510 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1511 fprintf (dump_file
, " transformation skipped because of type mismatch");
1512 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1514 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1520 fprintf (dump_file
, "Indirect call -> direct call ");
1521 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1522 fprintf (dump_file
, "=> ");
1523 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1524 fprintf (dump_file
, " transformation on insn postponned to ipa-profile");
1525 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1526 fprintf (dump_file
, "hist->count "HOST_WIDEST_INT_PRINT_DEC
1527 " hist->all "HOST_WIDEST_INT_PRINT_DEC
"\n", count
, all
);
1533 /* Return true if the stringop CALL with FNDECL shall be profiled.
1534 SIZE_ARG be set to the argument index for the size of the string
1538 interesting_stringop_to_profile_p (tree fndecl
, gimple call
, int *size_arg
)
1540 enum built_in_function fcode
= DECL_FUNCTION_CODE (fndecl
);
1542 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1543 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1548 case BUILT_IN_MEMCPY
:
1549 case BUILT_IN_MEMPCPY
:
1551 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1552 INTEGER_TYPE
, VOID_TYPE
);
1553 case BUILT_IN_MEMSET
:
1555 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1556 INTEGER_TYPE
, VOID_TYPE
);
1557 case BUILT_IN_BZERO
:
1559 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1566 /* Convert stringop (..., vcall_size)
1568 if (vcall_size == icall_size)
1569 stringop (..., icall_size);
1571 stringop (..., vcall_size);
1572 assuming we'll propagate a true constant into ICALL_SIZE later. */
1575 gimple_stringop_fixed_value (gimple vcall_stmt
, tree icall_size
, int prob
,
1576 gcov_type count
, gcov_type all
)
1578 gimple tmp_stmt
, cond_stmt
, icall_stmt
;
1579 tree tmp0
, tmp1
, vcall_size
, optype
;
1580 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1581 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1582 gimple_stmt_iterator gsi
;
1586 fndecl
= gimple_call_fndecl (vcall_stmt
);
1587 if (!interesting_stringop_to_profile_p (fndecl
, vcall_stmt
, &size_arg
))
1590 cond_bb
= gimple_bb (vcall_stmt
);
1591 gsi
= gsi_for_stmt (vcall_stmt
);
1593 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1594 optype
= TREE_TYPE (vcall_size
);
1596 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1597 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1598 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1599 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1601 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1602 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1604 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1605 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1607 gimple_set_vdef (vcall_stmt
, NULL
);
1608 gimple_set_vuse (vcall_stmt
, NULL
);
1609 update_stmt (vcall_stmt
);
1610 icall_stmt
= gimple_copy (vcall_stmt
);
1611 gimple_call_set_arg (icall_stmt
, size_arg
, icall_size
);
1612 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1615 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1616 e_ci
= split_block (cond_bb
, cond_stmt
);
1617 icall_bb
= e_ci
->dest
;
1618 icall_bb
->count
= count
;
1620 e_iv
= split_block (icall_bb
, icall_stmt
);
1621 vcall_bb
= e_iv
->dest
;
1622 vcall_bb
->count
= all
- count
;
1624 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1625 join_bb
= e_vj
->dest
;
1626 join_bb
->count
= all
;
1628 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1629 e_ci
->probability
= prob
;
1630 e_ci
->count
= count
;
1632 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1633 e_cv
->probability
= REG_BR_PROB_BASE
- prob
;
1634 e_cv
->count
= all
- count
;
1638 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1639 e_ij
->probability
= REG_BR_PROB_BASE
;
1640 e_ij
->count
= count
;
1642 e_vj
->probability
= REG_BR_PROB_BASE
;
1643 e_vj
->count
= all
- count
;
1645 /* Insert PHI node for the call result if necessary. */
1646 if (gimple_call_lhs (vcall_stmt
)
1647 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1649 tree result
= gimple_call_lhs (vcall_stmt
);
1650 gimple phi
= create_phi_node (result
, join_bb
);
1651 gimple_call_set_lhs (vcall_stmt
,
1652 duplicate_ssa_name (result
, vcall_stmt
));
1653 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1654 gimple_call_set_lhs (icall_stmt
,
1655 duplicate_ssa_name (result
, icall_stmt
));
1656 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1659 /* Because these are all string op builtins, they're all nothrow. */
1660 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1661 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1664 /* Find values inside STMT for that we want to measure histograms for
1665 division/modulo optimization. */
1667 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1669 gimple stmt
= gsi_stmt (*gsi
);
1672 enum built_in_function fcode
;
1673 histogram_value histogram
;
1674 gcov_type count
, all
, val
;
1676 unsigned int dest_align
, src_align
;
1681 if (gimple_code (stmt
) != GIMPLE_CALL
)
1683 fndecl
= gimple_call_fndecl (stmt
);
1686 fcode
= DECL_FUNCTION_CODE (fndecl
);
1687 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1690 blck_size
= gimple_call_arg (stmt
, size_arg
);
1691 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1694 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1697 val
= histogram
->hvalue
.counters
[0];
1698 count
= histogram
->hvalue
.counters
[1];
1699 all
= histogram
->hvalue
.counters
[2];
1700 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1701 /* We require that count is at least half of all; this means
1702 that for the transformation to fire the value must be constant
1703 at least 80% of time. */
1704 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1706 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1709 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1712 dest
= gimple_call_arg (stmt
, 0);
1713 dest_align
= get_pointer_alignment (dest
);
1716 case BUILT_IN_MEMCPY
:
1717 case BUILT_IN_MEMPCPY
:
1718 src
= gimple_call_arg (stmt
, 1);
1719 src_align
= get_pointer_alignment (src
);
1720 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1723 case BUILT_IN_MEMSET
:
1724 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1725 gimple_call_arg (stmt
, 1),
1729 case BUILT_IN_BZERO
:
1730 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1738 tree_val
= build_int_cst_wide (get_gcov_type (),
1739 (unsigned HOST_WIDE_INT
) val
,
1740 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
1743 fprintf (dump_file
, "Single value %i stringop transformation on ",
1745 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1747 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1753 stringop_block_profile (gimple stmt
, unsigned int *expected_align
,
1754 HOST_WIDE_INT
*expected_size
)
1756 histogram_value histogram
;
1757 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1759 *expected_size
= -1;
1760 else if (!histogram
->hvalue
.counters
[1])
1762 *expected_size
= -1;
1763 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1768 size
= ((histogram
->hvalue
.counters
[0]
1769 + histogram
->hvalue
.counters
[1] / 2)
1770 / histogram
->hvalue
.counters
[1]);
1771 /* Even if we can hold bigger value in SIZE, INT_MAX
1772 is safe "infinity" for code generation strategies. */
1775 *expected_size
= size
;
1776 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1778 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1780 *expected_align
= 0;
1781 else if (!histogram
->hvalue
.counters
[0])
1783 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1784 *expected_align
= 0;
1791 count
= histogram
->hvalue
.counters
[0];
1793 while (!(count
& alignment
)
1794 && (alignment
* 2 * BITS_PER_UNIT
))
1796 *expected_align
= alignment
* BITS_PER_UNIT
;
1797 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1802 /* Find values inside STMT for that we want to measure histograms for
1803 division/modulo optimization. */
1805 gimple_divmod_values_to_profile (gimple stmt
, histogram_values
*values
)
1807 tree lhs
, divisor
, op0
, type
;
1808 histogram_value hist
;
1810 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1813 lhs
= gimple_assign_lhs (stmt
);
1814 type
= TREE_TYPE (lhs
);
1815 if (!INTEGRAL_TYPE_P (type
))
1818 switch (gimple_assign_rhs_code (stmt
))
1820 case TRUNC_DIV_EXPR
:
1821 case TRUNC_MOD_EXPR
:
1822 divisor
= gimple_assign_rhs2 (stmt
);
1823 op0
= gimple_assign_rhs1 (stmt
);
1825 values
->reserve (3);
1827 if (TREE_CODE (divisor
) == SSA_NAME
)
1828 /* Check for the case where the divisor is the same value most
1830 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1831 HIST_TYPE_SINGLE_VALUE
,
1834 /* For mod, check whether it is not often a noop (or replaceable by
1835 a few subtractions). */
1836 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1837 && TYPE_UNSIGNED (type
))
1840 /* Check for a special case where the divisor is power of 2. */
1841 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1845 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1846 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1848 hist
->hdata
.intvl
.int_start
= 0;
1849 hist
->hdata
.intvl
.steps
= 2;
1850 values
->quick_push (hist
);
1859 /* Find calls inside STMT for that we want to measure histograms for
1860 indirect/virtual call optimization. */
1863 gimple_indirect_call_to_profile (gimple stmt
, histogram_values
*values
)
1867 if (gimple_code (stmt
) != GIMPLE_CALL
1868 || gimple_call_internal_p (stmt
)
1869 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1872 callee
= gimple_call_fn (stmt
);
1874 values
->reserve (3);
1876 values
->quick_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_INDIR_CALL
,
1882 /* Find values inside STMT for that we want to measure histograms for
1883 string operations. */
1885 gimple_stringops_values_to_profile (gimple stmt
, histogram_values
*values
)
1892 if (gimple_code (stmt
) != GIMPLE_CALL
)
1894 fndecl
= gimple_call_fndecl (stmt
);
1898 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1901 dest
= gimple_call_arg (stmt
, 0);
1902 blck_size
= gimple_call_arg (stmt
, size_arg
);
1904 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1906 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1907 HIST_TYPE_SINGLE_VALUE
,
1909 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1912 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1913 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1917 /* Find values inside STMT for that we want to measure histograms and adds
1918 them to list VALUES. */
1921 gimple_values_to_profile (gimple stmt
, histogram_values
*values
)
1923 gimple_divmod_values_to_profile (stmt
, values
);
1924 gimple_stringops_values_to_profile (stmt
, values
);
1925 gimple_indirect_call_to_profile (stmt
, values
);
1929 gimple_find_values_to_profile (histogram_values
*values
)
1932 gimple_stmt_iterator gsi
;
1934 histogram_value hist
= NULL
;
1938 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1939 gimple_values_to_profile (gsi_stmt (gsi
), values
);
1941 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_TIME_PROFILE
, 0, 0));
1943 FOR_EACH_VEC_ELT (*values
, i
, hist
)
1947 case HIST_TYPE_INTERVAL
:
1948 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1951 case HIST_TYPE_POW2
:
1952 hist
->n_counters
= 2;
1955 case HIST_TYPE_SINGLE_VALUE
:
1956 hist
->n_counters
= 3;
1959 case HIST_TYPE_CONST_DELTA
:
1960 hist
->n_counters
= 4;
1963 case HIST_TYPE_INDIR_CALL
:
1964 hist
->n_counters
= 3;
1967 case HIST_TYPE_TIME_PROFILE
:
1968 hist
->n_counters
= 1;
1971 case HIST_TYPE_AVERAGE
:
1972 hist
->n_counters
= 2;
1976 hist
->n_counters
= 1;
1984 fprintf (dump_file
, "Stmt ");
1985 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
1986 dump_histogram_value (dump_file
, hist
);