Page MenuHomePhabricator

[SCEV] Relax abnormal exit check in isAddRecNeverPoison.
Changes PlannedPublic

Authored by fhahn on May 11 2020, 2:03 PM.

Details

Summary

Currently isAddRecNeverPoison fails if there are any abnormal exits in a
loop, like function calls that may throw.

This check can be a bit relaxed however: if the instruction we are
looking at is in the latch block and guaranteed to transfer execution
to the successor, then the instruction can never yield poison (if the
latch is control dependent on it), as the branch is always executed when
the instruction is executed.

Diff Detail

Unit TestsFailed

TimeTest
70 msLLVM.Analysis/ScalarEvolution::Unknown Unit Message ("")
Script: -- : 'RUN: at line 1'; /mnt/disks/ssd0/agent/workspace/BETA_amd64_debian_testing_clang8/llvm-project/build/bin/opt < /mnt/disks/ssd0/agent/workspace/BETA_amd64_debian_testing_clang8/llvm-project/llvm/test/Analysis/ScalarEvolution/nsw.ll -analyze -scalar-evolution | /mnt/disks/ssd0/agent/workspace/BETA_amd64_debian_testing_clang8/llvm-project/build/bin/FileCheck /mnt/disks/ssd0/agent/workspace/BETA_amd64_debian_testing_clang8/llvm-project/llvm/test/Analysis/ScalarEvolution/nsw.ll
60 msLLVM.Analysis/ScalarEvolution::Unknown Unit Message ("")
Script: -- : 'RUN: at line 1'; c:\ws\beta\llvm-project\build\bin\opt.exe < C:\ws\beta\llvm-project\llvm\test\Analysis\ScalarEvolution\nsw.ll -analyze -scalar-evolution | c:\ws\beta\llvm-project\build\bin\filecheck.exe C:\ws\beta\llvm-project\llvm\test\Analysis\ScalarEvolution\nsw.ll

Event Timeline

fhahn created this revision.May 11 2020, 2:03 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 11 2020, 2:03 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
nlopes added a subscriber: aqjune.May 11 2020, 2:22 PM
fhahn updated this revision to Diff 263283.May 11 2020, 2:47 PM

Actually check all instructions between I and the end of the block.

Despite the fact that this takes an "Instruction*", it's not really trying to compute some property of users of that instruction; it's trying compute some property of users of the equivalent SCEV expression. So any computation based on the position of the instruction in the loop is not going to give the result you want: even if users of the given instruction can be assumed to be never poison, you can't generalize that property to all equivalent values in the loop.

I think there might be another way to handle the testcase, though. If the input instruction is a PHI node, we can use PHI-specific reasoning. In this context, we don't care if the base value is poison, I think; we're trying to compute a property of the increment. And the "add nsw" can't be poison because it's also used by the loop latch of the previous iteration: if it's poison, we can't reach the current iteration, regardless of whether the loop has other exits.

llvm/lib/Analysis/ScalarEvolution.cpp
6180

You're not checking "all instructions between I and the end of the block".

fhahn added a comment.May 12 2020, 1:13 PM

Despite the fact that this takes an "Instruction*", it's not really trying to compute some property of users of that instruction; it's trying compute some property of users of the equivalent SCEV expression. So any computation based on the position of the instruction in the loop is not going to give the result you want: even if users of the given instruction can be assumed to be never poison, you can't generalize that property to all equivalent values in the loop.

Thanks Eli! I missed that the instruction here is indeed not suitable for position based inference. It seems a bit unfortunate to me that we fail to make use of that information, until we actually construct a equivalent expression for which it does not hold :( Not sure how worthwhile/feasible it would be to try to invalidate the information. Do you know if something like that was explored previously?

I think there might be another way to handle the testcase, though. If the input instruction is a PHI node, we can use PHI-specific reasoning. In this context, we don't care if the base value is poison, I think; we're trying to compute a property of the increment. And the "add nsw" can't be poison because it's also used by the loop latch of the previous iteration: if it's poison, we can't reach the current iteration, regardless of whether the loop has other exits.

Sounds good! I also explored something similar earlier, but somehow thought the current version of the patch seemed a bit more direct (but I missed the bit about not being able to use the location here). I'll update the patch tomorrow.

Not sure how worthwhile/feasible it would be to try to invalidate the information. Do you know if something like that was explored previously?

I don't think that's something anyone has looked at. I have no idea how it would work.

On a more general topic, there's been some interest in changing the way poison flags on SCEV expressions work, so it's possible to have both a poison and non-poison SCEV computing the same value. But nobody has actually tried to implement it, I think.

fhahn added a comment.May 15 2020, 9:49 AM

I think there might be another way to handle the testcase, though. If the input instruction is a PHI node, we can use PHI-specific reasoning. In this context, we don't care if the base value is poison, I think; we're trying to compute a property of the increment. And the "add nsw" can't be poison because it's also used by the loop latch of the previous iteration: if it's poison, we can't reach the current iteration, regardless of whether the loop has other exits.

Sounds good! I also explored something similar earlier, but somehow thought the current version of the patch seemed a bit more direct (but I missed the bit about not being able to use the location here). I'll update the patch tomorrow.

Hm I think the reasoning does not really help here unfortunately, as isAddRecNeverPoison takes the increment instruction of the AddRec I think .

IIUC the problematic case is if the have an %iv.next = add nsw %iv, 1, we know that %iv cannot be poison (and %iv.next from the previous iteration also cannot be poison). But %iv.next could overflow in the current iteration and then take an abnormal exit, hence we cannot assume the AddRec never overflows.

On a more general topic, there's been some interest in changing the way poison flags on SCEV expressions work, so it's possible to have both a poison and non-poison SCEV computing the same value. But nobody has actually tried to implement it, I think.

Would the idea here be allowing to use overflow flags for expressions depending on where an expression is evaluated/used? (for example the latch branch for the trip count computation)

Would the idea here be allowing to use overflow flags for expressions depending on where an expression is evaluated/used? (for example the latch branch for the trip count computation)

I guess it could vary based on that. The discussion has mostly centered around making the overflow flags vary depending on whether the IR instruction is marked nsw/nuw, but that isn't the only possible input.

fhahn planned changes to this revision.May 19 2020, 2:07 PM

Would the idea here be allowing to use overflow flags for expressions depending on where an expression is evaluated/used? (for example the latch branch for the trip count computation)

I guess it could vary based on that. The discussion has mostly centered around making the overflow flags vary depending on whether the IR instruction is marked nsw/nuw, but that isn't the only possible input.

Thanks for clarifying! IIUC the idea would be to de-couple overflow flags from directly storing them in the expressions and have a way to pass them in depending on the context. I'll try to look into that when I have a bit more time.