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 595 : all_abnormal_succs_p (basic_block bb)
53 : {
54 1254 : for (edge e : bb->succs)
55 325 : 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 288 : cfg_as_graph (struct function* fn)
70 : {
71 288 : struct graph *g = new_graph (n_basic_blocks_for_fn (fn));
72 288 : basic_block entry = ENTRY_BLOCK_PTR_FOR_FN (fn);
73 288 : basic_block exit = EXIT_BLOCK_PTR_FOR_FN (fn);
74 :
75 288 : g->vertices[entry->index].data = entry;
76 288 : g->vertices[exit->index].data = exit;
77 :
78 288 : const unsigned ignore = EDGE_FAKE | EDGE_ABNORMAL | EDGE_ABNORMAL_CALL;
79 288 : basic_block bb;
80 2550 : FOR_EACH_BB_FN (bb, fn)
81 : {
82 2262 : g->vertices[bb->index].data = bb;
83 10138 : for (edge e : bb->succs)
84 3352 : if (!(e->flags & ignore) && e->dest != exit)
85 2986 : add_edge (g, e->src->index, e->dest->index)->data = e;
86 : }
87 288 : 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 631 : pred_entry_p (const_basic_block bb)
94 : {
95 945 : 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 288 : find_prime_paths (struct function *fn)
104 : {
105 288 : struct graph *cfg = cfg_as_graph (fn);
106 288 : vec<vec<int>> paths = prime_paths (cfg, path_coverage_limit);
107 :
108 288 : bool any_empty = false;
109 3359 : 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 2501 : if (path.length () == 1
117 631 : && !pred_entry_p (BASIC_BLOCK_FOR_FN (fn, path[0]))
118 3096 : && all_abnormal_succs_p (BASIC_BLOCK_FOR_FN (fn, path[0])))
119 309 : path.pop ();
120 4693 : if (!path.is_empty () && path[0] == ENTRY_BLOCK)
121 285 : path.ordered_remove (0);
122 4408 : if (!path.is_empty () && path.last () == EXIT_BLOCK)
123 0 : path.pop ();
124 :
125 5002 : if (path.is_empty ())
126 : {
127 594 : any_empty = true;
128 594 : path.release ();
129 : }
130 : }
131 :
132 288 : unsigned ix1, ix2;
133 288 : vec<int> *ptr;
134 288 : if (any_empty)
135 2786 : VEC_ORDERED_REMOVE_IF (paths, ix1, ix2, ptr, ptr->is_empty ());
136 :
137 288 : return paths;
138 : }
139 :
140 : /* Return the edge between SRC and DST. */
141 : edge
142 8507 : edge_between (struct function *fn, int src, int dst)
143 : {
144 8507 : basic_block bbsrc = BASIC_BLOCK_FOR_FN (fn, src);
145 8507 : basic_block bbdst = BASIC_BLOCK_FOR_FN (fn, dst);
146 49504 : for (edge e : bbsrc->succs)
147 32490 : if (e->dest == bbdst)
148 8507 : 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 285 : topsort (struct function *fn)
156 : {
157 285 : vec<basic_block> blocks {};
158 285 : auto_vec<int> order {};
159 285 : blocks.reserve (n_basic_blocks_for_fn (fn));
160 285 : order.safe_grow (n_basic_blocks_for_fn (fn));
161 :
162 285 : const int n = post_order_compute (order.address (), false, false);
163 2325 : for (int i = 0; i < n; ++i)
164 2040 : blocks.quick_push (BASIC_BLOCK_FOR_FN (fn, order[i]));
165 285 : blocks.reverse ();
166 285 : return blocks;
167 285 : }
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 2768 : union_incoming_bit_and (hash_map <edge_hash, uint64_t> &ands,
186 : const basic_block bb, size_t bucket)
187 : {
188 2768 : uint64_t inc = 0;
189 12767 : for (edge e : bb->preds)
190 : {
191 4463 : const uint64_t *val = ands.get ({e, bucket});
192 4463 : inc |= (val ? *val : 0);
193 : }
194 2768 : 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 591 : 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 2030 : for (edge e : bb->preds)
207 : {
208 625 : const uint64_t *e_and = ands.get ({e, bucket});
209 625 : if (!e_and || *e_and != all_and)
210 591 : 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 1857 : all_bits_set_p (uint64_t bitset, size_t target_size)
221 : {
222 3034 : 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 726 : safe_insert_zero_phi_arg (edge e, tree gcov_type_node)
238 : {
239 726 : tree cst = build_zero_cst (gcov_type_node);
240 726 : 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 1132 : constant_p (tree ssa)
259 : {
260 1132 : 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 63 : fixup_and (gphi *phi, edge e, size_t bucket, uint64_t mask,
298 : tree gcov_type_node)
299 : {
300 63 : fixup todo;
301 63 : todo.phi = phi;
302 63 : todo.e = e;
303 63 : todo.bucket = bucket;
304 63 : todo.lhs = make_ssa_name (gcov_type_node);
305 63 : todo.mask = build_int_cst (gcov_type_node, mask);
306 63 : 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 173 : safe_insert_ior (basic_block bb, tree local, tree mask, gphi *phi,
316 : tree gcov_type_node)
317 : {
318 173 : gimple_stmt_iterator gsi = gsi_start_nondebug_after_labels_bb (bb);
319 173 : 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 157 : if (stmt && is_gimple_call (stmt)
327 199 : && (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 156 : tree next = make_ssa_name (gcov_type_node);
350 156 : gassign *put = gimple_build_assign (next, BIT_IOR_EXPR, local, mask);
351 156 : gsi_insert_before (&gsi, put, GSI_SAME_STMT);
352 156 : local = next;
353 : }
354 173 : 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 18 : flush_on_edges (basic_block bb, size_t bucket, tree local, tree mask,
380 : tree atomic_ior, tree gcov_type_node)
381 : {
382 18 : gimple *def = !constant_p (local) ? SSA_NAME_DEF_STMT (local) : NULL;
383 17 : gphi *phi = safe_dyn_cast <gphi *> (def);
384 :
385 18 : tree relaxed = nullptr;
386 18 : if (atomic_ior)
387 0 : relaxed = build_int_cst (integer_type_node, MEMMODEL_RELAXED);
388 :
389 93 : for (edge e : bb->preds)
390 : {
391 39 : if (e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
392 18 : continue;
393 :
394 21 : tree global = tree_coverage_counter_ref (GCOV_COUNTER_PATHS, bucket);
395 21 : if (phi)
396 20 : local = gimple_phi_arg_def_from_edge (phi, e);
397 :
398 21 : tree global_copy = make_ssa_name (gcov_type_node);
399 21 : gassign *ga1 = gimple_build_assign (global_copy, global);
400 21 : gsi_insert_on_edge (e, ga1);
401 :
402 21 : tree masked;
403 21 : if (mask)
404 : {
405 21 : masked = make_ssa_name (gcov_type_node);
406 21 : gassign *ga2 = gimple_build_assign (masked, BIT_AND_EXPR, local,
407 : mask);
408 21 : gsi_insert_on_edge (e, ga2);
409 : }
410 : else
411 : masked = local;
412 :
413 21 : 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 21 : tree tmp = make_ssa_name (gcov_type_node);
423 21 : gassign *ga3 = gimple_build_assign (tmp, BIT_IOR_EXPR, global_copy,
424 : masked);
425 21 : gassign *ga4 = gimple_build_assign (unshare_expr (global), tmp);
426 21 : gsi_insert_on_edge (e, ga3);
427 21 : gsi_insert_on_edge (e, ga4);
428 : }
429 : }
430 18 : }
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 489 : flush_on_gsi (gimple_stmt_iterator *gsi, size_t bucket, tree local, tree mask,
448 : tree atomic_ior, tree gcov_type_node)
449 : {
450 489 : tree relaxed = nullptr;
451 489 : if (atomic_ior)
452 86 : relaxed = build_int_cst (integer_type_node, MEMMODEL_RELAXED);
453 489 : tree global = tree_coverage_counter_ref (GCOV_COUNTER_PATHS, bucket);
454 :
455 489 : tree global_copy = make_ssa_name (gcov_type_node);
456 489 : gassign *ga1 = gimple_build_assign (global_copy, global);
457 489 : gsi_insert_before (gsi, ga1, GSI_SAME_STMT);
458 :
459 489 : tree masked;
460 489 : if (mask)
461 : {
462 479 : masked = make_ssa_name (gcov_type_node);
463 479 : gassign *ga2 = gimple_build_assign (masked, BIT_AND_EXPR, local, mask);
464 479 : gsi_insert_before (gsi, ga2, GSI_SAME_STMT);
465 : }
466 : else
467 : masked = local;
468 :
469 489 : if (atomic_ior)
470 : {
471 86 : global = unshare_expr (global);
472 86 : gcall *call = gimple_build_call (atomic_ior, 3, build_addr (global),
473 : masked, relaxed);
474 86 : gsi_insert_before (gsi, call, GSI_SAME_STMT);
475 : }
476 : else
477 : {
478 403 : tree tmp = make_ssa_name (gcov_type_node);
479 403 : gassign *ga3 = gimple_build_assign (tmp, BIT_IOR_EXPR, global_copy,
480 : masked);
481 403 : gassign *ga4 = gimple_build_assign (unshare_expr (global), tmp);
482 403 : gsi_insert_before (gsi, ga3, GSI_SAME_STMT);
483 403 : gsi_insert_before (gsi, ga4, GSI_SAME_STMT);
484 : }
485 489 : }
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 288 : instrument_prime_paths (struct function *fn)
509 : {
510 288 : mark_dfs_back_edges (fn);
511 288 : vec<vec<int>> paths = find_prime_paths (fn);
512 :
513 288 : 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 285 : tree gcov_type_node = get_gcov_type ();
522 285 : const size_t bucketsize = TYPE_PRECISION (gcov_type_node);
523 285 : const size_t nbuckets = (paths.length () + (bucketsize - 1)) / bucketsize;
524 285 : gcc_checking_assert (sizeof (uint64_t) * BITS_PER_UNIT >= bucketsize);
525 :
526 285 : if (!coverage_counter_alloc (GCOV_COUNTER_PATHS, nbuckets))
527 : {
528 0 : release_vec_vec (paths);
529 0 : return 0;
530 : }
531 :
532 285 : hash_map <edge_hash, uint64_t> ands;
533 285 : hash_map <block_hash, uint64_t> iors;
534 285 : 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 2192 : for (size_t pathno = 0; pathno != paths.length (); ++pathno)
540 : {
541 1907 : const vec<int> &path = paths[pathno];
542 1907 : const size_t bucket = pathno / bucketsize;
543 1907 : const uint64_t bit = uint64_t (1) << (pathno % bucketsize);
544 :
545 1907 : basic_block first = BASIC_BLOCK_FOR_FN (fn, path[0]);
546 1907 : basic_block last = BASIC_BLOCK_FOR_FN (fn, path[path.length () - 1]);
547 :
548 20828 : for (unsigned i = 1; i != path.length (); ++i)
549 : {
550 8507 : edge e = edge_between (fn, path[i-1], path[i]);
551 8507 : ands.get_or_insert ({e, bucket}) |= bit;
552 : }
553 :
554 1907 : iors.get_or_insert ({first, bucket}) |= bit;
555 1907 : 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 285 : 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 285 : 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 285 : hash_map<block_hash, tree> SSAen;
571 :
572 285 : auto_vec<fixup, 4> todos;
573 :
574 : /* Generate the operations for each basic block. */
575 2895 : for (basic_block bb : blocks)
576 : {
577 4808 : for (size_t bucket = 0; bucket != nbuckets; ++bucket)
578 : {
579 2768 : tree ssa = nullptr;
580 2768 : gphi *phi = nullptr;
581 2768 : uint64_t all_and = union_incoming_bit_and (ands, bb, bucket);
582 :
583 2768 : 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 1535 : tree *prev = SSAex.get ({single_pred (bb), bucket});
590 1535 : gcc_checking_assert (prev);
591 1535 : ssa = *prev;
592 : }
593 1233 : else if (all_and)
594 : {
595 : /* There are multiple predecessors, so we need a phi. */
596 251 : ssa = make_ssa_name (gcov_type_node);
597 251 : phi = create_phi_node (ssa, bb);
598 : }
599 :
600 2768 : if (ssa)
601 1786 : SSAen.put ({bb, bucket}, ssa);
602 :
603 2768 : 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 591 : 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 3167 : else for (edge e : bb->preds)
617 : {
618 2063 : 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 2063 : if (!bitmask && !phi)
623 160 : ssa = nullptr;
624 1903 : else if (!bitmask && phi)
625 : {
626 726 : tree zero = safe_insert_zero_phi_arg (e, gcov_type_node);
627 726 : add_phi_arg (phi, zero, e, UNKNOWN_LOCATION);
628 : }
629 1177 : 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 1177 : 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 1177 : 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 1114 : tree prev = *SSAex.get ({e->src, bucket});
651 1114 : gcc_assert (prev);
652 1114 : if (constant_p (prev))
653 : {
654 284 : const uint64_t x = tree_to_uhwi (prev);
655 284 : tree cst = build_int_cst (gcov_type_node, x & *bitmask);
656 284 : if (phi)
657 284 : add_phi_arg (phi, cst, e, UNKNOWN_LOCATION);
658 : else
659 0 : ssa = cst;
660 : }
661 : else
662 : {
663 830 : tree lhs = make_ssa_name (gcov_type_node);
664 830 : tree mask = build_int_cst (gcov_type_node, *bitmask);
665 830 : gassign *put = gimple_build_assign (lhs, BIT_AND_EXPR,
666 : prev, mask);
667 830 : gsi_insert_on_edge (e, put);
668 830 : if (phi)
669 830 : 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 63 : gcc_assert (phi);
680 63 : gcc_assert (e->flags & EDGE_DFS_BACK);
681 63 : fixup todo = fixup_and (phi, e, bucket, *bitmask,
682 : gcov_type_node);
683 63 : 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 2768 : const uint64_t *ior = iors.get ({bb, bucket});
692 2768 : 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 289 : ssa = build_int_cst (gcov_type_node, *ior);
699 289 : SSAen.put ({bb, bucket}, ssa);
700 : }
701 173 : else if (ior && all_bits_set_p (*ior, bucketsize))
702 0 : ssa = build_all_ones_cst (gcov_type_node);
703 2479 : else if (ior)
704 : {
705 173 : gcc_assert (ssa);
706 173 : tree mask = build_int_cst (gcov_type_node, *ior);
707 173 : ssa = safe_insert_ior (bb, ssa, mask, phi, gcov_type_node);
708 : }
709 :
710 2768 : if (ssa)
711 2075 : 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 918 : for (fixup &todo : todos)
719 : {
720 63 : tree *exit = SSAex.get ({todo.e->src, todo.bucket});
721 63 : gcc_assert (exit && *exit);
722 63 : gcc_checking_assert (todo.phi);
723 63 : if (todo.mask)
724 : {
725 63 : gassign *put = gimple_build_assign (todo.lhs, BIT_AND_EXPR, *exit,
726 : todo.mask);
727 63 : gsi_insert_on_edge (todo.e, put);
728 : }
729 :
730 63 : add_phi_arg (todo.phi, todo.lhs ? todo.lhs : *exit, todo.e,
731 : UNKNOWN_LOCATION);
732 : }
733 :
734 285 : tree atomic_ior = nullptr;
735 285 : 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 2610 : for (basic_block bb : blocks)
743 : {
744 2040 : gimple_stmt_iterator gsi = gsi_after_labels (bb);
745 4808 : for (size_t bucket = 0; bucket != nbuckets; ++bucket)
746 : {
747 2768 : const uint64_t *bitmask = flushes.get ({bb, bucket});
748 2768 : if (!bitmask || !*bitmask)
749 2261 : 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 18 : flush_on_edges (bb, bucket, *counter, mask, atomic_ior,
762 : gcov_type_node);
763 : else
764 489 : flush_on_gsi (&gsi, bucket, *counter, mask, atomic_ior,
765 : gcov_type_node);
766 : }
767 : }
768 :
769 285 : const unsigned npaths = paths.length ();
770 285 : blocks.release ();
771 285 : release_vec_vec (paths);
772 285 : return npaths;
773 285 : }
|
