Mercurial > repo
diff interps/c-intercal/src/idiotism.oil @ 996:859f9b4339e6
<Gregor> tar xf egobot.tar.xz
| author | HackBot |
|---|---|
| date | Sun, 09 Dec 2012 19:30:08 +0000 |
| parents | |
| children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/interps/c-intercal/src/idiotism.oil Sun Dec 09 19:30:08 2012 +0000 @@ -0,0 +1,579 @@ +; +; NAME +; idiotism.oil -- optimizer idioms for C-INTERCAL +; +; LICENSE TERMS +; Copyright (C) 2007 Alex Smith +; +; This program is free software; you can redistribute it and/or modify +; it under the terms of the GNU General Public License as published by +; the Free Software Foundation; either version 2 of the License, or +; (at your option) any later version. +; +; This program is distributed in the hope that it will be useful, +; but WITHOUT ANY WARRANTY; without even the implied warranty of +; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +; GNU General Public License for more details. +; +; You should have received a copy of the GNU General Public License +; along with this program; if not, write to the Free Software +; Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. +; + +; Optimizer Idiom Language input file for C-INTERCAL + +; See the appendix "Optimizer Idiom Language" in the Revamped manual +; for information about the format of this file. + +; Some useful constants: +; 0x55555555 1431655765 +; 0xAAAAAAAA 2863311530 +; 0x0000FFFF 65535 +; 0xFFFF0000 4294901760 +; 0xFFFFFFFF 4294967295 + +; Constant folding +[minglefold] +(#{1}1$#{1}2)->(#{mingle(x1,x2)}0) +[selectfold] +(#{1}1~#{1}2)->(#{iselect(x1,x2)}0) +[and32fold] +(&32 #{1}1)->(#{and32(x1)}0) +[or32fold] +(V32 #{1}1)->(#{or32(x1)}0) +[xor32fold] +(?32 #{1}1)->(#{xor32(x1)}0) +[and16fold] +(&16 #{1}1)->(#{and16(x1)}0) +[or16fold] +(V16 #{1}1)->(#{or16(x1)}0) +[xor16fold] +(?16 #{1}1)->(#{xor16(x1)}0) +; C operations can, and should, be folded too +[cfold] +(#{1}1 & #{1}2)->(#{x1 & x2}0) +(#{1}1 | #{1}2)->(#{x1 | x2}0) +(#{1}1 ^ #{1}2)->(#{x1 ^ x2}0) +(#{1}1 + #{1}2)->(#{x1 + x2}0) +(#{1}1 - #{1}2)->(#{x1 - x2}0) +(#{1}1 * #{1}2)->(#{x1 * x2}0) +(#{1}1 / #{1}2)->(#{x1 / x2}0) +(#{1}1 % #{1}2)->(#{x1 % x2}0) +(#{1}1 > #{1}2)->(#{x1 > x2}0) +(#{1}1 < #{1}2)->(#{x1 < x2}0) +(#{1}1 >> #{1}2)->(#{x1 >> x2}0) +(#{1}1 << #{1}2)->(#{x1 << x2}0) +(#{1}1 == #{1}2)->(#{x1 == x2}0) +(#{1}1 != #{1}2)->(#{x1 != x2}0) + +; Reducing constants inside a C or operation can help to recognize idioms +[cfoldintoorinand] +(((_1) | #{1}2) & #{1}3)->(((_1) | #{x2 & x3}0) & _3) + +; Binary bitwise optimizations +[cbinand] +((&32(_{!(c&4294901760LU)}1$_{!(c&4294901760LU)}2))~ + #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3 +)->((_1 & _2) & #{iselect(x3,1431655765LU)}0) +[cbinor] +((V32(_{!(c&4294901760LU)}1$_{!(c&4294901760LU)}2))~ + #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3 +)->((_1 | _2) & #{iselect(x3,1431655765LU)}0) +[cbinxor] +((?32(_{!(c&4294901760LU)}1$_{!(c&4294901760LU)}2))~ + #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3 +)->((_1 ^ _2) & #{iselect(x3,1431655765LU)}0) +; Sometimes, an expanded output is wanted, optimizations happen in the wrong +; order, and we end up with & rather than ~ on the previous idiom. Correct +; such situations now. +[cbinandnoselect] +((&32(_{!(c&4294901760LU)}1$_{!(c&4294901760LU)}2))& + #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3 +)->(#0 $ ((_1 & _2) & #{iselect(x3,1431655765LU)}0)) +[cbinornoselect] +((V32(_{!(c&4294901760LU)}1$_{!(c&4294901760LU)}2))& + #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3 +)->(#0 $ ((_1 | _2) & #{iselect(x3,1431655765LU)}0)) +[cbinxornoselect] +((?32(_{!(c&4294901760LU)}1$_{!(c&4294901760LU)}2))& + #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3 +)->(#0 $ ((_1 ^ _2) & #{iselect(x3,1431655765LU)}0)) +; Sometimes, there isn't even a mingle... +[cbinandnomingle] +((&32(_{!(c&2863311530LU)}1|_{!(c&1431655765LU)}2))~ + #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3 +)->(((_2 >> #1) & _1) ~ _3) +((&32(_{!(c&1431655765LU)}2|_{!(c&2863311530LU)}1))~ + #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3 +)->(((_2 >> #1) & _1) ~ _3) +((&32(_{!(c&2863311530LU)}1|_{!(c&1431655765LU)}2))& + #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3 +)->(((_2 >> #1) & _1) & _3) +((&32(_{!(c&1431655765LU)}2|_{!(c&2863311530LU)}1))& + #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3 +)->(((_2 >> #1) & _1) & _3) +[cbinornomingle] +((V32(_{!(c&2863311530LU)}1|_{!(c&1431655765LU)}2))~ + #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3 +)->(((_2 >> #1) | _1) ~ _3) +((V32(_{!(c&1431655765LU)}2|_{!(c&2863311530LU)}1))~ + #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3 +)->(((_2 >> #1) | _1) ~ _3) +((V32(_{!(c&2863311530LU)}1|_{!(c&1431655765LU)}2))& + #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3 +)->(((_2 >> #1) | _1) & _3) +((V32(_{!(c&1431655765LU)}2|_{!(c&2863311530LU)}1))& + #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3 +)->(((_2 >> #1) | _1) & _3) +[cbinxornomingle] +((?32(_{!(c&2863311530LU)}1|_{!(c&1431655765LU)}2))~ + #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3 +)->(((_2 >> #1) ^ _1) ~ _3) +((?32(_{!(c&1431655765LU)}2|_{!(c&2863311530LU)}1))~ + #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3 +)->(((_2 >> #1) ^ _1) ~ _3) +((?32(_{!(c&2863311530LU)}1|_{!(c&1431655765LU)}2))& + #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3 +)->(((_2 >> #1) ^ _1) & _3) +((?32(_{!(c&1431655765LU)}2|_{!(c&2863311530LU)}1))& + #{!(x&2863311530LU)&&iselect(x,1431655765LU)==xselx(iselect(x,1431655765LU))}3 +)->(((_2 >> #1) ^ _1) & _3) + +; Bitwise complements. (The INTERCAL which ultimately leads to cases 3 and 4 +; is not the most efficient way to do this, by the way.) +[cnot1] +(#65535 ^ .{!(c&4294901760LU)}1)->(~16 .1) +[cnot2] +(.{!(c&4294901760LU)}1 ^ #65535)->(~16 .1) +[cnot3] +(#4294967295 ^ :1)->(~32 :1) +[cnot4] +(:1 ^ #4294967295)->(~32 :1) + +; bitwise logical equivalence +[cxorand16] +((.1 ^ _2) & _2)->((~16 .1) & _2) +((_2 ^ .1) & _2)->((~16 .1) & _2) +((.1 & _2) ^ _2)->((~16 .1) & _2) +((_2 & .1) ^ _2)->((~16 .1) & _2) +(_2 ^ (.1 & _2))->((~16 .1) & _2) +(_2 ^ (_2 & .1))->((~16 .1) & _2) +(_2 & (.1 ^ _2))->((~16 .1) & _2) +(_2 & (_2 ^ .1))->((~16 .1) & _2) +[cxorand32] +((:1 ^ _2) & _2)->((~32 _1) & _2) +((_2 ^ :1) & _2)->((~32 _1) & _2) +((:1 & _2) ^ _2)->((~32 _1) & _2) +((_2 & :1) ^ _2)->((~32 _1) & _2) +(_2 ^ (:1 & _2))->((~32 _1) & _2) +(_2 ^ (_2 & :1))->((~32 _1) & _2) +(_2 & (:1 ^ _2))->((~32 _1) & _2) +(_2 & (_2 ^ :1))->((~32 _1) & _2) + +; Special cases of select + +; Selecting the rightmost bits of a number +[xselpow2m1] +(_1 ~ #{x==xselx(x)}2)->(_1 & _2) +; Selecting one bit from a number +[xselpow2] +(_1 ~ #{xselx(x)==1}2)->(!(!(_1 & _2))) +; Selecting a number against itself and then selecting 1 from that +[xselxsel1] +((_1~_1)~#1)->(!(!_1)) +((_1~_1))->(!(!_1)) +(#1&(_1~_1))->(!(!_1)) +((_1~_1)&_{c==1}2)->(_1 && _2) +(_{c==1}2&(_1~_1))->(_1 && _2) +; Selecting a number from a constant that's just below a power of 2 +[pow2m1selx] +((#{x==xselx(x)}1 ~ _2) ~ #1)->(!(!(_1 & _2))) +; Boolean-negating a select +[notselect] +(!(_1~_2))->(!(_1&_2)) + +; Sometimes select and mingle cancel each other out +[selectmingle1] +((_1~#2863311530)$_2)->((_1�)|(#0$_2)) +[selectmingle2] +(_1$(_2~#1431655765))->((_1$#0)|(_2�)) +[selectmingle3] +((_1~#1431655765)$_2)->(((_1�)<<#1)|(#0$_2)) +[selectmingle4] +(_1$(_2~#2863311530))->(((_2�)>>#1)|(_1$#0)) +[selectmingle5] +((_{!(c&4294901760UL)}1$_{!(c&4294901760UL)}2)~#3579139412) +->((_1耀)|(_2>>#1)) + +; special cases of V16/?16; the top bit was 0, so becomes equal to the +; bottom bit +[or16and] +((V16 _{!(c&4294934528UL)}1)耀)->((_1)<<#15) +[xor16and] +((?16 _{!(c&4294934528UL)}1)耀)->((_1)<<#15) + +; Shifts + +; A helper in calculating 32-bit shifts; this is a shift on half the bits of +; a 32-bit number. +[lshift32half] +(#0$((_1~#715827882)<<#1))->((_1�)<<#1) +; Rightshift some of the bits +[rshift] +<#1-#31 +(_1~#{xselx(x)<<r==x&&x}2)->((_1&_2)>>#{r}0) +> +; General 16-bit leftshifts +; +; Large left-shifts can be written in an optimized way using knowledge of the +; rightmost bits to shift more than one bit at a time. +; If the rightmost few bits of a number are known to be 0, it can be mingled +; with 0, and then selected with a number which has many 0s to do a leftshift. +; Here, if none of the bits marked l are set this is a right-shift by 3, and +; for each bit set, the shift goes 1 leftwards. +; (xxxxxxxxxxxxxttt $ 000000000000uuuu) ~ (h0h0h0h0h0h0h0h0h0h0h0h01lllllll) +; x0x0x0x0x0x0x0x0x0x0x0x0xutututu +; h0h0h0h0h0h0h0h0h0h0h0h01lllllll +; There's three cases here for each possible width for the ts, including one +; which has them as zeros and two which have them higher. +[lshift16] +<#0-#14 +((_{c<=65535&&!(c&((1LU<<r)-1LU))}1$ + #{!(x&(4294967294LU<<r))}2)~#{!(x&(1431655765LU<<(r*2+2)))}3) +->((((_1>>#{r}0)~#{iselect(x3>>(r*2+1),1431655765LU)}0) + <<#{setbitcount(x3&((2LU<<(r*2))-1))}0)|#{iselect(mingle(0,x2),x3)}0) +(((_{c<=65535&&!(c&((1LU<<r)-1LU))}1|#{x<=65535&&!(c&~((1LU<<r)-1LU))}4)$ + #{!(x&(4294967294LU<<r))}2)~#{!(x&(1431655765LU<<(r*2+2)))}3) +->((((_1>>#{r}0)~#{iselect(x3>>(r*2+1),1431655765LU)}0) + <<#{setbitcount(x3&((2LU<<(r*2))-1))}0)|#{iselect(mingle(x4,x2),x3)}0) +(((#{x<=65535&&!(c&~((1LU<<r)-1LU))}4|_{c<=65535&&!(c&((1LU<<r)-1LU))}1)$ + #{!(x&(4294967294LU<<r))}2)~#{!(x&(1431655765LU<<(r*2+2)))}3) +->((((_1>>#{r}0)~#{iselect(x3>>(r*2+1),1431655765LU)}0) + <<#{setbitcount(x3&((2LU<<(r*2))-1))}0)|#{iselect(mingle(x4,x2),x3)}0) +> + + +; 32-bit leftshift by 1; there are 8 ways to write this. +[lshift32by1] +(((_1�)<<#1)|((_1�)<<#1))->((_1�)<<#1) +(((#1431655765&_1)<<#1)|((_1�)<<#1))->((_1�)<<#1) +(((_1�)<<#1)|((#715827882&_1)<<#1))->((_1�)<<#1) +(((#1431655765&_1)<<#1)|((#715827882&_1)<<#1))->((_1�)<<#1) +(((_1�)<<#1)|((_1�)<<#1))->((_1�)<<#1) +(((_1�)<<#1)|((#1431655765&_1)<<#1))->((_1�)<<#1) +(((#715827882&_1)<<#1)|((_1�)<<#1))->((_1�)<<#1) +(((#715827882&_1)<<#1)|((#1431655765&_1)<<#1))->((_1�)<<#1) + +; a weird part of a leftshift +[lshift32half] +(#0$((:1�)~#715827883))->((:1�)<<#1) + +; Move rshift, AND out of neg +[rshiftoutofneg] +(~16 (.1 >> #{1}2))->(((~16 .1) >> _2) | #32768) +(~32 (:1 >> #{1}2))->(((~32 :1) >> _2) | #2147483648) +[andoutofneg] +(~16 (.1 & #{1}2))->(((~16 .1) & _2) | #{(~x2)&65535}0) +(~32 (:1 & #{1}2))->(((~32 :1) & _2) | #{~x2}0) + +; Move AND inside shifts, and OR and XOR outside shifts +[andintoshift] +((_1 << #{1}2) & #{1}3)->((_1 & #{x3>>x2}0) << _2) +((_1 >> #{1}2) & #{1}3)->((_1 & #{x3<<x2}0) >> _2) +[oroutofshift] +((_1 | #{1}2) << #{1}3)->((_1 << _3) | #{x2<<x3}0) +((_1 | #{1}2) >> #{1}3)->((_1 >> _3) | #{x2>>x3}0) +[xoroutofshift] +((_1 ^ #{1}2) << #{1}3)->((_1 << _3) ^ #{x2<<x3}0) +((_1 ^ #{1}2) >> #{1}3)->((_1 >> _3) ^ #{x2>>x3}0) +; Larger leftshifts can be created by combining smaller ones, although there +; are shortcuts that can be used and this idiom only works if they haven't +; been. Also, idioms later on can create shifts that cancel each other out, so +; the code for cancelling them is here. +[combinellshift] +((_1 << #{1}2) << #{1}3)->(_1 << #{x2+x3}0) +[combinelrshift] +((_1 << #{1}2) >> #{x>x2}3)->(_1 >> #{x3-x2}0) +((_1 << #{1}2) >> #{x==x2}3)->(_1) +((_1 << #{1}2) >> #{x<x2}3)->(_1 << #{x2-x3}0) +[combinerlshift] +((_1 >> #{1}2) << #{x>x2}3)->(_1 << #{x3-x2}0) +((_1 >> #{1}2) << #{x==x2}3)->(_1) +((_1 >> #{1}2) << #{x<x2}3)->(_1 >> #{x2-x3}0) +[combinerrshift] +((_1 >> #{1}2) >> #{1}3)->(_1 >> #{x2+x3}0) +[nullshift] +(_1 >> #0)->(_1) +(_1 << #0)->(_1) + +; INTERCAL logical values are 1 and 2. +[xorto1or2] +((?32(_{!(c&4294901760LU)}1$#1)))->((_1)+#1) +((?32(_{!(c&4294901760LU)}1$#2)))->(#2-(_1)) + +; Removing, combining and weakening unneeded C_ANDs +[unneededand] +(_1&#{!(c1&~x)}0)->(_1) +(#{!(c1&~x)}0&_1)->(_1) +[combineand] +((_1&#{1}2)&#{1}3)->(_1&#{x2&x3}0) +((#{1}2&_1)&#{1}3)->(_1&#{x2&x3}0) +(#{1}3&(_1&#{1}2))->(_1&#{x2&x3}0) +(#{1}3&(#{1}2&_1))->(_1&#{x2&x3}0) +[weakenand] +(_1&#{(~c1)&x}2)->(_1&#{c1&x2}0) +(#{(~c1)&x}2&_1)->(_1&#{c1&x2}0) + +; 32-bit complements + +; Complement odd bits, zero even bits +[com1z0] +(((?32(_1|#1431655765))�)<<#1)->((_1�)^#2863311530) +(((?32(#1431655765|_1))�)<<#1)->((_1�)^#2863311530) +((#1431655765&(?32(_1|#1431655765)))<<#1)->((_1�)^#2863311530) +((#1431655765&(?32(#1431655765|_1)))<<#1)->((_1�)^#2863311530) +; Complement even bits, zero odd bits +[com0z1] +((?32(((_1�)<<#1)|#1431655765))�) +->((_1�)^#1431655765) +((?32(((#1431655765&_1)<<#1)|#1431655765))�) +->((_1�)^#1431655765) +((?32(#1431655765|((_1�)<<#1)))�) +->((_1�)^#1431655765) +((?32(#1431655765|((#1431655765&_1)<<#1)))�) +->((_1�)^#1431655765) +(#1431655765&(?32(((_1�)<<#1)|#1431655765))) +->((_1�)^#1431655765) +(#1431655765&(?32(((#1431655765&_1)<<#1)|#1431655765))) +->((_1�)^#1431655765) +(#1431655765&(?32(#1431655765|((_1�)<<#1)))) +->((_1�)^#1431655765) +(#1431655765&(?32(#1431655765|((#1431655765&_1)<<#1)))) +->((_1�)^#1431655765) +; 32-bit complements, in full +[cnot5] +(((:1&#{1}2)^#{x==x2}0)|((:1&#{(x^x2)==4294967295LU}3)^#{x==x3}0))->(~32 :1) + +; Distributive laws + +; Several of these laws go towards helping finish off 32-bit C binary logical +; operations, but are useful in other places as well (especially distributions +; involving shifts). +[distribll] +((_1&_3)&(_2&_3))->((_1&_2)&_3) +((_1|_3)&(_2|_3))->((_1&_2)|_3) +((_1&_3)|(_2&_3))->((_1|_2)&_3) +((_1|_3)|(_2|_3))->((_1|_2)|_3) +((_1&_3)^(_2&_3))->((_1^_2)&_3) +((_1<<_3)&(_2<<_3))->((_1&_2)<<_3) +((_1<<_3)|(_2<<_3))->((_1|_2)<<_3) +((_1<<_3)^(_2<<_3))->((_1^_2)<<_3) +((_1>>_3)&(_2>>_3))->((_1&_2)>>_3) +((_1>>_3)|(_2>>_3))->((_1|_2)>>_3) +((_1>>_3)^(_2>>_3))->((_1^_2)>>_3) +[distribrl] +((_3&_1)&(_2&_3))->((_1&_2)&_3) +((_3|_1)&(_2|_3))->((_1&_2)|_3) +((_3&_1)|(_2&_3))->((_1|_2)&_3) +((_3|_1)|(_2|_3))->((_1|_2)|_3) +((_3&_1)^(_2&_3))->((_1^_2)&_3) +[distriblr] +((_1&_3)&(_3&_2))->((_1&_2)&_3) +((_1|_3)&(_3|_2))->((_1&_2)|_3) +((_1&_3)|(_3&_2))->((_1|_2)&_3) +((_1|_3)|(_3|_2))->((_1|_2)|_3) +((_1&_3)^(_3&_2))->((_1^_2)&_3) +[distribrr] +((_3&_1)&(_3&_2))->((_1&_2)&_3) +((_3|_1)&(_3|_2))->((_1&_2)|_3) +((_3&_1)|(_3&_2))->((_1|_2)&_3) +((_3|_1)|(_3|_2))->((_1|_2)|_3) +((_3&_1)^(_3&_2))->((_1^_2)&_3) +[distribunary] +((!_1)&(!_2))->(!(_1|_2)) + +; 32-bit C binary logical operations + +; Strangely enough, these can be done for the most part with the combined +; effect of many small optimizations (of course, that's the best way to do it). +; The only potential problem is that the distributive law isn't quite general +; enough for some cases involving constants, and for some cases where one side +; or the other is known to have no set evenbits or no set oddbits. +; Some generalised versions of the distributive law are needed here. +; Unfortunately, there are lots of binary operators here that need to be +; written both ways round. The 96 cases that follow, combined with weakenand, +; should be enough for all but the most pathological cases. +[distribhalfxoroveror1] +(((_1 ^ _2) & _3) | (_1 & _{(c&c3)==0}4))->((_1 ^ _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | ((_1 ^ _2) & _3))->((_1 ^ _2) & (_3 | _4)) +(((_1 ^ _2) & _3) | (_{(c&c3)==0}4 & _1))->((_1 ^ _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | ((_1 ^ _2) & _3))->((_1 ^ _2) & (_3 | _4)) +((_3 & (_1 ^ _2)) | (_1 & _{(c&c3)==0}4))->((_1 ^ _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | (_3 & (_1 ^ _2)))->((_1 ^ _2) & (_3 | _4)) +((_3 & (_1 ^ _2)) | (_{(c&c3)==0}4 & _1))->((_1 ^ _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | (_3 & (_1 ^ _2)))->((_1 ^ _2) & (_3 | _4)) +(((_2 ^ _1) & _3) | (_1 & _{(c&c3)==0}4))->((_1 ^ _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | ((_2 ^ _1) & _3))->((_1 ^ _2) & (_3 | _4)) +(((_2 ^ _1) & _3) | (_{(c&c3)==0}4 & _1))->((_1 ^ _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | ((_2 ^ _1) & _3))->((_1 ^ _2) & (_3 | _4)) +((_3 & (_2 ^ _1)) | (_1 & _{(c&c3)==0}4))->((_1 ^ _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | (_3 & (_2 ^ _1)))->((_1 ^ _2) & (_3 | _4)) +((_3 & (_2 ^ _1)) | (_{(c&c3)==0}4 & _1))->((_1 ^ _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | (_3 & (_2 ^ _1)))->((_1 ^ _2) & (_3 | _4)) +[distribhalfxoroveror2] +(((_1 & _3) ^ _{(c&c3)==c}2) | (_1 & _{(c&c3)==0}4))->((_1 ^ _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | ((_1 & _3) ^ _{(c&c3)==c}2))->((_1 ^ _2) & (_3 | _4)) +(((_1 & _3) ^ _{(c&c3)==c}2) | (_{(c&c3)==0}4 & _1))->((_1 ^ _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | ((_1 & _3) ^ _{(c&c3)==c}2))->((_1 ^ _2) & (_3 | _4)) +((_{(c&c3)==c}2 ^ (_1 & _3)) | (_1 & _{(c&c3)==0}4))->((_1 ^ _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | (_{(c&c3)==c}2 ^ (_1 & _3)))->((_1 ^ _2) & (_3 | _4)) +((_{(c&c3)==c}2 ^ (_1 & _3)) | (_{(c&c3)==0}4 & _1))->((_1 ^ _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | (_{(c&c3)==c}2 ^ (_1 & _3)))->((_1 ^ _2) & (_3 | _4)) +(((_3 & _1) ^ _{(c&c3)==c}2) | (_1 & _{(c&c3)==0}4))->((_1 ^ _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | ((_3 & _1) ^ _{(c&c3)==c}2))->((_1 ^ _2) & (_3 | _4)) +(((_3 & _1) ^ _{(c&c3)==c}2) | (_{(c&c3)==0}4 & _1))->((_1 ^ _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | ((_3 & _1) ^ _{(c&c3)==c}2))->((_1 ^ _2) & (_3 | _4)) +((_{(c&c3)==c}2 ^ (_3 & _1)) | (_1 & _{(c&c3)==0}4))->((_1 ^ _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | (_{(c&c3)==c}2 ^ (_3 & _1)))->((_1 ^ _2) & (_3 | _4)) +((_{(c&c3)==c}2 ^ (_3 & _1)) | (_{(c&c3)==0}4 & _1))->((_1 ^ _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | (_{(c&c3)==c}2 ^ (_3 & _1)))->((_1 ^ _2) & (_3 | _4)) +[distribhalforoveror1] +(((_1 | _2) & _3) | (_1 & _{(c&c3)==0}4))->((_1 | _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | ((_1 | _2) & _3))->((_1 | _2) & (_3 | _4)) +(((_1 | _2) & _3) | (_{(c&c3)==0}4 & _1))->((_1 | _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | ((_1 | _2) & _3))->((_1 | _2) & (_3 | _4)) +((_3 & (_1 | _2)) | (_1 & _{(c&c3)==0}4))->((_1 | _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | (_3 & (_1 | _2)))->((_1 | _2) & (_3 | _4)) +((_3 & (_1 | _2)) | (_{(c&c3)==0}4 & _1))->((_1 | _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | (_3 & (_1 | _2)))->((_1 | _2) & (_3 | _4)) +(((_2 | _1) & _3) | (_1 & _{(c&c3)==0}4))->((_1 | _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | ((_2 | _1) & _3))->((_1 | _2) & (_3 | _4)) +(((_2 | _1) & _3) | (_{(c&c3)==0}4 & _1))->((_1 | _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | ((_2 | _1) & _3))->((_1 | _2) & (_3 | _4)) +((_3 & (_2 | _1)) | (_1 & _{(c&c3)==0}4))->((_1 | _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | (_3 & (_2 | _1)))->((_1 | _2) & (_3 | _4)) +((_3 & (_2 | _1)) | (_{(c&c3)==0}4 & _1))->((_1 | _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | (_3 & (_2 | _1)))->((_1 | _2) & (_3 | _4)) +[distribhalforoveror2] +(((_1 & _3) | _{(c&c3)==c}2) | (_1 & _{(c&c3)==0}4))->((_1 | _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | ((_1 & _3) | _{(c&c3)==c}2))->((_1 | _2) & (_3 | _4)) +(((_1 & _3) | _{(c&c3)==c}2) | (_{(c&c3)==0}4 & _1))->((_1 | _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | ((_1 & _3) | _{(c&c3)==c}2))->((_1 | _2) & (_3 | _4)) +((_{(c&c3)==c}2 | (_1 & _3)) | (_1 & _{(c&c3)==0}4))->((_1 | _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | (_{(c&c3)==c}2 | (_1 & _3)))->((_1 | _2) & (_3 | _4)) +((_{(c&c3)==c}2 | (_1 & _3)) | (_{(c&c3)==0}4 & _1))->((_1 | _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | (_{(c&c3)==c}2 | (_1 & _3)))->((_1 | _2) & (_3 | _4)) +(((_3 & _1) | _{(c&c3)==c}2) | (_1 & _{(c&c3)==0}4))->((_1 | _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | ((_3 & _1) | _{(c&c3)==c}2))->((_1 | _2) & (_3 | _4)) +(((_3 & _1) | _{(c&c3)==c}2) | (_{(c&c3)==0}4 & _1))->((_1 | _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | ((_3 & _1) | _{(c&c3)==c}2))->((_1 | _2) & (_3 | _4)) +((_{(c&c3)==c}2 | (_3 & _1)) | (_1 & _{(c&c3)==0}4))->((_1 | _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | (_{(c&c3)==c}2 | (_3 & _1)))->((_1 | _2) & (_3 | _4)) +((_{(c&c3)==c}2 | (_3 & _1)) | (_{(c&c3)==0}4 & _1))->((_1 | _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | (_{(c&c3)==c}2 | (_3 & _1)))->((_1 | _2) & (_3 | _4)) +[distribhalfandoveror1] +(((_1 & _2) & _3) | (_1 & _{(c&c3)==0}4))->((_1 & _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | ((_1 & _2) & _3))->((_1 & _2) & (_3 | _4)) +(((_1 & _2) & _3) | (_{(c&c3)==0}4 & _1))->((_1 & _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | ((_1 & _2) & _3))->((_1 & _2) & (_3 | _4)) +((_3 & (_1 & _2)) | (_1 & _{(c&c3)==0}4))->((_1 & _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | (_3 & (_1 & _2)))->((_1 & _2) & (_3 | _4)) +((_3 & (_1 & _2)) | (_{(c&c3)==0}4 & _1))->((_1 & _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | (_3 & (_1 & _2)))->((_1 & _2) & (_3 | _4)) +(((_2 & _1) & _3) | (_1 & _{(c&c3)==0}4))->((_1 & _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | ((_2 & _1) & _3))->((_1 & _2) & (_3 | _4)) +(((_2 & _1) & _3) | (_{(c&c3)==0}4 & _1))->((_1 & _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | ((_2 & _1) & _3))->((_1 & _2) & (_3 | _4)) +((_3 & (_2 & _1)) | (_1 & _{(c&c3)==0}4))->((_1 & _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | (_3 & (_2 & _1)))->((_1 & _2) & (_3 | _4)) +((_3 & (_2 & _1)) | (_{(c&c3)==0}4 & _1))->((_1 & _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | (_3 & (_2 & _1)))->((_1 & _2) & (_3 | _4)) +[distribhalfandoveror2] +(((_1 & _3) & _2) | (_1 & _{(c&c3)==0}4))->((_1 & _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | ((_1 & _3) & _2))->((_1 & _2) & (_3 | _4)) +(((_1 & _3) & _2) | (_{(c&c3)==0}4 & _1))->((_1 & _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | ((_1 & _3) & _2))->((_1 & _2) & (_3 | _4)) +((_2 & (_1 & _3)) | (_1 & _{(c&c3)==0}4))->((_1 & _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | (_2 & (_1 & _3)))->((_1 & _2) & (_3 | _4)) +((_2 & (_1 & _3)) | (_{(c&c3)==0}4 & _1))->((_1 & _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | (_2 & (_1 & _3)))->((_1 & _2) & (_3 | _4)) +(((_3 & _1) & _2) | (_1 & _{(c&c3)==0}4))->((_1 & _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | ((_3 & _1) & _2))->((_1 & _2) & (_3 | _4)) +(((_3 & _1) & _2) | (_{(c&c3)==0}4 & _1))->((_1 & _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | ((_3 & _1) & _2))->((_1 & _2) & (_3 | _4)) +((_2 & (_3 & _1)) | (_1 & _{(c&c3)==0}4))->((_1 & _2) & (_3 | _4)) +((_1 & _{(c&c3)==0}4) | (_2 & (_3 & _1)))->((_1 & _2) & (_3 | _4)) +((_2 & (_3 & _1)) | (_{(c&c3)==0}4 & _1))->((_1 & _2) & (_3 | _4)) +((_{(c&c3)==0}4 & _1) | (_2 & (_3 & _1)))->((_1 & _2) & (_3 | _4)) + +; A right-shift idiom in syslib that was written in an unneccessarily complex +; way, by doing the bits separately the same way as left-shifts have to be done +; (of course, select can right-shift by any difference without much trouble); +; the next idiom is a helper for that. Previous code produced a warning when +; this idiom was used, but the optimizer has now been enhanced to the extent +; that it can deal with it without much special-casing, and therefore there's +; no way now to tell that that case is being used, so the warning has been +; removed. +; lshift32half done in the other direction; note that the large constant here +; is 0x55555554, not the all-5s number +[rshift32half] +((_1~#1431655764)$#0)->((_1�)>>#1) +; and piecing together this with selectmingle4 gives the syslib idiom, which +; optimizes through distributions over C_OR and then constant folding + +; When a 0 is on one side of a C binary logic operation, or the two sides are +; the same, simplification is often possible. The and-0 case has been dealt +; with already. +[noopor] +(_1|#0)->(_1) +(#0|_1)->(_1) +[noopxor] +(_1^#0)->(_1) +(#0^_1)->(_1) +[anditself] +(_1&_1)->(_1) +[oritself] +(_1|_1)->(_1) +[xoritself] +(_1^_1)->(#0) +; The following four idioms by JH +((_1^_2)^_1) -> (_2) +((_2^_1)^_1) -> (_2) +(_1^(_1^_2)) -> (_2) +(_1^(_2^_1)) -> (_2) + +; Equality and inequality +[xortoequal] +(!(_1^_2))->(_1==_2) +[negatingequal] +(!(_1==_2))->(_1!=_2) +(!(_1!=_2))->(_1==_2) + +; Greater than and less than +[greaterthan32] +((_1~:2)~((?32(:2~:2))^#2147483648))->(_1>(:2^_1)) +((_1~:2)~(#2147483648^(?32(:2~:2))))->(_1>(:2^_1)) +[greaterthan16] +((_1~.2)~((?16(.2~.2))^#32768))->(_1>(.2^_1)) +((_1~.2)~(#32768^(?16(.2~.2))))->(_1>(.2^_1)) + +; Consistency in C logical operation nesting, when it doesn't matter +[xoroutsideand] +((_1^_2)&_2)->((_1&_2)^_2) +(_2&(_1^_2))->((_1&_2)^_2) +((_2^_1)&_2)->((_1&_2)^_2) +(_2&(_2^_1))->((_1&_2)^_2) + +; Boolean algebra, on 0s and 1s or on 1s and 2s. Unary bitwidth is irrelevant. +[booleannot] +(_{c==1}1^#1)->(!_1) +[not21] +(#2-(!(_{c==1}1)))->(_1+#1) +(#1+(!(_{c==1}1)))->(#2-_1) +((!(_{c==1}1))+#1)->(#2-_1) +[nullmingle] +(#0$_{c==1}1)->(_1) +; Thanks to Joris Huizer for suggesting the idea behind the next one; +; this is a more general idiom than the suggested [triplenot]. +[redundantdoublenot] +(!(!(_{c==1}1)))->(_1)