Incorrect result with -O1 -march=skx

[Vsevolod-Livinskij]

Bugzilla Link	52335
Version	trunk
OS	Linux
CC	@dbabokin,@topperc,@RKSimon,@phoebewang,@regehr,@rotateright,@Vsevolod-Livinskij

Extended Description

It looks like LoopVectorizePass introduces changes that uncover a bug in the backend. The transformation was verified with alive2. I've attached C++ and LLVM IR reproducers.

C++ reproducer:

// func.cpp
extern int var_3;
extern bool var_23;
extern int arr_12[];
extern short arr_13[];
void test() {
#pragma clang loop vectorize_predicate(enable)
  for (char a = 4; a < var_3; a++) {
    arr_13[a] = arr_12[a - 3];
    var_23 = arr_12[a - 1];
  }
}

// driver.cpp 
#include <stdio.h>

int var_3 = 24;
bool var_23 = 1;
int arr_12 [25];
unsigned short arr_13 [25];

void test();

int main() {
    for (size_t i_0 = 0; i_0 < 25; ++i_0)
        arr_12 [i_0] = 1;
    test();
    printf("%d\n", (int)var_23);
}

$ clang++ -O0 -march=skx func.cpp driver.cpp && sde -skx -- ./a.out
1
$ clang++ -O1 -march=skx func.cpp driver.cpp && sde -skx -- ./a.out
0

LLVM IR Reproducer:

; ModuleID = 'func.cpp'
source_filename = "func.cpp"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

@var_3 = external dso_local local_unnamed_addr global i32, align 4
@arr_12 = external dso_local local_unnamed_addr global [0 x i32], align 4
@arr_13 = external dso_local local_unnamed_addr global [0 x i16], align 2
@var_23 = external dso_local local_unnamed_addr global i8, align 1

; Function Attrs: mustprogress nofree norecurse nosync nounwind uwtable
define dso_local void @_Z4testv() local_unnamed_addr #0 {
entry:
  %0 = load i32, i32* @var_3, align 4, !tbaa !3
  %cmp13 = icmp sgt i32 %0, 4
  br i1 %cmp13, label %for.body.preheader, label %for.cond.cleanup

for.body.preheader:                               ; preds = %entry
  br label %for.body

for.cond.for.cond.cleanup_crit_edge:              ; preds = %for.body
  %conv15.lcssa = phi i32 [ %conv15, %for.body ]
  %sub6 = add nsw i32 %conv15.lcssa, -1
  %idxprom7 = sext i32 %sub6 to i64
  %arrayidx8 = getelementptr inbounds [0 x i32], [0 x i32]* @arr_12, i64 0, i64 %idxprom7
  %1 = load i32, i32* %arrayidx8, align 4, !tbaa !3
  %tobool = icmp ne i32 %1, 0
  %frombool = zext i1 %tobool to i8
  store i8 %frombool, i8* @var_23, align 1, !tbaa !7
  br label %for.cond.cleanup

for.cond.cleanup:                                 ; preds = %for.cond.for.cond.cleanup_crit_edge, %entry
  ret void

for.body:                                         ; preds = %for.body.preheader, %for.body
  %conv15 = phi i32 [ %conv, %for.body ], [ 4, %for.body.preheader ]
  %a.014 = phi i8 [ %inc, %for.body ], [ 4, %for.body.preheader ]
  %sub = add nsw i32 %conv15, -3
  %idxprom = sext i32 %sub to i64
  %arrayidx = getelementptr inbounds [0 x i32], [0 x i32]* @arr_12, i64 0, i64 %idxprom
  %2 = load i32, i32* %arrayidx, align 4, !tbaa !3
  %conv2 = trunc i32 %2 to i16
  %idxprom3 = sext i8 %a.014 to i64
  %arrayidx4 = getelementptr inbounds [0 x i16], [0 x i16]* @arr_13, i64 0, i64 %idxprom3
  store i16 %conv2, i16* %arrayidx4, align 2, !tbaa !9
  %inc = add i8 %a.014, 1
  %conv = sext i8 %inc to i32
  %cmp = icmp sgt i32 %0, %conv
  br i1 %cmp, label %for.body, label %for.cond.for.cond.cleanup_crit_edge, !llvm.loop !11
}

attributes #0 = { mustprogress nofree norecurse nosync nounwind uwtable "frame-pointer"="none" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="skx" "target-features"="+adx,+aes,+avx,+avx2,+avx512bw,+avx512cd,+avx512dq,+avx512f,+avx512vl,+bmi,+bmi2,+clflushopt,+clwb,+crc32,+cx16,+cx8,+f16c,+fma,+fsgsbase,+fxsr,+invpcid,+lzcnt,+mmx,+movbe,+pclmul,+pku,+popcnt,+prfchw,+rdrnd,+rdseed,+sahf,+sse,+sse2,+sse3,+sse4.1,+sse4.2,+ssse3,+x87,+xsave,+xsavec,+xsaveopt,+xsaves" }

!llvm.module.flags = !{#0, !​1}
!llvm.ident = !{#2}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 7, !"uwtable", i32 1}
!2 = !{!"clang version 14.0.0 (https://github.com/llvm/llvm-project.git 2d77b272a8f9b5b89b022628ca30b6b896a8f725)"}
!3 = !{#4, !4, i64 0}
!4 = !{!"int", !5, i64 0}
!5 = !{!"omnipotent char", !6, i64 0}
!6 = !{!"Simple C++ TBAA"}
!7 = !{#8, !8, i64 0}
!8 = !{!"bool", !5, i64 0}
!9 = !{#10, !10, i64 0}
!10 = !{!"short", !5, i64 0}
!11 = distinct !{#11, !12, !13, !14, !15}
!12 = !{!"llvm.loop.mustprogress"}
!13 = !{!"llvm.loop.unroll.disable"}
!14 = !{!"llvm.loop.vectorize.predicate.enable", i1 true}
!15 = !{!"llvm.loop.vectorize.enable", i1 true}

$ clang++ -O0 ok.ll driver.cpp && sde -skx -- ./a.out
1
$ opt -loop-vectorize ok.ll > opt.ll && clang++ -O0 opt.ll driver.cpp && sde -skx -- ./a.out
0

LLVM version:
clang version 14.0.0 (https://github.com/llvm/llvm-project.git 2d77b27)

[phoebewang]

Gdb to the binary, the bad one has 4 extra offset than the good one to arr_12 in the last assignment to var_23.
By reading the assembly, I found the dubious code snippet:

mov -0x2c(%rsp),%eax
sub $0x1,%eax
add $0x4,%eax ; <-- Here the add seems superfluous
...
mov %eax,-0x60(%rsp)
...
mov -0x60(%rsp),%eax
add $0xffffffff,%eax
cltq
cmpl $0x0,0x601040(,%rax,4) ; <-- rax here actually is "a - 1"

The MIR after ISel is:

bb.5.middle.block:
; predecessors: %bb.4
successors: %bb.7, %bb.6

%84:gr32 = SUB32ri8 %2:gr32(tied-def 0), 1, implicit-def $eflags
%83:gr32 = ADD32ri8 %84:gr32(tied-def 0), 4, implicit-def $eflags
%81:gr8 = MOV8ri 1
TEST8ri %81:gr8, 1, implicit-def $eflags
JCC_1 %bb.7, 5, implicit $eflags

But I haven't found the corresponding BB during ISel from the log. The only one has ADD32ri8 is below. But I didn't find any clue on the relationship.

===== Instruction selection ends:
Selected selection DAG: %bb.4 '_Z4testv:vector.body'
SelectionDAG has 29 nodes:
t0: ch = EntryToken
t3: i32,ch = CopyFromReg t0, Register:i32 %6
t67: i32 = Register $noreg
t4: i32,i32 = ADD32ri8 t3, TargetConstant:i32<4>
t19: ch = CopyToReg t0, Register:i32 %74, t4
t20: i8 = EXTRACT_SUBREG t3, TargetConstant:i32<1>
t22: i8,i32 = ADD8ri t20, TargetConstant:i8<4>
t36: ch = CopyToReg t0, Register:i8 %60, t22
t59: v8i32 = VPBROADCASTDrZ256rr t3
t56: v8i32,ch = VMOVDQA64Z256rm<Mem:(load (s256) from constant-pool)> Register:i64 $rip, TargetConstant:i8<1>, Register:i64 $noreg, TargetConstantPool:i32<<8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>> 0, Register:i16 $noreg, t0
t39: v8i32 = VPADDDZ256rr t59, t56
t41: v8i32,ch = CopyFromReg t0, Register:v8i32 %5
t43: v8i1 = VPCMPUDZ256rri t39, t41, TargetConstant:i8<2>
t45: ch = CopyToReg t0, Register:v8i1 %52, t43
t46: ch = TokenFactor t19, t36, t45

[phoebewang]

I found the dubious "sub 1" and "add 4" in the opt.ll. Backend doesn't do anything special for them:

middle.block: ; preds = %vector.body
%cast.cmo = sub i32 %n.vec, 1
%ind.escape = add i32 4, %cast.cmo
br i1 true, label %for.cond.for.cond.cleanup_crit_edge, label %scalar.ph

And there is no relevance to skx. Modified the attributes in opt.ll to other targets can reproduce it too.

@​Vsevolod, how did you verify it with alive2? Is it possible the problem of LoopVectorizePass?

[Vsevolod-Livinskij]

And there is no relevance to skx. Modified the attributes in opt.ll to
other targets can reproduce it too.

That is weird. The initial C++ error is reproducible for skx only. There might be multiple bugs in the same pass, and they switch between each other if we alter optimization sequence.

@​Vsevolod, how did you verify it with alive2?

I used alive2 translation validation mode on files before and after LoopVectorizePass.

$ opt -loop-vectorize -S before.ll > after.ll).
$ alive-tv before.ll after.ll
...
Transformation seems to be correct!

Summary:
1 correct transformations
0 incorrect transformations
0 failed-to-prove transformations
0 Alive2 errors

Is it possible the problem of LoopVectorizePass?

LoopVectorizePass is certainly involved in this bug, but I don't know exactly how.
It exposes wrong result, but that might be caused by error in pass itself, backend, or interaction with other optimizations.

[rickyz]

Here's a small repro:

#include <stddef.h>
#include <stdint.h>

int test(int* arr, size_t n) {
  int value = 0;
#pragma clang loop vectorize_predicate(enable)
  for (uint8_t i = 1; i < n; ++i) {
    arr[i - 1] = 0x41;
    value = arr[i];
  }
  return value;
}

Note that this C no longer miscompiles on the latest clang build from git main, as the InstCombine pass now changes i to an i64 that is masked with 0xff. This seems to prevent LoopVectorizationLegality from detecting i as an induction variable, so the loop cannot be vectorized at all. I ended up having to extract IR from an older version of clang to repro this bug (see repro.ll).

$ opt -passes=loop-vectorize repro.ll -S > after_vectorize.ll # See attached after_vectorize.ll.

The loop vectorization pass generates incorrect code. The for.cond.for.cond.cleanup_crit_edge block outside of the loop is responsible for loading arr[i] from the last iteration into value. When this block is reached from the vectorized loop via middle.block, the index for the load ends up equaling %n.vec, which is the number of loop iterations (n - 1) rounded up to the next multiple of 4. When the number of iterations isn't divisible by 4, this causes the load to read past the end of arr.

Reading through https://github.com/llvm/llvm-project/blob/04d083b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp, we see that %n.vec is generated here:

llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

Lines 3144 to 3191 in 04d083b

	Value *InnerLoopVectorizer::getOrCreateVectorTripCount(Loop *L) {
	if (VectorTripCount)
	return VectorTripCount;
	Value *TC = getOrCreateTripCount(L);
	IRBuilder<> Builder(L->getLoopPreheader()->getTerminator());
	Type *Ty = TC->getType();
	// This is where we can make the step a runtime constant.
	Value *Step = createStepForVF(Builder, Ty, VF, UF);
	// If the tail is to be folded by masking, round the number of iterations N
	// up to a multiple of Step instead of rounding down. This is done by first
	// adding Step-1 and then rounding down. Note that it's ok if this addition
	// overflows: the vector induction variable will eventually wrap to zero given
	// that it starts at zero and its Step is a power of two; the loop will then
	// exit, with the last early-exit vector comparison also producing all-true.
	if (Cost->foldTailByMasking()) {
	assert(isPowerOf2_32(VF.getKnownMinValue() * UF) &&
	"VF*UF must be a power of 2 when folding tail by masking");
	assert(!VF.isScalable() &&
	"Tail folding not yet supported for scalable vectors");
	TC = Builder.CreateAdd(
	TC, ConstantInt::get(Ty, VF.getKnownMinValue() * UF - 1), "n.rnd.up");
	}
	// Now we need to generate the expression for the part of the loop that the
	// vectorized body will execute. This is equal to N - (N % Step) if scalar
	// iterations are not required for correctness, or N - Step, otherwise. Step
	// is equal to the vectorization factor (number of SIMD elements) times the
	// unroll factor (number of SIMD instructions).
	Value *R = Builder.CreateURem(TC, Step, "n.mod.vf");
	// There are cases where we *must* run at least one iteration in the remainder
	// loop. See the cost model for when this can happen. If the step evenly
	// divides the trip count, we set the remainder to be equal to the step. If
	// the step does not evenly divide the trip count, no adjustment is necessary
	// since there will already be scalar iterations. Note that the minimum
	// iterations check ensures that N >= Step.
	if (Cost->requiresScalarEpilogue(VF)) {
	auto *IsZero = Builder.CreateICmpEQ(R, ConstantInt::get(R->getType(), 0));
	R = Builder.CreateSelect(IsZero, Step, R);
	}
	VectorTripCount = Builder.CreateSub(TC, R, "n.vec");
	return VectorTripCount;
	}

Usually, the vector trip count is equal to the trip count rounded down to the next multiple of the step. However, the loop vectorization code supports "tail loop folding," where the final iteration of the vectorized loop is able to handle a number of elements than less than the step size by masking the vector operations appropriately. In that case, the vector trip count is equal to the trip count rounded /up/ to the next multiple of the step size.

The vector trip count is passed here

llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

Lines 4104 to 4106 in 04d083b

	fixupIVUsers(Entry.first, Entry.second,
	getOrCreateVectorTripCount(LI->getLoopFor(LoopVectorBody)),
	IVEndValues[Entry.first], LoopMiddleBlock);

which ends up generating the index computation in middle.block here:

llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

Lines 3759 to 3787 in 04d083b

	// An external user of the penultimate value need to see EndValue - Step.
	// The simplest way to get this is to recompute it from the constituent SCEVs,
	// that is Start + (Step * (CRD - 1)).
	for (User *U : OrigPhi->users()) {
	auto *UI = cast<Instruction>(U);
	if (!OrigLoop->contains(UI)) {
	const DataLayout &DL =
	OrigLoop->getHeader()->getModule()->getDataLayout();
	assert(isa<PHINode>(UI) && "Expected LCSSA form");
	IRBuilder<> B(MiddleBlock->getTerminator());
	// Fast-math-flags propagate from the original induction instruction.
	if (II.getInductionBinOp() && isa<FPMathOperator>(II.getInductionBinOp()))
	B.setFastMathFlags(II.getInductionBinOp()->getFastMathFlags());
	Value *CountMinusOne = B.CreateSub(
	CountRoundDown, ConstantInt::get(CountRoundDown->getType(), 1));
	Value *CMO =
	!II.getStep()->getType()->isIntegerTy()
	? B.CreateCast(Instruction::SIToFP, CountMinusOne,
	II.getStep()->getType())
	: B.CreateSExtOrTrunc(CountMinusOne, II.getStep()->getType());
	CMO->setName("cast.cmo");
	Value *Escape = emitTransformedIndex(B, CMO, PSE.getSE(), DL, II);
	Escape->setName("ind.escape");
	MissingVals[UI] = Escape;
	}
	}

The vector trip count is passed in an argument named CountRoundDown, which implies that the rounded-up value in the tail loop folding case is not expected here. This is how we end up computing the incorrect index described above.

Looking at how loop vectorization decides whether to perform tail loop folding, it seems like tail loop folding isn't supposed to be allowed when there are uses of induction variables outside of the loop:

llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

Lines 1253 to 1278 in 04d083b

	bool LoopVectorizationLegality::prepareToFoldTailByMasking() {
	LLVM_DEBUG(dbgs() << "LV: checking if tail can be folded by masking.\n");
	SmallPtrSet<const Value *, 8> ReductionLiveOuts;
	for (auto &Reduction : getReductionVars())
	ReductionLiveOuts.insert(Reduction.second.getLoopExitInstr());
	// TODO: handle non-reduction outside users when tail is folded by masking.
	for (auto *AE : AllowedExit) {
	// Check that all users of allowed exit values are inside the loop or
	// are the live-out of a reduction.
	if (ReductionLiveOuts.count(AE))
	continue;
	for (User *U : AE->users()) {
	Instruction *UI = cast<Instruction>(U);
	if (TheLoop->contains(UI))
	continue;
	LLVM_DEBUG(
	dbgs()
	<< "LV: Cannot fold tail by masking, loop has an outside user for "
	<< *UI << "\n");
	return false;
	}
	}

Adding some debugging prints to this code shows that the induction variable %conv12 in repro.ll is missing from AllowedExit despite being used outside of the loop. The reason is this logic:

llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

Lines 549 to 558 in 04d083b

	// Both the PHI node itself, and the "post-increment" value feeding
	// back into the PHI node may have external users.
	// We can allow those uses, except if the SCEVs we have for them rely
	// on predicates that only hold within the loop, since allowing the exit
	// currently means re-using this SCEV outside the loop (see PR33706 for more
	// details).
	if (PSE.getUnionPredicate().isAlwaysTrue()) {
	AllowedExit.insert(Phi);
	AllowedExit.insert(Phi->getIncomingValueForBlock(TheLoop->getLoopLatch()));
	}

This code claims to disallow external uses of the induction PHI node if its SCEV might rely on predicates that might not hold outside of the loop (in the case of this bug, I'm guessing there is a predicate on the the i8 IV not overflowing). However, it never actually checks for external uses of the PHI node (on the other hand, uses of the "post-increment" value will be properly checked when LoopVectorizationLegality::canVectorizeInstrs() processes that instruction). The only effect of this logic on the PHI node is that that it skips adding it to AllowedExit. This hides the the PHI from the tail loop folding logic, which expects all externally used values to appear in AllowedExit.

If I understand correctly, it should be safe to use the induction variable externally, since all of the necessary SCEV predicates should have held at the time that it was computed. If this is correct, then we can fix this bug by unconditionally adding the induction PHI to AllowedExit in LoopVectorizationLegality::addInductionPhi().

I mailed https://reviews.llvm.org/D115109 a few days ago to try to fix this (only commenting here now since the BZ migration just completed :-))

[rickyz]

Oops, forgot to attach the files mentioned above:
after_vectorize.ll.txt
repro.ll.txt