[InstCombine] Extending InstructionSimplify

[opaparo]

Summary

1. So far, InstructionSimplify would not approach OverflowingBinaryOperators and PossiblyExactOperators. If it have encountered one of these, it would simply give up, aborting the transformation. However, in some cases, these operators can be proven to be safe, and the transformation can carry on. I've added a function for each of the two types, determining whether they are safe or not. In this patch I've added support for all types of shifts.
2. Added support for CastInst for specific cases.

[hfinkel]

lib/Analysis/InstructionSimplify.cpp

3432

I'd prefer not to have these kinds of TODO comment. If you have specific ideas, that's good to mention, but comments that are essentially "TODO: Think about this more.", don't add much value.

Comments should also end with a period.

In any case, with a bit of refactoring, I think that you could handle this in a more-general way. There definitely are other cases that could be handled. Note that the implementation in ValueTracking of known bits for an add/sub is essentially:

unsigned BitWidth = KnownOut.getBitWidth();
KnownBits LHSKnown(BitWidth);
computeKnownBits(Op0, LHSKnown, Depth + 1, Q);
computeKnownBits(Op1, Known2, Depth + 1, Q);
KnownOut = KnownBits::computeForAddSub(Add, NSW, LHSKnown, Known2);

where the actual logic has been put in KnownBits::computeForAddSub (in lib/Support/KnownBits.cpp). To detect whether we can prove non-overflow, you could get the known bits of the operands, make the APInts larger, call KnownBits::computeForAddSub, and then see if the extended bits of the result are all known zero.

KnownBits::computeForAddSub is currently the only part of ValueTracking split out like that, but the same could be done for the code in computeKnownBitsMul and computeKnownBitsFromShiftOperator (or, more specifically, the relevant code in its caller) to handle mul and shifts.

[opaparo]

1. Generalized InstructionSimplify's IsSafeOverflowingBinaryOperator to handle 'add', 'sub' and 'mul' in addition to 'shl'. This was done by refactoring existing behavior out of InstCombine's internals into ValueTracking, so now both InstCombine and InstructionSimplify use it.
2. Added tests to cover possible cases. For each OverflowingBinaryOperator ('shl', 'add', 'sub' and 'mul') I've created tests according to the Cartesian product of four factors: the op has the nuw flag, the op has the nsw flag, there actually is an unsigned overflow, there actually is a signed overflow. The key idea is to check that optimizations occur if and only if the overflow flag is absent or no overflow is guaranteed. also note that the file name had changed from select-bitext-bitwise-ops.ll to select-obo-peo-ops.ll to better reflect the nature of the tests it contains.

[opaparo]

Ping

[opaparo]

Ping

lib/Analysis/InstructionSimplify.cpp

static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
   return nullptr;
 }
 
 Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
                               FastMathFlags FMF, const SimplifyQuery &Q) {
   return ::SimplifyFCmpInst(Predicate, LHS, RHS, FMF, Q, RecursionLimit);
 }
 
+static bool
+IsSafeOverflowingBinaryOperator(const OverflowingBinaryOperator *OBO,
+                                const SimplifyQuery &Q) {
+  const Instruction *I = dyn_cast_or_null<Instruction>(OBO);
+  if (!I)
+    return false;
+  if (I->getOpcode() != Instruction::Shl)
+    // TODO: Perhaps we can handle other instructions too
+    return false;
+
+  Value *Op0 = I->getOperand(0), *Op1 = I->getOperand(1);
+
+  const APInt *ShAmtAPInt;
+  if (!match(Op1, m_APInt(ShAmtAPInt)))
+    return false;
+
+  unsigned ShAmt = ShAmtAPInt->getZExtValue();
+  unsigned BitWidth = I->getType()->getScalarSizeInBits();
+
+  if (I->hasNoUnsignedWrap() &&
+      !MaskedValueIsZero(Op0, APInt::getHighBitsSet(BitWidth, ShAmt), Q.DL, 0,
+                         Q.AC, I, Q.DT))
+    return false;
+
+  if (I->hasNoSignedWrap() &&
+      ComputeNumSignBits(Op0, Q.DL, 0, Q.AC, I, Q.DT) <= ShAmt)
+    return false;
+
+  return true;
+}
+
+static bool IsSafePossiblyExactOperator(const PossiblyExactOperator *PEO,
+                                        const SimplifyQuery &Q) {
+  const Instruction *I = dyn_cast_or_null<Instruction>(PEO);
+  if (!I)
+    return false;
+  if (I->getOpcode() != Instruction::LShr &&
+      I->getOpcode() != Instruction::AShr)
+    // TODO: Perhaps we can handle other instructions too
+    return false;
+
+  Value *Op0 = I->getOperand(0), *Op1 = I->getOperand(1);
+
+  const APInt *ShAmtAPInt;
+  if (!match(Op1, m_APInt(ShAmtAPInt)))
+    return false;
+
+  unsigned ShAmt = ShAmtAPInt->getZExtValue();
+  unsigned BitWidth = I->getType()->getScalarSizeInBits();
+
+  if (I->isExact() &&
+      !MaskedValueIsZero(Op0, APInt::getLowBitsSet(BitWidth, ShAmt), Q.DL, 0,
+                         Q.AC, I, Q.DT))
+    return false;
+
+  return true;
+}
+
 /// See if V simplifies when its operand Op is replaced with RepOp.
 static const Value *SimplifyWithOpReplaced(Value *V, Value *Op, Value *RepOp,
                                            const SimplifyQuery &Q,
                                            unsigned MaxRecurse) {
   // Trivial replacement.
   if (V == Op)
     return RepOp;
 
   // We cannot replace a constant, and shouldn't even try.
   if (isa<Constant>(Op))
     return nullptr;
 
   auto *I = dyn_cast<Instruction>(V);
   if (!I)
     return nullptr;
 
   // If this is a binary operator, try to simplify it with the replaced op.
   if (auto *B = dyn_cast<BinaryOperator>(I)) {
     // Consider:
     //   %cmp = icmp eq i32 %x, 2147483647
     //   %add = add nsw i32 %x, 1
     //   %sel = select i1 %cmp, i32 -2147483648, i32 %add
     //
     // We can't replace %sel with %add unless we strip away the flags.
-    if (isa<OverflowingBinaryOperator>(B))
-      if (B->hasNoSignedWrap() || B->hasNoUnsignedWrap())
+    if (OverflowingBinaryOperator *OBO = dyn_cast<OverflowingBinaryOperator>(B))
+      if (!IsSafeOverflowingBinaryOperator(OBO, Q))
         return nullptr;
-    if (isa<PossiblyExactOperator>(B))
-      if (B->isExact())
+    if (PossiblyExactOperator *PEO = dyn_cast<PossiblyExactOperator>(B))
+      if (!IsSafePossiblyExactOperator(PEO, Q))
         return nullptr;
 
     if (MaxRecurse) {
       if (B->getOperand(0) == Op)
         return SimplifyBinOp(B->getOpcode(), RepOp, B->getOperand(1), Q,
                              MaxRecurse - 1);
       if (B->getOperand(1) == Op)
         return SimplifyBinOp(B->getOpcode(), B->getOperand(0), RepOp, Q,
                              MaxRecurse - 1);
     }
   }
 
   // Same for CmpInsts.
   if (CmpInst *C = dyn_cast<CmpInst>(I)) {
     if (MaxRecurse) {
       if (C->getOperand(0) == Op)
         return SimplifyCmpInst(C->getPredicate(), RepOp, C->getOperand(1), Q,
                                MaxRecurse - 1);
       if (C->getOperand(1) == Op)
         return SimplifyCmpInst(C->getPredicate(), C->getOperand(0), RepOp, Q,
                                MaxRecurse - 1);
     }
   }
 
+  if (CastInst *C = dyn_cast<CastInst>(I)) {
+    if (MaxRecurse) {
+      const Value *CastInstWithReplacement = SimplifyWithOpReplaced(
+          I->getOperand(0), Op, RepOp, Q, MaxRecurse - 1);
+      if (const Constant *Const =
+              dyn_cast_or_null<Constant>(CastInstWithReplacement))
+        return ConstantExpr::getCast(
+            C->getOpcode(), const_cast<Constant *>(Const), C->getType());
+    }
+  }
+
   // TODO: We could hand off more cases to instsimplify here.
 
   // If all operands are constant after substituting Op for RepOp then we can
   // constant fold the instruction.
   if (Constant *CRepOp = dyn_cast<Constant>(RepOp)) {
     // Build a list of all constant operands.
     SmallVector<Constant *, 8> ConstOps;
     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {

test/Transforms/InstCombine/select-bitext-bitwise-ops.ll

 ; RUN: opt -S -instcombine < %s | FileCheck %s
 
 define i64 @sel_false_val_is_a_masked_shl_of_true_val1(i32 %x, i64 %y) {
 ; CHECK-LABEL: @sel_false_val_is_a_masked_shl_of_true_val1(
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 15 
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 15
 ; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i32 [[TMP1]], 2
 ; CHECK-NEXT:    [[TMP3:%.*]] = zext i32 [[TMP2]] to i64
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP1]], 0
-; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP4]], i64 0, i64 [[TMP3]]
-; CHECK-NEXT:    [[TMP6:%.*]] = ashr i64 %y, [[TMP5]]
-; CHECK-NEXT:    ret i64 [[TMP6]]
+; CHECK-NEXT:    [[TMP4:%.*]] = ashr i64 %y, [[TMP3]]
+; CHECK-NEXT:    ret i64 [[TMP4]]
 ;
   %1 = and i32 %x, 15
   %2 = shl nuw nsw i32 %1, 2
   %3 = zext i32 %2 to i64
   %4 = icmp eq i32 %1, 0
   %5 = ashr i64 %y, %3
   %6 = select i1 %4, i64 %y, i64 %5
   ret i64 %6
 }
 
 define i64 @sel_false_val_is_a_masked_shl_of_true_val2(i32 %x, i64 %y) {
 ; CHECK-LABEL: @sel_false_val_is_a_masked_shl_of_true_val2(
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 15
 ; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i32 [[TMP1]], 2
 ; CHECK-NEXT:    [[TMP3:%.*]] = zext i32 [[TMP2]] to i64
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP1]], 0
-; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP4]], i64 0, i64 [[TMP3]]
-; CHECK-NEXT:    [[TMP6:%.*]] = ashr i64 %y, [[TMP5]]
-; CHECK-NEXT:    ret i64 [[TMP6]]
+; CHECK-NEXT:    [[TMP4:%.*]] = ashr i64 %y, [[TMP3]]
+; CHECK-NEXT:    ret i64 [[TMP4]]
 ;
   %1 = and i32 %x, 15
   %2 = shl nuw nsw i32 %1, 2
   %3 = zext i32 %2 to i64
   %4 = icmp eq i32 %2, 0
   %5 = ashr i64 %y, %3
   %6 = select i1 %4, i64 %y, i64 %5
   ret i64 %6
 }
 
 define i64 @sel_false_val_is_a_masked_lshr_of_true_val1(i32 %x, i64 %y) {
 ; CHECK-LABEL: @sel_false_val_is_a_masked_lshr_of_true_val1(
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 60
-; CHECK-NEXT:    [[TMP2:%.*]] = lshr exact i32 [[TMP1]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 %x, 2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 15
 ; CHECK-NEXT:    [[TMP3:%.*]] = zext i32 [[TMP2]] to i64
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP1]], 0
-; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP4]], i64 0, i64 [[TMP3]]
-; CHECK-NEXT:    [[TMP6:%.*]] = ashr i64 %y, [[TMP5]]
-; CHECK-NEXT:    ret i64 [[TMP6]]
+; CHECK-NEXT:    [[TMP4:%.*]] = ashr i64 %y, [[TMP3]]
+; CHECK-NEXT:    ret i64 [[TMP4]]
 ;
   %1 = and i32 %x, 60
   %2 = lshr i32 %1, 2
   %3 = zext i32 %2 to i64
   %4 = icmp eq i32 %1, 0
   %5 = ashr i64 %y, %3
   %6 = select i1 %4, i64 %y, i64 %5
   ret i64 %6
;
   %4 = icmp eq i32 %2, 0
   %5 = ashr i64 %y, %3
   %6 = select i1 %4, i64 %y, i64 %5
   ret i64 %6
 }
 
 define i64 @sel_false_val_is_a_masked_ashr_of_true_val1(i32 %x, i64 %y) {
 ; CHECK-LABEL: @sel_false_val_is_a_masked_ashr_of_true_val1(
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, -2147483588
-; CHECK-NEXT:    [[TMP2:%.*]] = ashr exact i32 [[TMP1]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = ashr i32 %x, 2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], -536870897
 ; CHECK-NEXT:    [[TMP3:%.*]] = zext i32 [[TMP2]] to i64
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP1]], 0
-; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP4]], i64 0, i64 [[TMP3]]
-; CHECK-NEXT:    [[TMP6:%.*]] = ashr i64 %y, [[TMP5]]
-; CHECK-NEXT:    ret i64 [[TMP6]]
+; CHECK-NEXT:    [[TMP4:%.*]] = ashr i64 %y, [[TMP3]]
+; CHECK-NEXT:    ret i64 [[TMP4]]
 ;
   %1 = and i32 %x, -2147483588
   %2 = ashr i32 %1, 2
   %3 = zext i32 %2 to i64
   %4 = icmp eq i32 %1, 0
   %5 = ashr i64 %y, %3
   %6 = select i1 %4, i64 %y, i64 %5
   ret i64 %6