Page MenuHomePhabricator

Make processing @llvm.assume more efficient - operand bundles
ClosedPublic

Authored by hfinkel on Nov 30 2016, 8:39 AM.

Details

Summary

There is an efficiency problem with how we process @llvm.assume in ValueTracking (and other places). The AssumptionCache tracks all of the assumptions in a given function. In order to find assumptions relevant to computing known bits, etc. we search every assumption in the function. For ValueTracking that means that we do O(#assumes * #values) work in InstCombine and other passes (with a constant factor that can be quite large because we'll repeat this search at every level of recursion of the analysis).

Several of us discussed this situation at the last developers' meeting, and here's the first step toward implementing the discussed solution: Make the values that an assume might affect operands of the assume itself. To avoid exposing this detail to frontends and passes that need not worry about it, I've used the new operand-bundle feature to add these extra call "operands" in a way that does not affect the intrinsic's signature. I think this solution is relatively clean. InstCombine adds these extra operands based on what ValueTracking, LVI, etc. will need and then those passes need only search the users of the values under consideration. This should fix the computational complexity problem.

My goal is to use this scheme to remove the need for the AssumptionCache all together. The only user not removed by the current patch is ScalarEvolution. @sanjoy, do you have a good idea of how this might be done? I looked at the handing of the guard intrinsics in SE, and it looks like we should handle both the same way, although the handling of the guard intrinsics seems to involve a lot of basic-block scanning, and I'd hope there was a more-efficient way.

Event Timeline

hfinkel updated this revision to Diff 79744.Nov 30 2016, 8:39 AM
hfinkel retitled this revision from to Make processing @llvm.assume more efficient - operand bundles.
hfinkel updated this object.
hfinkel added reviewers: Prazek, chandlerc, sanjoy, wash.
hfinkel added subscribers: llvm-commits, sanjoy.
davide added a subscriber: davide.Nov 30 2016, 5:24 PM
sanjoy edited edge metadata.Dec 8 2016, 7:23 PM

Hi Hal,

Thanks for doing this! I have not yet looked at the code in detail, but I have some high level comments, questions and answers.

One high level question: did you look at keeping this "affected" set as part of the AssumptionCache itself? That is, keep a map that maps ValueHandles to the corresponding assume instruction they affect?

Despite being an implementation detail we should add some basic documentation about this operand bundle to the langref.

I don't have a good solution for using this in SCEV. One not-great solution is to have a pre-pass in SCEV that does this:

for (AssumeInst AI : all_assumes_in_func) {
  for (AffectOp : AI) {
    AffectedMap[getSCEV(AffectOp)].push_back(AI);
  }
}

and then use the AffectedMap instead of using the "affected" operand bundle directly.

You could also try to scan a SCEV expression to fetch Value s out of SCEVUnknown nodes and use the use lists of those values. But they won't catch cases like the loop preheader containing assume(%a + 1 < %b) and then a isKnownPredicate(%a + 1 < %b) query since getSCEV("%a + 1") will look through the addition and create an add expr.

As for your question about guards: while I initially wanted to use AssumptionCache (and I did have an RFC on llvm-dev about this), I did not go ahead with that idea since it wasn't obvious to me that it would be faster (that is, it isn't obviously a good idea; and I'd have to measure both sides to make an informed judgement). This is because we tend to have lots of guards in every function, and looking at each one *could* get expensive.

However, I think we will be able to use this "affected" infrastructure more readily.

Prazek edited edge metadata.Dec 13 2016, 5:54 AM

Does it solve my problem with assume vtable loads being processed slowly? If so, do I understand it correctly that it just keep track of what variables are effected by assume?

lib/Analysis/LazyValueInfo.cpp
928 ↗(On Diff #81441)

auto
rename it to II?

lib/Analysis/ValueTracking.cpp
531 ↗(On Diff #81441)

DITTO

Hi Hal,

Thanks for doing this! I have not yet looked at the code in detail, but I have some high level comments, questions and answers.

One high level question: did you look at keeping this "affected" set as part of the AssumptionCache itself? That is, keep a map that maps ValueHandles to the corresponding assume instruction they affect?

I thought about this, but I wanted to first see if we could get rid of the assumption cache entirely. I don't really like requiring the side contract which needs to be updated by every place that might clone instructions. If we can't eliminate it, then I agree that keeping this information in the cache is cleaner.

Despite being an implementation detail we should add some basic documentation about this operand bundle to the langref.

Sure.

I don't have a good solution for using this in SCEV. One not-great solution is to have a pre-pass in SCEV that does this:

for (AssumeInst AI : all_assumes_in_func) {
  for (AffectOp : AI) {
    AffectedMap[getSCEV(AffectOp)].push_back(AI);
  }
}

and then use the AffectedMap instead of using the "affected" operand bundle directly.

Hrmm. I don't really want to scan if possible - in part because it seems like it would make SCEV much less lazy than it is now (and in part because I want to get rid of the assumption cache, and if I do that, then I don't have an efficient way to find the assumptions). What if I hooked getSCEV so that, if the value in question was affected by an assumptions, then we add that to the AffectedMap?

The code that I'm currently trying to replace, as such, is this:

// Check conditions due to any @llvm.assume intrinsics.
for (auto &AssumeVH : AC.assumptions()) {
  if (!AssumeVH)
    continue;
  auto *CI = cast<CallInst>(AssumeVH);
  if (!DT.dominates(CI, Latch->getTerminator()))
    continue;

  if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0), false))
    return true;
}

And so the problem is that I need to be able to figure out, given LHS and RHS, if the assumption condition might make isImpliedCond(Pred, LHS, RHS, ...) true. getSCEV(affected_value) might not be exactly equal to wither LHS or RHS for this to be the case. Perhaps, however, if AffectedMap was essentially the transitive closure of the getSCEV(affected_value) -- meaning that the map contains those SCEVs but also all other SCEVs that use those as operands -- it might work?

You could also try to scan a SCEV expression to fetch Value s out of SCEVUnknown nodes and use the use lists of those values. But they won't catch cases like the loop preheader containing assume(%a + 1 < %b) and then a isKnownPredicate(%a + 1 < %b) query since getSCEV("%a + 1") will look through the addition and create an add expr.

Yea, this was exactly my concern with trying to use the values from SCEVUnknown.

As for your question about guards: while I initially wanted to use AssumptionCache (and I did have an RFC on llvm-dev about this), I did not go ahead with that idea since it wasn't obvious to me that it would be faster (that is, it isn't obviously a good idea; and I'd have to measure both sides to make an informed judgement). This is because we tend to have lots of guards in every function, and looking at each one *could* get expensive.

However, I think we will be able to use this "affected" infrastructure more readily.

Sounds good. Thanks!

Does it solve my problem with assume vtable loads being processed slowly? If so, do I understand it correctly that it just keep track of what variables are effected by assume?

Fixing that, and related symptoms, is certainly my motivation.

lib/Analysis/LazyValueInfo.cpp
928 ↗(On Diff #81441)

Sure.

lib/Analysis/ValueTracking.cpp
531 ↗(On Diff #81441)

Sure.

hfinkel updated this revision to Diff 81436.Dec 14 2016, 12:28 PM
hfinkel edited edge metadata.

Responded to review comments and implemented the discussed solution for ScalarEvolution.

At this point, no passes will depend on the AssumptionCache, and after this is committed, I'd unceremoniously rip that out as a follow-up change.

hfinkel updated this revision to Diff 81441.Dec 14 2016, 12:43 PM

Added updates to the LangRef.

Prazek accepted this revision.Dec 14 2016, 3:00 PM
Prazek edited edge metadata.

LGTM, Thanks!

This revision is now accepted and ready to land.Dec 14 2016, 3:00 PM
This revision was automatically updated to reflect the committed changes.