hoist-binop.ll | Explore in Territory

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

; Fold ADD and remove old op if unused.
define void @add_one_use(i64 %c1, i64 %c2) {
; CHECK-LABEL: @add_one_use(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[INVARIANT_OP:%.*]] = add i64 [[C1:%.*]], [[C2:%.*]]
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDEX_NEXT_REASS:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[INDEX_NEXT_REASS]] = add i64 [[INDEX]], [[INVARIANT_OP]]
; CHECK-NEXT:    br label [[LOOP]]
;
entry:
  br label %loop

loop:
  %index = phi i64 [ 0, %entry ], [ %index.next, %loop ]
  %step.add = add i64 %index, %c1
  %index.next = add i64 %step.add, %c2
  br label %loop
}

; Fold ADD and copy NUW if both ops have it.
; https://alive2.llvm.org/ce/z/bPAT7Z
define void @add_nuw(i64 %c1, i64 %c2) {
; CHECK-LABEL: @add_nuw(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[INVARIANT_OP:%.*]] = add nuw i64 [[C1:%.*]], [[C2:%.*]]
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDEX_NEXT_REASS:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[STEP_ADD:%.*]] = add nuw i64 [[INDEX]], [[C1]]
; CHECK-NEXT:    call void @use(i64 [[STEP_ADD]])
; CHECK-NEXT:    [[INDEX_NEXT_REASS]] = add nuw i64 [[INDEX]], [[INVARIANT_OP]]
; CHECK-NEXT:    br label [[LOOP]]
;
entry:
  br label %loop

loop:
  %index = phi i64 [ 0, %entry ], [ %index.next, %loop ]
  %step.add = add nuw i64 %index, %c1
  call void @use(i64 %step.add)
  %index.next = add nuw i64 %step.add, %c2
  br label %loop
}

; Fold ADD but don't copy NUW if only one op has it.
define void @add_no_nuw(i64 %c1, i64 %c2) {
; CHECK-LABEL: @add_no_nuw(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[INVARIANT_OP:%.*]] = add i64 [[C1:%.*]], [[C2:%.*]]
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDEX_NEXT_REASS:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[STEP_ADD:%.*]] = add i64 [[INDEX]], [[C1]]
; CHECK-NEXT:    call void @use(i64 [[STEP_ADD]])
; CHECK-NEXT:    [[INDEX_NEXT_REASS]] = add i64 [[INDEX]], [[INVARIANT_OP]]
; CHECK-NEXT:    br label [[LOOP]]
;
entry:
  br label %loop

loop:
  %index = phi i64 [ 0, %entry ], [ %index.next, %loop ]
  %step.add = add i64 %index, %c1
  call void @use(i64 %step.add)
  %index.next = add nuw i64 %step.add, %c2
  br label %loop
}

; Fold ADD but don't copy NSW if one op has it.
define void @add_no_nsw(i64 %c1, i64 %c2) {
; CHECK-LABEL: @add_no_nsw(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[INVARIANT_OP:%.*]] = add i64 [[C1:%.*]], [[C2:%.*]]
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDEX_NEXT_REASS:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[STEP_ADD:%.*]] = add i64 [[INDEX]], [[C1]]
; CHECK-NEXT:    call void @use(i64 [[STEP_ADD]])
; CHECK-NEXT:    [[INDEX_NEXT_REASS]] = add i64 [[INDEX]], [[INVARIANT_OP]]
; CHECK-NEXT:    br label [[LOOP]]
;
entry:
  br label %loop

loop:
  %index = phi i64 [ 0, %entry ], [ %index.next, %loop ]
  %step.add = add i64 %index, %c1
  call void @use(i64 %step.add)
  %index.next = add nsw i64 %step.add, %c2
  br label %loop
}

; Fold ADD but don't copy NSW even if both ops have it.
define void @add_no_nsw_2(i64 %c1, i64 %c2) {
; CHECK-LABEL: @add_no_nsw_2(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[INVARIANT_OP:%.*]] = add i64 [[C1:%.*]], [[C2:%.*]]
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDEX_NEXT_REASS:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[STEP_ADD:%.*]] = add nsw i64 [[INDEX]], [[C1]]
; CHECK-NEXT:    call void @use(i64 [[STEP_ADD]])
; CHECK-NEXT:    [[INDEX_NEXT_REASS]] = add i64 [[INDEX]], [[INVARIANT_OP]]
; CHECK-NEXT:    br label [[LOOP]]
;
entry:
  br label %loop

loop:
  %index = phi i64 [ 0, %entry ], [ %index.next, %loop ]
  %step.add = add nsw i64 %index, %c1
  call void @use(i64 %step.add)
  %index.next = add nsw i64 %step.add, %c2
  br label %loop
}

; Don't fold if the ops are different (even if they are both associative).
define void @diff_ops(i64 %c1, i64 %c2) {
; CHECK-LABEL: @diff_ops(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDEX_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[STEP_ADD:%.*]] = add i64 [[INDEX]], [[C1:%.*]]
; CHECK-NEXT:    call void @use(i64 [[STEP_ADD]])
; CHECK-NEXT:    [[INDEX_NEXT]] = mul i64 [[STEP_ADD]], [[C2:%.*]]
; CHECK-NEXT:    br label [[LOOP]]
;
entry:
  br label %loop

loop:
  %index = phi i64 [ 0, %entry ], [ %index.next, %loop ]
  %step.add = add i64 %index, %c1
  call void @use(i64 %step.add)
  %index.next = mul i64 %step.add, %c2
  br label %loop
}

; Don't fold if the ops are not associative.
define void @noassoc_ops(i64 %c1, i64 %c2) {
; CHECK-LABEL: @noassoc_ops(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDEX_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[STEP_ADD:%.*]] = sub i64 [[INDEX]], [[C1:%.*]]
; CHECK-NEXT:    call void @use(i64 [[STEP_ADD]])
; CHECK-NEXT:    [[INDEX_NEXT]] = sub i64 [[STEP_ADD]], [[C2:%.*]]
; CHECK-NEXT:    br label [[LOOP]]
;
entry:
  br label %loop

loop:
  %index = phi i64 [ 0, %entry ], [ %index.next, %loop ]
  %step.add = sub i64 %index, %c1
  call void @use(i64 %step.add)
  %index.next = sub i64 %step.add, %c2
  br label %loop
}

; Don't fold floating-point ops, even if they are associative. This would be
; valid, but is currently disabled.
define void @fadd(float %c1, float %c2) {
; CHECK-LABEL: @fadd(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[INDEX:%.*]] = phi float [ 0.000000e+00, [[ENTRY:%.*]] ], [ [[INDEX_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[STEP_ADD:%.*]] = fadd fast float [[INDEX]], [[C1:%.*]]
; CHECK-NEXT:    call void @use(float [[STEP_ADD]])
; CHECK-NEXT:    [[INDEX_NEXT]] = fadd fast float [[STEP_ADD]], [[C2:%.*]]
; CHECK-NEXT:    br label [[LOOP]]
;
entry:
  br label %loop

loop:
  %index = phi float [ 0., %entry ], [ %index.next, %loop ]
  %step.add = fadd fast float %index, %c1
  call void @use(float %step.add)
  %index.next = fadd fast float %step.add, %c2
  br label %loop
}

; Don't fold if the intermediate op has more than two uses. This is an
; heuristic that can be adjusted if warranted. Currently we are being
; conservative to minimise potential impact in code size.
define void @not_many_uses(i64 %c1, i64 %c2, i64 %c3) {
; CHECK-LABEL: @not_many_uses(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDEX_NEXT:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[STEP_ADD:%.*]] = add i64 [[INDEX]], [[C1:%.*]]
; CHECK-NEXT:    call void @use(i64 [[STEP_ADD]])
; CHECK-NEXT:    [[INDEX_NEXT]] = add i64 [[STEP_ADD]], [[C2:%.*]]
; CHECK-NEXT:    [[OTHER:%.*]] = add i64 [[STEP_ADD]], [[C3:%.*]]
; CHECK-NEXT:    call void @use(i64 [[OTHER]])
; CHECK-NEXT:    br label [[LOOP]]
;
entry:
  br label %loop

loop:
  %index = phi i64 [ 0, %entry ], [ %index.next, %loop ]
  %step.add = add i64 %index, %c1
  call void @use(i64 %step.add)
  %index.next = add i64 %step.add, %c2
  %other = add i64 %step.add, %c3
  call void @use(i64 %other)
  br label %loop
}

; Original reproducer, adapted from:
;   for(long i = 0; i < n; ++i)
;     a[i] = (i*k) * v;
define void @test(i64 %n, i64 %k) {
; CHECK-LABEL: @test(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[K_2:%.*]] = shl nuw nsw i64 [[K:%.*]], 1
; CHECK-NEXT:    [[VEC_INIT:%.*]] = insertelement <2 x i64> zeroinitializer, i64 [[K]], i64 1
; CHECK-NEXT:    [[DOTSPLATINSERT:%.*]] = insertelement <2 x i64> poison, i64 [[K_2]], i64 0
; CHECK-NEXT:    [[DOTSPLAT:%.*]] = shufflevector <2 x i64> [[DOTSPLATINSERT]], <2 x i64> poison, <2 x i32> zeroinitializer
; CHECK-NEXT:    [[INVARIANT_OP:%.*]] = add <2 x i64> [[DOTSPLAT]], [[DOTSPLAT]]
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[VEC_IND:%.*]] = phi <2 x i64> [ [[VEC_INIT]], [[ENTRY:%.*]] ], [ [[VEC_IND_NEXT_REASS:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[STEP_ADD:%.*]] = add <2 x i64> [[VEC_IND]], [[DOTSPLAT]]
; CHECK-NEXT:    call void @use(<2 x i64> [[STEP_ADD]])
; CHECK-NEXT:    [[VEC_IND_NEXT_REASS]] = add <2 x i64> [[VEC_IND]], [[INVARIANT_OP]]
; CHECK-NEXT:    br label [[LOOP]]
;
entry:
  %k.2 = shl nuw nsw i64 %k, 1
  %vec.init = insertelement <2 x i64> zeroinitializer, i64 %k, i64 1
  %.splatinsert = insertelement <2 x i64> poison, i64 %k.2, i64 0
  %.splat = shufflevector <2 x i64> %.splatinsert, <2 x i64> poison, <2 x i32> zeroinitializer
  br label %loop

loop:
  %vec.ind = phi <2 x i64> [ %vec.init, %entry ], [ %vec.ind.next, %loop ]
  %step.add = add <2 x i64> %vec.ind, %.splat
  call void @use(<2 x i64> %step.add)
  %vec.ind.next = add <2 x i64> %step.add, %.splat
  br label %loop
}

declare void @use()
llvm/llvm/test/Transforms/LICM/hoist-binop.ll
