Mercurial > repo

comparison interps/c-intercal/src/idiotism.oil @ 996:859f9b4339e6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
<Gregor> tar xf egobot.tar.xz
author HackBot
date Sun, 09 Dec 2012 19:30:08 +0000
parents
children
comparison
equal deleted inserted replaced
995:6883f5911eb7 996:859f9b4339e6
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)->(!(!_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&#2863311530)|(#0$_2))
198 [selectmingle2]
199 (_1$(_2~#1431655765))->((_1$#0)|(_2&#1431655765))
200 [selectmingle3]
201 ((_1~#1431655765)$_2)->(((_1&#1431655765)<<#1)|(#0$_2))
202 [selectmingle4]
203 (_1$(_2~#2863311530))->(((_2&#2863311530)>>#1)|(_1$#0))
204 [selectmingle5]
205 ((_{!(c&4294901760UL)}1$_{!(c&4294901760UL)}2)~#3579139412)
206 ->((_1&#32768)|(_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)&#32768)->((_1&#1)<<#15)
212 [xor16and]
213 ((?16 _{!(c&4294934528UL)}1)&#32768)->((_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&#715827882)<<#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&#1431655765)<<#1)|((_1&#715827882)<<#1))->((_1&#2147483647)<<#1)
259 (((#1431655765&_1)<<#1)|((_1&#715827882)<<#1))->((_1&#2147483647)<<#1)
260 (((_1&#1431655765)<<#1)|((#715827882&_1)<<#1))->((_1&#2147483647)<<#1)
261 (((#1431655765&_1)<<#1)|((#715827882&_1)<<#1))->((_1&#2147483647)<<#1)
262 (((_1&#715827882)<<#1)|((_1&#1431655765)<<#1))->((_1&#2147483647)<<#1)
263 (((_1&#715827882)<<#1)|((#1431655765&_1)<<#1))->((_1&#2147483647)<<#1)
264 (((#715827882&_1)<<#1)|((_1&#1431655765)<<#1))->((_1&#2147483647)<<#1)
265 (((#715827882&_1)<<#1)|((#1431655765&_1)<<#1))->((_1&#2147483647)<<#1)
266
267 ; a weird part of a leftshift
268 [lshift32half]
269 (#0$((:1&#2863311530)~#715827883))->((:1&#2863311530)<<#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))&#3)->((_1&#1)+#1)
312 ((?32(_{!(c&4294901760LU)}1$#2))&#3)->(#2-(_1&#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))&#1431655765)<<#1)->((_1&#2863311530)^#2863311530)
332 (((?32(#1431655765|_1))&#1431655765)<<#1)->((_1&#2863311530)^#2863311530)
333 ((#1431655765&(?32(_1|#1431655765)))<<#1)->((_1&#2863311530)^#2863311530)
334 ((#1431655765&(?32(#1431655765|_1)))<<#1)->((_1&#2863311530)^#2863311530)
335 ; Complement even bits, zero odd bits
336 [com0z1]
337 ((?32(((_1&#1431655765)<<#1)|#1431655765))&#1431655765)
338 ->((_1&#1431655765)^#1431655765)
339 ((?32(((#1431655765&_1)<<#1)|#1431655765))&#1431655765)
340 ->((_1&#1431655765)^#1431655765)
341 ((?32(#1431655765|((_1&#1431655765)<<#1)))&#1431655765)
342 ->((_1&#1431655765)^#1431655765)
343 ((?32(#1431655765|((#1431655765&_1)<<#1)))&#1431655765)
344 ->((_1&#1431655765)^#1431655765)
345 (#1431655765&(?32(((_1&#1431655765)<<#1)|#1431655765)))
346 ->((_1&#1431655765)^#1431655765)
347 (#1431655765&(?32(((#1431655765&_1)<<#1)|#1431655765)))
348 ->((_1&#1431655765)^#1431655765)
349 (#1431655765&(?32(#1431655765|((_1&#1431655765)<<#1))))
350 ->((_1&#1431655765)^#1431655765)
351 (#1431655765&(?32(#1431655765|((#1431655765&_1)<<#1))))
352 ->((_1&#1431655765)^#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&#1431655764)>>#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)