Debian Codegraph @

src/theory/bv/rewrites-elimination

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