Common — library colibrilib.bitwise_rules — module Term

The bit–level terms of Dom_genrelbitv (BDD representation), trusted

10
module Term
11
use int.Int
12
use colibrilib.known_bits.KnownBits
13
use list.List
14
use list.Length
15
use option.Option
16
use colibrilib.zarith.Zbit
17
use colibrilib.safe_bits.BitsSpec
18
use colibrilib.bdd.Node
19
use colibrilib.ibdd.IBDD
20
use colibrilib.bddbitv.Export
21
use colibrilib.env.Env
22
use colibrilib.spec.Opt
23
use colibrilib.bv_sem.Sem
24
use colibrilib.bv_dolmen.Dolmen as D

The integer value of a node in d.m for the bit–level terms: the value of an integer or bit–vector node, -1 or 0 for a true or false Boolean node (the scalar of b is -m b)

29
function
ienv
(d:env) (n:Node.t) : int

The term t has the value of the node n in the model of d

32
predicate
is_term
(d:env) (n:Node.t) (t:IBDD.t) =
33
live d -> ienv d n = ivalue t (ienv d)

The term of the node (for a bit–vector of size s, its s bits: 0 <= ienv d n < 2^s): TermSize.monome, proved (the driver binds it)

38
val
monome
(d:env) (n:Node.t) : IBDD.t
39
ensures { is_term d n result }

Dom_genrelbitv.assume_equality: the equation can make the e–graph contradictory. The OCaml function can also raise Unsupported, from int_normalize and int_subst of Pivot (a substitution out of the bounds of the shifts): no specification, its condition depends on the table of the solutions of Pivot, which is not modelled here.

46
val
assume_equality
(d:env) (n:Node.t) (t:IBDD.t) : unit
47
requires { is_term d n t }
48
raises { Contradiction -> not live d }

The rules of r = testbit a k: r is the testbit node of a

51
predicate
is_testbit
(d:env) (r a:Node.t) (k:int) =
52
ienv d r = if Zbit.bittest (ienv d a) k then -1 else 0

s is a size of the node n

55
predicate
has_size
(d:env) (n:Node.t) (s:int) =
56
0 <= s /\ (live d -> 0 <= ienv d n < Zbit.lsl 1 s)

The size of a bit–vector node: TermSize.size, proved (the driver binds it)

60
val
size
(d:env) (n:Node.t) : option int
61
ensures { when_some (has_size d n) result }

The least size of the bit–vector types of the node (Dom_genrelbitv_env.type_size, from Ground.tys)

65
val
type_size
(d:env) (n:Node.t) : option int
66
ensures { when_some (has_size d n) result }

The term of the node of size s (its s bits), or of an unbounded integer (Bddbitv.monome, Bddbitv.int_monome)

70
val
monome_sized
(d:env) (n:Node.t) (s:option int) : IBDD.t
71
requires { when_some (has_size d n) s }
72
ensures { is_term d n result }

The equality of the terms (only to avoid a useless equation)

75
val
same
(a b:IBDD.t) : bool

c is the value of the integer node n

78
predicate
has_int
(d:env) (n:Node.t) (c:int) = live d -> ienv d n = c

The value of an integer node, if known (RealValue)

81
val
int_value
(d:env) (n:Node.t) : option int
82
ensures { when_some (has_int d n) result }

v is the value of the Boolean node n

85
predicate
has_bool
(d:env) (n:Node.t) (v:bool) = live d -> (ienv d n = -1 <-> v)

The value of a Boolean node, if known (Boolean.is)

88
val
bool_value
(d:env) (n:Node.t) : option bool
89
ensures { when_some (has_bool d n) result }

The value in the model of the ground term of the builtin b applied to the nodes l: Sem.code

93
function
vals
(d:env) (l:list Node.t) : list int =
94
match l with Nil -> Nil | Cons x r -> Cons (ienv d x) (vals d r) end
95
96
function
meaning
(d:env) (b:builtin) (l:list Node.t) : int = code b (vals d l)

A ground term (Ground.t) and its node

99
type
ground
100
function
gnode
(g:ground) : Node.t
101
102
val
node
(g:ground) : Node.t
103
ensures { result = gnode g }

g has the value of the builtin applied to the arguments in every model

107
predicate
interprets
(g:ground) (v:(builtin, list Node.t)) =
108
let b, l = v in forall d: env. live d -> ienv d (gnode g) = meaning d b l

The construction of terms

The number of arguments of a builtin

113
function
arity
(b:builtin) : int =
114
match b with
115
| Not | Sbv2int _ | Bv2nat _ | Int2bv _ | BvExtract _ _ _ | BvRepeat _ _
116
| BvZeroExtend _ _ | BvSignExtend _ _ | BvRotl _ _ | BvRotr _ _
117
| BvNot _ | BvNeg _ -> 1
118
| And | Or | Xor | Asr | Test | BvConcat _ _ | BvAnd _ | BvOr _ | BvXor _
119
| BvNand _ | BvNor _ | BvXnor _ | BvComp _ | BvAdd _ | BvSub _ | BvMul _
120
| BvUdiv _ | BvUrem _ | BvSdiv _ | BvSrem _ | BvSmod _ | BvShl _
121
| BvLshr _ | BvAshr _ | BvUlt _ | BvUle _ | BvUgt _ | BvUge _ | BvSlt _
122
| BvSle _ | BvSgt _ | BvSge _ -> 2
123
| Extract | SignedExtract -> 3
124
| Update -> 4
125
end

A term constant of colibri2 (Expr.Term.Const.t, a record of Dolmen) and its Dolmen builtin (its field builtin)

129
type
cst
= private {
builtin
: D.builtin }

The builtin of bv_sem.mlw of a constant, if it has one

132
function
cst_sem
(c:cst) : option builtin = D.of_builtin c.builtin

RealValue_builtin.colibri_testbit_int

135
val
testbit_cst
() : cst
136
ensures { result.builtin = D.Int_Test }

The node of the integer constant k (RealValue.cst)

139
val
int_node
(d:env) (k:int) : Node.t
140
ensures { live d -> ienv d result = k }

Ground.apply' and Egraph.register: the registered node of the term c l, which has the value of the builtin of c applied to l

144
val
apply
(d:env) (c:cst) (l:list Node.t) : Node.t
145
requires { match cst_sem c with Some b -> length l = arity b | None -> false end }
146
ensures { live d -> match cst_sem c with
147
| Some b -> ienv d result = meaning d b l
148
| None -> false end }
149
end