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. 25define 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 nuw nsw 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 nuw nsw i64 [[CHAIN_A0]], [[INV4]] 34; LOCAL_CSE-NEXT: [[CHAIN_A2:%.*]] = add nuw nsw i64 [[CHAIN_A1]], [[VAL_BB2]] 35; LOCAL_CSE-NEXT: [[CHAIN_B1:%.*]] = add nuw nsw i64 [[CHAIN_A0]], [[INV5]] 36; LOCAL_CSE-NEXT: [[CHAIN_B2:%.*]] = add nuw nsw i64 [[CHAIN_B1]], [[VAL_BB2]] 37; LOCAL_CSE-NEXT: [[CHAIN_C0:%.*]] = add nuw nsw i64 [[INV3]], [[INV1]] 38; LOCAL_CSE-NEXT: [[CHAIN_C1:%.*]] = add nuw nsw 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 nuw nsw i64 [[VAL_BB2]], [[INV1]] 51; CSE-NEXT: [[CHAIN_A1:%.*]] = add nuw nsw 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 nuw nsw 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; 60bb1: 61 %chain_a0 = add nuw nsw i64 %inv1, %inv2 62 br label %bb2 63 64bb2: 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. 86define 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 nuw nsw 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 nuw nsw i64 [[CHAIN_A0]], [[INV4_BB2]] 101; LOCAL_CSE-NEXT: [[CHAIN_A2:%.*]] = add nuw nsw i64 [[CHAIN_A1]], [[VAL_BB2]] 102; LOCAL_CSE-NEXT: [[CHAIN_B1:%.*]] = add nuw nsw i64 [[CHAIN_A0]], [[INV5_BB2]] 103; LOCAL_CSE-NEXT: [[CHAIN_B2:%.*]] = add nuw nsw i64 [[CHAIN_B1]], [[VAL_BB2]] 104; LOCAL_CSE-NEXT: [[CHAIN_C0:%.*]] = add nuw nsw i64 [[VAL_BB2]], [[INV1_BB1]] 105; LOCAL_CSE-NEXT: [[CHAIN_C1:%.*]] = add nuw nsw 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 nuw nsw i64 [[VAL_BB2]], [[INV1_BB1]] 124; CSE-NEXT: [[CHAIN_A1:%.*]] = add nuw nsw 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 nuw nsw 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; 133bb0: 134 %inv2_bb0 = call i64 @get_val() 135 br label %bb1 136 137bb1: 138 %inv1_bb1 = call i64 @get_val() 139 %chain_a0 = add nuw nsw i64 %inv1_bb1, %inv2_bb0 140 br label %bb2 141 142bb2: 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} 159declare i64 @get_val() 160declare void @keep_alive(i64) 161