This is an archive of the discontinued LLVM Phabricator instance.

Differential D63629

[JumpThreading][PR42085] Fold constant TIs before calculating LoopHeaders
AbandonedPublic

Authored by brzycki on Jun 20 2019, 3:33 PM.

Details

Reviewers
craig.topper
sebpop
hfinkel
Summary

In some IR shapes constant terminator instructions prevent FindFunctionBackedges() from detecting the true loop headers in F since it's only done once at the beginning of the pass. When ProcessBlock() later detects and convert these constant TIs it is non-trivial to determine if BB, and any of its successors, are loop headers. If we do not have accurate loop header analysis in JumpThreading there is a possibility of a miscompile when threading an edge across the LH. Please see PR42085 for more analysis and the original the failing test cases.

This patch folds all constant TIs before calculating loop header analysis which is what a normal Clang invocation of the pass manager pipeline hands to JT. This allows FindFunctionBackedges() to locate the loop headers in F. It also helps remove unreachable code regions since we remove these inacurate edges from the IR before we calculate Unreachable BBs using dominators in runImpl().

Diff Detail

Event Timeline

brzycki created this revision.Jun 20 2019, 3:33 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 20 2019, 3:33 PM
Herald added subscribers: jfb, hiraditya. · View Herald Transcript
brzycki added a comment.Jun 20 2019, 3:34 PM

This code passes ninja check and a full test-suite run.

lebedev.ri added a subscriber: lebedev.ri.Jun 20 2019, 3:39 PM

Folding conditional terminator instructions for basic blocks that are also loop headers can cause miscompiled code emitted from JumpThreading.

Please can you write a more detailed explanation of the problem in the patch description.
"cause miscompiled code emitted" is vague.

brzycki added a comment.Jun 20 2019, 3:49 PM
In D63629#1552868, @lebedev.ri wrote:

Folding conditional terminator instructions for basic blocks that are also loop headers can cause miscompiled code emitted from JumpThreading.

Please can you write a more detailed explanation of the problem in the patch description.
"cause miscompiled code emitted" is vague.

I forgot to add https://bugs.llvm.org/show_bug.cgi?id=42085 which links to the deeper analysis. I'll fix the description.

brzycki edited the summary of this revision. (Show Details)Jun 20 2019, 3:58 PM
brzycki updated this revision to Diff 206473.Jun 25 2019, 10:05 AM
brzycki retitled this revision from [JumpThreading][PR42085] Do not fold conditional terminators of loop headers to [JumpThreading][PR42085] Fold constant TIs before calculating LoopHeaders.
brzycki edited the summary of this revision. (Show Details)

Passes ninja check and test-suite compilation and lit execution. Compile time for some benchmarks improves for some benchmarks:

  0.9200 -> 0.8200       [ 12.20%]  SingleSource/UnitTests/SignlessTypes/factor.test
  0.2240 -> 0.2000       [ 12.00%]  SingleSource/UnitTests/ms_struct-bitfield.test
  0.4880 -> 0.4360       [ 11.93%]  SingleSource/UnitTests/2003-05-26-Shorts.test
  0.2640 -> 0.2360       [ 11.86%]  SingleSource/UnitTests/2002-04-17-PrintfChar.test
  0.1920 -> 0.1720       [ 11.63%]  SingleSource/UnitTests/block-byref-cxxobj-test.test
  0.3640 -> 0.3320       [  9.64%]  SingleSource/UnitTests/2008-04-18-LoopBug.test
  0.6000 -> 0.5480       [  9.49%]  SingleSource/UnitTests/2002-05-02-CastTest.test
  0.2000 -> 0.1840       [  8.70%]  SingleSource/UnitTests/block-copied-in-cxxobj.test
  0.2640 -> 0.2440       [  8.20%]  SingleSource/UnitTests/DefaultInitDynArrays.test
  0.2320 -> 0.2160       [  7.41%]  SingleSource/UnitTests/2005-07-15-Bitfield-ABI.test
  0.4080 -> 0.3800       [  7.37%]  SingleSource/UnitTests/conditional-gnu-ext-cxx.test
 24.2560 -> 22.6680      [  7.01%]  MicroBenchmarks/ImageProcessing/Interpolation/Interpolation.test
  3.4920 -> 3.2640       [  6.99%]  SingleSource/Benchmarks/CoyoteBench/huffbench.test
  0.4360 -> 0.4080       [  6.86%]  SingleSource/UnitTests/2002-08-19-CodegenBug.test
  0.3760 -> 0.3520       [  6.82%]  SingleSource/UnitTests/2002-05-02-ManyArguments.test
 33.1200 -> 31.0440      [  6.69%]  SingleSource/Benchmarks/Adobe-C++/stepanov_vector.test
  2.8920 -> 2.7160       [  6.48%]  SingleSource/Benchmarks/Polybench/datamining/correlation/correlation.test
  1.1960 -> 1.1240       [  6.41%]  SingleSource/UnitTests/2005-05-11-Popcount-ffs-fls.test
  0.4680 -> 0.4400       [  6.36%]  SingleSource/UnitTests/stmtexpr.test
  8.3920 -> 7.9000       [  6.23%]  SingleSource/UnitTests/C++11/stdthreadbug.test
  0.2760 -> 0.2600       [  6.15%]  SingleSource/UnitTests/StructModifyTest.test
  3.7840 -> 3.5720       [  5.94%]  MultiSource/Benchmarks/ASC_Sequoia/IRSmk/IRSmk.test
  0.5880 -> 0.5560       [  5.76%]  SingleSource/UnitTests/2009-04-16-BitfieldInitialization.test
  0.8200 -> 0.7760       [  5.67%]  SingleSource/Benchmarks/Misc/flops-8.test
  6.0120 -> 5.7040       [  5.40%]  SingleSource/Benchmarks/Polybench/stencils/fdtd-apml/fdtd-apml.test
  0.2480 -> 0.2360       [  5.08%]  SingleSource/UnitTests/2002-08-02-CastTest2.test
  0.2520 -> 0.2400       [  5.00%]  SingleSource/UnitTests/2002-10-13-BadLoad.test
  0.5160 -> 0.4920       [  4.88%]  SingleSource/UnitTests/2002-12-13-MishaTest.test
  9.5360 -> 9.1000       [  4.79%]  MultiSource/Benchmarks/Olden/bh/bh.test
 95.6480 -> 91.2840      [  4.78%]  MultiSource/Benchmarks/TSVC/LoopRestructuring-dbl/LoopRestructuring-dbl.test
 28.4240 -> 27.1280      [  4.78%]  MicroBenchmarks/ImageProcessing/Blur/blur.test
  2.7680 -> 2.6480       [  4.53%]  MultiSource/Benchmarks/Prolangs-C++/trees/trees.test
 20.6520 -> 19.7840      [  4.39%]  SingleSource/Benchmarks/Polybench/medley/reg_detect/reg_detect.test
  2.2040 -> 2.1120       [  4.36%]  SingleSource/Benchmarks/Stanford/FloatMM.test
  5.4480 -> 5.2240       [  4.29%]  MultiSource/Applications/viterbi/viterbi.test
  7.1080 -> 6.8240       [  4.16%]  MultiSource/Benchmarks/Trimaran/netbench-url/netbench-url.test
  0.4080 -> 0.3920       [  4.08%]  SingleSource/UnitTests/2006-02-04-DivRem.test
  1.5840 -> 1.5240       [  3.94%]  MultiSource/Benchmarks/Trimaran/enc-rc4/enc-rc4.test
  0.8680 -> 0.8360       [  3.83%]  SingleSource/Benchmarks/Misc/mandel-2.test
  1.5320 -> 1.4760       [  3.79%]  MultiSource/Benchmarks/MiBench/telecomm-adpcm/telecomm-adpcm.test
  2.1200 -> 2.0440       [  3.72%]  MultiSource/Benchmarks/Olden/perimeter/perimeter.test
  6.9360 -> 6.6920       [  3.65%]  MultiSource/Benchmarks/Ptrdist/ft/ft.test
  1.0760 -> 1.0400       [  3.46%]  MultiSource/Benchmarks/Prolangs-C++/family/family.test
  1.6760 -> 1.6200       [  3.46%]  SingleSource/Benchmarks/BenchmarkGame/fannkuch.test
  0.2440 -> 0.2360       [  3.39%]  SingleSource/UnitTests/2004-02-02-NegativeZero.test
 81.7760 -> 79.2040      [  3.25%]  MultiSource/Benchmarks/TSVC/LinearDependence-flt/LinearDependence-flt.test
 31.3560 -> 30.3920      [  3.17%]  MicroBenchmarks/harris/harris.test
 26.6120 -> 25.8200      [  3.07%]  MultiSource/Benchmarks/Prolangs-C/simulator/simulator.test
  0.8120 -> 0.7880       [  3.05%]  SingleSource/Benchmarks/Misc/flops-5.test
  0.9600 -> 0.9320       [  3.00%]  SingleSource/Benchmarks/Misc/dt.test
 77.8440 -> 75.7840      [  2.72%]  MultiSource/Benchmarks/TSVC/Equivalencing-flt/Equivalencing-flt.test
 94.5200 -> 92.0600      [  2.67%]  MultiSource/Benchmarks/TSVC/InductionVariable-dbl/InductionVariable-dbl.test
 12.9680 -> 12.6400      [  2.59%]  MultiSource/Benchmarks/DOE-ProxyApps-C++/HACCKernels/HACCKernels.test
 40.1440 -> 39.1360      [  2.58%]  SingleSource/Benchmarks/Misc-C++/stepanov_container.test
  0.8080 -> 0.7880       [  2.54%]  SingleSource/Benchmarks/Misc/flops-2.test
  0.9760 -> 0.9520       [  2.52%]  MultiSource/Benchmarks/MiBench/telecomm-CRC32/telecomm-CRC32.test
  3.9120 -> 3.8160       [  2.52%]  MultiSource/Benchmarks/Olden/tsp/tsp.test
  1.7960 -> 1.7520       [  2.51%]  MultiSource/Benchmarks/Prolangs-C/fixoutput/fixoutput.test
  7.0520 -> 6.8800       [  2.50%]  MultiSource/Benchmarks/MiBench/automotive-bitcount/automotive-bitcount.test
  0.3320 -> 0.3240       [  2.47%]  SingleSource/UnitTests/Threads/2010-12-08-tls.test
  4.2560 -> 4.1560       [  2.41%]  MultiSource/Benchmarks/Prolangs-C++/ocean/ocean.test
  2.9040 -> 2.8360       [  2.40%]  MultiSource/Benchmarks/Trimaran/enc-pc1/enc-pc1.test
197.8400 -> 193.3880     [  2.30%]  MultiSource/Applications/oggenc/oggenc.test
 12.7600 -> 12.4760      [  2.28%]  SingleSource/Benchmarks/Misc-C++/Large/ray.test
  0.3680 -> 0.3600       [  2.22%]  SingleSource/UnitTests/2006-01-29-SimpleIndirectCall.test
  2.9800 -> 2.9160       [  2.19%]  SingleSource/Benchmarks/BenchmarkGame/n-body.test
125.9800 -> 123.2760     [  2.19%]  MultiSource/Applications/d/make_dparser.test
  2.4480 -> 2.3960       [  2.17%]  SingleSource/Benchmarks/Stanford/Oscar.test
  4.4040 -> 4.3120       [  2.13%]  SingleSource/Benchmarks/Polybench/stencils/jacobi-2d-imper/jacobi-2d-imper.test
  1.9680 -> 1.9280       [  2.07%]  MultiSource/Benchmarks/FreeBench/mason/mason.test
  7.5440 -> 7.3960       [  2.00%]  MultiSource/Benchmarks/FreeBench/neural/neural.test
  0.2040 -> 0.2000       [  2.00%]  SingleSource/UnitTests/2010-05-24-BitfieldTest.test
  2.6800 -> 2.6280       [  1.98%]  SingleSource/Benchmarks/Polybench/linear-algebra/kernels/trmm/trmm.test
225.3760 -> 221.1200     [  1.92%]  MicroBenchmarks/LCALS/SubsetBRawLoops/lcalsBRaw.test
  1.4840 -> 1.4560       [  1.92%]  SingleSource/UnitTests/initp1.test
  6.8200 -> 6.6920       [  1.91%]  MultiSource/Benchmarks/ASC_Sequoia/CrystalMk/CrystalMk.test
  1.7120 -> 1.6800       [  1.90%]  MultiSource/Benchmarks/VersaBench/bmm/bmm.test
  0.2160 -> 0.2120       [  1.89%]  SingleSource/UnitTests/2007-04-25-weak.test
 30.8960 -> 30.3320      [  1.86%]  SingleSource/Benchmarks/Misc-C++/bigfib.test
  0.2200 -> 0.2160       [  1.85%]  SingleSource/UnitTests/2002-05-02-CastTest1.test
 77.3600 -> 75.9720      [  1.83%]  MultiSource/Benchmarks/TSVC/NodeSplitting-flt/NodeSplitting-flt.test
  0.2240 -> 0.2200       [  1.82%]  SingleSource/UnitTests/2002-05-02-CastTest3.test
 90.6920 -> 89.1360      [  1.75%]  MultiSource/Benchmarks/TSVC/Searching-dbl/Searching-dbl.test
 94.6920 -> 93.0800      [  1.73%]  MultiSource/Benchmarks/TSVC/IndirectAddressing-dbl/IndirectAddressing-dbl.test
 95.6480 -> 94.0240      [  1.73%]  MultiSource/Benchmarks/TSVC/Equivalencing-dbl/Equivalencing-dbl.test
  3.3000 -> 3.2440       [  1.73%]  SingleSource/Benchmarks/Polybench/linear-algebra/kernels/2mm/2mm.test
  2.6360 -> 2.5920       [  1.70%]  SingleSource/Benchmarks/Stanford/IntMM.test
  0.4800 -> 0.4720       [  1.69%]  MultiSource/Benchmarks/Prolangs-C++/NP/np.test
  2.4000 -> 2.3600       [  1.69%]  MultiSource/Benchmarks/McCat/03-testtrie/testtrie.test
 43.2800 -> 42.5600      [  1.69%]  MultiSource/Benchmarks/Ptrdist/bc/bc.test
  3.6840 -> 3.6240       [  1.66%]  MultiSource/Benchmarks/Prolangs-C++/garage/garage.test
  4.2440 -> 4.1760       [  1.63%]  MultiSource/Benchmarks/Olden/health/health.test
  2.9960 -> 2.9480       [  1.63%]  SingleSource/Benchmarks/Polybench/linear-algebra/kernels/atax/atax.test
  3.3080 -> 3.2560       [  1.60%]  SingleSource/Benchmarks/Misc/flops.test
 83.3320 -> 82.0320      [  1.58%]  MultiSource/Benchmarks/TSVC/ControlFlow-flt/ControlFlow-flt.test
 19.9040 -> 19.5960      [  1.57%]  MultiSource/Benchmarks/Prolangs-C/assembler/assembler.test
193.3520 -> 190.4600     [  1.52%]  MultiSource/Benchmarks/MiBench/consumer-lame/consumer-lame.test
869.6760 -> 856.7040     [  1.51%]  MultiSource/Benchmarks/DOE-ProxyApps-C++/CLAMR/CLAMR.test
 77.5960 -> 76.4480      [  1.50%]  MultiSource/Benchmarks/TSVC/LoopRestructuring-flt/LoopRestructuring-flt.test
  1.9360 -> 1.9080       [  1.47%]  SingleSource/Benchmarks/Misc/fbench.test
  3.3200 -> 3.2720       [  1.47%]  MultiSource/Benchmarks/Olden/mst/mst.test
 20.7600 -> 20.4760      [  1.39%]  MultiSource/Benchmarks/McCat/05-eks/eks.test
 11.7360 -> 11.5760      [  1.38%]  MultiSource/Benchmarks/SciMark2-C/scimark2.test
  2.6600 -> 2.6240       [  1.37%]  SingleSource/Benchmarks/Polybench/linear-algebra/solvers/dynprog/dynprog.test
  0.2960 -> 0.2920       [  1.37%]  SingleSource/UnitTests/2009-12-07-StructReturn.test
 79.4960 -> 78.4320      [  1.36%]  MultiSource/Benchmarks/TSVC/Expansion-flt/Expansion-flt.test
 13.2400 -> 13.0640      [  1.35%]  MultiSource/Benchmarks/McCat/18-imp/imp.test
  3.9440 -> 3.8920       [  1.34%]  MultiSource/Benchmarks/Rodinia/srad/srad.test
 96.2000 -> 94.9560      [  1.31%]  MultiSource/Benchmarks/TSVC/GlobalDataFlow-dbl/GlobalDataFlow-dbl.test
  1.2640 -> 1.2480       [  1.28%]  SingleSource/Benchmarks/Stanford/Quicksort.test
  0.3160 -> 0.3120       [  1.28%]  SingleSource/UnitTests/2006-12-07-Compare64BitConstant.test
 54.2280 -> 53.5520      [  1.26%]  MultiSource/Benchmarks/nbench/nbench.test
 10.0040 -> 9.8840       [  1.21%]  MultiSource/Benchmarks/MiBench/security-blowfish/security-blowfish.test
513.1000 -> 507.1320     [  1.18%]  MultiSource/Benchmarks/MiBench/consumer-typeset/consumer-typeset.test
 13.8200 -> 13.6600      [  1.17%]  SingleSource/Benchmarks/Linpack/linpack-pc.test
 77.1760 -> 76.3000      [  1.15%]  MultiSource/Benchmarks/TSVC/Symbolics-flt/Symbolics-flt.test
  1.8280 -> 1.8080       [  1.11%]  SingleSource/Benchmarks/McGill/misr.test
  1.1040 -> 1.0920       [  1.10%]  MultiSource/Benchmarks/Olden/treeadd/treeadd.test
  2.9600 -> 2.9280       [  1.09%]  SingleSource/Benchmarks/Polybench/linear-algebra/kernels/syr2k/syr2k.test
 76.9360 -> 76.1200      [  1.07%]  MultiSource/Benchmarks/TSVC/IndirectAddressing-flt/IndirectAddressing-flt.test
  5.7200 -> 5.6600       [  1.06%]  MultiSource/Benchmarks/Ptrdist/ks/ks.test
  0.3960 -> 0.3920       [  1.02%]  SingleSource/UnitTests/2007-01-04-KNR-Args.test
  0.4120 -> 0.4080       [  0.98%]  SingleSource/UnitTests/ms_struct-bitfield-init.test
  0.8560 -> 0.8480       [  0.94%]  SingleSource/UnitTests/SignlessTypes/shr.test
  0.4400 -> 0.4360       [  0.92%]  SingleSource/UnitTests/AtomicOps.test
138.0680 -> 136.8200     [  0.91%]  MultiSource/Benchmarks/DOE-ProxyApps-C++/miniFE/miniFE.test
  0.4520 -> 0.4480       [  0.89%]  SingleSource/UnitTests/2002-05-02-CastTest2.test
  1.3600 -> 1.3480       [  0.89%]  SingleSource/Benchmarks/BenchmarkGame/Large/fasta.test
 46.8640 -> 46.4560      [  0.88%]  MultiSource/Applications/lemon/lemon.test
  3.7000 -> 3.6680       [  0.87%]  MultiSource/Benchmarks/FreeBench/distray/distray.test
 92.6880 -> 91.8880      [  0.87%]  MultiSource/Benchmarks/TSVC/NodeSplitting-dbl/NodeSplitting-dbl.test
 38.2920 -> 37.9640      [  0.86%]  MultiSource/Applications/ALAC/encode/alacconvert-encode.test
  2.8720 -> 2.8480       [  0.84%]  SingleSource/Benchmarks/Polybench/medley/floyd-warshall/floyd-warshall.test
  0.4880 -> 0.4840       [  0.83%]  SingleSource/UnitTests/2003-07-06-IntOverflow.test
  1.9600 -> 1.9440       [  0.82%]  MultiSource/Benchmarks/McCat/17-bintr/bintr.test
  5.0880 -> 5.0480       [  0.79%]  MultiSource/Benchmarks/MiBench/security-sha/security-sha.test
  3.1920 -> 3.1680       [  0.76%]  SingleSource/Benchmarks/Polybench/linear-algebra/kernels/mvt/mvt.test
  0.5360 -> 0.5320       [  0.75%]  SingleSource/UnitTests/ms_struct-bitfield-init-1.test
  2.7000 -> 2.6800       [  0.75%]  Bitcode/Benchmarks/Halide/blur/halide_blur.test
 26.3360 -> 26.1440      [  0.73%]  MultiSource/Applications/minisat/minisat.test
  1.6600 -> 1.6480       [  0.73%]  SingleSource/Benchmarks/Stanford/Towers.test
227.5280 -> 225.9960     [  0.68%]  MicroBenchmarks/LCALS/SubsetBLambdaLoops/lcalsBLambda.test
  5.9640 -> 5.9240       [  0.68%]  SingleSource/Benchmarks/Polybench/stencils/fdtd-2d/fdtd-2d.test
  2.5240 -> 2.5080       [  0.64%]  SingleSource/Benchmarks/Misc/whetstone.test
 60.6240 -> 60.2400      [  0.64%]  MultiSource/Benchmarks/Prolangs-C/bison/mybison.test
  2.5680 -> 2.5520       [  0.63%]  SingleSource/Benchmarks/Polybench/linear-algebra/kernels/gesummv/gesummv.test
  0.6480 -> 0.6440       [  0.62%]  MultiSource/Benchmarks/Prolangs-C++/primes/primes.test
 16.5240 -> 16.4240      [  0.61%]  MultiSource/Applications/sgefa/sgefa.test
 40.3160 -> 40.0760      [  0.60%]  MultiSource/Benchmarks/MiBench/telecomm-gsm/telecomm-gsm.test
 57.1920 -> 56.8520      [  0.60%]  MultiSource/Benchmarks/mediabench/mpeg2/mpeg2dec/mpeg2decode.test
 33.0720 -> 32.8840      [  0.57%]  MultiSource/Benchmarks/DOE-ProxyApps-C/SimpleMOC/SimpleMOC.test
 36.1520 -> 35.9560      [  0.55%]  MultiSource/Applications/hexxagon/hexxagon.test
 10.4720 -> 10.4160      [  0.54%]  MultiSource/Benchmarks/Olden/voronoi/voronoi.test
 39.8760 -> 39.6640      [  0.53%]  MultiSource/Benchmarks/mediabench/gsm/toast/toast.test
 79.9360 -> 79.5200      [  0.52%]  MultiSource/Benchmarks/TSVC/Reductions-flt/Reductions-flt.test
  1.5760 -> 1.5680       [  0.51%]  MultiSource/Benchmarks/llubenchmark/llu.test
  5.6360 -> 5.6080       [  0.50%]  SingleSource/Benchmarks/Stanford/Puzzle.test
  3.2280 -> 3.2120       [  0.50%]  SingleSource/Benchmarks/Polybench/datamining/covariance/covariance.test

and regresses for others:

  0.3320 <- 0.4000       [ 20.48%]  SingleSource/UnitTests/2003-07-10-SignConversions.test
  0.2960 <- 0.3520       [ 18.92%]  SingleSource/UnitTests/2003-09-18-BitFieldTest.test
  0.1880 <- 0.2200       [ 17.02%]  SingleSource/UnitTests/ms_struct_pack_layout-1.test
  0.7400 <- 0.8640       [ 16.76%]  SingleSource/UnitTests/2003-07-09-SignedArgs.test
  8.7360 <- 9.9080       [ 13.42%]  MultiSource/Benchmarks/Prolangs-C++/deriv1/deriv1.test
  0.4320 <- 0.4840       [ 12.04%]  SingleSource/UnitTests/2003-08-05-CastFPToUint.test
  0.3080 <- 0.3440       [ 11.69%]  SingleSource/UnitTests/2002-05-19-DivTest.test
  0.3200 <- 0.3560       [ 11.25%]  SingleSource/UnitTests/2008-04-20-LoopBug2.test
  0.3680 <- 0.4080       [ 10.87%]  SingleSource/UnitTests/2003-04-22-Switch.test
  2.9160 <- 3.2080       [ 10.01%]  SingleSource/Benchmarks/Polybench/linear-algebra/kernels/symm/symm.test
  0.3200 <- 0.3520       [ 10.00%]  SingleSource/UnitTests/2002-10-12-StructureArgsSimple.test
  1.1480 <- 1.2560       [  9.41%]  SingleSource/Benchmarks/Misc/mandel.test
  0.5600 <- 0.6120       [  9.29%]  SingleSource/UnitTests/2003-07-09-LoadShorts.test
  0.1840 <- 0.2000       [  8.70%]  SingleSource/UnitTests/block-byref-test.test
  0.7560 <- 0.8200       [  8.47%]  SingleSource/Benchmarks/Misc/flops-6.test
  0.1920 <- 0.2080       [  8.33%]  SingleSource/UnitTests/ms_struct-bitfield-1.test
  0.4400 <- 0.4760       [  8.18%]  SingleSource/UnitTests/ms_struct_pack_layout.test
  0.3680 <- 0.3960       [  7.61%]  SingleSource/UnitTests/byval-alignment.test
  0.4760 <- 0.5120       [  7.56%]  SingleSource/UnitTests/Threads/tls.test
  0.8120 <- 0.8720       [  7.39%]  SingleSource/UnitTests/SignlessTypes/div.test
  1.7480 <- 1.8760       [  7.32%]  MultiSource/Benchmarks/McCat/15-trie/trie.test
  1.8520 <- 1.9840       [  7.13%]  MultiSource/Benchmarks/BitBench/five11/five11.test
  0.7560 <- 0.8080       [  6.88%]  SingleSource/Benchmarks/Misc/flops-4.test
  0.1800 <- 0.1920       [  6.67%]  SingleSource/UnitTests/blockstret.test
  2.2760 <- 2.4240       [  6.50%]  SingleSource/Benchmarks/Misc/salsa20.test
  0.2480 <- 0.2640       [  6.45%]  SingleSource/UnitTests/SignlessTypes/cast-bug.test
  1.3720 <- 1.4560       [  6.12%]  MultiSource/Benchmarks/mediabench/adpcm/rawdaudio/rawdaudio.test
 35.4240 <- 37.5800      [  6.09%]  MultiSource/UnitTests/C++11/frame_layout/frame_layout.test
  1.7160 <- 1.8200       [  6.06%]  SingleSource/Benchmarks/BenchmarkGame/puzzle.test
  1.3760 <- 1.4560       [  5.81%]  SingleSource/Benchmarks/Dhrystone/fldry.test
 17.3920 <- 18.3800      [  5.68%]  SingleSource/UnitTests/Vectorizer/gcc-loops.test
  1.4800 <- 1.5640       [  5.68%]  SingleSource/UnitTests/SignlessTypes/Large/cast.test
  2.6280 <- 2.7760       [  5.63%]  SingleSource/Benchmarks/Misc/ffbench.test
  0.3680 <- 0.3880       [  5.43%]  SingleSource/UnitTests/2003-05-02-DependentPHI.test
  0.3680 <- 0.3880       [  5.43%]  SingleSource/UnitTests/2007-03-02-VaCopy.test
  1.4120 <- 1.4880       [  5.38%]  SingleSource/Benchmarks/Misc/perlin.test
  0.3000 <- 0.3160       [  5.33%]  SingleSource/UnitTests/2003-10-13-SwitchTest.test
 25.5080 <- 26.8160      [  5.13%]  MultiSource/Benchmarks/Ptrdist/yacr2/yacr2.test
  0.5840 <- 0.6120       [  4.79%]  SingleSource/Benchmarks/Misc-C++/mandel-text.test
  1.0080 <- 1.0560       [  4.76%]  SingleSource/UnitTests/vla.test
  2.2480 <- 2.3520       [  4.63%]  MultiSource/Benchmarks/NPB-serial/is/is.test
  0.5280 <- 0.5520       [  4.55%]  SingleSource/UnitTests/2004-11-28-GlobalBoolLayout.test
  0.7440 <- 0.7760       [  4.30%]  SingleSource/Benchmarks/Misc/flops-3.test
  1.3280 <- 1.3840       [  4.22%]  MultiSource/Benchmarks/BitBench/uuencode/uuencode.test
  0.8720 <- 0.9080       [  4.13%]  MultiSource/Benchmarks/Prolangs-C++/vcirc/vcirc.test
119.4640 <- 124.3280     [  4.07%]  SingleSource/Benchmarks/Misc-C++-EH/spirit.test
  0.7000 <- 0.7280       [  4.00%]  SingleSource/Benchmarks/Misc/flops-7.test
 75.1280 <- 78.1040      [  3.96%]  MultiSource/Benchmarks/TSVC/Recurrences-flt/Recurrences-flt.test
  1.0200 <- 1.0600       [  3.92%]  SingleSource/Benchmarks/Misc/evalloop.test
451.9000 <- 469.3280     [  3.86%]  MultiSource/Applications/sqlite3/sqlite3.test
  0.3160 <- 0.3280       [  3.80%]  SingleSource/UnitTests/2002-08-02-CastTest.test
  0.8440 <- 0.8760       [  3.79%]  SingleSource/Benchmarks/BenchmarkGame/partialsums.test
  1.3160 <- 1.3640       [  3.65%]  SingleSource/Benchmarks/Stanford/Bubblesort.test
  0.6600 <- 0.6840       [  3.64%]  SingleSource/Benchmarks/BenchmarkGame/recursive.test
 93.8360 <- 97.2200      [  3.61%]  MultiSource/Benchmarks/TSVC/ControlLoops-dbl/ControlLoops-dbl.test
  0.3360 <- 0.3480       [  3.57%]  SingleSource/UnitTests/2003-10-29-ScalarReplBug.test
 93.2880 <- 96.6040      [  3.55%]  MultiSource/Benchmarks/TSVC/Expansion-dbl/Expansion-dbl.test
  0.3400 <- 0.3520       [  3.53%]  SingleSource/UnitTests/FloatPrecision.test
  9.1080 <- 9.4240       [  3.47%]  MultiSource/Benchmarks/Prolangs-C/loader/loader.test
 78.0120 <- 80.6920      [  3.44%]  MultiSource/Benchmarks/TSVC/ControlLoops-flt/ControlLoops-flt.test
  3.2840 <- 3.3960       [  3.41%]  SingleSource/Benchmarks/Polybench/linear-algebra/solvers/lu/lu.test
  0.5880 <- 0.6080       [  3.40%]  SingleSource/UnitTests/2006-01-23-UnionInit.test
  4.3600 <- 4.5080       [  3.39%]  SingleSource/UnitTests/2006-12-11-LoadConstants.test
  6.3680 <- 6.5840       [  3.39%]  MultiSource/Benchmarks/mediabench/g721/g721encode/encode.test
  0.3600 <- 0.3720       [  3.33%]  SingleSource/UnitTests/2003-07-08-BitOpsTest.test
  0.6040 <- 0.6240       [  3.31%]  SingleSource/UnitTests/2003-05-31-CastToBool.test
  0.5000 <- 0.5160       [  3.20%]  SingleSource/UnitTests/member-function-pointers.test
  0.8800 <- 0.9080       [  3.18%]  SingleSource/UnitTests/2003-08-11-VaListArg.test
  0.3800 <- 0.3920       [  3.16%]  SingleSource/UnitTests/2005-05-12-Int64ToFP.test
  2.9400 <- 3.0320       [  3.13%]  MultiSource/Benchmarks/Trimaran/netbench-crc/netbench-crc.test
  3.3840 <- 3.4880       [  3.07%]  SingleSource/Benchmarks/Polybench/linear-algebra/kernels/cholesky/cholesky.test
  1.4400 <- 1.4840       [  3.06%]  MultiSource/Benchmarks/mediabench/adpcm/rawcaudio/rawcaudio.test
  4.1960 <- 4.3240       [  3.05%]  MultiSource/Benchmarks/MiBench/automotive-basicmath/automotive-basicmath.test
 72.2360 <- 74.3560      [  2.93%]  MultiSource/Benchmarks/PAQ8p/paq8p.test
  0.9600 <- 0.9880       [  2.92%]  SingleSource/Benchmarks/Stanford/Perm.test
  2.3360 <- 2.4040       [  2.91%]  MultiSource/Benchmarks/McCat/12-IOtest/iotest.test
  2.4840 <- 2.5560       [  2.90%]  MultiSource/Benchmarks/Rodinia/pathfinder/pathfinder.test
 74.5080 <- 76.6480      [  2.87%]  MultiSource/Benchmarks/TSVC/StatementReordering-flt/StatementReordering-flt.test
 91.9920 <- 94.6200      [  2.86%]  MultiSource/Benchmarks/TSVC/Symbolics-dbl/Symbolics-dbl.test
  2.5080 <- 2.5760       [  2.71%]  SingleSource/Benchmarks/CoyoteBench/almabench.test
 91.8320 <- 94.3000      [  2.69%]  MultiSource/Benchmarks/TSVC/LoopRerolling-dbl/LoopRerolling-dbl.test
  0.4480 <- 0.4600       [  2.68%]  SingleSource/Benchmarks/Misc/pi.test
  0.3160 <- 0.3240       [  2.53%]  SingleSource/UnitTests/2006-12-01-float_varg.test
 89.7320 <- 91.9760      [  2.50%]  MultiSource/Benchmarks/TSVC/Recurrences-dbl/Recurrences-dbl.test
  2.2720 <- 2.3280       [  2.46%]  SingleSource/Benchmarks/Polybench/linear-algebra/kernels/trisolv/trisolv.test
  0.3280 <- 0.3360       [  2.44%]  SingleSource/UnitTests/2003-08-20-FoldBug.test
  2.5280 <- 2.5880       [  2.37%]  SingleSource/Benchmarks/Misc/richards_benchmark.test
 79.2720 <- 81.1320      [  2.35%]  MultiSource/Benchmarks/DOE-ProxyApps-C++/HPCCG/HPCCG.test
  3.0760 <- 3.1440       [  2.21%]  SingleSource/Benchmarks/Polybench/linear-algebra/kernels/bicg/bicg.test
  0.7240 <- 0.7400       [  2.21%]  SingleSource/UnitTests/2006-12-04-DynAllocAndRestore.test
  0.3640 <- 0.3720       [  2.20%]  SingleSource/UnitTests/2002-10-12-StructureArgs.test
  2.7880 <- 2.8480       [  2.15%]  SingleSource/Benchmarks/Polybench/linear-algebra/kernels/gemm/gemm.test
  0.3720 <- 0.3800       [  2.15%]  SingleSource/UnitTests/printargs.test
  1.8800 <- 1.9200       [  2.13%]  MultiSource/Benchmarks/VersaBench/8b10b/8b10b.test
  0.1880 <- 0.1920       [  2.13%]  SingleSource/UnitTests/block-call-r7674133.test
  4.9360 <- 5.0400       [  2.11%]  MultiSource/Benchmarks/Fhourstones-3.1/fhourstones3.1.test
  0.1920 <- 0.1960       [  2.08%]  SingleSource/UnitTests/block-copied-in-cxxobj-1.test
  1.3440 <- 1.3720       [  2.08%]  MultiSource/Benchmarks/MiBench/network-dijkstra/network-dijkstra.test
 41.4040 <- 42.2240      [  1.98%]  SingleSource/Benchmarks/Adobe-C++/functionobjects.test
  0.6080 <- 0.6200       [  1.97%]  SingleSource/UnitTests/SignlessTypes/ccc.test
  1.8680 <- 1.9040       [  1.93%]  MultiSource/Benchmarks/Olden/bisort/bisort.test
  8.1800 <- 8.3320       [  1.86%]  MultiSource/Benchmarks/Trimaran/enc-md5/enc-md5.test
  1.5080 <- 1.5360       [  1.86%]  MultiSource/Benchmarks/Prolangs-C++/fsm/fsm.test
  0.4320 <- 0.4400       [  1.85%]  SingleSource/UnitTests/2002-05-03-NotTest.test
  0.4400 <- 0.4480       [  1.82%]  SingleSource/UnitTests/2007-04-10-BitfieldTest.test
  3.3160 <- 3.3720       [  1.69%]  SingleSource/Benchmarks/Polybench/stencils/adi/adi.test
 21.7920 <- 22.1600      [  1.69%]  MultiSource/Benchmarks/ASC_Sequoia/AMGmk/AMGmk.test
  8.3440 <- 8.4840       [  1.68%]  MultiSource/Benchmarks/Prolangs-C++/office/office.test
 19.2680 <- 19.5880      [  1.66%]  MicroBenchmarks/XRay/ReturnReference/retref-bench.test
  0.7360 <- 0.7480       [  1.63%]  SingleSource/Benchmarks/Misc/fp-convert.test
 40.9200 <- 41.5840      [  1.62%]  MultiSource/Benchmarks/FreeBench/pifft/pifft.test
  4.2080 <- 4.2760       [  1.62%]  MultiSource/Benchmarks/Olden/power/power.test
 22.3880 <- 22.7440      [  1.59%]  MultiSource/Benchmarks/VersaBench/dbms/dbms.test
  0.7680 <- 0.7800       [  1.56%]  SingleSource/Benchmarks/Misc/flops-1.test
  0.5240 <- 0.5320       [  1.53%]  SingleSource/UnitTests/2005-07-17-INT-To-FP.test
  5.8680 <- 5.9520       [  1.43%]  SingleSource/Benchmarks/CoyoteBench/lpbench.test
  3.9600 <- 4.0160       [  1.41%]  MultiSource/Benchmarks/McCat/04-bisect/bisect.test
  2.8360 <- 2.8760       [  1.41%]  SingleSource/Benchmarks/Polybench/linear-algebra/kernels/syrk/syrk.test
  3.1280 <- 3.1720       [  1.41%]  SingleSource/Benchmarks/Polybench/stencils/jacobi-1d-imper/jacobi-1d-imper.test
  3.7680 <- 3.8200       [  1.38%]  SingleSource/UnitTests/SignlessTypes/rem.test
  6.6800 <- 6.7720       [  1.38%]  SingleSource/Benchmarks/Misc-C++/stepanov_v1p2.test
 14.9680 <- 15.1680      [  1.34%]  MultiSource/Benchmarks/VersaBench/beamformer/beamformer.test
  4.5560 <- 4.6160       [  1.32%]  MultiSource/Benchmarks/MiBench/telecomm-FFT/telecomm-fft.test
  0.9200 <- 0.9320       [  1.30%]  SingleSource/Benchmarks/BenchmarkGame/nsieve-bits.test
  0.3120 <- 0.3160       [  1.28%]  SingleSource/UnitTests/2004-06-20-StaticBitfieldInit.test
  0.6400 <- 0.6480       [  1.25%]  SingleSource/Benchmarks/Misc/lowercase.test
  0.3240 <- 0.3280       [  1.23%]  SingleSource/UnitTests/2003-05-31-LongShifts.test
 10.6280 <- 10.7560      [  1.20%]  MultiSource/Benchmarks/Prolangs-C++/shapes/shapes.test
  2.0000 <- 2.0240       [  1.20%]  MultiSource/Benchmarks/Prolangs-C++/simul/simul.test
  0.3360 <- 0.3400       [  1.19%]  SingleSource/UnitTests/2005-05-13-SDivTwo.test
  3.5120 <- 3.5520       [  1.14%]  SingleSource/Benchmarks/Polybench/linear-algebra/kernels/gemver/gemver.test
 29.5120 <- 29.8440      [  1.12%]  MultiSource/Benchmarks/Prolangs-C/football/football.test
  2.9280 <- 2.9600       [  1.09%]  MultiSource/Benchmarks/Prolangs-C++/objects/objects.test
 45.4760 <- 45.9720      [  1.09%]  MultiSource/Applications/hbd/hbd.test
  8.4480 <- 8.5400       [  1.09%]  SingleSource/Benchmarks/Misc/ReedSolomon.test
 75.3400 <- 76.1600      [  1.09%]  MultiSource/Benchmarks/TSVC/LoopRerolling-flt/LoopRerolling-flt.test
 73.7840 <- 74.5800      [  1.08%]  MultiSource/Benchmarks/TSVC/Searching-flt/Searching-flt.test
  5.5680 <- 5.6280       [  1.08%]  MultiSource/Benchmarks/MiBench/office-stringsearch/office-stringsearch.test
 44.8240 <- 45.3040      [  1.07%]  MultiSource/Applications/Burg/burg.test
  7.2760 <- 7.3520       [  1.04%]  SingleSource/Benchmarks/McGill/chomp.test
 13.1520 <- 13.2880      [  1.03%]  MicroBenchmarks/LoopInterchange/LoopInterchange.test
  0.3880 <- 0.3920       [  1.03%]  SingleSource/UnitTests/2008-07-13-InlineSetjmp.test
  0.4040 <- 0.4080       [  0.99%]  SingleSource/UnitTests/TestLoop.test
 16.2280 <- 16.3880      [  0.99%]  MultiSource/Benchmarks/FreeBench/fourinarow/fourinarow.test
  0.4080 <- 0.4120       [  0.98%]  SingleSource/UnitTests/2002-10-09-ArrayResolution.test
 74.3560 <- 75.0760      [  0.97%]  MultiSource/Benchmarks/TSVC/Packing-flt/Packing-flt.test
  1.2440 <- 1.2560       [  0.96%]  SingleSource/Benchmarks/Stanford/Treesort.test
  2.5080 <- 2.5320       [  0.96%]  MultiSource/Benchmarks/MiBench/network-patricia/network-patricia.test
 13.8000 <- 13.9280      [  0.93%]  MultiSource/Benchmarks/DOE-ProxyApps-C/RSBench/rsbench.test
 99.7880 <- 100.7120     [  0.93%]  SingleSource/Benchmarks/Adobe-C++/simple_types_constant_folding.test
  0.4360 <- 0.4400       [  0.92%]  SingleSource/UnitTests/2003-05-14-AtExit.test
 62.6160 <- 63.1720      [  0.89%]  MultiSource/Benchmarks/DOE-ProxyApps-C/miniGMG/miniGMG.test
  1.8160 <- 1.8320       [  0.88%]  SingleSource/Benchmarks/BenchmarkGame/spectral-norm.test
  2.2720 <- 2.2920       [  0.88%]  MultiSource/Benchmarks/Prolangs-C/allroots/allroots.test
  4.1400 <- 4.1760       [  0.87%]  SingleSource/Benchmarks/SmallPT/smallpt.test
 37.1640 <- 37.4840      [  0.86%]  MultiSource/Applications/obsequi/Obsequi.test
 33.4560 <- 33.7320      [  0.82%]  MultiSource/Benchmarks/Prolangs-C/unix-tbl/unix-tbl.test
548.8680 <- 553.3840     [  0.82%]  MultiSource/Applications/kimwitu++/kc.test
 26.0760 <- 26.2880      [  0.81%]  SingleSource/Benchmarks/Adobe-C++/stepanov_abstraction.test
 77.5280 <- 78.1560      [  0.81%]  MultiSource/Benchmarks/TSVC/CrossingThresholds-flt/CrossingThresholds-flt.test
 57.1480 <- 57.6080      [  0.80%]  MultiSource/Benchmarks/Prolangs-C++/city/city.test
  1.9920 <- 2.0080       [  0.80%]  SingleSource/Benchmarks/Stanford/RealMM.test
 37.6320 <- 37.9200      [  0.77%]  MultiSource/Applications/ALAC/decode/alacconvert-decode.test
 14.2080 <- 14.3160      [  0.76%]  MultiSource/Benchmarks/Prolangs-C/plot2fig/plot2fig.test
168.1240 <- 169.3720     [  0.74%]  SingleSource/Benchmarks/Adobe-C++/loop_unroll.test
  3.8360 <- 3.8640       [  0.73%]  SingleSource/Benchmarks/Polybench/linear-algebra/kernels/3mm/3mm.test
  2.2160 <- 2.2320       [  0.72%]  MultiSource/Benchmarks/Prolangs-C++/life/life.test
 53.9240 <- 54.3120      [  0.72%]  MultiSource/Applications/SIBsim4/SIBsim4.test
 27.9880 <- 28.1840      [  0.70%]  MultiSource/Benchmarks/DOE-ProxyApps-C/Pathfinder/PathFinder.test
 13.7480 <- 13.8440      [  0.70%]  MultiSource/Benchmarks/Prolangs-C/compiler/compiler.test
  9.4480 <- 9.5080       [  0.64%]  SingleSource/Benchmarks/Misc/himenobmtxpa.test
  9.1920 <- 9.2480       [  0.61%]  MultiSource/Benchmarks/McCat/08-main/main.test
342.7920 <- 344.8640     [  0.60%]  MultiSource/Benchmarks/Prolangs-C/TimberWolfMC/timberwolfmc.test
 27.2840 <- 27.4400      [  0.57%]  MicroBenchmarks/ImageProcessing/Dither/Dither.test
  1.4240 <- 1.4320       [  0.56%]  SingleSource/Benchmarks/Stanford/Queens.test
  1.4560 <- 1.4640       [  0.55%]  MultiSource/Benchmarks/BitBench/drop3/drop3.test
  3.6560 <- 3.6760       [  0.55%]  MultiSource/Applications/aha/aha.test
 67.1080 <- 67.4600      [  0.52%]  MultiSource/Benchmarks/DOE-ProxyApps-C/miniAMR/miniAMR.test
 24.5600 <- 24.6840      [  0.50%]  MicroBenchmarks/ImageProcessing/BilateralFiltering/BilateralFilter.test

I suspect the regressions are due to a larger number of blocks in F such as spirit and sqlite3 which both regress around 4%.

xbolva00 added a subscriber: xbolva00.Jun 25 2019, 10:43 AM

Maybe you can use some reasonable BB size threshold to fix these regressions ?

brzycki added a comment.Jun 25 2019, 10:53 AM
In D63629#1557847, @xbolva00 wrote:

Maybe you can use some reasonable BB size threshold to fix these regressions ?

Hello @xbolva00, I appreciate your help but I but don't quite understand how to apply your suggestion. I have to remove trivially constant TIs from all BBs before calculating LoopHeaders and is irrespective of the size of each BB or of the size of F. I'm curious if you meant to apply such a heuristic in FindFunctionBackedges()?

xbolva00 added a comment.Jun 25 2019, 11:04 AM

Yes, FindFunctionBackedges. But not sure if it would not introduce new regressions..

brzycki added a comment.Jun 25 2019, 11:21 AM
In D63629#1557870, @xbolva00 wrote:

Yes, FindFunctionBackedges. But not sure if it would not introduce new regressions..

Yes, that's my concern as well. The way that JumpThreading uses FindFunctionBackedges() is a bit unusual as a proxy for detecting loop headers without dominators or loopinfo. I'm unsure if alternate forms of loopheader detection using this analysis can remove the need to eliminate these invalid edges in F. The core problem of this IR shape is JT's analysis fails to detect the true loop headers and eventually we thread across one.

efriedma added a subscriber: efriedma.Jun 26 2019, 3:30 PM

there is a possibility of a miscompile when threading an edge across the LH

How do we actually get a miscompile? The reason we don't thread across loop headers is to promote later loop optimizations, not because threading across loop headers is unsound. In general, we have to support irreducible CFGs, and I'm worried this fix is covering up a bug in our handling of such code.

brzycki added a comment.EditedJun 27 2019, 8:43 AM

Hello @efriedma,

How do we actually get a miscompile?

The new test-case below, pr42085-loopheader-detection.ll exhibits the miscompile on unpatched tip LLVM. In PR42085 I've attached a test harness which runs the code using a simple main.c and a shell script. The main.c looks like:

#include <libgen.h>
#include <stdio.h>
#include <stdlib.h>

extern int test(unsigned char, unsigned char);

char *name;

int main(int arc, char *argv[]) {
  unsigned char arg1 = atoi(argv[1]);
  unsigned char arg2 = atoi(argv[2]);
  name = basename(argv[0]);
  printf("    [%-10s] test == %d\n", name, test(arg1, arg2));
  return 0;
}

And we compile pr42085-loopheader-detection.ll two different ways to thread and not thread the code:

echo build main.o
"$clang" -O3 -c "$main" $debug -o main.o

echo build pr.o
"$llc" -O0 "$pr" -o pr.s
"$clang" -c pr.s -o pr.o

echo build jt.o
"$opt" -passes=jump-threading -S -o jt.ll "$pr"
"$llc" -O0 jt.ll -o jt.s
"$clang" -c jt.s -o jt.o

echo link
"$clang" jt.o main.o -o runme_jt
"$clang" pr.o main.o -o runme_pr

In the above code pr.o is not JumpThreaded while jt.o is.

the output of execution shows the miscompile. When test(0, 0) is called we see different returned values:

[ INPUT ==> arg1=0 arg1=0 ]
    [runme_pr  ] test == 2
    [runme_jt  ] test == 3

[ INPUT ==> arg1=0 arg1=1 ]
    [runme_pr  ] test == 0
    [runme_jt  ] test == 0

[ INPUT ==> arg1=1 arg1=0 ]
    [runme_pr  ] test == -1
    [runme_jt  ] test == -1

[ INPUT ==> arg1=1 arg1=1 ]
    [runme_pr  ] test == -1
    [runme_jt  ] test == -1

In the miscompile case we thread body1 ==> body2 ==> latch1 to body1 ==> body2.thread ==> latch1. We find the following backedges from FindFunctionBackedges(). We store the destination Edge.second as each BB entry in LoopHeaders:

latch2 ==> body1
body1  ==> pre_head

With the fix (removing trivial constant terminators) before calculating LoopHeaders, the function FindFunctionBackedges() finds the following edges:

body1 ==> body2
body1 ==> pre_head

And correctly promoting body2 to a loop header pessimizes threads across it.

I'm worried this fix is covering up a bug in our handling of [loop header] code.

It's entirely possible, I'm not an expert on loop transforms. The reason I went down this path is I noticed the change in LoopHeaders when I made the following single change to the IR:

--- pr42085.ll  2019-06-27 09:55:57.501853639 -0500
+++ pr42085_good.ll     2019-06-27 10:36:57.667534318 -0500
@@ -15,7 +15,7 @@
   br i1 %ARG1, label %exit, label %head2

 head2:
-  br i1 false, label %head3, label %body2
+  br label %body2

 head3:
   %tmp8 = add i32 %tmp3, 1

Using the above IR with opt -S -jump-threading on an unpatched LLVM compiler does not exhibit the miscompile. But, as you say, this may be masking a deeper issue that I haven't noticed. I'd definitely appreciate your expertise or any suggestions you may have.

efriedma added a comment.Jun 27 2019, 5:52 PM

Posted https://reviews.llvm.org/D63913

brzycki abandoned this revision.Jun 28 2019, 9:22 AM

Abandoning for @efriedma 's patch in D63913.

brzycki mentioned this in D63913: [JumpThreading] Fix threading with unusual PHI nodes..Jul 2 2019, 8:23 AM

Revision Contents

PathSize
llvm/
include/
llvm/
Transforms/
Scalar/
2 lines
lib/
Transforms/
Scalar/
43 lines
test/
Transforms/
JumpThreading/
7 lines
46 lines
4 lines
4 lines

Diff 206473

llvm/include/llvm/Transforms/Scalar/JumpThreading.h

Show First 20 Lines • Show All 101 Lines • ▼ Show 20 Linespublic:
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
void releaseMemory() { void releaseMemory() {
BFI.reset(); BFI.reset();
BPI.reset(); BPI.reset();
} }
void FindLoopHeaders(Function &F); bool FindLoopHeaders(Function &F);
bool ProcessBlock(BasicBlock *BB); bool ProcessBlock(BasicBlock *BB);
bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs, bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs,
BasicBlock *SuccBB); BasicBlock *SuccBB);
bool DuplicateCondBranchOnPHIIntoPred( bool DuplicateCondBranchOnPHIIntoPred(
BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs); BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
bool ComputeValueKnownInPredecessorsImpl( bool ComputeValueKnownInPredecessorsImpl(
Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result, Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result,
▲ Show 20 Lines • Show All 44 Lines • Show Last 20 Lines

llvm/lib/Transforms/Scalar/JumpThreading.cpp

Show First 20 Lines • Show All 357 Lines • ▼ Show 20 Lines if (HasProfileData) {
BFI = std::move(BFI_); BFI = std::move(BFI_);
} }
// JumpThreading must not processes blocks unreachable from entry. It's a // JumpThreading must not processes blocks unreachable from entry. It's a
// waste of compute time and can potentially lead to hangs. // waste of compute time and can potentially lead to hangs.
SmallPtrSet<BasicBlock *, 16> Unreachable; SmallPtrSet<BasicBlock *, 16> Unreachable;
assert(DTU && "DTU isn't passed into JumpThreading before using it."); assert(DTU && "DTU isn't passed into JumpThreading before using it.");
assert(DTU->hasDomTree() && "JumpThreading relies on DomTree to proceed."); assert(DTU->hasDomTree() && "JumpThreading relies on DomTree to proceed.");
bool EverChanged = FindLoopHeaders(F);
DominatorTree &DT = DTU->getDomTree(); DominatorTree &DT = DTU->getDomTree();
for (auto &BB : F) for (auto &BB : F)
if (!DT.isReachableFromEntry(&BB)) if (!DT.isReachableFromEntry(&BB))
Unreachable.insert(&BB); Unreachable.insert(&BB);
FindLoopHeaders(F);
bool EverChanged = false;
bool Changed; bool Changed;
do { do {
Changed = false; Changed = false;
for (auto &BB : F) { for (auto &BB : F) {
if (Unreachable.count(&BB)) if (Unreachable.count(&BB))
continue; continue;
while (ProcessBlock(&BB)) // Thread all of the branches we can over BB. while (ProcessBlock(&BB)) // Thread all of the branches we can over BB.
Changed = true; Changed = true;
▲ Show 20 Lines • Show All 153 Lines • ▼ Show 20 Lines
/// Note that there definitely are cases when we want to allow threading of /// Note that there definitely are cases when we want to allow threading of
/// edges across a loop header. For example, threading a jump from outside the /// edges across a loop header. For example, threading a jump from outside the
/// loop (the preheader) to an exit block of the loop is definitely profitable. /// loop (the preheader) to an exit block of the loop is definitely profitable.
/// It is also almost always profitable to thread backedges from within the loop /// It is also almost always profitable to thread backedges from within the loop
/// to exit blocks, and is often profitable to thread backedges to other blocks /// to exit blocks, and is often profitable to thread backedges to other blocks
/// within the loop (forming a nested loop). This simple analysis is not rich /// within the loop (forming a nested loop). This simple analysis is not rich
/// enough to track all of these properties and keep it up-to-date as the CFG /// enough to track all of these properties and keep it up-to-date as the CFG
/// mutates, so we don't allow any of these transformations. /// mutates, so we don't allow any of these transformations.
void JumpThreadingPass::FindLoopHeaders(Function &F) { bool JumpThreadingPass::FindLoopHeaders(Function &F) {
// FindFunctionBackedges() only examines the edges present in the IR and
// constant terminators can obscure the true loop headers of F. When
// JumpThreading eventually folds these terminators in ProcessBlock() it is
// non-trivial to re-run partial analysis to detect potentially new (correct)
// loop headers. We eliminate that issue here by converting all TIs that can
// be folded before detecting our loop headers. This also aids in removing
// dead code and potentially reducing the number of blocks we examine in the
// main JumpThreading loop.
bool Changed = false;
for (auto &BB : F) {
if (ConstantFoldTerminator(&BB, true, TLI, DTU)) {
Changed = true;
++NumFolds;
LLVM_DEBUG(dbgs() << " FindLoopHeaders, in block '" << BB.getName()
<< "' folded to new terminator: " << *BB.getTerminator()
<< '\n');
}
}
SmallVector<std::pair<const BasicBlock*,const BasicBlock*>, 32> Edges; SmallVector<std::pair<const BasicBlock *, const BasicBlock *>, 32> Edges;
FindFunctionBackedges(F, Edges); FindFunctionBackedges(F, Edges);
for (const auto &Edge : Edges) for (const auto &Edge : Edges)
LoopHeaders.insert(Edge.second); LoopHeaders.insert(Edge.second);
return Changed;
} }
/// getKnownConstant - Helper method to determine if we can thread over a /// getKnownConstant - Helper method to determine if we can thread over a
/// terminator with the given value as its condition, and if so what value to /// terminator with the given value as its condition, and if so what value to
/// use for that. What kind of value this is depends on whether we want an /// use for that. What kind of value this is depends on whether we want an
/// integer or a block address, but an undef is always accepted. /// integer or a block address, but an undef is always accepted.
/// Returns null if Val is null or not an appropriate constant. /// Returns null if Val is null or not an appropriate constant.
static Constant *getKnownConstant(Value *Val, ConstantPreference Preference) { static Constant *getKnownConstant(Value *Val, ConstantPreference Preference) {
▲ Show 20 Lines • Show All 538 Lines • ▼ Show 20 Lines if (isa<UndefValue>(Condition)) {
return true; return true;
} }
// If the terminator of this block is branching on a constant, simplify the // If the terminator of this block is branching on a constant, simplify the
// terminator to an unconditional branch. This can occur due to threading in // terminator to an unconditional branch. This can occur due to threading in
// other blocks. // other blocks.
if (getKnownConstant(Condition, Preference)) { if (getKnownConstant(Condition, Preference)) {
LLVM_DEBUG(dbgs() << " In block '" << BB->getName() LLVM_DEBUG(dbgs() << " In block '" << BB->getName()
<< "' folding terminator: " << *BB->getTerminator() << "' trying to fold terminator: " << *BB->getTerminator()
<< '\n'); << '\n');
if (ConstantFoldTerminator(BB, true, TLI, DTU)) {
++NumFolds; ++NumFolds;
ConstantFoldTerminator(BB, true, nullptr, DTU); LLVM_DEBUG(dbgs() << " In block '" << BB->getName()
<< "' folded to new terminator: "
<< *BB->getTerminator() << '\n');
return true; return true;
} }
return false;
}
Instruction *CondInst = dyn_cast<Instruction>(Condition); Instruction *CondInst = dyn_cast<Instruction>(Condition);
// All the rest of our checks depend on the condition being an instruction. // All the rest of our checks depend on the condition being an instruction.
if (!CondInst) { if (!CondInst) {
// FIXME: Unify this with code below. // FIXME: Unify this with code below.
if (ProcessThreadableEdges(Condition, BB, Preference, Terminator)) if (ProcessThreadableEdges(Condition, BB, Preference, Terminator))
return true; return true;
▲ Show 20 Lines • Show All 1,617 Lines • Show Last 20 Lines

llvm/test/Transforms/JumpThreading/pr15851_hang.ll

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

llvm/test/Transforms/JumpThreading/pr42085-loopheader-detection.ll

  • This file was added.
; RUN: opt -S < %s -jump-threading | FileCheck %s
; PR42085: Do not thread any code in this example.
define i32 @test(i1 %ARG1, i1 %ARG2) {
; CHECK-NOT: {{.+}}.thread:
entry:
br label %pre_head
pre_head:
%tmp = phi i32 [ 0, %entry ], [ %tmp10, %body1 ]
%tmp3 = phi i32 [ 0, %entry ], [ %tmp11, %body1 ]
%tmp4 = phi i32 [ 0, %entry ], [ %tmp11, %body1 ]
br label %head1
head1:
br i1 %ARG1, label %exit, label %head2
head2:
br i1 false, label %head3, label %body2
head3:
%tmp8 = add i32 %tmp3, 1
br label %body1
body1:
%tmp10 = phi i32 [ %tmp, %head3 ], [ %tmp16, %latch2 ]
%tmp11 = phi i32 [ %tmp8, %head3 ], [ %tmp16, %latch2 ]
%tmp12 = icmp sgt i32 %tmp11, 1
br i1 %tmp12, label %body2, label %pre_head
body2:
%tmp14 = phi i32 [ %tmp10, %body1 ], [ %tmp, %head2 ]
%tmp15 = phi i32 [ %tmp11, %body1 ], [ %tmp3, %head2 ]
%tmp16 = add i32 %tmp14, 1
br i1 %ARG2, label %exit, label %latch1
latch1:
%tmp18 = icmp sgt i32 %tmp16, 2
br i1 %tmp18, label %exit, label %latch2
latch2:
br label %body1
exit:
%rc = phi i32 [ %tmp15, %body2 ], [ %tmp15, %latch1 ], [ -1, %head1 ]
ret i32 %rc
}

llvm/test/Transforms/JumpThreading/removed-use.ll

; RUN: opt -S < %s -jump-threading | FileCheck %s ; RUN: opt -S < %s -jump-threading | FileCheck %s
; CHECK-LABEL: @foo ; CHECK-LABEL: @foo
; CHECK: entry:
; CHECK-NEXT: br label %bb6
; CHECK: bb6: ; CHECK: bb6:
; CHECK-NEXT: ret void ; CHECK-NEXT: ret void
; CHECK: bb3:
; CHECK: br label %bb3
define void @foo() { define void @foo() {
entry: entry:
br i1 true, label %bb6, label %bb3 br i1 true, label %bb6, label %bb3
bb3: bb3:
%x0 = phi i32 [ undef, %entry ], [ %x1, %bb5 ] %x0 = phi i32 [ undef, %entry ], [ %x1, %bb5 ]
%y = and i64 undef, 1 %y = and i64 undef, 1
%p = icmp ne i64 %y, 0 %p = icmp ne i64 %y, 0
Show All 40 Lines

llvm/test/Transforms/JumpThreading/select.ll

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