xref: /llvm-project/llvm/test/Transforms/Reassociate/local-cse.ll (revision 73e22ff3d77db72bb9b6e22342417a5f4fe6afb4)

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
; Check that the default heuristic use the local cse constraints.
; RUN: opt -S -passes=reassociate,early-cse %s -o - | FileCheck %s -check-prefix=LOCAL_CSE
; RUN: opt -S -passes=reassociate,early-cse %s -reassociate-use-cse-local=true -o - | FileCheck %s -check-prefix=LOCAL_CSE
; RUN: opt -S -passes=reassociate,early-cse %s -reassociate-use-cse-local=false -o - | FileCheck %s -check-prefix=CSE


; Check that when we use the heuristic to expose only local (to the first
; encountered block) CSE opportunities, we choose the right sub expression
; to expose.
;
; In these example we have three chains of expressions:
; chain a: inv1, val_bb2, inv2, inv4
; chain b: inv1, val_bb2, inv2, inv5
; chain c: inv1, val_bb2, inv3
;
; The CSE-able pairs with there respective occurrences are:
; inv1, val_bb2: 3
; inv1, inv2: 2
;
; val_bb2 is anchored in bb2 but inv1 and inv2 can start in bb1.
; With the local heuristic we will push inv1, inv2 at the beginning
; of chain_a and chain_b.
; With the non-local heuristic we will push inv1, val_bb2.
define void @chain_spanning_several_blocks(i64 %inv1, i64 %inv2, i64 %inv3, i64 %inv4, i64 %inv5) {
; LOCAL_CSE-LABEL: define void @chain_spanning_several_blocks
; LOCAL_CSE-SAME: (i64 [[INV1:%.*]], i64 [[INV2:%.*]], i64 [[INV3:%.*]], i64 [[INV4:%.*]], i64 [[INV5:%.*]]) {
; LOCAL_CSE-NEXT:  bb1:
; LOCAL_CSE-NEXT:    [[CHAIN_A0:%.*]] = add nuw nsw i64 [[INV2]], [[INV1]]
; LOCAL_CSE-NEXT:    br label [[BB2:%.*]]
; LOCAL_CSE:       bb2:
; LOCAL_CSE-NEXT:    [[VAL_BB2:%.*]] = call i64 @get_val()
; LOCAL_CSE-NEXT:    [[CHAIN_A1:%.*]] = add nuw nsw i64 [[CHAIN_A0]], [[INV4]]
; LOCAL_CSE-NEXT:    [[CHAIN_A2:%.*]] = add nuw nsw i64 [[CHAIN_A1]], [[VAL_BB2]]
; LOCAL_CSE-NEXT:    [[CHAIN_B1:%.*]] = add nuw nsw i64 [[CHAIN_A0]], [[INV5]]
; LOCAL_CSE-NEXT:    [[CHAIN_B2:%.*]] = add nuw nsw i64 [[CHAIN_B1]], [[VAL_BB2]]
; LOCAL_CSE-NEXT:    [[CHAIN_C0:%.*]] = add nuw nsw i64 [[INV3]], [[INV1]]
; LOCAL_CSE-NEXT:    [[CHAIN_C1:%.*]] = add nuw nsw i64 [[CHAIN_C0]], [[VAL_BB2]]
; LOCAL_CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_A2]])
; LOCAL_CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_B2]])
; LOCAL_CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_C1]])
; LOCAL_CSE-NEXT:    ret void
;
; CSE-LABEL: define void @chain_spanning_several_blocks
; CSE-SAME: (i64 [[INV1:%.*]], i64 [[INV2:%.*]], i64 [[INV3:%.*]], i64 [[INV4:%.*]], i64 [[INV5:%.*]]) {
; CSE-NEXT:  bb1:
; CSE-NEXT:    br label [[BB2:%.*]]
; CSE:       bb2:
; CSE-NEXT:    [[VAL_BB2:%.*]] = call i64 @get_val()
; CSE-NEXT:    [[CHAIN_A0:%.*]] = add nuw nsw i64 [[VAL_BB2]], [[INV1]]
; CSE-NEXT:    [[CHAIN_A1:%.*]] = add nuw nsw i64 [[CHAIN_A0]], [[INV2]]
; CSE-NEXT:    [[CHAIN_A2:%.*]] = add nuw nsw i64 [[CHAIN_A1]], [[INV4]]
; CSE-NEXT:    [[CHAIN_B2:%.*]] = add nuw nsw i64 [[CHAIN_A1]], [[INV5]]
; CSE-NEXT:    [[CHAIN_C1:%.*]] = add nuw nsw i64 [[CHAIN_A0]], [[INV3]]
; CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_A2]])
; CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_B2]])
; CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_C1]])
; CSE-NEXT:    ret void
;
bb1:
  %chain_a0 = add nuw nsw i64 %inv1, %inv2
  br label %bb2

bb2:
  %val_bb2 = call i64 @get_val()
  %chain_a1 = add nuw nsw i64 %chain_a0, %val_bb2
  %chain_a2 = add nuw nsw i64 %chain_a1, %inv4
  %chain_b0 = add nuw nsw i64 %val_bb2, %inv1
  %chain_b1 = add nuw nsw i64 %chain_b0, %inv2
  %chain_b2 = add nuw nsw i64 %chain_b1, %inv5
  %chain_c0 = add nuw nsw i64 %val_bb2, %inv3
  %chain_c1 = add nuw nsw i64 %chain_c0, %inv1
  call void @keep_alive(i64 %chain_a2)
  call void @keep_alive(i64 %chain_b2)
  call void @keep_alive(i64 %chain_c1)
  ret void
}

; Same as @chain_spanning_several_blocks, but with values that are all anchored
; on the non-entry block.
; I.e., same pair map as previous but with invX_bbY instead of invX.
; Note: Although %inv1_bb0 is anchored in the entry block, it doesn't constrain
; the sub expressions on the entry block because we need to see at least two
; values to be able to form a sub-expression and thus only the second one
; add a constraint.
define void @chain_spanning_several_blocks_no_entry_anchor() {
; LOCAL_CSE-LABEL: define void @chain_spanning_several_blocks_no_entry_anchor() {
; LOCAL_CSE-NEXT:  bb0:
; LOCAL_CSE-NEXT:    [[INV2_BB0:%.*]] = call i64 @get_val()
; LOCAL_CSE-NEXT:    br label [[BB1:%.*]]
; LOCAL_CSE:       bb1:
; LOCAL_CSE-NEXT:    [[INV1_BB1:%.*]] = call i64 @get_val()
; LOCAL_CSE-NEXT:    [[CHAIN_A0:%.*]] = add nuw nsw i64 [[INV1_BB1]], [[INV2_BB0]]
; LOCAL_CSE-NEXT:    br label [[BB2:%.*]]
; LOCAL_CSE:       bb2:
; LOCAL_CSE-NEXT:    [[INV3_BB2:%.*]] = call i64 @get_val()
; LOCAL_CSE-NEXT:    [[INV4_BB2:%.*]] = call i64 @get_val()
; LOCAL_CSE-NEXT:    [[INV5_BB2:%.*]] = call i64 @get_val()
; LOCAL_CSE-NEXT:    [[VAL_BB2:%.*]] = call i64 @get_val()
; LOCAL_CSE-NEXT:    [[CHAIN_A1:%.*]] = add nuw nsw i64 [[CHAIN_A0]], [[INV4_BB2]]
; LOCAL_CSE-NEXT:    [[CHAIN_A2:%.*]] = add nuw nsw i64 [[CHAIN_A1]], [[VAL_BB2]]
; LOCAL_CSE-NEXT:    [[CHAIN_B1:%.*]] = add nuw nsw i64 [[CHAIN_A0]], [[INV5_BB2]]
; LOCAL_CSE-NEXT:    [[CHAIN_B2:%.*]] = add nuw nsw i64 [[CHAIN_B1]], [[VAL_BB2]]
; LOCAL_CSE-NEXT:    [[CHAIN_C0:%.*]] = add nuw nsw i64 [[VAL_BB2]], [[INV1_BB1]]
; LOCAL_CSE-NEXT:    [[CHAIN_C1:%.*]] = add nuw nsw i64 [[CHAIN_C0]], [[INV3_BB2]]
; LOCAL_CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_A2]])
; LOCAL_CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_B2]])
; LOCAL_CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_C1]])
; LOCAL_CSE-NEXT:    ret void
;
; CSE-LABEL: define void @chain_spanning_several_blocks_no_entry_anchor() {
; CSE-NEXT:  bb0:
; CSE-NEXT:    [[INV2_BB0:%.*]] = call i64 @get_val()
; CSE-NEXT:    br label [[BB1:%.*]]
; CSE:       bb1:
; CSE-NEXT:    [[INV1_BB1:%.*]] = call i64 @get_val()
; CSE-NEXT:    br label [[BB2:%.*]]
; CSE:       bb2:
; CSE-NEXT:    [[INV3_BB2:%.*]] = call i64 @get_val()
; CSE-NEXT:    [[INV4_BB2:%.*]] = call i64 @get_val()
; CSE-NEXT:    [[INV5_BB2:%.*]] = call i64 @get_val()
; CSE-NEXT:    [[VAL_BB2:%.*]] = call i64 @get_val()
; CSE-NEXT:    [[CHAIN_A0:%.*]] = add nuw nsw i64 [[VAL_BB2]], [[INV1_BB1]]
; CSE-NEXT:    [[CHAIN_A1:%.*]] = add nuw nsw i64 [[CHAIN_A0]], [[INV2_BB0]]
; CSE-NEXT:    [[CHAIN_A2:%.*]] = add nuw nsw i64 [[CHAIN_A1]], [[INV4_BB2]]
; CSE-NEXT:    [[CHAIN_B2:%.*]] = add nuw nsw i64 [[CHAIN_A1]], [[INV5_BB2]]
; CSE-NEXT:    [[CHAIN_C1:%.*]] = add nuw nsw i64 [[CHAIN_A0]], [[INV3_BB2]]
; CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_A2]])
; CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_B2]])
; CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_C1]])
; CSE-NEXT:    ret void
;
bb0:
  %inv2_bb0 = call i64 @get_val()
  br label %bb1

bb1:
  %inv1_bb1 = call i64 @get_val()
  %chain_a0 = add nuw nsw i64 %inv1_bb1, %inv2_bb0
  br label %bb2

bb2:
  %inv3_bb2 = call i64 @get_val()
  %inv4_bb2 = call i64 @get_val()
  %inv5_bb2 = call i64 @get_val()
  %val_bb2 = call i64 @get_val()
  %chain_a1 = add nuw nsw i64 %chain_a0, %val_bb2
  %chain_a2 = add nuw nsw i64 %chain_a1, %inv4_bb2
  %chain_b0 = add nuw nsw i64 %val_bb2, %inv1_bb1
  %chain_b1 = add nuw nsw i64 %chain_b0, %inv2_bb0
  %chain_b2 = add nuw nsw i64 %chain_b1, %inv5_bb2
  %chain_c0 = add nuw nsw i64 %val_bb2, %inv3_bb2
  %chain_c1 = add nuw nsw i64 %chain_c0, %inv1_bb1
  call void @keep_alive(i64 %chain_a2)
  call void @keep_alive(i64 %chain_b2)
  call void @keep_alive(i64 %chain_c1)
  ret void
}
declare i64 @get_val()
declare void @keep_alive(i64)