Mercurial > repo
view interps/c-intercal/src/idiotism.oil @ 12256:821155c00e34 draft
<fizzie> ` sed -e \'s|wisdom|bin|\' < ../bin/culprits > ../bin/cblprits; chmod a+x ../bin/cblprits
| author | HackEso <hackeso@esolangs.org> |
|---|---|
| date | Sat, 07 Dec 2019 23:36:22 +0000 |
| parents | 859f9b4339e6 |
| children |
line wrap: on
line source
; ; 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)