[InstCombine] Combine neg of shl of sub (PR44529)

[nikic]

Summary

Fixes https://bugs.llvm.org/show_bug.cgi?id=44529. We already have a combine to sink a negation through a left-shift, but it currently only works if the shift operand is negatable without creating any instructions. This patch introduces freelyNegateValue() as a more powerful extension of dyn_castNegVal(), which allows negating a value as long as this doesn't end up increasing instruction count. Specifically, this patch adds support for negating A-B to B-A.

This mechanism could in the future be extended to handle general negation chains that a) start at a proper 0-X negation and b) only require one operand to be freely negatable. This would end up as a weaker form of D68408 aimed at the most obviously profitable subset (that eliminates a negation).

[spatel]

LGTM - last comment I saw on the negator was that it's on hold, and this improvement shouldn't be hard to subsume if we do proceed there.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (match(Op0, m_Zero())) {
             BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(Op11C));
         BO->setIsExact(cast<BinaryOperator>(Op1)->isExact());
         return BO;
       }
     }
 
     // 0 - (X << Y)  -> (-X << Y)   when X is freely negatable.
     if (match(Op1, m_Shl(m_Value(X), m_Value(Y))) && match(Op0, m_Zero()))
-      if (Value *XNeg = dyn_castNegVal(X))
+      if (Value *XNeg = freelyNegateValue(X))
         return BinaryOperator::CreateShl(XNeg, Y);
 
     // Subtracting -1/0 is the same as adding 1/0:
     // sub [nsw] Op0, sext(bool Y) -> add [nsw] Op0, zext(bool Y)
     // 'nuw' is dropped in favor of the canonical form.
     if (match(Op1, m_SExt(m_Value(Y))) &&
         Y->getType()->getScalarSizeInBits() == 1) {
       Value *Zext = Builder.CreateZExt(Y, I.getType());

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

public:
 
   LoadInst *combineLoadToNewType(LoadInst &LI, Type *NewTy,
                                  const Twine &Suffix = "");
 
 private:
   bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
   bool shouldChangeType(Type *From, Type *To) const;
   Value *dyn_castNegVal(Value *V) const;
+  Value *freelyNegateValue(Value *V);
   Type *FindElementAtOffset(PointerType *PtrTy, int64_t Offset,
                             SmallVectorImpl<Value *> &NewIndices);
 
   /// Classify whether a cast is worth optimizing.
   ///
   /// This is a helper to decide whether the simplification of
   /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
   ///

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

for (unsigned i = 0, e = CV->getNumOperands(); i != e; ++i) {
         return nullptr;
     }
     return ConstantExpr::getNeg(CV);
   }
 
   return nullptr;
 }
 
+/// Get negated V (that is 0-V) without increasing instruction count,
+/// assuming that the original V will become unused.
+Value *InstCombiner::freelyNegateValue(Value *V) {
+  if (Value *NegV = dyn_castNegVal(V))
+    return NegV;
+
+  if (!V->hasOneUse())
+    return nullptr;
+
+  Value *A, *B;
+  // 0-(A-B)  =>  B-A
+  if (match(V, m_Sub(m_Value(A), m_Value(B))))
+    return Builder.CreateSub(B, A);
+
+  return nullptr;
+}
+
 static Value *foldOperationIntoSelectOperand(Instruction &I, Value *SO,
                                              InstCombiner::BuilderTy &Builder) {
   if (auto *Cast = dyn_cast<CastInst>(&I))
     return Builder.CreateCast(Cast->getOpcode(), SO, I.getType());
 
   assert(I.isBinaryOp() && "Unexpected opcode for select folding");
 
   // Figure out if the constant is the left or the right argument.

llvm/test/Transforms/InstCombine/sub.ll

 ;
   %shl = shl i32 3, %x
   %neg = sub i32 0, %shl
   ret i32 %neg
 }
 
 define i64 @test_neg_shl_sub(i64 %a, i64 %b) {
 ; CHECK-LABEL: @test_neg_shl_sub(
-; CHECK-NEXT:    [[SUB:%.*]] = sub i64 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[MUL:%.*]] = shl i64 [[SUB]], 2
-; CHECK-NEXT:    [[NEG:%.*]] = sub i64 0, [[MUL]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[NEG:%.*]] = shl i64 [[TMP1]], 2
 ; CHECK-NEXT:    ret i64 [[NEG]]
 ;
   %sub = sub i64 %a, %b
   %mul = shl i64 %sub, 2
   %neg = sub i64 0, %mul
   ret i64 %neg
 }