This is an archive of the discontinued LLVM Phabricator instance.

[clang][dataflow] Use a dedicated bool to encode which branch was taken
Needs RevisionPublic

Authored by samestep on Jul 21 2022, 7:00 AM.

Details

Summary

This is a continuation of D129289 using @sgatev's feedback.

This patch attempts to resolve a FIXME in DataflowEnvironment.cpp about merging BoolValues when the two flow conditions are not mutually exclusive. The issue here is that we are using the truth value of each flow condition as a proxy for the idea of whether or not we took that branch, which breaks down on backedges.

To try to resolve the issue, this patch creates one additional AtomicBoolValue to explicitly represent which branch we took, and uses that directly within mergeDistinctValues. As currently written, this doesn't quite seem to work: the JoinBackedge test added by this patch fails both before and after the patch is applied.

Diff Detail

Event Timeline

samestep created this revision.Jul 21 2022, 7:00 AM
Herald added a project: Restricted Project. · View Herald Transcript
samestep requested review of this revision.Jul 21 2022, 7:00 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 21 2022, 7:00 AM
Herald added a subscriber: cfe-commits. · View Herald Transcript
samestep edited the summary of this revision. (Show Details)Jul 21 2022, 7:02 AM
samestep added reviewers: ymandel, sgatev, gribozavr2.
ymandel added inline comments.Jul 22 2022, 7:11 AM
clang/unittests/Analysis/FlowSensitive/DataflowAnalysisContextTest.cpp
504–506

I'm a bit concerned by the need to update this (essentially) unrelated test. It implies the test is depending on implementation details that it shouldn't be concerned with.

Not for this patch, but if you have thoughts on how to simplify this test to do what it needs w/o being tied to the details of how joins work, that would be appreciated. At least, it seems worth a FIXME.

thanks

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
1202

should we also test the inverse?

EXPECT_FALSE(Env.flowConditionImplies(Env.makeNot(FooVal)));

That is, I would think we want to show that neither is provable.

samestep added inline comments.Jul 22 2022, 7:15 AM
clang/unittests/Analysis/FlowSensitive/DataflowAnalysisContextTest.cpp
504–506

Agreed, this test seems a bit awkward; in this patch I was just focusing on updating it instead of rethinking it.

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
1202

Sure, that makes sense; if I remember correctly, the inverse of FooVal is indeed not provable already. You're right that it would be good to test both here, though.

gribozavr2 requested changes to this revision.Jul 26 2022, 5:23 AM

Sorry, could you rebase the patch? It does not apply cleanly anymore.

This revision now requires changes to proceed.Jul 26 2022, 5:23 AM
samestep updated this revision to Diff 447656.Jul 26 2022, 5:41 AM

Rebase and add Yitzie's assertion

Sorry, could you rebase the patch? It does not apply cleanly anymore.

Done; I didn't see any conflicts when I rebased, but hopefully the issue on your end is resolved now?

@gribozavr2 I rebased again, should work now.

sgatev accepted this revision.Jul 28 2022, 7:39 AM
sgatev added inline comments.
clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
105

We should probably pass TookSecondBranch here so that models can also use it in the implementation of merge. Could be in a follow up, but let's leave a FIXME.

samestep updated this revision to Diff 448405.Jul 28 2022, 11:53 AM

Add FIXME about passing TookSecondBranch to merge

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
105

FIXME added; thanks!

ymandel requested changes to this revision.Sep 9 2022, 10:19 AM

It turns out that this change wasn't necessary. I've deleted the relevant FIXME in https://reviews.llvm.org/rGabc16c7a5b0a63d14172262153608b3d24de957f.

AFAICT, the reason that the new test JoinBackedge fails at HEAD is because we discard the results of analyzing the function body, so the update Foo = false is simply ignored. This hypothesis rests on observing that each block is visited only once during analysis of the test. It's also consistent with the known (broken) behavior of our comparison operator. Interestingly, this is a nicely stark illustration of the unsoundness of our current approach. :( So, this test will be useful in the future when add proper widening.

This revision now requires changes to proceed.Sep 9 2022, 10:19 AM
samestep accepted this revision.Sep 9 2022, 10:21 AM

@ymandel Huh, interesting! I'll go ahead and abandon this patch, then?

@ymandel Huh, interesting! I'll go ahead and abandon this patch, then?

Please. Sorry I didn't catch this earlier!