Fix for PR20059 (instcombine reorders shufflevector after instruction that may trap)

[spatel]

Summary

In PR20059 ( http://llvm.org/pr20059 ), instcombine eliminates shuffles that are necessary before performing an operation that can trap (srem).

This patch calls isSafeToSpeculativelyExecute() and bails out of the optimization in SimplifyVectorOp() if needed.

I'm not sure if this 'reordering of shuffles' optimization should also be disallowed for all vector FP ops (any of those can cause an exception?), but since there's an existing test case in test/Transforms/InstCombine/vec_shuffle.ll that will have to be removed if we want to change that behavior, I'll post it as a separate patch.

[spatel]

Forgot to add reviewers when creating patch.

[aschwaighofer]

I believe the optimization is safe for floating values that cannot trap.

undef = fadd undef, %x

but it does not trap. So the optimization of reordering the shuffle should be safe.

However:

fdiv %x, undef

can trap because undef can be assumed to be any value including zero. And fdiv traps on zero. So the optimization is not safe.

What does isSafeToSpeculativelyExecute() return for fdiv? It seems to be an omission (bug) that it returns true? (Note, I have not verified this claim but the switch in this function does not contain fdiv and the default case returns true)

At least LICM seems like it could go wrong with conditionally executed fdiv (with loop invariant operands):

bool LICM::isSafeToExecuteUnconditionally(Instruction &Inst) {

// If it is not a trapping instruction, it is always safe to hoist.
if (isSafeToSpeculativelyExecute(&Inst))
  return true;

[aschwaighofer]

Actually, now I am not sure myself - does an floating point div trap on zero? :D

[aschwaighofer]

We probably get NaN or some infinity - forget what I said.

[aschwaighofer]

Your patch LGTM.

[spatel]

Closed by commit rL212629 (authored by @spatel).

[spatel]

Thanks, Arnold.

I've committed the fix for int ops, but I'm still doubtful that this is safe for FP (any FP)...because any FP op can cause an exception, right? We don't normally have exceptions enabled for FP div-by-zero, denorms, underflow, etc (especially for vector ops), but a system or user can certainly enable those manually. If that is true and one of the unknown operands in the vector is bad in some way, then we'll generate an exception that wouldn't have occurred without this optimization. I suppose I can generate a C test case to prove this by twiddling the FP exception bits.

[hfinkel]

"but a system or user can certainly enable those manually" -- No, Clang/LLVM specifically do not support this! In the context of C, this means that we don't support "#pragma STDC FENV_ACCESS on". It is not well defined for the user to fool with the fp environment without informing the compiler (in C, that pragma is the standard mechanism), and if the user tries, they'll receive an error.

llvm/trunk/lib/Transforms/InstCombine/InstructionCombining.cpp

 #include "InstCombine.h"
 #include "llvm-c/Initialization.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"

 
 /// \brief Makes transformation of binary operation specific for vector types.
 /// \param Inst Binary operator to transform.
 /// \return Pointer to node that must replace the original binary operator, or
 ///         null pointer if no transformation was made.
 Value *InstCombiner::SimplifyVectorOp(BinaryOperator &Inst) {
   if (!Inst.getType()->isVectorTy()) return nullptr;
 
+  // It may not be safe to reorder shuffles and things like div, urem, etc.
+  // because we may trap when executing those ops on unknown vector elements.
+  // See PR20059.
+  if (!isSafeToSpeculativelyExecute(&Inst)) return nullptr;
+
   unsigned VWidth = cast<VectorType>(Inst.getType())->getNumElements();
   Value *LHS = Inst.getOperand(0), *RHS = Inst.getOperand(1);
   assert(cast<VectorType>(LHS->getType())->getNumElements() == VWidth);
   assert(cast<VectorType>(RHS->getType())->getNumElements() == VWidth);
 
   // If both arguments of binary operation are shuffles, which use the same
   // mask and shuffle within a single vector, it is worthwhile to move the
   // shuffle after binary operation:

llvm/trunk/test/Transforms/InstCombine/pr20059.ll

+; RUN: opt -S -instcombine < %s | FileCheck %s
+
+; In PR20059 ( http://llvm.org/pr20059 ), shufflevector operations are reordered/removed
+; for an srem operation. This is not a valid optimization because it may cause a trap
+; on div-by-zero.
+
+; CHECK-LABEL: @do_not_reorder
+; CHECK: %splat1 = shufflevector <4 x i32> %p1, <4 x i32> undef, <4 x i32> zeroinitializer
+; CHECK-NEXT: %splat2 = shufflevector <4 x i32> %p2, <4 x i32> undef, <4 x i32> zeroinitializer
+; CHECK-NEXT: %retval = srem <4 x i32> %splat1, %splat2
+define <4 x i32> @do_not_reorder(<4 x i32> %p1, <4 x i32> %p2) {
+  %splat1 = shufflevector <4 x i32> %p1, <4 x i32> undef, <4 x i32> zeroinitializer
+  %splat2 = shufflevector <4 x i32> %p2, <4 x i32> undef, <4 x i32> zeroinitializer
+  %retval = srem <4 x i32> %splat1, %splat2
+  ret <4 x i32> %retval
+}
+; RUN: opt -S -instcombine < %s | FileCheck %s
+
+; In PR20059 ( http://llvm.org/pr20059 ), shufflevector operations are reordered/removed
+; for an srem operation. This is not a valid optimization because it may cause a trap
+; on div-by-zero.
+
+; CHECK-LABEL: @do_not_reorder
+; CHECK: %splat1 = shufflevector <4 x i32> %p1, <4 x i32> undef, <4 x i32> zeroinitializer
+; CHECK-NEXT: %splat2 = shufflevector <4 x i32> %p2, <4 x i32> undef, <4 x i32> zeroinitializer
+; CHECK-NEXT: %retval = srem <4 x i32> %splat1, %splat2
+define <4 x i32> @do_not_reorder(<4 x i32> %p1, <4 x i32> %p2) {
+  %splat1 = shufflevector <4 x i32> %p1, <4 x i32> undef, <4 x i32> zeroinitializer
+  %splat2 = shufflevector <4 x i32> %p2, <4 x i32> undef, <4 x i32> zeroinitializer
+  %retval = srem <4 x i32> %splat1, %splat2
+  ret <4 x i32> %retval
+}