This is an archive of the discontinued LLVM Phabricator instance.

[LCSSA] Skip blocks in sub-loops when scanning for uses.
ClosedPublic

Authored by fhahn on Jan 17 2019, 5:10 AM.

Details

Summary

Scanning blocks in sub-loops for uses is unnecessary, as they were
already handled while dealing with the containing sub-loop.

This speeds up LCSSA for highly nested loops. For the test case in PR37202, it
halves the time spent in LCSSA. In cases were we won't be able to skip
any blocks, the additional lookup should be negligible.

Time-passes without this patch for test case from PR37202:

Total Execution Time: 48.5505 seconds (48.5511 wall clock)

 ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
10.0822 ( 21.0%)   0.1406 ( 27.0%)  10.2228 ( 21.1%)  10.2228 ( 21.1%)  Loop-Closed SSA Form Pass
10.0417 ( 20.9%)   0.1467 ( 28.2%)  10.1884 ( 21.0%)  10.1890 ( 21.0%)  Loop-Closed SSA Form Pass #2
 4.2703 (  8.9%)   0.0040 (  0.8%)   4.2742 (  8.8%)   4.2742 (  8.8%)  Unswitch loops
 2.7376 (  5.7%)   0.0229 (  4.4%)   2.7605 (  5.7%)   2.7611 (  5.7%)  Loop-Closed SSA Form Pass #5
 2.7332 (  5.7%)   0.0214 (  4.1%)   2.7546 (  5.7%)   2.7546 (  5.7%)  Loop-Closed SSA Form Pass #3
 2.7088 (  5.6%)   0.0230 (  4.4%)   2.7319 (  5.6%)   2.7324 (  5.6%)  Loop-Closed SSA Form Pass #4
 2.6855 (  5.6%)   0.0236 (  4.5%)   2.7091 (  5.6%)   2.7090 (  5.6%)  Loop-Closed SSA Form Pass #6
 2.1648 (  4.5%)   0.0018 (  0.4%)   2.1666 (  4.5%)   2.1664 (  4.5%)  Unroll loops
 1.8371 (  3.8%)   0.0009 (  0.2%)   1.8379 (  3.8%)   1.8380 (  3.8%)  Value Propagation
 1.8149 (  3.8%)   0.0021 (  0.4%)   1.8170 (  3.7%)   1.8169 (  3.7%)  Loop Invariant Code Motion
 1.6755 (  3.5%)   0.0226 (  4.3%)   1.6981 (  3.5%)   1.6980 (  3.5%)  Loop-Closed SSA Form Pass #7

Time-passes with this patch

Total Execution Time: 29.9285 seconds (29.9276 wall clock)

 ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
 5.2786 ( 17.7%)   0.0021 (  1.2%)   5.2806 ( 17.6%)   5.2808 ( 17.6%)  Unswitch loops
 4.3739 ( 14.7%)   0.0303 ( 18.1%)   4.4042 ( 14.7%)   4.4042 ( 14.7%)  Loop-Closed SSA Form Pass
 4.2658 ( 14.3%)   0.0192 ( 11.5%)   4.2850 ( 14.3%)   4.2851 ( 14.3%)  Loop-Closed SSA Form Pass #2
 2.2307 (  7.5%)   0.0013 (  0.8%)   2.2320 (  7.5%)   2.2318 (  7.5%)  Loop Invariant Code Motion
 2.0888 (  7.0%)   0.0012 (  0.7%)   2.0900 (  7.0%)   2.0897 (  7.0%)  Unroll loops
 1.6761 (  5.6%)   0.0013 (  0.8%)   1.6774 (  5.6%)   1.6774 (  5.6%)  Value Propagation
 1.3686 (  4.6%)   0.0029 (  1.8%)   1.3716 (  4.6%)   1.3714 (  4.6%)  Induction Variable Simplification
 1.1457 (  3.8%)   0.0010 (  0.6%)   1.1468 (  3.8%)   1.1468 (  3.8%)  Loop-Closed SSA Form Pass #4
 1.1384 (  3.8%)   0.0005 (  0.3%)   1.1389 (  3.8%)   1.1389 (  3.8%)  Loop-Closed SSA Form Pass #6
 1.1360 (  3.8%)   0.0027 (  1.6%)   1.1387 (  3.8%)   1.1387 (  3.8%)  Loop-Closed SSA Form Pass #5
 1.1331 (  3.8%)   0.0010 (  0.6%)   1.1341 (  3.8%)   1.1340 (  3.8%)  Loop-Closed SSA Form Pass #3

Diff Detail

Repository
rL LLVM

Event Timeline

fhahn created this revision.Jan 17 2019, 5:10 AM
fhahn edited the summary of this revision. (Show Details)Jan 17 2019, 5:11 AM
efriedma added inline comments.Jan 17 2019, 12:39 PM
llvm/lib/Transforms/Utils/LCSSA.cpp
328 ↗(On Diff #182256)

The relevant property here is that the sub-loops are already in LCSSA form, right? The documentation for formLCSSA doesn't actually say that explicitly... granted, it's probably true in the cases we care about.

fhahn updated this revision to Diff 182381.Jan 17 2019, 1:02 PM
fhahn marked an inline comment as done.

state explicitly that sub-loops must be in LCSSA form already for formLCSSA()

fhahn added inline comments.Jan 17 2019, 1:05 PM
llvm/lib/Transforms/Utils/LCSSA.cpp
328 ↗(On Diff #182256)

That's a better way of putting it, yes! The formLCSSA uses in LCSSA.cpp guarantee that already and I checked the other 3 uses in LoopSimplify.cpp and SimpleLoopUnswitch.cpp and they either call formLCSSA depth first for their sub-loops or assert that the subloops are in LCSSA form.

This revision is now accepted and ready to land.Jan 17 2019, 1:17 PM
davide accepted this revision.Jan 17 2019, 5:13 PM

LGTM, just a minor comment (food for thought).

llvm/lib/Transforms/Utils/LCSSA.cpp
328 ↗(On Diff #182256)

This property of sub loops should always be true, maybe there's a way of verifying this?

fhahn marked an inline comment as done.Jan 18 2019, 9:39 AM
fhahn added inline comments.
llvm/lib/Transforms/Utils/LCSSA.cpp
328 ↗(On Diff #182256)

Yes, I think we can just check isRecursivelyLCSSAForm on all sub-loops. This is quite expensive, which is why I didn't put it in this patch. But I'll create a follow up, where it is under EXPENSIVE_CHECKS

This revision was automatically updated to reflect the committed changes.