[ValueTracking] Don't assume we can speculate shifts

[mkuper]

Summary

Shifts are only isSafeToSpeculativelyExecute if we know the amount we're shifting by is smaller than the bitwidth of the shifted value.

This fixes PR30708

[davide]

LGTM, modulo nit. This was a little bit painful.

lib/Analysis/ValueTracking.cpp

3217

Nit: I think the LLVM spelling is FIXME

[efriedma]

"A shift is undefined if the second operand is equal or larger than the number of bits in the first operand."

Yes... but that's not undefined behavior. LangRef just says "the result is undefined".

[mkuper]

lib/Analysis/ValueTracking.cpp

3217

This is really inconsistent, both are used.

lib$ grep -R "// TODO" | wc -l
984
lib$ grep -R "// FIXME" | wc -l
2213

We do consistently have a space after the // , though.
I'll change to "// FIXME:" to match the leading style. :-)

[davide]

In D25847#575957, @efriedma wrote:

"A shift is undefined if the second operand is equal or larger than the number of bits in the first operand."

Yes... but that's not undefined behavior. LangRef just says "the result is undefined".

hmm, does this change the fact that we don't want to speculate in this case or you're commenting on the wording?

[sanjoy]

This looks wrong -- shifts should always be safe to speculate. I wasn't following PR30708 closely, but can you describe why you think shift speculation is the root cause for PR30708?

[efriedma]

In LangRef "the result is undefined" essentially means "returns undef", like a load from uninitialized memory. There isn't any reason we can't speculate a shift, as long as the result isn't actually used for anything.

I would guess that we're performing a transformation which assumes that "lshr i32 1, %n" returns either 1 or 0, which isn't correct for n >= 32.

[mkuper]

I think you're right, I misread the LangRef. Back to the drawing board.

[mkuper]

In D25847#575972, @sanjoy wrote:

This looks wrong -- shifts should always be safe to speculate. I wasn't following PR30708 closely, but can you describe why you think shift speculation is the root cause for PR30708?

Because of this comment on PR30708:

This instruction:

%shr.i.us21 = lshr i32 1, 53

has UB as we're trying to shift right > 32

But, as Eli pointed out (thanks!), this isn't true.

[davide]

In D25847#575978, @mkuper wrote:

In D25847#575972, @sanjoy wrote:

This looks wrong -- shifts should always be safe to speculate. I wasn't following PR30708 closely, but can you describe why you think shift speculation is the root cause for PR30708?

Because of this comment on PR30708:

This instruction:

%shr.i.us21 = lshr i32 1, 53

has UB as we're trying to shift right > 32

But, as Eli pointed out (thanks!), this isn't true.

Oh, sorry, this is entirely my fault. I misread result undefined == undefined behaviour, that's where the confusion started. Sorry again!

[mkuper]

Nah, I've read the same text (several times, for each type of shift) and didn't catch it either. :-)
Sorry for the noise.

lib/Analysis/ValueTracking.cpp

bool llvm::isSafeToSpeculativelyExecute(const Value *V,
   for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
     if (Constant *C = dyn_cast<Constant>(Inst->getOperand(i)))
       if (C->canTrap())
         return false;
 
   switch (Inst->getOpcode()) {
   default:
     return true;
+  //TODO: Div, rem and shifts can probably be smarter about non-constant values,
+  //and use known bits.
   case Instruction::UDiv:
   case Instruction::URem: {
     // x / y is undefined if y == 0.
     const APInt *V;
     if (match(Inst->getOperand(1), m_APInt(V)))
       return *V != 0;
     return false;
   }
if (*Denominator != -1)
       return true;
     // At this point we know that the denominator is -1.  It is safe to hoist as
     // long we know that the numerator is not INT_MIN.
     if (match(Inst->getOperand(0), m_APInt(Numerator)))
       return !Numerator->isMinSignedValue();
     // The numerator *might* be MinSignedValue.
     return false;
   }
+  case Instruction::AShr:
+  case Instruction::LShr:
+  case Instruction::Shl: {
+    // A shift is undefined if the second operand is equal or larger than
+    // the number of bits in the first operand.
+    const APInt *ShiftAmt;
+    unsigned BitWidth =
+        cast<IntegerType>(Inst->getOperand(0)->getType()->getScalarType())
+            ->getBitWidth();
+    if (!match(Inst->getOperand(1), m_APInt(ShiftAmt)))
+      return false;
+
+    return (ShiftAmt->getZExtValue() < BitWidth);
+  }
   case Instruction::Load: {
     const LoadInst *LI = cast<LoadInst>(Inst);
     if (!LI->isUnordered() ||
         // Speculative load may create a race that did not exist in the source.
         LI->getFunction()->hasFnAttribute(Attribute::SanitizeThread) ||
         // Speculative load may load data from dirty regions.
         LI->getFunction()->hasFnAttribute(Attribute::SanitizeAddress))
       return false;

test/Transforms/SimplifyCFG/speculat-shift.ll

+; RUN: opt -S -simplifycfg < %s | FileCheck %s
+
+
+; CHECK-LABEL: @ashr_test_static_good(
+; CHECK: select i1 %cmp, i32 %shift, i32 0
+define i32 @ashr_test_static_good(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp eq i32 %a, %b
+  br i1 %cmp, label %cond.true, label %cond.end
+
+cond.true:
+  %shift = ashr i32 %b, 1
+  br label %cond.end
+
+cond.end:
+  %cond = phi i32 [ %shift, %cond.true ], [ 0, %entry ]
+  ret i32 %cond
+}
+
+; CHECK-LABEL: @ashr_test_static_bad(
+; CHECK: %cond = phi i32 [ %shift, %cond.true ], [ 0, %entry ]
+define i32 @ashr_test_static_bad(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp eq i32 %a, %b
+  br i1 %cmp, label %cond.true, label %cond.end
+
+cond.true:
+  %shift = ashr i32 %b, 40
+  br label %cond.end
+
+cond.end:
+  %cond = phi i32 [ %shift, %cond.true ], [ 0, %entry ]
+  ret i32 %cond
+}
+
+; CHECK-LABEL: @ashr_test_dynamic(
+; CHECK: %cond = phi i32 [ %shift, %cond.true ], [ 0, %entry ]
+define i32 @ashr_test_dynamic(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp eq i32 %a, %b
+  br i1 %cmp, label %cond.true, label %cond.end
+
+cond.true:
+  %shift = ashr i32 %b, %a
+  br label %cond.end
+
+cond.end:
+  %cond = phi i32 [ %shift, %cond.true ], [ 0, %entry ]
+  ret i32 %cond
+}
+
+; CHECK-LABEL: @lshr_test_static_good(
+; CHECK: select i1 %cmp, i32 %shift, i32 0
+define i32 @lshr_test_static_good(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp eq i32 %a, %b
+  br i1 %cmp, label %cond.true, label %cond.end
+
+cond.true:
+  %shift = lshr i32 %b, 1
+  br label %cond.end
+
+cond.end:
+  %cond = phi i32 [ %shift, %cond.true ], [ 0, %entry ]
+  ret i32 %cond
+}
+
+; CHECK-LABEL: @lshr_test_static_bad(
+; CHECK: %cond = phi i32 [ %shift, %cond.true ], [ 0, %entry ]
+define i32 @lshr_test_static_bad(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp eq i32 %a, %b
+  br i1 %cmp, label %cond.true, label %cond.end
+
+cond.true:
+  %shift = lshr i32 %b, 40
+  br label %cond.end
+
+cond.end:
+  %cond = phi i32 [ %shift, %cond.true ], [ 0, %entry ]
+  ret i32 %cond
+}
+
+; CHECK-LABEL: @lshr_test_dynamic(
+; CHECK: %cond = phi i32 [ %shift, %cond.true ], [ 0, %entry ]
+define i32 @lshr_test_dynamic(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp eq i32 %a, %b
+  br i1 %cmp, label %cond.true, label %cond.end
+
+cond.true:
+  %shift = lshr i32 %b, %a
+  br label %cond.end
+
+cond.end:
+  %cond = phi i32 [ %shift, %cond.true ], [ 0, %entry ]
+  ret i32 %cond
+}
+
+; CHECK-LABEL: @shl_test_static_good(
+; CHECK: select i1 %cmp, i32 %shift, i32 0
+define i32 @shl_test_static_good(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp eq i32 %a, %b
+  br i1 %cmp, label %cond.true, label %cond.end
+
+cond.true:
+  %shift = shl i32 %b, 1
+  br label %cond.end
+
+cond.end:
+  %cond = phi i32 [ %shift, %cond.true ], [ 0, %entry ]
+  ret i32 %cond
+}
+
+; CHECK-LABEL: @shl_test_static_bad(
+; CHECK: %cond = phi i32 [ %shift, %cond.true ], [ 0, %entry ]
+define i32 @shl_test_static_bad(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp eq i32 %a, %b
+  br i1 %cmp, label %cond.true, label %cond.end
+
+cond.true:
+  %shift = shl i32 %b, 40
+  br label %cond.end
+
+cond.end:
+  %cond = phi i32 [ %shift, %cond.true ], [ 0, %entry ]
+  ret i32 %cond
+}
+
+; CHECK-LABEL: @shl_test_dynamic(
+; CHECK: %cond = phi i32 [ %shift, %cond.true ], [ 0, %entry ]
+define i32 @shl_test_dynamic(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp eq i32 %a, %b
+  br i1 %cmp, label %cond.true, label %cond.end
+
+cond.true:
+  %shift = shl i32 %b, %a
+  br label %cond.end
+
+cond.end:
+  %cond = phi i32 [ %shift, %cond.true ], [ 0, %entry ]
+  ret i32 %cond
+}