[Bug debug/78288] Compile time hog (with var-tracking) for libsanitizer/asan/asan_interceptors.cc

[Bug debug/78288] Compile time hog (with var-tracking) for libsanitizer/asan/asan_interceptors.cc

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78288

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
As update with todays trunk 96b7f495f9269d5448822e4fc28882 I see for
not bootstrapped build of asan_interceptors.cc on x86_64 with -fno-checking:

 callgraph ipa passes               :   1.24 ( 11%)   0.11 ( 14%)   1.36 ( 11%)
 117240 kB ( 19%)
 integrated RA                      :   0.47 (  4%)   0.06 (  8%)   0.35 (  3%)
  48666 kB (  8%)
 variable tracking                  :   0.15 (  1%)   0.00 (  0%)   0.21 (  2%)
  14895 kB (  2%)
 var-tracking dataflow              :   1.64 ( 14%)   0.00 (  0%)   1.57 ( 13%)
    158 kB (  0%)
 var-tracking emit                  :   0.30 (  3%)   0.01 (  1%)   0.32 (  3%)
   9859 kB (  2%)
 TOTAL                              :  11.51          0.76         12.27       
 625036 kB

so this might not be the very best example for var-tracking slowness.  I
do have a simple patch that improves it to

 variable tracking                  :   0.21 (  2%)   0.00 (  0%)   0.22 (  2%)
  14895 kB (  2%)
 var-tracking dataflow              :   0.95 (  8%)   0.00 (  0%)   0.94 (  8%)
    157 kB (  0%)
 var-tracking emit                  :   0.31 (  3%)   0.00 (  0%)   0.37 (  3%)
   9859 kB (  2%)

though which is done by changing the vt_find_locations iteration scheme
from worklist/pending to immediately following backedges for cache locality
reasons and to avoid processing parts of the function we'd eventually have
to revisit anyway due to changed DF on the backedge destination.

diff --git a/gcc/var-tracking.c b/gcc/var-tracking.c
index 899a5c0290d..7929b0b39eb 100644
--- a/gcc/var-tracking.c
+++ b/gcc/var-tracking.c
@@ -7209,22 +7209,18 @@ vt_find_locations (void)
                      if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
                        continue;

-                     if (bitmap_bit_p (visited, e->dest->index))
-                       {
-                         if (!bitmap_bit_p (in_pending, e->dest->index))
-                           {
-                             /* Send E->DEST to next round.  */
-                             bitmap_set_bit (in_pending, e->dest->index);
-                             pending->insert (bb_order[e->dest->index],
-                                              e->dest);
-                           }
-                       }
-                     else if (!bitmap_bit_p (in_worklist, e->dest->index))
+                     if (!bitmap_bit_p (in_worklist, e->dest->index))
                        {
                          /* Add E->DEST to current round.  */
                          bitmap_set_bit (in_worklist, e->dest->index);
                          worklist->insert (bb_order[e->dest->index],
                                            e->dest);
+                         /* Clear visited in case we already visited
+                            the block.  We're following backedges
+                            immediately to improve cache locality
+                            and avoid wasting cycles on blocks we'd
+                            have to re-visit eventually.  */
+                         bitmap_clear_bit (visited, e->dest->index);
                        }
                    }
                }


all the worklist/fibheap/visited tracking could be also simplified down
to a single worklist bitmap (not sbitmap) indexed by bb_order and
extracting elements via bitmap_first_set_bit.  But that's of course
unrelated and not part of the performance issue (the visited bitmap
can be elimiated though).

It looks like this two-worklist approach is there from the very beginning,
also the use of a fibheap.

[Bug debug/78288] Compile time hog (with var-tracking) for libsanitizer/asan/asan_interceptors.cc

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78288

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 48848
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=48848&action=edit
patch

[Bug debug/78288] Compile time hog (with var-tracking) for libsanitizer/asan/asan_interceptors.cc

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78288

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #5)
> Created attachment 48848 [details]
> patch

statistics show it's not always a win for the overall number of processed
blocks.  stage3 of a GCC boostrap for gcc/ files shows (first number is
trunk, second is patched) counting the number of fibheap extracts:

a-conftest.c.324t.statistics 1 1
adjust-alignment.c.324t.statistics 48 47
alias.c.324t.statistics 3078 3340
alloc-pool.c.324t.statistics 46 43
asan.c.324t.statistics 3205 3022
attribs.c.324t.statistics 2093 2127
auto-inc-dec.c.324t.statistics 6 6
auto-profile.c.324t.statistics 2896 4546
bb-reorder.c.324t.statistics 3806 5965
bitmap.c.324t.statistics 2303 2276
builtins.c.324t.statistics 7263 7097
caller-save.c.324t.statistics 1076 1459
calls.c.324t.statistics 4959 6321
cc1-checksum.c.324t.statistics
cc1plus-checksum.c.324t.statistics
ccmp.c.324t.statistics 195 195
cet.c.324t.statistics 8 8
cfg.c.324t.statistics 1329 1276
cfganal.c.324t.statistics 2021 2154
cfgbuild.c.324t.statistics 880 1076
cfgcleanup.c.324t.statistics 3545 5586
cfgexpand.c.324t.statistics 8038 8337
cfghooks.c.324t.statistics 1425 1521
cfgloop.c.324t.statistics 2963 3300
cfgloopanal.c.324t.statistics 644 792
cfgloopmanip.c.324t.statistics 1961 2042
cfgrtl.c.324t.statistics 4604 5242
cgraph.c.324t.statistics 4489 4232
cgraphbuild.c.324t.statistics 377 398
cgraphclones.c.324t.statistics 1205 1173
cgraphunit.c.324t.statistics 2943 3768
collect-utils.c.324t.statistics 59 58
collect2-aix.c.324t.statistics 1 1
collect2.c.324t.statistics 766 867
combine-stack-adj.c.324t.statistics 519 760
combine.c.324t.statistics 8697 9667
compare-elim.c.324t.statistics 600 652
context.c.324t.statistics 6 6
convert.c.324t.statistics 1135 1135
coroutine-passes.cc.324t.statistics 780 908
coverage.c.324t.statistics 1328 1458
cppbuiltin.c.324t.statistics 62 62
cppdefault.c.324t.statistics 7 7
cprop.c.324t.statistics 1165 1903
cse.c.324t.statistics 5849 7881
cselib.c.324t.statistics 3037 2982
data-streamer-in.c.324t.statistics 72 63
data-streamer-out.c.324t.statistics 263 238
data-streamer.c.324t.statistics 65 71
dbgcnt.c.324t.statistics 250 320
dbxout.c.324t.statistics 2832 2652
dce.c.324t.statistics 1356 1530
ddg.c.324t.statistics 1047 1708
debug.c.324t.statistics 16 16
df-core.c.324t.statistics 1412 1534
df-problems.c.324t.statistics 3574 4339
df-scan.c.324t.statistics 3223 3431
dfp.c.324t.statistics 106 106
diagnostic-color.c.324t.statistics 120 121
diagnostic-format-json.cc.324t.statistics 93 91
diagnostic-show-locus.c.324t.statistics 1787 1759
diagnostic.c.324t.statistics 718 698
digraph.cc.324t.statistics 576 560
dojump.c.324t.statistics 1253 1144
dominance.c.324t.statistics 1447 1651
domwalk.c.324t.statistics 288 310
double-int.c.324t.statistics 535 476
driver-i386.c.324t.statistics 574 670
dse.c.324t.statistics 2719 3515
dumpfile.c.324t.statistics 1677 1693
dwarf2asm.c.324t.statistics 580 550
dwarf2cfi.c.324t.statistics 2264 2404
dwarf2out.c.324t.statistics 32574 32617
early-remat.c.324t.statistics 2373 3489
edit-context.c.324t.statistics 960 959
emit-rtl.c.324t.statistics 5075 5084
errors.c.324t.statistics 49 44
et-forest.c.324t.statistics 614 514
except.c.324t.statistics 2857 2752
explow.c.324t.statistics 778 758
expmed.c.324t.statistics 2692 2501
expr.c.324t.statistics 9552 9399
fibonacci_heap.c.324t.statistics 806 742
file-find.c.324t.statistics 75 73
file-prefix-map.c.324t.statistics 19 17
final.c.324t.statistics 2692 2895
fixed-value.c.324t.statistics 357 351
fold-const-call.c.324t.statistics 900 891
fold-const.c.324t.statistics 13221 12822
function-abi.cc.324t.statistics 202 272
function-tests.c.324t.statistics 324 324
function.c.324t.statistics 5441 5523
fwprop.c.324t.statistics 1057 1044
gcc-ar.c.324t.statistics 56 55
gcc-main.c.324t.statistics 2 2
gcc-nm.c.324t.statistics 53 52
gcc-ranlib.c.324t.statistics 53 52
gcc-rich-location.c.324t.statistics 77 73
gcc.c.324t.statistics 5953 6594
gcov-dump.c.324t.statistics 453 526
gcov-tool.c.324t.statistics 198 261
gcov.c.324t.statistics 3554 4749
gcse-common.c.324t.statistics 239 391
gcse.c.324t.statistics 2284 3321
generic-match.c.324t.statistics 47432 46970
gengtype-lex.c.324t.statistics 524 760
gengtype-parse.c.324t.statistics 597 672
gengtype-state.c.324t.statistics 2120 2317
gengtype.c.324t.statistics 2897 3544
ggc-common.c.324t.statistics 922 867
ggc-none.c.324t.statistics 11 11
ggc-page.c.324t.statistics 965 963
ggc-tests.c.324t.statistics 556 570
gimple-array-bounds.cc.324t.statistics 775 641
gimple-builder.c.324t.statistics 55 55
gimple-expr.c.324t.statistics 1067 938
gimple-fold.c.324t.statistics 6076 6045
gimple-isel.cc.324t.statistics 420 405
gimple-iterator.c.324t.statistics 447 427
gimple-laddress.c.324t.statistics 82 111
gimple-loop-interchange.cc.324t.statistics 2657 3525
gimple-loop-jam.c.324t.statistics 511 770
gimple-loop-versioning.cc.324t.statistics 1808 2744
gimple-low.c.324t.statistics 732 678
gimple-match.c.324t.statistics 79313 78121
gimple-pretty-print.c.324t.statistics 2177 2165
gimple-ssa-backprop.c.324t.statistics 916 890
gimple-ssa-evrp-analyze.c.324t.statistics 614 640
gimple-ssa-evrp.c.324t.statistics 45 45
...
web.c.324t.statistics 438 679
wide-int-print.cc.324t.statistics 83 81
wide-int.cc.324t.statistics 1914 1816
x86-tune-sched-atom.c.324t.statistics 185 265
x86-tune-sched-bd.c.324t.statistics 208 217
x86-tune-sched-core.c.324t.statistics 79 84
x86-tune-sched.c.324t.statistics 235 220
xcoffout.c.324t.statistics 1 1

and overall it's a loss as well with previously 1190266 visits and patched
1314850.

I would expect that for nested CFG cycles only immediately iterating the
outermost one should be always profitable, and if we processed all
backedge predecessors and the dataflow was unchanged on them, backtrack
to the earliest inner cycle that needs re-processing.

So consider the patch withdrawn in its current form.

But as can be seen there's sth to gain from looking at the iteration scheme.

Inventing some reasonable behavior for unvisited backedges and thus doing
a non-iterative scheme for large routines might also be sth to investigate.
I've noticed the odd intesection vs. unioning of the IN dataflow solutions
keyed on MAY_HAVE_DEBUG_BIND_INSNS but maybe it's just a documentation wart.

[Bug debug/78288] Compile time hog (with var-tracking) for libsanitizer/asan/asan_interceptors.cc

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78288

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 48869
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=48869&action=edit
alternate patch

OK, I have another patch that reduces the overall number of visited blocks
in stage3 gcc/*.o by about 10%.  There are a few outliers that I need to
understand (because it should never(?) cause more blocks to be iterated).
Famous last words...

[Bug debug/78288] Compile time hog (with var-tracking) for libsanitizer/asan/asan_interceptors.cc

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78288

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
files with growth:

obj/gcc/calls.c.325t.statistics:320 4958                      | 5571
obj/gcc/prefix.c.325t.statistics:320 115                      | 118

yes, that's all of them.

[Bug debug/78288] Compile time hog (with var-tracking) for libsanitizer/asan/asan_interceptors.cc

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78288

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #48869|0                           |1
        is obsolete|                            |

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 48873
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=48873&action=edit
updated alternate patch

(In reply to Richard Biener from comment #8)
> files with growth:
> 
> obj/gcc/calls.c.325t.statistics:320 4958                      | 5571
> obj/gcc/prefix.c.325t.statistics:320 115                      | 118
> 
> yes, that's all of them.

The prefix.c one is a two-BB natural loop inside an irreducible region.  Since
we do not represent irreducible regions in the loop tree it is falsely
classified as being independent so the scheduling change could make things
worse here.  Not regressing could be easily achieved by keying the thing on no
BB_IRREDUCIBLE_LOOP block in the function but then we need to compute that.
That said, the patch logic assumes that there's no natural loop inside an
irreducible region at outermost loop level.

mark_irreducible_loops uses graphds_scc which in the end would be all we
need (sorting RPO after the SCC component number).

Updated patch taking into account optimized iteration between two outermost
loops w/o a block in the root loop.

[Bug debug/78288] Compile time hog (with var-tracking) for libsanitizer/asan/asan_interceptors.cc

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78288

--- Comment #10 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Richard Biener <rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:1212cfad09378bc85860a7de22dde0cf7a19fd01

commit r11-2447-g1212cfad09378bc85860a7de22dde0cf7a19fd01
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Jul 24 13:44:09 2020 +0200

    Improve var-tracking dataflow iteration order

    This builds upon the rev_post_order_and_mark_dfs_back_seme improvements
    and makes vt_find_locations iterate over the dataflow problems for
    each toplevel SCC separately, improving memory locality and avoiding
    to process nodes after the SCC before the SCC itself stabilized.

    On the asan_interceptors.cc testcase this for example reduces the
    number of visited blocks from 3751 to 2867.  For stage3-gcc
    this reduces the number of visited blocks by ~4%.

    2020-07-28  Richard Biener  <rguenther@suse.de>

            PR debug/78288
            * var-tracking.c (vt_find_locations): Use
            rev_post_order_and_mark_dfs_back_seme and separately iterate
            over toplevel SCCs.

[Bug debug/78288] Compile time hog (with var-tracking) for libsanitizer/asan/asan_interceptors.cc

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78288

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
So var-tracking should be down (still slow) on this testcase now.