diff options
Diffstat (limited to 'llvm/test/Analysis/DependenceAnalysis/symbolic-rdiv-overflow.ll')
| -rw-r--r-- | llvm/test/Analysis/DependenceAnalysis/symbolic-rdiv-overflow.ll | 137 |
1 files changed, 137 insertions, 0 deletions
diff --git a/llvm/test/Analysis/DependenceAnalysis/symbolic-rdiv-overflow.ll b/llvm/test/Analysis/DependenceAnalysis/symbolic-rdiv-overflow.ll new file mode 100644 index 0000000..c5ff988 --- /dev/null +++ b/llvm/test/Analysis/DependenceAnalysis/symbolic-rdiv-overflow.ll @@ -0,0 +1,137 @@ +; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 6 +; RUN: opt < %s -disable-output "-passes=print<da>" 2>&1 \ +; RUN: | FileCheck %s --check-prefixes=CHECK,CHECK-ALL +; RUN: opt < %s -disable-output "-passes=print<da>" -da-enable-dependence-test=symbolic-rdiv 2>&1 \ +; RUN: | FileCheck %s --check-prefixes=CHECK,CHECK-SYMBOLIC-RDIV + +; for (i = 0; i < (1LL << 62); i++) { +; if (0 <= 2*i - 2) +; A[2*i - 2] = 1; +; A[i] = 2; +; } +; +; FIXME: DependenceAnalysis currently detects no dependency between the two +; stores, but it does exist. For example, each store will access A[0] when i +; is 1 and 0 respectively. +; The root cause is that the product of the BTC and the coefficient +; ((1LL << 62) - 1 and 2) overflows in a signed sense. +define void @symbolicrdiv_prod_ovfl(ptr %A) { +; CHECK-ALL-LABEL: 'symbolicrdiv_prod_ovfl' +; CHECK-ALL-NEXT: Src: store i8 1, ptr %gep.0, align 1 --> Dst: store i8 1, ptr %gep.0, align 1 +; CHECK-ALL-NEXT: da analyze - none! +; CHECK-ALL-NEXT: Src: store i8 1, ptr %gep.0, align 1 --> Dst: store i8 2, ptr %gep.1, align 1 +; CHECK-ALL-NEXT: da analyze - none! +; CHECK-ALL-NEXT: Src: store i8 2, ptr %gep.1, align 1 --> Dst: store i8 2, ptr %gep.1, align 1 +; CHECK-ALL-NEXT: da analyze - none! +; +; CHECK-SYMBOLIC-RDIV-LABEL: 'symbolicrdiv_prod_ovfl' +; CHECK-SYMBOLIC-RDIV-NEXT: Src: store i8 1, ptr %gep.0, align 1 --> Dst: store i8 1, ptr %gep.0, align 1 +; CHECK-SYMBOLIC-RDIV-NEXT: da analyze - none! +; CHECK-SYMBOLIC-RDIV-NEXT: Src: store i8 1, ptr %gep.0, align 1 --> Dst: store i8 2, ptr %gep.1, align 1 +; CHECK-SYMBOLIC-RDIV-NEXT: da analyze - none! +; CHECK-SYMBOLIC-RDIV-NEXT: Src: store i8 2, ptr %gep.1, align 1 --> Dst: store i8 2, ptr %gep.1, align 1 +; CHECK-SYMBOLIC-RDIV-NEXT: da analyze - consistent output [*]! +; +entry: + br label %loop.header + +loop.header: + %i = phi i64 [ 0, %entry ], [ %i.inc, %loop.latch ] + %offset = phi i64 [ -2, %entry ], [ %offset.next, %loop.latch ] + %ec = icmp eq i64 %i, 4611686018427387904 + br i1 %ec, label %exit, label %loop.body + +loop.body: + %cond = icmp sge i64 %offset, 0 + br i1 %cond, label %if.then, label %loop.latch + +if.then: + %gep.0 = getelementptr inbounds i8, ptr %A, i64 %offset + store i8 1, ptr %gep.0 + br label %loop.latch + +loop.latch: + %gep.1 = getelementptr inbounds i8, ptr %A, i64 %i + store i8 2, ptr %gep.1 + %i.inc = add nuw nsw i64 %i, 1 + %offset.next = add nsw i64 %offset, 2 + br label %loop.header + +exit: + ret void +} + +; offset0 = -4611686018427387904; // -2^62 +; offset1 = 4611686018427387904; // 2^62 +; for (i = 0; i < (1LL << 62) - 100; i++) { +; if (0 <= offset0) +; A[offset0] = 1; +; if (0 <= offset1) +; A[offset1] = 2; +; offset0 += 2; +; offset1 -= 1; +; } +; +; FIXME: DependenceAnalysis currently detects no dependency between the two +; stores, but it does exist. For example, +; +; memory access | i == 2^61 | i == 2^61 + 2^59 | i == 2^61 + 2^60 +; -------------------------|-----------|------------------|------------------- +; A[2*i - 2^62] (offset0) | | A[2^60] | A[2^61] +; A[-i + 2^62] (offset1) | A[2^61] | | A[2^60] +; +; The root cause is that the calculation of the differenct between the two +; constants (-2^62 and 2^62) overflows in a signed sense. +define void @symbolicrdiv_delta_ovfl(ptr %A) { +; CHECK-ALL-LABEL: 'symbolicrdiv_delta_ovfl' +; CHECK-ALL-NEXT: Src: store i8 1, ptr %gep.0, align 1 --> Dst: store i8 1, ptr %gep.0, align 1 +; CHECK-ALL-NEXT: da analyze - none! +; CHECK-ALL-NEXT: Src: store i8 1, ptr %gep.0, align 1 --> Dst: store i8 2, ptr %gep.1, align 1 +; CHECK-ALL-NEXT: da analyze - none! +; CHECK-ALL-NEXT: Src: store i8 2, ptr %gep.1, align 1 --> Dst: store i8 2, ptr %gep.1, align 1 +; CHECK-ALL-NEXT: da analyze - none! +; +; CHECK-SYMBOLIC-RDIV-LABEL: 'symbolicrdiv_delta_ovfl' +; CHECK-SYMBOLIC-RDIV-NEXT: Src: store i8 1, ptr %gep.0, align 1 --> Dst: store i8 1, ptr %gep.0, align 1 +; CHECK-SYMBOLIC-RDIV-NEXT: da analyze - consistent output [*]! +; CHECK-SYMBOLIC-RDIV-NEXT: Src: store i8 1, ptr %gep.0, align 1 --> Dst: store i8 2, ptr %gep.1, align 1 +; CHECK-SYMBOLIC-RDIV-NEXT: da analyze - none! +; CHECK-SYMBOLIC-RDIV-NEXT: Src: store i8 2, ptr %gep.1, align 1 --> Dst: store i8 2, ptr %gep.1, align 1 +; CHECK-SYMBOLIC-RDIV-NEXT: da analyze - consistent output [*]! +; +entry: + br label %loop.header + +loop.header: + %i = phi i64 [ 0, %entry ], [ %i.inc, %loop.latch ] + %offset.0 = phi i64 [ -4611686018427387904, %entry ], [ %offset.0.next, %loop.latch ] + %offset.1 = phi i64 [ 4611686018427387904, %entry ], [ %offset.1.next, %loop.latch ] + %cond.0 = icmp sge i64 %offset.0, 0 + %cond.1 = icmp sge i64 %offset.1, 0 + br i1 %cond.0, label %if.then.0, label %loop.middle + +if.then.0: + %gep.0 = getelementptr inbounds i8, ptr %A, i64 %offset.0 + store i8 1, ptr %gep.0 + br label %loop.middle + +loop.middle: + br i1 %cond.1, label %if.then.1, label %loop.latch + +if.then.1: + %gep.1 = getelementptr inbounds i8, ptr %A, i64 %offset.1 + store i8 2, ptr %gep.1 + br label %loop.latch + +loop.latch: + %i.inc = add nuw nsw i64 %i, 1 + %offset.0.next = add nsw i64 %offset.0, 2 + %offset.1.next = sub nsw i64 %offset.1, 1 + %ec = icmp eq i64 %i.inc, 4611686018427387804 ; 2^62 - 100 + br i1 %ec, label %exit, label %loop.header + +exit: + ret void +} +;; NOTE: These prefixes are unused and the list is autogenerated. Do not add tests below this line: +; CHECK: {{.*}} |