/* Calculate branch probabilities, and basic block execution counts. Copyright (C) 1990-2024 Free Software Foundation, Inc. Contributed by James E. Wilson, UC Berkeley/Cygnus Support; based on some ideas from Dain Samples of UC Berkeley. Further mangling by Bob Manson, Cygnus Support. Converted to use trees by Dale Johannesen, Apple Computer. This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see . */ /* Generate basic block profile instrumentation and auxiliary files. Tree-based version. See profile.cc for overview. */ #include "config.h" #include "system.h" #include "coretypes.h" #include "memmodel.h" #include "backend.h" #include "target.h" #include "tree.h" #include "gimple.h" #include "cfghooks.h" #include "tree-pass.h" #include "ssa.h" #include "cgraph.h" #include "coverage.h" #include "diagnostic-core.h" #include "fold-const.h" #include "varasm.h" #include "tree-nested.h" #include "gimplify.h" #include "gimple-iterator.h" #include "gimplify-me.h" #include "tree-cfg.h" #include "tree-into-ssa.h" #include "value-prof.h" #include "profile.h" #include "tree-cfgcleanup.h" #include "stringpool.h" #include "attribs.h" #include "tree-pretty-print.h" #include "langhooks.h" #include "stor-layout.h" #include "xregex.h" #include "alloc-pool.h" #include "symbol-summary.h" #include "symtab-thunks.h" #include "cfganal.h" static GTY(()) tree gcov_type_node; static GTY(()) tree tree_interval_profiler_fn; static GTY(()) tree tree_pow2_profiler_fn; static GTY(()) tree tree_topn_values_profiler_fn; static GTY(()) tree tree_indirect_call_profiler_fn; static GTY(()) tree tree_average_profiler_fn; static GTY(()) tree tree_ior_profiler_fn; static GTY(()) tree tree_time_profiler_counter; static GTY(()) tree ic_tuple_var; static GTY(()) tree ic_tuple_counters_field; static GTY(()) tree ic_tuple_callee_field; /* Types of counter update methods. By default, the counter updates are done for a single threaded system (COUNTER_UPDATE_SINGLE_THREAD). If the user selected atomic profile counter updates (-fprofile-update=atomic), then the counter updates will be done atomically on a best-effort basis. One of three methods to do the counter updates is selected according to the target capabilities. Ideally, the counter updates are done through atomic operations in hardware (COUNTER_UPDATE_ATOMIC_BUILTIN). If the target supports only 32-bit atomic increments and gcov_type_node is a 64-bit integer type, then for the profile edge counters the increment is performed through two separate 32-bit atomic increments (COUNTER_UPDATE_ATOMIC_SPLIT or COUNTER_UPDATE_ATOMIC_PARTIAL). If the target supports libatomic (targetm.have_libatomic), then other counter updates are carried out by libatomic calls (COUNTER_UPDATE_ATOMIC_SPLIT). If the target does not support libatomic, then the other counter updates are not done atomically (COUNTER_UPDATE_ATOMIC_PARTIAL) and a warning is issued. If the target does not support atomic operations in hardware, however, it supports libatomic, then all updates are carried out by libatomic calls (COUNTER_UPDATE_ATOMIC_BUILTIN). */ enum counter_update_method { COUNTER_UPDATE_SINGLE_THREAD, COUNTER_UPDATE_ATOMIC_BUILTIN, COUNTER_UPDATE_ATOMIC_SPLIT, COUNTER_UPDATE_ATOMIC_PARTIAL }; static counter_update_method counter_update = COUNTER_UPDATE_SINGLE_THREAD; /* These functions support measuring modified conditition/decision coverage (MC/DC). MC/DC requires all of the below during testing: - Each entry and exit point is invoked - Each decision takes every possible outcome - Each condition in a decision takes every possible outcome - Each condition in a decision is shown to independently affect the outcome of the decision Independence of a condition is shown by recording it being evaluated to a value (true/false) and not being made irrelevant ("masked") by a later term. This feature adds some instrumentation code, a few bitwise operators, that records the branches taken in conditions and applies a filter for the masking effect. Masking is essentially short-circuiting in reverse: a condition does not contribute to the outcome if it would short circuit the (sub) expression if it was evaluated right-to-left, (_ && false) and (_ || true). The program is essentially rewritten this way: - if (a || b) { fn () } + if (a) { _t |= 0x1; goto _then; } + else { _f |= 0x1; + if (b) { _t |= 0x2; _mask |= 0x1; goto _then; } + else { _f |= 0x2; goto _else; } + _then: + _gcov_t |= (_t & _mask); + _gcov_f |= (_f & _mask); + fn (); goto _end; + _else: + _gcov_t |= (_t & _mask); + _gcov_f |= (_f & _mask); + fn (); + _end: It is assumed the front end will provide discrimnators so that conditional basic blocks (basic block with a conditional jump and outgoing true/false edges) that belong to the same Boolean expression have the same discriminator. Masking is determined by analyzing these expressions as a reduced order binary decision diagram. */ namespace { /* Some context and reused instances between function calls. Large embedded buffers are used to up-front request enough memory for most programs and merge them into a single allocation at the cost of using more memory in the average case. Some numbers from linux v5.13 which is assumed to be a reasonably diverse code base: 75% of the functions in linux have less than 16 nodes in the CFG and approx 2.5% have more than 64 nodes. The functions that go beyond a few dozen nodes tend to be very large (>100) and so 64 seems like a good balance. This is really just a performance balance of the cost of allocation and wasted memory. */ struct conds_ctx { /* This is both a reusable shared allocation which is also used to return single expressions, which means it for most code should only hold a couple of elements. */ auto_vec blocks; /* Index for the topological order indexed by basic_block->index to an ordering so that expression (a || b && c) => top_index[a] < top_index[b] < top_index[c]. */ auto_vec top_index; /* Pre-allocate bitmaps and vectors for per-function book keeping. This is pure instance reuse and the bitmaps carry no data between function calls. */ auto_vec B1; auto_vec B2; auto_sbitmap G1; auto_sbitmap G2; auto_sbitmap G3; explicit conds_ctx (unsigned size) noexcept (true) : G1 (size), G2 (size), G3 (size) { } }; /* Only instrument terms with fewer than number of bits in a (wide) gcov integer, which is probably 64. The algorithm itself does not impose this limitation, but it makes for a simpler implementation. * Allocating the output data structure (coverage_counter_alloc ()) can assume pairs of gcov_type_unsigned and not use a separate length field. * A pair gcov_type_unsigned can be used as accumulators. * Updating accumulators is can use the bitwise operations |=, &= and not custom operators that work for arbitrary-sized bit-sets. Most real-world code should be unaffected by this, but it is possible (especially for generated code) to exceed this limit. */ #define CONDITIONS_MAX_TERMS (TYPE_PRECISION (gcov_type_node)) #define EDGE_CONDITION (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE) /* Compare two basic blocks by their order in the expression i.e. for (a || b) then topological_cmp (a, b, ...) < 0. The result is undefined if LHS, RHS belong to different expressions. The TOP_INDEX argument should be the top_index vector from ctx. */ int topological_cmp (const void *lhs, const void *rhs, void *top_index) { const_basic_block l = *(const basic_block*) lhs; const_basic_block r = *(const basic_block*) rhs; const vec* im = (const vec*) top_index; return (*im)[l->index] - (*im)[r->index]; } /* Find the index of NEEDLE in BLOCKS; return -1 if not found. This has two uses, sometimes for the index and sometimes for set member checks. Sets are typically very small (number of conditions, >8 is uncommon) so linear search should be very fast. */ int index_of (const basic_block needle, array_slice blocks) { for (size_t i = 0; i < blocks.size (); i++) if (blocks[i] == needle) return int (i); return -1; } /* Special cases of the single_*_p and single_*_edge functions in basic-block.h that don't consider exception handling or other complex edges. This helps create a view of the CFG with only normal edges - if a basic block has both an outgoing fallthrough and exceptional edge, it should be considered a single-successor. */ bool single_p (const vec *edges) { int n = EDGE_COUNT (edges); if (n == 0) return false; for (edge e : edges) if (e->flags & EDGE_COMPLEX) n -= 1; return n == 1; } /* Get the single, non-complex edge. Behavior is undefined edges have more than 1 non-complex edges. */ edge single_edge (const vec *edges) { gcc_checking_assert (single_p (edges)); for (edge e : edges) { if (e->flags & EDGE_COMPLEX) continue; return e; } return NULL; } /* Sometimes, for example with function calls, goto labels, and C++ destructors, the CFG gets extra nodes that are essentially single-entry single-exit in the middle of boolean expressions. For example: x || can_throw (y) A /| / | B | | | C | / \ | / \| F T Without the extra node inserted by the function + exception it becomes a proper 2-term graph, not 2 single-term graphs. A /| C | / \| F T This function finds the source edge of these paths. This is often the identity function. */ edge contract_edge_up (edge e) { while (true) { basic_block src = e->src; if (!single_p (src->preds)) return e; if (!single_p (src->succs)) return e; e = single_edge (src->preds); } } /* A simple struct for storing/returning outcome block pairs. Either both blocks are set or both are NULL. */ struct outcomes { basic_block t = NULL; basic_block f = NULL; operator bool () const noexcept (true) { return t && f; } }; /* Get the true/false successors of a basic block. If b is not a conditional block both edges are NULL. */ outcomes conditional_succs (const basic_block b) { outcomes c; for (edge e : b->succs) { if (e->flags & EDGE_TRUE_VALUE) c.t = e->dest; if (e->flags & EDGE_FALSE_VALUE) c.f = e->dest; } gcc_assert ((c.t && c.f) || (!c.t && !c.f)); return c; } /* Get the index or offset of a conditional flag, 0 for true and 1 for false. These indices carry no semantics but must be consistent as they are used to index into data structures in code generation and gcov. */ unsigned condition_index (unsigned flag) { return (flag & EDGE_CONDITION) == EDGE_TRUE_VALUE ? 0 : 1; } /* Returns the condition identifier for the basic block if set, otherwise 0. This is only meaningful in GIMPLE and is used for condition coverage. There may be conditions created that did not get an uid, such as those implicitly created by destructors. We could include them in the condition coverage for completeness (i.e. condition coverage implies (implicit) branch coverage), but they have no natural buckets and should all be single-term. For now these are ignored and given uid = 0, and branch coverage is left to -fprofile-arcs. Under optimization, COND_EXPRs may be folded, replaced with switches, min-max, etc., which leaves ghost identifiers in basic blocks that do not end with a conditional jump. They are not really meaningful for condition coverage anymore, but since coverage is unreliable under optimization anyway this is not a big problem. The cond_uids map in FN cannot be expected to exist. It will only be created if it is needed, and a function may have gconds even though there are none in source. This can be seen in PR gcov-profile/114601, when -finstrument-functions-once is used and the function has no conditions. */ unsigned condition_uid (struct function *fn, basic_block b) { gimple *stmt = gsi_stmt (gsi_last_bb (b)); if (!safe_is_a (stmt) || !fn->cond_uids) return 0; unsigned *v = fn->cond_uids->get (as_a (stmt)); return v ? *v : 0; } /* Compute the masking table. Masking and short circuiting are deeply connected - masking occurs when control flow reaches a state that is also reachable with short circuiting. In fact, masking corresponds to short circuiting for the reversed expression. This means we can find the limits, the last term in preceeding subexpressions, by following the edges that short circuit to the same outcome. The algorithm treats the CFG as a reduced order binary decision diagram (see Randall E. Bryant's Graph Based Algorithms for Boolean Function Manipulation (1987)). In the simplest case a || b: a |\ | b |/ \ T F T has multiple incoming edges and is the outcome of a short circuit, with top = a, bot = b. The top node (a) is masked when the edge (b, T) is taken. The names "top" and "bot" refer to a pair of nodes with a shared successor. The top is always the node corresponding to the left-most operand of the two, and it holds that top < bot in a topological ordering. Now consider (a && b) || (c && d) and its masking table: a |\ b \ |\| | c | |\ | d \ |/ \| T F a[0] = {} a[1] = {} b[0] = {a} b[1] = {} c[0] = {} c[1] = {} d[0] = {c} d[1] = {a,b} Note that 0 and 1 are indices and not boolean values - a[0] is the index in the masking vector when a takes the true edge. b[0] and d[0] are identical to the a || b example, and d[1] is the bot in the triangle [d, b] -> T. b is the top node in the [d, b] relationship and last term in (a && b). To find the other terms masked we use the fact that all paths in an expression go through either of the outcomes, found by collecting all non-complex edges that go out of the expression (the neighborhood). In some cases the outgoing edge go through intermediate (or bypass) nodes, and we collect these paths too (see contract_edge_up). We find the terms by marking the outcomes (in this case c, T) and walk the predecessors starting at top (in this case b) and masking nodes when both successors are marked. The masking table is represented as two bitfields per term in the expression with the index corresponding to the term in the Boolean expression. a || b && c becomes the term vector [a b c] and the masking table [a[0] a[1] b[0] ...]. The kth bit of a masking vector is set if the kth term is masked by taking the edge. The out masks are in uint64_t (the practical maximum for gcov_type_node for any target) as it has to be big enough to store the target size gcov types independent of the host. */ void masking_vectors (conds_ctx& ctx, array_slice blocks, array_slice maps, array_slice masks) { gcc_assert (blocks.is_valid ()); gcc_assert (!blocks.empty ()); gcc_assert (maps.is_valid ()); gcc_assert (masks.is_valid ()); gcc_assert (sizeof (masks[0]) * BITS_PER_UNIT >= CONDITIONS_MAX_TERMS); if (bitmap_count_bits (maps[0]) == 1) return; sbitmap marks = ctx.G1; const sbitmap core = maps[0]; const sbitmap allg = maps[1]; vec& queue = ctx.B1; vec& body = ctx.B2; const vec& top_index = ctx.top_index; /* Set up for the iteration - include the outcome nodes in the traversal. The algorithm compares pairs of nodes and is not really sensitive to traversal order, but need to maintain topological order because the index of masking nodes maps to the index in the accumulators. We must also check the incoming-to-outcome pairs. These edges may in turn be split (this happens with labels on top of then/else blocks) so we must follow any single-in single-out path. The non-condition blocks do not have to be in order as they are non-condition blocks and will not be considered for the set-bit index. */ body.truncate (0); body.reserve (blocks.size () + 2); for (const basic_block b : blocks) if (bitmap_bit_p (core, b->index)) body.quick_push (b); for (basic_block b : blocks) { if (!bitmap_bit_p (core, b->index)) continue; for (edge e : b->succs) { if (e->flags & EDGE_COMPLEX) continue; if (bitmap_bit_p (allg, e->dest->index)) continue; body.safe_push (e->dest); /* There may be multiple nodes between the condition edge and the actual outcome, and we need to know when these paths join to determine if there is short circuit/masking. This is effectively creating a virtual edge from the condition node to the real outcome. */ while (!(e->flags & EDGE_DFS_BACK) && single_p (e->dest->succs)) { e = single_edge (e->dest->succs); body.safe_push (e->dest); } } } /* Find the masking. The leftmost element cannot mask anything, so start at 1. */ for (size_t i = 1; i != body.length (); i++) { const basic_block b = body[i]; for (edge e1 : b->preds) for (edge e2 : b->preds) { if (e1 == e2) continue; if ((e1->flags | e2->flags) & EDGE_COMPLEX) continue; edge etop = contract_edge_up (e1); edge ebot = contract_edge_up (e2); gcc_assert (etop != ebot); const basic_block top = etop->src; const basic_block bot = ebot->src; const unsigned cond = etop->flags & ebot->flags & EDGE_CONDITION; if (!cond) continue; if (top_index[top->index] > top_index[bot->index]) continue; if (!bitmap_bit_p (core, top->index)) continue; if (!bitmap_bit_p (core, bot->index)) continue; outcomes out = conditional_succs (top); gcc_assert (out); bitmap_clear (marks); bitmap_set_bit (marks, out.t->index); bitmap_set_bit (marks, out.f->index); queue.truncate (0); queue.safe_push (top); // The edge bot -> outcome triggers the masking const int m = 2*index_of (bot, body) + condition_index (cond); gcc_assert (m >= 0); while (!queue.is_empty ()) { basic_block q = queue.pop (); /* q may have been processed & completed by being added to the queue multiple times, so check that there is still work to do before continuing. */ if (bitmap_bit_p (marks, q->index)) continue; outcomes succs = conditional_succs (q); if (!bitmap_bit_p (marks, succs.t->index)) continue; if (!bitmap_bit_p (marks, succs.f->index)) continue; const int index = index_of (q, body); gcc_assert (index != -1); masks[m] |= uint64_t (1) << index; bitmap_set_bit (marks, q->index); for (edge e : q->preds) { e = contract_edge_up (e); if (e->flags & EDGE_DFS_BACK) continue; if (bitmap_bit_p (marks, e->src->index)) continue; if (!bitmap_bit_p (core, e->src->index)) continue; queue.safe_push (e->src); } } } } } /* Emit LHS = RHS on edges. This is just a short hand that automates the building of the assign and immediately puts it on the edge, which becomes noisy. */ tree emit_assign (edge e, tree lhs, tree rhs) { gassign *w = gimple_build_assign (lhs, rhs); gsi_insert_on_edge (e, w); return lhs; } /* Emit lhs = RHS on edges. The lhs is created. */ tree emit_assign (edge e, tree rhs) { return emit_assign (e, make_ssa_name (gcov_type_node), rhs); } /* Emit LHS = OP1 OP2 on edges. */ tree emit_bitwise_op (edge e, tree op1, tree_code op, tree op2 = NULL_TREE) { tree lhs = make_ssa_name (gcov_type_node); gassign *w = gimple_build_assign (lhs, op, op1, op2); gsi_insert_on_edge (e, w); return lhs; } /* Visitor for make_top_index. */ void make_top_index_visit (basic_block b, vec& L, vec& marks) { if (marks[b->index]) return; /* Follow the false edge first, if it exists, so that true paths are given the lower index in the ordering. Any iteration order would yield a valid and useful topological ordering, but making sure the true branch has the lower index first makes reporting work better for expressions with ternaries. Walk the false branch first because the array will be reversed to finalize the topological order. With the wrong ordering (a ? b : c) && d could become [a c b d], but the (expected) order is really [a b c d]. */ const unsigned false_fwd = EDGE_DFS_BACK | EDGE_FALSE_VALUE; for (edge e : b->succs) if ((e->flags & false_fwd) == EDGE_FALSE_VALUE) make_top_index_visit (e->dest, L, marks); for (edge e : b->succs) if (!(e->flags & false_fwd)) make_top_index_visit (e->dest, L, marks); marks[b->index] = 1; L.quick_push (b); } /* Find a topological sorting of the blocks in a function so that left operands are before right operands including subexpressions. Sorting on block index does not guarantee this property and the syntactical order of terms is very important to the condition coverage. The sorting algorithm is from Cormen et al (2001) but with back-edges ignored and thus there is no need for temporary marks (for cycle detection). The L argument is a buffer/working memory, and the output will be written to TOP_INDEX. For the expression (a || (b && c) || d) the blocks should be [a b c d]. */ void make_top_index (array_slice blocks, vec& L, vec& top_index) { L.truncate (0); L.reserve (blocks.size ()); /* Use of the output map as a temporary for tracking visited status. */ top_index.truncate (0); top_index.safe_grow_cleared (blocks.size ()); for (const basic_block b : blocks) make_top_index_visit (b, L, top_index); /* Insert canaries - if there are unreachable nodes (for example infinite loops) then the unreachable nodes should never be needed for comparison, and L.length () < max_index. An index mapping should also never be recorded twice. */ for (unsigned i = 0; i != top_index.length (); i++) top_index[i] = -1; gcc_assert (blocks.size () == L.length ()); L.reverse (); const unsigned nblocks = L.length (); for (unsigned i = 0; i != nblocks; i++) { gcc_assert (L[i]->index != -1); top_index[L[i]->index] = int (i); } } /* Find all nodes including non-conditions in a Boolean expression. We need to know the paths through the expression so that the masking and instrumentation phases can limit searches and know what subgraphs must be threaded through, but not counted, such as the (b || c) in a && fn (b || c) && d. It is essentially the intersection of downwards paths from the expression nodes EXPR to the post-dominator and upwards from the post-dominator. Finding the dominator is slightly more involved than picking the first/last, particularly under optimization, because both incoming and outgoing paths may have multiple entries/exits. It is assumed GRAPH is an array_slice of the basic blocks of this function sorted by the basic block index. */ vec& paths_between (conds_ctx &ctx, array_slice graph, const vec& expr) { if (expr.length () == 1) { ctx.blocks.truncate (0); ctx.blocks.safe_push (expr[0]); return ctx.blocks; } basic_block dom; sbitmap up = ctx.G1; sbitmap down = ctx.G2; sbitmap paths = ctx.G3; vec& queue = ctx.B1; queue.truncate (0); bitmap_clear (down); dom = get_immediate_dominator (CDI_POST_DOMINATORS, expr[0]); for (basic_block b : expr) if (dom != b) dom = nearest_common_dominator (CDI_POST_DOMINATORS, dom, b); queue.safe_splice (expr); while (!queue.is_empty ()) { basic_block b = queue.pop (); if (!bitmap_set_bit (down, b->index)) continue; if (b == dom) continue; for (edge e : b->succs) if (!(e->flags & (EDGE_COMPLEX | EDGE_DFS_BACK))) queue.safe_push (e->dest); } queue.truncate (0); bitmap_clear (up); dom = expr[0]; for (basic_block b : expr) if (dom != b) dom = nearest_common_dominator (CDI_DOMINATORS, dom, b); queue.safe_splice (expr); while (!queue.is_empty ()) { basic_block b = queue.pop (); if (!bitmap_set_bit (up, b->index)) continue; if (b == dom) continue; for (edge e : b->preds) if (!(e->flags & (EDGE_COMPLEX | EDGE_DFS_BACK))) queue.safe_push (e->src); } bitmap_and (paths, up, down); vec& blocks = ctx.blocks; blocks.truncate (0); blocks.reserve (graph.size ()); sbitmap_iterator itr; unsigned index; EXECUTE_IF_SET_IN_BITMAP (paths, 0, index, itr) blocks.quick_push (graph[index]); return blocks; } } /* Context object for the condition coverage. This stores conds_ctx (the buffers reused when analyzing the cfg) and the output arrays. This is designed to be heap allocated and aggressively preallocates large buffers to avoid having to reallocate for most programs. */ struct condcov { explicit condcov (unsigned nblocks) noexcept (true) : ctx (nblocks), m_maps (sbitmap_vector_alloc (2 * nblocks, nblocks)) { bitmap_vector_clear (m_maps, 2 * nblocks); } auto_vec m_index; auto_vec m_blocks; auto_vec m_masks; conds_ctx ctx; sbitmap *m_maps; }; /* Get the length, that is the number of Boolean expression found. cov_length is the one-past index for cov_{blocks,masks,maps}. */ size_t cov_length (const struct condcov* cov) { if (cov->m_index.is_empty ()) return 0; return cov->m_index.length () - 1; } /* The subgraph, exluding intermediates, for the nth Boolean expression. */ array_slice cov_blocks (struct condcov* cov, size_t n) { if (n >= cov->m_index.length ()) return array_slice::invalid (); basic_block *begin = cov->m_blocks.begin () + cov->m_index[n]; basic_block *end = cov->m_blocks.begin () + cov->m_index[n + 1]; return array_slice (begin, end - begin); } /* The masks for the nth Boolean expression. */ array_slice cov_masks (struct condcov* cov, size_t n) { if (n >= cov->m_index.length ()) return array_slice::invalid (); uint64_t *begin = cov->m_masks.begin () + 2*cov->m_index[n]; uint64_t *end = cov->m_masks.begin () + 2*cov->m_index[n + 1]; return array_slice (begin, end - begin); } /* The maps for the nth Boolean expression. */ array_slice cov_maps (struct condcov* cov, size_t n) { if (n >= cov->m_index.length ()) return array_slice::invalid (); sbitmap *begin = cov->m_maps + 2*n; sbitmap *end = begin + 2; return array_slice (begin, end - begin); } /* Deleter for condcov. */ void cov_free (struct condcov* cov) { sbitmap_vector_free (cov->m_maps); delete cov; } /* Condition coverage (MC/DC) Whalen, Heimdahl, De Silva in "Efficient Test Coverage Measurement for MC/DC" describe an algorithm for modified condition/decision coverage based on AST analysis. This algorithm does analyzes the control flow graph (interpreted as a binary decision diagram) to determine the masking vectors. The individual phases are described in more detail closer to the implementation. The coverage only considers the positions, not the symbols, in a conditional, e.g. !A || (!B && A) is a 3-term conditional even though A appears twice. Subexpressions have no effect on term ordering: (a && (b || (c && d)) || e) comes out as [a b c d e]. Functions whose arguments are Boolean expressions are treated as separate expressions, that is, a && fn (b || c) && d is treated as [a _fn d] and [b c], not [a b c d]. The output for gcov is a vector of pairs of unsigned integers, interpreted as bit-sets, where the bit index corresponds to the index of the condition in the expression. The returned condcov should be released by the caller with cov_free. */ struct condcov* find_conditions (struct function *fn) { mark_dfs_back_edges (fn); const bool have_dom = dom_info_available_p (fn, CDI_DOMINATORS); const bool have_post_dom = dom_info_available_p (fn, CDI_POST_DOMINATORS); if (!have_dom) calculate_dominance_info (CDI_DOMINATORS); if (!have_post_dom) calculate_dominance_info (CDI_POST_DOMINATORS); const unsigned nblocks = n_basic_blocks_for_fn (fn); basic_block *fnblocksp = basic_block_info_for_fn (fn)->address (); condcov *cov = new condcov (nblocks); conds_ctx& ctx = cov->ctx; array_slice fnblocks (fnblocksp, nblocks); make_top_index (fnblocks, ctx.B1, ctx.top_index); /* Bin the Boolean expressions so that exprs[id] -> [x1, x2, ...]. */ hash_map, auto_vec> exprs; for (basic_block b : fnblocks) { const unsigned uid = condition_uid (fn, b); if (uid == 0) continue; exprs.get_or_insert (uid).safe_push (b); } /* Visit all reachable nodes and collect conditions. Topological order is important so the first node of a boolean expression is visited first (it will mark subsequent terms). */ cov->m_index.safe_push (0); for (auto expr : exprs) { vec& conds = expr.second; if (conds.length () > CONDITIONS_MAX_TERMS) { location_t loc = gimple_location (gsi_stmt (gsi_last_bb (conds[0]))); warning_at (loc, OPT_Wcoverage_too_many_conditions, "Too many conditions (found %u); giving up coverage", conds.length ()); continue; } conds.sort (topological_cmp, &ctx.top_index); vec& subgraph = paths_between (ctx, fnblocks, conds); subgraph.sort (topological_cmp, &ctx.top_index); const unsigned index = cov->m_index.length () - 1; sbitmap condm = cov->m_maps[0 + 2*index]; sbitmap subgm = cov->m_maps[1 + 2*index]; for (basic_block b : conds) bitmap_set_bit (condm, b->index); for (basic_block b : subgraph) bitmap_set_bit (subgm, b->index); cov->m_blocks.safe_splice (subgraph); cov->m_index.safe_push (cov->m_blocks.length ()); } if (!have_dom) free_dominance_info (fn, CDI_DOMINATORS); if (!have_post_dom) free_dominance_info (fn, CDI_POST_DOMINATORS); cov->m_masks.safe_grow_cleared (2 * cov->m_index.last ()); const size_t length = cov_length (cov); for (size_t i = 0; i != length; i++) masking_vectors (ctx, cov_blocks (cov, i), cov_maps (cov, i), cov_masks (cov, i)); return cov; } namespace { /* Stores the incoming edge and previous counters (in SSA form) on that edge for the node e->deston that edge for the node e->dest. The counters record the seen-true (0), seen-false (1), and current-mask (2). They are stored in an array rather than proper members for access-by-index as the code paths tend to be identical for the different counters. */ struct counters { edge e; tree counter[3]; tree& operator [] (size_t i) { return counter[i]; } }; /* Find the counters for the incoming edge e, or NULL if the edge has not been recorded (could be for complex incoming edges). */ counters* find_counters (vec& candidates, edge e) { for (counters& candidate : candidates) if (candidate.e == e) return &candidate; return NULL; } /* Resolve the SSA for a specific counter KIND. If it is not modified by any incoming edges, simply forward it, otherwise create a phi node of all the candidate counters and return it. */ tree resolve_counter (vec& cands, size_t kind) { gcc_assert (!cands.is_empty ()); gcc_assert (kind < 3); counters& fst = cands[0]; if (!fst.e || fst.e->dest->preds->length () == 1) { gcc_assert (cands.length () == 1); return fst[kind]; } tree zero0 = build_int_cst (gcov_type_node, 0); tree ssa = make_ssa_name (gcov_type_node); gphi *phi = create_phi_node (ssa, fst.e->dest); for (edge e : fst.e->dest->preds) { counters *prev = find_counters (cands, e); if (prev) add_phi_arg (phi, (*prev)[kind], e, UNKNOWN_LOCATION); else { tree zero = make_ssa_name (gcov_type_node); gimple_stmt_iterator gsi = gsi_after_labels (e->src); gassign *set = gimple_build_assign (zero, zero0); gsi_insert_before (&gsi, set, GSI_NEW_STMT); add_phi_arg (phi, zero, e, UNKNOWN_LOCATION); } } return ssa; } /* Resolve all the counters for a node. Note that the edge is undefined, as the counters are intended to form the base to push to the successors, and because the is only meaningful for nodes with a single predecessor. */ counters resolve_counters (vec& cands) { counters next; next[0] = resolve_counter (cands, 0); next[1] = resolve_counter (cands, 1); next[2] = resolve_counter (cands, 2); return next; } } /* Add instrumentation to a decision subgraph. EXPR should be the (topologically sorted) block of nodes returned by cov_blocks, MAPS the bitmaps returned by cov_maps, and MASKS the block of bitsets returned by cov_masks. CONDNO should be the index of this condition in the function, i.e. the same argument given to cov_{masks,graphs}. EXPR may contain nodes in-between the conditions, e.g. when an operand contains a function call, or there is a setjmp and the cfg is filled with complex edges. Every node is annotated with three counters; the true, false, and mask value. First, walk the graph and determine what if there are multiple possible values for either accumulator depending on the path taken, in which case a phi node is created and registered as the accumulator. Then, those values are pushed as accumulators to the immediate successors. For some very particular programs there may be multiple paths into the expression (e.g. when prior terms are determined by a surrounding conditional) in which case the default zero-counter is pushed, otherwise all predecessors will have been considered before the successor because of topologically ordered traversal. Finally, expr is traversed again to look for edges to the outcomes, that is, edges with a destination outside of expr, and the local accumulators are flushed to the global gcov counters on these edges. In some cases there are edge splits that cause 3+ edges to the two outcome nodes. If a complex edge is taken (e.g. on a longjmp) the accumulators are attempted poisoned so that there would be no change to the global counters, but this has proven unreliable in the presence of undefined behavior, see the setjmp003 test. It is important that the flushes happen on the basic condition outgoing edge, otherwise flushes could be lost to exception handling or other abnormal control flow. */ size_t instrument_decisions (array_slice expr, size_t condno, array_slice maps, array_slice masks) { tree zero = build_int_cst (gcov_type_node, 0); tree poison = build_int_cst (gcov_type_node, ~0ULL); const sbitmap core = maps[0]; const sbitmap allg = maps[1]; hash_map> table; counters zerocounter; zerocounter.e = NULL; zerocounter[0] = zero; zerocounter[1] = zero; zerocounter[2] = zero; unsigned xi = 0; bool increment = false; tree rhs = build_int_cst (gcov_type_node, 1ULL << xi); for (basic_block current : expr) { vec& candidates = table.get_or_insert (current); if (candidates.is_empty ()) candidates.safe_push (zerocounter); counters prev = resolve_counters (candidates); if (increment) { xi += 1; gcc_checking_assert (xi < sizeof (uint64_t) * BITS_PER_UNIT); rhs = build_int_cst (gcov_type_node, 1ULL << xi); increment = false; } for (edge e : current->succs) { counters next = prev; next.e = e; if (bitmap_bit_p (core, e->src->index) && (e->flags & EDGE_CONDITION)) { const int k = condition_index (e->flags); next[k] = emit_bitwise_op (e, prev[k], BIT_IOR_EXPR, rhs); if (masks[2*xi + k]) { tree m = build_int_cst (gcov_type_node, masks[2*xi + k]); next[2] = emit_bitwise_op (e, prev[2], BIT_IOR_EXPR, m); } increment = true; } else if (e->flags & EDGE_COMPLEX) { /* A complex edge has been taken - wipe the accumulators and poison the mask so that this path does not contribute to coverage. */ next[0] = poison; next[1] = poison; next[2] = poison; } table.get_or_insert (e->dest).safe_push (next); } } /* Since this is also the return value, the number of conditions, make sure to include the increment of the last basic block. */ if (increment) xi += 1; gcc_assert (xi == bitmap_count_bits (core)); const tree relaxed = build_int_cst (integer_type_node, MEMMODEL_RELAXED); const bool atomic = flag_profile_update == PROFILE_UPDATE_ATOMIC; const tree atomic_ior = builtin_decl_explicit (TYPE_PRECISION (gcov_type_node) > 32 ? BUILT_IN_ATOMIC_FETCH_OR_8 : BUILT_IN_ATOMIC_FETCH_OR_4); /* Flush to the gcov accumulators. */ for (const basic_block b : expr) { if (!bitmap_bit_p (core, b->index)) continue; for (edge e : b->succs) { /* Flush the accumulators on leaving the Boolean function. The destination may be inside the function only when it returns to the loop header, such as do { ... } while (x); */ if (bitmap_bit_p (allg, e->dest->index)) { if (!(e->flags & EDGE_DFS_BACK)) continue; if (e->dest != expr[0]) continue; } vec *cands = table.get (e->dest); gcc_assert (cands); counters *prevp = find_counters (*cands, e); gcc_assert (prevp); counters prev = *prevp; /* _true &= ~mask, _false &= ~mask */ counters next; next[2] = emit_bitwise_op (e, prev[2], BIT_NOT_EXPR); next[0] = emit_bitwise_op (e, prev[0], BIT_AND_EXPR, next[2]); next[1] = emit_bitwise_op (e, prev[1], BIT_AND_EXPR, next[2]); /* _global_true |= _true, _global_false |= _false */ for (size_t k = 0; k != 2; ++k) { tree ref = tree_coverage_counter_ref (GCOV_COUNTER_CONDS, 2*condno + k); if (atomic) { ref = unshare_expr (ref); gcall *flush = gimple_build_call (atomic_ior, 3, build_addr (ref), next[k], relaxed); gsi_insert_on_edge (e, flush); } else { tree get = emit_assign (e, ref); tree put = emit_bitwise_op (e, next[k], BIT_IOR_EXPR, get); emit_assign (e, unshare_expr (ref), put); } } } } return xi; } #undef CONDITIONS_MAX_TERMS #undef EDGE_CONDITION /* Do initialization work for the edge profiler. */ /* Add code: __thread gcov* __gcov_indirect_call.counters; // pointer to actual counter __thread void* __gcov_indirect_call.callee; // actual callee address __thread int __gcov_function_counter; // time profiler function counter */ static void init_ic_make_global_vars (void) { tree gcov_type_ptr; gcov_type_ptr = build_pointer_type (get_gcov_type ()); tree tuple_type = lang_hooks.types.make_type (RECORD_TYPE); /* callee */ ic_tuple_callee_field = build_decl (BUILTINS_LOCATION, FIELD_DECL, NULL_TREE, ptr_type_node); /* counters */ ic_tuple_counters_field = build_decl (BUILTINS_LOCATION, FIELD_DECL, NULL_TREE, gcov_type_ptr); DECL_CHAIN (ic_tuple_counters_field) = ic_tuple_callee_field; finish_builtin_struct (tuple_type, "indirect_call_tuple", ic_tuple_counters_field, NULL_TREE); ic_tuple_var = build_decl (UNKNOWN_LOCATION, VAR_DECL, get_identifier ("__gcov_indirect_call"), tuple_type); TREE_PUBLIC (ic_tuple_var) = 1; DECL_ARTIFICIAL (ic_tuple_var) = 1; DECL_INITIAL (ic_tuple_var) = NULL; DECL_EXTERNAL (ic_tuple_var) = 1; if (targetm.have_tls) set_decl_tls_model (ic_tuple_var, decl_default_tls_model (ic_tuple_var)); } /* Create the type and function decls for the interface with gcov. */ void gimple_init_gcov_profiler (void) { tree interval_profiler_fn_type; tree pow2_profiler_fn_type; tree topn_values_profiler_fn_type; tree gcov_type_ptr; tree ic_profiler_fn_type; tree average_profiler_fn_type; const char *fn_name; if (!gcov_type_node) { const char *fn_suffix = flag_profile_update == PROFILE_UPDATE_ATOMIC ? "_atomic" : ""; gcov_type_node = get_gcov_type (); gcov_type_ptr = build_pointer_type (gcov_type_node); /* void (*) (gcov_type *, gcov_type, int, unsigned) */ interval_profiler_fn_type = build_function_type_list (void_type_node, gcov_type_ptr, gcov_type_node, integer_type_node, unsigned_type_node, NULL_TREE); fn_name = concat ("__gcov_interval_profiler", fn_suffix, NULL); tree_interval_profiler_fn = build_fn_decl (fn_name, interval_profiler_fn_type); free (CONST_CAST (char *, fn_name)); TREE_NOTHROW (tree_interval_profiler_fn) = 1; DECL_ATTRIBUTES (tree_interval_profiler_fn) = tree_cons (get_identifier ("leaf"), NULL, DECL_ATTRIBUTES (tree_interval_profiler_fn)); /* void (*) (gcov_type *, gcov_type) */ pow2_profiler_fn_type = build_function_type_list (void_type_node, gcov_type_ptr, gcov_type_node, NULL_TREE); fn_name = concat ("__gcov_pow2_profiler", fn_suffix, NULL); tree_pow2_profiler_fn = build_fn_decl (fn_name, pow2_profiler_fn_type); free (CONST_CAST (char *, fn_name)); TREE_NOTHROW (tree_pow2_profiler_fn) = 1; DECL_ATTRIBUTES (tree_pow2_profiler_fn) = tree_cons (get_identifier ("leaf"), NULL, DECL_ATTRIBUTES (tree_pow2_profiler_fn)); /* void (*) (gcov_type *, gcov_type) */ topn_values_profiler_fn_type = build_function_type_list (void_type_node, gcov_type_ptr, gcov_type_node, NULL_TREE); fn_name = concat ("__gcov_topn_values_profiler", fn_suffix, NULL); tree_topn_values_profiler_fn = build_fn_decl (fn_name, topn_values_profiler_fn_type); free (CONST_CAST (char *, fn_name)); TREE_NOTHROW (tree_topn_values_profiler_fn) = 1; DECL_ATTRIBUTES (tree_topn_values_profiler_fn) = tree_cons (get_identifier ("leaf"), NULL, DECL_ATTRIBUTES (tree_topn_values_profiler_fn)); init_ic_make_global_vars (); /* void (*) (gcov_type, void *) */ ic_profiler_fn_type = build_function_type_list (void_type_node, gcov_type_node, ptr_type_node, NULL_TREE); fn_name = concat ("__gcov_indirect_call_profiler_v4", fn_suffix, NULL); tree_indirect_call_profiler_fn = build_fn_decl (fn_name, ic_profiler_fn_type); free (CONST_CAST (char *, fn_name)); TREE_NOTHROW (tree_indirect_call_profiler_fn) = 1; DECL_ATTRIBUTES (tree_indirect_call_profiler_fn) = tree_cons (get_identifier ("leaf"), NULL, DECL_ATTRIBUTES (tree_indirect_call_profiler_fn)); tree_time_profiler_counter = build_decl (UNKNOWN_LOCATION, VAR_DECL, get_identifier ("__gcov_time_profiler_counter"), get_gcov_type ()); TREE_PUBLIC (tree_time_profiler_counter) = 1; DECL_EXTERNAL (tree_time_profiler_counter) = 1; TREE_STATIC (tree_time_profiler_counter) = 1; DECL_ARTIFICIAL (tree_time_profiler_counter) = 1; DECL_INITIAL (tree_time_profiler_counter) = NULL; /* void (*) (gcov_type *, gcov_type) */ average_profiler_fn_type = build_function_type_list (void_type_node, gcov_type_ptr, gcov_type_node, NULL_TREE); fn_name = concat ("__gcov_average_profiler", fn_suffix, NULL); tree_average_profiler_fn = build_fn_decl (fn_name, average_profiler_fn_type); free (CONST_CAST (char *, fn_name)); TREE_NOTHROW (tree_average_profiler_fn) = 1; DECL_ATTRIBUTES (tree_average_profiler_fn) = tree_cons (get_identifier ("leaf"), NULL, DECL_ATTRIBUTES (tree_average_profiler_fn)); fn_name = concat ("__gcov_ior_profiler", fn_suffix, NULL); tree_ior_profiler_fn = build_fn_decl (fn_name, average_profiler_fn_type); free (CONST_CAST (char *, fn_name)); TREE_NOTHROW (tree_ior_profiler_fn) = 1; DECL_ATTRIBUTES (tree_ior_profiler_fn) = tree_cons (get_identifier ("leaf"), NULL, DECL_ATTRIBUTES (tree_ior_profiler_fn)); /* LTO streamer needs assembler names. Because we create these decls late, we need to initialize them by hand. */ DECL_ASSEMBLER_NAME (tree_interval_profiler_fn); DECL_ASSEMBLER_NAME (tree_pow2_profiler_fn); DECL_ASSEMBLER_NAME (tree_topn_values_profiler_fn); DECL_ASSEMBLER_NAME (tree_indirect_call_profiler_fn); DECL_ASSEMBLER_NAME (tree_average_profiler_fn); DECL_ASSEMBLER_NAME (tree_ior_profiler_fn); } } /* If RESULT is not null, then output instructions as GIMPLE trees to assign the updated counter from CALL of FUNC to RESULT. Insert the CALL and the optional assignment instructions to GSI. Use NAME for temporary values. */ static inline void gen_assign_counter_update (gimple_stmt_iterator *gsi, gcall *call, tree func, tree result, const char *name) { if (result) { tree result_type = TREE_TYPE (TREE_TYPE (func)); tree tmp1 = make_temp_ssa_name (result_type, NULL, name); gimple_set_lhs (call, tmp1); gsi_insert_after (gsi, call, GSI_NEW_STMT); tree tmp2 = make_temp_ssa_name (TREE_TYPE (result), NULL, name); gassign *assign = gimple_build_assign (tmp2, NOP_EXPR, tmp1); gsi_insert_after (gsi, assign, GSI_NEW_STMT); assign = gimple_build_assign (result, tmp2); gsi_insert_after (gsi, assign, GSI_NEW_STMT); } else gsi_insert_after (gsi, call, GSI_NEW_STMT); } /* Output instructions as GIMPLE trees to increment the COUNTER. If RESULT is not null, then assign the updated counter value to RESULT. Insert the instructions to GSI. Use NAME for temporary values. */ static inline void gen_counter_update (gimple_stmt_iterator *gsi, tree counter, tree result, const char *name) { tree type = gcov_type_node; tree addr = build_fold_addr_expr (counter); tree one = build_int_cst (type, 1); tree relaxed = build_int_cst (integer_type_node, MEMMODEL_RELAXED); if (counter_update == COUNTER_UPDATE_ATOMIC_BUILTIN || (result && counter_update == COUNTER_UPDATE_ATOMIC_SPLIT)) { /* __atomic_fetch_add (&counter, 1, MEMMODEL_RELAXED); */ tree f = builtin_decl_explicit (TYPE_PRECISION (type) > 32 ? BUILT_IN_ATOMIC_ADD_FETCH_8 : BUILT_IN_ATOMIC_ADD_FETCH_4); gcall *call = gimple_build_call (f, 3, addr, one, relaxed); gen_assign_counter_update (gsi, call, f, result, name); } else if (!result && (counter_update == COUNTER_UPDATE_ATOMIC_SPLIT || counter_update == COUNTER_UPDATE_ATOMIC_PARTIAL)) { /* low = __atomic_add_fetch_4 (addr, 1, MEMMODEL_RELAXED); high_inc = low == 0 ? 1 : 0; __atomic_add_fetch_4 (addr_high, high_inc, MEMMODEL_RELAXED); */ tree zero32 = build_zero_cst (uint32_type_node); tree one32 = build_one_cst (uint32_type_node); tree addr_high = make_temp_ssa_name (TREE_TYPE (addr), NULL, name); tree four = build_int_cst (size_type_node, 4); gassign *assign1 = gimple_build_assign (addr_high, POINTER_PLUS_EXPR, addr, four); gsi_insert_after (gsi, assign1, GSI_NEW_STMT); if (WORDS_BIG_ENDIAN) std::swap (addr, addr_high); tree f = builtin_decl_explicit (BUILT_IN_ATOMIC_ADD_FETCH_4); gcall *call1 = gimple_build_call (f, 3, addr, one, relaxed); tree low = make_temp_ssa_name (uint32_type_node, NULL, name); gimple_call_set_lhs (call1, low); gsi_insert_after (gsi, call1, GSI_NEW_STMT); tree is_zero = make_temp_ssa_name (boolean_type_node, NULL, name); gassign *assign2 = gimple_build_assign (is_zero, EQ_EXPR, low, zero32); gsi_insert_after (gsi, assign2, GSI_NEW_STMT); tree high_inc = make_temp_ssa_name (uint32_type_node, NULL, name); gassign *assign3 = gimple_build_assign (high_inc, COND_EXPR, is_zero, one32, zero32); gsi_insert_after (gsi, assign3, GSI_NEW_STMT); gcall *call2 = gimple_build_call (f, 3, addr_high, high_inc, relaxed); gsi_insert_after (gsi, call2, GSI_NEW_STMT); } else { tree tmp1 = make_temp_ssa_name (type, NULL, name); gassign *assign1 = gimple_build_assign (tmp1, counter); gsi_insert_after (gsi, assign1, GSI_NEW_STMT); tree tmp2 = make_temp_ssa_name (type, NULL, name); gassign *assign2 = gimple_build_assign (tmp2, PLUS_EXPR, tmp1, one); gsi_insert_after (gsi, assign2, GSI_NEW_STMT); gassign *assign3 = gimple_build_assign (unshare_expr (counter), tmp2); gsi_insert_after (gsi, assign3, GSI_NEW_STMT); if (result) { gassign *assign4 = gimple_build_assign (result, tmp2); gsi_insert_after (gsi, assign4, GSI_NEW_STMT); } } } /* Output instructions as GIMPLE trees to increment the edge execution count, and insert them on E. */ void gimple_gen_edge_profiler (int edgeno, edge e) { gimple_stmt_iterator gsi = gsi_last (PENDING_STMT (e)); tree counter = tree_coverage_counter_ref (GCOV_COUNTER_ARCS, edgeno); gen_counter_update (&gsi, counter, NULL_TREE, "PROF_edge_counter"); } /* Emits code to get VALUE to instrument at GSI, and returns the variable containing the value. */ static tree prepare_instrumented_value (gimple_stmt_iterator *gsi, histogram_value value) { tree val = value->hvalue.value; if (POINTER_TYPE_P (TREE_TYPE (val))) val = fold_convert (build_nonstandard_integer_type (TYPE_PRECISION (TREE_TYPE (val)), 1), val); return force_gimple_operand_gsi (gsi, fold_convert (gcov_type_node, val), true, NULL_TREE, true, GSI_SAME_STMT); } /* Output instructions as GIMPLE trees to increment the interval histogram counter. VALUE is the expression whose value is profiled. TAG is the tag of the section for counters, BASE is offset of the counter position. */ void gimple_gen_interval_profiler (histogram_value value, unsigned tag) { gimple *stmt = value->hvalue.stmt; gimple_stmt_iterator gsi = gsi_for_stmt (stmt); tree ref = tree_coverage_counter_ref (tag, 0), ref_ptr; gcall *call; tree val; tree start = build_int_cst_type (integer_type_node, value->hdata.intvl.int_start); tree steps = build_int_cst_type (unsigned_type_node, value->hdata.intvl.steps); ref_ptr = force_gimple_operand_gsi (&gsi, build_addr (ref), true, NULL_TREE, true, GSI_SAME_STMT); val = prepare_instrumented_value (&gsi, value); call = gimple_build_call (tree_interval_profiler_fn, 4, ref_ptr, val, start, steps); gsi_insert_before (&gsi, call, GSI_NEW_STMT); } /* Output instructions as GIMPLE trees to increment the power of two histogram counter. VALUE is the expression whose value is profiled. TAG is the tag of the section for counters. */ void gimple_gen_pow2_profiler (histogram_value value, unsigned tag) { gimple *stmt = value->hvalue.stmt; gimple_stmt_iterator gsi = gsi_for_stmt (stmt); tree ref_ptr = tree_coverage_counter_addr (tag, 0); gcall *call; tree val; ref_ptr = force_gimple_operand_gsi (&gsi, ref_ptr, true, NULL_TREE, true, GSI_SAME_STMT); val = prepare_instrumented_value (&gsi, value); call = gimple_build_call (tree_pow2_profiler_fn, 2, ref_ptr, val); gsi_insert_before (&gsi, call, GSI_NEW_STMT); } /* Output instructions as GIMPLE trees for code to find the most N common values. VALUE is the expression whose value is profiled. TAG is the tag of the section for counters. */ void gimple_gen_topn_values_profiler (histogram_value value, unsigned tag) { gimple *stmt = value->hvalue.stmt; gimple_stmt_iterator gsi = gsi_for_stmt (stmt); tree ref_ptr = tree_coverage_counter_addr (tag, 0); gcall *call; tree val; ref_ptr = force_gimple_operand_gsi (&gsi, ref_ptr, true, NULL_TREE, true, GSI_SAME_STMT); val = prepare_instrumented_value (&gsi, value); call = gimple_build_call (tree_topn_values_profiler_fn, 2, ref_ptr, val); gsi_insert_before (&gsi, call, GSI_NEW_STMT); } /* Output instructions as GIMPLE trees for code to find the most common called function in indirect call. VALUE is the call expression whose indirect callee is profiled. TAG is the tag of the section for counters. */ void gimple_gen_ic_profiler (histogram_value value, unsigned tag) { tree tmp1; gassign *stmt1, *stmt2, *stmt3; gimple *stmt = value->hvalue.stmt; gimple_stmt_iterator gsi = gsi_for_stmt (stmt); tree ref_ptr = tree_coverage_counter_addr (tag, 0); ref_ptr = force_gimple_operand_gsi (&gsi, ref_ptr, true, NULL_TREE, true, GSI_SAME_STMT); /* Insert code: stmt1: __gcov_indirect_call.counters = get_relevant_counter_ptr (); stmt2: tmp1 = (void *) (indirect call argument value) stmt3: __gcov_indirect_call.callee = tmp1; Example: f_1 = foo; __gcov_indirect_call.counters = &__gcov4.main[0]; PROF_fn_9 = f_1; __gcov_indirect_call.callee = PROF_fn_9; _4 = f_1 (); */ tree gcov_type_ptr = build_pointer_type (get_gcov_type ()); tree counter_ref = build3 (COMPONENT_REF, gcov_type_ptr, ic_tuple_var, ic_tuple_counters_field, NULL_TREE); stmt1 = gimple_build_assign (counter_ref, ref_ptr); tmp1 = make_temp_ssa_name (ptr_type_node, NULL, "PROF_fn"); stmt2 = gimple_build_assign (tmp1, unshare_expr (value->hvalue.value)); tree callee_ref = build3 (COMPONENT_REF, ptr_type_node, ic_tuple_var, ic_tuple_callee_field, NULL_TREE); stmt3 = gimple_build_assign (callee_ref, tmp1); gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT); gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT); gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT); } /* Output instructions as GIMPLE trees for code to find the most common called function in indirect call. Insert instructions at the beginning of every possible called function. */ void gimple_gen_ic_func_profiler (void) { struct cgraph_node * c_node = cgraph_node::get (current_function_decl); gcall *stmt1; tree tree_uid, cur_func, void0; /* Disable indirect call profiling for an IFUNC resolver and its callees since it requires TLS which hasn't been set up yet when the dynamic linker is resolving IFUNC symbols. See https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114115 */ if (c_node->only_called_directly_p () || c_node->called_by_ifunc_resolver) return; gimple_init_gcov_profiler (); basic_block entry = ENTRY_BLOCK_PTR_FOR_FN (cfun); basic_block cond_bb = split_edge (single_succ_edge (entry)); basic_block update_bb = split_edge (single_succ_edge (cond_bb)); /* We need to do an extra split in order to not create an input for a possible PHI node. */ split_edge (single_succ_edge (update_bb)); edge true_edge = single_succ_edge (cond_bb); true_edge->flags = EDGE_TRUE_VALUE; profile_probability probability; if (DECL_VIRTUAL_P (current_function_decl)) probability = profile_probability::very_likely (); else probability = profile_probability::unlikely (); true_edge->probability = probability; edge e = make_edge (cond_bb, single_succ_edge (update_bb)->dest, EDGE_FALSE_VALUE); e->probability = true_edge->probability.invert (); /* Insert code: if (__gcov_indirect_call.callee != NULL) __gcov_indirect_call_profiler_v3 (profile_id, ¤t_function_decl); The function __gcov_indirect_call_profiler_v3 is responsible for resetting __gcov_indirect_call.callee to NULL. */ gimple_stmt_iterator gsi = gsi_start_bb (cond_bb); void0 = build_int_cst (ptr_type_node, 0); tree callee_ref = build3 (COMPONENT_REF, ptr_type_node, ic_tuple_var, ic_tuple_callee_field, NULL_TREE); tree ref = force_gimple_operand_gsi (&gsi, callee_ref, true, NULL_TREE, true, GSI_SAME_STMT); gcond *cond = gimple_build_cond (NE_EXPR, ref, void0, NULL, NULL); gsi_insert_before (&gsi, cond, GSI_NEW_STMT); gsi = gsi_after_labels (update_bb); cur_func = force_gimple_operand_gsi (&gsi, build_addr (current_function_decl), true, NULL_TREE, true, GSI_SAME_STMT); tree_uid = build_int_cst (gcov_type_node, cgraph_node::get (current_function_decl)->profile_id); stmt1 = gimple_build_call (tree_indirect_call_profiler_fn, 2, tree_uid, cur_func); gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT); } /* Output instructions as GIMPLE tree at the beginning for each function. TAG is the tag of the section for counters, BASE is offset of the counter position and GSI is the iterator we place the counter. */ void gimple_gen_time_profiler (unsigned tag) { tree type = get_gcov_type (); basic_block entry = ENTRY_BLOCK_PTR_FOR_FN (cfun); basic_block cond_bb = split_edge (single_succ_edge (entry)); basic_block update_bb = split_edge (single_succ_edge (cond_bb)); /* We need to do an extra split in order to not create an input for a possible PHI node. */ split_edge (single_succ_edge (update_bb)); edge true_edge = single_succ_edge (cond_bb); true_edge->flags = EDGE_TRUE_VALUE; true_edge->probability = profile_probability::unlikely (); edge e = make_edge (cond_bb, single_succ_edge (update_bb)->dest, EDGE_FALSE_VALUE); e->probability = true_edge->probability.invert (); gimple_stmt_iterator gsi = gsi_start_bb (cond_bb); tree original_ref = tree_coverage_counter_ref (tag, 0); tree ref = force_gimple_operand_gsi (&gsi, original_ref, true, NULL_TREE, true, GSI_SAME_STMT); /* Emit: if (counters[0] != 0). */ gcond *cond = gimple_build_cond (EQ_EXPR, ref, build_int_cst (type, 0), NULL, NULL); gsi_insert_before (&gsi, cond, GSI_NEW_STMT); /* Emit: counters[0] = ++__gcov_time_profiler_counter. */ gsi = gsi_start_bb (update_bb); gen_counter_update (&gsi, tree_time_profiler_counter, original_ref, "PROF_time_profile"); } /* Output instructions as GIMPLE trees to increment the average histogram counter. VALUE is the expression whose value is profiled. TAG is the tag of the section for counters, BASE is offset of the counter position. */ void gimple_gen_average_profiler (histogram_value value, unsigned tag) { gimple *stmt = value->hvalue.stmt; gimple_stmt_iterator gsi = gsi_for_stmt (stmt); tree ref_ptr = tree_coverage_counter_addr (tag, 0); gcall *call; tree val; ref_ptr = force_gimple_operand_gsi (&gsi, ref_ptr, true, NULL_TREE, true, GSI_SAME_STMT); val = prepare_instrumented_value (&gsi, value); call = gimple_build_call (tree_average_profiler_fn, 2, ref_ptr, val); gsi_insert_before (&gsi, call, GSI_NEW_STMT); } /* Output instructions as GIMPLE trees to increment the ior histogram counter. VALUE is the expression whose value is profiled. TAG is the tag of the section for counters, BASE is offset of the counter position. */ void gimple_gen_ior_profiler (histogram_value value, unsigned tag) { gimple *stmt = value->hvalue.stmt; gimple_stmt_iterator gsi = gsi_for_stmt (stmt); tree ref_ptr = tree_coverage_counter_addr (tag, 0); gcall *call; tree val; ref_ptr = force_gimple_operand_gsi (&gsi, ref_ptr, true, NULL_TREE, true, GSI_SAME_STMT); val = prepare_instrumented_value (&gsi, value); call = gimple_build_call (tree_ior_profiler_fn, 2, ref_ptr, val); gsi_insert_before (&gsi, call, GSI_NEW_STMT); } static vec profile_filter_files; static vec profile_exclude_files; /* Parse list of provided REGEX (separated with semi-collon) and create expressions (of type regex_t) and save them into V vector. If there is a regular expression parsing error, error message is printed for FLAG_NAME. */ static void parse_profile_filter (const char *regex, vec *v, const char *flag_name) { v->create (4); if (regex != NULL) { char *str = xstrdup (regex); for (char *p = strtok (str, ";"); p != NULL; p = strtok (NULL, ";")) { regex_t r; if (regcomp (&r, p, REG_EXTENDED | REG_NOSUB) != 0) { error ("invalid regular expression %qs in %qs", p, flag_name); return; } v->safe_push (r); } } } /* Parse values of -fprofile-filter-files and -fprofile-exclude-files options. */ static void parse_profile_file_filtering () { parse_profile_filter (flag_profile_filter_files, &profile_filter_files, "-fprofile-filter-files"); parse_profile_filter (flag_profile_exclude_files, &profile_exclude_files, "-fprofile-exclude-files"); } /* Parse vectors of regular expressions. */ static void release_profile_file_filtering () { profile_filter_files.release (); profile_exclude_files.release (); } /* Return true when FILENAME should be instrumented based on -fprofile-filter-files and -fprofile-exclude-files options. */ static bool include_source_file_for_profile (const char *filename) { /* First check whether file is included in flag_profile_exclude_files. */ for (unsigned i = 0; i < profile_exclude_files.length (); i++) if (regexec (&profile_exclude_files[i], filename, 0, NULL, 0) == REG_NOERROR) return false; /* For non-empty flag_profile_filter_files include only files matching a regex in the flag. */ if (profile_filter_files.is_empty ()) return true; for (unsigned i = 0; i < profile_filter_files.length (); i++) if (regexec (&profile_filter_files[i], filename, 0, NULL, 0) == REG_NOERROR) return true; return false; } #ifndef HAVE_sync_compare_and_swapsi #define HAVE_sync_compare_and_swapsi 0 #endif #ifndef HAVE_atomic_compare_and_swapsi #define HAVE_atomic_compare_and_swapsi 0 #endif #ifndef HAVE_sync_compare_and_swapdi #define HAVE_sync_compare_and_swapdi 0 #endif #ifndef HAVE_atomic_compare_and_swapdi #define HAVE_atomic_compare_and_swapdi 0 #endif /* Profile all functions in the callgraph. */ static unsigned int tree_profiling (void) { struct cgraph_node *node; /* Verify whether we can utilize atomic update operations. */ bool can_support_atomic = targetm.have_libatomic; unsigned HOST_WIDE_INT gcov_type_size = tree_to_uhwi (TYPE_SIZE_UNIT (get_gcov_type ())); bool have_atomic_4 = HAVE_sync_compare_and_swapsi || HAVE_atomic_compare_and_swapsi; bool have_atomic_8 = HAVE_sync_compare_and_swapdi || HAVE_atomic_compare_and_swapdi; bool needs_split = gcov_type_size == 8 && !have_atomic_8 && have_atomic_4; if (!can_support_atomic) { if (gcov_type_size == 4) can_support_atomic = have_atomic_4; else if (gcov_type_size == 8) can_support_atomic = have_atomic_8; } if (flag_profile_update != PROFILE_UPDATE_SINGLE && needs_split) counter_update = COUNTER_UPDATE_ATOMIC_PARTIAL; if (flag_profile_update == PROFILE_UPDATE_ATOMIC && !can_support_atomic) { warning (0, "target does not support atomic profile update, " "single mode is selected"); flag_profile_update = PROFILE_UPDATE_SINGLE; } else if (flag_profile_update == PROFILE_UPDATE_PREFER_ATOMIC) flag_profile_update = can_support_atomic ? PROFILE_UPDATE_ATOMIC : PROFILE_UPDATE_SINGLE; if (flag_profile_update == PROFILE_UPDATE_ATOMIC) { if (needs_split) counter_update = COUNTER_UPDATE_ATOMIC_SPLIT; else counter_update = COUNTER_UPDATE_ATOMIC_BUILTIN; } /* This is a small-ipa pass that gets called only once, from cgraphunit.cc:ipa_passes(). */ gcc_assert (symtab->state == IPA_SSA); init_node_map (true); parse_profile_file_filtering (); FOR_EACH_DEFINED_FUNCTION (node) { bool thunk = false; if (!gimple_has_body_p (node->decl) && !node->thunk) continue; /* Don't profile functions produced for builtin stuff. */ if (DECL_SOURCE_LOCATION (node->decl) == BUILTINS_LOCATION) continue; if (lookup_attribute ("no_profile_instrument_function", DECL_ATTRIBUTES (node->decl))) continue; /* Do not instrument extern inline functions when testing coverage. While this is not perfectly consistent (early inlined extern inlines will get acocunted), testsuite expects that. */ if (DECL_EXTERNAL (node->decl) && flag_test_coverage) continue; const char *file = LOCATION_FILE (DECL_SOURCE_LOCATION (node->decl)); if (!include_source_file_for_profile (file)) continue; if (node->thunk) { /* We cannot expand variadic thunks to Gimple. */ if (stdarg_p (TREE_TYPE (node->decl))) continue; thunk = true; /* When generate profile, expand thunk to gimple so it can be instrumented same way as other functions. */ if (profile_arc_flag || condition_coverage_flag) expand_thunk (node, false, true); /* Read cgraph profile but keep function as thunk at profile-use time. */ else { read_thunk_profile (node); continue; } } push_cfun (DECL_STRUCT_FUNCTION (node->decl)); if (dump_file) dump_function_header (dump_file, cfun->decl, dump_flags); /* Local pure-const may imply need to fixup the cfg. */ if (gimple_has_body_p (node->decl) && (execute_fixup_cfg () & TODO_cleanup_cfg)) cleanup_tree_cfg (); branch_prob (thunk); if (! flag_branch_probabilities && flag_profile_values) gimple_gen_ic_func_profiler (); if (flag_branch_probabilities && !thunk && flag_profile_values && flag_value_profile_transformations && profile_status_for_fn (cfun) == PROFILE_READ) gimple_value_profile_transformations (); /* The above could hose dominator info. Currently there is none coming in, this is a safety valve. It should be easy to adjust it, if and when there is some. */ free_dominance_info (CDI_DOMINATORS); free_dominance_info (CDI_POST_DOMINATORS); pop_cfun (); } release_profile_file_filtering (); /* Drop pure/const flags from instrumented functions. */ if (profile_arc_flag || condition_coverage_flag || flag_test_coverage) FOR_EACH_DEFINED_FUNCTION (node) { if (!gimple_has_body_p (node->decl) || !(!node->clone_of || node->decl != node->clone_of->decl)) continue; /* Don't profile functions produced for builtin stuff. */ if (DECL_SOURCE_LOCATION (node->decl) == BUILTINS_LOCATION) continue; node->set_const_flag (false, false); node->set_pure_flag (false, false); } /* Update call statements and rebuild the cgraph. */ FOR_EACH_DEFINED_FUNCTION (node) { basic_block bb; if (!gimple_has_body_p (node->decl) || !(!node->clone_of || node->decl != node->clone_of->decl)) continue; /* Don't profile functions produced for builtin stuff. */ if (DECL_SOURCE_LOCATION (node->decl) == BUILTINS_LOCATION) continue; push_cfun (DECL_STRUCT_FUNCTION (node->decl)); if (profile_arc_flag || condition_coverage_flag || flag_test_coverage) FOR_EACH_BB_FN (bb, cfun) { gimple_stmt_iterator gsi; for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { gcall *call = dyn_cast (gsi_stmt (gsi)); if (!call || gimple_call_internal_p (call)) continue; /* We do not clear pure/const on decls without body. */ tree fndecl = gimple_call_fndecl (call); cgraph_node *callee; if (fndecl && (callee = cgraph_node::get (fndecl)) && callee->get_availability (node) == AVAIL_NOT_AVAILABLE) continue; /* Drop the const attribute from the call type (the pure attribute is not available on types). */ tree fntype = gimple_call_fntype (call); if (fntype && TYPE_READONLY (fntype)) { int quals = TYPE_QUALS (fntype) & ~TYPE_QUAL_CONST; fntype = build_qualified_type (fntype, quals); gimple_call_set_fntype (call, fntype); } /* Update virtual operands of calls to no longer const/pure functions. */ update_stmt (call); } } /* re-merge split blocks. */ cleanup_tree_cfg (); update_ssa (TODO_update_ssa); cgraph_edge::rebuild_edges (); pop_cfun (); } handle_missing_profiles (); del_node_map (); return 0; } namespace { const pass_data pass_data_ipa_tree_profile = { SIMPLE_IPA_PASS, /* type */ "profile", /* name */ OPTGROUP_NONE, /* optinfo_flags */ TV_IPA_PROFILE, /* tv_id */ 0, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ TODO_dump_symtab, /* todo_flags_finish */ }; class pass_ipa_tree_profile : public simple_ipa_opt_pass { public: pass_ipa_tree_profile (gcc::context *ctxt) : simple_ipa_opt_pass (pass_data_ipa_tree_profile, ctxt) {} /* opt_pass methods: */ bool gate (function *) final override; unsigned int execute (function *) final override { return tree_profiling (); } }; // class pass_ipa_tree_profile bool pass_ipa_tree_profile::gate (function *) { /* When profile instrumentation, use or test coverage shall be performed. But for AutoFDO, this there is no instrumentation, thus this pass is disabled. */ return (!in_lto_p && !flag_auto_profile && (flag_branch_probabilities || flag_test_coverage || profile_arc_flag || condition_coverage_flag) && !seen_error ()); } } // anon namespace simple_ipa_opt_pass * make_pass_ipa_tree_profile (gcc::context *ctxt) { return new pass_ipa_tree_profile (ctxt); } #include "gt-tree-profile.h"