This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Don't violate dominance when replacing instructions
ClosedPublic

Authored by davide on Jul 13 2017, 12:13 PM.

Details

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.

Diff Detail

Event Timeline

lib/Transforms/InstCombine/InstCombineCompares.cpp
3744

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 added inline comments.Jul 14 2017, 8:35 AM
lib/Transforms/InstCombine/InstCombineCompares.cpp
3744

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

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

lib/Transforms/InstCombine/InstCombineCompares.cpp
3744

Argument 1. looks 100% valid to me!

Thanks a lot for the fix!

This revision is now accepted and ready to land.Jul 15 2017, 12:27 PM
This revision was automatically updated to reflect the committed changes.