1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt < %s -instcombine -S | FileCheck %s
3
4target datalayout = "n8:16:32:64"
5
6; Eliminating the casts in this testcase (by narrowing the AND operation)
7; allows instcombine to realize the function always returns false.
8
9define i1 @test1(i32 %A, i32 %B) {
10; CHECK-LABEL: @test1(
11; CHECK-NEXT:    ret i1 false
12;
13  %C1 = icmp slt i32 %A, %B
14  %ELIM1 = zext i1 %C1 to i32
15  %C2 = icmp sgt i32 %A, %B
16  %ELIM2 = zext i1 %C2 to i32
17  %C3 = and i32 %ELIM1, %ELIM2
18  %ELIM3 = trunc i32 %C3 to i1
19  ret i1 %ELIM3
20}
21
22; The next 6 (3 logic ops * (scalar+vector)) tests show potential cases for narrowing a bitwise logic op.
23
24define i32 @shrink_xor(i64 %a) {
25; CHECK-LABEL: @shrink_xor(
26; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[A:%.*]] to i32
27; CHECK-NEXT:    [[TRUNC:%.*]] = xor i32 [[TMP1]], 1
28; CHECK-NEXT:    ret i32 [[TRUNC]]
29;
30  %xor = xor i64 %a, 1
31  %trunc = trunc i64 %xor to i32
32  ret i32 %trunc
33}
34
35; Vectors (with splat constants) should get the same transform.
36
37define <2 x i32> @shrink_xor_vec(<2 x i64> %a) {
38; CHECK-LABEL: @shrink_xor_vec(
39; CHECK-NEXT:    [[TMP1:%.*]] = trunc <2 x i64> [[A:%.*]] to <2 x i32>
40; CHECK-NEXT:    [[TRUNC:%.*]] = xor <2 x i32> [[TMP1]], <i32 2, i32 2>
41; CHECK-NEXT:    ret <2 x i32> [[TRUNC]]
42;
43  %xor = xor <2 x i64> %a, <i64 2, i64 2>
44  %trunc = trunc <2 x i64> %xor to <2 x i32>
45  ret <2 x i32> %trunc
46}
47
48; Source and dest types are not in the datalayout.
49
50define i3 @shrink_or(i6 %a) {
51; CHECK-LABEL: @shrink_or(
52; CHECK-NEXT:    [[TMP1:%.*]] = trunc i6 [[A:%.*]] to i3
53; CHECK-NEXT:    [[TRUNC:%.*]] = or i3 [[TMP1]], 1
54; CHECK-NEXT:    ret i3 [[TRUNC]]
55;
56  %or = or i6 %a, 33
57  %trunc = trunc i6 %or to i3
58  ret i3 %trunc
59}
60
61; Vectors (with non-splat constants) should get the same transform.
62
63define <2 x i8> @shrink_or_vec(<2 x i16> %a) {
64; CHECK-LABEL: @shrink_or_vec(
65; CHECK-NEXT:    [[TMP1:%.*]] = trunc <2 x i16> [[A:%.*]] to <2 x i8>
66; CHECK-NEXT:    [[TRUNC:%.*]] = or <2 x i8> [[TMP1]], <i8 -1, i8 0>
67; CHECK-NEXT:    ret <2 x i8> [[TRUNC]]
68;
69  %or = or <2 x i16> %a, <i16 -1, i16 256>
70  %trunc = trunc <2 x i16> %or to <2 x i8>
71  ret <2 x i8> %trunc
72}
73
74; We discriminate against weird types.
75
76define i31 @shrink_and(i64 %a) {
77; CHECK-LABEL: @shrink_and(
78; CHECK-NEXT:    [[AND:%.*]] = and i64 [[A:%.*]], 42
79; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i64 [[AND]] to i31
80; CHECK-NEXT:    ret i31 [[TRUNC]]
81;
82  %and = and i64 %a, 42
83  %trunc = trunc i64 %and to i31
84  ret i31 %trunc
85}
86
87; Chop the top of the constant(s) if needed.
88
89define <2 x i32> @shrink_and_vec(<2 x i33> %a) {
90; CHECK-LABEL: @shrink_and_vec(
91; CHECK-NEXT:    [[TMP1:%.*]] = trunc <2 x i33> [[A:%.*]] to <2 x i32>
92; CHECK-NEXT:    [[TRUNC:%.*]] = and <2 x i32> [[TMP1]], <i32 0, i32 6>
93; CHECK-NEXT:    ret <2 x i32> [[TRUNC]]
94;
95  %and = and <2 x i33> %a, <i33 4294967296, i33 6>
96  %trunc = trunc <2 x i33> %and to <2 x i32>
97  ret <2 x i32> %trunc
98}
99
100; FIXME:
101; This is based on an 'any_of' loop construct.
102; By narrowing the phi and logic op, we simplify away the zext and the final icmp.
103
104define i1 @searchArray1(i32 %needle, i32* %haystack) {
105; CHECK-LABEL: @searchArray1(
106; CHECK-NEXT:  entry:
107; CHECK-NEXT:    br label [[LOOP:%.*]]
108; CHECK:       loop:
109; CHECK-NEXT:    [[INDVAR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[LOOP]] ]
110; CHECK-NEXT:    [[FOUND:%.*]] = phi i8 [ 0, [[ENTRY]] ], [ [[OR:%.*]], [[LOOP]] ]
111; CHECK-NEXT:    [[TMP0:%.*]] = sext i32 [[INDVAR]] to i64
112; CHECK-NEXT:    [[IDX:%.*]] = getelementptr i32, i32* [[HAYSTACK:%.*]], i64 [[TMP0]]
113; CHECK-NEXT:    [[LD:%.*]] = load i32, i32* [[IDX]], align 4
114; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[LD]], [[NEEDLE:%.*]]
115; CHECK-NEXT:    [[ZEXT:%.*]] = zext i1 [[CMP1]] to i8
116; CHECK-NEXT:    [[OR]] = or i8 [[FOUND]], [[ZEXT]]
117; CHECK-NEXT:    [[INDVAR_NEXT]] = add i32 [[INDVAR]], 1
118; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INDVAR_NEXT]], 1000
119; CHECK-NEXT:    br i1 [[EXITCOND]], label [[EXIT:%.*]], label [[LOOP]]
120; CHECK:       exit:
121; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i8 [[OR]], 0
122; CHECK-NEXT:    ret i1 [[TOBOOL]]
123;
124entry:
125  br label %loop
126
127loop:
128  %indvar = phi i32 [ 0, %entry ], [ %indvar.next, %loop ]
129  %found = phi i8 [ 0, %entry ], [ %or, %loop ]
130  %idx = getelementptr i32, i32* %haystack, i32 %indvar
131  %ld = load i32, i32* %idx
132  %cmp1 = icmp eq i32 %ld, %needle
133  %zext = zext i1 %cmp1 to i8
134  %or = or i8 %found, %zext
135  %indvar.next = add i32 %indvar, 1
136  %exitcond = icmp eq i32 %indvar.next, 1000
137  br i1 %exitcond, label %exit, label %loop
138
139exit:
140  %tobool = icmp ne i8 %or, 0
141  ret i1 %tobool
142}
143
144; FIXME:
145; This is based on an 'all_of' loop construct.
146; By narrowing the phi and logic op, we simplify away the zext and the final icmp.
147
148define i1 @searchArray2(i32 %hay, i32* %haystack) {
149; CHECK-LABEL: @searchArray2(
150; CHECK-NEXT:  entry:
151; CHECK-NEXT:    br label [[LOOP:%.*]]
152; CHECK:       loop:
153; CHECK-NEXT:    [[INDVAR:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INDVAR_NEXT:%.*]], [[LOOP]] ]
154; CHECK-NEXT:    [[FOUND:%.*]] = phi i8 [ 1, [[ENTRY]] ], [ [[AND:%.*]], [[LOOP]] ]
155; CHECK-NEXT:    [[IDX:%.*]] = getelementptr i32, i32* [[HAYSTACK:%.*]], i64 [[INDVAR]]
156; CHECK-NEXT:    [[LD:%.*]] = load i32, i32* [[IDX]], align 4
157; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[LD]], [[HAY:%.*]]
158; CHECK-NEXT:    [[ZEXT:%.*]] = zext i1 [[CMP1]] to i8
159; CHECK-NEXT:    [[AND]] = and i8 [[FOUND]], [[ZEXT]]
160; CHECK-NEXT:    [[INDVAR_NEXT]] = add i64 [[INDVAR]], 1
161; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[INDVAR_NEXT]], 1000
162; CHECK-NEXT:    br i1 [[EXITCOND]], label [[EXIT:%.*]], label [[LOOP]]
163; CHECK:       exit:
164; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i8 [[AND]], 0
165; CHECK-NEXT:    ret i1 [[TOBOOL]]
166;
167entry:
168  br label %loop
169
170loop:
171  %indvar = phi i64 [ 0, %entry ], [ %indvar.next, %loop ]
172  %found = phi i8 [ 1, %entry ], [ %and, %loop ]
173  %idx = getelementptr i32, i32* %haystack, i64 %indvar
174  %ld = load i32, i32* %idx
175  %cmp1 = icmp eq i32 %ld, %hay
176  %zext = zext i1 %cmp1 to i8
177  %and = and i8 %found, %zext
178  %indvar.next = add i64 %indvar, 1
179  %exitcond = icmp eq i64 %indvar.next, 1000
180  br i1 %exitcond, label %exit, label %loop
181
182exit:
183  %tobool = icmp ne i8 %and, 0
184  ret i1 %tobool
185}
186
187; FIXME:
188; Narrowing should work with an 'xor' and is not limited to bool types.
189
190define i32 @shrinkLogicAndPhi1(i8 %x, i1 %cond) {
191; CHECK-LABEL: @shrinkLogicAndPhi1(
192; CHECK-NEXT:  entry:
193; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF:%.*]], label [[ENDIF:%.*]]
194; CHECK:       if:
195; CHECK-NEXT:    br label [[ENDIF]]
196; CHECK:       endif:
197; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ 21, [[ENTRY:%.*]] ], [ 33, [[IF]] ]
198; CHECK-NEXT:    [[ZEXT:%.*]] = zext i8 [[X:%.*]] to i32
199; CHECK-NEXT:    [[LOGIC:%.*]] = xor i32 [[PHI]], [[ZEXT]]
200; CHECK-NEXT:    ret i32 [[LOGIC]]
201;
202entry:
203  br i1 %cond, label %if, label %endif
204if:
205  br label %endif
206endif:
207  %phi = phi i32 [ 21, %entry], [ 33, %if ]
208  %zext = zext i8 %x to i32
209  %logic = xor i32 %phi, %zext
210  ret i32 %logic
211}
212
213; FIXME:
214; Narrowing should work with an 'xor' and is not limited to bool types.
215; Test that commuting the xor operands does not inhibit optimization.
216
217define i32 @shrinkLogicAndPhi2(i8 %x, i1 %cond) {
218; CHECK-LABEL: @shrinkLogicAndPhi2(
219; CHECK-NEXT:  entry:
220; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF:%.*]], label [[ENDIF:%.*]]
221; CHECK:       if:
222; CHECK-NEXT:    br label [[ENDIF]]
223; CHECK:       endif:
224; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ 21, [[ENTRY:%.*]] ], [ 33, [[IF]] ]
225; CHECK-NEXT:    [[ZEXT:%.*]] = zext i8 [[X:%.*]] to i32
226; CHECK-NEXT:    [[LOGIC:%.*]] = xor i32 [[PHI]], [[ZEXT]]
227; CHECK-NEXT:    ret i32 [[LOGIC]]
228;
229entry:
230  br i1 %cond, label %if, label %endif
231if:
232  br label %endif
233endif:
234  %phi = phi i32 [ 21, %entry], [ 33, %if ]
235  %zext = zext i8 %x to i32
236  %logic = xor i32 %zext, %phi
237  ret i32 %logic
238}
239
240