This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Don't crash on out of bounds shifts
ClosedPublic

Authored by igor-laevsky on Nov 30 2017, 6:04 AM.

Details

Summary

This is branched from the D40390.

We can't crash instcombine when we encounter shift by unreasonable amount. Even though it's an undefined behaviour, compiler crash is incorrect.

Diff Detail

Event Timeline

igor-laevsky created this revision.Nov 30 2017, 6:04 AM
spatel edited edge metadata.

We should stub this out sooner and in one place. I think we can extend what we did in D38637:

Index: lib/Analysis/ValueTracking.cpp
===================================================================
--- lib/Analysis/ValueTracking.cpp	(revision 319435)
+++ lib/Analysis/ValueTracking.cpp	(working copy)
@@ -800,8 +800,14 @@
   unsigned BitWidth = Known.getBitWidth();
 
   if (auto *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
+    if (SA->getZExtValue() >= BitWidth) {
+      // This shift produces poison because the shift amount is too big. We can
+      // return anything we want. Choose 0 for the best folding opportunity.
+      Known.setAllZero();
+      return;
+    }
+
     unsigned ShiftAmt = SA->getLimitedValue(BitWidth-1);
-
     computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
     Known.Zero = KZF(Known.Zero, ShiftAmt);
     Known.One  = KOF(Known.One, ShiftAmt);

Update test case

I see your point. Unfortunately I can't find any good place to common this out. Problem is that code is structured as a consecutive matching of unrelated patterns which may sometimes contain invalid shift operations. But I don't know the code base enough so maybe I'm missing something. Any advice?

Have you checked for compile time impact?

Oops wrong review. Ignore that comment

spatel added a comment.Dec 1 2017, 9:36 AM

I see your point. Unfortunately I can't find any good place to common this out. Problem is that code is structured as a consecutive matching of unrelated patterns which may sometimes contain invalid shift operations. But I don't know the code base enough so maybe I'm missing something. Any advice?

Not sure if you saw my earlier patch draft. Here's a hopefully better version - does this solve the crashing you're seeing?

Index: lib/Analysis/ValueTracking.cpp
===================================================================
--- lib/Analysis/ValueTracking.cpp	(revision 319542)
+++ lib/Analysis/ValueTracking.cpp	(working copy)
@@ -800,7 +800,16 @@
   unsigned BitWidth = Known.getBitWidth();
 
   if (auto *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
-    unsigned ShiftAmt = SA->getLimitedValue(BitWidth-1);
+    // We can't use getZExtValue() here because the shift amount could be bigger
+    // than a 64-bit, but anything over 32-bit (the knownbits width is
+    // 32-bit) would result in poison, so it's fine to saturate to a 64-bit.
+    uint64_t ShiftAmt = SA->getLimitedValue();
+    if (ShiftAmt >= BitWidth) {
+      // This shift produces poison because the shift amount is too big. We can
+      // return anything we want. Choose 0 for the best folding opportunity.
+      Known.setAllZero();
+      return;
+    }
 
     computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
     Known.Zero = KZF(Known.Zero, ShiftAmt);

No, unfortunately your patch doesn't fix the problem. I believe those are two different paths in the code.

No, unfortunately your patch doesn't fix the problem. I believe those are two different paths in the code.

Ah - I see what happened. I was only trying my reduced case. In the example here, we're getting into computeKnownBitsFromAssume() from the 'and'.

But I think my draft wasn't a waste. Try this test too:

define i128 @test1(i128 %a) {

%and1 = and i128 %a, 3
%B = lshr i128 %and1, -1
%cmp = icmp eq i128 %B, 1
tail call void @llvm.assume(i1 %cmp)
ret i128 %and1

}

igor-laevsky updated this revision to Diff 125315.EditedDec 4 2017, 5:48 AM

Thanks! Please see updated change with this issue fixed.

spatel accepted this revision.Dec 4 2017, 8:20 AM

LGTM.

This revision is now accepted and ready to land.Dec 4 2017, 8:20 AM
This revision was automatically updated to reflect the committed changes.