[GVN] Restrict equality propagation for pointers

[nikic]

This looks okay on the surface, but this needs at least a spot check of llvm-test-suite IR diffs to get an idea of how much this affects codegen. If there are no substantial regressions, let's go with it. Otherwise we may need to think harder about how we can mitigate regressions.

The one case I'm probably worried about most are checks of the form %p == null, where replacing %p with null is not generally legal because it has nullary provenance. Replacing two arbitrary pointers likely isn't super important, but replacement with null might be.

Note that it *is* possible to perform the replacement for uses that are provenance-independent, in particular inside icmp instructions. Whether we need to make that distinction depends on how the fallout looks like.

[mnadeem]

In D143129#4098809, @nikic wrote:

This looks okay on the surface, but this needs at least a spot check of llvm-test-suite IR diffs to get an idea of how much this affects codegen. If there are no substantial regressions, let's go with it. Otherwise we may need to think harder about how we can mitigate regressions.

I'll try to collect some data with the getUnderlyingObject() change you suggested.

[mnadeem]

@nikic
I was looking at https://llvm.org/devmtg/2018-04/slides/Lopes-Sbirlea-Pointers,%20Alias%20and%20ModRef%20Analyses.pdf page 15, which says that replacement with null ptr is safe. So I did two runs, one where we do pointer replacement only when they have same underlying objects, and the another where we also replace pointers with null.

Here are the diffs for llvm-test-suite bitcode:
https://github.com/UsmanNadeem/vigilant-octo-journey/commit/125698f591df1f8de81ad4119b0838e135a18af8
and
https://github.com/UsmanNadeem/vigilant-octo-journey/commit/a778479334852e7f05b5a248da4473106aa986fb

here is some data:

Tests: 2432
Metric: gvn.NumGVNInstr

Program                                       gvn.NumGVNInstr
                                              base            sameunderlying-and-nullptr sameunderlying diff
MultiSource/Benchmarks/Olden/tsp/tsp            35.00           21.00                      21.00        66.7%
MultiSourc...s/Prolangs-C++/objects/objects     16.00           16.00                      14.00        14.3%
MultiSourc...nchmarks/tramp3d-v4/tramp3d-v4   7857.00         6964.00                    6936.00        13.3%
MultiSource/Benchmarks/McCat/09-vor/vor         59.00           55.00                      54.00         9.3%
MicroBench...CALS/SubsetBRawLoops/lcalsBRaw   1267.00         1363.00                    1324.00         7.6%
MicroBench...ubsetBLambdaLoops/lcalsBLambda   1270.00         1366.00                    1327.00         7.6%
MicroBench...ubsetALambdaLoops/lcalsALambda   1350.00         1446.00                    1407.00         7.1%
MicroBench...CALS/SubsetARawLoops/lcalsARaw   1321.00         1414.00                    1375.00         7.0%
MicroBench...ubsetCLambdaLoops/lcalsCLambda   1370.00         1466.00                    1427.00         7.0%
MicroBench...CALS/SubsetCRawLoops/lcalsCRaw   1393.00         1489.00                    1450.00         6.9%
MicroBench...teralFiltering/BilateralFilter     69.00           72.00                      72.00         4.3%
MultiSourc.../DOE-ProxyApps-C++/CLAMR/CLAMR   6769.00         7044.00                    7038.00         4.1%
MicroBench.../ImageProcessing/Dither/Dither     75.00           78.00                      78.00         4.0%
MultiSourc...ks/FreeBench/analyzer/analyzer     29.00           29.00                      30.00         3.4%
SingleSour...ks/Misc-C++/stepanov_container    577.00          558.00                     558.00         3.4%
                           Geomean difference                                                            0.5%
      gvn.NumGVNInstr
run              base sameunderlying-and-nullptr sameunderlying        diff
count  334.000000      334.000000                 334.000000     334.000000
mean   376.790419      376.655689                 375.895210     0.005643
std    1264.258518     1254.702622                1253.774169    0.039618
min    1.000000        1.000000                   1.000000       0.000000
25%    9.000000        9.000000                   9.000000       0.000000
50%    29.000000       29.000000                  29.000000      0.000000
75%    125.000000      125.000000                 125.000000     0.000000
max    10671.000000    10671.000000               10671.000000   0.666667
Tests: 2432
Metric: gvn.NumGVNLoad

Program                                       gvn.NumGVNLoad
                                              base           sameunderlying-and-nullptr sameunderlying diff
ultiSource/Applications/SPASS/SPASS           398.00         394.00                     394.00          1.0%
ultiSource/Applications/kimwitu++/kc          204.00         202.00                     202.00          1.0%
ultiSource...-ProxyApps-C++/PENNANT/PENNANT   149.00         150.00                     150.00          0.7%
icroBenchm...ubsetBLambdaLoops/lcalsBLambda   207.00         207.00                     208.00          0.5%
icroBenchm...CALS/SubsetBRawLoops/lcalsBRaw   209.00         209.00                     210.00          0.5%
icroBenchm...CALS/SubsetARawLoops/lcalsARaw   226.00         226.00                     227.00          0.4%
icroBenchm...ubsetALambdaLoops/lcalsALambda   230.00         230.00                     231.00          0.4%
icroBenchm...ubsetCLambdaLoops/lcalsCLambda   231.00         231.00                     232.00          0.4%
icroBenchm...CALS/SubsetCRawLoops/lcalsCRaw   244.00         244.00                     245.00          0.4%
ultiSource.../Applications/JM/ldecod/ldecod   646.00         645.00                     645.00          0.2%
ultiSource.../DOE-ProxyApps-C++/CLAMR/CLAMR   934.00         933.00                     933.00          0.1%
ultiSource...nchmarks/tramp3d-v4/tramp3d-v4   978.00         977.00                     977.00          0.1%
ultiSource...ring-flt/LoopRestructuring-flt     1.00           1.00                       1.00          0.0%
ultiSource...ring-dbl/LoopRestructuring-dbl     1.00           1.00                       1.00          0.0%
ultiSource...marks/Trimaran/enc-pc1/enc-pc1     2.00           2.00                       2.00          0.0%
                           Geomean difference                                                           0.0%
      gvn.NumGVNLoad
run             base sameunderlying-and-nullptr sameunderlying        diff
count  216.000000     216.000000                 216.000000     216.000000
mean   92.689815      92.652778                  92.680556      0.000265
std    283.845653     283.785744                 283.798757     0.001286
min    1.000000       1.000000                   1.000000       0.000000
25%    2.000000       2.000000                   2.000000       0.000000
50%    10.000000      10.000000                  10.000000      0.000000
75%    44.000000      44.000000                  44.000000      0.000000
max    2516.000000    2516.000000                2516.000000    0.010152
Tests: 2432
Metric: gvn.NumGVNPRE

Program                                       gvn.NumGVNPRE
                                              base          sameunderlying-and-nullptr sameunderlying diff
SingleSour.../Benchmarks/Misc-C++-EH/spirit     5.00          2.00                       2.00         150.0%
SingleSour...ks/Misc-C++/stepanov_container    22.00         19.00                      19.00          15.8%
MultiSourc...-ProxyApps-C++/PENNANT/PENNANT    12.00         11.00                      11.00           9.1%
MultiSourc...e/Applications/ClamAV/clamscan   109.00        107.00                     107.00           1.9%
MultiSourc.../DOE-ProxyApps-C++/CLAMR/CLAMR   377.00        372.00                     372.00           1.3%
Bitcode/Be...hmarks/Halide/blur/halide_blur     4.00          4.00                       4.00           0.0%
MultiSourc...s/Prolangs-C++/objects/objects     1.00          1.00                       1.00           0.0%
MultiSourc...olangs-C/unix-smail/unix-smail     8.00          8.00                       8.00           0.0%
MultiSourc...s/Prolangs-C/football/football     6.00          6.00                       6.00           0.0%
MultiSourc...s/Prolangs-C/compiler/compiler     2.00          2.00                       2.00           0.0%
MultiSourc...marks/Prolangs-C/bison/mybison    19.00         19.00                      19.00           0.0%
MultiSourc...Prolangs-C/assembler/assembler     1.00          1.00                       1.00           0.0%
MultiSourc...rolangs-C/archie-client/archie     2.00          2.00                       2.00           0.0%
MultiSourc...chmarks/Prolangs-C/agrep/agrep    17.00         17.00                      17.00           0.0%
MultiSourc...gs-C/TimberWolfMC/timberwolfmc    49.00         49.00                      49.00           0.0%
                           Geomean difference                                                           1.1%
      gvn.NumGVNPRE
run            base sameunderlying-and-nullptr sameunderlying        diff
count  111.000000    110.000000                 110.000000     111.000000
mean   20.684685     20.654545                  20.654545      0.016044
std    46.993226     46.829857                  46.829857      0.143183
min    1.000000      1.000000                   1.000000       0.000000
25%    2.000000      2.000000                   2.000000       0.000000
50%    5.000000      5.000000                   5.000000       0.000000
75%    16.000000     16.500000                  16.500000      0.000000
max    377.000000    372.000000                 372.000000     1.500000
Tests: 2432
Metric: gvn.NumGVNBlocks

Program                                       gvn.NumGVNBlocks
                                              base             sameunderlying-and-nullptr sameunderlying diff
MultiSourc...OE-ProxyApps-C++/miniFE/miniFE    69.00            68.00                      68.00          1.5%
MultiSourc...enchmarks/mafft/pairlocalalign   578.00           578.00                     578.00          0.0%
SingleSour...enchmarks/BenchmarkGame/n-body    15.00            15.00                      15.00          0.0%
SingleSour...chmarks/BenchmarkGame/fannkuch    14.00            14.00                      14.00          0.0%
SingleSour...arks/BenchmarkGame/Large/fasta     2.00             2.00                       2.00          0.0%
SingleSour...arks/Adobe-C++/stepanov_vector     4.00             4.00                       4.00          0.0%
SingleSour...Adobe-C++/stepanov_abstraction     4.00             4.00                       4.00          0.0%
SingleSour...++/simple_types_loop_invariant     2.00             2.00                       2.00          0.0%
SingleSour.../simple_types_constant_folding   126.00           126.00                     126.00          0.0%
SingleSour...nchmarks/Adobe-C++/loop_unroll     8.00             8.00                       8.00          0.0%
SingleSour...arks/Adobe-C++/functionobjects     3.00             3.00                       3.00          0.0%
MultiSourc...++11/frame_layout/frame_layout     2.00             2.00                       2.00          0.0%
MultiSourc...nchmarks/tramp3d-v4/tramp3d-v4   503.00           503.00                     503.00          0.0%
MultiSource/Benchmarks/nbench/nbench           48.00            48.00                      48.00          0.0%
MultiSourc...nch/mpeg2/mpeg2dec/mpeg2decode    53.00            53.00                      53.00          0.0%
                           Geomean difference                                                             0.0%
      gvn.NumGVNBlocks
run               base sameunderlying-and-nullptr sameunderlying        diff
count  291.000000       291.000000                 291.000000     291.000000
mean   47.079038        47.075601                  47.075601      0.000051
std    130.828991       130.828426                 130.828426     0.000862
min    1.000000         1.000000                   1.000000       0.000000
25%    2.000000         2.000000                   2.000000       0.000000
50%    8.000000         8.000000                   8.000000       0.000000
75%    50.000000        50.000000                  50.000000      0.000000
max    1476.000000      1476.000000                1476.000000    0.014706
Tests: 2432
Metric: gvn.NumGVNSimpl

Program                                       gvn.NumGVNSimpl
                                              base            sameunderlying-and-nullptr sameunderlying diff
MultiSourc...s/Prolangs-C++/objects/objects      4.00            4.00                       2.00        100.0%
MultiSourc...nchmarks/tramp3d-v4/tramp3d-v4   3739.00         3002.00                    2984.00         25.3%
MicroBench.../ImageProcessing/Dither/Dither     34.00           39.00                      39.00         14.7%
MicroBench...ubsetBLambdaLoops/lcalsBLambda    415.00          474.00                     434.00         14.2%
MicroBench...CALS/SubsetBRawLoops/lcalsBRaw    415.00          474.00                     434.00         14.2%
MicroBench...CALS/SubsetCRawLoops/lcalsCRaw    421.00          480.00                     440.00         14.0%
MicroBench...ubsetCLambdaLoops/lcalsCLambda    426.00          485.00                     445.00         13.8%
MicroBench...ubsetALambdaLoops/lcalsALambda    430.00          489.00                     449.00         13.7%
MicroBench...CALS/SubsetARawLoops/lcalsARaw    412.00          468.00                     428.00         13.6%
MicroBench...teralFiltering/BilateralFilter     38.00           43.00                      43.00         13.2%
MultiSource/Applications/kimwitu++/kc          702.00          786.00                     786.00         12.0%
MultiSourc.../DOE-ProxyApps-C++/CLAMR/CLAMR   2460.00         2740.00                    2734.00         11.4%
SingleSource/Benchmarks/Misc-C++/bigfib         53.00           59.00                      59.00         11.3%
MultiSource/Benchmarks/McCat/09-vor/vor         10.00           10.00                       9.00         11.1%
MultiSourc...ks/FreeBench/analyzer/analyzer     15.00           15.00                      16.00          6.7%
                           Geomean difference                                                             0.9%
      gvn.NumGVNSimpl
run              base sameunderlying-and-nullptr sameunderlying        diff
count  311.000000      311.000000                 311.000000     311.000000
mean   155.244373      155.379421                 154.565916     0.010764
std    511.943543      502.146410                 501.382767     0.063660
min    1.000000        1.000000                   1.000000       0.000000
25%    6.000000        6.000000                   6.000000       0.000000
50%    17.000000       17.000000                  17.000000      0.000000
75%    59.000000       60.500000                  60.500000      0.000000
max    4872.000000     4871.000000                4871.000000    1.000000
Tests: 2432
Metric: gvn.NumGVNEqProp

Program                                       gvn.NumGVNEqProp
                                              base             sameunderlying-and-nullptr sameunderlying diff
MultiSourc...OE-ProxyApps-C++/miniFE/miniFE    66.00             8.00                       4.00         1550.0%
SingleSour.../Benchmarks/Misc-C++-EH/spirit    49.00             3.00                       3.00         1533.3%
SingleSour...ks/Misc-C++/stepanov_container   107.00            12.00                      11.00          872.7%
SingleSource/Benchmarks/Misc-C++/bigfib        18.00             2.00                       2.00          800.0%
MultiSourc.../DOE-ProxyApps-C++/HPCCG/HPCCG     6.00             1.00                       1.00          500.0%
MultiSourc.../Benchmarks/McCat/15-trie/trie     6.00             6.00                       1.00          500.0%
MultiSourc...hmarks/MallocBench/cfrac/cfrac     6.00             6.00                       1.00          500.0%
MultiSourc.../DOE-ProxyApps-C++/CLAMR/CLAMR   874.00           175.00                     169.00          417.2%
MultiSourc...nchmarks/tramp3d-v4/tramp3d-v4   222.00            75.00                      43.00          416.3%
MultiSource/Benchmarks/McCat/09-vor/vor        14.00             3.00                                     366.7%
MultiSource/Applications/kimwitu++/kc         293.00            72.00                      63.00          365.1%
MultiSourc...-ProxyApps-C++/PENNANT/PENNANT    55.00            12.00                      12.00          358.3%
MicroBench...ubsetCLambdaLoops/lcalsCLambda   122.00            70.00                      37.00          229.7%
MicroBench...ubsetBLambdaLoops/lcalsBLambda   122.00            70.00                      37.00          229.7%
MicroBench...CALS/SubsetBRawLoops/lcalsBRaw   122.00            70.00                      37.00          229.7%
                           Geomean difference                                                              37.7%
      gvn.NumGVNEqProp
run               base sameunderlying-and-nullptr sameunderlying        diff
count  147.000000       133.000000                 126.000000     147.000000
mean   44.442177        33.511278                  30.103175      0.809993
std    104.076048       69.462614                  60.728356      2.227728
min    1.000000         1.000000                   1.000000       0.000000
25%    2.000000         2.000000                   2.000000       0.000000
50%    9.000000         9.000000                   8.000000       0.000000
75%    36.500000        34.000000                  34.000000      0.431444
max    874.000000       509.000000                 373.000000     15.500000
Tests: 2432
Metric: gvn.NumPRELoad

Program                                       gvn.NumPRELoad
                                              base           sameunderlying-and-nullptr sameunderlying diff
ultiSource/Benchmarks/Olden/tsp/tsp             11.00           7.00                       7.00        57.1%
ultiSource/Benchmarks/McCat/09-vor/vor          10.00           8.00                       8.00        25.0%
ultiSource...nchmarks/tramp3d-v4/tramp3d-v4   1133.00        1061.00                    1061.00         6.8%
ultiSource/Applications/d/make_dparser         191.00         192.00                     192.00         0.5%
ultiSource...sumer-typeset/consumer-typeset    727.00         726.00                     726.00         0.1%
ultiSource...VC/Expansion-dbl/Expansion-dbl      6.00           6.00                       6.00         0.0%
ultiSource/Benchmarks/Ptrdist/ft/ft              3.00           3.00                       3.00         0.0%
ultiSource/Benchmarks/Ptrdist/ks/ks              3.00           3.00                       3.00         0.0%
ultiSource...Benchmarks/Ptrdist/yacr2/yacr2     35.00          35.00                      35.00         0.0%
ultiSource...Benchmarks/SciMark2-C/scimark2     11.00          11.00                      11.00         0.0%
ultiSource...ontrolFlow-dbl/ControlFlow-dbl      7.00           7.00                       7.00         0.0%
ultiSource...ontrolFlow-flt/ControlFlow-flt      7.00           7.00                       7.00         0.0%
ultiSource...lds-dbl/CrossingThresholds-dbl      1.00           1.00                       1.00         0.0%
ultiSource...lds-flt/CrossingThresholds-flt      1.00           1.00                       1.00         0.0%
icroBenchmarks/Builtins/Int128/Builtins         12.00          12.00                      12.00         0.0%
                           Geomean difference                                                           0.4%
      gvn.NumPRELoad
run             base sameunderlying-and-nullptr sameunderlying        diff
count  194.000000     194.000000                 194.000000     194.000000
mean   74.097938      73.695876                  73.695876      0.004618
std    186.856476     184.798491                 184.798491     0.044925
min    1.000000       1.000000                   1.000000       0.000000
25%    2.000000       2.000000                   2.000000       0.000000
50%    7.500000       7.000000                   7.000000       0.000000
75%    42.000000      42.000000                  42.000000      0.000000
max    1133.000000    1061.000000                1061.000000    0.571429
Tests: 2432
Metric: gvn.NumPRELoad

Program                                       gvn.NumPRELoad
                                              base           sameunderlying-and-nullptr sameunderlying diff
ultiSource/Benchmarks/Olden/tsp/tsp             11.00           7.00                       7.00        57.1%
ultiSource/Benchmarks/McCat/09-vor/vor          10.00           8.00                       8.00        25.0%
ultiSource...nchmarks/tramp3d-v4/tramp3d-v4   1133.00        1061.00                    1061.00         6.8%
ultiSource/Applications/d/make_dparser         191.00         192.00                     192.00         0.5%
ultiSource...sumer-typeset/consumer-typeset    727.00         726.00                     726.00         0.1%
ultiSource...VC/Expansion-dbl/Expansion-dbl      6.00           6.00                       6.00         0.0%
ultiSource/Benchmarks/Ptrdist/ft/ft              3.00           3.00                       3.00         0.0%
ultiSource/Benchmarks/Ptrdist/ks/ks              3.00           3.00                       3.00         0.0%
ultiSource...Benchmarks/Ptrdist/yacr2/yacr2     35.00          35.00                      35.00         0.0%
ultiSource...Benchmarks/SciMark2-C/scimark2     11.00          11.00                      11.00         0.0%
ultiSource...ontrolFlow-dbl/ControlFlow-dbl      7.00           7.00                       7.00         0.0%
ultiSource...ontrolFlow-flt/ControlFlow-flt      7.00           7.00                       7.00         0.0%
ultiSource...lds-dbl/CrossingThresholds-dbl      1.00           1.00                       1.00         0.0%
ultiSource...lds-flt/CrossingThresholds-flt      1.00           1.00                       1.00         0.0%
icroBenchmarks/Builtins/Int128/Builtins         12.00          12.00                      12.00         0.0%
                           Geomean difference                                                           0.4%
      gvn.NumPRELoad
run             base sameunderlying-and-nullptr sameunderlying        diff
count  194.000000     194.000000                 194.000000     194.000000
mean   74.097938      73.695876                  73.695876      0.004618
std    186.856476     184.798491                 184.798491     0.044925
min    1.000000       1.000000                   1.000000       0.000000
25%    2.000000       2.000000                   2.000000       0.000000
50%    7.500000       7.000000                   7.000000       0.000000
75%    42.000000      42.000000                  42.000000      0.000000
max    1133.000000    1061.000000                1061.000000    0.571429
Tests: 2432
Metric: gvn.NumPRELoopLoad

Program                                       gvn.NumPRELoopLoad
                                              base               sameunderlying-and-nullptr sameunderlying diff
MicroBench...ubsetALambdaLoops/lcalsALambda     1.00               1.00                       1.00          0.0%
MultiSourc...marks/Prolangs-C++/simul/simul     1.00               1.00                       1.00          0.0%
MultiSourc...chmarks/Prolangs-C/agrep/agrep     4.00               4.00                       4.00          0.0%
MultiSourc...marks/Prolangs-C/bison/mybison    17.00              17.00                      17.00          0.0%
MultiSourc...chmarks/Prolangs-C/cdecl/cdecl     1.00               1.00                       1.00          0.0%
MultiSourc...s/Prolangs-C/compiler/compiler     1.00               1.00                       1.00          0.0%
MultiSourc...s/Prolangs-C/football/football     1.00               1.00                       1.00          0.0%
MultiSourc...Prolangs-C/simulator/simulator     1.00               1.00                       1.00          0.0%
MultiSourc...hmarks/Ptrdist/anagram/anagram     1.00               1.00                       1.00          0.0%
MultiSourc...Benchmarks/Ptrdist/yacr2/yacr2     4.00               4.00                       4.00          0.0%
MultiSourc...enchmarks/mafft/pairlocalalign     5.00               5.00                       5.00          0.0%
MultiSourc...iabench/g721/g721encode/encode     1.00               1.00                       1.00          0.0%
MultiSourc...nch/mpeg2/mpeg2dec/mpeg2decode     1.00               1.00                       1.00          0.0%
MultiSource/Benchmarks/nbench/nbench            1.00               1.00                       1.00          0.0%
SingleSour...nchmarks/Adobe-C++/loop_unroll   130.00             130.00                     130.00          0.0%
                           Geomean difference                                                               0.0%
      gvn.NumPRELoopLoad
run                 base sameunderlying-and-nullptr sameunderlying  diff
count  45.000000          45.000000                  45.000000      45.0
mean   15.711111          15.711111                  15.711111      0.0
std    37.860163          37.860163                  37.860163      0.0
min    1.000000           1.000000                   1.000000       0.0
25%    1.000000           1.000000                   1.000000       0.0
50%    1.000000           1.000000                   1.000000       0.0
75%    6.000000           6.000000                   6.000000       0.0
max    168.000000         168.000000                 168.000000     0.0

[aqjune]

The one case I'm probably worried about most are checks of the form %p == null, where replacing %p with null is not generally legal because it has nullary provenance. Replacing two arbitrary pointers likely isn't super important, but replacement with null might be.

I was looking at https://llvm.org/devmtg/2018-04/slides/Lopes-Sbirlea-Pointers,%20Alias%20and%20ModRef%20Analyses.pdf page 15, which says that replacement with null ptr is safe. So I did two runs, one where we do pointer replacement only when they have same underlying objects, and the another where we also replace pointers with null.

The validity of this transformation depends on the definition of a null pointer which is in a gray area.
The slide is based on the following memory model: (1) we can safely replace p with inttoptr (ptrtoint p). (2) null pointer is equivalent to inttoptr 0 (or inttoptr c for some special, fixed constant).
In this model, replacing p with null is fine.

I think we can talk about this in the LLVM discourse group. The numbers look informative and people would like to see them & suggest their ideas.

[nikic]

Thanks a lot for the detailed analysis!

In D143129#4117091, @mnadeem wrote:

@nikic
I was looking at https://llvm.org/devmtg/2018-04/slides/Lopes-Sbirlea-Pointers,%20Alias%20and%20ModRef%20Analyses.pdf page 15, which says that replacement with null ptr is safe. So I did two runs, one where we do pointer replacement only when they have same underlying objects, and the another where we also replace pointers with null.

I believe the currently accepted interpretation of null in LLVM is that it has nullary provenance. For example, we rely on this here: https://github.com/llvm/llvm-project/blob/46cdf7f0991280a3601a777a80fbc460196fb033/llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp#L1064 This folds load (gep null, x) to unreachable. Of course, we also fold inttoptr 0 to null, which is inconsistent with that interpretation.

As @nlopes suggested, this should probably be discussed on discourse. Giving null universal provenance seems wrong from a principled perspective, but it may well be the most pragmatic option. (I don't think we rely on nullary provenance in many places, not sure there are any beyond the one I shared, and for that one we can probably recover most practically useful cases with an inbounds requirement.)

Here are the diffs for llvm-test-suite bitcode:
https://github.com/UsmanNadeem/vigilant-octo-journey/commit/125698f591df1f8de81ad4119b0838e135a18af8
and
https://github.com/UsmanNadeem/vigilant-octo-journey/commit/a778479334852e7f05b5a248da4473106aa986fb

Oh, that's a nice way to analyze differences. How did you produce the output?

I looked through the diffs a bit, and while most of them are immaterial diffs (just replacing one pointer with another without further simplification), it looks like there are also many genuine regressions in optimization quality. The first one is https://github.com/UsmanNadeem/vigilant-octo-journey/commit/a778479334852e7f05b5a248da4473106aa986fb#diff-429f0aa0b366d469c8f0fe4aaded9e87e83898118f192b6741caf4100e4e7792. I think the logic here is that we have a icmp eq ptr %link.112821, %48 condition on the edge, and then check

%313 = phi ptr [ %.pre12846, %for.end11932.loopexit ], [ %link.112821, %if.end11920 ]
%cmp11936 = icmp ne ptr %313, %48

so if we replace %link.112821 with %48 here, we see that the condition is always true when coming from %if.end11920 and that allows us to thread the branch. This is a legal optimization, because icmp is provenance independent.

From a quick glance, the same basic pattern also occurs in many other IR diffs, so it seems like this is something important to preserve, though I'm not entirely sure what the best way to only propagating the equality in provenance-independent contexts would be (doing a recursive user walk seems rather iffy, but I don't have a better idea).

[mnadeem]

In D143129#4125424, @nikic wrote:

Here are the diffs for llvm-test-suite bitcode:
https://github.com/UsmanNadeem/vigilant-octo-journey/commit/125698f591df1f8de81ad4119b0838e135a18af8
and
https://github.com/UsmanNadeem/vigilant-octo-journey/commit/a778479334852e7f05b5a248da4473106aa986fb

...
Oh, that's a nice way to analyze differences. How did you produce the output?
...

I compiled the test suite using -O3 with the base toolchain and made a list of files where GVN did pointer replacements by adding some debug output in that function. Copied the compile commands for those files from the make output and then used those to dump the IR for the base toolchain and toolchains with various patches.

Discourse link: https://discourse.llvm.org/t/restricting-equality-propagation-for-pointers-whats-the-best-way-how-to-deal-with-regressions/68619

[aqjune]

llvm/lib/Transforms/Scalar/GVN.cpp

2563

As @nikic suggested in the Discourse thread, do you want to fix patchAndReplaceAllUsesWith so that if it is a pointer it allows replacing uses at instructions that are unaware of provenance? I wonder how things will go.
Actually, we can count different assembly files rather than LLVM IR. If it is less than 10, then we can investigate the files more deeply. Actually, if there are diffs even after allowing this, I think it might be miscompilation bugs.

llvm/test/Transforms/GVN/condprop.ll

591

Nit: could you avoid using br i1 undef? This is UB and there is this side project: https://llvm.org/OpenProjects.html#remove_ub_tests
You can add a function argument for this branch condition and use it instead.

[mnadeem]

• Added a new method replaceDominatedUsesWithIf() that takes a callback.
• Updated canReplacePointersIfEqual() to return true for the following:
  • Uses in ICmpInst and PtrToIntInst
  • Replacements with null
  • When underlying objects are the same
• Update tests.
• New LLVM test suite bitcode diff using O3 (assembly files were more difficult to analyze): https://github.com/UsmanNadeem/vigilant-octo-journey/commit/65a770a65eca4ed2cb37f6ff6a36ec6193fe8b73

Not sure about the changes in the assume-equal.ll test.

[mnadeem]

llvm/lib/Transforms/Scalar/GVN.cpp

2563

Maybe in a separate patch? I tried doing assembly files but the changes were more extensive due to register assignment changes.

[mnadeem]

clang format

[aqjune]

Thanks! Yes, indeed there are still many files having diffs. But the number shrunk to ~1/5, which seems nice!

I looked at the diffs, and I could see a few replacements in the past that seem buggy...
In 82.ll:

  %call103 = tail call ptr @encodingLine(ptr noundef %messageIn) #17
  %22 = load ptr, ptr %t_next, align 8, !tbaa !30
  %cmp105 = icmp eq ptr %call103, %22
  br i1 %cmp105, label %if.then107, label %do.cond

if.then107:
  %23 = load ptr, ptr %22, align 8, !tbaa !28 // Replacing %22 with %call103 is illegal

encodingLine does not have a function body as well as meaningful attributes, so it can return any pointer. This patch fixes the bug, which is good.

In 73.ll: I think we can make an improvement.

  %call.i = tail call noalias dereferenceable_or_null(64) ptr @malloc(i64 noundef 64) #35
  %tobool.not = icmp eq ptr %call.i, null
  ...

cond.end.i.i: // At this point %call.i isn't null.
  %5 = load ptr, ptr %arrayidx6.i.i, align 8, !tbaa !5
  %cmp.i.i = icmp eq ptr %5, %call.i
  br i1 %cmp.i.i, label %_Z15yy_flush_bufferP15yy_buffer_state.exit.thread.i,....

_Z15yy_flush_bufferP15yy_buffer_state.exit.thread.i: ; preds = %cond.end.i.i
  %yy_n_chars.i.i.i = getelementptr inbounds %struct.yy_buffer_state, ptr %5, i64 0, i32 4 // <- This can be replaced with 'gep inbounds %call.i, 0, 4'.
  %6 = load i32, ptr %yy_n_chars.i.i.i, align 4, !tbaa !13

Replacing p at load (gep inbounds p, ofs) with q at is fine if (1) q points to the beginning address of a live object (e.g. unfreed malloc), and (2) ofs is non-negative.
To guarantee liveness (1), you will probably need to check whether q hasn't been escaped, because an unknown function call may deallocate it.
My reasoning is like this:

• If p was a freed (dead) pointer, load would have already been UB, so q can be anything.
• If p was an unfreed (live) pointer, q must also be a live object because otherwise the replacement will make load introduce UB. If p and q are both live:
  • If p and q pointed to the same object: replacement is trivially correct
  • If p and q pointed to different objects: since p == q was true, the two different objects must be adjacent in their memory layout, and one of q or p must point to the beginning address of a live object. 73.ll corresponds to q pointing to 'the beginning address of a live object' case.

I hope I didn't miss something obvious in 73.ll & this replacement helps.

llvm/lib/Analysis/Loads.cpp

699

Could you elaborate a bit about isa<PHINode>(User) condition?
I think that in the following case replacing %p with %q should fail, but this condition seems to allow it:

BB1:
  %phi1 = phi [%p, <pred>], ..
  br BB2
BB2:
  %phi2 = phi [%phi1, <BB1>], ..
  store i32 0, ptr %phi2

[mnadeem]

llvm/lib/Analysis/Loads.cpp

699

I was trying to handle something like the example below. I guess I didn't think about the cases where the second phi's use could have illegal replacements.

Not sure what the best way to handle this would be.

BB1:
  %phi1 = phi [%p, <pred>], ..
  %cond = icmp eq ptr %phi1 , %q    <<---- This case
  br BB2
BB2:
  %phi2 = phi [%phi1, <BB1>], ..
  store i32 0, ptr %phi2

[mnadeem]

Fix the check for PHI nodes and add some reduced tests relevant to the case.

[aqjune]

Hi, I am currently occupied with something else. I will be back by today and continue reviewing this.

[aqjune]

Regarding the updated experimental results, I think people might have thoughts about them. I will leave a comment there.

llvm/include/llvm/Transforms/Utils/Local.h

416

You'll want to use clang-format. https://llvm.org/docs/Contributing.html#format-patches

llvm/lib/Analysis/Loads.cpp

699

I think dealing with this case is tricky.
To replace %p in the operand of %phi1, we should copy it as follows:

BB1:
  %phi1 = phi [%p, <pred>], ..
  %phi1_copy = phi [%p, <pred>], .. <<-- we can replace %p with %q here
  %cond = icmp eq ptr %phi1_copy , %q    <<---- ... because %phi1_copy's only use is this icmp.
  br BB2
BB2:
  %phi2 = phi [%phi1, <BB1>], ..
  store i32 0, ptr %phi2

[arichardson]

llvm/test/Transforms/GVN/assume-equal.ll

56

Instead of the negative checks (which may pass for other reasons) I'd use a positive one with the new output.

[nikic]

Okay, the test diffs look much better now. Some interesting remaining cases:

• 10.ll: This is another jump threading failure. The problem here is that the phi nodes are used in icmps, but not *only* in icmps, so we can't simply replace the operand there. I'm not sure what to do about this one. We could obviously duplicate the phi node and replace its non-provenance uses, but that's not going to be profitable in general. Possibly there is some specialized jump threading support one could add for this, but this is technically tricky, especially as threading can't use the dominator tree. LVI currently only tracks equality to constants.
• 101.ll (sink) and 103.ll (hoist): Here we have something like if (p == q) { store v, p } else { store v, q } where previously store v, q could be sunk/hoisted out of it. This isn't legal anymore. This is probably unrecoverable at the IR level, but maybe the machine layer handles it (I didn't check).

Overall I'd be willing to try landing this and seeing whether any significant performance issues arise.

llvm/include/llvm/Transforms/Utils/Local.h

416

The callback doesn't need From and To -- if it needs them, it can capture them from context. Instead of User * we should pass Use &, which is more general. (E.g. if some operands are provenance-dependent, but others aren't -- I have future ptr_provenance support in mind here).

llvm/lib/Analysis/Loads.cpp

706

I think we should split this up into two APIs: One should stay as previous any just answer the question "can this always be replaced?" and the other should only take a Use and answer the question "is this provenance-independent?" We don't need to perform some of these checks for every single use, and some of the things (e.g. addition to leader table) can only be done if all uses can be replaced.

llvm/lib/Transforms/Scalar/GVN.cpp

2325

I don't think we can do this unless it's legal to unconditionally replace the pointers.

[aqjune]

+1 for landing this patch if there is no significant input from the discourse thread by next Monday (Mar. 13).

[mnadeem]

• Guard addToLeaderTable with the pointer replacement check.

• Create two APIs
  • bool canReplacePointersIfEqual(const Value *From, const Value *To);
  • bool canReplacePointersIfEqualInUse(const Use &U, const Value *To);

• For the callback in replaceDominatedUsesWithIf I changed the from argument with a Use. But I still need the to value in the callback.

• Clang format

• Update tests

[mnadeem]

llvm/include/llvm/Transforms/Utils/Local.h

416

You'll want to use clang-format. https://llvm.org/docs/Contributing.html#format-patches

It is already clang-formatted, not sure why the formatting is now different.
git diff -U0 --relative HEAD~ | clang/tools/clang-format/clang-format-diff.py -p1 -sort-includes -i

416

The callback doesn't need From and To -- if it needs them, it can capture them from context. Instead of User * we should pass Use &, which is more general. (E.g. if some operands are provenance-dependent, but others aren't -- I have future ptr_provenance support in mind here).

I replaced From with Use &, but I still needed the To param. Can you look at loads.cpp to see if it makes sense to use both the use and the to value?

llvm/lib/Analysis/Loads.cpp

699

I fixed the code and added a test case in a previous revision. I think fixing this will need more extensive changes than can be easily done in replaceDominatedUsesWith

706

I created an isPointerUseReplacable(const Use &U but made it a static function which can be exposed in the future.
I have also taken some of the checks out of the recursive function.

llvm/lib/Transforms/Scalar/GVN.cpp

2563

I have guarded addToLeaderTable with the check so IIUC this is not needed any more?

[mnadeem]

ping

[nikic]

llvm/lib/Analysis/Loads.cpp

704

This API should not contain any Use-based reasoning, it should be just the isPointerAlwaysReplacable() part. The leader table replacement isn't valid even if all uses of this particular pointer are fine, as we may end up performing an indirect replacement on additional users.

llvm/test/Transforms/GVN/assume-equal.ll

24

Hm, these regressions look problematic. These assumptions are emitted by clang in EmitVTableAssumptionLoad() specifically to allow these replacements. This is going to lose devirtualization support for these cases.

We probably need to carve out another exception for this case. Possibly we should just keep the existing exception for constants (i.e. allow if they are deferencable) to make this work.

[mnadeem]

Added an exception for constant dereferenceable pointers and changed canReplacePointersIfEqual to not look at the Uses.

To get the dereferenceability of the pointer, Instead of passing the DL around I am trying to get it from the value, let me know if it looks okay.

[mnadeem]

ping

[mnadeem]

ping

[mnadeem]

@nikic Please feel free to take over/commandeer this revision.

[mnadeem]

ping

llvm/include/llvm/Analysis/Loads.h

 ///
 /// \returns The found value, or nullptr if no value is found.
 Value *findAvailablePtrLoadStore(const MemoryLocation &Loc, Type *AccessTy,
                                  bool AtLeastAtomic, BasicBlock *ScanBB,
                                  BasicBlock::iterator &ScanFrom,
                                  unsigned MaxInstsToScan, AAResults *AA,
                                  bool *IsLoadCSE, unsigned *NumScanedInst);
 
-/// Returns true if a pointer value \p A can be replace with another pointer
-/// value \B if they are deemed equal through some means (e.g. information from
+/// Returns true if a pointer value \p From can be replaced with another pointer
+/// value \To if they are deemed equal through some means (e.g. information from
 /// conditions).
-/// NOTE: the current implementations is incomplete and unsound. It does not
-/// reject all invalid cases yet, but will be made stricter in the future. In
-/// particular this means returning true means unknown if replacement is safe.
-bool canReplacePointersIfEqual(Value *A, Value *B, const DataLayout &DL,
-                               Instruction *CtxI);
+/// NOTE: The current implementation allows replacement in Icmp and PtrToInt
+/// instructions, as well as when we are replacing with a null pointer.
+/// Additionally it also allows replacement of pointers when both pointers have
+/// the same underlying object.
+bool canReplacePointersIfEqual(const Value *From, const Value *To,
+                               const User *U);
 }
 
 #endif

llvm/include/llvm/Transforms/Utils/Local.h

 /// Replace each use of 'From' with 'To' if that use is dominated by
 /// the given edge.  Returns the number of replacements made.
 unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT,
                                   const BasicBlockEdge &Edge);
 /// Replace each use of 'From' with 'To' if that use is dominated by
 /// the end of the given BasicBlock. Returns the number of replacements made.
 unsigned replaceDominatedUsesWith(Value *From, Value *To, DominatorTree &DT,
                                   const BasicBlock *BB);
+/// Replace each use of 'From' with 'To' if that use is dominated by
+/// the given edge and the callback ShouldReplace returns true. Returns the
+/// number of replacements made.
+unsigned replaceDominatedUsesWithIf(
+    Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Edge,
+    function_ref<bool(const Value *From, const Value *To, const User *U)>
+        ShouldReplace);
+/// Replace each use of 'From' with 'To' if that use is dominated by
+/// the end of the given BasicBlock and the callback ShouldReplace returns true.
+/// Returns the number of replacements made.
+unsigned replaceDominatedUsesWithIf(
+    Value *From, Value *To, DominatorTree &DT, const BasicBlock *BB,
+    function_ref<bool(const Value *From, const Value *To, const User *U)>
+        ShouldReplace);
 
 /// Return true if this call calls a gc leaf function.
 ///
 /// A leaf function is a function that does not safepoint the thread during its
 /// execution.  During a call or invoke to such a function, the callers stack
 /// does not have to be made parseable.
 ///
 /// Most passes can and should ignore this information, and it is only used

llvm/lib/Analysis/Loads.cpp

if (Available) {
     for (Instruction *Inst : MustNotAliasInsts)
       if (isModSet(AA.getModRefInfo(Inst, Loc)))
         return nullptr;
   }
 
   return Available;
 }
 
-bool llvm::canReplacePointersIfEqual(Value *A, Value *B, const DataLayout &DL,
-                                     Instruction *CtxI) {
-  Type *Ty = A->getType();
-  assert(Ty == B->getType() && Ty->isPointerTy() &&
-         "values must have matching pointer types");
-
-  // NOTE: The checks in the function are incomplete and currently miss illegal
-  // cases! The current implementation is a starting point and the
-  // implementation should be made stricter over time.
-  if (auto *C = dyn_cast<Constant>(B)) {
-    // Do not allow replacing a pointer with a constant pointer, unless it is
-    // either null or at least one byte is dereferenceable.
-    APInt OneByte(DL.getPointerTypeSizeInBits(Ty), 1);
-    return C->isNullValue() ||
-           isDereferenceableAndAlignedPointer(B, Align(1), OneByte, DL, CtxI);
-  }
+static bool canReplacePointersRecursive(const Value *From, const Value *To,
+                                        const User *U, int MaxLookup = 6) {
+  if (MaxLookup == 0)
+    return false;
+
+  if (isa<ConstantPointerNull>(To))
+    return true;
+  if (isa<ICmpInst>(U))
+    return true;
+  if (isa<PtrToIntInst>(U))
+    return true;
+  if (isa<PHINode, SelectInst>(U) && all_of(U->users(), [&](const User *User) {
+        return canReplacePointersRecursive(U, To, User, MaxLookup - 1);
+      }))
+    return true;
+  return getUnderlyingObject(From) == getUnderlyingObject(To);
 
+bool llvm::canReplacePointersIfEqual(const Value *From, const Value *To,
+                                     const User *U) {
+  // Not a pointer, just return true.
+  if (!From->getType()->isPointerTy())
     return true;
+  assert(From->getType() == To->getType() && "values must have matching types");
+  return canReplacePointersRecursive(From, To, U);
 }

llvm/lib/Transforms/Scalar/GVN.cpp

 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumeBundleQueries.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionPrecedenceTracking.h"
 #include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/PHITransAddr.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
while (!Worklist.empty()) {
     // the invariant that instructions only occur in the leader table for their
     // own value number (this is used by removeFromLeaderTable), do not do this
     // if RHS is an instruction (if an instruction in the scope is morphed into
     // LHS then it will be turned into RHS by the next GVN iteration anyway, so
     // using the leader table is about compiling faster, not optimizing better).
     // The leader table only tracks basic blocks, not edges. Only add to if we
     // have the simple case where the edge dominates the end.
     if (RootDominatesEnd && !isa<Instruction>(RHS))
       addToLeaderTable(LVN, RHS, Root.getEnd());
 
     // Replace all occurrences of 'LHS' with 'RHS' everywhere in the scope.  As
     // LHS always has at least one use that is not dominated by Root, this will
     // never do anything if LHS has only one use.
     if (!LHS->hasOneUse()) {
       unsigned NumReplacements =
           DominatesByEdge
-              ? replaceDominatedUsesWith(LHS, RHS, *DT, Root)
-              : replaceDominatedUsesWith(LHS, RHS, *DT, Root.getStart());
+              ? replaceDominatedUsesWithIf(LHS, RHS, *DT, Root,
+                                           canReplacePointersIfEqual)
+              : replaceDominatedUsesWithIf(LHS, RHS, *DT, Root.getStart(),
+                                           canReplacePointersIfEqual);
 
-      Changed |= NumReplacements > 0;
+      if (NumReplacements > 0) {
+        Changed = true;
         NumGVNEqProp += NumReplacements;
         // Cached information for anything that uses LHS will be invalid.
         if (MD)
           MD->invalidateCachedPointerInfo(LHS);
       }
+    }
 
     // Now try to deduce additional equalities from this one. For example, if
     // the known equality was "(A != B)" == "false" then it follows that A and B
     // are equal in the scope. Only boolean equalities with an explicit true or
     // false RHS are currently supported.
     if (!RHS->getType()->isIntegerTy(1))
       // Not a boolean equality - bail out.
       continue;
if (CmpInst *Cmp = dyn_cast<CmpInst>(LHS)) {
       uint32_t Num = VN.lookupOrAddCmp(Cmp->getOpcode(), NotPred, Op0, Op1);
       // If the number we were assigned was brand new then there is no point in
       // looking for an instruction realizing it: there cannot be one!
       if (Num < NextNum) {
         Value *NotCmp = findLeader(Root.getEnd(), Num);
         if (NotCmp && isa<Instruction>(NotCmp)) {
           unsigned NumReplacements =
               DominatesByEdge
-                  ? replaceDominatedUsesWith(NotCmp, NotVal, *DT, Root)
-                  : replaceDominatedUsesWith(NotCmp, NotVal, *DT,
-                                             Root.getStart());
-          Changed |= NumReplacements > 0;
+                  ? replaceDominatedUsesWithIf(NotCmp, NotVal, *DT, Root,
+                                               canReplacePointersIfEqual)
+                  : replaceDominatedUsesWithIf(NotCmp, NotVal, *DT,
+                                               Root.getStart(),
+                                               canReplacePointersIfEqual);
+          if (NumReplacements > 0) {
+            Changed = true;
             NumGVNEqProp += NumReplacements;
             // Cached information for anything that uses NotCmp will be invalid.
             if (MD)
               MD->invalidateCachedPointerInfo(NotCmp);
           }
         }
+      }
       // Ensure that any instruction in scope that gets the "A < B" value number
       // is replaced with false.
       // The leader table only tracks basic blocks, not edges. Only add to if we
       // have the simple case where the edge dominates the end.
       if (RootDominatesEnd)
         addToLeaderTable(Num, NotVal, Root.getEnd());
 
       continue;
if (!Repl) {
     return false;
   } else if (Repl == I) {
     // If I was the result of a shortcut PRE, it might already be in the table
     // and the best replacement for itself. Nothing to do.
     return false;
   }
 
   // Remove it!
   patchAndReplaceAllUsesWith(I, Repl);
   if (MD && Repl->getType()->isPtrOrPtrVectorTy())
     MD->invalidateCachedPointerInfo(Repl);
   markInstructionForDeletion(I);
   return true;
 }
 
 /// runOnFunction - This is the main transformation entry point for a function.
 bool GVNPass::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,

llvm/lib/Transforms/Utils/Local.cpp

static const unsigned KnownIDs[] = {
       LLVMContext::MD_fpmath,          LLVMContext::MD_invariant_load,
       LLVMContext::MD_invariant_group, LLVMContext::MD_nonnull,
       LLVMContext::MD_access_group,    LLVMContext::MD_preserve_access_index,
       LLVMContext::MD_noundef,         LLVMContext::MD_nontemporal};
   combineMetadata(ReplInst, I, KnownIDs, false);
 }
 
 template <typename RootType, typename DominatesFn>
-static unsigned replaceDominatedUsesWith(Value *From, Value *To,
-                                         const RootType &Root,
-                                         const DominatesFn &Dominates) {
+static unsigned replaceDominatedUsesWith(
+    Value *From, Value *To, const RootType &Root, const DominatesFn &Dominates,
+    std::optional<
+        function_ref<bool(const Value *, const Value *, const User *)>>
+        ShouldReplace) {
   assert(From->getType() == To->getType());
 
   unsigned Count = 0;
   for (Use &U : llvm::make_early_inc_range(From->uses())) {
     if (!Dominates(Root, U))
       continue;
+    if (ShouldReplace.has_value() &&
+        !ShouldReplace.value()(From, To, U.getUser()))
+      continue;
     U.set(To);
     LLVM_DEBUG(dbgs() << "Replace dominated use of '" << From->getName()
                       << "' as " << *To << " in " << *U << "\n");
     ++Count;
   }
   return Count;
 }
 

 }
 
 unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
                                         DominatorTree &DT,
                                         const BasicBlockEdge &Root) {
   auto Dominates = [&DT](const BasicBlockEdge &Root, const Use &U) {
     return DT.dominates(Root, U);
   };
-  return ::replaceDominatedUsesWith(From, To, Root, Dominates);
+  return ::replaceDominatedUsesWith(From, To, Root, Dominates, std::nullopt);
 }
 
 unsigned llvm::replaceDominatedUsesWith(Value *From, Value *To,
                                         DominatorTree &DT,
                                         const BasicBlock *BB) {
   auto Dominates = [&DT](const BasicBlock *BB, const Use &U) {
     return DT.dominates(BB, U);
   };
-  return ::replaceDominatedUsesWith(From, To, BB, Dominates);
+  return ::replaceDominatedUsesWith(From, To, BB, Dominates, std::nullopt);
+}
+
+unsigned llvm::replaceDominatedUsesWithIf(
+    Value *From, Value *To, DominatorTree &DT, const BasicBlockEdge &Root,
+    function_ref<bool(const Value *From, const Value *To, const User *U)>
+        ShouldReplace) {
+  auto Dominates = [&DT](const BasicBlockEdge &Root, const Use &U) {
+    return DT.dominates(Root, U);
+  };
+  return ::replaceDominatedUsesWith(From, To, Root, Dominates, ShouldReplace);
+}
+
+unsigned llvm::replaceDominatedUsesWithIf(
+    Value *From, Value *To, DominatorTree &DT, const BasicBlock *BB,
+    function_ref<bool(const Value *From, const Value *To, const User *U)>
+        ShouldReplace) {
+  auto Dominates = [&DT](const BasicBlock *BB, const Use &U) {
+    return DT.dominates(BB, U);
+  };
+  return ::replaceDominatedUsesWith(From, To, BB, Dominates, ShouldReplace);
 }
 
 bool llvm::callsGCLeafFunction(const CallBase *Call,
                                const TargetLibraryInfo &TLI) {
   // Check if the function is specifically marked as a gc leaf function.
   if (Call->hasFnAttr("gc-leaf-function"))
     return true;
   if (const Function *F = Call->getCalledFunction()) {

llvm/test/Transforms/GVN/assume-equal.ll

entry:
   %vtable = load ptr, ptr %call, align 8
   %cmp.vtables = icmp eq ptr %vtable, getelementptr inbounds ([4 x ptr], ptr @_ZTV1A, i64 0, i64 2)
   tail call void @llvm.assume(i1 %cmp.vtables)
   br i1 %p, label %if.then, label %if.else
 
 if.then:                                          ; preds = %entry
   %0 = load ptr, ptr %vtable, align 8
   
-  ; CHECK: call i32 @_ZN1A3fooEv(
+  ; CHECK-NOT: call i32 @_ZN1A3fooEv(
   %call2 = tail call i32 %0(ptr %call) #1
   
   br label %if.end
 
 if.else:                                          ; preds = %entry
   %vfn47 = getelementptr inbounds ptr, ptr %vtable, i64 1
   
-  ; CHECK: call i32 @_ZN1A3barEv(
+  ; CHECK-NOT: call i32 @_ZN1A3barEv(
   %1 = load ptr, ptr %vfn47, align 8
   
   %call5 = tail call i32 %1(ptr %call) #1
   br label %if.end
 
 if.end:                                           ; preds = %if.else, %if.then
   ret void
 }
 
 ; Check integration with invariant.group handling
 ; CHECK-LABEL: define void @invariantGroupHandling(i1 zeroext %p) {
 define void @invariantGroupHandling(i1 zeroext %p) {
 entry:
   %call = tail call noalias ptr @_Znwm(i64 8) #4
   tail call void @_ZN1AC1Ev(ptr %call) #1
   %vtable = load ptr, ptr %call, align 8, !invariant.group !0
   %cmp.vtables = icmp eq ptr %vtable, getelementptr inbounds ([4 x ptr], ptr @_ZTV1A, i64 0, i64 2)
   tail call void @llvm.assume(i1 %cmp.vtables)
   br i1 %p, label %if.then, label %if.else
 
 if.then:                                          ; preds = %entry
   %0 = load ptr, ptr %vtable, align 8
   
-; CHECK: call i32 @_ZN1A3fooEv(
+; CHECK-NOT: call i32 @_ZN1A3fooEv(
   %call2 = tail call i32 %0(ptr %call) #1
   %vtable1 = load ptr, ptr %call, align 8, !invariant.group !0
   %call1 = load ptr, ptr %vtable1, align 8
-; CHECK: call i32 @_ZN1A3fooEv(
+; CHECK-NOT: call i32 @_ZN1A3fooEv(
   %callx = tail call i32 %call1(ptr %call) #1
   
   %vtable2 = load ptr, ptr %call, align 8, !invariant.group !0
   %call4 = load ptr, ptr %vtable2, align 8
-; CHECK: call i32 @_ZN1A3fooEv(
+; CHECK-NOT: call i32 @_ZN1A3fooEv(
   %cally = tail call i32 %call4(ptr %call) #1
   
   %vtable3 = load ptr, ptr %call, align 8, !invariant.group !0
   %vfun = load ptr, ptr %vtable3, align 8
-; CHECK: call i32 @_ZN1A3fooEv(
+; CHECK-NOT: call i32 @_ZN1A3fooEv(
   %unknown = tail call i32 %vfun(ptr %call) #1
   
   br label %if.end
 
 if.else:                                          ; preds = %entry
   %vfn47 = getelementptr inbounds ptr, ptr %vtable, i64 1
   
-  ; CHECK: call i32 @_ZN1A3barEv(
+  ; CHECK-NOT: call i32 @_ZN1A3barEv(
   %1 = load ptr, ptr %vfn47, align 8
   
   %call5 = tail call i32 %1(ptr %call) #1
   br label %if.end
 
 if.end:                                           ; preds = %if.else, %if.then
   ret void
 }

llvm/test/Transforms/GVN/condprop.ll

 
 ; Check that we dont propagate pointer equalities when illegal.
 define i32 @test13(ptr %ptr1, ptr %ptr2) {
 ; CHECK-LABEL: @test13(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[GEP1:%.*]] = getelementptr i32, ptr [[PTR2:%.*]], i32 1
 ; CHECK-NEXT:    [[GEP2:%.*]] = getelementptr i32, ptr [[PTR2]], i32 2
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq ptr [[PTR1:%.*]], [[PTR2]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[ENTRY_END_CRIT_EDGE:%.*]]
-; CHECK:       entry.end_crit_edge:
-; CHECK-NEXT:    [[VAL2_PRE:%.*]] = load i32, ptr [[GEP2]], align 4
-; CHECK-NEXT:    br label [[END:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    [[VAL1:%.*]] = load i32, ptr [[GEP2]], align 4
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[VAL2:%.*]] = phi i32 [ [[VAL1]], [[IF]] ], [ [[VAL2_PRE]], [[ENTRY_END_CRIT_EDGE]] ]
-; CHECK-NEXT:    [[PHI1:%.*]] = phi ptr [ [[PTR2]], [[IF]] ], [ [[GEP1]], [[ENTRY_END_CRIT_EDGE]] ]
-; CHECK-NEXT:    [[PHI2:%.*]] = phi i32 [ [[VAL1]], [[IF]] ], [ 0, [[ENTRY_END_CRIT_EDGE]] ]
+; CHECK-NEXT:    [[PHI1:%.*]] = phi ptr [ [[PTR1]], [[IF]] ], [ [[GEP1]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[PHI2:%.*]] = phi i32 [ [[VAL1]], [[IF]] ], [ 0, [[ENTRY]] ]
 ; CHECK-NEXT:    store i32 0, ptr [[PHI1]], align 4
+; CHECK-NEXT:    [[VAL2:%.*]] = load i32, ptr [[GEP2]], align 4
 ; CHECK-NEXT:    [[RET:%.*]] = add i32 [[PHI2]], [[VAL2]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
 entry:
   %gep1 = getelementptr i32, ptr %ptr2, i32 1
   %gep2 = getelementptr i32, ptr %ptr2, i32 2
   %cmp = icmp eq ptr %ptr1, %ptr2
   br i1 %cmp, label %if, label %end

 
 define void @test14(ptr %ptr1, ptr noalias %ptr2, i1 %c1, i1 %c2) {
 ; CHECK-LABEL: @test14(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[GEP1:%.*]] = getelementptr inbounds i32, ptr [[PTR1:%.*]], i32 1
 ; CHECK-NEXT:    [[GEP2:%.*]] = getelementptr inbounds i32, ptr [[PTR1]], i32 2
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    br i1 [[C1:%.*]], label [[LOOP_IF1_CRIT_EDGE:%.*]], label [[THEN:%.*]]
-; CHECK:       loop.if1_crit_edge:
-; CHECK-NEXT:    [[VAL2_PRE:%.*]] = load i32, ptr [[GEP2]], align 4
-; CHECK-NEXT:    br label [[IF1:%.*]]
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[IF1:%.*]], label [[THEN:%.*]]
 ; CHECK:       if1:
-; CHECK-NEXT:    [[VAL2:%.*]] = phi i32 [ [[VAL2_PRE]], [[LOOP_IF1_CRIT_EDGE]] ], [ [[VAL3:%.*]], [[LOOP_END:%.*]] ]
+; CHECK-NEXT:    [[VAL2:%.*]] = load i32, ptr [[GEP2]], align 4
 ; CHECK-NEXT:    store i32 [[VAL2]], ptr [[GEP2]], align 4
 ; CHECK-NEXT:    store i32 0, ptr [[GEP1]], align 4
 ; CHECK-NEXT:    br label [[THEN]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq ptr [[GEP2]], [[PTR2:%.*]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP_END]], label [[IF2:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP_END:%.*]], label [[IF2:%.*]]
 ; CHECK:       if2:
 ; CHECK-NEXT:    br label [[LOOP_END]]
 ; CHECK:       loop.end:
-; CHECK-NEXT:    [[PHI3:%.*]] = phi ptr [ [[PTR2]], [[THEN]] ], [ [[PTR1]], [[IF2]] ]
-; CHECK-NEXT:    [[VAL3]] = load i32, ptr [[GEP2]], align 4
+; CHECK-NEXT:    [[PHI3:%.*]] = phi ptr [ [[GEP2]], [[THEN]] ], [ [[PTR1]], [[IF2]] ]
+; CHECK-NEXT:    [[VAL3:%.*]] = load i32, ptr [[GEP2]], align 4
 ; CHECK-NEXT:    store i32 [[VAL3]], ptr [[PHI3]], align 4
 ; CHECK-NEXT:    br i1 [[C2:%.*]], label [[LOOP]], label [[IF1]]
 ;
 entry:
   %gep1 = getelementptr inbounds i32, ptr %ptr1, i32 1
   %gep2 = getelementptr inbounds i32, ptr %ptr1, i32 2
   br label %loop
 
 loop:
   %phi1 = phi ptr [ %gep3, %loop.end ], [ %gep1, %entry ]
   br i1 %c1, label %if1, label %then
 
 
 if1:
   %val2 = load i32, ptr %gep2, align 4
   store i32 %val2, ptr %gep2, align 4
   store i32 0, ptr %phi1, align 4
   br label %then
 
 then:
   %cmp = icmp eq ptr %gep2, %ptr2
   br i1 %cmp, label %loop.end, label %if2
 
 if2:
   br label %loop.end
 
 loop.end:
   %phi3 = phi ptr [ %gep2, %then ], [ %ptr1, %if2 ]
   %val3 = load i32, ptr %gep2, align 4
   store i32 %val3, ptr %phi3, align 4
   %gep3 = getelementptr inbounds i32, ptr %ptr1, i32 1
   br i1 %c2, label %loop, label %if1
 }
 
+; Make sure we dont return 1.
 define i32 @test15(ptr noalias %p, i64 %i) {
 ; CHECK-LABEL: @test15(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, ptr [[P:%.*]], i64 [[I:%.*]]
 ; CHECK-NEXT:    store i32 1, ptr [[ARRAYIDX]], align 4
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq ptr [[P]], @a
 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    store i32 2, ptr @a, align 4
+; CHECK-NEXT:    store i32 2, ptr [[P]], align 4
+; CHECK-NEXT:    [[DOTPRE:%.*]] = load i32, ptr [[ARRAYIDX]], align 4
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    ret i32 1
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ [[DOTPRE]], [[IF_THEN]] ], [ 1, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i32 [[TMP0]]
 ;
 entry:
   %arrayidx = getelementptr inbounds i32, ptr %p, i64 %i
   store i32 1, ptr %arrayidx, align 4
   %cmp = icmp eq ptr %p, @a
   br i1 %cmp, label %if.then, label %if.end
 
 if.then:
   store i32 2, ptr %p, align 4
   br label %if.end
 
 if.end:
   %0 = load i32, ptr %arrayidx, align 4
   ret i32 %0
 }
 
+; Make sure that the call to use_ptr does not have %p1
+; TODO: Use of %cmp2 can be optimized to true.
 define void @single_phi1(ptr %p1) {
 ; CHECK-LABEL: @single_phi1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[P2:%.*]] = load ptr, ptr poison, align 8
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq ptr [[P2]], [[P1:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP1]], label [[BB4:%.*]], label [[BB1:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    switch i8 poison, label [[BB2:%.*]] [
 ; CHECK-NEXT:    i8 0, label [[BB1]]
 ; CHECK-NEXT:    i8 1, label [[BB3:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    unreachable
 ; CHECK:       bb3:
 ; CHECK-NEXT:    br label [[BB4]]
 ; CHECK:       bb4:
-; CHECK-NEXT:    call void @use_bool(i1 true)
-; CHECK-NEXT:    call void @use_ptr(ptr [[P1]])
+; CHECK-NEXT:    call void @use_bool(i1 [[CMP1]])
+; CHECK-NEXT:    call void @use_ptr(ptr [[P2]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %p2 = load ptr, ptr poison, align 8
   %cmp1 = icmp eq ptr %p2, %p1
   br i1 %cmp1, label %bb4, label %bb1
 
 bb1:

 ; CHECK-NEXT:    i8 0, label [[BB1]]
 ; CHECK-NEXT:    i8 1, label [[BB3:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    br label [[BB4]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    br label [[BB4]]
 ; CHECK:       bb4:
-; CHECK-NEXT:    [[PHI1:%.*]] = phi ptr [ [[P1]], [[ENTRY:%.*]] ], [ [[P2]], [[BB2]] ], [ poison, [[BB3]] ]
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq ptr [[PHI1]], [[P1]]
-; CHECK-NEXT:    call void @use_bool(i1 [[CMP2]])
-; CHECK-NEXT:    call void @use_ptr(ptr [[PHI1]])
+; CHECK-NEXT:    call void @use_bool(i1 [[CMP1]])
+; CHECK-NEXT:    call void @use_ptr(ptr [[P2]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %p2 = load ptr, ptr poison, align 8
   %cmp1 = icmp eq ptr %p2, %p1
   br i1 %cmp1, label %bb4, label %bb1
 
 bb1:

 ; CHECK-NEXT:    i8 0, label [[BB1]]
 ; CHECK-NEXT:    i8 1, label [[BB3:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    unreachable
 ; CHECK:       bb3:
 ; CHECK-NEXT:    br label [[BB4]]
 ; CHECK:       bb4:
-; CHECK-NEXT:    call void @use_bool(i1 true)
+; CHECK-NEXT:    call void @use_bool(i1 [[CMP1]])
 ; CHECK-NEXT:    br label [[BB5:%.*]]
 ; CHECK:       bb5:
-; CHECK-NEXT:    call void @use_ptr(ptr [[P1]])
+; CHECK-NEXT:    call void @use_ptr(ptr [[P2]])
 ; CHECK-NEXT:    br label [[BB5]]
 ;
 entry:
   %p2 = load ptr, ptr poison, align 8
   %cmp1 = icmp eq ptr %p2, %p1
   br i1 %cmp1, label %bb4, label %bb1
 
 bb1:

 ; CHECK-NEXT:    i8 0, label [[BB1]]
 ; CHECK-NEXT:    i8 1, label [[BB3:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    br label [[BB4]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    br label [[BB4]]
 ; CHECK:       bb4:
-; CHECK-NEXT:    [[PHI1:%.*]] = phi ptr [ [[P1]], [[ENTRY:%.*]] ], [ [[P2]], [[BB2]] ], [ poison, [[BB3]] ]
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq ptr [[PHI1]], [[P1]]
-; CHECK-NEXT:    call void @use_bool(i1 [[CMP2]])
+; CHECK-NEXT:    call void @use_bool(i1 [[CMP1]])
 ; CHECK-NEXT:    br label [[BB5:%.*]]
 ; CHECK:       bb5:
-; CHECK-NEXT:    call void @use_ptr(ptr [[PHI1]])
+; CHECK-NEXT:    call void @use_ptr(ptr [[P2]])
 ; CHECK-NEXT:    br label [[BB5]]
 ;
 entry:
   %p2 = load ptr, ptr poison, align 8
   %cmp1 = icmp eq ptr %p2, %p1
   br i1 %cmp1, label %bb4, label %bb1
 
 bb1:

llvm/unittests/Analysis/LoadsTest.cpp

 }
 
 TEST(LoadsTest, CanReplacePointersIfEqual) {
   LLVMContext C;
   std::unique_ptr<Module> M = parseIR(C,
                                       R"IR(
 @y = common global [1 x i32] zeroinitializer, align 4
 @x = common global [1 x i32] zeroinitializer, align 4
-
 declare void @use(i32*)
 
-define void @f(i32* %p) {
+define void @f(i32* %p1, i32* %p2, i64 %i) {
   call void @use(i32* getelementptr inbounds ([1 x i32], [1 x i32]* @y, i64 0, i64 0))
-  call void @use(i32* getelementptr inbounds (i32, i32* getelementptr inbounds ([1 x i32], [1 x i32]* @x, i64 0, i64 0), i64 1))
+  call void @use(i32* %p1)
+
+  %p1_idx = getelementptr inbounds i32, i32* %p1, i64 %i
+  call void @use(i32* %p1_idx)
+
+  %icmp = icmp eq i32* %p1, getelementptr inbounds ([1 x i32], [1 x i32]* @y, i64 0, i64 0)
+  %ptrInt = ptrtoint i32* %p1 to i64
   ret void
 }
 )IR");
-  const auto &DL = M->getDataLayout();
   auto *GV = M->getNamedValue("f");
   ASSERT_TRUE(GV);
   auto *F = dyn_cast<Function>(GV);
   ASSERT_TRUE(F);
 
-  // NOTE: the implementation of canReplacePointersIfEqual is incomplete.
-  // Currently the only the cases it returns false for are really sound and
-  // returning true means unknown.
-  Value *P = &*F->arg_begin();
+  Value *P1 = &*F->arg_begin();
+  Value *P2 = F->getArg(1);
+  Value *NullPtr = Constant::getNullValue(P1->getType());
   auto InstIter = F->front().begin();
-  Value *ConstDerefPtr = *cast<CallInst>(&*InstIter)->arg_begin();
-  // ConstDerefPtr is a constant pointer that is provably de-referenceable. We
-  // can replace an arbitrary pointer with it.
-  EXPECT_TRUE(canReplacePointersIfEqual(P, ConstDerefPtr, DL, nullptr));
-
-  ++InstIter;
-  Value *ConstUnDerefPtr = *cast<CallInst>(&*InstIter)->arg_begin();
-  // ConstUndDerefPtr is a constant pointer that is provably not
-  // de-referenceable. We cannot replace an arbitrary pointer with it.
-  EXPECT_FALSE(
-      canReplacePointersIfEqual(ConstDerefPtr, ConstUnDerefPtr, DL, nullptr));
+  CallInst *UserOfY = cast<CallInst>(&*InstIter);
+  CallInst *UserOfP1 = cast<CallInst>(&*++InstIter);
+  Value *ConstDerefPtr = UserOfY->getArgOperand(0);
+  // We cannot replace two pointers in arbitrary instructions unless we are
+  // replacing with null or they have the same underlying object.
+  EXPECT_FALSE(canReplacePointersIfEqual(ConstDerefPtr, P1, UserOfY));
+  EXPECT_FALSE(canReplacePointersIfEqual(P1, ConstDerefPtr, UserOfP1));
+  EXPECT_FALSE(canReplacePointersIfEqual(P1, P2, UserOfP1));
+  EXPECT_TRUE(canReplacePointersIfEqual(P1, NullPtr, UserOfP1));
+
+  GetElementPtrInst *BasedOnPtr = cast<GetElementPtrInst>(&*++InstIter);
+  CallInst *UserOfP1_Idx = cast<CallInst>(&*++InstIter);
+  EXPECT_TRUE(canReplacePointersIfEqual(BasedOnPtr, P1, UserOfP1_Idx));
+  EXPECT_FALSE(canReplacePointersIfEqual(BasedOnPtr, P2, UserOfP1_Idx));
+
+  // We can replace two arbitrary pointers in icmp and ptrtoint instructions.
+  ICmpInst *IcmpUser = cast<ICmpInst>(&*++InstIter);
+  PtrToIntInst *PtrToIntUser = cast<PtrToIntInst>(&*++InstIter);
+  EXPECT_TRUE(canReplacePointersIfEqual(P1, P2, IcmpUser));
+  EXPECT_TRUE(canReplacePointersIfEqual(P1, P2, PtrToIntUser));
 }