llvm/test/Transforms/Reassociate/local-cse.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
   2 ; Check that the default heuristic use the local cse constraints.
   3 ; RUN: opt -S -passes=reassociate,early-cse %s -o - | FileCheck %s -check-prefix=LOCAL_CSE
   4 ; RUN: opt -S -passes=reassociate,early-cse %s -reassociate-use-cse-local=true -o - | FileCheck %s -check-prefix=LOCAL_CSE
   5 ; RUN: opt -S -passes=reassociate,early-cse %s -reassociate-use-cse-local=false -o - | FileCheck %s -check-prefix=CSE
   6
   7
   8 ; Check that when we use the heuristic to expose only local (to the first
   9 ; encountered block) CSE opportunities, we choose the right sub expression
  10 ; to expose.
  11 ;
  12 ; In these example we have three chains of expressions:
  13 ; chain a: inv1, val_bb2, inv2, inv4
  14 ; chain b: inv1, val_bb2, inv2, inv5
  15 ; chain c: inv1, val_bb2, inv3
  16 ;
  17 ; The CSE-able pairs with there respective occurrences are:
  18 ; inv1, val_bb2: 3
  19 ; inv1, inv2: 2
  20 ;
  21 ; val_bb2 is anchored in bb2 but inv1 and inv2 can start in bb1.
  22 ; With the local heuristic we will push inv1, inv2 at the beginning
  23 ; of chain_a and chain_b.
  24 ; With the non-local heuristic we will push inv1, val_bb2.
  25 define void @chain_spanning_several_blocks(i64 %inv1, i64 %inv2, i64 %inv3, i64 %inv4, i64 %inv5) {
  26 ; LOCAL_CSE-LABEL: define void @chain_spanning_several_blocks
  27 ; LOCAL_CSE-SAME: (i64 [[INV1:%.*]], i64 [[INV2:%.*]], i64 [[INV3:%.*]], i64 [[INV4:%.*]], i64 [[INV5:%.*]]) {
  28 ; LOCAL_CSE-NEXT:  bb1:
  29 ; LOCAL_CSE-NEXT:    [[CHAIN_A0:%.*]] = add i64 [[INV2]], [[INV1]]
  30 ; LOCAL_CSE-NEXT:    br label [[BB2:%.*]]
  31 ; LOCAL_CSE:       bb2:
  32 ; LOCAL_CSE-NEXT:    [[VAL_BB2:%.*]] = call i64 @get_val()
  33 ; LOCAL_CSE-NEXT:    [[CHAIN_A1:%.*]] = add i64 [[CHAIN_A0]], [[INV4]]
  34 ; LOCAL_CSE-NEXT:    [[CHAIN_A2:%.*]] = add i64 [[CHAIN_A1]], [[VAL_BB2]]
  35 ; LOCAL_CSE-NEXT:    [[CHAIN_B1:%.*]] = add i64 [[CHAIN_A0]], [[INV5]]
  36 ; LOCAL_CSE-NEXT:    [[CHAIN_B2:%.*]] = add i64 [[CHAIN_B1]], [[VAL_BB2]]
  37 ; LOCAL_CSE-NEXT:    [[CHAIN_C0:%.*]] = add i64 [[INV3]], [[INV1]]
  38 ; LOCAL_CSE-NEXT:    [[CHAIN_C1:%.*]] = add i64 [[CHAIN_C0]], [[VAL_BB2]]
  39 ; LOCAL_CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_A2]])
  40 ; LOCAL_CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_B2]])
  41 ; LOCAL_CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_C1]])
  42 ; LOCAL_CSE-NEXT:    ret void
  43 ;
  44 ; CSE-LABEL: define void @chain_spanning_several_blocks
  45 ; CSE-SAME: (i64 [[INV1:%.*]], i64 [[INV2:%.*]], i64 [[INV3:%.*]], i64 [[INV4:%.*]], i64 [[INV5:%.*]]) {
  46 ; CSE-NEXT:  bb1:
  47 ; CSE-NEXT:    br label [[BB2:%.*]]
  48 ; CSE:       bb2:
  49 ; CSE-NEXT:    [[VAL_BB2:%.*]] = call i64 @get_val()
  50 ; CSE-NEXT:    [[CHAIN_A0:%.*]] = add i64 [[VAL_BB2]], [[INV1]]
  51 ; CSE-NEXT:    [[CHAIN_A1:%.*]] = add i64 [[CHAIN_A0]], [[INV2]]
  52 ; CSE-NEXT:    [[CHAIN_A2:%.*]] = add nuw nsw i64 [[CHAIN_A1]], [[INV4]]
  53 ; CSE-NEXT:    [[CHAIN_B2:%.*]] = add nuw nsw i64 [[CHAIN_A1]], [[INV5]]
  54 ; CSE-NEXT:    [[CHAIN_C1:%.*]] = add i64 [[CHAIN_A0]], [[INV3]]
  55 ; CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_A2]])
  56 ; CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_B2]])
  57 ; CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_C1]])
  58 ; CSE-NEXT:    ret void
  59 ;
  60 bb1:
  61   %chain_a0 = add nuw nsw i64 %inv1, %inv2
  62   br label %bb2
  63
  64 bb2:
  65   %val_bb2 = call i64 @get_val()
  66   %chain_a1 = add nuw nsw i64 %chain_a0, %val_bb2
  67   %chain_a2 = add nuw nsw i64 %chain_a1, %inv4
  68   %chain_b0 = add nuw nsw i64 %val_bb2, %inv1
  69   %chain_b1 = add nuw nsw i64 %chain_b0, %inv2
  70   %chain_b2 = add nuw nsw i64 %chain_b1, %inv5
  71   %chain_c0 = add nuw nsw i64 %val_bb2, %inv3
  72   %chain_c1 = add nuw nsw i64 %chain_c0, %inv1
  73   call void @keep_alive(i64 %chain_a2)
  74   call void @keep_alive(i64 %chain_b2)
  75   call void @keep_alive(i64 %chain_c1)
  76   ret void
  77 }
  78
  79 ; Same as @chain_spanning_several_blocks, but with values that are all anchored
  80 ; on the non-entry block.
  81 ; I.e., same pair map as previous but with invX_bbY instead of invX.
  82 ; Note: Although %inv1_bb0 is anchored in the entry block, it doesn't constrain
  83 ; the sub expressions on the entry block because we need to see at least two
  84 ; values to be able to form a sub-expression and thus only the second one
  85 ; add a constraint.
  86 define void @chain_spanning_several_blocks_no_entry_anchor() {
  87 ; LOCAL_CSE-LABEL: define void @chain_spanning_several_blocks_no_entry_anchor() {
  88 ; LOCAL_CSE-NEXT:  bb0:
  89 ; LOCAL_CSE-NEXT:    [[INV2_BB0:%.*]] = call i64 @get_val()
  90 ; LOCAL_CSE-NEXT:    br label [[BB1:%.*]]
  91 ; LOCAL_CSE:       bb1:
  92 ; LOCAL_CSE-NEXT:    [[INV1_BB1:%.*]] = call i64 @get_val()
  93 ; LOCAL_CSE-NEXT:    [[CHAIN_A0:%.*]] = add i64 [[INV1_BB1]], [[INV2_BB0]]
  94 ; LOCAL_CSE-NEXT:    br label [[BB2:%.*]]
  95 ; LOCAL_CSE:       bb2:
  96 ; LOCAL_CSE-NEXT:    [[INV3_BB2:%.*]] = call i64 @get_val()
  97 ; LOCAL_CSE-NEXT:    [[INV4_BB2:%.*]] = call i64 @get_val()
  98 ; LOCAL_CSE-NEXT:    [[INV5_BB2:%.*]] = call i64 @get_val()
  99 ; LOCAL_CSE-NEXT:    [[VAL_BB2:%.*]] = call i64 @get_val()
 100 ; LOCAL_CSE-NEXT:    [[CHAIN_A1:%.*]] = add i64 [[CHAIN_A0]], [[INV4_BB2]]
 101 ; LOCAL_CSE-NEXT:    [[CHAIN_A2:%.*]] = add i64 [[CHAIN_A1]], [[VAL_BB2]]
 102 ; LOCAL_CSE-NEXT:    [[CHAIN_B1:%.*]] = add i64 [[CHAIN_A0]], [[INV5_BB2]]
 103 ; LOCAL_CSE-NEXT:    [[CHAIN_B2:%.*]] = add i64 [[CHAIN_B1]], [[VAL_BB2]]
 104 ; LOCAL_CSE-NEXT:    [[CHAIN_C0:%.*]] = add i64 [[VAL_BB2]], [[INV1_BB1]]
 105 ; LOCAL_CSE-NEXT:    [[CHAIN_C1:%.*]] = add i64 [[CHAIN_C0]], [[INV3_BB2]]
 106 ; LOCAL_CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_A2]])
 107 ; LOCAL_CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_B2]])
 108 ; LOCAL_CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_C1]])
 109 ; LOCAL_CSE-NEXT:    ret void
 110 ;
 111 ; CSE-LABEL: define void @chain_spanning_several_blocks_no_entry_anchor() {
 112 ; CSE-NEXT:  bb0:
 113 ; CSE-NEXT:    [[INV2_BB0:%.*]] = call i64 @get_val()
 114 ; CSE-NEXT:    br label [[BB1:%.*]]
 115 ; CSE:       bb1:
 116 ; CSE-NEXT:    [[INV1_BB1:%.*]] = call i64 @get_val()
 117 ; CSE-NEXT:    br label [[BB2:%.*]]
 118 ; CSE:       bb2:
 119 ; CSE-NEXT:    [[INV3_BB2:%.*]] = call i64 @get_val()
 120 ; CSE-NEXT:    [[INV4_BB2:%.*]] = call i64 @get_val()
 121 ; CSE-NEXT:    [[INV5_BB2:%.*]] = call i64 @get_val()
 122 ; CSE-NEXT:    [[VAL_BB2:%.*]] = call i64 @get_val()
 123 ; CSE-NEXT:    [[CHAIN_A0:%.*]] = add i64 [[VAL_BB2]], [[INV1_BB1]]
 124 ; CSE-NEXT:    [[CHAIN_A1:%.*]] = add i64 [[CHAIN_A0]], [[INV2_BB0]]
 125 ; CSE-NEXT:    [[CHAIN_A2:%.*]] = add nuw nsw i64 [[CHAIN_A1]], [[INV4_BB2]]
 126 ; CSE-NEXT:    [[CHAIN_B2:%.*]] = add nuw nsw i64 [[CHAIN_A1]], [[INV5_BB2]]
 127 ; CSE-NEXT:    [[CHAIN_C1:%.*]] = add i64 [[CHAIN_A0]], [[INV3_BB2]]
 128 ; CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_A2]])
 129 ; CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_B2]])
 130 ; CSE-NEXT:    call void @keep_alive(i64 [[CHAIN_C1]])
 131 ; CSE-NEXT:    ret void
 132 ;
 133 bb0:
 134   %inv2_bb0 = call i64 @get_val()
 135   br label %bb1
 136
 137 bb1:
 138   %inv1_bb1 = call i64 @get_val()
 139   %chain_a0 = add nuw nsw i64 %inv1_bb1, %inv2_bb0
 140   br label %bb2
 141
 142 bb2:
 143   %inv3_bb2 = call i64 @get_val()
 144   %inv4_bb2 = call i64 @get_val()
 145   %inv5_bb2 = call i64 @get_val()
 146   %val_bb2 = call i64 @get_val()
 147   %chain_a1 = add nuw nsw i64 %chain_a0, %val_bb2
 148   %chain_a2 = add nuw nsw i64 %chain_a1, %inv4_bb2
 149   %chain_b0 = add nuw nsw i64 %val_bb2, %inv1_bb1
 150   %chain_b1 = add nuw nsw i64 %chain_b0, %inv2_bb0
 151   %chain_b2 = add nuw nsw i64 %chain_b1, %inv5_bb2
 152   %chain_c0 = add nuw nsw i64 %val_bb2, %inv3_bb2
 153   %chain_c1 = add nuw nsw i64 %chain_c0, %inv1_bb1
 154   call void @keep_alive(i64 %chain_a2)
 155   call void @keep_alive(i64 %chain_b2)
 156   call void @keep_alive(i64 %chain_c1)
 157   ret void
 158 }
 159 declare i64 @get_val()
 160 declare void @keep_alive(i64)