Page MenuHomePhabricator

[ValueTracking] Handle assumes on arguments with context instruction
Needs RevisionPublic

Authored by nikic on Feb 19 2021, 2:39 PM.

Details

Summary

This is an alternative to D93974 and D97077. If CtxI is null, then we can still make use of any assumes that are guaranteed to be executed from the entry of the function. This allows us to handle assumes on arguments, for cases where no explicit context instruction is provided.

Relative to D93974 the advantage here is that we only need to do the "guaranteed to execute" check if there are potentially relevant assumes, rather than always doing it. Relative to D97077 the advantage is that this is not SCEV specific, and avoids issues with ephemeral values (i.e., we support assumes directly at the start of the function).

This change has no compile-time impact on CTMark, though that isn't exactly an assume heavy workload.

The unit tests are adopted from D93974.

Diff Detail

Unit TestsFailed

TimeTest
60 msx64 debian > Polly.ScopInfo::user_provided_assumptions_2.ll
Script: -- : 'RUN: at line 1'; opt -polly-process-unprofitable -polly-remarks-minimal -polly-use-llvm-names -polly-import-jscop-dir=/mnt/disks/ssd0/agent/llvm-project/polly/test/ScopInfo -polly-codegen-verify -pass-remarks-analysis="polly-scops" -polly-scops -disable-output < /mnt/disks/ssd0/agent/llvm-project/polly/test/ScopInfo/user_provided_assumptions_2.ll 2>&1 | FileCheck /mnt/disks/ssd0/agent/llvm-project/polly/test/ScopInfo/user_provided_assumptions_2.ll

Event Timeline

nikic created this revision.Feb 19 2021, 2:39 PM
nikic requested review of this revision.Feb 19 2021, 2:39 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 19 2021, 2:39 PM

I like this idea. As I mentioned before, we should check the willreturn and nounwind function attribute to avoid scanning all together, but that is again only partially related.

LG from me, someone else might want to chime in as well.

reames added a subscriber: test.EditedFeb 19 2021, 4:41 PM

I posted another alternative (or maybe a stepping stone towards this one), over in D97099. It simply sets the context for arguments, and uses the existing mechanism. The key detail from this patch is that it doesn't attempt to side step the ephemeral value case.

For the ephemeral value case, I'd really like to have a solution which is not non-instruction specific. If we asking a query on some instruction I, the fact that I is directly used by the assume should not prevent us from inferring facts about that assume.

The test case I'm thinking of is something like the following:

declare void @llvm.assume(i1)

define i32 @test(i1* %p) {

%a = load i1, i1* %p
call void @llvm.assume(i1 %a)
%a.32 = sext i1 %a to i32
ret i32 %a.32

}

$ opt -enable-new-pm=0 -analyze -scalar-evolution ephemeral.ll
Printing analysis 'Scalar Evolution Analysis' for function 'test':
Classifying expressions for: @test

%a = load i1, i1* %p, align 1
-->  %a U: full-set S: full-set
%a.32 = sext i1 %a to i32
-->  (sext i1 %a to i32) U: [-1,1) S: [-1,1) <--- FOCUS HERE

Determining loop execution counts for: @test

From this, we appear to not be picking up the assume on %a - as I'd expect from the code structure.

Interestingly, instcombine does constant fold this. This is because instcombine queries the sext directly with the context set to the sext and that gets preserved through the recursion. So unlikely SCEV's usage, when analyzing %a (the load) inscombine has a context set. This explains the difference in behavior.

Having said all that, I also don't want to block progress on perfection, and this does seem like progress. If you want to land this as is, and we can iterate in tree, I'm completely fine with that. (To be explicit, you can consider this a long winded LGTM.)

(Edited to clarify instcombine bit)

Thinking about it further, there's one property that results from this approach that I really don't like. After this patch, there will be cases where setting a context instruction *pessimizes* the result returned over not including one. That's really not supposed to happen. In particular, it means that for some use cases (analyzing assume calls) forgetting a context instruction now becomes a miscompile. That seems unpleasant.

reames requested changes to this revision.Feb 19 2021, 7:55 PM

Continuing from my last comment, I've come to believe this change is fatally flawed. Let me explain the problem I see. I haven't found a practical test case yet, so it's possible I'm wrong about this.

As noted previously, when analyzing an assume, we must pass in a context instruction to prevent using the assumption in forming facts about the conditions contributing to the assume (when that assume is in the entry block and involves an argument). The problem is that SCEV does not do so, and in fact, can not. As a result, SCEV will infer facts about the values which hold because of the assume. If we can trick any SCEV based transform pass into optimizing the assume condition, we've created the exact condition that the ephemeral logic code exists to prevent.

Until this concern has been addressed, please consider my previous LGTM revoked.

This revision now requires changes to proceed.Feb 19 2021, 7:55 PM
nikic added a comment.Feb 20 2021, 2:06 AM

As noted previously, when analyzing an assume, we must pass in a context instruction to prevent using the assumption in forming facts about the conditions contributing to the assume (when that assume is in the entry block and involves an argument). The problem is that SCEV does not do so, and in fact, can not. As a result, SCEV will infer facts about the values which hold because of the assume. If we can trick any SCEV based transform pass into optimizing the assume condition, we've created the exact condition that the ephemeral logic code exists to prevent.

You're correct, but I don't think you've followed this thought to its logical conclusion. The difference between the different approaches we have isn't whether ephemeral values get ignored, it's whether they get ignored intentionally, or accidentally.

foo(int a, int b) {
    assume(a != 0);
    assume(b != 0);
}
foo(int a, int b) {
    assume(b != 0);
    assume(a != 0);
}

This patch is going to use both assumption consistently. Approaches that set context to the first instruction will use the second assume in each function, but not the first. In either case, if the analysis result is used to fold the assume conditions, we may end up eliminating non-redundant assumes.

This is a problem that will affect any approach that uses assumes on the value itself without an explicit context instruction that guarantees that assume conditions will not get folded. And I think you're right that we should avoid this. That does mean that all four patches are ultimately broken (heh).

For SCEV, the right approach would probably be to do something similar to LVI, and take assumptions into account not directly on the value itself, but on each use, i.e. assume(x >= 0); x >> 1 would apply the assume only when computing the range of x >> 1.

And I think you're right that we should avoid this. That does mean that all four patches are ultimately broken (heh).

Unfortunately, I think you're right. I spent way more time this weekend trying to find a principled work around, and nothing I've found so far works. I'm not quite ready to admit defeat here, but this does appear to be a hard to bypass problem.

One point worth highlighting is that the bad thing we're trying to avoid is a loss of the information encoded in an assume. It's not a correctness issue. From a purely pragmatic perspective, we may wish to explore whether the benefit of increased inference is worth the information loss. I suspect that tradeoff is different for each patch, and I have not really explored in that direction yet. It's also worth noting that the current mechanism does allow some assumes to be removed, so we wouldn't be adding that behavior.

For SCEV, the right approach would probably be to do something similar to LVI, and take assumptions into account not directly on the value itself, but on each use, i.e. assume(x >= 0); x >> 1 would apply the assume only when computing the range of x >> 1.

Unfortunately, this would be a fairly major redesign of SCEV. I don't think this is a practical path forward. The main problem is that SCEV doesn't track an explicit use list for SCEVExprs.

One idea on an alternate approach we could explore...

In the langref, we have an alternate way of spelling assumes using operand bundles. The key advantage of that approach (in the context of this discussion), is that there are no ephemeral icmps generated. We still have to concern ourselves with not eliminating assumes, but at least the assumes are themselves direct uses of the values we're inferring facts about.

If we were to extend the operand bundle syntax to allow arbitrary predicates, we could allow the use of the operand bundle assumes without a context, and simply restrict transform passes from *directly* simplifying assume operands. The only tricky case I see here is equalities as CSE would tend to replace the operands in the deopt bundle if e.g. instsimplify knew two values were equivalent from the assume. (I haven't fully thought this through.)

If we do pursue this, we'd need to untangle the operand bundle form handling from the knowledge transfer work, but that doesn't seem challenging. I'm not sure why those are coupled currently anyways.

jdoerfert added a comment.EditedFeb 22 2021, 9:31 AM

[EDIT: I wrote this before I saw the last comment ;) ]

If you move the information into the operand bundle: llvm.assume(i1 true) ["icmp.eq"(%a, %b)] ["icmp.le"(%p, 0)] this problem goes away, doesn't it?
If so, there is also the outline approach which has many other benefits (https://lists.llvm.org/pipermail/llvm-dev/2019-December/137632.html):

llvm.assume(i1 true) ["assertion_fn"(%a, %b, %p)]
static void assertion_fn(%a, %b, %p) {
  %c0 = icmp eq %a, %b
  llvm.assume(%c0)
  %c1 = icmp le %p, 0
  llvm.assume(%c1)
  // or ret `and c0, c1`
}

Just to clarify one thing: The (general) ephemeral value problem is a bit more complicated in that we actually *do* want to fold assume conditions -- just not on themselves. For example, if you have assume(x > 0); assume(x > 1);, then it is expected that the second assume gets folded away, because it is implied by the first and thus redundant. I don't think assume operand bundles fundamentally change the picture here, they just make it easier to identify ephemeral values.

jdoerfert added a comment.EditedFeb 22 2021, 1:40 PM

EDIT: submitted a half-baked answer I forgot I was typing with a new one -.- after hitting the "quote" button the old text was basically hidden.

One idea on an alternate approach we could explore...

In the langref, we have an alternate way of spelling assumes using operand bundles. The key advantage of that approach (in the context of this discussion), is that there are no ephemeral icmps generated. We still have to concern ourselves with not eliminating assumes, but at least the assumes are themselves direct uses of the values we're inferring facts about.

If we were to extend the operand bundle syntax to allow arbitrary predicates, we could allow the use of the operand bundle assumes without a context, and simply restrict transform passes from *directly* simplifying assume operands. The only tricky case I see here is equalities as CSE would tend to replace the operands in the deopt bundle if e.g. instsimplify knew two values were equivalent from the assume. (I haven't fully thought this through.)

I think operand bundles are not "accidentally" removed because it is easy to determine if they are assume bundle uses. (I would argue that you don't want to optimize "unknown" bundle uses in general but that is a different conversation.)

If we do pursue this, we'd need to untangle the operand bundle form handling from the knowledge transfer work, but that doesn't seem challenging. I'm not sure why those are coupled currently anyways.

Because that was the only use case. Untangling is eventually needed for sure.

Just to clarify one thing: The (general) ephemeral value problem is a bit more complicated in that we actually *do* want to fold assume conditions -- just not on themselves. For example, if you have assume(x > 0); assume(x > 1);, then it is expected that the second assume gets folded away, because it is implied by the first and thus redundant. I don't think assume operand bundles fundamentally change the picture here, they just make it easier to identify ephemeral values.

It does because you can identify assume uses easily. So you can ask if x > 1 is known not using the particular use of x for the reasoning.