This is an archive of the discontinued LLVM Phabricator instance.

[BasicAA] Fix BatchAA results for phi-phi assumptions
ClosedPublic

Authored by nikic on Nov 22 2020, 10:58 AM.

Details

Summary

Change the way NoAlias assumptions in BasicAA are handled. Instead of handling this inside the phi-phi code, always initially insert a NoAlias result into the map and keep track whether it is used. If it is used, then we require that we also get back NoAlias from the recursive queries. Otherwise, the entry is changed to MayAlias.

Additionally, keep track of all location pairs we inserted that may still be based on assumptions higher up. If it turns out one of those assumptions is incorrect, we flush them from the cache.

The compile-time impact for the new implementation is higher than before: https://llvm-compile-time-tracker.com/compare.php?from=c0bb9859de6991cc233e2dedb978dd118da8c382&to=c07112373279143e37568b5bcd293daf81a35973&stat=instructions However, it avoids exponential runtime cases we run to if we don't cache assumption-based results entirely.

This also produces better results in some cases, because NoAlias assumptions can now start at any root, rather than just phi-phi pairs. This is not just relevant for analysis quality, but also for BatchAA consistency: Otherwise, results would once again depend on query order, though at least they wouldn't be wrong.

This ended up more complicated and more expansive than I hoped, but I wasn't able to come up with another solution that satisfies all the constraints.

Diff Detail

Event Timeline

nikic created this revision.Nov 22 2020, 10:58 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 22 2020, 10:58 AM
nikic requested review of this revision.Nov 22 2020, 10:58 AM
nikic updated this revision to Diff 306928.EditedNov 22 2020, 11:34 AM
nikic edited the summary of this revision. (Show Details)

Rebase. I've committed the not-really-related change that lead to the compile-time improvement separately. With that gone, the new numbers are: https://llvm-compile-time-tracker.com/compare.php?from=6f5ef648a57aed3274118dcbd6467e8ac4f6ed1f&to=50d73a31620111c4298cc336ac4682ef7585ed6b&stat=instructions Which does make this a mild compile-time regression, but not too bad.

asbirlea accepted this revision.Nov 24 2020, 4:29 PM

This is great, thank you for this fix!

This revision is now accepted and ready to land.Nov 24 2020, 4:29 PM
This revision was automatically updated to reflect the committed changes.

Which does make this a mild compile-time regression, but not too bad.

I've hit a case where this causes compilation to hang indefinitely (or so it seems; the case earlier compiled in around 2 seconds, and now hasn't finished after at least 7 minutes), with https://martin.st/temp/dvdec-preproc.c compiled with clang -target x86_64-w64-mingw32 -w -c -O3 dvdec-preproc.c.

nikic reopened this revision.Nov 27 2020, 1:35 PM

@mstorsjo Thanks for the report & revert.

Best reduction for the hang I have for now is https://gist.github.com/nikic/bc0e46b99555c93995d07c55cb4f8420 under -O3.

This revision is now accepted and ready to land.Nov 27 2020, 1:35 PM
thakis added a subscriber: thakis.Nov 27 2020, 8:54 PM

We also found an infinite loop triggered by this. Our repro is at https://bugs.chromium.org/p/chromium/issues/detail?id=1153398#c3

nikic planned changes to this revision.Nov 29 2020, 1:38 AM

This will clearly need something more sophisticated. After thinking this over, I also think that the current approach of inserting assumptions at phis is not optimal, as the tests added in https://github.com/llvm/llvm-project/commit/b5e8de9c7903d458b098a8af03939384270c1a5e show. I expect this can also result in BatchAA returning different results, depending on whether a gep or a phi is visited first. We should be inserting everything as NoAlias into the cache in the first place and tracking whether that assumption gets used or not.

nikic updated this revision to Diff 309635.Dec 4 2020, 1:28 PM
nikic edited the summary of this revision. (Show Details)

New implementation, see summary.

This revision is now accepted and ready to land.Dec 4 2020, 1:28 PM
nikic requested review of this revision.Dec 4 2020, 1:28 PM
nikic added a comment.Jan 5 2021, 11:18 AM

Gentle ping :)

asbirlea accepted this revision.Jan 5 2021, 5:50 PM

Apologies for the delay, I spent some more time understanding how the assumptions changed in the new implementation.

The compile time impact on this one is noticeable, but it provides more powerful results and resolves the miscompiles when using BatchAA. Overall I think this is great to have patched in.

This revision is now accepted and ready to land.Jan 5 2021, 5:50 PM
This revision was automatically updated to reflect the committed changes.