[JumpThreading] use UnreachableBlocks to avoid unreachable regions

[brzycki]

Summary

It is possible to cause hangs in JumpThreading due to how the pass decides there is no more work to be done. An older attempt at fixing this problem was D3991 where removeUnreachableBlocks(F) is now called on the function before any JumpThreading is attempted. This has a few drawbacks though:

• It's an expensive transformation.
• It is a coarse tool: it does not comprehend or care about preserving Loops.
• It actually has nothing to do with the JumpThreading pass.
• It does more than just remove unrechable blocks, it changes reachable blocks too, especially Terminator Instructions.

This patch foregoes calling removeUnreachableBlocks and uses a SmallPtrSet using the initial DominatorTree to track unreachable blocks.

[brzycki]

Here are 4 ctmark runs on x86_64 of compile_time results. The tip compiler is llvm-project SHA 7a365bd12dd84be1e7c9ca6d9a2268b80f604ae9. The upstream compiler is the same as tip with this patch applied.

# tip (left), upstream (right)
#  left column: build.tip_ctmark_1/results.json
# right column: build.upstream_ctmark_1/results.json
#  metric name: compile_time
    378.3760 -> 346.6120     [  9.16%]  CTMark/sqlite3/sqlite3.test
    499.5760 -> 492.7440     [  1.39%]  CTMark/tramp3d-v4/tramp3d-v4.test
    390.3720 -> 386.4720     [  1.01%]  CTMark/kimwitu++/kc.test
    503.2800 -> 499.5320     [  0.75%]  CTMark/ClamAV/clamscan.test
    253.5440 <- 255.4160     [  0.74%]  CTMark/mafft/pairlocalalign.test
   1272.1440 <- 1279.2400    [  0.56%]  CTMark/7zip/7zip-benchmark.test
    463.2200 -> 461.1600     [  0.45%]  CTMark/SPASS/SPASS.test
    595.7480 <- 597.0600     [  0.22%]  CTMark/lencod/lencod.test
    928.3480 -> 927.5960     [  0.08%]  CTMark/Bullet/bullet.test
    370.5800 -> 370.5160     [  0.02%]  CTMark/consumer-typeset/consumer-typeset.test
#  left column: build.tip_ctmark_1/results.json
# right column: build.upstream_ctmark_2/results.json
#  metric name: compile_time
    499.5760 -> 487.3400     [  2.51%]  CTMark/tramp3d-v4/tramp3d-v4.test
    378.3760 -> 372.8840     [  1.47%]  CTMark/sqlite3/sqlite3.test
    253.5440 -> 250.2840     [  1.30%]  CTMark/mafft/pairlocalalign.test
    390.3720 -> 387.8960     [  0.64%]  CTMark/kimwitu++/kc.test
    595.7480 -> 592.4760     [  0.55%]  CTMark/lencod/lencod.test
    928.3480 <- 931.6960     [  0.36%]  CTMark/Bullet/bullet.test
    370.5800 <- 371.3080     [  0.20%]  CTMark/consumer-typeset/consumer-typeset.test
    503.2800 -> 502.3880     [  0.18%]  CTMark/ClamAV/clamscan.test
   1272.1440 <- 1273.3800    [  0.10%]  CTMark/7zip/7zip-benchmark.test
    463.2200 -> 462.7920     [  0.09%]  CTMark/SPASS/SPASS.test
#  left column: build.tip_ctmark_1/results.json
# right column: build.upstream_ctmark_3/results.json
#  metric name: compile_time
    253.5440 <- 256.0280     [  0.98%]  CTMark/mafft/pairlocalalign.test
    595.7480 -> 591.4720     [  0.72%]  CTMark/lencod/lencod.test
    390.3720 <- 392.2520     [  0.48%]  CTMark/kimwitu++/kc.test
    463.2200 -> 461.2000     [  0.44%]  CTMark/SPASS/SPASS.test
   1272.1440 <- 1275.2320    [  0.24%]  CTMark/7zip/7zip-benchmark.test
    503.2800 -> 502.0800     [  0.24%]  CTMark/ClamAV/clamscan.test
    928.3480 -> 927.0640     [  0.14%]  CTMark/Bullet/bullet.test
    370.5800 <- 371.0080     [  0.12%]  CTMark/consumer-typeset/consumer-typeset.test
    499.5760 -> 499.0160     [  0.11%]  CTMark/tramp3d-v4/tramp3d-v4.test
    378.3760 -> 378.0360     [  0.09%]  CTMark/sqlite3/sqlite3.test
#  left column: build.tip_ctmark_1/results.json
# right column: build.upstream_ctmark_4/results.json
#  metric name: compile_time
    499.5760 <- 541.9040     [  8.47%]  CTMark/tramp3d-v4/tramp3d-v4.test
    378.3760 -> 350.2080     [  8.04%]  CTMark/sqlite3/sqlite3.test
    253.5440 <- 257.6560     [  1.62%]  CTMark/mafft/pairlocalalign.test
    370.5800 -> 365.7360     [  1.32%]  CTMark/consumer-typeset/consumer-typeset.test
    595.7480 -> 590.7960     [  0.84%]  CTMark/lencod/lencod.test
    390.3720 <- 392.9920     [  0.67%]  CTMark/kimwitu++/kc.test
    463.2200 -> 461.2760     [  0.42%]  CTMark/SPASS/SPASS.test
    503.2800 -> 502.0880     [  0.24%]  CTMark/ClamAV/clamscan.test
    928.3480 <- 929.7520     [  0.15%]  CTMark/Bullet/bullet.test
   1272.1440 <- 1273.3720    [  0.10%]  CTMark/7zip/7zip-benchmark.test
#  left column: build.tip_ctmark_2/results.json
# right column: build.upstream_ctmark_1/results.json
#  metric name: compile_time
    587.0520 <- 597.0600     [  1.70%]  CTMark/lencod/lencod.test
    466.3600 -> 461.1600     [  1.13%]  CTMark/SPASS/SPASS.test
    257.6840 -> 255.4160     [  0.89%]  CTMark/mafft/pairlocalalign.test
    496.7760 -> 492.7440     [  0.82%]  CTMark/tramp3d-v4/tramp3d-v4.test
    343.8520 <- 346.6120     [  0.80%]  CTMark/sqlite3/sqlite3.test
    502.8960 -> 499.5320     [  0.67%]  CTMark/ClamAV/clamscan.test
   1275.4080 <- 1279.2400    [  0.30%]  CTMark/7zip/7zip-benchmark.test
    930.1400 -> 927.5960     [  0.27%]  CTMark/Bullet/bullet.test
    369.5240 <- 370.5160     [  0.27%]  CTMark/consumer-typeset/consumer-typeset.test
    387.4960 -> 386.4720     [  0.26%]  CTMark/kimwitu++/kc.test
#  left column: build.tip_ctmark_2/results.json
# right column: build.upstream_ctmark_2/results.json
#  metric name: compile_time
    343.8520 <- 372.8840     [  8.44%]  CTMark/sqlite3/sqlite3.test
    257.6840 -> 250.2840     [  2.96%]  CTMark/mafft/pairlocalalign.test
    496.7760 -> 487.3400     [  1.94%]  CTMark/tramp3d-v4/tramp3d-v4.test
    587.0520 <- 592.4760     [  0.92%]  CTMark/lencod/lencod.test
    466.3600 -> 462.7920     [  0.77%]  CTMark/SPASS/SPASS.test
    369.5240 <- 371.3080     [  0.48%]  CTMark/consumer-typeset/consumer-typeset.test
    930.1400 <- 931.6960     [  0.17%]  CTMark/Bullet/bullet.test
   1275.4080 -> 1273.3800    [  0.16%]  CTMark/7zip/7zip-benchmark.test
    387.4960 <- 387.8960     [  0.10%]  CTMark/kimwitu++/kc.test
    502.8960 -> 502.3880     [  0.10%]  CTMark/ClamAV/clamscan.test
#  left column: build.tip_ctmark_2/results.json
# right column: build.upstream_ctmark_3/results.json
#  metric name: compile_time
    343.8520 <- 378.0360     [  9.94%]  CTMark/sqlite3/sqlite3.test
    387.4960 <- 392.2520     [  1.23%]  CTMark/kimwitu++/kc.test
    466.3600 -> 461.2000     [  1.12%]  CTMark/SPASS/SPASS.test
    587.0520 <- 591.4720     [  0.75%]  CTMark/lencod/lencod.test
    257.6840 -> 256.0280     [  0.65%]  CTMark/mafft/pairlocalalign.test
    496.7760 <- 499.0160     [  0.45%]  CTMark/tramp3d-v4/tramp3d-v4.test
    369.5240 <- 371.0080     [  0.40%]  CTMark/consumer-typeset/consumer-typeset.test
    930.1400 -> 927.0640     [  0.33%]  CTMark/Bullet/bullet.test
    502.8960 -> 502.0800     [  0.16%]  CTMark/ClamAV/clamscan.test
   1275.4080 -> 1275.2320    [  0.01%]  CTMark/7zip/7zip-benchmark.test
#  left column: build.tip_ctmark_2/results.json
# right column: build.upstream_ctmark_4/results.json
#  metric name: compile_time
    496.7760 <- 541.9040     [  9.08%]  CTMark/tramp3d-v4/tramp3d-v4.test
    343.8520 <- 350.2080     [  1.85%]  CTMark/sqlite3/sqlite3.test
    387.4960 <- 392.9920     [  1.42%]  CTMark/kimwitu++/kc.test
    466.3600 -> 461.2760     [  1.10%]  CTMark/SPASS/SPASS.test
    369.5240 -> 365.7360     [  1.04%]  CTMark/consumer-typeset/consumer-typeset.test
    587.0520 <- 590.7960     [  0.64%]  CTMark/lencod/lencod.test
    502.8960 -> 502.0880     [  0.16%]  CTMark/ClamAV/clamscan.test
   1275.4080 -> 1273.3720    [  0.16%]  CTMark/7zip/7zip-benchmark.test
    930.1400 -> 929.7520     [  0.04%]  CTMark/Bullet/bullet.test
    257.6840 -> 257.6560     [  0.01%]  CTMark/mafft/pairlocalalign.test
#  left column: build.tip_ctmark_3/results.json
# right column: build.upstream_ctmark_1/results.json
#  metric name: compile_time
    540.9680 -> 492.7440     [  9.79%]  CTMark/tramp3d-v4/tramp3d-v4.test
    357.0480 -> 346.6120     [  3.01%]  CTMark/sqlite3/sqlite3.test
    589.7160 <- 597.0600     [  1.25%]  CTMark/lencod/lencod.test
    366.6280 <- 370.5160     [  1.06%]  CTMark/consumer-typeset/consumer-typeset.test
    257.4080 -> 255.4160     [  0.78%]  CTMark/mafft/pairlocalalign.test
    502.8920 -> 499.5320     [  0.67%]  CTMark/ClamAV/clamscan.test
    388.6480 -> 386.4720     [  0.56%]  CTMark/kimwitu++/kc.test
    930.4400 -> 927.5960     [  0.31%]  CTMark/Bullet/bullet.test
   1277.1600 <- 1279.2400    [  0.16%]  CTMark/7zip/7zip-benchmark.test
    460.5200 <- 461.1600     [  0.14%]  CTMark/SPASS/SPASS.test
#  left column: build.tip_ctmark_3/results.json
# right column: build.upstream_ctmark_2/results.json
#  metric name: compile_time
    540.9680 -> 487.3400     [ 11.00%]  CTMark/tramp3d-v4/tramp3d-v4.test
    357.0480 <- 372.8840     [  4.44%]  CTMark/sqlite3/sqlite3.test
    257.4080 -> 250.2840     [  2.85%]  CTMark/mafft/pairlocalalign.test
    366.6280 <- 371.3080     [  1.28%]  CTMark/consumer-typeset/consumer-typeset.test
    460.5200 <- 462.7920     [  0.49%]  CTMark/SPASS/SPASS.test
    589.7160 <- 592.4760     [  0.47%]  CTMark/lencod/lencod.test
   1277.1600 -> 1273.3800    [  0.30%]  CTMark/7zip/7zip-benchmark.test
    388.6480 -> 387.8960     [  0.19%]  CTMark/kimwitu++/kc.test
    930.4400 <- 931.6960     [  0.13%]  CTMark/Bullet/bullet.test
    502.8920 -> 502.3880     [  0.10%]  CTMark/ClamAV/clamscan.test
#  left column: build.tip_ctmark_3/results.json
# right column: build.upstream_ctmark_3/results.json
#  metric name: compile_time
    540.9680 -> 499.0160     [  8.41%]  CTMark/tramp3d-v4/tramp3d-v4.test
    357.0480 <- 378.0360     [  5.88%]  CTMark/sqlite3/sqlite3.test
    366.6280 <- 371.0080     [  1.19%]  CTMark/consumer-typeset/consumer-typeset.test
    388.6480 <- 392.2520     [  0.93%]  CTMark/kimwitu++/kc.test
    257.4080 -> 256.0280     [  0.54%]  CTMark/mafft/pairlocalalign.test
    930.4400 -> 927.0640     [  0.36%]  CTMark/Bullet/bullet.test
    589.7160 <- 591.4720     [  0.30%]  CTMark/lencod/lencod.test
    502.8920 -> 502.0800     [  0.16%]  CTMark/ClamAV/clamscan.test
   1277.1600 -> 1275.2320    [  0.15%]  CTMark/7zip/7zip-benchmark.test
    460.5200 <- 461.2000     [  0.15%]  CTMark/SPASS/SPASS.test
#  left column: build.tip_ctmark_3/results.json
# right column: build.upstream_ctmark_4/results.json
#  metric name: compile_time
    357.0480 -> 350.2080     [  1.95%]  CTMark/sqlite3/sqlite3.test
    388.6480 <- 392.9920     [  1.12%]  CTMark/kimwitu++/kc.test
   1277.1600 -> 1273.3720    [  0.30%]  CTMark/7zip/7zip-benchmark.test
    366.6280 -> 365.7360     [  0.24%]  CTMark/consumer-typeset/consumer-typeset.test
    589.7160 <- 590.7960     [  0.18%]  CTMark/lencod/lencod.test
    540.9680 <- 541.9040     [  0.17%]  CTMark/tramp3d-v4/tramp3d-v4.test
    460.5200 <- 461.2760     [  0.16%]  CTMark/SPASS/SPASS.test
    502.8920 -> 502.0880     [  0.16%]  CTMark/ClamAV/clamscan.test
    257.4080 <- 257.6560     [  0.10%]  CTMark/mafft/pairlocalalign.test
    930.4400 -> 929.7520     [  0.07%]  CTMark/Bullet/bullet.test
#  left column: build.tip_ctmark_4/results.json
# right column: build.upstream_ctmark_1/results.json
#  metric name: compile_time
    351.1320 -> 346.6120     [  1.30%]  CTMark/sqlite3/sqlite3.test
    486.5040 <- 492.7440     [  1.28%]  CTMark/tramp3d-v4/tramp3d-v4.test
    253.6800 <- 255.4160     [  0.68%]  CTMark/mafft/pairlocalalign.test
    464.2840 -> 461.1600     [  0.68%]  CTMark/SPASS/SPASS.test
   1275.1200 <- 1279.2400    [  0.32%]  CTMark/7zip/7zip-benchmark.test
    595.3080 <- 597.0600     [  0.29%]  CTMark/lencod/lencod.test
    387.2880 -> 386.4720     [  0.21%]  CTMark/kimwitu++/kc.test
    500.5120 -> 499.5320     [  0.20%]  CTMark/ClamAV/clamscan.test
    369.8800 <- 370.5160     [  0.17%]  CTMark/consumer-typeset/consumer-typeset.test
    926.4040 <- 927.5960     [  0.13%]  CTMark/Bullet/bullet.test
#  left column: build.tip_ctmark_4/results.json
# right column: build.upstream_ctmark_2/results.json
#  metric name: compile_time
    351.1320 <- 372.8840     [  6.19%]  CTMark/sqlite3/sqlite3.test
    253.6800 -> 250.2840     [  1.36%]  CTMark/mafft/pairlocalalign.test
    926.4040 <- 931.6960     [  0.57%]  CTMark/Bullet/bullet.test
    595.3080 -> 592.4760     [  0.48%]  CTMark/lencod/lencod.test
    369.8800 <- 371.3080     [  0.39%]  CTMark/consumer-typeset/consumer-typeset.test
    500.5120 <- 502.3880     [  0.37%]  CTMark/ClamAV/clamscan.test
    464.2840 -> 462.7920     [  0.32%]  CTMark/SPASS/SPASS.test
    486.5040 <- 487.3400     [  0.17%]  CTMark/tramp3d-v4/tramp3d-v4.test
    387.2880 <- 387.8960     [  0.16%]  CTMark/kimwitu++/kc.test
   1275.1200 -> 1273.3800    [  0.14%]  CTMark/7zip/7zip-benchmark.test
#  left column: build.tip_ctmark_4/results.json
# right column: build.upstream_ctmark_3/results.json
#  metric name: compile_time
    351.1320 <- 378.0360     [  7.66%]  CTMark/sqlite3/sqlite3.test
    486.5040 <- 499.0160     [  2.57%]  CTMark/tramp3d-v4/tramp3d-v4.test
    387.2880 <- 392.2520     [  1.28%]  CTMark/kimwitu++/kc.test
    253.6800 <- 256.0280     [  0.93%]  CTMark/mafft/pairlocalalign.test
    464.2840 -> 461.2000     [  0.67%]  CTMark/SPASS/SPASS.test
    595.3080 -> 591.4720     [  0.65%]  CTMark/lencod/lencod.test
    500.5120 <- 502.0800     [  0.31%]  CTMark/ClamAV/clamscan.test
    369.8800 <- 371.0080     [  0.30%]  CTMark/consumer-typeset/consumer-typeset.test
    926.4040 <- 927.0640     [  0.07%]  CTMark/Bullet/bullet.test
   1275.1200 <- 1275.2320    [  0.01%]  CTMark/7zip/7zip-benchmark.test
#  left column: build.tip_ctmark_4/results.json
# right column: build.upstream_ctmark_4/results.json
#  metric name: compile_time
    486.5040 <- 541.9040     [ 11.39%]  CTMark/tramp3d-v4/tramp3d-v4.test
    253.6800 <- 257.6560     [  1.57%]  CTMark/mafft/pairlocalalign.test
    387.2880 <- 392.9920     [  1.47%]  CTMark/kimwitu++/kc.test
    369.8800 -> 365.7360     [  1.13%]  CTMark/consumer-typeset/consumer-typeset.test
    595.3080 -> 590.7960     [  0.76%]  CTMark/lencod/lencod.test
    464.2840 -> 461.2760     [  0.65%]  CTMark/SPASS/SPASS.test
    926.4040 <- 929.7520     [  0.36%]  CTMark/Bullet/bullet.test
    500.5120 <- 502.0880     [  0.31%]  CTMark/ClamAV/clamscan.test
    351.1320 -> 350.2080     [  0.26%]  CTMark/sqlite3/sqlite3.test
   1275.1200 -> 1273.3720    [  0.14%]  CTMark/7zip/7zip-benchmark.test

[sebpop]

LGTM.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

366

I would have called this bitmap UnreachableBlocks.

[brzycki]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

366

Good point, renaming.

[brzycki]

Renamed InvalidBlocks to UnreachableBlocks, minor tweaks to comments.

[kuhar]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

362

I can see that UnreachableBlocks are being cleared every time at the beginning and at the end. Can it be a local function variable instead, or am I missing something?

371

I'd put it on a separate line, one uninitialized value looks a bit suspicious.

373–374

Can this be rewritten to a range-based for loop?

379–382

Can you add a comment on why the entry block is skipped? I guess this is because the latter code tries to delete block with no predecessor as it figures they are unreachable, but that's not the case for the function entry?

396–399

I think the type is obvious here: auto *BI = ...

[brzycki]

Hi @kuhar , thanks for the review. As a general comment I tried to minimize changes to JumpThreading to remove removeUnreachableBlocks.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

362

I added UnreachableBlocks to JumpThreading.h because I used the LoopHeaders code as my model. Originally I was tracking ValidBlocks but that became memory and performance prohibitive. I can try UnreachableBlocks as a local variable although I'm not quite sure what the LLVM style guide is for defining a local variable differently based on NDEBUG.

Either way this UnreachableBlocks.clear() should be removed.

371

Will do. Changed is set 2 lines later but I don't mind either way.

373–374

Possibly. I left it as it was to minimize disruptions. I wasn't certain if this form handles deleted elements better than for (auto &BB : F) does. I can give it a try and see if all tests pass.

379–382

It's the same code as before. If you look at the original JumpThreading loop both of the subsequent cleanups (DeleteDeadBlock and TryToSimplifyUncondBranchFromEmptyBlock) guarded against touching the entry. This is because both of these delete BB block from`F`. Whether or not this is pessimizing potential JumpThreads is uncertain. I can certainly add a comment.

396–399

Will do.

[kuhar]

Thanks for clarifying. It would be definitely nice to see some cleanup, but I'll be fine with this happening in a follow-up patch if that makes testing easier.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

362

I think that having a different field types depending on build type is is much more problematic than having local variables of different types. This is because in the former case you may expose different ABI based on build type, while having local variables of different types is not something others can depend on.

[brzycki]

@kuhar I attempted to use a ranged iterator for (auto &BB : F) loop and it causes crashes in test-suite.

FAILED: Bitcode/Benchmarks/Halide/bilateral_grid/CMakeFiles/halide_bilateral_grid.dir/driver.cpp.o
/work/brzycki/test-suite/build/tools/timeit --summary Bitcode/Benchmarks/Halide/bilateral_grid/CMakeFiles/halide_bilateral_grid.dir/driver.cpp.o.time /work/brzycki/upstream/install/bin/clang++  -DNDEBUG -I../Bitcode/Benchmarks/Halide/bilateral_grid -IBitcode/Benchmarks/Halide/bilateral_grid -O3   -O3 -DNDEBUG   -w -Werror=date-time -std=c++11 -MD -MT Bitcode/Benchmarks/Halide/bilateral_grid/CMakeFiles/halide_bilateral_grid.dir/driver.cpp.o -MF Bitcode/Benchmarks/Halide/bilateral_grid/CMakeFiles/halide_bilateral_grid.dir/driver.cpp.o.d -o Bitcode/Benchmarks/Halide/bilateral_grid/CMakeFiles/halide_bilateral_grid.dir/driver.cpp.o -c ../Bitcode/Benchmarks/Halide/bilateral_grid/driver.cpp
While deleting: label %lpad142

I'm going to revert to the original loop structure.

[brzycki]

Addressed @kuhar 's comments.

@kuhar , I was incorrect about the for (auto &BB : F) causing crashes. It was actually the ifdef NDEBUG when I moved it into JumpThreading.cpp. I opted to not add an NDEBUG stanza and just use SmallPtrSet. There are several other instances of local pointer sets within JumpThreading that do the same.

[brzycki]

Ping. @sebpop, @kuhar, or @dberlin any objections to pushing this patch as-is?

[kuhar]

LGTM. Thanks for the fixes

[sebpop]

LGTM. Thanks!

[brzycki]

Thanks guys. I found a few spelling mistakes in the comments that I'm fixing and testing now. I'll upload the diff and push the change shortly if all goes well.

[brzycki]

Comment cleanup and rebase. NFC.

[efriedma]

It looks like in general, the union of the the Unreachable set and DeletedBBs does not contain all unreachable blocks; the Unreachable set never gets updated, and DeletedBBs only contains blocks which trivially have no predecessors. Could this lead to problems when jump threading erases an edge?

[brzycki]

In D44177#1040497, @efriedma wrote:

Could this lead to problems when jump threading erases an edge?

Hi @efriedma , it is possible there are still problems inside JumpThreading related to unreachable block chains. However, this patch wouldn't make that problem any better (or worse) than how JumpThreading was before. Here's the high-level algorithm of JumpThreading before this change:

removeUnreachableBlocks(F);
while Changed:
  for BB in F:
    ProcessBlock(BB);  // Can modify Changed
    // Try to delete BB (can modify Changed)
    // Try to merge BB with its successor (can modify Changed)

Previously removeUnreachableBlocks(F) removed unreachable blocks (and altered the reachable blocks) before starting its main while Changed loop. There are several places in JumpThreading where blocks were deleted or altered that didn't necessarily lead to threadable edges: DeleteDeadBlock, TryToSimplifyUncondBranchFromEmptyBlock, MergeBasicBlockIntoOnlyPred, and ConstantFoldTerminator. Any one of these calls could lead to unreachable regions being generated and they weren't being tracked before.

This patch works almost identical to the old algorithm:

// Generate Unreachable Blocks Set
while Changed:
  if BB in Unreachable:
    continue;
  for BB in F:
    ProcessBlock(BB);  // Can modify Changed
    // Try to delete BB (can modify Changed)
    // Try to merge BB with its successor (can modify Changed)

The big difference here is instead of actually removing the blocks we simply ignore them. But in both cases they are identified once before the main while Changed loop starts.

The only way I know of preventing any wasted work done on unreachable regions is to check if BB is to maintain a set of blocks that are reachable from entry. We'd need to verify this state with calls to DT on almost every iteration inside ProcessBlock. It's not practical as it greatly lengthens compile time. For large functions like those found in sqlite3.c I was seeing a slowdown of 20% or more to track the 3,000+ blocks in the main REPL function when I initially tried this approach.

If you have ideas to better test IR coverage for JumpThreading I'd be very interested in hearing about them.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
   auto *GuardDecl = F.getParent()->getFunction(
       Intrinsic::getName(Intrinsic::experimental_guard));
   HasGuards = GuardDecl && !GuardDecl->use_empty();
   if (HasProfileData) {
     BPI = std::move(BPI_);
     BFI = std::move(BFI_);
   }
 
-  // Remove unreachable blocks from function as they may result in infinite
-  // loop. We do threading if we found something profitable. Jump threading a
-  // branch can create other opportunities. If these opportunities form a cycle
-  // i.e. if any jump threading is undoing previous threading in the path, then
-  // we will loop forever. We take care of this issue by not jump threading for
-  // back edges. This works for normal cases but not for unreachable blocks as
-  // they may have cycle with no back edge.
-  bool EverChanged = false;
-  EverChanged |= removeUnreachableBlocks(F, LVI, DDT);
+  // JumpThreading must not processes blocks unreachable from entry. It's a
+  // waste of compute time and can potentially lead to hangs.
+  SmallPtrSet<BasicBlock *, 16> Unreachable;
+  DominatorTree &DT = DDT->flush();
+  for (auto &BB : F)
+    if (!DT.isReachableFromEntry(&BB))
+      Unreachable.insert(&BB);
 
   FindLoopHeaders(F);
 
+  bool EverChanged = false;
   bool Changed;
   do {
     Changed = false;
-    for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
-      BasicBlock *BB = &*I;
-      // Thread all of the branches we can over this block.
-      while (ProcessBlock(BB))
+    for (auto &BB : F) {
+      if (Unreachable.count(&BB))
+        continue;
+      while (ProcessBlock(&BB)) // Thread all of the branches we can over BB.
         Changed = true;
-
-      ++I;
-
-      // Don't thread branches over a block that's slated for deletion.
-      if (DDT->pendingDeletedBB(BB))
+      // Stop processing BB if it's been deleted or is the entry block. The
+      // following transforms attempt to delete BB and in the case of the entry
+      // block it is non-trivial to find a suitable replacement.
+      if (&BB == &F.getEntryBlock() || DDT->pendingDeletedBB(&BB))
         continue;
 
-      // If the block is trivially dead, zap it.  This eliminates the successor
-      // edges which simplifies the CFG.
-      if (pred_empty(BB) &&
-          BB != &BB->getParent()->getEntryBlock()) {
-        DEBUG(dbgs() << "  JT: Deleting dead block '" << BB->getName()
-              << "' with terminator: " << *BB->getTerminator() << '\n');
-        LoopHeaders.erase(BB);
-        LVI->eraseBlock(BB);
-        DeleteDeadBlock(BB, DDT);
+      if (pred_empty(&BB)) {
+        // When ProcessBlock makes BB unreachable it doesn't bother to fix up
+        // the instructions in it. We must remove BB to prevent invalid IR.
+        DEBUG(dbgs() << "  JT: Deleting dead block '" << BB.getName()
+                     << "' with terminator: " << *BB.getTerminator() << '\n');
+        LoopHeaders.erase(&BB);
+        LVI->eraseBlock(&BB);
+        DeleteDeadBlock(&BB, DDT);
         Changed = true;
         continue;
       }
 
-      BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
-
-      // Can't thread an unconditional jump, but if the block is "almost
-      // empty", we can replace uses of it with uses of the successor and make
-      // this dead.
-      // We should not eliminate the loop header or latch either, because
-      // eliminating a loop header or latch might later prevent LoopSimplify
-      // from transforming nested loops into simplified form. We will rely on
-      // later passes in backend to clean up empty blocks.
+      // ProcessBlock doen't thread BBs with unconditional TIs. However, if BB
+      // is "almost empty", we attempt to merge BB with its sole successor.
+      auto *BI = dyn_cast<BranchInst>(BB.getTerminator());
       if (BI && BI->isUnconditional() &&
-          BB != &BB->getParent()->getEntryBlock() &&
-          // If the terminator is the only non-phi instruction, try to nuke it.
-          BB->getFirstNonPHIOrDbg()->isTerminator() && !LoopHeaders.count(BB) &&
-          !LoopHeaders.count(BI->getSuccessor(0))) {
-        // FIXME: It is always conservatively correct to drop the info
-        // for a block even if it doesn't get erased.  This isn't totally
-        // awesome, but it allows us to use AssertingVH to prevent nasty
-        // dangling pointer issues within LazyValueInfo.
-        LVI->eraseBlock(BB);
-        if (TryToSimplifyUncondBranchFromEmptyBlock(BB, DDT))
-          Changed = true;
+          // The terminator must be the only non-phi instruction.
+          BB.getFirstNonPHIOrDbg()->isTerminator() &&
+          // Don't alter Loop headers and latches to ensure LoopSimplify will
+          // transform nested loops later.
+          !LoopHeaders.count(&BB) && !LoopHeaders.count(BI->getSuccessor(0)) &&
+          TryToSimplifyUncondBranchFromEmptyBlock(&BB, DDT)) {
+        // We passed in DDT so BB's parent remains F until DDT->flush() is
+        // called. BB can still be used for cleanup.
+        LVI->eraseBlock(&BB);
       }
     }
     EverChanged |= Changed;
   } while (Changed);
 
   LoopHeaders.clear();
   DDT->flush();
   LVI->enableDT();

llvm/test/Transforms/JumpThreading/pr15851_hang.ll

 ; RUN: opt -S -jump-threading < %s | FileCheck %s
 
 ; CHECK-LABEL: @f(
 ; CHECK-LABEL: entry
-; CHECK: ret void
-; CHECK-NOT: for.cond1
-; CHECK-NOT: for.body
+; CHECK-NEXT: ret void
+;
+; JumpThreading must detect the next two blocks are unreachable from entry
+; and leave them alone. A subsequent pass will remove them from @f.
+;
+; CHECK: for.cond1:
+; CHECK-NEXT: phi
+; CHECK-NEXT: icmp
+; CHECK-NEXT: br i1 %cmp, label %for.body, label %for.cond1
+; CHECK: for.body:
+; CHECK-NEXT: add
+; CHECK-NEXT: icmp
+; CHECK-NEXT: br i1 %a, label %for.cond1, label %for.cond1
 
 define void @f() {
 entry:
   ret void
 
 for.cond1:
   %i.025 = phi i32 [ %inc, %for.body ], [ %inc, %for.body ], [ 1, %for.cond1 ]
   %cmp = icmp slt i32 %i.025, 2
   br i1 %cmp, label %for.body, label %for.cond1
 
 for.body:
   %inc = add nsw i32 %i.025, 0
   %a = icmp ugt i32 %inc, 2
   br i1 %a, label %for.cond1, label %for.cond1
 }

llvm/test/Transforms/JumpThreading/select.ll

L4:
   br label %L0
 }
 
 ; Make sure the edge value of %0 from entry to L2 includes 0 and L3 is
 ; reachable.
 ; CHECK: test_switch_default
 ; CHECK: entry:
 ; CHECK: load
-; CHECK: icmp
+; CHECK: switch
 ; CHECK: [[THREADED:[A-Za-z.0-9]+]]:
 ; CHECK: store
 ; CHECK: br
 ; CHECK: L2:
-; CHECK: icmp
+; CHECK-SAME: preds = %entry, %entry
+; CHECK-NEXT: phi i32
 define void @test_switch_default(i32* nocapture %status) nounwind {
 entry:
   %0 = load i32, i32* %status, align 4
   switch i32 %0, label %L2 [
     i32 5061, label %L1
     i32 0, label %L2
   ]