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