wrong code at -O1 and above on x86_64-linux-gnu

[zhendongsu]

Bugzilla Link	51125
Resolution	FIXED
Resolved on	Oct 11, 2021 20:29
Version	trunk
OS	All
Blocks	#51489
CC	@LebedevRI,@nikic,@rotateright,@TNorthover,@tstellar
Fixed by commit(s)	909cba9 84a3be8

Extended Description

[505] % clangtk -v
clang version 13.0.0 (https://github.com/llvm/llvm-project.git 5df4849)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /local/suz-local/opfuzz/bin
Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/8
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/6
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/6.5.0
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/7
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/7.5.0
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/8
Selected GCC installation: /usr/lib/gcc/x86_64-linux-gnu/7.5.0
Candidate multilib: .;@m64
Candidate multilib: 32;@m32
Candidate multilib: x32;@MX32
Selected multilib: .;@m64
[506] %
[506] % clangtk -O0 small.c; ./a.out
1
[507] % clangtk -O1 small.c
[508] % ./a.out
-1
[509] % cat small.c
int printf(const char *, ...);
int a = 1, b;
int main() {
L:
b = a;
if (a) {
unsigned c = a;
a = -1;
if (a == c)
goto L;
}
printf("%d\n", b);
return 0;
}

[zhendongsu]

From Compiler Explorer: https://godbolt.org/z/nMz5Pne4s

[zhendongsu]

A slightly different test that is miscompiled at -O1 and above:

[512] % clangtk -O0 small.c; ./a.out
1
[513] % clangtk -O1 small.c; ./a.out
-1
[514] % clangtk -Os small.c; ./a.out
-1
[515] % clangtk -O2 small.c; ./a.out
-1
[516] % clangtk -O3 small.c; ./a.out
-1
[517] % cat small.c
#include <stdio.h>
int a = 1;
int main() {
int b;
L:
b = a;
if (a) {
unsigned c = a;
a = -1;
if (a == c)
goto L;
}
printf("%d\n", b);
return 0;
}

[zhendongsu]

Bisects to commit
932e3d9

[rotateright]

Bisects to commit
https://github.com/llvm/llvm-project/commit/
932e3d9

That looks like a misleading bisection.
The bug appears to be in -simplifycfg:

https://godbolt.org/z/xcanbhv3v
https://alive2.llvm.org/ce/z/LA_SzY

[rotateright]

https://alive2.llvm.org/ce/z/LA_SzY

I reduced that slightly (unused phi instruction) and committed a test for this bug here:
https://reviews.llvm.org/rGfbe64f136f76

We have extended the functionality of FoldBranchToCommonDest() to allow extra instructions (there are some stale function comments that should be updated), but I don't know what the best fix for this bug will be.

As noted in the test comment, we are updating the phi in the successor with a value from the new/updated block, but that's wrong for a load of memory that might have been over-written.

cc'ing Roman and Nikita in case they can see an obvious fix.

[nikic]

Possibly this will do? I don't think we should be rewriting uses of bonus instructions in the same block.

diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
index c0a31e3bdca9..ed8b3097ee84 100644
--- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -1106,8 +1106,6 @@ static void CloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(
auto *UI = cast(U.getUser());
if (UI->getParent() != PredBlock)
SSAUpdate.RewriteUseAfterInsertions(U);

•  else // Use is in the same block as, and comes before, NewBonusInst.
  

•    SSAUpdate.RewriteUse(U);
  

  }
  }
  }
  diff --git a/llvm/test/Transforms/SimplifyCFG/fold-branch-to-common-dest.ll b/llvm/test/Transforms/SimplifyCFG/fold-branch-to-common-dest.ll
  index 5ce7d600dceb..b0c0cbf112a7 100644
  --- a/llvm/test/Transforms/SimplifyCFG/fold-branch-to-common-dest.ll
  +++ b/llvm/test/Transforms/SimplifyCFG/fold-branch-to-common-dest.ll
  @@ -972,9 +972,8 @@ define void @​pr49510() {
  ; CHECK-NEXT: [[TOBOOL_OLD:%.]] = icmp ne i16 [[DOTOLD]], 0
  ; CHECK-NEXT: br i1 [[TOBOOL_OLD]], label [[LAND_RHS:%.]], label [[FOR_END:%.]]
  ; CHECK: land.rhs:
  -; CHECK-NEXT: [[DOTMERGE:%.]] = phi i16 [ [[TMP0:%.]], [[LAND_RHS]] ], [ [[DOTOLD]], [[ENTRY:%.]] ]
  -; CHECK-NEXT: [[CMP:%.]] = icmp slt i16 [[DOTMERGE]], 0
  -; CHECK-NEXT: [[TMP0]] = load i16, i16 @​global_pr49510, align 1
  +; CHECK-NEXT: [[CMP:%.]] = icmp slt i16 [[DOTOLD]], 0
  +; CHECK-NEXT: [[TMP0:%.]] = load i16, i16* @​global_pr49510, align 1
  ; CHECK-NEXT: [[TOBOOL:%.]] = icmp ne i16 [[TMP0]], 0
  ; CHECK-NEXT: [[OR_COND:%.]] = select i1 [[CMP]], i1 [[TOBOOL]], i1 false
  ; CHECK-NEXT: br i1 [[OR_COND]], label [[LAND_RHS]], label [[FOR_END]]
  @@ -1010,15 +1009,14 @@ define i32 @​pr51125() {
  ; CHECK-NEXT: [[ISZERO_OLD:%.]] = icmp eq i32 [[LD_OLD]], 0
  ; CHECK-NEXT: br i1 [[ISZERO_OLD]], label [[EXIT:%.]], label [[L2:%.]]
  ; CHECK: L2:
  -; CHECK-NEXT: [[LD_MERGE:%.]] = phi i32 [ [[LD:%.]], [[L2]] ], [ [[LD_OLD]], [[ENTRY:%.]] ]
  ; CHECK-NEXT: store i32 -1, i32* @​global_pr51125, align 4
  -; CHECK-NEXT: [[CMP:%.]] = icmp ne i32 [[LD_MERGE]], -1
  -; CHECK-NEXT: [[LD]] = load i32, i32 @​global_pr51125, align 4
  +; CHECK-NEXT: [[CMP:%.]] = icmp ne i32 [[LD_OLD]], -1
  +; CHECK-NEXT: [[LD:%.]] = load i32, i32* @​global_pr51125, align 4
  ; CHECK-NEXT: [[ISZERO:%.]] = icmp eq i32 [[LD]], 0
  ; CHECK-NEXT: [[OR_COND:%.]] = select i1 [[CMP]], i1 true, i1 [[ISZERO]]
  ; CHECK-NEXT: br i1 [[OR_COND]], label [[EXIT]], label [[L2]]
  ; CHECK: exit:
  -; CHECK-NEXT: [[R:%.]] = phi i32 [ [[LD]], [[L2]] ], [ [[LD_OLD]], [[ENTRY]] ]
  +; CHECK-NEXT: [[R:%.]] = phi i32 [ [[LD]], [[L2]] ], [ [[LD_OLD]], [[ENTRY:%.*]] ]
  ; CHECK-NEXT: ret i32 [[R]]
  ;
  entry:

[rotateright]

Possibly this will do? I don't think we should be rewriting uses of bonus
instructions in the same block.

diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
index c0a31e3bdca9..ed8b3097ee84 100644
--- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -1106,8 +1106,6 @@ static void
CloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(
auto *UI = cast(U.getUser());
if (UI->getParent() != PredBlock)
SSAUpdate.RewriteUseAfterInsertions(U);

•  else // Use is in the same block as, and comes before, NewBonusInst.
  

•    SSAUpdate.RewriteUse(U);
  

We might want to do that (no test regressions AFAICT), but no, that doesn't appear to fix the bug in the reduced IR, and it doesn't change the miscompile in the C example in the description.

We're still using the new loaded value in the successor phi, and that's still wrong because we stored a different value there before the load.

[nikic]

Oh right, I completely misunderstood what the problem here is.

[rotateright]

I think we need to do something stronger when checking if we can do this fold at all. I don't know if there's a better way to phrase it, but I have this so far:

diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
index c0a31e3bdca9..703c863ad221 100644
--- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -3271,8 +3271,18 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI, DomTreeUpdater *DTU,
// Ignore dbg intrinsics, and the terminator.
if (isa(I) || isa(I))
continue;

• // I must be safe to execute unconditionally.
• if (!isSafeToSpeculativelyExecute(&I))

• // I must be safe to execute unconditionally and predecessors must have

• // no side effects that could alter the result of speculated instructions.

• auto HasSideEffects = [](BasicBlock *BB) {

•  return any_of(*BB, [](const Instruction &I) {
  

•    return I.mayWriteToMemory() || I.mayHaveSideEffects();
  

•  });
  

• };

• if (!isSafeToSpeculativelyExecute(&I) ||

•    (I.mayReadFromMemory() && any_of(Preds, [&](BasicBlock *PredBB) {
  

•       return HasSideEffects(PredBB);
  

•     })))
   return false;
  

  // Account for the cost of duplicating this instruction into each

[LebedevRI]

We just need to make the SSA flow explicit via PHI nodes,
before doing the cloning.

I think we need to do something stronger when checking if we can do this
fold at all. I don't know if there's a better way to phrase it, but I have
this so far:

diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
index c0a31e3bdca9..703c863ad221 100644
--- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -3271,8 +3271,18 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI,
DomTreeUpdater *DTU,
// Ignore dbg intrinsics, and the terminator.
if (isa(I) || isa(I))
continue;

• // I must be safe to execute unconditionally.
• if (!isSafeToSpeculativelyExecute(&I))

• // I must be safe to execute unconditionally and predecessors must have

• // no side effects that could alter the result of speculated
  instructions.

• auto HasSideEffects = [](BasicBlock *BB) {

•  return any_of(*BB, [](const Instruction &I) {
  

•    return I.mayWriteToMemory() || I.mayHaveSideEffects();
  

•  });
  

• };

• if (!isSafeToSpeculativelyExecute(&I) ||

•    (I.mayReadFromMemory() && any_of(Preds, [&](BasicBlock *PredBB) {
  

•       return HasSideEffects(PredBB);
  

•     })))
   return false;
  

  // Account for the cost of duplicating this instruction into each

I don't think this makes sense.

[rotateright]

We just need to make the SSA flow explicit via PHI nodes,
before doing the cloning.

I've been staring at the SSAUpdater API, but I'm not seeing it. Do you want to have a try at implementing that?

[LebedevRI]

We just need to make the SSA flow explicit via PHI nodes,
before doing the cloning.

I've been staring at the SSAUpdater API, but I'm not seeing it. Do you want
to have a try at implementing that?

https://reviews.llvm.org/D106317

[LebedevRI]

Fixed in 78af5cb, thanks.
Could you please see which other bugs duplicate bugs got fixed by this?

[LebedevRI]

*** Bug llvm/llvm-bugzilla-archive#51385 has been marked as a duplicate of this bug. ***

[LebedevRI]

Forgot to actually stage the test change after precommitting it,
so relanded everything in 3d9beef.