1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
|
/* State will store states of variables for a function's single execution path.
It will be used for bit-level symbolic execution to determine values of bits
of function's return value and symbolic marked arguments. */
#ifndef SYM_EXEC_STATE_H
#define SYM_EXEC_STATE_H
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "gimple.h"
#include "tree-pass.h"
#include "ssa.h"
#include "gimple-iterator.h"
#include "tree-cfg.h"
#include "tree-ssa-loop-niter.h"
#include "cfgloop.h"
#include "gimple-range.h"
#include "tree-scalar-evolution.h"
#include "hwint.h"
#include "gimple-pretty-print.h"
#include "is-a.h"
#include "vec.h"
#include "hash-map.h"
#include "hash-set.h"
#include "expression.h"
#include "expression-is-a-helper.h"
/* Stores states of variables' values on bit-level. */
class state {
typedef void (state::*binary_func) (vec<value*> * arg1_bits,
vec<value*> * arg2_bits, tree dest);
private:
/* Here is stored values of bit of each variable. */
hash_map<tree, vec < value * >> var_states;
hash_set<bit_expression *> conditions;
vec<value*> create_bits_for_const (tree var, size_t size) const;
void free_bits (vec<value*> * bits) const;
void check_args_compatibility (tree arg1, tree arg2, tree dest);
void do_binary_operation (tree arg1, tree arg2, tree dest,
binary_func bin_func);
void do_and (vec<value*> * arg1_bits, vec<value*> * arg2_bits, tree dest);
void do_or (vec<value*> * arg1_bits, vec<value*> * arg2_bits, tree dest);
void do_xor (vec<value*> * arg1_bits, vec<value*> * arg2_bits, tree dest);
void do_shift_right (vec<value*> * arg1_bits, vec<value*> * arg2_bits,
tree dest);
void do_shift_left (vec<value*> * arg1_bits, vec<value*> * arg2_bits,
tree dest);
void do_add (vec<value*> * arg1_bits, vec<value*> * arg2_bits, tree dest);
void do_sub (vec<value*> * arg1_bits, vec<value*> * arg2_bits, tree dest);
/* Performs AND operation for 2 symbolic_bit operands. */
value *and_sym_bits (const value * var1, const value * var2) const;
/* Performs AND operation for a symbolic_bit and const_bit operands. */
value *and_var_const (const value * var1, const bit * const_bit) const;
/* Performs AND operation for 2 constant bit operands. */
bit *and_const_bits (const bit * const_bit1, const bit * const_bit2) const;
/* Performs OR operation for 2 symbolic_bit operands. */
value *or_sym_bits (const value * var1, const value * var2) const;
/* Performs OR operation for a symbolic_bit and a constant bit operands. */
value *or_var_const (const value * var1, const bit * const_bit) const;
/* Performs OR operation for 2 constant bit operands. */
bit *or_const_bits (const bit * const_bit1, const bit * const_bit2) const;
/* Performs NOT operation for constant bit. */
bit *complement_const_bit (const bit * const_bit) const;
/* Performs NOT operation for symbolic_bit. */
value *complement_sym_bit (const value * var) const;
/* Performs XOR operation for 2 symbolic_bit operands. */
value *xor_sym_bits (const value * var1, const value * var2) const;
/* Performs XOR operation for 2 constant bit operands. */
bit *xor_const_bits (const bit * const_bit1, const bit * const_bit2) const;
/* Performs XOR operation for a symbolic_bit and const_bit operands. */
value *xor_var_const (const value * var, const bit * const_bit) const;
/* shift_right operation. Case: var2 is a sym_bit. */
void shift_right_sym_bits (vec<value*> * arg1_bits, vec<value*> * arg2_bits,
tree dest);
/* shift_left operation. Case: var2 is a sym_bit. */
void shift_left_sym_bits (vec<value*> * arg1_bits, vec<value*> * arg2_bits,
tree dest);
/* Shifts value_vector right by shift_value bits. */
vec <value *> shift_right_by_const (const vec <value *> * value_vector,
size_t shift_value);
/* Return node which has a const bit child. Traversal is done based
on safe branching. */
bit_expression* get_parent_with_const_child (value* root) const;
/* Checks if node is AND, OR or XOR expression. */
bool is_safe_branching (value* node) const;
/* Checks whether state for variable with specified name already
exists or not. */
bool is_declared (tree var);
public:
state ();
~state ();
/* Adds an empty state for the given variable. */
bool decl_var (tree name, unsigned size);
state (const state& s);
bool add_var_state (tree var, vec<value*> * state);
void clear_states ();
void clear_conditions ();
bool add_condition (bit_expression* cond);
bool bulk_add_conditions (const hash_set<bit_expression*>& conds);
vec<value*> * get_bits (tree var);
const hash_set<bit_expression *>& get_conditions ();
/* Adds a variable with unknown value to state. Such variables are
represented as sequence of symbolic bits. */
bool make_symbolic (tree var, unsigned size);
/* Returns size of the given variable. */
unsigned get_var_size (tree var);
/* Does bit-level XOR operation for given variables. */
void do_xor (tree arg1, tree arg2, tree dest);
/* Does bit-level AND operation for given variables. */
void do_and (tree arg1, tree arg2, tree dest);
/* Does bit-level OR operation for given variables. */
void do_or (tree arg1, tree arg2, tree dest);
void do_assign (tree arg, tree dest);
/* Shifts value_vector left by shift_value bits. */
vec <value *> shift_left_by_const (const vec <value *> * value_vector,
size_t shift_value);
/* Checks if all vector elements are const_bit_expressions. */
bool is_bit_vector (vec <value *> * value_vector);
/* Returns the value of the number represented as a bit vector. */
size_t get_value (vec <value *> * bit_vector);
/* Does shift_left operation for given variables. */
void do_shift_left (tree arg1, tree arg2, tree dest);
/* Does shift_right operation for given variables. */
void do_shift_right (tree arg1, tree arg2, tree dest);
/* Adds two variables. */
void do_add (tree arg1, tree arg2, tree dest);
/* Does subtraction. */
void do_sub (tree arg1, tree arg2, tree dest);
/* Negates given variable. */
void do_complement (tree arg, tree dest);
void add_equal_cond (tree arg1, tree arg2);
void add_not_equal_cond (tree arg1, tree arg2);
void add_greater_than_cond (tree arg1, tree arg2);
void add_less_than_cond (tree arg1, tree arg2);
void add_greater_or_equal_cond (tree arg1, tree arg2);
void add_less_or_equal_cond (tree arg1, tree arg2);
void add_bool_cond (tree arg);
bool check_const_bit_equality (vec<value *> * arg1_bits,
vec<value *> * arg2_bits) const;
bool check_const_bit_are_not_equal (vec<value *> * arg1_bits,
vec<value *> * arg2_bits) const;
bool check_const_bit_is_greater_than (vec<value *> * arg1_bits,
vec<value *> * arg2_bits) const;
bool check_const_bit_is_less_than (vec<value *> * arg1_bits,
vec<value *> * arg2_bits) const;
};
#endif /* SYM_EXEC_STATE_H. */
|
