;
; 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]
(#{x<=65535}1$#{x<=65535}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)
(! #{1}1)->(#{!x1}0)

; Reducing constants inside a C or operation can help to recognize idioms
[cfoldintoorinand]
(((_1) | #{(x != (x & x3))}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)
[cxorandmixed]
; This requires typecasting .1 to 32 bits.
((.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)
[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~_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&#2863311530)|(#0$_2))
[selectmingle2]
(_1$(_2~#1431655765))->((_1$#0)|(_2&#1431655765))
[selectmingle3]
((_1~#1431655765)$_2)->(((_1&#1431655765)<<#1)|(#0$_2))
[selectmingle4]
(_1$(_2~#2863311530))->(((_2&#2863311530)>>#1)|(_1$#0))
[selectmingle5]
;3579139412=0xd5555554
((_{!(c&4294901760UL)}1$_{!(c&4294901760UL)}2)~#3579139412)
->((_1&#32768)|(_2>>#1))

; special cases of V16/?16; the top bit was 0, so becomes equal to the
; bottom bit
[or16and]
((V16 _{!(c&4294934528UL)}1)&#32768)->((_1&#1)<<#15)
[xor16and]
((?16 _{!(c&4294934528UL)}1)&#32768)->((_1&#1)<<#15)

; Shifts

; 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)
>

; 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&#715827882)<<#1)
(#0$((:1&#2863311530)~#715827883))->((:1&#2863311530)<<#1)

; 32-bit leftshift by 1; there are 8 ways to write this.
[lshift32by1]
(((_1&#1431655765)<<#1)|((_1&#715827882)<<#1))->((_1&#2147483647)<<#1)
(((#1431655765&_1)<<#1)|((_1&#715827882)<<#1))->((_1&#2147483647)<<#1)
(((_1&#1431655765)<<#1)|((#715827882&_1)<<#1))->((_1&#2147483647)<<#1)
(((#1431655765&_1)<<#1)|((#715827882&_1)<<#1))->((_1&#2147483647)<<#1)
(((_1&#715827882)<<#1)|((_1&#1431655765)<<#1))->((_1&#2147483647)<<#1)
(((_1&#715827882)<<#1)|((#1431655765&_1)<<#1))->((_1&#2147483647)<<#1)
(((#715827882&_1)<<#1)|((_1&#1431655765)<<#1))->((_1&#2147483647)<<#1)
(((#715827882&_1)<<#1)|((#1431655765&_1)<<#1))->((_1&#2147483647)<<#1)

; Move rshift, AND out of neg
[rshiftoutofneg]
(~16 (.1 >> #1))->(((~16 .1) >> #1) | #32768)
(~32 (:1 >> #1))->(((~32 :1) >> #1) | #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]
((.{65535LU>>x2 >= c}1 << #{1}2) >> #{x>x2}3)->(.1 >> #{x3-x2}0)
((.{65535LU>>x2 >= c}1 << #{1}2) >> #{x==x2}3)->(.1)
((.{65535LU>>x2 >= c}1 << #{1}2) >> #{x<x2}3)->(.1 << #{x2-x3}0)
((:{4294967295LU>>x2 >= c}1 << #{1}2) >> #{x>x2}3)->(:1 >> #{x3-x2}0)
((:{4294967295LU>>x2 >= c}1 << #{1}2) >> #{x==x2}3)->(:1)
((:{4294967295LU>>x2 >= c}1 << #{1}2) >> #{x<x2}3)->(:1 << #{x2-x3}0)
[combinerlshift]
((_{!(((1LU<<x2)-1)&c)}1 >> #{1}2) << #{x>x2}3)->(_1 << #{x3-x2}0)
((_{!(((1LU<<x2)-1)&c)}1 >> #{1}2) << #{x==x2}3)->(_1)
((_{!(((1LU<<x2)-1)&c)}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))&#3)->((_1&#1)+#1)
((?32(_{!(c&4294901760LU)}1$#2))&#3)->(#2-(_1&#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))&#1431655765)<<#1)->((_1&#2863311530)^#2863311530)
(((?32(#1431655765|_1))&#1431655765)<<#1)->((_1&#2863311530)^#2863311530)
((#1431655765&(?32(_1|#1431655765)))<<#1)->((_1&#2863311530)^#2863311530)
((#1431655765&(?32(#1431655765|_1)))<<#1)->((_1&#2863311530)^#2863311530)
; Complement even bits, zero odd bits
[com0z1]
((?32(((_1&#1431655765)<<#1)|#1431655765))&#1431655765)
->((_1&#1431655765)^#1431655765)
((?32(((#1431655765&_1)<<#1)|#1431655765))&#1431655765)
->((_1&#1431655765)^#1431655765)
((?32(#1431655765|((_1&#1431655765)<<#1)))&#1431655765)
->((_1&#1431655765)^#1431655765)
((?32(#1431655765|((#1431655765&_1)<<#1)))&#1431655765)
->((_1&#1431655765)^#1431655765)
(#1431655765&(?32(((_1&#1431655765)<<#1)|#1431655765)))
->((_1&#1431655765)^#1431655765)
(#1431655765&(?32(((#1431655765&_1)<<#1)|#1431655765)))
->((_1&#1431655765)^#1431655765)
(#1431655765&(?32(#1431655765|((_1&#1431655765)<<#1))))
->((_1&#1431655765)^#1431655765)
(#1431655765&(?32(#1431655765|((#1431655765&_1)<<#1))))
->((_1&#1431655765)^#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 & (_3 | _4)) ^ (_2 & _3))
((_1 & _{(c&c3)==0}4) | ((_1 ^ _2) & _3))->((_1 & (_3 | _4)) ^ (_2 & _3))
(((_1 ^ _2) & _3) | (_{(c&c3)==0}4 & _1))->((_1 & (_3 | _4)) ^ (_2 & _3))
((_{(c&c3)==0}4 & _1) | ((_1 ^ _2) & _3))->((_1 & (_3 | _4)) ^ (_2 & _3))
((_3 & (_1 ^ _2)) | (_1 & _{(c&c3)==0}4))->((_1 & (_3 | _4)) ^ (_2 & _3))
((_1 & _{(c&c3)==0}4) | (_3 & (_1 ^ _2)))->((_1 & (_3 | _4)) ^ (_2 & _3))
((_3 & (_1 ^ _2)) | (_{(c&c3)==0}4 & _1))->((_1 & (_3 | _4)) ^ (_2 & _3))
((_{(c&c3)==0}4 & _1) | (_3 & (_1 ^ _2)))->((_1 & (_3 | _4)) ^ (_2 & _3))
(((_2 ^ _1) & _3) | (_1 & _{(c&c3)==0}4))->((_1 & (_3 | _4)) ^ (_2 & _3))
((_1 & _{(c&c3)==0}4) | ((_2 ^ _1) & _3))->((_1 & (_3 | _4)) ^ (_2 & _3))
(((_2 ^ _1) & _3) | (_{(c&c3)==0}4 & _1))->((_1 & (_3 | _4)) ^ (_2 & _3))
((_{(c&c3)==0}4 & _1) | ((_2 ^ _1) & _3))->((_1 & (_3 | _4)) ^ (_2 & _3))
((_3 & (_2 ^ _1)) | (_1 & _{(c&c3)==0}4))->((_1 & (_3 | _4)) ^ (_2 & _3))
((_1 & _{(c&c3)==0}4) | (_3 & (_2 ^ _1)))->((_1 & (_3 | _4)) ^ (_2 & _3))
((_3 & (_2 ^ _1)) | (_{(c&c3)==0}4 & _1))->((_1 & (_3 | _4)) ^ (_2 & _3))
((_{(c&c3)==0}4 & _1) | (_3 & (_2 ^ _1)))->((_1 & (_3 | _4)) ^ (_2 & _3))
[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))
; We require bits in common between 1 and 2 to prevent an infinite loop;
; otherwise this swaps (1<=>3, 2<=>4) indefinitely.
[distribhalforoveror1]
(((_1 | _{c&c1}2) & _3) | (_1 & _{(c&c3)==0}4))->((_1 & (_3 | _4)) | (_2 & _3))
((_1 & _{(c&c3)==0}4) | ((_1 | _{c&c1}2) & _3))->((_1 & (_3 | _4)) | (_2 & _3))
(((_1 | _{c&c1}2) & _3) | (_{(c&c3)==0}4 & _1))->((_1 & (_3 | _4)) | (_2 & _3))
((_{(c&c3)==0}4 & _1) | ((_1 | _{c&c1}2) & _3))->((_1 & (_3 | _4)) | (_2 & _3))
((_3 & (_1 | _{c&c1}2)) | (_1 & _{(c&c3)==0}4))->((_1 & (_3 | _4)) | (_2 & _3))
((_1 & _{(c&c3)==0}4) | (_3 & (_1 | _{c&c1}2)))->((_1 & (_3 | _4)) | (_2 & _3))
((_3 & (_1 | _{c&c1}2)) | (_{(c&c3)==0}4 & _1))->((_1 & (_3 | _4)) | (_2 & _3))
((_{(c&c3)==0}4 & _1) | (_3 & (_1 | _{c&c1}2)))->((_1 & (_3 | _4)) | (_2 & _3))
(((_{c&c1}2 | _1) & _3) | (_1 & _{(c&c3)==0}4))->((_1 & (_3 | _4)) | (_2 & _3))
((_1 & _{(c&c3)==0}4) | ((_{c&c1}2 | _1) & _3))->((_1 & (_3 | _4)) | (_2 & _3))
(((_{c&c1}2 | _1) & _3) | (_{(c&c3)==0}4 & _1))->((_1 & (_3 | _4)) | (_2 & _3))
((_{(c&c3)==0}4 & _1) | ((_{c&c1}2 | _1) & _3))->((_1 & (_3 | _4)) | (_2 & _3))
((_3 & (_{c&c1}2 | _1)) | (_1 & _{(c&c3)==0}4))->((_1 & (_3 | _4)) | (_2 & _3))
((_1 & _{(c&c3)==0}4) | (_3 & (_{c&c1}2 | _1)))->((_1 & (_3 | _4)) | (_2 & _3))
((_3 & (_{c&c1}2 | _1)) | (_{(c&c3)==0}4 & _1))->((_1 & (_3 | _4)) | (_2 & _3))
((_{(c&c3)==0}4 & _1) | (_3 & (_{c&c1}2 | _1)))->((_1 & (_3 | _4)) | (_2 & _3))
[distribhalforoveror2]
(((_1 & _3) | _2) | (_1 & _{(c&c3)==0}4))->((_1 & (_3 | _4)) | _2)
((_1 & _{(c&c3)==0}4) | ((_1 & _3) | _2))->((_1 & (_3 | _4)) | _2)
(((_1 & _3) | _2) | (_{(c&c3)==0}4 & _1))->((_1 & (_3 | _4)) | _2)
((_{(c&c3)==0}4 & _1) | ((_1 & _3) | _2))->((_1 & (_3 | _4)) | _2)
((_2 | (_1 & _3)) | (_1 & _{(c&c3)==0}4))->((_1 & (_3 | _4)) | _2)
((_1 & _{(c&c3)==0}4) | (_2 | (_1 & _3)))->((_1 & (_3 | _4)) | _2)
((_2 | (_1 & _3)) | (_{(c&c3)==0}4 & _1))->((_1 & (_3 | _4)) | _2)
((_{(c&c3)==0}4 & _1) | (_2 | (_1 & _3)))->((_1 & (_3 | _4)) | _2)
(((_3 & _1) | _2) | (_1 & _{(c&c3)==0}4))->((_1 & (_3 | _4)) | _2)
((_1 & _{(c&c3)==0}4) | ((_3 & _1) | _2))->((_1 & (_3 | _4)) | _2)
(((_3 & _1) | _2) | (_{(c&c3)==0}4 & _1))->((_1 & (_3 | _4)) | _2)
((_{(c&c3)==0}4 & _1) | ((_3 & _1) | _2))->((_1 & (_3 | _4)) | _2)
((_2 | (_3 & _1)) | (_1 & _{(c&c3)==0}4))->((_1 & (_3 | _4)) | _2)
((_1 & _{(c&c3)==0}4) | (_2 | (_3 & _1)))->((_1 & (_3 | _4)) | _2)
((_2 | (_3 & _1)) | (_{(c&c3)==0}4 & _1))->((_1 & (_3 | _4)) | _2)
((_{(c&c3)==0}4 & _1) | (_2 | (_3 & _1)))->((_1 & (_3 | _4)) | _2)
[distribhalfandoveror1]
(((_1 & _2) & _3) | (_1 & _{(c&c3)==0}4))->(((_3 & _2) | _4) & _1)
((_1 & _{(c&c3)==0}4) | ((_1 & _2) & _3))->(((_3 & _2) | _4) & _1)
(((_1 & _2) & _3) | (_{(c&c3)==0}4 & _1))->(((_3 & _2) | _4) & _1)
((_{(c&c3)==0}4 & _1) | ((_1 & _2) & _3))->(((_3 & _2) | _4) & _1)
((_3 & (_1 & _2)) | (_1 & _{(c&c3)==0}4))->(((_3 & _2) | _4) & _1)
((_1 & _{(c&c3)==0}4) | (_3 & (_1 & _2)))->(((_3 & _2) | _4) & _1)
((_3 & (_1 & _2)) | (_{(c&c3)==0}4 & _1))->(((_3 & _2) | _4) & _1)
((_{(c&c3)==0}4 & _1) | (_3 & (_1 & _2)))->(((_3 & _2) | _4) & _1)
(((_2 & _1) & _3) | (_1 & _{(c&c3)==0}4))->(((_3 & _2) | _4) & _1)
((_1 & _{(c&c3)==0}4) | ((_2 & _1) & _3))->(((_3 & _2) | _4) & _1)
(((_2 & _1) & _3) | (_{(c&c3)==0}4 & _1))->(((_3 & _2) | _4) & _1)
((_{(c&c3)==0}4 & _1) | ((_2 & _1) & _3))->(((_3 & _2) | _4) & _1)
((_3 & (_2 & _1)) | (_1 & _{(c&c3)==0}4))->(((_3 & _2) | _4) & _1)
((_1 & _{(c&c3)==0}4) | (_3 & (_2 & _1)))->(((_3 & _2) | _4) & _1)
((_3 & (_2 & _1)) | (_{(c&c3)==0}4 & _1))->(((_3 & _2) | _4) & _1)
((_{(c&c3)==0}4 & _1) | (_3 & (_2 & _1)))->(((_3 & _2) | _4) & _1)
[distribhalfandoveror2]
(((_1 & _3) & _2) | (_1 & _{(c&c3)==0}4))->(((_3 & _2) | _4) & _1)
((_1 & _{(c&c3)==0}4) | ((_1 & _3) & _2))->(((_3 & _2) | _4) & _1)
(((_1 & _3) & _2) | (_{(c&c3)==0}4 & _1))->(((_3 & _2) | _4) & _1)
((_{(c&c3)==0}4 & _1) | ((_1 & _3) & _2))->(((_3 & _2) | _4) & _1)
((_2 & (_1 & _3)) | (_1 & _{(c&c3)==0}4))->(((_3 & _2) | _4) & _1)
((_1 & _{(c&c3)==0}4) | (_2 & (_1 & _3)))->(((_3 & _2) | _4) & _1)
((_2 & (_1 & _3)) | (_{(c&c3)==0}4 & _1))->(((_3 & _2) | _4) & _1)
((_{(c&c3)==0}4 & _1) | (_2 & (_1 & _3)))->(((_3 & _2) | _4) & _1)
(((_3 & _1) & _2) | (_1 & _{(c&c3)==0}4))->(((_3 & _2) | _4) & _1)
((_1 & _{(c&c3)==0}4) | ((_3 & _1) & _2))->(((_3 & _2) | _4) & _1)
(((_3 & _1) & _2) | (_{(c&c3)==0}4 & _1))->(((_3 & _2) | _4) & _1)
((_{(c&c3)==0}4 & _1) | ((_3 & _1) & _2))->(((_3 & _2) | _4) & _1)
((_2 & (_3 & _1)) | (_1 & _{(c&c3)==0}4))->(((_3 & _2) | _4) & _1)
((_1 & _{(c&c3)==0}4) | (_2 & (_3 & _1)))->(((_3 & _2) | _4) & _1)
((_2 & (_3 & _1)) | (_{(c&c3)==0}4 & _1))->(((_3 & _2) | _4) & _1)
((_{(c&c3)==0}4 & _1) | (_2 & (_3 & _1)))->(((_3 & _2) | _4) & _1)

; 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&#1431655764)>>#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.
[noopor]
(_1|#0)->(_1)
(#0|_1)->(_1)
[noopxor]
(_1^#0)->(_1)
(#0^_1)->(_1)
[anditself]
(_1&_1)->(_1)
[and0]
(_1&#0)->(#0)
(#0&_1)->(#0)
[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)