[InstCombine] Don't violate dominance when replacing instructions

[davide]

Summary

When we match a MulZExtIdiom, after r307554, and we try to replace the original mul with a narrower one, we look at the uses of the mul, and if one is a BinaryOperator we create a trunc based on it.

From the diff in r307554.

> -        ConstantInt *CI = cast<ConstantInt>(BO->getOperand(1));
> -        APInt ShortMask = CI->getValue().trunc(MulWidth);
> +        Value *ShortMask =
> +            Builder.CreateTrunc(BO->getOperand(1), Builder.getIntNTy(MulWidth));

As pointed out in the ML thread, I don't think this is quite right.

Bo->getOperand(1) could live in another block, consider e.g.

@glob = external global i16

define void @patatino(i8 %beth) {
  %conv = zext i8 %beth to i32
  %mul = mul nuw nsw i32 %conv, %conv
  %conv3 = and i32 %mul, 255
  %tobool8 = icmp ne i32 %mul, %conv3
  br i1 %tobool8, label %if.then9, label %if.then9

if.then9:                                         ; preds = %0, %0
  %tinky = load i16, i16* @glob
  %conv13 = sext i16 %tinky to i32
  %and = and i32 %mul, %conv13
  %conv14 = trunc i32 %and to i16
  store i16 %conv14, i16* @glob
  ret void
}

after this transformation would become:

define void @patatino(i8 %beth) {
  %conv = zext i8 %beth to i32
  %umul = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 %beth, i8 %beth)
  %umul.value = extractvalue { i8, i1 } %umul, 0
  %1 = trunc i32 %conv13 to i8
  %2 = and i8 %umul.value, %1
  %3 = zext i8 %2 to i32
  %mul = mul nuw nsw i32 %conv, %conv
  %conv3 = and i32 %mul, 255
  %tobool8 = extractvalue { i8, i1 } %umul, 1
  br i1 %tobool8, label %if.then9, label %if.then9

if.then9:                                         ; preds = %0, %0
  %tinky = load i16, i16* @glob
  %conv13 = sext i16 %tinky to i32
  %and = and i32 %mul, %conv13
  %conv14 = trunc i32 %3 to i16
  store i16 %conv14, i16* @glob
  ret void
}

Note how you're inserting %1 which has an operand an use of %conv13 which is defined in %if.then9, i.e. you end up with a def that doesn't dominate all the uses -> violates SSA.
As I'm not sure how common this case is, I propose fixing restoring the old behaviour, and in order to fix the original crash bail out in case the first operand of the binary op is not a constant, as the code after actually assumes this.

[davide]

Forgot to mention. This fixes https://bugs.llvm.org/show_bug.cgi?id=33765

[serge-sans-paille]

lib/Transforms/InstCombine/InstCombineCompares.cpp

3744 ↗

(On Diff #106487)

Ok, i understand and agree with the rational behind this fix. Would it be reasonable to check if the operand is either a constant or defined in the same block, previous to current instruction, in order to catch more candidates?

[davide]

lib/Transforms/InstCombine/InstCombineCompares.cpp

3744 ↗

(On Diff #106487)

As far as I can tell the canonical way to see if two instruction are ordered is to get a local numbering via OrderedBasicBlocks. I'm not sure it's worth the trouble here, unless there's a super-cheap way of computing it.

Note that:

1. This always assumed constant (and not instructions) for many years but never seem to have triggered.
2. The only two cases where this triggered are clearly tests crafted by a fuzzer. Whether I agree we shouldn't crash or produce something that violates SSA, I'm not sure it's good value for money.

3744 ↗

(On Diff #106487)

Sigh, what I mean here is: "the canonical way to check if an instruction is defined before or after another in the same BB"

[serge-sans-paille]

lib/Transforms/InstCombine/InstCombineCompares.cpp

3744 ↗

(On Diff #106487)

Argument 1. looks 100% valid to me!

[serge-sans-paille]

Thanks a lot for the fix!

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

for (User *U : MulVal->users()) {
       } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(U)) {
         // Check if AND ignores bits above MulWidth.
         if (BO->getOpcode() != Instruction::And)
           return nullptr;
         if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) {
           const APInt &CVal = CI->getValue();
           if (CVal.getBitWidth() - CVal.countLeadingZeros() > MulWidth)
             return nullptr;
+        } else {
+          // In this case we could have the operand of the binary operation
+          // being defined in another block, and performing the replacement
+          // could break the dominance relation.
+          return nullptr;
         }
       } else {
         // Other uses prohibit this transformation.
         return nullptr;
       }
     }
 
   // Recognize patterns
for (User *U : MulVal->users()) {
       if (TruncInst *TI = dyn_cast<TruncInst>(U)) {
         if (TI->getType()->getPrimitiveSizeInBits() == MulWidth)
           IC.replaceInstUsesWith(*TI, Mul);
         else
           TI->setOperand(0, Mul);
       } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(U)) {
         assert(BO->getOpcode() == Instruction::And);
         // Replace (mul & mask) --> zext (mul.with.overflow & short_mask)
-        Value *ShortMask =
-            Builder.CreateTrunc(BO->getOperand(1), Builder.getIntNTy(MulWidth));
+        ConstantInt *CI = cast<ConstantInt>(BO->getOperand(1));
+        APInt ShortMask = CI->getValue().trunc(MulWidth);
         Value *ShortAnd = Builder.CreateAnd(Mul, ShortMask);
-        Value *Zext = Builder.CreateZExt(ShortAnd, BO->getType());
-        if (auto *ZextI = dyn_cast<Instruction>(Zext))
-          IC.Worklist.Add(ZextI);
+        Instruction *Zext =
+            cast<Instruction>(Builder.CreateZExt(ShortAnd, BO->getType()));
+        IC.Worklist.Add(Zext);
         IC.replaceInstUsesWith(*BO, Zext);
       } else {
         llvm_unreachable("Unexpected Binary operation");
       }
-      if (auto *UI = dyn_cast<Instruction>(U))
-        IC.Worklist.Add(UI);
+      IC.Worklist.Add(cast<Instruction>(U));
     }
   }
   if (isa<Instruction>(OtherVal))
     IC.Worklist.Add(cast<Instruction>(OtherVal));
 
   // The original icmp gets replaced with the overflow value, maybe inverted
   // depending on predicate.
   bool Inverse = false;

llvm/trunk/test/Transforms/InstCombine/2017-07-07-UMul-ZExt.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
-; CHECK: llvm.umul.with.overflow
 define i32 @sterix(i32, i8, i64) {
+; CHECK-LABEL: @sterix(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CONV:%.*]] = zext i32 [[TMP0:%.*]] to i64
+; CHECK-NEXT:    [[CONV1:%.*]] = sext i8 [[TMP1:%.*]] to i32
+; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[CONV1]], 1945964878
+; CHECK-NEXT:    [[SH_PROM:%.*]] = trunc i64 [[TMP2:%.*]] to i32
+; CHECK-NEXT:    [[SHR:%.*]] = lshr i32 [[MUL]], [[SH_PROM]]
+; CHECK-NEXT:    [[CONV2:%.*]] = zext i32 [[SHR]] to i64
+; CHECK-NEXT:    [[MUL3:%.*]] = mul nuw nsw i64 [[CONV]], [[CONV2]]
+; CHECK-NEXT:    [[CONV6:%.*]] = and i64 [[MUL3]], 4294967295
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i64 [[CONV6]], [[MUL3]]
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[LOR_RHS:%.*]], label [[LOR_END:%.*]]
+; CHECK:       lor.rhs:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[MUL3]], [[TMP2]]
+; CHECK-NEXT:    [[CONV4:%.*]] = trunc i64 [[AND]] to i32
+; CHECK-NEXT:    [[TOBOOL7:%.*]] = icmp eq i32 [[CONV4]], 0
+; CHECK-NEXT:    [[PHITMP:%.*]] = zext i1 [[TOBOOL7]] to i32
+; CHECK-NEXT:    br label [[LOR_END]]
+; CHECK:       lor.end:
+; CHECK-NEXT:    [[TMP3:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ [[PHITMP]], [[LOR_RHS]] ]
+; CHECK-NEXT:    ret i32 [[TMP3]]
+;
 entry:
   %conv = zext i32 %0 to i64
   %conv1 = sext i8 %1 to i32
   %mul = mul i32 %conv1, 1945964878
   %sh_prom = trunc i64 %2 to i32
   %shr = lshr i32 %mul, %sh_prom
   %conv2 = zext i32 %shr to i64
   %mul3 = mul nuw nsw i64 %conv, %conv2

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

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S %s -instcombine | FileCheck %s
+
+@glob = external global i16
+
+define void @patatino(i8 %beth) {
+; CHECK-LABEL: @patatino(
+; CHECK-NEXT:    [[CONV:%.*]] = zext i8 [[BETH:%.*]] to i32
+; CHECK-NEXT:    br i1 undef, label [[IF_THEN9:%.*]], label [[IF_THEN9]]
+; CHECK:       if.then9:
+; CHECK-NEXT:    [[MUL:%.*]] = mul nuw nsw i32 [[CONV]], [[CONV]]
+; CHECK-NEXT:    [[TINKY:%.*]] = load i16, i16* @glob, align 2
+; CHECK-NEXT:    [[CONV131:%.*]] = zext i16 [[TINKY]] to i32
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[MUL]], [[CONV131]]
+; CHECK-NEXT:    [[CONV14:%.*]] = trunc i32 [[AND]] to i16
+; CHECK-NEXT:    store i16 [[CONV14]], i16* @glob, align 2
+; CHECK-NEXT:    ret void
+;
+  %conv = zext i8 %beth to i32
+  %mul = mul nuw nsw i32 %conv, %conv
+  %conv3 = and i32 %mul, 255
+  %tobool8 = icmp ne i32 %mul, %conv3
+  br i1 %tobool8, label %if.then9, label %if.then9
+
+if.then9:
+  %tinky = load i16, i16* @glob
+  %conv13 = sext i16 %tinky to i32
+  %and = and i32 %mul, %conv13
+  %conv14 = trunc i32 %and to i16
+  store i16 %conv14, i16* @glob
+  ret void
+}