Branch data Line data Source code
1 : : /* Every class defined here represents a single bit value of a variable.
2 : : Every variable will be represented as a vector of these classes which later
3 : : will be used for bit-level symbolic execution.
4 : : Copyright (C) 2022-2024 Free Software Foundation, Inc.
5 : : Contributed by Matevos Mehrabyan <matevosmehrabyan@gmail.com>
6 : :
7 : : This file is part of GCC.
8 : :
9 : : GCC is free software; you can redistribute it and/or modify it under
10 : : the terms of the GNU General Public License as published by the Free
11 : : Software Foundation; either version 3, or (at your option) any later
12 : : version.
13 : :
14 : : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 : : WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 : : for more details.
18 : :
19 : : You should have received a copy of the GNU General Public License
20 : : along with GCC; see the file COPYING3. If not see
21 : : <http://www.gnu.org/licenses/>. */
22 : :
23 : : #ifndef SYM_EXEC_EXPRESSION_H
24 : : #define SYM_EXEC_EXPRESSION_H
25 : :
26 : : #include "config.h"
27 : : #include "system.h"
28 : : #include "coretypes.h"
29 : : #include "backend.h"
30 : : #include "tree.h"
31 : : #include "hwint.h"
32 : : #include "gimple-pretty-print.h"
33 : : #include "is-a.h"
34 : : #include "vec.h"
35 : : #include "hash-map.h"
36 : : #include "hash-set.h"
37 : : #include "stddef.h"
38 : :
39 : : /* Enum used for identifying the class of the bit. */
40 : :
41 : : enum value_type {
42 : : SYMBOLIC_BIT,
43 : : BIT,
44 : : BIT_XOR_EXPRESSION,
45 : : BIT_AND_EXPRESSION,
46 : : BIT_OR_EXPRESSION,
47 : : BIT_COMPLEMENT_EXPRESSION,
48 : : SHIFT_RIGHT_EXPRESSION,
49 : : SHIFT_LEFT_EXPRESSION,
50 : : ADD_EXPRESSION,
51 : : SUB_EXPRESSION,
52 : : BIT_CONDITION
53 : : };
54 : :
55 : :
56 : : /* Base class for single bit value. */
57 : :
58 : : class value_bit {
59 : : protected:
60 : : /* This will help us to understand where is moved the bit
61 : : from its initial position. */
62 : : const size_t m_index;
63 : :
64 : : /* Type of the bit. Used by type checkers. */
65 : : value_type m_type;
66 : :
67 : : public:
68 : :
69 : : /* Default constructor. Sets m_index 0. */
70 : 12930275 : value_bit () : m_index (0)
71 : : {};
72 : :
73 : : /* Constructor that sets m_index to the specified value. */
74 : 9843349 : value_bit (size_t i) : m_index (i)
75 : : {};
76 : :
77 : : /* Copy constructor for value_bit. */
78 : : value_bit (const value_bit &val) : m_index (val.m_index)
79 : : {};
80 : :
81 : : /* Returns the bit's initial index in bit-vector. */
82 : : size_t get_index () const;
83 : :
84 : : /* Returns type of the bit. */
85 : : value_type get_type () const;
86 : :
87 : : /* This will support deep copy of objects' values. */
88 : : virtual value_bit *copy () const = 0;
89 : :
90 : : /* Prints the bit. Inherited classes must implement it. */
91 : : virtual void print () = 0;
92 : :
93 : : /* Destructor. */
94 : 1147982 : virtual ~value_bit () = default;
95 : : };
96 : :
97 : :
98 : : /* Represents value of a single bit of symbolic marked variables. */
99 : :
100 : : class symbolic_bit : public value_bit {
101 : : /* The Origin of the bit. */
102 : : tree m_origin = nullptr;
103 : :
104 : : public:
105 : : /* Constructor that sets the bit's initial position and its origin. */
106 : : symbolic_bit (size_t i, tree orig);
107 : :
108 : : /* Copy constructor for symbolic_bit. */
109 : 8233029 : symbolic_bit (const symbolic_bit &sym_bit) : symbolic_bit (sym_bit.m_index,
110 : 8233029 : sym_bit.m_origin)
111 : : {};
112 : :
113 : : /* Returns a copy of the bit. */
114 : : value_bit *copy () const;
115 : :
116 : : /* Prints the bit. */
117 : : void print ();
118 : :
119 : : /* Returns the origin of the bit, to whom it belongs. */
120 : : tree get_origin ();
121 : : };
122 : :
123 : :
124 : : /* Represents value of a single bit. */
125 : :
126 : 0 : class bit : public value_bit {
127 : : private:
128 : : /* This is the value of a bit. It must be either 1 or 0. */
129 : : unsigned char m_val = 0;
130 : :
131 : : public:
132 : : /* Constructor that sets m_val to the specified value. */
133 : : bit (unsigned char i);
134 : :
135 : : /* Copy constructor for bit. */
136 : 7180478 : bit (const bit &b) : bit (b.m_val)
137 : : {};
138 : :
139 : : /* Returns the value of the bit. */
140 : : unsigned char get_val () const;
141 : :
142 : : /* Sets the value of the bit. */
143 : : void set_val (unsigned char new_val);
144 : :
145 : : /* Return a copy of the bit. */
146 : : value_bit *copy () const;
147 : :
148 : : /* Prints the bit. */
149 : : void print ();
150 : : };
151 : :
152 : :
153 : : /* Bit-level base expression class. In general expressions consist of
154 : : two operands. Here we named them m_left and m_right. */
155 : :
156 : 1049174 : class bit_expression : public value_bit {
157 : : protected:
158 : : /* The bit left to the expression sign. */
159 : : value_bit *m_left = nullptr;
160 : :
161 : : /* The bit right to the expression sign. */
162 : : value_bit *m_right = nullptr;
163 : :
164 : : /* Copies the given expression to it by copying
165 : : the left and right operands. */
166 : : void copy (const bit_expression *expr);
167 : :
168 : : /* Depending on the expression, prints its sign. */
169 : : virtual void print_expr_sign ();
170 : :
171 : : public:
172 : :
173 : : /* Returns left operand of the expression. */
174 : : value_bit *get_left ();
175 : :
176 : : /* Returns right operand of the expression. */
177 : : value_bit *get_right ();
178 : :
179 : : /* Destructor for bit_expression. */
180 : : ~bit_expression ();
181 : :
182 : : /* Sets left operand of the expression. */
183 : : void set_left (value_bit *expr);
184 : :
185 : : /* Sets right operand of the expression. */
186 : : void set_right (value_bit *expr);
187 : :
188 : : /* Returns a deep copy of the expression. */
189 : : value_bit *copy () const = 0;
190 : :
191 : : /* Prints the expression. */
192 : : void print ();
193 : : };
194 : :
195 : :
196 : : /* Bit-level XOR expression. XOR operation on two variables (when one of
197 : : them is symbolic) can be represented by XOR operations on
198 : : each of their bits. */
199 : :
200 : : class bit_xor_expression : public bit_expression {
201 : : public:
202 : : /* Constructor that sets the left and right side bits
203 : : of the bit_xor_expression sign. */
204 : : bit_xor_expression (value_bit *left, value_bit *right);
205 : :
206 : : /* Copy constructor for bit_xor_expression. */
207 : : bit_xor_expression (const bit_xor_expression &expr);
208 : :
209 : : /* Returns a copy of the expression. */
210 : : value_bit *copy () const;
211 : : };
212 : :
213 : :
214 : : /* Bit-level AND expression. AND operation on two variables (when one of
215 : : them is symbolic) can be represented by AND operations on
216 : : each of their bits. */
217 : :
218 : : class bit_and_expression : public bit_expression {
219 : : public:
220 : : /* Constructor that sets the left and right side bits
221 : : of the bit_and_expression sign. */
222 : : bit_and_expression (value_bit *left, value_bit *right);
223 : :
224 : : /* Copy constructor for bit_and_expression. */
225 : : bit_and_expression (const bit_and_expression &expr);
226 : :
227 : : /* Returns a copy of the expression. */
228 : : value_bit *copy () const;
229 : : };
230 : :
231 : :
232 : : /* Bit-level OR expression. OR operation on two variables (when one of
233 : : them is symbolic) can be represented by OR operations on
234 : : each of their bits. */
235 : :
236 : : class bit_or_expression : public bit_expression {
237 : : public:
238 : : /* Constructor that sets the left and right side bits
239 : : of the bit_or_expression sign. */
240 : : bit_or_expression (value_bit *left, value_bit *right);
241 : :
242 : : /* Copy constructor for bit_or_expression. */
243 : : bit_or_expression (const bit_or_expression &expr);
244 : :
245 : : /* Returns a copy of the expression. */
246 : : value_bit *copy () const;
247 : : };
248 : :
249 : :
250 : : /* SHIFT_RIGHT expression. Result must be stored bit by bit. */
251 : :
252 : : class shift_right_expression : public bit_expression {
253 : : public:
254 : : /* Constructor that sets the left and right side bits
255 : : of the shift_right_expression sign. */
256 : : shift_right_expression (value_bit *left, value_bit *right);
257 : :
258 : : /* Copy constructor for shift_right_expression. */
259 : : shift_right_expression (const shift_right_expression &expr);
260 : :
261 : : /* Returns a copy of the expression. */
262 : : value_bit *copy () const;
263 : : };
264 : :
265 : :
266 : : /* SHIFT_LEFT expression. Result must be stored bit by bit. */
267 : :
268 : : class shift_left_expression : public bit_expression {
269 : : public:
270 : : /* Constructor that sets the left and right side bits
271 : : of the shift_left_expression sign. */
272 : : shift_left_expression (value_bit *left, value_bit *right);
273 : :
274 : : /* Copy constructor for shift_left_expression. */
275 : : shift_left_expression (const shift_left_expression &expr);
276 : :
277 : : /* Returns a copy of the expression. */
278 : : value_bit *copy () const;
279 : : };
280 : :
281 : :
282 : : /* ADD expression. Result must be stored bit by bit. */
283 : :
284 : : class add_expression : public bit_expression {
285 : : public:
286 : : /* Constructor that sets the left and right side bits
287 : : of the add_expression sign. */
288 : : add_expression (value_bit *left, value_bit *right);
289 : :
290 : : /* Copy constructor for add_expression. */
291 : : add_expression (const add_expression &expr);
292 : :
293 : : /* Returns a copy of the expression. */
294 : : value_bit *copy () const;
295 : : };
296 : :
297 : :
298 : : /* SUB expression. Result must be stored bit by bit. */
299 : :
300 : : class sub_expression : public bit_expression {
301 : : public:
302 : : /* Constructor that sets the left and right side bits
303 : : of the sub_expression sign. */
304 : : sub_expression (value_bit *left, value_bit *right);
305 : :
306 : : /* Copy constructor for sub_expression. */
307 : : sub_expression (const sub_expression &expr);
308 : :
309 : : /* Returns a copy of the expression. */
310 : : value_bit *copy () const;
311 : : };
312 : :
313 : :
314 : : /* Bit-level negation expression. */
315 : :
316 : : class bit_complement_expression : public bit_expression {
317 : : public:
318 : : /* Constructor that sets the left and right side bits
319 : : of the bit_complement_expression sign. */
320 : : bit_complement_expression (value_bit *right);
321 : :
322 : : /* Copy constructor for bit_complement_expression. */
323 : : bit_complement_expression (const bit_complement_expression &expr);
324 : :
325 : : /* Returns a copy of the expression. */
326 : : value_bit *copy () const;
327 : :
328 : : /* Prints the expression. */
329 : : void print ();
330 : : };
331 : :
332 : : #endif /* SYM_EXEC_EXPRESSION_H. */
|
