Miscompile with opt -loop-vectorize

[mikaelholmen]

Bugzilla Link	44488
Resolution	FIXED
Resolved on	Feb 06, 2020 08:50
Version	trunk
OS	Linux
Blocks	#43900
Attachments	bbi-37172.ll reproducer
CC	@bjope,@fhahn,@zmodem,@RKSimon,@rotateright
Fixed by commit(s)	f14f2a8

Extended Description

I think I've found a case where -loop-vectorize produces wrong code.

Reproduce with
opt -loop-vectorize -S -o - bbi-37172.ll

The input looks like

---

@​v_38 = global i16 12061, align 1
@​v_39 = global i16 11333, align 1

define i16 @​main() {
entry:
br label %for.body

for.cond.cleanup: ; preds = %cond.end5
%0 = load i16, i16* @​v_39, align 1
ret i16 %0

for.body: ; preds = %entry, %cond.end5
%i.07 = phi i16 [ 99, %entry ], [ %inc7, %cond.end5 ]
%1 = load i16, i16* @​v_38, align 1
%cmp1 = icmp eq i16 %1, 32767
br i1 %cmp1, label %cond.end, label %cond.end

cond.end: ; preds = %for.body, %for.body
%cmp2 = icmp eq i16 %1, 0
br i1 %cmp2, label %cond.end5, label %cond.false4

cond.false4: ; preds = %cond.end
%rem = srem i16 5786, %1
br label %cond.end5

cond.end5: ; preds = %cond.end, %cond.false4
%cond6 = phi i16 [ %rem, %cond.false4 ], [ 5786, %cond.end ]
store i16 %cond6, i16* @​v_39, align 1
%inc7 = add nsw i16 %i.07, 1
%cmp = icmp slt i16 %inc7, 111
br i1 %cmp, label %for.body, label %for.cond.cleanup, !llvm.loop !​26
}

If we just focus at the beginning of the loop we have

---

for.body: ; preds = %entry, %cond.end5
%i.07 = phi i16 [ 99, %entry ], [ %inc7, %cond.end5 ]
%1 = load i16, i16* @​v_38, align 1
%cmp1 = icmp eq i16 %1, 32767
br i1 %cmp1, label %cond.end, label %cond.end

cond.end: ; preds = %for.body, %for.body
%cmp2 = icmp eq i16 %1, 0
br i1 %cmp2, label %cond.end5, label %cond.false4

cond.false4: ; preds = %cond.end
%rem = srem i16 5786, %1
br label %cond.end5

v_38 is 12061 and we will always branch from for.body to cond.end.
Then we do

%cmp2 = icmp eq i16 %1, 0

which will be false, so

br i1 %cmp2, label %cond.end5, label %cond.false4

will branch to cond.false4 where we will execute the srem

%rem = srem i16 5786, %1

v_38 doesn't change throughout the program so this is the path we will use
every loop round.

After vectorization, we instead get the following:

---

vector.body: ; preds = %pred.srem.continue2, %vector.ph
%index = phi i32 [ 0, %vector.ph ], [ %index.next, %pred.srem.continue2 ]
%0 = trunc i32 %index to i16
%offset.idx = add i16 99, %0
%broadcast.splatinsert = insertelement <2 x i16> undef, i16 %offset.idx, i32 0
%broadcast.splat = shufflevector <2 x i16> %broadcast.splatinsert, <2 x i16> undef, <2 x i32> zeroinitializer
%induction = add <2 x i16> %broadcast.splat, <i16 0, i16 1>
%1 = add i16 %offset.idx, 0
%2 = load i16, i16* @​v_38, align 1
%3 = load i16, i16* @​v_38, align 1
%4 = insertelement <2 x i16> undef, i16 %2, i32 0
%5 = insertelement <2 x i16> %4, i16 %3, i32 1
%6 = icmp eq <2 x i16> %5, <i16 32767, i16 32767>
%7 = icmp eq <2 x i16> %5, zeroinitializer
%8 = or <2 x i1> %6, %6
%9 = xor <2 x i1> %7, <i1 true, i1 true>
%10 = and <2 x i1> %9, %8
%11 = extractelement <2 x i1> %10, i32 0
br i1 %11, label %pred.srem.if, label %pred.srem.continue

pred.srem.if: ; preds = %vector.body
%12 = srem i16 5786, %2
%13 = insertelement <2 x i16> undef, i16 %12, i32 0
br label %pred.srem.continue

Since v_38 is 12061, %5 will be <12061, 12061>, and thus both %6 and %7 will
be <0, 0>.

From this we get that %8 is <0, 0>, %9 is <1, 1> and finally %10 is then <0, 0>.
%11 will be 0, and we will thus branch to pred.srem.continue and not execute
the srem.

In pred.srem.continue we then have

---

pred.srem.continue: ; preds = %pred.srem.if, %vector.body
%14 = phi <2 x i16> [ undef, %vector.body ], [ %13, %pred.srem.if ]
%15 = extractelement <2 x i1> %10, i32 1
br i1 %15, label %pred.srem.if1, label %pred.srem.continue2

pred.srem.if1: ; preds = %pred.srem.continue
%16 = srem i16 5786, %3
%17 = insertelement <2 x i16> %14, i16 %16, i32 1
br label %pred.srem.continue2

%10 is still <0, 0> so also %15 will be 0, and we will branch to
pred.srem.continue2 and also skip the srem in pred.srem.if1.

Phew.

So, before vectorization we would execute the srem, but after vectorization
we don't anymore. This looks wrong to me.

I don't know really what is happening inside the vectorizer, but I have to say
I'm suspicious towards the generated

%8 = or <2 x i1> %6, %6
%9 = xor <2 x i1> %7, <i1 true, i1 true>
%10 = and <2 x i1> %9, %8

Especially the

%8 = or <2 x i1> %6, %6

looks pointless. I suppose in some way it's connected to the

br i1 %cmp1, label %cond.end, label %cond.end

part in the input, but while that branch always takes us to cond.end,
the %8 will always be <0, 0> and then prevent us from reaching any of the
"srem" instructions since %8 is used in the and to calculate %10.

[mikaelholmen]

I'm out on very deep water here because I don't know the Vectorizer, but
could the bug possibly be in VPRecipeBuilder::createEdgeMask?

---

VPValue *VPRecipeBuilder::createEdgeMask(BasicBlock *Src, BasicBlock *Dst,
VPlanPtr &Plan) {
assert(is_contained(predecessors(Dst), Src) && "Invalid edge");

// Look for cached value.
std::pair<BasicBlock *, BasicBlock *> Edge(Src, Dst);
EdgeMaskCacheTy::iterator ECEntryIt = EdgeMaskCache.find(Edge);
if (ECEntryIt != EdgeMaskCache.end())
return ECEntryIt->second;

VPValue *SrcMask = createBlockInMask(Src, Plan);

// The terminator has to be a branch inst!
BranchInst *BI = dyn_cast(Src->getTerminator());
assert(BI && "Unexpected terminator found");

if (!BI->isConditional())
return EdgeMaskCache[Edge] = SrcMask;

VPValue *EdgeMask = Plan->getVPValue(BI->getCondition());
assert(EdgeMask && "No Edge Mask found for condition");

if (BI->getSuccessor(0) != Dst)
EdgeMask = Builder.createNot(EdgeMask);

if (SrcMask) // Otherwise block in-mask is all-one, no need to AND.
EdgeMask = Builder.createAnd(EdgeMask, SrcMask);

return EdgeMaskCache[Edge] = EdgeMask;
}

IIUC, normally for conditional branches, the above code seems to invert the
mask for the false edge with the code

if (BI->getSuccessor(0) != Dst)
EdgeMask = Builder.createNot(EdgeMask);

But now consider a branch like this:

br i1 %cmp1, label %cond.end, label %cond.end

Could it be that we calculate a mask for the true edge, cache it, and then
when we are asked to calculate the edge mask for the false edge, we just pick
the cached value

// Look for cached value.
std::pair<BasicBlock *, BasicBlock *> Edge(Src, Dst);
EdgeMaskCacheTy::iterator ECEntryIt = EdgeMaskCache.find(Edge);
if (ECEntryIt != EdgeMaskCache.end())
return ECEntryIt->second;

and misses the needed negation?

[fhahn]

Interesting, that looks suspicious indeed. I'll try to take a look later today/tomorrow.

[mikaelholmen]

Btw, never mind the caching. Even the

if (BI->getSuccessor(0) != Dst)
EdgeMask = Builder.createNot(EdgeMask);

as a way to know if we're dealing with the true or the false edge is broken for
degenerate branches where the true and false BB are the same.

[mikaelholmen]

Interesting, that looks suspicious indeed. I'll try to take a look later
today/tomorrow.

Oh sounds good. Great!

[bjope]

I wonder if this should be a release blocker for 10.0. Considering that it results in miscompiles.

We see this a lot in fuzzy tests, using both random input and random opt pass pipelines. But we haven't proven that it can't happen with a standard pipeline.

Not quite sure how to solve it. Should LV treat all conditional branches with a single destination as an unconditional branches?

[fhahn]

I wonder if this should be a release blocker for 10.0. Considering that it
results in miscompiles.

We see this a lot in fuzzy tests, using both random input and random opt
pass pipelines. But we haven't proven that it can't happen with a standard
pipeline.

I think with a regular pipeline, the conditional branch would get simplified to an unconditional one long before LV sees it, so it should very hard to hit in a 'real' pipeline.

But if we can agree on the simple fix relatively soon, picking it for 10.0 should be fairly easy.

Not quite sure how to solve it. Should LV treat all conditional branches
with a single destination as an unconditional branches?

I've proposed a simple patch: https://reviews.llvm.org/D73079

It solves the issue by using an expression that's always true for edge masks for terminators with equal true and false successors. This should solve the problem in a very straight forward way. It creates an unnecessary bitwise operator, but that will get cleaned up later on.

[fhahn]

Should be fixed by https://reviews.llvm.org/rGf14f2a856802

[mikaelholmen]

Should be fixed by https://reviews.llvm.org/rGf14f2a856802

Great, thanks!

[RKSimon]

I wonder if this should be a release blocker for 10.0. Considering that it
results in miscompiles.

Florian - do you think this should be cherry picked into 10.0?

[RKSimon]

Reopening for merge into 10.0

[fhahn]

Thanks, I think picking it is safe.

[zmodem]

Cherry-picked to 10.x in c0c5ab3
Sorry for the delay.

[mikaelholmen]

Hi,

Just want to mention that I wrote

llvm/llvm-bugzilla-archive#44800

yesterday which seems to be somewhat connected to the case handled here.

In llvm/llvm-bugzilla-archive#44800 an assert is triggered though so at least there it doesn't silently produce wrong code.

[zmodem]

mentioned in issue #43900

[mikaelholmen]

mentioned in issue llvm/llvm-bugzilla-archive#44800