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-2026 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 13376174 : value_bit () : m_index (0)
71 : {};
72 :
73 : /* Constructor that sets m_index to the specified value. */
74 10085565 : 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 1166544 : 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 8420413 : symbolic_bit (const symbolic_bit &sym_bit) : symbolic_bit (sym_bit.m_index,
110 8420413 : 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 7403094 : 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 1066138 : 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. */
|
