Page MenuHomePhabricator

[PredicateInfo] Generalize processing of conditions
ClosedPublic

Authored by nikic on Jan 11 2021, 1:44 PM.

Details

Summary

Branch/assume conditions in PredicateInfo are currently handle in a rather ad-hoc manner, with some arbitrary limitations. For example, an and of two icmps will be handled, but an and of an icmp and some other condition will not. That also includes the case where more than two conditions and and'ed together.

This patch makes the handling more general by looking through an arbitrary number of ands/ors and considering all kinds of conditions (though operands will only be taken for cmps of course).

Diff Detail

Event Timeline

nikic created this revision.Jan 11 2021, 1:44 PM
nikic requested review of this revision.Jan 11 2021, 1:44 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 11 2021, 1:44 PM
nikic added a comment.Jan 12 2021, 9:22 AM

The thought that the current limitations are compile-time related crossed my mind, but that doesn't seem to be a concern: https://llvm-compile-time-tracker.com/compare.php?from=00f773cf424699d8eb31591fdc95e0ca18b2682c&to=10ec7c7960ea47e899003fcd7d1ba5c389ba1cae&stat=instructions

The thought that the current limitations are compile-time related crossed my mind, but that doesn't seem to be a concern: https://llvm-compile-time-tracker.com/compare.php?from=00f773cf424699d8eb31591fdc95e0ca18b2682c&to=10ec7c7960ea47e899003fcd7d1ba5c389ba1cae&stat=instructions

I believe compile-time is at least partly a motivation for some limitation here, but not in a way that is exposed by CTMark. I think here we mostly want to guard against the worst case (deeply nested AND/OR). Those kind of cases are not really covered by the tests in CTMark (or other parts in the test-suite), but are surprisingly common in practice (e.g. various code-generators that feed into Clang/LLVM). I think it would be desirable to have a limit on the number of items in the worklist to guard against that.

llvm/test/Transforms/SCCP/conditions-ranges.ll
1012

Perhaps I missed it, but do we have tests with a chain or Ors? If not, it would be good to add one, also independent of SCCP. The same also for assume And it would probably be also good to cover the case where and and or are mixed.

nikic updated this revision to Diff 317413.Jan 18 2021, 1:29 PM

Rebase over more tests, prevent exponential renaming with reused operands.

nikic added a comment.Jan 18 2021, 1:30 PM

I believe compile-time is at least partly a motivation for some limitation here, but not in a way that is exposed by CTMark. I think here we mostly want to guard against the worst case (deeply nested AND/OR). Those kind of cases are not really covered by the tests in CTMark (or other parts in the test-suite), but are surprisingly common in practice (e.g. various code-generators that feed into Clang/LLVM). I think it would be desirable to have a limit on the number of items in the worklist to guard against that.

You make a good point here. I think it's worthwhile to distinguish two cases though: The first is where you have a simple chain of and's. I believe this is harmless. Even if you have 32 and's in a row, you would introduce 32 new variables, and that's linear in the input size. This is not a pathological case. The second case is where you have code like this:

%b = and i1 %a, %a
%c = and i1 %b, %b
%d = and i1 %c, %c
...

That is, where and operands get reused in a tree. In this case, my previous code introduced an exponential number of variables for %a, which is certainly not good. I have updated the implementation to add a Visited set, which will cut down the number of renames to linear. I've also added some test cases for deep chains and trees (as well as general tests for nesting).

Does this address this concern sufficiently, or do you want the linear case to be limited as well?

fhahn added a comment.Jan 20 2021, 7:37 AM

I believe compile-time is at least partly a motivation for some limitation here, but not in a way that is exposed by CTMark. I think here we mostly want to guard against the worst case (deeply nested AND/OR). Those kind of cases are not really covered by the tests in CTMark (or other parts in the test-suite), but are surprisingly common in practice (e.g. various code-generators that feed into Clang/LLVM). I think it would be desirable to have a limit on the number of items in the worklist to guard against that.

You make a good point here. I think it's worthwhile to distinguish two cases though: The first is where you have a simple chain of and's. I believe this is harmless. Even if you have 32 and's in a row, you would introduce 32 new variables, and that's linear in the input size. This is not a pathological case. The second case is where you have code like this:

%b = and i1 %a, %a
%c = and i1 %b, %b
%d = and i1 %c, %c
...

That is, where and operands get reused in a tree. In this case, my previous code introduced an exponential number of variables for %a, which is certainly not good. I have updated the implementation to add a Visited set, which will cut down the number of renames to linear. I've also added some test cases for deep chains and trees (as well as general tests for nesting).

Does this address this concern sufficiently, or do you want the linear case to be limited as well?

I think there is still a potentially problematic case: multiple branches could use the same deep chain/tree of and/ors (or different entries of the same tree), in which case the new approach would still have to traverse a lot of instructions in the worst case I think.

Granted, this is unlikely to happen often in practice, but the original goal of PredicateInfo is to be as fast as possible IIRC, so ensuring we only traverse and create a constant number of instructions per branch/assume would still be desirable I think.

nikic updated this revision to Diff 317892.Jan 20 2021, 8:43 AM

Add a limit on the maximum number of conditions we handle for each branch/assume. Value for the limit was picked arbitrarily...

fhahn accepted this revision.Jan 20 2021, 10:45 AM

LGTM, thanks

lib/Transforms/Utils/PredicateInfo.cpp
58 ↗(On Diff #317892)

can this be static or in an anonymous namespace?

This revision is now accepted and ready to land.Jan 20 2021, 10:45 AM
nikic added inline comments.Jan 20 2021, 11:35 AM
lib/Transforms/Utils/PredicateInfo.cpp
58 ↗(On Diff #317892)

Yeah, this should've been static. I'll fix this when landing.

This revision was automatically updated to reflect the committed changes.