InstCombiner::SimplifyDemandedBit can modify an instruction without adding it to the worklist

[llvmbot]

Bugzilla Link	19985
Version	trunk
OS	Linux
Reporter	LLVM Bugzilla Contributor
CC	@d0k

Extended Description

bool InstCombiner::SimplifyDemandedBits(Use &U, APInt DemandedMask,
APInt &KnownZero, APInt &KnownOne,
unsigned Depth) {
Value *NewVal = SimplifyDemandedUseBits(U.get(), DemandedMask,
KnownZero, KnownOne, Depth);
if (!NewVal) return false;
U = NewVal;
return true;
}

The use is modified, but the instructions in not added back to the worklist.

I don't have a testcase where this changes the result. I just noticed an instruction being modified and not immediately being revisited while looking at another issuer in a debugger.

[llvmbot]

The testcase where I see this is

define i1 @​f(i1 %cmp4) {
%conv = zext i1 %cmp4 to i32
%sub1 = shl nuw nsw i32 %conv, 24
%sext = or i32 %sub1, -134217728
%conv6 = ashr exact i32 %sext, 24
%cmp7 = icmp ult i32 %conv6, 2
ret i1 %cmp7
}

There are no simplifications until we get tho cmp7. Then SimplifyDemandedBis recurses until it finds out that cmp4 can be replaced with undef. We add cmp7 back to the worklist, which means we keep running SimplifyDemandedBits. The transformations it does are

%conv = zext i1 %cmp4 to i32 -> %conv = zext i1 undef to i32
%sub1 = shl nuw nsw i32 %conv, 24 -> %sub1 = shl nuw nsw i32 0, 24
%sext = or i32 %sub1, -134217728 -> %sext = or i32 0, -134217728
%conv6 = ashr exact i32 %sext, 24 -> %conv6 = ashr exact i32 -134217728, 24
%cmp7 = icmp ult i32 %conv6, 2 -> %cmp7 = icmp ult i32 -8, 2

The transformations themselves are fine, but at each step SimplifyDemandedBis has to start recursing again from %cmp7. We also end up with a somewhat funny looking code:

define i1 @​f(i1 %cmp4) {
%conv = zext i1 undef to i32
%sub1 = shl nuw nsw i32 0, 24
%sext = or i32 0, -134217728
%conv6 = ashr exact i32 -134217728, 24
%cmp7 = icmp ult i32 -8, 2
ret i1 %cmp7
}

Which fortunately constant folds.

If we were adding the instructions SimplifyDemandedBis modifies to the worklist this would have folded earlier.

[llvmbot]

testcese

[llvmbot]

It is trivial to add

Worklist.Add(cast(U.getUser()));

but that doesn't fix the issues from comment 1. The problem is that it will add the modified instruction to the worklist, but then the top level loop in instcombine will add cmp7 to the list too. Since the worklist is a lifo we will still get the behavior of SimplifyDemandedBis being called in cmp7 repeatedly.

The patch would change the output in some corner cases (see attached test), but it is not clear if that is worth it.

Maybe what is needed first is for the worklist to be a smarter datastructure. For example, an instruction could be added after any other instruction that it uses.