| /* Calculate prime path coverage. | |
| Copyright (C) 2024-2026 Free Software Foundation, Inc. | |
| 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 | |
| <http://www.gnu.org/licenses/>. */ | |
| #include "config.h" | |
| #include "system.h" | |
| #include "coretypes.h" | |
| #include "diagnostic-core.h" | |
| #include "memmodel.h" | |
| #include "target.h" | |
| #include "function.h" | |
| #include "basic-block.h" | |
| #include "tree.h" | |
| #include "tree-cfg.h" | |
| #include "tree-nested.h" | |
| #include "cfg.h" | |
| #include "gimple.h" | |
| #include "gimple-iterator.h" | |
| #include "gimplify.h" | |
| #include "coverage.h" | |
| #include "ssa.h" | |
| #include "vec.h" | |
| #include "sbitmap.h" | |
| #include "graphds.h" | |
| #include "hash-map.h" | |
| #include "bitmap.h" | |
| #include "cfganal.h" | |
| bool mark_dfs_back_edges (struct function *); | |
| vec<vec<int>> prime_paths (struct graph*, size_t); | |
| namespace | |
| { | |
| /* Check if all the successors of BB are abnormal, e.g. setjmp. */ | |
| bool | |
| all_abnormal_succs_p (basic_block bb) | |
| { | |
| for (edge e : bb->succs) | |
| if (!(e->flags & EDGE_ABNORMAL)) | |
| return false; | |
| return true; | |
| } | |
| /* Build a struct graph equivalent to the CFG for the function FN. The caller | |
| must free the returned graph with free_graph. The data field of every | |
| vertex and edge point to the basic blocks and edges in the CFG. | |
| The CFG recording and gcov is not aware of abnormal edges, so they are | |
| ignored here, too. This means some paths are lost, e.g. those that involve | |
| setjmp/longjmp. They are still paths but would need more support from | |
| profile.cc and gcov.cc to work. */ | |
| struct graph* | |
| cfg_as_graph (struct function* fn) | |
| { | |
| struct graph *g = new_graph (n_basic_blocks_for_fn (fn)); | |
| basic_block entry = ENTRY_BLOCK_PTR_FOR_FN (fn); | |
| basic_block exit = EXIT_BLOCK_PTR_FOR_FN (fn); | |
| g->vertices[entry->index].data = entry; | |
| g->vertices[exit->index].data = exit; | |
| const unsigned ignore = EDGE_FAKE | EDGE_ABNORMAL | EDGE_ABNORMAL_CALL; | |
| basic_block bb; | |
| FOR_EACH_BB_FN (bb, fn) | |
| { | |
| g->vertices[bb->index].data = bb; | |
| for (edge e : bb->succs) | |
| if (!(e->flags & ignore) && e->dest != exit) | |
| add_edge (g, e->src->index, e->dest->index)->data = e; | |
| } | |
| return g; | |
| } | |
| /* Check if BB's predecessor is the ENTRY_BLOCK, i.e. BB is the first real | |
| block in the function. */ | |
| bool | |
| pred_entry_p (const_basic_block bb) | |
| { | |
| return single_pred_p (bb) && single_pred (bb)->index == ENTRY_BLOCK; | |
| } | |
| /* Find the prime paths for the function FN with the ENTRY and EXIT blocks | |
| removed. This can lead to empty paths when there is a fake edge to the exit | |
| block, for example for abort functions or infinite loops. Empty paths are | |
| removed because the length of the returned vec is important. */ | |
| vec<vec<int>> | |
| find_prime_paths (struct function *fn) | |
| { | |
| struct graph *cfg = cfg_as_graph (fn); | |
| vec<vec<int>> paths = prime_paths (cfg, path_coverage_limit); | |
| bool any_empty = false; | |
| for (vec<int> &path : paths) | |
| { | |
| /* setjmp calls will be isolated basic blocks when ABNORMAL_EDGEs are | |
| removed. If a path is made up of just such a vertex it is pointless | |
| and can be removed. If a function is only __builtin_exit() (see | |
| gcov-22.C) the CFG will only have one block and look like such an | |
| island, and we want to preserve it. */ | |
| if (path.length () == 1 | |
| && !pred_entry_p (BASIC_BLOCK_FOR_FN (fn, path[0])) | |
| && all_abnormal_succs_p (BASIC_BLOCK_FOR_FN (fn, path[0]))) | |
| path.pop (); | |
| if (!path.is_empty () && path[0] == ENTRY_BLOCK) | |
| path.ordered_remove (0); | |
| if (!path.is_empty () && path.last () == EXIT_BLOCK) | |
| path.pop (); | |
| if (path.is_empty ()) | |
| { | |
| any_empty = true; | |
| path.release (); | |
| } | |
| } | |
| unsigned ix1, ix2; | |
| vec<int> *ptr; | |
| if (any_empty) | |
| VEC_ORDERED_REMOVE_IF (paths, ix1, ix2, ptr, ptr->is_empty ()); | |
| free_graph (cfg); | |
| return paths; | |
| } | |
| /* Return the edge between SRC and DST. */ | |
| edge | |
| edge_between (struct function *fn, int src, int dst) | |
| { | |
| basic_block bbsrc = BASIC_BLOCK_FOR_FN (fn, src); | |
| basic_block bbdst = BASIC_BLOCK_FOR_FN (fn, dst); | |
| for (edge e : bbsrc->succs) | |
| if (e->dest == bbdst) | |
| return e; | |
| gcc_unreachable (); | |
| } | |
| /* Get the basic blocks of FN in topological order so that all predecessors | |
| come before the vertex, while ignoring back edges. */ | |
| vec<basic_block> | |
| topsort (struct function *fn) | |
| { | |
| vec<basic_block> blocks {}; | |
| auto_vec<int> order {}; | |
| blocks.reserve (n_basic_blocks_for_fn (fn)); | |
| order.safe_grow (n_basic_blocks_for_fn (fn)); | |
| const int n = post_order_compute (order.address (), false, false); | |
| for (int i = 0; i < n; ++i) | |
| blocks.quick_push (BASIC_BLOCK_FOR_FN (fn, order[i])); | |
| blocks.reverse (); | |
| return blocks; | |
| } | |
| /* Hasher for maps where the key is a pair of edge/basic_block and bucket id | |
| (size_t). */ | |
| template <typename T> | |
| using bucket_hash = pair_hash <nofree_ptr_hash <T>, | |
| int_hash <size_t, size_t(-1)>>; | |
| /* Hasher for {edge, bucket-id} keys. */ | |
| using edge_hash = bucket_hash <edge_def>; | |
| /* Hasher for {basic_block, bucket-id} keys. */ | |
| using block_hash = bucket_hash <basic_block_def>; | |
| /* Find the union of the bitsets sets on the incoming edges of BB at BUCKET. | |
| If no paths go through BB the returned bitset would be empty. Bitsets are | |
| looked up in ANDS, and if the nth bit is set then the nth path contains that | |
| edge. */ | |
| uint64_t | |
| union_incoming_bit_and (hash_map <edge_hash, uint64_t> &ands, | |
| const basic_block bb, size_t bucket) | |
| { | |
| uint64_t inc = 0; | |
| for (edge e : bb->preds) | |
| { | |
| const uint64_t *val = ands.get ({e, bucket}); | |
| inc |= (val ? *val : 0); | |
| } | |
| return inc; | |
| } | |
| /* Check if the incoming edges have the power to modify the paths in flight for | |
| BUCKET. If all the incoming edges would apply the same bitmask the | |
| BB+BUCKET will not actually update the path set, and we don't need to emit | |
| an AND_EXPR and have a later fork distinguish the paths. */ | |
| bool | |
| can_change_path_p (hash_map <edge_hash, uint64_t> &ands, | |
| const basic_block bb, size_t bucket, uint64_t all_and) | |
| { | |
| for (edge e : bb->preds) | |
| { | |
| const uint64_t *e_and = ands.get ({e, bucket}); | |
| if (!e_and || *e_and != all_and) | |
| return true; | |
| } | |
| return false; | |
| } | |
| /* Check if all bits in BITSET are 1 for the target size TARGET_SIZE. For a | |
| 32-bit target only the bits in the lower half should be set, and this should | |
| return true when all bits in the lower half are set, even if the bitset type | |
| have room for more bits. */ | |
| bool | |
| all_bits_set_p (uint64_t bitset, size_t target_size) | |
| { | |
| return (size_t)popcount_hwi (bitset) == target_size; | |
| } | |
| /* Create a constant or SSA name of GCOV_TYPE_NODE type and zero-assign to it | |
| safely on the edge E. If the edge is abnormal it is assumed the phi is | |
| abnormal and we need an SSA name, otherwise fall back to a constant. The | |
| returned value is safe to use with add_phi_arg (). | |
| If the edge is abnormal we cannot insert on it directly, and instead | |
| carefully add the assignment on the source block. If that source block ends | |
| with control flow (like those produced by _setjmp) we must insert before to | |
| not break that invariant, otherwise insert after so that things like the | |
| setjmp receiver is the first element of the basic block. Doing the assign | |
| is necessary as phis cannot resolve to constants. */ | |
| tree | |
| safe_insert_zero_phi_arg (edge e, tree gcov_type_node) | |
| { | |
| tree cst = build_zero_cst (gcov_type_node); | |
| if (!(e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))) | |
| return cst; | |
| tree zero = make_ssa_name (gcov_type_node); | |
| gassign *put = gimple_build_assign (zero, cst); | |
| gimple_stmt_iterator gsi = gsi_start_nondebug_after_labels_bb (e->src); | |
| if (gimple_call_internal_p (*gsi, IFN_ABNORMAL_DISPATCHER) | |
| || stmt_ends_bb_p (*gsi)) | |
| gsi_insert_before (&gsi, put, GSI_NEW_STMT); | |
| else | |
| gsi_insert_after (&gsi, put, GSI_NEW_STMT); | |
| return zero; | |
| } | |
| /* Check if SSA is a constant value (created by build_int_cst) and can be | |
| folded. */ | |
| bool | |
| constant_p (tree ssa) | |
| { | |
| return tree_fits_uhwi_p (ssa); | |
| } | |
| /* A fixup task. When resolving the exit SSA for a back edge arg to a phi | |
| node, the exit SSA has not been created yet. Record what needs to be done | |
| when it is created, and tie the phi to the right SSA name once it is | |
| guaranteed it is created. If MASK is nullptr the predecessor's SSA should | |
| be used as-is, and does not need an AND. This should only be created with | |
| the helpers fixup_noop and fixup_and. */ | |
| struct fixup | |
| { | |
| gphi *phi; | |
| edge e; | |
| tree lhs; | |
| tree mask; | |
| size_t bucket; | |
| }; | |
| /* Create a fixup with a no-op for the PHI in BUCKET. Use this when the edge E | |
| does not need an AND applied and should rather propagate the predecessor's | |
| SSA name. */ | |
| fixup | |
| fixup_noop (gphi *phi, edge e, size_t bucket) | |
| { | |
| fixup todo; | |
| todo.phi = phi; | |
| todo.e = e; | |
| todo.bucket = bucket; | |
| todo.lhs = nullptr; | |
| todo.mask = nullptr; | |
| return todo; | |
| } | |
| /* Create a fixup for PHI through BUCKET with the exit SSA name E->src ANDed | |
| with MASK (E->src & MASK). GCOV_TYPE_NODE should be a tree of the gcov type | |
| node for creating SSA names. */ | |
| fixup | |
| fixup_and (gphi *phi, edge e, size_t bucket, uint64_t mask, | |
| tree gcov_type_node) | |
| { | |
| fixup todo; | |
| todo.phi = phi; | |
| todo.e = e; | |
| todo.bucket = bucket; | |
| todo.lhs = make_ssa_name (gcov_type_node); | |
| todo.mask = build_int_cst (gcov_type_node, mask); | |
| return todo; | |
| } | |
| /* Insert LOCAL |= MASK on BB safely, even when BB is a returns_twice block. | |
| This is a helper to safely emit code for updating the path bitmask in the | |
| presence of abnormal edges and returns_twice blocks, since they have special | |
| restrictions on edge splits and first/last instructions on the block. */ | |
| tree | |
| safe_insert_ior (basic_block bb, tree local, tree mask, gphi *phi, | |
| tree gcov_type_node) | |
| { | |
| gimple_stmt_iterator gsi = gsi_start_nondebug_after_labels_bb (bb); | |
| gimple *stmt = gsi_stmt (gsi); | |
| /* This is a returns_twice block (e.g. setjmp) which does not really expect | |
| anything before or after, so we cannot insert the IOR on the block itself. | |
| We move the IORs to the predecessors instead and update the phi. The | |
| abnormal edge cannot be split, so in that case we carefully put the IOR | |
| after the ABNORMAL_DISPATCHER. */ | |
| if (stmt && is_gimple_call (stmt) | |
| && (gimple_call_flags (stmt) & ECF_RETURNS_TWICE)) | |
| { | |
| for (edge e : bb->preds) | |
| { | |
| gcc_checking_assert (phi); | |
| tree next = make_ssa_name (gcov_type_node); | |
| tree prev = gimple_phi_arg_def_from_edge (phi, e); | |
| gassign *put = prev | |
| ? gimple_build_assign (next, BIT_IOR_EXPR, prev, mask) | |
| : gimple_build_assign (next, mask); | |
| gimple_stmt_iterator gsi = gsi_last_bb (e->src); | |
| add_phi_arg (phi, next, e, UNKNOWN_LOCATION); | |
| if (e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) | |
| gsi_insert_before (&gsi, put, GSI_SAME_STMT); | |
| else | |
| gsi_insert_on_edge (e, put); | |
| } | |
| } | |
| else | |
| { | |
| tree next = make_ssa_name (gcov_type_node); | |
| gassign *put = gimple_build_assign (next, BIT_IOR_EXPR, local, mask); | |
| gsi_insert_before (&gsi, put, GSI_SAME_STMT); | |
| local = next; | |
| } | |
| return local; | |
| } | |
| /* Insert instructions updating the global counter at BUCKET with the contents | |
| of (LOCAL & MASK). LOCAL is the SSA counter for this bucket, MASK the bits | |
| that should be updated (that is, the paths that end in this basic block). | |
| If ATOMIC_IOR is non-null the it uses atomics. GCOV_TYPE_NODE should be a | |
| tree of the gcov type node for creating SSA names. | |
| global[BUCKET] |= (LOCAL & MASK) | |
| If MASK is null, no mask is applied and it becomes: | |
| global[BUCKET] |= LOCAL | |
| This function should only be necessary for the successor of an | |
| ABNORMAL_DISPATCHER e.g. the destination of a longjmp. Paths starting at a | |
| longjmp do not have anything to flush, so those edges are simply ignored. | |
| Since this is a returns_twice block we cannot put anything before (or really | |
| after), so we instrument on the edge itself, rather than messing with | |
| splitting and changing the graph now. | |
| This is similar to gsi_safe_insert_before, but this function does not | |
| immediately commit edge inserts and does not split blocks. */ | |
| void | |
| flush_on_edges (basic_block bb, size_t bucket, tree local, tree mask, | |
| tree atomic_ior, tree gcov_type_node) | |
| { | |
| gimple *def = !constant_p (local) ? SSA_NAME_DEF_STMT (local) : NULL; | |
| gphi *phi = safe_dyn_cast <gphi *> (def); | |
| tree relaxed = nullptr; | |
| if (atomic_ior) | |
| relaxed = build_int_cst (integer_type_node, MEMMODEL_RELAXED); | |
| for (edge e : bb->preds) | |
| { | |
| if (e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) | |
| continue; | |
| tree global = tree_coverage_counter_ref (GCOV_COUNTER_PATHS, bucket); | |
| if (phi) | |
| local = gimple_phi_arg_def_from_edge (phi, e); | |
| tree global_copy = make_ssa_name (gcov_type_node); | |
| gassign *ga1 = gimple_build_assign (global_copy, global); | |
| gsi_insert_on_edge (e, ga1); | |
| tree masked; | |
| if (mask) | |
| { | |
| masked = make_ssa_name (gcov_type_node); | |
| gassign *ga2 = gimple_build_assign (masked, BIT_AND_EXPR, local, | |
| mask); | |
| gsi_insert_on_edge (e, ga2); | |
| } | |
| else | |
| masked = local; | |
| if (atomic_ior) | |
| { | |
| global = unshare_expr (global); | |
| gcall *call = gimple_build_call (atomic_ior, 3, build_addr (global), | |
| masked, relaxed); | |
| gsi_insert_on_edge (e, call); | |
| } | |
| else | |
| { | |
| tree tmp = make_ssa_name (gcov_type_node); | |
| gassign *ga3 = gimple_build_assign (tmp, BIT_IOR_EXPR, global_copy, | |
| masked); | |
| gassign *ga4 = gimple_build_assign (unshare_expr (global), tmp); | |
| gsi_insert_on_edge (e, ga3); | |
| gsi_insert_on_edge (e, ga4); | |
| } | |
| } | |
| } | |
| /* Insert instructions update the global counter at BUCKET with the contents of | |
| (LOCAL & MASK). LOCAL is the SSA counter for this bucket, MASK the bits | |
| that should be updated (that is, the paths that end in this basic block). | |
| If ATOMIC_IOR is non-null the it uses atomics. GCOV_TYPE_NODE should be a | |
| tree of the gcov type node for creating SSA names. | |
| global[BUCKET] |= (LOCAL & MASK) | |
| If MASK is null, no mask is applied and it becomes: | |
| global[BUCKET] |= LOCAL | |
| This function should be used on every block except returns_twice blocks (see | |
| flush_on_edge) as all incoming edges can use the same flushing code. */ | |
| void | |
| flush_on_gsi (gimple_stmt_iterator *gsi, size_t bucket, tree local, tree mask, | |
| tree atomic_ior, tree gcov_type_node) | |
| { | |
| tree relaxed = nullptr; | |
| if (atomic_ior) | |
| relaxed = build_int_cst (integer_type_node, MEMMODEL_RELAXED); | |
| tree global = tree_coverage_counter_ref (GCOV_COUNTER_PATHS, bucket); | |
| tree global_copy = make_ssa_name (gcov_type_node); | |
| gassign *ga1 = gimple_build_assign (global_copy, global); | |
| gsi_insert_before (gsi, ga1, GSI_SAME_STMT); | |
| tree masked; | |
| if (mask) | |
| { | |
| masked = make_ssa_name (gcov_type_node); | |
| gassign *ga2 = gimple_build_assign (masked, BIT_AND_EXPR, local, mask); | |
| gsi_insert_before (gsi, ga2, GSI_SAME_STMT); | |
| } | |
| else | |
| masked = local; | |
| if (atomic_ior) | |
| { | |
| global = unshare_expr (global); | |
| gcall *call = gimple_build_call (atomic_ior, 3, build_addr (global), | |
| masked, relaxed); | |
| gsi_insert_before (gsi, call, GSI_SAME_STMT); | |
| } | |
| else | |
| { | |
| tree tmp = make_ssa_name (gcov_type_node); | |
| gassign *ga3 = gimple_build_assign (tmp, BIT_IOR_EXPR, global_copy, | |
| masked); | |
| gassign *ga4 = gimple_build_assign (unshare_expr (global), tmp); | |
| gsi_insert_before (gsi, ga3, GSI_SAME_STMT); | |
| gsi_insert_before (gsi, ga4, GSI_SAME_STMT); | |
| } | |
| } | |
| } // namespace | |
| /* Instrument FN for prime path coverage, enabled by -fpath-coverage. The | |
| number of paths grows very fast with the complexity (control flow) which | |
| explodes compile times and object file size. Giving up is controlled by the | |
| -fpath-coverage-limit flag. The paths are sorted lexicographically by basic | |
| block id, and each path is identified by its index in the sorted set of | |
| paths, which in turn corresponds to a bit in a large bitset associated with | |
| FN. The monitoring code is a few bitwise operations added to edges and | |
| basic blocks to maintain a set of live paths (note that many paths may | |
| overlap and that many paths may be covered by the same input). When | |
| reaching the final vertex of a path the global counters are updated. | |
| This is made more complicated by the gcov type having very limited size. To | |
| support functions with more than 32/64 paths the bitmap is implemented on | |
| top of a sequence of gcov integers, "buckets", where path N is recorded as | |
| bit N%64 in bucket N/64. For large functions, an individual basic block | |
| will only be part of a small subset of paths, and by extension buckets and | |
| local counters. Only the necessary counters are read and written. */ | |
| unsigned | |
| instrument_prime_paths (struct function *fn) | |
| { | |
| mark_dfs_back_edges (fn); | |
| vec<vec<int>> paths = find_prime_paths (fn); | |
| if (paths.is_empty ()) | |
| { | |
| warning_at (fn->function_start_locus, OPT_Wcoverage_too_many_paths, | |
| "paths exceeding limit, giving up path coverage"); | |
| release_vec_vec (paths); | |
| return 0; | |
| } | |
| tree gcov_type_node = get_gcov_type (); | |
| const size_t bucketsize = TYPE_PRECISION (gcov_type_node); | |
| const size_t nbuckets = (paths.length () + (bucketsize - 1)) / bucketsize; | |
| gcc_checking_assert (sizeof (uint64_t) * BITS_PER_UNIT >= bucketsize); | |
| if (!coverage_counter_alloc (GCOV_COUNTER_PATHS, nbuckets)) | |
| { | |
| release_vec_vec (paths); | |
| return 0; | |
| } | |
| hash_map <edge_hash, uint64_t> ands; | |
| hash_map <block_hash, uint64_t> iors; | |
| hash_map <block_hash, uint64_t> flushes; | |
| /* Now that we have all paths we must figure out what bitmasks must be | |
| applied on the edges. We also record in which basic block the path starts | |
| (e.g. accumulator resets) and ends (accumulator flushes). */ | |
| for (size_t pathno = 0; pathno != paths.length (); ++pathno) | |
| { | |
| const vec<int> &path = paths[pathno]; | |
| const size_t bucket = pathno / bucketsize; | |
| const uint64_t bit = uint64_t (1) << (pathno % bucketsize); | |
| basic_block first = BASIC_BLOCK_FOR_FN (fn, path[0]); | |
| basic_block last = BASIC_BLOCK_FOR_FN (fn, path[path.length () - 1]); | |
| for (unsigned i = 1; i != path.length (); ++i) | |
| { | |
| edge e = edge_between (fn, path[i-1], path[i]); | |
| ands.get_or_insert ({e, bucket}) |= bit; | |
| } | |
| iors.get_or_insert ({first, bucket}) |= bit; | |
| flushes.get_or_insert ({last, bucket}) |= bit; | |
| } | |
| /* The basic blocks (except entry, exit) for this function, in topological | |
| order. Processing in this order means that the predecessor(s) exit SSAs | |
| will have been created by the time a block is processed, unless it is a | |
| loop/back edge. This simplifies processing a bit. */ | |
| vec<basic_block> blocks = topsort (fn); | |
| /* The exit SSA names for the BLOCK, the SSA name the BLOCK successors should | |
| use as inputs. */ | |
| hash_map<block_hash, tree> SSAex; | |
| /* The entry SSA name for the BLOCK. This name forms the basis for the | |
| flushing to the global accumulators. In the presence of phi nodes this is | |
| the resolved phi, otherwise it is some predecessor's exit SSA name. */ | |
| hash_map<block_hash, tree> SSAen; | |
| auto_vec<fixup, 4> todos; | |
| /* Generate the operations for each basic block. */ | |
| for (basic_block bb : blocks) | |
| { | |
| for (size_t bucket = 0; bucket != nbuckets; ++bucket) | |
| { | |
| tree ssa = nullptr; | |
| gphi *phi = nullptr; | |
| uint64_t all_and = union_incoming_bit_and (ands, bb, bucket); | |
| if (all_and && single_pred_p (bb)) | |
| { | |
| /* There is a path on this edge through the bucket, but since | |
| there is only one predecessor there it has no decisive power. | |
| Just push the predecessor's exit and have later ANDs sort it | |
| out. */ | |
| tree *prev = SSAex.get ({single_pred (bb), bucket}); | |
| gcc_checking_assert (prev); | |
| ssa = *prev; | |
| } | |
| else if (all_and) | |
| { | |
| /* There are multiple predecessors, so we need a phi. */ | |
| ssa = make_ssa_name (gcov_type_node); | |
| phi = create_phi_node (ssa, bb); | |
| } | |
| if (ssa) | |
| SSAen.put ({bb, bucket}, ssa); | |
| if (single_pred_p (bb) && single_succ_p (bb)) | |
| { | |
| /* Straight line -- the AND mask will already have been applied | |
| to the first ancestor of this chain, so we don't need to apply | |
| it here. */ | |
| } | |
| else if (!can_change_path_p (ands, bb, bucket, all_and)) | |
| { | |
| /* All incoming edges would apply the same mask, so applying the | |
| AND here would not actually distinguish paths. Such an AND | |
| will be applied later anyway so we don't need to apply it | |
| here. This is a huge improvement for large programs. */ | |
| } | |
| else for (edge e : bb->preds) | |
| { | |
| const uint64_t *bitmask = ands.get ({e, bucket}); | |
| /* There is no phi, and there are no paths through this bucket. | |
| Set the SSA name to nullptr so we don't contaminate it by | |
| pushing unrelated predecessors. */ | |
| if (!bitmask && !phi) | |
| ssa = nullptr; | |
| else if (!bitmask && phi) | |
| { | |
| tree zero = safe_insert_zero_phi_arg (e, gcov_type_node); | |
| add_phi_arg (phi, zero, e, UNKNOWN_LOCATION); | |
| } | |
| else if (all_bits_set_p (*bitmask, bucketsize) && !phi) | |
| { | |
| /* This reduces to a no-op (x & ~0) and there is no phi | |
| selection, so just push the SSA. */ | |
| gcc_checking_assert (ssa); | |
| } | |
| else if (all_bits_set_p (*bitmask, bucketsize) && phi) | |
| { | |
| /* This reduces to a no-op (x & ~0). Reusing the SSA and not | |
| emitting an unnecessary AND is a big improvement for large | |
| programs. */ | |
| tree *prev = SSAex.get ({e->src, bucket}); | |
| if (prev) | |
| add_phi_arg (phi, *prev, e, UNKNOWN_LOCATION); | |
| else | |
| todos.safe_push (fixup_noop (phi, e, bucket)); | |
| } | |
| else if (SSAex.get ({e->src, bucket})) | |
| { | |
| /* We need to apply a mask, folding if possible. If there is | |
| a phi it is already the latest-touched ssa. */ | |
| tree prev = *SSAex.get ({e->src, bucket}); | |
| gcc_assert (prev); | |
| if (constant_p (prev)) | |
| { | |
| const uint64_t x = tree_to_uhwi (prev); | |
| tree cst = build_int_cst (gcov_type_node, x & *bitmask); | |
| if (phi) | |
| add_phi_arg (phi, cst, e, UNKNOWN_LOCATION); | |
| else | |
| ssa = cst; | |
| } | |
| else | |
| { | |
| tree lhs = make_ssa_name (gcov_type_node); | |
| tree mask = build_int_cst (gcov_type_node, *bitmask); | |
| gassign *put = gimple_build_assign (lhs, BIT_AND_EXPR, | |
| prev, mask); | |
| gsi_insert_on_edge (e, put); | |
| if (phi) | |
| add_phi_arg (phi, lhs, e, UNKNOWN_LOCATION); | |
| else | |
| ssa = lhs; | |
| } | |
| } | |
| else | |
| { | |
| /* There is a phi and this edge is a back edge, | |
| which means the predecessor (and descendant) exit | |
| SSA has not been created yet. */ | |
| gcc_assert (phi); | |
| gcc_assert (e->flags & EDGE_DFS_BACK); | |
| fixup todo = fixup_and (phi, e, bucket, *bitmask, | |
| gcov_type_node); | |
| todos.safe_push (todo); | |
| } | |
| } | |
| /* Bitwise IOR. Unlike the AND this assignment can always be created | |
| right away as this should be applied to the result of the phi, | |
| AND, or single predecessor's exit SSA, and all of those have | |
| already been created. */ | |
| const uint64_t *ior = iors.get ({bb, bucket}); | |
| if (ior && !ssa) | |
| { | |
| /* In case there was no predecessor, the IOR/initial state can | |
| just be a constant. In this case, the IOR also becomes the | |
| block's entry node which means it will be considered for | |
| flushing in single-vertex paths. */ | |
| ssa = build_int_cst (gcov_type_node, *ior); | |
| SSAen.put ({bb, bucket}, ssa); | |
| } | |
| else if (ior && all_bits_set_p (*ior, bucketsize)) | |
| ssa = build_all_ones_cst (gcov_type_node); | |
| else if (ior) | |
| { | |
| gcc_assert (ssa); | |
| tree mask = build_int_cst (gcov_type_node, *ior); | |
| ssa = safe_insert_ior (bb, ssa, mask, phi, gcov_type_node); | |
| } | |
| if (ssa) | |
| SSAex.put ({bb, bucket}, ssa); | |
| } | |
| } | |
| /* Apply fixups -- now that all exit SSA names are created we can properly | |
| set the phi argument if there is a phi node, and emit the (x & mask) | |
| instruction if necessary. */ | |
| for (fixup &todo : todos) | |
| { | |
| tree *exit = SSAex.get ({todo.e->src, todo.bucket}); | |
| gcc_assert (exit && *exit); | |
| gcc_checking_assert (todo.phi); | |
| if (todo.mask) | |
| { | |
| gassign *put = gimple_build_assign (todo.lhs, BIT_AND_EXPR, *exit, | |
| todo.mask); | |
| gsi_insert_on_edge (todo.e, put); | |
| } | |
| add_phi_arg (todo.phi, todo.lhs ? todo.lhs : *exit, todo.e, | |
| UNKNOWN_LOCATION); | |
| } | |
| tree atomic_ior = nullptr; | |
| if (flag_profile_update == PROFILE_UPDATE_ATOMIC) | |
| atomic_ior = builtin_decl_explicit | |
| (TYPE_PRECISION (gcov_type_node) > 32 | |
| ? BUILT_IN_ATOMIC_FETCH_OR_8 | |
| : BUILT_IN_ATOMIC_FETCH_OR_4); | |
| /* Finally, add instructions to update the global counters. */ | |
| for (basic_block bb : blocks) | |
| { | |
| gimple_stmt_iterator gsi = gsi_after_labels (bb); | |
| for (size_t bucket = 0; bucket != nbuckets; ++bucket) | |
| { | |
| const uint64_t *bitmask = flushes.get ({bb, bucket}); | |
| if (!bitmask || !*bitmask) | |
| continue; | |
| tree *counter = SSAen.get ({bb, bucket}); | |
| gcc_checking_assert (counter); | |
| if (!*counter) | |
| continue; | |
| tree mask = nullptr; | |
| if (!all_bits_set_p (*bitmask, bucketsize)) | |
| mask = build_int_cst (gcov_type_node, *bitmask); | |
| if (bb_has_abnormal_pred (bb)) | |
| flush_on_edges (bb, bucket, *counter, mask, atomic_ior, | |
| gcov_type_node); | |
| else | |
| flush_on_gsi (&gsi, bucket, *counter, mask, atomic_ior, | |
| gcov_type_node); | |
| } | |
| } | |
| const unsigned npaths = paths.length (); | |
| blocks.release (); | |
| release_vec_vec (paths); | |
| return npaths; | |
| } |