1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 3 2; PR41445: This test checks the case when LSR split critical edge 3; and phi node has other pending fixup operands 4 5; RUN: opt -S -loop-reduce < %s | FileCheck %s 6 7target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" 8target triple = "x86_64-unknown-linux-gnu" 9 10; We have %indvars.iv.lcssa phi node where 4 input operands 11; need to be rewritten: %tmp1, %tmp2, %tmp3, %tmp4. 12; When we try to rewrite %tmp1, we first split the critical edge. 13; All the other PHI inputs besides %tmp1 go to a new phi node. 14; This test checks that LSR is still able to rewrite %tmp2, %tmp3, %tmp4. 15define i32 @foo(ptr %A, i32 %t) { 16; CHECK-LABEL: define i32 @foo( 17; CHECK-SAME: ptr [[A:%.*]], i32 [[T:%.*]]) { 18; CHECK-NEXT: entry: 19; CHECK-NEXT: br label [[LOOP_32:%.*]] 20; CHECK: loop.exit.loopexitsplitsplitsplit: 21; CHECK-NEXT: [[LSR_IV:%.*]] = phi i64 [ [[LSR_IV1:%.*]], [[IFMERGE_34:%.*]] ] 22; CHECK-NEXT: [[TMP0:%.*]] = add i64 [[LSR_IV]], -1 23; CHECK-NEXT: br label [[LOOP_EXIT_LOOPEXITSPLITSPLIT:%.*]] 24; CHECK: ifmerge.38.loop.exit.loopexitsplitsplit_crit_edge: 25; CHECK-NEXT: [[LSR_IV_LCSSA10:%.*]] = phi i64 [ [[LSR_IV1]], [[IFMERGE_38:%.*]] ] 26; CHECK-NEXT: br label [[LOOP_EXIT_LOOPEXITSPLITSPLIT]] 27; CHECK: loop.exit.loopexitsplitsplit: 28; CHECK-NEXT: [[INDVARS_IV_LCSSA_PH_PH_PH:%.*]] = phi i64 [ [[LSR_IV_LCSSA10]], [[IFMERGE_38_LOOP_EXIT_LOOPEXITSPLITSPLIT_CRIT_EDGE:%.*]] ], [ [[TMP0]], [[LOOP_EXIT_LOOPEXITSPLITSPLITSPLIT:%.*]] ] 29; CHECK-NEXT: br label [[LOOP_EXIT_LOOPEXITSPLIT:%.*]] 30; CHECK: ifmerge.42.loop.exit.loopexitsplit_crit_edge: 31; CHECK-NEXT: [[LSR_IV_LCSSA11:%.*]] = phi i64 [ [[LSR_IV1]], [[IFMERGE_42:%.*]] ] 32; CHECK-NEXT: [[TMP1:%.*]] = add i64 [[LSR_IV_LCSSA11]], 1 33; CHECK-NEXT: br label [[LOOP_EXIT_LOOPEXITSPLIT]] 34; CHECK: loop.exit.loopexitsplit: 35; CHECK-NEXT: [[INDVARS_IV_LCSSA_PH_PH:%.*]] = phi i64 [ [[TMP1]], [[IFMERGE_42_LOOP_EXIT_LOOPEXITSPLIT_CRIT_EDGE:%.*]] ], [ [[INDVARS_IV_LCSSA_PH_PH_PH]], [[LOOP_EXIT_LOOPEXITSPLITSPLIT]] ] 36; CHECK-NEXT: br label [[LOOP_EXIT_LOOPEXIT:%.*]] 37; CHECK: then.34.loop.exit.loopexit_crit_edge: 38; CHECK-NEXT: [[LSR_IV_LCSSA:%.*]] = phi i64 [ [[LSR_IV1]], [[THEN_34:%.*]] ] 39; CHECK-NEXT: [[TMP2:%.*]] = add i64 [[LSR_IV_LCSSA]], -2 40; CHECK-NEXT: br label [[LOOP_EXIT_LOOPEXIT]] 41; CHECK: loop.exit.loopexit: 42; CHECK-NEXT: [[INDVARS_IV_LCSSA_PH:%.*]] = phi i64 [ [[TMP2]], [[THEN_34_LOOP_EXIT_LOOPEXIT_CRIT_EDGE:%.*]] ], [ [[INDVARS_IV_LCSSA_PH_PH]], [[LOOP_EXIT_LOOPEXITSPLIT]] ] 43; CHECK-NEXT: br label [[LOOP_EXIT:%.*]] 44; CHECK: loop.exit: 45; CHECK-NEXT: [[INDVARS_IV_LCSSA:%.*]] = phi i64 [ 48, [[THEN_8:%.*]] ], [ 49, [[THEN_8_1:%.*]] ], [ [[INDVARS_IV_LCSSA_PH]], [[LOOP_EXIT_LOOPEXIT]] ] 46; CHECK-NEXT: [[TMP:%.*]] = trunc i64 [[INDVARS_IV_LCSSA]] to i32 47; CHECK-NEXT: br label [[FOR_END:%.*]] 48; CHECK: for.end: 49; CHECK-NEXT: [[I_0_LCSSA:%.*]] = phi i32 [ [[TMP]], [[LOOP_EXIT]] ], [ 50, [[THEN_8_1]] ], [ 50, [[IFMERGE_8:%.*]] ] 50; CHECK-NEXT: ret i32 [[I_0_LCSSA]] 51; CHECK: loop.32: 52; CHECK-NEXT: [[LSR_IV1]] = phi i64 [ [[LSR_IV_NEXT:%.*]], [[IFMERGE_46:%.*]] ], [ 2, [[ENTRY:%.*]] ] 53; CHECK-NEXT: [[I1_I64_0:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[NEXTIVLOOP_32:%.*]], [[IFMERGE_46]] ] 54; CHECK-NEXT: [[TMP3:%.*]] = shl nuw nsw i64 [[LSR_IV1]], 2 55; CHECK-NEXT: [[SCEVGEP7:%.*]] = getelementptr i8, ptr [[A]], i64 [[TMP3]] 56; CHECK-NEXT: [[SCEVGEP8:%.*]] = getelementptr i8, ptr [[SCEVGEP7]], i64 -4 57; CHECK-NEXT: [[GEPLOAD:%.*]] = load i32, ptr [[SCEVGEP8]], align 4 58; CHECK-NEXT: [[CMP_34:%.*]] = icmp sgt i32 [[GEPLOAD]], [[T]] 59; CHECK-NEXT: br i1 [[CMP_34]], label [[THEN_34]], label [[IFMERGE_34]] 60; CHECK: then.34: 61; CHECK-NEXT: [[TMP4:%.*]] = shl nuw nsw i64 [[LSR_IV1]], 2 62; CHECK-NEXT: [[SCEVGEP5:%.*]] = getelementptr i8, ptr [[A]], i64 [[TMP4]] 63; CHECK-NEXT: [[SCEVGEP6:%.*]] = getelementptr i8, ptr [[SCEVGEP5]], i64 -8 64; CHECK-NEXT: [[GEPLOAD18:%.*]] = load i32, ptr [[SCEVGEP6]], align 4 65; CHECK-NEXT: [[CMP_35:%.*]] = icmp slt i32 [[GEPLOAD18]], [[T]] 66; CHECK-NEXT: br i1 [[CMP_35]], label [[THEN_34_LOOP_EXIT_LOOPEXIT_CRIT_EDGE]], label [[IFMERGE_34]] 67; CHECK: ifmerge.34: 68; CHECK-NEXT: [[TMP5:%.*]] = shl nuw nsw i64 [[LSR_IV1]], 2 69; CHECK-NEXT: [[SCEVGEP4:%.*]] = getelementptr i8, ptr [[A]], i64 [[TMP5]] 70; CHECK-NEXT: [[GEPLOAD20:%.*]] = load i32, ptr [[SCEVGEP4]], align 4 71; CHECK-NEXT: [[CMP_38:%.*]] = icmp sgt i32 [[GEPLOAD20]], [[T]] 72; CHECK-NEXT: [[CMP_39:%.*]] = icmp slt i32 [[GEPLOAD]], [[T]] 73; CHECK-NEXT: [[OR_COND:%.*]] = and i1 [[CMP_38]], [[CMP_39]] 74; CHECK-NEXT: br i1 [[OR_COND]], label [[LOOP_EXIT_LOOPEXITSPLITSPLITSPLIT]], label [[IFMERGE_38]] 75; CHECK: ifmerge.38: 76; CHECK-NEXT: [[TMP6:%.*]] = shl nuw nsw i64 [[LSR_IV1]], 2 77; CHECK-NEXT: [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[A]], i64 [[TMP6]] 78; CHECK-NEXT: [[SCEVGEP3:%.*]] = getelementptr i8, ptr [[SCEVGEP2]], i64 4 79; CHECK-NEXT: [[GEPLOAD24:%.*]] = load i32, ptr [[SCEVGEP3]], align 4 80; CHECK-NEXT: [[CMP_42:%.*]] = icmp sgt i32 [[GEPLOAD24]], [[T]] 81; CHECK-NEXT: [[CMP_43:%.*]] = icmp slt i32 [[GEPLOAD20]], [[T]] 82; CHECK-NEXT: [[OR_COND55:%.*]] = and i1 [[CMP_42]], [[CMP_43]] 83; CHECK-NEXT: br i1 [[OR_COND55]], label [[IFMERGE_38_LOOP_EXIT_LOOPEXITSPLITSPLIT_CRIT_EDGE]], label [[IFMERGE_42]] 84; CHECK: ifmerge.42: 85; CHECK-NEXT: [[TMP7:%.*]] = shl nuw nsw i64 [[LSR_IV1]], 2 86; CHECK-NEXT: [[SCEVGEP:%.*]] = getelementptr i8, ptr [[A]], i64 [[TMP7]] 87; CHECK-NEXT: [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[SCEVGEP]], i64 8 88; CHECK-NEXT: [[GEPLOAD28:%.*]] = load i32, ptr [[SCEVGEP1]], align 4 89; CHECK-NEXT: [[CMP_46:%.*]] = icmp sgt i32 [[GEPLOAD28]], [[T]] 90; CHECK-NEXT: [[CMP_47:%.*]] = icmp slt i32 [[GEPLOAD24]], [[T]] 91; CHECK-NEXT: [[OR_COND56:%.*]] = and i1 [[CMP_46]], [[CMP_47]] 92; CHECK-NEXT: br i1 [[OR_COND56]], label [[IFMERGE_42_LOOP_EXIT_LOOPEXITSPLIT_CRIT_EDGE]], label [[IFMERGE_46]] 93; CHECK: ifmerge.46: 94; CHECK-NEXT: [[NEXTIVLOOP_32]] = add nuw nsw i64 [[I1_I64_0]], 1 95; CHECK-NEXT: [[LSR_IV_NEXT]] = add nuw nsw i64 [[LSR_IV1]], 4 96; CHECK-NEXT: [[CONDLOOP_32:%.*]] = icmp ult i64 [[NEXTIVLOOP_32]], 12 97; CHECK-NEXT: br i1 [[CONDLOOP_32]], label [[LOOP_32]], label [[LOOP_25:%.*]] 98; CHECK: loop.25: 99; CHECK-NEXT: [[ARRAYIDX31:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 49 100; CHECK-NEXT: [[GEPLOAD32:%.*]] = load i32, ptr [[ARRAYIDX31]], align 4 101; CHECK-NEXT: [[CMP_8:%.*]] = icmp sgt i32 [[GEPLOAD32]], [[T]] 102; CHECK-NEXT: br i1 [[CMP_8]], label [[THEN_8]], label [[IFMERGE_8]] 103; CHECK: then.8: 104; CHECK-NEXT: [[ARRAYIDX33:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 48 105; CHECK-NEXT: [[GEPLOAD34:%.*]] = load i32, ptr [[ARRAYIDX33]], align 4 106; CHECK-NEXT: [[CMP_15:%.*]] = icmp slt i32 [[GEPLOAD34]], [[T]] 107; CHECK-NEXT: br i1 [[CMP_15]], label [[LOOP_EXIT]], label [[IFMERGE_8]] 108; CHECK: ifmerge.8: 109; CHECK-NEXT: [[ARRAYIDX31_1:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 50 110; CHECK-NEXT: [[GEPLOAD32_1:%.*]] = load i32, ptr [[ARRAYIDX31_1]], align 4 111; CHECK-NEXT: [[CMP_8_1:%.*]] = icmp sgt i32 [[GEPLOAD32_1]], [[T]] 112; CHECK-NEXT: br i1 [[CMP_8_1]], label [[THEN_8_1]], label [[FOR_END]] 113; CHECK: then.8.1: 114; CHECK-NEXT: [[ARRAYIDX33_1:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 49 115; CHECK-NEXT: [[GEPLOAD34_1:%.*]] = load i32, ptr [[ARRAYIDX33_1]], align 4 116; CHECK-NEXT: [[CMP_15_1:%.*]] = icmp slt i32 [[GEPLOAD34_1]], [[T]] 117; CHECK-NEXT: br i1 [[CMP_15_1]], label [[LOOP_EXIT]], label [[FOR_END]] 118; 119entry: 120 br label %loop.32 121 122loop.exit: ; preds = %then.8.1, %then.8, %ifmerge.42, %ifmerge.38, %ifmerge.34, %then.34 123 %indvars.iv.lcssa = phi i64 [ 48, %then.8 ], [ 49, %then.8.1 ], [ %tmp4, %ifmerge.42 ], [ %tmp3, %ifmerge.38 ], [ %tmp2, %ifmerge.34 ], [ %tmp1, %then.34 ] 124 %tmp = trunc i64 %indvars.iv.lcssa to i32 125 br label %for.end 126 127for.end: ; preds = %then.8.1, %ifmerge.8, %loop.exit 128 %i.0.lcssa = phi i32 [ %tmp, %loop.exit ], [ 50, %then.8.1 ], [ 50, %ifmerge.8 ] 129 ret i32 %i.0.lcssa 130 131; shl instruction will be dead eliminated when all it's uses will be rewritten. 132loop.32: ; preds = %ifmerge.46, %entry 133 %i1.i64.0 = phi i64 [ 0, %entry ], [ %nextivloop.32, %ifmerge.46 ] 134 %tmp1 = shl i64 %i1.i64.0, 2 135 %tmp2 = or disjoint i64 %tmp1, 1 136 %arrayIdx = getelementptr inbounds i32, ptr %A, i64 %tmp2 137 %gepload = load i32, ptr %arrayIdx, align 4 138 %cmp.34 = icmp sgt i32 %gepload, %t 139 br i1 %cmp.34, label %then.34, label %ifmerge.34 140 141then.34: ; preds = %loop.32 142 %arrayIdx17 = getelementptr inbounds i32, ptr %A, i64 %tmp1 143 %gepload18 = load i32, ptr %arrayIdx17, align 4 144 %cmp.35 = icmp slt i32 %gepload18, %t 145 br i1 %cmp.35, label %loop.exit, label %ifmerge.34 146 147ifmerge.34: ; preds = %then.34, %loop.32 148 %tmp3 = or disjoint i64 %tmp1, 2 149 %arrayIdx19 = getelementptr inbounds i32, ptr %A, i64 %tmp3 150 %gepload20 = load i32, ptr %arrayIdx19, align 4 151 %cmp.38 = icmp sgt i32 %gepload20, %t 152 %cmp.39 = icmp slt i32 %gepload, %t 153 %or.cond = and i1 %cmp.38, %cmp.39 154 br i1 %or.cond, label %loop.exit, label %ifmerge.38 155 156ifmerge.38: ; preds = %ifmerge.34 157 %tmp4 = or disjoint i64 %tmp1, 3 158 %arrayIdx23 = getelementptr inbounds i32, ptr %A, i64 %tmp4 159 %gepload24 = load i32, ptr %arrayIdx23, align 4 160 %cmp.42 = icmp sgt i32 %gepload24, %t 161 %cmp.43 = icmp slt i32 %gepload20, %t 162 %or.cond55 = and i1 %cmp.42, %cmp.43 163 br i1 %or.cond55, label %loop.exit, label %ifmerge.42 164 165ifmerge.42: ; preds = %ifmerge.38 166 %tmp5 = add i64 %tmp1, 4 167 %arrayIdx27 = getelementptr inbounds i32, ptr %A, i64 %tmp5 168 %gepload28 = load i32, ptr %arrayIdx27, align 4 169 %cmp.46 = icmp sgt i32 %gepload28, %t 170 %cmp.47 = icmp slt i32 %gepload24, %t 171 %or.cond56 = and i1 %cmp.46, %cmp.47 172 br i1 %or.cond56, label %loop.exit, label %ifmerge.46 173 174ifmerge.46: ; preds = %ifmerge.42 175 %nextivloop.32 = add nuw nsw i64 %i1.i64.0, 1 176 %condloop.32 = icmp ult i64 %nextivloop.32, 12 177 br i1 %condloop.32, label %loop.32, label %loop.25 178 179loop.25: ; preds = %ifmerge.46 180 %arrayIdx31 = getelementptr inbounds i32, ptr %A, i64 49 181 %gepload32 = load i32, ptr %arrayIdx31, align 4 182 %cmp.8 = icmp sgt i32 %gepload32, %t 183 br i1 %cmp.8, label %then.8, label %ifmerge.8 184 185then.8: ; preds = %loop.25 186 %arrayIdx33 = getelementptr inbounds i32, ptr %A, i64 48 187 %gepload34 = load i32, ptr %arrayIdx33, align 4 188 %cmp.15 = icmp slt i32 %gepload34, %t 189 br i1 %cmp.15, label %loop.exit, label %ifmerge.8 190 191ifmerge.8: ; preds = %then.8, %loop.25 192 %arrayIdx31.1 = getelementptr inbounds i32, ptr %A, i64 50 193 %gepload32.1 = load i32, ptr %arrayIdx31.1, align 4 194 %cmp.8.1 = icmp sgt i32 %gepload32.1, %t 195 br i1 %cmp.8.1, label %then.8.1, label %for.end 196 197then.8.1: ; preds = %ifmerge.8 198 %arrayIdx33.1 = getelementptr inbounds i32, ptr %A, i64 49 199 %gepload34.1 = load i32, ptr %arrayIdx33.1, align 4 200 %cmp.15.1 = icmp slt i32 %gepload34.1, %t 201 br i1 %cmp.15.1, label %loop.exit, label %for.end 202} 203