996
|
1 ;
|
|
2 ; NAME
|
|
3 ; idiotism.oil -- optimizer idioms for C-INTERCAL
|
|
4 ;
|
|
5 ; LICENSE TERMS
|
|
6 ; Copyright (C) 2007 Alex Smith
|
|
7 ;
|
|
8 ; This program is free software; you can redistribute it and/or modify
|
|
9 ; it under the terms of the GNU General Public License as published by
|
|
10 ; the Free Software Foundation; either version 2 of the License, or
|
|
11 ; (at your option) any later version.
|
|
12 ;
|
|
13 ; This program is distributed in the hope that it will be useful,
|
|
14 ; but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
15 ; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
16 ; GNU General Public License for more details.
|
|
17 ;
|
|
18 ; You should have received a copy of the GNU General Public License
|
|
19 ; along with this program; if not, write to the Free Software
|
|
20 ; Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
|
|
21 ;
|
|
22
|
|
23 ; Optimizer Idiom Language input file for C-INTERCAL
|
|
24
|
|
25 ; See the appendix "Optimizer Idiom Language" in the Revamped manual
|
|
26 ; for information about the format of this file.
|
|
27
|
|
28 ; Some useful constants:
|
|
29 ; 0x55555555 1431655765
|
|
30 ; 0xAAAAAAAA 2863311530
|
|
31 ; 0x0000FFFF 65535
|
|
32 ; 0xFFFF0000 4294901760
|
|
33 ; 0xFFFFFFFF 4294967295
|
|
34
|
|
35 ; Constant folding
|
|
36 [minglefold]
|
|
37 (#{1}1$#{1}2)->(#{mingle(x1,x2)}0)
|
|
38 [selectfold]
|
|
39 (#{1}1~#{1}2)->(#{iselect(x1,x2)}0)
|
|
40 [and32fold]
|
|
41 (&32 #{1}1)->(#{and32(x1)}0)
|
|
42 [or32fold]
|
|
43 (V32 #{1}1)->(#{or32(x1)}0)
|
|
44 [xor32fold]
|
|
45 (?32 #{1}1)->(#{xor32(x1)}0)
|
|
46 [and16fold]
|
|
47 (&16 #{1}1)->(#{and16(x1)}0)
|
|
48 [or16fold]
|
|
49 (V16 #{1}1)->(#{or16(x1)}0)
|
|
50 [xor16fold]
|
|
51 (?16 #{1}1)->(#{xor16(x1)}0)
|
|
52 ; C operations can, and should, be folded too
|
|
53 [cfold]
|
|
54 (#{1}1 & #{1}2)->(#{x1 & x2}0)
|
|
55 (#{1}1 | #{1}2)->(#{x1 | x2}0)
|
|
56 (#{1}1 ^ #{1}2)->(#{x1 ^ x2}0)
|
|
57 (#{1}1 + #{1}2)->(#{x1 + x2}0)
|
|
58 (#{1}1 - #{1}2)->(#{x1 - x2}0)
|
|
59 (#{1}1 * #{1}2)->(#{x1 * x2}0)
|
|
60 (#{1}1 / #{1}2)->(#{x1 / x2}0)
|
|
61 (#{1}1 % #{1}2)->(#{x1 % x2}0)
|
|
62 (#{1}1 > #{1}2)->(#{x1 > x2}0)
|
|
63 (#{1}1 < #{1}2)->(#{x1 < x2}0)
|
|
64 (#{1}1 >> #{1}2)->(#{x1 >> x2}0)
|
|
65 (#{1}1 << #{1}2)->(#{x1 << x2}0)
|
|
66 (#{1}1 == #{1}2)->(#{x1 == x2}0)
|
|
67 (#{1}1 != #{1}2)->(#{x1 != x2}0)
|
|
68
|
|
69 ; Reducing constants inside a C or operation can help to recognize idioms
|
|
70 [cfoldintoorinand]
|
|
71 (((_1) | #{1}2) & #{1}3)->(((_1) | #{x2 & x3}0) & _3)
|
|
72
|
|
73 ; Binary bitwise optimizations
|
|
74 [cbinand]
|
|
75 ((&32(_{!(c&4294901760LU)}1$_{!(c&4294901760LU)}2))~
|
|
76 #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3
|
|
77 )->((_1 & _2) & #{iselect(x3,1431655765LU)}0)
|
|
78 [cbinor]
|
|
79 ((V32(_{!(c&4294901760LU)}1$_{!(c&4294901760LU)}2))~
|
|
80 #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3
|
|
81 )->((_1 | _2) & #{iselect(x3,1431655765LU)}0)
|
|
82 [cbinxor]
|
|
83 ((?32(_{!(c&4294901760LU)}1$_{!(c&4294901760LU)}2))~
|
|
84 #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3
|
|
85 )->((_1 ^ _2) & #{iselect(x3,1431655765LU)}0)
|
|
86 ; Sometimes, an expanded output is wanted, optimizations happen in the wrong
|
|
87 ; order, and we end up with & rather than ~ on the previous idiom. Correct
|
|
88 ; such situations now.
|
|
89 [cbinandnoselect]
|
|
90 ((&32(_{!(c&4294901760LU)}1$_{!(c&4294901760LU)}2))&
|
|
91 #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3
|
|
92 )->(#0 $ ((_1 & _2) & #{iselect(x3,1431655765LU)}0))
|
|
93 [cbinornoselect]
|
|
94 ((V32(_{!(c&4294901760LU)}1$_{!(c&4294901760LU)}2))&
|
|
95 #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3
|
|
96 )->(#0 $ ((_1 | _2) & #{iselect(x3,1431655765LU)}0))
|
|
97 [cbinxornoselect]
|
|
98 ((?32(_{!(c&4294901760LU)}1$_{!(c&4294901760LU)}2))&
|
|
99 #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3
|
|
100 )->(#0 $ ((_1 ^ _2) & #{iselect(x3,1431655765LU)}0))
|
|
101 ; Sometimes, there isn't even a mingle...
|
|
102 [cbinandnomingle]
|
|
103 ((&32(_{!(c&2863311530LU)}1|_{!(c&1431655765LU)}2))~
|
|
104 #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3
|
|
105 )->(((_2 >> #1) & _1) ~ _3)
|
|
106 ((&32(_{!(c&1431655765LU)}2|_{!(c&2863311530LU)}1))~
|
|
107 #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3
|
|
108 )->(((_2 >> #1) & _1) ~ _3)
|
|
109 ((&32(_{!(c&2863311530LU)}1|_{!(c&1431655765LU)}2))&
|
|
110 #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3
|
|
111 )->(((_2 >> #1) & _1) & _3)
|
|
112 ((&32(_{!(c&1431655765LU)}2|_{!(c&2863311530LU)}1))&
|
|
113 #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3
|
|
114 )->(((_2 >> #1) & _1) & _3)
|
|
115 [cbinornomingle]
|
|
116 ((V32(_{!(c&2863311530LU)}1|_{!(c&1431655765LU)}2))~
|
|
117 #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3
|
|
118 )->(((_2 >> #1) | _1) ~ _3)
|
|
119 ((V32(_{!(c&1431655765LU)}2|_{!(c&2863311530LU)}1))~
|
|
120 #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3
|
|
121 )->(((_2 >> #1) | _1) ~ _3)
|
|
122 ((V32(_{!(c&2863311530LU)}1|_{!(c&1431655765LU)}2))&
|
|
123 #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3
|
|
124 )->(((_2 >> #1) | _1) & _3)
|
|
125 ((V32(_{!(c&1431655765LU)}2|_{!(c&2863311530LU)}1))&
|
|
126 #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3
|
|
127 )->(((_2 >> #1) | _1) & _3)
|
|
128 [cbinxornomingle]
|
|
129 ((?32(_{!(c&2863311530LU)}1|_{!(c&1431655765LU)}2))~
|
|
130 #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3
|
|
131 )->(((_2 >> #1) ^ _1) ~ _3)
|
|
132 ((?32(_{!(c&1431655765LU)}2|_{!(c&2863311530LU)}1))~
|
|
133 #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3
|
|
134 )->(((_2 >> #1) ^ _1) ~ _3)
|
|
135 ((?32(_{!(c&2863311530LU)}1|_{!(c&1431655765LU)}2))&
|
|
136 #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3
|
|
137 )->(((_2 >> #1) ^ _1) & _3)
|
|
138 ((?32(_{!(c&1431655765LU)}2|_{!(c&2863311530LU)}1))&
|
|
139 #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3
|
|
140 )->(((_2 >> #1) ^ _1) & _3)
|
|
141
|
|
142 ; Bitwise complements. (The INTERCAL which ultimately leads to cases 3 and 4
|
|
143 ; is not the most efficient way to do this, by the way.)
|
|
144 [cnot1]
|
|
145 (#65535 ^ .{!(c&4294901760LU)}1)->(~16 .1)
|
|
146 [cnot2]
|
|
147 (.{!(c&4294901760LU)}1 ^ #65535)->(~16 .1)
|
|
148 [cnot3]
|
|
149 (#4294967295 ^ :1)->(~32 :1)
|
|
150 [cnot4]
|
|
151 (:1 ^ #4294967295)->(~32 :1)
|
|
152
|
|
153 ; bitwise logical equivalence
|
|
154 [cxorand16]
|
|
155 ((.1 ^ _2) & _2)->((~16 .1) & _2)
|
|
156 ((_2 ^ .1) & _2)->((~16 .1) & _2)
|
|
157 ((.1 & _2) ^ _2)->((~16 .1) & _2)
|
|
158 ((_2 & .1) ^ _2)->((~16 .1) & _2)
|
|
159 (_2 ^ (.1 & _2))->((~16 .1) & _2)
|
|
160 (_2 ^ (_2 & .1))->((~16 .1) & _2)
|
|
161 (_2 & (.1 ^ _2))->((~16 .1) & _2)
|
|
162 (_2 & (_2 ^ .1))->((~16 .1) & _2)
|
|
163 [cxorand32]
|
|
164 ((:1 ^ _2) & _2)->((~32 _1) & _2)
|
|
165 ((_2 ^ :1) & _2)->((~32 _1) & _2)
|
|
166 ((:1 & _2) ^ _2)->((~32 _1) & _2)
|
|
167 ((_2 & :1) ^ _2)->((~32 _1) & _2)
|
|
168 (_2 ^ (:1 & _2))->((~32 _1) & _2)
|
|
169 (_2 ^ (_2 & :1))->((~32 _1) & _2)
|
|
170 (_2 & (:1 ^ _2))->((~32 _1) & _2)
|
|
171 (_2 & (_2 ^ :1))->((~32 _1) & _2)
|
|
172
|
|
173 ; Special cases of select
|
|
174
|
|
175 ; Selecting the rightmost bits of a number
|
|
176 [xselpow2m1]
|
|
177 (_1 ~ #{x==xselx(x)}2)->(_1 & _2)
|
|
178 ; Selecting one bit from a number
|
|
179 [xselpow2]
|
|
180 (_1 ~ #{xselx(x)==1}2)->(!(!(_1 & _2)))
|
|
181 ; Selecting a number against itself and then selecting 1 from that
|
|
182 [xselxsel1]
|
|
183 ((_1~_1)~#1)->(!(!_1))
|
|
184 ((_1~_1))->(!(!_1))
|
|
185 (#1&(_1~_1))->(!(!_1))
|
|
186 ((_1~_1)&_{c==1}2)->(_1 && _2)
|
|
187 (_{c==1}2&(_1~_1))->(_1 && _2)
|
|
188 ; Selecting a number from a constant that's just below a power of 2
|
|
189 [pow2m1selx]
|
|
190 ((#{x==xselx(x)}1 ~ _2) ~ #1)->(!(!(_1 & _2)))
|
|
191 ; Boolean-negating a select
|
|
192 [notselect]
|
|
193 (!(_1~_2))->(!(_1&_2))
|
|
194
|
|
195 ; Sometimes select and mingle cancel each other out
|
|
196 [selectmingle1]
|
|
197 ((_1~#2863311530)$_2)->((_1�)|(#0$_2))
|
|
198 [selectmingle2]
|
|
199 (_1$(_2~#1431655765))->((_1$#0)|(_2�))
|
|
200 [selectmingle3]
|
|
201 ((_1~#1431655765)$_2)->(((_1�)<<#1)|(#0$_2))
|
|
202 [selectmingle4]
|
|
203 (_1$(_2~#2863311530))->(((_2�)>>#1)|(_1$#0))
|
|
204 [selectmingle5]
|
|
205 ((_{!(c&4294901760UL)}1$_{!(c&4294901760UL)}2)~#3579139412)
|
|
206 ->((_1耀)|(_2>>#1))
|
|
207
|
|
208 ; special cases of V16/?16; the top bit was 0, so becomes equal to the
|
|
209 ; bottom bit
|
|
210 [or16and]
|
|
211 ((V16 _{!(c&4294934528UL)}1)耀)->((_1)<<#15)
|
|
212 [xor16and]
|
|
213 ((?16 _{!(c&4294934528UL)}1)耀)->((_1)<<#15)
|
|
214
|
|
215 ; Shifts
|
|
216
|
|
217 ; A helper in calculating 32-bit shifts; this is a shift on half the bits of
|
|
218 ; a 32-bit number.
|
|
219 [lshift32half]
|
|
220 (#0$((_1~#715827882)<<#1))->((_1�)<<#1)
|
|
221 ; Rightshift some of the bits
|
|
222 [rshift]
|
|
223 <#1-#31
|
|
224 (_1~#{xselx(x)<<r==x&&x}2)->((_1&_2)>>#{r}0)
|
|
225 >
|
|
226 ; General 16-bit leftshifts
|
|
227 ;
|
|
228 ; Large left-shifts can be written in an optimized way using knowledge of the
|
|
229 ; rightmost bits to shift more than one bit at a time.
|
|
230 ; If the rightmost few bits of a number are known to be 0, it can be mingled
|
|
231 ; with 0, and then selected with a number which has many 0s to do a leftshift.
|
|
232 ; Here, if none of the bits marked l are set this is a right-shift by 3, and
|
|
233 ; for each bit set, the shift goes 1 leftwards.
|
|
234 ; (xxxxxxxxxxxxxttt $ 000000000000uuuu) ~ (h0h0h0h0h0h0h0h0h0h0h0h01lllllll)
|
|
235 ; x0x0x0x0x0x0x0x0x0x0x0x0xutututu
|
|
236 ; h0h0h0h0h0h0h0h0h0h0h0h01lllllll
|
|
237 ; There's three cases here for each possible width for the ts, including one
|
|
238 ; which has them as zeros and two which have them higher.
|
|
239 [lshift16]
|
|
240 <#0-#14
|
|
241 ((_{c<=65535&&!(c&((1LU<<r)-1LU))}1$
|
|
242 #{!(x&(4294967294LU<<r))}2)~#{!(x&(1431655765LU<<(r*2+2)))}3)
|
|
243 ->((((_1>>#{r}0)~#{iselect(x3>>(r*2+1),1431655765LU)}0)
|
|
244 <<#{setbitcount(x3&((2LU<<(r*2))-1))}0)|#{iselect(mingle(0,x2),x3)}0)
|
|
245 (((_{c<=65535&&!(c&((1LU<<r)-1LU))}1|#{x<=65535&&!(c&~((1LU<<r)-1LU))}4)$
|
|
246 #{!(x&(4294967294LU<<r))}2)~#{!(x&(1431655765LU<<(r*2+2)))}3)
|
|
247 ->((((_1>>#{r}0)~#{iselect(x3>>(r*2+1),1431655765LU)}0)
|
|
248 <<#{setbitcount(x3&((2LU<<(r*2))-1))}0)|#{iselect(mingle(x4,x2),x3)}0)
|
|
249 (((#{x<=65535&&!(c&~((1LU<<r)-1LU))}4|_{c<=65535&&!(c&((1LU<<r)-1LU))}1)$
|
|
250 #{!(x&(4294967294LU<<r))}2)~#{!(x&(1431655765LU<<(r*2+2)))}3)
|
|
251 ->((((_1>>#{r}0)~#{iselect(x3>>(r*2+1),1431655765LU)}0)
|
|
252 <<#{setbitcount(x3&((2LU<<(r*2))-1))}0)|#{iselect(mingle(x4,x2),x3)}0)
|
|
253 >
|
|
254
|
|
255
|
|
256 ; 32-bit leftshift by 1; there are 8 ways to write this.
|
|
257 [lshift32by1]
|
|
258 (((_1�)<<#1)|((_1�)<<#1))->((_1�)<<#1)
|
|
259 (((#1431655765&_1)<<#1)|((_1�)<<#1))->((_1�)<<#1)
|
|
260 (((_1�)<<#1)|((#715827882&_1)<<#1))->((_1�)<<#1)
|
|
261 (((#1431655765&_1)<<#1)|((#715827882&_1)<<#1))->((_1�)<<#1)
|
|
262 (((_1�)<<#1)|((_1�)<<#1))->((_1�)<<#1)
|
|
263 (((_1�)<<#1)|((#1431655765&_1)<<#1))->((_1�)<<#1)
|
|
264 (((#715827882&_1)<<#1)|((_1�)<<#1))->((_1�)<<#1)
|
|
265 (((#715827882&_1)<<#1)|((#1431655765&_1)<<#1))->((_1�)<<#1)
|
|
266
|
|
267 ; a weird part of a leftshift
|
|
268 [lshift32half]
|
|
269 (#0$((:1�)~#715827883))->((:1�)<<#1)
|
|
270
|
|
271 ; Move rshift, AND out of neg
|
|
272 [rshiftoutofneg]
|
|
273 (~16 (.1 >> #{1}2))->(((~16 .1) >> _2) | #32768)
|
|
274 (~32 (:1 >> #{1}2))->(((~32 :1) >> _2) | #2147483648)
|
|
275 [andoutofneg]
|
|
276 (~16 (.1 & #{1}2))->(((~16 .1) & _2) | #{(~x2)&65535}0)
|
|
277 (~32 (:1 & #{1}2))->(((~32 :1) & _2) | #{~x2}0)
|
|
278
|
|
279 ; Move AND inside shifts, and OR and XOR outside shifts
|
|
280 [andintoshift]
|
|
281 ((_1 << #{1}2) & #{1}3)->((_1 & #{x3>>x2}0) << _2)
|
|
282 ((_1 >> #{1}2) & #{1}3)->((_1 & #{x3<<x2}0) >> _2)
|
|
283 [oroutofshift]
|
|
284 ((_1 | #{1}2) << #{1}3)->((_1 << _3) | #{x2<<x3}0)
|
|
285 ((_1 | #{1}2) >> #{1}3)->((_1 >> _3) | #{x2>>x3}0)
|
|
286 [xoroutofshift]
|
|
287 ((_1 ^ #{1}2) << #{1}3)->((_1 << _3) ^ #{x2<<x3}0)
|
|
288 ((_1 ^ #{1}2) >> #{1}3)->((_1 >> _3) ^ #{x2>>x3}0)
|
|
289 ; Larger leftshifts can be created by combining smaller ones, although there
|
|
290 ; are shortcuts that can be used and this idiom only works if they haven't
|
|
291 ; been. Also, idioms later on can create shifts that cancel each other out, so
|
|
292 ; the code for cancelling them is here.
|
|
293 [combinellshift]
|
|
294 ((_1 << #{1}2) << #{1}3)->(_1 << #{x2+x3}0)
|
|
295 [combinelrshift]
|
|
296 ((_1 << #{1}2) >> #{x>x2}3)->(_1 >> #{x3-x2}0)
|
|
297 ((_1 << #{1}2) >> #{x==x2}3)->(_1)
|
|
298 ((_1 << #{1}2) >> #{x<x2}3)->(_1 << #{x2-x3}0)
|
|
299 [combinerlshift]
|
|
300 ((_1 >> #{1}2) << #{x>x2}3)->(_1 << #{x3-x2}0)
|
|
301 ((_1 >> #{1}2) << #{x==x2}3)->(_1)
|
|
302 ((_1 >> #{1}2) << #{x<x2}3)->(_1 >> #{x2-x3}0)
|
|
303 [combinerrshift]
|
|
304 ((_1 >> #{1}2) >> #{1}3)->(_1 >> #{x2+x3}0)
|
|
305 [nullshift]
|
|
306 (_1 >> #0)->(_1)
|
|
307 (_1 << #0)->(_1)
|
|
308
|
|
309 ; INTERCAL logical values are 1 and 2.
|
|
310 [xorto1or2]
|
|
311 ((?32(_{!(c&4294901760LU)}1$#1)))->((_1)+#1)
|
|
312 ((?32(_{!(c&4294901760LU)}1$#2)))->(#2-(_1))
|
|
313
|
|
314 ; Removing, combining and weakening unneeded C_ANDs
|
|
315 [unneededand]
|
|
316 (_1&#{!(c1&~x)}0)->(_1)
|
|
317 (#{!(c1&~x)}0&_1)->(_1)
|
|
318 [combineand]
|
|
319 ((_1&#{1}2)&#{1}3)->(_1&#{x2&x3}0)
|
|
320 ((#{1}2&_1)&#{1}3)->(_1&#{x2&x3}0)
|
|
321 (#{1}3&(_1&#{1}2))->(_1&#{x2&x3}0)
|
|
322 (#{1}3&(#{1}2&_1))->(_1&#{x2&x3}0)
|
|
323 [weakenand]
|
|
324 (_1&#{(~c1)&x}2)->(_1&#{c1&x2}0)
|
|
325 (#{(~c1)&x}2&_1)->(_1&#{c1&x2}0)
|
|
326
|
|
327 ; 32-bit complements
|
|
328
|
|
329 ; Complement odd bits, zero even bits
|
|
330 [com1z0]
|
|
331 (((?32(_1|#1431655765))�)<<#1)->((_1�)^#2863311530)
|
|
332 (((?32(#1431655765|_1))�)<<#1)->((_1�)^#2863311530)
|
|
333 ((#1431655765&(?32(_1|#1431655765)))<<#1)->((_1�)^#2863311530)
|
|
334 ((#1431655765&(?32(#1431655765|_1)))<<#1)->((_1�)^#2863311530)
|
|
335 ; Complement even bits, zero odd bits
|
|
336 [com0z1]
|
|
337 ((?32(((_1�)<<#1)|#1431655765))�)
|
|
338 ->((_1�)^#1431655765)
|
|
339 ((?32(((#1431655765&_1)<<#1)|#1431655765))�)
|
|
340 ->((_1�)^#1431655765)
|
|
341 ((?32(#1431655765|((_1�)<<#1)))�)
|
|
342 ->((_1�)^#1431655765)
|
|
343 ((?32(#1431655765|((#1431655765&_1)<<#1)))�)
|
|
344 ->((_1�)^#1431655765)
|
|
345 (#1431655765&(?32(((_1�)<<#1)|#1431655765)))
|
|
346 ->((_1�)^#1431655765)
|
|
347 (#1431655765&(?32(((#1431655765&_1)<<#1)|#1431655765)))
|
|
348 ->((_1�)^#1431655765)
|
|
349 (#1431655765&(?32(#1431655765|((_1�)<<#1))))
|
|
350 ->((_1�)^#1431655765)
|
|
351 (#1431655765&(?32(#1431655765|((#1431655765&_1)<<#1))))
|
|
352 ->((_1�)^#1431655765)
|
|
353 ; 32-bit complements, in full
|
|
354 [cnot5]
|
|
355 (((:1&#{1}2)^#{x==x2}0)|((:1&#{(x^x2)==4294967295LU}3)^#{x==x3}0))->(~32 :1)
|
|
356
|
|
357 ; Distributive laws
|
|
358
|
|
359 ; Several of these laws go towards helping finish off 32-bit C binary logical
|
|
360 ; operations, but are useful in other places as well (especially distributions
|
|
361 ; involving shifts).
|
|
362 [distribll]
|
|
363 ((_1&_3)&(_2&_3))->((_1&_2)&_3)
|
|
364 ((_1|_3)&(_2|_3))->((_1&_2)|_3)
|
|
365 ((_1&_3)|(_2&_3))->((_1|_2)&_3)
|
|
366 ((_1|_3)|(_2|_3))->((_1|_2)|_3)
|
|
367 ((_1&_3)^(_2&_3))->((_1^_2)&_3)
|
|
368 ((_1<<_3)&(_2<<_3))->((_1&_2)<<_3)
|
|
369 ((_1<<_3)|(_2<<_3))->((_1|_2)<<_3)
|
|
370 ((_1<<_3)^(_2<<_3))->((_1^_2)<<_3)
|
|
371 ((_1>>_3)&(_2>>_3))->((_1&_2)>>_3)
|
|
372 ((_1>>_3)|(_2>>_3))->((_1|_2)>>_3)
|
|
373 ((_1>>_3)^(_2>>_3))->((_1^_2)>>_3)
|
|
374 [distribrl]
|
|
375 ((_3&_1)&(_2&_3))->((_1&_2)&_3)
|
|
376 ((_3|_1)&(_2|_3))->((_1&_2)|_3)
|
|
377 ((_3&_1)|(_2&_3))->((_1|_2)&_3)
|
|
378 ((_3|_1)|(_2|_3))->((_1|_2)|_3)
|
|
379 ((_3&_1)^(_2&_3))->((_1^_2)&_3)
|
|
380 [distriblr]
|
|
381 ((_1&_3)&(_3&_2))->((_1&_2)&_3)
|
|
382 ((_1|_3)&(_3|_2))->((_1&_2)|_3)
|
|
383 ((_1&_3)|(_3&_2))->((_1|_2)&_3)
|
|
384 ((_1|_3)|(_3|_2))->((_1|_2)|_3)
|
|
385 ((_1&_3)^(_3&_2))->((_1^_2)&_3)
|
|
386 [distribrr]
|
|
387 ((_3&_1)&(_3&_2))->((_1&_2)&_3)
|
|
388 ((_3|_1)&(_3|_2))->((_1&_2)|_3)
|
|
389 ((_3&_1)|(_3&_2))->((_1|_2)&_3)
|
|
390 ((_3|_1)|(_3|_2))->((_1|_2)|_3)
|
|
391 ((_3&_1)^(_3&_2))->((_1^_2)&_3)
|
|
392 [distribunary]
|
|
393 ((!_1)&(!_2))->(!(_1|_2))
|
|
394
|
|
395 ; 32-bit C binary logical operations
|
|
396
|
|
397 ; Strangely enough, these can be done for the most part with the combined
|
|
398 ; effect of many small optimizations (of course, that's the best way to do it).
|
|
399 ; The only potential problem is that the distributive law isn't quite general
|
|
400 ; enough for some cases involving constants, and for some cases where one side
|
|
401 ; or the other is known to have no set evenbits or no set oddbits.
|
|
402 ; Some generalised versions of the distributive law are needed here.
|
|
403 ; Unfortunately, there are lots of binary operators here that need to be
|
|
404 ; written both ways round. The 96 cases that follow, combined with weakenand,
|
|
405 ; should be enough for all but the most pathological cases.
|
|
406 [distribhalfxoroveror1]
|
|
407 (((_1 ^ _2) & _3) | (_1 & _{(c&c3)==0}4))->((_1 ^ _2) & (_3 | _4))
|
|
408 ((_1 & _{(c&c3)==0}4) | ((_1 ^ _2) & _3))->((_1 ^ _2) & (_3 | _4))
|
|
409 (((_1 ^ _2) & _3) | (_{(c&c3)==0}4 & _1))->((_1 ^ _2) & (_3 | _4))
|
|
410 ((_{(c&c3)==0}4 & _1) | ((_1 ^ _2) & _3))->((_1 ^ _2) & (_3 | _4))
|
|
411 ((_3 & (_1 ^ _2)) | (_1 & _{(c&c3)==0}4))->((_1 ^ _2) & (_3 | _4))
|
|
412 ((_1 & _{(c&c3)==0}4) | (_3 & (_1 ^ _2)))->((_1 ^ _2) & (_3 | _4))
|
|
413 ((_3 & (_1 ^ _2)) | (_{(c&c3)==0}4 & _1))->((_1 ^ _2) & (_3 | _4))
|
|
414 ((_{(c&c3)==0}4 & _1) | (_3 & (_1 ^ _2)))->((_1 ^ _2) & (_3 | _4))
|
|
415 (((_2 ^ _1) & _3) | (_1 & _{(c&c3)==0}4))->((_1 ^ _2) & (_3 | _4))
|
|
416 ((_1 & _{(c&c3)==0}4) | ((_2 ^ _1) & _3))->((_1 ^ _2) & (_3 | _4))
|
|
417 (((_2 ^ _1) & _3) | (_{(c&c3)==0}4 & _1))->((_1 ^ _2) & (_3 | _4))
|
|
418 ((_{(c&c3)==0}4 & _1) | ((_2 ^ _1) & _3))->((_1 ^ _2) & (_3 | _4))
|
|
419 ((_3 & (_2 ^ _1)) | (_1 & _{(c&c3)==0}4))->((_1 ^ _2) & (_3 | _4))
|
|
420 ((_1 & _{(c&c3)==0}4) | (_3 & (_2 ^ _1)))->((_1 ^ _2) & (_3 | _4))
|
|
421 ((_3 & (_2 ^ _1)) | (_{(c&c3)==0}4 & _1))->((_1 ^ _2) & (_3 | _4))
|
|
422 ((_{(c&c3)==0}4 & _1) | (_3 & (_2 ^ _1)))->((_1 ^ _2) & (_3 | _4))
|
|
423 [distribhalfxoroveror2]
|
|
424 (((_1 & _3) ^ _{(c&c3)==c}2) | (_1 & _{(c&c3)==0}4))->((_1 ^ _2) & (_3 | _4))
|
|
425 ((_1 & _{(c&c3)==0}4) | ((_1 & _3) ^ _{(c&c3)==c}2))->((_1 ^ _2) & (_3 | _4))
|
|
426 (((_1 & _3) ^ _{(c&c3)==c}2) | (_{(c&c3)==0}4 & _1))->((_1 ^ _2) & (_3 | _4))
|
|
427 ((_{(c&c3)==0}4 & _1) | ((_1 & _3) ^ _{(c&c3)==c}2))->((_1 ^ _2) & (_3 | _4))
|
|
428 ((_{(c&c3)==c}2 ^ (_1 & _3)) | (_1 & _{(c&c3)==0}4))->((_1 ^ _2) & (_3 | _4))
|
|
429 ((_1 & _{(c&c3)==0}4) | (_{(c&c3)==c}2 ^ (_1 & _3)))->((_1 ^ _2) & (_3 | _4))
|
|
430 ((_{(c&c3)==c}2 ^ (_1 & _3)) | (_{(c&c3)==0}4 & _1))->((_1 ^ _2) & (_3 | _4))
|
|
431 ((_{(c&c3)==0}4 & _1) | (_{(c&c3)==c}2 ^ (_1 & _3)))->((_1 ^ _2) & (_3 | _4))
|
|
432 (((_3 & _1) ^ _{(c&c3)==c}2) | (_1 & _{(c&c3)==0}4))->((_1 ^ _2) & (_3 | _4))
|
|
433 ((_1 & _{(c&c3)==0}4) | ((_3 & _1) ^ _{(c&c3)==c}2))->((_1 ^ _2) & (_3 | _4))
|
|
434 (((_3 & _1) ^ _{(c&c3)==c}2) | (_{(c&c3)==0}4 & _1))->((_1 ^ _2) & (_3 | _4))
|
|
435 ((_{(c&c3)==0}4 & _1) | ((_3 & _1) ^ _{(c&c3)==c}2))->((_1 ^ _2) & (_3 | _4))
|
|
436 ((_{(c&c3)==c}2 ^ (_3 & _1)) | (_1 & _{(c&c3)==0}4))->((_1 ^ _2) & (_3 | _4))
|
|
437 ((_1 & _{(c&c3)==0}4) | (_{(c&c3)==c}2 ^ (_3 & _1)))->((_1 ^ _2) & (_3 | _4))
|
|
438 ((_{(c&c3)==c}2 ^ (_3 & _1)) | (_{(c&c3)==0}4 & _1))->((_1 ^ _2) & (_3 | _4))
|
|
439 ((_{(c&c3)==0}4 & _1) | (_{(c&c3)==c}2 ^ (_3 & _1)))->((_1 ^ _2) & (_3 | _4))
|
|
440 [distribhalforoveror1]
|
|
441 (((_1 | _2) & _3) | (_1 & _{(c&c3)==0}4))->((_1 | _2) & (_3 | _4))
|
|
442 ((_1 & _{(c&c3)==0}4) | ((_1 | _2) & _3))->((_1 | _2) & (_3 | _4))
|
|
443 (((_1 | _2) & _3) | (_{(c&c3)==0}4 & _1))->((_1 | _2) & (_3 | _4))
|
|
444 ((_{(c&c3)==0}4 & _1) | ((_1 | _2) & _3))->((_1 | _2) & (_3 | _4))
|
|
445 ((_3 & (_1 | _2)) | (_1 & _{(c&c3)==0}4))->((_1 | _2) & (_3 | _4))
|
|
446 ((_1 & _{(c&c3)==0}4) | (_3 & (_1 | _2)))->((_1 | _2) & (_3 | _4))
|
|
447 ((_3 & (_1 | _2)) | (_{(c&c3)==0}4 & _1))->((_1 | _2) & (_3 | _4))
|
|
448 ((_{(c&c3)==0}4 & _1) | (_3 & (_1 | _2)))->((_1 | _2) & (_3 | _4))
|
|
449 (((_2 | _1) & _3) | (_1 & _{(c&c3)==0}4))->((_1 | _2) & (_3 | _4))
|
|
450 ((_1 & _{(c&c3)==0}4) | ((_2 | _1) & _3))->((_1 | _2) & (_3 | _4))
|
|
451 (((_2 | _1) & _3) | (_{(c&c3)==0}4 & _1))->((_1 | _2) & (_3 | _4))
|
|
452 ((_{(c&c3)==0}4 & _1) | ((_2 | _1) & _3))->((_1 | _2) & (_3 | _4))
|
|
453 ((_3 & (_2 | _1)) | (_1 & _{(c&c3)==0}4))->((_1 | _2) & (_3 | _4))
|
|
454 ((_1 & _{(c&c3)==0}4) | (_3 & (_2 | _1)))->((_1 | _2) & (_3 | _4))
|
|
455 ((_3 & (_2 | _1)) | (_{(c&c3)==0}4 & _1))->((_1 | _2) & (_3 | _4))
|
|
456 ((_{(c&c3)==0}4 & _1) | (_3 & (_2 | _1)))->((_1 | _2) & (_3 | _4))
|
|
457 [distribhalforoveror2]
|
|
458 (((_1 & _3) | _{(c&c3)==c}2) | (_1 & _{(c&c3)==0}4))->((_1 | _2) & (_3 | _4))
|
|
459 ((_1 & _{(c&c3)==0}4) | ((_1 & _3) | _{(c&c3)==c}2))->((_1 | _2) & (_3 | _4))
|
|
460 (((_1 & _3) | _{(c&c3)==c}2) | (_{(c&c3)==0}4 & _1))->((_1 | _2) & (_3 | _4))
|
|
461 ((_{(c&c3)==0}4 & _1) | ((_1 & _3) | _{(c&c3)==c}2))->((_1 | _2) & (_3 | _4))
|
|
462 ((_{(c&c3)==c}2 | (_1 & _3)) | (_1 & _{(c&c3)==0}4))->((_1 | _2) & (_3 | _4))
|
|
463 ((_1 & _{(c&c3)==0}4) | (_{(c&c3)==c}2 | (_1 & _3)))->((_1 | _2) & (_3 | _4))
|
|
464 ((_{(c&c3)==c}2 | (_1 & _3)) | (_{(c&c3)==0}4 & _1))->((_1 | _2) & (_3 | _4))
|
|
465 ((_{(c&c3)==0}4 & _1) | (_{(c&c3)==c}2 | (_1 & _3)))->((_1 | _2) & (_3 | _4))
|
|
466 (((_3 & _1) | _{(c&c3)==c}2) | (_1 & _{(c&c3)==0}4))->((_1 | _2) & (_3 | _4))
|
|
467 ((_1 & _{(c&c3)==0}4) | ((_3 & _1) | _{(c&c3)==c}2))->((_1 | _2) & (_3 | _4))
|
|
468 (((_3 & _1) | _{(c&c3)==c}2) | (_{(c&c3)==0}4 & _1))->((_1 | _2) & (_3 | _4))
|
|
469 ((_{(c&c3)==0}4 & _1) | ((_3 & _1) | _{(c&c3)==c}2))->((_1 | _2) & (_3 | _4))
|
|
470 ((_{(c&c3)==c}2 | (_3 & _1)) | (_1 & _{(c&c3)==0}4))->((_1 | _2) & (_3 | _4))
|
|
471 ((_1 & _{(c&c3)==0}4) | (_{(c&c3)==c}2 | (_3 & _1)))->((_1 | _2) & (_3 | _4))
|
|
472 ((_{(c&c3)==c}2 | (_3 & _1)) | (_{(c&c3)==0}4 & _1))->((_1 | _2) & (_3 | _4))
|
|
473 ((_{(c&c3)==0}4 & _1) | (_{(c&c3)==c}2 | (_3 & _1)))->((_1 | _2) & (_3 | _4))
|
|
474 [distribhalfandoveror1]
|
|
475 (((_1 & _2) & _3) | (_1 & _{(c&c3)==0}4))->((_1 & _2) & (_3 | _4))
|
|
476 ((_1 & _{(c&c3)==0}4) | ((_1 & _2) & _3))->((_1 & _2) & (_3 | _4))
|
|
477 (((_1 & _2) & _3) | (_{(c&c3)==0}4 & _1))->((_1 & _2) & (_3 | _4))
|
|
478 ((_{(c&c3)==0}4 & _1) | ((_1 & _2) & _3))->((_1 & _2) & (_3 | _4))
|
|
479 ((_3 & (_1 & _2)) | (_1 & _{(c&c3)==0}4))->((_1 & _2) & (_3 | _4))
|
|
480 ((_1 & _{(c&c3)==0}4) | (_3 & (_1 & _2)))->((_1 & _2) & (_3 | _4))
|
|
481 ((_3 & (_1 & _2)) | (_{(c&c3)==0}4 & _1))->((_1 & _2) & (_3 | _4))
|
|
482 ((_{(c&c3)==0}4 & _1) | (_3 & (_1 & _2)))->((_1 & _2) & (_3 | _4))
|
|
483 (((_2 & _1) & _3) | (_1 & _{(c&c3)==0}4))->((_1 & _2) & (_3 | _4))
|
|
484 ((_1 & _{(c&c3)==0}4) | ((_2 & _1) & _3))->((_1 & _2) & (_3 | _4))
|
|
485 (((_2 & _1) & _3) | (_{(c&c3)==0}4 & _1))->((_1 & _2) & (_3 | _4))
|
|
486 ((_{(c&c3)==0}4 & _1) | ((_2 & _1) & _3))->((_1 & _2) & (_3 | _4))
|
|
487 ((_3 & (_2 & _1)) | (_1 & _{(c&c3)==0}4))->((_1 & _2) & (_3 | _4))
|
|
488 ((_1 & _{(c&c3)==0}4) | (_3 & (_2 & _1)))->((_1 & _2) & (_3 | _4))
|
|
489 ((_3 & (_2 & _1)) | (_{(c&c3)==0}4 & _1))->((_1 & _2) & (_3 | _4))
|
|
490 ((_{(c&c3)==0}4 & _1) | (_3 & (_2 & _1)))->((_1 & _2) & (_3 | _4))
|
|
491 [distribhalfandoveror2]
|
|
492 (((_1 & _3) & _2) | (_1 & _{(c&c3)==0}4))->((_1 & _2) & (_3 | _4))
|
|
493 ((_1 & _{(c&c3)==0}4) | ((_1 & _3) & _2))->((_1 & _2) & (_3 | _4))
|
|
494 (((_1 & _3) & _2) | (_{(c&c3)==0}4 & _1))->((_1 & _2) & (_3 | _4))
|
|
495 ((_{(c&c3)==0}4 & _1) | ((_1 & _3) & _2))->((_1 & _2) & (_3 | _4))
|
|
496 ((_2 & (_1 & _3)) | (_1 & _{(c&c3)==0}4))->((_1 & _2) & (_3 | _4))
|
|
497 ((_1 & _{(c&c3)==0}4) | (_2 & (_1 & _3)))->((_1 & _2) & (_3 | _4))
|
|
498 ((_2 & (_1 & _3)) | (_{(c&c3)==0}4 & _1))->((_1 & _2) & (_3 | _4))
|
|
499 ((_{(c&c3)==0}4 & _1) | (_2 & (_1 & _3)))->((_1 & _2) & (_3 | _4))
|
|
500 (((_3 & _1) & _2) | (_1 & _{(c&c3)==0}4))->((_1 & _2) & (_3 | _4))
|
|
501 ((_1 & _{(c&c3)==0}4) | ((_3 & _1) & _2))->((_1 & _2) & (_3 | _4))
|
|
502 (((_3 & _1) & _2) | (_{(c&c3)==0}4 & _1))->((_1 & _2) & (_3 | _4))
|
|
503 ((_{(c&c3)==0}4 & _1) | ((_3 & _1) & _2))->((_1 & _2) & (_3 | _4))
|
|
504 ((_2 & (_3 & _1)) | (_1 & _{(c&c3)==0}4))->((_1 & _2) & (_3 | _4))
|
|
505 ((_1 & _{(c&c3)==0}4) | (_2 & (_3 & _1)))->((_1 & _2) & (_3 | _4))
|
|
506 ((_2 & (_3 & _1)) | (_{(c&c3)==0}4 & _1))->((_1 & _2) & (_3 | _4))
|
|
507 ((_{(c&c3)==0}4 & _1) | (_2 & (_3 & _1)))->((_1 & _2) & (_3 | _4))
|
|
508
|
|
509 ; A right-shift idiom in syslib that was written in an unneccessarily complex
|
|
510 ; way, by doing the bits separately the same way as left-shifts have to be done
|
|
511 ; (of course, select can right-shift by any difference without much trouble);
|
|
512 ; the next idiom is a helper for that. Previous code produced a warning when
|
|
513 ; this idiom was used, but the optimizer has now been enhanced to the extent
|
|
514 ; that it can deal with it without much special-casing, and therefore there's
|
|
515 ; no way now to tell that that case is being used, so the warning has been
|
|
516 ; removed.
|
|
517 ; lshift32half done in the other direction; note that the large constant here
|
|
518 ; is 0x55555554, not the all-5s number
|
|
519 [rshift32half]
|
|
520 ((_1~#1431655764)$#0)->((_1�)>>#1)
|
|
521 ; and piecing together this with selectmingle4 gives the syslib idiom, which
|
|
522 ; optimizes through distributions over C_OR and then constant folding
|
|
523
|
|
524 ; When a 0 is on one side of a C binary logic operation, or the two sides are
|
|
525 ; the same, simplification is often possible. The and-0 case has been dealt
|
|
526 ; with already.
|
|
527 [noopor]
|
|
528 (_1|#0)->(_1)
|
|
529 (#0|_1)->(_1)
|
|
530 [noopxor]
|
|
531 (_1^#0)->(_1)
|
|
532 (#0^_1)->(_1)
|
|
533 [anditself]
|
|
534 (_1&_1)->(_1)
|
|
535 [oritself]
|
|
536 (_1|_1)->(_1)
|
|
537 [xoritself]
|
|
538 (_1^_1)->(#0)
|
|
539 ; The following four idioms by JH
|
|
540 ((_1^_2)^_1) -> (_2)
|
|
541 ((_2^_1)^_1) -> (_2)
|
|
542 (_1^(_1^_2)) -> (_2)
|
|
543 (_1^(_2^_1)) -> (_2)
|
|
544
|
|
545 ; Equality and inequality
|
|
546 [xortoequal]
|
|
547 (!(_1^_2))->(_1==_2)
|
|
548 [negatingequal]
|
|
549 (!(_1==_2))->(_1!=_2)
|
|
550 (!(_1!=_2))->(_1==_2)
|
|
551
|
|
552 ; Greater than and less than
|
|
553 [greaterthan32]
|
|
554 ((_1~:2)~((?32(:2~:2))^#2147483648))->(_1>(:2^_1))
|
|
555 ((_1~:2)~(#2147483648^(?32(:2~:2))))->(_1>(:2^_1))
|
|
556 [greaterthan16]
|
|
557 ((_1~.2)~((?16(.2~.2))^#32768))->(_1>(.2^_1))
|
|
558 ((_1~.2)~(#32768^(?16(.2~.2))))->(_1>(.2^_1))
|
|
559
|
|
560 ; Consistency in C logical operation nesting, when it doesn't matter
|
|
561 [xoroutsideand]
|
|
562 ((_1^_2)&_2)->((_1&_2)^_2)
|
|
563 (_2&(_1^_2))->((_1&_2)^_2)
|
|
564 ((_2^_1)&_2)->((_1&_2)^_2)
|
|
565 (_2&(_2^_1))->((_1&_2)^_2)
|
|
566
|
|
567 ; Boolean algebra, on 0s and 1s or on 1s and 2s. Unary bitwidth is irrelevant.
|
|
568 [booleannot]
|
|
569 (_{c==1}1^#1)->(!_1)
|
|
570 [not21]
|
|
571 (#2-(!(_{c==1}1)))->(_1+#1)
|
|
572 (#1+(!(_{c==1}1)))->(#2-_1)
|
|
573 ((!(_{c==1}1))+#1)->(#2-_1)
|
|
574 [nullmingle]
|
|
575 (#0$_{c==1}1)->(_1)
|
|
576 ; Thanks to Joris Huizer for suggesting the idea behind the next one;
|
|
577 ; this is a more general idiom than the suggested [triplenot].
|
|
578 [redundantdoublenot]
|
|
579 (!(!(_{c==1}1)))->(_1)
|