This is an archive of the discontinued LLVM Phabricator instance.

[X86] Fix PR39658: avoid duplicated successors in condibr merge
Needs RevisionPublic

Authored by xur on Nov 15 2018, 11:35 AM.

Details

Summary

This is to fix PR39658 where duplicated successors (and phi operands) causing miscompile.

Diff Detail

Event Timeline

xur created this revision.Nov 15 2018, 11:35 AM
mkazantsev requested changes to this revision.Nov 15 2018, 9:35 PM
mkazantsev added inline comments.
lib/Target/X86/X86CondBrFolding.cpp
230

It is just wrong. In PR39658, we are dealing with the following situation:

A:
  sub x, y
  jg C
  jmp B
B:
  sub x, y
  jmp C
C:
  Phi [v1, A], [v2, B]

You are trying to merge A and B together, but they cannot be merged specifically for the reason that it is actually important from which block we came to C. The value of the Phi node depends on this. You cannot just say that we no longer come from B and therefore Phi never takes value v2. It does take this value if x was less or equal than y.

This patch is not helping the ogirinal miscompile. I think that the right solution is to prohibit merging blocks A and B if there is a Phi which has different incoming values for these blocks.

test/CodeGen/X86/pr39658.ll
11

Please use FileCheck to assert that the contents of Phis in question is correct.

This revision now requires changes to proceed.Nov 15 2018, 9:35 PM
vsk added a subscriber: vsk.Nov 17 2018, 7:23 PM
xur updated this revision to Diff 174854.Nov 20 2018, 4:19 PM

This is the updated version. We will bail out the optimization is there are PHIs preventing the merge.

@Max: could you tell you real test case to see if this fixes the problem.

Note that this patch still leave this optimization off by default. I will have separated patch to turn if on later.

xbolva00 added inline comments.
lib/Target/X86/X86CondBrFolding.cpp
275

Remove brackets?

377

Extra newline

xur updated this revision to Diff 174855.Nov 20 2018, 4:42 PM

Uploaded a wrong patch. This is the patch I intended to send.

mkazantsev requested changes to this revision.Nov 20 2018, 10:10 PM

I confirm that this helps all original miscompile tests I have. I am OK with the approach in general, but have some comments about implementation. I think it should be done either faster and easier (with the same scope) or made less conservative.

lib/Target/X86/X86CondBrFolding.cpp
145

A Phi cannot be the last instruction in a block, so MI != ME is redundant.

152

You are just checking that a Phi has inputs from both MBB and RootMBB, and you check it for every Phi. It actually makes no sense: all Phis either have inputs from these two blocks or they don't.

This is actually a very conservative check. Even if you have these two blocks as predecessors, but the *same* value comes to this Phi from these blocks, then this particular Phi does not prevent you from folding.

So you should pick one of two approaches:

  1. Conservative approach: do the check you are doing now, but for one Phi only. It makes no sense to check incoming blocks for all Phis because they all have the same set of incoming blocks. I am not familiar with MBBs well enough, but I guess it can be done by just checking if both MBB and RootMBB are in set of our blocks' predecessors.
  2. General approach: do checks for every Phi, but only return true if different values come from RootMBB and MBB to a Phi.
This revision now requires changes to proceed.Nov 20 2018, 10:10 PM
xur marked an inline comment as done.Nov 21 2018, 10:20 AM
xur added inline comments.
lib/Target/X86/X86CondBrFolding.cpp
152

your comments make a lot of sense. I would prefer to use the conservative approach:
(1) I don't think the general approach will touch many more cases -- they are rare.
(2) there does not seem to existing a function to compare phi values in general. I also need to remove duplicated phi-operands after updating. I don't feel it worthy for all the code needed.

For the conservative approach, as you suggested, I still check phi, but one only. I don't think checking the blocks' predecessors is better here. There are cases that we have both MBB and RootMBB as the predecessors but there is no PHI.

xur updated this revision to Diff 174959.Nov 21 2018, 11:45 AM

Integrated Max's review comments.

mkazantsev requested changes to this revision.Nov 21 2018, 8:45 PM
mkazantsev added inline comments.
lib/Target/X86/X86CondBrFolding.cpp
152

Should be llvm::find_if(MBBI->predecessors(), ..., not successors.

test/CodeGen/X86/pr39658.ll
16

I would rather check Phi nodes we used to modify improperly, not jump instructions that can accidentally be matched in other blocks.

This revision now requires changes to proceed.Nov 21 2018, 8:45 PM