208 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 62; RUN: opt < %s -disable-output -passes="print<da>" -da-dump-monotonicity-report \3; RUN: -da-enable-monotonicity-check 2>&1 | FileCheck %s4 5; int8_t offset = start;6; for (int i = 0; i < 100; i++, offset += step)7; a[sext(offset)] = 0;8;9define void @sext_nsw(ptr %a, i8 %start, i8 %step) {10; CHECK-LABEL: 'sext_nsw'11; CHECK-NEXT: Monotonicity check:12; CHECK-NEXT: Inst: store i8 0, ptr %idx, align 113; CHECK-NEXT: Expr: {(sext i8 %start to i64),+,(sext i8 %step to i64)}<nsw><%loop>14; CHECK-NEXT: Monotonicity: MultivariateSignedMonotonic15; CHECK-EMPTY:16; CHECK-NEXT: Src: store i8 0, ptr %idx, align 1 --> Dst: store i8 0, ptr %idx, align 117; CHECK-NEXT: da analyze - none!18;19entry:20 br label %loop21 22loop:23 %i = phi i64 [ 0, %entry ], [ %i.inc, %loop ]24 %offset = phi i8 [ %start, %entry ], [ %offset.next, %loop ]25 %offset.sext = sext i8 %offset to i6426 %idx = getelementptr i8, ptr %a, i64 %offset.sext27 store i8 0, ptr %idx28 %i.inc = add nsw i64 %i, 129 %offset.next = add nsw i8 %offset, %step30 %exitcond = icmp eq i64 %i.inc, 10031 br i1 %exitcond, label %exit, label %loop32 33exit:34 ret void35}36 37; The addition for `%offset.next` can wrap, so we cannot prove monotonicity.38;39; int8_t offset = start;40; for (int i = 0; i < 100; i++, offset += step)41; a[sext(offset)] = 0;42;43define void @sext_may_wrap(ptr %a, i8 %start, i8 %step) {44; CHECK-LABEL: 'sext_may_wrap'45; CHECK-NEXT: Monotonicity check:46; CHECK-NEXT: Inst: store i8 0, ptr %idx, align 147; CHECK-NEXT: Expr: (sext i8 {%start,+,%step}<%loop> to i64)48; CHECK-NEXT: Monotonicity: Unknown49; CHECK-NEXT: Reason: (sext i8 {%start,+,%step}<%loop> to i64)50; CHECK-EMPTY:51; CHECK-NEXT: Src: store i8 0, ptr %idx, align 1 --> Dst: store i8 0, ptr %idx, align 152; CHECK-NEXT: da analyze - confused!53;54entry:55 br label %loop56 57loop:58 %i = phi i64 [ 0, %entry ], [ %i.inc, %loop ]59 %offset = phi i8 [ %start, %entry ], [ %offset.next, %loop ]60 %offset.sext = sext i8 %offset to i6461 %idx = getelementptr i8, ptr %a, i64 %offset.sext62 store i8 0, ptr %idx63 %i.inc = add nsw i64 %i, 164 %offset.next = add i8 %offset, %step65 %exitcond = icmp eq i64 %i.inc, 10066 br i1 %exitcond, label %exit, label %loop67 68exit:69 ret void70}71 72; for (int8_t i = 0; i < 100; i++)73; a[zext(offset)] = 0;74;75define void @zext_pos(ptr %a) {76; CHECK-LABEL: 'zext_pos'77; CHECK-NEXT: Monotonicity check:78; CHECK-NEXT: Inst: store i8 0, ptr %idx, align 179; CHECK-NEXT: Expr: {0,+,1}<nuw><nsw><%loop>80; CHECK-NEXT: Monotonicity: MultivariateSignedMonotonic81; CHECK-EMPTY:82; CHECK-NEXT: Src: store i8 0, ptr %idx, align 1 --> Dst: store i8 0, ptr %idx, align 183; CHECK-NEXT: da analyze - none!84;85entry:86 br label %loop87 88loop:89 %i = phi i8 [ 0, %entry ], [ %i.inc, %loop ]90 %offset.zext = zext nneg i8 %i to i6491 %idx = getelementptr i8, ptr %a, i64 %offset.zext92 store i8 0, ptr %idx93 %i.inc = add nsw i8 %i, 194 %exitcond = icmp eq i8 %i.inc, 10095 br i1 %exitcond, label %exit, label %loop96 97exit:98 ret void99}100 101; The zero-extened value of `offset` is no longer monotonic. In fact, the102; values of `offset` in each iteration are:103;104; iteration | 0 | 1 | 2 | ...105; -------------|-----|---|---|---------106; offset | -1 | 0 | 1 | ...107; zext(offset) | 255 | 0 | 1 | ...108;109;110; for (int8_t i = -1; i < 100; i++)111; a[zext(offset)] = 0;112;113define void @zext_cross_zero(ptr %a) {114; CHECK-LABEL: 'zext_cross_zero'115; CHECK-NEXT: Monotonicity check:116; CHECK-NEXT: Inst: store i8 0, ptr %idx, align 1117; CHECK-NEXT: Expr: (zext i8 {-1,+,1}<nsw><%loop> to i64)118; CHECK-NEXT: Monotonicity: Unknown119; CHECK-NEXT: Reason: (zext i8 {-1,+,1}<nsw><%loop> to i64)120; CHECK-EMPTY:121; CHECK-NEXT: Src: store i8 0, ptr %idx, align 1 --> Dst: store i8 0, ptr %idx, align 1122; CHECK-NEXT: da analyze - confused!123;124entry:125 br label %loop126 127loop:128 %i = phi i8 [ -1, %entry ], [ %i.inc, %loop ]129 %offset.zext = zext nneg i8 %i to i64130 %idx = getelementptr i8, ptr %a, i64 %offset.zext131 store i8 0, ptr %idx132 %i.inc = add nsw i8 %i, 1133 %exitcond = icmp eq i8 %i.inc, 100134 br i1 %exitcond, label %exit, label %loop135 136exit:137 ret void138}139 140; In principle, we can prove that `zext(offset)` is monotonic since we know141; that `offset` is non-negative.142;143; int8_t offset = 0;144; for (int i = 0; i < 100; i++, offset += step)145; a[zext(offset)] = 0;146;147define void @zext_nneg_nsw(ptr %a, i8 %step) {148; CHECK-LABEL: 'zext_nneg_nsw'149; CHECK-NEXT: Monotonicity check:150; CHECK-NEXT: Inst: store i8 0, ptr %idx, align 1151; CHECK-NEXT: Expr: (zext i8 {0,+,%step}<nsw><%loop> to i64)152; CHECK-NEXT: Monotonicity: Unknown153; CHECK-NEXT: Reason: (zext i8 {0,+,%step}<nsw><%loop> to i64)154; CHECK-EMPTY:155; CHECK-NEXT: Src: store i8 0, ptr %idx, align 1 --> Dst: store i8 0, ptr %idx, align 1156; CHECK-NEXT: da analyze - confused!157;158entry:159 br label %loop160 161loop:162 %i = phi i64 [ 0, %entry ], [ %i.inc, %loop ]163 %offset = phi i8 [ 0, %entry ], [ %offset.next, %loop ]164 %offset.zext = zext nneg i8 %offset to i64165 %idx = getelementptr i8, ptr %a, i64 %offset.zext166 store i8 0, ptr %idx167 %i.inc = add nsw i64 %i, 1168 %offset.next = add nsw i8 %offset, %step169 %exitcond = icmp eq i64 %i.inc, 100170 br i1 %exitcond, label %exit, label %loop171 172exit:173 ret void174}175 176; SCEV handles `i & 1` as an i1 addrec. Ensure that the monotonicity analysis177; properly analyzes it.178;179; for (i = 0; i < 100; i++)180; a[i & 1] = 0;181;182define void @offset_truncated_to_i1(ptr %a) {183; CHECK-LABEL: 'offset_truncated_to_i1'184; CHECK-NEXT: Monotonicity check:185; CHECK-NEXT: Inst: store i8 0, ptr %idx, align 1186; CHECK-NEXT: Expr: (zext i1 {false,+,true}<%loop> to i64)187; CHECK-NEXT: Monotonicity: Unknown188; CHECK-NEXT: Reason: (zext i1 {false,+,true}<%loop> to i64)189; CHECK-EMPTY:190; CHECK-NEXT: Src: store i8 0, ptr %idx, align 1 --> Dst: store i8 0, ptr %idx, align 1191; CHECK-NEXT: da analyze - confused!192;193entry:194 br label %loop195 196loop:197 %i = phi i64 [ 0, %entry ], [ %i.inc, %loop ]198 %and = and i64 %i, 1199 %idx = getelementptr inbounds i8, ptr %a, i64 %and200 store i8 0, ptr %idx201 %i.inc = add nsw i64 %i, 1202 %exitcond = icmp eq i64 %i.inc, 100203 br i1 %exitcond, label %exit, label %loop204 205exit:206 ret void207}208