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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
|
; RUN: opt < %s -instcombine -S | FileCheck %s
target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128"
; These are UB-free rotate left/right patterns that are narrowed to a smaller bitwidth.
; See PR34046 and PR16726 for motivating examples:
; https://bugs.llvm.org/show_bug.cgi?id=34046
; https://bugs.llvm.org/show_bug.cgi?id=16726
define i16 @rotate_left_16bit(i16 %v, i32 %shift) {
; CHECK-LABEL: @rotate_left_16bit(
; CHECK-NEXT: [[TMP1:%.*]] = trunc i32 %shift to i16
; CHECK-NEXT: [[TMP2:%.*]] = and i16 [[TMP1]], 15
; CHECK-NEXT: [[TMP3:%.*]] = sub i16 0, [[TMP1]]
; CHECK-NEXT: [[TMP4:%.*]] = and i16 [[TMP3]], 15
; CHECK-NEXT: [[TMP5:%.*]] = lshr i16 %v, [[TMP4]]
; CHECK-NEXT: [[TMP6:%.*]] = shl i16 %v, [[TMP2]]
; CHECK-NEXT: [[CONV2:%.*]] = or i16 [[TMP5]], [[TMP6]]
; CHECK-NEXT: ret i16 [[CONV2]]
;
%and = and i32 %shift, 15
%conv = zext i16 %v to i32
%shl = shl i32 %conv, %and
%sub = sub i32 16, %and
%shr = lshr i32 %conv, %sub
%or = or i32 %shr, %shl
%conv2 = trunc i32 %or to i16
ret i16 %conv2
}
; Commute the 'or' operands and try a vector type.
define <2 x i16> @rotate_left_commute_16bit_vec(<2 x i16> %v, <2 x i32> %shift) {
; CHECK-LABEL: @rotate_left_commute_16bit_vec(
; CHECK-NEXT: [[TMP1:%.*]] = trunc <2 x i32> %shift to <2 x i16>
; CHECK-NEXT: [[TMP2:%.*]] = and <2 x i16> [[TMP1]], <i16 15, i16 15>
; CHECK-NEXT: [[TMP3:%.*]] = sub <2 x i16> zeroinitializer, [[TMP1]]
; CHECK-NEXT: [[TMP4:%.*]] = and <2 x i16> [[TMP3]], <i16 15, i16 15>
; CHECK-NEXT: [[TMP5:%.*]] = shl <2 x i16> %v, [[TMP2]]
; CHECK-NEXT: [[TMP6:%.*]] = lshr <2 x i16> %v, [[TMP4]]
; CHECK-NEXT: [[CONV2:%.*]] = or <2 x i16> [[TMP5]], [[TMP6]]
; CHECK-NEXT: ret <2 x i16> [[CONV2]]
;
%and = and <2 x i32> %shift, <i32 15, i32 15>
%conv = zext <2 x i16> %v to <2 x i32>
%shl = shl <2 x i32> %conv, %and
%sub = sub <2 x i32> <i32 16, i32 16>, %and
%shr = lshr <2 x i32> %conv, %sub
%or = or <2 x i32> %shl, %shr
%conv2 = trunc <2 x i32> %or to <2 x i16>
ret <2 x i16> %conv2
}
; Change the size, rotation direction (the subtract is on the left-shift), and mask op.
define i8 @rotate_right_8bit(i8 %v, i3 %shift) {
; CHECK-LABEL: @rotate_right_8bit(
; CHECK-NEXT: [[TMP1:%.*]] = zext i3 %shift to i8
; CHECK-NEXT: [[TMP2:%.*]] = sub i3 0, %shift
; CHECK-NEXT: [[TMP3:%.*]] = zext i3 [[TMP2]] to i8
; CHECK-NEXT: [[TMP4:%.*]] = shl i8 %v, [[TMP3]]
; CHECK-NEXT: [[TMP5:%.*]] = lshr i8 %v, [[TMP1]]
; CHECK-NEXT: [[CONV2:%.*]] = or i8 [[TMP4]], [[TMP5]]
; CHECK-NEXT: ret i8 [[CONV2]]
;
%and = zext i3 %shift to i32
%conv = zext i8 %v to i32
%shr = lshr i32 %conv, %and
%sub = sub i32 8, %and
%shl = shl i32 %conv, %sub
%or = or i32 %shl, %shr
%conv2 = trunc i32 %or to i8
ret i8 %conv2
}
; The shifted value does not need to be a zexted value; here it is masked.
; The shift mask could be less than the bitwidth, but this is still ok.
define i8 @rotate_right_commute_8bit(i32 %v, i32 %shift) {
; CHECK-LABEL: @rotate_right_commute_8bit(
; CHECK-NEXT: [[TMP1:%.*]] = trunc i32 %shift to i8
; CHECK-NEXT: [[TMP2:%.*]] = and i8 [[TMP1]], 3
; CHECK-NEXT: [[TMP3:%.*]] = sub nsw i8 0, [[TMP2]]
; CHECK-NEXT: [[TMP4:%.*]] = and i8 [[TMP3]], 7
; CHECK-NEXT: [[TMP5:%.*]] = trunc i32 %v to i8
; CHECK-NEXT: [[TMP6:%.*]] = lshr i8 [[TMP5]], [[TMP2]]
; CHECK-NEXT: [[TMP7:%.*]] = shl i8 [[TMP5]], [[TMP4]]
; CHECK-NEXT: [[CONV2:%.*]] = or i8 [[TMP6]], [[TMP7]]
; CHECK-NEXT: ret i8 [[CONV2]]
;
%and = and i32 %shift, 3
%conv = and i32 %v, 255
%shr = lshr i32 %conv, %and
%sub = sub i32 8, %and
%shl = shl i32 %conv, %sub
%or = or i32 %shr, %shl
%conv2 = trunc i32 %or to i8
ret i8 %conv2
}
; If the original source does not mask the shift amount,
; we still do the transform by adding masks to make it safe.
define i8 @rotate8_not_safe(i8 %v, i32 %shamt) {
; CHECK-LABEL: @rotate8_not_safe(
; CHECK-NEXT: [[TMP1:%.*]] = trunc i32 %shamt to i8
; CHECK-NEXT: [[TMP2:%.*]] = sub i8 0, [[TMP1]]
; CHECK-NEXT: [[TMP3:%.*]] = and i8 [[TMP1]], 7
; CHECK-NEXT: [[TMP4:%.*]] = and i8 [[TMP2]], 7
; CHECK-NEXT: [[TMP5:%.*]] = lshr i8 %v, [[TMP4]]
; CHECK-NEXT: [[TMP6:%.*]] = shl i8 %v, [[TMP3]]
; CHECK-NEXT: [[RET:%.*]] = or i8 [[TMP5]], [[TMP6]]
; CHECK-NEXT: ret i8 [[RET]]
;
%conv = zext i8 %v to i32
%sub = sub i32 8, %shamt
%shr = lshr i32 %conv, %sub
%shl = shl i32 %conv, %shamt
%or = or i32 %shr, %shl
%ret = trunc i32 %or to i8
ret i8 %ret
}
; The next two tests mask sure we narrower (x << (x & 15)) | (x >> (-x & 15))
; when types have been promoted.
; FIXME: We should be able to narrow this.
define i16 @rotate16_neg_mask(i16 %v, i16 %shamt) {
; CHECK-LABEL: @rotate16_neg_mask(
; CHECK-NEXT: [[CONV:%.*]] = zext i16 [[V:%.*]] to i32
; CHECK-NEXT: [[RSHAMT:%.*]] = and i16 [[SHAMT:%.*]], 15
; CHECK-NEXT: [[RSHAMTCONV:%.*]] = zext i16 [[RSHAMT]] to i32
; CHECK-NEXT: [[SHR:%.*]] = lshr i32 [[CONV]], [[RSHAMTCONV]]
; CHECK-NEXT: [[NEG:%.*]] = sub i16 0, [[SHAMT]]
; CHECK-NEXT: [[LSHAMT:%.*]] = and i16 [[NEG]], 15
; CHECK-NEXT: [[LSHAMTCONV:%.*]] = zext i16 [[LSHAMT]] to i32
; CHECK-NEXT: [[SHL:%.*]] = shl i32 [[CONV]], [[LSHAMTCONV]]
; CHECK-NEXT: [[OR:%.*]] = or i32 [[SHR]], [[SHL]]
; CHECK-NEXT: [[RET:%.*]] = trunc i32 [[OR]] to i16
; CHECK-NEXT: ret i16 [[RET]]
;
%conv = zext i16 %v to i32
%rshamt = and i16 %shamt, 15
%rshamtconv = zext i16 %rshamt to i32
%shr = lshr i32 %conv, %rshamtconv
%neg = sub i16 0, %shamt
%lshamt = and i16 %neg, 15
%lshamtconv = zext i16 %lshamt to i32
%shl = shl i32 %conv, %lshamtconv
%or = or i32 %shr, %shl
%ret = trunc i32 %or to i16
ret i16 %ret
}
define i8 @rotate8_neg_mask(i8 %v, i8 %shamt) {
; CHECK-LABEL: @rotate8_neg_mask(
; CHECK-NEXT: [[CONV:%.*]] = zext i8 [[V:%.*]] to i32
; CHECK-NEXT: [[RSHAMT:%.*]] = and i8 [[SHAMT:%.*]], 7
; CHECK-NEXT: [[RSHAMTCONV:%.*]] = zext i8 [[RSHAMT]] to i32
; CHECK-NEXT: [[SHR:%.*]] = lshr i32 [[CONV]], [[RSHAMTCONV]]
; CHECK-NEXT: [[NEG:%.*]] = sub i8 0, [[SHAMT]]
; CHECK-NEXT: [[LSHAMT:%.*]] = and i8 [[NEG]], 7
; CHECK-NEXT: [[LSHAMTCONV:%.*]] = zext i8 [[LSHAMT]] to i32
; CHECK-NEXT: [[SHL:%.*]] = shl i32 [[CONV]], [[LSHAMTCONV]]
; CHECK-NEXT: [[OR:%.*]] = or i32 [[SHR]], [[SHL]]
; CHECK-NEXT: [[RET:%.*]] = trunc i32 [[OR]] to i8
; CHECK-NEXT: ret i8 [[RET]]
;
%conv = zext i8 %v to i32
%rshamt = and i8 %shamt, 7
%rshamtconv = zext i8 %rshamt to i32
%shr = lshr i32 %conv, %rshamtconv
%neg = sub i8 0, %shamt
%lshamt = and i8 %neg, 7
%lshamtconv = zext i8 %lshamt to i32
%shl = shl i32 %conv, %lshamtconv
%or = or i32 %shr, %shl
%ret = trunc i32 %or to i8
ret i8 %ret
}
; The next two types have a shift amount that is already i32 so we would still
; need a truncate for it going into the rotate pattern.
; FIXME: We can narrow this, but we would still need a trunc on the shift amt.
define i16 @rotate16_neg_mask_wide_amount(i16 %v, i32 %shamt) {
; CHECK-LABEL: @rotate16_neg_mask_wide_amount(
; CHECK-NEXT: [[CONV:%.*]] = zext i16 [[V:%.*]] to i32
; CHECK-NEXT: [[RSHAMT:%.*]] = and i32 [[SHAMT:%.*]], 15
; CHECK-NEXT: [[SHR:%.*]] = lshr i32 [[CONV]], [[RSHAMT]]
; CHECK-NEXT: [[NEG:%.*]] = sub i32 0, [[SHAMT]]
; CHECK-NEXT: [[LSHAMT:%.*]] = and i32 [[NEG]], 15
; CHECK-NEXT: [[SHL:%.*]] = shl i32 [[CONV]], [[LSHAMT]]
; CHECK-NEXT: [[OR:%.*]] = or i32 [[SHR]], [[SHL]]
; CHECK-NEXT: [[RET:%.*]] = trunc i32 [[OR]] to i16
; CHECK-NEXT: ret i16 [[RET]]
;
%conv = zext i16 %v to i32
%rshamt = and i32 %shamt, 15
%shr = lshr i32 %conv, %rshamt
%neg = sub i32 0, %shamt
%lshamt = and i32 %neg, 15
%shl = shl i32 %conv, %lshamt
%or = or i32 %shr, %shl
%ret = trunc i32 %or to i16
ret i16 %ret
}
define i8 @rotate8_neg_mask_wide_amount(i8 %v, i32 %shamt) {
; CHECK-LABEL: @rotate8_neg_mask_wide_amount(
; CHECK-NEXT: [[CONV:%.*]] = zext i8 [[V:%.*]] to i32
; CHECK-NEXT: [[RSHAMT:%.*]] = and i32 [[SHAMT:%.*]], 7
; CHECK-NEXT: [[SHR:%.*]] = lshr i32 [[CONV]], [[RSHAMT]]
; CHECK-NEXT: [[NEG:%.*]] = sub i32 0, [[SHAMT]]
; CHECK-NEXT: [[LSHAMT:%.*]] = and i32 [[NEG]], 7
; CHECK-NEXT: [[SHL:%.*]] = shl i32 [[CONV]], [[LSHAMT]]
; CHECK-NEXT: [[OR:%.*]] = or i32 [[SHR]], [[SHL]]
; CHECK-NEXT: [[RET:%.*]] = trunc i32 [[OR]] to i8
; CHECK-NEXT: ret i8 [[RET]]
;
%conv = zext i8 %v to i32
%rshamt = and i32 %shamt, 7
%shr = lshr i32 %conv, %rshamt
%neg = sub i32 0, %shamt
%lshamt = and i32 %neg, 7
%shl = shl i32 %conv, %lshamt
%or = or i32 %shr, %shl
%ret = trunc i32 %or to i8
ret i8 %ret
}
|
