<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/108451>108451</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            Missed optimization: X - Y  + Y * N = X - Y * (N -1)
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          khagankhan
      </td>
    </tr>
</table>

<pre>
    LLVM does not optimize the following pattern: `X - Y + Y * N`

```llvm
; LLVM does not optimize this further
define i32 @src(i32 %0, i32 %1) local_unnamed_addr #0 {
  %3 = sub i32 %0, %1 ; a - b
  %4 = mul i32 %1, 2 ; b * 2
  %5 = add i32 %3, %4 ; a - b + b * 2 (which is simply a + b)
  ret i32 %5 ; return a + b
}
```

which can be simply written as:
```llvm
define i32 @tgt(i32 %0, i32 %1) local_unnamed_addr #0 {
  %3 = add i32 %1, %0 ; a + b
  ret i32 %3 ; return a + b
}
```

Alive2 confirms that this is a correct transformation [here](https://alive2.llvm.org/ce/z/u6ys9T)

Well I have added the following pattern to the `llvm/lib/Transforms/InstCombine/InstructionCombining.cpp` file:
```cpp
 {
    ConstantInt *C = nullptr;
    Value *X = nullptr;
    Value *Y = nullptr;
    Value *LHS = nullptr;
    Value *RHS = nullptr;
    // X - Y + Y * C = X + Y * (C - 1)
    if (match(I, m_c_Add(m_Value(LHS), m_Value(RHS)))) {
      if (match(LHS, m_Sub(m_Value(X), m_Value(Y))) &&
          match(RHS, m_c_Mul(m_Value(Y), m_ConstantInt(C)))) {
        Value *NewMul = IC.Builder.CreateMul(
 Y, IC.Builder.CreateSub(C, ConstantInt::get(C->getType(), 1)));
 Instruction *NewAdd = BinaryOperator::CreateAdd(X, NewMul);
 return NewAdd;
      }
    }
}
```

When I recompiled LLVM with this version the optimization fired 18 times.
I also added these tests that pass (Each test has Alive2 verification link with):

```llvm
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -passes=instcombine -S | FileCheck %s

;; LLVM has no optimizations for the following: https://godbolt.org/z/rGnGE79Wv
;; <- Positive Tests ->

;; LHS: For positive numbers
;; ALive2 verified: https://alive2.llvm.org/ce/z/66iv-o
define i32 @test1(i32 %A, i32 %B) {
  %C = sub i32 %A, %B     
  %D = mul i32 %B, 10        
  %E = add i32 %C, %D       
  ret i32 %E                 
; CHECK-LABEL: @test1(
; CHECK-NEXT:    [[F:%.*]] = mul i32 [[B:%.*]], 9
; CHECK-NEXT: [[G:%.*]] = add i32 [[B:%.*]], [[F:%.*]]
; CHECK-NEXT:    ret i32 [[G:%.*]]
;
}

;; LHS: For Negative numbers
;; Alive2 verified: https://alive2.llvm.org/ce/z/Q2cups
define i32 @test2(i32 %A, i32 %B) {
  %C = sub i32 %A, %B     
  %D = mul i32 %B, -10        
 %E = add i32 %C, %D       
  ret i32 %E                 
; CHECK-LABEL: @test2(
; CHECK-NEXT:    [[F:%.*]] = mul i32 [[B:%.*]], -11
; CHECK-NEXT:    [[G:%.*]] = add i32 [[B:%.*]], [[F:%.*]]
; CHECK-NEXT:    ret i32 [[G:%.*]]
;
}

;; RHS: For positive numbers
;; Alive2 verified: https://alive2.llvm.org/ce/z/xTD-6v
define i32 @test3(i32 %A, i32 %B) {
  %C = mul i32 %B, 10 ; b * 10
  %D = sub i32 %A, %B ; a - b
  %E = add i32 %D, %C ; a + 9 * b
  ret i32 %E
; CHECK-LABEL: @test3(
; CHECK-NEXT:    [[F:%.*]] = mul i32 [[B:%.*]], 9
; CHECK-NEXT:    [[G:%.*]] = add i32 [[B:%.*]], [[F:%.*]]
; CHECK-NEXT:    ret i32 [[G:%.*]]
;
}

;; RHS: For negative numbers
;; Alive2 verified: https://alive2.llvm.org/ce/z/c6e77U
define i32 @test4(i32 %A, i32 %B) {
  %C = mul i32 %B, -10 ; b * 10
  %D = sub i32 %A, %B ; a - b
  %E = add i32 %D, %C ; a + 9 * b
  ret i32 %E
; CHECK-LABEL: @test4(
; CHECK-NEXT:    [[F:%.*]] = mul i32 [[B:%.*]], -11
; CHECK-NEXT:    [[G:%.*]] = add i32 [[B:%.*]], [[F:%.*]]
; CHECK-NEXT:    ret i32 [[G:%.*]]
;
}

;; <- Negative Tests ->

;; When mul B, C where C can be shl no optimization happens
;; Alive2 verified: https://alive2.llvm.org/ce/z/w23md4
define i32 @test5(i32 %A, i32 %B) {
  %C = sub i32 %A, %B     
  %D = mul i32 %B, 8      
 %E = add i32 %C, %D       
  ret i32 %E                 
; CHECK-LABEL: @test5(
; CHECK-NOT:    [[F:%.*]] = mul i32 [[B:%.*]], 7
}
```

To be honest, I am not sure if it is worth of implementing. But if it is and if my way looks okay you can assign this to me.

Acknowledgement: This work has been done by the student Khagan Karimov for the initial two assignments from the CS6475-Advanced Compilers course, being instructed by Prof. Dr. John Regehr at the University pf Utah.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzsWF1z4jjW_jXKzSkoI2M-LrgAA915O52eN0lPJ1cp2T7G2tiSS5JhmV-_JdmAIZD0zPT01GxtiqKC_OjR-Xh8pCOmNV8JxAkJZiSYX7HKZFJNXjK2YuIlY-Iqksl2cnPz62dIJGoQ0oAsDS_4bwgmQ0hlnssNFysomTGoBPGnQAbeI3TgCQidue8p3JKBR7w58abN98CrP3m-LpohfwYXV-Ia0kqZDFUNTjDlAoH7FEjf0yomdOR-0MAjNITm_x6hY8hlzPLnSghWYPLMkkQBob4HZDirycBCfSD-HHQVQZvHcoC1jEEHoha87-BFlbeWCoE6bORcpi104NAsSXZovyHvH8hdtJqpQOhok_E4A65B86LMt8BqAKHjHbFCs-MLHI9CUymxR9ZhHc5PQt7OQ71IzAREuFtoo7gxKIBp4l9O13EGzMr8oAy0gtRrguQ1QWp5deS8_wedn-Z8jRRiKVKuCg0mY6bWGtfAIJZKYWzAKCZ0KlXBDJcCSDDLUCEJ5oSOMmNKFya6JHTJHGHXBqkr1YrQZYyELn8jdFkNtnr8sE9e_f0N8xyuIWNrtH5jcv6dAiPdg1386TLnEaHLh51hmtDltdAmlEXEBTa_VBVbg-tBLlbduCzJwIOU5_g6s_ZhHdpWVgBCKbRhwlwLY6UZuhyJKs9Lo4jfAv7K8got5PF9yNP7kJuP9--D7t4A1RmB00JUO_DYGiF0FEIHeq0XC4CndrxgJs4IHV1bIRbP8fM0Sezws7OA0NHNx3s7zT3djd01Y83nOJynzI7Azr6voiPmx1e8Ty1KOrCfFqv923He7Tjj589VfsT6tGdt5dUG4C2LWwG_xc3nKnchvA67s4rnCapuqJAZrNdqJj7ZVV5BaidD-6y9vj8l_nSFzpAO8RcrNA_b0trbmNs7mLdPcUvhjWXTJHGWzbhgavulRMWMVDV7vX6dvkdLWXtyxNgUkJrpSEsA-0Jy9OPt8vItQwHXoDCWRclzTOrtbcNNVleZNSptzbfvdrPX1SUm5QoT6I3A8AJ1t6a7BpZreagTGsGgNk3ZKpnWVlgLFmduHDKmoalwa1Q85XFNnnPx4oxwzk-_Y1e-_fKwsPv6VGtUlkPXJStCu0tURq5Q2GBjAtEWKsNzW5CqMmEGn60tz3GG8YvultsD6d3XW8spSwPEd2VeQ8d6gZr4cy60ietqBp17IMMQljzH0PI47JHZ_mx_eLBeC3kUTg2pVMeV1a58XLpXMolkbpqybSu2-iA-LIbjb-ujRYgfduAXqbnha4QHlwCr2XP2fLy36yylgnI3QVRFhEof4aY3rSRh8tq2N7aVwYCvO_Lsjoza9A578rS1J89OXnJCg_D09DNt9t5ZLf8Dcn568Jm5N9Tb1YoWdHG6oYcN6fwE29rLF3D6d5BM-HERfurcTGeLG3fMPDh5irldPD5YiJ1uj7azpQtm0CV0ajfuUy8cZnaKsdaOL1HXcz6c5d27fJn3gllvOLIP0vmFD5I6KU0XJHmLK3ZZkvkfl-T_07gq9SVJ0p8myc4rTf40SdK_VJKdXu9d8n-YLu--t1T-CV3--2HeGawv6dL_nbo8UwAPrV_Pe6XOszo-11i-Uui8gYetLmjsljnXCy3e06b_95TL_wJlir-qYsYDHA6_XlJm_08qs_OPkWb_f2Xz94nTHUb3G_mbh1HXjNgoOU2EsMlQIYT7q58sPz02Q8bKEsWPk_mG-kXSvyTz4KcdDEZ_z6EgOKfuLz9I3MPvaUgfpE11JgVq4_pzYIW7aNWVQuApcANcw0Yqk4FMgRdljgUKw8WqC7PKHDBMJPZHsYUN20Iu5YsG-cK2sJWV01R9tVz3uUZCgd2jm7f4RchNjsnK8dsYPGT10i-uhXOtZSIF2o7Stm7aVAkKA5_c3TR8YooXcr3v7LjghrMczEY2S1teDamShQOE94P-MOhMkzUTMSYQ1j250hDLSmm08YiQixXw5mKh7mZ_UTLtwlx14f9kJuAOV5gpcPeECF8Fdz282UKZwlfDsu5VMvGTsT9mVzjpDemgN-xTv3-VTYJeOqDBKB35UW889v3xMArGERumDHtj5sVXfEI92vfGPUq9wPP73WAwHMf9_oAOUjaI04j0PSwYz_cv1xXXusJJzxv1g95VziLM9e4qX00sqhNVK036Xs610Yd5hpscJ5-51pgcvfM2EfWNWfvuvrky6xwuzG6h0yN0fFWpfHLSR3OTVVE3lu6asrmttJaUSv4LY0Po0lmtCV02hq8n9D8BAAD__wGAdYA">