;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
;; NOTE: This test was ported using port_passes_tests_to_lit.py and could be cleaned up.

;; RUN: foreach %s %t wasm-opt --local-cse -S -o - | filecheck %s

(module
  (memory 100 100)
  ;; CHECK:      (type $0 (func))

  ;; CHECK:      (type $1 (func (param i32) (result i32)))

  ;; CHECK:      (type $2 (func (result i64)))

  ;; CHECK:      (memory $0 100 100)

  ;; CHECK:      (func $basics
  ;; CHECK-NEXT:  (local $x i32)
  ;; CHECK-NEXT:  (local $y i32)
  ;; CHECK-NEXT:  (local $2 i32)
  ;; CHECK-NEXT:  (local $3 i32)
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (local.tee $2
  ;; CHECK-NEXT:    (i32.add
  ;; CHECK-NEXT:     (i32.const 1)
  ;; CHECK-NEXT:     (i32.const 2)
  ;; CHECK-NEXT:    )
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (local.get $2)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (if
  ;; CHECK-NEXT:   (i32.const 0)
  ;; CHECK-NEXT:   (then
  ;; CHECK-NEXT:    (nop)
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (i32.add
  ;; CHECK-NEXT:    (i32.const 1)
  ;; CHECK-NEXT:    (i32.const 2)
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (local.tee $3
  ;; CHECK-NEXT:    (i32.add
  ;; CHECK-NEXT:     (local.get $x)
  ;; CHECK-NEXT:     (local.get $y)
  ;; CHECK-NEXT:    )
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (local.get $3)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (local.get $3)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (call $basics)
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (local.get $3)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (local.set $x
  ;; CHECK-NEXT:   (i32.const 100)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (i32.add
  ;; CHECK-NEXT:    (local.get $x)
  ;; CHECK-NEXT:    (local.get $y)
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
  (func $basics
    (local $x i32)
    (local $y i32)
    ;; These two adds can be optimized.
    (drop
      (i32.add (i32.const 1) (i32.const 2))
    )
    (drop
      (i32.add (i32.const 1) (i32.const 2))
    )
    (if (i32.const 0) (then (nop)))
    ;; This add is after an if, which means we are no longer in the same basic
    ;; block - which means we cannot optimize it with the previous identical
    ;; adds.
    (drop
      (i32.add (i32.const 1) (i32.const 2))
    )
    ;; More adds with different contents than the previous, but all three are
    ;; identical.
    (drop
      (i32.add (local.get $x) (local.get $y))
    )
    (drop
      (i32.add (local.get $x) (local.get $y))
    )
    (drop
      (i32.add (local.get $x) (local.get $y))
    )
    ;; Calls have side effects, but that is not a problem for these adds which
    ;; only use locals, so we can optimize the add after the call.
    (call $basics)
    (drop
      (i32.add (local.get $x) (local.get $y))
    )
    ;; Modify $x, which means we cannot optimize the add after the set.
    (local.set $x (i32.const 100))
    (drop
      (i32.add (local.get $x) (local.get $y))
    )
  )

  ;; CHECK:      (func $recursive1
  ;; CHECK-NEXT:  (local $x i32)
  ;; CHECK-NEXT:  (local $y i32)
  ;; CHECK-NEXT:  (local $2 i32)
  ;; CHECK-NEXT:  (local $3 i32)
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (local.tee $3
  ;; CHECK-NEXT:    (i32.add
  ;; CHECK-NEXT:     (i32.const 1)
  ;; CHECK-NEXT:     (local.tee $2
  ;; CHECK-NEXT:      (i32.add
  ;; CHECK-NEXT:       (i32.const 2)
  ;; CHECK-NEXT:       (i32.const 3)
  ;; CHECK-NEXT:      )
  ;; CHECK-NEXT:     )
  ;; CHECK-NEXT:    )
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (local.get $3)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (local.get $2)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
  (func $recursive1
    (local $x i32)
    (local $y i32)
    ;; The first two dropped things are identical and can be optimized.
    (drop
      (i32.add
        (i32.const 1)
        (i32.add
          (i32.const 2)
          (i32.const 3)
        )
      )
    )
    (drop
      (i32.add
        (i32.const 1)
        (i32.add
          (i32.const 2)
          (i32.const 3)
        )
      )
    )
    ;; The last thing here appears inside the previous pattern, and can still
    ;; be optimized, with another local.
    (drop
      (i32.add
        (i32.const 2)
        (i32.const 3)
      )
    )
  )

  ;; CHECK:      (func $recursive2
  ;; CHECK-NEXT:  (local $x i32)
  ;; CHECK-NEXT:  (local $y i32)
  ;; CHECK-NEXT:  (local $2 i32)
  ;; CHECK-NEXT:  (local $3 i32)
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (local.tee $3
  ;; CHECK-NEXT:    (i32.add
  ;; CHECK-NEXT:     (i32.const 1)
  ;; CHECK-NEXT:     (local.tee $2
  ;; CHECK-NEXT:      (i32.add
  ;; CHECK-NEXT:       (i32.const 2)
  ;; CHECK-NEXT:       (i32.const 3)
  ;; CHECK-NEXT:      )
  ;; CHECK-NEXT:     )
  ;; CHECK-NEXT:    )
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (local.get $2)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (local.get $3)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
  (func $recursive2
    (local $x i32)
    (local $y i32)
    ;; As before, but the order is different, with the sub-pattern in the
    ;; middle.
    (drop
      (i32.add
        (i32.const 1)
        (i32.add
          (i32.const 2)
          (i32.const 3)
        )
      )
    )
    (drop
      (i32.add
        (i32.const 2)
        (i32.const 3)
      )
    )
    (drop
      (i32.add
        (i32.const 1)
        (i32.add
          (i32.const 2)
          (i32.const 3)
        )
      )
    )
  )

  ;; CHECK:      (func $self
  ;; CHECK-NEXT:  (local $x i32)
  ;; CHECK-NEXT:  (local $y i32)
  ;; CHECK-NEXT:  (local $2 i32)
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (i32.add
  ;; CHECK-NEXT:    (local.tee $2
  ;; CHECK-NEXT:     (i32.add
  ;; CHECK-NEXT:      (i32.const 2)
  ;; CHECK-NEXT:      (i32.const 3)
  ;; CHECK-NEXT:     )
  ;; CHECK-NEXT:    )
  ;; CHECK-NEXT:    (local.get $2)
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (local.get $2)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
  (func $self
    (local $x i32)
    (local $y i32)
    ;; As before, with just the large pattern and the sub pattern, but no
    ;; repeats of the large pattern.
    (drop
      (i32.add
        (i32.add
          (i32.const 2)
          (i32.const 3)
        )
        (i32.add
          (i32.const 2)
          (i32.const 3)
        )
      )
    )
    (drop
      (i32.add
        (i32.const 2)
        (i32.const 3)
      )
    )
  )

  ;; CHECK:      (func $loads
  ;; CHECK-NEXT:  (local $0 i32)
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (local.tee $0
  ;; CHECK-NEXT:    (i32.load
  ;; CHECK-NEXT:     (i32.const 10)
  ;; CHECK-NEXT:    )
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (local.get $0)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
  (func $loads
    ;; The possible trap on loads does not prevent optimization, since if we
    ;; trap then it doesn't matter that we replaced the later expression.
    (drop
      (i32.load (i32.const 10))
    )
    (drop
      (i32.load (i32.const 10))
    )
  )

  ;; CHECK:      (func $calls (param $x i32) (result i32)
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (call $calls
  ;; CHECK-NEXT:    (i32.const 10)
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (call $calls
  ;; CHECK-NEXT:    (i32.const 10)
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (i32.const 10)
  ;; CHECK-NEXT: )
  (func $calls (param $x i32) (result i32)
    ;; The side effects of calls prevent optimization.
    (drop
      (call $calls (i32.const 10))
    )
    (drop
      (call $calls (i32.const 10))
    )
    (i32.const 10)
  )

  ;; CHECK:      (func $many-sets (result i64)
  ;; CHECK-NEXT:  (local $temp i64)
  ;; CHECK-NEXT:  (local $1 i64)
  ;; CHECK-NEXT:  (local.set $temp
  ;; CHECK-NEXT:   (local.tee $1
  ;; CHECK-NEXT:    (i64.add
  ;; CHECK-NEXT:     (i64.const 1)
  ;; CHECK-NEXT:     (i64.const 2)
  ;; CHECK-NEXT:    )
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (local.set $temp
  ;; CHECK-NEXT:   (i64.const 9999)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (local.set $temp
  ;; CHECK-NEXT:   (local.get $1)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (local.get $temp)
  ;; CHECK-NEXT: )
  (func $many-sets (result i64)
    (local $temp i64)
    ;; Assign to $temp three times here. We can optimize the add regardless of
    ;; that, and should not be confused by the sets themselves having effects
    ;; that are in conflict (the value is what matters).
    (local.set $temp
      (i64.add
        (i64.const 1)
        (i64.const 2)
      )
    )
    (local.set $temp
      (i64.const 9999)
    )
    (local.set $temp
      (i64.add
        (i64.const 1)
        (i64.const 2)
      )
    )
    (local.get $temp)
  )

  ;; CHECK:      (func $switch-children (param $x i32) (result i32)
  ;; CHECK-NEXT:  (local $1 i32)
  ;; CHECK-NEXT:  (block $label$1 (result i32)
  ;; CHECK-NEXT:   (br_table $label$1 $label$1
  ;; CHECK-NEXT:    (local.tee $1
  ;; CHECK-NEXT:     (i32.and
  ;; CHECK-NEXT:      (local.get $x)
  ;; CHECK-NEXT:      (i32.const 3)
  ;; CHECK-NEXT:     )
  ;; CHECK-NEXT:    )
  ;; CHECK-NEXT:    (local.get $1)
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
  (func $switch-children (param $x i32) (result i32)
    (block $label$1 (result i32)
      ;; We can optimize the two children of this switch. This test verifies
      ;; that we do so properly and do not hit an assertion involving the
      ;; ordering of the switch's children, which was incorrect in the past.
      (br_table $label$1 $label$1
        (i32.and
          (local.get $x)
          (i32.const 3)
        )
        (i32.and
          (local.get $x)
          (i32.const 3)
        )
      )
    )
  )

  ;; CHECK:      (func $dominance
  ;; CHECK-NEXT:  (local $0 i32)
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (local.tee $0
  ;; CHECK-NEXT:    (i32.add
  ;; CHECK-NEXT:     (i32.const 2)
  ;; CHECK-NEXT:     (i32.const 3)
  ;; CHECK-NEXT:    )
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (if
  ;; CHECK-NEXT:   (i32.const 0)
  ;; CHECK-NEXT:   (then
  ;; CHECK-NEXT:    (drop
  ;; CHECK-NEXT:     (local.get $0)
  ;; CHECK-NEXT:    )
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:   (else
  ;; CHECK-NEXT:    (drop
  ;; CHECK-NEXT:     (i32.add
  ;; CHECK-NEXT:      (i32.const 2)
  ;; CHECK-NEXT:      (i32.const 3)
  ;; CHECK-NEXT:     )
  ;; CHECK-NEXT:    )
  ;; CHECK-NEXT:   )
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
  (func $dominance
    (drop
      (i32.add
        (i32.const 2)
        (i32.const 3)
      )
    )
    (if
      (i32.const 0)
      ;; This add is dominated by the above, so we can use a tee of it.
      (then
        (drop
          (i32.add
            (i32.const 2)
            (i32.const 3)
          )
        )
      )
      ;; We could optimize this add as well, but do not yet. TODO
      (else
        (drop
          (i32.add
            (i32.const 2)
            (i32.const 3)
          )
        )
      )
    )
  )
)

(module
  ;; CHECK:      (type $0 (func))

  ;; CHECK:      (global $glob (mut i32) (i32.const 1))
  (global $glob (mut i32) (i32.const 1))

  ;; CHECK:      (global $other-glob (mut i32) (i32.const 1))
  (global $other-glob (mut i32) (i32.const 1))

  ;; CHECK:      (func $global
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (global.get $glob)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (global.get $glob)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (global.set $other-glob
  ;; CHECK-NEXT:   (i32.const 100)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (global.get $glob)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (global.set $glob
  ;; CHECK-NEXT:   (i32.const 200)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT:  (drop
  ;; CHECK-NEXT:   (global.get $glob)
  ;; CHECK-NEXT:  )
  ;; CHECK-NEXT: )
  (func $global
    ;; We should not optimize redundant global.get operations: they are of size
    ;; 1 (no children), and so we may end up increasing code size here for
    ;; unclear benefit. The benefit is unclear since VMs already do GVN/CSE
    ;; themselves, and so we focus on things of size 2 and above, where we
    ;; definitely reduce code size at least.
    (drop (global.get $glob))
    (drop (global.get $glob))
    ;; We can do it past a write to another global
    (global.set $other-glob (i32.const 100))
    (drop (global.get $glob))
    ;; But we can't do it past a write to our global.
    (global.set $glob (i32.const 200))
    (drop (global.get $glob))
  )
)