| /* Calculate prime path coverage. |
| Copyright (C) 2024-2025 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 ()); |
| |
| 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 = SSA_NAME_DEF_STMT (local); |
| gphi *phi = 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 unecessary 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; |
| } |