Page MenuHomePhabricator

[GVN] Fix miscompile shown in github issue #57025
AbandonedPublic

Authored by bjope on Aug 12 2022, 7:07 AM.

Details

Reviewers
nikic
fhahn
Summary

Make sure that we are conservative in AnalyzeLoadAvailability when
finding an Unknown memdep, also when the dependent BB is dead.

Fixes: https://github.com/llvm/llvm-project/issues/57025

Diff Detail

Event Timeline

bjope created this revision.Aug 12 2022, 7:07 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 12 2022, 7:08 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
bjope requested review of this revision.Aug 12 2022, 7:08 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 12 2022, 7:08 AM
bjope added inline comments.Aug 12 2022, 7:22 AM
llvm/test/Transforms/GVN/memdep-unknown-deadblocks.ll
49

This was almost correct.
It would have been correct if this phi looked like this instead:

[[VALUE:%.*]] = phi i16 [ 42, [[STORE_IDX_I]] ], [ [[7]], [[STORE_IDX_0]] ]

and then the load in while.end can be eliminated. And then we also would get rid of VALUE2 and DEAD.

But my fix here is not aiming at optimizing this kind of scenario, just to avoid the miscompile we see today.
Current fix makes the result look just like if we would have had

%j = phi i16 [ %i, %store.done ], [ poison, %while.body ]

instead of

%j = phi i16 [ %i, %store.done ], [ 0, %while.body ]

already in the input. Which would have triggered an early remove of that phi in GVN iteration 0. So it does not seem like GVN would eliminate the load by adding a phi in store.done even if cleaning up some of the "stupid" things in the IR such as the dead load and the phi related to the unconditional cond branch.

bjope added a comment.Aug 29 2022, 1:38 AM

Gentle ping!

(Looks like nikic har been away for some time. Do you know anything about this @fhahn, or any idea for additional reviewers? I know that someone is trying to replace MemDep by MemorySSA in this pass, but maybe won't hurt to get things more correct first anyway.)

nikic added a comment.Aug 30 2022, 2:54 AM

I've spent a good bit of time looking into this, and I don't think this patch fixes the right issue.

The core problem seems to be that the store in store.idx.0 is not reported as a def clobber, even though it clearly is on the first loop iteration. The reason we get this result is that we perform an AA query between %arr and %arr.i -- but %arr.i is in a block that that is guarded by %i != 0, so the two are NoAlias.

I'm not entirely sure who is at fault here yet, but probably we shouldn't be using %arr.i as the pointer value here -- while it has the correct value, it is located in an incorrect context.

nikic added a comment.Aug 30 2022, 3:51 AM

The good news is that PHITranslateValue has a MustDominate argument that controls this behavior. If we make MemDep pass MustDominate=true, then this phi translation is no longer performed. The bad news is that this does regress GVN test results...

bjope added a comment.Aug 30 2022, 6:20 AM

Big thanks for looking at this (and I wasn't sure at all about my patch attempt so your solution is probably much better, specially if it also happens to solve our old outstanding issue since 2017 ( https://github.com/llvm/llvm-project/issues/30999 ).

bjope added inline comments.Wed, Aug 31, 6:19 AM
llvm/lib/Transforms/Scalar/GVN.cpp
1297

I've tried replacing this with assert(!DepInfo.isUnknown()) and it seems like that is a totally untested scenario (except for the new test/Transforms/GVN/memdep-unknown-deadblocks.ll test case).

So even if D131776 is a better fix in some sense, I'm still wondering what would be correct to do if getting here with a DepInfo that is Unknown. At least when I looked at this a couple of weeks ago I got the feeling that the behavior without this patch could be wrong and that adding to UnavailableBlocks would be more correct as we do not know if there is a dependent mem-op or not. Or am I missing something.

Given that D131776 probably will hide this code path also for the memdep-unknown-deadblocks.ll test case, then I'm not sure how to motivate this fix. If we never expect to get here with DepInfo.isUnknown, then maybe we should assert on that instead.

I'll try to run some fuzzy testing to see if I can trigger this code path even with the fix from D131776.

nikic added inline comments.Thu, Sep 1, 6:07 AM
llvm/lib/Transforms/Scalar/GVN.cpp
1297

I don't think this code path cares about the value of DepInfo at all. If the block is unreachable, then we can always assume it produces a poison value.

bjope abandoned this revision.Fri, Sep 2, 3:55 AM

Abandoned. Problem was solved in D131776.

llvm/lib/Transforms/Scalar/GVN.cpp
1297

Right. Well, I have been able to trigger this code path with a DepInfo.isUnknown() here, but haven't found any case where the change in this patch makes a difference to the end result (given that I have merged the fix from D131776).

So I'm not doing any further investigation of this right now, and will just abondon this issue.

Btw, thanks a lot for the help (and with the more correct fix in D131776). Very much appreciated!