This is an archive of the discontinued LLVM Phabricator instance.

[ConstraintElimination] Add constraint elimination pass.
ClosedPublic

Authored by fhahn on Jul 24 2020, 12:34 PM.

Details

Summary

This patch is a first draft of a new pass that adds a more flexible way
to eliminate compares based on more complex constraints collected from
dominating conditions.

In particular, it aims at simplifying conditions of the forms below
using a forward propagation approach, rather than instcomine-style
ad-hoc backwards walking of def-use chains.

if (x < y)
  if (y < z)
    if (x < z) <- simplify

or

if (x + 2 < y)
    if (x + 1 < y) <- simplify assuming no wraps

The general approach is to collect conditions and blocks, sort them by
dominance and then iterate over the sorted list. Conditions are turned
into a linear inequality and add it to a system containing the linear
inequalities that hold on entry to the block. For blocks, we check each
compare against the system and see if it is implied by the constraints
in the system.

We also keep a stack of processed conditions and remove conditions from
the stack and the constraint system once they go out-of-scope (= do not
dominate the current block any longer).

Currently there still are the least the following issues

  • Checking the system requires multiplications/additions on potentially large numbers and could overflow. I guess we would need to detect and bail out when that happens
  • Currently large unsigned constants cannot be added to the system (coefficients must be represented as integers)
  • The way constraints are managed currently is not very optimized.

The last 2 don't need to be addressed immediately, but I think the first
one would need to be addressed to start with.

But for now, I'd like to share the approach to get some initial
thoughts/feedback.

Diff Detail

Event Timeline

fhahn created this revision.Jul 24 2020, 12:34 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 24 2020, 12:34 PM
fhahn updated this revision to Diff 280576.Jul 24 2020, 1:26 PM

Now clang-formatted

Noting else in the compiler does this sort of symbolic reasoning, I think, so this is sort of a new space. The way the constraint system is constructed seems a little complicated, but I'm not sure how much you could simplify it.

What sort of patterns in realistic code are you hoping to catch? This seems like the sort of thing that could come up with array bounds checks, I guess?

Noting else in the compiler does this sort of symbolic reasoning, I think, so this is sort of a new space. The way the constraint system is constructed seems a little complicated, but I'm not sure how much you could simplify it.

Are you referring to the way comparisons are converted to constraints (getConstraint) or the the iteration over the BBs? getConstraint is definitely a bit ugly at the moment and could hopefully be improved.

What sort of patterns in realistic code are you hoping to catch? This seems like the sort of thing that could come up with array bounds checks, I guess?

Yes, I mainly want to improve elimination of various kinds of bounds checks. As is, ~380 conditions are removed in an -O3 -flto build of MultiSource/SPEC2006/SPEC2000, but it currently only leads to 4 binaries with differences. So it might not help a lot with regular C/C++ codebases, but could have a big impact on code with redundant runtime checks and cases where people try to make the compiler look stupid.

Currently we do not optimize case like these:

int foo_notoptimized(int a, int b)
{
  if (b < a)
    __builtin_unreachable();
  if (a < 0)
    return -1;
  if (b < 0) // never true
    return 0;
  return 1;
}

int foo_notoptimized2(int a, int b)
{
  if (a < 0)
    return -1;
  if (b < a)
    __builtin_unreachable();
  if (b < 0) // never true
    return 0;
  return 1;
}

int foo_notoptimized3(int a, int b)
{
  if (b < a)
    return 2;
  if (a < 0)
    return -1;
  if (b < 0) // never true
    return 0;
  return 1;
}

Clang does no optimization here. GCC optimizes foo_notoptimized2. Would this pass optimize those examples?

Maybe worth to check if example posted in PR38349 could be optimized this pass or some other pass (cc @nikic) as well.

int foo(int x, int y) {

int k = x & 15;
if(k == 0) {
    int p = x & 7;
    return p == 0; // true
}
return y;

}

Currently we do not optimize case like these:

snip

Clang does no optimization here. GCC optimizes foo_notoptimized2. Would this pass optimize those examples?

Yes I think those are exactly cases this pass should optimize. Currently, signed compare are not supported, but with a and b turned into unsigned (and < 0 adjusted) simplifies the commented checks to false for foo_notoptimized and foo_notoptimized3. It doesn't for foo_notoptimized2 currently because something introduces an and which is not yet supported. Also, with the current position in the pipeline, the early simplify cfg run needs to be disabled, as it removes the control flow that's used by this pass. But this is just a tangential issue.

Maybe worth to check if example posted in PR38349 could be optimized this pass or some other pass (cc @nikic) as well.

int foo(int x, int y) {

int k = x & 15;
if(k == 0) {
    int p = x & 7;
    return p == 0; // true
}
return y;

}

This case is problematic, because I am not sure how bitwise ops would be integrated into the constraint system.

Maybe worth to mention GCC’s project Ranger:

https://gcc.gnu.org/wiki/AndrewMacLeod/Ranger

fhahn added a comment.Jul 27 2020, 3:31 AM

Maybe worth to mention GCC’s project Ranger:

https://gcc.gnu.org/wiki/AndrewMacLeod/Ranger

Thanks for sharing. I am not familiar with ranger, but I think this patch is a fundamentally different approach With the approach in the patch, we don't explicitly track constant ranges for each value. The ranges for values are implicit in the constraint system and can also be symbolic. IIUC Ranger's approach is more similar to the way constant ranges are used in LVI/SCCP in LLVM

fhahn updated this revision to Diff 283329.Aug 5 2020, 12:17 PM

Rebase and simplify

fhahn updated this revision to Diff 283337.Aug 5 2020, 12:28 PM

Do not enable by default

fhahn retitled this revision from [ConstraintElimination] Add constraint elimination pass (WIP). to [ConstraintElimination] Add constraint elimination pass..Aug 6 2020, 8:13 AM
fhahn added a comment.Aug 6 2020, 8:15 AM

Ping. I think this should be ready for review. I simplified the code in the the latest update a bit, put up a patch fixing potential integer overflows while simplifying the constraint system (D85336) and also put up follow-up patches to decompose add nuw, sub nuw and using conditions from and and or.

We definitely stretch instcombine beyond the basics to try to reduce icmps, so if we can do that more efficiently here, that seems like a win.
Do you know if http://bugs.llvm.org/PR47091 could (eventually) be handled here?
Is there any initial compile-time data?

MSxDOS added a subscriber: MSxDOS.Aug 14 2020, 4:37 PM
fhahn added a comment.Aug 15 2020, 8:05 AM

We definitely stretch instcombine beyond the basics to try to reduce icmps, so if we can do that more efficiently here, that seems like a win.
Do you know if http://bugs.llvm.org/PR47091 could (eventually) be handled here?

Initially we only keep the current constraints for basic block level granularity, but this could be changed in the future to make it track & query per instruction. For the example in PR47091, we can check if any of the constraints become redundant. It would require extending the scope of the pass to consider re-writing a set of compares to a reduced set, instead of only removing known conditions. I think that's certainly possible in the future, once the initial implementation settled in. Also, the pass itself is quite small, so it should be easy to iterate/change/rewrite/extend in tree.

Is there any initial compile-time data?

With a few additional changes to decompose more constructs, it doesn't look too bad, O3 +0.23% geomean, ReleaseThinLto + 0.36% (http://llvm-compile-time-tracker.com/compare.php?from=6a821908f49019f3180c640cd6ddf570aceaca78&to=2569b43f8184c94b878060cb23455e397f2ef8d9&stat=instructions). That's with plenty of tuning opportunities in the constraint-system implementation. There seems to be quite a big regression for a case with -g which I need to check out though.

One additional caveat is that it currently only handles information from unsigned compares. If we can prove that a value is non-negative, it should also be possible to include info from signed compares. But we would probably need to maintain a separate set of constraints for signed compares.

fhahn added a comment.Aug 24 2020, 2:51 PM

ping :)

Any thoughts about what changes should be made to make some progress, e.g. structuring the patches, testing, additional work/docs/tests.

I'm not familiar with the underying ConstraintSystem (Fourier–Motzkin elimination), so if anyone else has experience with it and can chime in, that would be nice.

Would the overflow concerns mentioned in the description be handled more easily by changing the ConstraintSystem to use APInt?

Given that this is off-by-default, I don't think this needs detailed review at this stage - we have sufficient optimization motivation, and the cost of keeping it in trunk while making improvements isn't high. Either we'll eventually flip it to default-on because it will be shown to be worth its compile-time cost, or it will be dismissed and removed.

llvm/test/Transforms/ConstraintElimination/uge.ll
2

What does this file/diffs demonstrate?

fhahn updated this revision to Diff 289249.Sep 1 2020, 12:29 PM

I'm not familiar with the underying ConstraintSystem (Fourier–Motzkin elimination), so if anyone else has experience with it and can chime in, that would be nice.

In a way, we delegate most of the logic to a 'black-box', the constraint system, which potentially makes debugging failures a bit more tricky.

It should however be possible to record the constraints and the found solutions and use a different solver (e.g. Z3) to verify the implementation in LLVM produces the correct result. I put up D86966, which adds a nice way to print the system and solution for each check if there is a solution.

It also adds a script which generates a python script that uses Z3's API to feed the same constraints to Z3 and checks if it produces the same result. I use this to verify all queries generated when building the test-suite (MultiSource/SPEC2000/SEPC2006) with LTO and all queries matched.

Would the overflow concerns mentioned in the description be handled more easily by changing the ConstraintSystem to use APInt?

I am not sure. I think it would boil down replacing the calls to __builtin_mul_overflow & co with APInt's smul_ov & co. Unless I am missing something, I am not sure if that is enough benefit to complicate things by using APInt everywhere.

Given that this is off-by-default, I don't think this needs detailed review at this stage - we have sufficient optimization motivation, and the cost of keeping it in trunk while making improvements isn't high. Either we'll eventually flip it to default-on because it will be shown to be worth its compile-time cost, or it will be dismissed and removed.

That sounds good to me, thanks!

fhahn added a comment.Sep 1 2020, 12:30 PM
llvm/test/Transforms/ConstraintElimination/uge.ll
2

I missed changing that back to constraint-elimination when comparing it to instcombine. Should be fixed now.

spatel accepted this revision.Sep 2 2020, 5:48 AM

LGTM

llvm/include/llvm/Analysis/ConstraintSystem.h
57

Call addVariableRow() instead of duplicating the code?

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp
178

conditions -> condition

This revision is now accepted and ready to land.Sep 2 2020, 5:48 AM
fhahn added a comment.Sep 2 2020, 2:43 PM

LGTM

Thanks! How should we proceed with the prerequisite patches adding the constraint system? Should I just add reviewers for them as well?

spatel added a comment.Sep 3 2020, 5:36 AM

LGTM

Thanks! How should we proceed with the prerequisite patches adding the constraint system? Should I just add reviewers for them as well?

Sure - add similar reviewers as listed on this review. I just see some potential cosmetic improvements, but others may want to comment.

fhahn updated this revision to Diff 289801.Sep 3 2020, 1:38 PM

Remove unnecessary variable, address comments & rebase.

LGTM

Thanks! How should we proceed with the prerequisite patches adding the constraint system? Should I just add reviewers for them as well?

Sure - add similar reviewers as listed on this review. I just see some potential cosmetic improvements, but others may want to comment.

SGTM & done.

fhahn updated this revision to Diff 291893.Sep 15 2020, 6:39 AM

rebased, will commit shortly.

This revision was landed with ongoing or failed builds.Sep 15 2020, 11:32 AM
This revision was automatically updated to reflect the committed changes.