[InstCombine] PR30366 : Teach the udiv folding logic how to handle constant expressions.

[andreadb]

Summary

This patch fixes PR30366.

Function 'foldUDivShl' works under the assumption that the value in input to the function is always an llvm::Instruction.
However, function 'visitUDivOperand' (the only user of 'foldUDivShl') clearly violates that precondition since it uses pattern matchers to check if the udiv can be folded. Internally, pattern matchers for binary operators know how to work with both Instruction and ConstantExpr values.

This causes problems with instructions like this one:

udiv i32 %z, zext (i16 shl (i16 1, i16 ptrtoint ([1 x i16]* @b to i16)) to i32)

Where:
Op1 = zext (i16 shl (i16 1, i16 ptrtoint ([1 x i16]* @b to i16)) to i32)

Internally, function 'visitUDivOperand' uses the following matcher:

match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))

In our example, that matcher would return 'true'. However, Op1 is a ConstantExpr and not an Instruction! Later on, Op1 is passed in input to foldUDivShl ; that function attempts to simplify the udiv instruction according to the following rule:

// X udiv (C1 << N), where C1 is "1<<C2"  -->  X >> (N+C2)

The code in foldUDivShl explicitly casts Op1 to llvm::Instruction. In our example, this would trigger an assertion failure due to an invalid cast from ConstantExpr to Instruction.

This patch fixes the problem in foldUDivShl() using pattern matchers instead of using explicit casts. The reduced test case from pr30366 has been added to test file InstCombine/udiv-simplify.ll.

Please let me know if okay to commit.

Thanks,
Andrea

[majnemer]

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

1002 ↗

(On Diff #71364)

You should check if match fails.

[andreadb]

Hi David,

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

1002 ↗

(On Diff #71364)

In theory, this check should never fail because visitUDivOperand (see lines 1036:1040) always checks that Op1 is a left shift of a power_of_2 before adding 'foldUDivShl' to the set of folding actions.

Would it be okay if I add an assertion failure if the call to match returns false?

[majnemer]

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

1002 ↗

(On Diff #71364)

Yes, something like:

if (!match(...))
  llvm_unreachable("match shouldn't fail here!");

1004–1005 ↗

(On Diff #71364)

This looks strangely formatted.

[andreadb]

Thanks for the feedback David!

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

1002 ↗

(On Diff #71364)

I will add that check.

1004–1005 ↗

(On Diff #71364)

Sorry, I forgot to clang-format this patch. I will fix it.

[andreadb]

Patch updated.

Addressed David's review comments.

[andreadb]

Ping.

Okay to commit?

[uabelho]

The patch solves PR30366 which I wrote and I haven't seen any problems when I've used it so I'd like to see it merged as well.

[spatel]

LGTM. See inline comments for a couple of nits.

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

993 ↗

(On Diff #71392)

It would be helpful to add a comment about the optional zext that we are pattern matching.

996 ↗

(On Diff #71392)

Unnecessary to initialize to nullptr here?

[uabelho]

Thanks Andrea!

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

static Instruction *foldUDivNegCst(Value *Op0, Value *Op1,
                                    const BinaryOperator &I, InstCombiner &IC) {
   Value *ICI = IC.Builder->CreateICmpULT(Op0, cast<ConstantInt>(Op1));
 
   return SelectInst::Create(ICI, Constant::getNullValue(I.getType()),
                             ConstantInt::get(I.getType(), 1));
 }
 
 // X udiv (C1 << N), where C1 is "1<<C2"  -->  X >> (N+C2)
+// X udiv (zext (C1 << N)), where C1 is "1<<C2"  -->  X >> (N+C2)
 static Instruction *foldUDivShl(Value *Op0, Value *Op1, const BinaryOperator &I,
                                 InstCombiner &IC) {
-  Instruction *ShiftLeft = cast<Instruction>(Op1);
-  if (isa<ZExtInst>(ShiftLeft))
-    ShiftLeft = cast<Instruction>(ShiftLeft->getOperand(0));
-
-  const APInt &CI =
-      cast<Constant>(ShiftLeft->getOperand(0))->getUniqueInteger();
-  Value *N = ShiftLeft->getOperand(1);
-  if (CI != 1)
-    N = IC.Builder->CreateAdd(N, ConstantInt::get(N->getType(), CI.logBase2()));
-  if (ZExtInst *Z = dyn_cast<ZExtInst>(Op1))
-    N = IC.Builder->CreateZExt(N, Z->getDestTy());
+  Value *ShiftLeft;
+  if (!match(Op1, m_ZExt(m_Value(ShiftLeft))))
+    ShiftLeft = Op1;
+
+  const APInt *CI;
+  Value *N;
+  if (!match(ShiftLeft, m_Shl(m_APInt(CI), m_Value(N))))
+    llvm_unreachable("match should never fail here!");
+  if (*CI != 1)
+    N = IC.Builder->CreateAdd(N,
+                              ConstantInt::get(N->getType(), CI->logBase2()));
+  if (Op1 != ShiftLeft)
+    N = IC.Builder->CreateZExt(N, Op1->getType());
   BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, N);
   if (I.isExact())
     LShr->setIsExact();
   return LShr;
 }
 
 // \brief Recursively visits the possible right hand operands of a udiv
 // instruction, seeing through select instructions, to determine if we can

llvm/trunk/test/Transforms/InstCombine/udiv-simplify.ll

 ; CHECK-NEXT:    [[Z1:%.*]] = zext i32 [[R]] to i64
 ; CHECK-NEXT:    ret i64 [[Z1]]
 ;
   %y = lshr i32 %x, 31
   %r = udiv i32 %y, %v
   %z = sext i32 %r to i64
   ret i64 %z
 }
+
+; The udiv should be simplified according to the rule:
+; X udiv (C1 << N), where C1 is `1<<C2` --> X >> (N+C2)
+@b = external global [1 x i16]
+
+define i32 @PR30366(i1 %a) {
+; CHECK-LABEL: @PR30366(
+; CHECK-NEXT:    [[Z:%.*]] = zext i1 %a to i32
+; CHECK-NEXT:    [[D:%.*]] = lshr i32 [[Z]], zext (i16 ptrtoint ([1 x i16]* @b to i16) to i32)
+; CHECK-NEXT:    ret i32 [[D]]
+;
+  %z = zext i1 %a to i32
+  %d = udiv i32 %z, zext (i16 shl (i16 1, i16 ptrtoint ([1 x i16]* @b to i16)) to i32)
+  ret i32 %d
+}