1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt < %s -S -indvars -loop-unroll -verify-loop-info | FileCheck %s 3; 4; Unit tests for loop unrolling using ScalarEvolution to compute trip counts. 5; 6; Indvars is run first to generate an "old" SCEV result. Some unit 7; tests may check that SCEV is properly invalidated between passes. 8 9; Completely unroll loops without a canonical IV. 10define i32 @sansCanonical(i32* %base) nounwind { 11; CHECK-LABEL: @sansCanonical( 12; CHECK-NEXT: entry: 13; CHECK-NEXT: [[ZEXT:%.*]] = zext i32 0 to i64 14; CHECK-NEXT: br label [[WHILE_BODY:%.*]] 15; CHECK: while.body: 16; CHECK-NEXT: [[ADR:%.*]] = getelementptr inbounds i32, i32* [[BASE:%.*]], i64 9 17; CHECK-NEXT: [[TMP:%.*]] = load i32, i32* [[ADR]], align 8 18; CHECK-NEXT: [[ADR_1:%.*]] = getelementptr inbounds i32, i32* [[BASE]], i64 8 19; CHECK-NEXT: [[TMP_1:%.*]] = load i32, i32* [[ADR_1]], align 8 20; CHECK-NEXT: [[SUM_NEXT_1:%.*]] = add i32 [[TMP]], [[TMP_1]] 21; CHECK-NEXT: [[ADR_2:%.*]] = getelementptr inbounds i32, i32* [[BASE]], i64 7 22; CHECK-NEXT: [[TMP_2:%.*]] = load i32, i32* [[ADR_2]], align 8 23; CHECK-NEXT: [[SUM_NEXT_2:%.*]] = add i32 [[SUM_NEXT_1]], [[TMP_2]] 24; CHECK-NEXT: [[ADR_3:%.*]] = getelementptr inbounds i32, i32* [[BASE]], i64 6 25; CHECK-NEXT: [[TMP_3:%.*]] = load i32, i32* [[ADR_3]], align 8 26; CHECK-NEXT: [[SUM_NEXT_3:%.*]] = add i32 [[SUM_NEXT_2]], [[TMP_3]] 27; CHECK-NEXT: [[ADR_4:%.*]] = getelementptr inbounds i32, i32* [[BASE]], i64 5 28; CHECK-NEXT: [[TMP_4:%.*]] = load i32, i32* [[ADR_4]], align 8 29; CHECK-NEXT: [[SUM_NEXT_4:%.*]] = add i32 [[SUM_NEXT_3]], [[TMP_4]] 30; CHECK-NEXT: [[ADR_5:%.*]] = getelementptr inbounds i32, i32* [[BASE]], i64 4 31; CHECK-NEXT: [[TMP_5:%.*]] = load i32, i32* [[ADR_5]], align 8 32; CHECK-NEXT: [[SUM_NEXT_5:%.*]] = add i32 [[SUM_NEXT_4]], [[TMP_5]] 33; CHECK-NEXT: [[ADR_6:%.*]] = getelementptr inbounds i32, i32* [[BASE]], i64 3 34; CHECK-NEXT: [[TMP_6:%.*]] = load i32, i32* [[ADR_6]], align 8 35; CHECK-NEXT: [[SUM_NEXT_6:%.*]] = add i32 [[SUM_NEXT_5]], [[TMP_6]] 36; CHECK-NEXT: [[ADR_7:%.*]] = getelementptr inbounds i32, i32* [[BASE]], i64 2 37; CHECK-NEXT: [[TMP_7:%.*]] = load i32, i32* [[ADR_7]], align 8 38; CHECK-NEXT: [[SUM_NEXT_7:%.*]] = add i32 [[SUM_NEXT_6]], [[TMP_7]] 39; CHECK-NEXT: [[ADR_8:%.*]] = getelementptr inbounds i32, i32* [[BASE]], i64 1 40; CHECK-NEXT: [[TMP_8:%.*]] = load i32, i32* [[ADR_8]], align 8 41; CHECK-NEXT: [[SUM_NEXT_8:%.*]] = add i32 [[SUM_NEXT_7]], [[TMP_8]] 42; CHECK-NEXT: [[TMP_9:%.*]] = load i32, i32* [[BASE]], align 8 43; CHECK-NEXT: ret i32 [[SUM_NEXT_8]] 44; 45entry: 46 br label %while.body 47 48while.body: 49 %iv = phi i64 [ 10, %entry ], [ %iv.next, %while.body ] 50 %sum = phi i32 [ 0, %entry ], [ %sum.next, %while.body ] 51 %iv.next = add i64 %iv, -1 52 %adr = getelementptr inbounds i32, i32* %base, i64 %iv.next 53 %tmp = load i32, i32* %adr, align 8 54 %sum.next = add i32 %sum, %tmp 55 %iv.narrow = trunc i64 %iv.next to i32 56 %cmp.i65 = icmp sgt i32 %iv.narrow, 0 57 br i1 %cmp.i65, label %while.body, label %exit 58 59exit: 60 ret i32 %sum 61} 62 63; SCEV unrolling properly handles loops with multiple exits. In this 64; case, the computed trip count based on a canonical IV is *not* for a 65; latch block. Canonical unrolling incorrectly unrolls it, but SCEV 66; unrolling does not. 67define i64 @earlyLoopTest(i64* %base) nounwind { 68; CHECK-LABEL: @earlyLoopTest( 69; CHECK-NEXT: entry: 70; CHECK-NEXT: br label [[LOOP:%.*]] 71; CHECK: loop: 72; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[TAIL:%.*]] ] 73; CHECK-NEXT: [[S:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[S_NEXT:%.*]], [[TAIL]] ] 74; CHECK-NEXT: [[ADR:%.*]] = getelementptr i64, i64* [[BASE:%.*]], i64 [[IV]] 75; CHECK-NEXT: [[VAL:%.*]] = load i64, i64* [[ADR]], align 4 76; CHECK-NEXT: [[S_NEXT]] = add i64 [[S]], [[VAL]] 77; CHECK-NEXT: [[INC]] = add nuw nsw i64 [[IV]], 1 78; CHECK-NEXT: [[CMP:%.*]] = icmp ne i64 [[INC]], 4 79; CHECK-NEXT: br i1 [[CMP]], label [[TAIL]], label [[EXIT1:%.*]] 80; CHECK: tail: 81; CHECK-NEXT: [[CMP2:%.*]] = icmp ne i64 [[VAL]], 0 82; CHECK-NEXT: br i1 [[CMP2]], label [[LOOP]], label [[EXIT2:%.*]] 83; CHECK: exit1: 84; CHECK-NEXT: [[S_LCSSA:%.*]] = phi i64 [ [[S]], [[LOOP]] ] 85; CHECK-NEXT: ret i64 [[S_LCSSA]] 86; CHECK: exit2: 87; CHECK-NEXT: [[S_NEXT_LCSSA1:%.*]] = phi i64 [ [[S_NEXT]], [[TAIL]] ] 88; CHECK-NEXT: ret i64 [[S_NEXT_LCSSA1]] 89; 90entry: 91 br label %loop 92 93loop: 94 %iv = phi i64 [ 0, %entry ], [ %inc, %tail ] 95 %s = phi i64 [ 0, %entry ], [ %s.next, %tail ] 96 %adr = getelementptr i64, i64* %base, i64 %iv 97 %val = load i64, i64* %adr 98 %s.next = add i64 %s, %val 99 %inc = add i64 %iv, 1 100 %cmp = icmp ne i64 %inc, 4 101 br i1 %cmp, label %tail, label %exit1 102 103tail: 104 %cmp2 = icmp ne i64 %val, 0 105 br i1 %cmp2, label %loop, label %exit2 106 107exit1: 108 ret i64 %s 109 110exit2: 111 ret i64 %s.next 112} 113 114; SCEV properly unrolls multi-exit loops. 115define i32 @multiExit(i32* %base) nounwind { 116; CHECK-LABEL: @multiExit( 117; CHECK-NEXT: entry: 118; CHECK-NEXT: br label [[L1:%.*]] 119; CHECK: l1: 120; CHECK-NEXT: [[IV1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC1:%.*]], [[L2:%.*]] ] 121; CHECK-NEXT: [[INC1]] = add nuw nsw i32 [[IV1]], 1 122; CHECK-NEXT: [[ADR:%.*]] = getelementptr i32, i32* [[BASE:%.*]], i32 [[IV1]] 123; CHECK-NEXT: [[VAL:%.*]] = load i32, i32* [[ADR]], align 4 124; CHECK-NEXT: br i1 false, label [[L2]], label [[EXIT1:%.*]] 125; CHECK: l2: 126; CHECK-NEXT: br i1 true, label [[L1]], label [[EXIT2:%.*]] 127; CHECK: exit1: 128; CHECK-NEXT: ret i32 1 129; CHECK: exit2: 130; CHECK-NEXT: [[VAL_LCSSA1:%.*]] = phi i32 [ [[VAL]], [[L2]] ] 131; CHECK-NEXT: ret i32 [[VAL_LCSSA1]] 132; 133entry: 134 br label %l1 135l1: 136 %iv1 = phi i32 [ 0, %entry ], [ %inc1, %l2 ] 137 %iv2 = phi i32 [ 0, %entry ], [ %inc2, %l2 ] 138 %inc1 = add i32 %iv1, 1 139 %inc2 = add i32 %iv2, 1 140 %adr = getelementptr i32, i32* %base, i32 %iv1 141 %val = load i32, i32* %adr 142 %cmp1 = icmp slt i32 %iv1, 5 143 br i1 %cmp1, label %l2, label %exit1 144l2: 145 %cmp2 = icmp slt i32 %iv2, 10 146 br i1 %cmp2, label %l1, label %exit2 147exit1: 148 ret i32 1 149exit2: 150 ret i32 %val 151} 152 153 154; SCEV should not unroll a multi-exit loops unless the latch block has 155; a known trip count, regardless of the early exit trip counts. The 156; LoopUnroll utility uses this assumption to optimize the latch 157; block's branch. 158define i32 @multiExitIncomplete(i32* %base) nounwind { 159; CHECK-LABEL: @multiExitIncomplete( 160; CHECK-NEXT: entry: 161; CHECK-NEXT: br label [[L1:%.*]] 162; CHECK: l1: 163; CHECK-NEXT: [[IV1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC1:%.*]], [[L3:%.*]] ] 164; CHECK-NEXT: [[INC1]] = add nuw i32 [[IV1]], 1 165; CHECK-NEXT: [[ADR:%.*]] = getelementptr i32, i32* [[BASE:%.*]], i32 [[IV1]] 166; CHECK-NEXT: [[VAL:%.*]] = load i32, i32* [[ADR]], align 4 167; CHECK-NEXT: [[CMP1:%.*]] = icmp ult i32 [[IV1]], 5 168; CHECK-NEXT: br i1 [[CMP1]], label [[L2:%.*]], label [[EXIT1:%.*]] 169; CHECK: l2: 170; CHECK-NEXT: br i1 true, label [[L3]], label [[EXIT2:%.*]] 171; CHECK: l3: 172; CHECK-NEXT: [[CMP3:%.*]] = icmp ne i32 [[VAL]], 0 173; CHECK-NEXT: br i1 [[CMP3]], label [[L1]], label [[EXIT3:%.*]] 174; CHECK: exit1: 175; CHECK-NEXT: ret i32 1 176; CHECK: exit2: 177; CHECK-NEXT: ret i32 2 178; CHECK: exit3: 179; CHECK-NEXT: ret i32 3 180; 181entry: 182 br label %l1 183l1: 184 %iv1 = phi i32 [ 0, %entry ], [ %inc1, %l3 ] 185 %iv2 = phi i32 [ 0, %entry ], [ %inc2, %l3 ] 186 %inc1 = add i32 %iv1, 1 187 %inc2 = add i32 %iv2, 1 188 %adr = getelementptr i32, i32* %base, i32 %iv1 189 %val = load i32, i32* %adr 190 %cmp1 = icmp slt i32 %iv1, 5 191 br i1 %cmp1, label %l2, label %exit1 192l2: 193 %cmp2 = icmp slt i32 %iv2, 10 194 br i1 %cmp2, label %l3, label %exit2 195l3: 196 %cmp3 = icmp ne i32 %val, 0 197 br i1 %cmp3, label %l1, label %exit3 198 199exit1: 200 ret i32 1 201exit2: 202 ret i32 2 203exit3: 204 ret i32 3 205} 206 207; When loop unroll merges a loop exit with one of its parent loop's 208; exits, SCEV must forget its ExitNotTaken info. 209define void @nestedUnroll() nounwind { 210; CHECK-LABEL: @nestedUnroll( 211; CHECK-NEXT: entry: 212; CHECK-NEXT: br label [[FOR_INC:%.*]] 213; CHECK: for.inc: 214; CHECK-NEXT: br label [[FOR_BODY38:%.*]] 215; CHECK: for.body38: 216; CHECK-NEXT: br label [[FOR_BODY43:%.*]] 217; CHECK: for.body43: 218; CHECK-NEXT: br label [[FOR_BODY87:%.*]] 219; CHECK: for.body87: 220; CHECK-NEXT: br label [[FOR_BODY87]] 221; 222entry: 223 br label %for.inc 224 225for.inc: 226 br i1 false, label %for.inc, label %for.body38.preheader 227 228for.body38.preheader: 229 br label %for.body38 230 231for.body38: 232 %i.113 = phi i32 [ %inc76, %for.inc74 ], [ 0, %for.body38.preheader ] 233 %mul48 = mul nsw i32 %i.113, 6 234 br label %for.body43 235 236for.body43: 237 %j.011 = phi i32 [ 0, %for.body38 ], [ %inc72, %for.body43 ] 238 %add49 = add nsw i32 %j.011, %mul48 239 %sh_prom50 = zext i32 %add49 to i64 240 %inc72 = add nsw i32 %j.011, 1 241 br i1 false, label %for.body43, label %for.inc74 242 243for.inc74: 244 %inc76 = add nsw i32 %i.113, 1 245 br i1 false, label %for.body38, label %for.body87.preheader 246 247for.body87.preheader: 248 br label %for.body87 249 250for.body87: 251 br label %for.body87 252} 253 254; PR16130: clang produces incorrect code with loop/expression at -O2 255; rdar:14036816 loop-unroll makes assumptions about undefined behavior 256; 257; The loop latch is assumed to exit after the first iteration because 258; of the induction variable's NSW flag. However, the loop latch's 259; equality test is skipped and the loop exits after the second 260; iteration via the early exit. So loop unrolling cannot assume that 261; the loop latch's exit count of zero is an upper bound on the number 262; of iterations. 263define void @nsw_latch(i32* %a) nounwind { 264; CHECK-LABEL: @nsw_latch( 265; CHECK-NEXT: entry: 266; CHECK-NEXT: br label [[FOR_BODY:%.*]] 267; CHECK: for.body: 268; CHECK-NEXT: [[B_03:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ADD:%.*]], [[FOR_COND:%.*]] ] 269; CHECK-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[B_03]], 0 270; CHECK-NEXT: [[ADD]] = add nuw nsw i32 [[B_03]], 8 271; CHECK-NEXT: br i1 [[TOBOOL]], label [[FOR_COND]], label [[RETURN:%.*]] 272; CHECK: for.cond: 273; CHECK-NEXT: br i1 false, label [[RETURN]], label [[FOR_BODY]] 274; CHECK: return: 275; CHECK-NEXT: [[B_03_LCSSA:%.*]] = phi i32 [ 8, [[FOR_BODY]] ], [ 0, [[FOR_COND]] ] 276; CHECK-NEXT: [[RETVAL_0:%.*]] = phi i32 [ 1, [[FOR_BODY]] ], [ 0, [[FOR_COND]] ] 277; CHECK-NEXT: store i32 [[B_03_LCSSA]], i32* [[A:%.*]], align 4 278; CHECK-NEXT: ret void 279; 280entry: 281 br label %for.body 282 283for.body: ; preds = %for.cond, %entry 284 %b.03 = phi i32 [ 0, %entry ], [ %add, %for.cond ] 285 %tobool = icmp eq i32 %b.03, 0 286 %add = add nsw i32 %b.03, 8 287 br i1 %tobool, label %for.cond, label %return 288 289for.cond: ; preds = %for.body 290 %cmp = icmp eq i32 %add, 13 291 br i1 %cmp, label %return, label %for.body 292 293return: ; preds = %for.body, %for.cond 294 %b.03.lcssa = phi i32 [ %b.03, %for.body ], [ %b.03, %for.cond ] 295 %retval.0 = phi i32 [ 1, %for.body ], [ 0, %for.cond ] 296 store i32 %b.03.lcssa, i32* %a, align 4 297 ret void 298} 299