Line data Source code
1 : /* Calculate branch probabilities, and basic block execution counts.
2 : Copyright (C) 1990-2026 Free Software Foundation, Inc.
3 : Contributed by James E. Wilson, UC Berkeley/Cygnus Support;
4 : based on some ideas from Dain Samples of UC Berkeley.
5 : Further mangling by Bob Manson, Cygnus Support.
6 : Converted to use trees by Dale Johannesen, Apple Computer.
7 :
8 : This file is part of GCC.
9 :
10 : GCC is free software; you can redistribute it and/or modify it under
11 : the terms of the GNU General Public License as published by the Free
12 : Software Foundation; either version 3, or (at your option) any later
13 : version.
14 :
15 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 : for more details.
19 :
20 : You should have received a copy of the GNU General Public License
21 : along with GCC; see the file COPYING3. If not see
22 : <http://www.gnu.org/licenses/>. */
23 :
24 : /* Generate basic block profile instrumentation and auxiliary files.
25 : Tree-based version. See profile.cc for overview. */
26 :
27 : #include "config.h"
28 : #include "system.h"
29 : #include "coretypes.h"
30 : #include "memmodel.h"
31 : #include "backend.h"
32 : #include "target.h"
33 : #include "tree.h"
34 : #include "gimple.h"
35 : #include "cfghooks.h"
36 : #include "tree-pass.h"
37 : #include "ssa.h"
38 : #include "cgraph.h"
39 : #include "coverage.h"
40 : #include "diagnostic-core.h"
41 : #include "fold-const.h"
42 : #include "varasm.h"
43 : #include "tree-nested.h"
44 : #include "gimplify.h"
45 : #include "gimple-iterator.h"
46 : #include "gimple-fold.h"
47 : #include "gimplify-me.h"
48 : #include "tree-cfg.h"
49 : #include "tree-into-ssa.h"
50 : #include "value-prof.h"
51 : #include "profile.h"
52 : #include "tree-cfgcleanup.h"
53 : #include "stringpool.h"
54 : #include "attribs.h"
55 : #include "tree-pretty-print.h"
56 : #include "langhooks.h"
57 : #include "stor-layout.h"
58 : #include "xregex.h"
59 : #include "alloc-pool.h"
60 : #include "symbol-summary.h"
61 : #include "symtab-thunks.h"
62 : #include "cfganal.h"
63 :
64 : static GTY(()) tree gcov_type_node;
65 : static GTY(()) tree tree_interval_profiler_fn;
66 : static GTY(()) tree tree_pow2_profiler_fn;
67 : static GTY(()) tree tree_topn_values_profiler_fn;
68 : static GTY(()) tree tree_indirect_call_profiler_fn;
69 : static GTY(()) tree tree_average_profiler_fn;
70 : static GTY(()) tree tree_ior_profiler_fn;
71 : static GTY(()) tree tree_time_profiler_counter;
72 :
73 :
74 : static GTY(()) tree ic_tuple_var;
75 : static GTY(()) tree ic_tuple_counters_field;
76 : static GTY(()) tree ic_tuple_callee_field;
77 :
78 : /* Types of counter update methods.
79 :
80 : By default, the counter updates are done for a single threaded system
81 : (COUNTER_UPDATE_SINGLE_THREAD).
82 :
83 : If the user selected atomic profile counter updates
84 : (-fprofile-update=atomic), then the counter updates will be done atomically
85 : on a best-effort basis. One of three methods to do the counter updates is
86 : selected according to the target capabilities.
87 :
88 : Ideally, the counter updates are done through atomic operations in hardware
89 : (COUNTER_UPDATE_ATOMIC_BUILTIN).
90 :
91 : If the target supports only 32-bit atomic increments and gcov_type_node is a
92 : 64-bit integer type, then for the profile edge counters the increment is
93 : performed through two separate 32-bit atomic increments
94 : (COUNTER_UPDATE_ATOMIC_SPLIT or COUNTER_UPDATE_ATOMIC_PARTIAL). If the
95 : target supports libatomic (targetm.have_libatomic), then other counter
96 : updates are carried out by libatomic calls (COUNTER_UPDATE_ATOMIC_SPLIT).
97 : If the target does not support libatomic, then the other counter updates are
98 : not done atomically (COUNTER_UPDATE_ATOMIC_PARTIAL) and a warning is
99 : issued.
100 :
101 : If the target does not support atomic operations in hardware, however, it
102 : supports libatomic, then all updates are carried out by libatomic calls
103 : (COUNTER_UPDATE_ATOMIC_BUILTIN). */
104 : enum counter_update_method {
105 : COUNTER_UPDATE_SINGLE_THREAD,
106 : COUNTER_UPDATE_ATOMIC_BUILTIN,
107 : COUNTER_UPDATE_ATOMIC_SPLIT,
108 : COUNTER_UPDATE_ATOMIC_PARTIAL
109 : };
110 :
111 : static counter_update_method counter_update = COUNTER_UPDATE_SINGLE_THREAD;
112 :
113 : /* These functions support measuring modified conditition/decision coverage
114 : (MC/DC). MC/DC requires all of the below during testing:
115 :
116 : - Each entry and exit point is invoked
117 : - Each decision takes every possible outcome
118 : - Each condition in a decision takes every possible outcome
119 : - Each condition in a decision is shown to independently affect the outcome
120 : of the decision
121 :
122 : Independence of a condition is shown by recording it being evaluated to a
123 : value (true/false) and not being made irrelevant ("masked") by a later term.
124 : This feature adds some instrumentation code, a few bitwise operators, that
125 : records the branches taken in conditions and applies a filter for the
126 : masking effect. Masking is essentially short-circuiting in reverse: a
127 : condition does not contribute to the outcome if it would short circuit the
128 : (sub) expression if it was evaluated right-to-left, (_ && false) and (_ ||
129 : true).
130 :
131 : The program is essentially rewritten this way:
132 :
133 : - if (a || b) { fn () }
134 : + if (a) { _t |= 0x1; goto _then; }
135 : + else { _f |= 0x1;
136 : + if (b) { _t |= 0x2; _mask |= 0x1; goto _then; }
137 : + else { _f |= 0x2; goto _else; }
138 : + _then:
139 : + _gcov_t |= (_t & _mask);
140 : + _gcov_f |= (_f & _mask);
141 : + fn (); goto _end;
142 : + _else:
143 : + _gcov_t |= (_t & _mask);
144 : + _gcov_f |= (_f & _mask);
145 : + fn ();
146 : + _end:
147 :
148 : It is assumed the front end will provide discrimnators so that conditional
149 : basic blocks (basic block with a conditional jump and outgoing true/false
150 : edges) that belong to the same Boolean expression have the same
151 : discriminator. Masking is determined by analyzing these expressions as a
152 : reduced order binary decision diagram. */
153 : namespace
154 : {
155 : /* Some context and reused instances between function calls. Large embedded
156 : buffers are used to up-front request enough memory for most programs and
157 : merge them into a single allocation at the cost of using more memory in the
158 : average case. Some numbers from linux v5.13 which is assumed to be a
159 : reasonably diverse code base: 75% of the functions in linux have less than
160 : 16 nodes in the CFG and approx 2.5% have more than 64 nodes. The functions
161 : that go beyond a few dozen nodes tend to be very large (>100) and so 64
162 : seems like a good balance.
163 :
164 : This is really just a performance balance of the cost of allocation and
165 : wasted memory. */
166 : struct conds_ctx
167 : {
168 : /* This is both a reusable shared allocation which is also used to return
169 : single expressions, which means it for most code should only hold a
170 : couple of elements. */
171 : auto_vec<basic_block, 64> blocks;
172 :
173 : /* Index for the topological order indexed by basic_block->index to an
174 : ordering so that expression (a || b && c) => top_index[a] < top_index[b]
175 : < top_index[c]. */
176 : auto_vec<int, 256> top_index;
177 :
178 : /* Pre-allocate bitmaps and vectors for per-function book keeping. This is
179 : pure instance reuse and the bitmaps carry no data between function
180 : calls. */
181 : auto_vec<basic_block, 64> b1;
182 : auto_vec<basic_block, 64> b2;
183 : auto_sbitmap g1;
184 : auto_sbitmap g2;
185 : auto_sbitmap g3;
186 : auto_vec<edge, 64> edges;
187 :
188 166 : explicit conds_ctx (unsigned size) noexcept (true) : g1 (size), g2 (size),
189 332 : g3 (size)
190 : {
191 166 : }
192 : };
193 :
194 : /* Only instrument terms with fewer than number of bits in a (wide) gcov
195 : integer, which is probably 64. The algorithm itself does not impose this
196 : limitation, but it makes for a simpler implementation.
197 :
198 : * Allocating the output data structure (coverage_counter_alloc ()) can
199 : assume pairs of gcov_type_unsigned and not use a separate length field.
200 : * A pair gcov_type_unsigned can be used as accumulators.
201 : * Updating accumulators is can use the bitwise operations |=, &= and not
202 : custom operators that work for arbitrary-sized bit-sets.
203 :
204 : Most real-world code should be unaffected by this, but it is possible
205 : (especially for generated code) to exceed this limit. */
206 : #define CONDITIONS_MAX_TERMS (TYPE_PRECISION (gcov_type_node))
207 : #define EDGE_CONDITION (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)
208 :
209 : /* Compare two basic blocks by their order in the expression i.e. for (a || b)
210 : then topological_cmp (a, b, ...) < 0. The result is undefined if LHS, RHS
211 : belong to different expressions. The TOP_INDEX argument should be the
212 : top_index vector from ctx. */
213 : int
214 142148 : topological_cmp (const void *lhs, const void *rhs, void *top_index)
215 : {
216 142148 : const_basic_block l = *(const basic_block *) lhs;
217 142148 : const_basic_block r = *(const basic_block *) rhs;
218 142148 : const vec<int> *im = (const vec<int> *) top_index;
219 142148 : return (*im)[l->index] - (*im)[r->index];
220 : }
221 :
222 : /* topological_cmp of the src block of LHS and RHS. The TOP_INDEX argument
223 : should be the top_index vector from ctx. */
224 : int
225 133804 : topological_src_cmp (const void *lhs, const void *rhs, void *top_index)
226 : {
227 133804 : const_edge l = *(const edge *) lhs;
228 133804 : const_edge r = *(const edge *) rhs;
229 133804 : return topological_cmp (&l->src, &r->src, top_index);
230 : }
231 :
232 : /* Find the index of NEEDLE in BLOCKS; return -1 if not found. This has two
233 : uses, sometimes for the index and sometimes for set member checks. Sets are
234 : typically very small (number of conditions, >8 is uncommon) so linear search
235 : should be very fast. */
236 : int
237 134935 : index_of (const basic_block needle, array_slice<basic_block> blocks)
238 : {
239 2936866 : for (size_t i = 0; i < blocks.size (); i++)
240 2936866 : if (blocks[i] == needle)
241 134935 : return int (i);
242 : return -1;
243 : }
244 :
245 : /* Special cases of the single_*_p and single_*_edge functions in basic-block.h
246 : that don't consider exception handling or other complex edges. This helps
247 : create a view of the CFG with only normal edges - if a basic block has both
248 : an outgoing fallthrough and exceptional edge, it should be considered a
249 : single-successor. */
250 : bool
251 271431 : single_p (const vec<edge, va_gc> *edges)
252 : {
253 271431 : int n = EDGE_COUNT (edges);
254 266869 : if (n == 0)
255 : return false;
256 :
257 670770 : for (edge e : edges)
258 403907 : if (e->flags & EDGE_COMPLEX)
259 55 : n -= 1;
260 :
261 266863 : return n == 1;
262 : }
263 :
264 : /* Get the single, non-complex edge. Behavior is undefined edges have more
265 : than 1 non-complex edges. */
266 : edge
267 1307 : single_edge (const vec<edge, va_gc> *edges)
268 : {
269 1307 : gcc_checking_assert (single_p (edges));
270 1307 : for (edge e : edges)
271 : {
272 1307 : if (e->flags & EDGE_COMPLEX)
273 0 : continue;
274 : return e;
275 : }
276 : return NULL;
277 : }
278 :
279 : /* Sometimes, for example with function calls, goto labels, and C++
280 : destructors, the CFG gets extra nodes that are essentially single-entry
281 : single-exit in the middle of boolean expressions. For example:
282 :
283 : x || can_throw (y)
284 :
285 : A
286 : /|
287 : / |
288 : B |
289 : | |
290 : C |
291 : / \ |
292 : / \|
293 : F T
294 :
295 : Without the extra node inserted by the function + exception it becomes a
296 : proper 2-term graph, not 2 single-term graphs.
297 :
298 : A
299 : /|
300 : C |
301 : / \|
302 : F T
303 :
304 : This function finds the source edge of these paths. This is often the
305 : identity function. */
306 : edge
307 136626 : contract_edge_up (edge e)
308 : {
309 137680 : while (true)
310 : {
311 137153 : basic_block src = e->src;
312 137153 : if (!single_p (src->preds))
313 : return e;
314 131749 : if (!single_p (src->succs))
315 : return e;
316 527 : e = single_edge (src->preds);
317 527 : }
318 : }
319 :
320 : /* A simple struct for storing/returning outcome block pairs. Either both
321 : blocks are set or both are NULL. */
322 : struct outcomes
323 : {
324 : basic_block t = NULL;
325 : basic_block f = NULL;
326 :
327 4633 : operator bool () const noexcept (true)
328 : {
329 4633 : return t && f;
330 : }
331 : };
332 :
333 : /* Get the true/false successors of a basic block. If b is not a conditional
334 : block both edges are NULL. */
335 : outcomes
336 135273 : conditional_succs (const basic_block b)
337 : {
338 135273 : outcomes c;
339 676365 : for (edge e : b->succs)
340 : {
341 270546 : if (e->flags & EDGE_TRUE_VALUE)
342 135273 : c.t = e->dest;
343 270546 : if (e->flags & EDGE_FALSE_VALUE)
344 135273 : c.f = e->dest;
345 : }
346 :
347 135273 : gcc_assert ((c.t && c.f) || (!c.t && !c.f));
348 135273 : return c;
349 : }
350 :
351 : /* Get the index or offset of a conditional flag, 0 for true and 1 for false.
352 : These indices carry no semantics but must be consistent as they are used to
353 : index into data structures in code generation and gcov. */
354 : unsigned
355 5797 : condition_index (unsigned flag)
356 : {
357 5797 : return (flag & EDGE_CONDITION) == EDGE_TRUE_VALUE ? 0 : 1;
358 : }
359 :
360 : /* Returns the condition identifier for the basic block if set, otherwise 0.
361 : This is only meaningful in GIMPLE and is used for condition coverage.
362 :
363 : There may be conditions created that did not get an uid, such as those
364 : implicitly created by destructors. We could include them in the condition
365 : coverage for completeness (i.e. condition coverage implies (implicit) branch
366 : coverage), but they have no natural buckets and should all be single-term.
367 : For now these are ignored and given uid = 0, and branch coverage is left to
368 : -fprofile-arcs.
369 :
370 : Under optimization, COND_EXPRs may be folded, replaced with switches,
371 : min-max, etc., which leaves ghost identifiers in basic blocks that do not
372 : end with a conditional jump. They are not really meaningful for condition
373 : coverage anymore, but since coverage is unreliable under optimization anyway
374 : this is not a big problem.
375 :
376 : The cond_uids map in FN cannot be expected to exist. It will only be
377 : created if it is needed, and a function may have gconds even though there
378 : are none in source. This can be seen in PR gcov-profile/114601, when
379 : -finstrument-functions-once is used and the function has no conditions. */
380 : unsigned
381 1949 : condition_uid (struct function *fn, basic_block b)
382 : {
383 1949 : gimple *stmt = gsi_stmt (gsi_last_bb (b));
384 1951 : if (!safe_is_a <gcond *> (stmt) || !fn->cond_uids)
385 : return 0;
386 :
387 649 : unsigned *v = fn->cond_uids->get (as_a <gcond *> (stmt));
388 649 : return v ? *v : 0;
389 : }
390 :
391 : /* Compute the masking table.
392 :
393 : Masking and short circuiting are deeply connected - masking occurs when
394 : control flow reaches a state that is also reachable with short circuiting.
395 : In fact, masking corresponds to short circuiting for the reversed
396 : expression. This means we can find the limits, the last term in preceding
397 : subexpressions, by following the edges that short circuit to the same
398 : outcome. The algorithm treats the CFG as a reduced order binary decision
399 : diagram (see Randall E. Bryant's Graph Based Algorithms for Boolean
400 : Function Manipulation (1987)).
401 :
402 : In the simplest case a || b:
403 :
404 : a
405 : |\
406 : | b
407 : |/ \
408 : T F
409 :
410 : T has multiple incoming edges and is the outcome of a short circuit,
411 : with top = a, bot = b. The top node (a) is masked when the edge (b, T) is
412 : taken.
413 :
414 : The names "top" and "bot" refer to a pair of nodes with a shared
415 : successor. The top is always the node corresponding to the left-most
416 : operand of the two, and it holds that top < bot in a topological ordering.
417 :
418 : Now consider (a && b) || (c && d) and its masking table:
419 :
420 : a
421 : |\
422 : b \
423 : |\|
424 : | c
425 : | |\
426 : | d \
427 : |/ \|
428 : T F
429 :
430 : a[0] = {}
431 : a[1] = {}
432 : b[0] = {a}
433 : b[1] = {}
434 : c[0] = {}
435 : c[1] = {}
436 : d[0] = {c}
437 : d[1] = {a,b}
438 :
439 : Note that 0 and 1 are indices and not boolean values - a[0] is the index in
440 : the masking vector when a takes the true edge.
441 :
442 : b[0] and d[0] are identical to the a || b example, and d[1] is the bot in
443 : the triangle [d, b] -> T. b is the top node in the [d, b] relationship and
444 : last term in (a && b). To find the other terms masked we use the fact that
445 : all paths in an expression go through either of the outcomes, found by
446 : collecting all non-complex edges that go out of the expression (the
447 : neighborhood). In some cases the outgoing edge go through intermediate (or
448 : bypass) nodes, and we collect these paths too (see contract_edge_up).
449 :
450 : We find the terms by marking the outcomes (in this case c, T) and walk the
451 : predecessors starting at top (in this case b) and masking nodes when both
452 : successors are marked. This is equivalent to removing the two outcome nodes
453 : of the subexpression and finding the nodes not in the inverse reachability
454 : set.
455 :
456 : We only have to consider the pairs of top, bot where top is the the closest
457 : (highest-index'd) candidate that still satisfies top < bot in the
458 : topological order, as this will be the immediate left operand. The nodes of
459 : the other left operands will also be found when going through the rightmost
460 : term, and a lower-index'd top would just find subsets. This has a
461 : significant performance impact, 15-20x faster for the worst cases of (x && y
462 : && ..) with no nesting.
463 :
464 : The masking table is represented as two bitfields per term in the expression
465 : with the index corresponding to the term in the Boolean expression.
466 : a || b && c becomes the term vector [a b c] and the masking table [a[0]
467 : a[1] b[0] ...]. The kth bit of a masking vector is set if the kth term
468 : is masked by taking the edge.
469 :
470 : The out masks are in uint64_t (the practical maximum for gcov_type_node for
471 : any target) as it has to be big enough to store the target size gcov types
472 : independent of the host. */
473 : void
474 297 : masking_vectors (conds_ctx& ctx, array_slice<basic_block> blocks,
475 : array_slice<sbitmap> maps, array_slice<uint64_t> masks)
476 : {
477 297 : gcc_assert (blocks.is_valid ());
478 297 : gcc_assert (!blocks.empty ());
479 297 : gcc_assert (maps.is_valid ());
480 297 : gcc_assert (masks.is_valid ());
481 297 : gcc_assert (sizeof (masks[0]) * BITS_PER_UNIT >= CONDITIONS_MAX_TERMS);
482 :
483 297 : if (bitmap_count_bits (maps[0]) == 1)
484 : return;
485 :
486 100 : sbitmap marks = ctx.g1;
487 100 : const sbitmap core = maps[0];
488 100 : const sbitmap allg = maps[1];
489 100 : vec<basic_block> &queue = ctx.b1;
490 100 : vec<basic_block> &body = ctx.b2;
491 100 : const vec<int> &top_index = ctx.top_index;
492 :
493 : /* Set up for the iteration - include the outcome nodes in the traversal.
494 : The algorithm compares pairs of nodes and is not really sensitive to
495 : traversal order, but need to maintain topological order because the
496 : index of masking nodes maps to the index in the accumulators. We must
497 : also check the incoming-to-outcome pairs. These edges may in turn be
498 : split (this happens with labels on top of then/else blocks) so we must
499 : follow any single-in single-out path. The non-condition blocks do not
500 : have to be in order as they are non-condition blocks and will not be
501 : considered for the set-bit index. */
502 100 : body.truncate (0);
503 100 : body.reserve (blocks.size () + 2);
504 533 : for (const basic_block b : blocks)
505 433 : if (bitmap_bit_p (core, b->index))
506 385 : body.quick_push (b);
507 :
508 533 : for (basic_block b : blocks)
509 : {
510 433 : if (!bitmap_bit_p (core, b->index))
511 48 : continue;
512 :
513 1925 : for (edge e : b->succs)
514 : {
515 770 : if (e->flags & EDGE_COMPLEX)
516 0 : continue;
517 770 : if (bitmap_bit_p (allg, e->dest->index))
518 322 : continue;
519 448 : body.safe_push (e->dest);
520 :
521 : /* There may be multiple nodes between the condition edge and the
522 : actual outcome, and we need to know when these paths join to
523 : determine if there is short circuit/masking. This is
524 : effectively creating a virtual edge from the condition node to
525 : the real outcome. */
526 1676 : while (!(e->flags & EDGE_DFS_BACK) && single_p (e->dest->succs))
527 : {
528 780 : e = single_edge (e->dest->succs);
529 780 : body.safe_push (e->dest);
530 : }
531 : }
532 : }
533 :
534 : /* Find the masking. The leftmost element cannot mask anything, so
535 : start at 1. */
536 3226 : for (size_t i = 1; i != body.length (); i++)
537 : {
538 1513 : const basic_block b = body[i];
539 1513 : if (b->preds->length () < 2)
540 710 : continue;
541 803 : ctx.edges.truncate (0);
542 803 : ctx.edges.reserve (b->preds->length ());
543 8337 : for (edge e : b->preds)
544 5928 : if (!(e->flags & EDGE_COMPLEX))
545 5921 : ctx.edges.quick_push (contract_edge_up (e));
546 803 : if (ctx.edges.length () < 2)
547 3 : continue;
548 800 : ctx.edges.sort (topological_src_cmp, &ctx.top_index);
549 :
550 11842 : for (size_t i0 = 0, i1 = 1; i1 != ctx.edges.length (); ++i0, ++i1)
551 : {
552 5121 : edge etop = ctx.edges[i0];
553 5121 : edge ebot = ctx.edges[i1];
554 5121 : gcc_assert (etop != ebot);
555 :
556 5121 : const basic_block top = etop->src;
557 5121 : const basic_block bot = ebot->src;
558 5121 : const unsigned cond = etop->flags & ebot->flags & EDGE_CONDITION;
559 5121 : if (!cond)
560 488 : continue;
561 4670 : if (top_index[top->index] > top_index[bot->index])
562 0 : continue;
563 4670 : if (!bitmap_bit_p (core, top->index))
564 24 : continue;
565 4646 : if (!bitmap_bit_p (core, bot->index))
566 13 : continue;
567 :
568 4633 : outcomes out = conditional_succs (top);
569 4633 : gcc_assert (out);
570 4633 : bitmap_clear (marks);
571 4633 : bitmap_set_bit (marks, out.t->index);
572 4633 : bitmap_set_bit (marks, out.f->index);
573 4633 : queue.truncate (0);
574 4633 : queue.safe_push (top);
575 :
576 : // The edge bot -> outcome triggers the masking
577 9266 : const int m = 2 * index_of (bot, body) + condition_index (cond);
578 4633 : gcc_assert (m >= 0);
579 140081 : while (!queue.is_empty ())
580 : {
581 130815 : basic_block q = queue.pop ();
582 : /* q may have been processed & completed by being added to the
583 : queue multiple times, so check that there is still work to
584 : do before continuing. */
585 130815 : if (bitmap_bit_p (marks, q->index))
586 513 : continue;
587 :
588 130640 : outcomes succs = conditional_succs (q);
589 130640 : if (!bitmap_bit_p (marks, succs.t->index))
590 237 : continue;
591 130403 : if (!bitmap_bit_p (marks, succs.f->index))
592 101 : continue;
593 :
594 260604 : const int index = index_of (q, body);
595 130302 : gcc_assert (index != -1);
596 130302 : masks[m] |= uint64_t (1) << index;
597 130302 : bitmap_set_bit (marks, q->index);
598 :
599 521611 : for (edge e : q->preds)
600 : {
601 130705 : e = contract_edge_up (e);
602 130705 : if (e->flags & EDGE_DFS_BACK)
603 10 : continue;
604 130695 : if (bitmap_bit_p (marks, e->src->index))
605 5 : continue;
606 130690 : if (!bitmap_bit_p (core, e->src->index))
607 4508 : continue;
608 126182 : queue.safe_push (e->src);
609 : }
610 : }
611 : }
612 : }
613 : }
614 :
615 : /* Emit LHS = RHS onto SEQ. This is just a short hand that automates the
616 : building of the assign, which becomes noisy. */
617 : static tree
618 1868 : emit_assign (gimple_seq *seq, tree lhs, tree rhs)
619 : {
620 934 : gassign *w = gimple_build_assign (lhs, rhs);
621 1868 : gimple_seq_add_stmt (seq, w);
622 1868 : return lhs;
623 : }
624 :
625 : /* Emit lhs = RHS onto SEQ. The lhs is created. */
626 : static tree
627 934 : emit_assign (gimple_seq *seq, tree rhs)
628 : {
629 934 : return emit_assign (seq, make_ssa_name (gcov_type_node), rhs);
630 : }
631 :
632 : /* Emit/fold OP1 <OP> [OP2] onto SEQ.
633 : Return folded constant or SSA name. */
634 : static tree
635 4902 : emit_bitwise_op (gimple_seq *seq, tree op1, tree_code op,
636 : tree op2 = NULL_TREE)
637 : {
638 4902 : return op2 == NULL_TREE
639 4058 : ? gimple_build (seq, op, gcov_type_node, op1)
640 4058 : : gimple_build (seq, op, gcov_type_node, op1, op2);
641 : }
642 :
643 : /* Visitor for make_top_index. */
644 : void
645 4361 : make_top_index_visit (basic_block b, vec<basic_block> &l, vec<int> &marks)
646 : {
647 4361 : if (marks[b->index])
648 : return;
649 :
650 : /* Follow the false edge first, if it exists, so that true paths are given
651 : the lower index in the ordering. Any iteration order
652 : would yield a valid and useful topological ordering, but making sure the
653 : true branch has the lower index first makes reporting work better for
654 : expressions with ternaries. Walk the false branch first because the
655 : array will be reversed to finalize the topological order.
656 :
657 : With the wrong ordering (a ? b : c) && d could become [a c b d], but the
658 : (expected) order is really [a b c d]. */
659 :
660 1949 : const unsigned false_fwd = EDGE_DFS_BACK | EDGE_FALSE_VALUE;
661 7973 : for (edge e : b->succs)
662 2458 : if ((e->flags & false_fwd) == EDGE_FALSE_VALUE)
663 650 : make_top_index_visit (e->dest, l, marks);
664 :
665 7973 : for (edge e : b->succs)
666 2458 : if (!(e->flags & false_fwd))
667 1762 : make_top_index_visit (e->dest, l, marks);
668 :
669 1949 : marks[b->index] = 1;
670 1949 : l.quick_push (b);
671 : }
672 :
673 : /* Find a topological sorting of the blocks in a function so that left operands
674 : are before right operands including subexpressions. Sorting on block index
675 : does not guarantee this property and the syntactical order of terms is very
676 : important to the condition coverage. The sorting algorithm is from Cormen
677 : et al (2001) but with back-edges ignored and thus there is no need for
678 : temporary marks (for cycle detection). The L argument is a buffer/working
679 : memory, and the output will be written to TOP_INDEX.
680 :
681 : For the expression (a || (b && c) || d) the blocks should be [a b c d]. */
682 : void
683 166 : make_top_index (array_slice<basic_block> blocks, vec<basic_block> &l,
684 : vec<int> &top_index)
685 : {
686 166 : l.truncate (0);
687 166 : l.reserve (blocks.size ());
688 :
689 : /* Use of the output map as a temporary for tracking visited status. */
690 166 : top_index.truncate (0);
691 166 : top_index.safe_grow_cleared (blocks.size ());
692 2115 : for (const basic_block b : blocks)
693 1949 : make_top_index_visit (b, l, top_index);
694 :
695 : /* Insert canaries - if there are unreachable nodes (for example infinite
696 : loops) then the unreachable nodes should never be needed for comparison,
697 : and l.length () < max_index. An index mapping should also never be
698 : recorded twice. */
699 4230 : for (unsigned i = 0; i != top_index.length (); i++)
700 1949 : top_index[i] = -1;
701 :
702 332 : gcc_assert (blocks.size () == l.length ());
703 166 : l.reverse ();
704 166 : const unsigned nblocks = l.length ();
705 2115 : for (unsigned i = 0; i != nblocks; i++)
706 : {
707 1949 : gcc_assert (l[i]->index != -1);
708 1949 : top_index[l[i]->index] = int (i);
709 : }
710 166 : }
711 :
712 : /* Find all nodes including non-conditions in a Boolean expression. We need to
713 : know the paths through the expression so that the masking and
714 : instrumentation phases can limit searches and know what subgraphs must be
715 : threaded through, but not counted, such as the (b || c) in
716 : a && fn (b || c) && d.
717 :
718 : It is essentially the intersection of downwards paths from the expression
719 : nodes EXPR to the post-dominator and upwards from the post-dominator.
720 : Finding the dominator is slightly more involved than picking the first/last,
721 : particularly under optimization, because both incoming and outgoing paths
722 : may have multiple entries/exits.
723 :
724 : It is assumed GRAPH is an array_slice of the basic blocks of this function
725 : sorted by the basic block index. */
726 : vec<basic_block> &
727 297 : paths_between (conds_ctx &ctx, array_slice<basic_block> graph,
728 : const vec<basic_block> &expr)
729 : {
730 297 : if (expr.length () == 1)
731 : {
732 197 : ctx.blocks.truncate (0);
733 197 : ctx.blocks.safe_push (expr[0]);
734 197 : return ctx.blocks;
735 : }
736 :
737 100 : basic_block dom;
738 100 : sbitmap up = ctx.g1;
739 100 : sbitmap down = ctx.g2;
740 100 : sbitmap paths = ctx.g3;
741 100 : vec<basic_block> &queue = ctx.b1;
742 :
743 100 : queue.truncate (0);
744 100 : bitmap_clear (down);
745 100 : dom = get_immediate_dominator (CDI_POST_DOMINATORS, expr[0]);
746 685 : for (basic_block b : expr)
747 385 : if (dom != b)
748 383 : dom = nearest_common_dominator (CDI_POST_DOMINATORS, dom, b);
749 100 : queue.safe_splice (expr);
750 1674 : while (!queue.is_empty ())
751 : {
752 1474 : basic_block b = queue.pop ();
753 1474 : if (!bitmap_set_bit (down, b->index))
754 692 : continue;
755 782 : if (b == dom)
756 100 : continue;
757 3151 : for (edge e : b->succs)
758 1105 : if (!(e->flags & (EDGE_COMPLEX | EDGE_DFS_BACK)))
759 1089 : queue.safe_push (e->dest);
760 : }
761 :
762 100 : queue.truncate (0);
763 100 : bitmap_clear (up);
764 100 : dom = expr[0];
765 485 : for (basic_block b : expr)
766 385 : if (dom != b)
767 285 : dom = nearest_common_dominator (CDI_DOMINATORS, dom, b);
768 100 : queue.safe_splice (expr);
769 980 : while (!queue.is_empty ())
770 : {
771 780 : basic_block b = queue.pop ();
772 780 : if (!bitmap_set_bit (up, b->index))
773 335 : continue;
774 445 : if (b == dom)
775 100 : continue;
776 1442 : for (edge e : b->preds)
777 407 : if (!(e->flags & (EDGE_COMPLEX | EDGE_DFS_BACK)))
778 395 : queue.safe_push (e->src);
779 : }
780 :
781 100 : bitmap_and (paths, up, down);
782 100 : vec<basic_block> &blocks = ctx.blocks;
783 100 : blocks.truncate (0);
784 100 : blocks.reserve (graph.size ());
785 100 : sbitmap_iterator itr;
786 100 : unsigned index;
787 633 : EXECUTE_IF_SET_IN_BITMAP (paths, 0, index, itr)
788 433 : blocks.quick_push (graph[index]);
789 : return blocks;
790 : }
791 :
792 : }
793 :
794 : /* Context object for the condition coverage. This stores conds_ctx (the
795 : buffers reused when analyzing the cfg) and the output arrays. This is
796 : designed to be heap allocated and aggressively preallocates large buffers to
797 : avoid having to reallocate for most programs. */
798 : struct condcov
799 : {
800 166 : explicit condcov (unsigned nblocks) noexcept (true) : ctx (nblocks),
801 166 : m_maps (sbitmap_vector_alloc (2 * nblocks, nblocks))
802 : {
803 166 : bitmap_vector_clear (m_maps, 2 * nblocks);
804 166 : }
805 : auto_vec<size_t, 128> m_index;
806 : auto_vec<basic_block, 256> m_blocks;
807 : auto_vec<uint64_t, 512> m_masks;
808 : conds_ctx ctx;
809 : sbitmap *m_maps;
810 : };
811 :
812 : /* Get the length, that is the number of Boolean expression found. cov_length
813 : is the one-past index for cov_{blocks,masks,maps}. */
814 : size_t
815 332 : cov_length (const struct condcov *cov)
816 : {
817 332 : if (cov->m_index.is_empty ())
818 : return 0;
819 332 : return cov->m_index.length () - 1;
820 : }
821 :
822 : /* The subgraph, excluding intermediates, for the nth Boolean expression. */
823 : array_slice<basic_block>
824 594 : cov_blocks (struct condcov *cov, size_t n)
825 : {
826 594 : if (n >= cov->m_index.length ())
827 0 : return array_slice<basic_block>::invalid ();
828 :
829 1188 : basic_block *begin = cov->m_blocks.begin () + cov->m_index[n];
830 594 : basic_block *end = cov->m_blocks.begin () + cov->m_index[n + 1];
831 594 : return array_slice<basic_block> (begin, end - begin);
832 : }
833 :
834 : /* The masks for the nth Boolean expression. */
835 : array_slice<uint64_t>
836 594 : cov_masks (struct condcov *cov, size_t n)
837 : {
838 594 : if (n >= cov->m_index.length ())
839 0 : return array_slice<uint64_t>::invalid ();
840 :
841 1188 : uint64_t *begin = cov->m_masks.begin () + 2 * cov->m_index[n];
842 594 : uint64_t *end = cov->m_masks.begin () + 2 * cov->m_index[n + 1];
843 594 : return array_slice<uint64_t> (begin, end - begin);
844 : }
845 :
846 : /* The maps for the nth Boolean expression. */
847 : array_slice<sbitmap>
848 594 : cov_maps (struct condcov *cov, size_t n)
849 : {
850 594 : if (n >= cov->m_index.length ())
851 0 : return array_slice<sbitmap>::invalid ();
852 :
853 594 : sbitmap *begin = cov->m_maps + 2 * n;
854 594 : sbitmap *end = begin + 2;
855 594 : return array_slice<sbitmap> (begin, end - begin);
856 : }
857 :
858 : /* Deleter for condcov. */
859 : void
860 166 : cov_free (struct condcov *cov)
861 : {
862 166 : sbitmap_vector_free (cov->m_maps);
863 166 : delete cov;
864 166 : }
865 :
866 : /* Condition coverage (MC/DC)
867 :
868 : Whalen, Heimdahl, De Silva in "Efficient Test Coverage Measurement for
869 : MC/DC" describe an algorithm for modified condition/decision coverage based
870 : on AST analysis. This algorithm does analyzes the control flow graph
871 : (interpreted as a binary decision diagram) to determine the masking vectors.
872 : The individual phases are described in more detail closer to the
873 : implementation.
874 :
875 : The coverage only considers the positions, not the symbols, in a
876 : conditional, e.g. !A || (!B && A) is a 3-term conditional even though A
877 : appears twice. Subexpressions have no effect on term ordering:
878 : (a && (b || (c && d)) || e) comes out as [a b c d e]. Functions whose
879 : arguments are Boolean expressions are treated as separate expressions, that
880 : is, a && fn (b || c) && d is treated as [a _fn d] and [b c], not [a b c d].
881 :
882 : The output for gcov is a vector of pairs of unsigned integers, interpreted
883 : as bit-sets, where the bit index corresponds to the index of the condition
884 : in the expression.
885 :
886 : The returned condcov should be released by the caller with cov_free. */
887 : struct condcov *
888 166 : find_conditions (struct function *fn)
889 : {
890 166 : mark_dfs_back_edges (fn);
891 166 : const bool have_dom = dom_info_available_p (fn, CDI_DOMINATORS);
892 166 : const bool have_post_dom = dom_info_available_p (fn, CDI_POST_DOMINATORS);
893 166 : if (!have_dom)
894 162 : calculate_dominance_info (CDI_DOMINATORS);
895 166 : if (!have_post_dom)
896 166 : calculate_dominance_info (CDI_POST_DOMINATORS);
897 :
898 166 : const unsigned nblocks = n_basic_blocks_for_fn (fn);
899 166 : basic_block *fnblocksp = basic_block_info_for_fn (fn)->address ();
900 166 : condcov *cov = new condcov (nblocks);
901 166 : conds_ctx &ctx = cov->ctx;
902 166 : array_slice<basic_block> fnblocks (fnblocksp, nblocks);
903 166 : make_top_index (fnblocks, ctx.b1, ctx.top_index);
904 :
905 : /* Bin the Boolean expressions so that exprs[id] -> [x1, x2, ...]. */
906 166 : hash_map<int_hash<unsigned, 0>, auto_vec<basic_block>> exprs;
907 2115 : for (basic_block b : fnblocks)
908 : {
909 1949 : const unsigned uid = condition_uid (fn, b);
910 1949 : if (uid == 0)
911 1302 : continue;
912 647 : exprs.get_or_insert (uid).safe_push (b);
913 : }
914 :
915 : /* Visit all reachable nodes and collect conditions. Topological order is
916 : important so the first node of a boolean expression is visited first
917 : (it will mark subsequent terms). */
918 166 : cov->m_index.safe_push (0);
919 762 : for (auto expr : exprs)
920 : {
921 298 : vec<basic_block> &conds = expr.second;
922 596 : if (conds.length () > CONDITIONS_MAX_TERMS)
923 : {
924 2 : location_t loc = gimple_location (gsi_stmt (gsi_last_bb (conds[0])));
925 1 : warning_at (loc, OPT_Wcoverage_too_many_conditions,
926 : "too many conditions (found %u); giving up coverage",
927 : conds.length ());
928 1 : continue;
929 1 : }
930 297 : conds.sort (topological_cmp, &ctx.top_index);
931 297 : vec<basic_block> &subgraph = paths_between (ctx, fnblocks, conds);
932 297 : subgraph.sort (topological_cmp, &ctx.top_index);
933 297 : const unsigned index = cov->m_index.length () - 1;
934 297 : sbitmap condm = cov->m_maps[0 + 2 * index];
935 297 : sbitmap subgm = cov->m_maps[1 + 2 * index];
936 1473 : for (basic_block b : conds)
937 582 : bitmap_set_bit (condm, b->index);
938 1521 : for (basic_block b : subgraph)
939 630 : bitmap_set_bit (subgm, b->index);
940 297 : cov->m_blocks.safe_splice (subgraph);
941 594 : cov->m_index.safe_push (cov->m_blocks.length ());
942 : }
943 :
944 166 : if (!have_dom)
945 162 : free_dominance_info (fn, CDI_DOMINATORS);
946 166 : if (!have_post_dom)
947 166 : free_dominance_info (fn, CDI_POST_DOMINATORS);
948 :
949 166 : cov->m_masks.safe_grow_cleared (2 * cov->m_index.last ());
950 166 : const size_t length = cov_length (cov);
951 463 : for (size_t i = 0; i != length; i++)
952 297 : masking_vectors (ctx, cov_blocks (cov, i), cov_maps (cov, i),
953 : cov_masks (cov, i));
954 :
955 166 : return cov;
956 166 : }
957 :
958 : namespace
959 : {
960 :
961 : /* Stores the incoming edge and previous counters (in SSA form) on that edge
962 : for the node e->deston that edge for the node e->dest. The counters record
963 : the seen-true (0), seen-false (1), and current-mask (2). They are stored in
964 : an array rather than proper members for access-by-index as the code paths
965 : tend to be identical for the different counters. */
966 : struct counters
967 : {
968 : edge e;
969 : tree counter[3];
970 6068 : tree &operator[] (size_t i) { return counter[i]; }
971 : };
972 :
973 : /* Find the counters for the incoming edge e, or NULL if the edge has not been
974 : recorded (could be for complex incoming edges). */
975 : counters *
976 1186 : find_counters (vec<counters> &candidates, edge e)
977 : {
978 6032 : for (counters &candidate : candidates)
979 3648 : if (candidate.e == e)
980 : return &candidate;
981 : return NULL;
982 : }
983 :
984 : /* Resolve the SSA for a specific counter KIND. If it is not modified by any
985 : incoming edges, simply forward it, otherwise create a phi node of all the
986 : candidate counters and return it. */
987 : tree
988 1890 : resolve_counter (vec<counters> &cands, size_t kind)
989 : {
990 1890 : gcc_assert (!cands.is_empty ());
991 1890 : gcc_assert (kind < 3);
992 :
993 1890 : counters &fst = cands[0];
994 :
995 1890 : if (!fst.e || fst.e->dest->preds->length () == 1)
996 : {
997 1722 : gcc_assert (cands.length () == 1);
998 1722 : return fst[kind];
999 : }
1000 :
1001 168 : tree zero0 = build_int_cst (gcov_type_node, 0);
1002 168 : tree ssa = make_ssa_name (gcov_type_node);
1003 168 : gphi *phi = create_phi_node (ssa, fst.e->dest);
1004 846 : for (edge e : fst.e->dest->preds)
1005 : {
1006 342 : counters *prev = find_counters (cands, e);
1007 342 : if (prev)
1008 330 : add_phi_arg (phi, (*prev)[kind], e, UNKNOWN_LOCATION);
1009 : else
1010 : {
1011 12 : tree zero = make_ssa_name (gcov_type_node);
1012 12 : gimple_stmt_iterator gsi = gsi_after_labels (e->src);
1013 12 : gassign *set = gimple_build_assign (zero, zero0);
1014 12 : gsi_insert_before (&gsi, set, GSI_NEW_STMT);
1015 12 : add_phi_arg (phi, zero, e, UNKNOWN_LOCATION);
1016 : }
1017 : }
1018 : return ssa;
1019 : }
1020 :
1021 : /* Resolve all the counters for a node. Note that the edge is undefined, as
1022 : the counters are intended to form the base to push to the successors, and
1023 : because the is only meaningful for nodes with a single predecessor. */
1024 : counters
1025 630 : resolve_counters (vec<counters> &cands)
1026 : {
1027 630 : counters next;
1028 630 : next[0] = resolve_counter (cands, 0);
1029 630 : next[1] = resolve_counter (cands, 1);
1030 630 : next[2] = resolve_counter (cands, 2);
1031 630 : return next;
1032 : }
1033 :
1034 : }
1035 :
1036 : /* Add instrumentation to a decision subgraph. EXPR should be the
1037 : (topologically sorted) block of nodes returned by cov_blocks, MAPS the
1038 : bitmaps returned by cov_maps, and MASKS the block of bitsets returned by
1039 : cov_masks. CONDNO should be the index of this condition in the function,
1040 : i.e. the same argument given to cov_{masks,graphs}. EXPR may contain nodes
1041 : in-between the conditions, e.g. when an operand contains a function call,
1042 : or there is a setjmp and the cfg is filled with complex edges.
1043 :
1044 : Every node is annotated with three counters; the true, false, and mask
1045 : value. First, walk the graph and determine what if there are multiple
1046 : possible values for either accumulator depending on the path taken, in which
1047 : case a phi node is created and registered as the accumulator. Then, those
1048 : values are pushed as accumulators to the immediate successors. For some
1049 : very particular programs there may be multiple paths into the expression
1050 : (e.g. when prior terms are determined by a surrounding conditional) in which
1051 : case the default zero-counter is pushed, otherwise all predecessors will
1052 : have been considered before the successor because of topologically ordered
1053 : traversal. Finally, expr is traversed again to look for edges to the
1054 : outcomes, that is, edges with a destination outside of expr, and the local
1055 : accumulators are flushed to the global gcov counters on these edges. In
1056 : some cases there are edge splits that cause 3+ edges to the two outcome
1057 : nodes.
1058 :
1059 : If a complex edge is taken (e.g. on a longjmp) the accumulators are
1060 : attempted poisoned so that there would be no change to the global counters,
1061 : but this has proven unreliable in the presence of undefined behavior, see
1062 : the setjmp003 test.
1063 :
1064 : It is important that the flushes happen on the basic condition outgoing
1065 : edge, otherwise flushes could be lost to exception handling or other
1066 : abnormal control flow. */
1067 : size_t
1068 297 : instrument_decisions (array_slice<basic_block> expr, size_t condno,
1069 : array_slice<sbitmap> maps, array_slice<uint64_t> masks)
1070 : {
1071 297 : tree zero = build_int_cst (gcov_type_node, 0);
1072 297 : tree poison = build_int_cst (gcov_type_node, ~0ULL);
1073 297 : const sbitmap core = maps[0];
1074 297 : const sbitmap allg = maps[1];
1075 :
1076 297 : hash_map<basic_block, vec<counters>> table;
1077 297 : counters zerocounter;
1078 297 : zerocounter.e = NULL;
1079 297 : zerocounter[0] = zero;
1080 297 : zerocounter[1] = zero;
1081 297 : zerocounter[2] = zero;
1082 :
1083 297 : unsigned xi = 0;
1084 297 : bool increment = false;
1085 297 : tree rhs = build_int_cst (gcov_type_node, 1ULL << xi);
1086 927 : for (basic_block current : expr)
1087 : {
1088 630 : vec<counters> &candidates = table.get_or_insert (current);
1089 630 : if (candidates.is_empty ())
1090 303 : candidates.safe_push (zerocounter);
1091 630 : counters prev = resolve_counters (candidates);
1092 :
1093 630 : if (increment)
1094 : {
1095 285 : xi += 1;
1096 285 : gcc_checking_assert (xi < sizeof (uint64_t) * BITS_PER_UNIT);
1097 285 : rhs = build_int_cst (gcov_type_node, 1ULL << xi);
1098 285 : increment = false;
1099 : }
1100 :
1101 3117 : for (edge e : current->succs)
1102 : {
1103 1227 : counters next = prev;
1104 1227 : next.e = e;
1105 1227 : gimple_seq seq = NULL;
1106 :
1107 1227 : if (bitmap_bit_p (core, e->src->index) && (e->flags & EDGE_CONDITION))
1108 : {
1109 1164 : const int k = condition_index (e->flags);
1110 1164 : next[k] = emit_bitwise_op (&seq, prev[k], BIT_IOR_EXPR, rhs);
1111 1164 : if (masks[2 * xi + k])
1112 : {
1113 272 : tree m = build_int_cst (gcov_type_node, masks[2 * xi + k]);
1114 272 : next[2] = emit_bitwise_op (&seq, prev[2], BIT_IOR_EXPR, m);
1115 : }
1116 : increment = true;
1117 : }
1118 63 : else if (e->flags & EDGE_COMPLEX)
1119 : {
1120 : /* A complex edge has been taken - wipe the accumulators and
1121 : poison the mask so that this path does not contribute to
1122 : coverage. */
1123 3 : next[0] = poison;
1124 3 : next[1] = poison;
1125 3 : next[2] = poison;
1126 : }
1127 1227 : if (seq)
1128 166 : gsi_insert_seq_on_edge (e, seq);
1129 1227 : table.get_or_insert (e->dest).safe_push (next);
1130 : }
1131 : }
1132 :
1133 : /* Since this is also the return value, the number of conditions, make sure
1134 : to include the increment of the last basic block. */
1135 297 : if (increment)
1136 297 : xi += 1;
1137 :
1138 297 : gcc_assert (xi == bitmap_count_bits (core));
1139 :
1140 297 : const tree relaxed = build_int_cst (integer_type_node, MEMMODEL_RELAXED);
1141 297 : const bool atomic = flag_profile_update == PROFILE_UPDATE_ATOMIC;
1142 297 : const tree atomic_ior
1143 297 : = builtin_decl_explicit (TYPE_PRECISION (gcov_type_node) > 32
1144 : ? BUILT_IN_ATOMIC_FETCH_OR_8
1145 : : BUILT_IN_ATOMIC_FETCH_OR_4);
1146 :
1147 : /* Flush to the gcov accumulators. */
1148 927 : for (const basic_block b : expr)
1149 : {
1150 630 : if (!bitmap_bit_p (core, b->index))
1151 48 : continue;
1152 :
1153 2910 : for (edge e : b->succs)
1154 : {
1155 : /* Flush the accumulators on leaving the Boolean function. The
1156 : destination may be inside the function only when it returns to
1157 : the loop header, such as do { ... } while (x); */
1158 1164 : if (bitmap_bit_p (allg, e->dest->index))
1159 : {
1160 324 : if (!(e->flags & EDGE_DFS_BACK))
1161 320 : continue;
1162 4 : if (e->dest != expr[0])
1163 0 : continue;
1164 : }
1165 :
1166 844 : vec<counters> *cands = table.get (e->dest);
1167 844 : gcc_assert (cands);
1168 844 : counters *prevp = find_counters (*cands, e);
1169 844 : gcc_assert (prevp);
1170 844 : counters prev = *prevp;
1171 844 : gimple_seq seq = NULL;
1172 :
1173 : /* _true &= ~mask, _false &= ~mask */
1174 844 : counters next;
1175 844 : next[2] = emit_bitwise_op (&seq, prev[2], BIT_NOT_EXPR);
1176 844 : next[0] = emit_bitwise_op (&seq, prev[0], BIT_AND_EXPR, next[2]);
1177 844 : next[1] = emit_bitwise_op (&seq, prev[1], BIT_AND_EXPR, next[2]);
1178 :
1179 : /* _global_true |= _true, _global_false |= _false */
1180 2532 : for (size_t k = 0; k != 2; ++k)
1181 : {
1182 1688 : if (integer_zerop (next[k]))
1183 739 : continue;
1184 949 : tree ref = tree_coverage_counter_ref (GCOV_COUNTER_CONDS,
1185 : 2 * condno + k);
1186 949 : if (atomic)
1187 : {
1188 15 : ref = unshare_expr (ref);
1189 15 : gcall *flush = gimple_build_call (atomic_ior, 3,
1190 : build_addr (ref),
1191 15 : next[k], relaxed);
1192 15 : gimple_seq_add_stmt (&seq, flush);
1193 : }
1194 : else
1195 : {
1196 934 : tree get = emit_assign (&seq, ref);
1197 934 : tree put = emit_bitwise_op (&seq, next[k], BIT_IOR_EXPR, get);
1198 934 : emit_assign (&seq, unshare_expr (ref), put);
1199 : }
1200 : }
1201 844 : if (seq)
1202 844 : gsi_insert_seq_on_edge (e, seq);
1203 : }
1204 : }
1205 :
1206 297 : return xi;
1207 297 : }
1208 :
1209 : #undef CONDITIONS_MAX_TERMS
1210 : #undef EDGE_CONDITION
1211 :
1212 : /* Do initialization work for the edge profiler. */
1213 :
1214 : /* Add code:
1215 : __thread gcov *__gcov_indirect_call.counters; // pointer to actual counter
1216 : __thread void *__gcov_indirect_call.callee; // actual callee address
1217 : __thread int __gcov_function_counter; // time profiler function counter */
1218 : static void
1219 437 : init_ic_make_global_vars (void)
1220 : {
1221 437 : tree gcov_type_ptr;
1222 :
1223 437 : gcov_type_ptr = build_pointer_type (get_gcov_type ());
1224 :
1225 437 : tree tuple_type = lang_hooks.types.make_type (RECORD_TYPE);
1226 :
1227 : /* callee */
1228 437 : ic_tuple_callee_field = build_decl (BUILTINS_LOCATION, FIELD_DECL, NULL_TREE,
1229 : ptr_type_node);
1230 :
1231 : /* counters */
1232 437 : ic_tuple_counters_field = build_decl (BUILTINS_LOCATION, FIELD_DECL,
1233 : NULL_TREE, gcov_type_ptr);
1234 437 : DECL_CHAIN (ic_tuple_counters_field) = ic_tuple_callee_field;
1235 :
1236 437 : finish_builtin_struct (tuple_type, "indirect_call_tuple",
1237 : ic_tuple_counters_field, NULL_TREE);
1238 :
1239 437 : ic_tuple_var
1240 437 : = build_decl (UNKNOWN_LOCATION, VAR_DECL,
1241 : get_identifier ("__gcov_indirect_call"), tuple_type);
1242 437 : TREE_PUBLIC (ic_tuple_var) = 1;
1243 437 : DECL_ARTIFICIAL (ic_tuple_var) = 1;
1244 437 : DECL_INITIAL (ic_tuple_var) = NULL;
1245 437 : DECL_EXTERNAL (ic_tuple_var) = 1;
1246 437 : if (targetm.have_tls)
1247 437 : set_decl_tls_model (ic_tuple_var, decl_default_tls_model (ic_tuple_var));
1248 437 : }
1249 :
1250 : /* Create the type and function decls for the interface with gcov. */
1251 :
1252 : void
1253 2564 : gimple_init_gcov_profiler (void)
1254 : {
1255 2564 : tree interval_profiler_fn_type;
1256 2564 : tree pow2_profiler_fn_type;
1257 2564 : tree topn_values_profiler_fn_type;
1258 2564 : tree gcov_type_ptr;
1259 2564 : tree ic_profiler_fn_type;
1260 2564 : tree average_profiler_fn_type;
1261 2564 : const char *fn_name;
1262 :
1263 2564 : if (!gcov_type_node)
1264 : {
1265 416 : const char *fn_suffix
1266 437 : = flag_profile_update == PROFILE_UPDATE_ATOMIC ? "_atomic" : "";
1267 :
1268 437 : gcov_type_node = get_gcov_type ();
1269 437 : gcov_type_ptr = build_pointer_type (gcov_type_node);
1270 :
1271 : /* void (*) (gcov_type *, gcov_type, int, unsigned) */
1272 437 : interval_profiler_fn_type
1273 437 : = build_function_type_list (void_type_node,
1274 : gcov_type_ptr, gcov_type_node,
1275 : integer_type_node,
1276 : unsigned_type_node, NULL_TREE);
1277 437 : fn_name = concat ("__gcov_interval_profiler", fn_suffix, NULL);
1278 437 : tree_interval_profiler_fn = build_fn_decl (fn_name,
1279 : interval_profiler_fn_type);
1280 437 : free (const_cast<char *> (fn_name));
1281 437 : TREE_NOTHROW (tree_interval_profiler_fn) = 1;
1282 437 : DECL_ATTRIBUTES (tree_interval_profiler_fn)
1283 437 : = tree_cons (get_identifier ("leaf"), NULL,
1284 437 : DECL_ATTRIBUTES (tree_interval_profiler_fn));
1285 :
1286 : /* void (*) (gcov_type *, gcov_type) */
1287 437 : pow2_profiler_fn_type
1288 437 : = build_function_type_list (void_type_node,
1289 : gcov_type_ptr, gcov_type_node,
1290 : NULL_TREE);
1291 437 : fn_name = concat ("__gcov_pow2_profiler", fn_suffix, NULL);
1292 437 : tree_pow2_profiler_fn = build_fn_decl (fn_name, pow2_profiler_fn_type);
1293 437 : free (const_cast<char *> (fn_name));
1294 437 : TREE_NOTHROW (tree_pow2_profiler_fn) = 1;
1295 437 : DECL_ATTRIBUTES (tree_pow2_profiler_fn)
1296 437 : = tree_cons (get_identifier ("leaf"), NULL,
1297 437 : DECL_ATTRIBUTES (tree_pow2_profiler_fn));
1298 :
1299 : /* void (*) (gcov_type *, gcov_type) */
1300 437 : topn_values_profiler_fn_type
1301 437 : = build_function_type_list (void_type_node,
1302 : gcov_type_ptr, gcov_type_node,
1303 : NULL_TREE);
1304 437 : fn_name = concat ("__gcov_topn_values_profiler", fn_suffix, NULL);
1305 437 : tree_topn_values_profiler_fn
1306 437 : = build_fn_decl (fn_name, topn_values_profiler_fn_type);
1307 437 : free (const_cast<char *> (fn_name));
1308 :
1309 437 : TREE_NOTHROW (tree_topn_values_profiler_fn) = 1;
1310 437 : DECL_ATTRIBUTES (tree_topn_values_profiler_fn)
1311 437 : = tree_cons (get_identifier ("leaf"), NULL,
1312 437 : DECL_ATTRIBUTES (tree_topn_values_profiler_fn));
1313 :
1314 437 : init_ic_make_global_vars ();
1315 :
1316 : /* void (*) (gcov_type, void *) */
1317 437 : ic_profiler_fn_type
1318 437 : = build_function_type_list (void_type_node,
1319 : gcov_type_node,
1320 : ptr_type_node,
1321 : NULL_TREE);
1322 437 : fn_name = concat ("__gcov_indirect_call_profiler_v4", fn_suffix, NULL);
1323 437 : tree_indirect_call_profiler_fn
1324 437 : = build_fn_decl (fn_name, ic_profiler_fn_type);
1325 437 : free (const_cast<char *> (fn_name));
1326 :
1327 437 : TREE_NOTHROW (tree_indirect_call_profiler_fn) = 1;
1328 437 : DECL_ATTRIBUTES (tree_indirect_call_profiler_fn)
1329 437 : = tree_cons (get_identifier ("leaf"), NULL,
1330 437 : DECL_ATTRIBUTES (tree_indirect_call_profiler_fn));
1331 :
1332 437 : tree_time_profiler_counter
1333 437 : = build_decl (UNKNOWN_LOCATION, VAR_DECL,
1334 : get_identifier ("__gcov_time_profiler_counter"),
1335 : get_gcov_type ());
1336 437 : TREE_PUBLIC (tree_time_profiler_counter) = 1;
1337 437 : DECL_EXTERNAL (tree_time_profiler_counter) = 1;
1338 437 : TREE_STATIC (tree_time_profiler_counter) = 1;
1339 437 : DECL_ARTIFICIAL (tree_time_profiler_counter) = 1;
1340 437 : DECL_INITIAL (tree_time_profiler_counter) = NULL;
1341 :
1342 : /* void (*) (gcov_type *, gcov_type) */
1343 437 : average_profiler_fn_type
1344 437 : = build_function_type_list (void_type_node,
1345 : gcov_type_ptr, gcov_type_node, NULL_TREE);
1346 437 : fn_name = concat ("__gcov_average_profiler", fn_suffix, NULL);
1347 437 : tree_average_profiler_fn = build_fn_decl (fn_name,
1348 : average_profiler_fn_type);
1349 437 : free (const_cast<char *> (fn_name));
1350 437 : TREE_NOTHROW (tree_average_profiler_fn) = 1;
1351 437 : DECL_ATTRIBUTES (tree_average_profiler_fn)
1352 437 : = tree_cons (get_identifier ("leaf"), NULL,
1353 437 : DECL_ATTRIBUTES (tree_average_profiler_fn));
1354 437 : fn_name = concat ("__gcov_ior_profiler", fn_suffix, NULL);
1355 437 : tree_ior_profiler_fn = build_fn_decl (fn_name, average_profiler_fn_type);
1356 437 : free (const_cast<char *> (fn_name));
1357 437 : TREE_NOTHROW (tree_ior_profiler_fn) = 1;
1358 437 : DECL_ATTRIBUTES (tree_ior_profiler_fn)
1359 437 : = tree_cons (get_identifier ("leaf"), NULL,
1360 437 : DECL_ATTRIBUTES (tree_ior_profiler_fn));
1361 :
1362 : /* LTO streamer needs assembler names. Because we create these decls
1363 : late, we need to initialize them by hand. */
1364 437 : DECL_ASSEMBLER_NAME (tree_interval_profiler_fn);
1365 437 : DECL_ASSEMBLER_NAME (tree_pow2_profiler_fn);
1366 437 : DECL_ASSEMBLER_NAME (tree_topn_values_profiler_fn);
1367 437 : DECL_ASSEMBLER_NAME (tree_indirect_call_profiler_fn);
1368 437 : DECL_ASSEMBLER_NAME (tree_average_profiler_fn);
1369 437 : DECL_ASSEMBLER_NAME (tree_ior_profiler_fn);
1370 : }
1371 2564 : }
1372 :
1373 : /* If RESULT is not null, then output instructions as GIMPLE trees to assign
1374 : the updated counter from CALL of FUNC to RESULT. Insert the CALL and the
1375 : optional assignment instructions to GSI. Use NAME for temporary values. */
1376 :
1377 : static inline void
1378 557 : gen_assign_counter_update (gimple_stmt_iterator *gsi, gcall *call, tree func,
1379 : tree result, const char *name)
1380 : {
1381 557 : if (result)
1382 : {
1383 19 : tree result_type = TREE_TYPE (TREE_TYPE (func));
1384 19 : tree tmp1 = make_temp_ssa_name (result_type, NULL, name);
1385 19 : gimple_set_lhs (call, tmp1);
1386 19 : gsi_insert_after (gsi, call, GSI_NEW_STMT);
1387 19 : tree tmp2 = make_temp_ssa_name (TREE_TYPE (result), NULL, name);
1388 19 : gassign *assign = gimple_build_assign (tmp2, NOP_EXPR, tmp1);
1389 19 : gsi_insert_after (gsi, assign, GSI_NEW_STMT);
1390 19 : assign = gimple_build_assign (result, tmp2);
1391 19 : gsi_insert_after (gsi, assign, GSI_NEW_STMT);
1392 : }
1393 : else
1394 538 : gsi_insert_after (gsi, call, GSI_NEW_STMT);
1395 557 : }
1396 :
1397 : /* Output instructions as GIMPLE trees to increment the COUNTER. If RESULT is
1398 : not null, then assign the updated counter value to RESULT. Insert the
1399 : instructions to GSI. Use NAME for temporary values. */
1400 :
1401 : static inline void
1402 6919 : gen_counter_update (gimple_stmt_iterator *gsi, tree counter, tree result,
1403 : const char *name)
1404 : {
1405 6919 : tree type = gcov_type_node;
1406 6919 : tree addr = build_fold_addr_expr (counter);
1407 6919 : tree one = build_int_cst (type, 1);
1408 6919 : tree relaxed = build_int_cst (integer_type_node, MEMMODEL_RELAXED);
1409 :
1410 6919 : if (counter_update == COUNTER_UPDATE_ATOMIC_BUILTIN
1411 6362 : || (result && counter_update == COUNTER_UPDATE_ATOMIC_SPLIT))
1412 : {
1413 : /* __atomic_fetch_add (&counter, 1, MEMMODEL_RELAXED); */
1414 557 : tree f = builtin_decl_explicit (TYPE_PRECISION (type) > 32
1415 : ? BUILT_IN_ATOMIC_ADD_FETCH_8
1416 : : BUILT_IN_ATOMIC_ADD_FETCH_4);
1417 557 : gcall *call = gimple_build_call (f, 3, addr, one, relaxed);
1418 557 : gen_assign_counter_update (gsi, call, f, result, name);
1419 557 : }
1420 5791 : else if (!result && (counter_update == COUNTER_UPDATE_ATOMIC_SPLIT
1421 5791 : || counter_update == COUNTER_UPDATE_ATOMIC_PARTIAL))
1422 : {
1423 : /* low = __atomic_add_fetch_4 (addr, 1, MEMMODEL_RELAXED);
1424 : high_inc = low == 0 ? 1 : 0;
1425 : __atomic_add_fetch_4 (addr_high, high_inc, MEMMODEL_RELAXED); */
1426 0 : tree zero32 = build_zero_cst (uint32_type_node);
1427 0 : tree one32 = build_one_cst (uint32_type_node);
1428 0 : tree addr_high = make_temp_ssa_name (TREE_TYPE (addr), NULL, name);
1429 0 : tree four = build_int_cst (size_type_node, 4);
1430 0 : gassign *assign1 = gimple_build_assign (addr_high, POINTER_PLUS_EXPR,
1431 : addr, four);
1432 0 : gsi_insert_after (gsi, assign1, GSI_NEW_STMT);
1433 0 : if (WORDS_BIG_ENDIAN)
1434 : std::swap (addr, addr_high);
1435 0 : tree f = builtin_decl_explicit (BUILT_IN_ATOMIC_ADD_FETCH_4);
1436 0 : gcall *call1 = gimple_build_call (f, 3, addr, one, relaxed);
1437 0 : tree low = make_temp_ssa_name (uint32_type_node, NULL, name);
1438 0 : gimple_call_set_lhs (call1, low);
1439 0 : gsi_insert_after (gsi, call1, GSI_NEW_STMT);
1440 0 : tree is_zero = make_temp_ssa_name (boolean_type_node, NULL, name);
1441 0 : gassign *assign2 = gimple_build_assign (is_zero, EQ_EXPR, low,
1442 : zero32);
1443 0 : gsi_insert_after (gsi, assign2, GSI_NEW_STMT);
1444 0 : tree high_inc = make_temp_ssa_name (uint32_type_node, NULL, name);
1445 0 : gassign *assign3 = gimple_build_assign (high_inc, COND_EXPR,
1446 : is_zero, one32, zero32);
1447 0 : gsi_insert_after (gsi, assign3, GSI_NEW_STMT);
1448 0 : gcall *call2 = gimple_build_call (f, 3, addr_high, high_inc,
1449 : relaxed);
1450 0 : gsi_insert_after (gsi, call2, GSI_NEW_STMT);
1451 0 : }
1452 : else
1453 : {
1454 6362 : tree tmp1 = make_temp_ssa_name (type, NULL, name);
1455 6362 : gassign *assign1 = gimple_build_assign (tmp1, counter);
1456 6362 : gsi_insert_after (gsi, assign1, GSI_NEW_STMT);
1457 6362 : tree tmp2 = make_temp_ssa_name (type, NULL, name);
1458 6362 : gassign *assign2 = gimple_build_assign (tmp2, PLUS_EXPR, tmp1, one);
1459 6362 : gsi_insert_after (gsi, assign2, GSI_NEW_STMT);
1460 6362 : gassign *assign3 = gimple_build_assign (unshare_expr (counter), tmp2);
1461 6362 : gsi_insert_after (gsi, assign3, GSI_NEW_STMT);
1462 6362 : if (result)
1463 : {
1464 571 : gassign *assign4 = gimple_build_assign (result, tmp2);
1465 571 : gsi_insert_after (gsi, assign4, GSI_NEW_STMT);
1466 : }
1467 : }
1468 6919 : }
1469 :
1470 : /* Output instructions as GIMPLE trees to increment the edge
1471 : execution count, and insert them on E. */
1472 :
1473 : void
1474 6329 : gimple_gen_edge_profiler (int edgeno, edge e)
1475 : {
1476 6329 : gimple_stmt_iterator gsi = gsi_last (PENDING_STMT (e));
1477 6329 : tree counter = tree_coverage_counter_ref (GCOV_COUNTER_ARCS, edgeno);
1478 6329 : gen_counter_update (&gsi, counter, NULL_TREE, "PROF_edge_counter");
1479 6329 : }
1480 :
1481 : /* Emits code to get VALUE to instrument at GSI, and returns the
1482 : variable containing the value. */
1483 :
1484 : static tree
1485 146 : prepare_instrumented_value (gimple_stmt_iterator *gsi, histogram_value value)
1486 : {
1487 146 : tree val = value->hvalue.value;
1488 146 : if (POINTER_TYPE_P (TREE_TYPE (val)))
1489 41 : val = fold_convert (build_nonstandard_integer_type
1490 : (TYPE_PRECISION (TREE_TYPE (val)), 1), val);
1491 146 : return force_gimple_operand_gsi (gsi, fold_convert (gcov_type_node, val),
1492 146 : true, NULL_TREE, true, GSI_SAME_STMT);
1493 : }
1494 :
1495 : /* Output instructions as GIMPLE trees to increment the interval histogram
1496 : counter. VALUE is the expression whose value is profiled. TAG is the
1497 : tag of the section for counters, BASE is offset of the counter position. */
1498 :
1499 : void
1500 5 : gimple_gen_interval_profiler (histogram_value value, unsigned tag)
1501 : {
1502 5 : gimple *stmt = value->hvalue.stmt;
1503 5 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1504 5 : tree ref = tree_coverage_counter_ref (tag, 0), ref_ptr;
1505 5 : gcall *call;
1506 5 : tree val;
1507 10 : tree start = build_int_cst_type (integer_type_node,
1508 5 : value->hdata.intvl.int_start);
1509 10 : tree steps = build_int_cst_type (unsigned_type_node,
1510 5 : value->hdata.intvl.steps);
1511 :
1512 5 : ref_ptr = force_gimple_operand_gsi (&gsi,
1513 : build_addr (ref),
1514 : true, NULL_TREE, true, GSI_SAME_STMT);
1515 5 : val = prepare_instrumented_value (&gsi, value);
1516 5 : call = gimple_build_call (tree_interval_profiler_fn, 4,
1517 : ref_ptr, val, start, steps);
1518 5 : gsi_insert_before (&gsi, call, GSI_NEW_STMT);
1519 5 : }
1520 :
1521 : /* Output instructions as GIMPLE trees to increment the power of two histogram
1522 : counter. VALUE is the expression whose value is profiled. TAG is the tag
1523 : of the section for counters. */
1524 :
1525 : void
1526 5 : gimple_gen_pow2_profiler (histogram_value value, unsigned tag)
1527 : {
1528 5 : gimple *stmt = value->hvalue.stmt;
1529 5 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1530 5 : tree ref_ptr = tree_coverage_counter_addr (tag, 0);
1531 5 : gcall *call;
1532 5 : tree val;
1533 :
1534 5 : ref_ptr = force_gimple_operand_gsi (&gsi, ref_ptr,
1535 : true, NULL_TREE, true, GSI_SAME_STMT);
1536 5 : val = prepare_instrumented_value (&gsi, value);
1537 5 : call = gimple_build_call (tree_pow2_profiler_fn, 2, ref_ptr, val);
1538 5 : gsi_insert_before (&gsi, call, GSI_NEW_STMT);
1539 5 : }
1540 :
1541 : /* Output instructions as GIMPLE trees for code to find the most N common
1542 : values. VALUE is the expression whose value is profiled. TAG is the tag
1543 : of the section for counters. */
1544 :
1545 : void
1546 54 : gimple_gen_topn_values_profiler (histogram_value value, unsigned tag)
1547 : {
1548 54 : gimple *stmt = value->hvalue.stmt;
1549 54 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1550 54 : tree ref_ptr = tree_coverage_counter_addr (tag, 0);
1551 54 : gcall *call;
1552 54 : tree val;
1553 :
1554 54 : ref_ptr = force_gimple_operand_gsi (&gsi, ref_ptr,
1555 : true, NULL_TREE, true, GSI_SAME_STMT);
1556 54 : val = prepare_instrumented_value (&gsi, value);
1557 54 : call = gimple_build_call (tree_topn_values_profiler_fn, 2, ref_ptr, val);
1558 54 : gsi_insert_before (&gsi, call, GSI_NEW_STMT);
1559 54 : }
1560 :
1561 :
1562 : /* Output instructions as GIMPLE trees for code to find the most
1563 : common called function in indirect call.
1564 : VALUE is the call expression whose indirect callee is profiled.
1565 : TAG is the tag of the section for counters. */
1566 :
1567 : void
1568 49 : gimple_gen_ic_profiler (histogram_value value, unsigned tag)
1569 : {
1570 49 : tree tmp1;
1571 49 : gassign *stmt1, *stmt2, *stmt3;
1572 49 : gimple *stmt = value->hvalue.stmt;
1573 49 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1574 49 : tree ref_ptr = tree_coverage_counter_addr (tag, 0);
1575 :
1576 49 : ref_ptr = force_gimple_operand_gsi (&gsi, ref_ptr,
1577 : true, NULL_TREE, true, GSI_SAME_STMT);
1578 :
1579 : /* Insert code:
1580 :
1581 : stmt1: __gcov_indirect_call.counters = get_relevant_counter_ptr ();
1582 : stmt2: tmp1 = (void *) (indirect call argument value)
1583 : stmt3: __gcov_indirect_call.callee = tmp1;
1584 :
1585 : Example:
1586 : f_1 = foo;
1587 : __gcov_indirect_call.counters = &__gcov4.main[0];
1588 : PROF_fn_9 = f_1;
1589 : __gcov_indirect_call.callee = PROF_fn_9;
1590 : _4 = f_1 ();
1591 : */
1592 :
1593 49 : tree gcov_type_ptr = build_pointer_type (get_gcov_type ());
1594 :
1595 49 : tree counter_ref = build3 (COMPONENT_REF, gcov_type_ptr,
1596 : ic_tuple_var, ic_tuple_counters_field, NULL_TREE);
1597 :
1598 49 : stmt1 = gimple_build_assign (counter_ref, ref_ptr);
1599 49 : tmp1 = make_temp_ssa_name (ptr_type_node, NULL, "PROF_fn");
1600 49 : stmt2 = gimple_build_assign (tmp1, unshare_expr (value->hvalue.value));
1601 49 : tree callee_ref = build3 (COMPONENT_REF, ptr_type_node,
1602 : ic_tuple_var, ic_tuple_callee_field, NULL_TREE);
1603 49 : stmt3 = gimple_build_assign (callee_ref, tmp1);
1604 :
1605 49 : gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
1606 49 : gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
1607 49 : gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
1608 49 : }
1609 :
1610 :
1611 : /* Output instructions as GIMPLE trees for code to find the most
1612 : common called function in indirect call. Insert instructions at the
1613 : beginning of every possible called function.
1614 : */
1615 :
1616 : void
1617 589 : gimple_gen_ic_func_profiler (void)
1618 : {
1619 589 : struct cgraph_node * c_node = cgraph_node::get (current_function_decl);
1620 589 : gcall *stmt1;
1621 589 : tree tree_uid, cur_func, void0;
1622 :
1623 : /* Disable indirect call profiling for an IFUNC resolver and its
1624 : callees since it requires TLS which hasn't been set up yet when
1625 : the dynamic linker is resolving IFUNC symbols. See
1626 : https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114115
1627 : */
1628 589 : if (c_node->only_called_directly_p ()
1629 589 : || c_node->called_by_ifunc_resolver)
1630 36 : return;
1631 :
1632 553 : gimple_init_gcov_profiler ();
1633 :
1634 553 : basic_block entry = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1635 553 : basic_block cond_bb = split_edge (single_succ_edge (entry));
1636 553 : basic_block update_bb = split_edge (single_succ_edge (cond_bb));
1637 :
1638 : /* We need to do an extra split in order to not create an input
1639 : for a possible PHI node. */
1640 553 : split_edge (single_succ_edge (update_bb));
1641 :
1642 553 : edge true_edge = single_succ_edge (cond_bb);
1643 553 : true_edge->flags = EDGE_TRUE_VALUE;
1644 :
1645 553 : profile_probability probability;
1646 553 : if (DECL_VIRTUAL_P (current_function_decl))
1647 11 : probability = profile_probability::very_likely ();
1648 : else
1649 542 : probability = profile_probability::unlikely ();
1650 :
1651 553 : true_edge->probability = probability;
1652 553 : edge e = make_edge (cond_bb, single_succ_edge (update_bb)->dest,
1653 : EDGE_FALSE_VALUE);
1654 553 : e->probability = true_edge->probability.invert ();
1655 :
1656 : /* Insert code:
1657 :
1658 : if (__gcov_indirect_call.callee != NULL)
1659 : __gcov_indirect_call_profiler_v3 (profile_id, ¤t_function_decl);
1660 :
1661 : The function __gcov_indirect_call_profiler_v3 is responsible for
1662 : resetting __gcov_indirect_call.callee to NULL. */
1663 :
1664 553 : gimple_stmt_iterator gsi = gsi_start_bb (cond_bb);
1665 553 : void0 = build_int_cst (ptr_type_node, 0);
1666 :
1667 553 : tree callee_ref = build3 (COMPONENT_REF, ptr_type_node,
1668 : ic_tuple_var, ic_tuple_callee_field, NULL_TREE);
1669 :
1670 553 : tree ref = force_gimple_operand_gsi (&gsi, callee_ref, true, NULL_TREE,
1671 : true, GSI_SAME_STMT);
1672 :
1673 553 : gcond *cond = gimple_build_cond (NE_EXPR, ref,
1674 : void0, NULL, NULL);
1675 553 : gsi_insert_before (&gsi, cond, GSI_NEW_STMT);
1676 :
1677 553 : gsi = gsi_after_labels (update_bb);
1678 :
1679 553 : cur_func = force_gimple_operand_gsi (&gsi,
1680 : build_addr (current_function_decl),
1681 : true, NULL_TREE,
1682 : true, GSI_SAME_STMT);
1683 553 : tree_uid = build_int_cst
1684 553 : (gcov_type_node,
1685 553 : cgraph_node::get (current_function_decl)->profile_id);
1686 553 : stmt1 = gimple_build_call (tree_indirect_call_profiler_fn, 2,
1687 : tree_uid, cur_func);
1688 553 : gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
1689 : }
1690 :
1691 : /* Output instructions as GIMPLE tree at the beginning for each function.
1692 : TAG is the tag of the section for counters, BASE is offset of the
1693 : counter position and GSI is the iterator we place the counter. */
1694 :
1695 : void
1696 590 : gimple_gen_time_profiler (unsigned tag)
1697 : {
1698 590 : tree type = get_gcov_type ();
1699 590 : basic_block entry = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1700 590 : basic_block cond_bb = split_edge (single_succ_edge (entry));
1701 590 : basic_block update_bb = split_edge (single_succ_edge (cond_bb));
1702 :
1703 : /* We need to do an extra split in order to not create an input
1704 : for a possible PHI node. */
1705 590 : split_edge (single_succ_edge (update_bb));
1706 :
1707 590 : edge true_edge = single_succ_edge (cond_bb);
1708 590 : true_edge->flags = EDGE_TRUE_VALUE;
1709 590 : true_edge->probability = profile_probability::unlikely ();
1710 590 : edge e
1711 590 : = make_edge (cond_bb, single_succ_edge (update_bb)->dest, EDGE_FALSE_VALUE);
1712 590 : e->probability = true_edge->probability.invert ();
1713 :
1714 590 : gimple_stmt_iterator gsi = gsi_start_bb (cond_bb);
1715 590 : tree original_ref = tree_coverage_counter_ref (tag, 0);
1716 590 : tree ref = force_gimple_operand_gsi (&gsi, original_ref, true, NULL_TREE,
1717 : true, GSI_SAME_STMT);
1718 :
1719 : /* Emit: if (counters[0] != 0). */
1720 590 : gcond *cond = gimple_build_cond (EQ_EXPR, ref, build_int_cst (type, 0),
1721 : NULL, NULL);
1722 590 : gsi_insert_before (&gsi, cond, GSI_NEW_STMT);
1723 :
1724 : /* Emit: counters[0] = ++__gcov_time_profiler_counter. */
1725 590 : gsi = gsi_start_bb (update_bb);
1726 590 : gen_counter_update (&gsi, tree_time_profiler_counter, original_ref,
1727 : "PROF_time_profile");
1728 590 : }
1729 :
1730 : /* Output instructions as GIMPLE trees to increment the average histogram
1731 : counter. VALUE is the expression whose value is profiled. TAG is the
1732 : tag of the section for counters, BASE is offset of the counter position. */
1733 :
1734 : void
1735 41 : gimple_gen_average_profiler (histogram_value value, unsigned tag)
1736 : {
1737 41 : gimple *stmt = value->hvalue.stmt;
1738 41 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1739 41 : tree ref_ptr = tree_coverage_counter_addr (tag, 0);
1740 41 : gcall *call;
1741 41 : tree val;
1742 :
1743 41 : ref_ptr = force_gimple_operand_gsi (&gsi, ref_ptr,
1744 : true, NULL_TREE,
1745 : true, GSI_SAME_STMT);
1746 41 : val = prepare_instrumented_value (&gsi, value);
1747 41 : call = gimple_build_call (tree_average_profiler_fn, 2, ref_ptr, val);
1748 41 : gsi_insert_before (&gsi, call, GSI_NEW_STMT);
1749 41 : }
1750 :
1751 : /* Output instructions as GIMPLE trees to increment the ior histogram
1752 : counter. VALUE is the expression whose value is profiled. TAG is the
1753 : tag of the section for counters, BASE is offset of the counter position. */
1754 :
1755 : void
1756 41 : gimple_gen_ior_profiler (histogram_value value, unsigned tag)
1757 : {
1758 41 : gimple *stmt = value->hvalue.stmt;
1759 41 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1760 41 : tree ref_ptr = tree_coverage_counter_addr (tag, 0);
1761 41 : gcall *call;
1762 41 : tree val;
1763 :
1764 41 : ref_ptr = force_gimple_operand_gsi (&gsi, ref_ptr,
1765 : true, NULL_TREE, true, GSI_SAME_STMT);
1766 41 : val = prepare_instrumented_value (&gsi, value);
1767 41 : call = gimple_build_call (tree_ior_profiler_fn, 2, ref_ptr, val);
1768 41 : gsi_insert_before (&gsi, call, GSI_NEW_STMT);
1769 41 : }
1770 :
1771 : static vec<regex_t> profile_filter_files;
1772 : static vec<regex_t> profile_exclude_files;
1773 :
1774 : /* Parse list of provided REGEX (separated with semi-collon) and
1775 : create expressions (of type regex_t) and save them into V vector.
1776 : If there is a regular expression parsing error, error message is
1777 : printed for FLAG_NAME. */
1778 :
1779 : static void
1780 1230 : parse_profile_filter (const char *regex, vec<regex_t> *v,
1781 : const char *flag_name)
1782 : {
1783 1230 : v->create (4);
1784 1230 : if (regex != NULL)
1785 : {
1786 3 : char *str = xstrdup (regex);
1787 6 : for (char *p = strtok (str, ";"); p != NULL; p = strtok (NULL, ";"))
1788 : {
1789 3 : regex_t r;
1790 3 : if (regcomp (&r, p, REG_EXTENDED | REG_NOSUB) != 0)
1791 : {
1792 0 : error ("invalid regular expression %qs in %qs",
1793 : p, flag_name);
1794 0 : return;
1795 : }
1796 :
1797 3 : v->safe_push (r);
1798 : }
1799 : }
1800 : }
1801 :
1802 : /* Parse values of -fprofile-filter-files and -fprofile-exclude-files
1803 : options. */
1804 :
1805 : static void
1806 615 : parse_profile_file_filtering ()
1807 : {
1808 615 : parse_profile_filter (flag_profile_filter_files, &profile_filter_files,
1809 : "-fprofile-filter-files");
1810 615 : parse_profile_filter (flag_profile_exclude_files, &profile_exclude_files,
1811 : "-fprofile-exclude-files");
1812 615 : }
1813 :
1814 : /* Parse vectors of regular expressions. */
1815 :
1816 : static void
1817 615 : release_profile_file_filtering ()
1818 : {
1819 615 : profile_filter_files.release ();
1820 615 : profile_exclude_files.release ();
1821 615 : }
1822 :
1823 : /* Return true when FILENAME should be instrumented based on
1824 : -fprofile-filter-files and -fprofile-exclude-files options. */
1825 :
1826 : static bool
1827 2611 : include_source_file_for_profile (const char *filename)
1828 : {
1829 : /* First check whether file is included in flag_profile_exclude_files. */
1830 2611 : for (unsigned i = 0; i < profile_exclude_files.length (); i++)
1831 2 : if (regexec (&profile_exclude_files[i],
1832 : filename, 0, NULL, 0) == REG_NOERROR)
1833 : return false;
1834 :
1835 : /* For non-empty flag_profile_filter_files include only files matching a
1836 : regex in the flag. */
1837 5218 : if (profile_filter_files.is_empty ())
1838 : return true;
1839 :
1840 2 : for (unsigned i = 0; i < profile_filter_files.length (); i++)
1841 2 : if (regexec (&profile_filter_files[i], filename, 0, NULL, 0) == REG_NOERROR)
1842 : return true;
1843 :
1844 : return false;
1845 : }
1846 :
1847 : #ifndef HAVE_sync_compare_and_swapsi
1848 : #define HAVE_sync_compare_and_swapsi 0
1849 : #endif
1850 : #ifndef HAVE_atomic_compare_and_swapsi
1851 : #define HAVE_atomic_compare_and_swapsi 0
1852 : #endif
1853 :
1854 : #ifndef HAVE_sync_compare_and_swapdi
1855 : #define HAVE_sync_compare_and_swapdi 0
1856 : #endif
1857 : #ifndef HAVE_atomic_compare_and_swapdi
1858 : #define HAVE_atomic_compare_and_swapdi 0
1859 : #endif
1860 :
1861 : /* Profile all functions in the callgraph. */
1862 :
1863 : static unsigned int
1864 615 : tree_profiling (void)
1865 : {
1866 615 : struct cgraph_node *node;
1867 :
1868 615 : coverage_init_file ();
1869 :
1870 : /* Verify whether we can utilize atomic update operations. */
1871 615 : bool can_support_atomic = targetm.have_libatomic;
1872 615 : unsigned HOST_WIDE_INT gcov_type_size
1873 615 : = tree_to_uhwi (TYPE_SIZE_UNIT (get_gcov_type ()));
1874 615 : bool have_atomic_4
1875 615 : = HAVE_sync_compare_and_swapsi || HAVE_atomic_compare_and_swapsi;
1876 1230 : bool have_atomic_8
1877 615 : = HAVE_sync_compare_and_swapdi || HAVE_atomic_compare_and_swapdi;
1878 615 : bool needs_split = gcov_type_size == 8 && !have_atomic_8 && have_atomic_4;
1879 615 : if (!can_support_atomic)
1880 : {
1881 615 : if (gcov_type_size == 4)
1882 : can_support_atomic = have_atomic_4;
1883 615 : else if (gcov_type_size == 8)
1884 615 : can_support_atomic = have_atomic_8;
1885 : }
1886 :
1887 615 : if (flag_profile_update == PROFILE_UPDATE_ATOMIC
1888 14 : && !can_support_atomic)
1889 : {
1890 0 : if (needs_split)
1891 : {
1892 0 : warning (0, "target does not fully support atomic profile "
1893 : "update, single mode is selected with partial "
1894 : "atomic updates");
1895 0 : counter_update = COUNTER_UPDATE_ATOMIC_PARTIAL;
1896 : }
1897 : else
1898 0 : warning (0, "target does not support atomic profile update, "
1899 : "single mode is selected");
1900 0 : flag_profile_update = PROFILE_UPDATE_SINGLE;
1901 : }
1902 615 : else if (flag_profile_update == PROFILE_UPDATE_PREFER_ATOMIC)
1903 : {
1904 9 : if (can_support_atomic)
1905 9 : flag_profile_update = PROFILE_UPDATE_ATOMIC;
1906 : else
1907 : {
1908 0 : if (needs_split)
1909 0 : counter_update = COUNTER_UPDATE_ATOMIC_PARTIAL;
1910 0 : flag_profile_update = PROFILE_UPDATE_SINGLE;
1911 : }
1912 : }
1913 :
1914 615 : if (flag_profile_update == PROFILE_UPDATE_ATOMIC)
1915 : {
1916 23 : if (needs_split)
1917 0 : counter_update = COUNTER_UPDATE_ATOMIC_SPLIT;
1918 : else
1919 23 : counter_update = COUNTER_UPDATE_ATOMIC_BUILTIN;
1920 : }
1921 :
1922 : /* This is a small-ipa pass that gets called only once, from
1923 : cgraphunit.cc:ipa_passes(). */
1924 615 : gcc_assert (symtab->state == IPA_SSA);
1925 :
1926 615 : init_node_map (true);
1927 615 : parse_profile_file_filtering ();
1928 :
1929 3456 : FOR_EACH_DEFINED_FUNCTION (node)
1930 : {
1931 2841 : bool thunk = false;
1932 2841 : if (!gimple_has_body_p (node->decl) && !node->thunk)
1933 220 : continue;
1934 :
1935 : /* Don't profile functions produced for builtin stuff. */
1936 2621 : if (DECL_SOURCE_LOCATION (node->decl) == BUILTINS_LOCATION)
1937 0 : continue;
1938 :
1939 2621 : if (lookup_attribute ("no_profile_instrument_function",
1940 2621 : DECL_ATTRIBUTES (node->decl)))
1941 3 : continue;
1942 : /* Do not instrument extern inline functions when testing coverage.
1943 : While this is not perfectly consistent (early inlined extern inlines
1944 : will get accounted), testsuite expects that. */
1945 2618 : if (DECL_EXTERNAL (node->decl)
1946 2618 : && flag_test_coverage)
1947 7 : continue;
1948 :
1949 2611 : const char *file = LOCATION_FILE (DECL_SOURCE_LOCATION (node->decl));
1950 2611 : if (!include_source_file_for_profile (file))
1951 2 : continue;
1952 :
1953 2609 : if (node->thunk)
1954 : {
1955 : /* We cannot expand variadic thunks to Gimple. */
1956 14 : if (stdarg_p (TREE_TYPE (node->decl)))
1957 0 : continue;
1958 14 : thunk = true;
1959 : /* When generate profile, expand thunk to gimple so it can be
1960 : instrumented same way as other functions. */
1961 14 : if (coverage_instrumentation_p ())
1962 7 : expand_thunk (node, false, true);
1963 : /* Read cgraph profile but keep function as thunk at profile-use
1964 : time. */
1965 : else
1966 : {
1967 7 : read_thunk_profile (node);
1968 7 : continue;
1969 : }
1970 : }
1971 :
1972 2602 : push_cfun (DECL_STRUCT_FUNCTION (node->decl));
1973 :
1974 2602 : if (dump_file)
1975 181 : dump_function_header (dump_file, cfun->decl, dump_flags);
1976 :
1977 : /* Local pure-const may imply need to fixup the cfg. */
1978 2602 : if (gimple_has_body_p (node->decl)
1979 2602 : && (execute_fixup_cfg () & TODO_cleanup_cfg))
1980 230 : cleanup_tree_cfg ();
1981 :
1982 2602 : branch_prob (thunk);
1983 :
1984 2602 : if (! flag_branch_probabilities
1985 2022 : && flag_profile_values)
1986 589 : gimple_gen_ic_func_profiler ();
1987 :
1988 2602 : if (flag_branch_probabilities
1989 580 : && !thunk
1990 580 : && flag_profile_values
1991 434 : && flag_value_profile_transformations
1992 434 : && profile_status_for_fn (cfun) == PROFILE_READ)
1993 354 : gimple_value_profile_transformations ();
1994 :
1995 : /* The above could hose dominator info. Currently there is
1996 : none coming in, this is a safety valve. It should be
1997 : easy to adjust it, if and when there is some. */
1998 2602 : free_dominance_info (CDI_DOMINATORS);
1999 2602 : free_dominance_info (CDI_POST_DOMINATORS);
2000 2602 : pop_cfun ();
2001 : }
2002 :
2003 615 : release_profile_file_filtering ();
2004 :
2005 : /* Drop pure/const flags from instrumented functions. */
2006 615 : if (coverage_instrumentation_p () || flag_test_coverage)
2007 2688 : FOR_EACH_DEFINED_FUNCTION (node)
2008 : {
2009 2235 : if (!gimple_has_body_p (node->decl)
2010 2235 : || !(!node->clone_of
2011 0 : || node->decl != node->clone_of->decl))
2012 200 : continue;
2013 :
2014 : /* Don't profile functions produced for builtin stuff. */
2015 2035 : if (DECL_SOURCE_LOCATION (node->decl) == BUILTINS_LOCATION)
2016 0 : continue;
2017 :
2018 2035 : node->set_const_flag (false, false);
2019 2035 : node->set_pure_flag (false, false);
2020 : }
2021 :
2022 : /* Update call statements and rebuild the cgraph. */
2023 3456 : FOR_EACH_DEFINED_FUNCTION (node)
2024 : {
2025 2841 : basic_block bb;
2026 :
2027 2841 : if (!gimple_has_body_p (node->decl)
2028 2841 : || !(!node->clone_of
2029 0 : || node->decl != node->clone_of->decl))
2030 227 : continue;
2031 :
2032 : /* Don't profile functions produced for builtin stuff. */
2033 2614 : if (DECL_SOURCE_LOCATION (node->decl) == BUILTINS_LOCATION)
2034 0 : continue;
2035 :
2036 2614 : push_cfun (DECL_STRUCT_FUNCTION (node->decl));
2037 :
2038 2614 : if (coverage_instrumentation_p () || flag_test_coverage)
2039 17848 : FOR_EACH_BB_FN (bb, cfun)
2040 : {
2041 15813 : gimple_stmt_iterator gsi;
2042 82186 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2043 : {
2044 50560 : gcall *call = dyn_cast <gcall *> (gsi_stmt (gsi));
2045 4843 : if (!call || gimple_call_internal_p (call))
2046 45808 : continue;
2047 :
2048 : /* We do not clear pure/const on decls without body. */
2049 4752 : tree fndecl = gimple_call_fndecl (call);
2050 4752 : cgraph_node *callee;
2051 6828 : if (fndecl
2052 4694 : && (callee = cgraph_node::get (fndecl))
2053 9029 : && callee->get_availability (node) == AVAIL_NOT_AVAILABLE)
2054 2076 : continue;
2055 :
2056 : /* Drop the const attribute from the call type (the pure
2057 : attribute is not available on types). */
2058 2676 : tree fntype = gimple_call_fntype (call);
2059 2676 : if (fntype && TYPE_READONLY (fntype))
2060 : {
2061 1 : int quals = TYPE_QUALS (fntype) & ~TYPE_QUAL_CONST;
2062 1 : fntype = build_qualified_type (fntype, quals);
2063 1 : gimple_call_set_fntype (call, fntype);
2064 : }
2065 :
2066 : /* Update virtual operands of calls to no longer const/pure
2067 : functions. */
2068 2676 : update_stmt (call);
2069 : }
2070 : }
2071 :
2072 : /* re-merge split blocks. */
2073 2614 : cleanup_tree_cfg ();
2074 2614 : update_ssa (TODO_update_ssa);
2075 :
2076 2614 : cgraph_edge::rebuild_edges ();
2077 :
2078 2614 : pop_cfun ();
2079 : }
2080 :
2081 615 : handle_missing_profiles ();
2082 :
2083 615 : del_node_map ();
2084 615 : end_branch_prob ();
2085 615 : coverage_finish_file ();
2086 615 : return 0;
2087 : }
2088 :
2089 : namespace {
2090 :
2091 : const pass_data pass_data_ipa_tree_profile =
2092 : {
2093 : SIMPLE_IPA_PASS, /* type */
2094 : "profile", /* name */
2095 : OPTGROUP_NONE, /* optinfo_flags */
2096 : TV_IPA_PROFILE, /* tv_id */
2097 : 0, /* properties_required */
2098 : 0, /* properties_provided */
2099 : 0, /* properties_destroyed */
2100 : 0, /* todo_flags_start */
2101 : TODO_dump_symtab, /* todo_flags_finish */
2102 : };
2103 :
2104 : class pass_ipa_tree_profile : public simple_ipa_opt_pass
2105 : {
2106 : public:
2107 293828 : pass_ipa_tree_profile (gcc::context *ctxt)
2108 587656 : : simple_ipa_opt_pass (pass_data_ipa_tree_profile, ctxt)
2109 : {}
2110 :
2111 : /* opt_pass methods: */
2112 : bool gate (function *) final override;
2113 615 : unsigned int execute (function *) final override { return tree_profiling (); }
2114 :
2115 : }; // class pass_ipa_tree_profile
2116 :
2117 : bool
2118 236099 : pass_ipa_tree_profile::gate (function *)
2119 : {
2120 : /* When profile instrumentation, use or test coverage shall be performed. */
2121 236099 : return (!in_lto_p
2122 236099 : && (flag_branch_probabilities || flag_test_coverage
2123 235765 : || coverage_instrumentation_p ())
2124 236718 : && !seen_error ());
2125 : }
2126 :
2127 : } // anon namespace
2128 :
2129 : simple_ipa_opt_pass *
2130 293828 : make_pass_ipa_tree_profile (gcc::context *ctxt)
2131 : {
2132 293828 : return new pass_ipa_tree_profile (ctxt);
2133 : }
2134 :
2135 : #include "gt-tree-profile.h"
|
