[simplifycfg] constantexpr divide evaluation made unconditional

[llvmbot]

Bugzilla Link	957
Resolution	FIXED
Resolved on	Mar 06, 2010 14:07
Version	trunk
OS	All
Attachments	Test case
Reporter	LLVM Bugzilla Contributor
CC	@lattner

Extended Description

Without predsimplify pass:

LBB1_18: #cond_false179
testl %ebp, %ebp
jne LBB1_20 #cond_next185
LBB1_19: #cond_true182
movl $1, %eax
xorl %edx, %edx
divl %ebp
movl %eax, %ebp
LBB1_20: #cond_next185
cmpl $65535, %ebp
ja LBB1_24 #cond_false199

The divl is properly guarded to prevent divide by zero.

With -predsimplify:

LBB1_25: #cond_true182
xorl %edx, %edx
movl $1, %eax
divl %edx
movl %eax, %ebp
LBB1_26: #cond_next185
cmpl $65535, %ebp
ja LBB1_30 #cond_false199

That's guaranteed to cause an divide by zero exception!

[llvmbot]

assigned to @lattner

[llvmbot]

To reproduce:

opt -predsimplify pr957.bc > bug.bc
llc -f bug.bc

Look for cond_true182

[nlewycky]

I can't reproduce this. When I run -predsimplify over your testcase I get the
exact same LLVM ASM output as input. Evan, could you please double-check this?

[llvmbot]

New test case

[llvmbot]

Try the new test case. Take a look at BB cond_true182.

[nlewycky]

Predsimplify is right. Here's the input code:

cond_false179: ; preds = %cond_true
%tmp181 = seteq uint %tmp, 0 ; [#uses=1]
br bool %tmp181, label %cond_true182, label %cond_next185

cond_true182: ; preds = %cond_false179
%tmp184 = div uint 1, %tmp ; [#uses=1]
br label %cond_next185

cond_next185: ; preds = %cond_true182, %cond_false179
%d0.3 = phi uint [ %tmp184, %cond_true182 ], [ %tmp, %cond_false179 ] ;
[#uses=7]
%tmp191 = setgt uint %d0.3, 65535 ; [#uses=1]
br bool %tmp191, label %cond_false199, label %cond_true192

predsimplify decides to hoist the def'n of %tmp184 into cond_next185. If %tmp is
zero, then %tmp184 becomes "div uint 1, 0" which is a const. Here's the output
(with crit-edges manually rejoined):

cond_false179: ; preds = %cond_true
%tmp181 = seteq uint %tmp, 0 ; [#uses=1]
br bool %tmp181, label %cond_true182, label %cond_next185

cond_true182: ; preds = %cond_false179
br label %cond_next185

cond_next185: ; preds = %cond_true182, %cond_false179
%d0.3 = phi uint [ div (uint 1, uint 0), %cond_true182 ], [ %tmp,
%cond_false179 ] ; [#uses=7]
%tmp191 = setgt uint %d0.3, 65535 ; [#uses=1]
br bool %tmp191, label %cond_false199, label %cond_true192

The "div (uint 1, uint 0)" should only happen if the flow came from
cond_true182, which is the case where %tmp is equal to zero. If the backend is
computing that regardless of the flow, then that's a backend bug.

[lattner]

Nick is right. Consider this testcase:

uint %test(uint %tmp) {
cond_false179: ; preds = %cond_true
%tmp181 = seteq uint %tmp, 0 ; [#uses=1]
br bool %tmp181, label %cond_true182, label %cond_next185

cond_true182: ; preds = %cond_false179
br label %cond_next185

cond_next185: ; preds = %cond_true182, %cond_false179
%d0.3 = phi uint [ div (uint 1, uint 0), %cond_true182 ], [ %tmp,
%cond_false179 ] ; [#uses=7]

    ret uint %d0.3

}

gccas turns this into:

uint %test(uint %tmp) {
cond_false179:
%tmp181 = seteq uint %tmp, 0 ; [#uses=1]
%retval = select bool %tmp181, uint div (uint 1, uint 0), uint %tmp ; [#uses=1]
ret uint %retval
}

which unconditionally executes the div.

This is a bug in something in gccas (probably instcombine or simplifycfg), predsimplify just exposes it.

-Chris

[lattner]

simplifycfg does this.

[nlewycky]

Why does a select instruction unconditionally evaluate both arguments? Shouldn't
it look at the boolean and only execute one of them?

If I had to follow this rule as implied, then there is a bug in predsimplify,
just one involving select instead of phi.

[lattner]

select is closest to a conditional move. Given two values (which are precomputed) it picks one. Select
itself doesn't have a notion of control flow, a constant expr is a value like any other, which needs to be
evaluated.

Fixed. Patch here:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20061016/038778.html

testcase here: SimplifyCFG/2006-10-19-UncondDiv.ll

-Chris

[nlewycky]

That's not good. That means that I can't use
%tmp184->replaceAllUsesWith(ConstantExpr::get(DIV, 0, 1)) without first
iterating through the User list and see if any of them is a SelectInst.

[lattner]

Yes you can, why wouldn't you be able to?

[nlewycky]

Actually, I take it back. I can't see any way in which this choice of semantics
could manifest a bug in predsimplify, because if it did substitute a value into
a select instruction then it must already dominate that select instruction, so
the program would have trapped earlier.

If there is a bug, the fix doesn't involve iterating. It's just a matter of
testing for ConstantExpr canTrap() just as Chris' fix to simplifycfg.

File a new bug if you can manage to demonstrate the equivalent bug in predsimplify.

[lattner]

yep