Miscompile with GVN, load is replaced with wrong value

[mikaelholmen]

llvm commit: d9e5462da6 Reproduce with:

opt bbi-72447_x86.ll -S -o bbi-72447_x86_result.ll -passes='gvn'

bbi-72447_x86.ll.gz bbi-72447_x86_result.ll.gz

I've annotated the instructions in the input bbi-72447_x86.ll as well as in the output bbi-72447_x86_result.ll with what I think is the value of each instruction when executing loops_test, and there we can see that we end up passing 1 to the verify function in the input but after gvn we pass 0 instead. Input:

sw.bb38:                                          ; preds = %while.end
  %cmp43 = icmp eq i16 %i6, 10                                   ; 10 == 10 -> 1
  %conv44 = zext i1 %cmp43 to i16                                ; 1
  tail call void @verify(i16 %conv44)

output:

sw.bb38:                                          ; preds = %while.end
  %cmp43 = icmp eq i16 %i6, 10                                  ; 23130 != 10 -> 0
  %conv44 = zext i1 %cmp43 to i16                               ; 0
  tail call void @verify(i16 %conv44)

It's sort of like the write to %ub in

cond.end.thread:                                  ; preds = %for.body5
  store i16 10, ptr %ub, align 1                           ; 10 -> %ub
  br label %sw.epilog                                      ; -> %sw.epilog

is ignored and gvn instead has used the value written to %ub in %entry instead:

entry:
  %ub = alloca [4 x i16], align 1
  store i16 23130, ptr %ub, align 1

and then propagated this value into this phi

for.body5:                                        ; preds = %sw.epilog46, %entry
  %i62 = phi i16 [ 23130, %entry ], [ %i10, %sw.epilog46 ] ; 23130

With debug printouts GVN says the following:

Merging: cond.end25 into while.body
Inserting edge %while.body -> %while.body
	Reachable %while.body -> %while.body
		NCA == %while.body
Inserting edge %while.body -> %while.end
	Reachable %while.body -> %while.end
		NCA == %while.body
Mark %while.endas affected, CurrentLevel 5
	Successor %sw.epilog46, level = 6
		Marking visited not affected %sw.epilog46
	Successor %sw.epilog46, level = 6
	Successor %sw.bb38, level = 6
		Marking visited not affected %sw.bb38
	Successor %sw.default45, level = 6
		Marking visited not affected %sw.default45
 Next: %sw.default45
	Successor %sw.epilog46, level = 6
 Next: %sw.bb38
	Successor %sw.epilog46, level = 6
 Next: %sw.epilog46
	Successor %for.end54, level = 7
		Marking visited not affected %for.end54
	Successor %for.body5, level = 1
 Next: %for.end54
Updating NCD = %while.body
	IDom(%while.end) = %while.body
Deleting edge %cond.end25 -> %while.body
Deleting edge %cond.end25 -> %while.end
	NCD %while.body, ToIDom %while.body
Deleting reachable %cond.end25 -> %while.end
	Rebuilding subtree
	Top of subtree: %while.body
	Running Semi-NCA
Deleting edge %while.body -> %cond.end25
	NCD %while.body, ToIDom %while.body
IsReachableFromIDom %cond.end25
Deleting unreachable subtree %cond.end25
Erasing node %cond.end25
GVN iteration: 0
Inserting edge %while.body -> %while.body.while.body_crit_edge
Inserting %while.body -> (unreachable) %while.body.while.body_crit_edge
After adding unreachable nodes
Inserted %while.body -> (prev unreachable) %while.body.while.body_crit_edge
Inserting edge %while.body.while.body_crit_edge -> %while.body
	Reachable %while.body.while.body_crit_edge -> %while.body
		NCA == %while.body
Deleting edge %while.body -> %while.body
GVN REMOVING NONLOCAL LOAD:   %i6 = load i16, ptr %arrayidx31, align 1
  Inserted PHI:   %i62 = phi i16 [ 23130, %entry ], [ %i10, %sw.epilog46 ]
  Inserted PHI:   %i61 = phi i16 [ %i62, %cond.end.thread ], [ %mul, %cond.end ]
GVN removed:   %0 = load i16, ptr %arrayidx31, align 1
GVN REMOVING NONLOCAL LOAD:   %i8 = load i16, ptr @g, align 1
GVN removed:   %i8 = load i16, ptr @g, align 1
GVN iteration: 1
GVN removed:   %i5 = phi i16 [ %i, %sw.epilog ], [ poison, %while.body.while.body_crit_edge ]
GVN: load i16 %i10 is clobbered by   store i16 10, ptr %ub, align 1
GVN iteration: 2
GVN: load i16 %i2 is clobbered by   store i16 10, ptr %ub, align 1
GVN: load i16 %i10 is clobbered by   store i16 10, ptr %ub, align 1

[mikaelholmen]

I don't know if this might be related to https://github.com/llvm/llvm-project/issues/30999 but it goes wrong also if turning off PRE with -enable-pre=0 -enable-load-pre=0 so it's at least not exactly the same problem.

[mikaelholmen]

I'm not sure what this means but I noticed that in one GVN iteration it changes the phi in while.body from

  %i5 = phi i16 [ %i, %sw.epilog ], [ 0, %cond.end25 ]

to

  %i5 = phi i16 [ %i, %sw.epilog ], [ poison, %cond.end25 ]

The %cond.end25 to %while.body edge is never taken due to

cond.end25:                                       ; preds = %while.body
  br i1 false, label %while.body, label %while.end            ; -> %while.end

However, if I change the input, so the phi value is already poison:

  %i5 = phi i16 [ %i, %sw.epilog ], [ poison, %cond.end25 ]

then we get the following debug printout

GVN: load i16 %i6 is clobbered by   store i16 10, ptr %ub, align 1

and I think the end result is correct.

With the original input the load is removed and we use the wrong value.

[mikaelholmen]

When it examines the load

%i6 = load i16, ptr %arrayidx31, align 1

it calculates the dependencies with

MD->getNonLocalPointerDependency(Load, Deps);

and then examine each dependency. We get dependencies towards the following 4 BBs and instructions:

DepBB: while.body.while.body_crit_edge
DepInst: null

DepBB: sw.epilog46
DepInst:   %i10 = load i16, ptr %arrayidx49, align 1

DepBB: entry
DepInst:   store i16 23130, ptr %ub, align 1

DepBB: cond.end
DepInst:   store i16 %mul, ptr %arrayidx12, align 1

Especially note there is no dependency towards

cond.end.thread:
  store i16 10, ptr %ub, align 1

None of the dependencies above prevent removing the load

In the experiment where I changed the input from

  %i5 = phi i16 [ %i, %sw.epilog ], [ 0, %cond.end25 ]

to

  %i5 = phi i16 [ %i, %sw.epilog ], [ poison, %cond.end25 ]

(which GVN does itself anyway) I instead get the following 2 dependencies:

DepBB: cond.end.thread
DepInst:   store i16 10, ptr %ub, align 1

DepBB: cond.end
DepInst:   store i16 %mul, ptr %arrayidx12, align 1

and when examining the first one it realizes it clobbers the load and this prevents removing the load.

[bjope]

Here is my current idea for a fix (but GVN is not my usual playground so it would be nice with some second opinions on this):

diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp
index 7cb2fd6098c8..4000d2922f13 100644
--- a/llvm/lib/Transforms/Scalar/GVN.cpp
+++ b/llvm/lib/Transforms/Scalar/GVN.cpp
@@ -1296,7 +1296,10 @@ void GVNPass::AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps,
     if (DeadBlocks.count(DepBB)) {
       // Dead dependent mem-op disguise as a load evaluating the same value
       // as the load in question.
-      ValuesPerBlock.push_back(AvailableValueInBlock::getUndef(DepBB));
+      if (!DepInfo.isDef() && !DepInfo.isClobber())
+        UnavailableBlocks.push_back(DepBB);
+      else
+        ValuesPerBlock.push_back(AvailableValueInBlock::getUndef(DepBB));
       continue;
     }

Not sure exactly how to motivate it, but afaict MemDep can return Deps that are Unknown in cases when it has given up due to some limits, or as (I think) in the reproducer when there is a phi translation failure. And then I think it would be wrong to say that there is an available (even undef) value because there ain't really no def/clobber Dep for the block.

[bjope]

Proposed a patch here: https://reviews.llvm.org/D131776

[mikaelholmen]

Awesome, thank you @nikic and @bjope !