Page MenuHomePhabricator

[DSE] Improve partial overlap detection
ClosedPublic

Authored by ebrevnov on Oct 29 2020, 1:48 AM.

Details

Summary

Currently isOverwrite returns OW_MaybePartial even for accesss known not to overlap. This is not a big problem for legacy implementation (since isPartialOverwrite follows isOverwrite and clarifies the result). Contrary SSA based version does a lot of work to later find out that accesses don't overlap. Besides negative impact on compile time we quickly reach MemorySSAPartialStoreLimit and miss optimization opportunities.

Note: In fact, I think it would be cleaner implementation if isOverwrite returned fully clarified result in the first place whithout need to call isPartialOverwrite. This can be done as a follow up. What do you think?

Diff Detail

Event Timeline

ebrevnov created this revision.Oct 29 2020, 1:48 AM
ebrevnov requested review of this revision.Oct 29 2020, 1:48 AM
ebrevnov edited the summary of this revision. (Show Details)Oct 29 2020, 1:52 AM
ebrevnov added reviewers: fhahn, junbuml, hfinkel.
fhahn accepted this revision.Oct 29 2020, 5:01 AM

The initial split was quite crude and only re-used the existing utilities for partial store handling. Thanks for improving this! I am sure there's further potential for improvements.

LGTM!

This gives nice improvements in some cases and compile-time looks neutral to slightly positive (http://llvm-compile-time-tracker.com/compare.php?from=df63eedef64d715ce1f31843f7de9c11fe1e597f&to=e3bdfcf94a9eeae6e006d010464f0c1b3550577d&stat=instructions)

Same hash: 196 (filtered out)
Remaining: 41
Metric: dse.NumCompletePartials

Program                                        base   patch  diff
 test-suite...CI_Purple/SMG2000/smg2000.test     1.00  10.00 900.0%
 test-suite.../CINT2000/252.eon/252.eon.test    44.00 392.00 790.9%
 test-suite...rks/FreeBench/pifft/pifft.test     1.00   3.00 200.0%
 test-suite.../Benchmarks/Bullet/bullet.test    36.00  97.00 169.4%
 test-suite.../CINT2006/403.gcc/403.gcc.test     2.00   5.00 150.0%
 test-suite...tions/lambda-0.1.3/lambda.test     1.00   2.00 100.0%
 test-suite.../CINT2000/176.gcc/176.gcc.test     4.00   7.00 75.0%
 test-suite...3.xalancbmk/483.xalancbmk.test    19.00  26.00 36.8%
 test-suite...rks/tramp3d-v4/tramp3d-v4.test    37.00  50.00 35.1%
 test-suite...marks/7zip/7zip-benchmark.test    28.00  37.00 32.1%
 test-suite...yApps-C++/PENNANT/PENNANT.test     6.00   7.00 16.7%
 test-suite...006/447.dealII/447.dealII.test   405.00 423.00  4.4%
Same hash: 196 (filtered out)
Remaining: 41
Metric: dse.NumFastStores

Program                                        base    patch   diff
 test-suite...rks/FreeBench/pifft/pifft.test     1.00    3.00  200.0%
 test-suite...000/183.equake/183.equake.test     2.00    4.00  100.0%
 test-suite...langs-C/football/football.test     5.00    9.00  80.0%
 test-suite...lications/viterbi/viterbi.test     2.00    3.00  50.0%
 test-suite...hmarks/McCat/08-main/main.test    15.00   20.00  33.3%
 test-suite...arks/VersaBench/dbms/dbms.test     8.00   10.00  25.0%
 test-suite...ks/Prolangs-C++/city/city.test    24.00   27.00  12.5%
 test-suite.../CINT2000/175.vpr/175.vpr.test    11.00   12.00   9.1%
 test-suite...ce/Benchmarks/PAQ8p/paq8p.test    63.00   68.00   7.9%
 test-suite...arks/mafft/pairlocalalign.test    92.00   98.00   6.5%
 test-suite.../CINT2000/252.eon/252.eon.test   2405.00 2556.00  6.3%
 test-suite...CI_Purple/SMG2000/smg2000.test   153.00  162.00   5.9%
 test-suite.../Benchmarks/Bullet/bullet.test   1312.00 1357.00  3.4%
 test-suite.../CINT2000/176.gcc/176.gcc.test   587.00  603.00   2.7%
 test-suite...tions/lambda-0.1.3/lambda.test    44.00   45.00   2.3%
 test-suite...yApps-C++/PENNANT/PENNANT.test    46.00   47.00   2.2%
 test-suite...chmarks/MallocBench/gs/gs.test   113.00  115.00   1.8%
 test-suite...ications/JM/lencod/lencod.test   765.00  778.00   1.7%
 test-suite...rks/tramp3d-v4/tramp3d-v4.test   893.00  905.00   1.3%
 test-suite.../CINT2006/403.gcc/403.gcc.test   1204.00 1217.00  1.1%
 test-suite...marks/7zip/7zip-benchmark.test   2189.00 2209.00  0.9%
 test-suite...006/447.dealII/447.dealII.test   3013.00 3032.00  0.6%
 test-suite...3.xalancbmk/483.xalancbmk.test   1475.00 1482.00  0.5%
 test-suite...lications/ClamAV/clamscan.test   246.00  247.00   0.4%
 test-suite...006/453.povray/453.povray.test   1233.00 1237.00  0.3%
 test-suite...:: External/Povray/povray.test   1251.00 1255.00  0.3%

Note: In fact, I think it would be cleaner implementation if isOverwrite returned fully clarified result in the first place whithout need to call isPartialOverwrite. This can be done as a follow up. What do you think?

sounds good to me.

This revision is now accepted and ready to land.Oct 29 2020, 5:01 AM
asbirlea accepted this revision.Oct 29 2020, 4:37 PM

This LGTM.
I'd like to understand better what you mean by not calling partialOverwrite. If the functionality in that call would be included in the isOverwrite call, note that there are call-paths that would do more work than they do now, and I thought there was a previous refactoring done to avoid this.
I may be mis-understanding though, so feel free to send the additional changes and we can discuss on those.

This LGTM.
I'd like to understand better what you mean by not calling partialOverwrite. If the functionality in that call would be included in the isOverwrite call, note that there are call-paths that would do more work than they do now, and I thought there was a previous refactoring done to avoid this.

As of today isPartialOverwrite does two things. 1) Clarifies OW_MaybePartial returned by isOverwrite 2) Takes some actions if EnablePartialOverwriteTracking is true and accesses do overwrite. My suggestion to move part 1) into isOverwrite and keep second part inside isPartialOverwrite (and rename isPartialOverwrite).

I may be mis-understanding though, so feel free to send the additional changes and we can discuss on those.

This revision was landed with ongoing or failed builds.Oct 30 2020, 8:23 AM
This revision was automatically updated to reflect the committed changes.