| 1 |
; -- Operator Elimination Rules -- |
| 2 |
|
| 3 |
(define-rule bv-ugt-eliminate |
| 4 |
((x ?BitVec) (y ?BitVec)) |
| 5 |
(bvugt x y) |
| 6 |
(bvult y x)) |
| 7 |
(define-rule bv-uge-eliminate |
| 8 |
((x ?BitVec) (y ?BitVec)) |
| 9 |
(bvuge x y) |
| 10 |
(bvule y x)) |
| 11 |
(define-rule bv-sgt-eliminate |
| 12 |
((x ?BitVec) (y ?BitVec)) |
| 13 |
(bvsgt x y) |
| 14 |
(bvslt y x)) |
| 15 |
(define-rule bv-sge-eliminate |
| 16 |
((x ?BitVec) (y ?BitVec)) |
| 17 |
(bvsge x y) |
| 18 |
(bvsle y x)) |
| 19 |
(define-rule bv-sle-eliminate |
| 20 |
((x ?BitVec) (y ?BitVec)) |
| 21 |
(bvsle x y) |
| 22 |
(not (bvslt y x))) |
| 23 |
|
| 24 |
(define-cond-rule bv-redor-eliminate |
| 25 |
((x ?BitVec) (w Int)) |
| 26 |
(= w (@bvsize x)) |
| 27 |
(bvredor x) |
| 28 |
(bvnot (bvcomp x (@bv 0 w)))) |
| 29 |
(define-cond-rule bv-redand-eliminate |
| 30 |
((x ?BitVec) (w Int)) |
| 31 |
(= w (@bvsize x)) |
| 32 |
(bvredand x) |
| 33 |
(bvcomp x (bvnot (@bv 0 w)))) |
| 34 |
|
| 35 |
(define-rule bv-ule-eliminate |
| 36 |
((x ?BitVec) (y ?BitVec)) |
| 37 |
(bvule x y) |
| 38 |
(not (bvult y x))) |
| 39 |
(define-rule bv-comp-eliminate |
| 40 |
((x ?BitVec) (y ?BitVec)) |
| 41 |
(bvcomp x y) |
| 42 |
(ite (= x y) (@bv 1 1) (@bv 0 1))) |
| 43 |
|
| 44 |
(define-cond-rule bv-rotate-left-eliminate-1 |
| 45 |
((x ?BitVec) (amount Int) (u1 Int) (u2 Int) (l2 Int)) |
| 46 |
(def (n (@bvsize x)) (a (mod amount n))) |
| 47 |
(and (not (= a 0)) (= u1 (- n (+ 1 a))) (= u2 (- n 1)) (= l2 (- n a))) |
| 48 |
(rotate_left amount x) |
| 49 |
(concat |
| 50 |
(extract u1 0 x) |
| 51 |
(extract u2 l2 x))) |
| 52 |
(define-cond-rule bv-rotate-left-eliminate-2 |
| 53 |
((x ?BitVec) (amount Int)) |
| 54 |
(= (mod amount (@bvsize x)) 0) |
| 55 |
(rotate_left amount x) |
| 56 |
x) |
| 57 |
(define-cond-rule bv-rotate-right-eliminate-1 |
| 58 |
((x ?BitVec) (amount Int) (u1 Int) (u2 Int) (l2 Int)) |
| 59 |
(def (n (@bvsize x)) (a (mod amount n))) |
| 60 |
(and (not (= a 0)) (= u1 (- a 1)) (= u2 (- n 1)) (= l2 a)) |
| 61 |
(rotate_right amount x) |
| 62 |
(concat |
| 63 |
(extract u1 0 x) |
| 64 |
(extract u2 l2 x))) |
| 65 |
(define-cond-rule bv-rotate-right-eliminate-2 |
| 66 |
((x ?BitVec) (amount Int)) |
| 67 |
(= (mod amount (@bvsize x)) 0) |
| 68 |
(rotate_right amount x) |
| 69 |
x) |
| 70 |
|
| 71 |
(define-rule bv-nand-eliminate |
| 72 |
((x ?BitVec) (y ?BitVec)) |
| 73 |
(bvnand x y) |
| 74 |
(bvnot (bvand x y))) |
| 75 |
(define-rule bv-nor-eliminate |
| 76 |
((x ?BitVec) (y ?BitVec)) |
| 77 |
(bvnor x y) |
| 78 |
(bvnot (bvor x y))) |
| 79 |
(define-rule bv-xnor-eliminate |
| 80 |
((x ?BitVec) (y ?BitVec)) |
| 81 |
(bvxnor x y) |
| 82 |
(bvnot (bvxor x y))) |
| 83 |
|
| 84 |
(define-cond-rule bv-sdiv-eliminate |
| 85 |
((x ?BitVec) (y ?BitVec) (nm1 Int)) |
| 86 |
(def |
| 87 |
(xLt0 (= (extract nm1 nm1 x) (@bv 1 1))) |
| 88 |
(yLt0 (= (extract nm1 nm1 y) (@bv 1 1))) |
| 89 |
(rUdiv (bvudiv (ite xLt0 (bvneg x) x) (ite yLt0 (bvneg y) y))) |
| 90 |
) |
| 91 |
(= nm1 (- (@bvsize x) 1)) |
| 92 |
(bvsdiv x y) |
| 93 |
(ite (xor xLt0 yLt0) (bvneg rUdiv) rUdiv)) |
| 94 |
|
| 95 |
(define-rule bv-zero-extend-eliminate |
| 96 |
((x ?BitVec) (n Int)) |
| 97 |
(zero_extend n x) |
| 98 |
(concat (@bv 0 n) x)) |
| 99 |
|
| 100 |
(define-cond-rule bv-uaddo-eliminate |
| 101 |
((x ?BitVec) (y ?BitVec) (w Int)) |
| 102 |
(= w (@bvsize x)) |
| 103 |
(bvuaddo x y) |
| 104 |
(= (extract w w |
| 105 |
(bvadd (concat (@bv 0 1) x) (concat (@bv 0 1) y))) |
| 106 |
(@bv 1 1) |
| 107 |
)) |
| 108 |
(define-cond-rule bv-saddo-eliminate |
| 109 |
((x ?BitVec) (y ?BitVec) (wm1 Int)) |
| 110 |
(def |
| 111 |
(xS (extract wm1 wm1 x)) |
| 112 |
(yS (extract wm1 wm1 y)) |
| 113 |
(aS (extract wm1 wm1 (bvadd x y))) |
| 114 |
) |
| 115 |
(= wm1 (- (@bvsize x) 1)) |
| 116 |
(bvsaddo x y) |
| 117 |
(or |
| 118 |
(and (and (= xS (@bv 1 1)) (= yS (@bv 1 1))) (= aS (@bv 0 1))) |
| 119 |
(and (and (= xS (@bv 0 1)) (= yS (@bv 0 1))) (= aS (@bv 1 1))) |
| 120 |
)) |
| 121 |
(define-cond-rule bv-sdivo-eliminate |
| 122 |
((x ?BitVec) (y ?BitVec) (w Int) (wm1 Int)) |
| 123 |
(and (= wm1 (- (@bvsize x) 1)) (= w (@bvsize y))) |
| 124 |
(bvsdivo x y) |
| 125 |
(and |
| 126 |
(= x (concat (@bv 1 1) (@bv 0 wm1))) |
| 127 |
(= y (bvnot (@bv 0 w))) |
| 128 |
)) |
| 129 |
(define-cond-rule bv-smod-eliminate |
| 130 |
((x ?BitVec) (y ?BitVec) (w Int) (wm1 Int)) |
| 131 |
(def |
| 132 |
(xLt0 (= (extract wm1 wm1 x) (@bv 1 1))) |
| 133 |
(yLt0 (= (extract wm1 wm1 y) (@bv 1 1))) |
| 134 |
(nxLt0 (= (extract wm1 wm1 x) (@bv 0 1))) |
| 135 |
(nyLt0 (= (extract wm1 wm1 y) (@bv 0 1))) |
| 136 |
(xAbs (ite nxLt0 x (bvneg x))) |
| 137 |
(yAbs (ite nyLt0 y (bvneg y))) |
| 138 |
(u (bvurem xAbs yAbs)) |
| 139 |
) |
| 140 |
(and (= w (@bvsize x)) (= wm1 (- (@bvsize x) 1))) |
| 141 |
(bvsmod x y) |
| 142 |
(ite (= u (@bv 0 w)) |
| 143 |
u |
| 144 |
(ite (and nxLt0 nyLt0) |
| 145 |
u |
| 146 |
(ite (and xLt0 nyLt0) |
| 147 |
(bvadd (bvneg u) y) |
| 148 |
(ite (and nxLt0 yLt0) |
| 149 |
(bvadd u y) |
| 150 |
(bvneg u)))))) |
| 151 |
|
| 152 |
(define-cond-rule bv-srem-eliminate |
| 153 |
((x ?BitVec) (y ?BitVec) (nm1 Int)) |
| 154 |
(def |
| 155 |
(xLt0 (= (extract nm1 nm1 x) (@bv 1 1))) |
| 156 |
(yLt0 (= (extract nm1 nm1 y) (@bv 1 1))) |
| 157 |
(xAbs (ite xLt0 (bvneg x) x)) |
| 158 |
(yAbs (ite yLt0 (bvneg y) y)) |
| 159 |
(u (bvurem xAbs yAbs)) |
| 160 |
) |
| 161 |
(= nm1 (- (@bvsize x) 1)) |
| 162 |
(bvsrem x y) |
| 163 |
(ite xLt0 (bvneg u) u)) |
| 164 |
|
| 165 |
(define-cond-rule bv-usubo-eliminate |
| 166 |
((x ?BitVec) (y ?BitVec) (n Int)) |
| 167 |
(def |
| 168 |
(s (bvsub (zero_extend 1 x) (zero_extend 1 y))) |
| 169 |
) |
| 170 |
(= n (@bvsize x)) |
| 171 |
(bvusubo x y) |
| 172 |
(= (extract n n s) (@bv 1 1))) |
| 173 |
; Overflow occurs when |
| 174 |
; 1. (N - P) = P |
| 175 |
; 2. (P - N) = N |
| 176 |
(define-cond-rule bv-ssubo-eliminate |
| 177 |
((x ?BitVec) (y ?BitVec) (nm1 Int)) |
| 178 |
(def |
| 179 |
(n (@bvsize x)) |
| 180 |
(xe (extract nm1 nm1 x)) |
| 181 |
(ye (extract nm1 nm1 y)) |
| 182 |
(s (bvsub x y)) |
| 183 |
(se (extract nm1 nm1 s)) |
| 184 |
) |
| 185 |
(= nm1 (- n 1)) |
| 186 |
(bvssubo x y) |
| 187 |
(or |
| 188 |
(and (and (= xe (@bv 1 1)) (= ye (@bv 0 1))) (= se (@bv 0 1))) |
| 189 |
(and (and (= xe (@bv 0 1)) (= ye (@bv 1 1))) (= se (@bv 1 1))))) |
| 190 |
|
| 191 |
(define-cond-rule bv-nego-eliminate |
| 192 |
((x ?BitVec) (n Int)) |
| 193 |
(= n (- (@bvsize x) 1)) |
| 194 |
(bvnego x) |
| 195 |
(= x (concat (@bv 1 1) (@bv 0 n)))) |