1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
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: {{.*}}
|
