Branch data Line data Source code
1 : : /* Calculate prime path coverage.
2 : : Copyright (C) 2024-2025 Free Software Foundation, Inc.
3 : :
4 : : This file is part of GCC.
5 : :
6 : : GCC is free software; you can redistribute it and/or modify it under
7 : : the terms of the GNU General Public License as published by the Free
8 : : Software Foundation; either version 3, or (at your option) any later
9 : : version.
10 : :
11 : : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 : : WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : : for more details.
15 : :
16 : : You should have received a copy of the GNU General Public License
17 : : along with GCC; see the file COPYING3. If not see
18 : : <http://www.gnu.org/licenses/>. */
19 : :
20 : : #include "config.h"
21 : : #include "system.h"
22 : : #include "coretypes.h"
23 : : #include "diagnostic-core.h"
24 : : #include "memmodel.h"
25 : : #include "target.h"
26 : : #include "function.h"
27 : : #include "basic-block.h"
28 : : #include "tree.h"
29 : : #include "tree-cfg.h"
30 : : #include "tree-nested.h"
31 : : #include "cfg.h"
32 : : #include "gimple.h"
33 : : #include "gimple-iterator.h"
34 : : #include "gimplify.h"
35 : : #include "coverage.h"
36 : : #include "ssa.h"
37 : : #include "vec.h"
38 : : #include "sbitmap.h"
39 : : #include "graphds.h"
40 : : #include "hash-map.h"
41 : : #include "bitmap.h"
42 : : #include "cfganal.h"
43 : :
44 : : bool mark_dfs_back_edges (struct function *);
45 : : vec<vec<int>> prime_paths (struct graph*, size_t);
46 : :
47 : : namespace
48 : : {
49 : :
50 : : /* Check if all the successors of BB are abnormal, e.g. setjmp. */
51 : : bool
52 : 599 : all_abnormal_succs_p (basic_block bb)
53 : : {
54 : 1259 : for (edge e : bb->succs)
55 : 326 : if (!(e->flags & EDGE_ABNORMAL))
56 : : return false;
57 : : return true;
58 : : }
59 : :
60 : : /* Build a struct graph equivalent to the CFG for the function FN. The caller
61 : : must free the returned graph with free_graph. The data field of every
62 : : vertex and edge point to the basic blocks and edges in the CFG.
63 : :
64 : : The CFG recording and gcov is not aware of abnormal edges, so they are
65 : : ignored here, too. This means some paths are lost, e.g. those that involve
66 : : setjmp/longjmp. They are still paths but would need more support from
67 : : profile.cc and gcov.cc to work. */
68 : : struct graph*
69 : 291 : cfg_as_graph (struct function* fn)
70 : : {
71 : 291 : struct graph *g = new_graph (n_basic_blocks_for_fn (fn));
72 : 291 : basic_block entry = ENTRY_BLOCK_PTR_FOR_FN (fn);
73 : 291 : basic_block exit = EXIT_BLOCK_PTR_FOR_FN (fn);
74 : :
75 : 291 : g->vertices[entry->index].data = entry;
76 : 291 : g->vertices[exit->index].data = exit;
77 : :
78 : 291 : const unsigned ignore = EDGE_FAKE | EDGE_ABNORMAL | EDGE_ABNORMAL_CALL;
79 : 291 : basic_block bb;
80 : 2590 : FOR_EACH_BB_FN (bb, fn)
81 : : {
82 : 2299 : g->vertices[bb->index].data = bb;
83 : 10282 : for (edge e : bb->succs)
84 : 3385 : if (!(e->flags & ignore) && e->dest != exit)
85 : 3017 : add_edge (g, e->src->index, e->dest->index)->data = e;
86 : : }
87 : 291 : return g;
88 : : }
89 : :
90 : : /* Check if BB's predecessor is the ENTRY_BLOCK, i.e. BB is the first real
91 : : block in the function. */
92 : : bool
93 : 633 : pred_entry_p (const_basic_block bb)
94 : : {
95 : 948 : return single_pred_p (bb) && single_pred (bb)->index == ENTRY_BLOCK;
96 : : }
97 : :
98 : : /* Find the prime paths for the function FN with the ENTRY and EXIT blocks
99 : : removed. This can lead to empty paths when there is a fake edge to the exit
100 : : block, for example for abort functions or infinite loops. Empty paths are
101 : : removed because the length of the returned vec is important. */
102 : : vec<vec<int>>
103 : 291 : find_prime_paths (struct function *fn)
104 : : {
105 : 291 : struct graph *cfg = cfg_as_graph (fn);
106 : 291 : vec<vec<int>> paths = prime_paths (cfg, path_coverage_limit);
107 : :
108 : 291 : bool any_empty = false;
109 : 3364 : for (vec<int> &path : paths)
110 : : {
111 : : /* setjmp calls will be isolated basic blocks when ABNORMAL_EDGEs are
112 : : removed. If a path is made up of just such a vertex it is pointless
113 : : and can be removed. If a function is only __builtin_exit() (see
114 : : gcov-22.C) the CFG will only have one block and look like such an
115 : : island, and we want to preserve it. */
116 : 2497 : if (path.length () == 1
117 : 633 : && !pred_entry_p (BASIC_BLOCK_FOR_FN (fn, path[0]))
118 : 3096 : && all_abnormal_succs_p (BASIC_BLOCK_FOR_FN (fn, path[0])))
119 : 311 : path.pop ();
120 : 4683 : if (!path.is_empty () && path[0] == ENTRY_BLOCK)
121 : 288 : path.ordered_remove (0);
122 : 4395 : if (!path.is_empty () && path.last () == EXIT_BLOCK)
123 : 0 : path.pop ();
124 : :
125 : 4994 : if (path.is_empty ())
126 : : {
127 : 599 : any_empty = true;
128 : 599 : path.release ();
129 : : }
130 : : }
131 : :
132 : 291 : unsigned ix1, ix2;
133 : 291 : vec<int> *ptr;
134 : 291 : if (any_empty)
135 : 2785 : VEC_ORDERED_REMOVE_IF (paths, ix1, ix2, ptr, ptr->is_empty ());
136 : :
137 : 291 : return paths;
138 : : }
139 : :
140 : : /* Return the edge between SRC and DST. */
141 : : edge
142 : 8451 : edge_between (struct function *fn, int src, int dst)
143 : : {
144 : 8451 : basic_block bbsrc = BASIC_BLOCK_FOR_FN (fn, src);
145 : 8451 : basic_block bbdst = BASIC_BLOCK_FOR_FN (fn, dst);
146 : 49279 : for (edge e : bbsrc->succs)
147 : 32377 : if (e->dest == bbdst)
148 : 8451 : return e;
149 : 0 : gcc_unreachable ();
150 : : }
151 : :
152 : : /* Get the basic blocks of FN in topological order so that all predecessors
153 : : come before the vertex, while ignoring back edges. */
154 : : vec<basic_block>
155 : 288 : topsort (struct function *fn)
156 : : {
157 : 288 : vec<basic_block> blocks {};
158 : 288 : auto_vec<int> order {};
159 : 288 : blocks.reserve (n_basic_blocks_for_fn (fn));
160 : 288 : order.safe_grow (n_basic_blocks_for_fn (fn));
161 : :
162 : 288 : const int n = post_order_compute (order.address (), false, false);
163 : 2365 : for (int i = 0; i < n; ++i)
164 : 2077 : blocks.quick_push (BASIC_BLOCK_FOR_FN (fn, order[i]));
165 : 288 : blocks.reverse ();
166 : 288 : return blocks;
167 : 288 : }
168 : :
169 : : /* Hasher for maps where the key is a pair of edge/basic_block and bucket id
170 : : (size_t). */
171 : : template <typename T>
172 : : using bucket_hash = pair_hash <nofree_ptr_hash <T>,
173 : : int_hash <size_t, size_t(-1)>>;
174 : :
175 : : /* Hasher for {edge, bucket-id} keys. */
176 : : using edge_hash = bucket_hash <edge_def>;
177 : : /* Hasher for {basic_block, bucket-id} keys. */
178 : : using block_hash = bucket_hash <basic_block_def>;
179 : :
180 : : /* Find the union of the bitsets sets on the incoming edges of BB at BUCKET.
181 : : If no paths go through BB the returned bitset would be empty. Bitsets are
182 : : looked up in ANDS, and if the nth bit is set then the nth path contains that
183 : : edge. */
184 : : uint64_t
185 : 2805 : union_incoming_bit_and (hash_map <edge_hash, uint64_t> &ands,
186 : : const basic_block bb, size_t bucket)
187 : : {
188 : 2805 : uint64_t inc = 0;
189 : 12910 : for (edge e : bb->preds)
190 : : {
191 : 4495 : const uint64_t *val = ands.get ({e, bucket});
192 : 4495 : inc |= (val ? *val : 0);
193 : : }
194 : 2805 : return inc;
195 : : }
196 : :
197 : :
198 : : /* Check if the incoming edges have the power to modify the paths in flight for
199 : : BUCKET. If all the incoming edges would apply the same bitmask the
200 : : BB+BUCKET will not actually update the path set, and we don't need to emit
201 : : an AND_EXPR and have a later fork distinguish the paths. */
202 : : bool
203 : 586 : can_change_path_p (hash_map <edge_hash, uint64_t> &ands,
204 : : const basic_block bb, size_t bucket, uint64_t all_and)
205 : : {
206 : 2012 : for (edge e : bb->preds)
207 : : {
208 : 620 : const uint64_t *e_and = ands.get ({e, bucket});
209 : 620 : if (!e_and || *e_and != all_and)
210 : 586 : return true;
211 : : }
212 : : return false;
213 : : }
214 : :
215 : : /* Check if all bits in BITSET are 1 for the target size TARGET_SIZE. For a
216 : : 32-bit target only the bits in the lower half should be set, and this should
217 : : return true when all bits in the lower half are set, even if the bitset type
218 : : have room for more bits. */
219 : : bool
220 : 1850 : all_bits_set_p (uint64_t bitset, size_t target_size)
221 : : {
222 : 3023 : return (size_t)popcount_hwi (bitset) == target_size;
223 : : }
224 : :
225 : : /* Create a constant or SSA name of GCOV_TYPE_NODE type and zero-assign to it
226 : : safely on the edge E. If the edge is abnormal it is assumed the phi is
227 : : abnormal and we need an SSA name, otherwise fall back to a constant. The
228 : : returned value is safe to use with add_phi_arg ().
229 : :
230 : : If the edge is abnormal we cannot insert on it directly, and instead
231 : : carefully add the assignment on the source block. If that source block ends
232 : : with control flow (like those produced by _setjmp) we must insert before to
233 : : not break that invariant, otherwise insert after so that things like the
234 : : setjmp receiver is the first element of the basic block. Doing the assign
235 : : is necessary as phis cannot resolve to constants. */
236 : : tree
237 : 725 : safe_insert_zero_phi_arg (edge e, tree gcov_type_node)
238 : : {
239 : 725 : tree cst = build_zero_cst (gcov_type_node);
240 : 725 : if (!(e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)))
241 : : return cst;
242 : :
243 : 43 : tree zero = make_ssa_name (gcov_type_node);
244 : 43 : gassign *put = gimple_build_assign (zero, cst);
245 : 43 : gimple_stmt_iterator gsi = gsi_start_nondebug_after_labels_bb (e->src);
246 : 43 : if (gimple_call_internal_p (*gsi, IFN_ABNORMAL_DISPATCHER)
247 : 43 : || stmt_ends_bb_p (*gsi))
248 : 21 : gsi_insert_before (&gsi, put, GSI_NEW_STMT);
249 : : else
250 : 22 : gsi_insert_after (&gsi, put, GSI_NEW_STMT);
251 : :
252 : : return zero;
253 : : }
254 : :
255 : : /* Check if SSA is a constant value (created by build_int_cst) and can be
256 : : folded. */
257 : : bool
258 : 1111 : constant_p (tree ssa)
259 : : {
260 : 1111 : return tree_fits_uhwi_p (ssa);
261 : : }
262 : :
263 : : /* A fixup task. When resolving the exit SSA for a back edge arg to a phi
264 : : node, the exit SSA has not been created yet. Record what needs to be done
265 : : when it is created, and tie the phi to the right SSA name once it is
266 : : guaranteed it is created. If MASK is nullptr the predecessor's SSA should
267 : : be used as-is, and does not need an AND. This should only be created with
268 : : the helpers fixup_noop and fixup_and. */
269 : : struct fixup
270 : : {
271 : : gphi *phi;
272 : : edge e;
273 : : tree lhs;
274 : : tree mask;
275 : : size_t bucket;
276 : : };
277 : :
278 : : /* Create a fixup with a no-op for the PHI in BUCKET. Use this when the edge E
279 : : does not need an AND applied and should rather propagate the predecessor's
280 : : SSA name. */
281 : : fixup
282 : 0 : fixup_noop (gphi *phi, edge e, size_t bucket)
283 : : {
284 : 0 : fixup todo;
285 : 0 : todo.phi = phi;
286 : 0 : todo.e = e;
287 : 0 : todo.bucket = bucket;
288 : 0 : todo.lhs = nullptr;
289 : 0 : todo.mask = nullptr;
290 : 0 : return todo;
291 : : }
292 : :
293 : : /* Create a fixup for PHI through BUCKET with the exit SSA name E->src ANDed
294 : : with MASK (E->src & MASK). GCOV_TYPE_NODE should be a tree of the gcov type
295 : : node for creating SSA names. */
296 : : fixup
297 : 62 : fixup_and (gphi *phi, edge e, size_t bucket, uint64_t mask,
298 : : tree gcov_type_node)
299 : : {
300 : 62 : fixup todo;
301 : 62 : todo.phi = phi;
302 : 62 : todo.e = e;
303 : 62 : todo.bucket = bucket;
304 : 62 : todo.lhs = make_ssa_name (gcov_type_node);
305 : 62 : todo.mask = build_int_cst (gcov_type_node, mask);
306 : 62 : return todo;
307 : : }
308 : :
309 : : /* Insert LOCAL |= MASK on BB safely, even when BB is a returns_twice block.
310 : :
311 : : This is a helper to safely emit code for updating the path bitmask in the
312 : : presence of abnormal edges and returns_twice blocks, since they have special
313 : : restrictions on edge splits and first/last instructions on the block. */
314 : : tree
315 : 170 : safe_insert_ior (basic_block bb, tree local, tree mask, gphi *phi,
316 : : tree gcov_type_node)
317 : : {
318 : 170 : gimple_stmt_iterator gsi = gsi_start_nondebug_after_labels_bb (bb);
319 : 170 : gimple *stmt = gsi_stmt (gsi);
320 : :
321 : : /* This is a returns_twice block (e.g. setjmp) which does not really expect
322 : : anything before or after, so we cannot insert the IOR on the block itself.
323 : : We move the IORs to the predecessors instead and update the phi. The
324 : : abnormal edge cannot be split, so in that case we carefully put the IOR
325 : : after the ABNORMAL_DISPATCHER. */
326 : 155 : if (stmt && is_gimple_call (stmt)
327 : 196 : && (gimple_call_flags (stmt) & ECF_RETURNS_TWICE))
328 : : {
329 : 88 : for (edge e : bb->preds)
330 : : {
331 : 37 : gcc_checking_assert (phi);
332 : 37 : tree next = make_ssa_name (gcov_type_node);
333 : 37 : tree prev = gimple_phi_arg_def_from_edge (phi, e);
334 : 37 : gassign *put = prev
335 : 37 : ? gimple_build_assign (next, BIT_IOR_EXPR, prev, mask)
336 : 1 : : gimple_build_assign (next, mask);
337 : :
338 : 37 : gimple_stmt_iterator gsi = gsi_last_bb (e->src);
339 : 37 : add_phi_arg (phi, next, e, UNKNOWN_LOCATION);
340 : :
341 : 37 : if (e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
342 : 17 : gsi_insert_before (&gsi, put, GSI_SAME_STMT);
343 : : else
344 : 20 : gsi_insert_on_edge (e, put);
345 : : }
346 : : }
347 : : else
348 : : {
349 : 153 : tree next = make_ssa_name (gcov_type_node);
350 : 153 : gassign *put = gimple_build_assign (next, BIT_IOR_EXPR, local, mask);
351 : 153 : gsi_insert_before (&gsi, put, GSI_SAME_STMT);
352 : 153 : local = next;
353 : : }
354 : 170 : return local;
355 : : }
356 : :
357 : : /* Insert instructions updating the global counter at BUCKET with the contents
358 : : of (LOCAL & MASK). LOCAL is the SSA counter for this bucket, MASK the bits
359 : : that should be updated (that is, the paths that end in this basic block).
360 : : If ATOMIC_IOR is non-null the it uses atomics. GCOV_TYPE_NODE should be a
361 : : tree of the gcov type node for creating SSA names.
362 : :
363 : : global[BUCKET] |= (LOCAL & MASK)
364 : :
365 : : If MASK is null, no mask is applied and it becomes:
366 : :
367 : : global[BUCKET] |= LOCAL
368 : :
369 : : This function should only be necessary for the successor of an
370 : : ABNORMAL_DISPATCHER e.g. the destination of a longjmp. Paths starting at a
371 : : longjmp do not have anything to flush, so those edges are simply ignored.
372 : : Since this is a returns_twice block we cannot put anything before (or really
373 : : after), so we instrument on the edge itself, rather than messing with
374 : : splitting and changing the graph now.
375 : :
376 : : This is similar to gsi_safe_insert_before, but this function does not
377 : : immediately commit edge inserts and does not split blocks. */
378 : : void
379 : 17 : flush_on_edges (basic_block bb, size_t bucket, tree local, tree mask,
380 : : tree atomic_ior, tree gcov_type_node)
381 : : {
382 : 17 : gimple *def = SSA_NAME_DEF_STMT (local);
383 : 17 : gphi *phi = dyn_cast <gphi *> (def);
384 : :
385 : 17 : tree relaxed = nullptr;
386 : 17 : if (atomic_ior)
387 : 0 : relaxed = build_int_cst (integer_type_node, MEMMODEL_RELAXED);
388 : :
389 : 88 : for (edge e : bb->preds)
390 : : {
391 : 37 : if (e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
392 : 17 : continue;
393 : :
394 : 20 : tree global = tree_coverage_counter_ref (GCOV_COUNTER_PATHS, bucket);
395 : 20 : if (phi)
396 : 20 : local = gimple_phi_arg_def_from_edge (phi, e);
397 : :
398 : 20 : tree global_copy = make_ssa_name (gcov_type_node);
399 : 20 : gassign *ga1 = gimple_build_assign (global_copy, global);
400 : 20 : gsi_insert_on_edge (e, ga1);
401 : :
402 : 20 : tree masked;
403 : 20 : if (mask)
404 : : {
405 : 20 : masked = make_ssa_name (gcov_type_node);
406 : 20 : gassign *ga2 = gimple_build_assign (masked, BIT_AND_EXPR, local,
407 : : mask);
408 : 20 : gsi_insert_on_edge (e, ga2);
409 : : }
410 : : else
411 : : masked = local;
412 : :
413 : 20 : if (atomic_ior)
414 : : {
415 : 0 : global = unshare_expr (global);
416 : 0 : gcall *call = gimple_build_call (atomic_ior, 3, build_addr (global),
417 : : masked, relaxed);
418 : 0 : gsi_insert_on_edge (e, call);
419 : : }
420 : : else
421 : : {
422 : 20 : tree tmp = make_ssa_name (gcov_type_node);
423 : 20 : gassign *ga3 = gimple_build_assign (tmp, BIT_IOR_EXPR, global_copy,
424 : : masked);
425 : 20 : gassign *ga4 = gimple_build_assign (unshare_expr (global), tmp);
426 : 20 : gsi_insert_on_edge (e, ga3);
427 : 20 : gsi_insert_on_edge (e, ga4);
428 : : }
429 : : }
430 : 17 : }
431 : :
432 : : /* Insert instructions update the global counter at BUCKET with the contents of
433 : : (LOCAL & MASK). LOCAL is the SSA counter for this bucket, MASK the bits
434 : : that should be updated (that is, the paths that end in this basic block).
435 : : If ATOMIC_IOR is non-null the it uses atomics. GCOV_TYPE_NODE should be a
436 : : tree of the gcov type node for creating SSA names.
437 : :
438 : : global[BUCKET] |= (LOCAL & MASK)
439 : :
440 : : If MASK is null, no mask is applied and it becomes:
441 : :
442 : : global[BUCKET] |= LOCAL
443 : :
444 : : This function should be used on every block except returns_twice blocks (see
445 : : flush_on_edge) as all incoming edges can use the same flushing code. */
446 : : void
447 : 490 : flush_on_gsi (gimple_stmt_iterator *gsi, size_t bucket, tree local, tree mask,
448 : : tree atomic_ior, tree gcov_type_node)
449 : : {
450 : 490 : tree relaxed = nullptr;
451 : 490 : if (atomic_ior)
452 : 85 : relaxed = build_int_cst (integer_type_node, MEMMODEL_RELAXED);
453 : 490 : tree global = tree_coverage_counter_ref (GCOV_COUNTER_PATHS, bucket);
454 : :
455 : 490 : tree global_copy = make_ssa_name (gcov_type_node);
456 : 490 : gassign *ga1 = gimple_build_assign (global_copy, global);
457 : 490 : gsi_insert_before (gsi, ga1, GSI_SAME_STMT);
458 : :
459 : 490 : tree masked;
460 : 490 : if (mask)
461 : : {
462 : 480 : masked = make_ssa_name (gcov_type_node);
463 : 480 : gassign *ga2 = gimple_build_assign (masked, BIT_AND_EXPR, local, mask);
464 : 480 : gsi_insert_before (gsi, ga2, GSI_SAME_STMT);
465 : : }
466 : : else
467 : : masked = local;
468 : :
469 : 490 : if (atomic_ior)
470 : : {
471 : 85 : global = unshare_expr (global);
472 : 85 : gcall *call = gimple_build_call (atomic_ior, 3, build_addr (global),
473 : : masked, relaxed);
474 : 85 : gsi_insert_before (gsi, call, GSI_SAME_STMT);
475 : : }
476 : : else
477 : : {
478 : 405 : tree tmp = make_ssa_name (gcov_type_node);
479 : 405 : gassign *ga3 = gimple_build_assign (tmp, BIT_IOR_EXPR, global_copy,
480 : : masked);
481 : 405 : gassign *ga4 = gimple_build_assign (unshare_expr (global), tmp);
482 : 405 : gsi_insert_before (gsi, ga3, GSI_SAME_STMT);
483 : 405 : gsi_insert_before (gsi, ga4, GSI_SAME_STMT);
484 : : }
485 : 490 : }
486 : :
487 : : } // namespace
488 : :
489 : :
490 : : /* Instrument FN for prime path coverage, enabled by -fpath-coverage. The
491 : : number of paths grows very fast with the complexity (control flow) which
492 : : explodes compile times and object file size. Giving up is controlled by the
493 : : -fpath-coverage-limit flag. The paths are sorted lexicographically by basic
494 : : block id, and each path is identified by its index in the sorted set of
495 : : paths, which in turn corresponds to a bit in a large bitset associated with
496 : : FN. The monitoring code is a few bitwise operations added to edges and
497 : : basic blocks to maintain a set of live paths (note that many paths may
498 : : overlap and that many paths may be covered by the same input). When
499 : : reaching the final vertex of a path the global counters are updated.
500 : :
501 : : This is made more complicated by the gcov type having very limited size. To
502 : : support functions with more than 32/64 paths the bitmap is implemented on
503 : : top of a sequence of gcov integers, "buckets", where path N is recorded as
504 : : bit N%64 in bucket N/64. For large functions, an individual basic block
505 : : will only be part of a small subset of paths, and by extension buckets and
506 : : local counters. Only the necessary counters are read and written. */
507 : : unsigned
508 : 291 : instrument_prime_paths (struct function *fn)
509 : : {
510 : 291 : mark_dfs_back_edges (fn);
511 : 291 : vec<vec<int>> paths = find_prime_paths (fn);
512 : :
513 : 291 : if (paths.is_empty ())
514 : : {
515 : 3 : warning_at (fn->function_start_locus, OPT_Wcoverage_too_many_paths,
516 : : "paths exceeding limit, giving up path coverage");
517 : 3 : release_vec_vec (paths);
518 : 3 : return 0;
519 : : }
520 : :
521 : 288 : tree gcov_type_node = get_gcov_type ();
522 : 288 : const size_t bucketsize = TYPE_PRECISION (gcov_type_node);
523 : 288 : const size_t nbuckets = (paths.length () + (bucketsize - 1)) / bucketsize;
524 : 288 : gcc_checking_assert (sizeof (uint64_t) * BITS_PER_UNIT >= bucketsize);
525 : :
526 : 288 : if (!coverage_counter_alloc (GCOV_COUNTER_PATHS, nbuckets))
527 : : {
528 : 0 : release_vec_vec (paths);
529 : 0 : return 0;
530 : : }
531 : :
532 : 288 : hash_map <edge_hash, uint64_t> ands;
533 : 288 : hash_map <block_hash, uint64_t> iors;
534 : 288 : hash_map <block_hash, uint64_t> flushes;
535 : :
536 : : /* Now that we have all paths we must figure out what bitmasks must be
537 : : applied on the edges. We also record in which basic block the path starts
538 : : (e.g. accumulator resets) and ends (accumulator flushes). */
539 : 2186 : for (size_t pathno = 0; pathno != paths.length (); ++pathno)
540 : : {
541 : 1898 : const vec<int> &path = paths[pathno];
542 : 1898 : const size_t bucket = pathno / bucketsize;
543 : 1898 : const uint64_t bit = uint64_t (1) << (pathno % bucketsize);
544 : :
545 : 1898 : basic_block first = BASIC_BLOCK_FOR_FN (fn, path[0]);
546 : 1898 : basic_block last = BASIC_BLOCK_FOR_FN (fn, path[path.length () - 1]);
547 : :
548 : 20698 : for (unsigned i = 1; i != path.length (); ++i)
549 : : {
550 : 8451 : edge e = edge_between (fn, path[i-1], path[i]);
551 : 8451 : ands.get_or_insert ({e, bucket}) |= bit;
552 : : }
553 : :
554 : 1898 : iors.get_or_insert ({first, bucket}) |= bit;
555 : 1898 : flushes.get_or_insert ({last, bucket}) |= bit;
556 : : }
557 : :
558 : : /* The basic blocks (except entry, exit) for this function, in topological
559 : : order. Processing in this order means that the predecessor(s) exit SSAs
560 : : will have been created by the time a block is processed, unless it is a
561 : : loop/back edge. This simplifies processing a bit. */
562 : 288 : vec<basic_block> blocks = topsort (fn);
563 : :
564 : : /* The exit SSA names for the BLOCK, the SSA name the BLOCK successors should
565 : : use as inputs. */
566 : 288 : hash_map<block_hash, tree> SSAex;
567 : : /* The entry SSA name for the BLOCK. This name forms the basis for the
568 : : flushing to the global accumulators. In the presence of phi nodes this is
569 : : the resolved phi, otherwise it is some predecessor's exit SSA name. */
570 : 288 : hash_map<block_hash, tree> SSAen;
571 : :
572 : 288 : auto_vec<fixup, 4> todos;
573 : :
574 : : /* Generate the operations for each basic block. */
575 : 2941 : for (basic_block bb : blocks)
576 : : {
577 : 4882 : for (size_t bucket = 0; bucket != nbuckets; ++bucket)
578 : : {
579 : 2805 : tree ssa = nullptr;
580 : 2805 : gphi *phi = nullptr;
581 : 2805 : uint64_t all_and = union_incoming_bit_and (ands, bb, bucket);
582 : :
583 : 2805 : if (all_and && single_pred_p (bb))
584 : : {
585 : : /* There is a path on this edge through the bucket, but since
586 : : there is only one predecessor there it has no decisive power.
587 : : Just push the predecessor's exit and have later ANDs sort it
588 : : out. */
589 : 1571 : tree *prev = SSAex.get ({single_pred (bb), bucket});
590 : 1571 : gcc_checking_assert (prev);
591 : 1571 : ssa = *prev;
592 : : }
593 : 1234 : else if (all_and)
594 : : {
595 : : /* There are multiple predecessors, so we need a phi. */
596 : 250 : ssa = make_ssa_name (gcov_type_node);
597 : 250 : phi = create_phi_node (ssa, bb);
598 : : }
599 : :
600 : 2805 : if (ssa)
601 : 1821 : SSAen.put ({bb, bucket}, ssa);
602 : :
603 : 2805 : if (single_pred_p (bb) && single_succ_p (bb))
604 : : {
605 : : /* Straight line -- the AND mask will already have been applied
606 : : to the first ancestor of this chain, so we don't need to apply
607 : : it here. */
608 : : }
609 : 586 : else if (!can_change_path_p (ands, bb, bucket, all_and))
610 : : {
611 : : /* All incoming edges would apply the same mask, so applying the
612 : : AND here would not actually distinguish paths. Such an AND
613 : : will be applied later anyway so we don't need to apply it
614 : : here. This is a huge improvement for large programs. */
615 : : }
616 : 3154 : else for (edge e : bb->preds)
617 : : {
618 : 2056 : const uint64_t *bitmask = ands.get ({e, bucket});
619 : : /* There is no phi, and there are no paths through this bucket.
620 : : Set the SSA name to nullptr so we don't contaminate it by
621 : : pushing unrelated predecessors. */
622 : 2056 : if (!bitmask && !phi)
623 : 158 : ssa = nullptr;
624 : 1898 : else if (!bitmask && phi)
625 : : {
626 : 725 : tree zero = safe_insert_zero_phi_arg (e, gcov_type_node);
627 : 725 : add_phi_arg (phi, zero, e, UNKNOWN_LOCATION);
628 : : }
629 : 1173 : else if (all_bits_set_p (*bitmask, bucketsize) && !phi)
630 : : {
631 : : /* This reduces to a no-op (x & ~0) and there is no phi
632 : : selection, so just push the SSA. */
633 : 0 : gcc_checking_assert (ssa);
634 : : }
635 : 1173 : else if (all_bits_set_p (*bitmask, bucketsize) && phi)
636 : : {
637 : : /* This reduces to a no-op (x & ~0). Reusing the SSA and not
638 : : emitting an unecessary AND is a big improvement for large
639 : : programs. */
640 : 0 : tree *prev = SSAex.get ({e->src, bucket});
641 : 0 : if (prev)
642 : 0 : add_phi_arg (phi, *prev, e, UNKNOWN_LOCATION);
643 : : else
644 : 0 : todos.safe_push (fixup_noop (phi, e, bucket));
645 : : }
646 : 1173 : else if (SSAex.get ({e->src, bucket}))
647 : : {
648 : : /* We need to apply a mask, folding if possible. If there is
649 : : a phi it is already the latest-touched ssa. */
650 : 1111 : tree prev = *SSAex.get ({e->src, bucket});
651 : 1111 : gcc_assert (prev);
652 : 1111 : if (constant_p (prev))
653 : : {
654 : 283 : const uint64_t x = tree_to_uhwi (prev);
655 : 283 : tree cst = build_int_cst (gcov_type_node, x & *bitmask);
656 : 283 : if (phi)
657 : 283 : add_phi_arg (phi, cst, e, UNKNOWN_LOCATION);
658 : : else
659 : 0 : ssa = cst;
660 : : }
661 : : else
662 : : {
663 : 828 : tree lhs = make_ssa_name (gcov_type_node);
664 : 828 : tree mask = build_int_cst (gcov_type_node, *bitmask);
665 : 828 : gassign *put = gimple_build_assign (lhs, BIT_AND_EXPR,
666 : : prev, mask);
667 : 828 : gsi_insert_on_edge (e, put);
668 : 828 : if (phi)
669 : 828 : add_phi_arg (phi, lhs, e, UNKNOWN_LOCATION);
670 : : else
671 : 0 : ssa = lhs;
672 : : }
673 : : }
674 : : else
675 : : {
676 : : /* There is a phi and this edge is a back edge,
677 : : which means the predecessor (and descendant) exit
678 : : SSA has not been created yet. */
679 : 62 : gcc_assert (phi);
680 : 62 : gcc_assert (e->flags & EDGE_DFS_BACK);
681 : 62 : fixup todo = fixup_and (phi, e, bucket, *bitmask,
682 : : gcov_type_node);
683 : 62 : todos.safe_push (todo);
684 : : }
685 : : }
686 : :
687 : : /* Bitwise IOR. Unlike the AND this assignment can always be created
688 : : right away as this should be applied to the result of the phi,
689 : : AND, or single predecessor's exit SSA, and all of those have
690 : : already been created. */
691 : 2805 : const uint64_t *ior = iors.get ({bb, bucket});
692 : 2805 : if (ior && !ssa)
693 : : {
694 : : /* In case there was no predecessor, the IOR/initial state can
695 : : just be a constant. In this case, the IOR also becomes the
696 : : block's entry node which means it will be considered for
697 : : flushing in single-vertex paths. */
698 : 292 : ssa = build_int_cst (gcov_type_node, *ior);
699 : 292 : SSAen.put ({bb, bucket}, ssa);
700 : : }
701 : 170 : else if (ior && all_bits_set_p (*ior, bucketsize))
702 : 0 : ssa = build_all_ones_cst (gcov_type_node);
703 : 2513 : else if (ior)
704 : : {
705 : 170 : gcc_assert (ssa);
706 : 170 : tree mask = build_int_cst (gcov_type_node, *ior);
707 : 170 : ssa = safe_insert_ior (bb, ssa, mask, phi, gcov_type_node);
708 : : }
709 : :
710 : 2805 : if (ssa)
711 : 2113 : SSAex.put ({bb, bucket}, ssa);
712 : : }
713 : : }
714 : :
715 : : /* Apply fixups -- now that all exit SSA names are created we can properly
716 : : set the phi argument if there is a phi node, and emit the (x & mask)
717 : : instruction if necessary. */
718 : 926 : for (fixup &todo : todos)
719 : : {
720 : 62 : tree *exit = SSAex.get ({todo.e->src, todo.bucket});
721 : 62 : gcc_assert (exit && *exit);
722 : 62 : gcc_checking_assert (todo.phi);
723 : 62 : if (todo.mask)
724 : : {
725 : 62 : gassign *put = gimple_build_assign (todo.lhs, BIT_AND_EXPR, *exit,
726 : : todo.mask);
727 : 62 : gsi_insert_on_edge (todo.e, put);
728 : : }
729 : :
730 : 62 : add_phi_arg (todo.phi, todo.lhs ? todo.lhs : *exit, todo.e,
731 : : UNKNOWN_LOCATION);
732 : : }
733 : :
734 : 288 : tree atomic_ior = nullptr;
735 : 288 : if (flag_profile_update == PROFILE_UPDATE_ATOMIC)
736 : 34 : atomic_ior = builtin_decl_explicit
737 : 34 : (TYPE_PRECISION (gcov_type_node) > 32
738 : : ? BUILT_IN_ATOMIC_FETCH_OR_8
739 : : : BUILT_IN_ATOMIC_FETCH_OR_4);
740 : :
741 : : /* Finally, add instructions to update the global counters. */
742 : 2653 : for (basic_block bb : blocks)
743 : : {
744 : 2077 : gimple_stmt_iterator gsi = gsi_after_labels (bb);
745 : 4882 : for (size_t bucket = 0; bucket != nbuckets; ++bucket)
746 : : {
747 : 2805 : const uint64_t *bitmask = flushes.get ({bb, bucket});
748 : 2805 : if (!bitmask || !*bitmask)
749 : 2298 : continue;
750 : :
751 : 507 : tree *counter = SSAen.get ({bb, bucket});
752 : 507 : gcc_checking_assert (counter);
753 : 507 : if (!*counter)
754 : 0 : continue;
755 : :
756 : 507 : tree mask = nullptr;
757 : 507 : if (!all_bits_set_p (*bitmask, bucketsize))
758 : 497 : mask = build_int_cst (gcov_type_node, *bitmask);
759 : :
760 : 507 : if (bb_has_abnormal_pred (bb))
761 : 17 : flush_on_edges (bb, bucket, *counter, mask, atomic_ior,
762 : : gcov_type_node);
763 : : else
764 : 490 : flush_on_gsi (&gsi, bucket, *counter, mask, atomic_ior,
765 : : gcov_type_node);
766 : : }
767 : : }
768 : :
769 : 288 : const unsigned npaths = paths.length ();
770 : 288 : blocks.release ();
771 : 288 : release_vec_vec (paths);
772 : 288 : return npaths;
773 : 288 : }
|
