1;RUN: opt -S -reassociate < %s | FileCheck %s
2
3; ==========================================================================
4;
5;   Xor reassociation general cases
6;
7; ==========================================================================
8
9; (x | c1) ^ (x | c2) => (x & c3) ^ c3, where c3 = c1^c2
10;
11define i32 @xor1(i32 %x) {
12  %or = or i32 %x, 123
13  %or1 = or i32 %x, 456
14  %xor = xor i32 %or, %or1
15  ret i32 %xor
16
17;CHECK-LABEL: @xor1(
18;CHECK: %and.ra = and i32 %x, 435
19;CHECK: %xor = xor i32 %and.ra, 435
20}
21
22; Test rule : (x & c1) ^ (x & c2) = (x & (c1^c2))
23; Real testing case : (x & 123) ^ y ^ (x & 345) => (x & 435) ^ y
24define i32 @xor2(i32 %x, i32 %y) {
25  %and = and i32 %x, 123
26  %xor = xor i32 %and, %y
27  %and1 = and i32 %x, 456
28  %xor2 = xor i32 %xor, %and1
29  ret i32 %xor2
30
31;CHECK-LABEL: @xor2(
32;CHECK: %and.ra = and i32 %x, 435
33;CHECK: %xor2 = xor i32 %and.ra, %y
34}
35
36; Test rule: (x | c1) ^ (x & c2) = (x & c3) ^ c1, where c3 = ~c1 ^ c2
37;  c3 = ~c1 ^ c2
38define i32 @xor3(i32 %x, i32 %y) {
39  %or = or i32 %x, 123
40  %xor = xor i32 %or, %y
41  %and = and i32 %x, 456
42  %xor1 = xor i32 %xor, %and
43  ret i32 %xor1
44
45;CHECK-LABEL: @xor3(
46;CHECK: %and.ra = and i32 %x, -436
47;CHECK: %xor = xor i32 %y, 123
48;CHECK: %xor1 = xor i32 %xor, %and.ra
49}
50
51; Test rule: (x | c1) ^ c2 = (x & ~c1) ^ (c1 ^ c2)
52define i32 @xor4(i32 %x, i32 %y) {
53  %and = and i32 %x, -124
54  %xor = xor i32 %y, 435
55  %xor1 = xor i32 %xor, %and
56  ret i32 %xor1
57; CHECK-LABEL: @xor4(
58; CHECK: %and = and i32 %x, -124
59; CHECK: %xor = xor i32 %y, 435
60; CHECK: %xor1 = xor i32 %xor, %and
61}
62
63; ==========================================================================
64;
65;  Xor reassociation special cases
66;
67; ==========================================================================
68
69; Special case1:
70;  (x | c1) ^ (x & ~c1) = c1
71define i32 @xor_special1(i32 %x, i32 %y) {
72  %or = or i32 %x, 123
73  %xor = xor i32 %or, %y
74  %and = and i32 %x, -124
75  %xor1 = xor i32 %xor, %and
76  ret i32 %xor1
77; CHECK-LABEL: @xor_special1(
78; CHECK: %xor1 = xor i32 %y, 123
79; CHECK: ret i32 %xor1
80}
81
82; Special case1:
83;  (x | c1) ^ (x & c1) = x ^ c1
84define i32 @xor_special2(i32 %x, i32 %y) {
85  %or = or i32 %x, 123
86  %xor = xor i32 %or, %y
87  %and = and i32 %x, 123
88  %xor1 = xor i32 %xor, %and
89  ret i32 %xor1
90; CHECK-LABEL: @xor_special2(
91; CHECK: %xor = xor i32 %y, 123
92; CHECK: %xor1 = xor i32 %xor, %x
93; CHECK: ret i32 %xor1
94}
95
96; (x | c1) ^ (x | c1) => 0
97define i32 @xor_special3(i32 %x) {
98  %or = or i32 %x, 123
99  %or1 = or i32 %x, 123
100  %xor = xor i32 %or, %or1
101  ret i32 %xor
102;CHECK-LABEL: @xor_special3(
103;CHECK: ret i32 0
104}
105
106; (x & c1) ^ (x & c1) => 0
107define i32 @xor_special4(i32 %x) {
108  %or = and i32 %x, 123
109  %or1 = and i32 123, %x
110  %xor = xor i32 %or, %or1
111  ret i32 %xor
112;CHECK-LABEL: @xor_special4(
113;CHECK: ret i32 0
114}
115
116; ==========================================================================
117;
118;  Xor reassociation curtail code size
119;
120; ==========================================================================
121
122; (x | c1) ^ (x | c2) => (x & c3) ^ c3
123; is enabled if one of operands has multiple uses
124;
125define i32 @xor_ra_size1(i32 %x) {
126  %or = or i32 %x, 123
127  %or1 = or i32 %x, 456
128  %xor = xor i32 %or, %or1
129
130  %add = add i32 %xor, %or
131  ret i32 %add
132;CHECK-LABEL: @xor_ra_size1(
133;CHECK: %xor = xor i32 %and.ra, 435
134}
135
136; (x | c1) ^ (x | c2) => (x & c3) ^ c3
137; is disenabled if bothf operands has multiple uses.
138;
139define i32 @xor_ra_size2(i32 %x) {
140  %or = or i32 %x, 123
141  %or1 = or i32 %x, 456
142  %xor = xor i32 %or, %or1
143
144  %add = add i32 %xor, %or
145  %add2 = add i32 %add, %or1
146  ret i32 %add2
147
148;CHECK-LABEL: @xor_ra_size2(
149;CHECK: %or1 = or i32 %x, 456
150;CHECK: %xor = xor i32 %or, %or1
151}
152
153
154; ==========================================================================
155;
156;  Xor reassociation bugs
157;
158; ==========================================================================
159
160@xor_bug1_data = external global <{}>, align 4
161define void @xor_bug1() {
162  %1 = ptrtoint i32* undef to i64
163  %2 = xor i64 %1, ptrtoint (<{}>* @xor_bug1_data to i64)
164  %3 = and i64 undef, %2
165  ret void
166}
167
168; The bug was that when the compiler optimize "(x | c1)" ^ "(x & c2)", it may
169; swap the two xor-subexpressions if they are not in canoninical order; however,
170; when optimizer swaps two sub-expressions, if forgot to swap the cached value
171; of c1 and c2 accordingly, hence cause the problem.
172;
173define i32 @xor_bug2(i32, i32, i32, i32) {
174  %5 = mul i32 %0, 123
175  %6 = add i32 %2, 24
176  %7 = add i32 %1, 8
177  %8 = and i32 %1, 3456789
178  %9 = or i32 %8,  4567890
179  %10 = and i32 %1, 543210987
180  %11 = or i32 %1, 891034567
181  %12 = and i32 %2, 255
182  %13 = xor i32 %9, %10
183  %14 = xor i32 %11, %13
184  %15 = xor i32 %5, %14
185  %16 = and i32 %3, 255
186  %17 = xor i32 %16, 42
187  %18 = add i32 %6, %7
188  %19 = add i32 %18, %12
189  %20 = add i32 %19, %15
190  ret i32 %20
191;CHECK-LABEL: @xor_bug2(
192;CHECK: xor i32 %5, 891034567
193}
194