This is an archive of the discontinued LLVM Phabricator instance.

[LoopDelete][Assume] Allow deleting loops with assumes
ClosedPublic

Authored by Tyker on Aug 28 2020, 2:17 PM.

Details

Summary

This pervent very poor optimization caused by a signle assume like https://godbolt.org/z/EK3oMh

baseline flags: -O3
patched flags: -O3 -mllvm --enable-knowledge-retention

Before the patch

Metric: compile_time
Program                                                      baseline patched diff
             test-suite :: CTMark/tramp3d-v4/tramp3d-v4.test  20.72    29.74  43.5%
                     test-suite :: CTMark/Bullet/bullet.test  24.39    24.91   2.2%
               test-suite :: CTMark/7zip/7zip-benchmark.test  37.39    38.06   1.8%
                      test-suite :: CTMark/kimwitu++/kc.test  11.76    11.94   1.5%
                   test-suite :: CTMark/sqlite3/sqlite3.test  12.94    12.91  -0.3%
                       test-suite :: CTMark/SPASS/SPASS.test  11.72    11.70  -0.2%
                     test-suite :: CTMark/lencod/lencod.test  16.12    16.10  -0.1%
                   test-suite :: CTMark/ClamAV/clamscan.test  13.31    13.30  -0.1%
              test-suite :: CTMark/mafft/pairlocalalign.test   9.12     9.12  -0.1%
 test-suite :: CTMark/consumer-typeset/consumer-typeset.test   9.34     9.34  -0.1%
                                          Geomean difference                   4.2%

Metric: compiler_Kinst_count
Program                                                      baseline     patched      diff
             test-suite :: CTMark/tramp3d-v4/tramp3d-v4.test 107576069.87 172886418.90 60.7%
                     test-suite :: CTMark/Bullet/bullet.test 123291865.66 125457117.96  1.8%
                      test-suite :: CTMark/kimwitu++/kc.test  56347884.64  57298544.14  1.7%
               test-suite :: CTMark/7zip/7zip-benchmark.test 180637699.58 183341656.57  1.5%
                   test-suite :: CTMark/sqlite3/sqlite3.test  66723788.85  66664692.80 -0.1%
                   test-suite :: CTMark/ClamAV/clamscan.test  69581500.56  69597863.92  0.0%
                     test-suite :: CTMark/lencod/lencod.test  94236501.48  94216545.32 -0.0%
                       test-suite :: CTMark/SPASS/SPASS.test  58516756.95  58505089.07 -0.0%
 test-suite :: CTMark/consumer-typeset/consumer-typeset.test  48832815.53  48841989.39  0.0%
              test-suite :: CTMark/mafft/pairlocalalign.test  49682720.53  49686324.34  0.0%
                                          Geomean difference                            5.4%

After the patch

Metric: compile_time
Program                                                      baseline patched diff
             test-suite :: CTMark/tramp3d-v4/tramp3d-v4.test  20.70    22.40   8.2%
               test-suite :: CTMark/7zip/7zip-benchmark.test  37.13    38.05   2.5%
                     test-suite :: CTMark/Bullet/bullet.test  24.25    24.83   2.4%
                      test-suite :: CTMark/kimwitu++/kc.test  11.69    11.94   2.2%
                   test-suite :: CTMark/ClamAV/clamscan.test  13.19    13.36   1.3%
                     test-suite :: CTMark/lencod/lencod.test  16.02    16.19   1.1%
 test-suite :: CTMark/consumer-typeset/consumer-typeset.test   9.29     9.36   0.7%
                       test-suite :: CTMark/SPASS/SPASS.test  11.64    11.73   0.7%
              test-suite :: CTMark/mafft/pairlocalalign.test   9.10     9.15   0.5%
                   test-suite :: CTMark/sqlite3/sqlite3.test  12.95    12.96   0.0%
                                          Geomean difference                   1.9%

Metric: compiler_Kinst_count
Program                                                      baseline     patched      diff
             test-suite :: CTMark/tramp3d-v4/tramp3d-v4.test 107590933.61 114044834.72  6.0%
                      test-suite :: CTMark/kimwitu++/kc.test  56344526.77  57235806.29  1.6%
                     test-suite :: CTMark/Bullet/bullet.test 123291285.10 125128334.97  1.5%
               test-suite :: CTMark/7zip/7zip-benchmark.test 180641540.10 183155706.39  1.4%
                   test-suite :: CTMark/sqlite3/sqlite3.test  66725619.22  66668713.92 -0.1%
                       test-suite :: CTMark/SPASS/SPASS.test  58509029.85  58478704.75 -0.1%
 test-suite :: CTMark/consumer-typeset/consumer-typeset.test  48843711.23  48826894.68 -0.0%
                     test-suite :: CTMark/lencod/lencod.test  94233305.79  94207544.23 -0.0%
                   test-suite :: CTMark/ClamAV/clamscan.test  69587887.66  69603549.90  0.0%
              test-suite :: CTMark/mafft/pairlocalalign.test  49686968.65  49689291.04  0.0%
                                          Geomean difference                            1.0%

I am not sure this fix is the best way to fix the issue. I think the issue is more general,
assume are considered as modifying memory because they are control-flow sensitive
but they dont't affect memory. because of this mayHaveSideEffects returns true for assumes when it souldn't.

any thought ?

Diff Detail

Event Timeline

Tyker created this revision.Aug 28 2020, 2:17 PM
Tyker requested review of this revision.Aug 28 2020, 2:17 PM

I'd almost say mayHaveSideEffects could have a boolean parameter to ignore droppable uses. Either way, this is right now the best we can do, teach the things that query mayHaveSideEffects and friends about droppable uses. If we have them as flags to all of them that might be easier to do.

@efriedma @lebedev.ri @xbolva00 @fhahn thoughts?

Tyker added a comment.Aug 28 2020, 2:56 PM

I'd almost say mayHaveSideEffects could have a boolean parameter to ignore droppable uses. Either way, this is right now the best we can do, teach the things that query mayHaveSideEffects and friends about droppable uses. If we have them as flags to all of them that might be easier to do.

mayHaveSideEffects isn't the only place where this is visible, assume also prevent function/arguments from being treated as readonly or readnone.

I'd almost say mayHaveSideEffects could have a boolean parameter to ignore droppable uses. Either way, this is right now the best we can do, teach the things that query mayHaveSideEffects and friends about droppable uses. If we have them as flags to all of them that might be easier to do.

mayHaveSideEffects isn't the only place where this is visible, assume also prevent function/arguments from being treated as readonly or readnone.

Similar solution, we need to have a readXXXX_and_droppable as an attribute and the query functions, like mayHaveSideEffects will return no if droppable should be ignored.
I might actually propose a new way to specify side effect attributes soon, the current one has obvious limitations ;) Till then, I'm fine with this patch FWIW.
Let's wait a bit to see if there are other opinions.

Should mayWriteToMemory/mayHaveSideEffects be true for llvm.assume? It can't have any side-effects, really; at most, it has undefined behavior.

Of course, if we added readonly to llvm.assume, we'd have to be careful that transforms don't accidentally throw away llvm.assume operations. But that seems solvable.

Should mayWriteToMemory/mayHaveSideEffects be true for llvm.assume? It can't have any side-effects, really; at most, it has undefined behavior.

Of course, if we added readonly to llvm.assume, we'd have to be careful that transforms don't accidentally throw away llvm.assume operations. But that seems solvable.

The problem is it is control dependent. Maybe our shift towards speculatable has made it possible that possible UB is strong enough for assume. That would be cool. I haven't thought about this, we should.

jdoerfert accepted this revision.Sep 14 2020, 9:25 PM

OK, I think we need to revisit assume but an otherwise empty loop with an assume doesn't seem to be particularly useful. We might want to hoist loop invariant assumes, but that can be revisited. I think this solves a problem and is reasonable until we have time and ideas.

@efriedma please let us know if u disagree

@Tyker let's wait before committing.

This revision is now accepted and ready to land.Sep 14 2020, 9:25 PM
efriedma accepted this revision.Sep 16 2020, 7:22 PM

Sure, seems fine for now.

The problem is it is control dependent.

So is every other instruction with potentially undefined behavior?

This revision was automatically updated to reflect the committed changes.
Tyker added a comment.Sep 26 2020, 3:34 AM

OK, I think we need to revisit assume but an otherwise empty loop with an assume doesn't seem to be particularly useful. We might want to hoist loop invariant assumes, but that can be revisited. I think this solves a problem and is reasonable until we have time and ideas.

i agree on the idea but proving the assume is loop invariant doesn't seem enough since assumes a control-flow dependent.